Best of Both Worlds: Regret Minimization versus Minimax Play
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2025
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912412466151424 |
|---|---|
| author | Müller, Adrian Schneider, Jon Skoulakis, Stratis Viano, Luca Cevher, Volkan |
| author_facet | Müller, Adrian Schneider, Jon Skoulakis, Stratis Viano, Luca Cevher, Volkan |
| contents | 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 $\tilde{O}(\sqrt{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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_11673 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Best of Both Worlds: Regret Minimization versus Minimax Play Müller, Adrian Schneider, Jon Skoulakis, Stratis Viano, Luca Cevher, Volkan 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 $\tilde{O}(\sqrt{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. |
| title | Best of Both Worlds: Regret Minimization versus Minimax Play |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2502.11673 |