Module 3 — Value functions and Bellman equations

Two questions organize the rest of the course. How good is this state? — that is the value function V. How good is this action in this state? — that is the action-value function Q. The Bellman equations tie both to themselves through one step of the MDP, and every algorithm of modules 4 to 9 is a way of turning that self-reference into a computation.

Two value functions, two uses

The state-value function of a policy π is the expected return starting from state s and following π from there:

$$V^\pi(s) = \mathbb{E}_\pi\left[\sum_{t=0}^\infty \gamma^t r_{t+1} \;\middle|\; s_0 = s\right]$$

The action-value function is the same but starting by forcing action a before letting π take over:

$$Q^\pi(s, a) = \mathbb{E}_\pi\left[\sum_{t=0}^\infty \gamma^t r_{t+1} \;\middle|\; s_0 = s, a_0 = a\right]$$

The relation between them is direct: V^π(s) = Σ_a π(a|s) Q^π(s, a). Why keep both, then? Because they answer different questions. V tells you the score of a policy; Q tells you which action to try next without needing to know the transition model. That distinction is the reason model-free algorithms — Q-learning, DQN — work at all.

The Bellman expectation equation

V^π and Q^π satisfy a self-referential equation that follows from the one-step decomposition of the return:

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

Read it aloud: the value of s under π equals the immediate reward plus γ times the value of the next state, averaged over what the policy does and what the environment does. This is a system of |S| linear equations in |S| unknowns — for FrozenLake, 16 equations in 16 unknowns. It is solvable in closed form.

The analogous equation for Q:

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

Both are called expectation equations because they express V (or Q) as an expectation over what would happen next under the current policy.

The Bellman optimality equation

Now stop evaluating a fixed policy and ask about the best possible one. The optimality equations replace the average over actions with a max:

$$V^*(s) = \max_a \sum_{s'} P(s'|s,a) \, [\, R(s,a,s') + \gamma V^*(s') \,]$$ $$Q^*(s, a) = \sum_{s'} P(s'|s,a) \, [\, R(s,a,s') + \gamma \max_{a'} Q^*(s', a') \,]$$

The optimal policy is then trivially recovered: π*(s) = argmax_a Q*(s, a). Everything to come is a way of estimating Q* — with the model when it is known (module 4), by sampling when it is not (modules 4, 5), with a table (modules 5, 6) or with a network (module 7).

Worked by hand on a 3×3 grid

Consider a 3×3 grid where cell (2, 2) is a terminal goal with reward +1, and every other transition has reward 0. Actions are up, down, left, right, deterministic, and γ = 0.9. Under the uniform random policy π(a|s) = 1/4, what is V^π((1, 1))?

Solving the linear system by hand for the four cells adjacent to the goal — (1, 2), (2, 1), (0, 2), (2, 0) — then propagating one more step gives, after simplification, V^π((1, 1)) ≈ 0.19. The exact value is not the point; the point is that the answer would be about 0.9 under an optimal policy — a factor of 5. That gap is what a learning algorithm has to close.

In code

import numpy as np

# Bellman expectation update as a fixed-point iteration.
def evaluate_policy(P, R, pi, gamma=0.99, tol=1e-8):
    n_states, n_actions = pi.shape
    V = np.zeros(n_states)
    while True:
        V_new = np.zeros(n_states)
        for s in range(n_states):
            for a in range(n_actions):
                for prob, s_next, reward, done in P[s][a]:
                    V_new[s] += pi[s, a] * prob * (reward + gamma * V[s_next] * (not done))
        if np.max(np.abs(V_new - V)) < tol:
            return V_new
        V = V_new

Running this on FrozenLake with the uniform policy converges in about 150 iterations and returns a vector where V[0] ≈ 0.014 — the random agent almost never reaches the goal, and its states are almost worthless. Under the optimal policy, V*[0] ≈ 0.82. The learning problem is exactly the gap between these two vectors.

What Bellman does not give you

The equations are correct even when P and R are unknown, but you cannot compute them without those. When the model is missing — the usual case — you replace expectations by samples (Monte Carlo, module 4) or one-step bootstraps (temporal difference, module 5). The math stays the same; the estimator changes.

Summary

• V^π(s) scores a policy, Q^π(s, a) scores an action; the second is what lets you improve without knowing the model.
• The Bellman expectation equation ties V^π (or Q^π) to a one-step average — a linear system with a unique solution.
• The Bellman optimality equation replaces the average over actions by a max, and its solution is the optimal V* (or Q*).
• All following algorithms turn these fixed-point equations into an iterative computation, with a model or with samples.

Next module: two ways to solve them — dynamic programming when the model is known, Monte Carlo when it is not.