MDP Numerical Examples

Value Iteration and Policy Iteration

Part 1: Value Iteration

The Question

Consider a simple linear corridor MDP with 4 states: S1, S2, S3, S4 laid out in a line.

S1 -- S2 -- S3 -- S4 (terminal, goal)

• Actions available: {Right, Left}
• Transitions (deterministic):
  • From S1: Right → S2, Left → S1 (wall, stays put)
  • From S2: Right → S3, Left → S1
  • From S3: Right → S4 (terminal), Left → S2
  • S4 is terminal — once reached, the game ends, no further actions
• Rewards:
  • Any move that lands on S4: reward = +10
  • Any other move (including bumping into a wall): reward = −1 (a living cost)
• Discount factor: γ = 0.9
• States to solve for: S1, S2, S3 (S4 is terminal, always V(S4) = 0)

Find V*(S1), V*(S2), V*(S3) and the optimal policy π*, using value iteration.

---

The Steps (Method)

1. Initialize V₀(s) = 0 for every non-terminal state. V(S4) = 0 always, since it's terminal.
2. For each iteration k, and for every state s, compute the Bellman update: $$V{k+1}(s) = \max{a} \Big[R(s,a,s') + \gamma \, V_k(s')\Big]$$ (transitions are deterministic here, so no summation over multiple s′ is needed — see earlier note on why the general formula collapses in this case)
3. Do this for every state, using the previous iteration's values — don't use values you've already updated in the same sweep.
4. Repeat until the values stop changing between sweeps (convergence).
5. Once converged, extract the policy via one-step lookahead: pick whichever action gives the max at each state.

---

The Solution

Iteration 0 (initialization):

State	V₀
S1	0
S2	0
S3	0

Iteration 1 — using V₀ values:

• V₁(S3): Right → S4: reward 10, plus γ·V₀(S4) = 0 → total = 10. Left → S2: reward −1, plus γ·V₀(S2) = 0 → total = −1. Max = 10 (action: Right)
• V₁(S2): Right → S3: −1 + 0.9(0) = −1. Left → S1: −1 + 0.9(0) = −1. Max = −1 (tie)
• V₁(S1): Right → S2: −1 + 0.9(0) = −1. Left → S1: −1 + 0.9(0) = −1. Max = −1 (tie)

State	V₁
S1	−1
S2	−1
S3	10

Iteration 2 — using V₁ values:

• V₂(S3): Right → S4: 10 (unchanged, always terminal). Left → S2: −1 + 0.9(−1) = −1 − 0.9 = −1.9. Max = 10
• V₂(S2): Right → S3: −1 + 0.9(10) = −1 + 9 = 8. Left → S1: −1 + 0.9(−1) = −1.9. Max = 8 (action: Right)
• V₂(S1): Right → S2: −1 + 0.9(−1) = −1.9. Left → S1: −1 + 0.9(−1) = −1.9. Max = −1.9 (tie)

State	V₂
S1	−1.9
S2	8
S3	10

Iteration 3 — using V₂ values:

• V₃(S3): Right → S4: 10. Left → S2: −1 + 0.9(8) = −1 + 7.2 = 6.2. Max = 10
• V₃(S2): Right → S3: −1 + 0.9(10) = 8. Left → S1: −1 + 0.9(−1.9) = −1 − 1.71 = −2.71. Max = 8 (Right)
• V₃(S1): Right → S2: −1 + 0.9(8) = −1 + 7.2 = 6.2. Left → S1: −1 + 0.9(−1.9) = −2.71. Max = 6.2 (Right)

State	V₃
S1	6.2
S2	8
S3	10

Iteration 4 — using V₃ values (checking for convergence):

• V₄(S3): Right → S4: 10. Left → S2: −1 + 0.9(8) = 6.2. Max = 10 ✓ same as V₃
• V₄(S2): Right → S3: −1 + 0.9(10) = 8. Left → S1: −1 + 0.9(6.2) = −1 + 5.58 = 4.58. Max = 8 ✓ same as V₃
• V₄(S1): Right → S2: −1 + 0.9(8) = 6.2. Left → S1: −1 + 0.9(6.2) = 4.58. Max = 6.2 ✓ same as V₃

No change from V₃ to V₄ → converged.

