Policy evaluation estimates the value of a fixed policy. It is the prediction problem inside dynamic programming, TD learning, actor-critic methods, and off-policy evaluation.
Iterative policy evaluation
Repeated Bellman updates converge to the policy value in the tabular discounted case.
Definition. Starting from \(v_0\), iterative policy evaluation applies \[ v_{k+1}=T_\pi v_k. \]
Theorem. For bounded rewards and \(0\le\gamma<1\), \[ \|v_k-v_\pi\|_\infty\le\gamma^k\|v_0-v_\pi\|_\infty. \]
Proof. Since \(v_\pi=T_\pi v_\pi\) and \(T_\pi\) is a \(\gamma\)-contraction, \[ \|v_{k+1}-v_\pi\|_\infty\le\gamma\|v_k-v_\pi\|_\infty. \] Iterating gives the result.
Monte Carlo evaluation
Monte Carlo evaluation estimates values by sample returns without bootstrapping.
Definition. For visits to state \(s\), Monte Carlo evaluation averages realized returns: \[ \hat v_N(s)=\frac1{N_s}\sum_{i:S_i=s}G_i. \]
Proposition. If returns from state \(s\) are sampled i.i.d. with finite mean, then \(\hat v_N(s)\to v_\pi(s)\) almost surely.
Proof. Conditional on starting from \(s\), each return has expectation \(v_\pi(s)\). The strong law of large numbers applies to the return samples.
Linear system solution
In finite MDPs, exact policy evaluation can be solved by matrix inversion or iterative linear solvers.
Proposition. The finite policy value solves \((I-\gamma P_\pi)v=r_\pi\), and the Neumann representation is \[ v_\pi=\sum_{t=0}^\infty\gamma^tP_\pi^tr_\pi. \]
Proof. The Bellman equation gives the linear system. The Neumann series converges because \(\gamma P_\pi\) has spectral radius at most \(\gamma<1\), and multiplying \((I-\gamma P_\pi)\) by the series gives the identity.
Prediction error
Evaluation error can be measured by value norm, Bellman residual, or downstream policy-improvement loss.
Remark. A small value-function error does not always imply a small control error unless action gaps or approximate-greedy conditions are also controlled.
Model-based evaluation
For a finite MDP and fixed policy, \[ V^\pi=(I-\gamma P_\pi)^{-1}r_\pi. \] Direct solution costs \(O(|\mathsf S|^3)\) in dense arithmetic, while iterative evaluation \[ V_{k+1}=r_\pi+\gamma P_\pi V_k \] has \[ \|V_k-V^\pi\|_\infty \le\gamma^k\|V_0-V^\pi\|_\infty. \] Sparse linear solvers, Krylov methods, and multigrid ideas can exploit transition structure when the model is known.
Monte Carlo evaluation
From independent episodes starting at \(s\), the return \(G_i=\sum_{t\ge0}\gamma^tR_{i,t}\) is unbiased: \(E(G_i\mid S_{i,0}=s)=V^\pi(s)\). If \(|R_t|\le R_{\max}\), then \(|G_i|\le R_{\max}/(1-\gamma)\), and Hoeffding's inequality gives \[ \mathbb P\!\left( \left|\frac1n\sum_{i=1}^nG_i-V^\pi(s)\right|>\varepsilon \right) \le2\exp\!\left\{ -\frac{n\varepsilon^2(1-\gamma)^2}{2R_{\max}^2} \right\}. \] Monte Carlo requires completed returns but avoids bootstrapping bias.
Linear value approximation and LSTD
Let \(V_w=\Phi w\), with feature row \(\phi(s)^\top\), and let \(D=\operatorname{diag}(d_\pi)\) for a stationary state distribution. The projected Bellman equation \[ \Phi w=\Pi_D(r_\pi+\gamma P_\pi\Phi w) \] has normal equations \[ Aw=b,\qquad A=\Phi^\top D(I-\gamma P_\pi)\Phi,\quad b=\Phi^\top Dr_\pi. \] Least-squares TD estimates these moments from transitions: \[ \widehat A_n=\frac1n\sum_t \phi_t(\phi_t-\gamma\phi_{t+1})^\top,\qquad \widehat b_n=\frac1n\sum_t\phi_tR_t. \]
Theorem (on-policy uniqueness). If \(d_\pi\) is stationary with positive mass on represented states and \(\Phi\) has full column rank, then \(A\) is positive definite in quadratic form: \[ w^\top Aw\ge(1-\gamma)\|\Phi w\|_D^2. \] Hence the projected Bellman equation has a unique solution.
Proof. Put \(v=\Phi w\). Stationarity and Jensen imply \[ \|P_\pi v\|_D^2 =E\{E(v(S_{t+1})\mid S_t)^2\} \le E v(S_{t+1})^2=\|v\|_D^2. \] Thus \[ w^\top Aw =\langle v,v-\gamma P_\pi v\rangle_D \ge\|v\|_D^2-\gamma\|v\|_D\|P_\pi v\|_D \ge(1-\gamma)\|v\|_D^2. \]
Dependence and uncertainty
A single trajectory is not iid. Consistency and confidence intervals require ergodicity or mixing, and asymptotic variance includes temporal autocovariances. Regenerative simulation, batch means, martingale bounds, or Markov-chain central limit theorems supply valid uncertainty. Reporting only the regression residual variance treats dependent targets as independent and is generally wrong.