Decentralized TD Tracking with Linear Function Approximation and its Finite-Time Analysis

Gang Wang, Songtao Lu, Georgios B. Giannakis, Gerald Tesauro, Jian SunNeurIPS 2020 · OpenReview

Abstract

This paper introduces Decentralized TD Tracking (DTDT), a novel algorithm for multi-agent policy evaluation that combines temporal-difference (TD) learning with gradient tracking. By leveraging variance reduction, DTDT achieves finite-time convergence rates comparable to centralized TD methods, effectively removing the performance penalty typically associated with increasing the number of agents in a decentralized network.

Introduction: The Multi-Agent Bottleneck

In multi-agent reinforcement learning (MARL), a group of agents often needs to collaboratively estimate a "value function"—the expected long-term reward of a policy—within a shared environment. While agents observe the same state transitions, their rewards are often private.

The standard approach is decentralized TD learning (DTDL), where agents perform local updates and use consensus (averaging) to stay synchronized. However, existing DTDL methods face two major hurdles:

  1. The Scaling Bottleneck: Their error bounds often scale poorly with the number of agents ($N$), making them significantly less accurate than a single centralized learner.
  2. The Markovian Mess: In real RL, data isn't independent and identically distributed (i.i.d.); consecutive states are highly correlated (Markovian). This correlation introduces bias and makes it extremely difficult to prove how fast an algorithm will actually converge in a finite amount of time.

The authors aim to bridge the gap between decentralized and centralized performance while providing a rigorous "finite-time" analysis for realistic, correlated data.

Methodology: Decentralized TD Tracking

The core innovation is the Decentralized TD Tracking (DTDT) algorithm. It builds on two main pillars:

  • Linear Function Approximation: To handle large state spaces, the value function is represented as a linear combination of fixed features ($\phi(s)^\top \theta$).
  • Gradient Tracking: This is the "secret sauce." In standard consensus algorithms, agents only average their parameter estimates ($\theta$). In DTDT, agents also maintain and communicate an auxiliary variable ($\psi$) dedicated to tracking the global gradient. By mixing these trackers, each agent gets a much more accurate estimate of the overall network's gradient, which reduces the variance of their local updates.

The authors also provide a multistep Lyapunov analysis. This mathematical framework allows them to prove that even when data is biased and correlated (Markovian), the algorithm's error "drifts" toward zero at a predictable, linear rate.

Experimental Setup

The paper evaluates the algorithm using numerical simulations rather than standard public datasets, which is common for theoretical RL papers focusing on convergence properties. The environment is a synthetic MDP with 100 states and a 10-dimensional feature space. The network consists of 100 agents connected via an Erdős–Rényi random graph, utilizing a doubly stochastic and symmetric transition matrix.

Key Insights

  • Variance Reduction is Key: The primary reason decentralized algorithms underperform is the high variance of local gradient estimates. Gradient tracking acts as a variance reduction mechanism, allowing local nodes to "see" the global objective more clearly.
  • Independence from $N$: Perhaps the most surprising insight is that the residual error term in DTDT does not depend on the number of agents. This means you can add more agents to the network without necessarily degrading the final solution's accuracy—a major improvement over prior art.
  • Unifying Analysis: The authors show that the same Lyapunov-based proof technique can handle both the "easy" i.i.d. case and the "hard" Markovian case, providing a robust theoretical foundation for the algorithm.

Key Results

Under both i.i.d. and Markovian settings, DTDT converges linearly to a neighborhood of the optimal parameter $\theta^*$. The finite-time error bounds for DTDT match the sharpest known bounds for centralized TD learning, effectively proving that decentralization doesn't have to come at a cost to performance.

Comparison of DTDT and DTDL performance metrics

In simulations, DTDT achieved a consensus error (disagreement between agents) several orders of magnitude smaller than standard DTDL algorithms. Furthermore, DTDT reached a stable solution faster than DTDL when using the same step size, confirming that gradient tracking effectively accelerates the learning process.

Limitations and Future Work

While DTDT represents a significant step forward, it has a few limitations:

  • Linearity Constraint: The analysis is strictly for linear function approximation. Extending these finite-time guarantees to non-linear "Deep" RL (using neural networks) remains a significant open challenge.
  • Policy Evaluation Only: This work focuses on evaluating a fixed policy. It does not address the "control" problem—where agents must also improve their policy over time—which introduces further non-stationarity.
  • Communication Overhead: While DTDT is efficient, it requires agents to exchange both parameter estimates and gradient trackers, doubling the communication load per iteration compared to the simplest consensus methods.
  • Robustness: The paper assumes a static, connected graph. Future work could explore how DTDT handles directed graphs, time-varying topologies, or communication delays.

Summary updated

Abstract

The present contribution deals with decentralized policy evaluation in multi-agent Markov decision processes using temporal-difference (TD) methods with linear function approximation for scalability. The agents cooperate to estimate the value function of such a process by observing continual state transitions of a shared environment over the graph of interconnected nodes (agents), along with locally private rewards. Different from existing consensus-type TD algorithms, the approach here develops a simple decentralized TD tracker by wedding TD learning with gradient tracking techniques. The non-asymptotic properties of the novel TD tracker are established for both independent and identically distributed (i.i.d.) as well as Markovian transitions through a unifying multistep Lyapunov analysis. In contrast to the prior art, the novel algorithm forgoes the limiting error bounds on the number of agents, which endows it with performance comparable to that of centralized TD methods that are the sharpest known to date.
BibTeX
@inproceedings{wang2020decentralized,
  author = {Gang Wang and Songtao Lu and Georgios B. Giannakis and Gerald Tesauro and Jian Sun},
  title = {{Decentralized TD Tracking with Linear Function Approximation and its Finite-Time Analysis}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2020},
  url = {https://openreview.net/forum?id=TJQOeIrvDL},
}
Figure