On this page The unified language of nearly all RL problems — the 5-tuple, the Markov property, discounted return, policies, value functions, and the Bellman equation; plus the three solution routes from a known model to an unknown one.

Markov Decision Process (MDP)

In one sentence: this page explains the Markov decision process (MDP) — the unified mathematical language behind almost every reinforcement learning problem. By the end, you'll be able to cast any sequential-decision problem as an MDP 5-tuple, write down its policy, value functions, and Bellman equations, and tell which of the three solution routes to take.

If you're still unsure what problems RL actually solves, start with What Is Reinforcement Learning; if you're after terminology definitions, this page is the anchor entry of the Glossary.

1. Why We Need MDPs: Sequential Decisions Need a Common Language

Most problems faced by humans and machines are not one-shot decisions like "classify this image" — they are chains of decisions:

Playing chess: every move shapes all the positions that follow;
Autonomous driving: dozens of steering, braking, and lane-change decisions each second, all interlocked;
Dialogue: every utterance influences the other side's next reply;
Robotic grasping: the torque applied at each frame determines whether the object is caught in the end.

These problems share one structure: the current decision affects future states, and future states shape future decisions. If we invented a bespoke formalism for every such problem, no general theory would ever emerge. The value of the MDP is that it captures sequential decision-making with just five ingredients, so every algorithm — dynamic programming, Q-learning, PPO, SAC — operates in the same language.

