Every reinforcement learning algorithm in this track rests on one mathematical object: the Markov Decision Process (MDP). Richard Bellman introduced the framework in the 1950s for operations research, and it remains the language in which RL problems are stated, analysed and solved. Mastering it makes the rest of the track straightforward.
Definition#
An MDP is a tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$:
- $\mathcal{S}$ — the set of states;
- $\mathcal{A}$ — the set of actions;
- $P(s' \mid s, a)$ — the transition probability of reaching $s'$ after taking $a$ in $s$;
- $R(s, a, s')$ (or $R(s, a)$) — the expected reward;
- $\gamma \in [0, 1]$ — the discount factor.
More generally, the dynamics $p(s', r \mid s, a)$ give the joint probability of next state and reward.
The Markov property#
The future depends only on the present state and action, not on the history:
The state must therefore summarise everything relevant from the past. In chess the board position (plus whose turn, castling rights, etc.) is Markov. For a moving robot, position alone is not — velocity must be included. Designing a Markov state representation is a key modelling step; stacking recent frames in Atari games is a common trick to recover velocity information.
A worked example: a gridworld#
A 4×4 grid; the agent moves up/down/left/right; each move costs −1; the top-left and bottom-right cells are terminal. With probability 0.8 the agent moves as intended and with 0.2 it slips to a random neighbouring direction — a stochastic transition model.
import numpy as np
N = 4
states = [(r, c) for r in range(N) for c in range(N)]
terminal = {(0, 0), (N - 1, N - 1)}
actions = {"U": (-1, 0), "D": (1, 0), "L": (0, -1), "R": (0, 1)}
def move(s, a):
r, c = s[0] + actions[a][0], s[1] + actions[a][1]
return (r, c) if 0 <= r < N and 0 <= c < N else s # bump into wall -> stay
def transitions(s, a, slip=0.2):
"""Return list of (probability, next_state, reward)."""
if s in terminal:
return [(1.0, s, 0.0)]
outcomes = [(1 - slip, move(s, a), -1.0)]
others = [b for b in actions if b != a]
outcomes += [(slip / len(others), move(s, b), -1.0) for b in others]
return outcomes
print(transitions((1, 1), "R"))We will solve this MDP with dynamic programming in a later lecture.
Episodic and continuing tasks#
- Episodic tasks end in terminal states (a game, a maze run); returns are finite sums.
- Continuing tasks go on indefinitely (process control); discounting ($\gamma < 1$) or average-reward formulations keep returns finite.
Time limits in simulators create truncation, which differs from true termination: at truncation, the future value is not zero and should be bootstrapped — Gymnasium distinguishes terminated from truncated for exactly this reason.
Policies#
A policy $\pi(a \mid s)$ fully specifies behaviour. For a finite MDP there always exists an optimal policy that is deterministic and stationary (depends only on the current state). Stochastic policies are still useful for exploration, for partially observable problems and in games against adversaries.
Partial observability: POMDPs#
Often the agent cannot observe the full state: a robot's sensors are noisy; a poker player cannot see others' cards; a conversational agent does not know the user's intent. A Partially Observable MDP adds observations $o \sim O(o \mid s)$. The optimal agent maintains a belief state — a probability distribution over states updated with Bayes' rule (like the HMM filtering algorithm). In deep RL, recurrent networks or transformers over observation histories approximate this memory.
Formulating real problems as MDPs#
Consider allocating a limited supply of relief kits across distribution points each week:
- State: stock levels, recent demand at each point, weather forecast.
- Actions: how many kits to send to each point.
- Transitions: stochastic demand and delivery delays.
- Reward: needs met minus penalties for shortages and waste — and here, reward design embeds ethical choices about fairness between locations.
- Discount: how much future shortages matter relative to today.