A Scalable Solver for 2p0s Differential Games with One-Sided Payoff Information and Continuous Actions, States, and Time

Mukesh Ghimire, Lei Zhang, Zhe Xu, Yi RenSubmission to ICML 2025 · Rejected

TL;DR

Solving continuous-time, continuous-action imperfect-information games has long been bottlenecked by the need to discretize actions, which causes exponential computational blowups. This paper reveals that in two-player zero-sum (2p0s) differential games with one-sided payoff uncertainty, optimal strategies need only mix over a tiny, finite set of atomic actions proportional to the number of secret types, independent of the action space dimension. Leveraging this property alongside a temporal multigrid acceleration scheme, the authors present CAMS, a solver that scales to multi-stage, continuous differential games previously intractable for state-of-the-art algorithms.

What Problem Does This Paper Address?

In real-world competitive scenarios—such as missile interception or robotic defense—the environment is governed by continuous physical dynamics (differential games), continuous control inputs, and asymmetric information (e.g., the attacker knows their target among $I$ possibilities, while the defender only holds a prior belief).

Existing game-theoretic solvers (e.g., CFR+, DeepCFR, MMD) were built for discrete extensive-form games. Applying them to continuous differential games requires fine action-state-time discretization, which triggers severe combinatorial explosions. Meanwhile, continuous-action game solvers typically require restrictive assumptions like monotonicity or pseudoconcavity. The authors address how to compute approximate Nash equilibria in continuous-action, continuous-state, continuous-time 2p0s games with one-sided information without relying on fine action discretization.

Methods

The authors introduce CAMS (Continuous Action Mixed Strategy solver) combined with a temporal Multigrid acceleration framework:

  1. Primal-Dual Dynamic Programming (DP):
  2. The informed player's (P1) strategy is formulated as a discrete-time Bellman backup over public beliefs $p \in \Delta(I)$.
  3. Because P2's strategy depends on the subgradient of the value with respect to belief ($\partial_p V$), the authors use the Fenchel conjugate dual game where P2 minimizes worst-case risk across types.
  4. Atomic Splitting Reformulation: Under the Isaacs' condition (which guarantees that the complete-information game has a pure-strategy saddle point, common in control-affine systems), value convexification over the simplex $\Delta(I)$ requires at most $I$ extreme points. Consequently:

  5. P1’s optimal mixed strategy is $I$-atomic (mixes over at most $I$ pure actions).

  6. P2’s optimal dual strategy is $(I+1)$-atomic.
  7. Non-convex, non-concave minimax subproblems at each collocation point are solved via Doubly Smoothed Gradient Descent Ascent (DS-GDA).
  8. Neural Value Function Approximation: Input Convex Neural Networks (ICNNs) are trained backward in time to approximate the value functions across continuous states and beliefs.

  9. Full Approximation Scheme (FAS) Multigrid: Standard backward value iteration incurs error propagation that grows exponentially with the number of time steps $K$. The authors adapt FAS multigrid methods to time discretization: coarse-grid solves correct low-frequency errors cheaply, drastically reducing fine-grid sweeps.

Datasets

The paper evaluates the methods on standard and modified differential game benchmarks:

  • Hexner’s Game: A canonical linear-quadratic differential pursuit-evasion game with an analytical Nash equilibrium. P1 knows their hidden target position while P2 must infer it.
  • 1-Stage Normal-Form Hexner’s Game
  • 4-Stage and 10-Stage Hexner’s Games (evaluated in both unconstrained and state-constrained versions where P1 receives a $+\infty$ penalty for colliding within distance $r = 0.05$ of P2)
  • 16-Stage Hexner’s Game
  • 3D Hexner’s Game: High-dimensional extension featuring a 6D joint action space, 12D state space, and 13D value space.
  • Zero-Sum Beer-Quiche Game: A turn-based signaling game benchmark presented in the appendix.

