Multi-Armed Bandits

Latest papers 332

48 papers in the last four weeks, up 109% on the four weeks before. 0.3% of all new papers.

Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries
Jun 7, 2026Linfeng Cao, Ming Shi, Ness B. ShroffMulti-Armed Bandits Combinatorial Multi-Armed Bandits
Department of Computer Science and Engineering, The Ohio State University · Department of Electrical Engineering, University at Buffalo · Department of Electrical and Computer Engineering, The Ohio State University
Cutting LLM Evaluation Costs with SySRs: A Bandit Algorithm that Provably Exploits Model Similarity
Jun 5, 2026Zifan Lyu, Chahine Nejma, Tobias Wegel +2Model Selection Multi-Armed Bandits
1ETH Zurich · 2Centrale Sup´elec · 3ENS de Cachan +1
Adaptive Learning Rates with Surrogate Probability for Follow-the-Perturbed-Leader
Jun 4, 2026Jongyeong Lee, Junya Honda, Shinji Ito +1Multi-Armed Bandits Adversarial Bandits
Korea Institute of Science and Technology · Kyoto University · RIKEN AIP +2
Mean-based algorithms: A lower bound and regret
Jun 3, 2026Julius Durmann, Amelie KleberMulti-Armed Bandits Regret Minimization
Technical University of Munich
Provably Reduced Sample Cost in Prior-Guided Hyperparameter Optimization
Jun 3, 2026Leona Hennig, Jasmin Brandt, Lukas Fehring +3Multi-Fidelity Optimization Multi-Armed Bandits
Institute of Artificial Intelligence Leibniz University Hanover, Germany · University of Bielefeld Bielefeld, Germany · Institute of Artificial Intelligence, Leibniz University Hanover & L3S Research Center Hanover, Germany
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
Two-Action Apple Tasting with Switching Costs
Jun 2, 2026Tommaso Cesari, Roberto ColomboniMulti-Armed Bandits Minimax Regret
School of Electrical Engineering and Computer Science University of Ottawa Ottawa, Canada · School of Mathematics University of Bristol Bristol, United Kingdom
Constraint-Enhanced Physical Search through Correlation Matching
Jun 2, 2026Song-Ju KimMulti-Armed Bandits RL Exploration
SOBIN Institute LLC, Kawanishi, Hyogo, Japan
Tree-Guided Identify-Then-Exploit: A Unified Framework of Best Arm Identification and Regret Minimization for Dueling Bandits
Jun 1, 2026Pu Wang, Yao-Xiang DingMulti-Armed Bandits Best-Arm Identification
State Key Lab of CAD&CG, Zhejiang University
Two-Fidelity Best-Action Identification for Stochastic Minimax Tree
Jun 1, 2026Peter Chen, Xi ChenMulti-Fidelity Optimization Multi-Armed Bandits
Department of Mathematics Columbia University · Stern School of Business New York University
MINTS: Minimalist Thompson Sampling
Jun 1, 2026Kaizheng WangThompson Sampling Multi-Armed Bandits
Department of IEOR and Data Science Institute, Columbia University.
SEArch: Optimistic Policy Selection Between Scene Noise and Drift for UAV Radar Search
May 31, 2026Noor Khial, Naram Mhaisen, Loay Ismail +1Multi-Armed Bandits Non-Stationary Bandits
College of Engineering, Qatar University, Qatar · Faculty of Electrical Engineering, Mathematics, and Computer Science, Delft University of Technology, The Netherlands
Bandit Simulation for Average Reward Inference
May 30, 2026Samya Praharaj, Chih-Yu Chang, Koulik Khamaru +1Multi-Armed Bandits Simulation-Based Inference
Rutgers University · Imperial College London
CUPID in the Model Zoo: Online Matchmaking for Selecting Your Dream LLM
May 30, 2026Son Nguyen, Xinyuan Liu, Ransalu SenanayakeMulti-Armed Bandits User Preference Modeling
School of Computing and Augmented Intelligence, Arizona State University, Tempe, United States of America
Online Packet Scheduling with Deadlines and Learning
May 30, 2026Gianmarco Genalti, Achraf Azize, Vianney PerchetCompetitive Analysis Multi-Armed Bandits
Politecnico di Milano · FairPlay Joint Team, CREST, ENSAE, IP Paris · FairPlay Joint Team, CREST, ENSAE, IP Paris, CRITEO AI Team
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
Structured Neuron Pruning in Deep Neural Networks Using Multi-Armed Bandits
May 29, 2026Salem Ameen, Sunil VaderaMulti-Armed Bandits Neural Network Compression
School of Science, Engineering and Environment, University of Salford, Salford, United Kingdom
Trajectory-Aware Best-Arm Identification for Local Search Allocation in Bayesian Optimization and Beyond
May 29, 2026Nobuo Namura, Sho TakemoriMulti-Armed Bandits Bayesian Optimization
Fujitsu Limited, Kawasaki, Japan.
Annealed Softmax Greedy in Many-Armed Bayesian Bandits
May 29, 2026William Overman, Mohsen BayatiMulti-Armed Bandits Exploration-Exploitation Tradeoff
Stanford University
Batched Stochastic Linear Bandits with 1-Bit Communication Constraints
May 29, 2026Ivan Lau, Daniel McMorrow, Kevin Jamieson +1Multi-Armed Bandits Minimax Regret
National University of Singapore · University of Washington
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
Instance-dependent Stochastic Lipschitz bandit
May 28, 2026Marius Potfer, Vianney PerchetMulti-Armed Bandits
Crest (Fairplay joint team), ENSAE · EDF R&D · Criteo AI Lab
Compute Allocation in Evolutionary Search: From Depth-Breadth to Multi-Armed Bandits
May 28, 2026Sixue Xing, Haoyu He, Kerui Wu +4Multi-Armed Bandits Evolutionary Optimization
University of Notre Dame · 2Northeastern University · University of Massachusetts Amherst +4
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 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
Cost of Structural Learning Under Censored Feedback: A Threshold-Bandit Approach
May 26, 2026Michael Ledford, William RegliMulti-Armed Bandits Multi-Agent Coordination
University of Maryland, College Park
Learning to Orchestrate Agents under Uncertainty
May 26, 2026Mary Chriselda Antony Oliver, Lan Jiang, Aaron Bundi Anampiu +3Multi-Armed Bandits Multi-Agent Orchestration
Department of Applied Mathematics and Theoretical Physics, University of Cambridge · Centre for Human-Inspired Artificial Intelligence, University of Cambridge · African Institute for Mathematical Sciences, South Africa +1
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
On the Benefits of Free Exploration for Regret Minimization in Multi-Armed Bandits
May 25, 2026Yunlong Hou, Zixin Zhong, Vincent Y. F. TanMulti-Armed Bandits Regret Minimization
Department of Mathematics, National University of Singapore · Data Science and Analytics Thrust, Hong Kong University of Science and Technology (Guangzhou) · Department of Electrical and Computer Engineering, National University of Singapore
Optimal Design for Multinomial Logit Model with Applications to Best Assortment Identification
May 25, 2026Joongkyu Lee, Min-hwan OhMulti-Armed Bandits Discrete Choice Modeling
Seoul National University, Seoul, Korea.

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

