完全拜占庭容错的多智能体强化学习

# Fully Byzantine-Resilient Multi-Agent Reinforcement Learning
Source: [https://arxiv.org/html/2609.25701](https://arxiv.org/html/2609.25701)
Dimitra Panagou††thanks:\*This work is supported by the Air Force Office of Scientific Research \(AFOSR\) under FA9550\-23\-1\-0163††thanks:All authors are with the Robotics Department, University of Michigan, Ann Arbor, MI, USA\{haejoonl,dpanagou\}@umich\.edu††thanks:$ˆa$Code:[https://github\.com/joonlee16/frac\-marl](https://github.com/joonlee16/frac-marl)

###### Abstract

We study distributed Byzantine\-resilient actor\-critic multi\-agent reinforcement learning \(AC\-MARL\), where agents collectively learn policies through local interactions\. Existing methods guarantee convergence of the agents’ parameters only to a neighborhood of the attack\-free limit points, resulting in degraded performance\. We propose Fully Resilient AC\-MARL \(FRAC\-MARL\), a decentralized method in which each agent leverages redundancy in two\-hop messages to identify reliable messages\. Under linear parameterizations of the value and team\-reward functions and Byzantine edge attacks, where adversarial behavior is confined to the communication layer, we prove that agents’ parameters converge almost surely to the same limit points as in the attack\-free case over time\-varying communication graphs\. We introduce a novel topological condition for the convergence of our method, present a systematic method to construct such networks, and prove that this condition can be verified in polynomial time\. Finally, we demonstrate our method on cooperative multi\-robot formation control tasks\. \[code\]a

###### Index Terms:

Multi\-Agent reinforcement learning, networked control systems, fault\-tolerant systems

## IIntroduction

Multi\-agent reinforcement learning \(MARL\) has emerged as a powerful and scalable extension of reinforcement learning \(RL\)\[[1](https://arxiv.org/html/2609.25701#bib.bib8)\]for learning optimal policies of multiple agents interacting within a shared environment\[[2](https://arxiv.org/html/2609.25701#bib.bib9)\]\. Distributed cooperative MARL in particular considers multiple agents that aim to optimize a shared global objective \- often expressed as the average of local rewards \- through information sharing with their neighbors in a network\[[3](https://arxiv.org/html/2609.25701#bib.bib1),[4](https://arxiv.org/html/2609.25701#bib.bib19),[5](https://arxiv.org/html/2609.25701#bib.bib20)\]\.

In this paper, we consider fully distributed actor\-critic MARL \(AC\-MARL\) methods studied in\[[3](https://arxiv.org/html/2609.25701#bib.bib1),[6](https://arxiv.org/html/2609.25701#bib.bib3),[7](https://arxiv.org/html/2609.25701#bib.bib42),[8](https://arxiv.org/html/2609.25701#bib.bib41)\], where agents with heterogeneous reward functions perform consensus\-based updates of their local policy and value\-function parameter estimates over a communication network\. Compared with distributed tabular Q\-learning approaches\[[9](https://arxiv.org/html/2609.25701#bib.bib2)\], these methods offer improved scalability to problems with large state and action spaces\. Representative deep actor\-critic MARL methods include MADDPG\[[10](https://arxiv.org/html/2609.25701#bib.bib43)\], COMA\[[11](https://arxiv.org/html/2609.25701#bib.bib44)\], and MAPPO\[[12](https://arxiv.org/html/2609.25701#bib.bib45)\]\. However, these methods typically rely on centralized training or centralized value estimation\.

For fully distributed AC\-MARL,\[[3](https://arxiv.org/html/2609.25701#bib.bib1)\]established convergence under linear function approximation, while finite\-time convergence guarantees were provided in\[[6](https://arxiv.org/html/2609.25701#bib.bib3)\]\. Later,\[[7](https://arxiv.org/html/2609.25701#bib.bib42)\]established convergence under linear function approximation for directed communication graphs\. Finally,\[[8](https://arxiv.org/html/2609.25701#bib.bib41)\]presented an algorithm with nonlinear function approximation and established asymptotic convergence guarantees\.

Despite these merits, distributed MARL algorithms, similarly to other distributed learning and optimization methods, are highly susceptible to adversarial attacks that corrupt or manipulate information\. In the distributed systems literature, the Byzantine model represents an omniscient adversary capable of injecting arbitrary disruptions through compromised hardware, software, or communication channels\[[13](https://arxiv.org/html/2609.25701#bib.bib18),[14](https://arxiv.org/html/2609.25701#bib.bib10)\]\. As a result, a wide range of resilient algorithms have been developed to contain the impact of Byzantine agents on distributed consensus\[[14](https://arxiv.org/html/2609.25701#bib.bib10),[15](https://arxiv.org/html/2609.25701#bib.bib15),[16](https://arxiv.org/html/2609.25701#bib.bib30)\], optimization\[[17](https://arxiv.org/html/2609.25701#bib.bib17),[13](https://arxiv.org/html/2609.25701#bib.bib18),[18](https://arxiv.org/html/2609.25701#bib.bib25)\], learning frameworks\[[19](https://arxiv.org/html/2609.25701#bib.bib22),[20](https://arxiv.org/html/2609.25701#bib.bib23),[21](https://arxiv.org/html/2609.25701#bib.bib24)\], and, more recently, multi\-agent LLM decision\-making systems\[[22](https://arxiv.org/html/2609.25701#bib.bib32),[23](https://arxiv.org/html/2609.25701#bib.bib33)\]\.

Similarly, Byzantine\-resilient distributed MARL has received increasing attention in recent years\. Early studies demonstrated that even a single adversarial agent can significantly degrade or destabilize learning in cooperative MARL settings\[[24](https://arxiv.org/html/2609.25701#bib.bib4),[25](https://arxiv.org/html/2609.25701#bib.bib13)\]\. In fact, it has been shown in\[[26](https://arxiv.org/html/2609.25701#bib.bib14)\]that learning optimal policies is generally impossible in the presence of Byzantine agents\.

To address this vulnerability, several Byzantine\-resilient MARL algorithms have been proposed\. The distributed tabular Q\-learning algorithm in\[[9](https://arxiv.org/html/2609.25701#bib.bib2)\]was extended in\[[27](https://arxiv.org/html/2609.25701#bib.bib21)\]by incorporating trimmed\-mean aggregation to guarantee convergence in the presence of Byzantine agents\. The trimmed\-mean strategy was subsequently incorporated into consensus\-based AC\-MARL algorithms with linear function approximation to achieve resilience against Byzantine agents\[[28](https://arxiv.org/html/2609.25701#bib.bib29),[29](https://arxiv.org/html/2609.25701#bib.bib12)\]\. More recently,\[[30](https://arxiv.org/html/2609.25701#bib.bib5),[31](https://arxiv.org/html/2609.25701#bib.bib31)\]combined projection\-based updates with trimmed\-mean aggregation to further strengthen the resilience of AC\-MARL\. Similarly,\[[32](https://arxiv.org/html/2609.25701#bib.bib34)\]employs geometric\-median aggregation to mitigate Byzantine attacks, although it does not provide convergence guarantees and considers only non\-colluding adversaries\.

Despite these advances, existing methods have several limitations\. First, these approaches guarantee convergence only to a neighborhood of the attack\-free limit point of the attack\-free case\. Thus, Byzantine agents may strategically manipulate the exchanged parameters to substantially degrade the performance of the non\-Byzantine agents\[[30](https://arxiv.org/html/2609.25701#bib.bib5)\]\. Although\[[30](https://arxiv.org/html/2609.25701#bib.bib5),[31](https://arxiv.org/html/2609.25701#bib.bib31)\]mitigate this issue, they still guarantee only neighborhood convergence, and the size of the resulting neighborhood is generally difficult to characterize\.

Furthermore, many Byzantine\-resilient AC\-MARL methods, including\[[30](https://arxiv.org/html/2609.25701#bib.bib5),[29](https://arxiv.org/html/2609.25701#bib.bib12),[31](https://arxiv.org/html/2609.25701#bib.bib31)\], require the communication network to satisfy\(2​F\+1\)\(2F\+1\)\-robustness\[[14](https://arxiv.org/html/2609.25701#bib.bib10)\]\. Since verifying such properties is coNP\-complete\[[33](https://arxiv.org/html/2609.25701#bib.bib11)\], their applicability to large\-scale systems may be limited\. A separate line of work\[[34](https://arxiv.org/html/2609.25701#bib.bib6),[35](https://arxiv.org/html/2609.25701#bib.bib16),[36](https://arxiv.org/html/2609.25701#bib.bib28)\]avoids theserr\-robustness requirements, but instead relies on a trusted central coordinator\.

In addition, decentralized MARL with heterogeneous local rewards can be viewed through the lens of decentralized stochastic optimization under non\-i\.i\.d\. data distributions\. Compared with Byzantine\-resilient deterministic optimization\[[17](https://arxiv.org/html/2609.25701#bib.bib17),[13](https://arxiv.org/html/2609.25701#bib.bib18)\]and stochastic optimization under i\.i\.d\. assumptions\[[19](https://arxiv.org/html/2609.25701#bib.bib22),[37](https://arxiv.org/html/2609.25701#bib.bib39)\], the non\-i\.i\.d\. setting introduces additional challenges due to heterogeneity and stochasticity across agents, which induces intrinsic bias that is further exacerbated by Byzantine attacks\[[38](https://arxiv.org/html/2609.25701#bib.bib36)\]\. The work in\[[39](https://arxiv.org/html/2609.25701#bib.bib37)\]studied Byzantine\-resilient stochastic optimization with non\-i\.i\.d\. data from a consensus perspective under a complete communication graph\. In\[[38](https://arxiv.org/html/2609.25701#bib.bib36)\], authors iteratively remove values farthest from the weighted mean to construct a doubly stochastic mixing matrix with a sufficiently small contraction factor, thereby ensuring convergence\. In contrast,\[[40](https://arxiv.org/html/2609.25701#bib.bib40)\]proposed a clipping\-based mechanism that clips received values to neighborhoods centered at the receiving agents’ values\. Nevertheless, these methods only guarantee convergence to a neighborhood of a stationary point of the underlying optimization problem\.

To address these limitations, we build on our prior work on resilient distributed Q\-learning\[[41](https://arxiv.org/html/2609.25701#bib.bib35)\]and extend the framework to decentralized Byzantine\-resilient AC\-MARL over time\-varying communication graphs\. Specifically, we propose Fully Resilient AC\-MARL \(FRAC\-MARL\), in which agents use redundant information relayed through two\-hop communication to identify reliable messages before incorporating them into their local updates\. Under a sufficient topological condition on the communication networks and a weaker Byzantine attack model, we establish that the agents’ parameters converge almost surely to the exact limit points of the attack\-free scenario, rather than to a neighborhood\.

#### Contributions

Our contributions are as follows:

- •We propose a novel decentralized Byzantine\-resilient AC\-MARL algorithm, termed Fully Resilient AC\-MARL \(FRAC\-MARL\), that leverages redundancy in two\-hop communication to identify and incorporate reliable messages for learning over time\-varying communication graphs\.
- •We introduce a novel topological condition, termed\(r,r′\)\(r,r^\{\\prime\}\)\-redundancy, and prove that under linear function approximation it guarantees that FRAC\-MARL converges almost surely to the same limit points as the attack\-free case under Byzantine edge attacks, a weaker Byzantine model in which adversarial behavior is restricted to the communication layer\.
- •We provide a constructive procedure for designing\(r,r′\)\(r,r^\{\\prime\}\)\-redundant graphs and show that this property can be verified in polynomial time, in contrast torr\-robustness\[[14](https://arxiv.org/html/2609.25701#bib.bib10)\], which is widely adopted in existing work\[[30](https://arxiv.org/html/2609.25701#bib.bib5),[29](https://arxiv.org/html/2609.25701#bib.bib12),[31](https://arxiv.org/html/2609.25701#bib.bib31)\]but is coNP\-complete to verify\[[33](https://arxiv.org/html/2609.25701#bib.bib11)\]\.
- •We demonstrate our method can be applied even with nonlinear function approximation in a cooperative multi\-agent formation task\.

## IINotation

We denote the cardinality of a set𝒞\\mathcal\{C\}as\|𝒞\|\|\\mathcal\{C\}\|\. We denote the sets of non\-negative and positive integers asℤ≥0\\mathbb\{Z\}\_\{\\geq 0\}andℤ\>0\\mathbb\{Z\}\_\{\>0\}\. A multiset𝒞\\mathcal\{C\}is a collection in which elements may occur with multiplicity\. For a \(multi\)set𝒞\\mathcal\{C\}, we definemode⁡\(𝒞\)\{\\rm mode\}\(\\mathcal\{C\}\)as any element with the highest number of occurrences in𝒞\\mathcal\{C\}, with ties broken uniformly at random andmode⁡\(∅\)=0\{\\rm mode\}\(\\emptyset\)=0\. We denotemode​\_​count​\(𝒞\)\{\\rm mode\\\_count\}\(\\mathcal\{C\}\)as the maximum number of occurrences of any element in a \(multi\)set𝒞\\mathcal\{C\}\. We denotediag⁡\(⋅\)\{\\rm diag\}\(\\cdot\)as the diagonal matrix formed by the elements of its argument\. We denote the probability and expectation of a probability space\(Ω,ℱ,ℙ\)\(\\Omega,\\mathcal\{F\},\\mathbb\{P\}\)byℙ⁡\(⋅\)\\mathbb\{P\}\(\\cdot\)and𝔼⁡\(⋅\)\\mathbb\{E\}\(\\cdot\)\. We denote the Kronecker product by⊗\\otimes\. For finite sets𝒞1\\mathcal\{C\}\_\{1\}and𝒞2\\mathcal\{C\}\_\{2\}and functionsg1:𝒞1→ℝg\_\{1\}:\\mathcal\{C\}\_\{1\}\\to\\mathbb\{R\}andg2:𝒞1×𝒞2→ℝg\_\{2\}:\\mathcal\{C\}\_\{1\}\\times\\mathcal\{C\}\_\{2\}\\to\\mathbb\{R\}, we write\[g1​\(c1\),c1∈𝒞1\]⊤∈ℝ\|𝒞1\|\[g\_\{1\}\(c\_\{1\}\),\\ c\_\{1\}\\in\\mathcal\{C\}\_\{1\}\]^\{\\top\}\\in\\mathbb\{R\}^\{\|\\mathcal\{C\}\_\{1\}\|\}and\[g2​\(c1,c2\),c1∈𝒞1,c2∈𝒞2\]⊤∈ℝ\|𝒞1\|⋅\|𝒞2\|\[g\_\{2\}\(c\_\{1\},c\_\{2\}\),\\ c\_\{1\}\\in\\mathcal\{C\}\_\{1\},c\_\{2\}\\in\\mathcal\{C\}\_\{2\}\]^\{\\top\}\\in\\mathbb\{R\}^\{\|\\mathcal\{C\}\_\{1\}\|\\cdot\|\\mathcal\{C\}\_\{2\}\|\}for the column vector of valuesg1​\(c1\)g\_\{1\}\(c\_\{1\}\)andg2​\(c1,c2\)g\_\{2\}\(c\_\{1\},c\_\{2\}\)respectively, stacked according to fixed orderings of𝒞1\\mathcal\{C\}\_\{1\}and𝒞1×𝒞2\\mathcal\{C\}\_\{1\}\\times\\mathcal\{C\}\_\{2\}, respectively, used consistently throughout the paper\. A sequence of random variables\{Xt\}t≥0\\\{X\_\{t\}\\\}\_\{t\\geq 0\}is said to converge to a random variableXXalmost surely \(a\.s\.\) ifℙ⁡\(limt→∞Xt=X\)=1\\mathbb\{P\}\(\\lim\_\{t\\to\\infty\}X\_\{t\}=X\)=1\.

## IIIPreliminaries

We consider a system ofnnagents interacting over a simple, undirected, and time\-varying communication graph𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)\. The vertex set𝒱=\{1,…,n\}\\mathcal\{V\}=\\\{1,\\dots,n\\\}represents the agents, and the edge setℰt⊆𝒱×𝒱\\mathcal\{E\}\_\{t\}\\subseteq\\mathcal\{V\}\\times\\mathcal\{V\}denotes a set of communication links between agents at timett\. Since the graph is undirected,\(i,j\)∈ℰt\(i,j\)\\in\\mathcal\{E\}\_\{t\}implies\(j,i\)∈ℰt\(j,i\)\\in\\mathcal\{E\}\_\{t\}\. For agentii, its one\-hop and two\-hop neighbor sets at timettare denoted by𝒩i,t=\{j∈𝒱∣\(i,j\)∈ℰt\}\\mathcal\{N\}\_\{i,t\}=\\\{j\\in\\mathcal\{V\}\\mid\(i,j\)\\in\\mathcal\{E\}\_\{t\}\\\}and𝒩i,t\(2\)=\{k∈𝒱∣∃j∈𝒩i,t​s\.t\.​k∈𝒩j,t∖\{i\}\}\\mathcal\{N\}^\{\(2\)\}\_\{i,t\}=\\\{k\\in\\mathcal\{V\}\\mid\\exists\\,j\\in\\mathcal\{N\}\_\{i,t\}\\ \\text\{s\.t\.\}\\ k\\in\\mathcal\{N\}\_\{j,t\}\\setminus\\\{i\\\}\\\}\. The extended one\-hop neighbor set isℬi,t=𝒩i,t∪\{i\}\\mathcal\{B\}\_\{i,t\}=\\mathcal\{N\}\_\{i,t\}\\cup\\\{i\\\}\. A path of lengthk∈ℤ\>0k\\in\\mathbb\{Z\}\_\{\>0\}is a sequence of vertices\(y0,…,yk\)\(y\_\{0\},\\dots,y\_\{k\}\)such that\(yℓ−1,yℓ\)∈ℰt\(y\_\{\\ell\-1\},y\_\{\\ell\}\)\\in\\mathcal\{E\}\_\{t\}∀ℓ∈\{1,…,k\}\\forall\\ell\\in\\\{1,\\dots,k\\\}\. A graph is connected if there exists a path between any pair of nodes\.

In our setting, agentsi∈𝒱i\\in\\mathcal\{V\}not only communicate with their direct neighbors𝒩i,t\\mathcal\{N\}\_\{i,t\}at timett, but also with their two\-hop neighbors𝒩i,t\(2\)\\mathcal\{N\}^\{\(2\)\}\_\{i,t\}through relaying, which we refer to as*two\-hop communication*:

###### Definition 1\(Two\-hop communication\)\.

Letmj′j→i​\(t\)m^\{j\\to i\}\_\{j^\{\\prime\}\}\(t\)denote the copy of the messagemj′​\(t\)m\_\{j^\{\\prime\}\}\(t\)originating from any agentj′∈𝒱j^\{\\prime\}\\in\\mathcal\{V\}and delivered to agentiiby agentjjat timett\. We setmj′j→i​\(t\)=∅m^\{j\\to i\}\_\{j^\{\\prime\}\}\(t\)=\\varnothingif the message is not received by agentii\.

At each timet∈ℤ≥0t\\in\\mathbb\{Z\}\_\{\\geq 0\}, agents exchange messages over𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)in two consecutive rounds\. In roundz=1z=1\(*sending*\), each agentiitransmits its own messagemi​\(t\)m\_\{i\}\(t\)to every neighborj∈𝒩i,tj\\in\\mathcal\{N\}\_\{i,t\}\. In roundz=2z=2\(*relaying*\), each agentiiforwards to every neighborj∈𝒩i,tj\\in\\mathcal\{N\}\_\{i,t\}the messages it received in round11, i\.e\.,\{mkk→i​\(t\)\}k∈𝒩i,t\\left\\\{m\_\{k\}^\{k\\to i\}\(t\)\\right\\\}\_\{k\\in\\mathcal\{N\}\_\{i,t\}\}\. Thus, agentjjobtains a copy of the messages originating from its two\-hop neighbors𝒩j,t\(2\)\\mathcal\{N\}^\{\(2\)\}\_\{j,t\}through an intermediate neighbori∈𝒩j,ti\\in\\mathcal\{N\}\_\{j,t\}\.

The environment is modeled as a networked multi\-agent Markov Decision Process \(MDP\) defined by a tuple\(𝒮,\{𝒜i\}i∈𝒱,P,\{ri\}i∈𝒱,\{𝒢t\}t≥0,γ\)\(\\mathcal\{S\},\\\{\\mathcal\{A\}^\{i\}\\\}\_\{i\\in\\mathcal\{V\}\},P,\\\{r^\{i\}\\\}\_\{i\\in\\mathcal\{V\}\},\\\{\\mathcal\{G\}\_\{t\}\\\}\_\{t\\geq 0\},\\gamma\)\. Here,𝒮\\mathcal\{S\}denotes the finite state space shared by all agents, and𝒜i\\mathcal\{A\}^\{i\}denotes the finite action space of agentii\. The joint action space is given by𝒜=∏i∈𝒱𝒜i\\mathcal\{A\}=\\prod\_\{i\\in\\mathcal\{V\}\}\\mathcal\{A\}^\{i\}\. The functionP:𝒮×𝒜×𝒮→\[0,1\]P:\\mathcal\{S\}\\times\\mathcal\{A\}\\times\\mathcal\{S\}\\rightarrow\[0,1\]specifies the state transition probability, whereP⁡\(s′∣s,a\)P\(s^\{\\prime\}\\mid s,a\)denotes the probability of transitioning to states′s^\{\\prime\}from statessunder actionaa\. Each agentiihas a local reward functionri:𝒮×𝒜→ℝr^\{i\}:\\mathcal\{S\}\\times\\mathcal\{A\}\\rightarrow\\mathbb\{R\}, andγ∈\(0,1\)\\gamma\\in\(0,1\)is the discount factor\. We assume that the state and joint action are globally observable, while rewards are private and observed only by the corresponding agents\.

At each time steptt, each agenti∈𝒱i\\in\\mathcal\{V\}observes the current statest∈𝒮s\_\{t\}\\in\\mathcal\{S\}and independently selects an action

ati∼πi\(⋅∣st\),\\displaystyle a\_\{t\}^\{i\}\\sim\\pi^\{i\}\(\\cdot\\mid s\_\{t\}\),\(1\)whereπi:𝒮×𝒜i→\[0,1\]\\pi^\{i\}:\\mathcal\{S\}\\times\\mathcal\{A\}^\{i\}\\rightarrow\[0,1\]is the local stochastic policy\. The resulting joint action isat=\(at1,…,atn\)∈𝒜a\_\{t\}=\(a\_\{t\}^\{1\},\\dots,a\_\{t\}^\{n\}\)\\in\\mathcal\{A\}\. We assume that agent actions are conditionally independent given the current state, that is,

π⁡\(a∣s\)=∏i∈𝒱πi​\(ai∣s\)\.\\displaystyle\\pi\(a\\mid s\)=\\prod\_\{i\\in\\mathcal\{V\}\}\\pi^\{i\}\(a^\{i\}\\mid s\)\.\(2\)
After executingatia\_\{t\}^\{i\}at the statests\_\{t\}, each agentiireceives a local realized rewardrt\+1i=ri​\(st,at\)r\_\{t\+1\}^\{i\}=r^\{i\}\(s\_\{t\},a\_\{t\}\), and the environment transitions to the next state according tost\+1∼P\(⋅∣st,at\)s\_\{t\+1\}\\sim P\(\\cdot\\mid s\_\{t\},a\_\{t\}\)\.

### III\-AObjective and Policy Parameterization

For a joint policyπ\\piand a fixed initial\-state distributionν\\nuover𝒮\\mathcal\{S\}, the agents collectively maximize a globally averaged, discounted long\-term reward

J⁡\(π\)\\displaystyle J\(\\pi\):=𝔼s0∼ν,π​\[∑t=0∞γt​r¯​\(st,at\)\],\\displaystyle:=\\mathbb\{E\}\_\{s\_\{0\}\\sim\\nu,\\,\\pi\}\\Big\[\\textstyle\\sum\_\{t=0\}^\{\\infty\}\\gamma^\{t\}\\bar\{r\}\(s\_\{t\},a\_\{t\}\)\\Big\],\(3\)wherer¯​\(s,a\)=1n​∑i∈𝒱ri​\(s,a\)\\bar\{r\}\(s,a\)=\\frac\{1\}\{n\}\\sum\_\{i\\in\\mathcal\{V\}\}r^\{i\}\(s,a\)represents the network\-wise average reward at state\-action pair\(s,a\)\(s,a\)\. We also define the associated action\- and state\-value functions

Qπ​\(s,a\)\\displaystyle Q\_\{\\pi\}\(s,a\):=𝔼π\[∑t=0∞γtr¯\(st,at\)\|s0=s,a0=a\],\\displaystyle:=\\mathbb\{E\}\_\{\\pi\}\\Big\[\\textstyle\\sum\_\{t=0\}^\{\\infty\}\\gamma^\{t\}\\bar\{r\}\(s\_\{t\},a\_\{t\}\)\\;\\Big\|\\;s\_\{0\}=s,\\,a\_\{0\}=a\\Big\],\(4\)Vπ​\(s\)\\displaystyle V\_\{\\pi\}\(s\):=∑a∈𝒜π⁡\(a∣s\)​Qπ​\(s,a\)\.\\displaystyle:=\\textstyle\\sum\_\{a\\in\\mathcal\{A\}\}\\pi\(a\\mid s\)\\,Q\_\{\\pi\}\(s,a\)\.\(5\)SinceQπ​\(s,a\)=r¯​\(s,a\)\+γ​∑s′∈𝒮P⁡\(s′∣s,a\)​Vπ​\(s′\)Q\_\{\\pi\}\(s,a\)=\\bar\{r\}\(s,a\)\+\\gamma\\sum\_\{s^\{\\prime\}\\in\\mathcal\{S\}\}P\(s^\{\\prime\}\\mid s,a\)V\_\{\\pi\}\(s^\{\\prime\}\), the temporal\-difference \(TD\) error

δt=r¯​\(st,at\)\+γ​Vπ​\(st\+1\)−Vπ​\(st\)\\displaystyle\\delta\_\{t\}=\\bar\{r\}\(s\_\{t\},a\_\{t\}\)\+\\gamma V\_\{\\pi\}\(s\_\{t\+1\}\)\-V\_\{\\pi\}\(s\_\{t\}\)\(6\)is an unbiased sample of the global advantage, i\.e\.,𝔼\[δt∣st=s,at=a\]=Qπ\(s,a\)−Vπ\(s\)\\mathbb\{E\}\[\\delta\_\{t\}\\mid s\_\{t\}=s,\\,a\_\{t\}=a\]=Q\_\{\\pi\}\(s,a\)\-V\_\{\\pi\}\(s\)\.

To enable scalable learning in large state and action spaces, we parameterize each local policy\[[42](https://arxiv.org/html/2609.25701#bib.bib38)\]\. Letπθii:𝒮×𝒜i→\[0,1\]\\pi^\{i\}\_\{\\theta^\{i\}\}:\\mathcal\{S\}\\times\\mathcal\{A\}^\{i\}\\to\[0,1\]denote the local policy of agenti∈𝒱i\\in\\mathcal\{V\}parametrized byθi∈Θi⊂ℝbi\\theta^\{i\}\\in\\Theta^\{i\}\\subset\\mathbb\{R\}^\{b\_\{i\}\}\. By the conditional independence in \([2](https://arxiv.org/html/2609.25701#S3.E2)\), we have

πθ​\(a∣s\)\\displaystyle\\pi\_\{\\theta\}\(a\\mid s\)=∏i∈𝒱πθii​\(ai∣s\),\\displaystyle=\\prod\_\{i\\in\\mathcal\{V\}\}\\pi^\{i\}\_\{\\theta^\{i\}\}\(a^\{i\}\\mid s\),Pθ​\(s′∣s\)\\displaystyle P\_\{\\theta\}\(s^\{\\prime\}\\mid s\)=∑a∈𝒜πθ​\(a∣s\)​P​\(s′∣s,a\),\\displaystyle=\\sum\_\{a\\in\\mathcal\{A\}\}\\pi\_\{\\theta\}\(a\\mid s\)P\(s^\{\\prime\}\\mid s,a\),whereθ=\[\(θ1\)⊤,…,\(θn\)⊤\]⊤∈∏i∈𝒱Θi=Θ\\theta=\[\(\\theta^\{1\}\)^\{\\top\},\\dots,\(\\theta^\{n\}\)^\{\\top\}\]^\{\\top\}\\in\\prod\_\{i\\in\\mathcal\{V\}\}\\Theta^\{i\}=\\Theta\. For anyθ∈Θ\\theta\\in\\Theta, the Markov process\{st\}t∈ℤ≥0\\\{s\_\{t\}\\\}\_\{t\\in\\mathbb\{Z\}\_\{\\geq 0\}\}induced byπθ\\pi\_\{\\theta\}is irreducible and aperiodic\. This guarantees unique, strictly positive stationary distributionsdθ​\(s\)d\_\{\\theta\}\(s\)anddθ′​\(s,a\)=dθ​\(s\)​πθ​\(a∣s\)d^\{\\prime\}\_\{\\theta\}\(s,a\)=d\_\{\\theta\}\(s\)\\pi\_\{\\theta\}\(a\\mid s\)of states and state\-action pairs\.

WritingJ⁡\(θ\):=J⁡\(πθ\)J\(\\theta\):=J\(\\pi\_\{\\theta\}\),Qθ:=QπθQ\_\{\\theta\}:=Q\_\{\\pi\_\{\\theta\}\}, andVθ:=VπθV\_\{\\theta\}:=V\_\{\\pi\_\{\\theta\}\}, our objective is to findθ⋆=arg⁡maxθ∈Θ⁡J⁡\(θ\)\\theta^\{\\star\}=\\arg\\max\_\{\\theta\\in\\Theta\}J\(\\theta\)\. We follow the multi\-agent policy gradient theorem from\[[30](https://arxiv.org/html/2609.25701#bib.bib5)\], where each agent improves its policy along the direction

hi​\(θ\):=𝔼dθ,πθ​\[∇θi​log​πθii​\(ai∣s\)​\(Qθ​\(s,a\)−Vθ​\(s\)\)\]\.\\displaystyle h^\{i\}\(\\theta\):=\\mathbb\{E\}\_\{d\_\{\\theta\},\\pi\_\{\\theta\}\}\\left\[\\nabla\_\{\\theta^\{i\}\}\\log\\pi^\{i\}\_\{\\theta^\{i\}\}\(a^\{i\}\\mid s\)\\big\(Q\_\{\\theta\}\(s,a\)\-V\_\{\\theta\}\(s\)\\big\)\\right\]\.\(7\)Note that \([7](https://arxiv.org/html/2609.25701#S3.E7)\) follows the form given in\[[24](https://arxiv.org/html/2609.25701#bib.bib4),[30](https://arxiv.org/html/2609.25701#bib.bib5)\]which is the surrogate for∇θiJ​\(θ\)\\nabla\_\{\\theta^\{i\}\}J\(\\theta\)obtained by taking the expectation under the on\-policy stationary distributiondθd\_\{\\theta\}rather than the discounted visitation measure\.

### III\-BDecentralized Policy Evaluation

Evaluating \([6](https://arxiv.org/html/2609.25701#S3.E6)\) requires evaluations ofr¯​\(s,a\)\\bar\{r\}\(s,a\)andVθ​\(s\)V\_\{\\theta\}\(s\), which are not available to individual agents as rewards are private\. Therefore, we adopt the consensus\-based AC\-MARL algorithm from\[[3](https://arxiv.org/html/2609.25701#bib.bib1)\], where each agent maintains approximationsr¯​\(s,a,λi\)≈r¯​\(s,a\)\\bar\{r\}\(s,a;\\lambda^\{i\}\)\\approx\\bar\{r\}\(s,a\)andV⁡\(s,vi\)≈Vθ​\(s\)V\(s;v^\{i\}\)\\approx V\_\{\\theta\}\(s\), parameterized byλi\\lambda^\{i\}andviv^\{i\}, respectively, while reaching consensus onλi,vi\\lambda^\{i\},v^\{i\}over the communication graph𝒢t\\mathcal\{G\}\_\{t\}\. In this paper, we consider linear approximation, i\.e\.,

r¯​\(s,a,λi\)=f​\(s,a\)⊤​λi,V⁡\(s,vi\)=ϕ​\(s\)⊤​vi,\\displaystyle\\bar\{r\}\(s,a;\\lambda^\{i\}\)=f\(s,a\)^\{\\top\}\\lambda^\{i\},\\qquad V\(s;v^\{i\}\)=\\phi\(s\)^\{\\top\}v^\{i\},\(8\)with the assumption:

###### Assumption 1\.

The feature vectorsf⁡\(s,a\)=\[f1​\(s,a\),…,fM​\(s,a\)\]⊤∈ℝMf\(s,a\)=\[f\_\{1\}\(s,a\),\\dots,f\_\{M\}\(s,a\)\]^\{\\top\}\\in\\mathbb\{R\}^\{M\}andϕ⁡\(s\)=\[ϕ1​\(s\),…,ϕL​\(s\)\]⊤∈ℝL\\phi\(s\)=\[\\phi\_\{1\}\(s\),\\dots,\\phi\_\{L\}\(s\)\]^\{\\top\}\\in\\mathbb\{R\}^\{L\}are uniformly bounded for anys∈𝒮s\\in\\mathcal\{S\}anda∈𝒜a\\in\\mathcal\{A\}\. Furthermore, if we define the feature matrix𝐅∈ℝ\|𝒮\|⋅\|𝒜\|×M\\mathbf\{F\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\cdot\|\\mathcal\{A\}\|\\times M\}with itsmm\-th column\[fm​\(s,a\),s∈𝒮,a∈𝒜\]⊤\[f\_\{m\}\(s,a\),\\ s\\in\\mathcal\{S\},a\\in\\mathcal\{A\}\]^\{\\top\}for anym∈\{1,…,M\}m\\in\\\{1,\\dots,M\\\}, and the feature matrix𝚽∈ℝ\|𝒮\|×L\\mathbf\{\\Phi\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\times L\}with\[ϕl​\(s\),s∈𝒮\]⊤\[\\phi\_\{l\}\(s\),\\ s\\in\\mathcal\{S\}\]^\{\\top\}as itsll\-th column for anyl∈\{1,…,L\}l\\in\\\{1,\\dots,L\\\}, then both𝚽\\mathbf\{\\Phi\}and𝐅\\mathbf\{F\}have full column rank\.

The assumption of the full\-rank feature matrices allow us to characterize a unique asymptotically stable equilibrium in the estimations of the critic and team\-averaged reward functions\.

In\[[3](https://arxiv.org/html/2609.25701#bib.bib1)\], at timet∈ℤt\\in\\mathbb\{Z\}, each agent first uses the current statests\_\{t\}, next statest\+1s\_\{t\+1\}, and its*private*rewardrt\+1ir^\{i\}\_\{t\+1\}to compute its local TD error and reward\-estimation error:

ψti\\displaystyle\\psi\_\{t\}^\{i\}=rt\+1i\+γ​V​\(st\+1,vti\)−V⁡\(st,vti\),\\displaystyle=r^\{i\}\_\{t\+1\}\+\\gamma V\(s\_\{t\+1\};v\_\{t\}^\{i\}\)\-V\(s\_\{t\};v\_\{t\}^\{i\}\),\(9a\)ξti\\displaystyle\\xi\_\{t\}^\{i\}=rt\+1i−r¯​\(st,at,λti\),\\displaystyle=r^\{i\}\_\{t\+1\}\-\\bar\{r\}\(s\_\{t\},a\_\{t\};\\lambda\_\{t\}^\{i\}\),\(9b\)respectively\. Then, using \([9](https://arxiv.org/html/2609.25701#S3.E9)\), each agent updates its parameters by interleaving local stochastic approximation steps

v~ti\\displaystyle\\tilde\{v\}^\{i\}\_\{t\}=vti\+αtv⋅ψti⋅∇viV​\(st,vti\),\\displaystyle=v\_\{t\}^\{i\}\+\\alpha\_\{t\}^\{v\}\\cdot\\psi\_\{t\}^\{i\}\\cdot\\nabla\_\{v^\{i\}\}V\(s\_\{t\};v\_\{t\}^\{i\}\),\(10a\)λ~ti\\displaystyle\\tilde\{\\lambda\}\_\{t\}^\{i\}=λti\+αtλ⋅ξti⋅∇λir¯​\(st,at,λti\),\\displaystyle=\\lambda\_\{t\}^\{i\}\+\\alpha\_\{t\}^\{\\lambda\}\\cdot\\xi^\{i\}\_\{t\}\\cdot\\nabla\_\{\\lambda^\{i\}\}\\bar\{r\}\(s\_\{t\},a\_\{t\};\\lambda\_\{t\}^\{i\}\),\(10b\)with consensus over𝒢t\\mathcal\{G\}\_\{t\}:

vt\+1i=∑k∈ℬi,twv,ti,k​v~tk,λt\+1i=∑k∈ℬi,twλ,ti,k​λ~tk,\\displaystyle v\_\{t\+1\}^\{i\}=\\sum\_\{k\\in\\mathcal\{B\}\_\{i,t\}\}w\_\{v,t\}^\{i,k\}\\tilde\{v\}^\{k\}\_\{t\},\\quad\\lambda\_\{t\+1\}^\{i\}=\\sum\_\{k\\in\\mathcal\{B\}\_\{i,t\}\}w\_\{\\lambda,t\}^\{i,k\}\\tilde\{\\lambda\}^\{k\}\_\{t\},\(11\)whereαtv,αtλ\>0\\alpha\_\{t\}^\{v\},\\alpha\_\{t\}^\{\\lambda\}\>0are step sizes and the consensus weights satisfy∑k∈ℬi,twv,ti,k=∑k∈ℬi,twλ,ti,k=1\\sum\_\{k\\in\\mathcal\{B\}\_\{i,t\}\}w^\{i,k\}\_\{v,t\}=\\sum\_\{k\\in\\mathcal\{B\}\_\{i,t\}\}w^\{i,k\}\_\{\\lambda,t\}=1for allt∈ℤ≥0t\\in\\mathbb\{Z\}\_\{\\geq 0\}\.

Becauseψti\\psi^\{i\}\_\{t\}andξti\\xi^\{i\}\_\{t\}are formed fromrt\+1ir^\{i\}\_\{t\+1\}rather thanr¯​\(st,at\)\\bar\{r\}\(s\_\{t\},a\_\{t\}\), the local steps \([10](https://arxiv.org/html/2609.25701#S3.E10)\) alone are generally biased with respect to the team objective\. This discrepancy is compensated for by the consensus step in \([11](https://arxiv.org/html/2609.25701#S3.E11)\), which drives the agents toward agreement\. Consequently, every agent converges to a common limit determined by the team\-average rewardr¯\\bar\{r\}under some assumptions\.

### III\-CByzantine Resilient AC\-MARL

However, such AC\-MARL methods are vulnerable to Byzantine agents who deviate arbitrarily from the prescribed protocols\[[14](https://arxiv.org/html/2609.25701#bib.bib10),[13](https://arxiv.org/html/2609.25701#bib.bib18)\]\. Although numerous methods have been proposed to ensure resilience\[[30](https://arxiv.org/html/2609.25701#bib.bib5),[28](https://arxiv.org/html/2609.25701#bib.bib29),[31](https://arxiv.org/html/2609.25701#bib.bib31)\], they only guarantee convergence to a neighborhood of the attack\-free limit that would be achieved in the absence of Byzantine attacks\. In fact, finding the exact optimal value functions in the presence of Byzantine agents is generally impossible\[[26](https://arxiv.org/html/2609.25701#bib.bib14)\]\. Therefore, we consider a slightly weaker but practical model in which Byzantine agents can only attack in the communication layer:

###### Definition 2\(FF\-total Byzantine Edge Attack\)\.

Consider the two\-hop communication of Definition[1](https://arxiv.org/html/2609.25701#Thmdefinition1)\. An edge\(i,j\)∈ℰℬz​\(t\)⊆ℰt\(i,j\)\\in\\mathcal\{E\}\_\{\\mathcal\{B\}\}^\{z\}\(t\)\\subseteq\\mathcal\{E\}\_\{t\}is said to be under aByzantine edge attackduring roundz∈\{1,2\}z\\in\\\{1,2\\\}at timettif the message sent by agentiiis arbitrarily altered or dropped before being received by agentjj; that is,

z=1:\\displaystyle z=1:mii→j​\(t\)≠mi​\(t\),\\displaystyle\\quad m^\{i\\to j\}\_\{i\}\(t\)\\neq m\_\{i\}\(t\),z=2:\\displaystyle z=2:mki→j​\(t\)≠mkk→i​\(t\),for some​k∈𝒩i,t\.\\displaystyle\\quad m^\{i\\to j\}\_\{k\}\(t\)\\neq m^\{k\\to i\}\_\{k\}\(t\),\\ \\text\{ for some \}k\\in\\mathcal\{N\}\_\{i,t\}\.
The network𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)is said to be under anFF\-total Byzantine edge attackif∑z=12\|ℰℬz​\(t\)\|≤F\\sum\_\{z=1\}^\{2\}\|\\mathcal\{E\}\_\{\\mathcal\{B\}\}^\{z\}\(t\)\|\\leq F,∀t∈ℤ≥0\\forall t\\in\\mathbb\{Z\}\_\{\\geq 0\}\.

We assume that Byzantine edge attackers have limited resources and can compromise at mostFFcommunications during each time steptt\. By definition, an attacker may corrupt either an agent’s original message or a message relayed by an intermediate agent\. This attack model is closely related to the communication attack models studied in\[[31](https://arxiv.org/html/2609.25701#bib.bib31),[43](https://arxiv.org/html/2609.25701#bib.bib26)\]\.

Unlike much of the Byzantine MARL literature that assumes agents themselves are unreliable, we consider only*unreliable communication\.*Thus, we assume that

###### Assumption 2\.

All agentsi∈𝒱i\\in\\mathcal\{V\}are cooperative and follow the prescribed protocol\.

Leveraging this assumption on the agents’ behavior \- equivalently, that adversarial behavior is confined to the communication layer \- we aim to develop AC\-MARL that is fully resilient to Byzantine attacks and recovers the learning performance achievable in the absence of attacks, rather than merely guaranteeing convergence to a neighborhood of the attack\-free performance\. Our problem is therefore as follows:

###### Problem 1\.

Design a resilient AC\-MARL algorithm such that, under Assumptions[1](https://arxiv.org/html/2609.25701#Thmassumption1)\-[2](https://arxiv.org/html/2609.25701#Thmassumption2)and anFF\-total Byzantine edge attack, the critic, team\-reward, and policy parameter estimates\{vti\}\\\{v^\{i\}\_\{t\}\\\},\{λti\}\\\{\\lambda^\{i\}\_\{t\}\\\}, and\{θti\}\\\{\\theta^\{i\}\_\{t\}\\\}of every agenti∈𝒱i\\in\\mathcal\{V\}converge almost surely to the same limits attained in the absence of attacks, using two\-hop communications over𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)\.

By \([11](https://arxiv.org/html/2609.25701#S3.E11)\), each agent updates its parameters from the messages received from its neighbors\. Under anFF\-total Byzantine edge attack some of these messages are corrupted, but an agent cannot tell which messages to trust and filter\. The problem therefore reduces to replacing the weighted average in \([11](https://arxiv.org/html/2609.25701#S3.E11)\) with a robust aggregation operatorℛ\\mathcal\{R\}such that

vt\+1i,λt\+1i=ℛ⁡\(\{mkj→i\}k∈ℬi,t∪𝒩i,t\(2\)\)\\displaystyle v\_\{t\+1\}^\{i\},\\lambda\_\{t\+1\}^\{i\}=\\mathcal\{R\}\\left\(\\\{m^\{j\\to i\}\_\{k\}\\\}\_\{k\\in\\mathcal\{B\}\_\{i,t\}\\cup\\mathcal\{N\}\_\{i,t\}^\{\(2\)\}\}\\right\)\(12\)using only the messages available to agentii\. Thus, the main challenge is to design an aggregation rule that can identify and filter unreliable messages without disrupting the learning performance\.

We develop a method that guarantees each agent determines which messages to trust and filter through two\-hop communication, such that the \(i\) actual induced communication remains connected and undirected \([Lemma2](https://arxiv.org/html/2609.25701#Thmlemma2)\) and \(ii\)ℛ\\mathcal\{R\}completely filters out the Byzantine\-induced messages in its update \([Lemma3](https://arxiv.org/html/2609.25701#Thmlemma3)\)\. Combining these two results, we demonstrate that our method ensures the same convergence guarantees as in the absence of attacks \(Theorems[1](https://arxiv.org/html/2609.25701#Thmtheorem1)\-[2](https://arxiv.org/html/2609.25701#Thmtheorem2)\)\.

## IVMethod

Before presenting our method, we first provide the intuition\. From a local perspective, agents cannot directly identify which messages from one\-hop neighbors are compromised by Byzantine edge attacks\. Therefore, many Byzantine\-resilient methods rely on blind trimmed\-mean techniques to discard outlier parameters\. While effective, such filtering approaches have two fundamental limitations\. First, because each agent independently filters the received messages, different agents may retain different subsets of their neighbors’ parameters, breaking the symmetry of the underlying information flow and, consequently, the doubly stochastic property of the mixing weight matrix\. Second, even after filtering, Byzantine messages that remain within the accepted range can still introduce a systematic bias, preventing the agents from fully recovering the attack\-free learning behavior\.

Our method leverages message redundancy through two\-hop communication\. Specifically, each agent relays the information received from its one\-hop neighbors\. As a result, agenti∈𝒱i\\in\\mathcal\{V\}may receive information originating from the same agentk∈𝒩i,t\(2\)∪𝒩i,tk\\in\\mathcal\{N\}\_\{i,t\}^\{\(2\)\}\\cup\\mathcal\{N\}\_\{i,t\}through multiple distinct one\-hop neighbors, corresponding to different communication paths\. Under anFF\-total Byzantine edge attack, only a limited number of messages through these paths can be compromised\. As a result, the same parameter update from the same two\-hop neighbor may be relayed through multiple independent paths, providing redundant copies of the information available to agentii\. By cross\-checking these redundant parameter updates, agentiican aggregate messages while filtering the influence of Byzantine\-corrupted information\.

### IV\-AFully Resilient Actor\-Critic MARL \(FRAC\-MARL\)

Algorithm 1Fully Resilient Actor\-Critic MARL \(FRAC\-MARL\)Inputs :Threshold

τ\\tauand step sizes

αtθ,αtv,αtλ\{\\alpha\_\{t\}^\{\\theta\}\},\{\\alpha\_\{t\}^\{v\}\},\{\\alpha\_\{t\}^\{\\lambda\}\}
//Local Update

1Take action

ati∼πθtii\(⋅∣st\)a\_\{t\}^\{i\}\\sim\\pi^\{i\}\_\{\\theta\_\{t\}^\{i\}\}\(\\cdot\\mid s\_\{t\}\), and observe next state

st\+1s\_\{t\+1\}and local reward

rt\+1ir\_\{t\+1\}^\{i\}
2Update actor

δti\\displaystyle\\delta\_\{t\}^\{i\}=r¯​\(st,at,λti\)\+γ​V​\(st\+1,vti\)−V⁡\(st,vti\)\\displaystyle=\\bar\{r\}\(s\_\{t\},a\_\{t\};\\lambda^\{i\}\_\{t\}\)\+\\gamma V\(s\_\{t\+1\};v\_\{t\}^\{i\}\)\-V\(s\_\{t\};v\_\{t\}^\{i\}\)θt\+1i\\displaystyle\\theta\_\{t\+1\}^\{i\}=θti\+αtθ​δti​∇θi​log⁡πθtii​\(ati∣st\)\\displaystyle=\\theta\_\{t\}^\{i\}\+\\alpha\_\{t\}^\{\\theta\}\\delta\_\{t\}^\{i\}\\nabla\_\{\\theta^\{i\}\}\\log\\pi^\{i\}\_\{\\theta^\{i\}\_\{t\}\}\(a\_\{t\}^\{i\}\\mid s\_\{t\}\)
3Update critic and reward function

ψti\\displaystyle\\psi\_\{t\}^\{i\}=rt\+1i\+γ​V​\(st\+1,vti\)−V⁡\(st,vti\)\\displaystyle=r^\{i\}\_\{t\+1\}\+\\gamma V\(s\_\{t\+1\};v\_\{t\}^\{i\}\)\-V\(s\_\{t\};v\_\{t\}^\{i\}\)\(13a\)v~ti\\displaystyle\\tilde\{v\}\_\{t\}^\{i\}=vti\+αtv​ψti​∇viV​\(st,vti\)\\displaystyle=v\_\{t\}^\{i\}\+\\alpha\_\{t\}^\{v\}\\psi\_\{t\}^\{i\}\\nabla\_\{v^\{i\}\}V\(s\_\{t\};v\_\{t\}^\{i\}\)\(13b\)λ~ti\\displaystyle\\tilde\{\\lambda\}\_\{t\}^\{i\}=λti\+αtλ​\(rt\+1i−r¯​\(st,at,λti\)\)​∇λir¯​\(st,at,λti\)\\displaystyle=\\lambda\_\{t\}^\{i\}\+\\alpha\_\{t\}^\{\\lambda\}\\left\(r^\{i\}\_\{t\+1\}\-\\bar\{r\}\(s\_\{t\},a\_\{t\};\\lambda\_\{t\}^\{i\}\)\\right\)\\nabla\_\{\\lambda^\{i\}\}\\bar\{r\}\(s\_\{t\},a\_\{t\};\\lambda\_\{t\}^\{i\}\)\(13c\)
//Two\-Hop Communication

4send

mi​\(t\):=\(v~ti,λ~ti,i\)m\_\{i\}\(t\):=\(\\tilde\{v\}^\{i\}\_\{t\},\\tilde\{\\lambda\}^\{i\}\_\{t\},i\)to every

j∈𝒩i,tj\\in\\mathcal\{N\}\_\{i,t\}
5Relay

\{mkk→i​\(t\)\}k∈𝒩i,t\\\{m^\{k\\to i\}\_\{k\}\(t\)\\\}\_\{k\\in\\mathcal\{N\}\_\{i,t\}\}to every

j∈𝒩i,tj\\in\\mathcal\{N\}\_\{i,t\}
//Redundancy\-Based Filter/Consensus

6For each

k∈𝒱∖\{i\}k\\in\\mathcal\{V\}\\setminus\\\{i\\\}, collect the received copies of

mk​\(t\)m\_\{k\}\(t\), with at most one copy from each relaying agent

j∈𝒩i,tj\\in\\mathcal\{N\}\_\{i,t\}, and define a multi\-set

𝒦ti,k←\{mkj→i\(t\)∣j∈𝒩i,t,mkj→i\(t\)≠∅\}\\displaystyle\\mathcal\{K\}^\{i,k\}\_\{t\}\\leftarrow\\big\\\{\\,m^\{j\\to i\}\_\{k\}\(t\)\\ \\mid\\ j\\in\\mathcal\{N\}\_\{i,t\},\\ m^\{j\\to i\}\_\{k\}\(t\)\\neq\\varnothing\\,\\big\\\}
7Collect the indices received in the two rounds,

ℐi,t←\{k∈𝒱∖\{i\}∣𝒦ti,k≠∅\}\\mathcal\{I\}\_\{i,t\}\\leftarrow\\big\\\{k\\in\\mathcal\{V\}\\setminus\\\{i\\\}\\mid\\mathcal\{K\}^\{i,k\}\_\{t\}\\neq\\emptyset\\big\\\}
8for*k∈ℐi,tk\\in\\mathcal\{I\}\_\{i,t\}*do

9Find the most repeated message,

\(v^tk,λ^tk,k\)←mode⁡\(𝒦ti,k\)\\displaystyle\(\\hat\{v\}\_\{t\}^\{k\},\\hat\{\\lambda\}\_\{t\}^\{k\},k\)\\leftarrow\{\\rm mode\}\\big\(\\mathcal\{K\}^\{i,k\}\_\{t\}\\big\)\(14\)
10

ℳi,t=\{k∈𝒱∖\{i\}∣mode​\_​count​\(𝒦ti,k\)≥τ\}\\mathcal\{M\}\_\{i,t\}=\\left\\\{k\\in\\mathcal\{V\}\\setminus\\\{i\\\}\\mid\\mathrm\{mode\\\_count\}\(\\mathcal\{K\}\_\{t\}^\{i,k\}\)\\geq\\tau\\right\\\}
11Update the parameters

vt\+1i=wv,ti,i​v~ti\+∑j∈ℳi,twv,ti,j​v^tj,\\displaystyle v^\{i\}\_\{t\+1\}=w\_\{v,t\}^\{i,i\}\\tilde\{v\}\_\{t\}^\{i\}\+\\sum\_\{j\\in\\mathcal\{M\}\_\{i,t\}\}w\_\{v,t\}^\{i,j\}\\hat\{v\}\_\{t\}^\{j\},\(15a\)λt\+1i=wλ,ti,i​λ~ti\+∑j∈ℳi,twλ,ti,j​λ^tj,\\displaystyle\\lambda^\{i\}\_\{t\+1\}=w\_\{\\lambda,t\}^\{i,i\}\\tilde\{\\lambda\}\_\{t\}^\{i\}\+\\sum\_\{j\\in\\mathcal\{M\}\_\{i,t\}\}w\_\{\\lambda,t\}^\{i,j\}\\hat\{\\lambda\}\_\{t\}^\{j\},\(15b\)where

∑j∈ℳi,t∪\{i\}wv,ti,j=∑j∈ℳi,t∪\{i\}wλ,ti,j=1\\sum\_\{j\\in\\mathcal\{M\}\_\{i,t\}\\cup\\\{i\\\}\}w^\{i,j\}\_\{v,t\}=\\sum\_\{j\\in\\mathcal\{M\}\_\{i,t\}\\cup\\\{i\\\}\}w^\{i,j\}\_\{\\lambda,t\}=1

The FRAC\-MARL \(outlined in[Algorithm1](https://arxiv.org/html/2609.25701#alg1)\) operates by combining local actor\-critic updates \(lines 1\-3\), adopted from\[[3](https://arxiv.org/html/2609.25701#bib.bib1), Algorithm 2\], with redundancy\-based resilient aggregation \(lines 4\-11\), which corresponds to the robust aggregatorℛ\\mathcal\{R\}in \([12](https://arxiv.org/html/2609.25701#S3.E12)\)\. At each time stept∈ℤ≥0t\\in\\mathbb\{Z\}\_\{\\geq 0\}, agenti∈𝒱i\\in\\mathcal\{V\}first performs the standard local actor\-critic updates \(lines 1\-3\), yielding intermediate value\-function and reward\-model parametersv~ti\\tilde\{v\}\_\{t\}^\{i\}andλ~ti\\tilde\{\\lambda\}\_\{t\}^\{i\}, respectively\.

After local learning, agentiibroadcasts its messagemi​\(t\)=\(v~ti,λ~ti,i\)m\_\{i\}\(t\)=\(\\tilde\{v\}\_\{t\}^\{i\},\\tilde\{\\lambda\}\_\{t\}^\{i\},i\)to its one\-hop neighbors\. Then each agent relays the messages it receives\{mkk→i​\(t\)\}k∈𝒩i,t\\\{m\_\{k\}^\{k\\to i\}\(t\)\\\}\_\{k\\in\\mathcal\{N\}\_\{i,t\}\}to its own one\-hop neighbors, allowing information to propagate over two\-hop communication paths \(lines 4\-5\)\. Then agentiistores the messages with claimed indexkkinto the multiset𝒦ti,k\\mathcal\{K\}\_\{t\}^\{i,k\}, one per relaying agent, for everyk∈𝒱∖\{i\}k\\in\\mathcal\{V\}\\setminus\\\{i\\\}\(line 6\)\. Note that, an honest relay forwards at most one message per origin, so𝒦ti,k\\mathcal\{K\}^\{i,k\}\_\{t\}receives more than one tuple fromjjonly if\(j,i\)\(j,i\)is attacked\. In this case, agentiiretains an arbitrary message for the indexkk\. Then, to filter out Byzantine\-influenced messages, agentiiperforms redundancy\-based filtering by constructing the setℳi,t\\mathcal\{M\}\_\{i,t\}containing only agentskkwhose relayed parameter updates in𝒦ti,k\\mathcal\{K\}\_\{t\}^\{i,k\}have a mode appearing at leastτ\\tautimes \(lines 7\-10\)\. Finally, the accepted critic and reward\-model parameters are aggregated via weighted averaging to updatevtiv\_\{t\}^\{i\}andλti\\lambda\_\{t\}^\{i\}\(line 11\)\.

### IV\-B\(r,r′\)\(r,r^\{\\prime\}\)\-redundancy

Note that FRAC\-MARL relies on the redundancy\-based filtering \(lines 7\-10\)\. The required level of redundancy, denoted byτ\\tau, is a user\-defined threshold that affects the filtering process and, consequently, the learning performance\. In this subsection, we introduce a novel topological property that allows us to theoretically characterize the conditions under which the proposed filtering mechanism and FRAC\-MARL achieve the desired performance\.

First, we define anrr\-2\-hop graph which is defined as below:

###### Definition 3\(rr\-2\-hop Graph\)\.

Let𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)be an undirected graph at timett\. We define therr\-2\-hop graph of𝒢t\\mathcal\{G\}\_\{t\}, denoted as𝒢tr=\(𝒱,ℰtr\)\\mathcal\{G\}^\{r\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}^\{r\}\_\{t\}\), such that an edge\(i,j\)∈ℰtr\(i,j\)\\in\\mathcal\{E\}^\{r\}\_\{t\}if\|ℬi,t∩𝒩j,t\|≥r\|\\mathcal\{B\}\_\{i,t\}\\cap\\mathcal\{N\}\_\{j,t\}\|\\geq r, whereℬi,t=𝒩i,t∪\{i\}\\mathcal\{B\}\_\{i,t\}=\\mathcal\{N\}\_\{i,t\}\\cup\\\{i\\\}\.

An illustrative example of anrr\-2\-hop graph is given in[Figure1](https://arxiv.org/html/2609.25701#S4.F1)\. Anrr\-2\-hop graph contains an edge\(i,j\)\(i,j\)if agentsiiandjjshare at leastrrneighbors \(including direct links\)\. Equivalently, there are at leastrrvertex\-disjoint paths of length at most 2 connecting them\.

###### Definition 4\(\(r,r′\)\(r,r^\{\\prime\}\)\-redundant\)\.

Let𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)be an undirected graph at timett, and let𝒢tr=\(𝒱,ℰtr\)\\mathcal\{G\}^\{r\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}^\{r\}\_\{t\}\)be itsrr\-2\-hop graph\. We say that𝒢t\\mathcal\{G\}\_\{t\}is\(r,r′\)\(r,r^\{\\prime\}\)\-redundantwithr\>r′≥0r\>r^\{\\prime\}\\geq 0at timettif:

1. 1\.𝒢tr\\mathcal\{G\}^\{r\}\_\{t\}is connected, and
2. 2\.for all\(i,j\)∉ℰtr\(i,j\)\\notin\\mathcal\{E\}^\{r\}\_\{t\},\|ℬi,t∩𝒩j,t\|≤r′\|\\mathcal\{B\}\_\{i,t\}\\cap\\mathcal\{N\}\_\{j,t\}\|\\leq r^\{\\prime\}\.

Fig\. 1:Visualizations of \(a\) graph𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)and \(b\) its55\-2\-hop graph𝒢t5=\(𝒱,ℰt5\)\\mathcal\{G\}^\{5\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}^\{5\}\_\{t\}\)at timett\. The edge\(i,j\)∈ℰt5\(i,j\)\\in\\mathcal\{E\}^\{5\}\_\{t\}, since\|ℬi,t∩𝒩j,t\|≥5\|\\mathcal\{B\}\_\{i,t\}\\cap\\mathcal\{N\}\_\{j,t\}\|\\geq 5\.Fig\. 2:\(a\)\(1,0\)\(1,0\)\-redundant graph and \(b\) its 1\-2\-hop graph\.[Figure2](https://arxiv.org/html/2609.25701#S4.F2)visualizes an\(r,r′\)\(r,r^\{\\prime\}\)\-redundant graph and itsrr\-2\-hop graph\. A graph𝒢t\\mathcal\{G\}\_\{t\}is\(r,r′\)\(r,r^\{\\prime\}\)\-redundant if two things hold\. First, itsrr\-2\-hop graph is connected\. Second, for all agent pairs not connected in therr\-2\-hop graph, they share at mostr′r^\{\\prime\}neighbors \(including direct links\) in the graph𝒢t\\mathcal\{G\}\_\{t\}\. That is, for anyi,j∈𝒱i,j\\in\\mathcal\{V\}, they share either at leastrror at mostr′r^\{\\prime\}neighbors \(including direct links\)\.

Going back to[Figure2](https://arxiv.org/html/2609.25701#S4.F2)as an example, for every edge\(i,j\)\(i,j\)in the original graph \([Figure2](https://arxiv.org/html/2609.25701#S4.F2)\(a\)\), we have\|ℬi,t∩𝒩j,t\|=1\|\\mathcal\{B\}\_\{i,t\}\\cap\\mathcal\{N\}\_\{j,t\}\|=1\. Settingr=1r=1, itsrr\-2\-hop graph \([Figure2](https://arxiv.org/html/2609.25701#S4.F2)\(b\)\) is connected\. Because every pairi,j∈𝒱i,j\\in\\mathcal\{V\}of nodes not connected in therr\-2\-hop graph satisfies\|ℬi,t∩𝒩j,t\|=0\|\\mathcal\{B\}\_\{i,t\}\\cap\\mathcal\{N\}\_\{j,t\}\|=0, the graph in[Figure2](https://arxiv.org/html/2609.25701#S4.F2)\(a\) is\(1,0\)\(1,0\)\-redundant\.

Now, we provide a useful property related to\(r,r′\)\(r,r^\{\\prime\}\)\-redundancy:

###### Lemma 1\.

Let𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)be\(r,r′\)\(r,r^\{\\prime\}\)\-redundant at timett\. Then, itsrr\-2\-hop graph𝒢tr=\(𝒱,ℰtr\)\\mathcal\{G\}^\{r\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}^\{r\}\_\{t\}\)is connected and undirected at timett\.

###### Proof\.

By[Definition4](https://arxiv.org/html/2609.25701#Thmdefinition4),𝒢tr\\mathcal\{G\}^\{r\}\_\{t\}is connected\. Furthermore, because𝒢t\\mathcal\{G\}\_\{t\}is undirected,\|ℬi,t∩𝒩j,t\|=\|ℬj,t∩𝒩i,t\|\|\\mathcal\{B\}\_\{i,t\}\\cap\\mathcal\{N\}\_\{j,t\}\|=\|\\mathcal\{B\}\_\{j,t\}\\cap\\mathcal\{N\}\_\{i,t\}\|for anyi,j∈𝒱i,j\\in\\mathcal\{V\},i≠ji\\neq j\. Hence,𝒢tr\\mathcal\{G\}^\{r\}\_\{t\}is also undirected\. ∎

[Lemma1](https://arxiv.org/html/2609.25701#Thmlemma1)characterizes the connectivity and symmetry properties of\(r,r′\)\(r,r^\{\\prime\}\)\-redundancy\. These results provide the foundation for the subsequent analysis of the robust aggregation mechanism presented in the next subsection\.

### IV\-CTheoretical Analysis

To further facilitate the convergence analysis of our algorithm, we define an induced communication graph:

###### Definition 5\(Induced Communication Graph\)\.

Let each agent execute FRAC\-MARL and construct the filtered\-neighbor setℳi,t=\{k∈𝒱∖\{i\}∣mode​\_​count​\(𝒦ti,k\)≥τ\}\\mathcal\{M\}\_\{i,t\}=\\left\\\{k\\in\\mathcal\{V\}\\setminus\\\{i\\\}\\mid\\mathrm\{mode\\\_count\}\(\\mathcal\{K\}\_\{t\}^\{i,k\}\)\\geq\\tau\\right\\\}, where multisets𝒦ti,k\\mathcal\{K\}\_\{t\}^\{i,k\}are constructed in line 6 of[Algorithm1](https://arxiv.org/html/2609.25701#alg1)\. Theinduced communication graphis𝒢tind=\(𝒱,ℰtind\)\\mathcal\{G\}\_\{t\}^\{\\rm ind\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}^\{\\rm ind\}\), where\(i,k\)∈ℰtind⇔k∈ℳi,t\(i,k\)\\in\\mathcal\{E\}\_\{t\}^\{\\rm ind\}\\iff k\\in\\mathcal\{M\}\_\{i,t\}\.

The induced graph𝒢tind\\mathcal\{G\}\_\{t\}^\{\\rm ind\}captures the information flow where agents receive the information for update even after filtering step \(lines 7\-10\) in FRAC\-MARL\. In general,𝒢tind\\mathcal\{G\}\_\{t\}^\{\\rm ind\}is a directed graph since it is possible thatk∈ℳi,tk\\in\\mathcal\{M\}\_\{i,t\}whilei∉ℳk,ti\\notin\\mathcal\{M\}\_\{k,t\}\.

For eachtt, we define two weight matricesWλ,t=\[wλ,ti,k\]∈ℝn×nW\_\{\\lambda,t\}=\[w\_\{\\lambda,t\}^\{i,k\}\]\\in\\mathbb\{R\}^\{n\\times n\}andWv,t=\[wv,ti,k\]∈ℝn×nW\_\{v,t\}=\[w\_\{v,t\}^\{i,k\}\]\\in\\mathbb\{R\}^\{n\\times n\}associated with𝒢tind\\mathcal\{G\}\_\{t\}^\{\\rm ind\}such that

wλ,ti,k=wv,ti,k=\{1nif​\(i,k\)∈ℰtind1−\|ℳi,t\|nif​k=i0otherwise\\displaystyle w\_\{\\lambda,t\}^\{i,k\}=w\_\{v,t\}^\{i,k\}=\\begin\{cases\}\\frac\{1\}\{n\}&\\text\{if \}\(i,k\)\\in\\mathcal\{E\}\_\{t\}^\{\\rm ind\}\\\\ 1\-\\frac\{\|\\mathcal\{M\}\_\{i,t\}\|\}\{n\}&\\text\{if \}k=i\\\\ 0&\\text\{otherwise\}\\end\{cases\}\(16\)
###### Lemma 2\.

Let Assumption[2](https://arxiv.org/html/2609.25701#Thmassumption2)hold\. Let𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)be\(r,r−2​F−1\)\(r,r\-2F\-1\)\-redundant wherer\>2​Fr\>2F, and suppose that each agenti∈𝒱i\\in\\mathcal\{V\}runs the FRAC\-MARL algorithm withτ=r−F\\tau=r\-Funder anFF\-total Byzantine edge attack for allt∈ℤ≥0t\\in\\mathbb\{Z\}\_\{\\geq 0\}\. Then, for allt∈ℤ≥0t\\in\\mathbb\{Z\}\_\{\\geq 0\}, the induced communication graph𝒢tind\\mathcal\{G\}^\{\\rm ind\}\_\{t\}is equal to therr\-2\-hop graph𝒢tr=\(𝒱,ℰtr\)\\mathcal\{G\}^\{r\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}^\{r\}\_\{t\}\)of𝒢t\\mathcal\{G\}\_\{t\}, i\.e\.ℰtind=ℰtr\\mathcal\{E\}^\{\\rm ind\}\_\{t\}=\\mathcal\{E\}^\{r\}\_\{t\}\. Furthermore,𝒢tind\\mathcal\{G\}^\{\\rm ind\}\_\{t\}is connected and undirected\.

###### Proof\.

By definition,\(i,k\)∈ℰtind\(i,k\)\\in\\mathcal\{E\}^\{\\rm ind\}\_\{t\}if and only ifk∈ℳi,tk\\in\\mathcal\{M\}\_\{i,t\}, so it suffices to show

\(i,k\)∈ℰtr⇔k∈ℳi,t\.\(i,k\)\\in\\mathcal\{E\}^\{r\}\_\{t\}\\iff k\\in\\mathcal\{M\}\_\{i,t\}\.\(17\)We show in three parts\.

Part 1 \(⇒\\Rightarrow\):Suppose first that\(i,k\)∈ℰtr\(i,k\)\\in\\mathcal\{E\}\_\{t\}^\{r\}\. Then,\|ℬi,t∩𝒩k,t\|≥r\|\\mathcal\{B\}\_\{i,t\}\\cap\\mathcal\{N\}\_\{k,t\}\|\\geq r\. By[Assumption2](https://arxiv.org/html/2609.25701#Thmassumption2), all agentsi∈𝒱i\\in\\mathcal\{V\}generate and transmit the correct parameter pairs\(v~ti,λ~ti\)\(\\tilde\{v\}\_\{t\}^\{i\},\\tilde\{\\lambda\}\_\{t\}^\{i\}\)according to \([13](https://arxiv.org/html/2609.25701#S4.E13)\) \(lines 1\-3 in[Algorithm1](https://arxiv.org/html/2609.25701#alg1)\)\. Since at mostFFrelayed transmissions can be corrupted under anFF\-total Byzantine edge attack, agentsiiandkkreceive at leastr−Fr\-Fidentical copies of each other’s parameter tuple\. Because FRAC\-MARL uses the thresholdτ=r−F\\tau=r\-F, both agents accept one another, i\.e\., we havek∈ℳi,tk\\in\\mathcal\{M\}\_\{i,t\}\.

Part 2 \(⇐\\Leftarrow\):Now assume to the contrary thatk∈ℳi,tk\\in\\mathcal\{M\}\_\{i,t\}and\(i,k\)∉ℰtr\(i,k\)\\notin\\mathcal\{E\}\_\{t\}^\{r\}\. Then since \(i\)\(i,k\)∉ℰtr\(i,k\)\\notin\\mathcal\{E\}\_\{t\}^\{r\}and \(ii\)𝒢t\\mathcal\{G\}\_\{t\}is\(r,r−2​F−1\)\(r,r\-2F\-1\)\-redundant,\|ℬi,t∩𝒩k,t\|≤r−2​F−1\|\\mathcal\{B\}\_\{i,t\}\\cap\\mathcal\{N\}\_\{k,t\}\|\\leq r\-2F\-1\. A tuple claiming the origin ofkkcan reach agentiiin only two ways\. First, along an uncorrupted path: \(i\) agentkkbroadcasts to𝒩k,t\\mathcal\{N\}\_\{k,t\}in the first round, andj∈𝒩i,t∩𝒩k,tj\\in\\mathcal\{N\}\_\{i,t\}\\cap\\mathcal\{N\}\_\{k,t\}forwards it toiiin the second round, and \(ii\)iireceives it directly wheneveri∈𝒩k,ti\\in\\mathcal\{N\}\_\{k,t\}; the number of such paths is exactly\|ℬi,t∩𝒩k,t\|\|\\mathcal\{B\}\_\{i,t\}\\cap\\mathcal\{N\}\_\{k,t\}\|\. Second, along a compromised edge: an attacker may alter a transmission so that it carries a tuple labeled with originkk, whether or not the sender ever received one\. Each compromised edge contributes at most one such tuple to𝒦ti,k\\mathcal\{K\}\_\{t\}^\{i,k\}, and at mostFFedges are compromised in total\. Hence

\|𝒦ti,k\|≤\|ℬi,t∩𝒩k,t\|\+F≤\(r−2​F−1\)\+F<τ=r−F,\\displaystyle\|\\mathcal\{K\}\_\{t\}^\{i,k\}\|\\leq\|\\mathcal\{B\}\_\{i,t\}\\cap\\mathcal\{N\}\_\{k,t\}\|\+F\\leq\(r\-2F\-1\)\+F<\\tau=r\-F,somode​\_​count​\(𝒦ti,k\)≤\|𝒦ti,k\|<τ\\mathrm\{mode\\\_count\}\(\\mathcal\{K\}\_\{t\}^\{i,k\}\)\\leq\|\\mathcal\{K\}\_\{t\}^\{i,k\}\|<\\tauandk∉ℳi,tk\\notin\\mathcal\{M\}\_\{i,t\}, which is a contradiction\.

Part 3:Combining Parts 1 and 2, we have shown that \([17](https://arxiv.org/html/2609.25701#S4.E17)\) holds\. Thus,ℰtind=ℰtr\\mathcal\{E\}^\{\\rm ind\}\_\{t\}=\\mathcal\{E\}^\{r\}\_\{t\}\. Also, together with[Lemma1](https://arxiv.org/html/2609.25701#Thmlemma1), this implies𝒢tind\\mathcal\{G\}^\{\\rm ind\}\_\{t\}is undirected and connected\. ∎

[Lemma2](https://arxiv.org/html/2609.25701#Thmlemma2)shows that the \(i\) communication graph induced by the FRAC\-MARL filtering mechanism coincides with therr\-2\-hop graph of the underlying communication graph𝒢t\\mathcal\{G\}\_\{t\}, and thus \(ii\) is undirected and connected at everytt\. Thus, the resulting weight matricesWv,tW\_\{v,t\}andWλ,tW\_\{\\lambda,t\}defined in \([16](https://arxiv.org/html/2609.25701#S4.E16)\) are doubly stochastic\. Also their nonzero elements are uniformly bounded below by1/n1/n\.

###### Lemma 3\.

Let[Assumption2](https://arxiv.org/html/2609.25701#Thmassumption2)hold\. Let𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)be\(r,r−2​F−1\)\(r,r\-2F\-1\)\-redundant wherer\>2​Fr\>2F, and suppose that each agenti∈𝒱i\\in\\mathcal\{V\}runs the FRAC\-MARL algorithm withτ=r−F\\tau=r\-Funder anFF\-total Byzantine edge attack for allt∈ℤ≥0t\\in\\mathbb\{Z\}\_\{\\geq 0\}\. Then, for any timet∈ℤ≥0t\\in\\mathbb\{Z\}\_\{\\geq 0\}, agenti∈𝒱i\\in\\mathcal\{V\}, and every accepted agent indicesk∈ℳi,tk\\in\\mathcal\{M\}\_\{i,t\}, we have\(v^tk,λ^tk\)=\(v~tk,λ~tk\)\(\\hat\{v\}\_\{t\}^\{k\},\\hat\{\\lambda\}\_\{t\}^\{k\}\)=\(\\tilde\{v\}\_\{t\}^\{k\},\\tilde\{\\lambda\}\_\{t\}^\{k\}\), where\(v^tk,λ^tk\)\(\\hat\{v\}\_\{t\}^\{k\},\\hat\{\\lambda\}\_\{t\}^\{k\}\)and\(v~tk,λ~tk\)\(\\tilde\{v\}\_\{t\}^\{k\},\\tilde\{\\lambda\}\_\{t\}^\{k\}\)are defined in \([14](https://arxiv.org/html/2609.25701#S4.E14)\) and \([13](https://arxiv.org/html/2609.25701#S4.E13)\), respectively\. Consequently, the consensus update laws \([15](https://arxiv.org/html/2609.25701#S4.E15)\) depend only on true local parameter estimates of agents and are independent of Byzantine\-modified transmissions\.

###### Proof\.

By[Assumption2](https://arxiv.org/html/2609.25701#Thmassumption2), all agentsk∈𝒱k\\in\\mathcal\{V\}generate parameter pairs\(v~tk,λ~tk\)\(\\tilde\{v\}\_\{t\}^\{k\},\\tilde\{\\lambda\}\_\{t\}^\{k\}\)according to \([13](https://arxiv.org/html/2609.25701#S4.E13)\) and transmit them\. Also, since𝒢t\\mathcal\{G\}\_\{t\}is\(r,r−2​F−1\)\(r,r\-2F\-1\)\-redundant and is underFF\-total Byzantine edge attack, any pair of agents connected in therr\-2\-hop graph has at leastr−Fr\-Findependent relayed copies of the correct message at each time steptt\.

Now assume to the contrary that\(v^tk,λ^tk\)≠\(v~tk,λ~tk\)\(\\hat\{v\}\_\{t\}^\{k\},\\hat\{\\lambda\}\_\{t\}^\{k\}\)\\neq\(\\tilde\{v\}\_\{t\}^\{k\},\\tilde\{\\lambda\}\_\{t\}^\{k\}\)\. Acceptance requires at leastτ=r−F\\tau=r\-Fidentical occurrences\. Since onlyFFtransmissions can be corrupted in total, at mostFFcopies of any altered value can exist\. However, sincer\>2​Fr\>2F, we getτ=r−F\>F\\tau=r\-F\>F, which leads to a contradiction\. ∎

Using these lemmas, we now provide our main results\. To establish almost sure convergence under linear function approximation with[Assumption1](https://arxiv.org/html/2609.25701#Thmassumption1), we formalize the following standard regularity conditions regarding the reward bounds, learning step sizes, and parameter spaces\.

###### Assumption 3\.

For every agenti∈𝒱i\\in\\mathcal\{V\}, states∈𝒮s\\in\\mathcal\{S\}, actionai∈𝒜ia^\{i\}\\in\\mathcal\{A\}^\{i\}, and parameterθi∈Θi\\theta^\{i\}\\in\\Theta^\{i\}, the local policyπθii​\(ai∣s\)\\pi\_\{\\theta^\{i\}\}^\{i\}\(a^\{i\}\\mid s\)is positive and continuously differentiable with respect toθi\\theta^\{i\}overΘi\\Theta^\{i\}\.

###### Assumption 4\.

The local reward functionri​\(s,a\)r^\{i\}\(s,a\)is uniformly bounded for every agenti∈𝒱i\\in\\mathcal\{V\}, states∈𝒮s\\in\\mathcal\{S\}, and joint actiona∈𝒜a\\in\\mathcal\{A\}\.

###### Assumption 5\.

The stochastic approximation step sizesαtv\\alpha\_\{t\}^\{v\},αtλ\\alpha\_\{t\}^\{\\lambda\}, andαtθ\\alpha\_\{t\}^\{\\theta\}are positive sequences satisfying:

∑t=0∞αtq=∞,∑t=0∞\(αtq\)2<∞,∀q∈\{v,λ,θ\},\\displaystyle\\sum\_\{t=0\}^\{\\infty\}\\alpha\_\{t\}^\{q\}=\\infty,\\quad\\sum\_\{t=0\}^\{\\infty\}\(\\alpha\_\{t\}^\{q\}\)^\{2\}<\\infty,\\quad\\forall q\\in\\\{v,\\lambda,\\theta\\\},\(18\)along with the two\-time\-scale conditionαtθ=o⁡\(αtv\)=o⁡\(αtλ\)\\alpha\_\{t\}^\{\\theta\}=o\(\\alpha\_\{t\}^\{v\}\)=o\(\\alpha\_\{t\}^\{\\lambda\}\), and the limit tracking propertylimt→∞αt\+1q/αtq=1\\lim\_\{t\\to\\infty\}\\alpha\_\{t\+1\}^\{q\}/\\alpha\_\{t\}^\{q\}=1\.

###### Assumption 6\.

For agenti∈𝒱i\\in\\mathcal\{V\}, the parameter spaceΘi⊂ℝbi\\Theta^\{i\}\\subset\\mathbb\{R\}^\{b\_\{i\}\}is compact and hyper\-rectangular\. The policy parameter update includes a projection operatorΨΘi:ℝbi→Θi\\Psi\_\{\\Theta^\{i\}\}:\\mathbb\{R\}^\{b\_\{i\}\}\\rightarrow\\Theta^\{i\}that maps any exterior iterate back onto the boundary ofΘi\\Theta^\{i\}\.

Assumptions[3](https://arxiv.org/html/2609.25701#Thmassumption3)and[4](https://arxiv.org/html/2609.25701#Thmassumption4)provide the regularity and boundedness conditions needed for the policy\-gradient and TD\-error terms to be well defined\.[Assumption5](https://arxiv.org/html/2609.25701#Thmassumption5)establishes the two\-time\-scale stochastic approximation framework, which is common in actor\-critic setting\[[42](https://arxiv.org/html/2609.25701#bib.bib38)\]\. Since the actor parametersθt\\theta\_\{t\}change asymptotically more slowly than the critic and reward parametersvtv\_\{t\}andλt\\lambda\_\{t\},vtv\_\{t\}andλt\\lambda\_\{t\}evolve on a faster timescale thanθt\\theta\_\{t\}, allowing the critic and reward parameter estimates to track their equilibria for the current policy while the actor parameters are effectively quasi\-static\. Finally,[Assumption6](https://arxiv.org/html/2609.25701#Thmassumption6)ensures that projection operatorΨΘi\\Psi\_\{\\Theta^\{i\}\}satisfies the conditions required by the projected stochastic approximation analysis used to establish convergence of the limiting ODEs, following the analysis of\[[3](https://arxiv.org/html/2609.25701#bib.bib1),[30](https://arxiv.org/html/2609.25701#bib.bib5)\]\. UsingΨΘi\\Psi\_\{\\Theta^\{i\}\}, fory∈ℝbiy\\in\\mathbb\{R\}^\{b\_\{i\}\}andθi∈Θi\\theta^\{i\}\\in\\Theta^\{i\}, we further define

Ψ^Θi​\[y\]:=lim0<η→0ΨΘi​\(θi\+η​y\)−θiη,\\displaystyle\\hat\{\\Psi\}\_\{\\Theta^\{i\}\}\[y\]:=\\lim\_\{0<\\eta\\to 0\}\\frac\{\\Psi\_\{\\Theta^\{i\}\}\(\\theta^\{i\}\+\\eta y\)\-\\theta^\{i\}\}\{\\eta\},\(19\)the projection ofyyonto the tangent cone ofΘi\\Theta^\{i\}atθi\\theta^\{i\}, which reduces toyywheneverθi\\theta^\{i\}lies in the interior ofΘi\\Theta^\{i\}\. When the limit in \([19](https://arxiv.org/html/2609.25701#S4.E19)\) is not unique, we defineΨ^Θi​\[y\]\\hat\{\\Psi\}\_\{\\Theta^\{i\}\}\[y\]as the set of all possible limit points\.

We first show the convergence of the critic and team reward approximation functions\. Let𝐃sθ=diag⁡\(\[dθ​\(s\),s∈𝒮\]\)∈ℝ\|𝒮\|×\|𝒮\|\\mathbf\{D\}^\{\\theta\}\_\{s\}=\{\\rm diag\}\\left\(\\begin\{bmatrix\}d\_\{\\theta\}\(s\),\\ s\\in\\mathcal\{S\}\\end\{bmatrix\}\\right\)\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\times\|\\mathcal\{S\}\|\}and𝐃s,aθ=diag⁡\(\[dθ′​\(s,a\),s∈𝒮,a∈𝒜\]\)∈ℝ\|𝒮\|⋅\|𝒜\|×\|𝒮\|⋅\|𝒜\|\\mathbf\{D\}^\{\\theta\}\_\{s,a\}=\{\\rm diag\}\\left\(\\begin\{bmatrix\}d\_\{\\theta\}^\{\\prime\}\(s,a\),\\ s\\in\\mathcal\{S\},a\\in\\mathcal\{A\}\\end\{bmatrix\}\\right\)\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\cdot\|\\mathcal\{A\}\|\\times\|\\mathcal\{S\}\|\\cdot\|\\mathcal\{A\}\|\}denote the diagonal matrices corresponding to the state distribution and state\-action distribution induced by policyπθ\\pi\_\{\\theta\}, respectively\. Also, we denote𝐑=\[r¯​\(s,a\),s∈𝒮,a∈𝒜\]⊤∈ℝ\|𝒮\|⋅\|𝒜\|\\mathbf\{R\}=\\begin\{bmatrix\}\\bar\{r\}\(s,a\),\\ s\\in\\mathcal\{S\},a\\in\\mathcal\{A\}\\end\{bmatrix\}^\{\\top\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\cdot\|\\mathcal\{A\}\|\}and𝐑θ=\[∑a∈𝒜πθ​\(a∣s\)​r¯​\(s,a\),s∈𝒮\]⊤∈ℝ\|𝒮\|\\mathbf\{R\}\_\{\\theta\}=\\begin\{bmatrix\}\\sum\_\{a\\in\\mathcal\{A\}\}\\pi\_\{\\theta\}\(a\\mid s\)\\bar\{r\}\(s,a\),\\ s\\in\\mathcal\{S\}\\end\{bmatrix\}^\{\\top\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\}\. We denote𝐏θ=\[Pθ​\(s′∣s\),s∈𝒮,s′∈𝒮\]∈ℝ\|𝒮\|×\|𝒮\|\\mathbf\{P\}\_\{\\theta\}=\\begin\{bmatrix\}P\_\{\\theta\}\(s^\{\\prime\}\\mid s\),s\\in\\mathcal\{S\},s^\{\\prime\}\\in\\mathcal\{S\}\\end\{bmatrix\}\\in\\mathbb\{R\}^\{\|\\mathcal\{S\}\|\\times\|\\mathcal\{S\}\|\}\.

###### Theorem 1\.

Let Assumptions[1](https://arxiv.org/html/2609.25701#Thmassumption1)\-[5](https://arxiv.org/html/2609.25701#Thmassumption5)hold and fixθ∈Θ\\theta\\in\\Theta\. Suppose that, for everyt∈ℤ≥0t\\in\\mathbb\{Z\}\_\{\\geq 0\}, \(i\) the graph𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)is\(r,r−2​F−1\)\(r,r\-2F\-1\)\-redundant wherer\>2​Fr\>2F, and \(ii\) every agenti∈𝒱i\\in\\mathcal\{V\}selectsati∼πθii\(⋅∣st\)a^\{i\}\_\{t\}\\sim\\pi^\{i\}\_\{\\theta^\{i\}\}\(\\cdot\\mid s\_\{t\}\)and updates\{vti\}\\\{v^\{i\}\_\{t\}\\\}and\{λti\}\\\{\\lambda^\{i\}\_\{t\}\\\}via \([13](https://arxiv.org/html/2609.25701#S4.E13)\) and \([15](https://arxiv.org/html/2609.25701#S4.E15)\) of FRAC\-MARL with thresholdτ=r−F\\tau=r\-Fand consensus weights \([16](https://arxiv.org/html/2609.25701#S4.E16)\), under anFF\-total Byzantine edge attack\. Then

limt→∞vti=vθ,limt→∞λti=λθ,for all​i∈𝒱,\\lim\_\{t\\to\\infty\}v\_\{t\}^\{i\}=v\_\{\\theta\},\\qquad\\lim\_\{t\\to\\infty\}\\lambda\_\{t\}^\{i\}=\\lambda\_\{\\theta\},\\quad\\text\{for all \}i\\in\\mathcal\{V\},\(20\)almost surely, whereλθ\\lambda\_\{\\theta\}andvθv\_\{\\theta\}are the unique solutions to

𝐅⊤​𝐃s,aθ​\(𝐑−𝐅​λθ\)\\displaystyle\\mathbf\{F\}^\{\\top\}\\mathbf\{D\}\_\{s,a\}^\{\\theta\}\(\\mathbf\{R\}\-\\mathbf\{F\}\\lambda\_\{\\theta\}\)=0,\\displaystyle=0,\(21a\)𝚽⊤​𝐃sθ​\(𝐑θ\+γ​𝐏θ​𝚽​vθ−𝚽​vθ\)\\displaystyle\\mathbf\{\\Phi\}^\{\\top\}\\mathbf\{D\}\_\{s\}^\{\\theta\}\(\\mathbf\{R\}\_\{\\theta\}\+\\gamma\\mathbf\{P\}\_\{\\theta\}\\mathbf\{\\Phi\}v\_\{\\theta\}\-\\mathbf\{\\Phi\}v\_\{\\theta\}\)=0\.\\displaystyle=0\.\(21b\)

###### Proof\.

By[Lemma3](https://arxiv.org/html/2609.25701#Thmlemma3), all Byzantine\-modified transmissions are removed by FRAC\-MARL before the consensus update\. Therefore, the critic and reward parameter updates are equivalent to those of a standard decentralized actor\-critic algorithm operating over the induced communication graph𝒢tind\\mathcal\{G\}\_\{t\}^\{\\rm ind\}\.

Furthermore, by[Lemma2](https://arxiv.org/html/2609.25701#Thmlemma2), the induced graph is connected and undirected\. This means the corresponding weight matricesWλ,tW\_\{\\lambda,t\}andWv,tW\_\{v,t\}as defined in \([16](https://arxiv.org/html/2609.25701#S4.E16)\) are doubly stochastic by construction\. Because the weight matrices are doubly stochastic with uniformly positive diagonal entries and satisfy the required connectivity condition, we get spectral radiisuptρ⁡\(Wq,t​\(I−1n​𝟏𝟏⊤\)​Wq,t\)<1\\sup\_\{t\}\\rho\\big\(W\_\{q,t\}\(I\-\\tfrac\{1\}\{n\}\\mathbf\{1\}\\mathbf\{1\}^\{\\top\}\)W\_\{q,t\}\\big\)<1forq∈\{v,λ\}q\\in\\\{v,\\lambda\\\}\. Furthermore,𝒢t\\mathcal\{G\}\_\{t\}is independent of the sample path\{\(st′,at′,rt′\+1\)\}t′≥0\\\{\(s\_\{t^\{\\prime\}\},a\_\{t^\{\\prime\}\},r\_\{t^\{\\prime\}\+1\}\)\\\}\_\{t^\{\\prime\}\\geq 0\}and the iterates\{vt′i,λt′i,θt′i\}t′≥0,i∈𝒱\\\{v^\{i\}\_\{t^\{\\prime\}\},\\lambda^\{i\}\_\{t^\{\\prime\}\},\\theta^\{i\}\_\{t^\{\\prime\}\}\\\}\_\{\{t^\{\\prime\}\}\\geq 0,\\,i\\in\\mathcal\{V\}\}\. Then becauseWλ,tW\_\{\\lambda,t\}andWv,tW\_\{v,t\}are determined by𝒢t\\mathcal\{G\}\_\{t\}alone,Wλ,tW\_\{\\lambda,t\}andWv,tW\_\{v,t\}satisfy\[[24](https://arxiv.org/html/2609.25701#bib.bib4), Assumption 4\]\.

We first stack the parameters into

λt=\[\(λt1\)⊤⋯\(λtn\)⊤\]⊤,vt=\[\(vt1\)⊤⋯\(vtn\)⊤\]⊤\.\\displaystyle\\lambda\_\{t\}=\\begin\{bmatrix\}\(\\lambda\_\{t\}^\{1\}\)^\{\\top\}&\\cdots&\(\\lambda\_\{t\}^\{n\}\)^\{\\top\}\\end\{bmatrix\}^\{\\top\},\\ v\_\{t\}=\\begin\{bmatrix\}\(v\_\{t\}^\{1\}\)^\{\\top\}&\\cdots&\(v\_\{t\}^\{n\}\)^\{\\top\}\\end\{bmatrix\}^\{\\top\}\.Then the update laws for both parameters can be compactly written as

λt\+1=\(Wλ,t⊗I\)​\(λt\+αtλ​\(Atλ​λt\+btλ\)\)\\displaystyle\\lambda\_\{t\+1\}=\(W\_\{\\lambda,t\}\\otimes I\)\\left\(\\lambda\_\{t\}\+\\alpha\_\{t\}^\{\\lambda\}\(A\_\{t\}^\{\\lambda\}\\lambda\_\{t\}\+b\_\{t\}^\{\\lambda\}\)\\right\)\(22a\)vt\+1=\(Wv,t⊗I\)​\(vt\+αtv​\(Atv​vt\+btv\)\),\\displaystyle v\_\{t\+1\}=\(W\_\{v,t\}\\otimes I\)\\left\(v\_\{t\}\+\\alpha\_\{t\}^\{v\}\(A\_\{t\}^\{v\}v\_\{t\}\+b\_\{t\}^\{v\}\)\\right\),\(22b\)where

Atλ\\displaystyle A\_\{t\}^\{\\lambda\}=−I⊗f\(st,at\)f\(st,at\)⊤,\\displaystyle=\-I\\otimes f\(s\_\{t\},a\_\{t\}\)f\(s\_\{t\},a\_\{t\}\)^\{\\top\},Atv\\displaystyle A\_\{t\}^\{v\}=I⊗ϕ⁡\(st\)​\(γ​ϕ​\(st\+1\)−ϕ⁡\(st\)\)⊤,\\displaystyle=I\\otimes\\phi\(s\_\{t\}\)\(\\gamma\\phi\(s\_\{t\+1\}\)\-\\phi\(s\_\{t\}\)\)^\{\\top\},and

btλ=\[f⁡\(st,at\)​rt\+11f⁡\(st,at\)​rt\+1n\],btv=\[ϕ⁡\(st\)​rt\+11ϕ⁡\(st\)​rt\+1n\]\.\\displaystyle b\_\{t\}^\{\\lambda\}=\\begin\{bmatrix\}f\(s\_\{t\},a\_\{t\}\)r\_\{t\+1\}^\{1\}\\\\ \\vdots\\\\ f\(s\_\{t\},a\_\{t\}\)r\_\{t\+1\}^\{n\}\\end\{bmatrix\},\\ b\_\{t\}^\{v\}=\\begin\{bmatrix\}\\phi\(s\_\{t\}\)r\_\{t\+1\}^\{1\}\\\\ \\vdots\\\\ \\phi\(s\_\{t\}\)r\_\{t\+1\}^\{n\}\\end\{bmatrix\}\.
The compact form \([22](https://arxiv.org/html/2609.25701#S4.E22)\) is mathematically in the same form as those defined in\[[24](https://arxiv.org/html/2609.25701#bib.bib4), Lemmas 1 and 3\]\. By\[[24](https://arxiv.org/html/2609.25701#bib.bib4), Lemma 1\],supt‖λt‖<∞\\sup\_\{t\}\\\|\\lambda\_\{t\}\\\|<\\inftyandsupt‖vt‖<∞\\sup\_\{t\}\\\|v\_\{t\}\\\|<\\inftyalmost surely, and by\[[24](https://arxiv.org/html/2609.25701#bib.bib4), Lemma 3\],limt→∞‖λt−𝟏⊗λ¯t‖=limt→∞‖vt−𝟏⊗v¯t‖=0\\lim\_\{t\\to\\infty\}\\\|\\lambda\_\{t\}\-\\mathbf\{1\}\\otimes\\bar\{\\lambda\}\_\{t\}\\\|=\\lim\_\{t\\to\\infty\}\\\|v\_\{t\}\-\\mathbf\{1\}\\otimes\\bar\{v\}\_\{t\}\\\|=0almost surely, where

λ¯t=1n​\(𝟏⊤⊗I\)​λt,v¯t=1n​\(𝟏⊤⊗I\)​vt\.\\displaystyle\\bar\{\\lambda\}\_\{t\}=\\frac\{1\}\{n\}\(\\mathbf\{1\}^\{\\top\}\\otimes I\)\\lambda\_\{t\},\\qquad\\bar\{v\}\_\{t\}=\\frac\{1\}\{n\}\(\\mathbf\{1\}^\{\\top\}\\otimes I\)v\_\{t\}\.Premultiplying \([22](https://arxiv.org/html/2609.25701#S4.E22)\) by1n​\(𝟏⊤⊗I\)\\tfrac\{1\}\{n\}\(\\mathbf\{1\}^\{\\top\}\\otimes I\)and using𝟏⊤​Wλ,t=𝟏⊤​Wv,t=𝟏⊤\\mathbf\{1\}^\{\\top\}W\_\{\\lambda,t\}=\\mathbf\{1\}^\{\\top\}W\_\{v,t\}=\\mathbf\{1\}^\{\\top\}yields the closed recursions

λ¯t\+1\\displaystyle\\bar\{\\lambda\}\_\{t\+1\}=λ¯t\+αtλ​\(−f⁡\(st,at\)​f​\(st,at\)⊤​λ¯t\+f⁡\(st,at\)​r¯t\+1\),\\displaystyle=\\bar\{\\lambda\}\_\{t\}\+\\alpha\_\{t\}^\{\\lambda\}\\left\(\-f\(s\_\{t\},a\_\{t\}\)f\(s\_\{t\},a\_\{t\}\)^\{\\top\}\\bar\{\\lambda\}\_\{t\}\+f\(s\_\{t\},a\_\{t\}\)\\bar\{r\}\_\{t\+1\}\\right\),v¯t\+1\\displaystyle\\bar\{v\}\_\{t\+1\}=v¯t\+αtv​\(ϕ⁡\(st\)​\(γ​ϕ​\(st\+1\)−ϕ⁡\(st\)\)⊤​v¯t\+ϕ⁡\(st\)​r¯t\+1\),\\displaystyle=\\bar\{v\}\_\{t\}\+\\alpha\_\{t\}^\{v\}\\left\(\\phi\(s\_\{t\}\)\(\\gamma\\phi\(s\_\{t\+1\}\)\-\\phi\(s\_\{t\}\)\)^\{\\top\}\\bar\{v\}\_\{t\}\+\\phi\(s\_\{t\}\)\\bar\{r\}\_\{t\+1\}\\right\),wherer¯t\+1=1n​∑i∈𝒱rt\+1i\\bar\{r\}\_\{t\+1\}=\\frac\{1\}\{n\}\\sum\_\{i\\in\\mathcal\{V\}\}r\_\{t\+1\}^\{i\}is the team\-averaged realized reward\. By\[[3](https://arxiv.org/html/2609.25701#bib.bib1), Appendix B\.4 Step 2\], under Assumptions[1](https://arxiv.org/html/2609.25701#Thmassumption1),[3](https://arxiv.org/html/2609.25701#Thmassumption3),[4](https://arxiv.org/html/2609.25701#Thmassumption4),[5](https://arxiv.org/html/2609.25701#Thmassumption5), and that since\{\(st,at\)\}\\\{\(s\_\{t\},a\_\{t\}\)\\\}is irreducible and aperiodic with stationary distributiondθ′d\_\{\\theta\}^\{\\prime\}, the asymptotic behaviors ofλ¯t\\bar\{\\lambda\}\_\{t\}andv¯t\\bar\{v\}\_\{t\}are described by

λ˙\\displaystyle\\dot\{\\lambda\}=−𝐅⊤​𝐃s,aθ​𝐅​λ\+𝐅⊤​𝐃s,aθ​𝐑,\\displaystyle=\-\\mathbf\{F\}^\{\\top\}\\mathbf\{D\}\_\{s,a\}^\{\\theta\}\\mathbf\{F\}\\lambda\+\\mathbf\{F\}^\{\\top\}\\mathbf\{D\}\_\{s,a\}^\{\\theta\}\\mathbf\{R\},\(23a\)v˙\\displaystyle\\dot\{v\}=𝚽⊤​𝐃sθ​\(γ​𝐏θ−I\)​𝚽​v\+𝚽⊤​𝐃sθ​𝐑θ\.\\displaystyle=\\mathbf\{\\Phi\}^\{\\top\}\\mathbf\{D\}\_\{s\}^\{\\theta\}\(\\gamma\\mathbf\{P\}\_\{\\theta\}\-I\)\\mathbf\{\\Phi\}v\+\\mathbf\{\\Phi\}^\{\\top\}\\mathbf\{D\}\_\{s\}^\{\\theta\}\\mathbf\{R\}\_\{\\theta\}\.\(23b\)Since−𝐅⊤​𝐃s,aθ​𝐅\-\\mathbf\{F\}^\{\\top\}\\mathbf\{D\}\_\{s,a\}^\{\\theta\}\\mathbf\{F\}and𝚽⊤​𝐃sθ​\(γ​𝐏θ−I\)​𝚽\\mathbf\{\\Phi\}^\{\\top\}\\mathbf\{D\}\_\{s\}^\{\\theta\}\(\\gamma\\mathbf\{P\}\_\{\\theta\}\-I\)\\mathbf\{\\Phi\}are Hurwitz under Assumptions[1](https://arxiv.org/html/2609.25701#Thmassumption1)and[3](https://arxiv.org/html/2609.25701#Thmassumption3), the ODEs \([23](https://arxiv.org/html/2609.25701#S4.E23)\) admit the unique globally asymptotically stable equilibriaλθ\\lambda\_\{\\theta\}andvθv\_\{\\theta\}, respectively \(and thus solutions to \([21](https://arxiv.org/html/2609.25701#S4.E21)\)\)\. Combined withsupt‖λt‖<∞\\sup\_\{t\}\\\|\\lambda\_\{t\}\\\|<\\inftyandsupt‖vt‖<∞\\sup\_\{t\}\\\|v\_\{t\}\\\|<\\infty, this givesλ¯t→λθ\\bar\{\\lambda\}\_\{t\}\\to\\lambda\_\{\\theta\}andv¯t→vθ\\bar\{v\}\_\{t\}\\to v\_\{\\theta\}almost surely\. Therefore, since‖λti−λ¯t‖≤‖λt−𝟏⊗λ¯t‖\\\|\\lambda\_\{t\}^\{i\}\-\\bar\{\\lambda\}\_\{t\}\\\|\\leq\\\|\\lambda\_\{t\}\-\\mathbf\{1\}\\otimes\\bar\{\\lambda\}\_\{t\}\\\|,

‖λti−λθ‖≤‖λti−λ¯t‖\+‖λ¯t−λθ‖→0,\\displaystyle\\\|\\lambda\_\{t\}^\{i\}\-\\lambda\_\{\\theta\}\\\|\\leq\\\|\\lambda\_\{t\}^\{i\}\-\\bar\{\\lambda\}\_\{t\}\\\|\+\\\|\\bar\{\\lambda\}\_\{t\}\-\\lambda\_\{\\theta\}\\\|\\rightarrow 0,and similarly,

‖vti−vθ‖≤‖vti−v¯t‖\+‖v¯t−vθ‖→0\\displaystyle\\\|v\_\{t\}^\{i\}\-v\_\{\\theta\}\\\|\\leq\\\|v\_\{t\}^\{i\}\-\\bar\{v\}\_\{t\}\\\|\+\\\|\\bar\{v\}\_\{t\}\-v\_\{\\theta\}\\\|\\rightarrow 0almost surely\. Thus,limt→∞λti=λθ\\lim\_\{t\\to\\infty\}\\lambda\_\{t\}^\{i\}=\\lambda\_\{\\theta\}andlimt→∞vti=vθ\\lim\_\{t\\to\\infty\}v\_\{t\}^\{i\}=v\_\{\\theta\}, almost surely for everyi∈𝒱i\\in\\mathcal\{V\}, completing the proof\. ∎

[Theorem1](https://arxiv.org/html/2609.25701#Thmtheorem1)depends on Assumptions[1](https://arxiv.org/html/2609.25701#Thmassumption1)\-[5](https://arxiv.org/html/2609.25701#Thmassumption5)\. Except for[Assumption2](https://arxiv.org/html/2609.25701#Thmassumption2), all other assumptions are standard in reinforcement learning and can be applied to a broad class of multi\-agent systems, including multi\-robot task allocation, navigation, and formation control, where agents employ stochastic policies with bounded rewards over a prescribed operating domain\. We discuss the implications of[Assumption2](https://arxiv.org/html/2609.25701#Thmassumption2)in more detail later in this section\.

[Theorem1](https://arxiv.org/html/2609.25701#Thmtheorem1)establishes that, despite Byzantine edge attacks, the proposed algorithm enables all agents to reach consensus on the critic and team\-averaged reward approximations almost surely\. Specifically, the parameter estimates converge toλθ\\lambda\_\{\\theta\}andvθv\_\{\\theta\}, which are, respectively, the least\-squares approximation of the global reward functionr¯\\bar\{r\}and the unique solution to the mean square projected Bellman equation under the linear function approximation\.

Having established convergence of the critic and team\-reward parameter estimates, we next discuss the convergence of the actor in a slower timescale:

###### Theorem 2\.

Let Assumptions[1](https://arxiv.org/html/2609.25701#Thmassumption1)\-[6](https://arxiv.org/html/2609.25701#Thmassumption6)hold\. Suppose that, for everyt∈ℤ≥0t\\in\\mathbb\{Z\}\_\{\\geq 0\}, \(i\) the graph𝒢t=\(𝒱,ℰt\)\\mathcal\{G\}\_\{t\}=\(\\mathcal\{V\},\\mathcal\{E\}\_\{t\}\)is\(r,r−2​F−1\)\(r,r\-2F\-1\)\-redundant wherer\>2​Fr\>2F, and \(ii\) every agenti∈𝒱i\\in\\mathcal\{V\}executes the FRAC\-MARL algorithm with thresholdτ=r−F\\tau=r\-Fand consensus weights \([16](https://arxiv.org/html/2609.25701#S4.E16)\), under anFF\-total Byzantine edge attack\. Then, for every agenti∈𝒱i\\in\\mathcal\{V\}, the policy parameterθti\\theta^\{i\}\_\{t\}converges almost surely to a point in the set of locally asymptotically stable equilibria of the ordinary differential equation

θ˙i=Ψ^Θi​\[𝔼dθ,πθ,P​\[δθ​\(st,at,st\+1\)​∇θi​log⁡πθii​\(ati∣st\)\]\],\\displaystyle\\dot\{\\theta\}^\{i\}=\\hat\{\\Psi\}\_\{\\Theta^\{i\}\}\\left\[\\mathbb\{E\}\_\{d\_\{\\theta\},\\pi\_\{\\theta\},P\}\\left\[\\delta\_\{\\theta\}\(s\_\{t\},a\_\{t\},s\_\{t\+1\}\)\\nabla\_\{\\theta^\{i\}\}\\log\\pi^\{i\}\_\{\\theta^\{i\}\}\(a^\{i\}\_\{t\}\\mid s\_\{t\}\)\\right\]\\right\],\(24\)with

δθ​\(st,at,st\+1\)=r¯​\(st,at,λθ\)\+γ​V​\(st\+1,vθ\)−V⁡\(st,vθ\),\\displaystyle\\delta\_\{\\theta\}\(s\_\{t\},a\_\{t\},s\_\{t\+1\}\)=\\bar\{r\}\(s\_\{t\},a\_\{t\};\\lambda\_\{\\theta\}\)\+\\gamma V\(s\_\{t\+1\};v\_\{\\theta\}\)\-V\(s\_\{t\};v\_\{\\theta\}\),where parametersλθ\\lambda\_\{\\theta\}andvθv\_\{\\theta\}are the globally asymptotically stable equilibria under the global policyπθ\\pi\_\{\\theta\}\.

###### Proof\.

The proof proceeds by combining the convergence result established in[Theorem1](https://arxiv.org/html/2609.25701#Thmtheorem1)with the analysis developed in\[[3](https://arxiv.org/html/2609.25701#bib.bib1), Theorem 4\.10\]and\[[30](https://arxiv.org/html/2609.25701#bib.bib5), Theorem 6\]\. The actor update of each agent can be written as

θt\+1i=ΨΘi​\(θti\+αtθ⋅δti⋅∇θi​log​πθtii​\(ati∣st\)\),\\displaystyle\\theta\_\{t\+1\}^\{i\}=\\Psi\_\{\\Theta^\{i\}\}\\left\(\\theta\_\{t\}^\{i\}\+\\alpha\_\{t\}^\{\\theta\}\\cdot\\delta\_\{t\}^\{i\}\\cdot\\nabla\_\{\\theta^\{i\}\}\\log\\pi^\{i\}\_\{\\theta^\{i\}\_\{t\}\}\(a^\{i\}\_\{t\}\\mid s\_\{t\}\)\\right\),\(25\)where

δti\\displaystyle\\delta\_\{t\}^\{i\}=r¯​\(st,at,λti\)\+γ​V​\(st\+1,vti\)−V⁡\(st,vti\)\.\\displaystyle=\\bar\{r\}\(s\_\{t\},a\_\{t\};\\lambda^\{i\}\_\{t\}\)\+\\gamma V\(s\_\{t\+1\};v\_\{t\}^\{i\}\)\-V\(s\_\{t\};v\_\{t\}^\{i\}\)\.\(26\)
By[Theorem1](https://arxiv.org/html/2609.25701#Thmtheorem1), the critic and reward parameters\(vti,λti\)\(v\_\{t\}^\{i\},\\lambda\_\{t\}^\{i\}\)almost surely converge to\(vθ,λθ\)\(v\_\{\\theta\},\\lambda\_\{\\theta\}\)for every fixedθ∈Θ\\theta\\in\\Theta\. Also, the mapθ↦\(vθ,λθ\)\\theta\\mapsto\(v\_\{\\theta\},\\lambda\_\{\\theta\}\)is continuous onΘ\\Thetaby[Assumption3](https://arxiv.org/html/2609.25701#Thmassumption3)and the continuity ofdθd\_\{\\theta\}inθ\\theta\[[3](https://arxiv.org/html/2609.25701#bib.bib1), Appendix B\.3\]\. Since the actor evolves on a slower timescale by[Assumption5](https://arxiv.org/html/2609.25701#Thmassumption5),θt\\theta\_\{t\}can be held constant when analyzing the faster recursions, and the standard two\-time\-scale argument from\[[3](https://arxiv.org/html/2609.25701#bib.bib1), Theorem 4\.10\]and\[[30](https://arxiv.org/html/2609.25701#bib.bib5), Theorem 6\]applies, yielding

limt→∞‖vti−vθt‖=limt→∞‖λti−λθt‖=0a\.s\.,∀i∈𝒱\.\\displaystyle\\lim\_\{t\\to\\infty\}\\\|v^\{i\}\_\{t\}\-v\_\{\\theta\_\{t\}\}\\\|=\\lim\_\{t\\to\\infty\}\\\|\\lambda^\{i\}\_\{t\}\-\\lambda\_\{\\theta\_\{t\}\}\\\|=0\\quad\\text\{a\.s\.\},\\ \\forall i\\in\\mathcal\{V\}\.\(27\)Hence the biasεti:=δti−δθt​\(st,at,st\+1\)\\varepsilon^\{i\}\_\{t\}:=\\delta^\{i\}\_\{t\}\-\\delta\_\{\\theta\_\{t\}\}\(s\_\{t\},a\_\{t\},s\_\{t\+1\}\)introduced by using\(vti,λti\)\(v^\{i\}\_\{t\},\\lambda^\{i\}\_\{t\}\)in place of\(vθt,λθt\)\(v\_\{\\theta\_\{t\}\},\\lambda\_\{\\theta\_\{t\}\}\)satisfiesεti→0\\varepsilon^\{i\}\_\{t\}\\to 0almost surely by \([27](https://arxiv.org/html/2609.25701#S4.E27)\)\.

Combining this with Assumptions[1](https://arxiv.org/html/2609.25701#Thmassumption1)and[4](https://arxiv.org/html/2609.25701#Thmassumption4), we know thatεti\\varepsilon\_\{t\}^\{i\}in the actor TD errorδti=δθt​\(st,at,st\+1\)\+εti\\delta\_\{t\}^\{i\}=\\delta\_\{\\theta\_\{t\}\}\(s\_\{t\},a\_\{t\},s\_\{t\+1\}\)\+\\varepsilon\_\{t\}^\{i\}is bounded andεti→0\\varepsilon\_\{t\}^\{i\}\\to 0almost surely, and the actor update asymptotically becomes

θt\+1i=ΨΘi​\(θti\+αtθ⋅δθt​\(st,at,st\+1\)​∇θi​log⁡πθtii​\(ati∣st\)\)\.\\displaystyle\\theta\_\{t\+1\}^\{i\}=\\Psi\_\{\\Theta^\{i\}\}\\left\(\\theta\_\{t\}^\{i\}\+\\alpha\_\{t\}^\{\\theta\}\\cdot\\delta\_\{\\theta\_\{t\}\}\(s\_\{t\},a\_\{t\},s\_\{t\+1\}\)\\nabla\_\{\\theta^\{i\}\}\\log\\pi^\{i\}\_\{\\theta^\{i\}\_\{t\}\}\(a^\{i\}\_\{t\}\\mid s\_\{t\}\)\\right\)\.\(28\)
At this point, the actor recursion has the same limiting stochastic approximation form as those analyzed in\[[3](https://arxiv.org/html/2609.25701#bib.bib1), Theorem 4\.10\]and\[[30](https://arxiv.org/html/2609.25701#bib.bib5), Theorem 6\]\. It now remains to verify that the assumptions required for their stochastic approximation analysis hold in our setting\. More specifically, we have

- •supt𝔼⁡\(‖δti​∇θi​log⁡πθtii​\(ati\|st\)‖∣θt′,t′≤t\)<∞\\sup\_\{t\}\\mathbb\{E\}\\big\(\\\|\\delta^\{i\}\_\{t\}\\nabla\_\{\\theta^\{i\}\}\\log\\pi^\{i\}\_\{\\theta^\{i\}\_\{t\}\}\(a^\{i\}\_\{t\}\|s\_\{t\}\)\\\|\\mid\\theta\_\{t^\{\\prime\}\},\\,t^\{\\prime\}\\leq t\\big\)<\\inftyby Assumptions[1](https://arxiv.org/html/2609.25701#Thmassumption1),[3](https://arxiv.org/html/2609.25701#Thmassumption3),[4](https://arxiv.org/html/2609.25701#Thmassumption4)and[6](https://arxiv.org/html/2609.25701#Thmassumption6)with[Theorem1](https://arxiv.org/html/2609.25701#Thmtheorem1);
- •compact and hyper\-rectangular projection setΘi\\Theta^\{i\}by[Assumption6](https://arxiv.org/html/2609.25701#Thmassumption6);
- •∑t=0∞αtθ=∞\\sum\_\{t=0\}^\{\\infty\}\\alpha\_\{t\}^\{\\theta\}=\\infty,∑t=0∞\(αtθ\)2<∞\\sum\_\{t=0\}^\{\\infty\}\(\\alpha\_\{t\}^\{\\theta\}\)^\{2\}<\\infty, andlimt→∞αt\+1θ/αtθ=1\\lim\_\{t\\to\\infty\}\\alpha\_\{t\+1\}^\{\\theta\}/\\alpha\_\{t\}^\{\\theta\}=1by[Assumption5](https://arxiv.org/html/2609.25701#Thmassumption5);
- •biasεti→0\\varepsilon^\{i\}\_\{t\}\\to 0almost surely \(which is established above\);
- •continuous limiting mean updateg⁡\(θti\)=𝔼dθ,πθ,P​\[δθ​\(st,at,st\+1\)​∇θi​log⁡πθtii​\(ati\|st\)\]g\(\\theta^\{i\}\_\{t\}\)=\\mathbb\{E\}\_\{d\_\{\\theta\},\\pi\_\{\\theta\},P\}\\big\[\\delta\_\{\\theta\}\(s\_\{t\},a\_\{t\},s\_\{t\+1\}\)\\nabla\_\{\\theta^\{i\}\}\\log\\pi^\{i\}\_\{\\theta^\{i\}\_\{t\}\}\(a^\{i\}\_\{t\}\|s\_\{t\}\)\\big\]by[Assumption3](https://arxiv.org/html/2609.25701#Thmassumption3);
- •continuity ofθ↦\(vθ,λθ\)\\theta\\mapsto\(v\_\{\\theta\},\\lambda\_\{\\theta\}\)\(which is established above\)\.

Hence, by\[[30](https://arxiv.org/html/2609.25701#bib.bib5), Theorem 6\], the asymptotic behavior of the actor is governed by

θ˙i=Ψ^Θi​\[𝔼dθ,πθ,P​\[δθ​\(st,at,st\+1\)​∇θi​log⁡πθii​\(ati\|st\)\]\],\\displaystyle\\dot\{\\theta\}^\{i\}=\\hat\{\\Psi\}\_\{\\Theta^\{i\}\}\\left\[\\mathbb\{E\}\_\{d\_\{\\theta\},\\pi\_\{\\theta\},P\}\\left\[\\delta\_\{\\theta\}\(s\_\{t\},a\_\{t\},s\_\{t\+1\}\)\\nabla\_\{\\theta^\{i\}\}\\log\\pi^\{i\}\_\{\\theta^\{i\}\}\(a\_\{t\}^\{i\}\|s\_\{t\}\)\\right\]\\right\],andθi\\theta^\{i\}converges almost surely to a point in the set of locally asymptotically stable equilibria of \([24](https://arxiv.org/html/2609.25701#S4.E24)\)\. ∎

Our analysis is in the same spirit as those developed in\[[3](https://arxiv.org/html/2609.25701#bib.bib1),[24](https://arxiv.org/html/2609.25701#bib.bib4),[30](https://arxiv.org/html/2609.25701#bib.bib5)\]\. The convergence guarantees established in[Theorem2](https://arxiv.org/html/2609.25701#Thmtheorem2)show that every agent converges almost surely to an asymptotically stable equilibrium of \([24](https://arxiv.org/html/2609.25701#S4.E24)\), which is the standard convergence guarantee for actor\-critic algorithms even in the single\-agent setting\[[42](https://arxiv.org/html/2609.25701#bib.bib38),[3](https://arxiv.org/html/2609.25701#bib.bib1)\]\. Our result nevertheless represents a notable improvement over existing Byzantine\-resilient MARL methods \(e\.g\.,\[[44](https://arxiv.org/html/2609.25701#bib.bib7),[30](https://arxiv.org/html/2609.25701#bib.bib5),[31](https://arxiv.org/html/2609.25701#bib.bib31)\]\), which guarantee convergence only to*a neighborhood*\.

The key distinction is that FRAC\-MARL completely removes the Byzantine\-induced bias that affects the existing work before it enters the consensus updates\. Specifically, Byzantine attacks introduce bias in two ways: \(i\) corrupted messages that, if accepted, directly perturb the consensus updates, and \(ii\) asymmetric information flow created by filtering, which itself introduces consensus bias\. As established by Lemmas[2](https://arxiv.org/html/2609.25701#Thmlemma2)\-[3](https://arxiv.org/html/2609.25701#Thmlemma3), our method removes such biases through\(r,r′\)\(r,r^\{\\prime\}\)\-redundancy\. Consequently, the critic and reward estimates converge to the same values as in the Byzantine\-free setting\.

We note that such stronger convergence guarantees are obtained under[Assumption2](https://arxiv.org/html/2609.25701#Thmassumption2), where all agents are assumed to follow the prescribed protocol, and Byzantine attacks are introduced only through communication corruption\. This setting constitutes a weaker attack model than the classical Byzantine\-agent model\[[13](https://arxiv.org/html/2609.25701#bib.bib18),[14](https://arxiv.org/html/2609.25701#bib.bib10)\], in which Byzantine agents may*arbitrarily*deviate from the prescribed protocol\.

However, this weakened attack model at the same time allows our method to remain completely independent of how the Byzantine attack unfolds, as long as the number of corrupted communications stays bounded\. This is also an improvement over some of the existing work on Byzantine\-resilient AC\-MARL\[[30](https://arxiv.org/html/2609.25701#bib.bib5),[31](https://arxiv.org/html/2609.25701#bib.bib31)\], as they assume that Byzantine agents’ policies converge to some stationary policy, which ensures stationary MDP from the perspective of non\-Byzantine agents\. This effectively restricts the learning\-dynamics of the Byzantine attackers in the asymptotic sense\. FRAC\-MARL requires no restriction on the temporal or learning\-dynamics behavior of Byzantine attacks\. As a result, as long as the attack occurs at the communication level, our guarantee holds regardless of the behavior of the Byzantine attack\.

## VRedundant Network Graph

Through Theorems[1](https://arxiv.org/html/2609.25701#Thmtheorem1)\-[2](https://arxiv.org/html/2609.25701#Thmtheorem2), we have shown that\(r,r−2​F−1\)\(r,r\-2F\-1\)\-redundancy wherer\>2​Fr\>2Fplays a pivotal role in achieving resilience against theFF\-total Byzantine edge attacks\. In this section, we explore different aspects of the notion of\(r,r′\)\(r,r^\{\\prime\}\)\-redundancy by providing \(i\) a systematic construction of an\(r,r′\)\(r,r^\{\\prime\}\)\-redundant graph \([Proposition1](https://arxiv.org/html/2609.25701#Thmprop1)\) and \(ii\) its computation time \([Proposition2](https://arxiv.org/html/2609.25701#Thmprop2)\)\. As the underlying structural requirements are independent of the learning dynamics, we focus on time\-invariant graphs and drop the argumenttton a graph throughout this discussion\.

We first present a systematic method to construct\(r,r′\)\(r,r^\{\\prime\}\)\-redundant graphs for anyrrandr′r^\{\\prime\}:

###### Proposition 1\.

Let𝒱=\{1,…,n\}\\mathcal\{V\}=\\\{1,\\dots,n\\\}wheren\>rn\>r, and𝒱c=\{1,…,r\}⊂𝒱\\mathcal\{V\}\_\{c\}=\\\{1,\\dots,r\\\}\\subset\\mathcal\{V\}\. Then, a graph𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\)is\(r,r′\)\(r,r^\{\\prime\}\)\-redundant forr\>r′≥0r\>r^\{\\prime\}\\geq 0if \(i\) every node in𝒱c\\mathcal\{V\}\_\{c\}is connected to every other node in𝒱c\\mathcal\{V\}\_\{c\}and \(ii\) every nodei∈𝒱∖𝒱ci\\in\\mathcal\{V\}\\setminus\\mathcal\{V\}\_\{c\}is connected to allrrnodes in𝒱c\\mathcal\{V\}\_\{c\}\.

###### Proof\.

By \(i\) and \(ii\), everyi∈𝒱ci\\in\\mathcal\{V\}\_\{c\}is adjacent to every other node of𝒱\\mathcal\{V\}, so𝒩i=𝒱∖\{i\}\\mathcal\{N\}\_\{i\}=\\mathcal\{V\}\\setminus\\\{i\\\}andℬi=𝒱\\mathcal\{B\}\_\{i\}=\\mathcal\{V\}; and everyi∈𝒱∖𝒱ci\\in\\mathcal\{V\}\\setminus\\mathcal\{V\}\_\{c\}is adjacent to all of𝒱c\\mathcal\{V\}\_\{c\}, so𝒩i⊇𝒱c\\mathcal\{N\}\_\{i\}\\supseteq\\mathcal\{V\}\_\{c\}andℬi⊇𝒱c∪\{i\}\\mathcal\{B\}\_\{i\}\\supseteq\\mathcal\{V\}\_\{c\}\\cup\\\{i\\\}\.

We show\|ℬi∩𝒩j\|≥r\|\\mathcal\{B\}\_\{i\}\\cap\\mathcal\{N\}\_\{j\}\|\\geq rfor everyi≠ji\\neq j, considering four cases\. \(a\) Ifi,j∈𝒱ci,j\\in\\mathcal\{V\}\_\{c\}, thenℬi∩𝒩j=𝒱∖\{j\}\\mathcal\{B\}\_\{i\}\\cap\\mathcal\{N\}\_\{j\}=\\mathcal\{V\}\\setminus\\\{j\\\}, so\|ℬi∩𝒩j\|=n−1≥r\|\\mathcal\{B\}\_\{i\}\\cap\\mathcal\{N\}\_\{j\}\|=n\-1\\geq rsincen\>rn\>r\. \(b\) Ifi∈𝒱ci\\in\\mathcal\{V\}\_\{c\}andj∉𝒱cj\\notin\\mathcal\{V\}\_\{c\}, thenℬi∩𝒩j=𝒩j⊇𝒱c\\mathcal\{B\}\_\{i\}\\cap\\mathcal\{N\}\_\{j\}=\\mathcal\{N\}\_\{j\}\\supseteq\\mathcal\{V\}\_\{c\}, so\|ℬi∩𝒩j\|≥r\|\\mathcal\{B\}\_\{i\}\\cap\\mathcal\{N\}\_\{j\}\|\\geq r\. \(c\) Ifi∉𝒱ci\\notin\\mathcal\{V\}\_\{c\}andj∈𝒱cj\\in\\mathcal\{V\}\_\{c\}, then\|ℬi∩𝒩j\|≥\|\(𝒱c∪\{i\}\)∖\{j\}\|\|\\mathcal\{B\}\_\{i\}\\cap\\mathcal\{N\}\_\{j\}\|\\geq\|\(\\mathcal\{V\}\_\{c\}\\cup\\\{i\\\}\)\\setminus\\\{j\\\}\|\. Sincej∈𝒱cj\\in\\mathcal\{V\}\_\{c\}andi∉𝒱ci\\notin\\mathcal\{V\}\_\{c\}, this set has\(r−1\)\+1=r\(r\-1\)\+1=relements\. \(d\) Ifi,j∉𝒱ci,j\\notin\\mathcal\{V\}\_\{c\}, thenℬi∩𝒩j⊇𝒱c\\mathcal\{B\}\_\{i\}\\cap\\mathcal\{N\}\_\{j\}\\supseteq\\mathcal\{V\}\_\{c\}, so\|ℬi∩𝒩j\|≥r\|\\mathcal\{B\}\_\{i\}\\cap\\mathcal\{N\}\_\{j\}\|\\geq r\.

In every case\|ℬi∩𝒩j\|≥r\|\\mathcal\{B\}\_\{i\}\\cap\\mathcal\{N\}\_\{j\}\|\\geq r, so\(i,j\)∈ℰr\(i,j\)\\in\\mathcal\{E\}^\{r\}for alli≠ji\\neq j\. Hence𝒢\\mathcal\{G\}is\(r,r′\)\(r,r^\{\\prime\}\)\-redundant for everyr′r^\{\\prime\}withr\>r′≥0r\>r^\{\\prime\}\\geq 0\. ∎

While[Proposition1](https://arxiv.org/html/2609.25701#Thmprop1)provides a method to construct\(r,r′\)\(r,r^\{\\prime\}\)\-redundant graphs, the following result establishes that we can verify the redundancy of an arbitrary graph efficiently\.

###### Proposition 2\.

Given anr,r′∈ℤ≥0r,r^\{\\prime\}\\in\\mathbb\{Z\}\_\{\\geq 0\}and a communication graph𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\)with\|𝒱\|=n\|\\mathcal\{V\}\|=n, one can verify whether𝒢\\mathcal\{G\}is\(r,r′\)\(r,r^\{\\prime\}\)\-redundant inO⁡\(n3\)O\(n^\{3\}\)\.

###### Proof\.

LetAAbe an adjacency matrix of𝒢\\mathcal\{G\}\. Then,A¯:=A2\+A\\bar\{A\}:=A^\{2\}\+Awill contain elementsa¯i​j\\bar\{a\}\_\{ij\}that counts the number of shared neighbors between nodesiiandjj\(including nodeiiitself\) i\.e\.,\|ℬi∩𝒩j\|\|\\mathcal\{B\}\_\{i\}\\cap\\mathcal\{N\}\_\{j\}\|\. ComputingA¯\\bar\{A\}using standard matrix multiplication requiresO⁡\(n3\)O\(n^\{3\}\)operations\[[45](https://arxiv.org/html/2609.25701#bib.bib27), Sec\. 4\], and checking whethera¯i​j≥r\\bar\{a\}\_\{ij\}\\geq rora¯i​j≤r′\\bar\{a\}\_\{ij\}\\leq r^\{\\prime\}adds at mostO⁡\(n2\)O\(n^\{2\}\)operations\. Next, to verify that therr\-2\-hop graph𝒢r=\(𝒱,ℰr\)\\mathcal\{G\}^\{r\}=\(\\mathcal\{V\},\\mathcal\{E\}^\{r\}\)of𝒢\\mathcal\{G\}is connected, one can perform a Breadth\-First Search \(BFS\), which requiresO⁡\(n\+mr\)O\(n\+m\_\{r\}\)time, wheremr=\|ℰr\|m\_\{r\}=\|\\mathcal\{E\}^\{r\}\|\[[45](https://arxiv.org/html/2609.25701#bib.bib27), Sec\. 22\.2\]\. Therefore, the total required computation isO⁡\(n3\+mr\)O\(n^\{3\}\+m\_\{r\}\)\. Sincemr≤\(n2\)=O⁡\(n2\)m\_\{r\}\\leq\\binom\{n\}\{2\}=O\(n^\{2\}\),O⁡\(n3\+mr\)=O⁡\(n3\)O\(n^\{3\}\+m\_\{r\}\)=O\(n^\{3\}\)\. ∎

[Proposition2](https://arxiv.org/html/2609.25701#Thmprop2)establishes that\(r,r′\)\(r,r^\{\\prime\}\)\-redundancy can be verified efficiently\. Compare this withrr\-robustness\[[14](https://arxiv.org/html/2609.25701#bib.bib10)\], whose definition is given below:

###### Definition 6\(𝐫\\mathbf\{r\}\-robustness\[[14](https://arxiv.org/html/2609.25701#bib.bib10)\]\)\.

A graph𝒢=\(𝒱,ℰ\)\\mathcal\{G\}=\(\\mathcal\{V\},\\mathcal\{E\}\)is𝐫\\mathbf\{r\}\-robustif for every pair of nonempty, disjoint subsets𝒫1,𝒫2⊂𝒱\\mathcal\{P\}\_\{1\},\\mathcal\{P\}\_\{2\}\\subset\\mathcal\{V\}, at least one of the subsets contains a node with at leastrrneighbors outside the subset\. That is, there exists a nodei∈𝒫ki\\in\\mathcal\{P\}\_\{k\}such that\|𝒩i∖𝒫k\|≥r\|\\mathcal\{N\}\_\{i\}\\setminus\\mathcal\{P\}\_\{k\}\|\\geq rfor somek∈\{1,2\}k\\in\\\{1,2\\\}\.

While\(2​F\+1\)\(2F\+1\)\-robustness provides a sufficient condition for many Byzantine\-resilient AC\-MARL frameworks\[[30](https://arxiv.org/html/2609.25701#bib.bib5),[27](https://arxiv.org/html/2609.25701#bib.bib21),[29](https://arxiv.org/html/2609.25701#bib.bib12),[31](https://arxiv.org/html/2609.25701#bib.bib31)\], determining whether a graph satisfies this property is coNP\-complete\[[33](https://arxiv.org/html/2609.25701#bib.bib11)\]\. Consequently, there is no known efficient algorithm for verifyingrr\-robustness in general, making robustness\-based design impractical for large\-scale and dynamic networks\. In contrast,\(r,r′\)\(r,r^\{\\prime\}\)\-redundancy offers a tractable alternative, making our method more suitable\.

###### Lemma 4\.

Let𝒢\\mathcal\{G\}be an\(r,r′\)\(r,r^\{\\prime\}\)\-redundant graph constructed according to[Proposition1](https://arxiv.org/html/2609.25701#Thmprop1)withn≥2​r−1n\\geq 2r\-1\. Then,𝒢\\mathcal\{G\}isrr\-robust\.

###### Proof\.

By[Proposition1](https://arxiv.org/html/2609.25701#Thmprop1), eachi∈𝒱ci\\in\\mathcal\{V\}\_\{c\}satisfies𝒩i=𝒱∖\{i\}\\mathcal\{N\}\_\{i\}=\\mathcal\{V\}\\setminus\\\{i\\\}, and eachi∈𝒱∖𝒱ci\\in\\mathcal\{V\}\\setminus\\mathcal\{V\}\_\{c\}satisfies𝒩i⊇𝒱c\\mathcal\{N\}\_\{i\}\\supseteq\\mathcal\{V\}\_\{c\}\. Let𝒫1,𝒫2⊂𝒱\\mathcal\{P\}\_\{1\},\\mathcal\{P\}\_\{2\}\\subset\\mathcal\{V\}be nonempty and disjoint; since\|𝒫1\|\+\|𝒫2\|≤n\|\\mathcal\{P\}\_\{1\}\|\+\|\\mathcal\{P\}\_\{2\}\|\\leq n, assume without loss of generality\|𝒫1\|≤⌊n/2⌋\|\\mathcal\{P\}\_\{1\}\|\\leq\\lfloor n/2\\rfloor\. If𝒫1∩𝒱c≠∅\\mathcal\{P\}\_\{1\}\\cap\\mathcal\{V\}\_\{c\}\\neq\\emptyset, anyi∈𝒫1∩𝒱ci\\in\\mathcal\{P\}\_\{1\}\\cap\\mathcal\{V\}\_\{c\}gives\|𝒩i∖𝒫1\|=n−\|𝒫1\|≥⌈n/2⌉≥r\|\\mathcal\{N\}\_\{i\}\\setminus\\mathcal\{P\}\_\{1\}\|=n\-\|\\mathcal\{P\}\_\{1\}\|\\geq\\lceil n/2\\rceil\\geq r\. Otherwise𝒱c∩𝒫1=∅\\mathcal\{V\}\_\{c\}\\cap\\mathcal\{P\}\_\{1\}=\\emptyset, so anyi∈𝒫1i\\in\\mathcal\{P\}\_\{1\}gives𝒩i∖𝒫1⊇𝒱c\\mathcal\{N\}\_\{i\}\\setminus\\mathcal\{P\}\_\{1\}\\supseteq\\mathcal\{V\}\_\{c\}and thus\|𝒩i∖𝒫1\|≥r\|\\mathcal\{N\}\_\{i\}\\setminus\\mathcal\{P\}\_\{1\}\|\\geq r\. In either case𝒫1\\mathcal\{P\}\_\{1\}contains a nodeiisuch that\|𝒩i∖𝒫1\|≥r\|\\mathcal\{N\}\_\{i\}\\setminus\\mathcal\{P\}\_\{1\}\|\\geq r, completing the proof\. ∎

[Lemma4](https://arxiv.org/html/2609.25701#Thmlemma4)connects\(r,r′\)\(r,r^\{\\prime\}\)\-redundancy of graphs constructed via[Proposition1](https://arxiv.org/html/2609.25701#Thmprop1)to the notion ofrr\-robustness\. Note that this result does not establish a general characterization between the two properties; it applies only to the specific class of graphs\. Establishing a full characterization of the relationship between these two topological conditions remains future work\.

## VISimulation Results

We evaluate the proposed algorithm on a cooperative formation task built on the Multi\-Particle Environments 2 \(MPE2\)\[[10](https://arxiv.org/html/2609.25701#bib.bib43)\]\. We consider a team ofn=10n=10agents that must arrange themselves into a circular formation of radiusRcircle=0\.5R\_\{\\rm circle\}=0\.5around a stationary landmark located atplm∈ℝ2p^\{\\mathrm\{lm\}\}\\in\\mathbb\{R\}^\{2\}\. Each agent estimates its actor, critic, and team\-average reward functions using neural networks with a single hidden layer of 30 units and Leaky ReLU activation functions with negative slope0\.10\.1\.

State Space:At each timett, agenti∈𝒱=\{1,…,10\}i\\in\\mathcal\{V\}=\\\{1,\\ldots,10\\\}observes the state

st=\[\(ot1\)⊤,\(ot2\)⊤,…,\(otn\)⊤\]⊤∈ℝ6​n,\\displaystyle s\_\{t\}=\\big\[\(o\_\{t\}^\{1\}\)^\{\\top\},\(o\_\{t\}^\{2\}\)^\{\\top\},\\dots,\(o\_\{t\}^\{n\}\)^\{\\top\}\\big\]^\{\\top\}\\in\\mathbb\{R\}^\{6n\},\(29\)whereoti=\[\(p˙ti\)⊤,\(pti\)⊤,\(pti,rel\)⊤\]⊤o\_\{t\}^\{i\}=\\big\[\(\\dot\{p\}\_\{t\}^\{i\}\)^\{\\top\},\\;\(p\_\{t\}^\{i\}\)^\{\\top\},\(p\_\{t\}^\{i,\{\\rm rel\}\}\)^\{\\top\}\\big\]^\{\\top\}contains the agentii’s velocityp˙ti\\dot\{p\}\_\{t\}^\{i\}, positionpti∈ℝ2p\_\{t\}^\{i\}\\in\\mathbb\{R\}^\{2\}, and its relative position to the landmark,pti,rel=pti−plmp\_\{t\}^\{i,\{\\rm rel\}\}=p\_\{t\}^\{i\}\-p^\{\\mathrm\{lm\}\}\.

Action Space:Each agent selects a discrete actionati∈𝒜i=\{stay,left,right,down,up\}a\_\{t\}^\{i\}\\in\\mathcal\{A\}^\{i\}=\\\{\{\\rm stay\},\{\\rm left\},\{\\rm right\},\{\\rm down\},\{\\rm up\}\\\}, corresponding to stay still or a unit force applied along one of the four cardinal directions\.

Reward Space:Each agentiireceives a rewardrt\+1i=−clip⁡\(‖pti−gti‖2,0,2\)r\_\{t\+1\}^\{i\}=\-\\operatorname\{clip\}\(\\\|p\_\{t\}^\{i\}\-g\_\{t\}^\{i\}\\\|\_\{2\},0,2\)based on its distance to an assigned formation goalgtig\_\{t\}^\{i\}\. At each time step,nngoal positions\{gti\}i∈𝒱\\\{g\_\{t\}^\{i\}\\\}\_\{i\\in\\mathcal\{V\}\}are evenly spaced on a circle of radiusRcircleR\_\{\\rm circle\}around the landmark, with the orientation determined by the current agents’ configurations, and are assigned to the agents by minimizing the total assignment distance using the Hungarian algorithm\.

Agent Dynamics:We use the default dynamics defined in MPE2, where each agentiiis modeled as a point mass with damped double\-integrator dynamics:

pt\+1i\\displaystyle p\_\{t\+1\}^\{i\}=pti\+p˙ti​Δ​t,\\displaystyle=p\_\{t\}^\{i\}\+\\dot\{p\}\_\{t\}^\{i\}\\,\\Delta t,\(30\)p˙t\+1i\\displaystyle\\dot\{p\}\_\{t\+1\}^\{i\}=\(1−β\)​p˙ti\+Δ​tm​uti,\\displaystyle=\(1\-\\beta\)\\,\\dot\{p\}\_\{t\}^\{i\}\+\\frac\{\\Delta t\}\{m\}\\,u\_\{t\}^\{i\},\(31\)whereuti∈\{\(0,0\),\(±1,0\),\(0,±1\)\}u\_\{t\}^\{i\}\\in\\\{\(0,0\),\(\\pm 1,0\),\(0,\\pm 1\)\\\}is the control input selected byatia\_\{t\}^\{i\}, with sampling timeΔ​t=0\.1\\Delta t=0\.1, damping coefficientβ=0\.25\\beta=0\.25, and massm=1m=1\.

Training:We compare our method against four baselines:

- •Normal:the vanilla decentralized AC\-MARL from\[[3](https://arxiv.org/html/2609.25701#bib.bib1), Alg\. 2\]without attacks;
- •Naive:the vanilla decentralized AC\-MARL from\[[3](https://arxiv.org/html/2609.25701#bib.bib1), Alg\. 2\]underFFByzantine edge attacks;
- •Projection:the resilient AC\-MARL method from\[[30](https://arxiv.org/html/2609.25701#bib.bib5), Alg\. 2\]that uses a projection\-based defense mechanism\. Following the authors’ implementation, trimmed\-mean aggregation is applied to the hidden\-layer parameters before the projection\-based updates; and
- •Trimmed\-Mean:the resilient AC\-MARL from\[[44](https://arxiv.org/html/2609.25701#bib.bib7), Alg\. 1\]that performs an element\-wise trimmed\-mean operation\.

We simulate Byzantine edge attacks by randomly selectingFFedges incident to agent11, replacing the transmitted messages with parameter tuples obtained by adding a positive offset to each parameter tensor\. The offset scaled according to the mean absolute magnitude of the corresponding tensor\. Then, it is upper bounded by 1 to ensure numerical stability\.

We train all methods for1000010000episodes using five different random seeds, with each episode consisting of3535steps, using 10 critic and reward\-function updates per actor update\. The learning rates areαtv=αtλ=0\.01\\alpha\_\{t\}^\{v\}=\\alpha\_\{t\}^\{\\lambda\}=0\.01andαtθ=0\.001\\alpha\_\{t\}^\{\\theta\}=0\.001\. Updates are performed in batches every 20 episodes\. We set the discount factor toγ=0\.9\\gamma=0\.9and each agent selects a random action with probabilityμ=0\.1\\mu=0\.1\.

![Refer to caption](https://arxiv.org/html/2609.25701v1/figures/bounded.png)Fig\. 3:Reward curves underFF\-total Byzantine edge attack, with \(a\)F=1F=1and \(b\)F=2F=2\. Our method attains the same reward level as the attack\-free Normal baseline, whereas the other methods converge to suboptimal policies with visibly lower rewards\.We considerF=1F=1andF=2F=2withr=2​F\+1r=2F\+1\. Every2020episodes we generate a\(2​F\+1,0\)\(2F\+1,0\)\-redundant network using the construction mechanism in[Proposition1](https://arxiv.org/html/2609.25701#Thmprop1), while randomly permuting the agent indices to emulate a time\-varying communication topology\. By construction, the resulting networks satisfy the topological conditions required by Theorems[1](https://arxiv.org/html/2609.25701#Thmtheorem1)\-[2](https://arxiv.org/html/2609.25701#Thmtheorem2)\. By[Lemma4](https://arxiv.org/html/2609.25701#Thmlemma4), the network is also\(2​F\+1\)\(2F\+1\)\-robust for all time, satisfying the sufficient topological condition required for the convergence of the projection\-based method in\[[30](https://arxiv.org/html/2609.25701#bib.bib5)\]\.

[Figure3](https://arxiv.org/html/2609.25701#S6.F3)reports the reward curves underF=1F=1andF=2F=2Byzantine edge attacks\. Our method matches the attack\-free Normal baseline in both settings\. This is consistent with Theorems[1](https://arxiv.org/html/2609.25701#Thmtheorem1)\-[2](https://arxiv.org/html/2609.25701#Thmtheorem2), which guarantee convergence to equilibria of the limiting ODEs rather than a neighborhood of them\. In contrast, the other methods converge to lower reward levels, reflecting the residual errors introduced by their consensus steps underFF\-total Byzantine edge attacks\.

## VIIConclusion

We study resilient actor\-critic multi\-agent reinforcement learning under Byzantine edge attacks\. Our method exploits the redundancy of two\-hop communication to decide which messages to trust and filter\. We introduce a novel topological condition,\(r,r′\)\(r,r^\{\\prime\}\)\-redundancy, to provide the conditions under which the policy parameters converge almost surely to a locally asymptotically stable equilibrium of the attack\-free limiting ODE\. We validate our method on a multi\-agent formation control task\.

## References

## References

- \[1\]R\. S\. Sutton and A\. Barto\(1998\)Reinforcement learning: an introduction\.Vol\.1,MIT press Cambridge\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p1.1)\.
- \[2\]K\. Zhang, Z\. Yang, and T\. Başar\(2021\)Multi\-agent reinforcement learning: a selective overview of theories and algorithms\.Handbook of reinforcement learning and control,pp\. 321–384\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p1.1)\.
- \[3\]K\. Zhang, Z\. Yang, H\. Liu, T\. Zhang, and T\. Basar\(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:[§I](https://arxiv.org/html/2609.25701#S1.p1.1),[§I](https://arxiv.org/html/2609.25701#S1.p2.1),[§I](https://arxiv.org/html/2609.25701#S1.p3.1),[§III\-B](https://arxiv.org/html/2609.25701#S3.SS2.p1.1),[§III\-B](https://arxiv.org/html/2609.25701#S3.SS2.p3.1),[§IV\-A](https://arxiv.org/html/2609.25701#S4.SS1.p1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p12.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p17.3.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p21.1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p22.1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p24.1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p26.1),[1st item](https://arxiv.org/html/2609.25701#S6.I1.i1.p1.1),[2nd item](https://arxiv.org/html/2609.25701#S6.I1.i2.p1.1)\.
- \[4\]Y\. Lin, G\. Qu, L\. Huang, and A\. Wierman\(2021\)Multi\-agent reinforcement learning in stochastic networked systems\.InAdvances in Neural Information Processing Systems,Vol\.34,pp\. 7825–7837\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p1.1)\.
- \[5\]G\. Qu, A\. Wierman, and N\. Li\(2020\)Scalable reinforcement learning of localized policies for multi\-agent networked systems\.InProceedings of the 2nd Conference on Learning for Dynamics and Control,Proceedings of Machine Learning Research, Vol\.120,pp\. 256–266\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p1.1)\.
- \[6\]S\. Zeng, T\. Chen, A\. Garcia, and M\. Hong\(2022\)Learning to coordinate in multi\-agent systems: a coordinated actor\-critic algorithm and finite\-time guarantees\.InProceedings of The 4th Annual Learning for Dynamics and Control Conference,Proceedings of Machine Learning Research, Vol\.168,pp\. 278–290\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p2.1),[§I](https://arxiv.org/html/2609.25701#S1.p3.1)\.
- \[7\]P\. Dai, W\. Yu, H\. Wang, and S\. Baldi\(2023\)Distributed actor–critic algorithms for multiagent reinforcement learning over directed graphs\.IEEE Transactions on Neural Networks and Learning Systems34\(10\),pp\. 7210–7221\.External Links:[Document](https://dx.doi.org/10.1109/TNNLS.2021.3139138)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p2.1),[§I](https://arxiv.org/html/2609.25701#S1.p3.1)\.
- \[8\]P\. Dai, Y\. Mo, W\. Yu, and W\. Ren\(2025\)Distributed neural policy gradient algorithm for global convergence of networked multiagent reinforcement learning\.IEEE Transactions on Automatic Control70\(11\),pp\. 7109–7124\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2025.3570065)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p2.1),[§I](https://arxiv.org/html/2609.25701#S1.p3.1)\.
- \[9\]S\. Kar, J\. M\. F\. Moura, and H\. V\. Poor\(2013\)𝒬𝒟\{\{\\cal Q\}\{\\cal D\}\}\-Learning: a collaborative distributed strategy for multi\-agent reinforcement learning throughConsensus\+Innovations\{\\rm Consensus\}\+\{\\rm Innovations\}\.IEEE Transactions on Signal Processing61\(7\),pp\. 1848–1862\.External Links:[Document](https://dx.doi.org/10.1109/TSP.2013.2241057)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p2.1),[§I](https://arxiv.org/html/2609.25701#S1.p6.1)\.
- \[10\]R\. Lowe, Y\. Wu, A\. Tamar, J\. Harb, P\. Abbeel, and I\. Mordatch\(2017\)Multi\-agent actor\-critic for mixed cooperative\-competitive environments\.Neural Information Processing Systems \(NIPS\)\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p2.1),[§VI](https://arxiv.org/html/2609.25701#S6.p1.1)\.
- \[11\]J\. Foerster, G\. Farquhar, T\. Afouras, N\. Nardelli, and S\. Whiteson\(2018\)Counterfactual multi\-agent policy gradients\.InProceedings of the AAAI conference on artificial intelligence,Vol\.32\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p2.1)\.
- \[12\]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:[§I](https://arxiv.org/html/2609.25701#S1.p2.1)\.
- \[13\]L\. Su and N\. H\. Vaidya\(2021\)Byzantine\-resilient multiagent optimization\.IEEE Transactions on Automatic Control66\(5\),pp\. 2227–2233\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2020.3008139)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p4.1),[§I](https://arxiv.org/html/2609.25701#S1.p9.1),[§III\-C](https://arxiv.org/html/2609.25701#S3.SS3.p1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p28.1)\.
- \[14\]H\. J\. LeBlanc, H\. Zhang, X\. Koutsoukos, and S\. Sundaram\(2013\)Resilient asymptotic consensus in robust networks\.IEEE Journal on Selected Areas in Communications31\(4\),pp\. 766–781\.External Links:[Document](https://dx.doi.org/10.1109/JSAC.2013.130413)Cited by:[3rd item](https://arxiv.org/html/2609.25701#S1.I1.i3.p1.1),[§I](https://arxiv.org/html/2609.25701#S1.p4.1),[§I](https://arxiv.org/html/2609.25701#S1.p8.1),[§III\-C](https://arxiv.org/html/2609.25701#S3.SS3.p1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p28.1),[§V](https://arxiv.org/html/2609.25701#S5.p8.1),[Definition 6](https://arxiv.org/html/2609.25701#Thmdefinition6)\.
- \[15\]L\. Yuan and H\. Ishii\(2025\)Resilient average consensus with adversaries via distributed detection and recovery\.IEEE Transactions on Automatic Control70\(1\),pp\. 415–430\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2024.3426387)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p4.1)\.
- \[16\]H\. Lee and D\. Panagou\(2025\)Distributed resilience\-aware control in multi\-robot networks\.In2025 IEEE 64th Conference on Decision and Control \(CDC\),Vol\.,pp\. 3868–3875\.External Links:[Document](https://dx.doi.org/10.1109/CDC57313.2025.11312021)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p4.1)\.
- \[17\]S\. Sundaram and B\. Gharesifard\(2019\)Distributed optimization under adversarial nodes\.IEEE Transactions on Automatic Control64\(3\),pp\. 1063–1076\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2018.2836919)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p4.1),[§I](https://arxiv.org/html/2609.25701#S1.p9.1)\.
- \[18\]M\. Yemini, A\. Nedić, A\. J\. Goldsmith, and S\. Gil\(2025\)Resilient distributed optimization for multiagent cyberphysical systems\.IEEE Transactions on Automatic Control70\(6\),pp\. 3952–3967\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2025.3532791)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p4.1)\.
- \[19\]C\. Fang, Z\. Yang, and W\. U\. Bajwa\(2022\)BRIDGE: byzantine\-resilient decentralized gradient descent\.IEEE Transactions on Signal and Information Processing over Networks8\(\),pp\. 610–626\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p4.1),[§I](https://arxiv.org/html/2609.25701#S1.p9.1)\.
- \[20\]Y\. Chen, L\. Su, and J\. Xu\(2017\)Distributed statistical machine learning in adversarial settings: byzantine gradient descent\.1\(2\)\.External Links:[Document](https://dx.doi.org/10.1145/3154503)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p4.1)\.
- \[21\]P\. Blanchard, E\. M\. El Mhamdi, R\. Guerraoui, and J\. Stainer\(2017\)Machine learning with adversaries: byzantine tolerant gradient descent\.InAdvances in Neural Information Processing Systems,Vol\.30,pp\.\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p4.1)\.
- \[22\]H\. Lee, V\. Yun, H\. Oh, D\. Panagou, and S\. P\. Karimireddy\(2026\)Robust multi\-agent llms under byzantine faults\.arXiv preprint arXiv:2605\.09076\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p4.1)\.
- \[23\]H\. Luo, G\. Sun, Y\. Liu, D\. Zhao, D\. Niyato, H\. Yu, and S\. Dustdar\(2025\)A weighted byzantine fault tolerance consensus driven trusted multiple large language models network\.IEEE Transactions on Cognitive Communications and Networking\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p4.1)\.
- \[24\]M\. Figura, K\. C\. Kosaraju, and V\. Gupta\(2021\)Adversarial attacks in consensus\-based multi\-agent reinforcement learning\.In2021 American Control Conference \(ACC\),Vol\.,pp\. 3050–3055\.External Links:[Document](https://dx.doi.org/10.23919/ACC50511.2021.9483080)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p5.1),[§III\-A](https://arxiv.org/html/2609.25701#S3.SS1.p3.2),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p15.1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p17.1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p26.1)\.
- \[25\]Y\. Xie, S\. Mou, and S\. Sundaram\(2021\)Towards resilience for multi\-agent qd\-learning\.In2021 60th IEEE Conference on Decision and Control \(CDC\),Vol\.,pp\. 1250–1255\.External Links:[Document](https://dx.doi.org/10.1109/CDC45484.2021.9683145)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p5.1)\.
- \[26\]Hairi, M\. Fang, Z\. Zhang, A\. Velasquez, and J\. Liu\(2024\)On the hardness of decentralized multi\-agent policy evaluation under byzantine attacks\.In2024 International Symposium on Modeling and Optimization in Mobile, Ad Hoc, and Wireless Networks \(WiOpt\),Vol\.,pp\. 257–264\.External Links:[Document](https://dx.doi.org/)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p5.1),[§III\-C](https://arxiv.org/html/2609.25701#S3.SS3.p1.1)\.
- \[27\]Y\. Xie, S\. Mou, and S\. Sundaram\(2023\)Communication\-efficient and resilient distributed q\-learning\.IEEE Transactions on Neural Networks and Learning Systems35\(3\),pp\. 3351–3364\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p6.1),[§V](https://arxiv.org/html/2609.25701#S5.p9.1)\.
- \[28\]Z\. Wu, H\. Shen, T\. Chen, and Q\. Ling\(2021\)Byzantine\-resilient decentralized policy evaluation with linear function approximation\.IEEE Transactions on Signal Processing69\(\),pp\. 3839–3853\.External Links:[Document](https://dx.doi.org/10.1109/TSP.2021.3090952)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p6.1),[§III\-C](https://arxiv.org/html/2609.25701#S3.SS3.p1.1)\.
- \[29\]J\. Yao and X\. Gong\(2024\)Communication\-efficient and resilient distributed deep reinforcement learning for multi\-agent systems\.In2024 IEEE International Conference on Unmanned Systems \(ICUS\),Vol\.,pp\. 1521–1526\.External Links:[Document](https://dx.doi.org/10.1109/ICUS61736.2024.10839941)Cited by:[3rd item](https://arxiv.org/html/2609.25701#S1.I1.i3.p1.1),[§I](https://arxiv.org/html/2609.25701#S1.p6.1),[§I](https://arxiv.org/html/2609.25701#S1.p8.1),[§V](https://arxiv.org/html/2609.25701#S5.p9.1)\.
- \[30\]L\. Ye, M\. Figura, Y\. Lin, M\. Pal, P\. Das, J\. Liu, and V\. Gupta\(2024\)Resilient multiagent reinforcement learning with function approximation\.IEEE Transactions on Automatic Control69\(12\),pp\. 8497–8512\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2024.3409676)Cited by:[3rd item](https://arxiv.org/html/2609.25701#S1.I1.i3.p1.1),[§I](https://arxiv.org/html/2609.25701#S1.p6.1),[§I](https://arxiv.org/html/2609.25701#S1.p7.1),[§I](https://arxiv.org/html/2609.25701#S1.p8.1),[§III\-A](https://arxiv.org/html/2609.25701#S3.SS1.p3.1),[§III\-A](https://arxiv.org/html/2609.25701#S3.SS1.p3.2),[§III\-C](https://arxiv.org/html/2609.25701#S3.SS3.p1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p12.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p21.1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p22.1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p24.1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p25.1.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p26.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p29.1),[§V](https://arxiv.org/html/2609.25701#S5.p9.1),[3rd item](https://arxiv.org/html/2609.25701#S6.I1.i3.p1.1),[§VI](https://arxiv.org/html/2609.25701#S6.p8.1)\.
- \[31\]X\. Gong, Y\. Lu, J\. Gui, and T\. Yu\(2026\)Resilient fully\-distributed reinforcement learning for uav swarms against general byzantine attacks\.Journal of the Franklin Institute363\(12\),pp\. 108732\.External Links:ISSN 0016\-0032,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.jfranklin.2026.108732)Cited by:[3rd item](https://arxiv.org/html/2609.25701#S1.I1.i3.p1.1),[§I](https://arxiv.org/html/2609.25701#S1.p6.1),[§I](https://arxiv.org/html/2609.25701#S1.p7.1),[§I](https://arxiv.org/html/2609.25701#S1.p8.1),[§III\-C](https://arxiv.org/html/2609.25701#S3.SS3.p1.1),[§III\-C](https://arxiv.org/html/2609.25701#S3.SS3.p2.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p26.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p29.1),[§V](https://arxiv.org/html/2609.25701#S5.p9.1)\.
- \[32\]J\. K\. Medhi, R\. Liu, Q\. Wang, and X\. Chen\(2023\)Robust multiagent reinforcement learning for uav systems: countering byzantine attacks\.Information14\(11\)\.External Links:ISSN 2078\-2489Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p6.1)\.
- \[33\]H\. Zhang, E\. Fata, and S\. Sundaram\(2015\)A notion of robustness in complex networks\.IEEE Transactions on Control of Network Systems2\(3\),pp\. 310–320\.External Links:[Document](https://dx.doi.org/10.1109/TCNS.2015.2413551)Cited by:[3rd item](https://arxiv.org/html/2609.25701#S1.I1.i3.p1.1),[§I](https://arxiv.org/html/2609.25701#S1.p8.1),[§V](https://arxiv.org/html/2609.25701#S5.p9.1)\.
- \[34\]Y\. Lin, S\. Gade, R\. Sandhu, and J\. Liu\(2020\)Toward resilient multi\-agent actor\-critic algorithms for distributed reinforcement learning\.In2020 American Control Conference \(ACC\),Vol\.,pp\. 3953–3958\.External Links:[Document](https://dx.doi.org/10.23919/ACC45564.2020.9147381)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p8.1)\.
- \[35\]Q\. Lin and Q\. Ling\(2024\)Robust reward\-free actor–critic for cooperative multiagent reinforcement learning\.IEEE Transactions on Neural Networks and Learning Systems35\(12\),pp\. 17318–17329\.External Links:[Document](https://dx.doi.org/10.1109/TNNLS.2023.3302131)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p8.1)\.
- \[36\]M\. Fang, X\. Wang, and N\. Z\. Gong\(2025\)Provably robust federated reinforcement learning\.InProceedings of the ACM on Web Conference 2025,WWW ’25,New York, NY, USA,pp\. 896–909\.External Links:ISBN 9798400712746,[Document](https://dx.doi.org/10.1145/3696410.3714728)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p8.1)\.
- \[37\]S\. Guo, T\. Zhang, H\. Yu, X\. Xie, L\. Ma, T\. Xiang, and Y\. Liu\(2022\)Byzantine\-resilient decentralized stochastic gradient descent\.IEEE Transactions on Circuits and Systems for Video Technology32\(6\),pp\. 4096–4106\.External Links:[Document](https://dx.doi.org/10.1109/TCSVT.2021.3116976)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p9.1)\.
- \[38\]Z\. Wu, T\. Chen, and Q\. Ling\(2023\)Byzantine\-resilient decentralized stochastic optimization with robust aggregation rules\.IEEE Transactions on Signal Processing71\(\),pp\. 3179–3195\.External Links:[Document](https://dx.doi.org/10.1109/TSP.2023.3300629)Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p9.1)\.
- \[39\]E\. M\. El\-Mhamdi, S\. Farhadkhani, R\. Guerraoui, A\. Guirguis, L\. Hoang, and S\. Rouault\(2021\)Collaborative learning in the jungle \(decentralized, byzantine, heterogeneous, asynchronous and nonconvex learning\)\.Advances in neural information processing systems34,pp\. 25044–25057\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p9.1)\.
- \[40\]L\. He, S\. P\. Karimireddy, and M\. Jaggi\(2022\)Byzantine\-robust decentralized learning via clippedgossip\.arXiv preprint arXiv:2202\.01545\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p9.1)\.
- \[41\]H\. Lee and D\. Panagou\(2026\)Fully byzantine\-resilient distributed multi\-agent q\-learning\.arXiv preprint arXiv:2604\.02791\.Cited by:[§I](https://arxiv.org/html/2609.25701#S1.p10.1)\.
- \[42\]S\. Bhatnagar, R\. S\. Sutton, M\. Ghavamzadeh, and M\. Lee\(2009\)Natural actor–critic algorithms\.Automatica45\(11\),pp\. 2471–2482\.External Links:ISSN 0005\-1098,[Document](https://dx.doi.org/https%3A//doi.org/10.1016/j.automatica.2009.07.008)Cited by:[§III\-A](https://arxiv.org/html/2609.25701#S3.SS1.p2.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p12.1),[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p26.1)\.
- \[43\]X\. Lei, G\. Wen, and M\. M\. Polycarpou\(2026\)Distributed secure consensus tracking for multi\-agent systems: from asymptotic to finite\-/fixed\-time convergence\.IEEE Transactions on Automatic Control\(\),pp\. 1–8\.External Links:[Document](https://dx.doi.org/10.1109/TAC.2026.3660041)Cited by:[§III\-C](https://arxiv.org/html/2609.25701#S3.SS3.p2.1)\.
- \[44\]Z\. Wu, H\. Shen, T\. Chen, and Q\. Ling\(2021\)Byzantine\-resilient decentralized td learning with linear function approximation\.InICASSP 2021 \- 2021 IEEE International Conference on Acoustics, Speech and Signal Processing \(ICASSP\),Vol\.,pp\. 5040–5044\.External Links:[Document](https://dx.doi.org/10.1109/ICASSP39728.2021.9413992)Cited by:[§IV\-C](https://arxiv.org/html/2609.25701#S4.SS3.p26.1),[4th item](https://arxiv.org/html/2609.25701#S6.I1.i4.p1.1)\.
- \[45\]T\. H\. Cormen, C\. E\. Leiserson, R\. L\. Rivest, and C\. Stein\(2009\)Introduction to algorithms, 3rd edition\.MIT Press\.External Links:ISBN 978\-0\-262\-03384\-8Cited by:[§V](https://arxiv.org/html/2609.25701#S5.p7.1.1)\.

![[Uncaptioned image]](https://arxiv.org/html/2609.25701v1/haejoonlee.jpg)Haejoon Lee\(Student Member, IEEE\) received the B\.S\. degree in applied math and statistics from Stony Brook University, Stony Brook, NY, USA, in 2023\. He earned the M\.S\. degree in robotics in 2025 from the University of Michigan, Ann Arbor, MI, USA, where he is currently working toward the Ph\.D\. degree in robotics, advised by Prof\. Dimitra Panagou\.His research interests include safety, resilience, and security of autonomous systems, with particular emphasis on distributed consensus, optimization, and learning for multi\-agent systems in adversarial and uncertain environments\.![[Uncaptioned image]](https://arxiv.org/html/2609.25701v1/DimitraPanagou2.jpg)Dimitra Panagou\(Diploma \(2006\) and PhD \(2012\) in Mechanical Engineering from the National Technical University of Athens, Greece\) is an Associate Professor with the Department of Robotics, with a courtesy appointment with the Department of Aerospace Engineering, University of Michigan\. Her research program spans the areas of nonlinear systems and control; multi\-agent systems; autonomy; and aerospace robotics\. She is particularly interested in the development of provably\-correct methods for the safe and secure \(resilient\) operation of autonomous systems with applications in robot/sensor networks and multi\-vehicle systems under uncertainty\. She is a recipient of the NASA Early Career Faculty Award, the AFOSR Young Investigator Award, the NSF CAREER Award, the George J\. Huebner, Jr\. Research Excellence Award, and a Senior Member of the IEEE and the AIAA\.