\(\varepsilon\)-Optimally Solving Two-Player Zero-Sum POSGs
Erwan escudie, Matthia Sabatelli, Olivier Buffet, Jilles Steeve Dibangoye
Abstract
We present a novel framework for \(\varepsilon\)-optimally solving two-player zero-sum partially observable stochastic games (zs-POSGs). These games pose a major challenge due to the absence of a principled connection with dynamic programming (DP) techniques developed for two-player zero-sum stochastic games (zs-SGs). Prior attempts at transferring solution methods have lacked a lossless reduction—defined here as a transformation that preserves value functions, equilibrium strategies, and optimality structure—thereby limiting generalisation to ad hoc algorithms. This work introduces the first lossless reduction from zs-POSGs to transition-independent zs-SGs, enabling the principled application of a broad class of DP-based methods. We show empirically that point-based value iteration (PBVI) algorithms, applied via this reduction, produce \(\varepsilon\)-optimal strategies across a range of benchmark domains, consistently matching or outperforming existing state-of-the-art methods. Our results open a systematic pathway for algorithmic and theoretical transfer from SGs to partially observable settings.
BibTeX
@inproceedings{
escudie2025varepsilonoptimally,
title={{\textbackslash}({\textbackslash}varepsilon{\textbackslash})-Optimally Solving Two-Player Zero-Sum {POSG}s},
author={Erwan escudie and Matthia Sabatelli and Olivier Buffet and Jilles Steeve Dibangoye},
booktitle={The Thirty-ninth Annual Conference on Neural Information Processing Systems},
year={2025},
url={https://openreview.net/forum?id=tqoAQMk4AH}
}