Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Nan Jiang; Lihong Li

Source-linked AI summary

Doubly Robust Off-policy Value Evaluation for Reinforcement Learning

Nan Jiang, Lihong Li

arXiv:1511.03722v3Nov 11, 2015cs.LGcs.AIeess.SYstat.MEstat.ML

TL;DR

Off-policy value evaluation must estimate a target policy’s value from behavior-policy data when direct experimentation is costly or infeasible, but existing approaches trade bias against variance. The paper extends doubly robust estimation to sequential decisions, combining unbiasedness with lower variance, and reports benchmark accuracy, safe policy-improvement utility, and lower-bound matching in certain scenarios.

Problem
Off-policy value evaluation estimates a new policy’s value from another policy’s data, but general methods either have uncontrolled bias or suffer high variance.
Method
The paper proposes a sequential-decision doubly robust estimator extending the contextual-bandit estimator and analyzes its statistical properties and safe policy-improvement use.
Results
The estimator is much more accurate than importance-sampling baselines while remaining unbiased relative to regression-based approaches, and can match the Cramer-Rao lower bound in certain scenarios.
Takeaways & Limitations
Doubly robust estimation provides a high-accuracy point estimator and can serve as a subroutine for more effective safe policy improvement.
Takeaways & Limitations
The original DR estimator only reduces action-stochasticity variance and can retain large variance from stochastic rewards or state transitions even with a perfect Q-value function.

Abstract

from arXiv · show

We study the problem of off-policy value evaluation in reinforcement learning (RL), where one aims to estimate the value of a new policy based on data collected by a different policy. This problem is often a critical step when applying RL in real-world problems. Despite its importance, existing general methods either have uncontrolled bias or suffer high variance. In this work, we extend the doubly robust estimator for bandits to sequential decision-making problems, which gets the best of both worlds: it is guaranteed to be unbiased and can have a much lower variance than the popular importance sampling estimators. We demonstrate the estimator's accuracy in several benchmark problems, and illustrate its use as a subroutine in safe policy improvement. We also provide theoretical results on the hardness of the problem, and show that our estimator can match the lower bound in certain scenarios.

1. Introduction

Off-policy value evaluation estimates a new policy’s value from data collected by another policy, a setting important when direct experimentation is costly, risky, or infeasible. Existing approaches trade off variance against bias, motivating a doubly robust estimator intended to combine low variance with unbiasedness.

Off-policy value evaluation estimates a policy’s value using data collected by a different policy.
Directly running a policy may be expensive, risky, unethical, or illegal in real-world reinforcement-learning applications.
Regression-based estimators can have low variance but may require function classes that are difficult to learn accurately with limited data.
Importance-sampling approaches avoid bias but can suffer high variance, creating a central bias–variance trade-off.
The proposed estimator aims to combine the low variance of regression with the no bias of importance sampling.

2. Related Work

Related work places off-policy evaluation within finite-horizon counterfactual decision-making and connects doubly robust estimation to prior methods in statistics, treatment regimes, and contextual bandits. It also motivates DR as a tool for safer policy iteration.

The paper studies finite-horizon evaluation of expected returns from randomly drawn start states, rather than estimating an entire value function.
Doubly robust estimation extends from statistics and dynamic treatment regimes to contextual-bandit policy learning, where its variance is typically lower than importance sampling.
Off-policy evaluation supports policy-iteration safeguards, including conservative and safe policy iteration methods.

3. Background

The background defines finite-horizon off-policy evaluation from behavior-policy trajectories and reviews model-based regression, importance sampling, and contextual-bandit doubly robust estimators. These methods respectively expose challenges involving approximation bias, high variance, and independence requirements.

3.1. Markov Decision Processes: The MDP framework specifies states, actions, transitions, rewards, discounting, an initial-state distribution, and policies over actions.
3.1. Markov Decision Processes: Finite-horizon state and action values condition the target policy’s return on the initial state or action, while truncation can approximate infinite-horizon value as H increases.
3.1. Markov Decision Processes: The target is the finite-horizon value of policy π1, estimated from length-H trajectories sampled under behavior policy π0.
3.2.1. REGRESSION ESTIMATORS: Regression evaluation fits an MDP model and computes its policy value, but function approximation can introduce bias that is difficult to quantify from data.
3.2.2. IMPORTANCE SAMPLING ESTIMATORS: Importance sampling is unbiased, whereas ordinary and weighted variants differ in variance and bias: IS can grow exponentially with horizon, while WIS is biased but lower-variance.
3.3. Doubly Robust Estimator: Contextual-bandit doubly robust estimation combines an estimated reward model with importance weighting, remaining unbiased under independence and often reducing variance when the model is accurate.
3.3. Doubly Robust Estimator: When the target policy or reward model is learned from data, independent samples are required for the DR estimator to retain unbiasedness.

4. DR Estimator for the Sequential Setting

The sequential doubly robust estimator applies a contextual-bandit DR correction recursively at each horizon, combining an estimated value function with importance weighting. It is unbiased, can reduce action-induced variance when bQ is accurate, and supports confidence intervals and transition-model extensions.

Estimator: The estimator views step-wise importance sampling as a contextual-bandit problem at each horizon, with return rt + γV H−t_step-IS.The context is st, the action is at, and the stochastic return has expected value Q(st, at).
Estimator: Applying the bandit doubly robust estimator at every horizon yields an unbiased sequential estimator VDR.The construction uses an independently supplied estimate bQ of Q and defines the final policy-value estimate recursively.
Variance analysis: DR’s variance depends on the value-function error ∆ = bQ − Q, so an accurate bQ reduces variance relative to step-wise importance sampling.Step-wise importance sampling is DR’s special case with bQ ≡ 0.
Confidence intervals: Confidence intervals follow from DR’s unbiasedness on i.i.d. trajectories, although strict concentration bounds are often pessimistic in practice.The paper reports using normally approximated confidence intervals for more effective and reliable policy improvement than importance sampling.
Limitations and extension: DR only reduces action-stochasticity variance; substantial reward or state-transition stochasticity can still produce large variance even with bQ = Q.A transition-model modification can reduce state-transition variance, but using an estimated transition model introduces a small bias bounded by its estimation error.

5. Hardness of Off-policy Value Evaluation

The paper derives constrained Cramer–Rao lower bounds for off-policy value evaluation under increasingly structured MDP assumptions. In discrete tree MDPs, perfect-value DR attains the lower bound, showing that remaining transition variance is intrinsic without additional knowledge.

Setup: The hardness analysis compares DR’s variance with a constrained Cramer–Rao lower bound to determine whether transition-induced variance can be reduced.The parameterization and its encoded prior knowledge crucially affect the bound.
Tree MDPs: The analysis first considers discrete tree MDPs, where states are histories and transitions append observations after actions.The setting assumes discrete observations and actions, γ = 1, and rewards only at trajectory end.
Lower bound: Theorem 2 lower-bounds the variance of every unbiased off-policy value estimator for discrete tree MDPs.The bound is obtained by combining the constrained information calculation with the Jacobian of the target policy value.
Implication: With minimal prior knowledge, perfect-value DR matches the lower bound, so its unremoved transition variance cannot be eliminated without extra knowledge.More accurate bQ generally gives DR lower variance, while DAG structure makes the problem easier than the tree case.
C-R bound derivation: The constrained bound accounts for probability normalization through the constraint Jacobian, Fisher information matrix, and target-value Jacobian.The derivation constructs an auxiliary matrix that diagonalizes the relevant constrained information expression, making its inverse tractable.

6. Experiments

Experiments compare IS, WIS, REG, DR, and DR-bsl across benchmark domains and apply DR to safe policy improvement. DR generally combines regression’s low variance with importance sampling’s unbiasedness, achieving strong accuracy and policy-value improvement under the tested settings.

Experimental setup: Across Mountain Car, estimators are compared by normalized logarithmic RMSE while varying evaluation-data size and target-policy similarity.DR and the importance-sampling methods use Dtest; REG uses the remaining data, and 2-fold DR is shown separately.
Mountain Car: On Mountain Car, DR reaches its best error at an intermediate Dtest size and beats using all data for IS/WIS in all four graphs.DR-bsl, using a constant bQ, also outperforms IS/WIS most of the time.
Sailing: On Sailing, results are qualitatively similar to Mountain Car, with WIS matching DR in two graphs and 2-fold DR improving the strongest 3:2 split result.In the fourth graph, DR with a 3:2 split outperforms all other estimators, including REG, by a significant margin.
KDD Cup 1998 donation dataset: On the donation dataset, DR-v2 is best in every tested situation, beating WIS when π1 is far from π0 and REG when the policies are close.The setup yields an almost perfect transition model but a relatively inaccurate reward model; DR-v2 is intended for this combination.
Safe policy improvement: In safe policy improvement, DR’s value improvement largely outperforms IS, but both methods achieve their best value with C = 0 when πtrain is mostly good.This raises concern about unsafe recommendations when πtrain is poor; in a deliberately poor-policy experiment, DR is as safe as IS or better at |D| = 5000.

7. Conclusions

The paper proposes a doubly robust estimator for off-policy value evaluation, reports high point-estimation accuracy and usefulness in safe policy improvement, and shows variance can match a lower bound in certain scenarios.

The doubly robust estimator achieves high accuracy as a point estimator and is useful in safe policy improvement.
The paper provides hardness results for off-policy value evaluation.
In certain scenarios, the estimator’s variance can match the lower bound.

A. Proof of Theorem 1

The proof establishes unbiasedness and analyzes the estimator recursively across time steps, using conditional independence and zero-mean terms to control variance-related expressions.

The base case at t = H + 1 has estimator value 0, so it is unbiased with zero variance.
The inductive step assumes the theorem at step t + 1 and derives the corresponding result at time t.
The proof uses conditional independence between reward noise and the continuation value, with both terms having zero means.
The squared sum therefore becomes a sum of squared terms in expectation.
For the approximation analysis, the estimator’s bias is expressed as the expectation of the difference between the approximated and unbiased estimators.
The bias analysis defines β1 as a constant and later βt as a path-dependent random quantity bounded by maximal absolute magnitude.

C. Cramer-Rao bound for discrete DAG MDPs

This section derives a constrained Cramer–Rao lower bound for discrete DAG MDPs, parameterizing transition probabilities under normalization constraints and relating the bound to state-action occupancy ratios.

The lower-bound analysis considers layered DAG MDPs, where trajectories can diverge and later reunite at the same state.
A discrete DAG MDP has finite state and action spaces, with each state occurring at a unique time step.
The analysis assumes γ = 1 and terminal non-zero rewards, represented using an additional state sH+1.
Theorem 3 states that every unbiased estimator has variance bounded below in discrete DAG MDPs.
Compared with tree MDPs, the DAG bound replaces cumulative importance ratios with state-action occupancy ratios.
The theorem parameterizes the initial distribution and transition probabilities while enforcing normalization constraints through a Jacobian matrix F.
The constrained-bound derivation relies on an adjustment because existing Cramer–Rao-bound literature does not handle unconstrained parameters that violate normalization.
The constrained Cramer–Rao bound uses the Fisher Information Matrix and the Jacobian of the value being estimated.

D. Experiment Details

The appendix provides full details for experiments omitted from the main paper because of space limitations.

The appendix supplies full experimental details omitted from the main paper due to space limits.
The omitted material concerns the experiments reported in the paper.
The appendix serves as the location for details excluded from the main-paper presentation.

D.1. Mountain Car

Mountain Car uses a continuous-state benchmark with deterministic dynamics, then evaluates policies using a discretized tabular model learned from data. The evaluation dataset is split across increasing test-set sizes, with importance-sampling outliers cropped to a bounded range.

Mountain Car has a 2-dimensional continuous state, 3 discrete actions, deterministic dynamics, and rewards of −1 per step with discount factor 0.99.
The constructed model aggregates states by scaling position by 26 and velocity by 28, then estimates tabular model parameters from data.Unseen aggregated state-action pairs receive reward Rmin = −1 and a self-loop transition.
The experiment uses |Dtrain| = 2000 and |Deval| = 5000, with Dtest sizes ranging from 10 to 4990.
Importance-sampling estimates are cropped to [Vmin, Vmax] because their highly skewed distributions can produce extreme outliers.The cropping is used to obtain statistically significant results within a reasonable number of simulations.

D.3. KDD Cup 1998 Donation Dataset

The KDD donation experiments use simulator-generated evaluation data matched in size to the true dataset. The training policy is produced by recurrent-neural-network Q-value fitting, with sparse particles used to estimate next-state distributions efficiently.

The simulator-generated off-policy evaluation dataset matches the true dataset size of 3754 trajectories.
The training policy πtrain is generated by training a recurrent neural network to fit a Q-value function on the original data.
For each state-action pair, five sampled next states are cached as particles to approximate the fitted model’s next-state distribution.The sparse-sample approach is used for computational efficiency and is described as sufficiently accurate.
The kernel implementation is cropped to zero when state-action pairs differ by more than 1 in any dimension.Directional differences are represented as angular differences divided by 45°.