Conservative Policy Iteration For Zero-Sum POSGs

Erwan C. Escudie; Matthia Sabatelli; Jilles Steeve Dibangoye

cs.AIOct 27, 2026

Conservative Policy Iteration For Zero-Sum POSGs

Authors: Erwan C. Escudie, Matthia Sabatelli, Jilles Steeve Dibangoye

Organizations: University of Groningen

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+.

Figures & tables

Panel of Figure 1 — Figure 1: The optimal value function of the game $\mathcal{M}^{i}$ is convex in the belief space. While value-iteration methods such as PBVI sample this space and operate on a set of vectors to represent $\underline{v}_{i,t}$ , our method works with a single vector $\underline{v}_{i,t}^{\pi^{i}_{t:T}}$ at a time, reducing the complexity of the associated algorithms.

Panel of Figure 2 — Figure 2: Evolution of value and exploitability across different games under a fixed horizon $\ell=5$ . The results compare three methods: CFR+ , PBVI , and CPI , highlighting their respective performance profiles in terms of convergence behaviour and solution quality across the considered benchmarks.

		CPI (Ours)			PBVI			HSVI			CFR+
Problem	$T$	t	val.	$\epsilon$	t	val.	$\epsilon$	t	val.	$\epsilon$	t	val.	$\epsilon$
	2	0.3	0.078		0.2	0.078		0.4	0.078		0.3	0.078
	3	11	0.097		24	0.096		70	0.097		12	0.095
	4	23	0.11		65	0.11	0.01	oot	oot	oot	49	0.11	0.01
	5	29	0.12		31	0.12		oot	oot	oot	82	0.12	0.01
	7	97	0.14	0.01	190	0.14	0.005	oot	oot	oot	292	0.14	0.02

Table 1: Snapshot of the empirical results, including the computational cost of exploitability evaluation. For each game, horizon and algorithm, we report time, value and exploitability

\epsilon

associated with the computed

\epsilon

-Nash equilibrium. OOT occurs when the target exploitability threshold cannot be reached within the prescribed time limit, while oom means that the algorithms ran out of memory. magenta = lowest exploitability/value per benchmark

Appendix figures & tables6 assets

Supplementary material from the paper’s appendix.

Appendix

Update step	# variables	# constraints
Ours: LP	$\|{H}^{1}_{t}\|\|{A}^{1}_{t}\|+\|{H}^{2}_{t}\|\|{A}^{2}_{t}\|\|{Z}^{2}_{t}\|+\|{H}^{2}_{t}\|$	$O(\|{H}^{2}_{t}\|\|{A}^{2}_{t}\|\|{Z}^{2}_{t}\|\|\Lambda\|)$
( Delage et al., 2023 )	(rule variables $+$ epigraph)	Exponential: $O\!\bigl(\|{A}^{2}_{t}\|^{\|{H}^{2}_{t}\|}\bigr)$
( Escudie et al., 2025 )	$\|{H}^{1}_{t}\|\|{A}^{1}_{t}\|\|\Gamma_{1}\|+\|{H}^{2}_{t}\|\|{A}^{2}_{t}\|\|{Z}^{2}_{t}\|+\|{H}^{2}_{t}\|$	$O\!\bigl(\|\Gamma_{1}\|\cdot\|\Gamma^{*}_{2}\|\cdot\|{H}^{2}_{t}\|\cdot\|{A}^{2}_{t}\|\cdot\|{Z}^{2}_{t}\|\bigr)$

Appendix

Table 2: LP complexity comparison (input-size view). The OMG greedy-update LP has constraints indexed by opponent decision rules, yielding an exponential dependence on

|{H}^{2}_{t}|

( Delage et al., 2023 ) . Both the cached-envelope greedy LP ( Escudie et al., 2025 ) and our backup scale polynomially in the same explicit representation objects, but expose different optimization structures. In our formulation, both the number of variables and constraints are reduced by a factor of

