Paper Overview
- Field: Machine Learning
- Authors: Sreejeet Maity, Aritra Mitra
- arXiv: 2611.12878
- High-probability finite-time error bounds for BAQ-TD.
- Above a certain finite channel capacity, BAQ-TD retains the convergence rate of unquantized TD up to at most a logarithmic factor.
- For a d-dimensional value function parameter, transmitting a total of O(d log(T)) bits over a horizon of length T suffices to achieve the order-optimal rate Õ(1/T).
- This represents an exponential improvement in communication complexity over prior work.
Summary
Motivated by reinforcement learning under communication constraints, this paper studies policy evaluation with linear function approximation over a rate-limited channel. The setting: an agent interacts with an unknown environment (modeled as a Markov decision process) and must transmit quantized estimates of the temporal-difference (TD) learning update direction to a server over a finite-capacity channel. The central question is: to what extent can the statistical convergence rates achievable with an unlimited-capacity channel be preserved?
To answer this, the authors propose Batched Adaptively Quantized TD (BAQ-TD), which leverages batching to reduce the variance of transmitted information and adaptive quantization to encode innovations.
Key Results
Original Abstract
> We study policy evaluation with linear function approximation over a rate-limited channel, and propose Batched Adaptively Quantized TD (BAQ-TD), which uses batching to reduce variance and adaptive quantization to encode innovations. We show that transmitting O(d log(T)) bits over a horizon of length T suffices to achieve the order-optimal rate.