A simple adaptive procedure leading to correlated equilibrium
By Sergiu Hart, Andreu Mas-Colell. 2000
1,376 citations recorded by the source corpus.
We propose a new and simple adaptive procedure for playing a game: ‘‘regret-matching.’’ In this procedure, players may depart from their current play with probabilities that are proportional to measures of regret for not having used other strategies in the past. It is shown that our adaptive procedure guarantees that, with probability one, the empirical distributions of play converge to the set of correlated equilibria of the game.
Subfields: Economics and Econometrics, Management Science and Operations Research, Economics & Operations Research
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Economics and Econometrics
- Tuomas Sandholm
- Noam Brown
- Marc Lanctot
- Karl Tuyls
- Neil Burch
- Elad Hazan
- Julien Pérolat
- Aleksandrs Slivkins
In Management Science and Operations Research
- Karl Tuyls
- Marc Lanctot
- Aleksandrs Slivkins
- Elad Hazan
- Tuomas Sandholm
- David Silver
- Alekh Agarwal
- Nicolò Cesa-Bianchi
In Economics & Operations Research
- Nicolò Cesa-Bianchi
- Shai Shalev-Shwartz
- Josef Hofbauer
- Christos H. Papadimitriou
- Yishay Mansour
- Zhu Han
- Hongyuan Zha
- Sylvain Sorin
Citations in the corpus
- OpenSpiel: A Framework for Reinforcement Learning in Games (2019, methodology): “CFR proceeds by minimizing this regret, typically using regret-matching [23].”
- Introduction to Online Convex Optimization (2016, methodology): “More general connections of convergence of low-regret algorithms to equilibria in games were studied by Hart and Mas-Collel [51], and more recently in [41, 93].”
- Regret Analysis of Stochastic and Nonstochastic Multi-armed Bandit Problems (2012, neutral): “Another direction was explored by Hazan and Kale [2009] building on previous works in the full information setting —see Cesa-Bianchi et al.”
- A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, background): “Regret matching (RM) is a simple adaptive procedure that leads to correlated equilibria [32], which tabulates cumulative regret Ri(πi,k) for πi,k at epoch k.”
- Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving (2016, background): “Other approaches to Stochastic Games are explicit modeling of the other players, that goes back to Brown’s fictitious play [9], and vanishing regret learning algorithms [13, 10].”
- Dynamic fictitious play, dynamic gradient play, and distributed convergence to Nash equilibria (2005, methodology): “Contrary to the case of Nash equilibria, there are methods [16], [22], [25] that are guaranteed for all games to converge to the larger set of so-called correlated equilibria, which is a convex set that contains the set of Nash equilibria.”
- Prediction, learning, and games (2006, methodology): “The existence of adaptive procedures leading to a correlated equilibrium was shown by Foster and Vohra [105]; see also Fudenberg and Levine [118, 121] and Hart and Mas-Colell [145, 146].”
- Stochastic Approximations and Differential Inclusions (2005, methodology): “This method was introduced by Ljung [24] and extensively studied thereafter (see, e.”
- New Criteria and a New Algorithm for Learning in Multi-Agent Systems (2004, background): “We therefore propose requiring the algorithm achieve at least the value of some Nash equilibrium that is Pareto effi cient over the set of Nash equilibria.2 Similarly, algorithms exist that satisfy ‘universal consi stency’ and if played by all agents will converge to a correlated equilibria[ 10 ], b”
- Dynamic Thresholding and Pruning for Regret Minimization (2017, methodology): “By far the most popular regret-minimizing algorithm to use within CFR is regret matching (RM) and variants of RM [15, 12, 11, 5].”
- Joint Strategy Fictitious Play with Inertia for Potential Games (2005, positive): “It turns out that there is a strong similarity between JSFP and the regret matching algorithm [22].”
- Rethinking Formal Models of Partially Observable Multiagent Decision Making (2019, background): “the general category of a policy improvement algorithm, and can be compactly described as self-play with independent instances of the regret-matching algorithm (Hart and Mas-Colell, 2000) operating over the actions at each information state for each player, using a particular notion of expected rewa”