cs.LGNov 2, 2026

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

Authors: Yizhou Zhang, Yashaswini Murthy, Laixi Shi, Adam Wierman

Organizations: The University of Texas at Austin · Johns Hopkins University

Abstract

We study the problem of average reward Multi-Agent Reinforcement Learning (MARL) where agents interact within a network. Each agent in the network conducts local updates with information within its kk-hop neighborhood and collaboratively maximizes the overall reward of the entire network. We first provide impossibility results in achieving convergence to the global optimal joint policies in our setting. These impossibility results highlight the challenges of decentralized learning with local information in multi-agent systems, namely the issues of multiagency, where each agent independently optimizes its policy, and partial observability, where agents have limited visibility into the global state. Given these challenges which indicate that decentralized policy optimization can generally be certified only up to stationarity, we provide finite-sample convergence guarantees for a decentralized actor-critic algorithm with linear function approximation that converges to an approximate stationary point with small gradient norm. To overcome such impossibility results, we further show that adding fixed-state entropy regularization reshapes the objective landscape which leads to even stronger global convergence guarantees for our proposed actor-critic algorithm.

Figures & tables

Appendix figures & tables12 assets

Supplementary material from the paper’s appendix.

Appendix

Explore similar work

CardsList
  1. A Unified Framework for Locality in Scalable MARL

    Feb 19, 2026Sourav Chakraborty, Amit Kiran Rege, Claire Monteleoni +1Multi-Agent Reinforcement LearningAverage-Reward RL

  2. Ensemble-MIX: Enhancing Sample-Efficiency in Multi-Agent RL via Selective Ensemble-Based Exploration

    Jun 3, 2025Tom Danino, Nahum ShimkinMulti-Agent Reinforcement LearningSample-Efficient RL

  3. Variance-Reduced Q-Learning over Static and Time-Varying Networks

    Jul 24, 2026Sreejeet Maity, Feng Zhu, Aritra Mitra +1Reinforcement LearningQ-Learning