Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Best of Both Worlds: Regret Minimization versus Minimax Play
 
conference paper

Best of Both Worlds: Regret Minimization versus Minimax Play

Müller, Adrian
•
Schneider, Jon
•
Skoulakis, Stratis
Show more
July 2025
Proceedings of the 42 nd International Conference on Machine Learning
Forty-Second International Conference on Machine Learning

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 Õ(√ 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 Ω(T) from exploitable opponents, thereby combining the benefits of both no-regret algorithms and minimax play.

  • Files
  • Details
  • Metrics
Type
conference paper
Author(s)
Müller, Adrian
Schneider, Jon
Skoulakis, Stratis
Viano, Luca  

EPFL

Cevher, Volkan  orcid-logo

EPFL

Date Issued

2025-07

Published in
Proceedings of the 42 nd International Conference on Machine Learning
Series title/Series vol.

Proceedings of Machine Learning Research; 267

ISSN (of the series)

2640-3498

Subjects

ML-AI

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
LIONS  
Event nameEvent acronymEvent placeEvent date
Forty-Second International Conference on Machine Learning

ICML 2025

Vancouver, Canada

2025-07-13 - 2025-07-19

Available on Infoscience
August 8, 2025
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/252848
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés