Policies define how actions are chosen, and value functions summarize the long-run consequences of those choices. The whole Bellman theory is a calculus for these functions.
State and action values
State values average over the policy's first action; action values keep the first action fixed.
Definition. For a policy \(\pi\), \[ v_\pi(s)=\mathbb E_\pi(G_0\mid S_0=s), \qquad q_\pi(s,a)=\mathbb E_\pi(G_0\mid S_0=s,A_0=a). \] The optimal values are \(v_*(s)=\sup_\pi v_\pi(s)\) and \(q_*(s,a)=\sup_\pi q_\pi(s,a)\).
Proposition. The state and action values are related by \[ v_\pi(s)=\int q_\pi(s,a)\pi(\mathrm{d}a\mid s), \quad q_\pi(s,a)=r(s,a)+\gamma\int v_\pi(s')P(\mathrm{d}s'\mid s,a). \]
Proof. The first identity conditions on \(A_0\sim\pi(\cdot\mid s)\). The second identity splits the return into \(R_1+\gamma G_1\) and conditions on \(S_1\) after fixing \((S_0,A_0)=(s,a)\).
Stationary deterministic policies
For discounted finite MDPs, optimizing over all history-dependent randomized policies is no better than optimizing over stationary deterministic policies.
Theorem. In a finite discounted MDP, there exists an optimal stationary deterministic policy \(\pi_*\) satisfying \[ \pi_*(s)\in\operatorname*{argmax}_{a\in\mathcal A}q_*(s,a). \]
Proof. The Bellman optimality operator has a unique fixed point \(v_*\). For each state choose an action attaining the finite maximum in the Bellman equation. The greedy policy \(\pi_*\) has Bellman expectation operator agreeing with the optimal operator at \(v_*\), so \(T_{\pi_*}v_*=T_*v_*=v_*\). By uniqueness of the fixed point of \(T_{\pi_*}\), \(v_{\pi_*}=v_*\).
Occupancy measures
A policy can also be represented by the discounted distribution of states and actions it visits.
Definition. The discounted state occupancy measure of \(\pi\) from \(\mu\) is \[ d_{\mu,\pi}(B)=(1-\gamma)\sum_{t=0}^\infty \gamma^tP_\pi(S_t\in B\mid S_0\sim\mu). \] The state-action occupancy is \(d_{\mu,\pi}(\mathrm{d}s,\mathrm{d}a)=d_{\mu,\pi}(\mathrm{d}s)\pi(\mathrm{d}a\mid s)\).
Proposition. For bounded \(g\), \[ \mathbb E_{\mu,\pi}\sum_{t=0}^\infty\gamma^tg(S_t,A_t) =\frac{1}{1-\gamma}\int g(s,a)d_{\mu,\pi}(\mathrm{d}s,\mathrm{d}a). \]
Proof. Substitute the definition of \(d_{\mu,\pi}\), integrate \(g\) against the distribution of \((S_t,A_t)\) at each time, and interchange the bounded sum and integral.
Value as a sufficient statistic for control
The value function compresses all future consequences of a state under a policy.
Remark. A value function is not a model of the environment. It is a prediction of return. Dynamic programming is possible because that prediction recursively supplies the continuation value after one transition.
State, action, and advantage values
For a stationary policy \(\pi\), \[ V^\pi(s)=E_s^\pi\sum_{t\ge0}\gamma^t r(S_t,A_t), \] \[ Q^\pi(s,a)=r(s,a)+\gamma\int V^\pi(s')P(\mathrm{d}s'\mid s,a), \qquad A^\pi(s,a)=Q^\pi(s,a)-V^\pi(s). \] Since \(V^\pi(s)=\int Q^\pi(s,a)\pi(\mathrm{d}a\mid s)\), \[ \int A^\pi(s,a)\pi(\mathrm{d}a\mid s)=0. \] Advantage therefore measures a one-step action deviation relative to the policy's own conditional mean.
Occupancy measures and a linear program
Theorem (finite occupancy polytope). For a finite discounted MDP, a nonnegative array \(d(s,a)\) is the normalized occupancy measure of some stationary randomized policy if and only if \[ \sum_a d(s,a) =(1-\gamma)\rho(s) +\gamma\sum_{x,a}P(s\mid x,a)d(x,a) \quad(s\in\mathsf S). \] When \(d_S(s)>0\), a realizing policy is \(\pi(a\mid s)=d(s,a)/d_S(s)\).
Proof. Necessity is the discounted flow equation. Conversely, define \(\pi\) by the displayed ratio, arbitrarily on zero-mass states. The flow equation says \(d_S\) is a fixed point of \((1-\gamma)\rho+\gamma d_SP_\pi\). This affine map is a contraction in total variation, so the fixed point is the discounted state occupancy of \(\pi\); then \(d=d_S\pi\).
Optimal control is therefore the linear program \[ \max_{d\ge0}\ \frac1{1-\gamma}\sum_{s,a}d(s,a)r(s,a) \quad\text{subject to the flow equations}. \] Its dual is \[ \min_V\ \sum_s\rho(s)V(s) \quad\text{subject to}\quad V(s)\ge r(s,a)+\gamma\sum_{s'}P(s'\mid s,a)V(s'). \] Bellman inequalities are dual feasibility conditions, and complementary slackness says an optimal occupancy places mass only on greedy actions.
The performance-difference identity
Theorem. For stationary policies \(\pi,\pi'\), \[ J_\rho(\pi')-J_\rho(\pi) =\frac1{1-\gamma} E_{(S,A)\sim d_\rho^{\pi'}}A^\pi(S,A). \]
Proof. Along a trajectory from \(\pi'\), \[ A^\pi(S_t,A_t) =r_t+\gamma E\{V^\pi(S_{t+1})\mid S_t,A_t\}-V^\pi(S_t). \] Multiply by \(\gamma^t\), take expectations, and sum. The value terms telescope to \(-E_\rho V^\pi\), while rewards sum to \(J_\rho(\pi')\). Normalize the discounted sum to obtain the identity.
Corollary. If \(\int A^\pi(s,a)\pi'(\mathrm{d}a\mid s)\ge0\) for every state, then \(V^{\pi'}\ge V^\pi\). Strict improvement at a state visited with positive discounted probability yields strict performance improvement.
Deterministic optimal policies
In finite discounted MDPs, the occupancy polytope has an optimal extreme point, and extreme occupancies can be realized by stationary deterministic policies on states with positive mass. Equivalently, selecting one maximizer of \(Q^*(s,\cdot)\) in every state gives a deterministic optimal policy. Randomization is still useful under constraints, entropy regularization, partial observability, and game-theoretic objectives.