Fetching the paper…
Reading the bibliography…
We give a simple and computationally efficient algorithm that, for any constant $\varepsilon>0$, obtains $\varepsilon T$-swap regret within only $T = \mathsf{polylog}(n)$ rounds; this is an exponential improvement compared to the super-linear number of rounds required by the state-of-the-art algorithm, and resolves the main open problem of [Blum and Mansour 2007].
Equilibrium points in n-person games
John Nash · 1950
Earlier work this paper cites.
Iterative solutions of games by fictitious play
George W. Brown · 1951
Earlier work this paper cites.
Non-cooperative games
John Nash · 1951
Earlier work this paper cites.
An iterative method of solving a game
Julia Robinson · 1951
Earlier work this paper cites.
Subjectivity and correlation in randomized strategies
Robert J Aumann · 1974
Earlier work this paper cites.
The well-calibrated bayesian
A Philip Dawid · 1982
Earlier work this paper cites.
Existence of correlated equilibria
Sergiu Hart and David Schmeidler · 1989
Earlier work this paper cites.
Five legitimate definitions of correlated equilibrium in games with incomplete information
Françoise Forges · 1993
Earlier work this paper cites.
A randomization rule for selecting forecasts
Dean P Foster and Rakesh V Vohra · 1993
Earlier work this paper cites.
The weighted majority algorithm
Nick Littlestone and Manfred K Warmuth · 1994
Earlier work this paper cites.
How to use expert advice
Nicolo Cesa-Bianchi, Yoav Freund, David Haussler, David P Helmbold, Robert E Schapire, and Manfred K Warmuth · 1997
Earlier work this paper cites.
A decision-theoretic generalization of on-line learning and an application to boosting
Yoav Freund and Robert E Schapire · 1997
Earlier work this paper cites.
Calibrated learning and correlated equilibrium
Dean P Foster and Rakesh V Vohra · 1997
Earlier work this paper cites.
Asymptotic calibration
Dean P Foster and Rakesh V Vohra · 1998
Earlier work this paper cites.
Conditional universal consistency
Drew Fudenberg and David K. Levine · 1999
Earlier work this paper cites.
Adaptive game playing using multiplicative weights
Yoav Freund and Robert E Schapire · 1999
Earlier work this paper cites.
Regret in the on-line decision problem
Dean P Foster and Rakesh Vohra · 1999
Earlier work this paper cites.
A simple adaptive procedure leading to correlated equilibrium
Sergiu Hart and Andreu Mas-Colell · 2000
Earlier work this paper cites.
A reinforcement procedure leading to correlated equilibrium
Sergiu Hart and Andreu Mas-Colell · 2001
Earlier work this paper cites.
Potential-based algorithms in on-line prediction and game theory
Nicolo Cesa-Bianchi and Gábor Lugosi · 2003
Earlier work this paper cites.
Uncoupled dynamics do not lead to nash equilibrium
Sergiu Hart and Andreu Mas-Colell · 2003
Earlier work this paper cites.
Efficient algorithms for online decision problems
Adam Kalai and Santosh Vempala · 2005
Earlier work this paper cites.
Internal regret in on-line portfolio selection
Gilles Stoltz and Gábor Lugosi · 2005
Earlier work this paper cites.
Prediction, learning, and games
Nicolo Cesa-Bianchi and Gábor Lugosi · 2006
Earlier work this paper cites.
From external to internal regret
Avrim Blum and Yishay Mansour · 2007
Earlier work this paper cites.
Algorithmic game theory, 2007
Noam Nisan, Tim Roughgarden, Eva Tardos, and Vijay V Vazirani · 2007
Earlier work this paper cites.
Learning correlated equilibria in games with compact sets of strategies
Gilles Stoltz and Gábor Lugosi · 2007
Earlier work this paper cites.
Regret minimization in games with incomplete information
Martin Zinkevich, Michael Johanson, Michael Bowling, and Carmelo Piccione · 2007
Earlier work this paper cites.
Computing an extensive-form correlated equilibrium in polynomial time
Wan Huang and Bernhard von Stengel · 2008
Earlier work this paper cites.
Computing correlated equilibria in multi-player games
Christos H Papadimitriou and Tim Roughgarden · 2008
Earlier work this paper cites.
Extensive-form correlated equilibrium: Definition and computational complexity
Bernhard Von Stengel and Françoise Forges · 2008
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.
The complexity of computing a nash equilibrium
Constantinos Daskalakis, Paul W Goldberg, and Christos H Papadimitriou · 2009
Cited alongside, same era.
Monte carlo sampling for regret minimization in extensive games
Marc Lanctot, Kevin Waugh, Martin Zinkevich, and Michael Bowling · 2009
Cited alongside, same era.
How long to equilibrium? the communication complexity of uncoupled equilibrium procedures
Sergiu Hart and Yishay Mansour · 2010
Cited alongside, same era.
Near-optimal no-regret algorithms for zero-sum games
Constantinos Daskalakis, Alan Deckelbaum, and Anthony Kim · 2011
Cited alongside, same era.
The multiplicative weights update method: a meta-algorithm and applications
Sanjeev Arora, Elad Hazan, and Satyen Kale · 2012
Cited alongside, same era.
Simple adaptive strategies: from regret-matching to uncoupled dynamics
Sergiu Hart and Andreu Mas-Colell · 2013
Regret circuits: Composability of regret minimizers
Gabriele Farina, Christian Kroer, and Tuomas Sandholm · 2019
Later among the works it cites.
Efficient regret minimization algorithm for extensive-form correlated equilibrium
Gabriele Farina, Chun Kai Ling, Fei Fang, and Tuomas Sandholm · 2019
Later among the works it cites.
Informational bounds on equilibria (a survey)
Yakov Babichenko · 2020
Later among the works it cites.
Communication complexity of nash equilibrium in potential games
Yakov Babichenko and Aviad Rubinstein · 2020
Later among the works it cites.
Mechanisms for a no-regret agent: Beyond the common prior
Modibo K Camara, Jason D Hartline, and Aleck Johnsen · 2020
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.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
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
Sasha Rakhlin and Karthik Sridharan · 2013
Cited alongside, same era.
Query complexity of correlated equilibrium
Yakov Babichenko and Siddharth Barman · 2015
Cited alongside, same era.
Well-supported versus approximate nash equilibria: Query complexity of large games
Xi Chen, Yu Cheng, and Bo Tang · 2015
Cited alongside, same era.
No-regret learning in bayesian games
Jason Hartline, Vasilis Syrgkanis, and Eva Tardos · 2015
Cited alongside, same era.
Polynomial-time computation of exact correlated equilibrium in compact games
Albert Xin Jiang and Kevin Leyton-Brown · 2015
Cited alongside, same era.
A tight lower bound and efficient reduction for swap regret
Shinji Ito · 2020
Later among the works it cites.
Near-optimal no-regret learning in general games
Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich · 2021
Later among the works it cites.
Convergence analysis of no-regret bidding algorithms in repeated auctions
Zhe Feng, Guru Guruganesh, Christopher Liaw, Aranyak Mehta, and Abhishek Sethi · 2021
Later among the works it cites.
On communication complexity of fixed point computation
Anat Ganor and Dömötör Pálvölgyi · 2021
Later among the works it cites.
Near-optimal no-regret learning for correlated equilibria in multi-player general-sum games
Ioannis Anagnostides, Constantinos Daskalakis, Gabriele Farina, Maxwell Fishelson, Noah Golowich, and Tuomas Sandholm · 2022
Later among the works it cites.
Faster no-regret learning dynamics for extensive-form correlated and coarse correlated equilibria
Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Andrea Celli, Tuomas Sandholm, et al · 2022
Later among the works it cites.
Uncoupled learning dynamics with O ( log T ) O(\log T) swap regret in multiplayer games
Ioannis Anagnostides, Gabriele Farina, Christian Kroer, Chung-Wei Lee, Haipeng Luo, and Tuomas Sandholm · 2022
Later among the works it cites.
Efficient phi-regret minimization in extensive-form games via online mirror descent
Yu Bai, Chi Jin, Song Mei, Ziang Song, and Tiancheng Yu · 2022
Later among the works it cites.
Fast rates for nonparametric online learning: from realizability to learning in games
Constantinos Daskalakis and Noah Golowich · 2022
Later among the works it cites.
Near-optimal no-regret learning dynamics for general convex games
Gabriele Farina, Ioannis Anagnostides, Haipeng Luo, Chung-Wei Lee, Christian Kroer, and Tuomas Sandholm · 2022
Later among the works it cites.
Simple uncoupled no-regret learning dynamics for extensive-form correlated equilibrium
Gabriele Farina, Andrea Celli, Alberto Marchesi, and Nicola Gatti · 2022
Later among the works it cites.
Kernelized multiplicative weights for 0/1-polyhedral games: Bridging the gap between learning in extensive-form and normal-form games
Gabriele Farina, Chung-Wei Lee, Haipeng Luo, and Christian Kroer · 2022
Later among the works it cites.
Strategizing against learners in bayesian games
Yishay Mansour, Mehryar Mohri, Jon Schneider, and Balasubramanian Sivan · 2022
Later among the works it cites.
Optimal correlated equilibria in general-sum extensive-form games: Fixed-parameter algorithms, hardness, and two-sided column-generation
Brian Hu Zhang, Gabriele Farina, Andrea Celli, and Tuomas Sandholm · 2022
Later among the works it cites.
Polynomial-time optimal equilibria with a mediator in extensive-form games
Brian Zhang and Tuomas Sandholm · 2022
Later among the works it cites.
Online learning and solving infinite games with an ERM oracle
Angelos Assos, Idan Attias, Yuval Dagan, Constantinos Daskalakis, and Maxwell K. Fishelson · 2023
Closest in time.
Near-optimal Φ \Phi -regret learning in extensive-form games
Ioannis Anagnostides, Gabriele Farina, and Tuomas Sandholm · 2023
Closest in time.
Is learning in games good for the learners?
William Brown, Jon Schneider, and Kiran Vodrahalli · 2023
Closest in time.
Multiplicative weight updates for extensive form games
Chirag Chhablani, Michael Sullins, and Ian A Kash · 2023
Closest in time.
Selling to multiple no-regret buyers
Linda Cai, S Matthew Weinberg, Evan Wildenhain, and Shirley Zhang · 2023
Closest in time.
Yuval Dagan, Constantinos Daskalakis, Maxwell Fishelson, and Noah Golowich · 2023
Closest in time.
Polynomial-time linear-swap regret minimization in imperfect-information sequential games
Gabriele Farina and Charilaos Pipis · 2023
Closest in time.
Bayes correlated equilibria and no-regret dynamics
Kaito Fujii · 2023
Closest in time.
Calibrated stackelberg games: Learning optimal commitments against calibrated agents
Nika Haghtalab, Chara Podimata, and Kunhe Yang · 2023
Closest in time.
An impossibility theorem in game dynamics
Jason Milionis, Christos Papadimitriou, Georgios Piliouras, and Kelly Spendlove · 2023
Closest in time.