Recap: \(\pi^\star = \arg\max_a Q^\star\)

From L13, the optimal policy is one greedy step from \(V^\star\):

\(\pi^\star(s) = \arg\max_a Q^\star(s, a).\)

Two value functions: \(V^\star\) and \(Q^\star\)

Since you would just pick the best first action:

Unrolling \(Q^\star(s, a)\): reward + future value

Take action \(a\) in state \(s\). What happens?

• You collect the reward \(R(s)\).
• The environment lands you in a next state \(s'\) with probability \(P(s' \mid s, a)\).
• From \(s'\) onward you act optimally — worth \(V^\star(s')\).

One fix remaining: future reward should be discounted.

Discounting the future

A reward received one step later is worth less than a reward now, so we discount the downstream value \(V^\star(s')\) by \(\gamma \in [0, 1)\):

Why discount? Future reward is less certain, and \(\gamma < 1\) keeps the long-run sum finite (and the upcoming iteration convergent).

Putting it together: the Bellman equation

The two connections between \(V^\star\) and \(Q^\star\):

Substitute ② into ①:

\(|S|\) coupled equations; \(V^\star\) is their unique solution. Turn it into an update rule → value iteration.

Apply Bellman to \(V^\star(s_{11})\)

Q1. Can we solve this system of Bellman equations in polynomial time?

The value iteration algorithm

Treat the Bellman equation as an update rule. Let \(V_i(s)\) be the \(i^{\text{th}}\) estimate.

Guarantee: \(V_i \to V^\star\) as \(i \to \infty\).

• Synchronous: keep \(V_i\) frozen while computing all of \(V_{i+1}\).
• Asynchronous: update entries in place, in any order. Often converges faster.

Apply VI to the grid

Setup: \(\gamma = 1\), \(R(s) = -0.04\) for non-goal states. Terminals: \(V(s_{24}) = -1, V(s_{34}) = +1\). Init \(V_0(s) = 0\) for all non-terminals.

After one Bellman update, only the cells adjacent to a goal will see something different from \(-0.04\).

One iteration: \(V_1(s_{23})\)

\(s_{23}\) is just left of the \(-1\) terminal. Update from \(V_0\) (all \(0\) except the \(\pm1\) terminals), \(\gamma=1\); each action is \(0.8\) intended + \(0.1\) each side (a wall bump stays put).

One iteration: \(V_1(s_{33})\)

\(s_{33}\) sits just left of the \(+1\) terminal. Same update from \(V_0\), \(\gamma = 1\):

The \(+1\) reward has "leaked" one cell up; values propagate one cell per iteration.

Two iterations: \(V_2(s)\)

Apply Bellman again, using \(V_1\) as input. For each cell we show its best action — the one \(\max_a\) selects. Three cells worth a closer look:

Values propagate one cell per iteration. After enough sweeps they converge to the L13 \(V^\star\).

Policy iteration

Insight: if one action is clearly better, you don't need precise utility values — just enough to rank actions.

Terminates in finitely many steps: there are finitely many policies and each iteration strictly improves.

Policy evaluation vs Bellman: the max disappears

In PE the action is fixed by \(\pi\), so the system becomes linear in \(V\):

Policy improvement reintroduces the \(\arg\max\):  \(\pi_{i+1}(s) = \arg\max_a \sum_{s'} P(s' \mid s, a)\, V^{\pi_i}(s')\).

How do we perform policy evaluation?

Two ways to solve the linear system \(V^\pi(s) = R(s) + \gamma \sum_{s'} P(s' \mid s, \pi(s))\, V^\pi(s')\):

In practice, a small \(m\) is usually enough — PI converges in far fewer outer iterations than VI.

Policy iteration on the grid: \(\pi_0 = \) all-right

Same 3×4 grid (\(\gamma = 1\), \(R = -0.04\)). Start from a deliberately mediocre policy — every state goes right.

Round 1: evaluate \(\pi_0\), then improve

\(\pi_0\) drove the top half straight into the \(-1\) (values \(\approx -1.4\)). Greedy improvement turns those states down/around toward the \(+1\).

Round 2: evaluate \(\pi_1\), then improve

Values jump up; the top row now steers away from the \(-1\). Only the corner near \(-1\) still needs adjusting.

Convergence: PI meets VI

A couple more rounds settle the top row, and the policy stops changing — that is \(\pi^\star\).

Exactly the \(V^\star\) and optimal policy from L13 — value iteration and policy iteration agree.