CS188 MDPs and Reinforcement Learning: From Value Iteration to Q-Learning

🌏 中文版

Search assumes successors can be enumerated. Reinforcement learning must act under uncertain outcomes and delayed rewards. Lectures 9–12 establish MDPs and then RL; Project 3 implements value iteration, Q-learning, epsilon-greedy exploration, and approximate Q-learning.

Separate planning from learning

Value iteration knows transition and reward models and computes values through Bellman updates. Q-learning does not require the model in advance; it updates Q-values from (state, action, reward, nextState) experience. Both can produce a policy, but their information sources differ.

Check synchronous updates carefully: every new value in an iteration should come from the previous iteration, not from values modified earlier in the same sweep. For Q-learning, observe learning rate, discount, and exploration separately. A random epsilon-greedy action gathers information; it is not a malfunction.

From tables to features

Tabular Q-learning stores every state-action pair separately and generalizes poorly in a large Pacman state space. Approximate Q-learning expresses Q-values through features and weights so related situations share experience. First verify that an identity extractor behaves like the tabular version, then introduce meaningful features. This isolates the effect of representation while preserving the update rule.

Hand-calculate one Bellman update in a tiny Gridworld before running a single autograder case. Finally compare policies before and after exploration is disabled. Do not stop at average score; explain why the agent selects its action.

Series navigation: Previous: CSPs and multi-agent search | Next: Bayes nets and Ghostbusters

References

• CS188 textbook — MDPs
• CS188 textbook — Reinforcement Learning
• CS188 Spring 2026 Project 3