\(\varepsilon\)-Optimally Solving Two-Player Zero-Sum POSGs
Authors: Erwan escudie
Matthia Sabatelli
Olivier Buffet
Jilles Steeve Dibangoye
Venue: NeurIPS 2025 poster ()
Keywords: Zero-Sum Partially Observable Stochastic Games
Transition-Independent Stochastic Games
Planning
Linear Programming
Primary area: theory

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.

E-Optimally Solving Two-Player Zero-Sum POSGs
Erwan C. Escudie e. c. escudierrug. nl University of Groningen
Matthia Sabatelli m. sabatelliii @rug. ml University of Groningen
Olivier Buffet olivier. wuffet@loorrr.....fo.omoo Inria Nancy Grand-Est
Jilles Steeve Dibangoye s. dibangoye@rug nl University of Groningen
Abstract
We present a novel framework for s-optimally solving two-player zero-sum par- tially observable stochastic games (zs-POSGss. These games pose major chal- lenge 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 lossless reduc- tion-defined here transformation that preserves value functions, equilib- rium strategies, and optimality structure thereby limiting generalisation to ad hoc algorithms. This work introduces the first lossless reduction from as-POSGs to consiiion--ndepeendee class DP-based methods. We show empirically that point-based value iteration (PBVI) algorithms, applied via this reduction, produce s-optimal strategies across a range of benchmark domains, consistently matching or outperforming existing state-of-the-art methods. Our results open systematic pathway for algorithmic and theoretical transfer from SGs to partially observable settings.
zs-SGs, enabling the principled application of broad
Introduction
Bellman [1957] introduced the principle of optimality for sequential decision Decision-making under uncer- tainty in the 1950s, originally in the context of Markov decision processes (MDPs). Since then, this principle has provided foundation for solving progressively [1953] extended it to zero-sum stochastic games (zs-SGs), while others adapted to the partially observable case, including Aström [1965], Smallwood and Sondik [1973], and Sondik [1978] for partially observable Markov decision processes (POMDPs). More recently, rich body of work has applied this reduction-based methodology partially observable stochastic games (POSGs). For common-paye payyff POSGs, several approaches have successfully constructed fully observable surrogates typically common-per payoff Markov games thus enabling the transfer of dynamic pro- gramming (DP) theories and algorithms without compromising optimality [Szer et al., 2005, Oliehoek al., 2008, 2010. Nayyar et al., 2013, Dibangoye et al., 2013a, 2016, Olichock, 2013, Oliehock et al., 2013, Lerer et al., 2020, Peralez et al., 2024, 2025]. In contrast, for zs- zs-POSGs, although a number of methods have been proposed [Wiggers et al., 2016, Nayyar and Gupta, 2017, Horák et al., 2017, Horák and Bošanský, 2019, Buffet et al., 2020, Brown et al., 2020, Delage et al., 2023, Sokota et al., 2023], none constitutes a lossless reduction [Sanjari et al., 2023]. As consequence, generalisation to this setting has remained restricted to ad hoc algorithmic designs, with no principled framework for transferring DP techniques from SGs to ZS-SSSSs.
complex problems. Shapley
A lossless reduction transforms zs- PO-SSS into zs-SGs while satisfying three main criteria: value preservation, equilibrium correspondence, and information structure equivalence [Sanjari al., 2023]. Value preservation requires that the expected return of any joint policy in the original game equals
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

that of its image in the reduced game. Equilibrium correspondence demands that the reduction induce a bijection between equilibria, ensuring that Nash strategies remain valid and interpretable across both formulations. Finally, information structure equívalence ensures that the transformation does not introduce extraneous information or collapse distinctions essential the players' strategic reasoning. Several reductions have been proposed, but all fail to satisfy one or more of these criteria. The occupancy Markov game (OMG) assumes a centralised planner selects joint policies based on the occupancy state-an object unobservable to either player- thhs violating the equilibrium correspondence criterion [Wiggers et al., 2016, Buffet et al., 2020, Delage et al., 2023]. To circumvent this limitation, Delage et al. [2023] introduce policy tracking via ad hoc bookkeeping techniques. The public- alternating Markov game (PuB-AMG) assumes that both players publicly commit to their policies, which violates the equilibrium correspondence criterion [Sokota et al., 2023]. To address this, the authors introduce a regularised minimax formulation intended to restore solution correspondence ensuring that strategies computed in the reduced game interpretable in the original rs-POSG. While the regularisation guarantees convergence to unique solutions within the PuB-AMG, the resulting strategies may correspond policies with high exploitability in the original game. Although an annealing scheme can reduce this gap empirically, there is no formal guarantee that the regularised solutions preserve value or recover exact Nash equilibria in the original zs-POSG. As result, the reduction does not satisfy the criteria for a lossless transformation.
Contributions. We make several key contributions the study of zs- Ps-POSGs:
(1) principled and lossless reduction transition-independeen zs-SGs. We introduce the first reduction that maps any 7s-POSG to strategically equivalent cuusitiion-indeeendeee 7s-SG, preserving value, equilibrium structure, and information constraints. The reduction adopts a decen- tralised perspective: each player independently selects a sequence of decision rules rules-mapppngs from private histories (i.e., past actions and observations) to action distributions- defining the local state of that player, formalised as occupancy set. The global state of the reduced game, the occupancy state, is the intersection the two players' occupancy sets, capturing the joint consistency of their behaviours. Because each local state evolves independently of the opponent, the reduced game exhibits consition-indepeenie selected decision rule. This reformulation preserves the strategic structure of the original zs-POSG while enabling dynamic programming over occupancy sets avoiding explicit reasoning over joint policy spaces and supporting scalable, exact solution methods. The hierarchy of planners introduced in this work-ranging from focal to marginal planners- forms a nested structure based on increasing information availability, illustrated in Figure 1.
dynamics, where transitions depend only on the current local state and
Focal planner
Uninformed planner
Informed planner
Marginal planner
Knows only the focal policy and nothing else
Knowe the rnpoovet pollicy and focal planser data
Kncns, public signals and snlaforme planner data
Knnnes eppoment nt hiztories and liformed de phanner data
Figure 1: A planner hierarchy induced by relaxing information constraints, from the focal to the marginal planner, supporting our theoretical and algorithmic framework.
(2) A planner hierarchy for structured reasoning. The reduced game reveals a hicrarchy of planners-ranghe from a minimally informed focal planner, increasingly informed uninformed, informed, and finally marginal planners. Each planner defines a distinct optimisation problem, characterised by reasoning scope (single-agent or centralised) and its access to information (from no observations to full access to public and private histories). While only the focal planner is ever implemented in practice, the remaining planners serve as conceptual tools that underpin the structure of value functions and guide the transfer of theoretical insights. Solving the reduced game requires traversing this hierarchy: each planner contributes well-defined subproblem whose value function and policy essential for constructing the overall solution to the zs- POSG.

---

(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 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 toint-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 e-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 algorithmss originally developed for stochastic games-ine partially observable settings, thereby expanding the set of scalable planning tools available for zs-POSGs.
-orignalll
2
Preliminaries
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. poo-player zero-sum partially observable stochastic game M is defined as the tuple A1, 21, Z2, W. p.r, b, E). where players I and 2 are the maximising and minimising players. respectively. S a finite set of hidden states. A, and A2 are finite sets of private actions, and 2, and Ze are finite sets of private obxervations for each player. W denotes the set of public observations available to both players. The transition function p 3:8 x A, A2 - (8 x Zn x 22 x W) defines the probability p(sr, Z1, Z2, W Ss a a²) of transitioning to next state st and emitting observations (Zi, Z2, W) given current state S and actions (a,, 22). The reward function r x A x A2 + IR specifies the stage payoff rss, a,, az) received by player 1. The initial belief over states is given by (SS), the discount factor 7 E [0. 1), and the planning horizon is finite with E 1 < 00.
Policies. At each stage E (o...., f. player i selects actions based on a private action-observation
history h E HG, (A, x 2.)' and public observation history Apu..t E Hpub.t = W starting from hio 0. A decision rule d, Hi,, x Hpuhh + (AA)) maps joint histories to distributions over actions, with the set of all such rules denoted Di,,- The players' actions determine a transition to state St41. yield a payoff r(s, a a,,), and generate new observations (Zi,te1, Z2,t41, Wh11), which update the histories recursively. A policy x; (di,o, .... di.e) is a sequence of such rules; the set of all history-dependent policies is denoted n; The full sets of private and public histories are H,, = , and Hpub = Uf respectively.
Value Functions. Given an initial state distribution b, the expected cumulative discounted payoff under joint policies (T), T22 is V=,,,, (b) = E|Ei= 7" r(st, ai.; 22.)). 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 's minimax theorem [Neumann, 1928]-extended the existence of a game value v. vb()), satisfying (b) min,,, max;, Vrr, (b) max,, min,, Ve,.,y (b). The solution to M is a policy Ty that maximises the guaranteed payoff against any opponent policy, i.c., min,, (b)) = (b(;; the symmetric holds for player 2. The corresponding pair forms a Nash equilibrium.
to behavioral strategy spaces by Delage et al.
Lossless Reductions. A reduction from 7s- Ps-POSG M to surrogate game M'' is said to be lossless it preserves value functions, supports equilibrium transfer, and maintains the relevant information structure. This includes: (i) value preservation, i.e., yM (b) = VAr (b) for all joint policies; (ii) equilibrium correspondence, meaning each Nash equilibrium in M' induces one in M and vice versa; and (iii) information compatibility, ensuring the reduction respects players' original observation constraints and decision spaces. These conditions allow exact transfer of optimality equations and policies, while preserving the strategic essence of the original game.
3

---

3 Reducing zs-POSGs to Transtion-Indeppeneen zs-SGs
This section presents the main contribution of this work: a lossless reduction from any zs-POSG to a strategically equivalent transition-independent zs-SG. The reduced model preserves the value function, equilibrium structure, and information constraints of the original zs-POSG, thereby enabling the exact transfer of dynamic programming principles and solution methods. The key insight behind this reduction is to factor the game into local planning processes, one for each player, while maintaining the strategic dependencies of the original interaction through shared global state.
We reformulate the original zs- 7s-POSG as a planning process-a transition- iisiitioon-ideeeddeen zs- SG-through two complementary perspectives. The centralised view casts it as a planning problem executed by an uninformed planner, hypothetical central authority that selects joint decision rules without access to any observations. The decentralised view decomposes this process into two player- specific focal planners, each reasoning independently over a single player's sequence of decision rules. This planning process unfolds stage by stage. At each time step t, the underlying global state is an uninformed occupancy state X₁: a distribution over hidden states, private action-observation histories, and public observations, induced by the sequence of decision rules 8 = (d1,o, d2.0, ..... di.c-1, d2,t-1). This global state captures the full strategic context of the game but remains unobservable to either player. Instead, each player reasons over a local state X defined set: the collection of uninformed occupancy states consistent with their own sequence of decision rules (d.o...., d),-1), regardless of the opponent's choices. Based solely on this local state, player i selects a decision rule d and transitions to the next local state Tx(x,,, d,,). formed by appending the selected rule. This decentralised process continues until the planning horizon l f+ 1 is reached. At each step, the environment returns an immediate payoff p(x,, di,, d2,1) and updates the global state via 7 rXx, di,, d2,1). both unobservable to the players. Crucially, each local state evolves independently of the opponent, and the current global state satisfies {xt} = X1, O X2.:- These properties define a structured model known as a transition transition-independenn zero- sum stochastic game (zs-SG), cf. Figure 2.
player-specific occupancy
d2
d2.1
X2.b
Xg.
X2.b
Pilaye''s siewpoint
X
X
X
P3.
Hiddes
Goal
X1.6
K1A
X1
d1.b
d1.6
('llaye's siewpoiit
Time
fo
h
Figure 2: An influence diagram of transition-indeeendenn, two-player, zero-sum stochastic game.
We first describe model M, for each player-specific planner-a single-agent planner that selects policies for player i, based only on their own decision-rule history, with no access to observations or the opponent's 's policy. This defines the least informed level of the planner hierarchy and serves as the local computational engine underlying decentralised dynamic programming within the zs-SG.
Definition 3.1. player-specific focal planning process M, = (X,, D,, Ti pi) consists of: a set X, of local states (occupancy sets); set F, C X, of (terminal) occupancy sets at stage E 1; a set of decision rules Dj a local transition operator Tx,,; d) = {r(x, d, [ E X, d_i D DDi). and local payoff function, which is zero if x; X, and pi: x; + optxex g(x) otherwise, where

---

the operator opt corresponds to min for player and max for player 2, for any uninformed occupancy state X(+1, g(X = ar.
o r(Sy, a 22,1
Having formalised the focal planning processes as M, and M2. we now lift these constructions to zero-sum stochastic game M', which governs the joint dynamics
define the consition-indepemuee over uninformed occupancy states and their associated objective.
Definition 3.2. A transition transition-independee independent zero-sum stochastic game (zs-SG) a tuple NC (M,J,MM, M,,M2, T, iP, p, 7), where T is the set of uninformed occupancy states; I C X is the +1;T T (x, di, de) + XI is the global transition function, that is, for all hidden states St, private action-observation histories (h; a, for player and public observation histories (hpub, W).
set of (terminal) uninformed occupancy states at stage 11;;
xi(si, (hi, a; Zi)i, (hputs w)) = Es x(s, h1 02, nmub p(s), Z1, Z2, w a1, 82) II, (a hi, hpub); (x(1, x2) x. where (x} X1 p (x, di. d2) + R is the stage-wise payoff function,, given by p(x, di, d2) = No Mn... x(s, h1 h2, puu)) Es. a, di (a h, )p (2 h2, (pw ai, a2);
L 1 is the horizon and y E [O. 1) the discount factor. Each component M, captures the planning process from from the perspective of player i, see Definition 3.1.
Having defined the transitioniiddepedeent ZS-SG M', we now specify the objective of solving it. The goal is to find policies 11 : X, - D) and 1/2 X2 De that map player-specific occupancy sets to decision rules. These are accupancy-sel dependent policies, tailored to the decentralised structure of the reduced game. Let ;, denote the set of such policies for player i. Given initial
uninformed occupancy state Xo b and initial occupancy sets X1,0 = X2 = {b), the expected cumulative discounted payoff under joint policy (v,, 4/2 is defined as
Ver.v (b) Eii 7" p(x, di.t. de:))xr = (x x2.)). d,, = ()) X = 1.
Player seeks to maximise this quantity, while player 2 aims to minimise it. We now show that the reduced game M' admits well-defined value and satisfies the minimax property, enabling us to reason about optimal policies via standard theertheo principles.
Lemma 1. The reduced game M' admits a well-defined value (b), which satisfies the minimax identity: v' min max,,ew, Vir. (b) max,,ev; min Vori (b).
The objective in solving M' is to compute an optimal policy 45 for each player i such that min Vor ./s (b) ew, Voyg (b) (b).
We now formally state our main theoretical result, which establishes that the reduced game satisfies the lossless reduction criteria introduced above.
Theorem 1. The reduced game M' constitutes lossless reduction of the original zs-POSG M.
This reformulation preserves the strategic structure the original zs zs-POSG while enabling dynamic programming across a hierarchy of planners, avoiding explicit reasoning over joint policy spaces and supporting scalable, e-exact solution methods.
Solving Transition-Independent zs-SGs via A Hierarchy of Planners
Transition-independeer zs-SGs enable value-based planning over structured state spaces induced by sequences of decision rules selected independently by each player. This structure supports hierarchy of planners, from local focal planners reasoning unilaterally over single player's policy to more informed marginal and central planners. While the two least-informed planners suffice to define the reduced game, the full hierarchy enables more efficient solutions. Foundational results in planning and reinforcement learning show that hierarchical formulations improve efficiency by introducing abstraction, decomposition, and temporally extended reasoning [Ghallab al., 2004, André and Russell, 2002, Vezhnevets et al., 2017, Kaelbling and Lozano-Pérez, 2011]. Similarly, in wwwnssiioonindependee 7s-SGs, the planner hierarchy refines state representations specific occupancy sets to marginal occupancy states preserving strategic structure and
player-
5

---

enabling dynamic programming. The hierarchy includes two focal planners, one per player: central uninformed planner blind to observations; an informed planner with access to public signals; and two marginal planners, each aware of both policies but only one player's private trajectory. This layered structure underpins the analysis and algorithms presented next.
Solving a transttioninddpendent zs-SG can be approached by solving focal planning problems, each defined over player-speeific process M, These problems may be solved independenty--wnee computing only safe policy for one jointly since the planners share structural components. The objective to compute an optimal occupancy-ser dependent policy uj that optimises the worst- case expected return. The value of a given policy db from initial state X is Vi (X:o) pi(Xxe+1). where x,, = (x,,- 2) (x,,-))). The optimal value function is then V.. (x.o)) = opt V. The following result characterises this function through Bellman's 's optimality equations.
Theorem 2. The optimal state-value function Vi,x X; + R of M, satisfies Bellman's 's optimality
equations: (x)) pi(x)) if X, Fr, and (x, = optdeD, (x, d.)) otherwise; with an optimal policy given by v X; + arg deD, Vi, di)). where the optimisation operator opt corresponds to max for player 1 and min for player 2.
Focal planners offer safe and implementable policies but are difficult to solve due to reasoning over entire occupancy sets. We now turn to the next planner in the hierarchy: the uninformed planner. This planner operates over individual uninformed occupancy states and, while not designed to extract safe policy for either player, its value function aligns with that of the focal planners. Specifically, (x = V2,- (X2.0) = V- (xo). where X = ((X1,,, o, X2.0). Thus, computing the value of an occupancy set can be reduced to computing the values of its constituent uninformed occupancy states.
Theorem 3. The optimal state-value function V.: X + I of M' satisfies Bellman's 's optimality equations: vx(x)= if x E J, and v. (x) = maxd ED; mind [ø(x, di, de) + +V di dz))] otherwise. For player i, the value of their focal planner at occupancy set X at stage is given by:
Vx, = optxxx lg(x) + v'v.(x),, VXI E X,,
The uninformed planner treats all public observation histories as indistinguishable, preventing it from leveraging structure revealed by public signals. The informed planner addresses this limitation by reasoning separately for each realisation of public observations. It operates over informed occupancy states Ox,t which are distributions over hidden states and private induced by the uninformed occupancy state x and public observation history Hpub E Hgub: that is, for any hidden state S and private histories (h, h2) of the two players: Ox.t,.n (s, h, h2) Pr(s, h, h 6, hows). Uninformed occupancy states are convex combinations of these informed states, indexed by public observation histories. Letting @rpe. denote the one-hot vector for hpub- we have:
ooservoobervttion histories,
Σ Nu Eup Pr(hputs>x) (x)- (O(x.A...) @n,..), where O(x.)pm) @ @hyn. denotes a Kronecker product. This decomposition allows the optimal value function V+ X - I to be computed separately for each informed occupancy state, by selecting decision rules di Di for player i independently across all public observation histories hpuh-
Theorem 4. The optimal state-value function V, X + R of transition-independae zs-SG M', as defined by Bellman's 's optimality equations in Theorem 3, is a linear map over informed occupancy states. Specifically, if x F, then V. vx(x) = O; otherwise,
vx(x)= = Pr(hpud x) max. Dii min E22 9- (-( di Buss da dps) q. (O(x))o)))): di de,nwa) = p (x,,)) di de + ( (T( diw da.ngal).
where O,x, denotes the informed occupancy state induced by (x, hpub).
While the informed planner leverages structure across public observations, it remains agnostic to the private action-observatton histories of each player. The marginal planner further refines this reasoning by branching on one player's private history. Specifically, for player i, the marginal planner operates over marginal occupancy states C,Ix, which represent distributions over hidden states and the opponent private histories, conditioned on the uninformed occupancy states x, the public observation history hpub. and the private history h, That is, for hidden state S and opponent private histories h_,, one has C.ix.hm..njss, h- Pr(s. h_ ixx, hpuh. h.). Uninformed occupancy states can be expressed as convex combinations of these marginal states, indexed by public and private histories. Let @ and on denote the onc-hot vectors for hpub and h, respectively. Then

---

x x=Emp Mip Pr(mpublx)E Pr(hi|x, npab) (Ci, & @ @ en), where @ denotes the Kronecker product. This refinement allows the marginal planner to isolate the strategic impact of private information while maintaining a full representation of the game evolution. As such, marginal planners are the most informed entities in the hierarchy, incorporating both public and private signals in their reasoning. This decomposition unveils that the optimal value function V. X + R is uniformly continuous across uninformed occupancy states.
Theorem 5.
The optimal state-value function V. X + R. is uniformly continuous across uninformed occupancy states. There exists a collection I of finite sets L2 of functions 02 each linear over marginal occupancy states C2, such that for any uninformed occupancy state x, we have:
Va (x( = Enp EKn Pr(h x) maxxEe Ene Tr(helhpuir ; x) minaSEE ar (2((E((x.t..ntt))
In practice, point-based methods approximate the optimal value function using finite collection I of finite sets 22 of linear functions over sampled marginal occupancy states. This suffices to support value updates and policy extraction with performance guarantees, as formalised in Section 5.
E-Optimally Solving M as M' via Point-Based Value Iteration
The hierarchy of planners offers more than structural insight-it enables practical computation. In particular, the uniform continuity of the value function, established at the level of the marginal planner, allows point-based representations to be leveraged without compromising E-optimality. We exploit this structure to solve the reduced game M' using point- based value iteration (PBVI) algorithm [Pineau al., 2003], yielding an E-optimal solution the original zs-POSG M. At the core of this method is the ability to define action-value functions q. X x D, + R over uninformed occupancy states, from which greedy decision rules are extracted via linear programming. These rules are then used to propagate and refine value estimates. The resulting value function helps extracting a robust focal policy whose exploitability is explicitly bounded in terms of the selected points.
To enable point-based backups, our PBVI Algorithm variant samples a finite set of informed t occupancy states O' that jointly induce a representative set of marginal occupancy states. The process begins with the initial informed state and expands the sample set by simulating one-step forward transitions. For each marginal state C2 E eyg- and for each focal decision rule di and opponent action ag, we compute a successor marginal state (C2,, di az) and reconstruct compatible informed states by exploiting the convex decomposition linking marginal and informed occupancy states via public observation histories. The newly obtained marginal state is retained only if it lies farther-in fi-norm-from the current sample set than any existing point, ensuring the sample density improves in worst-case regions. At each expansion, the marginal set grows by at most a factor of two. This synchronized sampling yields a nested hierarchy of representative informed and marginal occupancy states suitable for accurate, generalisable point-based value backups.
Given an uninformed occupancy state X at stage t and joint decision rules (di, de). the expected cu- mulative discounted payoff under joint policies (Tt, T2,--)) -) is defined as Ama-mmae- (x, di, dz) p(x, d,, d VT, 1.Te (T(x, d, de)). The optimal action-valus function q. is given by q. (x, d,) mi [p(x, di, da) + (T d, de))]. The uniform continuity of v. ensures that q. generalises across nearby uninformed occupancy states.
The optimal action-value function q.: Dj - R is uniformly continuous across uninformed occupancy states. There exists collection & of finite sets &2 of functions 42., each linear over marginal occupancy states C2 and private decision rules di. Thus, for any uninformed occupancy state x and private decision rule di,
Corollary 1.
(x, di)= Σ Pr(tprul (x)
max di (A(A)))
Φr (12) Pr(hz|x, hpwr) min se(Ce_(xhun.b)) di, az), ab. o
Aaab
Point-basee methods approximate the optimal action-value function using finite collection O of finite sets &2 of linear functions 2h2 over sampled marginal occupancy states and decision rules. We now describe how to extract a greedy decision rule for focal player 1 from the uniform continuity of action-value function q. Thanks to the uniform continuity of this function informed occupancy states, this optimisation can be cast as tractable linear program.
7

---

Theorem 6. Let o be an informed occupancy state. Then the decision rule di maximising q(o, -) can be computed as the solution of the following linear program with:
0( (o) (A,1) variables,
-(1011-102) [H2(0)]
[A2l) constraints,
where 8 denotes the largest set of linear functions within any 42 Q1 The linear program is: Maximise
Eoge, Emeristo Pr(h2|o) v(h2. 222
Subject to
Ea EAi EoSeo (i h2) =1, vh E Hi()),
vlh2, 42) S 2m Ea, (( 02 02)11) Eses dz(s, h, a a2) (2, hn), v02, Vo2 02 Vaz A2, Whe E EHH((),
where HG(o) denotes the finite set of private histories of player reachable in O. The variable (a,, (2)h1 encodes the probability of taking action a in history h, assuming the value model $2 drawn from Φ1. The inner constraint ensures that the worst-case evaluation u(h2, 42) is always pessimistic-icc., matter how the opponent reacts, the value function bound holds.
This primal linear program computes solution &1, which induces decision rule dj that is robust to all potential responses from player 2. Solving the primal linear program identifies the safest and most effective decision rule d, under this structure. The solution obtained from the primal linear program can be used to improve the current estimate of the value function. The following result formalises this improvement: the update operator raises the value at least at one informed occupancy state while preserving or improving it elsewhere. This monotonicity ensures progress with each update, forming the foundation of convergence guarantees in point-based dynamic programming.
Corollary 2. Let V and q be the current state- and action- value functions represented by finite collections F of sets I2, and 1 of sets 22, respectively. Let O be an informed occupancy state, and let Eι denote the solution of the greedy linear program from Theorem 6 at O. We define an updated value function VI by augmenting I with new set (2,10,,1)) of linear functions a22e0 given by:
(c2 = Exieo argmin d202, 22 22E.22 02
02. (c2)
0.2 (s, h,) = Ea (a,, h.) (2 h a,, 82).
Then vr(x) 2 v(x) for any uninformed occupancy state x induced by C. and vi(x) > v(x) for at least one such x if the greedy update yields strict improvement.
To further improve scalability. we incorporate two distinct pruning strategies: one that removes dominated elements from the set of linear functions 22 (cf. Algorithm 2) and another that discards redundant informed occupancy states from the sample set O' (cf. Algorithm 3) Each pruning operation introduces approximation error in the value function. While these errors can be controlled
individually, combining both strategies may lead to compounding errors and the loss of formal performance guarantees.
We now present a bound on the exploitability of the focal policy computed by our boset-based value iteration algorithm in the finite-horizon setting of length l. Given any sample set C2 the algorithm produces a focal policy oं with estimated value (b). The exploitability of this policy is defined as = (b) minagen; (b),=((), (b), and quantifies the worst-case suboptimality of o' against best-responding opponent. The exploitability decreases as the sampled set Cl2, becomes denser in the marginal occupancy space; in the limit, Vi (b) converges to the optimal value (b),, and approaches zero. The remainder of this section formalises and proves this bound. To this end, we define the density 8 as the maximum distance from any reachable marginal occupancy state the sample set C/2,ox: more precisely, 8 = max E22 mincrgeeter C| c2ll, Let m > 0 be a constant such that ||r]| S m.
Theorem 7. For any marginal occupancy sample sets C/2 the exploitability of the focal policy obtained via PBVI and evaluated at the initial state distribution, is bounded as
4mo
8 5
(1 7}- [1+ (f+ f+ (f 2)+))
is worth noticing that whenever goes to infinity, our exploitability bound is twice the error-bound from Pineau et al. [2003] for infinite-horizon partially observable Markov decision processes.
8

---

Empirical Evaluation
We evaluate our method on suite of established benchmarks for simultaneous-move partially observable stochastic games (POSGs); Adversarial Tiger. Competitive Tiger, Recycling, Mabe, Matching Pennies, and three Pursuit-Evasion variants. These benchmarks are among the most challenging in the POSG literature; see http://mtmee / cecespaannog//////eeeeeo for detailed descriptions. Several were originally common-par -aaooff problems and have been adapted to the competitive setting by reversing the objective for player 2. For each benchmark, we compare three variants of our PBVI algorithm: PBVI, (baseline, without pruning), PBVI2, and PBVI3 (both applying the bounded pruning scheme from Section 5). We benchmark against the HSVI implementation of Delage et al. [2023] and the CFR+ algorithm of Tammelin [2014]. Table summarises results for the most computationally demanding horizons, reporting the final value reached by each algorithm and the exploitability of the resulting focal policy. Full results for all tested horizons & (2. 4, 5, 70) are deferred to Table 3. To foster reproducibility, the full codebase, including configuration files and experimental scripts, is available at Escudie et al. [2025].
Exploitability & c-Optimal Values: Table presents the algorithms achieving the lowest ex- ploitability in magenta. Across all benchmarks, there always exists at least one PBVI variant that significantly outperforms both HSVI and CFR+. Among these, PBVI3 emerges as the most reliable, consistently yielding the lowest exploitability except for horizons & {4.5) on the Competitive Tiger benchmark and = on Mabe. Nonetheless, PBVI, and PBVI2 also perform favourably, outperforming both baselines in nearly every instance. Notably, CFR+ fails to scale in most cases, running out of memory on many benchmarks, while HSVI frequently exceeds the time limit. This behaviour reflects fundamental limitations of both methods: HSVI's backup operator grows ex- its poor
ponentially with the horizon L, unless the problem exhibits strong structure-explaingg scalability beyond small-horizon settings, with Matching Pennies being a notable exception; CFR+, in contrast, is sensitive to the size of the history space, which explains why it performs well on compact extensive-fore games such as Matching Pennies at = 10, but fails on shallow instances like Competitive Tiger at f = 4, where the set of local histories is already large. Regarding the values achieved, we observe only minor differences between PBVI variants, with most converging to nearly identical solutions. Discrepancies occur primarily on the Competitive Tiger and Pursuit-Evasion benchmarks, where the variants exhibit slightly divergent convergence behaviours.
Table 1: Snapshot of empirical results. Games are ordered by increasing planning horizon E, and within each horizon by ascending number of local histories. For each setting, we report the value v(b) and exploitability 8. OOT indicates a timeout (2-hour limit), OOM denotes out-of-memont runs, and means the exploitability budget was exceeded. Best results are highlighted in magenta.
PRVI.
PRVL
PRVL,
HSVI [Delage
2023]
CPR-
[Tummelin, 2014]
v(0)
v(D)
v(0)
v(0)
vibi
parsii--vasion-31
0.00
0.00
0.000
0.00
11.00
0.00
0.00
0.08
pussuit-vvsion- 3x3x2(2)
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.01
persuit-evasionn-kkku (x3c112)))))))
0.00
0.00
0.00
0.00
0.000
0.00
0.00
0.00
0.00
0.01
pursii-evasion-22233
0.06
0.00
0.00
0.00
01.00
0.00
0.00
0.00
0.00
0.06
pursuit evaseeeeaax.cc..... 2x3x2(33
22.00
0.92
41.00
3.85
0.00
0.00
OCT
0.00
0.10
pursuit-evasonn evasievvsoonnnn 3x3x1()
0.00
0.00
0.00
0.00
0.00
0.00
0.00
0.17
matching- pannies(4)
0.60
0.60
0.01
0.60
alverarial-ligen(()
4076
-0.76
-0.75
ma
0.11
0.11
rocyding(4)
0.36
0.36
01.36
0CT
0.36
0.05
cimperin--tieerr)
.003
0.03
-0.07
0.00
-0.05
0.03
OCT
00M
poruni-vvasion22220
-22.00
37.00
-26.00
48.00
-28.00
1.00
OCT
00M
evasion
0.00
95.00
-6.00
9.00
0.00
6.00
00T
06M
0.00
6.00
-6.00
6.00
11:00
0.00
001
06M
bulching-ennniees
0.80
0.01
0.78
0.01
0.78
0.00
0.50
0.01
0.90
0.01
udversaria--igenn (igen)))
4.95
-0.95
-0.95
0.03
5)
0.12
0.12
rocycling(5)
0.40
0.40
0..40
061
06M
compunive-tipens
-0.66
0.01
-0.08
0.00
-0.10
0.02
00T
06M
matching ponniest"))
1.20
0.05
1.20
0.04
1.19
0.04
001
1.29
0.06
adverseril--igeet))
-1.40
0.00
-1.40
0.09
-1.40
0.00
OCT
06M
mubet?)
0.14
0.00
0.14
0.00
0.14
0.00
OCT
06M
()
0,51
0.07
0.50
0.04
0.49
0.02
OCT
00M
competiive digen')
00.55
0.17
-0.15
pannhsin--pnnnisitt
1.80
1,80
1,80
0.06
alversaiial digen
00M
mabe(10)
0.17
0.18
0.20
001
06M
recyclingt 10)
0.60
0.60
0.60
001
06M
compenine-ggertli
OXT
.0.29
.0.20
00T
00M

