PaperlayerView exact revision on arXiv

Source-linked AI summary

Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents

Kaiqing Zhang, Zhuoran Yang, Han Liu, Tong Zhang, Tamer Başar

arXiv:1802.08757v2cs.LGcs.AIcs.MAmath.OCstat.ML

TL;DR

The paper addresses fully decentralized MARL when agents have local rewards and communicate over time-varying networks without a central controller. It develops two decentralized actor-critic algorithms with function approximation, using consensus for critic updates, and proves convergence under linear value-function approximation.

  • Problem

    Fully decentralized MARL must coordinate agents with locally known, potentially task-specific rewards through neighbor communication while maximizing globally averaged return.

  • Method

    The paper proposes two decentralized actor-critic algorithms with function approximation, performing individual actor updates and consensus-based critic updates over the communication network.

  • Results

    The proposed algorithms are shown to converge under linear function approximation, with convergence theorems provided for both algorithms.

  • Takeaways & Limitations

    The framework provides a fully decentralized, incremental approach for large-scale networked MARL with provable convergence guarantees in the linear approximation setting.

  • Takeaways & Limitations

    The convergence analysis assumes conditionally independent local action choices and uses projection for stabilizing theoretical stochastic-approximation analysis.

Abstract

from arXiv · show

We consider the problem of \emph{fully decentralized} multi-agent reinforcement learning (MARL), where the agents are located at the nodes of a time-varying communication network. Specifically, we assume that the reward functions of the agents might correspond to different tasks, and are only known to the corresponding agent. Moreover, each agent makes individual decisions based on both the information observed locally and the messages received from its neighbors over the network. Within this setting, the collective goal of the agents is to maximize the globally averaged return over the network through exchanging information with their neighbors. To this end, we propose two decentralized actor-critic algorithms with function approximation, which are applicable to large-scale MARL problems where both the number of states and the number of agents are massively large. Under the decentralized structure, the actor step is performed individually by each agent with no need to infer the policies of others. For the critic step, we propose a consensus update via communication over the network. Our algorithms are fully incremental and can be implemented in an online fashion. Convergence analyses of the algorithms are provided when the value functions are approximated within the class of linear functions. Extensive simulation results with both linear and nonlinear function approximations are presented to validate the proposed algorithms. Our work appears to be the first study of fully decentralized MARL algorithms for networked agents with function approximation, with provable convergence guarantees.

1 Introduction

The paper formulates fully decentralized MARL for agents with local rewards and decisions connected through time-varying communication networks. It proposes function-approximation actor-critic methods with convergence guarantees under linear approximation.

  • Agents collaboratively maximize globally averaged returns while observing only local rewards and exchanging messages over a time-varying network.
  • Centralized control can reduce MARL to a classical MDP but may be unavailable, costly, or communication-intensive in real-world systems.
  • The proposed decentralized actor-critic algorithms use function approximation to address large state-action spaces and many agents.
  • The paper establishes convergence guarantees for the proposed algorithms with linear function approximation.
  • Related Work: The work positions its algorithms within actor-critic MARL and distinguishes them from prior collaborative methods that often assume identical rewards or centralized information.

2 Background

The paper reviews MDPs and actor-critic learning before defining networked multi-agent MDPs with locally observed rewards and decentralized policies. Its objective is to optimize network-wide average return using local information and communication.

  • 2.1 Markov Decision Process and Actor-critic Algorithm: An MDP models state transitions and rewards under a policy, with the objective of maximizing expected long-term average reward.
  • 2.1 Markov Decision Process and Actor-critic Algorithm: Function approximation represents value functions and policies with parameterized classes when state and action spaces are large.
  • 2.1 Markov Decision Process and Actor-critic Algorithm: Actor-critic learning uses a faster critic step to estimate value functions and a slower actor step to improve policy parameters along a gradient direction.
  • 2.2 Multi-Agent Reinforcement Learning: A networked multi-agent MDP consists of a shared state space, individual action spaces, local reward functions, transition dynamics, and a time-varying communication network.
  • 2.2 Multi-Agent Reinforcement Learning: The fully decentralized setting requires each agent to receive rewards and execute actions locally while sharing information with neighbors.
  • 2.2 Multi-Agent Reinforcement Learning: The joint policy factorizes into conditionally independent local policies, while agents jointly maximize globally averaged long-term return using local information.

