Final

Question 1

It is not always possible to convert a finite horizon MDP to an infinite horizon MDP.

Answer 1

False. You can always convert a terminal state into an absorbing state with a transition to itself and reward 0

Question 2

In RL, recent moves influence outcomes more than moves further in the past.

Answer 2

False as you can lose a game (like the chess game that was mentioned by prof. Isbell in one of the earliest videos) at the beginning and no matter how perfectly you play it afterwards, you might still lose it.
Anonymous

Question 3

An MDP given a fixed policy is a Markov chain with rewards.

Answer 3

True since fixed policy means the agent doesn’t have an option to choose an action in each state. The agent transitions from state to state according to this fixed policy (without choosing any actions) which is Markov chain.

Question 4

f we know the optimal Q values, we can get the optimal V values only if we know the environment’s transition function/matrix.

Answer 4

False, you don’t need the transition function.

Question 5

In the gridworld MDP in “Smoov and Curly’s Bogus Journey”, if we add 10 to each state’s reward (terminal and non-terminal) the optimal policy will not change.

Answer 5

True, assuming an infinite horizon the optimal policy will be unchanged

Question 6

Markov means RL agents are amnesiacs and forget everything up until the current state.

Answer 6

True here: the current state is all the agent should know.

Now if you want to discuss what a “current state” is… Well that can get more complicated.

Question 7

A policy that is greedy–with respect to the optimal value function–is not necessarily an optimal policy.

Answer 7

false. optimal action, on optimal value function, is by definition, optimal.

Question 8

In TD learning, the sum of the learning rates used must converge for the value function to converge.

Answer 8

False

Question 9

Monte Carlo is an unbiased estimator of the value function compared to TD methods. Therefore, it is the preferred algorithm when doing RL with episodic tasks.

Answer 9

False. As pointed out, there are other things you might want to consider as well…

Question 10

The value of the returned policy is the only metric we care about when evaluating a learner.

Answer 10

False. This is kind of subjective. I would say, machine time, data efficiency, the experience required from data scientists are all additional things to consider.

Question 11

T/F POMDP allow us to strike a balance actions to gan reward and actions to gain information

Answer 11

TRUE this was all folded into one model (there was not special info to do this)

Question 12

T/F DEC-POMDPS allow us to wrap coordinating and communicating into choosing actions to maximize utility

Answer 12

TRUE

Question 13

DEC-POMDP stands for

Answer 13

Decentralized Partially Observable Markov Decisions

Question 14

The primary difference between POMDPs and DEC-POMDPS

Answer 14

Actions are taken simultaneously by a finite set of agents (not just 1) in DEC-POMDPS

Question 15

DEC-POMDPS vs POSG

Answer 15

DEC-POMDP all share reward function (they are working together)

Question 16

T/F DEC-POMDPs are represented by Ri (diff reward for each agent)

Answer 16

FALSE, there is a shared Reward (all agents working together). If reward wasn’t shared the model would be POSG

Question 17

Properties of DEC-POMDP

Answer 17

1. Elements of game theory and POMDPS

2. NEXP-complete (for finite horizon)

Question 18

Inverse RL

Answer 18

Input behavior and environment and OUTPUT reward

Question 19

MLRL

Answer 19

Guess R, compute policy, measure probability of data given policy, compute gradient R to find how to change reward to make it fit the data better

Question 20

In reward shaping, if the human believes X, Y, Z with 2/3, 1/6, 1/6 and the algorithm believes 1/10, 1/10, 8/10. What action should they choose?

Answer 20

Choose action Z because pairwise product is highest. Argmax p(a|poliicy1)*p(a|policy2)

Question 21

Drama Management

Answer 21

There is a 3rd agent, the “Author” that wants to build an agent that interferes with the player. Author created packman, agent is game itself, player is player obvi

Question 22

TTD-MDPs vs MDPs

Answer 22

rather than states as, have trajectories (sequence so far) and rather than rewards, have target distribution p(T).

Question 23

Value Iteration Algorithm

Answer 23

Start w/ arbitrary utilities
Update utilities based on reward + neighbors (discounted future reward)
Repeat until convergence

Question 24

Supervised Learning

Answer 24

y = f(x). Function approximation, find f that maps y to x

Question 25

Unsupervised Learning

Answer 25

f(c). Clusters descripition

Question 26

Reinforcement Learning

Answer 26

y = f(x) but given x and z. Still trying to find f to generate y. We see so r is the z

Question 27

