PaperlayerView exact revision on arXiv

Source-linked AI summary

Conservative Policy Iteration For Zero-Sum POSGs

Erwan C. Escudie, Matthia Sabatelli, Jilles Steeve Dibangoye

arXiv:2610.36847v1cs.AIcs.GT

TL;DR

Point-based planning for zs-POSGs must approximate a central value across high-dimensional occupancy spaces, while policy-update methods do not provide the focused Bellman representation the paper seeks. CPI jointly and conservatively updates player-specific policies along occupancy trajectories using local policy improvements and persistent exploration. On finite-horizon benchmarks, it is competitive at small horizons and often improves the runtime–exploitability trade-off at larger horizons; scalability remains limited by computation and slow convergence.

  • Problem

    Point-based zs-POSG solvers approximate central values across large occupancy spaces, while existing approaches lack a player-specific value representation for focused local Bellman backups.

    Source: §1 · pp. 1–2, §2.1 · p. 3

  • Method

    CPI maintains a policy per player and uses fixed-policy continuation values for local Bellman improvements, conservatively updating both policies along occupancy trajectories with exploration.

    Source: §1 · p. 2, §4.2 · p. 6, §4.1 · p. 6

  • Results

    CPI is competitive at small horizons and often improves the runtime–exploitability trade-off at larger horizons compared with PBVI, HSVI, and CFR+.

    Source: §1 · p. 2, §6 · p. 9

  • Takeaways & Limitations

    The reported benchmarks show that policy iteration focused along occupancy trajectories can offer a competitive runtime–exploitability trade-off without approximating the full central value function.

    Source: §1 · p. 2, §6 · p. 9

    CPI requires local optimization for both players, and slow convergence, high sample complexity, and reliance on linear-programming subroutines may limit scalability at larger horizons.

    Source: §6 · p. 9

Abstract

from arXiv · show

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

1 INTRODUCTION

Occupancy-state reductions restore Bellman recursion for zs-POSGs, but point-based methods must approximate values across a large occupancy space. Conservative Policy Iteration (CPI) instead combines player-specific policy updates with local backups, and is competitive at small horizons while often improving the runtime–exploitability trade-off at larger ones.

1 INTRODUCTION

  • Occupancy-state reductions restore Bellman recursion for zs-POSGs by lifting the game to a fully observed occupancy stochastic game that preserves its value.The lifted state is a distribution over hidden states and histories, and its actions are decision rules.Source: §1 · p. 1
  • Existing point-based solvers approximate a central value over sampled occupancy states, creating a coverage problem across a large space.The value information needed for player-specific policy improvement is concentrated where the current policy may fail security, including under unilateral deviations and worst-case responses.Source: §1 · pp. 1–2
  • Policy-update methods produce executable policies, but the paper identifies no existing approach that combines them with a player-specific value representation for local Bellman backups.Central occupancy planning supplies Bellman equations but broad, non-executable states; focal planning is player-specific but set-valued; policy-space methods lack Bellman representations for focused backups.Source: §1 · p. 2
  • CPI maintains one policy per player and improves both along occupancy trajectories, using policy-induced values for local backups instead of a global central value function.Its empirical evaluation finds CPI competitive at small horizons and often better on runtime–exploitability trade-off at larger horizons than PBVI, HSVI, and CFR+.Source: §1 · p. 2

2 PRELIMINARIES

A finite-horizon zs-POSG has hidden states and imperfect information, so players act from private and public histories. A central occupancy state makes the continuation problem Markovian, but its size and decision space grow rapidly with the horizon.

2 PRELIMINARIES

  • A finite-horizon zs-POSG is a two-player zero-sum stochastic game with hidden states, where players act from private and public histories.The game is evaluated by expected cumulative payoff, with the second player's reward equal to the negative of the first player's.Source: §2 · p. 2

