A Tight Lower Bound and Efficient Reduction for Swap Regret

Shinji ItoNeurIPS 2020 · OpenReview

TL;DR

This paper resolves a long-standing open problem in online learning by proving a tight lower bound of $\Omega(\sqrt{TN \log N})$ for swap regret, demonstrating that previously known upper bounds were already optimal. Additionally, the author introduces a new, highly efficient algorithm that converts standard "no-external-regret" algorithms into "no-swap-regret" algorithms with significantly lower computational overhead.

Introduction: External vs. Swap Regret

In online decision-making, a player chooses actions and receives losses over $T$ time steps. Most algorithms aim to minimize external regret—the difference between the player's total loss and the loss they would have incurred by consistently picking the single best action in hindsight.

However, swap regret is a much stricter requirement. It compares the player's performance against a version of themselves that could have "swapped" every instance of action $A$ for action $B$ (for all possible pairs of actions). Swap regret is vital in game theory because if all players in a game exhibit "no swap regret," their collective behavior converges to a correlated equilibrium.

The Theoretical and Computational Gaps

Before this paper, there were two significant gaps in our understanding of swap regret:

  1. The Bound Gap: Known algorithms achieved $O(\sqrt{TN \log N})$ swap regret, but the best-known lower bound was only $\Omega(\sqrt{TN})$. It was unclear whether the $\sqrt{\log N}$ factor was a fundamental necessity or merely a byproduct of inefficient algorithms.
  2. The Efficiency Gap: Existing methods to achieve no-swap-regret were computationally expensive, typically requiring the update of $N$ different sub-algorithms at every single time step.

Proposed Methods and Contributions

The paper attacks these two gaps with two distinct theoretical contributions:

1. Refining the Lower Bound (Theorem 1)

The author builds upon a classic adversarial environment designed by Blum and Mansour. By applying sophisticated tools from order statistics and concentration inequalities, the author proves that an adversary can always force a swap regret of at least $\Omega(\sqrt{TN \log N})$. This confirms that the $\sqrt{\log N}$ factor is an inherent difficulty of the swap regret problem, providing closure to an open problem highlighted in foundational texts like Algorithmic Game Theory (Nisan et al., 2007).

2. A Two-Step Randomization Reduction (Theorem 2)

To improve efficiency, the paper proposes a new "reduction" method. Standard reductions maintain $N$ separate "internal" algorithms (one for each action) and update all of them every time a loss vector is revealed.

The author introduces a novel sampling technique:

  • Instead of updating all $N$ internal algorithms, the master algorithm picks just one internal algorithm to provide the action and only updates that specific instance with the feedback received.
  • This "two-step randomization" ensures that the expected regret remains low while slashing the per-step computational cost by a factor of $N$.

Unlike previous methods that required "data-dependent" or "first-order" regret bounds to work well, this new reduction is highly generic and works with any standard no-external-regret algorithm as a black box.

Key Results

The paper successfully establishes matching bounds for the full-information setting and significantly improves the state-of-the-art for the bandit setting.

Summary of upper and lower bounds for swap regret
  • Tight Lower Bound: Established the first $\Omega(\sqrt{TN \log N})$ lower bound for swap regret (Theorem 1), perfectly matching the known upper bounds in the full-information setting.
  • Computational Speedup: The new reduction reduces the per-step complexity from $O(N \cdot \text{Step}_A)$ to $O(\text{Step}_A + \text{SD}_N)$, where $\text{SD}_N$ is the time to compute a stationary distribution of a Markov chain (roughly $O(N^2)$).
  • Improved Bandit Bounds: In the "bandit" setting (where the algorithm only observes the loss of the chosen action), the paper provides a new polynomial-time algorithm achieving $O(\sqrt{TN^2})$ regret (Theorem 2), which strictly improves upon previous poly-time results.

Limitations and Future Work

  • Assumptions on $T$: The lower bound proof currently requires certain assumptions regarding the relationship between $T$ and $N$ (specifically that $T$ isn't excessively large relative to $N$). The author conjectures these assumptions can be removed with more sophisticated analysis.
  • The Bandit Gap: While the full-information setting is now theoretically "solved" with matching upper and lower bounds, a gap still exists in the bandit setting. The lower bound is $\Omega(\sqrt{TN \log N})$, but the best efficient upper bound is now $O(\sqrt{TN^2})$. Closing this remaining gap is a primary direction for future research.

Summary updated

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.
BibTeX
@inproceedings{ito2020tight,
  author = {Shinji Ito},
  title = {{A Tight Lower Bound and Efficient Reduction for Swap Regret}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=W2ZZp9P6yo},
}
Figure