PaperlayerView exact revision on arXiv

Source-linked AI summary

Optimal and Adaptive Off-policy Evaluation in Contextual Bandits

Yu-Xiang Wang, Alekh Agarwal, Miroslav Dudik

arXiv:1612.01205v2stat.MLcs.LG

TL;DR

The paper asks how to evaluate a target policy from logged contextual-bandit data without assuming a consistent reward model. It proves minimax limits and matching guarantees for standard estimators, then proposes SWITCH to adaptively combine reward modeling and importance weighting. SWITCH retains no-worse worst-case MSE than DR or IPS and empirically improves the bias-variance tradeoff across multiple problems.

  • Problem

    The paper studies the hardness of off-policy evaluation when a consistent reward model is unavailable.

  • Method

    The paper derives finite-sample minimax bounds and proposes SWITCH, which adaptively interpolates between DM and DR or IPS using existing reward models.

  • Results

    SWITCH has MSE no worse than DR or IPS in the worst case, can reduce variance under large importance weights, and shows substantial empirical improvements across multiple problems.

  • Takeaways & Limitations

    In agnostic contextual-bandit evaluation, IPS and DR are minimax optimal, while incorporating side information through SWITCH can improve practical bias-variance tradeoffs.

  • Takeaways & Limitations

    The analysis assumes finite importance weights and includes technical assumptions on the problem instances; estimator assumptions also vary, with weaker requirements for DR than DM.

Abstract

from arXiv · show

We study the off-policy evaluation problem---estimating the value of a target policy using data collected by another policy---under the contextual bandit model. We consider the general (agnostic) setting without access to a consistent model of rewards and establish a minimax lower bound on the mean squared error (MSE). The bound is matched up to constants by the inverse propensity scoring (IPS) and doubly robust (DR) estimators. This highlights the difficulty of the agnostic contextual setting, in contrast with multi-armed bandits and contextual bandits with access to a consistent reward model, where IPS is suboptimal. We then propose the SWITCH estimator, which can use an existing reward model (not necessarily consistent) to achieve a better bias-variance tradeoff than IPS and DR. We prove an upper bound on its MSE and demonstrate its benefits empirically on a diverse collection of data sets, often outperforming prior work by orders of magnitude.

1. Introduction

The paper studies the statistical hardness of off-policy evaluation without consistent reward-model assumptions, establishing minimax guarantees and introducing SWITCH to improve the bias-variance tradeoff. Experiments show substantial improvements across multiple contextual-bandit problems.

  • Motivation: Off-policy evaluation estimates a target policy’s expected reward from logs collected under a different logging policy, avoiding costly online testing.The paper positions this as an alternative to evaluating policies directly on users, which does not scale to many target policies.
  • Motivation: The paper asks how hard policy evaluation is when reward-model consistency is unavailable, because parametric models can be biased and non-parametric models can be limited in higher dimensions.
  • Contributions: The first part establishes a rate-optimal finite-sample MSE lower bound for contextual-bandit off-policy evaluation without consistency assumptions.
  • Contributions: The lower bound matches IPS and DR upper bounds up to constants for non-degenerate context distributions, unlike settings with consistent reward models where IPS is suboptimal.
  • Contributions: SWITCH adaptively interpolates between DM and DR or IPS, retaining no-worse worst-case MSE while reducing variance when importance weights are large.
  • Empirical evaluation: Experiments on real-world multiclass-classification data show a superior SWITCH bias-variance tradeoff with substantial improvements across multiple problems.

2. Setup

The setup formalizes contextual-bandit data, target and logging policies, importance weighting, and three standard estimators for evaluating a target policy from logged samples.

  • Problem setup: Each logged contextual-bandit sample contains a context, a chosen action, and its scalar reward, with no reward feedback for other actions.
  • Problem setup: The logging policy µ generates n i.i.d. samples, while the target policy π defines the value to be estimated.
  • Importance weighting: Importance weights ρ(x, a) = π(a|x)/µ(a|x) correct for differences between target and logging action distributions under an absolute-continuity assumption.
  • Estimators: DM evaluates the target policy using a fitted reward model, whereas IPS uses importance weighting without assumptions on reward dependence.
  • Estimators: DR combines reward modeling and importance weighting because IPS can have high variance and parametric DM can be inconsistent and biased.
  • Estimators: IPS is a special case of DR with the reward estimate set identically to zero; SWITCH further interpolates these approaches with DM.

3. Limits of Off-policy Evaluation

The paper uses a minimax framework to characterize finite-sample difficulty in contextual-bandit off-policy evaluation without consistent reward models. Its lower bound matches IPS and DR up to constants in important settings, while context structure determines when this agnostic regime applies.

  • Minimax framework: The minimax analysis fixes the context distribution and logging and target policies, then takes the worst case over reward distributions.This makes the risk depend explicitly on λ, µ, and π while avoiding trivial or pathological problem classes.
  • Context regimes: Frequent context-action pairs form an intrinsically realizable component, whereas infrequent pairs are non-realizable in the worst case.With continuous contexts, all pairs are infrequent under the paper’s measure-based definition, so the worst-case problem is non-realizable everywhere.
  • Comparison with IPS and DR: For continuous context distributions, the lower bound is sharp: IPS and DR attain the minimax risk up to constant factors.The DR risk can improve on IPS when its reward model is moderately better than the zero estimator, despite identical worst-case rates.
  • Contextual versus non-contextual settings: The result extends the multi-armed-bandit lower bound and shows that IPS is minimax optimal when contexts are continuous or repeated contexts are unlikely.The additional lower-bound term is nonzero when contexts have small probabilities relative to the sample size.
  • Proof insight: The proof combines a reward-noise lower bound with an additional lower bound caused by non-degenerate context distributions.The latter component is identified as a key technical novelty and can make even deterministic rewards difficult to evaluate.

4. Incorporating Reward Models

The SWITCH estimators use a threshold on importance weights to combine unbiased IPS or DR estimates with potentially biased direct-model predictions. Automatic tuning estimates variance and conservatively bounds bias to select a threshold, yielding minimax-optimal behavior and robustness to large weights.

  • 4.1. The SWITCH Estimators: SWITCH uses IPS or DR for small importance weights and switches to the direct method for large weights, controlled by threshold τ.The threshold creates a family interpolating between agnostic estimators and reward-model imputation.
  • 4.1. The SWITCH Estimators: SWITCH interpolates between DM at τ = 0 and IPS as τ →∞, while SWITCH-DR replaces IPS with DR in the small-weight region.Both variants are designed to reduce sensitivity to large or heavy-tailed importance weights.
  • 4.2. Automatic Parameter Tuning: The threshold-selection procedure minimizes an estimate of variance plus an upper bound on squared bias using logged data and a known reward bound.Variance is estimated from the SWITCH outputs, while the bias bound uses the largest possible direct-method error for each data point.
  • 4.2. Automatic Parameter Tuning: The conservative bias bound preserves minimax optimality because SWITCH incurs bounded bias only where IPS would otherwise have larger variance.The bound favors the unbiased component unless its variance would exceed the worst-case direct-method error.
  • 4.2. Automatic Parameter Tuning: Automatic tuning selects one threshold, unlike MAGIC, which combines estimates from multiple thresholds; the paper reports that SWITCH tuning generally performs better than MAGIC.MAGIC uses a weighted combination based on different bias and variance estimators.

5. Experiments

Experiments simulate contextual bandits from UCI multiclass classification data under deterministic and noisy rewards. Across data sets and sample sizes, SWITCH-DR improves the bias-variance tradeoff, especially under reward noise and large importance-weight variance.

  • 5. Experiments: The study converts 10 UCI multiclass data sets into contextual bandits by treating labels as actions and rewarding correct predictions with 1.The target policy is a logistic classifier, while the logging policy uses probabilities from a model trained under covariate shift.
  • 5. Experiments: Experiments compare SWITCH and SWITCH-DR with IPS, logistic-regression DM, DR, TrunIPS, and TrimIPS using automatically tuned or oracle thresholds.The evaluation also includes MAGIC and optimizes among 21 thresholds on an exponential grid.
  • 5. Experiments: Relative MSE is measured against IPS, with smaller values across more data sets appearing toward the top-left of Figure 1.The reported MSE uses a clipped squared error to control confidence intervals when importance weights create very large variance.
  • 5. Experiments: SWITCH-DR dominates the baselines across UCI data sets, while automatically tuned τ is close to the hindsight-optimal threshold.The relative-MSE differences can span several orders of magnitude because the plot uses a logarithmic scale.
  • 5. Experiments: SWITCH-DR’s gains are greater with noisy rewards, and it remains robust as sample size increases when IPS and DR suffer higher variance.In one case it outperforms DM and IPS; in another it performs about as well as IPS and DR despite poor DM performance.

6. Conclusion

The paper establishes minimax theory for agnostic contextual-bandit off-policy evaluation and develops SWITCH estimators to exploit imperfect reward models. It reports favorable theoretical and empirical performance while identifying finite-sample theory as an open direction.

  • 6. Conclusion: IPS and DR are minimax optimal in worst-case contextual-bandit off-policy evaluation when no consistent reward model is available.The result distinguishes agnostic settings from settings with consistent reward-model assumptions.
  • 6. Conclusion: SWITCH adaptively combines DM with IPS or DR, using DM for large importance weights and importance weighting for small ones.The estimator is motivated by the practical value of side information when importance weights are too large.
  • 6. Conclusion: The paper proves favorable theoretical properties for SWITCH and finds that it works well on real-world data.The conclusion frames SWITCH as a practical way to exploit domain knowledge without requiring a consistent reward model.
  • 6. Conclusion: High-probability finite-sample MSE bounds and sharper lower bounds under realistic reward-model assumptions remain open problems.These directions are explicitly identified for future work.

A. Proof of Theorem 1

The minimax lower bound is proved by reducing off-policy evaluation to hypothesis-testing problems and applying Le Cam’s method. Separate constructions capture reward-noise variance and contextual difficulty, which are then combined under the theorem’s moment assumptions.

  • A. Proof of Theorem 1: Theorem 1’s minimax bound is obtained by combining two lower bounds proved through reductions to hypothesis testing.The appendix first simplifies the component bounds before returning to their proofs.
  • A. Proof of Theorem 1: Theorem 3 assumes E_µ[ρ^2σ^2] < ∞, and Theorem 4 introduces γ′ = max{γ, δ} to permit the important case γ = 0.The stated constructions provide functions R̂(x, a) and ρ̂(x, a) satisfying multiplicative approximation inequalities.
  • A. Proof of Theorem 1: The first lower bound captures intrinsic reward-variance difficulty even without contexts, while the second adds dependence on R2_max in non-degenerate contextual distributions.The second result applies even when reward noise σ is zero.
  • A. Proof of Theorem 1: Le Cam’s argument lower-bounds estimation error by constructing testing problems whose distributions are difficult to distinguish.The two theorems use slightly different testing reductions because their mean and variance constraints differ.

A.1. Proof of Theorem 3

The proof constructs a Gaussian family of contextual-bandit instances and reduces value estimation to testing between two reward-mean parameters. Le Cam’s method then yields a minimax lower bound by balancing distinguishability, value separation, and reward constraints.

  • Creating a family of problems: The hard-instance family fixes λ, π, and μ while varying Gaussian reward means η(x, a), subject to variance and pointwise reward bounds.Rewards are normally distributed with mean η(x, a) and variance σ2(x, a).
  • Reduction to hypothesis testing: The estimation risk is lower bounded by considering two admissible parameters η1 and η2 whose policy values are sufficiently separated.The proof relates squared estimation losses to the difficulty of distinguishing the corresponding data-generating distributions.
  • Reduction to hypothesis testing: A test derived from any estimator makes an error only when the estimator incurs sufficiently large loss under the true parameter.The argument uses the separation of the two losses and bounds test error through estimation error.
  • Invoking Le Cam’s argument: Le Cam’s argument lower bounds the testing error, with Gaussian KL divergence determined by squared mean separation scaled by reward variance.This converts limited statistical distinguishability into a lower bound for policy-value estimation.
  • Picking the parameters: The minimax lower bound is characterized variationally as the largest separation level satisfying the estimation, testing, and reward-range constraints.A feasible choice of the reward-mean difference Δ is then substituted to obtain the theorem’s final bound.

