PaperlayerView exact revision on arXiv

Source-linked AI summary

Doubly Robust Policy Evaluation and Learning

Miroslav Dudik, John Langford, Lihong Li

arXiv:1103.4601v2cs.LGcs.AIcs.ROstat.APstat.ML

TL;DR

The paper addresses offline contextual-bandit policy evaluation when rewards are partially observed and historic action proportions differ from those of a new policy. It applies doubly robust estimation, showing that accurate estimates can result from either a good reward model or a good past-policy model, with improved estimation and policies in experiments.

  • Problem

    Offline contextual-bandit policy evaluation must use partially observed historic rewards whose action proportions may not match the policy being evaluated.

  • Method

    The paper applies doubly robust estimation, combining direct reward modeling with inverse propensity scoring for policy evaluation and optimization.

  • Results

    Doubly robust policy estimation virtually always improves on inverse propensity scoring, yielding more reliable and accurate estimates in benchmark and real-world experiments.

  • Takeaways & Limitations

    Doubly robust estimation can provide unbiased or accurate value estimates when either the reward model or past-policy model is good, and the authors expect it to become common practice.

  • Takeaways & Limitations

    Inverse propensity scoring can have much larger variance, especially when the data-collection policy assigns small probabilities or differs substantially from the evaluated policy.

Abstract

from arXiv · show

We study decision making in environments where the reward is only partially observed, but can be modeled as a function of an action and an observed context. This setting, known as contextual bandits, encompasses a wide variety of applications including health-care policy 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 strength and overcome the weaknesses of the two approaches by applying the doubly robust 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 approach 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.

1. Introduction

Offline contextual-bandit learning must evaluate policies from historic data with only partial reward feedback and mismatched action proportions. The paper applies doubly robust estimation to combine reward and past-policy models, aiming for more reliable policy evaluation and optimization.

  • Contextual bandits provide feedback only for chosen actions, leaving rewards for unselected ads or treatments unobserved.
  • Offline learning evaluates policies using historic data without the ability to gather new data.
  • Direct methods require an accurate reward model, while inverse propensity scoring requires a past-policy model and can have large variance when policies differ.
  • Doubly robust estimation combines direct and inverse-propensity approaches, producing an unbiased estimate when either model is correct.
  • The paper analyzes how reward and past-policy model deviations affect doubly robust bias and variance, then applies the method to policy evaluation and optimization.

2. Problem Definition and Approach

The paper formulates offline contextual-bandit policy evaluation and optimization under partial reward observation. It combines reward modeling with action-propensity correction through a doubly robust estimator.

  • Problem Definition: Offline contextual-bandit data reveal only the reward for the selected action, while the context and action history are observed.The data-collection policy may be adaptive and randomized, and neither the environment distribution nor that policy is known.
  • Problem Definition: Policy evaluation estimates a stationary policy’s value, while policy optimization seeks a policy with maximum value.The theoretical analysis focuses on evaluation, and experiments study its use for optimization in classification.
  • Existing Approaches: The direct method estimates expected rewards from context-action pairs, but its reward model may emphasize regions irrelevant to the evaluated policy.Its estimate is close to the policy value when the estimated reward function approximates the true conditional expected reward.
  • Existing Approaches: Inverse propensity scoring estimates the past action probabilities and reweights observations to correct differences between data-collection and target policies.IPS is less susceptible to bias when the past-policy estimate is accurate, but its variance grows when action probabilities are small.
  • Doubly Robust Estimator: Doubly robust estimation combines the reward and propensity estimates, using the reward estimate as a baseline and observed data for correction.Its accuracy requires at least one of the two estimates to be accurate, motivating bias and variance analysis when both deviate from truth.

3. Bias Analysis

The bias analysis characterizes how reward-model and past-policy errors affect doubly robust estimation. Unlike analyses assuming one model is correct, it examines deviations of both estimates from truth.

  • Bias Analysis: The analysis represents reward-model error as an additive deviation and past-policy-model error as a multiplicative deviation.These deviations provide the variables used to study the bias of DM, IPS, and DR estimators.
  • Bias Analysis: The theoretical analysis assumes the reward and propensity estimates are fixed independently of the evaluation sample.One way to satisfy this condition is to split the original data into separate estimation and evaluation portions.
  • Bias Analysis: The bias derivation conditions on history because the propensity-related quantities depend on the history, even though context is independent of history.Summing the conditional terms yields the stated bias theorem.
  • Bias Analysis: When either reward-model error is approximately zero or propensity-model error is approximately zero, DR’s expected value is close to the true policy value.DM requires accurate reward modeling, whereas IPS requires accurate propensity modeling.
  • Bias Analysis: When one model is nearly correct and the other is imperfect, DR can outperform the corresponding single-model estimator.The paper states that DR can exploit both information sources for better estimation, while neither DM nor IPS dominates in general.

