Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2505.17277 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917143416668160 |
|---|---|
| author | Hait, Soumita Li, Ping Luo, Haipeng Zhang, Mengxiao |
| author_facet | Hait, Soumita Li, Ping Luo, Haipeng Zhang, Mengxiao |
| contents | In the classic expert problem, $Φ$-regret measures the gap between the learner's total loss and that achieved by applying the best action transformation $ϕ\in Φ$. A recent work by Lu et al., [2025] introduces an adaptive algorithm whose regret against a comparator $ϕ$ depends on a certain sparsity-based complexity measure of $ϕ$, (almost) recovering and interpolating optimal bounds for standard regret notions such as external, internal, and swap regret. In this work, we propose a general idea to achieve an even better comparator-adaptive $Φ$-regret bound via much simpler algorithms compared to Lu et al., [2025]. Specifically, we discover a prior distribution over all possible binary transformations and show that it suffices to achieve prior-dependent regret against these transformations. Then, we propose two concrete and efficient algorithms to achieve so, where the first one learns over multiple copies of a prior-aware variant of the Kernelized MWU algorithm of Farina et al., [2022], and the second one learns over multiple copies of a prior-aware variant of the BM-reduction [Blum and Mansour, 2007]. To further showcase the power of our methods and the advantages over Lu et al., [2025] besides the simplicity and better regret bounds, we also show that our second approach can be extended to the game setting to achieve accelerated and adaptive convergence rate to $Φ$-equilibria for a class of general-sum games. When specified to the special case of correlated equilibria, our bound improves over the existing ones from Anagnostides et al., [2022a,b] |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_17277 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Comparator-Adaptive $Φ$-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games Hait, Soumita Li, Ping Luo, Haipeng Zhang, Mengxiao Machine Learning In the classic expert problem, $Φ$-regret measures the gap between the learner's total loss and that achieved by applying the best action transformation $ϕ\in Φ$. A recent work by Lu et al., [2025] introduces an adaptive algorithm whose regret against a comparator $ϕ$ depends on a certain sparsity-based complexity measure of $ϕ$, (almost) recovering and interpolating optimal bounds for standard regret notions such as external, internal, and swap regret. In this work, we propose a general idea to achieve an even better comparator-adaptive $Φ$-regret bound via much simpler algorithms compared to Lu et al., [2025]. Specifically, we discover a prior distribution over all possible binary transformations and show that it suffices to achieve prior-dependent regret against these transformations. Then, we propose two concrete and efficient algorithms to achieve so, where the first one learns over multiple copies of a prior-aware variant of the Kernelized MWU algorithm of Farina et al., [2022], and the second one learns over multiple copies of a prior-aware variant of the BM-reduction [Blum and Mansour, 2007]. To further showcase the power of our methods and the advantages over Lu et al., [2025] besides the simplicity and better regret bounds, we also show that our second approach can be extended to the game setting to achieve accelerated and adaptive convergence rate to $Φ$-equilibria for a class of general-sum games. When specified to the special case of correlated equilibria, our bound improves over the existing ones from Anagnostides et al., [2022a,b] |
| title | Comparator-Adaptive $Φ$-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2505.17277 |