Exam Study

Question 1

A Markov Process is a process in which all states do not depend on actions

Answer 1

True. Markov means that you don’t have to condition on anything past the most recent state. A Markov Decision Process is a set of Markov Property Compliant states, with rewards and values

Question 2

Decaying Reward encourages the agent to end the game quickly instead of running around and gathering more rewards

Answer 2

True. As reward decays the total reward for the episode decreases, so the agent is encouraged to maximize total reward by ending the game quickly.

Question 3

R(s) and R(s,a) are equivalent

Answer 3

True. It just happens that it’s easier to think about one vs. the other in certain situations

Question 4

Reinforcement Learning is harder to compute than a simple MDP

Answer 4

True. You can just use the Bellman for MDP but Reinforcement Learning requires that you make observations and then summarize those observations as values

Question 5

An optimal policy is the best possible sequence of actions for an MDP

Answer 5

True, with a single caveat. The optimal policy is a policy that maximizes reward over an entire episode by taking the argmax of resulting values of actions + rewards. But MDPs are memoryless, so there is no concept of “sequence” for policy.

Question 6

Temporal Difference Learning is the difference in reward you see on subsequent time steps.

Answer 6

False. Temporal Difference Learning is the difference in value estimates on subsequence time steps.

Question 7

RL falls generally into 3 different categories: Model-Based, Value-Based, and Policy-Based

Answer 7

True, Model-Based is essentially using the Bellman Equation to solve a problem Value-Based is Temporal Difference Learning Policy-Based is similar to Value-Based, but it solves in a finite amount of time with a certain amount of confidence (in Greedy it’s guaranteed)

Question 8

TD Learning is defined by Incremental Estimates that are Outcome Based

Answer 8

True. TD Learning thinks of learning in terms of “episodes”, which it uses to estimate the transition functions rather than having a predefined model.

Question 9

For learning rate to guarantee convergence, the sum of the learning rate must be infinite, and the sum of the learning rate squared must be finite.

Answer 9

True. This is called contraction mapping and it guarantees convergence.

Question 10

All of the TD learning methods have set backs, TD(1) is inefficient because it requires too much data and has high variance, TD(0) has a maximum likelihood estimate but is hard to calculate for long episodes.

Answer 10

True. This is why we use TD(Lamba), which has many fo the benefits of TD(0) but is much more performant. Empirically, lambas between 0.3 and 0.7 seem to perform best.

Question 11

To control learning, you simply have the operator choose actions in addition to learning.

Answer 11

True. States are experienced as observations during learning, so the operator can influence learning.

Question 12

Q-Learning converges

Answer 12

True. The Bellman Equation satisfies a Contraction Mapping where the sum of all is infinite, but the sum of all squared is less than infinite. It always converges to Q.

Question 13

As long as the update operators for Q-learning or Value-iterations are non-expansions, then they will converge.

Answer 13

True. There are expansions that will converge, but only non-expansions are guaranteed to converge independent of their starting values.

Question 14

A convex combination will converge.

Answer 14

False. It must be a fixed convex combination to converge. If the value can change, like the Boltzmann exploration, then it is no guaranteed to converge.

Question 15

In Greedy Policies, the difference between the true value and the current value of the policy is less than some epsilon value for exploration.

Answer 15

True

Question 16

It serves as a good check for how long we run value iteration until we’re pretty confident that we have the optimal policy.

Answer 16

True

Question 17

For a set of linear equations, the solution can be found in polynomial time.

Answer 17

True

Question 18

For Policy Iteration, Convergence is exact and complete in finite time.

Answer 18

False. This is only true for a Greedy Policy. It is true that it will be optimal policy, however.

Question 19

The optimal policy will dominate all other policies in finite time.

Answer 19

This is true for greedy policy. This is because policies dominate on a state-by-state bases, so we don’t get stuck in local optima.

Question 20

We get strict value improvement anytime we don’t have a policy that is already optimal.

Answer 20

True. Any time a policy is already optimal then a step of policy iteration results in a value non-deprovement. It might not get better, but it won’t get worse.

Question 21

You can change the reward function only by multiplying the reward.

Answer 21

False. You can also change the reward function by shifting a constant, or using a potential functions. You can also scale positively, otherwise you may swap max and min by accident.

Question 22

You can change the reward function only by adding a constant.

Answer 22

False. You can also change the reward function by multiplying the reward by a positive constant, or using a potential function.

Question 23

You can change the reward function only using a potential function.

Answer 23

False, you can also change the reward function by multiplying the reward by a positive constant, or adding a constant.

Question 24

You can change the reward function to learn faster only by using a potential function.

Answer 24

True. Multiplying a positive constant or shifting by a constant will not work, they work in roughly the same time.

Question 25

You can change the reward function to learn faster by multiplying by a positive constant or shifting by a constant.

Answer 25

False. You can only speed up learning with a potential function.

Question 26

Even when you use reward shaping, you’ll still always find the optimal policy.

Answer 26

False. You can sometimes end up in sub-optimal feedback loops.

Question 27

The Gitten’s Index can be used for all Q-Learning algorithms.

Answer 27

False. This actually only works for K-Armed Bandit spaces, not for continuous spaces. This is because it depends on a ratio of observations to determine confidence, which cannot be achieved in spaces where the ratio changes.

Question 28

The Gitten’s Index is the only metric for K-Armed Bandit problems.

Answer 28

False, there are actually several, including: - Identify optimal arm in the limit - Maximize the expected reward over a finite horizon - Find best - Few mistakes - Do well (the last 3 are related and have equivalent algorithms)

Question 29

If you have an algorithm that can find the best arm, you can find an algorithm that can find an arm with few mistakes

Answer 29

True. If you have an algorithm that finds e-best with a probability of 1-delta in tau pulls, you will find that same arm with that same probability with an upper bound tau for the first algorithm.

Question 30

We can estimate what we know using Hoeffding bounds and Union bounds.

Answer 30

True. In stochastic decision problems, we can convince ourselves that we have a sufficiently accurate estimate using those bounds. This lets us get near optimal rewards.

Question 31

In a deterministic MDP, Rmax will cause us to explore all states by assuming that unexplored or unknown states will have the maximum possible reward.

Answer 31

True. In a sequential decision process, we can convince ourselves that we have a sufficient amount of information by proving that we have visited all states.

Question 32

Using Rmax, once all edges are known, the algorithm will no longer make mistakes.

Answer 32

True. Because in step 3 we solve the MDP using the Bellman equations, which will give us the optimal policy and therefore never make a mistake.

Question 33

Using Rmax, you will always visit all unknown states.

Answer 33

False. Sometimes you will end up in a suboptimal reward loop if the discount factor is too low or the state is too far away.

Question 34

Using Rmax, you will never make any mistakes.

Answer 34

False. In order to learn new states, you may make mistakes in order to discover those states. The maximum number of mistakes that Rmax will make over the course of it’s lifetime is O(n^2 K). Where n is the number of states and k if number of actions.

Question 35

Using a simulation lemma (theorem), if you have an estimate of the real MDP, then optimizing the rewards in the estimate will be near optimal for the real MDP.

Answer 35

True. If the difference between the transition functions is less than or equal to alpha, then the difference between the rewards is also less than or equal to alpha.

Question 36

If all transitions are either accurately estimates or unknown, optimal policy is either near optimal or an unknown state is reached quickly.

Answer 36

False. Using the explore or exploit lemma (theorem), Rmax guarantees that we will either explore or be near optimal with ***high probability***, ***not guaranteed***. The maximum run time is either guarantee near optimal or learn something new is bounded by the number of states times the number of actions (n*k)

Question 37

There is both a need and a method to do generalizations in RL.

Answer 37

True. The need comes from the fact that there can be zillions upon zillions of states. In a continuous space, it’s even impossible to visit every state once. The method is to take what we learned in supervised learning, specifically linear function approximation.

Question 38

Policy Gradients are the most popular for linear function approximation for generalized reinforcement learning.

Answer 38

False. Value Function Gradients are the most popular because there’s been a bunch of success there. However, in the Robotics sector, policy gradients have been very successful.

Question 39

A Linear Value Approximator always works

Answer 39

