acceptodds
Under review as a conference paper at ICLR 2027

Conservative Policy Iteration for Zero-Sum POSGs

Abstract

Occupancy-state reductions make dynamic programming possible for zero-sum partially observable stochastic games (zs-POSGs). Existing point-based solvers usually optimise a central value function. This restores Bellman recursion, but it requires point-based updates over high-dimensional occupancy spaces. We introduce an approximate policy-iteration algorithm for finite-horizon zs-POSGs. The method maintains one policy per player and updates both jointly along occupancy trajectories induced by conservative policy updates. Instead of approximating a full central value function, each update uses a single supporting hyperplane induced by the current joint policy. The algorithm alternates local policy improvements, conservative updates, and persistent exploration. Computation is therefore concentrated on occupancy regions where the current joint policy is exploitable. On finite-horizon zero-sum POSG benchmarks, the method is competitive at small horizons and often improves the runtime–exploitability trade-off at larger horizons compared with PBVI, HSVI, and CFR+.

Primary area:
reinforcement learning
Keywords:
simultaneous POSG, competitive, game theory, policy iteration, zs-POSG

Reviews

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

The paper proposes a novel approximate policy-iteration algorithm called Conservative Policy Iteration (CPI) for finite-horizon zs-POSGs, maintaining one policy per player and updating both jointly along occupancy trajectories induced by conservative policy updates. The proposed algorithm alternates local policy improvements, conservative updates, and persistent exploration. Each player's current policy leads to a value function in the corresponding player-specific planning process. Instead of approximating a full central value function as several methods do, the policy-induced value function is leveraged by CPI for local Bellman backups, and then an improved decision rule for one player is computed from its current value function. The improved decision rules are integrated into current policies, and GLIE perturbations allow exploration to continue, such that updates are performed when the current joint policy is challenged by an adversarial interaction. Convergence guarantees depend on exact local safeguards, sufficient coverage, and the stated regularity assumptions. A CPI evaluation on standard zero-sum, finite-horizon POSG benchmarks is presented, and the results demonstrate that the method is competitive on short horizons. Furthermore, over longer horizons, it often improves the trade-off between runtime and exploitability compared to the PBVI, HSVI, and CFR methods.

Critical strengths

The problem is well motivated: combining player-specific value representations with executable policies and local Bellman backups is relevant. The focal belief construction and conservative policy iteration are conceptually interesting. The complexity comparison with prior LP formulations is potentially valuable if correct.

  1. Focal-belief construction: restricting each player’s backup to a player-specific belief game yields executable policies together with local value representations. This matters for the decision because it is the paper’s main route to avoiding global LPs over the full belief space, which is the source of the claimed complexity gain.

  2. Conservative policy iteration with GLIE exploration: averaging improved decision rules conservatively is a sensible way to stabilise learning in zero-sum games. If the convergence argument is repaired, this would be a useful and general principle for zs-POSGs.

  3. A different algorithm targeting the main scalability bottleneck Existing occupancy-based solvers for zs-POSGs restore Bellman recursion by approximating a central value function, which forces point-based backups over high-dimensional occupancy spaces. To overcome that issue, the paper proposes approximate policy iteration with one policy per player, updated jointly along occupancy trajectories, each update relying on a single supporting hyperplane induced by the current joint policy. This bypasses the full value-function approximation and focuses computation on occupancy regions where the current joint policy is exploitable. The above description matters to my assessment because the cost of point-based updates is precisely what limits existing methods as the horizon grows. A viable policy-based alternative is a substantive contribution, not only a refinement of PBVI/HSVI-style solvers

4.Evaluation on real datasets and against strong baselines generally used in the literature The CPI method is compared with PBVI, HSVI and CFR+, using exploitability, relevant metric for zero-sum games. The numerical results show that the method is competitive at small horizons and improves runtime-exploitability trade-off (in most studied cases) at larger horizons, which is the regime where many solvers struggle. This is relevant because it provides empirical support that the design choice is actually good (practically) for the setting it was designed for.

Critical weaknesses

