Markov Decision ProcessesOpen in Colab
ML project loop
Data·Hypothesis space·Objective·Optimization·Evaluation·Deployment feedback

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.

Deep dive
The ML Project Loop
Includes runnable notebook

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 (S,A,P,R,γ)(S, A, P, R, \gamma):

SymbolNameMeaning
SSStatesSituations the agent can be in
AAActionsChoices available
P(s′∣s,a)P(s' \mid s, a)TransitionProbability of next state
R(s,a)R(s, a)RewardImmediate payoff
γ∈[0,1)\gamma \in [0,1)DiscountHow much the future matters

The loop: in state sts_t, the agent picks action ata_t, the environment returns reward rt+1r_{t+1} and next state st+1s_{t+1}. 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:

P(st+1∣st,at)=P(st+1∣st,at,st−1,at−1,… )P(s_{t+1} \mid s_t, a_t) = P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots)

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:

Gt=rt+1+γrt+2+γ2rt+3+⋯=∑k=0∞γkrt+k+1G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \dots = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1}

The discount γ\gamma does two jobs: it keeps the infinite sum finite, and it sets the agent's horizon. γ→0\gamma \to 0 is myopic (grab the nearest reward); γ→1\gamma \to 1 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 γ=0.9\gamma = 0.9, a reward 10 steps away is worth 0.910≈0.350.9^{10} \approx 0.35 of an immediate one. Choosing γ\gamma is choosing how patient the agent is.

Policies and value functions

A policy π(a∣s)\pi(a \mid s) is the agent's strategy — a mapping from states to actions (possibly stochastic). The goal is the optimal policy π∗\pi^* that maximizes expected return.

To compare policies we use value functions:

  • State value — expected return from state ss under π\pi:
Vπ(s)=Eπ ⁣[Gt∣st=s]V^\pi(s) = \mathbb{E}_\pi\!\left[G_t \mid s_t = s\right]
  • Action value (Q) — expected return from taking aa in ss, then following π\pi:
Qπ(s,a)=Eπ ⁣[Gt∣st=s, at=a]Q^\pi(s, a) = \mathbb{E}_\pi\!\left[G_t \mid s_t = s,\, a_t = a\right]

QQ is the more useful of the two for control: if you know Q∗Q^*, the optimal action is simply arg⁡max⁡aQ∗(s,a)\arg\max_a Q^*(s,a) — 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:

Vπ(s)=∑aπ(a∣s)∑s′P(s′∣s,a)[R(s,a,s′)+γVπ(s′)]V^\pi(s) = \sum_a \pi(a\mid s)\sum_{s'} P(s'\mid s,a)\big[R(s,a,s') + \gamma V^\pi(s')\big]

And the Bellman optimality equation (the one π∗\pi^* satisfies) replaces the policy average with a max:

V∗(s)=max⁡a∑s′P(s′∣s,a)[R(s,a,s′)+γV∗(s′)]V^*(s) = \max_a \sum_{s'} P(s'\mid s,a)\big[R(s,a,s') + \gamma V^*(s')\big] Q∗(s,a)=∑s′P(s′∣s,a)[R(s,a,s′)+γmax⁡a′Q∗(s′,a′)]Q^*(s,a) = \sum_{s'} P(s'\mid s,a)\Big[R(s,a,s') + \gamma \max_{a'} Q^*(s',a')\Big]

(We use the transition-reward convention R(s,a,s′)R(s,a,s') here to match the worked code below, where reward is attached to landing in s′s'. If reward depends only on (s,a)(s,a), it factors out of the ∑s′\sum_{s'} as R(s,a)R(s,a).)

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 PP and RR are known, value iteration just applies the Bellman optimality update until VV stops changing:

Python
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

1/12

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.

python
1def value_iteration(P, gamma, tol=1e-6):
2 V = [0.0] * n_states
3 for it in range(1000):
4 V_new = [0.0] * n_states
5 for s in range(n_states):
6 # Bellman optimality backup
7 V_new[s] = max(
8 sum(p * (r + gamma * V[s2])
9 for p, s2, r in P[s][a])
10 for a in range(n_actions))
11 if allclose(V, V_new, atol=tol):
12 break # converged
13 V = V_new
14 policy = [argmax([q(s, a) for a in acts])
15 for s in range(n_states)]
16 return V, policy
state
the MDP — deterministic transitions
statea0 → (next, reward)a1 → (next, reward)
s0s0, r=0s1, r=0
s1s0, r=0s2 (goal), r=0
s2 (goal)s2 (goal), r=1s2 (goal), r=1
V — value of each state
s0
0.000
s1
0.000
s2 (goal)
0.000

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, s1s_1; after sweep 3, s0s_0. 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 VV and reads the policy off with a one-step lookahead once VV 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 VV:

Value Iteration — 4×4 Gridworld

S0.000.000.000.000.00#0.000.000.000.000.000.000.000.000.00G+1
sweep0/50
max ΔV—
γ0.90
Goal (reward +1)
Wall (blocked)
V(s): dark → blue = low → high

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 P,RP, R?MethodExamples
Model-basedYesPlan with Bellman directlyValue/policy iteration
Model-freeNoLearn from sampled experienceQ-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.

00.501
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

  1. 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).
  2. γ=1\gamma = 1 in a continuing task: the return diverges; keep γ<1\gamma < 1.
  3. Confusing reward with return: reward is the immediate signal; return is the discounted sum. Agents optimize return.

Key takeaways

  • An MDP is (S,A,P,R,γ)(S, A, P, R, \gamma); the agent maximizes discounted return.
  • The Markov property makes the recursive Bellman equation valid.
  • Value functions V/QV/Q measure expected return; π∗\pi^* acts greedily on Q∗Q^*.
  • The Bellman equation underlies every RL algorithm.

Related concepts

Concept neighbourhood

How this concept connects — click any node to jump there, or explore the whole concept map.

Builds onRelatedGo deeper
Markov Decision ProcessesNeural NetworksProbabilistic Models & EMQ-LearningPolicy Gradient & Actor-C…Exploration Strategies & …Reward ModelsSession-Based & Real-Time…The ML Project LoopPartially Observable MDPs…Random WalkMulti-Agent Reinforcement…