Distributed TD(0) with Almost No Communication

Rui Liu, Alex OlshevskyarXiv 2021 · OpenReview

TL;DR

This paper introduces a novel distributed TD(0) algorithm that achieves state-of-the-art convergence rates with significantly reduced communication. By employing a "one-shot averaging" strategy, where agents only communicate their learned parameters at the very end, the method matches centralized TD(0) performance in a global state setting and achieves a linear speedup in a local state setting, demonstrating the power of parallelism for temporal difference learning.

What Problem Does This Paper Address?

Reinforcement learning (RL) is increasingly applied in multi-agent systems, but understanding how standard RL algorithms perform in these settings, especially with limited communication, remains a challenge. Policy evaluation, a fundamental problem in RL, is often tackled with Temporal Difference (TD) learning. While distributed versions of TD learning exist, prior work often required frequent communication between agents at each step, leading to high communication overhead and potentially worse performance than centralized methods, sometimes by a factor of $O(N^3)$ where $N$ is the number of agents. This paper aims to develop a distributed TD(0) algorithm that is communication-efficient and can match or even improve upon the performance of its centralized counterpart.

Methods

The core contribution is a distributed TD(0) algorithm based on a "one-shot averaging" approach. Instead of continuous communication, each of the $N$ agents runs a local copy of the TD(0) algorithm. At the very end of the learning process, all agents communicate their learned parameters once to compute a global average. This approach is analyzed under two distinct multi-agent settings:

  1. Global State Model: Agents interact with a shared environment where the next state and rewards depend on the joint actions of all agents. The authors show that their one-shot averaging method achieves convergence rates identical to centralized TD(0), overcoming the $O(N^3)$ performance degradation seen in prior work.
  2. Local State Model: Each agent operates on its own independent copy of the same Markov Decision Process (MDP). In this setting, the authors demonstrate a "linear time speedup" phenomenon, where the convergence time of the distributed algorithm is reduced by a factor of $N$ compared to the centralized version. This is the first rigorous demonstration of parallelism benefits for TD methods.

The analysis relies on non-asymptotic convergence bounds and standard assumptions about the MDP and feature representations.

Datasets

The paper evaluates its methods on:

  • Gridworld: A standard, small-scale discrete state-action environment.
  • Classic Control Problems: Standard benchmarks from OpenAI Gym, including Acrobot-v1, CartPole-v1, MountainCar-v1, MountainCarContinuous-v0, and Pendulum-v1. These environments are used to test the algorithm's performance on continuous state spaces using tile coding for function approximation.

No new benchmarks were introduced; existing ones were used to compare against prior work.

Key Insights and Ideas

  • "One-Shot Averaging" is Sufficient: The most striking insight is that for distributed TD(0), extensive communication at every step is not necessary. A single averaging step at the end is enough to achieve competitive or superior performance. This drastically reduces communication overhead.
  • Parallelism Benefits in Local State Model: The local state model setting reveals a significant advantage of parallelism. When agents have independent MDPs, distributing the computation allows for a linear speedup in convergence time, directly attributed to the ability to process independent samples in parallel.
  • Overcoming Prior Limitations: The proposed method explicitly addresses the performance degradation observed in previous distributed TD algorithms, particularly in the global state model, where communication bottlenecks or spectral gap issues could lead to $O(N^3)$ performance penalties. This work shows that these penalties can be avoided.
  • Theoretical Guarantees for Parallelism: The paper provides rigorous non-asymptotic convergence guarantees, demonstrating that the benefits of parallelism are not just empirical but theoretically grounded.

Key Results

  • Global State Model: The distributed one-shot averaging method achieves convergence rates that match the state-of-the-art for centralized TD(0), without dependence on the number of agents $N$ or the spectral gap of communication. This contrasts with prior work that could degrade by $O(N^3)$.
  • Local State Model: A linear speedup in convergence time is demonstrated, meaning the distributed algorithm converges $N$ times faster than the centralized version. This is a novel theoretical result for TD methods.
  • Empirical Validation: Experiments on Gridworld and classic control problems (Figure 1) show that increasing the number of agents ($N=17$) leads to a quadratic improvement in the inverse variance of the final solution compared to a linear improvement with $N=1$, supporting the theoretical findings. Figure 2 shows that the proposed method achieves comparable TD errors to prior methods with significantly less communication.

Limitations and Future Work

  • i.i.d. Sampling Assumption: The theoretical analysis relies on the assumption of i.i.d. samples, which is a simplification of real-world scenarios where states often form a Markov chain. While the paper mentions that the i.i.d. model is standard for analyzing TD and Q-learning, relaxing this assumption would be a valuable future direction.
  • Linear Function Approximation: The analysis is restricted to linear function approximation. Extending the results to non-linear function approximators, which are common in deep RL, would be a significant advancement.
  • Exploration: The paper focuses on policy evaluation. Future work could explore how this communication-efficient distributed approach can be applied to policy optimization and exploration in multi-agent settings.
  • More Complex Communication Topologies: While the paper discusses message complexity in terms of average consensus, exploring more general or dynamic communication topologies could be an area for future research.

Summary updated

Abstract

We provide a new non-asymptotic analysis of distributed TD(0) with linear function approximation. Our approach relies on "one-shot averaging," where $N$ agents run local copies of TD(0) and average the outcomes only once at the very end. We consider two models: one in which the agents interact with an environment they can observe and whose transitions depends on all of their actions (which we call the global state model), and one in which each agent can run a local copy of an identical Markov Decision Process, which we call the local state model. In the global state model, we show that the convergence rate of our distributed one-shot averaging method matches the known convergence rate of TD(0). By contrast, the best convergence rate in the previous literature showed a rate which, according to the worst-case bounds given, could underperform the non-distributed version by $O(N^3)$ in terms of the number of agents $N$. In the local state model, we demonstrate a version of the linear time speedup phenomenon, where the convergence time of the distributed process is a factor of $N$ faster than the convergence time of TD(0). As far as we are aware, this is the first result rigorously showing benefits from parallelism for temporal difference methods.
BibTeX
@misc{liu2021distributed,
  author = {Rui Liu and Alex Olshevsky},
  title = {{Distributed TD(0) with Almost No Communication}},
  year = {2021},
  eprint = {2104.07855},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2104.07855},
}
Figure