|\Gamma_{1}|

. Here,

|\Gamma_{1}|

denotes the number of piecewise-linear concave functions maintained, while

|\Lambda|

is the number of piecewise-linear vectors associated with each element of

\Gamma_{1}

Panel of Figure 3 — Figure 3: Example of a situation at $T=2$ . The background represents the gradient of the dual gap at $t=0$ . The black arrows represent updates of the policy where only ${\pi}^{i}_{0}$ is changing. At $t=0$ , since ${i}$ has an optimal view of the pessimistic value function, the move strictly improves the global dual gap. The dashed arrows represent updates at $t=1$ ; since the update is also influenced by ${-i}$ past, nothing guarantees that the update will follow the global dual gap $d_{0}$ gradient direction. Here, we present an extreme case where the update at $t=1$ almost cancels the one at $t=0$ . On the left , we do not adapt the step sizes, on the right , we apply the proof such that destructive updates are avoided and we are sure the updates go to the right direction.

Panel of Figure 4 — Figure 4: $\mathcal{T}_{\mathcal{G}\rightarrow\mathcal{G}^{\prime}}$ denotes the reduction from game $\mathcal{G}$ to game $\mathcal{G}^{\prime}$ . The reduction $\mathcal{T}_{POSG\rightarrow EFG}$ is almost transparent: it simply reformulates the POSG as an extensive-form game (EFG). However, unlike $\mathcal{T}_{POSG\rightarrow SG}$ , this reduction does not induce an equilibrium concept that can be characterized inductively in the reduced game. The composition $\mathcal{T}_{POSG\rightarrow EFG}\circ\mathcal{T}_{EFG\rightarrow OEFG}$ corresponds to the focal-planner reduction introduced in Escudie et al. (2025) .

Name in EFG	Symbol	Name in POSG	Symbol
History	$h$	State and Joint history	$(s_{t},h_{t})$
i’s information set	$I$	i’s private history	$h_{i}$
Strategy profile	$\sigma$	Joint policy	$\pi$
i’s private strategy	$\sigma_{i}$	i’s private policy	$\pi_{i}$
Players’ contribution except i	$\pi^{\sigma}_{i}(I)$	Players’ contribution except i	$\Pr(h_{i}\mid\pi,b_{0})$
Players’ contribution except i	$\pi^{\sigma}_{i}(h)$	Counterfactual state	$c_{i}(s,h_{-i})$

Appendix

Table 3: Translation from EFG to POSG. For more information, we refer the reader to ( Kovařík et al., 2022 ) . We connect the history

h

in EFG to the pair

(s,h)

in POSG since the reward is not associated to the history but to the state in POSG. The quantity

v^{\pi}_{\mathcal{M}}(s,h)

is formally defined in ( Cunha et al., 2023 ) , we refer the reader for more information. It is simply the expected cumulated value a player can get at this pair.

		CPI (Ours)			PBVI			HSVI			CFR+
Problem	$T$	t	val.	$\epsilon$	t	val.	$\epsilon$	t	val.	$\epsilon$	t	val.	$\epsilon$
	2	0.3	0.078		0.2	0.078		0.4	0.078		0.3	0.078
	3	11	0.097		24	0.096		70	0.097		7	0.095
	4	23	0.11		65	0.11	0.01	oot	oot	oot	25	0.11	0.01
	5	29	0.12		31	0.12		oot	oot	oot	69	0.12	0.01
	7	97	0.14	0.01	190	0.14	0.0	oot	oot	oot	92	0.14	0.02

Appendix

Table 4: Snapshot of empirical results. For each game, horizon and algorithm, we report time, value and exploitability

\epsilon

associated with the computed

\epsilon

-

’ means the time budget for computing the exploitability has been exceeded.

		CPI (Ours)			PBVI			HSVI			CFR+
