A Review of Off-Policy Evaluation in Reinforcement Learning

1. INTRODUCTION

• OPE estimates a policy’s mean reward from historical data generated by another policy, and is crucial offline when experimentation is unavailable or risky.Reliable uncertainty quantification can also be crucial in applications such as healthcare, recommendation, education, dialog systems, and robotics.Source: §1 · p. 1
• Dynamic treatment regimes use patient information to select treatments, with later decisions potentially depending on patients’ responses over time.Their expected outcomes can be evaluated using historical trial or observational health-record data.Source: §1 · p. 2
• The review brings statistics and reinforcement-learning research together because the communities use different frameworks and often lack awareness of each other’s work.Statistical work often uses potential outcomes and identification assumptions, while RL work commonly starts from structural assumptions such as an MDP.Source: §1 · p. 2
• Long- and infinite-horizon evaluation is challenging: stepwise estimators can be inconsistent with finitely many trajectories and can have MSE growing exponentially with horizon.The exponential dependence is unavoidable in NMDPs without further assumptions, but additional structure can alleviate the challenges.Source: §1 · p. 2
• The review focuses on long- or infinite-horizon Markovian OPE, discussing efficiency bounds, estimators that attain them, and state-of-the-art methods’ advantages and limitations.It also surveys statistical properties and possible directions for future development.Source: §1 · p. 3

2. NON-DYNAMIC SETTING

• The non-dynamic setting, also called contextual-bandit evaluation, estimates an evaluation policy’s expected return from contextual information, actions, and rewards.The action is selected by a behavior policy, which determines its conditional distribution given the context.Source: §2 · p. 3
• Identification uses weak positivity, consistency, and unconfoundedness; consistency rules out interference across time, and unconfoundedness holds automatically in randomized studies.Weak positivity requires evaluation-policy support to be included in behavior-policy support.Source: §2 · p. 4
• Importance sampling can be unstable when evaluation and behavior policies differ greatly, while the direct method can be biased under regression misspecification but needs weaker coverage.With known behavior probabilities, importance sampling is unbiased; its variance can nevertheless exceed the direct method’s when policies differ considerably.Source: §2 · pp. 4–5
• The doubly robust estimator is consistent when either the reward-regression model or behavior-policy model is well specified.Its scaled MSE can achieve the efficiency bound with sample splitting and nuisance-function error rates of op(n^-1/4).Source: §2 · pp. 5–6
• The doubly robust estimator is semiparametrically efficient when its MSE achieves the efficiency bound under the stated rate conditions.The efficiency bound is the lower bound on asymptotic MSE among regular, root-n-consistent estimators in the model.Source: §2 · p. 5
• Several alternatives address limitations of the vanilla doubly robust estimator, including methods designed for nuisance-model misspecification and estimators with specified optimality properties.Some alternatives’ optimality properties still require correct specification of the behavior policy.Source: §2 · p. 6

3.1 Data Generating Process and Problem Formulation

• The target is an evaluation policy's average cumulative reward from n i.i.d. trajectories; NMDPs allow history-dependent transitions and behavior policies, whereas TMDPs impose Markov structure.For TMDPs, transition and reward distributions depend on the current state-action pair, and the behavior policy is Markov.Source: §3.1 · pp. 7–8

3.2 DM and IS Estimators

• DM estimates the Q-function and uses it to estimate value, risking bias under Q-function misspecification; IS weights data by policy density ratios and can have large variance when ratios are large.The IS estimator is unbiased when the behavior policy is known and the cumulative ratios are set to their oracle values.Source: §3.2 · pp. 8–9

3.3 Efficiency Bounds in NMDP and TMDP

• When C′ = O(1), the TMDP efficiency bound grows polynomially with horizon H, while the NMDP bound grows exponentially and makes exponential error unavoidable without further assumptions.Both C and C′ exceed 1 when the evaluation and behavior policies differ.Source: §3.3 · p. 10

3.4 Efficient Estimators in NMDP

• In NMDPs, the DR estimator combines DM and IS, is consistent when either the density-ratio or Q-function model is correctly specified, and is efficient under mild nuisance-estimation rate conditions.With sample splitting, the stated rate requirements are op(n^-1/4) for both nuisance functions; the estimator's asymptotic MSE still grows exponentially with H.Source: §3.4 · pp. 10–11

3.5 Efficient Estimators in TMDP

• The TMDP DRL estimator is consistent if either its marginal density-ratio or Q-function estimates are consistent, is efficient at op(n^-1/4) rates, and has polynomial rather than exponential MSE growth in H.The NMDP DR estimator's asymptotic MSE grows exponentially with H even when it is efficient.Source: §3.5 · p. 11, §3.4 · p. 11

• The section reviews OPE using data generated from a standard Markov decision process.Source: §4 · p. 12
• MDPs have time-homogeneous transitions, and the section focuses on evaluating a stationary policy.The paper notes that most state-of-the-art RL algorithms rely on the time-homogeneity assumption.Source: §4 · p. 12
• The section proceeds from the data-generating process and parameter of interest to the efficiency bound, EIF, and OPE estimators.Source: §4 · p. 12

4.1 Data Generating Process and Parameter of Interest

• An MDP has time-invariant transition functions, and the behavior policy is assumed stationary unless otherwise noted.Source: §4.1 · p. 12
• A stationary behavior policy does not imply that states are stationary over time; the discussion also covers fixed-length trajectories without a stationary distribution.Source: §4.1 · p. 12
• For theoretical analysis, the observed data are represented as i.i.d. state-action-reward-next-state tuples, defining the nonparametric MMDP model.The tuples correspond to n trajectories of H observed decision points, so N = nH.Source: §4.1 · p. 12
• The parameter of interest is expected discounted cumulative reward, with 0 ≤ γ < 1 in this section.The paper notes that most computer-science works use discounted rewards, while some statistical work studies average reward with γ = 1.Source: §4.1 · p. 12
• Time-homogeneity permits consistent OPE estimation even when the data contain a single trajectory, unlike the NMDP or TMDP setting described earlier.The section attributes this result to the time-homogeneity assumption, which allows consistency with limited trajectories.Source: §4.1 · p. 13
• The Q-function, value function, and marginal density ratio are introduced for the evaluation policy; the initial-state distribution may be pre-specified or estimated empirically.Source: §4.1 · p. 13

4.2 Efficiency Bound and EIF

• Theorem 5 gives the efficient influence function and efficiency bound for discounted OPE under the nonparametric MMDP model.Source: §4.2 · p. 13
• The MDP efficiency bound yields an asymptotic MSE lower bound faster by a factor of H than the TMDP bound, since N = nH.Source: §4.2 · p. 13
• If the initial-state distribution is not pre-specified, the efficiency bound gains a variance term proportional to the variance of the evaluation value function under that distribution.Source: §4.2 · p. 13
• Embedding a TMDP by augmenting the state with time produces a larger EIF variance than under a stationary MDP.With a pre-specified initial-state distribution, the resulting bound is consistent with the TMDP bound; setting γ = 0 recovers Theorem 2's results.Source: §4.2 · pp. 13–14
• The discussed MDP bound is for discounted rewards; cited work also derives bounds for average reward and dependent-unit settings.Source: §4.2 · p. 14

4.3 Model-Free Estimators

• DM and marginal IS are special cases of DRL, but these model-free estimators are not efficient because they do not use additional structure.They require the number of trajectories to approach infinity for consistency and converge more slowly than the estimators introduced later.Source: §4.3 · p. 14
• With linear Q-functions, DM requires a weaker coverage condition than MIS, while consistently estimating the marginal density ratio remains challenging.The ratio remains unknown even when the behavior policy is known, unlike in the bandit setting.Source: §4.3 · p. 14
• With sample splitting, DRL is semiparametrically efficient when both nuisance functions converge at o(N^-1/4).Some nuisance-function-dependent DM and MIS estimators can also achieve the efficiency bound under specified function classes.Source: §4.3 · p. 14
• DRL is consistent when either its estimated marginal ratio or Q-function is consistent.The section also compares DRL with related doubly robust and debiased estimators.Source: §4.3 · p. 14
• Tang et al. (2020)’s horizon-robust doubly robust estimator has larger asymptotic variance than DRL and is generally not efficient.Shi et al. (2021b)’s deeply-debiased estimator supports confidence intervals and uncertainty quantification, with nuisance functions allowed to diverge at arbitrary rates.Source: §4.3 · p. 15

4.4.1 Estimation of Q-functions q(s,a)

• Fitted Q-iteration recursively updates the Q-estimator using the Bellman equation, with flexible function approximation.Each update can be cast as supervised learning using rewards plus next-state estimated values as responses and state-action pairs as predictors.Source: §4.4.1 · p. 15
• Minimax Q-learning estimates Q by minimizing a Bellman-based objective against discriminator functions; an RKHS discriminator ball gives a closed-form inner maximization.The outer minimization can use stochastic gradient descent, while linear function classes yield a closed-form estimator and reduce DM to LSTDQ.Source: §4.4.1 · p. 15
• Minimax Q-learning’s Bellman-closedness assumption has a monotonic property that FQE’s assumption does not necessarily satisfy.Minimax optimization is more challenging to implement, and hyperparameter selection is difficult for both methods because cross-validation is non-trivial.Source: §4.4.1 · pp. 15–16

4.4.2 Estimation of Marginal Ratios µ∗(s,a)

• Minimax weight-learning estimates the marginal ratio without a stationarity assumption, using an identity that is agnostic to the behavior policy.With linear function classes, the resulting marginal IS estimator reduces to LSTDQ.Source: §4.4.2 · p. 16
• When the behavior policy is known, estimating the marginal ratio can reduce to estimating the state density ratio; related minimax estimators also arise from linear-programming duality.Those estimators derive their objective from the corresponding Lagrange function.Source: §4.4.2 · p. 16

4.5 Model-Based Estimators

• A model-based estimator fits transition and reward densities from data and plugs them into the value estimator; in causal-inference literature, it is also known as the g-formula.Probabilistic neural networks have shown good empirical performance in challenging continuous-control domains.Source: §4.5 · p. 16
• Yin and Wang (2020) proved that the model-based estimator in discrete MDPs is asymptotically efficient.Uehara and Sun (2021) studied maximum-likelihood estimation of transition densities in continuous domains.Source: §4.5 · pp. 16–17
• Model-based methods can simplify hyperparameter selection through supervised learning and cross-validation, but may be less preferable with high-dimensional state information.In that setting, modeling the transition function is more challenging than modeling the value function.Source: §4.5 · p. 17

4.6 OPE and Nonparametric Instrumental Variable Estimation

• Because the Bellman equation is a conditional moment equation, Q-function estimation and subsequent policy evaluation can be formulated as nonparametric instrumental-variable estimation.The Q-function appears on both sides of the estimating equation with different inputs, a structure that permits sequential regression such as FQE.Source: §4.6 · p. 17
• Consistent OPE estimators such as ĴMIS can be constructed without Q-function estimation.Q-function estimation is therefore not required for every consistent OPE estimator.Source: §4.6 · p. 17

5.1 Convergence Rates of Q-functions

• Q-function convergence-rate analyses commonly require realizability and Bellman completeness, whose function-class requirements differ between FQE and minimax Q-learning.FQE requires BQ ⊂ Q; minimax Q-learning requires BQ ⊂ F, and enlarging F weakens the latter assumption.Source: §5.1 · p. 17
• Parametric models with finite VC dimensions yield O_p(N^-1/2) Bellman residual rates, while Hölder classes yield O_p(N^-α/(2α+d)).These rates rely on realizability and Bellman completeness; Bellman-residual errors can translate to Q-function ℓ2 errors under mild conditions.Source: §5.1 · pp. 17–18

5.2 Convergence Rates of Marginal Ratios µ∗(s, a)

• Marginal-ratio Bellman residual rates are O_p(N^-1/2) for finite-VC parametric models and O_p(N^-α/(2α+d)) for Hölder classes.The analysis requires µ* realizability and adjoint Bellman completeness; the adjoint operator plays the Bellman operator’s role for marginal density ratios.Source: §5.2 · p. 18

5.3 Do We Really Need Bellman Completeness?

• Realizability alone may not yield horizon-polynomial non-asymptotic bounds, while realizable marginal density ratios can support policy-value convergence without nuisance-estimator convergence.Bellman completeness is one additional condition used for Q-functions; matrix invertibility conditions are another option in specialized linear models.Source: §5.3 · p. 18

6.1 Non-asymptotic Lower bounds

• Non-asymptotic minimax lower bounds characterize best-possible MSE as a function of sample size, horizon, and other quantities, and have been established in specific settings.Source: §6.1 · pp. 18–19

6.2 Unmeasured confounding

• When sequential ignorability fails, policy value is not identified without added assumptions; proposed approaches include sensitivity bounds, confounded MDPs with proxies, and partially observable models.The reviewed approaches rely on assumptions that may be difficult to validate in practice.Source: §6.2 · p. 19

6.3 Partially Observable MDPs

• A model-free POMDP OPE method leverages POMDP structure, but whether model-based methods can avoid the horizon curse and learn from one trajectory remains unclear.Off-the-shelf NMDP methods suffer from the horizon curse and cannot consistently learn policy value from a single trajectory.Source: §6.3 · p. 19

6.4 Offline policy optimization

• In long- or infinite-horizon RL, policy-dependent nuisance functions and out-of-distribution actions complicate OPE-based optimization; pessimism is proposed to limit overestimation and policy drift.Source: §6.4 · pp. 19–20

6.5 General policies

• When the evaluation policy depends on an unknown behavior policy, the efficiency bound and EIF differ; deterministic policies with continuous actions lack pathwise differentiability and √n-consistent estimation.Under action-space smoothness, kernel-based estimation can remain consistent, but may perform poorly in high-dimensional action spaces.Source: §6.5 · p. 20

6.6 General causal graphs

• For general causal graphs, efficient estimators exist in some special cases, but whether nonparametrically efficient estimators exist more broadly remains unknown.With unmeasured variables, estimation procedures are less explored than the general identification condition.Source: §6.6 · p. 20