Markov decision process (MDP): definition, example and how to solve one

A Markov decision process (MDP) is the mathematical model of a decision problem in which an agent repeatedly observes a state, picks an action, and receives a reward and a new state drawn from probabilities that depend only on the current state and action. It is written as a tuple of states, actions, transition probabilities, rewards and a discount factor, and solving it means finding a policy that maximises expected discounted reward. Almost every reinforcement learning algorithm is a method for solving an MDP whose probabilities the agent does not know.

This page builds one small MDP from scratch, the five-by-five reference gridworld used throughout our reinforcement learning series, and uses it to make every part of the definition concrete. You can click any cell to see its transition probabilities, sample a thousand episodes and compare them with the exact answer, and watch the optimal policy change character when the discount factor moves from 0.9 to 0.99. Every number below comes from a seeded numpy simulation or an exact linear solve that you can rerun from the code at the end.

A concrete example: the reference gridworld#

Picture a robot on a five-by-five floor. It starts in the bottom-left corner, marked S. The top-right cell is a charging dock worth +1 when the robot reaches it; one cell below and to the left of the dock is a stairwell worth $-1$. Three cells are walls. The floor is slippery: when the robot tries to move in a direction it succeeds 80% of the time, and otherwise slides to one side or the other, 10% each. Bumping into a wall or the edge of the floor leaves it where it was. Reaching the dock or the stairwell ends the episode.

That paragraph is already a complete MDP. The states are the 22 cells the robot can occupy (25 cells minus 3 walls), two of which are terminal. The actions are up, right, down and left. The transition probabilities are the 80/10/10 slip rule plus the walls. The reward is +1 for entering the dock, $-1$ for entering the stairwell and 0 for every other move. The one thing the story did not say is how much the robot should care about reward later rather than sooner. That is the discount factor, and we set it to $\gamma =0.9$ unless stated otherwise.

What are the components of a Markov decision process?#

The formulation goes back to Bellman [1], and Puterman's textbook remains the standard reference for its theory [2]. Each element of the tuple answers one question about the problem. Getting each one right is most of the work of applying reinforcement learning, because an algorithm can only optimise what the MDP says.

States and actions#

The state $s\in \mathcal{S}$ is everything the agent needs to know to predict what happens next. In the gridworld it is the cell. The actions $\mathcal{A}$ (or $\mathcal{A}(s)$ if they depend on the state) are the choices available. Here both sets are finite and small, which lets us store the whole model in arrays: 25 states by 4 actions by 25 next states. Continuous states (joint angles, prices) and continuous actions (torques) are allowed in the general theory; the sums below then become integrals.

The transition function#

Here $S_t$ and $A_t$ are the state and action at time step $t$, and $s^{\prime }$ is a candidate next state. For every state and action the probabilities over $s^{\prime }$ sum to one. This is where the environment's randomness lives. In the gridworld, take the cell at row 2, column 3, directly below the stairwell. Choosing "up" gives $P=0.8$ of entering the stairwell, 0.1 of sliding left to (2,2) and 0.1 of sliding right to (2,4). Choosing "down" runs into the wall at (3,3), so the robot stays put with probability 0.8 and slides sideways with probability 0.1 each. Select that cell in Figure 1 and switch actions to see all four distributions.

The reward function#

We write the reward as $R(s,a,s^{\prime })$, the reward received on the transition from $s$ to $s^{\prime }$ under action $a$. Many texts use the expected reward $R(s,a)={\sum }_{s^{\prime }}P(s^{\prime }\mid s,a)R(s,a,s^{\prime })$ instead, which carries the same information for planning. For "up" from (2,3), $R(s,a)=0.8\times (-1)+0.1\times 0+0.1\times 0=-0.8$: a bad action even before you think about the future. The reward is the only channel through which you tell the agent what you want, which is why mistakes in it are so costly; see reward shaping for the safe way to add guidance and specification gaming for what happens when the reward and the intention part ways.

The discount factor#

The discount $\gamma$ sets how much a reward $k$ steps in the future is worth now: ${\gamma }^k$ times its face value. With $\gamma =0.9$, the dock reached in eight moves is worth $0.9^7=0.478$ at the start (seven discount factors, because the reward arrives on the eighth transition). A useful rule of thumb is the effective horizon $1/(1-\gamma )$: about 10 steps at 0.9, 100 steps at 0.99. Discounting also keeps the sum of rewards finite in problems that never end, and it is what makes the solution methods converge (see value iteration and policy iteration).

