PaperlayerView exact revision on arXiv

Source-linked AI summary

Data-Efficient Off-Policy Policy Evaluation for Reinforcement Learning

Philip S. Thomas, Emma Brunskill

arXiv:1604.00923v1cs.LGcs.AI

TL;DR

The paper addresses how to evaluate a reinforcement-learning policy from historical data generated by a different policy when deployment may be costly or dangerous. It introduces MAGIC, combining an extension of doubly robust estimation with MSE-minimizing blending of model-based and importance-sampling estimates. Empirically, MAGIC often achieves orders of magnitude lower MSE than existing estimators, although the blending scheme’s consistency requires attention in the stated setting.

  • Problem

    Off-policy policy evaluation seeks accurate estimates of a new policy’s performance from historical data without deploying it in costly or dangerous applications.

  • Method

    MAGIC extends doubly robust estimation through WDR and uses BIM to blend WDR with a model-based estimator while minimizing mean squared error.

  • Results

    MAGIC often achieves orders of magnitude lower mean squared error than prior state-of-the-art estimators and can match or exceed prior methods.

  • Takeaways & Limitations

    The proposed estimators often outperform existing importance-sampling and approximate-model estimators, while MAGIC performs similarly when the approximate model is already best.

  • Takeaways & Limitations

    The weighting schemes considered for BIM do not necessarily ensure strong consistency because they were designed for single-trajectory, on-policy evaluation.

Abstract

from arXiv · show

In this paper we present a new way of predicting the performance of a reinforcement learning policy given historical data that may have been generated by a different policy. The ability to evaluate a policy from historical data is important for applications where the deployment of a bad policy can be dangerous or costly. We show empirically that our algorithm produces estimates that often have orders of magnitude lower mean squared error than existing methods---it makes more efficient use of the available data. Our new estimator is based on two advances: an extension of the doubly robust estimator (Jiang and Li, 2015), and a new way to mix between model based estimates and importance sampling based estimates.

1. Introduction

The paper addresses off-policy policy evaluation: predicting a new reinforcement-learning policy’s performance from historical data without deploying it. MAGIC combines an extended doubly robust estimator with an MSE-minimizing blend of model-based and importance-sampling estimates, achieving substantially lower empirical error than existing methods.

  • Motivation: Off-policy policy evaluation estimates a new policy’s performance from historical data generated by other policies.Accurate evaluation matters when deploying a poor policy could be costly or dangerous.
  • Objective: The paper uses mean squared error as its estimator loss and requires strong consistency as data increases.Strong consistency means MSE converges almost surely to zero with increasing data.
  • Contribution: MAGIC is a strongly consistent estimator that directly optimizes mean squared error.Its empirical estimates often have orders of magnitude lower MSE than estimates from existing algorithms.
  • Contribution: The first contribution extends the doubly robust estimator beyond a finite, known horizon and introduces the weighted doubly robust estimator.WDR reduces variance by introducing a small amount of bias, trading bias against MSE.
  • Contribution: The second contribution, BIM, blends model-based and importance-sampling estimators to minimize mean squared error.MAGIC uses BIM to combine a purely model-based estimator with WDR.
  • Results: MAGIC often achieves orders of magnitude lower mean squared error than prior state-of-the-art estimators in simulations.The reported comparison concerns general performance across the simulations.

2. Notation

The paper formalizes discounted reinforcement-learning trajectories, value functions, historical behavior-policy data, and importance weights. It allows finite, indefinite, and infinite horizons while highlighting the variance challenge created by importance weighting.

  • Notation: A trajectory records states, actions, and rewards in a Markov decision process with finite sets for simplicity.The authors state that results carry over to more general settings, including continuous variables.
  • Notation: The objective is the expected discounted return v(π), with discount γ constrained according to the horizon setting.γ may equal 1 for finite horizons but must be below 1 for indefinite and infinite horizons.
  • Notation: The state value and state-action value functions describe expected discounted returns under policy π.The notation distinguishes the objective v from policy-specific value functions vπ and qπ.
  • Data: Historical data consists of n trajectories paired with the known behavior policies that generated them.The dataset is represented as D := {(H_i, π_i)} from trajectories H_i sampled under π_i.
  • Importance weighting: Importance weights compare the evaluation policy’s probability for the first t steps with the behavior policy’s probability.The notation ρ_i^t abbreviates the weight for trajectory i and its behavior policy.
  • Challenges: Importance weights can have high variance and a large range, creating a primary estimation challenge.Approximate-model reward predictions are bounded, and the model need not be accurate.

