Source-linked AI summary
Counterfactual Risk Minimization: Learning from Logged Bandit Feedback
Adith Swaminathan, Thorsten Joachims
TL;DR
The paper tackles batch learning when logged bandit feedback is counterfactual, biased, and incomplete. It develops CRM, which accounts for propensity-estimator variance, and derives POEM for efficient structured prediction; POEM substantially improves generalization over the state-of-the-art on multi-label classification.
Problem
Batch learning from logged bandit feedback must learn from feedback observed only for historical predictions, making standard supervised risk estimation invalid because logs are biased and incomplete.
Method
CRM derives variance-aware generalization bounds for stochastic policies, and POEM instantiates the principle for structured output prediction with efficient stochastic optimization.
Results
POEM demonstrates substantially improved generalization performance over the state-of-the-art across several multi-label classification problems.
Takeaways & Limitations
CRM provides a robust batch-learning principle, while POEM can optimize rich policy families and massive output spaces efficiently.
Takeaways & Limitations
Counterfactual learning can be sub-optimal when the logging policy is deterministic or lacks full support over possible outputs.
Abstract
from arXiv · showhide
We develop a learning principle and an efficient algorithm for batch learning from logged bandit feedback. This learning setting is ubiquitous in online systems (e.g., ad placement, web search, recommendation), where an algorithm makes a prediction (e.g., ad ranking) for a given input (e.g., query) and observes bandit feedback (e.g., user clicks on presented ads). We first address the counterfactual nature of the learning problem through propensity scoring. Next, we prove generalization error bounds that account for the variance of the propensity-weighted empirical risk estimator. These constructive bounds give rise to the Counterfactual Risk Minimization (CRM) principle. We show how CRM can be used to derive a new learning method -- called Policy Optimizer for Exponential Models (POEM) -- for learning stochastic linear rules for structured output prediction. We present a decomposition of the POEM objective that enables efficient stochastic gradient optimization. POEM is evaluated on several multi-label classification problems showing substantially improved robustness and generalization performance compared to the state-of-the-art.
1. Introduction
The paper addresses batch learning from logged bandit feedback, where observed feedback covers only the prediction shown. It proposes CRM, which incorporates estimator variance into generalization guarantees and motivates POEM for structured prediction.
- Problem: Logged interaction data records inputs, predictions, and feedback, but the feedback is limited to the prediction actually shown.This partial-information setting differs fundamentally from supervised learning, which provides feedback for correct predictions.
- Problem: Batch learning reuses existing logs and supports offline cross-validation without requiring interactive experimental control.
- Approach: Counterfactual learning requires estimating how alternative systems would have performed using propensity-based off-policy evaluation.
- CRM: CRM selects hypotheses using generalization bounds that account for variance differences in propensity-weighted risk estimates.The bounds use an empirical Bernstein argument and extend structural risk minimization to stochastic hypothesis families.
- POEM: POEM applies CRM to structured output prediction and uses variance linearization with AdaGrad for efficient stochastic optimization.Experiments on multi-label classification report substantially improved generalization over the state-of-the-art.
2. Related Work
Prior approaches either reduce bandit learning to supervised estimation or evaluate a small candidate set with propensity scoring. The paper instead optimizes over expressive hypothesis families and assumes a stationary stochastic logging policy.
- Existing approaches: A two-stage supervised approach estimates feedback for unseen predictions before applying a supervised learner, but is reported not to generalize well.
- Existing approaches: Propensity-scored estimators are commonly used to evaluate a small candidate set, after which exhaustive search selects the best estimate.
- This approach: The paper optimizes over potentially infinite hypothesis families with gradient descent while retaining expressiveness comparable to supervised-learning families.
- Counterfactual estimators: The approach focuses on inverse propensity scoring, while the derived results also apply to doubly robust estimators.
- Scope: The analysis assumes the historical algorithm is a stationary stochastic policy; other techniques address deterministic or adaptive logging policies.
- Connections: The paper's conservative-bound selection strategy parallels approaches used in supervised learning, bandits, and reinforcement learning.
- Applications: Potential applications include warm-starting bandits, pre-selecting search retrieval functions, and contextual-bandit policy evaluation.
3. Learning Setting: Batch Learning with Logged Bandit Feedback
The learning setting uses stochastic policies that sample structured outputs while observing loss only for the sampled output. Logged data are biased toward the historical policy and incomplete for alternatives, preventing direct supervised-style risk estimation.
- Hypotheses: A stochastic hypothesis h(Y | x) defines an output distribution and samples predictions, while deterministic hypotheses are included as point-mass distributions.
- Feedback and risk: The system observes cardinal feedback only for the sampled output; smaller loss values indicate greater user satisfaction.
- Comparison: Table 1 compares supervised learning with bandit-feedback learning across assumptions, hypotheses, and learning principles.
- Feedback and risk: Learning seeks a hypothesis with minimum expected loss, equivalently maximizing expected user satisfaction.
- Logged data: The logs are collected under a stationary historical policy h0, which generates each observed output and its associated feedback.
- Sampling bias: Logged data cannot directly estimate a new hypothesis's risk because predictions favored by h0 are over-represented and feedback for other predictions is missing.
4. Learning Principle: Counterfactual Risk Minimization
Counterfactual Risk Minimization addresses sampling bias and estimator variance in logged bandit learning by optimizing a variance-sensitive conservative risk bound. The resulting principle supports propensity-weighted learning while requiring careful loss scaling, clipping, regularization, and exploration assumptions.
- Counterfactual estimation: Importance sampling corrects the distribution mismatch between the logging policy h0 and a target hypothesis h, enabling counterfactual risk estimation from logged data.The logs retain the logging policy's propensity h0(y | x), which supports an unbiased Monte Carlo estimate before clipping or regularization choices are applied.
- Estimator pitfalls: Naively minimizing the empirical risk estimator is unsafe because its behavior depends on loss scaling and its importance weights can produce unbounded variance.Small propensities can make the estimator arbitrarily far from the true risk, while additive loss transformations can create degenerate results.
- Variance-sensitive bounds: The generalization bound incorporates the empirical variance of propensity-weighted estimates, using capacity control for stochastic hypothesis classes.The analysis introduces an auxiliary deterministic function class and covering-number reasoning to establish convergence of the clipped estimator to the corresponding risk bound.
- Counterfactual Risk Minimization: The CRM principle jointly optimizes estimated risk and empirical standard deviation, treating the latter as a data-dependent regularizer.This selects a hypothesis with a tight conservative upper bound; setting λ = 0 recovers the inverse propensity scoring objective.
- Loss scaling and regularization: Losses must be scaled to [−1, 0], because nonnegative losses can make IPS and CRM degenerate by rewarding hypotheses that avoid all logged samples.The paper also uses clipping and hyper-parameters M and λ to manage bias, variance, and avoidance of the observed data.
- Feasibility conditions: Counterfactual learning depends on the logging policy exploring relevant outputs, since deterministic or incomplete-support policies can cause sub-optimal learning even with unlimited data.Heavier tails alone do not guarantee better learning; exploration of regions with favorable losses is what matters.
5. Learning Algorithm: POEM
POEM instantiates CRM for structured output prediction with stochastic exponential-family linear rules and an efficiently optimized objective. Its variance term is decomposed for stochastic optimization, though the resulting objective is non-convex and optimization finds local optima.
- POEM applies CRM to structured output prediction using stochastic linear rules parameterized by a joint feature map.The model samples predictions from an exponential-family distribution defined by weights and joint features.
- The exponential model is a soft-max distribution whose temperature-scaled weights produce more peaked, more deterministic variants while preserving prediction modes.
- The resulting objective is non-convex, and gradient-based methods find local optima with good generalization error.
- POEM software and the code and data for the reported experiments are publicly available.
- The POEM objective decomposes its variance term into differentiable functions, enabling stochastic gradient optimization at scale.The decomposition uses a Majorization-Minimization scheme and repeated variance linearization.
6. Experiments
The experiments evaluate POEM on multilabel classification using simulated bandit feedback, comparing variance-regularized and variance-agnostic methods across accuracy, efficiency, deterministic prediction, data size, logging-policy quality, and stochasticity.
- Experiment methodology: POEM is evaluated on LibSVM multilabel datasets using a Supervised 7→Bandit conversion with a CRF logging policy trained on 5% of the supervised data.The conversion samples labels from h0 and records Hamming-loss feedback and propensity scores; four passes create the bandit dataset.
- Does variance regularization improve generalization?: POEM is significantly better than IPS on each dataset and optimization variant, and substantially improves over the logging policy h0.The comparison uses a one-tailed paired difference t-test at significance level 0.05 across 10 runs.
- How computationally efficient is POEM?: Stochastic optimization recovers good parameter settings in a fraction of the time required by batch L-BFGS, with the advantage increasing as the number of labels grows.Runtime is dominated by computation of Z(x_i).
- Can MAP predictions derived from stochastic policies perform well?: The deterministic MAP predictors derived from POEM policies typically have loss close to, and often slightly better than, the corresponding stochastic policies.MAP prediction can also be substantially faster because it avoids computing the structured-output partition function Z(x).
- How does generalization improve with size of D?: As training-data size increases, POEM(S) is evaluated on Yeast under replayed bandit samples, while the experiments also vary logging-policy quality and stochasticity.POEM(S) consistently finds a hypothesis at least as good as h0, including when h0 is poor; when h0 is too deterministic, performance recovers h0 map.
- Cross-experiment trends: The same experimental trends appear across datasets and optimization variants, including when l2-regularization is added.This tests robustness of the observed findings beyond a single dataset or optimization setting.
7. Conclusion
CRM provides a robust framework for learning stochastic policies from batch bandit interactions by incorporating estimator variance into generalization guarantees. The paper applies this principle to POEM and identifies extensions for broader feedback and modeling assumptions.
- CRM expands the hypothesis class to stochastic policies, accounts for risk-estimator variance, and derives a data-dependent regularizer for robust learning.The resulting generalization bound guides hypothesis selection within the expanded policy space.
- POEM applies CRM to structured output prediction, optimizing rich exponential-model policy families and massive output spaces as efficiently as classical supervised methods.
- CRM also applies to supervised learning with non-differentiable losses because its objective does not require loss gradients.
- The paper identifies extensions involving noisy δ(·, ·), ordinal or coactive feedback, and adaptive h0 assumptions.