What is the Markov property?#

The word Markov is a promise about the state:

On the left the next state and reward are conditioned on the entire history; on the right only on the present state and action. The equation says the present state screens off the past. It is a property of how you define the state, not of the world. Any process becomes Markov if the state includes enough history, and almost any process stops being Markov if you throw away part of the state.

We checked both directions in simulation. Running 20,000 random-policy episodes in the gridworld (seed 11), the probability that "right" from cell (2,2) lands on (2,3) was 0.789, 0.797, 0.804 and 0.793 when the previous cell was (3,2), (1,2), (2,2) and (2,3) respectively: the same 0.8 up to sampling noise, as the definition requires. Then we hid the row and gave the agent only its column, a crude stand-in for a sensor that cannot see depth. Now the chance that "up" keeps the agent in column 2 was 0.841 if it had just arrived from column 1, 0.868 if it had stayed in column 2 and 0.818 if it came from column 3. The past now carries information the "state" does not, because where you came from hints at which row you are in, and the row decides which walls you can bump into.

Practitioners restore the Markov property by enlarging the state. The Atari agent of Mnih and colleagues stacked the last four video frames as its input, because a single frame shows where the ball is but not where it is going [6]. When the true state is hidden for good, the right model is a partially observable MDP, covered below.

Policies, returns and value functions#

A policy $\pi (a\mid s)$ is the agent's rule for choosing actions: a probability for each action in each state, or a single action per state for a deterministic policy. Following a policy from time $t$ produces a stream of rewards whose discounted sum is the return:

$R_{t+k+1}$ is the reward received $k+1$ steps after time $t$. In the gridworld every reward is zero except the last, so an episode that ends at the dock after $T$ transitions has $G_0={\gamma }^{T-1}$, and one that ends in the stairwell has $G_0=-{\gamma }^{T-1}$. That is why the histogram in Figure 1 has a cluster of positive returns, one bar per episode length, and a smaller mirror-image cluster below zero.

The return is random. Its expectation is the object everything else is built on:

The state value $V^{\pi }(s)$ is the expected return starting from $s$ and following $\pi$; the action value $Q^{\pi }(s,a)$ is the expected return if you first take action $a$ and then follow $\pi$. An optimal policy ${\pi }^{\ast }$ has $V^{{\pi }^{\ast }}(s)\ge V^{\pi }(s)$ in every state for every policy $\pi$. A classical result for finite MDPs with $\gamma <1$ is that such a policy always exists, and that one can be chosen deterministic and stationary: a fixed action per state, no randomisation, no dependence on time [2, 3]. That fact is what lets a gridworld policy be drawn as one arrow per cell.

Worked example: one cell, two discount factors#

Take the cell at (0,3), immediately left of the dock with the stairwell directly beneath it. Using the optimal values at $\gamma =0.9$, $V^{\ast }(0,3)=0.769$ and $V^{\ast }(0,2)=0.648$, compare two actions:

• Right: 0.8 into the dock (+1), 0.1 bump upward and stay, 0.1 slide down into the stairwell ($-1$). $Q=0.8-0.1+0.1\times 0.9\times 0.769=0.769$.
• Up: 0.8 bump the top edge and stay, 0.1 slide left to (0,2), 0.1 slide right into the dock. $Q=0.1+0.9\times (0.8\times 0.769+0.1\times 0.648)=0.712$.

"Right" wins: take the 10% risk and collect the reward now. Repeat the calculation with $\gamma =0.99$ and the order flips, $Q(\text{up})=0.899$ against $Q(\text{right})=0.789$. A patient agent prefers to push against the wall, which can never drop it into the stairwell, and wait for a lucky sideways slip into the dock. Nothing about the floor changed; only the exchange rate between now and later did. The Bellman equation page derives the one-step look-ahead used here in general.

Evaluating a policy: sampling versus solving#

The value of a fixed policy obeys a linear equation. Conditioning on the first step,

which in matrix form is $V^{\pi }=R_{\pi }+\gamma P_{\pi }{V}^{\pi }$, so $V^{\pi }=(I-\gamma P_{\pi }{)}^{-1}{R}_{\pi }$. Here $P_{\pi }$ is the 25-by-25 matrix of state-to-state probabilities under $\pi$ and $R_{\pi }$ the vector of expected one-step rewards, with terminal states given value zero. When you know $P$ and $R$, one linear solve gives the exact value of every state. When you do not, you can still estimate $V^{\pi }(s)$ by running episodes and averaging their returns, which is the Monte Carlo idea behind much of reinforcement learning. The two must agree, and checking that they do is a good test of any simulator.