2.1 OCCUPANCY-STATE DYNAMIC PROGRAMMING

  • The central occupancy state is a distribution over the hidden state and histories, and it is Markovian for a central planner.Given this state and a policy profile, the next occupancy and one-step expected reward are defined, restoring Bellman recursion for the zero-sum value.Source: §2.1 · p. 3
  • Occupancy-based dynamic programming is computationally challenging because the occupancy representation grows exponentially with horizon and its subgame decision space quickly becomes intractable.Point-based methods are a natural approximation, but zs-POSG implementations provide limited guidance on where to sample.Source: §2.1 · p. 3
  • The central formulation produces the correct value equation and decision rules, but efficient planning seeks to explore relevant decision-rule regions without enumerating or sampling the entire occupancy space.The desired representation retains Bellman recursion while making relevant parts of the decision-rule space more efficient to explore.Source: §2.1 · p. 3

3 FOCAL BELIEF GAMES

Focal belief games condition the central occupancy representation on information relevant to one player, supporting fixed-policy evaluation and local policy improvement. Their value structure provides a compact way to characterize policy-induced values, despite continuous conditional-state spaces.

3 FOCAL BELIEF GAMES

  • Conditioning the central state on public history, the opponent’s private history, and the focal player’s policy prefix yields a player-specific representation.It separates fixed-policy evaluation against a best-responding opponent from policy improvement using the resulting pessimistic continuation value.Source: §3 · pp. 3–4

3.3 STRUCTURE OF THE FOCAL BELIEF VALUE

  • For a fixed policy, the focal-belief value is linear in the belief, while the optimal value function of the game is convex in belief space.The fixed-policy value can be characterized using a reduced representation, although the continuous conditional-state space remains a source of complexity.Source: Figure 1 · p. 4, §3.3 · p. 5

3.1 CONDITIONAL OCCUPANCY STATES

  • A conditional occupancy state is a distribution over the hidden state and focal player’s private history, used to evaluate and improve a fixed focal policy.For fixed-policy evaluation, pure opponent actions suffice because the objective is affine in the opponent’s mixed action.Source: §3.1 · p. 4

3.2 THE FOCAL BELIEF GAME

  • A focal belief is a distribution over conditional occupancy states and defines a fully observed planning game for the focal player.This is a one-sided representation, not a strict lossless reduction; fixed-policy values agree across the representations, while the opponent is modeled in conditional coordinates as a virtual player.Source: §3.2 · pp. 4–5

4 CONSERVATIVE POLICY ITERATION

CPI improves each player’s policy locally along occupancy trajectories generated by conservative updates and persistent exploration. Its convergence result is conditional on stochastic-approximation and operator-approximation assumptions.

4 CONSERVATIVE POLICY ITERATION

  • CPI maintains one behavioural policy per player and performs local policy improvement along occupancy trajectories without constructing the optimal focal-belief value or covering the full central occupancy space.Each update uses the fixed-policy value as a continuation term and averages the improved decision rule into the current policy.Source: §4 · p. 5

4.1 LOCAL POLICY IMPROVEMENT

  • At a focal belief, the local Bellman backup solves a zero-sum continuation game for a max–min focal decision rule and an opponent’s minimizing rule.The opponent can use deterministic minimizing rules because the local payoff is affine in its mixed rule.Source: §4.1 · p. 6

4.2 CONSERVATIVE POLICY ITERATION

  • At each reached occupancy, CPI forms each player’s focal belief, applies a local LP backup, averages the improved rules, and adds GLIE exploration.Exploration keeps all belief components represented; without it, zero action probabilities can make the induced belief degenerate and remove distribution support.Source: §4.2 · p. 6
  • CPI converges almost surely to the set of Nash equilibria under standard stochastic-approximation conditions and controlled approximation error between the discrete and continuous update operators.The theorem’s result is unaffected by GLIE noise when it satisfies the required conditions.Source: §4.2 · p. 7

5 EMPIRICAL EVALUATION

On standard finite-horizon zero-sum POSG benchmarks, CPI is competitive with PBVI at small horizons and improves the runtime–exploitability trade-off at larger horizons, though PBVI performs better on Adversarial Tiger and Recycling. CFR+ has cheaper iterations, while CPI makes fewer, costlier updates.

