Measuring Bellman Completeness Inside Multi-Agent World Models

Multi-agent world models, which are learned simulators that let a team of agents practice in imagination instead of in the real environment, have made cooperative reinforcement learning far cheaper in environment samples. They share a stubborn limit, though. Imagined rollouts stop helping after a handful of steps, and the field usually blames errors in the learned simulator for this. We propose a different explanation that can be tested directly. The value network trained on those rollouts may be unable to represent its own update targets. As teammates change their policies, the function the critic is asked to fit moves, and it can move outside anything the critic can express. That failure would appear even with a perfect simulator. The world model also offers a way to measure it: a model can draw two independent next states from the same state and joint action, which removes the "double-sampling" obstacle that makes this error unmeasurable from logged data.

The core proposal is an estimator of this representational error, computed from paired imagined transitions under the teammates' current policies. We use it to decide, per state and per training phase, how far to trust imagination. The note also sets out a diagnostic study with a simulator-reset oracle in cooperative multi-agent robot control. That study separates simulator error from critic error and from teammate-induced drift, and it decides whether the fix is worth building.

Core Claim

Bellman completeness is the property that applying one step of the Bellman update (reward plus discounted next-step value) to any function in the critic's class gives a function that is still in that class. When completeness fails, every fitted update projects its target back into the class and loses some accuracy, and those losses compound across updates (Randomized Exploration in Reinforcement Learning with General Value Function Approximation; Taming "data-hungry" reinforcement learning? Stability in continuous state-action spaces).

In cooperative multi-agent learning with a centralized critic, the joint transition kernel is stationary, which is the point made by MADDPG. The policy-evaluation update still depends on the current joint policy, because the next-step value is taken under the teammates' next actions. Completeness is therefore a property of the pair (critic class, joint policy). A class that is nearly closed under the team's policy at one point in training can be far from closed after teammates adapt. Centralization removes non-stationarity from the dynamics. It does not remove it from the fitting problem.

We claim three things. First, this policy-dependent projection error is a measurable, separate cause of the short useful imagination horizons reported for multi-agent world models, and it is not reducible to simulator error. Second, a world model makes the error estimable without extra real samples. Third, gating imagination by this signal beats gating by ensemble disagreement, which is what current methods use.

To make this precise, let $f$ be the current critic and $\mathcal{F}$ its function class. Let $y = r + \gamma f(s', \mathbf{a}')$ be a backup target, with $s'$ drawn from the world model at $(s,\mathbf{a})$ and $\mathbf{a}'$ drawn from the current joint policy. The target error we care about is the inherent Bellman error $\inf_{g \in \mathcal{F}} \mathbb{E}[(g(s,\mathbf{a}) - \mathcal{T}f(s,\mathbf{a}))^2]$. Here $\mathcal{T}f$ is the conditional mean of $y$, and the expectation is over states in the replay buffer.

Regressing a fresh network $g$ onto single-sample targets overestimates this quantity by the conditional variance of $y$. Offline, that variance cannot be separated out, which is the double-sampling problem behind the difficulty Xie and Jiang work around with tournaments. With a model we draw two independent targets $y_1, y_2$ from the same $(s,\mathbf{a})$ and estimate

$$\widehat{\mathrm{IBE}} = \mathbb{E}\big[(g(s,\mathbf{a}) - y_1)^2\big] - \tfrac{1}{2}\,\mathbb{E}\big[(y_1 - y_2)^2\big],$$

where $g \in \mathcal{F}$ is fit on held-out imagined data and the second term cancels target noise. Each $g$ is fit on data separate from the evaluation set, so the first term does not reward overfitting.

The estimate is conditional on the model, and model error enters it. We therefore report it alongside ensemble disagreement and treat the two as different axes. Disagreement asks whether the simulator is sure. The estimator asks whether the critic can express what the simulator says it should.

Relation to Prior Work

Several papers motivate the gap. MARIE, DIMA, VDFD and DMAWM each build a multi-agent world model and train critics inside it. MARIE uses a shared Transformer with Perceiver aggregation. DIMA uses sequential diffusion over agents' actions. VDFD disentangles dynamics under QMIX. DMAWM disentangles agent latents and reports that imagination beyond four steps collapses performance. All four treat critic training inside imagination as unproblematic and attribute horizon limits to dynamics error. We test that attribution directly instead of adding another simulator architecture.

Other papers supply parts of the method. MOBILE penalizes the spread of Bellman targets across a dynamics ensemble. M2AC masks imagined transitions by ensemble disagreement and keeps long "non-stop" rollouts. MBPO bounds rollout length because error grows with horizon. We reuse their ensembles and short branched rollouts. Our signal differs in kind, however. Ensemble spread goes to zero wherever the models agree, even if the agreed-upon target lies outside the critic class. Our estimator is designed to be large exactly there.

Some papers constrain the design. Fujimoto et al. show that Bellman error can be tiny while value error is large; they found BRM's value error about 57 times its Bellman error on HalfCheetah. We therefore never minimize our estimator as a training loss. We use it only as a diagnostic and as a gate, and we validate it against true value error computed by Monte Carlo in the real simulator.

MBRCSL takes the opposite route and avoids completeness entirely through supervised return-conditioned learning on model-stitched data. Its LinearQ result, that Q-learning needs network width linear in state count to be complete while supervised learning needs constant width, sharpens our question about whether capacity alone fixes the problem. Fitted Q Evaluation Without Bellman Completeness via Stationary Weighting offers a reweighting remedy for evaluation, and it is a natural later comparison.