---

Adversarial Tiger
Mabc
0:10
Adversarial Tiger
Explaibbilyy
Explsiabillty
Explobubility
Time (min)
0.5
0.1
0.05
10
PBV1,
0.00
PBV12
5
0
250
500
2
PBVIg
Dirations
Fierations
Time (6)
PBVL
CFR+
Figure Exploitability of PBVIx across iterations and runtime on Adversarial Tiger and Mabe (f 5), with CFR+ for comparison. Rightmost plot shows
for PBVI; on Mabc.
Additional Results & Insights: We now discuss complementary insights that characterise the empirical behaviour of our PBVI variants, see Apprendix E.2. In terms of scalability with respect to the planning horizon f, many PBVI versions remain tractable across all tested instances, including large horizons up to = 10, without running O0T or OOM. This is enabled by the pruning heuristics introduced in Section 5, which become essential as the naive PBVI, variant grows increasingly expensive. The bounded pruning mechanisms in PBVI2 and PBVI3 allow deeper backups and longer runs, as illustrated in the first two panels of Figure 3 for the Adversarial Tiger and Mabc benchmarks with = 5. In addition, our PBVI variants converge significantly faster than HSVI and CFR+ across most benchmarks. The third panel of Figure 3 shows PBVI, achieving low-exploitability solution substantially earlier than CFR+ on Adversarial Tiger with = 5. For further convergence statistics and runtime comparisons, by highlighting the trade-off introduced by pruning. Although it weakens theoretical guarantees, the empirical gains in efficiency are substantial. As shown in the final panel of Figure 3, PBVI2 and PBVI3 solve Mabe with & = in fraction of the time required by PBVI, while maintaining comparably low exploitability confirmed in Table 3.
refer the reader to Table 3 in the supplemental material. We conclude
Conclusion
We introduced the first principled and lossless reduction from zs-POSGs to transition-indepeedent zs- SGs. While transition independence has been applied in common-payoff POSGs [Becker et al., 2003, 2004, Dibangoye et al., 2012, 2013b, 2014], this work is the first to extend to adversarial games, providing both theoretical guarantees and scalable planning methods. By exploiting hierarchy of planners and the uniform continuity of the value function, we developed a point-based value iteration algorithm that operates states. The method supports value-function improvement via linear programming, admits an explicit exploitability bound, and scales challenging benchmarks previously beyond reach for dynamic programming theory and algorithms. Our results demonstrate both the theoretical soundness and practical viability of planning with occupancy-sed dependent policies in adversarial settings with imperfect information. Together, these contributions establish a general pathway for transferring dynamic programming theory and algorithms from stochastic games to partially observable settings, and offer a promising foundation for unifying the solution of cooperative, competitive, and mixed- motive POSGs under a common framework. Such unification is groundbreaking because it dissolves the Long-standing divide between algorithmic principles across multi- agent problems, enabling shared planning infrastructure that can adapt flexibly diverse strategic interactions and uncertainty structures.
structured sample of marginal and informed occupancy
Linitations. While the linear programs generated by our method are significantly smaller than those used in HSVI-based approaches, their size still grows with the planning horizon in the worst case, potentially limiting scalability. Future work could explore compact representations local update schemes, such as regret minimisation, to mitigate this bottleneck.
Acknowledgments
This work was supported by the French National Research Agency (ANR) under projects 1N--19- CF23-0018 (Planning and Learning to Act in Systems of Multiple Agents), ANR-19-CF23-0006 (Data and Prior: Machine Learning and Control), and ANR-21-CE23-000 (Multi-Agent Trust
10

---

Decision Process for the Internet of Things). The authors also acknowledge financial support for Erwan C. Escudie through a PhD scholarship from the University of Groningen.
References
David André and Stuart J. Russell. State abstraction for programmable reinforcement learning agents. In Proceedings of the 18th National Conference on Artificial Intelligence (AAAI), pages 119-125. AAAI Press, 2002.
Karl J. Aström. Optimal control of Markov decision processes with incomplete state estimation. Journal of Mathematical Analysis and Applications, 10: 10:174-200 1965.
Raphen Beeker, Shlomo Zilberstein, Victor Lesser, and Claudia V. Goldman. Transition- iinestion-indeeendent decentralized Markov decision processes. In Proceedings of the Second International Joint Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 41-48, 2003.
Raphen Becker, Shlomo Zilberstein, Victor Lesser, and Claudia V. Goldman. Solving transition independent decentralized Markov decision processes. Journal of Artificial Intelligence Research, 12:423-455, 2004.
Richard Bellman. Dynamic Programming. Dover Publications, Incorporated, 1957.
Noam Brown, Anton Bakhtin, Adam Lerer, and Qucheng Gong. Combining deep reinforcement learn- ing and search for imperfect-information games. In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Olivier Buffet, Jilles Steeve Dibangoye, Abdallah Safidine, and Vincent Thomas. e-optimally solving zs-POSGs using Bellman's 's optimality principle. Technical report, Inria Nancy Grand-Est. 2020.
Rafael F. Cunba, Jacopo Castellini, Johan Peralez, and Jilles Steeve Dibangoye. On convex optimal value functions for POSGs. urXiv preprint arXiv:2311.0945 2023.
Aurélien Delage, Olivier Buffet, Jilles Steeve Dibangoye, and Abdallah Saffidine. HSVI can solve zero-sum partially observable stochastic games. Dynamic Games and Applications, pages 1-55, 2023.
Jilles Steeve Dibangoye, Christopher Amato, and Arnaud Doniec. Scaling up decentralized MDPs through heuristic search. In Proceedings of the 28th Conference Uncertainty in Artificial Intelligence (UAI), pages 217-226, 2012.
Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, and François Charpillet. Optimally solving Dec-POMDPs as continuous-state MDPs. In Proceedings of the 23rd International Joint Conference on Artificial Intelligence (ICCAI), pages 90-96, 2013a.
Jilles Steeve Dibangoye, Christopher Amato, Arnaud Doniec, and François Charpillet. Producing efficient error-bounded solutions for transition independent decentralized MDPs. In Proceedings of the 12th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 539-546, 2013b.
Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, and François Charpillet. Exploiting separability multiagent planning with continuous-state MDPs. In Proceedings of the 13th International Conference Autonomous Agents and Multiageni Systems (AAMAS). ACM, 2014.
Jilles Steeve Dibangoye, Christopher Amato, Olivier Buffet, and François Charpillet. Optimally solving Dec-POMDPs as continuous-state MDPs. Journal of Artificial Intelligence Research, 55: 443-497, 2016.
Erwan C. Escudie, Matthia Sabatteli, Olivier Buffet, and Jilles Steeve Dibangaye. Code for e-Optimally Solving Two-Player -em POSGs, 2025. wtthhhtt/////gg wet...wp.ruug rww.nllg.n/. nl/e. c. Seccuddie//eurIPs-22222 POSG. University of Groningen, version 1.0.0, accessed October 2025.
Malik Ghallab, Dana Nau, and Paolo Traverso. Automated Planning: Theory and Practice. Elsevier, 2004. ISBN 9781558608566.

---

Karel Horák and Branislav Bošanský. Solving partially observable stochastic games with public observations. In Proceedings of the AAAI Conference on Artificcal Intelligence, 2019.
Karel Horák, Branislav Bošanský, and Michal Pěchouček. Heuristic search value iteration for one- sided partially observable stochastic games. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 31, 2017.
Leslie Pack Kaelbling and Tomas Lozano-Pérez. Hierarchical task and motion planning in the now. In Proceedings of the IEEE International Conference on Robotics and Automation (ICRA), pages 1470-1477. IEEE, 2011.
H. W. Kuhn. Extensive Games and the Problem of Information. Princeton University Press, Princeton, NJ, 1953.
Adam Lerer, Hengyuan Hu, Jakob Foerster, and Noam Brown. Improving policies via search in cooperative partially observable games. Pruceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 7187-7194, 2020.
Ashutosh Nayyar and Abhishek Gupta. Information structures and values in zero-sum stochastic games. In Proceedings of the 2017 American Control Conference (ACC), pages 3658-3663, 2017.
Ashutosh Nayyar, Aditya Mahajan, and Demosthenis Teneketzis. Decentralized stochastic control with partial history sharing: A common information approach. IEEE Transactions on Automatic Control, 58(7):6644- 1658, 2013.
von Neumann. Zur theorie der gesellschaftsspiele. Muthematische Annalen, 100:295-320, 1928.
Frans A. Oliehoek, Matthijs J. Spaan, and Nikos Vlassis. Optimal and approximate q-value functions for decentralized POMDPs. Journal of Artificial Intelligence Research, 32:289-353, 2008.
Frans A. Oliehoek, Matthijs T. J. Spaan, Jilles Steeve Dibangoye, and Christopher Amato. Heuristic search for identical payoff bayesian games. In Proceedings of the 9th International Conference on Autonomous Agents and Multiagent Systems (AAMAS), pages 1115-1122, 2010.
Frans A. Oliehoek, Matthijs Spaan, Christopher Amato, and Shimon Whiteson. Incremental clustering and expansion for faster optimal planning in Dec-POMDPs. Journal of Artificial Intelligence Research, 46:449-509, 2013.
Frans Adriaan Oliehoek, Sufficient plan-time statistics for decentralized POMDPs. Proceedings of the 23rd International Joint Conference on Artificial Intelligence (IJCAI), 2013.
Johan Peralez, Aurélien Delage, Olivier Buffet, and Jilles Steeve Dibangoye. Solving hierarchical information-sharing POMDPs: An extensive-form game approach. Proceedings of the st International Conference Machine Learning (ICML), 2024.
Johan Peralez, Aurélien Delage, Jacopo Castellini, Rafael F. Cunha, and Jilles Steeve Dibangoye. POMDPs: The sequential central planning approach.
Optimally solving simultaneous-mov Proceedings of the AAAI Conference on Artificial Intelligence, 38 (888)4411-99199 2025.
Joelle Pineau, Geoff Gordon, Sebastian Thrun, et al. Point-based value iteration: An anytime algorithm for POMDPs. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI), volume 3, pages 1025-1032, 2003.
Sina Sanjari, Tamer Başar, and Serdar Yüksel. Isomorphism properties of optimality and equilibrium solutions under equivalent information structure transformations: Stochastic dynamic games and teams. SIAM Journal Control and Optimization, 61(5):3102-3133 2023.
L. S. Shapley. Stochastic games* Proceedings of the National Academy of Sciences, 39(10): 1095-1100, 1953.
Maurice Sion. On general minimax theorems. Pacific Journal of Mathematics, 8(1):111-176, 1958.
Richard D. Smallwood and Edward Sondik, The optimal control of partially observable Markov decision processes over finite horizon. Operations Research, 1(5):1071-1088 1973.
12

