Review for NeurIPS paper: Hedging in games: Faster convergence of external and swap regrets

Summary and Contributions: Standard low-regret algorithms guarantee O(sqrt(T)) regret after T rounds (which is tight). One common application of low-regret algorithms is to play an n-action game (in settings like this, it is known that if all players are running low-regret algorithms, then their empirical strategies will converge to specific types of equilibria for the game). It was shown in a series of works that in this more structured setting, it is possible to design algorithms with better regret guarantees; in particular, Syrgkanis et al show that an algorithm known as "Optimistic Hedge" (a generalization of the standard "hedge" / multiplicative weights algorithm) achieves regret bounds on the order of O(T {1/4}) when players in 2 player games both play it. This paper examines the Optimistic Hedge algorithm in further detail, significantly improving the bounds shown by Syrgkanis et al. Specifically, this paper: 1. Shows that if both players in a two-player game run Optimistic Hedge, each player's regret is at most O (T {1/6}). These improvements rely on the fact that Optimistic Hedge converges quickly if the loss vectors and strategies it outputs are relatively stable.