Relabeling the Shadow Price: Sample-Efficient Dual Consensus for Coupled Multi-Agent Constraints

Many multi-agent control problems share one global budget. Buildings drawing on a common grid, robots limited by a shared energy allowance, and fleets under a joint fairness rule are examples. A standard way to coordinate them without a central controller is dual decomposition. Each agent keeps a local copy of a "shadow price" (a Lagrange multiplier saying how costly it currently is to consume the shared resource). It optimizes its own reward minus that price, and it averages its price with neighbors until the network agrees. In reinforcement learning this approach is very expensive in samples. Every time the price moves, the reward each agent is optimizing changes, and its policy has to be relearned from fresh interaction. Most of the environment data is spent chasing a moving price.

We propose to remove that cost. Each agent learns a single policy and critic conditioned on the price. Because the priced reward is linear in the price, every stored transition can be relabeled with any other price and reused to train the policy at that price. This is analogous to hindsight goal relabeling. When dynamics are coupled, the needed off-policy correction is a product of every agent's importance ratio, and agents can compute it with the same neighbor-averaging channel they already use for the price. A second payoff comes from the same object. A price that the network agrees on and samples once per episode works as a shared coordination signal. It lets decentralized agents run mixtures of joint behaviors, which we conjecture removes the duality gap that On the Hardness of Constrained Cooperative Multi-Agent Reinforcement Learning proves for independent product policies.

Core Claim

Two claims are tested here. The first is the main one. In decentralized constrained multi-agent RL with coupled transition dynamics and a global coupling constraint, almost all the sample overhead of primal-dual learning relative to unconstrained learning comes from relearning policies after price changes. Price-conditioned policies trained with price relabeling should reach a feasible, near-best policy in a number of environment steps close to that of an unconstrained learner on the same task.

The second claim is conditional. Suppose the network agrees on a price trajectory and draws one price per episode from it. Agents that observe the global state then realize a mixture of product policies, and the gap between the best feasible decentralized policy and the dual bound shrinks toward zero. That bound is otherwise stuck at $\Omega(\Delta)$.

The relabeling identity is simple. Each agent $i$ incurs a reward $r$ and a cost $c$ toward a shared budget $b$. Under a common price $\lambda \ge 0$, the per-step priced reward is

$$ \ell_\lambda(s,a) = r(s,a) - \lambda\,(c(s,a) - b), $$

where $s$ is the state and $a$ the joint action. For a fixed policy, the priced value splits as $Q_\lambda = Q_r - \lambda (Q_c - b/(1-\gamma))$, with $\gamma$ the discount factor. So separate reward and cost critics, both conditioned on $\lambda$, give the priced value at every price at once.

The hard part is that the data was collected while the network acted at price $\lambda_0$, whereas we want to evaluate the policy at $\lambda'$. Under coupled dynamics, the correction factor is the joint ratio $\prod_j \pi_j(a_j \mid s,\lambda')/\pi_j(a_j \mid s,\lambda_0)$. No single agent can compute it, because each agent knows only its own policy $\pi_j$.

Relation to Prior Work

The closest work is Distributed Constrained Multi-Agent Reinforcement Learning with Consensus and Networked Communication. It trains policies conditioned on the multiplier offline and runs neighbor-averaging of multipliers at execution. On CityLearn it reports a cost gap under 0.2% against a centralized oracle and 100% constraint satisfaction at up to 1,000 agents. That paper motivates our design: conditioning on the price works, and dual exchange is what keeps agents from meeting the budget by shutting down. It also sets the limit we target. It assumes separable dynamics, trains each agent independently and offline, and does not study online sample cost. Our contribution is the online, coupled-dynamics case, where a transition depends on all agents and relabeling requires a joint correction.

Three other lines constrain the design.

Scalable Constrained Policy Optimization for Safe Multi-agent Reinforcement Learning (Scal-MAPPO-L) handles coupled dynamics using advantages truncated to a few-hop neighborhood. That relies on influence decaying with network distance, which is exactly what a global budget violates.

On the Hardness of Constrained Cooperative Multi-Agent Reinforcement Learning proves that requiring independent product policies makes the problem non-convex. Strong duality then fails, with a gap of 3/4 in an explicit instance, and primal-dual errors stall at $\Omega(\Delta)$. Their fix is a primal-only method, which then depends on how well the joint value function factorizes across agents. We address the gap differently. With global-state observation, every deterministic joint policy is already a product of local deterministic policies, and deterministic policies are the vertices of the occupancy polytope. Mixtures over episodes of product policies therefore span the full feasible set. The only thing missing is shared randomness, and an agreed price can supply it. This is a conjecture to be verified on their counterexample, not a result we assume.

Divergence-Regularized Multi-Agent Actor-Critic warns that regularizer weights are fragile across environments. That is a reason to adapt the price rather than fix it.

Two papers supply the method. A Multi-Agent Off-Policy Actor-Critic Algorithm for Distributed Reinforcement Learning computes global importance ratios by having agents agree on the sum of their local log-ratios. We reuse this "log-consensus" to correct relabeled transitions, but we apply it along the price axis rather than between behavior and target policies. Order Matters: Agent-by-agent Policy Optimization (A2PO) supplies preceding-agent off-policy correction for reusing one batch across sequential agent updates, and we adopt it for the actor step. On the dual side, Proximity Without Consensus in Online Multiagent Optimization shows that a quadratic dual regularizer $-\delta\lambda^2$ keeps multipliers from exploding under constant step sizes. We use it so that sampled prices stay in a bounded range where the conditioned policies have been trained.

Research Program

The algorithm runs four coupled loops.

The first loop is acting. At the start of each episode, agents agree by a few neighbor-averaging rounds on a price drawn from a narrow distribution around their current estimate. Each agent then acts with its price-conditioned policy.

The second loop is critic learning. Each stored transition is relabeled with several prices drawn from a window around the current estimate. Agents compute the joint correction by averaging local log-ratios over the communication graph and then truncate it. The window and truncation level trade bias for variance. Their effect on the effective sample size is the main thing we measure.

The third loop is actor learning. Agents update one after another on the shared batch using A2PO's correction, and each update is applied at every relabeled price.

The fourth loop is the dual update. Each agent estimates the constraint violation of its own contribution from the cost critic, takes a regularized ascent step, and averages with neighbors.

Because the policy already covers nearby prices, a dual step requires no new policy learning. Fresh data is needed only to keep the cost estimate honest.

The analysis has two parts. First, we derive the variance of the relabeled critic target as a function of the price window. Under bounded policy sensitivity to $\lambda$, the log-ratio grows linearly in $|\lambda'-\lambda_0|$, so the variance grows exponentially in window width. This should yield an optimal window that shrinks as dual steps shrink. Second, on the hardness counterexample, we test whether episode-level price mixing reaches the occupancy-measure optimum. We also bound the extra constraint violation caused by incomplete agreement on the price, as a function of the spectral gap of the averaging matrix and the number of averaging rounds.

Baselines

The naive reference point is a fixed constraint penalty: each agent trains A2PO-style on $r - c\cdot\text{violation}$ with a hand-tuned $c$. Per the Amaya-Corredor et al. paper, this already failed with exhaustive tuning on CityLearn. We include it so the cost of dual machinery is visible. It receives the same environment-step budget and a grid search over $c$ at equal total compute.

The second reference is independent Lagrangian learning without communication. Each agent keeps its own multiplier on its own share of the budget. This isolates whether exchanging prices matters under coupled dynamics, as it did under separable ones.

The strongest existing methods are centralized MAPPO-Lagrangian, run where it fits in memory, and Scal-MAPPO-L, both run on the same Safe MAMuJoCo tasks with identical networks, rollout budgets, and hyperparameter-search budgets. On the separable CityLearn task, the strongest baseline is the Amaya-Corredor state-augmented dual consensus method. Its reported figures are a cost gap of 0.2% or less against a centralized oracle and 100% constraint satisfaction. Beating it there means matching those numbers while using fewer total environment steps across training. Since it trains offline, we count its offline steps. For Safe MAMuJoCo, no reported numerical result was found on Lacuna for Scal-MAPPO-L or MAPPO-L; we will rerun both. Beating them means reaching their final feasible reward in at least 2x fewer environment steps with no higher violation rate, or surpassing their final feasible reward under a global budget.