---

Samuel Sokota, Ryan D' D'Orazio, Chun Kai Ling, David J. Wu, J. Zico Kolter, and Noam Brown. Abstracting imperfect information away from two-player zero-sum games. In Proceedings of the 40th International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pages 32169-32193, 2023.
Edward J. Sondik. The optimal control partially observable Markov decision processes over the infinite horizon: Discounted cost. Operations Research, 12:282-300 1978.
Daniel Szer, François Charpillet, and Shlomo Zilberstein. MAA*: A heuristic search algorithm for solving decentralized POMDPs. In Proceedings of the 21 Conference on Uncertainty in Artificial Intelligence (UAI), 2005.
Oskari Tammelin. Solving large imperfect information games using CFR+. CoRR, 2014.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning (ICML), volume 70, pages 3540-3549, PMLR, 2017.
Auke J. Wiggers, Frans A. Olichock, and Diederik M. Roijers. Structure in the value function of two-player zero-sum games of incomplete information. In Proceedings of the 22nd European Conference Artificial Intelligence (ECAI), 2016.
13

---

NeurIPS Paper Checklist
The checklist is designed to encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and follow the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No]. or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the relevant information is Not Available.
Please provide short (1-2 sentence) justification right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation. While "[Yes] is generally preferable to "[No]" it is perfectly acceptable to answer "[No] provided proper justification is given (e.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). In general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer is often more nuanced, please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS Paper Checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only use the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: This work introduces the first lossless reduction from zs-POSGs transition- independent zs-SGs, enabling the principled application of broad class of DP-based methods. We show empirically that point-based value iteration (PBVI) algorithms, applied via this reduction, produce s-optimal strategies across a range of benchmark domains, consistently matching or outperforming existing state-of-the-art methods.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
14

---

Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification: Each pruning operation introduces approximation error in the value function. While these errors can be controlled individually, combining both strategies may lead to compounding errors and the loss of formal performance guarantees.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't It acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proof's
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: [Yes]
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless whether the code and data are provided or not)?
Question:
Answer: [Yes]
15

---

Justification:
The paper shall release code and data to ensure reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, provide access the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access to a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g.. a large language model), then there should either be way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors welcome deseribe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, as described in supplemental material?
Answer: [Yes]
Justification: the paper shall release code and data for a faithful reproduction of the main experimental results.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nips.ce)
public/ hellliiggguiese/ee httggguddd/eeeeee SeloodeSuuiissiioooooooo
for more details.
While encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new spen-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https: / /nipss wttpccppppcccceceecc.cccccecccce http:/udddss//eeeee
for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
16

---

The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: While this is primarily a Maaning--fcusser paper, we nonetheless report the parameter settings used in our experiments for completeness and reproducibility.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: While this is primarily a planning-focused paper, we reported exploitability.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g.. Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
The paper provides the computer resources used to conduct experiments.
17

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental rums well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethies
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics https: http:/rrrsss..ppppiiiiiicco wwtppbccc//eteeeeeeeeeeeeeeeeeee htc/pppllcctthhiiiiiiiiiieeeeeee ines???
Answer: [Yes]
Justification:
The paper fully adheres to the NeurIPS Code of Conduct.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is a special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive socictal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: This work is primarily theoretical in nature.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA No, they should explain why their work has societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point that improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional or unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Question: Does the paper describe safeguards that have been put in place for responsible release of data models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
18

---

Answer:
[NA]
Justification:
This work is primarily theoretical in nature.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: [Yes]
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version the asset used and, possible, include URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of in the package should be provided. For popular datasets, paperswi thcode. com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information is not available online, the authors are encouraged to reach out to the asset's s creators.
New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/codeemoodll as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
19

---

Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethies, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [Yes]
Justification:
Guidelines:
The answer NA means that the method development in this research does not involve LLMs as any important, original, or non-standard components.
Please refer to our LLM policy (https: : http///eerpp..eee/ cc/Confferences/2255 /LLM) for what should or should be described.
20

---

A Preliminaries
Actiona
Actions
Ohservationg
Observation;
Observation
Payoff
Payoff
Payoof
Par
player vieupoint
start
State
Plar
State
Plar
State
Pree
Hidden
P
p
P
player I's viewpoint
Ohservation PPgyfff
Observation: Payolf
Observation PPyyoff
Action;
Action
Time
t
t+1
1+2
Figure 4: A graphical model of a two-player zero-sum partially observable stochastic game. Each triple Z (21, Z2, w) comprises private and public observations. The diagram illustrates an influence process over three stages: central nodes represent the hidden states (S:); the top and bottom rows show the private observations and actions of players 2 and I, respectively. Observation nodes also include the local payoff: "+" denotes gain for player 1, and "_" a loss for player 2. Directed edges indicate probabilistic dependencies: actions influence transitions and observations, while observations inform future actions. The shaded region highlights the hidden environment state from each player's 's viewpoint, emphasising the decentralised and asymmetric information structure. This diagram captures the sequential, partially observable, and adversarial nature of zs sS-POSGs. The underlying dynamics decompose into two functions, the state transition matrices {p and the observation matrices (p ), where p(s',z|s. a) pas P3r
B Reducing zs-POSGs to Transition-Indeeeneer zs-SGs
B.1 Proof of Lemma
Lemma 1. The reduced game M' admits well-defined value (b),, which satisfies the minimax identity: (b) = mingzew; max,,ew, V vbo (b) = max min Ver,s,())
Proof. The proof shows that any occupancy-set dependent policy induces valid behavioural strategy, thereby enabling the application of the minimax theorem. Let e X + di, be an occupancy-set dependent policy for player assigning decision rule at each occupancy set Xi.r This induces behavioural strategy in the extensive-form game associated with the zs-POSG. The construction recursive. Let X denote the initial occupancy set induced by the prior {b}. each stage
t = O, ...,,,,, f, define: d (x,(),,,, and for all (h,,, Пubb.e E Hi X Hppb.t define: T,(- huuo.t) = d.,(-Ih,, hpus.t). The next occupancy set is obtained by the deterministic transition X T/(X,,, di,). This construction yields behavioural strategy x, that is fully defined across all stages, consistent with the player's local information, and realisable the extensive- form game associated with the zs- POSG. Since the game has perfect recall, the equivalence between behavioural and mixed strategies
21

---

holds [Kuhn, 1953], and thus the minimax theorem [Neumann, 1928, Sion, 1958] applies to the reduced game M by turning it into a normal-form game where actions are pure strategies also known as deterministic history-dependenn policies [Delage et al., 2023]. This concludes the proof.
B.2 Proof of Theorem
Theorem 1.
The reduced game M. constitutes lossless reduction of the original zs-POSG M.
Proof. The proof verifies that the reduced game M' satisfies the three criteria of a lossless reduction from the original zs-POSG M. Let (1/1 v/2) be a joint policy the reduced game. The value of M under this policy, starting from the initial uninformed occupancy state Xo = b, is given by:
Viri (b) = Ei=o? 7 p(x,, dh.,, d2.)) (x X2.) di, (x.a) x., (x..11
= Σi-o 7 Pts.aa...e.)---//............d a1, a2,)]
Ei-o Esso (etp:
r r(st, a a2.1)
(2)
Eio
r(st, a a2,1) = (b)
(3)
Equations (1)(3) follow from the definition of p. linearity of expectation, and the mapping म (dio...., ..., die)) induced by 1b. This establishes value preservation.
we let (1i9. 25)) be an optimal strategy in M', then for any 1i E V,,
Vernin (b) S Vo (b) S Vil w/ (b).
Let (xx.)) di,, with d- (T( hi.). where X is the occupancy set summarising (d.o.... d..-1). Then, by (3) and (4), for any ni ΠT
Va (b) S V (b) S (b)
(5)
which confirms equilibrium correspondence.
Conversely, any joint policy (T)) in the original game induces decision-rule sequences (d.o...., d.e). which define an occupancy-set dependent policy b such that (x,,) = d,,- By the same construction, V Ver wby (b) V=,,,()), (b), which ensures that all equilibria and values in the original game are preserved in the reduced game.
Finally, the definition of admissible decision rules Di, for M at each stage and player i remains unchanged with respect to admissible decision rules for the original game M
Di Dit-
(6)
The reduction preserves the original observation structure and introduces no informational asymmetry, ensuring that the information structure is preserved.
Combining (3), (5), and (6), conclude that MY is lossless reduction of M.
C
Solving TransttonnInndeeedeel zs-SGs via A Hierarchy of Planners
C.1 Proof of Theorem 2
Theorem 2. The optimal stafe-value function v,,: X; The Mf satisfies Bellman's optimality equations: (x,) = pi(x) if x; E 'r, and Vi,-(x) = optded, (T,((,( d:)) otherwise; with an optimal policy given by V X; + arg opt (T d:)). where the optimisation operator opt corresponds to max for player and min for player 2.
Proof. We prove the theorem by induction the number of remaining stages until the planning horizon É + 1, starting from a focal occupancy set X E X,.
Base case (stage t = e 1): At the final decision stage, the focal planner reaches terminal occupancy set X Ft. By definition, the expected return from this state the terminal reward:
Vi,+ (x) p=()
22

---

which matches the first part of the optimality equations.
Inductive step: Suppose Bellman's optimality equation holds stage 1 1 for all Xirt Xy, i.e.
(x(,,))1) opt opt Vi,a (T, din)))
Xtx+1 E Fi. otherwise.
(Xit-1) =
Now consider stage t. The planner must choose a decision rule di E D, transitioning to x Tx di,), and then continuing optimally from there. The value of applying the optimal continuation policy in policy space n from occupancy set Xi, is:
Vi, (X opt VwEW (x.r)
e opt MunEE.. Visran (Mi, dir))
V1,- eD.
(X, d.t)).
which proves the recursive part of Bellman's optimality equation. Conclusion: By induction, Bellman's optimality equations hold all stages = 1,6-1,,.. 0. The greedy policy v (Xi,) arg eD (T di,)) selects the optimising decision rule at each stage and is therefore optimal.
C.2 Proof of Theorem
Theorem 3. The optimal state-value function V.: X + R of M' satisfies Bellman's optimality equations: v.(x) x E J, and V. (x) maxd, eD, mind [ølx, di, d2) otherwise. For player i, the value of their focal planner at occupancy set x at stage is given by:
di d2)))
(x, o xptxex
[g(x)
+ AX E X,
Proof. We proceed by induction the number of remaining stages until the horizon f 1, starting from any uninformed occupancy state x E X.
Base case (t = f 1): By construction, all terminal states x E I yield no further payoff. Thus, the expected cumulative reward zero: v.(x) 0, for all
Inductive step: Assume that the optimal value satisfies Bellman's equation at stage + 1, i.e., (x(x max, ED, min d, de) ( d, de))] for all with f - f-1 stages to go.
Now consider an uninformed occupancy state X at stage t. The planner selects joint decision rule (di, de), leading deterministically to the next state r(x, d,, de). The expected cumulative reward is the sum of the immediate stage return and the discounted future value:
(x)
max min Vasamas (x), (by definition)
max max min
min
Va (x), (split ni. (di.t, 11.++))
d &f der Fam E7
Delage [2023, Thm. 321
min max d du Taueella mumelha
max min
VaLnnee (x),
(swap min and max)
Delage et al. (2023 Thm. 3.2]
max d dur munell 52m Efaa Vinnm (x).
max min
min
(swap min and max)
max min
max min (p(x, di, db) + + V (7(x, db)))
di, da T Ramllbas
p(x, di db) max min TV Vorun (7 di, Eul TameEee max min p(x, d. db) + (,, db)). d,, dur Dar
max min
(xx, dz))
di,E2t, E22
which confirms the recursive Bellman's optimality equations for the uninformed planner.
23

---

For each player i, recall that the value of M, at occupancy set x at stage f is defined as the worst-case
expected return under any possible realisation of the opponent's strategy:
Vi,- (xi) opt Vi (x), (by definition)
en, (i( X T.(..... (x d.t). die+) ...), die))
opt En, opt Ex g(xe11)
opt opt x g(X++1)
opt un, opt XEEK opt, MED g(((X,, die, d
opt EN opt EX opt MED (g(x)) + +f pxx,, die. d-i,e))
opt opt x EXI opt _, (g(xe) + +f Va.ndd (x)]]
opt EN,, opt XEX opt mn [g(() 72 Vana i (x)] (re-arranging terms)
Observe that any two min two max operators can be swapped freely. Moreover, min and max operator can be interchanged when both appear in the innermost (rightmost) positions. With appropriate ordering of operations, this flexibility allows arranging the optimisation operators in any desired sequence. It then follows that:
v1, (x) xptxex g(x) + 7f optmmen mn opt, v un V (= (x), (swap opt and opt)
xxxxex [g(x) + (x),
where opt is min for i and max for i = 2. This concludes the connection between the focal value function and that of the uninformed planner.
Conclusion: By induction, V. satisfies Bellman's optimality equations across X, and induces the focal planners' values minimax aggregations over their respective occupancy sets.
C.3 Proof of Theorem 4
Theorem 4. The optimal state-value function V defined by Bellman's 's optimality equations in Theorem is linear map over informed occupancy states. Specifically, if x F, then V, v,(x) otherwise.
R of transition transition-indeeenden inddeeendeddtettt zs-SG M,, as
vx(x) E Pr(h a x) maxd a, a min E'D2A q- (O(xhhua)) di Sus de q- (O(x, di hpar de.n.aa) p( di. de. + YV, (O. di de.nnal))
where O(x.h,s) denotes the informed occupaney state induced by (x, hpue).
Proof. The result follows from Theorem 3, leveraging the linearity of and and the fact that uninformed occupancy states are convex combinations of informed occupancy states.
Linearity of p. Suppose x = Enpee c Pr(hpub ix) (Oix,Abaa) 2 @ Then,
plx, di, de) = Em.h En,. x(s, hi h2, hpub) Ea, di Ih, de ( a a2)
= =E Npub Pr(hpubl xx) p(O)))mm)) di de,r.a)
where din. (aj hi) = (((a;) h, hpu)).
Linearity of Let X/ 7(x, di, de). and use the same decomposition of above. Then:
xI(s!, (h, a,, Zi)i, (houb, w)) E. x(s, hr h2, ((s)) Z1, Z2, w/ a, 2z) 11, d(a h; hpm)) Pr(h xx) (O di hp de (sr, (h, a, 2),,, w).
Hence, 7(x, di, de) is convex combination of next informed states.

---

Linearity of v. From Theorem 3, we have:
vx(x)= maxd, min [ø(x, di de) + (x di d2))]
=Σn Mpu Pr(h x) dax. dinoe (p(0 Aon d2. + (TV.(T(0(x)))))) di Bus d2 1)
= E Mpu Pr(hpub x) V- (O(.
where the final equality holds by definition of the informed value V. (O(,Aa))))) by an abuse of notation, completing the proof.
C.4 Proof of Theorem 5
Theorem The optimal state-value function V. X - is uniformly continuous across uninformed occupancy stales. There exists collection I finite sets of functions 02, each linear over marginal occupancy states Cz, such that for any uninformed occupancy state x, we have:
(x(x) E Pr(hpub x) [maxEER Eneeor Pr(h2) hpub: x) min (2.
Proof. The result follows from the definition of the optimal value function of the focal planner and the convex decomposition of uninformed occupancy states x at stage t:
V. (x) max - -e min min Vine-
(7)
= Σ Mpe
pr( x) maxx..-- min x2c-1 Vina-n-2ee (Ox.))
(8)
Pr(hpuh
ni,-- En Pr(h2|X, pub)) min 02 02 (x..
(9)
Apn
= Σ Apn
Pr(hhuu
x) maxper
Σn Pr(h2 x, bouh)) min (e2(C2,(x.,aart)))
(10)
Equation (7) follows from the definition of the optimal value rooted at x. Equation (8) uses the convex decomposition of x across informed occupancy states, that is, En... Pr(hpub xx) (Oxx.) @h..))
Equation (9) follows expressing
convex combination over marginal occupancy states indexed by public and private histories. Equation (10) introduces collection of sets F2, .. one for each focal policy -1,6-t- Although the space of such policies is uncountably infinite- since policies lie in continuum each set 1,,,,..; in Equation (9) is finite, as it contains only deterministic policy trees ó2 22,--1 Each element a2 1,, is linear function over marginal occupancy states, defined as : (s, h)) + 1 h le draw inspiration from the literature on partially observable Markov decision processes [Pineau al., 2003].
D e-Optimally Solving M as M' via Point-Based Value Iteration
Existing uniform continuity properties are weaker. Recent work has established various uniform continuity properties of optimal value functions to support the design of efficient point-based oper- ators [Wiggers et al., 2016, Delage et al., 2023, Cunha et al., 2023]. To formulate these properties precisely, we introduce two notions associated with an uninformed occupancy state: marginals and conditionals. For any uninformed occupancy state x, the marginal ma of player 2 is defined as the marginal distribution x over private histories ha He and public histories hpub E Hppu:
m2(he, huub) = EsEs Emeog x(s, (h, h2, hpua)).
Moreover, for any x, and any pair (h2, hpuo). the conditional occupancy state C2.(x.he,hae) is the marginal distribution over (s, hi) given (he, hout), such that:
Ce. (s, hi) x(s, (h,, h2, hpub))
mz(he, hpwb)
We write C2 to denote the family of such conditionals: Pe.wee) h H2, hpub Huu) and use C2 2 m2 to denote a unique uninformed occupancy state x reconstructed from this decomposition:
x(s, (h,, h2, hpub)) hp. hi) m2(ha, hpub),
'Strictly speaking, we should have referred to marginal occupancy states as conditional occupancy states, in line with their formal definition. Likewise, the marginal planner would be more appropriately named the conditional planner. We will revise this terminology the final version of the paper.
25

