Matching-Scheduled Dual Ascent for Action Selection in Coordination Graphs

Teams of agents that each see only part of the world often need to choose actions jointly. One example is two predators that must strike the same prey at the same moment. A common way to do this is a coordination graph: the team's value is written as a sum of per-agent terms plus pairwise terms on edges between agents. The best joint action is then found by passing messages along those edges. On graphs with cycles, the standard message passing (max-plus) can oscillate, never settle, and return a joint action that is far from the best one. Current fixes cut edges out of the graph. That avoids the cycles, but it also removes coordination the task may need.

We propose a different fix that keeps every edge. Max-plus is replaced with an equivalent dual coordinate-ascent procedure, and the edges are scheduled by matchings: in each communication round, every agent exchanges messages with at most one partner. Messages exchanged inside one matching never interfere with each other. Each round can therefore only tighten a computable upper bound on the team's value. This gives a convergent schedule that runs in parallel, needs one message per agent per round, tolerates dropped messages, and reports its own optimality gap. That gap can be used during learning as a signal of how much to trust the selected action.

Core Claim

Deep Coordination Graphs (DCG) shows that pairwise payoffs avoid relative overgeneralization. Relative overgeneralization is the failure in which per-agent value sums such as QMIX learn to avoid jointly optimal actions because those actions look bad when explored alone. DCG pays for this with loopy max-plus and a fixed iteration cutoff, and it gives no guarantee about the result. Its default graph is fully connected, which is the most cyclic graph possible.

Our claim is that the right replacement is not acyclicity. It is a schedule under which every step provably improves the same objective. Let $f^i(a^i)$ be agent $i$'s utility and $f^{ij}(a^i,a^j)$ the payoff on edge $\{i,j\}$, both computed from the agents' observation histories. Let $\lambda_{ji}(a^i)$ be the share of edge $\{i,j\}$'s payoff that has been moved onto agent $i$. For any choice of $\lambda$, the bound

$$U(\lambda)=\sum_i \max_{a^i}\Big[f^i(a^i)+\sum_{j}\lambda_{ji}(a^i)\Big]+\sum_{\{i,j\}}\max_{a^i,a^j}\Big[f^{ij}(a^i,a^j)-\lambda_{ji}(a^i)-\lambda_{ij}(a^j)\Big]$$

is at least the true best joint value $\max_{\mathbf a} Q(\mathbf a)$.

Updating all $\lambda$ on one edge to their best values is an exact block-coordinate step on $U$. In such a step, an agent repartitions the payoff between itself and its partner, which is the "handshake" update of MPLP++. The updates on edges in a common matching touch disjoint agents, so they can run simultaneously and still never increase $U$. A proper edge coloring covers the graph with at most $\Delta+1$ matchings, where $\Delta$ is the maximum degree; this bound comes from Vizing's theorem. A full sweep over all edges therefore costs at most $\Delta+1$ communication rounds.

The agents also obtain a gap for free. They decode a joint action $\hat{\mathbf a}$ from the local maximizers and compute $U(\lambda)-Q(\hat{\mathbf a})\ge 0$. When the gap is zero, the selected action is certified optimal.

The novelty is not dual block-coordinate ascent on Markov random fields itself, which is classical. It lies in four things together:

  • running that ascent as the decentralized action-selection step of a multi-agent reinforcement-learning agent under partial observability;
  • using edge colorings as a communication protocol, not as a thread scheduler;
  • showing that a dropped message only skips a step and so cannot break monotonicity;
  • feeding the certified gap back into the bootstrapped learning target.

Research Program

Part one: the decentralized protocol. A distributed greedy edge coloring is computed once per episode. This is cheap for the graph sizes in our benchmarks, and recoloring after topology changes can be done locally. In round $r$, each agent that has a partner in matching $r \bmod K$ runs a two-message handshake: send its current reparameterized utility, receive the partner's, and both sides commit the edge update only after acknowledgment. The commit step is what makes a lost message equivalent to a skipped block. A skipped block leaves $U$ unchanged rather than corrupting it, which is the property that loopy max-plus lacks under packet loss. Computing the bound and the decoded value needs one extra aggregation, a sum of local terms. We charge that cost honestly as additional rounds.

Part two: training. We substitute this procedure for max-plus inside DCG's training loop, both when acting and when computing the bootstrap target. In DCG, the target's $\arg\max$ is itself an output of loopy inference, so inference error feeds directly into the learning target. We then test one use of the gap: down-weighting temporal-difference targets whose bootstrap action has a large certified gap. This is an ablation, not a core assumption.

Part three: topology. We study how the graph shape governs rounds-to-certificate. Our working model is that rounds to reach a given gap scale with the edge chromatic number times the number of sweeps needed. Sweeps needed should depend on cycle structure rather than on the spectral gap. This is motivated by Beyond spectral gap, which shows that spectral gap mispredicts decentralized optimization (rings beat stars) and proposes an "effective number of neighbors" instead. This creates a real tension. Dense graphs reduce relative overgeneralization but pay about $n-1$ rounds per sweep. Sparse cyclic graphs are cheap per sweep but may need more sweeps. We will measure which topology property actually predicts certification cost on learned payoffs: chromatic index, spectral gap, effective number of neighbors, or the Kirchhoff index used by KINGS.

