Adversarial Bandits

Follow this topic Ask about this topic

Momentum

4 papers in the last four weeks, up 33% on the four weeks before. 0.0% of all new papers.

Jul 13Week of Sep 28

Latest papers 34

All topics

m-Set Adversarial Bandits with Winner Feedback
Oct 7, 2026Nicolò Cesa-Bianchi, Matteo PapiniMulti-Armed Bandits Adversarial Bandits
Universit`a degli Studi di Milano · Politecnico di Milano
Square-Root Regret for Adversarial Multiplayer Bandits without Collision Information or Shared Randomness
Oct 5, 2026Chenyu GanMulti-Armed Bandits Adversarial Bandits
Tsinghua University
Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback
Sep 28, 2026Yuheng ZhangGame Theory Adversarial Bandits
University of Illinois Urbana-Champaign
Minimax Last-Iterate Convergence in Matrix Games with Observed Actions
Sep 28, 2026Yuheng ZhangLast-Iterate Convergence Zero-Sum Games
University of Illinois Urbana-Champaign
Bandits with Probing: Optimal Regret and the Limits of Winner Feedback
Sep 14, 2026Yongjie GuanMulti-Armed Bandits Minimax Regret
Zhejiang University of Technology
Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits
Sep 9, 2026Hao Li, Jie Xu, Zheng XieMulti-Armed Bandits Contextual Bandits
College of Science, National University of Defense Technology, Changsha 410073, China
An Efficient Near-Optimal Algorithm for Adversarial $m$ -Set Bandits
Aug 12, 2026Francesco Bacchiocchi, Tommaso Cesari, Roberto ColomboniCombinatorial Multi-Armed Bandits Adversarial Bandits
DEIB, Politecnico di Milano, Milano, Italy · School of Electrical Engineering and Computer Science, University of Ottawa, Ottawa, Canada · School of Mathematics, University of Bristol, Bristol, United Kingdom
Tracking the Best Strategy in an Extensive-Form Game
Aug 10, 2026Stephen Pasteris, Rahul Savani, Theodore TurocyImperfect-Information Games Regret Minimization
The Alan Turing Institute · London, United Kingdom · The University of Liverpool +3
Regret, equilibrium, and learning in games: A guided tour
Aug 10, 2026Panayotis MertikopoulosNash Equilibrium Adversarial Bandits
Univ. Grenoble Alpes, CNRS, Inria, Grenoble INP, LIG, 38000 Grenoble, France.
Bandit PCA with Minimax Optimal Regret
Jul 12, 2026Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa SahaPrincipal Component Analysis Minimax Regret
Georgia Tech · University of Illinois, Chicago
When Routes Run Out: Adversarial Co-Learning and Explainable Robustness in Quantum Repeater Networks
Jul 10, 2026Brennan Bell, Inti Gabriel Mendoza Estrada, Andreas Trügler +1Adversarial Bandits
RFI-IRFOS and TU Graz, Graz, Austria · openmaind FlexCo and TU Graz, Graz, Austria · Know Center Research GmbH and University of Graz, Graz, Austria +1
Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations
Jul 1, 2026Bin Du, Chang Liu, Dingqi Zhu +2Submodular Optimization Distributed Optimization
College of Automation Engineering, Nanjing University of Aeronautics and Astronautics, Nanjing 211106, China · School of Artificial Intelligence and Automation at the Huazhong University of Science and Technology, Wuhan, China · School of Aeronautics and Astronautics, Purdue University, West Lafayette, IN 47906, USA
Leveraging Similarities in Multi-Armed Bandits
Jun 22, 2026Khaled Eldowa, Thibaud Rahier, Augustin Cablant +2Multi-Armed Bandits Adversarial Bandits
Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LJK, 38000 Grenoble, France · Criteo AI Lab, Paris, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France
Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses
Jun 18, 2026Zhuoyu Cheng, Kohei Hatano, Eiji TakimotoOnline Convex Optimization Bandit Convex Optimization
Joint Graduate School of Mathematics for Innovation, Kyushu University, Japan · RIKEN AIP, Japan · Department of Informatics, Kyushu University, Japan
Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning
Jun 18, 2026Ananya Kunisetty, Avishek GhoshMulti-Armed Bandits Decision-Making under Uncertainty
Indian Institute of Technology Bombay, Mumbai 400076, India
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.
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
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
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
Fairness in two-player zero-sum games with bandit feedback
May 31, 2026S Akash, Pratik GajaneNash Equilibrium Zero-Sum Games
LatentForce.ai Bengaluru, India · Laboratoire d’Informatique Fondamentale d’Orléans University of Orléans, France
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
Near-Optimal Regret in Adversarial Kernel Bandits
May 26, 2026Yu-Jie Zhang, Hao Qiu, Jonathan Scarlett +1Kernel Methods Adversarial Bandits
National University of Singapore
Prudent-Banker: No Extra Fees for Baseline Safety in Adversarial Bandits With and Without Delays
May 22, 2026Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-GkaragkounisMulti-Armed Bandits Minimax Regret
Department of Finance University of Wisconsin–Madison · Department of Computer Sciences University of Wisconsin–Madison
Online Market Making and the Value of Observing the Order Book
May 19, 2026Davide Maran, Marcello RestelliAdversarial Bandits Algorithmic Trading
Politecnico di Milano, Piazza Leonardo da Vinci, 32-36 - Citt`a Studi, Milano (MI)
Nearly-Optimal Algorithm for Adversarial Kernelized Bandits
May 11, 2026Shogo IwazakiMulti-Armed Bandits Adversarial Bandits
LY Corporation Tokyo, Japan
A Complete Characterization of Learnability for Adversarial Noisy Bandits
May 9, 2026Steve Hanneke, Kun WangMulti-Armed Bandits Statistical Learning Theory
Department of Computer Science, Purdue University
Multi-Armed Bandits With Best-Action Queries
May 8, 2026Francesco Bacchiocchi, Matteo Castiglioni, Alberto Marchesi +1Multi-Armed Bandits Adversarial Bandits
Politecnico di Milano
Constrained Contextual Bandits with Adversarial Contexts
May 7, 2026Dhruv Sarkar, Abhishek SinhaContextual Bandits Adversarial Bandits
Indian Institute of Technology Kharagpur, India · Tata Institute of Fundamental Research, Mumbai, India
Online learning with Erdős-Rényi side-observation graphs
Apr 28, 2026Tomáš Kocák, Gergely Neu, Michal ValkoMulti-Armed Bandits Adversarial Bandits
SequeL team INRIA Lille - Nord Europe · Universitat Pompeu Fabra Barcelona, Spain
Efficient learning by implicit exploration in bandit problems with side observations
Apr 27, 2026Tomas Kocak, Gergely Neu, Michal Valko +1Multi-Armed Bandits Exploration-Exploitation Tradeoff
SequeL team, INRIA Lille – Nord Europe, France · Current affiliation: Google DeepMind
Online Conformal Prediction with Adversarial Semi-bandit Feedback via Regret Minimization
Apr 20, 2026Junyoung Yang, Kyungmin Kim, Sangdon ParkUncertainty Quantification Conformal Prediction
GSAI POSTECH · GSAI & CSE POSTECH
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
Self-Concordant Perturbations for Linear Bandits
Oct 28, 2025Lucas Lévy, Jean-Lou Valeau, Arya Akhavan +1Multi-Armed Bandits Exploration-Exploitation Tradeoff
Ecole Polytechnique and University of Oxford · ENSAE Paris and University of Oxford · University of Oxford and Ecole Polytechnique +1
Best-of-Both Worlds for linear contextual bandits with paid observations
Oct 8, 2025Nathan Boyer, Dorian Baudry, Patrick RebeschiniMulti-Armed Bandits Follow-the-Regularized-Leader
ENS Paris-Saclay, France · Univ. Grenoble Alpes, Inria, CNRS, Grenoble INP, LIG, 38000 Grenoble, France · Department of Statistics, University of Oxford

Oct 7, 2026, cs.LGJ/K move · Enter open · S save

m-Set Adversarial Bandits with Winner Feedback

Nicolò Cesa-Bianchi, Matteo Papini

Universit`a degli Studi di Milano · Politecnico di Milano

Multi-Armed Bandits Adversarial Bandits Combinatorial Multi-Armed Bandits Minimax Regret

Open paper AskPDF arXiv

We show upper and lower bounds on the regret of

m

-set adversarial bandits for different utilities (winner reward or sum of rewards) and feedback models (winner index, winner reward, sum of rewards, and their combinations). By comparing to standard bounds for combinatorial and MNL bandits, our results reveal how subtle changes in the setting can have a dramatic impact on the learning rates. Our main technical contributions are the information-theoretic lower bounds on the regret. Experiments on synthetic data confirm our theoretical analyses.

Momentum

Related topics

Latest papers 34