Monte Carlo Sampling for Regret Minimization in Extensive Games

By Marc Lanctot, Kevin Waugh, Martin A. Zinkevich, Michael H. Bowling. 2009

353 citations recorded by the source corpus.

Subfields: General Decision Sciences, Management Science and Operations Research, Probabilistic & Bayesian Methods, 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 General Decision Sciences

In Management Science and Operations Research

In Probabilistic & Bayesian Methods

In Game & Decision Theory

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, methodology): “In addition to basic CFR, OpenSpiel contains a few variants of Monte Carlo CFR [34] such as outcome sampling and external sampling, and CFR+ [69].”
Tractable Objectives for Robust Policy Optimization (2012, background): “In the past five years there have been dramatic advances in solving large zero-sum extensive-form games with imperfect information [21, 5, 8].”
Fictitious Self-Play in Extensive-Form Games (2015, methodology): “Counterfactual regret minimization (CFR) is the first approach which essentially solved an imperfect-information game of real-world scale (Bowling et al., 2015).”
Self-play Monte-Carlo tree search in computer poker (2014, background): “(Lanctot et al. 2009), these are generally full-width methods and therefore are particularly exposed to the curse of dimensionality.”
Computing Approximate Nash Equilibria and Robust Best-Responses Using Sampling (2011, neutral): “In our experiments, we confirm this finding: the algorithm can indeed learn reasonably strong policies in Poker, with the drawback that these strategies are not necessarily a NE. MCCFR on the other hand has already been shown to converge to a NE in smaller imperfect information games, such as the on”
Deep Counterfactual Regret Minimization (2018, methodology): “However, external sampling may be impractical in games with extremely large branching factors, so a different sampling scheme, such as outcome sampling (Lanctot et al., 2009), may be desired in those cases.”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “When the abstractions are constructed, an improved version of the Monte-Carlo CFR (Lanctot et al., 2009; Burch et al., 2012; Gibson et al., 2012) is utilized to compute the policy.”
The State of Solving Large Incomplete-Information Games, and Application to Poker (2010, background): “Other forms of sampling can also be used (Lanctot et al. 2009).”
Finding Optimal Abstract Strategies in Extensive-Form Games (2012, methodology): “Monte-Carlo CFR (MCCFR) is a family of sampling variants of CFR in which some of the actions in a game, such as the chance events, can be sampled instead of enumerated (Lanctot et al. 2009).”
Opponent Modeling by Expectation–Maximization and Sequence Prediction in Simplified Poker (2017, neutral): “iterations is bounded by theory [27], we cannot yet say how our algorithm affects this.”
Time and Space: Why Imperfect Information Games are Hard (2018, background): “We also know that for all I, ∑T t=1 ∑ I∈B χ σt −p(I)/ξp(B) ≤ T , so by Lemma 6 of [58], ∑ I∈B √∑T t=1(χ σt −p(I)/ξp(B)) 2 ≤ √ |B|T and we have”
Computer poker: A review (2011, background): “MCCFR has been shown to converge to a Nash equilibrium much faster than standard CFR in several game domains [52].”
Joint Policy Search for Multi-agent Collaboration with Imperfect Information (2020, background): “For imperfect information games (IG), Double-Oracle [26], Fictitious (self-)play [20] and Counterfactual Regret Minimization (CFR [44, 23]) can be proven to achieve Nash equilibrium.”
Depth-Limited Solving for Imperfect-Information Games (2018, methodology): “This abstraction was approximately solved by running Monte Carlo Counterfactual Regret Minimization for 700 core hours [22].”