mlsanityData to 7 Oct 2026

Multi-Agent Off-Policy TD Learning: Finite-Time Analysis with Near-Optimal Sample Complexity and Communication Complexity

arXiv 2103.13147 ↗First posted 24 Mar 2021cs.LG cs.MA math.OCcited by 5

Not on the map. Why?

Abstract (arXiv)

The finite-time convergence of off-policy TD learning has been comprehensively studied recently. However, such a type of convergence has not been well established for off-policy TD learning in the multi-agent setting, which covers broader applications and is fundamentally more challenging. This work develops two decentralized TD with correction (TDC) algorithms for multi-agent off-policy TD learning under Markovian sampling. In particular, our algorithms preserve full privacy of the actions, policies and rewards of the agents, and adopt mini-batch sampling to reduce the sampling variance and communication frequency. Under Markovian sampling and linear function approximation, we proved that the finite-time sample complexity of both algorithms for achieving an ε-accurate solution is in the order of O(ε-1ln ε-1), matching the near-optimal sample complexity of centralized TD(0) and TDC. Importantly, the communication complexity of our algorithms is in the order of O(ln ε-1), which is significantly lower than the communication complexity O(ε-1ln ε-1) of the existing decentralized TD(0). Experiments corroborate our theoretical findings.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 22 of its 47 references that are in the map. First posted on arXiv 24 Mar 2021.

Builds on

22 of 47 references.

References · 22

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 225
  2. 2019Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learningcited by 165
  3. 2019Finite-Sample Analysis for SARSA with Linear Function Approximationcited by 85
  4. 2017Optimal algorithms for smooth and strongly convex distributed optimization in networkscited by 81
  5. 2020Finite Time Analysis of Linear Two-timescale Stochastic Approximation with Markovian Noisecited by 52
  6. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  7. 2019Finite-Time Performance Bounds and Adaptive Learning Rate Selection for Two Time-Scale Reinforcement Learningcited by 40
  8. 2020Finite-Sample Analysis of Proximal Gradient TD Algorithmscited by 32
  9. 2019Two Time-scale Off-Policy TD Learning: Non-asymptotic Analysis over Markovian Samplescited by 31
  10. 2019A Tale of Two-Timescale Reinforcement Learning with the Tightest Finite-Time Boundcited by 31
  11. 2020SQuARM-SGD: Communication-Efficient Momentum SGD for Decentralized Optimizationcited by 31
  12. 2020Reanalysis of Variance Reduced Temporal Difference Learningcited by 23
10 more
  1. 2014On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergencecited by 20
  2. 2020Sample Complexity Bounds for Two Timescale Value-based Reinforcement Learning Algorithmscited by 19
  3. 2013Distributed Policy Evaluation Under Multiple Behavior Strategiescited by 17
  4. 2019Characterizing the Exact Behaviors of Temporal Difference Learning Algorithms Using Markov Jump Linear System Theorycited by 17
  5. 2018Multi-Agent Fully Decentralized Value Function Learning with Linear Convergence Ratescited by 13
  6. 2020Variance-Reduced Off-Policy TDC Learning: Non-Asymptotic Convergence Analysiscited by 12
  7. 2019A Multistep Lyapunov Approach for Finite-Time Analysis of Biased Stochastic Approximationcited by 10
  8. 2019Finite-Sample Analysis of Decentralized Temporal-Difference Learning with Linear Function Approximationcited by 9
  9. 2013Distributed Reinforcement Learning via Gossipcited by 8
  10. 2020A Hysteretic Q-learning Coordination Framework for Emerging Mobility Systems in Smart Citiescited by 4

Built on by

Cited by year

Citing papers per year: 2021: 3; 2022: 1; 2023: 0; 2024: 1.

5 papers.

  1. 2021Sample and Communication-Efficient Decentralized Actor-Critic Algorithms with Finite-Time Analysiscited by 25
  2. 2021Learning to Coordinate in Multi-Agent Systems: A Coordinated Actor-Critic Algorithm and Finite-Time Guaranteescited by 6
  3. 2024Compressed Federated Reinforcement Learning with a Generative Modelcited by 5
  4. 2021A Law of Iterated Logarithm for Multi-Agent Reinforcement Learningcited by 1
  5. 2022Finite-Time Analysis of Fully Decentralized Single-Timescale Actor-Criticcited by 1