An $ϵ$-Optimal Sequential Approach for Solving zs-POSGs

Recent reductions of finite-horizon two-player zero-sum partially observable stochastic games (zs-POSGs) admit dynamic programming with linear programming backups, but these remain computationally demanding. Building on sequential central planning for cooperative games, we factorise the optimisation over the joint decision rule into two planning sub-stages per game stage, one per player. This ordering preserves the game value and the players' information constraints while their actions remain simultaneous. We establish the sufficiency of sequential occupancy states for the value recursion and show that both sub-stages retain the maximum-of-concave structure of the simultaneous formulation. We integrate the resulting linear programming backups into a sequential point-based value iteration algorithm (PBVIseq). We bound the exploitability of its policies, accounting for approximation at both sub-stages. On several medium-to-large benchmarks, PBVIseq returns policies with lower exploitability than competing solvers and solves horizons at which some baselines exceed time or memory limits.