The Bellman optimality equations replace policy averaging by maximization. They characterize the best achievable value and the policies that attain it.
Optimal Bellman operator
The optimal operator performs the best one-step action choice plus optimal continuation.
Definition. For bounded \(v\), \[ (T_*v)(s)=\sup_{a\in\mathcal A}\left\{r(s,a)+\gamma\int v(s')P(\mathrm{d}s'\mid s,a)\right\}. \] For finite action sets, the supremum is a maximum.
Theorem. The optimal value \(v_*\) is the unique bounded fixed point of \(T_*\).
Proof. The operator \(T_*\) is a \(\gamma\)-contraction: for any \(u,v\), \[ |(T_*u)(s)-(T_*v)(s)|\le\gamma\|u-v\|_\infty \] because the same action comparison bounds the difference of two suprema. Banach's theorem gives a unique fixed point. Dynamic programming shows \(v_*\) satisfies the equation by optimizing the first action and then optimizing the tail.
Optimal action values
The \(q\)-form moves the maximization to the next state.
Definition. The optimal action-value equation is \[ q_*(s,a)=r(s,a)+\gamma\int \max_{a'}q_*(s',a')P(\mathrm{d}s'\mid s,a). \]
Proposition. The operator \[ (T_*^Qq)(s,a)=r(s,a)+\gamma\int\max_{a'}q(s',a')P(\mathrm{d}s'\mid s,a) \] is a \(\gamma\)-contraction in sup norm and has unique fixed point \(q_*\).
Proof. The map \(q\mapsto\max_a q(s,a)\) is nonexpansive in sup norm. Combining this with the Markov integral and the factor \(\gamma\) gives contraction. The fixed point is the optimal \(q\)-function by the same one-step optimality argument.
Greedy policies
A fixed point of the optimality equation immediately gives an optimal policy.
Theorem. If \(\pi\) is greedy with respect to \(v_*\), meaning \[ \pi(s)\in\operatorname*{argmax}_{a}\left\{r(s,a)+\gamma\int v_*(s')P(\mathrm{d}s'\mid s,a)\right\}, \] then \(v_\pi=v_*\).
Proof. For a greedy policy, \(T_\pi v_*=T_*v_*=v_*\). Thus \(v_*\) is a fixed point of \(T_\pi\). The policy Bellman operator has a unique bounded fixed point, so \(v_\pi=v_*\).
Optimality and nonuniqueness
The optimal value is unique, but optimal policies need not be.
Remark. When several actions attain the Bellman maximum at a state, any measurable selection among them is optimal. This is why value functions are often better identified than policies.
Optimal operators
For bounded \(V\), define \[ (TV)(s) =\sup_{a\in\mathsf A(s)} \left\{r(s,a)+\gamma\int V(s')P(\mathrm{d}s'\mid s,a)\right\}, \] and for action values, \[ (\mathcal TQ)(s,a) =r(s,a)+\gamma\int\sup_bQ(s',b)P(\mathrm{d}s'\mid s,a). \] Measurable-selection assumptions are needed in general spaces to replace suprema by measurable maximizing actions.
Theorem (Bellman optimality). In a finite discounted MDP, \(T\) has a unique fixed point \(V^*\), and \[ V^*(s)=\max_a\{r(s,a)+\gamma P_aV^*(s)\}. \] Every policy greedy with respect to \(V^*\) is optimal, and every optimal policy chooses only actions attaining the maximum on states it visits.
Proof. The max inequality \(|\max_ax_a-\max_ay_a|\le\max_a|x_a-y_a|\) makes \(T\) a \(\gamma\)-contraction, hence it has a unique fixed point. Let \(\pi^*\) select a maximizing action. Then \(T^{\pi^*}V^*=TV^*=V^*\); uniqueness of the policy-evaluation fixed point gives \(V^{\pi^*}=V^*\). For any \(\pi\), \(T^\pi V\le TV\); iterating from \(V^*\) or using finite-horizon induction gives \(V^\pi\le V^*\).
Finite-horizon dynamic programming
With horizon \(H\), terminal value \(V_{H+1}=0\), and possibly time-dependent rewards and kernels, \[ V_h^*(s) =\max_a\left\{r_h(s,a)+ E[V_{h+1}^*(S_{h+1})\mid s,a]\right\}, \quad h=H,\ldots,1. \] Backward induction proves optimality without contraction. The optimal policy is generally nonstationary because remaining time is part of the state.
Bellman inequalities and verification
Proposition (verification). If a bounded function \(U\) satisfies \[ U(s)\ge r(s,a)+\gamma P_aU(s)\quad\text{for every }(s,a), \] then \(U\ge V^*\). If a policy \(\pi\) attains equality \(\pi\)-almost surely at every state, then \(U=V^\pi=V^*\).
Proof. The inequality is \(U\ge TU\). Monotonicity gives \(U\ge T^nU\to V^*\). If \(\pi\) attains equality, then \(U=T^\pi U\), so \(U=V^\pi\); combined with the first conclusion this policy is optimal.
Nonuniqueness
The optimal value is unique, but optimal actions and policies need not be. Ties define a set-valued greedy correspondence. This matters for differentiability: \(V^*\) is a pointwise maximum of smooth functions and may be nonsmooth when the maximizing action changes. Entropy regularization replaces the maximum by log-sum-exp and makes the greedy policy unique under a full-support reference measure.