PaperlayerView exact revision on arXiv

Source-linked AI summary

Doubly Robust Policy Evaluation and Optimization

Miroslav Dudík, Dumitru Erhan, John Langford, Lihong Li

arXiv:1503.02834v1stat.MEcs.AI

TL;DR

Contextual-bandit policy evaluation must infer outcomes for actions not faithfully represented in historic data, while reward and past-policy models each have weaknesses. The paper applies doubly robust estimation to policy evaluation and optimization, finding more reliable estimates and improved policies.

  • Problem

    Contextual-bandit data reveals rewards only for presented actions, while direct reward modeling can focus on areas irrelevant to the evaluated policy.

  • Method

    The paper applies doubly robust estimation to policy evaluation and optimization, combining direct modeling and inverse propensity scoring so either estimator can support unbiased estimation when correct.

  • Results

    Doubly robust policy estimation virtually always improves on inverse propensity scoring, producing more reliable and accurate estimates across stationary and nonstationary policy evaluation.

  • Takeaways & Limitations

    The authors expect doubly robust estimation to become common practice for improving contextual-bandit algorithms and policy evaluation and optimization.

  • Takeaways & Limitations

    For long-horizon trajectories, inverse-propensity likelihood ratios can grow exponentially, making estimator variance extremely large or vacuous.

Abstract

from arXiv · show

We study sequential decision making in environments where rewards are only partially observed, but can be modeled as a function of observed contexts and the chosen action by the decision maker. This setting, known as contextual bandits, encompasses a wide variety of applications such as health care, content recommendation and Internet advertising. A central task is evaluation of a new policy given historic data consisting of contexts, actions and received rewards. The key challenge is that the past data typically does not faithfully represent proportions of actions taken by a new policy. Previous approaches rely either on models of rewards or models of the past policy. The former are plagued by a large bias whereas the latter have a large variance. In this work, we leverage the strengths and overcome the weaknesses of the two approaches by applying the doubly robust estimation technique to the problems of policy evaluation and optimization. We prove that this approach yields accurate value estimates when we have either a good (but not necessarily consistent) model of rewards or a good (but not necessarily consistent) model of past policy. Extensive empirical comparison demonstrates that the doubly robust estimation uniformly improves over existing techniques, achieving both lower variance in value estimation and better policies. As such, we expect the doubly robust approach to become common practice in policy evaluation and optimization.

1. INTRODUCTION

The paper studies offline contextual-bandit policy evaluation and optimization, where historical actions and partial rewards complicate assessment of new policies. It applies doubly robust estimation to combine reward and past-policy models for more reliable inference across stationary and nonstationary policies.

  • Problem setting: Contextual bandits use observed contexts to select actions, revealing rewards only for chosen actions; applications include advertising, recommendation, and personalized treatment.Contexts can include user geography, interests, or patient health and treatment history.
  • Problem setting: Offline policy evaluation estimates a new policy’s value from historical data without gathering new data, supporting decisions such as changing ad-selection policies.Policy optimization instead searches for a high-value policy using a policy evaluator.
  • Existing approaches: Direct methods require an accurate reward model, whereas inverse propensity scoring requires an accurate model of the past policy.These approaches address the mismatch between historical action proportions and those induced by the evaluated policy.
  • Contribution: Doubly robust estimation combines the direct and inverse-propensity approaches, remaining unbiased when either estimator is correct.The paper applies this technique to policy evaluation and optimization in contextual-bandit settings.
  • Contribution: The analysis examines model deviations, bias, and variance for stationary policies, then extends the approach to nonstationary policies using rejection sampling.The nonstationary procedure uses improved rejection sampling that trades small controllable bias for better data use.

2. PRIOR WORK

The paper places doubly robust contextual-bandit estimation within statistical inference, machine learning, and dynamic treatment-regime research. It develops a nonasymptotic analysis and reports improved nonstationary evaluation quality relative to earlier rejection sampling.

  • Doubly robust estimation: Earlier doubly robust analyses largely focused on asymptotic behavior or relied on modeling assumptions, whereas this paper’s analysis is nonasymptotic and assumption-free in that respect.The claim concerns the analysis described by the authors, not the absence of all modeling requirements in applications.
  • Machine-learning connections: Related machine-learning methods use reward estimates or offsets, but the paper states that its algorithms and estimators are substantially more general.The cited examples include benign-bandit algorithms and the Offset Tree.
  • Dynamic treatment regimes: The nonstationary evaluator combines rejection sampling with doubly robust estimation and a controlled bias-variance tradeoff, yielding an empirical order-of-magnitude improvement over earlier evaluation quality.The approach builds on prior rejection-sampling work.
  • Dynamic treatment regimes: Contextual-bandit policy evaluation and optimization correspond to estimating and optimizing dynamic treatment regimes using observational or offline data.A treatment is an action, patient characteristics are context, and a treatment regime is a policy.
  • Dynamic treatment regimes: Contextual-bandit contexts are IID and do not depend on previous actions, unlike the long-term state effects typical of dynamic treatment regimes.The paper identifies this distinction as enabling statistically more efficient estimators.

