PaperlayerView exact revision on arXiv

Source-linked AI summary

Multi-Agent Fully Decentralized Value Function Learning with Linear Convergence Rates

Lucas Cassano, Kun Yuan, Ali H. Sayed

arXiv:1810.07792v5cs.LGcs.DCstat.ML

TL;DR

Policy evaluation estimates a target policy’s performance, but this work addresses doing so in a fully decentralized setting across independent environments and multi-agent settings. It introduces FDPE, a finite-data algorithm combining off-policy learning, eligibility traces, and linear function approximation. The analysis establishes linear convergence under stated conditions, and collective exploration can let agents cover the state space without each exploring it fully.

  • Problem

    The paper studies how agents can evaluate a common target policy in a fully decentralized setting across independent environment instances or a shared multi-agent environment.

    Source: §I · p. 1

  • Method

    FDPE combines off-policy learning, eligibility traces, and linear function approximation for finite-data policy evaluation without a fusion center.

    Source: B. Contribution · p. 2

  • Results

    The analysis establishes linear convergence of the iterates to the specified solution under the theorem’s assumptions and sufficiently small step-sizes.

    Source: B. Contribution · p. 2, B. Algorithm Derivation · p. 9

  • Takeaways & Limitations

    In the independent-environment setting, agents need not each explore the full state space, provided their collective data covers it.

    Source: B. Algorithm Derivation · p. 6

Abstract

from arXiv · show

This work develops a fully decentralized multi-agent algorithm for policy evaluation. The proposed scheme can be applied to two distinct scenarios. In the first scenario, a collection of agents have distinct datasets gathered following different behavior policies (none of which is required to explore the full state space) in different instances of the same environment and they all collaborate to evaluate a common target policy. The network approach allows for efficient exploration of the state space and allows all agents to converge to the optimal solution even in situations where neither agent can converge on its own without cooperation. The second scenario is that of multi-agent games, in which the state is global and rewards are local. In this scenario, agents collaborate to estimate the value function of a target team policy. The proposed algorithm combines off-policy learning, eligibility traces and linear function approximation. The proposed algorithm is of the variance-reduced kind and achieves linear convergence with $O(1)$ memory requirements. The linear convergence of the algorithm is established analytically, and simulations are used to illustrate the effectiveness of the method.

I. INTRODUCTION

The introduction frames fully decentralized policy evaluation for agents learning from separate environment instances and teams sharing a global state with local rewards. It presents a finite-data algorithm with linear convergence and a cost function whose parameters control bias and variance, and points to Appendix C for the associated proof.

I. INTRODUCTION

  • The paper addresses policy evaluation for agents with separate data and for multi-agent teams sharing a global state while keeping their rewards local.The independent-agent setting allows agents following potentially different behavior policies to cooperate; the team setting assumes a common goal.Source: §I · p. 1

A. Related Work

  • Earlier decentralized methods and converge sub-linearly and may yield biased solutions, whereas this method guarantees linear convergence and offers more control of bias; versus [18], it adds eligibility traces, O(1) memory, and no synchronized sampling requirement.The proposed algorithm can also serve as the critic in the actor-critic schemes of.Source: A. Related Work · p. 2

B. Contribution

  • FDPE combines off-policy learning, eligibility traces, and linear function approximation to achieve guaranteed linear convergence in finite-data settings, without a fusion center and with neighbor-only communication.It applies to both independent-MDP and multi-agent reinforcement-learning settings and has O(1) memory requirements.Source: B. Contribution · p. 2, A. Related Work · p. 2

C. Notation and Paper Outline

  • The paper’s outline moves from the framework to algorithm derivation and its linear-convergence theorem, then to the MARL setting and simulations.Source: C. Notation and Paper Outline · p. 3

A. Markov Decision Processes and the Value Function

B. Definition of cost function

  • The H-truncated λ-weighted MSPBE uses a finite horizon H and parameter λ to control the bias-variance trade-off in the batch setting.The paper derives expressions for this trade-off that it describes as new and specific to its batch model.Source: B. Definition of cost function · pp. 4–5
  • The proposed cost lets λ and H control bias relative to the desired solution; for finite H, bias cannot be eliminated, while larger λ reduces it but increases variance.When the true value function lies in the feature space and there is no regularization, the bias is zero regardless of λ and H.Source: B. Definition of cost function · pp. 4–5
  • The proof associated with the cost-function definition is in Appendix C.Source: B. Definition of cost function · p. 5