3 Multi-Agent Actor-Critic with Networked Agents

The section derives a decentralized policy-gradient foundation and develops two actor-critic algorithms whose critics exchange parameter estimates over time-varying networks. Function approximation, consensus updates, and online implementation address large-scale MARL while preserving decentralized information constraints.

  • Policy-gradient foundation: The MARL policy-gradient theorem expresses each agent’s gradient using its local score function and an unbiased global action-value or advantage estimate.Local information alone cannot generally estimate these global quantities because they depend on all agents’ rewards.
  • Decentralized actor-critic design: Each agent performs the actor update individually, while critic updates combine local temporal-difference information with neighboring parameter estimates through consensus.The consensus step uses a time-varying weight matrix for transmitted messages.
  • Convergence analysis: The update analysis uses stochastic-approximation machinery because the diffusion-like direction is not a stochastic gradient of a well-defined objective and diminishing stepsizes are used.These differences mean distributed-optimization proof techniques cited for related diffusion updates do not apply directly.
  • State-value critic: A second algorithm replaces the action-value update’s next-action requirement with the transition sample (s_t,a_t,s_t+1), using state-value TD-error to estimate advantage.The state-value and long-term-return estimates are represented with parametrized functions and shared local parameters.
  • Action-value critic: The action-value algorithm estimates the globally averaged reward and action-value function without directly transmitting other agents’ rewards or policies.The consensual reward estimate cannot recover individual reward functions, preserving reward and policy privacy.
  • Scalability and implementation: The algorithms support online operation with per-agent memory O(N + L + M + m_i), reducing storage relative to tabular representations whose joint-action dimension grows exponentially with agent count.The tabular comparison requires a Q-table over |S|·|A|×|S|·|A|, with |A| growing exponentially in N.

4 Theoretical Results

Under bounded-reward, communication, projection, and linear-approximation assumptions, both decentralized actor-critic algorithms have convergence guarantees. The critic reaches globally averaged value estimates through consensus, while the actor approaches stable equilibria near local optima under stated approximation conditions.

  • Assumptions: The analysis assumes bounded rewards, local projection onto compact parameter sets, and communication matrices respecting the time-varying graph.The projection set is assumed to contain at least one local minimum, and projection is described as an analysis device for stabilizing stochastic approximation.
  • Assumptions: Consensus weights are random nonnegative matrices with stochasticity, positive-weight lower bounds, graph compatibility, and conditional independence requirements.Metropolis weights use only local neighbor information; pairwise gossip, broadcast gossip, and network dropouts are also cited as compatible choices.
  • Algorithm 1: The two-time-scale analysis first establishes critic convergence for a fixed joint policy, then analyzes policy-parameter convergence after critic convergence.This separates the faster critic update from the slower actor update using stochastic approximation.
  • Algorithm 1: With linear action-value approximation, the critic converges almost surely for every agent to the globally averaged action-value approximation under a fixed policy.The limiting solution corresponds to the TD(0) limit for the approximated action-value function and minimizes the mean square projected Bellman error.
  • Algorithm 1: The Algorithm 1 policy parameters converge almost surely to asymptotically stable equilibria, approaching a local optimum when action-value approximation error is sufficiently small.The theorem is stated under Assumptions 2.2 and 4.1–4.5; the local-optimum conclusion is qualified by the approximation error.
  • Algorithm 2: For Algorithm 2, the critic converges almost surely to globally averaged value quantities, and its policy parameters converge to stable equilibria that are close to a local optimum when value-estimation errors are small.The limiting state-value component matches the TD(0) limit as if all agents observed every reward, while the auxiliary component is the unique minimizer of the stated problem.

5 Proofs of the Main Results

