# Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning

arXiv: https://arxiv.org/abs/2301.00944 · HTML: https://mlsanity.com/paper/2301.00944/

## Key facts

- Cited by 12 papers in the map (data through 14 Oct 2026).
- Builds on 38 of its 57 references that are in the map.
- First posted on arXiv 3 Jan 2023.

## Builds on (most cited first, 30 of 38)

- [Local SGD Converges Fast and Communicates Little](https://mlsanity.com/paper/1805.09767/) (2018)
- [signSGD: Compressed Optimisation for Non-Convex Problems](https://mlsanity.com/paper/1802.04434/) (2018)
- [Federated Optimization: Distributed Machine Learning for On-Device Intelligence](https://mlsanity.com/paper/1610.02527/) (2016)
- [Deep Gradient Compression: Reducing the Communication Bandwidth for Distributed Training](https://mlsanity.com/paper/1712.01887/) (2017)
- [Sparsified SGD with Memory](https://mlsanity.com/paper/1809.07599/) (2018)
- [A Unified Theory of Decentralized SGD with Changing Topology and Local Updates](https://mlsanity.com/paper/2003.10422/) (2020)
- [FedPAQ: A Communication-Efficient Federated Learning Method with Periodic Averaging and Quantization](https://mlsanity.com/paper/1909.13014/) (2019)
- [Error Feedback Fixes SignSGD and other Gradient Compression Schemes](https://mlsanity.com/paper/1901.09847/) (2019)
- [TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning](https://mlsanity.com/paper/1705.07878/) (2017)
- [Sparse Communication for Distributed Gradient Descent](https://mlsanity.com/paper/1704.05021/) (2017)
- [A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximation](https://mlsanity.com/paper/1806.02450/) (2018)
- [The Convergence of Sparsified Gradient Methods](https://mlsanity.com/paper/1809.10505/) (2018)
- [Finite-Time Error Bounds For Linear Stochastic Approximation and TD Learning](https://mlsanity.com/paper/1902.00923/) (2019)
- [Federated Learning with Compression: Unified Analysis and Sharp Guarantees](https://mlsanity.com/paper/2007.01154/) (2020)
- [On Biased Compression for Distributed Learning](https://mlsanity.com/paper/2002.12410/) (2020)
- [Dissecting Adam: The Sign, Magnitude and Variance of Stochastic Gradients](https://mlsanity.com/paper/1705.07774/) (2017)
- [EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback](https://mlsanity.com/paper/2106.05203/) (2021)
- [Linear Convergence in Federated Learning: Tackling Client Heterogeneity and Sparse Gradients](https://mlsanity.com/paper/2102.07053/) (2021)
- [Distributed Learning with Compressed Gradient Differences](https://mlsanity.com/paper/1901.09269/) (2019)
- [Acceleration for Compressed Gradient Descent in Distributed and Federated Optimization](https://mlsanity.com/paper/2002.11364/) (2020)
- [Federated Reinforcement Learning: Techniques, Applications, and Open Challenges](https://mlsanity.com/paper/2108.11887/) (2021)
- [Perturbed Iterate Analysis for Asynchronous Stochastic Optimization](https://mlsanity.com/paper/1507.06970/) (2015)
- [Stochastic Distributed Learning with Gradient Quantization and Variance Reduction](https://mlsanity.com/paper/1904.05115/) (2019)
- [Federated Reinforcement Learning with Environment Heterogeneity](https://mlsanity.com/paper/2204.02634/) (2022)
- [Linearly Converging Error Compensated SGD](https://mlsanity.com/paper/2010.12292/) (2020)
- [Distributed learning with compressed gradients](https://mlsanity.com/paper/1806.06573/) (2018)
- [EF21-P and Friends: Improved Theoretical Communication Complexity for Distributed Optimization with Bidirectional Compression](https://mlsanity.com/paper/2209.15218/) (2022)
- [Federated Stochastic Approximation under Markov Noise and Heterogeneity: Applications in Reinforcement Learning](https://mlsanity.com/paper/2206.10185/) (2022)
- [RATQ: A Universal Fixed-Length Quantizer for Stochastic Optimization](https://mlsanity.com/paper/1908.08200/) (2019)
- [On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence](https://mlsanity.com/paper/1411.3224/) (2014)

## Built on by (most cited first, 12 of 12)

- [Momentum Provably Improves Error Feedback!](https://mlsanity.com/paper/2305.15155/) (2023)
- [A Simple Finite-Time Analysis of TD Learning with Linear Function Approximation](https://mlsanity.com/paper/2403.02476/) (2024)
- [Federated TD Learning over Finite-Rate Erasure Channels: Linear Speedup under Markovian Sampling](https://mlsanity.com/paper/2305.08104/) (2023)
- [Stochastic Approximation with Delayed Updates: Finite-Time Rates under Markovian Sampling](https://mlsanity.com/paper/2402.11800/) (2024)
- [Compressed Federated Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2404.10635/) (2024)
- [Towards Faster Decentralized Stochastic Optimization with Communication Compression](https://mlsanity.com/paper/2405.20114/) (2024)
- [Model-Free Learning for the Linear Quadratic Regulator over Rate-Limited Channels](https://mlsanity.com/paper/2401.01258/) (2024)
- [Robust Q-Learning under Corrupted Rewards](https://mlsanity.com/paper/2409.03237/) (2024)
- [Collaborative Value Function Estimation Under Model Mismatch: A Federated Temporal Difference Analysis](https://mlsanity.com/paper/2503.17454/) (2025)
- [Achieving Tighter Finite-Time Rates for Heterogeneous Federated Stochastic Approximation under Markovian Sampling](https://mlsanity.com/paper/2504.11645/) (2025)
- [Convergence Guarantees for Federated SARSA with Local Training and Heterogeneous Agents](https://mlsanity.com/paper/2512.17688/) (2025)
- [Corruption-Tolerant Asynchronous Q-Learning with Near-Optimal Rates](https://mlsanity.com/paper/2509.08933/) (2025)

## Abstract (arXiv)

In large-scale distributed machine learning, recent works have studied the effects of compressing gradients in stochastic optimization to alleviate the communication bottleneck. These works have collectively revealed that stochastic gradient descent (SGD) is robust to structured perturbations such as quantization, sparsification, and delays. Perhaps surprisingly, despite the surge of interest in multi-agent reinforcement learning, almost nothing is known about the analogous question: Are common reinforcement learning (RL) algorithms also robust to similar perturbations? We investigate this question by studying a variant of the classical temporal difference (TD) learning algorithm with a perturbed update direction, where a general compression operator is used to model the perturbation. Our work makes three important technical contributions. First, we prove that compressed TD algorithms, coupled with an error-feedback mechanism used widely in optimization, exhibit the same non-asymptotic theoretical guarantees as their SGD counterparts. Second, we show that our analysis framework extends seamlessly to nonlinear stochastic approximation schemes that subsume Q-learning. Third, we prove that for multi-agent TD learning, one can achieve linear convergence speedups with respect to the number of agents while communicating just tildeO(1) bits per iteration. Notably, these are the first finite-time results in RL that account for general compression operators and error-feedback in tandem with linear function approximation and Markovian sampling. Our proofs hinge on the construction of novel Lyapunov functions that capture the dynamics of a memory variable introduced by error-feedback.