Spending Integration Steps Only Where Credit Is Uncertain: Certified Path Attribution for Multi-Agent Value Learning

When a team of learning agents shares one reward, training has to work out how much each agent's action contributed. This is the credit assignment problem. The most common answer squeezes the team's value through a "mixing network" that can only increase when any individual agent's value increases. That constraint rules out sacrifice, where one agent takes a locally bad action so the team does better. Q-value Path Decomposition (QPD) avoids the constraint by borrowing Integrated Gradients from explainable AI. Integrated Gradients is an attribution method that splits a network's output among its inputs by adding up gradients at many points along a path. QPD applies it to a centralized team-value network and treats each agent's share as that agent's credit. The cost is that every training sample needs many network passes. QPD therefore truncated the integral to five uniform steps, whereas the attribution literature recommends 50 to 100. As a result, the credits QPD trains on do not sum to the team value they are supposed to decompose.

We propose to stop giving every training transition the same step budget. Integrated Gradients has a built-in exactness property called completeness: per-agent credits should sum exactly to the change in team value along the path. The amount by which a cheap estimate misses that sum is available for free. We use this residual, together with a nested-grid refinement check, as a per-sample error certificate. Each transition gets the smallest number of integration steps that makes its credit trustworthy. Our hypothesis is that attribution error is concentrated in a small fraction of transitions: the decisive, non-linear moments such as a sacrifice or a focus-fire switch. If that holds, faithful non-monotonic credit can be computed at close to the cost of a single gradient pass.

The same certified credits give a measurable answer to a question the field currently argues about: whether a given task needs non-monotonic credit at all. We measure how often, on a given map, an agent is certified to receive negative credit while team value rises.

Core Claim

Let $x$ be the critic input for a transition and $x'$ the reference point at the start of QPD's integration path. Let $Q$ be the centralized team-value critic. Let $\phi_i^{(m)}(x)$ be agent $i$'s credit computed with an $m$-point Riemann sum over the gradients of $Q$ with respect to agent $i$'s input features. The completeness residual is

$$ r^{(m)}(x) = \frac{\left| Q(x) - Q(x') - \sum_i \phi_i^{(m)}(x) \right|}{|Q(x) - Q(x')| + \delta}, $$

where $\delta$ is a small constant that avoids division by zero. The residual $r^{(m)}$ is zero for an exact integral and costs nothing beyond passes the method already makes.

Per-agent errors can cancel in the sum, so the residual alone is a necessary check but not a sufficient one. We therefore pair it with a second test. We evaluate on dyadic grids ($m = 1, 2, 4, 8, \dots$), so each refinement reuses every earlier gradient evaluation. The second test is the per-agent change between consecutive levels, $\max_i |\phi_i^{(2m)} - \phi_i^{(m)}|$, which is the standard error estimate from adaptive quadrature. A transition is refined only while either quantity exceeds a tolerance $\tau$, up to a cap $m_{\max}$.

The claim has three parts. First, under this rule the average number of steps per transition will be far below five. Second, the certified credits will be closer to a 100-step reference than QPD's uniform five-step credits. Third, these two effects together will match or improve QPD's learning curves at a fraction of the wall-clock cost.

This idea differs from the closest attribution work, Integrated Decision Gradients (IDG). IDG moves a fixed step budget along a single path toward the region where the model's output changes fastest, for after-the-fact explanation of one image. We instead move budget across the thousands of transitions in a training batch, driven by an error certificate. In our setting the attributions are regression targets, so their errors feed directly into learning. The two ideas are compatible, and IDG-style within-path weighting appears below as a separate ablation.

Research Program

The first stage is a measurement study that can kill the idea cheaply. We will train QPD critics with the released multi-channel design on SMAC maps and on didactic non-monotonic matrix games. For stored batches we will compute reference credits with $m = 100$ and record three things per transition: the error of the five-step uniform estimate, the completeness residual at each dyadic level, and the value-change magnitude. The proposal rests on two measured facts. The error distribution must be heavy-tailed, meaning a minority of transitions carries most of the error. And the residual-plus-refinement certificate must rank transitions by true error well, which we measure with Spearman correlation against the reference error.

If five-step error is instead spread evenly, adaptive allocation cannot help. In that case the right conclusion is that a better fixed quadrature rule is enough, and the proposal would pivot to that.

The second stage builds certified allocation into the training loop. Nested grids let a batch be processed in rounds: all samples get one step, the unresolved fraction gets two, and so on. We will measure cost in critic forward-backward passes and in wall-clock time on the same hardware. We will also test whether the tolerance $\tau$ can be tied to the scale of the temporal-difference error. The reasoning is that credit error smaller than the regression noise the agents already face is not worth paying for. This gives a principled default instead of another hyperparameter.

The third stage turns certified credits into a diagnostic. For each map we compute the sacrificial-credit rate: the fraction of transitions where the team value rises but some agent's certified credit is negative beyond tolerance. Uncertified five-step credits cannot support this statistic, because discretization error alone can flip signs. We will test whether this rate predicts, across maps, the performance gap between non-monotonic methods and well-tuned monotonic QMIX. That would turn the disagreement between QPD, ResQ and QPLEX on one side and Rethinking the Implementation Tricks and Monotonicity Constraint on the other into a per-task measurement.

On the attribution side, the method reuses IDG's observation that uniform steps are wasted in flat, saturated regions. It is also motivated by the variance analysis in Path-Sampled Integrated Gradients, which shows that restructuring the integral changes convergence from $O(m^{-1/2})$ to $O(m^{-1})$. That result tells us quadrature design matters at low step counts; it does not supply our allocation rule.

