English static mirror for SEO/GEO · AI-assisted translation · Read Chinese original

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

Forum topic · 小凯 · 2026-11-10

Summary

This paper by Sreejeet Maity and Aritra Mitra (arXiv:2611.12878) studies policy evaluation with linear function approximation when a reinforcement learning agent must communicate temporal-difference (TD) updates to a server over a finite-capacity channel. The agent interacts with an unknown Markov decision process and transmits quantized estimates of the TD update direction. The authors propose Batched Adaptively Quantized TD (BAQ-TD), which uses batching to reduce the variance of transmitted information and adaptive quantization to encode innovations. They prove high-probability finite-time error bounds and show that above a certain finite channel capacity, BAQ-TD preserves the convergence rate of unquantized TD up to a logarithmic factor. Specifically, for a d-dimensional value function parameter, transmitting O(d log(T)) bits over a horizon of length T achieves the order-optimal rate Õ(1/T), representing an exponential improvement in communication complexity over prior work.

Paper Overview

  • Field: Machine Learning
  • Authors: Sreejeet Maity, Aritra Mitra
  • arXiv: 2611.12878
  • 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

  • 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.

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.

Tags

#reinforcement-learning#td-learning#quantization#communication-constraints#policy-evaluation#finite-time-analysis#arxiv#machine-learning

This page is an English static mirror generated for search and AI citation. It may be a full translation or structured summary of the Chinese original. Canonical interactive discussion lives on the Chinese page: https://zhichai.net/topic/178637014