Multi-Armed Bandits

Follow this topic Ask about this topic

Latest papers 332

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

All topics

How Log-Barrier Helps Exploration in Policy Optimization
Mar 16, 2026Leonardo Cesani, Matteo Papini, Marcello RestelliRL Exploration Policy Gradient Methods
Politecnico di Milano, Milan, Italy · Università degli Studi di Milano, Milan, Italy
Few Batches or Little Memory, But Not Both: Simultaneous Space and Adaptivity Constraints in Stochastic Bandits
Mar 14, 2026Ruiyuan Huang, Zicheng Lyu, Xiaoyi Zhu +1Multi-Armed Bandits Minimax Regret
School of Data Science, Fudan University · School of Data Science, Fudan University Shanghai Innovation Institute
Batched Kernelized Bandits: Refinements and Extensions
Mar 13, 2026Chenkai Ma, Keqin Chen, Jonathan ScarlettBlack-Box Optimization Multi-Armed Bandits
National University of Singapore
A Further Efficient Algorithm with Best-of-Both-Worlds Guarantees for $m$ -Set Semi-Bandit Problem
Mar 12, 2026Botao Chen, Jongyeong Lee, Chansoo Kim +1Combinatorial Multi-Armed Bandits Adversarial Bandits
Department of Systems Science Graduate School of Informatics, Kyoto University Kyoto, Japan · Computational Science Research Center Korea Institute of Science and Technology Seoul, Korea · Computational Science Research Center Korea Institute of Science and Technology & University of Science and Technology Seoul, Korea +1
Exploiting Expertise of Non-Expert and Diverse Agents in Social Bandit Learning: A Free Energy Approach
Mar 12, 2026Erfan Mirzaei, Seyed Pooya Shariatpanahi, Alireza Tavakoli +2Multi-Armed Bandits Multi-Agent Reinforcement Learning
The authors are with the Cognitive Systems Lab., School of Electrical and Computer Engineering, College of Engineering, University of Tehran, Tehran, Iran.
On The Complexity of Best-Arm Identification in Non-Stationary Linear Bandits
Mar 11, 2026Leo Maynard-Zhang, Zhihan Xiong, Kevin Jamieson +1Multi-Armed Bandits Best-Arm Identification
University of Washington
A Diffusion Analysis of Policy Gradient for Stochastic Bandits
Mar 10, 2026Tor LattimoreMulti-Armed Bandits Policy Gradient
Google DeepMind
Stabilizing Bandits using Regularization: Precise Regret and A Quantitative Central Limit Theorem
Mar 10, 2026Budhaditya Halder, Ishan Sengupta, Koustav Chowdhury +2Multi-Armed Bandits Algorithmic Stability
Department of Statistics, Rutgers University · Indian Statistical Institute, Kolkata
Rigidity in LLM Bandits with Implications for Human-AI Dyads
Mar 8, 2026Haomiaomiao Wang, Tomás E Ward, Lili ZhangLLM Decision-Making Language Model Bias Evaluation
Insight Research Ireland Centre for Data Analytics, Ireland · School of Computing, Dublin City University, Ireland
Adapter-Augmented Bandits for Online Multi-Constrained Multi-Modal Inference Scheduling
Mar 6, 2026Xianzhi Zhang, Yue Xu, Yinlin Zhu +4LLM Inference Scheduling Multi-Armed Bandits
School of Computer Science and Engineering, Sun Yat-sen University, Guangzhou, 510006, China · School of Computing, Macquarie University, NSW 2109, Australia
Design Experiments to Compare Multi-armed Bandit Algorithms
Mar 6, 2026Huiling Meng, Ningyuan Chen, Xuefeng GaoMulti-Armed Bandits
Department of Systems Engineering and Engineering Management, The Chinese University of Hong Kong, Hong Kong, China. · Rotman School of Management, University of Toronto, Toronto, Canada.
Autocorrelation effects in a stochastic-process model for solving two-armed bandit problems
Mar 5, 2026Tomoki Yamagami, Mikio Hasegawa, Takatomo Mihana +2Multi-Armed Bandits
Department of Information and Computer Sciences, Saitama University, 255 Shimo-Okubo, Sakura-ku, Saitama City, Saitama 338–8570, Japan. · Department of Electrical Engineering, Tokyo University of Science, 6–3–1, Niijuku, Katsushika-ku, Tokyo 125–8585, Japan. · Department of Information Physics and Computing, The University of Tokyo, 7–3–1 Hongo, Bunkyo-ku, Tokyo 113–8656, Japan.
Fixed-Budget Constrained Best Arm Identification in Grouped Bandits
Mar 4, 2026Raunak Mukherjee, Sharayu MoharirBest-Arm Identification Multi-Armed Bandits
Indian Institute of Technology, Bombay · Dept. of Electrical Engineering, IIT Bombay
Invariance-Based Dynamic Regret Minimization
Mar 4, 2026Margherita Lazzaretto, Jonas Peters, Niklas PfisterNon-Stationary Bandits Linear Contextual Bandits
University of Copenhagen · ETH Zürich · Lakera Zürich
Near-Optimal Regret for KL-Regularized Multi-Armed Bandits
Mar 2, 2026Kaixuan Ji, Qingyue Zhao, Heyang Zhao +2Multi-Armed Bandits KL-Regularized RL
Department of Computer Science, University of California, Los Angeles, CA 90095, USA
Stochastic Multi-Armed Bandits with Limited Control Variates
Mar 2, 2026Arun Verma, Manjesh Kumar Hanawal, Arun RajkumarMulti-Armed Bandits UCB Algorithms
Singapore-MIT Alliance for Research and Technology Centre · Department of IEOR, Indian Institute of Technology Bombay · Department of DSAI, Indian Institute of Technology Madras
PARWiS: Winner determination under shoestring budgets using active pairwise comparisons
Mar 1, 2026Shailendra BhandariPairwise Preference Learning Pairwise Comparison
Department of Computer Science OsloMet– Oslo Metropolitan University Oslo, Norway
Lookahead identification in adversarial bandits: accuracy and memory bounds
Feb 28, 2026Nataly Brukhim, Nicolò Cesa-Bianchi, Carlo CilibertoMulti-Armed Bandits Adversarial Bandits
DIMACS, Rutgers University · Institute for Advanced Study · Universit`a degli Studi di Milano +3
Learning with a Budget: Identifying the Best Arm with Resource Constraints
Feb 27, 2026Zitian Li, Wang Chi CheungBest-Arm Identification Multi-Armed Bandits
Department of Industrial Systems Engineering & Management, National University of Singapore, Singapore
Sustainable Multi-Agent Crowdsourcing via Physics-Informed Bandits
Feb 25, 2026Chayan BanerjeeMulti-Armed Bandits Robust Multi-Armed Bandits
School of Electrical Engineering and Robotics, Queensland University of Technology (QUT), Brisbane, QLD, Australia.
Prior-Agnostic Incentive-Compatible Exploration
Feb 24, 2026Ramya Ramalingam, Osbert Bastani, Aaron RothMulti-Armed Bandits Regret Minimization
Department of Computer and Information Sciences, University of Pennsylvania
Box Thirding: Anytime Best Arm Identification under Insufficient Sampling
Feb 20, 2026Seohwa Hwang, Junyong ParkBest-Arm Identification Multi-Armed Bandits
Department of Statistics, Seoul National University, Seoul, Republic of Korea
Bayesian Online Model Selection
Feb 20, 2026Aida Afshar, Yuke Zhang, Aldo PacchianoModel Selection Multi-Armed Bandits
Boston University · Broad Institute of MIT and Harvard
Tighter Regret Lower Bound for Gaussian Process Bandits with Squared Exponential Kernel in Hypersphere
Feb 20, 2026Shogo IwazakiMinimax Regret Multi-Armed Bandits
LY Corporation, Tokyo, Japan
Flickering Multi-Armed Bandits
Feb 19, 2026Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1Multi-Armed Bandits Graph Bandits
University of Colorado Boulder, USA. · INRIA Paris, France.
Dynamic Decision-Making under Model Misspecification: A Stochastic Stability Approach
Feb 19, 2026Xinyu Dai, Daniel Chen, Yian QianThompson Sampling Model Misspecification
Department of Economics, Brown University. · Department of Applied Mathematics, Brown University.
Multi-Agent Lipschitz Bandits
Feb 18, 2026Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1Multi-Armed Bandits Multi-Agent Coordination
University of Colorado Boulder · INRIA Paris
Poisson-MNL Bandit: Nearly Optimal Dynamic Joint Assortment and Pricing with Decision-Dependent Customer Arrivals
Feb 18, 2026Junhui Cai, Ran Chen, Qitao Huang +2Assortment Optimization Dynamic Pricing
Department of Information Technology, Analytics, and Operations, University of Notre Dame · Department of Statistics and Data Science, Washington University in St. Louis · Department of Mathematics, Tsinghua University +2
Multi-Agent Combinatorial-Multi-Armed-Bandit framework for the Submodular Welfare Problem under Bandit Feedback
Feb 18, 2026Subham Pokhriyal, Shweta Jain, Vaneet AggarwalSubmodular Optimization Combinatorial Multi-Armed Bandits
Indian Institute of Technology Ropar, Rupnagar, India · Purdue University, West Lafayette, USA
Fast Online Learning with Gaussian Prior-Driven Hierarchical Unimodal Thompson Sampling
Feb 17, 2026Tianchi Zhao, He Liu, Hongyin Shi +1Multi-Armed Bandits Thompson Sampling
School of Intelligence Science and Technology, Beijing University Of Civil Engineering And Architecture, Beijing, 102616, China. · School of Economics and Management, Tsinghua University, Street, Beijing, 100084, China.

Mar 16, 2026J/K move · Enter open · S save

How Log-Barrier Helps Exploration in Policy Optimization

Leonardo Cesani, Matteo Papini, Marcello Restelli

Politecnico di Milano, Milan, Italy · Università degli Studi di Milano, Milan, Italy

RL Exploration Policy Gradient Methods Multi-Armed Bandits

Open paper AskPDF arXiv

Recently, it has been shown that the Stochastic Gradient Bandit (SGB) algorithm converges to a globally optimal policy with a constant learning rate. However, these guarantees rely on unrealistic assumptions about the learning process, namely that the probability of the optimal action is always bounded away from zero. We attribute this to the lack of an explicit exploration mechanism in SGB. To address these limitations, we propose to regularize the SGB objective with a log-barrier on the parametric policy, structurally enforcing a minimal amount of exploration. We prove that Log-Barrier Stochastic Gradient Bandit (LB-SGB) matches the sample complexity of SGB, but also converges (at a slower rate) without any assumptions on the learning process. We also show a connection between the log-barrier regularization and Natural Policy Gradient, as both exploit the geometry of the policy space by controlling the Fisher information. We validate our theoretical findings through numerical simulations, showing the benefits of the log-barrier regularization.