Counterfactual Risk Minimization: Learning from Logged Bandit Feedback

Adith Swaminathan, Thorsten Joachims

Introduction

Most machine learning models thrive on "full-information" supervised data, where the "correct" label is known for every input. However, real-world systems—like search engines, recommendation algorithms, and ad platforms—generate bandit feedback. If a system shows a user Ad A and they don't click, we know Ad A was a miss, but we have no idea if they would have clicked Ad B or Ad C.

This paper introduces Counterfactual Risk Minimization (CRM), a novel framework for training machine learning models using logged data where only this partial feedback is available. By explicitly accounting for the variance of performance estimators, the authors develop the POEM algorithm, which significantly outperforms standard approaches in structured prediction tasks.

The Challenge of Bandit Feedback

Learning from logged bandit feedback is notoriously difficult because the data is both incomplete (we only see the outcome of the chosen action) and biased (the data distribution is skewed by the previous system's choices).

Researchers often use Inverse Propensity Scoring (IPS) to "unbias" this data. However, IPS estimators suffer from massive variance. If a new model wants to try an action that the old system rarely took, the importance weights explode. This leads to unstable learning, poor generalization, and a phenomenon the authors call "Propensity Over-fitting"—where the learner gravitates toward actions with high importance weights but low frequency in the logs, hallucinating high performance.

Methods: Counterfactual Risk Minimization

To solve the variance problem, the authors propose moving beyond simple unbiased estimation to the Counterfactual Risk Minimization (CRM) principle.

  1. Variance-Sensitive Bounds: The authors prove a new generalization error bound using empirical Bernstein inequalities. Unlike standard bounds, this formulation explicitly includes the variance of the loss estimator.
  2. The CRM Principle: Instead of just minimizing the estimated risk (like standard IPS), CRM minimizes the estimated risk plus a penalty based on the standard deviation of that estimate. This acts as a data-dependent regularizer, preventing the model from choosing actions that the logging policy didn't explore sufficiently.
  3. POEM (Policy Optimizer for Exponential Models): The authors apply CRM to linear models for structured prediction. Because the variance-penalized objective is non-convex, they use a Majorization-Minimization approach to create a differentiable surrogate for the variance term, allowing the model to be optimized efficiently via Stochastic Gradient Descent (SGD).

Experiments and Key Results

The authors evaluated their approach using a "Supervised-to-Bandit" conversion on four multi-label classification datasets (Scene, Yeast, TMC, and LYRL). They simulated bandit feedback by training a weak "logging policy" on a tiny fraction of the data, using it to select labels, and observing only the resulting Hamming loss.

  • Superior Generalization: Unbiasedness is not enough. The experiments demonstrated that POEM consistently and significantly outperformed the standard IPS approach across all datasets by avoiding propensity over-fitting.
  • Robustness: POEM successfully improved upon the logging policy even when that policy was extremely poor (trained on only 1% of the data) or nearly deterministic.
  • Computational Efficiency: By decomposing the objective, the stochastic version of POEM (POEM-S) reached high-quality solutions orders of magnitude faster than traditional batch methods, especially as the action space grew.

Limitations and Future Work

While CRM provides a robust framework for counterfactual learning, it has a few notable limitations:

  • Support Constraints: Counterfactual learning fundamentally requires that the logging policy had a non-zero probability of trying the actions the new model wants to take. If the logger never explored a specific region of the action space, CRM cannot learn about it.
  • Known Propensities: The method assumes exact knowledge of the probabilities used by the logging policy. In legacy systems, these propensities might not be recorded accurately and would need to be estimated.

Future directions suggested by the authors include extending the CRM framework to handle noisy feedback, ordinal feedback (such as ranking tasks), and adaptive logging policies that shift over time.

Summary updated

BibTeX
@inproceedings{swaminathan2015counterfactual,
  author = {Adith Swaminathan and Thorsten Joachims},
  title = {{Counterfactual Risk Minimization: Learning from Logged Bandit Feedback}},
  booktitle = {The Web Conference},
  year = {2015},
  doi = {10.1145/2740908.2742564},
}
Figure