Policy evaluation is the task of determining how well a fixed policy performs in a sequential decision-making environment. In reinforcement learning, it usually means computing or estimating the expected cumulative reward obtained by following that policy, either from particular states and actions or from a specified initial-state distribution. Unlike policy optimization, which seeks a better policy, evaluation treats the policy as given. It is a central component of many learning and planning algorithms, as well as a means of comparing decision-making systems before deployment.
Mathematical formulation
The standard setting is a Markov decision process (MDP), consisting of states, available actions, transition probabilities, rewards, and a criterion for accumulating rewards. A stationary stochastic policy specifies the probability of choosing action in state .
For a discounted task, the return from time is
where is a subsequent reward and is the discount factor. With bounded rewards, discounting ensures that this infinite sum is well defined.
The state-value function is the expected return conditional on starting in a particular state and subsequently following the policy:
The action-value function additionally conditions on the first action:
After that first action, actions are selected according to . These are two forms of a value function: one evaluates states, while the other evaluates state–action pairs.
Evaluation can also target a single performance measure,
where is the initial-state distribution. This distinction matters: estimating average performance from typical starting states can be easier than accurately estimating values throughout the entire state space.
Other return criteria
Discounted return is not the only evaluation objective:
- Finite-horizon return sums rewards over a fixed number of steps. Values generally depend on both the state and the remaining time.
- Undiscounted episodic return sums rewards until termination. Conditions on termination and rewards are needed to ensure finite expected returns.
- Average reward measures long-run reward per time step. Depending on the environment and policy, this quantity may depend on the initial state. Its evaluation uses different equations from discounted evaluation, often involving a relative or differential value function.
Consequently, the evaluation criterion must be specified before policy performance can be meaningfully compared.
Bellman expectation equations
Policy evaluation exploits a recursive property: the value of a state equals its expected immediate reward plus its discounted expected successor value. This is expressed by the Bellman expectation equation:
where is the expected immediate reward and is the transition probability.
For a finite state space, define the policy-induced reward vector and transition matrix by
The value equation becomes
For , it has the unique solution
This expression establishes that discounted evaluation of a fixed policy is a linear problem in the tabular setting. Implementations normally solve the linear system rather than explicitly form the inverse.
The corresponding action-value equation is
These are expectation equations, not optimality equations: future actions are averaged under the specified policy rather than selected by a maximum.
Evaluation with a known model
When transition probabilities and expected rewards are available, policy evaluation can use dynamic programming or numerical linear algebra.
Direct solution
For a finite MDP, solving the Bellman linear system gives values up to numerical error. A general dense direct solver has cubic time complexity in the number of states, although sparsity, problem structure, and iterative linear solvers can substantially change practical costs.
Direct solution is useful for small and moderately sized models, but storing the transition model may itself be prohibitive in large environments.
Iterative policy evaluation
An alternative repeatedly applies the Bellman expectation operator:
In the discounted finite-state setting, this operator is a contraction in the maximum norm:
Repeated updates therefore converge to from any finite initial value vector. Updates may be synchronous, using a complete previous vector, or asynchronous, updating selected states in place. Asynchronous convergence requires suitable update conditions, including continued updating of every relevant state.
The Bellman residual provides one way to assess accuracy:
As approaches one, this bound becomes less favorable, and reward information can take more iterations to propagate across long trajectories.
For finite-horizon problems, backward induction evaluates the policy from the final time step toward the beginning, without requiring an infinite sequence of iterations.
Evaluation from sampled experience
When the environment model is unavailable, values can be estimated from observed transitions or complete trajectories.
Monte Carlo evaluation
Monte Carlo methods estimate values by averaging observed returns. For example, first-visit evaluation averages the returns following the first occurrence of a state in each episode.
The method does not require transition probabilities and does not bootstrap from an existing value estimate. However, it normally requires completed episodes or a justified truncation procedure. Long or highly variable trajectories can produce estimates with high variance.
Under appropriate sampling and finite-expectation conditions, sample averages converge to the relevant expected returns. States rarely visited by the policy may nevertheless remain poorly estimated.
Temporal-difference evaluation
Temporal-difference learning updates a value estimate using an immediate reward and the estimated value of a successor state. The one-step TD(0) update is
where is a step size.
The bracketed quantity is the temporal-difference error. Because the target contains , the method bootstraps: it learns partly from its current predictions.
TD methods can update before an episode ends and can operate in continuing tasks. Tabular on-policy TD converges under standard visitation, reward, and step-size conditions. This guarantee does not extend without qualification to arbitrary combinations of function approximation and off-policy learning.
Multi-step methods and eligibility traces interpolate between short bootstrapped targets and longer sampled returns. Their performance depends on the interaction among sampling noise, bootstrapping error, and data availability.
On-policy and off-policy evaluation
On-policy evaluation uses experience generated by the policy being evaluated. Off-policy evaluation estimates a target policy’s performance using data generated by a different behavior policy.
Off-policy evaluation is important when collecting new interactions is expensive, limited, or potentially consequential. It is also statistically more demanding because the observed action and state distributions differ from those induced by the target policy.
Importance sampling
Importance sampling corrects for differing action probabilities by reweighting observations. For a finite trajectory with actions , a trajectory weight is
where is the behavior policy.
Under suitable assumptions, including the same environment dynamics and initial-state distribution, this ratio converts expectations under the behavior policy into expectations under the target policy. A crucial coverage condition is that the behavior policy gives positive probability to actions needed by the target policy on relevant trajectories.
Products of probability ratios can have extremely high variance, especially over long horizons. Per-decision weighting, weight normalization, and clipping can improve statistical behavior, but some modifications introduce bias.
Model-based and fitted evaluation
Another approach learns an environment model and evaluates the policy inside it. This can reuse data efficiently, but model errors may compound over long simulated trajectories.
Fitted Q evaluation instead learns an action-value function by repeatedly fitting targets of the form
It avoids explicitly learning transition probabilities. Nevertheless, predictions for poorly covered states or actions can be unreliable, and low fitting error on the dataset does not guarantee accurate target-policy performance.
Doubly robust estimators combine value-model predictions with importance-weighted corrections. Under the assumptions of particular estimators, consistency can hold when either the relevant value model or weighting model is correctly specified. Such guarantees do not remove coverage requirements or automatically ensure low finite-sample error.
Function approximation and scale
Large or continuous state spaces make separate tabular values impractical. Evaluation then uses a parameterized approximation such as
Possible representations include linear features, trees, and an artificial neural network. Approximation enables generalization across states but changes both the statistical problem and the convergence properties.
With linear features, some methods solve a projected Bellman equation rather than the original equation exactly. With nonlinear models, optimization may be nonconvex, and prediction errors can affect subsequent bootstrapped targets.
The combination of function approximation, bootstrapping, and off-policy learning is often called the deadly triad because it can cause instability or divergence. This is a warning about a class of interactions, not a claim that every method combining these ingredients fails.
Role in learning and control
Policy evaluation has its roots in dynamic programming and sequential decision theory. It is one of the two main stages of policy iteration:
- Evaluate the current policy.
- Improve the policy using the resulting values.
Exact policy iteration separates these stages, whereas many practical algorithms interleave partial evaluation with policy improvement.
In actor–critic methods, a critic evaluates the actor’s policy or related value quantities, while the actor changes the policy. Policy-gradient methods often use these estimates to reduce gradient variance or estimate advantages. Because the actor changes during training, the critic may continually track a moving target rather than complete evaluation of one fixed policy.
Policy evaluation should also be distinguished from Q-learning, whose standard update targets a maximizing action value and is directed toward optimal control rather than evaluation of an arbitrary fixed policy.
Reliability and limitations
An evaluation result is conditional on its reward definition, horizon, discount factor, initial-state distribution, and environment. Two evaluations using different specifications may answer different questions even when they concern the same policy.
Important limitations include:
- Insufficient coverage: logged data may contain little or no evidence about decisions favored by the target policy.
- Distribution change: distribution shift between data collection and deployment can invalidate an otherwise accurate estimate.
- Partial observability: an observed state representation may omit information needed for Markov-based evaluation assumptions.
- Unobserved confounding: in observational logs, action selection may depend on information unavailable to the evaluator, undermining ordinary off-policy identification.
- Reward misspecification: an accurately estimated return need not measure every outcome of interest.
- Selection effects: choosing the best-looking policy among many noisy estimates can produce overly optimistic reported performance.
A scalar expected return also does not describe the full distribution of outcomes. Policies with equal expected return may differ substantially in variability, rare failures, or performance across initial states. Statistical reporting may therefore include confidence intervals, outcome distributions, and subgroup or state-specific estimates, provided the data and assumptions support them.