An $ε$-Optimal Sequential Approach for Solving zs-POSGs
For researchers in game theory and multi-agent reinforcement learning, this work provides a practical solution to a known computational bottleneck in zs-POSGs.
The paper tackles the computational intractability of zero-sum partially observable stochastic games by reformulating the simultaneous minimax backup as a sequential decision process, reducing complexity from exponential to polynomial. Experiments show the new method significantly outperforms state-of-the-art, solving previously intractable domains.
While recent reductions of zero-sum partially observable stochastic games (zs-POSGs) to transition-independent stochastic games (TI-SGs) theoretically admit dynamic programming, practical solutions remain stifled by the inherent non-linearity and exponential complexity of the simultaneous minimax backup. In this work, we surmount this computational barrier by rigorously recasting the simultaneous interaction as a sequential decision process via the principle of separation. We introduce distinct sufficient statistics for valuation and execution, the sequential occupancy state and the private occupancy family, which reveal a latent geometry in the optimal value function. This structural insight allows us to linearise the backup operator, reducing the update complexity from exponential to polynomial while enabling the direct extraction of safe policies without heuristic bookkeeping. Experimental results demonstrate that algorithms leveraging this sequential framework significantly outperform state-of-the-art methods, effectively rendering previously intractable domains solvable.