The proofs establish boundedness and consensus of the critic iterates, then use two-time-scale analysis to derive convergence of the actor and critic parameters under linear function approximation.

  • Boundedness: The convergence proof first establishes almost-sure boundedness of the local auxiliary and critic sequences under the stated assumptions.The boundedness results support the subsequent stochastic-approximation arguments.
  • Two-time-scale analysis: For the faster critic timescale, the policy parameter is held fixed so the critic converges to a policy-dependent limit that simplifies the slower actor analysis.This is the two-time-scale stochastic-approximation setup used in the convergence proof.
  • Consensus: The critic iteration is decomposed into consensus and disagreement components, with the disagreement sequence converging almost surely to zero.The proof separately analyzes the consensus vector and the disagreement vector.
  • Consensus: The consensus component converges to an equilibrium whose averaged auxiliary variable equals J(θ) and whose averaged critic parameter equals ωθ.This combines the consensus-limit argument with the almost-sure boundedness established earlier.
  • Actor convergence: The actor updates converge almost surely to asymptotically stable equilibria of the associated ordinary differential equation under the listed assumptions.The proof applies the Kushner-Clark lemma after establishing the required boundedness and continuity conditions.

6 Numerical Results

The proposed decentralized actor-critic algorithms are evaluated with linear and neural-network function approximation. In both settings, decentralized methods approach centralized performance, with slower convergence attributed to information diffusion delays.

  • Experimental Setup: The experiments evaluate fully decentralized actor-critic algorithms with both linear and nonlinear function approximation.The nonlinear evaluation uses neural networks in a Cooperative Navigation environment.
  • Linear Function Approximation: N = 20 agents use binary actions and |S| = 20 states in the linear-function-approximation experiment.The joint action space has cardinality 2^20.
  • Linear Function Approximation: Both decentralized algorithms converge to the globally long-term averaged return achieved by their centralized counterparts.Consensus of the approximated value functions occurs faster than actor-critic convergence, while decentralized value convergence is slower than centralized convergence.
  • Linear Function Approximation: Both decentralized algorithms converge to policies similar to their centralized counterparts, with local-information policies almost as good as policies using full system information.The comparison uses probability distributions at randomly selected states.
  • Nonlinear Function Approximation: In Cooperative Navigation, N = 10 agents move among L = 10 landmarks using five movement actions and network communication.Agents receive rewards based on distance to their target landmarks, with an additional collision penalty.
  • Nonlinear Function Approximation: Both decentralized algorithms successfully converge with neural-network approximators and achieve globally averaged returns close to centralized counterparts, though slightly more slowly.State-value TD-error methods appear superior to action-value-function methods in this experiment.

7 Conclusions

The paper addresses fully decentralized MARL over networked agents and proposes function-approximation actor-critic algorithms for large-scale settings. It provides linear-approximation convergence analysis while identifying competitive agents and continuous actions as future extensions.

  • The paper studies fully decentralized MARL in which agents exchange information over networks while pursuing optimal network-wide averaged return.
  • Two decentralized actor-critic algorithms with function approximation target large-scale MARL problems with numerous agents and massive state-action spaces.
  • The paper provides convergence analysis for the proposed algorithms when value functions use linear function approximation.
  • Future work includes extending the algorithms and analyses to competitive agents and continuous action spaces.

A Proof for the Stability of Consensus Updates

This appendix establishes stability for consensus-based stochastic-approximation updates under stated network, regularity, noise, and dynamical assumptions. It then connects the general stability theorem to the critic updates used by both algorithms.

  • General Stability Result: The proof studies consensus updates for N agents whose state vectors are coupled through stochastic communication updates.The agents’ update variables are assembled into a joint vector in R^(dN).
  • Assumptions: The analysis assumes suitable consensus matrices, Lipschitz update maps, martingale-difference noise, and additional boundedness conditions.These conditions are collected in Assumption A.1.
  • ODE Stability Condition: The stability condition is formulated through an averaged ODE in the consensus subspace with a globally asymptotically stable attractor.The condition requires the attractor to lie within a ball of radius less than N^-1/2.
  • Stability Theorem: Under Assumption A.1, the sequence generated by the consensus update is bounded almost surely.

A.1 Proof of Theorem A.2