3. Off-Policy Policy Evaluation (OPE)

Off-policy policy evaluation asks for an estimate of an evaluation policy’s value using historical data and an approximate model. The estimator should have low mean squared error under an unknown MDP.

  • Problem definition: OPE takes an evaluation policy, historical data, and an approximate model as inputs.The historical trajectories may have been generated by known behavior policies.
  • Objective: The goal is to construct an estimator of v(πe) with low mean squared error.The MDP’s initial-state distribution, transition function, and reward function are unknown.

4. Doubly Robust (DR) Estimator

The doubly robust estimator combines an approximate MDP model with importance sampling to reduce variance while retaining robustness properties. The paper extends its derivation and establishes theoretical results beyond the original finite, known-horizon setting.

  • DR estimator: The DR estimator uses an approximate MDP model to reduce the variance of unbiased ordinary importance-sampling estimates.It is doubly robust because it can provide good estimates when either the model is accurate or behavior policies are known.
  • Derivation: The paper derives a non-recursive DR definition that removes the assumption of a finite, known horizon.The new derivation also clarifies DR’s relationship to advantage-sum estimators and control variates.
  • Theory: The new DR definition is equivalent to Jiang and Li’s estimator for finite, known horizons.The paper provides conditions for unbiasedness without horizon assumptions and proves strong consistency.
  • Interpretation: DR is a guided importance-sampling method rather than either a purely model-based or model-free estimator.The approximate model guides importance-sampling estimates without completely replacing them.

5. Weighted Doubly Robust (WDR) Estimator

WDR extends doubly robust estimation with weighted importance sampling to better balance bias and variance while retaining strong consistency under stated assumptions.

  • Strong consistency requires mean squared error to converge almost surely to zero as the available data increases, a property often preferable to unbiasedness when minimizing MSE.MSE decomposes into variance plus squared bias, so a small bias can be worthwhile when it substantially reduces variance.
  • WDR applies weighted importance sampling to the doubly robust estimator, producing a guided estimator that better balances bias and variance while maintaining asymptotic consistency.Unlike ordinary doubly robust estimation, WDR is generally biased, but its bias follows a predictable pattern.
  • WDR is unbiased for the behavior policy when n = 1, while with one behavior policy its expected value shifts toward the evaluation-policy value as trajectories increase.This describes WDR’s finite-sample bias pattern and asymptotic direction.
  • The theoretical guarantees rely on coverage and, depending on the theorem, assumptions about a single behavior policy, finite horizon, or bounded importance weights.The paper notes that assumptions not satisfied do not imply poor empirical performance; they only remove the guarantee supplied by the proof.
  • WDR is strongly consistent with one behavior policy under finite-horizon assumptions, and with many behavior policies under bounded importance weights.For finite state and action sets with finite horizon, bounded importance weights hold automatically, leaving only the coverage assumption in the many-policy result.

6. Empirical Studies (WDR)

Experiments compare WDR with importance-sampling, guided, and model-based estimators across three domains, showing that WDR often excels but is not uniformly best.

  • WDR achieved the lowest MSE among the importance-sampling and guided estimators in every simulation, and no single competitor always came within one order of its MSE.Figure 1 plots MSE against the number of episodes on logarithmic axes, with standard error bars from 128 trials.
  • ModelFail: When function approximation makes the approximate model converge to the wrong MDP, AM’s MSE plateaus above zero while WDR’s MSE converges almost surely to zero.This setting is illustrated by the ModelFail domain.
  • ModelWin: When the approximate model quickly converges to the correct MDP, AM outperforms WDR.The paper constructs the ModelWin domain to exemplify this setting.
  • WDR sometimes achieved orders of magnitude lower MSE than other guided importance-sampling estimators.The comparison included IS, PDIS, WIS, CWPDIS, DR, WDR, and the approximate-model estimator AM.
  • Because AM can sometimes achieve an order lower MSE than WDR, the experiments motivate combining or automatically selecting between the two estimators.The paper presents this as the motivation for the subsequent blending method.

7. Blending IS and Model (BIM) Estimator

