76 - The Bellman Equation Derived in Full, and Why Future Reward Must Be Discounted

If there is a single formula to understand well in all of reinforcement learning, it is the Bellman equation. Every algorithm we will see later (Q-Learning, SARSA, Deep Q-Learning) is a way of solving it, or of getting close to solving it, when the environment is not known. Its content is an almost trivial idea with enormous consequences: the value of a situation is the reward I take right away plus the value of the situation I find myself in afterwards. Here we derive it in full, starting from the definition of return and skipping no steps; we explain why the discount γ is needed, with three different arguments and with numbers; we use it to compute, without simulating anything, the table of values of the article on the Markov decision process; and we derive the version for the optimal policy, which is the one that really matters.

The vocabulary you need

We reuse the terms of the MDP article (state, action, policy, return, γ, P, R) and add a few. The expected value E[X] is the average you would obtain by repeating the experiment infinitely many times, and E[X | Y] is the average of X knowing the value of Y. The state value function v_π(s) = E_π[G_t | S_t = s] answers "how good is this situation for me, if I play according to π?"; the action value function q_π(s, a) = E_π[G_t | S_t = s, A_t = a] says how much it is worth to do a in s and then follow π.

The Bellman equation ties the value of a state to the values of the successor states; it is named after Richard Bellman, to whom Sutton and Barto attribute the term "dynamic programming". A backup is the operation of computing the value of a state from those of its successors, and a backup diagram draws it; a sweep is one pass of updates over all the states. A fixed point is a value that the update leaves unchanged: the correct value is the fixed point of the Bellman equation. Finally v*(s) is the maximum value obtainable from s among all policies, and a policy that is greedy with respect to a value chooses, in every state, the action that maximises "reward plus value of the successor".

The analogy: the travel time left

You are in the car and the satnav tells you "arrival in 42 minutes". How does it know? It does not simulate the whole journey from the start: it reasons like this. "From here to the next junction there are 3 minutes. At the junction, I already know (by the same logic) that 39 minutes remain. So from here 3 + 39 = 42 remain." The time left from here is the cost of the first little stretch plus the time left from where I arrive. This is all of Bellman: the value of a place is the cost (the reward) of the next step plus the value of the next place. If you add uncertainty ("from the junction I can go left with 70% or right with 30%") the time left is a weighted average over the possibilities. And there is a detail that will require the discount: an hour ten years from now is worth less to you than an hour now.

First of all: why must future reward be discounted?

In the previous article we defined the discounted return G_t = R_{t+1} + γR_{t+2} + γ²R_{t+3} + … with 0 ≤ γ ≤ 1 without saying why. There are three independent reasons, and it pays to know them all because each says something different about how to choose γ.

Reason 1: the sum must have a finite value (the geometric series)

If a problem never ends (or can last a long time) and the rewards are, say, always 1, the sum 1 + 1 + 1 + … diverges: you cannot compare two policies with an infinite return. With the discount the sum is a geometric series, which is computed in two lines. Let S = 1 + γ + γ² + γ³ + …. Multiplying by γ: γS = γ + γ² + γ³ + …, that is γS = S − 1. So S − γS = 1, whence

S = 1 / (1 − γ)         (for 0 ≤ γ < 1)

In general, if every reward is at most R_max in absolute value, the return cannot exceed R_max / (1 − γ): it is finite. With γ = 0.9 the sum of many "1"s is worth 10; with γ = 0.99, 100. The number 1/(1 − γ) is, in a precise sense, the agent's "horizon": roughly how many steps it counts in deciding.

Reason 2: the discount is the probability that the story continues

Imagine that at every step the episode may suddenly end (the car breaks down, the player quits, the robot runs out of charge): it continues with probability γ and ends with probability 1 − γ. The reward of step k is collected only if you survived the k previous steps, and the probability is γ^k. Then the expected value of the undiscounted sum of the rewards is

E[ Σ_k R_{k+1} · 1{I am still alive at step k} ] = Σ_k γ^k · E[R_{k+1}]

which is exactly the discounted return. So γ can be read as "the per-step probability that the world does not end". We verify it with a simulation in the code below: reward 1 per step, episode that continues with probability γ.

Reason 3: the future is more uncertain and (often) we prefer the immediate

A euro today is worth more than a euro in a year, because in a year you might not have it, or you might have invested it. In the same way, in RL, a distant reward depends on many things that may turn out differently. The closer γ is to 0, the more "short-sighted" the agent; the closer to 1, the more "far-sighted". The right value depends on the problem: for a robot that has to grasp an object a few steps of horizon are enough, for playing chess a whole game counts.

