---
title: Value Functions and Optimality
module: Foundations
moduleNumber: 1
lessonNumber: 6
order: 106
summary: >
  A value function scores how good a state (or state–action pair) is under a
  policy: the expected return from there onward. Its defining property is the
  Bellman equation, a self-consistency condition linking a state's value to its
  successors' values, which we derive from the return and the dynamics. Pushing
  the same idea to the best-achievable value gives the Bellman optimality
  equations, whose solution yields an optimal policy — and whose intractability
  is what the rest of the course is about.
topics: [Foundations]
sources:
  - book: Sutton & Barto
    ref: "Ch. 3 — Finite Markov Decision Processes; §3.5 Policies and Value Functions"
  - book: Sutton & Barto
    ref: "§3.6 Optimal Policies and Optimal Value Functions; §3.7 Optimality and Approximation; §3.8 Summary"
---

A [Markov decision process](/reinforcement-learning/foundations/markov-decision-processes)
gives us the machinery of interaction — states, actions, rewards, the dynamics
$p(s',r \mid s,a)$ — and the [return](/reinforcement-learning/foundations/markov-decision-processes)
$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.[^sb-vf]

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:

$$
v_\pi(s) \;\doteq\; \mathbb{E}_\pi\!\left[\,G_t \mid S_t = s\,\right]
\;=\; \mathbb{E}_\pi\!\left[\,\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \;\middle|\; S_t = s\,\right],
\qquad \text{for all } s \in \mathcal{S}.
$$

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.

$$
q_\pi(s,a) \;\doteq\; \mathbb{E}_\pi\!\left[\,G_t \mid S_t = s,\, A_t = a\,\right]
\;=\; \mathbb{E}_\pi\!\left[\,\sum_{k=0}^{\infty} \gamma^k R_{t+k+1} \;\middle|\; S_t = s,\, A_t = a\,\right].
$$

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,

$$
v_\pi(s) = \sum_{a} \pi(a \mid s)\, q_\pi(s,a),
\qquad
q_\pi(s,a) = \mathbb{E}\!\left[\,R_{t+1} + \gamma\, v_\pi(S_{t+1}) \mid S_t = s,\, A_t = a\,\right],
$$

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.

> **Definition (Value functions).** For a policy $\pi$, the state-value
> $v_\pi(s)$ is the expected return from state $s$ under $\pi$, and the
> action-value $q_\pi(s,a)$ is the expected return from $s$ after first taking
> action $a$ and then following $\pi$. Both measure "how good" as expected
> long-run reward.

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](/reinforcement-learning/tabular-methods/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.

$$
\begin{aligned}
v_\pi(s)
&\doteq \mathbb{E}_\pi\!\left[\,G_t \mid S_t = s\,\right] \\
&= \mathbb{E}_\pi\!\left[\,R_{t+1} + \gamma\, G_{t+1} \mid S_t = s\,\right]
   && \text{(the return unrolls one step)} \\
&= \sum_{a} \pi(a \mid s) \sum_{s'} \sum_{r} p(s', r \mid s, a)
   \Big[\, r + \gamma\, \mathbb{E}_\pi[\,G_{t+1} \mid S_{t+1} = s'\,] \,\Big] \\
&= \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)
   \Big[\, r + \gamma\, v_\pi(s') \,\Big],
   \qquad \text{for all } s \in \mathcal{S}.
\end{aligned}
$$

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', r)$ with probability
$p(s', 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'$ — and the sums weight each possibility by how likely it is. The last line
merges the two inner sums (over $s'$ 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']$ _is_ $v_\pi(s')$ — the same function
we started with, evaluated at the successor. That coincidence is what makes the
equation a recursion rather than a definition.

> **Definition (Bellman equation for $v_\pi$).** For every state $s$,
> $$
> v_\pi(s) = \sum_{a} \pi(a \mid s) \sum_{s', r} p(s', r \mid s, a)\big[\, r + \gamma\, v_\pi(s') \,\big].
> $$
> The value of a state equals the expected immediate reward plus the discounted
> expected value of the next state, the expectation taken over the policy's
> actions and the environment's dynamics.

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.

$$
% caption: Backup diagram for $v_\pi$. From the root state $s$ the agent's
% policy $\pi$ selects one of several actions (solid dots); the environment's
% dynamics $p$ then respond with a next state $s'$ and reward $r$. The Bellman
% equation averages $r + \gamma\, v_\pi(s')$ over both branchings, weighting each
% path by $\pi(a\mid s)\,p(s',r\mid s,a)$ — value flows *back* up the tree.
\begin{tikzpicture}[>=stealth, font=\small,
  st/.style={circle, draw, fill=white, minimum size=5mm, inner sep=0pt},
  ac/.style={circle, draw, fill=black, minimum size=2.4mm, inner sep=0pt},
  lf/.style={circle, draw, fill=white, minimum size=4mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % root state
  \node[st, label={[text=acc]above:$s$}] (s) at (0,3) {};
  % action layer
  \node[ac] (a1) at (-2.2,1.7) {};
  \node[ac] (a2) at (0,1.7) {};
  \node[ac] (a3) at (2.2,1.7) {};
  \draw[acc, thick] (s) -- (a1);
  \draw[acc, thick] (s) -- (a2);
  \draw[acc, thick] (s) -- (a3);
  \node[acc, anchor=south west, font=\footnotesize] at (0.05,2.15) {policy};
  % successor states
  \node[lf] (l1) at (-2.8,0.2) {};
  \node[lf] (l2) at (-1.6,0.2) {};
  \node[lf] (l3) at (-0.6,0.2) {};
  \node[lf] (l4) at (0.6,0.2) {};
  \node[lf] (l5) at (1.6,0.2) {};
  \node[lf] (l6) at (2.8,0.2) {};
  \draw[black] (a1) -- (l1);
  \draw[black] (a1) -- (l2);
  \draw[black] (a2) -- (l3);
  \draw[black] (a2) -- (l4);
  \draw[black] (a3) -- (l5);
  \draw[black] (a3) -- (l6);
  \node[anchor=west, font=\footnotesize] at (2.95,0.2) {next state};
\end{tikzpicture}
$$

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'$. 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', r)$; from each successor $s'$ the policy then branches on
the next action $a'$, and $q_\pi$ satisfies

$$
q_\pi(s,a) = \sum_{s', r} p(s', r \mid s, a)\Big[\, r + \gamma \sum_{a'} \pi(a' \mid s')\, q_\pi(s', a') \,\Big].
$$

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$.

$$
% caption: A three-state MDP. From $S_1$ the equiprobable policy flips between
% action $a$ (to $S_2$, reward $+4$) and action $b$ (to $S_3$, reward $0$); $S_2$
% and $S_3$ each loop back to $S_1$, with $S_3$ paying $+2$ on the way. Solving the
% three Bellman equations gives the state values.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  st/.style={circle, draw, minimum size=11mm}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[st] (s1) at (0,0) {S1};
  \node[st] (s2) at (4.4,1.5) {S2};
  \node[st] (s3) at (4.4,-1.5) {S3};
  \draw[->, acc, thick] (s1) to[bend left=15] node[midway, above, sloped] {a: r=4} (s2);
  \draw[->, acc, thick] (s1) to[bend right=15] node[midway, below, sloped] {b: r=0} (s3);
  \draw[->, black] (s2) to[bend left=15] node[midway, above, sloped] {r=0} (s1);
  \draw[->, red] (s3) to[bend right=15] node[midway, below, sloped] {r=2} (s1);
\end{tikzpicture}
$$

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

$$
\begin{aligned}
v_\pi(S_1) &= \tfrac12\big[4 + 0.9\,v_\pi(S_2)\big] + \tfrac12\big[0 + 0.9\,v_\pi(S_3)\big], \\
v_\pi(S_2) &= 0 + 0.9\,v_\pi(S_1), \\
v_\pi(S_3) &= 2 + 0.9\,v_\pi(S_1).
\end{aligned}
$$

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

$$
v_\pi(S_1) = 2 + 0.45(0.9\,v_\pi(S_1)) + 0.45(2 + 0.9\,v_\pi(S_1))
  = 2.9 + 0.81\,v_\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) = \tfrac12[4 + 0.9(13.74)] +
\tfrac12[0.9(15.74)] = \tfrac12(16.37) + \tfrac12(14.16) = 15.26$.

That last line also exposes the action-values hidden in the average:
$q_\pi(S_1, a) = 4 + 0.9\,v_\pi(S_2) = 16.37$ and $q_\pi(S_1, b) = 0.9\,v_\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.

$$
% caption: The three-state MDP under the random policy versus the optimal policy.
% At $S_1$ the random policy's value $15.26$ is the average of the two action
% values ($16.37$ and $14.16$); the optimal policy takes only the better action,
% and every state's value rises ($v_*(S_1)=21.05$). Optimality removes the
% averaging over the worse action.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \definecolor{grn}{HTML}{1F9D4D}
  \draw[->, black] (0,0) -- (0,4.0) node[above] {value at S1};
  \draw[black] (-0.2,0) -- (5.6,0);
  \node[anchor=east, font=\scriptsize] at (-0.25,0) {0};
  \node[anchor=east, font=\scriptsize] at (-0.25,3.2) {21};
  % scale: 21.05 -> 3.2 => factor 0.152
  % q(S1,a)=16.37 -> 2.489 ; q(S1,b)=14.16 -> 2.153 ; v_pi=15.26 -> 2.320 ; v*=21.05->3.2
  \fill[black, draw=black] (0.5,0) rectangle (1.3,2.489);
  \node[anchor=north, font=\scriptsize] at (0.9,-0.05) {q(a)};
  \node[anchor=south, font=\scriptsize] at (0.9,2.489) {16.4};
  \fill[black, draw=black] (1.5,0) rectangle (2.3,2.153);
  \node[anchor=north, font=\scriptsize] at (1.9,-0.05) {q(b)};
  \node[anchor=south, font=\scriptsize] at (1.9,2.153) {14.2};
  \draw[grn, very thick] (2.9,0) rectangle (3.7,2.320);
  \node[anchor=north, font=\scriptsize] at (3.3,-0.05) {v-pi};
  \node[grn, anchor=south, font=\scriptsize] at (3.3,2.320) {15.3};
  \draw[acc, very thick] (4.3,0) rectangle (5.1,3.2);
  \node[anchor=north, font=\scriptsize] at (4.7,-0.05) {v-star};
  \node[acc, anchor=south, font=\scriptsize] at (4.7,3.2) {21.1};
  \node[grn, anchor=west, font=\scriptsize] at (0.5,3.7) {v-pi = average of q(a),q(b); v-star takes the max and beyond};
\end{tikzpicture}
$$

## 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'$; from the special cell $B$, every action
pays $+5$ and teleports it to $B'$.[^sb-grid]

Now fix the policy to be uniformly random — each of the four actions with
probability $\tfrac{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.

$$
% caption: Gridworld state values $v_\pi$ under the equiprobable random policy,
% $\gamma = 0.9$. Cell $A$ is worth less than its $+10$ immediate reward because
% it lands the agent in $A'$ near the edge; $B$ is worth more than $+5$ because
% $B'$ sits in safer territory. Negative values crowd the border, where the
% random policy often walks into a wall for reward $-1$.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % grid
  \foreach \x in {0,...,5} \draw[black] (\x,0) -- (\x,5);
  \foreach \y in {0,...,5} \draw[black] (0,\y) -- (5,\y);
  % row 5 (top): 3.3 8.8 4.4 5.3 1.5
  \foreach \x/\v in {0/3.3, 1/8.8, 2/4.4, 3/5.3, 4/1.5}
    \node at (\x+0.5,4.5) {\v};
  % row 4: 1.5 3.0 2.3 1.9 0.5
  \foreach \x/\v in {0/1.5, 1/3.0, 2/2.3, 3/1.9, 4/0.5}
    \node at (\x+0.5,3.5) {\v};
  % row 3: 0.1 0.7 0.7 0.4 -0.4
  \foreach \x/\v in {0/0.1, 1/0.7, 2/0.7, 3/0.4, 4/-0.4}
    \node at (\x+0.5,2.5) {\v};
  % row 2: -1.0 -0.4 -0.4 -0.6 -1.2
  \foreach \x/\v in {0/-1.0, 1/-0.4, 2/-0.4, 3/-0.6, 4/-1.2}
    \node at (\x+0.5,1.5) {\v};
  % row 1 (bottom): -1.9 -1.3 -1.2 -1.4 -2.0
  \foreach \x/\v in {0/-1.9, 1/-1.3, 2/-1.2, 3/-1.4, 4/-2.0}
    \node at (\x+0.5,0.5) {\v};
  % mark special cells A (col 1,row5) B (col 3,row5) A' (col1,row1) B' (col3,row3)
  \node[acc, font=\footnotesize\bfseries, anchor=north west] at (1.02,5.0) {A};
  \node[acc, font=\footnotesize\bfseries, anchor=north west] at (3.02,5.0) {B};
  \node[red, font=\footnotesize\bfseries, anchor=south west] at (1.02,0.02) {A'};
  \node[red, font=\footnotesize\bfseries, anchor=south west] at (3.02,2.02) {B'};
\end{tikzpicture}
$$

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'$ 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'$, 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'$ iff
$v_\pi(s) \ge v_{\pi'}(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$:

$$
v_\ast(s) \;\doteq\; \max_{\pi}\, v_\pi(s), \qquad \text{for all } s \in \mathcal{S}.
$$

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

$$
q_\ast(s,a) \;\doteq\; \max_{\pi}\, q_\pi(s,a), \qquad \text{for all } s \in \mathcal{S},\; a \in \mathcal{A}(s).
$$

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$:

$$
q_\ast(s,a) = \mathbb{E}\!\left[\,R_{t+1} + \gamma\, v_\ast(S_{t+1}) \mid S_t = s,\, A_t = a\,\right].
$$

$$
% caption: Optimal values under a random policy have negative regions; under
% $v_*$ every state's value rises to the best achievable. Because $v_*(s) =
% \max_a q_*(s,a)$, the optimal state value is the height of the best action
% available at that state — the tallest bar, not the average bar.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  % baseline
  \draw[black] (-0.3,0) -- (5.6,0);
  \node[anchor=east, font=\scriptsize] at (-0.35,0) {0};
  % four action-value bars for one state
  \foreach \x/\h/\lab in {0.4/1.1/a1, 1.7/2.6/a2, 3.0/1.7/a3, 4.3/0.9/a4} {
    \draw[black, fill=black!8] (\x,0) rectangle (\x+0.8,\h);
    \node[anchor=north, font=\scriptsize] at (\x+0.4,-0.08) {\lab};
  }
  % highlight the max bar (a2)
  \draw[acc, very thick] (1.7,0) rectangle (2.5,2.6);
  \node[acc, anchor=south, font=\scriptsize] at (2.1,2.62) {best};
  % v_* line at max height
  \draw[acc, dashed, thick] (0.2,2.6) -- (5.2,2.6);
  \node[acc, anchor=west, font=\scriptsize] at (5.25,2.6) {value v(s)};
  \node[anchor=north, font=\scriptsize] at (2.6,-0.55) {action values q(s,a) at a f\/ixed state};
\end{tikzpicture}
$$

## 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:

$$
\begin{aligned}
v_\ast(s)
&= \max_{a \in \mathcal{A}(s)} q_{\pi_\ast}(s,a) \\
&= \max_a \mathbb{E}\!\left[\,R_{t+1} + \gamma\, v_\ast(S_{t+1}) \mid S_t = s,\, A_t = a\,\right] \\
&= \max_a \sum_{s', r} p(s', r \mid s, a)\big[\, r + \gamma\, v_\ast(s') \,\big].
\end{aligned}
$$

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

$$
q_\ast(s,a) = \sum_{s', r} p(s', r \mid s, a)\Big[\, r + \gamma \max_{a'} q_\ast(s', a') \,\Big],
$$

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

> **Definition (Bellman optimality equations).** The optimal value functions are
> the unique solutions of
> $$
> v_\ast(s) = \max_a \sum_{s', r} p(s', r \mid s, a)\big[\, r + \gamma\, v_\ast(s') \,\big],
> \qquad
> q_\ast(s,a) = \sum_{s', r} p(s', r \mid s, a)\Big[\, r + \gamma \max_{a'} q_\ast(s', a') \,\Big].
> $$
> Each is a system of nonlinear equations — one per state, or per state–action
> pair — coupled through the $\max$.

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.

$$
% caption: Backup diagrams for the Bellman optimality equations. Left ($v_*$):
% at the root state the agent takes the *max* over actions (the arc across the
% action branches), then the environment averages over $(s',r)$. Right ($q_*$):
% the environment responds first, then at each successor state the agent again
% takes the max over next actions $a'$.
\begin{tikzpicture}[>=stealth, font=\small,
  st/.style={circle, draw, fill=white, minimum size=5mm, inner sep=0pt},
  ac/.style={circle, draw, fill=black, minimum size=2.4mm, inner sep=0pt},
  lf/.style={circle, draw, fill=white, minimum size=4mm, inner sep=0pt}]
  \definecolor{acc}{HTML}{2348F2}
  % ============ LEFT: v_* ============
  \begin{scope}
    \node[st, label={[text=acc]above:s}] (s) at (0,3) {};
    \node[ac] (a1) at (-1.5,1.7) {};
    \node[ac] (a2) at (0,1.7) {};
    \node[ac] (a3) at (1.5,1.7) {};
    \draw[acc, thick] (s) -- (a1);
    \draw[acc, thick] (s) -- (a2);
    \draw[acc, thick] (s) -- (a3);
    % max arc across the action branches, high near the root so it clears the dots
    \draw[red, thick] (-0.72,2.5) arc[start angle=218, end angle=322, radius=0.92];
    \node[red, anchor=east, font=\footnotesize] at (-0.82,2.5) {max};
    \node[lf] (l1) at (-1.9,0.3) {};
    \node[lf] (l2) at (-1.1,0.3) {};
    \node[lf] (l3) at (-0.4,0.3) {};
    \node[lf] (l4) at (0.4,0.3) {};
    \node[lf] (l5) at (1.1,0.3) {};
    \node[lf] (l6) at (1.9,0.3) {};
    \draw[black] (a1) -- (l1); \draw[black] (a1) -- (l2);
    \draw[black] (a2) -- (l3); \draw[black] (a2) -- (l4);
    \draw[black] (a3) -- (l5); \draw[black] (a3) -- (l6);
    \node[anchor=north, font=\footnotesize] at (0,-0.25) {(v-star)};
  \end{scope}
  % ============ RIGHT: q_* ============
  \begin{scope}[xshift=6.2cm]
    \node[ac, label={[text=acc]above:(s a)}] (sa) at (0,3) {};
    \node[st] (r1) at (-1.1,1.7) {};
    \node[st] (r2) at (1.1,1.7) {};
    \draw[acc, thick] (sa) -- (r1);
    \draw[acc, thick] (sa) -- (r2);
    \node[acc, anchor=west, font=\footnotesize] at (0.15,2.4) {r};
    % next actions under each successor with a max arc
    \node[ac] (b1) at (-1.7,0.3) {};
    \node[ac] (b2) at (-0.5,0.3) {};
    \node[ac] (b3) at (0.5,0.3) {};
    \node[ac] (b4) at (1.7,0.3) {};
    \draw[black] (r1) -- (b1); \draw[black] (r1) -- (b2);
    \draw[black] (r2) -- (b3); \draw[black] (r2) -- (b4);
    \draw[red, thick] (-1.95,0.75) arc[start angle=210, end angle=330, radius=0.83];
    \draw[red, thick] (0.25,0.75) arc[start angle=210, end angle=330, radius=0.83];
    \node[red, anchor=north, font=\footnotesize] at (-1.1,0.72) {max};
    \node[red, anchor=north, font=\footnotesize] at (1.1,0.72) {max};
    \node[anchor=north, font=\footnotesize] at (0,-0.25) {(q-star)};
  \end{scope}
\end{tikzpicture}
$$

## 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.

> **Theorem (Greedy in $v_\ast$ is optimal).** Any policy that, in each state,
> selects only actions achieving $\max_a \sum_{s',r} p(s',r\mid s,a)[r + \gamma
> v_*(s')]$ is an optimal policy. A one-step-ahead search on $v_*$ yields
> globally optimal actions.

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](/reinforcement-learning/tabular-methods/temporal-difference-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:[^sb-approx]

1. **The dynamics are known.** Explicitly solving needs $p(s',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.

$$
% caption: The three assumptions that direct solution of the Bellman optimality
% equation requires — a known model, enough computation, and the Markov property
% — are jointly seldom met, which is why reinforcement learning turns to methods
% that only *approximate* the optimality equation from sampled experience.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=30mm, minimum height=10mm, align=center, font=\footnotesize}]
  \definecolor{acc}{HTML}{2348F2}
  \node[box] (model) at (0,1.6)  {known model\\dynamics p};
  \node[box] (comp)  at (0,0)    {enough\\computation};
  \node[box] (markov)at (0,-1.6) {the Markov\\property};
  \node[box, draw=acc, text=acc, thick] (solve) at (5.6,0) {solve the\\Bellman equations};
  \draw[->, acc, thick] (model)  -- (solve);
  \draw[->, acc, thick] (comp)   -- (solve);
  \draw[->, acc, thick] (markov) -- (solve);
\end{tikzpicture}
$$

## 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.

> **Definition (Tabular vs. approximate).** When a value function has one stored
> entry per state, the setting is _tabular_ and the value function is
> represented exactly. When states outnumber any feasible table, the function
> must be replaced by a parameterized approximation with far fewer parameters
> than states.

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](/reinforcement-learning/tabular-methods/dynamic-programming)
sweeps a known model and turns the optimality equations directly into update
rules; [Monte Carlo](/reinforcement-learning/tabular-methods/monte-carlo-methods)
and [temporal-difference learning](/reinforcement-learning/tabular-methods/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'}Q(S_{t+1}, a')$ from sampled
transitions, and converges to $q_\ast$ without a model.[^qlearning] 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.[^dqn] The two tricks that made the network stable — a slowly
updated _target network_ supplying the $\max_{a'}Q(s',a')$ 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.

$$
% caption: Deep Q-learning is the Bellman optimality equation for $q_*$ turned
% into a sampled, network-based update. A network estimates $Q(s,a)$; the training
% target is $r + \gamma \max_{a'} Q(s', a')$ from a target copy of the network, and
% the difference between them is minimized. It is the same equation as $q_*(s,a) =
% \sum p [r + \gamma \max_{a'} q_*(s',a')]$, sampled instead of summed.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=26mm, minimum height=11mm, align=center}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{red}{HTML}{C0392B}
  \node[box, draw=acc, text=acc] (q) at (0,0) {network Q(s,a)};
  \node[box] (tgt) at (6.2,1.3) {target: r + g max Q(s-next, a-next)};
  \node[box, draw=red, text=red] (loss) at (6.2,-1.3) {minimize di\/f\/ference};
  \draw[->, acc, thick] (q.east) to[bend left=12] (tgt.west);
  \draw[->, thick] (tgt.south) -- (loss.north) node[midway, right, font=\scriptsize] {compare};
  \draw[->, red, thick] (loss.west) to[bend left=20] node[midway, below, font=\scriptsize, text=black] {gradient step} (q.south);
\end{tikzpicture}
$$

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.[^tdgammon] 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.[^alphago] 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.

> **Definition (Value-based deep RL).** Methods that represent $v_\ast$ or $q_\ast$ by a
> parameterized function (typically a neural network) and fit it to the Bellman
> optimality target from sampled experience. Q-learning with a network (DQN) and
> TD-trained value networks (TD-Gammon, AlphaZero) are the canonical instances;
> all are approximate solvers of the equations derived in this lesson.

[^sb-vf]: **Sutton & Barto**, _Reinforcement Learning: An Introduction_ (2nd ed.), §3.5 — Policies and Value Functions: the state-value $v_\pi$ (3.12) and action-value $q_\pi$ (3.13) as expected returns under a policy, and the Bellman equation (3.14) as the recursive consistency condition they satisfy.
[^sb-grid]: **Sutton & Barto**, §3.5, Example 3.5 (Gridworld): the $5\times5$ grid with special cells $A,B$, the equiprobable random policy at $\gamma = 0.9$, and its state-value function computed by solving the linear system (3.14).
[^sb-approx]: **Sutton & Barto**, §3.6–§3.7 — Optimal Value Functions; Optimality and Approximation: the Bellman optimality equations (3.19)–(3.20), greedy policies with respect to $v_\ast$ and $q_\ast$, the three assumptions that make direct solution infeasible, and the tabular-versus-approximate distinction.
[^qlearning]: **Watkins, C. J. C. H. (1989)**, _Learning from Delayed Rewards_, PhD thesis, University of Cambridge; and **Watkins, C. J. C. H. & Dayan, P. (1992)**, "Q-learning", _Machine Learning_ 8, 279–292 — the Q-learning update toward the Bellman-optimality target $R_{t+1} + \gamma\max_{a'}Q(S_{t+1},a')$ and its proof of convergence to $q_\ast$ in the tabular case.
[^dqn]: **Mnih, V. et al. (2015)**, "Human-level control through deep reinforcement learning", _Nature_ 518, 529–533 — the Deep Q-Network, reaching human-level play on 49 Atari 2600 games from raw pixels, stabilized by experience replay and a periodically-updated target network.
[^tdgammon]: **Tesauro, G. (1994)**, "TD-Gammon, a self-teaching backgammon program, achieves master-level play", _Neural Computation_ 6(2), 215–219 — a neural value function trained by TD learning through self-play to near-championship backgammon, the early proof that approximate value functions scale.
[^alphago]: **Silver, D. et al. (2016)**, "Mastering the game of Go with deep neural networks and tree search", _Nature_ 529, 484–489; and **Silver, D. et al. (2018)**, "A general reinforcement learning algorithm that masters chess, shogi, and Go through self-play", _Science_ 362(6419), 1140–1144 (AlphaZero) — learned value (and policy) networks combined with Monte-Carlo tree search, defeating top human Go players and superseding hand-crafted engines in chess and shogi.