PaperlayerView exact revision on arXiv

Source-linked AI summary

More Robust Doubly Robust Off-policy Evaluation

Mehrdad Farajtabar, Yinlam Chow, Mohammad Ghavamzadeh

arXiv:1802.03493v2cs.AI

TL;DR

The paper addresses how to learn the performance model inside doubly robust off-policy estimators, whose accuracy strongly affects estimation quality. It proposes MRDR, which learns model parameters by minimizing estimator variance, derives sample-estimable variance gradients, and evaluates the approach in bandits and reinforcement learning. MRDR is shown to be strongly consistent and asymptotically optimal, with experiments reporting superior performance in most contextual-bandit cases.

  • Problem

    Doubly robust OPE depends on its performance model, but prior work focused more on importance sampling than on how to learn that model.

  • Method

    MRDR learns the direct-method model parameters by minimizing the variance of the doubly robust estimator using sample-estimable variance gradients.

  • Results

    MRDR is strongly consistent and asymptotically optimal, and is statistically superior to alternative estimators in most contextual-bandit experiments.

  • Takeaways & Limitations

    Learning the direct-method component through the doubly robust estimator’s variance provides a principled alternative for OPE in bandits and reinforcement learning.

  • Takeaways & Limitations

    The paper leaves extensions to multiple behavior policies, combinatorial actions, and unknown behavior policies as future work.

Abstract

from arXiv · show

We study the problem of off-policy evaluation (OPE) in reinforcement learning (RL), where the goal is to estimate the performance of a policy from the data generated by another policy(ies). In particular, we focus on the doubly robust (DR) estimators that consist of an importance sampling (IS) component and a performance model, and utilize the low (or zero) bias of IS and low variance of the model at the same time. Although the accuracy of the model has a huge impact on the overall performance of DR, most of the work on using the DR estimators in OPE has been focused on improving the IS part, and not much on how to learn the model. In this paper, we propose alternative DR estimators, called more robust doubly robust (MRDR), that learn the model parameter by minimizing the variance of the DR estimator. We first present a formulation for learning the DR model in RL. We then derive formulas for the variance of the DR estimator in both contextual bandits and RL, such that their gradients w.r.t.~the model parameters can be estimated from the samples, and propose methods to efficiently minimize the variance. We prove that the MRDR estimators are strongly consistent and asymptotically optimal. Finally, we evaluate MRDR in bandits and RL benchmark problems, and compare its performance with the existing methods.

1. Introduction

Off-policy evaluation estimates an evaluation policy’s performance from behavior-policy data, a problem motivated by costly, unethical, or illegal deployment errors. The paper focuses on improving doubly robust estimators by learning their model component through variance minimization.

  • Deploying a policy without an accurate performance estimate can be costly, unethical, or illegal.
  • Off-policy evaluation estimates an evaluation policy’s performance using data generated by another policy.The problem is studied in contextual bandits and reinforcement learning and has applications including marketing, healthcare, and education.
  • Direct methods can have low variance, while importance sampling is unbiased under mild assumptions when the behavior policy is known but can have high variance.
  • Doubly robust estimators combine importance sampling with a performance model to exploit their complementary statistical properties.Prior variance-reduction methods modify the importance-sampling component or blend direct and importance-sampling estimates.
  • MRDR learns the model parameters by minimizing the variance of the doubly robust estimator in contextual bandits and reinforcement learning.The paper derives sample-estimable variance gradients, proposes efficient optimization methods, and proves strong consistency and asymptotic optimality.

2. Preliminaries

The paper models reinforcement learning as finite-horizon Markov decision processes and defines policy performance through expected discounted trajectory returns. OPE uses behavior-policy trajectories to estimate an evaluation policy’s performance under an absolute-continuity assumption.

  • Markov Decision Processes: A Markov decision process specifies state and action spaces, reward distributions, transition probabilities, an initial-state distribution, and a discount factor.The discount factor satisfies γ ∈[0, 1).
  • Markov Decision Processes: A trajectory records states, actions, and rewards generated from the initial-state, policy, transition, and reward distributions.
  • Markov Decision Processes: Policy performance is the expected discounted return of finite-horizon trajectories generated by that policy.The paper also defines state-value and action-value functions as expected returns from states or state-action pairs.
  • Markov Decision Processes: Contextual bandits are the horizon-1 special case, with contexts sampled from the initial-state distribution and no dynamic transition model.
  • Off-policy Evaluation: OPE estimates an evaluation policy’s performance from independently generated trajectories collected by a behavior policy, using mean squared error as a quality criterion.
  • Off-policy Evaluation: Absolute continuity requires every action possible under the evaluation policy to have positive probability under the behavior policy.
  • Off-policy Evaluation: Cumulative importance ratios quantify the mismatch between behavior- and evaluation-policy action probabilities along trajectory segments.

3. Existing Approaches to OPE