# Why a discount? Three views of the same number.
import numpy as np
rng = np.random.default_rng(0)
for gamma in (0.5, 0.9, 0.99):
    closed = 1 / (1 - gamma)                                            # sum of gamma^k for k = 0, 1, 2, ...  (geometric series)
    horizon = int(np.ceil(np.log(0.01) / np.log(gamma)))                # steps after which gamma^k < 1%
    # view 3: reward 1 per step, but at every step the episode SURVIVES with probability gamma. Undiscounted total reward:
    lengths = []
    for _ in range(20000):
        n = 1
        while rng.random() < gamma:                                    # survive another step with prob. gamma
            n += 1
        lengths.append(n)
    print(f"gamma={gamma}:  discounted sum of 1s = {closed:6.2f}   effective horizon ~{horizon:3d} steps   mean undiscounted reward if the episode ends with prob 1-gamma per step: {np.mean(lengths):6.2f}")

# Output (two consecutive runs, same output):
# gamma=0.5:  discounted sum of 1s =   2.00   effective horizon ~  7 steps   mean undiscounted reward if the episode ends with prob 1-gamma per step:   1.99
# gamma=0.9:  discounted sum of 1s =  10.00   effective horizon ~ 44 steps   mean undiscounted reward if the episode ends with prob 1-gamma per step:  10.04
# gamma=0.99:  discounted sum of 1s = 100.00   effective horizon ~459 steps   mean undiscounted reward if the episode ends with prob 1-gamma per step:  99.79

For each γ the listing computes three things. The first is closed = 1/(1 − γ), the geometric sum: 2, 10, 100. The second is horizon, the number of steps after which the weight γ^k falls below 1%, that is log(0.01)/log(γ): 7, 44, 459 steps, a window of attention that widens very quickly with γ. The third is the simulation of reason 2: 20,000 episodes in which, at every step, the world continues with probability γ (rng.random() < gamma); the mean duration, that is the total undiscounted reward (1 per step), is 1.99, 10.04, 99.79 and coincides with 1/(1 − γ) within sampling noise. The three reasons describe the same object from three points of view. The fixed seed (default_rng(0)) makes the output reproducible; with a different seed the two sample means change in the last digit.

The derivation of the Bellman equation

Now the central piece. We start from the definitions: the return G_t = R_{t+1} + γ G_{t+1} (the recursion derived in the previous article) and the value v_π(s) = E_π[G_t | S_t = s]. We proceed by steps, declaring each time what is being used.

Step 1: substitute the recursion of the return.

v_π(s) = E_π[ G_t | S_t = s ]
       = E_π[ R_{t+1} + γ G_{t+1} | S_t = s ]

Step 2: split using the linearity of expected value (the mean of a sum is the sum of the means, and constants come out):

v_π(s) = E_π[ R_{t+1} | S_t = s ]  +  γ · E_π[ G_{t+1} | S_t = s ]

Step 3: open the first term. The immediate reward depends on the action I choose (with probability π(a|s)) and on the next state the world sends me to (with probability P(s′|s,a)). By the definition of expected value as a weighted sum over the possibilities:

E_π[ R_{t+1} | S_t = s ] = Σ_a π(a|s) Σ_{s′} P(s′|s,a) · R(s,a,s′)

Step 4: open the second term with the law of total probability for expected values. To compute the mean of G_{t+1} knowing only S_t = s, we condition on the possible values of (A_t, S_{t+1}) and weight them by their probability:

E_π[ G_{t+1} | S_t = s ] = Σ_a π(a|s) Σ_{s′} P(s′|s,a) · E_π[ G_{t+1} | S_t = s, A_t = a, S_{t+1} = s′ ]

Step 5: the Markov property. The future return G_{t+1} depends on the past only through the present state, which here is S_{t+1} = s′. So, once s′ is known, knowing also that before we were in s and did a adds nothing:

E_π[ G_{t+1} | S_t = s, A_t = a, S_{t+1} = s′ ] = E_π[ G_{t+1} | S_{t+1} = s′ ] = v_π(s′)

The last equality is the definition of v_π applied to the state s′. This is the step where the Markov property really comes in: without it the equation does not hold.

Step 6: put it back together. We put the results of steps 3, 4 and 5 into step 2:

v_π(s) = Σ_a π(a|s) Σ_{s′} P(s′|s,a) · [ R(s,a,s′) + γ · v_π(s′) ]

