Closing the gap between SVRG and TD-SVRG with Gradient Splitting
Authors: Arsenii Mustafin
Alex Olshevsky
Ioannis Paschalidis
Venue: Accepted by TMLR ()

Abstract: Temporal difference (TD) learning is a policy evaluation in reinforcement learning whose performance can be enhanced by variance reduction methods.
Recently, multiple works have sought to fuse TD learning with Stochastic Variance Reduced Gradient (SVRG) method to achieve a geometric 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. Our main result is a geometric convergence bound with predetermined learning rate of $1/8$, which is identical to the convergence bound available for SVRG in the convex setting. Our theoretical findings are supported by a set of experiments.

Published in Transactions on Machine Learning Research (8/2024)
Closing the gap between SVRG and TD-SVRG with Gradient Splitting
Arsenii Mustafin
aam @bu. edu
Deportment of Computer Science
Boston Universily
Alex Olshevsky
alezols Abu. edu
Department Electrical and Computer Engineering Boston University
Ioannis Ch. Paschalidis
yannisp Obu. edu
Department of Electrical and Computer Engineering Boston University
Reviewed on OpenReview: / opw.r/veeeereeee...emeee net/ forum? id- dizU4fo2
Abstract
Temporal difference (TD) learning is policy evaluation in reinforcement learning whose performance can be enhanced by variance reduction methods. Recently, multiple works have sought to fuse TD learning with Stochastic Variance Reduced Gradient (SVRG) method to achieve a geometric rale of convergence. However, the resulting convergence rate significantly weaker than what is achieved by SVRG in the setting of convex optimization. In this work utilize recent interpretation of TD-lcarning the splitting of the gradient of an appropriately chosen function, thus simplilying the algorithm and fusing TD with SVRG. Our main result is geometric convergence bound with predetermined learning rate of 1/8, which is identical to the convergence bound available for SVRG in the convex setting. Our theoretical findings are supported by a set of experiments.
1 Introduction
Reinforcement learning (RL) a framework for solving sequential decision making environments. Policy evaluation one of those problems, which seeks to determine the expected return an agent achieves if it chooses actions according is popular algorithm with particularly simple form which can be performed in an online setting. TD learning uses the Bellman equation to bootstrap the estimation process and update the value function from each incoming sample or mini-batch. As all RL methods, tabular TD learning suffers from the "curse of dimensionality" when the number of states is large, motivating parametric approximations of the value function.
specific stationary policy. Temporal Difference (TD) learning [Sutton] (1988)
Despite its simple formulation, theoretical analysis of approximate TD learning is subtle. There are a few important milestones in this process, one of which the work in Tsitsiklis & Van Roy (1997), where asymptotic convergence guarantees were established. More recent advances include Bhandari et al. (2018). Srikant & Ying (2019) and Liu & Olshevsky (2021). In particular, Liu & Olshevsky (2021) shows that TD learning might be viewed as an example of gradient splitting, a process analogous to gradient descent.
TD-leaning has an inherent variance problem: the variance of the update does not go to zero as the method converges. This problem also present a class of convex optimization problems where the objective function a sum of functions and Stochastic Grodient Descent (SGD)-type methods are applied Robbins & Monro (1551). Such methods proceed incrementally by sampling single function, mini-batch

---

Published in Transactions on Machine Learning Research (8/2024)
of functions, to use for stochastic gradient evaluations. Variance reduction techniques were developed to address this problem and yield faster convergence, including Stochastic Average Gradient (SAG) (Schmidt let al. 2013), SVRG (Johnson & Zhang 2013) and SAGA (Defazio et al., 2014). Their distinguishing feature is that they converge geometrically.
Previous research has analysed the application variance reduction technique to TD updates two problem settings: (i) pre-sampled trajectory of the Markov Decision Process (MDP) (finite sample), and (ti) when states are sampled directly from the MDP (online sampling). We briefly mention the most relevant works in both veins. In the online sampling setting, the first attempt to adapt variance reduction to TD learning made in Korda& & La (015). Their results were discussed by Dalal et al. (2018) and Narayanan & Szepesvári (2017); Xu et al. (2020) provided further analysis of such approaches and showed geometric convergence for the so-called Variance Reduction Temporal Difference learning ( (VRTD) algorithm for both Markovian
and i.idd sampling: Ma et al. (2020) applics the variance reduction technique to Temporal Difference with Correction. However, both Xu et al. (2020) and Ma et al. (2020) achieve total complexity better than 1/c for the policy evaluation problem, which is not possible in the setting of this paper (see Appendix A for details).
The finite sample setting was analysed in Du et al. 2017 where authors directly applied SVRG and SAGA to a version of policy evaluation by transforming it into an equivalent convex-concave saddle-point problem. Since their algorithm uses two sets of parameters, in this paper we call it Primal-Dual SVRG or PD-SVRG. Their results were improved in Peng et al. (2020) by introducing inexact mean path update calculation (Batched SVRG algorithm).
1.1 Motivation and Contribution
The previous analysis of finite sample settings and both cases of online sampling has demonstrated the geometric convergence of the algorithm. However, this convergence has been established separately with different proof strategies, and several unsatisfying aspects persist. A prominent concern is the high com- plexity in all scenarios: convergence times derived for variance reduction in temporal difference learning not only show a quadratic relationship with the condition number (ratio of largest to smallest eigenvalues of a matrix) but also include additional factors related to the condition number of cortain diagonalizing matricos. Such complexities, especially in the context of ill-conditioned matrices lypical reinforcement learning, lead to prohibitive sample complexities even for straightforward problems. For instance, in a simple Markov Decision Process (MDP) with 400 states and 10 actions, the batch size required to ensure convergence is impractically large using the bounds from previous work, illustrated in Table 2 (sccond and third rows of the table) and further discussed in Appendix J.1
Additionally, there is a qualitative discrepancy in the current results: the current analysis of the SVRG- enhanced TD algorithm requires complexity that is quadratic in terms of the condition number, which does not align with the complexity of classical SVRG in the convex setting with its linear dependency on the condition number. This gap, not addressed by the previous literature, remains an unresolved question.
In this paper we analyze the convergence of SVRG applied to TD (for convenience we call it TD-SVRG) in both finite sample and online sampling cases. Our theoretical results are summarized in Table 1 Our key contributions are:
For the finite sample case, we show that TD-SVRG has the same convergence rate as SVRG in the convex optimization setting. In particular, we replace the quadratic scaling with the condition mumber by linear scaling and remove extraneous factors depending on the diagonalizing matrix. Notably, we use simple, pre-determined learning rate of 1/8 to do this.
For i.id. online sampling, we similarly achieve better rates with simpler analysis. Again, our analysis is the first to show that TD-SVRG has the same convergence rate as SVRG in the convex optimization setting with a predetermined learning rate of 1/8, and a linear rather than quadratic scaling with the condition number. Similar improvement obtained for Markovian sampling.
Our theoretical findings have significant practical implications: Previous analyses for both finite sample and online sampling scenarios require batch sizes so large to be impractical. In contrast.
2

---

Published in Transactions on Machine Learning Research (8/2024)
Table 1: Comparison of algorithmic complexities, where desired expected accuracy, X is a minimum eigenvalue of the matrix A, miin is minimum state probability of the MDP stationary distribution, is discount factor and N is a dataset size. The complexity is reported as the number of samples required to shrink distance function
average by factor of where the distance function is a quadratic of the quantity 0-0", similar to previous works (Du et al.) 2017 Xu et al., 2020 The definitions of other quantities and a table with additional algorithms and details of the comparison might be found in Appendix K
Complexity
Type
Algorithm
Feature case
Tabular case
Finite
PD-SVRG
N Amin C-1
x (CIL
log(t))
N + (1-))=mmi
log( 2
Finite
Our
o
N + Ad
log(t)
N
+ [1 (1- 7-/5mmm
log(
i.i.d.
TD
log(t)
log(t)
x
( (1-))2mmm min
d.
Our
o
log( t
O
(1 TT-io log +
Axc
Markovian
VRTD
log( ))
log(
x
(1- 7) min
Markovian
Our
log (+)
[1 7 Taioe log
log²(t) (t)
Table 2: This table gives the output of formulas from Table 1 on the simplest possible MDP (a random MDP) to show the magnitude the improvement. Specifically, we compare theoretically suggested batch sizes for random MDP with 400 states, 10 actions and y = 0.95. Values the first row indicate the dimensionality of the feature vectors. Values in the other show the batch size required by the corresponding method. Values are averaged over 10 generated datasets and environments.
/eethod/Featurne
11
41
TD-SVRG (ours)
3176
6942
18100
54688
PD-SVRG
1.72 10
3.83
10
3.06
1021
5.77
10
VRTD
5.41 10
2.53
107
1.63
10
1.58
109
our analysis leads to batch-sizes that are implementable in practice. A simple example of random MDPs illustrating this is given in Table 2.
We conducted experimental studies demonstrating that our theorelically derived batch size and learning rate achieve geometric convergence and outperform other algorithms that rely on parameters selected via grid search, as detailed in Section 6 and Appendix [ Specifically, we have re-done carlier experiments from Du et al. (2017) and found that our TD-SVRG method with parameters coming from our theoretical analysis converges much faster than previous best SVRG based algorithm (PD SVRG): on average, it requires 132 times fewer iterations contract by factor of 0.5. Note that this comparison favors previous work due; specifically use parameters from thcorems whereas previous work uses parameters selected by grid search. When we also run our algorithm with parameters chosen via grid search this disparity increases to 180 times.
To summarize, in every setting our key contribution is the reduce the scaling with a condition number from quadratic to linear, as well as to remove extraneous factors that do not appear in the analysis of SVRG in the convex sotting. As described below, the final result matches the bounds that are known for the SVRG the separable convex optimization setting. These theoretical results also lead large gains in convergence speed.
3

---

Published in Transactions on Machine Learning Research (8/2024)
2 Problem formulation
where S is the state space, A the action space, P = P(s'|s,, AS the transition probabilities, r= r(s, s') the reward function, and y E [0, 1) is a discount rate. The agent follows a policy т : - A -a mapping from states to the probability simplex over actions. A policy æ induces a joint probability distribution x ((s, a), defined as the probability of choosing action a while being in state s. Given that the policy is fixed and we are interested only in policy evaluation, for the remainder of the paper we will consider the transition probability matrix P. such that: s's,s') = E. ((s, a) (ss"|s, a). We assume, that the Markov process produced by the transition probability matrix is irreducible and aperiodic with stationary distribution pa..
We consider discounted reward Markov Decision Process (MDP) defined by the tuple
The policy evaluation problem is to compute V*, defined as: (*(() E [ sum of discounted rewards, where the expectation is taken with respect to the sampled trajectory of states. Here rt is the reward at time & and v is the value function, formally defined to be the unique vector which satisfies the Bellman equation T
7're+1), 7 which is the expected
V*, where 7 the Bellman operator, defined as: (V)*(s) Eg P's,s') (r(s, s') +V)"(s')) The (D()) method is defined follows: one iteration performs fixed point update on randomly sampled pair of states s, with learning rate V(s) + V(s) + a(((s,')) + >V('') - ((s)). When the state space size [S] is large, labular methods which update the value function for every state become impractical. For this reason, a linear approximation of the value function is often used. Each state is represented by a feature voctor ((s) E Id and the state value (*(s) is approximated by (*)))) & (s)FO, where 0 is a lunable parameter vector. single TD updale on a randomly sampled transition s, s' becomes:
0 + 0 (0) 0+ ( + o(s) - 0))(s))
where the second equation should be viewed as a definition of ga.z/ (0).
Our goal is to find parameter vector l such that the average update vector is zero
Ess 19 (0*)] = O,
where the expectation is taken with respect to sampled pair of states s.s'. This expectation is also called mean-path update g(0) and can be written as:
(0) = E,,s' [9,, (0) = E,,, -()ds))) (0))=()))()))]) + Ba, ((s.s')((s)) = - A0 + b,
(1)
where the last line should be taken as the definition of the matrix A and vector b. Finally, the minimum eigenvalue of the matrix (A + / plays an important role in our analysis and will be denoted as AA-
There few possible settings of the problem: the samples s, s' might be drawn from the MDP on-line (Markovian sampling) or independently (i..dd sampling): the first state is drawn from fa: then s' is drawn as the next state under the policy и. Another possible setting for analysis is the "finite sample set': first, a trajectory of length N is drawn from an MDP following Markovian sampling and forms dataset D = {(s,, ag rı, $++1) Then TD()) proceeds by drawing samples from this dataset. Note that the definition of the expectation E,,y and, consequently, of matrix will be slightly different these two settings: in the on-line sampling case probability of pair of states s, is determined by the stationary distribution pn, and the transition matrix P; we define
A, = Σ Σ (s) (1.00)0)) -700)))0))0000)))))) )
#ES E'ES
In the "finite sample' case, the probability of s refers to the probability of getting a pair of states from one particular data point t: s = $t, = S141, and the matrix A is defined as:
N
Aa N Σ
(ss)((((s)) - 17))
4

