Kevin Waugh

AAAI Conference 2019 Conference Paper

Solving Large Extensive-Form Games with Strategy Constraints

• Trevor Davis
• Kevin Waugh
• Michael Bowling

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.

AAAI Conference 2015 Conference Paper

Solving Games with Functional Regret Estimation

• Kevin Waugh
• Dustin Morrill
• James Bagnell
• Michael Bowling

We propose a novel online learning method for minimizing regret in large extensive-form games. The approach learns a function approximator online to estimate the regret for choosing a particular action. A noregret algorithm uses these estimates in place of the true regrets to define a sequence of policies. We prove the approach sound by providing a bound relating the quality of the function approximation and regret of the algorithm. A corollary being that the method is guaranteed to converge to a Nash equilibrium in selfplay so long as the regrets are ultimately realizable by the function approximator. Our technique can be understood as a principled generalization of existing work on abstraction in large games; in our work, both the abstraction as well as the equilibrium are learned during self-play. We demonstrate empirically the method achieves higher quality strategies than state-of-the-art abstraction techniques given the same resources.

IROS Conference 2012 Conference Paper

Space-time localization and registration on the beating heart

• Nathan A. Wood
• Kevin Waugh
• Tian Yu Tommy Liu
• Marco A. Zenati
• Cameron N. Riviere

This paper presents a framework for localizing a miniature epicardial crawling robot, HeartLander, on the beating heart using only 6-degree-of-freedom position measurements from an electromagnetic position tracker and a dynamic surface model of the heart. Using only this information, motion and observation models of the system are developed such that a particle filter can accurately estimate not only the location of the robot on the surface of the heart, but also the pose of the heart in the world coordinate frame as well as the current physiological phase of the heart. The presented framework is then demonstrated in simulation on a dynamic 3-D model of the human heart and a robot motion model which accurately mimics the behavior of the HeartLander robot.

AAMAS Conference 2012 Conference Paper

Strategy Purification and Thresholding: Effective Non-Equilibrium Approaches for Playing Large Games

• Sam Ganzfried
• Tuomas Sandholm
• Kevin Waugh

There has been significant recent interest in computing effective strategies for playing large imperfect-information games. Much prior work involves computing an approximate equilibrium strategy in a smaller abstract game, then playing this strategy in the full game (with the hope that it also well approximates an equilibrium in the full game). In this paper, we present a family of modifications to this approach that work by constructing non-equilibrium strategies in the abstract game, which are then played in the full game. Our new procedures, called \emph{purification} and \emph{thresholding}, modify the action probabilities of an abstract equilibrium by preferring the higher-probability actions. Using a variety of domains, we show that these approaches lead to significantly stronger play than the standard equilibrium approach. As one example, our program that uses purification came in first place in the two-player no-limit Texas Hold'em total bankroll division of the 2010 Annual Computer Poker Competition. Surprisingly, we also show that purification significantly improves performance (against the full equilibrium strategy) in random 4 x 4 matrix games using random 3 x 3 abstractions. We present several additional results (both theoretical and empirical). Overall, one can view these approaches as ways of achieving robustness against overfitting one's strategy to one's lossy abstraction. Perhaps surprisingly, the performance gains do not necessarily come at the expense of worst-case exploitability.

IJCAI Conference 2011 Conference Paper

Accelerating Best Response Calculation in Large Extensive Games

• Michael Johanson
• Kevin Waugh
• Michael Bowling
• Martin Zinkevich

One fundamental evaluation criteria of an AI technique is its performance in the worst-case. For static strategies in extensive games, this can be computed using a best response computation. Conventionally, this requires a full game tree traversal. For very large games, such as poker, that traversal is infeasible to perform on modern hardware. In this paper, we detail a general technique for best response computations that can often avoid a full game tree traversal. Additionally, our method is specifically well-suited for parallel environments. We apply this approach to computing the worst-case performance of a number of strategies in heads-up limit Texas hold'em, which, prior to this work, was not possible. We explore these results thoroughly as they provide insight into the effects of abstraction on worst-case performance in large imperfect information games. This is a topic that has received much attention, but could not previously be examined outside of toy domains.

ICML Conference 2011 Conference Paper

Computational Rationalization: The Inverse Equilibrium Problem

• Kevin Waugh
• Brian D. Ziebart
• J. Andrew Bagnell

AAMAS Conference 2011 Conference Paper

Strategy Purification

• Sam Ganzfried
• Tuomas Sandholm
• Kevin Waugh

There has been significant recent interest in computing good strategies for large games. Most prior work involves computing an approximate equilibrium strategy in a smaller abstract game, then playing this strategy in the full game. In this paper, we present a modification of this approach that works by constructing a deterministic strategy in the full game from the solution to the abstract game; we refer to this procedure as purification. We show that purification, and its generalization which we call thresholding, lead to significantly stronger play than the standard approach in a wide variety of experimental domains. One can view these approaches as ways of achieving robustness against one's own lossy abstraction.

AAMAS Conference 2009 Conference Paper

Abstraction Pathologies in Extensive Games

• Kevin Waugh
• David Schnizlein
• Michael Bowling
• Duane Szafron

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.

NeurIPS Conference 2009 Conference Paper

Monte Carlo Sampling for Regret Minimization in Extensive Games

• Marc Lanctot
• Kevin Waugh
• Martin Zinkevich
• Michael Bowling

Sequential decision-making with multiple agents and imperfect information is commonly modeled as an extensive game. One efficient method for computing Nash equilibria in large, zero-sum, imperfect information games is counterfactual regret minimization (CFR). In the domain of poker, CFR has proven effective, particularly when using a domain-specific augmentation involving chance outcome sampling. In this paper, we describe a general family of domain independent CFR sample-based algorithms called Monte Carlo counterfactual regret minimization (MCCFR) of which the original and poker-specific versions are special cases. We start by showing that MCCFR performs the same regret updates as CFR on expectation. Then, we introduce two sampling schemes: {\it outcome sampling} and {\it external sampling}, showing that both have bounded overall regret with high probability. Thus, they can compute an approximate equilibrium using self-play. Finally, we prove a new tighter bound on the regret for the original CFR algorithm and relate this new bound to MCCFRs bounds. We show empirically that, although the sample-based algorithms require more iterations, their lower cost per iteration can lead to dramatically faster convergence in various games.

NeurIPS Conference 2009 Conference Paper

Strategy Grafting in Extensive Games

• Kevin Waugh
• Nolan Bard
• Michael Bowling

Extensive games are often used to model the interactions of multiple agents within an environment. Much recent work has focused on increasing the size of an extensive game that can be feasibly solved. Despite these improvements, many interesting games are still too large for such techniques. A common approach for computing strategies in these large games is to first employ an abstraction technique to reduce the original game to an abstract game that is of a manageable size. This abstract game is then solved and the resulting strategy is used in the original game. Most top programs in recent AAAI Computer Poker Competitions use this approach. The trend in this competition has been that strategies found in larger abstract games tend to beat strategies found in smaller abstract games. These larger abstract games have more expressive strategy spaces and therefore contain better strategies. In this paper we present a new method for computing strategies in large games. This method allows us to compute more expressive strategies without increasing the size of abstract games that we are required to solve. We demonstrate the power of the approach experimentally in both small and large games, while also providing a theoretical justification for the resulting improvement.