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, while that can be the case (and often works well), some algorithms, like TD(1) give equal weight to each move and it is also possible to give more weight to earlier moves as well. It depends on the problem you’re trying to solve.

False. You can lose a chess game on your first move – and apparently someone did.

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.

True. A fixed policy means a fixed action is taken given a state. In this case, this MDP totally depends on the current state, and it is now reduced to a Markov chain with rewards.

Question 4

If 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.

False. For an optimal policy, max V(s) is equal to the max Q(s, a). No need to know the environment transition matrix.

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.

True. In a MDP the present is a sufficient statistic of the past.

Only the current state matters and what past states were is irrelevant to the agent.

Question 7

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

Answer 7

False as noted… Optimal action on an optimal value function is optimal by definition.

Question 8

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

Answer 8

False, the sum of learning rates must diverge for the value function to converge.

Also, the sum of learning rates squared must converge for the value function to converge.

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. (second sentence)

True –> Monte Carlo is an unbiased estimator of the value function compared to TD methods –> TD methods start with an initial estimate of q values and tend to be biased on these

False –> Most episodic tasks are too long and the computational advantages of TD updates favor TD methods over MC methods.

Question 10

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

Answer 10

False. We can evaluate a learner on other metrics including computational complexity and how much data is required to effectively learn.

Question 11

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

Answer 11

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

Partially Observable Markov Decision Processes (POMDPs) have succeeded in planning domains that require balancing actions that increase an agent’s knowledge and actions that increase an agent’s reward.

Question 12

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

Answer 12

True.

The decentralized partially observable Markov decision process (Dec-POMDP) is a model for coordination and decision-making among multiple agents.

It is a probabilistic model that can consider uncertainty in outcomes, sensors and communication (i.e., costly, delayed, noisy or nonexistent communication). it is a generalization of a Markov decision process (MDP) and a partially observable Markov decision process (POMDP) to consider multiple decentralized agents.

Question 13

DEC-POMDP stands for

Answer 13

Decentralized Partially Observable Markov Decision Process

Question 14

The primary difference between POMDPs and DEC-POMDPS

Answer 14

In DEC-POMDPS, actions are taken simultaneously by a finite set of agents (not just 1)

Question 15

DEC-POMDPS vs POSG

Answer 15

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

—> Note: what is POSG?

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) –> NEXP-complete when the input is represented as a brief circuit

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: have trajectories (sequence so far)
• rather than rewards: have target distribution p(T).

Trajectory Distribution Markov Decision Process

Question 23

Value Iteration Algorithm

Answer 23

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

Note that value iteration is obtained simply by turning the Bellman optimality equation into an update rule. Also note how the value iteration backup is identical to the policy evaluation backup (4.5) except that it requires the maximum to be taken over all actions.

Value iteration effectively combines, in each of its sweeps, one sweep of policy evaluation and one sweep of policy improvement.

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.

For example, in football, at each second, each football player takes an action. In this context, an action can e.g. be “pass the ball”, “dribbe”, “run” or “shoot the ball”. At the end of the football match, the outcome can either be a victory, a loss or a tie. After the match, the coach talks to the players and analyses the match and the performance of each player. He discusses the contribution of each player to the result of the match. The problem of determinig the contribution of each player to the result of the match is the (temporal) credit assignment problem.

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

Scalar value means single value.

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 Markov Decision Process and Markov Reward Process

Answer 59

An Markov Decision Process 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

Q-Learning is an off-policy TD control policy. It’s exactly like SARSA with the only difference being — it doesn’t follow a policy to find the next action A’ but rather chooses the action in a greedy fashion.

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 Language Processing (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 Language Processing (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

The non-expansion is a vital and widely-used sufficient condition to guarantee the convergence of value iteration.

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

Their basic concept is that in the Bellman equations, the operation $ \sum_y P(x,a,y) \ldots$ (i.e., taking expected value w.r.t. the transition probabilities) describes the effect of the environment, while the operation $ \max_a …$ describes the effect of an optimal agent (i.e., selecting an action with maximum expected value). Changing these operators, other well-known models can be recovered.

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

https://sites.ualberta.ca/~szepesva/papers/gmdp.ps.pdf

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 Value Iteration (VI)

Answer 79

True

Question 80

T/F Policy Iteration is more computationally expensive than Value Iteration (VI)

Answer 80

True

Policy iteration is also guaranteed to converge to the optimal policy and it often takes less iterations to converge than the value-iteration algorithm.

Comparing to each other, policy-iteration is computationally efficient as it often takes considerably fewer number of iterations to converge although each iteration is more computationally expensive.

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

If this is the case, then the policy improvement step will not stop at the local optimum state-action space Π#, as there exists at least one state-action in Π∗ which is different from Π# and yields a higher value of 𝑣∗ compared to 𝑣#

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

(1. ) Multiply by positive constant
(2. ) Shift by constant
(3. ) 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 “know what it knows” 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.

A KWIK algorithm is an online learning algorithm that is considered to be self-aware i.e.,
if and only if the learner believes that it has insufficient experience to predict on a new sample, does the learner ask the expert for the answer

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

R-max is a very simple model-based reinforcement learning algorithm which can attain near-optimal average reward in polynomial time. In R-max, the agent always maintains a complete, but possibly inaccurate model of its environment and acts based on the optimal policy derived from this model.

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

Machine learning is a discipline in which given some training data/environment, we would like to find a model that optimizes some objective, but with the intent of performing well on data that has never been seen by the model during training.

This is usually referred to as Generalization, or the ability to learn something that is useful beyond the specifics of the training environment.

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

POMDPs - We’re unsure which state we’re in. The current state emits observations.

• we have control of over the state transitions
• the states are not completely observable

Question 105

Model based POMDP

Answer 105

Use expectation maximization to learn the model

The model-based approach — learning a POMDP model of the world, and computing an optimal policy for the learned model — may generate superior results in the presence of sensor noise, but learning and solving a model of the environment is a difficult problem.

When sensor noise increases, model-free methods provide less accurate policies.

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 independent 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 abstraction

Answer 110

Modular RL and arbitration.

Abstraction is a technique to reduce the complexity of a problem by filtering out irrelevant properties while preserving all the important ones necessary to still be able solve a given problem

Question 111

Temporal abstractions (hierarchical RL)

Answer 111

Options and semiMDPs

Applying reinforcement learning (RL) to real-world problems will require reasoning about action-reward correlation over long time horizons. Hierarchical reinforcement learning (HRL) methods handle this by dividing the task into hierarchies, often with hand-tuned network structure or pre-defined subgoals.

The learned abstraction allows us to learn new tasks on higher level more efficiently. We convey a significant speedup in convergence over benchmark learning problems. These results demonstrate that learning temporal abstractions is an effective technique in increasing the convergence rate and sample efficiency of RL algorithms.

Question 112

Pavlov strategy

Answer 112

Cooperate if agree, defect if disagree

Question 113

Subgame perfect

Answer 113

always best response independent of history

A Nash equilibrium is said to be subgame perfect if and only if it is a Nash equilibrium in every subgame of the game.

Question 114

Properties of minimax 1 for 2 player 0 sum games

Answer 114

• value iteration works
• minimaX Q converges
• efficient

Question 115

Properties of nash q for multiplayer

Answer 115

• value iteration does not work

- minimax q does not converge

Question 116

Does coco generalize to n>2 players

Answer 116

No, Coco-Q, like coco values in normal-form games, is not defined for games with three or more players

Coco (“cooperative/competitive”) values are a solution concept for two-player normalform games with transferable utility, when binding agreements and side payments between players are possible.

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