Not Logged In

Evaluating state-space abstractions in extensive-form games

Efficient algorithms exist for finding optimal policies in extensive-form games. However, human-scale problems are typically so large that this computation remains infeasible with modern computing resources. State-space abstraction techniques allow for the derivation of a smaller and strategically similar abstract domain, in which an optimal strategy can be computed and then used as a suboptimal strategy in the real domain. In this paper, we consider the task of evaluating the quality of an abstraction, independent of a specific abstract strategy. In particular, we use a recent metric for abstraction quality and examine imperfect recall abstractions, in which agents "forget" previously observed information to focus the abstraction effort on more recent and relevant state information. We present experimental results in the domain of Texas hold'em poker that validate the use of distribution-aware abstractions over expectation-based approaches, demonstrate that the new metric better predicts tournament performance, and show that abstractions built using imperfect recall outperform those built using perfect recall in terms of both exploitability and one-on-one play.

Citation

M. Johanson, N. Burch, R. Valenzano, M. Bowling. "Evaluating state-space abstractions in extensive-form games". Joint Conference on Autonomous Agents and Multi-Agent Systems (AAMAS), (ed: Maria L. Gini, Onn Shehory, Takayuki Ito, Catholijn M. Jonker), pp 271-278, May 2013.

Keywords:  
Category: In Conference
Web Links: ACM Digital Library

BibTeX

@incollection{Johanson+al:AAMAS13,
  author = {Michael Johanson and Neil Burch and Richard Valenzano and Michael
    Bowling},
  title = {Evaluating state-space abstractions in extensive-form games},
  Editor = {Maria L. Gini, Onn Shehory, Takayuki Ito, Catholijn M. Jonker},
  Pages = {271-278},
  booktitle = {Joint Conference on Autonomous Agents and Multi-Agent Systems
    (AAMAS)},
  year = 2013,
}

Last Updated: October 29, 2020
Submitted by Sabina P

University of Alberta Logo AICML Logo