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:
- Primal-Dual Dynamic Programming (DP):
- The informed player's (P1) strategy is formulated as a discrete-time Bellman backup over public beliefs $p \in \Delta(I)$.
- 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.
-
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:
-
P1’s optimal mixed strategy is $I$-atomic (mixes over at most $I$ pure actions).
- P2’s optimal dual strategy is $(I+1)$-atomic.
- Non-convex, non-concave minimax subproblems at each collocation point are solved via Doubly Smoothed Gradient Descent Ascent (DS-GDA).
-
Neural Value Function Approximation: Input Convex Neural Networks (ICNNs) are trained backward in time to approximate the value functions across continuous states and beliefs.
-
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