Regret Minimization in Games with Incomplete Information

By Martin A. Zinkevich, Michael Bradley Johanson, Michael H. Bowling, Carmelo Piccione. 2007

899 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Management Science and Operations Research, 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 Game & Decision Theory

Citations in the corpus

OpenSpiel: A Framework for Reinforcement Learning in Games (2019, background): “Counterfactual Regret Minimization Counterfactual regret (CFR) minimization is a policy iteration algorithm for computing approximate equilibra in two-player zero-sum games [78].”
DeepStack: Expert-level artificial intelligence in heads-up no-limit poker (2017, methodology): “tion (CFR) (14, 17, 18) is one such technique that uses selfplay to do recursive reasoning through adapting its strategy against itself over successive iterations.”
The Hanabi Challenge: A New Frontier for AI Research (2019, background): “In the competitive case, such as poker, strong play required new algorithmic foundations [71,72,14,13].”
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).”
A Unified Game-Theoretic Approach to Multiagent Reinforcement Learning (2017, background): “We now show results for a Leduc poker where strong benchmark algorithms exist, such as counterfactual regret (CFR) minimization [107, 11].”
A survey and critique of multiagent deep reinforcement learning (2018, methodology): “7 Counterfactual regret minimization is a technique for solving large games based on regret minimization [133, 134] due to a well-known connection between regret and Nash equilibria [135].”
Online Monte Carlo Counterfactual Regret Minimization for Search in Imperfect Information Games (2015, background): “…the algorithm maintains for each information set the average strategy proﬁle where P The combination of the coun-terfactual regret minimizers in individual information sets also minimizes the overall average regret [38], and hence the average proﬁle is a 2 ǫ -equilibrium, with ǫ → 0 as T → ∞ .”
Poker-CNN: A Pattern Learning Strategy for Making Draws and Bets in Poker Games Using Convolutional Networks (2015, background): “Second, because quite a few poker games have a search space larger than heads-up limit Texas Hold’em, it is very difficult to traverse the game states and find the best responses (Zinkevich et al. 2007) (Johanson et al. 2011) (Johanson et al. 2013a) for those games.”
Solving Games with Functional Regret Estimation (2014, methodology): “To generate strategies, chance sampling CFR (Zinkevich et al. 2007) was run for 100000 iterations to solve each abstract game.”
Counterfactual VQA: A Cause-Effect Look at Language Bias (2020, background): “The machine learning community has also made efforts in treatment effect estimation [39, 40, 41] and real-world applications [42, 43, 44, 28, 45, 46, 47].”
Maximin effects in inhomogeneous large-scale data (2014, background): “…have also been explored in game theoretical aspects of decision theory and machine learning, for example, in Cesa-Bianchi and Lugosi (2006) and Zinkevich et al. (2007), and bandit-type problems and on-line decision problems, [e.g., Audibert, Bubeck and Lugosi (2014), Auer, Cesa-Bianchi and…”
Measuring the Size of Large No-Limit Poker Games (2013, methodology): “In the ﬁrst paper on approximating a Nash equilibrium strategy for the game, Billings et al. presented a ﬁgure illustrating the branching factor of the game [3, Figure 1].”
Tractable Objectives for Robust Policy Optimization (2012, background): “Counterfactual regret minimization (CFR) is one such approach [21].”
Smoothing Techniques for Computing Nash Equilibria of Sequential Games (2010, neutral): “[23]).”
Solving Imperfect Information Games Using Decomposition (2013, methodology): “CFR is an iterated self play algorithm, where the average policy across all iterations approaches a Nash equilibrium (Zinkevich et al. 2008).”
Endgame Solving in Large Imperfect-Information Games (2015, methodology): “Solving the river endgames, as opposed to the flop endgames which the prior approach does, is very important because CFR only occasionally samples from a specific river endgame during the course of the initial equilibrium computation, while it very frequently samples from the flop endgames that foll”
Dynamic Thresholding and Pruning for Regret Minimization (2017, methodology): “In CFR, the strategy vector for each information set is determined according to a regret-minimization algorithm (Zinkevich et al. 2007).”
Joint Policy Search for Multi-agent Collaboration with Imperfect Information (2020, methodology): “Both CFR [44] and CFR1k+JPS repeats with 1k different seeds.”
Pommerman: A Multi-Agent Playground (2018, methodology): “These benchmarks have also lead to the discovery of new algorithms and approaches like Monte Carlo Tree Search (Vodopivec, Samothrakis, and ˇSter 2017; Browne et al. 2012; Kocsis and Szepesv´ari 2006; Coulom 2006) and Counterfactual Regret Minimization (Zinkevich et al. 2008).”
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].”