Deep Reinforcement Learning

Dynamic Programming — Value Iteration, Policy Iteration, and Q-Learning

📅 Published: 2026-07-21

🎓 Level: postgraduate

👥 Audience: Postgraduate students in Deep Reinforcement Learning

Prerequisite Knowledge

This lecture builds on the following concepts from earlier lectures. If any feel unfamiliar, review the linked notes before proceeding.

Previously Covered in This Subject

Markov Decision Processes — covered in Lecture 4 (states, actions, transitions, rewards, discount factor, policy, value functions)
Bellman Equations — covered in Lecture 5 (Bellman expectation equation, Bellman optimality equation, value iteration basics)
Policy and Value Functions — covered in Lecture 5 (state-value V(s), action-value Q(s,a), deterministic vs stochastic policies)
Model-Based vs Model-Free RL — covered in Lecture 2 (distinction between planning with a model and learning from experience)

# Dynamic Programming — Value Iteration, Policy Iteration, and Q-Learning

6.1 Review: MDP and Bellman Equations

6.1.1 MDP Framework and Bellman Equations

Hook: How do you formalize the problem of an agent making sequential decisions under uncertainty? The answer is the Markov Decision Process (MDP) — the mathematical language that lets us reason about "what should I do next?" when my actions have consequences that unfold over time.

A Markov Decision Process (MDP) is the formal framework for stating a Reinforcement Learning problem. The word "Markov" refers to the Markov property: the future depends only on the current state, not on how you got there. Think of it like a board game where only your current position matters — your history of moves is irrelevant to what happens next.

Intuition: An MDP is like a decision-making recipe. The states are the possible situations you could be in. The actions are the choices available to you. The transition function (model dynamics) tells you the probability of moving from one state to another given an action and the reward you receive. The reward function tells you the immediate payoff. The discount factor

γ

determines how much you value future rewards versus immediate ones.

An MDP consists of five components:

