Final Exam

Question 1

What is an MDP?

Answer 1

A Markov decision process

Question 2

What are the components of an MDP?

Answer 2

State, Action, Reward

Question 3

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

Answer 3

Yes

Question 4

What is the Markov property?

Answer 4

Next state only depends on current state.Everything one needs to know about the environment is encoded in the current state. There is no need to access data from past steps.

Question 5

What is Value Iteration?

Answer 5

Using the Bellman equation to update the value of each state iteratively until convergence. Updating the policy once per iteration until convergence.

Question 6

What is a policy?

Answer 6

A policy is a mapping from states to actions for an MDP.

Question 7

What is the meaning of the Bellman equations? What do they do?

Answer 7

“(the Bellman equation) expresses a relationship between the value of a state and the values of its successor states.” S&B 2020

OR

An update rule for the value of a state based on the seen reward and the expected value of the next state.

Question 8

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

Answer 8

False. “(Policy and Value Iteration)… All of these algorithms converge to an optimal policy for discounted finite MDPs.” S&B 2020.

Question 9

Does policy iteration or value iteration converge faster? Give an explanation of your answer.

Answer 9

Both algorithms are guaranteed to converge to an optimal policy in the end. Yet, the policy iteration algorithm converges within fewer iterations. As a result, the policy iteration is reported to conclude faster than the value iteration algorithm.

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

Episodic - sequences of states that repeat … for example a card game gets to the end and then restarts with a shuffle/deal. And so would also be finite.

Continuing - sequences of states with no definable end. Like predicting the weather … the days continue with new weather each time … you never get to the last day and restart the episode.

You can unify them by making the last state in episodic tasks act as a sink that transitions to itself with probability 1.0 and reward = 0.

We use lambda to convert continuing tasks to simulate a finite length task; but, it would never become episodic as you’d never reset to the original state 0.

Question 11

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

Answer 11

True, the markov property states that an agent only needs the data of the currents state. However, the current state can have past experiences/observations included in the current state.

Question 12

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

Answer 12

False

Question 13

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 13

True. Adding a constant to reward would not change the policy. This is not considered as reward shaping.

Question 14

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

Answer 14

True. This is because the agent would be traversing through a fixed set of states which will never change.

Question 15

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

Answer 15

False … can’t we always set the last state to loop back upon itself with prob 1.0. Then it can go on forever (and the reward would be 0).

Question 16

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 16

False, V(s) = max_a Q(s,a). Thus V(s) is the action that maximizes Q(s,a). If we already have all of the Q-values for each possible action of a given state, V(s) is simply the largest number in the set of Q-values. No transition matrix needed.

Question 17

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

Answer 17

True - “A DP (Dynamic Programming) method is guaranteed to find an optimal policy in polynomial time even though the total number of (deterministic) policies is k^n” S&B 2020

Question 18

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

Answer 18

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

Question 19

What is TD? In which algorithms is TD used?

Answer 19

Temporal Difference. Classical TD has TD(0) - One-Step, TD(1) - Monte-Carlo, TD(lambda) - weighted look-ahead. A one-step TD update is the basis of all bootstrapping RL algorithms such as Q-learning, SARAS, DQN, PPO.

Question 20

What are model-free methods?

Answer 20

Methods that do not use transition probabilities and reward functions

“Methods for solving reinforcement learning problems that use models and planning are called model-based methods, as opposed to simpler model-free methods that are explicitly trial-and-error learners—viewed as almost the opposite of planning” - S&B 2020

Question 21

What is the prediction problem?

Answer 21

Estimating/Predicting the value of each state.

As opposed to the Control Problem, in which we can take actions to impact the sequence of states.

Question 22

What is a n-step estimator?

Answer 22

This is an estimator of state values that looks ahead n time steps into the future.

Question 23

What is a Monte-Carlo return?

Answer 23

The return of a full episode (sum of all rewards)

Question 24

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

Answer 24

0, because there are no future rewards for being in the terminal state.

