Finding Optimal Abstract Strategies in Extensive-Form Games

By Michael Bradley Johanson, Nolan Bard, Neil Burch, Michael H. Bowling. 2012

85 citations recorded by the source corpus.

Extensive-form games are a powerful model for representing interactions between agents. Nash equilibrium strategies are a common solution concept for extensive-form games and, in two-player zero-sum games, there are efficient algorithms for calculating such strategies. In large games, this computation may require too much memory and time to be tractable. A standard approach in such cases is to apply a lossy state-space abstraction technique to produce a smaller abstract game that can be tractably solved, while hoping that the resulting abstract game equilibrium is close to an equilibrium strategy in the unabstracted game. Recent work has shown that this assumption is unreliable, and an arbitrary Nash equilibrium in the abstract game is unlikely to be even near the least suboptimal strategy that can be represented in that space. In this work, we present for the first time an algorithm which efficiently finds optimal abstract strategies --- strategies with minimal exploitability in the unabstracted game. We use this technique to find the least exploitable strategy ever reported for two-player limit Texas hold'em.

Subfields: Artificial Intelligence, 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

In Management Science and Operations Research

In Game & Decision Theory

Citations in the corpus

A survey and critique of multiagent deep reinforcement learning (2018, background): “This algorithm is similar to CFR-BR [138] and has the main advantage that the current policy convergences rather than the average policy, so there is no need to learn the average strategy, which requires large reservoir buffers or many past networks.”
Tractable Objectives for Robust Policy Optimization (2012, background): “A recent variant of CFR, called CFR-BR, specifically addresses the challenge of an adversary having an intractably large strategy space [6].”
Solving Imperfect Information Games Using Decomposition (2013, methodology): “The CFR-BR algorithm (Johanson et al. 2012a) uses these properties, and provided the inspiration for the CFR-D algorithm.”
Computing Approximate Equilibria in Sequential Adversarial Games by Exploitability Descent (2019, methodology): “When using the counterfactual values, ED then turns into CFR-BR(hedge).”
Multi-Agent Reinforcement Learning: A Selective Overview of Theories and Algorithms (2019, methodology): “This method is equivalent to the CFR-BR algorithm [299] with Hedge.”
Depth-Limited Solving for Imperfect-Information Games (2018, methodology): “One option, which achieves the best empirical results and is what we use, involves ﬁrst abstracting the game [19, 12] and then applying the iterative algorithm Monte Carlo Counterfactual Regret Minimization [22].”
Measuring the Size of Large No-Limit Poker Games (2013, methodology): “In the ﬁrst paper on approximating a Nash equilibrium strategy for the game, Billings et al. presented a ﬁgure illustrating the branching factor of the game [3, Figure 1].”
Time and Space: Why Imperfect Information Games are Hard (2018, methodology): “The flexible framework of regret minimisation allows special purpose variants of CFR like CFR-BR [45] which uses a best response for one player, or MCCFR using game specific sampling schemes.”
Evaluating state-space abstractions in extensive-form games (2013, unknown): “Johanson et al. also demonstrated that CFR-BR could be used for evaluating abstractions by measuring the closest approximation to a Nash equilibrium that can be represented by the abstraction [10].”