Counterfactual Risk Minimization: Learning from Logged Bandit Feedback

Abstract

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.

arXiv comment10 pages

References in corpus (9)

• Scikit-learn: Machine Learning in Python
• A Contextual-Bandit Approach to Personalized News Article Recommendation
• Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Empirical Bernstein Bounds and Sample Variance Penalization
• Learning from Logged Implicit Exploration Data
• Exploration vs Exploitation vs Safety: Risk-averse Multi-Armed Bandits
• Counterfactual Estimation and Optimization of Click Metrics for Search Engines
• Improving offline evaluation of contextual bandit algorithms via bootstrapping techniques

Cited by in corpus (55)

• Unbiased Learning to Rank with Unbiased Propensity Estimation
• KuaiRec: A Fully-observed Dataset and Insights for Evaluating Recommender Systems
• KuaiRand: An Unbiased Sequential Recommendation Dataset with Randomly Exposed Videos
• What is the Effect of Importance Weighting in Deep Learning?
• Alleviating Matthew Effect of Offline Reinforcement Learning in Interactive Recommendation
• To Model or to Intervene: A Comparison of Counterfactual and Online Learning to Rank from User Interactions
• Generalization Bounds and Representation Learning for Estimation of Potential Outcomes and Causal Effects
• A Survey on Causal Inference
• Benchmarks for Deep Off-Policy Evaluation
• Model Inversion Networks for Model-Based Optimization
• CoinDICE: Off-Policy Confidence Interval Estimation
• Evaluating stochastic seeding strategies in networks
• Doubly robust off-policy evaluation with shrinkage
• Understanding the role of importance weighting for deep learning
• Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weighting
• Rebounding Bandits for Modeling Satiation Effects
• Causality and Batch Reinforcement Learning: Complementary Approaches To Planning In Unknown Domains
• Fair Decisions Despite Imperfect Predictions
• More robust estimation of sample average treatment effects using Kernel Optimal Matching in an observational study of spine surgical interventions
• Conservative Exploration in Reinforcement Learning
• Ad-load Balancing via Off-policy Learning in a Content Marketplace
• Efficient Policy Learning from Surrogate-Loss Classification Reductions
• Efficient Contextual Bandits with Continuous Actions
• Imitation-Regularized Offline Learning
• Learning from Bandit Feedback: An Overview of the State-of-the-art
• Towards Optimal Problem Dependent Generalization Error Bounds in Statistical Learning Theory
• Improving Evolutionary Strategies with Generative Neural Networks
• Asymmetric Tri-training for Debiasing Missing-Not-At-Random Explicit Feedback
• Combining Offline Causal Inference and Online Bandit Learning for Data Driven Decision
• A Field Test of Bandit Algorithms for Recommendations: Understanding the Validity of Assumptions on Human Preferences in Multi-armed Bandits
• On the Value of Bandit Feedback for Offline Recommender System Evaluation
• Counterfactual Evaluation of Treatment Assignment Functions with Networked Observational Data
• Learning Individualized Treatment Rules with Estimated Translated Inverse Propensity Score
• Productization Challenges of Contextual Multi-Armed Bandits
• Semi-Parametric Efficient Policy Learning with Continuous Actions
• Learning Continuous Treatment Policy and Bipartite Embeddings for Matching with Heterogeneous Causal Effects
• Causal World Models by Unsupervised Deconfounding of Physical Dynamics
• Debiasing Samples from Online Learning Using Bootstrap
• Cost-Effective Incentive Allocation via Structured Counterfactual Inference
• Human-AI Collaboration with Bandit Feedback
• A General Framework for Pairwise Unbiased Learning to Rank
• Control Variates for Slate Off-Policy Evaluation
• Off-policy Learning for Multiple Loggers
• A framework for massive scale personalized promotion
• Privacy-Preserving Causal Inference via Inverse Probability Weighting
• Beyond traditional assumptions in fair machine learning
• The Label Complexity of Active Learning from Observational Data
• Learning Robust Decision Policies from Observational Data
• Counterfactual Adversarial Learning with Representation Interpolation
• Improved Algorithms for Conservative Exploration in Bandits
• Learning Pareto-Efficient Decisions with Confidence
• Ranking metrics on non-shuffled traffic
• Bandits with Temporal Stochastic Constraints
• An Empirical Analysis on Transparent Algorithmic Exploration in Recommender Systems
• Offline Contextual Bandits with Overparameterized Models