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

Aug 27, 2026

A Finite-Sample Analysis of Quantile Temporal-Difference Learning

Quantile temporal-difference learning (QTD) is an effective method for learning return distributions through quantile approximation, yet its finite-time behavior remains poorly understood. Its update is nonlinear and nonsmooth, and the stability needed for a sharp convergence rate holds only near the target. We establish a global high-probability last-iterate guarantee for synchronous tabular QTD under general positive, nonincreasing step-size sequences and arbitrary initialization in the natural parameter range. For polynomially decaying step sizes with exponent a∈(0,1)a\in(0,1), the last iterate converges to the target at rate T−a/2T^{-a/2} in the infinity norm, up to logarithmic and lower-order terms. A suitably tuned harmonic schedule recovers the T−1/2T^{-1/2} statistical rate up to logarithmic factors. For the mm-quantile representation, its ∞\infty-Wasserstein error scales as m/T\sqrt{m/T} up to logarithmic factors, matching the leading polynomial dependence on the quantile resolution and sample size of the corresponding model-based estimator. The proof uses a two-stage global-to-local argument. From arbitrary initialization, Bellman contraction and CDF monotonicity first bring the iterate close to the target, after which, a novel variance--drift matching argument sharpens the control of accumulated noise and local contraction reduces the remaining errors, yielding the sharp rate. Simulations verify the predicted polynomial decay and assess the finite-time entrance bound.
Jun 4, 2026

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

In this paper, we study the finite-time behavior of the TD(0) temporal-difference method with linear function approximation (LFA). We consider on-policy independent and identically distributed (i.i.d.) samples, a constant learning step, and the Polyak-Juditsky averaging method. We establish a new convergence rate, for the Mean-Square Error (MSE) on the approximated function, that is (i) fast in the sense that it admits an optimal dependency in the number of iterations k (i.e., of order 1/k), (ii) robust to ill-conditioning: it only depends on an initial error and modelindependent constants and (iii) sharp up to a multiplicative constant lower than 11. In particular, it does not depend on the smallest eigenvalue of the uncentered covariance matrix of the linear parametrization, unlike all pre-existing O(1/k) rates in the TD(0) literature. We also introduce PCTD(0), a variant of TD(0), which benefits from better convergence properties under an additional assumption of strong mixing on the Markov Chain.
May 29, 2026

Batched Stochastic Linear Bandits with 1-Bit Communication Constraints

We study stochastic linear bandits under a natural combination of batching and communication constraints: the time horizon is partitioned into batches of equal size BB, and during each batch the learner sends BB requested arm pulls to an agent, who then observes the corresponding BB rewards and responds with a single bit of feedback to the learner. For each batch, the learner specifies the 1-bit quantization rule the agent uses, which may depend on all previously received bits but not on any past rewards directly. This setting addresses a significant yet unexplored ``middle ground'' between previous models having per-round quantization only or total bit budgets only. We establish a minimax lower bound showing that Ω(Bmin⁡{d,log⁡∣A∣})Ω(B\min\{d,\log\lvert \mathcal{A} \rvert\}) regret is unavoidable due to the 1-bit communication bottleneck, even in the absence of noise. Combined with standard statistical limits, this yields a general lower bound of Ω~(Bmin⁡{d,log⁡∣A∣}+dTmin⁡{d,log⁡∣A∣})\widetildeΩ(B\min\{d,\log\lvert \mathcal{A} \rvert\} + \sqrt{dT \min\{d,\log\lvert \mathcal{A} \rvert\}}). We develop two phased-elimination algorithms based on GG-optimal designs and 1-bit mean estimation. The first achieves O~(dB+dT)\widetilde{O}(dB + d\sqrt{T}) regret, matching the lower bound up to logarithmic factors when ∣A∣=exp⁡(Ω(d))\lvert \mathcal{A} \rvert = \exp(Ω(d)), and the second incorporates a safe-arm identification and warm-start procedure to obtain O~(Blog⁡∣A∣+d3/2B+dTlog⁡∣A∣)\widetilde{O}(B\log\lvert \mathcal{A} \rvert + d^{3/2}\sqrt{B} + \sqrt{dT\log\lvert \mathcal{A} \rvert}) regret, which is near-optimal in broad scaling regimes of (∣A∣,B,d,T)(\lvert \mathcal{A} \rvert, B, d, T). Together, our results demonstrate that a single bit of feedback per batch suffices to nearly match the minimax regret of unconstrained linear bandits in broad scaling regimes, even for batch sizes as large as Θ(T)Θ(\sqrt{T}).