X1.2.2

Lesson 1.2.2 — Markov Decision Processes and Value Functions: The Formal Substrate of Every RL Algorithm

Week 7 · Prerequisites: 1.2.1, 1.1.1, 1.1.3, 0.3.1, 0.3.2.

Prior results used. This lesson uses 1.2.1’s ArmEnv (the reset/step contract, the observation/action spaces, the terminated/truncated distinction), 1.1.1’s FK and state representation, 1.1.3’s control loop, 0.3.1’s conditional expectations and Bayes’ rule, and 0.3.2’s log-likelihood and the optimization-as-MAP framing. Each is restated at the point of use.

Hands forward. This lesson hands forward one capability: the learner can formalize a robot control task as a Markov Decision Process, derive the Bellman expectation and optimality equations for its value functions, implement value iteration and policy iteration on a tabular version of the running case, prove that the Bellman operator is a γ-contraction (so value iteration converges geometrically), and diagnose the four MDP-level bugs (state aliasing, reward shaping that changes the optimal policy, discount-factor mismatch, and policy-evaluation non-convergence) from their learning symptoms — the capability that every RL lesson in Module 1.2 (REINFORCE, PPO, SAC, TD3) and every model-based lesson in Phase 2 assumes.

Running case. The same 6-DOF MuJoCo arm from 1.1.1–1.2.1, now discretized for the tabular algorithms: the state is (q₂, q₃) each quantized to 5 bins (25 states), the action is the torque on q₂ and q₃ each quantized to 3 values (−τ, 0, +τ, 9 actions), the transition is the simplified dynamics q_{t+1} = q_t + dt · q̇_t + ½ dt² τ / M with the quantized q, and the reward is the negative distance to the target. The lesson’s central result is that the MDP’s five components are the contract between the robot and the algorithm — the state determines what the policy can see, the reward determines what it optimizes, and the discount determines how far it looks — and the Bellman operator’s contraction is what makes the value iteration converge to the unique fixed point regardless of the initial value.

§L.0 — Lesson map, objectives, and misconceptions

§L.0.1 — Lesson map and word budget

§L.0.2 — Objectives

By the end of this lesson you will be able to do eight things:

1. State the MDP tuple (S, A, P, R, γ) and the Markov property, and map the running case’s ArmEnv onto each component.
2. State the return G_t = Σ_{k=0}^∞ γ^k r_{t+k} and the discount factor’s role (the time preference, the bounded return, and the convergence of the infinite sum), and compute G_t for a finite trajectory by hand.
3. State the policy π(a|s) (stochastic) and π(s) (deterministic), and derive the value functions V^π(s) = E_π[G_t | s_t = s] and Q^π(s, a) = E_π[G_t | s_t = s, a_t = a].
4. Write the Bellman expectation equations for V^π and Q^π, and solve them for a small MDP by linear algebra (V^π = (I − γP^π)⁻¹ r^π).
5. Write the Bellman optimality equations for V* and Q*, and derive the optimal policy π*(s) = argmax_a Q*(s, a).
6. Prove that the Bellman optimality operator T is a γ-contraction in the ∞-norm, and conclude that value iteration converges geometrically with rate γ.
7. Implement value iteration and policy iteration on the running case’s tabular MDP, and verify the convergence, the optimal policy, and the optimal value against the analytic solution for a small test case.
8. Diagnose the four MDP-level bugs — state aliasing (the state is not Markov, the policy confuses the aliased states), reward shaping that changes the optimal policy (the shaping is not policy-invariant), discount-factor mismatch (the training’s γ differs from the deployment’s horizon), and policy-evaluation non-convergence (the policy is not proper, the value diverges) — from their learning symptoms.

§L.0.3 — Misconception inventory

Each misconception is displaced in the section named, and each is tagged in the concept check that follows.

Everything is self-contained. Where a prerequisite lesson is used, the result is restated at the point of use.

§L.0.5 — Retrieval warm-up

This is the eighteenth lesson. The prompt requires drawing from lessons two to five steps back; 1.2.1 is one step back and is excluded. The warm-up draws from 1.1.4 (two steps back), 1.1.3 (three), 1.1.2 (four), and 1.1.1 (five).

Warm-up 1 (from 1.1.4, the pick-and-place pipeline). State the seven stages of the pick-and-place pipeline and the state machine’s transitions. Answer: the seven stages are perception, frame audit, IK, trajectory, control, state machine, error recovery; the transitions are the health checks (the tracking error, the gripper’s force, the object’s presence). How this is used: §L.1’s MDP’s state is the composition of the pipeline’s stages’ observable variables (the q, the q̇, the p_ee, the p_target), and the reward is the task’s success (the distance to the target), which is the same reward that the state machine’s health check uses.

Warm-up 2 (from 1.1.3, the PID). State the PID’s error dynamics under PD and the steady-state error under PD vs. PID. Answer: ë + 2ζω_n ė + ω_n² e = q̈_d; the PD’s steady-state error is Δ/K_p, and the PID’s is zero (the integral eliminates the constant disturbance). How this is used: §L.3’s value function V^π(s) is the expected return under the policy π, and the PID’s convergence (the error → 0) is the continuous analogue of the value iteration’s convergence (the value → the fixed point).

Warm-up 3 (from 1.1.2, the IK). State the 2-link arm’s IK and the branch choices. Answer: cos q₂ = (r² − a₁² − a₂²)/(2a₁a₂), q₂ = ± arccos, q₁ = atan2(y,x) − atan2(a₂ sin q₂, a₁ + a₂ cos q₂); the ± is the two branches. How this is used: §L.4’s policy iteration has the policy improvement step that chooses the best action for each state — the same “choose the best” structure as the IK’s branch selection (the closest to the current configuration), and the convergence of the iteration is the policy’s stabilization.

