Natural Actor-Critic Converges Globally for Hierarchical Linear Quadratic Regulator

Abstract

Multi-agent reinforcement learning has been successfully applied to a number of challenging problems. Despite these empirical successes, theoretical understanding of different algorithms is lacking, primarily due to the curse of dimensionality caused by the exponential growth of the state-action space with the number of agents. We study a fundamental problem of multi-agent linear quadratic regulator (LQR) in a setting where the agents are partially exchangeable. In this setting, we develop a hierarchical actor-critic algorithm, whose computational complexity is independent of the total number of agents, and prove its global linear convergence to the optimal policy. As LQRs are often used to approximate general dynamic systems, this paper provides an important step towards a better understanding of general hierarchical mean-field multi-agent reinforcement learning.

References in corpus (17)

• Learning to Communicate with Deep Multi-Agent Reinforcement Learning
• Stabilising Experience Replay for Deep Multi-Agent Reinforcement Learning
• Safe, Multi-Agent, Reinforcement Learning for Autonomous Driving
• Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents
• Mean Field Multi-Agent Reinforcement Learning
• Global Convergence of Policy Gradient Methods for the Linear Quadratic Regulator
• Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability
• Mean-Field Optimal Control
• Gradient Descent Learns Linear Dynamical Systems
• On the Sample Complexity of the Linear Quadratic Regulator
• Deep Reinforcement Learning for Event-Driven Multi-Agent Decision Processes
• Learning Without Mixing: Towards A Sharp Analysis of Linear System Identification
• On the Global Convergence of Actor-Critic: A Case for Linear Quadratic Regulator with Ergodic Cost
• Least-Squares Temporal Difference Learning for the Linear Quadratic Regulator
• Linear Quadratic Mean Field Teams: Optimal and Approximately Optimal Decentralized Solutions
• Learning Deep Mean Field Games for Modeling Large Population Behavior
• A Class of Discrete-time Mean-field Stochastic Linear-quadratic Optimal Control Problems with Financial Application

Cited by in corpus (3)

• Game-Theoretic Multiagent Reinforcement Learning
• Non-asymptotic Convergence of Adam-type Reinforcement Learning Algorithms under Markovian Sampling
• Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis