5 papers · 1 filter
The Value of Recall in Extensive-Form Games
Ratip Emin Berker, Emanuel Tewolde, Ioannis Anagnostides +2
Imperfect-recall games, in which players may forget previously acquired information, have found many practical applications, ranging from game abstractions to team games and testin…
Computational Lower Bounds for Regret Minimization in Normal-Form Games
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm
A celebrated connection in the interface of online learning and game theory establishes that players minimizing swap regret converge to correlated equilibria (CE) -- a seminal game…
Barriers to Welfare Maximization with No-Regret Learning
Ioannis Anagnostides, Alkis Kalavasis, Tuomas Sandholm
A celebrated result in the interface of online learning and game theory guarantees that the repeated interaction of no-regret players leads to a coarse correlated equilibrium (CCE)…
Convergence of for Gradient-Based Algorithms in Zero-Sum Games without the Condition Number: A Smoothed Analysis
Ioannis Anagnostides, Tuomas Sandholm
Gradient-based algorithms have shown great promise in solving large (two-player) zero-sum games. However, their success has been mostly confined to the low-precision regime since t…
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…