The main weaknesses are the inconsistent value-function claims, the incomplete algorithm, the fragile convergence argument, the unbounded |Λ| dependence, and the insufficient empirical validation. The current version is not reproducible and does not yet support the convergence claims or a favorable runtime/exploitability trade-off.

  1. Incomplete Algorithm 1 (l. 270–282): VECTOR is undefined, the schedule for (ε_k) is not given, Recurse uses t without receiving it as a parameter, and the text refers to “lines 4, 10, 11–12” that belong to different functions.
  2. Fragile theory: Lemmas 14–17 and the proof of Theorem 7 (see Soundness) do not support the convergence claim. Λ is likely a finite subset, so the computed value is optimistic and the polynomial LP complexity in Table 2 hides the growth of |Λ| across iterations.
  3. Evaluation fairness: for CPI, exploitability is “obtained directly from the algorithm”, whereas for CFR+ it goes through a separate evaluation procedure. It is not clear that a common exact evaluator is used for all methods.
  4. Dependence on pruning: Table 5 (no pruning) shows CPI becomes much slower (Mabc T=5: 29 s to 2176 s; Recycling T=5: 213 s to 5146 s), yet pruning is not described anywhere in the main text.
  5. Mixed and limited results: CPI loses on Adversarial Tiger (ε=0.24 versus 0.18 for PBVI at T=10). The extension to extensive-form games is only a proof of concept without results, and the benchmarks are small.
  6. Use of AI: the authors state that AI provided “critical ingredients” to the proofs. This warrants a careful reading of the proofs, which is where several of the issues above were found.
  7. Conditional guarantees CPI is motivated by avoiding the coverage requirement of point-based solvers. Yet, the CPI convergence holds under exact local safeguards, sufficient coverage and regularity assumptions. Theorem 2 does not state this condition, and the paper does not show how exploration ensures it. This could matter because the efficiency claim (focused updates) and the correctness claim (convergence) rest on requirements whose reconciliation is hard to find in the current version of the paper.
  8. Missing Fictitious-play baseline The CPI update (step-size averaging toward an improved decision rule + noise) seems to be structurally similar to generalized weakened fictitious-play, which the paper mentions, but no fictitious-play variant is evaluated (and no practical reason is provided). This matters because without it, the added value of the player-specific occupancy value representation is hard to isolate and to assess.
  9. Exploitability evaluation How is exploitability approximated, and is the procedure the same for all methods? This could be helpful to determine whether the reported values over- or under-estimate the true gap. Also, does the same reliability caveat apply to CPI, HSVI and CFR+ at the longer horizons where CPI is claimed to improve the trade-off? It could be interesting to report exact exploitability where it is tractable.
  10. Metrics not defined Several abbreviations and metrics are not defined. Although these are commonly used terms (in game theory), it would be preferable to define them clearly to help the reader understand what these concepts mean in our specific context. For example, the concepts of “exploitability” and “occupancy trajectories,” as well as acronyms such as PBVI and HSVI, etc.
Questions for authors
  1. Clarify the value-function structure: linear vs piecewise-linear concave vs convex, and fixed-policy vs optimal value.
  2. Provide the complete Algorithm 1, including Recurse, LP, Λ updates, and GLIE schedule.
  3. Theorem 6 and the LP appear only in Appendix A.6.1. Please state them in the main text, justify the polynomial complexity, and bound |Λ|.
  4. Justify the stochastic-approximation conditions and the approximation error between F̃_i and F_i.
  5. Provide full empirical details: seeds, hyperparameters, time/memory limits, code, and baseline implementations.
  6. Clarify the algorithmic difference from Escudie et al. (2025) and Delage et al. (2023).
  7. Describe the pruning procedure and report all main results with and without it.
  8. Confirm that the same exact exploitability evaluator is used for CPI, CFR+, PBVI and HSVI.
  9. Is Λ a subset of the full vector set? If so, how does the resulting optimism affect the guarantees?
  10. Coverage condition. The introduction says convergence requires “sufficient coverage”, but theorem 2 does not state this condition. How is coverage formalized, and does GLIE exploration provably ensure it in occupancy space?
  11. Relation to fictitious-play. How does CPI differ from generalized fictitious play in occupancy space and how does it compare empirically with a fictitious-play baseline?
  12. How does CPI relate to Kakade & Langford (2002)’s conservative policy iteration, which the paper cites in Section 4.2 of page 6?
  13. How is exploitability approximated, and is the procedure the same for all methods? does the same reliability caveat apply to CPI, HSVI and CFR+ at the longer horizons where CPI is claimed to improve the trade-off?
2 comments

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

1. Value-function structure

The focal value function's property depends on the adopted point of view. Player i's focal value function associated to a fixed policy is linear over Bti\mathcal{B}^i_t (Theorem 1) while it is piecewise linear concave if we consider it over occupancy space Ot\mathcal{O}_t (Proposition 1).

Player i's optimal value function is convex over Bti\mathcal{B}^i_t.

2. Typos in Algorithm 1

The revised version includes correction of Algorithm 1. We could not find the source of the incorrect line references.

3. Justify the polynomial complexity, and bound ∣Λ∣|\Lambda|.

∣Λ∣\lvert\Lambda\rvert is only bounded by the size of the deterministic policy space, which is not polynomial, so the original wording was too strong and potentially misleading. We have revised the paper accordingly.

Nevertheless, the storage is memory-efficient. The focal value of a policy πt:T−1i\pi^i_{t:T-1} is stored over Ot\mathcal{O}_t rather than Bti\mathcal{B}^i_t (Proposition 1). Over this space, it is represented by a \underline{finite} set of vectors Λ\Lambda, each encoding a deterministic best-response policy, of which we keep only a subset in practice. Moreover, the best response computed at a history ht−ih^{-i}_t can be reused at any other history hˉt−i\bar{h}^{-i}_t. A set Λ\Lambda thus represents up to ∣Λ∣∣Ht−i∣\lvert\Lambda\rvert^{\lvert\mathcal{H}^{-i}_t\rvert} best-response policies, exponentially more than the number of stored vectors.

In our experiments, each Λ\Lambda contained about 20 vectors, depending on the benchmark and the horizon. With only 4 histories, this already represents up to 204=160,00020^4 = 160{,}000 best-response policies per stage.

4. Stochastic-approximation conditions and the approximation error

The stochastic-approximation conditions stems from (Benaim and al. 2005): Ui,k+1U_{i,k+1} is either a deterministic or random perturbations. One possible assumption on the perturbation satisfying the convergence is mentioned in Theorem 3 [Added after discussion with Reviewer Gyou](see Appendix B.1 for further details).

In the revised version, the continuous-time and discrete-time dynamics are unified (Definition 4, now in the main body). This simplifies the proof without any loss in the proofs or in optimality: the update remains a safe improvement direction produced by the LP.

5. Empirical details

Seed = 42, hyperparameters are provided in the revised version in Appendix, time/memory depends on the horizon, we ran as much as we could each algorithm. The code contains implementation of PBVI and CFR+. HSVI is the code provided by the authors Delage et al. Owing to past experiences in which our code was fed to AI tools without our consent, we will provide it after publication only.

6. Difference from Escudie et al. (2025) and Delage et al. (2023).

Delage et al. (2023) rely on Lipschitz continuity to compensate for the weaker generalization of their value function, stored over Δ(Hti)\Delta(\mathcal{H}^{i}_t) rather than Ot\mathcal{O}_t. Escudie et al. sample points (and, by extension, policies), which makes their LP heavier. We keep a single point per iteration, reducing LP compelxity.

7. Pruning procedure

“pruning” was a misleading term (from PBVI), and we now say “compression” in the captions. The main-body results use the lossless occupancy-state compression of Dibangoye et al. (2016), which merges histories with identical conditional distributions in Ot\mathcal{O}_t and thus reduces the cost of the update operator. Table 4 does not use it while the main results do. (Appendix D.3)

8. & 13. How is exploitability approximated?

Exploitability is approximated by fixing player ii's policy πi\pi^i, which induces a sequence of occupancy states (beliefs). Player −i-i then faces a POMDP with state space S×HiS \times H^i, actions A−i\mathcal{A}^{-i}, and observations Z−i\mathcal{Z}^{-i}. Its lossless reduction to a belief-MDP yields beliefs b∈Δ(S×Hi∣H−i,πi)b \in \Delta(S \times H^i \mid H^{-i}, \pi^i), which coincide exactly with the conditionals. Applying PBVI to this belief-MDP provides an approximate best response and hence an exploitability estimate. Exact solutions are intractable for the long horizons considered. CPI, CFR+, and HSVI use the same evaluation procedure (Appendix D.2)

CPI uses the same procedure: Λ\Lambda contains precisely the vectors computed by PBVI on the belief-MDP induced by πi\pi^i. Thus, this computation is already part of PBVI (zsPOSG) and CPI, but must be performed separately for CFR.

9. Is Λ\Lambda a subset of the full vector set? If so, how does the resulting optimism affect the guarantees?

An object Λ\Lambda compactly represents a single vector of Figure 1. Each vector in Λ\Lambda gives the value of player ii's policy against one best response at a history ht−ih^{-i}_t. A finite set of vectors thus represents a policy over the entire occupancy space, whereas only ∣Ht−i∣\lvert\mathcal{H}^{-i}_t\rvert vectors are needed to represent its focal value locally.

Including more best responses makes the value function more robust over the whole domain, but keeping a subset is sufficient for two reasons:

  • some deterministic policies are never a best response;
  • a few vectors represent many best responses.

The perturbation guarantees also cover this approximation. Since Λ\Lambda approximates a vector defined over Bti\mathcal{B}^i_t (Figure 1), the operator FiF^i may differ from the one used in the proof. This error can be absorbed into the noise term Ui,k+1U_{i,k+1} and, by uniform continuity, is bounded, so it satisfies the corresponding condition of Theorem~3. It decreases as Λ\Lambda grows and vanishes when Λ\Lambda contains all possible vectors [Added after discussion with Reviewer Gyou](see Appendix B.1 for further details).

10. Coverage condition

Sufficient coverage concerns the availability of the supports of the occupancy state and, consequently, of the conditional distributions. GLIE perturbation does not guarantee occupancy-space coverage; rather, it keeps the algorithm away from the simplex boundary, where updates may become unstable and conditional distributions may vanish. This issue was also reported in Kakade’s work (see our answer below). We revised this notion.

11. Relation to fictitious-play

Regret Matching has a clean, dimension-robust O(1T)O(\frac{1}{\sqrt{T}}) guarantee. Fictitious Play has cheap iterations and an intuitive best-response structure, but its worst-case convergence is poor and its behavior depends on tie-breaking. For solving zero-sum games, RM+/CFR+ is the better default, and FP is mostly of interest as a learning model or when a best-response oracle is the only thing you have.

The link with fictitious play concerns our proof technique, not the algorithm itself. As Benaïm et al. (2005) did for fictitious play, we prove convergence of the continuous-time version of CPI, then transfer it to the discrete algorithm via stochastic approximation.

12. How does CPI relate to Kakade (2002)’s conservative policy iteration?

We extend conservative policy updates to multi-agent, partially observable problems and address the same restart issue: vanishing conditional occupancy states can destabilize subsequent updates. As in their work, we prevent this through a small GLIE perturbation (equivalently, a restart distribution).

Use of AI: the authors state that AI provided “critical ingredients” to the proofs.

The main contribution of AI in this regard was helping us identify Benaïm's work, which provides an alternative framework for proving convergence through continuous-time dynamics. We subsequently developed the convergence analysis of CPI using this framework which is indeed a critical ingredient of the proof. We acknowledge the importance of carefully distinguishing the ideas and results originating from the cited work from our own contributions.

The extension to extensive-form games is only a proof of concept without results, and the benchmarks are small.

We successfully implemented and solved Kuhn Poker as an extensive-form game. Since extensive-form games are outside the scope of this paper, we consider this extension a proof of concept rather than a complete experimental contribution.

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

This paper proposes a policy iteration algorithm for the games of two players with sum equal to zero. In the settings, each player only see part of information not full information of the game. The basic idea is to maintain each policy for each player and then see the effectiveness of each policy regarding the game and have small updates to improve it. This helps to save cost to build a whole complete policy regarding optimization cost.

The difficulty lies in the fact that we don't have the full state of envs and so the authors proposed to use central occupancy state which contain the distributions of envs's state, player 1's trajectory history, player 2's trajectory history and the shared history. The proposed method begins by constructing a unique perspective for each player, referred to as a "focal belief."

A "focal belief" is a distribution over conditional states - describing the hidden state of the environment and the specific history of a focal player - conditioned on the information available to their opponent. This representation allows the algorithm to evaluate the payoff that a player’s current strategy can guarantee against an opponent who is responding optimally. The method employs a value function tied to that specific strategy, rather than attempting to approximate the global optimal value function.

