Contextual Bandit Algorithms with Supervised Learning Guarantees

Abstract

We address the problem of learning in an online, bandit setting where the learner must repeatedly select among $K$ actions, but only receives partial feedback based on its choices. We establish two new facts: First, using a new algorithm called Exp4.P, we show that it is possible to compete with the best in a set of $N$ experts with probability $1-\delta$ while incurring regret at most $O(\sqrt{KT\ln (N/\delta )})$ over $T$ time steps. The new algorithm is tested empirically in a large-scale, real-world dataset. Second, we give a new algorithm called VE that competes with a possibly infinite set of policies of VC-dimension $d$ while incurring regret at most $O(\sqrt{T(d\ln (T)+\ln (1/\delta ))})$ with probability $1-\delta$. These guarantees improve on those of all previous algorithms, whether in a stochastic or adversarial environment, and bring us closer to providing supervised learning type guarantees for the contextual bandit setting.

10 pages

References in corpus (1)

• A Contextual-Bandit Approach to Personalized News Article Recommendation

Cited by in corpus (85)

• Unbiased Offline Evaluation of Contextual-bandit-based News Article Recommendation Algorithms
• Taming the Monster: A Fast and Simple Algorithm for Contextual Bandits
• Fairness in Learning: Classic and Contextual Bandits
• Learning Representations for Counterfactual Inference
• Online Learning: A Comprehensive Survey
• Doubly Robust Policy Evaluation and Optimization
• Efficient Optimal Learning for Contextual Bandits
• Reinforcement and Imitation Learning via Interactive No-Regret Learning
• A Survey on Contextual Multi-armed Bandits
• Polylogarithmic width suffices for gradient descent to achieve arbitrarily small test error with shallow ReLU networks
• BISTRO: An Efficient Relaxation-Based Method for Contextual Bandits
• An efficient algorithm for contextual bandits with knapsacks, and an extension to concave objectives
• Model selection for contextual bandits
• A New Algorithm for Non-stationary Contextual Bandits: Efficient, Optimal, and Parameter-free
• Beyond UCB: Optimal and Efficient Contextual Bandits with Regression Oracles
• Resourceful Contextual Bandits
• Learning Adversarial MDPs with Bandit Feedback and Unknown Transition
• Logistic Regression: The Importance of Being Improper
• Latent Contextual Bandits and their Application to Personalized Recommendations for New Users
• Preference-based Online Learning with Dueling Bandits: A Survey
• Unified Models of Human Behavioral Agents in Bandits, Contextual Bandits and RL
• Stochastic Linear Optimization with Adversarial Corruption
• Explore no more: Improved high-probability regret bounds for non-stochastic bandits
• Quantum exploration algorithms for multi-armed bandits
• Power Constrained Bandits
• Agnostic Learning of a Single Neuron with Gradient Descent
• A High Probability Analysis of Adaptive SGD with Momentum
• On Convergence and Generalization of Dropout Training
• Better Algorithms for Stochastic Bandits with Adversarial Corruptions
• PAC-Bayes-Bernstein Inequality for Martingales and its Application to Multiarmed Bandits
• Minimax Regret for Stochastic Shortest Path with Adversarial Costs and Known Transition
• Semiparametric Contextual Bandits
• Graphical Models for Bandit Problems
• Learning to Optimize Via Posterior Sampling
• Warm-starting Contextual Bandits: Robustly Combining Supervised and Bandit Feedback
• Importance weighting without importance weights: An efficient algorithm for combinatorial semi-bandits
• Convergence and Margin of Adversarial Training on Separable Data
• Efficient First-Order Contextual Bandits: Prediction, Allocation, and Triangular Discrimination
• Corruption-Tolerant Gaussian Process Bandit Optimization
• An Analysis of the Value of Information when Exploring Stochastic, Discrete Multi-Armed Bandits
• OSOM: A simultaneously optimal algorithm for multi-armed and linear contextual bandits
• Taking a hint: How to leverage loss predictors in contextual bandits?
• Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation
• Contextual Blocking Bandits
• Smooth Contextual Bandits: Bridging the Parametric and Non-differentiable Regret Regimes
• Neural Network Retraining for Model Serving
• Parallelizing Thompson Sampling
• Finding the Stochastic Shortest Path with Low Regret: The Adversarial Cost and Unknown Transition Case
• Stochastic bandits robust to adversarial corruptions
• The K-Nearest Neighbour UCB algorithm for multi-armed bandits with covariates
• Top-$k$ eXtreme Contextual Bandits with Arm Hierarchy
• A Model Selection Approach for Corruption Robust Reinforcement Learning
• Nonparametric Contextual Bandits in an Unknown Metric Space
• Equal Opportunity in Online Classification with Partial Feedback
• Upper Confidence Bounds for Combining Stochastic Bandits
• PAC-Bayes Bounds for Bandit Problems: A Survey and Experimental Comparison
• Agnostic Learning of Halfspaces with Gradient Descent via Soft Margins
• Contextual Bandits with Stochastic Experts
• Sample-efficient Nonstationary Policy Evaluation for Contextual Bandits
• Tractable contextual bandits beyond realizability
• Design of Experiments for Stochastic Contextual Linear Bandits
• Probabilistic Sequential Shrinking: A Best Arm Identification Algorithm for Stochastic Bandits with Corruptions
• ADARES: Adaptive Resource Management for Virtual Machines
• Stochastic Linear Contextual Bandits with Diverse Contexts
• Active Hybrid Classification
• Learning to Use Learners' Advice
• An Optimal Reduction of TV-Denoising to Adaptive Online Learning
• Policy Optimization in Adversarial MDPs: Improved Exploration via Dilated Bonuses
• A Bandit Model for Human-Machine Decision Making with Private Information and Opacity
• Cache Replacement as a MAB with Delayed Feedback and Decaying Costs
• Decision Making Problems with Funnel Structure: A Multi-Task Learning Approach with Application to Email Marketing Campaigns
• Online Algorithm for Unsupervised Sequential Selection with Contextual Information
• Measurable Monte Carlo Search Error Bounds
• Confidence-Budget Matching for Sequential Budgeted Learning
• Cooperative Stochastic Multi-agent Multi-armed Bandits Robust to Adversarial Corruptions
• Information-gain computation
• Risk-Aware Algorithms for Adversarial Contextual Bandits
• Efficient Online-Bandit Strategies for Minimax Learning Problems
• Minimax Optimal Algorithms for Adversarial Bandit Problem with Multiple Plays
• DTR Bandit: Learning to Make Response-Adaptive Decisions With Low Regret
• Learning the Truth From Only One Side of the Story
• A Map of Bandits for E-commerce
• Efficient Methods for Online Multiclass Logistic Regression
• Selective Harvesting over Networks
• A Time and Space Efficient Algorithm for Contextual Linear Bandits