Finite-Time Analysis of Distributed TD(0) with Linear Function Approximation for Multi-Agent Reinforcement Learning

Thinh T. Doan, Siva Theja Maguluri, Justin RombergarXiv 2019 · DOI · arXiv

Abstract

We study the policy evaluation problem in multi-agent reinforcement learning. In this problem, a group of agents works cooperatively to evaluate the value function for the global discounted accumulative reward problem, which is composed of local rewards observed by the agents. Over a series of time steps, the agents act, get rewarded, update their local estimate of the value function, then communicate with their neighbors. The local update at each agent can be interpreted as a distributed consensus-based variant of the popular temporal difference learning algorithm TD(0). While distributed reinforcement learning algorithms have been presented in the literature, almost nothing is known about their convergence rate. Our main contribution is providing a finite-time analysis for the convergence of the distributed TD(0) algorithm. We do this when the communication network between the agents is time-varying in general. We obtain an explicit upper bound on the rate of convergence of this algorithm as a function of the network topology and the discount factor. Our results mirror what we would expect from using distributed stochastic gradient descent for solving convex optimization problems.

Introduction

In reinforcement learning (RL), policy evaluation is the fundamental task of estimating the long-term value of a specific strategy. In a multi-agent reinforcement learning (MARL) setting, this task becomes significantly more complex. Here, the "global" reward is the sum of many "local" rewards observed only by individual agents.

Consider a fleet of autonomous delivery drones. Each drone tracks its own battery levels and local delivery successes (local rewards), yet the objective is to evaluate the performance of the entire fleet (the global value function). To achieve this without a central controller, drones must communicate with their neighbors to reach a consensus. While distributed algorithms for this purpose exist, their efficiency—specifically how fast they converge to an accurate estimate—has remained largely unquantified. Most prior research focused on asymptotic convergence, proving that algorithms eventually reach the correct answer. This paper provides the first finite-time analysis, offering mathematical guarantees on the remaining error after a specific number of iterations ($k$).

Methodology: Distributed Consensus-Based TD(0)

The study analyzes a distributed version of the TD(0) algorithm. The process at each time step for every agent involves four primary components:

  1. Consensus Step: Each agent computes a weighted average of its current estimate with those of its immediate neighbors. This "gossip" mechanism ensures that all agents eventually converge toward a shared global estimate.
  2. Local TD Update: The agent performs a standard Temporal Difference (TD) update using its own local reward and the observed state transition.
  3. Linear Function Approximation: To handle large state spaces, agents approximate the value function using a linear combination of features rather than a lookup table.
  4. Projection: Updates are projected onto a bounded convex set to maintain mathematical stability.

The analysis is robust, covering both constant stepsizes (fixed learning rates) and diminishing stepsizes (rates that decrease over time). Crucially, it accounts for time-varying communication networks, where the set of neighbors for any given agent may change dynamically.

Theoretical Insights

TD(0) as "Pseudo-SGD"

A significant challenge in this analysis is that TD(0) is not a true gradient descent method; it does not follow the gradient of a fixed objective function. However, this research demonstrates that its convergence behavior is remarkably similar to distributed stochastic gradient descent (SGD) used in convex optimization.

The Impact of Network Topology

The convergence rate is explicitly tied to the spectral gap ($1-\delta$) of the communication network. This value quantifies the connectivity of the agents. A better-connected network allows for faster consensus, which in turn accelerates the reduction of the global error. This "topology tax" highlights the importance of communication efficiency in distributed RL.

The Role of the Discount Factor

The error bounds are also sensitive to the discount factor ($\gamma$). As $\gamma$ approaches 1—indicating that agents prioritize long-term rewards over immediate ones—the problem becomes more difficult, and the convergence rate slows accordingly.

Key Results

The paper establishes explicit upper bounds on the convergence rate of the distributed TD(0) algorithm:

  • Constant Stepsize ($\alpha$): The error converges to a neighborhood of the optimal value at a rate of $O(1/k)$. While this rate is efficient, the fixed stepsize prevents the error from reaching zero, eventually hitting a "floor."
  • Diminishing Stepsize ($\alpha = 1/\sqrt{k+1}$): The error converges asymptotically to the true optimal value at a rate of $O(1/\sqrt{k})$.

These rates match the known optimal rates for distributed stochastic optimization, suggesting that distributed TD(0) is as efficient as theoretically possible for this class of problems.

Limitations and Future Directions

While this work provides a foundational finite-time analysis, several avenues for future research remain:

  • I.I.D. Sampling: The current analysis assumes data samples are independent and identically distributed (i.i.d.). In practice, RL data is collected sequentially, introducing temporal correlations that are difficult to model.
  • TD($\lambda$): This study focuses on $\lambda=0$. Extending these finite-time bounds to the more general TD($\lambda$) algorithm is a logical next step.
  • Non-Stationary Policies: The analysis assumes fixed policies. Future work could extend these results to distributed actor-critic methods, where the policy evolves as the agents learn.

Summary updated

Abstract

We study the policy evaluation problem in multi-agent reinforcement learning. In this problem, a group of agents works cooperatively to evaluate the value function for the global discounted accumulative reward problem, which is composed of local rewards observed by the agents. Over a series of time steps, the agents act, get rewarded, update their local estimate of the value function, then communicate with their neighbors. The local update at each agent can be interpreted as a distributed consensus-based variant of the popular temporal difference learning algorithm TD(0). While distributed reinforcement learning algorithms have been presented in the literature, almost nothing is known about their convergence rate. Our main contribution is providing a finite-time analysis for the convergence of the distributed TD(0) algorithm. We do this when the communication network between the agents is time-varying in general. We obtain an explicit upper bound on the rate of convergence of this algorithm as a function of the network topology and the discount factor. Our results mirror what we would expect from using distributed stochastic gradient descent for solving convex optimization problems.
BibTeX
@misc{doan2019finite,
  author = {Thinh T. Doan and Siva Theja Maguluri and Justin Romberg},
  title = {{Finite-Time Analysis of Distributed TD(0) with Linear Function Approximation for Multi-Agent Reinforcement Learning}},
  year = {2019},
  eprint = {1902.07393},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1902.07393},
}
Figure