Optimistic Hedge, a multiplicative weight update with one step of extrapolation, is one of the most natural regret-minimizing dynamics for games, and characterizing its regret has been a longstanding open question. Daskalakis, Fishelson and Golowich proved that if all
m m m players in a finite general-sum game follow Optimistic Hedge with a fixed learning rate, each player's regret is polylogarithmic in the horizon
T T T . Subsequently, Ha showed that an appropriate choice of learning rate makes each player's regret bounded independently of
T T T . This bound, however, is non-constructive and its dependence on the number of actions
n n n is not explicit, leaving open whether Optimistic Hedge can achieve a constant regret bound which is polynomial in the size of the game. We show that the answer hinges on the number of players. In two-player games, there is a learning rate for which Optimistic Hedge guarantees
O ( n log n ) O(n\log n) O ( n log n ) regret independent of the horizon. In three-player games, however, no such bound is possible: for any learning rate up to an absolute constant and for sufficiently large horizon
T T T , there is a game with
n n n actions per player in which some player's regret is
2 Ω ( n ) 2^{Ω(n)} 2 Ω ( n ) , and more generally, for every
m ≥ 3 m\ge3 m ≥ 3 we construct
m m m -player games in which some player's regret is
2 Ω ( m n ) 2^{Ω(mn)} 2 Ω ( mn ) ; for learning rates above
2 − Ω ( m n ) 2^{-Ω(mn)} 2 − Ω ( mn ) , that player's regret even grows linearly in
T T T . Our upper bound is based on a temporal approximation framework for the analysis of Optimistic Hedge. Starting from the variance-based RVU bound of Daskalakis et al., we approximate the losses over time-localized windows by well-behaved functions, whose total variation is a small fraction of their cumulative variance. In
m m m -player games, the same framework gives a significantly simplified proof of the recent
O ( m log n log T ) O(\sqrt{m}\log n\log T) O ( m log n log T ) regret bound due to Ha.