Online Target Q-learning with Reverse Experience Replay: Efficiently finding the Optimal Policy for Linear MDPs
Authors: Naman Agarwal
Syomantak Chaudhuri
Prateek Jain
Dheeraj Mysore Nagaraj
Praneeth Netrapalli
Venue: ICLR 2022 Poster (2022)
Keywords: Q Learning
RL with Function Approximation
Experience Replay
Online Target Learning

Abstract: Q-learning is a popular Reinforcement Learning (RL) algorithm which is widely used in practice with function approximation (Mnih et al., 2015). In contrast, existing theoretical results are pessimistic about Q-learning. For example, (Baird, 1995) shows that Q-learning does not converge even with linear function approximation for linear MDPs. Furthermore, even for tabular MDPs with synchronous updates, Q-learning was shown to have sub-optimal sample complexity (Li et al., 2021, Azar et al., 2013). The goal of this work is to bridge the gap between practical success of Q-learning and the relatively pessimistic theoretical results. The starting point of our work is the observation that in practice, Q-learning is used with two important modifications: (i) training with two networks, called online network and target network simultaneously (online target learning, or OTL) , and (ii) experience replay (ER) (Mnih et al., 2015). While they have been observed to play a significant role in the practical success of Q-learning, a thorough theoretical understanding of how these two modifications improve the convergence behavior of Q-learning has been missing in literature. By carefully combining the Q-learning with OTL and reverse experience replay (RER) (a form of experience replay), we present novel methods Q-Rex and Q-RexDaRe (Q-Rex+data reuse). We show that Q-Rex efficiently finds the optimal policy for linear MDPs and provide non-asymptotic bounds on sample complexity -- the first such result for a Q-learning method with linear MDPs. Furthermore, we demonstrate that Q-RexDaRe in fact achieves near optimal sample complexity in the tabular setting, improving upon the existing results for vanilla Q-learning. 


Published as a conference paper at ICLR 2022
ONLINE TARGET Q-LEARNING WITH REVERSE EXPE- RIENCE REPLAY: EFFICIENTLY FINDING THE OPTIMAL POLICY FOR LINEAR MDPS
Naman Agarwal, Prateek Jain, Dheeraj Nagaraj, Praneeth Netrapalli Google Research (namanagarwal, prajain, dheeraj, ceetrappalll8gooogLLe com com
Syomantak Chaudhuri
University of California, Berkeley
syomantakeberkeet edu
ABSTRACT
Q-learning is popular Reinforcement Learning (RL) algorithm which is widely deployed with function approximation (Mnih et al., 2015). In contrast, existing theoretical results pessimistic about Q-learning. For example, Q-learning does not converge even with linear function approximation for linear MDPs ((Baird, 1995)) and even for tabular MDPs with synchronous updates, Q-learning has sub- optimal sample complexity (Li et al., 2021; Azar et al.. 2013). The goal of this work to bridge the gap between practical success Q-learning and the relatively pessimistic theoretical results. The starting point of our work is the observation that in practice, Q-learning is used with two important modifications: (i) train- ing with two networks, called online network and target network simultaneously (online target learning, or OTL) and (ii) experience replay (ER) (Mnih et al., 2015). While they play significant role in the practical success of Q-learning, a thorough theoretical understanding of how these two modifications improve the convergence behavior of Q-learning has been missing in literature. By carefully combining Q-learning with OTL and reverse experience replay (RER) (a form experience replay), we present novel methods Q-Rex and Q-RexDaRe (Q-Rex+ data reuse). We show that Q-Rex efficiently finds the optimal policy for linear MDPs (or more generally for MDPs with zero inherent Bellman error with lin- ear approximation (ZIBEL)) and provide non-asympiotic bounds on sample com- plexity the first such result for Q-learning method for this class of MDPs un- der standard assumptions. Furthermore, we demonstrate that Q-RexDaRe in fact achieves near optimal sample complexity in the tabular setting, improving upon the existing results for vanilla Q-learning.
INTRODUCTION
Reinforcement Learning (RL) has been shown be highly successful in practice for a variety of long term decision making problems (Mnih et al., 2015). Several classical works have studied RL methods like TD-learing, Q-learning and their variants (Sutton & Barto, 2018; Bertsekas, 2011; Borkar & Meyn, 2000; Sutton, 1988; Tsitsiklis & Van Roy, 1997; Watkins & Dayan, 1992; Watkins, 1989) but the guarantees are mostly asymptotic and therefore do not sufficiently answer important questions that relevant practitioners who struggle with constraints on the number of data points and the computation power. Recent works provide -symptoti results for a variety of important settings (Kearss& & Singh, 1999; Beck & Srikant, 2012: Qu & Wierman, 2020; Ghavamzadeh al., 2011; Bhandari et al., 2018; Chen et al., 2020; 2019; Dalal et al., 201 8a;;; Doan et al., 2020; Gupta et al., 2019; Srikant & Ying, 2019; Weng al., 2020; Yang & Wang, 2019; Zou et al., 2019a).
Despite a large body of work, several aspects of fundamental methods like Q-learning (Watkins & Dayan, 1992) still ill-understood. Q-learning's 's simplicity and the ability learn from off off-policy

---

Published as a conference paper at ICLR 2022
data makes it widely applicable. However, theoretical analyses show that even with linear function approximation and when the approximation is exact, Q-learning can fail to converge even in simple examples (Baird, 1995; Boyan & Moore, 1995; Tsitsiklis & Van Roy, 1996). Furthermore, even in the simple case of tabular RI with synchronous updates, Q-learning is known to have sub-optimal sample complexity (Wainwright, 2019a; Li et al., 2021).
However, Q-learning has seen tremendous practical success when deployed with "heuristic" mod- ifications like experience replay (ER) and online target learning (OTL). ER is used alleviate the issues arising due highly dependent samples in an episode whereas OTL helps stabilize the Q iter- ation. Mnih et al. (2015) conducted extensive experiments to show that both these techniques, are essential for the success of Q- Q-learning. But, existing analyses for ER with Q-learning either require stringent assumptions (Carvalho et al., 2020) to ensure convergence to a good Q value, or assume that ER provides i.i.d. samples which might not hold in practice (Fan et al., 2020; Carvalho et al., 2020). In this paper, we attempt to bridge the gap between theory and practice, by rigorously in- vestigating how Q-learning performs with these practical heuristics. We thus introduce two model free algorithms: Q-Rex and Q-RexDaRe that combine the standard Q-learning with OTL and re- verse experience replay (RER). RER is form of ER which was recently studied to unravel spurious correlations present while learning form Markovian data in the context of system identification (Jain al., 20). We show that OTL stabilizes the Q value by essentially serving as a variance reduc- tion technique and RER unravels the spurious correlations present in the Markovian data to remove inherent biases introduced in vanilla Q learning.
These simple modifications have surprisingly far-reaching consequences. Firstly, this allows us to show that unlike vanilla Q-learning, Q-Rex finds the optimal policy for MDPs with an exact linear function representation of the Bellman operator. and allows us to derive non-asymptotic sample complexity bounds. In the tabular setting, Q-Rex even with asynchronous data is able to match the best known bounds for Q-learning with synchronous data. Its variant Q-RexDake which reuses old samples, admits nearly optimal sample complexity for recovering the optimal Q-function in the tabular setting. Previously, only Q-learning methods with explicit variance-reduction techniques (not popular in practice) (Wainwright, 2019b; Li et al., 2020b) or model based methods (Agarwal et al., 2020; Li et al., 2020a) were known to achieve such sample complexity bound. Our experiments show that when the algorithmic parameters are chosen carefully, Q-Rex and its variants outperform both vanilla Q-learning and OTL+ER+Q-leaninn with the same parameters (see Appendix A).
To summarize, in this work, we study Q-learning with practical heuristics like ER and OTL, and propose two concrete methods Q-Rex and Q-RexDaRe based on OTL and reverse experience replay a modification of the standard ER used in practice. We show that Q-Rex is able to find the optimal policy for ZIBEL MDPs, with strong sample complexity bound which is the first such result for Q-learning. We also show that Q-RexDaRe obtains nearly optimal sample complexity for the simpler tabular setting despite not using any explicit variance reduction technique. See Table for a comparison of our guarantees against the state-of-the tfee---fe-eeretttss- for the tabular setting.
Organization We review related works in next subsection. In Section 2 we develop the MDP problem which we seek to solve and present our algorithm, Q-Rex in Section 3. The main theoretical results are presented in Section 4. We present a brief overview of the analysis in Section 5 and present our experiments in Section A. We provide minimax lower bounds for the asynchronous tabular setting in Section K. Most of the formal proofs are relegated to the appendix.
1.1 RELATED WORKS
Tabular Q-learning Tabular MDPs are the most basic examples of MDPs where the state space (8) and the action space (AA) are both finite and the Q-values are represented by assigning a unique co-ordinate to each state-action pair. This setting has been well studied over the last few decades and convergence guarantees have been derived in both asymptotic and non-asymptotic regimes for popu- lar model-free and model- algorithms. Azar et al. (2013) shows that the minimax lower bounds on the sample complexity of obtaining the optimal Q-function up-to 6 error is the discount factor. Near sample-optimal estimation is achieved by several model- based algorithms (Agarwal et al., 2020; Li et al., 2020a) and model-free algorithms like variance reduced Q-learning (Wainwright, 2019b; Li et al., 2020b). (Li et al., 2021) also shows that vanilla Q-learning with stan- dard step sizes, even in the synchronous data setting where transitions corresponding to each state
|S||A]]
"-> where Y is
[
2

---

Published as a conference paper at ICLR 2022
Paper (GHAVAMZADEH ET AL.. 2011)
Algorithm
Data Type
Sample Complexity STA CQ-oa
SPEEDY Q-LEARNING
SYNCHRONOUS
(WAINWRIGHT, 2019B)
VARIANCE REDUCED
SYNCHRONOUS
18 [S (11-7)
Q-LEARNING
VARIANCE REDUCED
(L1 ET AL.. 2020B)
ASYNCHRONOUS
Q-LEARNING
(L) ET AL,, 2020B)
Q-LEARNING
ASYNCHRONOUS
Manto
EL.ET AI.,, 2021)
Q-LEARNING
SYNCHRONOUS
THIS WORK, THEOREM 2
Q-LEARNING+ OTL RER (Q-REX)
ASYNCHRONOUS
S1AAA
Q-REX+ DATA-REUSE (Q-REXDARE)
THIS WORK, THEOREM
ASYNCHRONOUS
Paece (1-7g3
Table I: Comparison of tabular Q-learnng based algorithms. d S |S| is maximum size of support of P(-)s, a)- In the case of asynchronous setting, Mmnn is roughly equivalent to |S||_A| in the syn- chronous setting. We use the color green represent results with optimal dependence on (1 -1)--
action pair are sampled independently at each step - suffers from a sample complexity of |8 |
and the best known bounds in the asynchronous setting- where data is derived from a Markovian trajectory and only one Q value is updated in each step is (1-7)- These results seem unsatis- factory since Y (0.99, 1) most practical applications. In contrast, our algorithm Q-Rex with asynchronous data has a sample complexity that matches Q-learning bound with synchronous data and its data-efficient variant Q-RexDaRe has near minimax optimal sample complexity (see Ta- ble 1). For details on model based algorithms, and previous works with sub-optimal guarantees we refer to (Agarwal et al., 2020; Li et al., 2020b). We note that the lower bounds apply only to the synchronous case (i.e, when every state-action pair is sampled at every step). We provide minimax lower-bounds which show that the bound is tight in the asynchronous case too (see Theorem 5 in Section K), where [S]] A|| in the synchronous case of (Azar et al., 2013) is replaced by Plain"
|S||A|
Q-learning with Linear Function Approximation Since tabular Q-learning is intractable in most practical RL problems due to a large state space S, function approximation is deployed. Linear function approximation is the simplest such case where the Q-function is approximated with linear function of the 'feature embedding' associated with each state- action pair. However, Q-learning can be shown to diverge even in the simplest cases introduced residual gradient methods which converged rather slowly but provably. We will only discuss recent works closest to our work and refer the reader (Carvalho et al., 2020; Yang & Wang, 2019) for a full survey of various works in this direction. SARSA is the on-policy control variant of Q-learning where the challenge is to explore the state-space while learning the optimal policy. Unlike Q-learning, SARSA is inherently stable due to its on-policy nature (Gordon, 2000). Therefore, we do not compare our results to the results of on-policy control algorithms like SARSA. We refer to (Zou et al., 201 9b; Perkins & Precup, 2002; Melo et al., 2008) for further details.
first noticed in (Baird, 1995), which also
Yang & Wang (2019) consider MDPs with approximate linear function representation. They require additional assumptions like finite state-action space and existence of known anchor subsets which might not hold in practice. Our results on the other hand hold with standard assumptions, with asynchronous updates and can handle infinite state-action spaces (sce Theorem 1). Similarly, Chen et al. (2019) consider Q-learning with linear function approximation which need not be exact. But the result requires the restrictive assumption that the offline policy is close the optimal policy. In contrast, we consider the less general but well-studied case of MDPs with zero inherent Bellman error and provide global convergence without restrictive assumptions on the behaviour policy.
Under the most general conditions Maei et al. (2010) present the Greedy-GQ algorithm which con- verges to point asymptotically instead of diverging. Similar results are obtained by Carvalho et al. (2020) for Coupled Q-learning, a 2-timescale variant of Q-learning which uses a version of OTL and ER!. This algorithm experimentally resolves the popular counter-examples provided by (Tsitsiklis & Van Roy, 1996; Baird, 1995). However, the value function guarantees in Carvalho et al. (2020,
'The version of ER used in Carvalho et al. (2020) makes the setting completely synchronous opposed to the asynchronous setting considered by us.
3

---

Published as a conference paper at ICLR 2022
Theorem 2) (albeit without sample complexity guarantees) requires very stringent assumptions and even in the case of tabular Q-learing might not converge to the optimal policy.
Experience Replay and Reverse Experience Replay Reinforcement learning involves learning on-the-go with highly correlated correlated data. Iterative learning algorithms like Q-learning can sometimes get coupled to the Markov chain resulting in sub-optimal convergence Experience replay (ER) was introduced in order to mitigate this drawback (Lin, 1992) - here a large FIFO buffer of fixed size stores the streaming data and the learning algorithm samples data point uniformly at random from this buffer at each step. This makes the samples look roughly i.i.d., thus breaking the harmful correlations. Reverse experience replay (RER) is form of ER which stores data in a buffer but processes the data points in the reverse order as stored in the buffer. This was introduced in entirely different contexts by (Rotinov, 2019; Jain et al., 202 (0a). In this work, we note that reverse order traversal endows super-mattingale structure which yields the strong concentration result in Theorem 4, which is not possible with forward order traversal (see (Jain et al., 2021b, Section 3.1) for a brief demonstration of this fact). We can also look at RER is through the lens of Dynamic programming (Bertsekas, 201 1) where the value function is evaluated backwards starting from time T to time 1 similar to how RER bootstraps present to the future.
In the context of reinforcement learning, works like Bhandari et al. (2018); Zou et al. (2019b) obtain finite time convergence guarantees for RL algorithms under the mixing assumptions just like this work. The strategy followed in these works is that if two samples are (Tiiix time apart, then they are approximately independent and thus analysis for i.i.d. data can be applied. The sample complexity to obtain error here is O ( Note that this is no better than keeping one every Tmix samples and throwing away the rest and under general mis-specified linear function representation, might not be able do any better (Bresler al., 2020). In this work, we show that when the linear approximation is well specifed (ZIBEL), we can use RER to obtain sample complexity of OTmix ) where the mixing time serves as a cut-off.
Online Target Learning OTL (Mnih et al., 2015) maintains two different Q-values (called online Q-value and target Q-value) where the target Q-value held constant for some time and only the online Q-value is updated by 'bootstrapping' to the target. After a number of such iterations, the target Q-value is set to the current online Q value. OTL thus attempts to mitigate the destabilizing effects of bootstrapping by removing the 'moving target'. This technique has been noted to allow for an unbiased estimation of the bellman operator (Fan et al., 2020) and when trained with large batch sizes is similar to the well known neural fitted Q-iteration (Riedmiller, 2005).
2 PROBLEM SETTING
Markoy Decision Process We consider infinite horizon, time homogenous Markov Decision Pro- cesses (MDPs) and we denote MDP by MDP(S, A. P, R) where S is the state space, A is the action space, 7 E [o, 1) is the discount factor, P(s'|s, (s, a) is the probability of transition to state s' from the state on action a. We assume that S and A are compact subsets of R" (for some n E N). R: S x A + [0, 1] is the deterministic reward associated with every state-action pair.
We will think of an MDP as an agent that is aware of its current state and it can choose the action to be taken. Suppose the agent takes action T(s), where т : S + A, at state E S, then P along with the "policy" æ induces Markov chain over S, whose transition kernel is denoted by p*, We write the d-disouuneed value function of the MDP starting at state s to be:
oz
V(s, ())
=() - F 7" R(S., A.) = 8, A = π (S.)Vl).
(1)
is well-known that under mild assumptions, there exists at least one optimal policy '² such that the value function V Vss, T) is maximized for every sand that there is optimal Q-function, Q' S x A + IR, such that one can find the optimal policy as T" (s) = arg max Q" a), optimal value function as (*) max (s, a) and it satisfies the following fixed point equation.
(s) R(s a) + (( [max Q*(s', a')] V(s,a) E S x A.
(2)
a'EA
(2) can be alternately viewed as Q" being the fixed point of the Bellman operator T, where
T(Q)(s, a) = R(s,a) a) + +P (s)) [max (()),
a'
4

---

Published as a conference paper at ICLR 2022
The basic task at hand is to estimate (s.saa a) from single trajectory (st, at) such that S141 ~ P(-|st: ae) along with rewards (re) where 71,.... "T are random variables such that E B s, ar = R(s, a). We refer to Section for rigorous definitions.
Q-learning Since the transition kemel P (and hence the Bellman operator 7) is often unknown in practice, Equation (2) cannot be directly used to estimate the optimal Q-function. To this end, we resort to estimating Q" using observations from the MDP. An agent traverses the MDP and we obtain the state, action, and the reward obtained at each time step. We assume the off-policy setting which means that the agent is not in our control, i.c.. it is not possible to choose the agent's 's actions; rather, we just observe the state, the action, and the corresponding reward. Further, we assume that the agent follows a time homogeneous policy rT()) for choosing its action at state 8.
Given a trajectory {st, de. re]T= generated using some unknown behaviour policy x, we aim to estimate Q* in model-free manner i.e, estimate Q' without directly estimating P. We further assume that the trajectory given to us as a data stream so we can not arbitrarily fetch the data for any time instant. A popular method to estimate Q" is using the Q-learning algorithm. In this online algorithm, we maintain an estimate of Q" a) at time t, Qc(s, a) and the estimate is updated at time t for (s, a) (st, a²) in the trajectory. Formally, with step-sizes given as {nc. Q-learning performs the following update at time 1,
Qu+1(St; ae) (1 7o Qe ?e r + max Qe(s)t2,
a'EA
(3)
ac+ Qr(s,a) V (s,a)= + (st,
In this work, focus two special classes of MDPs which are popular in literature.
Linear Markoy Decision Process Linear MDPs (Jin et al., 2020) is a popular example of exact linear approximation for which statistically and computationally tractable algorithms are available. We use the definition from Jin et al. (2020), stated as Definition 1.
7, P. R) is linear MDP with feature map ::Sx A + RR Definition 1. An M A,
1. there exists a vector 0 E TRd such that R(s, a) = (((s,a)) a), and
2. there exists d unknown (signed) measures over S B(-) transition probability P(-|s, a) = (d(s, a), B()))
(()),,....,..))) such that the
In the rest of this paper, in the tabular setting we assume that the dimension d x A and we use a one hot embedding where we map (s, a) + (ss, s, a) = cs.a. a unique standard basis vector. It is easy to show that this system is linear MDP (Jin et al., 2020) and Q-lcarning in this setting reduces to the standard tabular Q-learning (3). However, when the assumption of a tabular MDP allows us to obtain stronger results, we will present the analysis separately.
Inherent Bellman Error There is another widely studied class of MDPs which admit a good linear representation (Zanette al., 2020; Munos & Szepesvári, 2008; Szepesvári & Smart, 2004).
Definition 2. (ZIBEL MDP) For an M = MDP(S, A, RR) with a feature map a S x A + Rd, we define the inherent Bellman error (IBE(M)) as:
sup inf sup (s,4)ESxA
(((ss a),s,a), 0') R(s,a) -. sup (0, 605' a')Il d'EA
BER O'ERd
If IBE(M) = 0. then call this MDP 7IBEL (zero inherent Bellman error with linear function approximation) MDP.
The class of ZIBEL MDPs is strictly more general than the class of linear MDPs (Zanette et al., 2020). Both these classes of MDPs have the property that there exists a vector w" E Rd such that the optimal fuunction, Q* a) (Ø(s, a), w²) for every (s,a) S x A, which can be explicity expressed as a function of 8, 3 and Q". More generally, they allow us to lift the Bellman iteration to Rd exactly and update our estimates for w" values directly (Lemmas 3, 4).
Hence, we can focus on estimating Q' by estimating w". To this end, the standard Q-Learning approach to learning the Q function can be extended to the linear case follows:
5

---

Published as a conference paper at ICLR 2022
W++1 = We + Tt rt + max
(o(s++1,, m d'EA
wi) - (d(or, ar), we) o(srs at).
The above update can be seen as a gradient descent step on the loss function f(w.) (10(s,, dt), -tagett) where target +y max. (0(++),, wz). This update while heavily used practice, has been known to be unstable and does not converge to w² general. The rea- son often cited for this phenomenon is the presence of the 'deadly triad' of bootstrapping, function approximation, and ooflco learning.
2.1 ASSUMPTIONS
We make the following assumptions on the MDPs considered through the paper in order to present our theoretical results.
Assumption 1. The MDP M has (BE(M) 0 (Definition 2), [ a)ll S 1. Furthermore, R(s,a) E [0, 1].
Assumption 2. Lei 4 = ( (8,a) E E ((s, a) measurable.
ESxx x A). & is compact, s Rd and (s, a)
Even when span o Rd, our results hold after discard the space orthogonal the span of em- bedding vectors in Assumption 4 and note that Q-Rex does not update the iterates along $
Definition 3. For > 0, let ( || l12. r) be the r-covering mumber under the standard Euclidean norm over RRd. Define:
Co Co==/ [ Vlog 11,,,,,,,,1111 r)2r
Observe that since & is subset of the unit Euclidean ball in Rd, Co S CVd. However, in the case of tabular MDPs is easy to show that Co S CVlogd d. Definition 4. We define the norm lle over Rd by || = suP() K (() a)]
This is the natural norm of interest for the problem (Lemmas 2 and 4). We assume the existence of fixed (random) behaviour policy S - ((A) which selects a random action corresponding to each state. At each step, given (st, at) = (s, a), 81+1 ~ P(|ss, a) and ac+1 ~ (s{++)). This gives Markov kernel over S x A which specifies the law of ($t+1, a(+1) conditioned on (st, at). We will denote this kernel by p This setting is commonly known as the off-policy asynchronous setting. We make the following assumption which is standard in this line of work.
There exists unique stationary distribution ps for the kernel pa, Moreover, this Markov chain is exponentially ergodic in the total variation distance with mixing time Tmix- That is, there exist constant Cmix for every N
Assumption 3.
sup (V.(P") S Cmix exp( exp(-t//mii) #ESXA
In the tabular setting, we will use the standard definition of Tmix instead:
Tmix = inf(t:
sup (V((PT)(( S 1/4).
zESxA
Here TV refers to the total variation distance.
Assumption 4. There exists K. > such that: E(s.a)) a) (s,
Remark 1. (Bresler al., 2020, Theorem 1) shows that even linear regression with Markovian data, zero noise and (² recovery is hard when the condition number or the mixing time Tmix are too large. Hence, our setup of noisy reinforcement learning with for error also requires these quantities be small. Therefore, Assumptions 3 and 4 are necessary in order to obtain non-trivial bounds.
In the tabular setting, Assumption 4 manifests itself as 1 = Pmin := min (s.a) juss, a) which is also standard (Li et al., 2020b). Whenever discuss high probability bounds (i.e, probability at least 1 - 5), we assume that E (0, 1/2). Similarly, we will assume that the discount factor y E (1/2 so that absorb poly(1/7) factors into constants.
k

---

Published as a conference paper at ICLR 2022
Algorithm Q-Rex
Input: learning rates 73, horizon T, discount factor 7, trajectory X; = {st, 0t, rt), Buffer size
B. Buffer gap u, Number of inner loop buffers NN
2: Total buffer size: S <- B + Outer-loop length: K f
T NS.
Initialization w."'
3: for =
K do
4: for j 1, ..... .N do
5:
Form buffer Buf (X ..... ss' where, X t XNS(R-1)48G-1)) - (65, ..
6:
Define for all i E 1, S). of
7:
for i l...., do
8:
k.j 141 = u. +n
k.j "++1-
( ( kjj
max a'eA
kij with) B+2- a'), wf (0 04-1-1
Option I: w/ - WB B+1
9:
10:
Option II: 11
k
Σ
i=
kj 141
Option I: 1 k+1,1
N,N+1
11:
12:
Option II wi
1+1,1 21=2
11
k.
13: Return w1
K+111
Time
Buffer Collection Order
Buffer Collection Order
Buffer proceesing order
Buffer processing
Bufter 1m1
Gop
Butfer j+2
Gap
Butter
Gap
Butter pri
Loop Iteration
(Target is foxed through the loap)
Buffer Langth B
Gap Length
Figure I: Illustration of Online Target Q-learning with Reverse Experience Replay
OUR ALGORITHM
As discussed in the introduction, we incorporate RER and OTL into Q-learning and introduce the algorithms Q-Rex (Online Target Q-learning with reverse experience replay, Algorithm 1), its sam- ple efficient variant Q-RexDaRe (Q-Rex + data reuse, Algorithm 2) and its episodic variant EpiQ- Rex (Episodic Q-Rex, Algorithm 3). Since QeRe and EpiQ-Rex are only minor modifications of Q-Rex, we refer the reader to the appendix for their pseudocode.
Q-Rex is parametrized by K the number of iterations in the outer-loop, N the number of buffers within outer-loop iteration, B the size of buffer and the gap between the buffers. The algorithm has a three-loop structure where at the start of every outer-loop iteration (indexed by & E [K]. we checkpoint our current guess of the Q function given by w Each outer-loop iteration corresponds to an inner-loop over the buffer collection with N buffers, i.e. iteration j [N], we collect buffer of size B + u consecutive state-action-rewe the first B collected experiences and perform the target based Q-learning update in the reverse order for these experiences. We refer Figure for illustration of the processing order. Of note, is the usage of checkpointed target network the RHS of the Q-learning update through the entirety of the outer-loop iteration, i.e. for fixed and for all j, i, our algorithm sets
tuples. For every collected buffer we consider
kij W.+1 w!
AJ kJ + +1 "B1--s + max kJ B42-5 a'), wk
Kg (0
ki B
Figure/ provides an illustration of the processing order for our updates. It can be seen that the number of experiences collected through the run of the algorithm is KN + u). For the sake of simplicity, will assume that the initial point, w O. Essentially the same results hold for arbitrary initial conditions. RexxDe is a modification of Q-Rex where we re- re-use use the data from the first outer-loop iteration (i.e, data from k 1) in every outer-loop iteration (i.e, k 1).

---

Published as a conference paper at ICLR 2022
Setting
K
N
B
ZIBEL MDP
21
C. log ((T-1))
Tmxx logí KNa
10u
Camin (1-5)
(THEOREM I)
TABULAR MDP
(THEOREM 2)
2 C2
[ox]
> C4 log(
(STAII
2 CiTiii log! K.N.)
10u
<
logl (SSAA
Og
TABULAR MDP
(TUEOREM 3)
2 C2
log
1-4
>
Co
D Male
log! (
2 CiTiiic log! K
10u
< C3 [t-yya
illgg
(THEOREM 1)
ZIBEL MDP
(T-3)
Ch K:ly maxd "m 1)
Tmix log (*x)
10u
unins (00ii(0mm))) (0-m)
C2. 25 (x)
TABULAR MDP
(THEOREM 2)
max
(Bh, _..1)
log (XF)
10u
[1=71" min(e, e*)
TABULAR MDP
(THEOREM 3)
(1-19
Prste
max (Ps-
Timix log( 8
10kc
min
34
dis
Table 2: Parameter constraints (first rows) and choice for < eiror (last 3 rows) for our algorithms. Here the poly-log factors 3e are given by 31 = log (1-7) m)) Ao = log (1-7)38 min((,))
B2 = (K) 33. 54 = log( [SI]A1K), As = log( (S|]LA)).
Remark 2. For the sake of clarity, we only analyze the algorithms Q-Rex and Q-RexDaRe for data from a single trajectory with Option I. Option II involves averaging of the iterates which boosts the convergence - indeed we can obtain much better bounds in this setting by using standard analysis.
MAIN RESULTS
We will now provide finite time convergence analysis and sample complexity for the algorithms Q-Rex and Q-RexDaRe. Recall that K is the number of outer-loops, N is the number of buffers inside outer-loop iteration, B is the buffer size and u is the size of the gap. In what follows, we will take Ō B 10u, K ((r_T)) We also note that the total number of samples used (K( + u) for Q-Rex and N + u) for Q-RexDaRe since we reuse data in each outer-loop iteration. what follows, by Q K+1.1 (s, a), we denote (Ø(s, a), wi K+1.1 which is our estimate for the optimal Q function. Here w1 K+1,1 is the output of either Q-Rex or Q-RexDaRe at the end of K outer-loop iterations. Define [|Q] 110k+1,1
Ql := a / K K+1, (s, a) Q" (s, a)). We
first consider the performance of Q-Rex with data derived from linear MDP (Defintion 1) or ZIBEL MDP (Definition 2) and satisfying the Assumptions in Section 2.1.
Theorem (ZIBEL /Linear MDP). Suppose we run Q-Rex using Option I with data from an MDP with IBE 0. There exists constants C1, C2, C3, Ca, Cs > O such that whenever the parameter bounds given in Table (row 1) are satisfied, then with probability at-least 1 - 5, we must have:
0/88-1o8( 41
1 K - Q" S i + CaV Ūा- exp (- ANB + +Cs1
(1-7)-
Given E (0, و and the parameters as given in Table (row 4)(up to constant factors), then with probability at-least 1 8: |[@++11( (s,a) (*,ssa)lloc < c. This has a sample complexity
O(NKB) = maxx
c8+1 Tmll (1-1).. 1-
We consider the performance of Q-Rex and Q-RexDaRe in the case of tabular MDPs. We refer to Table 1 for a comparison of our results to the state-of-art results provided in literature for Q-learning based algorithms.
Remark 3. To the best of our knowledge, Theorem I presents the first non-asymptotic convergence results for Q-learning based methods for ZIBEL MDPs under standard assumptions. Notice that the sample complexity scales as 3/2 + Tmix instead of Suga like in Zou et al. (2019b); Bhandari et al. (2018). This is because in the case of ZIBEL MDPs RER brings out the super-marttnngae structure present in the problem which forward pass does not.
Theorem 2 (Tabular MDP). Suppose we run Q-Rex using Option I with data derived from tabular MDPs. Whenever the algorithmic parameters are picked as given in Table (row 2) for some universal constants Ci...., Cs, we obtain with probubility at-least 8:
1 <Cs
-- + exp(
MMmin NB
n log K|S||AA)
+
log
K|S||A| 6
8

---

Published as a conference paper at ICLR 2022
Where L
by K log I-7
Given (0, 1- and the parameters picked as given in Table 2 (row
5). then with probability at-least 1 - 8, we have: [1Q 100-t-Q11lee < t. This gives us sample
complexity of
O(NKB) - 0 ( max
(I-3) min(e,e"))
Even though the sample complexity provided in Theorem matches the sample complexity of syu- chronous Q-learning even with asynchronous data, it is still sub-optimal with respect the min-max lower bounds (i.e, it has dependence of has a dependence of (T-タyт instead of the optimal (1- We resolve this gap for QeRexDaRe in Theorem 3. For tabular MDPs, the number states can be large but the support of P(-ss, a) is bounded in most problems of practical interest. Consider the following assumption (note that this holds for every tabular MDP with d = [S|)
Assumption 5. Tabular MDP is such that (supp(P(()s, al) S d N.
Theorem (Tabular MDP with Data Reuse). For tabular MDPs, suppose additionally Assumption holds and we run Q- R-ReeDaRe using Option I. There exist universal constants C1. C2. C3, C2 such that when the parameter values satisfy the bounds in Table 2 (row 3), with probability at-least 5:
[xpp
DHmm NB t
|S|LA|K 5
110 110+L11 10*+ SC
QQ
n log
Vā+ V(- (1-2)a log(
K K(S|LAI)
(1-7)2
(1-3)3
Suppose 6 E (0, 1 If we choose the parameters as per Table (row 6), then with probability at-least 1 5 we have; 11QK+ 17 < The sample complexity in this case is
Va ))
O(NB) = Amin
max (Tmixs 2[|17]3: (I-932+ -l1>))))
OVERVIEW OF THE ANALYSIS
We divide the analysis of Q-Rex and Q-RexDaRe into two parts: Analysis of # obtained the end of outer-loop iteration & and the analysis of the algorithm within the outer-loop. The algorithm reduces to SGD for linear regression with Markovian data within an outer-loop due to OTL. That is, we try to find w k+1,1 such that (w/+1., k+1,1 (ss a)) z R(s, a) + Bx-P((-lss sup, (w h.1 o(s', ,a))-
Therefore, write w1 k+1,1 T( k.1, +ex((u) (u( (..) where T is the y contractive Bellman operator whose unique fixed point is w² and ед is the noise to be controlled. Following a similar setting in in (Jain et al., 2021b), control 6g with the following steps:
(1) We introduce a fictitious coupled process (see Section C) (ăt, ā, Fr) where the data in different buffers are exactly independent (since the gaps of size u make the buffers approximately indepen- dent) and show that the algorithm run with the fictitious data has the same output as the algorithm run with the actual data with high probability when u is large enough.
(2) We give
decomposition (Lemma 5) for the error én where the exponentially de- caying bias term helps forget the initial condition and the variance term arises due the inherent noise in the samples.
(3) We control the bias and variance terms separately in order to ensure that the noise e is small enough. RER plays a key role in controlling the variance term by endowing it with super- martingale structure, which not possible with forward order traversal (see Theorem 4).
The procedure described above allows us to show that 1+1,1 v T(w k,1y uniformly for k S K, which directly gives convergence bound to the fixed point of T i.e, w² (Theorem 1). In the tabular case, the approximate Bellman iteration connects to the analysis of synchronous Q-learning in (Li al., 2021). which allows us obtain a better convergence guarantee (Theorem 2). To obtain convergence guarantees for Q-RexDaRe, we first observe that if we re-use the data used in outer- loop iteration 1 in all future outer-loop iterations & > 1, (w("!) might not be small since k. depends on (-). However, (w ))x approximates the deterministic path of the noiseless Bellman iterates: w6-11 := w and w *+1,1 == T (w Since || (w ) S (wed(w) - e²(w + Iloo. we argue inductively that (w ct (wf ll z 0 since whil k,1 w and ||e (wo ss 0 since w. is deterministic sequence and hence wi
&+1,1 w 1+1,1

---

Published as a conference paper at ICLR 2022
ACKNOWLEDGMENTS
Most of this work was done when D.N. was graduate student MIT and was supported in part by NSF grant DMS-2022448. Part of this work was done when D.N. was a visitor at the Simons Institute for Theory of Computing, Berkeley. We would also like to thank Gaurav Mahajan for introducing us to low-inherent Bellman eπror setting, and providing intuition that our technique might be applicable in this more general setting (than linear MDP) as well.
10

---

Published as a conference paper at ICLR 2022
REFERENCES
Alekh Agarwal, Sham Kakade, and Lin F Yang. Model-based reinforcement learning with gener- ative model minimax optimal. In Conference on Learning Theory, pp. 67-83. PMLR, 2020.
Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert Kappen. Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91(3): 325-349, 2013.
Leemon Baird. Residual algorithms: Reinforcement learning with function approximation. In Machine Learming Proceedings 1995, pp. 30-37. Elsevier, 1995.
Carolyn Beck and Rayadurgam Srikant. Error bounds for constant step-size q-learning. Systems & control letters, 61(12):203-1108, 2012.
Dimitri P Bertsekas. Dynamic programming and optimal control 3rd edition, volume ii Belmont, MA: Athena Scientific, 2011.
Jalaj Bhandari, Daniel Russo, and Raghav Singal. A finite time analysis of temporal difference learning with linear function approximation. In Conference on learning theory, pp. 1691-1692. PMLR, 2018.
Vivek S Borkar and Sean P Meyn. The ode method for convergence of stochastic approximation and reinforcement learning. SIAM Journal on Control and Optimization, 38(2):447-469, 2000.
Justin Boyan and Andrew W Moore. Generalization in reinforcement learning: Safely approximat- ing the value function. Advances in neural information processing systems, pp. 369-376. 1995.
Guy Bresler, Prateek Jain, Dheeraj Nagaraj, Praneeth Netrapalli, and Xian Wu. Least squares regres- sion with markovian data: Fundamental limits and algorithms. arXiv preprint arXiv:2006.00 08916, 2020.
Diogo Carvalho, Francisco S. Melo, and Pedro Santos. A new convergent variant of q-learning with linear function approximation. H. Larochelle, M. Ranzato, R. Hadsell, M. Balcan, and H. Lin (eds.), Advances in Neural Information Processing Systems, volume 33, pp. 19412-19421. Cur- ran Associates, Inc., 2020. URL attps::/proceeedinggg wtwp:eediiiinnnnnnnieeeeeeeeeeee neurips cc/ wwtppppr//20//////// pdf.
Zaiwei Chen, Sheng Zhang, Thinh Doan, John-Paul Clarke, and Siva Theja Maguluri. Finite- sample analysis of nonlinear stochastic approximation with applications in reinforcement learn- ing. arXiv preprint A905: 1425, 2019.
Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes. arXiv preprint 00204 2020.
Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor. Finite sample analyses for td (0) with function approximation. In Thirty-second AAAI conference on artificial intelligence, 201 Sa.
Gal Dalal, Gugan Thoppe, Balázs Szörényi, and Shie Mannor. Finite sample analysis of two- timescale stochastic approximation with applications to reinforcement learning. In Sébastien Bubeck, Vianney Perchet, and Philippe Rigollet (eds.), Proceedings of the 31st Conference On Learning Theory, volume of Proceedings of Machine Learning Research, pp. 1199-1233. PMLR, 06-09 Jul 2018b. URL https: htttp:://proceedingg mlr www.s//eessse... /ttress//////daallllll.. html.
Thinh T Doan, Lam M Nguyen, Nhan H Pham, and Justin Romberg. Convergence rates of ac- celerated markov gradient descent with applications reinforcement learning. arXiv preprint 2oXiv:2002.02873.. 2020.
Jianqing Fan, Zhaoran Wang. Yuchen Xie, and Zhuoran Yang. A theoretical analysis of deep q- learning. In Learning for Dynamics and Control, pp. PMLR, 2020.

---

Published as a conference paper at ICLR 2022
David A Freedman. On tail probabilities for martingales. the Annals of Probability, pp- 100-118, 1975.
Mohammad Ghavamzadeh, Hilbert Kappen, Mohammad Azar, and Rémi Munos. Speedy q-
learning. Advances in neural information processing systems, 24:2411 2419,, 2011.
Sheldon Goldstein. Maximal coupling. Zeitschrifi für Wahhschhennicckeetssheeerr und verwandte Gebiete, 46(2):193-204, 1979.
Geoffrey Gordon. Reinforcement learning with function approximation converges to region.
Advances in neural information processing systems, 13, 2000.
Harsh Gupta, R. Srikant, and Lei Ying. Finite-time performance bounds and adap- tive learning rate selection for two time-scale reinforcement learning. In H. Wal- d'Alché-Buc, E. Fox, and R. Garnett (eds.),
lach, H. Larochelle, A. Beygelzimer, Advances in Neural Information Processing Systems, volume 32. Curran Associates, Inc., 2019. URL https: pttps:://proceedinggg wwwpo/eeeeeniinn.nneneeeeeeeeeee neurips wttpppppr///19//11111.. pdf.
Prateek Jain, Suhas S Kowshik, Dheeraj Nagaraj. and Praneeth Netrapalli. fline and streaming algorithms for learning non-linear dynamical systems. arXiv:2105.11558. 202la.. 2021a.
Near-optimal of- arXiv preprint
Prateek Jain, Suhas S Kowshik, Dheeraj Nagaraj, and Praneeth Netrapalli. Streaming linear system identification with reverse experience replay. arXiv preprint arXiv:2103.05896 2021b.
Chi Jin, Zhuoran Yang. Zhaoran Wang, and Michael Jordan. Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory, pp. 2137-2143. PMLR, 2020.
Michael Kearns and Satinder Singh. Finite-sample convergence rates for q-learning and indirect algorithms. Advances in neural information processing systems, pp. 996-1002, 1999.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in neural information processing systems, 33, 2020a.
Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen. Sample complexity asynchronous q-learning: Sharper analysis and variance reduction. In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.). Advances Neural Information Processing Systems, volume 33, pp. 7031-7043. Curran Associates, Inc., 2020b. URL https: /ttpc//eeooc..ssseee/eepsscs..se neurips. ccc scc/paper/202//Eii0
Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, and Yuejie Chi. Is q-learning mini- max optimal? tight sample complexity analysis. arXiv preprint arXiv:2102.06544 2021.
Long-Ji Lin. Self-improving reactive agents based reinforcement learning, planning and teaching.
Machine learning, 8(3-4):293-321, 1992.
Hamid Reza Maei, Csaba Szepesvári, Shalabh Bhatnagar, and Richard S. Sutton. Toward off-policy learning control with function approximation. In Proceedings of the 27th International Con- ference on International Conference on Machine Learning, ICML'10, 10, pp. 719-726. Omnipress, 2010. ISBN 9781605589077.
Francisco S Melo, Sean Meyn, and Isabel Ribeiro. An analysis of reinforcement learning with function approximation. In Proceedings of the 25th international conference Machine learning, pp. 664-671, 2008
Volodymyr Mnih, Koray Kavukcuoglu, David Silver. Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 8(754)) 2015.
Rémi Munos and Csaba Szepesvári. Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(5), 2008
12

---

Published as a conference paper at ICLR 2022
Daniel Paulin. Concentration inequalities for markov chains by marton couplings and spectral meth- ods. Electronic Journal of Probability, 20:1-32, 2015.
Theodore Perkins and Doina Precup. A convergent form of approximate policy iteration. Advances in neural information processing systems, 15, 2002.
Guannan Qu and Adam Wierman. Finite-time analysis of asynchronous stochastic approximation and q-learning. In Conference Learning Theory, pp- 3185-3205. PMLR, 2020.
Martin Riedmiller. Neural fitted q iteration-firs' experiences with data efficient neural reinforce- ment learning method. In European conference on machine learning, pp. 317-328. Springer, 2005.
Egor Rotinov. Reverse experience replay. arXiv preprint arXiv:1910008780, 2019.
Rayadurgam Srikant and Lei Ying. Finite-time enror bounds for linear stochastic approximation andtd learning. In Conference Learning Theory, pp. 9903-2830. PMLR, 2019.
Richard S Sutton. Learning to predict by the methods of temporal differences. Machine learning, 3 (1):9 44, 1988.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018. 8.
Csaba Szepesvári and William D Smart. Interpolation-basee q-learning. In Proceedings of the twenty-first international conference on Machine learning, pp. 100, 2004.
John Tsitsiklis and Benjamin Van Roy. Deasede-based methods for large scale dynamic program- ming. Machine Learning, 22(1):59-99) 94, 1996.
John Tsitsiklis and Benjamin Van Roy. An analysis of temporal-difference learning with function approximation. IEEE transactions automatic control, 42(5))674-69)) 1997.
Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018
Martin Wainwright. Stochastic approximation with cone-contractive operators: Sharp 6o0 -bondd 2019a.
for q-learning. arXiv preprint
Martin J Wainwright. Variance-reduced q-learning is minimax optimal.
arXiv preprint
arXiv: 04697, 2019b.
Martin J. Wainwright. High- Digeeniimesional Statistics: A Nom-Asymptotie Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019c. doi: 10.1017/ 9781 108627771.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-292, 1992.
Christopher John Cornish Hellaby Watkins. Learning from delayed rewards. 1989.
Bowen Weng, Huaqing Xiong, Lin Zhao, Yinghin Liang, and Wei Zhang. Momentum q-learning with finite-sample convergence guarantee. arXiv preprint arXiv:2007.15416 2020.
Lin Yang and Mengdi Wang. Sample-optimal parametric q-learning using linearly additive features. In International Conference on Machine Learning, pp. 6995-7004. PMLR, 2019.
Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill. Learning near op- timal policies with low inherent bellman error. In International Conference on Machine Learning, pp. 10978-10989, PMLR, 2020.
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for sarsa with linear func- tion approximation. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, Fox, and R. Garnett (cds.), Advances in Neural Information Processing Systems, volume 32, Curran Asso- ciates, Inc., 2019a. URL https:tt///m httpt:::s//ppcceeiigg...... wttpeeediiiinnnnuuispeee http:/aappe229///1eee. 9f9e8cba3" wew.00f6.4488ff1105555008
Shaofeng Zou, Tengyu Xu, and Yingbin Liang. Finite-sample analysis for sarsa with linear function approximation. Advances in neural information processing systems, 32, 2019b.
13

---

Published as a conference paper at ICLR 2022
A EXPERIMENTS
Even though OTL has a stabilizing effect on the Q-iteration, it reduces the rate of bias decay since the values are not updated for a long time. Therefore, the success of our procedure depends on picking the right values for the parameters N, B and Option I vs. Option II. However, under the right conditions the algorithms which include OTL+RER converge to much smaller final error as illustrated by the examples we provide in this section. If a better sample complexity is desired, then Q-RexDaRe can be used as shown by Theorem 3. Further research is needed to identify the practical conditions such as (function approximation coarseness, MDP reward structure etc.) under which techniques like OTL+RER help.
100-State Random Walk We first consider the episodic MDP (Sutton & Barto, 2018, example 6.2) - but with 100 states instead of 1000. Here the agent can either move left right on straight line, receiving a reward of at each step. Reaching the right terminal point ends the episode with reward 1, while the left terminal point ends the episode with reward 0. In each episode, the initial point is uniformly random and the offline policy chooses right and left directions uniformly at ran- dom. We use state aggregation to obtain a linear function representation (Sutton & Barto, 2018) with total 10 aggregate states. Along with 2 actions, this leads to a 20 dimensional embedding. We compare vanilla Q-learning, OTL+ER+O-leaniin same step size (0.01) was chosen for all the algorithms. OTL+ER+Q has the same structure as EpiQ-Rex and was run with the same parameters as EpiQ-Rex The main difference between the two algorithms is that OTL+ER+Q processes the experiences collected in each episode in a random order processing instead of reverse order. Refering to Figure 4, we note that the bias decay for EpiQ- Rex and Q are slower than vanilla Q-learning due to the online target structure. However EpiQ-Rex converges to a better solution than the other algorithms.
and EpiQ-Rex (Option II, N 1). The
Mountain Car We run an online control type experiment with the Mountain car problem (Sutton & Barto, 2018, Example 10. The task here is to control the car and help it reach the correct peak (which ends the episode) as soon as possible (i.e, terminate the episode with fewest steps). The agent receives reward of -1 unless the correct peak is reached. Here we run EpiQ-Rex with Option I and N = 1, OTL+ER+Q-leannin policy at the end of k 1-th episode for each of the three algorithms. We use = 4 tile coding to represent the Q values for a given action, each of which has 4 x 4 squares. The step-size was picked as 0.1/n and the result was averaged over 500 runs of the experiment. We refer Figure for the outcomes. For the last 300 episodes, the mean episode length for Vanilla Q-learning was 145, EpiQ-Rex was 136 and OTL+ER+Q-leariin was 143 (rounded to the nearest integer).
and vanilla Q-learnnng The k-tt episode is generated with the
Grid-World We consider the grid-world problem which is tabular MDP (Sutton & Barto, 2018, Example 3.5), which is a continuing task. Here, an agent can walk north, south, east or west in a 5 x 5 grid. Trying to fall off the grid accrues a reward of 11, while reaching certain special states accrues a reward of 10 or 5. In our example, we also add unif[-0.5, 0.5] noise to all rewards to make the problem harder. We run the grid world experiment with the discount factor y 0.9 and step size 0.05 for Vanilla Q-learning, Q-Rex (Option II, B = 3000, N = 1) and OTL+ER+Q- learning which run with the same parameters as Q-Rex but with random samples from the buffer. We run the experiment 30 times and plot the error in the Q-values vs. time in Figure 3.
Baird's Counter-Example Consider the famous Baird's 's counter-example shown in Figure 6. The features corresponding to each state is shown and the reward for any transition O. Thus, w* is the optimal solution. Since Assumption 4 made in this work is violated for this example, we consider the analog of the problem where at each step, a state sampled uniformly at random and the corresponding transition, along with the 0 reward is used to learn the vector w. In the experiment, we set the problem and algorithmic parameters to be 7 0.99 and = 0.01 /5 (the factor of v5 normalizes the features to satisfy Assumption 1). We set B = 50, u = 0, and N = 5 since there is no need for keeping a gap between the buffers in this experiment. Figure 7 shows the non-convergent behavior of vanilla Q-Learnig while -aLebased Q-learning converges. Note that since the sampling of state, action and reward is done in uniformly random fashion, it is not relevant to use reverse experience replay. It is easy to see that with data reuse, we only need few samples to ensure all states covered; the rate of convergence would be same as that of OTTL+Q-leaming.
14

---

Published as a conference paper at ICLR 2022
E:42 Rox
Epl on aeitu bomenn
OTL-3nVG-
Epieodes
Time
Figure 2: Mountain Car problem
Figure 3: Grid woold problem
Wanis CHeamiing
ColD- flnn
d-eaming
330
230
200
110
03
00050
102000
Figure 100 State Random Walk
Figure Linear System Problem
Vantila Q-leaning OTL+O leamning
State
State 2
State 3
State
State
2e 7
277 I 22y
22's Z
22, i 2
22% I 2
mpt 9000
27,
State
20000
60000
00200
20000
3000ED
Stepo
Figure 6: Feature embedding in the modified Baird's counter-example: éū represents the i- th canonical basis vector R². Each transi- tion shown occurs with probability 1.
Figure 7: Performance of vanilla Q-learning as compared to OTL+Q-learnng, averaged over 10 independent runs
Linear Dynamical System with Linear Rewards We also compare the algorithms on linear dynamical systems problem. While the problem described next is strictly not linear MDP, the value functions for certain policies can be written linearly in terms of the initial condition; this is made precise next. Consider a linear dynamical system with initial state being Xo E Rd The state evolves X AX, + T/, where A Rdxd The reward obtained for such transition given by (X,, 8) for a fixed E IRd. The maximum singular value of A is chosen less than ensure that the system is stable. The infinite horizon 7-discounted expected reward is given by (Xo, oz (7." Thus, the expected reward can be written as (Xo, w*), where
w² wT=
Since there are actions in this case, the Q learning algorithms reduce to value function approx- imation (i.e, TD(0) type algorithms). We take the embedding o(X.) Xx, the identity mapping. We considered d = 5. 7 0.99, " 0.01, and a randomly generated normal matrix A and 0. We Option II for Q-Rex along with B = 75, u = 25, and N for the experiments. For OTL+ER+Q- learning, keep the same parameters, but with random order sampling, while ER+Q-learnnng does not include OTL. The results shown in Figure 5 are averaged over 100 independent runs of the experiment. Note that the errors considered are using iterate averaging.
15

---

Published as a conference paper at ICLR 2022
As seen from Figure 5, Q-Rex outperforms vanilla Q-learning and OTL+ER-based Q-learning one would expect based on the theory presented this work. However, is interesting to note that ER+O-learning performs slightly better than Q-Rex. One possible reason could be due to the fact that in Q-Rex, the target gets updated at slower rate at the cost of reducing bias. However, setting smaller value of N B might resolve the issue.
B DEFINITIONS AND NOTATIONS
B.1 Q-REXDARE
The psuedocode for Q-RexDaRe is given in Algorithm 2. Note that we reuse the sample data in every outer-loop iteration instead of drawing fresh samples.
Algorithm Q-RexDaRe
1: Input: learning rates 1/. horizon T, discount factor % trajectory X, {st, 0s, 0e, re), number of outer-loops K buffer size B, buffer gap u
2: Total buffer size: S 4- B +
3: Number of buffers loops: N <- T/S
4: 1.1 = 0 initialization
5: for 1..... K do
6: for j 1..... NN do
Form buffer Buf = (X ..... x where,
7:
x.J X1(-
Define for all S) k.j A ((5 )
8:
9:
for i = 1,..., do
10:
w ++1 = w,
+n
k.j r
B+1-: + maxo m (0) k.j
11 10 0
kud withi)
W1 kjtl kj
W
1+1,1
k.N+1
12:
W1
w1
Return w
B.2 EPIQ-REX
The psuedocode for EpiQ-Rex is given in Algorithm 3. Note that the buffers here are individual episodes and can vary in size due inherent randomness. We do not require gap here since separate episodes are assumed to be independent.
MDP definition Here construct the MDP with (possibly) random reward We consider non-episodic, i.c. infinite horizon, time homogenous Markov Decision Processes (MDPs) and we denote an MDP by MDP(S.A, 7, P) where S denotes the state space, A denotes the action space, represents the discount factor, P(s'|s, (s, a) represents the probability of transition to state s' from the state s action a. We assume for purely technical reasons that S and A are compact subsets of R for some n E N). r is reward process (not to be confused with Markov Reward Processes iee MRP) indexed by S A S. such that r(s,a, a, s') E [o, 1] almost surely. We will skip the measure theoretic details of the definitions and assume that the sequence of i.i.d. reward processes (re)teN can be jointly defined over a Polish probability space. The function represents the deterministic reward R(s, a) obtained on taking action a at state and is defined by a(s, E [E....t P(-ss))) a. s')]. Here the expectation is with respect to both the randomness in the reward process and in state s'.
S A - [0. 1]
Now, given trajectory, (St, TT) which is independent of i.id sequence of rewards processes (rx) We observe (St, a,, Te (8,, 02 st41))==1+ and we will henceforth denote r, r5 Ge 8t+1) by jus
16

---

Published as a conference paper at ICLR 2022
Algorithm 3 EpiQ-Rex
Input: learning rates 17, number of episodes T, discount factor y Epsiodes Ez {($1, ri).......... (5%, 'B "B, ",,,,, Number of buffer per outer-loop iteration N.
2: Number of outer loop iterations: K <- T/N
3: wi = 0 initialization
4: for k = L,..., K do
5: for 1, N do
6:
1 t (k - 1) N +j NJ
7:
Collect experience and form buffer Buf {X,, X,,, ). where,
x (5), ri)
Define for all i [1 B, - 1), o Kō (( k.
a. a...)).
8:
9:
for i = 1, 1..... ,B do
kJ w u 4: +1
k.
B,- + y max E (0( Aod (0 d'), wt.l) (0% w w o
Option I: w1 k.tt B.
k.j
11:
12:
Option 1::0 k,jt1
B.-1 Σ w
N.1+1
13:
Return w1 K,1
14:
Notation Due to three loop nature of our algorithm it will be convenient to define some simplitying notation. To this end, consider the outer loop with index [K] and buffer number j E [N] inside this outer loop. Further given an i E [S] define a time index as / NS(k - 1) + S - 1) + i. We now denote the i-th nate-action-rewart tuple inside this buffer by
ai ;r kJ kJ Rd) = (s a T.p. (s
).). For conciseness, we define for all i, k. of h/ = ا ) Similarly, R.d = R( a.
Since we are processing the data in the reverse order within the buffer, the following notation will il be useful for analysis:
k.j
J.j = a a - 1 = BB R ==
Rh. B+1- and h.j = QB-1-1
== 8 B++1-: a
C COUPLED PROCESS
It can be seen that the buffers are approximately i.i.d. whenever we take u = O(Tiix log F) when- ever Assumption 3 is satisfied. For the sake of clarity of analysis, we will consider exactly inde- pender where we assume that the fictitious trajectory is generated such that the first state of every buffer is sampled from the stationary distribution μ.. We show that define it on common probability space as the original process (8t, at, rt)) such that
pendent buffers. That is, we assume the algorithms are run with fictitious trajectory (3,, a, f.),
couple this fictitious process (i.e,
P (nth Oi 1
(
kid Ri a. (8)
R-d)
ked kd ( 2 8.
(4)
Notice that the equality does not hold within the gaps between the buffer which are of size u but inside the buffers of size B only. That is, the sequence of iterates obtained by running the algorithm with the original data (st, ar, rt) is the same as the sequence of iterates obtained by running the algo- rithm with the fictitious coupled data (3,, āz, Fz) with high probability. We state this result formally Lemma 16 and prove it in Section M.I. Henceforth, we will assume that we run the algorithm with data (3,, ā, F.) and refer to Lemma 16 to carry over the results to the original data set with high probability. We analogously define 3 We will denote the iterates of the algorithm run with the coupled trajectory as whs instead of u. and will focus on entirely. We now provide some definitions based the above process. These definitions will be used repeatedly in analysis.
17

---

Published as a conference paper at ICLR 2022
D BASIC STRUCTURAL LEMMAS
We first note some basic structural lemmas regarding ZIBEL MDPs under the assumptions in Sec- tion 2.1. We refer Section M for the proofs.
Lemma 1. For tabular MDPs satisfying the assumptions in Section 2.1, for both Q-Rex and Q- RexDaRe, we have that for every k. j,j, i we have that ||ū llo
The lemma above says, in particular, that the Q-value estimate given by our algorithm never exceeds T-y due to initialization. The proof is straightforward induction argument, which omit. We will henceforth use Lemma without explicitly mentioning it.
Lemma 2. Suppose (s, (w, o(s, a)) and let (s. (w" "ot,,(ss,o a)) be the optimal Q function. Then:
sup (sa)eSxA
1w a) (s, = 1|0 w"
Moreover, we must have: ||-||| 2 | 2 |||||
for any IRd. vR
Lemma 3. For any wo R,, there exists unique w1 R& such that
(Wi, (lss a)) R(s,a) a) + 7 sup (o(s', wo).
e'EA
We will denote this mapping wo + wi by w1 ((w)). Lemma 4. T Rd Rd is y contractive in the norm || l| The unique fixed point of T is w². Moreover, we have: ||0" S l and || S 1-7
In view of Lemma 4, we can begin to look at the following noiseless Q-iteration. Let Φ = = 0 and ++1 = T (w*). This converges geometrically to w² with contraction coefficient under the norm || ||.. In our case, however, we only have sample access to the operator T. Therefore, our Q-iteration at the end k-th outer loop can be written as v² ----111 error introduced via sampling which needs be controlled.
((ok.1) + ε. where é is the
E BIAS VARIANCE DECOMPOSITION
We begin our analysis by providing bias-variance decomposition of the error with respect the noiseless Q-iteration at every loop. We will need the following definitions which we use repeatedly through our analysis.
Given step size outer loop index i and buffer index j. we define the following contraction matrices for a, b [B].
b II (1 (1- n
H
(5)
Whenever a > b, we will define A by (s,ssa) a) to be the number of samples of (s, a) seen in the outer loop k (excluding the gaps)
I. In the tabular setting, we define for any (s E S x A
N B
N* a) =
1((3)) ,at")) = (s,
Further we denote by N. (s, a), the number of samples of (s, a) seen in the outer loop i in the buffers post the buffer well as the number of samples of (s, a) in buffer before iteration Formally.
N Σ
No. NoW (s, a) Σ ((s a.)))) (8, (s)
1 a.d)) (s)
18

---

Published as a conference paper at ICLR 2022
We define the error term for any
ck ( - kbj R
+ sup (w,
(1 (g 141
a²)) ((8)41)a")
- 8 P(18, aa sup (0(s', ,2),,''), (6) dee
a'EAA
Finally we define the following shorthands for any i, k:
T ,+ == (
:= (wif-t)
I = E 3kJ
Given the above definition, the following the lemma provides the Bias- Variina decomposition which is the core of our analysis.
Lemma 5 Varrinar Decomposition). For every k have that,
Eg 1.1
II
hik k. 1,B w x++)
ΣI -I
Here and later on in the paper, use the reverse order in the product to highlight the convention that higher indices in 1,n appear towards the left side of the product and further define II 11 I. We call the first term in Equation (7) the bias term and it decays geometrically with N and the second term is called the variance, which has zero mean. We will bound these terms separately. Since tabular setting allows for improved analysis of error, will provide special cases for the tabular setting with refined bounds. We refer to Section M.5 for the proof of Lemma 5.
F BOUNDING THE BIAS TERM
F.1 TABULAR CASE
In the tabular case, we have the following expression for bias. We omit the proof since it follows from a simple calculation. Lemma 6. In the tabular setting, we have:
1
(ő(s, a), II
i xk+l,t)) = (1- -11-1) (=aa) wh+ p(s,a))
J=N
For particular outer loop k. we show that (* a) is D(PminNB with high probability whenever N B is large enough. For this use (Paulin, 2015, Theorem 3.4) similar to the proof of (Li et al., 2020b, Lemma 8). We give the proof in Section M.6.
Lemma 7. There exists a constant such that whenever B 2 Tmix and NB 2 Iuis log( [5)
with probability at least 1 8, we have that for every (s, a) E S x A:
Ñ* a) 2 2)(s,0)NBB 2 Hmmin NB
1
F.2 ZIBEL MDP CASE
Lemma 8. Suppose g e Ed is fixed and nB 1. Then, the following hold:
1.
El II
0i < exp(- 9NB )l
(8)
J=N
2. With probability at-least 1 we have:
E
II A I exp(-=ND > Iglll
K 2N0
9NB
We refer Section L.1 for the proof.
19

---

Published as a conference paper at ICLR 2022
G BOUNDING THE VARIANCE TERM
G.1 TABULAR CASE
In the tabular case, is clear that:
J+1 (o a), I
Σ 3 m) m) N. (s.a)) did 1((5))(())))))))))) _. = (s, j=l
me;
(9)
Now, we note that N (s, a) depends on data in buffers > j and when i < i inside buffer j. Following the discussion in (Li et al., 2021), we define the vector V (V*) E RSXA such that
( - Ey (()o(() sup (ols', a)), n Varp(Vi((s,a) = P()l)))) sup (o(s' (o( (.))
(10)
La'EA
a'En
) (11)
1
Varp(V*)(ssd)) = P(1so)
sup (o(ss','),,") BVNP(ila)) (()) sup (0(s' a'), a'
(op'"','a') w²),
a'EA
More generally, we define
sup (é(s', aa), w) ( sup (o(s', a)), w) 2
(V) E(
La'EA
d'EA
Similarly, we define I (w) by replacing with with any fixed, arbitrary w. It easy to see that:
E 1 (w))²
(8 abd (s) 2 (Varr as))
(12)
Lemma 9. In the labular setting, suppose is fixed vector such that (wo, ols a)) [0, T-y
every (s x A. Fix (s,a) E S A. Then there exists a universal constant C such that with probability atleast 1 6, we have that:
Then,
(0(s,a), a), EI 1.
J+1
1log 1-7
IEN
G.2 ZIBEL MDP CASE
We will use an appropriate exponential super-artingale bound the error term in the ZIBEL MDP case just like in the proof of (Jain et al., 2021b, Lemma 27). The following thereom summarizes the result and we refer Section L.33 for its proof.
Theorem 4. Suppose
E R& are fixed. Then, there exists universal constant C such that with probability at least 8, we have:
N 1+1
(I.
II i J=LLEN
s C||as|| (1 + (|w]la) log(2//8)
(13)
By a direct application of (Vershynin, 2018, Theorem 8. 8.6,6,, we derive the following corollary. We remind the reader that Cq. is the covering number defined in Definition 3.
Corollary 1. Suppose x. w E Rd are fixed. Then, there exists a universal constant C such that with probability least 8. we have:
1-1
Σ II
501+ luolld) Co v10g(3)
20

---

Published as a conference paper at ICLR 2022
In order apply the theorem above, will need to control ||w|-11, llo uniformly for all k. The following lemma presents such a bound and we refer to Section L.4 for the proof.
Lemma 10. Suppose प are the iterates of Q-Rex with coupled data from ZIBEL MDP.
There exist universal constants C,Ci, C2 such that whenever NB > Ci log ((1-7)) < (1-3) C2 oz (lgg( and nB < < with probability at-least 1 8, the following hold:
1. For every S k 5 K, [1 110 S 1-7
2. For every 1 < k < K, @i V
25K 0(1-7)
exp(
NNB
+
CVπ (I-
Co + v /log( 2xx
H PROOF OF THEOREM
Proof. Consider the learning iteration:
w1 k+11 -T( ēk
Using Lemma 4, we conclude:
1R+111 w¹ = - T(w")) + ep and thence: ūj
|100 k+1,1 w"lls I 71100 w" w'll + sup |all. ISK
Unrolling the recursion above, we conclude:
supısk Icall
|| K+111 w" lla I I| "
w=lla
1-7
Now, we invoke item of Lemma 10 along with the constraints on N, B, K, and Lemma 2 to conclude the result.
I PROOF OF THEOREM 2
In this section analyze the output of Q-Rex in the tabular setting and obtain convergence guar- antees. To connect with the standard theory for tabular MDP Q-learning in (Li et al., 2021), let us use the standard Q-function notation where we assume for all k, Qt E RSA and we have must have
that (s, @ wf.1 In the tabular setting, we see by using Lemmas 5, 6, 7, and 9 that for any 8 > O, there exists universal constant C, whenever NB 2 C. Imic log( [SII-A/K) ), with probability at-least Mmin
(wi ,6,, a)). Since Φ(s, a) the standard basis vectors,
1 6, for every is [K] and every (s, a) E S A:
@u+111 = [Qt + t
(14)
where ěs E SSS is such that for all (s)
0 log( KiS|(A
((((8, s C nlo KIS]IA|
(1 + (Vr
1-
Pmin NB
5 T (
(1
(15)
Now that we have set-up the notation, we will roughly follow the analysis methods used in (Li et al., 2021). Since we start our algorithm with Q = 0, and r, E [0, 1] almost surely, we can easily show
that 2 a) E [0, + for every k s, a. Therefore, we upper bound
< -
21

---

Published as a conference paper at ICLR 2022
in Equation (15) to conclude that with probability at-least 1 6, for every & [K] and every (s, E x A:
( a)l S CV logg KIS|LAi )r² Varp(VV)(s,
(16)
Where Og = O 7log log K|S||A|
expl Mimii
+ C
1-7
Now define As 0f Q" and Thy S A to be the deterministic policy given by Qt i., (s))) = arg argsupas.J (s, and X¹ to be optimal policy given by π (*(s) argsuPaEA Q" (s, a). We use the convention that we pick a single maximizing action using some rule whenever there are multiple. Similarly, we let pa*, be the Markov transition kernel over A given by (FM((sa)) o')) P(s'|s, a) (T()')). Similarly, we define p with respect to the policy πτ. It is easy to show that:
T(Ô = R + 7 Q
Similarly,
Q' Q'= R Q"
Furthermore given any RSXAA, letting #q being the greedy policy with respect to the function Q we have that for any policy æ, can be easily seen from the definitions that following element-wise inequality follows:
Pd S
P
We now use Equation (14) along with the equations above to conclude:
yP' A. + E S Ak+1 S Av. Eg.
(17)
Here, the inequality is assumed be point-wise. By properties of Markov transition kernels, write:
y (prt) K-k
K 26 g (pri)*
A S AK+1
1++11
K-k
pst
II N=
pm
Ar.
(18)
1=1
K
Here, we use the convention that K+1 pm: T. We bound the lower bound and the upper bound given in Equation (18) separately in order to bound ||
We first consider the lower bound. Using (Azar al., 2013, Lemma 7), we have:
2
(1=")""*)
Varrp(V)) I V (1-
(19)
We also note from (Li et al., 2021, Equation 64) and basic calculations that:
VV - )Var S / (V Varp(V*)]lo
Aalloo
(20)
22

---

Published as a conference paper at ICLR 2022
Using Equations (15) (16), we conclude that there exist universal constants C, C1 such that with
probability at least 1 - (interpreting the inequalities as element-wise wise):
AK+1 2- an + t K
OV mmm log(
KIS 6
K
7 K-
(pm')
K-k
VVrpp(Vi)
1 7
Og +
K K- (prt) K-k
CV 1772 log( K[S||A!
(Vrr((+*)
k=1
CCV 1 1-7
log
K(S) Al
Kー V1l
b
2 an k
CV 17,
log( KIS|IA|
(T - > Varr(V*)
k
KiSi A Ci V 1 1-7 V 1772 log
K-k |
3
1=1
Og +
1772
7 VV (1 7))3 log(
-CIV 1- V ?72 log K(S) Al)
K-k
(21)
In the above chain, the first inequality follows from Equations (16) (18), the second inequality from Equation (20) and the fourth inequality from Equation (19). For the upper bound consider the following set of equations interpreting them element-wise which hold for universal constant C' and with probability at least
k++1
1
AK+I S
II V=K
E + +
II A
pmd
b=
On + 7
+ CV 17 log( KIS LAl
K
K-k
k+1
p
Varr(VV)
1-7 7
k=1
I=K
5 On + K
K
K+1
+ CC 1n'2 log( KIS|AA
K-k
psi
Varp(V*)
7-7
A=1
|=K
On +, 1-7
+ 172 log( KAS|AA|
K
K-k
K-k
II pm VVr V=K
k++1
2
7
k=1
On + K
K
K
1K+1
<
+ CV. 1772 log KIS|AA))
K
K
II pm VVrp(Ve)
1 7
k=1
V=K
S Og 7
+ +C
m2
log(
K(S|IA 0
K 7 K-k
II pm V=K
k+1
Varr(Vi))
1 ?
y
ag + t K
m2
k+1
7//2
7 + C
1-7 log
K|S||AA)
K-
II I=
pm.
Varp(V&) +
(1 7)3
K//21
(22)
In the above chain, the first inequality follows from Equation (18), the second inequality follows from Equation (16), the third inequality follows from Jensen's 's inequality and noting that pr is Markov operator, the fourth inequality via Cauchy-Schward and the last inequality by noting that
that (Vi)lol & 1/(1- -7)².
23

---

Published as a conference paper at ICLR 2022
It can now be verified that (Li et al., 2021, Lemma 5) applies in our setting conclude that:
K
1+1 pm
K-k
II
(Vt)(Vi)) S 7² - 7)2
11+
max k/241skER
||
k=K/2+1
Using the equation above, along with Equations (22) and (21), we conclude there exists a universal constant C' such that with probability at least 6, we have:
Oty t A 1 7-7
gK/2
+0 +CV 7)3 log( KISIIA >
1 +
max K/2+1SA5K
A + (1-7) (23)
We note that this works with every K replaced with / for any S K. importantly under the same event (with probability least 1 - 8) described above for which Equation (23) holds. De- fine
K for some s [logg(1 + log( [)] Under the conditions of the Theorem, i.,
2
K CapT-R (Log( (18((1-)) )
we have 1- 1. Therefore we conclude from the discussion above
1/2
that for every K 1 2 L, we must have:
On + 7
| v
+ + V (1 [1- log( K(S||As)
"
1 + max
|
1 y
1/2+15kg!
On + 1 1-7 +C
n nlog( K
1 log K|S||A|)
$
(1 213
+ CVV
7)3
1/2+15kS!
max
| (24)
To analyze this recursion, we have the following lemma which establishes hyper-contractivity. whose proof we defer Section M.8.
Lemma 11. Suppose a, 2 Consider the function f R R+ given by f(u) a + BVū.
2
Then, I has the unique fixed point: u" = @
For E N, denoting ( to be the & fold
composition of f with itself, we have for any E I
(w) - u0 S 3(2-21111
1
Now consider for 8,
Ua
sup
|
K 2-a
SISK
K|S||A
K|S
In lemma 11, define f with tx fixed point u² is such that:
+ CV
ylo
and B = CV
log
The
1-y
(1-7)a
7) llog( KISIIA
On t
log ( K(S)AA|
n" SC
V (1 -1-9) 7)3
(25)
7)3
1-7
Clearly, by Equation (24). we have: ua < f(Wa-1) and ||t+il| f(ug-1). By monotonicity of f(+) and the fact that up < + (Lemma l):
Ws-1 S ((o)))(uo)) S (((11
1
1-
Therefore,
A S s(ug-1) S ((+)
-
24

---

Published as a conference paper at ICLR 2022
Applying Lemma 11, conclude:
Ak+illo S Su" - 3(2-x))) u 2
(26)
Note that under the constraints on the parameter 7) and K as stated in the Theorem, must have u" S |.- By our choice of s, we must have: |パー- u²1 20 C². Using this Equation 26
and the fact that g(2 x I + B², we conclude that with probability at-least 1 - 6, we must have:
log
KISIIA!
On + 7t
1) logg KISIIA!
|A C
+
(1-
This proves the first part of the theorem. For the second part, we directly substitute the values provided to verify that we indeed obtain error.
PROOF OF THEOREM 3
We will now show uniform convergence type result under Assumption 5. For (s,a) S x A and E supp(P(-ls, a)). We define the random variables for all k:
N
B
Pa(s'(s,a) =
Σ
(1
- 11) (..a) (s,a) 1(3 = = =, = a)
j=1
1=1
N
ax( == Σ
Σ
(1 n) n) ( (s.a)
P( (1.( = = a.o a).
j=1
Lemma 12. Suppose Assumption 5 holds. Then, with probability at-least 1 - 8, we must have for any fixed a):
(a(()s)) (a( s C. &C (/dloo(44/) + Crddlog(4/0 (4/8)
5f ((.saa)
We refer to Section L.5 for the proof. We now proceed with the proof of Theorem 3. Recall the noiseless iteration w defined in the discussion following the statement of Lemma 4. We define D₁ := w/ $h. Observe that we cannot apply Lemma 9 in the proof of Theorem 2 where we used w w in order bound ||c/|lo. This is because of data re-use which causes w. to depend on the 'variance' term.
However, note that w a deterministic sequence and we can apply Lemma and then use the fact k.0
that k ss w to show a similar concentration inequality. this end, we prove the following lemma:
Lemma 13. In the tabular setting, we have almost surely:
N j+1
N i+1
(0s.00) a). ΣI
II
n T.
(w) - EII
1=
I <>/lw ه|ا
Σ
(Pa(s'ls, - Pa(s'(s.a)
(27)
The proof follows from elementary arguments via. the mean value theorem and triangle inequality. We refer to Section M.7 for the proof. We are now ready to give the proof of Theorem 3.
Proof of Theorem 3. We proceed with a similar setup as proof Theorem 2. Notice that due to data reuse, the noise 6, in outer loop le is given by < (10
Q *+11
T k. - e1 (Q) k.1
25

---

Published as a conference paper at ICLR 2022
We also define the noiseless Q iteration such that Q1:1 Q and @++ =((Q Let A= == Q Q
Now, by Lemma 5, we can write down
N 1+1
(1()))(ssa)) = (1 (1-n) (6.0) Q)++))++))))) + (Ø(s, a),
Σ 1
j=I IEN
N J+1
=(1 -11-1) -
(a (Q (h: ((b))+
a).
Σ
--
j=1|=N
j+1
+(o(s,a) a).
(28)
j-1l-N
We bound each of the terms above separately. By union bound, the following statements all hold simulataneously with probability at-least By Theorem 7, whenever B C Tmix log(
Pmin
must have A7(2) (s,a) Hmin NB. A simple observation using recursion shows that @f (s, a), (s, E
[0, Using Lemmas 12 and 13 we conclude that we must have:
j+1
(o(s,a) a).
Σ II A (1 L -
sup (s.a)ESxAl
j=1==N
ScllAull> Vndlogg ( + pn ydlog( log (
(29)
Now observe that @h:1 is deterministic sequence. Therefore, using Lemma uniformly for every k S K and (s, E S x A:
N j+1
II s SCvnlog( (1ILA1K)(1 (V+)(s) O² log( [S]AA|K
(o(s,o) a),
-
(30)
Where, Varp (V)) = Varp(V)(s, 21
now combine all the above with Equation (28) to show that with probability at least (1 - 8), we must have uniformly for every ie S K and (s, S x A:
((.
1 1-7 exp
N NB
V Vnd (SIAAI) (ITII
+ nd log
[SILAS (1 (V))(())(, + c. 7log |SIAAK
+ +CV 17 log(
(31)
We will now present crude bound on | to reduce the analysis of ReRexDaRe to the analysis of Q-Rex.
(1-g)a [ A 8
Claim 1. Whenever S Ci
with probability at-least - 8, we must have for every
dlog(
l < K uniformly:
M1min NB
exp
A S
C.
7
log
S SAAK
(1-1)²
(I-7}t
Applying this directly to Equation (31), we conclude that with probability at least (1 8). we must have uniformly for every l. & K and a) S A:
26

---

Published as a conference paper at ICLR 2022
C 27 log [S11A|K
(E(((T"))s, 5
(1-7) exp (- B
C
Vd
(1-7)2
(1 + Var (V C log [S1LA|K
+ CV nlog( [SI|A|
(32)
Proof of Claim 1. First note that T is contractive under the sup norm. Therefore,
| = T(a - T T(xl ) + c
[ - -T(atiit)
+ 12xloo
0c
- 7 || + 11ēx
(33)
In Equation (31), note that Varp a) S -ーン Therefore, under the conditions of this Claim, we can take C small enough so that uniformly for every (s, a) and < K with probability at-least (1 8). Equation (31) becomes:
Mltii NB
(| )| <
exp
+ ||Ax
(1-7) 2
+ CV
7 (1-T)²
log
SIAAIK
Combining the display above and the fact that é é with probability at-least 1 - 5, for every h I K uniformly:
(Q) in Equation (33), we conclude that
ZiAbmin NB
| I 2
1 1+7 |
exp
2
C.
7
log( I
(34)
(1-
Unrolling the recursion above and using the fact that ||11 = O, we conclude the statement of the claim.
We also note that the deterministic iterations @ converges exponentially in sup norm to Q" due contractivity of T. That is:
11 - Q' S
(35)
(1 (-7)
We are now ready to connect up with the proof of Theorem 2 with minor modifications. We follow
the same analysis the proof of Theorem 2 but with Varp(Vi) replaced with Var (VV).. Similar the proof of Theorem we can control Vary (V:) with respect Varr(V*) and [1 Q" |lo. along with Equation (35), We also replace on with
C 77 log [SILAIK
Vd C " log( |SS|AAIK)
C (1 (1-7) exp
a
Milain NB
(1 (1-7)) 7)
Therefore, we conclude version of Equation (23):
0 + K 1-y
xk/2
A <
+ 73
+ +C (1
log( K(S||AA)
V (1 (1-7)
(36)
Where A₁ Qf - Using the bounds on the parameters given in the statement of the Theorem, we conclude the result.
27

---

Published as a conference paper at ICLR 2022
K MINIMAX LOWERBOUNDS FOR TABULAR MDPS
Suppose & denotes the class of all tuples (M, r) where M is a tabular MDP and æ is an exploratory policy such that under the policy π, the MDP achieves stationary distribution z with minimum probability at-least Ammn (see section 2.1). The rewards are almost surely in the set [0.1]. We receive the stationary sequence (st, at rt)==1 from MDP M under policy х, which we denote as (st, a4, rr) (M.T) T). Let FF be the class of all estimators f which estimate Q" for the MDP M
with f((s), at, 1)) We write the minimax risk as:
((,,T) == inf sup JEF (M,r)E
(1 ((st, ar, (., -Q"
Theorem 5. There exists constant C such that, for every Hmnin E (0, 1/41/4). y (0, and 2 Mmii(1-77)' we must have:
((0,T) 2 C Pmin
Therefore, we need T 2 (1mmn[1-733 in order to achieve e error for the Q values.
Proof. We will use Le-Cam's two point method to prove the result. Consider a class of MDPs denoted by MDP(q, p) (p. 9 E [0, 1]) with state space S {0. 1}. only one possible action, reward
function R : S + R. R(s) = and discount factor [0, 1). The transition probability for the MDP given by P(Oj0)=
9, P(1 (0) q. P(O[1) = p and P(1 = p.
Under these conditions, the stationary distribution is given by (00) p+g and u(1) - and the value function can be written as
p+g
V(1) 1 1- pp yph(g)
h(g)
V(0) = 1- p) )ph(gg)
where h(()) = [-x(1-)) Since there is only one action in each state, the value function coincides with the Q function.
For showing the lower bound, consider two MDPs with parameters (pr. g) and (p2, g) with < min(p1, p2) and P1.P2 0.5. The stationary trajectories of length T under the two MDPs, denoted
by the random variables 1 for = 1, 2, satisfies
2q(p1 - P2)
+ +T 2q(p1 P22)
KL(X
<
1:7
1:T
(p) + 4) + 4) In 2n
(p2 + 4)p In
using (L(Ber(a)) Ber(b)) <
2(a b)2
whenever b < 1/2.
blu?
Observe that /4 ( = μ (1) = pato and 1i = (1) = 9. Combining this with the KL (1x
q
pit-"
divergence bound above, we conclude that KL(X (2) (1) < if we set Now let = 1-
1.T 1:T)
P2 P1 = -V Tu
P1 for small enough constant e and 2 p(p+a) (notice that the equation gives
Pa < 0.5 when T satisfies the condition above and < 0.25). By Pinsker's inequality, we must
have TV(X 1:7 L.T < 1
(2) x
Elementary calculations show that (10 PP-
a since & < P1 Tr
PL
(1-7)²
[1-7}²
1-y Therefore:
| T(1 - (1
28

---

Published as a conference paper at ICLR 2022
for 2, y E (0, 1). Let P; be the distribution of x x and let the distribution be parameterised by 0(F,) v (1) for
Consider the semi-metric p(z, y) = 1->(1-z)- 11-7(1-)) (((11-))-hh(()))
== 1, Let f be any estimator based on the observations. By (Wainwright, 2019c, Chapter 15),
min max Ep [80 -((P)] C PEJFi
1
(1 - TV(X ( 1: x x
V
T(1 3)
1
C1
(37)
T(1
7) Umin
- for less than error, T has to be at-least
Minin (1--733
q= (min(1->)
1-2ptmin T (1-7) we can ensure that Mmin = 2pmin and Mmin 2 Amin which ensures that MDP(Pi, 1) and MDP(p2, are both elements of O Therefore, the two point risk in the LHS of Equation (37) lower bounds [(),T), which allows us to conclude the result by substituting (1)
Mmin Mmin
L PROOFS OF CONCENTRATION INEQUALITIES
L.1 PROOF OF LEMMA
First, we leverage the techniques established in (Jain al., 2021b, Lemma 28) to show Lemma 14. The proof follows by a simple re-writing of the proof of the aforementioned lemma which uses linear approximation (in 17) to H. We omit the proof for the sake of clarity.
Lemma 14. Suppose nB $. Then, the following PSD inequalities hold almost surely:
B
B
I I-2n (1 1 B
BB
ki
CkJ 9i
3
H 1,
H I I- I-2n (1 11-1-38
BB 1- 2n
k.
0
1=1
1=1
(38)
Proof of Lemmaa 8. We begin by proving the first part. Using Assumption I and the fact that the
decoupled trajectory (3, a) is assumed to be mixed at the start of every buffer, we begin by first noting from Lemma 14 that:
< ( T T 31 nB
1
nB 1. x
(39)
Now, observe that:
N-1
II J=N
1.89 2 = gd II
(1it))) T (1T B
K
II J=N-1
(40)
1=1
Now note that HAN is independent of H for j < N - 1. Therefore, taking conditional expecta-
tion conditioned on H for j < N - 1 in Equation (40) and using Equation (39), we conclude:
E|J II 1 s (1 28 EL
II
J=N
J=N-1
Applying the equation above inductively, we conclude the result.
We now prove Part 2. We apply Markov's inequality to Part 1 along with Lemma 2 show that with probability at least
nNB
II J=
H H & $ |I II
A H < exp
||
I exp(
7NB N ) All9ll6
v8
J=N
29

---

Published as a conference paper at ICLR 2022
L.2 PROOF OF LEMMA
Proof. We intend to apply Freedman's inequality (Freedman, 1975) like in (Li et al., 2021, Theorem 4), but in asynchronous fashion and with Markovian data. Here, reverse experience replay endows our problem with the right filtration structure. Using Equation (9), we can write
N i+1
N
(6(8,0), a).
H
= j=1
ΣΣ x
(41)
1=1L=N
Where x = (1 7) n) NT (2,)) 26 ((8 2 / (8,a)) a)). This allows us to define the sequence of sigma algebras J.
and m S i)) that is, is the sigma algebra of all states and rewards which appeared before and including (3 a.")) inside the buffer j and all the states in buffers I > j. Notice that N: (s, a) is measurable with respect the sigma algebra F. Using the fact that the buffers are independent, conclude that: x k.j 1 0 and
(((
(mm a (I and m E [B]) or
S 2 > (Vrrp(V)ss, [((5 a.²) = (s,,a) (1))22
2)2 (..0)
It is also clear from our assumptions that |X/*X| - almost surely. Consider the almost sure inequality for the sum of conditional variances:
N
B
Wh
x
VVrr
o.. = (s. 17) 2)
(*,aa)-
(1 (1-1)² < ( au
2 [1 + + Var VV
Σ
(42)
11
We now apply (Li et al., 2021, Equation Theorem 4) with R 1 and o²
1-y
(V to conclude the result.
L.3 PROOF OF THEOREM
Proof. For the sake of convenience, in this proof we will take o² 4(1 [//ll3). Suppose X IR
For m N consider:
N m-++1
m++1
j+1
Xm = 11202
II
H k
Σ
i (m)(ww)
x
H
g
l=
j=N
m+1
VEN
Xo = | 1 122
Here we use the convention that I exp(Xm)) forms a super martingale under an appropriate filtration. In this proof only, consider the sigma algebra Fm be the sigma algebra of all the state action reward tuples in buffers N. N....,
n.l = 1 jereeveerj+1 > N. We claim that the sequence 1,8
w + 1 and let Fo be the trivial sigma algebra. Notice that exp(X is Fm measurable.
Lemma 15. Fix N 2 m 2 1. Suppose Y Rdd is a Fm-1 measurable random vector. Then,
exp 1)) p m+1
(AT,.N--tH) Y) + X(V, jA.N m+1 ( 1.B
((o())) (000)))mmmm)))) S exp (11220211113))
30

---

Published as a conference paper at ICLR 2022
In particular, taking Y with respect to the filtration Fm
[ m 11, I, we conclude that exp(Xm) is a super martingale
k.d.
Proof of Lemma 15. In the proof of this lemma, we will drop the superseripts k, m for the sake of convenience and due to conditioning on Fm we will treat Y as a constant. Now we define the natural filtration on the buffer under consideration (Gi) where 9, is the sigma algebra of the all state-action tuples from (#1, 01) (o)...... (+i, 0;) and rewards (rn)ighei.
Note that by the definition of L(w), we write: L(w) = Σi= ( With this in mind, for h E [B] define La(w) Σ (1) Now, L(w) TJē (w) H1, B- 168 + LB-((w)
Now, notice that the random variables (Y, -I-.)),( H- and (Y, Hr [ GB measureable. Furthermore, must have: E (E)(w))(s) 0 and (ē 2(1 + |10ll)) -
Y) are
V2o. Therefore, applying conditional Hoeffding's lemma, we have:
ni n22o2 (Y, H1. (H1.s) Y) XYY GB
E
exp
H1, (H1.)) T Y) A L(X,LB-1(w)) E exp (AyěB(w)((, Hy ( 9B s exp (nNPo2
exp
H1s (i1.))
T Y) + A(Y, LB- exp (APPPOR (
(43)
In the third step we have used the conditional version of Hoeffding's lemma. Now, consider Z == (1,,B-))T TY. Y. Clearly,
(Y, M, (fh.s) 'v) y) (Y, H1, =7 H H B, 7 7 @n(68) T2
= | n T +1 z
< |
Here we have used the fact that 1) < and || < 1. Using the bounds above in Equation (43), we conclude:
o2 (Y, Hi (Hr.s) T Y) + A(Y, X(Y, Lo(W)) 9B
E
exp
12, H1. (H ) r) X(Y,
S cxp
(44)
Using Equation (44) recursively, we conclude the first statement of the lemma. The last part of the lemma follows easily from the definition of Xm-
By Lemma 15, we conclude that exp(Xm) is super martingale with respect to the filtration Fm Therefore, we must have:
Eexp(XN) S exp(Xo) = exp(r|la:1
is also clear that X 2 A x, E (ITEtA - i [ Applying Chernoff bound
with conclude that the concentration inequality in Equation (13). We then directly apply (Vershynin, 2018, Theorem 8. 1.6) to Equation (13) in order to obtain uniform concentration bounds.
31

---

Published as a conference paper at ICLR 2022
L.4 PROOF OF LEMMA 10
Proof of Lemma 10. By definition of Éx. we have: W1 k+1.1
T(w]. + En. Therefore, for any
(s,a) 8 A, we must have:
(ø(s, a), / + = R(s,a) + BB sup (o(s', a'), a'). 2 ()))
d'EA
Using the fact that R(s, a) [0, 1], conclude:
[1 lla S + 7|101 11000111 11 ||
(45)
By independence of outer-loops for the coupled data, we note that w is independent of the data buffer k. Therefore we can apply Theorem 4 (and resp. Lemma 8) conditionally with w = of (and resp. 1i k.1 w²), the bias variance decomposition given in Lemma 5 and the bound on I|w" ll in Lemma to conclude that with probability at-least 6, for every K:
l1 S /
Kn J 8 exp(- nNB ( llo + 1
1-
C(1 + (lo)) Co + v Vlog(
22
(46)
We now choose constants C1 and C2 in the statement of the Lemma such that Equation 46 implies:
1
| llo -
10
l1 +
2
Using the equation above in Equation (45), we conclude:
2
k+
1.1
lb 2
1 7
1 1100
2
Unrolling the recursion above and noting wh.l O, we conclude that with probability at-least 1- 6, we must have ا ll I - for every l < K. The bound in item follows by using item 1, Equation (46) and the fact that w/ is independent of the data in buffer & due to our coupling.
L.5 PROOF OF LEMMA 12
Proof. For the sake of convenience, we will take d (Ssup(((()ss,))) a)) and index supp (p((pPP(ss)) (s, by [d]. Consider Y E 1-1, We consider the class of random variables indexed by elements of {-1,1)d:
A(; EY Pa(o'ls, - P(s'Is,
The proof proceeds in a similar way to the proof of Lemma 9 via the Freedman inequality. To bring out the similarities we define similar notation. Consider the sequence of sigma algebras Fh. for i [B] and j [K] as defined in the proof of Lemma 9. We now define
x (Y) = (1 (1- 2
(s.a) ΣY. (1(5 = s = s
Y
k.j = a) P(s'ls, = =, at =
= =a))
We note that I. x [kk
0 and 1x (Y) 2 almost surely and simple calculation
{.. [(( <1 (1 - (11-1)22) 2N 1( s, a. a)
reveals that: E
It is also clear that: A(Y; a) = Σ Σ X kJ (Y). Apply Freedman's concentration in- cquality, we conclude for any fixed E 1-1, and (s, E S A.
P(IA(Y;8, CV log (2/0))
32

---

Published as a conference paper at ICLR 2022
Applying union bound over all Y -1, 14, conclude:
P sup AY > C Cddlog(4/0) nd 8.
Ye(-1,144
We complete the proof by noting that
sup
A(Y;
E
|Pa(5'(s,a) - Ps(('(ls
YE(-1.1)4
''Esup(((-la,aa)
M TECHNICAL LEMMAS
M.I COUPLING LEMMA
We first introduce some useful notation: Let D&J (resp. DhJ) be the tuple of random variables (s.-) Li RJy y (resp. (5 2k B11)
rr 1=11
Lemma 16. Suppose
Tiixx log( ( in the tabular setting CTmix log( (riis) in the general setting
(47)
Then, define the sequences (st, at, rt) and (5t. 01, common probability space such that:
1. The tuples D and D have the same distribution for every (k.
2. The sequence B for k < N,j S K isi.
3. Equation (4) holds
Proof. The proof of this lemma for the tabular case is a rewriting of the the proofs of Lemmas 1,2,3 in (Bresler al., 2020). For the general state space case, we apply appropriate modifications as pioneered in (Goldstein, 1979).
M.2 PROOF OF LEMMA 2
Proof. The first part follows from the definitions. For the second part, note that: |||||| 2 ||alle follows from Cauchy-Schwan inequality and Assumption 1. For the reverse inequality we use Assumption show that:
| K
| 2 (0(s,))
M.3 PROOF OF LEMMA
Proof. Existence guaranteed by Definition (2) and uniqueness follows from the assumption that span(0) ④)
-dd
M.4 PROOF LEMMA
Proof. Suppose Wo, wo E ad are arbitrary. Let =T(wp) and w T(wo). For any a(s a), we have:
(0(8, a), w.)l B B()aa))) sup (0(8', "olss,aa), wo) - EewP((la)) sup (6(0', a'), uo) (48)
d'EA
d'EA
33

---

Published as a conference paper at ICLR 2022
By Assumption 2, for every fixed s' there exist (s'), m (s') such that (Ø(s', "ass,,'),, wo) = (o(s', mmax(s')), wo)
sup (ó(s', d' (s')), wo) = (ø(s', d (s))), wo) and sup a'EA
d'EA
Therefore for any s' it holds that,
(0(s', (0('',max); max)) wa wo) S sup d'EA
sup (0(s', "a)ss"a'),, wo)) S (o(s', : (aaxx)uu wa wD)
a'EA
= sup a'EA
(p(s' a'), wo) sup d'EA
(0(8', a'), moo) S llwo ãoll
Combining this with Equation (48), we conclude the 7-contractivity of T. By contraction map- ping theorem, T has a unique fixed point we conclude that w* by considering ((s, a) (w" ((s, a)) and showing that it satisfies the bellman optimality condition in Equation (2). For the norm inequality, we note that since R(s, a) E [0, 1] by assumption and wv = T(w"), ). we have: (ō(s, w*)l Lemma
y||w" lo- Therefore, |w=" - The second norm equality follows from
M.5 PROOF LEMMA
Proof.
We write the iteration in the outer-loop lt as:
The i+ n
-
whe n
phg + y sup (m (05ht (65 a'})
d'eA
Using the fact that (w + Ri 7 sup (0(8' (0(0'(0()) aa), afi and recall- ing the notation (5), we write:
Akj w
[--mer n - (it wh + nott xx++,*
Therefore,
k.tt1 w+++ H. (10 wh++l + Ihs
Unfurling further, and using the fact that w. N.N1 lemma.
141,1 we conclude the statement of W1
M.6 PROOF OF LEMMA
Een ((5 IN (s.i(s, a) concentrates around its expectation. Note that EÑ = Bp(s, a) and that (N, a) are i.i.d. for [N]. From the proof of (Paulin, 2015, Theorem 3.4) and the fact that 7ps 2mmin we conclude:
We let (s,
(s, We show that the quantity
N
Eexp(A( (k. Bu(s,
II
E Eexp(X(N*>>(e,. Bu(s,a))
(N [ + 2mmix (1 a a)mmixi 1
exp
(49)
20ATmix
Following the Chernoff bound the proof (Paulin, 2015, Theorem 3.4), we conclude:
1 16T 2T ) (u(ss, a) + 40tTmix
P(IN+*(s, NB)((s,)) 2) < 2exp
(50)
34

---

Published as a conference paper at ICLR 2022
Taking NN d), whenever B 2 Tmix (by assumption), must have:
1 N (*) - N S 2xp
(-ck BB(ss.a
Timi
for some constant C. Further, via a union bound over all state action pairs (s, a), we conclude the statement of the lemma.
M.7 PROOF OF LEMMA 13
We first prove a simple consequence of multivariate calculus. Lemma 17. Let f: I=" + R be defined by f(x) sup; zy. Then, for every E I", there exists
Ç E IRd such that ||[|| 1, G and:
((x) [w)) (S, - y)
Proof. We consider the log-sum-exp function.
Given L E Rt. define f2(x) =
log (E= exp(Lx;)). An elementary calculation shows that:
log(n)
sup x; 2 fx(2) sup
L
Therefore, for any fixed x,
lim f((x) f(x). L
Now, ffz(z) (PI....,,P)) where p;
Σn-1 Lx,) Clearly, (Vfz(z),ei) > and
expl Lorg)
[V = 1. By the mean value theorem there exists 3g such that:
(((x)-f(0) (V)) y).
(51)
Now, the simplex in R" (denoted by A,) is compact. Therefore, there exists a sub-sequence LE + oo such that lim VLL. (BLx) = < A,. Taking limit along the sub-sequence L in Equation (51), we conclude the result.
Proof of Lemma 13. In the tabular setting, we have the following expression using Equation (41):
1) 8 (15/ ( = (s. (o.aa] [ (10) & [x)]
L.H.S my
(52)
j=1
Where
(w)
sup (w, ( a')) -E -B atd sup (0(s', a'), w))
La'EA
d'eA
Now, by an application of Lemma 17, we show that for some 77(1/6 w, v) E A(A), depending only on (8', w. v), we have:
sup (w, d'eA
w) sup (w, 6(5', a'),
E w(, a',, v)
a'EA
a'EA
Now, using the definition of Pa a) and P(-|s, a) in the discussion preceding Lemma 12, we can simplify Equation (52) to:
L.H.S.
Σ
(Pa(s')s,a) - Pa(s'(s,a)) ((a'ls', ())() vs
(53)
d'Esupp( (()).))) a'EAA
We conclude the statement of the lemma by application of the Holder inequality.
35

---

Published as a conference paper at ICLR 2022
M.8 PROOF OF LEMMA 11
Proof. We solve for f(u") = u² to obtain the relation: u² = a + 3vu" which after discarding the
2
negative solution for vu" yields the unique solution: "² B+ +1
To prove the second
part, consider for arbitrary y, E Rt the following hyper-contraattiityy
lf(x) - f(v) = 3 Vz v
s v x yl
(54)
The second step follows from the fact that Ivā vbl S via -b. bl. Since u² f(u"), we apply the inequality above:
(w1 1001=1(0((1) - (10('))
S / (() (u-))
(55)
We then conclude the result by induction.
36


Reviews:
[{"review_id": "iXnjBCjuP5y", "reviewer": "Reviewer_UL8L", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\n1. The paper provides solid novel analysis combining the recently proposed reverse experience replay. \n2. I could not find no typos and the writing was good.\n\nWeaknesses:\n3. Much of the paper is in the appendix (all proofs, the experiments). On the other hand, the paper holds 2 options inside the algorithm (that doesn't seem to be part of the core message but more of a technical point) and 3 algorithms where only one is given and considered in the theory. This makes things unnecessarily complex in the paper itself, while actually missing some of the more interesting complexities of the proofs, or the empirical results.\n\n4. I'm missing some understanding regarding the reverse experience replay. Usually experience replay buffers are used to reduce correlations in the updates of the Q, but when samples are taken serially backwards - won't the correlations be very strong? The observation regarding super-martingale might important here - perhaps it would be better to state it in the paper itself in a more clear way (since this does seem like part of the core of the paper). \n\n5. As a follow-up - I understand the gaps are there to make the buffers independent (also could be made clearer in the paper). But why do we need the buffers to be independent? Is this just as a technicality to make the analysis easier?", "summary_of_the_paper": "The paper provides sample complexity bounds for a Q-learning based algorithm with target Q and experience replay.\nContributions: The authors provide an algorithm with proven sample complexity for linear MDPs and the tabular setting bridging the current state of the art. The analysis relies on common heuristics of experience replay buffer and using a target network given these some theoretical grounding.", "summary_of_the_review": "I think the paper provides interesting theoretical results and analysis. The idea of using a reverse experience replay buffer sounds interesting for practical use, though I'm not entirely sold there as mentioned in the main review. The work is not groundbreaking but is a solid advancement in its niche.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "V6BwM9A7hAW", "reviewer": "Reviewer_EMzv", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "I start by saying that I agree with the motivation of the paper to study practically successful algorithms. However, I am not very convinced with the significance of the results or techniques. \n\n- The paper does not study Q-learning as it is, but uses a fixed-policy to remove correlations between Q-estimate and actions. \n\n- Algorithm 1 seems like a minor variation of variance-reduction technique. I think that the formulation of (reverse) experience-replay or online target Q-learning should be more explicitly described before Algorithm 1. \n\n- Assumption 3 with Assumption 4 is quite strong and crucial for the analysis. With this assumption, I think the analysis should be similar to previous analysis on Q-learning or SARSA (e.g., Zou et al., 2019). \n\n- In Theorem 3, by the sample complexity do you mean $\\Theta(NKB)$? ", "summary_of_the_paper": "This paper studies the convergence of Q-learning with two popular empirical heuristics (a) online target learning and (b) experience replay. The analysis in this paper is established upon the off-policy setting along with fast-mixing and minimum reachability assumptions. Main convergence results are provided for the linear MDP where all relevant quantities (transition, reward, and Q functions) can be represented as linear functions. The authors propose two variations of Q-learning, namely, Q-Rex and Q-RexDaRe. Convergence results are also given for two algorithms with the sample-optimality guarantee for Q-RexDaRe. ", "summary_of_the_review": "Overall, I agree that it is important to study practically successful and well-used algorithms (even if they do not have any particular benefits from a theoretical standpoint). However, considering the theoretical nature of the paper, I think the contribution of this paper is marginal given a long line of work in the convergence analysis of practical RL algorithms. I lean toward rejections.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "SWwZFAfM1cL", "reviewer": "Reviewer_Da1Z", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: This paper studies the sample complexity of asynchronous learning. Especially, the new algorithm Q-REX achieves the sample complexity $\\frac{|\\mathcal{S}||\\mathcal{A}|}{\\epsilon^{2}(1-\\gamma)^{4}}$ and Q-REXDARE achieves complexity $\\frac{\\max \\left(\\bar{d}, \\frac{1}{\\epsilon^{2}}\\right)}{\\mu_{\\min }(1-\\gamma)^{3}}$.\n\nWeaknesses:\n\n1. Although Q-learning is known to be sub-optimal, the variant of Q-learning are optimal in a couple of setting. For instance, [1] in online setting and [2] in finite horizon offline setting. Since Q-REXDARE is also a variant of q-learning, I think the improvement is a little bit limited comparing to [2] (which uses variance-reduction for Q-learning with $d_m\\approx \\mu_\\min$). I do notice the there is a theorem 1 which holds for linear MDPs, but I cannot see whether this is optimal. (By the way, the paper did not include the related literature [1],[2])\n\n[1] Zhang et al., Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decomposition, NeurIPS 2020,\n[2] Yin et al. Near-optimal offline reinforcement learning via double variance reduction, NeurIPS 2021.\n\n2. Another major weakness is the current algorithm can only guarantee Q-function learning, which cannot guarantee $\\epsilon$-optimal policy with the same complexity since it is known $\\epsilon$-optimal Q-function learning can only imply $(1-\\gamma)^{-1}\\epsilon$-optimal policy. Therefore, the current result cannot guarantee $\\epsilon$-optimal policy with near-optimal sample complexity.\n\n\n", "summary_of_the_paper": "This paper connects Q-learning with online target learning and reverse experience replay and also obtain the result for linear MDPs. Those results are the first of its kind and are shown to be near-optimal in their respective regime. In particular, for asynchronous setting the Q-REX has order $\\frac{|\\mathcal{S}||\\mathcal{A}|}{\\epsilon^{2}(1-\\gamma)^{4}}$ and Q-REXDARE has order $\\frac{\\max \\left(\\bar{d}, \\frac{1}{\\epsilon^{2}}\\right)}{\\mu_{\\min }(1-\\gamma)^{3}}$. The latter one nearly matches the standard lower bound.", "summary_of_the_review": "Overall, due to the weaknesses I mentioned above, I think this paper does not cross the bar due to the high selective of ICLR. Since the theorems are correct from my point of view, I will choose weak reject.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "-dbj7AOrk5", "reviewer": "Reviewer_JvSF", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "In this paper, the authors study the sample efficiency of the Q-learning algorithm, which is a popular approach with broad applications in RL. Based on the standard Q-learning approach, they propose several algorithms called Q-Rex and Q-RexDaRe. With the mixing-time assumption and access to an exploration policy with good coverage, they prove that their algorithms can converge to the optimal policy with near-optimal sample complexity bounds. Their results highlight the benefits of online target learning and experience replay. \n\nAssumption 3 ensures that the Markov chain induced by the policy $\\pi$ can quickly converge to a stationary distribution after $O(\\tau_{mix})$ steps, and Assumption 4 indicates that the stationary distribution has a good coverage in the feature space. These assumptions simplify the problem since the agent can collect i.i.d. samples from a stationary distribution with good coverage by executing the policy $\\pi$. I wonder whether there are concrete examples in which these assumptions hold, or whether these assumptions can be further weaken with other techniques. Besides, I remember that the lower bound proposed in Azar et al. (2013) is proved in the generative-model setting without such assumptions. In other words,  the lower bound in Azar et al. (2013) may not hold with further assumptions in this work, which means that the sample complexity of Q-RexDaRe may not be minimax optimal as claimed by the authors.\n\nThe sample complexity (regret) of Q-learning algorithm in the tabular setting has also been studied by Jin et al. [1]. They obtained the near-optimal sample complexity $O(H^4SA/\\epsilon^2)$ in the online-exploration setting without access to the exploration policy $\\pi$ or any generative model. More comparison between the tabular results in this work and that in [1] is necessary in the related work section.\n\nminor comments:\n1. The parameter $\\kappa$ may implicitly depends on the feature dimension in the linear setting. Therefore, the sample complexity bounds in the theorems still have implicit dependence on the dimension $d$.\n2. Several techniques in this work have also been used in the algorithmic design and complexity analysis of previous related results. For example, the design of gaps with length $u$ between buffers has been applied in [2] to obtain near-optimal regret in the infinite-horizon average-reward setting, and the benefits of experience replay has also been observed in [3] for policy optimization methods. It would be better if these relevant references are added in the paper.\n\n[1] Is Q-learning Provably Efficient?\n\n[2] Model-free Reinforcement Learning in Infinite-horizon Average-reward Markov Decision Processes\n\n[3] Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximation", "summary_of_the_paper": "This paper studies the sample efficiency of the Q-learning algorithm in both tabular and linear setting. They propose efficient algorithms which can provably converge to the optimal policy with near-optimal sample complexity bounds.", "summary_of_the_review": "Overall, the paper is clear with solid theoretical bounds. Their results show that the Q-learning algorithm with online target learning and experience replay can provably converge to the optimal policy with near-optimal sample complexity. One concern is that the assumptions may simplify the analysis of the problem. Besides, more discussion on the related works needs to be added.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper analyzes a variant of the Q-Learning algorithm with two modifications: Online Target Learning (OTL), and Reverse Experience Replay (REP). OTL is essentially the same as using the target network. REP is a new modification of ER, which instead of randomly selecting samples from the buffer, replays them in the reverse order.

Most reviewers are positive about this paper, so I am going to recommend acceptance. There are, however, several concerns that have been raised by the reviewers. As the authors have not revised the paper during the discussion period, my acceptance recommendation is under the good faith expectation that the authors make a serious effort in improving their work based on the reviews. Some of the concerns are:

- The intuition of why REP breaks the correlation is not clear enough. This has been brought up several times by the reviewers.
- What are the technical differences in the analysis compared to previous work such as Zou et al., 2019?
- The kappa appearing in Assumption 4, and showing up in the error bounds, can be dimension dependent. Please clarify this and its effect on the results.
- Much of the paper is in the appendix. It helps if the authors can include more about the proof technique in the main body of the paper.
- Describe the relation between the error in the value function vs. the performance of its greedy policy.
Decision: Accept (Poster)