mlsanityData to 7 Oct 2026

Fighting Bandits with a New Kind of Smoothness

arXiv 1512.04152 ↗First posted 14 Dec 2015cs.LG cs.GT stat.MLcited by 45

Not on the map. Why?

Abstract (arXiv)

We define a novel family of algorithms for the adversarial multi-armed bandit problem, and provide a simple analysis technique based on convex smoothing. We prove two main results. First, we show that regularization via the Tsallis entropy, which includes EXP3 as a special case, achieves the Theta(√TN) minimax regret. Second, we show that a wide class of perturbation methods achieve a near-optimal regret as low as O(√TN log N) if the perturbation distribution has a bounded hazard rate. For example, the Gumbel, Weibull, Frechet, Pareto, and Gamma distributions all satisfy this key property.

Key facts. Cited by 45 papers in the map (data through 7 Oct 2026). First posted on arXiv 14 Dec 2015.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 5; 2022: 9; 2023: 10; 2024: 8; 2025: 11; 2026: 2.

45 papers.

Sort:

By area:

  1. 2021Adapting to Misspecification in Contextual Banditscited by 81
  2. 2022Smoothed Online Learning is as Easy as Statistical Learningcited by 50
  3. 2022A Best-of-Both-Worlds Algorithm for Bandits with Delayed Feedbackcited by 23
  4. 2022Adaptive Best-of-Both-Worlds Algorithm for Heavy-Tailed Multi-Armed Banditscited by 17
  5. 2021Nonstochastic Bandits with Composite Anonymous Feedbackcited by 16
  6. 2021Improved Analysis of the Tsallis-INF Algorithm in Stochastically Constrained Adversarial Bandits and Stochastic Bandits with Adversarial Corruptionscited by 15
  7. 2023Stability-penalty-adaptive follow-the-regularized-leader: Sparsity, game-dependency, and best-of-both-worldscited by 15
  8. 2022Better Best of Both Worlds Bounds for Bandits with Switching Costscited by 13
  9. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
  10. 2023A Best-of-both-worlds Algorithm for Bandits with Delayed Feedback with Robustness to Excessive Delayscited by 11
  11. 2024Adaptive Learning Rate for Follow-the-Regularized-Leader: Competitive Analysis and Best-of-Both-Worldscited by 11
  12. 2021Efficient Competitions and Online Learning with Strategic Forecasterscited by 9
33 more
  1. 2025Towards a Sharp Analysis of Offline Policy Learning for f-Divergence-Regularized Contextual Banditscited by 9
  2. 2023On the Minimax Regret for Online Learning with Feedback Graphscited by 8
  3. 2023Meta-Learning Adversarial Bandit Algorithmscited by 8
  4. 2023Banker Online Mirror Descent: A Universal Approach for Delayed Online Bandit Learningcited by 7
  5. 2024No-Regret Learning for Fair Multi-Agent Social Welfare Optimizationcited by 7
  6. 2022A Unified Perspective on Value Backup and Exploration in Monte-Carlo Tree Searchcited by 6
  7. 2022Meta-Learning Adversarial Banditscited by 5
  8. 2022On Efficient Online Imitation Learning via Classificationcited by 5
  9. 2023Oracle-Efficient Smoothed Online Learning for Piecewise Continuous Decision Makingcited by 5
  10. 2024Beyond Minimax Rates in Group Distributionally Robust Optimization via a Novel Notion of Sparsitycited by 5
  11. 2026Provably Efficient Regularized Online RLHF with Generalized Bilinear Preferencescited by 5
  12. 2023The equivalence of dynamic and strategic stability under regularized learning in gamescited by 4
  13. 2024A Simple and Adaptive Learning Rate for FTRL in Online Learning with Minimax Regret of Theta(T2/3) and its Application to Best-of-Both-Worldscited by 3
  14. 2024Improved Regret Bounds for Bandits with Expert Advicecited by 3
  15. 2024Optimism in the Face of Ambiguity Principle for Multi-Armed Banditscited by 3
  16. 2025Revisiting Follow-the-Perturbed-Leader with Unbounded Perturbations in Bandit Problemscited by 3
  17. 2022Online Meta-Learning in Adversarial Multi-Armed Banditscited by 2
  18. 2023Learning in Zero-Sum Markov Games: Relaxing Strong Reachability and Mixing Time Assumptionscited by 2
  19. 2024Near-optimal Per-Action Regret Bounds for Sleeping Banditscited by 2
  20. 2025Follow-the-Perturbed-Leader Approaches Best-of-Both-Worlds for the m-Set Semi-Bandit Problemscited by 2
  21. 2021Scale-Free Adversarial Multi-Armed Bandit with Arbitrary Feedback Delayscited by 1
  22. 2025Efficient and Optimal No-Regret Caching under Partial Observationcited by 1
  23. 2025Faster Rates for Private Adversarial Banditscited by 1
  24. 2025Follow-the-Perturbed-Leader for Decoupled Bandits: Best-of-Both-Worlds and Practicalitycited by 1
  25. 2025The Hidden Cost of Approximation in Online Mirror Descentcited by 1
  26. 2023No-Regret Online Prediction with Strategic Expertscited by 0
  27. 2023Learning to Relax: Setting Solver Parameters Across a Sequence of Linear System Instancescited by 0
  28. 2024Distributed No-Regret Learning for Multi-Stage Systems with End-to-End Bandit Feedbackcited by 0
  29. 2025Note on Follow-the-Perturbed-Leader in Combinatorial Semi-Bandit Problemscited by 0
  30. 2025One-shot acceleration of transient PDE solvers via online-learned preconditionerscited by 0
  31. 2025Self-Concordant Perturbations for Linear Banditscited by 0
  32. 2025Robust equilibria in continuous games: From strategic to dynamic robustnesscited by 0
  33. 2026Regret, equilibrium, and learning in games: A guided tourcited by 0