Source-linked AI summary
Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, Mingyi Hong
TL;DR
MARL policy evaluation must handle interactions among agents and private local rewards while learning a shared value function. The paper reformulates the problem as a decentralized convex-concave saddle point and proposes double averaging; it proves global geometric convergence and identifies a communication-related scope boundary for a variant.
Problem
MARL policy evaluation remains challenging when agents jointly observe states and actions but receive private local rewards, creating a need for decentralized information exchange.
Method
The paper applies Fenchel duality to obtain a decentralized primal-dual finite-sum problem and uses double averaging over agents and trajectory observations.
Results
The proposed algorithm achieves global geometric, or linear, convergence and is presented as the first fast finite-time result for decentralized convex-concave saddle-point problems.
Takeaways & Limitations
The algorithm and analysis extend beyond MARL policy evaluation to a broader class of decentralized convex-concave saddle-point problems with sampled observations.
Takeaways & Limitations
A communication-reducing time-varying-weight modification is proposed, but its convergence is left for future work.
Abstract
from arXiv · showhide
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.
1 Introduction
The paper studies collaborative MARL policy evaluation when agents share state-action observations but have private local rewards. It combines a Fenchel-duality reformulation with decentralized primal-dual optimization and double averaging, targeting fast convergence.
- Motivation: Collaborative MARL requires agents to learn a globally optimal value while observing only their own potentially different rewards.Agents share joint state transitions and must exchange local information to maximize the global sum of local rewards.
- Contribution: The paper reformulates policy evaluation through Fenchel duality and proposes a decentralized primal-dual algorithm with double averaging.Agents average information across space for consensus and across time to incorporate trajectory observations and local rewards.
- Related work: Prior collaborative MARL analyses often use tabular models, asymptotic two-time-scale methods, identical rewards, or empirical deep-learning evaluations without theoretical guarantees.These limitations motivate methods that support function approximation, private rewards, efficient information exchange, and finite-time guarantees.
- Contribution: The proposed algorithm is proved to converge at a global geometric rate and is presented as the first fast linear-convergence algorithm for MARL.The analysis also applies to a broader class of decentralized convex-concave saddle-point problems with sampled observations.
2 Problem Formulation
The paper formulates MARL policy evaluation as decentralized optimization of an approximate value function under shared state-action observations and private local rewards. Function approximation, sampling, Fenchel duality, and consensus together produce a convex-concave primal-dual finite-sum problem.
- Policy evaluation: A fixed joint policy induces a value function defined by expected discounted cumulative reward, and policy evaluation seeks to learn that function.The value function satisfies a Bellman equation associated with the policy-induced Markov chain and stationary distribution.
- Function approximation: Linear function approximation represents the value as Vθ(s) using a parameter θ and known feature dictionary φ(s), avoiding storage of the full state-value vector.The goal is to find θ such that the approximated value Vθ closely matches the policy value Vπ.
- Objective: The approximation parameter is obtained by minimizing the mean squared projected Bellman error, with projection and regularization defined using the policy’s stationary distribution.Under full-rank and positive-definiteness conditions, the MSPBE has a unique minimizer.
- Decentralized information: Agents observe joint states and actions but only their private local rewards, so no agent can independently compute the global reward-based empirical objective.Each agent can compute shared sampled quantities such as  and Ĉ, while reward-dependent b̂_i remains private.
- Primal-dual reformulation: Fenchel duality converts the empirical MSPBE minimization into a decentralized convex-concave saddle-point problem whose local functions share the primal parameter θ.The resulting formulation preserves local-function privacy while coupling agents through consensus on θ.
- Optimization challenges: Solving the saddle-point problem requires simultaneous primal-dual updates, finite-sum handling, and decentralized consensus despite potentially large sample counts.These challenges arise because the objective may lack strong convexity in θ, contain M local sample terms, and keep each agent’s local function private.
3 Primal-dual Distributed Incremental Aggregated Gradient Method
PD-DistIAG combines decentralized primal-dual optimization with double gradient averaging to solve large finite-sum problems while tracking consensus and gradient information. Under sufficient conditions, it converges linearly, with extensions to broader multi-agent finite-sum optimization.
- Communication Model: Each agent maintains local primal and dual copies while exchanging information over a connected undirected communication graph.The shared primal parameter requires agents to communicate to reach a consensual solution.
- Proposed Method: PD-DistIAG combines primal-dual batch updates, distributed gradient tracking, and stochastic average gradient techniques.The method addresses simultaneous primal-dual updates, decentralized information sharing, and large sample sums.
- Double Averaging: Double averaging tracks gradients across agents and samples by combining neighbor averaging with incremental swap-in swap-out updates.The spatial component resembles distributed gradient tracking, while the temporal component follows the SAG approach.
- Double Averaging: The gradient estimator is unbiased with respect to the network-wide average and averages local and past sample gradients.This construction supplies sample-averaged gradient surrogates despite disparities across agents.
- Limitations and Extensions: Communication can be reduced through multiple local updates, but convergence with the resulting time-varying weight matrix remains future work.The standard method may incur significant communication overhead when d ≫1 and successive updates make little progress.
- Convergence Analysis: Theorem 1 confirms linear convergence of the primal-dual solution and linear decay of the consensual error of local parameters.The analysis establishes convergence for the coupled delayed system when a suitable step size makes the relevant spectral radius less than one.
- Convergence Analysis: For N, M ≫1 on a geometric graph, γ = O(1/ max{N^2, M^2}) gives rate σ = 1 −O(1/ max{MN^2, M^3}).The stated rate is a sufficient-condition result for the large-agent, large-sample regime.
- Limitations and Extensions: The analysis may extend to multi-agent empirical risk minimization when the sum objective is strongly convex and local objectives are smooth.The paper identifies this as an independently interesting extension of the double averaging framework.
4 Numerical Experiments
The mountaincar experiment evaluates PD-DistIAG against centralized baselines under decentralized data collection with 10 agents. PD-DistIAG converges faster than the other methods except SAGA, with speed comparable to SAGA when regularization is positive.
- Experimental setup: The experiment studies graph topology alongside settings with ρ = 0.01 and ρ = 0.The figure caption identifies these as the middle and right panels, respectively.
- Evaluation metric: Figure 1 reports optimality gaps in MSPBE against epoch number, with epochs defined as t/M.For PD-DistIAG, the optimality gap is measured using its average objective across agents.
- Results: With ρ > 0, PD-DistIAG converges at a speed comparable to SAGA.The comparison uses the left-panel setting with positive regularization.
- Results: With ρ = 0, PD-DistIAG converges more slowly than SAGA but faster than the other compared methods.The paper also reports supplementary experiments across topology and regularization settings.
- Conclusion: The proposed method demonstrates linear convergence in the studied policy-evaluation setting under the paper’s assumptions.This conclusion summarizes the method’s reported convergence property.
A Proof of Theorem 1
The proof establishes linear convergence by tracking optimality, consensus, and gradient-estimation errors through a coupled Lyapunov analysis. Under sufficiently small step sizes, these quantities contract geometrically.
- Contraction argument: If the primal step size is sufficiently small, a constant 0 < σ < 1 bounds the error contraction.The resulting contraction applies to the averaged parameter error and related Lyapunov quantities.
- Optimality system: The proof derives the coupled recursion from the first-order optimality system represented by the matrix G and sample matrices Gp.G is the sample average of the matrices Gp.
- Algorithmic interpretation: The primal and dual averaged iterates can be viewed as decentralized primal-dual updates using tracked gradient estimates.These estimates serve as decentralized counterparts of centralized batch gradients.
- Convergence analysis: The proof analyzes the difference from the primal-dual optimum using Lyapunov functions for the algorithm’s error components.The convergence analysis begins by bounding the difference from the optimal solution and then tracks associated residual terms.
- Error decomposition: The recursion separates optimality, consensus, and gradient-tracking residuals into coupled error terms.Consensus residuals and gradient-estimation terms are explicitly bounded in the proof sequence.
- Conclusion: The proof concludes that the relevant Lyapunov quantities converge linearly with iteration index t.This conclusion follows after applying the auxiliary recursive-system lemmas to the derived inequality.
A.1 Two Useful Lemmas
The auxiliary lemmas reduce convergence to the spectral radius of a nonnegative delayed-recursion matrix. They show that sufficiently small step sizes ensure contraction and provide asymptotic scaling for large agent and sample counts.
- Role in theorem: The lemmas supply the spectral-radius condition used to prove linear convergence of the main algorithm.Combining the two lemmas yields the final step of the theorem’s proof.
- Lemma 2: A delayed nonnegative-vector recursion converges when its governing matrix Q is irreducible and has spectral radius ρ(Q) < 1.The lemma bounds the recursion by powers of ρ(Q), with constants depending on initialization.
- Lemma 2: The proof uses the positive Perron eigenvector of Q to establish geometric bounds across delayed blocks.Induction extends the bound from the initial block through subsequent blocks of length M.
- Lemma 3: For sufficiently small γ, the matrix Q satisfies ρ(Q) < 1, providing the contraction condition required by the first lemma.The argument bounds the spectral radius using the characteristic polynomial and Perron-Frobenius reasoning.
- Asymptotic scaling: When M, N ≫ 1 and the graph is geometric, γ = O(1/max{N^2, M^2}) is sufficient for convergence.The scaling combines sample-size and network-connectivity constraints.
- Asymptotic scaling: Under the same large-scale geometric-graph regime, ρ(Q) ≤ 1 − O(1/max{N^2, M^2}).This bound characterizes the contraction factor for the auxiliary recursion.
A.2 Derivation of Equation (A.6)
This derivation verifies the blockwise representation of the centralized gradient system used in the convergence proof. It treats the primal block first and then establishes the corresponding dual blocks.
- Blockwise derivation: The derivation establishes Equation (A.6) by verifying each block of the vector h(t).The proof explicitly separates the first block from the remaining blocks.
- Primal block: The first block is obtained from the definition of the primal gradient hθ(t).The argument evaluates the primal component directly before treating the dual components.
- Conclusion: Combining the primal and dual block calculations yields the desired equality in Equation (A.6).The final step assembles the separately verified block identities.
- Dual blocks: For each agent i, the remaining block is derived from the local dual gradient hwi(t).The proof identifies the corresponding block of the matrix-vector product involving G.
B Additional Experiments
Additional experiments examine how graph topology, sample size, and regularization affect PD-DistIAG. With many samples, ring and ER graph performance becomes nearly identical because sample-size effects dominate connectivity.
- The experiments vary graph topology, sample size M, and regularization parameter ρ to test their effects on PD-DistIAG.
- The additional experiments compare M = 500 and M = 5000 samples while varying ρ between 0.01 and 0.1.
- With N = 500 agents, the topology comparison uses a ring graph and an ER graph with connection probability 1.01 log N/N.
- For M = 5000, ring and ER graph performances are almost identical, indicating that large sample size makes the algorithm insensitive to graph connectivity.The stated rate is O(σ^t), with σ = 1 − O(1/max{MN^2, M^3}); when M ≫ N, sample-size effects dominate.