75 - The Markov Decision Process: The Language Every RL Problem Is Written In

In the previous article the bandit had a single "state": every choice was independent of the others. Interesting problems are not like that: moving through a maze, playing chess, driving a car change the situation, and what you do now determines what you will be able to do next. The mathematical language that describes these problems is called the Markov decision process (MDP). It is not an algorithm: it is a frame. But the whole rest of the module (the Bellman equation, Q-Learning, Deep Q-Learning) is written in this frame, and if the frame is not clear neither is the rest. So here we go slowly: we define every element, verify the subtlest point (the Markov property) with an experiment, write a small MDP as a table of numbers and make it play.

The vocabulary of an MDP

A state s is everything you need to know about the situation in order to decide what to do; the set of states is S. An action a is what the agent can do in a state; the set of actions is A. The transition P(s′ | s, a) is the probability of ending in state s′ by taking action a in state s: if all the probabilities are 0 or 1 the environment is deterministic, otherwise stochastic. The reward R(s, a, s′) is the number received in that transition. The discount factor γ (gamma), with 0 ≤ γ ≤ 1, says how much a future reward is worth compared with an immediate one; here we define it, and why it is needed you derive in the derivation of the Bellman equation.

The policy π(a | s) is the agent's rule, that is the probability with which it chooses each action in each state; a deterministic policy is a "state → action" table. A terminal state is a state in which the episode ends: you do not leave it and you earn nothing more. An episode is a complete trajectory from the initial state to a terminal one; an "episodic" problem has finite episodes (a game), a "continuing" one never ends (the control of a thermostat). Finally the value functions v_π(s) and q_π(s, a) are the average return one can expect starting from s (and doing a) and then following the policy π: they serve to evaluate how "good" a state or an action is. We define them here and estimate them in two ways, a slow one on this page and an exact one in the next.

The analogy: the satnav that does not remember where you came from

A satellite navigator, to tell you where to turn, needs to know where you are now and where you want to go. It does not need to know which road you arrived by, nor at what time you set out: the current position contains everything that matters for the future. This is the idea of the Markov property: the future depends on the past only through the present. A good "state" is one that summarises enough of the past to make the rest superfluous. If instead the navigator only knew "you are at a junction" without saying which, it could not decide: that state is not rich enough. Understanding whether the state you are giving the agent is really "Markov" is one of the most important and most underrated design decisions in RL.

The five things of an MDP

An MDP is defined by five things: (S, A, P, R, γ). The drawing has a concrete example: a 4×4 grid with 16 states (numbered 0 to 15), 4 actions (up, right, down, left), two terminal states (the corners 0 and 15, "goal") and a reward of −1 at every step, until you reach a corner. This last choice is important: with −1 at every step, to accumulate as little penalty as possible the agent must reach a corner as quickly as possible. The goal "hurry up" is all in the reward; we did not tell the agent. Moving against a wall leaves you in the same state; and if the floor is "slippery" the action succeeds with probability 0.8 and veers sideways with probability 0.1 + 0.1 (this is the example in the drawing). Sutton and Barto define the finite MDP in chapter 3 of their text and say something worth keeping in mind: the Markov property is a restriction not on the decision process but on the state, which must include whatever of the past makes a difference for the future.

The Markov property, verified

The definition says: the probability of the next state and of the reward depends only on s and a, not on the history. Let us verify it on an example where we can watch it fail. A ball bounces between positions 0 and 9, moving one cell per step and reversing direction at the edges. If "the state" is only the position, can we predict the next position? The listing uses a generator with a fixed seed (default_rng(0)), so the trajectory and the output are the same at every run.

# Is "the position" a Markov state? A ball bounces between 0 and 9 moving one cell per step.
import numpy as np
from collections import Counter, defaultdict

def ball_trajectory(steps, rng):
    pos, vel = int(rng.integers(0, 10)), int(rng.choice([-1, 1]))
    traj = [pos]
    for _ in range(steps):
        if not (0 <= pos + vel <= 9):
            vel = -vel                                # bounce
        pos += vel
        traj.append(pos)
    return traj

rng = np.random.default_rng(0)
traj = ball_trajectory(20000, rng)

def best_possible_accuracy(feature):
    """Largest accuracy any predictor can reach if it can only look at `feature(t)` to guess position t+1."""
    table = defaultdict(Counter)
    for t in range(1, len(traj) - 1):
        table[feature(t)][traj[t + 1]] += 1
    hits = sum(c.most_common(1)[0][1] for c in table.values())
    return hits / (len(traj) - 2)

print("state = position only          :", round(best_possible_accuracy(lambda t: traj[t]), 3))
print("state = (previous, current)    :", round(best_possible_accuracy(lambda t: (traj[t - 1], traj[t])), 3))

# Output (two consecutive runs, same output):
# state = position only          : 0.556
# state = (previous, current)    : 1.0

ball_trajectory generates 20,000 steps of the ball. best_possible_accuracy(feature) builds, for each value of the "state description" (feature), a table that counts which next position appeared most often; the fraction of cases in which the most frequent choice is correct is the maximum possible accuracy for any predictor that sees only that description, because the information to do better is not there. With the position alone the maximum is 55.6%: in the intermediate cells the ball can go either right or left, and the position alone does not say which. With the pair (previous position, current position) it is 100%: the difference between the two reveals the direction. Conclusion: "the position only" is not a Markov state for this system, "position and previous position" is.

When the observation is not enough, you add the necessary history (the velocity, for example) or use a recurrent memory, as in the networks of the sequences module (see LSTM and the adding problem). In Atari video games, for instance, the DQN paper by Mnih and colleagues applies the network to the last 4 stacked frames: a single frame does not say whether the ball is going up or down. The limit of our experiment is that 55.6% holds for this ball and this trajectory length: the figure shows the mechanism, it is not a general property.

Writing an MDP as a table

For a small MDP you can write P as a real table: for every state and every action, the list of possible consequences, each with its probability, next state, reward and an "episode finished" flag. Gymnasium's tabular environments expose the same structure in the unwrapped.P attribute, as you see in Gymnasium in practice. The code below builds our 4×4 grid.

import numpy as np

# Actions: 0=up, 1=right, 2=down, 3=left
MOVES = {0: (-1, 0), 1: (0, 1), 2: (1, 0), 3: (0, -1)}

class GridWorld:
    """A small MDP written out explicitly: P[s][a] = list of (probability, next_state, reward, done)."""
    def __init__(self, n=4, terminals=(0, 15), step_reward=-1.0, slip=0.0):
        self.n, self.terminals, self.n_states, self.n_actions = n, set(terminals), n * n, 4
        self.P = {s: {a: self._transitions(s, a, step_reward, slip) for a in range(4)} for s in range(self.n_states)}

    def _move(self, s, a):
        r, c = divmod(s, self.n)
        dr, dc = MOVES[a]
        r2, c2 = r + dr, c + dc
        if not (0 <= r2 < self.n and 0 <= c2 < self.n):       # bumping into a wall: stay where you are
            r2, c2 = r, c
        return r2 * self.n + c2

    def _transitions(self, s, a, step_reward, slip):
        if s in self.terminals:                                # terminal states: absorbing, no reward
            return [(1.0, s, 0.0, True)]
        outcomes = {}                                          # next_state -> probability
        for a2, p in [(a, 1.0 - slip), ((a + 1) % 4, slip / 2), ((a - 1) % 4, slip / 2)]:   # intended, or slip to a side
            if p > 0:
                s2 = self._move(s, a2)
                outcomes[s2] = outcomes.get(s2, 0.0) + p
        return [(p, s2, step_reward, s2 in self.terminals) for s2, p in outcomes.items()]

env = GridWorld()
print("from state 1, action 'left' (towards the terminal state 0):", env.P[1][3])
print("from state 5, action 'up':", env.P[5][0])
print("from state 0 (terminal):", env.P[0][2])
slippery = GridWorld(slip=0.2)
print("slippery, state 5, action 'right':", [(round(p, 2), s2) for p, s2, r, d in slippery.P[5][1]])

# Output (two consecutive runs, same output):
# from state 1, action 'left' (towards the terminal state 0): [(1.0, 0, -1.0, True)]
# from state 5, action 'up': [(1.0, 1, -1.0, False)]
# from state 0 (terminal): [(1.0, 0, 0.0, True)]
# slippery, state 5, action 'right': [(0.8, 6), (0.1, 9), (0.1, 1)]

The GridWorld class builds the dictionary self.P, such that P[s][a] is the list of consequences. _move computes where you end up moving in direction a, staying put if you hit the edge. _transitions distinguishes two cases: if s is terminal, the transition is "absorbing" (you stay there, reward 0, done=True); otherwise, with probability 1 − slip the action succeeds, and with probability slip/2 each the "rotated" action to the right or to the left is executed ((a + 1) % 4 and (a − 1) % 4). If two outcomes lead to the same state (it happens near walls), the probabilities are added up in the outcomes dictionary: without this merging the list would contain two entries for the same arrival state.

