Comparator-Adaptive $Φ$-Regret: Improved Bounds, Simpler Algorithms, and Applications to Games
This work addresses the challenge of designing efficient and adaptive algorithms for online learning and game theory, offering incremental improvements in regret bounds and algorithm simplicity.
The paper tackles the problem of improving comparator-adaptive Φ-regret bounds in expert learning by proposing simpler algorithms that achieve better performance than prior work, with applications to game theory showing accelerated convergence to Φ-equilibria, such as improving bounds for correlated equilibria over existing results.
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]