Final Review

Question 1

True or False: A policy that is greedy – with respect to the optimal value function – is not necessarily an optimal policy. Why?

Answer 1

False. Behaving greedily with respect to an optimal value function is an optimal policy because it optimizes the long-term cumulative reward.

A greedy policy derived from an optimal value function is necessarily optimal. However a greedy policy derived from just any value function is not necessarily optimal.

Question 2

True or False: The optimal policy for any MDP can be found in polynomial time. Why?

Answer 2

True for any finite MDP. We can reduce the MDP to linear program and solve it in polynomial time.

Question 3

True or False: The value of the returned policy is the only way to evaluate a learner. Why?

Answer 3

False, you might also care about the computational- or memory- or sample-efficiency

Question 4

True or False: If we know the optimal Q values, we can get the optimal V values only if we know the environment’s transition function/matrix. Why?

Answer 4

**verify from review 1
True. Because Q values needs to be multiplied with the corresponding transition probabilities and the summed over the action space to derive optimal Q values.

Question 5

True or False: An MDP given a fixed policy is a Markov chain with rewards. Why?

Answer 5

True. A fixed policy means same action selection for a given state. That means MDP is a a Markov chain with rewards.

An MDP describes (1) a set of states, (2) a set of actions (3) transition probabilities and (4) rewards for transitioning.

By applying a fixed policy (which defines what action to take in each state), we eliminate the choice of action, which means we’re left with:

[(1) a set of states (3) transition probabilities] (Markov Chain)

[(4) rewards for transitioning]. (w/ Rewards)

Question 6

True or False: 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. Why?

Answer 6

**verify from review 1

True. Because the underlying differential rewards across the states do not change by adding 10 to all rewards.

Question 7

True or False: 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. Why?

Answer 7

**verify from review 1

True. Because the underlying differential rewards across the states do not change by adding 10 to all rewards.

Question 8

True or False: In RL, recent moves influence outcomes more than moves further in the past. Why?

Answer 8

False. It depends on the discount factor.

Question 9

True or False: The Markov property means RL agents are amnesiacs and forget everything up until the current state. Why?

Answer 9

I think True. Markov property means the future can be predicted only with the present.

Question 10

Explain the two types of tasks modeled by MDPs; unify the notation used to describe these two tasks, and describe the type of state that allows you to unify them. (Hint: you may find section 3.4 of S&B helpful.)

Answer 10

We are talking about episodic and continuous tasks. The returns from these tasks could be unified using a self-loop with zero rewards to the terminal state for an episodic task.

Question 11

Does policy iteration or value iteration converge faster? If so, why?

Answer 11

Policy iteration converges faster because it takes few iterations than value iterations.

Question 12

Is it possible that value iteration just never converges on your formulation of MDP with a proper convergence criterion?

Answer 12

No value iteration is guaranteed to converge.

Question 13

What is the meaning of the bellman equations? What is it saying? What is your way of visualizing this equation in your head?

Answer 13

The long-term return for an action is the sum of the current reward and all possible future rewards.

the long term return for an action is the sum of the current reward and all possible discounted future rewards.

Question 14

What are the bellman equations? (try to write it down without looking at notes since this is the single most important equation to know for this class)

Question 15

What is a policy?

Answer 15

choice function for action for a given state.

Question 16

What is Value Iteration?

Answer 16

value iteration is an iterative algorithm to compute the optimal value function.

Question 17

What is Value Iteration?

Answer 17

value iteration is an iterative algorithm to compute the optimal value function.

Question 18

What is the Markov property?

Answer 18

Markov property is a memoryless property: your future is only dependent on your present. It can capture the past in the current state

Question 19

Is it possible to have multiple terminal states in an MDP?

Answer 19

there is no restriction for an MDP to have multiple terminal states.

Question 20

True or False: Contraction mappings and non-expansions are concepts used to prove the convergence of RL algorithms, but are otherwise unrelated concepts. Why?

Answer 20

non-expansion is a general case of contraction mapping. For contraction mapping |F(a) - F(b)| <= gamma*|a-b| where gamma needs to be strictly smaller than 1. But for non-expansion the gamma value can be 1 so it allows the distance to be smaller or remain equal

Question 21

True or False: An update rule which is not a non-expansion will not converge without exception. Why?

Answer 21

In general, True. But as an ultimatum, this is False.

Non-expansion is a condition that guarantees convergence. However, the lack thereof does not guarantee the lack of convergence.

Question 22

True or False: In TD(λ), we should see the same general curve for best learning rate (lowest error), regardless of λ value. Why?

Answer 22

The Lambda matters. In fact the lambda has some effect on the learning rate, as it is somehow (the summation of its exponents multiplied by xt) a multiplier to (Pt+1 - Pt) as well. You will observe that at higher lambdas you will need to lower your alpha in order not to exceed the threshold necessary for convergence

Question 23

True or False: TD(1) slowly propagates information, so it does better in the repeated presentations regime rather than with single presentations. Why?

Answer 23

False.

TD(0) is == to Monte Carlo learning which updates very slowly. TD(1) propagates information all the way down the “chain” for every presentation.

Question 24

True or False: Given a model (T,R) we can also sample in, we should first try TD learning. Why?

Answer 24

False.

While TD learning was revolutionary and is used in many algorithms today, value or policy iterations have better convergence properties and should by tried first.

Question 25

True or False: Offline algorithms are generally superior to online algorithms. Why?

Answer 25

False.

Online algorithms update values as soon as new information is presented, therefore making the most efficient use of experiences.

Question 26

True or False: Backward and forward TD(\lambdaλ) can be applied to the same problems. Why?

Answer 26

True.

Both backward and forward TD(λ) will converge on the same problem. Backward TD(λ) typically is easier to compute.

Question 27

True or False: 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. Why?

Answer 27

False. Even though MC is unbiased but it has higher variances, therefore TD methods may outperform MC in terms of learning performance.

Question 28

True or False: In TD learning, the sum of the learning rates used must converge for the value function to converge. Why?

Answer 28

False. Sum of learning rates must diverge. Sum of the square of learning rates must converge.

Question 29

What are some advantages of TD methods compared to dynamic programming methods? to Monte Carlo methods?

Answer 29

TD combines the merits of DP and MC. Compared to DP which requires the transition model for planning, TD can do model-free learning. Compared to MC which has high variance, TD makes more efficient use of the data from intermediate states thus has lower variance, and can do online learning.

Compared to DP: it’s model free

Compared to MC: lower variance, online, incremental method

Question 30

What can we say about the bias-variance trade-off between a 1-step estimator versus a Monte Carlo estimator (in other words, which estimator has a higher variance and which estimator has a higher bias?)

Answer 30

MC: High variance, 0 bias. Good Convergence. Not sensitive to initial value. Simple to understand and use. Effective in non-Markov.

TD: low variance, medium/high bias. More efficient than MC. TD(0) converges with LP to optimal V(s). IT is not guaranteed to converge with function approximation. More sensitive to initial value. Exploits Markov Property.

Question 31

What’s the formula to view TD(\lambdaλ) as a function of n step estimators?

Question 32

What is the value of the 5-step estimator of the terminal state? What about other n-step estimators of the terminal state?

Answer 32

The state value of the terminal state in an episodic problem should always be 0 (since the agent terminates)

Question 33

What is a Monte-Carlo return?

Answer 33

The value of the state is the expected return. (Sutton and Barto, p. 92)

Question 34

What is the prediction problem?

Answer 34

‘Using past experience with an incompletely known system to predict its future behavior’

Question 35

What are model-free methods?

Answer 35

In model-free methods, we do not need to learn transition probabilities and rewards explicitly. We learn value function and/or optimal policy directly instead.

Question 36

What is TD? In which algorithms is TD used?

Answer 36

TD is short for temporal difference, and is a value-based learning algorithm.