acceptodds
Under review as a conference paper at ICLR 2027

An -Optimal Sequential Approach for Solving zs-POSGs

Abstract

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

Primary area:
reinforcement learning
Keywords:
POSG, competitive POSG, PBVI, Partially Observable Stochastic Game, Game Theory

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_QMeUOpenReview ↗
Rating
3
Confidence
3
Informativeness
3
Presentation
2
Soundness
2
Read review
Paper summary

This paper proposes PBVIseqPBVI_{seq}, an ϵ\epsilon-optimal sequential approach for solving finite-horizon two-player zero-sum partially observable stochastic games (zs-POSGs). The authors reformulate the simultaneous backup of the existing work into two planning sub-stages while preserving the original game value and information structure. By exploiting the max-of-concave structure of the value function, the proposed method separates the simultaneous Bellman backup into two linear programs and reduces the computational cost of the optimization. Experiments on several benchmark games demonstrate improved computational efficiency and lower policy exploitability compared with existing methods, particularly for larger horizons.

Critical strengths
  1. The presentation of this paper is complete and clear. The structure of this manuscript is well-organized. The topic of this work is interesting and useful.
  2. The authors provide a set of solid mathematical proofs.
  3. The experiments efficiently support the proposed method.
Critical weaknesses
  1. I think that a part is missing between steps 1 and 2 in Appendix C.2. Because the derivation process involves a large leap (the transition is too fast), it is difficult for readers to understand the author's line of thought. It is recommended to provide a complete derivation process so that readers can understand the equations in LP2LP_2.
  2. The proof of Theorem 4.5 is based on PBVIseqPBVI_{seq} without pruning. However, Algorithms 3 and 4 employ a pruning strategy. The authors should provide an ablation study to demonstrate the effect of pruning on PBVIseqPBVI_{seq}. Otherwise, Theorem 4.5 will not support the relevant claims in the paper.
Questions for authors

Please review my weaknesses.

2 comments

We thank the reviewer for their time. In response, we have revised the manuscript to include additional explanations and new plots. A summary of the changes is provided below.

The missing derivation between Steps 1 and 2 of Appendix C.2.

Appendix C.2 now starts from the Bellman objective and substitutes the envelope representation of the continuation value. Step 1 expands the successor weighted beliefs, moves the transition kernel onto the continuation vectors, and combines the reward and future value to obtain the backup coefficients. Step 2 justifies the minimax exchange and separates the minimisation by private history. Step 3 derives LP0LP_0 and proves its equivalence to LP2LP_2 in both directions by eliminating the branch variables. The argument includes zero mixture weights and does not assume that every auxiliary inequality is tight at every optimum.

Theorem 4.5 concerns the unpruned algorithm, whereas the experiments use pruning.

We make this scope explicit after Theorem 4.5. Table 3 compares both algorithms with and without all pruning mechanisms. For Seq at horizon~55, pruning reduces runtime from 5454 to 3030 s on Adversarial Tiger, 467467 to 4444 s on MABC, and 101101 to 7272 s on Recycling. Appendix J.2 discusses the full results. This ablation quantifies pruning's empirical effect; the theoretical guarantee remains restricted to the unpruned algorithm.

I thank the authors for their effort to address my concerns and questions. I will maintain my previous positive score for this paper.

Reviewer_hVJWOpenReview ↗
Rating
3
Confidence
2
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

The paper deals with finite-horizon two-player zero-sum partially observable stochastic games (zs-POSGs) with discounted rewards. The authors build upon a work about reduction of finite-horizon zs-POSGs to transition-independent zero-sum stochastic games, where value updates were formulated as linear programs. Since the resulting programs can be expensive to solve, the authors propose sequential factorisation of the optimisation over the joint decision rule that was previously proposed for finite-horizon discounted POMDPs (Dec-POMDPs). Essentially, the simultaneous backup (minimax optimisation over the joint space of decision rules) is replaced by two planning sub-stages per game stage per player. The sequential reformulation is then integrated into point-based value iteration, called sequential point-based value iteration (seq-PBVI). Finally the performance of seq-PBVI was compared to state-of-the-art approaches, where significant advantages of the proposed approach were visible.

Critical strengths
  • Extending sequential occupancy states from Dec-POMDPs to zs-POSGs: To my understanding this is the main contribution of this paper. While it is not clear if the extension is very challenging (especially because a lot of concepts seem already to come from the related work Escudie et al. 2025 and Peralez et al. 2025), the effects of this method is well reflected in the benchmarks. The authors compared their seq-PBVI with state-of-the-art approaches and show that their approach is significantly faster on 77% of the benchmarks while keeping better or slightly worse exploitability. Especially, at larger horizons it is better as compared to HSVI that times out or CFR+ that runs out of memory.
Critical weaknesses
  • The paper is at some places hard to follow: Especially section 2.2. that is crucial for understanding the remainder of the paper is not more informative than the description in the introduction that overlap quite a bit. There are also multiple inconsistencies in naming terms (e.g. hidden vs. latent state). Not critical but the paper would profit from giving more intuition in section 3 that is currently very technical and Figure 3 is in my opinion not really helpful.
Questions for authors

None

1 comment

We thank the reviewer for their time. In response, we have revised the manuscript to include additional explanations.

Clarity of Section 2.2, terminology, intuition in Section 3, and Figure 3.

We revised Section 2.2 to explain the separate roles of the occupancy, player occupancy sets and envelopes. Section 3 now introduces the two planning sub-stages before their formal construction: the first incorporates the first player's rule, and the second applies the original transition and reward. In Section 4.1, we use ''hidden state'' consistently and specify the components of the best-response POMDP state. Figure 3 in the appendix clarifies the distinction between centralized planning and decentralized execution, where players act simultaneously based on their private histories.

Reviewer_GCgZOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The authors propose a modified variant of point based value iteration for solving zs-POSGs, which first factorises each stage of the game into two planning sub-stages for each player in the game. They establish the sufficiency of this alternative representation (this is already a well-known result), and then use it in the construct of their new algorithm PBVIseq. They then test it on several experimental settings where they show the method outperforms other alternatives, where alternative methods like HSVI hit OOT or OOM. The primary trick as I understand it comes in the construction of the sampled occupancies and envelopes to construct a LP update per player in each sequential variant. This is the part that, to my knowledge is new.

Critical strengths
  • Very clear presentation of thje paper
  • Idea novelly combines the "simultaneous occupancy formulation" of Escudie (2025) and sequential representation of player actions.
  • Nice results showing basic properties of PBVI are preserved. Overall I think the strengths outweigh the weaknesses below, though a major question of novelty remains.
Critical weaknesses
  • Fundamental limitation of exponential compute cost in size of game (any method in this vein suffers from this, but perhaps you could trade off accuracy for subexponential growth)
  • No uniform convergence guarantees like you would get with HSVI
  • Question of how much approach adds versus existing PBSSim which works seems heavily based on. In particular, while it is indeed faster, it is somewhat complicated by noisy results on v(b). It would be clearer if there was additional robustness/ablations trading off accuracy and compute time.
  • Bounds found for exploitability apply only to unpruned framework. But they use pruning.
Questions for authors
  • Was pruning similarly used for PBSsim as it is used for PBSseq? How do the results compare if similar pruning is done for each and/or no pruning is done if PBSsim results do not use pruning. I think it should be apples-to-apples for the comparison. If this can be clarified, I will increase my score accordingly.
  • Would you be able to hold accuracy fixed and compare time or vice-versa when looking at seq and sim comparison for clearer comparison?
3 comments

We thank the reviewer for their time and valuable feedback. In response, we have revised the manuscript to include additional explanations and new plots. We hope that these changes address the concerns and questions raised in the review. A summary of the changes is provided below.

Pruning and a fair comparison between sequential and simultaneous PBVI.

Both methods use the same pruning procedures and settings, together with the same hardware, solver configuration, stopping criterion and seed set for each benchmark and horizon (Section 6; Appendix J.3). Table 3 now also compares both methods with all pruning disabled. The sequential method remains faster on all nine instances, by factors of 2.6-15.3. At horizon 5, its runtimes are 54, 467, and 101s on Adversarial Tiger, MABC, and Recycling, versus 216, 2704, and 624 s for the simultaneous method.

Although both algorithms use the same pruning mechanism, its impact on runtime differs. The relative runtime reduction is larger for Sim in six of nine cases, with exceptions on MABC at horizons 4 and 7 and Recycling at horizon 7. Appendix J.2 explains these differences.

Accuracy versus computation time and variability in v(b).

Figure 7 provides exploitability versus cumulative time for the runs shown by iteration in Figure 6. We now discuss it explicitly in Section 6 and Appendix J.2. Near 3600 s, the plotted exploitabilities are approximately 0.003 versus 0.038 on Recycling and 0.0070.007 versus 0.0270.027 on Adversarial Tiger (Seq versus Sim). These curves pair each iteration's mean exploitability with its cumulative time. We use exploitability to assess policy quality and retain v(b) as a descriptive result.

Novelty relative to simultaneous PBVI and sequential central planning.

We clarified this connection in Sections 2.2 and 3. Beyond the sufficient statistic, the contribution is the maximum-of-concave representation at the intermediate planning sub-stage and the resulting zero-sum backup formulations. Theorem 4.4 quantifies how they reduce the coupling in the LP constraints. Section 5 establishes that this planning order preserves the original game's value, equilibrium correspondence and information constraints.

Exponential growth, convergence and the scope of the guarantee.

The backup is polynomial in the stored representation; private histories and that representation can still grow exponentially with horizon. We state this limitation in the conclusion. Theorem 4.5 gives an exploitability bound for unpruned PBVI that tends to zero as the covering radius tends to zero. It does not prove that the sampling procedure achieves any prescribed radius in finite time, nor extend the guarantee to the pruned algorithm. We clarify these distinctions after the theorem. The pruning ablation measures the practical effect of pruning and does not replace a proof for the pruned method.

Thank you for the follow-up. This addresses most of my concerns. I am willing to increase my score to 3 (I actually did but have since reverted to 2 just waiting on final point addressed) but can the authors address my last concern on the theory not extending to pruning? Can the theorem be extended to pruned version? If pruning is essential can this be stated up front as a limitation clearly? If it is not then please also indicate this.

Thank you for following up on this point.

Pruning is not required for our theoretical result: Theorem 4.5 applies to unpruned sequential PBVI. The ablation in Table 3 also shows that, with all pruning disabled, sequential PBVI remains faster on all nine tested instances, by factors of 2.62.6–15.315.3.

To address the remaining theoretical question, we have added Appendix J. Corollary J.4 extends Theorem 4.5 to bounded pruning under the stated assumptions. The proof bounds the pruning loss at each sub-stage and propagates it through the sequential backups, yielding an explicit additional term in the exploitability bound. The assumptions and full proof are provided in that appendix.

Comments on the paper

1 comment

We thank the reviewers for their careful reading. The responses below refer to the revised manuscript; shaded blocks identify the changes.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.