A Tight Lower Bound and Efficient Reduction for Swap Regret

Abstract

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.

PDF NeurIPS Semantic Scholar

Cite

Text

Ito. "A Tight Lower Bound and Efficient Reduction for Swap Regret." Neural Information Processing Systems, 2020.

Markdown

[Ito. "A Tight Lower Bound and Efficient Reduction for Swap Regret." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/ito2020neurips-tight-a/)

BibTeX

@inproceedings{ito2020neurips-tight-a,
  title     = {{A Tight Lower Bound and Efficient Reduction for Swap Regret}},
  author    = {Ito, Shinji},
  booktitle = {Neural Information Processing Systems},
  year      = {2020},
  url       = {https://mlanthology.org/neurips/2020/ito2020neurips-tight-a/}
}