Value Functions and Optimality

A Markov decision process gives us the machinery of interaction — states, actions, rewards, the dynamics $p(s^{\prime },r\mid s,a)$ — and the return$G_t=R_{t+1}+\gamma R_{t+2}+{\gamma }^2{R}_{t+3}+\cdots$ that an agent tries to maximize. What it does not yet give us is a way to act. To choose well an agent needs to know, before it moves, how good its situation is; and how good can only mean one thing here — how much return it can expect from here on. That number, attached to every state, is a value function, and almost every reinforcement-learning algorithm is a scheme for estimating one.¹

Value is always relative to a way of behaving. A policy $\pi$ is a mapping from states to probabilities over actions: $\pi (a\mid s)$ is the probability of taking action $a$ when in state $s$. (The bar is ordinary conditioning notation; $\pi (\cdot \mid s)$ is a distribution over $\mathcal{A}(s)$ for each $s$.) A different policy makes different states good. So a value function is defined with respect to a policy, and a change of policy changes the values.

Two value functions

The state-value function for policy $\pi$, written $v_{\pi }(s)$, is the expected return when the agent starts in $s$ and follows $\pi$ thereafter:

Here ${\mathbb{E}}_{\pi }[\cdot ]$ is the expected value of a random variable given that the agent follows $\pi$, and $t$ is any time step (the definition does not depend on which one, because the process is stationary). The value of a terminal state, if there is one, is always zero.

Alongside it we define the action-value function for $\pi$, written $q_{\pi }(s,a)$: the expected return from starting in $s$, taking action $a$ now, and following $\pi$ afterward.

The difference is one committed first action. $v_{\pi }$ averages over the action $\pi$ would choose; $q_{\pi }$ pins the first action to $a$ and only then defers to $\pi$. The two are tied together by that averaging in both directions,

In words: a state's value is the policy-weighted average of its action-values, and an action's value is the immediate reward plus the discounted value of the state it leads to. These two relations lead directly to the Bellman equation.

These functions are not given; they are estimated. If an agent follows $\pi$ and, for each state it meets, averages the actual returns that followed, those averages converge to $v_{\pi }(s)$ as the state is visited more and more often — the idea behind Monte Carlo methods. Keep separate averages per action and they converge to $q_{\pi }(s,a)$. But raw averaging ignores a structural fact about these functions that makes them far cheaper to compute: they are recursive.

The Bellman equation

The intuition: a state's value equals the expected reward on the next step plus the discounted value of the next state. The derivation below carries that idea through the expectation carefully.

The returns at successive time steps are related — $G_t=R_{t+1}+\gamma G_{t+1}$ — and that single algebraic fact propagates all the way up into the value function, turning a definition into a recursion. Take the definition of $v_{\pi }$ and unfold it.

Read the middle line as an explicit expectation over three random variables. To be in $s$ and act under $\pi$ is to draw an action $a$ with probability $\pi (a\mid s)$, then draw a next-state–reward pair $(s^{\prime },r)$ with probability $p(s^{\prime },r\mid s,a)$. For each such triple the quantity in brackets is what you collect — the immediate reward $r$ plus the discounted value of the successor $s^{\prime }$ — and the sums weight each possibility by how likely it is. The last line merges the two inner sums (over $s^{\prime }$ and over $r$) into one sum over all pairs, a compaction we will use constantly. The inner expectation ${\mathbb{E}}_{\pi }[G_{t+1}\mid S_{t+1}=s^{\prime }]$ is $v_{\pi }(s^{\prime })$ — the same function we started with, evaluated at the successor. That coincidence is what makes the equation a recursion rather than a definition.

The equation is a consistency condition: it says the value assigned to $s$ and the values assigned to $s$'s possible successors cannot be set independently — looking one step ahead and averaging must reproduce the value we started with.

A picture like this is a backup diagram. Each open circle is a state, each solid dot a state–action pair. Starting from the root $s$ at the top, the branches to the solid dots are the actions the policy might select; from each dot the branches to the next open circles are the responses the environment might make, each labelled by its reward $r$ and successor $s^{\prime }$. The name is literal: these diagrams show value information being backed up, transferred back to a state (or state–action pair) from its successors. The Bellman equation averages over one full level of this tree, nothing more. Note that, unlike a transition graph, the nodes need not be distinct states — a state can be its own successor.

The action-value function has its own backup and its own Bellman equation, rooted at a state–action pair instead of a state. From $(s,a)$ the environment first branches on $(s^{\prime },r)$; from each successor $s^{\prime }$ the policy then branches on the next action $a^{\prime }$, and $q_{\pi }$ satisfies

The two Bellman equations are the same self-consistency read from two roots. Their central property, proved in later chapters, is uniqueness: for a finite MDP the equation for $v_{\pi }$ has exactly one solution, so the consistency condition alone determines the value function.

Solving the Bellman equations on a 3-state MDP

The Bellman equation is a linear system in the unknowns $v_{\pi }(s)$, so for a small MDP we can solve it by hand and watch the values fall out. Take three states $S_1,S_2,S_3$ and $\gamma =0.9$. In $S_1$ the policy is a coin flip between two actions: action $a$ moves to $S_2$ for reward $+4$, action $b$ moves to $S_3$ for reward $0$. States $S_2$ and $S_3$ each have a single action: $S_2$ returns to $S_1$ for reward $0$, and $S_3$ returns to $S_1$ for reward $+2$.

Write out the Bellman equation $v_{\pi }(s)={\sum }_a\pi (a\mid s){\sum }_{s^{\prime },r}p(s^{\prime },r\mid s,a)[r+\gamma v_{\pi }(s^{\prime })]$ for each state. The transitions are deterministic, so the inner sum collapses to one term per action:

Substitute the last two into the first. With $v_{\pi }(S_2)=0.9v_{\pi }(S_1)$ and $v_{\pi }(S_3)=2+0.9v_{\pi }(S_1)$,

so $v_{\pi }(S_1)(1-0.81)=2.9$ and $v_{\pi }(S_1)=2.9/0.19=15.26$. Back-substitute: $v_{\pi }(S_2)=0.9(15.26)=13.74$ and $v_{\pi }(S_3)=2+13.74=15.74$. Every equation now checks — for instance $v_{\pi }(S_1)=\frac{1}{2}[4+0.9(13.74)]+\frac{1}{2}[0.9(15.74)]=\frac{1}{2}(16.37)+\frac{1}{2}(14.16)=15.26$.

That last line also exposes the action-values hidden in the average: $q_{\pi }(S_1,a)=4+0.9v_{\pi }(S_2)=16.37$ and $q_{\pi }(S_1,b)=0.9v_{\pi }(S_3)=14.16$. The state value $15.26$ is exactly their equiprobable average, as $v_{\pi }(s)={\sum }_a\pi (a\mid s)q_{\pi }(s,a)$ requires. Action $a$ is the better of the two ($16.37>14.16$), which foreshadows the next section: an optimal policy would drop the coin flip and always take $a$. Doing so (and re-solving with a $\max$ in place of the average) gives the larger optimal values $v_{\ast }(S_1)=21.05$, $v_{\ast }(S_2)=18.95$, $v_{\ast }(S_3)=20.95$ — the payoff of never averaging in the inferior action.

Gridworld: a value function you can read

Consider a $5\times 5$ grid. In each cell the agent may go north, south, east, or west; each move is deterministic and shifts the agent one cell. An action that would leave the grid instead keeps the agent in place and pays reward $-1$. All other moves pay $0$ — with two exceptions. From the special cell $A$, every action pays $+10$ and teleports the agent to $A^{\prime }$; from the special cell $B$, every action pays $+5$ and teleports it to $B^{\prime }$.²

Now fix the policy to be uniformly random — each of the four actions with probability $\frac{1}{4}$ everywhere — and discount at $\gamma =0.9$. Solving the $25$ linear Bellman equations (one per state, $25$ unknowns) gives the value function below.

Two features carry the whole intuition. State $A$ is the best state under this policy, yet its value ($8.8$) is less than its immediate reward of $10$: taking any action sends the agent to $A^{\prime }$ in the bottom row, from which the random policy is likely to run into the edge and lose reward. State $B$, worth $5.3$, is valued above its immediate reward of $5$: it sends the agent to $B^{\prime }$, which sits in safer interior territory, so the expected penalty from future edge-collisions is more than offset by the guaranteed gain of landing in $A$ or $B$. The negative values along the border are the accumulated cost of a policy that keeps blundering into walls. Every one of these numbers satisfies the Bellman equation exactly: the center cell's value equals the average of $0+\gamma$ times its four neighbors' values.

Optimal policies and optimal value functions

Solving a reinforcement-learning task means, roughly, finding a policy that earns a lot of reward over the long run. Value functions let us make this precise. They induce a partial order on policies: $\pi \ge {\pi }^{\prime }$ iff $v_{\pi }(s)\ge v_{{\pi }^{\prime }}(s)$ for all states $s$. A policy that beats or ties every other policy in every state is an optimal policy. For a finite MDP at least one always exists (there may be several); they all share the same state-value function, the optimal state-value function $v_{\ast }$:

Optimal policies also share the same optimal action-value function $q_{\ast }$:

For a state–action pair, $q_{\ast }(s,a)$ is the expected return from taking $a$ in $s$ and thereafter following an optimal policy. So $q_{\ast }$ can be written in terms of $v_{\ast }$:

The Bellman optimality equations

The one change from before is this: an optimal agent does not average over its actions — it takes the best one. So wherever the ordinary Bellman equation averaged over the policy's action choices, the optimality equation puts a $\max$. Everything else is the same.

Because $v_{\ast }$ is the value function for a policy, it must satisfy the Bellman equation. But because it is the value function for an optimal policy, its self-consistency condition takes a special form that mentions no policy at all. Under an optimal policy the value of a state must equal the expected return of the single best action available there — not a policy-weighted average, but a maximum:

The last line is the Bellman optimality equation for $v_{\ast }$. The only change from the Bellman equation for $v_{\pi }$ is that the outer ${\sum }_a\pi (a\mid s)$ has become a ${\max }_a$: an optimal agent does not average over its actions, it takes the best one. The corresponding equation for the action-value function is

where the max now sits inside, at the successor: after the environment responds, the optimal agent again picks the best next action.

Their backup diagrams are the same trees as before, with one addition: an arc across the branches at the choice point marks that the $\max$, not an average, is taken there. In the $v_{\ast }$ diagram the arc sits at the agent's action choice; in the $q_{\ast }$ diagram it sits at the successor state's action choice.

Why the optimal value function is enough

The payoff of $v_{\ast }$ is that it collapses a hard long-term problem into an easy short-term one. Once you have $v_{\ast }$, an optimal policy falls out almost for free. For each state, there is at least one action that attains the max in the Bellman optimality equation; any policy that puts all its probability on such actions is optimal. That is, any policy greedy with respect to $v_{\ast }$ is an optimal policy.

The word greedy usually carries a warning in computer science: a greedy procedure chooses by immediate appeal and can miss a better path that requires short-term sacrifice. With $v_{\ast }$ the warning does not apply. Because $v_{\ast }$ already folds the full discounted consequences of all future behavior into a single number per state, acting greedily on it — a one-step lookahead, no deeper — is optimal in the full long-term sense. The long-run optimization has been baked into the values in advance; the runtime search is one step deep.

With $q_{\ast }$ it is easier still — no lookahead at all. For any state $s$ the agent simply picks any $a$ maximizing $q_{\ast }(s,a)$. The action-value function has cached the result of the one-step search into each state–action pair, so an optimal action can be chosen with no model of the environment: no need to know the successor states, their values, or the dynamics $p$. This is the practical appeal of learning $q$ rather than $v$, and it is the basis of Q-learning.

Why we cannot just solve it

If the Bellman optimality equation hands us an optimal policy, why is the rest of the course not a single chapter on solving it? Because for the tasks we care about, solving it directly is out of reach. The equation for $v_{\ast }$ is a system of $|\mathcal{S}|$ nonlinear equations in $|\mathcal{S}|$ unknowns; in principle, if the dynamics $p$ are known, one can solve it with any method for systems of nonlinear equations. In practice that route is rarely useful, because it leans on three assumptions that are seldom all true at once:³

1. The dynamics are known. Explicitly solving needs $p(s^{\prime },r\mid s,a)$ for every transition. An agent learning from interaction usually does not have this model; discovering it is part of the problem.
2. The computation is affordable. The solution is akin to an exhaustive lookahead over all possibilities. Backgammon has about $10^{20}$ states; even granting a perfect model, solving its Bellman equation would take a present-day computer thousands of years. Chess, Go, and any real control problem are worse.
3. The Markov property holds. The equation is exact only if the state summarizes everything relevant about the past — which real sensory streams rarely satisfy exactly.

Board games such as chess are a vanishing fraction of human experience, yet the largest custom computers still cannot compute their optimal moves. So the sharp notion of optimality is best read as a reference point — it organizes the theory and lets us reason about how good an algorithm's answers are — not as a target we expect to hit.

Optimality and approximation

Because exact optimality is out of reach, reinforcement learning settles for approximating it — and the two constraints that force the compromise are computation and memory. In small, finite tasks the value function can be stored as an array or table with one entry per state (or per state–action pair). This is the tabular case, and its methods — the subject of the next several lessons — are the tabular methods. When the state set is astronomically larger than any table, the value function itself must be approximated by a compact parameterized function, the topic of the later chapters on function approximation.

Approximation is not purely a concession; it also has a benefit: an agent that meets some states with vanishingly low probability can afford to make poor decisions there, since those states barely touch its total reward. A backgammon player of the caliber of TD-Gammon plays with great skill overall while very possibly misjudging board positions that never arise between experts. The online nature of reinforcement learning lets an agent spend its limited approximation effort on the states it actually encounters often, at the expense of the ones it rarely sees — a bias that distinguishes it from generic schemes for approximately solving MDPs.

This reframing is what the rest of the course elaborates. Many decision-making methods can be read as ways of approximately solving the Bellman optimality equation. Dynamic programming sweeps a known model and turns the optimality equations directly into update rules; Monte Carlo and temporal-difference learning drop the model and use sampled transitions in place of the expected ones. Every one of them is a different way of enforcing the self-consistency condition derived here.

Value functions in deep RL

The Bellman optimality equation is not only a theoretical reference point; its sampled, function-approximated form is what runs inside the systems that made RL famous. Two lines descend directly from the equations of this lesson.

The $q_{\ast }$ line turns pick $\arg {\max }_a{q}_{\ast }(s,a)$ into an algorithm. Watkins' Q-learning (1989) updates a tabular estimate toward the Bellman-optimality target $R_{t+1}+\gamma {\max }_{a^{\prime }}Q(S_{t+1},a^{\prime })$ from sampled transitions, and converges to $q_{\ast }$ without a model.⁴ Replace the table with a deep network $Q(s,a;\theta )$ and you get the Deep Q-Network of Mnih et al. (2015), which learned to play $49$ Atari games from raw pixels at or above human level, using a single architecture and one set of hyperparameters.⁵ The two tricks that made the network stable — a slowly updated target network supplying the ${\max }_{a^{\prime }}Q(s^{\prime },a^{\prime })$ term, and a replay buffer of past transitions — are both patches on the plain Bellman update, which diverges when the same rapidly-changing network appears on both sides of the equation. That instability has a name in the next module: the deadly triad of function approximation, bootstrapping, and off-policy learning together.

The $v_{\ast }$ line powers the model-based game players. Tesauro's TD-Gammon (1994) — named earlier in this lesson — trained a neural value function $v(s;\theta )$ by temporal-difference learning against itself and reached championship backgammon, the first demonstration that approximate value functions scale.⁶ Silver et al.'s AlphaGo (2016) and its successor AlphaZero (2018) combined a learned value network $v(s)$ with Monte-Carlo tree search, using the value estimate to prune a lookahead far shallower than the $\max$-over-everything the exact Bellman equation would demand, and defeated the world's strongest Go players.⁷ These systems are the practical answer to this lesson's closing worry: the state spaces ($\approx 10^{170}$ for Go) are far past any table, so $v_{\ast }$ is approximated by a network and the one-step greedy-in-$v_{\ast }$ ideal is replaced by a few-step search on the approximation — the online, encounter-weighted approximation this lesson argued for.