WorksComputer Science
Adaptive Quantization Preserves Fast Rates for TD Learning over Rate-Limited Channels
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 -dimensional value function parameter, we establish that transmitting a total of bits over a horizon of length suffices to achieve the order-optimal rate of , marking an exponential improvement in communication-complexity over prior work.
Introduction
The classical paradigm of networked control seeks to characterize how the presence of a communication network impacts closed-loop performance [1, 2, 3]. Specifically, when data collected from multiple sensors is transmitted over non-ideal channels that are rate-limited, noisy, lossy, and introduce latencies, the goal is to understand how tasks such as state estimation, stabilization, and optimal control design get affected. Although the study of such questions is quite mature by now, the central pervasive assumption in networked control is that the system model is perfectly known. Realizing that such an assumption is impractical for modern, complex dynamical systems, over the last decade, there has been a gradual shift of interest towards data-driven control/reinforcement learning (RL) algorithms. Typically, the performance of RL algorithms is assessed via sample complexity, i.e., the number of samples (or interactions with the unknown environment) needed to learn a near-optimal policy. Communication once again becomes a central consideration in this context when the sensing and decision-making modules are not co-located. Surprisingly, even for the simplest of RL problems, the impact of communication constraints on sample-complexity is not well understood. Motivated by this gap, in this paper, we aim to shed light on the interplay between control, communication, and model-uncertainty.
The authors are with the Department of Electrical and Computer Engineering, North Carolina State University, Raleigh. Email: {smaity2,amitraz}@ncsu.edu. This work is supported by the following grant from the National Science Foundation: NSF CAREER award 2542396.
The Setting. A natural starting point for our investigation is (arguably) the simplest RL problem of policy evaluation - estimating the value function corresponding to a given policy for subsequent policy improvement. We consider such a problem in discrete Markov Decision Processes (MDPs) with a finite number of states and actions. To allow for large state-spaces, we follow the standard idea of linear function approximation (LFA), where the value function estimate is parameterized by a linear function class. The classical Temporal Difference (TD) learning algorithm [4] uses data generated by the policy (to be evaluated) to iteratively update the value-function parameter. While both asymptotic [4] and finite-sample [5, 6, 7, 8] convergence results for TD learning exist in the literature, our specific focus here is to characterize how communication constraints impact such convergence.
To do so, we take inspiration from the networked control literature [1], and consider a setting where a worker agent interacts directly with the MDP, collects raw data samples, and communicates encoded information to a remote server over a noiseless, rate-limited up-link channel that can support only a finite-bit message per transmission; see Figure 1. The agent uses observed data to maintain noisy estimates of the TD direction and transmit quantized versions of such estimates. The server uses a decoded version of the quantized TD direction to update the value function parameter which is transmitted back to the agent over a perfect down-link channel of infinite capacity. In our setup, one can essentially view the agent as the “sensor” responsible for data collection and estimation, and the server as the “decision-maker” responsible for parameter updates.

