Closing the Gap Between SVRG and TD-SVRG with Gradient Splitting
Authors: Arsenii Mustafin
Ioannis Paschalidis
Alex Olshevsky
Venue: Submitted to ICLR 2023 (2023)
Keywords: Temporal Difference learning
Reinforcement Learning
SVRG
Optimization

Abstract: Temporal difference (TD) learning is a simple algorithm for policy evaluation
in reinforcement learning. The performance of TD learning is affected by high
variance and it can be naturally enhanced with variance reduction techniques, such
as the Stochastic Variance Reduced Gradient (SVRG) method. Recently, multiple
works have sought to fuse TD learning with SVRG to obtain a policy evaluation
method with a linear rate of convergence. However, the resulting convergence rate
is significantly weaker than what is achieved by SVRG in the setting of convex
optimization. In this work we utilize a recent interpretation of TD-learning as the
splitting of the gradient of an appropriately chosen function, thus simplifying the
algorithm and fusing TD with SVRG. We prove a linear convergence bound that
is identical to the convergence bound available for SVRG in the convex setting.

Under review as a conference paper at ICLR 2023
CLOSING THE GAP BETWEEN SVRG AND TD-SVRG WITH GRADIENT SPLITTING
Anonymous authors Paper under double-blind review
ABSTRACT
Temporal difference (TD) learning is simple algorithm for policy evaluation in reinforcement learning. The performance of TD learning is affected by high variance and it be naturally enhanced with variance reduction techniques, such as the Stochastic Variance Reduced Gradient (SVRG) method. Recently, multiple works have sought fuse TD learning with SVRG to obtain a policy evaluation method with geometric rate of convergence. However, the resulting convergence rate significantly weaker than what is achieved by SVRG in the setting of convex optimization. In this work we utilize recent interpretation of TD-learning as the splitting of the gradient of an appropriately chosen function, thus simplifying the algorithm and fusing TD with SVRG. We prove geometric convergence bound with predetermined learning rate of 1/8, that is identical to the convergence bound available for SVRG in the convex setting.
INTRODUCTION
Reinforcement learning (RL) is learning paradigm which addresses class of problems in sequen- tial decision making environments. Policy evaluation is one of those problems, which consists of determining expected reward agent will achieve if it chooses actions according to stationary policy. Temporal Difference learning (TD learning, [Sutton (1988) is popular algorithm, since it is simple and might be performed online on single samples or small mini-batches. TD learning method uses Bellman equation to bootstrap the estimation process update the value function from each incoming sample or minibatch. As all methods RL, TD learning from the "curse of dimensionality" when number of states is large. To address this issue, in practice linear or nonlinear feature approximation of state values often used.
Despite its simple formulation, theoretical analysis of approximate TD learning is subtle. There few important milestones in this process, one of which a work of Tsitsiklis Van Roy (1997), in which asymptotic convergence guarantees were established. More recently advances by Bhandari et al. (2018), Srikant & Yingl (2019) and Liu & Olshevsky (2020). In particular, the last paper shows that TD learning might be viewed as an example of gradient splitting, a process analogous to gradient descent.
made
TD-learning has inherent variance problem, which is that the variance of the update does not go to zero as the method converges. This problem is also present in a class of convex optimization prob- lems where target function is represented as sum of functions and SGD-type methods are applied Robbins & Monro (995T). Such methods proceed incrementally by sampling a single function, or a minibatch of functions, techniques were developed to address this problem and make convergence faster, including SAG Schmidt al. (2013), SVRG Johnson & Zhang (2013) and SAGA Defazio et al. (2014). These methods collectively known as variance- reduced gradient methods. The distinguishing feature of these methods is that they converge geometrically.
use for stochastic gradient evaluations. A few variance reduction
The first attempt to adapt variance reduction to TD learning with online sampling was done by Korda & La (2013). Their results were discussed by Dalal et al. (2018) and Narayanan Szepesvári (2017 Xu et al. (2020) performed reanalysis of their results and shown geometric convergence for Variance Reduction Temporal Difference learning (VRTD) algorithm for both Markovian and i.i.d
sampling. The work of Du et al. (2017) directly apply SVRG and SAGA to version of policy

---

Under review as a conference paper at ICLR 2023
evaluations by transforming it into equivalent convex-coneaye saddle-point problem. Since their algorithm uses two sets of parameters, in this paper we call it Primal Dual SVRG or PD SVRG.
All these results obtained geometric convergence of the algorithms, improving the sub- nub-geometric convergence of the standard TD methods. However, the convergence rates obtained in these papers significantly worse than the convergence of SVRG in convex setting. In particular, the result- ing convergence times for policy evaluations scaled with the square of the condition number, as opposed SVRG which retains the linear scaling with the condition number of SGD, Quadratic scaling makes practical application of theoretically obtain values almost unfeasible, since number of computations becomes very large even for simple problems. Moreover, the convergence time bounds contained additional terms coming from the condition number of a matrix that diagonalizes some of the matrices appearing the problem formulations, which can be arbitrarily large.
In this paper we analyze the convergence of the SVRG technique applied to TD (TD-SVRG) in two settings: (t) a pre-sampled trajectory of the Markov Decision Process (MDP) (finite sampling), and (ii) when states are sampled directly from the MDP (online sampling). Our contribution is threefold:
For the finite sample case we achieve significantly better results with simpler analysis. We are first to show that TD-SVRG has the same convergence rate as SVRG in the convex optimization setting with a pre-determined learning rate of 1/8.
For i.i.d. online sampling, we similarly achieve better results with simpler analysis. Sim- ilarly, we are first to show that TD-SVRG has the same convergence rate as SVRG in the convex optimization setting with predetermined learning rate of 1/8. In addition, for Markovian online sampling, we provide convergence guarantees that in most cases are better than state-of-the art results.
We are the first develop theoretical guarantees for an algorithm that can be directly applied to practice. In previous works, batch sizes required to guarantee convergence were very large that made them impractical (see Subsection H..) and grid search was needed to optimize the learning rate and batch size values. We include experiments that show our theoretically obtained batch size and learning rate can be applied in practice and achieve geometric convergence.
2 PROBLEM FORMULATION
We consider discounted reward Markov Decision Process (MDP) (S, A, Prr, r), where S is a state space, is an action space, P P(s'|s, s'S,., are the transition probabilities, are the rewards and 7 E [0, 1) is a discount factor. In this MDP agent follows policy x. which is a mapping क : S X A - [0, 1J. Given that policy fixed, for the remainder of the paper we will consider transition matrix P. such that: P(s, 8') En a))(')) a)) We assume, that Markov process produced by transition matrix is irreducible and aperiodic with stationary distribution Pa.
r(s, s')
Here V is the value functioo, formally defined to be the unique vector which satisties the equality TVVT= VT, where T is Bellman operator, defined as: V=) = Σ, P(s, s') (r(s, s') + (s)(s')) The TD(0) method is defined as follows: one iteration performs a fixed point update on randomly sampled pair of states s, s' with learning rate ry: V(s) V(s) 17(r(s, s') + +VV(s') Vs))). When the state space size |S] is large, tabular methods which update a value for every state V(s) become impractical. For this reason linear approximation is often used. Each state represented as feature vector d(s) E Ad and state value V (s) is approximated by (*((s) s oss) To, where 0 is tunable parameter vector. Now single TD update on randomly sampled transition s, s' becomes:
The policy evaluation problem is compute V*, detined as: (*) = E [
7'r++1] 2'r+11)
<- 0 + 70s.s'
= 0 + ((((s, + - ((s)
where the second equation should be viewed as a definition of (0).
Our goal is to find parameter vector 0* such that average update vector zero E (f*)] = O.
This expectation is also called mean-path update g(0) and can be written
2

---

Under review as a conference paper at ICLR 2023
Table 1: Algorithms parameter comparison. PD SVRG and PD SAGA results reported from Du et al. (2017). VRTD and TD results from Xu et al. 2022), GTD2 from Touati et al. (018)) Amin Q and x))) are used define, respectively, minimum eigenvalue and condition number of matrix Q Aa in this table denotes minimum eigenvalue of matrix 1/2( + AT). Other notation is taken from original papers. For simplicity + y upper bounded by 2.
Setting
Method
Learning rate
Batch size
Total complexity
GTD2
92x20 9
0 x(Q)'H Amin (G)
Finite sample
PD SVRG
Auiin (A" CA
(C) Amin (A LAy
O Amiin
AJ log( (1)
48k(C)L2
(A'C I
PD SAGA
AA A) 3(8x tmpp))
1
0 k²(C)
Amnin (A"0- log (b)(
This paper
1/8
16/AA
0 0 AA
1
log(?))
TD
da min
0 1 log(?)) EAA
16 Aa
i..d sampling
VRDT
Aa/64
132
O(max( + x log( 2))
X
This paper
1/8
16/\A
O &, , log )))
σ(0) [a (0)
(( ())))))))) + E.,y s()((s]
= A0 b,
where the last line should be taken as the definition of A and Finally, the minimum eigenvalue of matrix (A + //2 plays important role in our analysis and will be denoted as Amin-
There are few possible setting of the problem: the samples 8, might be drawn from the MDP on-line (Markovian sampling) independently (L.dd. sampling): first state is drawn from May then is drawn from correspondent row P. The latter case analysis is covered in 6 An- other possible setting for analysis is the "finite sample set" setting, in which states a data set D {(8,, (1, Ft, 8 of size N drawn ahead of time following Markov sampling, and TD(O) proceeds by drawing samples from this data set. We analyze this case in Sections 5
We make following standard assumptions: Assumption 1. The matrix A is non-singular.
Assumption 2. [[ø())ll2 & for all s E S.
Assumption needed to guarantee that A A- exists and the problem is solvable. Assumption is introduced for simplicity, it always might be fulfilled by rescaling feature matrix.
2.1 KEY IDEA OF THE ANALYSIS
In our analysis we often use function (0),, defined as:
f(0) (0 -00)TA(( 8*).
(1)
3

---

Under review as a conference paper at ICLR 2023
Function f(0) is key characteristic function of TD learning. In their paper Liu & Olshevsky
(2020) introduce function f()) as (1- (1->>llVe Vo 1 + > -Vp= [| Then, authors define gradient splitting (linear function h(x) ( a) is gradient splitting of quadratic function j(x:) (x a) (a - a). where Q is symmetric positive semi-definite matrix, if B + B² 2Q) and show that negation mean-path update -0(0) is indeed gradient splitting of function f(0)- In this paper we do not use the fact that function f(0) might be represented as weighted sum of D- norm and Dirichlet norm and, for convenience, define function f(0) based on its gradient splitting properties.
We rely on interpretation of TD learning as splitting of the gradient descent in our analysis. In Xu et al. (2020) authors note: "In Johnson & Zhang (2013) the convergence proof relies on the relationship between the gradient and the value of the objective function, but there is not such an objective function in the TD learning problem." Well, viewing on TD learning as gradient splitring gives the relationship between the gradient and the value function, which allows implementation of similar analysis in Johnson & Zhang (2013) to achieve stronger results. It also gives the objective function f(0) which is better measure of the distance to optimal solution, rather than ||0 0*1,, and yields tighter convergence bounds.
THE TD-SVRG ALGORITHM
We next propose modification of the TD(0) method (TD SVRG) which can attain geometric rate. This algorithm is given below as Algorithm 1. The algorithm works under the "fixed sample set" setting which assumes there already exists a sampled data set D. This the same setting was considered in Du et al. (2017). However, the method we propose does not add regularization and does not use dual parameters, which makes it considerably simpler.
Algorithm TD-SVRG for finite sample case
Parameters update frequency M and learning rate 17
Initialize to- Iterate: for m 1,2,...
0 mm
((0) = N Le. (0),
where (0,5(1)) (r(s, 5i) -
Ou O.
Iterate: for .,, MM
Randomly sample s from the dataset and compute update vector 1t (0,-1) (0) + g(0). Update parameters O2 0, Tpu..
end
Set 0m = 02 for randomly chosen t E (O...., M 1).
end
Like the classic SVRG algorithm, our proposed TD-SVRG has two layers of loops. We refer one step of the outer loop as an epoch and one step of inner loop as an iteration. TD-SVRG keeps two parameter vectors: current parameter vector Oz, which is being updated every iteration, and the vector 8, which is updated the end of each epoch. In the beginning of outer loop, the mean-path TD update vector g()) is computed with pass through the entire data set. This vector is used in inner loop compute local updates vi 9s.s (0..) g (0) g()), where g0.--(0t-1 is TD update computed on uniformly randomly sampled data point from D with current parameter vector 0, and ( is a TD update computed on the same data point. Each iteration ends with an update of epoch vector, which is randomly chosen from parameter vectors during the epoch.
4 CONVERGENCE ANALYSIS
In this section we show, that under simple assumption Algorithm attaai geometric convergence in terms of specially chosen function f(0) with v) is (11) and M is (1/Ammi))
4

---

Under review as a conference paper at ICLR 2023
4.1 PRELIMINARIES
In order to analyze the convergence of the presented algorithm we define expected square nomn of difference current and optimal parameters as w(0)
mo( = Ea,orllge, I0.8' (01
(2)
With this notation provide an technical lemma. All of our proofs are based on variations of this lemma.
Lemma 1. If Assumptions 7 hold, epoch parameters of two consecutive epochs and m
related by the following inequality:
2qM - (eo & 1 21/² M'Ew (mm-))
where the expectation taken with respect to all previous epochs and choices of states s, s during the epoch m.
Proof. The proof of the lemma generally follows the analysis logic in Johnson & Zhang (0133) might be found in Appendix
Lemma 1 plays an auxiliary role in our analysis and significantly simplifies it. introduces new approach to the convergence proof by carrying iteration to iteration and epoch to epoch bounds to the earlier part of the analysis. particular, deriving bounds terms of some arbitrary function u(() is now reduced to deriving upper bounds on ||0m- and w(0) and lower bound on f() in terms of the function In fact, the function (() itself will play the role of u(O) in our proof.
In addition, it is now easy to demonstrate the point we made in Subsection 2. The main problem of direct application of the SVRG convergence analysis to TD learning is that it requires the target function P(w) to be a sum of convex functions d; ()) ) where all functions d; are L-Lipschitz and y- smooth (notation here is from Johnsonn & Zhang (203)) Of course, the TD learning problem cannot be represented in this form. However, the main use of T.-Lipschitz and smoothness properties in the original to derive bound on the expected norm of the difference between current and optimal parameters. As will be shown later, in TD learning this expected norm (w(() in our notation) still might be derived, even when a sum representation does exist.
4.2 WARM-UP: CONVERGENCE TERMS OF SQUARED NORM
Firstly, we derive the convergence bound in terms of ||@ 181 and show that they are consistent with previous results.
Proposition 1. Suppose Assumptions 7 2 hold. If we chose learning rate 17 number of iteration as M = 32/Xanm then Algorithm has a convergence rate of:
Amin/ /32 and
El - 8+1191 <
1100 -0 8$112.
7
Proof. The proof is given in Appendix B
Note that deriving convergence rate terms of squared norm 11 - 8* leads to batch size m to be (1/122 ( which is better than results in Du et al. (2017). since their results has com- plexity O (C) where x(C') is condition number of matrix C = E.ep[o(s (())))())')) and Roor1/Amii (AT A). Experimental comparison of these values is provided in Subsection
5

---

Under review as a conference paper at ICLR 2023
4.3 FIRST MAIN RESULT: CONVERGENCE TERMS OF f(0)
In this section derive a bound in terms of f(0). For analysis to be simpler and illustrative we introduce one more assumption which ease in section 4.5.
Assumption (Dataset Balance). In the dataset D first state of the first sample and the second state of the last sample is the same state, i.e. 81
We need this assumption to omit dataset bias, so that states s and have the same distribution, as in the original MDP. Having this assumption, we can proof theorem 1:
Theorem 1, Suppose Assumptions inner loop iterations M 16/2min then Algorithm I will have convergence rate of:
7
hold. If we choose learning rate rj = 1/8 and number of 3
m f(06).
E(((mm)) &
Note that 6m refers to the iterate after m iterations of the outer loop. Because we choose the length M of the inner loop to be 16/Amins the total number of samples guaranteed by this theorem until (O)() & is actually (16/Anl /m/n) logg)/1))
Proof of Theorem 7
The proof is given in Appendix
Convergence analysis without Assumption 3
provided in Appendix Section D
4.4 SIMILARITY OF SVRG AND TD-SVRG
Liu & Olshevsky 2020) show that negation mean-path update -g(0) is gradient splitting of ](O). In this work we show even greater importance of function s(0) for TD learning process.
Recall convergence rate obtained in Johnson & Zhang (2013) for sum of convex functions setting:
1
2Lm
7n(1 - -mmmm 1 2T,
where y is a strong convexity parameter and L is Lipschitz smoothness parameter (employing nota- tion from the original paper). Function (() (0 0+)z A(D 0* is 2Amin strongly convex and 2-1 2-Lipschhtzz smooth, which means that convergence rate obtained in this paper is identical to the convergence rate SVRG in convex setting (we have slightly better bound L instead of 2L due to strong bound on (f) we derived for this setting). This fact further extends the analogy between TD learning and convex optimization earlier explored by Bhandari al. (2018) and Liu & Olshevsky 2020
5 BATCHING SVRG CASE ANALYSIS
this section we extend our results to inexact mean-path update computation, applying the results of Babanezhad et al. (2015) to TD SVRG algorithm. We show that geometric convergence rate might be achieved with smaller number computations by estimating mean-path TD-update instead of performing full computation. This approach is similar to to|Peng et all] (2019), but again doesn't 't require introduction of dual variables. In addition, we provide a particular way to compute nmm which might be used in practice.
Since computation of mean-path error is not related to the dataset balance, in this section for sim- plicity assume that dataset is balanced.
Theorem 2. Suppose Assumptions 7 3 hold, then if learning rate is chosen as 7) = 1/8 number of inner loop iterations M = 16/ Amin and batch size Thm = min(N, cpam(N (2) mmaal" 2 + 8|( 11²)),
N
where c is a parameter, Algorithm 2 will have convergence rate of:
(((()))) pz' + C),
where p (0, 1) is convergence rate and C is some constant.

---

Under review as a conference paper at ICLR 2023
Algorithm 2 TD-SVRG with batching for finite sample case
Parameters update frequency M and learning rate 1)
Initialize Og-
Iterate: for m 2,
0 = 0-0
choose batch size T'm
sample batch D of size nm from DD without replacement, compute μ Pa LEDm (0),
where 9s.8 (0) = (r(s,
( - 0))s)))
Bu A.
Iterate: for = 1.2....,
Randomly sample 8, from D and compute update vector
U/ (0,-1) 0 (0) + 14.
Update parameters O2 = O1-1 THUp.
end
set 6m 0, for randomly chosen t (0,.... M - 1).
end
Proof. The proof is given Appendix
This theorem shows that during early epochs approximation of mean-path update good enough to guarantee geometric convergence. However, the batch size used for approximation increases geometrically with each epoch with rate p², where p is a desired convergence rate, until it reaches size of the dataset N. The constant C' depends parameter and upper bound 2 = maxa(10- where the max is taken over all parameter vectors seen during the run of the algorithm.
SECOND MAIN RESULT: ONLINE IID SAMPLING FROM THE MDP
In this section we apply TD learning as gradient splitting analysis to the case of online i.i.d sampling from the MDP each time need to generate new state We show that this view of TD learning as gradient splitting might be applied in this case to derive tighter convergence bounds. One issue of TD-SVRG in i...d. setting is that mean-path update may not be computed directly. However, this issue might be addressed with sampling technique introduced in Section 5 which makes i.i.d. case very similar to TD-SVRG with non-exact mean-path computation in finite samples case.
In this setting, geometric convergence is clearly not attainable with variance reduction, which always relies on a pass through the entire dataset. Since here there is no data set, and one samples from the MDP at every step, one clearly cannot make pass through all states of the MDP (or, rather, this is unrealistic to do practice). To obtain convergence, one needs to take increasing batch sizes. Our next theorem does so, while improving the scaling with condition number from quadratic to linear.
with only difference that states s' are being sampled from the MDP instead of the dataset D. Formal definition of Algorithm 3 might be found section
TD-SVRG algorithm for iid sampling case very similar to Algorithm 2
Theorem 3. Suppose Assumptions hold, then if learning rate chosen as 1) 1/8, number of
inner loop iterations M = 16/ Xmin and batch size P'm = 2g (2)mmarl + 81101 where is some arbitrary chosen constant, Algorithm will have a convergence rate of:
E(((mm)) & p ()(0)) + C),
where p (0,1) 1) is convergence rate and C is some constant.
Proof. The proof is given in Appendix F
To parse this, observe that as in 5 each epoch requires n. computations to estimate mean-path update and 16/Amin to perform inner loop iterations. Thus, as epoch number grows, nem will
7

---

Under review as a conference paper at ICLR 2023
dominate 16/ Ammi which results in the total computational complexity of ( 2 ) log( )), which is better than (
Amin x-_ (b))))) shown by Xu et al. (2020) when Amin > E.
min
In practice, Amn is determined by the MDP and the feature matrix, while e is desired accuracy, thus, the former is given and the latter might be chosen. In most scenarios, Amin is a small number and is chosen such that Amin Even if this is not case, X is very small number and most likely c < Ami Thus, in the absolute majority of cases results shown in this paper are stronger.
The same convergence result with predetermined constant learning rate cannot be derived for Marko- vian sampling case, in which update sampling strategy is different from one in classical SVRG sampling. However, gradients splitting interpretation of TD learning still allows to achieve better convergence guarantees than in previous works for the absolute majority of problems. Algorithm, discussion and convergence proof is provided in Appendix Section G
7
EXPERIMENTS
MDP,F
Acrobot,
CartPole,
Mountain carr
10
10"1
10"
logif)
10"4
logif)
logif)
logif)
501
10
2/RG
SVRG 1D-Seent
SVRG 1D-Lxppt1)
3/10
20
T>-bsertt
C200
G702
10
RD 9VRG
PD SUBS
SURS
23 DVRG
00
25
15
id's
52.5
10
15
11
Number of passes
Number of pesses
Number of passes
Number of passes
MDP, norm
Acrobot, norm
CartPole, norm
Mountain car, norm
log(norm
log(norm)
10P
(og(nor)
10
(gg(norm)
10
10
10-
10-1
10
9VRG
SVRG
S/R [0-1/yyti)
3/R5
DDJiann
Lisant
10-
10
10-2X
ID-0VRG
10 FD-SING
10
FD-SVRG
10" PO-SVRG
25
15
10.
20
16
is Number passes
Number of passes
Number of passes
Number passes
Figure 1: Average performance of different algorithms in finite sample case. source environments: MDP, Acrobot, CartPole and Mountain Car. Rows performance measure- ments: (f)) and log(10 1*)..
Columns dataset
7.1 ALGORITHMS COMPARISON
In this set of experiments compare the performance of TD-SVRG with GTD2 et al. (2009) Vanilla TD learning Sutton 1988) and PD SVRG et al. (2017) in finite sample setting. Generally, experiment set-up similar to Peng al. (2019). Datasets of size 5000 are generated from environments: Random MDP Dann et al. (2014) and Acrobot, CartPole and Mountain car OpenAI Gym environments Brockman et al. (2116) For Random MDP, we construct MDP environment with [S| 400, 21, features and 10 actions, with actions choice probabilities generated from U(O. 1). For OpenAI gym environments, agent select states uniformly at random. Features constructed by applying RBF kernels to original states and then removing highly correlated features (correlation coefficient > 0.5). To produce datasets similar sizes we resampled dataset if smallest eigen-value of its matrix A was outside the interval [0.32, 0.54] 10-4, which corresponds to TD-SVRG batch sizes between 30000 and 50000. Decay rate 7 is set to 0.95.
Hyperparameters for algorithms selected as follows: for TD-SVRG theoretically justified parameters are selected, learning rate = 1/8 and number of inner loop computations M = 16/> /mman for GTD2 used parameters which are suggested for small problems a and 3 = 1. For vanilla TD decreasing learning rates are set to a = 1/vt and a = 1/t. For PD-SVRG setting parameters to theoretically suggested is not feasible, since even for simple problems values of number of inner
8

---

Under review as a conference paper at ICLR 2023
Following original paper Du et al. (2017) we run a simple grid search are pick best performing values, which are dg dw 0.1/ 0.1/2max Xmax (C). Results presented on Figure Each algorithm for each setting was run 10 times, average result is presented. As theory predicts, TD-SVRG and PD-SVRG converge geometrically, while GTD and vanilla TD converge sub linearly.
loop computations M is too large (see Appendix Subsection H.Ip
7.2
ONLINE IID SAMPLING FROM THE MDP
MDP,
MDP, norm
log leg(norm)
logi()
1D-deer
Tidderr WID
WITD
coret
100 100
140
160
Number batches size 4000
Number batches size 4000
Average performance of TD-SVRG, VRTD and vanilla TD in iid. sampling case. "TD- decr" refers to vanilla TD with decrasing learning rate, "TD-const" to vanilla TD with constant learning rate. Left figure performance in terms of (()), right in terms of log( (*1).
Figure 2:
In this of experiments we compare the performance of TD-SVRG, VRTD and three Vanilla TD with fixed and decreasing learning rates in i.i.d. sampling case. States and rewards are sampled from the same MDP as in Section 7.1 Hyperparameters are chosen as follows: for TD-SVRG learning rate 7 1/8, number of inner loop computations M 16/Amin- VRTD learning rate and batch size M = 2000. For vanilla TD with constant learning rate its value set to 0.1 and for decreasing learning rate it is 1/t, where is number of performed update. Average results over 10 runs presented on Figure 2
0.1
7.3 REPRODUCIBILITY
Authors provide [link to anonynous github repository with code and instruction how reproduce the experiments.
CONCLUSION
In the paper we utilize a view on TD learning as splitting of gradient descent to show that SVRG technique applied to TD updates attain similar convergence rate SVRG in convex function set- ting. Our analysis addresses both finite sample and i.i.d. sampling cases, which previously were analyzed separately, and improves state of the art bounds in both cases. In addition we show that gradient splitting interpretation helps to improve convergence guarantees in Markovian sampling case. The algorithms based on analysis have fixed learning and small number of inner loop computation, easy to implement and demonstrates good performance during experiments.
REFERENCES
Reza Babanezhad, Mohamed Osama Ahmed, Alim Virani, Mark Schmidt, Jakub Konečný, and Scott Sallinen. Stop wasting my gradients: Practical svrg, 2015.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. finite time analysis of temporal difference learning with linear function approximation. CoRR, abs/1806..n 006.02450, 2018.

---

Under review as a conference paper at ICLR 2023
Greg Brockman, Vicki Cheung. Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv:1606.0154., 2016.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for td(0) with function approximation. Proceedings the AAAI Conference Artificial Intelligence, 32(1), Apr. 2018.
Christoph Dann, Gerhard Neumann, Jan Peters, et al. Policy evaluation with temporal differences: A survey and comparison. Journal of Machine Learning Research, 15:809-883, 2014.
Aaron Defazio, Francis Bach, and Simon Lacoste-Julien. Saga: A fast incremental gradient method with support for non-strongly convex composite objectives, 2014.
Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduc- tion methods for policy evaluation. CoRR, abs/1702,,7944, 2017.
Rie Johnson and Tong Zhang. Accelerating stochastic gradient descent using predictive variance reduction. In C.J. Burges, L. Bottou, M. Welling, Z. Ghahramani, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 26. Curran Associates, Inc., 2013.
Nathaniel Korda and Prashanth La. On td(O) with function approximation: Concentration bounds and a centered variant with exponential convergence. In Proceedings of the 32nd International Conference on Machine Learning (ICML). pp. 626-634, 2015.
Rui Liu and Alex Olshevsky. Jbs/2010.14667, 2020.
Temporal difference learning as gradient splitting.
CoRR,
C Narayanan and Csaba Szepesvári. Finite time bounds for temporal difference learning with func- tion approximation: Problems with some "state-of-the -hate-oftthh-at"" results. Technical report, Technical report, 2017.
Zilun Peng, Ahmed Touati, Pascal Vincent, and Doina Precup. SVRG for policy evaluation with fewer gradient evaluations. CoRR, abs/1990.00374, 2019.
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathemati- cal statistics, pp. 400-407, 1951.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient, 2013.
R. Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation and TD learn- ing. CORR, abs/1902.00023,, 2019.
Richard Sutton. Learning predict by the methods of temporal differences. Mach Learn, 3, 1988.
Richard S Sutton, Hamid Reza Maei, Doina Precup, Shalabh Bhatnagar, David Silver, Csaba Szepesvári, and Eric Wiewiora. Fast gradient-descent methods for temporal-difference learning with linear function approximation. Proceedings of the 26th annual international conference machine learning, pp. 913-99930000 2009.
Ahmed Touati, Pierre-Lut Bacon, Doina Precup, and Pascal Vincent. Convergent tree backup and re- trace with function approximation. In International Conference on Machine Learning, pp. 4955- 4964. PMLR, 2018
J.N. Tsitsiklis and B. Van Roy. An analysis of temporal-difference learning with function approxi- mation. IEEE Transactions on Automatic Control, 42(5))674-668 690, 1997. doi: 10.1109/9.588744
Tengyu Xu, Zhe Wang, Yi Zhou, and Yingbin Liang. Reanalysis of variance reduced temporal difference learning. CoRR, abs/2001 .01898, 2020.
10

---

Under review as a conference paper at ICLR 2023
A PROOF OF LEMMA 1
The proof follows the same logic as in Johnson & Zhang (2013) and organized in four steps. Step A.1. In the original paper proof starts with deriving bound on the squared norm of the difference between current and optimal sets of parameters. Since the introduction of w(() this step in our proof is trivial.
(l0, 9s =w(())
Step A.2. During Step we derive a bound on the norm of an single iteration update Vt (s, (0--)
+ g(0), assuming that states 8, were sampled randomly during step
F.s [ree(11
Fll l (0.- - 3 (0) + 0()]1
= Es (99,0' (0 (0-1) ( 00)) + (ge,e(0*)) g0. (0)+
$ 2 (0s, (6:-1) s (0* ]112
1lg,,r 0 (0*) (Ø(0) 1112
= 2 110. - S (0*))) ||[2 + 2 0 (0) - g (8*)
Ea Fg. yr.0 (0*)
< 2.E,, (0:-1) 90.5 (0* ||1 + 2 11
/ (0) g (0*) )|
2wo(O=1) + 2w
The first inequality uses BlIa + b112 < 2|||a||2 + 2| The second inequality uses the face that second central moment is smaller than second moment. The last equality uses the equality from step
Step A.3. During this step derive bound on the expected squared norm of distance optimal parameter vector after a single update l:
110, 08112= = Ee,e' (0,.:110:11 - 0* + npell
|10c-1 - 8011² + (y(6t-1- - 8*) Eur + 1ee1
< |10=11 1 0º1|2= + 2n(0,-1 0* 0*)g(0,-1) -1 + 2nj² w/ (0000)) + 2n²"
|10:-1 101 2nf(0.-1) + 21/ (0t-1) + 2ny² (()
The inequality uses the bound obtained in step 2. After rearranging terms it becomes:
0 0012
-
< 110,11 0012 w0)
Step A.4. During this step we sum the inequality obtained in Step 3 over the epoch and take expec- tations with respect all choices of pair of states s' and all previous history and use the random choice property to obtain Equation which relates parameter vectors of two consecutive epochs:
Σ
EE 0
00112 + Σ 2nEf(0
Σ
2n Ew (0.1) & Σ 1110--1-001
Σ 2m Ew(() 1-1
We analyze this expression term-wise.
DM 1 0* 011 and E. El - 001 consist of same lerms, except the first term in the first sum and the last term in the last sum, which are El| and 2 -0000=00*11 is always positive and it is on the left hand side of the inequality, we could drop it.
Since El|0 8*
We denote the parameter vector chosen for epoch parameters the end of the epoch 8m Since this vector is chosen uniformly at random among all iteration vectors O,, MM1 (0( = ME
and EM Ew((0-)) MMEuv(())))
11

---

Under review as a conference paper at ICLR 2023
At the same time, 0, which was chosen in the end of the previous epoch remains the same throughout the epoch, therefore, Li= Ear(O) ME)x((). Note, that current epoch starts with setting On 0. Also, to underline it is previous epoch, we denote as 0m-1-
Plugging this values in we have 3
2n 2M1r"uu(Om)) 11 18 2nj MEW (6m-1)
B PROOF OF PROPOSITION 1
To transform incquality from Lemma into convergence rate guarantee, we need to bound w((
and f(0) in terms of |0 08 Both bounds are easy to show:
(0) E,, |0,,0' (0) 90. - (6*)
(0 8*) E, (()(s')) o(s=))))(( -(s)) 8*)
(0 8*) J E.,, [1(()((s)) d(s)) [((()) -
[[o(s)] [1(7p())) ((s))[I[( 8*)
4 0º1
f(0) (0 8*) Es ( > 8*) > Ammn 88112.
Plugging these bounds into Equation 3 we have:
(2 Aminn 8.,,))] - 08112 8M1 0* 08112.
Which yields epoch to epoch convergence rate of:
8M12
2 1.
For this expression to be < 1, we need that nM to be (11/Amsn), which means that r needs to be
O ((mmin) for Mr² to be O(1). Therefore, M need to be 01//2 Setting r Amin/33 and 32/ X yields convergence rate of 5/7.
C PROOF OF THEOREM
The same in the previous section, start with deriving bounds, but this time bound ||e - 1+1 and w(() in terms of f()). First bound straightforward:
1 f(0).
f(0) (0 00) 1o00 0*)
110
8+1|2 <
Amin
For un( we have:
12

---

Under review as a conference paper at ICLR 2023
w( = (0 - E. o() (0 -(6)) 09)
(0 8*) 7
1
Σ
- 8r)
-(s))
S
< (0 8*) |
Σ
d())
N
(4)
(0 8 I
Σ
" (00))))"~0(())660))00 70(5) 00 f())
S,8'ED
-0- 0 0
Σ
- -000)))0000))
2f(())
first inequality uses Assumption third equality uses Assumption ? (
Σ, d)))))())) since and s' are the same set of states). The last inequality uses the fact that 711.
Plugging these bound into Equation 3 have:
2n..)((mm) 4M1 &
Ef(0m-1) + MB
Amin
which yields epoch to epoch convergence rate of:
2n
Ef(@m) & AAminnM(( 2n)
Bf(0m-1).
1 - 2m
Setting y and
Aman we have the desired inequality.
D CONVERGENCE ANALYSIS WITHOUT DATASET BALANCE
In this section show the convergence bound for the problem without Assumption In this case, the problem that after the sampling, 8 and s' in the dataset does not have the same distribution, i.e., the first element of the tuples (st, at, Tr. 8r+1) in our dataset need have the same distribution as the last element of this tuple. Indeed, it could happen that a particular state occurs different numbers of times the first element of the tuples in as compared the last element, which would not happen under Assumption 3 When this happens, we will say that the data set is unbalanced. In that case, g(6) need not be gradient splitting of function f(0).
One might hope that, when the size of the data set N is large, this effect has an impact which decays to zero with N. Our second main result shows something even stronger: we show that the effect of unbalacedness disappears completely for large N. Thus our next theorem completely recovers the performance attained by Theorem for large N. The catch the size of the dataset has to be at least as big as > for this to happen.
Theorem 4. Suppose Assumptions
2 hold and dataset is unbalanced. Define error term J Then, if we choose learning rate 7 = 1/(8 + J) and number of inner loop iterations M = 2/(mmn))) Algorithm 1 will have a convergence rate of:
4-2
(2) m f(0o).
E\((Om))
Proof. The proof is given in Appendix D.I
Note, that in this case 7 O max max (1. Amiin.))))) Amin parameters required to guarantee convergence of 00 (Proposition) Note that the guarantees
and O Amin which always better than
of this theorem are identical to the guarantees of Theorem in the unbalanced case when N > X-1
13

---

Under review as a conference paper at ICLR 2023
D.1 PROOF OF THEOREM 4
To proof the theorem we follow the same strategy as in C For the ((0) we can use the same bound:
((0) (0 E 10(0 -00 = - -0112 & Amin
S(0)
Bound for w()) is little bit more difficult:
1
( (0 1
Σ (70(8) o(s)) -(0) 0*)
N
s,S'ED
(0
I'1
Σ
(70(8))
6()) 0*)
N
s,s'ED
(0
I
Σ 70(5)(70(5)) - (()(((((s)) (()) 0*)
s,a'DD
(0
I
Σ ('(()))(()
70(5))(s)7] 0*) f(0)
s,S'DD
(0 I
Σ (s)))(()) 7 -0) (())
s,s'DD
12 N (0 0*) 0*) ((((==))))((N=) ((=)))(s)""(0-007))
< 2f) + - -0-
-(s))))())( 06 0z)
The first inequality follows from the assumption about norms of feature vectors. The third equality obtained by adding and subtracting =0 (**()(())))))))))))(((())))) ((00)) 0*). Second inequality uses the fact that 72 < We denote maximum eigen-value of matrix ((*N+1)((SN+1) -(s)))((s))" as K. (note that K. & 1). Thus,
PC N
T2K
(0) < 25(0)
0 0+1|2 (2
NA
N NAmin
Plugging these bounds into Equation
we have:
7² NAmin
(2n (2 NA
(0m)) $
+ 2 M(2
)))
Amin
Which yields convergence rate of:
1
17(2 + NAmin
Amin 21 - 17(2 + NAm
1)2 + NAmen
To achieve constant convergence rate, for example 3. we set up 77 such that 17(2 + Nomee 0.25, thus the second term is equal to 1/3 and
x²)
Then, to make the first term equal to 1/3,
xXmin
we need to set
2
2
M
Amin
Amin 472 NAmen
Thus, 77 is scale of
Iax((11/(NAA... Amiin) and M is scale of Amin Nin(I,NAmss
14

---

Under review as a conference paper at ICLR 2023
E PROOF OF THEOREM 3
In the first part of the proof we derive an inequality which relates model parameters of two consec- utive epochs similar what achieved in previous proofs, but with error term. In this part of the proof we follow the same 4 steps logic as while proof of Lemma In the second part of the proof show that there are conditions under which error term converges to O.
Step E.1. During the first step we use the bound obtained in inequality
w(0) < 2f(0)
Step E.2. During this step we derive bound on the squared norm of a single update E[[lva] But now, compared previous case, we do not compute the exact mean-path updated g(0), but its estimate, and assume our computation has error g(0) + e. Thus the single update vector will be
1t = 9 g(0) + g(0) + t
Thus, the bound on the single update might be derived as:
E
|| Bl(g(0(-1) 9(0) 9(0) 0(0) ell
El(((((--1) g(0*)) (0(0*) ((0) 5(0) e)l
2E][(g(0:-1) =(0*))[²+2Bl(((00))))))) -)(()) - (g(0) - g(0)) e|1
2E]((((f--1) ((0)))]²+2B(((0) - - Elg(O) o(0*)) ) - cl12
2E]1(((0:-1) ( -(8*)) - Elg(O)
(0*)
2R(g(0) - g(0*) 4F - -(0))),,) + |||2
< 2 o(0*))]1 (Bllg(0) g(0*)) )1 eel
-2w(0,11) + 2w) + |||2
< <f(00_1)) (0) + e||
where first inequality uses E||A- + B1F & 2| + 2E
second inequality uses EEI
B[A]]| & A|] and the third inequality uses the result of Step E.
Step E.3. During this step, we derive a bound on a vector norm after a single update:
E| - 1|2 = El - 0* + (-mue)l12
= 1 1º112 - 2n) " + u||
& 10 0²112 2n(0,-1 8*) (((-1) + 4n f f(0(-1) 4n' + 2n7
110-1 0²112 2n -*)((((((-1) (0 Te
+ ((0-1)) + 4n7 (()) + 2///1||e||
Rearranging terms we obtain:
E| 0 - 112 2n (0,-1) - -17 ((0r)
|10 11 2n f(0) 2n(0,-1 0 e 2n E|lll
|1 1= + f()) 2n|10,_1 g*ll ||ell + E|eel
Step E.4. Now derive a bound on epoch update. We assume that quantity || - 8011 might be bounded by constant Z. Similarly, we denote ervor term from previous epoch e We use the similar logic as during the proof of theorem 1. Since error term doesn' 't change over the epoch, thus, summing the epoch have:
15

---

Under review as a conference paper at ICLR 2023
B m 0 1 2nME)((mm) 8n)² ME)((mm)
E 00 - 8* 1|2 + 8n) ME ( + 2Mn 21j MEI
Rearranging terms we have the bound:
+ 4n (Bf
(fm) & 2min2n 4n)
(0mml) 1)+ 1 4n
[ZE) c00 + :BBBee m-1 11²)
1 4n
To obtain convergence, we need to guarantee geometric convergence of first and second term in the sum separately. The first term is dependent on inner loop updates, its convergence is analyzed in Theorem 1. Here we show how to achieve similar geometric convergence rate of the second term. Since error term has 0 mean and it is finite sample case with replacement, expected squared norm might be bounded by:
N 7m 5 & &
S 7m
S
E||e-113<
(1
Nnm
N
7m
where S2 is bound update vector variance. If want the to be bounded by cpam. we need the number of batch computations nmm to satisfy the condition:
S2
Thy
cp2m
Satisfying this condition guarantees that the second term has geometric convergence:
2
(ZEl m- 111 + 1 113)
max( max(Z
4n
1 4nj
is only left to derive bound 22 for on update vector norm sample variance:
N 11g.. (0)1 1
N 1
1
N 11 (0)11=
[1(r(s, + 7 (11s)))-od())0)0(()))) d((s)))
N
1
2||r(())]1 411>"(8')) +11((())
(2) Maaz 7 10 4101) = N (2)r raz 2 8|1012) = S
N
PROOF OF THEOREM 4
TD-SVRG algorithm for iid sampling case described as Algorithm 3
The proof of its convergence is very similar E the only difference is that now we derive expecta- tion with respect to MDP instead of fixed dataset.
16

---

Under review as a conference paper at ICLR 2023
Algorithm 3 TD-SVRC for iid sampling case Parameters update frequency M and learning rate 7
Initialize Og-
Iterate: for m 2,
0 == 0-0-11
choose batch size Tmm sample batch D of size 1m.
compute μ Pa Σ Le (0),
where 9s.8' (0) = (r(s, (' o(s)²
Bu 0.
Iterate: for = 1,2..... .M1
Randomly sample 8, s and compute update vector
U/ (0,-1) 0 (0) μ..
Update parameters 0g = 01-1 TpUp.
end
set 6m 0, for randomly chosen t (O...., M - 1).
end
Step F.I.
During the first step we use the bound obtained during the proof of theorem 1:
w = (0 E. 11
(0 o ((s)) 0*)
(0 0+ Σ u. - -(s)) 0*)
(5)
(0 0t ) ( "o(p)))"""-((())))))())))))) 0*) + f(0)
(0 0²)
0*) + ((0)
2f(()),
first inequality uses Assumption 2 third equality uses the fact that por is stationary distribution of P ( d')((s) (0(6")(( last inequality uses the fact that y <
E. (5)))(( E [_Hx(()))P(())000)) The
Step F.2. During this step we derive a bound on the squared norm of a single update E Similarly with E we assume inexact computation of meth update g(()) + Thus the single update vector becomes:
g(0.-1) g(0) + 5(0) +
Norm of this vector is bounded by:
17

