Networked average-reward multi-agent learning gets finite-sample bounds: decentralized updates certify only stationarity, strong entropy restores global optimality
Synopsis
In networked average-reward multi-agent reinforcement learning, each agent updates its policy using only its k-hop neighborhood, and prior results in this setting were tabular convergence to stationary points. The work first gives two counterexamples: even in a fully cooperative, fully observable, ergodic setting, product local policies can stall at a suboptimal local optimum, and when local policies cannot see the global state a vanishing gradient need not certify unilateral optimality. It then proves a finite-sample stationarity bound for a decentralized actor-critic with linear critics, and shows that strong fixed-state entropy regularization upgrades the guarantee to global optimality.
Interpretation
Networked average-reward multi-agent reinforcement learning now has a finite-sample convergence characterization, but without regularization what can be certified is only that the policy-gradient norm vanishes, not convergence to a globally optimal joint policy. Prior convergence guarantees in this setting were largely tabular and asymptotic convergence to stationary points, with no finite-time bounds in the number of samples and no account of how k-hop truncation localization error, feature-class function-approximation error and finite-sample TD statistical error interact. Two counterexamples support the limit: in a one-state two-agent coordination problem the product policy at (p,q)=(0,0) has value 1 and is a strict local optimum while the global optimum (1,1) has value 2; in a two-node example all local policy gradients vanish at p=1/2, yet a unilateral move to p′=1/4 raises average reward from 2/3 to 10/13, giving a Nash gap of at least 4/39.
The algorithm has each agent maintain a low-dimensional linear critic over its k-hop neighborhood and build the actor direction from a weighted sum of neighborhood critic values, avoiding a local table that grows exponentially with the neighborhood. A k-hop tabular critic is itself a linear approximation to the global Q function, with features that group global state-action pairs indistinguishable from the agent's local view; compressing further to d features splits the error into a localization term and a function-approximation term. Localization error decays geometrically as O(cρk+1), while at fixed feature dimension a larger k increases the compression burden; in maintenance-unit environments with paths of 8, 16, 32 and 64 agents and grids of side length 3, 4, 6 and 8, that is 9, 16, 36 and 64 agents, path k=1 at feature dimension 16 reaches 0.676±0.002 greedy reward per agent while k=3 falls to 0.392±0.148, and the tabular critic stays near 0.058 on grids.
Perspective
The conclusions apply to networked average-reward settings where each agent's state transition is influenced only by immediate neighbors and the exponential decay property therefore holds, with policies restricted to product local policies that depend only on local states; the numerical examples are finite-state maintenance-unit environments with paths of 8, 16, 32 and 64 agents and grids of side length 3, 4, 6 and 8, that is 9, 16, 36 and 64 agents.
The global convergence guarantee requires entropy regularization to be strong, with the entropy weight exceeding the ratio of the unregularized objective's curvature bound on the explored region to the minimum state weight, and the authors explicitly treat fixed-state entropy regularization as a remedy rather than a universal fix; convergence is to the regularized optimum over the local product-policy region, not to optimality over unrestricted centralized policies.