BIM blends model-based and importance-sampling returns across different lengths, choosing weights to minimize MSE while addressing the limitations of prior weighting schemes.

  • The paper classifies OPE estimators as importance-sampling, purely model-based, or partial importance-sampling estimators according to their use of importance weights.Partial estimators use weights only for early steps and model predictions thereafter.
  • As return length increases, variance is expected to increase while bias decreases.This creates a spectrum between low-variance, potentially biased model estimates and higher-variance, less-biased importance-sampling estimates.
  • BIM computes a weighted average of off-policy returns spanning the purely model-based estimator and importance-sampling estimator.Shorter returns use importance sampling for fewer early rewards and rely more on the model; longer returns do the reverse.
  • Prior λ-, γ-, and Ω-return weighting schemes are insufficient because they do not necessarily make BIM strongly consistent and were designed for single-trajectory on-policy evaluation.The λ-return with λ = 1 is consistent but does not mix the two OPE methods.
  • BIM selects weights by directly minimizing the mean squared error of the combined return, using a finite subset of return lengths in practice.The ideal weights depend on unknown MSE, so the paper estimates an approximation instead.

8. Model and Guided Importance Sampling Combining (MAGIC) Estimator

MAGIC combines WDR with the approximate model through BIM, using data-driven weights to target low MSE while retaining a strong-consistency guarantee under stated conditions.

  • MAGIC is the BIM estimator instantiated with WDR as its importance-sampling component and the approximate model as its model-based component.It therefore blends guided importance-sampling estimates with purely model-based estimates.
  • The estimator’s return construction combines importance-sampling and model-based terms with a shared control variate, using WDR’s importance-weight definition.The paper places the detailed derivation of the off-policy j-step return in an appendix.
  • BIM estimates return covariances from the trajectories in D using a sample covariance matrix.The paper provides implementation details and pseudocode for MAGIC in an appendix.
  • MAGIC estimates return bias conservatively at small sample sizes using distance from a confidence interval around WDR, with the estimate becoming correct as n increases.The experiments use the tighter of percentile-bootstrap and Chernoff-Hoeffding confidence intervals.
  • MAGIC is strongly consistent when the coverage and bounded-importance-weight assumptions hold and the WDR return is included.Under these conditions, MAGIC(D) converges almost surely to v(πe).

9. Empirical Studies (MAGIC)

MAGIC generally tracks or exceeds the best performance of WDR and AM, with especially strong results in the Hybrid setting where model accuracy varies across trajectories.

  • MAGIC generally tracks or exceeds the best performance of WDR and AM across the reported experiments.In Figure 2c, MAGIC falls slightly short of AM, but the difference is small on the logarithmic scale.
  • In Hybrid, MAGIC outperforms all other estimators by combining WDR where partial observability makes the model inaccurate with AM where it is accurate.MAGIC-B performs relatively poorly, supporting the use of off-policy j-step returns rather than binary blending alone.
  • Figure 2 compares MAGIC with other estimators using the Figure 1 legend; only Figure 2d includes MAGIC-B.

10. Conclusion

The paper concludes that its new OPE estimators outperform existing methods empirically, often by orders of magnitude, while MAGIC remains competitive when the approximate model is strongest.

  • MAGIC often outperforms the approximate model estimator by orders of magnitude, unlike previous importance-sampling estimators.When the approximate model remains best, MAGIC performs similarly; elsewhere it meets or exceeds prior state-of-the-art estimators.
  • The analysis uses partial trajectories, policy-support notation, discounted returns, and boundedness assumptions for rewards and estimators.
  • The paper develops theoretical results connecting estimator consistency with mean squared error and establishes conditions for the doubly robust estimator.The supplied passages include definitions, convergence properties, and lemmas used in these proofs.

B. Doubly Robust Derivation and Proofs

The paper derives the doubly robust estimator through control variates, extends its horizon assumptions, and establishes unbiasedness and strong consistency under stated conditions.

  • Doubly Robust Derivation: The derivation explains the variance reduction by making the control variate approximate the PDIS estimator while retaining an unbiased correction.
  • Doubly Robust Derivation: The control-variate derivation subtracts a model-based term from PDIS and adds an equal-expectation estimator to reduce variance without introducing bias.The construction recursively introduces lower-variance control variates until the added term is non-random.
  • Equivalence of DR Definitions: The new DR derivation applies to infinite, indefinite, and unknown finite horizons, while matching the prior recursive definition when a finite horizon is known.
  • DR is Unbiased: Under Assumption 1, DR is unbiased for v(πe).
  • Conditions for Consistency of DR: DR is strongly consistent with one behavior policy under Assumptions 1 and 2, or with many behavior policies when importance weights are bounded under Assumptions 1 and 4.

C.1. Proof of Theorem 1