3. EVALUATION OF STATIONARY POLICIES

The paper formalizes stationary policy evaluation from contextual-bandit logs, where only chosen-action rewards are observed and the exploration policy may be unknown or nonstationary. It analyzes doubly robust estimation by relating bias and variance to reward-model and exploration-policy accuracy, then derives finite-sample guarantees.

  • Setting: Stationary policy evaluation estimates the expected reward of a target policy from finite historical triples generated by an exploration policy.Contexts are IID, actions come from a finite set, and rewards may depend stochastically on context and action.
  • Setting: Partial reward observation prevents direct evaluation because logs reveal rewards only for chosen actions, not counterfactual actions selected by a new policy.The target policy must therefore be evaluated using models or reweighting based on historical data.
  • Existing approaches: IPS is approximately unbiased when the exploration-policy estimate is accurate, but its variance increases with the importance-weight ratio, especially when estimated propensities are small.The doubly robust estimator uses the reward estimate as a baseline and applies an observed-reward correction.
  • Doubly robust analysis: Doubly robust estimation remains close to the true value when either the reward-model error or exploration-policy error is small, whereas DM and IPS each require their corresponding model to be accurate.Its variance includes an importance-weighting penalty, while better reward estimates can reduce the penalty without eliminating it in general.
  • Existing approaches: The direct method has low variance because it avoids exploration-policy and reward-randomness terms, but its value estimates can have larger bias when the reward model is inaccurate.Its reward estimate may also focus on regions irrelevant to the target policy.
  • Finite-sample analysis: The analysis derives a finite-sample confidence bound for the doubly robust estimate and examines how deviations of both models from truth affect bias and variance without assuming either model is correct.The bound holds for every sample size n, while the stated assumptions require probability-one bounds that are also relaxed to moment bounds in an appendix.

4. EXPERIMENTS: THE STATIONARY CASE

The stationary experiments evaluate DR against DM and IPS on simulated partial-feedback classification data, policy optimization benchmarks, and real-world policy-evaluation tasks. Across these settings, DR reduces estimation variance and improves optimized classifiers, while its comparison with DM under estimated propensities remains unresolved.

  • 4.1.1 Data generation: The experiments use multiclass classification datasets transformed into contextual-bandit data with only the selected action’s loss observed.Fully revealed data provide ground-truth policy values, while exploration and partial feedback are simulated.
  • 4.1.2 Policy evaluation: With perfect exploration-policy logging, IPS and DR are unbiased, whereas DM has substantially larger bias because its linear loss model misses classification error.The evaluation repeats the protocol 500 times and reports bias and RMSE.
  • 4.1.3 Policy optimization: For policy optimization, DR produces substantially more reliable loss estimates than IPS and significantly improved classifiers across all datasets.The optimization procedure learns classifiers from losses completed by either IPS or DR using DLM and Filter Tree.
  • 4.1.3 Policy optimization: DR versions of DLM and Filter Tree are competitive with Offset Tree in all datasets and sometimes significantly outperform it.The improvement appears in both gradient-descent and tree-induction algorithms.
  • 4.2 Estimating the Average Number of User Visits: DR has lower variance and RMSE than IPS in policy evaluation, especially with smaller datasets, reducing RMSE by 10%–20% and by 13.6% on average.The accuracy gain is attributed to lower variance when a reasonable reward estimator is available.
  • 4.2 Estimating the Average Number of User Visits: In the real-world user-visit experiment, DR has the smallest variance, but its comparison with DM is not established when exploration probabilities are estimated rather than perfectly known.The authors attribute slight self-evaluation bias to imperfect logging.

5. EVALUATION OF NONSTATIONARY POLICIES

