10 papers
Accelerating Min-Max Optimization via Power-Law Stepsizes
Yue Wu, Weiqiang Zheng, Yang Cai +1
We revisit the convergence guarantees of the Extragradient (EG) method for unconstrained biaffine min-max optimization. It is known that EG with a fixed stepsize achieves a $Θ(T^{-…
Is Online Linear Optimization Sufficient for Strategic Robustness?
Yang Cai, Haipeng Luo, Chen-Yu Wei +1
We consider bidding in repeated Bayesian first-price auctions. Bidding algorithms that achieve optimal regret have been extensively studied, but their strategic robustness to the s…
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…
Proximal Regret and Proximal Correlated Equilibria: A New Tractable Solution Concept for Online Learning and Games
Yang Cai, Constantinos Daskalakis, Haipeng Luo +2
Learning and computation of equilibria are central problems in game theory, theory of computation, and artificial intelligence. In this work, we introduce proximal regret, a new no…
From Average-Iterate to Last-Iterate Convergence in Games: A Reduction and Its Applications
Yang Cai, Haipeng Luo, Chen-Yu Wei +1
The convergence of online learning algorithms in games under self-play is a fundamental question in game theory and machine learning. Among various notions of convergence, last-ite…
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…
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…
On Tractable -Equilibria in Non-Concave Games
Yang Cai, Constantinos Daskalakis, Haipeng Luo +2
While Online Gradient Descent and other no-regret learning procedures are known to efficiently converge to a coarse correlated equilibrium in games where each agent's utility is co…
Near-Optimal Policy Optimization for Correlated Equilibrium in General-Sum Markov Games
Yang Cai, Haipeng Luo, Chen-Yu Wei +1
We study policy optimization algorithms for computing correlated equilibria in multi-player general-sum Markov Games. Previous results achieve convergence rate to a c…
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…