Adversarial Bandits

Follow this topic Ask about this topic

In adversarial bandits, a learner chooses among actions but observes feedback only for selected actions, while rewards or losses may vary arbitrarily or respond to past choices. The central goal is low regret against a comparator, using methods such as importance-weighted estimates, EXP3, online mirror descent, and follow-the-perturbed-leader. These ideas extend to contextual, linear, kernel, and combinatorial action spaces, as well as settings with delays, constraints, side observations, or switching comparators. A key tension is achieving strong guarantees against adversaries while adapting to stochastic structure, richer feedback, or practical computational limits.

Latest papers

52 papers5 papers in the last four weeks, level with the four weeks before. 0.0% of all new papers.

Three Worlds for the Price of a Logarithm: Baseline-Protected Best-of-Both-Worlds Combinatorial Semi-Bandits
Oct 26, 2026Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-GkaragkounisCombinatorial Semi-Bandits Multi-Armed Bandits
Department of Economics, University of Wisconsin–Madison · Department of Finance, University of Wisconsin–Madison · Department of Computer Sciences, University of Wisconsin–Madison
Follow the Perturbed Leader for Linear Bandits: $\sqrt{T}$ Regret over General Action Sets
Oct 13, 2026Chen-Yu WeiFollow-the-Perturbed-Leader Adversarial Bandits
University of Virginia
m-Set Adversarial Bandits with Winner Feedback
Oct 7, 2026Nicolò Cesa-Bianchi, Matteo PapiniMulti-Armed Bandits Bandit Learning
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
The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits
Sep 19, 2026Changkun Guan, Mengfan XuMulti-Armed Bandits Adversarial Bandits
H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology · Mechanical and Industrial Engineering University of Massachusetts Amherst
Bandits with Probing: Optimal Coverage and the Role of Feedback
Sep 14, 2026Yongjie GuanMulti-Armed Bandits Minimax Regret
Zhejiang University of Technology
Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious Adversary
Sep 11, 2026Mengxiao ZhangMulti-Armed Bandits Adversarial Bandits
University of Iowa
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
Model-Adaptive and Risk-Constrained Frequency Hopping Against Predictive Jammers
Sep 6, 2026Yanbo Chen, Xinjing ZhouWireless Communications Adversarial Bandits
School of Electrical and Electronic Engineering, Nanyang Technological University, Singapore · Università di Udine, Udine, Italy
Bandit Submodular Maximization under Matroid Constraints: Learning Compressed Exchange Policy
Aug 25, 2026Zongqi Wan, Zhijie ZhangSubmodular Optimization Bandit Learning
Great Bay University · Fuzhou University
Toward Optimal Second-Order Path-Length Guarantee for Adversarial Multi-Armed Bandits
Aug 17, 2026Mengxiao ZhangMulti-Armed Bandits Adversarial Bandits
University of Iowa
Lipschitz Bandits with Arbitrary Feedback Delays
Aug 15, 2026Yuhao Liu, Yu Chen, Longbo HuangLipschitz Bandits Multi-Armed Bandits
Institute for Interdisciplinary Information Sciences, Tsinghua University
An Efficient Minimax-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 +2Lipschitz Bandits Multi-Armed 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 Follow-the-Perturbed-Leader
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

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

Three Worlds for the Price of a Logarithm: Baseline-Protected Best-of-Both-Worlds Combinatorial Semi-Bandits

Ting Hu, Luanda Cai, Emmanouil-Vasileios Vlatakis-Gkaragkounis

Department of Economics, University of Wisconsin–Madison · Department of Finance, University of Wisconsin–Madison · Department of Computer Sciences, University of Wisconsin–Madison

Combinatorial Semi-Bandits Multi-Armed Bandits Adversarial Bandits

Open paper AskPDF arXiv

Improving on a baseline requires exploring away from it, precisely where its performance may be lost. We propose DUET (Doubling Under Empirical Tests), a horizon-free phased mixing scheme for combinatorial semi-bandits with arbitrary finite action sets. Two observable tests decide when to double the learning weight and when to double the empirical-regret budget and restart. We instantiate the scheme with entropy-FTRL in mixed phases and hybrid-FTRL in pure phases. Assuming the baseline selects every arm with positive probability, this instantiation keeps expected baseline regret logarithmic in

T

, while its expected regret to every fixed action is

\widetilde{O}(\sqrt{T})

under non-anticipating adversarial losses and polylogarithmic, gap-dependent, under i.i.d. losses with a unique optimal action. All three guarantees hold at every deterministic horizon, and the algorithm knows neither the horizon, nor the gap, nor the environment type. Baseline protection, adversarial robustness, and stochastic adaptivity thus come from one scheme and two base learners, at the price of a logarithm.