Existing OPE methods trade off model bias and estimator variance: direct methods model the system, importance sampling corrects policy mismatch, and doubly robust estimators combine both. The paper motivates MRDR by targeting the direct method’s loss function toward the evaluation policy and the doubly robust estimator’s variance.

  • Direct Method: Direct methods learn a system or value-function model and use it to estimate evaluation-policy performance.With suitable representations and sufficient relevant data, they can have low variance and small bias.
  • Direct Method: The direct-method loss should weight states and actions visited by the evaluation policy, so the paper assumes that policy is known before model learning.
  • Importance Sampling: Importance sampling corrects behavior-policy data using cumulative action-probability ratios and is unbiased under absolute continuity when the behavior policy is known.
  • Importance Sampling: When the behavior policy is unknown, estimating it or its importance ratios can make importance sampling biased.
  • Importance Sampling: Importance-sampling variance can grow exponentially with horizon, motivating weighted importance sampling despite its bias.Weighted importance sampling is biased but consistent and has lower variance than ordinary importance sampling.
  • Doubly Robust Estimators: Doubly robust estimators combine step-wise importance sampling with direct-method value estimates and are unbiased when either component is unbiased, under the paper’s known-behavior-policy assumption.

4. More Robust Doubly Robust Estimators

MRDR learns the direct-method model inside a doubly robust estimator by minimizing the estimator’s variance, using variance formulations whose gradients can be estimated from behavior-policy data. The resulting estimators are strongly consistent and asymptotically optimal within the relevant DR class.

  • Core idea: MRDR learns the DM parameters by minimizing the variance of the DR estimator, producing a variance-derived loss function for bandits and RL.The approach assumes a known behavior policy, so the IS and DR estimators are unbiased; MRDR then minimizes DR variance.
  • Contextual bandits: The original variance expression is unsuitable because its gradient contains the unknown DM bias term Δ(x, a) = bQ(x, a) − Q(x, a).Theorem 1 derives alternative variance forms without this unknown term, making their derivatives computable from samples.
  • Optimization: The variance formulations use expectations under the behavior policy, enabling unbiased sample-average objectives and stochastic-gradient optimization from logged data.The resulting objective is a convex quadratic function of qβ when the modeled action value is smooth, and its empirical optimizer converges almost surely to the population optimizer.
  • Optimization: For deterministic evaluation policies, MRDR can be obtained through weighted least squares with weights that adjust occupancy differences and emphasize policy-discrepant samples.Compared with DM weighting, the MRDR weighting increases the penalty for actions matching the evaluation policy but having low behavior-policy probability.
  • Reinforcement learning: The RL extension derives an analogous variance objective from behavior-policy trajectories and uses it to learn the MRDR model parameter.The RL objective is quadratic and convex in qβ, permitting gradient-based optimization when the approximation is smooth.
  • Properties and extensions: MRDR estimators are strongly consistent and have minimum variance among DR estimators of the specified form, making them asymptotically optimal in the stated estimator class.The paper also describes weighted MRDR, which introduces bias through weighted importance sampling, and extensions to multiple behavior policies using fused importance sampling.

5. Experiments

The experiments evaluate MRDR against DM, IS, DR, and DR0 on contextual-bandit and reinforcement-learning benchmarks. MRDR is significantly better than alternatives in most reported cases, while performance improves with more evaluation trajectories.

  • Experimental design: MRDR is compared with DM, IS, DR, and DR0 using MSE on contextual-bandit and RL benchmark problems.The contextual-bandit evaluation uses benchmark datasets, while RL experiments include ModelWin, ModelFail, 4 × 4 Maze, Mountain Car, and Cart Pole.
  • Contextual Bandits: In contextual-bandit experiments, MRDR significantly outperforms the alternative estimators in most cases.DM has much higher MSE across experiments, and estimation error generally increases as behavior and evaluation policies become more mismatched.
  • Reinforcement Learning: In RL experiments, MRDR has significantly lower MSE than existing methods in most cases except ModelWin, which favors DM.The comparisons use corresponding MSE values, and switching from DR0 to DR also produces significant improvements.
  • Reinforcement Learning: Increasing the sample size of evaluation trajectories improves the accuracy of every estimator in every RL experiment.Sampling-based trajectory counts vary by domain, with larger ranges used for Maze and Mountain Car.

6. Conclusions

The paper proposes MRDR estimators that learn the DR model by minimizing estimator variance, proves consistency and asymptotic optimality, and evaluates them in bandit and RL benchmarks. Future work targets settings with multiple or unknown behavior policies and combinatorial action spaces.

  • Conclusions: MRDR learns the DR model using a principled variance-minimization method.The method is proposed for off-policy evaluation in reinforcement learning.
  • Conclusions: MRDR is consistent and asymptotically optimal among unbiased, consistent, and asymptotically normal estimators.
  • Conclusions: The paper demonstrates MRDR effectiveness on contextual bandit and reinforcement learning benchmark problems.
  • Conclusions: Future work includes multiple behavior policies, combinatorial action sets such as slates, and unknown behavior policies.

