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

# Scalable Constrained Multi-Agent Reinforcement Learning via State Augmentation and Consensus for Separable Dynamics
Source: [https://arxiv.org/html/2605.30461](https://arxiv.org/html/2605.30461)
Santiago Amaya\-Corredorsantiagoesteban\.amaya@upf\.edu Department of Engineering University Pompeu FabraMiguel Calvo\-Fullanamiguel\.calvo@upf\.edu Department of Engineering University Pompeu FabraAnders Jonssonanders\.jonsson@upf\.edu Department of Engineering University Pompeu Fabra

###### Abstract

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*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\.

## 1Introduction

In recent years, reinforcement learning \(RL\) has achieved significant success in solving diverse and complex decision\-making tasks\(Brown and Sandholm,[2019](https://arxiv.org/html/2605.30461#bib.bib49); Orr and Dutta,[2023](https://arxiv.org/html/2605.30461#bib.bib53); Silveret al\.,[2017](https://arxiv.org/html/2605.30461#bib.bib24)\)\. Many of these successes involve multiple agents and can be characterized as multi\-agent RL \(MARL\)\. Generally, MARL addresses a sequential problem where a set of autonomous agents make decisions and interact in a shared environment to maximize a reward\. However, MARL problems can quickly become intractable as the number of agents increases, since the number of possible interactions and the space of possible states can grow exponentially in the number of agents\. Moreover, as all agents navigate and learn simultaneously, the environment may become non\-stationary, invalidating many of the single\-agent RL assumptions\. In realistic scenarios, conflicting objectives often need to be balanced to achieve satisfactory solutions\. This issue is exacerbated when increasing the number of autonomous agents, whose specific goals are not commonly aligned\. Finding optimal strategies in multi\-agent systems \(MAS\) usually require at least some level of coordination and communication\.

Our work addresses distributed systems where agents have separable dynamics but must coordinate to satisfy global operational constraints\. While this assumption is restrictive compared to general MARL with coupled dynamics, it enables linear scaling in both training and execution, making our approach practical for hundreds or thousands of agents\. The setting remains genuinely multi\-agent as agents must coordinate through consensus to satisfy global constraints\. This structure naturally arises in infrastructure management \(e\.g\., building thermostats, EV chargers\) where local controllers make independent decisions but must respect system\-wide limits \(e\.g\., power grid capacity\)\. When agents share the same MDP, we only need to train one policy for all agents, significantly reducing complexity\. The multi\-agent coordination occurs through consensus on a dual variable during execution\. Our Constrained MARL \(CMARL\) framework has each agent maximize a primary reward while adhering to a global average constraint on a secondary reward, with the constraint acting as the coupling mechanism\.

Agents communicate only with immediate neighbors in the network, reflecting realistic constraints where global broadcast is infeasible\. Through local communication, agents share dual variables to achieve consensus dynamically\. Crucially, we demonstrate empirically that this coordination is not merely beneficial but*necessary*: without consensus, independently\-trained agents cannot distinguish between feasible demand management and trivial constraint satisfaction through indefinite demand postponement\. The dual variable consensus mechanism is what transforms independently\-trained policies into a collectively feasible solution\. We develop a novel CMARL algorithm and validate it on smart grid management\(Dileep,[2020](https://arxiv.org/html/2605.30461#bib.bib54)\), optimizing energy distribution while satisfying operational constraints\. Our experiments demonstrate scalability across different network configurations with varying complexity and agent heterogeneity\. The contributions of this paper are threefold:

1. 1\.A distributed consensus mechanism for constrained MARL with separable dynamics\.We integrate distributed consensus over Lagrange multipliers with state\-augmented constrained RL\. We prove bounded consensus error under mild connectivity assumptions and show that this implies bounded constraint violation through a Lipschitz sensitivity argument\. This enables global constraint coordination through local communication alone, without centralized critics or joint state observations\.
2. 2\.Linear scalability in both training and execution\.By exploiting problem separability for policy learning and lightweight consensus for coordination, our method scales to 1000 agents while CTDE approaches are limited to tens of agents due to centralized critic requirements\.
3. 3\.Empirical evidence that consensus coordination is necessary for feasibility\.On smart grid economic dispatch, we show that the same independently\-trained policies produce fundamentally different outcomes, feasible versus infeasible, depending solely on whether consensus is enabled\. We further validate the approach against a centralized oracle, demonstrating that distributed consensus achieves equivalent constraint satisfaction and cost \(<0\.2%<\\\!0\.2\\%gap\)\.

## 2Related Work

Constrained Reinforcement Learning\.Constrained RL formulates objectives with side constraints, typically solved via Lagrangian methods\(Altman,[2021](https://arxiv.org/html/2605.30461#bib.bib3); Borkar,[2005](https://arxiv.org/html/2605.30461#bib.bib25)\)\. We distinguish two paradigms:*safe RL*ensures per\-step constraint satisfaction\(Achiamet al\.,[2017](https://arxiv.org/html/2605.30461#bib.bib21); Chowet al\.,[2019](https://arxiv.org/html/2605.30461#bib.bib5); Achiam and Amodei,[2019](https://arxiv.org/html/2605.30461#bib.bib2)\), while*average\-constrained RL*permits temporary violations if long\-term averages stay within bounds\(Lianget al\.,[2018](https://arxiv.org/html/2605.30461#bib.bib13); Paternainet al\.,[2022](https://arxiv.org/html/2605.30461#bib.bib48)\)\. The latter suits resource management where momentary spikes are acceptable\. Standard Lagrangian methods can fail to produce feasible policies when the relationship between dual variables and constraint satisfaction is complex\. State augmentation\(Calvo\-Fullanaet al\.,[2024](https://arxiv.org/html/2605.30461#bib.bib19)\)addresses this by incorporating the dual variable into the state representation, enabling policies that adapt their behavior to the current level of constraint pressure\. Our work extends state augmentation from the single\-agent to the multi\-agent setting through distributed consensus on the shared dual variable; concurrent multi\-agent state\-augmentation work\(Agorioet al\.,[2024](https://arxiv.org/html/2605.30461#bib.bib23)\)addresses assignment problems\.

Cooperative MARL\.Centralized training with decentralized execution \(CTDE\) has emerged as the dominant paradigm for cooperative MARL\(Kraemer and Banerjee,[2016](https://arxiv.org/html/2605.30461#bib.bib12)\), encompassing value decomposition methods\(Sunehaget al\.,[2018](https://arxiv.org/html/2605.30461#bib.bib56); Rashidet al\.,[2018](https://arxiv.org/html/2605.30461#bib.bib18); Wanget al\.,[2021](https://arxiv.org/html/2605.30461#bib.bib51)\)and policy gradient approaches with centralized critics\(Loweet al\.,[2017](https://arxiv.org/html/2605.30461#bib.bib14); Yuet al\.,[2022](https://arxiv.org/html/2605.30461#bib.bib60)\), though both scale poorly with agent count\. Recent work has questioned whether CTDE provides benefits over independent learning in many settings\(de Wittet al\.,[2020](https://arxiv.org/html/2605.30461#bib.bib30)\), though independent methods cannot handle global constraints without additional mechanisms\. For comprehensive coverage, we refer to recent surveys\(Cheruiyotet al\.,[2025](https://arxiv.org/html/2605.30461#bib.bib39); Low and Zhou,[2025](https://arxiv.org/html/2605.30461#bib.bib42); Hadyet al\.,[2025](https://arxiv.org/html/2605.30461#bib.bib35)\)and the textbook byAlbrechtet al\.\([2024](https://arxiv.org/html/2605.30461#bib.bib22)\)\. Our approach differs fundamentally: rather than centralizing during training, we train policies independently and coordinate only through dual variable consensus during execution\.

Networked and Scalable MARL\.Several works achieve scalability by exploiting network structure\.Zhanget al\.\([2018](https://arxiv.org/html/2605.30461#bib.bib61)\)develop fully decentralized MARL for networked agents, establishing convergence for policy gradient methods with local communication\.Quet al\.\([2020](https://arxiv.org/html/2605.30461#bib.bib52)\)propose scalable multi\-agent RL for networked systems with average reward objectives, achieving linear scaling through separable dynamics but without handling constraints\.Chuet al\.\([2020](https://arxiv.org/html/2605.30461#bib.bib28)\)develop a multi\-agent RL framework for networked system control with localized rewards\. In the power systems domain,Chenet al\.\([2022](https://arxiv.org/html/2605.30461#bib.bib26)\)develop PowerNet for scalable grid control,Fenget al\.\([2024](https://arxiv.org/html/2605.30461#bib.bib32)\)address stability\-constrained RL for decentralized voltage control, andMaiet al\.\([2024](https://arxiv.org/html/2605.30461#bib.bib44)\)study multi\-agent RL for fast\-timescale demand response\. More recently,Wanget al\.\([2025](https://arxiv.org/html/2605.30461#bib.bib41)\)propose distributed MARL for multi\-objective microgrid dispatch using actor\-critic with multiple critics, achieving coordination through neighbor\-to\-neighbor communication; however, their method targets Pareto optimization without explicit global constraint handling\. While these works demonstrate scalability through network structure, none provides mechanisms for satisfying global constraints that couple agents’ decisions\.

Constrained Multi\-Agent RL\.Recent work addresses constraints in MARL with coupled dynamics\.Luet al\.\([2021](https://arxiv.org/html/2605.30461#bib.bib43)\)propose Safe Dec\-PG for distributed constrained MDPs, achieving convergence but with computational complexity limiting experiments to 5 agents\.Guet al\.\([2021](https://arxiv.org/html/2605.30461#bib.bib33)\)introduce Multi\-Agent Constrained Policy Optimization \(MACPO\), extending TRPO\-Lagrangian to multi\-agent settings\.Yinget al\.\([2023](https://arxiv.org/html/2605.30461#bib.bib59)\)develop a primal\-dual actor\-critic method usingκ\\kappa\-hop truncation, trading off constraint coupling accuracy for scalability\.Zhanget al\.\([2024](https://arxiv.org/html/2605.30461#bib.bib62)\)introduce Scal\-MAPPO\-L with local policy optimization, though they note exponential growth in state\-action space with neighborhood size \(experiments limited to 12 agents\)\. On the theoretical front,Chenet al\.\([2024](https://arxiv.org/html/2605.30461#bib.bib27)\)establish hardness results showing constrained cooperative MARL is computationally intractable in general settings, whileDinget al\.\([2023](https://arxiv.org/html/2605.30461#bib.bib1)\)provide a generalized Lagrangian primal\-dual scheme with provable sample\-efficient convergence\. Importantly, these methods target*safety constraints*requiring per\-step satisfaction under*coupled dynamics*where agents’ transitions directly affect each other\. While more general than our setting, this generality comes at computational cost that limits scalability to tens of agents\. We target*average constraint satisfaction*with*separable dynamics*—assumptions satisfied in many infrastructure management problems—enabling linear scaling demonstrated up to 1000 agents\.

Distributed Optimization and Consensus in RL\.Our dual consensus mechanism builds on distributed optimization with coupled constraints\(Nedic and Ozdaglar,[2009](https://arxiv.org/html/2605.30461#bib.bib46); Olfati\-Saberet al\.,[2007](https://arxiv.org/html/2605.30461#bib.bib17)\), with recent extensions to RL settings\(Yarmoshiket al\.,[2024](https://arxiv.org/html/2605.30461#bib.bib58); Wanget al\.,[2024](https://arxiv.org/html/2605.30461#bib.bib57)\)\. Closely related,Ohet al\.\([2025](https://arxiv.org/html/2605.30461#bib.bib47)\)develop consensus\-based actor\-critic for network optimization, where agents share*local rewards*with neighbors to approximate the global return without centralized training\. Our consensus operates on a fundamentally different quantity:*dual variables*\(Lagrange multipliers\) rather than rewards\. In reward\-consensus methods\(Ohet al\.,[2025](https://arxiv.org/html/2605.30461#bib.bib47); Wanget al\.,[2025](https://arxiv.org/html/2605.30461#bib.bib41)\), each agent’s feasibility is independent, whereas our global constraint∑iV1i​\(πi\)≤c\\sum\_\{i\}V\_\{1\}^\{i\}\(\\pi^\{i\}\)\\leq ccouples agents’ feasible sets\. This requires state\-augmented policiesπi​\(s,λ\)\\pi^\{i\}\(s,\\lambda\)that respond to the evolving multiplier—a design absent in reward\-consensus methods\. As we demonstrate in Section[7\.2](https://arxiv.org/html/2605.30461#S7.SS2), this coordination is necessary for feasibility\.

Neural Controllers for Power Systems\.Cuiet al\.\([2023](https://arxiv.org/html/2605.30461#bib.bib29)\)propose structured neural\-PI controllers using strictly convex neural networks, achieving stability and output tracking through equilibrium\-independent passivity—a model\-based approach requiring knowledge of system dynamics\.Fenget al\.\([2023](https://arxiv.org/html/2605.30461#bib.bib31)\)construct decentralized RL\-based controllers for voltage regulation, combining a transient neural policy with a steady\-state gradient flow optimizer\. While both address power systems with distributed controllers, they focus on*stability and tracking*rather than*constraint satisfaction*, embedding constraints in the controller architecture rather than handling them explicitly through Lagrangian duality\. The approaches are complementary\.

Positioning Our Work\.Table[1](https://arxiv.org/html/2605.30461#S2.T1)summarizes how our approach compares to prior methods across three dimensions: constraint type, dynamics structure, and scalability\. Our key distinction is the combination of \(i\) separable dynamics enabling independent policy training, \(ii\) average rather than per\-step constraint satisfaction, and \(iii\) distributed consensus over dual variables for coordination\. This combination enables linear scaling—demonstrated up to 1000 agents—while methods handling coupled dynamics\(Luet al\.,[2021](https://arxiv.org/html/2605.30461#bib.bib43); Yinget al\.,[2023](https://arxiv.org/html/2605.30461#bib.bib59); Zhanget al\.,[2024](https://arxiv.org/html/2605.30461#bib.bib62)\)are limited to tens of agents, and methods achieving scalability through separable structure\(Quet al\.,[2020](https://arxiv.org/html/2605.30461#bib.bib52); Chuet al\.,[2020](https://arxiv.org/html/2605.30461#bib.bib28)\)lack explicit constraint handling\. For the important class of infrastructure management problems satisfying our assumptions, we achieve unprecedented scale with bounded constraint violation guarantees, coordinated through lightweight neighbor\-to\-neighbor communication\.

Table 1:Comparison of constrained and scalable MARL methods\. Scalability indicates computational complexity: exponential in agents \(nn\), exponential in communication radius \(κ\\kappa\), or linear\. Methods marked with†\\daggerhandle coupled dynamics but at higher computational cost\.MethodConstraintsDynamicsScalabilityMax Agents*Scalable \(separable/networked dynamics, no global constraints\)*Quet al\.\([2020](https://arxiv.org/html/2605.30461#bib.bib52)\)NoneNetworkedLinear25Chuet al\.\([2020](https://arxiv.org/html/2605.30461#bib.bib28)\)NoneNetworkedLinear28Chenet al\.\([2022](https://arxiv.org/html/2605.30461#bib.bib26)\)NoneNetworkedLinear40Fenget al\.\([2024](https://arxiv.org/html/2605.30461#bib.bib32)\)Stability \(local\)NetworkedLinear123*Constrained \(coupled dynamics, limited scalability\)†*Luet al\.\([2021](https://arxiv.org/html/2605.30461#bib.bib43)\)Safety \(per\-step\)CoupledExp\. innn5Guet al\.\([2021](https://arxiv.org/html/2605.30461#bib.bib33)\)Safety \(per\-step\)CoupledExp\. innn8Yinget al\.\([2023](https://arxiv.org/html/2605.30461#bib.bib59)\)Safety \(per\-step\)CoupledExp\. inκ\\kappa20Zhanget al\.\([2024](https://arxiv.org/html/2605.30461#bib.bib62)\)Safety \(per\-step\)CoupledExp\. inκ\\kappa12OursAverage \(global\)SeparableLinear1000
## 3Problem Formulation

Typically, CMARL is studied using the Markov Games framework\(Littman,[1994](https://arxiv.org/html/2605.30461#bib.bib15)\), an extension of game theory to environments where the dynamics can be modeled using a Markov Decision Process \(MDP\)\. Markov games model interactions among multiple agents whose decisions influence a shared environment\. In our distributed constrained setting, the Markov game is defined by the tuple⟨N,\{Si\}i=1N,\{Ai\}i=1N,\{Pi\}i=1N,\{r0i\}i=1N,\{r1i\}i=1N⟩\\langle N,\\\{S^\{i\}\\\}\_\{i=1\}^\{N\},\\\{A^\{i\}\\\}\_\{i=1\}^\{N\},\\\{P^\{i\}\\\}\_\{i=1\}^\{N\},\\\{r\_\{0\}^\{i\}\\\}\_\{i=1\}^\{N\},\\\{r\_\{1\}^\{i\}\\\}\_\{i=1\}^\{N\}\\rangle, whereNNis the number of agents,Si⊂ℝmS^\{i\}\\subset\\mathbb\{R\}^\{m\}andAi⊂ℝdA^\{i\}\\subset\\mathbb\{R\}^\{d\}are compact sets denoting the states and actions of agentii, withS:=S1×⋯×SNS:=S^\{1\}\\times\\cdots\\times S^\{N\}andA:=A1×⋯×ANA:=A^\{1\}\\times\\cdots\\times A^\{N\}denoting the sets of joint states and actions\. The joint state transition probability is given byP:S×A→Δ​\(S\)P:S\\times A\\rightarrow\\Delta\(S\), with each individual agent’s transition given byPi:Si×Ai→Δ​\(Si\)P^\{i\}:S^\{i\}\\times A^\{i\}\\rightarrow\\Delta\(S^\{i\}\), whereΔ​\(S\)\\Delta\(S\)is the probability simplex onSS\. We further denote byr0i:Si×Ai→ℝr\_\{0\}^\{i\}:S^\{i\}\\times A^\{i\}\\rightarrow\\mathbb\{R\}the reward function for the main objective of agentii, and byr1i:Si×Ai→ℝr\_\{1\}^\{i\}:S^\{i\}\\times A^\{i\}\\rightarrow\\mathbb\{R\}the reward function for the secondary objective subject to a constraint, with global counterparts defined asr0:S×A→ℝr\_\{0\}:S\\times A\\rightarrow\\mathbb\{R\}andr1:S×A→ℝr\_\{1\}:S\\times A\\rightarrow\\mathbb\{R\}\. At timett, given a joint statest=\(st1,…,stN\)s\_\{t\}=\(s^\{1\}\_\{t\},\\ldots,s^\{N\}\_\{t\}\)and actionat=\(at1,…,atN\)a\_\{t\}=\(a^\{1\}\_\{t\},\\ldots,a^\{N\}\_\{t\}\), the system transitions to a new statest\+1=\(st\+11,…,st\+1N\)s\_\{t\+1\}=\(s^\{1\}\_\{t\+1\},\\ldots,s^\{N\}\_\{t\+1\}\)with probabilityP​\(st\+1\|st,at\)P\(s\_\{t\+1\}\|s\_\{t\},a\_\{t\}\)\. The Markov property ensures that the system dynamics only depend on the last state and action, i\.e\.P​\(st\+1\|s0,a0,…,st,at\)=P​\(st\+1\|st,at\)P\(s\_\{t\+1\}\|s\_\{0\},a\_\{0\},\\ldots,s\_\{t\},a\_\{t\}\)=P\(s\_\{t\+1\}\|s\_\{t\},a\_\{t\}\)\. We consider a scenario where agents maximize a primary rewardr0r\_\{0\}subject to a global resource constraint on a secondary quantityr1r\_\{1\}\. Specifically, we aim to maximize the long\-term average ofr0​\(st,at\)r\_\{0\}\(s\_\{t\},a\_\{t\}\), while ensuring that the long\-term average ofr1​\(st,at\)r\_\{1\}\(s\_\{t\},a\_\{t\}\)does not exceed a given upper boundcc\.111For simplicity, we restrict ourselves to the single constraint case, though the results generalize to multiple constraints\.This constrained optimization problem can be expressed as

maximize𝜋\\displaystyle\\underset\{\\pi\}\{\\operatorname\{maximize\}\}\\enskiplimT→∞1T​𝔼s,a∼π​\[∑t=0Tr0​\(st,at\)\]\\displaystyle\\lim\_\{T\\rightarrow\\infty\}\\frac\{1\}\{T\}\\mathbb\{E\}\_\{s,a\\sim\\pi\}\\left\[\\sum\_\{t=0\}^\{T\}r\_\{0\}\(s\_\{t\},a\_\{t\}\)\\right\]\(1a\)subject​to\\displaystyle\\operatorname\{subject\\ to\}\\enskiplimT→∞1T​𝔼s,a∼π​\[∑t=0Tr1​\(st,at\)\]≤c\.\\displaystyle\\lim\_\{T\\rightarrow\\infty\}\\frac\{1\}\{T\}\\mathbb\{E\}\_\{s,a\\sim\\pi\}\\left\[\\sum\_\{t=0\}^\{T\}r\_\{1\}\(s\_\{t\},a\_\{t\}\)\\right\]\\leq c\.\(1b\)This is a multi\-agent centralized problem, which is often impractical due to its poor scalability\. Specifically, we are interested in problems that can be decomposed into distributed problems\. Formally, we consider scenarios satisfying the following assumptions\.

###### Assumption 3\.1\(Independent Policies\)\.

Each agentiiselects an action taking into account only its own local state\. Namely,π​\(at\|st\)=∏n=1Nπn​\(atn\|stn\)\\pi\(a\_\{t\}\|s\_\{t\}\)=\\prod\_\{n=1\}^\{N\}\\pi^\{n\}\(a^\{n\}\_\{t\}\|s^\{n\}\_\{t\}\)\.

###### Assumption 3\.2\(Separable Dynamics\)\.

The actions of one agent do not affect the states of others\. That is, state transitions are given byP​\(st\+1\|st,at\)=∏i=1NPi​\(st\+1i\|sti,ati\)P\(s\_\{t\+1\}\|s\_\{t\},a\_\{t\}\)=\\prod\_\{i=1\}^\{N\}P^\{i\}\(s^\{i\}\_\{t\+1\}\|s^\{i\}\_\{t\},a^\{i\}\_\{t\}\)\.

###### Assumption 3\.3\(Summable Rewards\)\.

The global reward can be decomposed as the sum of individual rewards, i\.e\.r0​\(st,at\)=∑n=1Nr0n​\(sti,ati\)r\_\{0\}\(s\_\{t\},a\_\{t\}\)=\\sum\_\{n=1\}^\{N\}r\_\{0\}^\{n\}\(s^\{i\}\_\{t\},a^\{i\}\_\{t\}\)andr1​\(st,at\)=∑n=1Nr1n​\(sti,ati\)r\_\{1\}\(s\_\{t\},a\_\{t\}\)=\\sum\_\{n=1\}^\{N\}r\_\{1\}^\{n\}\(s^\{i\}\_\{t\},a^\{i\}\_\{t\}\)\.

The first assumption allows each agent to operate based solely on local information, the second assumption ensures that the interactions of the agents are structured in a non\-interfering manner, and the third assumption ensures that global objectives can be achieved through local decisions\. This set of assumptions allows for the problem to be rewritten in the following form:

maxπ1,…,πN\\displaystyle\\underset\{\\pi^\{1\},\\ldots,\\pi^\{N\}\}\{\\max\}∑i=1NlimT→∞1T​𝔼si,ai∼πi​\[∑t=0Tr0i​\(sti,ati\)\]\\displaystyle\\sum\_\{i=1\}^\{N\}\\lim\_\{T\\rightarrow\\infty\}\\frac\{1\}\{T\}\\mathbb\{E\}\_\{s^\{i\},a^\{i\}\\sim\\pi^\{i\}\}\\left\[\\sum\_\{t=0\}^\{T\}r\_\{0\}^\{i\}\(s^\{i\}\_\{t\},a^\{i\}\_\{t\}\)\\right\]\(2a\)s\.t\.\\displaystyle\\operatorname\{s\.t\.\}∑i=1NlimT→∞1T​𝔼si,ai∼πi​\[∑t=0Tr1i​\(sti,ati\)\]≤c\.\\displaystyle\\sum\_\{i=1\}^\{N\}\\lim\_\{T\\rightarrow\\infty\}\\frac\{1\}\{T\}\\mathbb\{E\}\_\{s^\{i\},a^\{i\}\\sim\\pi^\{i\}\}\\left\[\\sum\_\{t=0\}^\{T\}r\_\{1\}^\{i\}\(s^\{i\}\_\{t\},a^\{i\}\_\{t\}\)\\right\]\\leq c\.\\hskip\-4\.30554pt\\hskip\-4\.30554pt\(2b\)By defining value functions as the long\-term average of each reward,

Vji​\(πi\)≜limT→∞1T​𝔼si,ai∼πi​\[∑t=0Trji​\(sti,ati\)\],\\displaystyle V\_\{j\}^\{i\}\(\\pi^\{i\}\)\\triangleq\\lim\_\{T\\rightarrow\\infty\}\\frac\{1\}\{T\}\\mathbb\{E\}\_\{s^\{i\},a^\{i\}\\sim\\pi^\{i\}\}\\left\[\\sum\_\{t=0\}^\{T\}r\_\{j\}^\{i\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)\\right\],\(3\)we can then rewrite the maximization problem in equation[2](https://arxiv.org/html/2605.30461#S3.E2)in the following more concise manner:

maximizeπ1,…,πN​∑i=1NV0i​\(πi\)​subject​to​∑i=1NV1i​\(πi\)≤c\.\\displaystyle\\underset\{\\pi^\{1\},\\ldots,\\pi^\{N\}\}\{\\operatorname\{maximize\}\}\\enskip\\sum\_\{i=1\}^\{N\}V\_\{0\}^\{i\}\(\\pi^\{i\}\)\\enskip\\operatorname\{subject\\ to\}\\enskip\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\(\\pi^\{i\}\)\\leq c\.\(4\)The resulting formulation now exhibits a certain degree of separability across agents, with each agent maximizing its own policy with respect to its individual value function, while still being coupled to the other agents through the global constraint\. While the separable structure might suggest independent single\-agent solutions would suffice, the global constraint in equation[4](https://arxiv.org/html/2605.30461#S3.E4)creates a critical coordination challenge: without communication, agents cannot determine appropriate individual contributions to satisfy the collective constraint\. This necessitates our consensus mechanism to coordinate the dual variables that encode constraint violation feedback\.

## 4Methodology

We begin by formulating the Lagrangian of the optimization problem in equation[4](https://arxiv.org/html/2605.30461#S3.E4)\. This involves introducing Lagrange multipliers to transform the constrained optimization problem into a form where the constraints are incorporated into the objective function as penalty terms\. Namely,

ℒ​\(π,λ\)\\displaystyle\\mathcal\{L\}\(\\pi,\\lambda\)=∑i=1NV0i​\(πi\)\+λ​\(c−∑i=1NV1i​\(πi\)\)=∑i=1N\(V0i​\(πi\)\+λ​\(cN−V1i​\(πi\)\)\),\\displaystyle=\\sum\_\{i=1\}^\{N\}V\_\{0\}^\{i\}\(\\pi^\{i\}\)\+\\lambda\\Biggl\(c\-\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\(\\pi^\{i\}\)\\Biggr\)=\\sum\_\{i=1\}^\{N\}\\Biggl\(V\_\{0\}^\{i\}\(\\pi^\{i\}\)\+\\lambda\\left\(\\frac\{c\}\{N\}\-V\_\{1\}^\{i\}\(\\pi^\{i\}\)\\right\)\\Biggr\),\(5\)whereλ∈ℝ\+\\lambda\\in\\mathbb\{R\}^\{\+\}is the Lagrange multiplier \(dual variable\) for the inequality constraint\. We rewrite the Lagrangian as individual agent components to maintain distributed formulation\. The dual problem becomes

minimize𝜆​\[∑i=1Nmaxπi⁡\(V0i​\(πi\)\+λ​\(cN−V1i​\(πi\)\)\)\]\\displaystyle\\underset\{\\lambda\}\{\\operatorname\{minimize\}\}\\Bigg\[\\sum\_\{i=1\}^\{N\}\\max\_\{\\pi^\{i\}\}\\Biggl\(V\_\{0\}^\{i\}\(\\pi^\{i\}\)\+\\lambda\\left\(\\frac\{c\}\{N\}\-V\_\{1\}^\{i\}\(\\pi^\{i\}\)\\right\)\\Biggr\)\\Bigg\]\\hskip\-4\.30554pt\(6\)
where summation and maximization are exchanged due to Assumptions[3\.1](https://arxiv.org/html/2605.30461#S3.Thmtheorem1)and[3\.2](https://arxiv.org/html/2605.30461#S3.Thmtheorem2)\. This decomposition enables independent local optimization while satisfying the global constraint\. The problem exhibits strong duality\(Paternainet al\.,[2019](https://arxiv.org/html/2605.30461#bib.bib20)\), so the optimal solution of equation[4](https://arxiv.org/html/2605.30461#S3.E4)equals the saddle\-point of equation[6](https://arxiv.org/html/2605.30461#S4.E6)\.

### 4\.1Offline independent training

The primal step of equation[6](https://arxiv.org/html/2605.30461#S4.E6)\(policy learning\) is distributable\. For a givenλ\\lambda, the problem decomposes across agents\. Defining the weighted rewardrλi​\(sti,ati\)≜r0i​\(sti,ati\)−λ​r1i​\(sti,ati\)r^\{i\}\_\{\\lambda\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)\\triangleq r\_\{0\}^\{i\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)\-\\lambda r\_\{1\}^\{i\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\), the maximization becomes

\{π⋆i​\(λ\)\}=arg​maxπ1,…,πN​∑i=1NlimT→∞1T​𝔼si,ai∼πi​\[∑t=0Trλi​\(sti,ati\)\]\.\\displaystyle\\\{\\pi^\{i\}\_\{\\star\}\(\\lambda\)\\\}=\\operatorname\*\{arg\\,max\}\_\{\\pi^\{1\},\\ldots,\\pi^\{N\}\}\\sum\_\{i=1\}^\{N\}\\lim\_\{T\\rightarrow\\infty\}\\frac\{1\}\{T\}\\mathbb\{E\}\_\{s^\{i\},a^\{i\}\\sim\\pi^\{i\}\}\\left\[\\sum\_\{t=0\}^\{T\}r\_\{\\lambda\}^\{i\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)\\right\]\.\(7\)Each agent’s primal step follows standard unconstrained RL\. However, standard dual methods can fail to produce feasible policies for CRL\(Calvo\-Fullanaet al\.,[2024](https://arxiv.org/html/2605.30461#bib.bib19)\)\. We thus learn state\-augmented policiesπi​\(λ\)\\pi^\{i\}\(\\lambda\)in augmented spaceSi×ℝ\+S^\{i\}\\times\\mathbb\{R\}\_\{\+\}that maximize equation[5](https://arxiv.org/html/2605.30461#S4.E5), instead of ordinary policies inSiS^\{i\}\. Agents independently train these policies using any standard RL method\. The trained policies handle any constraint levelccwhen coupled with our dual update mechanism\.

### 4\.2Online dual consensus

Determiningλ\\lambdaremains challenging since gradient descent on equation[5](https://arxiv.org/html/2605.30461#S4.E5)couples all agents\. Consider agents communicating over an undirected graphG=\(V,E\)G=\(V,E\), whereVVare vertices \(agents\) andE⊂N×NE\\subset N\\times Nare edges\. The neighborhood𝒩i=\{j∈V∣\(i,j\)∈E\}\\mathcal\{N\}^\{i\}=\\\{j\\in V\\mid\(i,j\)\\in E\\\}contains nodes directly connected toii\. We rewrite equation[6](https://arxiv.org/html/2605.30461#S4.E6)in distributed dual consensus form:

minimizeλ1,…,λN​∑i=1Nmaxπi⁡\(V0i​\(πi\)\+λi​\(cN−V1i​\(πi\)\)\)\\displaystyle\\hskip 2\.15277pt\\underset\{\\lambda^\{1\},\\ldots,\\lambda^\{N\}\}\{\\operatorname\{minimize\}\}\\sum\_\{i=1\}^\{N\}\\max\_\{\\pi^\{i\}\}\\Biggl\(V\_\{0\}^\{i\}\(\\pi^\{i\}\)\+\\lambda^\{i\}\\left\(\\frac\{c\}\{N\}\-V\_\{1\}^\{i\}\(\\pi^\{i\}\)\\right\)\\Biggr\)\(8a\)subject​to⁡λi=1\|𝒩i\|​∑n∈𝒩iλn,i=1,…,N\.\\displaystyle\\operatorname\{subject\\ to\}\\enskip\\lambda^\{i\}=\\frac\{1\}\{\|\\mathcal\{N\}\_\{i\}\|\}\\sum\_\{n\\in\\mathcal\{N\}^\{i\}\}\\lambda^\{n\},\\quad i=1,\\ldots,N\.\(8b\)The solution to equation[8](https://arxiv.org/html/2605.30461#S4.E8)equals that of equation[6](https://arxiv.org/html/2605.30461#S4.E6)\. Each agent holds local copyλi\\lambda^\{i\}, with neighborhood constraints ensuring consensus\. Using optimal policies from equation[7](https://arxiv.org/html/2605.30461#S4.E7), we obtain

minimizeλ1,…,λN\\displaystyle\\underset\{\\lambda^\{1\},\\ldots,\\lambda^\{N\}\}\{\\operatorname\{minimize\}\}\\enskip∑i=1N\[V0i​\(π⋆i​\(λi\)\)\+λi​\(cN−V1i​\(π⋆i​\(λi\)\)\)\]\\displaystyle\\sum\_\{i=1\}^\{N\}\\Bigl\[V\_\{0\}^\{i\}\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda^\{i\}\)\\bigr\)\+\\lambda^\{i\}\\left\(\\frac\{c\}\{N\}\-V\_\{1\}^\{i\}\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda^\{i\}\)\\bigr\)\\right\)\\Bigr\]\(9a\)subject​to\\displaystyle\\operatorname\{subject\\ to\}\\enskipλi=1\|𝒩i\|​∑n∈𝒩iλn,i=1,…,N\.\\displaystyle\\lambda^\{i\}=\\frac\{1\}\{\|\\mathcal\{N\}\_\{i\}\|\}\\sum\_\{n\\in\\mathcal\{N\}^\{i\}\}\\lambda^\{n\},\\quad i=1,\\ldots,N\.\(9b\)

### 4\.3Primal\-consensus update

To solve equation[9](https://arxiv.org/html/2605.30461#S4.E9), each agentiimaintainsλi\\lambda^\{i\}and iteratively \(i\) performs local gradient updates for constraint satisfaction and \(ii\) averages with neighbors’ variables\. With gradient step sizeα\>0\\alpha\>0and consensus step sizeϵ\>0\\epsilon\>0, agentiiupdates:

λk\+1i=λki−α​∇λi\[V0i​\(π⋆i​\(λki\)\)\+λki​\(cN−V1i​\(π⋆i​\(λki\)\)\)\]−ϵ​\(λki−λ¯ki\),\\lambda\_\{k\+1\}^\{i\}\\;=\\;\\lambda\_\{k\}^\{i\}\\;\-\\;\\alpha\\,\\nabla\_\{\\lambda^\{i\}\}\\\!\\Bigl\[V\_\{0\}^\{i\}\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda\_\{k\}^\{i\}\)\\bigr\)\\;\+\\;\\lambda\_\{k\}^\{i\}\\Bigl\(\\frac\{c\}\{N\}\\;\-\\;V\_\{1\}^\{i\}\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda\_\{k\}^\{i\}\)\\bigr\)\\Bigr\)\\Bigr\]\\;\-\\;\\epsilon\\,\\Bigl\(\\lambda\_\{k\}^\{i\}\-\\overline\{\\lambda\}\_\{k\}^\{i\}\\Bigr\),\(10\)
whereλ¯ki=∑n∈𝒩iλkn/\|𝒩i\|\\overline\{\\lambda\}\_\{k\}^\{i\}=\\sum\_\{n\\in\\mathcal\{N\}\_\{i\}\}\\lambda\_\{k\}^\{n\}/\|\\mathcal\{N\}\_\{i\}\|is the neighbor average\. The first term performs local gradient descent; the second enforces consensus\. These corrections drive allλi\\lambda^\{i\}to converge, matching the solution of equation[6](https://arxiv.org/html/2605.30461#S4.E6)\.

## 5Algorithm

Each agentiioptimizes its local policy by maximizing the Lagrangian given its current copy of the dual variableλi\\lambda^\{i\}\. To ensure that the policy appropriately accounts for constraint satisfaction, we augment each agent’s state space with the local multiplierλi\\lambda^\{i\}\. This augmentation yields a policyπ⋆i​\(sti,λti\)\\pi^\{i\}\_\{\\star\}\(s\_\{t\}^\{i\},\\lambda\_\{t\}^\{i\}\)that viewsλi\\lambda^\{i\}as part of the state, so that standard reinforcement\-learning \(RL\) algorithms can be used to learn this policy\.222In practice, many RL methods—e\.g\., policy gradient, value\-based methods—can be adapted to handle such an augmented state\.

If we have an optimal policy for a given set of multipliersπ⋆​\(s,λ\)\\pi\_\{\\star\}\(s,\\lambda\), and wecontinuously updatethese multipliers \(via[10](https://arxiv.org/html/2605.30461#S4.E10)\), then the state\-action trajectories generated by each agent satisfy the constraints in equation[2](https://arxiv.org/html/2605.30461#S3.E2)\(Calvo\-Fullanaet al\.,[2024](https://arxiv.org/html/2605.30461#bib.bib19), Theorem 1\)\. Combining these ideas, we summarize the execution in Algorithm[1](https://arxiv.org/html/2605.30461#alg1)\.

###### Theorem 5\.1\.

Suppose the local value functions satisfy

‖V1i​\(π⋆i​\(λki\)\)−1N​∑j=1NV1j​\(π⋆j​\(λkj\)\)‖≤σ,\\Bigl\\\|V\_\{1\}^\{i\}\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda^\{i\}\_\{k\}\)\\bigr\)\\;\-\\;\\frac\{1\}\{N\}\\sum\_\{j=1\}^\{N\}V\_\{1\}^\{j\}\\bigl\(\\pi^\{j\}\_\{\\star\}\(\\lambda^\{j\}\_\{k\}\)\\bigr\)\\Bigr\\\|\\;\\leq\\;\\sigma,\(11\)and letwi=\|𝒩i\|/∑j=1N\|𝒩j\|w^\{i\}=\|\\mathcal\{N\}^\{i\}\|/\\sum\_\{j=1\}^\{N\}\|\\mathcal\{N\}^\{j\}\|\. Under mild conditions on the connectivity and step sizes, the execution of Algorithm[1](https://arxiv.org/html/2605.30461#alg1)results in a bounded consensus error:

limk→∞‖λk\+1−∑i=1Nwi​λki‖≤ρℒ1−ρℒ​α​σ,\\lim\_\{k\\to\\infty\}\\Bigl\\\|\\lambda\_\{k\+1\}\\;\-\\;\\sum\_\{i=1\}^\{N\}w^\{i\}\\,\\lambda^\{i\}\_\{k\}\\Bigr\\\|\\;\\leq\\;\\frac\{\\rho^\{\\mathscr\{L\}\}\}\{1\-\\rho^\{\\mathscr\{L\}\}\}\\;\\alpha\\,\\sigma,\(12\)
whereρ\\rhoandℒ\\mathscr\{L\}relate to the graph’s spectral properties and the number of communication steps per iteration \(or partial consensus steps\)\.

Theorem[5\.1](https://arxiv.org/html/2605.30461#S5.Thmtheorem1)guarantees that agents’ local multipliers remain close to one another throughout execution\. The proof appears in Appendix[A\.1](https://arxiv.org/html/2605.30461#A1.SS1)\. The bound decreases asℒ\\mathscr\{L\}increases, indicating that additional consensus steps reduce the discrepancy among agents’ multipliers\. In practice, a smallρ\\rho\(which occurs in well\-connected graphs\) accelerates convergence, allowingℒ\\mathscr\{L\}to remain small\. For many real\-world network structures, a single consensus iteration \(ℒ=1\\mathscr\{L\}=1\) per gradient step suffices to keep the discrepancy inλi\\lambda^\{i\}below an acceptable threshold\.

A natural question is whether bounded multiplier disagreement translates into bounded constraint violation and near\-optimal performance\. We answer this affirmatively under two additional assumptions\.

###### Assumption 5\.2\(Lipschitz Sensitivity of Constraint Value\)\.

For each agentii, the mapλ↦V1i​\(π⋆i​\(λ\)\)\\lambda\\mapsto V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda\)\\bigr\)isLVL\_\{V\}\-Lipschitz onℝ\+\\mathbb\{R\}\_\{\+\}:

\|V1i​\(π⋆i​\(λ\)\)−V1i​\(π⋆i​\(λ′\)\)\|≤LV​\|λ−λ′\|,∀λ,λ′≥0,∀i\.\\bigl\|V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda\)\\bigr\)\-V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda^\{\\prime\}\)\\bigr\)\\bigr\|\\;\\leq\\;L\_\{V\}\\,\|\\lambda\-\\lambda^\{\\prime\}\|,\\qquad\\forall\\;\\lambda,\\lambda^\{\\prime\}\\geq 0,\\quad\\forall\\;i\.\(13\)

###### Assumption 5\.3\(Approximate Policy Optimality\)\.

Each agent’s learned policyπ^i​\(λ\)\\hat\{\\pi\}^\{i\}\(\\lambda\)isεapprox\\varepsilon\_\{\\mathrm\{approx\}\}\-optimal in both value functions: for allλ≥0\\lambda\\geq 0,

\|Vji​\(π^i​\(λ\)\)−Vji​\(π⋆i​\(λ\)\)\|≤εapprox,j∈\{0,1\},∀i\.\\bigl\|V\_\{j\}^\{i\}\\\!\\bigl\(\\hat\{\\pi\}^\{i\}\(\\lambda\)\\bigr\)\-V\_\{j\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda\)\\bigr\)\\bigr\|\\;\\leq\\;\\varepsilon\_\{\\mathrm\{approx\}\},\\qquad j\\in\\\{0,1\\\},\\quad\\forall\\;i\.\(14\)

Assumption[5\.2](https://arxiv.org/html/2605.30461#S5.Thmtheorem2)captures how sensitively each agent’s constraint\-relevant behavior changes with the dual variable\. It is naturally satisfied by state\-augmented neural network policies, whereλ\\lambdaenters as a continuous input to a smooth function approximator; we discuss this in detail in Appendix[B\.2](https://arxiv.org/html/2605.30461#A2.SS2)\. Assumption[5\.3](https://arxiv.org/html/2605.30461#S5.Thmtheorem3)accounts for function approximation error due to finite network capacity and finite training\.

###### Proposition 5\.4\(Primal Sensitivity to Consensus Error\)\.

Let𝛌=\(λ1,…,λN\)\\bm\{\\lambda\}=\(\\lambda^\{1\},\\dots,\\lambda^\{N\}\)be the vector of local dual variables, letλ¯=∑i=1Nwi​λi\\bar\{\\lambda\}=\\sum\_\{i=1\}^\{N\}w^\{i\}\\lambda^\{i\}denote the degree\-weighted average \(wi=\|𝒩i\|/∑j\|𝒩j\|w^\{i\}=\|\\mathcal\{N\}^\{i\}\|/\\sum\_\{j\}\|\\mathcal\{N\}^\{j\}\|\), and letλ⋆\\lambda^\{\\star\}denote the centralized dual optimum\. Suppose Assumptions[5\.2](https://arxiv.org/html/2605.30461#S5.Thmtheorem2)and[5\.3](https://arxiv.org/html/2605.30461#S5.Thmtheorem3)hold, and the consensus error satisfies‖𝛌−λ¯​1‖≤δ\\\|\\bm\{\\lambda\}\-\\bar\{\\lambda\}\\,\\mathbf\{1\}\\\|\\leq\\deltaas guaranteed by Theorem[5\.1](https://arxiv.org/html/2605.30461#S5.Thmtheorem1)\.

\(a\) Feasibility gap due to multiplier disagreement\.The aggregate constraint value under heterogeneous multipliers deviates from that under the common average multiplier by at most

\|∑i=1NV1i​\(π^i​\(λi\)\)−∑i=1NV1i​\(π⋆i​\(λ¯\)\)\|≤LV​N​δ\+N​εapprox\.\\biggl\|\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\hat\{\\pi\}^\{i\}\(\\lambda^\{i\}\)\\bigr\)\-\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\bar\{\\lambda\}\)\\bigr\)\\biggr\|\\;\\leq\\;L\_\{V\}\\sqrt\{N\}\\,\\delta\\;\+\\;N\\,\\varepsilon\_\{\\mathrm\{approx\}\}\.\(15\)
\(b\) Constraint violation bound\.If the centralized dual optimum yields a feasible solution, i\.e\.∑i=1NV1i​\(π⋆i​\(λ⋆\)\)≤c\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda^\{\\star\}\)\\bigr\)\\leq c, then the distributed solution satisfies

∑i=1NV1i​\(π^i​\(λi\)\)≤c\+LV​\(N​δ\+N​\|λ¯−λ⋆\|\)\+N​εapprox\.\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\hat\{\\pi\}^\{i\}\(\\lambda^\{i\}\)\\bigr\)\\;\\leq\\;c\\;\+\\;L\_\{V\}\\\!\\bigl\(\\sqrt\{N\}\\,\\delta\+N\\,\|\\bar\{\\lambda\}\-\\lambda^\{\\star\}\|\\bigr\)\\;\+\\;N\\,\\varepsilon\_\{\\mathrm\{approx\}\}\.\(16\)
\(c\) Optimality gap\.IfV0i​\(π⋆i​\(⋅\)\)V\_\{0\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\cdot\)\\bigr\)is alsoL0L\_\{0\}\-Lipschitz onℝ\+\\mathbb\{R\}\_\{\+\}, then

\|∑i=1NV0i​\(π^i​\(λi\)\)−∑i=1NV0i​\(π⋆i​\(λ⋆\)\)\|≤L0​\(N​δ\+N​\|λ¯−λ⋆\|\)\+N​εapprox\.\\biggl\|\\sum\_\{i=1\}^\{N\}V\_\{0\}^\{i\}\\\!\\bigl\(\\hat\{\\pi\}^\{i\}\(\\lambda^\{i\}\)\\bigr\)\-\\sum\_\{i=1\}^\{N\}V\_\{0\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda^\{\\star\}\)\\bigr\)\\biggr\|\\;\\leq\\;L\_\{0\}\\\!\\bigl\(\\sqrt\{N\}\\,\\delta\+N\\,\|\\bar\{\\lambda\}\-\\lambda^\{\\star\}\|\\bigr\)\\;\+\\;N\\,\\varepsilon\_\{\\mathrm\{approx\}\}\.\(17\)

The proof \(Appendix[B](https://arxiv.org/html/2605.30461#A2)\) combines Lipschitz sensitivity with Cauchy–Schwarz to translate theℓ2\\ell\_\{2\}consensus error into anℓ1\\ell\_\{1\}bound on individual deviations\.

###### Corollary 5\.5\(Explicit Constraint Violation Bound\)\.

Under the conditions of Proposition[5\.4](https://arxiv.org/html/2605.30461#S5.Thmtheorem4)and Theorem[5\.1](https://arxiv.org/html/2605.30461#S5.Thmtheorem1), ifλ¯k→λ⋆\\bar\{\\lambda\}\_\{k\}\\to\\lambda^\{\\star\}and the centralized solution is feasible, then asymptotically the constraint violation is bounded by

∑i=1NV1i​\(π^i​\(λki\)\)≤c\+LV​N​ρℒ​α​σ1−ρℒ\+N​εapprox\.\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\hat\{\\pi\}^\{i\}\(\\lambda^\{i\}\_\{k\}\)\\bigr\)\\;\\leq\\;c\\;\+\\;\\frac\{L\_\{V\}\\,\\sqrt\{N\}\\,\\rho^\{\\mathscr\{L\}\}\\,\\alpha\\,\\sigma\}\{1\-\\rho^\{\\mathscr\{L\}\}\}\\;\+\\;N\\,\\varepsilon\_\{\\mathrm\{approx\}\}\.\(18\)In particular, the constraint violation vanishes as \(i\)ℒ→∞\\mathscr\{L\}\\to\\infty\(more consensus rounds\), \(ii\)α→0\\alpha\\to 0\(smaller dual step size\), \(iii\)ρ→0\\rho\\to 0\(better\-connected graph\), or \(iv\)εapprox→0\\varepsilon\_\{\\mathrm\{approx\}\}\\to 0\(more expressive policy class\)\.

We note that Danskin’s theorem also justifies the multiplier update in Algorithm[1](https://arxiv.org/html/2605.30461#alg1)\. For every fixed multiplierλ\\lambda, the policyπ⋆​\(λ\)\\pi\_\{\\star\}\(\\lambda\)is*defined*as a maximizer of the inner problemmaxπ⁡ℒ​\(π,λ\)\\max\_\{\\pi\}\\,\\mathcal\{L\}\(\\pi,\\lambda\)\. By Danskin’s theorem, the gradient of this maximized objective with respect toλ\\lambdadepends only on the partial derivative ofℒ\\mathcal\{L\}, evaluated at the maximizer\. Hence, in the multiplier update \(Lines 6–8 of Algorithm[1](https://arxiv.org/html/2605.30461#alg1)\) we treatπ⋆\\pi\_\{\\star\}as constant without loss of correctness\. This argument is standard in Lagrangian\-based constrained RL\(see, e\.g\., Calvo\-Fullanaet al\.,[2024](https://arxiv.org/html/2605.30461#bib.bib19)\)\.

Algorithm 1Distributed multiplier update with Separated Consensus and Gradient Steps1:Input:Trained policies

π⋆i​\(λ\)\\pi\_\{\\star\}^\{i\}\(\\lambda\), learning rates

α\\alpha,

ϵ\\epsilon, requirement

cc, number of consensus steps

ℒ\\mathscr\{L\}
2:Output:Trajectories satisfying the constraints

3:Initialize:Dual variables

λ0i=0\\lambda\_\{0\}^\{i\}=0,

μ0i=0\\mu\_\{0\}^\{i\}=0for

i=1,…,Ni=1,\\dots,N
4:for

k=0,1,…,K−1k=0,1,\\dots,K\-1do

5:Gradient Descent Step:

6:

λk\+12i=\[λki−α​\(cN−V1,ki\)\]\+\\lambda^\{i\}\_\{k\+\\frac\{1\}\{2\}\}=\\left\[\\lambda^\{i\}\_\{k\}\-\\alpha\\left\(\\frac\{c\}\{N\}\-V^\{i\}\_\{1,k\}\\right\)\\right\]\_\{\+\}
7:Initialize Consensus Variable:

8:

λℓ=0i=λk\+12i\\lambda^\{i\}\_\{\\ell=0\}=\\lambda^\{i\}\_\{k\+\\frac\{1\}\{2\}\}
9:for

ℓ=0,…,ℒ−1\\ell=0,\\dots,\\mathscr\{L\}\-1do

10:Consensus Update:

11:

λℓ\+1i=λℓi−ϵ​\(λℓi−1\|𝒩i\|​∑j∈𝒩iλℓj\)\\lambda^\{i\}\_\{\\ell\+1\}=\\lambda^\{i\}\_\{\\ell\}\-\\epsilon\\left\(\\lambda^\{i\}\_\{\\ell\}\-\\frac\{1\}\{\|\\mathcal\{N\}\_\{i\}\|\}\\sum\_\{j\\in\\mathcal\{N\}\_\{i\}\}\\lambda^\{j\}\_\{\\ell\}\\right\)
12:endfor

13:Update for Next Iteration:

14:

λk\+1i=λℓ=ℒi\\lambda^\{i\}\_\{k\+1\}=\\lambda^\{i\}\_\{\\ell=\\mathscr\{L\}\}
15:endfor

In practice, we perform only one consensus iteration per time step \(ℒ=1\\mathscr\{L\}=1\)\.

## 6Use Case: Smart Grid Management

We apply our method to Demand Response \(DR\) in a district of buildings with solar energy and battery storage\. Our goal is to minimize energy costs for each building while avoiding critical grid peaks through energy storage and load shifting\. Each building’s agent observes the current demand, battery charge, and grid price, then decides how to allocate energy between grid and battery sources\. The local objective is defined asr0i​\(sti,ati\)=−egrid​\(sti,ati\)​pt,r\_\{0\}^\{i\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)=\-e\_\{\\text\{grid\}\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)\\,p\_\{t\},whereegrid​\(sti,ati\)e\_\{\\text\{grid\}\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)is the building’s grid consumption andptp\_\{t\}is the energy price at timett\. By maximizingr0i,r\_\{0\}^\{i\},agents minimize their grid electricity spending while respecting global consumption constraints\.

The secondary rewardr1i​\(sti,ati\)=egrid​\(sti,ati\)r\_\{1\}^\{i\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)=e\_\{\\text\{grid\}\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)with constraint∑i=1NV1i​\(πi\)≤c\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\(\\pi^\{i\}\)\\leq censures that average total grid usage stays below thresholdcc\(a percentage of peak demand\), maintaining grid stability\. Agents can postpone unmet demand for later, and batteries charge automatically from solar generation\. To ensure all demand is eventually met, we add a local constraint with reward

r2i​\(sti,ati\)=dti−egrid​\(sti,ati\)−ebat​\(sti,ati\),r\_\{2\}^\{i\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)=d\_\{t\}^\{i\}\-e\_\{\\text\{grid\}\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)\-e\_\{\\text\{bat\}\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\),\(19\)
wheredtid\_\{t\}^\{i\}is the demand of agentiiat timettandebat​\(sti,ati\)e\_\{\\text\{bat\}\}\(s\_\{t\}^\{i\},a\_\{t\}^\{i\}\)is the battery\-delivered energy\. LetV2i​\(πi\)V\_\{2\}^\{i\}\(\\pi^\{i\}\)be the corresponding value function, defined as in equation[3](https://arxiv.org/html/2605.30461#S3.E3)\. We then impose the local constraint

V2i​\(πi\)=0,V\_\{2\}^\{i\}\(\\pi^\{i\}\)=0,which ensures that, in expectation, all of agentii’s demand is met over the long run\. Since the constraint is local, it only affects the optimization problem of agentii\. The training of the policy is performed following the state augmented procedure described in Section[4\.1](https://arxiv.org/html/2605.30461#S4.SS1)and the updates of the global constraint and the consensus multipliers are performed as shown in Algorithm[1](https://arxiv.org/html/2605.30461#alg1)\. For the handling of the local constraint we just add another term to the Lagrangian which only needs the addition of the following update

νk\+1i=νki−η​\(dki−egrid​\(ski,aki\)−ebat​\(ski,aki\)\),\\displaystyle\\nu^\{i\}\_\{k\+1\}=\\nu^\{i\}\_\{k\}\-\\eta\\left\(d^\{i\}\_\{k\}\-e\_\{\\text\{grid\}\}\(s\_\{k\}^\{i\},a\_\{k\}^\{i\}\)\-e\_\{\\text\{bat\}\}\(s\_\{k\}^\{i\},a\_\{k\}^\{i\}\)\\right\),\(20\)with step sizeη\\eta\. Energy prices, demand, and solar generation data come from City Learn\(Vázquez\-Canteliet al\.,[2020](https://arxiv.org/html/2605.30461#bib.bib8);[2019](https://arxiv.org/html/2605.30461#bib.bib7); Lab,[2024](https://arxiv.org/html/2605.30461#bib.bib9)\)\. Since this constraint is purely local,νi\\nu^\{i\}does not participate in the consensus mechanism: eachνi\\nu^\{i\}is updated independently using agentii’s own unmet demand signal\. Consequently, the local constraint does not affect the consensus analysis in Theorem[5\.1](https://arxiv.org/html/2605.30461#S5.Thmtheorem1)or Proposition[5\.4](https://arxiv.org/html/2605.30461#S5.Thmtheorem4), which concern only the global multiplierλ\\lambda\.

## 7Experimental Results

![Refer to caption](https://arxiv.org/html/2605.30461v1/x1.png)\(a\)Circular connections, one agent with double demand
![Refer to caption](https://arxiv.org/html/2605.30461v1/x2.png)\(b\)Linear connections, one agent with double demand
![Refer to caption](https://arxiv.org/html/2605.30461v1/x3.png)\(c\)Two clusters, two agents with double demand

Figure 1:Different communication networks and agent demands\.We test our method333Execution experiments were carried out on a MacBook Pro M3 with 8 GB RAM\. Training benchmarks were measured on a 16\-core CPU with 21 GB RAM\.on the network configurations in Figure[1](https://arxiv.org/html/2605.30461#S7.F1), which vary in connectivity and demand diversity\. Less\-connected networks challenge consensus, while heterogeneous demands create problems that require coordination to solve\. We focus on the configuration in Figure[1\(c\)](https://arxiv.org/html/2605.30461#S7.F1.sf3): two weakly connected groups where one agent in each has double the demand of others\. Using PPO\(Schulmanet al\.,[2017](https://arxiv.org/html/2605.30461#bib.bib50)\)on the Farama Gymnasium framework\(Towerset al\.,[2024](https://arxiv.org/html/2605.30461#bib.bib34)\), we train just two policies—one for normal demand, one for double demand—demonstrating the efficiency of single\-agent training with multi\-agent execution\. Individual Lagrange multipliers \(λi\\lambda^\{i\}\) enable coordination during execution, with consensus being critical for linking training to execution and ensuring constraint satisfaction\. Training uses10610^\{6\}PPO timesteps per agent type, in episodes of 80 timesteps \(about 3 days of demand\), with multipliers sampled fromλ∈\[0,15\]\\lambda\\in\[0,15\]andν∈\[−25,25\]\\nu\\in\[\-25,25\]\. The dataset contains 3,000 hours of data with random episode starting points\.

All multiplier step sizes are set toα=ϵ=η=0\.01\\alpha=\\epsilon=\\eta=0\.01, and we useℒ=1\\mathscr\{L\}=1consensus round per timestep\. The step sizes were selected to balance convergence speed against oscillation amplitude; the consensus bound in Theorem[5\.1](https://arxiv.org/html/2605.30461#S5.Thmtheorem1)shows that the asymptotic error scales asα​σ/\(1−ρ\)\\alpha\\,\\sigma/\(1\-\\rho\), so smallerα\\alphareduces steady\-state error at the cost of slower adaptation\. A single consensus round \(ℒ=1\\mathscr\{L\}=1\) is sufficient because the spectral gap1−ρ1\-\\rhoof our communication graphs is large enough to keep the consensus error within acceptable bounds \(Section[7\.1](https://arxiv.org/html/2605.30461#S7.SS1)\)\.

We focus on smart grid management as it naturally fits our structural assumptions while remaining complex enough to demonstrate consensus necessity\. We validate the approach through: \(i\) ablations demonstrating the necessity of both consensus and state augmentation \(Sections[7\.1](https://arxiv.org/html/2605.30461#S7.SS1)–[7\.2](https://arxiv.org/html/2605.30461#S7.SS2)\), \(ii\) comparison against a centralized oracle establishing that distributed consensus incurs negligible performance loss \(Section[7\.3](https://arxiv.org/html/2605.30461#S7.SS3)\), and \(iii\) scaling to 1,000 agents, far beyond CTDE capabilities \(Section[7\.4](https://arxiv.org/html/2605.30461#S7.SS4)\)\.

### 7\.1Consensus Necessity

We set the constraintccto 27% of peak demand \(challenging yet feasible\)\. Agents run for 3,000 timesteps with continuous multiplier updates \(Algorithm[1](https://arxiv.org/html/2605.30461#alg1)\)\. To demonstrate coordination importance, we compare two variants: with*consensus*, agents exchange multipliersλi\\lambda^\{i\}with neighbors and average them \(lines 8–13 in Algorithm[1](https://arxiv.org/html/2605.30461#alg1)\); without*consensus*, agents only perform local gradient updates without coordination\. While both maintain grid consumption below the threshold \(Figure[3\(a\)](https://arxiv.org/html/2605.30461#S7.F3.sf1)\), the no\-consensus version achieves this by indefinitely postponing demand rather than finding a true solution\.

![Refer to caption](https://arxiv.org/html/2605.30461v1/x4.png)\(a\)With consensus
![Refer to caption](https://arxiv.org/html/2605.30461v1/x5.png)\(b\)Without consensus

Figure 2:Evolution of the global multipliersλi\\lambda^\{i\}for the first three agents during execution\.![Refer to caption](https://arxiv.org/html/2605.30461v1/x6.png)\(a\)Avg\. total grid consumption\.
![Refer to caption](https://arxiv.org/html/2605.30461v1/x7.png)\(b\)Unmet demand \(with consensus\)\.

Figure 3:Cumulative unmet demand with consensus\. Stable negative values \(c=0\.3, 0\.4\) indicate proactive load shifting; stable zero indicates exact demand matching \(no control\); unbounded positive growth \(c=0\.2\) indicates infeasibility\.Testing four constraint levelsc∈\{0\.2,0\.3,0\.4,0\.5\}c\\in\\\{0\.2,0\.3,0\.4,0\.5\\\}, we find that consensus achieves stable unmet demand for feasible cases \(c≥0\.3c\\geq 0\.3\), with lower constraints allowing more grid usage as expected \(Figure[3\(b\)](https://arxiv.org/html/2605.30461#S7.F3.sf2)\)\. Atc=0\.2c=0\.2, even consensus cannot find a solution\. Without consensus, the problem becomes infeasible even for moderate constraints likec∈\{0\.3,0\.4\}c\\in\\\{0\.3,0\.4\\\}\(Figure[4\(b\)](https://arxiv.org/html/2605.30461#S7.F4.sf2)\)\. Crucially, at our targetc=27%c=27\\%, the no\-consensus version fails to solve the problem despite meeting grid constraints—its multipliers never converge \(Figure[2\(b\)](https://arxiv.org/html/2605.30461#S7.F2.sf2)\), preventing optimal solution discovery\.

![Refer to caption](https://arxiv.org/html/2605.30461v1/x8.png)\(a\)Mean energy cost
![Refer to caption](https://arxiv.org/html/2605.30461v1/x9.png)\(b\)Unmet demand \(no consensus\)

Figure 4:Cost and demand\-satisfaction trajectories\. The dashed horizontal line in \([4\(b\)](https://arxiv.org/html/2605.30461#S7.F4.sf2)\) marks zero unmet demand\.The absence of consensus produces both higher operating cost \(Figure[4\(a\)](https://arxiv.org/html/2605.30461#S7.F4.sf1)\) and continued growth of deferred demand \(Figure[4\(b\)](https://arxiv.org/html/2605.30461#S7.F4.sf2)\)\. These complementary views underline the practical value of the lightweight neighbor\-to\-neighbor communication adopted in Algorithm[1](https://arxiv.org/html/2605.30461#alg1)\. Figure[2\(a\)](https://arxiv.org/html/2605.30461#S7.F2.sf1)shows that exchangingλi\\lambda^\{i\}with immediate neighbors causes convergence to the same value, thereby satisfying the global grid\-consumption constraint\. Without this exchange \(Figure[2\(b\)](https://arxiv.org/html/2605.30461#S7.F2.sf2)\), the two high\-demand agents push their multipliers to the hard cap of 15, signaling that dual ascent has saturated before a feasible primal solution was found\.

### 7\.2Ablation: State Augmentation and Comparison with Baselines

Training policies with fixed Lagrange multipliers,rather than conditioning onλ\\lambdaas input \(state augmentation\),is equivalent to standard Lagrangian approaches thatCalvo\-Fullanaet al\.\([2024](https://arxiv.org/html/2605.30461#bib.bib19)\)prove can fail to produce feasible policies\. To empirically validate this and demonstrate the necessity of state augmentation, we trained a grid of Independent PPO \(IPPO\) agents, one for every fixed\(λ,ν\)∈\[0,15\]×\[−20,8\]\(\\lambda,\\nu\)\\\!\\in\\\!\[0,15\]\\times\[\-20,8\]\(a subset of the full training sweepλ∈\[0,15\]×ν∈\[−25,25\]\\lambda\\in\[0,15\]\\times\\nu\\in\[\-25,25\]retained for this feasibility analysis\), yielding 414 models\. Each model represents a policy trained*without*state augmentation: the multipliers are fixed during training and cannot adapt during execution\. Figure[5](https://arxiv.org/html/2605.30461#S7.F5)shows the performance for every\(λ,ν\)\(\\lambda,\\nu\)pair, measuring \(a\) mean grid consumption and \(b\) absolute rate of change of cumulative postponed demand\. Only 7 of 414 configurations \(<2%<2\\%\) satisfy both the 27% grid\-consumption limit and prevent postponed demand from diverging \(Table[2](https://arxiv.org/html/2605.30461#S7.T2)\)\. This extreme sensitivity confirms the theoretical fragility of non\-augmented methods\. In contrast, our state\-augmented approach trains a single policy that generalizes across allλ\\lambdavalues, with consensus dynamically finding the correct multiplier during execution\.

![Refer to caption](https://arxiv.org/html/2605.30461v1/x10.png)\(a\)Mean grid consumption
![Refer to caption](https://arxiv.org/html/2605.30461v1/x11.png)\(b\)Derivative of postponed demand

Figure 5:Ablation: 414 IPPO agents trained with fixed\(λ,ν\)\(\\lambda,\\nu\)\(without state augmentation\)\. Only 7 yield feasible behavior\. Blank cells indicate diverging runs\.Table 2:The 7 fixed multiplier pairs \(of 414 tested\) yielding stable behavior, demonstrating the brittleness of non\-augmented methods\.##### Comparison with MARL Baselines\.

From the seven feasible pairs we selected\(λ⋆,ν⋆\)=\(8,−8\)\(\\lambda^\{\\star\},\\nu^\{\\star\}\)=\(8,\-8\), giving baselines their best chance, and trained four multi\-agent methods: MAPPO, MADDPG, MASAC, and ISAC\. Each baseline ran with these hand\-tuned fixed penalty weights, whereas our method adapted multipliers online via consensus\. For every algorithm we executed 10 roll\-outs and recorded \(i\) the trajectory closest to satisfying the 27% grid threshold and \(ii\) the mean total cost\. Figure[6](https://arxiv.org/html/2605.30461#S7.F6)shows that only MAPPO and ISAC keep grid consumption near the limit, while MASAC and MADDPG overshoot\. Even these “successful” baselines closely match the operating cost of our decentralized multiplier\-adaptive method, which achieves 0% infeasible roll\-outs across all seeds\. Despite their hand\-tuned advantage from exhaustive search, the baselines still violate constraints, highlighting the fundamental limitation of fixed\-multiplier approaches\.

![Refer to caption](https://arxiv.org/html/2605.30461v1/x12.png)Figure 6:Average performance of state\-of\-the\-art MARL baselines\. The grey dashed line marks the grid\-consumption constraint \(27 % of peak demand\)\.All four baselines rely on centralized components; MAPPO, MASAC and ISAC use a joint critic, while MADDPG conditions each critic on the full joint action\.444The policies may execute decentralized actions at test time, but training still scales at least quadratically with the number of agents because the critics ingest the joint state–action tuple\.Consequently, their computational and memory costs explode as the population grows, limiting practical use to a few dozen agents\. Our method keeps both training and execution fully decentralized, needs only one policy per agent type, and scales linearly in the number of agents \(Figure[8\(a\)](https://arxiv.org/html/2605.30461#S7.F8.sf1)\), giving it a clear advantage for large systems\.

The related work discusses constrained MARL methods such as Safe Dec\-PG\(Luet al\.,[2021](https://arxiv.org/html/2605.30461#bib.bib43)\), MACPO\(Guet al\.,[2021](https://arxiv.org/html/2605.30461#bib.bib33)\), and Scal\-MAPPO\-L\(Zhanget al\.,[2024](https://arxiv.org/html/2605.30461#bib.bib62)\)\. These methods address different problem settings \(coupled dynamics, per\-step or cumulative safety constraints\) and are not directly applicable to our separable\-dynamics, average\-constraint formulation\. Rather than adapting an external method to our setting, we compare against a*centralized oracle*: a single globalλ\\lambdaupdated with perfect knowledge of the aggregate constraint signal at every timestep\. This is the strongest possible baseline under our formulation, as it represents the performance achievable with unlimited communication\. Any gap between our distributed method and this oracle is precisely the cost of decentralization\.

### 7\.3Centralized Oracle Comparison

To quantify the cost of decentralization, we compare against a*centralized oracle*that replaces the distributed consensus mechanism with a single global multiplier updated from the true average constraint satisfaction across all agents:λk\+1=\[λk−α​\(c/N−1N​∑i=1NV1,ki\)\]\+\\lambda\_\{k\+1\}=\[\\lambda\_\{k\}\-\\alpha\\,\(c/N\-\\frac\{1\}\{N\}\\sum\_\{i=1\}^\{N\}V\_\{1,k\}^\{i\}\)\]\_\{\+\}\. This oracle has perfect global information at every timestep, an assumption that is unrealistic in practice but provides a best\-case reference\. Both methods use the same state\-augmented policies trained offline; the only difference is howλ\\lambdais coordinated during execution\.

Table[3](https://arxiv.org/html/2605.30461#S7.T3)reports results over 10 identical random seeds\. The distributed method matches the centralized oracle in all operational metrics: grid consumption is very close \(44\.89±0\.0144\.89\\pm 0\.01kWh vs\. the 47\.14 kWh threshold\), energy cost differs by\+0\.086%±0\.075%\+0\.086\\%\\pm 0\.075\\%\(distributed is marginally more expensive than the oracle, well within the<0\.2%<\\\!0\.2\\%regime\), and both achieve negative cumulative unmet demand indicating proactive demand fulfillment\. The constraint is satisfied in 100% of runs for both methods\.

Table 3:Centralized oracle vs\. distributed consensus \(N=7N\\\!=\\\!7,c=0\.27c=0\.27,T=3000T=3000,1010paired seeds\)\. Both methods use the same trained policies; the only difference is the coordination mechanism\.The only notable difference is in the converged dual variable:λ¯=1\.49±0\.01\\bar\{\\lambda\}=1\.49\\pm 0\.01\(distributed\) versus2\.11±0\.012\.11\\pm 0\.01\(centralized\)\. Despite this difference in the multiplier values, the state\-augmented policies produce operationally equivalent behavior\. This demonstrates that the policies are robust to variation inλ\\lambda, consistent with the Lipschitz sensitivity assumption \(Assumption[5\.2](https://arxiv.org/html/2605.30461#S5.Thmtheorem2)\): the constraint value function changes smoothly with the multiplier, so moderate differences inλ\\lambdado not significantly affect constraint satisfaction or cost\.

The empirical Lipschitz constant, estimated from policy evaluations overλ∈\[0,15\]\\lambda\\in\[0,15\]\(Appendix[B\.2](https://arxiv.org/html/2605.30461#A2.SS2), Figure[B\.1](https://arxiv.org/html/2605.30461#A2.F1)\), isL^V=8\.44\\hat\{L\}\_\{V\}=8\.44kWh per unitλ\\lambdaandL^0=39\.24\\hat\{L\}\_\{0\}=39\.24$ per unitλ\\lambda\. For the 7\-agent configuration withℒ=1\\mathscr\{L\}=1, the consensus error term in Corollary[5\.5](https://arxiv.org/html/2605.30461#S5.Thmtheorem5)givesLV​N​δ≈22\.3​δL\_\{V\}\\sqrt\{N\}\\,\\delta\\approx 22\.3\\,\\deltakWh\. The observed constraint margin \(47\.14−44\.89=2\.2547\.14\-44\.89=2\.25kWh, Table[3](https://arxiv.org/html/2605.30461#S7.T3)\) is well within this bound for the empirical consensus errors, showing that the theoretical guarantees of Proposition[5\.4](https://arxiv.org/html/2605.30461#S5.Thmtheorem4)are well grounded\.

Figure[7](https://arxiv.org/html/2605.30461#S7.F7)shows the execution dynamics\. Both methods converge to the same grid\-consumption level below the constraint threshold, with the distributed approach achieving slightly more proactive demand fulfillment \(more negative cumulative unmet demand\) due to its marginally more conservative operation\.

![Refer to caption](https://arxiv.org/html/2605.30461v1/x13.png)Figure 7:Centralized oracle vs\. distributed consensus \(N=7N\\\!=\\\!7,c=0\.27c=0\.27, 10 seeds\)\. Both satisfy the constraint and achieve equivalent cost and demand fulfillment\.
### 7\.4Scalability Study

![Refer to caption](https://arxiv.org/html/2605.30461v1/x14.png)\(a\)Execution time
![Refer to caption](https://arxiv.org/html/2605.30461v1/x15.png)\(b\)Multiplier convergence

Figure 8:Scalability of the execution phase\. \([8\(a\)](https://arxiv.org/html/2605.30461#S7.F8.sf1)\) Wall\-clock execution time versus agent count\. \([8\(b\)](https://arxiv.org/html/2605.30461#S7.F8.sf2)\) Running mean ofλi\\lambda^\{i\}for systems of 10, 100, 500, and 1000 agents\.To validate scalability claims, we tested our method on systems with 10, 100, 500, and 1000 agents\. Figure[8\(a\)](https://arxiv.org/html/2605.30461#S7.F8.sf1)confirms the*linear*execution\-time scaling predicted by our decentralized design, while Figure[8\(b\)](https://arxiv.org/html/2605.30461#S7.F8.sf2)demonstrates that all agents converge to a common multiplier irrespective of population size\. This scalability to 1000 agents far exceeds the capabilities of CTDE\-based methods, which are typically limited to a few dozen agents due to their centralized training components\.

Because our method trains a single policy per agent type, not per agent, training cost isO​\(1\)O\(1\)in the number of agentsNN\. The same two policies \(one per building type,10610^\{6\}PPO timesteps each\) serve all configurations from 7 to 1,000 agents\. Training required 26\.7 minutes total \(13\.2 \+ 13\.5 min\) on a 16\-core CPU with∼5\{\\sim\}5GB peak memory\. In contrast, CTDE methods require retraining wheneverNNchanges, as the centralized critic takes the joint state–action space\. The combination ofO​\(1\)O\(1\)training and linear execution scaling is what enables the orders\-of\-magnitude improvement over existing approaches\.

## 8Conclusion

We presented a distributed approach to constrained MARL that combines state\-augmented policy learning with consensus\-based coordination over dual variables\. Our experiments demonstrate that the dual\-variable consensus mechanism is what makes independently\-trained policies collectively feasible: without it, agents resort to degenerate solutions despite individually satisfying their local objectives\. The comparison with a centralized oracle in Section[7\.3](https://arxiv.org/html/2605.30461#S7.SS3)shows that, on the smart\-grid configurations evaluated, distributed consensus closes the cost gap to\+0\.086%±0\.075%\+0\.086\\%\\pm 0\.075\\%\(within the<0\.2%<\\\!0\.2\\%regime\), while training cost isO​\(1\)O\(1\)in the number of agents and execution scales linearly, reaching 1,000 agents where CTDE methods are limited to tens\. We emphasize that this near\-equivalence with the centralized oracle is an empirical observation in a specific testbed, not a general optimality claim\. The analysis of Appendix[A\.1](https://arxiv.org/html/2605.30461#A1.SS1)bounds the consensus error of the global multiplierλ\\lambdaand translates this bound into a feasibility margin through Proposition[5\.4](https://arxiv.org/html/2605.30461#S5.Thmtheorem4), but does not yield a full primal optimality guarantee\. The local\-constraint multiplierν\\nuis updated by an analogous primal\-dual scheme and is well\-behaved in our experiments; however, its convergence is not covered by Theorem[5\.1](https://arxiv.org/html/2605.30461#S5.Thmtheorem1), and we treat it as an empirical extension of the global\-constraint theory rather than a setting in which the formal guarantees apply\.

The separable\-dynamics and summable\-rewards assumptions are restrictive, and identifying the class of problems for which our framework is appropriate is therefore important\. Our method is naturally suited to infrastructure\-management settings in which agents have physically decoupled local dynamics and interact only through a shared resource budget\. Smart\-grid demand response \(studied here\), distributed electric\-vehicle charging, traffic\-signal coordination at lightly\-coupled intersections, and water\- or heating\-network management all share this structure: each node manages a local controllable resource, and the global constraint aggregates linearly across nodes\. Conversely, settings in which agent dynamics are physically coupled, such as multi\-robot manipulation, cooperative navigation in a shared workspace, or pursuit\-evasion in a joint state space, violate Assumption[3\.2](https://arxiv.org/html/2605.30461#S3.Thmtheorem2)and lie outside the regime to which our analysis applies\. For such problems the consensus error bound of Theorem[5\.1](https://arxiv.org/html/2605.30461#S5.Thmtheorem1)no longer guarantees that aligned multipliers produce a coherent joint policy, and a different coordination mechanism is required\.

The empirical evidence we present is encouraging but comes predominantly from one application domain, and broader validation across the application classes identified above remains a priority for follow\-up work\. Several further directions are open\. First, extending the framework to time\-varying constraints would broaden applicability to settings where resource limits fluctuate, such as renewable\-energy availability or congestion\-dependent capacities\. Second, heterogeneous and time\-evolving communication graphs would better model realistic infrastructure networks\. Third, hybrid approaches that combine our lightweight consensus mechanism with more expressive coordination, for example sparse joint critics on small clusters of strongly coupled agents, could address problems with partially\-coupled dynamics and bridge the gap between full separability and the general coupled setting\. Fourth, a theoretical treatment of the local\-constraint multiplierν\\nuremains open; establishing convergence guarantees analogous to Theorem[5\.1](https://arxiv.org/html/2605.30461#S5.Thmtheorem1)for the joint\(λ,ν\)\(\\lambda,\\nu\)update is a natural next step\.

## References

- Benchmarking safe exploration in deep reinforcement learning\.Technical reportOpenAI\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p1.1)\.
- J\. Achiam, D\. Held, A\. Tamar, and P\. Abbeel \(2017\)Constrained policy optimization\.InProceedings of the 34th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.70,pp\. 22–31\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p1.1)\.
- L\. Agorio, S\. Van Alen, M\. Calvo\-Fullana, S\. Paternain, and J\. A\. Bazerque \(2024\)Multi\-agent assignment via state augmented reinforcement learning\.arXiv preprint arXiv:2406\.01782\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p1.1)\.
- S\. V\. Albrecht, F\. Christianos, and L\. Schäfer \(2024\)Multi\-agent reinforcement learning: foundations and modern approaches\.MIT Press\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p2.1)\.
- E\. Altman \(2021\)Constrained Markov decision processes\.Routledge,Boca Raton\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p1.1)\.
- V\. S\. Borkar \(2005\)An actor\-critic algorithm for constrained Markov decision processes\.Systems & Control Letters54\(3\),pp\. 207–213\.External Links:[Document](https://dx.doi.org/10.1016/j.sysconle.2004.08.007)Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p1.1)\.
- N\. Brown and T\. Sandholm \(2019\)Superhuman AI for multiplayer poker\.Science365\(6456\),pp\. 885–890\.External Links:[Document](https://dx.doi.org/10.1126/science.aay2400)Cited by:[§1](https://arxiv.org/html/2605.30461#S1.p1.1)\.
- M\. Calvo\-Fullana, S\. Paternain, L\. F\. O\. Chamon, and A\. Ribeiro \(2024\)State augmented constrained reinforcement learning: overcoming the limitations of learning with rewards\.IEEE Transactions on Automatic Control69\(7\),pp\. 4275–4290\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2023.3325279)Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p1.1),[§4\.1](https://arxiv.org/html/2605.30461#S4.SS1.p1.6),[Remark 4\.1](https://arxiv.org/html/2605.30461#S4.Thmtheorem1.p1.1),[§5](https://arxiv.org/html/2605.30461#S5.p2.1),[§5](https://arxiv.org/html/2605.30461#S5.p7.6),[§7\.2](https://arxiv.org/html/2605.30461#S7.SS2.p1.6)\.
- D\. Chen, K\. Chen, Z\. Li, T\. Chu, R\. Yao, F\. Qiu, and K\. Lin \(2022\)PowerNet: multi\-agent deep reinforcement learning for scalable powergrid control\.IEEE Transactions on Power Systems37\(2\),pp\. 1007–1017\.External Links:[Document](https://dx.doi.org/10.1109/TPWRS.2021.3100898)Cited by:[Table 1](https://arxiv.org/html/2605.30461#S2.T1.11.10.5.1),[§2](https://arxiv.org/html/2605.30461#S2.p3.1)\.
- Z\. Chen, Y\. Zhou, and H\. Huang \(2024\)On the hardness of constrained cooperative multi\-agent reinforcement learning\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p4.1)\.
- K\. Cheruiyot, N\. Kiprotich, V\. Kungurtsev, K\. Mugo, V\. Mwirigi, and M\. Ngesa \(2025\)A survey of multi agent reinforcement learning: federated learning and cooperative and noncooperative decentralized regimes\.arXiv preprint arXiv:2507\.06278\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p2.1)\.
- Y\. Chow, O\. Nachum, A\. Faust, M\. Ghavamzadeh, and E\. A\. Duéñez\-Guzmán \(2019\)Lyapunov\-based safe policy optimization for continuous control\.arXiv preprint arXiv:1901\.10031\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p1.1)\.
- T\. Chu, S\. Chinchali, and S\. Katti \(2020\)Multi\-agent reinforcement learning for networked system control\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[Table 1](https://arxiv.org/html/2605.30461#S2.T1.11.9.4.1),[§2](https://arxiv.org/html/2605.30461#S2.p3.1),[§2](https://arxiv.org/html/2605.30461#S2.p7.1)\.
- F\. R\. K\. Chung \(1997\)Spectral graph theory\.CBMS Regional Conference Series in Mathematics, Vol\.92,American Mathematical Society\.Cited by:[item 1](https://arxiv.org/html/2605.30461#A1.I1.i1.p1.5),[§A\.1](https://arxiv.org/html/2605.30461#A1.SS1.p1.1)\.
- W\. Cui, Y\. Jiang, B\. Zhang, and Y\. Shi \(2023\)Structured neural\-PI control with end\-to\-end stability and output tracking guarantees\.InAdvances in Neural Information Processing Systems,Vol\.36\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p6.1)\.
- C\. S\. de Witt, T\. Gupta, D\. Makoviichuk, V\. Makoviychuk, P\. H\. S\. Torr, M\. Sun, and S\. Whiteson \(2020\)Is independent learning all you need in the StarCraft multi\-agent challenge?\.arXiv preprint arXiv:2011\.09533\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p2.1)\.
- G\. Dileep \(2020\)A survey on smart grid technologies and applications\.Renewable Energy146,pp\. 2589–2625\.External Links:[Document](https://dx.doi.org/10.1016/j.renene.2019.08.092)Cited by:[§1](https://arxiv.org/html/2605.30461#S1.p3.1)\.
- D\. Ding, X\. Wei, Z\. Yang, Z\. Wang, and M\. R\. Jovanović \(2023\)Provably efficient generalized lagrangian policy optimization for safe multi\-agent reinforcement learning\.arXiv preprint arXiv:2306\.00212\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p4.1)\.
- J\. Feng, W\. Cui, J\. Cortés, and Y\. Shi \(2023\)Bridging transient and steady\-state performance in voltage control: a reinforcement learning approach with safe gradient flow\.IEEE Control Systems Letters7,pp\. 2845–2850\.External Links:[Document](https://dx.doi.org/10.1109/LCSYS.2023.3289435)Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p6.1)\.
- J\. Feng, Y\. Shi, G\. Qu, S\. H\. Low, A\. Anandkumar, and A\. Wierman \(2024\)Stability constrained reinforcement learning for decentralized real\-time voltage control\.IEEE Transactions on Control of Network Systems11\(2\),pp\. 1115–1127\.External Links:[Document](https://dx.doi.org/10.1109/TCNS.2023.3338240)Cited by:[Table 1](https://arxiv.org/html/2605.30461#S2.T1.11.11.6.1),[§2](https://arxiv.org/html/2605.30461#S2.p3.1)\.
- C\. Godsil and G\. Royle \(2001\)Algebraic graph theory\.Graduate Texts in Mathematics, Vol\.207,Springer\.External Links:ISBN 978\-0\-387\-95220\-8,[Document](https://dx.doi.org/10.1007/978-1-4613-0163-9)Cited by:[item 1](https://arxiv.org/html/2605.30461#A1.I1.i1.p1.5)\.
- S\. Gu, J\. G\. Kuba, M\. Wen, R\. Chen, Z\. Wang, Z\. Tian, J\. Wang, A\. Knoll, and Y\. Yang \(2021\)Multi\-agent constrained policy optimisation\.arXiv preprint arXiv:2110\.02793\.Cited by:[Table 1](https://arxiv.org/html/2605.30461#S2.T1.9.3.2),[§2](https://arxiv.org/html/2605.30461#S2.p4.1),[§7\.2](https://arxiv.org/html/2605.30461#S7.SS2.SSS0.Px1.p3.1)\.
- M\. A\. Hady, S\. Hu, M\. Pratama, Z\. Cao, and R\. Kowalczyk \(2025\)Multi\-agent reinforcement learning for resources allocation optimization: a survey\.Artificial Intelligence Review58\.External Links:[Document](https://dx.doi.org/10.1007/s10462-025-11340-5)Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p2.1)\.
- R\. A\. Horn and C\. R\. Johnson \(2012\)Matrix analysis\.Second edition,Cambridge University Press,Cambridge, United Kingdom\.Cited by:[item 2](https://arxiv.org/html/2605.30461#A1.Ex18.m1.1.1),[§A\.2\.1](https://arxiv.org/html/2605.30461#A1.SS2.SSS1.1.p1.1)\.
- S\. Kakade and J\. Langford \(2002\)Approximately optimal approximate reinforcement learning\.InProceedings of the 19th International Conference on Machine Learning,pp\. 267–274\.Cited by:[Remark B\.1](https://arxiv.org/html/2605.30461#A2.Thmtheorem1.p2.9)\.
- M\. Kearns and S\. Singh \(2002\)Near\-optimal reinforcement learning in polynomial time\.Machine Learning49\(2–3\),pp\. 209–232\.External Links:[Document](https://dx.doi.org/10.1023/A%3A1017984413808)Cited by:[Remark B\.1](https://arxiv.org/html/2605.30461#A2.Thmtheorem1.p2.9)\.
- L\. Kraemer and B\. Banerjee \(2016\)Multi\-agent reinforcement learning as a rehearsal for decentralized planning\.Neurocomputing190,pp\. 82–94\.External Links:[Document](https://dx.doi.org/10.1016/j.neucom.2016.01.031)Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p2.1)\.
- I\. E\. Lab \(2024\)CityLearn: official reinforcement learning environment for demand response and load shaping\.Note:[https://github\.com/intelligent\-environments\-lab/CityLearn](https://github.com/intelligent-environments-lab/CityLearn)Accessed: 2024\-05\-20Cited by:[§6](https://arxiv.org/html/2605.30461#S6.p5.5)\.
- D\. A\. Levin, Y\. Peres, and E\. L\. Wilmer \(2009\)Markov chains and mixing times\.American Mathematical Society,Providence, RI\.External Links:ISBN 978\-0\-8218\-4739\-8Cited by:[§A\.2\.1](https://arxiv.org/html/2605.30461#A1.SS2.SSS1.3.p3.6)\.
- Q\. Liang, F\. Que, and E\. H\. Modiano \(2018\)Accelerated primal\-dual policy optimization for safe reinforcement learning\.arXiv preprint arXiv:1802\.06480\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p1.1)\.
- M\. L\. Littman \(1994\)Markov games as a framework for multi\-agent reinforcement learning\.InMachine Learning Proceedings 1994,W\. W\. Cohen and H\. Hirsh \(Eds\.\),pp\. 157–163\.Cited by:[§3](https://arxiv.org/html/2605.30461#S3.p1.27)\.
- D\. Low and Y\. Zhou \(2025\)Cooperative multi\-agent reinforcement learning for robotic systems: a review\.International Journal of Advanced Robotic Systems\.External Links:[Document](https://dx.doi.org/10.1177/15741702251370050)Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p2.1)\.
- R\. Lowe, Y\. Wu, A\. Tamar, J\. Harb, P\. Abbeel, and I\. Mordatch \(2017\)Multi\-agent actor\-critic for mixed cooperative\-competitive environments\.InAdvances in Neural Information Processing Systems,Vol\.30\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p2.1)\.
- S\. Lu, K\. Zhang, T\. Chen, T\. Başar, and L\. Horesh \(2021\)Decentralized policy gradient descent ascent for safe multi\-agent reinforcement learning\.Proceedings of the AAAI Conference on Artificial Intelligence35\(10\),pp\. 8767–8775\.External Links:[Document](https://dx.doi.org/10.1609/aaai.v35i10.17062)Cited by:[Table 1](https://arxiv.org/html/2605.30461#S2.T1.8.2.2),[§2](https://arxiv.org/html/2605.30461#S2.p4.1),[§2](https://arxiv.org/html/2605.30461#S2.p7.1),[Remark 3\.4](https://arxiv.org/html/2605.30461#S3.Thmtheorem4.p1.2),[§7\.2](https://arxiv.org/html/2605.30461#S7.SS2.SSS0.Px1.p3.1)\.
- V\. Mai, P\. Maisonneuve, T\. Zhang, H\. Nekoei, L\. Paull, and A\. Lesage\-Landry \(2024\)Multi\-agent reinforcement learning for fast\-timescale demand response of residential loads\.Machine Learning113\(8\),pp\. 5203–5234\.External Links:[Document](https://dx.doi.org/10.1007/s10994-023-06460-4)Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p3.1)\.
- T\. Miyato, T\. Kataoka, M\. Koyama, and Y\. Yoshida \(2018\)Spectral normalization for generative adversarial networks\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[Remark B\.1](https://arxiv.org/html/2605.30461#A2.Thmtheorem1.p2.9)\.
- B\. Mohar, Y\. Alavi, G\. Chartrand, O\. R\. Oellermann, and A\. J\. Schwenk \(1991\)The Laplacian spectrum of graphs\.Graph Theory, Combinatorics, and Applications2,pp\. 871–898\.Cited by:[item 2](https://arxiv.org/html/2605.30461#A1.Ex18.m1.1.1)\.
- A\. Nedic and A\. Ozdaglar \(2009\)Distributed subgradient methods for multi\-agent optimization\.IEEE Transactions on Automatic Control54\(1\),pp\. 48–61\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2008.2009515)Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p5.2),[Remark 5\.6](https://arxiv.org/html/2605.30461#S5.Thmtheorem6.p1.2),[Remark 5\.7](https://arxiv.org/html/2605.30461#S5.Thmtheorem7.p1.4)\.
- M\. S\. Oh, Z\. Zhang, F\. Hairi, A\. Velasquez, and J\. Liu \(2025\)Consensus\-based decentralized multi\-agent reinforcement learning for random access network optimization\.InProceedings of the 26th International Symposium on Theory, Algorithmic Foundations, and Protocol Design for Mobile Networks and Mobile Computing \(MobiHoc ’25\),External Links:[Document](https://dx.doi.org/10.1145/3704413.3764464)Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p5.2)\.
- R\. Olfati\-Saber, J\. A\. Fax, and R\. M\. Murray \(2007\)Consensus and cooperation in networked multi\-agent systems\.Proceedings of the IEEE95\(1\),pp\. 215–233\.External Links:[Document](https://dx.doi.org/10.1109/JPROC.2006.887293)Cited by:[§A\.1](https://arxiv.org/html/2605.30461#A1.SS1.p1.1),[§2](https://arxiv.org/html/2605.30461#S2.p5.2)\.
- R\. Olfati\-Saber and R\. M\. Murray \(2004\)Consensus problems in networks of agents with switching topology and time\-delays\.IEEE Transactions on Automatic Control49\(9\),pp\. 1520–1533\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2004.834113)Cited by:[§A\.1](https://arxiv.org/html/2605.30461#A1.SS1.p1.1)\.
- J\. Orr and A\. Dutta \(2023\)Multi\-agent deep reinforcement learning for multi\-robot applications: a survey\.Sensors23\(7\),pp\. 3625\.External Links:[Document](https://dx.doi.org/10.3390/s23073625)Cited by:[§1](https://arxiv.org/html/2605.30461#S1.p1.1)\.
- S\. Paternain, M\. Calvo\-Fullana, L\. F\. O\. Chamon, and A\. Ribeiro \(2022\)Safe policies for reinforcement learning via primal\-dual methods\.IEEE Transactions on Automatic Control68\(3\),pp\. 1321–1336\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2022.3152724)Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p1.1)\.
- S\. Paternain, L\. F\. O\. Chamon, M\. Calvo\-Fullana, and A\. Ribeiro \(2019\)Constrained reinforcement learning has zero duality gap\.InAdvances in Neural Information Processing Systems,Vol\.32,pp\. 7553–7563\.Cited by:[§4](https://arxiv.org/html/2605.30461#S4.p2.1)\.
- G\. Qu, Y\. Lin, A\. Wierman, and N\. Li \(2020\)Scalable multi\-agent reinforcement learning for networked systems with average reward\.InAdvances in Neural Information Processing Systems,Vol\.33\.Cited by:[Table 1](https://arxiv.org/html/2605.30461#S2.T1.11.8.3.1),[§2](https://arxiv.org/html/2605.30461#S2.p3.1),[§2](https://arxiv.org/html/2605.30461#S2.p7.1)\.
- T\. Rashid, M\. Samvelyan, C\. Schroeder de Witt, G\. Farquhar, J\. Foerster, and S\. Whiteson \(2018\)QMIX: monotonic value function factorisation for deep multi\-agent reinforcement learning\.InProceedings of the 35th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.80,pp\. 4295–4304\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p2.1)\.
- J\. Schulman, F\. Wolski, P\. Dhariwal, A\. Radford, and O\. Klimov \(2017\)Proximal policy optimization algorithms\.arXiv preprint arXiv:1707\.06347\.Cited by:[§7](https://arxiv.org/html/2605.30461#S7.p1.4)\.
- D\. Silver, J\. Schrittwieser, K\. Simonyan, I\. Antonoglou, A\. Huang, A\. Guez, T\. Hubert, L\. Baker, M\. Lai, A\. Bolton, Y\. Chen, T\. Lillicrap, F\. Hui, L\. Sifre, G\. van den Driessche, T\. Graepel, and D\. Hassabis \(2017\)Mastering the game of Go without human knowledge\.Nature550\(7676\),pp\. 354–359\.External Links:[Document](https://dx.doi.org/10.1038/nature24270)Cited by:[§1](https://arxiv.org/html/2605.30461#S1.p1.1)\.
- P\. Sunehag, G\. Lever, A\. Gruslys, W\. M\. Czarnecki, V\. Zambaldi, M\. Jaderberg, M\. Lanctot, N\. Sonnerat, J\. Z\. Leibo, K\. Tuyls, and T\. Graepel \(2018\)Value\-decomposition networks for cooperative multi\-agent learning based on team reward\.InProceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems \(AAMAS\),pp\. 2085–2087\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p2.1)\.
- C\. Szegedy, W\. Zaremba, I\. Sutskever, J\. Bruna, D\. Erhan, I\. Goodfellow, and R\. Fergus \(2014\)Intriguing properties of neural networks\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[Remark B\.1](https://arxiv.org/html/2605.30461#A2.Thmtheorem1.p2.9)\.
- M\. Towers, A\. Kwiatkowski, J\. Terry, J\. U\. Balis, G\. De Cola, T\. Deleu, M\. Goulão, A\. Kallinteris, M\. Krimmel, A\. KG, R\. Perez\-Vicente, A\. Pierré, S\. Schulhoff, J\. J\. Tai, H\. Tan, and O\. G\. Younis \(2024\)Gymnasium: a standard interface for reinforcement learning environments\.arXiv preprint arXiv:2407\.17032\.Cited by:[§7](https://arxiv.org/html/2605.30461#S7.p1.4)\.
- J\. R\. Vázquez\-Canteli, S\. Dey, G\. Henze, and Z\. Nagy \(2020\)CityLearn: standardizing research in multi\-agent reinforcement learning for demand response and urban energy management\.arXiv preprint arXiv:2012\.10504\.Cited by:[§6](https://arxiv.org/html/2605.30461#S6.p5.5)\.
- J\. R\. Vázquez\-Canteli, J\. Kämpf, G\. Henze, and Z\. Nagy \(2019\)CityLearn v1\.0: an OpenAI Gym environment for demand response with deep reinforcement learning\.InProceedings of the 6th ACM International Conference on Systems for Energy\-Efficient Buildings, Cities, and Transportation \(BuildSys ’19\),New York, NY, USA,pp\. 356–357\.External Links:[Document](https://dx.doi.org/10.1145/3360322.3360998)Cited by:[§6](https://arxiv.org/html/2605.30461#S6.p5.5)\.
- D\. Wang, X\. Wu, Z\. Ou, and J\. Lu \(2024\)Globally\-constrained decentralized optimization with variable coupling\.arXiv preprint arXiv:2407\.10770\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p5.2),[Remark 4\.1](https://arxiv.org/html/2605.30461#S4.Thmtheorem1.p1.1)\.
- J\. Wang, Z\. Ren, T\. Liu, Y\. Yu, and C\. Zhang \(2021\)QPLEX: duplex dueling multi\-agent Q\-learning\.InInternational Conference on Learning Representations \(ICLR\),Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p2.1)\.
- X\. Wang, S\. Liu, Q\. Xu, and X\. Shao \(2025\)Distributed multi\-agent reinforcement learning for multi\-objective optimal dispatch of microgrids\.ISA Transactions158,pp\. 130–140\.External Links:[Document](https://dx.doi.org/10.1016/j.isatra.2025.01.009)Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p3.1),[§2](https://arxiv.org/html/2605.30461#S2.p5.2)\.
- L\. Xiao and S\. Boyd \(2003\)Fast linear iterations for distributed averaging\.In42nd IEEE Conference on Decision and Control,Vol\.5,pp\. 4997–5002\.Cited by:[§A\.1](https://arxiv.org/html/2605.30461#A1.SS1.p1.1),[Remark 4\.1](https://arxiv.org/html/2605.30461#S4.Thmtheorem1.p1.1)\.
- D\. Yarmoshik, A\. Rogozin, N\. Kiselev, D\. Dorin, A\. Gasnikov, and D\. Kovalev \(2024\)Decentralized optimization with coupled constraints\.arXiv preprint arXiv:2407\.02020\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p5.2),[Remark 4\.1](https://arxiv.org/html/2605.30461#S4.Thmtheorem1.p1.1)\.
- D\. Ying, Y\. Zhang, Y\. Ding, A\. Koppel, and J\. Lavaei \(2023\)Scalable primal\-dual actor\-critic method for safe multi\-agent RL with general utilities\.InAdvances in Neural Information Processing Systems,Vol\.36\.Cited by:[Table 1](https://arxiv.org/html/2605.30461#S2.T1.10.4.2),[§2](https://arxiv.org/html/2605.30461#S2.p4.1),[§2](https://arxiv.org/html/2605.30461#S2.p7.1)\.
- C\. Yu, A\. Velu, E\. Vinitsky, J\. Gao, Y\. Wang, A\. Bayen, and Y\. Wu \(2022\)The surprising effectiveness of PPO in cooperative multi\-agent games\.Advances in Neural Information Processing Systems35,pp\. 24611–24624\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p2.1)\.
- K\. Zhang, Z\. Yang, H\. Liu, T\. Zhang, and T\. Başar \(2018\)Fully decentralized multi\-agent reinforcement learning with networked agents\.InProceedings of the 35th International Conference on Machine Learning,Proceedings of Machine Learning Research, Vol\.80,pp\. 5872–5881\.Cited by:[§2](https://arxiv.org/html/2605.30461#S2.p3.1)\.
- L\. Zhang, L\. Li, W\. Wei, H\. Song, Y\. Yang, and J\. Liang \(2024\)Scalable constrained policy optimization for safe multi\-agent reinforcement learning\.InAdvances in Neural Information Processing Systems,A\. Globerson, L\. Mackey, D\. Belgrave, A\. Fan, U\. Paquet, J\. Tomczak, and C\. Zhang \(Eds\.\),Vol\.37,pp\. 138698–138730\.External Links:[Link](https://proceedings.neurips.cc/paper_files/paper/2024/file/fa76985f05e0a25c66528308dda33de0-Paper-Conference.pdf)Cited by:[Table 1](https://arxiv.org/html/2605.30461#S2.T1.11.5.2),[§2](https://arxiv.org/html/2605.30461#S2.p4.1),[§2](https://arxiv.org/html/2605.30461#S2.p7.1),[Remark 3\.4](https://arxiv.org/html/2605.30461#S3.Thmtheorem4.p1.2),[§7\.2](https://arxiv.org/html/2605.30461#S7.SS2.SSS0.Px1.p3.1)\.

## Appendix ATheoretical Analysis

### A\.1Convergence of the Consensus Algorithm

In this section, we provide a rigorous analysis of the convergence properties of the consensus algorithm employed in our distributed optimization framework\. The convergence properties of consensus algorithms over networks are well\-studied in the literature\(Olfati\-Saber and Murray,[2004](https://arxiv.org/html/2605.30461#bib.bib16); Olfati\-Saberet al\.,[2007](https://arxiv.org/html/2605.30461#bib.bib17); Xiao and Boyd,[2003](https://arxiv.org/html/2605.30461#bib.bib4)\)\. Our analysis follows standard techniques in distributed optimization and consensus algorithms, as well as properties of graph Laplacians and their spectra\(Chung,[1997](https://arxiv.org/html/2605.30461#bib.bib6)\)\. Specifically, we leverage results from spectral graph theory and matrix analysis to establish the exponential convergence of our algorithm\. We examine how the local dual variablesλi\\lambda^\{i\}converge to a consensus value, ensuring coordination among agents while satisfying global constraints\.

#### A\.1\.1Consensus Update Rule

The consensus update for agentiiat iterationℓ\\ellcan be written in a standard form for consensus algorithms:

λℓ\+1i\\displaystyle\\lambda^\{i\}\_\{\\ell\+1\}=λℓi−ϵ​\(λℓi−1\|𝒩i\|​∑j∈𝒩iλℓj\),\\displaystyle=\\lambda^\{i\}\_\{\\ell\}\-\\epsilon\\left\(\\lambda^\{i\}\_\{\\ell\}\-\\frac\{1\}\{\|\\mathcal\{N\}^\{i\}\|\}\\sum\_\{j\\in\\mathcal\{N\}^\{i\}\}\\lambda^\{j\}\_\{\\ell\}\\right\),=λℓi−ϵ​\(1\|𝒩i\|​∑j∈𝒩i\(λℓi−λℓj\)\),\\displaystyle=\\lambda^\{i\}\_\{\\ell\}\-\\epsilon\\left\(\\frac\{1\}\{\|\\mathcal\{N\}^\{i\}\|\}\\sum\_\{j\\in\\mathcal\{N\}^\{i\}\}\(\\lambda^\{i\}\_\{\\ell\}\-\\lambda^\{j\}\_\{\\ell\}\)\\right\),=λℓi−ϵ​∑j∈𝒩i1\|𝒩i\|​\(λℓi−λℓj\)\.\\displaystyle=\\lambda^\{i\}\_\{\\ell\}\-\\epsilon\\sum\_\{j\\in\\mathcal\{N\}^\{i\}\}\\frac\{1\}\{\|\\mathcal\{N\}^\{i\}\|\}\\left\(\\lambda^\{i\}\_\{\\ell\}\-\\lambda^\{j\}\_\{\\ell\}\\right\)\.\(A\.1\)whereϵ\>0\\epsilon\>0is the consensus step size\. This update rule adjusts each agent’s dual variable towards the average of its neighbors’ dual variables\.

#### A\.1\.2Matrix Formulation

We consider a communication network among the agents, given by an undirected graphG=\(V,E\)G=\(V,E\), whereVVis the set of vertices \(agents\) andE⊂V×VE\\subset V\\times Vis the set of edges \(communication links between agents\)\. The neighborhood of a nodei∈Vi\\in V, denoted by𝒩i\\mathcal\{N\}^\{i\}, is the set of nodes that are directly connected to nodeiiby an edge; i\.e\.,𝒩i=\{j∈V∣\(i,j\)∈E\}\\mathcal\{N\}^\{i\}=\\\{j\\in V\\mid\(i,j\)\\in E\\\}\.

We aim to express the collective updates in matrix form to facilitate the convergence analysis\. To do this, we first define the necessary matrices and vectors\.

Letλℓ=\[λℓ1,λℓ2,…,λℓN\]T∈ℝN\\lambda\_\{\\ell\}=\[\\lambda^\{1\}\_\{\\ell\},\\lambda^\{2\}\_\{\\ell\},\\dots,\\lambda^\{N\}\_\{\\ell\}\]^\{T\}\\in\\mathbb\{R\}^\{N\}be the global vector of local dual variables at iterationℓ\\ell, and let𝟏∈ℝN\\mathbf\{1\}\\in\\mathbb\{R\}^\{N\}be a vector of ones\. We denote byA∈ℝN×NA\\in\\mathbb\{R\}^\{N\\times N\}the adjacency matrix of the graph, where

A​\(i,j\)=\{1,if​\(i,j\)∈E,0,otherwise,A\(i,j\)\\;=\\;\\begin\{cases\}1,&\\text\{if \}\(i,j\)\\in E,\\\\ 0,&\\text\{otherwise\},\\end\{cases\}\(A\.2\)and byD∈ℝN×ND\\in\\mathbb\{R\}^\{N\\times N\}the diagonal degree matrix withD​\(i,i\)=\|𝒩i\|D\(i,i\)=\|\\mathcal\{N\}^\{i\}\|\. We define the \(unnormalized\) graph Laplacian asL=D−AL=D\-A, and the random\-walk normalized Laplacian asLrw=D−1​L=I−D−1​AL^\{\\mathrm\{rw\}\}=D^\{\-1\}L=I\-D^\{\-1\}A\.

Then the update ofλℓ\+1\\lambda\_\{\\ell\+1\}in vector form is:

λℓ\+1\\displaystyle\\lambda\_\{\\ell\+1\}=λℓ−ϵ​\(λℓ−D−1​A​λℓ\),\\displaystyle=\\lambda\_\{\\ell\}\-\\epsilon\\left\(\\lambda\_\{\\ell\}\-D^\{\-1\}A\\lambda\_\{\\ell\}\\right\),=λℓ−ϵ​Lrw​λℓ,\\displaystyle=\\lambda\_\{\\ell\}\-\\epsilon L^\{\\text\{rw\}\}\\lambda\_\{\\ell\},=P​λℓ,\\displaystyle=P\\lambda\_\{\\ell\},\(A\.3\)whereP=I−ϵ​LrwP=I\-\\epsilon L^\{\\text\{rw\}\}is the*Perron matrix*, andIIis the identity matrix\. The graph LaplacianLrwL^\{\\text\{rw\}\}captures the connectivity of the communication network among agents\.

#### A\.1\.3Assumptions for Convergence

To analyze the convergence of the consensus algorithm, we make the following assumptions:

###### Assumption A\.1\(Connected Graph\)\.

The communication graphG=\(V,E\)G=\(V,E\)is undirected and connected; that is, there exists a path between any pair of agents\.

###### Assumption A\.2\(Step Size\)\.

The consensus step sizeϵ\\epsilonsatisfies0<ϵ<10<\\epsilon<1, ensuring thatPPremains a stochastic matrix with non\-negative entries\.

Assumption[A\.1](https://arxiv.org/html/2605.30461#A1.Thmtheorem1)ensures that information can propagate through the network, which is necessary for achieving global consensus\. Assumption[A\.2](https://arxiv.org/html/2605.30461#A1.Thmtheorem2)provides a bound on the step size to guarantee convergence\.

#### A\.1\.4Convergence Analysis

We analyze the convergence of the consensus algorithm by examining the properties of the Perron matrixPP\.

###### Lemma A\.3\(Properties of the Perron Matrix\)\.

Under Assumptions[A\.1](https://arxiv.org/html/2605.30461#A1.Thmtheorem1)and[A\.2](https://arxiv.org/html/2605.30461#A1.Thmtheorem2), the Perron matrixP=I−ϵ​LrwP=I\-\\epsilon L^\{\\text\{rw\}\}satisfies the following properties: \(a\)PPis row\-stochastic and irreducible\. \(b\)The eigenvalues ofPPareνi=1−ϵ​Λi\\nu\_\{i\}=1\-\\epsilon\\Lambda\_\{i\}, whereΛi\\Lambda\_\{i\}are the eigenvalues of the LaplacianLrwL^\{\\text\{rw\}\}\. \(c\)All eigenvalues ofPPsatisfy\|νi\|≤1\|\\nu\_\{i\}\|\\leq 1, the eigenvalueν1=1\\nu\_\{1\}=1has algebraic multiplicity one, and all other eigenvalues satisfy\|νi\|<1\|\\nu\_\{i\}\|<1\.

###### Proof\.

\(a\) Row\-Stochasticity and Irreducibility:The elements ofPPare given by

P​\(i,j\)=\{1−ϵ,if​i=j,ϵ\|𝒩i\|,if​\(i,j\)∈E,0,otherwise\.P\(i,j\)=\\begin\{cases\}1\-\\epsilon,&\\text\{if \}i=j,\\\\ \\frac\{\\epsilon\}\{\|\\mathcal\{N\}^\{i\}\|\},&\\text\{if \}\(i,j\)\\in E,\\\\ 0,&\\text\{otherwise\}\.\\end\{cases\}For each rowii, the sum of the entries is

∑j=1NP​\(i,j\)\\displaystyle\\sum\_\{j=1\}^\{N\}P\(i,j\)=P​\(i,i\)\+∑j∈𝒩iP​\(i,j\)\\displaystyle=P\(i,i\)\+\\sum\_\{j\\in\\mathcal\{N\}^\{i\}\}P\(i,j\)=\(1−ϵ\)\+∑j∈𝒩iϵ\|𝒩i\|\\displaystyle=\(1\-\\epsilon\)\+\\sum\_\{j\\in\\mathcal\{N\}^\{i\}\}\\frac\{\\epsilon\}\{\|\\mathcal\{N\}^\{i\}\|\}=\(1−ϵ\)\+ϵ​\|𝒩i\|\|𝒩i\|\\displaystyle=\(1\-\\epsilon\)\+\\epsilon\\frac\{\|\\mathcal\{N\}^\{i\}\|\}\{\|\\mathcal\{N\}^\{i\}\|\}=\(1−ϵ\)\+ϵ=1\.\\displaystyle=\(1\-\\epsilon\)\+\\epsilon=1\.Thus,PPis row\-stochastic\. Since the graphGGis connected \(Assumption[A\.1](https://arxiv.org/html/2605.30461#A1.Thmtheorem1)\), andPPis non\-negative, it follows thatPPis irreducible\.

\(b\) Eigenvalues ofPP:LetΛi\\Lambda\_\{i\}be the eigenvalues ofLrwL^\{\\text\{rw\}\}with corresponding eigenvectorsviv\_\{i\}\. Then,

Lrw​vi=Λi​vi\.L^\{\\text\{rw\}\}v\_\{i\}=\\Lambda\_\{i\}v\_\{i\}\.Therefore,

P​vi=\(I−ϵ​Lrw\)​vi=vi−ϵ​Lrw​vi=vi−ϵ​Λi​vi=\(1−ϵ​Λi\)​vi\.Pv\_\{i\}=\(I\-\\epsilon L^\{\\text\{rw\}\}\)v\_\{i\}=v\_\{i\}\-\\epsilon L^\{\\text\{rw\}\}v\_\{i\}=v\_\{i\}\-\\epsilon\\Lambda\_\{i\}v\_\{i\}=\(1\-\\epsilon\\Lambda\_\{i\}\)v\_\{i\}\.Thus, the eigenvalues ofPPareνi=1−ϵ​Λi\\nu\_\{i\}=1\-\\epsilon\\Lambda\_\{i\}\.

\(c\) Eigenvalues within\[−1,1\]\[\-1,1\]:Since the random\-walk LaplacianLrwL^\{\\mathrm\{rw\}\}is similar to the symmetric normalized Laplacian

Lsym=D−12​L​D−12L^\{\\mathrm\{sym\}\}\\;=\\;D^\{\-\\tfrac\{1\}\{2\}\}\\,L\\,D^\{\-\\tfrac\{1\}\{2\}\}via

Lsym=D12​Lrw​D−12,L^\{\\mathrm\{sym\}\}\\;=\\;D^\{\\tfrac\{1\}\{2\}\}\\,L^\{\\mathrm\{rw\}\}\\,D^\{\-\\tfrac\{1\}\{2\}\},they share the same set of eigenvalues\{Λi\}\\\{\\Lambda\_\{i\}\\\}\.

To see this more explicitly, letΛi\\Lambda\_\{i\}andviv\_\{i\}be an eigenvalue–eigenvector pair ofLsymL^\{\\mathrm\{sym\}\}, i\.e\.,

Lsym​vi=Λi​vi⟺\(I−D−12​A​D−12\)​vi=Λi​vi\.L^\{\\mathrm\{sym\}\}\\,v\_\{i\}\\;=\\;\\Lambda\_\{i\}\\,v\_\{i\}\\quad\\Longleftrightarrow\\quad\\bigl\(I\\;\-\\;D^\{\-\\tfrac\{1\}\{2\}\}A\\,D^\{\-\\tfrac\{1\}\{2\}\}\\bigr\)\\,v\_\{i\}\\;=\\;\\Lambda\_\{i\}\\,v\_\{i\}\.Pre\-multiplying both sides byD−12D^\{\-\\tfrac\{1\}\{2\}\}gives

\(D−12−D−1​A​D−12\)​vi=Λi​D−12​vi⟺\(I−D−1​A\)​D−12​vi=Λi​D−12​vi\.\\bigl\(D^\{\-\\tfrac\{1\}\{2\}\}\\;\-\\;D^\{\-1\}A\\,D^\{\-\\tfrac\{1\}\{2\}\}\\bigr\)\\,v\_\{i\}\\;=\\;\\Lambda\_\{i\}\\,D^\{\-\\tfrac\{1\}\{2\}\}\\,v\_\{i\}\\quad\\Longleftrightarrow\\quad\\bigl\(I\\;\-\\;D^\{\-1\}A\\bigr\)\\,D^\{\-\\tfrac\{1\}\{2\}\}\\,v\_\{i\}\\;=\\;\\Lambda\_\{i\}\\,D^\{\-\\tfrac\{1\}\{2\}\}\\,v\_\{i\}\.Recalling thatLrw=I−D−1​AL^\{\\mathrm\{rw\}\}=I\-D^\{\-1\}A, it follows that

Lrw​\(D−12​vi\)=Λi​\(D−12​vi\)\.L^\{\\mathrm\{rw\}\}\\,\\bigl\(D^\{\-\\tfrac\{1\}\{2\}\}\\,v\_\{i\}\\bigr\)\\;=\\;\\Lambda\_\{i\}\\,\\bigl\(D^\{\-\\tfrac\{1\}\{2\}\}\\,v\_\{i\}\\bigr\)\.Hence, if\(Λi,vi\)\(\\Lambda\_\{i\},v\_\{i\}\)is an eigenvalue–eigenvector pair ofLsymL^\{\\mathrm\{sym\}\}, then the sameΛi\\Lambda\_\{i\}andD−12​viD^\{\-\\tfrac\{1\}\{2\}\}v\_\{i\}form an eigenvalue–eigenvector pair ofLrwL^\{\\mathrm\{rw\}\}\. Therefore, both matrices share the same eigenvalues\. We can establish the following facts:

1. 1\.Real symmetry and positive semidefiniteness:The matrixLsymL^\{\\mathrm\{sym\}\}is real symmetric \(sinceLLis symmetric andD−1/2D^\{\-1/2\}is diagonal\)\. Then,LsymL^\{\\mathrm\{sym\}\}is diagonalizable, and its eigenvalues are real\. Standard results in spectral graph theory further showLsymL^\{\\mathrm\{sym\}\}is positive semidefinite, implying its eigenvalues are nonnegative\(Chung,[1997](https://arxiv.org/html/2605.30461#bib.bib6); Godsil and Royle,[2001](https://arxiv.org/html/2605.30461#bib.bib10)\)\.
2. 2\.Eigenvalues in\[0,2\]\[0,2\]:From classical bounds on the spectrum ofLsymL^\{\\mathrm\{sym\}\}\(e\.g\., using the structure of the degree and adjacency matrices\), one obtains 0=Λ1≤Λ2≤⋯≤ΛN≤2\(Horn and Johnson,[2012](https://arxiv.org/html/2605.30461#bib.bib36); Moharet al\.,[1991](https://arxiv.org/html/2605.30461#bib.bib11)\)\.0=\\Lambda\_\{1\}\\leq\\Lambda\_\{2\}\\leq\\cdots\\leq\\Lambda\_\{N\}\\leq 2\\quad\\text\{\\cite\[citep\]\{\(\\@@bibref\{AuthorsPhrase1Year\}\{hornJohn,GoodGraphTheory\}\{\\@@citephrase\{, \}\}\{\}\)\}\}\.The eigenvalues ofLrwL^\{\\mathrm\{rw\}\}also lie in\[0,2\]\[0,2\]\.

Because0≤Λi≤20\\leq\\Lambda\_\{i\}\\leq 2and0<ϵ<10<\\epsilon<1, we have

\|νi\|=\|1−ϵ​Λi\|≤1,\|\\nu\_\{i\}\|=\|1\-\\epsilon\\Lambda\_\{i\}\|\\leq 1,
SinceGGis connected, the multiplicity of the zero eigenvalue ofLrwL^\{\\text\{rw\}\}is one, so the eigenvalueν1=1\\nu\_\{1\}=1ofPPhas algebraic multiplicity one\. Since there are no complex eigenvalues \(Ls​y​mL^\{sym\}is real and symmetric\), all other eigenvalues satisfy\|νi\|<1\|\\nu\_\{i\}\|<1fori≥2i\\geq 2\. Hence, all eigenvalues ofPPlie in\[−1,1\]\[\-1,1\]\.

This ensures that the spectral radius ofPPisρ​\(P\)=1\\rho\(P\)=1, and the convergence of the consensus algorithm is governed by the second\-largest eigenvalue in magnitude, which is less than 1\. ∎

### A\.2Global Consensus Error

We analyze the convergence of the consensus algorithm by first establishing the value to which it converges, and then proving the rate of convergence\.

#### A\.2\.1Consensus Value

###### Lemma A\.4\(Consensus Value\)\.

Under Assumption[A\.1](https://arxiv.org/html/2605.30461#A1.Thmtheorem1), the consensus algorithm converges to a weighted average of the initial dual variables\. Specifically, for any initial vectorλ0∈ℝN\\lambda\_\{0\}\\in\\mathbb\{R\}^\{N\},

limℓ→∞λℓ=λ^​𝟏,\\lim\_\{\\ell\\to\\infty\}\\lambda\_\{\\ell\}=\\hat\{\\lambda\}\\mathbf\{1\},where

λ^=∑i=1Nwi​λ0i,\\hat\{\\lambda\}=\\sum\_\{i=1\}^\{N\}w^\{i\}\\lambda\_\{0\}^\{i\},and the weightswiw^\{i\}are given by

wi=\|𝒩i\|∑j=1N\|𝒩j\|\.w^\{i\}=\\frac\{\|\\mathcal\{N\}^\{i\}\|\}\{\\sum\_\{j=1\}^\{N\}\|\\mathcal\{N\}^\{j\}\|\}\.

###### Proof\.

By the Perron\-Frobenius theorem\(Horn and Johnson,[2012](https://arxiv.org/html/2605.30461#bib.bib36)\), sincePPis a primitive nonnegative matrix, it satisfies

limℓ→∞Pℓ=𝐯1​𝐰1⊤,\\lim\_\{\\ell\\to\\infty\}P^\{\\ell\}=\\mathbf\{v\}\_\{1\}\\mathbf\{w\}\_\{1\}^\{\\top\},where𝐯1=𝟏\\mathbf\{v\}\_\{1\}=\\mathbf\{1\}is the right eigenvector corresponding to the eigenvalue11, and𝐰1\\mathbf\{w\}\_\{1\}is the unique left eigenvector satisfying𝐰1⊤​P=𝐰1⊤\\mathbf\{w\}\_\{1\}^\{\\top\}P=\\mathbf\{w\}\_\{1\}^\{\\top\}with𝐯1⊤​𝐰1=1\\mathbf\{v\}\_\{1\}^\{\\top\}\\mathbf\{w\}\_\{1\}=1\.

The consensus iteration is given by

λℓ=Pℓ​λ0\.\\lambda\_\{\\ell\}=P^\{\\ell\}\\lambda\_\{0\}\.\(A\.4\)Taking the limit asℓ→∞\\ell\\to\\infty,

limℓ→∞λℓ=limℓ→∞Pℓ​λ0=𝐯1​𝐰1⊤​λ0=𝟏​\(𝐰1⊤​λ0\)=λ^​𝟏\.\\lim\_\{\\ell\\to\\infty\}\\lambda\_\{\\ell\}=\\lim\_\{\\ell\\to\\infty\}P^\{\\ell\}\\lambda\_\{0\}=\\mathbf\{v\}\_\{1\}\\mathbf\{w\}\_\{1\}^\{\\top\}\\lambda\_\{0\}=\\mathbf\{1\}\(\\mathbf\{w\}\_\{1\}^\{\\top\}\\lambda\_\{0\}\)=\\hat\{\\lambda\}\\mathbf\{1\}\.This shows that all agents’ dual variables converge to the scalarλ^\\hat\{\\lambda\}, which is a weighted average of the initial values\.

To explicitly determine𝐰1\\mathbf\{w\}\_\{1\}, consider the transition matrixPrw=D−1​AP^\{\\text\{rw\}\}=D^\{\-1\}A, associated with the random walk normalized LaplacianLr​wL^\{rw\}whereAAis the adjacency matrix andDDis the degree matrix\. For an undirected graph,PrwP^\{\\text\{rw\}\}satisfies the detailed balance condition\(Levinet al\.,[2009](https://arxiv.org/html/2605.30461#bib.bib40)\):

wi​Pi​jrw=wj​Pj​irw\.w^\{i\}P^\{\\text\{rw\}\}\_\{ij\}=w^\{j\}P^\{\\text\{rw\}\}\_\{ji\}\.SubstitutingPr​w​\(i,j\)=A​\(i,j\)\|𝒩i\|P^\{rw\}\(i,j\)=\\frac\{A\(i,j\)\}\{\|\\mathcal\{N\}^\{i\}\|\}andPr​w​\(j,i\)=A​\(j,i\)\|𝒩j\|P^\{rw\}\(j,i\)=\\frac\{A\(j,i\)\}\{\|\\mathcal\{N\}^\{j\}\|\}, and sinceA​\(i,j\)=A​\(j,i\)A\(i,j\)=A\(j,i\)for undirected graphs, we obtain

wi\|𝒩i\|\\displaystyle\\frac\{w^\{i\}\}\{\|\\mathcal\{N\}^\{i\}\|\}=wj\|𝒩j\|=c,\\displaystyle=\\frac\{w^\{j\}\}\{\|\\mathcal\{N\}^\{j\}\|\}=c,wi\\displaystyle w^\{i\}=c​\|𝒩i\|\\displaystyle=c\|\\mathcal\{N\}^\{i\}\|Since∑i=1Nwi=1\\sum\_\{i=1\}^\{N\}w^\{i\}=1, this implies that

c=1∑i=1N\|𝒩i\|,c=\\frac\{1\}\{\\sum\_\{i=1\}^\{N\}\|\\mathcal\{N\}^\{i\}\|\},
Therefore, the consensus value is

λ^=∑i=1Nwi​λ0i=∑i=1N\|𝒩i\|​λ0i∑i=1N\|𝒩i\|,\\hat\{\\lambda\}=\\sum\_\{i=1\}^\{N\}w^\{i\}\\lambda\_\{0\}^\{i\}=\\frac\{\\sum\_\{i=1\}^\{N\}\|\\mathcal\{N\}^\{i\}\|\\lambda\_\{0\}^\{i\}\}\{\\sum\_\{i=1\}^\{N\}\|\\mathcal\{N\}^\{i\}\|\},which is the degree\-weighted average of the initial dual variables\. ∎

#### A\.2\.2Convergence Rate

We now establish the exponential convergence rate to the consensus valueλ^\\hat\{\\lambda\}\.

###### Theorem A\.5\(Exponential Convergence to Consensus\)\.

Under Assumptions[A\.1](https://arxiv.org/html/2605.30461#A1.Thmtheorem1)and[A\.2](https://arxiv.org/html/2605.30461#A1.Thmtheorem2), the consensus algorithm converges exponentially fast toλ^​𝟏\\hat\{\\lambda\}\\mathbf\{1\}\. Specifically, for any initial vectorλ0∈ℝN\\lambda\_\{0\}\\in\\mathbb\{R\}^\{N\},

‖λℓ−λ^​𝟏‖≤C​ρℓ​‖λ0−λ^​𝟏‖,\\\|\\lambda\_\{\\ell\}\-\\hat\{\\lambda\}\\mathbf\{1\}\\\|\\leq C\\rho^\{\\ell\}\\\|\\lambda\_\{0\}\-\\hat\{\\lambda\}\\mathbf\{1\}\\\|,\(A\.5\)where:

- •ρ=maxi≥2⁡\|νi\|<1\\rho=\\max\_\{i\\geq 2\}\|\\nu\_\{i\}\|<1whereνi\\nu\_\{i\}are the eigenvalues of P\.
- •C=κ​\(V\)=‖V‖​‖V−1‖C=\\kappa\(V\)=\\\|V\\\|\\\|V^\{\-1\}\\\|is the condition number of the eigenvector matrixVV\.

###### Proof\.

Define the error vector at iterationℓ\\ellas:

eℓ=λℓ−λ^​𝟏\.e\_\{\\ell\}=\\lambda\_\{\\ell\}\-\\hat\{\\lambda\}\\mathbf\{1\}\.From Lemma[A\.4](https://arxiv.org/html/2605.30461#A1.Thmtheorem4), we havelimℓ→∞eℓ=𝟎\\lim\_\{\\ell\\to\\infty\}e\_\{\\ell\}=\\mathbf\{0\}\.

The consensus update rule is:

λℓ\+1=P​λℓ,\\lambda\_\{\\ell\+1\}=P\\lambda\_\{\\ell\},which implies:

eℓ\+1=P​eℓ\.e\_\{\\ell\+1\}=Pe\_\{\\ell\}\.Iterating this, we obtain:

eℓ=Pℓ​e0\.e\_\{\\ell\}=P^\{\\ell\}e\_\{0\}\.
SincePPis diagonalizable, we can express it as:

P=V​Γ​V−1,P=V\\Gamma V^\{\-1\},where:

- •VVis the matrix of right eigenvectors ofPP\.
- •Γ=diag⁡\(ν1,ν2,…,νN\)\\Gamma=\\operatorname\{diag\}\(\\nu\_\{1\},\\nu\_\{2\},\\dots,\\nu\_\{N\}\)contains the eigenvalues ofPP, withνi=1−ϵ​Λi\\nu\_\{i\}=1\-\\epsilon\\Lambda\_\{i\}\.

Substituting into the error expression:

eℓ=V​Γℓ​V−1​e0\.e\_\{\\ell\}=V\\Gamma^\{\\ell\}V^\{\-1\}e\_\{0\}\.\(A\.6\)
In the degree\-weighted consensus setting, for eigenvalue11, the matrixPPhas𝟏\\mathbf\{1\}as its right eigenvector, while its left eigenvector is𝐰1\\mathbf\{w\}\_\{1\}\. By definition, the initial error ise0=λ0−λ^​1e\_\{0\}=\\lambda\_\{0\}\-\\hat\{\\lambda\}\\,\\mathbf\{1\}\(whereλ^\\hat\{\\lambda\}is the weighted average\), we then have

𝐰1⊤​e0=∑i=1Nwi​\(λ0i−λ^\)=0\.\\mathbf\{w\}\_\{1\}^\{\\top\}e\_\{0\}=\\sum\_\{i=1\}^\{N\}w^\{i\}\(\\lambda\_\{0\}^\{i\}\-\\hat\{\\lambda\}\)=0\.
Thus,e0e\_\{0\}lies in the subspace orthogonal to𝐰1\\mathbf\{w\}\_\{1\}\. Sinceeℓ=Pℓ​e0e\_\{\\ell\}=P^\{\\ell\}e\_\{0\}and𝐰1⊤​P=𝐰1⊤\\mathbf\{w\}\_\{1\}^\{\\top\}P=\\mathbf\{w\}\_\{1\}^\{\\top\}, it follows that

𝐰1⊤​eℓ=𝐰1⊤​Pℓ​e0=𝐰1⊤​e0=0for all​ℓ\.\\mathbf\{w\}\_\{1\}^\{\\top\}e\_\{\\ell\}=\\mathbf\{w\}\_\{1\}^\{\\top\}P^\{\\ell\}e\_\{0\}=\\mathbf\{w\}\_\{1\}^\{\\top\}e\_\{0\}=0\\quad\\text\{for all \}\\ell\.
Hence, the error remains in the subspace orthogonal to𝐰1\\mathbf\{w\}\_\{1\}at every iteration, allowing us to exclude the dominant component in the consensus convergence analysis\. Thus,

eℓ=Vred​Γredℓ​Vred−1​e0,e\_\{\\ell\}=V\_\{\\text\{red\}\}\\Gamma\_\{\\text\{red\}\}^\{\\ell\}V\_\{\\text\{red\}\}^\{\-1\}e\_\{0\},where:

- •VredV\_\{\\text\{red\}\}consists of eigenvectors corresponding toνi\\nu\_\{i\}fori≥2i\\geq 2\.
- •Γred=diag⁡\(ν2,ν3,…,νN\)\\Gamma\_\{\\text\{red\}\}=\\operatorname\{diag\}\(\\nu\_\{2\},\\nu\_\{3\},\\dots,\\nu\_\{N\}\)\.

To bound the norm of the error, we apply the sub\-multiplicative property of matrix norms:

‖eℓ‖≤‖Vred‖​‖Γredℓ‖​‖Vred−1‖​‖e0‖\.\\\|e\_\{\\ell\}\\\|\\leq\\\|V\_\{\\text\{red\}\}\\\|\\\|\\Gamma\_\{\\text\{red\}\}^\{\\ell\}\\\|\\\|V\_\{\\text\{red\}\}^\{\-1\}\\\|\\\|e\_\{0\}\\\|\.Since‖Γredℓ‖2=ρℓ\\\|\\Gamma\_\{\\text\{red\}\}^\{\\ell\}\\\|\_\{2\}=\\rho^\{\\ell\}, whereρ=maxi≥2⁡\|νi\|\\rho=\\max\_\{i\\geq 2\}\|\\nu\_\{i\}\|, we have:

‖eℓ‖≤‖V‖​‖V−1‖​ρℓ​‖e0‖=C​ρℓ​‖e0‖,\\\|e\_\{\\ell\}\\\|\\leq\\\|V\\\|\\\|V^\{\-1\}\\\|\\rho^\{\\ell\}\\\|e\_\{0\}\\\|=C\\rho^\{\\ell\}\\\|e\_\{0\}\\\|,whereC=κ​\(V\)=‖V‖​‖V−1‖C=\\kappa\(V\)=\\\|V\\\|\\\|V^\{\-1\}\\\|is the condition number ofVV\.

Sinceρ<1\\rho<1, the error decays exponentially:

‖eℓ‖≤C​ρℓ​‖e0‖,\\\|e\_\{\\ell\}\\\|\\leq C\\rho^\{\\ell\}\\\|e\_\{0\}\\\|,confirming that the consensus algorithm converges exponentially fast toλ^​𝟏\\hat\{\\lambda\}\\mathbf\{1\}\. ∎

#### A\.2\.3Bounding the Global Consensus Error

We aim to bound the consensus errorek\+1=λk\+1−λ^k\+1​𝟏e\_\{k\+1\}=\\lambda\_\{k\+1\}\-\\hat\{\\lambda\}\_\{k\+1\}\\mathbf\{1\}, whereλ^k\+1\\hat\{\\lambda\}\_\{k\+1\}is the weighted average ofλk\+1i\\lambda\_\{k\+1\}^\{i\}\.

###### Lemma A\.6\(Consensus Error Recursion\)\.

Under Assumptions[A\.1](https://arxiv.org/html/2605.30461#A1.Thmtheorem1)and[A\.2](https://arxiv.org/html/2605.30461#A1.Thmtheorem2), the magnitude of the consensus error satisfies the recursion

‖ek\+1‖≤‖Pℒ‖​‖\(ek\+α​Δ​V1,k\)‖,\\left\\\|e\_\{k\+1\}\\right\\\|\\leq\\left\\\|P^\{\\mathscr\{L\}\}\\right\\\|\\left\\\|\\left\(e\_\{k\}\+\\alpha\\Delta V\_\{1,k\}\\right\)\\right\\\|,\(A\.7\)whereΔ​V1,k=V1,k−V^1,k​𝟏\\Delta V\_\{1,k\}=V\_\{1,k\}\-\\hat\{V\}\_\{1,k\}\\mathbf\{1\}andV^1,k=∑i=1N\|𝒩i\|​V1,ki∑i=1N\|𝒩i\|\\hat\{V\}\_\{1,k\}=\\frac\{\\sum\_\{i=1\}^\{N\}\|\\mathcal\{N\}^\{i\}\|V\_\{1,k\}^\{i\}\}\{\\sum\_\{i=1\}^\{N\}\|\\mathcal\{N\}^\{i\}\|\}\.

###### Proof\.

From the gradient descent step,

λk\+12i=\[λki−α​\(cN−V1,ki\)\]\+\.\\lambda\_\{k\+\\frac\{1\}\{2\}\}^\{i\}=\\left\[\\lambda\_\{k\}^\{i\}\-\\alpha\\left\(\\frac\{c\}\{N\}\-V\_\{1,k\}^\{i\}\\right\)\\right\]\_\{\+\}\.The weighted average is

λ^k\+12\\displaystyle\\hat\{\\lambda\}\_\{k\+\\frac\{1\}\{2\}\}=∑i=1Nwi​λk\+12i\.\\displaystyle=\\sum\_\{i=1\}^\{N\}w^\{i\}\\lambda\_\{k\+\\frac\{1\}\{2\}\}^\{i\}\.=∑i=1Nwi​\[λki−α​\(cN−V1,ki\)\]\+\.\\displaystyle=\\sum\_\{i=1\}^\{N\}w^\{i\}\\left\[\\lambda\_\{k\}^\{i\}\-\\alpha\\left\(\\frac\{c\}\{N\}\-V\_\{1,k\}^\{i\}\\right\)\\right\]\_\{\+\}\.Using the non\-expansive property of the projection\[⋅\]\+\[\\cdot\]\_\{\+\}, we can write the magnitude of the error after the gradient step as

‖ek\+12i‖\\displaystyle\\left\\\|e\_\{k\+\\frac\{1\}\{2\}\}^\{i\}\\right\\\|=‖λk\+12i−λ^k\+12‖\\displaystyle=\\left\\\|\\lambda\_\{k\+\\frac\{1\}\{2\}\}^\{i\}\-\\hat\{\\lambda\}\_\{k\+\\frac\{1\}\{2\}\}\\right\\\|\(A\.8\)=‖\[λki−α​\(cN−V1,ki\)\]\+−∑i=1Nwi​\[λki−α​\(cN−V1,ki\)\]\+‖,\\displaystyle=\\left\\\|\\left\[\\lambda\_\{k\}^\{i\}\-\\alpha\\left\(\\frac\{c\}\{N\}\-V\_\{1,k\}^\{i\}\\right\)\\right\]\_\{\+\}\-\\sum\_\{i=1\}^\{N\}w^\{i\}\\left\[\\lambda\_\{k\}^\{i\}\-\\alpha\\left\(\\frac\{c\}\{N\}\-V\_\{1,k\}^\{i\}\\right\)\\right\]\_\{\+\}\\right\\\|,≤‖λki−α​\(cN−V1,ki\)−∑i=1Nwi​\(λki−α​\(cN−V1,ki\)\)‖,\\displaystyle\\leq\\left\\\|\\lambda\_\{k\}^\{i\}\-\\alpha\\left\(\\frac\{c\}\{N\}\-V\_\{1,k\}^\{i\}\\right\)\-\\sum\_\{i=1\}^\{N\}w^\{i\}\\left\(\\lambda\_\{k\}^\{i\}\-\\alpha\\left\(\\frac\{c\}\{N\}\-V\_\{1,k\}^\{i\}\\right\)\\right\)\\right\\\|,=‖λki−α​\(cN−V1,ki\)−\(λ^k−α​\(cN−V^1,k\)\)‖,\\displaystyle=\\left\\\|\\lambda\_\{k\}^\{i\}\-\\alpha\\left\(\\frac\{c\}\{N\}\-V\_\{1,k\}^\{i\}\\right\)\-\\left\(\\hat\{\\lambda\}\_\{k\}\-\\alpha\\left\(\\frac\{c\}\{N\}\-\\hat\{V\}\_\{1,k\}\\right\)\\right\)\\right\\\|,=‖eki\+α​\(V1,ki−V^1,k\)‖\.\\displaystyle=\\left\\\|e\_\{k\}^\{i\}\+\\alpha\\left\(V\_\{1,k\}^\{i\}\-\\hat\{V\}\_\{1,k\}\\right\)\\right\\\|\.\(A\.9\)After the consensus update equation[A\.4](https://arxiv.org/html/2605.30461#A1.E4),

‖ek\+1‖≤‖Pℒ‖​‖ek\+12‖\.\\left\\\|e\_\{k\+1\}\\right\\\|\\leq\\left\\\|P^\{\\mathscr\{L\}\}\\right\\\|\\left\\\|e\_\{k\+\\frac\{1\}\{2\}\}\\right\\\|\.\(A\.10\)
since the consensus step only affects the error term through multiplication byPP\. Substituting equation[A\.9](https://arxiv.org/html/2605.30461#A1.E9)into equation[A\.10](https://arxiv.org/html/2605.30461#A1.E10)and lettingV1,ki−V^1,k=Δ​V1,kV^\{i\}\_\{1,k\}\-\\hat\{V\}\_\{1,k\}=\\Delta V\_\{1,k\}, we obtain equation[A\.7](https://arxiv.org/html/2605.30461#A1.E7)\. ∎

###### Theorem A\.7\(Asymptotic Bound on Consensus Error\)\.

For the standard assumption of bounded rewards, the constraint functionsV1,kiV\_\{1,k\}^\{i\}are bounded such that‖Δ​V1,k‖≤σ\\\|\\Delta V\_\{1,k\}\\\|\\leq\\sigmafor someσ\>0\\sigma\>0\. Then, the consensus error satisfies

limk→∞‖ek\+1‖≤ρℒ​α​σ1−ρℒ\.\\lim\_\{k\\to\\infty\}\\\|e\_\{k\+1\}\\\|\\leq\\frac\{\\rho^\{\\mathscr\{L\}\}\\alpha\\sigma\}\{1\-\\rho^\{\\mathscr\{L\}\}\}\.whereρ=1−ϵ​Λ2\\rho=1\-\\epsilon\\Lambda\_\{2\}as before\.

###### Proof\.

Using Lemma[A\.6](https://arxiv.org/html/2605.30461#A1.Thmtheorem6)and Theorem[A\.5](https://arxiv.org/html/2605.30461#A1.Thmtheorem5), we have

‖ek\+1‖\\displaystyle\\\|e\_\{k\+1\}\\\|≤‖Pℒ‖​\(‖ek‖\+α​‖Δ​V1,k‖\)\\displaystyle\\leq\\\|P^\{\\mathscr\{L\}\}\\\|\\left\(\\\|e\_\{k\}\\\|\+\\alpha\\\|\\Delta V\_\{1,k\}\\\|\\right\)≤ρℒ​‖ek‖\+ρℒ​α​σ,\\displaystyle\\leq\\rho^\{\\mathscr\{L\}\}\\\|e\_\{k\}\\\|\+\\rho^\{\\mathscr\{L\}\}\\alpha\\sigma,\(A\.11\)since‖Pℒ‖=ρℒ\\\|P^\{\\mathscr\{L\}\}\\\|=\\rho^\{\\mathscr\{L\}\}in the subspace orthogonal to𝟏\\mathbf\{1\}\.

Unrolling the recursion:

‖ek\+1‖\\displaystyle\\\|e\_\{k\+1\}\\\|≤ρℒ​‖ek‖\+ρ​α​σ\\displaystyle\\leq\\rho^\{\\mathscr\{L\}\}\\\|e\_\{k\}\\\|\+\\rho\\alpha\\sigma≤ρ2​ℒ​‖ek−1‖\+ρ2​ℒ​α​σ\+ρℒ​α​σ\\displaystyle\\leq\\rho^\{2\\mathscr\{L\}\}\\\|e\_\{k\-1\}\\\|\+\\rho^\{2\\mathscr\{L\}\}\\alpha\\sigma\+\\rho^\{\\mathscr\{L\}\}\\alpha\\sigma≤…\\displaystyle\\leq\\dots≤ρℒ​\(k\+1\)​‖e0‖\+ρℒ​α​σ​∑t=0kρt​ℒ\\displaystyle\\leq\\rho^\{\\mathscr\{L\}\(k\+1\)\}\\\|e\_\{0\}\\\|\+\\rho^\{\\mathscr\{L\}\}\\alpha\\sigma\\sum\_\{t=0\}^\{k\}\\rho^\{t\\mathscr\{L\}\}=ρℒ​\(k\+1\)​‖e0‖\+ρℒ​α​σ​\(1−ρℒ​\(k\+1\)1−ρℒ\)\.\\displaystyle=\\rho^\{\\mathscr\{L\}\(k\+1\)\}\\\|e\_\{0\}\\\|\+\\rho^\{\\mathscr\{L\}\}\\alpha\\sigma\\left\(\\frac\{1\-\\rho^\{\\mathscr\{L\}\(k\+1\)\}\}\{1\-\\rho^\{\\mathscr\{L\}\}\}\\right\)\.Taking the limit ask→∞k\\to\\infty, we obtain

limk→∞‖ek\+1‖≤ρℒ​α​σ1−ρℒ\.\\lim\_\{k\\to\\infty\}\\\|e\_\{k\+1\}\\\|\\leq\\frac\{\\rho^\{\\mathscr\{L\}\}\\alpha\\sigma\}\{1\-\\rho^\{\\mathscr\{L\}\}\}\.
since‖Pℒ‖=ρℒ\\\|P^\{\\mathscr\{L\}\}\\\|=\\rho^\{\\mathscr\{L\}\}in the subspace orthogonal to𝟏\\mathbf\{1\}\(the condition numberC=κ​\(V\)C=\\kappa\(V\)from Theorem[A\.5](https://arxiv.org/html/2605.30461#A1.Thmtheorem5)does not appear here because the error vectoreke\_\{k\}lies entirely in this subspace by construction \(see the proof of Theorem[A\.5](https://arxiv.org/html/2605.30461#A1.Thmtheorem5)\) so the dominant eigenvalueν1=1\\nu\_\{1\}=1and its associated eigenvector direction are absent from the error dynamics\)\. ∎

## Appendix BSensitivity Analysis: From Consensus Error to Feasibility

We prove Proposition[5\.4](https://arxiv.org/html/2605.30461#S5.Thmtheorem4)and then discuss the conditions under which the Lipschitz assumption holds\.

### B\.1Proof of Proposition[5\.4](https://arxiv.org/html/2605.30461#S5.Thmtheorem4)

###### Proof\.

Part \(a\)\.We decompose the left\-hand side of equation[15](https://arxiv.org/html/2605.30461#S5.E15)using the triangle inequality:

\|∑i=1NV1i\(π^i\(λi\)\)\\displaystyle\\biggl\|\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\hat\{\\pi\}^\{i\}\(\\lambda^\{i\}\)\\bigr\)−∑i=1NV1i\(π⋆i\(λ¯\)\)\|\\displaystyle\-\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\bar\{\\lambda\}\)\\bigr\)\\biggr\|≤∑i=1N\|V1i​\(π^i​\(λi\)\)−V1i​\(π⋆i​\(λi\)\)\|⏟\(I\)\+∑i=1N\|V1i​\(π⋆i​\(λi\)\)−V1i​\(π⋆i​\(λ¯\)\)\|⏟\(II\)\.\\displaystyle\\leq\\underbrace\{\\sum\_\{i=1\}^\{N\}\\bigl\|V\_\{1\}^\{i\}\\\!\\bigl\(\\hat\{\\pi\}^\{i\}\(\\lambda^\{i\}\)\\bigr\)\-V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda^\{i\}\)\\bigr\)\\bigr\|\}\_\{\(\\mathrm\{I\}\)\}\+\\underbrace\{\\sum\_\{i=1\}^\{N\}\\bigl\|V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda^\{i\}\)\\bigr\)\-V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\bar\{\\lambda\}\)\\bigr\)\\bigr\|\}\_\{\(\\mathrm\{II\}\)\}\.\(B\.1\)For term \(I\), Assumption[5\.3](https://arxiv.org/html/2605.30461#S5.Thmtheorem3)yields\(I\)≤N​εapprox\(\\mathrm\{I\}\)\\leq N\\,\\varepsilon\_\{\\mathrm\{approx\}\}\. For term \(II\), Assumption[5\.2](https://arxiv.org/html/2605.30461#S5.Thmtheorem2)gives

\(II\)≤LV​∑i=1N\|λi−λ¯\|≤LV​N​‖𝝀−λ¯​1‖≤LV​N​δ,\(\\mathrm\{II\}\)\\;\\leq\\;L\_\{V\}\\sum\_\{i=1\}^\{N\}\|\\lambda^\{i\}\-\\bar\{\\lambda\}\|\\;\\leq\\;L\_\{V\}\\,\\sqrt\{N\}\\,\\bigl\\\|\\bm\{\\lambda\}\-\\bar\{\\lambda\}\\,\\mathbf\{1\}\\bigr\\\|\\;\\leq\\;L\_\{V\}\\,\\sqrt\{N\}\\,\\delta,\(B\.2\)where the second inequality is the Cauchy–Schwarz inequality \(‖𝐱‖1≤N​‖𝐱‖2\\\|\\mathbf\{x\}\\\|\_\{1\}\\leq\\sqrt\{N\}\\,\\\|\\mathbf\{x\}\\\|\_\{2\}\) and the third follows from the premise‖𝝀−λ¯​1‖≤δ\\\|\\bm\{\\lambda\}\-\\bar\{\\lambda\}\\,\\mathbf\{1\}\\\|\\leq\\delta\. Combining gives equation[15](https://arxiv.org/html/2605.30461#S5.E15)\.

Part \(b\)\.We write

∑i=1NV1i​\(π^i​\(λi\)\)\\displaystyle\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\hat\{\\pi\}^\{i\}\(\\lambda^\{i\}\)\\bigr\)=∑i=1NV1i​\(π⋆i​\(λ¯\)\)\+\[∑i=1NV1i​\(π^i​\(λi\)\)−∑i=1NV1i​\(π⋆i​\(λ¯\)\)\]\\displaystyle=\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\bar\{\\lambda\}\)\\bigr\)\\;\+\\;\\biggl\[\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\hat\{\\pi\}^\{i\}\(\\lambda^\{i\}\)\\bigr\)\-\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\bar\{\\lambda\}\)\\bigr\)\\biggr\]≤∑i=1NV1i​\(π⋆i​\(λ¯\)\)\+LV​N​δ\+N​εapprox,\\displaystyle\\leq\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\bar\{\\lambda\}\)\\bigr\)\+L\_\{V\}\\sqrt\{N\}\\,\\delta\+N\\,\\varepsilon\_\{\\mathrm\{approx\}\},\(B\.3\)where the inequality applies the upper bound from part \(a\)\. Next, using Assumption[5\.2](https://arxiv.org/html/2605.30461#S5.Thmtheorem2)again,

∑i=1NV1i​\(π⋆i​\(λ¯\)\)≤∑i=1NV1i​\(π⋆i​\(λ⋆\)\)\+LV​N​\|λ¯−λ⋆\|≤c\+LV​N​\|λ¯−λ⋆\|,\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\bar\{\\lambda\}\)\\bigr\)\\;\\leq\\;\\sum\_\{i=1\}^\{N\}V\_\{1\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda^\{\\star\}\)\\bigr\)\+L\_\{V\}\\,N\\,\|\\bar\{\\lambda\}\-\\lambda^\{\\star\}\|\\;\\leq\\;c\+L\_\{V\}\\,N\\,\|\\bar\{\\lambda\}\-\\lambda^\{\\star\}\|,\(B\.4\)where the final inequality uses the assumed centralized feasibility∑iV1i​\(π⋆i​\(λ⋆\)\)≤c\\sum\_\{i\}V\_\{1\}^\{i\}\(\\pi^\{i\}\_\{\\star\}\(\\lambda^\{\\star\}\)\)\\leq c\. Substituting equation[B\.4](https://arxiv.org/html/2605.30461#A2.E4)into equation[B\.3](https://arxiv.org/html/2605.30461#A2.E3)yields equation[16](https://arxiv.org/html/2605.30461#S5.E16)\.

Part \(c\)\.The argument is identical to parts \(a\)–\(b\), replacingV1iV\_\{1\}^\{i\}byV0iV\_\{0\}^\{i\}and the Lipschitz constantLVL\_\{V\}byL0L\_\{0\}:

\|∑i=1NV0i​\(π^i​\(λi\)\)−∑i=1NV0i​\(π⋆i​\(λ⋆\)\)\|\\displaystyle\\biggl\|\\sum\_\{i=1\}^\{N\}V\_\{0\}^\{i\}\\\!\\bigl\(\\hat\{\\pi\}^\{i\}\(\\lambda^\{i\}\)\\bigr\)\-\\sum\_\{i=1\}^\{N\}V\_\{0\}^\{i\}\\\!\\bigl\(\\pi^\{i\}\_\{\\star\}\(\\lambda^\{\\star\}\)\\bigr\)\\biggr\|≤L0​N​δ⏟consensuserror\+L0​N​\|λ¯−λ⋆\|⏟dualconvergence\+N​εapprox⏟functionapprox\.,\\displaystyle\\leq\\underbrace\{L\_\{0\}\\,\\sqrt\{N\}\\,\\delta\}\_\{\\begin\{subarray\}\{c\}\\text\{consensus\}\\\\ \\text\{error\}\\end\{subarray\}\}\\;\+\\;\\underbrace\{L\_\{0\}\\,N\\,\|\\bar\{\\lambda\}\-\\lambda^\{\\star\}\|\}\_\{\\begin\{subarray\}\{c\}\\text\{dual\}\\\\ \\text\{convergence\}\\end\{subarray\}\}\\;\+\\;\\underbrace\{N\\,\\varepsilon\_\{\\mathrm\{approx\}\}\}\_\{\\begin\{subarray\}\{c\}\\text\{function\}\\\\ \\text\{approx\.\}\\end\{subarray\}\},which gives equation[17](https://arxiv.org/html/2605.30461#S5.E17)\. ∎

### B\.2Discussion of Assumptions

![Refer to caption](https://arxiv.org/html/2605.30461v1/x16.png)Figure B\.1:Empirical sensitivity of value functions to the dual variableλ\\lambda\(ν=−10\\nu=\-10fixed, 10 rollouts per point, horizon=80=80\)\.\(a\)Constraint valueV1i​\(π^i​\(λ\)\)V\_\{1\}^\{i\}\(\\hat\{\\pi\}^\{i\}\(\\lambda\)\)\(grid consumption\) decreases monotonically withλ\\lambda, with maximum slopeL^V=8\.44\\hat\{L\}\_\{V\}=8\.44kWh/λ\\lambda\.\(b\)Cost valueV0i​\(π^i​\(λ\)\)V\_\{0\}^\{i\}\(\\hat\{\\pi\}^\{i\}\(\\lambda\)\)shows similar behavior withL^0=39\.24\\hat\{L\}\_\{0\}=39\.24$/λ\\lambda\. Both curves are smooth, confirming Assumption[5\.2](https://arxiv.org/html/2605.30461#S5.Thmtheorem2)\.