MDP stands for

Answer 27

Markov Decision Processes.

Question 28

MDPs are made up of

Answer 28

States, transitions (model), actions, rewards and create a policy.

Question 29

Markovian Property

Answer 29

Only the present matters AND things are stationary (rules/the world doesn't change over time)

Question 30

Delayed Rewards

Answer 30

In chess example, if you make a bad move early on that you can never recover from. That bad move needs to be reflected in the reward

Question 31

Temporal Credit Assignment Problem

Answer 31

the problem of determining the actions that lead to a certain outcome in sequence

Question 32

How to change policies to account for finite horizons

Answer 32

Policy(s,t).. policy is function of state AND time

Question 33

Utility of Sequences (stationary preferences)

Answer 33

if you prefer one sequence of states over another today, you prefer the same sequence tomorrow

Question 34

How to calculate infinite horizons without infinity?

Answer 34

Use discounted future rewards (use gamma)

Question 35

Reward vs Utility

Answer 35

Reward is immediate payoff of state. Utility is long term payoff of action, it takes into account delayed reward

Question 36

Policy Iteration

Answer 36

start with initial policy (guess) evaluate: given policy, calculate utility improve: Policy at t+1 is the action that maximizes the utility

Question 37

T/F Policy Iteration won't converge

Answer 37

False

Question 38

On Policy vs Off-Policy

Answer 38

off policy estimates the q values (state-action value) directly from the Q function regardless of the policy being followed by the agent. (Q-learning) on-policy is that it updates its Q-values using the Q-value of the next state 𝑠′ and the current policy's action 𝑎″. It estimates the return for state-action pairs assuming the current policy continues to be followed. (SARSA)

Question 39

T/F TD update rule always converges with any learning rate

Answer 39

False. It will converge if you sum all of the learning rates at each time, t > infinity and if you sum all the learning rates squared at time < infinity

Question 40

T/F TD(1) is the same as outcome-based updates (if no repeated states)

Answer 40

True. and with even more learning because updates don't have to wait for the episode to be over

Question 41

Maximum Likelihood Estimate vs outcome-based estimate (TD(1))

Answer 41

Maximum Likelihood uses all of the examples, but TD(1) uses just individual runs so if a rare thing happens on TD(1) it can be biased (high variance). (this leads us to TD(lambda)

Question 42

T/F TD(0) is the same as maximum likelihood estimate

Answer 42

TRUE if we run over the data over and over again

Question 43

T/F TD(lambda) is weighted combination of k step estimators

Answer 43

True

Question 44

T/F TD(1) typically has less error than TD(0)

Answer 44

False. TD(1) typically has more error than TD(0)

Question 45

T/F TD(0) has the least amount of error usually

Answer 45

False. TD(lambda) performs best. Usually 0.3 - 0.7 is best

Question 46

Temporal Difference is

Answer 46

Difference between reward (value estimates) as we go from one step to another

Question 47

T/F reward must be scalar

Answer 47

TRUE

Question 48

T/F environment is visible to the agent

Answer 48

False, usually

Question 49

T/F all representations of state have same results

Answer 49

False. Cheese/rat example in David Slivers. remembering past 3 states is diff than past 4 or 5

Question 50

Partially Observable

Answer 50

Agent indirectly view state (agent state != env state). ex: robot with camera. POMDP

Question 51

T/F Model is the environment

Answer 51

False. Model is the agent's idea of the environment

Question 52

RL vs Planning

Answer 52

RL: model is unknown, the agent performs actions Planning: model is known, the agent performs computations (know planning)

Question 53

B is a Contraction Mapping when

Answer 53

||BF - BG|| <= ||F-G|| so max difference between f-g vs B applied to F and B applied to G

Question 54

Backward and forward TD(lambda) can be applied to the same problems.

Answer 54

True. As also noted, you would have to wait for a complete episode to do it forwards(i.e. forwards does not work "online")...

Question 55

gamma of 0 means

Answer 55

you care only about the current (short-sighted)

Question 56

gamma of 1 means

Answer 56

you care about the future a lot (far-sighted)

Question 57

why use gamma and discount future rewards

Answer 57

avoid infinite returns and also account for a model not being perfect (future reward is not guaranteed)

Question 58

T/F You can always flatten an MDP to a Markov Chain

Answer 58

True

Question 59

Difference between MDP and Markov Reward Process

Answer 59

An MDP is a Markov Reward Process with decisions. Includes actions and stochasticity

Question 60

T/F it has been proven that both forward and backward view of TD(lambda) are equivalent

Answer 60

True

Question 61

What is forward TD(lambda)

Answer 61

The forward view looks at all n-steps ahead and uses λ to essentially decay those future estimates.

Question 62

What is backward TD(lambda)

Answer 62

The backward view of TD(λ) updates values at each step. So after each step in the episode you make updates to all prior steps. Uses eligibility trace

Question 63

Online learning vs offline learning

Answer 63

Online learning means that you are doing it as the data comes in. Offline means that you have a static dataset. Let's say you want to build a classifier to recognize spam. You can acquire a large corpus of e-mail, label it, and train a classifier on it. This would be offline learning. Or, you can take all the e-mail coming into your system, and continuously update your classifier (labels may be a bit tricky). This would be online learning

Question 64

SARSA vs Q- Learning

Answer 64

In Q learning, you update the estimate from the maximum estimate of possible next actions, regardless of which action you took. Whilst in SARSA, you update estimates based on and take the same action.

Question 65

T/F Offline algorithms are generally superior to online algorithms.

Answer 65

False Generally, because it depends on the problem and a number of other things.

Question 66

T/F Given a model (T,R) we can also sample in, we should first try TD learning.

Answer 66

false, if you have the model one would expect it to be more efficient to use it.

Question 67

T/F TD(1) slowly propagates information, so it does better in the repeated presentations regime rather than with single presentations.

Answer 67

False. TD(0) propagates more slowly.

Question 68

T/F In TD(lambda), we should see the same general curve for best learning rate (lowest error), regardless of lambda value.

Answer 68

Generally True, same shape but different minima

Question 69

T/F In general, an update rule which is not a non-expansion will not converge.

Answer 69

True. A non-expansion is {constant, contraction}, and a not non-expansion is not a constant and not a contraction, therefore it is an expansion and expansions diverge.

Question 70

T/F MDPs are a type of Markov game.

Answer 70

True. Markov games with only one player action space and a corresponding single reward function are MDPs.

Question 71

T/F Contraction mappings and non-expansions are concepts used to prove the convergence of RL algorithms, but are otherwise unrelated concepts.

Answer 71

False. They are totally related. A non-expansion must be followed by a contraction, in order to provide convergence guarantees.

Question 72

T/F Linear programming is the only way we are able to solve MDPs in linear time.

Answer 72

False. First of all, LP takes super-linear polynomial time. Secondly, LP is only one part of a potential RL algorithm. Third of all, there are many methods that don't use LP that solve MDPs (though none in linear time).

Question 73

T/F The objective of the dual LP presented in lecture is minimization of “policy flow”. (The minimization is because we are aiming to find an upper bound on “policy flow”.)

Answer 73

False. The objective of the dual LP is to maximize "policy flow", subject to conservation of flow constraints. The minimization is for the primary LP problem, in order to find the least upper bound of value functions over states and actions.

Question 74

T/F max is non-expansion

Answer 74

True

Question 75

T/F Any optimal policy found with reward shaping is the optimal policy for the original MDP.

Answer 75

False, only potential based shaping might avoid introducing an sub-optimal policy loop.

Question 76

Generalized MDPs

Answer 76

as long as operators doing updates are non-expansion, we get convergence of q learning, value iteration,

Question 77

examples of non-expansion

Answer 77

order statistics (max, min), fixed convex combinations

Question 78

T/F If you get a good enough approximation of the value function then you are bound on how far off you are

Answer 78

True

Question 79

T/F Policy Iteration converges at least as fast as VI

Answer 79

True

Question 80

T/F Policy Iteration is more computationally expensive than VI

Answer 80

True

Question 81

Domination

Answer 81

policy 1 dominates policy 2 if for all states the value of that state for policy 1 is greater than or equal to the value of that state for policy 2

Question 82

T/F policy iteration won't get stuck in a local optimal

Answer 82

True

Question 83

T/F value non-deprovement in steps of policy iteration

Answer 83

true

Question 84

How can we change the MDP reward function w/o changing optimal policy (3 ways)

Answer 84

multiply by positive constant, shift by constant, non linear potential based rewards

Question 85

T/F initializing q values is the same as using potential based functions

Answer 85

True. Initialize to 0. Random means you are biasing

Question 86

Potential-based shaping will find an optimal policy faster than an unshaped MDP.

Answer 86

False... if the selected potential is wrong, it will slow things down.

Question 87

T/F potential functions can speed things up

Answer 87

True

Question 88

What is the problem with reward shaping

Answer 88

We can screw things up and create suboptimal policies optimized for these "helper" scenarios

Question 89

T/F Rmax will always find the optimal policy for a properly tuned learning function.

Answer 89

False (although true in spirit). The problem is the word 'always.' As Jacob alludes to, in these PAC-style bounds, there is always a small probability that the desired goal isn't reached, and if reached it's not quite optimal.

Question 90

Q-learning converges only under certain exploration decay conditions.

Answer 90

False as we are only concerned with exploration decay.convergence is guaranteed by the contraction property of the Bellman operator, which does not include any assumptions on the exploration rate.

Question 91

The tradeoff between exploration and exploitation is not applicable to finite bandit domains since we are able to sample all options.

Answer 91

False. You may still need to explore "non-optimal" arms of the bandit since there may be noise in the estimate of its value.

Question 92

T/F Since SARSA is an “online” algorithm, it will never learn the optimal policy for an environment.

Answer 92

False. SARSA converges to an optimal policy as long as all state-action are visited an infinite number of times and the policy converges to a greedy policy.

Question 93

T/F RL with linear function approximation only works on toy problems.

Answer 93

False. Nonlinear approximation can be approximated by linear piece-wise construction.

Question 94

T/F KWIK algorithms are an improvement of MB (mistake bound) algorithms and as such will have same or better time complexity for all classes of problems.

Answer 94

False. Some hypothesis classes are exponentially harder to learn in the KWIK setting than in the MB setting.

Question 95

T/F With a classic update using linear function approximation, we will always converge to some values, but they may not be optimal.

Answer 95

False. Baird's counter-example shows how classic update using linear function approximation can lead to divergence.

Question 96

T/F Applying generalization with an "averager" on an MDP results in another MDP.

Answer 96

True. As noted in Gordon (1995), you will have less states...

Question 97

Hoeffding and union bounds

Answer 97

a way to know how much we know (certainty). know when we are certain enough

Question 98

Rmax

Answer 98

optimism in the face of uncertainty

Question 99

Can combine Rmax bandits

Answer 99

stochastic + sequential

Question 100

When does generalization work

Answer 100

essentially anything that generalizes a linear model (ANN, CMAC, linear nets, deep nets)

Question 101

Generalization

Answer 101

some state may look like other states so take into account features of states and weight the importance of the feature when making a decision. Replace update rule with function approximation

Question 102

T/F averages can converge to optimal solution (but does not always)

Answer 102

True. Need anchor points to converge

Question 103

T/F value iteration converges for POMDPs

Answer 103

False, but you can get near-optimal

Question 104

T/F POMDPs are easy to solve

Answer 104

False. Piecewise linear convex can do it and throw away a lot that are striclty dominated

Question 105

Model based POMDP

Answer 105

use expectation maximization to learn the model

Question 106

memoryless POMDP

Answer 106

helps to be random

Question 107

Properties of Monte Carlo Tree Search

Answer 107

useful for large states, needs lot of samples to get good estimates, planning time indepedent of size of state space, running time is exponential in the horizon

Question 108

Gittens index only works for

Answer 108

bandits

Question 109

How does monte carlo tree search get q value estimates

Answer 109

random simulation

Question 110

Goal abstrction

Answer 110

Modular RL and arbitration

Question 111

Temporal abstractions (hierarchical RL)

Answer 111

options and semiMDPs

Question 112

Pavlov strategy

Answer 112

cooperate if agree, defect if disagree

Question 113

Subgame perfect

Answer 113

always best response independent of history

Question 114

Properties of minimax 1 for 2 player 0 sum games

Answer 114

value iteration works, minimaX Q converges, efficent

Question 115

Properites of nash q for multiplayer

Answer 115

value iteration does not work, minimax q does not coverge

Question 116

Does coco generalize to n>2 players

Answer 116

no

Question 117

what is coco

Answer 117

cooperative competitive values

Question 118

T/F POMDPs can be planned

Answer 118

False

Question 119

Semi-MDP

Answer 119

Instead of looking at a very small action space, we can create new actions that transitions that could help reduce the number of steps to learn and move towards a goal.

Question 120

T/F b/c SMDPs are abstracting MDP they inherit the hierarchical optimality, convergence and stability of an MDP

Answer 120

FALSE, true with the vaceat that we should choose the right options. Also, the sttates don't matter and helps with exploration