Contextual Bandits

Follow this topic Ask about this topic

Contextual bandits study how to choose an action using information about the current situation when feedback reveals the reward only for the action taken. Common approaches include linear and generalized linear models with UCB or Thompson sampling, alongside kernel, neural, and policy-based methods for richer reward patterns. Offline learning and evaluation, nonstationary or corrupted feedback, and constraints such as budgets, privacy, and safety extend these methods to settings including recommendation, pricing, and LLM routing. A central challenge is balancing exploration with reliable decisions when models are misspecified, feedback is sparse or delayed, and computational or operational costs matter.

Latest papers

152 papers20 papers in the last four weeks, up 150% on the four weeks before. 0.1% of all new papers.

Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces
Jun 26, 2026Joyanta Jyoti Mondal, Ibne Farabi Shihab, Anuj SharmaMulti-Armed Bandits Graph Bandits
Department of Computer and Information Sciences, University of Delaware, USA · Department of Computer Science, Iowa State University, USA · Department of Civil, Construction & Environmental Engineering, Iowa State University, USA
A Comparative Study of Bayesian Contextual Bandits for Real-Time Warehouse Sorter Optimization
Jun 22, 2026Tina Dongxu Li, Mouhacine Benosman, Ken Meszaros +1Contextual Bandits Warehouse Automation
Amazon.com, USA
Flow-Corrected Thompson Sampling for Non-Stationary Contextual Bandits
Jun 22, 2026AmirHossein Naghdi, Ali BaheriThompson Sampling Non-Stationary Bandits
Sharif University of Technology, Iran · Rochester Institute of Technology, USA
Counterfactual learning of new adaptive instructional policies using logged data
Jun 22, 2026Samuel Girard, Sein Minn, Amel Bouzeghoub +1Offline-to-Online Contextual Bandits Intelligent Tutoring Systems
SODA · Soda Team, Inria Saclay, Palaiseau, France · Pix, Paris, France +4
Statistical Inference for Misspecified Contextual Bandits
Jun 21, 2026Yongyi Guo, Ziping XuInverse Probability Weighting Adaptive Inference
Department of Statistics, University of Wisconsin–Madison · School of Data Science and Society, University of North Carolina at Chapel Hill
AdaPrivate-TS: Private Thompson Sampling for Contextual Bandits with Privacy Amplification
Jun 19, 2026Mohammadreza Riyazat, Eranga UkwattaThompson Sampling Differential Privacy
School of Engineering, University of Guelph, Guelph, ON, Canada.
Set Membership Estimation for Stochastic Linear Contextual Bandits
Jun 18, 2026Haonan Xu, Yingying LiMulti-Armed Bandits Contextual Bandits
The Grainger College of Engineering University of Illinois Urbana-Champaign Champaign, IL, 61801
Near-Optimal Stochastic Linear Bandits with Delay
Jun 15, 2026Ofir Schlisselberg, Mengxiao Zhang, Yishay MansourBandits with Delayed Feedback Contextual Bandits
Tel Aviv University · University of Iowa · Google Research
Contextual Bandits for Maximizing Stimulated Word-of-Mouth Rewards
Jun 13, 2026Ahmed Sayeed Faruk, Elena ZhelevaContextual Bandits
Department of Computer Science, University of Illinois at Chicago Chicago, IL, USA
Policy Regret for Embedding Model Routing: Contextual Bandits with Low-Rank Experts
Jun 12, 2026Yan Dai, Negin Golrezaei, Patrick JailletContextual Bandits Adversarial Bandits
Operations Research Center, MIT. · Sloan School of Management, MIT. · Department of EECS, MIT.
Efficient Multinomial Logistic Bandit via Frequent Directions
Jun 10, 2026Linzhe He, Yu-Jie Zhang, Sifan Yang +1Multi-Armed Bandits Contextual Bandits
State Key Laboratory of Novel Software Technology, Nanjing University, Nanjing 210023, China · School of Artificial Intelligence, Nanjing University, Nanjing 210023, China · Paul G. Allen School of Computer Science & Engineering, University of Washington, USA
Bandits for Efficient Experimentation: Adapting to Control Group, Preferences, and Context Drifts
Jun 8, 2026Udvas Das, Waris Radji, Debabrota Basu +1Multi-Armed Bandits Non-Stationary Bandits
Univ. Lille, Inria, CNRS, Centrale Lille, UMR 9189 – CRIStAL F-59000 Lille, France
Algorithm for Contextual Queueing Bandits with Rate-Optimal Queue Length Regret
Jun 8, 2026Seoungbin Bae, Dabeen LeeExploration-Exploitation Tradeoff Regret Minimization
Department of Industrial & Systems Engineering, KAIST · Department of Mathematical Sciences, Seoul National University
CANS: Accelerating Multiuser Collaborative Edge Inference via Cooperative Autodidactic NeuroSurgeon
Jun 8, 2026Zheshun Wu, Ziyang Zhang, Changyao Lin +2Edge Inference Contextual Bandits
School of Computer Science and Technology, Harbin Institute of Technology Shenzhen, Shenzhen 518055, China · NESLab, Politecnico di Milano, 39-20133 Milano, Italy · School of Computer Science and Technology, Harbin Institute of Technology, Harbin, Heilongjiang 150001, China +2
CAAL: Contextual Bandits based Online Hand-Craft Active Learning Strategy Selection
Jun 6, 2026Shao-An Yin, Jiacong Li, Tianpei Xie +3Active Learning Contextual Bandits
Department of Electrical and Computer Engineering, University of Minnesota, Twin Cities, USA · Jiacong Li, Tianpei Xie, Cecile Levasseur, and Wojciech Kowalinski are with Amazon.
Online Pandora's Box for Contextual LLM Cascading
Jun 5, 2026Alexandre Belloni, Yan Chen, Yehua WeiLLM Decision-Making LLM Routing
The Fuqua School of Business, Duke University
Online KL-Regularized Reinforcement Learning with Function Approximation under Misspecification
Jun 4, 2026Haoyang Hong, Zichen Wang, Quanquan Gu +1Regret Minimization in RL Reinforcement Learning
School of Electrical Engineering and Computer Science, Oregon State University · Department of Electrical and Computer Engineering and Coordinated Science Laboratory, University of Illinois Urbana-Champaign · Department of Computer Science, University of California, Los Angeles
Offline-to-Online Learning in Linear Bandits
Jun 3, 2026Kushagra Chandak, Toshinori Kitamura, Xiaoqi TanMulti-Armed Bandits Contextual Bandits
Department of Computing Science, University of Alberta, Canada
Decision-Focused On-Policy Learning for Contextual Linear Optimization with Partial Feedback
May 31, 2026Wyame Benslimane, Tinghan Ye, Pascal Van Hentenryck +1Predict-Then-Optimize Decision-Focused Learning
Department of Industrial Engineering and Operations Research University of California, Berkeley · H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology
Practical and Optimal Algorithm for Linear Contextual Bandits with Rare Parameter Updates
May 31, 2026Sanghoon Yu, Min-hwan OhBatched Bandits Contextual Bandits
Seoul National University, Seoul, Republic of Korea
Distributed GNEP Algorithms without Multiplier Sharing and Applications to Multi-Robot Coordination and Contextual Bandit-Based Active Learning
May 30, 2026Shao-An YinGame Theory Distributed Optimization
UNIVERSITY OF MINNESOTA
Variance-sensitive Thompson sampling for generalised linear bandits, revisited
May 29, 2026Tom Perneczky, Marc Abeille, David JanzThompson Sampling Multi-Armed Bandits
University of Oxford · Criteo AI Lab
Contextual Scalarisation Thompson Sampling for multi-objective decisions in public media
May 29, 2026Théo Maëtz, Luc Guillet, Andrea CavallaroThompson Sampling Recommender Systems
Radio Télévision Suisse, Geneva, Switzerland · EPFL, Lausanne, Switzerland
Certified Policy Optimisation for Nested Causal Bandits via PAC-Bayes Risk
May 28, 2026Tim Woydt, Paul-David ZuercherPAC-Bayesian Generalization Bounds Multi-Armed Bandits
ProdAxon · Department of Computer Science Technical University Darmstadt · Institute for Manufacturing Department of Engineering University of Cambridge
The Sample Complexity of Multiclass and Sparse Contextual Bandits
May 28, 2026Liad Erez, Fan Chen, Alon Cohen +4Combinatorial Semi-Bandits Contextual Bandits
1Tel Aviv University, Israel · 2Massachusetts Institute of Technology, USA · 3Google Research Tel Aviv, Israel +1
Adaptive Bandit Algorithms for Contextual Matching Markets
May 27, 2026Shiyun Lin, Simon Mauras, Vianney Perchet +1Multi-Armed Bandits Contextual Bandits
Center for Statistical Science, School of Mathematical Sciences, Peking University · INRIA, FairPlay Joint Team · CREST, ENSAE, IP Paris; Criteo AI lab, FairPlay Joint Team +1
Learning to Assign Prediction Tasks to Agents with Capacity Constraints
May 27, 2026Shang Wu, Saatvik Kher, Padhraic SmythLearning to Defer Contextual Bandits
Department of Computer Science University of California, Irvine Irvine, CA 92697, USA
Learning to target with network interference
May 27, 2026Xiaomeng Wang, Hamsa Bastani, Osbert Bastani +1Multi-Armed Bandits Contextual Bandits
Department of Statistics and Data Science, University of Pennsylvania · Operations, Information and Decisions Department, University of Pennsylvania · Department of Computer and Information Science, University of Pennsylvania
Linear and Neural Dueling Bandits with Delayed Feedback
May 26, 2026Xiangyi Wang, Pingchen Lu, Jie Mao +4Inverse Probability Weighting Multi-Armed Bandits
The Chinese University of Hong Kong, Shenzhen · The Chi- nese University of Hong Kong
Nonstationary Generalized Linear Bandits with Discounted Online Mirror Descent
May 25, 2026Joongkyu Lee, Min-hwan OhMulti-Armed Bandits Dynamic Regret Minimization
Seoul National University

