Logo image
Back
Comparator-Adaptive Φ-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games
Preprint   Open access

Comparator-Adaptive Φ-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games

Soumita Hait, Ping Li, Haipeng Luo and Mengxiao Zhang
ArXiV.org
Cornell University
05/22/2025
DOI: 10.48550/arxiv.2505.17277
url
https://doi.org/10.48550/arxiv.2505.17277View
Preprint (Author's original)This preprint has not been evaluated by subject experts through peer review. Preprints may undergo extensive changes and/or become peer-reviewed journal articles. Open Access

Abstract

In the classic expert problem, Φ-regret measures the gap between the learner's total loss and that achieved by applying the best action transformation φ ∈ Φ. 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]
Computer Science - Learning

Details

Metrics

43 Record Views
Logo image