Research map / Learning theory and algorithms / Combinatorial and search optimization
The Update-Equivalence Framework for Decision-Time Planning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes update-equivalence framework for decision-time planning that replicates last-iterate algorithm updates rather than solving public-belief-state subgames, yielding mirror descent search for cooperative games and magnetic mirror descent search for adversarial games.
Problem
Decision-time planning in imperfect-information games relies on public belief state subgame solving, which becomes intractable as the amount of non-public information grows.
Approach
Views DTP algorithms as implementing the updates of last-iterate algorithms (update equivalence), so search can focus computation on the agent's own decision point without PBS; instantiates this with mirror descent (MDS) for common-payoff games and magnetic mirror descent (MMDS) for two-player zero-sum games.
Key results
- In 5-card 8-hint Hanabi, MDS (multi-agent, Seq2Seq belief, 2s per move) achieves 24.62 ± 0.02, matching the best exact-belief PBS methods (e.g., multi-agent RLSearch 24.62 ± 0.03) at ~two orders of magnitude less search time.
- In 7-card 4-hint Hanabi, MDS scores 24.28 ± 0.02, outperforming multi-agent RLSearch with BFT (24.18 ± 0.03) and single-agent SPARTA (24.17 ± 0.03).
- MMDS reduces approximate exploitability of the uniform random blueprint in 3x3 Abrupt Dark Hex from 74 to 50 on a 0-100 scale, and in Phantom Tic-Tac-Toe from 78 to 50.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use MDS instead of multi-agent RLSearch with BFT | Hanabi search with an R2D2 blueprint · 7-card 4-hint Hanabi | expected return: 24.18 ± 0.03 -> 24.28 ± 0.02 | Helped |
| Use MDS instead of multi-agent RLSearch | Hanabi search with an R2D2 blueprint · 5-card 8-hint Hanabi | expected return: 24.62 ± 0.03 -> 24.62 ± 0.02 | No clear effect |
| Use MDS instead of multi-agent SPARTA | Hanabi search with an R2D2 blueprint · 5-card 8-hint Hanabi | expected return: 24.61 ± 0.02 -> 24.62 ± 0.02 | No clear effect |
| Apply MMDS to the uniform random blueprint | Uniform random blueprint · 3x3 Abrupt Dark Hex | approximate exploitability: 74 ± 1 -> 50 ± 1 | Helped |
| Apply MMDS to the uniform random blueprint | Uniform random blueprint · Phantom Tic-Tac-Toe | approximate exploitability: 78 ± 0 -> 50 ± 1 | Helped |
| Vary the mirror descent stepsize (ablation) | MDS · 7-card 4-hint Hanabi | expected return | Mixed |
| Add MMD updates at the planning agent's future decision points (ablation) | MMDS · Imperfect-information 2p0s games | convergence to AQRE | Helped |
| Fine-tune the belief model to the search policy (ablation) | MMDS · Imperfect-information 2p0s games | convergence to AQRE | Helped |
| Add an MMD update for the opponent at its next decision point (ablation) | MMDS · Imperfect-information 2p0s games | convergence to AQRE | Helped |
Surprising findings
- MDS outperforms public-belief-state-based search in Hanabi, the domain where such methods have historically dominated, despite using approximate beliefs and no validation check.
- Performance of MDS as a function of stepsize is unimodal: too large a stepsize causes the search policy to diverge from the blueprint and hurts performance.
Limitations
- Search uses an approximate learned belief model (Seq2Seq) rather than exact beliefs, and MDS lacks a validation check.
- MMDS experiments use only small games with a uniform random blueprint and 10-particle approximate posteriors, and exploitability is only approximated via DQN best response.
- Soundness guarantees for MDS are local (expected improvement for sufficiently small stepsize and large budget); the MMDS guarantee relies on an empirical observation of last-iterate convergence.
Experimental setup
Datasets: Hanabi Abrupt Dark Hex Phantom Tic-Tac-Toe
Benchmarks: Hanabi 3x3 Abrupt Dark Hex Phantom Tic-Tac-Toe
Metrics: expected return standard error approximate exploitability time per move
Baselines: single-agent SPARTA multi-agent SPARTA single-agent RLSearch multi-agent RLSearch NFSP PPO MMD
Builds on: mirror descent magnetic mirror descent Monte Carlo search SPARTA PPO
Closest papers by meaning
- Local and Adaptive Mirror Descents in Extensive-Form Games (NeurIPS 2024 · similarity 0.88)
- Adaptively Perturbed Mirror Descent for Learning in Games (ICML 2024 · similarity 0.86)
- Safe and Robust Subgame Exploitation in Imperfect Information Games (ICML 2024 · similarity 0.86)
- Configurable Mirror Descent: Towards a Unification of Decision Making (ICML 2024 · similarity 0.86)
- Implicit Search via Discrete Diffusion: A Study on Chess (ICLR 2025 · similarity 0.86)
- Mastering Board Games by External and Internal Planning with Language Models (ICML 2025 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.