In each iteration, the algorithm propagates "occupancy states" forward based on the current strategies, then refines decision rules in a backward pass, starting from the final stage. For each player, a linear program selects a decision rule that maximizes the worst-case payoff, while keeping the player’s subsequent (continuation) policy fixed. This improved rule is then combined with the previous one to perform a cautious update. An additional exploration component is incorporated to ensure that actions and information histories with potential significance do not lose all probability of occurrence. Both players repeat this process, focusing their computational resources on the occupancy states generated by their own evolving strategies.

Critical strengths

Contributions are: First, the paper propose a player-specific representation based on "focal beliefs," which allows for the evaluation of a player's policy against an opponent's optimal response. Within this framework, the authors characterize the structure of the value function: the value of a fixed policy is linear with respect to the focal belief, while at the conditional level, it can be expressed as the minimum over a set of α\alpha-vectors. Leveraging this structure, they formulate a linear programming (LP) problem for local policy improvement. This formulation optimizes the decision rule at the current step - holding the continuation policy fixed - while ensuring that all decisions remain implementable based solely on the player's private information. Next, they propose the CPI algorithm, designed for both players, which integrates occupancy expansion, backward improvement, conservative averaging, and exploration. Finally, they provide a theoretical result establishing conditional convergence to the set of Nash equilibrium, and they empirically evaluated the trade-off between runtime and exploitability.

Critical weaknesses

Key weaknesses include:

  1. Theorem 2 establishes convergence conditions based on stochastic approximation assumptions - specifically concerning the noise component and the discrepancy between the discrete operator and the continuous-time dynamics. However, these conditions are not defined with enough precision to determine whether Algorithm 1 satisfies them. In particular, the proof should clarify the relationship between the linear programming (LP)-based update direction - denoted as F~(π)−π\widetilde F(\pi)-\pi - and the gradient-based dynamics defined in Definition 4. Furthermore, it should explain how the exploration perturbation aligns with the stated assumptions.

  2. Lemmas 14–16 rely on stage-specific step-size selections to ensure improvement toward the original objective. In contrast, Algorithm 1 employs a uniform step size across all stages. The manuscript fails to demonstrate that this uniform step-size schedule provides the same theoretical guarantees, nor does it specify a practical, implementable schedule consistent with the arguments presented in the proofs.

  3. The manuscript should clarify how this method differs from the sequential approach - discussed in a 2026 study on solving zero-sum partially observable stochastic games (zs-POSGs) - with a particular focus on the computational advantages of the fixed-policy formulation. A direct comparison with the sequential PBVI method, under equivalent conditions regarding pruning and evaluation techniques, will help determine whether the proposed approach truly offers any additional practical advantages.