The four printed lines confirm it: from 1 with "left" you go to terminal 0 with probability 1, reward −1 and done=True; from 5 with "up" you go to 1 without finishing; terminal state 0 is absorbing; with a slippery floor (slip=0.2), from 5 with "right" you go to 6 with 0.8, to 9 with 0.1 and to 1 with 0.1, the same numbers as in the drawing.

Making the agent play: random policy against sensible policy

A policy is just a function from state to action. We write the function that simulates an episode and try two policies: one that chooses at random and one that heads straight for the nearest corner. The simulations use rng.choice(len(probs), p=probs) to draw the outcome according to the probabilities of P[s][a]; in the deterministic grid there is a single entry with probability 1, but the code works with slip > 0 too.

def run_episode(env, policy, rng, start, max_steps=10_000, gamma=1.0):
    """Follow `policy` (a function state -> action) from `start`. Returns (return, number_of_steps)."""
    s, G, discount = start, 0.0, 1.0
    for t in range(max_steps):
        a = policy(s)
        probs = [p for p, _, _, _ in env.P[s][a]]
        p, s2, r, done = env.P[s][a][rng.choice(len(probs), p=probs)]
        G += discount * r
        discount *= gamma
        s = s2
        if done:
            return G, t + 1
    return G, max_steps

rng = np.random.default_rng(0)
random_policy = lambda s: int(rng.integers(4))
non_terminal = [s for s in range(env.n_states) if s not in env.terminals]
results = [run_episode(env, random_policy, rng, start=s) for s in non_terminal for _ in range(2000)]
G = np.array([g for g, _ in results]); L = np.array([l for _, l in results])
print(f"random policy: mean return {G.mean():.1f}, mean episode length {L.mean():.1f}, longest {L.max()}")
# A hand-written policy: head for the NEAREST terminal state (state 0 or state 15)
def towards_nearest_corner(s):
    r, c = divmod(s, 4)
    dist0, dist15 = r + c, (3 - r) + (3 - c)
    if dist0 <= dist15:
        return 0 if r > 0 else 3                 # up while possible, then left
    return 2 if r < 3 else 1                     # down while possible, then right

results = [run_episode(env, towards_nearest_corner, rng, start=s) for s in non_terminal]
print(f"shortest-path policy: mean return {np.mean([g for g, _ in results]):.2f}, longest episode {max(l for _, l in results)} steps")

# Output (two consecutive runs, same output):
# random policy: mean return -18.2, mean episode length 18.2, longest 213
# shortest-path policy: mean return -2.00, longest episode 3 steps

run_episode starts from start and, at every step, asks the policy for the action, draws an outcome, accumulates the reward (discounted if gamma < 1) and stops when done is true. With the random policy, starting from each of the 14 non-terminal states 2000 times, the mean return is −18.2 and the episode lasts 18.2 steps on average (each step is worth −1, so return = −length); the longest has 213 steps, because a random walk can wander for a long time. The "towards the nearest corner" policy makes −2.00 on average, at most 3 steps: same environment, two policies, a return about nine times better. This is what "learning" means: RL looks for the policy that maximises the expected return. Mind the max_steps=10_000 parameter: it protects against a policy that never reaches a terminal, but if it triggers the returned return is partial, and in that case the episode should be flagged, not averaged in silence.

The discounted return

So far the return was the plain sum of the rewards. For long or endless problems you use the discounted return: each reward is multiplied by a power of γ that grows with the distance in time:

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

An algebraic observation, which you will use continuously, is that the return can be written recursively: factoring out γ from the second term on,

G_t = R_{t+1} + γ ( R_{t+2} + γ R_{t+3} + γ² R_{t+4} + … ) = R_{t+1} + γ G_{t+1}

"The return of now is the immediate reward plus γ times the return from tomorrow". This recursion is the seed of the Bellman equation. Let us see the numbers with a four-step episode: three steps with reward −1 and then the arrival with +10.

def discounted_return(rewards, gamma):
    """G_0 = R_1 + gamma R_2 + gamma^2 R_3 + ...   (computed from the end, which is how it is done in practice)"""
    G = 0.0
    for r in reversed(rewards):
        G = r + gamma * G                              # G_t = R_{t+1} + gamma * G_{t+1}
    return G

rewards = [-1, -1, -1, 10]                             # three steps of cost, then the goal
for gamma in (1.0, 0.9, 0.5):
    print(f"gamma={gamma}:  G_0 = {discounted_return(rewards, gamma):.3f}")
print("by hand, gamma=0.9:", -1 - 0.9 - 0.81 + 0.729 * 10)

# Output (two consecutive runs, same output):
# gamma=1.0:  G_0 = 7.000
# gamma=0.9:  G_0 = 4.580
# gamma=0.5:  G_0 = -0.500
# by hand, gamma=0.9: 4.58