text

       ┌────────────────────────────────────────────┐
       │               The MDP 5-tuple              │
       │                                            │
       │  (S, A, P, R, γ)                           │
       │   ├─ S   set of states                     │
       │   ├─ A   set of actions                    │
       │   ├─ P   transition probability P(s'|s,a)  │
       │   ├─ R   reward function R(s,a,s')         │
       │   └─ γ   discount factor γ ∈ [0,1)         │
       └────────────────────────────────────────────┘

Mnemonic
"States, Actions, Transitions, Rewards, Discount" — remember the five letters S, A, P, R, γ and you've remembered the entire MDP.

1. The 5-Tuple, Piece by Piece

Ingredient	Notation	Meaning	Example (CartPole balance)
State S	$s \in \mathcal{S}$	Everything the agent can observe that matters for the decision	Cart position, velocity, pole angle, angular velocity (a 4-dim continuous vector)
Action A	$a \in \mathcal{A}$	The operations available in each state	Push left / push right (2 discrete actions)
Transition prob. P	$P(s' \mid s, a)$	Probability of landing in next state s' after taking action a in state s	How the pole angle evolves after a push (dictated by physics)
Reward R	$R(s, a, s')$	Immediate feedback signal quantifying "how good was this step"	Pole still standing = 0, fallen = -1 (or +1 per step)
Discount γ	$\gamma \in [0, 1)$	Depreciation factor for future rewards relative to immediate ones	0.99: cares about roughly the next 99 steps

Note that $P$ is a probability distribution: for any fixed $(s,a)$, $\sum_{s'} P(s' \mid s,a) = 1$. It doesn't tell you where the next state will definitely be — it tells you how probability mass splits across the possible next states. The reward $R$ may be written $R(s,a,s')$ (depending on the state you arrive at) or simplified to $R(s,a)$ or even $R(s)$; notation varies slightly across textbooks, but the meaning is the same.

2. The Markov Property and State Representation

1. The Markov Property

The soul of an MDP is the Markov property:

The future depends only on the current state and the current action — not on the history that came before.

In probabilistic form:

$$ P(s_{t+1} \mid s_t, a_t, s_{t-1}, a_{t-1}, \dots, s_0, a_0) = P(s_{t+1} \mid s_t, a_t) $$

In other words, once $s_t$ is given, the entire past is redundant. Think of it as the memory of a goldfish: the state $s_t$ already contains everything needed to act optimally — how the agent got here doesn't matter.

2. State Representation: The Most Overlooked Engineering

The Markov property is not handed to you for free — it hinges on how you define the state. Hardly any real-world problem is naturally Markov; engineers effectively manufacture the property through state design:

Problem	Naive state (fails)	Good state (satisfies or approximates it)
Autonomous driving	A single camera frame	Stacked frames + ego velocity + map localization (one frame shows no object velocity)
Atari games	A single frame	The last 4 frames stacked (one frame shows no ball velocity)
Trading	The current price	Price-sequence features + position + holdings (a single price carries no trend)
Dialogue	The previous utterance	The full conversation history (a reply depends on context)

Common pitfall: mistaking "partially observable" for "Markov"
Most real problems are actually POMDPs (partially observable MDPs): the agent cannot see the full state, only an observation $o_t$. Observations $o_t$ then fail the Markov property, and treating the problem as a plain MDP degrades the decisions. The usual engineering compromises:
Fold history into the state (frame stacking, dialogue history, sliding windows);
Compress history into a hidden state with an RNN;
Accept the approximation and let exploration and generalization cover the gap. Academia treats POMDPs as a field of their own; most "good-enough" industrial solutions are option 1.

3. Return G and the Discount Factor γ

1. The Agent's Goal Is to Maximize Return, Not Any Single Reward

A one-step reward $r_t$ is just a fragment. What the agent optimizes is the return accumulated over an entire trajectory — most commonly the discounted return:

$$ G_t = r_{t+1} + \gamma r_{t+2} + \gamma^2 r_{t+3} + \cdots = \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} $$

It can also be written recursively (we'll reuse this constantly when deriving the Bellman equation):

$$ G_t = r_{t+1} + \gamma G_{t+1} $$

2. Why γ Must Be Less Than 1

The discount factor does three jobs, and all three matter:

Job of γ	Explanation
Mathematical convergence	If γ<1 and rewards are bounded, the infinite sum converges; with γ=1 the infinite-horizon return can diverge
Capturing uncertainty	The farther the future, the less certain it is — a dollar today is worth more than a dollar tomorrow (the economics analogy is "discounting")
Tuning the horizon	As γ approaches 1 the agent "looks far" (Go can even use γ=1, since games end); a small γ makes it "impatient"

Some intuition: with γ=0.9, a reward 10 steps away is worth only $0.9^{10}\approx 0.35$ times its face value; with γ=0.99 it's still worth 0.90 at 10 steps and 0.37 at 100. The "effective horizon" is roughly $1/(1-\gamma)$: γ=0.99 means the agent plans about 100 steps ahead, while γ=0.9 means only about 10.

Practical values
Control problems typically use γ ∈ [0.95, 0.999]; sparse-reward, long-horizon problems (Go, dialogue) use values close to 1; genuinely myopic problems (one-step decisions) can even set γ=0, which collapses the MDP into a multi-armed bandit (see Exploration vs Exploitation and Multi-Armed Bandit).

3. Two Kinds of Return: Finite-Horizon vs Infinite-Horizon

Episodic: the task has a terminal state (game over, reaching the finish line), $T$ is finite, and the return is $G_t = r_{t+1}+\gamma r_{t+2}+\cdots+\gamma^{T-t-1}r_T$. Examples: a game of chess, a round of dialogue.
Continuing: there is no termination, $T=\infty$, and convergence rests on γ<1. Examples: real-time control, recommendation systems.

An episodic task can be viewed as a special case of a continuing one: declare the terminal state an "absorbing state" (once entered, the agent stays forever and receives zero reward), and the two formalisms unify.

4. Policy, State Value V, and Action Value Q

1. The Policy π: the Agent's "Manual of Behavior"

A policy $\pi(a \mid s)$ is a mapping from states to action probabilities: the probability of taking action $a$ in state $s$. It defines how the agent acts.

Deterministic policy: $\pi(s) = a$ — exactly one action per state;
Stochastic policy: $\pi(a \mid s)$ gives a probability distribution over actions.

Why stochastic at all? Two reasons. First, exploration demands it (the agent must keep trying roads it hasn't taken). Second, under uncertainty the optimal policy is itself stochastic — in poker, for instance, a purely deterministic strategy can be exploited by opponents, so random "bluffing" is optimal.

2. The State-Value Function V

The state-value function $V^\pi(s)$ is the expected return from state s onward when acting according to policy π:

$$ V^\pi(s) = \mathbb{E}\pi \left[ G_t \mid s_t = s \right] = \mathbb{E}\pi \left[ \sum_{k=0}^{\infty} \gamma^k r_{t+k+1} \mid s_t = s \right] $$

Two key points:

It is an expectation: the future is random (transitions and possibly the policy itself), so value lives on average;
It depends on the policy: switch policies and the value of the same state changes. That's why $V^\pi$ is also called the "performance of policy π."

Intuition: $V^\pi(s)$ answers "if I keep playing this way, how much do I expect to win on average from here?"

3. The Action-Value Function Q

The action-value function $Q^\pi(s,a)$ is the expected return from state s when you take action a first and follow policy π afterwards:

$$ Q^\pi(s, a) = \mathbb{E}_\pi \left[ G_t \mid s_t = s, a_t = a \right] $$

The relationship between them:

$$ V^\pi(s) = \sum_a \pi(a \mid s) , Q^\pi(s, a) $$

That is, the state value is the probability-weighted average of action values under the policy. Intuition: Q answers "how much is this action worth," while V answers "how much is this position worth."

Why engineers reach for Q more often than V
V can only tell you whether a position is good — it doesn't tell you what to do. Q compares "this action vs that action" directly, and a policy falls straight out of it (pick the action with the highest Q). That's why tabular Q-learning and, later, deep DQN both learn Q. V still earns its keep as a baseline in policy gradients / Actor-Critic — see Value-Based Learning and The Actor-Critic Family.

5. The Bellman Equation: Where All RL Math Begins

1. Intuition: Value Decomposes into "Now + Future"

The Bellman equation says one thing: the value of the current state = the immediate reward + the discounted value of the next state. Since $G_t = r_{t+1} + \gamma G_{t+1}$, taking expectations on both sides gives:

$$ V^\pi(s) = \sum_a \pi(a \mid s) \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma V^\pi(s') \right] $$

Read the formula term by term:

$\sum_a \pi(a \mid s)$: the policy assigns a probability to each action, and every action's value is weighted by it;
$\sum_{s'} P(s' \mid s,a)$: the environment may move to any of the $s'$ outcomes, weighted the same way;
$R(s,a,s') + \gamma V^\pi(s')$: this step's reward plus the discounted value of the next step.

The action-value version follows the same logic:

$$ Q^\pi(s,a) = \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma \sum_{a'} \pi(a' \mid s') Q^\pi(s', a') \right] $$

2. The Bellman Optimality Equation

Define the optimal value function $V^*(s) = \max_\pi V^\pi(s)$ — the most value any policy can achieve from state s. The optimal policy picks the action with the highest Q in every state, which yields the Bellman optimality equation:

$$ V^(s) = \max_a \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma V^(s') \right] $$

$$ Q^(s,a) = \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma \max_{a'} Q^(s', a') \right] $$

Intuition: the Bellman optimality equation turns "find the optimal policy" into "solve a system of mutually dependent equations." Notice that it swaps $\sum_a \pi$ for $\max_a$ — an optimal policy puts probability 1 on an optimal action and 0 on the rest.

3. Why the Bellman Equation Is "the Foundation of Every Algorithm"

Almost every RL algorithm is some deformation or approximation of the Bellman equation:

Algorithm family	Relationship to the Bellman equation
Value iteration	Apply the Bellman optimality equation as an update, over and over
Policy iteration	Use the Bellman equation for policy evaluation
TD / Q-learning	Replace the sum over $s'$ with a single sample (a sampled version of the Bellman update)
DQN	Approximate $Q^*$ with a neural network whose training target enforces the Bellman equation (the TD error)
Policy gradient	Never enforces the Bellman equation explicitly, but still optimizes return

Does the Bellman equation require the model P and R?
Writing the Bellman equation down requires knowing $P(s'|s,a)$ and $R$. But Q-learning and TD need no model — they use sampled transitions $(s,a,r,s')$ to "approximate" the sums in the formula. This is precisely the watershed between the "model known" and "model unknown" solution routes; see Section 7.

6. A Grid-World Mini-Example: Putting Every Symbol Above to Work

Take the 3×4 grid world — the classic example from the Sutton & Barto book:

text

  ┌─────┬─────┬─────┬─────┐
  │  s1 │  s2 │  s3 │ +1  │   +1 = goal (positive reward)
  ├─────┼─────┼─────┼─────┤
  │  s4 │  s5 │  s6 │ -1  │   -1 = trap (negative reward)
  ├─────┼─────┼─────┼─────┤
  │  s7 │  s8 │  s9 │  s10│   s7 = start
  └─────┴─────┴─────┴─────┘

States: 11 cells (including the goal and the trap; after the trap, an absorbing state);
Actions: up, down, left, right;
Key twist: actions are noisy — try to move up and with 80% probability you actually go up, 10% you slip left, 10% you slip right (hitting a wall means staying put);
Rewards: entering the +1 or -1 cell pays the corresponding reward; every other step pays 0; γ=0.9;
Termination: the episode ends once the goal or the trap is entered.

1. First, Value a "Brainless" Policy (Policy Evaluation)

Suppose the "uniformly random" policy: all four directions equally likely (25% each) from every cell. Let's compute $V^\pi(s)$ by hand. Start with $s_3$, the cell closest to the goal:

$$V(s_3) = 0.25 \cdot \gamma V(\text{goal}) + 0.25 \cdot \gamma V(\text{wall above} \to \text{stay in } s_3) + \dots$$

Since moving up from $s_3$ reaches +1 with 80% probability under the optimal policy, its value ends up clearly higher than the other cells'. A full solution requires iteration (the algorithm in step 2 below); here we only point at the direction of the answer: cells closer to the goal along shorter paths carry higher value, while cells near the trap get dragged down.

2. Tabular Algorithm: Value Iteration in Three Steps

Value iteration simply uses the Bellman optimality equation as an update rule:

$$ V_{k+1}(s) = \max_a \sum_{s'} P(s' \mid s,a) \left[ R(s,a,s') + \gamma V_k(s') \right] $$

Start from $V_0(s)=0$ and iterate until convergence:

Iteration	s7 (start)	s3 (near goal)	s6 (next to trap)	Notes
k=0	0	0	0	All zeros
k=1	0	0.8×1=0.8	0.8×(-1)=-0.8	Rewards one step away start to "light up"
k=2	≈0.5	≈0.8	≈-0.8	Information diffuses outward

Once it converges, the policy reads: up in $s_3$, up in $s_8$, left in $s_9$ — a safe path that skirts the trap.

The intuition behind value iteration
Each round, value information ripples outward from the reward sources like a wave. After k iterations, the agent "sees" k steps ahead. This is the prototype of every bootstrapping algorithm that follows.

7. Three Solution Routes: From "Model Known" to "Model Unknown"

The Bellman optimality equation hands us the answer on paper, but solving it requires knowing $P$ and $R$ — something we almost never have in reality. RL has therefore evolved three solution routes:

text

                          ┌────────────────────────────────────┐
                          │      Model known: P, R             │
                          │      Dynamic programming (DP)      │
                          │      Policy / value iteration      │
                          └─────────────────┬──────────────────┘
                                            │ model unavailable in practice
              ┌─────────────────────────────┴─────────────────────────────┐
              │  Model unknown, but you can interact                      │
              │  Learn from samples (model-free)                          │
              │  ├── Monte Carlo: learn only after full episodes          │
              │  └── Temporal-difference: learn every step (Q-learning)   │
              └─────────────────────────────┬─────────────────────────────┘
                                            │ state space too large or continuous
              ┌─────────────────────────────┴─────────────────────────────┐
              │  Function approximation / deep RL                         │
              │  DQN / PPO / SAC (neural nets as value or policy)         │
              └───────────────────────────────────────────────────────────┘

Route	Requires	Pros	Cons	Representative methods
Dynamic programming	The full model P, R	Theoretically guaranteed and exact	Real-world models almost never exist; intractable for large state spaces	Policy iteration, value iteration
Monte Carlo	Interaction with the environment, complete episodes	Model-free, unbiased	High variance; must wait for the episode to end	First-visit MC
Temporal-difference (TD)	Interaction, incremental per-step updates	Model-free, low variance, online	Biased (depends on initial estimates)	TD(0), Q-learning, SARSA
Deep RL	Model-free + neural networks	Handles continuous, high-dimensional states	Sample-inefficient, unstable, hard to tune	DQN, PPO, SAC

How this handbook is organized
The three routes map directly onto this module's spine: dynamic programming and TD form the first half of Value-Based Learning; learning a policy directly is Policy Gradient Methods; if you also want to learn the "environment model" and exploit it, see Model-Based RL and World Models; the mathematical background lives in the Math Primer.

8. Common Misconceptions and Pitfalls (Interview Favorites)

Pit 1: Confusing "Return" with "One-Step Reward"

The objective is the expected discounted return $\mathbb{E}[G_t]$, not any single reward. Reward is the signal; return is the objective. However well-designed the rewards are, get the return wrong (e.g., γ=0) and the agent turns myopic.

Pit 2: Assuming the Markov Property Belongs to the Environment

The Markov property is a property of the state representation, not of the environment itself. The same physical process fails with a single frame and passes with four stacked frames. State design is modeling work.

Pit 3: Forgetting That the Bellman Equation Presumes a Known Model

The Bellman optimality equation contains an explicit sum over $P(s'|s,a)$. Many beginners, working through the derivation of TD, wonder "why doesn't Q-learning need a model?" — because Q-learning replaces the sum with a single sample $r + \gamma \max Q(s',a')$, which is equivalent in expectation. Details in Value-Based Learning.

Pit 4: Mixing Up V and Q

V has no action in it; Q does; and $\max_a Q^(s,a) = V^(s)$. Engineers pick Q because a policy drops straight out of it; in research papers V often serves as a baseline. Before writing down any equation, ask yourself: "is this page learning V or Q?"

Pit 5: Picking γ by Gut Feel

γ is a hyperparameter. Too large → high variance, slow convergence, hypersensitivity to distant rewards; too small → myopia, no long-term strategy. Work backwards from "effective horizon ≈ 1/(1−γ)": if the task's critical decisions span 50 steps, then γ ≈ 0.98~0.99.

9. How This Page Relates to the Rest of the Site

The MDP is the site's root node:

text

                       ┌───────────────────────┐
                       │    MDP (this page)    │
                       └───────────┬───────────┘
              ┌────────────────────┼────────────────────┐
              ▼                    ▼                    ▼
      ┌───────────────┐    ┌───────────────┐    ┌──────────────────┐
      │ Value-based   │    │ Policy        │    │ Model-based RL   │
      │ learn Q, then │    │ gradient      │    │ learn the model, │
      │ derive policy │    │ learn policy  │    │ then plan        │
      └───────┬───────┘    │ directly      │    └────────┬─────────┘
              │            └───────┬───────┘             │
              │                    │                     │
              └────────────┬───────┘                     │
                           ▼                             ▼
                ┌─────────────────────┐       ┌────────────────────┐
                │ Actor-Critic        │       │ RLHF / Offline RL  │
                │ the two routes      │       │ applying MDPs to   │
                │ converge here       │       │ the real world     │
                └─────────────────────┘       └────────────────────┘

Without the MDP, the other eleven concept pages are castles in the air; with this page down, value-based learning is just "approximating the Bellman equation with a neural network";
Policy Gradient Methods attack from a different angle: skip value learning and optimize the policy's parameters directly;
Model-Based RL and World Models explicitly learn $P$ and $R$;
If the math background feels thin, patch it up in the Math Primer: expectation, conditional expectation, and Markov chains all feed directly into this page;
When the terminology slips, revisit the Glossary.

References

Sutton, R. S., & Barto, A. G. (2018). Reinforcement Learning: An Introduction (2nd ed.). MIT Press. Ch. 3 (MDPs and value functions), Ch. 4 (dynamic programming), and Ch. 17 (a primer on POMDPs). Free official edition: http://incompleteideas.net/book/the-book-2nd.html
Bellman, R. (1957). Dynamic Programming. Princeton University Press. The original source of the Bellman equation and the principle of optimality.
Puterman, M. L. (2014). Markov Decision Processes: Discrete Stochastic Dynamic Programming. Wiley. A rigorous, mathematical treatment of MDPs.
Silver, D. (2015). UCL Course on RL (Lectures 1–3): a meticulous treatment of MDPs and DP. Public slides: https://www.davidsilver.uk/teaching/

Markov Decision Process (MDP)

Markov Decision Process (MDP) ​

1. Why We Need MDPs: Sequential Decisions Need a Common Language ​

1. The 5-Tuple, Piece by Piece ​

2. The Markov Property and State Representation ​

1. The Markov Property ​

2. State Representation: The Most Overlooked Engineering ​

3. Return G and the Discount Factor γ ​

1. The Agent's Goal Is to Maximize Return, Not Any Single Reward ​

2. Why γ Must Be Less Than 1 ​

3. Two Kinds of Return: Finite-Horizon vs Infinite-Horizon ​

4. Policy, State Value V, and Action Value Q ​

1. The Policy π: the Agent's "Manual of Behavior" ​

2. The State-Value Function V ​

3. The Action-Value Function Q ​

5. The Bellman Equation: Where All RL Math Begins ​

1. Intuition: Value Decomposes into "Now + Future" ​

2. The Bellman Optimality Equation ​

3. Why the Bellman Equation Is "the Foundation of Every Algorithm" ​

6. A Grid-World Mini-Example: Putting Every Symbol Above to Work ​

1. First, Value a "Brainless" Policy (Policy Evaluation) ​

2. Tabular Algorithm: Value Iteration in Three Steps ​

7. Three Solution Routes: From "Model Known" to "Model Unknown" ​

8. Common Misconceptions and Pitfalls (Interview Favorites) ​

Pit 1: Confusing "Return" with "One-Step Reward" ​

Pit 2: Assuming the Markov Property Belongs to the Environment ​

Pit 3: Forgetting That the Bellman Equation Presumes a Known Model ​

Pit 4: Mixing Up V and Q ​

Pit 5: Picking γ by Gut Feel ​

9. How This Page Relates to the Rest of the Site ​

Further Reading ​

References ​

Markov Decision Process (MDP)

1. Why We Need MDPs: Sequential Decisions Need a Common Language

1. The 5-Tuple, Piece by Piece

2. The Markov Property and State Representation

1. The Markov Property

2. State Representation: The Most Overlooked Engineering

3. Return G and the Discount Factor γ

1. The Agent's Goal Is to Maximize Return, Not Any Single Reward

2. Why γ Must Be Less Than 1

3. Two Kinds of Return: Finite-Horizon vs Infinite-Horizon

4. Policy, State Value V, and Action Value Q

1. The Policy π: the Agent's "Manual of Behavior"

2. The State-Value Function V

3. The Action-Value Function Q

5. The Bellman Equation: Where All RL Math Begins

1. Intuition: Value Decomposes into "Now + Future"

2. The Bellman Optimality Equation

3. Why the Bellman Equation Is "the Foundation of Every Algorithm"

6. A Grid-World Mini-Example: Putting Every Symbol Above to Work

1. First, Value a "Brainless" Policy (Policy Evaluation)

2. Tabular Algorithm: Value Iteration in Three Steps

7. Three Solution Routes: From "Model Known" to "Model Unknown"

8. Common Misconceptions and Pitfalls (Interview Favorites)

Pit 1: Confusing "Return" with "One-Step Reward"

Pit 2: Assuming the Markov Property Belongs to the Environment

Pit 3: Forgetting That the Bellman Equation Presumes a Known Model

Pit 4: Mixing Up V and Q

Pit 5: Picking γ by Gut Feel

9. How This Page Relates to the Rest of the Site

Further Reading

References