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

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 $φ\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]