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

arXiv: https://arxiv.org/abs/1806.00877 · HTML: https://mlsanity.com/paper/1806.00877/

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 3 Jun 2018.

## Built on by (most cited first, 30 of 40)

- [Gradient play in stochastic games: stationary points, convergence, and sample complexity](https://mlsanity.com/paper/2106.00198/) (2021)
- [The Confluence of Networks, Games and Learning](https://mlsanity.com/paper/2105.08158/) (2021)
- [Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysis](https://mlsanity.com/paper/2109.03699/) (2021)
- [Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximation](https://mlsanity.com/paper/2103.04972/) (2021)
- [Near-Optimal Algorithms for Making the Gradient Small in Stochastic Minimax Optimization](https://mlsanity.com/paper/2208.05925/) (2022)
- [Accelerated and instance-optimal policy evaluation with linear function approximation](https://mlsanity.com/paper/2112.13109/) (2021)
- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)
- [A Decentralized Adaptive Momentum Method for Solving a Class of Min-Max Optimization Problems](https://mlsanity.com/paper/2106.06075/) (2021)
- [Cooperative Multi-Agent Reinforcement Learning: Asynchronous Communication and Linear Function Approximation](https://mlsanity.com/paper/2305.06446/) (2023)
- [Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithm](https://mlsanity.com/paper/2310.20369/) (2023)
- [New Versions of Gradient Temporal Difference Learning](https://mlsanity.com/paper/2109.04033/) (2021)
- [Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guarantees](https://mlsanity.com/paper/2110.05597/) (2021)
- [Can Mean Field Control (MFC) Approximate Cooperative Multi Agent Reinforcement Learning (MARL) with Non-Uniform Interaction?](https://mlsanity.com/paper/2203.00035/) (2022)
- [An Efficient Stochastic Algorithm for Decentralized Nonconvex-Strongly-Concave Minimax Optimization](https://mlsanity.com/paper/2212.02387/) (2022)
- [Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity](https://mlsanity.com/paper/2103.13147/) (2021)
- [MARL with General Utilities via Decentralized Shadow Reward Actor-Critic](https://mlsanity.com/paper/2106.00543/) (2021)
- [PRECISION: Decentralized Constrained Min-Max Learning with Low Communication and Sample Complexities](https://mlsanity.com/paper/2303.02532/) (2023)
- [Faster Stochastic Algorithms for Minimax Optimization under Polyak--Lojasiewicz Conditions](https://mlsanity.com/paper/2307.15868/) (2023)
- [Second-Order Min-Max Optimization with Lazy Hessians](https://mlsanity.com/paper/2410.09568/) (2024)
- [Sample and Communication Efficient Fully Decentralized MARL Policy Evaluation via a New Approach: Local TD update](https://mlsanity.com/paper/2403.15935/) (2024)
- [Statistical inference for generative adversarial networks and other minimax problems](https://mlsanity.com/paper/2104.10601/) (2021)
- [Distributed saddle point problems for strongly concave-convex functions](https://mlsanity.com/paper/2202.05812/) (2022)
- [Scalable Interactive Machine Learning for Future Command and Control](https://mlsanity.com/paper/2402.06501/) (2024)
- [Non-Parametric Neuro-Adaptive Coordination of Multi-Agent Systems](https://mlsanity.com/paper/2110.05125/) (2021)
- [Convergence Rates of Average-Reward Multi-agent Reinforcement Learning via Randomized Linear Programming](https://mlsanity.com/paper/2110.12929/) (2021)
- [A Law of Iterated Logarithm for Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2110.15092/) (2021)
- [Distributed Policy Gradient with Variance Reduction in Multi-Agent Reinforcement Learning](https://mlsanity.com/paper/2111.12961/) (2021)
- [MAMRL: Exploiting Multi-agent Meta Reinforcement Learning in WAN Traffic Engineering](https://mlsanity.com/paper/2111.15087/) (2021)
- [Provably Efficient Convergence of Primal-Dual Actor-Critic with Nonlinear Function Approximation](https://mlsanity.com/paper/2202.13863/) (2022)
- [A primal-dual perspective for distributed TD-learning](https://mlsanity.com/paper/2310.00638/) (2023)

## Abstract (arXiv)

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.