The section establishes strong consistency for WDR under stated assumptions and evaluates related estimators across domains designed to expose model and importance-sampling strengths and weaknesses.

  • C.1. Proof of Theorem 1: WDR(D) is proved strongly consistent for estimating v(πe) when Assumptions 1, 2, and 3 hold.
  • Experimental setup: The experiments compare importance-sampling, doubly robust, weighted doubly robust, and approximate-model estimators across ModelFail, ModelWin, and gridworld domains.All three domains use finite horizons and γ = 1.0.
  • ModelFail domain: In ModelFail, partial observability prevents the agent from distinguishing three underlying states, creating a setting where the approximate model fails to converge to the true MDP.The agent observes only a single state, despite transitions and rewards depending on hidden states.
  • ModelFail results: WDR outperforms AM by orders of magnitude and DR by approximately an order of magnitude in the ModelFail full-data setting.Despite inaccurate model-based control variates, DR and WDR do not perform worse than PDIS and CWPDIS, respectively.
  • ModelFail results: In the half-data ModelFail setting, splitting data to build the model shifts DR and WDR curves upward, while WDR still outperforms AM by orders and DR by an order.The other estimators remain unchanged because they do not use an approximate model.
  • ModelWin results: In ModelWin, AM has approximately an order of magnitude lower MSE than the other methods, including WDR, motivating combination of AM and WDR using BIM.The approximate model quickly converges to the correct MDP, while stochastic transitions preserve variance for DR and WDR.

D.7. Gridworld Results

Across Gridworld settings, WDR generally performs best among importance-sampling methods, while AM excels when the true horizon and deterministic dynamics make the model accurate. MAGIC is motivated by these complementary strengths and blends them rather than always selecting one.

  • WDR outperforms all other methods by at least an order of magnitude in Gridworld-FH with π4 behavior and π5 evaluation policies.
  • WDR remains the best-performing estimator in the half-data Gridworld-FH setting, by approximately an order of magnitude.
  • In Gridworld-TH, AM excels with the true horizon; full-data DR and WDR lie directly on AM because the dynamics and rewards are deterministic.
  • With half-data in Gridworld-TH, DR and WDR lag slightly behind AM because they can use only half as much data.
  • WDR tends to outperform IS, PDIS, WIS, CWPDIS, and DR across the experiments, but AM outperforms WDR by an order of magnitude in ModelFail.
  • When deterministic dynamics and rewards combine with no partial observability, DR and WDR degenerate to AM, suggesting importance sampling is unnecessary in that setting.

F. Derivation of g(j)(D) using WDR

The appendix derives off-policy j-step returns using WDR, combines importance sampling with model predictions and control variates, and describes how MAGIC estimates blending quantities before solving for return weights. It also establishes convergence properties under the stated assumptions.

  • The WDR-based off-policy j-step return combines truncated importance sampling with model predictions for rewards beyond the j-step boundary.
  • The definition of IS(j) truncates the time index at j and is equivalent to applying the estimator to an MDP terminating after Rj.
  • AM(j) can use importance sampling to correct the distribution at Sj while using the model to predict remaining rewards, although this can produce high variance.
  • MAGIC estimates the covariance matrix with a sample-covariance approximation and uses bootstrap confidence intervals to estimate the bias vector.
  • The algorithm solves a constrained quadratic program for the return weights and returns their weighted combination of off-policy j-step returns.
  • If the relevant assumptions hold and infinity is included among candidate return lengths, MAGIC converges almost surely to v(πe).

I.2. Experimental Setup

The experiments compare MAGIC with existing estimators across ModelFail, ModelWin, Gridworld, and Hybrid domains using full- and half-data settings. Results show that MAGIC generally tracks the better of WDR and AM, while multi-length blending can outperform binary combinations.

  • On ModelFail, MAGIC tracks WDR, and both outperform AM and DR by at least an order of magnitude for most sample sizes.
  • On ModelWin, MAGIC tracks AM but drifts slightly as sample size increases, with the gap remaining small relative to the distance from DR.
  • Across Gridworld results, WDR tends to outperform DR, while MAGIC usually tracks WDR and degenerates to AM in true-horizon full-data settings.
  • The Hybrid experiments show MAGIC significantly outperforming all other methods, including WDR and AM, in both full-data and half-data settings.
  • MAGIC outperforms MAGIC-B on the Hybrid domain, demonstrating the value of using off-policy j-step returns across multiple lengths.
  • MAGIC does not track WDR or AM perfectly, especially with little data, because estimating the covariance matrix and bias vector becomes difficult.
  • MAGIC performance depends on estimating covariance and bias accurately; near-zero sample mean importance weights can create high variance not captured by the sample covariance.
Loading 1604.00923v1…