Question 25

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

Answer 25

Question 26

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 26

1-step estimator will have much higher bias due to bootstrapping whereas Monte Carlo will have much higher variance because it depends on a lot of signals.

Question 27

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

Answer 27

With TD you do not necessarily need a model, whereas with dynamic programming you do. TD reduces the variance of the expected return compared with MC.

Dynamic programming methods need a model, Monte Carlo methods will have high variance and TD methods can have high bias

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, The sum of the learning rates must not converge but go to infitinty. However, the sum of the squares of the learning rates must converge.

Question 29

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 29

MC is an unbiased estimator, but it is also has high variance. TD methods are preferred because they minimise variance and also approximate the ML estimate of an MDP. TD methods can also make a trade-off between bias and variance through TD(lambda).

Question 30

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

Answer 30

Technically True, but backward methods offer a convenient way of learning online when experience cannot be repeated or is expensive to generate. If episode data is cheap or stored, then using a backward view (with eligibility traces) does not have a major benefit.

Question 31

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

Answer 31

False, there are cases where either will do better. E.g. online algorithms can better deal with non-stationary tasks.

Question 32

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

Answer 32

false. If we are simply sampling from (transition, reward) then there is no concept of states to which to apply TD-methods, which require a temporally-ordered sequence of (S,R) to apply. If there is no temporal order to the model, then it makes no sense to apply a TD method. An MC method would be better.

Question 33

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

Answer 33

False. TD(1) is MC. Assuming an update is applied at the end of an episode, it performs worse. The return is apportioned to each state proportionally to the number of times it is visited, which means it diverges with repeated presentations.

Question 34

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

Answer 34

False, empirically we see different curves. The best value of lambda will vary across problems. Short episodes may benefit from smaller values of lambda for example.

Question 35

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

Answer 35

False, non-expansions and contractions are the only things guaranteed to converge because the gradients will shrink to 0 as the operations are applied.

When saying that it is not a non-expansion, it only indicates that there is no guarantee that the updates will approach each other. However, I believe it as also not certain that the updates won’t approach each other. It might be that convergence still happens.

Question 36

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 36

False, non-expansion means that the signal is shrinking monotonically. It’s the less restrictive version of a contraction

Question 37

What is an eligibility trace?

Answer 37

An eligibility trace is a weight value corresponding to how many time steps have passed since that state “participated in producing an estimate value” (Sutto Barto p.287).
The eligibility trace defines how much a given state estimate is updated.

It can be used to calculate TD updates more efficiently. It is used to generalize TD(0) and TD(1) methods to TD(\lambda) methods.

Question 38

In Sutton 88. What is “the maximum likelihood estimate of the underlying MDP” (quoted from the paper)?

Answer 38

“In the following section, we prove that in fact it is linear TD(0) that converges to what can be considered the optimal estimates for matching future experience - those consistent with the maximum-likelihood estimate of the underlying Markov process.”

Question 39

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

Answer 39

My guess is that it’s because it is a low variance estimate with high bias and under repeated presentations that bias would go away and therefore it should converge?

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

Because TD(>0) algorithms will have variance and will therefore begin to be off. TD(0) on the other hand has no variance but is biased because of bootstrapping. On repeated presentations the bias is eliminated and therefore will converge with 0 error.

Question 41

In Sutton 88, what is Pt? What is ∇w​Pt?

Answer 41

Pt is the prediction at time t … the estimated state value

∇w​Pt is the gradient, which is the partial derivative with respect to the weights of the expectations … in the paper it was the value of the x vector, which was the input.

Question 42

In Sutton 88, what is the value of ∇w​Pt in the paper, if xt [0,0,1,0,0] under the context of a random walk example? Why?

Answer 42

∇w​Pt is xt… its use is to ‘turn off’ the all the weights for the ‘other’ states. Only the weight associated with the value 1 is updated or used for the calculations.

Question 43

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

Answer 43

While written differently, it matched the Semi-gradient TD(λ) for estimating algorithm in the book.

