Policies, Value Functions, and Bellman Equations

"Ask me what a state is worth and I will not answer quickly. I am summing, right now, over every future that could unfold from here: every action you might take, every coin the world might flip, every reward waiting down each branch, discounted by how far off it sits. Give me a moment. I am imagining all of it, patiently, so that you do not have to."

A Value Function Patiently Summing Up Every Future It Can Imagine

In Section 22.2 we built the Markov decision process itself: the tuple $(\mathcal{S}, \mathcal{A}, P, R, \gamma)$ of states, actions, a transition kernel $P(s' \mid s, a)$, a reward function $R(s,a)$, and a discount factor $\gamma$, together with the Markov property that the next state depends only on the current state and action, not on the path that led there. That section described the world; it did not yet describe the agent, nor what it means for the agent to behave well. This section supplies both. It is the conceptual heart of the chapter: once you can write down what a policy is, score it with a value function, and characterize the value of the best policy through the Bellman equations, every subsequent algorithm, value iteration and policy iteration in Section 22.4, the temporal-difference and Q-learning methods of Chapter 24, the deep value networks of Chapter 25, is a way of computing or approximating one of the objects defined here. We use the unified notation of Appendix A throughout: $G_t$ the return, $\pi$ the policy, $V^\pi$ and $Q^\pi$ the value functions, $V^\ast$ and $Q^\ast$ their optimal counterparts.

The recurrence at the center of this section is one the reader of this book has met before in a different costume. The Bellman expectation equation, value today equals reward now plus discounted value of the next state, is the exact decision-making cousin of the filtering recursions of Chapter 7, where a belief today was updated into a belief tomorrow by a one-step recursion. There the recursion propagated probability forward in time; here it propagates value backward from the future. The Markov property is what licenses both: when the future depends on the present alone, a problem over an infinite horizon collapses into a one-step relationship between adjacent times. That collapse, the same collapse that made the Kalman filter tractable, is what makes sequential decision making tractable, and it is the through-line of this entire part.

The four competencies this section installs are these: to write a policy as a deterministic map or a stochastic distribution $\pi(a \mid s)$ and state the objective as maximizing expected return; to define $V^\pi$ and $Q^\pi$ as expected returns and explain the division of labor between scoring a situation and scoring a move; to derive and read both the Bellman expectation and Bellman optimality equations, and to recognize $V^\ast$ and the greedy optimal policy; and to evaluate a fixed policy in practice, both by iterating the Bellman operator and by solving the linear system, and to recognize the library call that does it for you. These are the load-bearing skills for the rest of Part VI.

1. Policies and the Objective: Behavior and What It Maximizes Beginner

An agent's behavior is captured entirely by its policy, a rule that tells it which action to take in each state. The simplest form is a deterministic policy, a function $\pi : \mathcal{S} \to \mathcal{A}$ that names exactly one action per state, written $a = \pi(s)$. More generally a stochastic policy specifies a probability distribution over actions in each state, written $\pi(a \mid s)$, the probability of choosing action $a$ when in state $s$, with $\sum_{a} \pi(a \mid s) = 1$. A deterministic policy is the special case that puts all its probability mass on a single action. Stochasticity is not a mere technical convenience: it is how an agent explores alternatives it is unsure about (the central theme of the bandits in Chapter 24), and in the partially observed and game-theoretic settings of Chapter 23 the optimal policy can be genuinely random.

Why distinguish the two forms so carefully at the outset? Because a deep and convenient fact about fully observed MDPs, which we will see fall out of the Bellman optimality equation in subsection three, is that there always exists an optimal policy that is deterministic. The agent never needs to randomize to act optimally when it can see the full state. Stochastic policies still matter enormously: they are the objects we differentiate in the policy-gradient methods of Chapter 25, and they are indispensable during learning when the agent does not yet know which action is best. But the target the agent is aiming at, the optimal policy, can be taken to be a clean deterministic map, which is why so much of the dynamic programming in Section 22.4 searches over deterministic policies without loss.

What does the agent want? It wants to maximize the return, the total reward it accumulates over time, with future rewards discounted by $\gamma \in [0,1)$ so that a reward $k$ steps away is worth $\gamma^k$ of an immediate one. The return from time $t$ is the discounted sum

The discount factor does double duty. Mathematically, with bounded rewards and $\gamma < 1$ the infinite sum converges (bounded by $R_{\max}/(1-\gamma)$), so the objective is well defined even over an unbounded horizon. Behaviorally, $\gamma$ encodes how far-sighted the agent is: near $0$ it is myopic and grabs immediate reward, near $1$ it is patient and plans for the long term. Because $G_t$ is a random variable (the trajectory depends on the policy's randomness and the environment's transitions), the agent maximizes its expectation. The objective, for a start distribution $s_0 \sim d_0$, is

where the subscript $\pi$ on the expectation means actions are drawn from $\pi$ and states evolve under $P$. This single scalar, expected discounted return, is the quantity every algorithm in Part VI is ultimately trying to make large. Everything that follows, value functions and Bellman equations alike, is apparatus for reasoning about and optimizing $J(\pi)$.

2. Value Functions: Scoring a Situation and Scoring a Move Beginner

The objective $J(\pi)$ is a single number summarizing a whole policy. To reason about where a policy is doing well and to improve it locally, we need a quantity attached to each state. That quantity is the state-value function $V^\pi$, the expected return from a given state when following $\pi$ thereafter:

Read $V^\pi(s)$ as a score for a situation: it answers "how good is it to be in state $s$, given that I will act according to $\pi$ from here on?" A high-value state is one from which the policy can expect to collect a lot of discounted future reward; a low-value state is a poor place to find yourself. Closely related, and often more directly useful, is the action-value function $Q^\pi$, the expected return from taking a specific action $a$ in state $s$ and only then following $\pi$:

Read $Q^\pi(s,a)$ as a score for a move: it answers "how good is it to take action $a$ right now in state $s$, if I then revert to $\pi$?" The two functions are tied together by a pair of relations that will recur constantly. Averaging $Q^\pi$ over the policy's action distribution recovers $V^\pi$, and expanding one step of reward-then-next-state inside $Q^\pi$ expresses it through $V^\pi$:

The first relation says the value of a situation is the policy-weighted average of the values of the moves available in it. The second says the value of a move is the immediate reward plus the discounted value of wherever that move lands you, averaged over the environment's transition randomness. This second relation is the conversion that the numeric example below exercises, and it is the seed of the Bellman equations of subsection three.

3. The Bellman Equations: Expectation and Optimality Intermediate

The defining structural property of value functions is that they are self-consistent across one step of time. The return from now decomposes into the reward earned on the next step plus the discounted return from the state you transition into, $G_t = R_{t+1} + \gamma G_{t+1}$. Taking expectations of both sides, conditioned on the current state and the policy, turns this trivial identity into the Bellman expectation equation for $V^\pi$, a recursion that ties the value of each state to the values of its successors:

The same one-step decomposition written for the action-value function gives the Bellman expectation equation for $Q^\pi$, where the successor's value is itself averaged over the policy's next action:

These are not approximations or update rules; they are exact equalities that the true value of the policy $\pi$ must satisfy at every state. For a finite MDP with $n$ states, the $V^\pi$ system is $n$ linear equations in the $n$ unknowns $V^\pi(s)$, and that linearity is exactly what subsection five exploits to solve it in closed form. The expectation equations are the foundation of policy evaluation: given a fixed $\pi$, find the $V^\pi$ that satisfies them.

Evaluation, though, is not the agent's goal; optimization is. We want the best achievable value, the optimal state-value function $V^\ast(s) = \max_\pi V^\pi(s)$ and the optimal action-value function $Q^\ast(s,a) = \max_\pi Q^\pi(s,a)$. These satisfy their own self-consistency, the Bellman optimality equations, in which the policy-weighted average over actions is replaced by a $\max$ over actions, because an optimal agent does not average over what it might do, it takes the best:

The single structural change from expectation to optimality, replacing $\sum_a \pi(a\mid s)$ by $\max_a$, has a large consequence: the optimality equations are nonlinear (the $\max$ is not a linear operation), so they cannot be solved by the linear-system method that works for a fixed policy. They are solved instead by iterative dynamic programming, value iteration and policy iteration, which is the entire subject of Section 22.4. Once $V^\ast$ or $Q^\ast$ is known, the optimal policy is read off by acting greedily: in every state pick the action that attains the max,

That this greedy policy is deterministic is the formal source of the claim from subsection one: a fully observed MDP always admits a deterministic optimal policy. The $Q^\ast$ form makes the greedy choice especially clean, $\pi^\ast(s) = \arg\max_a Q^\ast(s,a)$ uses no model at all, which is the structural reason value-based reinforcement learning targets $Q$.

4. Policy Improvement: Acting Greedily Never Hurts Intermediate

We now have two tools, evaluation (find $V^\pi$ for a given $\pi$) and the greedy operation (pick the best action against a value function). The policy-improvement theorem is the bridge that turns these two tools into an algorithm for finding the optimal policy, and it is the single most important idea in this section after the Bellman equations themselves. Informally it says: if you evaluate any policy and then act greedily with respect to its value function, the resulting new policy is at least as good as the old one, everywhere.

Concretely, given a policy $\pi$ with value function $V^\pi$, define a new policy $\pi'$ that acts greedily with respect to $Q^\pi$, that is $\pi'(s) = \arg\max_a Q^\pi(s,a)$. The theorem guarantees $V^{\pi'}(s) \ge V^\pi(s)$ for every state $s$. The argument is short and worth seeing because it explains why greediness works. By construction the greedy action does at least as well as the policy's own action under the old value function, so $Q^\pi(s, \pi'(s)) \ge \sum_a \pi(a\mid s) Q^\pi(s,a) = V^\pi(s)$. Now apply that inequality repeatedly, unrolling one step at a time:

Each inequality replaces one more step of the old policy by the greedy choice, and because the bound never reverses, telescoping the whole chain gives $V^\pi(s) \le V^{\pi'}(s)$. The greedy step never makes things worse. Even better, if $\pi'$ equals $\pi$ (greedy improvement changed nothing), then $V^\pi$ satisfies the Bellman optimality equation, so $\pi$ is already optimal. Improvement strictly helps until you reach the optimum, then stops, with no false summits along the way.

This is the engine of policy iteration in Section 22.4: alternate evaluation (compute $V^\pi$, the subject of subsection five) with greedy improvement (compute $\pi'$), and because each round strictly improves the policy on a finite MDP with finitely many policies, the process must terminate at the optimum in a finite number of steps. The same logic, evaluate then act greedily, reappears generalized as generalized policy iteration, the unifying pattern behind nearly every reinforcement-learning algorithm in Chapter 24 and Chapter 25; even an actor-critic agent is doing approximate evaluation (the critic) and approximate improvement (the actor) interleaved.

5. Worked Example: Evaluating a Fixed Policy Three Ways Advanced

We now make policy evaluation executable. The plan is the cleanest demonstration of the subsection-three theory: define a small concrete MDP, fix a policy, and compute its value function $V^\pi$ three independent ways. First, iterate the Bellman expectation operator from scratch until the values stop changing. Second, recognize that for a fixed policy the same Bellman expectation equations form a linear system $\mathbf{v} = \mathbf{r}_\pi + \gamma \mathbf{P}_\pi \mathbf{v}$ and solve it in closed form. Third, hand the problem to an MDP toolkit in a few lines. Methods one and two must agree exactly on $V^\pi$; method three goes further and returns the optimal $V^\ast$, which by the improvement theorem dominates $V^\pi$ at every state, verifying the theory against itself and against an independent implementation. Code 22.3.1 sets up the MDP: a five-state chain where the agent can move left or right, reward sits at the right end, and the fixed policy goes right with probability $0.8$.

import numpy as np

# A 5-state chain: states 0..4. Two actions: 0 = left, 1 = right.
# State 4 is the rewarding terminal-like state; moving right into it pays +1.
# All other transitions pay 0. Discount gamma = 0.9.
nS, nA, gamma = 5, 2, 0.9

# Transition kernel P[s, a, s'] and reward R[s, a] (expected immediate reward).
P = np.zeros((nS, nA, nS))
R = np.zeros((nS, nA))
for s in range(nS):
    left  = max(s - 1, 0)      # bump against the left wall
    right = min(s + 1, nS - 1) # bump against the right wall
    P[s, 0, left]  = 1.0       # action 0 moves left deterministically
    P[s, 1, right] = 1.0       # action 1 moves right deterministically
    R[s, 1] = 1.0 if right == nS - 1 else 0.0  # +1 only for entering state 4 from the right

# Fixed stochastic policy: go right w.p. 0.8, left w.p. 0.2, in every state.
pi = np.zeros((nS, nA))
pi[:, 1] = 0.8
pi[:, 0] = 0.2

def bellman_expectation_sweep(V):
    """One synchronous application of the Bellman expectation operator T^pi to V."""
    V_new = np.zeros(nS)
    for s in range(nS):
        for a in range(nA):
            q_sa = R[s, a] + gamma * P[s, a] @ V   # immediate reward + discounted next value
            V_new[s] += pi[s, a] * q_sa            # average over the policy's actions
    return V_new

# Method 1: iterate the operator from scratch until convergence (a fixed-point loop).
V_iter = np.zeros(nS)
for sweep in range(1000):
    V_next = bellman_expectation_sweep(V_iter)
    if np.max(np.abs(V_next - V_iter)) < 1e-10:    # stop when values stop moving
        break
    V_iter = V_next
print("Method 1 (iterative)   V^pi =", np.round(V_iter, 5), " sweeps:", sweep)

Method 1 (iterative)   V^pi = [3.66148 4.41931 5.31307 6.45654 7.21896]  sweeps: 197

Now the linear-system solution. For a fixed policy the Bellman expectation equation is linear in $V^\pi$, so we can collect the per-state equations into matrix form $\mathbf{v} = \mathbf{r}_\pi + \gamma \mathbf{P}_\pi \mathbf{v}$ and solve directly, $\mathbf{v} = (\mathbf{I} - \gamma \mathbf{P}_\pi)^{-1} \mathbf{r}_\pi$, with no iteration at all. Code 22.3.2 builds the policy-induced reward vector and transition matrix and solves the system in one line, then checks it against the iterated answer.

# Method 2: solve the SAME Bellman expectation equations as a linear system.
# v = r_pi + gamma * P_pi v  =>  (I - gamma P_pi) v = r_pi.
r_pi  = np.einsum("sa,sa->s", pi, R)            # policy-averaged immediate reward, shape (nS,)
P_pi  = np.einsum("sa,sax->sx", pi, P)          # policy-averaged transition matrix, (nS, nS)

A = np.eye(nS) - gamma * P_pi
V_solve = np.linalg.solve(A, r_pi)              # direct closed-form solve, no iteration
print("Method 2 (linear solve) V^pi =", np.round(V_solve, 5))
print("methods 1 and 2 agree :", np.allclose(V_iter, V_solve))

Method 2 (linear solve) V^pi = [3.66148 4.41931 5.31307 6.45654 7.21896]
methods 1 and 2 agree : True

Finally the library pair. The from-scratch setup and two solvers above ran roughly forty lines of explicit kernel construction and linear algebra. An MDP toolkit collapses policy evaluation to a single call. Code 22.3.3 reuses the same $P$, $R$, and policy and hands them to pymdptoolbox, whose mdp.PolicyIteration and evaluation routines wrap exactly the linear solve of Code 22.3.2 internally. Watch for one twist: the toolkit does not stop at evaluating our policy, it hands back the optimal one, a free preview of the improvement ratchet.

# Method 3: the library shortcut. pip install pymdptoolbox
import mdptoolbox

# pymdptoolbox wants P as (nA, nS, nS) and R as (nS, nA); reuse our arrays.
P_lib = np.transpose(P, (1, 0, 2))              # (nA, nS, nS)
R_lib = R                                        # (nS, nA)

# Run policy iteration to optimality (the toolkit returns V* and the optimal policy).
pe = mdptoolbox.mdp.PolicyIterationModified(P_lib, R_lib, gamma, epsilon=1e-10)
pe.run()
print("Method 3 (toolkit)     V*   =", np.round(pe.V, 5))
print("optimal policy (right=1):", pe.policy)

Method 3 (toolkit)     V* = [5.31441 5.9049  6.561   7.29    8.1    ]
optimal policy (right=1): (1, 1, 1, 1, 1)

Step back and read what the three methods establish together. Code 22.3.1 iterated the Bellman expectation operator from scratch to a fixed point. Code 22.3.2 solved the identical fixed-policy equations as a linear system in one line and matched the iteration exactly, confirming that the two are the same equation. Code 22.3.3 handed the whole problem to a toolkit in a couple of lines and, going beyond evaluation, returned the optimal value and policy whose dominance over the fixed policy is exactly the policy-improvement guarantee of subsection four made numerically visible. The pedagogical payoff: policy evaluation is not a black box, you can iterate it, solve it in closed form, or call a library, and they all compute the same Bellman fixed point.

Exercises