Who Bears the Burden? Learning Responsibility for Shared Constraints in Multi-Agent Reinforcement Learning

Xiaoyang Cao; Jingqi Li; Zhe Fu; Alexandre M. Bayen

cs.LGOct 5, 2026

Who Bears the Burden? Learning Responsibility for Shared Constraints in Multi-Agent Reinforcement Learning

Authors: Xiaoyang Cao, Jingqi Li, Zhe Fu, Alexandre M. Bayen

Organizations: Massachusetts Institute of Technology · The University of Texas at Austin · Stanford University · University of California, Berkeley

Abstract

When multiple agents share a cost budget, a common Lagrange multiplier can enforce the aggregate constraint but does not determine how its penalty should be allocated across agents. Uniform penalties ignore heterogeneity in the rewards agents sacrifice, while agent-specific multipliers may still rely on the same aggregate cost signal. We introduce Lagrangian Responsibility Allocation (LiRA), which learns each agent's share of a common multiplier by optimizing social welfare over a finite training horizon. The multiplier enforces the aggregate budget, while responsibility shares redistribute its influence without modifying the original rewards or constraints. For convex games under standard regularity conditions, varying these shares induces a smooth family of normalized generalized Nash equilibria in which active constraints remain at their budgets while welfare varies. To optimize responsibility before convergence, we derive a welfare gradient that accounts for both learning updates and the induced change in data distribution. Across CityLearn, MABIM, Harvest, and MetaDrive, spanning 3 to 400 agents, LiRA improves average social welfare by up to 29% over uniform and agent-specific multiplier baselines. Grid and driving costs remain within budget, inventory violations decrease, and Harvest makes more effective use of available budget.

Figures & tables

Figure 1: Overview of LiRA. (a) In the illustrated corridor scenario, uniform shares leave both robots waiting; learned shares let the robot without an urgent package yield so that the loaded robot proceeds. Both outcomes avoid collision but differ in welfare. (b) Under Theorem 1 ’s conditions, varying responsibility $\rho$ selects a smooth equilibrium family. For each active constraint $k$ , cost $C_{k}$ stays at its budget $d_{k}$ , while welfare $W$ can vary and the shared equilibrium multiplier $\lambda^{*}$ adapts to $\rho$ . (c) From checkpoint $x_{0}$ , LiRA runs $M\geq 2$ independent lookaheads of $q$ learner updates, each followed by fresh evaluation. It combines direct unrolling (DU) with sampling correction (SC) to estimate $\nabla_{\phi}V_{q}$ , update $\phi$ , and restart from $x_{0}$ .

Task $(N,K)$	Outcome	Budget	Uniform	PAL	LiRA
CityLearn $(3,1)$	Welfare ( $10^{3}$ )	–	$-16.87\pm 3.04$	$-16.87\pm 3.04$	$\mathbf{-14.51}\pm 1.66$
	Grid excess (kWh)	$28.76$	$28.44\pm 5.97$	$28.44\pm 5.97$	$28.73\pm 7.48$
MABIM $(400,2)$	Welfare ( $10^{6}$ )	–	$-596.31\pm 5.00$	$-597.27\pm 3.76$	$\mathbf{-591.36}\pm 4.48$
	Rejections $C_{1}$ ( $10^{6}$ )	$20.35$	$21.51\pm 0.25$	$21.56\pm 0.23$	$21.30\pm 0.18$
	Rejections $C_{2}$ ( $10^{3}$ )	$32.69$	$27.71\pm 2.31$	$27.54\pm 2.21$	$28.68\pm 0.90$
Harvest $(7,1)$	Welfare	–	$42.73\pm 12.22$	$44.73\pm 3.79$	$\mathbf{50.27}\pm 2.53$

Table 1: Welfare and shared costs across four tasks. Held-out mean

\pm

sample standard deviation over matched training seeds (three per task; six for MetaDrive). Costs and budgets use the units shown in each row. Bold marks the highest mean welfare.

Figure 2: Hourly temperature relative to setpoint in CityLearn. Each point averages observations at that hour in the matched 719-step seed-1102 evaluation. Uniform is dashed; LiRA is solid. Gray marks the

\pm 1^{\circ}

C comfort band, and tan the 16–18h price peak. The episode totals appear in Table 2 .

	Learned $\rho$	Electricity change (kWh)	Reward change ( $10^{3}$ )
Building 1	$0.395$	$-37.6$	$+4.43$
Building 2	$0.387$	$-32.7$	$+0.48$
Building 3	$0.218$	$-18.9$	$-0.03$

Table 2: CityLearn responsibility and episode outcomes. Seed-1102 evaluation over 719 steps. Uniform assigns

\rho=1/3

to each building; changes are LiRA minus Uniform. Reward is native building comfort reward.

Varied choice	Setting	Welfare ( $10^{3}$ )	Grid excess (kWh)
Main setting	$(2,8,0.05)$	$\mathbf{-14.51}\pm 1.66$	$28.73\pm 7.48$
Lookahead	$q=3$	$-18.13\pm 4.42$	$29.34\pm 4.67$
	$q=4$	$-19.03\pm 8.39$	$31.52\pm 4.20$
Replicates	$M=4$	$-16.02\pm 4.05$	$28.91\pm 4.02$
	$M=12$	$-16.68\pm 3.87$	$29.12\pm 2.38$
