Skip to content
Tutorials Center
My learning

Topics

Lesson 12 of 37 ยท Dynamic Programming

Value Iteration and the Gambler's Problem

Learn value iteration, the Bellman optimality backup as an update rule: truncated policy evaluation, convergence tests, policy extraction and the classic gambler's problem in Python.

Policy iteration does a full evaluation before every improvement. That is wasteful: early on, the policy is bad and its exact value is not worth computing. Value iteration takes the idea to the extreme: do one sweep of evaluation and improvement combined. The resulting update is simply the Bellman optimality equation turned into an assignment.

The update

v_{k+1}(s) = max over a of sum over s', r of p(s', r | s, a) * [ r + gamma * v_k(s') ]

Compare with policy evaluation: the average over the policy's actions has been replaced by a max over actions. Each sweep therefore improves the estimate of v*, and for gamma < 1 (or an episodic task that always terminates) the iteration converges to it. When the largest change in a sweep is below theta, read off a deterministic policy:

pi(s) = argmax over a of sum over s', r of p(s', r | s, a) * [ r + gamma * v(s') ]

Think of value iteration as policy iteration with a policy evaluation truncated to a single sweep. In between lie "modified policy iteration" methods that do a few evaluation sweeps per improvement.

flowchart LR
    A["v_0 = zeros"] --> B["sweep: v(s) = max over a of lookahead"]
    B --> C{"delta below theta?"}
    C -->|"no"| B
    C -->|"yes"| D["extract greedy policy from v"]

Value iteration on the slippery grid

We reuse the slippery 4x4 grid (a move goes sideways with probability 0.2). The code below runs value iteration, extracts the policy, and compares it with the one policy iteration found earlier, then counts how many sweeps it needed.

Python Value iteration on a slippery grid

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The values and policy match what policy iteration produced for the same problem, but with no inner evaluation loop. For this tiny grid the cost difference is small; for large problems truncating the evaluation is a big saving.

Convergence speed

For gamma < 1, the error of value iteration shrinks by a factor of at most gamma per sweep, so the number of sweeps needed grows like log(1/theta) / log(1/gamma). With gamma = 0.99 you need about ten times more sweeps than with gamma = 0.9. A policy often becomes optimal long before the values are accurate, so stopping early with a loose theta is common practice.

The gambler's problem

A gambler bets on coin flips. The coin lands heads with probability p_h = 0.4 (unfavourable). On each flip the gambler stakes some whole number of dollars from the current capital. Heads: win the stake. Tails: lose it. The game ends at 0 dollars (loss) or 100 dollars (win). The reward is +1 on reaching 100 and 0 otherwise, gamma = 1. So v(s) is the probability of winning from capital s, and the optimal policy picks the stake that maximizes it.

Python Value iteration for the gambler's problem

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The optimal policy has a surprising, jagged shape: at 50 dollars it stakes everything (50), at 25 it stakes 25, at 75 it stakes 25, while at 51 it stakes just 1. The reason: every extra flip gives the unfair coin more time to grind you down, so you want to reach the goal in as few flips as possible and aim at the round numbers 25, 50 and 75, where one lucky flip or two finish the job. (Several different stakes may tie at some capitals; we print the smallest.) Notice also that this is a case where a different gamma would not make sense: the only reward is on winning.

Value iteration versus policy iteration

Policy iteration Value iteration
Per iteration Full evaluation + improvement One combined sweep
Number of iterations Few Many
Intermediate policies Explicit Implicit in v
Memory Policy + values Values only

Neither dominates. In practice, hybrids (a few evaluation sweeps between improvements) work best.

Common mistakes

  • Stopping on a loose theta and treating the values as exact. Policy extraction is usually fine; precise values may not be.
  • Forgetting that terminal states must keep their value (0, or 1 in the gambler's problem).
  • Taking the max over actions before summing over outcomes. The max is outside the expectation.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. How does the value iteration update differ from iterative policy evaluation?

    The backup is the Bellman optimality equation, so the policy average becomes a max.
  2. 2. Value iteration can be seen as policy iteration with...

    One sweep of evaluation merged with greedy improvement is exactly value iteration.
  3. 3. In the gambler's problem, what does v(s) mean?

    The only reward is 1 for reaching the goal with gamma = 1, so the value is the winning probability.
  4. 4. Roughly how do the sweeps needed grow as gamma approaches 1?

    Contraction factor gamma means log(1/theta)/log(1/gamma) sweeps, which rises sharply near 1.

Summary

  • Value iteration repeatedly applies v(s) = max over a of lookahead, converging to v*.
  • Extract the policy afterwards with a final greedy step.
  • It equals policy iteration with a one-sweep evaluation; hybrids with a few sweeps are common.
  • The gambler's problem shows that optimal policies can be strikingly irregular.
  • Convergence slows as gamma approaches 1.

Next: Asynchronous DP and Generalized Policy Iteration