Questions for authors
  1. Theorem 2 at line 323, the formula for the policy update contain an extra Ui,k+1U_{i,k+1}, can you help to clarify what is the standard stochastic approximation conditions on Ui,k+1U_{i,k+1} and the approximation error between the discrete operator F˜iF˜i and the continuous dynamics Fi (see Definition 4)?

  2. Lemmas 14 - 16 establish improvement using carefully chosen, stage-dependent step sizes, while Algorithm 1 employs a common step size αk\alpha_k. What ensures that this unified schedule satisfies the conditions necessary to prevent subsequent updates from negating the improvements achieved at the root node?

  3. How does the proposed CPI method differ technically from An ε-Optimal Sequential Approach for Solving zs-POSGs (Escudie et al., 2026: https://arxiv.org/pdf/2602.24092v2), which also addresses the computational cost of minimax backups? Could you clarify the distinct contribution of your fixed-policy formulation and provide a direct comparison with sequential PBVI, using comparable pruning settings and the same exploitability evaluation procedure?

4 comments

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

1. Theorem 2 at line 323, the formula for the policy update contain an extra U, can you help to clarify what is the standard stochastic approximation conditions on and the approximation error between the discrete operator and the continuous dynamics Fi (see Definition 4)?

Stochastic Approximation conditions: The term UU follows the stochastic approximation formulation used in Benaïm at al's work (2005). It captures the perturbation affecting the update. The stochastic-approximation conditions stems from the same paper: Ui,k+1U_{i,k+1} is either a deterministic or random perturbations. One possible assumption on the perturbation satisfying the convergence is uniformly bounded in L2L^2 and αk=1k\alpha_k = \frac{1}{k} which are satisfied in our experiments (Remark 1.5 from Benaim et al. (2005)). We added the assumption in Theorem 2 (3 in the revised manuscript)

Relationship between discrete and continuous operator: We reformulated the dynamics driving the update (Definition 4) without loss of generality and moved it to the main body, so that it connects more directly to the rest of the paper, in particular to the LP. The underlying logic is unchanged: the update direction is a safe improvement direction produced by the LP. We also unified the continuous-time and discrete-time dynamics, which removes unnecessary complications from the proof and makes the link between the two explicit.

2. Lemmas 14 - 16: Step sizes are stage-dependent in the lemmas and common in Algorithm 1

First, an important point: the proofs in Section B (“Algorithm”) concern the continuous-time version of Algorithm 1, so the step sizes need not match those of the discrete algorithm. Section B shows that this continuous version converges to the equilibrium. For the associated discrete version (our algorithm), we rely on the results of Benaïm et al. (2005) and the continuous-time convergence. Since this is a critical point of the proof, we provide a thorough description of the process.

Lemma 13. Consider first an update of player ii in which only the policy at stage t=0t=0 changes. By definition, the overall pessimistic value of player ii cannot decrease, since player ii evaluates the game pessimistically from t=0t=0 onward, with best responses applied at every stage. Then, using the robustness and the uniform continuity of the focal value function (Theorem 1), we show that there always exists a direction along which an infinitesimal update improves the focal value function. It is sufficient since our objective is to establish that the focal value function improves along a smooth path in the policy space.

Lemma 14. This lemma extends the same argument inductively to subsequent stages.

Lemma 15. If both players improve their respective focal values while maintaining the guarantees established above, the dual gap necessarily decreases. Since the dual gap is non-negative over the policy space, this establishes convergence of the smooth trajectory in the policy space.

Remark. Benaim et al (2005) presents a similar reasoning in the analysis of fictitious play, where derivatives are used to establish the dual gap improvement along the continuous time version of this algorithm (Section 5.3. "Fictitious play in potential games"). However, the policy space considered here is more complex, which makes the corresponding proof substantially longer.

3. CPI vs "An ϵ\epsilon-Optimal Sequential Approach for Solving zs-POSGs"

Our method and the sequential approach are orthogonal. The sequential approach reduces the impact of the number of continuation policies that must be considered in each LP: by separating the decision rule from the continuation policy, it eases the computational burden of minimax backups. In our paper, however, each LP involves a single continuation policy, and hence a single continuation vector, which makes this principle unnecessary for CPI.

Therefore, the computational advantage of our formulation comes from reducing the number of points and, in turn, the number of continuation vectors. That said, the pruning and the exploitability computation are indeed the same in both versions, and both are already included in the algorithms.

Reviewer_GyouOpenReview ↗

The concerns are partly resolved

Thank you for your responses and revisions. While they partially address my concerns, I still have two remaining questions:

  1. Regarding Theorem 3, you invoke Remark 1.5 of Benaïm et al. (2005) to justify the assumptions on Ui,kU_{i,k} and the step-size schedule. However, Proposition 1.4 of Benaïm et al. (2005), which underlies that remark, assumes martingale-difference noise, including $ \mathbb E[U_{i,k+1}\mid\mathcal F_k]=0.$ Could you clarify whether the perturbation used in CPI satisfies this condition? If not, which alternative sufficient condition supports the convergence argument?

  2. Thank you for explaining the distinction between CPI and "An ε\varepsilon-Optimal Sequential Approach for Solving zs-POSGs" (Escudie et al., 2026). However, I could not find a citation to this work or the corresponding discussion in the revised manuscript. Could you incorporate both the citation and the technical distinction described in your response?

We thank the reviewer for pointing this out. Indeed, the condition we previously stated was too restrictive and our initial presentation was somewhat brief. As the perturbations used in practice were small. We have therefore revised Theorem 3 to explicitly state the general conditions required on the perturbations for the convergence result to hold (Proposition 1.3 from Benaim et al.).

In principle, the asymptotic conditions of Theorem 3 can be satisfied by setting ϵk=αk\epsilon_k=\alpha_k and progressively increasing the density of sampled best responses. In practice, however, our algorithm runs for fewer than 1,000 iterations. We therefore use a small fixed exploration parameter (ϵk=10−3\epsilon_k=10^{-3}) and a fixed set of approximately 20 alpha-vectors. The former prevents conditionals from being excluded from exploration, while the latter provides a compact approximation of the value function. Since the value function is uniformly continuous over the conditional space, sufficiently dense sampling can make the approximation error arbitrarily small. These fixed choices thus provide practical ε\varepsilon-accuracy, while the corresponding schedules can be adapted to satisfy the asymptotic convergence conditions.

For completeness, we have nevertheless added the appropriate asymptotic assumptions from Benaïm et al. to Theorem 3, as well as a discussion of the exploration and value-function approximation schedules in the appendix (Appendix B.1). This clarifies the distinction between the conditions required for an asymptotic convergence analysis and the practical choices made in our experiments.

Regarding the distinction between SeqPBVI and CPI, we have added explanations in Appendix A.7.

Thank you for answering my questions. I would consider this as practical limitation and hope that you can incorporate that into your revision. I keep my score.

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

This paper proposes the conservative policy iteration (CPI) for finite-horizon zero-sum partially observable stochastic games. They compare the proposed methods with standard methods in the domain, like PBVI and HSVI. The problem with these methods is that they grow exponentially with the horizon. The proposed method circumnavigates this issue by keeping one policy per player in the game. The proposed method does converge to Nash equilibrium. They use standard benchmarks which are used in the domain for problems like these. On these benchmarks, CPI matches the other commonly used techniques (PBVI, HSVI, etc.) at short horizons, and it does much better at longer ones.

Critical strengths

I think one of the key results is Theorem 1. They show that if a policy's value in the games under consideration is linear in the belief. This is useful, as this allows them to represent each player's current policy with a hyperplane. Other standard methods, like PBVI and HSVI, are not able to maintain a growing set of vectors. This is the reason why the proposed methods are able to scale to larger horizons.

Critical weaknesses

This is not a critical weakness. It's more of a limitation: The authors acknowledge that "the code requires further cleanup and validation before the experimental results can be presented as part of the main empirical evaluation." While the theoretical results do hold, it is highly recommended that the authors address this issue.

Questions for authors

I flag this issue as a critical weakness. If the issue regarding the code could be addressed and the code improved, then I would be happy to move my assessment from weak acceptance to clear acceptance.

Typos Line 83: "pertubations" Line 302: the algorithm "alternes"

1 comment

We thank the reviewer for their time and valuable feedback. We hope that our response below addresses the remaining concern.

“If the issue regarding the code could be addressed and the code improved, then I would be happy to move my assessment from weak acceptance to clear acceptance.”

Our code is mature for POSGs but has not yet been fully adapted to EFGs. Appendix C, “Extensive Form Game,” extends the theoretical framework of the main body from POSGs to EFGs. Sokota et al. identified problems with existing reductions, and our one-sided reduction generalizes to EFGs and resolves the issues they raised. Since EFGs are outside the scope of the paper, we do not consider this a fundamental limitation. On the contrary, the fact that our one-sided reduction extends to EFGs supports the theory introduced in the paper. We have also obtained encouraging preliminary results on Kuhn poker, which we will present in upcoming work.

We also wish to explain why the code is not publicly released at this stage. In the past, code shared during review was uploaded to AI tools without our consent, and we therefore prefer to wait until the review process is over. We will release the code, including the EFG adaptation if it is ready, upon acceptance.

Comments on the paper

1 comment

We thank the reviewers for their feedback, which we have incorporated into the revised version. The main changes are:

  1. Link between Theorem 3 and the proof. We clarified how the update in Theorem 3 relates to the continuous-time dynamics used in the proof, and we aligned the two. The algorithm is a moving average steered by the linear program (LP). We prove convergence of its continuous-time counterpart, obtained with an infinitesimal step size, and then use results from stochastic approximation to transfer this to the discrete-time algorithm of Theorem 3.
  2. Assumptions on the perturbation UU. We stated them more clearly.
  3. Restructuring. We moved material from the appendix to the main body, including the linear program.
  4. Experiments. We added more details about the experimental setup.

We believe these revisions improve the clarity and readability of the manuscript, and we thank the reviewers again for their helpful comments.

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

Related papers

Loading the map…

Discussion (0)

Sign in to comment.