Bandit Algorithms

2020/07/04 by Tor Lattimore, Csaba Szepesvári · 113 citations
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #Machine Learning and Algorithms #Optimization and Search Problems

paper · doi:10.1017/9781108571401

openalex publication_date 2020/07/04 · openalex created_date 2022/01/25 · openalex updated_date 2026/07/30

Abstract

Decision-making in the face of uncertainty is a significant challenge in machine learning, and the multi-armed bandit model is a commonly used framework to address it. This comprehensive and rigorous introduction to the multi-armed bandit problem examines all the major settings, including stochastic, adversarial, and Bayesian frameworks. A focus on both mathematical intuition and carefully worked proofs makes this an excellent reference for established researchers and a helpful resource for graduate students in computer science, engineering, statistics, applied mathematics and economics. Linear bandits receive special attention as one of the most useful models in applications, while other chapters are dedicated to combinatorial bandits, ranking, non-stationary problems, Thompson sampling and pure exploration. The book ends with a peek into the world beyond bandits with an introduction to partial monitoring and learning in Markov decision processes.

Citations

• A Stochastic Model with Applications to Learning
• Zur Theorie der Gesellschaftsspiele
• The Nonstochastic Multiarmed Bandit Problem
• Minimal Exploration in Structured Stochastic Bandits
• Information Directed Sampling and Bandits with Heteroscedastic Noise
• Generalized Linear Models
• Prospect Theory: An Analysis of Decision under Risk
• Time Discounting and Time Preference: A Critical Review

Cited by

