Solving Large Extensive-Form Games with Strategy Constraints
- Trevor Davis
- Kevin Waugh
- Michael Bowling, University of Alberta
Extensive-form games are a common model for multiagent interactions with imperfect information. In two-player zerosum games, the typical solution concept is a Nash equilibrium over the unconstrained strategy set for each player. In many situations, however, we would like to constrain the set of possible strategies. For example, constraints are a natural way to model limited resources, risk mitigation, safety, consistency with past observations of behavior, or other secondary objectives for an agent. In small games, optimal strategies under linear constraints can be found by solving a linear program; however, state-of-the-art algorithms for solving large games cannot handle general constraints. In this work we introduce a generalized form of Counterfactual Regret Minimization that provably finds optimal strategies under any feasible set of convex constraints. We demonstrate the effectiveness of our algorithm for finding strategies that mitigate risk in security games, and for opponent modeling in poker games when given only partial observations of private information.
Citation
T. Davis, K. Waugh, M. Bowling. "Solving Large Extensive-Form Games with Strategy Constraints". National Conference on Artificial Intelligence (AAAI), pp 1861-1868, January 2019.| Keywords: | |
| Category: | In Conference |
| Web Links: | DOI |
| AAAI |
BibTeX
@incollection{Davis+al:AAAI19,
author = {Trevor Davis and Kevin Waugh and Michael Bowling},
title = {Solving Large Extensive-Form Games with Strategy Constraints},
Pages = {1861-1868},
booktitle = {National Conference on Artificial Intelligence (AAAI)},
year = 2019,
}Last Updated: February 21, 2020Submitted by Sabina P
