Review Questions

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.

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.

False for an infinite MDP

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

False. V = max(Q)

Question 5

True or False: It is not always possible to convert a finite horizon MDP to an infinite horizon MDP. Why?

Answer 5

False. We can always convert a finite horizon MDP to an infinite horizon MDP by adding a self-loop with the terminal state.

Question 6

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

Answer 6

True. A fixed policy means same action selection for a given state. That means MDP is a a Markov chain with 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

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

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

Question 10

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

Answer 10

Policy iteration is guaranteed to converge at least as fast as value iteration

Question 11

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

Answer 11

No value iteration is guaranteed to converge.

Question 12

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

Answer 12

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

Question 13

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)

Answer 13

U(s,a,s’) = r(s’) + gamma * max_a [Sum_s’ T(s,a,s’)*U(s’)]

Question 14

What is a policy?

Answer 14

Choice function for action for a given state.

Question 15

What is Value Iteration?

Answer 15

Value iteration is an iterative algorithm to compute the optimal value function which is iteratively updating a value function that we use to create a policy. Contrasting with policy iteration where we directly update the policy.

Question 16

What is the Markov property?

Answer 16

Markov property is a memoryless property: your future is only dependent on your present.

Question 17

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

Answer 17

There is no restriction for an MDP to have multiple terminal states, although they can be abstracted into a single terminating state.

Question 18

What is an MDP? What are the components of an MDP?

Answer 18

States, Actions, Model (transition function, reward function), Policy

Question 19

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 19

My impression is that 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 20

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

Answer 20

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.
Coco-Q is a counter example.

Question 21

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

Answer 21

True. See figure 4 in Suttons TD(λ) paper.

Question 22

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

Answer 22

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.
TD(1) has high variance that is why we need repeated presentation.

Question 23

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

Answer 23

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 24

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

Answer 24

False.

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

Question 25

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

Answer 25

True.

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

Question 26

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 26

False. Even though MC is unbiased, it has higher variances, therefore TD methods may outperform MC in terms of learning performance. Additionally, they could require more samples to converge on the correct values

Question 27

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

Answer 27

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

Question 28

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

Answer 28

Compared to DP: it’s model free

Compared to MC: lower variance, online, incremental method

Question 29

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 29

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 30

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

Answer 30

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

Question 31

What is a Monte-Carlo return?

Answer 31

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

Question 32

What is the prediction problem?

Answer 32

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

Question 33

What are model-free methods?

Answer 33

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 34

What is TD? In which algorithms is TD used?

Answer 34

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

Question 35

In Sutton 88, why are all the curves in figure 4 convex?

Answer 35

It indicates for a given lambda, the error is minimum for some intermediate alpha. For low alpha, the weight update is taking place slowly which might lead to high bias. For high alpha, the weight update is taking place too fast which might lead to high variance.

Question 36

In Sutton 88, if there are way more data than 100 sequences for each training set in experiment one, what kind of graph of figure 3 would you expect? Why?

Answer 36

The shape of the curve should be similar, but the error values should all decrease because the impact of the random noise goes down as the number of sequences increases

Question 37

In Sutton 88, why doesn’t TD(0) do well in figure 5?

Answer 37

TD(0) is MC and requires multiple iterations to fully train itself. in Fig 5, only 1 iteration was presented which did not allow TD(0) to converge on optimal value function.

Question 38

In Sutton 88, experiment 1, what is the convergence criterion? What effect does it have on the TD algorithm?

Answer 38

The weight vector was not updated after each sequence and only used to update the weight after the complete presentation of the training set. This likely was done to account for the stochastic nature of the problem and allow for convergence in minimal sequences and training sets.

Question 39

In Sutton 88, is the TD algorithm used in the paper the same as the TD we saw in class?

Answer 39

I think the one in the class was applied to the Bellman equation. Therefore, it has the reward terms as well as the value terms in the equation. For the Sutton paper, it was much simpler.

Question 40

In Sutton 88, why does TD(0) do best in figure 3 of Prof. Sutton’s paper (you can use the intuition from the above question)?

Answer 40

In the linear case, TD(0) minimizes the error for future experience and converges to the ML estimate of the underlying Markov process.

Question 41

Intuitively, why would TD(0) converge to “the maximum likelihood estimate of the underlying MDP”?

Answer 41

With repeated presentations of finite data in TD(0), the next state for a given state occurs with a certain probability. The value of a given state is updated more often towards the target (sum of the immediate reward r plus single discounted value of immediate next state V(s’)) according to how often those next states occur (frequency is proportional to their transition probabilities from the originating state), leading essentially to the expected value of that state at convergence. Maximum likelihood estimates are also computed based on this same probabilities, hence it is expected that TD(0) will converge towards MLE

Question 42

What is an eligibility trace?

Answer 42

A temporary record of the occurrence of an event (think the exponentially decaying graph showing (1-λ)^n * λ)

Question 43

True or False: The trade-off between exploration and exploitation is not applicable to finite bandit domains since we are able to sample all options. Why?

Answer 43

False. The exploration is still needed since there can be noise of the estimated value

Question 44

What are the benefits of an off-policy algorithm?

Answer 44

Off policy allows the agent to evaluate and improve a policy that is different from the Policy that is used for action selection. Target Policy != Behavior Policy.

This allows for continuous exploration, learning from demonstration, and parallel learning.

Question 45

Is it possible that Q-learning doesn’t converge? Is it possible that the point it converges to is not optimal?

Answer 45

Neither is possible. We can prove that Q-learning always converges, and it converges to Q*. But it may take intractably long.

Question 46

Why can you find an optimal policy despite finding sub-optimal Q-values (e.g. via Q-learning)?

Answer 46

If Q is close enough to Q, then we could find pi through Q. This is because the policy contains less information than Q function.

Question 47

True or False: Policy shaping requires a completely correct oracle to give the RL agent advice. Why?

Answer 47

False. Policy shaping needs a certain degree of confidence, but a completely correct oracle is not necessary (it would help though).

Question 48

True or False: Since Sarsa is an “online” algorithm, it will never learn the optimal policy for an environment. Why?

Answer 48

False. Sarsa will use the new information to update its Q table, and may learn the optimal policy if the Q table is accurate enough.

Question 49

True or False: Rmax will always find the optimal policy for a properly tuned learning function. Why?

Answer 49

False. It does not guarantee optimal, but it can help get to near-optimal results.

Question 50

True or False: Potential-based shaping will always find an optimal policy faster than an unshaped MDP. Why?

Answer 50

False. Potential-based shaping is not magic. It is only a way to redefine your rewards, and does not always converge faster. But If you initialize Q(s,a) as all zeros, it can give you some head start.

Question 51

True or False: Any optimal policy found with reward shaping is the optimal policy for the original MDP. Why?

Answer 51

From the lecture, reward shaping via scaling, shifting, or potential functions preserves the optimal policy. Considering there are other reward shaping techniques that exists, I’d say this is False. When not careful, an agent could enter a sort of sub-optimal, feedback loop with the environment, i.e. just dribbling a soccer ball without shooting because rewards were given for time spent dribbling.

Question 52

One perspective of Sarsa is that it looks a bit like policy iteration? Can you tell us which part of Sarsa is policy evaluation and which part is policy improvement?

Answer 52

policy evaluation: update the Q(s,a) value

policy improvement: choose the A’ using epsilon-greedy policy

Question 53

In an assignment document, it says Sarsa uses TD to do control. What exactly does it mean? Which part of Sarsa is TD?

Answer 53

Sarsa still uses TD error to update the Q function, just as Q-learning.

Question 54

Why is Sarsa on policy? How does this compare to an off-policy method like Q-learning by following a random policy to generate data?

Answer 54

SARSA is on policy because it directly takes the action A’ going to S’ using an e-greedy policy. Q-learning takes action A and observes the R, S’ for all A and chooses the maximum value.

SARSA: Q(S,A) = Q(S,A) + alpha[Rt+1 + gamma(Q(S’,A’) - Q(S,A)]

Q-LEarning: Q(S,A) = Q(S,A) + alpha[Rt+1 + gamma(max_a Q(S’,a) - Q(S,A)]

Question 55

In HW3, we saw Sarsa is a ‘control’ algorithm? What is a ‘control’ task? Are any TD algorithms a ‘control’ algorithm?

Answer 55

Control task means the action is included. It estimates the action-value function Q(s,a). TD algorithms can be used for either prediction or control. Not all TD methods a control algorithm.

Question 56

True or False: The only algorithms that work in POMDPs are planning algorithms. Why?

Answer 56

False. RL algorithm also works for POMDP.

Question 57

True or False: Problems that can be represented as POMDPs cannot be represented as MDPs. Why?

Answer 57

False. MDP is a special kind of POMDP.

Question 58

True or False: Applying generalization with an “averager” on an MDP results in another MDP. Why?

Answer 58

True. Any generalization of an MDP results in another MDP

Question 59

True or False: With a classic update using linear function approximation, we will always converge to some values, but they may not be optimal. Why?

Answer 59

False. it may not even converge. Consider the Baird counterexample.

Question 60

True or False: RL with linear function approximation will not work on environments having a continuous state space. Why?

Answer 60

True. Because a linear function approximation would fail to capture non-linearities and feature interactions in a continuous state space.

Question 61

Let’s say you want to use Q-learning with some function approximator. Recall that we learned a convergence theorem and we used that to conclude that Q-learning converges. Can we apply that theorem to prove that your Q-learning with some function approximator converges? Why or why not?

Answer 61

False. Adding functional approximator might leads to divergence. Like we have seen in DQN for project 2.

Question 62

Let’s say you want to use a function approximator like we learned in class. What function(s) are you approximating? What’s the input of that function and what’s the output of that function?

Answer 62

We can approximate action value, Q, which takes state and action pairs as inputs.

Question 63

We learned about reward shaping in class. Could it be useful for solving Lunar Lander? If so, why and how?

Answer 63

Reward shaping could be useful given the high-dimensional state space and the agent is being trained to reach a particular point. I think it will accelerate the learning.

Question 64

Observe that the biggest difference between P2’s Lunar Lander problem and HW4’s Taxi problem is that there are infinitely many states in Lunar Lander. What are some good methods to handle this case? What are their pros and cons?

Answer 64

DQN is very useful to handle high-dimensional state space such as Lunar Landing. Other methods include Model-based DreamerV2, imitation learning, and different policy gradient algorithms such as REINFORCE, PPO, A2C, and SAC. While these algorithms provide superior accuracy, they are difficult to train because of non-convexity.

Question 65

Using the coco value, we calculate the side payments as: P = coco(u, u_bar). But why does u getting P amount of side payment make sense?

Answer 65

It makes sense in the case that by cooperating neither party is loosing more than by not cooperating. By taking the coco equation the maximum of both cooperating plus the maxmin (maximum negative reward inflicted on other agent) needs to be >0 for coco side payments to work. Each Coco agent will have an inverse side payment (if one agent gives one (-1) the other agent gets one (+1)).

Question 66

True or False: “Sub-game perfect” means that every stage of a multistage game has a Nash equilibrium. Why?

Answer 66

False the strategy is itself an equilibrium from multistage perspective, it doesn’t require each stage it’s the Nash, nor it requires the existence of Nash for each stage, as long as multistage angle it’s a Nash.

Question 67

True or False: If following the repeated game strategy “Pavlov”, we will cooperate until our opponent defects. Once an opponent defects we defect forever. Why?

Answer 67

False. This is grim trigger.

In pavlov, once the opponent defects we will defect until the opponent defects again. In which case, we will cooperate.

Question 68

True or False: The “folk theorem” states that the notion of threats can stabilize payoff profiles in one-shot games. Why?

Answer 68

False, the folks theorem describes a set of payoffs that can results from Nash strategies in a repeated game. Therefore, it does not apply in one-shot game since it only has 1 episode.

Question 69

True or False: An optimal pure strategy does not necessarily exist for a two-player, zero-sum finite deterministic game with perfect information. Why?

Answer 69

False, in 2 player, zero-sum, deterministic game with perfect information, there is always a pure optimal strategy.

Question 70

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

Answer 70

False. The objective of the dual LP is to maximize the reward carried by the policy flow

Question 71

True or False: LP is the only way to efficiently solve an MDP for its optimal policy. Why?

Answer 71

True. LP is the only way to guarantee convergence in polynomial time.

Question 72

True or False: MDPs are a type of Markov game. Why?

Answer 72

True. MDP can be considered as a single-agent Markov game, or it could be a multi-agent Markov game when there is only one agent contributes to the reward and transition function.

Question 73

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

Answer 73

False. The class of singletons H can be learned in a Mistake-bound model with mistake bound of only 1, while in the worst case KWIK can take 2^{n}-1 examples to learn since it doesn’t know the answer until it has seen its first positive example.(https://www.cs.cmu.edu/~avrim/Papers/kwikmb.pdf)

Question 74

What if instead of being given “fight_occurred” you are given “did peacemaker come?” and “did instigator come?” Can you create an KWIK algorithm that outputs fewer “don’t knows” than HW5?

Answer 74

If we are given two answers “did peacemaker come” and “did instigator come” I think we can apply Algorithm 6 from the KWIK paper. Since the size of each hypothesis class is n, the combined KWIK learner has a worst-case bound of (1-k) + sum(Hi) = 2n-1

Question 75

What’s the worst case number of “don’t know” answers in your algorithm for HW5?

Answer 75

n*(n-1) - 1

Question 76

KWIK is a learning framework like PAC (probably approximately correct) learning. Why do we even need a learning framework like PAC or KWIK?

Answer 76

To improve efficiency of exploration

Question 77

What is the KWIK framework? What are the strengths of this framework and its algorithms?

Answer 77

Know What It Knows, designed particularly for its utility in learning settings where active exploration can impact the training examples the learner is exposed to. It can also be used for anomaly detection where it requires some degree of reasoning about whether a recently presented input is predictable from previous examples.

Question 78

True or False: Options over an MDP form another MDP. Why?

Answer 78

True. Options over MDPs form SMDPs which can be converted to MDPs.

Question 79

Can we do Q learning on SMDP? If so, how do we do that?

Answer 79

True, we use observations in place of actions and discounted rewards in place of rewards

Question 80

Is value iteration guaranteed to converge to the optimal policy for an SMDP?

Answer 80

With a particular choice of option there is no guarantee that it would end up with an optimal policy

Question 81

Is value iteration guaranteed to converge for an SMDP?

Answer 81

Value iteration is guaranteed to converge with an SMDP but not necessarily to the optimal policy. Am I missing something?

Question 82

How is SMDP defined? Why is it called semi-Markov?

Answer 82

SMDPs are Markov Decision Processes that use options instead of discrete “atomic” actions. These options are allowed to take variable time instead of discrete time.

Question 83

How is an option defined?

Answer 83

(I, Pi, Beta) : I = the initialization set of states, Pi = the policy to take with that option, and Beta = the termination set of states.