Efficient Optimal Learning for Contextual Bandits

Abstract

We address the problem of learning in an online setting where the learner repeatedly observes features, selects among a set of actions, and receives reward for the action taken. We provide the first efficient algorithm with an optimal regret. Our algorithm uses a cost sensitive classification learner as an oracle and has a running time $\mathrm{polylog}(N)$, where $N$ is the number of classification rules among which the oracle might choose. This is exponentially faster than all previous algorithms that achieve optimal regret in this setting. Our formulation also enables us to create an algorithm with regret that is additive rather than multiplicative in feedback delay as in all previous work.

References in corpus (1)

• Contextual Bandit Algorithms with Supervised Learning Guarantees

Cited by in corpus (69)

• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Finite-Time Analysis of Kernelised Contextual Bandits
• Personalized Course Sequence Recommendations
• Parallelizing Exploration-Exploitation Tradeoffs with Gaussian Process Bandit Optimization
• BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits
• RecoGym: A Reinforcement Learning Environment for the problem of Product Recommendation in Online Advertising
• Distributed Online Learning in Social Recommender Systems
• Delay and Cooperation in Nonstochastic Bandits
• Forecasting Popularity of Videos using Social Media
• A Contextual Bandit Bake-off
• Contextual Bandit Learning with Predictable Rewards
• An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
• Efficient Algorithms for Adversarial Contextual Learning
• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Multi-objective Contextual Multi-armed Bandit with a Dominant Objective
• Sequential Batch Learning in Finite-Action Linear Contextual Bandits
• Online Learning under Delayed Feedback
• Adapting multi-armed bandits policies to contextual bandits scenarios
• RELEAF: An Algorithm for Learning and Exploiting Relevance
• A Practical Method for Solving Contextual Bandit Problems Using Decision Trees
• Stochastic Contextual Bandits with Known Reward Functions
• Improved Regret Bounds for Oracle-Based Adversarial Contextual Bandits
• Warm-starting Contextual Bandits: Robustly Combining Supervised and Bandit Feedback
• On component interactions in two-stage recommender systems
• Achieving Near Instance-Optimality and Minimax-Optimality in Stochastic and Adversarial Linear Bandits Simultaneously
• Upper Counterfactual Confidence Bounds: a New Optimism Principle for Contextual Bandits
• Taking a hint: How to leverage loss predictors in contextual bandits?
• Dialog State Tracking with Reinforced Data Augmentation
• Efficient Contextual Bandits with Continuous Actions
• Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
• Dynamic Pricing with Demand Covariates
• Provable Model-based Nonlinear Bandit and Reinforcement Learning: Shelve Optimism, Embrace Virtual Curvature
• Asymptotic Convergence in Online Learning with Unbounded Delays
• Bernstein-like Concentration and Moment Inequalities for Polynomials of Independent Random Variables: Multilinear Case
• Nonparametric Contextual Bandits in an Unknown Metric Space
• Adapting to Misspecification in Contextual Bandits with Offline Regression Oracles
• 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
• Multi-Armed Bandits with Fairness Constraints for Distributing Resources to Human Teammates
• Randomized Allocation with Nonparametric Estimation for Contextual Multi-Armed Bandits with Delayed Rewards
• Decentralized Online Big Data Classification - a Bandit Framework
• Efficient Online Learning of Optimal Rankings: Dimensionality Reduction via Gradient Descent
• Contextual Bandits with Stochastic Experts
• Decentralized Learning for Channel Allocation in IoT Networks over Unlicensed Bandwidth as a Contextual Multi-player Multi-armed Bandit Game
• Nonstochastic Multiarmed Bandits with Unrestricted Delays
• Tractable contextual bandits beyond realizability
• Doubly robust Thompson sampling for linear payoffs
• Bandit Multiclass Linear Classification: Efficient Algorithms for the Separable Case
• Learning to Scaffold the Development of Robotic Manipulation Skills
• The Computational Power of Optimization in Online Learning
• Cache Replacement as a MAB with Delayed Feedback and Decaying Costs
• A Dimension-free Algorithm for Contextual Continuum-armed Bandits
• Some performance considerations when using multi-armed bandit algorithms in the presence of missing data
• Personalized Advertisement Recommendation: A Ranking Approach to Address the Ubiquitous Click Sparsity Problem
• OFF-Set: One-pass Factorization of Feature Sets for Online Recommendation in Persistent Cold Start Settings
• Contextual Online Learning for Multimedia Content Aggregation
• Representation of Reinforcement Learning Policies in Reproducing Kernel Hilbert Spaces
• Efficient Online Bandit Multiclass Learning with $\tilde{O}(\sqrt{T})$ Regret
• Adversarial Linear Contextual Bandits with Graph-Structured Side Observations
• Nonstochastic Bandits and Experts with Arm-Dependent Delays
• DTR Bandit: Learning to Make Response-Adaptive Decisions With Low Regret
• To update or not to update? Delayed Nonparametric Bandits with Randomized Allocation
• Efficient and Optimal Algorithms for Contextual Dueling Bandits under Realizability
• Data-Driven Online Decision Making with Costly Information Acquisition
• Bandits with Stochastic Experts: Constant Regret, Empirical Experts and Episodes
• A Time and Space Efficient Algorithm for Contextual Linear Bandits
• Bandit Market Makers
• Sayer: Using Implicit Feedback to Optimize System Policies