Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization

Abstract

Despite the success of single-agent reinforcement learning, multi-agent reinforcement learning (MARL) remains challenging due to complex interactions between agents. Motivated by decentralized applications such as sensor networks, swarm robotics, and power grids, we study policy evaluation in MARL, where agents with jointly observed state-action pairs and private local rewards collaborate to learn the value of a given policy. In this paper, we propose a double averaging scheme, where each agent iteratively performs averaging over both space and time to incorporate neighboring gradient information and local reward information, respectively. We prove that the proposed algorithm converges to the optimal solution at a global geometric rate. In particular, such an algorithm is built upon a primal-dual reformulation of the mean squared projected Bellman error minimization problem, which gives rise to a decentralized convex-concave saddle-point problem. To the best of our knowledge, the proposed double averaging primal-dual optimization algorithm is the first to achieve fast finite-time convergence on decentralized convex-concave saddle-point problems.

final version as appeared in NeurIPS 2018

References in corpus (13)

• Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments
• SAGA: A Fast Incremental Gradient Method With Support for Non-Strongly Convex Composite Objectives
• Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents
• Distral: Robust Multitask Reinforcement Learning
• Deep Decentralized Multi-task Multi-Agent Reinforcement Learning under Partial Observability
• SBEED: Convergent Reinforcement Learning with Nonlinear Function Approximation
• Finite-Sample Analysis of Proximal Gradient TD Algorithms
• Stochastic Primal-Dual Methods and Sample Complexity of Reinforcement Learning
• Primal-Dual $\pi$ Learning: Sample Complexity and Sublinear Run Time for Ergodic Markov Decision Problems
• Diff-DAC: Distributed Actor-Critic for Average Multitask Deep Reinforcement Learning
• Learning from Conditional Distributions via Dual Embeddings
• Distributed Stochastic Gradient Tracking Methods
• Boosting the Actor with Dual Critic

Cited by in corpus (32)

• Stochastic Recursive Gradient Descent Ascent for Stochastic Nonconvex-Strongly-Concave Minimax Problems
• A Decentralized Parallel Algorithm for Training Generative Adversarial Nets
• Multi-Objective Multi-Agent Planning for Jointly Discovering and Tracking Mobile Object
• Recent theoretical advances in decentralized distributed convex optimization
• Accelerated Zeroth-Order and First-Order Momentum Methods from Mini to Minimax Optimization
• Byzantine-Resilient Decentralized TD Learning with Linear Function Approximation
• Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic Primal-Dual Optimization
• Optimization over time-varying directed graphs with row and column-stochastic matrices
• Communication-Efficient Distributed Optimization in Networks with Gradient Tracking and Variance Reduction
• Multi-Agent Trust Region Policy Optimization
• A Decentralized Policy Gradient Approach to Multi-task Reinforcement Learning
• Primal-Dual Distributed Temporal Difference Learning
• Distributed heavy-ball: A generalization and acceleration of first-order methods with gradient tracking
• Learning Mean-Field Games
• Alternating the Population and Control Neural Networks to Solve High-Dimensional Stochastic Mean-Field Games
• A Distributed Stochastic Gradient Tracking Method
• Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis
• Gradient play in stochastic games: stationary points, convergence, and sample complexity
• Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents
• A Reinforcement Learning Framework for Sequencing Multi-Robot Behaviors
• Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization
• Communication-Efficient Policy Gradient Methods for Distributed Reinforcement Learning
• MAMRL: Exploiting Multi-agent Meta Reinforcement Learning in WAN Traffic Engineering
• Decentralized Distributed Optimization for Saddle Point Problems
• Competing AI: How does competition feedback affect machine learning?
• Exploiting Fast Decaying and Locality in Multi-Agent MDP with Tree Dependence Structure
• On the Convergence of Consensus Algorithms with Markovian Noise and Gradient Bias
• Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning
• Some Limit Properties of Markov Chains Induced by Stochastic Recursive Algorithms
• A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning
• Voting-Based Multi-Agent Reinforcement Learning for Intelligent IoT
• The Confluence of Networks, Games and Learning