wikillm

Paper · 2018-06-03 · cs.LG, math.OC, stat.ML

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

Decentralised policy evaluation for multi-agent RL with private rewards. The projected Bellman error becomes a decentralised convex-concave saddle-point problem, solved by PD-DistIAG, where agents average gradients over neighbours and stored samples. Linear convergence is proved for connected graphs. Author-reported mountaincar runs with ten agents are comparable to centralised SAGA.

Multi-agent reinforcement learningMinimax optimizationVariance-reduced gradientGradient trackingmulti-agentpolicy-evaluationprimal-dualdecentralized-optimization

arXivPDFMarkdown9 min read

AI-compiled by claude-haiku-5-5 on 2026-11-12, not yet reviewed by a human. Every claim cites its source; check it when a detail matters.

In plain words

Several agents each see only their own reward, yet they need one shared estimate of how good a fixed way of acting is. The paper rewrites that estimation problem as a game between a value estimate and a set of dual variables, one per agent. The agents then solve the game together without sending their rewards to a central node.

Each agent keeps a running guess of the overall gradient. The guess is updated by averaging with neighbours over the network, and by swapping in a fresh per-sample gradient while the remaining samples keep their stored values. The agents end up agreeing on the estimate, and the authors prove that this happens at a fast, geometric rate under stated conditions. The setting is sensor networks, swarms or power grids, where a central controller is undesirable.

TL;DR

  • Policy evaluation for cooperative multi-agent RL, with linear value functions and private local rewards §2.
  • The estimation problem becomes a decentralised convex-concave saddle-point problem, solved by PD-DistIAG, which tracks the gradient over space (neighbours) and over time (stored samples) §3 alg. 1.
  • Theorem 1 proves linear convergence on connected graphs, with step sizes and rates given as orders of magnitude; the primal step is only "sufficiently small" §3.1 [thm. 1].
  • The only numeric results are curves for one mountaincar setup, with ten agents and author-reported speed §4 fig. 1.

Problem

Agents share the state and joint action, but each agent observes only its own reward. The goal is a value estimate for a fixed joint policy §2. A central controller that collects rewards would reduce the problem to a single-agent MDP, but it is a single point of failure, does not scale and conflicts with reward privacy §1. The paper therefore asks for a decentralised scheme in which agents exchange information only with neighbours in a connected network §1 §3.

Value function: the paper approximates the value with a linear model V_\theta(s) = \phi(s)^\top \theta and seeks \theta that minimises the mean squared projected Bellman error with a ridge term \rho\|\theta\|^2, where \rho \ge 0 §2 eq. 4. Because the state space is large, the expectations are replaced by sample averages over M samples from the policy's trajectory §2 eq. 6 eq. 7. The averaged reward R_c is the average of the local rewards §2 eq. 1.

Decentralisation: each agent can compute the sample matrices \hat A and \hat C but not \hat b, because it does not know the other agents' rewards §2. Writing the empirical error as an average over agents of local terms eq. 8 and applying Fenchel duality eq. 9 gives a finite-sum saddle-point problem eq. 10. The paper notes three difficulties: the primal function is not strongly convex, M may be large, and the agents must reach consensus without sharing their local functions §2.

Method

Notation: W is a doubly stochastic weight matrix, zero on non-edges. Its spectral gap parameter \lambda = \lambda_{\max}(W - \tfrac{1}{N}\mathbf{1}\mathbf{1}^\top) is below one for a connected graph §3. Each agent i holds a local primal copy \theta_i, a local dual vector w_i, a primal gradient tracker s_i and a dual gradient tracker d_i §3. A sample index p_t is chosen identically by all agents at each iteration alg. 1.

  1. Local sample terms. For sample p, agent i uses the matrices A_p, C_p and its private vector b_{p,i} defined in eq. 6 and the per-agent objective J_{i,p} of eq. 10. The primal gradient of J_{i,p} is A_p^\top w_i + \rho\theta and the dual gradient is A_p\theta - b_{p,i} - C_p w_i. These follow from eq. 10; the appendix writes them out in its definitions of the averaged gradients app. A.
  2. Primal tracker. Each agent mixes its neighbours' trackers with W and swaps in the new gradient for sample p_t in place of that sample's last stored gradient eq. 13 alg. 1. Lemma 1 shows that the network average of the trackers equals the average, over all agents and all samples, of each sample's most recent stored gradient [lem. 1] eq. 16.
  3. Dual tracker. The dual tracker is local, so it only averages over time, with the same swap-in, swap-out rule eq. 14 §3.
  4. Updates. Primal: consensus averaging of neighbours' \theta, then a descent step along s_i. Dual: an ascent step along d_i eq. 15. Step sizes satisfy \gamma_2 = \beta\gamma_1 with \beta given in §3.1 [thm. 1].
  5. Memory. Each agent stores the last primal and dual gradient for every sample §3, storage paragraph.
