RL Basics: Value & Policy Iteration

Chapter 1: Return — Why the Future Gets Discounted

Before we can say how good a square is, we need a single number that scores an entire future. That number is the return: the total reward the robot will collect from now on. We met it in Lecture 1; here we sharpen it, because it is the thing every value is an average of.

Write the rewards the robot receives, step by step, as r at time 1, r at time 2, and so on. The naive return is just their sum. But for an infinite-horizon problem — a robot that lives forever — that sum can blow up to infinity, and "infinity vs. infinity" tells you nothing about which behavior is better. The fix is the discount factor γ (gamma), a number between 0 and 1:

Read it slowly. G_t is the return measured from time t. A reward one step away counts at full value; a reward two steps away is multiplied by γ; three steps away by γ²; and so on. The further into the future a reward sits, the more it shrinks.

Why discount at all? Two reasons, and you should hold both.

• Mathematical: with γ < 1 a bounded per-step reward gives a finite sum, even over an infinite horizon. (A geometric series 1 + γ + γ² + … converges to 1/(1−γ).) Finite means comparable; comparable means we can optimize.
• Intuitive: γ encodes "a reward now beats the same reward later" — the same reason a dollar today is worth more than a dollar next year. γ near 1 makes a patient, far-sighted robot; γ near 0 makes a greedy, myopic one that cares only about the next step.

Let's nail the recursion with a number. The corridor pays −1 per step and 0 at the dock. Starting at square A under "always go right," the rewards are −1, −1, −1, then 0 forever. With γ = 0.9:

Hold onto that −2.71. It is the exact value of square A under the always-right policy, and we will rederive it three different ways in the chapters ahead — by the Bellman recursion, by iterative policy evaluation, and by value iteration — getting −2.71 every time. When three roads lead to the same number, you know you understand it.

Chapter 2: Two Value Functions — V and Q

The return is a property of a single rolled-out future. But futures are random — the world transitions stochastically, the policy may pick actions stochastically. What we want is the expected return: the average over all the futures a given starting point could produce. That average has a name, two of them in fact, and the difference between them is one of the most useful distinctions in all of RL.

The state-value function V

The state-value function, written V^π(s), is the expected return if you start in state s and then follow policy π forever. In words: "how good is it to be in this square, assuming I'll behave according to this plan from here on?" It is a single number per state — in our corridor, one number for each of A, B, C, D.

E means expected value (the average); the subscript π reminds us the average is taken over trajectories generated by following π. The bar reads "given that we start in s." So V^π(s) is the average cost-to-go of square s under plan π.

The action-value function Q

The action-value function, written Q^π(s, a), asks a slightly richer question: "how good is it to be in state s, take the specific action a right now, and only then follow π forever after?" It scores a state paired with a first move.

Q carries strictly more information than V. From the same square you can imagine taking each possible action and see which first move pays off best — that is exactly what V cannot tell you, because V has already averaged the first action away under the policy.

The optimal versions — and why Q* is the prize

Among all policies there is a best one, π*. Its value functions get a star: V*(s) is the most return any policy can squeeze out of state s, and Q*(s, a) is the most return achievable from s if you commit to first action a. They are linked the same way as before, but now with a max instead of an average over actions:

