Markov Decision Processes
Reinforcement Learning is about an agent learning to act in an environment to maximize long-term reward — no labeled examples, just trial, error, and a reward signal. The Markov Decision Process (MDP) is the mathematical frame that makes this precise. Master the MDP and the Bellman equation, and every RL algorithm becomes a way of solving it. RL bends the ML project loop in an instructive way: the reward is the objective, learning the policy is optimization, but the data isn't a fixed dataset. The agent generates its own data by acting, so exploration (lesson 05) is the data stage happening live at train time. That coupling is the whole personality of RL.
Real-world examples: Game playing (AlphaGo, Atari), robotics, recommendation systems, autonomous driving, resource management, RLHF for tuning language models.
The five pieces
An MDP is a tuple :
| Symbol | Name | Meaning |
|---|---|---|
| States | Situations the agent can be in | |
| Actions | Choices available | |
| Transition | Probability of next state | |
| Reward | Immediate payoff | |
| Discount | How much the future matters |
The loop: in state , the agent picks action , the environment returns reward and next state . Repeat.
Intuition
RL is learning by consequences, like training a dog. No one labels each move "correct." The agent tries actions, gets rewards (treats) or penalties, and gradually discovers a strategy that earns the most reward over time. The hard part: a reward now must be traded off against bigger rewards later.
The Markov property
The "Markov" in MDP means the future depends only on the current state, not the full history:
The state must capture everything relevant. (A chess board position is Markov; the last move alone is not.) This assumption is what makes the recursive Bellman equation valid.
Return and discounting
The agent maximizes the return — cumulative discounted reward, not just the next reward:
The discount does two jobs: it keeps the infinite sum finite, and it sets the agent's horizon. is myopic (grab the nearest reward); is far-sighted (plan for the long game).
Why discount the future?
A reward today beats the same reward in 100 steps — it's more certain and sooner usable (same logic as interest rates). With , a reward 10 steps away is worth of an immediate one. Choosing is choosing how patient the agent is.
Policies and value functions
A policy is the agent's strategy — a mapping from states to actions (possibly stochastic). The goal is the optimal policy that maximizes expected return.
To compare policies we use value functions:
- State value — expected return from state under :
- Action value (Q) — expected return from taking in , then following :
is the more useful of the two for control: if you know , the optimal action is simply — no model of the environment needed.
The Bellman equation
The key insight: value is recursive. The value of a state = immediate reward + discounted value of where you land. For a fixed policy:
And the Bellman optimality equation (the one satisfies) replaces the policy average with a max:
(We use the transition-reward convention here to match the worked code below, where reward is attached to landing in . If reward depends only on , it factors out of the as .)
The recursion that powers all of RL
"The value of where I am equals the best immediate reward plus the discounted value of where I'll be." Every RL algorithm (value iteration, Q-learning, DQN, actor-critic) is ultimately a way of solving or approximating this Bellman equation.
Worked example: value iteration
When and are known, value iteration just applies the Bellman optimality update until stops changing:
import numpy as np
# Tiny MDP: 3 states, 2 actions. Known dynamics.
P = { # P[s][a] -> list of (prob, next_state, reward)
0: {0: [(1.0, 0, 0)], 1: [(1.0, 1, 0)]},
1: {0: [(1.0, 0, 0)], 1: [(1.0, 2, 0)]},
2: {0: [(1.0, 2, 1)], 1: [(1.0, 2, 1)]}, # goal state: reward 1
}
gamma, n_states, n_actions = 0.9, 3, 2
V = np.zeros(n_states)
for it in range(500): # 131 sweeps needed at gamma=0.9
V_new = np.zeros(n_states)
for s in range(n_states):
V_new[s] = max(
sum(p * (r + gamma * V[s2]) for p, s2, r in P[s][a])
for a in range(n_actions)
)
if np.allclose(V, V_new, atol=1e-6):
print(f"converged in {it} iterations"); break
V = V_new
print("V* =", np.round(V, 3))
policy = [int(np.argmax([sum(p*(r+gamma*V[s2]) for p,s2,r in P[s][a])
for a in range(n_actions)])) for s in range(n_states)]
print("optimal actions:", policy)
Step through the loop on the MDP above — every action evaluated, every Bellman backup taken, and the sweep count that γ decides:
Value iteration — Bellman backups, and what γ actually controls
A three-state MDP: s0 and s1 are ordinary, s2 is an absorbing goal that pays 1 every step you sit in it. Both actions are deterministic. Value iteration needs no experience and no exploration — it is given P and R, and simply applies the Bellman optimality update until V stops moving. γ = 0.9, and every V starts at zero.
| state | a0 → (next, reward) | a1 → (next, reward) |
|---|---|---|
| s0 | s0, r=0 | s1, r=0 |
| s1 | s0, r=0 | s2 (goal), r=0 |
| s2 (goal) | s2 (goal), r=1 | s2 (goal), r=1 |
Nothing here is learning. Value iteration is dynamic programming on a known model — the contrast that makes Q-learning's model-free version interesting.
Value iteration on the 3-state MDP above, sweep by sweep. Watch reward information travel backwards from the goal one state per sweep — that propagation speed is why the sweep count grows with distance to reward. The last two steps show what γ does: it sets the contraction rate (30 sweeps at 0.5, 2062 at 0.99), and with one reward changed it flips the optimal policy outright. A myopic agent has not converged badly; it has solved a different problem.
What to notice as you step:
- Reward travels backwards, one state per sweep. After sweep 1 only the goal has value; after sweep 2, ; after sweep 3, . The number of sweeps needed scales with the distance from reward, which is exactly why sparse-reward problems are hard.
- No policy exists until the end. Value iteration optimizes and reads the policy off with a one-step lookahead once has settled — unlike policy iteration, which maintains and improves an explicit policy throughout.
- γ sets the contraction rate. Each sweep shrinks the error by a factor of γ, so convergence takes 20 sweeps at γ = 0.5 and 1375 at γ = 0.99. Caring about the far future is not free.
- The last step changes one reward and lowers γ, and the optimal policy reverses. A myopic agent has not converged badly. It has correctly solved a different problem. γ belongs in the problem specification, not the hyperparameter sweep.
Watch value iteration converge on a 4×4 gridworld — each step is one full sweep, and the arrows show the greedy policy extracted from :
Value Iteration — 4×4 Gridworld
Each sweep applies the Bellman optimality update to every cell. Arrows show the greedy policy: the action that maximises V(s′). Adjust γ to see how the agent's planning horizon changes.
Model-based vs model-free
| Known ? | Method | Examples | |
|---|---|---|---|
| Model-based | Yes | Plan with Bellman directly | Value/policy iteration |
| Model-free | No | Learn from sampled experience | Q-learning, DQN, policy gradient |
In most real problems you don't know the transition dynamics. You can only act and observe. That's the model-free setting the rest of this course tackles, starting with Q-learning.
Exercise
Which of these is NOT one of the five components of a Markov Decision Process?
Need a hint?
The five are states, actions, transitions, rewards, and discount.
Exercise
With discount factor γ = 0.9, what is a reward received 10 steps in the future worth relative to an immediate one?
Need a hint?
Compute 0.9 raised to the 10th power.
Exercise
Set the discount factor γ for an RL agent in a game with ~100-step episodes where future rewards matter.
Need a hint?
γ = 0 → only immediate reward; γ = 1 → all future rewards equally weighted.
Exercise
The Bellman optimality equation expresses the value of a state as what?
Need a hint?
Immediate reward plus something about the future.
Common mistakes
- A non-Markov state: if the state omits relevant history, the MDP framing breaks and learning stalls. Engineer the state to be Markov (e.g. stack frames in Atari).
- in a continuing task: the return diverges; keep .
- Confusing reward with return: reward is the immediate signal; return is the discounted sum. Agents optimize return.
Key takeaways
- An MDP is ; the agent maximizes discounted return.
- The Markov property makes the recursive Bellman equation valid.
- Value functions measure expected return; acts greedily on .
- The Bellman equation underlies every RL algorithm.
Related concepts
- Q-Learning: learning without a model
- Policy Gradient & Actor-Critic: optimizing the policy directly instead
- Partially Observable MDPs (POMDPs): decision-making when the true state is hidden behind noisy observations
- Random Walk: the simplest Markov process; a random-policy agent walks the state space this way