Solving Games with Functional Regret Estimation

By Kevin Waugh, Dustin Morrill, J. Bagnell, Michael H. Bowling. 2014

62 citations recorded by the source corpus.

We propose a novel online learning method for minimizing regret in large extensive-form games. The approach learns a function approximator online to estimate the regret for choosing a particular action. A no-regret algorithm uses these estimates in place of the true regrets to define a sequence of policies. We prove the approach sound by providing a bound relating the quality of the function approximation and regret of the algorithm. A corollary being that the method is guaranteed to converge to a Nash equilibrium in self-play so long as the regrets are ultimately realizable by the function approximator. Our technique can be understood as a principled generalization of existing work onabstraction in large games; in our work, both the abstraction as well as the equilibrium are learned during self-play. We demonstrate empirically the method achieves higher quality strategies than state-of-the-art abstraction techniques given the same resources.

Subfields: Artificial Intelligence, Economics and Econometrics, Management Science and Operations Research, 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. Zhuoran Yang
4. Yuxi Li
5. R´emi Munos
6. Karl Tuyls
7. Yoshua Bengio
8. Marc Lanctot

In Economics and Econometrics

1. Marc Lanctot
2. Noam Brown
3. R´emi Munos
4. Karl Tuyls
5. Julien Pérolat
6. Tuomas Sandholm
7. David Silver
8. Johannes Heinrich

In Management Science and Operations Research

1. David Silver
2. Zhuoran Yang
3. Marc Lanctot
4. Karl Tuyls
5. Johannes Heinrich
6. Kaiqing Zhang
7. Tamer Basar
8. Noam Brown

In Game & Decision Theory

1. Karl Tuyls
2. Julien Pérolat
3. Marc Lanctot
4. Zhuoran Yang
5. Noam Brown
6. Tuomas Sandholm
7. Tamer Basar
8. Kaiqing Zhang

Citations in the corpus

• OpenSpiel: A Framework for Reinforcement Learning in Games (2019, methodology): “Regression CFR Regression CFR (RCFR) was the first variant to combine RL-style function approximation with CFR techniques [73, 46].”
• Deep Reinforcement Learning from Self-Play in Imperfect-Information Games (2016, methodology): “Waugh et al. (2015) recently combined one of these methods with function approximation.”
• Deep Counterfactual Regret Minimization (2018, methodology): “Prior work has combined regression tree function approximation with CFR (Waugh et al., 2015) in an algorithm called Regression CFR (RCFR).”
• 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].”
• 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 ] .”
• 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”
• Actor-Critic Policy Optimization in Partially Observable Multiagent Environments (2018, methodology): “Regression CFR (RCFR) uses regression to estimate cumulative regrets from CFR [93].”