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

Replicable Bandits with UCB based Exploration
Apr 21, 2026Rohan Deb, Udaya Ghai, Karan Singh +1Multi-Armed Bandits Contextual Bandits
University of Illinois Urbana-Champaign · Amazon · Carnegie Mellon University
Optimal Exploration of New Products under Assortment Decisions
Apr 20, 2026Jackie Baek, Atanas Dinev, Thodoris LykourisMulti-Armed Bandits E-Commerce
Stern School of Business, New York University · Massachusetts Institute of Technology
Spectral bandits for smooth graph functions
Apr 20, 2026Michal Valko, Rémi Munos, Branislav Kveton +1Graph Signal Processing Multi-Armed Bandits
INRIA Lille - Nord Europe, SequeL team, 40 avenue Halley 59650, Villeneuve d’Ascq, France · INRIA Lille - Nord Europe, SequeL team, France · Microsoft Research New England, Cambridge, MA, USA +1
DORA Explorer: Improving the Exploration Ability of LLMs Without Training
Apr 19, 2026Priya Gurjar, Md Farhan Ishmam, Kenneth MarinoMulti-Armed Bandits LLM Agents
Kahlert School of Computing, University of Utah
Multi-User mmWave Beam and Rate Adaptation via Combinatorial Satisficing Bandits
Apr 16, 2026Emre Özyıldırım, Barış Yaycı, Umut Eren Akturk +1Multi-Armed Bandits Wireless Communications
Department of Electrical and Electronics Engineering, Bilkent University, Ankara, Türkiye
Regret Tail Characterization of Optimal Bandit Algorithms with Generic Rewards
Apr 16, 2026Subhodip Panda, Shubhada AgrawalMulti-Armed Bandits UCB Algorithms
Department of ECE · Indian Institute of Science · Bangalore, India
Best of both worlds: Stochastic & adversarial best-arm identification
Apr 16, 2026Yasin Abbasi-Yadkori, Peter L. Bartlett, Victor Gabillon +2Multi-Armed Bandits Best-Arm Identification
Adobe Research, USA · University of California, Berkeley, USA · Queensland University of Technology - ACEMS, Australia +2
Covariance-adapting algorithm for semi-bandits with application to sparse rewards
Apr 15, 2026Pierre Perrault, Vianney Perchet, Michal ValkoMulti-Armed Bandits Combinatorial Multi-Armed Bandits
Inria Lille & ENS Paris-Saclay · ENSAE & Criteo AI Lab · DeepMind Paris
Analysis of Search Heuristics in the Multi-Armed Bandit Setting
Apr 9, 2026Jasmin Brandt, Barbara Hammer, Timo Kötzing +1Multi-Armed Bandits Exploration-Exploitation Tradeoff
University of Bielefeld Bielefeld, Germany · Hasso Plattner Institute University of Potsdam Potsdam, Germany
Are Stochastic Multi-objective Bandits Harder than Single-objective Bandits?
Apr 8, 2026Changkun Guan, Mengfan XuMulti-Armed Bandits
H. Milton Stewart School of Industrial and Systems Engineering, Georgia Institute of Technology · Mechanical and Industrial Engineering, University of Massachusetts Amherst
Restless Bandits with Individual Penalty Constraints: Near-Optimal Indices and Deep Reinforcement Learning
Apr 5, 2026Nida Zamir, I-Hong HouMulti-Armed Bandits Sequential Decision Making
Texas A&M University, College Station, Texas, USA
Nearly Optimal Best Arm Identification for Semiparametric Bandits
Apr 5, 2026Seok-Jin KimBest-Arm Identification Multi-Armed Bandits
Columbia University
Best-Arm Identification with Noisy Actuation
Apr 2, 2026Merve Karakas, Osama Hanna, Lin F. Yang +1Best-Arm Identification Multi-Armed Bandits
University of California, Los Angeles · Meta, Central Applied Science
RepUCB: Representation Learning-Based UCB for Heterogeneous Multi-Task Linear Bandits
Apr 1, 2026Jiabin Lin, Shana MoothedathMulti-Armed Bandits Multi-Task Learning
Department of Electrical and Computer Engineering, Iowa State University, USA
Lipschitz Dueling Bandits over Continuous Action Spaces
Apr 1, 2026Mudit Sharma, Shweta Jain, Vaneet Aggarwal +1Multi-Armed Bandits
Indian Institute of Technology Ropar · Purdue University · Indian Institute of Technology Hyderabad
Softmax gradient policy for variance minimization and risk-averse multi armed bandits
Mar 31, 2026Gabriel TuriniciMulti-Armed Bandits Policy Gradient Methods
CEREMADE, Université Paris Dauphine - PSL, CNRS, Paris, France
A Perturbation Approach to Unconstrained Linear Bandits
Mar 30, 2026Andrew Jacobsen, Dorian Baudry, Shinji Ito +1Adversarial Bandits Dynamic Regret Minimization
Università degli Studi di Milano · Politecnico di Milano · Inria, Univ. Grenoble Alpes, Grenoble INP, CNRS, LIG, 38000 Grenoble, France +1
An LP-based Sampling Policy for Multi-Armed Bandits with Side-Observations and Stochastic Availability
Mar 27, 2026Ashutosh Soni, Peizhong Ju, Atilla Eryilmaz +1Multi-Armed Bandits Graph Bandits
Department of Electrical and Computer Engineering, The Ohio State University, Columbus, Ohio, USA · Department of Computer Science, University of Kentucky, Lexington, Kentucky, USA · Department of Computer Science and Engineering, The Ohio State University, Columbus, Ohio, USA
Restless bandits with imperfect binary feedback: PCL-indexability analysis and computation
Mar 27, 2026José Niño-MoraMulti-Armed Bandits
Departamento de Estadística Universidad Carlos III de Madrid 28903 Getafe (Madrid), Spain
A Lyapunov Analysis of Softmax Policy Gradient for Stochastic Bandits
Mar 27, 2026Tor LattimoreMulti-Armed Bandits Policy Gradient
Google DeepMind
Parameter-Free Dynamic Regret for Unconstrained Linear Bandits
Mar 26, 2026Alberto Rumi, Andrew Jacobsen, Nicolò Cesa-Bianchi +1Dynamic Regret Minimization Adversarial Bandits
Intesa Sanpaolo Innovation Center
Mixture-Greedy for Online Generative Model Selection: Is UCB Necessary in Diversity-Aware Multi-Armed Bandits?
Mar 23, 2026Bahar Dibaei Nia, Farzan FarniaMulti-Armed Bandits Exploration-Exploitation Tradeoff
Department of Computer Science and Engineering, Chinese University of Hong Kong.
ALMAB-DC: Active Learning, Multi-Armed Bandits, and Distributed Computing for Sequential Experimental Design and Black-Box Optimization
Mar 22, 2026Foo Hui-Mean, Yuan-chin I ChangBayesian Optimization Bayesian Experimental Design
Institute of Statistical Science, Academia Sinica, Taipei, Taiwan
Regret Analysis of Sleeping Competing Bandits
Mar 20, 2026Shinnosuke Uba, Yutaro YamaguchiMulti-Armed Bandits
Osaka University, Japan.
Best-of-Both-Worlds Multi-Dueling Bandits: Unified Algorithms for Stochastic and Adversarial Preferences under Condorcet and Borda Objectives
Mar 19, 2026S Akash, Pratik Gajane, Jawar SinghMulti-Armed Bandits Adversarial Bandits
Indian Institute of Technology Patna, India · University of Orléans, France
Multi-Armed Sequential Hypothesis Testing by Betting
Mar 18, 2026Ricardo J. Sandoval, Ian Waudby-Smith, Michael I. JordanSequential Hypothesis Testing Statistical Hypothesis Testing
University of California, Berkeley · École Normale Supérieure & Inria, Paris
Transfer Learning for Contextual Joint Assortment-Pricing under Cross-Market Heterogeneity
Mar 18, 2026Elynn Chen, Xi Chen, Yi ZhangCross-Domain Transfer Learning Assortment Optimization
New York University, Stern School of Business · Tsinghua University, School of Economics and Management
A Practical Algorithm for Feature-Rich, Non-Stationary Bandit Problems
Mar 17, 2026Wei Min Loh, Sajib Kumer Sinha, Ankur Agarwal +1Multi-Armed Bandits Contextual Bandits
University of Waterloo, Vector Institute · Manulife Financial
Robust and Computationally Efficient Linear Contextual Bandits under Adversarial Corruption and Heavy-Tailed Noise
Mar 16, 2026Naoto Tani, Futoshi FutamiContextual Bandits Linear Contextual Bandits
The University of Osaka · RIKEN AIP · The University of Tokyo
The Sampling Complexity of Condorcet Winner Identification in Dueling Bandits
Mar 16, 2026El Mehdi Saad, Victor Thuot, Nicolas VerzelenBest-Arm Identification Multi-Armed Bandits
CC-UM6P-Rabat · INRAE, MISTEA, Institut Agro, Univ. Montpellier Montpellier, France · MISTEA +1