Figure 1. Agent-server architecture for BAQ–TD, presented in Algorithm 1.
Given this premise, we ask: With a time-horizon of time-steps (equivalently, a sample budget of ), how many bits of information need to be transmitted from the agent to the server to match (if at all possible) the statistical accuracy of unquantized TD learning, i.e., TD learning with no communication constraints? The only two papers we know of that provide partial answers to this question are [9, 10] which explore the use of generic error-feedback and randomized quantization mechanisms, respectively. In each of these papers, the total communication cost scales linearly with the sample budget , which can be prohibitively large for communication-constrained environments. Our main contribution in this paper is to offer a new variant of the TD(0) algorithm where the corresponding communication complexity scales merely logarithmically in , marking an exponential improvement relative to the prior work in [9, 10]. In what follows, we elaborate on this contribution.
Algorithmic Contribution. There are two sources of error in our setup which complicate the process of encoder-
decoder design. First, the randomness in the data (rewards and state transitions) causes fluctuations in the empirically estimated TD directions. Such random fluctuations need to be accurately accounted for in the design of the encoding radius: if the radius is too small, then it may not be able to capture worst-case deviations around the mean estimate; if the radius is too large, then the resulting sample-complexity bounds might be too loose. Second, the rate-limited channel distorts the estimated TD direction, adding a second layer of uncertainty. The challenge lies in ensuring that the two errors alluded to above do not pile up across iterations.
In response to this challenge, we develop BAQ–TD, a novel variant of the TD(0) algorithm that relies on two key ideas: (i) model-based variance reduction to reduce the variance of each estimated TD direction, and (ii) adaptive quantization to encode innovations in the TD directions. Specifically, our algorithm runs in epochs, and in each epoch, the agent uses the data collected during that epoch to generate a “high-accuracy” variance reduced estimate of the ideal steady-state TD(0) direction. The simple intuition here is that reducing the variance leads to a lower uncertainty, which, in turn, translates to fewer bits needed to encode the uncertainty. To further save on bits, we only encode “innovations” capturing what is new at the agent (based on fresh data) relative to what is already known at the server from previous transmissions. Designing an adaptive encoding radius that contains such a random innovation process (with high probability) is the chief non-trivial task; we show how this can be done in Section III.
Theoretical contribution. Given samples, in Theorem 1, we provide a high-probability convergence rate on the order of for BAQ–TD. Such a rate is consistent with what is known for unquantized TD(0) [5, 6, 7, 8], and is order-optimal in the sample-size . Thus, we show that statistical rates can be preserved despite finite channel capacities. Interestingly, the channel capacity needed to achieve this result does not depend on , but rather scales as , where is the dimension of the value function parameter, and is a problem-dependent constant that we specify in Section IV. Moreover, we show that transmissions suffice to preserve order-optimal rates, leading to a total communication cost on the order .
Related Work. Recently, a growing body of work has started looking at the effect of communication constraints for decision-making problems under uncertainty, with stochastic bandits [11, 12, 13] and tabular MDPs [14] as natural starting points. Beyond the simple tabular case, the interplay between function approximation and bit constraints has been explored in [9, 10]. Moreover, for continuous state-action spaces, some recent papers conducted similar studies on policy gradient algorithms for the linear quadratic regulator (LQR) [15, 16]. In fact, we build on the adaptive quantization idea in [16]. However, all of the papers [9, 10, 15, 16] incur communication costs that are linear in sample-size/time-horizon. In contrast, we show that despite errors resulting from function approximation, random data, and channel-induced distortions, logarithmic-in-sample size communications costs are adequate for preserving “ideal” convergence rates.
Background and Problem Formulation
We consider a discounted Markov decision process , where and are the (finite) state and action spaces, is the collection of transition kernels, specifies reward functions, and is the discount factor. We consider deterministic policies, where each deterministic policy maps a state to an action. A fixed policy induces a Markov reward process with a transition matrix , and a reward function . For each , let denote the noisy random one-step reward with distribution and mean . We assume1 that and that the centered reward is sub-Gaussian with variance proxy , i.e., for every and . The long-term return obtained from playing policy in the MDP , starting from an initial state , is given by the value function , defined formally as
where represents the state of the Markov chain (induced by ) at time , with . To initiate the study of communication-constrained RL, we consider one of the simplest RL problems in this paper, namely policy evaluation - the task of evaluating corresponding to a given policy , when and are unknown. We make the following standard assumption [4, 5, 6, 8].
Assumption 1. The Markov chain induced by the policy is aperiodic and irreducible.
Assumption 1 ensures that the Markov chain induced by admits a unique stationary distribution with full support. To isolate the challenges introduced by communication constraints, we adopt the commonly used i.i.d. stationary sampling model [5, 19, 20, 21]: at each time-step , the agent receives an independent transition sample , where , , and . The results in this paper can be extended to a single-trajectory Markovian setting using sub-sampling and blocking arguments [17, 22].
Linear Function Approximation (LFA). To accommodate scalability to large state spaces, one typically considers a parametric approximation of . The simplest form of such an approximation is when belongs to the linear subspace spanned by a set of basis vectors, where . Let be a matrix with k$-th column, and its -th row representing the feature vector for state . We then have , and , where is the parametric approximation vector. For our analysis, we make the standard assumption [5, 6, 8] that the columns of are linearly independent, and that the feature vectors are normalized, i.e., for each , During each epoch , the agent uses transition samples from the unknown MDP under policy to estimate the TD direction and transmits the encoded innovation over a noiseless, rate-limited channel. The server reconstructs the direction, updates its parameter to , and returns this parameter exactly over an unconstrained noiseless reverse channel.
.2 Given the above setup, the goal is to estimate the “best-fit" parameter that minimizes the distance between and with respect to (w.r.t.) a suitable norm.
The TD(0) Algorithm with LFA. For achieving this goal, we now introduce the classical TD(0) algorithm [23] which processes observation tuples generated by the policy to maintain a sequence of estimates of the best-fit parameter . To see how this is done, for any , define the TD(0) direction: . The standard TD(0) update is then given by
where is a suitable step-size sequence. Under our assumption of i.i.d. sampling from the stationary distribution , the steady-state “mean-path" TD(0) direction can be defined as: , where and . Under Assumption 1, and the assumptions we made on the feature matrix , it turns out that is invertible. Accordingly, define . In the seminal paper [4], the authors showed that under mild conditions, the iterate sequence generated by (2) converges asymptotically almost surely to , which is the unique fixed point of a certain projected Bellman equation. More recent work has established non-asymptotic finite-time convergence rates, proving that after iterations of (2), the squared error is on the order in expectation [5], [6], [8]. We investigate whether similar rates can be preserved subject to the communication constraints that we describe next.
Rate-Limited TD(0) Policy Evaluation. We study estimation of the TD(0) fixed point in the agent–server architecture illustrated in Figure 1. In this setup, an agent interacting directly with the MDP observes data tuples of the form and transmits encoded information to a server over a finite-capacity channel that supports noiseless and error-free transmission of bits per channel use. Complying with standard communication protocols in distributed/federated RL, we impose an additional information constraint that the agent can only transmit encoded estimates of the TD(0) update direction, but not the raw data tuples. The channel from the server to the agent is assumed to be lossless with infinite capacity. Given this communication model, our goal is to design (i) an encoding scheme at the agent, and (ii) a parameter update rule at the server that continues to guarantee convergence to (if possible). Furthermore, we seek to quantify the interplay between channel capacity and finite-time convergence rates.
Problem 1. Given i.i.d. stationary transition samples and a failure probability , construct an estimate of using fixed-length -bit agent-to-server messages, and establish a bound of the form: that holds with probability at least . Investigate whether with a suitably large capacity , it is possible to preserve the order-optimal rate of .
Challenges. Even for the standard TD(0) algorithm with LFA, it is non-trivial to obtain high-probability concentration bounds due to the randomness associated with the noisy TD update directions. In our setup, the channel from the agent to the server injects additional uncertainty by distorting the estimates generated by the agent. Thus, we need to contend with two different forms of uncertainty: one due to sampling, and the other due to finite-bit quantization. Nonetheless, in Section III, we develop an algorithm that manages to preserve the order-optimal rate of , using a total of just bits over a time-horizon of length .
The Proposed Algorithm
Midpoint Encoding. Before presenting our main approach outlined in Algorithm 1, we specify a key finite-bit encoding subroutine. Say we wish to encode a -dimensional vector using bits per coordinate, so that each message contains bits. The encoder then takes as input the vector , a radius which determines the encoder’s input range, and an integer precision . The encoder and decoder share , , and . To define the encoding operation for every , including when , we first clip to radius : if ; else, . We write , which, by definition, satisfies , and hence, , , where is the -th coordinate of . This informs a simple midpoint encoding scheme in which we partition the interval into bins of equal width. For each coordinate , let be the center of the bin containing . The quantized version of a vector can be succinctly denoted by , where . It should be clear that this midpoint encoding scheme requires precisely -bits per coordinate. The following simple result provides an useful bound on the quantization error.
Lemma 1. (Quantization Error) Suppose satisfies . Then
Proof. The proof is standard and we only provide it here for completeness. Since , each lies in . From the description of the midpoint encoder, recall that the -th component of , namely is the quantized version of , and by construction, . Thus, , from which, the claimed bound follows trivially.
In particular, if , then , and (3) yields . In what follows, we explain how our proposed BAQ-TD algorithm leverages the midpoint encoding subroutine described above.
Batched Adaptively Quantized TD: We now introduce our algorithm, BAQ-TD, which employs the principle of adaptive quantization to encode “innovations” in the TD(0) update direction. For our setting, this poses a challenge since such innovations inherit randomness from the sampling-induced noise in the update directions. Intuitively, by reducing the uncertainty of the innovation process, one can reduce the number of bits needed to encode the innovations with a given precision. To that end, our main idea is to maintain variance-reduced estimates of the TD(0) update direction at the agent by batching the samples collected online into epochs of suitably large length. In what follows, we provide the details of our two core algorithmic ideas: batched estimation and adaptive quantization.
Batched TD-direction estimation. We partition the horizon/sample budget into epochs of samples each, with . For epoch , define its sample indices by . At the beginning of each epoch , the server sends its current parameter , previous decoded direction , and radius to the agent. We will soon explain how , and are initialized and updated in every epoch. The agent then collects observation tuples sequentially based on the i.i.d. sampling model in Section II. Using these samples and the received parameter , the agent computes an estimate of the mean-path TD(0) direction as follows:
Given that each of the objects being averaged above feature a common “frozen” parameter , it is not hard to see that under our i.i.d. sampling model, is an unbiased estimate of with variance scaling inversely with the batch size . As we shall soon see, by controlling , one can in turn control the uncertainty of the innovation process , and the radius of the ball needed to contain such a process (with high probability).
Encoding and Decoding the Innovation. The agent forms the innovation , which measures the difference between the current estimated direction at the agent and the previously decoded direction at the server. Using the scalar midpoint encoder described earlier, the agent transmits a -bit message corresponding to the quantized signal , where . The server decodes the message to recover perfectly, and then uses it to reconstruct the TD(0) direction and update the model parameter as follows:
Algorithm 1 Batched Adaptively Quantized TD (BAQ-TD)
Input: satisfying the conditions of Theorem 1.
Initialize: Set and ; compute by (6); set as per (7).
for do
(●) Server (Downlink): Sends to the agent.
(●) Agent (Compute and transmit):
Draws i.i.d. tuples , where .
Computes using (4).
Sets and .
Sends a -bit message encoding the innovation using a scalar midpoint encoder.
(●) Server (Decode and update):
Decodes .
Sets and .
Computes by (8).
end for
Return .
where is a step-size that we will specify in the next section. It remains to explain how the radius is adaptively tuned in each epoch to contain the innovation process. To do so, given , a confidence level , and statistics and of the reward distribution (defined in Section II), set
and define the fixed batch-error allowance ; note that can be computed offline. The agent and server share these quantities and the initial parameter . We initialize the decoded direction and encoding radius as
Let be the quantization constant from Lemma 1. After updating the parameter, the server adjusts the encoding radius as follows:
The next server transmission supplies to the agent, ensuring that both parties use the same reference for the encoding-decoding process. This also enables the server to decode the sequence exactly from the received -bit agent messages. Let us now briefly explain the rationale behind the adaptive range-update rule in (8).
Adaptive encoding radius. The radius is chosen to contain the next innovation . The first term on the R.H.S. of (8), namely , is informed by Lemma 1, and bounds the reconstruction error in the current decoded direction whenever saturation is inactive, i.e., when . Since is computed at and corresponds to , the gap depends on the parameter change , explaining the second term on the R.H.S. of (8). Finally, the encoding radius needs to account for
the errors in the batched TD(0) estimation process. In this regard, we show later in Lemma 2 that, with probability at least , the empirical TD matrices and reward vectors are simultaneously within of and , respectively, across all batches. As a result, the precision level shows up in the last term of (8). Together with the initial radius , these bounds ensure inductively that every transmitted innovation satisfies with high-probability; see Lemma 3.
Our method processes samples per communication round, yielding parameter updates and fixed-length messages over the full sample budget. Thus, over the time-horizon of length , the total communication cost is bits. In the next section, we show that for a suitably chosen parameter , epochs suffice to obtain the desired rate. The steps of our algorithm are outlined in Algorithm 1, where ▶ and ▶ denote operations performed by the agent and the server, respectively.
Main Results
We now establish a finite-time convergence guarantee for BAQ-TD. To do so, let denote the parameter error, and define a coupled Lyapunov function that jointly tracks the parameter error and the encoding radius. Let be a diagonal matrix containing the entries of the stationary distribution along the diagonal, and define . Under Assumption 1 and the conditions we imposed on , one can verify that is positive definite with smallest eigenvalue . Defining , and recalling from (6), we can state our main result.
Theorem 1. (Finite-Time Convergence) Suppose Assumption 1 holds. Given , run Algorithm 1 with stepsize and precision satisfying . Choose and suppose that the total sample count satisfies . Then, with probability (w.p.) at least , the bound
holds simultaneously for all . Here, and are sufficiently large universal constants.
Each epoch uses samples and produces one parameter update and one -bit agent-to-server message. The total costs are therefore samples, messages, and transmitted bits. The following corollary, which follows directly from Theorem 1, combines these communication costs with the statistical guarantee.
Corollary 1. (Accuracy and Communication) Under the conditions of Theorem 1, choose and . Over the time horizon, BAQ-TD transmits fixed-length messages, each containing bits. The total number of bits transmitted is thus
For any , if satisfies the sample-size condition of Theorem 1, then with probability at least ,
where , and is a sufficiently large universal constant.
Discussion of Theorem 1 and Corollary 1. Theorem 1 provides a finite-time high-probability guarantee for TD learning with finite-bit communication. The first term in (9) is a geometrically decaying transient term of the form , where reflects the coupling between the parameter estimation error and errors due to quantization (captured by the encoding radius ). The second term in (9) is a statistical error term that shrinks with the sample-size . We discuss the sample and communication complexities of our method below.
Statistical accuracy. The statistical residual obtained in our analysis is of order , where recall that is the size of each epoch. Clearly, increasing reduces the residual, but comes at the expense of fewer contractive epochs to control the transient (since ). Fortunately, since the transient term decays exponentially in , setting suffices to achieve an overall rate of , as established in Corollary 1. Such a rate is consistent with prior non-asymptotic mean-squared error [5, 6, 8] and high-probability bounds [7] for TD(0), and is order-optimal in its dependence on the sample size .
Communication Costs. In terms of communication complexity, our results provide two key messages. First, we show that with , a fixed channel capacity of bits suffices to preserve the ideal rate of , i.e., we establish that above a certain finite channel capacity, it is possible to ensure no loss in performance. Notably, the requirement on that we identify depends only on the feature-dimension and “strong-convexity-like” parameter , but not on the batch size or total budget . Thus, even when the sample budget increases, the number of bits per message can continue to remain fixed.
While this settles the question of how much information needs to be sent per round, it leaves open the issue of determining how frequently the agent should communicate with the server. Since the number of communication rounds is precisely , and , we show that the number of such rounds exhibits a modest logarithmic scaling with the horizon . In sharp contrast, compressed TD schemes in [9, 10] communicate at each time-step, incurring a total communication cost that scales linearly with . Thus, we achieve an exponential improvement in communication costs relative to prior work, and provide the first results to show that one can continue to obtain high-probability rates on the order with a total of just bits.
Simulation Results
We evaluate the performance of BAQ-TD on a finite discounted Markov decision process with 100 states and discount factor . The mean reward at each state is bounded above by , and the reward-noise variance satisfies . The value function is approximated using features, with each feature vector normalized to have norm at most one. We compute the stationary distribution and the corresponding TD fixed point using the known model. Each plot in Figure 2 reports the average estimation error over 100 independent runs. Figure 2 illustrates how batching and quantization precision affect estimation accuracy. In the left panel, larger batches reduce the terminal error while keeping both the number of transmissions and the message length fixed, at the cost of additional samples. In the middle panel, increasing the precision reduces the gap to unquantized TD; with , the quantized and unquantized curves nearly overlap. Finally, the right panel provides empirical support for the statistical rate predicted by Theorem 1, with terminal error decaying approximately as for .

