Overview

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

CardsList

62 papers8 papers in the last four weeks, up 60% on the four weeks before. 0.1% of all new papers.

  1. Adversarially Batched Online Learning

    Nov 12, 2026Mingda Qiao, Kerui WuBatched BanditsOnline Convex Optimization

  2. Near-Optimal Regret for Oracle-Efficient Adversarial Contextual Bandits

    Nov 12, 2026Kiarash Banihashem, MohammadTaghi HajiaghayiContextual BanditsAdversarial Bandits

  3. Best-of-Both-Worlds FTRL for Linear Bandits: The Interplay of Information Acquisition, Corruption, and Geometry

    Oct 31, 2026Canzhe Zhao, Vincent Y. F. TanBest-of-Both-Worlds BanditsAdversarial Bandits

  4. Near-Optimal First-Order Regret for Bandits with Feedback Graphs

    Oct 29, 2026Mengxiao Zhang, Yuheng Zhang, Haipeng Luo +1Graph BanditsRegret Minimization

  5. Nearly Minimax Optimal Regret for Adversarial Linear Bandits with Strong Corruptions

    Oct 28, 2026Qiwei Di, Quanquan GuAdversarial BanditsFollow-the-Regularized-Leader

  6. 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-GkaragkounisBest-of-Both-Worlds BanditsCombinatorial Semi-Bandits

  7. m-Set Adversarial Bandits with Winner Feedback

    Oct 7, 2026Nicolò Cesa-Bianchi, Matteo PapiniMulti-Armed BanditsBandit Learning

  8. Polylogarithmic Nash Regret in Matrix Games with Bandit Feedback

    Sep 28, 2026Yuheng ZhangGame TheoryAdversarial Bandits

  9. The Role of Coordinates in Pareto Regret for Adversarial Multi-Objective Bandits

    Sep 19, 2026Changkun Guan, Mengfan XuMulti-Armed BanditsAdversarial Bandits

  10. Meta-LinEXP3: Online-within-Online Learning for Adversarial Linear Contextual Bandits

    Sep 9, 2026Hao Li, Jie Xu, Zheng XieMulti-Armed BanditsContextual Bandits

  11. Model-Adaptive and Risk-Constrained Frequency Hopping Against Predictive Jammers

    Sep 6, 2026Yanbo Chen, Xinjing ZhouWireless CommunicationsAdversarial Bandits

  12. Lipschitz Bandits with Arbitrary Feedback Delays

    Aug 15, 2026Yuhao Liu, Yu Chen, Longbo HuangLipschitz BanditsMulti-Armed Bandits

  13. An Efficient Minimax-Optimal Algorithm for Adversarial mm-Set Bandits

    Aug 12, 2026Francesco Bacchiocchi, Tommaso Cesari, Roberto ColomboniCombinatorial Multi-Armed BanditsAdversarial Bandits

  14. Tracking the Best Strategy in an Extensive-Form Game

    Aug 10, 2026Stephen Pasteris, Rahul Savani, Theodore TurocyImperfect-Information GamesRegret Minimization

  15. Regret, equilibrium, and learning in games: A guided tour

    Aug 10, 2026Panayotis MertikopoulosNash EquilibriumAdversarial Bandits

  16. Bandit PCA with Minimax Optimal Regret

    Jul 12, 2026Moïse Blanchard, Dmitrii Ostrovskii, Aadirupa SahaPrincipal Component AnalysisMinimax Regret

  17. 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

  18. Distributed Online Bandit Submodular Maximization with Bounded Sampling Violations

    Jul 1, 2026Bin Du, Chang Liu, Dingqi Zhu +2Submodular OptimizationDistributed Optimization

  19. Leveraging Similarities in Multi-Armed Bandits

    Jun 22, 2026Khaled Eldowa, Thibaud Rahier, Augustin Cablant +2Lipschitz BanditsMulti-Armed Bandits

  20. Adversarial Bandit Optimization with Globally Bounded Perturbations to Convex Losses

    Jun 18, 2026Zhuoyu Cheng, Kohei Hatano, Eiji TakimotoOnline Convex OptimizationBandit Convex Optimization

  21. Matching Markets meet Cumulative Prospect Theory: Towards Optimal and Adversarially Robust Learning

    Jun 18, 2026Ananya Kunisetty, Avishek GhoshMulti-Armed BanditsDecision-Making under Uncertainty