The proof of Theorem A.2 uses a rescaled, linearly interpolated trajectory to establish boundedness, control noise, and show convergence toward the consensus subspace. These results yield almost-sure stability of the update sequence.

  • Rescaled Trajectory: The proof constructs a continuous-time interpolation and rescales it by the maximum norm over successive time blocks.The rescaled trajectory is defined so its norm at each block start is at most one.
  • Moment Bounds: The rescaled trajectory has uniformly bounded second moments under Assumption A.1.Lemma A.4 states that sup_t E[||x̂(t)||^2] is finite.
  • Noise Control: The martingale-noise accumulation converges almost surely, supporting control of stochastic terms in the interpolated update.
  • Boundedness: The trajectory is almost surely bounded, using row-stochasticity, Lipschitz continuity, noise conditions, and a discrete-time Grönwall inequality.
  • Consensus Convergence: The disagreement from the consensus subspace vanishes asymptotically, so all agents’ rescaled trajectories approach a common limiting trajectory.Lemma A.7 formalizes convergence of x̂(t) − 1⊗y_n(t) over successive time intervals.
  • Final Stability Argument: If the original trajectory attempts to leave the unit ball, the rescaled dynamics return it at an exponential rate, completing the stability argument.

A.2 Proof of Lemma 5.1

The proof verifies the stochastic-approximation conditions for the critic step and concludes convergence by showing that the limiting ODE has a globally asymptotically stable origin.

  • The critic recursion is analyzed by verifying the conditions required for Theorem A.2.The proof begins from the critic step in (3.7) and checks boundedness, growth, and limiting-dynamics conditions.
  • The Markov chain induced by policy πθ is assumed irreducible and aperiodic, supporting the required stochastic-approximation analysis.
  • The iterates µt are almost surely bounded, and the finite-state Markov chain yields a linear-growth bound for the drift difference.Specifically, the proof establishes a bound proportional to 1 + ∥ωt∥2 over sets where µt remains bounded.
  • Uniform boundedness of rt+1 and ∥φt∥ verifies the conditional second-moment bound for Mt+1.
  • The limiting ODE has the origin as its globally asymptotically stable attractor, so Theorem A.2 completes the proof.

A.3 Proof of Lemma 5.4

The proof of Lemma 5.4 puts the critic updates into compact form, verifies the stochastic-approximation assumptions, and invokes global asymptotic stability of the limiting ODE.

  • The critic updates from (3.12), (3.13), and (3.16) are written in a compact form for analysis.
  • The resulting recursion satisfies conditions (a.3) and (a.4) in Assumption A.1, and its limiting drift h∞(y) exists.
  • The limiting ODE has the origin as its globally asymptotically stable attractor, which completes the proof.

B.1 A Basic Result of Stochastic Approximation

This section states stochastic-approximation results linking Markov-driven recursions to limiting ODEs, with convergence guaranteed under boundedness and global stability conditions.

  • The stochastic-approximation iteration uses positive stepsizes and a Markov chain on a finite state set.
  • Assumption B.1 requires Lipschitz drift, an irreducible Markov chain with stationary distribution π, martingale-difference noise, and vanishing bounded perturbations.
  • The asymptotic behavior of the recursion is related to the solution of an associated ODE.
  • Under Assumption B.1 and almost-sure boundedness of xt, Theorem B.2 gives xt → x∗ when the ODE has a unique globally asymptotically stable equilibrium x∗.
  • Theorem B.3 additionally applies when the limiting drift exists uniformly on compact sets and the ODE has the origin as its unique globally asymptotically stable equilibrium.

B.2 Kushner-Clark Lemma

The Kushner-Clark framework gives almost-sure convergence to asymptotically stable ODE equilibria, while the paper situates its networked MARL model against broader multi-agent and collaborative-MARL settings.

  • B.2 Kushner-Clark Lemma: The Kushner-Clark Lemma states that the recursion converges almost surely to a compact set of asymptotically stable equilibria of its associated ODE.
  • B.2 Kushner-Clark Lemma: The projected recursion uses an operator Γ onto a compact set X, with a corresponding projected vector field and associated ODE.
  • B.2 Kushner-Clark Lemma: Assumption B.4 requires continuity of h, bounded perturbations that vanish almost surely, diminishing stepsizes, and a noise condition on ξt.
  • Related work: The networked multi-agent framework is connected to applications including vehicle formation control, robot navigation, energy-network load management, and sensor-network flocking.
  • Related work: Unlike canonical MMDPs, the model permits information exchange over possibly sparse communication networks, improving scalability for large agent populations.
  • Related work: The proposed MARL algorithms use actor-critic methods, contrasting with prior Q-learning-only approaches and differing in reward and controller assumptions.
Loading 1802.08757v2…