Finally, Minimax-Optimal Policy Regret in POMGs limits policy switches to geometrically growing epochs because each switch forces the other side to readapt. We borrow this idea for a secondary mechanism that pauses teammate updates while the critic catches up.

Research Program

The work has three stages, and the first decides whether the other two are worth doing.

The first stage is a decomposition study in Multi-Agent MuJoCo, where the true physics simulator can be reset to arbitrary states. We train model-based multi-agent actor-critic agents, using a DMAWM-style model with MAPPO or FACMAC-style critics (FACMAC). Imagination comes from one of three sources:

  1. the learned world model;
  2. the true simulator reset to buffer states, which gives perfect dynamics;
  3. the true simulator with teammate policies frozen at a snapshot.

We sweep rollout horizon from 1 to 20. If the horizon collapse persists under perfect dynamics and lessens when teammates are frozen, then the value side, and specifically policy-dependent incompleteness, is a real cause. We also compute the estimator against exact targets from the true simulator, and check whether it rises after teammate updates and predicts Monte Carlo value error.

The second stage builds the estimator into training. Each critic update also fits a small auxiliary copy of the critic architecture onto paired imagined targets. From it we compute a state-bucketed version of the estimator, using clusters of critic embeddings, and use it in two ways. Rollouts branched from a state continue only while the accumulated estimated projection error stays under a budget, which sets horizon locally rather than globally. Imagined transitions are also down-weighted where the estimator is high.

The third stage is the teammate-pacing mechanism, and it is optional and ablated. When the estimator jumps by more than a threshold after a joint policy update, actor updates pause for a few critic epochs.

Baselines

The naive reference is model-free MAPPO trained on the same real-sample budget. It establishes how much any world model helps at all.

The strongest existing methods are MARIE and DMAWM on SMAC. DMAWM reports a 71.5% win rate on the Super-Hard corridor map against 18.6% for the next best model-based baseline (DMAWM). MARIE reports 71% on corridor within 100k–400k environment steps (MARIE). Our method is implemented as a change to the imagination gating of the DMAWM pipeline, so the world model, critics and actors are identical, and we compare against DMAWM rerun under our seeds and budget.

On Multi-Agent MuJoCo I found no reported return on Lacuna for MARIE, DIMA or DMAWM. We therefore rerun the DMAWM-style backbone ourselves with its fixed four-step horizon. On Bi-DexHands BottleCap, DIMA reports a return of 259.9 against 210.9 for HASAC (DIMA), and we include that task as a harder continuous test.

Three gating baselines isolate the key ingredient, since they share the backbone and differ only in how imagination is trusted:

  • a fixed global horizon tuned over {1, 2, 4, 8}, which is the MBPO recipe;
  • M2AC-style disagreement masking with a reward penalty;
  • a MOBILE-style penalty on the ensemble spread of the centralized-critic target.

Two ablations target our estimator directly. One replaces the double-sample estimator with its single-sample, variance-contaminated version, which tests whether removing the double-sampling bias matters. The other drops teammate pacing.

Fairness rules apply to every method. All methods get the same real-environment budget, the same world model checkpoints, and at least five seeds. Each method receives an equal hyperparameter search of twelve configurations. Wall-clock time is reported, because the auxiliary regression adds compute.

Beating the strongest baseline means one of two things. The first is a statistically reliable win-rate gain over rerun DMAWM on corridor and on SMACv2 maps at equal samples. The second is reaching its final performance with at least 30% fewer real samples, together with a longer useful horizon on Multi-Agent MuJoCo.

Why not just…?

Why not just use shorter rollouts? A fixed short horizon is the honest default, and it may capture most of the benefit. The decomposition study settles this. If the value-side error is roughly uniform across states and training time, a tuned global horizon will match adaptive gating, and we would report that. The proposal only pays off if the estimator varies strongly by state and spikes after teammate updates, which is precisely what the frozen-teammate oracle measures.

Why not just use ensemble disagreement, as MOBILE and M2AC do? Disagreement measures whether the simulator is uncertain, not whether the critic can represent the target. MOBILE still assumes the value updates close. In the perfect-dynamics oracle condition, disagreement is zero by construction, so any remaining horizon collapse is invisible to it. The direct comparison is the gating ablation. We also report the correlation between the two signals: if they are highly correlated in practice, our estimator adds little.

Why not just make the critic bigger? This is a real threat. The LinearQ analysis in MBRCSL indicates that completeness can be bought with width. We sweep critic width by a factor of 4 in both the oracle study and the full method. If a wider critic removes both the estimator spikes and the horizon collapse at acceptable cost, the correct recommendation is "scale the critic." In that case the estimator becomes a tool for deciding how much capacity is needed, not a training component.

Why not just avoid value learning, as MBRCSL does? Return-conditioned supervised learning sidesteps completeness, but it relies on filtering near-deterministic rollouts. It is untested in online multi-agent settings, where teammates keep changing and the return distribution keeps shifting. We treat it as future comparison rather than a baseline here.

Decisive Checks

The proposal stands or falls on four observations.

  1. With perfect dynamics in Multi-Agent MuJoCo, horizon collapse remains, and freezing teammates reduces it.
  2. The double-sample estimator predicts Monte Carlo value error better than ensemble disagreement and better than the single-sample estimator.
  3. Estimator-gated imagination beats both tuned fixed-horizon gating and disagreement gating at equal samples on corridor, SMACv2, and Multi-Agent MuJoCo.
  4. The gain survives a 4× wider critic.

If the first observation fails, the program stops, and the result is a useful negative finding that simulator error is the whole story.