Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning
Authors: Aritra Mitra
George J. Pappas
Hamed Hassani
Venue: Accepted by TMLR ()

Abstract: In large-scale distributed machine learning, recent works have studied the effects of compressing gradients in stochastic optimization to alleviate the communication bottleneck. These works have collectively revealed that stochastic gradient descent (SGD) is robust to structured perturbations such as quantization, sparsification, and delays. Perhaps surprisingly, despite the surge of interest in multi-agent reinforcement learning, almost nothing is known about the analogous question: \textit{Are common reinforcement learning (RL) algorithms also robust to similar perturbations?} We investigate this question by studying a variant of the classical temporal difference (TD) learning algorithm with a perturbed update direction, where a general compression operator is used to model the perturbation. Our work makes three important technical contributions. First, we prove that compressed TD algorithms, coupled with an error-feedback mechanism used widely in optimization, exhibit the same non-asymptotic theoretical guarantees as their SGD counterparts. Second, we show that our analysis framework extends seamlessly to nonlinear stochastic approximation schemes that subsume Q-learning. Third, we prove that for multi-agent TD learning, one can achieve linear convergence speedups with respect to the number of agents while communicating just $\tilde{O}(1)$ bits per iteration. Notably, these are the first finite-time results in RL that account for general compression operators and error-feedback in tandem with linear function approximation and Markovian sampling. Our proofs hinge on the construction of novel Lyapunov functions that capture the dynamics of a memory variable introduced by error-feedback.

Published in Transactions on Machine Learning Research (04/2024)
Temporal Difference Learning with Compressed Updates: Error-Feedback meets Reinforcement Learning
Aritra Mitra
amitro@@mesu.edd
Deportment of Electrical and Computer Engineering
North Carolina State University
George J. Pappas
Sxppasg@scus.upeee
Department of Electrical and Systems Engineering University of Pennsylvania
Hamed Hassani
hassoni wpw.n.. edu
Department of Electricol and Systems Engineering University of Pennsylvania
Reviewed on OpenReview: https: openreviee.. net/ met/terrnn forum? UUdmUVV
Abstract
In large-scale distributed machine learning, recent works have studied the effects of compress- ing gradients in stochastic optimization to alleviate the communication bottleneck. These works have collectively revealed that stochastic gradient descent (SGD) is robust to struc- tured perturbations such quantization, sparsification, and delays. Perhaps surprisingly, despite the surge of interest in multi-agent reinforcement learning, almost nothing is known about the analogous question: Are common reinforcement learning (RL) algorithms also robust to similar perturbations? We investigate this question by studying a variant the classical lemporal difference (TD) learning algorithm with a perturbed update direction, where general compression operator is used to model the perturbation. Our work makes three important technical contributions. First, prove that compressed TD algorithms, coupled with feror-feedback mechanism used widely in optimization, exhibit the same non-asymptotic theoretical guarantees their SGD counterparts. Second, we show that our analysis framework extends seamlessly to nonlinear stochastic approximation schemes that subsume Q-learning. Third, we prove that for multi-agent TD learning, one can achieve linear convergence speedups with respect to the number of agents while communicating just Ó(1) bits per itcration. Notably, these are the first finite-time results RL that account for general compression operators and error-feedback in tandem with linear function approximation and Markovian sampling. Our proofs hinge the construction of novel Lyapunov functions that capture the dynamics of memory variable introduced by feror-feedback.
1 Introduction
Stochastic gradient descent (SGD) is the heart of large-scale distributed machine learning paradigms such as federated learning (FL) (Konečný al., 2016). In these applications, the task of training high-dimensional weight vectors is distributed among several workers that exchange information over networks of limited bandwidth. While parallelization at such an immense scale helps to reduce the computational burden, it creates several other challenges: delays, asynchrony, and most importantly, significant communication bottleneck. The popularity and success of SGD can be attributed in no small part to the fact that it is extremely robust to such deviations from ideal operating conditions. In fact, by now, there is a rich
"This work supported by NSF Award 1837253, NSF CAREER award CIF 1943064, and The Institute Learning-enabled Optimization Scale (TILOS), under award number NSF-CCF-21

---