Setup (simulation, seeded). We evaluated three policies from the start cell at $\gamma =0.9$ and slip 0.2: the optimal policy; a hand-written "bottom route" that goes right along the bottom row and up everywhere else; and the uniform random policy. For each we solved the linear system exactly and sampled 10,000 episodes (numpy seed 7, at most 500 steps).

The optimal and bottom-route estimates sit inside their intervals. The random policy's sample mean misses by three standard errors, which a correct simulator does about once in 400 runs; four further seeds of 20,000 episodes averaged $-0.0330$, against the exact $-0.0327$. Notice how noisy single returns are: the standard deviation of $G$ under the optimal policy is 0.26, nearly the size of its mean, so 100 episodes still left an error of 0.054 (Figure 2). The bottom route reveals another lesson. Its median episode is the same 10 steps as the optimal one, but its 90th percentile is 91 steps, because any slip off the bottom row sends the robot upward until it hits a wall or the top edge, where "up" does nothing until a sideways slip frees it. Mean values hide this; return distributions show it.

How the discount and the dynamics shape the optimal policy#

We solved the gridworld to optimality (value iteration to a tolerance of $10^{-8}$) across discount factors and slip probabilities, and computed the exact probability of ending in the stairwell and the expected episode length under each optimal policy using the absorbing Markov chain it induces.

With no slip, every discount gives the same eight-step path and no risk. With slip 0.2, the agent at $\gamma =0.9$ accepts a 12.3% chance of the stairwell to finish in about 10 steps. At $\gamma =0.99$ it accepts none, and takes more than twice as long: each of the four cells around the stairwell switches to an action that pushes into a wall or an edge, so that no slip can carry it into the hole (Figure 3). A slipperier floor makes the cautious policy optimal sooner, already at $\gamma =0.9$ for slip 0.4. At $\gamma =0.5$ the dock is so heavily discounted from the start ($V^{\ast }(S)=0.002$) that the start-cell policy barely matters.

The reward function matters as much. Adding a cost per step pushes the agent towards speed: at $\gamma =0.9$ and slip 0.2, a step reward of $-0.04$ raises the stairwell risk to 13.4%, $-0.5$ to 20.2%, and at $-1$ per step the optimal policy walks into the stairwell 83.8% of the time, because ending the episode at $-1$ beats paying $-1$ a step to reach a +1. That is not a bug in the solver. It is the MDP saying exactly what its rewards say, which is the root of the reward hacking problem.

How do you solve a Markov decision process?#

Solution methods split by what you know about $P$ and $R$.

• Known model, small state space: dynamic programming. Value iteration repeatedly applies the Bellman optimality update; policy iteration alternates exact evaluation (the linear solve above) with greedy improvement. Both are covered with an editable gridworld in value iteration vs policy iteration. Linear programming is a third exact option [2].
• Unknown model, sample access: reinforcement learning. Model-free methods learn values or policies from experience alone. Q-learning estimates $Q^{\ast }$ from transitions; policy gradient methods adjust a parametrised policy directly. Model-based methods first estimate $P$ and $R$ from data and then plan.
• Unknown model, fixed dataset: offline reinforcement learning, which has to avoid trusting actions the data never tried.

The single-state special case, where actions earn rewards but never change the state, is the multi-armed bandit: all exploration, no planning.

MDP vs Markov chain vs POMDP vs CMDP#

A POMDP is an MDP over beliefs: as Kaelbling, Littman and Cassandra set out, the posterior distribution over hidden states is itself a Markov state, so the belief can be planned over, at a much larger computational cost [4]. A constrained MDP makes the trade-off in our table explicit. Instead of tuning $\gamma$ or a step penalty until the agent stops gambling near the stairwell, you state the acceptable risk as a constraint and let the solver find the best policy that respects it [5].

Turning a real problem into an MDP#

Writing down the tuple is the step that decides whether the rest works. A checklist we use:

1. State: could a perfect predictor do better if it also knew the last few steps? If yes, the state is missing something. Add the history, a summary of it, or model the problem as a POMDP.
2. Actions: are they what the agent can actually control, at the time scale it acts on? Too fine and the horizon explodes; too coarse and good behaviour is unreachable.
3. Transitions: where does the randomness come from, and is a simulator faithful to it? Our slip rule decided the whole character of the optimal policy; a simulator with the wrong slip trains the wrong policy.
4. Reward: would you be happy if the agent maximised this number and nothing else? Run the solver on extreme settings, as we did with the step cost, and look at what it does.
5. Discount or horizon: is $1/(1-\gamma )$ close to the time scale on which outcomes matter? If the task has a natural end, an undiscounted episodic formulation may be more honest.

