Every step a reinforcement learning agent takes is one transition in a Markov decision process: a Markov chain where you also choose the action and collect a reward. One equation, the Bellman equation, links value iteration, policy iteration, Q-learning, PPO and AlphaZero.
Where Part 1 left off: Markov Chains & the Metropolis Sampler treated a chain as something that evolves on its own, with a transition matrix P, k-step probabilities P^k and a long-run distribution that solves π = π P. This lesson adds the missing ingredient, decisions. You may skip it if you are not heading toward reinforcement learning, and the Reinforcement Learning track continues the story from here with Q-learning and the methods built on it. If you do read on, the plan is concrete first: definitions and value functions, then a two-state decision problem by hand, and only then the general Bellman equations.
Learning Objectives
After this lesson, you will be able to:
Define a Markov decision process (states, actions, transition function, reward, discount) and tell a policy π apart from a stationary distribution π
Compute a discounted return and say what the discount factor γ controls, including why γ = 1 on an infinite horizon is dangerous
Solve a two-state decision process by hand with V = (I - gamma P)^-1 R, then read the general Bellman equations
Tell the Bellman expectation equation from the optimality equation, and explain why the max version still has a unique solution
Run value iteration and policy iteration on a small MDP and read the greedy policy off the values
Connect Markov chains and MDPs to MCMC, diffusion-model forward processes, and autoregressive LLM decoding without over-claiming what the Markov property alone gives you
#Markov Decision Processes: Adding Actions and Rewards
So far the chain has just evolved on its own. Markov Decision Processes (MDPs) add the missing ingredient: decisions. At each step, you (the agent) pick an action a, the environment transitions to a new state, and the environment hands you a reward.
An MDP is a tuple (S, A, P, R, γ):
S: state space (where you can be)
A: action space (what you can do)
P(s' | s, a): transition function — the probability of landing in state s' after taking action a in state s
R(s, a) or R(s, a, s'): reward function — the immediate reward for the transition
γ ∈ [0, 1]: discount factor — how much future reward is worth compared to immediate reward
The agent follows a policyπ(a | s), which prescribes the probability of taking action a in state s. This π is not the same as the stationary-distribution π from the previous lesson — yes, the symbol collides. RL textbooks lean on this overload heavily; just be aware.
The agent's job is to find a policy that maximises the expected discounted return — the expected sum of discounted future rewards.
Gt=Rt+1+γRt+2+γ2Rt+3+⋯=k=0∑∞γkRt+k+1
Why discount? Three reasons: (1) it keeps the sum finite even on infinite horizons; (2) it matches human / financial impatience; (3) it makes the math nice — the Bellman operator is a contraction, which we will see in a moment.
Reuse the weather chain from the previous lesson, P = [[0.8, 0.2], [0.4, 0.6]] with states Sunny and Rainy, and attach rewards: a sunny day is worth 1 point and a rainy day 0. To keep the arithmetic small, take γ = 0.5 and let the reward depend only on the state you are in, R = [1, 0]. With one action per state this is a Markov chain with rewards, and the value of each state is V(s), the expected discounted return from s.
Write the value of Sunny in words: the point you get today, plus half of the average value of tomorrow. Tomorrow is Sunny with probability 0.8 and Rainy with 0.2, so:
V(S) = 1 + 0.5 × (0.8 V(S) + 0.2 V(R))
V(R) = 0 + 0.5 × (0.4 V(S) + 0.6 V(R))
Two equations, two unknowns. In matrix form this is V = R + γ P V. Move the P V term across: (I − γ P) V = R, so
V=(I−γP)−1R
Now the numbers. I − γP = [[1 − 0.4, −0.1], [−0.2, 1 − 0.3]] = [[0.6, −0.1], [−0.2, 0.7]]. For a 2 by 2 matrix, the inverse swaps the diagonal entries, negates the off-diagonal ones, and divides by the determinant. The determinant is 0.6 × 0.7 − (−0.1)(−0.2) = 0.42 − 0.02 = 0.40. So the inverse is (1 / 0.4) × [[0.7, 0.1], [0.2, 0.6]] = [[1.75, 0.25], [0.5, 1.5]], and multiplying by R = [1, 0] picks out the first column:
V = [1.75, 0.5]
Check it against the two equations: 1 + 0.5 × (0.8 × 1.75 + 0.2 × 0.5) = 1 + 0.5 × 1.5 = 1.75, and 0 + 0.5 × (0.4 × 1.75 + 0.6 × 0.5) = 0.5 × 1.0 = 0.5. Both hold. The same thing in numpy:
pythonrunnable cell
1
2
3
4
5
6
7
import numpy as np
P = np.array([[0.8, 0.2], [0.4, 0.6]])
R = np.array([1.0, 0.0])
gamma = 0.5
V = np.linalg.solve(np.eye(2) - gamma * P, R)
print(V) # [1.75 0.5 ]
print(R + gamma * P @ V) # [1.75 0.5 ] the equation holds
Each application of the right-hand side, R + γ P V, is one Bellman backup. Start from V = [0, 0] and apply it repeatedly. The first backup gives [1, 0]. The second gives V(S) = 1 + 0.5 × (0.8 × 1 + 0.2 × 0) = 1.4 and V(R) = 0 + 0.5 × (0.4 × 1 + 0.6 × 0) = 0.2, so [1.4, 0.2]. Then [1.58, 0.34], [1.666, 0.418], [1.7082, 0.4586], creeping up on [1.75, 0.5]. Repeated backups and the direct solve agree.
Now add a decision. In Rainy you may take a second action, "go out and cheer up", which costs 0.2 points that day but moves you to Sunny with probability 0.9 (and stays Rainy with 0.1). Using the values [1.75, 0.5] as a guide, compare the two actions in Rainy with one backup each:
The max picks "go out". That choice, a max over actions instead of a fixed policy, is exactly what the Bellman optimality equation below does. Iterating the max backup to convergence gives V* = [1.7714, 0.6286], and the best action in Rainy is still "go out". In Sunny there is only one action, so nothing to choose.
You just used the idea on two states. Now the general form. The value functions satisfy a beautiful recursive structure. The expected return starting from s equals the expected immediate reward plus the discounted expected return from the next state:
These are the Bellman expectation equations. They are systems of linear equations — the value functions are uniquely determined by the policy and the MDP.
The really powerful version is the Bellman optimality equation, which describes the value of the best possible policy:
V∗(s)=amaxs′∑P(s′∣s,a)[R(s,a,s′)+γV∗(s′)]
The Bellman optimality is non-linear (because of the max), but it has a unique solution V^* and a corresponding optimal policy π^* that achieves it. The reason it has a unique solution is that the Bellman optimality operator is a contraction.
What Do You Think?
You are designing an MDP for a self-driving car. Episodes are not guaranteed to terminate (the road can be infinitely long). If you set the discount factor γ = 1.0, what is the most likely failure mode?
Two classical algorithms turn the Bellman equations into computational procedures:
Value iteration: start with any V_0. Repeatedly apply V_{k+1}(s) = max_a Σ_{s'} P(s'|s,a)[R + γ V_k(s')]. Converges to V^* geometrically. Extract the optimal policy π^*(s) = argmax_a [...] at the end.
Policy iteration: alternate between (a) policy evaluation — solve the Bellman expectation equation to get V^π for the current π, and (b) policy improvement, update π(s) ← argmax_a Q^π(s, a). Converges in finitely many iterations on finite MDPs.
These are Sutton & Barto Chapter 4 territory, and they are the conceptual backbone of every modern RL method. Q-learning is value iteration with a learned Q_θ. PPO is approximate policy iteration with a stochastic policy and a trust-region constraint. Knowing the Bellman equations means recognising every paper as a variation on this theme.
Press Step to apply one Bellman sweep and watch the value spread outward from the goal one cell at a time, then raise the slip probability or lower gamma and watch the greedy arrows turn away from the trap.
Put together everything in this lesson and the previous one and you can read most of modern AI's "stochastic" math in one breath.
Two different softmaxes show up in RL, and they are easy to mix up. Boltzmann exploration turns Q-values into action probabilities: π(a|s) ∝ exp(Q(s,a) / τ), a softmax over the Q-values divided by a temperature τ (the Greek letter tau; a large τ makes the choice nearly uniform, a small one nearly greedy). A policy network in policy-gradient methods does something else. It outputs raw scores called logits, one per action, and F.softmax turns those logits into π(a | s). The logits are learned directly. They are not Q-values.
Autoregressive LLM generation is a Markov chain on tokens, where the state is the full prefix and the action is the next token. Beam search, top-k, top-p (nucleus sampling), and temperature are all decoding policies on this chain. Constrained decoding (forcing JSON output, regex schemas) is constrained MDP territory — you are clipping the action space to legal next tokens.
DDPM diffusion is a clean example of a Markov chain in modern generative AI. The forward process q(x_t | x_{t-1}) = N(x_t; √(1−β_t) x_{t-1}, β_t I) is a Markov chain on images: each step shrinks the previous image a little and adds fresh Gaussian noise of size β_t (a small number chosen per step). The Markov property is what lets you describe the whole process as a composition of these one-step moves. The closed form for q(x_t | x_0) comes from something else, the linearity of Gaussians (multivariate-Gaussian lesson): a linear map of a Gaussian, plus independent Gaussian noise, is again Gaussian. Applying that 1000 times collapses the steps into one Gaussian, which is what makes the DDPM training objective a single-step regression and not a 1000-step Monte Carlo estimate.
The bridges, stated explicitly so you can come back and find them:
PageRank is the stationary distribution of the link Markov chain on the web. Google's original PageRank was an eigenvector computation (Eigenvalues & SVD lesson) on a stochastic transition matrix (the previous lesson), with the dangling-node and damping repairs from its PageRank section.
Diffusion models' forward process q(x_t | x_{t-1}) = N(x_t; √(1−β_t) x_{t-1}, β_t I) is a Markov chain of Gaussian steps. The chain structure lets you compose the steps, and the closed-form q(x_t | x_0) follows because linear Gaussian updates keep everything Gaussian.
Q-learning trains a neural network Q_θ(s, a) to satisfy the Bellman optimality equation: Q_θ(s, a) ← R + γ max_{a'} Q_θ(s', a'). The Bellman optimality from this lesson is the fixed-point that DQN, Rainbow, and all value-based RL methods chase.
PPO and TRPO use trust-region constraints (Lagrangian / KL-bounded updates). The discount factor γ in the Bellman equation reappears in the GAE advantage estimator: Â_t = Σ_l (γλ)^l δ_{t+l}, where δ is the TD error. Both terms are glossed in the DeepDive after this list.
MCMC samplers construct ergodic Markov chains whose stationary distribution is the target posterior. You built the simplest one, Metropolis with a symmetric proposal, in the Metropolis section of the previous lesson; Metropolis-Hastings adds a correction for non-symmetric proposals, and Gibbs and Hamiltonian Monte Carlo are other ways to build such chains. Bayesian deep learning's posterior sampling, used in tools like PyMC and NumPyro, is built on these Markov-chain foundations.
You solved a two-state decision problem by hand. Here you do a 3-state version in code: stack the two action matrices, run value iteration, read the greedy policy, then confirm it with an exact linear solve and with policy iteration. Work through the TODOs in order; the solution is there when you want to compare.
pythonplayground.py · Pyodide
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
Tests · Verify that 50 sweeps give V = [16.317, 14.858, 15.23] and policy [0, 0, 1], that the exact value of that policy is [16.397, 14.939, 15.31] (gap 0.081), that policy iteration evaluates [0, 0, 0] to [13.4, 11.433, 9.998], improves to [0, 0, 1], and stops after the second evaluation, and that gamma 0.5 gives V = [3.69, 2.5, 2.976] with the same policy.
Read your output against these numbers. Fifty sweeps at gamma 0.9 give V = [16.317, 14.858, 15.23] and the greedy policy [0, 0, 1]: keep action 0 in Sunny and Cloudy, and switch to action 1 in Rainy. Solving the linear system for that policy gives [16.397, 14.939, 15.31], about 0.08 higher. The gap is the contraction at work: after 50 sweeps the leftover error is about 0.9^50, roughly 0.005, times the size of the values. Policy iteration needs no such patience. It evaluates "always action 0" exactly as [13.4, 11.433, 9.998], improves to [0, 0, 1], evaluates that to the same exact values as above, finds nothing left to improve, and stops after two evaluations. With gamma 0.5 the values drop to [3.69, 2.5, 2.976] and the policy stays [0, 0, 1].
An MDP adds actions, rewards and a discount factor γ to a Markov chain: the tuple (S, A, P, R, γ). A policy π(a | s) is not the stationary distribution π, even though the symbol is the same
The return is the discounted sum of future rewards. At γ = 0.99 a reward 100 steps away is worth about 36 percent of an immediate one, and γ = 1 on an infinite horizon can make the return diverge
For a fixed policy, V = R + γ P V is linear, so V = (I - γP)^-1 R. On the two-state weather MDP with γ = 0.5 that gives V = [1.75, 0.5]
The Bellman optimality equation replaces the average over actions with a max. It is non-linear, yet it has a unique solution because the operator is a contraction with factor γ, so value iteration converges geometrically from any start
Value iteration repeats the max backup and reads the policy off at the end, while policy iteration alternates exact evaluation with greedy improvement. On the 3-state MDP both give the policy [0, 0, 1]
Q-learning is value iteration with a learned Q, PPO is approximate policy iteration with a trust region, and the Markov chain structure also sits under diffusion models, LLM decoding and MCMC
In an MDP, what does the discount factor γ ∈ [0,1) control?
Next up: Convex Optimization, KKT & Lagrangian Duality. You will see why some optimization problems have no bad local minima, and how Lagrange multipliers and the KKT conditions handle problems with constraints.