Markov decision processes, returns and the Bellman equations

Before this lesson: reading sums and indices (foundations 02); probability and expectation (foundations 08, probability 02); conditional expectation and the law of total expectation (probability 04); the matrix inverse (linear algebra 03); the $\infty$-norm, only for one proof (linear algebra 11). Time: about 60 minutes, plus the notebook.

---

Why this matters #

Every RL method estimates one of two things: how good a state is under a given policy ($V^\pi$), or how good it is under the best policy ($V^*$). The Bellman equations define these two objects as one-step recursions. Later methods are sample-based versions of the same equations: TD learning and Q-learning (lessons 04 and 05), DQN (lesson 06), the critic in actor-critic methods (lesson 08), and the value model in PPO for language models (lesson 09). If you know the exact version, you can see what each approximation gives up.

1. Predict first #

2. The picture #

The agent–environment loop #

Time runs in steps $t = 0, 1, 2, \dots$. At step $t$:

1. the agent sees the state $s_t$;
2. it picks an action $a_t$;
3. the environment gives a reward $r_t$ (a number) and moves to the next state $s_{t+1}$.

The rule that picks actions is the policy $\pi$. One run from a start state to an end is an episode. Four examples:

• A board game. State = the board, action = a move, reward = +1 for a win at the end, 0 otherwise.
• A robot. State = joint angles and speeds, action = motor torques, reward = progress minus energy.
• A recommender. State = the user's history, action = the item to show, reward = a click.
• A language model writing an answer. State = the prompt plus the tokens so far, action = the next token, reward = a score for the finished answer (lesson 09).

A small example: the robot vacuum #

We use one example through lessons 01 and 02. A robot vacuum has a high battery (state H) or a low battery (state L). It has two actions:

• clean: in H it earns 2, then stays in H or drops to L, with probability ½ each. In L it earns 1 and stays in L.
• charge: it earns 0 and moves to H.

Should the robot clean in L (earn 1 now) or charge (earn 0 now, but more later)? To answer, we need the value of a whole future, not of one step.

Interactive figure: loading…

Discounting: why the future counts less #

The robot runs forever, so the plain sum of rewards is infinite. The discount factor $\gamma \in [0, 1)$ fixes this: a reward $k$ steps ahead counts $\gamma^k$ times as much as a reward now. With reward 1 at every step, the geometric series gives

For $\gamma = 0.9$ this is $10$ (the answer to predict-first question 1). The number $1/(1-\gamma)$ is the effective horizon: the agent looks about $1/(1-\gamma)$ steps ahead. For $\gamma$ close to 1, the weights $\gamma^k$ with $k < 1/(1-\gamma)$ carry about 63% of the total weight, because $\gamma^{1/(1-\gamma)} \approx e^{-1}$ (for $\gamma = 0.9$ it is 65%).

Interactive figure: loading…

3. Definitions and main results #

Markov decision processes #

Definition (finite MDP). A finite Markov decision process is a tuple $(\mathcal S, \mathcal A, P, R, \gamma)$:

• $\mathcal S$ is a finite set of states and $\mathcal A$ a finite set of actions;
• $P(s' \mid s, a)$ is the transition probability: the probability that the next state is $s'$ when the agent takes action $a$ in state $s$;
• $R(s, a)$ is the expected reward for taking action $a$ in state $s$;
• $\gamma \in [0, 1]$ is the discount factor.

The Markov property says: the next state $s_{t+1}$ and the reward $r_t$ depend on the past only through the current pair $(s_t, a_t)$. In plain words, the state contains everything about the past that matters for the future. If it does not (for example, a single camera frame without the speed of a ball), you must put more into the state (for example, the last four frames).

Episodic and continuing tasks. In an episodic task, every episode ends in a terminal state. After a terminal state there are no more rewards, so its value is 0. A game is episodic. In a continuing task, the interaction goes on forever, like the robot vacuum. Continuing tasks need $\gamma < 1$. Episodic tasks may use $\gamma = 1$.

Returns #

Definition (return). The return from step $t$ is the discounted sum of the future rewards:

It is also called the reward-to-go. Take out the first term, and the rest is $\gamma$ times the return from step $t+1$:

This return recursion is the seed of every Bellman equation. It also gives a fast way to compute all returns of an episode $r_0, \dots, r_{T-1}$: start from $G_T = 0$ and go backwards, $G_{T-1} = r_{T-1}$, $G_{T-2} = r_{T-2} + \gamma G_{T-1}$, and so on. That is $T$ steps instead of $T^2$.

If the rewards are bounded, $|r_t| \le r_{\max}$, and $\gamma < 1$, then $|G_t| \le r_{\max}/(1 - \gamma)$: the return is always a finite number.

Policies and value functions #

A policy $\pi(a \mid s)$ gives the probability of action $a$ in state $s$. A deterministic policy picks one action per state; we write it $\pi(s)$. In this lesson policies are stationary: they depend on the current state only, not on the time or the past.

Definition (value functions). For a policy $\pi$:

The state-value function $V^\pi(s)$ is the expected return when you start in $s$ and follow $\pi$. The action-value function $Q^\pi(s, a)$ is the expected return when you start in $s$, take action $a$ first (whatever $\pi$ says), and follow $\pi$ after that. The expectation is over both sources of randomness: the policy's choices and the environment's transitions.

The advantage $A^\pi(s, a) = Q^\pi(s, a) - V^\pi(s)$ says how much better action $a$ is than the policy's average action in $s$. Policy-gradient methods use it (lesson 07).

Two links between $V$ and $Q$.

Proof.

1. First link. By the law of total expectation, average over the first action: $\mathbb E_\pi[G_t \mid s_t = s] = \sum_a \pi(a \mid s)\, \mathbb E_\pi[G_t \mid s_t = s, a_t = a]$. The inner expectation is $Q^\pi(s, a)$.
2. Second link. Use $G_t = r_t + \gamma G_{t+1}$ and linearity: $Q^\pi(s, a) = \mathbb E[r_t \mid s, a] + \gamma\, \mathbb E_\pi[G_{t+1} \mid s_t = s, a_t = a]$. The first term is $R(s, a)$.
3. Average the second term over the next state: $\mathbb E_\pi[G_{t+1} \mid s, a] = \sum_{s'} P(s' \mid s, a)\, \mathbb E_\pi[G_{t+1} \mid s_t = s, a_t = a, s_{t+1} = s']$.
4. By the Markov property, once $s_{t+1} = s'$ is known, the future does not depend on $s_t$ or $a_t$. So the last expectation is $\mathbb E_\pi[G_{t+1} \mid s_{t+1} = s'] = V^\pi(s')$. $\blacksquare$

As a consequence, the advantages average to zero under the policy: $\sum_a \pi(a \mid s) A^\pi(s, a) = V^\pi(s) - V^\pi(s) = 0$.

The Bellman expectation equation #

Put the second link into the first. The result is the Bellman expectation equation:

In words: the value of $s$ is the average, over the policy's action and the environment's next state, of "reward now plus $\gamma$ times the value of the next state". A backup diagram draws this: the state at the top, the actions below it, the next states at the bottom. The value flows up from the bottom ("is backed up").

Interactive figure: loading…

Matrix form. Average the reward and the transitions over the policy:

$P_\pi$ is the transition matrix of the Markov chain that the policy creates (row $s$ is the distribution of the next state), and $r_\pi$ is the expected reward in each state. With these, the Bellman equation for all states at once is

This is a linear system with $|\mathcal S|$ equations and $|\mathcal S|$ unknowns. One call to a linear solver gives the values of all states. It costs $O(|\mathcal S|^3)$.

Theorem (the system has exactly one solution). If $0 \le \gamma < 1$, then $I - \gamma P_\pi$ is invertible, and

Proof.

1. Each row of $P_\pi$ has entries $\ge 0$ that sum to at most 1. The $\infty$-norm of a matrix is its largest absolute row sum (linear algebra 11), so $\|P_\pi\|_\infty \le 1$ and $\|(\gamma P_\pi)^k\|_\infty \le \gamma^k$.
2. So the partial sums $S_K = \sum_{k < K} (\gamma P_\pi)^k$ converge: the terms are bounded by a geometric series. Call the limit $S$.
3. Multiply out (the middle terms cancel): $(I - \gamma P_\pi) S_K = I - (\gamma P_\pi)^K$.
4. Let $K \to \infty$. The right side tends to $I$, because $\|(\gamma P_\pi)^K\|_\infty \le \gamma^K \to 0$. So $(I - \gamma P_\pi) S = I$, and $S$ is the inverse. $\blacksquare$

The series has a direct meaning. $(P_\pi^k r_\pi)(s)$ is the expected reward at step $k$ when you start in $s$. So $\sum_k \gamma^k P_\pi^k r_\pi$ is the expected discounted sum of rewards: exactly the definition of $V^\pi$.

The 4×4 gridworld of Sutton and Barto (Example 4.1) shows this. The two aqua corners are terminal. Every step gives reward $-1$, and $\gamma = 1$, so $-V^\pi(s)$ is the expected number of steps to reach a corner.

Interactive figure: loading…

Optimal values and the Bellman optimality equations #

Definition (optimal value functions). $V^*(s) = \max_\pi V^\pi(s)$ and $Q^*(s, a) = \max_\pi Q^\pi(s, a)$. A policy $\pi^*$ is optimal if $V^{\pi^*}(s) = V^*(s)$ in every state $s$.

The best first action gives the best value, and after the first step you should act optimally again. This gives the Bellman optimality equations:

The links are now $V^*(s) = \max_a Q^*(s, a)$ and $Q^*(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V^*(s')$. The max sits inside: it is over the action in the current state, and the average over next states stays an average. The environment is not on your side or against you; only your own choice is maximised.

Lesson 02 proves that for $\gamma < 1$ the optimality equation has exactly one solution, and that this solution is $V^*$. Here we use that fact for the main consequence.

Theorem (a greedy policy with respect to $Q^*$ is optimal). Let $\pi(s) \in \arg\max_a Q^*(s, a)$ in every state. Then $V^\pi = V^*$. So every finite discounted MDP has an optimal policy that is deterministic and stationary, and it is optimal in all states at once.

Proof.

1. By the choice of $\pi$: $V^*(s) = \max_a Q^*(s, a) = Q^*(s, \pi(s)) = R(s, \pi(s)) + \gamma \sum_{s'} P(s' \mid s, \pi(s)) V^*(s')$.
2. Read this as a statement about the deterministic policy $\pi$: the vector $V^*$ solves $V = r_\pi + \gamma P_\pi V$, the Bellman expectation equation of $\pi$.
3. That linear system has exactly one solution, $V^\pi$ (previous theorem). So $V^\pi = V^*$. $\blacksquare$

Note what you need for this: $Q^*$, or $V^*$ together with the model $P, R$. With $V^*$ alone you cannot pick the action, because $Q^* = R + \gamma P V^*$ needs the model.

Linear versus nonlinear. For a fixed policy, the action probabilities are constants, so $V$ appears linearly and one solve is enough. In the optimality equation, the max over actions depends on $V$ itself. A max of linear functions is piecewise linear, not linear, so there is no single linear solve. Lesson 02 solves it with value iteration, policy iteration or a linear program.

4. Worked example #

The robot vacuum, $\gamma = 0.9$, states ordered (H, L).

(a) Evaluate "always clean" by hand. The policy is $\pi(H) = \pi(L) = \text{clean}$.

• In L, cleaning earns 1 and stays in L: $V(L) = 1 + 0.9\, V(L)$, so $0.1\, V(L) = 1$ and $V(L) = 10$.
• In H, cleaning earns 2 and goes to H or L with probability ½: $V(H) = 2 + 0.9\,(0.5\, V(H) + 0.5 \cdot 10) = 2 + 0.45\, V(H) + 4.5$. So $0.55\, V(H) = 6.5$ and $V(H) = 130/11 \approx 11.82$.

(b) The same with the linear system.

The second row gives $0.1\, V(L) = 1$, so $V(L) = 10$. The first row gives $0.55\, V(H) - 0.45 \cdot 10 = 2$, so $V(H) = 6.5/0.55 = 130/11$. The same numbers.

(c) $Q$ from $V$: is charging in L better? Use $Q^\pi(s, a) = R(s, a) + \gamma \sum_{s'} P(s' \mid s, a) V^\pi(s')$:

• $Q^\pi(L, \text{charge}) = 0 + 0.9 \cdot V(H) = 0.9 \cdot 11.82 = 10.64$;
• $Q^\pi(L, \text{clean}) = 1 + 0.9 \cdot 10 = 10 = V^\pi(L)$.

So $A^\pi(L, \text{charge}) = 10.64 - 10 = 0.64 > 0$: charging once in L, then cleaning as usual, beats the policy. In H, $Q^\pi(H, \text{charge}) = 0.9 \cdot 11.82 = 10.64 < 11.82$, so cleaning stays better there.

(d) Evaluate "clean in H, charge in L". Now L charges and moves to H:

• $V(L) = 0 + 0.9\, V(H)$.
• $V(H) = 2 + 0.9\,(0.5\, V(H) + 0.5\, V(L)) = 2 + 0.45\, V(H) + 0.45 \cdot 0.9\, V(H) = 2 + 0.855\, V(H)$.
• So $0.145\, V(H) = 2$, $V(H) = 400/29 \approx 13.79$, and $V(L) = 360/29 \approx 12.41$.

Both values went up, in both states.

(e) Check the optimality equation. For $V = (13.79, 12.41)$:

• H: $\max\big(2 + 0.9\,(0.5 \cdot 13.79 + 0.5 \cdot 12.41),\ 0 + 0.9 \cdot 13.79\big)$ $= \max(13.79,\ 12.41) = 13.79$ ✓
• L: $\max\big(1 + 0.9 \cdot 12.41,\ 0 + 0.9 \cdot 13.79\big)$ $= \max(12.17,\ 12.41) = 12.41$ ✓

In exact fractions, $2 + 0.45 \cdot \tfrac{760}{29} = \tfrac{400}{29}$ and $\tfrac{353}{29} < \tfrac{360}{29}$. The equation holds in both states, so $V^* = (400/29,\ 360/29)$, and the greedy policy "clean in H, charge in L" is optimal.

Answers to section 1. (1) $\sum_k 0.9^k = 1/(1 - 0.9) = 10$. (2) For a fixed policy, the Bellman equation is linear: one solve. For the best policy, the max over actions makes it nonlinear (piecewise linear); lesson 02 solves it. (3) Charge: $Q^*(L, \text{charge}) = 12.41 > Q^*(L, \text{clean}) = 12.17$.

5. In code #

NumPy checks the worked example. The notebook has these cells and the exercises.

import numpy as np

gamma = 0.9
# P[s, a, s'] and R[s, a]; states (H, L), actions (clean, charge)
P = np.zeros((2, 2, 2))
P[0, 0] = [0.5, 0.5]; P[0, 1] = [1, 0]
P[1, 0] = [0, 1];     P[1, 1] = [1, 0]
R = np.array([[2.0, 0.0], [1.0, 0.0]])

def evaluate(pi):                                  # pi[s, a]
    P_pi = np.einsum("sa,sat->st", pi, P)          # Markov chain of the policy
    r_pi = (pi * R).sum(axis=1)
    return np.linalg.solve(np.eye(2) - gamma * P_pi, r_pi)

always_clean = np.array([[1.0, 0.0], [1.0, 0.0]])
V = evaluate(always_clean)
print(V, 130 / 11)                                 # [11.818 10.   ] 11.818
Q = R + gamma * P @ V                              # Q[s, a] = R + gamma * sum_s' P V
print(Q)                                           # [[11.818 10.636] [10.    10.636]]

smart = np.array([[1.0, 0.0], [0.0, 1.0]])         # clean in H, charge in L
V_star = evaluate(smart)
print(V_star, 400 / 29, 360 / 29)                  # [13.793 12.414] 13.793 12.414
print((R + gamma * P @ V_star).max(axis=1))        # [13.793 12.414]: the optimality equation holds

P @ V multiplies the last axis of P (the next state) with V, so it is $\sum_{s'} P(s' \mid s, a) V(s')$ for every pair $(s, a)$ at once.

6. Where it shows up #

• Critics and value models. The critic in actor-critic methods, the value head in PPO and the value model in PPO-based RLHF are trained to satisfy the Bellman expectation equation from samples (lessons 08 and 09).
• Q-learning and DQN learn $Q^*$ from samples of the Bellman optimality equation (lessons 05 and 06).
• Advantages. Policy-gradient methods push up actions with $A^\pi(s, a) > 0$ (lesson 07).
• Language models. Generating an answer is an episodic MDP: tokens are actions, and the reward comes at the end. Post-training usually uses $\gamma = 1$, which is fine because every answer has a finite length.
• Science and engineering. Optimal stopping, inventory control, energy storage and control of physical systems (for example the magnetic control of a tokamak plasma with deep RL, Degrave et al., Nature 2022) are MDPs. Small ones with a known model are solved exactly by the methods of lesson 02.

7. Common mistakes #

• The max in the wrong place. In $V^*$ the max is over the action, and the next states are still averaged with $P$. It is not $\max_{s'}$.
• Greedy from $V$ without a model. $\arg\max_a Q(s, a)$ needs $Q$. Turning $V$ into $Q$ needs $P$ and $R$. This is why model-free methods learn $Q$, not $V$.
• Mixing reward conventions. $r_t$ here is $R_{t+1}$ in Sutton and Barto. Fix one convention in your code.
• $\gamma = 1$ without termination. $I - P_\pi$ is singular when the policy never ends an episode.
• One return is not the value. A return $G_t$ is one random sample; $V^\pi(s)$ is its expectation.
• $V^\pi$ versus $V^*$. The greedy policy with respect to $V^\pi$ is not optimal in general; only greedy with respect to $V^*$ (or $Q^*$) is.

8. Check yourself #

1. Write $Q^\pi$ in terms of $V^\pi$, and $V^\pi$ in terms of $Q^\pi$.
   Answer

   $Q^\pi(s,a) = R(s,a) + \gamma \sum_{s'} P(s' \mid s,a) V^\pi(s')$ and $V^\pi(s) = \sum_a \pi(a \mid s) Q^\pi(s,a)$.
2. A reward of 1 arrives only at step 10 (all other rewards are 0), and $\gamma = 0.9$. What is $G_0$?
   Answer

   $G_0 = 0.9^{10} \cdot 1 \approx 0.349$. A reward ten steps ahead keeps about a third of its weight.
3. Why is the expectation equation linear but the optimality equation not?
   Answer

   For a fixed $\pi$ the action probabilities are constants, so $V$ appears linearly. In $V^*$ the max over actions depends on $V$ itself; a max of linear functions is piecewise linear, not linear.
4. Show that $\sum_a \pi(a \mid s) A^\pi(s, a) = 0$.
   Answer

   $\sum_a \pi(a \mid s)(Q^\pi(s,a) - V^\pi(s)) = \sum_a \pi(a \mid s) Q^\pi(s,a) - V^\pi(s) \sum_a \pi(a \mid s) = V^\pi(s) - V^\pi(s) = 0$, by the first link and because the probabilities sum to 1.
5. Why does a finite discounted MDP always have a deterministic optimal policy?
   Answer

   The policy that is greedy with respect to $Q^*$ is optimal in every state, and picking one maximising action per state gives a deterministic policy.
6. In the 4×4 gridworld with $\gamma = 1$, the random policy has $V^\pi = -14$ next to a terminal corner. What does $-14$ mean?
   Answer

   Each step gives $-1$ and there is no discount, so $-V^\pi(s)$ is the expected number of steps until the random walk reaches a terminal corner: 14 steps on average.

Recall cardsAnswer in your head first, then reveal. Add the cards to your review deck to see them again just before you would forget.

1. Name the five parts of a finite MDP.

   Show answer

2. Write the return recursion.

   Show answer

3. Define $V^\pi(s)$.

   Show answer

4. Write $Q^\pi(s, a)$ in terms of $V^\pi$.

   Show answer

5. Write $V^\pi(s)$ in terms of $Q^\pi$.

   Show answer

6. Give the matrix form of the Bellman expectation equation and its solution.

   Show answer

7. Why is $I - \gamma P_\pi$ invertible for $\gamma < 1$?

   Show answer

8. Write the Bellman optimality equation for $Q^*$.

   Show answer

9. What is the effective horizon for $\gamma = 0.99$?

   Show answer

10. Compute $G_0$ for the rewards $(2, 2, 2)$ with $\gamma = 0.5$.

    Show answer

Add these cards to my reviewOpen the review →

9. Interview angle #

• "What is the Bellman equation, and why does it have a unique solution?" The value is the reward now plus $\gamma$ times the expected value of the next state: $V^\pi = r_\pi + \gamma P_\pi V^\pi$. For $\gamma < 1$, $I - \gamma P_\pi$ is invertible (Neumann series), so there is exactly one solution.
• "What is the difference between $V$ and $Q$? Why do model-free methods prefer $Q$?" $Q$ fixes the first action. To act greedily from $V$ you need the model to compute $Q = R + \gamma P V$; from $Q$ you only need an argmax.
• "Why discount?" It makes infinite sums finite, sets an effective horizon $1/(1-\gamma)$, and (lesson 02) makes the Bellman operator a contraction. It also reduces variance in policy gradients (lesson 08).
• "How do you evaluate a policy in a small known MDP?" Build $P_\pi$ and $r_\pi$, and solve $(I - \gamma P_\pi) V = r_\pi$: $O(|\mathcal S|^3)$. Lesson 02 gives the iterative alternative.

10. Practice #

The notebook for this lesson runs in Colab. It has five exercises, each with a check cell and a folded solution:

1. discounted_return and returns_to_go: one backward pass with $G_t = r_t + \gamma G_{t+1}$.
2. induced_chain: build $P_\pi$ and $r_\pi$ from the arrays P[s, a, s'], R[s, a], pi[s, a].
3. policy_evaluation_linear: solve $(I - \gamma P_\pi) V = r_\pi$ and check $V^\pi(H) = 130/11$.
4. Monte Carlo check: simulate many episodes of the robot vacuum and compare the mean return with $V^\pi$.
5. q_from_v and v_from_q: the two links, and a round trip on the 4×4 gridworld.

11. Watch and read #

RL Course by David Silver - Lecture 2: Markov Decision ProcessGoogle DeepMind · David Silver, UCL RL course · 102 min

The classic lecture on Markov processes, returns, value functions and both Bellman equations, with backup diagrams.

Reinforcement Learning, by the BookMutual Information · 18 min

A short visual overview of MDPs, returns and value functions, following Sutton and Barto.

DeepMind x UCL RL Lecture Series - MDPs and Dynamic Programming [3/13]Google DeepMind · DeepMind x UCL RL lecture series (2021) · 104 min

A more recent lecture; the first half covers MDPs and the Bellman equations, the second half is lesson 02.

• Richard Sutton and Andrew Barto, Reinforcement Learning: An Introduction, 2nd ed., free PDF: §3.1–3.6 (MDPs, returns, policies, value functions, Bellman equations). Note the $R_{t+1}$ convention.
• OpenAI Spinning Up, Part 1: Key Concepts in RL: a short, precise summary of the same definitions.
• Alekh Agarwal, Nan Jiang, Sham Kakade, Wen Sun, Reinforcement Learning: Theory and Algorithms, free PDF: chapter 1 (MDPs, Bellman equations) for a compact, rigorous version.