Pseudocode
# PD-DistIAG: one synchronous iteration over all N agents  [alg. 1]
# theta, w, s, d_track: (N, d), one row per agent
# memo_s, memo_d: (N, M, d), last stored gradient per agent and sample
# W: (N, N) doubly stochastic mixing matrix, zero on non-edges
def pd_distiag_step(theta, w, s, d_track, memo_s, memo_d, p):
    # Mix the previous primal tracker over the network  [eq. 13]
    s_mixed = W @ s
    # Fresh primal and dual gradients of every agent on sample p  [eq. 13]
    new_gs = grad_theta_J(theta, w, p)              # (N, d)
    new_gd = grad_w_J(theta, w, p)                  # (N, d)
    # Swap the stored gradient of sample p for the new one  [eq. 13]
    s = s_mixed + (new_gs - memo_s[:, p]) / M
    # Same swap-in, swap-out rule for the local dual tracker  [eq. 14]
    d_track = d_track + (new_gd - memo_d[:, p]) / M
    memo_s[:, p] = new_gs
    memo_d[:, p] = new_gd
    # Consensus step on theta, ascent step on w  [eq. 15]
    theta = W @ theta - gamma1 * s
    w = w + gamma2 * d_track
    return theta, w, s, d_track

Key equations, in this card's notation:

\min_{\theta}\max_{w_1,\dots,w_N}\frac{1}{NM}\sum_{i=1}^{N}\sum_{p=1}^{M}J_{i,p}(\theta,w_i),\quad J_{i,p}=w_i^\top A_p\theta-b_{p,i}^\top w_i-\tfrac12 w_i^\top C_p w_i+\tfrac{\rho}{2}\|\theta\|^2 eq. 10

A_p=\phi(s_p)\big(\phi(s_p)-\gamma\phi(s_{p+1})\big)^\top,\quad C_p=\phi(s_p)\phi(s_p)^\top,\quad b_{p,i}=\mathcal R_i(s_p,a_p)\,\phi(s_p) eq. 6

Theorem 1 §3.1 [thm. 1]: assume A1 and A2 (below), set \gamma_2=\beta\gamma_1 with \beta = 8(\rho+\lambda_{\max}(\hat A^\top\hat C^{-1}\hat A))/\lambda_{\min}(\hat C), and take \gamma_1 small enough. Then the averaged primal and the dual iterates converge to the saddle point at a rate O(\sigma^t), and the spread of the local primal copies also decays at rate O(\sigma^t). On a geometric graph, \gamma_1 = O(1/\max\{N^2,M^2\}) and \sigma = 1 - O(1/\max\{MN^2,M^3\}).

Assumptions §3.1:

  • A1 (sampling). Every sample is visited at least once in every window of M iterations. The paper's examples are a cyclic order or random shuffling without replacement.
  • A2 (full rank). \hat A is full rank and \hat C is non-singular. The paper states that M must be large enough for this §2.

Hyperparameters

NameValueWhereNotes
agents N10§4 fig. 1Erdős–Rényi communication graph
graph "connectivity"0.2§4Not defined in the text; probably the edge probability (not stated)
features d300§4 fig. 1The Sarsa run that produced the policy also uses d=300 features §4
samples M5000fig. 1Caption
primal step \gamma_10.005/\lambda_{\max}(\hat A)§4Depends on the estimated matrix
dual step \gamma_25\times10^{-3}§4
regularisation \rho0.01 and 0fig. 1Middle and right panels
horizontal axisepoch = t/M§4
sample selectionnot stated§4A1 requires a visiting rule
policy for dataSarsa, d=300 features§4Sarsa settings not stated
local reward splitrandom share per agent, average equals \mathcal R_c§4Distribution of the split not stated
baseline step sizes (PDBG, GTD2, SAGA)not stated§4
iterations, runs, seeds, error barsnot stated—
appendix: N, M, \rhoN=500; M=500 or 5000; \rho=0.01 or 0.1app. B fig. B.2 fig. B.3Ring vs Erdős–Rényi with p=1.01\log N/N fig. B.1

Results

Author-reported. Setup: the mountaincar dataset, d=300, M=5000, N=10 agents on an Erdős–Rényi graph, compared with the centralised PDBG eq. 11, GTD2 and SAGA §4. The metric is the optimality gap in MSPBE (average over agents) against epochs §4. The paper reports no numeric values, so the entries below are read from the curves fig. 1.

SettingMetricBaselineThis paperSource
N=10, M=5000, \rho=0.01MSPBE gap vs epochsSAGA, PDBG, GTD2Comparable to SAGA; faster than PDBG and GTD2§4 fig. 1
N=10, M=5000, \rho=0MSPBE gap vs epochsSAGA, PDBG, GTD2Slower than SAGA; faster than PDBG and GTD2§4 fig. 1
N=500, M=500, \rho=0.01 and 0.1MSPBE gapErdős–Rényi graphRing graph converges more slowly, more so at larger \rhoapp. B fig. B.2
N=500, M=5000, \rho=0.01 and 0.1MSPBE gapErdős–Rényi graphRing and Erdős–Rényi nearly identicalapp. B fig. B.3

