Markov Decision Process (MDP)

Picture training a little delivery robot to cross a busy campus.

Nobody gives it the correct turn at each corner. It learns by trying: drive, bump into things, occasionally earn a point for arriving on time.

And the world is not obedient. The same "turn left" command can end with it going straight, because of a patch of wet grass.

So the learner faces three problems at once:

• Delayed feedback. The decision that earns the reward may happen many steps before the reward arrives. Which step gets the credit?
• Random outcomes. The same action can land you in different places. Outcomes are probabilities, not guarantees.
• Sequential decisions. Every choice changes where the next choice happens. Decisions form a chain, not a pile of separate coin flips.

Reinforcement learning (RL) is the study of an agent that learns by interacting with an environment to maximize cumulative reward. But to analyze that setup rigorously — to actually prove things about learning — we need a precise mathematical object that captures situations, choices, randomness, and scoring, all in one place.

That object is the Markov Decision Process (MDP). Every topic in this phase is built on top of it.

An MDP is a 5-tuple — just a list of five ingredients:

M = (S, A, P, R, γ)

If you have ever played a board game, you already understand all five parts.

• S — the states. Every situation the agent can find itself in: the board positions. Concretely: a grid-world cell, a stock portfolio, or an LLM's current token prefix (the prompt plus everything generated so far).
• A — the actions. The moves allowed in each state: North / South / East / West, buy / hold / sell, or the next token to emit.
• P — the transition dynamics. The world's dice roll. P(s' | s, a) is the probability of landing in state s' after taking action a in state s. This is what makes the game stochastic: you aim left, the dice may still deliver you straight.
• R — the reward function. The immediate points handed out: R(s, a, s') (some books write R(s,a)). One plain number of feedback, right now. This is the reward hypothesis in action: whatever you want the agent to do must be written as points, because points are the only feedback the agent ever sees.
• γ (gamma) — the discount factor, a number in [0, 1]. A house rule for how much future points count compared to points right now.

Numbers for taste — the grid world in the diagram above is a complete MDP:

• States: grid cells plus a terminal goal cell.
• Actions: move North / East / South / West.
• Dynamics: a gust of wind means your intended direction only lands most of the time — the rest of the probability spills into the neighbours.
• Rewards: every step costs −0.04 (a "you are wasting time" penalty), and the goal pays +10.
• Discount: something like γ = 0.9.

And here is the punchline: everything in RL — policies, value functions, Bellman equations, Q-learning — is defined relative to an underlying MDP. Change any of the five ingredients and you have a different game to solve.

The entire edifice rests on one assumption: the Markov property.

Formally, a state S_t is Markov if:

P(S_{t+1} | S_t, A_t) = P(S_{t+1} | S_{t-1}, A_{t-1}, …, S_0, A_0)

In words: the chance of the next state given only (where you are now, what you just did) equals the chance given the entire history of the game. You gain nothing by remembering how you got here.

So the state representation is sufficient — S_t already packs in everything that matters for predicting what happens next.

Two gut checks:

• Grid-world position: Markov. Where you are now fully determines the odds of where you land next. The route you took is irrelevant.
• One camera frame from a self-driving car: usually NOT Markov. A single still image cannot tell you whether the car ahead is braking or parked. That information lives in the past frames — and the future depends on it.

code
Copy
The long tape (what we would fear needing):
  s0 → a0 → s1 → a1 → … → s_t   →   ??? what comes next?

The Markov shortcut (what we actually use):
  (s_t, a_t)   →   s_{t+1}
  the present alone is enough

In practice many real problems are partially observable (a robot's single camera frame is not Markov). Two standard fixes:

1. Feature stacking / recurrent state: concatenate the recent frames, or use an RNN/attention, so the internal representation approximates a Markov state.
2. POMDP formulation: when exact Markovianity matters (poker, dialogue — where the true state is hidden), carry a belief state: a probability distribution over the hidden states, which itself evolves Markov-style.

A single reward is a snapshot. The agent cares about the whole movie.

Because rewards trickle in over time, the thing the agent optimizes is the return G_t — the discounted sum of all future rewards:

G_t = R_{t+1} + γR_{t+2} + γ²R_{t+3} + … = Σ_{k=0}^{∞} γᵏ R_{t+k+1}

γ is a foresight dial:

• γ → 0: future rewards get multiplied by numbers close to zero → the agent chases only the immediate reward (pure myopia).
• γ → 1: the future counts as much as the present → far-sighted agent. Careful: in tasks that never end, the sum can blow up to infinity.

Now tiny numbers. Our delivery robot takes three boring steps, then earns the goal. The trajectory of rewards is: −0.04, −0.04, −0.04, +10. With γ = 0.9, compute the return working backward from the finish line:

• Standing at the goal: G_3 = 10.
• One step back: G_2 = −0.04 + 0.9 × 10 = 8.96.
• Two steps back: G_1 = −0.04 + 0.9 × (−0.04) + 0.9² × 10 = −0.04 − 0.036 + 8.1 = 8.024.
• At the very start: G_0 = −0.04 − 0.036 − 0.0324 + 0.9³ × 10 ≈ 7.18.

Two lessons hide in those numbers:

1. The same +10 is worth more the closer you are to collecting it. Delay is a tax, and γ sets the tax rate.
2. The step penalties are tiny, but a path with more of them loses. "Shortest path" falls out of the arithmetic for free.

Why the discount exists at all: bounded math, time preference, and a little humility about an uncertain future (a reward ten steps away might never arrive).

Two task shapes:

• Episodic tasks (a game that ends): the agent reaches a terminal state and G_t is a finite sum.
• Continuing tasks (a trading bot running forever): discounting is what keeps G_t bounded — if the maximum per-step reward is R_max, then G_t ≤ R_max / (1 − γ). A geometric series: always finite when γ < 1.

def discounted_returns(rewards, gamma=0.99):
    """G_t = R_{t+1} + gamma*R_{t+2} + ... (backward recursion)."""
    returns = [0.0] * len(rewards)
    running = 0.0
    for t in reversed(range(len(rewards))):
        running = rewards[t] + gamma * running
        returns[t] = running
    return returns

# Trajectory: small step penalties, one terminal bonus
print(discounted_returns([-0.04, -0.04, -0.04, 10.0], gamma=0.9))

Everything in an MDP happens inside one loop. At every timestep t:

code
Copy
       ┌──────────────┐   action a_t     ┌───────────────────┐
       │    AGENT     │ ───────────────► │   ENVIRONMENT     │
       │  (the brain) │                  │  (the world: P,R) │
       └──────────────┘ ◄─────────────── └───────────────────┘
                      next state s_{t+1},
                      reward r_{t+1}

1. The environment sits in state s_t.
2. The agent picks an action a_t (with its current decision rule — the policy, next topic).
3. The transition kernel P rolls the dice → s_{t+1}; the reward function R emits r_{t+1}.
4. Repeat.

The resulting sequence s_0, a_0, r_1, s_1, a_1, r_2, … is a trajectory (one episode). All the learning algorithms you will meet simply chew on trajectories like this one.

The Markov property is the promise that step 3 only needs (s_t, a_t) — no re-reading of the whole tape. The mermaid diagram above draws exactly this loop for a three-cell grid ending at the +10 goal with −0.04 step costs.

Carry one analogy through everything that follows: an MDP is a board game, and the learning agent is a player trying to get good at it.

• S = every square that can ever appear on the board.
• A = the moves printed on your player card.
• P = a die hidden behind the board: you intend North, the die sometimes delivers you elsewhere.
• R = the points you collect along the way — points are the ONLY feedback.
• γ = the house rule: "points collected later count for a bit less."
• Markov property = the board shows everything that matters; no hidden notes required.

Every topic in this phase is one question about this game:

• What is my move rule for each square? → the policy (topic 197).
• How good is each square overall? → value functions (topic 198).
• Can the whole game be decomposed into one square plus the rest? → Bellman equations (topic 199).
• What if I never get to see the die (no model of P) and must learn by playing? → TD learning and Q-learning (topics 200–201).

Notice what the analogy does not include: no oracle telling you the best move, no map of the board, no guaranteed points each turn. Those omissions are exactly the reinforcement-learning problem.

Why does a modern AI engineer care? Because today's biggest RL systems are literally MDP solvers. Fine-tuning ChatGPT-class models with RLHF treats the conversation as the board: the state is the prompt plus the tokens generated so far, the action is the next token, and the reward is a preference score handed out at the end. Robotics, recommendations, ad bidding, ops scheduling — all get cast as MDPs first, then trained.

In code, the interface you will actually touch is Gymnasium (the modern successor to OpenAI Gym). The Gymnasium API is an MDP interface: reset() samples an initial state, and step(action) returns the five-tuple (obs, reward, terminated, truncated, info), implementing P and R under the hood. terminated means a genuine terminal state (goal or death); truncated means "we cut the episode short, e.g. time limit" — an important distinction when learning returns.

Below, a one-dimensional random walk written out as a raw MDP: states 0..4 (both ends terminal), actions left/right, and the intended move succeeds only with probability P = 0.9 — the hidden die, made explicit. Reaching state 4 pays reward 1.0. Run it a few times and watch the die kick you back.

import numpy as np

S = list(range(5))          # states 0..4, 0 and 4 are terminal
A = ['left', 'right']       # actions
P = 0.9                     # prob of intended move (stochastic dynamics)
GAMMA = 1.0                 # undiscounted episodic task

def step(s, a, rng):
    intended = 1 if a == 'right' else -1
    moved = intended if rng.random() < P else -intended
    s2 = max(0, min(4, s + moved))
    reward = 1.0 if s2 == 4 else 0.0
    done = s2 in (0, 4)
    return s2, reward, done

rng = np.random.default_rng(0)
s = 2
for _ in range(5):
    s, r, done = step(s, 'right', rng)
    print(f"state={s} reward={r} done={done}")
    if done:
        break