Finite-Sample Convergence in Networked Average Reward MARL: Decentralization Pitfalls and Entropy Remedies

Introduction

Multi-Agent Reinforcement Learning (MARL) has been a practically important regime for training real-world cooperative multi-agent systems, with applications ranging from autonomous driving [6], energy systems [15] and robotics [26]. When scaling up the number of agents for better cooperation in more complex multi-agent systems, we are faced with a problem known as the curse of dimensionality: the joint state-action space scales exponentially in the number of agents, making centralized value estimation, policy optimization, and exploration statistically and computationally intractable [14, 35, 31].

To make multi-agent systems more scalable, one promising approach is to leverage the problem structure. Among various different structures, a line of work considering networked MARL, where agents are associated within a network and only interact with neighboring agents, has gained much attention [28, 27, 39, 40]. Such networked structure can be used to model various multi-agent systems including social networks [21], communication networks [41] and smart transportation [36]. Leveraging the local interaction structure, Qu et al. [ [28] formulated an exponential decay property, which formulates the system identity that the impact of an agent decays exponentially in the distance within the network. Using this property, agents can infer the global $Q$ function and update its policy based only on the information available nearby [28, 27], thereby making network MARL more scalable.

Despite this breadth, prior analyses leave two gaps. First, the optimality of stationary points of policy-gradient objective has been extensively characterized in single-agent settings across a variety of MDP formulations [17, 22, 7] (Murthy and Srikant 2023), whereas analogous insights for networked average-reward MARL—where agents are constrained to localized policies and update with nearby information—have not been developed. Second, existing convergence guarantees in this setting are largely tabular convergence to stationary points—the policy gradient norm vanishes in the limit [28, 27, 20]. Finite-time bounds that characterize the suboptimality of the policy as a function of the number of samples used for training, and that expose how the localization error from $k$-hop truncation, the function-approximation error from the feature class, and the statistical TD error from finite samples interact, have not been established for networked average-reward MARL. This motivates the two central questions of this paper:

Are global convergence guarantees achievable under decentralized localized learning? How do localization, function approximation, and the number of samples used for learning interact in the policy-based analyses of average-reward networked MARL?

Our contributions. We address these questions through three main contributions.

1. We identify Multiagency and Partial Observability—two intrinsic structural obstructions to global convergence under unregularized decentralized learning. For multiagency, we show through Example 2 that while ergodicity of the induced Markov chain guarantees global optimality of every stationary point of policy gradient in single-agent RL [17], this guarantee fails once the joint policy is constrained to be a product of local policies, even in a fully cooperative, fully observable, ergodic MDP. For partial observability, Example 3 shows that when the individual policies cannot depend on the global state, a vanishing local policy gradient need not even certify a notion of unilateral optimality: the stationary point can have strictly positive Nash gap, i.e., at least one agent has a profitable deviation given the others’ policies fixed. These two examples reflect broader coordination and local-information challenges in cooperative MARL, and motivate why our unregularized guarantees are stated in terms of stationarity.

2. We connect network localization with linear function approximation and derive finite-sample guarantees for the resulting actor-critic method. We observe that a $k$-hop tabular critic is simply a linear approximation to the global $Q$-function, with features that group together global state-action pairs indistinguishable from agent $i$’s local view. This perspective allows each agent to use a compact linear critic on its $k$-hop neighborhood, rather than maintaining an exponentially large local table. It also reveals a clear tradeoff: larger neighborhoods reduce localization bias, but require richer features to avoid approximation error. Using this localized-linear critic, we prove finite-sample stationarity of unregularized decentralized actor-critic. The resulting bound groups the error into a finite-sample learning term, which captures critic tracking, Markovian sampling, and actor-critic coupling, plus two structural approximation terms: feature approximation and network localization.

3. We show that adding strong fixed-state entropy regularization can restore global convergence. The regularized algorithm adds an analytic local entropy-gradient correction while leaving the reward critic unchanged. Theorem 5 gives finite-time global convergence for the fixed-state entropy objective under the entropy-dominance and uniform-exploration conditions. In contrast to the unregularized case, the regularized result admits convergence to the globally optimal regularized objective function, and improves the best-iterate guarantee to a stronger last-iterate. Additionally, the regularized suboptimality contracts geometrically up to the statistical, approximation, and localization errors.

Preliminaries

In this section we present our problem setup and introduce basic problem properties.

Networked Average-Reward MDP

We work under the same problem setting as in [27]. Consider a network of $n$ agents specified by an undirected graph $\mathcal{G}=(\mathcal{N},\mathcal{E})$ where $\mathcal{N}=\{1,2,\ldots,n\}$ is the set of nodes with each node representing an agent, and $\mathcal{E}\subseteq\mathcal{N}\times\mathcal{N}$ denotes the set of edges. Each agent $i$ has a local state $s_i\in\mathcal{S}_i$ and local action $a_i\in\mathcal{A}_i$. The global state and action are the joint tuples of local states and actions respectively, namely $s_g=(s_1,\ldots,s_n)\in\mathcal{S}_g:=\mathcal{S}_1\times\cdots\times\mathcal{S}_n$ and $a_g=(a_1,\ldots,a_n)\in\mathcal{A}_g:=\mathcal{A}_1\times\cdots\times\mathcal{A}_n$. For each agent $i$, we let $\mathcal{N}_i$ denote the set of its neighbors (including itself) in the graph, and $\mathcal{N}_i^k$ denote the $k$-hop neighborhood consisting of all agents with graph distance at most $k$ to $i$. We use $s_i^k\in\mathcal{S}_i^k$ and $a_i^k\in\mathcal{A}_i^k$ to denote the joint state and action in the $k$-hop neighborhood of $i$ respectively.

At each time step $t$, the next local state $s_i(t+1)$ is independently generated according to the transition kernel, which only depends on the local action and the (1-hop) neighboring states, such that $s_i(t+1)\sim P_i(\cdot\mid s_i^1(t),a_i(t))$. Accordingly, the global transition kernel is the following product:

Each agent has a policy $\pi_{\theta_i}:\mathcal{S}_i\to\Delta(\mathcal{A}_i)$ parameterized by $\theta_i$ that depends only on the local state. We assume that each agent adopts a softmax parameterization, such that $\pi_{\theta_i}(a_i\mid s_i)=\frac{\exp(\theta_i(s_i,a_i))}{\sum_{a_i'\in\mathcal{A}_i}\exp(\theta_i(s_i,a_i'))}$. The global policy $\pi_\theta(a_g\mid s_g)=\prod_{i=1}^{n}\pi_{\theta_i}(a_i\mid s_i)$ where $\theta=(\theta_1,\ldots,\theta_n)$ denotes the joint global parameters. Let $\nu^\theta$ denote the corresponding stationary distribution over $\mathcal{S}_g\times\mathcal{A}_g$.

When acting $a_i$ at local state $s_i$, agent $i$ receives a local reward $r_i(s_i,a_i)$. Throughout the paper, we assume local rewards are uniformly bounded: there exists $\bar r>0$ such that $|r_i(s_i,a_i)|\leq\bar r$ for all $i\in\mathcal{N}$ and $(s_i,a_i)\in\mathcal{S}_i\times\mathcal{A}_i$. We define the global reward as the sum of local rewards: $r(s_g,a_g):=\sum_{i=1}^{n}r_i(s_i,a_i)$. The objective of all agents is to collaboratively maximize the average global reward $J(\theta):=\mathbb{E}_{(s_g,a_g)\sim\nu^\theta}[r(s_g,a_g)]$, while each agent only uses information within its $k$-hop neighborhood $\mathcal{N}_i^k$. When the policy induces an ergodic Markov chain, the average reward is independent of initial state distribution [2]. We can decompose the global average reward $J(\theta)$ into local average rewards as: $J(\theta)=\sum_{i=1}^{n}J_i(\theta)$, where $J_i(\theta):=\mathbb{E}_{(s_i,a_i)\sim\nu^\theta}[r_i(s_i,a_i)]$ are the local average rewards of agent $i$. Define the global and local $Q$ functions as: