Hedging in games: Faster convergence of external and swap regrets

We consider the setting where players run the Hedge algorithm or its optimistic variant to play an n-action game repeatedly for T rounds.

1. For two-player games, we show that the regret of optimistic Hedge decays at O( 1/T ^5/6 ), improving the previous bound O(1/T^3/4) by .
2. In contrast, we show that the convergence rate of vanilla Hedge is no better than (1/ T), addressing an open question posted in . For general m-player games, we show that the swap regret of each player decays at rate O(m^1/2 (n/T)^3/4) when they combine optimistic Hedge with the classical external-to-internal reduction of Blum and Mansour . The algorithm can also be modified to achieve the same rate against itself and a rate of O(n/T) against adversaries. Via standard connections, our upper bounds also imply faster convergence to coarse correlated equilibria in two-player games and to correlated equilibria in multiplayer games.