Finite-Sample Analysis For Decentralized Batch Multi-Agent Reinforcement Learning With Networked Agents

Motivation

• Decentralized cooperative MARL can involve heterogeneous rewards and no central controller, but prior theoretical guarantees were asymptotic rather than finite-sample.Decentralized protocols are motivated by scalability, privacy preservation, and computational efficiency.Source: §1 · p. 2
• The paper studies a zero-sum setting in which two teams of decentralized agents compete, extending beyond the usual two-player competitive MARL model.The introduction notes that the two-team setting can support non-asymptotic analysis of mixed MARL.Source: §1 · p. 2

Main Contribution

• The paper proposes decentralized batch MARL algorithms for cooperative and competitive settings and provides finite-sample error bounds for their estimated action-value functions.The bounds characterize how function-class complexity, samples per iteration, and iteration count affect statistical accuracy; the authors describe this as the first such analysis for batch MARL.Source: §1 · p. 3

Related Work

• Prior batch-MARL analysis addressed error propagation but not statistical rates or the computational complexity of fitting, which arises explicitly in decentralized algorithms.Single-agent batch analyses cited here assumed exact fitting at each iteration.Source: §1 · p. 4
• Earlier finite-sample MARL-related work covered PAC analyses for Dec-POMDPs, but often relied on centralized planning, model access, special structure, or small tabular settings.The paper positions its function-approximation batch analysis for large state-action spaces as a contrast.Source: §1 · p. 4

2.1 Decentralized Cooperative MARL

• In the cooperative setting, agents share an environment and aim to maximize the global average of their cumulative discounted rewards.There is no central controller; agents exchange information over a possibly time-varying communication network.Source: §2.1 · pp. 5–6
• The cooperative model assumes globally observable states and joint actions, locally observed rewards, and conditionally independent action choices by agents given the current state.Each agent chooses actions according to its own policy.Source: §2.1 · p. 5
• The cooperative action-value function is defined for a joint policy, with bounded values and Bellman operators tied to the globally averaged reward.The global Q-function is the unique fixed point of its policy Bellman operator.Source: §2.1 · p. 6

2.2 Decentralized Two-Team Competitive MARL

• The competitive formulation has two teams that collaborate internally over communication networks and compete in a zero-sum Markov game.The instantaneous rewards across the two teams sum to zero, and rewards are observed locally.Source: §2.2 · pp. 6–7
• Each team optimizes its joint policy over its agents; under the zero-sum assumption, one team maximizes and the other minimizes the globally averaged return.The formulation uses team-joint policies for the minimax objective.Source: §2.2 · pp. 7–8
• Restricting team policies to independent per-agent policies can make the minimax value fail to exist, even for matrix games.The paper leaves that restricted-policy setting for future work and notes that its Q-learning approach can recover team-joint equilibrium policies without the independence restriction.Source: §2.2 · p. 8
• The competitive model defines equilibrium policies with respect to the action-value function, with the opponent team playing a best response.The game’s max-min matrix problem may not admit pure-strategy solutions.Source: §2.2 · pp. 8–9

3.1 Decentralized Cooperative Batch MARL

• Cooperative agents use trajectory data and local rewards to estimate a globally averaged Q-function, then fit updated value estimates from local targets.Each agent maintains its own estimate and calculates target data using its locally available reward.Source: §3.1 · p. 9
• Finite decentralized optimization may leave agents with different estimates, and these discrepancies can propagate into targets in later iterations.Agents solve a shared least-squares fitting problem using distributed local target data; the resulting local estimates need not reach exact consensus.Source: §3.1 · pp. 9–10
• The cooperative algorithm returns an average of agents’ local greedy policies based on their final value estimates.The estimates are produced after K iterations.Source: §3.1 · pp. 9–10
• For parametric cooperative models, DIGing is one option for distributed fitting; linear classes can yield strongly convex objectives under mild conditions, unlike general nonlinear classes.The mismatch from the global minimizer is difficult to quantify for general nonlinear decentralized optimization.Source: §3.1 · p. 10

3.2 Two-team Competitive Batch MARL

• In the two-team zero-sum setting, Team 1 agents use local rewards to update estimates of their team’s globally averaged minimax Q-function through decentralized least-squares fitting.The exposition focuses on Team 1’s update and analysis; Team 2 is treated similarly.Source: §3.2 · p. 11
• Finite iterations may leave Team 1 agents without consensus, and the final vector of estimates can differ from the exact minimizer.The algorithm’s final output is an average greedy policy based on the team’s estimate vector.Source: §3.2 · p. 12

4 Theoretical Results