The appendix repeats the convergence analysis and relates the ring-graph gap to the connectivity parameter \lambda app. B fig. B.1.

Paper vs code

No official code. The paper has no code or project link in its text. I searched GitHub for "PD-DistIAG", and for "multi-agent reinforcement learning policy evaluation primal-dual"; both returned zero repositories. Author-profile pages I checked were hoitowai (two repositories, both companion code for other papers) and Mingyi-Hong (one unrelated repository). A GitHub user search for "hoi-to wai" returned nothing. No discrepancies can be checked.

Pitfalls

  • Primal step is not given. Theorem 1 only asks for a "sufficiently small" \gamma_1. Its constants a_0,\dots,a_6 are non-negative, but the appendix proves only that some such step exists app. A §3.1. The §4 choice is one setting, and it is expressed through \lambda_{\max}(\hat A), so tune \gamma_1 on your own problem.
  • §4 step ratio is not the theorem's \beta. The stated steps give \gamma_2/\gamma_1 = \lambda_{\max}(\hat A) (computed from §4). Theorem 1 defines \beta = 8(\rho+\lambda_{\max}(\hat A^\top\hat C^{-1}\hat A))/\lambda_{\min}(\hat C) §3.1. The paper does not say the experiments used that \beta. Use the theorem's \beta if you want the stated guarantee.
  • Rate is per iteration, but the proof gives it per block. The proof bounds the error by \rho(Q)^{\lceil (t-1)/M\rceil} app. A, first lemma. Converting to one iteration (computed here, not spelled out in the paper) gives a gap of order 1/(M\max\{N^2,M^2\}), which matches the stated \sigma.
  • Sampling must satisfy A1. Independent draws with replacement can leave a sample unvisited for more than M iterations, which violates A1. The paper suggests cyclic order or shuffling. §4 does not state which sampler was used.
  • Zero initialisation. All trackers and stored gradients start at zero alg. 1. Until a sample is visited, its gradient counts as zero, so early iterations are biased. The paper gives no warm-up pass and does not analyse this transient.
  • Memory. The paper states 2Md reals per agent §3, storage. For M=5000, d=300 that is 3\times10^6 reals per agent (computed from the stated formula).
  • Communication. Each iteration needs one exchange of s_i and \theta_i with neighbours. The paper calls this costly when d is large and leaves a variant with fewer exchanges (time-varying W(t)) as future work §3.
  • Per-sample products. A_p and C_p are outer products of feature vectors eq. 6. Products with them can avoid forming d\times d matrices. The paper's O(d) per-iteration cost assumes this, but does not state it. Forming \hat C^{-1} for the error in eq. 7 is only needed for evaluation.
  • Regularisation \rho=0. Theorem 1 covers \rho \ge 0, and the only uniqueness requirement is A2. In §4 the \rho=0 case converges more slowly than SAGA §4.
  • Experiments are simulated. Per-agent rewards come from splitting one reward randomly so that the average is \mathcal R_c §4. The network is simulated §4; delays and failures are not discussed.
  • Geometric graph is an assumption. The \sigma and \gamma orders assume \lambda = 1 - c/N §3.1 app. A. The paper calls the ring graph non-geometric app. B.
  • Lemma numbers in the appendix. The text refers to the two appendix lemmas as "Lemma 1" and "Lemma 2" §3.1. Because the body's Lemma 1 numbers first in LaTeX, the printed labels are likely 2 and 3. This is inferred from source order.
  • Extension is conjectural. The paper says it believes a primal-only double-averaging method also converges linearly for a strongly convex finite sum, but gives no proof §3.1 extension.
  • Claims of novelty are the authors'. "First linear rate for decentralised convex-concave saddle-point problems with sampled observations" is the authors' claim §1. It is not checked here.

Lineage

  • Builds on: primal-dual gradient descent-ascent (the centralised PDBG template eq. 11); gradient tracking for distributed optimisation and stochastic average gradient (SAG), as cited in §3; the single-agent SAGA-type variance reduction for policy evaluation §1 §4.
  • Compared against: PDBG (centralised primal-dual gradient) §4; GTD2 §4; SAGA §4.
  • Related work: the paper cites a concurrent double-averaging method for a stochastic version of the finite-sum problem §3, extension. That method is not covered by this card.

Source and license

Adapted from “Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization” by Hoi-To Wai, Zhuoran Yang, Zhaoran Wang, Mingyi Hong (arXiv:1806.00877), used under CC BY 4.0. Changes: condensed and restructured for implementation, with tables, equations and algorithms taken from the paper and its code, each cited to its source. Not affiliated with or endorsed by the authors.