---

Under review as a conference paper at ICLR 2023
E 1 Bl1g(0,-1) 9(0) + σ + e|l²
B)((((0,-1) -(00)) ( (0()))(((0)-)())))) -(0)) e]l
2B]1(g(0:-1) =(0)))][=2((((()) g(0)) (0() 0(0))) el1
2E]1(((0--1) g(0*))][+2Bll((0)) -0(*)) - Elg(O) 9(0*) - c||²
28]1(g(0.-1) =(0*)))²+EE((((0)) -000) - F(a(O) 2(0 ]11
2E(g(0) - g(0*) -EE(g())- g00)), 2
$ 2E a(0*))11 ( |(0 e||2
-2w(0-11) + 2w( + 2||
4f(00-1)) (f) + 2
where first inequality uses E + B1F 2B|| + B second inequality uses IE|
B|A]|| & |||A|| and the third inequality uses the result of Step F.1
Step F.3. Bound on a vector norm after single update:
E - 011 B| 1-1 - 0t + (-12
= 1 0²1 - 2n(0, (0,- 0+) ) Eur + 1
< 110-1 0+1 0º112 - 2n(0,-1 TT) g(0(-1) + 4n² f(00-1) + 4n2 f(0) + 27/
110-11 0$112 2n(0,-1 V 20(00-1 8
f(6--)) + 4n²² f(0) + E||el
Rearranging terms we obtain:
B|10: 0*1 2n (0 4172
110-1 0-1|2 0 f(0) 2n(0,-1 - 0 e 217 El|l1
|10--1 1= + 4n/ 5(0) 20|10,-1 0*1| -|ellell 2n B||e||
Step F.4. Now derive a bound epoch update. We assume that quantity ||0,-1 0 might be bounded by constant Z. Similarly, we denote an error term from previous epoch as m- We use the similar logic as during the proof of Theorem 1. Since error term doesn't It change over the epoch, thus, summing over the epoch we have:
E| E|0mm mm - 1-112 (7).)((m) - ME) & + 2n MB]
El 101 8n7 ME) +
Rearranging terms we have the bound:
4n
(0m) & Amin2nM(1 4n) + 1- 4n
(ZE m 111 r/Bllee m-
1 4n
Similarly to convergeee for the first term might be obtained by setting learning rate r7 = 1/8 and number of inner loop iterations M 16/2 Amin- To guarantee convergence of the second term, need to bound "l [|2. In the infinite population with replacement case norm of the error vector is bounded by:
S2 nm
E 1|
18

---

Under review as a conference paper at ICLR 2023
where S² is bound update vector variance. If want the error to be bounded by cp cm need the number of batch computations 7mm to satisfy the condition:
S
Rym
cp2m
Satisfying this condition guarantees that the second term has geometric convergence:
2
[Z
11 + n) 1 113)
max(2./c, ppp)p"
1 4n
1- 4nj
Similarly bound on sample variance 5 might be derived as follows:
Mn (s) st (0)11 110
(r(s) 119 (0)1 Σ s3)()((ss)) (
5.8
4 41) 00(s)]13) (6(3)) <
(2 mmax 2 + + + 4 0 = (2) maz 0| = Sa
G MARKOVIAN SAMPLING CASE ALGORITHM AND ANALYSIS.
Markovian sampling case is the hardest to analyse due to its dependence on MDP properties, which makes establishing bounds various quantities used during the proof much harder. Applying gradient splitting view helps to improve over existing bounds but derived algorithm does not have nice property of constant learning rate. To deal with sample-to-sample dependencies with utilize one more assumption often used in the literature:
Assumption 4. The considered MDP irreducible and aperiodic and there exist constant m and p (0,1) such that
sup drp 1180 =), & mpp, VL 0, SES
where (Tv(P, Q) denotes the total-variatio distance between the probability measures and Q.
Another thing we need employ is projection, which will help set a bound on update vector v. Following Bhandari et al. (2018) and Xu et al. (2020) after each iteration we project parameter vector on ball or radius (denoted as (+)
0' We assume that |@ & R, choice of R which guarantees might be found in Bhandari et 2018). Section 8.2. Adding
arg minggreer
projection results in Algorithm 4
Guarantees of convergence of Algorithm are given in Theorem 5
Theorem 5. Suppose Assumptions
hold, then output of Algorithm Awill satisfy:
SC
Elf( = (2) f(0)) Amiin Pum
+ 4n miz (n)) 9RR*
where C' = 4(1 4(1-(m-1)o) (4R2 + -
Proof. The proof is given in Appendix G.I
Theorem iimples that if we choose = (log(I/e)), n. = ((1/(Amin)) and n Ole/ log( 1/e) and M O log(1/e)), total sample complexity to achieve accuracy of is:
AAmin
19

---

Under review as a conference paper at ICLR 2023
Algorithm 4 TD-SVRG with batching for Markovian sampling case
Parameters update frequency M, learning rate 77, projection radius R and batch size 7.m
Initialize Og-
Iterate: for m 1,
0 = 0
sample trajectory D of length Rmm.
compute μ 1 Ex. (8), where e (0) = (r(s, s') - ()s))
Ou = 0.
Iterate: for 1, ..... .M
Randomly sample s, s' and compute update vector
Up 0 (0,-1) ) gs.s" (0) + n.,
Update parameters 0g I mu2)-
end
set 0m O. for randomly chosen & (O,..., M 1).
end
0 log (1/c)
EAmin
In the most practical application his result better than for practical values of e and Amin.
O
log(1/e)), since log(1/e)/Amin)
G.1 PROOF OF THEOREM 5
In the Markovian sampling case, we cannot simply apply Lemma I due to high estimation bias the bounds on f()) and w0) will not be derived based current value of 0, but based on global constraints on the updates guaranteed by applying projection.
First, we analyse single iteration step t of epoch m, during which we apply the update vector Vt g)) gr (0) + nl ()) The update takes the form:
F 113 E: 12 + mpr) 1z
(0000))1 112 & E110, 0* + (-
|00 1 00113 2n)(0:11 / F(oo + 110011
(6)
10:- - 0*113 + 2n(0,-1 - 0*) (0. Lgg. (0) + p()))+
1/² E 11
where the expectation is taken with respect to s, sampled during iteration t. Recall that under Markovian sampling, [[gg((0.1)) * g(0--1) and that for the expectation of the estimated mean- g(0), where 8m-1 is the last state of epoch
path update we have [m]]]] tackle this issue, we follow the approach introduced in a previous works (Bhandari et (2018). [u of mean-path update and error terms. Similar Bhandari et al. (2018), we denote the eтror term on single update as Ç:
1. To
et al. 20200) and rewrite the expectation
(6) (0 a 7 (0) g(0))-
For error term on the trajectory we follow Xu et al. (2000) and denote it as &:
Sm (0) (0 ) (m((0) g(0)).
Applying this notation, 6 can be rewritten as:
El00
8* 1/113
16,- 11+
(n, - O+h²" (B[g-- -(nn +1())((0))))))))))())(())))))))) + 1² Ellual1
||0.-1 0²1 + (E[(((((())-))) (0,-1 0z g(=0( -))-
(E] -(0--1 (*)
(E][(()) -00-1 ( )2²")()))++")))))))))) E
20