S — a finite set of states (the possible situations)
A — a finite set of actions (the possible decisions)
$P (s^{'} ∣ s, a)$ — the transition function: probability of reaching state s' from state s by taking action a
$R (s, a, s^{'})$ — the reward function: immediate reward received when transitioning from s to s' via action a
$γ$ (gamma) — the discount factor: a scalar in [0,1) that controls how much the agent values future rewards relative to immediate ones

The agent follows a policy $π$ — a rule that says what action to take (or with what probability) in each state. A deterministic policy is simply $π (s) = a$ (a fixed action for each state). A stochastic policy specifies probabilities $π (a ∣ s)$ for each action in each state.

We evaluate a policy using a value function $V^{π} (s)$ , which tells us how good it is to be in state s if we follow policy $π$ from then on. The value function satisfies the Bellman expected update equation.

Bellman Expected Update Equation:

The Bellman expected update says: the value of a state under policy $π$ equals the expected immediate reward plus the discounted value of the next state, where the expectation is taken over the actions chosen by $π$ and the transition probabilities.

$V^{π} (s) = a \sum π (a ∣ s) s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{π} (s^{'})]$

Symbol breakdown:

$V^{π} (s)$ — value of state s under policy $π$ (how good it is to be in s following $π$ )
$π (a ∣ s)$ — probability of taking action a in state s under policy $π$
$P (s^{'} ∣ s, a)$ — probability of transitioning to state s' from s via action a
$R (s, a, s^{'})$ — immediate reward for the transition s → s' via action a
$γ$ — discount factor (how much we value future rewards)
$V^{π} (s^{'})$ — value of the next state s' under the same policy $π$

Why it matters: This equation decomposes the value of a state into two parts: (1) the expected immediate reward, and (2) the discounted expected value of wherever you end up next. It is a recursive relationship — the value of s depends on the values of successor states.

Professor's verbal description: "This part says what's the probability of taking an action as per the policy? And the second part says what is the value of that action? And you keep repeating it."

Analogy: Think of evaluating a job position. The value of being a CXO (Chief Experience Officer) is not fixed — it depends on the person occupying it and their behavior (policy). A brilliant person in that role extracts enormous value; a poor performer makes nothing of it. Similarly, the value of a state depends critically on the policy being followed.

The Bellman optimality equation replaces the policy-weighted expectation with a max over actions:

Bellman Optimality Equation:

$V^{*} (s) = a max s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{*} (s^{'})]$

The key difference from Bellman expected update:

In Bellman expected update: you see $\sum_{a} π (a ∣ s)$ weighting each action — averaging over what the policy tells you to do
In Bellman optimality: you see $max_{a}$ — you pick the single best action rather than averaging over the policy's choices

In Bellman optimality there is no policy weighting; you look at all actions and choose the one giving the maximum value. That value becomes the value of the state.

Professor's verbal description: "In the Bellman optimality expression, instead of the sigma weighted update, you would actually see a max. The optimal policy is about picking an action that takes you to the best state, instead of doing expectation."

Worked Example: Comparing Bellman Expected Update vs Bellman Optimality

Consider a simple MDP with 2 states (S₁, S₂) and 2 actions (left, right). From S₁:

Action "left" leads to S₁ with probability 1, reward = 0
Action "right" leads to S₂ with probability 1, reward = +1

Policy $π$ gives: $π (left ∣ S_{1})$ = 0.7, $π (right ∣ S_{1})$ = 0.3

Bellman expected update (with

γ = 0.9

, assuming

V (S_{2})

= 5):

$V^{π} (S_{1}) = π (left ∣ S_{1}) [R (S_{1}, left, S_{1}) + γ V^{π} (S_{1})] + π (right ∣ S_{1}) [R (S_{1}, right, S_{2}) + γ V^{π} (S_{2})]$

$V^{π} (S_{1}) = 0.7 \times [0 + 0.9 V^{π} (S_{1})] + 0.3 \times [1 + 0.9 \times 5] = 0.63 V^{π} (S_{1}) + 1.65$

Solving: $V (S_{1}) = \frac{1.65}{0.37} \approx 4.46$

Bellman optimality (choosing the best action):

$V^{*} (S_{1}) = max {1.0 \times [0 + 0.9 V^{*} (S_{1})], 1.0 \times [1 + 0.9 \times 5]} = max {0.9 V^{*} (S_{1}), 5.5}$

Since 5.5 > 0.9 $V (S_{1})$ for reasonable values, the optimal action is "right" and $V^{*} (S_{1}) = 5.5$ .

Sense-check: Under the policy, the agent goes right only 30% of the time, so the value is lower. Under optimality, the agent always goes right and gets the full value.

Q(s,a) (the optimal action-value function) was mentioned as an analogous quantity that can be understood if you understand

V^{*}

, but the professor deferred its detailed discussion to Section 6.12. Backup diagrams. The backup diagram for Bellman optimality uses a max node: you take each action branch, compute the value of each path, and take the max. This is in contrast to the expected-update backup diagram which uses a chance node averaging over actions per

π

Scope: The Bellman equations assume:

A finite MDP (finite states and actions)
The Markov property: the future depends only on the current state, not the history
The discount factor $γ \in [0, 1)$ ensures infinite sums converge
For the Bellman expected update, a fixed policy $π$ must be specified
For the Bellman optimality equation, we are seeking the best possible policy

When it breaks: If the state space is continuous or infinite, exact solutions become intractable. If the Markov property fails (the system has memory), the MDP formulation is insufficient — you would need a POMDP or state-augmentation.

Pitfalls:

Confusing $V^{π}$ with $V^{*}$ : $V^{π}$ is the value under a specific policy $π$ ; $V^{*}$ is the value under the best possible policy. They are equal only when $π$ is already optimal.
Forgetting the discount factor: Without $γ$ , the total reward can be infinite. The discount factor makes the sum finite and models the idea that future rewards are worth less than immediate ones.
Confusing the backup diagrams: The expected-update diagram averages over actions per $π$ (chance node); the optimality diagram takes the max over actions (max node). Mixing them up leads to wrong computations.

Recap: An MDP formalizes sequential decision-making with states, actions, transitions, rewards, and discount. The Bellman expected update evaluates a given policy; the Bellman optimality equation finds the best policy. The only difference is a weighted average vs a max over actions. This distinction is the foundation for everything that follows in this lecture.

Bridge: Now that we have the Bellman optimality equation, the natural question is: how do we actually compute

V^{*}

? The answer is value iteration — the topic of the next section.

6.2 Value Iteration — Algorithm and Race Car Example

6.2.1 Symbol Registry — Value Iteration

s — current state — $s$ — element of state space S
a — action — $a$ — element of action space A
s' — next state after taking action a — $s^{'}$ — element of S
$π (a ∣ s)$ — probability of taking action a in state s under policy $π$ — $π (a ∣ s)$ — scalar in [0,1]
$γ$ — discount factor — $γ$ — scalar in [0,1)
$P (s^{'} ∣ s, a)$ — transition probability from s to s' given action a — $P (s^{'} ∣ s, a)$ — scalar in [0,1]
$R (s, a, s^{'})$ — immediate reward — $R (s, a, s^{'})$ — scalar
$V^{*} (s)$ — optimal value of state s — $V^{*} (s)$ — scalar

6.2.2 The Race Car MDP

Hook: How do you actually compute the optimal value function

V^{*}

? You could try to solve the Bellman optimality equation directly, but that requires inverting a huge system of equations. Value iteration takes a simpler approach: start with any initial values, then repeatedly apply the Bellman optimality equation as an update rule. The values will converge to

V^{*}

The race car example has three states: cool, warm, and overheated. Overheated is a terminal state — once the car overheats, it is done and the value of that state is zero. From cool, two actions are available: slow and fast. From warm, two actions are also available: slow and fast.

Intuition: Think of the race car as a simple game. You start cool. You can drive slowly (safe, +1 reward, stay cool) or drive fast (risky, +2 reward, but might heat up). If you're warm and drive fast, you overheat and lose 10 points. The question is: what's the long-term value of being in each state?

Transition dynamics for the race car:

Cool → slow: With probability 1, the car remains cool. Immediate reward = +1.
Cool → fast: With probability 0.5 the car stays cool (reward +2), and with probability 0.5 the car goes to warm (reward +2). So fast has two branches, each with probability 0.5 and reward +2.
Warm → slow: With probability 0.5 the car goes to cool (reward +1), and with probability 0.5 the car stays warm (reward +1).
Warm → fast: With probability 1 the car goes to overheated. Immediate reward = −10.

Red lines in the diagram indicate driving fast. The objective is to estimate the value of being in each state — what is the value of being cool, warm, or overheated — using value iteration.

Race Car MDP — State Transition Diagram

Red lines: Driving Fast (Risky, High Reward / Overheat Risk) | Blue lines: Driving Slow (Safe, Lower Reward)

Interactive Value Iteration Workbench

Watch state values $V_{k} (s)$ converge sweep-by-sweep under the Bellman optimality update.

Discount factor

γ

Cool State $V (C oo l)$ FAST

0.000

Q(slow)=0.00 | Q(fast)=0.00

Warm State $V (W a r m)$ SLOW

0.000

Q(slow)=0.00 | Q(fast)=0.00

Overheated $V (O v er h e a t e d)$ TERMINAL

0.000

Fixed at 0.00 (No action choices)

Sweep Status: Iteration k = 0 (Initialized at 0.00)

                Ready to execute Value Iteration. Click "Step 1 Iteration" or "Run to Convergence".
              

Figure 6.2: Visual state-transition graph and interactive Value Iteration model for the Race Car MDP.

6.2.3 Value Iteration Algorithm

Value Iteration Algorithm:

The value iteration algorithm has two loops:

Outer loop: "Repeat until convergence" — initialize delta (the maximum change in value across all states in one iteration) to 0. Delta tracks the largest difference between the old and new value estimates. If delta becomes smaller than a threshold θ, the values have converged and the algorithm stops. Inner loop: For each state s ∈ S, apply the Bellman optimality equation to revise the value estimate. That is, for each state, compute the value of each available action (summing over possible next states weighted by their probabilities and including the discounted previous value of each next state), then take the maximum over actions as the new value.

The update rule for each state is:

$V_{k + 1} (s) = a max s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V_{k} (s^{'})]$

This is simply the Bellman optimality equation turned into an iterative update: at each step k, we use the current estimates $V_{k}$ to compute new estimates $V_{k + 1}$ .

Professor's advice: "To begin with, you need not really worry about this delta and theta. In your mind, all you need to know is if the difference between the values of subsequent iterations is not much, you can stop."

Sweeps. In dynamic programming terminology, going through all states once and updating each value is called a sweep. Value iteration performs multiple sweeps across the state space until convergence.

Assumptions & Scope:

Value iteration requires complete knowledge of the MDP (the model P and reward R)
The state space must be finite (or discretized)
The discount factor $γ$ must be in [0,1)
The algorithm is guaranteed to converge to $V^{*}$ under these conditions
Convergence is asymptotic — in practice, we stop when changes are below threshold θ

6.2.4 Worked Example: Race Car Value Iteration (Sweep 1)

Worked Example: Race Car Value Iteration — Sweep 1 Initialization. All state values are set to 0:

V_{0} (cool)

= 0,

V_{0} (warm)

= 0,

V_{0} (overheated)

= 0. The overheated state is terminal; its value remains 0 throughout. Sweep 1 — Computing V1(cool).

For the slow action from cool: there is only one outcome (stay in cool) with probability 1. The formula gives:

$Q (cool, slow) = 1 \times [1 + 0.9 \times V_{0} (cool)] = 1 \times [1 + 0.9 \times 0] = 1$

$Q (cool, fast) = 0.5 \times [2 + 0.9 \times V_{0} (cool)] + 0.5 \times [2 + 0.9 \times V_{0} (warm)] = 0.5 (2) + 0.5 (2) = 2$

Take the max: V1(cool) = max(1, 2) = 2.

Sweep 1 — Computing V1(warm).

For the fast action from warm: with probability 1, the car goes to overheated (reward −10):

$Q (warm, fast) = 1 \times [- 10 + 0.9 \times V_{0} (overheated)] = 1 \times [- 10 + 0] = - 10$

For the slow action from warm: two branches, each with probability 0.5. One branch goes to cool (reward +1), the other stays warm (reward +1):

$Q (warm, slow) = 0.5 \times [1 + 0.9 \times V_{0} (cool)] + 0.5 \times [1 + 0.9 \times V_{0} (warm)] = 0.5 (1) + 0.5 (1) = 1$

Take the max: V1(warm) = max(−10, 1) = 1.

V1(overheated) remains 0 (terminal). Summary after sweep 1: V1(cool) = 2, V1(warm) = 1, V1(overheated) = 0. Sense-check: After one sweep with all-zero initial values, the values reflect only the immediate expected reward. Cool is worth 2 (the fast action gives +2), warm is worth 1 (the slow action gives +1). These values will grow as future rewards propagate through subsequent sweeps.

Pitfalls:

Forgetting terminal states: Terminal states always have value 0 and are never updated. Do not include them in the inner loop.
Using wrong iteration values: When computing $V_{k + 1} (s)$ , use $V_{k}$ (s') — the values from the previous iteration, not the most recently updated values (that would be the in-place variant, covered in Section 6.3).
Miscounting branches: For actions with multiple outcomes, each outcome has its own probability and reward. Don't aggregate them incorrectly.

Recap: Value iteration repeatedly applies the Bellman optimality equation as an update rule until convergence. Starting from any initial values (typically all zeros), each sweep updates every state's value by taking the max over actions. The race car example shows how the algorithm computes V1 from V0 in one sweep.

Bridge: A natural question arises — can we use the most recently computed values within the same sweep? This leads to the distinction between in-place and not-in-place value iteration.

6.3 In-Place vs Not-In-Place Value Iteration

6.3.1 The Two Variants

Q: "In this one, the warm one, what is the previous? I thought previous would be two. No. But we took zero." A: When computing the values at iteration 1 (V1), you use the values from the previous iteration (V0), which are all initialized to 0. When you compute V2, you will use the values from V1 as the "previous" values. The student was thinking about using the most recently computed value of cool (which is 2) when computing warm, which leads to the in-place variant.

Hook: When we compute V1(warm), we used

V_{0} (cool)

= 0. But V1(cool) = 2 has already been computed! Why not use the freshest value? This question leads to two fundamentally different approaches to value iteration.

Not-in-place (standard) version. You maintain separate arrays for each iteration: V0, V1, V2, etc. When computing V1(warm), you use

V_{0} (cool)

= 0, even though V1(cool) = 2 has already been computed in the current sweep. The rule: "always use values from the previous iteration."

In-place version. You maintain a single array for values. Initialize all values to 0. In the first sweep, when you compute cool's value as 2, you immediately overwrite the old value. When you then compute warm, you reference the most recently updated value of cool (which is now 2), not the old 0. The rule: "always use the most recent values."

Worked Example: Comparing In-Place vs Not-In-Place (Sweep 1) Setup: Race car MDP,

γ = 0.9

V_{0} (cool)

= 0,

V_{0} (warm)

= 0,

V_{0} (overheated)

= 0. Not-in-place (standard):

V1(cool) = max{1, 2} = 2 (using V0 values)
V1(warm) = max{−10, 1} = 1 (using V0 values)
V1(overheated) = 0

In-place:

V1(cool) = max{1, 2} = 2 (using V0 values)
Now update V(cool) to 2 in the single array
V1(warm) = max{−10, 1} = 1 (using V0 values — $V_{0} (warm)$ = 0, $V_{0} (cool)$ = 0)

Wait — in this case, the in-place result is the same because we used $V_{0} (warm)$ for warm's own value, and $V_{0} (cool)$ for cool's value in the warm computation. The difference appears when we reference a state whose value was already updated in this sweep.

Sweep 2 (showing the difference): Not-in-place: V1(cool) = 2, V1(warm) = 1

V2(cool) = max{1 + 0.9×2, 0.5×(2+0.9×2) + 0.5×(2+0.9×1)} = max{2.8, 3.25} = 3.25 (using V1 values)
V2(warm) = max{−10 + 0.9×0, 0.5×(1+0.9×2) + 0.5×(1+0.9×1)} = max{−10, 2.35} = 2.35 (using V1 values)

In-place: V1(cool) = 2, V1(warm) = 1

V2(cool) = 3.25 (same as not-in-place — cool is processed first)
Now update V(cool) to 3.25
V2(warm) = max{−10, 0.5×(1+0.9×3.25) + 0.5×(1+0.9×1)} = max{−10, 0.5×3.925 + 0.5×1.9} = max{−10, 2.9125} = 2.9125

(uses the updated V(cool) = 3.25, not the old V1(cool) = 2)

Key difference: The in-place version gets V2(warm) = 2.9125 while not-in-place gets V2(warm) = 2.35. The in-place version converges faster because it uses the freshest information.

Exam note: "When you are writing an examination, the question would actually be referring to terms like in-place algorithm or the standard algorithm. If you are explicitly asked in-place algorithm, you need to show that at every step, the most recent values are actually being used."

This means: if you are computing $V_{k} (s)$ for some state s, and another state s' has already been updated in this sweep (i.e., $V_{k - 1} (s^{'})$ has been overwritten with $V_{k}$ (s')), then you MUST use $V_{k}$ (s') — the updated value — not $V_{k - 1} (s^{'})$ .

Key Properties:

Both versions converge to the same optimal values $V^{*}$ .
They differ in the speed and pattern of convergence.
Experimentally, the in-place version converges faster (because it uses fresher information).
The in-place version is also known as the Gauss-Seidel method in numerical linear algebra.
The not-in-place version is also known as the Jacobi method.

Pitfalls:

Confusing the two in exams: If asked for "in-place," you must show that updated values are used. If asked for "standard" or "not-in-place," use only values from the previous iteration.
Forgetting the order matters: In the in-place version, the order in which you process states affects the convergence pattern (though not the final answer). Processing states in a smart order can speed up convergence.
Assuming both give identical intermediate values: They don't — only the final converged values are the same. The intermediate values during iteration differ.

Recap: The standard (not-in-place) value iteration uses separate arrays for each iteration, always referencing the previous iteration's values. The in-place version overwrites values immediately and uses the most recent values. Both converge to

V^{*}

, but in-place is faster. In exams, explicitly show which version you are using.

Bridge: Now that we can compute

V^{*}

, the next question is: how do we extract the optimal policy from these converged values?

6.4 Policy Extraction from Value Iteration

6.4.1 Symbol Registry — Policy Extraction

$π (s)$ — deterministic policy for state s — $π (s)$ — action
a — action being evaluated — $a$ — element of action space A
$V^{*} (s^{'})$ — converged optimal value of next state — $V^{*} (s^{'})$ — scalar
$γ$ — discount factor — $γ$ — scalar in [0,1)

6.4.2 Extracting the Policy

Hook: Value iteration gives us

V^{*}

— the optimal value of each state. But what we actually want is a policy: what action should I take in each state? The extraction step converts values into actions.

After the value iteration converges, you need to extract the optimal policy $π (s)$ for each state. The algorithm's final step says "output a deterministic policy $π$ ."

Policy Extraction Formula:

For each state s, consider every available action a. Compute the value of taking action a using the same Bellman optimality formula but now with the converged values. Use the argmax over actions — the action that yields the highest value becomes the policy for that state:

$π (s) = ar g a max s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{*} (s^{'})]$

This is exactly the same computation as in value iteration, but instead of taking the max to get a value, we take the argmax to get the action that achieves that maximum.

Professor's verbal description: "For each action, compute the values of their outcomes, and choose the action that gives the highest outcome."

Intuition: Think of it like choosing a route on a map. Value iteration computed how good each city (state) is. Policy extraction is simply: "from each city, which road leads to the best-valued destination?" You don't need to recompute the values — just look them up and pick the road with the highest total (immediate reward + discounted destination value).

Worked Example: Policy Extraction for the Race Car (Using Converged Values)

Using the converged values V(cool) = 3.35, V(warm) = 2.35, V(overheated) = 0, and $γ = 0.9$ :

For cool — slow action:

$Q (cool, slow) = 1 \times [1 + 0.9 \times 3.35] = 1 + 3.015 = 4.015$

For cool — fast action:

$Q (cool, fast) = 0.5 \times [2 + 0.9 \times 3.35] + 0.5 \times [2 + 0.9 \times 2.35]$

$= 0.5 \times [2 + 3.015] + 0.5 \times [2 + 2.115] = 0.5 \times 5.015 + 0.5 \times 4.115 = 4.565$

Comparing: fast (4.565) > slow (4.015), so

π (cool) = fast

. For warm — slow action:

$Q (warm, slow) = 0.5 \times [1 + 0.9 \times 3.35] + 0.5 \times [1 + 0.9 \times 2.35]$

$= 0.5 \times [1 + 3.015] + 0.5 \times [1 + 2.115] = 0.5 \times 4.015 + 0.5 \times 3.115 = 3.565$

For warm — fast action:

$Q (warm, fast) = 1 \times [- 10 + 0.9 \times 0] = - 10$

Comparing: slow (3.565) > fast (−10), so

π (warm) = slow

. For overheated: Terminal state, no policy defined. Final policy:

$π (cool) = fast$
$π (warm) = slow$

Sense-check: The policy says: when cool, drive fast (gain +2 reward, risk warming up). When warm, drive slow (gain +1, avoid overheating). This makes intuitive sense — the optimal policy balances reward-seeking with risk management.

Scope & Pitfalls:

Deterministic policy only: Value iteration always produces a deterministic policy $π (s)$ = a. It will NOT give you probabilities like "drive slow is 0.7, drive fast is 0.3." If the argmax has ties, you can break them arbitrarily — the resulting policy is still optimal.

Notation matters: Write $π (s) = a$ (deterministic), NOT $π (a ∣ s)$ = probability. The professor emphasized: "You must be very clear that this algorithm is outputting a deterministic policy $π$ ."

Terminal states excluded: No policy is defined for terminal states — they have no outgoing actions.

Policy extraction cost: Computing the policy for all states costs $O (∣ S ∣^{2} ∣ A ∣)$ — the same as one iteration of value iteration.

Recap: Policy extraction is the final step of value iteration: for each state, compute the value of each action using the converged

V^{*}

values, and pick the action that maximizes this value. The result is a deterministic policy

π (s) = a

that tells you exactly what to do in each state.

Bridge: The race car example showed a complete value iteration. Now let's see a more complex example with multiple states in a grid, which will naturally lead us to the concept of policy evaluation.

6.5 Policy Evaluation

6.5.1 Definition and Intuition

Hook: Before we can improve a policy, we need to know how good it is. Policy evaluation answers: given a fixed policy

π

, how valuable is each state? The same state can be a goldmine or a death trap depending on the policy you follow.

Policy evaluation answers the question: given a fixed policy

π

, how good is each state? If I give you a policy and a state space, policy evaluation tells you the value of being in each state under that policy.

Analogy (Professor's CXO Position): "It seems that you are actually in a very top position — the value of being in that position depends on the policy. A person is hired for a high position, and you would assume he is great, but if he behaves badly, he makes nothing out of it. But a very good person who takes advantage of the position will make the value of that position pretty high. You cannot simply say the value of taking a position of CXO is always great — it depends on who is in that position and what he makes out of it."

The same state can have very different values depending on the policy. A good policy leads to positive values; a poor policy leads to negative values even from the same starting state.

6.5.2 Policy Evaluation Formula

Policy Evaluation Bellman Expected Update:

Policy evaluation uses the Bellman expected update equation with the fixed policy $π$ :

$V^{π} (s) = a \sum π (a ∣ s) s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{π} (s^{'})]$

This is the same equation from Section 6.1, applied iteratively: initialize all values, then repeatedly update each state's value using this equation until convergence.

Key distinction from value iteration: In policy evaluation, the policy

π

is FIXED. We use the expected update (weighted average over actions per

π

) rather than the optimality update (max over actions). We are not trying to find the best action — we are evaluating a given policy.

6.5.3 Policy Evaluation Algorithm

Iterative Policy Evaluation Algorithm

Initialization: Set $V (s)$ arbitrarily (e.g., 0) for all non-terminal states $s \in S^{+}$ , and $V (terminal) = 0$ .
Iterative Update: Repeat until convergence ( $Δ < θ$ ):
- $Δ \leftarrow 0$
- For each non-terminal state $s \in S$ :
  $v \leftarrow V (s)$ $V (s) \leftarrow a \in A \sum π (a ∣ s) s^{'} \in S \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V (s^{'})]$ $Δ \leftarrow max (Δ, ∣ v - V (s) ∣)$
Output: Converged value function $V \approx V^{π}$ .

Professor's summary: "For each state, you estimate the value based on Bellman expected update equation. Keep computing value of S for each state using the Bellman equation. Keep repeating it. Once it converges, you know the value of each of the states."

6.5.4 Worked Example: 5-State Grid Problem

Worked Example: 5-State Grid Policy Evaluation

Consider five states arranged linearly. The agent starts at state 3 and can move Left (L) or Right (R) at each step:

Bad (1)

Terminal (R = −1)

⟵ ⟶

State 2

Non-terminal

⟵ ⟶

Start (3)

Start State

⟵ ⟶

State 4

Non-terminal

⟵ ⟶

Good (5)

Terminal (R = +1)

Environment Rules: Non-terminal states: ${2, 3, 4}$ . Initial values $V_{0} (s) = 0$ for all states. Terminal states $V (Bad) = V (Good) = 0$ throughout. All step transition rewards are 0, except entering Bad ( $R = - 1$ ) or Good ( $R = + 1$ ).

Scenario 1: Left-Biased Policy ( $π (L) = 0.8, π (R) = 0.2$ )

"Wherever you are, you are strongly inclined to move Left."

Sweep 1 Calculations:

State 2: Going L (0.8) $\to$ Bad ( $R = - 1, V_{0} = 0$ ); Going R (0.2) $\to$ Start ( $R = 0, V_{0} = 0$ )
$V_{1} (2) = 0.8 \times [- 1 + 0] + 0.2 \times [0 + 0] = - 0.80$
Start (3): Going L (0.8) $\to$ State 2 ( $R = 0, V_{0} = 0$ ); Going R (0.2) $\to$ State 4 ( $R = 0, V_{0} = 0$ )
$V_{1} (Start) = 0.8 \times [0 + 0] + 0.2 \times [0 + 0] = 0.00$
State 4: Going L (0.8) $\to$ Start ( $R = 0, V_{0} = 0$ ); Going R (0.2) $\to$ Good ( $R = + 1, V_{0} = 0$ )
$V_{1} (4) = 0.8 \times [0 + 0] + 0.2 \times [1 + 0] = + 0.20$

After Sweep 1: $V_{1} (2) = - 0.80, V_{1} (Start) = 0, V_{1} (4) = + 0.20$

Converged Values ( $V_{\infty}$ ): $V (2) \approx - 0.80, V (Start) \approx - 0.78, V (4) \approx - 0.28$ .
⚠️ ALL NEGATIVE: Because the policy heavily prefers Left, the agent is consistently driven toward the Bad terminal state.

Scenario 2: Right-Biased Policy ( $π (L) = 0.2, π (R) = 0.8$ )

"Wherever you are, you are strongly inclined to move Right."

Sweep 1 Calculations:

State 2: $V_{1} (2) = 0.2 \times [- 1 + 0] + 0.8 \times [0 + 0] = - 0.20$
Start (3): $V_{1} (Start) = 0.2 \times [0 + 0] + 0.8 \times [0 + 0] = 0.00$
State 4: $V_{1} (4) = 0.2 \times [0 + 0] + 0.8 \times [1 + 0] = + 0.80$

After Sweep 1: $V_{1} (2) = - 0.20, V_{1} (Start) = 0, V_{1} (4) = + 0.80$

Converged Values ( $V_{\infty}$ ): State 4 achieves a high positive value ( $\approx + 0.80$ ), and positive reward flows back through Start to State 2.
✓ MOSTLY POSITIVE: Favoring Right makes proximity to the Good terminal valuable.

Scenario 3: Equal Policy ( $π (L) = 0.5, π (R) = 0.5$ )

"Unbiased random walk in both directions."

Sweep 1 Calculations:

State 2: $V_{1} (2) = 0.5 \times [- 1 + 0] + 0.5 \times [0 + 0] = - 0.50$
Start (3): $V_{1} (Start) = 0.5 \times [0 + 0] + 0.5 \times [0 + 0] = 0.00$
State 4: $V_{1} (4) = 0.5 \times [0 + 0] + 0.5 \times [1 + 0] = + 0.50$

Converged Values ( $V_{\infty}$ ): Values stabilize symmetrically. State 2 is slightly negative ( $\approx - 0.25$ ), State 4 is slightly positive ( $\approx + 0.25$ ), and Start stays near 0.

Policy Comparison Matrix

Policy Scenario	$π (L) / π (R)$	Sweep 1 $(V_{1} (2), V_{1} (3), V_{1} (4))$	Converged $(V_{\infty} (2), V_{\infty} (3), V_{\infty} (4))$	Key Insight
Left-Biased	0.8 / 0.2	$(- 0.80, 0.00, + 0.20)$	$(- 0.80, - 0.78, - 0.28)$	Drives toward BAD state; entire state space becomes negative.
Right-Biased	0.2 / 0.8	$(- 0.20, 0.00, + 0.80)$	$(+ 0.28, + 0.78, + 0.80)$	Drives toward GOOD state; positive value flows backwards.
Equal (Unbiased)	0.5 / 0.5	$(- 0.50, 0.00, + 0.50)$	$(- 0.25, 0.00, + 0.25)$	Symmetric evaluation reflecting equal distance to terminals.

Key Takeaway: The exact same MDP (same states, actions, rewards) yields completely different value functions depending on the policy being evaluated. Value functions measure the quality of a specific behavior in an environment.

Scope & Pitfalls:

Policy must be fixed: Policy evaluation assumes the policy does NOT change during the evaluation. If you change the policy mid-evaluation, the values become meaningless.
Terminal states are always 0: Do not update terminal states — their value is defined to be 0.
Uses expected update, NOT max: In policy evaluation, you average over actions per $π$ (using $\sum_{a} π (a ∣ s)$ ), not take the max. Using max would be value iteration, not policy evaluation.
Convergence is guaranteed: Under standard conditions ( $γ < 1$ or eventual termination), iterative policy evaluation converges to $V^{π}$ .

Recap: Policy evaluation computes

V^{π}

— the value of each state under a FIXED policy — by repeatedly applying the Bellman expected update equation. The same MDP can yield very different value functions under different policies. The professor's key insight: "Behavior is the key — if you have a behavior which is good, you get the best out of it."

Bridge: Now that we can evaluate a policy (find

V^{π}

), the natural next step is: can we use those values to improve the policy? This leads to policy improvement.

6.6 Policy Improvement

6.6.1 Greedy Policy Improvement

Hook: We can evaluate a policy (find

V^{π}

). But can we do better? The policy improvement theorem says: yes — by acting greedily on the value function, you can always find a policy that is at least as good, and usually better.

After evaluating a policy (finding $V^{π}$ for each state), the next question is: can we improve the policy by acting greedily on the evaluated values?

Policy Improvement Theorem:

The policy improvement theorem states: if for a deterministic policy $π$ , we define a new policy $π^{'}$ that is greedy with respect to $V^{π}$ , then $π^{'}$ is guaranteed to be at least as good as $π$ . Formally, if

$q^{π} (s, π^{'} (s)) \geq v^{π} (s) for all s \in S$

then

$v^{π^{'}} (s) \geq v^{π} (s) for all s \in S$

with strict improvement at any state where the first inequality is strict.

The greedy policy $π^{'}$ is defined as:

$π^{'} (s) = ar g a max s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{π} (s^{'})]$

This is the same formula as policy extraction (Section 6.4), but applied to $V^{π}$ (the value of the current policy) rather than $V^{*}$ (the optimal value).

The professor said: "I just want you to go through this theorem offline. I may not even ask you to recite this theorem in the exams, but I want you to go through it."

Intuition: After policy evaluation tells you how good each state is under the current policy, look at those values and greedily ask: "Can I do better?" If the current policy says go left from state 2 (value −0.80), but going right gives a better expected value, then update the policy to go right from state 2.

Worked Example: Improving the Left-Biased Policy

Starting from the left-biased policy ( $π (L) = 0.8, π (R) = 0.2$ ), policy evaluation gives negative values for all states:

$V^{π}$ (2) ≈ −0.80
$V^{π}$ (Start) ≈ −0.78
$V^{π}$ (4) ≈ −0.28

Now apply greedy policy improvement to each state:

State 2:

Action left (current policy): leads to Bad, expected value = −1
Action right: leads to Start (value ≈ −0.78), expected value = 0 + 0.9 × (−0.78) = −0.702
Right is better (−0.702 > −1) → change $π (2)$ to right

Start (3):

Action left: leads to State 2 (value ≈ −0.80), expected value = 0 + 0.9 × (−0.80) = −0.72
Action right: leads to State 4 (value ≈ −0.28), expected value = 0 + 0.9 × (−0.28) = −0.252
Right is better (−0.252 > −0.72) → change $π (Start)$ to right

State 4:

Action left: leads to Start (value ≈ −0.78), expected value = 0 + 0.9 × (−0.78) = −0.702
Action right: leads to Good (value = 1 since terminal), expected value = 1 + 0 = 1
Right is better (1 > −0.702) → change $π (4)$ to right

Improved policy: All states now favor going right — the policy has improved!

One can also create a stochastic policy by making the probability proportional to the relative goodness of each action. After improving the policy, you go back and evaluate the new policy, then improve again. This cycle of evaluate → improve → evaluate → improve continues until the policy stops changing.

Pitfalls:

Not re-evaluating: After improving the policy, you MUST re-evaluate it (run policy evaluation again) before the next improvement step. The old $V^{π}$ is no longer valid for the new policy.
Ties: If two actions have equal value, the argmax can pick either. The resulting policy is still optimal.
Terminal states: No policy improvement is needed for terminal states — they have no outgoing actions.

Recap: Policy improvement greedily updates each state's action to the one that maximizes expected value (using

V^{π}

from the current policy). The policy improvement theorem guarantees this new policy is at least as good. Combined with policy evaluation, this creates an evaluate-improve cycle that converges to the optimal policy.

Bridge: The evaluate-improve cycle is so fundamental that it has a name: Generalized Policy Iteration (GPI). Let's formalize this pattern.

6.7 Generalized Policy Iteration (GPI)

6.7.1 The Evaluate-Improve Cycle

Hook: Policy evaluation and policy improvement are like two dancers pulling in opposite directions — one makes the value function match the policy, the other makes the policy greedy on the values. This tension, when it stabilizes, gives you the optimal solution.

The evaluate-improve cycle is called Generalized Policy Iteration (GPI). The big picture: you start with a fixed policy, perform policy evaluation to get the value function, then greedily improve the policy using those values, and repeat.

Generalized Policy Iteration (GPI):

Start with an arbitrary policy $π_{0}$
Evaluate: Compute $V^{π}$ (the value function for the current policy)
Improve: Make the policy greedy with respect to $V^{π}$
Repeat steps 2–3 until the policy stops changing

When both processes stabilize (the policy is greedy with respect to its own value function), you have found the optimal policy $π^{*}$ and optimal value function $V^{*}$ .

Professor's summary: "You start with a fixed policy and you perform policy evaluation. You get the value for the policy. Now take the value and be greedy in the value and update the policy. Keep repeating it. Finally, you will get optimal value and optimal policy."

Analogy (Professor's SGD Analogy): "When you do machine learning, you have stochastic gradient descent, mini-batch gradient descent, and batch gradient descent. Stochastic gradient descent makes an update based on every single example — it is a very bad comparison, but I'm trying to relate. You evaluate, simultaneously improve. You don't know what you're doing, but things work."

The professor is drawing a parallel: in SGD, you update parameters after each batch (not after seeing all data). In GPI, you can improve the policy after partial evaluation (not waiting for full convergence). Both work because the iterative process converges regardless of the granularity of updates.

Scope: GPI is a framework, not a specific algorithm. It describes the general idea of letting policy evaluation and policy improvement interact. Different algorithms make different choices within this framework:

Policy iteration: Full policy evaluation (to convergence) at each step
Value iteration: One sweep of policy evaluation per improvement step
Truncated policy iteration: A few sweeps of policy evaluation per improvement step
Asynchronous methods: Interleave evaluation and improvement at the finest grain

The key insight: "This actually gives you a way by which you design how you do the learning."

Pitfalls:

Thinking GPI is one specific algorithm: GPI is a general framework — many algorithms are instances of GPI.
Assuming full evaluation is required: You do NOT need to run policy evaluation to convergence before improving. Partial evaluation also converges to optimal.
Confusing the two processes: Policy evaluation makes $V$ match $π$ (V → $V^{π}$ ). Policy improvement makes $π$ greedy on $V$ ( $π \to greedy (V)$ ). They pull in opposite directions but converge together.

Recap: GPI is the fundamental pattern of alternating between policy evaluation and policy improvement. It is the umbrella under which value iteration, policy iteration, and many RL algorithms operate. The granularity of evaluation (full, partial, or single sweep) gives rise to different algorithms.

Bridge: Let's now see the full policy iteration algorithm — GPI with complete policy evaluation at each step.

6.8 Policy Iteration Algorithm

6.8.1 Algorithm Steps

Hook: Value iteration works with values — iterate Bellman optimality until V converges, then extract the policy. Policy iteration works with policies — alternate between fully evaluating a policy and improving it until the policy stops changing. Both converge to the optimal policy, but they take very different paths.

Policy Iteration Algorithm:

Initialize: Set an initial policy $π_{0}$ (random or arbitrary). Initialize V(s) arbitrarily for all states.
Policy Evaluation: Run iterative policy evaluation (Bellman expected update) until convergence to get $V^{π}$ for the current policy.
Policy Improvement: For each state s:

$π^{'} (s) = ar g a max s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{π} (s^{'})]$

Check stability: If $π^{'} = π$ (policy unchanged), stop — you have $π^{*}$ and $V^{*}$ . Otherwise, set $π \leftarrow π^{'}$ and go to step 2.

The stopping condition is policy stability: "You stop when the policy between two iterations doesn't change." Repeat the evaluate-improve cycle until the policy is stable.

Worked Example: Policy Iteration on the 5-State Grid

Start with an arbitrary policy: $π_{0}$ = always go left.

Iteration 1:

Evaluate: Run policy evaluation for $π_{0}$ = always left. Converged values: $V (2)$ ≈ −1, $V (Start)$ ≈ −0.9, $V (4)$ ≈ −0.8 (all very negative because going left means hitting Bad).
Improve: At each state, going right gives better value than going left:
State 2: left → Bad (−1), right → Start (−0.9). Right is better → $π_{1}$ (2) = right
Start: left → State 2 (−1), right → State 4 (−0.8). Right is better → $π_{1}$ (Start) = right
State 4: left → Start (−0.9), right → Good (+1). Right is better → $π_{1}$ (4) = right
Policy changed ( $π_{1}$ ≠ $π_{0}$ ) → continue.

Iteration 2:

Evaluate: Run policy evaluation for $π_{1}$ = always right. Converged values: $V (2)$ ≈ +0.7, $V (Start)$ ≈ +0.8, $V (4)$ ≈ +0.9 (positive because going right means reaching Good).
Improve: At each state, going right still gives the best value.
Policy unchanged ( $π_{2}$ = $π_{1}$ ) → STOP. $π^{*}$ = always right, $V^{*}$ = converged values.

Intuition: Policy iteration is like hill-climbing on the landscape of policies. Each iteration, you first measure how good the current policy is (evaluation), then jump to the best neighboring policy (improvement). The policy improvement theorem guarantees you never go downhill.

Key difference from value iteration:

Value iteration: Initialize values, iterate Bellman optimality (max) until V converges, then extract policy. Works with values.
Policy iteration: Initialize policy, alternate between full evaluation (expected update) and greedy improvement. Works with policies.
Convergence: Both converge to the same optimal policy, but policy iteration often converges in fewer iterations (though each iteration is more expensive).

Pitfalls:

Incomplete evaluation: Policy iteration requires FULL policy evaluation (to convergence) before improvement. Truncating evaluation changes the algorithm to truncated policy iteration or value iteration.
Cycling: If the policy continually switches between equally good policies, the algorithm may never terminate (Exercise 4.4 in Sutton & Barto addresses this).
Initialization matters: Starting with a good initial policy (close to optimal) reduces the number of iterations needed.

Recap: Policy iteration = full policy evaluation + greedy policy improvement, repeated until the policy is stable. It is GPI with complete evaluation at each step. It often converges in fewer iterations than value iteration, but each iteration is more expensive (because evaluation must converge fully).

Bridge: Now that we have both value iteration and policy iteration, the natural question is: which one is better? The answer is nuanced.

6.9 Value Iteration vs Policy Iteration: Convergence and Comparison

6.9.1 The Policy-Convergence-Before-Values Observation

Hook: A striking observation about value iteration: the policy converges long before the values do. By iteration 10, the best actions are settled. But the values keep changing until iteration 100. If policy is all that matters, why wait for values to converge?

Worked Example: Grid Problem — Policy Converges Before Values

Using value iteration on a grid problem, the professor tracked both values and policies across iterations:

Iteration 10:

Policy: arrows indicating best actions have STABLE — no more changes
Values: still changing (e.g., 0.41 → 0.42, 0.27 → 0.28)

Iteration 100:

Policy: same as iteration 10 (unchanged)
Values: finally converged (changes are negligible)

Key insight: "If policy is all that matters, the policy got converged by the 10th iteration. Policy did not change after 10." Interpretation: The values needed 100 iterations to settle to their final decimal places, but the policy (which action is best) was already determined by iteration 10. This suggests that once the values are "good enough" to rank actions correctly, further refinement is unnecessary for policy purposes.

However, the professor cautioned: "That should not tell you that if I stop at iteration 10, I'm really good. In policy iteration, each iteration runs full policy evaluation, which is time-consuming."

Caveat: Just because the policy converged early does NOT mean you can safely stop value iteration at that point. In some problems, the policy can appear stable for many iterations and then change. You need to wait for delta < θ to be confident.

6.9.2 Value Iteration Versus Policy Iteration: Which Is Better?

Comparison: Value Iteration vs Policy Iteration

Aspect	Value Iteration	Policy Iteration
Works with	Values (V)	Policies ( $π$ )
Update per iteration	One sweep of Bellman optimality	Full policy evaluation (many sweeps) + improvement
Cost per iteration	$O (∣ S ∣^{2} ∣ A ∣)$ — cheap	O(S²A × #eval_sweeps) — expensive
# iterations to converge	Many	Few
Stopping condition	δ < θ (values stabilize)	Policy unchanged
Practical advantage	Fast iterations, usable policy early	Fewer total iterations

The professor referenced the Sutton and Barto textbook (Chapter 4 on dynamic programming): "It closes saying that it is very difficult to decide which is a good idea to solve a DP problem — policy iteration or value iteration. It's very difficult to quantify for all problems which one is good."

Professor's Personal Take: "I would certainly like to have value iteration, not policy iteration. The reason is each iteration of value iteration takes a very small amount of time, whereas each iteration of policy iteration takes a lot of time. You might say policy iteration stops early because policy converges as soon as the policy is converged, but inside each loop there's one full policy evaluation running to convergence."

"Practically most problems, value iteration, the way we have done, is actually good, because each iteration goes faster, very quickly you get a usable policy."

The textbook also notes that while in-place updates certainly improve convergence speed, it is very difficult to quantify the improvement mathematically.

Pitfalls:

Assuming fewer iterations = faster: Policy iteration converges in fewer iterations, but each iteration is much more expensive (full policy evaluation). Total computation may be higher.
Ignoring the cost of policy evaluation: Policy iteration's "few iterations" advantage is offset by the cost of running full evaluation each time.
Thinking one is always better: Neither algorithm dominates across all problems. The choice depends on the specific problem structure.

Recap: Policy converges before values in value iteration. Policy iteration takes fewer iterations but each is expensive; value iteration takes more iterations but each is cheap. The textbook says it's hard to declare a winner. The professor prefers value iteration for practical speed.

Bridge: Let's now understand why value iteration's per-iteration cost is

O (∣ S ∣^{2} ∣ A ∣)

and what this means for large problems.

6.10 Computational Complexity of Value Iteration

6.10.1 Why $O (∣ S ∣^{2} ∣ A ∣)$ Per Iteration

Hook: We know value iteration converges, but at what cost? For a problem with 1 billion states and 100 actions, one iteration requires 100 billion operations. This is why DP methods don't scale to enormous state spaces without special techniques.

Per-Iteration Complexity: $O (∣ S ∣^{2} ∣ A ∣)$

Value iteration has per-iteration cost $O (∣ S ∣^{2} ∣ A ∣)$ , where S is the number of states and A is the number of actions. This per-iteration cost is significant for large state spaces.

Key points:

Per-iteration cost is $O (∣ S ∣^{2} ∣ A ∣)$ — big O of S squared times A
Policy extraction cost is also $O (∣ S ∣^{2} ∣ A ∣)$ per iteration

Why $O (∣ S ∣^{2} ∣ A ∣)$ ? For each state (S), for each action (A), the possible outcomes can be any of the S states. So for each state-action pair, you sum over up to S possible next states. This gives S × A × S = S²A.

Formally: the inner computation for one state s is:

$V (s) = a max S terms summed s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V (s^{'})]$

Outer loop: S states
For each state: A actions evaluated
For each action: S terms summed
Total: S × A × S = S²A

Professor's explanation with help from a student: "Assume you are taking a particular state s and an action a. The outcomes can be any state s1, s2, s3, ... — all the states. For each state, for each action state-action pair, the outcome could be any or all of the states in the state space. So S × S × A."

Q: A student helped clarify the

O (∣ S ∣^{2} ∣ A ∣)

complexity: from a single state, one action can lead to up to S outcomes. Multiply by A actions to get the cost per state, then multiply by S states for the total. A: The professor confirmed: for each state, for each action, the outcomes can be any of the S states in the state space, giving S × A × S = S²A per iteration.

Policy extraction cost is also

O (∣ S ∣^{2} ∣ A ∣)

per iteration. The professor worked through this: "You are actually going to do this for all states. For each action, for a given state, the outcomes can be each other state, so A × S. For all states, S × A × S = S²A."

Worked Example: Complexity in Practice

Problem	States (S)	Actions (A)	S²A per iteration
Race car (this lecture)	3	2	3² × 2 = 18
4×4 grid (Sutton & Barto)	14	4	14² × 4 = 784
Chess (approximate)	10⁴⁷	30	10⁴⁷ × 30 × 10⁴⁷ ≈ 10⁹⁵
Go (approximate)	10¹⁷⁰	250	~10³⁴¹

For the race car, 18 operations per iteration is trivial. For chess or Go, S²A is astronomically large — DP is completely infeasible. This is why model-free methods (covered later) are needed for such problems.

Scope: The

O (∣ S ∣^{2} ∣ A ∣)

cost assumes:

The transition function $P (s^{'} ∣ s, a)$ is dense (any state can be reached from any state-action pair)
If P is sparse (most transitions have probability 0), the actual cost can be much lower
The cost is PER ITERATION — total cost is O(S²A × #iterations)
Both value iteration and policy extraction have this same per-iteration cost

Pitfalls:

Confusing per-iteration with total cost: $O (∣ S ∣^{2} ∣ A ∣)$ is one sweep. Total cost depends on how many iterations until convergence.
Forgetting the S in the denominator: For sparse MDPs where each action leads to only a few next states, the cost per state-action pair is much less than S.
Ignoring policy extraction: Even after value iteration converges, extracting the policy costs another $O (∣ S ∣^{2} ∣ A ∣)$ .

Recap: Value iteration costs

O (∣ S ∣^{2} ∣ A ∣)

per iteration because for each of S states, we evaluate A actions, each requiring a sum over S possible next states. This makes DP infeasible for problems with very large state spaces, motivating the need for model-free methods.

Bridge: When the state space is huge, can we avoid sweeping through all states every iteration? Yes — asynchronous value iteration addresses this.

6.11 Asynchronous Value Iteration

6.11.1 Priority Queue Approach

Hook: When the state space has billions of states, even one sweep through all states is impractical. Asynchronous value iteration says: don't sweep — prioritize. Update the states that need it most, and let the rest wait.

When the state space is huge (billions of states), iterating through all states in every sweep is impractical. Asynchronous value iteration addresses this by maintaining a priority queue of states that are likely to need updating.

Asynchronous Value Iteration (Priority Queue Approach):

Maintain a priority queue of states to update
When you update a state's value, its neighbors (states whose Bellman computation depends on the updated state) become candidates for update
Place neighbors in the priority queue, ordered by expected change magnitude
States with large expected changes get higher priority and are updated sooner
A particular state might be updated many times before other states are touched at all
Continue until convergence (all changes are small)

Professor's explanation: "As and when you make an update in different states, you keep track of those potential states where there could be more updates. You maintain a priority queue in which these states are put in. Depending on how significant is the change in the neighbor, if the change is very significant, it gets a high priority. The larger the likelihood of change, the higher in the queue."

Intuition: Think of it like spreading news through a network. When a state's value changes, it's like a piece of breaking news. The neighbors of that state are the most likely to be affected — they should be "interviewed" (updated) first. States far from the change are unlikely to be affected and can wait. The priority queue ensures the most impactful updates happen first.

Scope & Pitfalls:

Convergence guarantee: Asynchronous VI converges correctly only if every state is updated infinitely often (no state is permanently ignored). The priority queue must ensure this.
Not a magic bullet: Avoiding sweeps doesn't reduce total computation — it just avoids committing to a full sweep before making progress. The algorithm can focus on the most "active" parts of the state space.
Priority design matters: The efficiency gain depends on how well the priority function predicts which states actually need updating.

The professor acknowledged the specific expressions are in the course material but deferred detailed treatment: "These exact expressions are in material at this moment. Don't worry about the rest of the details. Follow the level at which I discuss and say what is not necessary."

Recap: Asynchronous value iteration avoids full sweeps by prioritizing states with the largest expected changes. It uses a priority queue to focus computation where it matters most. Useful for very large state spaces where sweeping all states is infeasible.

Bridge: We've seen how to compute

V^{*}

and extract policies. But what if we work with Q-values (state-action values) instead of V-values? This leads to Q-learning.

6.12 Q-Learning in the Model-Based Setting

This section covers Q-learning in the model-based setting, including the $Q^{*} (s, a)$ expression, a worked example, and the distinction between model-based and model-free Q-learning.

6.12.1 Symbol Registry — Q-Learning

$Q^{*} (s, a)$ — optimal action-value function for state s, action a — $Q^{*} (s, a)$ — scalar
s — current state — $s$ — element of state space S
a — action taken in state s — $a$ — element of action space A
s' — next state — $s^{'}$ — element of S
a' — action taken in next state s' — $a^{'}$ — element of A
$P (s^{'} ∣ s, a)$ — transition probability — $P (s^{'} ∣ s, a)$ — scalar in [0,1]
R — immediate reward — $R$ — scalar
$γ$ — discount factor — $γ$ — scalar in [0,1)

6.12.2 Motivation: Why Q Values Instead of V Values?

Hook: Value iteration computes

V^{*} (s)

— the value of each state. But to extract the policy, you must evaluate every action for every state (costly). What if we compute

Q^{*} (s, a)

— the value of each state-action pair — directly? Then policy extraction becomes trivial: just compare Q-values and pick the largest.

The second computational problem with value iteration is that extracting the policy from V values is expensive ( $O (∣ S ∣^{2} ∣ A ∣)$ ). If instead we compute $Q^{*} (s, a)$ values directly — one value for each state-action pair — policy extraction becomes trivial.

Why Q-values simplify policy extraction: With V values: To find the best action for state s, you must:

For each action a: compute $\sum_{s^{'}} P (s^{'} ∣ s, a) [R + γ V^{*} (s^{'})]$
Take argmax over actions

Cost: O(SA) per state × S states = $O (∣ S ∣^{2} ∣ A ∣)$

With Q values: If you already have

Q^{*} (s, a)

for every action in state s:

Simply compare: $π^{*} (s) = ar g max_{a} Q^{*} (s, a)$
Cost: O(A) per state × S states = O(SA)

For a grid problem with 4 actions per cell, you compute 4 Q values per cell, then compare — much simpler than computing 1 V value per cell and then doing the expensive argmax computation.

Professor's summary: "If I compute 4 Q values for each cell in place of computing 1 V value, I can make a comparison among the four and take the best, and I'm done. If I just compute V, for each action I need to look at for each state outcomes — a big job."

6.12.3 The $Q^{*} (s, a)$ Expression

$Q^{*}$ Bellman Optimality Equation:

The $Q^{*}$ expression is derived from $V^{*}$ by "flipping" the expression. The Bellman optimality for $V^{*}$ is:

$V^{*} (s) = a max s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{*} (s^{'})]$

For $Q^{*}$ , we want the value of taking action a in state s:

$Q^{*} (s, a) = s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ a^{'} max Q^{*} (s^{'}, a^{'})]$

The key difference: Instead of

V^{*} (s^{'})

inside the expression, we write

max_{a^{'}} Q^{*} (s^{'}, a^{'})

. This is because the value of the next state s' under the optimal policy equals the maximum Q value over all actions from s'. Symbol breakdown:

$Q^{*} (s, a)$ — the optimal value of taking action a in state s (how good this state-action pair is)
$max_{a^{'}} Q^{*} (s^{'}, a^{'})$ — the best Q-value from the next state s' (replaces $V^{*} (s^{'})$ )
$P (s^{'} ∣ s, a)$ — probability of transitioning to s' from s via action a
$R (s, a, s^{'})$ — immediate reward
$γ$ — discount factor

Professor's verbal description: "You take action a from state s. There could be multiple outcomes. For each outcome, what is the probability multiplied by the immediate reward plus gamma times the value of the next state. But you don't have V, you write it in terms of Q. Value of s' is max over all outgoing actions from s'."

6.12.4 Worked Example: $Q^{*}$ Computation

Worked Example: Computing $Q^{*} (s, right)$ Setup: State s, state s'. Taking action "right" from s leads to s' deterministically (probability 1). The immediate reward is 0. Assume

γ = 0.9

The four outgoing Q values from s' are:

$Q^{*} (s^{'}, up)$ = 0.85
$Q^{*} (s^{'}, down)$ = 0.60
$Q^{*} (s^{'}, left)$ = 0.40
$Q^{*} (s^{'}, right)$ = 0.70

Computation:

1. $max_{a^{'}} Q^{*} (s^{'}, a^{'}) = max (0.85, 0.60, 0.40, 0.70) = 0.85$ (action "up")

2. $Q^{*} (s, right) = R (s, right, s^{'}) + γ max_{a^{'}} Q^{*} (s^{'}, a^{'}) = 0 + 0.9 \times 0.85 = 0.765$

Sense-check:

Q^{*} (s, right)

= 0.765. This makes sense: taking "right" from s leads to s' with reward 0, and from s' the best you can do is

Q^{*} (s^{'}, up)

= 0.85, discounted by 0.9. The value is 0.9 × 0.85 = 0.765.

Q: "We have three terms associated with

Q^{*} (s, a)

— the reward, the gamma times max part, and the probability. The example only shows the R + gamma × max part. Where does the probability get multiplied?" A: The probability is always there. In the example, the probability of going from s to s' by taking action "right" was assumed to be 1, so it does not visibly appear. In the race car example, when taking the slow action from warm, there are two outcomes each with probability 0.5 — those probabilities explicitly appear. The general expression always multiplies by

P (s^{'} ∣ s, a)

; in simple examples where the action deterministically leads to one state, P = 1.

6.12.5 Model-Based vs Model-Free Q-Learning

Scope: Model-Based vs Model-Free Q-Learning:

The professor emphasized an important distinction: the Q-learning described above is model-based. "What we are actually doing is model-based learning. Aren't we? My computation of values and using values to extract policy all happens only if I have a model. The P function — the transition probability — is at the heart of all those expressions. Without this P, you don't have dynamic programming."

This Q-learning is based on the model and is not the popular form of Q-learning. The $Q^{*}$ expression works when you have the model. The professor noted: "In Reinforcement Learning, you would encounter the term Q-learning in two different places. This is the first place. This way of computing Q is not very popular. We don't really use model-based Q-learning much."

The second, more common form of Q-learning — model-free Q-learning — will be covered later in the course. Model-free Q-learning learns Q-values directly from experience (interacting with the environment) without needing the transition function P.

For now, the professor's advice: "Understand this Q-learning, understand the use of this expression, be able to answer if I give you some values — be able to plug in this expression and find the values. Don't sweat so much."

Recap:

Q^{*} (s, a)

is the optimal value of taking action a in state s. It replaces

V^{*} (s^{'})

with

max_{a^{'}} Q^{*} (s^{'}, a^{'})

in the Bellman equation. Q-values simplify policy extraction from

O (∣ S ∣^{2} ∣ A ∣)

to O(SA). This is the model-based form of Q-learning — the model-free form will come later.

Bridge: Now that we understand the fundamental DP methods and their limitations, let's examine what problems these methods face in practice.

Key Distinction: Model-Based vs Model-Free Q-Learning

This section covers Q-learning in the model-based setting. The model-based Q-learning expression $Q^{*} (s, a)$ works when you have the transition model P. The model-free Q-learning approach, which learns from experience without a model, will be covered later in the course.

Key concepts covered in this section:

Q-learning model-based expression $Q^{*} (s, a)$
Worked example computing $Q^{*}$ values with real numbers
Model-free distinction explained (covered in detail later in course)

6.13 Problems with Dynamic Programming / Value Iteration

6.13.1 Limitations

Hook: DP methods give us exact optimal policies — so why aren't they used everywhere? Because they require something we usually don't have: a perfect model of the environment. And even when we have the model, the computation can be prohibitive.

Limitations of Dynamic Programming / Value Iteration:

Slow algorithm — $O (∣ S ∣^{2} ∣ A ∣)$ per iteration. For problems with billions of states or millions of actions, this is infeasible.

Policy extraction is expensive — $O (∣ S ∣^{2} ∣ A ∣)$ . Computing the optimal policy from converged values requires significant additional work.

Policy converges long before values. This means the stopping criteria might waste computation.

Requires full knowledge of the model and reward function. "MDP, dynamic programming — if you want to use dynamic programming, you need a model. The model will tell you how the world works. You don't actually have to interact with the environment to learn the policy." This is why DP methods are called planning algorithms — they plan the optimal behavior using the model without actually interacting with the environment.

Offline optimization, not online. "You are actually doing an offline optimization, not an online optimization."

Requires discrete, finite actions. "This idea is completely not feasible in larger state spaces."

Intuition: DP methods are like solving a maze with a perfect map. You can find the optimal path without ever entering the maze — just compute it on paper. But what if you don't have a map? What if you have to learn by walking through the maze? That's the model-free setting, which is the focus of the rest of the course.

Scope: These limitations are inherent to the DP framework:

Limitations 1–3 (computational) can be partially addressed by asynchronous methods, better hardware, or approximation
Limitation 4 (model requirement) is the fundamental barrier — in most real-world problems, the model is unknown or imprecise
Limitation 5 (offline) means DP cannot adapt to a changing environment
Limitation 6 (discrete actions) requires discretization for continuous action spaces, which introduces approximation error

Recap: DP methods are powerful but limited: they require a perfect model (the transition function P and reward function R), have

O (∣ S ∣^{2} ∣ A ∣)

computational cost, and work only with discrete, finite state and action spaces. These limitations motivate the model-free methods covered in the rest of the course.

Bridge: Let's see a real-world case study where DP was successfully applied — diabetes treatment optimization — to understand when DP methods are practical.

6.14 Diabetes Treatment as an MDP: Case Study

6.14.1 Case Study Overview & Sequential Decision Problem

Hook: Can Dynamic Programming save lives? In chronic disease management (such as Type 2 diabetes), medical treatment decisions are not one-time classification problems. They are repeated, sequential decisions over time. A medication initiated now reduces future risk of cardiovascular complications like coronary heart disease (CHD) or stroke, but incurs immediate medication cost, burden, and side effects. Dynamic Programming computes an optimal, state-dependent clinical treatment policy by weighing immediate costs against long-term health values.

This case study is based on the landmark paper by Steimle and Denton (2017): Markov Decision Processes for Screening and Treatment of Chronic Diseases (with related work by Mason et al., 2014). It formulates repeated medication initiation as a finite-horizon Markov Decision Process (MDP).

Sequential Decision Question: At each periodic clinical epoch (e.g., annual review), given the patient's current metabolic state and medication history, which medication decision (if any) should be initiated so that long-term expected quality-adjusted health outcome is maximized?

6.14.2 Detailed MDP Formulation

The chronic disease treatment decision is formalized as a finite-horizon MDP: $(S, A, P, R, γ)$ .

1. Decision Epochs & Horizon:

Decision points occur periodically (e.g., annual clinical reviews) over a finite planning horizon $t = 0, 1, 2, \dots, N$ , representing the patient's lifetime or long-term management period.

2. State Space ( $S = S_{L} \cup S_{D}$ ):

The state space is partitioned into living states ( $S_{L}$ ) and absorbing event/terminal states ( $S_{D}$ ):

Detailed Living State ( $s \in S_{L}$ ): $s = (T C, H D L, S B P, m_{1}, m_{2}, \dots, m_{M})$ , where $T C$ is total cholesterol category, $H D L$ is HDL cholesterol category, $S B P$ is systolic blood pressure category, and $m_{i} \in {0, 1}$ records whether medication $i$ has already been initiated.
Compact Explanatory Living State: $s = (risk level, cholesterol-med status, BP-med status)$ , with $risk level \in {Low, Medium, High}$ .
Absorbing Event States ( $S_{D}$ ): Includes major event states like CHD event ( $d_{C}$ ), stroke event ( $d_{S}$ ), and death from other causes ( $d_{O}$ ). Once entered, the patient remains in $S_{D}$ with no further decision-making.

3. Action Space & State-Dependent Action Sets ( $A (s)$ ):

Actions represent medication initiation choices: $A = {Start none, Start cholesterol med, Start BP med, Start both}$ .

Critical constraint: The action set $A (s)$ is state-dependent to prevent unrealistic repeated initiation of a drug already being taken:

Current Medication Status	Feasible Action Set $A (s)$
No medication started	Start none, Start cholesterol med, Start BP med, Start both
Cholesterol med already started	Start none, Start BP med
BP med already started	Start none, Start cholesterol med
Both medication groups started	Start none

4. Transition Probabilities ( $P_{t} (j ∣ s, a_{t})$ ):

Let $p_{t}^{S} (s, a_{t})$ be the age/state-dependent stroke probability, $p_{t}^{C} (s, a_{t})$ the CHD probability, and $p_{t}^{O}$ the probability of death from other causes. The transition kernel is defined piecewise:

$P_{t} (j ∣ s, a_{t}) = ⎩ ⎨ ⎧ [1 - p_{t}^{S} (s, a_{t}) - p_{t}^{C} (s, a_{t}) - p_{t}^{O}] p (j ∣ s), p_{t}^{S} (s, a_{t}), p_{t}^{C} (s, a_{t}), p_{t}^{O}, 1, 0, s, j \in S_{L} j = d_{S}, s \in S_{L} j = d_{C}, s \in S_{L} j = d_{O}, s \in S_{L} s = j, s \in S_{D} otherwise$

5. Reward Function ( $R_{t} (s, a, j)$ ):

The reward reflects Quality-Adjusted Life Years (QALYs), treatment costs, side effects, and event penalties:

$R_{t} (s, a, j) = QALY (s, j) - λ \cdot MedicationCost (a) - EventPenalty (j)$

Illustrative numerical breakdown:

Survive 1 year without major event: +1.0
Medication cost/burden for Start C: -0.03
Medication cost/burden for Start B: -0.03
Medication cost/burden for Start Both: -0.06
CHD or Stroke event penalty: -5.0
Death: 0 continuation value

6. Objective:

Find optimal policy $π_{t}^{*} (s)$ maximizing long-term expected discounted reward with discount factor $γ \approx 1.0$ (since long-term health outcomes are clinically critical):

$V_{t}^{*} (s) = π max E [k = t \sum N γ^{k - t} R_{k} (S_{k}, A_{k}, S_{k + 1}) S_{t} = s]$

6.14.3 Solving the MDP via Dynamic Programming Algorithms

1. Backward Dynamic Programming (Finite Horizon):

Initialized with terminal value $V_{N} (s) = 0$ for all states. For $t = N - 1, N - 2, \dots, 0$ , Bellman backups are computed backward in time:

$V_{t} (s) = a \in A (s) max j \in S \sum P_{t} (j ∣ s, a) [R_{t} (s, a, j) + γ V_{t + 1} (j)]$

Optimal policy selection: $π_{t}^{*} (s) = ar g max_{a \in A (s)} \sum_{j \in S} P_{t} (j ∣ s, a) [R_{t} (s, a, j) + γ V_{t + 1} (j)]$ . Output is an age- and state-dependent decision table.

2. Value Iteration View (Stationary Discounted MDP):

Repeatedly applies Bellman optimality backup $V_{k + 1} (s) = max_{a \in A (s)} \sum_{j \in S} P (j ∣ s, a) [R (s, a, j) + γ V_{k} (j)]$ until $Δ = max_{s} ∣ V_{k + 1} (s) - V_{k} (s) ∣ < θ$ .

3. Policy Iteration View (Stationary Model):

Step 1 (Initialize): Start with baseline clinical guideline (e.g., no med for low risk, 1 med for medium risk, both for high risk).
Step 2 (Policy Evaluation): Solve $V^{π} (s) = \sum_{j \in S} P (j ∣ s, π (s)) [R (s, π (s), j) + γ V^{π} (j)]$ .
Step 3 (Policy Improvement): Extract $π_{new} (s) = ar g max_{a \in A (s)} \sum_{j \in S} P (j ∣ s, a) [R (s, a, j) + γ V^{π} (j)]$ .
Step 4 (Iterate): Repeat until policy $π$ stabilizes.

6.14.4 Optimal Policy Output & Interpretation

Illustrative Optimal Policy Table:

Patient State	Optimal Action $π^{*} (s)$	Clinical Rationale
Low risk, no medication	Wait (Start none)	Event risk reduction does not justify immediate medication cost/burden.
Medium risk, no medication	Start cholesterol medication	Targeted risk reduction balances treatment burden.
High risk, no medication	Start both medications	High immediate cost is offset by major reduction in high event loss (-5.0).
High risk, cholesterol med started	Start BP medication	Adds secondary prevention to control remaining elevated risk.
Absorbing event state ( $S_{D}$ )	No further initiation decision	Terminal state / decision process ends.

Practical Limitations & Clinical Cautions:

Transition Probability Estimation: Probabilities are estimated from epidemiological models and clinical trials; they are subject to statistical uncertainty.
Discretization Loss: Continuous medical parameters (e.g., blood pressure, cholesterol levels) must be discretized, which may lose fine-grained diagnostic information.
Imperfect Medication Adherence: Real patients may forget or skip doses, degrading real-world effectiveness relative to model assumptions.
Heterogeneous Patient Preferences & Side Effects: Individual tolerance and quality-of-life impact vary across patients.
Decision Support, Not Automated Physician Replacement: DP models serve as decision support tools to guide clinicians, not autonomous medical decision makers.

Case Study Review Questions:

Identify the state, action, transition probability, and reward components in the Type 2 diabetes treatment MDP.
Why is chronic disease medication a sequential decision problem rather than a standard one-step classification problem?
Write the Bellman optimality equation for the finite-horizon chronic treatment problem.
Explain how an action with a small immediate negative reward (medication cost/side effect) can have a higher long-term expected value.
Compare value iteration and policy iteration when solving stationary chronic treatment decision models.

Recap: The diabetes case study proves DP's real-world power: by modeling patient health as an MDP, Bellman backups compute personalized, risk-dependent medication strategies that maximize long-term QALYs while penalizing treatment burden and severe cardiovascular events.

Bridge: This case study illustrates the broader principle: DP methods are planning algorithms that work when you have a model. What happens when you don't have a model?

6.15 Planning Algorithms and the Model-Based Paradigm

6.15.1 Planning vs Learning: The Model-Based Paradigm

Hook: We've spent this entire lecture computing optimal policies on paper. But what if you don't have a model? What if you only have experience — a history of interactions with the environment? This question defines the boundary between planning and learning.

Planning vs Learning: Planning (Model-Based): If you have a model (the transition function P and reward function R), you can compute the optimal policy entirely on paper. You do not need to interact with the environment at all. The model perfectly simulates the environment. All DP algorithms (value iteration, policy iteration) are planning algorithms.

"Even without getting into the real environment and interacting with aspects, on paper I can find out what is the optimal way of working. People would call these planning algorithms."

Learning (Model-Free): If the model is NOT available, you must learn from experience — by interacting with the environment, observing transitions and rewards, and building up value estimates from samples. This is the domain of model-free RL methods (Monte Carlo, TD learning, Q-learning).

Worked Example: Planning vs Learning in Practice Planning scenario: You want to find the fastest route through a city. You have a complete map with all roads, distances, and speed limits. You can compute the optimal route entirely on your computer without driving. Learning scenario: You are dropped in an unfamiliar city with no map. You must explore by walking, learning which streets connect where, and gradually discovering the fastest route through trial and error.

DP methods = planning (have the map). Model-free methods = learning (no map, must explore).

Intuition: The professor's question — "What if the model is not available? What if only the details of past interactions are available?" — is the central motivation for the rest of the course. Everything from here forward addresses how to learn optimal behavior without a model, using only experience.

Scope: The distinction between planning and learning is fundamental:

Planning requires a model; learning does not
Planning can be done offline; learning requires interaction
Planning gives exact answers (given exact model); learning gives approximate answers
In practice, many systems combine both: use a learned model for planning, or use planning to improve sample efficiency

Recap: All algorithms in this lecture (value iteration, policy iteration) are planning algorithms — they require a model (P and R) and compute optimal policies without environment interaction. The model-free paradigm, where the agent learns from experience alone, is the focus of subsequent lectures.

Bridge: This lecture completes the DP foundation. The next lectures will explore model-free methods — Monte Carlo, Temporal Difference learning, and Q-learning — that learn optimal policies by interacting with the environment.

Exam Guidance Summary

Value iteration with the race car example is the primary exam problem format. "The problem can come in multiple flavors" — verbatim understanding of the algorithm and the ability to apply it in different ways is necessary.
In-place vs not-in-place algorithm: "This is very, very important stuff that you must understand. Whenever you solve a problem, if the question asked is in-place update or not-in-place update, I think you should be very careful." For in-place, show that at every step the most recent values are used.
Policy extraction is a required skill: after computing values, extract the deterministic policy by computing argmax over actions.
Policy evaluation: Be able to run Bellman expected update for a given fixed policy and show the values converging.
Policy iteration: Know the algorithm (initialize policy, evaluate, improve, repeat until stable).
Q-learning expressions: Be able to plug in values and compute $Q^{*} (s, a)$ . The professor said: "Be able to answer if I give you some values, be able to plug in this expression and find the values."
Policy improvement theorem: "I may not even ask you to recite this theorem, but I want you to go through it."
S vs S+ distinction: Write algorithms for S+ (all states including terminal) in exams. Verify that terminal states retain value 0 through iteration.
Computational complexity: Understand why value iteration is $O (∣ S ∣^{2} ∣ A ∣)$ — be able to explain the reasoning.
Generalized Policy Iteration: Understand the evaluate-improve cycle as a general framework.
Study advice: "Spend a lot of time on the lecture notes. Lecture notes plus actual lectures should give a lot of insights." Pick 3-4 problems from the textbook, try to solve them, and share scribbles for discussion.

Key Industry Applications

Diabetes treatment optimization using MDPs and dynamic programming — a research paper modeling Type 2 diabetes medication decisions as an MDP with states representing medical risk and medication history, actions being medication choices, and rewards based on Quality Adjusted Life Years.
MDP planning algorithms are used in any domain where the environment model is known — robotics (known physics), game playing (known rules), resource allocation (known constraints).
Transition probabilities from domain expertise: In healthcare and other domains, the model dynamics (P function) come from clinical data and expert knowledge rather than being perfectly known.

References & Further Reading

Steimle, L. N., and Denton, B. T. (2017). Markov Decision Processes for Screening and Treatment of Chronic Diseases. In Markov Decision Processes in Practice, Springer, pp. 189–222. Paper Link
Mason, J. E., Denton, B. T., Shah, N. D., and Smith, S. A. (2014). Optimizing the simultaneous management of blood pressure and cholesterol for type 2 diabetes patients. European Journal of Operational Research, 233(3), 727–738.
Sutton, R. S., and Barto, A. G. (2018). Reinforcement Learning: An Introduction, 2nd edition. MIT Press. Chapter 4: Dynamic Programming.

DRL Lecture 6 Notes · Dynamic Programming — Value Iteration, Policy Iteration, and Q-Learning

Deep Reinforcement Learning· postgraduate· 2026-07-21

Sections Breakdown

16.1 Review: MDP and Bellman Equations

Reviews MDP framework and Bellman equations

26.2 Value Iteration

Algorithm and race car example

36.3 In-Place vs Not-In-Place Value Iteration

Two variants of value iteration

46.4 Policy Extraction from Value Iteration

Extracting deterministic policy from $V^*$

56.5 Policy Evaluation

Computing V^pi for a fixed policy

66.6 Policy Improvement

Greedy policy improvement theorem

76.7 Generalized Policy Iteration

Evaluate-improve cycle framework

86.8 Policy Iteration Algorithm

Full evaluation + improvement loop

96.9 Value Iteration vs Policy Iteration

Convergence and comparison

106.10 Computational Complexity

O(S^2 A) per iteration

116.11 Asynchronous Value Iteration

Priority queue approach

126.12 Q-Learning in Model-Based Setting

$Q^*(s,a)$ expression and computation

136.13 Problems with DP

Limitations motivating model-free methods

146.14 Diabetes Treatment Case Study

Finite-horizon MDP formulation, state-dependent action sets, piecewise transitions, QALY rewards, and backward DP/VI/PI algorithms for chronic disease treatment

156.15 Planning Algorithms

Model-based paradigm vs learning

Postgraduate students in Deep Reinforcement Learning

Exam Revision Notes

Below is the distilled, exam-ready core. Every entry comes from the full explanation above. Use this section for rapid review; return to the main notes when a point needs more context.

MDP and Bellman Equations Review

Must-know: Bellman expected update uses $\sum_{a} π (a ∣ s)$ to average over policy; Bellman optimality uses $max_{a}$ to pick the best action. $V^{π} (s)$ evaluates a policy; $V^{*} (s)$ finds the optimal value.

$V^{π} (s) = a \sum π (a ∣ s) s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{π} (s^{'})]$

⚠️ Top pitfall: Confusing $V^{π}$ (value under a specific policy) with $V^{*}$ (value under the optimal policy).

Self-check: What is the only difference between the Bellman expected update equation and the Bellman optimality equation?

Connects to: 6.2, 6.5

Value Iteration — Algorithm and Race Car Example

Must-know: Value iteration: start with V0=0, repeatedly apply $V_{k + 1} (s) = max_{a} \sum_{s^{'}} P (s^{'} ∣ s, a) [R + γ V_{k} (s^{'})]$ until convergence. Terminal states stay at 0.

$V_{k + 1} (s) = a max s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V_{k} (s^{'})]$

⚠️ Top pitfall: Using updated values within the same sweep (in-place) vs using previous iteration values (standard).

Self-check: In the race car example, what is V1(cool) after sweep 1 if $γ = 0.9$ and all $V_{0} = 0$ ?

Connects to: 6.1, 6.3, 6.4

In-Place vs Not-In-Place Value Iteration

Must-know: In-place uses most recent values (Gauss-Seidel style); not-in-place uses previous iteration values (Jacobi style). Both converge to same $V^{*}$ . Exam: explicitly show which version you're using.

⚠️ Top pitfall: Confusing in-place with not-in-place in exams. In-place = use updated values immediately; not-in-place = use only previous iteration values.

Self-check: What is the key difference between in-place and not-in-place value iteration?

Connects to: 6.2

Policy Extraction from Value Iteration

Must-know: Policy extraction: $π (s) = ar g max_{a} \sum_{s^{'}} P (s^{'} ∣ s, a) [R + γ V^{*} (s^{'})]$ . Result is deterministic $π (s) = a$ , not probabilities.

$π (s) = ar g a max s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{*} (s^{'})]$

⚠️ Top pitfall: Confusing argmax (which action achieves max) with max (the max value itself). Writing $π (a ∣ s)$ =probability instead of $π (s)$ =a.

Self-check: What is the optimal policy for cool and warm in the race car example with converged values V(cool)=3.35, V(warm)=2.35?

Connects to: 6.2, 6.5

Policy Evaluation

Must-know: Policy evaluation: $V^{π} (s) = \sum_{a} π (a ∣ s) \sum_{s^{'}} P (s^{'} ∣ s, a) [R + γ V^{π} (s^{'})]$ . Uses expected update (average per policy), NOT max. Same MDP, different policies → different values.

$V^{π} (s) = a \sum π (a ∣ s) s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{π} (s^{'})]$

⚠️ Top pitfall: Using max instead of expected update (that's value iteration, not policy evaluation). Forgetting to keep policy fixed during evaluation.

Self-check: In the 5-state grid, why are all values negative under the left-biased policy?

Connects to: 6.1, 6.6

Policy Improvement

Must-know: Policy improvement: $π^{'} (s) = ar g max_{a} \sum_{s^{'}} P (s^{'} ∣ s, a) [R + γ V^{π} (s^{'})]$ . Guaranteed to be at least as good as $π$ . Requires re-evaluation before next improvement.

$π^{'} (s) = ar g a max s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ V^{π} (s^{'})]$

⚠️ Top pitfall: Not re-evaluating the policy after improvement. Old $V^{π}$ is invalid for the new policy.

Self-check: What does the policy improvement theorem guarantee about the new greedy policy?

Connects to: 6.5, 6.7

Generalized Policy Iteration (GPI)

Must-know: GPI: alternate policy evaluation (V → $V^{π}$ ) and policy improvement ( $π \to greedy (V)$ ) until stable. Different algorithms vary the granularity of evaluation.

⚠️ Top pitfall: Thinking GPI is one specific algorithm. It's a framework — policy iteration and value iteration are both instances.

Self-check: What is the difference between policy iteration and value iteration in terms of GPI?

Connects to: 6.6, 6.8

Policy Iteration Algorithm

Must-know: Policy iteration: initialize $π$ , evaluate $V^{π}$ fully, improve greedily, repeat until $π$ stable. Converges in fewer iterations than value iteration but each iteration is more expensive.

⚠️ Top pitfall: Truncating policy evaluation (that's no longer policy iteration). Not checking policy stability as stopping condition.

Self-check: What is the stopping condition for policy iteration?

Connects to: 6.7, 6.9

Value Iteration vs Policy Iteration Comparison

Must-know: Policy converges before values in value iteration. Value iteration = cheap iterations, many of them. Policy iteration = expensive iterations, few of them. Professor prefers value iteration for practical speed.

⚠️ Top pitfall: Assuming fewer iterations (policy iteration) means faster. Each policy iteration runs full evaluation.

Self-check: Why might value iteration be preferred over policy iteration in practice?

Connects to: 6.2, 6.8, 6.10

Computational Complexity of Value Iteration

Must-know: $O (∣ S ∣^{2} ∣ A ∣)$ per iteration: for each state (S), evaluate each action (A), sum over all possible next states (S). Be able to explain this derivation.

⚠️ Top pitfall: Confusing per-iteration cost ( $O (∣ S ∣^{2} ∣ A ∣)$ ) with total cost (O(S²A × #iterations)).

Self-check: Why is value iteration $O (∣ S ∣^{2} ∣ A ∣)$ per iteration?

Connects to: 6.2, 6.11

Asynchronous Value Iteration

Must-know: Asynchronous VI uses a priority queue to update states with largest expected changes first. Converges if all states are updated infinitely often.

⚠️ Top pitfall: Thinking it reduces total computation — it focuses computation but doesn't reduce the total amount needed.

Self-check: What is the key advantage of asynchronous value iteration over standard value iteration?

Connects to: 6.10, 6.12

Q-Learning in the Model-Based Setting

Must-know: $Q^{*} (s, a) = \sum_{s^{'}} P (s^{'} ∣ s, a) [R + γ max_{a^{'}} Q^{*} (s^{'}, a^{'})]$ . Plug in values and compute. Model-based (requires P). Model-free form comes later.

$Q^{*} (s, a) = s^{'} \sum P (s^{'} ∣ s, a) [R (s, a, s^{'}) + γ a^{'} max Q^{*} (s^{'}, a^{'})]$

⚠️ Top pitfall: Forgetting $P (s^{'} ∣ s, a)$ in the expression (it's 1 in simple examples but must appear in general). Confusing model-based Q-learning with model-free Q-learning.

Self-check: Compute $Q^{*} (s, right)$ if $P (s^{'} ∣ s, right) = 1$ , $R = 0$ , $γ = 0.9$ , and $max_{a^{'}} Q^{*} (s^{'}, a^{'}) = 0.85$ .

Connects to: 6.1, 6.13

Problems with DP / Value Iteration

Must-know: 6 limitations: $O (∣ S ∣^{2} ∣ A ∣)$ cost, expensive extraction, policy converges before values, requires full model, offline only, discrete actions only. DP = planning algorithms (no environment interaction needed).

⚠️ Top pitfall: Forgetting that DP requires a model. Confusing planning (model-based) with learning (model-free).

Self-check: Why are DP methods called 'planning algorithms'?

Connects to: 6.10, 6.14

Diabetes Treatment as an MDP: Case Study

Must-know: Diabetes MDP: states = medical indicators + medication history, actions = medication choices, rewards = QALY. Transition probabilities from domain expertise, not exact.

⚠️ Top pitfall: Assuming transition probabilities in real-world MDPs are exactly known. They are estimates from clinical data.

Self-check: What is the reward function in the diabetes treatment MDP based on?

Connects to: 6.13, 6.15

Planning Algorithms and the Model-Based Paradigm

Must-know: DP = planning algorithms (require model, no environment interaction). Model-free = learning algorithms (no model, learn from experience). This distinction drives the rest of the course.

⚠️ Top pitfall: Confusing planning (model-based) with learning (model-free). DP requires a model; if you don't have one, you need model-free methods.

Self-check: What distinguishes a planning algorithm from a learning algorithm in RL?

Connects to: 6.13

Previous LectureLecture 05 · Markov Decision Processes and Dynamic Programming

Next LectureLecture 07 · Monte Carlo Methods

Was this lecture useful?

Loading comments…

🤖

BitsNotes AI Assistant

Subject Notes Assistant

Configure AI Chat

Choose how to access the chatbot

Have your own API key?

Switch to "Bring Your Own Key" tab above for unlimited access with any OpenAI-compatible provider.

AI Provider Preset

API Endpoint URL (OpenAI-Compatible)

API Key

Model Name

🔑 Enter API key above to fetch live models from provider, or enter model name manually.

Remember key for this session (until tab closes)

OpenAI-Compatible API Support

Choose any provider preset (Gemini, DeepSeek, Kimi, GLM, MiniMax, Qwen, OpenAI, Groq, Ollama, etc.) or enter a custom endpoint URL.

Security & Privacy First

Your API key is sent directly from your browser to your specified provider. BitsNotes servers never store or see your key.

Prerequisite Knowledge

Previously Covered in This Subject

6.1 Review: MDP and Bellman Equations

6.1.1 MDP Framework and Bellman Equations

6.2 Value Iteration — Algorithm and Race Car Example

6.2.1 Symbol Registry — Value Iteration

6.2.2 The Race Car MDP

Race Car MDP — State Transition Diagram

Interactive Value Iteration Workbench

6.2.3 Value Iteration Algorithm

6.2.4 Worked Example: Race Car Value Iteration (Sweep 1)

6.3 In-Place vs Not-In-Place Value Iteration

6.3.1 The Two Variants

6.4 Policy Extraction from Value Iteration

6.4.1 Symbol Registry — Policy Extraction

6.4.2 Extracting the Policy

6.5 Policy Evaluation

6.5.1 Definition and Intuition

6.5.2 Policy Evaluation Formula

6.5.3 Policy Evaluation Algorithm

Iterative Policy Evaluation Algorithm

6.5.4 Worked Example: 5-State Grid Problem

Worked Example: 5-State Grid Policy Evaluation

Scenario 1: Left-Biased Policy (π(L)=0.8,π(R)=0.2)

Scenario 2: Right-Biased Policy (π(L)=0.2,π(R)=0.8)

Scenario 3: Equal Policy (π(L)=0.5,π(R)=0.5)

Policy Comparison Matrix

6.6 Policy Improvement

6.6.1 Greedy Policy Improvement

6.7 Generalized Policy Iteration (GPI)

6.7.1 The Evaluate-Improve Cycle

6.8 Policy Iteration Algorithm

6.8.1 Algorithm Steps

6.9 Value Iteration vs Policy Iteration: Convergence and Comparison

6.9.1 The Policy-Convergence-Before-Values Observation

6.9.2 Value Iteration Versus Policy Iteration: Which Is Better?

6.10 Computational Complexity of Value Iteration

6.10.1 Why O(∣S∣2∣A∣) Per Iteration

6.11 Asynchronous Value Iteration

6.11.1 Priority Queue Approach

6.12 Q-Learning in the Model-Based Setting

6.12.1 Symbol Registry — Q-Learning

6.12.2 Motivation: Why Q Values Instead of V Values?

6.12.3 The Q∗(s,a) Expression

6.12.4 Worked Example: Q∗ Computation

6.12.5 Model-Based vs Model-Free Q-Learning

Key Distinction: Model-Based vs Model-Free Q-Learning

6.13 Problems with Dynamic Programming / Value Iteration

6.13.1 Limitations

6.14 Diabetes Treatment as an MDP: Case Study

6.14.1 Case Study Overview & Sequential Decision Problem

6.14.2 Detailed MDP Formulation

6.14.3 Solving the MDP via Dynamic Programming Algorithms

6.14.4 Optimal Policy Output & Interpretation

6.15 Planning Algorithms and the Model-Based Paradigm

6.15.1 Planning vs Learning: The Model-Based Paradigm

Exam Guidance Summary

Key Industry Applications

References & Further Reading

DRL Lecture 6 Notes · Dynamic Programming — Value Iteration, Policy Iteration, and Q-Learning

Sections Breakdown

Exam Revision Notes

MDP and Bellman Equations Review

Value Iteration — Algorithm and Race Car Example

In-Place vs Not-In-Place Value Iteration

Policy Extraction from Value Iteration

Policy Evaluation

Policy Improvement

Generalized Policy Iteration (GPI)

Policy Iteration Algorithm

Value Iteration vs Policy Iteration Comparison

Computational Complexity of Value Iteration

Asynchronous Value Iteration

Q-Learning in the Model-Based Setting

Problems with DP / Value Iteration

Diabetes Treatment as an MDP: Case Study

Planning Algorithms and the Model-Based Paradigm

Was this lecture useful?

BitsNotes AI Assistant

Configure AI Chat

Scenario 1: Left-Biased Policy ( $π (L) = 0.8, π (R) = 0.2$ )

Scenario 2: Right-Biased Policy ( $π (L) = 0.2, π (R) = 0.8$ )

Scenario 3: Equal Policy ( $π (L) = 0.5, π (R) = 0.5$ )

6.10.1 Why $O (∣ S ∣^{2} ∣ A ∣)$ Per Iteration

6.12.3 The $Q^{*} (s, a)$ Expression

6.12.4 Worked Example: $Q^{*}$ Computation