Provably Efficient Personalized Multi-Objective Bandits with Proactive Conversational Queries

Linfeng Cao, Ming Shi, Ness B. Shroff

Department of Computer Science and Engineering, The Ohio State University · Department of Electrical Engineering, University at Buffalo · Department of Electrical and Computer Engineering, The Ohio State University

Multi-Armed Bandits Combinatorial Multi-Armed Bandits User Preference Modeling Preference Learning Preference Elicitation

Open paper AskPDF arXiv

Personalized decision-making in multi-objective bandits requires learning user-specific trade-offs among competing objectives. Since arm utility depends on both unknown rewards and unknown preferences, existing methods infer preferences only from utility feedback, entangling preference learning with reward exploration. In practice, however, users often reveal their priorities through proactive conversational queries (e.g., "cheap and clean hotel"), yet this structured signal is not leveraged. We formalize a proactive query-based framework in which user queries provide structured preference signals. Modeling these signals via a Plackett-Luce subset choice model, we show that query-only learning is insufficient due to a fundamental shift-invariance barrier. To resolve this, we introduce MO-PQUCB, a hybrid algorithm that integrates query-based preference anchoring with bandit feedback through shift-invariant regularization and dual-exploration UCB. We prove that proactive queries accelerate preference estimation and yield improved regret scaling over prior preference-aware MO-MAB methods. Under corrupted queries, we further characterize statistical limits and design a robust estimator achieving near-optimal performance when the corruption is sparse. Experiments validate both theoretical and practical gains.