5 EMPIRICAL EVALUATION

  • The evaluation compares CPI, PBVI, HSVI, and CFR+ on Adversarial Tiger, Recycling, Mabc, and Matching Pennies at shared finite horizons.Reported measures include runtime, value, and exploitability; the CFR+ baseline adapts extensive-form CFR+ to the occupancy-state reduction.Source: §5 · p. 7

CPI vs PBVI

  • CPI is competitive with PBVI at small horizons and improves the runtime–exploitability trade-off at larger horizons, although PBVI performs better on Adversarial Tiger and Recycling.PBVI's performance is particularly strong on those two games; CPI's computation time increases proportionally with horizon, while PBVI's may vary with sampling.Source: §5 · p. 7

CPI vs CFR

  • CFR iterations are cheaper than CPI updates, but CFR exploitability often changes non-monotonically while CPI's reported profiles are smoother.CFR exploitability estimation requires an additional procedure whose cost increases with horizon; CPI obtains estimates from quantities maintained during policy improvement.Source: §5 · p. 7

PENNIES RECYCLING

At horizon 5, Figure 2 compares value and exploitability trajectories for CFR+, PBVI, and CPI. The reported trade-offs distinguish CPI's costly updates from CFR+'s inexpensive iterations and repeated exploitability evaluations.

PENNIES RECYCLING

  • Figure 2 compares value and exploitability evolution for CFR+, PBVI, and CPI across games at fixed horizon ℓ=5.The caption identifies convergence behaviour and solution quality as the comparison focus but does not state specific outcomes.Source: Figure 2 · p. 8
  • Table 1 reports runtime, value, and exploitability for each game, horizon, and algorithm, including the computational cost of exploitability evaluation.It marks the lowest exploitability/value per benchmark; OOT denotes failure to reach the target exploitability within the time limit, and OOM denotes running out of memory.Source: Table 1 · p. 8
  • CFR+ uses inexpensive iterations but typically needs more iterations and repeated exploitability evaluations to reach quality comparable to CPI, often producing higher overall runtime at larger horizons.CPI instead makes fewer but more expensive updates, with a different trade-off among update cost, exploitability estimation, and empirical stability.Source: PENNIES RECYCLING · p. 9

6 CONCLUSION

CPI is an approximate policy-iteration method for finite-horizon zs-POSGs that updates both players' policies along occupancy trajectories using fixed-policy continuation values. It is competitive on standard benchmarks, with runtime–exploitability trade-off improvements in several instances and horizons, while optimization and scalability limitations remain.

6 CONCLUSION

  • CPI improves the runtime–exploitability trade-off over PBVI, HSVI, and CFR+ in several benchmark instances and horizons.The method combines local policy improvements, conservative updates, and persistent exploration rather than approximating a global central value function.Source: §6 · p. 9
  • The algorithm maintains one policy per player and updates both along occupancy trajectories induced by conservative policy updates, using fixed-policy continuation values for its local improvements.It combines elements of point-based value iteration and policy search.Source: §6 · p. 9
  • Local optimization for both players, potentially slow convergence, high sample complexity, and reliance on linear-programming subroutines may limit scalability at larger horizons.Proposed future directions include iterative approximations, improved exploration and scheduling, and neural continuation-value approximations.Source: §6 · p. 9

A PROOFS

  • Finite-horizon behavioural-policy spaces are compact and payoff maps continuous, so optimization over these spaces attains its extrema.The proof uses finite products of finite-dimensional simplexes, multilinearity of finite-horizon payoffs, and the extreme-value theorem.Source: A PROOFS · p. 13

A.3 CONTINUATION VALUES

  • The optimal focal-belief value function satisfies the focal-belief Bellman equation and equals the continuation value.The stated proof establishes the equality by backward induction from the terminal value.Source: §A.3 · pp. 15–16

A.5 PROOF OF THEOREM 1

  • The optimal focal-belief value function is concave in the belief, as shown by expressing it as a maximum over linear functionals.The displayed convex-combination inequality supports the concavity claim.Source: §A.5 · p. 17

A.6 LOCAL BELLMAN BACKUPS

  • The local-backup theorem is conditional on finite coverage, Bellman closure, globally valid inserted vectors, infinite exact updates, and covered-backup consistency.Source: §A.6 · p. 17

A.6.1 LOCAL POINT-BASED BACKUP

  • The local backup preserves a max–min structure and places the inner minimization over α after expectation over next-stage variables to yield a linear program.Source: §A.6.1 · p. 18

A.7 COMPARATIVE ANALYSIS OF BACKUP COMPLEXITY

The comparative analysis contrasts LP descriptions by how their constraints depend on opponent decision rules and cached value representations. The proposed backup avoids indexing constraints by opponent rules and remains polynomial-size in the explicit representation.

A.7 COMPARATIVE ANALYSIS OF BACKUP COMPLEXITY

  • The OMG greedy-update LP has exponentially many constraints in the opponent's private-history space, while the proposed cached-envelope LP constrains against finitely many vectors rather than opponent decision rules.The proposed LP has a polynomial-size description in the explicit parameters.Source: §A.7 · p. 18, Table 2 · p. 19
  • Both the cached-envelope greedy LP and the proposed backup scale polynomially in the same explicit representation objects, but the proposed formulation reduces variables and constraints by a factor of |Γ1|.|Γ1| counts the maintained piecewise-linear concave functions; |Λ| counts the associated piecewise-linear vectors for each function.Source: §A.7 · p. 19
  • Reducing |Γ1| matters more at longer horizons because PBVI's set of candidate functions grows with sampled points needed to cover the expanding continuous state space.Source: §A.7 · p. 19

B ALGORITHM

This section presents the algorithm’s structured policy-iteration updates and reports their almost-sure convergence to Nash equilibria. It also develops a one-sided extensive-form reduction that preserves a focal player’s security problem and supports unilateral subgame-perfect recursion for sequential games.

B ALGORITHM

  • The method replaces exponentially growing sampled-point value iteration with structured policy iteration, whose simultaneous stage updates can alter later beliefs through opponents’ past policies.Each update direction is defined locally while depending on the player’s complete policy and the opponent’s earlier policies.Source: B ALGORITHM · pp. 19–20
  • Although the Q-value is not differentiable everywhere, the local improvement mechanism handles such points, while deviation-aware values help protect against numerical instability.The passage says the discretization does not encounter pathological cases in practice.Source: B ALGORITHM · p. 20
  • For finite horizons, sufficiently small positive step sizes can preserve strict pessimistic-value improvements across stage updates, yielding a trajectory with decreasing dual gap at every non-degenerate iteration.The continuation-stage steps can be reduced so they do not cancel an earlier-stage improvement.Source: B ALGORITHM · pp. 22–23
  • The continuous flow’s dual gap decreases strictly outside Nash equilibria, and the flow converges to the Nash-equilibrium set.Along the flow, the dual gap is non-increasing and converges to zero.Source: B ALGORITHM · pp. 19, 24
  • Under Robbins–Monro conditions and standard noise assumptions, the discrete iterates’ limit set is almost surely contained in Nash equilibria, via Benaïm et al. (2005).The discrete algorithm is treated as a stochastic approximation of the continuous dynamics.Source: B ALGORITHM · p. 25
  • The algorithm converges almost surely to the set of Nash equilibria.Source: B ALGORITHM · p. 25

C.1 A HIERARCHY OF PLANNERS

  • Escudie et al. (2025) distinguish planners by their information and treatment of future decisions; the Backward Dependence Problem shows how public-policy reductions can miss dependencies on earlier decisions.Source: §C.1 · pp. 25–26

