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

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