C. Optimization problem

With finite data, the optimization problem uses empirical estimates of its expectations. Its estimates for A, b, and C are unbiased in the general off-policy case, while trajectory lookahead limits the usable sample count.

C. Optimization problem

  • Finite data requires empirical estimates of A, b, C, and U to replace the corresponding quantities in the optimization problem.Whether U must be estimated depends on its choice: U = I needs no estimate, while U = C uses the empirical estimate of C.Source: C. Optimization problem · p. 5
  • The general off-policy estimates for A, b, and C are unbiased.Lemma 4 provides the expressions for these estimates.Source: C. Optimization problem · p. 5
  • Each estimate uses an importance-sample weight for a trajectory that starts at s_t and reaches s_{t+h} after h steps.The weight is denoted ξ_{t,t+h}.Source: C. Optimization problem · p. 5
  • With N transitions, only N−H training samples are usable because estimates of x_n and b_n look H steps ahead.Source: C. Optimization problem · pp. 5–6

III. DISTRIBUTED POLICY EVALUATION

The section formulates decentralized policy evaluation over agents with separate data and local communication, then derives FDPE from a distributed framework. Under the stated assumptions and step-size conditions, the algorithm converges linearly, with convergence speed also shaped by network connectivity.

A. Distributed Setting

  • Agents estimate a common target policy’s value function from their own behavior-policy data, communicating only with immediate neighbors over a strongly connected, symmetric, doubly-stochastic network.Source: A. Distributed Setting · p. 6

B. Algorithm Derivation

  • Collective data coverage suffices: individual behavior-policy matrices need not be positive definite, provided the aggregate matrix is positive definite.This permits agents to explore different parts of the state space.Source: B. Algorithm Derivation · p. 6
  • The derivation yields fully distributed Algorithm 1, and its iterates converge linearly to (33) when Assumption 4 and the step-size conditions hold.Source: B. Algorithm Derivation · p. 7
  • The convergence rate depends on both the saddle-point matrix spectrum and the network’s second-largest eigenvalue, with the former dominating dense networks and information diffusion limiting sparse ones.Source: B. Algorithm Derivation · p. 8
  • FDPE combines Algorithm 1 with AVRG stochastic gradients, reducing computation while retaining convergence guarantees; mini-batch size trades communication against gradient calculations.Source: B. Algorithm Derivation · p. 9
  • With Assumption 4 and sufficiently small step sizes satisfying inequality (45), FDPE iterates converge linearly to (33).Source: B. Algorithm Derivation · p. 9

IV. MULTI-AGENT REINFORCEMENT LEARNING

This section adapts the policy-evaluation cost to multi-agent games, where agents share global states and team actions but receive local rewards. The resulting estimates preserve the form needed to apply Algorithms 1 and 3 without changes.

IV. MULTI-AGENT REINFORCEMENT LEARNING

  • Algorithms 1 and 3 apply to the MARL scenario without changes after adapting the cost and estimates to team transitions.The derived cost has the same form as equation (28), and the estimates match the earlier equations with τ_K = K^-1.Source: §IV · pp. 9–10
  • Agents share global states and pursue an aggregated return, while each agent's reward depends on the team transition.The transition probabilities and individual rewards depend on all agents' actions.Source: §IV · pp. 9–10
  • The derivation uses global team states, policies, features, and sampling weights to form the empirical problem.The section says the remaining derivation follows the earlier section once these quantities are treated globally.Source: §IV · p. 10

V. SIMULATIONS

The simulations illustrate FDPE in its two proposed scenarios, with a UAV application reported separately.

V. SIMULATIONS

  • The simulations cover both FDPE scenarios; a swarm-of-UAV application is reported in.Source: §V · p. 10

A. Experiment I

Experiment I evaluates FDPE when agents explore separate regions of one state space, examining its λ-dependent bias and variance, communication-computation trade-off, and convergence against existing algorithms.

A. Experiment I

  • Nine agents divide a 15×15 grid into exploration regions, with behavior policies matching the target except at region edges.The feature representation uses 26 features, including 25 radial basis functions and a bias feature.Source: A. Experiment I · p. 10
  • The bias and bias-plus-variance curves vary with λ as approximated by Lemmas 1 and 2; the experiment's approximate optimal λ is 0.6.The paper reports that the lemma expressions accurately capture the dependence on λ.Source: A. Experiment I · p. 10
  • All tested mini-batch choices are Pareto optimal, trading communication rounds against sample-gradient calculations, so the preferred size depends on implementation.The comparison fixes λ = 0.6 and adjusts step sizes for each batch size.Source: A. Experiment I · p. 10
  • FDPE converges faster than Diffusion GTD2 and ALG2 and reaches a lower MSD error level, though the advantage is not very significant under high variance.The paper says the advantages in convergence speed and minimizer become more pronounced as more data become available.Source: A. Experiment I · p. 10

B. Experiment II

Experiment II tests FDPE on randomly generated multi-agent MDPs and compares its convergence with three algorithms. FDPE converges faster and reaches a substantially lower MSD minimizer in this on-policy setting.

B. Experiment II

  • The test uses a random network of 15 agents and randomly generated MDPs with 50 states and 10 actions.The transition model is sparse, rewards are occasional, and the target policy is sampled subject to Assumption 1.Source: B. Experiment II · p. 11
  • The bias-variance analysis indicates an approximate preferred λ of 0.8 for this experiment.The curves were obtained in the same manner as in Experiment I.Source: B. Experiment II · p. 11
  • FDPE's MSD minimizer is approximately one order of magnitude smaller than those of the other algorithms.The experiment also reports faster convergence to the empirical minimizer.Source: B. Experiment II · p. 12, Figure 2 · p. 12
  • FDPE, Diffusion GTD2, and ALG2 show performance consistent with the theory, while PD-distIAG converges linearly but more slowly than FDPE.PD-distIAG is included in the on-policy comparison because it only works in that scenario.Source: B. Experiment II · pp. 11–12

APPENDIX A PROOF OF LEMMA 1

These appendices derive the parameter bias and variance bounds, express the estimators through trajectory samples, and establish uniqueness of a consensus fixed point.

APPENDIX A PROOF OF LEMMA 1

  • The Lemma 1 proof derives a representation of θo and analyzes its bias relative to θ⋆, separating the regularization term’s effect.When vπ = Πvπ, the supplied passage states that ˇθ−θ⋆=0.Source: Appendix A · pp. 12–13

APPENDIX B PROOF OF LEMMA 2

  • The Lemma 2 variance analysis assumes data substantially exceeds the Markov-chain mixing rate, making terms from different times approximately independent.The passage relates this data condition to accurately estimating the policy’s effect on every state.Source: Appendix B · p. 13

APPENDIX C PROOF LEMMA 3

  • The Lemma 3 proof writes A, b, and C as expectations using their definitions and expands the matrix operations.The supplied passage describes this proof step but does not state the lemma’s conclusion.Source: Appendix C · p. 14

APPENDIX D PROOF OF LEMMA 4

  • Lemma 4 estimates A from a single H-step trajectory using importance-sampling weights, while the sample estimate of C requires no importance sampling.The passage says b is estimated by similar steps and gives its sample expression only incompletely.Source: Appendix D · p. 14

APPENDIX E PROOF OF LEMMA 5

  • The Lemma 5 proof establishes a unique ζo satisfying the consensus constraints and a unique Yo fixed point in the range space of V.It derives ζo = 1K⊗[bθoT bωoT]T and concludes uniqueness of Yo by contradiction.Source: Appendix E · pp. 14–15

APPENDIX F PROOF OF LEMMA 6

These proofs simplify the transformed recursions, establish bounds on their components, and rewrite the empirical algorithm as a network recursion.

APPENDIX F PROOF OF LEMMA 6

  • The Lemma 6 proof uses IT V = 0 to show that the recursion’s variables ˉxi and bxi are independent of ˜x0, allowing ˜xi to be disregarded.This yields the desired recursion after the matrix decomposition.Source: Appendix F · p. 15

APPENDIX G PROOF OF LEMMA 7

  • The Lemma 7 proof bounds the top and bottom recursions using Jensen’s and Cauchy–Schwarz inequalities and writes the resulting bounds in matrix form.The supplied proof passage gives a step-size condition for the top recursion, µ < K/ρ(ΛG).Source: Appendix G · pp. 15–16

I. PROOF OF CONVERGENCE

  • The convergence proof rewrites the empirical FDPE equations as a unique network recursion, with Ak,σe denoting an agent’s sample estimate or mini-batch empirical average.Which estimate is used depends on whether mini-batches are being used.Source: §I · p. 17

