Dynamic Programming

Chapter 4 develops policy evaluation, policy iteration, and value iteration when a complete model of the environment is available.

Exercise 4.1

Since the transition probabilities are deterministic, we can simplify the equation to:

Exercise 4.2

Since the transition probabilities are deterministic and $\gamma = 1$, we can write the state values as:

For the first scenario, where the $\text{up}$ action at state $15$ leads to state $13$, we have:

For the second scenario, where the $\text{down}$ action at state $13$ also leads to state $15$, we have:

Solving the two equations simultaneously, we get:

Exercise 4.3

The analog of (4.3) is:

The analog of (4.4) is:

The analog of (4.5) is:

Exercise 4.4

To fix this bug, we should update the policy improvement algorithm to only update the policy if there's a strict improvement in the value function.

$\text{policy-stable} \leftarrow \text{true}$

$\text{For each } s \in \mathcal{S}$:

$\quad \text{old-action} \leftarrow \pi(s)$

$\quad \text{For each } a \in \mathcal{A}$:

$\quad \quad Q(s, a) \leftarrow \sum_{s',r} p(s', r \mid s, a) \Big[ r + \gamma V(s') \Big]$

$\quad \text{best-action} \leftarrow \argmax_a Q(s, a)$

$\quad \text{if } Q(s, \text{best-action}) > Q(s, \text{old-action}):$

$\quad \quad \pi(s) \leftarrow \text{best-action}$

$\quad \quad \text{policy-stable} \leftarrow \text{false}$

$\text{If policy-stable, then stop and return } V \approx v^* \text{ and } \pi \approx \pi^* \text{; else go to 2}$

Exercise 4.5

1. Initialization

$Q(s,a) \in \mathbb{R}, \quad \pi(s) \in \mathcal{A}(s), \quad \forall s \in \mathcal{S}, a \in \mathcal{A}(s) \quad Q(\text{terminal}, a) = 0$

2. Policy Evaluation

$\text{Loop:}$

$\quad \Delta \leftarrow 0$

$\quad \text{Loop for each } s \in \mathcal{S}, a \in \mathcal{A}(s):$

$\quad \quad q \leftarrow Q(s, a)$

$\quad \quad Q(s,a) \leftarrow \sum_{s',r} p(s', r \mid s, a) \big[ r + \gamma Q(s', \pi(s')) \big]$

$\quad \quad \Delta \leftarrow \max(\Delta, |Q(s,a) - q|)$

$\text{until } \Delta < \theta$

3. Policy Improvement

$\text{policy-stable} \leftarrow \text{true}$

$\text{For each } s \in \mathcal{S}$:

$\quad \text{old-action} \leftarrow \pi(s)$

$\quad \pi(s) \leftarrow \argmax_a Q(s, a)$

$\quad \text{if } \pi(s) \neq \text{old-action}:$

$\quad \quad \text{policy-stable} \leftarrow \text{false}$

$\text{If policy-stable, then stop and return } Q \approx q^* \text{ and } \pi \approx \pi^* \text{; else go to 2}$

Exercise 4.6

3. Policy Improvement

We will replace the deterministic greedy update with an $\epsilon$-soft update.

Also, we will now check if the policy is stable by comparing the distributions $\pi$ and $\pi'$ rather than just the argmax action.

2. Policy Evaluation

The Bellman expectation update must use $\pi(a \mid s)$ instead of a single action.

3. Policy Improvement

We will initialize $\pi$ as an $\epsilon$-soft policy (e.g. uniform over all actions) and set $V(s) = 0$.

Exercise 4.7

Since one free car can move from location 1 to 2, the optimal policy is asymmetric: it often sends cars $1 \rightarrow 2$ and only shifts $2 \rightarrow 1$ when location 1 is short.

Moreover, a $4$ parking surcharge creates sharp boundaries around $10$ cars, so the policy actively avoids holding more than $10$ cars at either site, which produces the visible "notches" in the contour plots.

Exercise 4.8

The coin is not fair and the odds are against the gambler. As the number of flips increases, the probability of winning decreases.

When the gambler's capital allows them to reach $100$ exactly with one win (such as at $50$ or $75$), the best strategy is to bet everything - it gives the highest possible chance of winning quickly.

But when the capital is just above or below such points (such as at $51$), betting everything becomes too risky: losing would drop them too close to $0$, where recovery is unlikely. In those cases, smaller bets slightly increase the overall probability of eventually reaching the goal.

Exercise 4.9

We can see from the plots that for $p_h = 0.25$, the results are very similar to those for $p_h = 0.4$. In both cases, the odds are against the gambler, leading to large, high-risk bets only when the gambler can reach the goal exactly on a win.

In contrast, when $p_h = 0.55$, the odds are favorable. The gambler adopts smaller, safer bets, using the advantage to make steady progress toward the goal without taking unnecessary risks.

Exercise 4.10