A1419
Title: Comparator-adaptive $\Phi$-regret: Improved bounds, simpler algorithms, and applications to games
Authors: Mengxiao Zhang - University of Iowa (United States) [presenting]
Abstract: In the classic expert problem, $\Phi$-regret measures the gap between the learner's total loss and that achieved by applying the best action transformation. A recent work introduces an adaptive algorithm whose regret against a comparator $\phi\in\Phi$ depends on a certain sparsity-based complexity measure of $\Phi$, recovering and interpolating optimal bounds for standard regret notions such as external, internal, and swap regret. A general idea is proposed to achieve an even better comparator-adaptive $\Phi$-regret via much simpler algorithms. Specifically, a prior distribution over all possible binary transformations is discovered and it is shown that it suffices to achieve prior-dependent regret against these transformations. Then, two efficient algorithms are proposed to achieve so, where the first one learns over multiple copies of a prior-aware variant of the kernelized MWU algorithm, and the second one learns over multiple copies of a prior-aware variant of the BM-reduction. To showcase the power of these methods and the advantages, it is also shown that the second approach can be extended to the game setting to achieve accelerated and adaptive convergence rate to $\Phi$-equilibria for a class of general-sum games. When specified to the special case of correlated equilibria, the bound improves over existing ones.
