Counterfactual regret minimization in sequential security games
- Viliam Lisy
- Trevor Davis
- Michael Bowling, University of Alberta
Many real world security problems can be modelled as finite zero-sum games with structured sequential strategies and limited interactions between the players. An abstract class of games unifying these models are the normal-form games with sequential strategies (NFGSS). We show that all games from this class can be modelled as well-formed imperfect-recall extensive-form games and consequently can be solved by counterfactual regret minimization. We propose an adaptation of the CFR+ algorithm for NFGSS and compare its performance to the standard methods based on linear programming and incremental game generation. We validate our approach on two security-inspired domains. We show that with a negligible loss in precision, CFR+ can compute a Nash equilibrium with five times less computation than its competitors.
Citation
V. Lisy, T. Davis, M. Bowling. "Counterfactual regret minimization in sequential security games". National Conference on Artificial Intelligence (AAAI), (ed: Dale Schuurmans, Michael P. Wellman), pp 544-550, February 2016.| Keywords: | counterfactual regret minimization, sequential game, imperfect information, extensive form game |
| Category: | In Conference |
| Web Links: | AAAI |
BibTeX
@incollection{Lisy+al:AAAI16,
author = {Viliam Lisy and Trevor Davis and Michael Bowling},
title = {Counterfactual regret minimization in sequential security games},
Editor = {Dale Schuurmans, Michael P. Wellman},
Pages = {544-550},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2016,
}Last Updated: October 28, 2020Submitted by Sabina P
