Fetching the paper…
Reading the bibliography…
We show that Optimistic Hedge -- a common variant of multiplicative-weights-updates with recency bias -- attains ${\rm poly}(\log T)$ regret in multi-player general-sum games.
Some Notes on Computation of Games Solutions
George W Brown · 1949
Earlier work this paper cites.
An Iterative Method of Solving a Game
Julia Robinson · 1951
Earlier work this paper cites.
Controlled Random Walks
David Blackwell · 1954
Earlier work this paper cites.
Approximation to Bayes risk in repeated play
James Hannan · 1957
Earlier work this paper cites.
Some Topics in Two-Person Games
L. Shapley · 1964
Earlier work this paper cites.
Concrete Mathematics: A Foundation for Computer Science
Ronald L. Graham, Donald E. Knuth, and Oren Patashnik · 1989
Earlier work this paper cites.
Uncoupled dynamics do not lead to nash equilibrium
Hart, Andreu Mas-colell, Of Jörgen W. Weibull, O Vega, Drew Fudenberg, David K. Levine, Josef Hofbauer, Karl Sigmund, Eric Maskin, Motty Perry, and Er Vasin · 2003
Earlier work this paper cites.
Information Theory and Statistics: A Tutorial
Imre Csiszár and Paul C. Shields · 2004
Earlier work this paper cites.
Excessive gap technique in nonsmooth convex minimization
Yu Nesterov · 2005
Earlier work this paper cites.
Prediction, Learning, and Games
Nicolo Cesa-Bianchi and Gábor Lugosi · 2006
Earlier work this paper cites.
The complexity of computing a nash equilibrium
Constantinos Daskalakis, Paul W. Goldberg, and Christos H. Papadimitriou · 2006
Earlier work this paper cites.
Settling the complexity of computing two-player nash equilibria
Xi Chen, Xiaotie Deng, and Shang-Hua Teng · 2009
Earlier work this paper cites.
Intrinsic robustness of the price of anarchy
Tim Roughgarden · 2009
Earlier work this paper cites.
On learning algorithms for nash equilibria
Constantinos Daskalakis, Rafael Frongillo, Christos H. Papadimitriou, George Pierrakos, and Gregory Valiant · 2010
Earlier work this paper cites.
Near-Optimal No-Regret Algorithms for Zero-Sum Games
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim · 2011
Cited alongside, same era.
Beyond the nash equilibrium barrier
Robert Kleinberg, Katrina Ligett, and Georgios Piliouras · 2011
Cited alongside, same era.
The Weighted Majority Algorithm does not Converge in Nearly Zero-sum Games
Maria-Florina Balcan, Florin Constantin, and Ruta Mehta · 2012
Cited alongside, same era.
Online learning with predictable sequences
Alexander Rakhlin and Karthik Sridharan · 2013
Cited alongside, same era.
Optimization, Learning, and Games with Predictable Sequences
Alexander Rakhlin and Karthik Sridharan · 2013
Cited alongside, same era.
Composable and efficient mechanisms
Vasilis Syrgkanis and Eva Tardos · 2013
Let’s be honest: An optimal no-regret framework for zero-sum games
Ehsan Asadi Kangarshahi, Ya-Ping Hsieh, Mehmet Fatih Sahin, and Volkan Cevher · 2018
Later among the works it cites.
Cycles in adversarial regularized learning
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras · 2018
Later among the works it cites.
More adaptive algorithms for adversarial bandits
Chen-Yu Wei and Haipeng Luo · 2018
Later among the works it cites.
Fast and furious learning in zero-sum games: Vanishing regret with non-vanishing step sizes
James P. Bailey and Georgios Piliouras · 2019
Later among the works it cites.
Vortices instead of equilibria in minmax optimization: Chaos and butterfly effects of online learning in zero-sum games
Yun Kuen Cheung and Georgios Piliouras · 2019
Later among the works it cites.
Last-iterate convergence: Zero-sum games and constrained min-max optimization
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Cited alongside, same era.
A counter-example to Karlin’s strong conjecture for fictitious play
Constantinos Daskalakis and Qinxuan Pan · 2014
Cited alongside, same era.
Convex Optimization: Algorithms and Complexity
Sébastien Bubeck · 2015
Cited alongside, same era.
Fast convergence of regularized learning in games
Vasilis Syrgkanis, Alekh Agarwal, Haipeng Luo, and Robert E Schapire · 2015
Cited alongside, same era.
Learning in games: Robustness of fast convergence
Dylan J Foster, Zhiyuan Li, Thodoris Lykouris, Karthik Sridharan, and Eva Tardos · 2016
Cited alongside, same era.
From nash equilibria to chain recurrent sets: Solution concepts and topology
Christos Papadimitriou and Georgios Piliouras · 2016
Cited alongside, same era.
The price of anarchy in auctions
Tim Roughgarden, Vasilis Syrgkanis, and Éva Tardos · 2017
Cited alongside, same era.
Constantinos Daskalakis and Ioannis Panageas · 2019
Later among the works it cites.
Hedging in games: Faster convergence of external and swap regrets
Xi Chen and Binghui Peng · 2020
Later among the works it cites.
Tight last-iterate convergence rates for no-regret learning in multi-player games
Noah Golowich, Sarath Pattathil, and Constantinos Daskalakis · 2020
Later among the works it cites.
No-regret learning and mixed nash equilibria: They do not mix
Emmanouil-Vasileios Vlatakis-Gkaragkounis, Lampros Flokas, Thanasis Lianeas, Panayotis Mertikopoulos, and Georgios Piliouras · 2020
Later among the works it cites.
The last-iterate convergence rate of optimistic mirror descent in stochastic variational inequalities
Waïss Azizian, Franck Iutzeler, Jérome Malick, and Panayotis Mertikopoulos · 2021
Closest in time.
Adaptive learning in continuous games: Optimal regret bounds and convergence to nash equilibrium
Yu-Guan Hsieh, Kimon Antonakopoulos, and Panayotis Mertikopoulos · 2021
Closest in time.
Last iterate convergence in no-regret learning: constrained min-max optimization for convex-concave landscapes
Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, and xiao wang · 2021
Closest in time.
Linear last-iterate convergence in constrained saddle-point optimization
Chen-Yu Wei, Chung-Wei Lee, Mengxiao Zhang, and Haipeng Luo · 2021
Closest in time.