Problem	$T$	t	val.	$\epsilon$	t	v	$\epsilon$	t	val.	$\epsilon$	t	val.	$\epsilon$
	2	0.3	0.078		0.2	0.077		0.3	0.078		0.3	0.078	0.003
	3	5	0.097		19	0.097		70	0.097		12	0.096	0.002
	4	38	0.11	0.001	50	0.1	0.001	oot	oot	oot	73	0.11	0.003
Mabc	5	2176	0.12	0.01	1365	0.12	0.013	oot	oot	oot	1614	0.12	0.005
	2	0.01	0.4		0.13	0.38		0.1	0.4		0.01	0.4

Appendix

Table 5: A snapshot of empirical results with no pruning mechanism applied (see Escudie et al. (2025) , Dibangoye et al. (2016b) ). For each game, horizon and algorithm, we report time, value and exploitability

\epsilon

associated with the computed

\epsilon

-

’ means the time budget for computing the exploitability has been exceeded.

Partially Observable Stochastic Games

See all 15 papers

Global Policy-Space Response Oracles for Two-Player Zero-Sum Games
May 27, 2026Junyu Zhang, Feihong Yang, Jian Wang +2Nash Equilibrium Game Theory
Department of Electronic Engineering, Tsinghua University, Beijing, China · Qiyuan Lab, Beijing, China
$Q$ Can Play That Game: Online Fitted $Q$ -Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation
Oct 2, 2026Kushagra Gupta, Jingqi Li, Cade Armstrong +4Zero-Sum Games Game-Theoretic RL
The University of Texas at Austin · The University of California, Berkeley · Massachusetts Institute of Technology (MIT) Lincoln Labs
Risk-seeking conservative policy iteration with agent-state based policies for Dec-POMDPs with guaranteed convergence
Apr 10, 2026Amit Sinha, Matthieu Geist, Aditya MahajanPartially Observable Markov Decision Processes Policy Iteration
Department of Electrical and Computer Engineering, McGill University, Montreal, Quebec · Earth Species Project

May 27, 2026J/K move · Enter open · S save

Global Policy-Space Response Oracles for Two-Player Zero-Sum Games

Junyu Zhang, Feihong Yang, Jian Wang, Chao Wang+1

Department of Electronic Engineering, Tsinghua University, Beijing, China · Qiyuan Lab, Beijing, China

Nash Equilibrium Game Theory Zero-Sum Games Multi-Agent Reinforcement Learning Nash Equilibrium Computation

Open paper AskPDF arXiv

The Policy-Space Response Oracles (PSRO) framework scales equilibrium computation to large zero-sum games by iteratively expanding a restricted strategy set using deep reinforcement learning (DRL). A central challenge is to construct, under limited computational budgets, a small strategy population whose induced game well approximates the full game. Existing PSRO variants typically expand the population using best responses to meta-strategies computed from restricted-game payoffs, which can lead to inefficient expansions that provide limited global improvement. We propose to guide population expansion by directly evaluating the post-expansion population quality. Specifically, we adopt Population Exploitability (PE) to measure how well a restricted strategy set represents the full game, and introduce a two-phase exploration--selection framework that explicitly minimizes PE during expansion. We instantiate this framework as Global PSRO, a practical DRL-based algorithm that efficiently generates candidate responses and estimates PE via parameter-sharing conditional neural networks. Experiments across multiple two-player zero-sum games show that Global PSRO achieves lower exploitability and approximates Nash equilibria with significantly fewer policy iterations than prior PSRO methods.

Abstract

Partially Observable Stochastic Games

Explore similar work

Global Policy-Space Response Oracles for Two-Player Zero-Sum Games

QQQ Can Play That Game: Online Fitted QQQ-Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation

Risk-seeking conservative policy iteration with agent-state based policies for Dec-POMDPs with guaranteed convergence

$Q$ Can Play That Game: Online Fitted $Q$ -Iteration for Continuous-Action Zero-Sum Markov Games with Convex-Concave Function Approximation