---

Published in Transactions on Machine Learning Research (8/2024)
Likewise, the definition of g()) differs between the MDP and dataset settings, since that definition involves Ba, which, as discussed above, means slightly different. things in both settings.
In the sequel, we will occasionally refer to the matrix A. Whenever we make such a statement, we are in fact making two statements: one for the dataset case when should be taken to be Ad, and one in the on-line case when should be taken be Ag-
We make the following standard assumptions: Assumption 2.1. (Problem solvability) The matrix A is non-singular. Assumption 2.2. (Bounded features) [|o(s)]l2 s 1 for all E S.
These assumptions are widely accepted and have been utilized in previous research within the field Bhandari et al. 2018), Du et al. (2017), Korda & La (0015). Liu & Olshevsky 20221, ,, Xu et al. (2000) Assumption 2.1 ensures that A b exists and the problem solvable. At the risk of being repetitive, we note that this
is really two assumptions, one that Ag is non-singular in the on-line case, and one that Ag non-singular
in the dataset case, which are stated together. Assumption 2.2 is made for simplicity and can be satisfied by feature vector rescaling.
In our analysis we often use the function f(0), defined as:
f() (0 - A00 6*)
(2)
We will use fa and fe notation for the dataset (A = Aa) and environment (A = (A=Ae) cases respectively.
3 The TD-SVRG algorithm
Let us consider an optimization problem where the target function f(0) the sum of convex functions f(0) = (L/N) Ex= fi(0), and the total number of functions N is very large. This makes computing the full gradient (1/N) (0)) too costly for every update. Instead, during iteration L, want to apply an update Jt that is inexpensive to compute:
0, = 0 + age.
where is the learning rate. If use dr Vf((0) with randomly chosen obtain standard SGD (stochastic gradient descent) algorithm. The challenge with SGD lies in its high variance. One common approach to mitigate this is by applying so-called variance reduction techniques: we instead update
0, = 0:-1 + ants
where
1 gi + Elgh
for some appropriately defined of The key idea here is that regardless of how choose of: we will have
Elv. = Elgh),
so in expectation the update is the same. On the other hand, if we can choose df to be highly correlated with ft, then the variance of e will be substantially smaller than the variance of gt-
There are several algorithms based on this idea, the most prominent which are SAG (Schmidt et al. 2013), SAGA (Defazio et al. 2014), and SVRG (Johnson Zhang 2013 These algorithms propose different methods of constructing L. this work, we take our inspiration from the SVRG algorithm which suggests choose gr' to be the gradient of the function chosen time step i, but estimated on previous parameter
vector 0: gf (()), 0 0y <tt
The major drawback of this idea is that Elghl N (. parameter vector is costly to compute, because the motivating scenario here involved large N. However,
while being a full update for the

---

Published in Transactions on Machine Learning Research (8/2024)
Algorithm 1 TD-SVRG for the finite sample case
Parameters update batch size M and learning rate a. Initialize dg.
for m' = ..,,,..,, do 1-mmn 0m-(0) N L (Deo(()))
where (0. (r(s, + (
0o 0.
for = 1 to M do
Sample s, from DD
Compute 8r = Io.e' (0,-1) (0) + Im (0).
Update parameters 02 = 9 + a2l.
end for Set fm = By for randomly chosen t' E (0..... M 1).
end for
it turns out that for SVRG to work well, we don't need to compute this expectation at every time stop, but rather can re-use the computation from a previous iteration. is proved in Johnson & Zhang (2013) that an optimal frequency of updates between computations of the full update [[g;(() allows the algorithm achieve a geometric convergence rate (in contrast to SGD, which does not attain geometric convergence rate).
In this paper we propose modification of the TD(0) method with SVRG technique (TD-SVRG) which can attain a geometric convergence rate. This algorithm is given above as Algorithm 1. The algorithm works under the "finite sample set" setting which assumes there already exists a sampled data set D. This is the same setting as in Du et al. (017)) However, the method we propose does not add regularization and does not use dual parameters, which makes it considcrably simpler.
Like the classic SVRG algorithm, our proposed TD-SVRG has two nested loops. We refer to one step of the outer loop as epoch and to one step of the inner loop iteration. TD-SVRG keeps two parameter vectors: the current parameter vector fe, which is being updated at every iteration, and the vector A,, which is updated at the end of each epoch.
Each epoch contains M iterations, which we call update batch size (not to be confused with the estimation batch size, which will be used in the algorithms below compute an estimate of the mean-path update).
4 Outline of the Analysis
In this section we briefly discuss perspective on TD learning which represents the key difference between our analysis and the previous works. In Xu et al. (2020) the 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." We show, that viewing TD learning as gradient splitting allows us to find such a function and establish a relationship between the gradient and the value function.
The concept of viewing TD-learning as gradient splitting comes from Liu & Olshevsky (2021). in which the authors define the lincar function h(() B(e 8*) gradient splitting of quadratic function (0) = (0 0T A(0 0*) if B + BT 24. Liu & Olshevsky define the function:
f(0) = (1 1) Vo- 113 + Vo-1
where Vo is vector of state values induced by 0,
||V| = [ur
6

---

Published in Transactions on Machine Learning Research (8/2024)
1 V f(0)
0 0
2
-h(0)
Figure 1: Illustration of gradient splitting. All gradient splittings of the function f(0) will lie on line L. In addition, we have a constraint on the 2-norm of the matrix A, all gradient splittings will Tie on an interval I, thus suggesting that an update in the direction gradient splitting is almost as good, is an update in the direction of the true gradient.
is weighted norm, and
is a Dirichlet seminorm. They show that mean-path update -ī(0) is a gradient splitting of this function f f0), which is how this function naturally appears in the analysis of TD-lcarning
Our arguments build the gradient splitting interpretation of TD, and it is this approach that differentiates our paper from previous works on variance-reduced policy evaluation. This interpretation provides a tool for its convergence analysis, since it leads to bounds on key quantity: the inner product of a gradient splitting h()) and the direction 0" - 0 to the minimizer is the same as the inner product of - ((( and 0" - (see Figure D.. At the same time, gradient splitting is not the gradient itself, and many properties that hold for the gradient do not hold for gradient splitting. Please see Appendix E for additional discussion.
A key difficulty to overcome is that, in the "finite sample" function f(0) are no longer equivalent and, result, the TD(0) update longer gradient splitting. This complicates things considerably and our key idea is to view TD updates in this case form of an approximate gradient splitting.
discussed earlier, the two definitions of the
In addition to f(0), we define the expected square norm of the difference between the current and optimal parameters as w()
w( B(llgs,> yo." (0..,(0))11
where expectation is taken with respect to sampled pair of states 8, 8' With this notation provide technical lemma. The next proofs are based variations of this lemma.
Lemma 4.1. If Assumptions 2. 2.2 hold, the epoch parameters of two consecutive epochs m' 1 and m
are related by the following inequality:
2aME((fa(em.)) 2Ma El Ei] - 11 - 2 ME[ (0((
(4)
where the expectation is taken with respect to all previous epochs and choices of states s, during the epoch

---

Published in Transactions on Machine Learning Research (8/2024)
Proof. The proof of the lemma generally follows the analysis in Johnson & Zhang (0013 and can be found in Appendix B
Lemma 4.1 plays an auxiliary role in our analysis and siguificantly simplifies it. It introduces a new approach to the convergence proof by carrying iteration to iteration and epoch to epoch bounds to the earlier part
of the analysis. In particular, deriving bounds in terms of some arbitrary function u(0) is now reduced to deriving upper bounds on ||@m'-1 1- and w()), and a lower bound on f(0) in terms of the function u.
Three mentioned quantities are natural choices for the function u. In Appendix [ we show Lemma 4.1 might
be used to derive convergence in terms of ||0m''1 - 0=1 with similar bounds in Du al. (2017). In this paper use f()) to improve on previous results.
5 Main results
Our main results contain 4 theorems which establish convergence for 4 different settings: TD-SVRG for the finite samples setting (with one extra subseciton which outlines the similarity between the achieved complexity of TD-SVRG and classical SVRG), batched TD-SVRG for the finite sample sctting, TD-SVRG for i.i.d. online sampling and TD-SVRG for Markovian online sampling.
5.1 Convergence of TD-SVRG for finite sample setting
In this section, we show that Algorithm 1 allains geometric convergence in terms of a specially chosen function fa(0) with a being ((1) and M being ((1/Aa). Before we start note that in general first state of the first pair and a sccond state of the last state pair in the randomly sampled dataset would not be the same state. That leads to the effect which we call unbalanced dalasel: unlike the MDP, the first and second states distributions in such a dataset are different. In the unbalanced dataset case, mean path update not exactly a gradient splitting of the target function f(0) and we need to introduce a correction term in our analysis. The following theorem covers the unbalanced dataset case and the balanced dataset case is covered in the corollary.
Theorem 5.1. Suppose Assumptions 2. 2.2 hold and the dataset D may be unbolanced. Define the ervor
lerna J Nx. Then, if we choose learning rale a = 1/(8 + J) and update batch size M 2/(Aaa), Algorithm will have a convergence rate of:
4-2
E [[ S (
2 m
fa(Oo).
Corollary 5.2. If the dalaset 'D is balonced, then we may take the error term is J = 0 and consequently the same convergence rate might be obtained with choices of learning rate a 1/8 and update batch size M = 16/
Proof of Theorem 5.1 The proof is given in Appendix
D
Note that 0. refers to the iterate after m iterations of the outer loop. Thus, the total number of samples guaranteed by this theorem until ((.)) & is actually O((N + 16/Aa) log(1/c)) in the balanced case and O(N + 1642/(NNA) log(1/e)) in the unbalanced case, which means that two complexities are identical if the datasct size N is large enough so that N 2 A-
Aa
Even an error term introduced by an unbalanced dataset negligible in the randomly sampled dataset cases; it might not be lower bounded by a value less than J. In practice the issue might be tackled by sampling from modified dataset this issuc is discussed in Appendix F.
5.2 Similarity of SVRG and TD-SVRG
Note that the dataset case is similar to SVRG in the convex setting in the sense that: 1) the update performed at each step is selected uniformly at random, and 2) the exact mean-path update can be computed at every
8

---

Published in Transactions on Machine Learning Research (8/2024)
epoch. If the dataset is balanced, negative mean-path update -0( is gradient splitting of the function [0).. These allow us to further demonstrats rate the significance of the function ʃ(0) for the TD learning process and the greater similarity between TD-eeannng and convex optimization. We recall the convergence rate obtained in Johnson & Zhang 2013 for a sum of convex functions:
2La
1a 2
1-2La
where 7 is strong convexity parameter and L is Lipschitz smoothness parameter (we employ the notation from the original paper and introduce the symbol to avoid duplicates). The function s(0) - 1 (0-00)² (00)"(A(00 A(0- 8*) is AA strongly convex and 1-Lipschitz smooth, which means that the convergence rate obtained in this paper is identical to the convergence rate of SVRG in the convex setting. We provide an intuition that
supports this similarity in Appendix D This fact further extends the analogy between TD learning and convex optimization earlier explored by Bhandari et al. (2018) and Liu & Olshevsky (2021).
5.3 TD-SVRG with batching
In this section, we extend our results to an inexact mean-path update computation, applying the results of Babanezhad Harikandeh al. (2015) the TD SVRG algorithm. We show that the geometric convergence rate might be achieved with smaller number of computations by estimating the mean-path TD-update instead of performing full computation. This approach is similar to Peng et al. 2020), but does not require dual variables and achieves better results.
Since the computation of the mean-pate mean- error is not related to the dataset balance, in this section we assume that the dataset is balanced for simplicity.
Theorem 5.3. Suppose Assumplions 2. hold and the algoritlm runs for a lotal of m epochs. Then, if the learning rate is chosen as a = 1/8, the update batch size is M = 16/XA, and the estimation batch size during epoch m' is nmm min [N, = caal2/33 (4f(0m)) + +o21) where e a parameter and o² Elg.,. (00) is an optimal point update variance, Algorithm 2 will converge to the optimum with a convergence rate of:
2 3
B[Ja(Om)) S
(Ja(Oo) + C),
where C is a constont dependent on the parometer c.
Proof. The proof is given in Appendix G.1
This result is an improvement on Peng al. (2020), compared which improves both the estimation and update batch sizes. In terms of the update batch size, our result is better by at least factor of 1/((1 - mm) where Tmin represents the minimum probability within the stationary distribution of the transition matrix, see Table for theoretical results and Section J.4 for experimental comparison. In terms estimation batch size, we have given the result explicitly in terms of the iterate norm, while Peng et al. 2020hh has a bound in terms of the variance of both primal and dual update vectors (E² in their notation).
Note, that both quantities [(āmc) and a² required to compute the estimation batch size Tim are not known during the run of the algorithm. However, we provide an alternative quantity, which might be used in practice: Tom min(N, n-1 2x (2)rmax|² 8||0m' -112), where [max is the maximum absolute reward.
5.4 Online i.i.d. sampling from the MDP
We now apply a gradient splitting analysis to TD learning in the case of online i.i.d. sampling from the MDP each time we need to generate a new state s. We show that our methods can be applied in this case to derive tighter convergence bounds. One issue of TD-SVRG in the i.i.d. setting that the mcan-path update may not be computed directly. Indeed, once we have a dataset of size N, we can simply make a pass through it; but in MDP setting, it is typical to assume that making a pass through all the states
9

---

Published in Transactions on Machine Learning Research (8/2024)
of the MDP is impossible. The inexactness of mean-path update is addressed with the sampling technique introduced previously in Subsection 5.3 which makes the i.idd case very similar to TD-SVRG with non-exact mean-path computation in the finite sample case. Thus, the TD-SVRG algorithm for the iidd sampling case is very similar to Algorithm 2 with the only difference being that states 8, s' are being sampled from
the MDP instead of the dataset D. Formal description of the algorithm is provided Appendix H
In this setting, geometric convergence not attainable with variance reduction, which always relies on a pass through the dataset. Since here one sample is obtained from the MDP at every step, one needs to use increasing batch sizes. Our algorithm does so, and the next theorem once again improves the scaling with the condition number from quadratic to linear compared to the previous literature.
Theorem 5.4. Suppose Assumptions 2.1 2.2 hold. Then if the learning rate is chosen a 1/16, the updale batch size as M = 32/X, A and the eslimation butch size Aom! "2/(233) (45(0m)) + 20²), where is some arbitrary chosen constant, Algorithm 3 will have convergence rate of:
2
[[Ja(Om)] S (c(0))+(1))
where C₁ is a constant.
Proof. The proof is given in Appendix
H
This convergence rate will lead to total computational complexity of O O log((-1)) to achieve accuracy 6.
Similarly to the previous section, a quantity (2((2/3)m (2)r (2 8110m/-1113) might be used for estimation batch sizes Rew during practical implementation of the algorithm. Note that the expression |mmaz| 12 + 41|0m=-1ll" is common in the literature, e.g., it is denoted as D2 in Xu et al. (020
5.5 Online Markovian sampling from the MDP
The Markovian sampling case the hardest to analyse due to its dependence on the MDP properties, which makes establishing bounds on various quantities used during the proof much harder. Leveraging the gradient splitting view still helps us improve over existing bounds, but the derived algorithm does not have the nice property of constant learning rate. To deal with sample dependencies introduce one more assumption often used in the literature:
Assumption 5.5. For the MDP there exist constants m and p (0,1) 1) such that
sup (P(s E -ls0 = s). S mp'
2 0,
.ES
where dry (P,Q) Q) denotes the total-variation distance between the probability measures P and Q.
In the Markovian setting, also need to employ projection, which helps to set bound the update vector Following Xu et al. (2020), after each iteration project the parameter vector on ball of radius R (denoted as (R) = arg ming:]00|ss 0 - 2) We assume that |0-1 <. R, where the choice of R that satisfics this bound can be found in Section 8.2 at Bhandari et al. (2018). The detailed description of the
algorithm in Appendix !
Theorem 5.6. Suppose Assumptions
2.1
5.5 hold. Then, the output of Algorithm 4 satisfies:
(3) fc()
8C2, Xanm
(0m)l <
(
4a(20 67 mix (a)) + 9R²),
where C2 4(1+mm 130)
[4R² + --axl-
(1-p)
Proof. The proof is given in Appendix
10

---

Published in Transactions on Machine Learning Research (8/2024)
MDP,
Acrebot-vl. f
Ce CP-leele-v.
MountainCar-v..
177
187
lrgh1
0110
Number uudides 10000
Kumbor updides 10500 Acrobot-vl, norm
Rambon undelee 15000
"aanie undalte 10000
MDP, nor
CartPole-Vl, nort
MountainCar-40, nor
lrginorm
loginommi
log Deginammt
C
DIG
30
12"
Number tgatades 10000
Kumber
10500
Namber updicles 15000
Naabbrr uodeiie 1.0000
Figure 2: Geometric average performance of different algorithms in the finite sample case. Columns dataset source environments: MDP, Acrobot, CartPole and Mountain Car. Rows performance measurements: 10)( and log(10 1)...
Theorem 5.6 implies that choose s (log(L//c), Rm O(L/(4e)), a -((ellg(L/e) and M (oge)/)) O
the total sample complexity is:
log (1/e)
cdA
This has improved scaling with the condition number A compared to O (11 log(1/e)) in Xu et al. (2020)
2x
6 Experimental results
shows the relative performance of TD-SVRG, GTD2 (Sutton al. 2009 "vanilla" TD learning (Sutton 1988), and PD-SVRG (Du et al., 2017) in the finite sample setting. We used theory-snggested parameters for TD-SVRG, whereas parameters for PD-SVRG and GTD2 are selected by grid search. Datasets of size 5,000 are generated from 4 environments: Random MDP (Dann et al.] 2014). and the Acrobot, CartPole and Mountain car OpenAl Gym environments (Brockman et al. 2016). The complexity (x-axis on the graph) measured in the number of basic updates computations, which is computing an update Js.e (0) for sampled pair of states 8, and parameter vector 0. Note that this complexity accounts for both basic updates required to perform inner loop iterations of the algorithms and updates required to compute or estimate the mean-path update. As the theory predicts, TD-SVRG and PD-SVRG converge geometrically, while GTD and vanilla TD converge sub-linearly.
Figure 2
Details on the experiments and grid scarch can be found in Appendix J In addition, Appendix J has more experimental results: comparison of theoretical batch sizes (Appendix J.1. results on a datasets with DQN produced features (Appendix J.3), results for the dataset case with batched estimation of mean-path update (Appendix J.4), parameter scarch results for TD-SVRG algorithm (Appendix J.2), results of experiments for the online case with i.idd sampling (Appendix J.5] and Markovian sampling (Appendix J.6). Instructions and code for reproducing the experiments can be found in our github repository
11

---

Published in Transactions on Machine Learning Research (8/2024)
7 Conclusions
In the paper we provide improved sample complexity results for variance-reduced policy evaluation. Our koy theoretical finding is that it is possible to reduce the scaling with the condition number of the problem from quadratic to linear, matching what is known for SVRG in the convex optimization setting, while simultancously removing number of extrancous factors. This results in a many orders of magnitude improvements for batch size and sample complexity for even simple problems such as random MDPs or OpenAI Gym problems. Results of this type are attained in several settings, e.g., when a dataset of size N is sampled from the MDP, and when states of the MDP are sampled online either in an i.i.d. or Markovian fashion. In simulations we find that our method with step-sizes and batch-sizes coming from our theorems outperforms algorithms from the previous literature with the same paramelers selected by grid search. The main innovation in the proofs of our results is to draw on a view of TD learning as an approximate splitting of gradient descent.
References
Reza Babanezhad Harikandeh, Mohamed Osama Ahmed, Alim Virani, Mark Schmidt, Jakub Konečný, and Scott Sallinen. Stop wasting my gradients: Practical svrg. In C. Cortes, N. Lawrence, D. Lee, M. Sugiyama, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 28. Curran Associates, Inc., 2015.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (ods.), Proceedings of the 31st Conference On Learning Theory, volume 75 of Proceedings of Machine Learning Research, pp. 1691-1692. PMLR, 06-09 Jul 2018.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: 16d.:00100554 2016.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for td(0) with function approximation. Proceedings of the AAAT Conference on 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 sup- port for non-strongly convex composite objectives. In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K.Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 27, 2014.
Simon S. Du, Jianshu Chen, Lihong Li, Lin Xiao, and Dengyong Zhou. Stochastic variance reduction hods for policy evaluation. In Proceedings of the 34th International Conference on Machine Learning, volume 70 of Proceedings of Machine Learning Reseorch, pp. 1049-1058 06-11 Aug 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) with function approximation: Concentration bounds and a centered variant with exponential convergence. In Proceedings of the 32nd International Conference on Machine Learning (TCML), pp. 626 634, 2015.
Lucien Le Cam. Asymptotic methods in statistical decision theory. Springer Science & Business Media, 2012.
Rui Liu and Alex Olshovsky. Temporal difference learning as gradient splitting. In Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. 18-24 Jul 2021.
Shaocong Ma, Yi Zhou, and Shaoteng Zou. Varianco-reduced off-policy tdc learning: Non-asymptotic con- vergence analysis. Advances in Newral Information Processing Systems, 1796-11806, 2020.
12

---

Published in Transactions on Machine Learning Research (8/2024)
Volodymyr Mnih, Koray Kavukeuoglu, David Silver, Andrei A. Rusu, Joel Veness, Mare G. Bellemare, Alex Graves, Martin Riedmiller, Andreas K. Fidjeland, Georg Ostrovski, Stig Petersen, Charles Beattie, Amir Sadik, loannis Antonoglou, Helen King, Dharshan Kumaran, Daan Wierstra, Shane Legg, and Demis Hassabis. Human-level control through deep reinforcement learning. Nature, (18(7540):529--3333 February 2015.
C Narayanan and Csaba Szepesvári. Finile time bounds for temporal difference learning with function approximation: Problems with some "state-of-the-art" results. Technical report, Technical report, 2017.
Zilun Peng, Ahmed Touati, Pascal Vincent, and Doina Precup. Svrg for policy evaluation with fewer gradient evaluations. In Proceedings of the Twendy-Ninth International Joint Conference on Artificial Intelligence, IJCAI-20, pp. 2697 2703, 7 2020. doi: 10.24963 234963/jjaai.2200/ Main track.
Herbert Robbins and Sutton Monro. stochastic approximation method. The annals of mathematical slalislics, pp. 400 407, 1951.
Mark Schmidt, Nicolas Le Roux, and Francis Bach. Minimizing finite sums with the stochastic average gradient, 2013.
Rayadurgam Srikant and Lei Ying, Finite-time error bounds for linear stochastic approximation andtd learning. In Conference on Learning Theory, pp.
PMLR, 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 dreseett methods for temporal-differnne learning with linear function approximation. In Proceedings of the 26th annual international conference on machine learning, pp. 993
1000, 2009.
Ahmed Touati, Pierre-Lue Bacon, Doina Precup, and Pascal Vincent. Convergent tree backup and retrace with function approximation. International Conference on Machine Learning, pp. 4964. PMLR, 2018.
J.N. Tsitsiklis and B. Van Roy. An analysis of temporal-diiference learning with function approximation. IEEE Transactions on Automatic Control, 42(5):674 690, 1997. doi: 10.1109/9.58087..
Tengyu Xu, Zhe Wang, Yi Zhou, and Yingbin Liang. Reanalysis of variance reduced temporal difference learning. In International Conference on Learning Representations, 2020.
13

---

Published in Transactions on Machine Learning Research (8/2024)
A Discussion on TD-learning lower bound
In this paper, we want to show that the sample efficiency of TD-lcarning cannot be lower than O(c This is easy to demonstrate by utilizing the fact that the policy evaluation problem easily reduces to a mean estimation problem, for which we have an established bound of ((e-)). Here, we give a simple example of how to reduce the policy evaluation problem to the problem of estimating the probability of a Bernoulli random variable.
Consider 3 state MDP and policy which has the following transition matrix between states:
1/2
p
1/2
P
1/2
1/2
0
1/2
1/2
As standard policy evaluation, we do not assume the MDP known; in particular, the parameter p is unknown. The agent receives reward of 1 whenever it moves from state 2 and reward of otherwise. Thus, the reward here depends only on the state. The MDP with this policy is geometrically ergodic since p2 is strictly positive matrix.
Let us compute the value function assuming we start from state 1. This can be done by observing that the stationary distribution of this probability transition matrix is (1/2,p, 1/2 - p), and that if we start at node 1, reaches the stationary distribution after a single step. Thus
((1) 0 7p- +
P 7 1-7
Thus if we take y= 1/2, V(1) = p and thus estimating the value function with certain expected square error will translate to a similar expected square error on estimating up to constants. Therefore, it is not possible to get the error with better complexity than O(e-)), since would violate lower bound provided by LeCam's method (Le Cam 2012).
This simple argument states that the results of i.i.d. case analysis reported directly in Ma et al. (020)) and indirectly implied by Xu et. al. (2020) (where complexity better than - might be achieved under certain choices of batch size and learning rate) are not possible to achieve.
14

---

Published in Transactions on Machine Learning Research (8/2024)
B Proof of Lemma 4.1
The proof follows the same logic as in Johnson & Zhang (2013) and is organized in four steps.
Step B.1. In the original paper, the proof starts with deriving bound on the squared norm of the difference between the current and optimal parameter vectors. With the introduction of wo(f) this step in our proof is trivial. We have
Pa.s:119a,./000 Ds.' (0") w(0).
where Eg,"' denotes the expectation taken with respect to the choice of a random pair of states s, In other words, [+] denotes the conditional expectation with respect to all variables that are not s, s', which, recall, are generated at time by sampling from the stationary distribution and letting s' be the next state. We will slightly abuse notation to write [-] instead of the more rigorous Es,, since what time index the states are generated at random is usually clear from the context.
Step B.2. During Step we derive a bound on the norm of single iteration t update v, = gs..
g (0) g(0), where g()) defined in assuming that states 8, s' were sampled randomly during step t:
Eg,e' [|/12/12 Eg,o' |1 (0=-1) # (0) + 3(0)112
E,, or [1 (0.-1) 9 (0")) + (90.5 g0. g0) 7(0))
s 2
(15s,s' (0t-1) - gx,x' 11)
+ 2E,,,r
|9 (0) 8 (0)) (g(0) -(00 1112
[( (0c-1) I (0") + 2R, 11 or (0) Is (0*)
Es,s' 190, (0) - g 101
S 2 [100, (0.-1) - Ja.d (0" ))1 + 2B,, 11 (0) Ia.s ( 11
2w (f)
The first incquality uses E|la + b1|2 < ||| + 2| 11|2. The second inequality uses the fact that the second
central moment is smaller than the second moment. The last equality uses the equality from Step 1. Step B.3. During this step we derive bound the expected squared norm of distance to the optimal parameter vector after single update t:
Eg,y 10 - 11 = E (e..r1100- |111-1 - 0" + tmrlll
110-1 0-2 + 2a(0,-1 0* E., + a² 2,2,, |1ze11
S 110-1 8-1 + 20 8¹) (0,_1) + 2a 2 ww (0.-1) + 2a (()
110_-1 0-11²- - 220/((0001)) + 2a² (0.00) 1) + 2a² (0).
The incquality uses the bound obtained in Step and equality uses gradient splitting propertics of g(;-.) 1)
(0--1 - (0)100")T((-111 (0t-1 (19)"(((0(11)) -
= (f)-1 - --- ( 1--00-1111 b + Ar8" b)
(5)
= - 0²)² An(O.-1 0*) --
After rearranging terms becomes:
E |0 112 + fa 2a2 ||0 0-112 20² 20²
Step B.4. During this step we sum the inequality obtained in Step 3 over the epoch and take another expectation to obtain:
M
M
M Σ
M 2a 20 (0, - & E
M 2a
110 - 11 Σ
(oEff((r-1)
Σ 10-11-1111
Σ
20²ud wo w()FF (6)
1=1
1=1
t=1
where Fin-11 is the information available in the beginning of epoch m'. We analyze this expression term-wise.
15

---

Published in Transactions on Machine Learning Research (8/2024)
Notice that E(= ||0 1*2 and Σx= |10g 11 consist of the same terms, except the first term in the first sum and the last term in the last sum, which are ||0p 0-1 and ||0M - 0-11 respectively. Since 1 - 0-1 is always positive and it is on the left hand side of the inequality, we could drop it.
We denote the parameter vector 8 chosen for epoch parameters at the end the epoch 6mc Since this vector is chosen uniformly at random among all iteration vectors 0,, E (0, M 1), we have that Σ E.a((L-1)) = (m and Σ Ew)(f-1) = MEm()mm))
At the same time, 0, which was chosen at the end the previous epoch remains the same throughout the epoch, therefore, Σn (w)(0) = MEw(O). Note, that the current epoch starts with setting On 0. Also, underline that 9 during the current epoch refers the previous epoch, we denote it m Plugging these values in (4) we have
2aMBfa((mm)) 2Ma 2M (mm))m)) S Bmmmmm 0-11 2a. MEw (fm'
16

---

Published in Transactions on Machine Learning Research (8/2024)
C Convergence in terms of squared norm
At this point, we on an aside to prove result that is not in the main body of the paper. We observe it is possible to derive a bound on Algorithm in the squared norm. This bound is generally worse than the results we report in the main body of the paper since it scales with the square of the condition number.
Proposition C.1. Suppose Assumptions 2.1 1 update batch size as M = 32/22, Xa, then Algorithm has a convergence rate of:
hold. If we chose the learning rate as XA/32 and
B[11mm 0- 1-
1100 111
This leads to batch size M being ((1/23), which is better than the results in Du et al. (017)) since their results have complexity (()(()) where x(C) is the condition number of matrix C' EEED (+s))((8*))
and KG & 1/Amin CAA C-
Proof. To transform inequality from Lemma into convergence rate guarantee, we need to bound w0)) and fa(0) in terms of 110 0 1?. Both bounds are easy to show:
w(0) = E I0. (0) 9 (0'))
(f 8*) " [((d(s))))))))) ((s)))(s)) (()(()))))
8*)
< (0 0*) 1 E'E.. [1(()((8') ((s))]l [[o(+)) [10))
[[(())] -1x(s)))) (1(7((8') - (()))III( 0*)
S 4 1',
fa(0) = (0 8*) "","",,r' [o(s) (0 0*) 2 AAllo 1'1
where E.,s' denotes the expectation taken with respect to choice of pair of states s. Plugging these
bounds into Equation (4)
we have:
(2aMAA 8Ma2)ll0m -011 <
-
which yields an epoch to epoch convergence rate of:
1 + 8
MaMA 8Ma2
For this expression to be < 1, we need that aM is set O(1/AA), which means that a needs to be O(Aa) for 2o to be (L). Therefore, M needs to be (11)3)) Setting AA/32 and M 32/X3 yields a convergence rate of 5/7.
17

---

Published in Transactions on Machine Learning Research (8/2024)
D Proof of Theorem 5.1
An analysis of the balanced dataset case follows from unbalanced dataset but for clarity of presentation provide a proof for balanced dataset separately, but before diving into it, let us provide an intuition as to why TD-SVRG in this case exhibits the same convergence as in the convex optimization case.
Let's assume we are solving a convex optimization problem for the function fa(O); i.e, we have access to the true gradients of the functions fa,s. In this case the update time t is
5. - (.(0.) [A (0) 0-)
In this case, the results of the SVRG paper are directly applicable. Instead, in the TD setting, have updates of the form:
9t = A.0; + by.
We see that the TD update is quite different from the convex update, it has different linear function and an extra term b,, which would affect the convergence as extra noise. However, once we apply the SVRG technique to these updates, as described in Section 3 the new updates become
1/ (f,())) ff(00) -E,,o' f (0)
2
2
(Ar + (0) 0)
1
EAee + A?, 0*)
2
2n
in the convex case and
(A,0; + +b,) -AA,0 + +b,) + Eg, + bood
Ar(0; - 0)+ + 1 Σ Ae.o' (0 0²),
n
in the TD case, where we again use the fact Eg [b,ar] = 1-A, to establish the equality.
The two updates look much more similar after applying the SVRG technique to them since the extra "noise" term by gets canceled with probability 1. Also, is a splitting of the true gradient vi which suggests that the application of v. updates instead of oy updates results in the same convergence rate. The formal proof of this fact is given below.
D.1 Balanced dataset case
Similar to the previous section, we start with deriving bounds, but this time we bound ||e - 101 and w()) in terms of f0). The first bound is straightforward:
fa(0) (0- -0") (
-706)))00000)000-- = 110 01112 Aa
fa(0).
18

---

Published in Transactions on Machine Learning Research (8/2024)
where g,,,' denotes the expectation taken with respect choice of pair of states s'. For w(f) we have:
w( = (0 - "" (.,s((((((s)) - (s)) (())(7((s)) 6(s))) -0)
(0 8-'
Σ (70(5') o(s)) (90(0))0))))) ((s)) 8*)
S,aEED
50 - 07) I
Σ
- ((o -
(7)
= -0 - '
p -00 8*) ) fa(0)
5,
-0 - 8-)
Σ S
{o())((s) 70()))())) (0- 8*) + fa(0)
2(Sa(0),
where the first inequality uses Assumption 2.2 the third equality uses the dataset balance property, and Es fact that 7 1.
". since and s' are the same set of states. The last inequality uses the
Plugging these bounds into Equation we have:
2a. 4Ma Bfa(Om)) s XA
Efa(fm--1) + 4a2 MBfa(Om
which yields an epoch to epoch convergence rate of:
20
Efa(Om/) S 211aM(1 - 2a)
Bfa(Om'-1).
2x
Setting a = and M = 16 we have the desired inequality. Xa
D.2 Unbalanced dataset case
To prove the theorem we follow the same strategy as in D For the Sa(O) we can use the same bound:
fa(0) = (0 - B
0*) = 110 --10 Aa
fa(O).
The bound for w0) is a little bit more difficult:
w-0) = (0 1 1
Σ (10(5))-((s)) - ((s))
(1016))-66))))0())00))))) -0s))
N
S (0 8*) I
Σ
- -(s))(()())))))) (0)) 0*)
N
(0
1
Σ
- (()) (T (0 0*)
N
1
(0
Σ
(5)(5)) 10)) fa(0)
N
6
(0 - 0
Σ
(()())(())) - -1d
N
# (0- 0¹'²" (6((sx=)) - ((000)6))))000000)
< 2fa((0) + 1100--0000 (0-
-(s))))s)))) 0²)².
19

---

Published in Transactions on Machine Learning Research (8/2024)
The first inequality follows from Assumption 2.2 The third equality is obtained by adding and subtracting
3 (0 - eigenvalue of the matrix o(11)))) by K. (note that K S 1). Thus,
8*). The second incquality uses the fact that 72 1. We denote the maximum
*²K 110 11 S (2 + >²K
7²
(= - 2fa(0)
S fa(0)(2 +
NĂA
NĂA
Plugging these bounds into Equation
4 we have:
(2aM 2Ma +
72 ])
S 1 AA
1 M22
7²
()m(mmm))))
NAA
NYA
which yields a convergence rate of:
a(2 97 NAa
212aM(1- - a(2 + xxx)) 1 - a2 + NAA
To achieve constant convergence rate, for example 3. we set up such that ax22 + xxx2 0.25, thus the second term is equal to 1/3 and a
Then, to make the first term equal 1/3, we need to set
84 NAA
M 2
2
Asa
A
8+ NAA
Thus, a is on the order of max(I.)/(NAA)) and M on the order of Xs Nin)
20