False. Baird’s Counterexample.

Question 40

POMPs Generalize MDPs

Answer 40

True. All you need to do is add observables and an observation function to the MDP tuple. However, you cannot go in reverse.

Question 41

You can always infer a state from observations.

Answer 41

False. You can infer the probability of being in a state, but you can’t always definitely say you are in a state. A POMP is just an MDP with probability 1.

Question 42

A POMP has a finite number of states.

Answer 42

Somewhat false. The underlying MDP has a finite number of states, but because our observations (belief states) are probability distributions, the actual number of states is infinite.

Question 43

A POMDP can be written in a finite way.

Answer 43

True. Convex piecewise linear belief space of a finite set of linear functions (which can represent an infinite number of inputs). Sondik

Question 44

A vector space of 0 with size s is the only maximum of belief state vectors.

Answer 44

False. Because you take the dot product of the result, you need a matching size. One way to do this is to make those all zero, but it also works if you use the reward vector.

Question 45

The maximum of all maximums in a bag of vectors is the piecewise-linear and convex value.

Answer 45

True. And you’ll maintain a finite number of vectors in doing so. You’ll eliminate the infinite set of vectors by taking their sum and product a new vector.

Question 46

You can eliminate vectors that are not participating in a piecewise-linear and convex value function.

Answer 46

True. Any vector that is dominated by another vector (that is, smaller at all points in the belief space) can be removed in linear time. You can also remove non-dominated vectors in O(LP) time.

Question 47

The Optimal Policy converges in finite time for POMPs.

Answer 47

False. POMDPs have infinite states so they cannot converge in finite time. It is however true that we get some arbitrarily “good” approximation of the optimal value function after some finite number of iterations.

Question 48

Planning in POMDPs is undecidable

Answer 48

True. You cannot definitely say what the optimal action given a state, if you could solve that problem you could solve the halting problem.

Question 49

A partially observed, uncontrolled process is called a POMP, and an observed, controlled process is called a MDP.

Answer 49

False. POMDPs are partially observed and controlled. Markov Cains are observed, uncontrollable processes.

Question 50

You can solve a POMP with piecewise linear and convex functions.

Answer 50

True. This is essentially taking the “max” of a POMP’s belief space. Since we don’t affirmatively know which state of the real MDP we are in unless the MDP = POMDP, we take actions based on the maximums of piecewise linear functions, which end up being convex when they are pieced together.

Question 51

Bayesian RL gets its name from Bayes Rule

Answer 51

True. It comes from the fact that as we learn about which state we’re actually in (through process of elimination) which converts to a POMDP, we normalize our belief states transition probability using Bayes

Question 52

Exploration is exploitation.

Answer 52

True. In Bayesian RL, you can simply maximize the reward and make no distinction on whether actions taken are exploring or exploiting. This is because the transition functions are unknown, and are instead given probability based on Bayes Rule, which converts to a POMDP.

Question 53

RL is actually planning in a continuous POMDP.

Answer 53

True. The hidden state is the parameters of the MDP that we’re trying to learn. So, essentially, through Bayesian RL, we recreate the MDP.

Question 54

RL is hard because of the delayed reward.

Answer 54

True. There’s also a difficulty of bootstrapping (exploration), and the scaling of the state space and action space.

Question 55

You can more easily solve continuous space problems by adding actions.

Answer 55

True. This is called temporal abstraction and while counterintuitive, it actually makes the space simpler. This is because instead of taking several individual actions, your policy is one “big” action which is a collection of actions. State abstraction (value-iteration) is like treating a bunch of states equivalently, Temporal abstraction is like treating a bunch of time-steps equivalently.

Question 56

In Temporal Abstraction, in order to get a regular MDP, all you need to do is set all termination probabilities of the options(s) to 1.

Answer 56

False. Options are a mapping of state-action pairs to some probability of taking the option as well. To get an MDP, you need to set up your initialization set and policy correctly as well. - The initialization set must be all valid actions for that particular state, and - The policy must have probability 1 for the action you wish to take, and 0s everywhere else.

Question 57

Variable time steps and atomic time steps are interchangeable.

Answer 57

