Harvard CS181 HW6 (Part 3): Policy Iteration and Value Iteration for MDPs

🌏 中文版

⚠️ Version and access: Based on CS1810 Spring 2026 HW6 (hw6_release.tex/pdf/ipynb, img_input/gridworld.png, due 2026-05-01), the Section 10 notes, and the 2026 Lecture 21 MDP slides, all opened on 2026-09-29. The slide link comes from a topic cell in the official schedule (visible only in the xlsx export). The course as a whole is A3, but there are no recordings from this term and no homework solutions. This post gives no answers and does not publish convergence counts or final policies.

This is part 13 of the Harvard CS181 weekly guide. The previous part, HW6 (Part 2), dealt with HMMs, where the state evolves on its own and you only watch. Here the agent starts making decisions.

Where it sits in the term

Per the 2026 official schedule, Week 12 covered Single-Agent MDPs on Tuesday (April 14) and Reinforcement Learning I on Thursday; Section 10, "MDPs and Reinforcement Learning", was the Tuesday of Week 13. HW6 was released April 17 and due May 1.

The Lecture 21 slides state the pivot from the previous lecture in one line: an HMM's state evolves passively through p(z_{t+1} | z_t), while an MDP's state evolves through p(s_{t+1} | s_t, a_t), which depends on the action you pick, and you want to maximize reward. The slides split the next two weeks into three parts: MDPs as "planning with a known model", RL 1 as "learning from unknown environments", and RL 2 as "scaling up with deep RL". Problem 2 belongs to the first.

The setting: a robot collecting two parts

The problem tells a story: you want a robot to collect two parts in an environment and bring them to a goal, while avoiding areas where it would wear down the floor. You decide to model the environment as the Gridworld below, where each cell shows its reward (from gridworld.png):

The middle column is a wall of negative rewards, and the positive rewards sit on both sides: a small +4 near START, with +20 and +50 across the wall.

Two special rules

Moves can slip. The actions are N, S, E, W. A move succeeds with probability 0.8 and slips to either side with probability 0.1 each, but never backwards. Bumping into the edge leaves you in place. Edge cells have no "slip off the map": the problem's example is that moving north from START succeeds with probability 0.9 and slips east with 0.1.

Rewards arrive when you leave a cell. Entering a cell gives no reward; you receive it after taking an action in that cell. The problem's example: moving east four times from START with no slipping yields rewards +0, +0, −50, +0, and you are now standing on the +50 cell. Whatever you do next, the next reward is +50.

Both rules are already built into the notebook helpers, so you never compute transition probabilities yourself. The problem says to use get_reward and get_transition_prob and forbids outside code.

Mapping the MDP tuple onto the notebook

Section 10 defines an MDP as (S, A, P, R, γ). In hw6_release.ipynb these are:

The policy pi and value function V are both 1-D arrays of length 20. The policy is deterministic: one action per state.

How policy iteration and value iteration differ

The two algorithms from Lecture 21 and Section 10:

flowchart LR
  subgraph PI["Policy iteration"]
    direction TB
    P0["Initial policy π"] --> P1["Evaluate: compute V^π"]
    P1 --> P2["Improve: act greedily on V^π"]
    P2 -->|policy still changing| P1
  end
  subgraph VI["Value iteration"]
    direction TB
    V0["V₀ = 0"] --> V1["Every cell: take the max over actions of (immediate reward + γ × expected next value)"]
    V1 -->|not converged| V1
  end

• Policy iteration computes the current policy's value to convergence in every round, then changes the policy based on it. Section 10's Bellman equation says how: V^π(s) = R(s) + γ Σ_{s'} p(s' | s, π(s)) V^π(s') (reward written as state-only to match the homework).
• Value iteration doesn't wait for evaluation to converge; it takes the max over actions at every step. The slides describe it as merging evaluation and improvement "into one continuous step".

You write three functions:

The outer loop is the provided learn_strategy, which calls your one-step updates repeatedly and stops when the largest change in V drops below ct.

Parts 3–5: thinking prompts

The second half of the problem stops asking for new algorithms and asks what you see and why:

• Part 3: plot the policy for each γ ∈ {0.6, 0.7, 0.8, 0.9} and describe the differences in a paragraph, with explanations. Consider: there is a small positive reward near START, the big positive rewards are across a wall of negative ones, and γ sets how much future reward is worth.
• Part 4: suppose the game ends on any positive-reward cell (you move to a zero-reward state you can't leave). How should the optimal policy change with γ? The problem wants intuition, not numbers.
• Part 5: we built a model, solved it, and then used the policy on a real robot. What's the value of that approach compared with running RL on the robot directly? What are its limitations (some of which also apply to RL)?

Part 5 rewards a second look at the story. The robot's task is "collect two parts, then deliver them", but the Gridworld state is only a location. If the state doesn't record whether the parts have been collected, can the model still express the original task? Lecture 21 raises the limitation when it discusses the Markov property: if states or actions from many steps ago affect later transitions and the state doesn't record them, acting optimally requires a policy that conditions on the whole history.

Common sticking points

• Mismatched filename: the problem text tells you to edit homework6.ipynb, but the file in the repo is hw6_release.ipynb.
• Two tolerances: theta is the inner tolerance inside policy_evaluation; ct is the outer convergence tolerance in learn_strategy. Parts 1(d) and 2(c) have you vary ct (0.01, 0.001, 0.0001) and watch the iteration count.
• The initial policy is all zeros: learn_strategy initializes pi with np.zeros, meaning every cell starts by going north.
• One step only: update_policy_iteration and update_value_iteration each perform a single update; don't write the outer loop yourself.
• Leave the plotting code alone: parts 1(c) and 2(b) want the first four iterations' plots on one page, and the problem says not to modify the plotting code.

Further reading

Posts on this site that approach the same ideas from another angle; they don't replace this one:

• CS221 Lecture 7: MDPs I: Putting Uncertainty into State Transitions
• CS188 MDPs and Reinforcement Learning: From Value Iteration to Q-Learning
• CMU 07-280 Lecture 21: How Bellman Equations Solve Markov Decision Processes

Next

This problem assumes you have get_transition_prob. The next part, HW6 (Part 4): Q-learning Swingy Monkey and Embedded EthiCS, removes that assumption: the agent doesn't know the rules and must learn by trial and error.

References

• CS1810 Spring 2026 HW6 problem set (hw6_release.tex)
• CS1810 Spring 2026 HW6 notebook (hw6_release.ipynb)
• HW6 Gridworld figure (img_input/gridworld.png)
• CS1810 2026 official schedule (Google Sheet)
• CS1810 2026 Lecture 21: Markov Decision Processes slides
• Section 10: Markov Decision Processes and Reinforcement Learning (solutions)
• CS181 2024 Lecture 21 scribe notes (policy iteration, value iteration)
• Sutton & Barto, 2018. Reinforcement Learning: An Introduction (2nd ed.) (listed on the course Resources page)