The paper extends doubly robust policy evaluation to nonstationary policies whose actions depend on current contexts and past histories. Its replay-based evaluator uses rejection sampling, reuses rejected data, and trades a small controllable bias for improved data efficiency.

  • Nonstationary policies choose actions from both the current context and the history of prior observations.
  • The evaluation goal is to estimate a policy’s expected cumulative reward over T rounds using historical exploration data.
  • Relation to Dynamic Treatment Regimes: Trajectory-level IPS can have exponentially large variance in T; under uniform exploration and deterministic targets, its variance is O(TK^T/n).
  • A Nonstationary Policy Evaluator: DR-ns combines doubly robust estimation with rejection sampling to simulate target-policy histories while improving acceptance and sample use.The method uses both accepted and rejected samples, with the latter helping reduce final-estimator variance.
  • A Nonstationary Policy Evaluator: The evaluator’s failure probability is bounded when n ≫ T and the exploration policy assigns actions sufficiently large probabilities.A lower bound α on rejection-sampling acceptance probability controls the failure guarantee.
  • A Nonstationary Policy Evaluator: The parameter q controls a bias–acceptance-rate trade-off: larger q increases bias but reaches length T with fewer exploration samples.The paper leaves practical selection of q and c as an open question.
  • Bias Analysis: Bias introduced at round t can affect later rewards through T−t remaining rounds, producing an O(εT^2) cumulative-reward effect.The analysis motivates accepting slight bias when it substantially improves the acceptance rate and provides more replicates.
  • Bias Analysis: The paper presents its bias theorem as the first theorem of this kind for policy evaluators.

6. EXPERIMENTS: THE NONSTATIONARY CASE

The experiment evaluates doubly robust estimators for nonstationary contextual-bandit policies using simulated partial-feedback classification data. DR-ns balances bias and variance, producing more accurate estimates and extracting more usable trajectories than competing evaluators.

  • 6.1 Data Generation: The rcv1 experiment treats multiclass multilabel classification as contextual-bandit evaluation, using 40,000 examples and four top-level classes.Loss is 1 when the selected class is not among the correct labels.
  • 6.1 Data Generation: The simulated exploration policy assigns every action nonzero probability while favoring likely-correct answers, whereas evaluated policies observe only the article covariate.The exploration policy uses an extended context containing labels and random action scores, but evaluated policies see only the covariate.
  • 6.2 Evaluation of a Nonstationary Policy: The adaptive ε-greedy classifier uses ε = 0.1 random exploration, logistic-regression scores, periodic updates, and a 300-round evaluation horizon.It is warm-started on full-feedback data and retrained every 15 rounds using initialization and online observations.
  • 6.3 Compared Evaluators: Evaluation compares DM, unbiased rejection sampling, DR-ns, and a conservative DR-ns-wc variant using repeated partially labeled datasets and a simulated ground truth.The reported metrics are RMSE, absolute bias, and standard deviation; RMSE receives 95% confidence intervals.
  • 6.4 Results: DR-ns achieves a better bias–variance balance than rejection sampling and direct method, with proper q selection making evaluation substantially more accurate.Rejection sampling is unbiased but often variance-dominated, while direct method has low variance but often large bias.
  • 6.4 Results: DR-ns’s low variance comes from adaptive c_t values that increase effective data size; for q > 0, it extracts many more 300-step trajectories than RS and DR-ns-wc.When the trajectory length increases to 500, RS and DR-ns-wc cannot construct a complete trajectory.

7. CONCLUSIONS

The paper concludes that doubly robust policy estimation improves policy evaluation for stationary and nonstationary policies, with theory supported by benchmark and large-scale real-world experiments.

  • 7. CONCLUSIONS: Doubly robust policy estimation virtually always improves on the widely used inverse propensity score method.The authors expect the technique to become common practice in improving contextual-bandit algorithms.
  • 7. CONCLUSIONS: The analysis and experiments indicate that doubly robust methods provide more reliable and accurate estimates for stationary and nonstationary policies.Evidence comes from benchmark data and two large-scale real-world problems.

APPENDIX A: PROOFS OF LEMMAS 3.1–3.3

The appendix proves boundedness, expectation, and variance properties for the estimator terms used in the paper’s theoretical analysis.

  • Lemma 3.1: Lemma 3.1 bounds the range of V̂_k by 1 + M.The bound follows because the reward estimates and rewards are bounded in [0,1].
  • Lemma 3.2: Lemma 3.2 derives the expectation of the estimator term V̂_k.The proof proceeds by decomposing the relevant expectation term.
  • Lemma 3.3: Lemma 3.3 decomposes and bounds the variance of V̂_k using the appendix’s intermediate identities and boundedness conditions.The proof combines the estimator decomposition with bounds obtained through Hölder’s inequality.