Read that second equation carefully, because it is the payoff of the whole distinction. If you know Q*, the optimal policy is free — just take the action with the largest Q* in each state. No model of the world needed; no looking ahead. That is why so much of RL chases Q directly (you'll see it in Lecture 8, Q-learning).

Let's make V and Q concrete on the exact slide example. In the corridor with no discount and a −1 step cost, the optimal values count the steps to the dock: V*(A)=−3, V*(B)=−2, V*(C)=−1, V*(D)=0. Now compare two action-values from A: Q*(A, right) = −1 + V*(B) = −3 (one step, then optimal from B), while Q*(A, stay) = −1 + V*(A) = −4 (waste a step, end up where you started). Since −3 > −4, π*(A) = right. The numbers decide the move.

Chapter 3: The Bellman Equation, Derived

We have a recursive fact about returns (Chapter 1) and a definition of value as expected return (Chapter 2). Snap them together and you get the equation that organizes all of reinforcement learning. We'll derive it line by line — no step skipped.

Start from the definition of state-value and substitute the one-step recursion for the return:

The expected value of a sum is the sum of expected values, so we split it into "expected immediate reward" plus "γ times expected next return." Now we make the two random choices explicit. First the policy picks an action a with probability π(a|s); then the world transitions to s′ with probability p(s′|s, a). Averaging over both:

This is the Bellman expectation equation. Decode each piece:

• ∑_a π(a|s) — average over the actions the policy might take from s.
• ∑_s′ p(s′|s, a) — average over the states the world might transition to, given that action.
• r(s, a) — the immediate reward, collected now.
• γ V^π(s′) — the discounted value of wherever we land, the future folded into a single number.

The crucial feature is the V^π on both sides: the value of s is defined in terms of the values of its successors. It is the recursion "this value = this reward + discounted next value," now written out as a precise average. Because our gridworld is deterministic and the reward depends only on the state, the equation collapses to the friendly form we'll actually compute with:

where next(s) is the single square the policy sends you to. Let's check it against Chapter 1's number. Under "always right," V(C) = −1 + 0.9·V(D) = −1 + 0 = −1. Then V(B) = −1 + 0.9·V(C) = −1 − 0.9 = −1.9. Then V(A) = −1 + 0.9·V(B) = −1 + 0.9(−1.9) = −2.71. The same −2.71 as before — this time straight from the Bellman recursion.

The optimality version — replace the average with a max

The Bellman expectation equation evaluates a fixed policy. To describe the best policy we make one surgical change: instead of averaging over the policy's actions, we take the action that maximizes. This gives the Bellman optimality equation:

The principle behind the max has a name — the principle of optimality: an optimal policy, from any state it reaches, must still be optimal for the rest of the journey. There is no "I'll be sloppy now and brilliant later." Optimal behavior is optimal all the way down, which is exactly why the recursion is allowed to call itself with a max at every step.

Chapter 4: Policy Evaluation — Scoring a Fixed Plan

Here is the first concrete algorithm. Policy evaluation answers exactly one question: given a fixed policy π (which may be terrible), what is V^π(s) for every state? In words — how good is this plan, square by square?

We have two routes to the answer, and seeing both is worth it.

Route 1 — solve the linear system exactly

For a tabular MDP, the Bellman expectation equation is one linear equation per state, all coupled. Stack the values into a vector and the equation becomes a single matrix line:

Here V^π is the vector of state-values, r is the vector of rewards, and T^π is the transition matrix under the policy — entry (j, k) is the probability of going from state j to state k when you act according to π. Solve algebraically:

This is exact and beautiful, but inverting a matrix is expensive when there are many states, and it only works because the equation is linear (no max). So in practice we usually take the second route.

Route 2 — iterate the recursion until it stops moving

Treat the Bellman equation as an update rule. Start from any guess (zeros are fine), and repeatedly replace each value with the right-hand side computed from the current values:

One pass over all states is a sweep. Keep sweeping; the values march toward V^π and freeze. Chapter 5 explains why this is guaranteed. First, let's grind a full example by hand so the mechanics are concrete.

A worked policy-evaluation sweep, by hand

Corridor A·B·C·D, γ = 0.9, reward −1 per non-goal square and 0 at the dock D. The policy under evaluation is "always go right", so next(A)=B, next(B)=C, next(C)=D, and D is absorbing. We initialize every value to 0.

Let's verify the arithmetic of sweep 2, square A: V₂(A) = r(A) + γ·V₁(B) = −1 + 0.9×(−1) = −1.90. And sweep 3, square A: V₃(A) = −1 + 0.9×V₂(B) = −1 + 0.9×(−1.90) = −1 − 1.71 = −2.71. There it is a third time — the same −2.71 we got from the geometric series and from the closed-form recursion. The values stop changing after sweep 3 because the corridor is only three squares deep, so the goal's pull needs exactly three sweeps to reach A.

Now let's build the iteration in code. You'll supply the single line that is the whole Bellman update — the matrix form V ← r + γTV — and prove the result satisfies the Bellman equation to machine precision.

Chapter 5: Why It Converges — The Contraction

We have been iterating a recursion and trusting it to settle. Why should it? Why is (I − γ T^π) even invertible? The answer is a single, gorgeous idea that underwrites every dynamic-programming method in this lecture: the Bellman update is a contraction.

An operator F — a rule that takes a value vector and returns a new one — is a γ-contraction if applying it to any two vectors shrinks the gap between them by at least a factor γ:

The double bars are the max-norm — the largest absolute difference across all the entries. The statement says: whatever the biggest disagreement between two value guesses is, one Bellman update multiplies it by at most γ.

Why is the Bellman operator F^π(V) = r + γ T^π V a contraction? Take two guesses x and y. Subtract: F(x) − F(y) = γ T^π(x − y) — the rewards cancel. T^π is a stochastic matrix (its rows are probabilities that sum to 1), and averaging can never amplify the largest entry. So the new gap is at most γ times the old gap. The γ out front is the entire reason it shrinks.

"Geometric rate γ^k" is worth feeling. With γ = 0.9, every ten sweeps cut the error by roughly a factor of e (since 0.9¹⁰ ≈ 0.35); with γ = 0.99 it's far slower. The discount factor that makes the robot far-sighted is the same factor that decides how quickly our algorithms converge — a tax on patience.

And this is why (I − γ T^π) is invertible: a contraction's fixed-point equation V = r + γ T^π V has a unique solution, so the matrix can't be singular. The same single fact — contraction — guarantees the linear solve, the iterative sweep, and (with the max swapped in) value iteration too.

Chapter 6: Policy Improvement — Acting Greedily

Policy evaluation tells us how good a plan is. But we want a better plan. Here is the move that improves it, and it is almost embarrassingly simple.

Suppose we have evaluated policy π and know its action-values Q^π(s, a). Define a new policy π′ that, in each state, picks the action with the highest Q^π — it acts greedily with respect to the old policy's Q:

In words: "for one step, do the thing that looked best according to the old plan's own scoring; then revert to the old plan." It seems too cheap to work. Does it?

The intuition behind the proof: at the first step, π′ takes an action whose Q^π is at least as high as what π would have done — so the value of that first step doesn't drop. But after that step we're following π again, and the same argument applies recursively at the next state, and the next. Each step is at least as good, so the whole trajectory is at least as good. The improvements stack down the chain.

A worked improvement step, by hand

Take a deliberately bad starting policy on the corridor: π₀ = "always go left." Under always-left, square A loops on itself forever (left from A stays at A), paying −1 every step. We evaluate it (Chapter 4) and find every transient square is a trap worth V^π₀ = −10 — that's the geometric sum −1/(1 − 0.9) of paying −1 forever with γ = 0.9.

Now improve. At square C, compare the two action-values using V^π₀:

Since −1 > −10, the greedy policy flips C to right. The same comparison flips B and A to right as well, because reaching the dock (value 0) beats wandering deeper into the −10 trap. One improvement step turns the worst policy into the best one. That is the leverage greedy improvement gives you.

When does improvement stop?

Improvement keeps producing strictly better policies — until it can't. The moment greedy gives you back the same policy you started with (the argmax doesn't change anything), you have a policy that is greedy with respect to its own value. Stare at that condition and you'll see it is the Bellman optimality equation: V^π(s) = max_a Q^π(s, a) for all s. A fixed point of improvement is exactly an optimal policy.