Language models fit this frame too. In reinforcement learning for LLMs the state is the prompt plus the tokens generated so far, an action is the next token, transitions are deterministic (append the token), and the reward usually arrives once, at the end, from a reward model or a verifier. The state is trivially Markov because it contains the whole history; the hard parts move to the reward and to the sheer size of the action space.

Code: build the MDP and evaluate a policy#

import numpy as np
LAYOUT = ["....G", ".#.X.", ".#...", "...#.", "S...."]
H, W, slip, gamma = 5, 5, 0.2, 0.9
DR = [(-1, 0), (0, 1), (1, 0), (0, -1)]          # up, right, down, left
cell = lambda s: LAYOUT[s // W][s % W]
live = np.array([cell(s) not in "#GX" for s in range(H * W)])

def move(s, d):
    r, c = divmod(s, W); r2, c2 = r + DR[d][0], c + DR[d][1]
    ok = 0 <= r2 < H and 0 <= c2 < W and LAYOUT[r2][c2] != "#"
    return r2 * W + c2 if ok else s

P = np.zeros((25, 4, 25)); R = np.zeros((25, 4))   # P[s, a, s'], expected R(s, a)
for s in np.flatnonzero(live):
    for a in range(4):
        for d, p in [(a, 1 - slip), ((a + 1) % 4, slip / 2), ((a + 3) % 4, slip / 2)]:
            s2 = move(s, d)
            P[s, a, s2] += p
            R[s, a] += p * {"G": 1.0, "X": -1.0}.get(cell(s2), 0.0)

def evaluate(pi):                                  # V = (I - gamma P_pi)^-1 R_pi
    idx = np.arange(25)
    P_pi = P[idx, pi] * live[:, None]
    return np.linalg.solve(np.eye(25) - gamma * P_pi, R[idx, pi] * live)

bottom = np.array([1 if (s // W == 4 and s % W < 4) else 0 for s in range(25)])
print(round(evaluate(bottom)[20], 4))              # 0.1735, the bottom route from S

Failure modes#

A state that is not Markov. Value estimates and greedy policies assume the state screens off the past. With an aliased state, as in our column-only experiment, a learned value averages over situations that call for different actions, and no amount of data fixes it. Testing the Markov assumption on logged data is possible; Shi and colleagues give a formal test [7]. A cheaper check is to see whether adding the previous observation to the input improves next-state prediction.

A reward that says something you did not mean. The step-cost sweep shows an optimal agent choosing the stairwell when living is expensive enough. In larger systems the same logic produces agents that exploit simulator bugs or graders, the pattern known as specification gaming.

A discount chosen for convenience. $\gamma$ is often treated as a training knob, but it changes which policy is optimal, not just how fast learning goes. Our agent's stairwell risk went from 12.3% to zero between 0.95 and 0.99. If you evaluate an agent on undiscounted success but trained it with a short horizon, expect a mismatch.

A model that is wrong in the tails. Planning in an MDP with misestimated transitions gives a policy that is optimal for the wrong world. Errors in rare transitions, like a slip into a hazard, matter most and are the hardest to estimate from data.

Mistaking the mean for the outcome. The MDP objective is an expectation. Two policies with similar values can have very different tails, as the bottom route's 91-step 90th percentile shows. When the tails matter, measure them, report them with intervals (our note on evaluating RL agents covers how), or put them in a constraint.

Frequently asked questions#

Sources#

1. R. Bellman. A Markovian Decision Process, 1957. doi.org
2. M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming, 1994. doi.org
3. R. S. Sutton, A. G. Barto. Reinforcement Learning: An Introduction (2nd ed.), 2018. incompleteideas.net
4. L. P. Kaelbling, M. L. Littman, A. R. Cassandra. Planning and acting in partially observable stochastic domains, 1998. doi.org
5. E. Altman. Constrained Markov Decision Processes, 1999. doi.org
6. V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, M. Riedmiller. Playing Atari with Deep Reinforcement Learning, 2013. arxiv.org
7. C. Shi, R. Wan, R. Song, W. Lu, L. Leng. Does the Markov Decision Process Fit the Data: Testing for the Markov Property in Sequential Decision Making, 2020. arxiv.org