• The analysis assumes finite function-class pseudo-dimension, stationary exponentially β-mixing trajectory data, concentrability, and bounded one-step decentralized computation error.The computation error can arise from finitely many optimization iterations and nonconvexity of the fitting objective; the sample-path behavior policy need not be known to generate the trajectory.Source: §4 · pp. 12–14

4.1 Decentralized Cooperative Batch MARL

• The cooperative policy error bound separates approximation, estimation, and decentralized computation errors, with estimation error decreasing as sample size T grows.The bound is high-probability under Assumptions 4.1–4.4; its estimation term has an additional O(N log(A)) dependence and effective dimension (N + 1)VH+ compared with single-agent results.Source: §4.1 · pp. 14, 16

4.2 Two-team Competitive Batch MARL

• The competitive policy error bound likewise comprises approximation, estimation, and decentralized computation errors, with estimation dependence N log(AB) and no dependence on Team 2’s agent count M.The effective dimension remains (N + 1)VH+; the computation-error term characterizes decentralized execution and would disappear with centralized controllers.Source: §4.2 · pp. 16, 18

4.3 Using Linear Function Approximation

• With linear function approximation, full-rank feature covariance makes the least-squares problems strongly convex, enabling DIGing’s geometric convergence over time-varying networks.The consensus matrices are required to satisfy decentralized, doubly stochastic, and joint-spectrum properties.Source: §4.3 · pp. 18–19
• For Algorithm 1, K and L scale linearly with logarithmic accuracy and discount-related terms, while T is polynomial in accuracy, discount, reward, confidence, β, and N log(A).The corollary assumes Assumptions 4.1–4.4 and 4.11–4.12 and uses Algorithm 2 for decentralized fitting.Source: §4.3 · p. 19
• For Algorithm 3’s Team 1 output policy, the same bounds hold over S × A × B, with T polynomial in N log(AB) instead of N log(A).The guarantee is stated for any fixed distribution over S × A × B and holds with probability at least 1−δ.Source: §4.3 · p. 19
• With mild assumptions and small inherent approximation error, Algorithms 1 and 3 need finitely many samples and iterations, scaling at most polynomially with problem parameters, for arbitrarily small Q-value errors.Corollary 4.13 follows from Theorems 4.5 and 4.8.Source: §4.3 · pp. 19–20
• Without the full-rank condition, the fitting problems are convex, and proximal-gradient consensus can achieve an O(1/l) convergence rate over time-varying networks.The paper omits further discussion of decentralized optimization algorithms as beyond its scope.Source: §4.3 · p. 20

5.1 Proof of Theorem 4.6

• For Theorem 4.6, the proof separates finite-sample fitting error from decentralized-optimization error and derives one-step and multi-step bounds on their propagation through Q-function estimates.The one-step recursion bounds Q* − eQ_{k+1} using Q* − eQ_k and the two error terms; Lemma 5.1 extends this propagation across iterations.Source: §5.1 · pp. 20–21
• The proof then bounds output-policy suboptimality using estimator error and decentralized-optimization accuracy, which vanishes with more updates when the least-squares problem is convex.It first relates Q* − Q^{π_k} to the estimator error and then applies the multi-step propagation bounds to the final iterate.Source: §5.1 · pp. 21–23
• The final Theorem 4.6 argument converts a pointwise error bound into a weighted-norm bound, using bounded Q-functions, concentrability coefficients, and Assumption 4.4 to control computation error.Lemma 5.2 bounds the one-step decentralized-computation error, yielding the bound needed to conclude Theorem 4.6.Source: §5.1 · pp. 23–26

5.2 Proof of Theorem 4.7

• For Theorem 4.7, the proof controls uniform empirical-to-population loss deviations with covering-number bounds and concentration for β-mixing data.The argument uses ghost samples and β-mixing tail bounds, alongside empirical covering-number lemmas, to establish the required control.Source: §5.2 · pp. 26–28
• Theorem 4.7’s proof concludes after establishing the desired bound.Source: §5.2 · p. 29

5.3 Proof of Theorem 4.9

• For Algorithm 3, the output policy’s Team 1 suboptimality, Q*−Qπk, is separated into an approximation error from the first fitting problem and a computational error from finite decentralized updates.Source: §5.3 · pp. 29–30

5.4 Proof of Theorem 4.10

• Theorem 4.10’s proof uses empirical covering-number bounds under Assumption 4.1 to control the probability bound and complete the sample-size argument.It derives a bound of the form ΛT = K1 + K2 · N, with constants depending on the listed parameters.Source: §5.4 · pp. 34–35

5.5 Proof of Corollary 4.13

• K is linear in log(1/ϵ), log[1/(1 −γ)], and log(Qmax), while L is linear in log(1/ϵ) and log[γ/(1 −γ)].T is polynomial in 1/ϵ, γ/(1 −γ), 1/eRmax, log(1/δ), log(β), and N log(A); for the competitive bound, N log(A) changes to N log(AB).Source: §5.5 · pp. 35–36

