CS7642_Week8

Question 1

From an algorithmic perspective, what makes RL hard?

Answer 1

1. Delayed reward (i.e. week feedback signals)
2. Bootstrapping (need exploration)
3. # of states, # of actions (state spaces grows massive quickly)

Question 2

What is temporal abstraction?

Answer 2

Making the action space bigger. Think about navigating in a house to the bathroom. Instead of saying take 30 steps to the right then 10 steps to the left, we might just say, go to the first doorway, walk down the hallway, and open the door on your left.

Question 3

Using temporal abstraction, backing up values is slower than it otherwise would be? (True/False)

Answer 3

False. If we’re backing up over fewer states/actions, the information propogates back to earlier states more quickly.

Question 4

An option generalizes the idea of an action? (True/False)

Answer 4

True. It’s atomic in the sense that it’s a wrapper that allows us to have more complicated actions that kind of run their own subroutine, then return the reward that was gathered in that subroutine, even though the number of time steps taken may be variable.

Question 5

What is the difference between a regular MDP and an SMDP (semi-MDP)?

Answer 5

A SMDP allows us to take variable length time steps.

Question 6

We always have to treat MDPs and SMDPs differently? (True/False)

Answer 6

False. Once we’ve defined the proper form of the Bellman operator for the SMDP, we can essentially treat the SMDP as we would any regular MDP.

Question 7

The number of steps you take in an SMDP don’t matter? (True/False)

Answer 7

False. This is why we define SMDPs with a variation of the Bellman operator such that we can treat the SMDP and MDP as the same, even though the time that it takes to accumulate reward in each of the options it takes might be variable.

Question 8

An SMDP will converge to the optimal solution regardless of the options we design? (True/False)

Answer 8

False. This gives us the idea of hierarchical optimality. We can guarantee optimality with respect to the options that we have, but we can’t guarantee that particular set of options is in fact optimal.

Question 9

Monte Carlo Tree Search isn’t useful for large state spaces? (True/False)

Answer 9

False. This is one of its principal benefits. Planning is also time independent of the size of the state space in MCTS. The trade-off is that you need lots of samples. However, running time grows exponentially.

Question 10

What are the three types of abstraction?

Answer 10

1. Temporal abstraction
2. Goal abstraction
3. State abstraction

Question 11

In a 2-player zero-sum deterministic game of perfect information, minimax == maximin? (True/False)

Answer 11

True.

Question 12

In a 2-player zero-sum deterministic game of perfect information, there is never an optimal pure strategy for each player? (True/False)

Answer 12

False. There is always an optimal pure strategy in a 2-player zero-sum deterministic game of perfect information.

Question 13

In a 2-player zero-sum non-deterministic game of perfect information, minimax != maximim? (True/False)

Answer 13

False.

Question 14

In a 2-player zero-sum non-deterministic game of hidden information, minimax != maximim? (True/False)

Answer 14

True. This is where the minimax/maximin equivalence breaks down for zero-sum games. This is because Von Neumann theorem breaks down in presence of imperfect information.

Question 15

When plotting the probability distributions for two mixed strategies, the intersection is the optimal strategy? (True/False)

Answer 15

False. Similar to the PWLC idea. Find the maximum minimum on the non-dominated piecewise surface to find the optimal strategy.

Question 16

What type of game is prisoner’s dilemma an example of?

Answer 16

2-player NON-zero sum non-deterministic game of hidden information.

Question 17

In a 2-player zero-sum deterministic game of perfect information, it doesn’t matter if agents are rational? (True/False)

Answer 17

False. Each player recursively is assuming that you’re doing what’s best for you.

Question 18

What is a Nash Equilibrium?

Answer 18

A Nash equilibrium exists IFF you randomly chose one of the players and gave them the chance to switch, they would have no reason to do it.

Question 19

Nash Equilibrium only applies to pure strategies? (True/False)

Answer 19

False. NE is just a probability distribution over strategies, which can be pure or mixed strategies.

Question 20

In an n=player pure strategy game, if elimination of strictly dominated strategies eliminates all but one combination, that combination is the unique Nash Equilibria? (True/False)

Answer 20

True

Question 21

Any Nash Equilibria will survive elimination of strictly dominated strategies? (True/False)

Answer 21

True

Question 22

For any finite game with a finite number of n-players and, there exists at least one Nash Equilibria? (True/False)

Answer 22

True.