Published in Transactions on Machine Learning Research (04/2024)
literature that analyzes the robustness of SGD to host of structured perturbations that include lossy gradient-quantization (Seide et al., 2014; Alistarh et al., 2017) and sparsification (Wen et al., 2017; Stich et al., 2018). For instance, SignSGD a variant of SGD where each coordinate of the gradient is replaced by its sign - is extensively used to train deep ncural networks (Aji & Heafield, 2017; Bernstein et al., 2018). Inspired by these findings, in this paper, we ask a different question: Are common reinforcement learning (RL) algorithms also robust to similar structured perturbations?
Motivation. Perhaps surprisingly, despite the recent surge of interest in caaitt-ageen/ffderattete RL, almost nothing is known about the above question. To fill this void, we initiate the study of a robustness theory for iterative RL algorithms with compressed update directions. We primarily focus on the problem of evaluating the value function associated with a fixed policy in a Markov decision process (MDP). Just as SGD is the workhorse of stochastic optimization, the classical temporal difference (TD) learning algorithm (Sutton, 1988) for policy evaluation forms the core subroutine in a variety of decision-making algorithms in RI. (e.g., Watkin's Q-learning algorithm). In fact, in their book (Sutton & Barto, 2018), Sutton and Barto mention: "If one had to idenlify one idea as central and novel lo reinforcement learning, il would undoubledly be lemporal-difference (TD) learning." " Thus, it stands to reason that center our investigation around variant of the TD(O) learning algorithm with linear function approximation, where the TD(O) update direction is replaced by a compressed version of it. Moreover, to account for general biased compression operators (e.g., sign and Top-k),, we couple this scheme with an error-feedback mechanism that retains some memory of TD(O) update directions from the past.
Other than the robustness angle, key motivation of our work is to design catmmmuninatioofffiiieeeee algorithms for the emerging paradigms of multi-agent RL (MARL) and federated RL (FRI.. In existing works on these topics (Doan et al., 2019; Qi et al., 2021; Jin et al., 2022; Khodadadian et al., 2022), agents typically exchange high- digh-dimennional models (parameters) or model-differentials (i.e., gradient-like update directions) over bhu-bandwidhh chanmels, keeping their personal data (i.e., rewards, states, and actions) private. In the recent survey paper on FRL by (Qi ct al., 2021); the authors explain how the above issues contribute to & major communication bottleneck, just as the standard FL selting. However, no work on MARL or FRL provides any theory whatsoever when it comes to compression/ /uaoon/zttaaaiiinnnnnmm in RL. Our work takes a significant step towards filling this gap via suite of comprehensive theoretical results that we discuss below.
1.1 Our Contributions
The main contributions of this work are as follows.
1. Algorithmic Framework for Compressed Stochastic Approximation. We develop a general framework for analyzing iterative compressed stochastic approximation (SA) algorithms with error- feedback. The generality of this framework stems from two salient features: (i) it applies to noulinear SA with Markovian noise; and (ii) the compression operator covers several common quantization and (biased) sparsífication schemes studied in optimization. As an instance of our framework, we propose new algorithm called EF-TD (Algorithm 1) to study extreme distortions to the TD(O) update direction. Examples of such distortion include, but are not limited to, replacing each coordinate of the (D) update direction with just its sign, or just retaining the coordinate with the largest magnitudc. While such distortions have been extensively studied for SGD, we are unaware of any analagous algorithms or analysis in the context of RL.
Analysis under Markovian Sampling. In Theorem 1, we show that with a constant step- size, EF-TD guarantees linear convergence to a ball centered around the optimal parameter. Up to compression factor, our result mirrors existing rates in RL without compression (Srikant & Ying, 2019). Moreover, the effect of the compression factor exactly mirrors that for compressed SGD (Beznosikov et al., 2020). The significance of this result is twofold: (i) It is the first result in RL that accounts for general compression operators and error-feedback in landem with Markovian sampling and linear function approximation; and (ii) It is the first theoretical result on the robustness of TD learning algorithms to structured perturbations. One interesting takeaway from Theorem 1 is that alowly-miring Markov chains have more inherent robustness to distortions/ appears to be new observation that we elaborate in Section 4. distortions/oopprssion ccompression. This
2

---

Published in Transactions on Machine Learning Research (04/2024)
3. Analysis for General Nonlinear Stochastic Approximation. In Section 5, we study Algorithm in its full generality by considering a compressed nonlinear SA scheme with error-feedback, and establishing an analog of Theorem in Theorem 2. The significance of this result lies in revealing that the power and scope of the popular aror-feedback mochanism (Scide et al., 2014) in large-scale ML is not limited to the optimization problems it has been used for thus far. In particular, since the nonlinear SA scheme we study captures certain instances of Q-learning (Chen et al., 2019), Theorem 2 conveys that our results extend well beyond policy evaluation to decision- maaking (control) problems well.
4. Communicationn-Fiiiteni MARL. Since one of our main goals is to facilitate communication- efficient MARL, we consider a collaborative MARL setting that has shown up in several recent works (Doan et al., 2019; Khodadadian et al., 2022; Liu & Olshevsky, 2021a). Here, M agents interact with the same MDP, but observe potentially different realizations of rewards and state transitions. These agents exchange compressed TD update dircctions via a central server to speed up the procoss of evaluating a specific policy. In this context, we ask the following fundamental question: How much information needs to be transmitted to achieve the optimal linear-speedup (w.r.t. the number of agents) for policy-eualuation?? To answer this question, we propose a multi-agent version of EF-TD. In Theorem 3, we prove that by collaborating, each agent can achieve an M-fold speedup in the dominant term of the convergence rate. Importantly, the effect of compression only shows up in higher-order terms, leaving the dominant term unaffected. Thus, we prove that by transmitting just Ö(1) bits per-agent per-round, one can preserve the same asymptotic rates as vanilla (D); while achieving an optimal linear convergence speedup w.r.t. the number of agents. We envision this result will have important implications for MARL. Our analysis also leads to a lighter linear dependence on the mixing time compared to the quadratic dependence in the only other paper that establishes linear speedups under Markovian sampling (Khodadadian et al., 2022).
5. Technical Challenges and Novel Proof Techniques. One might wonder whether our results above follow simple extensions of known analysis techniques in RL. In what follows, we explain why this isn't 't the case by outlining the key technical challenges unique to our setup, and our novel proof ideas to overcome them. First, a non-asymptotic analysis of even vanilla TD(O) under Markovian sampling is known to be extremely challenging due to complex temporal correlations. Our setting is further complicated by the fact that the dynamics of the parameter and the memory variable are intricately coupled with the temporally stochastic dynamical system that has not been analyzed before in RL. Second, we cannot directly appeal to existing proofs of compression in optimization since the problems study do not involve minimizing static loss function. Moreover, the aspect of temporally correlated observations is completely absent in compressed optimization since one deals with i.i.d. data. The above discussion motivates the need for new analysis tools beyond what are known for both RL and optimization.
Markov data tuples. This leads to a compler
New Proof Ingredients for Theorems and 2. To prove Theorem 1, our first innovation is to construct novel Lyapunov function that accounts for the joint dynamics of the parameter and the memory variable introduced by error-feedback. The next natural step is to then analyze the drift of this Lyapunov function by appealing to mixing time arguments- - as is typically done in finite-time RL proofs (Bhandari et al., 2018; Srikant & Ying, 2019). This is where we again run into difficulties since the presence of the memory variable due to error-feedback introduces non-standard delay terms in the drift bound. Notably, this difficulty does not show up when one analyzes ervor-feedback in optimization since there is no need for mizing time arguments of Markov chains. To overcome this challenge, we make connection to what might at first appear unrelated: the Incremental Aggregated Gradient (IAG) method for finitc-sum optimization. Our main observation here is that the clegant analysis of the IAG method by Gurbuzbalaban et al. (2017) shows how one can handle the effect of "shocks" (delayed terms), as long as the amplitude and duration of the shocks is not too large. This ends up being preciscly what we need for our purpose: we carcfully relate the amplitude of the shocks to our Lyapunov function, and their duration to the mixing time of the underlying Markov chain. We spell out these details explicitly in Section 7.
3

---

Published in Transactions on Machine Learning Research (04/2024)
New Proof Ingredients for Theorem 3. Despite the long list of papers on MARL, the only one that establishes a linear speedup (w.r.t. the number of agents) in sample-complexity under Markovian sampling is the very recent paper by Khodadadian et al. (2022); all other papers end up making a restrictive i..d. sampling assumption (Doan et al., 2019; Liu & Olshevsky, 2021a; Shen el. al., 2023) to show a speedup. The proof in (Khodadadian et al., 2022) is quite involved, and relies on Generalized Moreau Envelopes. This makes particularly challenging to extend their proof framework to our setting where we need to additionally contend with the effects of compression and feedbac.. As such, we provide an alternate proof technique for establishing the linear speedup effect that relies crucially on a new varionce reduction lemma under Markovian data, namely Lemma 2. This lemma is not just limited to TD learning, and may be of independent interest to the MARL literature. Lemma 2, coupled with a finer Lyapunov function (relative to that for proving Theorem 1) enable us to establish the desired linear speedup result under Markovian sampling for our sctting. We claborate on these points in Scction 7.
Scope of our Work. We note that our work is primarily theoretical in nature, in the same spirit as several recent finite-time RL papers (Dalal et al., 2018; Bhandari et al., 2018; Srikant & Ying, 2019; Doan et al., 2019; Khodadadian et al., 2022), none of which come with any simulations. We do, however, report simulations on moderately sized (100 states) MDPs that reveal: (i) without ervor-feeiback (EF), compressed TD(O) can end up making little to no progress; and (ii) with EF, the performance of compressed TD(O) complies with our theory. These simulations are in line with those known in optimization for deep learning (Stich et al., 2018; Aji & Heafield, 2017: Lin et al., 2017; Stich & Karimireddy, 2019), where one empirically observes significant benefits of performing EF. Succinetly, we convey: compressed TD learning algorithms with EF are just robust as their SGD counterports, and exhibit similar convergence guaranlees.
1.2 Related Work
In what follows, we discuss the most relevant threads of related work.
Analysis of TD Learning Algorithms. An analysis of the classical temporal difference learning algorithm (Sutton, 1988) with value function approximation was first provided by Tsitsiklis & Van Roy (1997). They employed the ODE method (Borkar & Meyn, 2000) - commonly used to study stochastic approximation algorithms- to provide an asymptotic convergence rate analysis of TD learning algorithms. Finite-time rates for such algorithms remained elusive for several years, till the work by Korda & La (2015). Soon after, Narayanan & Szepesvári (2017) noted some issues with the proofs in (Korda & La, 2015). Under an i.i.d. sampling assumption, Lakshminarayanan & Sxepesvári (2017) and Dalal et al. (2018) went on to provide finite-time rates for TD learning algorithms. For the more challenging Markovian setting, finite-time rates have been recently derived using various perspectives: (i) by making explicit connections to optimization (Bhandari et al., 2018); (ii) by taking a control-theoretic approach and studying the drift of a suitable Lyapunov function (Srikant & Ying, 2019); and (iii) by arguing that the mean-path temporal of an appropriately chosen function (Liu & Olshevsky,
difference direction acts as a "gradient-splittinn 2021b). Each of these interpretations provides interesting new insights into the dynamics of TD algorithms.
The above works focus on the vanilla. TD) learning rule. Our work adds to this literature by providing an understanding of the robustness of TD learning algorithms subject to structured distortions.
Communication Effiicien Algorithms for (Distributed) Optimization and Learning. In the last decade or so, a variety of both scalar (Seide et al., 2014; Wen et al., 2017; Bernstein et al., 2018; Alistarh et al., 2017), and vector (Mayekar & Tyagi, 2020; Gandikota et al., 2021) quantization schemes have been risk minimization. In particular,
explored for pptimization/eepiire employed popularly in deep learning is gradient sparsification, where one only transmits few components of the gradient vector that have the largest magnitudes. While empirical studies (Aji & Heafield, 2017; Lin et al., 2017) have revealed the benefits of extreme sparsification, theoretical guarantees for such methods are much harder to establish due to their biased nature: the output of the compression operator is not an unbiasod version of its argument. In fact, for biased schemes, naively compressing gradients can lead to diverging iterates (Karimireddy et al., 2019; Beznosikov et al., 2020). In (Stich et al., 2018; Alistarh et al., 2018), and later in (Karimireddy et al., 2019; Lin et al., 2022), it was shown that the above issue can be
aggressive compression scheme
4

---

Published in Transactions on Machine Learning Research (04/2024)
"fixed" by using mechanism known as error-feedback that exploits memory. This idea is also related to modulation techniques in coding theory (Gray, 2012). Recently, Bexnosikov et al. (2020) and Gorbunov et al. (2020) provided theoretical results on biased sparsification for a master worker type distributed architecture, and Mitra et al. (2021) studied sparsification in a foderated learning context. For more recent work on the error-feedback idea, we refer the reader to (Richtárik et al., 2021; Grunt et al., 2022).
Our work can be seen as the first analog of the above results in general, and the error-feedback idea in particular, in the context of iterative algorithms for RL.
Finally, we note that while several compression algorithms have been proposed and analyzed over the years, fundamental performance bounds were only recently identified by Mayekar & Tyagi (2020), Gandikota et al. (2021), and Lin et al. (2022). Compulationally efficient algorithms that match such performance bounds were developed by Saha et al. (2022). While all the above results pertain to static optimization, some recent works have also explored quantization schemes in the context of soquential-dccision making problems, focusing on multi-armed bandits (Hanna al., 2022; Mitra et al., 2022; Pase et al., 2022).
2 Model and Problem Setup
We consider a Markov Decision Process (MDP) denoted by M (S,,,,,,,, where S is a finite state space of size n, A is a finite action space, P is set of aetion-dependent Markov transition kernels, R is a reward function, and 7 (0, 1) is the discount factor. For the majority of the paper, will be interested in the policy evaluation problem where the goal is to evaluate the value function Vy, of a given policy μ!; here, p S + A. The policy μ induces a Markov reward process (MRP) characterized by a transition matrix P, and a reward function R. In particular, s's,s') denotes the probability of transitioning from state s to state s' under the action uus); R(s) denotes the expected instantancous reward from an initial state under the action of the policy μ. The discounted expected cumulative reward obtained by playing policy μ starting from initial state is given by:
(s) E Σ 7 R(s:) 80 =
(1)
where 8t represents the state of the Markov chain (induced by p) at time i, when initiated from so 8. It is well-known (Tsitsikkis & Van Roy, 1997) that V,, is the fixed point of the policy-specific Bellman operator Tu R + R", i..., TpVa Vp, where for any V E R",
= (T)V)(s)=R(s)
+ Σ P(s,s')V(ss) S.
S'ES
Linear Function Approximation. In practice, the size of the state space S can be extremely large. This renders the task of estimating Vn exactly (based on observations of rewards and state transitions) intractable. One common approach to tackle this difficulty is to consider a parametric approximation Vo of V, in the linear subspace spanned by a set {ØE]RE(K) of K & n basis vectors, where Φi E RK is a weight vector. Let & E Ra*K be matrix with Φb as its k-th column; we will denote the s-th row of by d(s) E R and refer to it as the feature vector corresponding to state s. Compactly, Vo Φ0, and for each s E S, we have that (s(s) (o(s), 8). As is standard, we assume that the columns of 4 are linearly independent, and that the feature vectors are normalized, i.e., for each E S, [[0(s)]13 < 1.
(I),...,(((()))
E R".
Specifically, we have Vo(s) = Σk= (()))u(s), where 0 == (0.
The TD(O) Algorithm. The goal now is to find the best parameter vector 0* that minimizes the distance (in a suitable norm) between Vo and V,,- To that end, we will focus on the classical TD(O) algorithm within the family of TD learning algorithms. Starting from an initial estimate Og at each time-step = 0, 1,.,,, this algorithm receives as obsorvation data tuple X, (st, 8141,7t R(s))) comprising of the current state, the next state reached by playing action p(se), and the instantaneous reward rt- Given this tuple X., let
For simplicity of notation, have dropped the dependence of and R the policy p.
5

---

Published in Transactions on Machine Learning Research (04/2024)
21 = 0
(8)
2x(0)
1<8' <8
Figure 1: A geometric interpretation of the operator 2s(+) in Algorithm 1. A larger 8 induces more distortion.
Algorithm The EF-TD Algorithm
Input: Tnitial estimate 0g E R&K, initial error e-1 = 0, and step-size a E (0, 1). for t= 0, 1.... do
Observe tuple X, (8t; 8141, rz). Compute perturbed TD(O) direction hy:
h4 2s (ct- (o:)))
(3)
Update parameter: 0++1 0, + ah,- Update error: E Cx-1 (0:) h4-
7: end for
define (0) g(Xe, 0) as:
()) a (rr + (0(8411) (0((s)) 0)) (8t)), vO e R
The TD(O) update to the current parameter O, with step-size ar E (0, 1) can now be described succinctly as:
Oc+1 0, + onge (0.).
(2)
Under some mild technical conditions, it shown in (Tsitsiklis & Van Roy, 1997) that the iterates generated by TD(O) converge almost surely to the best lincar approximator in the span of { In particular, O: 0", where 0* is the unique solution of the projected Bellman equation Il IT (%0*) = 40" Here, D is a diagonal matrix with entries given by the elements of the stationary distribution of the kernel P. Moreover, (-) is the projection operator onto the subspace spanned by (ox (ok]ke[K] with respect to the inner product (.)) The key question we explore in this paper is: What can be said of the converyence of TD(O) when the update direction (fx))) in equation 2 is replaced by a distorted coonpressed version of i?? Tn the next. section, we will make the notion of distortion precise, and outline the various technical challenges that make
it non-trivial to answer the above question.
3 Error-Feedback meets TD Learning
In this section, we propose a general framework for analyzing TD learning algorithms with distorted update directions. Extreme forms of such distortion could involve replacing cach coordinate of the TD(0) direction with just its sign, retaining just k [K] of the largest magnitude coordinates and zeroing out the rest. In the sequel, will refer to these variants of TD(O) as SignTD(O) and Topk-TD(O), respectively. Coupled with memory mechanism known error-feedback, it is known that analogous variants of SGD exhibit, almost remarkably, the same behavior as SGD itself (Stich et al., 2018). Inspired by these findings, we ask: Does compressed TD(O) with error-feedback exhibil behavior similar to that of TD(O)
Our motivation behind studying the above question to build an understanding of: (i) communccation-cffiionn versions of MARL algorithms where agents exchange compressed mofel-difeesentilss i.c., the gradient-lin like updates (see Section 6); and (ii) the robusiness of TD learning algorithms to structured perturbations. It is

---

Published in Transactions on Machine Learning Research (04/2024)
important to reiterate here that our motivation mirrors that of studying perturbed versions of SGD in the context of optimization.
Description of EF-TD. In Algorithm 1, we propose the compressed TD(O) algorithm with error-feedback (EF-TD). Compared to equation 2, we note that the parameter 8, is updated based on h4 - a compressed version of the actual (D) direction gi (ft), where the compression due to the operator O : R + R The information lost up to time t 1 due to compression is accumulated in the memory variable et-1, and injected back into the current step as in equation 3. In line with compressors used for optimization, we consider fairly general operator Qs that is required to only satisfy the following contraction property for some 8 211 1:
|| 1Qs(0) - 011 = ( (1-b) 1101 40 E
(4)
A distortion perspective. For 0 * 0, it is casy to verify based on equation 4 that (Qs(0), 2 1/ > O, i.e,, the angle between (0) and 0 is acute. This provides an alternative view to the compression perspective: one can think of (x) as a tilted version of 0, with a larger implying more tilt, and 5 = 1 implying no distortion at all. See Figure 1 for a visual interpretation of this point.
The contraction property in equation 4 is satisfied by several popular ceantization/spaarsfietttt /sprsiffiaaiinnn schemes. These include the sign operator, and the Top-k operator that selects k coordinates with the largest. magnitude, zeroing out the rest. Importantly, note that the operator Qs does not necessarily yield an unbiased version of its argument. In optimization, crror-feedback serves to counter the bias introduced by Qs. In fact, without error-feedback, algorithms like SignSGD can converge very slowly, or not converge at all (Karimireddy et al., 2019). In a similar spirit, we empirically observe in Fig. 2 (later in Section 8) that without frror-foedback, SOg can end up making little to no progress towards 0*, However, understanding whether freor-feedback guarantees convergence to 8 is quite non-trivial. We now provide some intuition as why this is the case.
Need for Technical Novelty. Error-fcedback ensures that past (pseudo)-graddient information is injected with some delay. Thus, for optimization, error-feedback essentially leads to delayed SGD algorithm. As long as the objective function is smooth, the gradient does not change much, and the delay-effect can be controlled. This intuition does not carry over to our setting since the TD(O) update direction is not a stochastic gradient of any fized objective function.? 2 Thus, controlling the effect of the compressor-indunt induced delay requires new techniques for our setting. Moreover, unlike the SGD noise, the data tuples {Xt) are part of the same Markov trajectory, introducing further complications. Finally, since the parameter updates of Algorithm are intricatcly linked with the error variable e,, to analyze their joint bchavior, we need to perform a more refined Lyapunov drift analysis relative to the standard TD(O) analysis. Despite these challenges, in the sequel, we will establish that EF-TD retains almost the same convergence guarantees as vanilla TD(O).
Remark 1. It is important to emphasize that even though the error vector e, in EF-TD might be dense, never gets transmitted. The
aspect of EF-TD stems from the fact that it only requires communicating the compressed update direction by - a vector that can be represented by using just a few bits (depending on the level of compression). This fact is further clarified in our description of the mulli-agent version of EF-TD in Section (see line 6 of Algorithm 2 in Section 6).
4 Analysis of EF-TD under Markovian Sampling
The goal of this section is to provide a rigorous finite-time analysis of EF-TD under Markovian sampling. To that end, we need to introduce a few concepts and make certain standard assumptions. We start by assuming that all rewards are uniformly bounded by some F >> 0, i... [R(s)] functions exist. Next, we state a standard assumption that shows up in the finite-time analysis of itcrative RL algorithms (Bhandari et al., 2018; Srikant & Ying, 2019; Chen et al., 2019; Patil el al., 2023; Doan el al., 2019; Khodadadian et al., 2022).
Vs E S. This ensures that the value
Assumption 1. The Markov chain induced by the policy μ is aperiodic and irreducible.
AA observed Bhandari et al. (2018) and Liu & Olshevsky (2021b), this can be seen from the fact that the derivative of the TD update direction produces matrix that is not necessarily symmetric, unlike the symmetric Hessian matrix of fixed objective function.
7

---

Published in Transactions on Machine Learning Research (04/2024)
The above assumption implics that the Markov chain induced by μ admits a unique stationary distribution
и (Levin & Peres, 2017). Let Σ = Φ DΦ. Since + is full column rank, Σ is full rank with strictly positive smallest eigenvalue w < 1. To appreciate the implication of the above assumption, let us define the "steady-state" version of the TD update direction as follows: for a fixed A E IR let
g00) A E PunT ())
We now introduce the notion of the mixing time Te. Definition 1. Define To minft 2 1: | (Xx, xx) - a(0)l22 S (11012 + vK
v 2 1, E ; vXo).
Assumption 1 implies that the total variation distance between the conditional distribution P (st - s) and the stationary distribution decays geometrically fast for all & 2 0, regardless of the initial state E S (Levin & Peres, 2017). As a consequence of this geometric mixing of the Markov chain, it is not hard to show that T, in Definition 1 is O (log(1/c)); see, for instance, Chen et al. (2019). The precision that suffices for all results in this paper is E = a², where recall that is the step-size. Henceforth, we will simply use т as a shorthand for Ta- Finally, let us define a - m1, F, (0] as the variance of our noise model, and de - 110, - 0" 112. We can now state the first main result of this paper.
Theorem 1. Suppose Assumption 1 holds. There ezist universal constants c, o,C 2 1 such that the iterates -(1-7) satisfy the following VT T:
generated by EF-TD with step-size S cmaxtó,7]
(1 ( )
aww(1
T-T +0
[((T [a(r++ 880²) ( w(1 77) (w(1-))/
d S Ci
where C1 = Od8 + o²).
(5)
CT
The proof of Theorem 1 is provided in Appendix D. We now discuss the key implications of this result.
Discussion. Theorem 1 tells us that EF-TD guarantees linear convergence of the iterates to a ball around 0r, where the size of the ball scales with the variance o²; this exactly matches the behavior of vanilla TD (Bhandari et al., 2018; Srikant & Ying, 2019). Since the step-size a scales inversely with the distortion factor 6, we observe from equation that the exponent of linear convergence gets slackened by d; once again, this is consistent with analogous results for SGD with (biased) compression (Beznosikov al., 2020). The variance term, namely the second term in equation 5, has the eract same dependence on 7,4, and y one obscrves for vanilla TD (Bhandari et al., 2018, Theorem 3). Observe that in this term, the effects of and 5 in inflating the variance are additive. Moreover, even in the absence of compression, the dependence of the variance term on the mixing time T is known to be unavoidable (Nagaraj et al., 2020). This immediately leads to the following interesting conclusion: when the underlying Markov chain induced by the policy mines "slowly', ; i.e., has a large miring lime T, one can afford to be more aggressive in lerms of compression, i.e., use a larger 8, since this would lend to a variance bound that is no worse than in the uncompressed setting. Said differently, Theorem reveals that slowly-mixing Markov chains have higher tolerance to distortions. This observation is novel since no prior work has studied the effect of distortions to RL algorithms under Markovian sampling. It is also interesting to note here that the phenomenon described above shows up in other contexts too: for instance, the authors in Gandikota et al. (2021) showed that certain quantization mechanisms in optimization automatically come with privacy guarantees.
Theorem 1 significant in that is the first result to reveal that coupled with error-feedback, EF-TD is robust to extreme distortions. We will corroborate this phenomenon empirically as well Section 8. The other key (akeaway from Theorem I is that the scope of the errockfeedback mechanism now popularly used in distributed learning extends to stochastic approximation problems well beyond just static optimization settings.
In Appendix B, we analyze a simpler steady-stale version of EF-TD to help build intuition. There, we also provide an analysis of compressed TD learning algorithms that do not employ any error- feedbacek mechanism. Our analysis reveals that such schemes can also converge, provided the compression parameter 5 satisfies a restrictive condition. Notably, as evident from the statement of Theorem 1, we do not need to impose any restrictions on 5 for the convergence of EF-TD.
8

---

Published in Transactions on Machine Learning Research (04/2024)
5 Compressed Nonlinear Stochastic Approximation with Error-Feedback
For the TD(O) algorithm, the update direction (o) is affinc in the parameter 8, i.c., lc(0) is of the form A(X:) - -())). As such, the recursion in equation 2 can be seen as an instance of linear stochastic approximation (SA), where the end goal is to use the data samples {X+} to find a I that solves the linear equation AO b; here, A and b are the stcady-state versions of A(X,) and b(X,); respectively. The more involved (D) algorithms within the TD learning family also turn out be instances of linear SA. Instead of deriving versions of our results for TD(A) algorithms in partieular, we will instead consider much more general nonlinear SA setting. Accordingly, nonlinear map, and as before, Xt comes from a finite-state Markov chain that is assumed to be aperiodic and irredueible. We assume that the nonlinear map satisfies the following regularity conditions.
now study variant of Algorithm where g(Xe, 0) is general
Assumption 2. There erist L, 2 1 s.t. the following hold for any X in the space of data tuples: (i) [l - 02)l2 & L| - 02|12, V01, 02 E RRK and (ii) (l((x,))e
T([10112 + v R
Assumption 3. Let g(0) & Ex,-= [g(Xx, f)), 40 E TR=K where л is the stationary distribution of the Markov process {Xr}. The equation g(0) = has a solution 0*, and 33 > s.t.
(0- 0-, , g0( g(0))) S - v0 E
(6)
In words, Assumption 2 says that ()))0) is globally uniformly (w.r.t. X) Lipschitz in the parameter 0. Assumption 3 is strong monotone property of the map -9(0) that guarantees that the iterates generated by the steady-state version of equation 2 converge exponentially fast to 8". To provide some context, consider the TD(O) setting. Under feature normalization and the bounded rewards assumption, the global Lipschitz property immediate. Moreover, Assumption 3 corresponds to negative-definitenss of the steady-state matrix A = Ex,~ [A(X:]] this negative-defiiite property is also easy to verify (Srikant & Ying, 2019). For optimization, Assumptions 2 and 3 simply correspond to L-smoothness and convexity of the loss function, respectively For simplicity, we state the main result. of this section for L. 2; the analysis for a general L follows identical arguments.
Theorem 2. Suppose Assumption 2 holds with L = 2, and Assumption 3 holds. Let B min (,,1//11111000 1/8). There ezist universal constants c, CCC2 such that Algorithm with step-size a S emaxto.7] guarantees
B
E [ Si (1- a3 CT
(1-08)
T-T
+0 ar(T [a(T+
+ ( B
(1- (1-or)
VT 2 where Ci = 0 + 0
(7)
Discussion. We note that the guarantec in Theorem 2 mirrors that in Theorem and represents our setting in its full generality, accounting for nonlinear SA, Markovian noise, compression, and error-feedback. Providing an explicit fiiie--ime analysis for this setting is one of the main contributions of our paper. Now let us comment on the applications of this result. As noted earlier, our result applics to TD(A) algorithms and SGD under Markovian noise (Doan, 2022); the effect of compression and error-feedback was previously unknown for both these settings. More importantly, certain instances of Q-learning with linear function approximation can also be captured via Assumptions 2 and 3 (Chen et al., 2019). The key implication that our analysis framework is not just limited to policy evaluation, but rather extends gracefully to decision-making (control) problems. This speaks to the significance of Theorem 2.
6 Communication-Effiiee
Aulti-Agent Reinforcement Learning (MARL)
A key motivation of our work is to develop commmicatiion-efiiieenn algorithms for MARL. This is particularly relevant for hettorkeddfederrtteee
versions of RL problems where communication imposes a major bottleneck (Qi et al., 2021). To that end, we consider a collaborative MARL setting that has appeared in various recent works (Qi et al., 2021; Doan el al., 2019; Liu & Olshevsky, 2021a; Jin el al., 2022; Khodadadian et al., 2022; Shen et al., 2023). The setup comprises of M agents, all of whom interact with the same MDP, and can communicate via a central server. Every agent socks to evaluate the same policy μ. The purpose of collaboration is as in the standard FL setting: achieve a M-lold reduction in sample-complexity by leveraging information from all agents. In particular, we ask: By erchanging compressed information via the
9

---

Published in Transactions on Machine Learning Research (04/2024)
Algorithm 2 Multi-Agent EF-TD
Input: Initial estimate 8 E RK initial errors c,,- = 0, Vi e [M], and step-size (0,
for t 0, I.... do
Server sends 92 to all agents.
4: for E [M] do
5:
Observe tuple X = (st,r, s1,4+.
6: Compute compressed TD(O) direction h4 = 2s (ci,--1 (i,) and send hig to server.
7: Update error: C,,t = c + (r,)(0)) hi,e
end for
Server updates the model follows: os+1 02 + ah,, where (1/M) Eie(m hic
10: end for
server, possible expedite the process of learning by achiewing linear speedup in the number of agents? While such questions have been extensively studied for supervised learning, we are unaware of any work that addresses them in the context of MARL. We further note that even without compression or error-feedback; establishing linear speedups under Markovian sampling is highly non-trivial, and the only other paper that does so is the very recent work of Khodadadian et al. (2022). As we explain later in Section 7, our proof technique departs significantly from (Khodadadian et. al., 2022).
We propose and analyze a natural multi-agent version of EF-TD, outlined as Algorithm 2. In a nutshell, multi-agent EF-TD operates as follows. At each time-step, the server sends down a model 8G; each agent observes a local data sample, computes and uploads the compressed direction ha,,, and updates its local error. The server then updates the model. Transmitting compressed TD(O) pscudo-gradients is consistent with both works in FL (Karimireddy et al., 2020), and in MARL (Qi et al., 2021; Doan et al., 2019; Khodadadian et al., 2022), where the agents essentially exchange modee-diiferentiall (i.e., the update directions), keeping their raw data private. It is worth noting here that while all agents play the same policy, the realizations of the data tuples { may vary across agents. Let Og = 6g + ac--1, where éN = (1/M) ΣiE(M) Ci and define d, A
||0, 8* 1l.. We can now state our main convergence result for Algorithm 2.
Theorem 3. Suppose Assumption holds. There crist universal constants c, C 2 such that with step-size w(1->) and C₁ = O(b + o²)) Algorithm guarentees the following VT 2 2r:
a < cmax(6.7]
E [ <
Ci C1 11
aw(1 - -7)
T-27
aT
0²
+0
a² max TJ0 w² 7)
0².
(8)
CT
- 7) w
M
Ti
T2
The proof of Theorem deferred to Appendix E. There are several key messages conveyed by Theorem 3. We discuss them below.
Message 1: Linear Speedup. Observe that the noise variance terms in equation are To and T3, where T3 is O(a²), i.e., higher-order term in Thus, for small T2 is the dominant noise term. Compared to the noise term for vanilla TD in (Bhandari et al., 2018, Theorem 3), T2 in our bound has exactly the same dependence on T, w, and y, and importantly, exhibits an inverse scaling w.r.t. M, implying a M M-fold reduction in the variance 2² relative to the single agent selting. This is precisely what we wanted. For exact. convergence, we can set a ((log(MTT).
to make T₁ and T3 of order Ö(1/T²), and the dominant term To = ((00((/2/00 0(02 (MT)). Thus, relative to the ( /T) rate of TD(O), we achieve linear speedup w.r.l. the number of agents M in our dominant term T2.
Mcssage 2: Communication-cffcccnny comes (ncarly) for free. The sccond key thing to note is that the dominant T2 term is completely unaffected by the compression faclor ö. Indeed, the compression factor 8 only affects higher-orden terms that decay much faster than Tz. This means that we can significantly ramp up 8, thereby communicating very little, while preserving the asymptotic rate of convergence of TD(0) and achieving optimal speedup in the number of agents, i.e., communication- -efeiiiinnfff comes almost for free. For instance, suppose 2a(-) top-1 operator, i.e. hi, has only one non-zero entry which can be encoded using
10

---

Published in Transactions on Machine Learning Research (04/2024)
(11 bits. In this case, although 8 = K, where K is the potentially large number of features, the dominant Ô term remains unaffected by K. Thus, in the context of MARL, our work is the first to show that asymptotically optimal rates can be achieved by transmitting just Ó(1) bits per-agent per time-step.
Mcssage 3: Tight Dependence on the Mixing Time. Compared to Khodadadian et al. (2022) the only other paper in MARL that provides a linear speedup under Markovian sampling- our dominant term 72 has a tighter ((T) dependence on the mixing time T as compared to the O(r²) dependence in Khodadadian et al. (2022, Theorem 4.1). It should be noted here that the O(T) dependence is known to be information-theortienn optimal (Nagaraj et al., 2020).
A few remarks are in order before we end this section.
We nole that the bound in Theorem 3 is stated for 0r, not Or. Since Or Or + cer-1, to oulpul br, the server needs to query GiT-1 from each agent ondy once at time T -11. 1. We believe that this one extra step of communication can also be avoided via a slightly sharper analysis. We provide such an analysis in Appendiz F, albeit under a common it sampling model (Dalal et al., 2018; Doan et al., 2019; Liu E Olsheusky, 2021a).
Remark 2.
Remark 3. While our MARL result in Theorem 3 is for TD learning, in light of the developments in Section 5, we note that one can develop anologs of Theorem 3 for mulli-agent Q-learning as well.
Remark 4. Suppose we set M 11 in equation 8, and compare the resulting bound with that in equation 5. While the effect of the distortion 8 shows up as a higher-order O(a²) lerm in the former, il manifests O(a) term in the latter. The difference in these bounds can be attributed to the fact that we use finer Lyapunov function to prove Theorem 3 relative to that which we use to prove Theorem 1. We do so primarily for the sake of exposition: the relatively simpler proof of Theorem (compared to Theorem 3) helps build much of the key intuilion needed to underslond the proof of Theorem 3.
7 Technical Challenges in Analysis and Overview of our Proof Techniques
We now discuss the novel steps in our analysis. Complete proof details are provided in the Appendix.
Proof Sketch for Theorem 1. Inspired by the perturbed iterate framework of Mania et al. (2015), our first
step is to define the perturbed iterate 0, = 0, + ae Simple calculations reveal: 0.+1 = 0, + (0.). Notice that this recursion is almost the same as equation 2, other than the fact that the TD(0) update direction is evaluated at 6g instcad of &. Thus, to analyze the above recursion, we need to account for the gap between O, and Ú., the cause of which is the memory variable 4t-1. Accordingly, our next key step is to construct a novel Lyapunov function the that captures the joint dynamics of 0g and 6--1:
(9) As for as we are aware, a potential function of the above form has not been analyzed in prior RL work. Our goal now is to exploit the geometrie mixing property in Assumption to establish that the decays over time (up to noise terms). This is precisely where the intricate coupling between the parameter 0z, the memory variable et, and the Markovian data tuples {X,} makes the analysis quite challenging. Let us claborate. To exploit mixing-time arguments, we need to condition sufficiently into the past and bound drift terms of the form |10, - 0.-rl12- This is where the coupling between 0, and e, introduces non-standard delay terms, precluding the direct use of prior approaches in RL (Bhandari et al., 2018; Srikant & Ying, 2019; Chen et al., 2019). This difficulty does not show up in compressed optimization since one deals with i.i.d. data, precluding the need for mixing-time arguments. A workaround here is to employ projection step (as in Bhandari et al. (2018); Doan et al. (2019)) to simplify the analysis. This is not satisfying for two reasons: (i) we show in the Appendix, the simplification in the analysis comes at the cost of a sub-optimal dependence on the distortion ó; and (ii) to project, one needs prior knowledge of the set containing 0*; this turns out to be unnecossary. Our key innovation here to bound the drift ||0e- - 0.-ill is the following tochnical lemma.
1I A Eld + al11ee-11121. where d: = 1|0
11. 1...-
Lemma 1. (Relating Drift to Past Shocks) For EF-TD, the following is true Vt 2 T:
Ell@. 0 = 0(a²72)
max the 0(227203).
(10)
11

---

Published in Transactions on Machine Learning Research (04/2024)
10
10
10
TD
TD
10a
EF- -DggnDD
10a
Ei-SigTTD
SignTT TD
SignTD
10
10a
10
10a
10a
10
10a
10a
10a
10a
10*
t
t
Figure 2: Plots of the mean-squared error E, = ||0 - 00 for vanilla TD(O) without compression, and S1g with (EF-SignTD) and without (SignTD) frrob-eeedback. (Left) Discount factor y = 0.5. (Right) Discount factor 7 0.9.
The above lemmn relates the drift to damped "shocks' (delay terms) from the past, where (i) the amplitude of the shocks is captured by our Lyapunov function; (ii) the duration of these shocks is the mixing time t; and (iii) the damping arises from the fact that shocks are scaled by a². In attempting to overcome one difficulty, we have created another for ourselves via the "max" term in equation 10. This is where we make a connection to the analysis of the IAG algorithm in Gurbuzbalaban et al. (2017) where a similar "max' term shows up. Via this connection, we are able analyze the following final recursion:
dee1 s cow 7))xkr + O(a²T) max the + O(a²) 8)o², where e < 1.
(11)
(-rses)
Proof Sketch for Theorem To establish the linear speedup property, we need a finer Lyapunov function (and much finer analysis) relative to Theorem Accordingly, we construct:
M Σ
12 + Ca where E, E a E 01,
E
lee
(12)
M
and C' is suitable design parameter. Using the techniques in Bhandari et al. (2018), Srikant & Ying (2019), and Chen et al. (2019) to bound (0)l² unfortunately do not yield the desired linear speedup. Moreover, it is unclear whether the Generalized Moreau Envelope framework in Khodadadian et al. (2022) can be extended to analyze equation 12. As such, we depart from these works by establishing the following key result by carefully exploiting the geometric mixing property.
Lemma 2. Let (6.) & (1/M) ΣiEMM (0.). Under Assumption 1, the following bound holds for Algo- rithm 2: [[[ z (0:) (()) + +(aa)), O(1/M a a²) 2
The above norm bound on the average TD direction turns out to be the main ingredient in bounding the drift terms for Algorithm and eventually establishing a recursion of the form in equation 11 for E,
8 Simulations
To corroborate theory, construct MDP with 100 states, and use feature matrix & with K 10 independent basis vectors. Using this MDP, we generate the state transition matrix P,, and reward vector R, associated with fixed policy μ. We compare the performance of the vanilla uncompressed TD(O) algorithm with linear function approximation to SignTD(O) with and without error-feedback. We perform 30 independent trials, and average the errors from each of these trials to report the mean-squared error E, = ||0 - 101 for each of the algorithms mentioned above. The results of this experiment are reported in Fig. We observe that in the absence of error- frebbck, (0) can make little no progress towards 8*. In contrast, the behavior of Sig with prror-feedback almost exactly matches that of vanilla uncompressed TD(O). Our
12

---

Published in Transactions on Machine Learning Research (04/2024)
30
1000
2009
3000
4000
5000
6008
7003
8000
9000
10503
t
Figure 3: Plot of the mean-squared error E, 1|0, 0 1 for EF-TD (Algo, 1), with 2s(-) chosen be the top-k operator. We study the effect of varying the number of components transmitted k.
Figure 4: Plots of the mean-squared error E, ||rr- 00 for multi-agent EF-TD (Algorithm 2). (Left) Qs(-) is the sign operator. (Right) Qs(-) is the Top-k operator with & 2.
results aligu with similar observations made in the context optimization, where SignSGD with error-feedback retains almost the same behavior as SGD with no compression (Stich al., 2018; Karimireddy et al., 2019). We provide some additional experiments below.
Simulation of Topk-TD(O) with Qs(+) chosen to be top-k operator. We consider the same MDP above, with the rewards for this experiment chosen from the interval [0 1]. The size of the parameter vector K is 50, and the discount factor y is set to be 0.5. We vary the level distortion introduced by Qs(-) by changing the number components k transmitted. Note that 5 = K/k. As one might expect,, increasing the distortion by transmitting fewer components impacts the exponential docay rate; this is clcarly reflocted in Fig. 3.
We simulate the behavior of EF-TD with the operator
Simulation of Multi-Agent EF-TD. To simulate the behavior of multi-agent EF-TD (Algorithm 2), we consider the same MDP on 100 states before with rewards in [0 1]. The dimension K of the parameter vector is set to 10 and the discount factor y to 0.3. We consider two cases: one where Qs(-) is the sign operator, and another where it is a top-2 operator, i.e., only two components are transmitted by each agent at every time-step. We report our findings in Fig. 4, where we vary the number of agents M, and observe that for both the sign- and top-k operator experiments, the residual mean-squared error goes down as we scale up M. Since the residual error is essentially an indicator of the noise variance, our plots display clear effect. of variance reduction by increasing the number of agents. Our observations thus align with Theorem 3.
13

---

Published in Transactions on Machine Learning Research (04/2024)
9 Conclusion and Future Work
We contributed to the development of robustness thcory for itcrative RL algorithms subject to general compression schemes. In particular, we proposed and analyzed EF-TD a compressed version of the classical TD(0) algorithm coupled with error-compensation. We then significantly generalized our analysis to nonlinear stochastic approximation and multi-agent settings. Concretely, our work conveys the following key messages: (i) compressod TD learning algorithms with error-ceedback can be just as robust as their optimization counterparts; (ii) the popular error-feedback mechanism extends gracefully beyond the static optimization problems it has been explored for thus far; and (iii) linear convergence speedups in multi-agent TD learning can be achieved with very little communication. Our work opens up several research directions. Studying alternate quantization schemes for RL and exploring other RL algorithms (beyond TD and Q-learning) are immediate next steps. A more open-ended question is the following. SigmSCD with momentum (Bernstein et al., 2018) is known to exhibit convergence behavior very similar to that of adaptive optimization algorithms such as ADAM (Balles Hennig, 2018), explaining their use in fast training of deep neural works. In a similar spirit, can we make connections between SignTD and adaptive RL algorithms? This is an interesting question to explore since its resolution potentially lead to faster RL algorithms.
14

---

Published in Transactions on Machine Learning Research (04/2024)
References
Alham Fikri Aji and Kenneth Heafield. Sparse communication for distributed gradient descent. aiv preprint wrXiv:1704.0500 2017.
Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. Qsgd: Communicttion-cffiicti sgd via gradient quantization and encoding. Advances in Newral Information Processing Systems, 30: 1709-1720, 2017.
Dan Alistarh, Torsten Hoeller, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. The convergence of sparsified gradient methods. In Advonces in Neural Information Processing Systems, pp. 5973-5983, 2018.
Lukas Balles and Philipp Hennig. Dissecting adam: The sign, magnitude and variance of stochastic gradients. In International Conference on Machine Learning, pp. 404-413. PMLR, 2018.
Jeremy Bernstein, Yu-Xiang Wang, Kamyar Arizzaenesheli, and Animashree Anandkumar. signsgd: Compressed optimisation for non-convex problems. In International Conference Machine Learning, pp- 560-569. PMLR, 2018.
Aleksandr Beznosikov, Samuel Horváth, Peter Richtárik, and Mher Salaryan. On biased compression for distributed learning. arXiv preprint arXiv:2002. 12410, 2020.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pp. 1691-1692. PMLR, 2018.
Vivek S Borkar. Stochastic approzimation: dynamical systems vieupoint, volume 48. Springer, 2009.
Vivek S Borkar and Sean P Meyn. The ode method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447-48) 2000.
Zaiwei Chen, Sheng Zhang, Thinh T Doan, Siva Theja Maguluri, and John-Paul Clarke. Performance of q-learning with linear function approximation: Stability and finite-time analysis. arXiv preprinl. 9rXiv:1905.11425 pp. 4, 2019.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for td (0) with function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Thinh Doan, Siva Maguluri, and Justin Romberg. Finite-time analysis of distributed td (0) with linear function approximation on multi-agent reinforcement learning. In International Conference on Machine Learning, pp. 1626-1638 PMLR, 2019.
Thinh Doan. Finito-time analysis of markov gradient descent. IEEE Transactions on Automatic Control, 2022.
Hamid Reza Feyzmahdavian, Arda Aytekin, and Mikacl Johansson. A delayed proximal gradient method with linear convergence rate. In 2014 IEFE international workshop on machine learning for signal processing (MLSP), pp. 1-6 6. IEEE, 2014.
Venkata Gandikota, Daniel Kane, Raj Kumar Maity, and Arya Mazumdar. vasgd: Vector quantized stochastic gradient descent. In International Conference on Artificial Intelligence and Statistics, pp. 2197 2205. PMLR, 2021.
Eduard Gorbunov, Dmitry Kovalev, Dmitry Makarenko, and Peter Richtárik. Lincarly converging error compensated sgd. Advances in Neural Information Processing Systems, 33, 2020.
Robert M Gray. Source coding theory, volume 83. Springer Science & Business Media, 2012.
Kaja Gruntkowska, Alexander Tyurin, and Peter Richtárik. Ef21-p and friends: Improved theoretical communication complexity for distributed optimization with bidirectional compression. arXiv preprint r-Xii:2209.1228 2022.
15

---

Published in Transactions on Machine Learning Research (04/2024)
Mert Gurbuzbalaban, Asuman Ozdaglar, and Pablo A Parrilo. On the convergence rate of incremental aggregated gradient algorithms. STAM Journal on Oplimization, 27(2):1035 2017.
Osama A Hanna, Lin Yang, and Christina Fragouli. Solving multi-arm bandit using few bits of communication. International Conference on Artificial Intelligence and Statistics, pp. 11215-11236. PMLR, 2022.
Roger Horn and Charles R Johnson. Matriz analysis. Cambridge university press, 2012.
Hao Jin, Yang Peng, Wenhao Yang, Shusen Wang, and Zhihua Zhang. Federated reinforcement learning with environment heterogeneity. In International Conference on Artificial Intelligence and Statistics, pp. 18 37. PMLR, 2022.
Sai Pranceth Karimireddy, Quentin Rebjock, Scbastian U Stich, and Martin Jaggi. Error feedback fixes signsgd and other gradient compression schemes. ar preprinl ar Xrv:::1900 190000081987 2019.
Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha. Suresh. Scaffold: Stochastic controlled averaging for federated learning. In Inter- national Conference on Machine Learning, pp. 5132-5143. PMLR, 2020.
Sajad Khodadadian, Pranay Sharma, Gauri Joshi, and Siva Theja Maguluri. Federated reinforcement learning: Linear speedup under markovian sampling. In International Conference on Machine Learning, pp. 10997-11057. PMLR, 2022.
Anastasia Koloskova, Nicolas Loizou, Sadra Borciri, Martin Jaggi, and Sebastian U Stich. A unified theory of decentralized sgd with changing topology and local updates. arXiv preprinl arXiv:2033.100 10422, 2020.
Jakub Konečný, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. Federated optimization: Distributed machine learning for on-device intelligence. arXiv preprint arXim:6610.02527, 2016.
Nathaniel Korda and Prashanth La. On td(0) with function approximation: Concentration bounds and a centered variant with exponential convergence. In International conference on machine learning, pp- 634. PMLR, 2015.
Chandrashekar Lakshminarayanan and Csaba Szepesvári. Linear stochastic approximation: Constant step-size and iterate averaging. arXiv preprint arXiv: 10t::10090000 709.04073. 2017.
David A Levin and Yuval Peres. Markow chains and mixing times, volume 107. American Mathematical Soc., 2017.
Chung-Y Yi Lin, Victoria Kostina, and Babak Hassibi. Differentially quantized gradient methods. 1EEE Transactions on Information Theory, 2022.
Yujun Lin, Song Han, Huizi Mao, Yu Wang, and William Dally. Deep gradient compression: Reducing the communication bandwidth for distributed training. arXiv preprint arXiv:1712.01887, 2017.
Rui Liu and Alex Olshevsky. Distributed td (0) with almost no communication. arXiv preprint 07X 2021a.
Rui Liu and Alex Olshevsky. Temporal difference learning gradient splitting. In International Conference on Machine Learning, pp. 6905-6913. PMLR, 2021b.
Horia Mania, Xinghao Pan, Dimitris Papailiopoulos, Benjamin Recht, Kannan Ramchandran, and Michael I Jordan. Perturbed iterate analysis for asynchronous stochastic optimization. Xiv preprinl (XXiv1507.00677) 2015.
Prathamesh Mayckar and Himanshu Tyagi Ratq: universal fixed-length quantizer for stochastic opti- mization. In International Conference on Artificial Intelligence and Statisties, pp. 1399-1409, PMLR, 2020.
16

---

Published in Transactions on Machine Learning Research (04/2024)
Aritra Mitra, Rayana Jaafar, George J Pappas, and Hamed Hassani. Linear convergence in federated learning: Tackling client heterogeneity and sparse gradients. Adoances in Newral Information Processing Systems, 34: 14606 14619, 2021.
Aritra Mitra, Hamed Hassani, and George J Pappas. Linear stochastic bandits over a bit-constrained channel. arXiv preprint Xrx::22003.0 01198, 2022.
Dhecraj Nagaraj, Xian Wu, Guy Bresler, Prateck Jain, and Pranccth Netrapalli. Least squares regression with markovian data: Fundamental limits and algorithus. Advances in neural information processing systems, 1816666-16676, 2020.
C Narayanan and Csaba Szepesvári. Finite time bounds for temporal difference learning with function approximation: Problems with some "state-of-the-art" results. Technical report, Technical report, 2017.
Angelia Nedic, Asuman Ozdaglar, and Pablo A Parrilo. Constrained consensus and optimization in multi-agent networks. IEEE Transactions Automatic Control, 55(4):922-99) 2010.
Francesco Pase, Deniz Gündüz, and Michele Zorzi Remote contextual bandits. In 2022 IEEE International Symposium on Information Theory (ISIT), pp. 1665 1670. IEEE, 2022.
Gandharv Patil, LA Prashanth, Dheeraj Nagaraj, and Doina Precup. Finite time analysis of temporal difference learning with linear function approximation: Tail averaging and regularisation. In International Conference on Artificial Intelligence and Statistics, pp. 5438 5448. PMLR, 2023.
Jiaju Qi, Qihao Zhou, Lei Lei, and Kan Zheng. Federated reinforcement learning: techniques, applications, and open challenges. arXiv preprint or 1tt:2108.11887 2021.
Peter Richtárik, Igor Sokolov, and Tyas Fatkhullin. Ef21: A new, simpler, theoretically better, and practically faster error feedback. Advances in Neural Information Processing Systems, 34:4384 4396, 2021.
Rajarshi Saha, Mert Pilanci, and Andrea J Goldsmith. Efficient randomized subspace embeddings for distributed optimization under a communication budget. IEEE Journal on Selecled Areus in Information Theory, 2022.
Frank Seide, Hao Fu, Jasha Droppo, Gang Li, and Dong Yu. 1-bit stochastic gradient descent and its application to data-parallel distributed training of speech dnns. In Fifteenth Annual Conference of the International Speech Communication Association, 2014.
Han Shen, Kaiqing Zhang, Mingyi Hong, and Tianyi Chen. Towards understanding asynchronous advantage actor-critic: Convergence and linear speedup. IEEE Tronsactions on Signal Processing, 2023.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. In Conference on Learning Theory, pp. 2803-2830 PMLR, 2019.
Sebastian U Stich. On communication compression for distributed optimization on heterogeneous data. anXiv preprint ar xrXi:22009.000 02388, 2020.
Sebastian U Stich and Sai Praneeth Karimireddy. The error-feedback framework: Better rates for sgd with delayed gradients and compressed communication. arXiv preprint MXXix:999.003350 2019.
Sebastian U Stich, Japn-tae Cordonnier, and Martin Jaggi. Sparsified sgd with memory. In Advances in Neural Information Processing Systems, pp. 4447-4458, 2018.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3(1):944 1988.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018
John N Tsitsiklis and Benjamin Van Roy. An analysis of temporal- learning with function approxi- mation. In IEEF Transactions Automatic Control, 1997.
17

---

Published in Transactions on Machine Learning Research (04/2024)
Wei Wen, Cong Xu, Feng Yan, Chumpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. Terngrad: Ternary gradients to reduce communication in distributed deep learning. Tn Advances in neural information processing systems, pp. 1509 1519, 2017.
18

---

Published in Transactions on Machine Learning Research (04/2024)
Contents
1 Introduction
1
1.1 Our Contributions
2
1.2 Related Work
4
2 Model and Problem Sctup
5
3
Error-Feedback meets TD Learning
6
4 Analysis of EF-TD under Markovian Sampling
7
Compressed Nonlinear Stochastic Approximation with Error-Feedback
9
6
Communication-Bffiien Multi-Agent Reinforcement Learning (MARL)
9
7 Technical Challenges in Analysis and Overview of our Proof Techniques
11
8 Simulations
12
9 Conclusion and Future Work
14
A Preliminary Results and Facts
20
B Building Intuition: Analysis of Mean-Path EF-TD
22
B.1 Can Compressed TD Methods Without Error-Feedback Still Converge?
25
C Warm-Up: Analysis of EF-TD with a Projection Step
27
D Analysis of EF-TD without Projection: Proof of Theorem 1 and Theorem 2
34
D.1 Bounding the Drift and Bias Terms
36
E Analysis of Multi-Agent EF-TD: Proof of Theorem
42
F Analysis of Multi-Agent EF-ID under an I.L.D. Sampling Assumption
50
19

---

Published in Transactions on Machine Learning Research (04/2024)
A Preliminary Results and Facts
In this section, we will compile and derive some preliminary results that will play a key role in our subsequent analysis. In what follows, unless otherwise stated, we will use || to refer to the standard Euclidean norm. The next three results are from Bhandari al. (2018).
Lemma 3. For all 81, I we have:
Vo - 0211 S lIVe, VegllD 1 1 02
We remind the reader here that in the above result, w is the smallest eigenvalue of the matrix 2' = - Dœ. Before stating the next result, we recall the definition of the steady-state TD update direction: for a fixed R let
( Res. (X,,, 0)]
The next lemma provides intuition as why the expected steady-state TD(0) update direction g(0) acts like "pseudo-gradient, driving the (D( iterates towards the minimizer 0 of the projected Bellman equation. Lemma 4. For any 0 E RKK the following holds:
(0 - (.)( (1 >>1V Vo
We will have occasion the following upper bound on the norm of the steady-state TD(0) update direction. Lemma 5. For any E RK the following holds:
|m(0) s 2 Volln.
The following bound on the norm of the random TD(0) update direction will also be invoked several times in analysis (Srikant & Ying, 2019).
Lemma 6. For any 0 E RK, the following holds VI. 2 0:
[1).(0)1 s 2||0|| 2F s 2||0|| 20,
(13)
where F1,
As mentioned earlier in Section 3, compressed SGD with error-feedback essentially acts like delayed SGD. Thus, for smooth functions where the gradients do not change much, the effect of the delay be effectively controlled. Unlike this optimization setting, we do not have fixed objective function at our disposal. So how do we leverage any kind smoothness property? Fortunately for us, the steady-state TD(O) update direction does satisfy a Lipschitz property; we prove this fact below.
Lemma 7. (Lipschitz property of steady-state TD(O) update direction) For all 0,, R we have: lg{(0;) g(02)ll < |0= - 021l-
Proof. We will make use of the explicit affine form g(0) shown below (Tsitsiklis Van Roy, 1997):
g(0) = T D (T, T0)= = A0 - b, where A T TD (rp, I) and b= - DR
(14)
In Bhandari et al. (2018), it was shown that A A < Σ, where Σ = & DΦ. Furthermore, due to feature normalization, it is easy to see that Amax (E)= < 1. Using these properties, we have:
llū(0;) {(22)1 (0, 0z) A Ā (0; 02)
S Amax (AT 0) 02
(15)
< Amax [2][0] 0211²
< 101 02112
which leads to the desired claim. For the first inequality above, we used the Rayleigh- Ritz theorem (Horn & Johnson, 2012, Theorem 4.2.2).
20

---

Published in Transactions on Machine Learning Research (04/2024)
An immediate consequence of the above result, in tandem with the fact that g(0*) O, is the following upper bound on the norm of the steady-state TD(O) update direction: 40 E IR we have
|0||| to. |g( ((((0) g(00) - 10 00
(16)
Essentially, this shows that the bound in Lemma 6 applies to the steady-state TD(0) update direction as well. Next, we prove an analog of the Lipschitz property in Lemma 7 for the random TD(0) update direction.
Lemma 8. (Lipschitz property of the noisy TD( update direction) For all 01, 02 IK have:
(lg)(0)) (02) - 2| 02|1-
Proof- As in the proof of Lemma 7, will the fact that the TD(O) update direction is affine function of the parameter 0. In particular, we have
ge(0) = A(X,) b(X,), where A(X,) " ($142) (bs:) (s))) and b, ((())r
Thus, have
(0,) - (9(())) = ||A(X)) (01 82)
$ ||A(x)) 02ll
(17)
11 1|0 021l
$ 2 - 02/1.
where for the last step we used that [|)()) s 1, Vs E
In addition to the above results, we will make use the following facts.
Given any two vectors x, y RK the following holds for any 77 > 0:
I + vll s (1+
11 ||.l1
(18)
Given m vectors 3i, Fm E RRK the following is a simple application of Jensen's inequality:
m
|
(19)
21

---

Published in Transactions on Machine Learning Research (04/2024)
B Building Intuition: Analysis of Mean-Path EF-TD
Since the dynamics of EF-TD are quite complex, and have not been studied before, we provide an analysis in this section for the simplest setting in our paper: the noiseless steady-state version of EF-TD where ge (0())) in
line 4 of Algorithm is replaced by g(O.). We refer to this variant as the mean-path version of EF-TD, and
compile its governing equations below:
h4 2s (ct-1 0(0)),
0[+1 = 0, + taus,
(20)
E, = et + g(0,) h4s
where the above equations hold for t= 0, I,.., with 0, E IRK and e-1 = 0. The goal of this section is to provide an analysis of mean-path EF-TD, and, in the process, outline some of the key ideas that will aid us in the more involved settings to follow. We have the following result.
Theorem 4. (Noiseless Setting) There exist universal constants e, C 21 1, such that the ilerates generaled by the mean-patl version of EF-TD with step-size a (1 16--0 (c)) satisfy the following after T iterations:
|00 0 < 2 11- (1 (1-)) 110 1
(21)
C6
Discussion. Theorem reveals linear convergence of the iterates to 0" When 5 = 1, ie., when there is distortion to the TD(0) direction, the linear rate of convergence exactly matches that in Bhandari et al. (2018). Moreover, when 8 >>> 1, the slowdown in the linear rate by factor of 5 is also exactly consistent with analogous results for SGD with (biased) compression (Beznosikov et al., 2020). Thus, our result captures in a transparent way precisely what one could have hoped for.
To proceed with the analysis of mean-path EF-TD, we will make use of the perturbed iterate framework from Mania et al. (2015). In particular, let us define the perturbed iterate 0, a 02 + aee-1- Using equation 20, we then obtain:
u4t 0.+1 + are
0, + ah, + a (ec-1 + g(Oc) he)
(22)
= 0, + ag().).
The final recursion above looks almost like the the standard steady-state TD(O) update direction, other than the fact that g(O.) is evaluated at 0,, and not 0.. To account for this "mismatch" introduced by the memory-variable et-1, we will analyze the following composite Lyapunov function:
v/ 100 112 + a 1|
(23)
Note that the above energy function captures the joint dynamics of the perturbed iterate and the memory variable. Our goal is to prove that this energy function decays exponentially over time. To that end, we start by establishing a bound on |10.+1 - 112 in the following lemma.
Lemma 9. (Bound on Perturbed Iterate) Suppose the step-size a is chosen such that S (1 - 7)/8.
Then, the iterotes generated by the mean-path version of EF-TD satisfy:
a(1 a(l 7) IVb. Vo- 11 + (1 7 llee- 112.
5
110+110011 - 0-10- < 110, - 1-1 00
(24)
4
Proof. Subtracting 0" from each side of equation 22 and then squaring both sides yields:
||0 11 = |10, 0r 12 + 20 (0. 00000000000000 (0e)) + a² (1
10, 102 + (0 - 00, (0.)) a² (0))) + (0, 0,, 0r,)(0,))
(a)
110, - 0-112 - 20, - 0-, .r(())))) +a a
llg(0.) + anilo; - 0,11
(25)
(b)
110, - 11 + 20x 0", ((,,)) +o
a /
1
110(0.)11 + +22
22

---

Published in Transactions on Machine Learning Research (04/2024)
For (a), used the fact that for any two vectors 2, y IR the following holds for all 17 > 0,
1 (a, - 2n
22 2 7 2 11111.
We will pick an appropriate 7, shortly, For (b), we used the fact that from the definition of the perturbed iterate, it holds that O,- 02 = 062-1- We will now make use of Lemma's 4 and 5. We proceed as follows.
10 11 I 110 001 2a(0. - ,((1)) + a aa 1) ") Io(0.)11 + +a alleee-2111
n
(0)
(a+ !) 15(0,)12 + a +a"n|le--11?
110, 0/112 - 20(1 >),, Vo- 1b + a
a
(6)
S 100 0-'o a 22(1 -7) - 4 (a+ [ ) 11 Vo- lb + 1 1|?
(26)
7)
(
4a
4a²
S 10, 1-1 - a(1 - -7) 1 (1 (1-
liVe - Vo- + (1 71 ||e-11 1|
( 110, 1- a(1 7) IV. - Vo- 1b +
4a
(I (1- ||a-1
2
In the above steps, (a) follows from Lemma 4; (b) follows from Lemma 5; (c) follows by setting 1) = 4/(1 - ?);
and (d) is a consequence of the fact that a S (1-7)/8. To complete the proof, we need to relate [V Vo- 11:
to 11Vo Vo- Ilb. We do so by using the fact that for any x, y E R", it holds that + S 2||==|Bb 2 2
This yields:
|| VVV Vo-11
22 Vo- 1b + 2116.. Ve, lb
(4)
- 2/16. V.- 11 + 2110, - 0,11
(27)
s 2/,V. Vog 1b + 10211e;-111?
where for (a), we used Lemma 3. Rearranging and simplifying, we obtain:
-I. - 11-112= S -I. - Ve- 11 + a 2 11
Plugging the above incquality in equation 26 leads to equation 24. This completes the proof.
The last term in equation 24 is one which does not show up in the standard analysis of TD(O), and is unique to our setting. In our next result, we control this extra term (depending on the memory variable) by appealing to the contraction property of the compression operator Qs(-) in equation 4.
Lemma 10. (Bound on Memory Variable) For the mean-pen path version of EF-TD, the following holds:
(1-22 1 + 4a20) ||er-1l2 + 1661IV6, v/- 11.-
|eel11 <
(28)
28
Proof. We begin as follows:
|| = =llez-1 + [(O,) - hell
-Ilee-1 + =(O,)) - 2s (61-1 + ((0))
(0)
1) ) ||e--1 + g(
(29)
(b)
(1 (1-3)
1 (1+ = / 1|2 + (1 (1-3) (1+ m) 10(
5)
23

---

Published in Transactions on Machine Learning Research (04/2024)
for some 1y > 0 to be chosen by shortly. Here, for (a), used the contraction property of Qs(-) in equation 4; for (b), we used the relaxed triangle inequality equation 18. To ensure that ||ex]2 contracts over time, we want
(1-)( < =
-
n> (0 1).
Accordingly, suppose v = 5 - 1. Simple calculations then yield
(1- (1 1 -1- (1-2) (1 + < 26.
Plugging these bounds back in equation 29, we oblain
|eal
| 11 + 20)1)
26
||4-1112 26)l g(o.) + g(0))l2
26
1e- (0,) 5(0.)11 + 4611)(0))11
20
(30)
(a)
1
||t_1 112 + 48100 0.11 4
28
1
+ 40
||ee-111 +8)15((0))1
20
1
+ 4a
||a-1|| 1681|V, 11.112.
28
In the above steps, for (a) we used the Lipschitz property of the steady-state TD(O) update direction, namely Lemma 7; and for (b), we used Lemma 5. This concludes the proof.
Lemmas 9 and 10 reveal that the crror-dynamics of the perturbed iterate and the memory variable are coupled with each other. As such, they cannot be studied in isolation. This precisely motivates the choice of the Lyapunov function ey in equation 23. We are now ready to complete the proof of Theorem 4.
Proof. (Proof of Theorem 4) Using the bounds from Lemmas 9 and 10, and recalling the definition of the Lyapunov function v, from equation 23, we have
Vi+1 < 110, 0-1 a(l-2
1 (1-
64ad
(1-
5a
4
-7)
1V
Vo- +0²
25
+
-4225+ +
(1 (-
||e-
1122
awl(1 - 7) (1
64ad
5a
(31)
||0:
1- +
a²
1
+ 4a
+
||e--1
7)
25
(1 7)
where we used Lemma 3 in the last step. Our goal is to establish an incquality of the form th41 S vale for some < 1. To that end, the next step the proof to pick the step-size a in way such that max max Accordingly, with (1 - (1221))) we have that
A 11-11111 10248
(1- and A₂ < (1 (1-1)
45
Furthermore, is easy to check that A2 S Ar- Combining these observations with equation 31, we obtain:
(1 (1-7)
(110: 0011² + a 211e--111²)
10248
24

---

Published in Transactions on Machine Learning Research (04/2024)
Unrolling the above recursion yields:
1 (1 - 7)
BT
1/0
10246
(32)
(1 ?)
110g 11
10240
where for the last step, we used the fact that e-1 To conclude the proof, it suffices to notice that:
100 - 1-112= = 110 - 0r + 0r - 1²
I 21(Ø - 11 + 2 0rl
(33)
=210r - 0' 2 + 20 1err-11
2//T.
B.1 Can Compressed TD Methods Without
Still Converge?
Earlier in this section, we provided intuition as to why EF-TD converges by studying its dynamics in the steady-state. One might ask: Can compressed TD algorithms without error-feedback still converge? so, under what conditions? We turn answering these questions in this subsection. In what follows, we will show that compressed TD without error-feedback can still converge, provided certain restrictive conditions the compression parameter 5 are met. Notably, these conditions error-feedback. To convey the key ideas, consider mean-path version of compressed TD shown below:
longer nceded when employs
0.+1 = 02 + @g(((())
(34)
where Qs(+) is the compression operator in equation 4. From the above display, immediately have
||0++1 - 12 = 110: - 1 (0, 0", , (F(((()))) + a² (22(0())
(35)
Among the three terms on the R.H.S. of the above equation, notice that the only term that can lead to decrease in the iterate error ||0++1 0* l is clearly 2a 0", (s As such, let us fix f E RRKKK and investigate what we can say about (0- p", Qa(ā()))) First, notice that if there is no compression, i.c., 8 = 1, then (x)) g(0), and we know from Lemmas 3 and 4 that
00 00)) S 3110 0-112
(36)
where B = w01 - 7) E (0, 1). It is precisely the above key property that causes uncompressed TD to converge to 8r Now let us observe:
2,(0(())))
(0 0r, ()) (0 0r, 2r(((0) g(0))
A8 3 (0 0", (0)) ||0 00 (a()(()) [(0)II
(0 8- ((0) +
10 (1)
(37)
(8)
(1111) ||0 - 11?
K (0 0-, ((0 +
(c)
2 - 3 v (1 (1-
110 0'112.
25

---

Published in Transactions on Machine Learning Research (04/2024)
In the above steps, (a) follows from equation 4, (b) follows from equation 16, and (c) from equation 36. Comparing equation 37 to equation 36, we conclude that for the distorted TD direction Qa ()() to ensure progress towards 0*, we need the following condition to hold:
((1 (1- (1-5)4
1 8
<B
(38)
Simplifying, the above condition amounts to
8 < 1 82)
(39)
The parameter E (0, 1) gets fixed when fixes an MDP, the policy to be evaluated, and the feature vectors for linear function approximation. The condition for contraction/coovergeeee in equation 39 tells that this parameter 3 limits the extent of compression 8. Said differently, one cannot choose the compression level 6 to be arbitrarily large; rather it dictated by the problem-dependent parameter B. It is important to note here that no such restriction on is necessary when one uses srror-feedbuck, as revealed by our analysis for mean-path EF-TD. This highlights the benefit of using error-feedback in the contect of compressed TD learning. With these observations in place, let return our analysis of the update rule in equation 34. For case of notation, let us define
(1-1) .
< _
B 88-
and note that if the compression parameter & satisfies the condition in equation 39, then Ç > 0. Plugging the bound from equation 37 in equation 35, we obtain
|10+11 - = 110,
< (1 - 2ac) 110 0r -
< (1 2aς) 110, 1- 20²10.(7(0.)) -000))1 2a 2070)1
(40)
(4)
S (1 20ς) 110, - 1- +2 o² (0))12
( (1 2nC + 4a²) 10, 1'11
where (a) follows from equation 4 and (b) from equation 16. Thus, with S C/4, we have
|0 1 < (1 ac) -
We conclude that when the compression parameter ô salisfies the condition in equation 39, and the step-size is chosen to be suitably small, the compressed TD update rule in equation 34 does converge linearly to 0",
26

---

Published in Transactions on Machine Learning Research (04/2024)
C Warm-Up Up: Analysis of EF-TD with a Projection Step
Before attempting to prove Thcorem 1, it is instructive to analyze the behavior of EF-TD with a projection step. The benefit of this projection step is that it makes it relatively easier to argue that the iterates generated by EF-ID remain uniformly bounded; nonetheless, as we shall soon see, the analysis remains quite non- con-trivial even light of this simplification. Let us now jot down the governing equations the dynamics we plan
study.
h 2s (et-1 + g:(())))
oc11 122,5 (0, + ah4)
(41)
6 = ct-1 1 (e.)) - h4
where (12, denotes the standard Euclidean projection on to a convex compact subset B C R that is assumed to contain the fixed point d". We also note here that a projection stop of the form in equation 41 is common in the literalure on stochastic approximation (Borkar, 2009) and RL (Bhandari et al., 2018; Doan et al., 2019).
Our main result concerning the performance of the projected version of EF-ID is the following.
Theorem 5. Suppose Assumption 1 holds. There exists a universal constant c 2 1 such that the iterates generaled by the projected version of EF-TD (i.e., equation 41) with slep-size a S (1 -7)/c satisfy the following after 2 iterations:
a7
E [110 11] S (1- -))) +0
(42)
w(1 - 7)
where Ci = 0la"6" + G and G is the radius of the convex compact set B.
Main Takeaway. We note that the nature of the above guarantee is similar to that of Theorem 1. That said, while the noise term in Theorem 1 is O(T + 6), it is O(78²) in Theorem 5. In words, with the somewhat cruder bounds we obtain via projection, we end up with a looser dependency on the distortion parameter 5. Moreover, the mixing time t and the distortion parameter show up multiplicative form Theorem Section D, we will provide finer analysis (without the need for projection) that yields the tighter O(r + 8) bound.
We now proceed with the proof of Theorem 5. Let us start by defining the projection error Ep,t at time-step & as follows: 6p.1 0r (ft-1 + aa)-1). We also define intermediate sequence {6.} follows: & 0 ah1-1 Thus, O₂ 0, Cp.t. Next, inspired by the perturbed iterate framework in Mania et al. (2015), we define a modified perturbed ilerale follows:
8, 2 02 + ae
(43)
Based on the above definitions, observe that
0,+1 0.+1 + aēt
02 + alu + a
+ + - lw)
= 0g + age( + aP:-1
(44)
02 ae + agi (0t) + Ep,t
0. age(O,) Ep.t
Subtracting 8* from cach side of equation 44 and then squaring both sides, we obtain:
||0+01 - 2 |10, - 11 + 20 0" g. + a (19:(0,)11 + 2(0. 0" + age()r)) ep.t) + |lemeel?.
(45)
Ci
Ca
In what follows, we outline the key steps of our proof that involve bounding each of the terms Ci C4.
Step The dynamics of the model parameter 9,, the Markov variable Xx, the memory variable e,, and the projection error b,t are all closely coupled, leading to dynamical system far more complex than the
27

---

Published in Transactions on Machine Learning Research (04/2024)
standard TD(O) system. To start unravelling this complex dynamical system, our key strategy is to disentangle the memory variable and the projection ervor from the perturbed ilerate and the Markow dola tuple. To do so, we derive uniform bounds on et, hi, and Ep.t by exploiting the contraction property in equation 4. This is achieved in Lemma 12.
Step 2. Using the uniform bounds from the previous step in tandem with properties of the Euclidean projection operator, we control terms C2 C4 in Lemma 13.
Step 3. Bounding C1 takes the most work. For this step, we exploit the idea of conditioning the system state sufficiently into the past, and using the geometric mixing property of the Markov chain. As we shall see, conditioning into the past creates the need to control 1|0, - -1--l1,, Vi 2 T, where T is the mixing time. This is done in Lemma 14. Using the result from Lemma 14, we bound C₁ in Lemma 15.
At the end of the three steps above, what we wish to establish is a recursion of the following form Vt 2 r
E [10 - 0-1 s (1 aw - 7)) 0, 0-1131 C0
To proceed with Step 1, recall the following result from Nedic et al. (2010).
Lemma 11. Let B be nonempty, closed, conver set in RR Then, for any E RKK we have:
(a) (T2.(1)) x v) -
=112 1 E B. (b) [[B[(*) - ylI & || - w|l² ([)==)) v B.
To lighten notation, let us assume without loss of generality that all rewards are uniformly bounded by 1. Our results can be trivially extended to the case where the uniform bound is some finite number Rmaa- To make the calculations cleaner, we also assume that the projection radius G is greater than We have the following key result that provides uniform bounds on the memory variable and the projection error.
Lemma 12. (Uniform bounds on memory variable and projection error) For the dynamics in equa- tion 41, the following hold vt 2 0:
(a) ||e/|| S 68G.
(b) ||bal| S 158G.
(c) ||em,e|| S 15a8G.
Proof. We start by noting that for all 2 0,
- l (0.)l = - <
|| |
+ (6X)) < 2G +1 3G,
(46)
where we used (i) the feature normalization property: (ii) the fact that the rewards are uniformly bounded by 1; and (iii) the fact that due to projection, ||0:1| < 1, 2 O. Next, observe that
| 2 ||e--1 + (Oc) hell
= ||e + (0.) - 2s (Et-1 + (0.)) 1|2
(0)
1
1 g
||e--1 + (0.)))
(47)
(b) (1 (1-3)
1) (1 (1+ ||2 (11+++111) (1+ (0.)1
(1-2)
8)
for some 77 > 0 to be chosen by shortly. Here, for (a), used the contraction property of Qs(-) in equation 4; for (b), we used the relaxed triangle inequality in equation 18. To ensure that |/e/]/ contracts over time, we want
1 (1 11 (1+ <1 = n> (6 1).
28

---

Published in Transactions on Machine Learning Research (04/2024)
Accordingly, suppose 7 = 1. Simple calculations then yield
(1- 1 +
- - );
(1-3) (1 +)) 26.
Plugging these bounds back in equation 47 and using equation 46, we obtain
||ea|12 < (
|e:- 11: (0)1
28
||e-1112 +1/2+1884 185G..
28
Unrolling the dynamics of the memory variable thus yiclds:
++1
k
(1-
1eell <
||e_1|2 + 185G
1
28
28 k=
1
(48)
< 188G
1
28
k=0
365 G2,
where we used the fact that 6-1 = Thus, ||+ s 68G, which establishes part (a). For part (b), we notice that h4 Ct-1 - (e.).. This immediately yiclds:
hhell $ ||e/ll ||e__1ll (0))l < 128G + 3G S 158G,
where we used the fact that 1, the bound from part (a), and the uniform bound on ge(O)) established carlier.
Next, for part (c), part (b) of Lemma 11 to observe that
||ep 11 ||22,s 0.11 s ||0, 0|I 4a e
Since the above bound holds for all E B3 and 0.-1 E B, we have
11ep,111 S 110 - 02-1ll 1I2 = a 2
where we used the fact that 0, = 0:-1 + ah:-1 by definition, and also the bound on [/e]] from part (b). This concludes the proof.
From the proof of the above lemma, bounds on terms C2 and C4 in equation 45 follow immediately. In our next result, bound the term Cs.
Lemma 13. For the dynamies in equation 41, the following holds for all 0:
2(0, - 0" + (O,) ep,) S 250282""
Proof. We start by decomposing the term we wish to bound into three parts:
2/0, 8* (ag) cp.)) 2(0, 8* ac agi (0c),
2(0 0" ep.))
e,
20 (0.), ep.e)
(49)
Ca1
Cap
Cas
We now bound each of the three terms above separately. For Cai, we have
2(0 0" (ee)) 240 0", 0",0, 0.) 2 0.11 = -21lep 12.
(50)
29

---

Published in Transactions on Machine Learning Research (04/2024)
where used part (a) of the projection lemma, namely Lemma 11, with 0g and y 0"; here, note that we used the fact that 0* E B. Next, for C32, observe that
(p)) S a 1
+ lle,,1l
(51)
- 36a 2 + ||ep,ell
where we used the bound on ||e--ll| from part (a) of Lemma 12. Notice that have kept ||ep,ell as is in the above bound since will cancel off its effect with one of the negative terms from the upper bound on Ca1- Finally, we bound the term C33 as follows:
2a(g (pa)) I a² (9:(1)))1 + 1
(52)
I Ga + 1l
where used the uniform bound (0t) from equation 46. Combining the bounds in equations 50, 51, and 52, and using the fact that 8 yields the desired result.
Notice that up until now, have not made any use of the geometric mixing property of the underlying Markov chain. We will call upon this property while bounding C₁. But first, we need the following intermediate result.
Lemma 14. For the dynamics in equation 41, the following holds for all t 2 T:
10 0-- 11 60a7ōG.
(53)
Proof. Based on equation 44, observe that
||0 0.11 S (l:))(0))1l1 + lle I 3aG + 15a6G
(54)
18a0G.
We also note that
0 ,,,
Σ
(bu+1 - -kx)
A=t-r
Based on equation 54, we then immediately have
1-1
- 0,-111
Σ
10x41 0all
-
Amt-7
t-1
(55)
(18o8G)
kmt-7
< 18aTGG.
Our goal is to now relate the above bound on |10 f ll to one on ||0, 02-rll. To that end, observe that
0, + CEE - ep,t.
8,, 0.- + acc Ep.
This gives exactly what we need:
|10 - 0c-r/1 < ||0 8 + alle--1 - + plep.e---------- ep.ell
< 00, 0 |l + alle--111 + ael e--r- + /lepp-rll + ||e
(56)
< 18 + 12.5G 30a0G < 60aT8G,
where we used equation 55, parts (a) and (c) of Lemma 12, and assumed that the mixing time to state the bounds more cleanly. This completes the proof.
30

---

Published in Transactions on Machine Learning Research (04/2024)
We now turn towards establishing upper bound on the term C₁ in equation 45.
Lemma 15. Suppose Assumplion 1 holds. For the dynamics in equation 41, the sollowing then holds Vl
E [2a(0. .x))) s --2a(1 ~) [IVVo Vo- [o-11b] 1454a28r &
Proof. Let us first focus on bounding T - (0r - 0" (0()) - g(0,)). Trivially, observe that
T = (0. Dt (0.) - g(0.)) + (0.-- - 0 ge,(0) g(0.)) 01
T2
To bound Ti, we recall from Lemma 7 that for all 02, 02 RK it holds that
(l((1)) (11) - 101 - -22l-
Since g(0") O, the above inequality immediately implies that ||9(0)]| = ||0|| + ||0 V0 E RK In particular, for any B, we then have that |lo(0)]| & 2G (since 0* B). Using the bound on || - - from Lemma 14, and the uniform bound on the noisy TD(O) update direction from equation 46, we then obtain
n $ (I10: - (I) (1l)( g(0+)l)
< (I10, 0.- II) (11g (l)(0)))))
(57)
s 60ar6G (3G + 2G) 300ar8G².
To bound T2, further split into two parts as follows:
T3 (0-r 0", ge (0,-)) g(0c-r))
(0-r- 0" g0()) go (0(rr) + g(0,_r) g(0,))
T21
T22
To bound T22, we will exploit the Lipschitz property of the TD(O) update directions in tandem with Lemma 14. Specifically, observe that:
Tea S |00- (Ilg ((: 1g(0)-+) ((e))l)
2 2G (0:) ge (0 ( [0(00-r)- - g(0,))))
(58)
6G 0z-
360aT6G2.
In the above steps, (a) follows from projection; (b) follows from Lemmas 7 and 8; and (c) follows from Lemma 14. remains to bound T21. This is precisely the only place in the entire proof that we will use the geometric mixing property of the Markov chain Definition 1. We proceed as follows.
E [T2]] E [0,-r 0" (0..) ((({-)))]
E [ 0º gi g(0,-r)) (10 Xe-r]
E [(0,- - 8", B.,EEe (G, - g(O,-, )) 10 X,-r
< E [||0r_r 0" [1| (g (0r-r) g(0, .) 10 X
(59)
(0)
2aG (E [||0,- -000---0'11))
$ 4a02
where (a) follows from the definition of the mixing time 7. Combining the above bound with those equations 57 and 58, we obtain
E [T] < 664aT602
(60)
31

---

Published in Transactions on Machine Learning Research (04/2024)
where used 5 2 1 and 8 2 1.
We can now go back to bounding C as follows:
C1 2a:0; 0t + act-1 cp. 9p.1.9((1))
2a (0: 8" gi (0,)) 2a (c-- 9 (0:) (0(e gc(()))
(61)
I 20 - 0" 9r (0t)) + 2a ||: (e))) + 20/llep.llllgr((0
I 2a 0-, 9t (0:)) + 126a 2G"
where we used equation 46, and parts (a) and (c) of Lemma 12. We continue as follows:
C1 < (0. 0% -(())) + 2nT + +126a2
Using Lemma 4 and the bound derived T in equation 60, finally obtain
[C]] S -2a(1 - 7) [IVo. Vo. [1]] 1454a28rG²
where in the last step, we used Lemma 4.
We can now complete the proof of Theorem 5.
Proof. (Proof of Theorem 5) We combine the bounds derived previously on the terms CJ-C₁ Lemmas 12, 13, and 15 to obtain that At 2 T,
E [[]0e+] 0-] E [10. - 11 20(11 - 7) [I6o, - Po- Vo-117] + 1454a"87
+ 0² + 450 G² + 225a 62
(62)
R [10,, 11 20(11 7B
|
Vo- Vo-113] + 173
To proceed, need to relate 11V Vo-11 11 to 1V - -V- We do so by using the fact that for any v. IR".
it holds that || + vllB 2||x IB 211y/1B. This yiclds:
|| IV, Vo- ll
< 2/
Vo. Il + 2118, Vo, lb
(63)
(a)
$ 2/1Ve.
Vo- 11 + 2110: - 0, 0,112
where for (a), we used Lemma 3. We thus have
-2a - V). - 1o-13 z -a a(1 7) V. Ve- 11: + 2n(1 - -) - -
s a(1 7) V..
Vo- 11 + 2a(1 7))l - ep,el?
(64)
< a(1 V) Vo- 11 + 4a(1 7) (a²1le--111 + +1lpp/llllll1 1llepell))
S a1 - 1)1 Vo- 11 + 1044a (1-
where we used Lemma 12. Plugging the above bound back in equation 62 yields:
E [1
13 < E 110 13 a(1 B [
V/ 11:11 287772827CC
(65)
< (1 aw 7)) [|00 [ + 2777 Vt 2 T,
where we used Lemma in the last step. Unrolling the above recursion starting from = T, we obtain
E [10Ø - [*]]]] S (1 aw(1 - -)) - TE [liē, 0 1 + 2777 28
Σ (1 - aw(1 - 7))*
k=0
(66)
aT&
- (1 -aw(1 -)) - EE [100, 0 1-
+ 2777
w11 77)
32

---

Published in Transactions on Machine Learning Research (04/2024)
We now make use of the following equation twice.
0. 02 + act1 Cp,t*
First, setting & = in the above equation, subtracting 0* from both sides, and then simplifying, we observe
that
10, 0*1 S 1|0+ 0* + aalee- 1ll + 1ep ll = O OadG + G),
where we invoked Lemma 12. Thus,
E |10, - 0r 13 - -0(00
Using similar arguments as above, one can also show that
| 0-112 < 3|,r 1- 30 1 + 31l S 3| 0-11- 0'112+0(02880
Plugging the two bounds we derived above in equation 66 completes the proof.
33

---

Published in Transactions on Machine Learning Research (04/2024)
D Analysis of EF-TD without Projection: Proof of Theorem 1 and Theorem 2
In this section, we will prove Theorem 1. In particular, via finer analysis relative to that in Appendix C, we will (i) show that the iterates gencrated by EF-ID remain bounded without the need for an explicit projection step to make this happen; and (ii) obtain lighter bound w.r.t. the distortion parameter 6. At this stage, we remind the reader about the dynamics we are interested in analyzing:
h 2s (e + (c())))
oc+1 0, + alis,
(67)
Et 6 + ge(0,) - h4-
To proceed with the analysis of the above dynamics, let us define the perturbed iterate 0g 2 0, + aee-1- Using equation 67, we then obtain:
0.+1 = 02+1 + aeet
0g + alı + +
+ (0,)) - h()
(68)
= 0 + ag:(Ot).
The final recursion above looks almost like the TD(O) update, other than the fact that gi (0x) is evaluated at le, and not 6. To account for this "mismatch' introduced by the nemory-variable et-1, we will analyze the following composite Lyapunov function:
Bid + (le--111)) where di 110, 1-
(69)
Note that the above energy function captures the joint dynamics of the perturbed iterate and the memory variable. Our goal is to prove that this energy function decays exponentially over time (up to noise terms). To that end, we start by establishing bound on di,, in the following lemma.
Lemma 16. (Bound on Perturbed Iterate) Suppose the step-size a satisfies a S 1/12. For the EF-TD
algorithm, the following bound then holds for 2 0.
6a ((1-7)) 11--1112 2a - 0" g),) - g(o.)) + =2a2002
E. (1-1w - +) 2402) de
(70)
Proof. Subtracting 0* from each side of equation 68 and then squaring both sides yields:
d+ d. + 20 8" (0.)) + a (e))
= d + (0, 8" (..)) + 2a - 8 g.().) (r,)) + +a (1))
(71)
(+)
(++)
(.0+)
We now have:
(*) = 20 0r, ,0(0())))) + 20 0-, (0.)) g(o.)) -2w(1 - 7] + 20, 0-, (0.) g(O,)),
(72)
where in the second step, we invoked Lemmas and 4. To bound (**), we proceed as follows:
(x*) < 4ad 0 02ll
(b) 2a d + 22n11 0.11
(73)
(c) x + 20 3 n n11
Thhe requirement. that S 1/12 necessary obtain the type of bound equation 70. Instead, it only serves simplify some of the leading constants the bound.
34

---

Published in Transactions on Machine Learning Research (04/2024)
where 7, > 0 is constant to be decided shortly. In the above steps, (a) follows from the Cauchy-Schwarz inequality and the Lipschitz property of the TD(O) update direction in Lemma 8. For (b), we used the fact. that for any two scalars E R, the following holds for all > 0,
1 2
xy 2n
Finally, for (c), we simply used the fact that 0, - f/ = 0-1-1- To bound (* * *), observe that
(0,)(
4(110:1l +0)²
8(10,,12 +
(74)
8 (3110, - 0.11 + +310, -0-10- +1
24a2||er-11/ 11? + 24d + +20
where (a) follows from Lemma 6, (b) follows from equation 19, and (c) follows from noting that ||0*|| S
Plugging the bounds in equations 72, 73, and 74 in equation 71, obtain:
2 S (1 - 2aw(11 7) 7
2a 24a² d3 + 2a + 12a 1e 11 + 2a 0", (.))) g(
(75)
02
The result follows from setting " w(1-7}) and simplifying using a S 1/12.
Unlike the standard TD(O) analysis, note from Lemma 16 that the distance to optimality of the iterates is intimately coupled with the magnitude of the memory variable es. As such, to proceed, we need to bound the growth of this memory variable. We do so in the following lemma.
Lemma 17. (Bound Memory Variable) For the EF-TD algorithm, the following bound holds for Vt 2 0:
||e/||2 < 1
25 + 16a2d) |1e 645d; + 96802
(76)
Proof. We begin follows:
| 2 ||e-- (0.) hell
||e-- (0:) 2s (ft-1 ge (0.)) 11
(a)
1 8 || + (e(())
(77)
(b) 1 1 1 (1+ ||et-1112 (1- (1 (1+m)
(0.)1
8
where (a) follows from the contraction property of Qs(-) in equation 4, (b) makes use of the relaxed triangle inequality in equation 18, and 7) 0 is constant to be chosen by shortly. To ensure that ||ea]] contracts
35

---

Published in Transactions on Machine Learning Research (04/2024)
over time, set 17 8 - 1 to obtain:
1
|e
||a_1]| + (0:))(())))
26
1
||q_1|1 + 25 (0,) - gr(0,) + ge (r()))l
26
1
W
||a-1 2| + 46 (0r) - g. (.() + 4011
28
WV
1
1
||e:11 12 + 160 0.11 + (01))((0))1
(78)
28
1
+
16a
8
||e:-1| + (0))l
28
(6)
1
16a 6
||e:11 1 + 325 (10&,1 + o²)
28
1
<
+ 16a28
||0--||2 328 (2d + 30²)
26
In the above steps, for (a) used the Lipschitz property of the noisy TD(O) update direction, and for (b), we appealed to Lemma 6, This completes the proof.
]
D.1 Bounding the Drift and Bias Terms
Inspecting Lemma 16, it is apparent that we need to bound the "bias" term (6. - -000)((0))) T(O.)). This requires some work for the following reasons.
In the (compressed) optimization setting, one does not encounter this term since g (0.) is an unbiased version of g(O.). Thus, taking expectations causes this term to vanish.
In the standard analysis of TD(O), while one does encounter such a bins term (under Markovian sampling), such a term features the true iterate Or, and not its perturbed version 0.. This where we again need carefully account for the error between 0, and 0,.
In Appendix C, we derived a bound on the bias term by leveraging the uniform bounds on the memory variable in Lemma. 12. Such uniform bounds were made possible via the projection step. Since no longer have such projection step at our disposal, we need an alternate proof technique.
In order to bound (0, 0-, () (00)), we will require mixing time argument where condition sufficiently into the past. This, in turn, will create the need to bound the drift ||6, - 6 of the perturbed iterate 0;; here, recall that T is the mixing time. In the analysis of vanilla TD(O), the authors in Srikant. & Ying (2019) show how such a drift term can be related to the distance to optimality of the (true) iterate at time t. The presence of the memory variable e, (that accounts for past errors) makes hard to establish such a result for our setting. As such, we will now establish different bound on the drift ||A 6,-rl as a function of the maximum amplitude of our constructed Lyapunov function (in equation 69) over the interval It - t.. In this context, we have the following key result (Lemma in the main body of the paper).
Lemma 18. (Relating Drift to Past Shocks) For EF-TD, the following is true Vt 2
Bl|lg - 01--112] 2
max the + 480227727 --sist-1
(79)
36

---

Published in Transactions on Machine Learning Research (04/2024)
Proof. Starting from equation 68, observe that
|10+11
0.ll (0:)l
$ (1gg (0:) 9r (6:) || + 11 (0:)1)
(0)
- 2a (110- dell + |0:11 + o)
(80)
2a (a (01le=111 || o)
S 2a let-1 + de + 20).
where (a) follows from Lemmas 6 and 8. We thus have
E
[10 A. [2]] - 12a [a 1e 12 di + 40
(81)
12a 48a20²
where for the first step, used equation 19, and for the second, the definition of th in equation 69, Appealing to equation 19 again, observe that
E [10 - 01--117
ST
Σ E
[100+1 - 0ell
t=tー
equation 81
1-1
(82)
S
12a2
Σ
(vhe + 440)
6-1-
< 12a
the + 4802
max t-r
which is the desired claim.
Interpreting the as a "shock" from time-step E, Lemmna 18 tells us that the drift the perturbed iterate over the interval [t - r, can bounded above by the maximum shock over this interval (up to noise terms). Fortunately, the effect of this shock is dampened by the presence of the O(a²) term multiplying it. Equipped with Lemma. 18, now proceed to bound the bias term
Lemma 19. (Bounding the Bias) Suppose Assumption holds. Let the step-size a be such that or S 11/6. For EF-TD, the following is then true Vt 2 T:
E (0. 0" (0.) g(0,)) < 3laTE [ + 103ar + 4540702
(83)
where
V₁
1-rSEs--1 tie.
max
Proof. We start by decomposing the bias term T = ( - 0", (0,) - -((+)) as follows:
T (0. - 106-0.1.000 0.... - g(o,)) + (0.- - 0" g0)) - g(0))
T1
12
To bound Ti, note that
Ti < 01, 0,-
allllg (0,) g(,))ll
1
0
11 + aT
2 (9)(()) g(0))1l
20T
1
00
0.- -12 ar (0.))1 (1)())))1)))
2ar
(84)
1
00,
0, 112 10a (0(aT([[@,)))) 01 + +²)
2nr
<
10 θ,- 2| + 10ar (2d2 + 30
2αt
37

---

Published in Transactions on Machine Learning Research (04/2024)
where for (a), used Lemma 6 and equation 16. Taking expectations on both sides of the above inequality, and using Lemma 18, we obtain:
[Ti) S 20 [d]] + 6ar V22 + 54aTO?
(85)
Next, to bound T2, we decompose it as follows:
T2 (0-- 0¹, ge (0(0,-)) 7(0r-))) + (0rr - 0' (0((0))) ge (0)+ (0,- 0¹, (rgg(0r)) -7(0))
(+)
(.0)
(10.)
We now proceed to bound each of the three terms above. Observe:
(**) S d. (19:(0)) ge (0(00_))l
(a)
- - -0,-71
s 2(h + 110 - -0g-r11)104 - rr-
(86)
(9)
Vard. + 11 - 02- 2
2
VaT 110 0
<4 atd
at
where for (a), we used the Lipschitz property in Lemin 8, and for (b), we used the fact that or S 1. Taking expectations on each side of the above inequality and appealing to Lemma 18, we obtain
E [**))] < 4 [dt] + 48 + 192aTo²
(87)
Using Lemma 7 and the same arguments as above, one can establish the exact same bound on EE [( * +)] as in equation 87, Before proceeding to bound (*), we make the observation that 0, inherits its randomness from all the Markov data tuples up to time 1, i.c., from {X*] We now have:
E [(+] E [(0 0*, ,0,,00000 g (0._r) g(0,,-))]]
E [E [(,,, - 0", "r,(((,,)) - () X
E (0.-, - 00,E [g((00)_)) g(0 110-1;
E [d [9:(0)_ -) 0(0.,))10 - X, II]
(
< oE 1 (10) || + 1)]
aE [1 (100, 0. + de + ||0*|1 || + 1)]
(88)
aE [(d. + 100 0.-+1)) (1 0.1l d. |10^1 1)]
aE [(d: + -100 - 0 II) (10,_, 0.ll + de + 20)]
aTE [[de + 00, 0,-rl || + 20)
IN 3arE [d]] 3arE |10 1.-11 + 12aTO²
30rE [d]]
V, + 16a7o
In the above steps, (a) follows from the mixing property in Definition 1, (b) follows from the fact that 7 2 1, and (c) follows by invoking Lemma. 18 and simplifying using < 1/6. Combining the above bound with that in equation 87, we conclude that
E[T2] S 11 [d)] + 97ar V2 + 400aTo².
Combining the above bound with that in equation 85 completes the proof.
38

---

Published in Transactions on Machine Learning Research (04/2024)
We now have all the pieces needed to prove Theorem 1.
Proof. (Proof of Theorem 1) We break up the proof into two parts. In the first step, establish recursion for our potential function th. In the second step, we analyze this recursion by making connection to the analysis of the Incremental Aggregated Gradient (IAG) algorithm in Gurbuzbalaban et al. (2017).
Step 1: Establishing a Recursion for Vh. Combining the bound on the bias term in Lemma 19 with Lemma 16, and simplifying using 1, we oblain the following inequality 2 T:
6a
E d S (1- aw 7) 86a E8 [
206a
w01 7) [[le-1 11 940a27903
Combining the above display with the bound on the memory variable in Lemma 17, and using the definition of the potential function tht, we then obtain 1I 2 T:
v4+1 S (1 (1- aw(( - -7)+ 86a 7 + 64a
d + 2206a2
A1
1
6a
(89)
+ a² 1
16a
28
E [[le,-111 + 0
28
w(1 - 7)
A
Our immediate goal is to pick a such that max ( (A1, A2) < 1. Accordingly, it is easy to check that if
w1
w(1 w11-7)
344r and <
(90)
2560
then
aw
7)
A S
2 It is also easily verified that with the choice of step-size in equation 90, the following hold:
1
16a
and
5
88
w(1 - 7)
88"
implying that
1
A2 51
45
Finally, note that based on the choice a in equation 90, we have
48 < aww( - 7)
Combining all the above obscrvations, we obtain that for all t 2
v/e+1 Σ (1 (ww(1 - 7) the + 206a
max the (-rsist
+ +0(22(++000))
(91)
2
If the second term (i.e., the "max' term) in the above bound were absent, one could easily unroll the resulting recursion and argue linear convergence to noise ball. In what follows, we will show that one can still establish such linear convergence guarantees for equation 91.
Step 2: Analyzing equation 91 via connection to the IAG algorithm. To see how analyze equation 91, we take a quick detour and recap the basic idea behind the IAG method for finite-sum optimization. Say we want to minimize
f(x) M Σ M(x), (E[M]
39

---

Published in Transactions on Machine Learning Research (04/2024)
where each component function is smooth. The IAG method does in computationaall--ffiiiin manner by processing each of the component functions one at time in a delerministic order, and crucially, by maintaining a memory of the most recent gradient values of each of the component functions. This memory introduces certain delaged gradient terms in the update rulc. In Gurbuzbalaban et al. (2017), it was shown that the presence of these delayed terms leads to a recursion of the form in equation 91. This turns out to be the key observation needed to complete our analysis. In particular, we recall an important lemma from Feyzmahdavian al. (2014) (used in Gurbuzbalaban
al. (2017)) that will help us reason about equation 91.
Lemma 20. Let {Gt} be sequence of non-negative real numbers satisfying
GL+1 SpGr + (t-T)) SeSt
max Getr, LEN,
for some non-negalive constants p. 9, and r. Here, for any real scalur x, use the nolation (x:)+ .max max(2;00 0}. p 1 and 0 S S Tmazi Vt 2 0 for some positive constant Tmaxs then
G. S p² Go 1120,
where
p = (p 4 s4tmar and
(1 -
Comparing equation 91 to Lemma 20, we note that for us:
= awl( 7)
2 . = 206a"
and = T,
where t is the mixing time. Now suppose is chosen such that
w(1 ((1-7)
(92)
8247
Then, we immediately obtain that
p p+q=1- aw(1 71
aw -)
+ 206a 2 <
2
4
Sctting Ci = maxosker the and appealing to Lemma 20 then yiclds the following VT 2 7:
t S Ci (1 (1- aw(1- 7)
T-r
+0 ( ( d0)²²
88
w(1 - 7)
where we used the facts that (1 - 2²"= < 1 ax for x, a E [0, 1], and t 2 1, to simplify the final expression. Next, note that
E | [1] E
|0r 0r + 0r 0-11"
S 2E
||0 0- [|]]
2E |10 0r 1*)
(93)
2E
[d]]
+ 2
||eT- 113]
24/T.
We conclude that VT 2 T
(1- aww(1 (1-ow(l-2)) Thr
a(( 5)0² w(1 - 7)
E 2
S 20
+0
87
Furthermore, from the requirements on the step-size a in equations 90 and 92, we note that for the above inequality to hold, it suffices for a satisfy:
w(1 - 7)
a < 824 max (T, (T,8)
40

---

Published in Transactions on Machine Learning Research (04/2024)
The only thing that remains to be shown is that C1 maxosks- t/ = O + + based on our choice of step-size above. This follows from straightforward calculations that we provide below for completeness.
From equation 68, we have
L+ = de +a(20(, - 00 (0,)) + (1)))1)))))11
$1 a.d + 9:
(94)
s 49c)) + 480 64a0²
where in the last step, we used equation 74. Combining the above bound with Lemma 17, we obtain the following inequality for all 2 0:
e4 S (1 49a + 64a 64 [b) + a 11
1 + 16a28 + 48a
[Iee + (64a + 96a 20)0
(95)
20
Using the fact that ad & 1/824, we can simplify the above display to obtain
Di+1 & (1 + 50a) + 65a0 vt 2
(96)
Unrolling the above inequality and using c- = 0, we have that for 0 < k T::
k-1
1/ - (1 50 + 650m 2
Σ (1 + 50x)
(97)
Now since (1+ S , Vx E IR, and a - 1/(200T), note that (1+ 50a)* - (1+ + 50a)) S 0.25 < 2. Thus, for o k S T, we have
2 S 2dh + 130aTo2 S 2d + o²
where in the last step, used 130ar 1. Thus, Ci maxogker the O(f + o²). This concludes the proof.
We conclude this section with note the proof of Theorem 2.
Proof of Theorem 2: A careful inspection of the proof of Theorem reveals that we never explicitly used the fact that the TD update direction is an affine function of the parameter 0. This was done on purpose to provide a unified analysis framework to not only reason about linear stochastic approximation schemes with ferorrkee,back, but also their nonlinear counterparts. As such, under Assumptions 2 and 3, the analysis for the nonlinear sctting in Scction follows ezactly the same steps as the proof of Thcorem 1. All one needs do is replace w(1 -7) in the proof of Theorem 1 with B, where B is as in Assumption 3. Everything else essentially remains the same. We thus omit routine details here.
41

---

Published in Transactions on Machine Learning Research (04/2024)
E
Analysis of Multi-Agent EF-TD: Proof of Theorem 3
In this section, we will analyze the multi-agent version of EF-TD outlined in Algorithm 2. The main technical challenge relative to the single-agent analysis conducted in Appendices C and D is in establishing the linear speedup property w.r.t, the number of agents M under the Markovian sampling assumption. As we mentioned earlier in the paper, this turns out to be highly non-trivial even in the absence of compression and error-feedback. The only work that establishes such speedup (under Markovian sampling) is Khodadadian et al. (2022), where the authors use the framework of Generalized Moreau Envelopes to perform their analysis. Although the analysis in Khodadadian et al. (2022) is elegant, it is quite involved, and it is unclear whether their framework can accommodate the crror-feedback mechanism. Morcover, the analysis in Khodadadian et al. (2022) leads to a sub-optimal O(7²) dependence on the mixing lime 7 in the main noise/ variance term. In light of the above discussion, we will provide a different analysis in this section that:
Departs from the Moreau Envelope approach in Khodadadian et al. (2022),
Achieves the optimal (T)) dependence on the mixing time T in the dominant noise term,
Establishes the desired linear speedup property, and
Shows that the effect of the distortion parameter 5 can be relegated to a higher-order term.
Crucial to achieving all of the above desiderata are a few novel ingredients in the proof that we now outline. First, we will require a more refined Lyapunov function than we used earlier. Before we introduce this Lyapunov function, let us define a couple of objects:
Σ Cs.e. and h, -
1 M
Σ h1g- SE[M]
é
M [E[M]
Next, let us define a perturbed iterate for this setting as 0, a 0, + ace-11 The potential function we employ is as follows:
M
E. E [10 0-| + Ca where E,
1
E
Σ
lee. 12
(98)
M
and C is a constant that will be chosen by later. Compared to the Lyapunov function the in equation 69 that we used for the single-agent setting, 3, differs in two ways. First, it incorporates the memory dynamics of all the agents. A more subtle difference, however, stems from the fact that the second term of E is scaled by a², and not a² (as in equation 69). This higher-order dependence on a will serve a twofold purpose: (i) help to shift the effect of to a higher-order term, and (ii) partially help in achieving the linear-speedup property. Unfortunately, however, the new Lyapunov function on its own will not suffice terms of achieving the linear speedup effect completely. For this, need careful way to bound the norm of the average TD direction defined below:
(0) &
Σ v0, R. KE[M]
(99)
M
An immediate way to bound (0) is to appeal to the bound on the norm of the TD update direction in Lemma 6. Indeed, this is what we did while proving Theorem 1, and this is also the typical approach for bounding norms of TD update directions in the centralized setting (Srikant & Ying, 2019; Chen al., 2019). The issue with adopting this approach in the multi-agent analysis is that it completely ignores the fact that the observations of the agents are statistically independent. As such, following this route will not lead to any "variance-reduction effect (key to the linear speedup property). At the same time, it is important to realize here that while the Markov data tuples are independent across agents, for any fixed agent i, {X,,} comes from a single Markov chain. This makes it trickier to analyze the variance of (0.). Via a careful mixing time argument, our next result (Lemma in the main body of the paper) shows how this can be done. Before stating this result, we remind the reader that we have used 7 as a shorthand for Te, with a². While a precision of a sufficed for all our prior singlo-agent analyses, we will need a² for the MARL case (to create higher-order noise terms in a).
42

---

Published in Transactions on Machine Learning Research (04/2024)
Lemma 21. (Controlling the norm of the Average TD Direction) Suppose Assumption 1 holds. For
Algoritim 2, the following are then true VI 2
E [1)=(()))111 & 8E
d +
32 M
+ 80* ) o², where de = 1|0g - 1* and
(100)
E [1)2(()))111
16E
16a
E
32
88a))0
88
02, )² where de = 110, -0
(101)
Proof. Let us start with the following set of observations:
[=))0
Σ gi
M
1
> (0c) )(.((0))
Σ gi (0))
M
M
2
Σ (0c) )l.c(0)))
Σ g cl
(102)
M
M
M
2
(0,), (0,((0")11
Σ gh. (00)
M
M
i=1
2
< _ +
Σ (00)
M
where in the last step, we used the Lipschitz property in Lemma 8. Next, to bound the second term in the above display, we split it into two parts as follows.
M Σ g
M
M
(0%)
= Σ
19,,( (0))2+
Σ
(0.)(()))).100))))
(+)
To bound (+), we simply use Lemma and the fact that ||0*|| < a to conclude that
< 16Mo
Now to bound (*+), let us zoom in particular cross-term, and write it out in way that highlights the sources of randomness. Accordingly, consider the term
T (0") (0")))"e+(00)) (K(,,, ((x
Since 0* deterministic, we note that the randomness in T originates from the Markov data samples X and Xi.. Moreover, since X and Xj. independent for + j, we have
E (E ( 0¹) [g(X 0*)).
Now X,, and Xj, were sampled i.i.d. from the stationary distribution æ, each of the two expectations within the above inner-product would have amounted g(#*) 0. Thus, the cross-terms would have vanished. Since for each agent i, X₁ comes from Markov chain, these expectations do not, unfortunately,
43

---

Published in Transactions on Machine Learning Research (04/2024)
vanish any longer. Nonetheless, now show that for t 2 7, can still make the cross-terms suitably "small" by exploiting the mixing property in Definition 1. Observe:
E [T]- [g [X
EE
x B 0 00 3(0)))
[[[ lo 1| -000) x ||E [E || 3(0")]
(103)
18 [| la( X 0*) Xx+- -(00)) E ( 00) X5,t=1 3(0*)]]
x (1001 + 1)²
S 4
In the above steps, (a) follows from the tower property of expectation conjunction with g(0)) = 0. For (b), used the Cauchy-Schwar inequality, and (c) follows from Jensen's inequality. Finally, (d) consequence of the mixing properly in Definition 1. We immediately conclude:
E [[(+)]] < 42
Putting the above pieces together and simplifying leads to equation 100. To from equation 100 to equa- tion 101, we simply note that
2E
d + FE
[106: 0,11 = 2R [+:] + 2 [||e-
113]
S
2 d. + +2x
(104)
This concludes the proof.
Essentially, Lemma 21 shows how the variance of the average TD update direction can be scaled down by factor of M, up to Oaa²) term. As we shall soon see, this result will play key role in our subsequent analysis of Algorithm 2. We now proceed to derive a multi-agent version of Lemma 16.
Lemma 22. Suppose Assumption 1 holds and the step-size satisfies a 1/16. For Algorithm 2, the following bound then holds for vt T:
E [di++] S (1 aww1 7) 16a E dd
3 w(1 - 7) E + 2nlE [A] +a²
/32
M + Sa² 02. )
(105)
where A = (0; 0 20,21 (0:) -(()))-
Proof. Simple calculations reveal that
o.t1 0, + a
Σ
=0, + (zz())).
(106)
M ME[M]
Subtracting 8' from each side of the above equation and then squaring both sides yields:
d = di + (0,0, ((,))()))) + (01))=(0.111
di + (0,0, 0", (0.)) + 2a 0" 20 (0))) + +a a 21122((0))1
(107)
(+)
(ao)
(*00)
We now have:
**) 2a(0, -0" (",)((+)) + 2a 00 (0.) g(0,))
(108)
$ 22ww(1 (1 - ? + 20, 8", (0.) - g(.)))
44

---

Published in Transactions on Machine Learning Research (04/2024)
where in second step, invoked Lemmas 3 and 4. To bound (**), we proceed as follows:
(**) v 4ad, 00: 0ell
20
x -dp d. + +2aml 0zl1
11
20: d 2a-nnlle-11
(109)
17
< di 2a 2a"110 nnE-I.
2x
where is constant to be decided shortly. In the first step above, used the fact that since each ( is 2-Lisschitz (see Lemma 8), the definition of (0) in equation 99 implies that =0 is also 2-Lipschitz. To bound (* ()), we directly use Lemma 21. Combining the above bounds, and simplifying by setting = w(1 and using < 1/16 leads to the desired claim.
In what follows, we will focus on bounding the bias term A 10,-0", g(O.)) by following the same high-level steps in the proof of Theorem 1. The key difference, however, will come from invoking Lemma. 21 instead of Lemma 6. We start with bound on the drift ||0 - -.
Lemma 23. Suppose Assumption holds. Then for Algoritlem 2, we have the following bound VI 2r:
( 32
E[110 - 0,- a s
max Gt, where G2 - 16E [ 1-TSeSt-1
16a Ex_
+ 80
0².
(110)
M
Proof.
The proof is a direct application of Lemma 21. Indeed, notice that
E [10 - 0.-- 12] S
Σ
E [1|0++] - 0=
t=t-
equation 106
2 Σ
E (0,))()))1
(111
eqoation 101
2
Ge: b--tttt-
max
which is the desired claim. In the last step, invoked Lemma 21 by noting that since t t2 27, we have that i 2 in the above steps requirement for using Lemma 21.
Equipped with Lemmas 21 and 23, we now proceed to bound the bias term following steps similar in spirit to the proof of Lemin 19.
Lemma 24. Suppose Assumption holds. Let the step-size be such that at 1/3. For Algorithm 2, the following is then true Vt 2 2T:
E (0. 8" 20.)) [(0.))] < 13arE [d]]] 1lar max G 12
(112)
1-rsest
Proof. We start by decomposing the bias term (0, -0 =0,) -((0)) as follows:
(0, Ō. ze ((O.)) + (Ō,-r 0" (0.) ((O)))
45

---

Published in Transactions on Machine Learning Research (04/2024)
To bound A1, we note that
A1
100
11-111 g(0ei
<
1
00.
01- + a5
2 |=+(0.)) - g(0.))1
207
1
(113)
1
10,
0.-11 112 (12)(0.)1 + (10(0,)
2at
1
100
-11 + or (0))1 4d)).
2at
where the last step follows from Lemmas and 5. Taking expectations on both sides the above inequality, and using Lemmas 21 and 23 yields:
E [Ai] S 4oTE [
aT
max
G. + OTG.
1-15tst-1
(114)
$ 4oTE
+ 2a7
max Ge.
t- stst
Next, to bound A2, we decompose it as follows:
A2 10,, - 0", (0p-)) 02, 5(0m_r)) + (0e- - 0-, =(0,) =0,000)))) z z000_r)) + (0e- -0, ((00(()))) -0(0,))
(+)
(*+)
(v**)
We now proceed to bound each of the three terms above. Let us start by observing that
(*+) S dc- (.(+-))ll
(a)
- 2dp_-11 0 - 8
< 2(d. + 110 - -0-r11)((0- - Ōr-rl
(115)
(8)
Vard, 110 - 0 2
2 2
Vat
110 8
< 4
ard +
at
where for (a), we used the fact that (0) 2-Lipschitz, and for (b), we used the fact that ar 1. Taking expectations each side of the above inequality and invoking Lemma 23, obtain
E [(())] S 4aTE [d]]] + 4a0 max G
(116)
(-r5PSt
46

---

Published in Transactions on Machine Learning Research (04/2024)
As before, the exact same bound in the above display applics to E [[(***)] x)]. We now turn to the main step in this proof.
E [*)] = E [6.- 0r, 21 (0,-))
g(0.-
10 I- 0r 1
E
(0))( g(0(_1)))
M
M
E
0
(0.,((0-0) -
M
M
E
0 0",
E
- g((()
M
11 E
(0. 0 1
E 10. - 9(06-))))
M
(117)
d
E (0=)) - 0(0.-t)1
0. 2 |
(1) + 1)]
3
[d]]
3 [11 - 11?] + 12a20²
30 [d")
+ 30 72
Ge + 12
max 1-stst-1
arE
[d]
+ AT
max
Ge + 12a20²
StSt
In the above steps, (a) follows from the fact that the Markov data tuples are independent across agents; (b) follows from the Cauchy-Schwarz and the triangle incquality; (c) consoquence of the mixing property Definition 1; for (d), we used steps similar those for arriving at equation 88; for (e), we used the bound on the drift from Lemma 23; and finally for (f), we simplified terms using ar S 1/3 and t 2 1. Combining the above bounds, we obtain
E [22] < 9aTE [c]] + 9aT
max Ge + 12a20². t-rSEst
The above display, in tandem with equation 114, leads to the claim of the lemma.
47

---

Published in Transactions on Machine Learning Research (04/2024)
We now ready to prove Theorem 3.
Proof. (Proof of Theorem 3) As in the proof of Theorem our first step is to establish recursion for the Lyapunov function E, in equation 98. To that end, appealing to Lemmas 22 and 24, using the definition of Ge, and some algebra leads to the following bound for all t 2 2T
5a
E [[ S (1 amd(1 7) + 42222)) R [ +
F
w(1 ?)
(118)
(1(1))
(2 + Sa +a 8a)
+ =552a T
max SESE
E
+ 35
max E t-sSISt
24a²
Now similar to the proof of Lemma 17, we have the following for each i e [M]:
|11e, 13] 5
E [[lest-11 [13] + 28E [[9..(0.)]]
26
1
S
E [ller-- [13] + 166E [[00 0.1[3] 48E [[19r. (0.)
(119)
25
1
E [[le,t-1lf =1 + 16a 16a2 2 + 648E [ + 9680².
28
Averaging the above bound across all agents then yields:
Es S ( 1 - 28
16a25) F + 645E [ + -66022
(120)
Combining the above display with equation 118, and using the definition of E,, we obtain Vt 2 27
E.t S (1- aaw(1 7) + 42a2- 64C [ + Ca' (1 (1- 23 + 16a26 + Cw(( 77)
5 E
+ + max 1-TSESt
E
d
352a
4
max b-rsest
F R
5
(1 (1-aw(1 7) + 42
64C 3 E [
+ Caa
1 (1-26
28 + 16a +
Ex-1
Cw(1 - -))
max + T (-7$1St
E, +
352ar
max -SSS
Ca Et-1 + R
(121)
5
< (1 1 aw[(1 - 42a² 64Coa
E d Ca²
1 11
16a28
E
28
Cw(( - 7)
Bi
B2
(a+ )
+ 352a7
max E + R, 1-7SES
where
(T (7(32)
32 8a + + 0² 96Ca"80"
R = 24a
Our goal is to now carefully pick a and so as to ensure that max (Bi, B2) < 1. Let us start with Bz. Suppose
and C = 2816 max max {
< 128
1122)
w(1 -
It is easy to then verify that
B2 < 1 1
48"
As for B1, we note that if
w 1 7
a < 850 max 6 T
(123)
48

---

Published in Transactions on Machine Learning Research (04/2024)
then
aw - ?)
Bi S
2
Also, under the requirement on the step-size a in equation 123, it easy to check that
awl(1 - ?)
46
In light of the above discussion, conclude that 1I 2T:
E4p+ 1 aww(1
7)
1 a + T)
E. 352ar
max E. R. P-TSESE
(124)
2
We are almost in position to invoke Lemma 20, All that remains to be verified is whether
awl( 7)
352a + 352 OT < 1.
2
C
With the choice C' in equation 122, if we set
w(1 -7
28167
then one can verify that
p+g<1- aw 7)
Combining all our prior requirements on a, we conclude that if
w(1
a S 2816 max {8, T)
(125)
then the following holds for all T > 27:
ET S Ci (1- aw(( - (1-a((1-))
T-27
4R
(126)
87
aw(1 77)²
where C1 maXisk<2> Eg. Simple calculations reveal that
4R aw 7) = -0
(0
aT
x²
+0
a² max (6, 7,
0².
ww1 [w((
M
w2 - 7/2
Using the above bound, and noting that [d]]
< Er, we have that VT 2 27:
E P S Ci (1-
aww(1 [1-aw(1- 7)
T-2r
+
aT
0²
a² max (8,7)8. 7 0².
(127)
87
ww1-
M
2 - 7)2
The fact that C = Onh + o²) follows from straightforward algebra similar to that the proof of Theorem This completes the proof.
49

---

Published in Transactions on Machine Learning Research (04/2024)
F Analysis of Multi-Agent EF-TD under an I.I.D. Sampling Assumption
In this scction, we provide simpler (relative to that in Appendix E) analysis of the MARL setting under common i.i.d. sampling assumplion. Essentially, consider a selting where for each agent i, al each time-step t, 8t, is sampled independently (from the past and across agents) from the stationary distribution n, and then 81,41 is sampled from Pu(-(8L,)) As it turns out, this particular "i.i.d. model" has been widely studied in the RL literature (Lakshminarayanan & Szepesvári, 2017; Dalal et al., 2018; Bhandari et al., 2018; Doan al., 2019; Liu & Olshevsky, 2021a); thus, we believe that providing an analysis for this setting would be useful to the reader. Our main result for this setting as follows.
Theorem 6. There exist universal constants e, C 2 1, step-size a S (1- (c)(, and set of conver weights (we), such that the ilerales generated by Algorillen 2 salisfy the following after ilerations:
EE [ - Vo. Po-118]] = =0 -(epp/ (oxp--ot
w (= ))
o²
+0
+ +33
(128)
C6
w - 7)
where T3 = (62 (w)
Br = Ei 1rbe, and 0² 2 E [119:(() (8* 112)4
As in Theorem 3 where analyzed the multi-agent setting under Markovian sampling, the above result also establishes a linear speedup in sample-complexity w.r.t. the number of agents M. The above result is somewhat cleaner in the sense that it provides a bound on the performance of the true iterate sequence {0,), as opposed to the perturbed iterate sequence {6r}. We believe that it should be possible to provide a bound on the true iterates of the form in Theorem under Markovian sampling as well; we leave this as future work.
To proceed with the analysis, we will require two auxiliary results. The first is taken from Bhandari et al. (2018).
Lemma 25. Fir any 0 E K The following holds under the i.i.d. sampling model:
E [119c(0)) s 20 + +11 - Vg- I1
The next result is an "averaging lemma" that has been adapted from Koloskova et al. (2020) and Stich (2020).
Lemma 26. Let {pelio and {sthe2 be sequences of positive numbers satisfying
Pot1 $ (1 aA)pp: - Bass Ca² + +Da
for some posilive constants A, B 2 0, C,D 2 0, and for consland slep-sizes 0 < a S 1b where E > 0. Then, there erists constant step-size a S E such that
T W
A (- + A(T A(T+1) +1) + Dl
2C'
Wis; S (E + A)exp
(129)
AT
1=0
for w A (1 - (-)) Wr 2 Σt Wt, and
= max (1), minn442po + ( ()9/,,,1),,,/////// (T D))
We start with the following result.
Lemma 27. Suppose the step-size a is chosen such that a S (1 (1-11/112. Then, the iterates generated by Algorithm satisfy the following under the i.i.d. observation model:
E [10 10 < (1 (1-00) aw(1
(1-aw(1- -7) E. [10. - 1- a(1
7) a)
[io - -Vo- 1o-113]
5a
Sa?
+ (1 (1-7) F +
4
M
(130)
We remind the reader here that the smallest eigenvalue the matrix 5, 4 12P.
50

---

Published in Transactions on Machine Learning Research (04/2024)
Proof. Starting from equation 106, we have:
E [100+11 [²] E [10: 0-1
20 M
E
(0:
0*
Di,t (0,))
+ t
1 M
Σ ge, (c(M]
(131)
(M[M]
T1
To bound Ti and T2, let first define by Fi-1 the sigma-algebra generated by all the agents' observations From the dynamics of Algorithm 2, observe that 0g, 0, and (er.hee[M) are all Je-r-measurable. Using this fact, bound T₃ follows:
up to time-step t 1-1, i.e., the sigma-algebra generated by
1
T
E
(0: 0" Σ (o.)(o.)))FF VE[MS]
M
2aEE
(0: ,", ((:))
2aE
(0. 0" ((0))) E&E [10, fr, (0.))
< 2nB [0: 0" ((())) + a(1 -1) [1.)11)111)
4a
4
+
(1 - 7)
E [110; 0.112]
(132)
S 2aE [(0: ,%, ((0.)) + a(1 - 7)
4
[1g(0))111
E |||@z_1113]
4
(1 7)
(6)
20 [00 - .4 .9(0))) + a(1 - 7)
4a 3
E [11)(0.)]
+
(1 77) Ei-1
4
4a²
a(1 B)B [IVo Vo- 11]1
ET-
(1 (1-
In the above steps, (a) follows from the fact that the agents' observations are assumed to have been drawn i..d. (over time and across agents) from the stationary distribution म; for (b), we applied equation 19; and (c) follows from Lemmas 4 and 5. To bound T2, we first split it into two parts as follows:
a T-
E M
Σ (0.). - x(0.)) + Mg(O,)
(E[M]
(133)
2a²
IE
Σ (g.,((.)) g(0,)) Sc[M]
2a²E [10(0:)11
M
To simplify the first term in the above inequality further, let define Yú, (r.e(0.) g(0)), Vi E [M] Conditioned on F,-1, observe that (i) Yú, has zero mean for all i E [M]; and (fi) Y., and Yj, are independent for i + j (this follows from the fact that Xx and Xj, are independent by assumption). As consequence of the two facts above, we immediately have
((Y,, [3)))==))000 0,Vi, [M] $j
51

---

Published in Transactions on Machine Learning Research (04/2024)
We thus conclude that
E
Σ (E(M
(o.)
9(8.))
E
E
Σ iE(M]
Y 1F
R
E [111,1111
(134)
ME
M (E [ [112..111=:
M (B [1
where (a) follows from the fact that conditioned on Fi-1, Yu, and Yj, are identically distributed for all
j.j E [M] with i $... Plugging the result in equation 134 back in equation 133, obtain
T2
2a
E
[[(..(0.)) - 3(0.))11
+ 2a [I0(0.)1*]
M
4a
2
[119n.(0.)11]] + 2a²
(1+
2
E
[1000))1]]
(135)
M
M
Saa02
S 56a
2
[IVo, - -vo-133] +
M
where in the last step, used Lemmas 5 and 25. Now that we have bounds each of the terms Tj and T2, we plug them back in equation 131 to obtain
E [1]0,+] 0-113] s E [110 0-113] a(1 -7) (1-
56a
E [iVe,
Vo- 11.113]
+ (1 (1-2)
4
Er-1
8020²
(136)
M
a(1 a(l-7) 116o
4a
8
- E [100, 0" [|3]
Vo- 1o-11%] +
E. +
2
(1
M
where in the last step, we used the fact that a S (1 711-1/112 112. By splitting the second term in the above inequality into two equal parts, using Lemma 3, and the fact that
liVe Vo- [b-1 s E [ive
Vo- vo-113]
+ a² +a²E.1. E.-1.
we further obtain that
E |11 1- < (1 (1- aw 7)
a(1 - 7) E [i. 1o-11%]
5a
80202
E |100 10]]]]
EE-1
(1 (1-7)
M
which is the desired conclusion.
We now complete the proof of Theorem as follows.
Proof. (Proof of Theorem 3) Our goal is to establish recursion of the form in Lemma 26. To that end, we need to first control the aggregate effect of the memory variables of all agents, captured by the term E,- This is casily done by first using the same analysis as in Lemma 17, and then appealing to Lemma 25, to conclude
E [1 < (1
25 [[lea-111 [13] + 168E [16. - 1o-1188 + 4802 Vi E [M].
Averaging the above inequality over all agents, and using the definition of E, yields:
Eg S 1
1
F + 165E [ - Vo- Vo-113] + 48o2
25
52

---

Published in Transactions on Machine Learning Research (04/2024)
Using the above bound along with Lemma 27, we obtain:
E(+1 1 aw(( - 7)
0-] a(1 7) E [IVe. Vo-118] + 5a
8a?
E [10,
1-79 Ei-1 +
Ca E,
8
M
1 aw(( - 7)
IE' |10, 0-1
a( 7) 16Ca.0
E LIvo Vo- Vo-113) 11b]
8
+ Ca
1
5
Pa-1
8a"0 40 M
28
C(1 0(1-7))
(137)
Based on the above inequality, our goal is to now choose a and C' in way such that we can establish a contraction (up to higher order noise terms). Accordingly, let us pick these parameters a and C as follows:
(1 (1-))² a (1-7)
206
556
With some simple algebra, it then easy verify that:
1 aww( 7)
a(1 7)
[1V. Vo-12 +ca3 (1-
1
E+1
E [110. 0-11]]
E
8
46
00
82
+
(1-9)
aw(1 7)
a(1 a(l-7)) | V 11
E ||06 - 1-] + C
(138)
+ 0a202 + (1 - 7)
80
aw(1 - 7)
8 E a(1 71)
8a202
80a
E [iVo. - Vo. 11/1
+
8
M
(1 -)-)
We have thus succeeded in establishing recursion of the form in Lemma 26. To spell things out explicitly in the language of Lemma 26, we have
P: E E [VV Vo- 11/] :A w01 (1177), B (1 (1-2), C=
S0²
800
D
M
(1 [1-7)
and a (1 (1-7)/(1125) suffices for the recursion in equation 138 to hold. Thus, for us, E Lemma 26 along with some simplifications then yields:
(1-7) Applying
T
|00 - 113
w(1
-1T
o²
Σ
E.E Vio.
Vg. [b]]
<0
+0
(1-
C'8
w(1 - 2T
2
t=
(139)
0282
+ δ
w
T72
where w. 2 Wr,WT, and C' suitably large constant. The result follows by noting that
T
E B[1 - -Vo- 1o-13
5
E.E |IVo
Vo- 10-12
2m0
where Ōr = Σtz w.Or.
53


Reviews:
[{"review_id": "unoX48jSo5", "reviewer": "Reviewer_bgpG", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Overall the paper has made solid theoretical contributions to the field of TD-learning analysis. They consider a particular variant of the algorithm which is motivated by sparse or communication efficient update. The theoretical results seem novel, as they adopt new techniques for proving the convergence, and generalize prior results as special case. The theoretical results are also fairly interesting and showing the convergence of the EF-TD algorithm.\n\nThe weakness is mainly empirical: ideally the paper can provide more simulation results that showcase the practical efficiencies of the algorithm, and shed light on the theoretical insights. From the theoretical perspective, I would also hope that the paper provides more geometric insight of the proof technique and discuss how the EF-TD algorithm addresses the communication efficient motivation for the paper - in its current form, EF-TD does not seem to be communication efficient due to the error feedback vector that needs to be stored.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces analysis for a variant of TD-learning where the updates are corrupted - the update vector is either computed to be a signed vector, or compressed to be just the top-k components. The paper proposes EF-TD, an error feedback mechanism to improve the convergence property of the algorithm. The paper analyzes such techniques, shows its convergence guarantee in both gradient descent and stochastic gradient descent case, and its extension to multi-agent case. The paper finishes with a simulation study on the practical behavior of such algorithms in tabular domains.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- What's the connection between EF-TD and momentum based methods for TD-learning? It feels that the error feedback mechanism is highly similar (at least in mathematical forms) of momentum based approaches for accelerating SGDs.\n\n- Without the error feedback, is it possible to deliver convergence results to the corresponding TD algorithms?\n\n- With the error correction feedback, I wonder if the update has been not as communication efficient as motivated. Concretely, each vector $h_t$ is sparse (for the top-k variant) and can be stored with fewer bytes (for the signed variant),  but the error correction term $e_t$ is not. In fact the complexity of the original update vector has been relayed to $e_t$ from $h_t$. So it feels like the motivation from efficient communication is not really addressed as expected.\n\n- Fig 1 provides a geometric interpretation of $Q_\\delta$, but I wonder whether it'd be more informative to provide geometric insights on how EF-TD works. Prior work (Bhandari et al 2018) provides a geometric insight into the convergence of TD-learning, that is the gradient moves in a direction that minimizes the distance between $\\theta$ and $\\theta^*$. If we do not carry out EF, does this become invalid? If we carry out EF, what kind of corrections do we gain in the geometric sense?\n\n- I am not an expert in noisy robust SGD analysis, but I wonder how much novelty the proof technique is from a proof process that takes the analysis from a SGD literature and adapt to the TD case similar to the techniques used in Bhandari et al 2018.\n\n- Simulation would be nice to see the scaling curve in terms of k for the top-k variant. How do the behavior changes as we increase k? We should expect to recover TD as k becomes large and worse performance as k becomes small.\n\n- TD and EF-signed-TD appear to have exactly the same performance in Fig 2. This makes me wonder whether the EF process basically makes up for the difference between signed TD and TD, which defies the sparse or low-storage motivation for such updates in the first place.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "e7PADXEYqQ", "reviewer": "Reviewer_KbFY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths and weaknesses Strengths\n\nThe paper makes solid technical contributions. The analysis is highly non-trivial considering the temporal correlations in Markovian sampling.\nGoing beyond the linear approximation case, the authors also extend their theory to cases of general nonlinear stochastic approximation and MARL, which greatly enriches and strengths the result. 3.The paper is well-written and easy to follow. Weaknesses & Questions 1.Question about the discussion on Thm. 1: As the authors stated, the effects of the mixing time  and the distortion measure  has an additive effect on inflating the variance. It seems that, to ensure the same level of \n, one should use smaller  for larger . However, the paper states the opposite. Could the authors explain more on this? 2.Abuse of notation: The authors use  to denote both the reward and the convergence error (Thm. 1), which probably leads to confusion. 3.A M-fold speedup -> an M-fold speedup; the only other paper that does so is the very recent work (Khodadadian et al., 2022) -> the only other paper that does so is the very recent work Khodadadian et al., 2022 Requested changes Some clarifications and minor corrections requested in \"Weaknesses & Questions\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "Summary of contribution This paper provides the first theoretical analysis for TD learning with compressed updates and error feedback, which achieves a similar convergence rate compared with the SGD counterpart without compression. This result reveals the robustness of RL algorithms to structured perturbations. The authors also conducted simulation to verify the theory.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Summary of contribution This paper provides the first theoretical analysis for TD learning with compressed updates and error feedback, which achieves a similar convergence rate compared with the SGD counterpart without compression. This result reveals the robustness of RL algorithms to structured perturbations. The authors also conducted simulation to verify the theory.\n\nStrengths and weaknesses Strengths\n\nThe paper makes solid technical contributions. The analysis is highly non-trivial considering the temporal correlations in Markovian sampling.\nGoing beyond the linear approximation case, the authors also extend their theory to cases of general nonlinear stochastic approximation and MARL, which greatly enriches and strengths the result. 3.The paper is well-written and easy to follow. Weaknesses & Questions 1.Question about the discussion on Thm. 1: As the authors stated, the effects of the mixing time  and the distortion measure  has an additive effect on inflating the variance. It seems that, to ensure the same level of \n, one should use smaller  for larger . However, the paper states the opposite. Could the authors explain more on this? 2.Abuse of notation: The authors use  to denote both the reward and the convergence error (Thm. 1), which probably leads to confusion. 3.A M-fold speedup -> an M-fold speedup; the only other paper that does so is the very recent work (Khodadadian et al., 2022) -> the only other paper that does so is the very recent work Khodadadian et al., 2022 Requested changes Some clarifications and minor corrections requested in \"Weaknesses & Questions\"", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "0fWM1sdxp1", "reviewer": "Reviewer_GFLY", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "* The theoretical results seem to be novel and relevant. While similar analysis was performed for SGD (with similar guarantees), the paper seems to be the first to establish theoretical guarantees for MDPs. Furthermore, the paper makes the point, that this setting requires novel proof techniques.\n\n* The presentation is excellent. The paper makes a very good job in motivating the problem, discussing the results and comparing to related work and pointing out the differences.\n\n* I do not see any major weakness.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper provides theoretical analysis of the impact of using compressed gradients on the convergence of policy evaluation.\nNamely, the paper considers TD(0) algorithms for a quite general form of compression types (including using only the sign of the gradient, or the top-k dimensions) and analyses algorithms that use error feedback by locally accumulating the differences between actual and compressed update direction. In particular, the paper proves\n\n* linear convergence for TD(0) with linear function approximation\n* a similar theorem for the non-linear setting under the assumption that the update direction is Lipschitz continuous\n* linear speedup with the number of agents in a multi-agent RL setting.\n \nThe theoretical results are validated on simple toy problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "* Section 3 claims that the TD(0) update direction is not a stochastic gradient of any fixed objective. To me it is not immediately clear whether this is true or not, and hence, I would suggest to either provide evidence or soften the claim. (The claim is not critical to the contribution)\n\n* The main theorems all state that there exist a $C \\ge 1$ , but later uses $C_\\tau$. Please make the notation consistent.\n\n* In theorem, as far as I understand, should read \"Suppose Assumption 2 holds **with L=2** [...]\"\n\n* I suggest to use logscale when plotting the MSE in Figure 2, to make it easier to spot differences (if any) between TD and EF-SignTD", "broader_impact_concerns": "I don't think that the paper requires a broader impact statement.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "zemV0Dz6Gm", "reviewer": "Reviewer_fvTK", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main ideas are clearly presented, both for the results and the technical contributions.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper investigates the robustness of reinforcement learning (RL) algorithms to compressed updates. This attempts to extend to the RL setting the type of results that have been carried out for stochastic gradient descent. The authors first develop a general framework for compressed stochastic approximation, with a perturbed update direction. They also consider a collaborative multi-agent RL (MARL) setting and show that it is possible, even in the presence of compression, to have a scheme almost as efficient as in the non-compressed case.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I do not have any specific changes to request.", "broader_impact_concerns": "No specific concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper is thoroughly written and introduces interesting proof techniques / approaches to the considered RL problems. As such it can be a worthwhile contribution to the relevant TMLR community. Also the reviewers recommend acceptance of the submisson and appreciated the authors' updates made during the discussion phase. Hence, following their recommendations, I am recommending acceptance of the paper.
Decision: Accept (poster)