- 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.
-
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.
-
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.
-
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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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
- Clarify the value-function structure: linear vs piecewise-linear concave vs convex, and fixed-policy vs optimal value.
- Provide the complete Algorithm 1, including Recurse, LP, Λ updates, and GLIE schedule.
- 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 |Λ|.
- Justify the stochastic-approximation conditions and the approximation error between F̃_i and F_i.
- Provide full empirical details: seeds, hyperparameters, time/memory limits, code, and baseline implementations.
- Clarify the algorithmic difference from Escudie et al. (2025) and Delage et al. (2023).
- Describe the pruning procedure and report all main results with and without it.
- Confirm that the same exact exploitability evaluator is used for CPI, CFR+, PBVI and HSVI.
- Is Λ a subset of the full vector set? If so, how does the resulting optimism affect the guarantees?
- 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?
- 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?
- How does CPI relate to Kakade & Langford (2002)’s conservative policy iteration, which the paper cites in Section 4.2 of page 6?
- 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
9. Is a subset of the full vector set? If so, how does the resulting optimism affect the guarantees?
An object compactly represents a single vector of Figure 1. Each vector in gives the value of player 's policy against one best response at a history . A finite set of vectors thus represents a policy over the entire occupancy space, whereas only 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 approximates a vector defined over (Figure 1), the operator may differ from the one used in the proof. This error can be absorbed into the noise term and, by uniform continuity, is bounded, so it satisfies the corresponding condition of Theorem~3. It decreases as grows and vanishes when 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 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.
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 (Theorem 1) while it is piecewise linear concave if we consider it over occupancy space Ot (Proposition 1).
Player i's optimal value function is convex over Bti.
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 ∣Λ∣.
∣Λ∣ 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 is stored over Ot rather than Bti (Proposition 1). Over this space, it is represented by a \underline{finite} set of vectors Λ, 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−i can be reused at any other history hˉt−i. A set Λ thus represents up to ∣Λ∣∣Ht−i∣ best-response policies, exponentially more than the number of stored vectors.
In our experiments, each Λ contained about 20 vectors, depending on the benchmark and the horizon. With only 4 histories, this already represents up to 204=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+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) rather than Ot. 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 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 i's policy πi, which induces a sequence of occupancy states (beliefs). Player −i then faces a POMDP with state space S×Hi, actions A−i, and observations Z−i. Its lossless reduction to a belief-MDP yields beliefs b∈Δ(S×Hi∣H−i,π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: Λ contains precisely the vectors computed by PBVI on the belief-MDP induced by πi. Thus, this computation is already part of PBVI (zsPOSG) and CPI, but must be performed separately for CFR.