8 papers
Swap Regret Minimization Through Response-Based Approachability
Ioannis Anagnostides, Gabriele Farina, Maxwell Fishelson +2
We consider the problem of minimizing different notions of swap regret in online optimization. These forms of regret are tightly connected to correlated equilibrium concepts in gam…
On Separation Between Best-Iterate, Random-Iterate, and Last-Iterate Convergence of Learning in Games
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
Non-ergodic convergence of learning dynamics in games is widely studied recently because of its importance in both theory and practice. Recent work (Cai et al., 2024) showed that a…
Last-Iterate Convergence Properties of Regret-Matching Algorithms in Games
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
We study last-iterate convergence properties of algorithms for solving two-player zero-sum games based on Regret Matching (RM). Despite their widespread use for solving rea…
Fast Last-Iterate Convergence of Learning in Games Requires Forgetful Algorithms
Yang Cai, Gabriele Farina, Julien Grand-Clément +4
Self-play via online learning is one of the premier ways to solve large-scale two-player zero-sum games, both in theory and practice. Particularly popular algorithms include optimi…
Efficient Learning and Computation of Linear Correlated Equilibrium in General Convex Games
Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson +2
We propose efficient no-regret learning dynamics and ellipsoid-based methods for computing linear correlated equilibria$\unicode{x2014}$a relaxation of correlated equilibria and a…
On the Optimality of Dilated Entropy and Lower Bounds for Online Learning in Extensive-Form Games
Zhiyuan Fan, Christian Kroer, Gabriele Farina
First-order methods (FOMs) are arguably the most scalable algorithms for equilibrium computation in large extensive-form games. To operationalize these methods, a distance-generati…