Enhancing Model Interpretability with Local Attribution over Global Exploration constrains the design. It shows that paths through regions a network never trained on yield meaningless gradients. We keep QPD's trajectory path for that reason: its points are states the critic actually saw. We will also report whether high-residual transitions cluster where the path leaves visited states.

Greedy PIG shows that one-shot path attribution splits credit arbitrarily among correlated inputs. This is a real limitation, and our method inherits it, because certification guarantees numerical accuracy of the integral, not a good split between redundant agents. We treat that as out of scope and state it as such.

Baselines

The naive reference point is QPD exactly as published: uniform five-step integration along the trajectory with the multi-channel critic. QPD reports an 85% median win rate on 3s5z, where QMIX reached 16%, and a 10% mean win rate on 3s5z_vs_3s6z, where all other methods stayed at 0%. These are the numbers our method must at least match at lower cost. Two variants isolate the step budget. QPD with $m = 1$ is essentially gradient times input change, the cheapest possible path credit. QPD with $m = 50$ is the expensive, near-exact version. Together they bound what budget alone buys.

The strongest competitors on the core question are the single-pass non-monotonic mixers, which avoid path integrals entirely. The first is ResQ, which adds a masked unconstrained residual to a monotonic mixer and reports about 90% on MMM2, where QMIX reached about 70%. The second is QPLEX, which factorizes advantages with positive attention weights and reports on average a 10% higher win rate than the next best method across 17 SMAC maps. Alongside these we run the monotonic reference, finetuned QMIX from Rethinking the Implementation Tricks and Monotonicity Constraint. That paper reports it "often reaching 100% win rates" on hard and super-hard maps, but the file gives no per-map number, so we will produce our own.

Fairness is the central issue, because the Rethinking paper shows that implementation details can outweigh architecture. Every method will therefore get the same finetuned recipe: the Adam optimizer, TD($\lambda$) targets (a standard multi-step return), the same replay buffer and network sizes. All runs use the PyMARL codebase from The StarCraft Multi-Agent Challenge, the same number of environment steps, and an equal hyperparameter search budget. Results are reported both against environment steps and against wall-clock time.

Beating a baseline has a specific meaning here. We must match or exceed QPD's win rate at no more than half its critic passes. We must beat ResQ and QPLEX on at least the maps and matrix games with a high sacrificial-credit rate. And we must not lose to finetuned QMIX on maps with a low rate.

Three ablations isolate the key ingredient. Random allocation gives the same average number of steps per transition, but to randomly chosen samples; it tests whether the certificate matters or only the average budget. Residual-only allocation drops the per-agent refinement check, testing whether cancellation in the sum hides real errors. IDG-style reweighting keeps the budget fixed and uniform across samples but moves steps within each path toward regions of steep value change, per Integrated Decision Gradients; it tests whether within-path placement already captures the gain. IDG reports an AIC (an insertion-curve faithfulness score) of 0.701 versus 0.571 for standard IG on ImageNet with ResNet-101. That shows placement matters in vision, but there is no reported result on Lacuna for IDG inside a multi-agent critic.

Why not just…?

Why not just use finetuned monotonic QMIX? This is the most serious threat. The Rethinking paper shows that tuned QMIX reaches very high win rates on hard SMAC maps and that monotonicity improves sample efficiency in purely cooperative tasks. On many maps QMIX may simply win. We do not argue otherwise. Instead, the sacrificial-credit rate is designed to predict exactly where it wins. The counter-evidence is QPD's 16% for QMIX on 3s5z and the matrix-game failures reported by ResQ and DAVE, but those QMIX runs were not tuned. If tuned QMIX matches certified QPD even on high-rate maps, the conclusion is that non-monotonic credit is not needed in SMAC, and we will report it that way.

Why not just use ResQ or QPLEX, which need only one pass? These methods are cheap and strong. Their weaknesses are specific. ResQ depends on a greedy estimate of the optimal joint action, which is unreliable early in training. QPLEX failed on the hard matrix games where DAVE succeeded, according to the DAVE paper. Neither produces credits that are guaranteed to sum to the team value. The matched-recipe comparison settles whether this matters for performance. Independently, only path credits support the certified diagnostic, which is useful even if win rates tie.

Why not just use a single local gradient, or a better fixed quadrature rule such as the trapezoid or midpoint rule? A single gradient vanishes where the critic saturates, which is the sensitivity failure described in Axiomatic Attribution for Deep Networks. A higher-order fixed rule is a real alternative. For smooth integrands it converges much faster than a plain Riemann sum and could make five uniform steps accurate everywhere. The first-stage measurement tests this directly by including fixed trapezoid and midpoint estimates at matched budgets. If a fixed rule already achieves reference-level error on the heavy tail, it is the simpler answer and we adopt it, with certification kept only as the diagnostic.

Why not just reweight steps along the path as IDG does? Within-path placement cannot move budget away from the many near-linear transitions that need only one step. It can only rearrange a fixed cost per sample. The IDG ablation measures how much of the gain placement alone recovers.

Decisive Checks

The idea stands or falls on three measurements. First, in the offline study on trained SMAC critics, a minority of transitions must carry most of the five-step error. The dyadic certificate must also rank transitions by true error well (Spearman correlation against the 100-step reference). Second, in training on 3s5z, 3s5z_vs_3s6z, MMM2, the matrix games and the difficulty-enhanced predator-prey task, certified allocation must match QPD's reported win rates while using substantially fewer critic passes. It must also beat the random-allocation ablation at the same average budget; otherwise the certificate is not doing the work. Third, across maps, the sacrificial-credit rate must correlate with the gap between certified QPD and finetuned QMIX. A near-zero rate on maps where QMIX wins and a high rate on maps where it loses would give the monotonicity debate a per-task test instead of a blanket answer.