---

Published in Transactions on Machine Learning Research (8/2024)
E Properties of gradient splitting
While gradient splitting is one of our main tools, it is not true that this interpretation can be simply used to carry over results from convex optimization to policy evaluation. To illustrate this point, consider the following properties of convex functions with I-smooth gradients:
|| - -
2. - v()) 22));
/6) 2 V/) x),
[[Vf(z)
5. f(v =/)))+
=z1?,
(a000)) aa) - (a(1 - (2(())))/(2)]]\//)) vSOM
7. f(v) 2 f(x) V/x)' z) z [ 4
Now consider the following question: suppose we replace cach instance of a gradient by gradicnt splitting: which the above inequalities still hold? It turns out that (2), (4), (6) still work with gradient splittings, but (1), (3); (5), (7) do not.
Proofs in the convex optimization litcrature will typically when porting these arguments to the convex optimization literature, they must be reworked to only (2), (4), (6). Sometimes this will be trivial, but sometimes this may require a lot of creativity. Adopting the proofs to use gradient splitting instead of the gradient is one of the technical contributions of this paper.
subset of the inequalitics (1)-(7), and
21

---

Published in Transactions on Machine Learning Research (8/2024)
F Discussion on Unbalanced dataset
If the dataset balance assumption is not satisfied, it is always possible to modify the MDP slightly and make it satisfied. Indeed, suppose we are given an MDP M with initial state (or distribution) 8o and discount factor y. We can then modify the transition probabilities by always transitioning to so with probability p regardless of state and action chosen (and doing the normal transition from the MDP M with probability p), and changing the discount factor to new y'. Calling the new MDP M', we have that:
It is very easy to draw a dataset from M' such that the last state the same as the first one (just make sure to end on transition to so!) and the collected dataset will have the dataset balance property.
Under appropriate choice of p and y,, the value function VM in the original MDP can be easily recovered from the value function of the new MDP Vas-
A formal statement of this is in the comment below. Note that all need to be able to do is change the discount factor (which we usually set) as well as be able to restart the MDP (which we can do in any computer simulation).
The only caveat that the size of the dataset one can draw this way will have to be at least (1- 7) in expectation because to make the above sketch work will require a choice of p that is essentially proportional to (1-7) (sce Theorem statement in the next comment for a formal statement). This is not problem in practice, as typical discount factors are usually 0.99, whereas datasets tend be many orders of magnitude bigger than 100 (1 >)- Even a discount factor of x 0.999, much closer to one than is used in practice, only forces us to draw a dataset of size 1000 in expectation.
Theorem F.1. Choose
1+
p-1-
1-2
2
p=
I+
and consider the pair of MDPs M and M' which are defined in our previous comment. Then the quantities (s(s) and (s) satisfy the following recursion:
(*)+) = Vsr + 71)-))
1 22 (50)
Proof. Let T denote be time step when the first resct appears. We can condition on T to represent Var (s) 88:
20 VMr(s) = Σ P(t (s)) = =
1=1
= Σ (1 - p) -1 pp( | n- E(rl) + 7 16' Var(ss))
t=1
where the expected rewards E[re] are the same as in the original MDP. We next change the order of sum- mations:
30
VMr (s)= Σ
n- E(r(t)]
> (1 11'pp"'-12 > (1 -1pp" "Vrr) (s)
1=1
t=t
P=1
n1' -1 (1 - p)) -1 ((r)tt + (1 (1- -1 VMr
F=1
22

---

Published in Transactions on Machine Learning Research (8/2024)
Now we use the fact that the chosen 7 = 7/((1 -p))pp p) and perform some algebraic manipulations:
(8r = Σ
Eir(t] + +(1 -ppp"-"">" (s0)
8=1
= VM((+) + Σ p)* "17" Vxr)
1==1
= VM((s) +
1 - VM (s0);
YP
which implics the claimed equality:
7(1 -7) 1 1+7 22 Vas(
(M((s) Vsr(()
As claimed above, this theorem can be used recover VM from VMr Consequently, the artificial addition of reset button above makes it possible to generate a dataset which satisfies our dataset balance assumption from any MDP.
23

---

Published in Transactions on Machine Learning Research (8/2024)
G TD-SVRG with batching exact algorithm and proof
The algorithm for the batching case given follows:
Algorithm 2 TD-SVRG with batching for the finite sample case
Parameters update batch size M and learning rate Initialize 0g.
for m' 1,2, m do
0 0 choose cstimation batch size Am';
sample batch D of size Tmm from D w/o replacement,
compute 9m (0) 1 EaN'DD'' Is. (0),
where S (0) (r(8, 7 -())0)(()))))) ()())) lo 0.
for t = 1 to M do
Sample s, from D.
Compute ii Is.s' (f.-1) (0) + Im (0)-
Update parameters O2 0,-1 + arly.
end for Set 0m = 0. for randomly chosen t' E (O...., ; M 1). end for
G.1 Proof of Theorem 5.3
In the first part of the proof derive incquality which relates model paramcters of two consccutive epochs similar lo what we achieved in previous proofs, but now we introduce error vector to show that the mean path update is estimated instead of being computed exactly. In this proof, we follow the same 4 steps we introduced in the proof of Lemma 4.1 In the second part of the proof we show that there are conditions
under which the error term converges to 0.
Step G.1. During the first step we use the bound obtained in incquality
(0) < 2fa(0).
Step G.2. During this step we derive a bound on the squared norm a single update E[[[va|P]. But now, compared to previous case, we do not compute the exact mean-path updated g(0), but its estimate, and assume our computation has error gmd (8) = g(0) + nmm Thus, during iteration epoch m the single update vector
vt g.(0--1) (0) + 5(0) mmd-
24

---

Published in Transactions on Machine Learning Research (8/2024)
Taking expectation conditioned on all history previous to epoch m, which we denote as Fm--1, the bound on the single update can be derived as:
E B||lvel| F (0)))(00-1)) (000))((0)))) 1mm
(0)())(0)-1) - -(()))
+ g(0) + 7mm 1m
- 2 (00)))]
(0) (()))) (0(0))((0))
M/me 11 12
(19) gr (0*) - (0) 0c
7/mm (F
( 9: (x (1)=
(ll)) 00 Flg (0 (01) m'
(0) - (0)) - (l) ge (0)))) ) Mom F + 21 1
Fm
< (9 |
(8) (6 )1 2E Mmm 1| F
20[[ + 20) 2 11
[m
- E[4fa(0,-1) + 452(0) 2m| ||
where the first inequality uses E 3 2 2
the second inequality uses B||A- - E[A]]] < E|| || and the fact B[mm/ (g(()) - g(0") - B. (0()) 9 Fm = O; and the third incquality uses the
result of Step
Step G.3. During this step, we derive a bound on a vector norm after a single update:
Bi|10, 0-l 0-1
[[] 0" + avr mmmm
B[ 0-11² 20(0;-1 0-) T a a1o
s 0i1 - 0- 2a 8¹)²² g((1-1) .) + 2a (0 - -- "
qm
4o fd(0--1) + 402 + 2x² |m 1
B1110-1 - 0-11² fa + 22 (0,01 000 'mmm'
+ 4a² f((0-)) + 4o (0) + 2a Mm 1/1
where the first incquality uses
102a(00-11 0-) Fm 1122((0111-0))))) (g) (0--1)-9((00
g.(0) + +g(0)
Tmm F
= -E/2a(0111 - -0-)" (g(0--1) g(0) + g(0) + 7mm 11).
and the last equality uses
5
Rearranging terms we obtain:
E 0-112 2afa(00-1) 4o fa(()-1))
< 0 - 112 + 4a² f(() 20(0. 8¹²²² "mm + 2a 20²1/mm/11 112 Fm
< f0ll 1-1 + 4a [a( + 2a|10
0-11 1|7mm111 || + 2xx
|| 112 F 1..
< B[ - 122 + 4a² (θ) + 2a Xa
1
110,- - 1²1 + 2AA
|m (12) + 222 mm 112 [m)
2
Step G.4. Now derive bound on epoch update. We use similar logic as during the proof of Theorem 5.1 Since the error term doesn't t change over the epoch, summing over the epoch we have:
25

---

Published in Transactions on Machine Learning Research (8/2024)
Bl 1-112 2a.Mfa(0mm) 4o Ma2 Fl
M
1100 -0-11++ + 4a² M (a + 12
100-1 - -0 +
1 112) + 22222M11 1/ 11
22A
1=1
Ad 111mm - -0-11
1
110m--1 0-112 + 4a M fa mm -1) + E 2
2ox +
Fmm S
2
1 fa(0mi=1) + 4o M fa -1) 2
(2 +
1
1m 113
+22
A1
22A
Rearranging terms, dropping 1m - 1- and dividing by 2aM we further obtain:
(1 - 2a 2
(
+ +2a
fa(om'-1) +
+a
B[llmn Fm
2aMAA
2)a
Dividing both sides of this equation to 0.5 2a we have the epoch convergence:
2a
fa(0m'-1)1
AA2aM 2a)
0.5 2a
(8)
16 1mm 11
20.5 -2x)
0.5 2a
To achieve convergence, need to guarantee the linear convergence of the first and second terms in the sum separately. The first term is dependent inner loop updates; its convergence is analyzed in Theorem Here we show how to achieve similar geometric convergence rate of the second term. Since the error term has mean and we are in a finite sample case with replacement, the expected squared norm can be bounded by:
Mm
1|
Tomm 52 < (1
7mmm
S2
52
Nnm
N
nmm
Tmmm
where S2 is a bound on the update vector norm variance. If we want the error to be bounded by cpm we need the estimation batch size Rm to satisfy the condition:
52
Tom' 2
cp
until growing batch size reaches sample size. Satisfying this condition, guarantees that the second term has geometric convergence:
El|mma
Mmm 112
a
cp"
2A, (0.5 2a)
0.5
2a
20.50.5 -2a)
0.5
2a
26

---

Published in Transactions on Machine Learning Research (8/2024)
It remains to derive bound S for the update vector norm sample variance:
Ilys.
8,6
N
11 (0)
119,5 (0) - 10,.0(00) + In,d (0)) z
N
N
N
N
2,8"
6,6"
N
1
2119,,0 (0) In, (0¹)11 + 2| 21 (0")112=
N
1N
N
N N (45(0) + 20 82
(2) 20
where 6² is the variance of the updates in the optimal point similar to Bhandari et al. 20188)
Alternatively, we might derive a bound S in terms of quantities known during the algorithm execution:
Σ 1 (0)112 - -17(0)) <
N
N
1
N 1
19 (0)11
Σ
+ 7 + o(s) -
N
IN
N IN
N
1
Σ
2|]ro(>)]12 411"=(((")) (l)())
N
S,s!
N
N (2) mmaz + [100113) = S
ra 12 + +1 + +1
N
N
Having the convergence of the both terms of proceed by expanding the equation for earlier epochs (denoting bracket terms as and p¹):
)) S pfo(0m + /' 1 Fm = B[fa(Om:) S Sa(5 (a((0mm)) + p (B]) |mm 1 + pllll mm²
B[fa(0m)) 5 PM fa(O)) + +p' 1(
Now, assuming that estimation batch sizes are large enough that all error terms are bounded by cp":
E p cpm) nThh Sa(00) + pm cp'
[[ S pT (a(0)) o
1-p p
Denoting sp 1-p
C have the claimed result.
27

---

Published in Transactions on Machine Learning Research (8/2024)
H Proof of Theorem 5.4
Algorithm 3 TD-SVRG for the i..dd. sampling case
Parameters update batch size M and learning rate Initialize 0g.
for m' 1,2, m do 0 -1, choose cstimation batch size Am' sample batch D of size Tem's compute 9m (0) n'n EndeDm' 0s,)
where (0. (r(8,8') - 8o 0.
for 1 1 to M do Sample s from D.
Compute vi Is.s' (fc-1) (0) + Im (0)-
Update parameters Og 01-1 + anl
end for Set dm- bn:=6h end for
for randomly chosen t' (O....,M. 1).
The proof is very similar to 8 the only difference is that now we derive an expectation with respect to an MDP instead of a finite sample dataset.
Step H.l. During the first step the bound obtained during the proof of Theorem 5.1
- (0) = (0- 8 (4
(0
Ma (
d0s)) 0*)
$ (0 8² I (1 - -8-8 8*)
8,8"
(9)
(0 (' (((()))ss -0()))))))))))))))) 0*) + (0)
8,8"
(0 0z
-0000)000000000000000000000-0000 fa(0)
$ (f)
where the first inequality uses Assumption 2.2
the third equality uses the fact that μe is stationary
distribution of P (Ee (s) 8 (')o('")dd (=)) E. (s)) ((()))) = (3)))()))((()))00 The
last inequality uses the fact that 1.
Step H.2. During this step we derive bound on the squared norm of a single update ||[[2;11], which is performed during time step & of epoch Since bound, we will be taking expectation conditioned on all history previous to epoch m, which we denote Fm Similarly with Appendix G.1 we assume that mean path update in the end of the previous epoch was computed inexactly and has estimation error: g(0m'=1) + Tms Thus the single update vector becomes (for simplicity we denote fm as 8):
aiming to derive epoch to epoch convergence
Vt 9c(0--1) (0( + -(0) Mmd-
28

---

Published in Transactions on Machine Learning Research (8/2024)
The norm of this vector is bounded by:
B|] Billgr - 9: + Ø(0) + 7m 1| Fm'
(0))))(0)-1) (0 (0(0') (() + 9(0) + mm 11
( _=(0=))]"F=mm==1++
(0) - -0)))((0))))) - (0(0)-5(0') - 7//m 11 1m
- (
7mmm 112m
( 9u (0))))]][=mm/
20(199.0)) - Elg. (0) (0 )111
(l().(0)))((T)) (l) (0( Time 1m 2E
((((1((( (. mm
(0)
- 9e (0)))
2 17mm' 11 [(
-2E(w(((-1) + 2w)(0 + +0) 11 [1
E(4ff(0:-1)) + (0) 2 11
where the first inequality uses E E B1 |||| || 21 B|12, the second inequality uses EE| [[|A-E[[4] [[A]]| = |||- and the fact E[mmr1g(6) 9(0*) E,,5 g )], 11] ; and the third inequality uses the result of Step H.
Step H.3. We obtain a bound on a vector norm after a single update during iteration t of epoch m:
El|10, 0*l 0-1
B[ 0" ava 11
Ei 0-1 2a(0;-1 fz)²² Us 12
E[| 0-1|2+ + 20 0²'²² g(0(-1) + 20 0² mmd
+ + (e)-)(()-1) + 4a (0) + 2a | |1 1m
Applying an argument similar to and rearranging terms we obtain:
B[|00 - -10 (e2
< _ 1- + fa² 20 0²) TT + 2a 2
11 112
< Bi 1² + 4o (e + 20 0 0, 8*11 |1 ||7l| + 2a
Mm Fmm-11l
1
< B[||0-11 0-1 + 4a (o( 20 110 1- + 2A
|| (12)
222 2l || -m]
Step H.4. Now derive bound epoch update. We use the similar logic during the proof of Theorem
5.1 Since the error term doesn'l change over the epoch, summing over the epoch have:
10 0-112 (d..)) 4a2 (o
XA
|10 8-112 + +4a² 2 fe
(0 -1) + 12
-8-112 110-11-8112
110
-
|m (12) + 2a
(a22Mllmm [m =
2
2AA
da
1
110m - 1-112 + 2 fe + E|aaM
110mm
1-112
|nmm' 112) +=2a214 Imme || 1 Fm S
2A
1
La (0 4a² 3 (5 -1) F|2a.M
()((0e)))
1
+
| 112
+
22222Mll
| 11
Xe
22
29

---

Published in Transactions on Machine Learning Research (8/2024)
Rearranging terms, dropping B| 1-1 and dividing by 2cM we further obtain:
(1 - 2a Bifa F(
+ 2a
fe f0 +
+
B Blllmm Fm
MaMAA
2>a
Dividing both sides of this equation to 0.5 - 2a we have the epoch convergencee:
2a
(l -
fe
AA20M 2a)
0.5
2a
B 11
20.5 2a)
0.5 0.5 2a
Similarly to Appendix D convergence for the first term might be obtained by setting the learning rate to a = 1/16 and the update batch size to M = =2/AAA To guarantee convergence of the second term, we need to bound |/ In the infinite population with replacement case, the norm of the error vector is bounded by:
E El
11
7mm!
where S² is bound update vector norm variance. If we want the error to be bounded by cp we need the estimation batch size Dem to satisfy the condition:
S2
Tim
cpm
Satisfying this condition guarantees that the second term has geometric convergence:
a
E Mm
1
a
cpm
2X, (0.5 2a)
0.5
2a
20.5 2a)
0.5 2a
Similarly to Appendix G.1 the bound on sample variance S can be derived as follows:
Σ
Mn s')P(s,')lll..--
11g(0)112 =
5,5'
(s) (1),,, Io.d (0") + Is. (0" (0¹)11 <
8,8"
((s, s2)2ll (0) go.S' (0 112 2 g2, (0))1
2w( + 20 < 4 s2
where 2² is the variance of the updates the optimal point similar to Bhandari et al. 2018
An alternative bound on 52 with known quantities for practical implementation:
Hx (sss (0)1 110(0) <
Mx (ss))) (0)11 Σ ( -
4r (s))((ss)))( +41 +41)((s <
8,8
(2) maa + 11 (2) mmmm 8 S2
30

---

Published in Transactions on Machine Learning Research (8/2024)
Setting hyperparameters to obtained values will results in final computational complexity of O log(e- I))
31

---

Published in Transactions on Machine Learning Research (8/2024)
Proof of Theorem 5.6
Algorithm TD-SVRG for the Markovian sampling case
Parameters updale batch size M and learning rate a and projection radius R. Initialize 9g.
for m 1.2, do 0 = 0m/m choose estimation batch size nmm,
sample trajectory D of length nem
compute 9m/ (0) = 1 LaveDm' Is.s
nmm!
where (0, = (r(s, + -
0o 0.
for t == to M do Sample s, from D.
Compute J0 (0,-1) (0) + gm (0).
Update parameters 02 11n(0,-1 + aw)) end for Set 6m = 8y for randomly chosen t' E (O...., M -)). end for
In this section we show the convergence of the Algorithm which might be applied in the Markovian sampling case. In this case, we cannot simply apply Lemma 4.1 due to high estimation bias the bounds on (0) and w0) will not be derived based on the current value of 0, but based on global constraints on the updates guaranteed by applying projection.
First, we analyse single iteration step of epoch m. during which apply the update vector (0) 90) + (0). The update takes the form:
E110, 01 [E| + are)) =I 113 - B1|0,-1 0" + (-a0z))1
| 8¹113 2a(0;-1 8*) [[,,] + aa El1,11
(10)
10 - 1²1 + 2a(0; - 8²)²² (E)g, (0,-1) )) - Elg. + gm. (8))+
2 1u:11
where the expectation is taken with respect to s sampled during iteration t. Recall that under Markovian sampling, E[g, 1)] * g(0:-1) and that for the expectation of the estimated mean-path update we have # g(0), where 8m--1 is the last state of epoch m - 1. To lackle this issue, we follow the
E[gm/ (0) approach introduced in Bhandari et al. (2018) and Xu et al. (2020), and rewrite the expectation as a sum of mean-path updates and error terms. Similar to Bhandari et al. (2018). we denote the error term on a single update as Ç:
1mmmm11 |0))|mmmm
(0) (0 (0--0)) (g. -0.00 -()))
For error term on the trajectory, we follow Xu et al. 2020 and denole it as
Em (0. 0) (0 y- (gm (0) g(()).
Applying this notation, 10 can be rewritten as:
El 11 < 0- 11112+
20(0;-1 - 0² (f (E[gr- (0.- ((): + gm (0) + a² Ellxa18=
||0-11 0-1 + (E + (0. 0T) (gg(((10))))
(11)
(ElGr(0)] -00-1 - 0- (
(Elg(0,-1, 0)] - (0t-1 - 8r) (()) + a 2
32

---

Published in Transactions on Machine Learning Research (8/2024)
The error terms can be bounded by slightly modified lemmas from the original papers. For ((f), apply bound from Bhandari et al. 2018), Lemma. 11:
[E|C((0)]| S G (
(12)
In the original lemma, bound on E[)](0) is stated, however, in the proof a bound absolute value of the expectation is also derived.
For the mean-path estimation error term, we use modified version of Lemma 1 Xu et al. 2020). The proof of this lemma in the original paper starts by applying the incquality
a s 1aal| 21 |b6
to the expression (0c-1 (9m' (())) with & = Aa/2 (using the notation in Xu et al. (2020) ) For the purposes of our proof we use l: = A1. Thus, we will have the expression:
\ Ell 111101-1 - 1* -m +
4(1 (m 1)p)
El[m/ (0.-1, []]
14R²
mmax
Aa(1 p)mmm
(13)
\ B||l0-1 0"112|sm--1l + AAnm
C2
Also, note, that the term E might be bounded as El1e.11 11 - 18R2. Plugging these bounds into obtain:
11 we
0 0-1 < 2110-1
1- - (0 + 4a 4a2 Gr (a:))
A1
C2 18a R²
2a
116 131
2
XAnM'
Summing the inequality over the epoch and taking expectation with respect to all previous history, we have:
2x.ME(f.(0a) < 0000011 -0113 + 2a (^1s |0,-1 10 +
C2
AAnm
a² M2 (4 67 miz (a)) + 18R2).
Then divide both sides by 2 and use |!Ō,-1 0- < (0.-1A) to obtain:
E(f,( S 2M + + fe(0.-1)
1
C2
AAnM
a(2G² (4 6r mix (a)) + +9R²).
We choose and M such that aMAA 2. We then apply this inequality to the value of the function ʃ in the first term of the right-hand side recursively, which yields the desired result:
3 (3) (f.)
8C2 + 4a(20 mix (a)) + 9R²).
fc(0 +
4
AgTi
33

---

Published in Transactions on Machine Learning Research (8/2024)
J Additional experiments
J.1 Comparison of theoretic batchsizes
In this subsection, we compare the values of update batch sizes which are theoretically required to guarantee convergence. We compare batch sizes of three algorithms: TD-SVRG, PDSVRG (Du et al. (2017) and VRTD (Xu et al. (2020)) Note that PDSVRG and VRTD are algorithms for different scttings, but for TD-SVRG the batch size value the same: 16/AA, thus, we compare two algorithms the same table. We compare the batch sizes required by the algorithm for three MDPs: first MDP with 50 state, 20 actions and y 0.8, second MDP with 400 states, 10 actions and y 0.95, and third MDP with 1000 states, 20 actions and 0.99, with actions selection probabilities generated from U 1) (similar to the settings used for the experiments in Sections f and J.5 Since the batch size is dependent on the smallest eigenvalue of the matrix A, which, in turn, is dependent on the dimensionality of the feature vector, we do the comparison for different fcature vector sizes: 5, 10, 20 and 40 randomly generated features and 1 constant feature for each state. We generale dalasets and environments for each feature size. Our results are summarized Figure and Tables and
Comparison of theoretically suggested batch sizes for an MDP with 50 states, 20 actions and Y = 0.8. Values in the first row indicate the demensionality of the feature vectors. Values the other rows: batch size of the corresponding method. Values averaged 10 generated datasets and environments.
Table 3:
Method/Featee Features
11
41
TD-SVRG
2339
6808
21553
4.51
103
PD-SVRG
1.52 10
3.09
10t9
1.85
1023
1.41
10
VRTD
3.07 106
2.13 107
3.79 10
165
10
Table 4: Comparison of theoretically suggested batch sizes for MDP with 400 states, 10 actions and 0.95. Values in the first row indicate the demensionality of the feature vectors. Values in the other rows: batch size of the corresponding method. Values are averaged 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
10
VRTD
5.41 106
2.53
107
1.63
108
1.58
109
Table 5: Comparison of theoretically suggested batch sizes for MDP with 1000 stales, 20 actions and = 0.99. Values in the first row indicate the demensionality of the feature vectors. Values in the other rows: batch size of the corresponding method. Values are averaged over 10 generated datasets and environments.
Method/Food Features
11
21
41
TD-SVRG
9206
16096
32723
79401
PD-SVRG
7.38 10
9.64
1020
5.14
1023
4.97
1026
VRTD
4.35 107
1.34 10
5.44 108
1.45 109
34

---

Published in Transactions on Machine Learning Research (8/2024)
states
400 states
1000 states
2000 states
batch 3b0e
Seathh 1l
Dottch 200e
feauues MountainCar
Foeeuurss Pondulum
Curtholc
Acrobot
batch size
battd NEO
botth
Figure 3: Theoretical batch sizes of different algorithms in log-scale, geometrical average over 10 samples.
The x-axis plots the dimension of the feature vector. First row: Batch sizes for random MDP environment (see Sec. 0 Left to right: Figure - 50 states, 20 actions and y = 0.8; Figure 2: 400 states, actions and
Y 0.95, Figure 3: 1000 states, actions and ς = 0.99; Figure 4: 2000 states, 50 actions and y = 0.75. Second row: batch sizes for dataset generated from OpenAl gym classic control environments Brockman ct al. (2016). Features generated by applying RBF kernels and then removing highly correlated feature
vectors one by one (see Sec. G
MDP,
MDP, norm
10-1
10p
10
10a4-
log(norm)
log(f)
10-16
SVRG,therr theory
SURG, theary
batch
30-19
10
PD SVRG, 01,00
PO SVRG, 01
14
12 14
16
Number of batches of size 10000
Number of batches size 10000
Figure 4: Average performance of TD-SVRG and PD-SVRG algorithms with different parame-
ters: "SVRG theory" is TD-SVRG algorithm with parameters suggested by theoretical analysis; "SVRG Ir 1r_1/4 batch scale 8" a best- post-porforming algorithm from TD-SVRG search grid (a 1/4, M 8/ AA) "PD-SVRG 0.01 le-6" is a the best perforing algorithm from the first. PD-SVRG search grid (oo 10 (, ow 10 ( "PD-SCRG 0.01 0.125 8" is the best performing PS-SVRG
Rows performance algorithms from the second grid search (a 1/8, M 8/AA, o 10-2 1012101 X measurements:: log( and log(10 (*))-
J.2 Additional parameter grid search in dataset case
In this set of experiments, we conducted additional grid searches for the TD-SVRG and PD-SVRG algo- rithms. For TD-SVRG, we executed a grid search on the set of parameters near the theoretically predicted parameters (update batch size M 16/AA, lcarning rate over two grids: parameters suggested by the authors of the original paper and parameters close to those suggested by our theory. All experiments were conducted
1/8). For PD-SVRG, we ran searches
MDP environment with 400 states, 21
35

---

Published in Transactions on Machine Learning Research (8/2024)
features, 10 actions, and 7 0.95, identical to the one described in Section G of this paper. For TD- SVRG, we ran grid search over the parameter batch size M E {8, 12, 16, 24, 32)/2x AA and learning rate a E (1/4, 1/8.//1/////./// 1/8. 1/12, 1/16]. For the PD-SVRG algorithm, the first grid was formed near the exact values suggested in Du et al. 2017]. i.c., primal variables learning rate de E {10-',... 10 1011100-011 ([),t(())), dual pa- rameters learning rale ow E (1, 10-1 1/ / (C), and the batch size is twice the dataset size (M = 2N). The second grid uses the same learning rate and batch sizes as TD-SVRG, with the dual parameters learning rate Ow being the samn as in the previous grid.
The results are illustrated in Figure 4 This figure demonstrates that TD-SVRG converges faster than the PD-SVRG algorithm, which utilizes dual variables.
J.3 Datasets with DQN features
Acrcbot-v1.
CartPole-Vl,
MountainEan-v,,
30%
201
132t1
1270
21 199
1214
B
Number updaias Acrobativl,
Kumber updabes CortPole
Number updatis 10000 MountainCa
(oginam)
togirrum (rrmmn
Noginom!!
D206
22000
Number of updates x 10000
Kumber upoates 10000
Number of updatees 10000
Figure 5: Geometric average performance of different algorithms in the finite sample with DQN fea- tures. Columns dataset source environments: Acrobot, CartPole and Mountain Car. Rows performance measurements: lo)( and log(10 - -))).
In this set of experiments, compare the performance of the same algorithms in Section 6 datasets collected from OpenAI Acrobot, CartPOle and MountainCar environments Brockman et al. (2016) using DQN features. To collect these features, we trained 1 hidden layer neural network with DQN algorithm Mnih et al. (2015) for 1000 plays. Then, the trained agent played 5000 episodes following greedy policy, while neural network hidden states were recorded as feature representation the visited states. Features collected this way tend be highly correlated, therefore we applied PCA clearing, keeping minimum set of principal components, corresponding to 90 % of the variance.
For the TD-SVRG algorithm we used theoretically justified parameters, for the other algorithms parameters selected with grid search (Sec. J.2), the results are presented in Figure 5 In all environments TD-SVRG exhibits stable linear convergence, GTD2 and vanilla TD algorithms converge sublinearly, while PD-SVRG performance unstable due to high range of condition numbers of dataset's characteristic matrices and C (large values xCC) caused PD-SVRG divergence in the Acrobot dataset).
J.4 Batched SVRG performance
In this set of experiments we compare the performance of TD-SVRG and batched TD-SVRG in the finite- sample case. We generate 10 datasets of size 50000 from similar MDP in Section Algorithms with
36

---

Published in Transactions on Machine Learning Research (8/2024)
the same hyperparameters. Average results 10 runs presented in Figure and show that batched TD-SVRG saves lot of computations during the earlier epochs, which provides faster convergence.
MDP,
MDP, norm
10'
10.--
10
log(norm)
10"1
log(n)
10
10t1
10:10
10
SVRG 8SVRG
SURG MVVG
10
10
Number of passes
Number of passes
Figure 6: Average performance of TD-SVRG and batching TD-SVRG in the finite sample case. Datasets sampled from MDP environments. Left figure performance in terms of log(f Right figure performance in terms of log(10 - l).
J.5 Online i.i.d. sampling from the MDP
MDP, iid, f
MDP, iid, norm
SVRG theory
10
SVIGG theary
VRTD Sk
VETO SK
10-1
20k
20k L.sggrttt
TD. 10-1/99111)
log(norm)
log(f)
10a
10
10a1
Number of batches of size 10000
Number of batches of size 10000
Figure 7: Online iid sampling: Average performance of TD-SVRG with theoretical parameters, VRTD with different batch sizes and vanilla TD with learning rate equal to 1/vt in the i.i.d. sampling case. Left figure performance in terms of log(s(0)), right figure in terms of log( - 0*)).
In this set of experiments we compare the performance of TD-SVRG, VRTD and Vanilla TD with decreasing learning rates in the i.i.d. sampling case. States and rewards are sampled from the same MDP in Section under iid sampling strategy next transition is being sampled independently from previous transition. Hyperparameters are chosen as follows: for TD-SVRG learning rate = 1/8, update batch size M = 16/AA. estimation batch size epoch expansion factor is p² = 1.2. VRTD learning rate a 0.1 and batch sizes E 5, 10, 20 * 103, For vanilla TD decreasing learning rate is set to 1/vt, where t is a mumber of the performed update. Average results over runs are shown in Figure 7 The figure shows that TD-SVRG converges even if its performance suffers from high variance, VRTD algorithms oscillate after reaching a certain level (due to bias). Vanilla TD with decreasing learning rate converges slowly then SVRG.
37

---

Published in Transactions on Machine Learning Research (8/2024)
J.6
Online Markovian sampling from MDP
MDP, Markov,
MDP, Markov, norm
S/RG, theory
10
SVRG, theory
VATD 20k
VRTO 20k
TD (D-Lharttt)
TD Lighitt)
log(norm)
log(f)
10-3
10a
10
10
10"4
15
Number of batches of size 10000
Number of batches of size 10000
Figure 8: Online Markovian sampling: Average performance of TD-SVRG with thcoretical parameters, VRTD with different batch sizes and vanilla TD with learning rate equal to 1/v1 in the i.i.d. sampling case. Left figure performance in terms of log( right figure in terms of log(10 0*)).
In this set of experiments compare the performance of TD-SVRG, VRTD and Vanilla TD with decreasing learning rates in the Markovian sampling case. States and rewards are sampled from the same MDP as in Section
f under Markovian sampling strategy next transition is being sampled dependent on the previous transition. Hyperparameters are chosen as follows: for TD-SVRG learning rate a = 1/8, update batch size M 16/AA, estimation batch size epoch expansion factor n² 1.2. VRTD learning rate a 0.1 and batch sizes . 5, 10, 20 103, For vanilla TD decreasing learning rate of the performed update. Average results over 10 runs shown in Figure g Because this MDP mixes very fast even under Markovian sampling, the results very similar to iid sampling case. The figure shows that TD-SVRG converges with decrcasing rate, VRTD algorithms reach certain level and then oscillate, vanilla TD converges with decreasing rate and slower then TD-SVRG.
to 1/vt, where
number
J.7 Comparison of update batch sizes
In this set of experiments, assume that dA and, consequently, the are not known. We investigate the effect of approximate update batch size on the algorithm's performance, checking the performance of batch sizes {8, 12, 24, 12/22/AA against the theory-predicted value. We run this experiment for all three cases: dataset (Figure 9) online iid sampling (Figure [0], and online Markovian sampling (Figure [T.. In all thrce cases, the algorithms demonstrate comparable performance, while in the online sampling cases, both iid and Markovian, the difference is negligible. This is caused by the fact that mean-path update estimation dominates the complexity.
batch size 16/AA
38

---

Published in Transactions on Machine Learning Research (8/2024)
MDP,
MDP, norm
10a
10
10"1
(ng
10x4
log
10"4
10-12
SURG, SVRG_theor
theory
SURG, Sheary
SURG Scele_0
bwtch
10-13
SMRG, ir 18 betch scale 24
10
SURG, v. 1U batch Scale
SVRG, vr 188 batch scale 32
SVRG v. U8 batch scale 32
Number of batches of size 10000
Number of batches of size 10000
Figure 9: Dataset sampling case: Average performance of TD-SVRG with theoretical parameters and with different update batch size scales of 1/AA-
MDP, iid, f
MDP, lid, norm
SWRG, theary
SVRG, theory
SVRG, 188 bwtth scale
SVRG, 1 twtch scale
SURG bitch
SVRG, 1/8 bwith scale
10-1
SvRG_Ir
SVRG Ir 1/8 batch scale
SVRG Ir 1/8 bwtch scale 32
log(norm)
log(f)
10-2
10a
10a
14
12
Number of batches of size 10000
Number of batches size 10000
Figure 10: IID sampling case: Average performance of TD-SVRG with theoretical parameters and with different update batch size scales 1/AA.
MDP, iid, f
MDP, iid, norm
10a
theory
theory
SVRG, 1/8 betch scate_
SVRG, 1r betch scale, 8
SWRG 1/8 betch 12
SVRG, Ir. 1/1 bwtch 12
10a
SVRGJI betch Scale,
SVRG wwtch scach_scale.24
Aosch_scale_11
log(norm)
log(f)
10-2
10-1
10
10a
14
12
14
Number of batches 10000
Number of batches size
Figure 11: Markovian sampling case: Average performance of TD-SVRG with theoretical parameters and with different update batch size scales of 1/\A-
39

---

Published in Transactions on Machine Learning Research (8/2024)
J.8 Experiment details
In our experiments (Section we compare the performance of TD-SVRG with GTD2 Sutton et. al. (2009)
"vanilla" TD learning Sutton [188), and PD-SVRG Du et al. (2017) in the finite sample setting. Gener- ally, our experimental sct-up is similar to Peng et al. (2020). Datasets of size 5,000 are generated from 4 environments: Random MDP Dann et al. (2014), and the Acrobot, CartPole and Mountain car OpenAI Gym environments Brockman et al. (2016). For the Random MDP, we construct an MDP environment with - = 400, 21 features (20 random and constant) and 10 actions, with action selection probabilities gener- ated from U00 1). For OpenAI gym environments, the agent selects states uniformly at random. Features are constructed by applying RBF kernels to discretize the original states and then removing highly correlated features. The docay rate " is set to 0.95.
We compare the performance TD-SVRG against the performance other algorithms with parameters selected by grid search. Details on the grid search might be found in Appendix (.2] Hyperparamters for the algorithms are selected as follows: for TD-SVRG our theorctically justified parameters are selected, the learning rate is set to a 1/8 and the updale batch size to M 16/\A; for GTD2 the best performing parameters were: for PD-SVRG the parameters are set to dg = 0.1/(L,x(C),, aw 0.1/\max (C) and the batch size is twice the size of the dataset, i.e., M = 2N. Each algorithm for each setting was run 10 times and the geometric average performance is presented.
0.125 and 8 0.25; for vanilla TD decreasing learning rate is set to
1/v/;
40

---

Published in Transactions on Machine Learning Research (8/2024)
K Algorithms comparison
In this section, we present a more detailed comparison of 'D algorithms. Our results are summarized in Table G and a detailed explanation of the quantities in the table is provided below.
Please note that while other algorithms derive convergence terms of ||0-0 our convergence is expressed in terms of the function f(0). The results can be compared using the incquality Aal10-0112 - f(0) S 110-0 8 p This implies that achieving an accuracy of in terms of one quantity can be accomplished by achieving an accuracy of Aa/E in terms of the other quantity. Consequently, our results for the finite sample case are strictly superior. For environment sampling cases, our results imply previous findings, whercas our results are not implied by previous ones. Furthermore, it is worth noting that the inequality Aall0 - 0 < f(0) is rarely strict, which means that in most cases, the convergence implied by our results would be superior.
Table 6: Comparison of algorithmic parameters. PD-SVRG and PD SAGA results reported from Du et al. 2017], VRTD and TD results from Xu al. (2020) GTD2 from Touati al.) (2018). Amin (Q) and =(Q) are used to define, respectively, minimum eigenvalue and condition number of matrix Q. AA in this table denotes minimum eigenvalue of the matrix 1/2(A + A²), which is defined in Equation ( Finite sample results use N for the size of the dataset sampled from the MDP. Other notation is taken from original papers, and Section 1 in the supplementary information gives self-contained definitions of all the symbols appearing in this table. For simplicity + y is upper bounded by 2 throughout, where y is the discount factor.
Method
Learning rale
Batch size
Total complexity
Finite sample case
x2x20 (k=
1
O <(Q))H Amii (G)c
GTD2
CAT 48K(C)L
(C Amin (A 1Ay
o O(N + Amii (A' A/²
(2
log(t)
PD-SVRG
Amin C 1A)
o ((N Aman CA" log(?)
x2(C)12
1
PD SAGA
3(8A2 (C)L
1/8
16/AA
o ((N+ 2t2 log(t)
This paper
L.d. sampling
TD
min( Aa )
1
log( 2
1/8
16/AA
o
Eha log( )
This paper
Markovian sampling
TD
(cc))))(?)
0
log?(2)
223
O(AA)
0
I Txa
o
log( +
VRDT
Ole/ ((e/log()))
o
(oR(2) cdA
0
1
log² (2)
This paper
cha
Definitions of quantities in Table 6
GTD2 convergence analysis resutls are taken from Touati et al. (2018) The learning rate required for their
guarantee to work is set to (o*()))) and the complexity to obtain accuracy c is O ((*(Q) ((Q))) notation:
x2x20
In this
is the minimum eigenvalue of the matrix A A' where the matrix M Elo(s (x)a(sk. and A' Elex (7 [0($41...] d(sk, ax)) where eg is the eligibility trace vector ex X8y(88, a 1 0(88, ax).
41

---

Published in Transactions on Machine Learning Research (8/2024)
A is an iteration number.
The matrix G plays key role in the analysis, it is a block matrix of the form
G (-VBA'
VBATT
BMx
and Ge is matrix of similar form generated from quantities estimated at time point k.
< x c + L2. where c(M) the condition number of the matrix M, P is the maximum eigenvalue of the matrix A M- and Lg is the Lg = ||E[G] Gx|Fx-illl Fk-1 this analysis the o-algebra generated by all previous history up to moment
1.
The quantity H. is equal to B - gell,, where x² = (0",
is the optimal solution and Bw
gh = (0, 73 b).
The last quantity left undefined is k(Q), which is the condition mumber of the matrix Q, obtained by diagonalization of the matrix G Q" AQ.
PD-SVRG and PD SAGA use the same quantities as GTD2, except that matrices A and C' are defined the same way as in this paper: = Ei(((s)) ((()) C ([o(s)o"(s)).
in this notation is the size of the dataset.
14p is the minimum eigenvalue of matrix AT 1-C1A.
All other quantities are defined in the paper.
42


Reviews:
[{"review_id": "uul22lVMYA", "reviewer": "Reviewer_vp5T", "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": "**Strength**\n\n- The key idea is clearly described which makes it easy to follow.\n- The idea allows shaving off the extra quadratic scaling on the condition number(which is not defined)/smallest eigenvalue\n- The empirical evaluations show a clear benefit of using this new \"method\" in terms of convergence\n\n**Weaknesses**\n\n- Even though the manuscript appears to be mostly theoretical, the technical novelty seems low. The reviewer agrees that the gradient splitting idea allows easier analysis and improved results, however, the results of the paper follow a repetitive proof strategy borrowed from results in the literature. For example, Lemma 5.1 seems like the key tool that allows the analysis to go through and it mostly follows --as stated by the authors as well -- Johnson & Zhang (2013). The reviewer does not think this is a major issue as long as the proof technique provides a new insight into the core of the problem, i.e. learning the value function. However, the manuscript fails to highlight how this idea directly helps the convergence besides making the proof easier. Similarly, it is not clear whether this idea allows a novel algorithmic structure or development. The proposed Algorithm 1 (and its variants for different settings) seems trivial and lacks novelty. The authors should clarify these points and comment on possible future directions for how this idea can be used in RL.  \n\n- Even though the empirical results look impressive in terms of performance and reducing the batch size, it is not clear if the batch size is the only computational bottleneck in the performance. Each epoch of the algorithm, requires computing $\\frac{1}{N} \\sum_{s, s^{\\prime} \\in \\mathcal{D}} g_{s, s^{\\prime}}(\\tilde{\\theta}) $ for growing N. This will be the main bottleneck in the computation. This should be included in the empirical results to demonstrate the clear benefit of the presented algorithm. Also, it is not clear why VRTD is not compared in the empirical performance.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 explores the gradient splitting interpretation of Temporal Difference (TD) learning and applies the Stochastic Variance Reduced Gradient (SVRG) method to achieve a geometric convergence rate. The authors present an algorithm that aligns with the convergence rate of SVRG in convex optimization by using a fixed learning rate of $1/8$. Their analysis spans three sampling regimes: finite sample, i.i.d., and Markovian settings. Empirical results are provided to support the claims.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please address the weaknesses in detail for theoretical and empirical results\n- Please provide intuition on how this new proof technique improves convergence in reducing the Bellman error\n- Please comment on how this idea could be useful/intuitive in future research directions", "broader_impact_concerns": "No Broader Impact Statement is needed for this work.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "M01pObjB79", "reviewer": "Reviewer_HR3f", "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**\n\n- The key ideas put forward in the paper is simple and clearly presented\n- The assumptions required for the results to hold are clearly stated, and effort is made to provide weaker results when certain assumptions (e.g. the balanced dataset assumption) are violated\n- The algorithm is clearly presented and easy to understand.\n- The use of gradient splitting, while simple, makes the analysis of the variance-reduced TD algorithm clean and obtains much better convergence results than the cited literature.\n\n**Weaknesses**\n1. While its simplicity makes the paper easy to follow, this simplicity is a symptom of the relative lack of novelty in this paper, which essentially investigates a corollary of the finding of Liu and Olshevsky (who note that the gradient splitting approach can be applied to analyze a number of variants of TD using similar tools as for gradient descent). Although my field of expertise isn't optimization and so I may have missed something, it doesn't appear that the paper provides new technical tools for studying the convergence of variance reduction methods in TD learning.\n2. The exponential convergence result requires sampling the full dataset and computing a full-batch gradient for every increment of $m$ (or in the batched case, sampling an exponentially growing subset of the dataset). This seems like it should add significantly to the computational cost of the algorithm, and it would be helpful to understand how the loss-reduction-per-flop compares with other methods, rather than loss-reduction-per-iteration (where each iteration has an exponentially growing computational cost). This is particularly relevant for the empirical evaluations, where it isn't clear whether the x-axis is providing a fair comparison between algorithms. How does TD-SVRG perform in terms of wall-clock time?\n3. Some of the quantities in theorems/equations are not always clearly defined. For example, what does it mean that $c$ is a parameter? Is its optimal value instance-dependent or instance-independent? Expectations are also often not qualified, so it is not clear what distribution and what random variable the expectation is being taken over. \n4. In the proof of Lemma 1, the quantity $\\bar{g}(\\theta^*)$ appears out of nowhere and is not justified in the text that follows its appearance.\n5. The objective for which the td update g is a gradient splitting doesn't appear to relate in an obvious way to the bellman error / projected bellman error / value error. It would be helpful to understand how the convergence of the parameters / auxiliary objective translates to the convergence of the TD objective.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 uses the finding of Liu and Olshevsky (2021) that temporal difference updates (in the linear, policy evaluation setting) can be viewed as a gradient splitting of a quadratic objective function to analyze the convergence rate of the Stochastic Variance Reduced Gradient method applied to TD learning. The result is an analysis showing geometric convergence rate for a simple algorithm which applies SVRG to the TD update direction. The algorithm is further shown to exhibit faster convergence than standard TD methods along with other variance-reduction approaches on a variety of environments from the OpenAI Gym suite.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- Please address the concerns raised in 'weaknesses'.\n- Please review the appropriate use of \\citep and \\citet", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "jRwd0GBjJB", "reviewer": "Reviewer_Pfqp", "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": "Getting better dependence on the problem-dependent constants compared to the previous works is the main strength of this work. \n \nThe paper needs restructuring. Mainly the paper leverages gradient splitting to get the desired objective function and convergence rates but it explains that in section 5.  The experimental part in the main body just considers the finite dataset case and ignores the other two online sampling versions.", "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 primary contribution of this paper lies in leveraging the gradient splitting interpretation of the Temporal Difference (TD) algorithm to apply Stochastic Variance Reduced Gradient (SVRG), achieving a linear convergence rate. By adopting the gradient splitting perspective, the authors formulate a quadratic objective function whose directional derivative aligns with the TD gradient when the direction points toward the optimal parameter. This insight allows for an analysis of the convergence of SVRG in optimizing the quadratic function, yielding improved dependence on problem-specific parameters. The authors examine three distinct sampling regimes: i.i.d. setting, Markovian setting, and finite data setting. In the finite data setting, akin to finite sum minimization, they establish a geometric convergence rate. For the i.i.d. and Markovian settings, they demonstrate a sublinear convergence rate due to the computational burden of evaluating the full gradient.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1- To set the step-size or batch size according to your theory, one needs to know the minimum eigenvalue of matrix A. But in some settings knowing that parameter is computationally expensive. How do you estimate that? It would be nice to see the effect of misestimation of this value empirically. \n    \n2-  There are some parameter overloading like m used as an iteration index or a constant. There are some parameters defined which is not used in the algorithm such as s in instantiation of Alg 4. So the paper needs a polish in terms of parameter definition and reuse.", "broader_impact_concerns": "There is no concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eUpAcdqjzS", "reviewer": "Reviewer_mVeV", "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 contribution of the work is strong by lowering the complexity of TD-learning when compared with the existing algorithms. The theoretical results are confirmed by clear improvement over the baselines in the experimental section. Finally, the variance reduction and gradient splitting techniques used to establish the algorithm and theory appear to be non-trivial and may inspire further work on the broader area.\n\nHowever, I believe the paper is not clear in a few important aspects, impacting the evaluation of the work. Specifically, at the moment, I am unclear about the following:\n- Is the algorithm new, or only the theoretical analysis, resulting in improved rates for the same algorithm?\n- The algorithm is not explained, nor introduced, and I have some questions. Does the algorithm come in a straightforward way from a variance reduction technique? Why is the technique not described, nor how the improvements come into place?\n- In the finite-sample case, the algorithm (Algorithm 1) has epochs, where an entire dataset is used to average the TD errors, and inside each epoch, has M iterations, where M samples are used (one per iteration). The complexity mentioned in the paper (for instance, table 1), is with respect to the number of epochs, iterations, or samples? \n- How does the algorithm work in the non-finite-sample case? Could a pseudo-code be also added, or Algorithm 1 written in a general fashion?\n- In the experimental results, we see clear benefits of the approach in terms of number of updates. Is an iteration of TD-SVRG an epoch or an iteration? And since each of these uses more samples (the entire dataset), can we see the results in terms of computation time?\n- What is meant by geometric convergence? On the number of epochs/iterations?\n\nI also have the following less important comments and questions:\n- Typo: \"worsk\" (page 9);\n- Was \"linearly\" meant \"geometrically\" on Section 6, of the experiments?\n- The \"condition number\" is not defined;\n- I believe $\\bar{g}_m$ should be $\\bar{g}_m(\\bar(\\theta))$ on the inner cycle of Algorithm 1;\n- If throughout the inner cycle of Algorithm 1, $\\bar{g}_m$ is constant, and given the linearity of the updates, why add it on every update and not just after the cycle, possibly with a different learning rate?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "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 focuses on policy evaluation in reinforcement learning. The paper shows improved convergence rates of TD-learning combined with variance reduction techniques (SVRG), in three different settings (finite, online i.i.d, and online Markovian), when compared with the existing results in the literature.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I believe it is important that the following points are addressed, with critical impact on my recommendation:\n- Clarification of the novelty of the algorithm;\n- Adding the derivation of the algorithm, or an explanation on how the variance is reduced;\n- Interpretation of the algorithm, and definition of the algorithm in the non-finite-sample case;\n- Definition of the notion of complexity used in Table 1;\n- Clarification on the experimental results, specifically what is considered an update;\n- Experimental results in terms of computation time.", "broader_impact_concerns": "I do not predict relevant ethical implications of the work in particular.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper shows that a simple application gradient splitting and SVRG can result in a simplified TD method that achieves a geometric rate of convergence.  This builds off other work, but is a stand-alone analysis that whose claims are justified by theory and experiments, and has an audience amongst those interested in the convergence of TD, with an even broader audience due to the clarity of presentation acknowledged by the reviewers.  This work clearly meets the TMLR criteria, even if the reviewers have some qualms about its advance over precursor results.
Decision: Accept (poster)