This is the Bellman equation for v_π. In words: the value of a state is the average, over my choices (π) and over the world's responses (P), of "reward now plus γ times the value of the state I end up in".

The backup diagram draws exactly this sum. At the top the state s; below, the black nodes are the actions, with the probabilities π(a|s) on the branches; further down, the successor states with the probabilities P(s′|s,a); at the bottom, what is averaged, r + γ·v(s′). "Backup" because the value travels from the bottom (the successors, already known) to the top (the state we want to evaluate).

The action version and the link between the two

With the same reasoning you derive the equation for q_π. The value of doing a in s no longer has the average over actions at the first level (the action is already given), but it has it at the next level:

q_π(s,a) = Σ_{s′} P(s′|s,a) · [ R(s,a,s′) + γ · Σ_{a′} π(a′|s′) · q_π(s′,a′) ]
v_π(s)   = Σ_a π(a|s) · q_π(s,a)

The second line says that the value of the state is the weighted average of the values of the actions; the first, that the value of an action looks one step ahead and then uses the same policy. The two are two views of the same structure.

Using it: iterative policy evaluation

If we know P (the table of the MDP), the Bellman equation becomes a recipe for computation: we do not know v_π but we know it must satisfy that equality; we start from any estimate (zero everywhere) and repeatedly apply the right-hand side as an update, until it no longer changes. This is the fixed point. The test bench is the 4×4 grid of the MDP article, which I reproduce here in compact form so that the listing can be run on its own: sixteen states, two terminals in the corners (0 and 15), reward −1 at every step, P[s][a] as a list of four-element tuples (probability, next_state, reward, done). With slip=0.0 (the default) every action has a single outcome.

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()]

This is the same grid that, for example, Sutton and Barto use as Example 4.1 (episodic undiscounted task, reward −1 on all transitions, equiprobable random policy), where the final value is the opposite of the expected number of steps to termination. With this class, iterative evaluation is written as follows, with γ = 1 (finite episodes).

def policy_evaluation(env, pi, gamma=1.0, tol=1e-10, history=()):
    """Iterative policy evaluation: turn the Bellman equation into an update and sweep until nothing changes.
    pi[s][a] = probability of action a in state s."""
    V = np.zeros(env.n_states)
    snapshots = {}
    for sweep in range(1, 10_000):
        delta = 0.0
        for s in range(env.n_states):
            v_new = sum(pi[s][a] * sum(p * (r + gamma * V[s2] * (not done))        # no future value after a terminal step
                                       for p, s2, r, done in env.P[s][a])
                        for a in range(env.n_actions))
            delta = max(delta, abs(v_new - V[s]))
            V[s] = v_new                                                          # in-place update
        if sweep in history:
            snapshots[sweep] = V.copy()
        if delta < tol:
            return V, sweep, snapshots
    return V, sweep, snapshots

env = GridWorld()
random_pi = np.full((env.n_states, 4), 0.25)                   # equiprobable random policy
V, sweeps, snaps = policy_evaluation(env, random_pi, gamma=1.0, history=(1, 2, 3, 10))
for k, Vk in snaps.items():
    print(f"after {k:2d} sweeps:", np.round(Vk.reshape(4, 4), 1).tolist()[1])      # second row, as a taste
print(f"converged after {sweeps} sweeps. v_pi:")
print(np.round(V.reshape(4, 4), 2))

# Output (two consecutive runs, same output):
# after  1 sweeps: [-1.0, -1.5, -1.7, -1.8]
# after  2 sweeps: [-1.9, -2.8, -3.2, -3.4]
# after  3 sweeps: [-2.8, -4.0, -4.7, -4.9]
# after 10 sweeps: [-7.8, -10.4, -11.8, -11.9]
# converged after 272 sweeps. v_pi:
# [[  0. -14. -20. -22.]
#  [-14. -18. -20. -20.]
#  [-20. -20. -18. -14.]
#  [-22. -20. -14.   0.]]

policy_evaluation starts with V at zero. In each sweep it runs through all the states and computes the Bellman formula for each: the double sum Σ_a π(a|s) Σ P·(r + γ·V[s2]); the factor (not done) cancels the value of the successor if the episode is over, because after a terminal state there is no future. The update is "in place" (V[s] = v_new): the states updated earlier in the same sweep are already used by the others. delta is the maximum change in the sweep; when it falls below tol = 10⁻¹⁰, we stop.

