# HSVI can solve zero-sum Partially Observable Stochastic Games

arXiv: https://arxiv.org/abs/2210.14640 · HTML: https://mlsanity.com/paper/2210.14640/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 12 of its 49 references that are in the map.
- First posted on arXiv 26 Oct 2022.

## Builds on (most cited first, 12 of 12)

- [DeepStack: Expert-Level Artificial Intelligence in No-Limit Poker](https://mlsanity.com/paper/1701.01724/) (2017)
- [The Complexity of Decentralized Control of Markov Decision Processes](https://mlsanity.com/paper/1301.3836/) (2013)
- [OpenSpiel: A Framework for Reinforcement Learning in Games](https://mlsanity.com/paper/1908.09453/) (2019)
- [Combining Deep Reinforcement Learning and Search for Imperfect-Information Games](https://mlsanity.com/paper/2007.13544/) (2020)
- [Solving Large Imperfect Information Games Using CFR+](https://mlsanity.com/paper/1407.5042/) (2014)
- [Rethinking Formal Models of Partially Observable Multiagent Decision Making](https://mlsanity.com/paper/1906.11110/) (2019)
- [Solving Imperfect Information Games Using Decomposition](https://mlsanity.com/paper/1303.4441/) (2013)
- [Revisiting CFR+ and Alternating Updates](https://mlsanity.com/paper/1810.11542/) (2018)
- [Solving Zero-Sum One-Sided Partially Observable Stochastic Games](https://mlsanity.com/paper/2010.11243/) (2020)
- [Search in Imperfect Information Games](https://mlsanity.com/paper/2111.05884/) (2021)
- [Structure in the Value Function of Two-Player Zero-Sum Games of Incomplete Information](https://mlsanity.com/paper/1606.06888/) (2016)
- [Value Functions for Depth-Limited Solving in Zero-Sum Imperfect-Information Games](https://mlsanity.com/paper/1906.06412/) (2019)

## Built on by (most cited first, 8 of 8)

- [Games for AI Control: Models of Safety Evaluations of AI Deployment Protocols](https://mlsanity.com/paper/2409.07985/) (2024)
- [Robust Markov Decision Processes: A Place Where AI and Formal Methods Meet](https://mlsanity.com/paper/2411.11451/) (2024)
- [Conjectural Online Learning with First-order Beliefs in Asymmetric Information Stochastic Games](https://mlsanity.com/paper/2402.18781/) (2024)
- [Imprecise Probabilities Meet Partial Observability: Game Semantics for Robust POMDPs](https://mlsanity.com/paper/2405.04941/) (2024)
- [Abstracting Imperfect Information Away from Two-Player Zero-Sum Games](https://mlsanity.com/paper/2301.09159/) (2023)
- [Partially Observable Stochastic Games with Neural Perception Mechanisms](https://mlsanity.com/paper/2310.11566/) (2023)
- [HSVI-based Online Minimax Strategies for Partially Observable Stochastic Games with Neural Perception Mechanisms](https://mlsanity.com/paper/2404.10679/) (2024)
- [ε-Optimally Solving Zero-Sum POSGs](https://mlsanity.com/paper/2406.00054/) (2024)

## Abstract (arXiv)

State-of-the-art methods for solving 2-player zero-sum imperfect information games rely on linear programming or regret minimization, though not on dynamic programming (DP) or heuristic search (HS), while the latter are often at the core of state-of-the-art solvers for other sequential decision-making problems. In partially observable or collaborative settings (e.g., POMDPs and Dec- POMDPs), DP and HS require introducing an appropriate statistic that induces a fully observable problem as well as bounding (convex) approximators of the optimal value function. This approach has succeeded in some subclasses of 2-player zero-sum partially observable stochastic games (zs- POSGs) as well, but how to apply it in the general case still remains an open question. We answer it by (i) rigorously defining an equivalent game to work with, (ii) proving mathematical properties of the optimal value function that allow deriving bounds that come with solution strategies, (iii) proposing for the first time an HSVI-like solver that provably converges to an ε-optimal solution in finite time, and (iv) empirically analyzing it. This opens the door to a novel family of promising approaches complementing those relying on linear programming or iterative methods.