Module 2 — Markov decision processes

The interaction loop of module 1 becomes an object we can reason about the moment we name its five pieces. That object is the Markov decision process (MDP), and every algorithm in this course either exploits its structure or works around its violations.

The five ingredients

An MDP is the tuple (S, A, P, R, γ):

• S: the set of states. On FrozenLake, S = {0, 1, ..., 15} — the 16 cells of a 4×4 grid.
• A: the set of actions. On FrozenLake, A = {0: left, 1: down, 2: right, 3: up}.
• P(s' | s, a): the transition probability of reaching state s' after taking action a in state s.
• R(s, a, s'): the reward received after that transition.
• γ ∈ [0, 1]: the discount factor from module 1.

FrozenLake in its is_slippery=True mode is stochastic on purpose: choosing "right" moves you right with probability 1/3, up with 1/3, down with 1/3. That is not noise added at the end; it is the transition function of the MDP. Ignore it and you will overestimate what a policy can guarantee.

The Markov property

The defining assumption is the one that gives MDPs their name: the future depends on the past only through the present state. Formally, for every history h_t = (s_0, a_0, r_1, ..., s_t):

$$\Pr(s_{t+1} \mid h_t, a_t) = \Pr(s_{t+1} \mid s_t, a_t)$$

The consequence is enormous: an optimal policy only needs to look at s_t, not at how the agent arrived there. The whole storage cost of history collapses to the cost of storing the current state. Every value function, every Q-table, every neural policy in the following modules rests on this.

Where the Markov assumption breaks

The assumption is easy to state and easy to violate. Three concrete cases you will meet in practice:

Partial observation. In Atari's Pong, one frame does not tell you the direction of the ball; you need two. The state you feed the agent is not the true state of the world, and any policy based on a single frame is Markov-blind to velocity. The classical fix is to stack the last four frames, which is exactly what the DQN paper did.

Hidden variables. A patient's response to a drug depends on their genotype, which is not in the state you observe. The problem is technically a POMDP (partially observable MDP), and its algorithms differ.

Non-stationary environment. A trading bot faces a market whose transition rule changes with regulations, competing agents, and time of day. The true P depends on more than (s, a), and a policy learned on last year's data has no guarantee on this year's.

When these break, the algorithms of this course still run — they just optimize the wrong objective. Diagnosing that mismatch is a large part of why RL projects fail silently.

Policy: what the agent actually computes

A policy π is a function from states to actions, or more generally to distributions over actions:

• Deterministic: π(s) = a. One state, one action.
• Stochastic: π(a | s) = probability. Useful for exploration (module 6) and required for policy gradients (module 8).

The agent's goal is to find a policy π* that maximizes the expected return from every state:

$$\pi^* = \arg\max_\pi \; \mathbb{E}_\pi\left[\sum_{t=0}^\infty \gamma^t r_{t+1}\right]$$

An MDP always admits a deterministic optimal policy in the tabular case — a strong theorem that justifies why Q-learning, which outputs one action per state, is not throwing anything away.

FrozenLake formalized

import gymnasium as gym

env = gym.make("FrozenLake-v1", is_slippery=True)
print("states  :", env.observation_space.n)   # 16
print("actions :", env.action_space.n)        # 4

# Inspect the transition table directly - Gymnasium exposes it for FrozenLake:
state, action = 0, 2                          # top-left cell, action = "right"
for prob, next_state, reward, done in env.unwrapped.P[state][action]:
    print(f"P={prob:.2f}  s'={next_state:2d}  r={reward}  terminal={done}")

Running this on cell 0 action right prints three transitions of probability 1/3 each: one goes right to 1, one goes down to 4, one stays at 0 (blocked by the wall). The reward is 0 on all three because the goal is elsewhere. That table is P(s' | s, a) and R(s, a, s') made concrete.

Why FrozenLake first

FrozenLake has 16 states and 4 actions — 64 (state, action) cells fit on one screen. Every value function, every optimal policy, every learning curve of modules 3 to 6 will be visualized on those 64 cells. When the same algorithms move to CartPole in module 7, the state space becomes continuous and neural networks become mandatory — but the mathematics you built here still holds line for line.

Summary

• An MDP is the tuple (S, A, P, R, γ); naming it is what turns a control problem into something we can compute on.
• The Markov property says the future depends on the past only through s_t; it justifies storing only the current state.
• Real problems violate it via partial observability, hidden variables or non-stationarity; frame stacking is the classical patch.
• A policy maps states to actions, deterministic or stochastic; in tabular MDPs an optimal deterministic policy always exists.

Next module: how to score a policy without simulating it forever — value functions and the Bellman equations.