Timezone: »

 
Spotlight
A Tight Lower Bound and Efficient Reduction for Swap Regret
Shinji Ito

Wed Dec 09 08:00 PM -- 08:10 PM (PST) @ Orals & Spotlights: Learning Theory
in Orals & Spotlights Track 24: Learning Theory »
Swap regret, a generic performance measure of online decision-making algorithms, plays an important role in the theory of repeated games, along with a close connection to correlated equilibria in strategic games. This paper shows an $\Omega( \sqrt{T N\log{N}} )$-lower bound for swap regret, where $T$ and $N$ denote the numbers of time steps and available actions, respectively. Our lower bound is tight up to a constant, and resolves an open problem mentioned, e.g., in the book by Nisan et al. (2007). Besides, we present a computationally efficient reduction method that converts no-external-regret algorithms to no-swap-regret algorithms. This method can be applied not only to the full-information setting but also to the bandit setting and provides a better regret bound than previous results.

Author Information

Shinji Ito (NEC Corporation)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors