Research map / Multi-agent systems and games / Cooperative multi-agent RL
Finite-Time Global Optimality Convergence in Deep Neural Actor-Critic Methods for Decentralized Multi-Agent Reinforcement Learning
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes a deep-neural actor-critic method for fully decentralized MARL with gossip-based consensus and a pseudo-centralized parameter, proving O(1/T) finite-time convergence to global optimality, and tests it on a Simple Spread ablation and a multi-agent RLHF experiment.
Problem
Existing theory for decentralized actor-critic MARL covers only linear critics and stationary-point convergence, leaving a gap with practical DNN-based critics and global optimality guarantees.
Approach
A decentralized actor-critic with overparameterized ReLU critic networks, gossip-based consensus on TD-errors and critic weights, and a pseudo-centralized averaged parameter used to handle the non-interchangeable order of nonlinear updates and consensus, yielding a global optimality bound with O(1/T) rate.
Key results
- Theorem gives E[J(theta*) - J(theta_T)] = O(1/T) plus bias terms O(sqrt(eps_bias)) and O(eps_critic), with sample complexity O(N^2/eps^3) stated in the corollary.
- In the Simple Spread ablation, the consensual TD-error version shows increasing rewards while the Q-value version fails to learn and rewards decrease over episodes.
- In the multi-agent RLHF experiment with two LLMs, average reward increases steadily for all LLMs over episodes.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| replace consensual TD-error with Q-values (ablation) | DNN-based actor-critic · Simple Spread | reward | Hurt |
| use consensual TD-error instead of Q-values (ablation) | DNN-based actor-critic · Simple Spread | reward | Helped |
| train with the decentralized actor-critic method | multi-agent RLHF · Multi-agent RLHF | average reward | Helped |
Surprising findings
- Q-value-based variant performs worse than TD-error/advantage-based updates, contrary to the theoretical advantage of skipping gossip in the actor.
- The analysis suggests depth matters more than width for performance, with width having little impact on the bound.
Experimental setup
Datasets: Simple Spread
Benchmarks: Simple Spread
Metrics: episode reward
Baselines: Q-value-based actor-critic variant linear-approximation decentralized actor-critic MARL
Builds on: actor-critic with neural network critic (single-agent) restart kernel Simple Spread
Closest papers by meaning
- Finite-Time Convergence and Sample Complexity of Multi-Agent Actor-Critic Reinforcement Learning with Average Reward (ICLR 2022 · similarity 0.92)
- Finite-Time Analysis of Actor-Critic Methods with Deep Neural Network Approximation (ICLR 2026 · similarity 0.91)
- Federated Natural Policy Gradient and Actor Critic Methods for Multi-task Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
- Closing the Gap: Achieving Global Convergence (Last Iterate) of Actor-Critic under Markovian Sampling with Neural Network Parametrization (ICML 2024 · similarity 0.88)
- Mean Field Langevin Actor-Critic: Faster Convergence and Global Optimality beyond Lazy Learning (ICML 2024 · similarity 0.88)
- A Sharper Global Convergence Analysis for Average Reward Reinforcement Learning via an Actor-Critic Approach (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.