Jun 26, 2026J/K move · Enter open · S save

Graph Dimensionality Reduction for Contextual Bandits: Structure-Specific Regret Bounds under Approximate Smoothness and Noisy Eigenspaces

Joyanta Jyoti Mondal, Ibne Farabi Shihab, Anuj Sharma

Department of Computer and Information Sciences, University of Delaware, USA · Department of Computer Science, Iowa State University, USA · Department of Civil, Construction & Environmental Engineering, Iowa State University, USA

Multi-Armed Bandits Graph Bandits Contextual Bandits Dimensionality Reduction Linear Contextual Bandits

Open paper AskPDF arXiv

Contextual bandits with graph-structured arms arise in recommendation, citation retrieval, and social advertising, where arms connected on a graph tend to share reward signal. Standard dimensionality reduction ignores this structure, inflating exploration cost by a factor of

d/k

. We propose GraphDR-LinUCB, which projects arm features onto the graph's low-frequency spectral subspace and runs linear UCB in the resulting

k

-dimensional space. We prove the first

\wtO(k\sqrt{T})

regret bound for spectral-projection-based contextual bandits, reducing dimension dependence from

d

k

; a perturbation argument extends this to noisy graphs, with an explicit penalty for reward-smoothness mismatch and graph-estimation error. Our central theoretical finding is that the high-frequency reward component need not incur a worst-case linear-in-

T

penalty: its actual cost depends on its realized impact along the played path, not on its total energy. A simple spectral comparison between subspaces (

Γ_k

) predicts which reducer wins on a given dataset, correctly calling five of six real-dataset outcomes without any fitted threshold. Across a synthetic benchmark and six real datasets (MovieLens, Amazon, LastFM, ogbn-arxiv, MIND), GraphDR-LinUCB reduces cumulative regret by

15\times

over full-dimensional LinUCB and outperforms competing graph-aware methods on five of six; the single failure is precisely where the graph's spectral subspace is misaligned with the reward.