Lecture 2 of CS234 Winter 2026 assumes the world model is known and asks how to compute the best policy. An MDP plus a policy is an MRP, so a policy can be evaluated by iterating a Bellman backup. Policy iteration alternates evaluation and improvement, and the slides prove each round is no worse than the last, so it stops within |A|^|S| rounds. Value iteration takes another route: apply the Bellman optimality operator over and over. For γ < 1 that operator is a contraction, so value iteration always converges. The lecture ends with finite horizons, where the best policy usually depends on how many steps remain.
HW6 Problem 2 (15 pts) hands you a 4×5 Gridworld where moves can slip and rewards arrive only when you leave a cell. You write one step each of policy evaluation, policy iteration, and value iteration in the notebook, watch how the discount factor γ reshapes the policy, and finally ask whether this is a sensible model of the robot task at all. The rules of the world are fully known, so this is planning, not learning yet.
Lecture 21 formulates stochastic sequential decisions as an MDP with known dynamics, defines value and Q-values through Bellman backups, and solves for an optimal policy with value or policy iteration.
Dynamic programming starts by defining subproblems, derives a recurrence from optimal substructure, and evaluates states in dependency order; Bellman–Ford layers by edge count, while Floyd–Warshall layers by allowed intermediate vertices.
Lecture 13 turns dynamic programming into five steps: choose a state, derive transitions, fill the table, reconstruct a solution, and then improve the implementation. LCS takes O(mn), both knapsack variants take O(nW) pseudo-polynomial time, and maximum-weight independent set on a tree takes O(|V|).