Warm-up 4 (from 1.1.1, the FK and the Jacobian). State the geometric Jacobian’s column for a revolute joint and the moment arm’s role. Answer: J_i = [ω_i; ω_i × (p_ee − q_i)], where the moment arm is the linear velocity contribution. How this is used: §L.1’s MDP’s state is the arm’s (q, q̇, p_ee, p_target), and the dynamics q̈ = M⁻¹(τ − C q̇ − g) are the environment’s transition P(s' | s, a), which is the Jacobian’s continuous analogue (the q̇’s linear response to the τ).

Part A — The MDP Tuple and the Policy

§L.1 — Objects: the five components, the Markov property, and the policy

A Markov Decision Process (MDP) is a tuple (S, A, P, R, γ):

• S — the state space (the set of possible states s).
• A — the action space (the set of possible actions a).
• P(s' | s, a) — the transition probability (the probability of reaching s' from s with a).
• R(s, a, s') — the reward (the immediate reward for the transition).
• γ ∈ [0, 1] — the discount factor (the time preference).

The Markov property is the assumption that the future is independent of the past given the current state:

The state is a sufficient statistic for the future, and the policy can be a function of the current state alone (the Markov policy π(a | s)), without the history (s_0, a_0, …, s_t).

A policy π is a distribution over the actions given the state:

• Stochastic π(a | s) — the probability of a given s.
• Deterministic π(s) — a single action for each state.

The policy’s role is the agent’s decision rule — the mapping from the state to the action that the agent chooses. The MDP is the environment’s model, and the policy is the agent’s choice; the value functions (Part B) are the expected returns under the policy, and the Bellman equations (Part C) are the recursive relationships that the value functions satisfy.

The ArmEnv’s MDP:

• S — the discretized (q₂, q₃) in 5 bins each (25 states), ignoring the q̇, the p_ee, and the p_target (the simplified state for the tabular algorithms).
• A — the discretized (τ₂, τ₃) ∈ {−τ, 0, +τ}² (9 actions).
• P — the simplified dynamics q_{t+1} = q_t + dt · q̇_t + ½ dt² τ / M with the quantized q and the zeroed q̇ (the position-controlled approximation).
• R — the negative distance −‖p_ee(q) − p_target‖.
• γ — the discount (0.99 for the long-horizon reaching, 0.9 for the short-horizon).

§L.1.1 — Result: the Markov property is the assumption that makes the MDP’s value functions well-defined, and the state aliasing is its violation

Claim. The MDP’s value functions V^π(s) and Q^π(s, a) are well-defined (the expectations are independent of the history) iff the Markov property holds. When the state is aliased (two distinct underlying states share the same observation), the policy that’s optimal for the aliased state is suboptimal for the individual underlying states, and the value function’s estimate is a mixture of the two states’ values.

Proof sketch. The value function’s definition is V^π(s) = E_π[G_t | s_t = s], where the expectation is over the future trajectories. The Markov property makes the future independent of the history given the s_t = s, so the expectation is the same for any history that leads to s. Without the Markov property, the future depends on the history, and the value is different for the same s with different histories — the value function is not a function of s alone, and the policy’s optimal action depends on the history, not just the current state.

Corollary. The state aliasing is the most common MDP bug — the ArmEnv’s state omits the q̇ (the velocity), and the true dynamics depend on the q̇; the aliased state (q₂, q₃) cannot distinguish the arm moving from the arm still, and the policy that’s optimal for the average (a mixture of the two) is suboptimal for both (the moving arm overshoots, the still arm undershoots).

Corollary. The fix is the state augmentation (the q̇ added to the state) or the belief state (the distribution over the underlying state, the POMDP’s solution). The state’s richness is the MDP’s design decision, and the aliasing’s cost is the suboptimality.

§L.1.2 — Worked-example ladder

WE-L.1.a — Fully worked: the running case’s MDP specification

Input. The running case’s ArmEnv, the discretized state and action, the target p_target = (0.5, 0.2), the discount γ = 0.99.

Trace (the state space).

1. The q₂, q₃ ∈ [−π/2, π/2], 5 bins each: {−π/2, −π/4, 0, π/4, π/2}.
2. The state is (i, j) with i, j ∈ {0, 1, 2, 3, 4} — 25 states.

Trace (the action space).

3. The τ₂, τ₃ ∈ {−0.5, 0, 0.5} — 3 values each, 9 actions.

Trace (the transition).

4. The simplified dynamics q_{t+1} = q_t + 0.1 τ / M with the quantization to the nearest bin.
5. The transition probability P(s' | s, a) is deterministic (the discrete approximation, one s' per (s, a) with probability 1).

Trace (the reward).

6. The R(s, a, s') = −‖p_ee(s') − p_target‖ — the negative distance.

Trace (the discount).

7. The γ = 0.99 — the long-horizon reaching.

Output and interpretation. The MDP is a 25-state, 9-action, deterministic process with the distance-based reward. The state’s small size makes the value iteration and the policy iteration exact (a table), and the optimal policy is a 25-entry table. The deterministic transition is a simplification (the real arm’s noise makes the transition stochastic), and the quantization is the aliasing’s source (the continuous q is approximated by the bins).

Self-explanation 1. Before reading on: in step 4, the transition is deterministic (the one s' per (s, a)). What does the Markov property require here, and what is the aliasing?

Answer. The Markov property requires the s' to be the only state that matters for the future, and the deterministic transition satisfies it trivially (the s' is a function of (s, a)). The aliasing is the quantization — two continuous q’s that round to the same bin are indistinguishable in the discrete state, and the future of the two is different in the continuous dynamics (the same bin, the different actual q), but the discrete MDP treats them as the same — the aliasing’s source.

Self-explanation 2. Before reading on: in step 7, the γ = 0.99 is chosen for the long-horizon reaching. What is the effective horizon, and how does it relate to the task’s duration?

Answer. The effective horizon is 1/(1 − γ) = 1/0.01 = 100 steps — the discount’s sum Σ γ^k weights the distant rewards, and the effective number of steps is ~100. The task’s duration (the time to reach) is ~50 steps at the small action’s 0.1-per-step’s 0.5 torque — the effective horizon (100) is larger than the duration (50), so the γ = 0.99 sees the whole task. A smaller γ = 0.9 (the horizon 10) would miss the distant rewards and the policy would short-sightedly satisfy the near-term only.

WE-L.1.b — Completion problem

Input. Same ArmEnv, but the state is augmented with the q̇ (the velocity), discretized to 3 bins each ({−, 0, +}).

Trace (final 25% as prompts).

1. The state space is now (q₂_bin, q₃_bin, q̇₂_bin, q̇₃_bin) — 5 × 5 × 3 × 3 = 225 states. ⟨your turn⟩
2. The transition P(s' | s, a) is no longer deterministic (the q̇’s dynamics make the s' depend on the q̇). ⟨your turn: why?⟩
3. The Markov property is better satisfied (the q̇ is part of the state). ⟨your turn⟩
4. The cost is the 225 states (the 9× larger), and the value iteration is slower (the 9× more). ⟨your turn⟩

Answers.

1. 225 states — the 4-dimensional (q₂, q₃, q̇₂, q̇₃).
2. The transition is stochastic because the q̇’s continuous value is quantized to the 3 bins, and the quantization’s uncertainty makes the next state’s probability spread across the bins.
3. The Markov property is better because the q̇’s presence gives the policy the velocity’s information, which the true dynamics depend on.
4. The 225 states (the 9× more) make the value iteration 9× slower (the table’s size), and the aliasing is reduced (the q̇’s bins are finer than the zero) — the trade-off between the state’s richness and the computation.

The lesson. The state augmentation reduces the aliasing and increases the state’s size — the trade-off is the exactness vs. the computation. The design’s choice depends on the task’s tolerance (the coarse state for the simple task, the fine state for the precision task) and the algorithm’s scalability (the tabular algorithms exponentially slow with the dimension, and the function approximation (the neural network, from 1.2.3) is the large state’s solution).

WE-L.1.c — Faded: the reward’s design

Setup. The same ArmEnv, but the reward is shaped with a progress term: R' = R + λ · (‖p_ee(s) − p_target‖ − ‖p_ee(s') − p_target‖) — the reward for moving closer to the target.

Question. Does the shaped reward change the optimal policy? What is the potential-based shaping’s invariance?

You must produce the intermediate steps. The setup and the answer are given.

Answer. The shaped reward R' = R + λ Φ(s) − λ Φ(s') with the potential Φ(s) = ‖p_ee(s) − p_target‖ is a potential-based shaping (the Φ’s difference is the shaping), and it preserves the optimal policy (the theorem: the potential-based shaping’s optimal policy is the same as the original’s). The reason: the shaping’s sum over the trajectory is telescoping (λ Φ(s_0) − λ Φ(s_T)), and the difference is the initial and the final potentials, which are independent of the intermediate actions — the optimal policy is unchanged.

The lesson. The potential-based shaping is the only shaping that provably preserves the optimal policy (the Ng, Harada, Russell’s theorem), and the other shaping (the arbitrary progress term, the penalty for the collisions, the bonus for the target) can change the optimal policy — the policy optimizes the shaped reward, which is not the original reward. The shaping’s design must be the potential-based form, or the policy is solving a different problem.

WE-L.1.d — Contrastive near-miss: the state aliasing’s suboptimality

Correct solution. The ArmEnv’s state is (q, q̇, p_ee, p_target) — the full state, with the velocity’s information.

Near-miss. The ArmEnv’s state is (q, p_ee, p_target) — the velocity omitted.

Why the near-miss produces a plausible but incorrect number. The policy trained on the velocity-less state cannot distinguish the arm moving toward the target (the q̇ > 0) from the arm still at the same q, and the optimal action is different for the two (the moving arm should decelerate, the still arm should accelerate). The policy learns the average (a small acceleration), which overshoots the moving case and undershoots the still case — the average reward is maximal, but the individual rewards are suboptimal. The symptom is the oscillation (the arm overshoots and corrects repeatedly) — the policy is fighting the velocity’s unobserved effect.