Question 44

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

Answer 44

IDK

Question 45

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

Answer 45

TD(0) updates slowly. This is because it’s a single step and unable to overcome it’s initial bias.

The other TD(lambda) learn from other steps so get more experience per iteration so it updates faster.

Per the paper, if there were more presentations, the handicap would go away.

Question 46

In Sutton 88, experiment 2, what kind of figure 4 would you expect if you were to give infinite sequences instead of 10? Why?

Answer 46

It would look more like Figure 3 as the experiment would be running to convergence. For 10 sequences, we are just discovering what can be learned at the start of training. Running infinitely, we’ll be more like experiment 1, running to convergence.

And I think the curves will all overlap. There is only one environment so there is really only one solution. The other curves in Figure 4 are because we’re starting from different conditions.

Question 47

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

Answer 47

My guess is the learning rate causing the alg to transition from undershooting to overshooting the true value given the calculated TD error term

Question 48

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

Answer 48

“RL with actions”

A control task is one where the agent develops a policy that it uses to interact with the environment. Contrast this with a prediction method, which only learns to predict the return, V(s) or Q(s,a). TD algorithms are a way of learning to predict the value function, which control methods can then use to develop a policy e.g. by acting epsilon-greedily with respect to the value function.

Question 49

What is Sarsa? What’s the input and output of this function?

Answer 49

SARSA is an on-policy model-free control method. It learns Q using TD learning, and selects actions using an epsilon-greedy (or soft) policy. The input is the state, reward, next state and the output are actions selected based on the learned Q-function.

Question 50

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 50

SARSA is on-policy in that it selects the actions A, A’ using the current best policy.

SARSA selects the update value from the q-table by choosing Q(S’,A’) based on S’ and the POLICY(S’) action. Then it follows that (S’,A’) for the next iteration.

Q-learning selects the update value from the q-table by choosing the maximum Q(S’, any possible action) and ignoring what the current best policy would select. Then it follows the (S’, POLICY(S’)) for the next iteration. The POLICY(S’) may not match the action chosen by the previous iteration.

Question 51

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

Answer 51

The value function estimation in SARSA is done with TD. The value function is used to do control by selecting actions (epsilon) greedily.

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

SARSA uses Generalised Policy Iteration i.e. take the current policy, evaluate it , update the policy using the new information or observed reward, repeat. The TD update is policy improvement, and the action selection is policy evaluation.

SARSA looks almost exactly like policy iteration except that it entirely uses the current policy to update values. Once it’s done with that it will do an improvement.

Question 53

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

Answer 53

True

Reward shaping won’t change the policy (so still finds the original optimal policy); but, it may find it faster.

Question 54

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

Answer 54

False

If set up wrong can cause negative potential feedback loops

Question 55

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

Answer 55

False.

False, Rmax is not guaranteed to find the optimal policy. But Rmax can help obtain near optimal results.

If the estimates of the MDP are sufficiently close to the original MDP, then the policy will be near-optimal, not necessarily optimal. Rmax leads to exploration of unknown states, which generates knowledge that can be used to estimate the value of those states (using Hoeffding Bounds) over time. If the parameters defining when “enough knowledge is enough” lead to the estimate of the MDP being tolerably close to the original, then Rmax can be said to lead to a near optimal policy with a properly tuned learning function.

Question 56

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

Answer 56

False. SARSA can learn the optimal policy but does less exploration than an off-policy algorithm. It is possible SARSA gets stuck in local optima, but not necessarily

Question 57

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

Answer 57

False. The Agent can assign a non-100% confidence in the correctness of the advice given. The Agent can also continue to learn from its own experiences

Question 58

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

Answer 58

Yes

The policy space (selecting the best action) only needs Q-values to be ‘sorted’ appropriately. By that I mean that the sub-optimal Q-values still have the best action with the highest Q-value for a particular state. Then the best action won’t change even though the Q-value has farther to go to become optimal.