• Self-Configurable Mesh-Networks for Scalable Distributed Submodular Bandit Optimization
• Online Learning in the Random Order Model
• TabImpute: Universal Zero-Shot Imputation for Tabular Data
• Performative Learning Theory
• Greedy Sampling Is Provably Efficient for RLHF
• Count Counts: Motivating Exploration in LLM Reasoning with Count-based Intrinsic Rewards
• Sparse Optimistic Information Directed Sampling
• Self-Concordant Perturbations for Linear Bandits
• Explore-then-Commit for Nonstationary Linear Bandits with Latent Dynamics
• Last Iterate Analyses of FTRL in Stochasitc Bandits
• UCB-type Algorithm for Budget-Constrained Expert Learning
• A Minimal-Assumption Analysis of Q-Learning with Time-Varying Policies
• Optimistic Task Inference for Behavior Foundation Models
• On Interaction Effects in Greybox Fuzzing
• Comparing Uniform Price and Discriminatory Multi-Unit Auctions through Regret Minimization
• No Intelligence Without Statistics: The Invisible Backbone of Artificial Intelligence
• Instance-Dependent Regret Bounds for Nonstochastic Linear Partial Monitoring
• Scalable LinUCB: Low-Rank Design Matrix Updates for Recommenders with Large Action Spaces
• Learning Peer Influence Probabilities with Linear Contextual Bandits
• Preference-based Reinforcement Learning beyond Pairwise Comparisons: Benefits of Multiple Options
• Physics-Informed Parametric Bandits for Beam Alignment in mmWave Communications
• Exploration via Feature Perturbation in Contextual Bandits
• Adapting to Stochastic and Adversarial Losses in Episodic MDPs with Aggregate Bandit Feedback
• Eliciting Truthful Feedback for Preference-Based Learning via the VCG Mechanism
• Online Mixture of Experts: No-Regret Learning for Optimal Collective Decision-Making
• Practical, Utilitarian Algorithm Configuration
• Multi-Armed Bandits with Minimum Aggregated Revenue Constraints
• Representation-Based Exploration for Language Models: From Test-Time to Post-Training
• Provable Anytime Ensemble Sampling Algorithms in Nonlinear Contextual Bandits
• PrediQL: Automated Testing of GraphQL APIs with LLMs
• Kernel Treatment Effects with Adaptively Collected Data
• Learning with Incomplete Context: Linear Contextual Bandits with Pretrained Imputation
• Bandits with Single-Peaked Preferences and Limited Resources
• A Frequency-Domain Analysis of the Multi-Armed Bandit Problem: A New Perspective on the Exploration-Exploitation Trade-off
• Regret Bounds for Adversarial Contextual Bandits with General Function Approximation and Delayed Feedback
• Rate optimal learning of equilibria from data
• Design-Based Bandits Under Network Interference: Trade-Off Between Regret and Statistical Inference
• Navigating Sparsities in High-Dimensional Linear Contextual Bandits
• Best-of-Both Worlds for linear contextual bandits with paid observations
• A Broader View of Thompson Sampling
• Risk level dependent Minimax Quantile lower bounds for Interactive Statistical Decision Making
• Rethinking Langevin Thompson Sampling from A Stochastic Approximation Perspective
• Fairness in Repeated Matching: A Maximin Perspective
• MUSE: Multi-Treatment Experiment Design for Winner Selection and Effect Estimation
• Trajectory Data Suffices for Statistically Efficient Policy Evaluation in Fixed-Horizon Offline RL with Linear q^π-Realizability and Concentrability
• Batched Bandits with Heavy-Tailed Rewards
• Cost Efficient Fairness Audit Under Partial Feedback
• Q-Learning with Shift-Aware Upper Confidence Bound in Non-Stationary Reinforcement Learning
• Beyond Softmax: A New Perspective on Gradient Bandits
• Best-of-Majority: Minimax-Optimal Strategy for Pass@k Inference Scaling
• Quantitative Convergence Analysis of Projected Stochastic Gradient Descent for Non-Convex Losses via the Goldstein Subdifferential
• A Control Theory inspired Exploration Method for a Linear Bandit driven by a Linear Gaussian Dynamical System
• Rectifying Regression in Reinforcement Learning
• MM-LMPC: Multi-Modal Learning Model Predictive Control via Bandit-Based Mode Selection
• Online Minimization of Polarization and Disagreement via Low-Rank Matrix Bandits
• Guiding Evolutionary Molecular Design: Adding Reinforcement Learning for Mutation Selection
• The Good, the Bad, and the Sampled: a No-Regret Approach to Safe Online Classification
• Sandbagging in a Simple Survival Bandit Problem
• When Greedy Wins: Emergent Exploitation Bias in Meta-Bandit LLM Training
• FedPOB: Sample-Efficient Federated Prompt Optimization via Bandits
• Towards Efficient Online Exploration for Reinforcement Learning with Human Feedback
• Learning from Delayed Feedback in Games via Extra Prediction
• Observation-Free Attacks on Online Learning to Rank
• Efficient Kernelized Learning in Polyhedral Games Beyond Full-Information: From Colonel Blotto to Congestion Games
• Non-Clairvoyant Scheduling with Progress Bars
• Identifying general reaction conditions by bandit optimization
• Asymptotically Optimal Problem-Dependent Bandit Policies for Transfer Learning
• KITE: Kernelized and Information Theoretic Exemplars for In-Context Learning
• Stochastic Sample Approximations of (Local) Moduli of Continuity
• High Effort, Low Gain: Fundamental Limits of Active Learning for Linear Dynamical Systems
• Human-in-the-loop Learning Through Decentralized Communication Mechanisms
• Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates
• The Keychain Problem: On Minimizing the Opportunity Cost of Uncertainty
• A Minimalist Bayesian Framework for Stochastic Optimization
• Beyond ATE: Multi-Criteria Design for A/B Testing
• Filtering with Randomised Observations: Sequential Learning of Relevant Subspace Properties and Accuracy Analysis
• Calibrated Recommendations with Contextual Bandits
• Using causal abstractions to accelerate decision-making in complex bandit problems
• Batched Stochastic Matching Bandits
• FraPPE: Fast and Efficient Preference-based Pure Exploration
• Online Learning of Optimal Sequential Testing Policies
• SharedRep-RLHF: A Shared Representation Approach to RLHF with Diverse Preferences
• Offline Contextual Bandit with Counterfactual Sample Identification
• Perturbing the Derivative: Wild Refitting for Model-Free Evaluation of Machine Learning Models under Bregman Losses
• Non-Linear Model-Based Sequential Decision-Making in Agriculture
• QueryBandits for Hallucination Mitigation: Exploiting Semantic Features for No-Regret Rewriting
• Context-Action Embedding Learning for Off-Policy Evaluation in Contextual Bandits
• Introduction to the Analysis of Probabilistic Decision-Making Algorithms
• Vector preference-based contextual bandits under distributional shifts
• Incentivized Lipschitz Bandits
• Recycling History: Efficient Recommendations from Contextual Dueling Bandits
• Efficient Best-of-Both-Worlds Algorithms for Contextual Combinatorial Semi-Bandits
• Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problems
• In-Context Decision Making for Optimizing Complex AutoML Pipelines
• Order Optimal Regret Bounds for Sharpe Ratio Optimization under Thompson Sampling
• Semantic Communication with Distribution Learning through Sequential Observations
• Low-Regret and Low-Complexity Learning for Hierarchical Inference
• Efficient Statistical Estimation for Sequential Adaptive Experiments with Implications for Adaptive Designs
• A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory
• The Fair Game: Auditing & Debiasing AI Algorithms Over Time
• Near-Optimal Regret for Efficient Stochastic Combinatorial Semi-Bandits
• A variational approach to dimension-free self-normalized concentration
• Stochastic Bandits for Crowdsourcing and Multi-Platform Autobidding
• Latent Preference Bandits
• Decoupling Understanding from Reasoning via Problem Space Mapping for Small-Scale Model Reasoning
• DP-NCB: Privacy Preserving Fair Bandits
• Achieving Limited Adaptivity for Multinomial Logistic Bandits
• ORVIT: Near-Optimal Online Distributionally Robust Reinforcement Learning
• Generalized Kernelized Bandits: A Novel Self-Normalized Bernstein-Like Dimension-Free Inequality and Regret Bounds
• Exploitation Is All You Need... for Exploration
• Learning to Optimize Feedback for One Million Students: Insights from Multi-Armed and Contextual Bandits in Large-Scale Online Tutoring
• Towards Heterogeneity-Aware and Energy-Efficient Topology Optimization for Decentralized Federated Learning in Edge Environment
• Designing Dynamic Pricing for Bike-sharing Systems via Differentiable Agent-based Simulation

Related

• Introduction to Multi-Armed Bandits
• Discrete Choice Multi-Armed Bandits
• Selective Reviews of Bandit Problems in AI via a Statistical View
• Forced Exploration in Bandit Problems
• A Frequency-Domain Analysis of the Multi-Armed Bandit Problem: A New Perspective on the Exploration-Exploitation Trade-off