---

for all S 8 and (h,, h2, hous) E H. We are now ready to formally present the known uniform continuity properties.
9e (mg)
A
m2 M2
M2
B
M2
Figure 5: Generalization across marginals of the value function given by a collection G {go.. Iog. 9c, } of linear functions over unknown marginals. Figure shows no generalization on marginal m2 because M2 & { M2, m2}. of Theorem D.I. Figure B shows generalization over unknown marginal occupancy state ma from known marginal me with offset x||x C2 @ mell1. cf. Theorem D.2. Best viewed in color.
Theorem D.1 (Adapted from Wiggers al. [2016]). For any arbitrary M, the optimal value functions V. defined in Theorem are convex over marginals, conditioned on a fixed conditional family. That is, there exists a collection G of linear functions over marginals such that for any stage t and any uninformed occupancy state X = O Ma, V.(x) = max Go, (M2), where each IK. is associated with the conditional family C2-
9o. H2 x Kpub +
Wiggers al. [2016] provides detailed proof of Theorem D.I, showing that if two uninformed occupancy states share the same conditional family, value generalisation from one to the other is possible. However, this conditional uniform continuity property does not support generalisation across uninformed occupancy states with differing conditionals. Figure 5 (A) visualises this limitation. To address this, Delage al. [2023] combine the conditional property with Lipschitz continuity, thereby enabling generalisation to previously unseen uninformed occupancy states.
Theorem D.2 (Adapted from Delage et al. [2023]). For any arbitrary M', the optimal value functions V. defined in Theorem 4 are Lipschitz continuous over uninformed occupancy states. That is, there exists a collection of linear functions over marginals such that, for any stage and any uninformed occupancy state X C2 & M2, v=(x) < (ma)+ + x C2 O mz ll, where is the Lipschitz constant associated with V., and Go: E G is any function associated with the conditional family C2.
Despite enabling broader generalisation, Theorem D.2 suffers from loose approximations due to the use of global Lipschitz constants see Figure 5 (B). Furthermore, applying greedy- action selection operators with non- value approximations requires evaluating exponentially many decision rules for player 2: (v, x) + argmax eD. minge p(x, d, dz) +7((r(x, di, de)). Delage et al. [2023] implement such operators using linear programs with exponentially many constraints. When is known, corresponding linear program takes the form:
max {u S p(x, di, de) >V(((x di, de)), Adz E DD2,
for each di E D1, involving O([A2] (f2(() (inel))))))( constraints, where
H2(x) (x) = {(2,, huuo) E Hi2 Hpub Pr(hg, hpub x) > 0}
To mitigate this burden, Delage et al. [2023] restrict attention to previously encountered (stochastic) decision rules rather than the full decision space. Nevertheless, these limitations hinder algorithmic efficiency and highlight the need for alternative approaches. Our uniform continuity property. presented in Theorem 5, is strictly stronger than all previously established results, enabling seamless generalisation across arbitrary uninformed occupancy states. Notably, prior work typically defined the optimal value function over marginal distributions, whereas we define it over conditional distributions of uninformed occupancy states-fore followig the approach commonly adopted in partially observable Markov decision processes [Smallwood and Sondik, 1973, Sondik, 1978] and decentralised variants [Dibangoye al., 2016]. This shift unveils markedly stronger uniform continuity properties.
26

---

D.1 Proof of Corollary
Corollary 1. The optimal action-value function q. X Dt - is uniformly continuous across uninformed occupancy states. There exists collection 4 of finite sets 42 of functions dz, each linear over marginal occupancy states C2 and private decision rules d,. Thus, for any uninformed occupancy state X and private decision rule dr,
(x, di) EPr(h (X)
max (A(P))
01 Σ C2
Σ f22
Pr(h2|x, hpwb)) 02E02
min @2(C2((x....be)) di, a2),
Proof. The result follows from the uniform continuity of V. over uninformed occupancy states (cf. Theorem 5) and the convex decomposition of such states. Starting from the definition of the optimal action-value function: for any uninformed occupancy state x and decision rule di.
q. (x, di> = minge max min 9 (x, di d2).
Expanding the occupancy state over public observation histories huh E Huh yields:
(x,, di) mind: Eny Pr(hpab (x) max min Q (O (Ox,) d, dz).
Refining (xx)) over private histories ha E H2s of player 2, and defining finite set @2, {qmL .oee : δ2,r-1 E 22,-1) of function Φe linear across marginal occupancy states and decision
rules of player 1, induced by policy trees ò2,e-1 2 of player 2, obtain:
min de
Σ Duo
Pr(hpuh xx) max xi.e
Σ
Pr(he) npuh)
Σ de (a h2) cb2(C2.(x.h,n.tt) Pt)) di a2). min de 22
Letting $ = (... - T 11t) and observing that de, (a2) = d2 h2 hpab). we can
apply Neumann [1928] to exchange the min-max ordering:
(x di) Σ Pr(hpab (x)
max ()((
Φn (02) Σ
Pr(helx, huuh) min 0
(2( di, az),
Ape
hg
which completes the proof.
D.2 Proof of Theorem
Theorem Let be an informed occupancy state. Then the decision rule di maximising q(o, :) can be computed as the solution of the following linear program with:
0[ (C)(
[AA,) variables,
-0 - [ [3((()) (A2l) constraints,
where 2 denotes the largest set of linear functions within any 42 Dj The linear program is:
Maximise
Eo.eo. Emerit Pr(h22o) v(h2, 42)
Subject to
Ea EA, Eo,co, ( 02 hn) 11, vh, E H() u(h2, 22) < Σn E. (i 02) de(s, h, a a²) (2, hi),
v0 Vo2 E 02, Va E A2, the E H2(O),
where H(( denotes the finite set of private histories of player reachable in O. The variable (a,,, h1) encodes the probability of taking action as in history h, assuming the value model do is drawn from Φ1. The inner constraint ensures that the worst-case evaluation u(h2, 42) is always pessimistic-i.c.. no matter how the opponent reacts, the value function bound holds.
Proof. Corollary shows that (o, d:) is the maximum over concave combinations of linear functions d2, each defined over marginal occupancy states, i.e.,
(o, d;) maxa,ea(0.) Eogeo, @ (02) Ene Pr(halo) min ore0, (2((2,(0.h)) a)))).
27

---

If we let Çi ( 42]hi) = Φ1 (92) di hi) encode the probability of taking action a in history h assuming the value model drawn from Ø1, then:
{ E , Eo.co, En. min 0.E0 Pr(ha) Φ1 ( o2 (2(C2 di, 22).
To extract greedy rule, we represent q- (o, dh) as linear objective with auxiliary variables u(h2, 02) that lower-bound the worst-case value against each opponent history and linear function, i.e.
u(h2, (2) I Φ1 (42) @2(C2,10,0)) di a2), v VΦ2 E 22 Vaz A2, vh2 H2(0).
The linearity in di and marginal state structure ensures the objective and constraints remain linear, vhh2 42) S Σn Ea a (i 9 h1) Eses (2 h, a ag) (2. h,). This yields a valid linear program whose optimum corresponds to the desired decision rule.
It is worth noting that each set Φ2 is derived from a corresponding set [2; that is, for every di E $2. there exists mapping v: 22 x + 2 such that:
(s, h, a, a2) r(s, a, 22) 7
Σ
pls' 2 22, w/s, a, az) v(zz, w) (h, 21, a,))
Evidently, (02 is exponential in the worst case, i... [02l E O 2aa W.). To enhance scalability when selecting greedy decision rules, one may instead optimise directly over F. thereby reducing the number constraints from exponential to linear.
Theorem D.3. Let be an informed occupancy state. Then the decision rule di that maximises q(o, -) can be obtained as the solution to the following linear program:
O(G [ [A2l- [2e] [W]) variables,
.
-O( 1 [+(((0)| [A2] [Z2| [W]) constraints,
where I2- denotes the largest value function set across all P2 E h. The linear program is:
Maximise
Σ
(h(2)
hEE3G((
Subject
Σ GET BEEAi
Σ
(g(ai)h)) h1)=1, vhn (o)
(h22)) S
ΣΣ Σ Σ
Be(h2, az 22, w), wha H2(O), va E A
BET 2222
(h2, a2, Z2, W) S Σ Σ
(g(ar)hi) aE (h, h2, a az, Z2, w),
B,EA, hiEK,
vTz E f, Vaz E 1h2 E HH2(o), Va E A2, V22 2w e w
where H((0) is the finite set of private histories of player i reachable in O.
The variable (g(ai (h) encodes the probability of taking action a at history h,, under value model T2. The inner constraint ensures that (h(2) is pessimistic estimate-i.e. it remains valid regardless of how the opponent responds. This achieved by ensuring the intermediate evaluation (.(-) is also pessimistic i.e., valid for all a2 f2. The value of following policy is given by:
96.a. (h), he. 2,, Zz, w) + Σ ols, h, h2) -2(s, h,, a1 22, Z2, w).
SES
32: (s. h, a. az Zz, w) + r(s, a, 22)
Σ Σ p(s' Zz, w/s. a 22) azlss h, ai, 21, S'E
Proof. The proof starts with the definition of the greedy decision rule selection at informed occupancy state O at stage assuming uniformly continuous value function V. Let q: (o, di, de) + p(o, d, de)+ (V((( d, dz)). Then, d argmax, ming, q(o. d, d2). The following holds by the application of the uniform continuity property of the optimal value function from Theorem 5:
v(T(o, d,, de)) maxger, Ema. Pr(he, az, Zz, w| di, de)) min @2(C2, d. a.
28

---

If we replace the maX by max) then there is no loss in optimality, i.e.
maX Σ Eiereaa w
EEEr OE ((h) Pr(h2, &g 22, w/r d, (2)))a0000.rrodddd00000aaaa
Notice that the product rule provides us with the following relation:
Pr(si, h, ai 21, f2, az, Z2, W vo de)
Pr(h2, ag. 22, ( d, d2))
h, a 21)
= di (a: hi) d2 ha) Es o(s, h, h2) p(si, 21, 22, w/s, a1, a2).
Exploiting this insight along with the linearity of 02 yields:
v(T(o, di, de)) = max Em.a. Zeen min
Es.rhhh ((E) (s h, a 21) ((aa))))) de(ae h2)
oss, h, h2) p(s,, 21, Z2, w/s, a1, a2).
Define the following two intermediate functions ab.a and B2 g (h, h2, a a, Z2, w) + Eses O hr h2) f2 h, a1, a2 22, W) A2(s, h, a az Z2, w) r(s, a 22) EsrEs ΣnEz, p(sr, 21, 22, w a 22) az(st, h, a1.2)).
Consequently, the action value can be rewritten as follows:
q(o, di, de) = maX
Eneie (alaelhe ((12)
Σ min (ii 9E (h,, h2, ai az. Z2, w).
026
Ze.w
h
Let us define the decision variable 0g (a: Ih:) di (a: /h:) - E(l2) then our greedy decision rule is the solution of the following maximin optimisation problem:
max, mind; En.a. d2 h2) EeEr Σz.w min En.a. (5 hi) I5. (h, h2, a 12.a2, Z2, w).
Using Wald's maximin model we can convert this maximin optimisation problem into a maximisation mathematical program, i.e.,
Maximise
Σnertso (6222)
Subject to
ΣEEn EarA, 05(a) (()) 11, vh (G)
1o(h)) S Eben EzEt, Ewew BE(he, 2 Z2, w), 4he H2(O), va E A2 Bg (h2, 22, Z2, w) EmEa, Emere, (5(a) hi) og (h, he, a az, Z2, w). VT2 Ri Vaz [2, Wh2 E H2((), Va A2, AZN Z2, Vw E W
Then, the solutin of the linear program in the theorem is the greedy decision rule of the focal player, which ends the proof.
D.3 Proof of Corollary 2
Let V and q be the current state- and action-value functions represented by finite collections of sets Fz, and $; of sets 22, respectively. Let O be an informed occupancy state, and let ε denote the solution of the greedy linear program from Theorem 6 at O. We define an updated value function VI by augmenting I with a new set Te,erss.) of linear functions a22(0)) given by:
Corollary 2.
022/02) = Eo.co, argmin
022 6..2 (C2)
22 d2002 azE.A2
02 (s. h.) = Ea (a), O ha) (2 hr a,, 22).
22
Then vI(x) 2 v(x)for for any uninformed occupancy state X induced by Cz and vi(x) > v(x) for at least one such if the greedy update yields strict improvement.
Proof. We are given that the value function V is represented by collection [ of finite sets [2, where each T2 contains functions linear over marginal occupancy states. Let be an informed occupancy state and & the greedy decision rule obtained by solving the lincar program in Theorem 6 at o.
29

---

We define a new set of linear functions (2te,s) supported on the sampled marginal states C2- For
each C2 E E2g. define the linear function
(2,(0)) = Exgeo, argmin 2 d2 az
2..0 (C2)
(s. h1) Ea. (ai, D2 hi) @2 h, al, a2)
These functions satisfy the constraints of the linear program at o and define new set I (.(e))))) We then update the value function by setting
r - Fi=ruurr (rreess))
Let v/ be the value function induced by r, and fix an uninformed occupancy state x such that all the marginal states hz, involved in its convex decomposition lie in Cz Then, by construction of improved state-value function Vr,
vi(x) = max Enpr. Pr(hpubl x) En Pr(h2 hup x) minagera 02(C22tx.Mm..aa))
Since we have added a new set of functions that are constructed to satisfy the linear program constraints o, this new maximum is least large as before. Thus,
vi(x) 2 v(x).
Finally, if the greedy linear program solution & strietly improves the linear program objective compared to the current value function V, then there exists at least one marginal occupancy state C2 C₁ where the new linear function yields strictly higher value than all previous ones. This yields:
vi(x) v(x)
for some whose decomposition includes that C2.
D.4 Algorithms
Algorithm 1 PBVI for M' (resp. M).
function PBVI()
function improve([1,.4)) for E do & - LP(T 1,11, 0) I.r - T (T (T2m)))))))
Initialise C2 Oo.-
Initialise 1, + 0 for all f E (O...., e). while has not converged do for f E, E..., 0 do
end for
improve([ 1.t). end for
for f = 0, .... do
(C2.1, 0₂) < expand(C2,r. Or).
end for end while
Algorithm 2 Bounded Pruning.
function BoundedPruning(f, O')
for 2 E F do refCount((e) 0.
end for for (0' do
2. + argmax Σne Pr(h; 0) min 0z (2((),
refCount((2.)) + ref) end for return
[T2 E f refCount(E)) > 0}
30

---

Algorithm 3 Redundant Informed Occupancy State Pruning.
function PruneStates(O", e)
Initialise 0 <- 0 for O E O' do
12. f argmax Ene Pr(ha] () minozer a2 (2(C2.
end for
for O E O' do isRedundant +- false for of E 0 do
if 1i,,, Pr(h2)0) mingget (2((2,(0.)) - En, Pr(hhao) minozeE. az((2((om))) S e then
isRedundant true and break end if end for if -iReddndant then 0 - U (0)
end if end for return (
D.5 Proof of Theorem 7
Theorem 7. For any marginal occupancy sample sets C22,s,, the exploitability of the focal policy obtained via PBVI and evaluated at the initial state distribution, is bounded as
4md
E S
(1 7)2 [1+ (e+ 11+1) (e+ 22+
Proof. Let Ii be optimal focal policy with value (b). Let (Xo.... Xe) denote the sequence of uninformed occupancy states induced by and the opponent policy TT, for which PBVI yields the worst estimate. Let (X.... ..., x²) be the closest sequence of uninformed occupancy states (Xo, xt) in (-norm, induced by the sampled marginal set (2 As a consequence, the following inequality holds ||x x|111 I 5 for any stage t. Let V1 be the approximate value function, and oi the induced focal policy computed by PBVI over 22 Let V. and v be the value functions induced by pairs of behavioural strategies, each linear over uninformed occupancy states, such that v.(b) (b) and v(b) vi (b), respectively. These functions always exist for a fixed joint policy, e.g., V. = Viray Then.
E Vb. min Vej,n; (b)
= (b) -000--40 v; (b) + (b ginn Vagiag(8) (b) (adding zero).
Since the values of the focal and uninformed planners coincide at the initial state distribution, i.c.. (b) = v. (Xo) and v, (b) v(xo), we have:
(b) vi (b) vx(x) v(xo)
EL p(x:, di.s, d2.)) v(xo) (by definition)
"Ehoo 7t p(x,, di, d2.)) Ele ((((x)) v(x;) v(xo) (adding zero)
Using the convention V.+ = 0, we rearrange terms:
Eiorr plx, di., d2,) + ( v(xen) Ele r'v(x)) (>9r(x0) + E'e v'(1))
Eion' plx,, di,, d2r) + Eto v(x(n) Eio v'v(x)
Eto 2 (o(x,, dr,, der) (((m)) v(x+))
Dio r (q(x, 1 d2,) v(x))).
31

---

Now substitute x in place of X;:
= Ei=o 7 (q(x,, di., -2.)) di.s d2.)) qx,, di.t d2.)) - v(xi))
Ei V (q(x,, d d2,)) q(x, dh d2,)) + q(x,, d d2,1) v(x)))
Because the greedy rule for q(x/ :) achieves value v(x;), we have:
Eio (g(x), di., de,1) q(xx di de, + v(x) - v(xi))
di d2.)) v(xi) qxx, di d2,1) v(x)) = Eio 7' (q(-, di,,, d2.1) - v(-)) -(i-)(xx----- x,)
Applying Hölder's inequality, using the definition 8, and the fact that / is bounded:
(b) (i(b) Eno y/ l1l., di d2,1) v(-)l ||x x/|1+
s 5 Eto 72 119(: di.,, d2,)) - v(-)l
2m E 26-0 7 > nhb, (q and being linear across x))
2m6 E
=0= E Li=b 7
yb-
2md 20-0 1-7
2md E 26=0(> (7 --et1) 21)
T-7
= (1-7}² [1 (l + 1) - ( (e+2)
2md
similar argument yields for this part Vi (b min Vatann (b). the focal policy ni induced by vi (b). Let Vai,- and Vyz be the value functions induced by the pairs of behavioural strategies, each linear over uninformed occupancy states, such that Vur,+ (b) minagen Vag.a; (b) and Vz; (b) Vi (b), respectively.
(b). Let I22 be best-response to
(b) minngen, Ve(,=(()) Vx)(X)) (X))
Let (Xo. x,) denote the sequence uninformed occupancy states induced by xi and the selected best-response π2. Let .y.... X²) be the closezt sequence of uninformed occupancy states to (Xo, X²) -norm, induced by the sampled marginal set C22-z- Then, follows that:
-vx((x)) - (E y p(x,, dh.,, d2.)), (by Definition)
=xx((x)) Elmn"' 7 (V<;(x)) - (x)( - (Ei 7- p(xt, di.t. de.)),, (adding zero).
Using the convention Vz: (Xe+1) = O. rearrange terms:
(Vo;(Xo) Ei 7t Vz (x)) (7 (Xen)) Eia 7- Vxr 1Eio p(x, di de,))
Eloon' Vx;(() Ei 1- vv=; (xi1) Ei. 7. p(xi, dh.,, d2,))
Elorr (Vx;(x)) Ve. pxx, di... de.1))
= Ei.or' (Vx((x) - [o(x, di., d2,) + 7 (xt.)))
Eioo (V=;(x) - (x;(X1, di d2,)), (by Definition)
-Eho (V=;(x)) (x,, di ., d2,1 d= (X/, dr., d2.)) qx, (x/s di,,, d2,)), (adding zero).
Because the greedy rules in 9x; (x,, di., d2.1) achieves value Vo; (xf), we have:
I Etor (Mx;(x) an; (x. d da,) 9x; dh da.)) Vaz (x))), (adding zero)
= ΣEon' ([V=((x) - (x, di,, de.1] [V=; (x. di.t. d2.)))
= =Eron' 2. ((57()) (: di.,, der))) (x: - x))
32