Figure 2. (Left) Evolution of the estimation error for BAQ-TD with batch sizes , precision , and epochs. (Middle) Results for precisions , compared with unquantized TD. (Right) Terminal estimation error versus sample budget for BAQ-TD with and unquantized TD. The dashed line shows the scaling suggested by our square-error bound.
Main Convergence Analysis
To prove Theorem 1, we first bound the estimation errors from batched estimation of the TD update direction in each epoch. To that end, recall that , and . For a generic transition sample , let . Due to feature normalization, . Consequently, since , we have . For each epoch , define the following:
where and . Then by (4). Also, under the i.i.d. stationary sampling model, we have and . We have the following result.
Lemma 2. (Operator Estimation) Define
Then , and on ,
simultaneously for all and .
Proof. We first control the empirical matrices. For , write . Feature normalization gives . Hence, for every realized batch and . Moreover, every entry satisfies . Since averages independent matrices with expectation , scalar Hoeffding’s inequality [24] yields, for every ,
The last inequality follows from and (6). A union bound over all entries and epochs then ensures that, with probability at least ,
simultaneously for . Here, denotes the Frobenius norm. Next, consider the empirical reward vectors. Let be a generic stationary transition tuple and fix . Since , we have . For every , define and using the reward assumption in Section II, we obtain:
Here, (i) follows by applying the conditional sub-Gaussian assumption to with scalar and using . For (ii), Hoeffding’s lemma applies to , which lies in and has mean . Therefore, is sub-Gaussian with variance proxy . Independence within each batch implies that is sub-Gaussian with variance proxy . By (6), . Scalar sub-Gaussian concentration therefore gives
again by (6). A union bound over the coordinates and epochs, followed by , gives simultaneously for all , with probability at least . Combining the matrix and vector bounds yields . On , for every epoch and every , the identity and the triangle inequality gives .
Next, we show that with high probability, every innovation lies within the encoding radius specified by (7) and (8).
Lemma 3. (No Saturation) On the event defined in (13), (7) and (8) imply for all . Therefore, by Lemma 1, the reconstruction error satisfies
Proof. We prove the claim on the event defined in (13). The reward bound and the feature bound from Section II give .
Since and , the initial innovation is . Applying (14) on gives . Thus, saturation is inactive at epoch 0. Suppose for all , where . Since , we have . Using , with defined in (4), the reconstruction update (5) gives . Lemma 1 then implies . For , we express as follows:
This decomposition separates the change in parameter from the difference between the two batch estimates evaluated at . On , and , since each empirical operator is within of its expectation. Thus, using and , we obtain . Induction establishes and (16) for every transmitted innovation.
Define the sampling error . The decoded direction then admits the decomposition . Here accounts for batch estimation and for finite-bit reconstruction. Recall that . Since , we have . Our next result provides bounds on the sampling error , reconstruction error , and encoding radius as a function of the sub-optimality .
Lemma 4. (Direction and Radius Bounds) Suppose . On the event defined in (13), the following bounds hold simultaneously for every :
Proof. By (14), on , . Using and the triangle inequality proves (17). Next, apply to . By (17) and (16),
where the last inequality uses . This proves (18). To bound the next radius, substitute into (8). Using from (16) and from (14), we obtain
Since , we have and . Using gives
Squaring this bound and applying yields the following:
Using and the operator-norm bound gives . Also, . Substituting these bounds proves (19).
The final piece we require is the following result from [5].
where recall that , and is the smallest eigenvalue of . We now combine these bounds through the joint Lyapunov function to prove Theorem 1.
▪ Proof of Theorem 1. By Lemma 2, the event defined in (13) has probability at least . We prove the claim on this event. Recall that . The prescribed precision gives . Since , the sample-size condition implies . Taking the universal constant therefore ensures that . The stepsize satisfies . Lemma 3 gives and for every . The sampling and reconstruction errors thus satisfy the bounds in Lemma 4.
We first derive a recursion for . The parameter update and the decomposition of give . From this and (21), we obtain
Young’s inequality gives . Together with , this yields
Because , the coefficient of the final term is at most . Substituting (18) therefore gives
Adding times (19) to (22) and collecting terms gives
Since and , we have and
Moreover, the stepsize and batch-size bounds give . Thus, the coefficients of and in (23) are both at most . Finally, bounds the additive term by . Substituting these estimates into (23) and using yields
for every . Iterating (24) gives
for every . Since , the geometric sum is bounded from above by . Using in (25) and dropping the nonnegative term , we obtain
The same bound holds at because . Thus, (26) holds simultaneously for all on the single event ; no additional union bound is needed.
To express the statistical contribution in terms of the sample budget, substitute into (26). This gives . Under the prescribed choice , this becomes , proving (9).
Conclusion
We studied policy evaluation with linear function approximation over a rate-limited channel and proposed BAQ-TD, which combines model-based variance reduction with adaptive quantization of innovations. Our high-probability guarantee matches the unquantized TD rate, requiring a modest logarithmic-in-sample size communication budget.
References
- [1]S. Tatikonda and S. Mitter, “Control under communication constraints,” IEEE Transactions on Automatic Control, pp. 1056–1068, 2004.DOI
- [2]G. N. Nair, F. Fagnani, S. Zampieri, and R. J. Evans, “Feedback control under data rate constraints: An overview,” Proceedings of the IEEE, vol. 95, no. 1, pp. 108–137, 2007.DOI
- [3]L. Schenato, B. Sinopoli, M. Franceschetti, K. Poolla, and S. S. Sastry, “Foundations of control and estimation over lossy networks,” Proceedings of the IEEE, vol. 95, no. 1, pp. 163–187, 2007.
- [4]J. N. Tsitsiklis and B. Van Roy, “An analysis of temporal-difference learning with function approximation,” in IEEE Transactions on Automatic Control, 1997.DOI
- [5]J. Bhandari, D. Russo, and R. Singal, “A finite time analysis of temporal difference learning with linear function approximation,” in Conference on learning theory. PMLR, 2018, pp. 1691–1692.arxiv.org/abs/1806.02450
- [6]R. Srikant and L. Ying, “Finite-time error bounds for linear stochastic approximation andtd learning,” in Conference on Learning Theory. PMLR, 2019, pp. 2803–2830.arxiv.org/abs/1902.00923
- [7]G. Patil, L. Prashanth, D. Nagaraj, and D. Precup, “Finite Time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation,” in International Conference on Artificial Intelligence and Statistics. PMLR, 2023, pp. 5438–5448.arxiv.org/abs/2210.05918
- [8]A. Mitra, “A simple finite-time analysis of td learning with linear function approximation,” IEEE Transactions on Automatic Control, vol. 70, no. 2, pp. 1388–1394, 2024.arxiv.org/abs/2403.02476
- [9]A. Mitra, G. J. Pappas, and H. Hassani, “Temporal difference learning with compressed updates: Error-feedback meets reinforcement learning,” arXiv preprint arXiv:2301.00944, 2023.arxiv.org/abs/2301.00944
- [10]N. Dal Fabbro, A. Mitra, and G. J. Pappas, “Federated td learning over finite-rate erasure channels: Linear speedup under markovian sampling,” IEEE Control Systems Letters, vol. 7, pp. 2461–2466, 2023.
- [11]O. A. Hanna, L. Yang, and C. Fragouli, “Solving multi-arm bandit using a few bits of communication,” in Proceedings of the 25th International Conference on Artificial Intelligence and Statistics, vol. 151. PMLR, 2022, pp. 11 215–11 236.arxiv.org/abs/2111.06067
- [12]S. Salgia and Q. Zhao, “Distributed linear bandits under communication constraints,” in International Conference on Machine Learning. PMLR, 2023, pp. 29 845–29 875.arxiv.org/abs/2211.02212
- [13]A. Mitra, H. Hassani, and G. J. Pappas, “Linear stochastic bandits over a bit-constrained channel,” in Learning for Dynamics and Control Conference. PMLR, 2023, pp. 1387–1399.arxiv.org/abs/2203.01198
- [14]S. Salgia and Y. Chi, “The sample-communication complexity trade-off in federated q-learning,” Advances in Neural Information Processing Systems, vol. 37, pp. 39 694–39 747, 2024.arxiv.org/abs/2408.16981
- [15]H. Yang, L. Huang, S. Dey, and L. Shi, “Over-the-air federated policy gradient,” in ICC 2024-IEEE International Conference on Communications. IEEE, 2024, pp. 5571–5576.arxiv.org/abs/2310.16592
- [16]A. Mitra, L. Ye, and V. Gupta, “Towards model-free LQR control over rate-limited channels,” in Proceedings of the 6th Annual Learning for Dynamics and Control Conference, vol. 242, 2024, pp. 1253–1265.
- [17]S. Maity and A. Mitra, “Adversarially-robust TD learning with markovian data: Finite-time rates and fundamental limits,” in Proceedings of the 28th International Conference on Artificial Intelligence and Statistics, ser. Proceedings of Machine Learning Research, vol. 258. PMLR, 03–05 May 2025, pp. 2431–2439.arxiv.org/abs/2502.04662
- [18]——, “Corruption-tolerant asynchronous Q-learning with near-optimal rates,” in Proceedings of the 43rd International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, vol. 306. PMLR, 06–11 Jul 2026, pp. 85 782–85 827.
- [19]N. Korda and P. La, “On TD(0) with function approximation: Concentration bounds and a centered variant with exponential convergence,” in International conference on machine learning. PMLR, 2015, pp. 626–634.arxiv.org/abs/1411.3224
- [20]G. Dalal, B. Szörényi, G. Thoppe, and S. Mannor, “Finite sample analyses for td (0) with function approximation,” in Proceedings of the AAAI Conference on Artificial Intelligence, vol. 32, no. 1, 2018.arxiv.org/abs/1704.01161
- [21]C. Narayanan and C. Szepesvári, “Finite time bounds for temporal difference learning with function approximation: Problems with some “state-of-the-art” results,” Technical report, Tech. Rep., 2017.
- [22]R. Dorfman and K. Y. Levy, “Adapting to mixing time in stochastic optimization with markovian data,” in International Conference on Machine Learning. PMLR, 2022, pp. 5429–5446.arxiv.org/abs/2202.04428
- [23]R. S. Sutton, “Learning to predict by the methods of temporal differences,” Machine learning, vol. 3, no. 1, pp. 9–44, 1988.DOI
- [24]F. Chung and L. Lu, “Concentration inequalities and martingale inequalities: a survey,” Internet mathematics, vol. 3, no. 1, pp. 79–127, 2006.