4. Variance Analysis

The variance analysis decomposes the doubly robust estimator's variance into reward randomness, context randomness, and an importance-weighting penalty. Compared with direct estimation and IPS, the analysis identifies distinct bias–variance and weighting-related trade-offs.

  • Implications: Lower variance implies faster convergence rates because large-deviation bounds primarily depend on variance.The paper uses this relationship to motivate comparing DR's variance with IPS and DM.
  • Variance Analysis: Theorem 2 gives the doubly robust estimator's variance under stationary past and evaluation policies.The analysis assumes stationary policies and drops dependence on history.
  • Variance decomposition: The doubly robust variance has three components: reward randomness, context randomness, and an importance-weighting penalty.These terms separate uncertainty from observed rewards, contexts, and action reweighting.
  • Comparison with IPS: For IPS, the first variance term matches DR and the second is similar when δ ≈0, but its importance-weighting term can be much larger.The IPS penalty grows when p(π(x) | x) is very small and |∆| is smaller than the relevant comparison quantity.
  • Comparison with the direct method: The direct method usually has lower variance because its variance lacks terms from past-policy or reward randomness.This lower variance is offset by typically much larger bias in policy-value estimation.

5. Experiments

Experiments evaluate doubly robust estimation for policy evaluation and optimization using contextual-bandit versions of classification benchmarks and an Internet-portal visitation dataset. Across these settings, DR reduces estimation error and improves learned classifiers relative to IPS and DM.

  • Data setup: The experiments transform multiclass classification into contextual bandits with partially revealed losses, enabling comparison of IPS and DR for evaluation and learning.Each example reveals only the loss of a randomly selected action; the benchmark problems come from the UCI repository.
  • Policy evaluation: IPS and DR are unbiased when the known action probability 1/k is accurate, whereas DM has much larger bias because its linear loss model poorly captures classification error.The estimators are evaluated over 500 repetitions using a linear loss model fit by least-squares ridge regression.
  • Policy optimization: DR has lower variance and rmse than IPS for policy evaluation, with the advantage becoming especially substantial during policy optimization.Policy optimization learns classifiers from losses imputed by IPS or DR and evaluates them on held-out data.
  • Policy optimization: Across all datasets, DR produces more reliable loss estimates than IPS and significantly improved classifiers.The reported average classification errors are based on 30 repeated train-test runs.
  • Policy optimization: DR versions of DLM and Filter Tree are competitive with Offset Tree in all datasets and sometimes significantly outperform it.The comparison includes DLM and Filter Tree, while the figure notes that their representations differ substantially from one another.

6. Conclusions

Doubly robust policy estimation is presented as an effective technique that improves inverse propensity score estimation, with theory supported by benchmark and real-world experiments. The authors expect it to become common practice for improving contextual bandit algorithms.

  • Doubly robust policy estimation virtually always improves on the widely used inverse propensity score method.The analysis reports more reliable and accurate estimates, corroborated by experiments on benchmark data and a large-scale real-world problem.
  • The authors expect doubly robust estimation to become common practice in improving contextual bandit algorithms.

A. Direct Loss Minimization

Direct Loss Minimization represents policies with action-specific weight vectors and optimizes them through approximate gradient updates. The implementation uses batched learning, repeated random starts, and training-loss selection.

  • The policy predicts the action with the largest dot product between the context and its action-specific weight vector.Policy π uses k weight vectors θ1, . . . , θk and predicts π(x) = arg maxa∈{1,...,k}{x · θa}.
  • Weights are updated by moving toward the loss-adjusted best action and away from the currently predicted action.The update adds ηx to θa1 and subtracts ηx from θa2, using a decaying learning rate η and parameter ǫ.
  • Batched updates use η = t−0.3/2, fix ǫ to 0.1, and continue until the weights converge.
  • Because policy loss is non-convex, the algorithm runs 20 randomly perturbed initializations and returns the run with the lowest training loss.Selecting among the 20 candidates with a holdout validation set did not provide benefits.

B. Filter Tree

The Filter Tree reduces cost-sensitive classification to binary classification using decision-tree classifiers arranged in a binary tree. Testing proceeds from root to leaf, giving logarithmic computation in the number of classes.

  • The Filter Tree converts cost-sensitive classification into a binary-tree predictor whose nodes use binary classifiers.In these experiments, each node uses the J48 decision tree implemented in Weka 3.6.4.
  • Root-to-leaf testing gives logarithmic test-time computation in the number of classes.The all-pairs Filter Tree was not tested because its test-time computation is linear in the class count, similar to Direct Loss Minimization.
Loading 1103.4601v2…