6.1 Simulation Setup

• The simulation uses a randomly generated zero-sum game with 5 and 9 agents, 65,536 joint actions, and 10 states.Transition probabilities are sampled and normalized, with 10^-4 added to each element; data are sampled after mixing to satisfy the stated mixing assumption.Source: §6.1 · pp. 36–37

6.2 Results

• At k = 1, 50, and 100, inner-loop iterates converge toward the unique fitting solution, with agents eventually reaching almost-consensus.This supports controlling one-step decentralized computation error by using a sufficiently large L.Source: Figure 1 · p. 37, §6.2 · p. 38

6.1 Simulation Setup

• Q-functions use linear features, while time-varying consensus matrices are generated from random graphs and the discount factor is set to 0.9.The feature dimension is chosen much smaller than the 655,360 state-joint-action combinations.Source: §6.1 · p. 37

6.2 Results

• Increasing T from 100 to 10,000 lowers final error; increasing L reduces computation error with diminishing returns, while larger d reduces approximation error.The gains from L = 10 to 100 exceed those from 100 to 1,000; further increasing L to 10,000 has almost no effect.Source: Figure 2 · p. 38, §6.2 · pp. 38–39
• Figure 2 compares outer-loop convergence across choices of T, L, and feature dimension d using 20 independent trials.Source: Figure 2 · p. 38

• The cooperative setting covers heterogeneous agents maximizing globally averaged return without a central controller, while the competitive setting uses two teams in a zero-sum Markov game.These settings include common-reward cooperative MARL and conventional two-player zero-sum games as special cases.Source: §7 · p. 39
• For both settings, decentralized optimization solves each fitted-Q iteration’s fitting problem, and the paper bounds output action-values using finitely many samples from a single RL trajectory.With linear function approximation, it also bounds performance after finitely many decentralized computation iterations.Source: §7 · p. 39
• The authors describe these as the first finite-sample analyses for batch MARL in cooperative or competitive settings, and suggest extending them to general-sum games and sharpening the bounds.Source: §7 · p. 39

• A process is β-mixing when its β_m coefficients tend to zero; exponential mixing further bounds them by β · exp(−gm^ζ).Source: A Definitions · p. 44
• Concentrability coefficients measure the supremum density ratio of policy-generated state-action distributions to a reference distribution, for multi-agent MDPs and two-team zero-sum games.Source: A Definitions · p. 45
• An empirical covering number is the smallest number of radius-ϵ discs covering a function class under the empirical ℓ1 pseudometric.For real-valued functions, the range distance is absolute difference.Source: A Definitions · p. 45
• A pseudometric satisfies metric properties except distinguishability, which it does not require.Source: A Definitions · p. 45

B Auxiliary Results

• A full-column-rank set of d feature vectors makes their averaged rank-1 matrix full rank; with rich enough data, this implies MMDP is full rank and also applies to MMG.The text says this argument justifies the rationale behind Assumption 4.11.Source: B Auxiliary Results · p. 46
• The appendix states a bound on empirical covering numbers for function classes using pseudo-dimension.It attributes the proposition to Haussler (1995), Corollary 3.Source: B Auxiliary Results · p. 46
• Under Assumption 4.12, DIGing converges geometrically to the unique solution of (B.1) at rate O(λ^l).The local objectives are strongly convex with Lipschitz continuous gradients, and λ lies in [0,1).Source: B Auxiliary Results · pp. 46–47

B.1 Proof of Lemma 5.4

• For N = 1, maxima over actions of functions from an ε′-cover of H(D_y) form a cover of H∨₁.The proof selects an approximating cover element for each Q₁.Source: §B.1 · p. 47
• The proof extends the covering argument to H∨_N, whose functions are averages of functions from N copies of H∨.The displayed passage gives a covering-number relation involving N₁(ε/A, H, D_y).Source: §B.1 · p. 47
• Proposition B.2 bounds N₁(ε/A, H, D_y) using the pseudo-dimension of H.The proof cites Haussler (1995), Corollary 3, for this step.Source: §B.1 · p. 47

B.2 Proof of Lemma 5.9

• The proof follows the approach used for Lemma 5.4 and starts from an ε′-cover of H(D_y).It states a covering claim for the class under consideration.Source: §B.2 · p. 47
• For any Q₁,₁ in H, the proof selects an element from the ε′-cover.The passage introduces the selected index l′ but does not state the resulting bound in full.Source: §B.2 · pp. 47–48
• The proof introduces a strategy pair associated with y_t and then invokes Proposition B.2 for a further bound.The supplied passage does not state the bound itself.Source: §B.2 · p. 48