Apr 21, 2026J/K move · Enter open · S save

Replicable Bandits with UCB based Exploration

Rohan Deb, Udaya Ghai, Karan Singh, Arindam Banerjee

University of Illinois Urbana-Champaign · Amazon · Carnegie Mellon University

Multi-Armed Bandits Contextual Bandits ML Reproducibility UCB Algorithms Generalized Linear Bandits

Open paper AskPDF arXiv

We study replicable algorithms for stochastic multi-armed bandits (MAB) and linear bandits with UCB (Upper Confidence Bound) based exploration. A bandit algorithm is

ρ

-replicable if two executions using shared internal randomness but independent reward realizations produce the same action sequence with probability at least

1-ρ

. Prior approaches to this problem are elimination-based and, in linear bandits with infinitely many actions, rely on discretization, leading to suboptimal dependence on the dimension

d

and

ρ

. We develop optimistic alternatives for both settings. For stochastic multi-armed bandits, we propose RepUCB, a replicable batched UCB algorithm and show that it attains a regret

O\!\left(\frac{K^2\log^2 T}{ρ^2}\sum_{a:Δ_a>0}\left(Δ_a+\frac{\log(KT\log T)}{Δ_a}\right)\right)

. For stochastic linear bandits, we first introduce RepRidge, a replicable ridge regression estimator that satisfies both a confidence guarantee and a

ρ

-replicability guarantee. Beyond its role in our bandit algorithm, this may also be of independent interest in other statistical estimation settings. We then use RepRidge to design RepLinUCB, a replicable optimistic algorithm for stochastic linear bandits, and show that its regret is bounded by

\widetilde{O}\!\big(\big(d+\frac{d^3}ρ\big)\sqrt{T}\big)

. This improves the best prior regret guarantee by a factor of

O(d/ρ)

, showing that our optimistic algorithm can substantially reduce the price of replicability. This is the first linear-bandit algorithm with an optimal dependence on

ρ

for large number of arms. Finally, we extend our framework to stochastic generalized linear bandits by developing RepGLM, a replicable penalized GLM estimator, and RepGLMUCB, a replicable optimistic algorithm for this setting.