Chapter 7: Dynamic Choice

Question 1

What are the components to a dynamic programming problem?

Answer 1

Actions, histories, strategies, law of motion, the objective function, and the constraint.

Question 2

Define a strategy

Answer 2

Maps a history into an action or a distribution across actions. Each strategy and history pair then generate a distribution measure over future histories,

Question 3

Bellman Equation

Answer 3

optimal value function today is the supremum of the expected optimal value function tomorrow given tomorrow’s history.
Note the emphasis on the optimal value function, not the function given the strategy.

Question 4

Conserving strategy

Answer 4

optimal value function equals the optimal value function of the next period, under the expectation of the strategy.

Question 5

Unimprovable strategy

Answer 5

value function given strategy today equals the optimal value function tomorrow given the current strategy is played through.

Question 6

Conserving vs Unimprovable

Answer 6

A conserving strategy does not prevent the optimal value function from no longer being the optimal value function.
An unimprovable strategy is a strategy that generates a better outcome than all other strategies for the next period, supposing the strategy is played in the next period.

Question 7

If a strategy is optimal, then it is

Answer 7

both conserving and unimprovable.

Question 8

In any finite horizon problem,

Answer 8

every conserving and unimprovable strategy is optimal.

Question 9

Upper convergent

Answer 9

The limit of the upper bar utility function equals u(h) as t goes to infinity.
Upper bar u is given by the supremum of all histories, given that the history before time t is held constant.

Question 10

Lower convergent

Answer 10

The limit of the lower bar utility function equals u(h) as t goes to infinity.
Lower bar u is given by the infimum of all histories, given that the history before time t is held constant.

Question 11

When is a conserving strategy optimal

Answer 11

if it is upper convergent.

Question 12

When is a unimprovable strategy optimal

Answer 12

if it is lower convergent.

Question 13

Example of conserving strategy

Answer 13

Always waiting and never taking an offer

Question 14

Example of unimprovable strategy

Answer 14

Kicking the can down the road large M number of times.

Question 15

Properties of additive rewards (3)

Answer 15

1. If all rewards are positive, utility is lower convergent so every unimprovable strategy is optimal.
2. If all rewards are negative, utility is upper convergent so every conserving strategy is optimal.
3. If functions are uniformly bounded, delta < 1, every unimprovable strategy and conserving strategy is optimal.

Question 16

Typical Approach to Dynamic Programming problems…

Answer 16

Show that a strategy is unimprovable and lower convergent. Why? Since we don’t know what f^* actually looks like.

For discounted additive utilities, don’t need lower convergence!

Question 17

Transience

Answer 17

Something is (upper) transient if there is a subset of histories that happen almost surely for a strategy, have bounded utility, and for which the utility is (upper) convergent.

Question 18

Use of transience

Answer 18

If a strategy is unimprovable and lower transient, then it is optimal.
If a strategy is conserving and upper transient, then it is optimal.

Question 19

Why transience?

Answer 19

Allows us to restrict our attention to relevant histories rather than proving for all histories.

Question 20

Value iteration results (2)

Answer 20

1. Iterating on the value function of a strategy converges to the infinite time-horizon value for said strategy.
2. Iterating on the optimal value function (assuming discounting and bounded rewards) yields the infinite time-horizon optimal value.

If we can find the optimal strategy via unimprovability, the second bullet is less important.