we further clarify that the notation Ak,σe

The supplement clarifies the empirical-iteration notation and develops bounds used to prove linear convergence of FDPE under step-size conditions.

we further clarify that the notation Ak,σe

  • The notation clarification distinguishes sample estimates from empirical averages and explains that convergence analysis focuses on updates after the finite initial updates.The supplied passage also defines error quantities and gradient noise for the analysis.Source: we further clarify that the notation… · pp. 17–18

r V) ¯LGHu

  • The analysis bounds transformed recursion components under step-size conditions, then addresses the remaining difference-norm bounds needed to establish convergence.Lemma 3 gives an inequality when µ ≤ K/ρ(ΛG); Lemma 4 supplies a further bound when µ < µ0.Source: r V) ¯LGHu · pp. 18–19

Theorem 1. If the step-size µ is small enough then the iterates

  • With a sufficiently small step size, FDPE iterates converge linearly to the saddle point of problem (42) for every agent.The theorem’s rate bound includes ρ(I−µK−1ΛG) plus an O(µ2) term.Source: Theorem 1. If the step-size µ is small… · p. 19

B. Proof of Lemma 2

These proofs establish the coordinate transformation and component bounds used in the convergence analysis, including bounds on gradient-noise terms.

B. Proof of Lemma 2

  • The Lemma 2 proof applies the document’s matrix decomposition and new coordinates to transform the recursion.The passage says expanding H−1P yields the desired relation.Source: B. Proof of Lemma 2 · p. 20

C. Proof of Lemma 3

  • The Lemma 3 proof bounds the top recursion using Jensen’s and Schwarz inequalities, with µ < K/ρ(ΛG) allowing a contraction factor below one.The passage identifies this as the top inequality of (S.12).Source: C. Proof of Lemma 3 · pp. 21–22

r V) ¯LGHu

  • The proof repeats the bounding procedure for the bottom recursion, completing the two inequalities of (S.12).The cited passage states that the resulting inequality is the bottom bound.Source: C. Proof of Lemma 3 · p. 22, r V) ¯LGHu · p. 22

D. Proof of Lemma 5

  • The Lemma 5 proof proceeds by bounding terms associated with gradient noise and analyzing them individually.The supplied passages describe the bounding steps but do not provide the final bound’s values.Source: D. Proof of Lemma 5 · pp. 22–23

where in (a) we used H¨older’s inequality. Now we need an equation relating

E. Proof Lemma 4

  • The Lemma 4 proof begins by iterating equation (S.12) to obtain a bound.The supplied passage does not state the resulting bound.Source: E. Proof Lemma 4 · p. 24

1 M2ze

The proof bounds intermediate error terms using a sufficiently small step size, then combines and sums the resulting recursions to obtain an epoch-level inequality.

1 M2ze

  • A sufficiently small step size makes the imposed conditions hold, yielding entry-wise matrix inequalities.The passage notes that the constants a1 through a8 are strictly positive.Source: §1 · p. 25

Using the above equation we can write the following expression for ˇxe

Similarly, as we did before, we get

Summing across all ze

  • Summing the error recursions across an epoch under a step-size constraint yields a matrix-form inequality and completes the proof.The section also derives and rewrites recursions for additional error terms before combining them.Source: Summing across all ze · pp. 27–30

G. Proof Theorem 1

The proof establishes linear convergence by showing that the maximum of three coefficients is below one for a sufficiently small step size. It also expresses a convergence-rate bound using the spectral quantities ρ(I−µK^-1ΛG) and λ2(¯L).

G. Proof Theorem 1

  • The proof introduces a positive constant ϵ and coefficients b1, b2, and b3, then aims to show their maximum is below one.The coefficients are expressed using the chosen ϵ and earlier bounds.Source: G. Proof Theorem 1 · pp. 30–31
  • For a sufficiently small step size, b1, b2, and b3 are all below one, which implies linear convergence.The proof shows b1 and b3 are below one for small enough µ, and uses limµ→0 b2=λ2(¯L) to establish b2<1.Source: G. Proof Theorem 1 · pp. 30–31
  • The convergence-rate bound uses ρ(I−µK^-1ΛG) with an O(µ^2) term and λ2(¯L) with an O(µ) term.Source: G. Proof Theorem 1 · p. 31
Loading 1810.07792v5…