2003 | OriginalPaper | Buchkapitel
A General Class of No-Regret Learning Algorithms and Game-Theoretic Equilibria
verfasst von : Amy Greenwald, Amir Jafari
Erschienen in: Learning Theory and Kernel Machines
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
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 Φ. Analogously, a class of game-theoretic equilibria, called Φ-equilibria, is defined, and it is shown that the empirical distribution of play of Φ-no-regret algorithms converges to the set of Φ-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 Φ-no-regret algorithms (provably) converge is correlated equilibrium. In particular, Nash equilibrium is not a necessary outcome of learning via any Φ-no-regret learning algorithms.