---

Applying Hölder's 's inequality, using the definition of 6, and the fact that r is bounded:
vi (bb) ming Vei,=g(b)
- Et= Y [1 9r; dr. d2.1)l 1|xt
x/11
S 8 Eto 7 [[<;(() - qx; di. d2.)
S 2md Σx= 7o Ei= 7tt
2mo E6 Σ Eh-h 7"1
= 2md 26==
bbー7
6== 1-9
2PM
1-7 26-0 7 - -
=
2md
[1 + ((+1)=+22 - (e 2)++t]]
(1-3)²
Combining both bounds gives the final exploitability guarantee and concludes the proof.
While it is theoretically sufficient to define focal policy by computing values over the entire set of uninformed occupancy states, this approach is often impractical due to the exponential growth of that set with the horizon. To address this, we construct a worst-case trajectory through the uninformed occupancy space by solving sequence of linear programs. At each step, the primal LP from Theorem provides a greedy decision rule for the focal player. To complete the picture, we require dual LP that identifies worst-case response for the opponent, certifying the pessimism constraints that underpin the primal solution. This primal-dual pair induces a compact trajectory of uninformed occupancy states along which focal policy can be explicitly extracted. The corollary below formalises the dual program that supports this construction.
Corollary D.4. Let O be an informed occupancy state. Then the pessimistic evaluation q(o, ) defined in Theorem 6, can equivalently be computed by solving the following linear progrum with:
-O([0,) | (9((()) (A2)) variables,
,(([,) (O) (A,]) constraints,
where
Φ21= maxeo.o, (22.. The dual linear program is:
Minimise
Emerrsto Pr(he o) u(h2, 22)
Subject to
Eorco, ExEo, EaEA, X(92, 02 h2 =1, the E Hc(()).
u(h2, 02) 2 Exseo, EaCA, 1(02, 02 h2, 22) Eses d2 h, a. a2) C2,o,,) h2),
vΦ2 E 91, Vh E (o), Ya
Vai A
The variable X(02, d2, he, 22) E (0, 1] represents the conditional probability of model-action pair (Ø2, a2) under value model set 42 and private history h2. The variable u(h2, 42) upper-bounds the expected value of Player I's return under the induced model &2.. The normalisation constraint ensures that for each he, the conditional distribution M- h2) valid. This dual program reflects the adversary's 's strategy: choosing a worst-case model-action distribution per private history h2 that maximises cost to Player I while respecting model uncertainty through Q2 Φ1
Proof. The proof follows directly from the proof for the primal linear program, see Theorem 6.
E
Experiments
E.1
Benchmarks
We evaluate approach several competitive benchmark problems, adapted from standard multi-agent settings. Their key characteristics are summarised Table
Multi-Agent Recycling. In the original cooperative version, two robots must clean a room rep- resented as a grid by emptying garbage cans. Each robot has limited battery life and restricted view of the environment, including limited observability of the other robot. Coordination is therefore required. We adapt the task to zero-sum setting by altering the reward function: each robot now aims to clean more efficiently than the other.
33

---

Multi-Agent Tiger. The environment consists of two rooms one containing a treasure and the other a tiger. Each agent stands before door and may choose either listen for cues or enter room. Due to stochastic listening outcomes, agents receive noisy observations. Two competitive variants, Adversarial Tiger and Competitive Tiger, were introduced in Wiggers et [2016] study adversarial behaviour under partial observability.
Multi-Agent Broadcast Channel (MABC). This benchmark captures communication scenario where two agents (nodes) must broadcast messages over a shared channel. To prevent collisions, only one node may broadcast at any time. While the original version cooperative- -aneraaiieemmximiiinnng joint throughput- we consider competitive variant by modifying the reward structure.
Matching Pennies. Each player secretly chooses heads tails. If the two choices match, Player wins; otherwise, Player 2 wins. This is simple, fully observable zero-sum game commonly used in theoretical analysis.
This benchmark involves grid-world where an evader attempts to escape pursuer. Both agents can in the four cardinal directions, and each perceives the opponent only when they occupy adjacent cells. The game continues after capture, which rewards the pursuer and penalises the evader. We consider multiple grid sizes and obstacle settings to vary difficulty and observability.
Pursuit-Evasion.
Table 2: Benchmark characteristics, [S] number of hidden states, |Ar:: number of actions for player i,
Iz/: number of observations for player Rmax/ Amin: reward bounds, 7: discount factor.
Problem
|
|A|
AAzl
Rinax
Pmin
7
Adversarial Tiger
2
3
2
2
0.75
-1.25
Competitive Tiger
2
4
4
3
3
0.66
-0,66
Recycling
0.5
-0.39
MABC
4
2
2
2
0.1
0.0
Matching Pennies
2.0
-1.0
Pursuit-Evaan x 2 x
2
16
4
4
6
6
0.0
-100
Pursuit Evasion 3
64
0.0
-100
Pursuit-Evasion Evasion 3 3
2
81
4
6
6
0.0
-100
34

---

E.2
Additional Plots
Adversarial Tiger
Competitive Tiger
Recycling
Value
0
0
PBVI V
HSW VISVIjowrr
3
-2
-1
1,000
2,000
1,000
2,000
1,000
2,000
Mabe
Matching Pennies
0.25
Value
0
1,000 Time (s)
2,000
-2
0
1,000
2,000
Time (s)
Figure 6: A visual representation of the performance of our best performing algorithm (PBVIs) against the HSVI algorithm of Delage et [2023] for horizon = 4 across five different games. Best viewed in color.
Table 3: Snapshot empirical results. Games are ordered by increasing planning horizon and within each horizon by ascending number of local histories. For each setting, we report the value v(b) and exploitability z. OOT indicates a timeout hour limit), OOM denotes out-of tut-oof-eemry runs, and means the exploitability budget exceeded. Best results are highlighted in magenta.
Game (f)
PBVI,
PBVI:
PBVIs
HSVI [Delage al., 2023]
CFR+ ['Tammelin, 2014]
v(b)
v(b)
v(b)
v(b)
v(b)
2
-0.40
0.00
-0.40
0.00
-0.40
0.00
-0.40
0.00
-0.40
0.00
adversarial -iger)()
-0.56
0.00
-0.56
0.00
-0.56
0.00
-0.56
lc-3
-0.56
0.00
competitive-tiger()
-0.02
0.00
-0.02
0.00
-0.02
0.00
0.00
0.00
0.00
0.00
competitive-tiger())
-0.02
0.00
-0.04
-0.03
0.00
O0T
0.00
0.00
recycling(2)
0.26
0.00
0.26
0.00
0.26
0.00
0.26
recycling(3)
0.32
0.00
0.32
0.32
0.00
0.32
1c-2
0.32
2c-2
mabe(2)
0.077
0.00
0.077
0.00
0.077
0.00
0.077
0.00
0.077
0.00
mahe(3)
0.095
0.00
0.094
0.00
0.096
0.00
0.096
0.00
0.096
0.00
Saaching-pennies22
0.20
0,00
0.20
0.00
0.20
0.00
0.20
0.00
0.20
lc-3
Satching-penniesS3
1c-3
0.40
1c-3
0.39
0.00
0.40
0.00
0.40
0.00
35

---

Adversarial Tiger
Competitive Tiger
Recycling
2
Value
-5
3
PBVI,
PBVI2
PBVI3
-00
7
4
2.5
1.5
3
4
MABC
Matching Pennies
0.2
Value
0
2.5
5
0
4
Iterations
Iterations
Figure 7: Performance over = 7 for five benchmark problems. PBVI, PBVI2, and PBVIa perform comparably Adversarial Tiger, Competitive Tiger, and Recycling. PBVIz also matches PBVI, on MABC and Matching Pennies, while PBVI3 struggles more on the latter. Pruning in PBVI, and PBVI; often enables continued improvement where PBVI, plateaus. Best viewed in colour.
36


Reviews:
[{"review_id": "dNIXORmuVo", "reviewer": "Reviewer_e8ES", "summary": "In this paper, the authors present a framework that introduces the first lossless reduction from zs-POSGs to transition-independent zs-SGs, enabling the principled application of a wide range of dynamic programming (DP) methods.\n\nThe paper begins by introducing the problem and detailing the limitations of existing reductions. The authors then reformulate zs-POSGs as transition-independent zs-SGs by decentralizing planning into per-player occupancy sets, thereby preserving value functions, equilibria, and information constraints.\n\nNext, they show how transition-independent zs-SGs can be solved via a hierarchy of planners, which enables more efficient value function decomposition and planning.\n\nFinally, the authors demonstrate how Point-Based Value Iteration (PBVI) can be applied over the reduced zs-SG and validate their theoretical results empirically on a suite of challenging benchmark domains.", "questions": "1. I am curious whether you have considered comparing your approach to recent deep reinforcement learning (deep RL) based methods for imperfect-information games, such as Neural Fictitious Self-Play or other policy optimization frameworks (e.g., actor-critic variants or regret minimization with function approximation). While I understand that these methods often lack the same theoretical guarantees and lossless reductions, they have shown practical success on some large-scale settings. Do you see your framework as complementary to these approaches, or would you expect it to outperform them in terms of exploitability or sample efficiency? It would be helpful to hear your perspective on how your method compares empirically or conceptually to deep RL-based baselines, and whether you envision integrating neural approximators into your framework in the future.", "limitations": "yes", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 3, "originality": 4, "strengths_and_weaknesses": "Strengths:\n1. The problem is very well motivated. I appreciate that the authors clearly articulate the desirable criterion of losslessness early on, which helps frame the technical goals precisely and underscores why prior approaches fell short.\n2. Although I am not deeply familiar with all related literature, the contributions appear to be technically solid and substantial. Sections 3, 4, and 5 each introduce significant and novel technical elements, including the construction of the reduction, the hierarchy of planners, and the uniform continuity results that underpin the approximation guarantees.\n3. Beyond the strong theoretical results, the authors thoughtfully address practical considerations around scalability. The proposed pruning strategies for point-based value iteration are well-motivated, and the experimental evaluation is convincing, showing consistent improvements in exploitability and runtime over prior baselines.\n\nWeakness:\n1. While the theoretical development is elegant, the presentation is quite dense. I think additional figures, diagrams, or illustrative examples would help make the key constructions (particularly the planner hierarchy and the occupancy set definitions) more accessible to readers who are less familiar with the technical background.\n2. One potential concern is memory usage. Because the approach relies on sampling and storing sets of marginal and informed occupancy states, I wonder whether the memory footprint grows significantly with the horizon and problem size, perhaps more so than some regret-minimization approaches. It would be helpful if the authors could clarify this point or provide comparative memory usage statistics.", "was_revised": true, "final_justification": "I appreciate the technical contribution of this paper. My main concern lies in the presentation of the results, which I believe can be improved in the camera-ready version. Therefore, I will maintain my current score.", "rebuttal": "We thank the reviewer for the thoughtful and encouraging evaluation. We are pleased that you found the contributions technically solid, well-motivated, and practically relevant. We address below the suggestions and questions raised.\n\n**(1) Clarity of Presentation – Additional Figures and Examples.** We appreciate your comment regarding the density of Sections 3–5. These sections indeed introduce several structural components, such as the planner hierarchy and occupancy set decompositions, which are central to the reduction and subsequent planning algorithm. In the camera-ready version, we plan to include additional figures and illustrative examples that visually convey:\n\n- The structure and recursive flow of the planner hierarchy\n- The distinction between informed, marginal, and focal occupancy sets\n- Concrete step-by-step transformations from zs-POSG instances into the reduced zs-SG formulation\n\nWe believe these additions will significantly improve accessibility without altering the technical\ndepth.\n\n**(2) Memory Usage and Scalability.** You are correct that PBVI-based methods rely on sampling and storing occupancy states, including marginal and informed sets. Our pruning strategies, as described in Section 6, aim precisely to mitigate this challenge by discarding dominated value vectors and uninformative occupancy states. Also, binary encodings of state–history tuples and history compression can help improve memory usage and scalability (see Dibangoye et al., JAIR, 2016).\n\n**(3) Comparison to Deep RL Methods and Neural Function Approximation.** This is a very insightful question. We view our framework as complementary to deep RL-based approaches, such as Neural Fictitious Self-Play (NFSP), actor-critic algorithms, and deep regret minimisation techniques. While these methods have achieved success in large-scale games (e.g., poker), they generally lack formal guarantees regarding value preservation or solution optimality under partial observability. Our goal is to establish a principled foundation for planning in zs-POSGs, enabling algorithmic transfer from dynamic programming while retaining lossless structure. That said, we agree that integrating neural approximators within our planner hierarchy (e.g., to generalise over large or continuous occupancy spaces) is a promising future direction. Preliminary experiments in this direction suggest that hybrid neural–symbolic versions of our approach could combine the best of both paradigms: structural interpretability and scalability through function approximation. We will mention this explicitly in the discussion section."}, {"review_id": "MAtL8tXQos", "reviewer": "Reviewer_WKef", "summary": "The authors tackle the problem of computing approximate equilibria to 2p0s POSGs, and present a novel framework that is lossless, in the sense that it preserves value functions, equilibria, and information. Based on this reduction, they apply PBVI algorithms, to compute $\\varepsilon$ optimal equilibria in a variety of games.", "questions": "Is there a reason why in the experiments why you don’t compare to the annealing approach of Sokota et al.?", "limitations": "Yes, the authors have addressed limitations.", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper is well-written and tackles an important problem of equilibrium computation in 2p0s POSGs. Their lossless framework allows application of techniques in “vanilla” Markov games to the 2p0s POSGs (PBVI algorithms are the only ones that can be applied). \nIn terms of weaknesses, given my background (or lack thereof), I am not well equipped to assess originality beyond the presentation of the authors. I find the math typesetting a bit odd and in some parts hard to read. It seems that many different typesetting styles are being combined, and personally, that, combined with the color subscripts, makes it harder to read rather than easier because it is distracting. The authors should consider shortening exposition in certain portions to make the graphs and tables in the experiment section larger. While the trends are clear in the graphs, and the figures in the table can be read, they are both quite small, the table especially.", "was_revised": true, "final_justification": "My questions above have all been addressed. The authors said that they will address the formatting concerns in the final revision. My question regarding the comparisons to Sokota et al. have also been addressed.", "rebuttal": "We thank the reviewer for the positive and constructive feedback. We appreciate your recognition of the importance of solving two-player zero-sum POSGs via a lossless reduction, and for highlighting the clarity of the experimental trends. Below, we respond to your suggestions point by point.\n\n**(1) Math typesetting and notational styles.** Thank you for this valuable observation. We acknowledge that the use of colour-coded subscripts (e.g., for player indices) and a mixture of font styles may appear visually non-standard. Our intention was to highlight agent roles and variable types clearly, but we understand that this can be visually distracting. Based on your feedback, we will streamline the notation in the final version—removing coloured subscripts, avoiding non-standard font changes, and adopting more conventional mathematical notation for improved consistency and readability.\n\n**(2) Graph and table sizing.** We appreciate your point regarding the sizing of figures and tables, especially in the experimental section. While we aimed to balance visual elements with structural exposition, we agree that certain graphical components—notably Table 1—are densely presented. In the final version, we will revise the layout to allocate more space to tables and figures, including enlarging key plots. To do so, we will condense surrounding text where possible, without compromising clarity or completeness.\n\n**(3) On the absence of Sokota et al. (ICML 2023) in our experimental comparisons.**\nThank you for raising this important point. We are familiar with Sokota et al. (2023), who propose a KL-regularised formulation of two-player zero-sum games. Their regularisation induces a perfect-information tree structure that facilitates dynamic programming. However, their approach fundamentally modifies the original game’s equilibrium structure through entropy regularisation, which alters the equilibrium value and policies. In contrast, our framework performs a lossless reduction that strictly preserves the original value functions, equilibrium strategies, and information constraints of the zs-POSG.\n\nThis key distinction implies that the two approaches are not directly comparable in terms of solution quality with respect to the original game (e.g., measured by exploitability). Moreover, the scalability of Sokota et al.’s method to large, unstructured zs-POSGs remains to be demonstrated, as their experiments are limited to small gridworlds and simplified poker subgames with fixed trees. That said, we view their approach as complementary to ours—particularly for structured domains where the induced perfect-information tree is compact. We will clarify this comparison in the related work section."}, {"review_id": "F2PVlcYcnY", "reviewer": "Reviewer_smLN", "summary": "This paper presents a method to simplify a zero-sum two player Stackelberg game by reformulating the primal construct of the game to allow for efficient representations and approximation of the players' value function. The authors provide the conditions and definitions for when this simplification is possible. Provide the methodology for this reduction, and theoretical guarantees regarding the algorithms performance, accompanied by empirical results.", "questions": "- Comparatively speaking, what is the more inefficient LP formualtion of the problem and what was the complexity reduction compared if someone were to brute-force the solution?\n- Where is the source-code to reproduce these experiments?\n- How come the CFR baseline is not presented in 3/4 plots?", "limitations": "- I don't see any major limitations of this work, my critique largely lies in the novelty of the methods. I do not believe the LP formulation is game-changing in terms of representing the Stackelberg ZS-POMDP efficiently. It provides a nice construct, good theory, but a more impactful research direction would be to look into kernel methods for non-lienar representations or dual-representations of the MIP/LP format, such that we can transform even non-linear problems into linear problems. Thus the technical challenge of the work is not to high, as I mentioned before, the von Neumann mini-max applies in this setting leading to simple reformulations, whereas in general sum games, a greater technical challenge exists.", "rating": 2, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 2, "originality": 3, "strengths_and_weaknesses": "Strengths:\n- The authors use rigorous methods to convert a Stackelberg zs-POMDP into a more tractable representation. This simplification could have strong ramifications in multi-agent optimization and game theory.\n\nWeaknesses:\n- As a zero-sum game, the mini-max von Neumann theorem applies, it is not overly challenging to show that Theorem 3.4, and subsequently 4.1, holds. This is merely an extension from normal form to extensive form games, and the minimax theorem would still apply to sequential games.\n- In the empirical experiments, there should be standard error measurements on the empirical estimates.\n- This paper in general needs a bit more polish, the empirical results in Table 1 contains some unconvincing results (i.e. the new method poses no significant advantage compared to the baseline CFR.)\n- Other Stackerlberg game solver baselines could also be employed here, such as KKT [1] reformulations of the problem, and gradient descent methods [2]. It was not considered.\n\n[1] Allende, Gemayqzel Bouza and Georg Still (2013). “Solving bilevel programs with the KKTapproach”. In: Mathematical programming 138, pp. 309–332.\n[2] Liu, Risheng et al. (2021). “Towards gradient-based bilevel optimization with non-convex followers\nand beyond”. In: Advances in Neural Information Processing Systems 34, pp. 8662–8675.", "was_revised": true, "final_justification": "First, I believe there was a significant violation of the supplemental appendix guidelines—as I noted in my original review. In its current form, the authors have effectively submitted two papers (a long and a short version), which risks reviewers defaulting to the longer document rather than the standard 8-page submission. While I acknowledge that the theory and proofs warrant extended discussion, this approach is unfair to other authors who adhere to the NeurIPS format of 8 pages for theoretical work. Supplemental material should supplement the main paper, not serve as a second, longer version. Even if this paper is accepted, this issue should be absolutely corrected.\n\nRegarding the theoretical contributions, the work should strive to ensure clear practical relevance. As I mentioned to the authors, aside from Theorem 5.4, I found it difficult to fully appreciate the significance of the other supporting \"Theorems.\" Some read more like definitions, while others seem better suited as supporting lemmas. A clearer organization of the theoretical presentation would really strengthen the paper.\n\nFinally, the absence of a supporting codebase raises serious concerns about reproducibility. This is a major red flag for me. That said, if other reviewers find the theoretical arguments convincing on their own merits, I would defer to their judgment (I may have overlooked hidden ingenuity in the paper’s theoretical arguments).", "rebuttal": "We thank the reviewer for the time and detailed feedback. We address each concern below and clarify key misunderstandings.\n\n**(1) Mischaracterisation of the setting as Stackelberg.** We respectfully clarify that our paper does not study Stackelberg games. Our focus is on two-player zero-sum partially observable stochastic games (zs-POSGs) with simultaneous moves. There is no notion of a committed leader policy or sequential leader–follower interaction. Consequently, suggestions such as KKT reformulations or bilevel gradient methods—tailored to Stackelberg-like settings—do not align with our formal setup. We suspect this mischaracterisation may have influenced the reviewer’s interpretation of the theoretical contribution and choice of baselines. We hope this clarification realigns the assessment with the actual scope of the paper.\n\nThat said, we acknowledge that our framework performs planning for a single (focal) agent\nunder worst-case assumptions, which may resemble leader optimisation in Stackelberg games. From this perspective, the focal agent plans over its own partial information while accounting for a best-responding opponent, which evokes the structure of zero-sum Stackelberg equilibria in partially observable domains. This resemblance may explain the reviewer’s terminology, though structurally our model remains a simultaneous-move game without any commitment semantics or sequential asymmetry.\n\nWhile Stackelberg POSGs strictly subsume zs-POSGs, our focus is not to generalise the setting but to preserve its semantics while enabling tractable and principled dynamic programming. We agree that the planning structure we introduce may inspire extensions to Stackelberg settings, but our analysis and algorithms are currently scoped to the simultaneous-move zs-POSG setting.\n\n**(2) On the novelty and theoretical contribution.** \nThe reviewer suggests that our results follow from von Neumann’s minimax theorem. However, our goal is not to reprove minimax duality, but to construct the first lossless reduction from zs-POSGs to transition-independent zs-SGs. This reduction preserves value functions, equilibrium strategies, and dynamic programming structure, enabling a principled transfer of solution techniques. It resolves a long-standing gap between partially observable game theory and dynamic planning. The reduction is technically nontrivial and does not follow from existing minimax results.\n\n**(3) On the lack of error bars in experiments. We appreciate the observation.** While our approach is deterministic given a model, PBVI relies on sampled occupancy sets, introducing approximation variability. In line with standard practice in computational game theory, we report exploitability per instance. That said, we agree that standard deviations across runs could quantify this variability and will consider including such statistics in the final version.\n\n**(4) On the comparative advantage over CFR.** Our contribution targets scalability, not marginal performance gains. Table 1 shows that CFR fails due to time or memory limits in large-horizon domains, while our PBVI variants continue to produce bounded-ε solutions. These are settings where zs-POSGs become intractable for regret-based methods, yet our structural reduction enables dynamic programming. This is a qualitative advantage arising from the reduced model’s structure.\n\n**(5) On the choice of baselines.** The reviewer suggests bilevel optimisation methods such as:\n\n- Allende & Still (2013): Solving bilevel programs with the KKT approach\n- Liu et al. (2021): Gradient-based bilevel optimisation with non-convex followers\n\nHowever, these works address static bilevel problems with leader–follower structure and do not incorporate stochastic transitions, partial observability, or multi-stage dynamics. For example, Allende & Still reformulate bilevel programs via KKT into MPCCs, while Liu et al. address differentiable bilevel problems from meta-learning. In contrast, our setting involves planning in multi-stage simultaneous-move zs-POSGs using a structural reduction to enable dynamic programming. These approaches operate in a different algorithmic and representational regime.\n\n**(6) On code availability.** As indicated in Checklist Item 5, we commit to releasing all code and data necessary to reproduce the results upon acceptance, in accordance with NeurIPS reproducibility policy.\n\n**(7) On supplementary material formatting.** Our submission follows NeurIPS 2025 formatting guidelines. To aid clarity, we included a supplementary version where hidden content (e.g., extended proofs and diagrams) has been revealed. This version introduces no new claims and serves to enhance transparency, not to circumvent formatting rules. We are happy to restructure this material if the reviewer prefers a different format."}, {"review_id": "WvQ6c1S4cg", "reviewer": "Reviewer_1Gi1", "summary": "This paper aims to solve two-player zero-sum partially observable stochastic games (zs-POSGs) up to $\\varepsilon$-optimality. It introduces the first principled and lossless reduction from zs-POSGs to transition-independent zero-sum stochastic games (zs-SGs), marking the first such reduction to adversarial games. The core technical contribution is a novel hierarchy-of-planners framework that enables this reduction. This, in turn, allows the use of a broad class of dynamic programming-based methods, leading to both theoretical guarantees and scalable planning algorithms. The authors also adapt point-based value iteration methods and evaluate their approach across several benchmark domains, including matching pennies and pursuit-evasion, demonstrating performance that matches or surpasses existing state-of-the-art methods such as HSVI and CFR+.", "questions": "Are there any decentralized algorithms for zero-sum stochastic games that could potentially be applied to your reduced game? Do you think such an approach might improve the performance, particularly in terms of its dependence on the planning horizon?", "limitations": "Yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 3, "significance": 4, "originality": 4, "strengths_and_weaknesses": "The main strength of this paper lies in the hierarchy-of-planners approach. The hierarchy comprises four planners:\n\n* **Focal planner**: Knows only the focal policy and nothing else.\n* **Uninformed planner**: Has access to the opponent's policy and the focal planner's data.\n* **Informed planner**: Knows the public signals and the uninformed planner's data.\n* **Marginal planner**: Has access to the opponent's history and the informed planner's data.\n\nWhile only the focal planner is executed, the other planners provide important theoretical insights into the structure of the value functions. This hierarchy also reveals new structural properties of zs-POSGs, such as optimality equations, strategy selection rules, and the uniform continuity of value functions. The proposed reduction to transition-independent zs-SGs preserves key elements such as the value, equilibrium structure, and information constraints.\n\nThe hierarchy of planners also enables practical computation. The uniform continuity of the value function, established at the level of the marginal planner, allows for the use of point-based representations. This, in turn, makes it possible to apply point-based value iteration methods. A key component of the approach is the definition of action-value functions over the uninformed occupancy states, from which greedy decision rules are extracted via linear programming.\n\nAlthough I did not identify any major weaknesses, I believe the presentation could be improved by including some of the diagrams from the supplementary material in the main body. Currently, the paper's main text feels somewhat dense due to the heavy concentration of technical content.", "was_revised": true, "final_justification": "The paper has novel aspects to it (see the Strengths section for more details). Moreover, the authors have responded to my questions in a satisfactory manner. Hence, I am retaining my current rating of '5: Accept'.", "rebuttal": "We thank the reviewer for their thoughtful evaluation and are pleased that you found the planner hierarchy and theoretical contributions both original and impactful. We address your suggestions and questions below.\n\n**(1) Clarity and Use of Supplementary Diagrams.** We appreciate your point about the presentation. The main body is indeed dense due to the technical depth of the proposed reduction and planner hierarchy. In the final version, we plan to incorporate selected diagrams from the supplementary material to illustrate:\n\n- The structure and recursive flow of the planner hierarchy;\n- The decomposition of occupancy states;\n- Key transitions and value propagation within the planning process.\n\nWe believe these visual aids will significantly improve clarity, especially for readers less familiar with zs-POSG structure.\n\n**(2) On Decentralised Algorithms and Horizon Scaling.** Thank you for this excellent question. While our reduction converts a zs-POSG into a transition-independent zs-SG with centralised occupancy states, the resulting planning procedure is decentralised in an important sense: we construct policies for the focal agent independently of the opponent’s strategy. This property arises from the structure of the reduced zs-SG and the design of our planner hierarchy. This opens up the possibility of distributed variants, where each agent plans over its own focal occupancy space, and coordination is achieved through shared guidance signals (e.g., by exchanging informative subspaces or value vectors). While still preliminary, this line of work shows promise, especially for distributed occupancy-set exploration or parallel policy refinement in structured settings. We will mention this as a speculative but compelling direction in the final version.\n\nRegarding horizon scalability, our method mitigates the exponential growth of the planning space through point-based approximations and pruning strategies. Nonetheless, we agree that future work could explore structured decompositions—such as factored occupancy representations or local Bellman updates—to improve scalability while maintaining solution fidelity. \n\nFinally, we note that decentralised learning or planning may be particularly viable in structured subclasses of zs-POSGs, such as those with sparse interaction or factored observation models. Combining our reduction with decentralised solvers in these settings could yield hybrid approaches that remain efficient without compromising equilibrium quality. While we have not yet pursued this empirically, structured multi-agent benchmarks could serve as a natural testbed. We will highlight this as a promising direction for future research."}]

Author rebuttal:

Meta-review: This paper presents the first lossless reduction from two-player zero-sum partially observable stochastic games (zs-POSGs) to transition-independent zs-SGs via a hierarchy-of-planners framework, enabling dynamic programming methods such as PBVI to compute approximate equilibria. Experiments on benchmark domains show performance on par with or better than state-of-the-art methods. 

From a technical side I think this is a strong paper that solves an important problem via a novel approach (as 3 out of the 4 reviewers agree), but I also agree with most reviewers that the presentation needs some improvement. Reviewer smLN's main reasons for rejection are 1) "violation" of the appendix format, 2) poor theoretical presentation, and 3) absence of a supporting codebase. As far as I know, 1) and 3) do not really violate any policies. Therefore, I still recommend accept, with the expectation that the authors will improve the presentation and eventually provide the codes for reproducing the experiments as promised.
Decision: Accept (poster)