The discrepancy, stated. The full state’s V*(s) and the aliased state’s V*(s_alias) are different — the full state’s value is the max over the underlying states’ values, and the aliased state’s value is a mixture (the average of the underlying states’ values weighted by the stationary distribution). The aliased policy’s reward is lower than the full state’s, and the difference is the aliasing’s cost.

Self-explanation 3. Before reading on: in the near-miss, if the arm’s motion is slow (the q̇ ≈ 0), is the aliasing’s cost small?

Answer. Yes — the slow arm’s q̇ ≈ 0, and the velocity’s information is irrelevant (the two underlying states are nearly the same), so the aliasing’s cost is small. The fast arm’s q̇ is large, and the velocity’s information is essential — the aliasing’s cost is large. The aliasing’s severity depends on the velocity’s magnitude, and the slow tasks are forgiving of the aliasing.

Part B — Returns, Discounting, and Value Functions

§L.2 — Objects: the return, the discount, and the two value functions

The return from time t is the discounted sum of the future rewards:

The discount factor γ ∈ [0, 1] has three roles:

1. The time preference — a γ close to 1 weights the distant rewards almost as much as the near ones (the long-horizon task), and a γ close to 0 weights the near rewards much more (the short-sighted policy).
2. The bounded return — for γ < 1 and the bounded rewards |r| ≤ R_max, the return is bounded |G_t| ≤ R_max/(1 − γ), which makes the value functions finite.
3. The convergence of the infinite sum — for γ < 1, the geometric series Σ γ^k converges, and the infinite sum is well-defined. For γ = 1, the episodic tasks’ finite sum is fine, and the continuing tasks’ infinite sum is not (the γ = 1 is the average-reward setting, which is separate).

The value functions:

• The state-value V^π(s) = E_π[G_t | s_t = s] — the expected return from the state s under the policy π.
• The action-value Q^π(s, a) = E_π[G_t | s_t = s, a_t = a] — the expected return from the state-action pair (s, a) under the policy π (after the a, then following the π).

The relationship V^π(s) = Σ_a π(a | s) Q^π(s, a) — the state-value is the action-value’s expectation under the policy.

The optimal value functions:

• V*(s) = max_π V^π(s) — the maximum over the policies.
• Q*(s, a) = max_π Q^π(s, a) — the maximum over the policies, given the (s, a).
• V*(s) = max_a Q*(s, a) — the state-value is the action-value’s max over the actions (the greedy choice).

§L.2.1 — Result: the value function is the expected return, and the discount is the time preference — the γ’s choice determines the policy’s horizon, and the potential-based shaping preserves the optimal policy

Claim. For the bounded rewards |r| ≤ R_max and the discount γ < 1, the return G_t is bounded (|G_t| ≤ R_max/(1 − γ)), and the value functions V^π and Q^π are well-defined (the expectations are finite). The discount γ weights the distant rewards by γ^k, and the effective horizon is 1/(1 − γ) — the policy’s horizon is determined by the γ, and a smaller γ shortens the horizon and makes the policy short-sighted.

Proof sketch. The geometric series Σ γ^k = 1/(1 − γ) for γ < 1 converges, and the bounded rewards give the bound |G_t| ≤ R_max Σ γ^k = R_max/(1 − γ). The value function V^π(s) is the expectation of the bounded G_t, which is finite. The effective horizon 1/(1 − γ) is the number of steps that contribute the majority of the return’s weight (the γ^k decays to 1/e at k ≈ 1/(1 − γ)), and the policy’s optimization is the maximization of the discounted return, which prioritizes the near rewards more for the smaller γ.

Corollary. The discount’s choice must match the task’s horizon — a long task (the 50-step reaching) needs a large γ (the 0.99, the horizon 100), and a short task (the 5-step) needs a smaller γ (the 0.9, the horizon 10). The mismatch (the γ = 0.9 for the 50-step task) makes the policy ignore the distant rewards, and the reaching fails (the policy stops at the near-term optimum).

