Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits

Abstract

We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of $K$ actions in response to the observed context, and observes the reward only for that chosen action. Our method assumes access to an oracle for solving fully supervised cost-sensitive classification problems and achieves the statistically optimal regret guarantee with only $\tilde{O}(\sqrt{KT/\log N})$ oracle calls across all $T$ rounds, where $N$ is the number of policies in the policy class we compete against. By doing so, we obtain the most practical contextual bandit learning algorithm amongst approaches that work for general policy classes. We further conduct a proof-of-concept experiment which demonstrates the excellent computational and prediction performance of (an online variant of) our algorithm relative to several baselines.

References in corpus (2)

• Doubly Robust Policy Evaluation and Learning
• Efficient Optimal Learning for Contextual Bandits

Cited by in corpus (132)

• A Study on Overfitting in Deep Reinforcement Learning
• Fairness in Learning: Classic and Contextual Bandits
• Counterfactual Risk Minimization: Learning from Logged Bandit Feedback
• A Survey on Contextual Multi-armed Bandits
• Making Contextual Decisions with Low Technical Debt
• Causal Bandits: Learning Good Interventions via Causal Inference
• Algorithms with Logarithmic or Sublinear Regret for Constrained Contextual Bandits
• Nearly Minimax-Optimal Regret for Linearly Parameterized Bandits
• Linear Contextual Bandits with Knapsacks
• A Survey of Online Experiment Design with the Stochastic Multi-Armed Bandit
• A Contextual Bandit Bake-off
• An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
• Practical Contextual Bandits with Regression Oracles
• Model selection for contextual bandits
• Efficient Algorithms for Adversarial Contextual Learning
• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• FLAMBE: Structural Complexity and Representation Learning of Low Rank MDPs
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Multi-objective Contextual Multi-armed Bandit with a Dominant Objective
• Resourceful Contextual Bandits
• Latent Contextual Bandits and their Application to Personalized Recommendations for New Users
• Bellman Eluder Dimension: New Rich Classes of RL Problems, and Sample-Efficient Algorithms
• Adapting multi-armed bandits policies to contextual bandits scenarios
• Learning nonlinear dynamical systems from a single trajectory
• Contextual Dueling Bandits
• Instance-Dependent Complexity of Contextual Bandits and Reinforcement Learning: A Disagreement-Based Perspective
• A Practical Method for Solving Contextual Bandit Problems Using Decision Trees
• Provably Efficient Imitation Learning from Observation Alone
• Deploying a Steered Query Optimizer in Production at Microsoft
• Neural Contextual Bandits with Deep Representation and Shallow Exploration
• Stochastic Bandits with Context Distributions
• Quantum exploration algorithms for multi-armed bandits
• Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
• Optimal No-regret Learning in Repeated First-price Auctions
• Stochastic Contextual Bandits with Known Reward Functions
• BubbleRank: Safe Online Learning to Re-Rank via Implicit Click Feedback
• Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits
• Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits
• Semiparametric Contextual Bandits
• Warm-starting Contextual Bandits: Robustly Combining Supervised and Bandit Feedback
• On component interactions in two-stage recommender systems
• New Insights into Bootstrapping for Bandits
• Top-K Off-Policy Correction for a REINFORCE Recommender System
• Meta-Learning for Contextual Bandit Exploration
• Fair Contextual Multi-Armed Bandits: Theory and Experiments
• Fair Decisions Despite Imperfect Predictions
• Combinatorial Semi-Bandit in the Non-Stationary Environment
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• contextual: Evaluating Contextual Multi-Armed Bandit Problems in R
• Playing against Nature: causal discovery for decision making under uncertainty
• Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Taking a hint: How to leverage loss predictors in contextual bandits?
• Contextual Blocking Bandits
• Corralling a Band of Bandit Algorithms
• A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem
• Efficient Contextual Bandits with Continuous Actions
• On the Prior Sensitivity of Thompson Sampling
• Empirical Likelihood for Contextual Bandits
• Representation Learning for Online and Offline RL in Low-rank MDPs
• Multi-Objective Generalized Linear Bandits
• CAB: Continuous Adaptive Blending Estimator for Policy Evaluation and Learning
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Deep Online Convex Optimization with Gated Games
• Meta-Learning Bandit Policies by Gradient Ascent
• Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles
• Equal Opportunity in Online Classification with Partial Feedback
• ASAC: Active Sensing using Actor-Critic models
• Learning Optimal Interventions
• Online Pricing with Reserve Price Constraint for Personal Data Markets
• Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy
• Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Search
• Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
• $\sqrt{n}$-Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
• Contextual Bandits with Stochastic Experts
• Tractable contextual bandits beyond realizability
• PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison
• Information Directed Sampling for Sparse Linear Bandits
• Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent
• ADARES: Adaptive Resource Management for Virtual Machines
• Upper Confidence Bounds for Combining Stochastic Bandits
• Sublinear Optimal Policy Value Estimation in Contextual Bandits
• Doubly robust Thompson sampling for linear payoffs
• Online Preselection with Context Information under the Plackett-Luce Model
• Stochastic Linear Contextual Bandits with Diverse Contexts
• Balanced Linear Contextual Bandits
• Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case
• Deep Online Convex Optimization by Putting Forecaster to Sleep
• Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
• Accelerated learning from recommender systems using multi-armed bandit
• Multidimensional Binary Search for Contextual Decision-Making
• Online Algorithm for Unsupervised Sequential Selection with Contextual Information
• Cost-Effective Incentive Allocation via Structured Counterfactual Inference
• Rate-adaptive model selection over a collection of black-box contextual bandit algorithms
• Learning Individualized Treatment Rules with Estimated Translated Inverse Propensity Score
• Learning to Use Learners' Advice
• Adaptive ABAC Policy Learning: A Reinforcement Learning Approach
• Personalized Advertisement Recommendation: A Ranking Approach to Address the Ubiquitous Click Sparsity Problem
• Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent
• The Computational Power of Optimization in Online Learning
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
• Beyond traditional assumptions in fair machine learning
• Boosting for Online Convex Optimization
• Incentivized Exploration for Multi-Armed Bandits under Reward Drift
• Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm
• Risk-Aware Algorithms for Adversarial Contextual Bandits
• Efficient Online Bandit Multiclass Learning with $\tilde{O}(\sqrt{T})$ Regret
• Learning causal effects from many randomized experiments using regularized instrumental variables
• Universal and data-adaptive algorithms for model selection in linear contextual bandits
• Provable RL with Exogenous Distractors via Multistep Inverse Dynamics
• Learning Reductions that Really Work
• Off-policy Learning for Multiple Loggers
• Combining Online Learning and Offline Learning for Contextual Bandits with Deficient Support
• Optimal Policies for the Homogeneous Selective Labels Problem
• Logarithmic Regret in Feature-based Dynamic Pricing
• Improving Offline Contextual Bandits with Distributional Robustness
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability
• Enhancing Evolutionary Conversion Rate Optimization via Multi-armed Bandit Algorithms
• Random Forest for the Contextual Bandit Problem - extended version
• DTR Bandit: Learning to Make Response-Adaptive Decisions With Low Regret
• Modeling and Optimization of Human-machine Interaction Processes via the Maximum Entropy Principle
• Learning to Bid Without Knowing your Value
• Pyramid: Enhancing Selectivity in Big Data Protection with Count Featurization
• Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
• CBA: Contextual Quality Adaptation for Adaptive Bitrate Video Streaming (Extended Version)
• Parallel Contextual Bandits in Wireless Handover Optimization
• The Assistive Multi-Armed Bandit
• Learning to Actively Learn: A Robust Approach
• Online Learning for Measuring Incentive Compatibility in Ad Auctions