After 1 sweep the value of each state is about −1: only the reward of the first step has been "seen". After 2 sweeps, between −2 and −3: the information about the cost has propagated by one step. After 10 sweeps we are between −8 and −12 and the value is still dropping, because random walks are long. After 272 sweeps it converges, and the final table (0, −14, −20, −22 …) is the one the book reports for this example in Figure 4.1. You can see the idea of the backup: the value "spreads" starting from the terminals (where it is 0) outwards, one step per sweep.

Without iterating: a linear system

The Bellman equation for a fixed policy is linear in v: written in matrix form it is v = r_π + γ P_π v, where P_π[s, s′] is the probability of going from s to s′ following π and r_π[s] is the expected immediate reward. It is solved with (I − γ P_π) v = r_π, a system of 16 equations in 16 unknowns, with one call to numpy.linalg.solve.

# The same numbers WITHOUT iterating: v = r_pi + gamma * P_pi v   ->   (I - gamma P_pi) v = r_pi   (a linear system)
def policy_matrices(env, pi, gamma=1.0):
    n = env.n_states
    P_pi = np.zeros((n, n)); r_pi = np.zeros(n)
    for s in range(n):
        for a in range(env.n_actions):
            for p, s2, r, done in env.P[s][a]:
                r_pi[s] += pi[s][a] * p * r                           # expected immediate reward under pi
                if not done:
                    P_pi[s, s2] += pi[s][a] * p                       # probability of moving s -> s2 (terminal: no continuation)
    return P_pi, r_pi

P_pi, r_pi = policy_matrices(env, random_pi)
V_exact = np.linalg.solve(np.eye(env.n_states) - 1.0 * P_pi, r_pi)
print("linear system vs iteration, max difference:", np.abs(V_exact - V).max())
residual = np.abs(r_pi + P_pi @ V_exact - V_exact).max()
print("Bellman residual  max| r + P v - v | :", residual)

# Output (two consecutive runs, same output):
# linear system vs iteration, max difference: 1.0726104449076956e-09
# Bellman residual  max| r + P v - v | : 3.552713678800501e-15

policy_matrices builds P_π and r_π by accumulating, for each state, the probabilities and rewards weighted by the policy; it skips the continuation term when the episode ends (if not done). Then np.linalg.solve(np.eye(n) − γ·P_π, r_π) solves the system. The result coincides with the iteration (maximum difference of the order of 10⁻⁹) and the Bellman residual, that is how much the solution violates the equation, is of the order of 10⁻¹⁵: zero to machine precision. The fact that the system is solvable with γ = 1 depends on the episodes terminating: the matrix I − P_π is invertible because from the terminals nothing continues. The Bellman equation thus has a solution that is computed in two independent ways, and the two coincide.

# Compare with the Monte Carlo table of the previous lesson
V_mc = np.array([[0.0, -13.8, -19.6, -21.7],
                 [-14.0, -18.4, -19.8, -20.4],
                 [-19.9, -19.9, -18.4, -14.1],
                 [-22.1, -20.3, -14.2, 0.0]]).ravel()
print("largest gap between Monte Carlo and the exact value:", round(np.abs(V_mc - V_exact).max(), 2))

# Output (two consecutive runs, same output):
# largest gap between Monte Carlo and the exact value: 0.4

The comparison with the previous article: the Monte Carlo estimate, obtained by averaging 4000 episodes per state, differs from the exact value by at most 0.4, on values that reach −22. A standard error of about 0.3 per cell, measured in the MDP article, makes it plausible that over 14 cells the maximum gap is 0.4: it is sampling noise. The Monte Carlo method has to simulate thousands of episodes per state and returns a noisy estimate; Bellman with the model gives the exact value in a fraction of a second (the whole listing of this article runs in about two seconds on this machine, one trial). The price is that it requires knowing P.

What the discount does to the computation and to the answer

We repeat the evaluation of the random policy for different values of γ, counting the sweeps needed and looking at two states: state 1, adjacent to the goal, and state 10, far away.

# How does gamma change the work and the answer?  Policy evaluation of the random policy for different discount factors
print(f"{'gamma':>6s} {'sweeps':>7s}   value of state 1 (next to the goal)   value of state 10 (far from the goal)")
for gamma in (0.0, 0.5, 0.9, 0.99, 1.0):
    Vg, sweeps, _ = policy_evaluation(env, random_pi, gamma=gamma)
    print(f"{gamma:6.2f} {sweeps:7d}   {Vg[1]:30.2f}   {Vg[10]:30.2f}")