True. Since you are summing the discounted reward for each of the atomic time steps that make up the variable time step (option), they are interchangeable at a single time step. In fact, MDPs are simply a special case of SMDPs, which are a generalization of MDPs, where at each time step the terminating probability for all possible result states of all available actions is 1 for time-step 1.

Question 58

SMDPs satisfy all the requirements of an MDP.

Answer 58

False. Because options depend on the number of steps k taken between steps, they are no longer stateless, bur rather ***sequential****, which violates the Markovian Property. For Semi-Markov decision problems (SMDPs), an additional parameter of interest is the time spent in each transition.

Question 59

Options perform temporal abstraction to shrink time-steps.

Answer 59

Somewhat false. There’s also a chance that options will shrink state-space through state abstraction, but it depends on how your options are defined. Additionally, if your options cover all possible states and time-steps, then nothing will shrink, since at that point it’s just the MDP instead of an SMDP.

Question 60

Modular RL is a field that studies Q-Learning through the concept of Arbitration.

Answer 60

True. 3 examples of this are: 1. Greatest Mass Q-Learning, which adds up all the Q-values for state-action pairs per goal/agent and takes the largest one (so essentially, the goals are voting on which action to take) 2. Top Q-Learning, in which the largest Q-value wins across all goals/agents 3. Negotiated W-Learning, in which the agent with the most to lose gets to choose the action.

Question 61

Greatest Mass Q-Learning is effective because all goals are satisfied by the action taken.

Answer 61

False. In fact, the opposite is true. Since agents are summing their Q-values for the state-action pairs, there is a possibility that none of the agents are satisfied by the action selected simply due to the intense disagreement. While it is possible that each goal’s maximum Q-value is the same and all agents would be satisfied, this is not always the case. Worse, it is possible when n goals < m actions that the least satisfactory action for all n agents ends ip being selected simply because that’s the only action that all n agents agree on.

Question 62

Top Q-Learning is effective because the goal that dominates will at least have it’s needs satisfied.

Answer 62

False. It is possible that the largest Q-value for a given agent is actually only slightly larger than the agent’s other actions, but it just happens to have the largest Q-value. So in this situation, the agent doesn’t actually care about which action it selects, but it still gets to choose which action to take simply because it’s Q-values are larger.

Question 63

In Negotiating Q-Learning, you maximize the Q-value of all agents.

Answer 63

False. For 2 reasons: 1. The agent that selects the action is the agent with the most to lose, not the most to gain, so you don’t necessarily find actions that maximize the Q-value. 2. You don’t maximize the value so much as minimize the loss of all agents, since you are choosing the agent with the largest loss and guaranteeing that the loss is minimized.

Question 64

Modular RL is impossible.

Answer 64

True. This is due to Arrow’s Impossibility Result, which states that it is not possible to construct a fair voting result. Because all of the Modular RL/Arbitration actions involve some kind of voting: - Greatest Mass Q-Learning through aggregation - Top Q-Learning through domination of top results - Negotiated Q-Learning through selecting the agent with the most to lose, you cannot construct these systems due to the lack of Units in the Q-values. (Metric vs Imperial example)

Question 65

In Monte Carlo Tree Searches, the best rollout policy is behave randomly.

Answer 65

False. You can get a better performance by applying failure constraints to your selection process.

Question 66

Monte Carlo Tree Search is useful for large state spaces.

Answer 66

True. This is because planning time is independent of the state space. The downside is that you need lots of samples to get a good estimate. Monte Carlo does depend on how far you look into the future, and has a running time that is exponential in the horizon O( (|A|*x)^H )

Question 67

Prisoner’s Dilemma-like problems (zero-sum games) will have different results played over multiple games than a single instance of game.

Answer 67

False. Even if the agents play relative to their observed reward in previous instances, they will all act relative to the expected terminal state, which will be the single-game result. Because of this, the single-game result. Because of this, the single-game result back-propagates identical results back through the games.

Question 68

All Zero-Sum 2 player games can be represented by a matrix.

Answer 68

True. This is because you can represent the reward of a pair of decisions by each player as a single value. The caveat is that you can infer from game to matrix, but not matrix to games.

Question 69

In a 2-player, zero-sum game, minimax = maximin, and there always exists an optimal pure strategy for each player.

Answer 69

False. The game must have perfect information. If you have both of these things, then there will be an optimal row/column that both players will see as maximizing their reward. The game must also be deterministic, but non-deterministic games can be changed to deterministic games by weighting the rewards by their probabilities.

Question 70

A deterministic game and a non-deterministic game are both conceptually equal.

Answer 70

True. Because the non-deterministic rewards can be simplified to their rewards weighted by their probabilities, you can still create the minimax-maximin matrix and find the optimal solution for both players (aka the value of the game).

Question 71

A game of perfect information and a game of hidden information are both conceptually equal.

Answer 71

False. A game of hidden information does not satisfy the requirement of minimax = maximin, so you can’t treat them equally. Hidden information games are solved through mixed strategies, or taking actions based on probability rather than based on perfect expected outcome, the probability being the solution to multiple linear equations for each player.

Question 72

A zero-sum game and a non-zero sum game are conceptually equal.

Answer 72

False. Because the rewards are different for non-zero-sum games, the Nash Equilibrium is not necessarily the minimax for the entire game, but rather the equilibrium where neither player can be convinced to switch their action (a.k.a neither player will get a greater reward for switching)

Question 73

A repeated 2-player bimatrix game with a certain end is equal to a repeated 2-player bimatrix game with an uncertain end.

Answer 73

False. Even though the game can be given an average number of plays, the strategies to maximize reward are not the same. For an unbounded series of games, you must define optimal strategies in terms of only the previous game, not future games.

Question 74

In repeated games, the possibility of retaliation opens the door for cooperation.

Answer 74

True. Because there are now strategies that each player can take in order to both create a plausible threat, and to also converge on the maximum possible value. The best example of this is Pavolv, where you can cooperate if you agree, and defect if you disagree. This converges to a cooperation for all plausible threat strategies.

Question 75

You can build a Pavolv-like machine for any game.

Answer 75

False. It must be a 2-player, bimatrix game. It will construct a perfect nash equilibrium in polynomial time. There are 3 possible results: Pavlov, Zero-Sum-Like, or only a single player improves.

Question 76

Nash-Q Converges.

Answer 76

False. Nash-Q can have different values for equilibria, so it does not converge to a single strategy.

Question 77

DEC-POMPs are impossible to solve.

Answer 77

True. Just like POMDPs they are impossible to solve. They are NEXP-complete for a finite horizon.

Question 78

Inverse Reinforcement Learning takes Behavior and infers the environment and rewards, in contrast to Reinforcement Learning which takes the environment and rewards and infers behavior.

Answer 78

False. In both IRL and RL the environment is observed by the agent(s).

Question 79

Reward Shaping and Policy Shaping are the same thing.

Answer 79

False. When working off a teacher’s +/- data for a given action space, Reward Shaping arbitrarily assigns +1 and -1. Not only is this not correct, but it won’t necessarily teach the agent the correct policy because the rewards are not scaled. Policy shaping is the literal policy based on +/- input, independent of reward.

Question 80

You need to include confidence of the human policy in order to calculate policy during policy shaping.

Answer 80

False. Confidence is baked into the policy already. This is because of a combination of Bayes Theorem and observations normalizing the policy. While we become less and less confident in the human’s observations over time, and start favoring the agent’s policy, these are already baked into their respective policies so we only need to combine them.

Question 81

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

Answer 81

True. The reward state simply becomes zero for additional states.

Question 82

In Reinforcement Learning, recent moves influence the outcome more than moves further in the past.

Answer 82

False. Recent moves influence the outcome less due to contraction. However, they end up influencing the same amount as all previous moves due to averaging.

Question 83

An MDP with a fixed policy is a Markov Chain with rewards.

Answer 83

True. Since a fixed policy never changes, you will experience the same chain every single time.

Question 84

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

Answer 84

False. Monte Carlo is TD(0), but we prefer TD(Lamba) so that that states can have multi-step lookaheads and be influenced not just by immediate rewards, but also future rewards.

Question 85

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

Answer 85

