Value iteration
If you know the transition model, repeatedly update $v(s)$ with the Bellman backup until it converges.
Initialize $v(s)$ (often zeros). Sweep over all states, setting each $v(s)$ to $\max_a[r(s,a)+\gamma v(s')]$. Repeat many times. Values propagate from rewarding states outward. Then act greedily: pick the action that leads to the best backed-up value.
Ladder again
10 states, actions up/down, reward 1 only for staying at 0 or 9, $\gamma=0.9$. After enough sweeps:
$v \approx [10, 9, 8.1, 7.29, 6.56, 6.56, 7.29, 8.1, 9, 10]$.
Notice symmetry: middle states are least valuable because you are farthest from a rewarding end. You did not need to guess the policy first — values reveal “walk toward the nearer end”.
Key takeaways
- Needs a model of transitions.
- Repeated Bellman updates.
- Then act greedily w.r.t. $v$.