mlsanityData to 7 Oct 2026

Abstracting Imperfect Information Away from Two-Player Zero-Sum Games

arXiv 2301.09159 ↗First posted 22 Jan 2023cs.GT cs.AI cs.LGcited by 6

Not on the map. Why?

Abstract (arXiv)

In their seminal work, Nayyar et al. (2013) showed that imperfect information can be abstracted away from common-payoff games by having players publicly announce their policies as they play. This insight underpins sound solvers and decision-time planning algorithms for common-payoff games. Unfortunately, a naive application of the same insight to two-player zero-sum games fails because Nash equilibria of the game with public policy announcements may not correspond to Nash equilibria of the original game. As a consequence, existing sound decision-time planning algorithms require complicated additional mechanisms that have unappealing properties. The main contribution of this work is showing that certain regularized equilibria do not possess the aforementioned non-correspondence problem -- thus, computing them can be treated as perfect-information problems. Because these regularized equilibria can be made arbitrarily close to Nash equilibria, our result opens the door to a new perspective to solving two-player zero-sum games and yields a simplified framework for decision-time planning in two-player zero-sum games, void of the unappealing properties that plague existing decision-time planning approaches.

Key facts. Cited by 6 papers in the map (data through 7 Oct 2026). Builds on 29 of its 67 references that are in the map. First posted on arXiv 22 Jan 2023.

Builds on

29 of 67 references.

References · 29

  1. 2017Thinking Fast and Slow with Deep Learning and Tree Searchcited by 245
  2. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 228
  3. 2019The Hanabi Challenge: A New Frontier for AI Researchcited by 194
  4. 2022Mastering the Game of Stratego with Model-Free Multiagent Reinforcement Learningcited by 129
  5. 2020Combining Deep Reinforcement Learning and Search for Imperfect-Information Gamescited by 110
  6. 2018Bayesian Action Decoder for Deep Multi-Agent Reinforcement Learningcited by 67
  7. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
  8. 2021Fast Policy Extragradient Methods for Competitive Games with Entropy Regularizationcited by 61
  9. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 59
  10. 2017Safe and Nested Subgame Solving for Imperfect-Information Gamescited by 39
  11. 2019Rethinking Formal Models of Partially Observable Multiagent Decision Makingcited by 35
  12. 2019Improving Policies via Search in Cooperative Partially Observable Gamescited by 33
17 more
  1. 2013Solving Imperfect Information Games Using Decompositioncited by 27
  2. 2018Depth-Limited Solving for Imperfect-Information Gamescited by 24
  3. 2021Scalable Online Planning via Reinforcement Learning Fine-Tuningcited by 18
  4. 2022Regularized Gradient Descent Ascent for Two-Player Zero-Sum Markov Gamescited by 18
  5. 2021Solving Common-Payoff Games with Approximate Policy Iterationcited by 15
  6. 2020Unlocking the Potential of Deep Counterfactual Value Networkscited by 8
  7. 2021Common Information based Approximate State Representations in Multi-Agent Reinforcement Learningcited by 8
  8. 2022HSVI can solve zero-sum Partially Observable Stochastic Gamescited by 8
  9. 2015Timeability of Extensive-Form Gamescited by 7
  10. 2016Structure in the Value Function of Two-Player Zero-Sum Games of Incomplete Informationcited by 6
  11. 2022A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solvingcited by 6
  12. 2019Online Planning for Decentralized Stochastic Control with Partial History Sharingcited by 5
  13. 2020Team Optimal Control of Coupled Subsystems with Mean-Field Sharingcited by 5
  14. 2022Public Information Representation for Adversarial Team Gamescited by 4
  15. 2013Structural Results and Explicit Solution for Two-Player LQG Systems on a Finite Time Horizoncited by 2
  16. 2020On Bellman's Optimality Principle for zs-POSGscited by 2
  17. 2021HSVI for zs-POSGs using Concavity, Convexity and Lipschitz Propertiescited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 2; 2024: 1; 2025: 2; 2026: 1.

6 papers.

  1. 2023Suspicion-Agent: Playing Imperfect Information Games with Theory of Mind Aware GPT-4cited by 67
  2. 2025Scalable Decision Making for Games of Imperfect Informationcited by 7
  3. 2026Detecting Multi-Agent Collusion Through Multi-Agent Interpretabilitycited by 6
  4. 2023The Update-Equivalence Framework for Decision-Time Planningcited by 2
  5. 2025Look-ahead Reasoning with a Learned Model in Imperfect Information Gamescited by 1
  6. 2024ε-Optimally Solving Zero-Sum POSGscited by 0