Smoothing Techniques for Computing Nash Equilibria of Sequential Games

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

189 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Economics and Econometrics, Management Science and Operations Research

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 Economics and Econometrics

In Management Science and Operations Research

Citations in the corpus

Tractable Objectives for Robust Policy Optimization (2012, background): “A worst-case analysis in such a formulation is non-sensical, except in the case of distributions with bounded support (i.e. Uniform distributions), in which case it offers nothing over uncertainty sets.”
Time and Space: Why Imperfect Information Games are Hard (2018, unknown): “solved this problem by introducing a recursively constructed prox function for sequence form problems, based on a choice of a base prox function at each information set [38].”
Deep Counterfactual Regret Minimization (2018, methodology): “…algorithms have been shown to minimize regret when parameters are tuned appropriately [26] but the performance of these algorithms is comparable to NFSP. First-order methods converge to a Nash equilibrium in O (1 /T ) [12, 16], which is far better than CFR’s theoretical bound of O (1 / √ T ) .”
Hierarchical Abstraction, Distributed Equilibrium Computation, and Post-Processing, with Application to a Champion No-Limit Texas Hold'em Agent (2015, background): “The leading approach for creating strong agents for large imperfect-information games—which is used by all of the strongest Texas Hold’em (TH) poker agents—is to first create a sufficiently small strategic approximation of the full game, called an abstraction, then to apply an equilibriumfinding alg”
The State of Solving Large Incomplete-Information Games, and Application to Poker (2010, background): “…then the conjugate d∗ is Lipschitz continuous, differentiable everywhere, and If the prox-function’s conjugate and the conjugate’s gradient are computable quickly (and the prox-function is continuous, strongly convex, and differentiable), we say that the prox-function is nice (Hoda et al. 2010).”
Finding Optimal Abstract Strategies in Extensive-Form Games (2012, methodology): “They have been used to model a variety of scenarios including game playing (Zinkevich et al. 2008; Lanctot et al. 2009; Hoda et al. 2010; Risk and Szafron 2010), bargaining and negotiation (Lazaric, de Cote, and Gatti 2007; Gatti 2008), argumentation (Procaccia and Rosenschein 2005), and even distri”
An Exact Double-Oracle Algorithm for Zero-Sum Extensive-Form Games with Imperfect Information (2014, methodology): “Another popular method is Excessive Gap Technique that exploits the convex properties of the sequence-form representation and uses recent mathematical results on finding extreme points of smooth functions (see Hoda et al., 2010, for the details).”
Dynamic Thresholding and Pruning for Regret Minimization (2017, methodology): “For EGT, the results using c = {0.001, 0.005, 0.01} are all similar and beneficial, while using a value of 0.05 is too aggressive, and hurts performance slightly.”
Stochastic Mirror Descent: Convergence Analysis and Adaptive Variants via the Mirror Stochastic Polyak Stepsize (2021, background): “For example, in sequential games particular instances of mirror descent have been designed to allow for efficient projections on the strategy spaces of players (Hoda et al., 2010; Kroer et al., 2020).”
Self-play Monte-Carlo tree search in computer poker (2014, methodology): “Common game-theoretic methods in computer poker are based on linear programming (Billings et al. 2003; Gilpin and Sandholm 2006), nonsmooth convex optimization (Hoda et al. 2010), fictitious play (Ganzfried and Sandholm 2008) or counterfactual regret minimization (CFR) (Zinkevich et al. 2007).”
Endgame Solving in Large Imperfect-Information Games (2015, methodology): “To address such large games, newer approximate equilibriumfinding algorithms have been developed that scale to games with around 10 14 nodes, such as counterfactual regret minimization (CFR) [21] and an algorithm based on the excessive gap technique (EGT) [10].”