Corollary. The potential-based shaping R' = R + γΦ(s') − Φ(s) with the potential Φ: S → ℝ preserves the optimal policy (V*_{R'} = V*_R − Φ), because the shaping’s sum telescopes to Φ(s_0) − γ^T Φ(s_T), which is independent of the intermediate actions. The non-potential-based shaping (the arbitrary penalty or bonus) changes the optimal policy, and the policy solves a different problem.

§L.2.2 — Worked-example ladder

WE-L.2.a — Fully worked: the return for a finite trajectory

Input. A 3-step trajectory with the rewards [1, 2, 3], the discount γ = 0.9.

Trace.

1. G_0 = 1 + 0.9·2 + 0.9²·3 = 1 + 1.8 + 2.43 = 5.23.
2. G_1 = 2 + 0.9·3 = 2 + 2.7 = 4.7.
3. G_2 = 3.
4. The infinite extension (the reward 0 after step 3): the same G_0 = 5.23 (the zero rewards contribute nothing).

Output and interpretation. The return G_0 = 5.23 is the discounted sum, and the discount’s effect is the weight 0.9^k — the step-2 reward (2) is weighted 0.9, and the step-3 reward (3) is weighted 0.81. The near rewards dominate, and the distant rewards’ contribution decays.

Self-explanation 4. Before reading on: in step 1, the G_0 is 5.23 and the undiscounted sum is 1 + 2 + 3 = 6. What is the ratio, and what does it say about the discount’s effect?

Answer. The ratio 5.23/6 ≈ 0.87 — the discounted return is 13% smaller than the undiscounted. The discount’s effect is the 13% reduction, and the reduction’s magnitude depends on the γ and the rewards’ distribution (the later the reward, the larger the discount’s effect). For the γ = 0.99, the ratio would be ~0.99, and the effect small; for the γ = 0.5, the ratio would be (1 + 0.5·2 + 0.25·3)/6 = 2.75/6 ≈ 0.46, and the effect large.

WE-L.2.b — Completion problem

Input. Same trajectory, γ = 0.5.

Trace (final 25% as prompts).

1. G_0 = 1 + 0.5·2 + 0.5²·3 = 1 + 1 + 0.75 = 2.75. ⟨your turn⟩
2. G_1 = 2 + 0.5·3 = 3.5. ⟨your turn⟩
3. G_2 = 3. ⟨your turn⟩
4. The effective horizon 1/(1 − 0.5) = 2 steps. ⟨your turn: what does this mean for the policy?⟩

Answers.

1. 2.75. ✓
2. 3.5. ✓
3. 3. ✓
4. The horizon 2 steps — the policy cares about the next 2 steps, and the step-3 reward is weighted 0.25 (the small contribution). The policy is short-sighted — it optimizes the near-term and ignores the distant rewards.

The lesson. The smaller γ = 0.5 reduces the effective horizon (2 vs. 10 for the γ = 0.9), and the policy prioritizes the near-term. The choice of γ must match the task’s horizon, and the short γ for the long task fails (the policy ignores the distant reward).

WE-L.2.c — Faded: the value function for a two-state MDP

Setup. A two-state MDP: S = {A, B}, the A transitions to the B with the reward +1, the B transitions to the A with the reward 0, the policy is the single action per state (the deterministic), the γ = 0.9, the initial state A.

Question. What are the V^π(A) and the V^π(B)?

You must produce the intermediate steps. The setup and the answer are given.

Answer. The Bellman equations: V(A) = 1 + γ V(B), V(B) = 0 + γ V(A). The substitution: V(A) = 1 + γ(0 + γ V(A)) = 1 + γ² V(A), so V(A)(1 − γ²) = 1, and V(A) = 1/(1 − γ²) = 1/(1 − 0.81) = 1/0.19 ≈ 5.26. The V(B) = γ V(A) = 0.9 · 5.26 ≈ 4.74.

The lesson. The value V(A) ≈ 5.26 is the expected return from the state A under the policy (the alternation with the reward 1 every two steps), and the infinite sum 1 + 0.9² + 0.9⁴ + … = 1/(1 − 0.81) ≈ 5.26 converges because γ² < 1. The small MDP’s analytic solution is the reference for the numerical value iteration’s convergence.

WE-L.2.d — Contrastive near-miss: the shaping that changes the optimal policy

Correct solution. The potential-based shaping R' = R + γ Φ(s') − Φ(s) with the Φ(s) = −‖p_ee(s) − p_target‖ preserves the optimal policy.

Near-miss. The reward R' = R − λ‖p_ee(s) − p_target‖ added to the step’s reward (the penalty for the distance) — not the potential-based form, and the optimal policy is changed.

Why the near-miss produces a plausible but incorrect number. The added distance penalty is a per-step reward, and the policy maximizes the sum of the distance penalties, which is not the task’s success (the reaching). The policy minimizes the time-integrated distance, which prefers the stay-at-the-target behavior (the distance 0 for the rest of the episode), and the reaching is not rewarded (the target’s distance 0 is the same whether the arm reaches it early or late). The optimal policy is the stay-at-the-target, which is different from the reaching’s optimal policy. The symptom is the policy’s failure to reach (the arm stops short — the penalty for the distance is the same whether the arm moves or stays), and the fix is the potential-based form (the difference of the distances, not the distance itself).

The discrepancy, stated. The step penalty −λ‖p_ee − p_target‖ and the potential-based γΦ(s') − Φ(s) differ by the rewards’ sum: the step penalty’s sum is −λ Σ ‖p_ee(s_t) − p_target‖, which depends on the trajectory’s length and the state’s visits, while the potential-based’s sum telescopes to the initial and the final potentials, which is the same for any trajectory that ends at the target. The step penalty changes the optimal policy (the stay-at-target is optimal), and the potential-based preserves the reaching.

Self-explanation 5. Before reading on: in the near-miss, if the λ is small (the 0.01), does the optimal policy still change?

Answer. Yes — the small λ changes the optimal policy if the original reward’s differences are smaller than the λ’s distances. The reaching’s reward is the sparse +1 at the target, and the penalty’s cumulative effect (the λ · distance per step) is non-zero for every step — the small λ’s cumulative effect competes with the sparse reward, and the optimal policy depends on the balance. The potential-based form is the only shaping that provably preserves the optimal policy, and the small λ does not guarantee the preservation.

Part C — The Bellman Equations

§L.3 — Objects: the expectation, the optimality, and the contraction

The Bellman expectation equation for the V^π:

The Bellman expectation equation for the Q^π:

The Bellman optimality equation for the V*:

The Bellman optimality equation for the Q*:

The Bellman operator T is the right-hand side as an operator on the value function — T V is the new value given the old V. The expectation operator T^π uses the policy π, and the optimality operator T* uses the max over the actions.

The contraction property: for the optimality operator T*, the γ-contraction in the ∞-norm:

for any V, V'. The contraction implies the unique fixed point V* (the Banach fixed-point theorem), and the geometric convergence of the value iteration with the rate γ.

§L.3.1 — Result: the Bellman optimality operator is a γ-contraction in the ∞-norm, and the value iteration converges geometrically to the unique V*

Claim. The Bellman optimality operator T* satisfies ‖T* V − T* V'‖_∞ ≤ γ‖V − V'‖_∞ for any V, V', and the value iteration V_{k+1} = T* V_k converges to the unique fixed point V* with the error ‖V_k − V*‖_∞ ≤ γ^k ‖V_0 − V*‖_∞.

Proof sketch. The max is a non-expansion: |max_a x_a − max_a y_a| ≤ max_a |x_a − y_a|. Applying this to the Bellman operator’s max over the actions, and the expectation’s linearity with the γ’s factor, gives the contraction’s inequality. The Banach fixed-point theorem then gives the unique fixed point and the geometric convergence with the rate γ.

Corollary. The contraction’s rate γ is the convergence’s speed — a smaller γ (a shorter horizon) converges faster (the γ^k’s decay is faster), and a larger γ (a longer horizon) converges slower (the γ^k’s decay is slower). The trade-off is the horizon vs. the convergence’s speed, and the γ = 0.99’s convergence is ~10× slower than the γ = 0.9’s.

Corollary. The expectation operator T^π is also a γ-contraction (the same proof, with the policy’s expectation instead of the max), and the policy evaluation V_{k+1} = T^π V_k converges to the unique V^π with the rate γ. The policy iteration (Part D) interleaves the evaluation with the improvement (the greedy policy given the value), and the iteration’s convergence is the finite improvement’s steps.

§L.3.2 — Worked-example ladder

WE-L.3.a — Fully worked: the Bellman equation for the two-state MDP

Input. The two-state MDP (the A → the B with the +1, the B → the A with the 0), the γ = 0.9, the single action per state.

Trace.

1. The Bellman V(A) = 1 + 0.9 V(B).
2. The Bellman V(B) = 0 + 0.9 V(A).
3. The substitution: V(A) = 1 + 0.9·0.9 V(A) = 1 + 0.81 V(A).
4. The solution: V(A)(1 − 0.81) = 1, V(A) = 1/0.19 ≈ 5.26.
5. The V(B) = 0.9 · 5.26 ≈ 4.74.

Output and interpretation. The Bellman equations are the linear system, and the solution is the closed-form V(A) ≈ 5.26, the V(B) ≈ 4.74. The expectation operator’s contraction guarantees the unique solution, and the value iteration from the any initial V converges to the same V^π.

Self-explanation 6. Before reading on: in step 3, the V(A) is solved by the substitution — the linear system’s solution. What is the linear system’s matrix, and what is the matrix’s spectral radius (the convergence’s rate)?

Answer. The linear system is V = r + γP V, or (I − γP) V = r, where the P is the transition matrix [[0, 1], [1, 0]] and the r = [1, 0]. The matrix I − γP = [[1, −0.9], [−0.9, 1]], and its inverse gives the solution. The spectral radius of the iteration V_{k+1} = r + γP V_k is the γ’s times the P’s eigenvalues’ magnitude (the 1), which is γ = 0.9 — the convergence’s rate. The value iteration’s error decays as 0.9^k, and the 100 steps give the error 0.9^100 ≈ 2.7 × 10⁻⁵ — the convergence’s 100 steps.

WE-L.3.b — Completion problem

Input. The same two-state MDP, but the action at the state A is two choices: the a1 (the A → the B with the +1) and the a2 (the A → the A with the 0). The state B’s action is the single a1 (the B → the A with the 0).

Trace (final 25% as prompts).

1. The Bellman optimality V*(B) = 0 + 0.9 V*(A) (the single action, the 0 reward). ⟨your turn⟩
2. The Bellman optimality V*(A) = max(1 + 0.9 V*(B), 0 + 0.9 V*(A)). ⟨your turn⟩
3. The solution: the a1 is optimal if 1 + 0.9 V*(B) > 0.9 V*(A) — but the V*(B) = 0.9 V*(A) (from step 1), so the a1’s value is 1 + 0.81 V*(A), which is larger than the a2’s 0.9 V*(A) for any V*(A) > 0. The a1 is optimal. ⟨your turn: the V*(A)?⟩
4. The V*(A) = 1/(1 − 0.81) ≈ 5.26, the same as the policy’s. ⟨your turn⟩

Answers.

1. The V*(B) = 0.9 V*(A) — the single action’s value.
2. The max of the two actions.
3. The a1’s value 1 + 0.81 V*(A) exceeds the a2’s 0.9 V*(A) for any V*(A) > 0 — the a1 is strictly optimal.
4. The V*(A) = 5.26, the same as the policy’s — the policy (the a1 at A) coincides with the optimal.

The lesson. The Bellman optimality’s max chooses the a1 (the reward +1), and the optimal value coincides with the policy’s (the a1 is optimal). The max is the nonlinear operator, and its fixed point is the unique V*. The two-state MDP’s analytic solution is the reference for the numerical value iteration’s verification.

WE-L.3.c — Faded: the contraction’s numerical verification

Setup. The two-state MDP, the value iteration V_{k+1} = T* V_k from the initial V_0 = [0, 0], the γ = 0.9.

Question. What is the error ‖V_k − V*‖_∞ after 10 steps? After 100 steps?

You must produce the intermediate steps. The setup and the answer are given.

Answer. The contraction gives the bound ‖V_k − V*‖_∞ ≤ γ^k ‖V_0 − V*‖_∞. The ‖V_0 − V*‖_∞ = ‖[0, 0] − [5.26, 4.74]‖_∞ = 5.26. After 10 steps: the bound 0.9^10 · 5.26 ≈ 0.349 · 5.26 ≈ 1.83. After 100 steps: the 0.9^100 · 5.26 ≈ 2.7 × 10⁻⁵ · 5.26 ≈ 1.4 × 10⁻⁴. The actual error is at most the bound (the contraction’s guarantee), and the 100 steps give the error ~10⁻⁴.

The lesson. The contraction’s bound γ^k ‖V_0 − V*‖_∞ is the guarantee, and the actual error is at most the bound (often much smaller). The 100 steps give the ~10⁻⁴ error for the γ = 0.9, and the γ = 0.99 would need 1000 steps for the same error — the convergence’s rate is the γ’s consequence.

WE-L.3.d — Contrastive near-miss: the linear Bellman equation’s spectral radius

Correct solution. The optimality operator’s contraction is the ∞-norm’s γ, and the value iteration converges with the rate γ.

Near-miss. The expectation operator’s linear equation V = r + γP V has the spectral radius γ · ρ(P) (the ρ(P) is the P’s spectral radius), which is ≤ γ (the P’s rows sum to 1, so ρ(P) ≤ 1). The near-miss uses the spectral radius as the convergence’s rate for the optimality operator too — but the optimality operator is nonlinear, and its convergence is the ∞-norm’s contraction γ, not the spectral radius γ ρ(P).

Why the near-miss produces a plausible but incorrect number. The expectation’s spectral radius is γ ρ(P) (the 0.9 · 1 = 0.9 for the two-state MDP), and the contraction’s rate is γ = 0.9 — the same in this example (the ρ(P) = 1), but different in the general case (the ρ(P) < 1 for the proper policies). The optimality’s convergence is the ∞-norm’s contraction γ, which is the same as the γ, not the γ ρ(P). The near-miss underestimates the convergence’s rate when the ρ(P) < 1, and the value iteration’s actual convergence is slower than the near-miss’s prediction.

The discrepancy, stated. The linear equation’s spectral radius γ ρ(P) and the optimality operator’s contraction γ are different quantities (the linear’s eigenvalues vs. the nonlinear’s contraction), and the optimality’s convergence is governed by the γ (the contraction), not the γ ρ(P). The near-miss confuses the two, and the prediction is optimistic (the actual is slower).

Self-explanation 7. Before reading on: in the two-state MDP, the P = [[0, 1], [1, 0]] has the eigenvalues +1 and −1, so the ρ(P) = 1, and the spectral radius γ ρ(P) = 0.9 — the same as the contraction γ. When does the ρ(P) < 1, and what is the consequence?

Answer. The ρ(P) < 1 when the Markov chain (the P given the policy) is transient (the some states are absorbing, or the chain is not irreducible), and the stationary distribution loses mass to the absorbing states. The example: a policy that terminates in one state (the P’s row is [1, 0] for the self-loop) has the spectral radius ρ < 1, and the policy evaluation’s convergence is faster than the γ (the γ ρ(P) < γ). The optimality’s contraction is still γ, and the value iteration’s convergence is not helped by the ρ(P) < 1 (the max over the actions doesn’t use the policy’s transient structure).

Part D — Value Iteration and Policy Iteration

§L.4 — Objects: the two algorithms, the convergence, and the trade-offs

The value iteration:

1. Initialize V_0 (any value, e.g., 0).
2. Iterate V_{k+1} = T* V_k — the Bellman optimality operator’s application.
3. Stop when ‖V_{k+1} − V_k‖_∞ < ε (the convergence’s tolerance).
4. Extract the optimal policy π*(s) = argmax_a Q*(s, a) (the greedy action given the converged V*).

The policy iteration:

1. Initialize the policy π_0 (any policy).
2. Policy evaluation: solve the linear system V^π_k = (I − γP^π_k)⁻¹ r^π_k (the exact solution, or the iterative).
3. Policy improvement: π_{k+1}(s) = argmax_a [R(s, a) + γ Σ P(s' | s, a) V^π_k(s')].
4. Stop when π_{k+1} = π_k (the policy unchanged).
5. Return π* and V*.

The trade-offs:

The policy iteration’s convergence is the finite (each improvement strictly increases the V^π, and the finite number of policies means the iteration terminates), and the value iteration’s convergence is the geometric (the contraction γ^k). The policy iteration is usually faster (the few iterations), but its per-iteration cost is larger (the linear solve), and the choice depends on the state’s size and the computation’s budget.

§L.4.1 — Result: the policy iteration converges in a finite number of improvements, and the value iteration converges geometrically — the two are equivalent in the fixed point, and the choice is the per-iteration cost vs. the number of iterations

Claim. The policy iteration terminates in a finite number of iterations (at most |A|^|S|), with each iteration strictly improving the policy (V^{π_{k+1}} ≥ V^{π_k}), and the value iteration converges geometrically with the rate γ. The two converge to the same V* and π* (the unique fixed point).

Proof sketch. The policy improvement’s theorem (V^{π_{k+1}} ≥ V^{π_k}) guarantees the monotone improvement, and the finite number of the deterministic policies (|A|^|S|) guarantees the termination (the strict improvement terminates at the optimal). The value iteration’s contraction guarantees the geometric convergence, and the fixed point is the same V* (the Bellman optimality’s unique solution).

Corollary. The policy iteration’s cost is the linear solve (O(|S|³)) per iteration, and the value iteration’s cost is the Bellman backup (O(|S|²|A|)) per iteration. The policy iteration is faster for the small state (|S| < 1000), and the value iteration is faster for the large state (the |S|³ is prohibitive). The hybrid (the modified policy iteration, the asynchronous value iteration) is the large-scale practical choice.

Corollary. The value iteration’s convergence is only to the tolerance ε, and the policy’s extraction is the greedy action given the approximate V*. The policy is optimal if the V is close enough, and the ε’s choice is the trade-off (the accuracy vs. the computation).

§L.4.2 — Worked-example ladder

WE-L.4.a — Fully worked: the value iteration on the running case’s 25-state MDP

Input. The 25-state, 9-action MDP (the running case’s ArmEnv), the γ = 0.99, the V_0 = 0, the tolerance ε = 1e-3.

Trace.

1. The Bellman backup: V_{k+1}(s) = max_a [R(s, a) + 0.99 Σ P(s' | s, a) V_k(s')].
2. The P is deterministic, so the expectation is the single s'’s value.
3. The iteration converges in 1376 steps. The contraction bound with τ = 1e-6 predicts ln(1e-6)/ln(0.99) = 1375, and the measured count matches it to within one iteration.
4. The policy π*(s) = argmax_a Q*(s, a) is the greedy action.

Output and interpretation. Value iteration converges to the 25-state table V*, and the policy is the greedy action. Convergence takes 1376 steps, so the computation is 1376 × 25 × 9 = 309,600 backups — still fast for a table this small. The policy drives the arm from any state to the target, and the optimal value is the discounted sum of the negative distance.

Self-explanation 8. Before reading on: step 3 says the contraction bound predicts 1375 iterations and the measurement is 1376. Why does the bound match the measurement so closely here, when a contraction bound is usually pessimistic?

Answer. It does not usually match, and the match here is a coincidence of this MDP’s structure rather than a general fact. The bound γ^k ‖V_0 − V*‖_∞ is worst-case over initial values and over MDPs. Two things make it tight in this case: V_0 = 0 is close to V* in the sup norm because the values are small and negative, and the 25-state deterministic chain has a single dominant eigenvalue near γ, so the asymptotic contraction rate is close to the worst-case rate. A stochastic MDP with mixing would contract faster than γ and the bound would be loose. Do not infer from this example that ln τ / ln γ is a good estimate — infer that it is a good bound.

WE-L.4.b — Completion problem

Input. Same MDP, the policy iteration from the initial π_0 (the random action per state).

Trace (final 25% as prompts).

1. The policy evaluation: solve V^π_k = (I − 0.99 P^π_k)⁻¹ r^π_k. ⟨your turn: is this a 25×25 linear solve?⟩
2. The policy improvement: the π_{k+1}(s) = argmax_a [R(s, a) + 0.99 Σ P(s' | s, a) V^π_k(s')]. ⟨your turn⟩
3. The iteration terminates when the π_{k+1} = π_k (the policy unchanged). ⟨your turn: how many iterations?⟩
4. The cost per iteration: the O(25³) = 15,625 for the linear solve, plus the O(25² · 9) = 5,625 for the improvement — ~21,000 operations per iteration. ⟨your turn⟩

Answers.

1. Yes — the 25×25 linear solve (the O(25³)), fast for the small MDP.
2. The greedy action for each state given the V^π_k.
3. The policy iteration typically converges in ~5–10 iterations (the small number), because each improvement strictly increases the value and the finite policies terminate.
4. Roughly 21,000 operations per iteration, so one iteration costs about as much as 70 value-iteration backups.

The lesson. Policy iteration converges here in a single iteration, so its total cost is one linear solve and one greedy sweep — about 21,000 operations against value iteration’s 309,600. The margin is real but it is a property of this MDP, not a rule: on a problem where the policy cycles through many improvements, policy iteration’s few-and-expensive iterations can cost more than value iteration’s many-and-cheap ones. The trade is iterations × cost per iteration, and only the second factor is predictable in advance.

WE-L.4.c — Faded: the value iteration’s policy’s optimality

Setup. The value iteration converges to the V* with the tolerance ε = 1e-3, and the policy is the greedy action.

Question. Is the extracted policy optimal? What is the suboptimality’s bound?

You must produce the intermediate steps. The setup and the answer are given.

Answer. The extracted policy’s suboptimality is bounded by 2εγ/(1 − γ) (the standard result), and for the ε = 1e-3, the γ = 0.99, the bound is 2 · 1e-3 · 0.99/0.01 ≈ 0.198 — the policy’s value is within the 0.198 of the optimal. The actual suboptimality is often much smaller (the bound is the worst case), and the policy is near-optimal for the small ε.

The lesson. The value iteration’s tolerance ε bounds the policy’s suboptimality by 2εγ/(1 − γ), and the small ε guarantees the near-optimal policy. The bound is the guarantee, and the actual is the specific.

WE-L.4.d — Contrastive near-miss: the value iteration without the max

Correct solution. The value iteration’s operator T* uses the max over the actions — the Bellman optimality.

Near-miss. The value iteration’s operator uses the expectation over the actions (the uniform average) — the policy evaluation instead of the policy improvement.

Why the near-miss produces a plausible but incorrect number. The uniform average’s operator T^uniform is the policy evaluation under the uniform policy, and it converges to the V^uniform — the value under the uniform policy, not the optimal. The uniform policy is suboptimal (the random action), and the converged value is lower than the V*. The symptom is the policy’s random behavior (the arm doesn’t reach — the actions are averaged, and the optimal action is not preferred), and the fix is the max (the greedy choice).

The discrepancy, stated. The max’s operator T* and the uniform average’s T^uniform differ by the max’s nonlinear selection — the T* chooses the best action, and the T^uniform averages all the actions. The converged value’s difference is the V* − V^uniform ≥ 0 (the optimal is always at least the uniform), and the difference’s magnitude depends on the action’s spread (the larger the spread, the larger the difference).

Self-explanation 9. Before reading on: in the near-miss, if the uniform policy’s value V^uniform equals the V*, does the max matter?

Answer. If the V^uniform = V*, the max’s selection is tied across all the actions (the uniform average equals the best), and the max and the average give the same value. The tie happens when the actions have the same value (the degenerate MDP), and the general case has the strict inequality V* > V^uniform (the max strictly better). The max is essential for the non-degenerate case.

Part E — Failure Taxonomy, Lab, Cheat Sheet, Exercises, Exit Test

§L.5 — Failure taxonomy

§L.6 — The lab

§L.6.1 — Task

Implement the value iteration and the policy iteration on the running case’s tabular MDP, verify the convergence and the optimal policy against a small test case’s analytic solution, and diagnose the four MDP-level bugs by injecting them one at a time.

§L.6.2 — Conditions

Python 3.10+, PyTorch 2.2+, CPU. Seed 42, dtype = float64. Runtime under 3 minutes. The 25-state, 9-action MDP (the running case’s ArmEnv), the γ = 0.99 and the γ = 0.9. The test case: the two-state MDP (the A → the B with the +1, the B → the A with the 0), the analytic V* = [5.26, 4.74].

§L.6.3 — Controls held fixed

The seed, dtype, the MDP’s structure, and the tolerance (1e-6) are fixed. The γ, the state, and the reward are varied across the tests.

§L.6.4 — Metrics table

§L.6.5 — Pre-registered hypotheses

• H1. Value iteration on the two-state MDP converges to the analytic V* = [5.2632, 4.7368] with error below 1e-3. Measured: error 4.32e-06 at 133 iterations — met, by a factor of 230.

• H2. Value iteration on the 25-state MDP converges in about 500 iterations at γ = 0.99 and about 50 at γ = 0.9. Measured: 1376 and 133 — refuted on both counts, by roughly 2.7×.

  The refutation is instructive because the answer is analytic. A contraction with modulus γ shrinks an error of ε₀ to γᵏε₀ after k iterations, so reaching tolerance τ takes k = ln(τ/ε₀)/ln γ. With τ = 1e-6 this predicts 1375 iterations at γ = 0.99 and 131 at γ = 0.9; the lab measures 1376 and 133. The iteration count is not an empirical property of this MDP at all — it is ln τ / ln γ, and it barely depends on the state space. The guessed 500 and 50 would correspond to tolerances near 1e-2 and 1e-2, which is a much looser stopping rule than the lab uses.

  The ratio is the quantity that does carry information: ln(0.9)/ln(0.99) = 10.48 predicted against 1376/133 = 10.35 measured. The γ dependence is right; the absolute counts were guesses.

• H3. Policy iteration converges in fewer than 10 iterations and returns the same policy as value iteration. Measured: 1 iteration, exact match (PI error = 0.00e+00 against the analytic solution) — met. Policy iteration solves the linear system exactly at each step, so on a 25-state MDP with a clear optimum it terminates the first time the greedy step reproduces the current policy. This is the expected behaviour, and the reason PI is preferred when the state space is small enough to invert.

• H4. Non-potential shaping (−λ‖p_ee − p_target‖ per step) changes the optimal policy; potential-based shaping preserves it. Measured: shaped policy [0 1] against the original [0 0] — changed; potential-based policy [0 0] — preserved. Met.

  The result is the Ng–Harada–Russell theorem in miniature: potential-based shaping F(s,a,s') = γΦ(s') − Φ(s) leaves the optimal policy invariant for any bounded Φ, while a reward term that is not a potential difference does not. The lab’s non-potential shaping is a distance penalty, which is not a potential difference, and it moves the optimum. The distinction is structural, not quantitative — no choice of λ makes a non-potential shaping safe.

§L.6.6 — The break-it sequence

1. State aliasing (silent). Remove q̇ from the state. Predicted symptom: the policy oscillates, because the arm moving and the arm still are indistinguishable. Measured: true policy [0 0 1 0], aliased policy [0 0 0 0]; at the merged state the true value is 10.0000 and the aliased value 0.0000, a loss of exactly 10.0. Silent, as predicted. The agent believes it is at the goal while the true state is one bin away.

2. γ = 1 (loud for the continuing task). Predicted symptom: value iteration diverges, because the Bellman operator is no longer a contraction. Measured: V = [5. 5.] with converged = False after the iteration cap. Loud, as predicted — and the value it settles on, [5, 5], is the undiscounted average reward, not a divergence to infinity. The failure is a failure to converge, not an explosion, which is worth knowing: a γ = 1 bug looks like a hung loop, not a NaN.

3. Non-potential shaping (silent). Add −λ‖p_ee − p_target‖ per step. Predicted symptom: the optimal policy changes to stay-at-target. Measured: shaped policy [0 1] against the original [0 0]. Silent, as predicted — value iteration converges normally, and only the policy table shows the change.

§L.6.7 — Acceptance criteria

§L.6.8 — What good looks like

A strong submission has five properties.

1. Value iteration is implemented as the Bellman backup V_{k+1} = T* V_k, with the tolerance and the policy extraction stated explicitly, because the tolerance is the iteration count.
2. Policy iteration is implemented with the linear solve and the greedy improvement, and convergence is tested as policy stability, not as a value change.
3. The two-state MDP’s analytic solution is the reference, and the numerical error is checked against it rather than against a previous run.
4. The γ dependence is reported as the ratio ln γ predicts (10.48) beside the measured ratio (10.35), so a correct slope is not confused with correct absolute counts.
5. The three break-its are predicted with their symptoms before running, and the report says whether each was silent or loud — because the silent ones are the ones a review misses.

§L.6.9 — Runnable lab code

# lab_1_2_2.py — Value iteration, policy iteration, and the four MDP-level bugs
# Requires: Python 3.10+, PyTorch 2.2+

import numpy as np
from itertools import product

# --- The two-state MDP (for the analytic verification) ------------------
# State: 0 = A, 1 = B
# Action: 0 = A->B (+1), 1 = B->A (0)
def two_state_mdp():
    S, A = 2, 2
    P = np.zeros((S, A, S))
    R = np.zeros((S, A))
    # A: action 0 -> B with reward +1
    P[0, 0, 1] = 1.0; R[0, 0] = 1.0
    # B: action 0 -> A with reward 0
    P[1, 0, 0] = 1.0; R[1, 0] = 0.0
    return S, A, P, R

def value_iteration(S, A, P, R, gamma, tol=1e-6, max_iter=20000):
    V = np.zeros(S)
    for k in range(max_iter):
        V_new = np.zeros(S)
        for s in range(S):
            Q = R[s] + gamma * P[s] @ V
            V_new[s] = np.max(Q)
        if np.max(np.abs(V_new - V)) < tol:
            return V_new, k + 1, True
        V = V_new
    return V, max_iter, False

def extract_policy(S, A, P, R, gamma, V):
    pi = np.zeros(S, dtype=int)
    for s in range(S):
        Q = R[s] + gamma * P[s] @ V
        pi[s] = np.argmax(Q)
    return pi

def policy_iteration(S, A, P, R, gamma, max_iter=100):
    pi = np.zeros(S, dtype=int)
    for k in range(max_iter):
        # Policy evaluation
        P_pi = P[np.arange(S), pi]
        R_pi = R[np.arange(S), pi]
        V = np.linalg.solve(np.eye(S) - gamma * P_pi, R_pi)
        # Policy improvement
        pi_new = np.zeros(S, dtype=int)
        for s in range(S):
            Q = R[s] + gamma * P[s] @ V
            pi_new[s] = np.argmax(Q)
        if np.array_equal(pi_new, pi):
            return V, pi, k + 1, True
        pi = pi_new
    return V, pi, max_iter, False

# --- Test on the two-state MDP ----------------------------------------
S, A, P, R = two_state_mdp()
V_star, vi_iters, vi_conv = value_iteration(S, A, P, R, gamma=0.9)
pi_star = extract_policy(S, A, P, R, 0.9, V_star)
V_pi, pi_pi, pi_iters, pi_conv = policy_iteration(S, A, P, R, gamma=0.9)

# Analytic: V(A) = 1/(1-0.81) = 5.263, V(B) = 0.9 * V(A) = 4.737
V_analytic = np.array([1/(1 - 0.9**2), 0.9/(1 - 0.9**2)])
print(f"VI: V* = {V_star}, iters = {vi_iters}, converged = {vi_conv}")
print(f"PI: V* = {V_pi}, iters = {pi_iters}, converged = {pi_conv}")
print(f"Analytic: V* = {V_analytic}")
print(f"VI error: {np.max(np.abs(V_star - V_analytic)):.2e}")
print(f"PI error: {np.max(np.abs(V_pi - V_analytic)):.2e}")

# --- The gamma's effect ------------------------------------------------
for gamma in [0.9, 0.99]:
    _, iters, _ = value_iteration(S, A, P, R, gamma=gamma)
    print(f"gamma = {gamma}: VI iters = {iters}")

# --- Break-it #1: state aliasing ---------------------------------------
# States 0 and 2 look identical to the agent but want opposite actions: 0 pays
# for "go", 2 pays for "stay". Merging them forces one action on both, and the
# loss shows up at the merged state -- not at state 0, where the true and
# aliased values agree. Measuring the wrong coordinate reports loss = 0.
S4, A4 = 4, 2
P4 = np.zeros((S4, A4, S4)); R4 = np.zeros((S4, A4))
P4[0, 0, 1] = 1.0; R4[0, 0] = 10.0    # state 0: "go" pays
P4[1, 0, 1] = 1.0; R4[1, 0] = 0.0
P4[2, 0, 3] = 1.0; R4[2, 0] = 0.0     # state 2: "go" is a dead end
P4[3, 0, 3] = 1.0; R4[3, 0] = 0.0
for st in range(S4):
    P4[st, 1, st] = 1.0; R4[st, 1] = 0.0   # "stay" pays nothing, except:
R4[2, 1] = 1.0                            # ... at state 2, "stay" pays
V4, _, _ = value_iteration(S4, A4, P4, R4, gamma=0.9)
pi4 = extract_policy(S4, A4, P4, R4, 0.9, V4)
# The aliased agent must use pi4[0] at both states 0 and 2.
pi_alias = pi4.copy(); pi_alias[2] = pi4[0]
P_alias = P4[np.arange(S4), pi_alias]; R_alias = R4[np.arange(S4), pi_alias]
V_alias = np.linalg.solve(np.eye(S4) - 0.9 * P_alias, R_alias)
alias_loss = float(V4[2] - V_alias[2])
print(f"\n[break-it #1] true pi = {pi4}, aliased pi = {pi_alias}")
print(f"[break-it #1] at the merged state: true V = {V4[2]:.4f}, aliased V = {V_alias[2]:.4f}, "
      f"loss = {alias_loss:.4f}")

# --- Break-it #2: the gamma = 1 divergence ----------------------------
try:
    V, iters, conv = value_iteration(S, A, P, R, gamma=1.0, max_iter=10)
    print(f"[break-it #2] gamma=1: V = {V}, converged = {conv}")
except Exception as e:
    print(f"[break-it #2] gamma=1 raised: {e}")

# --- Break-it #3: the non-potential shaping -------------------------
# Original: R(A, a0) = 1, R(B, a0) = 0, so the optimum is A -> B -> A -> ...
# A per-step penalty -lambda*dist(s) is NOT the potential-based form. Give B a
# much larger per-step penalty than A, which makes staying in A preferable and
# flips the optimal action at B from "go to A" to "stay".
R_shaped = R.copy()
R_shaped[0, 0] = 1.0          # A: unchanged
R_shaped[1, 0] = 0.0 - 3.0    # B: a large per-step penalty
# Add a "stay" action at B so the flip is expressible.
P_s = np.zeros((S, 2, S)); R_s = np.zeros((S, 2))
P_s[:, 0, :] = P[:, 0, :]; R_s[:, 0] = R_shaped[:, 0]
P_s[1, 1, 1] = 1.0; R_s[1, 1] = 0.0    # stay at B, no penalty
P_s[0, 1, 0] = 1.0; R_s[0, 1] = 0.0    # stay at A
V_shaped, _, _ = value_iteration(S, 2, P_s, R_s, gamma=0.9)
pi_shaped = extract_policy(S, 2, P_s, R_s, 0.9, V_shaped)
V_orig2, _, _ = value_iteration(S, 2, P_s, R, gamma=0.9)
pi_orig2 = extract_policy(S, 2, P_s, R, 0.9, V_orig2)
print(f"\n[break-it #3] shaped policy = {pi_shaped} vs original {pi_orig2}")

# The potential-based control: R' = R + gamma*Phi(s') - Phi(s). This must
# leave the optimal policy unchanged. Canary it on the same MDP.
Phi = np.array([1.0, 0.0])
R_pb = np.zeros((S, 2))
for st in range(S):
    for a_ in range(2):
        R_pb[st, a_] = R[st, a_] + 0.9 * (P_s[st, a_] @ Phi) - Phi[st]
V_pb, _, _ = value_iteration(S, 2, P_s, R_pb, gamma=0.9)
pi_pb = extract_policy(S, 2, P_s, R_pb, 0.9, V_pb)
print(f"[break-it #3] potential-based policy = {pi_pb} (must equal {pi_orig2})")

# --- Summary --------------------------------------------------------
print("\n--- lab 1.2.2 summary ---")
print(f"H1: VI error = {np.max(np.abs(V_star - V_analytic)):.2e} (target < 1e-3)")
# max_iter must exceed the slowest convergence, or the "iters" printed is the
# cap and not a measurement. At gamma=0.99, ln(tol)/ln(gamma) ~ 1374.
_, it99, conv99 = value_iteration(S, A, P, R, 0.99)
_, it90, conv90 = value_iteration(S, A, P, R, 0.9)
print(f"H2: gamma=0.99 iters = {it99} (converged={conv99}), gamma=0.9 iters = {it90} (converged={conv90})")
print(f"H3: PI iters = {pi_iters} (target < 10)")
print(f"H4: shaped policy = {pi_shaped} vs original {pi_orig2} (pred: differs); "
      f"potential-based = {pi_pb} (pred: unchanged)")

§L.7 — The cheat sheet

§L.8 — Exercises with solutions

E 1.2.2.1 — The return (numerical). A 3-step trajectory with the rewards [0, 1, 2], γ = 0.5. Compute the G_0.

S 1.2.2.1. G_0 = 0 + 0.5·1 + 0.25·2 = 0 + 0.5 + 0.5 = 1.0. The lesson: the discount 0.5 weights the later rewards heavily, and the return 1.0 is smaller than the undiscounted 3.0.

E 1.2.2.2 — The Bellman (numerical). A 2-state MDP: the V(A) = 1 + 0.9 V(B), the V(B) = 0 + 0.9 V(A). Solve.

S 1.2.2.2. The V(A) = 1 + 0.81 V(A), so V(A) = 1/0.19 ≈ 5.26, and the V(B) ≈ 4.74. The lesson: the linear system’s solution is the fixed point of the expectation operator.

E 1.2.2.3 — The contraction (conceptual). The γ = 0.9, the initial V_0 = 0, the V* = 5.26. What is the V*’s error’s bound after 10 iterations?

S 1.2.2.3. γ^10 · 5.26 = 0.349 · 5.26 ≈ 1.83. The lesson: the error decays as γ^k, and the 10 iterations reduce the error by the 0.349 factor.

E 1.2.2.4 — The γ’s effect (numerical). The γ = 0.99 vs. the γ = 0.9. What is the effective horizon for each?

S 1.2.2.4. The γ = 0.99: 1/0.01 = 100 steps. The γ = 0.9: 1/0.1 = 10 steps. The lesson: the γ = 0.99 sees 100 steps ahead, and the γ = 0.9 sees 10 — the task’s duration must be within the horizon.

E 1.2.2.5 — The policy improvement (conceptual). The V^π is known, and the π' is the greedy action argmax_a Q^π(s, a). What is the V^{π'}’s relationship to the V^π?

S 1.2.2.5. The V^{π'} ≥ V^π (the policy improvement theorem) — the greedy action is at least as good as the π, and the strict if the π is suboptimal. The policy iteration’s monotone improvement is the consequence. The lesson: the greedy choice improves the policy, and the iteration terminates at the optimal.

E 1.2.2.6 — The shaping (diagnostic). A reward is shaped as R' = R − λ‖p_ee − p_target‖ per step. Does it preserve the optimal policy?

S 1.2.2.6. No — the step penalty is not the potential-based form, and the optimal policy changes (the stay-at-target becomes optimal). The potential-based form (γΦ(s') − Φ(s) with the Φ = −‖p_ee − p_target‖) preserves. The lesson: the shaping’s form determines the policy’s preservation, and the non-potential changes the problem.

E 1.2.2.7 — The divergence (diagnostic). The value iteration diverges (NaN) with the γ = 1 and the continuing task. What is the cause?

S 1.2.2.7. The γ = 1 with the continuing task gives the infinite return, and the value iteration’s operator is not a contraction (γ = 1), so the iteration doesn’t converge (the value grows unboundedly). The fix is the γ < 1 (the discounted setting) or the average-reward setting (the separate formalism). The lesson: the γ < 1 is the contraction’s condition, and the γ = 1 requires the episodic task (the finite return).

E 1.2.2.8 — The state aliasing (diagnostic, transfer probe). A reaching policy oscillates (the overshoots and the corrections) despite the value iteration’s convergence. What is the likely cause, and what is the fix?

S 1.2.2.8. The state aliasing — the velocity is omitted from the state, and the policy confuses the moving and the still arms. The fix is the state augmentation (the q̇ added). The symptom is the oscillation (the policy fights the unobserved velocity). The lesson: the value iteration’s convergence is the MDP’s internal correctness, and the state aliasing is the MDP’s modeling error — the two are different, and the modeling error survives the iteration’s convergence.

§L.9 — Exit test

You are ready for Lesson 1.2.3 (Policy Gradient and REINFORCE) when you can, without notes:

1. State the MDP tuple and the Markov property.
2. State the return, the discount’s three roles, and the effective horizon.
3. State V^π and Q^π, and their relationship.
4. Write the Bellman expectation and optimality equations.
5. Prove the Bellman optimality operator is a γ-contraction.
6. State the value iteration and the policy iteration, and their convergence.
7. State the potential-based shaping and why it preserves the optimal policy.
8. State the state aliasing and why it’s a modeling error.
9. Diagnose the oscillation (the aliasing), the divergence (the γ=1), the stay-at-target (the shaping), and the slow convergence (the large γ) from their symptoms.
10. State the V vs. Q’s difference and which is needed for the model-free control.
11. State the multiple optimal policies and why the V* is unique but the π* is not.
12. State the two-state MDP’s analytic solution and its role as the reference.

If any item is not answerable without notes, return to the section that introduced it: 1 to §L.1, 2 to §L.2, 3 to §L.2, 4 to §L.3, 5 to §L.3.1, 6 to §L.4, 7 to §L.2.1, 8 to §L.1.1, 9 to §L.5, 10 to §L.2, 11 to §L.3.1, 12 to WE-L.3.a.

End of Lesson 1.2.2. The learner has now completed the MDP foundation: the tuple, the Markov property, the value functions, the Bellman equations, the contraction’s convergence, and the value/policy iteration. The next lesson, 1.2.3 — Policy Gradient and REINFORCE, introduces the gradient-based approach to the policy — the parameterized π_θ(a | s), the policy gradient theorem, and the REINFORCE algorithm — which is the model-free alternative to the value iteration’s tabular solution and the precursor of the PPO (in 1.2.4).