Abstraction pathologies in extensive games

By Kevin Waugh, David Schnizlein, Michael H. Bowling, Duane Szafron. 2009

90 citations recorded by the source corpus.

Extensive games can be used to model many scenarios in which multiple agents interact with an environment. There has been considerable recent research on finding strong strategies in very large, zero-sum extensive games. The standard approach in such work is to employ abstraction techniques to derive a more tractably sized game. An extensive game solver is then employed to compute an equilibrium in that abstract game, and the resulting strategy is presumed to be strong in the full game. Progress in this line of research has focused on solving larger abstract games, which more closely resemble the full game. However, there is an underlying assumption that by abstracting less, and solving a larger game, an agent will have a stronger strategy in the full game. In this work we show that this assumption is not true in general. Refining an abstraction can actually lead to a weaker strategy. We show examples of these abstraction pathologies in a small game of poker that can be analyzed exactly. These examples show that pathologies arise when abstracting both chance nodes as well as a player's actions. In summary, this paper shows that the standard approach to finding strong strategies for large extensive games rests on shaky ground.

How researchers see this paper

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

Citations in the corpus

Lossy stochastic game abstraction with bounds (2012, methodology): “, [22, 10, 7, 8, 9, 12, 27, 13, 11, 24, 25]) and manually-generated game abstractions (e.”
Dynamic Thresholding and Pruning for Regret Minimization (2017, background): “In two-player zero-sum games, if both players’ average regret satisfies R T i T ✏, their average strategies h̄T1 , ̄T2 i form a 2✏-equilibrium (Waugh et al. 2009).”
Solving Imperfect Information Games Using Decomposition (2013, methodology): “To show that re-solving subgames introduces at most an arbitrarily small exploitability, we use the game of Leduc Hold’em poker, a popular research testbed for imperfect information games (Waugh et al. 2009; Ganzfried, Sandholm, and Waugh 2011).”
Solving Games with Functional Regret Estimation (2014, background): “Though this turns out to be false (Waugh et al. 2008), it appears to not occur with any significance in the large games of interest (Johanson et al.”
Finding Optimal Abstract Strategies in Extensive-Form Games (2012, methodology): “However, Waugh et al. have shown that different abstract game equilibria can have a wide range of exploitability (Waugh et al. 2009a, Table 3), making this approach unreliable.”
Time and Space: Why Imperfect Information Games are Hard (2018, background): “It is possible to see pathological behaviour where the exploitability of an abstract strategy increases when using a larger abstraction, even if the larger abstraction is a strict refinement of the smaller abstraction [92].”
Computer poker: A review (2011, background): “Generally, increases in the size of the model (the less abstraction that is used) correlate with improvements in performance (see Waugh and colleagues discussion on abstraction pathologies [96] for why this is not always the case).”
Self-play Monte-Carlo tree search in computer poker (2014, background): “The following definition is similar to (Waugh et al. 2009) but makes use of information functions.”