Finite-Time Analysis of Temporal Difference Learning with Experience Replay
Authors: Han-Dong Lim
Donghwan Lee
Venue: Accepted by TMLR ()

Abstract: Temporal-difference (TD) learning is widely regarded as one of the most popular algorithms in reinforcement learning (RL). Despite its widespread use, it has only been recently that researchers have begun to actively study its finite time behavior, including the finite time bound on mean squared error and sample complexity. On the empirical side, experience replay has been a key ingredient in the success of deep RL algorithms, but its theoretical effects on RL have yet to be fully understood. In this paper, we present a simple decomposition of the Markovian noise terms and provide finite-time error bounds for tabular on-policy TD-learning with experience replay. Specifically, under the Markovian observation model, we demonstrate that for both the averaged iterate and final iterate cases, the error term induced by a constant step-size can be effectively controlled by the size of the replay buffer and the mini-batch sampled from the experience replay buffer.

Published in Transactions on Machine Learning Research (07/2024)
Finite-Time Analysis of Temporal Difference Learning with Experience Replay
Han-Dong Lim
lmmrries30@aaist.cc..
Deportment of Electrical Engineering Korea Advanced Institute of Science ond Technology
Donghwan Lec
donghwann oc..rr
Deportment Electrical Engineering Korea Advanced Institute of Science end Technology
Reviewed on OpenReview: https: // openreview. net/ forum? id= id= AbulffDBD
Abstract
Temporal-differenee (TD) learning widely regarded as one of the most popular algorithms in reinforcement learning (RL). Despite its widespread use, it has only been recently that researchers have begun to actively study its finite time behavior, including the finite time bound on the mean squared error and sample complexity. On the empirical side, experience replay has been key ingredient in the success of deep RL algorithms, but its thcoretical effects on RL have yet to be fully understood. In this paper, we present a simple decomposi- tion of the Markovian noise terms and provide finite-time error bounds for tabular on-policy TD-Icarning with experience replay. Specifically, under the Markovian observation model, we demonstrate that for both the averaged iterate and final iterate cases, the error term induced by constant step-size be effectively controlled by the size of the replay buffer and the mini-bated sampled from the experience replay buffer.
1 Introduction
The pioneering Deep Q-network (DQN) (Mnih et al. 2015) has demonstrated the vast potential of reinforce- ment learning (RL) algorithms, having achieved human-level performances in numerous Atari games (Belle-
mare et al. 2013). Such successes have fueled extensive research efforts in the development of RL. algorithms,
c.g.. /Seakk 22019] y Mnih et al. (2016) to name just few. Beyond video games, RL has showcased notable
performance in various fields, including robotics (Singh et al.
2020) and finance (Liu et al. 2020).
On the other hand, temporal-diiference (TD) learning (Sutton 1988
considered one of the most fun- objective is to learn the value function, which represents
damental and well-known RL algorithms. the expected of discounted rewards following particular policy. While asymptotic convergence of TD-learning (Jaakkola et al. 1993 Bertsekas & Tsitsiklis 1996) has been extensively studied and is now well-understood, such asymptotic analysis cannot measure how efficiently the estimation progresses towards a solution. Recently, the convergence rate TD-learning has gained much attention and has been actively investigated Bhandari ot al. the efliciency of the estimation process, and provide theoretical guarantees on the rate of convergence.
2018 Srikant & Ying 2019 Lee & Kim 2022p. These studies aim to understand
First appearing in Lin 1992 experience replay memory be viewed first-infirst-out queue and is one of the principal pillars of DQN (Mnih et al. 2015). Learning through uniformly random samplings from the experience replay memory, the strategy is known to reduce correlations among experience samplings, and improve the efficiency of the learning. Despite its empirical successes (Muih el al. 2015 Fedus el al. 2020 Hong et al. 2022), the theoretical side of the experience replay memory techniques remains largely an open yet challenging question. Only recently, Di-Castro et al. (2022 2021 studiod asymptotic convergence of actor-critic algorithm (Konda & Tsitsiklis, 1999) with experience replay memory. To the authors' knowledge, its non-asymptotic analysis has not. been thoroughly investigated in the context, of TD-learning far.

---

Published in Transactions on Machine Learning Research (07/2024)
The aim of this paper is to investigate the impact of experience replay memory on TD-learning (Sutton 1988), with the goal of shedding light on the question at hand. Our primary theoretical contribution is the derivation of the convergence rate of tabular on-policy TD-eerrnng with experience replay memory under Markovian observation models. This analysis reveals connections between the sizes of the mini-batch and experience replay memory, and the convergence rate. Specifically, we show that the error term, resulting from correlations among the samples from the Markovian observation models, can be effectively controlled by the sizes of the mini-batch and experience replay memory, for both the averaged and final iterate cases. We expect that our findings can provide further insights into the use of experience replay memory in RL algorithms.
Lastly, although our analysis only considers the standard TD-learning case, our presented arguments can be extended to more general scenarios, such as TD-learning with linear function approximation (Srikant &
Ying 2019 standard Q-learning (Watkins & Dayan 1992). periodic Q-learning (ee & He 2019
1.1 Related works
Experience replay. We begin by providing an overview of the existing theoretical results on experience replay. The recent work by Nagaraj et al. (2020) leverages the experience replay memory to address the least- squares problem under the Gaussian auto-regressive model. However, there are several notable differences between their approach and the proposed TD-learning with experience replay memory:
1. The approach in Nagaraj et al. (2020) assumes i.i.d. Gaussian noises, whereas the proposed TD-learning with experience replay memory covers Markovian and specific non-Gaussian noises.
2. The overall algorithmic structures are significantly different. Nagaraj et al. (2020) considered an oflline learning problem, while the proposed TD-learning framework is an online learning approach.
3. When operating the experience replay buffer, they maintain a sufficiently large gap between the separate samples inside the buffer to ensure the samples are almost identically and independently distributed.
4. The approach by Nagaraj et al. (2020) uses an inner loop to iterate over the samples in the buffer, whereas the proposed framework considers mini-batel style updates, which is widely used in practice.
Kowshik al. (021) presented an algorithm that employs the reverse experience memory approach proposed in |Rotinov (2019) to tackle linear system identification problems. This algorithm guarantees non-asymptotic convergence, and the reverse experience replay technique [Rotinov] 2019 involves using transitions in reverse order, rather than uniformly and randomly, without introducing any stochasticity, which distinguishes it from
the original experience replay method introduced in Mnih et al. (2015). Kowshik et al. (2021) assumes an regressiee model with i.idd noise. Following the spirit of Nagaraj et al. (2020), Kowshik et al. (2021) also maintains a gap between separate samples to enforce independence between the samples.
Using the super-martingale structure of the reverse experience replay memory, Agarwal et al. 2021 de- rives the sample complexity of Q-learning, which also maintains a gap between samples. Morcover, the works, Kowshik et al. (2021) and Agarwal al.) (2021) both exploit full samples from each experience replay memory rather than applying uniformly sampled mini-batch to maintain the reverse order property.
Lazic al. (2021) presented a regret bound analysis for regularized policy iteration with a replay buffer in the context of averaged reward Markov decision processes (MDPs). The authors assume that an accurate estimate of the action-value function is available, which is obtained via Monte Carlo methods (Singh & Sutton 1996). as opposed to the TD-Icarning algorithm (Sutton 1988). The use of experience replay memory is modified from Muih et al. (2015). One approach suggested in Lazic et al. (2021) involves storing all data from each phase, with a limit on the size of the replay buffer. When the buffer size exceeds the limit, a subset of the data climinated uniformly at random.
Fan et al. 2020) established a aoy-asympt convergence of fitted Q-learning (Ernst et al. 2005), which assumes i.i.d. sampling of transitions from a fixed distribution. This assumption is stronger compared to the Markovian observation models used with the time-varying replay buffer. The Markovian observation model is more natural and realistic scenario than the i.i.d. modeling, which improves practicality of the
2

---

Published in Transactions on Machine Learning Research (07/2024)
analysis. Furthermore, The replay buffer technique is different from the sampling i.i.d transitions because in the mini-batch approach, the samples are from single episode trajectory in a moving window, which are highly correlated, and the correlation increases proportionally to the size of the window. Lastly, Fan ct al. (020) imposed a condition that the fixed distribution satisfics a particular condition such that it is similar to the true underlying distribution over the stale-action space, which may not hold in our setting. Morcover, the fitted Q-iteration is similar to stochastic gradient descent algorithm in supervised-lcarning problem, whereas TD-learning is an online learning algorithu which does not use any (stochastic) gradient of an objective function.
A closely related approach to our work is presented in Di-Castro et al. 2022, which establishes the asymp- totic convergence of the actor-critic algorithm (Konda & Tsitsiklis 1999) using a mini-batch that is uniformly and randomly sampled from the roplay buffer. The proof relies on treating the replay buffer and mini-batch indices as random variables, which logether form an irreducible and aperiodic Markov chain. Following the O.D.E. approach outlined in BBorkrr & Meyn (2000) and the natural actor-critic algorithm described in Bhat- nagar et al.) (2009), Di-Castro et al. (2022) establishes the convergence of the actor-critic algorithm using the replay buller. among samples in the experience replay, their proof of asymptotic convergence does not explicitly address the impact of these factors on the convergence behavior. However, the study provides important insights into the convergence properties of actor-critic algorithms using the replay buffer and highlights the potential benefits of using mini-batches to improve the convergence rate.
Di-Castro et al. [2022 demonstrates decrease in aulo-correlation and covariance
Non-asymptotic analysis of TD-learning We highlight several recent studies on finite time behavior of
TD-learning (Lee & Kim 2022 Bhandari et al. 2018 Chen al. 2020 Srikant & Ying 2019 Dalal ct al.
2018 Hu & Syed 2019). Under an i.i.d. observation model and linear function approximation setting, Dalal
et al. (0188) derived O (1²) bound on the mean squared error with diminishing step-size (4+17² where E (0, 1) and k is the number of iterations. Under an i.i.d. observation model and tabular setup, from the discrete-time stochastic linear system perspective, Lee & Kim (2022) provided geometric convergence rate with constant error at the order of O(a) of TD-learning for both averaged iterate and final iterate using constant step-size a. Bhaanari et al. (2018) provided convergence rate of TD-learning with linear function approximation under the Markovian noise following the spirit. of convex optimization literature (Nemirovski et al. 2009). With the help of Moreau envelope (Parikh et al. 2014), Chen et al. (2020) derived a convergence rate of TD-lcarning with respect to an arbitrary norm. Mainly based on the Lyapunov approach (Khalil, 2015) for continuous time O.D.E. counterpart of TD-learning, [Srikant & Ying (2019) derived finite time bound on the mean squared error of TD-learning under Markovian noise with linear function approximation.
In contrast to the existing studies that have focused on the finite time behavior of TD-learning (Lee & Kim 2022. Bhandari et al.] 2018; Chen et al. 2020 Srikant & Ying, 2019 Dalal et al., 2018 Hu & Syed 2019)) our work investigates the finite time behavior of TD-learning with experience replay, which has not been thoroughly studied to date. Specifically, we demonstrate that the use of experience replay can be an effective mcans of reducing the constant error term that ariscs from employing a constant step-size. Our findings may provide valuable insights into the effectiveness of experience replay in RL, shedding new light on the benefits of this widely-used technique. Further research in this area could yield important research topics, with implications for the development of more efficient and effective reinforcement learning algorithms.
2 Preliminaries
2.1
Markov chain
In this section, basic concepts of Markov chain are briefly introduced. To begin with, the so-called total variation distance defines the distance between two probability measures follows.
Definition 2.1 (Total variation distance (evvin & Peres 2017) ). The total variation distance between two probability distributions, ii and P2, on S is given by
dTv((1, = sup 1M (A) (2()))
ACS
3

---

Published in Transactions on Machine Learning Research (07/2024)
Let us consider Markov chain with the set of states S == (1,,....,18) and the state transition probability P. For instance, a state E S transits to the next state s' with probability P(s, 8'). A stationary distribution of the Markov chain is defined as a distribution E R2||| on S such that j === where P E ||S|i|s| is the transition matrix of the Markov chain, i.e., [Plr = p(i for i,j E.
Let {Se) be a trajectory of a Markov chain. Then, an irreducible and aperiodic Markov chain is known to admit a unique stationary distribution I such that the total variation distance between the stationary distribution and the current state distribution decreases exponentially (Levin & Peres 2017 as follows:
sup drv (P[S, So s), S mp sE8
for some p (0, 1) and positive m E IR. The mixing time of a Markov chain is defined as
(eix == min { k E E+ supdTv = So = s1,14) =0s5),1) se}
(1)
ESS
for any E R4. Throughout the paper, we will use tii to denote tmix (1) for simplicity.
2.2 Markov decision process
A Markov decision process is described by the tuple A,, P,P,), where S = (1.2..... [S]].....]]]]]] is the set of states, A .1, reward function, and P S x A x S + [0, 1] is the state transition probability, i.e., P(s, 5') means the probability of the next state s' E S when taking action a E A at the current state s E S. For example, at state S% E S at time k if an agent selects an action ak, then the state transits to the next state sk+1 with probability P((k, ak, sk+1), and incurs the reward r(sk; ak, Sk+1), where the reward generated by the action at time k, r(sk, aks 8k+1), will be denoted by rk+1 == r(sk, axs 8841). ). In this paper, we adopt the standard assumption on the boundedness of the reward function.
[A]} -AA}
is the set of actions, y 1) is the discount. factor, 8 x A S - R is the
Assumption 2.2. There crists positive Rmax R such that |r(s, a, s'Il S Ruuax for all 8, a, s E Ax
Let consider a Markov decision process with the policy, क : S x A + [0. The corresponding state trajectory, {Sk J220, is a Markov chain induced by the policy and the state transition probability is given by pD : S x S > 1], i.c., (s"(s,'') == EaeA P(s,, a, s')x(a | s) for 8,5' E S. Throughout the paper, we assume that the induced Markov chain with transition kernel pa is irreducible and aperiodic so that it admits a unique stationary distribution denoted by n²_,, and satisfies the exponential convergence property
supdrv(P[se = So = =s). ) mipt, k 2 #ES
(2)
for some positive my E R and E 10, Let (Sk, S841) E O be a tuple of states at time step k and its next state Sk+1 ~ Pn (St. "), which will be frequently used in this paper to analyze TD-learning, and O denotes the realizable set of tuples consisting of a state and its next state, i.e., for (a, y) E S x S, we have (r, E O if and only if (Ir 3) > O. Then, the tuple forms another induced Markov chain. The transition probability of the induced Markov chain ((Sk, Sk+1) is P[S Sx+1 S*+1; Sx) P[S Sk+1), which follows from the Markov property. The next lemma states that the Markov chain {(Se, Sk+1) h220 is also irroducible and aperiodic provided that (Sx Ja20 is irreducible and aperiodic.
Lemma 2.3. If 1Sk is an àrreducible and aperiodic Markov chain, then so is {(S), 11+1)
The proof is in Appendix Section
A.3 Now, let us denote _ as the stationary distribution of the Markov chain {(S,, Sx+1) which satisfies the relation between 16__ and p3
Σ x(a a) (s) (s. (s) 13 S% (s) AEAA
(3)
Then, from Lemma 2.3 we have sup(s.rresxsdry ((SS, = 1 (s,s)))sss))) 33. S mapti
for some positive m2 E R and p2 E (0, Similar to the original Markov chain, the mixing time can be
4

---

Published in Transactions on Machine Learning Research (07 (224))
defined for this new Markov chain. Throughout this paper, adopt the notations, tyrx and ty to denote the mixing time of the Markov chain {Se and the mixing time of {(Sk, Sk+1))220, respectively. For simplicity of the notation, we will denote - ;= m :22 (
2.3 Temporal difference learning
To begin with several matrix notations are introduced. Let define
PSS.. (1)
a, 8'18 1]
M3 (2)
al
D"
E R SixIS
R
E RRS
1/ (1S))
R[r(s, a, 8')8 [Si]]
where RD defined above is a vector of expected rewards when action is taken under n. From Assumption 2.2 one can readily prove that R bounded as well.
Lemma 2.4. We have || 1bc S Rmmax.
Moreover, in this paper, ps E RiSii|Si denotes the transition matrix under the policy L.e, [P PT (i
for i E S, where [sy denotes the element in the i-th column and j-th row. The minimum probability in the stationary state distribution is denoted by Mmin == min.es 13 (8).
Proposed in Sutton 1988
TD-leanning aims to estimate the value function VT(() ==
Ex [T So S
through the following stochastic recursion for k 2
VR+1 = V/2 + adOOk, Va),
(4)
where a E (0,1) a constant step-size, On = (sk, Tk+1, sk+1) and called the TD-error defined as 8(0k, Vv.) Cag le + yes e Vo Cay e. Va,
(5)
where Esg, is the basis vector in IR||| whose sk-th element is one and all others are zero.
3
Main results
3.1
TD-learning with experience replay
In this subsection, we introduce the proposed TD-learnin method employing the original experience replay memory technique from Mnih et al. (2015) with no significant modifications. Experience replay memory, commonly referred to as the replay buffer, is first-in-firstouu (FIFO) queue that facilitates the adoption of mini-batch techniques in machine learning for online learning scenarios. Specifically, the replay buffer stores the slate-action-rewarte transitions in a FIFO manner, serving as the training set. At each step, a mini-batch is uniformly sampled from the replay buffer and utilized to update the learning parameter V₁. This approach presents dual advantages. Firstly, it enables the application of the batch update scheme, thereby reducing variance and accelerating learning. Secondly, through uniform sampling, it may reduce correlations among different samples in the Markovian observation models and consequently reduce extra biases in the value estimation. Despite its empirical benefits, theoretical studies on replay buffer have been limited.
In this paper, we employ the notation B and Mg to represent the replay buffer and mini-batch. respectively, at time step h. They are formally defined as follows:
M (Ot, of..o,
Ot,,
B. (Ok-N+1, On 100-N+1;O--N-000 N Ok);
where the replay buffer's size is N, the of the mini-batch ME. For the first N steps, only the observations, O-N from O-1 , is collected without updating the Vg. That is, at time-step k; O₂ is observed and V& is updated using a mini-batch M sampled from batch B The overall scheme is depicted in Figure 1
size is L, and O sis S L stands for the i-th sample
For each time step à 2 0, the agent selects an action ag following the target policy x, and observes next state Sk+1. The oldest sample (sk-N, aa--N.a--- N S&-N+1) is dropped from the replay buffer B and the new sample (8k, az 11+1) is added to the replay buffer, which becomes B
5

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Next, mini-batch of size L, Mf. is sampled uniformly from the replay buffer B at time step k, and the k + 1-th iterate of TDllearnin is updated via
Ve+1 = V& ak
E (STT)"))
(ex)(r + + -e, Vx),
(6)
ME
which is batch update version of the standard TD-learning. Note that when -
| for all k 2
the update in ( matches that of the standard TD-lcarning in 4 In this paper, we consider a constant step-size E 1), and the Markovian observation model, which means that transition samples are obtained from a single trajectory the underlying Markov decision process.
Agent
V(aa) Vlec)
E (r+aV(6)-
MT
Replay butfer B
M2 (
Mini-batch ME
[8k, 7 8k++1)
8k
8k+11
Delay
Environment
5k--1 7k++1
Figure 1: Diagram of TD-learning using experience replay
Algorithm TD-Jearnin with replay buffer
1: Initialize Vo E RlSS such that |[Vol S Rasx T-7 Collect N samples B-1 = NO.I.,O 0-1}.
3: for & & T do
4: Select action
T(-(s)).
5: Observe 8k+1 ~ "P(1ssk, ax) and recieve reward rst1 := r(8k, ax. 8k+1). Th+1, (6+1))))
Update replay buffer B + B
Uniformly sample M B
Update V4+1 Vv + O MET E(ens)eM
-e VR).
9: end for
To proceed with our analysis, we should establish the boundedness of the iterate resulting from the up- date in (6), assuming that ||Vo|oo s Rmax and that as E (0, This assumption is crucial to our main developments, and thus requires rigorous proof.
T-y
Lemma 3.1. Under the recursion in 1 V2 remains bounded ||Vill>o & Buns 1-y
The proof is given in Appendix Section A.4
3.2 Analysis framework
In the previous subsection, the algorithm underlying our analysis was introduced. In this subscction, we provide the preliminary frameworks for our main analysis. Specifically, we analyze TD-learning based par- tially on the linear dynamical system viewpoint, as presented in the recent work by Lee & Kim (022).
particular, using the Bellman equation (Bertsekas Tsitsiklis 1996), D=V D pa V D R we can
express the TD-learning update as follows:
Vet1 V A(Va V*) + oo(ME Vx),
(7)

---

Published in Transactions on Machine Learning Research (07 2024))
where
A == I=I--D D0
(8)
is the system matrix, and
w(M Vi)) = IME
Σ +c - V. D (R + - VVt)
(9)
(s.T,")
is the noise, which is the difference between the empirical mean of the TD-error via samples in mini-batch and the expected TD-error with respect the stationary distrribution 10
Some useful properties of the system matrix A (boundedness of A, and related Lyapunov theory (Chen 1984) are introduced in the next lemma, which play central roles in establishing the convergence rate.
Lemma 3.2 (Properties of matrix A (Lee & Kim 2022
1) ||l < - a(1 - Pit holds.
2) There exists positive definite matria M > 0 and || S
2|S] such that a(I->)mmm
A MA M --I.
(10)
For completeness of presentation, the proof is given Appendix A.5 distributions for j.j 8,
To proceed, let us define the empirical
Σ 1(s =
Σ 1((8,')= ((t,5) (s
B Ms (1)
(ST
B7 (s..s
[B
which denote the empirical distributions of the state s and the tuple (s, 8') in the replay buffer B respec- tively. Moreover, for an event A, the notation 1(A) denotes an indicator function that returns one the event A occurs and otherwise zero. Purthermore, let introduce the following matrix notations for i, E S:
Σ
[((,,')=((1}}}
D ky : Ms Ms
{
B (1) if i=j
1 =
Σ
[{=1]
if [B*(1)2 21
otherwise
otherwise
which define the empirical distribution of the state the replay buffer and (s) = ((,,,,8') E B : B7
8} C B". With above definitions, we can readily verify the relation [DB pBt ]es 1s (i.j) for i,j E.
Likewise, let us define the empirical estimation of the expected return, which is averaged over the action, a, and next state, s'. It is calculated from the samples of the replay buffer follows for i S:
Σ
(e.ra"))
if |B 21
[n
Σ
1(si))
otherwise
3.3 Bounds on noise
Our aim in this subsection is to bound the first and second moment of [[W[M V4)llp where w(M Vx) is defined in (9), which will play important role in deriving the convergence rate. For simplicity, let further define the functions, A+ R| + Rl and A S + S as follows:
A+(V) BE B BBR DBVV.
(11)

---

Published in Transactions on Machine Learning Research (07/2024)
= D" +DD"P"V - DVV.
(12)
The functions, A and Ag, can be viewed as expected TD-errors, respectively, in terms of the distribution of the replay buffer and the stationary distribution of the Markov chain. Morcover, note that A=(V") = 0. Based on the notations introduced, the noise term, w(ME V&), can be decomposed into the two parts
M
oo MOME, = M
Σ
8 V2) - (v(V)) - (A+(V) - (v+))),,
(13)
where
MM Σ Mi 800,, V&) Av(V)): the difference between the empirically expected TD-error with respect to the distribution of mini-batehh and empirically expected TD-error with respect to the replay buffer.
(v the difference between the expected TD-error with respect to the stationary distribution and the empirically expected TD-error with respect to the distribution of replay buffer.
The high level idea for bounding the first and second moment of [|u[M Vi)ll2 summarized below.
1. MET EM 810 Vi) (v&)),, the error between the empirical distribution of the mini-batch and the replay buffer, can be bounded by Bernstein inequality (Tropp et al. 2015) because the mini-batch samples are independently sampled from the replay buffer with the uniform distribution.
(V&) A& (V&), the error between the stationary distribution and distribution of replay buffer, can be bounded using the property of irredueible and aperiodic Markov chain (Levin & Peres 2017).
Next, introduce several lemmas to derive bound on the the first moment of [[ V4) which be bounded at the order of O (v ( To bound (v())) Av(V),, we introduce the coupled process {Se)E2-N, which starts from the stationary distribution of the Markov chain with transition kernel p", i.e, S_N ~ _ Let B the corresponding replay buffer such a Markov chain. We first derive the expected error bounds in terms of the coupled process {Sk) and the desired result will be obtained using the total variation distance between the distribution of Sg and St. The detailed proof is given in Appendix A.6 Now, combining with the bound 1 concentration iequalitiess we get the following result::
Σ MM i1 5(0), V&) Ae(V)), which follows from [M
Lemma 3.3. For 2 0, [l V2) can be bounded as follows:
4/ SVSSRRmax 1 1-y
(2
2 (2g((2)S)) M
mix
+16 - w
Elll Vo)lla] <
(
+ +3|5|
[ +
The detailed proof is given in Appendix Section A.7 Using similar arguments to bound the first moment of [MM, Vi)llps we can bound the second moment, which given the following lemma.
Lemma 3.4 (Second moment of [[, V+)]lz). Let us consider the noise term, w(Ms, Vw), is defined in
For l 0, the second moment of [MoMM, Va)lla is bounded as follows:
E [ Vil12] < (|ma + 1)2 (20(()g()))))² + +188
SISidrv(uss v3c.x))
71-
M
B
The proof is deferred to Appendix Scction A.8 for compactness of the presentation.
3.4 Averaged iterate convergence
In the previous subsoction, we derived bound on the noise term. Based on it, in this subscction, we analyze the convergence of the averaged iterate of TD-learning with experience replay. In the next theorem, we present the main result. for the convergence rate on the average iterate.
8

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Theorem 3.5 (Convergence rate average iterate of TD-learnnng. Suppose N > mie
1) For T 2 0, the following inequality holds:
2|8] T Ta(1 7)
S| R max
8 8log(2[8))
T EILV
vo
BIIIV
v*12]+
P
Concentration ervor in the first moment
+
32 32|5|2 maa
2|S] |4
T N
mix
64f
(14)
(1 7)
T
bank; Mankovian noise first moment
+ 4 | 1)²
1200 2((S1))2
11-2)8m
L
0 Concentration error in the second moment
4|S) + +1?
(415141A12 T mix
32t
+ a (1 7))ppinn
N +
T
B Markovion noise in the second moment
2) Por 2 0, the following inequality holds:
E
1 -
T
vo-
S
1
2|8]
11Vo V 122 112 + #V (1 - 2 Mmin
32 R2 max
8log(2|S1)
T
a(1 -
L
R max
m
64tqpix
+
2/5 2/15
(1 7)
N
T
4/5 (Rimax
+ +)2 (20(1og(2|S1))
+
(1-7)3m(m) 3
L
4/8/2
1)2 (418)4]112
7 mix
32tmix
(1-7)$ 3
The proof is given in Appendix A.9 Several comments can be made about the results in Theorem 3.5 The
term (14 arises because [[((V, V*) AT Mw(Mg, V&]] is not zero in comparison to the i.i.d. sampling update in 4 This is due to the Markovian noise and correlation between V& and the samples the replay buffer. As discussed in Soction 3.3 the bound on the term E V= AT Mw(MM, V&)] can be decomposod into two parts: the concentration error corresponding to the mini-batch uniformly sampled from the replay buffer, denoted Favs, and the Markovian noise term, denoted as Eave The first part, Favg can be controlled by the size of the other hand, the Markovian noise term, Ea can be controlled by the size of the replay buffer, decreasing at the order of O
decreasing at the order of O { as shown in Lemma. 3.3 On the
The terms, E and E arise from the second moment of (M] V These terms are non-zero in both i.idd. sampling and Markovian noise cases under the standard TD-learning update 4 However, the errors can be controlled by the size of the mini- batch and replay buffer, as shown in Lemma 3.4 Specifically, Eng Ea and Favg can be decreased at the order of O (1) and O (2), respectively.
Furthermore, the condition N mix is standard in the literature in sense that the analysis of Markovian observation model holds after quantity related to mixing time (rikant & Ying 2019 Chen et al. 2022 ,ii is only logarithmically proportional to the minimum of the stationary distribution, i.e., 7 _IIx v log Puij
where Pmin min (ming 13_..s, (s, (mnn) Assuming uniform transition matrix, i.e., P(s, 8¹) [ 1 for all s, s' S, have pini 2, and we have mix Slgg(
9

---

Published in Transactions on Machine Learning Research (07/2024)
Table 1: Comparitive analysis on results of root mean squared error of averaged iterate convergence using
constant step-size.
Observation
Initial
Method
Experience replay
Step-size
Feature
model
distribution
Ours
Markovian
a E (0,
Tabular
Arbitrary
Bhandari et al.
X
Markovian
Linear
Stationary
(2018)
vT
Lee & Kim
i.dd.
a E (0,
Tabular
Arbitrary
(2022)
Lakshmi-
narayanan
iid.
Universal
Linear
Arbitrary
Szepesvari (2018)
The paper Bhandari et al. 2018 adopted the assumption that the initial state distribution is already the stationary distribution for simplicily of the proof. Moreover, [akshminarayanan & Szepesvari (2018) derives convergence rate of O()) for general linear stochastic approximation problems. The universal step-size means that the step-size is dependent on the general linear stochastic approximation problems.
3.5 Comparative analysis
Table Mooleeppreeee presents a comprehensive comparison of the finite-time analysis of TD-leannin. In the context of on- policy linear function approximation, and under the assumption of starting from the stationary distribution, the work presented in [Bhandari et al. (2018) derives the following convergence rate of _ for the averaged iterate of TD-learning with a constant step-size, where T represents the final time of the iterate:
VT
50 () 2(1 Hmmi VT
log
T Vx Σ k=
Va
2
Notably, our result does not impose any condition the step-size E (0, 1), indicating that the use of experience replay memory can ease the strict requirements for selecting a constant step-size. Moreover, we can achieve fast convergence rate while maintaining small constant error by controlling the size of mini-batch and replay buffer instead of controlling the step-size. The result in Lee & Kim (2022) also holds for general step-size condition, but to obtain smaller bias, it requires small step-size yielding slower convergence rate.
Under the i.i.d. observation model and linear function approximation, Theorem 1 in Lakshminarayanan & Szepesvari (2018) provides O [1] convergence rate for the root mean squared error using specific step-size depending on the model parameters, which cannot be known beforehand in TD-learning. The work assumes a more general setup. However, the step-size condition depends on not only the feature space but also pmin: the minimum state-visitation distribution even in the tabular case.
3.6 Final iterate convergence
In the preceding subsection, we presented a finite-time analysis of the averaged iterate. this subsection, we extend our analysis to investigate the convergence the final iterate in TD-learning with a replay buffer, following a similar approach to the one used in the previous section. Instead of using Lyapunov arguments, we utilize the recursive formulas and the fact. that. |||]|> averaged iterate analysis, assume that the initial distribution corresponds to the stationary distribution
given in Lemma 3.2 In contrast. to the
of the Markov chain, common assumption in the literature (Bhandari et al. 2018 Nagaraj et al.) 2020 Jain et al. 2021). With the assumption, we are able to derive the convergence rate of the final iterate. Theorem 3.6. Suppose S-N ~ m3..
1) For any 2 0, we have
|1V - 11]] < - V" S|(1 a(1 - ) 22++2
10

---

Published in Transactions on Machine Learning Research (07/2024)
64|5|2 R
8 log(22[5)
64 1 |LA| R
+
(1 - 3
(1 7-7
Concentration error first moment
Buual Mankovian noise the first moment
(15)
4|8[ + 1)2 (20 2|S1) (1 - (1-7)8 N
16| 16)
(Rmaxx max 1) mix
(1 u N
gfiaal Concentration error second moment
Eliund Markovian second moment
2) For any & 2 0, we have
E l1VV (1ll - VoIl2 (1-11111) min )++1
8|S|
(log(2|SS)
Tmix +2)5|||AA1
(16)
(1 7) (M
L
N
+ Va 2|5) (Riax + 1)
(00log(2SS) 411/ m
(1 (1) (mmin))
L
N
The proof is given in Appendix Section A.10 In manner similar to the case of the averaged iterate, the term (15) arises due to the non-zero value of E[(VV - -V" (
( Mw(ME. V&)] as compared to the i.i.d. sampling update with ( This non-zero value is caused by Markovian noise and correlation between V& and the samples in the replay buffer. As explained in Section 3.3 the bound on the term B[
VT)TA A Mw(ME, Vx]] can be decomposed into two parts: Efmal, which the concentration error of uniform random sampling, and Efinal, which is the Markovian noise term. As can be seen from Lemma 3.3 Effial can be controlled by the size of mini-batch, where it can be decreased at the order of O (+z)
Moreover,
the Markovian noise Lafinalaan be controlled by the replay buffer size, decreasing at the order of O
VN
The error bounds provided in above are new in the sense that the it shows dependency on the size of the replay buffer which can be controlled by adjusting the buffer size, L and N.
Note that the assumption on the initial distribution is for simplicity of the proof, and it was also used in Bhandari et al. (2018). The assumption can be relaxed to more practical case that the initial distribution is arbitrary with some more efforts. To this end, we can bound the error caused by the initial distribution using the condition in (2). As from Bhandari et al. (2018), we bound the error by O(a), which will ultimately result in O(a) in the final error bound. However, such error is dominated by the O(a)) ) term in the error bound. Therefore, it does not significantly impact the convergence rate or the sample complexity.
3.7 Comparative analysis
The overall comparative analysis is given in Table 2 Under the Markovian assumption and on-policy linear function approximation, Bhandari et al. (0118) provided final iterate convergence under the constant step-size a smaller than
Pum (1-7)+ which is
E [ V (e- (e-a(1-3)Amin)) 1 -Vol2 +
(9 12 (a:) 2(1 3 Mminn
(17)
Error from constant step-size
Although the constant step-size is a widely used method, incurs constant error terms. However, the use of experience replay can reduce these errors. Specifically, as stated in the second statement of Thcorem 3.6 the term 166 decreases at the order of O + Furthermore, in the averaged iterate case, since we do not impose any condition on the step-size, we can achieve fast convergence rate while maintaining small error by controlling the size of mini-batch and replay buffer instead of the step-size.
The work in Loe & Kim 20022) provided a final iterate convergence of tabular TD-learning with a constant step-size and i.i.d. observation models, where the step-size induces constant errors proportional to O(va).
11

---

Published in Transactions on Machine Learning Research (07/2024)
Table 2: Comparitive analysis on results of root mean squared error of final iterate convergence using constant
step-size
Experience replay
Observation
Method
Step-size
Feature
Constant error term
model
Ours
Markovian
a E (0, 1)
Tabular
N
Bhandari et al. (2018)
X
Markovian
Model dependent
Linear
(Valog(()
Lee & Kim
iid.
a E (0,
Tabular
O(va)
2022)
Srikant. &
Model dependent
X
Markovian
Linear
O(va)
Ying (2019)
Dalal et al.
(k+1))* 0 E (0.1)
i.i.d.
Linear
( a E (0,1)
2018))
Model dependent step size implics that the step size depends on model parameters, e.g., maximum eignevalue of matrix A, discount factor 7, mixing time.
The approach in Srikant Ying 2019) provided a mean squared bound of TD-learning under linear function scheme and Markovian observation models, which is given by E -Vr--ve v where C1. 02 are model dependent parameters, and is the mixing time such that Vk > | pr - D (E [ne Eacss - -e ]]l2 I and || RT - E [e], HtT < However, the choice of the step-size depends on the mixing time and the model parameters.
- s 0 ((L- (1-ac,)² act)"=² + c2ar
Under the ii.d. assumption and using lincar function approximation, Dalal et al. 20188 derived (++), a E 10,1) bounds on the mean squared error bound, which is worse than O ( convergence rate. Since we used constant step-size, the result is not directly comparable.
Furthermore, our approach addresses scenario that standard TD-learning analysis cannot Suppose starting with pre-existing dataset before transitioning to online learning, a topic of recent interest (Song et al. 2022). Then, the convergence rate,
becomes faster as we choose large a, which possible thanks to
(n()) number of samples for [I[V - V*][] S 6 hold for (1-7)
a E (0, 1). This will only require δ
> 0, which is the so-called sample complexity. In other words, if we exclude N in the sample complexity, permitting large yields better sample complexity. However, as discussed in Appendix A.11
LA), A.111 if we take into (1-7) (u 1" à can be sub-optimal
account N in the sample complexity, the overall sample complexity Ö
in terms of T- an Pmin: compared to the result of Ô " (1e y2 by Bhandari et al. 2018
piix
22
Morcover, introducing and N can relax the condition on a for the convergence in expectation to hold. The related works require condition on a for the convergence statement to hold. However, we do not require such conditions, while the error can be controlled by and N. Moreover, the convergence statement holds for arbitrary (0, 1), L, and N where N only dependes on the mixing time, mix
Lastly, we would like to emphasize that our main contributions are as providing the first analysis of rein- forcement learning in setting that closely resembles the deep Q-learning approach described in Mnih et al.) (2015) within the TD-learning framework, and providing rigorous analysis on the relation between the error bound and the mini-batch size (L), and the replay buffer size (N) within the TD-learning framework. We hope these contributions will provide valuable insights to the community. In particular, the error bounds given in our paper are new in the sense that the it depends on the size of the replay buffer which can be controlled by adjusting the buffer size. For instance, the constant error ball caused by the constant step-size can become arbitrarily small by increasing the buffer size.
12

---

Published in Transactions on Machine Learning Research (07 (224))
4 Conclusion
In this work, we have undertaken analysis of the behavior of TD-eearnin utilizing experience replay memory under Markovian obscrvation model, which has thus far been unexplored despite the prevalence of experience replay memory in RL algorithms. By leveraging simple matrix concentration inequality and the geometric mixing property irreducible and aperiodic Markov chains, we have demonstrated that the expected root mean squared error the averaged iterate of TD-learning can be reduced at the order of under the constant step-size. Similarly, for the final iterate case, have established that O ( + (+)
the root squared error can be effectively reduced the order of + Potential avenues for future research include extending the proposed analysis frameworks to off-policy and linear function approximation settings, well as investigating the applicability of these results to Q-learning.
5 Acknowledgement
The work was supported in part by the BK21 FOUR from the Ministry of Education (Republic of Korea); and in part by the Institute of Information Communications Technology Planning Evaluation (TTPP) funded by the Korea government under Grant 2022-0-00469. The work was supported by KT Corporation as part of the KT-KAIST Open R&D project.
References
Naman Agarwal, Syomantak Chaudhuri, Prateek Jain, Dheeraj Nagaraj, and Praneeth Netrapalli. Online target q-learning with reverse experience replay: Efficiently finding the optimal policy for linear mdps. arXiv preprint arXiv:2110.08440, 2021.
Marc G Bellemare, Yavar Naddaf, Joel Veness, and Michael Bowling. The arcade learning environment: An evaluation platform for general agents. Journal of Artificial Intelligence Research, 47:253 279, 2013.
Dimitri Bertsekas and John N Tsitsiklis. Neuro-dynamic programming. Athena Scientific, 1996.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pp. 1691-1699) PMLR, 2018.
Shalabh Bhatnagar, Richard Sutton, Mohammad Ghavamzadeh, and Mark Lee. Natural actor critic
algorithms. Automatica, 45(11):2471-2444 -2482, 2009.
Vivek S Borkar and Sean P Meyn. The ode method for convergence of stochastic approximation and reinforcement learning. STAM Journal on Control and Optimization, 38(2):447-40) 2000.
George Casella and Roger Berger. Statistical inference. Cengage Learning, 2021.
Chi-Tsong Chen. Linear syslem theory and design. Saunders college publishing, 1984.
Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. Finite-sample analysis of stochastic approximation using smooth convex envelopes. arXiv preprint Xrxv::2002.0 00874. 2020.
Zaiwei Chen, Sheng Zhang, Thinh Doan, John-Paul Clarke, and Siva Theja Maguluri. Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning. Automation, 146:110623, 2022.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shic Mannor. Finite sample analyses for td (0) with function approximation. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018
Shirli Di-Castro Dotan Di Castro, and Shie Mannor. Sim and real: Better together. Advances in Newral Information Processing Systems, 116868-6880) 2021.
Shirli Di- Di-Castro, Shie Mannor, and Dotan Di Castro. Analysis of stochastic processes through replay buffers. In International Conference on Machine Learning, pp. 5039-5060. PMLR, 2022.
13

---

Published in Transactions on Machine Learning Research (07/2024)
Damien Ernst, Pierre Geurts, and Louis Wehenkel. Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6, 2005.
Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q-learning. In Learning for Dynamics and Control, pp. 486-489. PMLR, 2020.
William Fedus, Prajit Ramachandran, Rishabh Agarwal, Yoshua Bengio, Hugo Larochelle, Mark Rowland, and Will Dabney. Revisiting fundamentals of experience replay. In Intervational Conference on Machine Learning, pp. 3061-3071 3071. PMLR, 2020.
Zhang-We Wei Hong, Tao Chen, Yen-Chen Lin, Joni Pajarinen, and Pulkit Agrawal. Topological experience replay. arXiv preprint arXiv:2203.1588 2022.
Bin Hu and Usman Syed. Characterizing the exact behaviors of temporal difference learning algorithms using markov jump linear system theory. Advonces in neural information processing systems, 32, 2019.
Tommi Jaakkola, Michael Jordan, and Satinder Singh. Convergence of stochastic iterative dynamic pro- gramming algorithms. Advances in neural information processing systems, 6, 1993.
Prateek Jain, Suhas S Kowshik, Dheeraj Nagaraj, and Praneeth Netrapalli. Streaming linear system identi- fication with reverse experience replay. arXiv preprint arXiv:2103.052: 055866 2021.
Hassan K Khalil. Nonlinear control, volume 406. Pearson New York, 2015.
Vijay Konda and John Tsitsiklis. Actor-critic algorithms. Advances in newral information processing systems, 12, 1999.
Suhas Kowshik, Dheeraj Nagaraj, Pratock Jain, and Pranceth Netrapalli. Streaming lincar system identifica- tion with reverse experience replay. Advances in Neural Information Processing Systems, 14:30140-30152 2021.
Chandrashekar Lakshminarayanan and Csaba Szepesvari. Linear stochastic approximation: How far does constant step-size and iterate averaging go? In International Conference on Artificial Intelligence and Statistics, pp. 1347-1355. PMLR, 2018.
Nevena Lazic, Dong Yin, Yasin Abbasi-Yadkorf and Csaba Szepesvari. Improved regret bound and ex- perience replay in regularized policy iteration. In International Conference Machine Learning, pp. 6032-6042. PMLR, 2021.
Donghwan Lee and Niao He. Target-based temporal-difference learning. In International Conference on Machine Learning, pp. 3713-3722, 2019.
Donghwan Lee and Do Wan Kim. Analysis of temporal difference learning: Linear system approach. arXiv preprint arXiv:2204.100 10479, 2022.
David A Levin and Yuval Peres. Markov chains and miring times, volume 107. American Mathematical Soc., 2017.
Long-Ji Ji Lin. Self- improviggoving reactive agents based on reinforcement learning, planning and teaching, Machine learning, (33)2233332,, 1992.
Xiao- Yang Liu, Hongyang Yang, Qian Chen, Runjia Zhang, Liuqing Yang, Bowen Xiao, and Christina Dan Wang. Finrl: A deep reinforcement learning library for automated stock trading in quantitative finance. arXiv preprint arXiw:2011.0960) 2020.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 518(7540):529 533, 2015.
14

---

Published in Transactions on Machine Learning Research (07/2024)
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillierap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In Inter- national conference on machine learning, pp. 1928 1937. PMLR, 2016.
Dheeraj Nagaraj, Xian Wu, Guy Bresler, Prateek Jain, and Praneeth Netrapalli. Least squares regression with markovian data: Fundamental limits and algorithms. Advances in neural information processing systems, 16116666-1667, 2020.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approxima- tion approach to stochastic programming. SIAM Journal on oplimizalion, 19(4):1574-10) 1609, 2009.
Neal Parikh, Stephen Boyd, et al. Proximal algorithms. Foundations and trends@ in Optimization, 1(3): 127 239, 2014.
Daniel Paulin. Concentration incqualities for markov chains by marton couplings and spectral methods. Electronic Journal of Probability, 20:1-33: -22, 2015.
Egor Rotinov. Reverse experience replay. Xrv preprint arXiv:1100087880 2019.
Mohit Sewak. Deep q network (dqu), double dqn, and ducling dqn. In Deep Reinforcement Learning, pp. 95-108 Springer, 2019.
Avi Singh, Huihan Liu, Gaoyue Zhou, Albert Yu, Nicholas Rhinehart, and Sergey Levine. Parrot: Data- driven behavioral priors for reinforcement learning, arXiv preprint orXiv:2011.1002, 2020.
Satinder P Singh and Richard S Sutton. Reinforcement learning with replacing eligibility traces. Machine learnöng, 22(1-3):123-155 158, 1996.
Yuda Song, Yifci Zhou, Ayush Sckhari, J Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid rl: Using both offline and online data can make rl efficient. arXiv preprint Xic:2220000611 2022.
Rayadurgam Srikant and Lei Ying. Finite-time error bounds for linear stochastic approximation andtd learning. In Conference Learning Theory, pp. 2803 2830. PMLR, 2019.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3(1):9 44, 1988.
Joel A Tropp et al. An introduction matrix concentration inequalities. Foundations and Trends0 in Machine Learning, 8(1-2):1-230, 2015.
Christopher JCH Walkins and Peter Dayan. Q-learning. Machine learning, 8:279 292, 1992.
A Appendix
A.1 Notations
Throughout the paper, the following notations will be adopted: R: set of real numbers; R". set of all dimensional vectors; Raxm; set of all
real matrices; Z4: set of all non-ncgative integers; R set of non-negative real numbers; R, set of non-negative real nunbers; for matrix A E Raxm [A]y, 1 S i < n. 1 < j < m denotes i-th row and j-th column element of A; e. E R² for 1 1 S n s-th basis vector of R space, i.c., only the s-th element of e. is one and other elements are zero; ||Al|oo for A E Rmm denotes the infininty norm || == maxiçisn En [[4]y] : |S]: cardinality a finite set S; O(-) denotes the big O notation.
A.2 Technical Lemmas
Lemma A.1. [Concentration bound for i.i.d. matriz random voriables [Tropp et al. (2015), Corollary 6.2.1) Let X E Rdixd, where d1 and da are some positive integers. Moreover, assume that the sequence of random
15

---

Published in Transactions on Machine Learning Research (07/2024)
matrices {Xx] are i. samples from distribution such that E[Xx] X and ||xxll2 I Xmax for all & k n. Let = || x 1l. Them, we get
IP
X
X
21 S (d1 + d2) exp (-nt² /(a + 2X mmxxl/33)
and
B - X X
2o log (1 + d2)
2L log(d1 + d2)
+
3n
With the above result, bound on the socond moment E En Xx - x]6]] can be obtained as follows.
Corollary A.2. Let E Xd2, Assume that the sequence of random matrices {X&]k=1 are i. samples from distribution such that E[Xx] = X and ||x&ll2 S Xmax for all 1 S k n. Letting [ S g, the corresponding second moment can be bounded as follows:
E
X - X
20
20
16xX
32x²
log(d1 + d2) + 8.
log(d1 + d2)
max (log(d1 + d2))² 9n2
max
9n2
3n
Proof. The proof is completed by the incqualitics
E
X
X
P
Xx X
2 V1 dl
k=1
2
min { (d1 + d2) exp(p nt/ / (o + mmx ft/3)).11 ]
min (1, (dh + d2) (2 dt / min {1, {1, + d2) expp(33m/t/4XXmmaa dt
20
20 +
16X2 max
log(d) + dd)
(log(d) d1 + dz))²²
(dl + d2) expl -2n 3n/t/////// (4X
n
9n²
18x2 mun (log(ds +d2))²
20 log(d1 + d2)
2x
16X2
+
max
(log(d) (11 + dz)) +
2(d + d2) (eljeexp(3nna (4X
n
n
In2
4Xmax log(dh +d2)
20 (o1 + d2)
2x
16X2
32x2
8XX 8.Xmax
+
max (log(d; d1 + dz))²
+
mAx (og(d1 d2) +
n
9n²
9n2
3n
where the first equality follows from the inequality, Y Y, which can be found in Exercise 2.14 in Casella & Berger (2021).
P Y 2 0 dt for non-negative random variable
Moreover, the first inequality follows from applying Lemma change of variables vi = and integration by parts.
A.1 and the last incquality follows from applying
Lemma A.3 (Variance of empirical distribution, Paulin 2015 Proposition 3.21). Let {S be a Markov chain following transition kernel pd with the state space S and starting from its stationary distribution ' i.e., So ~ 1's_. The empirical distribution is defined as (s) = E 1(S = s)/n, & E S. Then,
1) E.es E. [1v3_ ( < 1 -
mix
16

---

Published in Transactions on Machine Learning Research (07 (024)
2) E [drv(ug mm 2 S (Ss
panx
Lemma A.4 (Bound on total variation distance, Chapter 4.5 and Excrcise 4.2 in Levin & Peres (0017)
Let [S be a Markow chain following transition kernel p with the state space S. Denole ils stationary distribution uss.. and mixing time as tiiix Then, the following holds:
For non-negative inleger 1, we have supses drv (PPlv(Ppsgmiix So = 8), 13 S 2--
2) supses (P|( So = s), P is non-increusing in terms of k.
Lemma A.5 (Propasition 3.4 in Paulin 2015
For irreducible and aperiodic Markov chain, we have, for
mix (e) gix 1
1 2 (1) + log dmin )
A.3 Proof of Lemma 2.3
Before the main proof, the formal definition of irreducible and aperiodic Markov chain is reviewed first.
Definition A.6 (Irreducible and aperiodic Markov chain Levin & Peres 2017 ) A Markov chain is colled irreducible if for any two states x. X, eg pbee 0 for some k 2 O. Let T(x) == (k 2 e p*ez 0} be the set of time instances such that the probability of returning back to the initial state is positive. The period of state is the greatest common divisor of (xx). A Markow chain is said to be aperiodic if all states have period one.
The proof of Lemma 2.3 is given below.
Proof. First of all, we prove that the extended Markov chain irroducible. By hypothesis, the Markov chain, (Sk) with transition kernel pd is irreducible. Then, one can prove that starting from any (Sk, Sk+1) (x, y) E O, there exists positive probability that any (S++T, Sk+1+7) (w, 2) E O can be reached for some T 1 0. This is because by hypothesis, PP[S4T w So x > for some T 2 and since (w, 2) E O is realizable pair, (b4r15S4114)) (w, 2) E O is visited with a positive probability. This proves the irredueibility.
Next, we prove the aperiodicity. By hypothesis, the Markov chain, (Sx) is aperiodic. To prove that the induced Markov chain (Sk, = is aperiodic by contradiction, let us suppose that (Sk. 1 is periodic with some period T> Then, there exists a state E such that its period larger than one, which contradicts the aperiodicity assumption of (Sk ( This completes the proof.
A.4 Proof of Lemma 31
Proof. The proof proceeds by induction. Suppose ||Vellso S
Rmax
holds for 1: 2 Rewriting 6 I-n
we have
Vx+1 = 1+a
Σ (rese) - -1555))) Vs + a [ME (sinot))MM
Σ
EgT.
MEI
(s.rae))
We can prove that for 8 E S, if (8,r, & MT, then e, Vk+1 is identical to e Vy- If (8, E ME for some E S, then the update e Vk+1 can be expressed as follows:
(1+00
T VxL11 k+1 = E
Σ
(rese -ge V4 +
1
Σ ear (enne))
[MME
(e.ne')EME
17

---

Published in Transactions on Machine Learning Research (07 (07/2024)
Consider subset of the mini-batch MI such that the first element of the tuple is 8, i.c., Mg Mg 8 8) S Mg. Then, we can bound eg Vi+1 as follows:
{(3,8,8) E
le V2+111
c.
I
1
E
(reses -ce,)
Vi
+
MM (s)
Rmax
[
(EM))))ME())
M (8) MMg]
1 [M
E
(Yeses - -eee,)
|1Vill
Rmax
ME (s)
(1 (1)
||Vallo JM (+) [M
1
Rimx
M
Rmax
where the first inequality follows from the application of the triangle inequality and the assumption that the reward is bounded, as given in Assumption 2.4 The second inequality due to the Cauchy-Schwaad Schwartz incquality, and the last inequality comes from the induction hypothesis. This completes the proof.
A.5 Proof of Lemma 3.2
Proof. First of all, to prove the first statement, ||Al]so is bounded as
[s| (1- [I-a|DTis + (= > [PP') 15
||Aloc = max
lis 1ss)
min - (0(1-1))0 ((11-))=(ss) sES
where the last oquality is obtained by expanding A according to the dcfinition a stochastic matrix, i.e. the row sum of the matrix equals one.
from the fact that p is
Next, for the second statement, one can readily prove that M := (A simply plugging it into M in (10). It remains to prove that M is bounded. In particular, ||M]] is bounded
solution of 10 by
|| 2 < ||41/2 + ||A| + ||A|] +
< || + || +...
<1+ [8[ a(1 P) (1 a(1 1 77)mmin) 12 (1 a(1 - -7) ....
SS|
<+ a(1 - 7
where the first inequality follows from applying triangle inequality and the fact that ||A /|2 = ||Al|2. The second incquality is due to the relation ||A||2 S ||S|||A||oo and the third inequality comes from Lemma 3.2
A.6 Auxiliary lemmas to prove Lemma 3.3
Bg Let ug and Ps.g. be the empirical distributions of the state and the consecutive state pair (s, s') in the B and Hs,S., respectively.
Br
replay buffer, By respectively, which are defined in the same manner as μ
Lemma A.7. For k 2 0, we have the following bounds:
1) n D 2
S V1Sl
11
A
2) D pm D p
1
mmix
18

---

Published in Transactions on Machine Learning Research (07 (2722)24)
8) D - D R.
[
I |S AA
Rmax
amix [Bg]
2
Proof. First of all, the expected value of D BE can be bounded as follows:
E D
Dā.
SE E
133
Br 1s (5)
S SIS
U B
SES
which proves the first statement. In the above inequalities, the first inequality follows from the fact that |Alla ||Al|æ, where A E (|S] and || || stands for Frobenius norm. The last inequality follows from
Jensen's inequality and Lemma A.3 in Appendix.
The second statement can be proved using the following similar arguments:
E 1
- DBE pBt
[ SE
Σ (s,0)
B7 - -s - (s,
I /5s1
trii |
NV
where the first inequality follows from the fact that ||A||2 S ||Al|F, where A E R and || I|,,, the second inequality is due to Lemma A.3 in Appendix, and follows from applying Jensen's inequality.
For the third statement, we can bound
| D i R
in a similar sense as follows:
E
D R D BB
[.] <E
Σ
BE E (rS(, S 8, p3 (6) Ms (1)
[S||A||maatt
Σ
Σ SES
Σ
Br s3 (8,5¹)
Pss.s (8,
A'ESS
<|S)
A
Romax
1/2 [
where the second inequality applies the inequality (oi axbb)) S (E and the relation between p3... and _3 in
az) (z) bb) for ak. by E R, k 2 0,
and
Σ
(s1, 8141 = (s, s')}
1= N+1
BI Pg
(s)
-s (s, s').
BT
N
1/==
N+
Morcover, the last incquality follows the same logic as that used for bounding E D D This completes the proof.
- p
2
Lemma A.8. For k 2 O, we have
1) E [[] DT - DBB [12] = visl
+ ( 13, N)
Byl
2) e DI pa - DB |||]
4 MSSTTv 110 1,
8) ||| nil - D R [1]
S |S|
amix
[ + +2 RmaxdTTaT
19

---

Published in Transactions on Machine Learning Research (07/2024)
Proof. Let {Sk be the stationary Markov chain defined in Section 3.3 The expected value of ||D
DB ||2 can be bounded using irreducible and aperiodic property of the Markov chain as follows:
E
B D DB:
D
B
Sk- = P(SA-N =
R68
IB
D D
1|
3k-N = 5 IP|SA s]
#ES
+
Σ E
D -
-D 8
1/ 5 (P[Sk-N =s] - =s)
sES
<
D
DBg [g] + Σ
P[Sk-N = PPS s]]
t
S SVIS/
+ [
4 US M
the above inequalities, the first equality follows from the law of total expectation, and the second equality is due the fact that 1 transition probabilities of both Markov chains identical. Next, the first inequality follows from the fact that ||0 and || ll2 both smaller than one, and the last equality follows from the definition of the total variation distance in 2.1 and applying Lemma A.7
S& = P St. Sk-N] because the
In the second statement, the expected value of || pM D pB l|2 can be bounded using the same argu- ment as in the first statement. In particular, we have
E
Da pa - DB p
2
Σ
E
DTT pD Bt p
S 5] P|Sk-N =
SES
Σ #ES
E
||| D pa
D Br pBt
33 s) (P(Sk-N- = -P = 8))
-
2
umix
Sv SVIsyy
S|drV((13 x. 4v
N
The same logic holds for D D RD
DB R [2] In particular, follows from
E
D R B B
Σ
D R B2 R
5k-N = P1SS = s]
DJ DJ
D B
JS-N = (P(SL-N = -] -P(S =l)
sES
amix |
<|8
Al Rmax
This completes the proof.
A.7 Proof of Lemma 3.3
Proof. First of all, the triangle inequality applied to the noise term in
13
leads to
M
(ME, V1]
=E
Σ
8(0) VR) - (Vx) + (V)) (V2)
M
20

---

Published in Transactions on Machine Learning Research (07 (07/2024)
MEI Σ
800%V1 - (Vi)
(V] (V.Vll
(18)
The first term in (18) is the difference of the empirically expected TD-errors in terms of replay buffer and mini-batch, which is bounded as
A4
E
1
(00;va - -v)b) Σ =1
2
S
Rmax
E
Σ
(e,es - DB
M
(s.Ma))
2.
+E
Σ
rese DB p
[M
(a
E
Σ
(err D Bg RBx)
(19)
M
(s.ma'))Mg
where the inequality is obtained simply by expanding the terms in inequality, together with the boundedness of Va and reward function Assumption 2.4 and Lemma 3.1 respectively.
11 and and applying triangle
As the next step, we will upper bound the above terms using Bernstein inequality (Tropp al. 2015). particular, note that for (s, ME, be thought as uniform sample from 13 Hence, using the matrix concentration inequality in Lemma A.l in Appendix, one gets
8 log (2|S)) |
E
(c.e, - DB) (arss"))MM
Σ
M
which is obtained by letting and Xmax in Lemma A.10 in the Appendix because ||Eee,e]]1 <
and ||e,e, 1l2 S 1.
Moreover, noting that ||B(eee]]ll - El S 1, and ||e,e112 12 S 1, we get the following bound on the second term:
2 2ogg(2|S) (2(S))
E
Σ
rleee - BC pBt)
2%
[ME
[ME
In similar sense, the third term can be bounded as
(2)S(2
Σ (ear - DB% RB8
22max
IME
which uses the inequalities, [[[eer]lla inqqualities yields the upper bound on 19 which is
Rmax and
[[ elle
R2a
Collecting the above three
M Σ
4 S Rmax
(og(([S)) [M
E
500 vo) - (v()
(20)
M
1=1
Now, we turn attention to he second term, E (V&) A (V) in 18 which is the difference
between the expected TD-error with respect to the stationary distribution and the replay buffer distribution.
Plugging the definitions in [1 and 12 into 18 yields
E (V())(V)) (V.)lla
21

---

Published in Transactions on Machine Learning Research (07/2024)
2 AVSl|Rmass
DB [[] -D
11 + D pD D pBi [,)] + D R - RB
E
2
1 1-7
2 2//S|Rmaa
-mix [
/3/5//Aly/
16|S/dTV (13 13
(21)
1 1-7
where the first inequality is due to the boundedness of V2 in Lemma 3. and the last inequality follows from Lemma A.8 Collecting the terms in 20 and (21). we obtain the desired result.
A.8 Proof of Lemma 3.4 (Bound on second moment of the noise term)
Proof. Expanding the noise term in
we get
Bl]l(MM; V <2
E
800% V.) Ax + E (V.) (v Σ
(22)
T.
where the inequality follows from the fact that ||a + 6112 -
for a, b R2. In what follows, each
terms in the above inequality will be bounded. First of all, the term E 1 v2) Av(()))
in 22 is bounded as
E
800% (v(22)
E
Σ
(crr DB R. RB.)) (ese) - DBB + 7eses - Br PBpppBpiB
L
(s,T,o")EM,
27
27
3|S] !22 max
E
1
Σ
(ese) D)
+
T. Σ
(lesed D pit)
(1 7)2
T
(sir,8")EM
(sir,e")EM
3E
Σ
(e-r-D D2 R
(s.r,e")EM
[1] + Rmaxx)
480 (log(2|8))
71
[M
where the first oquality obtained by expanding the TD-crror term in (5) and expected TD-crror terms of replay buffer in The first inequality follows from the fact that |a
+ b+ cl < 3(||a||++1bb)) [|c|[3)
for a, b T and from the fact that the iterate Ve is bounded in 3.1 We concentration inequality
in Corollary A.2 to bound the last inequality. To bound E ( (E.e) - D ||
we let
and Xmax I in Corollary A.2 since ||B|e,e]]lla 1 and I|e,e] 1a S 1. Moreover, terms in similar sense, which yiclds the last incquality.
bound remaining
To proceed further, Lemma A.9 is needed, which is provided after this proof. Applying Lemma A.9 the
term (Vx) (V bounded as
| (Vk) A (V
[10 DB + (D RT D R + <D=P= D p V
=E
22

---

Published in Transactions on Machine Learning Research (07/2024)
3|S R max (1 71-
(415)4)412 max fepii, tmix]
P3, w
B + S
where the incquality follows from applying the bound on Vy in Lemma 3.1 and collecting the terms in
Lemma A.9 This completes the proof.
The following two lemmas have been used in the proof above, and they are formally introduced in the sequel. Lemma A.9. For k 2 O, we have
1) Bi - DB [|]]
8drv (mS N)
2) Bi|lD* p. - D P
S |S
2/S
(MS P3 n);
3) E D 18th - D R
2
<
15
max
mixx
max dTv (13 L|
13 xx
Proof. Let (S* be the stationary Markov chain defined in Section 3.3 we get the following bounds:
Then, for the first statement,
B1||D* - 11
E
D 1 Sa-N =s] P(Sk-N s]
SES
D DB SS-N s|P[S s]
$ES
Bi||D* - -DB
SA-N s](P[Sk- s) - -P(SAN =s]
SES
miix
<|S|
+ 33,
[
where the first. equality due to the law of total expectation, and the fact that P[Sa-N N+1, Sk- ... Sp
SR-N] and (|$ Sx Sp-x] are identical. Moreover, the second equality follows from simple algebraic decomposition, and the incquality is due to the fact that || - BlI - 2011 + | (8) for A, B E IR SX|Si, and applies Lemina 10 and the definition of total variation distance in Definition 2.1 will
Note that Lemma A.10 will be given after the proof.
For the sccond statement, follows that
E 1 - D Bv
2 =
Σ
E Dr - "h pB ||= Sk-N = s) P[Sk-N = s)
2
SES
| px - DB pB; 12] +2|S(dTV(4s ,x
<
mnix
<|S|²
12
2|S
|
where the first inequality is due to the fact that ||P*|| < S). || || < |S| since ps and pßg are stochastic matrix, ie., the row sum equals one. This concludes the proof of the second statement.
Next, similar arguments hold for E D
DE
follows:
2
E D DD
R
E
D RD
D B
DB
Sk PiSS-N =
.ES
<E ||
D D
R.
D& B 2
+2 max dlv (u H
mnix
< S|S 2 R2
+
2|
( xx
[
23

---

Published in Transactions on Machine Learning Research (07 (07/202) /224)
This completes the proof.
Lemma A.10. For k 2 O, we have
D - DBg S
mmix BEl
1)
2
2)
D pa - DD PB,
- ||
mmix 1
8) E RT - D B7 R
1 |S 2 R
max
Proof.
The first statement is proved via the following inequalities:
||D0 8x
1
1 S Σ
27 (13 (s) - U (s)
S S
B
SES
Here, the first incquality follows from the matrix norm incquality || ll2 S || llf where || l|f stands for Frobenius norm, and the second inequality applies Lemma similar lines. particular, letting U3.s
A.3 The proof of the second statement follows
Bg stand for stationary distribution of {(5k, Sk+1) one gets
E - a [2]
-
Σ
B (1 (8, -5. (s, - $|S}
tmix
S
where the first inequality follows from the relation between spectral norm and Frobenius norm, and the second incquality applics Lemma A.3
For the third statement, can bound E - R 2 with the same logic as in the proof of
Lemma 3.3 as follows:
)²
E
D' Rd -DB
D R
=E Σ
E(r(S,A, S - (s) Us
B7
LES
<|S|$| 1 R2 max E
(MB Us (8,
B7 11 (8, (s,
LES EEE
amix
<
S|S|
|AA2
R2 R
D
This completes the proof.
A.9 Proof of Theorem 3.5
Proof. We prove the first statement. Using
||V++1 V can be expanded as follows:
||V++1 1I
=(V; V A MA(V, - V²*++ + 2o VT)T A Mw(M). V4) a a Vi)
=I[V/ VI 1[V + V A (M V&) + a² [e 1i
where the first equality follows from and the last equality uses the Lyapunov equation in 10 expoctation yields
Taking
E[llV+++ I
=V[l V [12] [. V*Ila]
2a VTJT A Mw Vo) a [ V
24

---

Published in Transactions on Machine Learning Research (07/2024)
8|5| Rmax Blll((ME V+)]la]
< - Vl - V
[=112]+
(1- 2
2a|S1
7) (M Vill
< [1[V% VL [[ir]]]
32|5| ( R
8 S1)
mmix
+||1]]
A 16/5/dTv(33 P3x..o wn
(1 - (-)
L
4 4 + 1)2
(20((og(2)81)) L
+ LAP mix
(1 (BaNN)
(1 77
where the first inequality follows from Cauchy-Schree Schwartz inequality, and the boundedness of V22 in Lemma 3.1 The last inequality comes from bounding the first and second moment of [[w[ME. Vi)lll by Lemma 3.3 and Lemma 3.4 respectively.
Summing the last inequality from k = 0 to k = - 1 and dividing both sides by T, one gets
Σ
B[ 113)
T
32,5|2
8log(2|SS)
mmix
+
+
2
|AV
(1 (
L
N
+ 1 32|5|2R2
16 (6 H3._
T (1 -7)²
+ ( +)
120(log(2|S)) (2()))
mix
118141112
(1-7)>
L
N
1 4|5 R2
16) vs
T (1 - 1
To bound the sum of total variation terms in the above inequality, the following relation can be used:
T-1
T/T
Σ d -B,_N) S emix
drv(UG 133 -N x S emix Σ
Σ k=
2 < 21
K=
where the first inequality follows from non-increasing property of total variation of irreducible and aperiodic Markov chain in Lemma A.4 in Appendix. Morcover, the second incquality follows from the first item in Lemma A.4 in Appendix. Combining the last two inequalities leads to
BlIVV V=
T
1 2|S]|
a(11 - 77)
S2|S| R2
(og(8|
mix
32 S2P1SR22. 2emix (1 13 T
+ (1 33)3
+ 2| LAl
( + 1)2 120(1og(2(8))) 1|1
128 R2
amix
+ a
(1 (1-7) p
71
T
This completes the proof of first statement, The second statement can be directly obtained from applying Jensen's incquality.
25

---

Published in Transactions on Machine Learning Research (07 2024)
A.10 Proof of Theorem 3,6
Proof.
First of all, we prove the first statement. The term [[V V=ll2 is expanded according to the update
in as follows:
V V
VV4 - V= + 20(V2 V (MM,, V2) + + V
(Vo va) (AT) 1 (Vo - v*) Σ 2V V - V.)
(23)
k 2
(M,; V.) (A A
(24)
where the second equality follows from the fact that for 0 S i S k k- 1, the i-th expansion results weighted inner product of A -*) and w(ME-i-n Vi-+-) and weighted squared norm of w(ME--i- Va-s-1)
which are (23 and 24 respectively.
Next, applying Cauchy Schwartz inequality to (24 yields
|| Vi+1 V
<o
12 + 20/S
|1V - V" | 1+1 - bollA4~11100 (00lll VVllz
1=0
0 Σ || 2| (2]
1=0
<
V |11 2 + 20(
Σ
|| - 12112|11132 2-++++
(Mo[M 1 V:)ll2
2i+
1=0
b Σ
+ a
V
2k- -
[M
t=0
where the first incquality follows from the matrix norm incquality ||4 S VISI|A|| oo and the last incquality is due to sub-multiplicatiitty of the mairix norm. After laking expectation, we get
E
V
VT
Vo - V" 1 S||AA 11
+ 64|S|2R² R R?max
(1gg(
miix
|
Σ
||A|
26+1
(1-
L
N
+ 2 V18 (Pmax 1)2
(120(lo((2(8))
mix
4 1|A1
Σ
||A1122 2k-2i
71
IM
B
< - VT - a(1 - 7)
2k+2
64|5 R2
8 (2g(())51)
mix
+ (1 (17))²m1 M
+ |S|
LA
L
N
4 4|5(( (Rmaxx + 1)2
(20)
mix
1A
+ 0
(1 P
|B
where the first inequality follows from Lemma 3.3
3.4
and the fact that (rv("__.,5 ,P,, is zero for all
k > 0 because the initial state distribution is identical to the stationary distribution. Moreover, the second
inequality comes from the bound on ||Alloo in Lemma 3.2 This proves the first statement. Finally, applying
Jensen's 's inequality to the first item which is the bound on E || Vi
v= leads to the second statement. J
26

---

Published in Transactions on Machine Learning Research (07/2024)
A.11 Sample complexity result of Theorem 3.6
The result of Bhandari et al. (0188) requires following number of samples to bound 17 with >> 0:
1
mmix
(25)
2 7) (mmin)
where we used gmix (a)) Ô (tmix) from Lemma A.5 in the Appendix, and (m) is defined 1
To bound the second line of the the second item in Theorem 3.6 with e, we require
L= δ ( (1 (1- (1- (Mmi)))
|S| )
T | 1
Ö
(1- (1- e4
Next, to bound the third line of the the second iteem in Theorem 3.6 with require
(
S
(1 mix 11)
|
L -=
N
(1-7)3 pmin
(1- 3m Pmin a 22
(1
Lastly, to bound the first line of the the second item in Theorem 3.6 with the number of steps k needs to satisfy the following:
(ar
1 )
=
a(1 >-
In
The overall sample complexity results to
1817 AA2 mix
- (1 (1- (p ( a
Compared to the sample complexity in 25 by Bhandari et al. (001)), the above sample complexity result However, if we consider, N, given pre-collected leaves room for improvement in terms of and Amm
dataset, the sample complexity result is only O a(I-)))mm In (t)) where (0, 1).
27


Reviews:
[{"review_id": "9SFWVe8gDN", "reviewer": "Reviewer_4S6k", "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* The paper takes on an ambitious but useful analysis\n* From the proofs I have checked, the analysis seems to be correct.\n* There are attempts to clarify and communicate the results to readers not immersed in such analysis and methods\n\n### Minor Weaknesses:\n* $k$ is overloaded to describe the Markov chain as well as the value function updates and the samples in the replay buffer. That makes it hard to keep track of which version of $k$ is being referred to sometimes.\n* In Section 3.1, Replay Buffer $B_k^{\\pi}$ has samples indexed as $O_{k-N+1}$, which implies $k$ is larger than $N$. But $k$ seems to refer to learning steps, which should start at $0$.\n* $e_{s_k}$, while evident, doesn't seem to be defined\n* Just before Section 3.3: the empirical estimation seems to be for the reward, not the return, and the reward is implied to only depend on $s$, but is defined to be over $(s, a, s')$ in Section 2. Even averaging over actions would imply that the reward here would be dependent on $(s, s')$\n\nNone of these nitpicks changes the analysis and the comparison with related methods though", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper looks at the finite-time analysis of the TD-learning when using an experience replay and where updates are done using minibatches drawn at random from the experience replay. It finds bounds on the noise induced by using minibatches, and uses it to analyze the convergence of the averaged iterate and the final iterate with respect to the true value function.\n\nThe paper also compares its results to other contemporary analyses.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "Ensure consistency and address issues above", "broader_impact_concerns": "NA", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "qfx8w60RBn", "reviewer": "Reviewer_gLw3", "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 authors claim that in their result the step size can be any constant in (0,1), and it does not need to be dependent on the horizon, and they count this as an advantage compared to the prior work. However, in this work we need to set L and N based on the horizon T prior to running the algorithm, which plays the same role as setting the step size depending on the horizon T. Can you elaborate more why setting L and N is better than setting the step size alpha?\n- Furthermore, the comment about Lakshminarayanan & Szepesvari (2018) is not clear to me. Clearly that paper studies a more general setting with linear function approximation, and hence the step size requires knowledge of the problem structure, including the feature space. \n- In this paper, rather than knowing the problem structure, we need the knowledge of the mixing time to set N>tau_mix. How is it different than the prior work?\n- Similarly, in Theorem 3.6 you impose the strong assumption of S_{-N}\\sim \\mu_S^\\pi. How is this assumption realistic, given that we do not know the stationary distribution of the underlying Markov chain?", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies the convergence of TD-learning with experience replay. The authors establish the convergence of this algorithm based on the step size, and the replay buffer’s size and the mini-batch’s size. The authors argue that compared to previous work, their algorithm has the advantage of not having strict problem dependent requirements on the step size.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "- In equation (3), you did not define what e_s_k is.\nOverall, besides comparing the requirements on the step size, can you also discuss about the sample complexity of TD-learning with experience replay, and under similar conditions (and assumptions), can you compare its sample complexity with normal TD-learning? that way we can have a clear view on potential advantages of this algorithm.", "broader_impact_concerns": "No concern", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "SHhpH1Kzf3", "reviewer": "Reviewer_EqyT", "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* The paper's organization was largely easy to follow.\n* As far as I was able to check, the results appear correct.\n\n**Weaknesses:**\n* While the emphasized result of the constant error being largely independent from the choice of step size is interesting, it seems intuitive, especially in the tabular setting. The step-size is related to the window size of a moving average, where a sufficiently small step-size is often needed to average out any stochasticity in the update targets. In the experience replay update, we see that a sample average is computed over the mini-batch, alleviating the need for the step-size to perform this averaging.\n* My primary concern with the paper is that they chose a very specific setup for their analysis, that it's difficult to situate the result among the space of similar setups. For example, while they emphasize that prior analysis on Fitted Q-Iteration had a very strong assumption on how transitions are sampled, it's unclear how the contrasting choice of a Markovian observation model manifests in the main result and the conclusions drawn. The emphasized result around the error term seems like it results from the use of mini-batch updates, and not be particularly unique to the chosen setup.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper provides a finite-time analysis of on-policy tabular temporal difference learning with experience replay. It then provides a comparative analysis with existing results in the literature. While the convergence rate is on a similar order, they emphasize that the error induced by using a constant step-size can be controlled by the mini-batch and replay buffer sizes.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Can the authors acknowledge or clarify the impact of using the Markovian observation model on the results? It's unclear in the comparative analysis as the table does not present any other works with Experience replay (or comparable mini-batch updates). The intuitions for why the constant error term can be controlled by the mini-batch size seems like it should similarly apply to an on-policy tabular analog of Fitted Q-Iteration. As this seems to be the main result being emphasized by the paper, it would be good to detail how the paper's chosen setting may have played a role in the result, if at all.\n\n2. The signs in Equation 7 seem incorrect--- Specifically, the expected TD-error with respect to the stationary distribution appears incorrect as the immediate reward and the discounted future value have opposing signs. The subsequent equations based on this appear correct, so this did not affect downstream results.\n\n3. In Appendix A.3, the proof of Lemma 2.3 is given in-line and is extremely dense. Is there any particular reason for this? It seems out of place given the presentation of the other proofs in the paper, and is very hard to read. I think its presentation would benefit from being unrolled.\n\n4. In Equation 3, the notation \"e\" is introduced with no definition or acknowledgement of it in any of the text preceding it. Later equations continue to use this undefined notation. I think it would improve clarity to explain this quantity, even informally.", "broader_impact_concerns": "N/A.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: While maybe not the end-all analysis of TD methods with replay buffers, it makes a distinct contribution to advance our theoretical understanding of such algorithms.  Theoretical evidence is sound, and the advance is of interest to TMLR's audience.  Straightforward acceptance.
Decision: Accept (poster)