Deep Counterfactual Regret Minimization

By Noam Brown, Adam Lerer, Sam Gross, Tuomas Sandholm. 2018

256 citations recorded by the source corpus.

Counterfactual Regret Minimization (CFR) is the leading framework for solving large imperfect-information games. It converges to an equilibrium by iteratively traversing the game tree. In order to deal with extremely large games, abstraction is typically applied before running CFR. The abstracted game is solved with tabular CFR, and its solution is mapped back to the full game. This process can be problematic because aspects of abstraction are often manual and domain specific, abstraction algorithms may miss important strategic nuances of the game, and there is a chicken-and-egg problem because determining a good abstraction requires knowledge of the equilibrium of the game. This paper introduces Deep Counterfactual Regret Minimization, a form of CFR that obviates the need for abstraction by instead using deep neural networks to approximate the behavior of CFR in the full game. We show that Deep CFR is principled and achieves strong performance in large poker games. This is the first non-tabular variant of CFR to be successful in large games.

Subfields: Artificial Intelligence, Clinical Psychology, Reinforcement Learning, Game & Decision Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

1. Sergey Levine
2. Pieter Abbeel
3. Yoshua Bengio
4. Yuxi Li
5. Zhuoran Yang
6. Ruslan Salakhutdinov
7. Chelsea Finn
8. Caiming Xiong

In Clinical Psychology

1. Zhuoran Yang
2. Kaiqing Zhang
3. Tamer Basar
4. Dustin Morrill

In Reinforcement Learning

1. Sergey Levine
2. Zhuoran Yang
3. Pieter Abbeel
4. R´emi Munos
5. Yuxi Li
6. Shimon Whiteson
7. Karl Tuyls
8. Chelsea Finn

In Game & Decision Theory

1. Zhuoran Yang
2. Karl Tuyls
3. Julien Pérolat
4. Tamer Basar
5. Kaiqing Zhang
6. Jean-Baptiste Lespiau
7. R´emi Munos
8. Shayegan Omidshafiei

Citations in the corpus

• OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “Deep CFR [14] applies these ideas to a significantly larger game using convolutional networks, external sampling Monte Carlo CFR, and–like NFSP–a reservoir-sampled buffer.”
• Neural Replicator Dynamics (2019, methodology): “These include approaches relying on self-play [23], regret minimization [9, 10, 12, 34, 43, 69], and a large body of works that assume a standard centralized learning, decentralized execution paradigm [18, 35, 44, 51].”
• Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “For example, [281, 282, 283, 284, 285, 286] combine CFR with Monte-Carlo sampling; [287, 288, 289] propose to estimate the counterfactual value functions via regression; [290, 291, 292] improve the computational efficiency by pruning suboptimal paths in the game tree; [293, 294, 295] analyze the per”
• Adversarial Policies: Attacking Deep Reinforcement Learning (2019, methodology): “Consequently, we urge caution when using methods such as self-play that assume transitivity, and would recommend more general methods where practical (Balduzzi et al., 2019; Brown et al., 2019).”
• Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent (2019, methodology): “Combining data buffers with CFR using regression to predict regrets has also shown promise in medium-sized poker variants [Waugh et al. , 2015; Brown et al. , 2018 ] .”