mlsanityData to 7 Oct 2026

Best of Both Worlds: Regret Minimization versus Minimax Play

arXiv 2502.11673 ↗First posted 17 Feb 2025cs.LG stat.MLcited by 1

Not on the map. Why?

Abstract (arXiv)

In this paper, we investigate the existence of online learning algorithms with bandit feedback that simultaneously guarantee O(1) regret compared to a given comparator strategy, and tildeO(√T) regret compared to any fixed strategy, where T is the number of rounds. We provide the first affirmative answer to this question whenever the comparator strategy supports every action. In the context of zero-sum games with min-max value zero, both in normal- and extensive form, we show that our results allow us to guarantee to risk at most O(1) loss while being able to gain Omega(T) from exploitable opponents, thereby combining the benefits of both no-regret algorithms and minimax play.

Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 34 of its 57 references that are in the map. First posted on arXiv 17 Feb 2025.

Builds on

34 of 57 references.

References · 34

  1. 2019Introduction to Online Convex Optimizationcited by 793
  2. 2019Online Learning: A Modern Introduction Using Convex Optimizationcited by 407
  3. 2013Bandits with Knapsackscited by 163
  4. 2020Exploration-Exploitation in Constrained MDPscited by 146
  5. 2016Coin Betting and Parameter-Free Online Learningcited by 131
  6. 2018Black-Box Reductions for Parameter-free Online Learning in Banach Spacescited by 124
  7. 2021Learning Policies with Zero or Bounded Constraint Violation for Constrained MDPscited by 78
  8. 2016Conservative Banditscited by 58
  9. 2019Strategizing against No-regret Learnerscited by 48
  10. 2022Strategizing against Learners in Bayesian Gamescited by 33
  11. 2022Near-Optimal Learning of Extensive-Form Games with Imperfect Informationcited by 26
  12. 2023Calibrated Stackelberg Games: Learning Optimal Commitments Against Calibrated Agentscited by 25
22 more
  1. 2021Auctions Between Regret-Minimizing Agentscited by 22
  2. 2024Contracting with a Learning Agentcited by 22
  3. 2018Online Convex Optimization for Sequential Decision Processes and Extensive-Form Gamescited by 21
  4. 2021Model-Free Learning for Two-Player Zero-Sum Partially Observable Markov Games with Perfect Recallcited by 21
  5. 2020Conservative Exploration in Reinforcement Learningcited by 20
  6. 2023Is Learning in Games Good for the Learners?cited by 19
  7. 2023Selling to Multiple No-Regret Buyerscited by 19
  8. 2021How and Why to Manipulate Your Own Agent: On the Incentives of Users of Learning Agentscited by 17
  9. 2024Pareto-Optimal Algorithms for Learning in Gamescited by 16
  10. 2021Bandit Linear Optimization for Sequential Decision Making and Extensive-Form Gamescited by 15
  11. 2015The Pareto Regret Frontier for Banditscited by 13
  12. 2020Comparator-adaptive Convex Banditscited by 11
  13. 2021Subgame solving without common knowledgecited by 11
  14. 2022Adapting to game trees in zero-sum imperfect information gamescited by 11
  15. 2015Timeability of Extensive-Form Gamescited by 7
  16. 2023Persuading a Behavioral Agent: Approximately Best Responding and Learningcited by 7
  17. 2014Computing Approximate Nash Equilibria and Robust Best-Responses Using Samplingcited by 6
  18. 2024Is Knowledge Power? On the (Im)possibility of Learning from Strategic Interactionscited by 5
  19. 2016Bayesian Opponent Exploitation in Imperfect-Information Gamescited by 4
  20. 2023Local and adaptive mirror descents in extensive-form gamescited by 2
  21. 2024On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Gamescited by 2
  22. 2015Strong Nash equilibria and mixed strategiescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Learning Safely Without Knowing the World:COMPASS-Hedgecited by 0