C.2 EQUILIBRIUM AND DYNAMIC PROGRAMMING

  • Dynamic programming in simultaneous-move POSGs yields a Subgame Perfect Nash Equilibrium, but sequential POSGs and extensive-form games may require only Nash equilibria, not subgame-perfect ones.In Kuhn Poker, directly applying the recursion selects a deterministic final-stage decision rule and misses its dependence on earlier deviations.Source: §C.2 · p. 26

C.3 ONE-SIDED EXTENSIVE-FORM GAMES

  • The one-sided EFG reduction preserves every joint-policy value, the focal player’s maximin value, and its optimal policies, but does not preserve the opponent’s information structure or all equilibrium strategies.The result is lossless for the focal player.Source: §C.3 · pp. 27–28
  • The one-sided EFG admits a unilateral Subgame Perfect Nash Equilibrium, and its Bellman recursion computes the equilibrium value and an equilibrium strategy for the focal player.The opponent observes the focal player’s complete policy prefix, making the sequential maximin construction correspond to this equilibrium.Source: §C.3 · pp. 28, 30
  • The one-sided reduction addresses this sequential-game issue by making players’ information explicit and defining proper subgames; standard simultaneous-move POSG dynamic programming already provides the appropriate solution concept.The reduction is unnecessary for most games considered here, which are simultaneous-move POSGs.Source: §C.3 · pp. 30–31

C.4 EXPERIMENTS

The extensive-form extension adapts local policy improvement to account for earlier decisions and evaluates deviations using the player’s intended information structure. The baseline discussion connects POSG regret updates to occupancy-space regret matching and describes the compared methods’ scope and computational constraints.

C.4 EXPERIMENTS

  • The extensive-form extension modifies local policy improvement to retain information about past decisions when computing deviations.The extension was evaluated on Kuhn Poker, but its implementation remains a proof of concept pending cleanup and validation; systematic experiments are deferred.Source: §C.4 · p. 31
  • Including public histories in the belief support restricts deviations to the player’s information, avoiding a separate deviation for every public history.The unrestricted optimization could produce an overly pessimistic evaluation that does not match the intended player model.Source: §C.4 · p. 31

D.1 BASELINES

  • PBVI’s adversarial backups require linear programs, and rapid α-vector growth makes its Bellman operator quickly intractable despite point-based approximation.In the one-sided surrogate, PBVI optimizes one player against sampled opponent behaviors, relying on relevant responses being near those samples.Source: §D.1 · p. 31
  • Table 3 maps EFG notions to POSG counterparts, linking an EFG history to a state-history pair because POSG rewards are state-based.The table is presented as a bridge for transferring extensive-form techniques such as CFR to POSGs.Source: Table 3 · p. 32, §D.1 · p. 32
  • Table 4 reports runtime, value, and exploitability by game, horizon, and algorithm, marking the lowest exploitability per benchmark.OOT indicates the target exploitability was not reached within the time limit; OOM indicates memory exhaustion.Source: Table 4 · p. 33
  • Regret minimization operates directly on occupancy-state regret functions, with policy updates corresponding to regret matching under occupancy-induced weights.This avoids explicitly enumerating histories; the POSG regret is conditioned on the hidden state and history because rewards depend on the hidden state.Source: §D.1 · pp. 32–33

D.2 IMPLEMENTATION DETAILS

The reported results were run on a CPU, and Table 5 presents a snapshot of results without pruning. The table reports runtime, value, and exploitability across games, horizons, and algorithms.

D.2 IMPLEMENTATION DETAILS

  • The results presented in the paper were run on an AMD Ryzen 7 PRO CPU.Source: §D.2 · p. 33
  • Table 5 reports results without a pruning mechanism for each game, horizon, and algorithm.It reports time, value, and exploitability associated with the computed ε-Nash equilibrium.Source: Table 5 · p. 34
  • Table 5 marks the lowest exploitability per benchmark; OOT denotes failure to reach the target within the time limit, and OOM denotes memory exhaustion.Source: Table 5 · p. 34
Loading 2610.36847v1…