betaFeedback

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

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.

Agent-server architecture for BAQ–TD

Figure 1. Agent-server architecture for BAQ–TD, presented in Algorithm 1.

Given this premise, we ask: With a time-horizon of TT time-steps (equivalently, a sample budget of TT), 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 TT, 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 TT, 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 TT samples, in Theorem 1, we provide a high-probability convergence rate on the order of O~(1/T)\widetilde{O}(1/T) 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 TT. 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 TT, but rather scales as dlog⁡(d/ω)d\log(d/\omega), where dd is the dimension of the value function parameter, and ω\omega is a problem-dependent constant that we specify in Section IV. Moreover, we show that O~(log⁡(T))\widetilde{O}(\log(T)) transmissions suffice to preserve order-optimal rates, leading to a total communication cost on the order O~(dlog⁡(T))\widetilde{O}(d\log(T)).

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 M=(S,A,P,R,γ)\mathcal{M} = (\mathcal{S}, \mathcal{A}, \mathcal{P}, \mathcal{R}, \gamma), where S\mathcal{S} and A\mathcal{A} are the (finite) state and action spaces, P\mathcal{P} is the collection of transition kernels, R\mathcal{R} specifies reward functions, and γ∈[0,1)\gamma\in[0,1) is the discount factor. We consider deterministic policies, where each deterministic policy μ:S→A\mu: \mathcal{S} \to\mathcal{A} maps a state to an action. A fixed policy μ\mu induces a Markov reward process with a transition matrix PμP_\mu, and a reward function Rμ:S→RR_\mu: \mathcal{S} \to\mathbb{R}. For each s∈Ss \in\mathcal{S}, let r(s)r(s) denote the noisy random one-step reward with distribution Dμ(⋅∣s)\mathcal{D}_\mu(\cdot\mid s) and mean Rμ(s)=E[r(s)]R_\mu(s) = \mathbb{E}[r(s)]. We assume1 that ∣Rμ(s)∣≤rˉ|R_\mu(s)| \le\bar{r} and that the centered reward r(s)−Rμ(s)r(s) - R_\mu(s) is sub-Gaussian with variance proxy σ2\sigma^2, i.e., E[exp⁡(λ(r(s)−Rμ(s)))]≤exp⁡(λ2σ2/2)\mathbb{E}[\exp(\lambda(r(s) - R_\mu(s)))] \le\exp(\lambda^2\sigma^2/2) for every s∈Ss \in\mathcal{S} and λ∈R\lambda\in\mathbb{R}. The long-term return obtained from playing policy μ\mu in the MDP M\mathcal{M}, starting from an initial state ss, is given by the value function Vμ(s)V_\mu(s), defined formally as

Vμ(s)=E[∑t=0∞γtRμ(st)∣s0=s,μ],(1)V_\mu(s) = \mathbb{E}\left[\left.\sum_{t=0}^{\infty}\gamma^t R_\mu(s_t)\right|s_0=s,\mu\right], \tag*{(1)}

where sts_t represents the state of the Markov chain (induced by μ\mu) at time tt, with s0=ss_0=s. 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 VμV_\mu corresponding to a given policy μ\mu, when Rμ=[Rμ(s)]s∈S∈R∣S∣R_\mu= [R_\mu(s)]_{s\in\mathcal{S}} \in\mathbb{R}^{|\mathcal{S}|} and PμP_\mu are unknown. We make the following standard assumption [4, 5, 6, 8].

Assumption 1. The Markov chain sts_t induced by the policy μ\mu is aperiodic and irreducible.

Assumption 1 ensures that the Markov chain induced by μ\mu admits a unique stationary distribution ν\nu 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 tt, the agent receives an independent transition sample (st,rt,st′)(s_t,r_t,s'_t), where st∼νs_t\sim\nu, st′∼Pμ(st,⋅)s'_t\sim P_\mu(s_t,\cdot), and rt∼Dμ(⋅∣st)r_t\sim\mathcal{D}_\mu(\cdot|s_t). 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 V^θ\widehat{V}_\theta of VμV_\mu. The simplest form of such an approximation is when V^θ\widehat{V}_\theta belongs to the linear subspace spanned by a set {ϕk}k∈[d]\{\phi_k\}_{k\in[d]} of d≪∣S∣:=pd \ll|\mathcal{S}| := p basis vectors, where ϕk=[ϕk(1),…,ϕk(p)]⊤∈Rp\phi_k = [\phi_k(1),\ldots,\phi_k(p)]^\top\in\mathbb{R}^p. Let Φ∈Rp×d\Phi\in\mathbb{R}^{p\times d} be a matrix with ϕkasits\phi_k as itsk$-th column, and its ss-th row ϕ(s)∈Rd\phi(s) \in\mathbb{R}^d representing the feature vector for state ss. We then have V^θ=Φθ\widehat{V}_\theta= \Phi\theta, and V^θ(s)=∑k=1dθkϕk(s)=ϕ(s)⊤θ\widehat{V}_\theta(s) = \sum_{k=1}^{d}\theta_k\phi_k(s) = \phi(s)^\top\theta, where θ=[θ1,…,θd]⊤∈Rd\theta= [\theta_1,\ldots,\theta_d]^\top\in\mathbb{R}^d is the parametric approximation vector. For our analysis, we make the standard assumption [5, 6, 8] that the columns of Φ\Phi are linearly independent, and that the feature vectors are normalized, i.e., for each s∈Ss \in\mathcal{S}, During each epoch kk, the agent uses HH transition samples from the unknown MDP under policy μ\mu 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 θk+1\theta_{k+1}, and returns this parameter exactly over an unconstrained noiseless reverse channel.

∥ϕ(s)∥≤1\|\phi(s)\| \le1.2 Given the above setup, the goal is to estimate the “best-fit" parameter θ∗\theta^* that minimizes the distance between V^θ\hat V_\theta and VμV_\mu 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 {Ot=(st,rt,st′)}\{O_t=(s_t,r_t,s'_t)\} generated by the policy μ\mu to maintain a sequence of estimates {θt}\{\theta_t\} of the best-fit parameter θ∗\theta^*. To see how this is done, for any θ∈Rd\theta\in\mathbb{R}^d, define the TD(0) direction: gt(θ)=[rt+γϕ(st′)⊤θ−ϕ(st)⊤θ]ϕ(st)g_t(\theta)=[r_t+\gamma\phi(s'_t)^\top\theta-\phi(s_t)^\top\theta]\phi(s_t). The standard TD(0) update is then given by

θt+1=θt+αtgt(θt),(2)\theta_{t+1}=\theta_t+\alpha_tg_t(\theta_t), \tag*{(2)}

where {αt}∈(0,1)\{\alpha_t\}\in(0,1) is a suitable step-size sequence. Under our assumption of i.i.d. sampling from the stationary distribution ν\nu, the steady-state “mean-path" TD(0) direction can be defined as: gˉ(θ):=E[gt(θ)]=b−Aθ\bar g(\theta):=\mathbb{E}[g_t(\theta)]=b-A\theta, where A:=E[ϕ(st)(ϕ(st)−γϕ(st′))⊤]A:=\mathbb{E}\left[\phi(s_t)(\phi(s_t)-\gamma\phi(s'_t))^\top\right] and b:=E[rtϕ(st)]b:=\mathbb{E}[r_t\phi(s_t)]. Under Assumption 1, and the assumptions we made on the feature matrix Φ\Phi, it turns out that AA is invertible. Accordingly, define θ∗=A−1b\theta^*=A^{-1}b. In the seminal paper [4], the authors showed that under mild conditions, the iterate sequence {θt}\{\theta_t\} generated by (2) converges asymptotically almost surely to θ∗\theta^*, 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 TT iterations of (2), the squared error ∥θT−θ∗∥2\|\theta_T-\theta^*\|^2 is on the order O~(1/T)\widetilde O(1/T) 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 θ∗\theta^* in the agent–server architecture illustrated in Figure 1. In this setup, an agent interacting directly with the MDP M\mathcal M observes data tuples of the form {Ot=(st,rt,st′)}\{O_t=(s_t,r_t,s'_t)\} and transmits encoded information to a server over a finite-capacity channel that supports noiseless and error-free transmission of BB 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 θ∗\theta^* (if possible). Furthermore, we seek to quantify the interplay between channel capacity and finite-time convergence rates.

Problem 1. Given TT i.i.d. stationary transition samples {(st,rt,st′)}t=0T−1\{(s_t,r_t,s'_t)\}_{t=0}^{T-1} and a failure probability δ∈(0,1)\delta\in(0,1), construct an estimate θ^\hat\theta of θ∗\theta^* using fixed-length BB-bit agent-to-server messages, and establish a bound of the form: ∥θ^−θ∗∥2≤e(δ,T)\|\hat\theta-\theta^*\|^2\le e(\delta,T) that holds with probability at least 1−δ1-\delta. Investigate whether with a suitably large capacity BB, it is possible to preserve the order-optimal rate of e(δ,T)=O~(log⁡(1/δ)/T)e(\delta,T)=\widetilde O(\log(1/\delta)/T).

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 O~(1/T)\widetilde O(1/T), using a total of just O~(dlog⁡(T))\widetilde O(d\log(T)) bits over a time-horizon of length TT.

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 dd-dimensional vector uu using mm bits per coordinate, so that each message contains B=dmB=dm bits. The encoder then takes as input the vector u∈Rdu\in\mathbb{R}^d, a radius ρ>0\rho>0 which determines the encoder’s input range, and an integer precision m≥1m\ge1. The encoder and decoder share ρ\rho, dd, and mm. To define the encoding operation for every uu, including when ∥u∥>ρ\|u\|>\rho, we first clip uu to radius ρ\rho: sat⁡ρ(u):=u\operatorname{sat}_{\rho}(u):=u if ∥u∥≤ρ\|u\|\le\rho; else, sat⁡ρ(u):=ρu/∥u∥\operatorname{sat}_{\rho}(u):=\rho u/\|u\|. We write v=sat⁡ρ(u)v=\operatorname{sat}_{\rho}(u), which, by definition, satisfies ∥v∥≤ρ\|v\|\le\rho, and hence, vi∈[−ρ,ρ]v_i\in[-\rho,\rho], ∀i∈[d]\forall i\in[d], where viv_i is the ii-th coordinate of vv. This informs a simple midpoint encoding scheme in which we partition the interval [−ρ,ρ][-\rho,\rho] into 2m2^m bins of equal width. For each coordinate vi∈[−ρ,ρ]v_i\in[-\rho,\rho], let v~i\tilde v_i be the center of the bin containing viv_i. The quantized version of a vector u∈Rdu\in\mathbb{R}^d can be succinctly denoted by Qm,ρ(v):=[v~1 v~2 ⋯ v~d]⊤Q_{m,\rho}(v):=[\tilde v_1\ \tilde v_2\ \cdots\ \tilde v_d]^\top, where v=sat⁡ρ(u)v=\operatorname{sat}_{\rho}(u). It should be clear that this midpoint encoding scheme requires precisely mm-bits per coordinate. The following simple result provides an useful bound on the quantization error.

Lemma 1. (Quantization Error) Suppose v∈Rdv\in\mathbb{R}^d satisfies ∥v∥≤ρ\|v\|\le\rho. Then

∥Qm,ρ(v)−v∥≤ηρ,η=d2m.(3)\|Q_{m,\rho}(v)-v\|\le\eta\rho,\qquad\eta=\frac{\sqrt d}{2^m}. \tag*{(3)}

Proof. The proof is standard and we only provide it here for completeness. Since ∥v∥≤ρ\|v\|\le\rho, each viv_i lies in [−ρ,ρ][-\rho,\rho]. From the description of the midpoint encoder, recall that the ii-th component of Qm,ρ(v)Q_{m,\rho}(v), namely v~i\tilde{v}_i is the quantized version of viv_i, and by construction, ∣vi−v~i∣≤ρ/2m|v_i-\tilde{v}_i|\leq\rho/2^m. Thus, ∥Qm,ρ(v)−v∥2=∑i=1d∣v~i−vi∣2≤dρ2/22m\|Q_{m,\rho}(v)-v\|^2=\sum_{i=1}^d|\tilde{v}_i-v_i|^2\leq d\rho^2/2^{2m}, from which, the claimed bound follows trivially.

In particular, if ∥u∥≤ρ\|u\|\leq\rho, then sat⁡ρ(u)=u\operatorname{sat}_{\rho}(u)=u, and (3) yields ∥Qm,ρ(sat⁡ρ(u))−u∥≤ηρ\|Q_{m,\rho}(\operatorname{sat}_{\rho}(u))-u\|\leq\eta\rho. 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 TT 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 TT into KK epochs of HH samples each, with T=KHT=KH. For epoch k=0,…,K−1k=0,\ldots,K-1, define its sample indices by Ik:={kH,…,(k+1)H−1}\mathcal{I}_k:=\{kH,\ldots,(k+1)H-1\}. At the beginning of each epoch kk, the server sends its current parameter θk∈Rd\theta_k\in\mathbb{R}^d, previous decoded direction hk−1h_{k-1}, and radius ρk\rho_k to the agent. We will soon explain how θk\theta_k, hk−1h_{k-1} and ρk\rho_k are initialized and updated in every epoch. The agent then collects HH observation tuples {(sj,rj,sj′)}j∈Ik\{(s_j,r_j,s'_j)\}_{j\in\mathcal{I}_k} sequentially based on the i.i.d. sampling model in Section II. Using these samples and the received parameter θk\theta_k, the agent computes an estimate YkY_k of the mean-path TD(0) direction gˉ(θk)\bar{g}(\theta_k) as follows:

Yk=1H∑j∈Ikϕ(sj)[rj+γϕ(sj′)⊤θk−ϕ(sj)⊤θk].(4)Y_k=\frac{1}{H}\sum_{j\in\mathcal{I}_k}\phi(s_j)\left[r_j+\gamma\phi(s'_j)^\top\theta_k-\phi(s_j)^\top\theta_k\right]. \tag*{(4)}

Given that each of the objects being averaged above feature a common “frozen” parameter θk\theta_k, it is not hard to see that under our i.i.d. sampling model, YkY_k is an unbiased estimate of gˉ(θk)\bar{g}(\theta_k) with variance scaling inversely with the batch size HH. As we shall soon see, by controlling HH, one can in turn control the uncertainty of the innovation process {uk:=Yk−hk−1}\{u_k:=Y_k-h_{k-1}\}, and the radius ρk\rho_k of the ball needed to contain such a process (with high probability).

  • Encoding and Decoding the Innovation. The agent forms the innovation uk:=Yk−hk−1u_k:=Y_k-h_{k-1}, 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 dmdm-bit message corresponding to the quantized signal zk:=Qm,ρk(vk)z_k:=Q_{m,\rho_k}(v_k), where vk=sat⁡ρk(uk)v_k=\operatorname{sat}_{\rho_k}(u_k). The server decodes the message to recover zkz_k perfectly, and then uses it to reconstruct the TD(0) direction and update the model parameter as follows:

hk=hk−1+zk,θk+1=θk+αhk,(5)h_k=h_{k-1}+z_k,\qquad\theta_{k+1}=\theta_k+\alpha h_k, \tag*{(5)}

Algorithm 1 Batched Adaptively Quantized TD (BAQ-TD)

  1. Input: T,K,δ,α,m,θ0T,K,\delta,\alpha,m,\theta_0 satisfying the conditions of Theorem 1.

  2. Initialize: Set H=T/KH=T/K and η=d/2m\eta=\sqrt{d}/2^m; compute CδC_\delta by (6); set h−1,ρ0h_{-1},\rho_0 as per (7).

  3. for k=0,…,K−1k=0,\ldots,K-1 do

  4. (●) Server (Downlink): Sends (θk,hk−1,ρk)(\theta_k,h_{k-1},\rho_k) to the agent.

  5. (●) Agent (Compute and transmit):

    • Draws i.i.d. tuples {(sj,rj,sj′)}j∈Ik\{(s_j,r_j,s'_j)\}_{j\in\mathcal{I}_k}, where ∣Ik∣=H|\mathcal{I}_k|=H.

    • Computes YkY_k using (4).

    • Sets uk=Yk−hk−1u_k=Y_k-h_{k-1} and vk=sat⁡ρk(uk)v_k=\operatorname{sat}_{\rho_k}(u_k).

    • Sends a dmdm-bit message encoding the innovation zk=Qm,ρk(vk)z_k=Q_{m,\rho_k}(v_k) using a scalar midpoint encoder.

  6. (●) Server (Decode and update):

    • Decodes zk=Qm,ρk(vk)z_k=Q_{m,\rho_k}(v_k).

    • Sets hk=hk−1+zkh_k=h_{k-1}+z_k and θk+1=θk+αhk\theta_{k+1}=\theta_k+\alpha h_k.

    • Computes ρk+1\rho_{k+1} by (8).

  7. end for

  8. Return θK\theta_K.

where α\alpha is a step-size that we will specify in the next section. It remains to explain how the radius ρk\rho_k is adaptively tuned in each epoch to contain the innovation process. To do so, given K,H,m≥1K,H,m\geq1, a confidence level δ∈(0,1)\delta\in(0,1), and statistics rˉ\bar{r} and σ\sigma of the reward distribution (defined in Section II), set

Cδ2=2max⁡{4d2, d(rˉ2+σ2)}log⁡(4Kd2δ),(6)C_\delta^2=2\max\left\{4d^2,\ d(\bar{r}^2+\sigma^2)\right\}\log\left(\frac{4Kd^2}{\delta}\right), \tag*{(6)}

and define the fixed batch-error allowance ϵH:=Cδ/H\epsilon_H:=C_\delta/\sqrt{H}; note that ϵH\epsilon_H can be computed offline. The agent and server share these quantities and the initial parameter θ0\theta_0. We initialize the decoded direction and encoding radius as

h−1=0,ρ0=rˉ+2∥θ0∥+ϵH(∥θ0∥+1).(7)h_{-1}=0,\qquad\rho_0=\bar{r}+2\|\theta_0\|+\epsilon_H(\|\theta_0\|+1). \tag*{(7)}

Let η=d/2m\eta=\sqrt{d}/2^m be the quantization constant from Lemma 1. After updating the parameter, the server adjusts the encoding radius as follows:

ρk+1=ηρk+2α∥hk∥+2ϵH(∥θk∥+1).(8)\rho_{k+1}=\eta\rho_k+2\alpha\|h_k\|+2\epsilon_H(\|\theta_k\|+1). \tag*{(8)}

The next server transmission supplies (θk+1,hk,ρk+1)(\theta_{k+1},h_k,\rho_{k+1}) to the agent, ensuring that both parties use the same reference for the encoding-decoding process. This also enables the server to decode the {zk}\{z_k\} sequence exactly from the received B=dmB=dm-bit agent messages. Let us now briefly explain the rationale behind the adaptive range-update rule in (8).

  • Adaptive encoding radius. The radius ρk\rho_k is chosen to contain the next innovation Yk+1−hkY_{k+1}-h_k. The first term on the R.H.S. of (8), namely ηρk\eta\rho_k, is informed by Lemma 1, and bounds the reconstruction error in the current decoded direction whenever saturation is inactive, i.e., when ∥uk∥≤ρk\|u_k\|\leq\rho_k. Since Yk+1Y_{k+1} is computed at θk+1\theta_{k+1} and hkh_k corresponds to θk\theta_k, the gap Yk+1−hkY_{k+1}-h_k depends on the parameter change θk+1−θk=αhk\theta_{k+1}-\theta_k=\alpha h_k, 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 1−δ1-\delta, the empirical TD matrices and reward vectors are simultaneously within ϵH\epsilon_H of AA and bb, respectively, across all KK batches. As a result, the precision level ϵH\epsilon_H shows up in the last term of (8). Together with the initial radius ρ0\rho_0, these bounds ensure inductively that every transmitted innovation satisfies ∥uk∥≤ρk\lVert u_k\rVert\leq\rho_k with high-probability; see Lemma 3.

Our method processes HH samples per communication round, yielding KK parameter updates and KK fixed-length messages over the full sample budget. Thus, over the time-horizon of length TT, the total communication cost is KdmKdm bits. In the next section, we show that for a suitably chosen parameter mm, K=O(log⁡T)K = \mathcal{O}(\log T) epochs suffice to obtain the desired O~(1/T)\widetilde{\mathcal{O}}(1/T) 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 ek:=θk−θ⋆e_k := \theta_k - \theta^\star denote the parameter error, and define a coupled Lyapunov function Vk:=∥ek∥2+αρk2V_k := \lVert e_k\rVert^2 + \alpha\rho_k^2 that jointly tracks the parameter error and the encoding radius. Let DD be a diagonal matrix containing the entries of the stationary distribution ν\nu along the diagonal, and define Σ=Φ⊤DΦ\Sigma= \Phi^\top D\Phi. Under Assumption 1 and the conditions we imposed on Φ\Phi, one can verify that Σ\Sigma is positive definite with smallest eigenvalue ω~∈(0,1)\widetilde{\omega} \in(0,1). Defining ω:=ω~(1−γ)\omega:= \widetilde{\omega}(1-\gamma), and recalling CδC_\delta from (6), we can state our main result.

Theorem 1. (Finite-Time Convergence) Suppose Assumption 1 holds. Given δ∈(0,1)\delta\in(0,1), run Algorithm 1 with stepsize α∈(0,ω/32]\alpha\in(0,\omega/32] and precision satisfying m≥⌈12log⁡2(64dω)⌉m \geq\left\lceil\frac{1}{2}\log_2\left(\frac{64d}{\omega}\right)\right\rceil. Choose K=⌈c1log⁡T/(αω)⌉K = \lceil c_1 \log T/(\alpha\omega)\rceil and suppose that the total sample count T=KHT = KH satisfies T≥c2KCδ2/ω2T \geq c_2KC_\delta^2/\omega^2. Then, with probability (w.p.) at least 1−δ1-\delta, the bound

∥θk−θ⋆∥2≤(1−αω)kV0+O(Cδ2(1+∥θ⋆∥)2log⁡Tαω3T)(9)\lVert\theta_k-\theta^\star\rVert^2 \leq(1-\alpha\omega)^k V_0+\mathcal{O}\left(\frac{C_\delta^2(1+\lVert\theta^\star\rVert)^2\log T}{\alpha\omega^3T}\right) \tag*{(9)}

holds simultaneously for all k∈[K]k \in[K]. Here, V0=∥θ0−θ⋆∥2+αρ02V_0 = \lVert\theta_0-\theta^\star\rVert^2+\alpha\rho_0^2 and c1,c2c_1,c_2 are sufficiently large universal constants.

Each epoch uses HH samples and produces one parameter update and one dmdm-bit agent-to-server message. The total costs are therefore KHKH samples, KK messages, and KdmKdm 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 m=⌈12log⁡2(64d/ω)⌉m = \left\lceil\frac{1}{2}\log_2(64d/\omega)\right\rceil and α=ω/32\alpha= \omega/32. Over the T=KHT = KH time horizon, BAQ-TD transmits K=⌈32c1log⁡T/(ω2)⌉K = \lceil32c_1\log T/(\omega^2)\rceil fixed-length messages, each containing dmdm bits. The total number of bits transmitted is thus

Kdm=O(dlog⁡(d/ω)ω2log⁡T).(10)Kdm=\mathcal{O}\left(\frac{d\log(d/\omega)}{\omega^2}\log T\right). \tag*{(10)}

For any δ∈(0,1)\delta\in(0,1), if TT satisfies the sample-size condition of Theorem 1, then with probability at least 1−δ1-\delta,

∥θK−θ⋆∥2≤V0T+Cδlog⁡Tω2δlog⁡(d2log⁡Tω2δ),(11)\lVert\theta_K-\theta^\star\rVert^2 \leq\frac{V_0}{T}+\frac{C_\delta\log T}{\omega^2\delta}\log\left(\frac{d^2\log T}{\omega^2\delta}\right), \tag*{(11)}

where Cρ=C1C12(1+∥θ⋆∥)2max⁡{4d2,d(rˉ2+σ2)}/ω4C_\rho= C_1C_1^2(1+\lVert\theta^\star\rVert)^2\max\{4d^2,d(\bar r^2+\sigma^2)\}/\omega^4, and C>0C>0 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 e−αωkV0e^{-\alpha\omega k}V_0, where V0=∥e0∥2+αρ02V_0 = \lVert e_0\rVert^2+\alpha\rho_0^2 reflects the coupling between the parameter estimation error and errors due to quantization (captured by the encoding radius ρ\rho). The second term in (9) is a statistical error term that shrinks with the sample-size TT. We discuss the sample and communication complexities of our method below.

  • Statistical accuracy. The statistical residual obtained in our analysis is of order Cδ2(1+∥θ⋆∥)2/(ω2H)C_\delta^2(1+\lVert\theta^\star\rVert)^2/(\omega^2H), where recall that HH is the size of each epoch. Clearly, increasing HH reduces the residual, but comes at the expense of fewer contractive epochs KK to control the transient (since T=KHT=KH). Fortunately, since the transient term decays exponentially in KK, setting K=O(log⁡(T))K=\mathcal{O}(\log(T)) suffices to achieve an overall rate of O~(1/T)\widetilde{\mathcal{O}}(1/T), 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 TT.

  • Communication Costs. In terms of communication complexity, our results provide two key messages. First, we show that with m=O(log⁡(d/ω))m=\mathcal{O}(\log(d/\omega)), a fixed channel capacity of B=dmB=dm bits suffices to preserve the ideal rate of O~(1/T)\widetilde{\mathcal{O}}(1/T), i.e., we establish that above a certain finite channel capacity, it is possible to ensure no loss in performance. Notably, the requirement on mm that we identify depends only on the feature-dimension dd and “strong-convexity-like” parameter ω\omega, but not on the batch size HH or total budget TT. Thus, even when the sample budget TT 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 KK, and K=log⁡(T)K=\log(T), we show that the number of such rounds exhibits a modest logarithmic scaling with the horizon TT. In sharp contrast, compressed TD schemes in [9, 10] communicate at each time-step, incurring a total communication cost that scales linearly with TT. 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 O~(log⁡(1/δ)/T)\widetilde{\mathcal{O}}(\log(1/\delta)/T) with a total of just O(dlog⁡(T))\mathcal{O}(d\log(T)) bits.

Simulation Results

We evaluate the performance of BAQ-TD on a finite discounted Markov decision process with 100 states and discount factor γ=0.5\gamma= 0.5. The mean reward at each state is bounded above by rˉ≤5\bar{r} \le5, and the reward-noise variance satisfies σ2≤1\sigma^2 \le1. The value function is approximated using d=10d = 10 features, with each feature vector normalized to have norm at most one. We compute the stationary distribution and the corresponding TD fixed point θ⋆\theta^\star using the known model. Each plot in Figure 2 reports the average ℓ2\ell_2 estimation error Ek=∥θk−θ⋆∥2E_k = \lVert\theta_k-\theta^\star\rVert_2 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 m=16m = 16, 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 EK=∥θK−θ⋆∥2E_K = \lVert\theta_K-\theta^\star\rVert_2 decaying approximately as 1/T1/\sqrt{T} for m∈{12,16}m \in\{12, 16\}.

Evolution of the estimation error and terminal estimation error

Figure 2. (Left) Evolution of the estimation error Ek=∥θk−θ⋆∥2E_k = \lVert\theta_k-\theta^\star\rVert_2 for BAQ-TD with batch sizes H∈{512,2048,8192}H \in\{512, 2048, 8192\}, precision m=16m = 16, and K=1000K = 1000 epochs. (Middle) Results for precisions m∈{10,12,16}m \in\{10, 12, 16\}, compared with unquantized TD. (Right) Terminal estimation error EK=∥θK−θ⋆∥2E_K = \lVert\theta_K-\theta^\star\rVert_2 versus sample budget TT for BAQ-TD with m∈{12,16}m \in\{12, 16\} and unquantized TD. The dashed line shows the T−1/2T^{-1/2} 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 ϵH=Cδ/H\epsilon_H = C_\delta/\sqrt{H}, and η=d/2m\eta= \sqrt{d}/2^m. For a generic transition sample (s,r,s′)(s,r,s'), let B:=ϕ(s)(ϕ(s)−γϕ(s′))⊤B := \phi(s)(\phi(s)-\gamma\phi(s'))^\top. Due to feature normalization, ∥B∥≤∥ϕ(s)∥(∥ϕ(s)∥+γ∥ϕ(s′)∥)≤2\lVert B\rVert\le\lVert\phi(s)\rVert(\lVert\phi(s)\rVert+\gamma\lVert\phi(s')\rVert) \le2. Consequently, since A=E[B]A = \mathbb{E}[B], we have ∥A∥≤E[∥B∥]≤2\lVert A\rVert\le\mathbb{E}[\lVert B\rVert] \le2. For each epoch k∈[K−1]k \in[K-1], define the following:

g^k(θ):=b^k−A^kθ,θ∈Rd,(12)\widehat{g}_k(\theta) := \widehat{b}_k-\widehat{A}_k\theta,\qquad\theta\in\mathbb{R}^d, \tag*{(12)}

where A^k:=H−1∑j∈Ikϕ(sj)(ϕ(sj)−γϕ(sj′))⊤\widehat{A}_k := H^{-1}\sum_{j\in I_k}\phi(s_j)(\phi(s_j)-\gamma\phi(s'_j))^\top and b^k:=H−1∑j∈Ikrjϕ(sj)\widehat{b}_k := H^{-1}\sum_{j\in I_k}r_j\phi(s_j). Then Yk=g^k(θk)Y_k=\widehat{g}_k(\theta_k) by (4). Also, under the i.i.d. stationary sampling model, we have E[A^k]=A\mathbb{E}[\widehat{A}_k]=A and E[b^k]=b\mathbb{E}[\widehat{b}_k]=b. We have the following result.

Lemma 2. (Operator Estimation) Define

G:=⋂k=0K−1{∥A^k−A∥≤ϵH, ∥b^k−b∥≤ϵH}.(13)\mathcal{G}:=\bigcap_{k=0}^{K-1}\left\{\lVert\widehat{A}_k-A\rVert\le\epsilon_H,\ \lVert\widehat{b}_k-b\rVert\le\epsilon_H\right\}. \tag*{(13)}

Then P(G)≥1−δ\mathbb{P}(\mathcal{G})\ge1-\delta, and on G\mathcal{G},

∥g^k(θ)−gˉ(θ)∥≤ϵH(∥θ∥+1)(14)\lVert\widehat{g}_k(\theta)-\bar{g}(\theta)\rVert\le\epsilon_H(\lVert\theta\rVert+1) \tag*{(14)}

simultaneously for all k=0,…,K−1k=0,\ldots,K-1 and ∀θ∈Rd\forall\theta\in\mathbb{R}^d.

Proof. We first control the empirical matrices. For j∈Ikj\in I_k, write Bj:=ϕ(sj)(ϕ(sj)−γϕ(sj′))⊤B_j:=\phi(s_j)(\phi(s_j)-\gamma\phi(s'_j))^\top. Feature normalization gives ∥Bj∥≤∥ϕ(sj)∥(∥ϕ(sj)∥+γ∥ϕ(sj′)∥)≤1+γ≤2\lVert B_j\rVert\le\lVert\phi(s_j)\rVert(\lVert\phi(s_j)\rVert+\gamma\lVert\phi(s'_j)\rVert)\le1+\gamma\le2. Hence, ∥A^k∥≤2\lVert\widehat{A}_k\rVert\le2 for every realized batch and E[Bj]=A\mathbb{E}[B_j]=A. Moreover, every entry satisfies ∣[Bj]iℓ∣≤∣ϕi(sj)∣(∣ϕℓ(sj)∣+γ∣ϕℓ(sj′)∣)≤2\lvert[B_j]_{i\ell}\rvert\le\lvert\phi_i(s_j)\rvert(\lvert\phi_\ell(s_j)\rvert+\gamma\lvert\phi_\ell(s'_j)\rvert)\le2. Since A^k\widehat{A}_k averages HH independent matrices with expectation AA, scalar Hoeffding’s inequality [24] yields, for every i,ℓ∈{1,…,d}i,\ell\in\{1,\ldots,d\},

P(∣[A^k−A]iℓ∣>ϵHd)≤2exp⁡(−HϵH28d2)≤δ2Kd2.\mathbb{P}\left(\left\lvert[\widehat{A}_k-A]_{i\ell}\right\rvert>\frac{\epsilon_H}{d}\right)\le2\exp\left(-\frac{H\epsilon_H^2}{8d^2}\right)\le\frac{\delta}{2Kd^2}.

The last inequality follows from HϵH2=Cδ2H\epsilon_H^2=C_\delta^2 and (6). A union bound over all d2d^2 entries and KK epochs then ensures that, with probability at least 1−δ/21-\delta/2,

∥A^k−A∥≤∥A^k−A∥F≤dmax⁡i,ℓ∣[A^k−A]iℓ∣≤ϵH\lVert\widehat{A}_k-A\rVert\le\lVert\widehat{A}_k-A\rVert_F\le d\max_{i,\ell}\left\lvert[\widehat{A}_k-A]_{i\ell}\right\rvert\le\epsilon_H

simultaneously for k=0,…,K−1k=0,\ldots,K-1. Here, ∥⋅∥F\lVert\cdot\rVert_F denotes the Frobenius norm. Next, consider the empirical reward vectors. Let (s,r,s′)(s,r,s') be a generic stationary transition tuple and fix i∈{1,…,d}i\in\{1,\ldots,d\}. Since E[r∣s]=Rμ(s)\mathbb{E}[r\mid s]=R_\mu(s), we have [b]i=E[Rμ(s)ϕi(s)][b]_i=\mathbb{E}[R_\mu(s)\phi_i(s)]. For every λ∈R\lambda\in\mathbb{R}, define (∙)≜E[exp⁡(λ(r−Rμ(s))∣s)](\bullet)\triangleq\mathbb{E}[\exp(\lambda(r-R_\mu(s))\mid s)] and using the reward assumption in Section II, we obtain:

(∙)=E[exp⁡(λ(Rμ(s)ϕi(s)−[b]i))∣s]E[exp⁡(λϕi(s)(r−Rμ(s)))∣s]≤(i)exp⁡(λ2σ22)E[exp⁡(λ(Rμ(s)ϕi(s)−[b]i))]≤(ii)exp⁡(λ2(rˉ2+σ2)2).(15)\begin{aligned} (\bullet)&=\mathbb{E}[\exp(\lambda(R_\mu(s)\phi_i(s)-[b]_i))\mid s]\mathbb{E}[\exp(\lambda\phi_i(s)(r-R_\mu(s)))\mid s]\\ &\underset{\text{(i)}}{\le}\exp\left(\frac{\lambda^2\sigma^2}{2}\right)\mathbb{E}[\exp(\lambda(R_\mu(s)\phi_i(s)-[b]_i))]\\ &\underset{\text{(ii)}}{\le}\exp\left(\frac{\lambda^2(\bar{r}^2+\sigma^2)}{2}\right). \tag*{(15)} \end{aligned}

Here, (i) follows by applying the conditional sub-Gaussian assumption to r−Rμ(s)r-R_\mu(s) with scalar λϕi(s)\lambda\phi_i(s) and using ∣ϕi(s)∣≤1\lvert\phi_i(s)\rvert\le1. For (ii), Hoeffding’s lemma applies to Rμ(s)R_\mu(s), which lies in [−rˉ,rˉ][-\bar{r},\bar{r}] and has mean E[Rμ(s)ϕi(s)]=[b]i\mathbb{E}[R_\mu(s)\phi_i(s)]=[b]_i. Therefore, rϕi(s)−[b]ir\phi_i(s)-[b]_i is sub-Gaussian with variance proxy rˉ2+σ2\bar{r}^2+\sigma^2. Independence within each batch implies that [b^k−b]i[\widehat{b}_k-b]_i is sub-Gaussian with variance proxy (rˉ2+σ2)/H(\bar{r}^2+\sigma^2)/H. By (6), ϵH/d≥2(rˉ2+σ2)log⁡(4Kd/δ)/H\epsilon_H/\sqrt{d}\ge\sqrt{2(\bar{r}^2+\sigma^2)\log(4Kd/\delta)/H}. Scalar sub-Gaussian concentration therefore gives

P(∣[b^k−b]i∣>ϵHd)≤2exp⁡(−log⁡(4Kdδ))=δ2Kd,\mathbb{P}\left(\left\lvert[\widehat{b}_k-b]_i\right\rvert>\frac{\epsilon_H}{\sqrt{d}}\right)\le2\exp\left(-\log\left(\frac{4Kd}{\delta}\right)\right)=\frac{\delta}{2Kd},

again by (6). A union bound over the dd coordinates and KK epochs, followed by ∥x∥≤dmax⁡i∣xi∣\lVert x\rVert\le\sqrt{d}\max_i\lvert x_i\rvert, gives ∥b^k−b∥≤dmax⁡i∣[b^k−b]i∣≤ϵH\lVert\widehat{b}_k-b\rVert\le\sqrt{d}\max_i\lvert[\widehat{b}_k-b]_i\rvert\le\epsilon_H simultaneously for all k=k= 0,…,K−10,\ldots,K-1, with probability at least 1−δ/21-\delta/2. Combining the matrix and vector bounds yields P(G)≥1−δ\mathbb{P}(\mathcal{G})\ge1-\delta. On G\mathcal{G}, for every epoch kk and every θ∈Rd\theta\in\mathbb{R}^{d}, the identity g^k(θ)−gˉ(θ)=(b^k−b)−(A^k−A)θ\widehat{g}_{k}(\theta)-\bar{g}(\theta)=(\widehat{b}_{k}-b)-(\widehat{A}_{k}-A)\theta and the triangle inequality gives ∥g^k(θ)−gˉ(θ)∥≤∥b^k−b∥+∥A^k−A∥∥θ∥≤ϵH(∥θ∥+1)\|\widehat{g}_{k}(\theta)-\bar{g}(\theta)\|\le\|\widehat{b}_{k}-b\|+\|\widehat{A}_{k}-A\|\|\theta\|\le\epsilon_{H}(\|\theta\|+1). □\square

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 G\mathcal{G} defined in (13), (7) and (8) imply ∥uk∥≤ρk\|u_k\|\le\rho_k for all k=0,…,K−1k=0,\ldots,K-1. Therefore, by Lemma 1, the reconstruction error satisfies

qk=Qm,ρk(uk)−uk,∥qk∥≤ηρk.(16)q_k=Q_{m,\rho_k}(u_k)-u_k,\qquad\|q_k\|\le\eta\rho_k. \tag*{(16)}

Proof. We prove the claim on the event G\mathcal{G} defined in (13). The reward bound ∣Rμ(s)∣≤rˉ|R_{\mu}(s)|\le\bar{r} and the feature bound ∥ϕ(s)∥≤1\|\phi(s)\|\le1 from Section II give ∥b∥=∥E[Rμ(s)ϕ(s)]∥≤E[∣Rμ(s)∣∥ϕ(s)∥]≤rˉ\|b\|=\|\mathbb{E}[R_{\mu}(s)\phi(s)]\|\le\mathbb{E}[|R_{\mu}(s)|\|\phi(s)\|]\le\bar{r}.

Since h−1=0h_{-1}=0 and Y0=g^0(θ0)Y_0=\widehat{g}_0(\theta_0), the initial innovation is u0=g^0(θ0)u_0=\widehat{g}_0(\theta_0). Applying (14) on G\mathcal{G} gives ∥u0∥≤∥gˉ(θ0)∥+ϵH(∥θ0∥+1)≤rˉ+2∥θ0∥+ϵH(∥θ0∥+1)=ρ0\|u_0\|\le\|\bar{g}(\theta_0)\|+\epsilon_H(\|\theta_0\|+1)\le\bar{r}+2\|\theta_0\|+\epsilon_H(\|\theta_0\|+1)=\rho_0. Thus, saturation is inactive at epoch 0. Suppose ∥uj∥≤ρj\|u_j\|\le\rho_j for all j=0,…,kj=0,\ldots,k, where k∈{0,…,K−1}k\in\{0,\ldots,K-1\}. Since ∥uk∥≤ρk\|u_k\|\le\rho_k, we have sat⁡ρk(uk)=uk\operatorname{sat}_{\rho_k}(u_k)=u_k. Using uk=Yk−hk−1u_k=Y_k-h_{k-1}, with YkY_k defined in (4), the reconstruction update (5) gives qk=hk−Yk=Qm,ρk(uk)−ukq_k=h_k-Y_k=Q_{m,\rho_k}(u_k)-u_k. Lemma 1 then implies ∥qk∥≤ηρk\|q_k\|\le\eta\rho_k. For k≤K−2k\le K-2, we express uk+1u_{k+1} as follows:

uk+1=Yk+1−hk=Yk+1−Yk−qk=g^k+1(θk+1)−g^k(θk)−qk=g^k+1(θk+1)−g^k+1(θk)+g^k+1(θk)−g^k(θk)−qk=A^k+1(θk−θk+1)−(A^k+1−A^k)θk+(b^k+1−b^k)−qk.\begin{aligned} u_{k+1}&=Y_{k+1}-h_k=Y_{k+1}-Y_k-q_k\\ &=\widehat{g}_{k+1}(\theta_{k+1})-\widehat{g}_k(\theta_k)-q_k\\ &=\widehat{g}_{k+1}(\theta_{k+1})-\widehat{g}_{k+1}(\theta_k)+\widehat{g}_{k+1}(\theta_k)-\widehat{g}_k(\theta_k)-q_k\\ &=\widehat{A}_{k+1}(\theta_k-\theta_{k+1})-(\widehat{A}_{k+1}-\widehat{A}_k)\theta_k+(\widehat{b}_{k+1}-\widehat{b}_k)-q_k. \end{aligned}

This decomposition separates the change in parameter from the difference between the two batch estimates evaluated at θk\theta_k. On G\mathcal{G}, ∥A^k+1−A^k∥≤2ϵH\|\widehat{A}_{k+1}-\widehat{A}_k\|\le2\epsilon_H and ∥b^k+1−b^k∥≤2ϵH\|\widehat{b}_{k+1}-\widehat{b}_k\|\le2\epsilon_H, since each empirical operator is within ϵH\epsilon_H of its expectation. Thus, using ∥A^k+1∥≤2\|\widehat{A}_{k+1}\|\le2 and θk+1−θk=αhk\theta_{k+1}-\theta_k=\alpha h_k, we obtain ∥uk+1∥≤2∥θk+1−θk∥+2ϵH(∥θk∥+1)+ηρk=2α∥hk∥+2ϵH(∥θk∥+1)+ηρk=ρk+1\|u_{k+1}\|\le2\|\theta_{k+1}-\theta_k\|+2\epsilon_H(\|\theta_k\|+1)+\eta\rho_k=2\alpha\|h_k\|+2\epsilon_H(\|\theta_k\|+1)+\eta\rho_k=\rho_{k+1}. Induction establishes ∥uk∥≤ρk\|u_k\|\le\rho_k and (16) for every transmitted innovation. □\square

Define the sampling error ξk:=Yk−gˉ(θk)\xi_k:=Y_k-\bar{g}(\theta_k). The decoded direction then admits the decomposition hk=gˉ(θk)+ξk+qkh_k=\bar{g}(\theta_k)+\xi_k+q_k. Here ξk\xi_k accounts for batch estimation and qkq_k for finite-bit reconstruction. Recall that ek=θk−θ⋆e_k=\theta_k-\theta^{\star}. Since Aθ⋆=bA\theta^{\star}=b, we have gˉ(θk)=b−Aθk=−Aek\bar{g}(\theta_k)=b-A\theta_k=-Ae_k. Our next result provides bounds on the sampling error ξk\xi_k, reconstruction error qkq_k, and encoding radius ρk\rho_k as a function of the sub-optimality eke_k.

Lemma 4. (Direction and Radius Bounds) Suppose 0<α≤ω/320<\alpha\le\omega/32. On the event G\mathcal{G} defined in (13), the following bounds hold simultaneously for every k=0,…,K−1k=0,\ldots,K-1:

∥ξk∥≤ϵH(∥ek∥+1+∥θ⋆∥),(17)\|\xi_k\|\le\epsilon_H(\|e_k\|+1+\|\theta^{\star}\|), \tag*{(17)}
∥ξk+qk∥2≤2η2ρk2+4ϵH2∥ek∥2+4ϵH2(1+∥θ⋆∥)2,(18)\|\xi_k+q_k\|^2\le2\eta^2\rho_k^2+4\epsilon_H^2\|e_k\|^2+4\epsilon_H^2(1+\|\theta^{\star}\|)^2, \tag*{(18)}
ρk+12≤12η2ρk2+(48α2+96ϵH2)∥ek∥2+96ϵH2(1+∥θ⋆∥)2.(19)\rho_{k+1}^2\le12\eta^2\rho_k^2+(48\alpha^2+96\epsilon_H^2)\|e_k\|^2+96\epsilon_H^2(1+\|\theta^{\star}\|)^2. \tag*{(19)}

Proof. By (14), on G\mathcal{G}, ∥ξk∥=∥g^k(θk)−gˉ(θk)∥≤ϵH(∥θk∥+1)\|\xi_k\|=\|\widehat{g}_k(\theta_k)-\bar{g}(\theta_k)\|\le\epsilon_H(\|\theta_k\|+1). Using θk=ek+θ⋆\theta_k=e_k+\theta^{\star} and the triangle inequality proves (17). Next, apply ∥x+y∥2≤2∥x∥2+2∥y∥2\|x+y\|^2\le2\|x\|^2+2\|y\|^2 to ξk+qk\xi_k+q_k. By (17) and (16),

∥ξk+qk∥2≤2∥ξk∥2+2∥qk∥2≤2ϵH2(∥ek∥+1+∥θ⋆∥)2+2η2ρk2≤4ϵH2∥ek∥2+4ϵH2(1+∥θ⋆∥)2+2η2ρk2,\begin{aligned} \|\xi_k+q_k\|^2 &\le2\|\xi_k\|^2+2\|q_k\|^2\\ &\le2\epsilon_H^2(\|e_k\|+1+\|\theta^{\star}\|)^2+2\eta^2\rho_k^2\\ &\le4\epsilon_H^2\|e_k\|^2+4\epsilon_H^2(1+\|\theta^{\star}\|)^2+2\eta^2\rho_k^2, \end{aligned}

where the last inequality uses (a+b)2≤2a2+2b2(a+b)^2\le2a^2+2b^2. This proves (18). To bound the next radius, substitute hk=gˉ(θk)+ξk+qkh_k=\bar{g}(\theta_k)+\xi_k+q_k into (8). Using ∥qk∥≤ηρk\|q_k\|\le\eta\rho_k from (16) and ∥ξk∥≤ϵH(∥θk∥+1)\|\xi_k\|\le\epsilon_H(\|\theta_k\|+1) from (14), we obtain

ρk+1≤ηρk+2α(∥gˉ(θk)∥+∥ξk∥+∥qk∥)+2ϵH(∥θk∥+1)≤η(1+2α)ρk+2α∥gˉ(θk)∥+2(1+α)ϵH(∥θk∥+1).\begin{aligned} \rho_{k+1}\le\eta\rho_k+2\alpha(\|\bar{g}(\theta_k)\|+\|\xi_k\|+\|q_k\|)+2\epsilon_H(\|\theta_k\|+1) \\ &\le\eta(1+2\alpha)\rho_k+2\alpha\|\bar{g}(\theta_k)\|+2(1+\alpha)\epsilon_H(\|\theta_k\|+1). \end{aligned}

Since α≤ω/32≤1/32\alpha\le\omega/32\le1/32, we have 1+2α≤21+2\alpha\le2 and 2(1+α)≤42(1+\alpha)\le4. Using ∥θk∥+1≤∥ek∥+1+∥θ⋆∥\|\theta_k\|+1\le\|e_k\|+1+\|\theta^{\star}\| gives

ρk+1≤2ηρk+2α∥gˉ(θk)∥+4ϵH(∥ek∥+1+∥θ⋆∥).(20)\rho_{k+1}\le2\eta\rho_k+2\alpha\|\bar{g}(\theta_k)\|+4\epsilon_H(\|e_k\|+1+\|\theta^{\star}\|). \tag*{(20)}

Squaring this bound and applying (a+b+c)2≤3(a2+b2+c2)(a+b+c)^2\le3(a^2+b^2+c^2) yields the following:

ρk+12≤12η2ρk2+12α2∥gˉ(θk)∥2+48ϵH2(∥ek∥+1+∥θ⋆∥)2.\rho_{k+1}^2\le12\eta^2\rho_k^2+12\alpha^2\|\bar{g}(\theta_k)\|^2+48\epsilon_H^2(\|e_k\|+1+\|\theta^{\star}\|)^2.

Using gˉ(θk)=−Aek\bar{g}(\theta_k)=-Ae_k and the operator-norm bound ∥A∥≤2\|A\|\le2 gives ∥gˉ(θk)∥≤∥A∥∥ek∥≤2∥ek∥\|\bar{g}(\theta_k)\|\le\|A\|\|e_k\|\le2\|e_k\|. Also, (∥ek∥+1+∥θ⋆∥)2≤2∥ek∥2+2(1+∥θ⋆∥)2(\|e_k\|+1+\|\theta^{\star}\|)^2\le2\|e_k\|^2+2(1+\|\theta^{\star}\|)^2. Substituting these bounds proves (19). □\square

The final piece we require is the following result from [5].

⟨θ⋆−θ,gˉ(θ)⟩≥ω∥θ−θ⋆∥2,∀ θ∈Rd,(21)\langle\theta^{\star}-\theta,\bar{g}(\theta)\rangle\ge\omega\|\theta-\theta^{\star}\|^2,\quad\forall\ \theta\in\mathbb{R}^{d}, \tag*{(21)}

where recall that ω=(1−γˉ)ω~∈(0,1)\omega=(1-\bar{\gamma})\widetilde{\omega}\in(0,1), and ω~\widetilde{\omega} is the smallest eigenvalue of Σ=EΦTΦ\Sigma=\mathbb{E}\Phi^{\mathsf{T}}\Phi. We now combine these bounds through the joint Lyapunov function Vk=∥ek∥2+αρk2V_k=\|e_k\|^2+\alpha\rho_k^2 to prove Theorem 1.

▪ Proof of Theorem 1. By Lemma 2, the event G\mathcal{G} defined in (13) has probability at least 1−δ1-\delta. We prove the claim on this event. Recall that η=d/2m\eta=\sqrt{d}/2^m. The prescribed precision m≥⌈12log⁡2(64d/ω)⌉m\ge\lceil\frac{1}{2}\log_2(64d/\omega)\rceil gives η2=d/22m≤ω/64\eta^2=d/2^{2m}\le\omega/64. Since T=KHT=KH, the sample-size condition implies H≥c2Cδ2/ω2H\ge c_2 C_{\delta}^2/\omega^2. Taking the universal constant c2≥1024c_2\ge1024 therefore ensures that ϵH2=Cδ2/H≤ω2/1024\epsilon_H^2=C_{\delta}^2/H\le\omega^2/1024. The stepsize satisfies 0<α≤ω/320<\alpha\le\omega/32. Lemma 3 gives ∥uk∥≤ρk\|u_k\|\le\rho_k and ∥qk∥≤ηρk\|q_k\|\le\eta\rho_k for every k=0,…,K−1k=0,\ldots,K-1. The sampling and reconstruction errors thus satisfy the bounds in Lemma 4.

We first derive a recursion for Vk=∥ek∥2+αρk2V_k=\|e_k\|^2+\alpha\rho_k^2. The parameter update and the decomposition of hkh_k give ek+1=ek+αgˉ(θk)+α(ξk+qk)e_{k+1}=e_k+\alpha\bar{g}(\theta_k)+\alpha(\xi_k+q_k). From this and (21), we obtain

∥ek+1∥2≤(1−2αω)∥ek∥2+2α⟨ek,ξk+qk⟩+2α2∥gˉ(θk)∥2+2α2∥ξk+qk∥2.\|e_{k+1}\|^2\le(1-2\alpha\omega)\|e_k\|^2+2\alpha\langle e_k,\xi_k+q_k\rangle+2\alpha^2\|\bar{g}(\theta_k)\|^2+2\alpha^2\|\xi_k+q_k\|^2.

Young’s inequality gives 2⟨ek,ξk+qk⟩≤ω2∥ek∥2+2ω∥ξk+qk∥22\langle e_k,\xi_k+q_k\rangle\le\frac{\omega}{2}\|e_k\|^2+\frac{2}{\omega}\|\xi_k+q_k\|^2. Together with ∥gˉ(θk)∥≤2∥ek∥\|\bar{g}(\theta_k)\|\le2\|e_k\|, this yields

∥ek+1∥2≤(1−32αω+8α2)∥ek∥2+2(αω+α2)∥ξk+qk∥2.\|e_{k+1}\|^2\le\left(1-\frac{3}{2}\alpha\omega+8\alpha^2\right)\|e_k\|^2+2\left(\frac{\alpha}{\omega}+\alpha^2\right)\|\xi_k+q_k\|^2.

Because αω≤1\alpha\omega\le1, the coefficient of the final term is at most 4α/ω4\alpha/\omega. Substituting (18) therefore gives

∥ek+1∥2≤(1−32αω+8α2+16αϵH2ω)∥ek∥2+8αη2ωρk2+16αϵH2ω(1+∥θ⋆∥)2(22)\lVert e_{k+1}\rVert^2 \le\left(1-\frac{3}{2}\alpha\omega+8\alpha^2+\frac{16\alpha\epsilon_H^2}{\omega}\right)\lVert e_k\rVert^2+\frac{8\alpha\eta^2}{\omega}\rho_k^2+\frac{16\alpha\epsilon_H^2}{\omega}(1+\lVert\theta^\star\rVert)^2 \tag*{(22)}

Adding α\alpha times (19) to (22) and collecting terms gives

Vk+1≤[1−32αω+α(8α+48α2+(16ω+96)ϵH2)]∥ek∥2+αη2(8ω+12)ρk2+α(16ω+96)ϵH2(1+∥θ⋆∥)2(23)V_{k+1}\le\left[1-\frac{3}{2}\alpha\omega+\alpha\left(8\alpha+48\alpha^2+\left(\frac{16}{\omega}+96\right)\epsilon_H^2\right)\right]\lVert e_k\rVert^2+\alpha\eta^2\left(\frac{8}{\omega}+12\right)\rho_k^2+\alpha\left(\frac{16}{\omega}+96\right)\epsilon_H^2(1+\lVert\theta^\star\rVert)^2 \tag*{(23)}

Since 0<ω≤10<\omega\le1 and α≤ω/32\alpha\le\omega/32, we have αω≤1/32\alpha\omega\le1/32 and

η2(8/ω+12)≤ω64(8/ω+12)=18+3ω16≤516≤3132≤1−αω.\eta^2(8/\omega+12)\le\frac{\omega}{64}(8/\omega+12)=\frac{1}{8}+\frac{3\omega}{16}\le\frac{5}{16}\le\frac{31}{32}\le1-\alpha\omega.

Moreover, the stepsize and batch-size bounds give 8α+48α2+(16/ω+96)ϵH2≤13ω/32≤ω/28\alpha+48\alpha^2+(16/\omega+96)\epsilon_H^2\le13\omega/32\le\omega/2. Thus, the coefficients of ∥ek∥2\lVert e_k\rVert^2 and αρk2\alpha\rho_k^2 in (23) are both at most 1−αω1-\alpha\omega. Finally, 16/ω+96≤112/ω16/\omega+96\le112/\omega bounds the additive term by O(αϵH2(1+∥θ⋆∥)2/ω)O(\alpha\epsilon_H^2(1+\lVert\theta^\star\rVert)^2/\omega). Substituting these estimates into (23) and using Vk=∥ek∥2+αρk2V_k=\lVert e_k\rVert^2+\alpha\rho_k^2 yields

Vk+1≤(1−αω)Vk+O(αϵH2ω)(1+∥θ⋆∥)2(24)V_{k+1}\le(1-\alpha\omega)V_k+O\left(\frac{\alpha\epsilon_H^2}{\omega}\right)(1+\lVert\theta^\star\rVert)^2 \tag*{(24)}

for every k=0,…,K−1k=0,\ldots,K-1. Iterating (24) gives

Vk≤(1−αω)kV0+O(αϵH2ω)(1+∥θ⋆∥)2∑j=0k−1(1−αω)j(25)V_k\le(1-\alpha\omega)^kV_0+O\left(\frac{\alpha\epsilon_H^2}{\omega}\right)(1+\lVert\theta^\star\rVert)^2\sum_{j=0}^{k-1}(1-\alpha\omega)^j \tag*{(25)}

for every k=1,…,Kk=1,\ldots,K. Since 0<αω<10<\alpha\omega<1, the geometric sum is bounded from above by 1/(αω)1/(\alpha\omega). Using ϵH=Cδ2/H\epsilon_H=C_\delta^2/H in (25) and dropping the nonnegative term αρk2\alpha\rho_k^2, we obtain

∥θk−θ⋆∥2≤(1−αω)kV0+O(Cδ2(1+∥θ⋆∥)2ω2H).(26)\lVert\theta_k-\theta^\star\rVert^2\le(1-\alpha\omega)^kV_0+O\left(\frac{C_\delta^2(1+\lVert\theta^\star\rVert)^2}{\omega^2H}\right). \tag*{(26)}

The same bound holds at k=0k=0 because ∥θ0−θ⋆∥2≤V0\lVert\theta_0-\theta^\star\rVert^2\le V_0. Thus, (26) holds simultaneously for all k=0,…,Kk=0,\ldots,K on the single event G\mathcal{G}; no additional union bound is needed.

To express the statistical contribution in terms of the sample budget, substitute H=T/KH=T/K into (26). This gives O(Cδ2(1+∥θ⋆∥)2K/(ω2T))O(C_\delta^2(1+\lVert\theta^\star\rVert)^2K/(\omega^2T)). Under the prescribed choice K=⌈c1log⁡T/(αω)⌉K=\lceil c_1\log T/(\alpha\omega)\rceil, this becomes O((1+∥θ⋆∥)2log⁡T/(αω3T))O((1+\lVert\theta^\star\rVert)^2\log T/(\alpha\omega^3T)), 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. [1]S. Tatikonda and S. Mitter, “Control under communication constraints,” IEEE Transactions on Automatic Control, pp. 1056–1068, 2004.DOI
  2. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [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. [24]F. Chung and L. Lu, “Concentration inequalities and martingale inequalities: a survey,” Internet mathematics, vol. 3, no. 1, pp. 79–127, 2006.

Paper details

vlnc:W_k97zvzks
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 9

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents