ε-Optimally Solving Two-Player Zero-Sum POSGs

We present a novel framework for ε-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 ε-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.

(3) Structural properties of value functions. The planner hierarchy reveals new structural properties of zs-POSGs, including optimality equations, strategy selection rules, and, critically, the uniform continuity of value functions. Uniform continuity guarantees that small changes in occupancy states lead to uniformly bounded changes in value, regardless of where they occur in the state space. This property enables value functions to generalise across occupancy states in a principled way, supporting reliable planning without requiring dense sampling or finely tuned control at every point.

(4) Practical benefits through algorithmic transfer. As a concrete example of the framework in use, we show that point-based value iteration (PBVI) [Pineau et al., 2003, Horák et al., 2017, Horák and Bošanský, 2019], applied to the reduced game, computes ε-optimal strategies across standard zs-POSG benchmarks, consistently matching or outperforming existing methods. More broadly, the reduction enables the transfer of a wide class of dynamic programming algorithms-originally developed for stochastic games-into partially observable settings, thereby expanding the set of scalable planning tools available for zs-POSGs.

This section presents the standard formulation of zero-sum partially observable stochastic games (zs-POSGs), along with their associated policies and value functions.

Definition 2.1. A two-player zero-sum partially observable stochastic game M is defined as the tuple (S, A 1 , A 2 , Z 1 , Z 2 , W, p, r , b, γ, ℓ), where players 1 and 2 are the maximising and minimising players, respectively. S is a finite set of hidden states. A 1 and A 2 are finite sets of private actions, and Z 1 and Z 2 are finite sets of private observations for each player. W denotes the set of public observations available to both players. The transition function p :

defines the probability p(s′, z 1 , z 2 , w|s, a 1 , a 2 ) of transitioning to next state s′ and emitting observations (z 1 , z 2 , w) given current state s and actions (a 1 , a 2 ). The reward function r : S × A 1 × A 2 → R specifies the stage payoff r (s, a 1 , a 2 ) received by player 1. The initial belief over states is given by b ∈ ∆(S), the discount factor is γ ∈ [0, 1), and the planning horizon is finite with ℓ + 1 < ∞.

Policies. At each stage t ∈ 0, ... , ℓ, player i selects actions based on a private action-observation history h i,t ∈ H i,t . = (A i × Z i ) t and a public observation history h pub,t ∈ H pub,t . = W t , starting from h i,0 = ∅. A decision rule d i,t : H i,t × H pub,t → ∆(A i ) maps joint histories to distributions over actions, with the set of all such rules denoted D i,t . The players' actions determine a transition to state s t+1 , yield a payoff r (s t , a 1,t , a 2,t ), and generate new observations (z 1,t+1 , z 2,t+1 , w t+1 ), which update the histories recursively. A policy π i = (d i,0 , ... , d i,ℓ ) is a sequence of such rules; the set of all history-dependent policies is denoted Π i . The full sets of private and public histories are H i = ∪ ℓ t=0 H i,t and H pub = ∪ ℓ t=0 H pub,t , respectively.

Given an initial state distribution b, the expected cumulative discounted payoff under joint policies

, where the expectation is over trajectories induced by b, p, and the policy pair. Player 1 seeks to maximise this value while player 2 seeks to minimise it. Under perfect recall, behavioural (history-dependent) policies are equivalent to mixed strategies [Kuhn, 1953], and von Neumann's minimax theorem [Neumann, 1928]-extended to behavioral strategy spaces by Delage et al. [2023]-ensures the existence of a game value v * (b),

The solution to M is a policy π 1 that maximises the guaranteed payoff against any opponent policy, i.e., min π 2 v π 1 ,π 2 (b) = v * (b); the symmetric holds for player 2. The corresponding pair forms a Nash equilibrium.

A reduction from a zs-POS