Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games

While no-regret learning procedures that converge to correlated equilibria have long been known to exist for normal form games, their analogue in sequential games remains less clear. We propose the sequential correlated equilibrium, a solution concept ...

We show that Optimistic Hedge - a common variant of multiplicative-weights-updates with recency bias - attains poly(logT) regret in multi-player general-sum games. In particular, when every player of the game uses Optimistic Hedge to iteratively update ...

We propose a new no-regret learning algorithm. When used against an adversary, our algorithm achieves average regret that scales as O (1/√T) with the number T of rounds. This regret bound is optimal but not rare, as there are a multitude of learning ...