Signature Belief States for Games with Unsynchronized Clocks

In many multi-agent problems, each agent has to work out what its opponents are like and intend from its own private and partial stream of observations. Examples include cars at an intersection exchanging delayed radio messages, or a pursuer that sees an evader only at irregular moments. Current learning methods for these games summarize that stream with a recurrent network that steps once per tick, so they assume everyone's sensors tick together and on schedule. We propose a different summary. Treat each agent's observation-and-action history as a continuous curve and describe it by its path signature, a fixed list of iterated integrals that records the curve's shape: how far each channel moved, and in what order pairs of channels moved relative to each other. A plain linear readout on that list can approximate any continuous function of the history. Because the signature does not change when the same curve is traced at a different speed or sampled at different instants, a belief model trained under one sensor timing should keep working under another.

The core claim is narrow and testable. The second-level signature terms of the joint path formed by "what I did" and "what I then saw the other agent do" encode lead-lag structure: whether the opponent's movement followed mine or preceded it. That is exactly the evidence needed to tell a reactive opponent from a stubborn one. A linear readout on these terms, updated online in constant memory, gives a belief over hidden opponent types and hidden state. We expect it to survive changes in sampling rate, dropped observations and communication latency between training and deployment, where per-tick recurrent beliefs do not. If a recurrent network that is simply given the time gaps and trained on randomized timing matches it, the claim reduces to an efficiency claim, and the experiments are designed to tell which of the two is true.

What exists and what is missing

The research file contains no paper that uses path signatures inside partially observable stochastic games (POSGs: multi-agent settings with hidden state, private observations and private rewards). The neighbouring work falls into three groups, and each plays a different role here.

The first group motivates the gap. Standard multi-agent learning on the StarCraft Multi-Agent Challenge passes local observation histories through per-tick recurrent networks (The StarCraft Multi-Agent Challenge). MACAD-Gym frames urban driving as a POSG with radio links between vehicles, but it relies on frame stacking (Multi-Agent Connected Autonomous Driving using Deep Reinforcement Learning). A survey of driver modeling names, as its open problem, compact representations of interactive trajectories in asynchronous continuous time (A Taxonomy and Review of Algorithms for Modeling and Predicting Human Driver Behavior). Continuous-time multi-agent value iteration shows that discrete-time learners lag and become biased when control intervals are randomized between 0.01s and 0.09s (Continuous-Time Value Iteration for Multi-Agent Reinforcement Learning). That fix replaces the Bellman recursion with Hamilton-Jacobi-Bellman equations, and it covers only deterministic, cooperative, fully observed systems. We leave the value side alone and change only how a partially observing agent summarizes its history, which is the part that work does not touch.

The second group constrains the design. Neural recursive belief states model opponents' nested beliefs with sampled latent codes. Their cost grows as $O((nK)^l)$ in agents, samples and belief order, and they fail catastrophically in Tiger with a single sample (Neural Recursive Belief States in Multi-Agent Reinforcement Learning). We do not attempt deep recursion. Our belief is a deterministic first-order readout, chosen precisely to avoid the sampling bottleneck that paper exposes. Learned Belief Search shows that learned beliefs can replace exact belief tracking at scale in Hanabi (Learned Belief Search: Efficiently Improving Policies in Partially Observable Settings), but its belief model is an autoregressive network over discrete turns. Compact value representations for one-sided POSGs project beliefs through a hand-designed matrix onto marginals (Compact Representation of Value Function in Partially Observable Stochastic Games). The signature offers a generic coordinate system in place of that hand-designed one. We test it only as a learned feature, and we do not claim that the convexity guarantees transfer.

The third group supplies the method. Signatures are invariant to time reparameterization and robust to irregular sampling (Csaba Tóth et al.). Linear functionals of signatures approximate continuous path functionals (Enea Monzio Compagnoni et al.; Linus Bleistein et al.). Level-two terms encode the chronological order of events across channels (Andrey Kormilitzin et al.). Rough Transformers combine local window signatures with global ones and remain robust with half the data dropped, but they were evaluated only as passive forecasters and classifiers (Rough Transformers). The rough-path policy optimization method dfPO borrows rough-path intuition for single-agent, fully observed control, and never builds signature features over observation histories (Stochastic Differential Policy Optimization: A Rough Path Approach to Reinforcement Learning). What is new here is the closed loop: signatures computed over a path that contains the agent's own actions, read out as a belief about other strategic agents, and used to drive behaviour.

Core mechanism

Agent $i$ maintains a low-dimensional path $X_t \in \mathbb{R}^k$. It is built from a learned linear projection of its observations, a cumulative encoding of its own actions, and an optional explicit time channel. Whenever a new observation arrives, after an arbitrary gap $\delta$, the agent updates the signature truncated at level $m$ using Chen's identity, the multiplicative rule for joining path segments:

$$ S(X)_{0,t+\delta} = S(X)_{0,t} \otimes S(X)_{t,t+\delta}, $$

where $\otimes$ is the truncated tensor product and the increment signature over a linear segment has a closed form. The update therefore needs constant memory, behaves like a recurrent cell, and requires no fixed tick. The belief is a linear readout

$$ \hat b_t = \mathrm{softmax}\big(W\, S(X)_{0,t}\big), $$

over hidden opponent types and coarse hidden-state variables. Under centralized training with decentralized execution, the true hidden variables are available as labels during training, so $W$ is fit by cross-entropy. The policy takes $\hat b_t$, the current observation and a windowed log-signature as input. With $k=6$ and $m=3$, the signature has 258 terms, which keeps the known combinatorial blow-up in channel count under control.

The invariance is double-edged. Opponent speed can itself be the evidence of type. We therefore treat the time channel as an explicit switch and test it, rather than assuming invariance is always desirable.

Research Program

The work is built in three stages. First, a diagnostic two-player continuous game in which the hidden opponent type is identifiable only through lead-lag responsiveness, meaning whether the opponent turns toward the ego agent after the ego agent moves. Every displacement statistic is matched across types, so first-level terms are provably uninformative and second-level terms are informative. Second, a competitive continuous-time particle setting adapted from the Predator-Prey task of the continuous-time multi-agent benchmark (Continuous-Time Value Iteration for Multi-Agent Reinforcement Learning). Each prey gets a hidden behaviour type, each agent observes on its own random clock, and observations are dropped stochastically. Third, the MACAD-Gym three-agent intersection with hidden yielding or aggressive driver traits and variable radio latency. We also run Running with Scissors and Multi-Agent Tiger to compare directly against recursive belief states on their own benchmarks.

For each setting we define a training timing regime, either a fixed clock or a single interval distribution, and a family of shifted test regimes. The shifts are rate multipliers between 0.25× and 4×, dropout from 0% to 70%, latency jitter, and mismatched clocks across agents. Belief quality is measured as log-loss and calibration of $\hat b_t$ against the true hidden type over time within an episode. Behaviour is measured as return, win or catch rate, and collision rate for driving. For the competitive two-player cases, we also report empirical exploitability against a best-response opponent trained against the frozen policy.

Baselines

The naive reference point is a memoryless policy on the current observation plus a frame stack, the MACAD-Gym default. It bounds how much history matters at all in each setting.

The standard competitor is the per-tick GRU history encoder used throughout PyMARL-style agents (The StarCraft Multi-Agent Challenge). We run it in its strongest fair form: the time gap $\delta$ is appended to every input, it is trained on randomized timing, and it receives the same auxiliary belief-prediction loss with the same centralized labels. This baseline is the strongest competitor because it is the simplest thing that could absorb irregular sampling, and it carries no signature assumptions.

A second competitor is a random controlled differential equation reservoir with only a trained linear readout (Random Controlled Differential Equations). It is the closest continuous-time alternative that shares our "fixed features plus linear readout" structure.

A third is a Rough Transformer encoder over observation windows (Rough Transformers). It tests whether attention on top of signatures beats a linear readout.

On the recursive-belief benchmarks, we compare against neural recursive belief states with $K=10$, the sample size that paper found necessary (Neural Recursive Belief States in Multi-Agent Reinforcement Learning).

All methods share the same policy and critic learner, environment-step budget, number of seeds, and hyperparameter search budget, and encoder parameter counts are matched within a factor of two.

Reported numbers to anchor against are thin. The file reports QMIX reaching 100% win rate on SMAC easy maps and most methods 0% on super-hard maps (The StarCraft Multi-Agent Challenge), but these are not asynchronous settings. For the continuous-time benchmarks, the file gives only a qualitative result, that discrete-time learning is distorted relative to ground truth. For Running with Scissors, it gives only qualitative superiority of higher-order belief agents. No reported result was found on Lacuna for any asynchronous or latency-shifted POSG, so all baseline numbers will come from our own runs.

Beating the GRU baseline means the following. On shifted test regimes, the signature belief achieves significantly lower belief log-loss and higher return across seeds, while staying within noise of the GRU on the training regime.

The key ablations remove one ingredient at a time. Truncation at level one removes the lead-lag area terms, and removing actions from the path breaks the interactive joint path. Each should collapse performance on the diagnostic game if the mechanism is what we claim. A third ablation toggles the time channel.

Why not just…?

Why not just give a GRU the time gaps and train on randomized timing? This is the real threat, and the proposal is built around it. Evidence that discrete-time learners degrade under irregular intervals comes from learners that were not given the gaps (Continuous-Time Value Iteration for Multi-Agent Reinforcement Learning), so it does not settle the question. Our shifted-regime tests include timings outside the randomization range used in training. If the augmented GRU still matches the signature belief there, we will report that the signature's contribution is sample efficiency and a parameter-free, label-efficient readout rather than robustness, and measure that separately through belief accuracy against the number of labelled episodes.

Why not use a neural CDE or ODE encoder, which already handles irregular sampling? Solver-based models are slow over long sequences (Rough Transformers). That matters inside a reinforcement learning loop that runs millions of steps. The random-CDE reservoir baseline isolates whether random continuous features do as well as the structured iterated integrals. If they do, the lead-lag interpretation is not what is doing the work.

Why not use a plain Transformer over the observation window? Its attention cost is quadratic in history length, and it degrades under heavy dropout (Rough Transformers). It also has no built-in notion of cross-channel ordering beyond what it learns. We include the Rough Transformer variant so that "signatures plus attention" competes against "signatures plus linear readout". If attention wins only on the training regime, that supports the claim that the linear readout transfers better.

Why not solve the game exactly? Point-based solvers for zero-sum POSGs stop at horizon 10, with CFR+ running out of memory and HSVI timing out (ε-Optimally Solving Two-Player Zero-Sum POSGs). Continuous-time, asynchronous versions do not fit their discrete history trees at all. We therefore use exact solutions only as a sanity reference on a discretized version of the diagnostic game.

Decisive checks

The diagnostic game gives the cleanest falsification. If the level-two signature readout does not recover opponent type when every level-one statistic is matched, the central mechanism is wrong.

The 4× rate-shift and 70%-dropout regimes in Predator-Prey and MACAD-Gym decide whether the robustness claim holds against the time-aware, timing-randomized GRU.

The comparison with recursive belief states on Running with Scissors and Tiger shows whether a deterministic first-order readout avoids the small-sample collapse reported there. It also shows what is lost by giving up higher-order beliefs.