---

Under review as a conference paper at ICLR 2023
Error terms can be bounded by slightly modified lemmas from the original papers. For ((0),
apply a bound from Lemma 11 Bhandari et al. (2018):
[[]{(0)]] (4 6r (n))
In the original lemma, a bound on E[(( is stated, however, in the proof bound on absolute value of the expectation is also derived.
For mean-patee path estimation eтror term, we use a modified version of Lemma 1 in Xu et al. (0200)
The proof of this lemma in the original paper starts by applying the inequality
a Σ 2
||a||
|b|1 2k
the expression (0 - For the purposes of our proof we use
( (())). with k Aa/2 (using the notation in Xu et al. (220
Amin- Thus, we will have the expression:
Amin
4(1 (m 1)p)
BlEm (0))
B
0-1 5mm +
[4R + maxd
2
Amin (1 p)
Amin
B[ 0 8m
2
A 1m
Also, note, that the term E 22 might be bounded as El/u,113 & 18R2. Plugging 8 and bounds into 7 we obtain:
B110, 111 < 0 - 1313 20,((,-1)
4n) min (n))+
2n(( Amin
110 0" 112 Amin
C c 181 R?.
Summing the inequality over the epoch and taking expectation with respect to all previous history, we have:
2TME < Ō10 0 2
Amiu 110_-1 0
-
2
Amin
17 M 6r 6r mn)) + 1812)..
Then we divide both sides by 2n and use 110-11 - 031 E 1/Amin (0 to obtain:
1
C
E[f(O.)] < 2M 2 f Amin
(22 (4 mix (n)) +
We choose 7) and M such that n 7yMAmin 2. We then apply this inequality to the value of the function f in the first term in the right-hand side recursively, which yields the desired result:
8Co
E[ & ((O)) + Aminn
+ 4n mir (m)) + 9R²)
H DETAILS ON ALGORITHM IMPLEMENTATION
H.1 COMPARISON OF THEORETIC BATCH SIZES
In this subsection we compare the values of batch sizes which are theoretically required to guarantee convergence. We compare batch sizes of three algorithms: TD-SVRG, PDSVRG (Du et al. (207)) and VRTD (Xu al. (2020). Note that PDSVRG and VRTD are algorithms for different settings, but for TD-SVRG the batch size value is the same: 16/Aminn thus, we compare two algorithms in the same table. We compare the batch sizes required by algorithm for three MDPs: first with 50 state, 20 action and states, 20 actions and y = 0.99, with actions choice probabilities generated from U[0, 1). (similar to used for experiments in Subsections 7.1 and 7.2h. Since batch size is dependent smallest eigenvalue of the matrix A, which 1s, in turn, Is dependent on the dimensionality of the feature vector, do the comparison for different feature vector sizes: 5, 10, 20 and 40 randomly
0.8, second with 400 state, 10 actions and
0.95, third with 1000
the
21

---

Under review as a conference paper at ICLR 2023
generated features constant feature for each state. We generate 10 datasets and environments for each feature size. Our results are summarized in tables and
Table 2: Comparison of theory suggested batch sizes for MDP with 50 states, 20 actions and y = 0.8. Values in the first row feature vectors dimensionality. Value in other rows: bitch size of corresponded method (row 1). Values are average over 10 generated datasets and environments.
Method/Features
11
21
41
TD-SVRG
2339
6808
21553
4.51 10
PD SVRG
1.52 10
3.09 10
1.85
1023
1.41 10
VRTD
3.07 106
2.13 107
3.79 10
165 10
Table 3: Comparison of theory suggested batch sizes for MDP with 400 states, 10 actions and 0.95. Values in the first row are feature vectors dimensionality. Value in other rows: bitch size of corresponded method (row 1). Values are average over 10 generated datasets and environments.
Method/Features
11
41
TD-SVRG
3176
6942
18100
54688
PD SVRG
1.72 10
3.83
10
3.06
1021
5.77
1024
VRTD
5.41 106
2.53
107
1.63
10
1.58
109
Table 4: Comparison of theory suggested batch sizes for MDP with 1000 states, 20 actions and 7 0.99. Values in the first row feature vectors dimensionality. Value in other rows: bitch size of corresponded method (row 1). Values are average over 10 generated datasets and environments.
Method/Features
11
21
41
TD-SVRG
9206
16096
32723
79401
PD SVRG
7.38 18
9.64 20
5.14
1023
4.97
20
VRTD
4.35 10?
1.34 10
5.44 108
1.45 109
H.2 BATCHED SVRG PERFORMANCE
In this set of experiments we compare the performance of TD-SVRG and batched TD-SVRG in sample case. We generate datasets of size 50000 from the similar MDP as in Section 7.1 Algorithms also with the same hyperparameters. Average results 10 runs presented on Figure 3 and show, that batched TD-SVRG saves a lot computations during the earlier epochs, which provides faster convergence.
22

---

Under review as a conference paper at ICLR 2023
MDP,
10
log(norm)
1071
logif)
1077
10"1
1013
10a
passes
Number passes
Figure 3: Average performance of TD-SVRG and batching TD-SVRG in finite sample case. Datasets sampled from MDP environments. Left figure performance in terms of log(f(0)). Right figure performance in terms of log( - l*1).
23


Reviews:
[{"review_id": "PDMAp1AjJK", "reviewer": "Reviewer_pncF", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper studies the Temporal difference (TD) learning method for policy evaluation in reinforcement learning. The proposed approach TD-SVRG method is a variant of the TD method by introducing the well-known SVRG technique. Theoretically, their analysis can lead to better convergence bounds for previous methods. Numerical results validate the improved performance of the proposed method over the existing methods.", "summary_of_the_review": "This paper proposes a variant of the TD method with a faster convergence by introducing the well-known SVRG technique. The novelty and the improvements are limited.\n\n------Update------\n\nI have read the author's response and would like to keep the score.", "strength_and_weaknesses": "Strengths:\n\n1: This paper proposes a variant of the TD method with a faster convergence by introducing the well-known SVRG technique.\n\n2: Extensive experiments are conducted to verify the effectiveness and efficiency of the proposed algorithm.\n\n\nWeaknesses:\n\n1: It is unclear whether the proposed method significantly improves the existing complexity in VRDT. For the overall complexity, which term will dominate the maximization function in theory or in practice? Since the superiority of the proposed method to the VRDT method depends on this, the authors would do well to provide more analysis. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "4H84aqCXQK", "reviewer": "Reviewer_kaRJ", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper develops a reanalysis of TD with SVRG variance reduction and establishes a tight bound that matches the complexity result of SVRG in convex optimization. The developed analysis is simpler than all previous research and leads to better convergence bounds. Moreover, numerical experiments show the advantage of this algorithm over other existing variance-reduced TD algorithms.", "summary_of_the_review": "See above.", "strength_and_weaknesses": "Strength:\n\n-The presentation is clear and easy to follow\n\n-This paper is the first to prove that TD with SVRG can match the complexity result of SVRG in convex optimization.\n\nWeakness:\n\n-Paper writing is poor. There are many grammar issues, incomplete sentences, etc.\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "2qs26TNMc3", "reviewer": "Reviewer_158U", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "The paper uses SVRG to reduce variance in TD learning. The resulting algorithm is analyzed using the gradient splitting perspective on TD learning to prove finite sample convergence rates that match those of SVRG in the setting of convex optimization. The analysis is done for several settings, and the findings are illustrated with experiments on several environments.", "summary_of_the_review": "~~Despite really liking this paper, I must recommend the current version be rejected due to concerns about clarity and the experiments detailed above. If the authors address these concerns satisfactorily and no critical issues are found by the other reviewers, I would recommend acceptance of a revised version.~~ The authors have addressed most of my concerns in their response, except some of my concerns about clarity (making these clarity changes would drastically reduce the work required of each reader to understand the paper). I have increased my score to reflect this.", "strength_and_weaknesses": "**Strengths:**\n1. The analysis uses the gradient splitting approach, which yields a significantly simpler algorithm, analysis, learning rate/step size, and a better convergence rate.\n1. The paper considers several different settings, which increases the number of readers who would be interested.\n1. The paper provides recommendations for setting the learning rate, and actually uses this recommended learning rate in the experiments.\n\n**Potential Weaknesses/Questions:**\n1. Many grammatical errors, including typographic errors (\"TD-leaning\", \"apprxoimate\") and missing words, especially definite and indefinite articles. For example, \"determining *the* expected reward *an* agent will achieve if it chooses *actions* according to *a* stationary policy\". Some grammatical issues are listed below, but there were too many for me to write down all of them.\n1. ~~The paper doesn't comment on the assumptions made other than stating that they are standard. It would be nice to include a sentence or two explaining why the assumptions are reasonable or whether they are just for convenience (like Assumption 2; the feature vectors can always be normalized to make it true).~~\n1. Jumping between the notation used in other papers and the notation used in this paper is difficult. It would be better to convert the results of other papers to the notation used in this paper.\n1. ~~Font size of figures is too small to read without zooming in a lot.~~\n1. I have some concerns about the experiments:\n    1. ~~Why weren't the parameters for each algorithm set using a grid search the way they were for PD-SVRG? Without doing this, it's not clear that the chosen parameters are representative of the performance of each algorithm, and hence no conclusion about the performance of each algorithm can be drawn.~~\n    1. ~~Why was the learning rate for TD set to $1/\\sqrt{t}$? It seems like the algorithm stops learning very quickly due to the learning rate shrinking so quickly. How does the algorithm perform with a learning rate of $1/t$ instead?~~ I realized I was confused about this.\n    1. ~~What were the parameter values checked during the grid search? This would make the experiments more reproducible.~~\n    1. ~~Either confidence intervals or standard error (itself a form of confidence interval, I guess) should be included in the plots to communicate statistical significance to the reader.~~\n    1. Consider using either colourblind-friendly colours in the plots, or replacing the legend with labels for each line to remove the dependence on colour to determine which algorithm is which. Using differently-shaped points for each algorithm is a good start, but when the points are too close together it becomes difficult to tell which algorithm is which.\n    1. ~~What is the threshold for removing highly correlated features? This would help reproducibility.~~\n1. ~~The paper states that TD-SVRG and PD-SVRG converge linearly, but the y-axis of the plots appears to be in log space, which is confusing. Could this be clarified?~~\n1. ~~It would be good to have a concluding section that summarizes the main takeaways of the paper.~~\n\n**Grammatical/typographic issues:**\n1. \"Robbins & Munro (1951)\" should have the authors names inside the parentheses, because they are not being referred to in the sentence. Also, I think the second author's name is spelled \"Monro\".\n1. The \"Korda & LA (2014)\" citation is wrong: the authors are Nathaniel Korda and L.A. Prashanth, and the paper was published at ICML 2015.\n1. \"These methods are collectively known as variance reduction.\" Should this be, \"These methods are collectively known as variance-reduced gradient methods.\"?\n1. \"We analyze this case in 4 and 5\": It's better to write \"Sections 4 and 5\", because otherwise \"4 and 5\" could refer to an equation, appendix, theorem, etc.\n1. In Algorithm 1, should N be M? If not, it would be good to define N explicitly.\n1. \"unbalacedness\"\n1. \"is the the size\"\n1. \"on practice\" should be \"in practice\"\n1. \"envtironments\" in Figure 1.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "0LJ76Op0VhG", "reviewer": "Reviewer_Tp1f", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "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": "", "main_review": "", "summary_of_the_paper": "This paper provides a theoretical convergence proof for TD-learning algorithm with variance reduction structure. The sample complexity can match the complexity of SGD for convex optimization in iid finite-sample and iid online sampling senario. The empirical study furthor verifies the performance improvement from the variance reduction technique.", "summary_of_the_review": "In summary, I will reject this paper because: (1) both algorithm and proof technique are not new; (2) the problem setting is not possible in RL.", "strength_and_weaknesses": "***Strength***\nThis paper improves the sample complexity of an existing convergence result of the VRTD algorithm.\n\n***Weaknesses***\n1. In RL, online learning cannot have iid sampling. It can be a good starting point but the author should consider the Markovian sampling structure as [Xu2019].\n\n[Xu2019] Xu T, Wang Z, Zhou Y, Liang Y. Reanalysis of Variance Reduced Temporal Difference Learning. In International Conference on Learning Representations 2019 Sep 25.\n\n2. The theoretical result only obtains a constant-level complexity improvement. I don't think it fills any gap unless the theoretical lower bound is also provided; TD-learning is not equivalent to SGD in convex optimization. Also, there exists theoretical results showing that variance-reduction technique can make a variant of TD-learning algorithm achieve better complexity than $\\mathcal{O}(\\epsilon^{-1}\\log \\epsilon^{-1})$, see [Ma2020].\n\n[Ma2020] Ma S, Zhou Y, Zou S. Variance-reduced off-policy TDC learning: Non-asymptotic convergence analysis. Advances in Neural Information Processing Systems. 2020;33:14796-806.\n\n3. The gradient splitting method seems unrelated to this paper, even if it is put in the title. To my understanding, it doesn't bring any high-level perspectives to make the reader have a new understanding on TD-learning algorithm; it is just a trick used to derive the bound. Every optimization paper can have a lot of such tricks.   \n ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject