The Bellman expectation equation is the fixed-point equation for the value of a fixed policy. It is linear in the value function once the policy is fixed.
Bellman operator for a policy
The one-step decomposition of return defines an operator whose fixed point is the policy value.
Definition. For a policy \(\pi\), define \[ (T_\pi v)(s)=r_\pi(s)+\gamma\int v(s')P_\pi(\mathrm{d}s'\mid s), \] where \(r_\pi(s)=\int r(s,a)\pi(\mathrm{d}a\mid s)\).
Theorem. The value function \(v_\pi\) is the unique bounded solution of \[ v=T_\pi v. \]
Proof. The return decomposition \(G_0=R_1+\gamma G_1\) gives \(v_\pi=T_\pi v_\pi\). If \(u\) and \(v\) both solve the equation, then \[ \|u-v\|_\infty=\gamma\|P_\pi(u-v)\|_\infty\le\gamma\|u-v\|_\infty. \] Since \(\gamma<1\), \(\|u-v\|_\infty=0\).
Matrix form
In finite spaces, policy evaluation is a linear system.
Proposition. For a finite MDP, \[ v_\pi=r_\pi+\gamma P_\pi v_\pi, \qquad v_\pi=(I-\gamma P_\pi)^{-1}r_\pi. \]
Proof. Rearrange the Bellman equation to \((I-\gamma P_\pi)v_\pi=r_\pi\). Since the spectral radius of \(P_\pi\) is at most \(1\), the Neumann series \(\sum_{k\ge0}\gamma^kP_\pi^k\) converges and equals \((I-\gamma P_\pi)^{-1}\).
Action-value expectation equation
The same fixed-point idea applies to \(q_\pi\).
Definition. The action-value Bellman operator is \[ (T_\pi^Q q)(s,a)=r(s,a)+\gamma\int\int q(s',a')\pi(\mathrm{d}a'\mid s')P(\mathrm{d}s'\mid s,a). \]
Theorem. The action-value function \(q_\pi\) is the unique bounded fixed point of \(T_\pi^Q\).
Proof. The return split after the first fixed action gives \(q_\pi=T_\pi^Qq_\pi\). The operator is a \(\gamma\)-contraction in sup norm because the transition-policy kernel is Markov. Banach's fixed-point theorem gives uniqueness.
Evaluation versus improvement
Expectation equations answer prediction questions for one policy; optimality equations answer control questions.
Remark. Many algorithms alternate these two roles: estimate \(v_\pi\) or \(q_\pi\), then choose actions greedily or approximately greedily with respect to that estimate.
Operators and resolvents
For a stationary policy \(\pi\), define \[ r_\pi(s)=\int r(s,a)\pi(\mathrm{d}a\mid s),\qquad P_\pi(\mathrm{d}s'\mid s) =\int P(\mathrm{d}s'\mid s,a)\pi(\mathrm{d}a\mid s), \] and \[ (T^\pi V)(s)=r_\pi(s)+\gamma(P_\pi V)(s). \] The Bellman expectation equation is \(V^\pi=T^\pi V^\pi\).
Theorem. On bounded measurable functions, \[ V^\pi=(I-\gamma P_\pi)^{-1}r_\pi =\sum_{t=0}^{\infty}\gamma^tP_\pi^tr_\pi, \] where the series converges in sup norm.
Proof. Markov kernels are sup-norm contractions, so \(\sum_t\|\gamma^tP_\pi^tr_\pi\|_\infty \le\|r_\pi\|_\infty/(1-\gamma)\). Multiplying partial sums by \(I-\gamma P_\pi\) telescopes to \(r_\pi-\gamma^{n+1}P_\pi^{n+1}r_\pi\), whose remainder vanishes. The series also equals the expected discounted reward by the Markov property.
Action-value equations
Define the state-action transition kernel \[ P^\pi_Q((s',a')\mid s,a) =P(s'\mid s,a)\pi(a'\mid s'). \] Then \[ Q^\pi=r+\gamma P^\pi_QQ^\pi, \qquad Q^\pi=(I-\gamma P^\pi_Q)^{-1}r. \] The value and action-value equations are linked by \[ V^\pi=\Pi_\pi Q^\pi,\qquad Q^\pi=r+\gamma P V^\pi, \] where \((\Pi_\pi Q)(s)=\int Q(s,a)\pi(\mathrm{d}a\mid s)\).
Monotonicity and comparison
Proposition. If \(r_\pi\le\tilde r_\pi\) and \(V\le W\), then \(T^\pi V\le\widetilde T^\pi W\). In particular, larger rewards produce larger values. Moreover, if \(V\le T^\pi V\), then \(V\le V^\pi\); if \(V\ge T^\pi V\), then \(V\ge V^\pi\).
Proof. Positivity of \(P_\pi\) proves operator monotonicity. Iterating \(V\le T^\pi V\) gives \(V\le(T^\pi)^nV\), and contraction implies \((T^\pi)^nV\to V^\pi\). The supersolution case is identical.
Potential-based reward shaping
Proposition. For a bounded potential \(\Phi\), replace reward by \[ r'(s,a,s')=r(s,a,s')+\gamma\Phi(s')-\Phi(s). \] Then \[ V'^\pi(s)=V^\pi(s)-\Phi(s),\qquad Q'^\pi(s,a)=Q^\pi(s,a)-\Phi(s), \] so all advantage functions and greedy policies are unchanged.
Proof. The shaping rewards telescope: \[ \sum_{t\ge0}\gamma^t \{\gamma\Phi(S_{t+1})-\Phi(S_t)\} =-\Phi(S_0), \] because boundedness makes the terminal remainder vanish.