Adaptive Quantization Preserves Fast Rates for TD Learning over Rate-Limited Channels

Sreejeet Maity, Aritra MitraarXiv 2026 · arXiv

This paper, "Adaptive Quantization Preserves Fast Rates for TD Learning over Rate-Limited Channels," presents a significant leap in the efficiency of distributed Reinforcement Learning (RL). The authors demonstrate that we can achieve the same "gold standard" learning speeds in communication-constrained environments as we do in unconstrained ones, but with exponentially less data transmitted.

TL;DR

The authors introduce BAQ-TD, an algorithm that enables Temporal Difference (TD) learning over rate-limited channels with a total communication cost that scales only logarithmically with time. By combining batching and adaptive quantization, they achieve the order-optimal $\tilde{\mathcal{O}}(1/T)$ convergence rate while reducing communication complexity from linear to logarithmic—an exponential improvement over previous state-of-the-art methods.

What Problem Does This Paper Address?

In many real-world RL scenarios, the "agent" (which collects data from the environment) and the "server" (which updates the model) are not the same machine. Think of a remote sensor or a mobile robot sending updates to a central cloud server.

The challenge is that the communication link between them is often rate-limited. The agent can only send a few bits per update. Standard TD learning assumes infinite precision, but in this "networked" setup, we face two types of noise:

  1. Sampling Noise: The inherent randomness of the environment (rewards and state transitions).
  2. Quantization Noise: The error introduced by squeezing a high-dimensional vector into a few bits.

Previous research suggested that to maintain high accuracy, the total number of bits sent must grow linearly with the number of samples ($T$). For long-running systems, this becomes prohibitively expensive. This paper asks: Can we preserve the ideal learning rate while sending significantly fewer bits?

Methods

The authors propose Batched Adaptively Quantized TD (BAQ-TD). The algorithm relies on two primary pillars:

  1. Model-Based Variance Reduction (Batching): Instead of sending an update for every single data point, the agent collects a "batch" of $H$ samples. It calculates a high-accuracy estimate of the TD update direction. This reduces the variance of the signal, making it "cleaner" before it even hits the communication channel.
  2. Adaptive Quantization of Innovations: Instead of sending the entire update vector, the agent only sends the "innovation"—the difference between its current estimate and what the server already knows. Crucially, the "radius" of the quantization (the range of values the bits represent) adapts over time. As the model converges, the innovations get smaller, and the quantization becomes finer, allowing for high precision without increasing the bit count.
The agent-server architecture for BAQ-TD. The agent batches samples and sends quantized innovations over a B-bit channel, while the server sends back exact parameters.

Datasets

The paper evaluates BAQ-TD using a synthetic 100-state discounted Markov Decision Process (MDP).

  • Function Approximation: They use Linear Function Approximation (LFA) with $d=10$ features.
  • Setup: The reward noise and state transitions are simulated to test the algorithm's robustness against the "sampling noise" mentioned earlier.
  • Comparison: They compare BAQ-TD against "unquantized TD" (the theoretical ideal with infinite communication) and previous compressed TD schemes.

Key Insights and Ideas

  • Variance is the Enemy of Communication: The "aha moment" here is that reducing statistical variance through batching directly translates to needing fewer bits. A lower-variance signal stays within a smaller "uncertainty ball," which is easier to describe with a fixed number of bits.
  • Logarithmic Communication is Sufficient: You don't need to talk to the server at every time step. By communicating in epochs that grow logarithmically with the total time horizon $T$, you can maintain the optimal $\tilde{\mathcal{O}}(1/T)$ error rate.
  • Fixed Channel Capacity: Remarkably, the number of bits required per message ($B$) does not need to increase as you collect more data. A fixed, finite channel capacity is enough to reach any level of precision, provided the quantization is adaptive.

Key Results

  • Exponential Speedup in Communication: BAQ-TD requires only $\mathcal{O}(d \log T)$ total bits to achieve the same error rate that previous methods required $\mathcal{O}(T)$ bits for.
  • Preservation of "Fast Rates": The algorithm achieves a high-probability convergence rate of $\tilde{\mathcal{O}}(1/T)$, which is the best possible rate for TD learning even without communication constraints.
  • Empirical Validation: Simulations show that with a precision of just $m=16$ bits per coordinate, BAQ-TD's performance is virtually indistinguishable from unquantized TD learning.
Fig. 2. (Left) Evolution of the estimation error Ek = ∥θk−θ⋆∥2 for BAQ-TD with batch sizes H ∈{512, 2048, 8192}, precision m = 16, and K = 1000 epochs. (Middle) Results for precisions m ∈{10, 12, 16}, compared with unquantized TD. (Right) Terminal estimation error EK = ∥θK −θ⋆∥2 versus sample budget T for BAQ-TD with m ∈{12, 16} and unquantized TD. The dashed line shows the T −1/2 scaling suggested by our square-error bound.

Limitations and Future Work

While a major step forward, the authors note a few areas for future exploration:

  • I.I.D. Sampling: The current proof assumes samples are independent and identically distributed (i.i.d.). While they mention extensions to Markovian (single-trajectory) data are possible using "blocking" arguments, the formal proof focuses on the i.i.d. case.
  • Perfect Down-link: The model assumes the server can send the updated parameters back to the agent with infinite precision. In real systems, the "down-link" might also be rate-limited.
  • Beyond Linear Approximation: The work is grounded in linear function approximation. Extending these adaptive quantization benefits to non-linear models (like Deep Neural Networks) remains an open challenge.
  • Algorithm Scope: This paper focuses on policy evaluation. Future work could extend these communication-efficient techniques to policy improvement (e.g., Q-learning or Policy Gradients).

Summary updated

Abstract

Motivated by reinforcement learning subject to communication constraints, we study a policy evaluation problem with linear function approximation over a rate-limited channel. In our setup, an agent interacting with an unknown environment (modeled as a Markov Decision Process) transmits quantized estimates of a temporal-difference (TD) learning update direction to a server over a finite-capacity channel. Our goal is to investigate to what extent one can preserve the statistical convergence rates achievable when the channel has infinite capacity. To that end, we propose a new algorithm called Batched Adaptively Quantized TD (BAQ-TD), which uses batching to reduce the variance of the transmitted information, and adaptive quantization to encode innovations. We prove a high-probability finite-time error bound for BAQ-TD, and show that, above a certain finite channel capacity, BAQ-TD preserves the convergence rate of unquantized TD up to logarithmic factors. Specifically, for a $d$-dimensional value function parameter, we establish that transmitting a total of $\mathcal{O}(d \log(T))$ bits over a horizon of length $T$ suffices to achieve the order-optimal rate of $\tilde{\mathcal{O}}(1/T)$, marking an exponential improvement in communication-complexity over prior work.
BibTeX
@misc{maity2026adaptive,
  author = {Sreejeet Maity and Aritra Mitra},
  title = {{Adaptive Quantization Preserves Fast Rates for TD Learning over Rate-Limited Channels}},
  year = {2026},
  eprint = {2611.12878},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2611.12878},
}
Figure