Adaptive quantization keeps td learning fast over limited channels
Adaptive Quantization Preserves Fast Rates for TD Learning over Rate-Limited Channels
Machine Learning
Summary
When a computer learns how to make decisions over a network with limited communication, it needs to send its updates efficiently. The authors studied how to send learning signals for a popular method called temporal-difference (TD) learning while using fewer bits over a slow channel. They created an approach that batches updates and uses adaptive compression to send these updates without losing the usual learning speed. Their math shows that beyond a certain network capacity, the learning speed almost matches what you get with unlimited communication, using exponentially fewer bits.
What this means in practice
- •For robotics engineers: Use efficient update transmissions to maintain fast learning rates in robots with limited wireless bandwidth.
- •For iot system developers: Enable IoT devices to perform reinforcement learning while minimizing data sent over constrained network connections.
Authors
Sreejeet Maity, Aritra Mitra
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.