True. But backward is easier to implement so we prefer it.

Question 86

The accuracy of the return policy is the only metric we care about when evaluating a learner.

Answer 86

False. We also care about the speed at which learning occurs, and the data that it requires.

Question 87

Predictions based on minimizing error – for example Widrow-Hoff – will be optimized as error by definition is minimized.

Answer 87

False. Sutton 1988 notes that Widrow-Hoff minimizes error on the training set, but that isn’t the same as an yielding an MLE estimate.

Question 88

TD methods are unbiased and accurate as they are based directly on the outcome of each trial/experience.

Answer 88

False. The initial values influence actions taken for each individual episode without exploration.

Question 89

An update that is an expansion will not converge.

Answer 89

False. Only non-expansions are guaranteed to converge, but there are fringe cases that will still converge.

Question 90

MDPs are a type of Markov Game.

Answer 90

True. They can be thought of as a 1-player Markov Game.

Question 91

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

Answer 91

True. You can change the reward function without changing the optimal policy by either multiplying by a constant, adding a scalar, or a non-linear potential-based reward.

Question 92

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

Answer 92

Somewhat true. You can create rewards that explore the MDP better and avoid sub-optimal states, but you can also create rewards that get caught in loops and do not converge.

Question 93

Thinking back to HW #1, state-based bonuses are an effective way to shape the rewards.

Answer 93

False. If you do this the MDP will converge to those bonus states rather than trying to explore. You need to have some kind of penalty or time decayed reward for those states for them to be effective.

Question 94

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

Answer 94

True. The optimal policy of the underlying MDP cannot be better than the one where unknown states are assigned an optimistic value of Rmax.

Question 95

In a k-armed bandit problem, even if you have found the best arm to pull you still must explore and try another.

Answer 95

False. If you’ve found the best arm then you’ve found the best arm with probability 1-delta and there’s no need to try other arms.

Question 96

Potential-Based shaping is equivalent to modifying initial Q-values.

Answer 96

False. Because potential-based shaping modifies rewards, and those rewards are constant, whereas Q-values can change.

Question 97

The credit assignment problem refers to the state that gives the most reward on an MDP.

Answer 97

False. It refers to temporal assignment of credit. You are propagating value backwards.

Question 98

Model-Based Reinforcement Learning is the use of supervised learning models such as neural networks to solve large state space RL problems.

Answer 98

False. Model-based refers to having a perfect information MDP (ie. all transition functions, states, and actions are known and perfectly observable). You can either have the MDP given to you, or you can estimate it using sampling. Once you have the model, you can solve it using the Bellman Equations.

Question 99

Value-Iteration is one of the most important model-free reinforcement learning methods.

Answer 99

False. Because Value-Iteration requires a model.

Question 100

Off-policy agents learn the values of a policy different than the policy they are acting under.

Answer 100

True. Because they are taking different actions, they are seeing different states and rewards than the greedy policy.

Question 101

Only non-linear function approximation has been proven to converge when used with the right hyper-parameters.

Answer 101

False. Only linear.

Question 102

POMDP are partially-observable because they are missing the MDP. An example this is model-free reinforcement learning problems.

Answer 102

False. POMDPs know the MDP, but they don’t know where they are in the MDP. Instead of affirmative states, they have belief states and observables.

Question 103

Grim trigger strategy means a player will cooperate for the entire game regardless of the other player’s action.

Answer 103

False. Grim Trigger strategy means a player will cooperate until the opponent does not, then the player uncooperates (take revenge) for the remainder of the game.

Question 104

Bayesian RL is a model-based approach that relies heavily in statistical methods such as Bayes Rule.

Answer 104

False. Bayesian RL is a statistical approach to RL that uses Bayes Rule, but is not necessarily model-based. You do not need to know the model ahead of time in order to use it.

Question 105

DEC-POMDPs is a modeling framework for cooperative problems under uncertainty.

Answer 105

True. Agents are acting based on local observable information to maximize a joint reward.

Question 106

Model-based reinforcement learning agents can solve environments with continuous state variables because they are able to learn the transition and reward function.

Answer 106

False, they solve environments regardless of whether they’re continuous or discrete.