# Output (two consecutive runs, same output):
#  gamma  sweeps   value of state 1 (next to the goal)   value of state 10 (far from the goal)
#   0.00       2                            -1.00                            -1.00
#   0.50      23                            -1.69                            -1.92
#   0.90      95                            -5.28                            -6.61
#   0.99     231                           -11.95                           -15.32
#   1.00     272                           -14.00                           -18.00

Two effects, both measured. The cost of the computation grows with γ: from 2 sweeps at γ = 0, 23 at 0.5, 95 at 0.9, 231 at 0.99, 272 at 1. With larger γ the information has to propagate over a longer horizon, so more sweeps are needed for the same tolerance. The answer changes with γ: with γ = 0 the agent is completely short-sighted and all states are worth −1 (it looks only at the reward of the next step, and that is −1 everywhere), so it does not distinguish "near the goal" from "far". With higher γ the values differentiate: at 0.99 state 1 is worth −11.95 and state 10 is worth −15.32, at 1 they are worth −14 and −18. The value of γ is part of the definition of the problem: what the agent considers "good" depends on how far it looks.

The Bellman optimality equation

Evaluation says how much one policy is worth. What we really want is the best one. Let v*(s) be the maximum value obtainable from s among all policies. In s the optimal agent chooses the action that maximises "reward now plus (optimal) value of where I arrive"; there is no reason to average over worse actions. Replacing, in the Bellman equation, the average over actions with the maximum:

v*(s) = max_a Σ_{s′} P(s′|s,a) · [ R(s,a,s′) + γ · v*(s′) ]
q*(s,a) = Σ_{s′} P(s′|s,a) · [ R(s,a,s′) + γ · max_{a′} q*(s′,a′) ]

In the case of q* the structure is exactly the one that will turn into Q-Learning. Here the maximum makes the equation non-linear: it cannot be solved with a linear system, but you can use the same trick of repeated updating, called value iteration.

def value_iteration(env, gamma=1.0, tol=1e-10):
    """Bellman OPTIMALITY equation as an update:  V(s) <- max_a sum_{s'} P (r + gamma V(s'))."""
    V = np.zeros(env.n_states)
    for sweep in range(1, 10_000):
        delta = 0.0
        for s in range(env.n_states):
            q = [sum(p * (r + gamma * V[s2] * (not done)) for p, s2, r, done in env.P[s][a]) for a in range(env.n_actions)]
            delta = max(delta, abs(max(q) - V[s]))
            V[s] = max(q)
        if delta < tol:
            return V, sweep
    return V, sweep

def greedy_policy(env, V, gamma=1.0):
    arrows = "^>v<"
    out = []
    for s in range(env.n_states):
        if s in env.terminals:
            out.append("G"); continue
        q = [sum(p * (r + gamma * V[s2] * (not done)) for p, s2, r, done in env.P[s][a]) for a in range(env.n_actions)]
        best = np.flatnonzero(np.isclose(q, max(q)))                 # all the actions that tie for best
        out.append("".join(arrows[a] for a in best))
    return out

V_star, sweeps = value_iteration(env)
print(f"value iteration converged in {sweeps} sweeps. v*:")
print(np.round(V_star.reshape(4, 4), 1))
pol = greedy_policy(env, V_star)
for r in range(4):
    print("  ".join(f"{pol[r * 4 + c]:>4s}" for c in range(4)))

# Output (two consecutive runs, same output):
# value iteration converged in 4 sweeps. v*:
# [[ 0. -1. -2. -3.]
#  [-1. -2. -3. -2.]
#  [-2. -3. -2. -1.]
#  [-3. -2. -1.  0.]]
#    G     <     <    v<
#    ^    ^<  ^>v<     v
#    ^  ^>v<    >v     v
#   ^>     >     >     G

value_iteration has the same structure as the evaluation, with max(q) in place of the weighted average over the policy. It converges in 4 sweeps (against 272): by maximising, the information "the shortest road" propagates immediately instead of waiting for the random walk. The result v* is, with the sign changed, the distance in steps from the nearest terminal: −1 for the cells adjacent to a corner, −2, −3 for the farthest. The arrows show the greedy policy with respect to v*: greedy_policy computes, for each state, the value of each action q and takes those that maximise (np.isclose to find the ties). Where several actions are equivalent they are all shown: state 6 has four arrows because every direction leads to a cell worth −2 and therefore gives the same value −3. This policy is optimal for this deterministic grid.

Why it is not enough: the limits of this approach

