The Bellman Optimality Equation

Recall that for a fixed policy $\pi$, the State-Value and Action-Value Functions $v_\pi(s)$ and $q_\pi(s,a)$ satisfy the ordinary Bellman equations, which express today's value as an expectation over the policy's action choice and the environment's transition. The optimal state-value function is defined as the best value achievable at each state, maximizing over all policies:

Similarly, the optimal action-value function gives the best value of taking action $a$ in state $s$ and then behaving optimally thereafter:

A policy $\pi_*$ is called optimal if $v_{\pi_*}(s) = v_*(s)$ for every state $s$. A foundational fact about finite MDPs is that such a policy always exists, and moreover it can be chosen to be deterministic and stationary (its action depends only on the current state, not on time). This is not obvious a priori — one might worry that different states demand incompatible tradeoffs requiring randomization — but the structure of MDPs rules this out. The Bellman optimality equation expresses $v_*$ recursively, by noting that the best you can do from state $s$ is to pick the single best action now, then act optimally forever after:

The companion equation for the action-value function replaces the outer maximization with an expectation over the next state's best action:

These two equations are mutually consistent — each can be derived from the other — and together they form a system of $|\mathcal{S}|$ (or $|\mathcal{S}||\mathcal{A}|$) nonlinear equations in the unknowns $v_*(s)$ (or $q_*(s,a)$). The crucial difference from the policy-evaluation Bellman equation is the $\max$ operator replacing an expectation $\sum_a \pi(a|s)(\cdot)$: this single change converts a linear system (solvable by matrix inversion for fixed $\pi$) into a nonlinear one with no closed-form solution in general. Once $q_*$ is known, an optimal policy falls out immediately by acting greedily:

This is the payoff of solving the optimality equation: it converts the global problem of searching over policies (an exponentially large space) into a local, one-step-lookahead decision at each state, because all of the long-term consequences of future decisions are already baked into $q_*$.

There is no closed-form algebraic solution to the Bellman optimality equations for a general MDP — the $\max$ operator makes the system nonlinear, so you cannot simply invert a matrix as you can for policy evaluation. Instead, the standard approach is to construct an operator whose fixed point is $v_*$, and show that iterating it converges. Define the Bellman optimality operator $T^*$ acting on any value function $v: \mathcal{S} \to \mathbb{R}$ by

The optimality equation is precisely the statement $v_* = T^* v_*$, i.e., $v_*$ is a fixed point of $T^*$. The algorithmic idea (fully developed under Value Iteration) is to start from an arbitrary $v_0$ and repeatedly apply $T^*$: ``` ALGORITHM: Bellman Optimality Backup (single sweep, conceptual) Input: MDP (S, A, p, r, gamma), current value estimate v[s] for all s Output: updated value estimate v'[s], and greedy policy pi[s] for each state s in S: best_value <- -infinity best_action <- undefined for each action a in A(s): q_sa <- 0 for each (s', r) with p(s', r | s, a) > 0: q_sa <- q_sa + p(s', r | s, a) (r + gamma v[s']) if q_sa > best_value: best_value <- q_sa best_action <- a v'[s] <- best_value # this is (T v)(s) pi[s] <- best_action # greedy policy w.r.t. v return v', pi ``` ``` ALGORITHM: Iterating to the fixed point (sketch of Value Iteration) Input: MDP, tolerance theta > 0 Initialize v[s] arbitrarily (e.g., 0) for all s, v[terminal] = 0 repeat: delta <- 0 v_old <- copy of v (v, pi) <- Bellman_Optimality_Backup(v_old) # one full sweep delta <- max_s |v[s] - v_old[s]| until delta < theta return v (approximately v_), pi (approximately pi_) ``` Each call to the backup is one application of $T^*$ to the entire value table (a <strong>synchronous sweep</strong>). The claim — proved below — is that this sequence $v_0, T^*v_0, (T^*)^2 v_0, \ldots$ converges to $v_*$ regardless of the initialization $v_0$, and does so at a geometric rate governed by the discount factor $\gamma$. The diagram below shows the local* computational structure of a single backup at one state: the max-over-actions "fan-out," each action fanning out further into a expectation over stochastic successor states — the classic backup diagram for $v_*$.

Existence and uniqueness of $v_*$. Define the max-norm on value functions, $\|u - v\|_\infty = \max_s |u(s) - v(s)|$. The key structural fact is: > Claim. $T^*$ is a $\gamma$-contraction: for any two value functions $u, v$, > $$\|T^u - T^v\|_\infty \le \gamma \|u - v\|_\infty.$$ Proof sketch. Fix $s$, and let $a^*$ be the action achieving the max in $(T^*u)(s)$ (ties broken arbitrarily). Then

because using $a^*$ in the second (possibly suboptimal for $v$) term can only decrease it. This simplifies to $\gamma \sum_{s'} p(s'\mid s,a^*)(u(s')-v(s')) \le \gamma \|u-v\|_\infty$. By symmetry, the same bound holds with $u,v$ swapped, giving $|(T^*u)(s) - (T^*v)(s)| \le \gamma\|u-v\|_\infty$ for every $s$, hence the claim. $\blacksquare$ Because the space of bounded value functions on $\mathcal{S}$ (with the max-norm) is a complete metric space, and $\gamma \in [0,1)$ makes $T^*$ a strict contraction, the Banach fixed-point theorem guarantees: 1. $T^*$ has a unique fixed point — call it $v_*$ — so the Bellman optimality equation has exactly one solution. 2. Starting from any initial $v_0$, the sequence $v_k = (T^*)^k v_0$ converges to $v_*$, and does so geometrically:

That this fixed point $v_*$ genuinely equals $\max_\pi v_\pi(s)$ (and is not just some arbitrary solution) is the second half of the argument, usually shown by verifying that (a) the greedy policy with respect to $v_*$ achieves $v_*$ exactly (so $v_* \le \max_\pi v_\pi$ is achieved), and (b) $v_*$ upper-bounds every $v_\pi$ (via a standard policy-improvement / induction argument). The upshot: existence of an optimal deterministic stationary policy is not an extra assumption — it is a theorem, and it comes bundled with the fixed-point argument, because the greedy policy with respect to $v_*$ is provably optimal.

Time and space complexity of one backup. For a finite MDP with $|\mathcal{S}| = n$ states, $|\mathcal{A}| = m$ actions, and letting $b$ be the number of possible successor states/rewards per $(s,a)$ pair (at most $n$ generally), one full synchronous sweep costs:

• Time: $O(n \cdot m \cdot b)$ — for each state, try each action, and for each action sum over successor outcomes. In the worst case $b = n$, giving $O(n^2 m)$ per sweep.
• Space: $O(n)$ for the value table (or $O(nm)$ if maintaining $q_*$ directly), plus $O(nm \cdot b)$ if the transition model $p(s',r\mid s,a)$ is stored explicitly (this dominates in practice).

Number of sweeps to reach tolerance $\theta$. From the contraction bound, to guarantee $\|v_k - v_*\|_\infty \le \theta$ it suffices to take

so the sweep count grows only logarithmically in the desired precision, but the constant $1/\log(1/\gamma)$ blows up as $\gamma \to 1$ — this is the well-known slow-mixing regime for highly far-sighted agents. Overall time to reach $\theta$-accuracy is $O\!\left(nmb \cdot \dfrac{\log(1/\theta)}{\log(1/\gamma)}\right)$.

Honest tradeoffs. The contraction argument requires $\gamma < 1$ (or an absorbing-goal / episodic structure ensuring effective contraction); for $\gamma = 1$ in a non-episodic setting the fixed-point theorem does not directly apply and the theory needs different tools (average-reward formulations). Also, this whole analysis assumes the transition model $p(s',r\mid s,a)$ is known — this is dynamic programming, not learning from samples. When the model is unknown, algorithms like Q-learning replace the exact expectation with a sampled estimate, trading the clean contraction guarantee for a stochastic-approximation argument (Robbins–Monro conditions) — a different but related correctness story.

Consider a tiny MDP: a robot on a 1-D line with states $\{S_1, S_2, S_3\}$ where $S_3$ is a terminal "goal" state. From $S_1$ or $S_2$ the robot can choose action Right (move toward goal) or Stay (do nothing). Transitions are deterministic. Rewards: moving Right from $S_2$ to $S_3$ gives $+10$; any other Right move gives $-1$ (cost of movement); Stay always gives $0$ and keeps the state fixed. Set $\gamma = 0.9$. $S_3$ is absorbing with value $0$ by convention (episode ends). Transition table:

We apply the value-iteration backup (deterministic transitions collapse the sum to a single term):

Initialize $v_0(S_1) = v_0(S_2) = 0$.

Sweep 1:

Sweep 2:

Sweep 3:

Since $v_3 = v_2$, we have converged: $v_*(S_1) = 8$, $v_*(S_2) = 10$, $v_*(S_3)=0$. Sanity-check directly against the optimality equation:

Both equations hold exactly, confirming $v_*$ is the fixed point. Reading off the argmax gives the optimal policy: Right in both $S_1$ and $S_2$ — the robot should always push toward the goal, and the $-1$ movement cost is worth paying because $\gamma=0.9$ discounts the future reward only mildly. Note how the convergence took only 2 sweeps here because the chain is short (length 2) — in general convergence is asymptotic, and this exactness is special to this small deterministic example.

The Bellman optimality equation is the theoretical bedrock beneath essentially every optimal-control and reinforcement-learning system that reasons about long-term consequences. Classical dynamic programming solvers for inventory management, scheduling, and finance directly compute approximations to $v_*$ or $q_*$ when the transition model is known. In modern reinforcement learning, Q-learning and its descendants (Deep Q-Networks, Double DQN, Rainbow) are all sample-based stochastic-approximation schemes whose target fixed point is exactly the $q_*$ defined here — the neural network is simply a function approximator standing in for the exact table. AlphaGo and its successors combine Monte Carlo tree search with learned value networks that approximate $v_*$ for the game tree, letting the search prune toward provably good moves. In robotics and autonomous driving, model-based planning modules that simulate forward trajectories are implicitly evaluating one-step Bellman-optimal backups at each planning horizon. Recommendation systems that model user interaction as a sequential decision process (maximizing long-term engagement rather than a single click) also frame their objective as solving this same equation, typically approximately, via policy-gradient or actor-critic methods that estimate advantages relative to $v_*$ or $q_*$.

Ask the tutor: How does the Bellman optimality equation change when transitioning from a discounted finite-horizon MDP to an average-reward or continuing task?