The method draws on prior work in four roles:

  • Mechanism. MPLP++ supplies the handshake update and the matching decomposition, but on a centralized GPU. It also reports that sequential TRW-S wins on very sparse graphs. We revisit that finding because in a decentralized system the cost is communication rounds, not floating-point operations, and a sequential sweep costs $O(N)$ rounds.
  • Coloring as a communication schedule. D-ADMM supplies the idea that a coloring can schedule peer-to-peer communication, but its guarantees are for continuous convex objectives with $\chi>2$ requiring strong convexity. Our objective is a discrete maximization whose dual is convex, so monotonicity carries over without those assumptions.
  • Motivating gap. Coordinated MARL in Networked Distributed POMDPs motivates the work. It couples Q-learning with synchronous Max-Sum on cyclic sensor graphs and explicitly lists better DCOP algorithms for cyclic graphs as open.
  • Constraint. Residual Belief Propagation and Scalable BP via Relaxed Scheduling constrain the design. They show that asynchronous informed schedules calm oscillation, but they rely on priority queues that peers cannot inspect. Their convergence proofs also hold only on trees, whereas the dual-ascent argument holds on any graph.

Baselines

Naive reference point. DCG with synchronous loopy max-plus at its published iteration cutoff, as in Deep Coordination Graphs. This is what practitioners run today. We use the authors' hyperparameters and the same networks, seeds, and environment steps. We count communication rounds for every method, since each synchronous max-plus iteration is one round.

Strongest graph-modifying competitors. We compare against two methods that remove cycles instead of scheduling around them.

We give each the same environment-step budget and the same hyperparameter-search budget, and we report communication rounds per decision. DHCG's sequential pass along the DAG is charged one round per level. No numerical win rates or returns for these methods are recorded in the file, so we will rerun them: no reported result found on Lacuna for DCG, DHCG, or KINGS numeric scores on MMM2, Predator-Prey, or MACO.

Monotonic factorization. QMIX (QMIX) is included as the zero-communication reference.

Ablations. Four ablations isolate the key ingredients, because the coloring and the dual form could each be doing the work.

  • Matching-scheduled max-plus: same schedule, no dual form.
  • Synchronous damped dual ascent: dual form, no schedule. This is convergent but averages all edges at once, as in MPLP.
  • Fully sequential edge-by-edge ascent in TRW-S order: best per-update progress, worst round count.
  • The full method with and without gap-weighted targets.

What counts as beating the baselines. The method beats max-plus DCG if, at an equal or smaller per-decision round budget, it reaches higher return on Predator-Prey with $p=-1.5$ and on MACO, and also certifies optimality on a substantially larger fraction of decisions. It beats DHCG and KINGS if it matches or exceeds their return on fully connected or cyclic graphs without removing edges.

Why not just…?

Why not just damp max-plus and run more iterations? This is the most serious threat. Damping often stops oscillation in practice. However, it gives no bound, no certificate, and no protection against dropped messages, and its fixed points need not decode to good actions. The ablation settles the question directly. We sweep damping and iteration count for synchronous max-plus at matched round budgets and compare against the true optimum on payoff graphs extracted from trained agents. For up to roughly 10 agents with small action sets, the optimum is computed exactly by enumeration. If tuned damped max-plus matches our decoded-action quality at equal rounds, the remaining contribution reduces to the certificate and dropout robustness, and we will say so.

Why not just prune cycles, as KINGS or DHCG do? Cyclicity-Regularized Coordination Graphs itself shows that pruning on the wrong criterion collapses Gather. Pruning also requires a Laplacian pseudoinverse that the file identifies as an $\mathcal{O}(|E||V|^3)$ centralized cost. DHCG's acyclic graphs force an ordering on peers. Our method keeps all edges and needs no global matrix computation. Pruning could still win when the removed edges carry little value. The topology study measures exactly this by running both approaches on the same learned payoffs.

Why not just use QMIX and skip communication? On tasks without tight coupling this may be enough, and we report it. Deep Coordination Graphs shows that value-factorization methods such as VDN fail at punishment $p=-1.5$ in Predator-Prey. The proposal is aimed at that regime, not at SMAC tasks where monotonic methods already do well.

Why not run residual or relaxed-priority scheduling? Those schedulers need a global or shared view of message residuals, which peers in a network do not have. A local residual variant also breaks the ascent guarantee unless it is restricted to matchings. We include a local-residual matching selector as an ablation.

Proposed Experiments

Offline inference study. First, an offline study isolates inference from learning. We freeze trained DCG payoff networks on Predator-Prey and MACO and log the payoff graphs encountered. We then run every inference method on these graphs over topologies we impose: complete, ring, 2D grid, random 3-regular, and Erdős–Rényi. We report the fraction of decisions that reach the exact optimum, the mean normalized value loss, the certified gap, and the rounds to reach gap $\le\epsilon$. On each topology we fit rounds-to-certificate against chromatic index, spectral gap, effective number of neighbors, and Kirchhoff index.

The decisive check has two parts. The first is whether matching-scheduled ascent dominates synchronous max-plus at equal rounds on cyclic graphs. The second is whether chromatic index or spectral gap better predicts certification cost.

Full learning runs. Second, we run full learning on three benchmarks: Predator-Prey at $p=-1.5$, the MACO tasks including Gather, and SMAC MMM2. We use the protocol described in Baselines and at least 8 seeds. We report return or win rate together with rounds per decision.

Dropout and topology change. Third, we stress-test partial observability and communication fragility on the ND-POMDP sensor networks 15-3D and 25-Grid from Coordinated MARL in Networked Distributed POMDPs. Their reported comparison is qualitative: Coordinated Learning outperformed CBDP on 15-3D and scaled to $T=100$ on 25-Grid. We inject independent message-drop rates from 0 to 30% and random edge churn, and compare our handshake protocol against synchronous Max-Sum on discounted reward.

Falsification. The proposal is falsified if either of the following holds. One is that tuned damped max-plus equals our method on both decoded-action quality and return at matched rounds, even with dropouts. The other is that the certified gap is uncorrelated with temporal-difference error, which would mean the gap-weighting has no signal to exploit.