The first limit is that you need the model: you must know P(s′|s,a) and R, that is the entire table, and in real problems (a video game, a robot) you do not have it. The second is that you have to sweep all the states: with 16 states it is instantaneous, with the states of a chess game or a video game the table does not fit in memory. The third is that this is planning and not learning: there is no experience, you reason on the model. These three limitations define the road: if you do not know P, you can estimate the Bellman update from samples of experience, and that is Q-Learning; if the states are too many for a table, you use a neural network to approximate q, and that is Deep Q-Learning.

The trade-offs

On γ: high means a long horizon and far-sighted behaviour, but slower computation (231 sweeps at 0.99 against 23 at 0.5) and learning more sensitive to noise; low means short-sighted but fast. Between iterative evaluation and the linear system: the linear system is exact and quick for tens or a few thousand states (the cost of a direct solution grows with the cube of the number of states), while the iteration scales better and suits large problems. And between planning and learning: with the model you do dynamic programming, without it you learn from samples.

Real pitfalls

1. Forgetting the "not done" term. If the value of the successor is added even after a terminal state, the agent "sees" future where there is none (and inflated values).
2. Mistaking γ for a learning parameter. γ is a property of the problem (how far the goal looks ahead), not a hyperparameter to optimise on the reward obtained: by changing it you change the problem.
3. Using γ = 1 on endless problems. The return diverges. With finite, reachable episodes it is allowed.
4. Confusing v and q. v(s) averages over actions according to the policy; q(s, a) fixes the first action.
5. Verifying an implementation without the Bellman residual. It is the simplest test: compute max |r + γ P v − v|; if it is not close to zero, the update is wrong.

The first two pitfalls produce values that are numerically plausible and wrong: an extra future after the terminal inflates the estimates, a γ chosen to push the reward up changes the problem you are solving. The fifth is the general remedy: the Bellman residual is a check that does not depend on the algorithm that produced v, so you can apply it to any implementation, including those of the later articles.

Exercises with solutions

1. A state has two equiprobable actions. The first gives reward 2 and leads to a state of value 10, the second gives −1 and leads to one of value 20. With γ = 0.5, what is the state worth?
   Solution: 0.5·(2 + 0.5·10) + 0.5·(−1 + 0.5·20) = 0.5·7 + 0.5·9 = 8.
2. With γ = 0.95, what is the sum of constant rewards equal to 1 worth?
   Solution: 1/(1 − 0.95) = 20.
3. At which step of the derivation is the Markov property needed?
   Solution: at step 5: saying that E[G_{t+1} | S_t=s, A_t=a, S_{t+1}=s′] = v_π(s′), that is that the past does not count once the current state is known.
4. Why does value iteration (4 sweeps) converge much faster than the evaluation of the random policy (272)?
   Solution: because the maximum immediately chooses the action towards the goal; the random policy wanders and its value depends on long walks, which need many sweeps to propagate.

The first two exercises are solved with the formula and an addition: they serve to check that you have understood the weighted average and the geometric series. The last two are interpretation and they are the ones that count: if you can say where Markov comes in and why the maximum speeds up propagation, you have understood why the equation works, not just how it is used.

Frequently asked questions

What is the difference between v and q?

v_π(s) is the value of a state following the policy; q_π(s, a) is the value of doing a specific action in the state and then following the policy. The link is v_π(s) = Σ_a π(a|s) q_π(s, a).

Do you really need to know the model to use Bellman?

To compute the value as in this article, yes, because you need P. When P is not known the update is estimated from samples of experience, which is what Q-Learning does.

Why does value iteration converge in 4 sweeps and the evaluation in 272?

Because value iteration maximises and immediately propagates the shortest road, while the random policy wanders and its value depends on long walks.

What you can do now

You can derive the Bellman equation, v_π(s) = Σ_a π(a|s) Σ_{s′} P(s′|s,a)[R + γ v_π(s′)], in six steps from the recursion of the return, and you can say where the linearity of expected value, the law of total probability and the Markov property come in. You can explain the discount with three equivalent readings and see that it controls both the answer (with γ = 0 all states are worth −1) and the cost of the computation (from 2 to 272 sweeps). On the grid, iterative evaluation and the linear system give the same table; the optimality equation, with a maximum in place of the average, is solved in 4 sweeps and gives v* = −distance from the goal. All of this requires the model P. In the next article we see what happens when the reward arrives late and how easy it is to write it badly (Delayed Rewards, Reward Shaping and Reward Hacking); then we learn to do without the model.