Where Do Decentralized Convergence Guarantees Stop Mattering?

Decentralized multi-agent learning studies agents that improve their behavior using only their own observations and rewards. There is no central trainer, no shared critic, and no view of what the other agents are doing. Theorists have built algorithms for this setting that provably reach an equilibrium, meaning a joint behavior where no agent gains by changing its own policy. These algorithms rely on a few recurring ingredients: entropy regularization (a bonus for keeping policies somewhat random), two-timescale updates (a value estimate that moves faster than the policy it evaluates), and optimism (a look-ahead that anticipates the other agents' next move). Almost none of them has been run on anything bigger than a four-player toy game, and several have never been run at all. Meanwhile, practitioners train independent deep learners with Adam and ignore the theory.

We propose to find out at what point, and why, each ingredient's advantage disappears. The design is an assumption-violation ladder. We start each algorithm in the exact setting its theorem covers and relax one assumption per rung: exact gradients, then sampled gradients, then neural networks instead of tables, then states instead of a single repeated game, then procedurally generated states that are never revisited, then games that are only approximately cooperative. At every rung we measure the quantity the theorem is actually about, which is distance to equilibrium, estimated by training a best-response deviator. We also measure task return. All methods receive the same tuning budget. The output is a map of which pieces of theory still earn their place in practice, and a controlled answer to whether a well-tuned independent PPO already captures them.

Core Claim

The claim is methodological, but it is testable. The theory-practice gap in decentralized multi-agent learning cannot be closed by dropping theoretical algorithms onto a benchmark and reporting win rates. Two confounds get in the way. First, optimization tricks swamp algorithmic differences: Hu et al. showed that switching QMIX to Adam alone raised the corridor win rate from 0% to 98%. Second, benchmark exploits reward behavior that has nothing to do with coordination: SMACv2 showed a policy blind to its observations reaching near 100% on 8m_vs_9m.

The gap can be closed by isolating ingredients and violating assumptions one at a time, while measuring equilibrium quality directly. We make three predictions, each of which the program can falsify:

  1. Entropy regularization keeps its benefit through the neural and Markov rungs.
  2. The two-timescale critic becomes indistinguishable from an ordinary target network once Adam and tuned step sizes are in place.
  3. Optimism helps only in zero-sum games, and only while states recur.

What Prior Work Establishes and Leaves Open

The theoretical side supplies the methods, and each paper was validated narrowly or not at all.

  • Independent natural policy gradient. Cen et al. prove fast, action-count-independent convergence for independent natural policy gradient with entropy regularization in potential games. A potential game is one where a single shared function tracks every agent's incentive to deviate. They test on one random 4-agent, 20-action stateless game, using oracle gradients.
  • Two-timescale actor-critic. Sastry et al. prove that a decentralized two-timescale actor-critic reaches approximate equilibrium in Markov potential games. They test on a 4-traveler, 2-link routing game with tabular critics.
  • Zero-sum last-iterate methods. For two-player zero-sum games, Wei et al. (optimistic gradient play with a slow critic) and Cai et al. (regularization plus optimism under bandit feedback) prove that the current policy converges, not merely the average policy. Neither paper reports a single experiment. Cai et al.'s step-size schedules also depend on the discount factor and the state count, which an uncoupled agent cannot know. Both proofs assume irreducibility, meaning every state is revisited infinitely often.
  • Approximately cooperative games. Guo et al. quantify how far a game is from a potential game with a scalar α. They note that their regret bounds are far more pessimistic than their own simulations. This is direct evidence that the rates hide slack, and it motivates measuring real behavior instead of trusting the bounds.
  • Linear function approximation. Cui et al. extend guarantees to linear function approximation, but their policy replay needs coordination. We therefore treat it as out of scope for the fully decentralized ladder.

The empirical side constrains the design.

  • Tuning. Hu et al. show that tuning must be equalized.
  • Benchmark choice. SMACv2 rules out original SMAC as evidence of coordination.
  • Task breadth. Papadopoulos et al. show that simple actor-critics beat complex methods on 5 of 8 cooperative tasks, and that SMAC-tuned methods fail on sparse-reward tasks such as the warehouse task RWARE. We therefore require a spread of tasks.
  • A tension we can test. Rethinking Individual Global Max proves that decomposing a team value into per-agent values is lossy under partial observability. Its fix distills from an omniscient central expert, which is unavailable in our setting. Fully decentralized learners never decompose a joint value, so the ladder can test whether they avoid that compounding error in the paper's zero-sight-view setting.

Research Program

We would build a single codebase. In it, the four theoretical algorithms and an independent PPO learner share one environment interface (PettingZoo's agent-environment cycle, PettingZoo), one network backbone, and one optimizer family. We implement each theoretical ingredient as a switchable module that can be added to independent PPO:

  • entropy regularization with a decaying temperature;
  • a critic whose learning rate is a fixed multiple of the actor's;
  • an optimistic extrapolation step on the policy update.

This lets us attribute differences to ingredients rather than to codebases.

The ladder has six rungs.

  1. The original synthetic games, reproduced exactly with oracle gradients: the random potential game, the Markov routing game, and the congestion and perturbed-team games of Guo et al.. This rung checks that our implementations match the theory.
  2. The same games with sampled trajectories replacing oracle gradients.
  3. The same games with small neural networks replacing tables.
  4. Cooperative Markov tasks from the extended suite of Papadopoulos et al.: MPE Spread, Level-Based Foraging, and RWARE.
  5. SMACv2, where procedural generation breaks irreducibility. We also run SMAC under the zero-sight view.
  6. General-sum and zero-sum variants: competitive MPE tasks for the zero-sum algorithms, and congestion games whose α we increase by perturbing payoffs.

We also measure equilibrium quality at each rung. On rungs 1–3 we compute exact Nash gaps. On rungs 4–6 we estimate each agent's exploitability: we freeze all other agents and train a fresh best-response learner with a fixed budget, then record how much it gains over the incumbent. This estimate is a lower bound, so we report it together with the best-response budget.

Tuning is identical for every method. Each gets the same number of random-search trials over its own hyperparameters. The theoretical algorithms are run twice: once with their published schedules and once with tuned schedules. Comparing the two directly tests whether the schedules themselves are the weak point.

Baselines

Naive references. The first reference point is uniform random policies on every task. On SMACv2 we add the open-loop policy conditioned only on timestep and agent ID. SMACv2 reports that this policy falls to a 0% win rate there, so any method that fails to beat it has learned nothing closed-loop.

Independent PPO. The strongest competitor on the actual question is independent PPO with Adam, observation normalization, and tuned rollout length. Every agent learns alone and treats the others as part of the environment. It is the simplest fully decentralized method, and it is what a practitioner would try first. It gets the same backbone, interaction budget, seeds, and tuning trials as every other method. We found no reported result on Lacuna for independent PPO on these benchmarks, so we will establish the number ourselves.

Centralized-training reference. MAPPO and QMIX serve as an upper reference that has privileged information during training. They are run with the PyMARLzoo+ configurations. The file's reported numbers are:

  • On SMACv2 20-vs-23 maps, SMACv2 reports that "win rates for top algorithms like QMIX and MAPPO often fall below 25%."
  • On the cooperative suite, Papadopoulos et al. report that MAPPO and MAA2C lead on 5 of 8 benchmarks.

A decentralized method need not beat these references. What matters is the size of the gap.

Ablations. The key ablations add each theoretical ingredient to tuned independent PPO, one at a time and then all together.

Criteria for winning. A theoretical ingredient counts as beating independent PPO at a rung if two conditions hold together. First, it lowers estimated exploitability by more than the seed-to-seed spread, using at least ten seeds and non-overlapping bootstrap intervals. Second, it does not lower return. An ingredient that improves return but not exploitability, or the reverse, is reported as such rather than counted as a win.

Why not just…?

Why not just run tuned independent PPO and skip the theory? This is the real threat. It may be the correct answer on cooperative tasks, and the ladder is built so that it can be. If every ingredient's advantage vanishes by rung 3 or 4, that is itself a finding: it says where theory stops predicting practice. What independent PPO cannot show on its own is whether it cycles around an equilibrium or settles at one. Wei et al. argue that unregularized gradient play cycles in zero-sum games. Our exploitability traces over training would reveal such cycling even when return curves look flat.

Why not just use centralized training with decentralized execution? Centralized training answers a different question. It assumes that global state or a shared critic is available during training, which is exactly what fails in the privacy-restricted and competitive settings that motivate Cen et al.. It is also not uniformly strong: Papadopoulos et al. report that value-decomposition methods degrade as agent counts grow on Spread and PressurePlate. We include it as a reference so the cost of decentralization is visible, not as a competitor to beat.

Why not just benchmark the theoretical algorithms on SMAC and report win rates? Win rates on original SMAC can be earned without any coordination, as the open-loop result in SMACv2 shows. A single jump from toy game to benchmark also cannot tell which assumption broke. The ladder exists to localize failure to one rung.

Why not just trust the toy experiments already in the papers? Those experiments use oracle gradients or tabular critics at the scale where the proofs hold. They therefore test nothing about the assumptions practitioners violate. Guo et al.'s own observation, that their bounds are loose relative to their simulations, cuts both ways: the theory might be too pessimistic or too optimistic. Only rungs 2–6 can tell which.

Decisive Checks

The rung-1 check is reproduction. Our implementations must recover the published qualitative results: faster convergence with regularization in Cen et al.'s game, and a decaying Nash gap within $10^4$ iterations in Sastry et al.'s routing game. Those papers report no exact numbers, so the comparison is to their curves.

The central check has three parts:

  • Entropy regularization. Does its exploitability advantage over tuned independent PPO survive at rungs 4 and 5? This is where our first prediction is most exposed.
  • Irreducibility. On SMACv2, compare the published and tuned schedules of the optimistic methods. If both fail only once states stop recurring, the irreducibility assumption is doing real work.
  • Partial observability. In the zero-sight-view setting of Rethinking Individual Global Max, the paper reports roughly a 20% success-rate gain from central distillation. We check whether decentralized learners that never decompose values close any part of that gap without a central expert.

A negative answer on all three would turn the project into a precise statement of where current decentralized theory stops being informative. That would be an equally publishable and useful outcome.