A. Proofs of Section 3.1

This proof section reformulates the weighted MSE objective using trajectory quantities, conditional expectations, and the evaluation-policy occupancy measure. Terms independent of the model parameter are removed during the derivation.

  • A. Proofs of Section 3.1: The weighted MSE problem is related to the evaluation policy’s discounted state-action occupancy measure.
  • A. Proofs of Section 3.1: The derivation introduces f(X,Y) for weighted future rewards and g(X; β) for the model’s action-value estimate.
  • A. Proofs of Section 3.1: The objective is decomposed into a centered conditional-expectation term and a model-dependent residual.
  • A. Proofs of Section 3.1: Terms independent of β are dropped because they do not affect optimization over the model parameter.

B. Proofs of Section 3.2

This section proves bias expressions for trajectory-level and step-wise importance-sampling estimators, including the case where the behavior policy is unknown. The arguments use i.i.d. trajectories, approximate importance ratios, and change-of-measure expansions.

  • B. Proofs of Section 3.2: The unknown-behavior-policy IS estimator uses an approximate behavior policy and requires that approximation to be computed from data separate from the estimator data.
  • B. Proofs of Section 3.2: The bias of the trajectory-level IS estimator is characterized when the behavior policy may be approximated.
  • B. Proofs of Section 3.2: The bias derivation expands expectations over i.i.d. trajectories and defines cumulative importance ratios for the change of measure.
  • B. Proofs of Section 3.2: The step-IS estimator has an analogous bias characterization under an approximate behavior policy.
  • B. Proofs of Section 3.2: The proofs rely on trajectory independence and cumulative ratios truncated at the relevant time step.

C. Proofs of Section 3.3

This section derives the bias of the doubly robust estimator with an approximate behavior policy. The derivation expresses the result through direct-method errors, telescoping sums, and importance-ratio definitions.

  • C. Proofs of Section 3.3: The unknown-behavior-policy DR estimator uses an approximate cumulative importance ratio based on an estimated behavior policy.
  • C. Proofs of Section 3.3: The DR estimator’s bias is characterized in terms of direct-method estimation errors.
  • C. Proofs of Section 3.3: The proof applies a telescoping sum to relate the estimator terms across time steps.
  • C. Proofs of Section 3.3: The derivation uses the terminal condition V^πe(xT)=0 and definitions of the temporal-difference quantity and cumulative importance ratios.

D.1. Proof of Proposition 1

The proofs derive contextual-bandit and RL variance expressions for the doubly robust estimator, including simplified forms under deterministic evaluation policies. The RL result is established by induction over truncated returns.

  • Proposition 1: Proposition 1 expresses the bias and variance of the DR estimator for stochastic evaluation policies.
  • Deterministic policies: For deterministic evaluation policies, the variance expression reduces to the form reported by Dudík et al. (2011).
  • Theorem 1: Theorem 1 gives two equivalent variance forms for the stochastic-policy DR estimator.
  • Matrix property: The matrix Ωπb(x) used in the variance formulation is positive semi-definite.
  • RL variance: The RL variance formulation is constructed recursively using total-variance decomposition, completion of squares, and induction over truncated returns.

F. Proofs of Section 4.3

The section establishes strong consistency results for MRDR and reports contextual-bandit evaluations using classification-derived bandit data. Across most experiments, MRDR significantly outperforms alternatives, particularly on medium and large datasets.

  • Consistency: Under bounded importance weights, the MRDR estimator is strongly consistent.
  • Consistency: The DR estimator converges almost surely to the evaluation-policy value for arbitrary model parameters.
  • Contextual-bandit experiments: The contextual-bandit experiments transform standard UCI classification datasets into policy-evaluation problems with classification accuracy as the ground-truth value.
  • Results: MRDR outperforms alternative estimators statistically significantly in most experiments, with larger improvements on medium to large datasets.
  • Results: MRDR significantly outperforms MRDR0 in practice, although their theoretical comparison remains future work.

G.2. Reinforcement Learning

The RL evaluation spans several simulated domains, including known and misspecified models, gridworld, Mountain Car, and Cart Pole. MRDR is compared with existing estimators and substantially outperforms MRDR0 in the reported simulations.

  • Experimental setup: The RL experiments average accuracy and significance results over N = 100 runs with randomly generated test behavioral trajectories.
  • RL domains: The ModelFail domain represents environments that are not known perfectly, with indistinguishable states and reward differences between transitions.
  • RL domains: The ModelWin domain represents a perfectly known environment with stochastic transitions, opposing evaluation and behavior policies, and horizon T = 20.
  • RL domains: The benchmark suite also includes a 4 × 4 Maze, Mountain Car, and Cart Pole, with horizons T = 100, T = 250, and T = 250 respectively.
  • Results: MRDR0 performs much worse than MRDR in the full RL simulation results.
Loading 1802.03493v2…