APPENDIX B: FREEDMAN’S INEQUALITY

The appendix states a Freedman-type concentration inequality for a sequence of bounded real-valued random variables with conditional variances.

  • Freedman’s Inequality: The inequality applies to a sequence y_1,...,y_n with conditional expectation E_k and conditional variance V_k.It assumes a uniform bound |y_k − E_k[y_k]| ≤ D and gives a probability guarantee for any δ > 0.

APPENDIX C: IMPROVED FINITE-SAMPLE ERROR BOUND

Appendix C analyzes the error of the doubly robust value estimator for a stationary policy under moment conditions, deriving a finite-sample error bound using Hölder’s and Freedman’s inequalities.

  • The appendix replaces variable-range conditions from Section 3.4.3 with conditions on moments when analyzing the stationary-policy estimator ˆVDR.
  • For conjugate exponents p and q, the analysis assumes finite constants controlling relevant moments and estimation quantities.
  • Freedman’s inequality is applied to obtain a specific high-probability error bound for the estimator.
  • The bias and variance bounds follow from earlier lemmas combined with Hölder’s inequality.

APPENDIX D: DIRECT LOSS MINIMIZATION

Appendix D describes a direct-loss-minimization procedure for optimizing multiclass policy weights, using approximate gradient descent, batch updates, and multiple randomized restarts.

  • The policy is represented by K weight vectors, selecting the action whose context-weight score x · θa is largest.
  • Approximate gradient descent optimizes the policy loss using a toward-better adaptation of direct loss minimization.
  • The update compares actions maximizing penalized and unpenalized scores, with a decaying learning rate η and input parameter ϵ.
  • Batch updates continue until convergence, using η = t^-0.3/2 and fixing ϵ to 0.1 across datasets.
  • Because the policy loss is nonconvex, the algorithm runs 20 randomly initialized trials and returns the one with the lowest training policy loss.

APPENDIX E: FILTER TREE

Appendix E describes the Filter Tree reduction from multiclass cost-sensitive classification to binary classification and its logarithmic-time prediction structure.

  • The Filter Tree converts multiclass cost-sensitive classification into a decision tree whose internal nodes use binary base classifiers.
  • Leaves represent the original classes, while training proceeds bottom-up and prediction proceeds from the root to a leaf.
  • Using J48 decision trees as base classifiers, the implementation has logarithmic prediction time in the number of classes.
  • The all-pairs Filter Tree was not tested because its classification time is linear in the number of classes, similar to direct loss minimization.

APPENDIX F: PROOFS OF LEMMAS 5.2 AND 5.3

Appendix F proves Lemmas 5.2 and 5.3 through induction, rejection-process probability calculations, triangle inequalities, and bounds on exploration-sample events.

  • Lemma 5.2 analyzes a block beginning at the kth exploration sample, relating the target history and acceptance-rate multiplier to the resulting bound.
  • The proof computes acceptance probabilities by conditioning on preceding exploration samples being rejected.
  • The proof bounds two nonnegative error expressions separately using the constraint 0 ≤ εm ≤ ε.
  • The reach indicator identifies whether the mth sample remains in the block, with its event determined by preceding samples.
  • The resulting expressions yield equation (F.2) after bounding the deterministic conditional expectation associated with the prior exploration sample.
  • A related lemma is established by induction on T and the triangle inequality, starting from the unique empty history at T = 0.

APPENDIX G: PROGRESSIVE VALIDATION POLICY

The appendix constructs a progressive validation policy from a nonstationary learning algorithm and shows that its estimated average reward accurately reflects the stationary policy’s expected reward.

  • Policy optimization: Applying the stationary DR estimator to policy optimization transforms the contextual bandit problem into a cost-sensitive classification problem.
  • Policy construction: The nonstationary doubly robust estimator can produce a high-performing stationary policy called the progressive validation policy.The policy is constructed using ideas behind progressive validation error bounds.
  • Policy construction: The progressive validation policy randomly selects a history and then executes the original policy conditioned on that history.Histories are selected with probabilities proportional to block sizes weighted by c_t.
  • Value estimation: The stationary DR estimator estimates the progressive validation policy’s expected reward with error O(1/N).N is the number of exploration samples used to generate T blocks.
  • Guarantees: The error bound relies on bounded density ratios, reward-model squared prediction error, and variance of conditional expected rewards.Because rewards lie in [0,1], the latter two bounds can be chosen no greater than 1.
Loading 1503.02834v1…