17 citations · 187 across the 55 of their papers we have counts for
61 papers
Normal-Form Correlation in Markov Games
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina +3
There has been a surge of recent work on correlated equilibrium concepts in Markov games. However, existing results focus on concepts weaker than normal-form correlated equilibria…
Polynomial-time computation of -contraction fixed points for even
Constantinos Daskalakis, Gabriele Farina, Brian Hu Zhang
We give a -time algorithm that computes an -approximate fixed point of any -nonexpansive map , where $\mat…
Efficient representations for team and imperfect-recall equilibrium computation
Luca Carminati, Brian Hu Zhang, Federico Cacciamani +4
Equilibrium finding in two-player zero-sum games with perfect recall is a well-studied topic that has led to many breakthroughs in computational game theory. This paper aims to gen…
A Polynomial-Time Algorithm for Variational Inequalities under the Minty Condition
Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm +1
Solving (Stampacchia) variational inequalities (SVIs) is a foundational problem at the heart of optimization. However, this expressivity comes at the cost of computational hardness…
Expected Variational Inequalities
Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde +4
Variational inequalities (VIs) encompass many fundamental problems in diverse areas ranging from engineering to economics and machine learning. However, their considerable expressi…
Learning and Computation of -Equilibria at the Frontier of Tractability
Brian Hu Zhang, Ioannis Anagnostides, Emanuel Tewolde +4
-equilibria -- and the associated notion of -regret -- are a powerful and flexible framework at the heart of online learning and game theory, whereby enriching the set of dev…
A Lower Bound on Swap Regret in Extensive-Form Games
Constantinos Daskalakis, Gabriele Farina, Noah Golowich +2
Recent simultaneous works by Peng and Rubinstein [2024] and Dagan et al. [2024] have demonstrated the existence of a no-swap-regret learning algorithm that can reach average sw…
Efficient -Regret Minimization with Low-Degree Swap Deviations in Extensive-Form Games
Brian Hu Zhang, Ioannis Anagnostides, Gabriele Farina +1
Recent breakthrough results by Dagan, Daskalakis, Fishelson and Golowich [2023] and Peng and Rubinstein [2023] established an efficient algorithm attaining at most swap regret…
Optimistic Policy Gradient in Multi-Player Markov Games with a Single Controller: Convergence Beyond the Minty Property
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina +1
Policy gradient methods enjoy strong practical performance in numerous tasks in reinforcement learning. Their theoretical understanding in multiagent settings, however, remains lim…
Mediator Interpretation and Faster Learning Algorithms for Linear Correlated Equilibria in General Extensive-Form Games
Brian Hu Zhang, Gabriele Farina, Tuomas Sandholm
A recent paper by Farina & Pipis (2023) established the existence of uncoupled no-linear-swap regret dynamics with polynomial-time iterations in extensive-form games. The equilibri…
Hidden-Role Games: Equilibrium Concepts and Computation
Luca Carminati, Brian Hu Zhang, Gabriele Farina +2
In this paper, we study the class of games known as hidden-role games in which players are assigned privately to teams and are faced with the challenge of recognizing and cooperati…
Polynomial-Time Linear-Swap Regret Minimization in Imperfect-Information Sequential Games
Gabriele Farina, Charilaos Pipis
No-regret learners seek to minimize the difference between the loss they cumulated through the actions they played, and the loss they would have cumulated in hindsight had they con…
Steering No-Regret Learners to a Desired Equilibrium
Brian Hu Zhang, Gabriele Farina, Ioannis Anagnostides +7
A mediator observes no-regret learners playing an extensive-form game repeatedly across rounds. The mediator attempts to steer players toward some desirable predetermined equil…
Computing Optimal Equilibria and Mechanisms via Learning in Zero-Sum Extensive-Form Games
Brian Hu Zhang, Gabriele Farina, Ioannis Anagnostides +7
We introduce a new approach for computing optimal equilibria via learning in games. It applies to extensive-form settings with any number of players, including mechanism design, in…
Regret Matching+: (In)Stability and Fast Convergence in Games
Gabriele Farina, Julien Grand-Clément, Christian Kroer +2
Regret Matching+ (RM+) and its variants are important algorithms for solving large-scale games. However, a theoretical understanding of their success in practice is still a mystery…
The Update-Equivalence Framework for Decision-Time Planning
Samuel Sokota, Gabriele Farina, David J. Wu +4
The process of revising (or constructing) a policy at execution time -- known as decision-time planning -- has been key to achieving superhuman performance in perfect-information g…
On the Convergence of No-Regret Learning Dynamics in Time-Varying Games
Ioannis Anagnostides, Ioannis Panageas, Gabriele Farina +1
Most of the literature on learning in games has focused on the restrictive setting where the underlying repeated game does not change over time. Much less is known about the conver…
Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planning
Anton Bakhtin, David J Wu, Adam Lerer +5
No-press Diplomacy is a complex strategy game involving both cooperation and competition that has served as a benchmark for multi-agent AI research. While self-play reinforcement l…
Meta-Learning in Games
Keegan Harris, Ioannis Anagnostides, Gabriele Farina +3
In the literature on game-theoretic equilibrium finding, focus has mainly been on solving a single game in isolation. In practice, however, strategic interactions -- ranging from r…
Clairvoyant Regret Minimization: Equivalence with Nemirovski's Conceptual Prox Method and Extension to General Convex Games
Gabriele Farina, Christian Kroer, Chung-Wei Lee +1
A recent paper by Piliouras et al. [2021, 2022] introduces an uncoupled learning algorithm for normal-form games -- called Clairvoyant MWU (CMWU). In this note we show that CMWU is…
Near-Optimal -Regret Learning in Extensive-Form Games
Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm
In this paper, we establish efficient and uncoupled learning dynamics so that, when employed by all players in multiplayer perfect-recall imperfect-information extensive-form games…
Near-Optimal No-Regret Learning Dynamics for General Convex Games
Gabriele Farina, Ioannis Anagnostides, Haipeng Luo +3
A recent line of work has established uncoupled learning dynamics such that, when employed by all players in a game, each player's \emph{regret} after repetitions grows polylog…
ESCHER: Eschewing Importance Sampling in Games by Computing a History Value Function to Estimate Regret
Stephen McAleer, Gabriele Farina, Marc Lanctot +1
Recent techniques for approximating Nash equilibria in very large games leverage neural networks to learn approximately optimal policies (strategies). One promising line of researc…
Uncoupled Learning Dynamics with Swap Regret in Multiplayer Games
Ioannis Anagnostides, Gabriele Farina, Christian Kroer +3
In this paper we establish efficient and \emph{uncoupled} learning dynamics so that, when employed by all players in a general-sum multiplayer game, the \emph{swap regret} of each…