Key Insights and Ideas

  • Action Complexity Decoupled from Action Space Size: Rather than learning a continuous probability density or finely binning controls, P1 only ever needs to identify at most $I$ discrete actions to achieve the lower convex envelope of the value function. Game complexity scales with the number of hidden types ($I^2$), completely bypassing the dimensionality or discretization of continuous controls.
  • Strategic Information Delay: CAMS analytically and empirically reconstructs the classic "target concealing" property: P1 intentionally moves toward the expected target $\mathbb{E}_{p_0}[z_\theta]$ to withhold information until a critical time threshold $t_r$, after which they break toward the true target.
  • Multigrid for Dynamic Programming: Treating backward induction as a nonlinear system of equations allows coarse time grids to smooth out global errors, bounding the error propagation across long time horizons.

Key Results

  • Action Invariance (1-Stage): While CFR+, MMD, and CFR-BR wall-clock times scaled steeply as discrete action lattice sizes increased from $|U|=16$ to $144$, CAMS’ runtime and iteration counts remained strictly constant.
  • Solution Quality (4-Stage): With similar or lower compute (~17 hours on an A100 GPU vs. 24h for JPSPG and 29–34h for DeepCFR), CAMS attained drastically lower expected action error across time steps ($\bar{\varepsilon}_t \approx 0$ vs. errors of $20\text{–}40$ for DeepCFR and JPSPG).
  • Scale and Constraints (10-Stage): Successfully resolved games with an equivalent game-tree complexity of $10^{80}$ (under a $100\times 100$ action grid). On unconstrained 10-stage Hexner's, CAMS learned an average reveal time of $t_r = 0.60 \pm 0.06\,\text{s}$ (close to the analytical ground truth of $0.5\,\text{s}$).
  • Multigrid Speedups:
  • 4-stage game: runtime dropped from 9.3 hrs to 2.32 hrs (4.0× speedup).
  • 10-stage game: runtime dropped from 27.6 hrs to 10.9 hrs (2.5× speedup).
  • 16-stage game (4-level multigrid): runtime dropped from 46.21 hrs to 17.83 hrs (2.6× speedup).

Limitations and Future Work

  • One-Sided Payoff Information Only: The theoretical splitting guarantees rely on asymmetric one-sided information; games where both players possess private information remain unaddressed.
  • Isaacs' Condition Reliance: The atomic nature of the equilibrium strategies requires Isaacs' condition to hold (guaranteeing pure equilibria in complete-information subgames). While typical for control-affine dynamics, this restricts applicability to general non-affine systems.
  • Dual Game Error: Approximating P2's dual value is harder because the dual variable space is one dimension higher than the primal belief simplex, resulting in higher policy error for P2 than P1.
  • Auto-Differentiation Bottlenecks: Mitigating value approximation error accumulation entirely via exact linear value approximators requires differentiating through linear programs at every descent-ascent step, which remains computationally prohibitive in PyTorch/JAX.

Summary updated

Abstract

Existing solvers for imperfect-information extensive-form games (IIEFGs) often struggle with scalability in terms of action and state space sizes and the number of time steps. However, many real-world games involve continuous action and state spaces and occur in continuous time, making them differential in nature. This paper addresses the scalability challenges for a representative class of two-player zero-sum (2p0s) differential games where the informed player knows the game type (payoff) while the uninformed one only has a prior belief over the set of possible types. Such games encompass a wide range of attack-defense scenarios, where the defender adapts based on their belief about the attacker's target. We make the following contributions: (1) We show that under the Isaacs' condition, the complexity of computing the Nash equilibrium for these games is not related to the action space size; and (2) we propose a multigrid approach to effectively reduce the cost of these games when many time steps are involved. Code for this work is available at [anonymous repo](https://anonymous.4open.science/r/icml-25).
BibTeX
@misc{ghimire2025scalable,
  author = {Mukesh Ghimire and Lei Zhang and Zhe Xu and Yi Ren},
  title = {{A Scalable Solver for 2p0s Differential Games with One-Sided Payoff Information and Continuous Actions, States, and Time}},
  year = {2025},
  eprint = {2502.00560},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2502.00560},
}

Loading related content...

Figure