Final Answer (Value Iteration)

State	V*(s)	π*(s)
S1	6.2	Right
S2	8	Right
S3	10	Right

Optimal policy: always move Right — makes sense, since Right is the only direction that ever makes progress toward the +10 reward at S4.

---

Part 2: Policy Iteration

The Question

Same MDP as above (states S1–S3, terminal S4, γ = 0.9, rewards as before).

Starting from a deliberately bad initial policy — π₀(s) = Left for every state — use policy iteration to find π*. Show every round of policy evaluation and policy improvement.

---

The Steps (Method)

1. Start with any policy π₀ (here: Left everywhere — intentionally suboptimal, to show the algorithm correct itself).
2. Policy evaluation: with the policy fixed, solve for $V^\pi(s)$ exactly using its (deterministic, no-max) Bellman equation: $$V^\pi(s) = R(s,\pi(s),s') + \gamma \, V^\pi(s')$$ Since the action is fixed, this is a system of linear equations — solve it directly.
3. Policy improvement: using the just-computed $V^\pi$, compute $Q^\pi(s,a)$ for every action at every state (not just the one π currently picks), and set the new policy to whichever action maximizes it: $$\pi'(s) = \arg\max_a \Big[R(s,a,s') + \gamma V^\pi(s')\Big]$$
4. If $\pi' \neq \pi$, repeat from step 2 using the new policy. If $\pi' = \pi$ (no change), stop — you've found π*.

---

The Solution

Round 1

Policy π₀: S1 → Left, S2 → Left, S3 → Left

Step A — Policy Evaluation (solve for V^π0 exactly):

Write out the equations using π₀'s fixed actions: $$V(S1) = -1 + 0.9\,V(S1) \quad \text{(Left at S1 → stays at S1)}$$ $$V(S2) = -1 + 0.9\,V(S1) \quad \text{(Left at S2 → S1)}$$ $$V(S3) = -1 + 0.9\,V(S2) \quad \text{(Left at S3 → S2)}$$

Solve equation 1 first, since it only involves V(S1): $$V(S1) - 0.9\,V(S1) = -1 \;\Rightarrow\; 0.1\,V(S1) = -1 \;\Rightarrow\; V(S1) = -10$$

Substitute into equation 2: $$V(S2) = -1 + 0.9(-10) = -1 - 9 = -10$$

Substitute into equation 3: $$V(S3) = -1 + 0.9(-10) = -10$$

V^π0 = (S1: −10, S2: −10, S3: −10)

Step B — Policy Improvement (check every action at every state, using V^π0):

• At S1: Q(S1,Right) = −1 + 0.9·V(S2) = −1 + 0.9(−10) = −10. Q(S1,Left) = −1 + 0.9·V(S1) = −10. Tie → keep Left.
• At S2: Q(S2,Right) = −1 + 0.9·V(S3) = −1 + 0.9(−10) = −10. Q(S2,Left) = −1 + 0.9·V(S1) = −10. Tie → keep Left.
• At S3: Q(S3,Right) = 10 + 0.9·V(S4) = 10 + 0.9(0) = 10 (remember: reaching S4 always gives reward 10, and V(S4)=0 since it's terminal). Q(S3,Left) = −1 + 0.9·V(S2) = −1 + 0.9(−10) = −10. Right is clearly better → change to Right.

New policy π₁: S1 → Left, S2 → Left, S3 → Right (changed)

Since the policy changed, we must repeat.

---

Round 2

Policy π₁: S1 → Left, S2 → Left, S3 → Right

Step A — Policy Evaluation:

$$V(S1) = -1 + 0.9\,V(S1) \quad \text{(Left, unchanged from before)}$$ $$V(S2) = -1 + 0.9\,V(S1) \quad \text{(Left → S1, unchanged)}$$ $$V(S3) = 10 + 0.9\,V(S4) = 10 \quad \text{(Right → terminal S4)}$$

From equation 1 (same as Round 1, since S1's action didn't change): $V(S1) = -10$

From equation 2: $V(S2) = -1 + 0.9(-10) = -10$

From equation 3: $V(S3) = 10$

V^π1 = (S1: −10, S2: −10, S3: 10)

Step B — Policy Improvement:

• At S1: Q(S1,Right) = −1 + 0.9·V(S2) = −1 + 0.9(−10) = −10. Q(S1,Left) = −1 + 0.9·V(S1) = −10. Tie → keep Left.
• At S2: Q(S2,Right) = −1 + 0.9·V(S3) = −1 + 0.9(10) = −1 + 9 = 8. Q(S2,Left) = −1 + 0.9·V(S1) = −1 + 0.9(−10) = −10. Right is much better → change to Right.
• At S3: Q(S3,Right) = 10 (still best). Q(S3,Left) = −1 + 0.9·V(S2) = −1 + 0.9(−10) = −10. Keep Right.

New policy π₂: S1 → Left, S2 → Right (changed), S3 → Right

Policy changed again — repeat.

---

Round 3

Policy π₂: S1 → Left, S2 → Right, S3 → Right

Step A — Policy Evaluation:

$$V(S1) = -1 + 0.9\,V(S1) \quad \text{(Left, still unchanged)}$$ $$V(S2) = -1 + 0.9\,V(S3) \quad \text{(Right → S3, now changed)}$$ $$V(S3) = 10 \quad \text{(Right → terminal, unchanged)}$$

From equation 1: $V(S1) = -10$ (same as always, since S1 still self-loops on Left)

From equation 3: $V(S3) = 10$

Substitute into equation 2: $V(S2) = -1 + 0.9(10) = -1 + 9 = 8$

V^π2 = (S1: −10, S2: 8, S3: 10)

Step B — Policy Improvement:

• At S1: Q(S1,Right) = −1 + 0.9·V(S2) = −1 + 0.9(8) = −1 + 7.2 = 6.2. Q(S1,Left) = −1 + 0.9·V(S1) = −1 + 0.9(−10) = −10. Right is dramatically better → change to Right.
• At S2: Q(S2,Right) = −1 + 0.9·V(S3) = −1 + 9 = 8 (matches current — best). Keep Right.
• At S3: Q(S3,Right) = 10 (still best). Keep Right.

New policy π₃: S1 → Right (changed), S2 → Right, S3 → Right

Policy changed once more — repeat.

---

Round 4

Policy π₃: S1 → Right, S2 → Right, S3 → Right

Step A — Policy Evaluation:

$$V(S1) = -1 + 0.9\,V(S2)$$ $$V(S2) = -1 + 0.9\,V(S3)$$ $$V(S3) = 10$$

From equation 3: $V(S3) = 10$

Substitute into equation 2: $V(S2) = -1 + 0.9(10) = 8$

Substitute into equation 1: $V(S1) = -1 + 0.9(8) = -1 + 7.2 = 6.2$

V^π3 = (S1: 6.2, S2: 8, S3: 10)

Step B — Policy Improvement (final check):

• At S1: Q(S1,Right) = −1 + 0.9·V(S2) = −1 + 7.2 = 6.2 (matches current). Q(S1,Left) = −1 + 0.9·V(S1) = −1 + 0.9(6.2) = −1 + 5.58 = 4.58. Right still best → no change.
• At S2: Q(S2,Right) = −1 + 0.9·V(S3) = 8 (matches current). Q(S2,Left) = −1 + 0.9·V(S1) = −1 + 0.9(6.2) = 4.58. Right still best → no change.
• At S3: Q(S3,Right) = 10 (matches current, still best) → no change.

Policy did not change (π₄ = π₃) → converged.

Final Answer (Policy Iteration)

State	V*(s)	π*(s)
S1	6.2	Right
S2	8	Right
S3	10	Right

---

Comparing the Two Results

State	Value Iteration V*	Policy Iteration V*	Match?
S1	6.2	6.2	✓
S2	8	8	✓
S3	10	10	✓

Both algorithms converge to exactly the same optimal values and the same optimal policy (Right everywhere) — as they must, since both are solving for the same underlying V* and π*. The difference was purely in how many steps it took and what work was done per step:

• Value iteration took 4 sweeps, each sweep touching every state with one cheap Bellman update.
• Policy iteration took 4 rounds, but each round required exactly solving a small system of linear equations (policy evaluation) — more expensive per round, but the policy itself locked in its final answer (Right at S3) after just the very first round, and never had to reconsider it again.