Markov Decision Process

Definition

A Markov Decision Process (MDP) is the formal object every RL algorithm optimizes: a model of sequential decision-making in which an agent in a state picks an action, receives a scalar reward, and transitions to a new state — with the defining property that the next state depends only on the current state and action, not the full history. It is the substrate on which value functions, the policy gradient, and all downstream methods are defined.

Key math

An MDP is a tuple $\mathcal{M}=(\mathcal{S},\mathcal{A},P,R,\gamma )$ with (optional) initial-state distribution ${\rho }_0$:

• $\mathcal{S},\mathcal{A}$ — state / action spaces
• $P(s^{\prime }\mid s,a)$ — transition kernel, Markov by construction
• $R(s,a)$ — expected immediate reward
• $\gamma \in [0,1]$ — discount factor

Markov property — the state is a sufficient statistic of history:
$P(s_{t+1}\mid s_t,a_t,\dots ,s_0,a_0)=P(s_{t+1}\mid s_t,a_t)$

A policy $\pi (a\mid s)$ induces a trajectory distribution that factorizes cleanly because of the Markov property:
$p_{\pi }(\tau )={\rho }_0(s_0){\prod }_{t\ge 0}\pi (a_t\mid s_t)P(s_{t+1}\mid s_t,a_t)$

The return $G_t={\sum }_{k\ge 0}{\gamma }^k{r}_{t+k}$ (recursion $G_t=r_t+\gamma G_{t+1}$) defines the objective
$J(\pi )={\mathbb{E}}_{\tau \sim p_{\pi }}[G_0],{\pi }^{\ast }=\arg {\max }_{\pi }J(\pi ).$

Why it matters

LLM generation is an MDP: state $s_t=(x,y_{1:t})$ is the prompt plus tokens so far, action $a_t$ is the next token, policy ${\pi }_{\theta }$ is the softmax over the vocabulary, and the transition is a deterministic append ($P$ is a delta). Two consequences: the state is trivially Markov (it is the full prefix), and $\log p_{\pi }(\tau )={\sum }_t\log {\pi }_{\theta }(y_{t+1}\mid s_t)$ is exactly the sequence log-likelihood — fully differentiable, reusing the pretraining forward/backward pass. Reward is typically sparse and terminal (a single reward-model or verifier score at EOS), which makes credit assignment the central challenge that the advantage function exists to solve.

Taught in

• 01-mdps-and-the-rl-objective — full development: Markov property, the MDP tuple, returns, the objective $J(\pi )$, Bellman equations, and the LLM-as-MDP mapping.

See also

• value-function — $V^{\pi },Q^{\pi }$ and the Bellman expectation equations
• advantage-function — the credit-assignment quantity on an MDP
• policy-gradient-theorem — how to climb $J(\pi )$ by sampling
• rl-for-llms — the broader curriculum