A Contextual Bandit Bake-off

Abstract

Contextual bandit algorithms are essential for solving many real-world interactive machine learning problems. Despite multiple recent successes on statistically and computationally efficient methods, the practical behavior of these algorithms is still poorly understood. We leverage the availability of large numbers of supervised learning datasets to empirically evaluate contextual bandit algorithms, focusing on practical methods that learn by relying on optimization oracles from supervised learning. We find that a recent method (Foster et al., 2018) using optimism under uncertainty works the best overall. A surprisingly close second is a simple greedy baseline that only explores implicitly through the diversity of contexts, followed by a variant of Online Cover (Agarwal et al., 2014) which tends to be more conservative but robust to problem specification by design. Along the way, we also evaluate various components of contextual bandit algorithm design such as loss estimators. Overall, this is a thorough study and review of contextual bandit methodology.

JMLR

References in corpus (10)

• Doubly Robust Policy Evaluation and Learning
• Recommendations as Treatments: Debiasing Learning and Evaluation
• Efficient Optimal Learning for Contextual Bandits
• Bootstrapped Thompson Sampling and Deep Exploration
• Online Importance Weight Aware Updates
• Contextual Bandit Learning with Predictable Rewards
• Practical Contextual Bandits with Regression Oracles
• Active Learning for Cost-Sensitive Classification
• Thompson sampling with the online bootstrap
• Make the Minority Great Again: First-Order Regret Bound for Contextual Bandits

Cited by in corpus (23)

• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Adapting multi-armed bandits policies to contextual bandits scenarios
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• Warm-starting Contextual Bandits: Robustly Combining Supervised and Bandit Feedback
• On component interactions in two-stage recommender systems
• Confident Off-Policy Evaluation and Selection through Self-Normalized Importance Weighting
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• An Efficient Algorithm For Generalized Linear Bandit: Online Stochastic Gradient Descent and Thompson Sampling
• Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
• Efficient Contextual Bandits with Continuous Actions
• Generalized Linear Bandits with Local Differential Privacy
• Contextual Bandits for adapting to changing User preferences over time
• Open Bandit Dataset and Pipeline: Towards Realistic and Reproducible Off-Policy Evaluation
• Fatigue-Aware Ad Creative Selection
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy
• Blending Search and Discovery: Tag-Based Query Refinement with Contextual Reinforcement Learning
• Balanced Linear Contextual Bandits
• Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent
• Predicting next shopping stage using Google Analytics data for E-commerce applications
• AutoML for Contextual Bandits
• Programming by Rewards
• Rarely-switching linear bandits: optimization of causal effects for the real world
• Greedy Bandits with Sampled Context