Scalable Solutions to Zero-Sum Partially Observable Stochastic Games through Belief Aggregation with Approximation Guarantees

Scalable Solutions to Zero-Sum Partially Observable Stochastic Games through Belief Aggregation with Approximation Guarantees Supplementary Material Kim Hammar1and Tansu Alpcan1 1Department of Electrical and Electronic Engineering University of Melbourne, Australia {kim.hammar,tansu.alpcan}@unimelb.edu.au Notation See Table 1. Hyperparameters We run all experiments on an M4PRO chip with operating system Sequoia 15.5 and 48 GB RAM. We instantiate all games with the discount factor γ= 0.99. We use the convergence threshold δ= 0.01 for both SAB and HSVI. If convergence does not occur within 2hours of computation, we use the smallest value of δreached after 2hours. In all evaluations except the evaluation on the large stopping game, we instantiate SAB with the set of representative beliefs and aggregation probabilities generated according to Eq. (16) and Eq. (15) in the main manuscript, respectively. We use the OPENSPIEL implementation of NFSP with the default hyperparameters; see Table 2 and (Lanctot et al. 2020). Since both SAB and HSVI are deterministic algorithms, we report their results based on a single evaluation. By contrast, when we evaluate NFSP, we run 5evaluations with different random seeds and report the average results. We use the following random seeds: 834921, 147385, 902613, 376248, 510982. For the patrolling game, we ensure that the graph is the same for both algorithms’ assessments. Additional Experimental Results See Tables 3–6. Linear Program Implementation of SAB From a computational perspective, applying the Shapley operator Hinvolves solving |B| stage games, one for each representative belief. Each of these stage games can be solved through the following linear program: max vsubject to µ1∈M1and uxr(µ1, µ2)≥vfor all µ2∈M2,(1) where the reward function uxr is given as uxr(µ1, µ2) = ˆr(x, µ1, µ2)+γX y∈B ˆpxy(µ1, µ2)V(y). Proof of Proposition 1 in the Main Manuscript Proposition 1. A value function V⋆that satisfies Eq. (5) in the main manuscript exists. Proof. Let ΓTbe a restriction of the game Γto a finite horizon T < ∞. Due to the finite horizon, ΓTcan be represented in extensive form and thus has a well-defined value vT; see e.g., (Myerson 1997, Thm. 4.3, Thm. 4.6). Let (π1,T , π2,T )be a Nash equilibrium that achieves this value and let π1,∞be an extension of π1,T where Player 1follows strategy π1,T for the first Ttime steps and then follows an arbitrary strategy for the rest of the game. Define r= mins,a1,a2r(s, a1, a2)and r= maxs,a1,a2r(s, a1, a2). The expected reward when Player 1follows strategy π1,T is at most v∞=vT+P∞ t=Tγtr= vT+γTr 1−γand at least v∞=vT+P∞ t=Tγtr=vT+γTr 1−γ. Since γT→0as T→ ∞, the bounds [v∞, v∞]converge to a single value, which we denote by v∞. Let v⋆= supπ1infπ2Vπ1,π2(b0). By definition, v∞≤v⋆≤v∞. It then follows from the squeeze theorem that v∞=v⋆is the value of the game. This value exists regardless of the initial belief b0. Hence V⋆(b)is well-defined for all beliefs b∈B. Copyright © 2026, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved. Proof that the Aggregate Belief Game is Well-Defined Proposition 2. The expected value of each stage game of the aggregate belief game satisfies v= max µ1∈M1 min µ2∈M2 [uxr(µ1, µ2)] = min µ2∈M2 max µ1∈M1 [uxr(µ1, µ2)]. Proof. The proof relies on showing that each stage game is a finite, two-player, zero-sum game, for which von Neumann’s minimax theorem holds (von Neumann 1928). A stage game is defined by a representative belief x∈ B and the current value function approximation Vfor the aggregate game. For a fixed xand V, the stage game is a one-shot interaction. 1. Strategy Spaces: Player 1 chooses a mixed strategy µ1∈M1= ∆(A1). Player 2, knowing the true state s∈ S, chooses a behavior strategy µ2∈M2, where µ2is a collection of probability distributions µ2(·|s)for each state s. Both M1and M2 are compact and convex sets. 2. Reward Function: The reward function uxr(µ1, µ2)gives the expected reward for Player 1 in this stage game. 3. Normal Form Equivalence: We can analyze this game in its normal form. A pure strategy for Player 1 is an action a1∈ A1. A pure strategy for Player 2 is a state-dependent strategy; that is, a function σ2:S → A2that specifies a single action for each state. The set of Player 2’s pure strategies is finite, with size |A2||S|. 4. Applying the Minimax Theorem: For any pair of pure strategies (a1, σ2), the reward uxr(a1, σ2)is a well-defined scalar value. The stage game is therefore equivalent to a finite matrix game of size |A1| × |A2||S|. For any such finite, twoplayer, zero-sum game, von Neumann’s minimax theorem guarantees that the value of the game exists and that max min = min max over the corresponding mixed strategy spaces. The expected reward function uxr(µ1, µ2)is the linear expectation of the pure-strategy reward, making it bilinear over the players’ mixed strategy spaces. The conditions of the minimax theorem are therefore met, which completes the proof. Simulation-based Implementation of SAB Suppose the transition probabilities in Eq. (7) of the main manuscript and the reward function in Eq. (8) of the main manuscript are not known in closed form but can be simulated. In that case, the implementation of SAB can be adapted according to Alg. 11. It can be shown that Alg. 1 converges almost surely to the value function of the aggregate belief game, i.e., V⋆. This result holds under standard Robbins-Monro conditions; see (Littman and Szepesv´ ari 1996) for details. Algorithm 1: Simulation-based implementation of Shapley iteration with Aggregated Beliefs. 1: Input: A simulator of the POSG, convergence threshold δ, exploration parameter ϵ, learning rate α, initial representative belief x. 2: Output: An approximation of the value function V⋆. 3: Initialize Q(x, a1, σ2)←1for all x∈ B, a1∈ A1, and σ2∈Σ2, where Σ2is the set of pure stage strategies for Player 2. 4: Initialize π1(a1|x)←1 |A1|for all x∈ B, a1∈ A1. 5: Initialize V(x)←1for all x∈ B and k←1. 6: while Not converged do 7: Sample u∼ U({0,1}). 8: if u < ϵ then 9: Choose a1∼ U(A1). 10: else 11: Choose a1∼π1(· | x). 12: end if 13: σ2←minσ2∈Σ2Q(x, a1, σ2). 14: Reward u, representative belief x′←simulator(x, a1, σ2). 15: Q(x, a1, σ2)←(1 −α)Q(x, a1, σ2) + α(u+γV(x′)). 16: Use linear programming to find π1such that π1(x)∈arg maxπ1minσ2∈Σ2hPa1∈A1π(a1|x)Q(x, a1, σ2)i. 17: V(x)←minσ2∈Σ2Pa1∈A1π1(a1|x)Q(x, a1, σ2). 18: x←x′, α ←α k, k ←k+ 1. 19: end while 20: Compute ˜ Vaccording to Eq. (10) in the main manuscript. 21: return ˜ V. 1In Alg. 1, U(X)denotes the uniform probability distribution over the set X. Notation Description ΓA zero-sum one-sided POSG. NThe set of players. SThe set of states. AkThe set of actions of Player k. pss′(a1, a2)Probability of the state transition s→s′given actions (a1, a2). rThe reward function. γThe discount factor. b0The initial belief state. btThe belief state at time step t. zThe observation function. OThe set of observations. nThe number of states. hkThe history of Player k. πkThe (behavioral) strategy of Player k. ΠkThe set of (behavioral) strategies of Player k. Vπ1,π2(b)The expected discounted reward when the game is played according to the strategies (π1, π2). V⋆The value function of the game. EThe expectation operator. ∥·∥∞The supremum norm. BThe belief space. BThe set of representative beliefs. ρThe discretization resolution. (x, y)Representative beliefs. ϕbx Aggregation probability from belief bto the representative belief x. SxBelief space partition related to representative belief x, i.e., the set of beliefs that aggregate to x. µkStage strategy of Player k. MkStage strategy space of Player k. Σ2Set of pure stage strategy space of Player 2. σ2A pure stage strategy of Player 2. π⋆ kEquilibrium strategy of Player k. ˆpxy(µ1, µ2)Transition probability between representative beliefs (x, y)in the aggregate belief game under stage strategies (µ1, µ2). ˆp(o|b, a1, µ2)Observation probability under belief b, action a1of Player 1and stage strategy µ2of Player 2. F(b, a1, µ2, o)Belief update operator given belief b, action a1of Player 1, stage strategy µ2of Player 2, and observation o. ˆr(b, µ1, µ2)Reward function in the aggregate belief game. uxr(µ1, µ2)Reward function in a stage game of the aggregate belief game. δConvergence threshold of SAB. HShapley operator of the aggregate belief game. ˜ VValue function approximation computed by SAB. NParameter that determines the sizes of the games in the experimental evaluation. V⋆Value function of the aggregate game. Table 1: Notation. Parameter Value Replay buffer capacity 3·106 Reservoir buffer capacity 2·106 Number of hidden layers 2 Number of neurons per hidden layer 128 Anticipatory parameter 0.1 Number of training episodes 3·106 Start value of the exploration parameter ϵ0.06 Final value of the exploration parameter ϵ0.001 Table 2: Hyperparameters of the neural fictitious self-play (NFSP) algorithm. Compute time (sec) Approximation error (SAB) Approximation error (HSVI) N= 1 0.0 69.1 69.1 0.1 24.0 68.0 0.2 12.2 55.7 0.6 1.2 41.4 1.2 0.2 33.6 2.4 0.2 23.7 5.0 0.2 16.9 9.1 0.2 9.3 15.2 0.1 3.1 20.8 0.1 1.09 25.2 0.1 0.5 30.7 0.1 0.1 44.4 0.1 0.0 N= 2 0.0 69.7 69.7 0.1 26.6 68.3 0.6 14.6 41.8 2.4 2.2 23.6 8.7 1.7 6.4 24.8 0.8 0.3 28.4 0.3 0.1 N= 3 0.0 69.7 69.7 0.1 26.6 68.3 1.1 14.6 25.9 7.1 1.9 8.5 209 1.3 0.0 N= 4 0.0 69.7 69.7 0.2 26.6 68.1 2.0 14.6 28.3 17.3 1.8 1.9 209 1.3 0.0 Table 3: Evaluation results for the comparison between SAB and HSVI on the stopping game. Compute time (sec) Approximation error (SAB) Approximation error (HSVI) N= 1 0.0 5 5 0.1 0.1 0.8 0.3 0.0 0.1 0.8 0.0 0.0 N= 2 0.0 66 66 1.1 1.6 41 14.5 1.0 0.7 33.45 0.4 0.1 74.1 0.0 0.0 N= 3 0.0 90 90 1.7 27.42 39.0 10.4 8.3 15.6 71.9 3.3 0.8 N= 4 0.0 102 102 12.9 46 67.7 18.6 19.2 45.8 211.5 7.75 26.9 1201 3.18 9.6 Table 4: Evaluation results for the comparison between SAB and HSVI on the patrolling game. References Karmarkar, N. 1984. A new polynomial-time algorithm for linear programming. Combinatorica, 4(4): 373–395. Lanctot, M.; Lockhart, E.; Lespiau, J.-B.; Zambaldi, V.; Upadhyay, S.; P´ erolat, J.; Srinivasan, S.; Timbers, F.; Tuyls, K.; Omidshafiei, S.; Hennes, D.; Morrill, D.; Muller, P.; Ewalds, T.; Faulkner, R.; Kram´ ar, J.; Vylder, B. D.; Saeta, B.; Bradbury, J.; Ding, D.; Borgeaud, S.; Lai, M.; Schrittwieser, J.; Anthony, T.; Hughes, E.; Danihelka, I.; and Ryan-Davis, J. 2020. OpenSpiel: A Framework for Reinforcement Learning in Games. arXiv:1908.09453. Littman, M. L.; and Szepesv´ ari, C. 1996. A generalized reinforcement-learning model: convergence and applications. In Proceedings of the Thirteenth International Conference on International Conference on Machine Learning, ICML’96, 310–318. San Francisco, CA, USA: Morgan Kaufmann Publishers Inc. ISBN 1558604197. Myerson, R. B. 1997. Game theory - Analysis of Conflict. Harvard University Press. ISBN 978-0-674-34116-6. Sion, M. 1958. On general minimax theorems. Pacific Journal of Mathematics, 8(1): 171 – 176. von Neumann, J. 1928. Zur Theorie der Gesellschaftsspiele. (German) [On the Theory of Games of Strategy]. j-MATH-ANN, 100: 295–320. Compute time (sec) Approximation error (SAB) Approximation error (HSVI) N= 1 0.0 55 55 0.4 40.1 51.2 0.8 7.7 44.5 1.4 7.6 37.1 2.7 3.0 26.3 3.9 2.0 18.6 5.3 1.8 12.0 7.2 1.7 5.1 9.3 1.5 2.9 11.7 1.3 0.4 14.6 1.3 0.1 16.2 0.4 0.1 19.4 0.4 0.0 23.3 0.4 0.0 27.5 0.4 0.0 31.5 0.3 0.0 N= 2 0.0 72 72 0.5 64.1 70.5 4.3 19.9 59.9 19.7 4.5 35.8 27.2 4.3 28.0 50.3 4.2 15.7 80.3 4.2 7.3 130.8 3.7 1.3 220.5 1.9 0 N= 3 0.0 78 78 0.9 65.2 76.8 14.6 21.2 68.9 109.2 6.7 41.8 300.7 5.9 8.4 539.8 5.4 2.9 800.2 2.1 1.3 1200.7 1.7 0.2 2700.2 0.8 0 N= 4 0 83 83 1.3 65.8 79.2 23.5 22.7 73.8 779.6 8.6 38.7 Table 5: Evaluation results for the comparison between SAB and HSVI on the pursuit-evasion game. Compute time (sec) Approximate exploitability (SAB) Approximate exploitability (NFSP) 0.0 1300.0 1300.0±0.0 68.3 721.2 1100.2±293.7 136.5 331.5 930.9±239.3 259.7 87.45 645.6±198.2 419.2 23.7 412.5±152.9 819.8 19.6 400.0±117.3 1000 19.6 490.6±247.8 2000 19.6 391.2±83.1 4000 19.6 168.5±41.5 8000 19.6 56.1±19.8 Table 6: Evaluation results for the comparison between SAB and NFSP on the large-scale stopping game. The numbers in the last column indicate the mean and standard deviation from 5evaluations with different random seeds.