Step size	$\eta_{\rho}=0.025$	$-20.67\pm 7.14$	$32.97\pm 5.65$

Table 3: CityLearn local search around the main setting. Each row changes one parameter from

(q,M,\eta_{\rho})=(2,8,0.05)

. Welfare and grid excess are mean

\pm

sample standard deviation over three matched seeds. The grid-excess budget is

28.76

kWh.

Appendix figures & tables1 asset

Supplementary material from the paper’s appendix.

Appendix

	Cold excess	$\Delta R_{\rm cold}$	$\Delta R_{\rm warm}$	$\Delta R_{\mathrm{in\text{-}band}}$
	( ∘ C $\cdot$ steps)
Building 1	586.1	+4528.01	$-102.80$	+6.55
Building 2	214.5	+813.09	$-340.49$	+6.26
Building 3	70.2	+159.58	$-205.55$	+11.62

Appendix

Table 4: CityLearn comfort components in the matched seed-1102 episode. Cold excess is measured under Uniform; reward changes are LiRA minus Uniform.

Explore similar work

May 28, 2026cs.LG

Scalable Constrained Multi-Agent Reinforcement Learning via State Augmentation and Consensus for Separable Dynamics

We present a distributed approach for constrained Multi-Agent Reinforcement Learning (MARL) that combines state-augmented policy learning with distributed consensus over dual variables. Our method targets systems where agents have separable dynamics but must coordinate to satisfy global resource constraints, a setting in which, as we demonstrate empirically, independent learning fails to produce feasible solutions because agents cannot determine appropriate individual contributions toward collective constraint satisfaction. The key technical contribution is showing that lightweight neighbor-to-neighbor consensus over Lagrange multipliers suffices for globally coordinated constraint enforcement while preserving the scalability of independent training. Each agent learns a single augmented policy offline, conditioned on both its local state and a dual variable encoding constraint feedback. During execution, agents reach agreement on this dual variable through local communication alone. We prove that under mild connectivity assumptions, the consensus error among agents' multipliers is bounded, and show that this translates to a bounded constraint violation that decreases with graph connectivity and the number of consensus rounds. Unlike centralized training with decentralized execution (CTDE) approaches, whose complexity grows at least quadratically with agent count, our method scales linearly in both training and execution. Experiments on smart grid demand response demonstrate that consensus coordination is \emph{essential for feasibility}: without it, agents satisfy grid capacity constraints only by indefinitely postponing demand, a degenerate non-solution. With consensus, agents converge to a shared dual variable and satisfy both grid constraints and demand fulfillment, scaling to thousands of agents while CTDE baselines are limited to dozens.

Santiago Amaya-Corredor, Miguel Calvo-Fullana, Anders Jonsson

Department of Engineering, University Pompeu Fabra

Multi-Agent Reinforcement Learning Structural Constraints Scalability

Ask PDF

Jun 1, 2026cs.AI

Coordination Graphs for Constrained Multi-Agent Reinforcement Learning

Constrained Multi-agent reinforcement learning (CMARL) faces two intertwined challenges: the joint action space grows exponentially with the number of agents, and additional requirements couple agents in ways that reward structure alone does not capture. We introduce Coordination Graphs for Constrained Multi-Agent Reinforcement Learning (CG-CMARL), a framework that addresses both challenges by combining coordination graphs with Lagrangian duality. The system decomposes the joint problem into pairwise regions, each served by a set of shared Q-functions, one for the primary objective and one for each of the constraints, so that the number of learned models is independent of the number of agents. At execution time, Max-Sum message passing coordinates actions across the factor graph, while a Lagrangian multiplier controls the objective--constraint tradeoff, allowing a single trained model to trace a Pareto front without retraining. We provide convergence guarantees under mild conditions, together with a compositional error bound that decomposes into separate interpretable sources, each traceable to a specific design choice and independently controllable. Experiments on cooperative navigation tasks (where teams of up to 10 agents must coordinate to reach target positions while satisfying pairwise constraints) show that our method produces Pareto fronts dominating established baselines trained at fixed reward-shaping ratios, while scaling to team sizes where centralized approaches become intractable.

Santiago Amaya-Corredor, Miguel Calvo-Fullana, Anders Jonsson

Department of Engineering, Universitat Pompeu Fabra, Barcelona, Spain

Multi-Agent Reinforcement Learning Coordination

Ask PDF

Apr 3, 2026cs.LG

Marginal-Contribution Policy Gradients under Filtered Feedback for Multi-Agent LLMs

We develop a unified treatment of credit assignment for RL training in multi-agent LLM systems. We show that observed reward alone cannot distinguish an agent that determines it from one that never affects it, and that standard shared-reward training performs exact gradient ascent on each agent's private utility rather than system performance. Moreover, we prove no single scalar per agent can consistently account for joint performance once agents interact. We thus develop the unique background-dependent notion of marginal contribution satisfying natural consistency requirements. From it we derive gradient-correct marginal contribution training signals, identify them from filtered feedback, and optimally allocate a budget of exact counterfactual evaluations against learned-signal error. Instantiated in GRPO, our signal improves routed GSM8K accuracy over winner-take-all training at no extra generation cost.

Elai Ben-Gal, Stela Tong

Department of Mathematics Stanford University · Graduate School of Business Stanford University

Credit Assignment Multi-Agent Large Language Model Systems Policy Gradient Feedback Gradient Descent

Ask PDF