Question 59

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

Answer 59

Q-learning will always converge to optimal (and correctly valued) policies under 2 conditions:
- Given a sufficiently small learning rate- one that converges when squared and diverges when added. I.e, 1/2, 1/4, 1/8…
- Each state is visited infinitely often

https://stackoverflow.com/questions/59709726/criteria-for-convergence-in-q-learning

(Practically, the state-space may be too large for Q-learning to be computationally tenable in most real-world problems)

Question 60

What are the benefits of an off-policy algorithm?

Answer 60

An off-policy algorithm can produce accurate state-value estimates independent of how good its policy is

A benefit of this is that it may do more exploration and be less likely to get stuck in local-optima

https://datascience.stackexchange.com/questions/13029/what-are-the-advantages-disadvantages-of-off-policy-rl-vs-on-policy-rl

Question 61

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 61

False

exploration is required to learn the reward distribution … and therefore the bandits with highest rewards. Too much exploration is wasting time on poor choices.

exploitation is required to receive rewards and get some benefit from the lessons learned so far. Too much exploitation is possibly missing better choices … or learning them too slowly.

Question 62

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 62

The continuous states of the Lunar Lander problem can be dealt with using function approximation to approximate the Q-function.

One pro of this technique is that it allows us to generalize states we’ve seen to similar states that have not been encountered before.

A con of this technique is that the Q-learner is no longer guaranteed to converge when using a function approximator.

Question 63

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

Answer 63

Yes, reward shaping can be used to help guide the policy search by encouraging the agent to take specific actions to follow a specific trajectory. needs to be a potential based rewarding scheme

Question 64

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 64

In general, we can use function approximation for Value, Q, Policy, and Transition/Reward functions.

The input can either be the state action pair or just the state. The output in the case of state action pair is the value for that pair, if the input is just the state it could be just the value of that state or it could be the values for all actions for that state.

Question 65

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 65

We cannot because Q learning only converges to the optimal values under the assumption that you visit each state-action pair an infinite number of times

Question 66

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

Answer 66

True … for a continuous state space you have infinite states so you’d need infinite equations.

False … if you discretize the continuous space in to discrete states, then you can use a linear function approximation.

Question 67

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 67

False, Baird’s star problem is not guaranteed to converge.

Question 68

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

Answer 68

True, any generalization of an MDP would result in another MDP.

Question 69

Problems that can be represented as POMDPs cannot be represented as MDPs.

Answer 69

False. You can go from an POMDP over some state-space to a larger MDP over a belief-space.

Question 70

We can represent any POMDP as a PSR, however some classes of POMDPs will be too large to deal with as PSRs.

Answer 70

False. Lot of algorithms will work here. PSR as noted is a great counter example.

Question 71

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

Answer 71

It is the “knows what it knows” framework. It provides a set of algorithms that can map directly the input X to output Y. It makes guarantees that it will never be wrong and instead just say it doesn’t know an answer if an out of distribution input is found. It can make bounding guarantees for how many examples it needs before it can make a non-unknown prediction.

Question 72

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

Answer 72

PAC - Correct labels for the outputs are given in training data and it will not make mistakes within a certain probability and be accurate to a certain degree. It is a good choice for supervised learning problems. It allows for some mistakes due to the approximate correctness

KWIK - It does not allow for mistakes, and can be given inputs where the outcome is incorrect. It also is trained with on-policy data. Limited by the number of hypothesis or requests/data it can make to the problem

Question 73

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

Answer 73

The size of the hypothesis space minus 1:

|H| = N * (N - 1)

Bound = |H| - 1

N - The size of the observation space (i.e. in Homework 5, this was the number of patrons)

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

Yes because you are given the required information directly. The worst case is now just N-1.

The worst case would be where all patrons come on first night and one drops out each succeeding night. For 8 patrons, you know on event 7 (worst case) when you’re left with two patrons. You’ve found both; but, not identified which is which. One more time with them split to identify them exactly. … so maybe worst case is N.

