Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
arXiv:1402.0555
Abstract
We present a new algorithm for the contextual bandit learning problem, where the learner repeatedly takes one of 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 oracle calls across all rounds, where 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 (5)
Cited by in corpus (133)
- A Study on Overfitting in Deep Reinforcement Learning
- Bandits with Knapsacks
- 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
- Resourceful Contextual Bandits
- Multi-objective Contextual Multi-armed Bandit with a Dominant Objective
- 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
- Deploying a Steered Query Optimizer in Production at Microsoft
- Provably Efficient Imitation Learning from Observation Alone
- Neural Contextual Bandits with Deep Representation and Shallow Exploration
- Stochastic Bandits with Context Distributions
- Non-stationary Reinforcement Learning without Prior Knowledge: An Optimal Black-box Approach
- Quantum exploration algorithms for multi-armed bandits
- 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
- Semiparametric Contextual Bandits
- Garbage In, Reward Out: Bootstrapping Exploration in Multi-Armed Bandits
- Warm-starting Contextual Bandits: Robustly Combining Supervised and Bandit Feedback
- New Insights into Bootstrapping for Bandits
- Top-K Off-Policy Correction for a REINFORCE Recommender System
- On component interactions in two-stage recommender systems
- Meta-Learning for Contextual Bandit Exploration
- Fair Contextual Multi-Armed Bandits: Theory and Experiments
- Fair Decisions Despite Imperfect Predictions
- Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
- OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
- Playing against Nature: causal discovery for decision making under uncertainty
- Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
- contextual: Evaluating Contextual Multi-Armed Bandit Problems in R
- Combinatorial Semi-Bandit in the Non-Stationary Environment
- 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
- Efficient Contextual Bandits with Continuous Actions
- A Smoothed Analysis of the Greedy Algorithm for the Linear Contextual Bandit Problem
- CAB: Continuous Adaptive Blending Estimator for Policy Evaluation and Learning
- Representation Learning for Online and Offline RL in Low-rank MDPs
- On the Prior Sensitivity of Thompson Sampling
- Meta-Learning Bandit Policies by Gradient Ascent
- Multi-Objective Generalized Linear Bandits
- Deep Online Convex Optimization with Gated Games
- Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
- Empirical Likelihood for Contextual Bandits
- -Regret for Learning in Markov Decision Processes with Function Approximation and Low Bellman Rank
- ASAC: Active Sensing using Actor-Critic models
- Learning Optimal Interventions
- Efficient and Robust Algorithms for Adversarial Linear Contextual Bandits
- Top- eXtreme Contextual Bandits with Arm Hierarchy
- Online Pricing with Reserve Price Constraint for Personal Data Markets
- Watch the Unobserved: A Simple Approach to Parallelizing Monte Carlo Tree Search
- Nearly Dimension-Independent Sparse Linear Bandit over Small Action Spaces via Best Subset Selection
- Equal Opportunity in Online Classification with Partial Feedback
- Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles
- Information Directed Sampling for Sparse Linear Bandits
- Sublinear Optimal Policy Value Estimation in Contextual Bandits
- Stochastic Linear Contextual Bandits with Diverse Contexts
- Tractable contextual bandits beyond realizability
- Doubly robust Thompson sampling for linear payoffs
- ADARES: Adaptive Resource Management for Virtual Machines
- Deep Online Convex Optimization by Putting Forecaster to Sleep
- Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent
- Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case
- Online Preselection with Context Information under the Plackett-Luce Model
- Balanced Linear Contextual Bandits
- Contextual Bandits with Stochastic Experts
- PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison
- Upper Confidence Bounds for Combining Stochastic Bandits
- Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization
- Online Algorithm for Unsupervised Sequential Selection with Contextual Information
- Learning Individualized Treatment Rules with Estimated Translated Inverse Propensity Score
- The Computational Power of Optimization in Online Learning
- Accelerated learning from recommender systems using multi-armed bandit
- Adaptive ABAC Policy Learning: A Reinforcement Learning Approach
- Cost-Effective Incentive Allocation via Structured Counterfactual Inference
- Rate-adaptive model selection over a collection of black-box contextual bandit algorithms
- Learning to Use Learners' Advice
- Multidimensional Binary Search for Contextual Decision-Making
- Personalized Advertisement Recommendation: A Ranking Approach to Address the Ubiquitous Click Sparsity Problem
- Learning Accurate Decision Trees with Bandit Feedback via Quantized Gradient Descent
- Disagreement-Based Combinatorial Pure Exploration: Sample Complexity Bounds and an Efficient Algorithm
- Efficient Online Bandit Multiclass Learning with Regret
- Learning causal effects from many randomized experiments using regularized instrumental variables
- Provable RL with Exogenous Distractors via Multistep Inverse Dynamics
- Optimal Policies for the Homogeneous Selective Labels Problem
- Combining Online Learning and Offline Learning for Contextual Bandits with Deficient Support
- Off-policy Learning for Multiple Loggers
- Logarithmic Regret in Feature-based Dynamic Pricing
- Risk-Aware Algorithms for Adversarial Contextual Bandits
- Universal and data-adaptive algorithms for model selection in linear contextual bandits
- Learning Reductions that Really Work
- Boosting for Online Convex Optimization
- Beyond traditional assumptions in fair machine learning
- Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
- Incentivized Exploration for Multi-Armed Bandits under Reward Drift
- Improving Offline Contextual Bandits with Distributional Robustness
- Learning to Bid Without Knowing your Value
- Contributions to Representation Learning with Graph Autoencoders and Applications to Music Recommendation
- Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability
- Pyramid: Enhancing Selectivity in Big Data Protection with Count Featurization
- Online Learning for Measuring Incentive Compatibility in Ad Auctions
- Random Forest for the Contextual Bandit Problem - extended version
- Modeling and Optimization of Human-machine Interaction Processes via the Maximum Entropy Principle
- Enhancing Evolutionary Conversion Rate Optimization via Multi-armed Bandit Algorithms
- Learning to Actively Learn: A Robust Approach
- DTR Bandit: Learning to Make Response-Adaptive Decisions With Low Regret
- CBA: Contextual Quality Adaptation for Adaptive Bitrate Video Streaming (Extended Version)
- Parallel Contextual Bandits in Wireless Handover Optimization
- The Assistive Multi-Armed Bandit