cs.LGNov 9, 2026

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

Authors: Sreejeet Maity, Aritra Mitra

Organizations: The authors are with the Department of Electrical and Computer Engineering, North Carolina State University, Raleigh.

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 dd-dimensional value function parameter, we establish that transmitting a total of O(dlog⁡(T))\mathcal{O}(d \log(T)) bits over a horizon of length TT suffices to achieve the order-optimal rate of O~(1/T)\tilde{\mathcal{O}}(1/T), marking an exponential improvement in communication-complexity over prior work.

Explore similar work

CardsList
  1. A Finite-Sample Analysis of Quantile Temporal-Difference Learning

    Aug 27, 2026Zijie Cheng, Xiang Li, Yang Peng +1Distributional RLStochastic Approximation

  2. Fast and Robust Convergence Rate for TD(0) with Linear Function Approximation, Universal Learning Steps and I.I.D. Samples

    Jun 4, 2026Ziad Kobeissi, Éloïse BerthierStochastic ApproximationTemporal-Difference Learning

  3. Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

    May 29, 2026Ivan Lau, Daniel McMorrow, Kevin Jamieson +1Multi-Armed BanditsBatched Bandits