Gradient-Based Algorithms for Finding Nash Equilibria in Extensive Form Games

By Andrew Gilpin, Samid Hoda, Javier F. Peña, Tuomas Sandholm. 2007

73 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, Optimization & Training, Game & Decision Theory

How researchers see this paper

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

In Artificial Intelligence

In Management Science and Operations Research

In Optimization & Training

In Game & Decision Theory

Citations in the corpus

Deep Reinforcement Learning from Self-Play in Imperfect-Information Games (2016, background): “In computer poker, current game-theoretic approaches use heuristics of card strength to abstract the game to a tractable size (Zinkevich et al., 2007; Gilpin et al., 2007; Johanson et al., 2013).”
Smoothing Techniques for Computing Nash Equilibria of Sequential Games (2010, methodology): “In the paper describing our implementation [2], we present an implicit representation for poker that is based on constructing A using Kronecker products of smaller matrices.”
Regret Minimization in Games with Incomplete Information (2007, background): “More recently, abstractions involving full four round games with the full four bets per round have proven to be a significant improvement [7, 6].”
A Practical Use of Imperfect Recall (2009, methodology): “more rapidly and use fewer resources than a standard linear program solver (Gilpin et al. 2007).”
Competitive Gradient Descent (2019, background): “For certain structured problems, Gilpin et al. (2007) use techniques from convex optimization (Nesterov, 2005) to minimize the implicitly deﬁned F .”
Computer poker: A review (2011, methodology): “The EGT algorithm presented by [30] is an iterative, anytime algorithm that requires O (1/!) iterations to approach an !-Nash equilibrium.”
Using counterfactual regret minimization to create competitive multiplayer poker agents (2010, methodology): “Some research on multiplayer extensive games has been done for a simple poker variant [4].”
Measuring the Size of Large No-Limit Poker Games (2013, background): “Over the last decade, heads-up limit Texas hold’em has become a common testbed for researchers studying computational game theory in imperfect information games, with signiﬁcant eﬀorts towards approximating optimal strategies for the game [3, 11, 6, 4].”
The State of Solving Large Incomplete-Information Games, and Application to Poker (2010, background): “We can thus exploit the problem structure to store only an implicit representation of A (Gilpin et al. 2007).”
Fictitious Self-Play in Extensive-Form Games (2015, methodology): “The most popular modern techniques are either optimizationbased (Koller et al., 1996; Gilpin et al., 2007; Miltersen & Sørensen, 2010; Bosansky et al., 2014) or perform regret minimization (Zinkevich et al., 2007).”
Abstraction pathologies in extensive games (2009, methodology): “In the past three years, a number of competing techniques have been developed by competitors in the AAAI Computer Poker Competitions [15], with some now able to solve games with about 10(12) game states [14, 3].”
Time and Space: Why Imperfect Information Games are Hard (2018, methodology): “based on accelerated gradient descent methods [31].”