Chapter 7: Policy Iteration — Evaluate, Improve, Repeat

We now have both halves. Policy iteration simply alternates them until the policy stops changing:

Each loop produces a policy that is provably at least as good as the last (improvement theorem), and there are only finitely many deterministic policies in a tabular MDP, so the sequence cannot improve forever — it must hit a policy that no longer changes. That fixed point is, by Chapter 6's equivalence, the optimal policy. Policy iteration is therefore guaranteed to terminate at π*, usually in remarkably few iterations.

A full policy-iteration run, by hand

On a 3-square corridor A·B·C (C = dock, γ = 0.9), start from the worst policy π₀ = "always left":

• Iteration 0. Evaluate π₀ = always-left. A loops on itself, so V^π₀(A) = V^π₀(B) = −10 (the −1-forever trap). Improve: every square's greedy action flips to right (reaching the dock beats the trap, as we computed in Chapter 6).
• Iteration 1. Evaluate the new policy π₁ = always-right. Now V(B) = −1 (one step to the dock), V(A) = −1 + 0.9·(−1) = −1.9. Improve: greedy stays right everywhere — the policy is unchanged.
• Stop. Policy stable ⇒ optimal. Final V*(A) = −1.9, V*(B) = −1, V*(C) = 0.

From the worst possible plan to the optimum in a single improvement step. Now build the loop and prove it lands on the same optimum value iteration would — and in just a handful of iterations.