Question 75

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 75

False. For some hypothesis classes, KWIK can take more time than MB since it predicts “don’t know” whereas MB can make a guess when uncertain.

Question 76

Let’s say we are doing a repeated version of rock paper scissors and we want to maximize the usual average payoff. What’s the minimax profile that we learned in game theory reloaded, of this new rock paper and scissors game?

Answer 76

I believe -1 because when forced to hava a pure strategy, you can’t protect yourself from the other player using the best action against you.

I think the Security Profile would be 0 with the best strategy being to choose random actions.

Question 77

Then what’s the feasible and “preferable region” of this new rock paper and scissors game?

Answer 77

a line between 1,-1 & -1,1 that also goes through 0,0

Question 78

What does the folk theorem / two player plot tell us? What are all the Nash equilibria in this new version of rock paper scissors?

Answer 78

I believe it would be for each player to have a mixed strategy to choose each action randomly?

Question 79

What’s the subgame perfect equilibrium of this game given by computational folk theorem? How do we find it in poly time claimed by computational folk theorem?

Answer 79

IDK check notes

Question 80

Why does the “folk theorem” help us to solve prisoner’s dilemma (i.e. so that people will not always defect to each other)?

Answer 80

By using threats, any payoff profile that strictly dominates the minimax profile can be realized.

Question 81

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

Answer 81

True because MDP’s can be a generalized form of Markov Game’s when there is only 1 other opponent

Question 82

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

Answer 82

False. Dynamic programming techniques like value iteration and policy iteration can solve an MDP for its optimal policy in polynomial time.

Question 83

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 83

False, the objective is to maximize the “policy flow”.

Question 84

True or False: Nash equilibria can only be pure, not mixed. Why?

Answer 84

False, a pure Nash strategy is one without randomization in actions to take while a mixed Nash strategy is one where there is randomization (take action with probability p)

Question 85

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 85

True. Even certain very simple games, like coordination game, have no optimal pure strategy.

Question 86

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

Answer 86

False. With any finite games the “folk theorem” will not apply as it becomes rational to cease cooperation before the last turn.

Question 87

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 87

False. This is the “Grim Trigger”… Pavlov cooperates whenever both players make the same choice (CC or DD), otherwise chooses D

Question 88

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

Answer 88

False. It indicates that every subgame be a Nash equilibirum.

Question 89

How is an option defined?

Answer 89

An option is a generalization over an action. It can be the composition of multiple actions.

Question 90

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

Answer 90

SMDPs are an MDP where transition dynamics can depend on time. It is called semi-Markov because now the transition no longer depend on the current state but on the time elapsed in that state.

Question 91

Does SMDP generalize over MDP?

Answer 91

yes… depends on how you construct the options. Constructed poorly, you do not get the convergence guarantees that you do over the MDP

Question 92

Can we use value iteration on SMDP given a model (transitions and reward function)? Notice that not all options can be executed in all states. Is that a problem for our value iteration on SMDP?

Answer 92

IDK

False because if an option can not be execute for all states, it could result in an error when implemented saying the action is not valid. There would be a problem using plain value iteration when used on SMDP’s

Question 93

Is value iteration guaranteed to converge for an SMDP?

Answer 93

Yes

Question 94

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

Answer 94

No, it only guarantees hierarchical optimality.

Question 95

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

Answer 95

Question 96

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

Answer 96

True.

The options are really just a combination of many atomic actions, rewards, discounts, and state transitions. You could conceivably unravel any option to get back to a conventional MDP.

Question 97

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 97

The Agents only cooperate if each benefits more from cooperating than acting alone. In many cases, cooperation leads to one Agent getting a high reward with the other Agent not being as well rewarded. Without a side payment from the Agent that was highly rewarded, the poorly rewarded Agent would not have reason to cooperate

The reward must be high enough that it’s the best option for the poorly rewarded Agent, while low enough that the well-rewarded Agent benefits more than acting alone even after paying out