Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward

Abstract

It has long been recognized that multi-agent reinforcement learning (MARL) faces significant scalability issues due to the fact that the size of the state and action spaces are exponentially large in the number of agents. In this paper, we identify a rich class of networked MARL problems where the model exhibits a local dependence structure that allows it to be solved in a scalable manner. Specifically, we propose a Scalable Actor-Critic (SAC) method that can learn a near optimal localized policy for optimizing the average reward with complexity scaling with the state-action space size of local neighborhoods, as opposed to the entire network. Our result centers around identifying and exploiting an exponential decay property that ensures the effect of agents on each other decays exponentially fast in their graph distance.

References in corpus (8)

• Benchmarking Deep Reinforcement Learning for Continuous Control
• Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents
• $QD$-Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through Consensus + Innovations
• Nonequilibrium phase transition in a model for the propagation of innovations among economic agents
• Non-asymptotic Convergence Analysis of Two Time-scale (Natural) Actor-Critic Algorithms
• Decentralized and Distributed Temperature Control via HVAC Systems in Energy Efficient Buildings
• A Survey on the Computational Complexity of Colouring Graphs with Forbidden Subgraphs
• Exploiting Fast Decaying and Locality in Multi-Agent MDP with Tree Dependence Structure

Cited by in corpus (4)

• Towards Understanding Asynchronous Advantage Actor-critic: Convergence and Linear Speedup
• Multi-Agent Algorithms for Collective Behavior: A structural and application-focused atlas
• Causal Multi-Agent Reinforcement Learning: Review and Open Problems
• Interpreting Graph Drawing with Multi-Agent Reinforcement Learning