The function discounted_return computes the return from right to left, applying the recursion G = r + γ·G, which avoids computing the powers of γ one by one. With γ = 1 (no discount) the return is the plain sum, −1 −1 −1 + 10 = 7. With γ = 0.9 the +10 prize, which arrives after three steps, is worth only 0.9³ · 10 = 7.29 and the return is −1 − 0.9 − 0.81 + 7.29 = 4.58, as the hand-computed line confirms. With γ = 0.5 the prize is worth 0.125 · 10 = 1.25 and the return becomes negative (−0.5): such a "short-sighted" agent would consider that episode a bad deal. The value of γ is not a detail: it changes what the agent considers optimal, and we discuss it in depth in the article on Bellman.

What "value" means: the slowest possible estimate

The value function v_π(s) is the expected return starting from s and following the policy π. We can estimate it with no theory at all, just by simulating: for each state we run many episodes with the random policy and average their returns (the Monte Carlo method).

# Estimating the VALUE of each state under the random policy, the slow way: average the returns of many simulated episodes
rng = np.random.default_rng(1)
random_policy = lambda s: int(rng.integers(4))
V_mc = np.zeros(env.n_states)
for s in range(env.n_states):
    if s in env.terminals:
        continue
    V_mc[s] = np.mean([run_episode(env, random_policy, rng, start=s)[0] for _ in range(4000)])
print(np.round(V_mc.reshape(4, 4), 1))

# Output (two consecutive runs, same output):
# [[  0.  -13.8 -19.6 -21.7]
#  [-14.  -18.4 -19.8 -20.4]
#  [-19.9 -19.9 -18.4 -14.1]
#  [-22.1 -20.3 -14.2   0. ]]

The code runs, for each of the 14 non-terminal states, 4000 episodes with the random policy and averages the return. The result is a map of values: near the terminal corners the value is "less bad" (about −14), far from the corners it is worse (about −22). It makes sense: starting from a state far from the finish means, for a random walk, expecting more steps and therefore more −1s. How far to trust each cell? Rerunning the same procedure with other seeds on three states (1, 5 and 10), the standard deviation of the returns is 17-18 and the standard error of the mean over 4000 episodes comes out at 0.27-0.28: each cell is reliable to about ±0.3, not to the first decimal digit. Remember this table: in the article on the Bellman equation it is computed without simulating anything, and the distance between the two is precisely that sampling noise.

From the MDP to the central question

With these definitions, the RL problem is stated in one line: given an MDP (often without knowing P and R), find the policy π that maximises the expected return from every state. Two situations are very different. If you know the MDP (the table P), you can plan, that is compute the value with dynamic programming; if you do not know it, you must learn from experience, which is the case of Q-Learning and of Deep Q-Learning. The difference between the two is the backbone of the module. For a finite MDP there always exists at least one optimal policy, and every policy that is greedy with respect to the optimal value is optimal (Sutton and Barto, section 3.6): this is why you can look for a deterministic policy without losing anything.

The modelling trade-offs

The first trade-off concerns how much to include in the state: little, and the agent does not see what it needs (the ball without direction); too much, and the states become many and learning slows down. The second is between deterministic and stochastic environment: the stochastic model is more realistic but forces you to reason on average, with expected values. The third concerns the density of the reward: a reward at every step (−1 here) guides the agent, while a reward only at the end makes learning much harder, the topic of Delayed Rewards, Reward Shaping and Reward Hacking. The fourth is between episodic and continuing: with finite episodes γ = 1 is allowed, for endless problems you need γ < 1 so that the sum stays finite.

Real pitfalls

1. Non-Markov state. The most common mistake: giving the agent an observation that does not contain what is needed (here, the ball without direction). Every algorithm works badly and you do not know why.
2. A reward that does not describe the goal. The agent maximises that number, not your intention. With −1 per step it obtains "hurry up"; with a badly written reward it obtains unexpected behaviour.
3. Confusing reward and return. The reward is the number of one step, the return is the (discounted) sum of all the future ones.
4. Forgetting the terminals. A terminal state must be absorbing with zero reward after arrival; if you let it emit reward, the agent may learn to "oscillate" there.
5. Measuring a policy with a single episode. The environment may be stochastic: you need the average over many episodes (here 2000 per state in the comparison between policies, 4000 for the value estimate).

The first two pitfalls are design errors and no measurement signals them: the algorithm runs, the numbers come out, and the behaviour is wrong for reasons that lie in the definition of the state or of the reward. The last three are implementation or evaluation errors and are found with a test: a terminal state is checked by looking at P[s][a] (as in the third output line above), an average over many episodes is checked with the standard error.

A worked example by hand: the value of a two-state chain

A tiny MDP that anticipates Bellman. Two states, A and B, plus a terminal. With the policy we are evaluating: from A you always go to B (reward −1); from B you go to the terminal with probability ½ or return to A with probability ½ (reward −1 in both cases). What is the value, that is the expected return (without discount), of A and of B?

Let us reason with the recursion of the return. From B: you pay −1 and then, with probability ½ you finish (value 0), with probability ½ you start again from A: v(B) = −1 + ½·0 + ½·v(A). From A: you pay −1 and go to B: v(A) = −1 + v(B). Substituting: v(A) = −1 − 1 + ½·v(A), so ½·v(A) = −2 and v(A) = −4, v(B) = −3. Independent check: the expected number of steps E to leave B satisfies E = 1 + ½·(1 + E) (one step; with probability ½ you return to A, take another step towards B and start again). Solving, ½·E = 1.5, that is E = 3 expected steps, and since each step costs −1 the return is −3, which coincides with v(B). I also rechecked the linear system with numpy.linalg.solve: it returns (−4, −3).

The two equations written above are Bellman equations, which we derive in general in the next article: we wrote the value of a state as a function of the values of the successor states and solved them as a linear system. With 16 states in the 4×4 grid the system has 16 equations; that is what the computer will do.

Frequently asked questions

What is the difference between "state" and "observation"?

The state is the complete description of the situation; the observation is what the agent receives, which may be partial (a single frame of a video game). When the observation is not Markov, you add history or memory.

Must a policy be deterministic?

No: it can assign probabilities to actions, and the random policy of the grid is a special case. For a finite MDP there always exists an optimal deterministic policy anyway (see above, section 3.6 of the book).

Why can the reward depend on s′?

For generality: the reward may depend on what happens after the action (for example "you fall into a hole"). Often one writes R(s, a) because it is the average over s′.

What does it mean for an MDP to be "finite"?

That the set of states and actions is finite, as in our grid; it is the case in which tables and dynamic programming work. With continuous states (CartPole) you need approximators.

Can the return be computed before the end of the episode?

Not exactly: it depends on future rewards still unknown. This is why the value is estimated (Monte Carlo at the end of the episode, or Bellman and TD without waiting).

Must terminal states have value zero?

By convention yes: after the end nothing more accumulates. Forgetting it (adding value after a terminal) inflates the estimates.

Exercises with solutions

Before moving on, try to solve these exercises with pen and paper; the solution is right below each one.

1. Compute G_0 for the rewards 2, 0, 4 with γ = 0.5.
   Solution: 2 + 0.5·0 + 0.25·4 = 3. With the recursion from the right: G = 4; G = 0 + 0.5·4 = 2; G = 2 + 0.5·2 = 3.
2. Compute G_0 for the rewards 1, 2, 3 with γ = 0.5.
   Solution: 1 + 0.5·2 + 0.25·3 = 2.75; from the right: G = 3; G = 2 + 0.5·3 = 3.5; G = 1 + 0.5·3.5 = 2.75.
3. A 5×5 grid with 4 actions: how many entries does the table P (state, action) have?
   Solution: 25·4 = 100. For the 4×4 grid of the article it is 16·4 = 64 entries, each with a single outcome if there is no slipping.
4. Why is "position" not enough as a state for the bouncing ball?
   Solution: because the direction is not determined by the position alone: in the intermediate cells the ball can go either way (maximum accuracy 55.6%).
5. In the chain A, B, terminal (B returns to A with probability ½), if the reward per step were −2, what would v(A) be worth?
   Solution: the values scale linearly: v(A) = −8, double −4 (rechecked with numpy.linalg.solve: −8 and −6).

The first three exercises are arithmetic: they serve to fix the recursion G = r + γ·G and the counting of the entries of P. The last two are interpretation, and they are the ones that separate whoever has understood the Markov property and the Bellman recursion from whoever has only learned the formulas: if you answer without rereading the text, you can move on.

What you can do now

You can write an MDP as (S, A, P, R, γ), you can say whether a state is Markov and you have seen how to measure it (maximum accuracy 55.6% with the position alone, 100% with position and previous position). You can build the table P of a small environment, simulate a policy and compare its return: in the grid, the random policy is worth −18.2 and the sensible one −2. You can compute the discounted return G_t = R_{t+1} + γ G_{t+1} and estimate the value of a state with Monte Carlo (from about −14 to about −22 in the grid, with a standard error around 0.3). The next step is the Bellman equation derived in full, which turns the recursion of the return into an exact computation without simulating.