Chapter 8: Value Iteration — Fold Improvement Into the Backup

Policy iteration has a hidden cost: every round runs a full policy evaluation to convergence before it improves even once. That's a lot of sweeps just to score a policy we're about to throw away. Value iteration asks: can we skip the inner loop entirely?

Yes. The insight is to apply the Bellman optimality backup directly — the one with the max baked in — instead of evaluating then improving as separate phases. One update per state, with the max folded in:

Compare it to policy evaluation's backup from Chapter 4. The only change is the max_a out front: instead of following a fixed policy's action, each sweep picks the best action on the fly. Improvement and evaluation have merged into a single line. You never store a policy during the loop — only values. When the values stop changing they equal V*, and the optimal policy falls out by one greedy read at the end.

A worked value-iteration sweep, by hand

Corridor A·B·C·D, γ = 0.9, two actions. Start all values at 0. Here is the optimality backup at each square for the first two sweeps. Recall right sends A→B, B→C, C→D; left sends A→A, B→A, C→B.

Sweep 1 (all V₀ = 0, so both actions tie at the reward):

Same for A and B — sweep 1 gives V₁ = (−1, −1, −1, 0).

Sweep 2 (now the future is non-zero, so the max starts to matter):

By sweep 3 the wavefront reaches A and it settles at −2.71 — the fourth time we've landed on that number. The full table:

Greedy read-out at the end: at C, Q(right) = −1 > Q(left) = −2.71, so π*(C) = right; the same holds at B and A. The optimal policy is "always right," exactly as policy iteration found — same answer, fewer phases. Now implement the backup and extract the policy.

Chapter 9: Connections — Where This Spine Goes Next

You now own the recursive heart of reinforcement learning. Every state has a value; that value is its reward plus the discounted value of where you land; solving that recursion — by averaging for a fixed policy, by maxing for the optimum — hands you the best behavior. Two algorithms realize it, and both are guaranteed to converge because the Bellman backup is a contraction.

The honest caveats

Everything here assumed two luxuries the rest of the course spends its time removing:

• We knew the dynamics. The backups need p(s′|s, a). When the world is unknown, you must sample it — that is the leap to Q-learning and temporal-difference learning (Lecture 8), which estimate the same backups from experience alone.
• The state space was tiny and tabular. A real robot has continuous, high-dimensional states; you can't store a value per state. The fix is function approximation — a neural network for V or Q — which leads to deep RL, policy gradients, and actor-critic.
• The max over actions was easy. With continuous actions even computing argmax_a Q(s, a) is its own optimization problem — another reason policy-based methods exist.

Where to go next on this site

This lesson is the foundation of the model-free RL strand of 16-831. Continue and deepen:

• Lecture 6 — Imitation Learning II — the previous lecture; how DAgger fights compounding error before we turn to reward-driven RL.
• Lecture 8 — Q-Learning — the next lecture; the same Bellman backups, but learned from samples without knowing the dynamics.
• Markov Decision Processes — the full MDP foundation, with its own gridworld value-iteration showcase.
• RL Algorithms — the model-free toolbox (Q-learning, SARSA, policy gradients) that grows from this skeleton.
• Q-Learning & Policy Gradients — the two families that scale these ideas to deep networks.

"The value of a state is the reward you get now, plus the discounted value of where you'll be next. Everything else is bookkeeping."