A General Class of No-Regret Algorithms and Game-Theoretic Equilibria

Amy Greenwald and Amir Jafari

Abstract

A general class of no-regret learning algorithms, called Φ-no-regret learning algorithms is defined, which spans the spectrum from no-internal-regret learning to no-external-regret learning, and beyond. Φ describes the set of strategies to which the play of a learning algorithm is compared: a learning algorithm satisfies Φ-no-regret iff no regret is experienced for playing as the algorithm prescribes, rather than playing according to any of the transformations of the algorithm's play prescribed by elements of &Phi.

φ ε Φ okay.

Analogously, a class of game-theoretic equilibria, called (&Phi,f)-equilibria, is defined, and it is shown that the empirical distribution of play of $\Phi$-no-regret algorithms converges to the set of $\Phi$-equilibria. Perhaps surprisingly, the strongest form of no-regret algorithms in this class are no-internal-regret algorithms. Thus, the tightest game-theoretic solution concept to which $\Phi$-no-regret algorithms (provably) converge is correlated equilibrium. In particular, Nash equilibrium is not a necessary outcome of learning via any $\Phi$-no-regret learning algorithms.