mlsanityData to 7 Oct 2026

The Update-Equivalence Framework for Decision-Time Planning

arXiv 2304.13138 ↗First posted 25 Apr 2023cs.AI cs.LGcited by 2

Not on the map. Why?

Abstract (arXiv)

The process of revising (or constructing) a policy at execution time -- known as decision-time planning -- has been key to achieving superhuman performance in perfect-information games like chess and Go. A recent line of work has extended decision-time planning to imperfect-information games, leading to superhuman performance in poker. However, these methods involve solving subgames whose sizes grow quickly in the amount of non-public information, making them unhelpful when the amount of non-public information is large. Motivated by this issue, we introduce an alternative framework for decision-time planning that is not based on solving subgames, but rather on update equivalence. In this update-equivalence framework, decision-time planning algorithms replicate the updates of last-iterate algorithms, which need not rely on public information. This facilitates scalability to games with large amounts of non-public information. Using this framework, we derive a provably sound search algorithm for fully cooperative games based on mirror descent and a search algorithm for adversarial games based on magnetic mirror descent. We validate the performance of these algorithms in cooperative and adversarial domains, notably in Hanabi, the standard benchmark for search in fully cooperative imperfect-information games. Here, our mirror descent approach exceeds or matches the performance of public information-based search while using two orders of magnitude less search time. This is the first instance of a non-public-information-based algorithm outperforming public-information-based approaches in a domain they have historically dominated.

Key facts. Cited by 2 papers in the map (data through 7 Oct 2026). Builds on 32 of its 70 references that are in the map. First posted on arXiv 25 Apr 2023.

Builds on

32 of 70 references.

References · 32

  1. 2017Proximal Policy Optimization Algorithmscited by 14,441
  2. 2014Sequence to Sequence Learning with Neural Networkscited by 2,974
  3. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,327
  4. 2017Thinking Fast and Slow with Deep Learning and Tree Searchcited by 245
  5. 2017DeepStack: Expert-Level Artificial Intelligence in No-Limit Pokercited by 228
  6. 2019The Hanabi Challenge: A New Frontier for AI Researchcited by 194
  7. 2019OpenSpiel: A Framework for Reinforcement Learning in Gamescited by 180
  8. 2016Deep Reinforcement Learning from Self-Play in Imperfect-Information Gamescited by 153
  9. 2020Combining Deep Reinforcement Learning and Search for Imperfect-Information Gamescited by 110
  10. 2022A Unified Approach to Reinforcement Learning, Quantal Response Equilibria, and Two-Player Zero-Sum Gamescited by 64
  11. 2020From Poincar'e Recurrence to Convergence in Imperfect Information Games: Finding Equilibrium via Regularizationcited by 59
  12. 2020On the role of planning in model-based deep reinforcement learningcited by 57
20 more
  1. 2021Modeling Strong and Human-Like Gameplay with KL-Regularized Searchcited by 50
  2. 2022Mastering the Game of No-Press Diplomacy via Human-Regularized Reinforcement Learning and Planningcited by 47
  3. 2017Safe and Nested Subgame Solving for Imperfect-Information Gamescited by 39
  4. 2019No Press Diplomacy: Modeling Multi-Agent Gameplaycited by 37
  5. 2019Rethinking Formal Models of Partially Observable Multiagent Decision Makingcited by 35
  6. 2019Improving Policies via Search in Cooperative Partially Observable Gamescited by 33
  7. 2013Solving Imperfect Information Games Using Decompositioncited by 27
  8. 2019Vortices Instead of Equilibria in MinMax Optimization: Chaos and Butterfly Effects of Online Learning in Zero-Sum Gamescited by 24
  9. 2020Approximate exploitability: Learning a best response in large gamescited by 23
  10. 2021Scalable Online Planning via Reinforcement Learning Fine-Tuningcited by 18
  11. 2021Solving Common-Payoff Games with Approximate Policy Iterationcited by 15
  12. 2020Joint Policy Search for Multi-agent Collaboration with Imperfect Informationcited by 13
  13. 2019Policy Gradient Search: Online Planning and Expert Iteration without Search Treescited by 11
  14. 2021Subgame solving without common knowledgecited by 11
  15. 2021Learned Belief Search: Efficiently Improving Policies in Partially Observable Settingscited by 10
  16. 2020Unlocking the Potential of Deep Counterfactual Value Networkscited by 8
  17. 2015Timeability of Extensive-Form Gamescited by 7
  18. 2022A Marriage between Adversarial Team Games and 2-player Games: Enabling Abstractions, No-regret Learning, and Subgame Solvingcited by 6
  19. 2023Abstracting Imperfect Information Away from Two-Player Zero-Sum Gamescited by 6
  20. 2022Public Information Representation for Adversarial Team Gamescited by 4

Built on by

Cited by year

Citing papers per year: 2025: 2.

2 papers.

  1. 2025Scalable Decision Making for Games of Imperfect Informationcited by 7
  2. 2025General search techniques without common knowledge for imperfect-information games, and application to superhuman Fog of War chesscited by 5