A.2. Proof of Theorem 4

The proof handles noiseless rewards by randomizing the reward function across a partition of context-action space. It reduces estimation to testing between priors and controls the resulting decomposition with concentration bounds.

  • Creating a family of problems: Because noiseless two-function constructions make mean identification trivial, the proof randomizes reward means using a prior over partition cells.The randomized design creates effective noise across problem instances while each individual reward function remains deterministic.
  • Creating a family of problems: Each cell Bi receives a scaled-Bernoulli reward level, preserving nonnegative bounded means and zero conditional reward variance.The construction sets rewards equal to the cell-specific η(i), with activation probability θ(i).
  • Creating a family of problems: The expected policy-value MSE is decomposed into error for estimating the prior-averaged value and the variance of the random value around that average.This decomposition permits analysis of a noisy surrogate despite degenerate rewards in each fixed instance.
  • Reduction to hypothesis testing: Two priors θ1 and θ2 are chosen with separated expected policy values, allowing an estimator to induce a hypothesis test between them.The proof again relates estimation loss to testing error and applies Le Cam’s argument using Bernoulli KL divergence.
  • Bounding T2: Hoeffding’s inequality controls fluctuations of the random policy value around its prior mean, while partition truncation handles the countably many cells.The resulting bound on the fluctuation term is combined with the testing bound to complete the theorem.
  • Bounding T2: The theorem follows after bounding the prior-induced variance term and combining it with the lower bound for the prior-mean estimation term.The proof uses finite-cell approximation and tail control to justify concentration for the countable partition.

B. Proof of Theorem 2

The proof of the SWITCH estimator’s guarantee decomposes its MSE into bias and variance. It separately controls errors from direct modeling and inverse-propensity weighting before combining the bounds.

  • Bias and variance decomposition: For each context, actions are split according to whether their importance weights exceed the threshold τ.The sets A_x and A_i identify the low- and high-weight regions used by SWITCH.
  • Variance: The IPS and direct-model components are not independent because their indicators are mutually exclusive.The proof therefore applies Var(X + Y) ≤ 2Var(X) + 2Var(Y) before bounding the two contributions separately.
  • Variance: Jensen’s inequality further upper-bounds the remaining variance term.This supplies the final ingredient needed for the variance estimate.
  • Conclusion: Combining the bias and variance estimates gives the stated MSE upper bound for SWITCH.

C. Utility Lemmas

The utility lemmas provide concentration and divergence tools used throughout the proofs. They state Hoeffding’s inequality for bounded independent averages and a bound for Bernoulli KL divergence.

  • Hoeffding inequality: Hoeffding’s lemma applies to independent variables Xi bounded in intervals [ai, bi] and controls their empirical mean.The result is used to bound deviations of averages of bounded random variables.
  • Bernoulli KL-divergence: The Bernoulli KL-divergence lemma supplies an upper bound for the divergence between Bernoulli parameters p and q.This bound is invoked when comparing the prior-induced testing distributions.

D. Additional Figures from the Experiments

The additional experiment figures compare several estimators across datasets under deterministic and noisy reward settings. Panels cover datasets including ecoli, glass, page-blocks, satimage, pendigits, letter, vehicle, and wdbc.

  • The figures list IPS, DM, DR, SWITCH-DR, oracle-SWITCH-DR, oracle-Trim/TrunIPS, and SWITCH-DR-magic as comparison methods.
  • Four panels show deterministic-reward results for ecoli, glass, page-blocks, and satimage.
  • Four panels show noisy-reward results for ecoli, glass, page-blocks, and satimage.
  • Additional deterministic-reward panels cover pendigits, letter, vehicle, and wdbc.
  • Additional noisy-reward panels cover pendigits, letter, vehicle, and wdbc.
Loading 1612.01205v2…