Three ablations isolate the key ingredient:

  1. No relabeling. The price-conditioned policy is trained only on transitions at their collection price. This is the decisive ablation: it separates the gain from conditioning on the price from the gain from reusing samples across prices.
  2. Uncorrected relabeling. Prices are relabeled but the log-consensus importance correction is dropped. This tests whether coupled dynamics actually require the correction.
  3. Fixed price within the window. The price is held constant across episodes instead of sampled. This isolates the mixing effect on the duality gap.

Why not just…?

Why not just use centralized MAPPO-Lagrangian with one global multiplier? At 6–12 agents this is a real threat. Scal-MAPPO-L found it competitive and occasionally worse, attributing the deficit to noise from distant agents in the centralized critic. The Amaya-Corredor et al. paper reports that centralized critics max out at a few dozen agents. A centralized multiplier still moves the reward target, so it pays the same relearning cost. We will compare learning curves at 6, 12, and larger agent counts on a coupled task. If MAPPO-Lagrangian matches our sample efficiency at small scale, we will report that honestly. The claim then narrows to the regime where centralization is unavailable.

Why not just tune a fixed penalty or shape the reward? Evidence in the file is consistently negative. Fixed penalties produced infeasible rollouts on CityLearn, and fixed-weight versions of IEC (IEC: When Information-Driven Exploration Meets Spectral Consensus via Primal–Dual Reward Regularization in Decentralized Multi-Agent RL) collapsed in GridWorld MultiRoom. A fixed penalty also cannot represent the right trade-off when the budget binds differently across states. The penalty baseline will show whether this holds under coupled dynamics.

Why not just average a scalar multiplier by gossip and run ordinary primal-dual updates? This is the obvious combination, and our "no relabeling" ablation is close to it. We predict it needs fresh rollouts after each multiplier move and oscillates, as the delayed dual subgradient work Decentralized Multi-Agent Optimization via Dual Decomposition observed. We also predict it stalls at the $\Omega(\Delta)$ floor. If it matches our method in samples to feasibility, relabeling adds nothing and the proposal fails.

Why not just share a random seed to mix policies, without any dual variable? A shared seed supplies the randomness but not the mixing weights. Which mixture satisfies the budget is exactly what the price determines. We will check this directly on the counterexample. A seed-only mixture with tuned weights is an extra comparison there.

Proposed Experiments

Duality gap test. Using the analytic counterexample from Chen et al., where $\Delta = 3/4$, we measure the gap between achieved feasible return and the occupancy-measure optimum. We compare standard primal-dual, the fixed-price ablation, and episode-level price mixing. A decisive success is driving the gap near zero with mixing while the fixed-price variant stays near $\Omega(\Delta)$.

Sample-efficiency test. On the synthetic distributed MDPs from Suttle et al. (10 agents, 20 states, binary actions, 10-dimensional linear features), we add a global cost budget and make transitions depend on joint actions. We plot environment steps to an ε-feasible, ε-optimal policy against relabeling window width. This tests the predicted interior optimum for the window.

Global-budget robotics test. We use Safe Coupled HalfCheetah (12 agents) and Safe ManyAgent Ant (6, 8, and 12 agents), adding a global aggregate actuation-energy budget that every joint draws on. This is where spatial decay fails by construction, and we compare against Scal-MAPPO-L and MAPPO-L.

Separable sanity check. On CityLearn we verify that we do not lose ground to the Amaya-Corredor et al. method on its home turf.

Metrics. Across all benchmarks we report environment steps to feasibility, final feasible reward, violation rate across seeds, averaging rounds per step, and effective sample size of relabeled batches.

Kill criterion. If, on the coupled tasks, the no-relabeling ablation is within 20% of the full method in steps to feasibility, the core claim is false.