Year: 2021

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 for Linear MDPs under 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.

text: 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 for Linear MDPs under 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.

heading: 1 INTRODUCTION
text: Reinforcement Learning (RL) has been shown to be highly successful for a variety of practical problems in the realm of long term decision making (Mnih et al., 2015). Several classical works have studied RL methods like TD-learning, Q-learning, SARSA and their variants for many decades (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 are relevant to practitioners who struggle with constraints on the number of data points and the computation power. Recent works provide non-asymptotic results for a variety of important settings (Kearns & Singh, 1999; Even-Dar et al., 2003; Beck & Srikant, 2012; Qu & Wierman, 2020; Ghavamzadeh et al., 2011; Bhandari et al., 2018; Chen et al., 2020; 2019; Dalal et al., 2018a;b; Doan et al., 2020; Gupta et al., 2019; Srikant & Ying, 2019; Weng et al., 2020; Xu & Gu, 2020; Yang & Wang, 2019; Zou et al., 2019).
Despite a large body of work, several aspects of fundamental methods like Q-learning (Watkins & Dayan, 1992) are still ill-understood. Q-learning’s simplicity and the ability to learn from off-policy data makes it attractive to the practitioner. 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 RL with synchronous updates, Q-learning is known to have suboptimal sample complexity (Wainwright, 2019a; Li et al., 2021).
Despite the negative results, Q-learning has been deployed with tremendous success in practice. The practitioners, however, use Q-learning with “heuristic” modifications like experience replay (ER) and online target learning (OTL). ER is used to alleviate the issue that the samples obtained in an episode might be highly dependent on each other whereas OTL helps stabilize the Q iteration. Mnih et al. (2015) conducted extensive experiments to show that both these techniques, along with neural function approximation, are essential for the success of 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 investigating how Q-learning performs with these practical heuristics. To this end, we introduce two model free algorithms: Q-Rex and its sample efficient variant Q-RexDaRe that combine the standard Q-learning with OTL and reverse experience replay (RER). RER is a form of ER which was recently introduced to unravel spurious correlations present while learning form Markovian data in the context of system identification (Rotinov, 2019; Jain et al., 2021b). We show that OTL stabilizes the Q value by essentially serving as a variance reduction technique and RER unravels the spurious correlations present in the off-policy Markovian data to remove inherent biases introduced in vanilla Q learning.
Inclusion of these simple heuristics has surprisingly far-reaching consequences. Firstly, this allows us to show that unlike vanilla Q-learning, Q-Rex finds the optimal policy for linear MDPs 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. Furthermore, we extend Q-Rex to obtain a new method Q-RexDaRethat reuses old samples and admits nearly optimal sample complexity for recovering the optimal Q-function in 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-learning 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 linear 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 1 for an comparison of our guarantees against the state-of-the-results for linear MDPs and 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. Most of the formal proofs are relegated to the appendix.

heading: 1.1 RELATED WORKS
text: Tabular Q-learning Tabular MDPs are the most basic examples of MDPs where the state space (S) and the action space (A) 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 regime for popular model-free and model-based algorithms. Azar et al. (2013) shows that the minimax lower bounds on the sample complexity of obtaining the optimal Q-function up-to error is |S||A|(1−γ)3 2 , where γ 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 standard step sizes, even in the synchronous data setting – where transitions corresponding to each state action pair are sampled independently at each step – suffers from a sample complexity of |S||A|(1−γ)4 2 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 |S||A|(1−γ)5 2 . These results seem unsatisfactory since γ ∼ 0.99 (or even 0.999) in 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 Table 1). For details on model based algorithms, and previous works with suboptimal guarantees we refer to (Agarwal et al., 2020; Li et al., 2020b).
Q-learning with Linear Function Approximation Even though tabular Q-learning is fairly well understood, it is intractable in most practical RL problems due to large size of the state space S. Therefore, Q-learning is deployed with function approximation. Linear function approximation is the simplest such case where the Q-function is approximated with a 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 as was first noticed in (Baird, 1995), which also introduced residual gradient methods which converged rather slowly but provably. We will only discuss recent works closest to our work and refer the reader to (Carvalho et al., 2020; Jin et al., 2020; Yang & Wang, 2019) for a full survey of various works in this direction.
Yang & Wang (2019) consider MDPs with approximate linear function representation - which is more general than the assumptions in this work but require additional assumptions like finite stateaction 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 (see Theorem 1). Similarly, Chen et al. (2019) consider Q-learning with linear function approximation for finite state-action spaces, which need not be exact. But the result requires a rather restrictive assumption that the offline policy is close to optimal policy. In contrast, we consider the less general but well-studied case of linear MDPs 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 converges to a 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 ER1 . This algorithm experimentally resolves the popular counter-examples provided by (Tsitsiklis & Van Roy, 1996; Baird, 1995). Carvalho et al. (2020, Theorem 2) provides value function guarantees for the point to which the algorithm converges (albeit without sample complexity guarantees). However, the assumptions for this result are very stringent and even in the case of tabular Q-learning, the method might not converge to the optimal policy.
Experience Replay and Reverse Experience Replay Reinforcement learning involves learning on-the-go with Markovian data, which are highly correlated. Iterative learning algorithms like Qlearning 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 a fixed size stores the streaming data and the learning algorithm samples a data point uniformly at random from this buffer at each step. This makes the samples look roughly i.i.d. due
1The version of ER used in Carvalho et al. (2020) makes the setting completely synchronous as opposed to the asynchronous setting considered by us.
to mixing, thus breaking the harmful correlations. Reverse experience replay (RER) is a form of experience replay which stores a buffer just like ER 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., 2021b;a). In the context of this work, we note that reverse order traversal endows a supermartingale structure which yields the strong concentration result in Theorem 4, which is not possible with forward order traversal. Yet another way to look at RER is through the lens of Dynamic programming (Bertsekas, 2011) – where the value function is evaluated backwards starting from time T to time 1. Similarly, RER bootstraps Q values to the future Q values instead of the past Q values.
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 is 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).

heading: 2 PROBLEM SETTING
text: Markov Decision Process We consider non-episodic, i.e. infinite horizon, time homogenous Markov Decision Processes (MDPs) and we denote an MDP by MDP(S,A, γ, P,R) where S denotes the state space,A denotes the action space, γ ∈ [0, 1) represents the discount factor, P (s′|s, a) represents the probability of transition to state s′ from the state s on action a. We assume for purely technical reasons that S and A are compact subsets of Rn (for some n ∈ N). R : S × A → [0, 1] is the deterministic reward associated with every state-action pair.
One way to view an MDP is to think of it as an agent that is aware of its current state and it can choose the action to be taken. Suppose the agent takes action π(s), where π : S → A, at state s ∈ S, then P along with the ‘policy’ π induces a Markov chain over S, whose transition kernel is denoted by Pπ . We write the γ-discounted value function of the MDP starting at state s to be:
V (s, π) = E[ ∞∑ t=0 γtR(St, At)|S0 = s,At = π(St)∀t]. (1)
It is well-known that under mild assumptions, there exists at least one optimal policy π∗ such that the value function V (s, π) is maximized for every sand that there is an optimal Q-function, Q∗ : S × A → R, such that one can find the optimal policy as π∗(s) = arg maxa∈AQ∗(s, a), optimal value function as V ∗(s) = maxa∈AQ∗(s, a) and it satisfies the following fixed point equation.
Q∗(s, a) = R(s, a) + γEs′∼P (·|s,a)[max a′∈A Q∗(s′, a′)] ∀(s, a) ∈ S ×A. (2)
(2) can be alternately viewed as Q∗ being the fixed point of the Bellman operator T , where T (Q)(s, a) = R(s, a) + γEs′∼P (·|s,a)[max
a′ Q(s′, a′)].
The basic task at hand is to estimate Q∗(s, a) from a single trajectory (st, at)Tt=1 such that st+1 ∼ P (·|st, at) along with rewards (rt)Tt=1, where r1, . . . , rT are random variables such that E [rt|st = s, at = a] = R(s, a). We refer to Section B for a more rigorous definition of random rewards.
Q-learning Since the transition kernel P (and hence the Bellman operator T ) is often unknown in practice, Equation (2) cannot be directly used to 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.e., it is not possible to choose the agent’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 π(s) for choosing its action at state s.
Given a trajectory {st, at, rt}Tt=1 generated using some unknown behaviour policy π, we aim to estimate Q∗ in a model-free manner - i.e, estimate Q∗ without directly estimating P . This is often more practical in settings where only a limited memory is available and the transition probabilities
can not be stored. We further assume that the trajectory is 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 Qlearning algorithm. In this online algorithm, we maintain an estimate of Q∗(s, a) at time t, Qt(s, a) and the estimate is updated at time t for (s, a) = (st, at) in the trajectory. Formally, with step-sizes given as {ηt}, Q-learning performs the following update at time t,
Qt+1(st, at) = (1− ηt)Qt(st, at) + ηt [ rt + γ max
a′∈A Qt(st+1, a
′) ] Qt+1(s, a) = Qt(s, a) ∀ (s, a) 6= (st, at).
(3)
Linear Markov Decision Process In this work, we focus on a special class of MDPs called linear MDPs. In a d-dimensional linear MDP, the transition probabilities and the reward functions can be expressed as a linear combination of a d-dimensional feature map φ(s, a). The transition probability is the inner product of d unknown measures and the feature map while the reward function is the inner product of an unknown vector and the feature map. We use the following formalization of this idea as used in Jin et al. (2020), stated as Definition 1.
Definition 1. An MDP(S,A, γ,P, R) is a linear MDP with feature map φ : S ×A → Rd, if
1. there exists a vector θ ∈ Rd such that R(s, a) = 〈φ(s, a), θ〉, and
2. there exists d unknown (signed) measures over S β(·) = {β1(·), . . . , βd(·)} such that the transition probability P (·|s, a) = 〈φ(s, a), β(·)〉.
In the tabular setting we assume that the dimension d = |S × A| and we use a one hot embedding where we map (s, a) → φ(s, a) = es,a, a unique standard basis vector. It is easy to show that this system is a linear MDP (Jin et al., 2020) and Q-learning 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. We refer to (Jin et al., 2020) for further discussion on linear MDPs. We however note that as a simple consequence of (Jin et al., 2020, Proposition 2.3), there exists a vector w∗ ∈ Rd such that the optimal Q-function, Q∗(s, a) = 〈φ(s, a), w∗〉 for every (s, a) ∈ S ×A, which can be explicity expressed as a function of θ, β and Q∗. 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 as follows:
wt+1 = wt + ηt [ rt + γ max
a′∈A 〈φ(st+1, a′), wt〉 − 〈φ(st, at), wt〉
] φ(st, at).
The above update can be seen as a gradient descent step on the loss function f(wt) = (〈φ(st, at),wt〉−target)2 where target = rt+γmaxa′〈φ(st+1, a′),wt〉. This update while heavily used in practice, has been known to be unstable and does not converge to w∗ in general. The reason often cited for this phenomenon is the presence of the ‘deadly triad’ of bootstrapping, function approximation, and off-policy learning.

heading: 2.1 ASSUMPTIONS
text: We make the following assumptions on the MDPs considered through the paper in order to present our theoretical results.
Assumption 1. The MDP is linear (Definition 1), ‖φ(s, a)‖2 ≤ 1 and 〈φ(s, a), θ〉 ∈ [0, 1]. Assumption 2. Let Φ := {φ(s, a) : (s, a) ∈ S × A}. Φ is compact, span(Φ) = Rd and (s, a) → φ(s, a) is measurable.
Even when span(Φ) 6= Rd, our results hold after we discard the space orthogonal to the span of embedding vectors in Assumption 4 and note that Q-Rex does not update the iterates along span(Φ)⊥.
Definition 2. For r > 0, letN (Φ, ‖ · ‖2, r) be the r-covering number under the standard Euclidean norm over Rd. Define:
CΦ := ∫ ∞ 0 √ logN (Φ, ‖‖2, r)dr
Algorithm 1 Q-Rex 1: Input: learning rates η, horizon T , discount factor γ, trajectory Xt = {st, at, rt}, Buffer size B, Buffer gap u, Number of inner loop buffers N
2: Total buffer size: S ← B + u, Outer-loop length: K ← TNS , Initialization w 1,1 1 = 0 3: for k = 1, . . . ,K do 4: for j = 1, . . . , N do 5: Form buffer Buf = {Xk,j1 , . . . , X k,j S }, where, X k,j i ← XNS(k−1)+S(j−1)+i 6: Define for all i ∈ [1, S], φk,ji , φ(s k,j i , a k,j i ). 7: for i = 1, . . . , B do
8: wk,ji+1 = w k,j i +η [ rk,jB+1−i + γ max
a′∈A 〈φ(sk,jB+2−i, a′), w k,1 1 〉 − 〈φ k,j B+1−i, w
k,j i 〉 ] φk,jB+1−i
9: Option I: wk,j+11 = w k,j B+1
10: Option II: wk,j+11 = 1 B ∑B i=1 w k,j i+1 11: Option I: wk+1,11 = w k,N+1 1 12: Option II: wk+1,11 = 1 N ∑N+1 l=2 w k,l 1 13: Return wK+1,11
Observe that since Φ is a subset of the unit Euclidean ball in Rd, CΦ ≤ C √ d. However, in the case
of tabular MDPs it is easy to show that CΦ ≤ C √
log d. Definition 3. We define the norm ‖ · ‖φ over Rd by ‖x‖φ = sup(s,a) |〈φ(s, a), x〉|.
Lemmas 2 and 4 show that this is the natural norm of interest for the problem. We assume the existence of a fixed (random) behaviour policy π : S → ∆(A) which selects a random action corresponding to each state. At each step, given (st, at) = (s, a), st+1 ∼ P (·|s, a) and at+1 ∼ π(st+1). This gives us a Markov kernel over S × A which specifies the law of (st+1, at+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. Assumption 3. There exists a unique stationary distribution µ for the kernel Pπ . Moreover, this Markov chain is exponentially ergodic in the total variation distance with total variation distance τmix. In the general case, we will take this to mean that there exists a constant Cmix for every t ∈ N
sup x∈S×A
TV((Pπ)t(x, ·), µ) ≤ Cmix exp(−t/τmix)
In the tabular setting, we will use the standard definition of τmix instead:
τmix = inf{t : sup x∈S×A TV((Pπ)t(x, ·), µ) ≤ 1/4} .
Here TV refers to the total variation distance. Assumption 4. There exists κ > 0 such that: E(s,a)∼µφ(s, a)φ>(s, a) Iκ .
In the tabular setting, Assumption 4 manifests itself as 1κ = µmin := min(s,a) µ(s, a) which is also standard (Li et al., 2020b). Whenever we discuss high probability bounds (i.e, probability at least 1− δ), we assume that δ ∈ (0, 1/2). Similarly, we will assume that the discount factor γ ∈ (1/2, 1) so that we can absorb poly(1/γ) factors into constants.

heading: 3 OUR ALGORITHM
text: 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 sample efficient variant Q-RexDaRe (Q-Rex + data reuse, Algorithm 2) and its episodic variant EpiQRex (Episodic Q-Rex, Algorithm 3). Since Q-RexDaRe 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 the following quantities, K the number of iterations in the outer-loop, N the number of buffers within an outer-loop iteration, B the size of a buffer and u the gap between
the buffers. The algorithm has a three-loop structure where at the start of every outer-loop iteration (indexed by k ∈ [K]), we checkpoint our current guess of theQ function given by wk,11 . Each outerloop iteration corresponds to an inner-loop over the buffer collection with N buffers, i.e. at iteration j ∈ [N ], we collect a buffer of sizeB+u consecutive state-action-reward tuples. For every collected buffer we consider the first B collected experiences and perform the target based Q-learning update in the reverse order for these experiences. We refer Figure 1 for an illustration of the processing order. Of note, is the usage of checkpointed target network in the RHS of the Q-learning update through the entirety of the outer-loop iteration, i.e. for a fixed k and for all j, i, our algorithm sets
wk,ji+1 = w k,j i + η [ rk,jB+1−i + γ max
a′∈A 〈φ(sk,jB+2−i, a ′),wk,11 〉 − 〈φ k,j B+1−i, w
k,j i 〉 ] φk,jB+1−i
Figure 1 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 T = KN(B + u). For the sake of simplicity, we will assume that the initial point, w1,11 = 0. Essentially the same results hold for arbitrary initial conditions. Q-RexDaRe is a modification of Q-Rex where we re-use the data from the first outer-loop iteration (i.e, data from k = 1) in every outer-loop iteration (i.e, k > 1) instead of drawing fresh samples. In the case of EpiQ-Rex we take the gap u = 0 and each buffer to be a single episode instead of the fixed length buffers.
Remark 1. For the sake of clarity, we only analyze the algorithms Q-Rex and Q-RexDaRe for data from a single trajectory with Option I. A similar analysis holds with respect to episodic data with EpiQ-Rex. Similarly Option II involves averaging of the iterates which boosts the performance of SGD for convex problems and indeed we can obtain much better bounds in this setting by using standard analysis.

heading: 4 MAIN RESULTS
text: 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 an outer-loop iteration, B is the buffer size and u is the size of the gap. In what follows, we will take u = Õ(τmix), B = 10u, K = Õ( 11−γ ). We also note that the total number of samples used is NK(B + u) for Q-Rex and N(B + u) for Q-RexDaRe since we reuse data in each outer-loop iteration. In what follows, by QK+1,11 (s, a), we denote 〈φ(s, a), w K+1,1 1 〉 which is our estimate for the optimal Q function. Here wK+1,11 is the output of either Q-Rex or Q-RexDaRe at the end of K outer-loop iterations. Define ‖QK+1,11 −Q‖∞ := sup(s,a)∈S×A
∣∣QK+1,11 (s, a)−Q∗(s, a)∣∣. We first consider the performance of Q-Rex with data derived from a linear MDP (Defintion 1) and satisfying the Assumptions in Section 2.1.
Theorem 1 (Linear MDP). Suppose we run Q-Rex using Option I with data from a linear MDP. There exists constants C1, C2, C3, C4, C5 > 0 such that whenever the parameter bounds given in Table 2 (row 1) are satisfied, then with probability at-least 1− δ, we must have:
‖QK+1,11 −Q∗‖∞ ≤ γK 1−γ + C4
√ Kκ δ(1−γ)4 exp ( −ηNBκ ) + C5
√ η [ C2Φ+log ( K δ
)] (1−γ)4
Setting K N u B η LINEAR MDP (THEOREM 1) ≥ 1 > C3 B κ η log
( Kκ
δ(1−γ) ) ≥ C1τmix log(CmixKNδ ) = 10u < C2 min( (1−γ)2 C2Φ+log(K/δ)) , 1B )
TABULAR MDP (THEOREM 2) ≥ C2
( log (
1 1−γ ))2 1−γ > C4 B τmix µmin log( |S||A|Kδ ) ≥ C1τmix log( KN δ ) = 10u <
C3 log ( |S||A|K
δ ) TABULAR MDP (THEOREM 3) ≥ C2 log ( 1 1−γ ) 1−γ > C4 B τmix µmin log( |S||A|δ ) ≥ C1τmix log( KN δ ) = 10u < C3 (1−γ)2 d̄ log ( |S||A|
δ ) LINEAR MDP (THEOREM 1) β1 (1−γ) κβ2 max ( C2Φ+β2 2(1−γ)4τmix , 1 ) τmix log ( KN δ ) 10u min ( (1−γ)4 2 C2Φ+β3 , 1B )
TABULAR MDP (THEOREM 2)
β21 1−γ
1 µmin
max ( β5,
β1 ητmix
)) τmix log ( KN δ ) 10u (1−γ) 3 β5 min( , 2)
TABULAR MDP (THEOREM 3)
β1 (1−γ)
1 µmin
max ( β5,
β1 ητmix
)) τmix log ( KN δ ) 10u min ( 2(1−γ)3 β4 , (1−γ) 2 d̄β5 , (1−γ) 3 √ d̄β4 )
Table 2: Parameter constraints (first 3 rows) and choice for< error (last 3 rows) for our algorithms. Here the poly-log factors βi are given by β1 = log ( 1
(1−γ) min( ,1) ) , β3 = log ( 1 (1−γ)δmin( ,1) ) ,
β2 = log(κ) + β3, β4 = log
( |S||A|K
δ
)
, β5 = log
( |S||A|
δ
)
.
Given ∈ (0, 1(1−γ) ], and the parameters as given in Table 2 (row 4)(up to constant factors), then with probability at-least 1− δ: ‖QK+1,11 (s, a)−Q∗(s, a)‖∞ < . This has a sample complexity
Θ(NKB) = Õ ( κmax ( C2Φ+1
(1−γ)5 2 , τmix 1−γ )) We now 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.
Remarks: To the best of our knowledge, Theorem 1 presents the first non-asymptotic convergence results for Q-learning based methods for Linear MDPs under standard assumptions. Note that the sample complexity is independent of d, so this result applies to kernel approximation as well. We note that RER is important for this result, and this is reflected in our experiments. The lower order dependency on τmix in the sample complexity is also independent of d, but this ‘burn in’ type dependence might be sub-optimal. 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 2 (row 2) for some universal constants C1, . . . , C5, we obtain with probability at-least 1− δ:
‖QK+1 −Q∗‖∞ < C5
[ γL 1−γ + exp ( −ηµminNB2 ) (1−γ)2 + η log (K|S||A| δ ) (1−γ)3 + √ η log (K|S||A| δ ) (1−γ)3 ]
Where L = b1K log
1 1−γ
. Given ∈ (0, 11−γ ], and the parameters are picked as given in Table 2 (row
5), then with probability at-least 1 − δ, we have: ‖QK+1 − Q∗‖∞ < . This gives us a sample complexity of
Θ(NKB) = Õ (
1 µmin
max (
1 (1−γ)4 min( , 2) , τmix 1−γ
)) .
The sample complexity provided in Theorem 2 matches the sample complexity of synchronous Qlearning even when dealing with asynchronous data. However it is still sub-optimal with respect to the mini-max lower bounds which has a dependence of 1(1−γ)3 instead of 1 (1−γ)4 . We resolve this gap for Q-RexDaRe in Theorem 3. In the case of tabular MDPs, the number states can be large but the support of P (·|s, a) is bounded in most problems of practical interest. Consider the following assumption: Assumption 5. Tabular MDP is such that |supp(P (·|s, a))| ≤ d̄ ∈ N. This holds for every tabular MDP with d̄ = |S|. Theorem 3 (Tabular MDP with Data Reuse). For tabular MDPs, suppose additionally Assumption 5 holds and we run Q-RexDaRe using Option I. There exist universal constants C1, C2, C3, C4 such that when the parameter values satisfy the bounds in Table 2 (row 3), with probability at-least 1−δ:
‖QK+1,11 −Q∗‖∞ ≤ C
[ exp ( −ηµminNB2 ) +γK
(1−γ)2 + η log
( |S||A|K δ ) (1−γ)3 √ d̄+ √ η (1−γ)3 log (K|S||A| δ )]
Suppose ∈ (0, 11−γ ]. If we choose the parameters as per Table 2 (row 6), then with probability at-least 1− δ we have: ‖QK+1(s, a)−Q∗‖∞ < . The sample complexity in this case is
Θ(NB) = Õ (
1 µmin
max ( τmix, 1 2(1−γ)3 , d̄ (1−γ)2 , √ d̄ (1−γ)3 )) .
Remarks: Theorem 3 obtains near-optimal sample complexity with respect to γ. Here again the ‘burn in’ type dependency on τmix, which might be sub-optimal, is due to the data being sampled from a Markovian trajectory.

heading: 5 OVERVIEW OF THE ANALYSIS
text: We divide the analysis of Q-Rex and Q-RexDaRe into two parts: Analysis of wk,11 obtained at the end of outer-loop iteration k 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 wk+1,11 such that 〈w k+1,1 1 , φ(s, a)〉 ≈ R(s, a) + Es′∼P (·|s,a) supa′〈w k,1 1 , φ(s
′, a′)〉. Therefore, we write wk+1,11 = T (w k,1 1 ) + k(w k,1 1 ), where T is the γ contractive Bellman operator whose unique fixed point is w∗ and k is the noise to be controlled. Following a similar setting in in (Jain et al., 2021b), we control k with the following steps: (1) We introduce a fictitious coupled process (see Section C) (s̃t, ãt, r̃t) where the data in different buffers are exactly independent (since the gaps of size u make the buffers approximately independent) 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 a bias-variance decomposition (Lemma 5) for the error k where the exponentially decaying 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 k is small enough. RER plays a key role in controlling the variance term by endowing it with a supermartingale structure, which is not possible with forward order traversal (see Theorem 4).
The procedure described above allows us to show that wk+1,11 ≈ T (w k,1 1 ) uniformly for k ≤ K, which directly gives us a 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 et al., 2021), which allows us to 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 outerloop iteration 1 in all future outer-loop iterations k > 1, k(w k,1 1 ) might not be small since w k,1 1 depends on k(·). However, (wk,11 )k approximates the deterministic path of the noiseless Bellman iterates: w̄1,11 := w 1,1 1 and w̄ k+1,1 1 := T (w̄ k,1 1 ). Since ‖ k(w k,1 1 )‖∞ ≤ ‖ k(w k,1 1 )− k(w̄ k,1 1 )‖∞ + ‖ k(w̄k,11 )‖∞, we argue inductively that ‖ k(w k,1 1 ) − k(w̄ k,1 1 )‖∞ ≈ 0 since w k,1 1 ≈ w̄ k,1 1 and ‖ k(w̄k,11 )‖∞ ≈ 0 since w̄ k,1 1 is a deterministic sequence and hence w k+1,1 1 ≈ w̄ k+1,1 1 .

heading: 6 DISCUSSION
text: In this work, we gave a finite-sample analysis for heuristics which are heavily used in practical Q-learning and showed that seemingly simple modifications can have far reaching consequences in both tabular and linear MDP settings. We also resolve some well known counter-examples to Q-learning with linear function approximation (Baird, 1995). Further research is needed to extend this setting to approximate linear MDPs where the linear representation is not exact (Yang & Wang, 2019; Munos & Szepesvári, 2008) and the most general setting of (Carvalho et al., 2020; Maei et al., 2010) where linear approximation maybe highly misspecified. Since Q-learning is mostly used in practice with non-linear function approximators like neural networks, it would be interesting to analyze such scenarios (Xu & Gu, 2020; Cai et al., 2019) precisely without simplifying assumptions like in (Fan et al., 2020). Another important direction is to understand on-policy algorithms (like SARSA) with the modifications suggested in this work, where the agent has the additional task of exploring the state-space while learning the optimal policy and obtain a regret analysis like in (Jin et al., 2020).

heading: A EXPERIMENTS
text: 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 a 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 or right on a straight line, receiving a reward of 0 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 random. 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+Q-learning and EpiQ-Rex (Option II, N = 1). The 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 EpiQRex and OTL+ER+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.
Mountain Car We run an online control type experiment with the Mountain car problem (Sutton & Barto, 2018, Example 10.1). 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 a reward of −1 unless the correct peak is reached. Here we run EpiQ-Rex with Option I and N = 1, OTL+ER+Q-learning and vanilla Q-learning. The k-th episode is generated with the policy at the end of k − 1-th episode for each of the three algorithms. We use a n = 4 tile coding to represent the Q values for a given action, each of which has 4 × 4 squares. The step-size was picked as 0.1/n and the result was averaged over 500 runs of the experiment. We refer to Figure 2 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-learning was 143 (rounded to the nearest integer).
Grid-World We consider the grid-world problem which is a 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 × 5 grid. Trying to fall off the grid accrues a reward of −1, while reaching certain special states accrues a reward of 10 or 5. In our example, we also add a unif[−0.5, 0.5] noise to all rewards to make the problem harder. We run the grid world experiment with the discount factor γ = 0.9 and step size 0.05 for Vanilla Q-learning, Q-Rex (Option II, B = 3000, N = 1) and OTL+ER+Qlearning which is 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 counter-example shown in Figure 6. The features corresponding to each state is shown and the reward for any transition is 0. Thus, w∗ = 0 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 is sampled uniformly at random and the corresponding transition, along with the 0 reward is used to learn the vectorw. In the experiment, we set the problem and algorithmic parameters to be γ = 0.99 and η = 0.01/ √ 5 (the factor of √ 5 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-learning while OTL-based Q-learning converges. Note that since the sampling of state, action and reward is done in a 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 are covered; the rate of convergence would be same as that of OTL+Q-learning.
Linear Dynamical System with Linear Rewards We also compare the algorithms on a linear dynamical systems problem. While the problem described next is strictly not a linear MDP, the value functions for certain policies can be written as a linearly in terms of the initial condition; this is made precise next. Consider a linear dynamical system with initial state being X0 ∈ Rd. The state evolves as Xt+1 = AXt + ηt, where A ∈ Rd×d. The reward obtained for such transition is given by 〈Xt, θ〉 for a fixed θ ∈ Rd. The maximum singular value of A is chosen less than 1 to ensure that the system is stable. The infinite horizon γ-discounted expected reward is given by 〈X0, ∑∞ i=0(γA T )iθ〉. Thus, the expected reward can be written as 〈X0, w∗〉, where
w∗ = (I − γAT )−1θ. Since there are no actions in this case, the Q learning algorithms reduce to value function approximation (i.e, TD(0) type algorithms). We take the embedding φ(Xt) = Xt, the identity mapping. We considered d = 5, γ = 0.99, η = 0.01, and a randomly generated normal matrix A and θ. We Option II for Q-Rex along with B = 75, u = 25, and N = 5 for the experiments. For OTL+ER+Qlearning, we keep the same parameters, but with random order sampling, while ER+Q-learning 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.
As seen from Figure 5, Q-Rex outperforms vanilla Q-learning and OTL+ER-based Q-learning as one would expect based on the theory presented in this work. However, it is interesting to note that ER+Q-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 a slower rate at the cost of reducing bias. However, setting a smaller value of NB might resolve the issue.

heading: B DEFINITIONS AND NOTATIONS

heading: B.1 Q-REXDARE
text: 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 2 Q-RexDaRe 1: Input: learning rates η, horizon T , discount factor γ, trajectory Xt = {st, at, rt}, number of
outer-loops K buffer size B, buffer gap u 2: Total buffer size: S ← B + u 3: Number of buffers loops: N ← T/S 4: w1,11 = 0 initialization 5: for k = 1, . . . ,K do 6: for j = 1, . . . , N do 7: Form buffer Buf = {Xk,j1 , . . . , X k,j S }, where,
Xk,ji ← XS(j−1)+i
8: Define for all i ∈ [1, S], φk,ji , φ(s k,j i , a k,j i ).
9: for i = 1, . . . , B do 10: wk,ji+1 = w k,j i +η [ rk,jB+1−i + γmaxa′∈A〈φ(s k,j B+2−i, a ′), wk,11 〉 − 〈φ k,j B+1−i, w k,j i 〉 ] φk,jB+1−i
11: wk,j+11 = w k,j B+1 12: wk+1,11 = w k,N+1 1 13: Return wT+10

heading: B.2 EPIQ-REX
text: The psuedocode for EpiQ-Rex is given in Algorithm 3. Note that the buffers here are individual episodes and can vary in size due to inherent randomness. We do not require a gap here since separate episodes are assumed to be independent.
MDP definition Here we construct the MDP with a (possibly) random reward r. We consider non-episodic, i.e. infinite horizon, time homogenous Markov Decision Processes (MDPs) and we denote an MDP by MDP(S,A, γ, P, r) where S denotes the state space,A denotes the action space, γ represents the discount factor, P (s′|s, a) represents the probability of transition to state s′ from the state s on action a. We assume for purely technical reasons that S and A are compact subsets of Rn for some n ∈ N). r is a reward process (not to be confused with Markov Reward Processes i.e, MRP) indexed by S × A × S , such that r(s, a, s′) ∈ [0, 1] almost surely. We will skip the measure theoretic details of the definitions and assume that the sequence of i.i.d. reward processes (rt)t∈N can be jointly defined over a Polish probability space. The function R : S × A → [0, 1] represents the deterministic reward R(s, a) obtained on taking action a at state s and is defined by R(s, a) = E [ Es′∼P (·|s,a)r(s, a, s′) ] . Here the expectation is with respect to both the randomness in the reward process and in state s′.
Now, given a trajectory, (st, at)Tt=1, which is independent of i.i.d sequence of rewards processes (rt) T t=1. We observe (st, at, rt(st, at, st+1)) T t=1, and we will henceforth denote rt(st, at, st+1) by just rt.
Algorithm 3 EpiQ-Rex 1: Input: learning rates η, number of episodes T , discount factor γ, Epsiodes Et = {(st1, at1, rt1), . . . , (s y Bt , atBt , r t Bt
)}, Number of buffer per outer-loop iteration N. 2: Number of outer loop iterations: K ← T/N 3: w1,11 = 0 initialization 4: for k = 1, . . . ,K do 5: for j = 1, . . . , N do 6: t← (k − 1) ∗N + j 7: Collect experience and form buffer Buf = {Xt1, . . . , XtBt}, where,
Xti = (s t i, a t i, r t i)
8: Define for all i ∈ [1, Bt − 1], φk,ji , φ(s k,j i , a k,j i ).
9: for i = 1, . . . , B do 10: wk,ji+1 = w k,j i +η [ rk,jBt−i + γmaxa′∈A〈φ(s k,j Bt+1−i, a ′), wk,11 〉 − 〈φ k,j Bt−i, w k,j i 〉 ] φk,jBt−i 11: Option I: wk,j+11 = w k,j Bt 12: Option II:wk,j+11 = 1 Bt−1 ∑Bt i=2 w k,j i 13: wk+1,11 = w k,N+1 1 14: Return wK,11
Notation Due to three loop nature of our algorithm it will be convenient to define some simplifying notation. To this end, consider the outer loop with index k ∈ [K] and buffer number j ∈ [N ] inside this outer loop. Further given an i ∈ [S] define a time index as tk,ji = NS(k − 1) + S(j − 1) + i. We now denote the i-th state-action-reward tuple inside this buffer by
(sk,ji , a k,j i , r k,j i ) = (stk,ji , atk,ji , rtk,ji ).
Similarly, Rk,ji = R(s k,j i , a k,j i ). For conciseness, we define for all i, j, k, φ k,j i := φ(s k,j i , a k,j i ). Since we are processing the data in the reverse order within the buffer, the following notation will be useful for analysis:
sk,j−i := s k,j B+1−i, a k,j −i := a k,j B+1−i, r k,j −i := r k,j B+1−i, R k,j −i := R k,j B+1−i and φ k,j −i := φ k,j B+1−i.

heading: C COUPLED PROCESS
text: It can be seen that the buffers are approximately i.i.d. whenever we take u = O(τmix log Tδ ) whenever Assumption 3 is satisfied. For the sake of clarity of analysis, we will consider exactly independent buffers. That is, we assume the algorithms are run with a fictitious trajectory (s̃t, ãt, r̃t), 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 we can couple this fictitious process (i.e, define it on a common probability space as the original process (st, at, rt)) such that
P ( ∩Kk=1 ∩Nj=1 ∩B+1i=1 {(s k,j i , r k,j i , a k,j i ) = (s̃ k,j i , r̃ k,j i , ã k,j i )} ) ≥ 1− δ . (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, at, rt) is the same as the sequence of iterates obtained by running the algorithm with the fictitious coupled data (s̃t, ãt, r̃t) with high probability. We state this result formally in Lemma 16 and prove it in Section L.1. Henceforth, we will assume that we run the algorithm with data (s̃t, ãt, r̃t) and refer to Lemma 16 to carry over the results to the original data set with high probability. We analogously define φ̃k,ji . We will denote the iterates of the algorithm run with the coupled trajectory as w̃k,ji instead of w k,j i and will focus on it entirely. We now provide some definitions based on the above process. These definitions will be used repeatedly in our analysis.

heading: D BASIC STRUCTURAL LEMMAS
text: We first note some basic structural lemmas regarding linear MDPs. We refer to Section L for the proofs.
Lemma 1. For tabular MDPs satisfying the assumptions in Section 2.1, for both Q-Rex and QRexDaRe, we have that for every k, j, i we have that ‖w̃k,ji ‖φ ≤ 11−γ
The lemma above says, in particular, that the Q-value estimate given by our algorithm never exceeds 1 1−γ due to 0 initialization. The proof is a straightforward induction argument, which we omit. We will henceforth use Lemma 1 without explicitly mentioning it.
Lemma 2. Suppose Qw(s, a) := 〈w, φ(s, a)〉 and let Q∗(s, a) = 〈w∗, φ(s, a)〉 be the optimal Q function. Then:
sup (s,a)∈S×A
|Qw(s, a)−Q∗(s, a)| = ‖w − w∗‖φ
Moreover, we must have: ‖x‖ ≥ ‖x‖φ ≥ ‖x‖√κ for any x ∈ R d.
Lemma 3. For any w0 ∈ Rd, there exists a unique w1 ∈ Rd such that
〈w1, φ(s, a)〉 = R(s, a) + γEs′∼P (·|s,a) sup a′∈A 〈φ(s′, a′), w0〉.
We will denote this mapping w0 → w1 by w1 = T (w0). Lemma 4. T : Rd → Rd is γ contractive in the norm ‖ · ‖φ. The unique fixed point of T is w∗. Moreover, we have: ‖w∗‖φ ≤ 11−γ and ‖w ∗‖ ≤ √ κ 1−γ .
In view of Lemma 4, we can begin to look at the following noiselessQ-iteration. Let w̄1 = w1,11 = 0 and w̄k+1 = T (w̄k). 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 of k-th outer loop can be written as w̃k+1,11 = T (w̃ k,1 1 ) + ̃k where ̃k is the error introduced via sampling which needs to be controlled.

heading: E BIAS VARIANCE DECOMPOSITION
text: We begin our analysis by providing a bias-variance decomposition of the error with respect to 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 k and buffer index j, we define the following contraction matrices for a, b ∈ [B].
H̃k,ja,b := b∏ i=a ( I − ηφ̃k,ji [φ̃ k,j i ] > ) . (5)
Whenever a > b, we will define H̃k,ja,b := I . In the tabular setting, we define for any (s, a) ∈ S ×A by Ñk(s, a) to be the number of samples of (s, a) seen in the outer loop k (excluding the gaps),i.e.
Ñk(s, a) = N∑ j=1 B∑ i=1 1((s̃k,ji , ã k,j i ) = (s, a))
Further we denote by Ñk,ji (s, a), the number of samples of (s, a) seen in the outer loop k in the buffers post the buffer j as well as the number of samples of (s, a) in buffer j before iteration i. Formally,
Ñk,ji (s, a) := i−1∑ r=1 1 ( (s̃k,jr , ã k,j r ) = (s, a) ) + N∑ l=j+1 B∑ r=1 1 ( (s̃k,lr , ã k,l r ) = (s, a) ) .
We define the error term for any w:
̃k,ji (w) := [ r̃k,ji − R̃ k,j i + γ sup
a′∈A 〈w, φ(s̃k,ji+1, a ′)〉 − γEs′∼P (·|s̃k,ji ,ãk,ji ) supa′∈A 〈φ(s′, a′), w〉
] . (6)
Finally we define the following shorthands for any i, j, k:
w̃k+1,∗ := T (w̃k,11 ) ̃ k,j i := ̃ k,j i (w̃ k,1 1 ) L̃ k,j := η B∑ i=1 ̃k,ji H̃ k,j 1,i−1φ̃ k,j i .
Given the above definition, the following the lemma provides the Bias-Variance decomposition which is the core of our analysis. Lemma 5 (Bias-Variance Decomposition). For every k, we have that,
̃k := w̃ k+1,1 1 − w̃k+1,∗ = 1∏ j=N H̃k,j1,B(w̃ k,1 1 − w̃k+1,∗) + N∑ j=1 j+1∏ l=N H̃k,l1,BL̃ k,j (7)
Here and later on in the paper, we use the reverse order in the product to highlight the convention that higher indices l in H̃k,l1,B appear towards the left side of the product and further define ∏N+1 l=N H̃ k,l 1,B = I . We call the first term in Equation (7) as 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, we will provide special cases for the tabular setting with refined bounds. We refer to Section L.5 for the proof of Lemma 5.

heading: F BOUNDING THE BIAS TERM

heading: F.1 TABULAR CASE
text: 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:
〈φ(s, a), 1∏
j=N
H̃k,j1,B(w̃ k,1 1 − w̃k+1,∗)〉 = (1− η)Ñ k(s,a)〈w̃k,11 − w̃k+1,∗, φ(s, a)〉
For a particular outer loop k, we show that Ñk(s, a) is Ω(µminNB) with high probability whenever NB is large enough. For this we use (Paulin, 2015, Theorem 3.4) similar to the proof of (Li et al., 2020b, Lemma 8). We give the proof in Section L.6.
Lemma 7. There exists a constant C such that whenever B ≥ τmix and NB ≥ C τmixµmin log( |S||A| δ ), with probability at least 1− δ, we have that for every (s, a) ∈ S ×A: Ñk(s, a) ≥ 12µ(s, a)NB ≥ 1 2µminNB

heading: F.2 LINEAR MDP CASE
text: Lemma 8. Suppose g ∈ Rd is fixed and ηB < 14 . Then, the following hold:
1.
E‖ 1∏
j=N
H̃k,j1,Bg‖ 2 ≤ exp(−ηNBκ )‖g‖ 2 (8)
2. With probability at-least 1− δ, we have:
E‖ 1∏
j=N
H̃k,j1,Bg‖φ ≤ exp(− ηNB κ )
√ κ
δ ‖g‖φ
We refer to Section K.1 for the proof.

heading: G BOUNDING THE VARIANCE TERM

heading: G.1 TABULAR CASE
text: In the tabular case, it is clear that:
〈φ(s, a), N∑ j=1 j+1∏ l=N H̃k,l1,BL̃ k,j〉 = N∑ j=1 B∑ i=1 (1− η)Ñ k,j i (s,a)η̃k,ji 1((s̃ k,j i , ã k,j i ) = (s, a)) (9)
Now, we note that Ñk,ji (s, a) depends on data in buffers l > j and when i1 < i inside buffer j. Following the discussion in (Li et al., 2021), we define the vector VarP (Vk),VarP (V ∗) ∈ RS×A such that
VarP (Vk)(s, a) = Es′∼P (·|s,a) [
sup a′∈A 〈φ(s′, a′), w̃k,11 〉 − Es′∼P (·|s,a) sup a′∈A 〈φ(s′, a′), w̃k,11 〉
]2 (10)
VarP (V ∗)(s, a) = Es′∼P (·|s,a) [ sup a′∈A 〈φ(s′, a′), w∗〉 − Es′∼P (·|s,a) sup a′∈A 〈φ(s′, a′), w∗〉 ]2 (11)
More generally, we define VarP (V )(s, a;w) = Es′∼P (·|s,a) [
sup a′∈A 〈φ(s′, a′), w〉 − Es′∼P (·|s,a) sup a′∈A 〈φ(s′, a′), w〉 ]2 Similarly, we define L̃k,j(w) by replacing wk,11 with any fixed, arbitrary w. It is easy to see that:
E [ |̃k,ji (w)| 2 ∣∣∣∣(s̃k,ji , ãk,ji ) = (s, a)] ≤ 2(1 + γ2VarP (V )(s, a;w)) (12) Lemma 9. In the tabular setting, suppose w is a fixed vector such that 〈w, φ(s, a)〉 ∈ [0, 11−γ ] for every (s, a) ∈ S × A. Fix (s, a) ∈ S × A. Then there exists a universal constant C such that with probability atleast 1− δ, we have that: Then,∣∣∣∣〈φ(s, a), N∑
j=1 j+1∏ l=N H̃k,l1,BL̃ k,j(w)〉 ∣∣∣∣ ≤ C√η log(2/δ)(1 + γ2VarP (V )(s, a;w)) + C η log(2/δ)1− γ

heading: G.2 LINEAR MDP CASE
text: We will use an appropriate exponential super-martingale to bound the error term in the linear-MDP case just like in the proof of (Jain et al., 2021b, Lemma 27). The following thereom summarizes the result and we refer to Section K.3 for its proof. Theorem 4. Suppose x,w ∈ Rd are fixed. Then, there exists a universal constant C such that with probability at least 1− δ, we have:∣∣∣∣〈x, N∑
j=1 j+1∏ l=N H̃k,l1,BL̃ k,j(w)〉 ∣∣∣∣ ≤ C‖x‖ (1 + ‖w‖φ)√η log(2/δ) . (13) By a direct application of (Vershynin, 2018, Theorem 8.1.6), we derive the following corollary. We remind the reader that CΦ is the covering number defined in Definition 2. Corollary 1. Suppose x,w ∈ Rd are fixed. Then, there exists a universal constant C such that with probability at least 1− δ, we have:∥∥∥∥ N∑
j=1 j+1∏ l=N H̃k,l1,BL̃ k,j(w) ∥∥∥∥ φ ≤ C(1 + ‖w‖φ) √ η [ CΦ + √ log( 2δ ) ] .
In order to apply the theorem above, we will need to control ‖wk,11 ‖φ uniformly for all k. The following lemma presents such a bound and we refer to Section K.4 for the proof.
Lemma 10. Suppose w̃k,11 are the iterates of Q-Rex with coupled data from a linear MDP. There exist universal constants C,C1, C2 such that whenever NB > C1 κη log
( Kκ
δ(1−γ)
) , η <
C2 (1−γ)2
C2φ+log(K/δ) and ηB < 14 , with probability at-least 1− δ, the following hold:
1. For every 1 ≤ k ≤ K, ‖w̃k,11 ‖φ ≤ 41−γ
2. For every 1 ≤ k ≤ K, ‖̃k‖φ ≤ √ 25Kκ δ(1−γ)2 exp(− ηNB κ ) + C √ η (1−γ) [ CΦ + √ log( 2Kδ ) ]

heading: H PROOF OF THEOREM 1
text: Proof. Consider the Q learning iteration:
w̃k+1,11 = T (w̃ k,1 1 ) + ̃k .
Using Lemma 4, we conclude: w̃k+1,11 − w∗ = T (w̃ k,1 1 )− T (w∗) + k and thence:
‖w̃k+1,11 − w∗‖φ ≤ γ‖w̃ k,1 1 − w∗‖φ + sup l≤K ‖ l‖φ .
Unrolling the recursion above, we conclude:
‖w̃K+1,11 − w∗‖φ ≤ γK‖w∗‖φ + supl≤K ‖ l‖φ
1− γ
Now, we invoke item 2 of Lemma 10 along with the constraints on N,B,K, η and Lemma 2 to conclude the result.

heading: I PROOF OF THEOREM 2
text: In this section we analyze the output of Q-Rex in the tabular setting and obtain convergence guarantees. 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, Q̃k,11 ∈ RS×A and we have that Q̃k,11 (s, a) = 〈w̃ k,1 1 , φ(s, a)〉. Since φ(s, a) are the standard basis vectors, we must have Q̃k,11 = w̃ k,1 1 . In the tabular setting, we see by using Lemmas 5, 6, 7, and 9 that for any δ > 0, there exists a universal constant C, whenever NB ≥ C τmixµmin log( |S||A|K
δ ), with probability at-least 1− δ, for every k ∈ [K] and every (s, a) ∈ S ×A:
Q̃k+1,11 = T [ Q̃k,11 ] + ̃k , (14)
where ̃k ∈ RS×A is such that for all (s, a), |̃k(s, a)| ≤ C √ η log ( K|S||A|
δ
) (1 + γ2VarP (V )(s, a; Q̃ k,1 1 )) + C η log(K|S||A|δ )
1− γ
+ (1− η) µminNB 2 ∥∥∥∥Q̃k,11 − T [Q̃k,11 ]∥∥∥∥ ∞ . (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̃1,11 = 0, and rt ∈ [0, 1] almost surely, we can easily show that Q̃k,11 (s, a) ∈ [0, 11−γ ] for every k, s, a. Therefore, we upper bound ∥∥∥∥Q̃k,11 −T [Q̃k,11 ]∥∥∥∥
∞ ≤ 11−γ
in Equation (15) to conclude that with probability at-least 1 − δ, for every k ∈ [K] and every (s, a) ∈ S ×A:
|̃k(s, a)| ≤ C √ η log(K|S||A|δ )γ 2 [VarP (Vk)(s, a)] + αη (16)
Where αη := C η log
(K|S||A| δ ) 1−γ + C √ η log ( K|S||A| δ ) + exp ( −ηµminNB2 ) 1−γ
Now we define ∆k = Q̃ k,1 1 − Q∗ and πk : S → A to be the deterministic policy given by Qk,11 i.e, πk(s) := arg supa∈A Q̃ k,1 1 (s, a) and π
∗ to be optimal policy given by π∗(s) := arg supa∈AQ
∗(s, a). We use the convention that we pick a single maximizing action using some rule whenever there are multiple. Similarly, we let Pπk , to be the Markov transition kernel over S × A given by Pπk((s, a), (s′, a′)) = P (s′|s, a)1(a′ = πk(s′)). Similarly, we define Pπ ∗ with respect to the policy π∗. It is easy to show that:
T (Q̃k,11 ) = R+ γPπkQ̃ k,1 1 .
Similarly,
Q∗ = T (Q∗) = R+ γPπ ∗ Q∗ .
Furthermore given anyQ ∈ RS×A, letting πQ being the greedy policy with respect to the functionQ we have that for any policy π, it can be easily seen from the definitions that following element-wise inequality follows:
PπQ ≤ PπQQ.
We now use Equation (14) along with the equations above to conclude:
γPπ ∗ ∆k + ̃k ≤ ∆k+1 ≤ γPπk∆k + ̃k . (17)
Here, the inequality is assumed to be point-wise. By properties of Markov transition kernels, we can write:
K∑ k=1 γK−k ( Pπ ∗ )K−k ̃k + γ K ( Pπ ∗ )K ∆1 ≤ ∆K+1
≤ K∑ k=1 γK−k ( k+1∏ l=K Pπl ) ̃k + γ K ( 1∏ l=K Pπl ) ∆1 . (18)
Here, we use the convention that ∏K+1 l=K P
πl = I . We bound the lower bound and the upper bound given in Equation (18) separately in order to bound ‖∆K+1‖∞. We first consider the lower bound. Using (Azar et al., 2013, Lemma 7), we have:
∥∥(I − γPπ∗)−1√VarP (V ∗)∥∥∞ ≤ √
2
(1− γ)3 . (19)
We also note from (Li et al., 2021, Equation 64) and basic calculations that:
‖ √ VarP (Vk)− √ VarP (V ∗)‖∞ ≤ √ ‖VarP (Vk)− VarP (V ∗)‖∞
≤ √ 4
1− γ ‖∆k‖∞ . (20)
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):
∆K+1 ≥ − αη + γ
K
1− γ − C
√ ηγ2 log (K|S||A| δ ) K∑ k=1 γK−k ( Pπ ∗ )K−k√ VarP (Vk)
≥ −αη + γ K
1− γ − C
√ ηγ2 log (K|S||A| δ ) K∑ k=1 γK−k ( Pπ ∗ )K−k√ VarP (V ∗)
− C1 √ 1
1− γ
√ ηγ2 log (K|S||A| δ ) K∑ k=1 γK−k √ ‖∆k‖∞
≥ −αη + γ K
1− γ − C
√ ηγ2 log (K|S||A| δ ) (I − γPπ∗)−1 √ VarP (V ∗)
− C1 √ 1
1− γ
√ ηγ2 log (K|S||A| δ ) K∑ k=1 γK−k √ ‖∆k‖∞
≥ −αη + γ K
1− γ − C
√ ηγ2
(1− γ)3 log (K|S||A| δ ) − C1 √ 1
1− γ
√ ηγ2 log (K|S||A| δ ) K∑ k=1 γK−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 a universal constant C and with probability at least 1− δ. ∆K+1 ≤ K∑ k=1 γK−k ( k+1∏ l=K Pπl ) ̃k + γ K ( 1∏ l=K Pπl ) ∆1
≤ αη + γ K
1− γ + C
√ ηγ2 log (K|S||A| δ ) K∑ k=1 γK−k ( k+1∏ l=K Pπl )√ VarP (Vk)
≤ αη + γ K
1− γ + C
√ ηγ2 log (K|S||A| δ ) K∑ k=1 γK−k √√√√(k+1∏ l=K Pπl ) VarP (Vk)
= αη + γ
K
1− γ + C
√ ηγ2 log (K|S||A| δ ) K∑ k=1 γ K−k 2 γ K−k 2 √√√√(k+1∏ l=K Pπl ) VarP (Vk)
≤ αη + γ K
1− γ + C
√ ηγ2 log (K|S||A| δ )√√√√ K∑ k=1 γK−k √√√√ K∑ k=1 γK−k ( k+1∏ l=K Pπl ) VarP (Vk)
≤ αη + γ K
1− γ + C
√ ηγ2
1− γ log (K|S||A| δ )√√√√ K∑ k=1 γK−k ( k+1∏ l=K Pπl ) VarP (Vk)
≤ αη + γ K
1− γ + C
√ ηγ2
1− γ log (K|S||A| δ )√√√√ K∑ k=K/2+1 γK−k ( k+1∏ l=K Pπl ) VarP (Vk) + γK/2 (1− γ)3 .
(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 inequality and noting that Pπ is a Markov operator, the fourth inequality via Cauchy-Schwartz and the last inequality by noting that that ‖VarP (Vk)‖∞ ≤ 1/(1− γ)2.
It can now be verified that (Li et al., 2021, Lemma 5) applies in our setting to conclude that:
K∑ k=K/2+1 γK−k ( k+1∏ l=K Pπl ) VarP (Vk) ≤
4
γ2(1− γ)2
( 1 + 2 max
K/2+1≤k≤K ‖∆k‖∞
) .
Using the equation above, along with Equations (22) and (21), we conclude there exists a universal constant C such that with probability at least 1− δ, we have:
‖∆K+1‖∞ ≤ αη + γ
K
1− γ +C
√ η
(1− γ)3 log (K|S||A| δ
)√ 1 + max
K/2+1≤k≤K ‖∆k‖∞ +
γK/2
(1− γ) (23)
We note that this works with every K replaced with l for any l ≤ K, importantly under the same event (with probability at least 1 − δ) described above for which Equation (23) holds. Define L = K2s for some s = dlog2(1 + C log( 1 1−γ ))e. Under the conditions of the Theorem, i.e,
K > C2 1
(1−γ) ( log( 11−γ ) )2 , we have γ L/2
1−γ < 1. Therefore we conclude from the discussion above that for every K ≥ l ≥ L, we must have:
‖∆l+1‖∞ ≤ αη + γ
L
1− γ + C
√ η
(1− γ)3 log (K|S||A| δ )√ 1 + max l/2+1≤k≤l ‖∆k‖∞
≤ αη + γ L
1− γ + C
√ η log (K|S||A| δ ) (1− γ)3 + C √ η log (K|S||A| δ ) (1− γ)3 √ max l/2+1≤k≤l ‖∆k‖∞ (24)
To analyze this recursion, we have the following lemma which establishes hyper-contractivity, whose proof we defer to Section L.8. Lemma 11. Suppose α, β ≥ 0. Consider the function f : R+ → R+ given by f(u) = α + β √ u.
Then, f has the unique fixed point: u∗ := ( β+ √ β2+4α
2
)2 . For t ∈ N, denoting f (t) to be the t fold
composition of f with itself, we have for any u ∈ R+:
|f (t)(u)− u∗| ≤ β(2− 1 2t−1 )|u− u∗| 1 2t .
Now consider for 0 ≤ a < s, ua := sup
K 2s−a≤l≤K
‖∆l+1‖∞
In lemma 11, define f with α = αη+γ L
1−γ + C
√ η log (K|S||A| δ ) (1−γ)3 and β = C √ η log (K|S||A| δ ) (1−γ)3 . The
fixed point u∗ is such that:
u∗ ≤ C η log(K|S||A|δ ) (1− γ)3 + αη + γ L 1− γ + √ η log (K|S||A| δ ) (1− γ)3  (25) Clearly, by Equation (24), we have: ua ≤ f(ua−1) and ‖∆K+1‖ ≤ f(us−1). By monotonicity of f(·) and the fact that u0 ≤ 11−γ (Lemma 1):
us−1 ≤ f (s−1)(u0) ≤ f (s−1) ( 1 1−γ ) .
Therefore, ‖∆K+1‖∞ ≤ f(us−1) ≤ f (s)
( 1
1−γ
)
Applying Lemma 11, we conclude:
‖∆K+1‖∞ ≤ u∗ + β(2− 1
2s−1 ) ∣∣ 1 1−γ − u ∗∣∣ 12s (26)
Note that under the constraints on the parameter η and K as stated in the Theorem, we must have
u∗ ≤ 1(1−γ)3 . By our choice of s, we must have: | 1 (1−γ) − u ∗|
1 2s ≤ C ′. Using this in Equation 26
and the fact that β(2− 1 2s−1 ) ≤ β + β2, we conclude that with probability at-least 1 − δ, we must have:
‖∆K+1‖ ≤ C η log(K|S||A|δ ) (1− γ)3 + αη + γ L 1− γ + √ η log (K|S||A| δ ) (1− γ)3  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.

heading: J PROOF OF THEOREM 3
text: We will now show uniform convergence type result under Assumption 5. For (s, a) ∈ S × A and s′ ∈ supp(P (·|s, a)). We define the random variables for all k:
P̂k(s ′|s, a) = η N∑ j=1 B∑ i=1 (1− η)Ñ k,j i (s,a)1(s̃k,ji+1 = s ′, s̃k,ji = s, ã k,j i = a)
P̄k(s ′|s, a) := η N∑ j=1 B∑ i=1 (1− η)Ñ k,j i (s,a)P (s′|s, a)1(s̃k,ji = s, ã k,j i = a).
Lemma 12. Suppose Assumption 5 holds. Then, with probability at-least 1 − δ, we must have for any fixed (s, a):∑
s′∈supp(P (·|s,a))
|P̂k(s′|s, a)− P̄k(s′|s, a)| ≤ C √ ηd̄ log(4/δ) + Cηd̄ log(4/δ)
We refer to Section K.5 for the proof. We now proceed with the proof of Theorem 3. Recall the noiseless iteration w̄k defined in the discussion following the statement of Lemma 4. We define D̄k := w k,0 0 − w̄k. Observe that we cannot apply Lemma 9 as in the proof of Theorem 2 where we used w = wk,00 in order to bound ‖ k‖∞. This is because of data re-use which causes w k,0 0 to depend on the ‘variance’ term.
However, note that w̄k is a deterministic sequence and we can apply Lemma 9 and then use the fact that w̄k ≈ wk,00 to show a similar concentration inequality. To this end, we prove the following lemma: Lemma 13. In the tabular setting, we have almost surely:∣∣∣∣〈φ(s, a), N∑
j=1 j+1∏ l=N H̃k,l1,BL̃ k,j(w)− N∑ j=1 j+1∏ l=N H̃k,l1,BL̃ k,j(v) 〉∣∣∣∣ ≤ γ‖w − v‖φ
∑ s′∈supp(P (·|s,a)) |P̂k(s′|s, a)− P̄k(s′|s, a)| (27)
The proof follows from elementary arguments via. the mean value theorem and triangle inequality. We refer to Section L.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 the proof of Theorem 2. Notice that due to data reuse, the noise k in outer loop k is given by 1(w̃ k,1 1 )
Qk+1,11 = T [ Qk,11 ] + 1(Q̃ k,1 1 ) .
We also define the noiseless Q iteration such that Q̄1,11 = Q̃ 1,1 1 and Q̄ k+1,1 1 = T (Q̄ k,1 1 ). Let ∆̄k := Q̃k,11 − Q̄ k,1 1 .
Now, by Lemma 5, we can write down
1(Q̃ k,1 1 )(s, a) = (1− η)Ñ 1(s,a)(Q̃k,11 − Q̃k,∗) + 〈φ(s, a), N∑ j=1 j+1∏ l=N H̃1,l1,BL̃ 1,j(Q̃k,11 )〉
= (1− η)Ñ 1(s,a)(Q̃k,11 − Q̃k,∗)+
〈 φ(s, a), N∑ j=1 j+1∏ l=N H̃1,l1,B ( L̃1,j(Q̃k,11 )− L̃1,j(Q̄ k,1 1 ) )〉
+ 〈 φ(s, a), N∑ j=1 j+1∏ l=N H̃1,l1,BL̃ 1,j(Q̄k,11 ) 〉 (28)
We bound each of the terms above separately. By union bound, the following statements all hold simulataneously with probability at-least 1− δ. By Theorem 7, whenever NB > C τmixµmin log( |S||A δ ), we must have Ñ (1)(s, a) ≥ µmin2 NB. A simple observation using recursion shows that Q̃k,11 (s, a), Q̄ k,1 1 (s, a) ∈ [0, 11−γ ]. Using Lemmas 12 and 13 we conclude that we must have:
sup (s,a)∈S×A ∣∣∣∣〈φ(s, a), N∑ j=1 j+1∏ l=N H̃1,l1,B ( L̃1,j(Q̃k,11 )− L̃1,j(Q̄ k,1 1 ) )〉∣∣∣∣
≤ C‖∆̄k‖∞ [√ ηd̄ log ( |S||A|
δ
) + ηd̄ log ( |S||A| δ )] (29)
Now observe that Q̄k,11 is a deterministic sequence. Therefore, using Lemma 9 uniformly for every k ≤ K and (s, a) ∈ S ×A:
∣∣∣∣〈φ(s, a), N∑ j=1 j+1∏ l=N H̃1,l1,BL̃ 1,j(Q̄k,11 ) 〉∣∣∣∣ ≤ C√η log( |S||A|Kδ )(1 + VarP (V̄k)(s, a)) + C η log ( |S||A|K δ ) 1− γ
(30)
Where, VarP (V̄k) := VarP (V )(s, a; Q̄ k,1 1 ).
We now combine all the above with Equation (28) to show that with probability at least (1− δ), we must have uniformly for every k ≤ K and (s, a) ∈ S ×A:
|̃1(Q̃k,11 )(s, a)| ≤ 1
1− γ exp
( −ηµminNB2 ) + C‖∆̄k‖∞ [√ ηd̄ log ( |S||A| δ ) + ηd̄ log ( |S||A| δ )] + C √ η log ( |S||A|K δ ) (1 + VarP (V̄k)(s, a)) + C η log ( |S||A|K δ ) 1− γ (31)
We will now present a crude bound on ‖∆̄k‖∞ to reduce the analysis of Q-RexDaRe to the analysis of Q-Rex.
Claim 1. Whenever η ≤ C1 (1−γ) 2 d̄ log ( |S||A|
δ ) , with probability at-least 1 − δ, we must have for every k ≤ K uniformly:
‖∆̄k‖∞ ≤ C exp
( −ηµminNB2 ) (1−γ)2 + C √ η (1−γ)4 log ( |S||A|K δ ) Applying this directly to Equation (31), we conclude that with probability at least (1 − δ), we must have uniformly for every k ≤ K and (s, a) ∈ S ×A:
|̃1(Q̃k,11 )(s, a)| ≤ C
(1− γ) exp
( −ηµminNB2 ) + C η log ( |S||A|K δ ) (1− γ)2 √ d̄
+ C √ η log ( |S||A|K δ ) (1 + VarP (V̄k)(s, a)) + C η log ( |S||A|K δ ) 1− γ
(32)
Proof of Claim 1. First note that T is γ contractive under the sup norm. Therefore, ‖∆̄k+1‖∞ = ∥∥∥∥T (w̃k,11 )− T (w̄k,11 ) + ̃k∥∥∥∥
∞ ≤ ∥∥∥∥T (w̃k,11 )− T (w̄k,11 )∥∥∥∥
∞ + ‖̃k‖∞
≤ γ‖∆̄k‖∞ + ‖̃k‖∞ (33)
In Equation (31), note that VarP (V̄k)(s, a) ≤ 1(1−γ)2 . Therefore, under the conditions of this Claim, we can take C1 small enough so that uniformly for every (s, a) and k ≤ K with probability at-least (1− δ), Equation (31) becomes:
‖̃k(Q̃k,11 )‖∞ ≤ exp
( −ηµminNB2 ) 1− γ + ‖∆̄k‖∞ ( 1− γ 2 ) + C √ η (1−γ)2 log ( |S||A|K δ ) .
Combining the display above and the fact that ̃k = ̃1(Q̃ k,1 1 ) in Equation (33), we conclude that with probability at-least 1− δ, for every k ≤ K uniformly:
‖∆̄k+1‖∞ ≤ 1 + γ
2 ‖∆̄k‖∞ +
exp ( −ηµminNB2 ) 1−γ + C √ η (1−γ)2 log ( |S||A|K δ ) (34)
Unrolling the recursion above and using the fact that ‖∆̄1‖∞ = 0, we conclude the statement of the claim.
We also note that the deterministic iterations Q̄k,11 converges exponentially in sup norm to Q ∗ due to γ contractivity of T . That is:
‖Q̄k,11 −Q∗‖∞ ≤ γk
(1− γ) (35)
We are now ready to connect up with the proof of Theorem 2 with minor modifications. We follow the same analysis as the proof of Theorem 2 but with VarP (Ṽk) replaced with VarP (V̄k). Similar to the proof of Theorem 2, we can control VarP (V̄k) with respect to VarP (V ∗) and ‖Q̄k,11 −Q∗‖∞ along with Equation (35). We also replace αη with
αdrη := C
(1− γ) exp
( −ηµminNB2 ) + C η log ( |S||A|K δ ) (1− γ)2 √ d̄+ C η log ( |S||A|K δ ) 1− γ
Therefore, we conclude a version of Equation (23):
‖∆K+1‖∞ ≤ αdrη + γ K
1− γ + C
√ η
(1− γ)3 log (K|S||A| δ
)√ 1 + γK/2
(1− γ) (36)
Where ∆k := Q k,1 1 −Q∗. Using the bounds on the parameters given in the statement of the Theorem, we conclude the result.

heading: K PROOFS OF CONCENTRATION INEQUALITIES

heading: K.1 PROOF OF LEMMA 8
text: First, we leverage the techniques established in (Jain et 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 a linear approximation (in η) to H̃k,j1,B . We omit the proof for the sake of clarity.
Lemma 14. Suppose ηB < 13 . Then, the following PSD inequalities hold almost surely:
I−2η (
1 + ηB1−2ηB ) B∑ i=1 φ̃k,ji ( φ̃k,ji )> ( H̃k,j1,B )> H̃k,j1,B I−2η ( 1− ηB1−2ηB ) B∑ i=1 φ̃k,ji ( φ̃k,ji )> (37)
Proof of Lemma 8. We begin by proving the first part. Using Assumption 1 and the fact that the decoupled trajectory (s̃, ã)t is assumed to be mixed at the start of every buffer, we begin by first noting from Lemma 14 that:
0 E(H̃k,j1,B) >H̃k,j1,B I − ηBE(s,a)∼µφ(s, a)(φ(s, a)) ᵀ (1− ηBκ )I . (38)
Now, observe that:
‖ 1∏
j=N
H̃k,j1,Bg‖ 2 = g> N−1∏ j=1 (H̃k,j1,B) > [ (H̃k,N1,B ) >H̃k,N1,B ] 1∏ j=N−1 H̃k,j1,Bg (39)
Now note that H̃k,N1,B is independent of H̃ k,j 1,B for j ≤ N − 1. Therefore, taking conditional expectation conditioned on Hk,j1,B for j ≤ N − 1 in Equation (39) and using Equation (38), we conclude:
E‖ 1∏
j=N
H̃k,j1,Bg‖ 2 ≤ (1− ηBκ )E‖ 1∏ j=N−1 H̃k,j1,Bg‖ 2
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 to show that with probability at least 1− δ:
‖ 1∏
j=N
H̃k,j1,Bg‖φ ≤ ‖ 1∏
j=N
H̃k,j1,Bg‖ ≤ exp
( −ηNBκ ) √ δ ‖g‖ ≤ exp(−ηNBκ ) √ κ δ ‖g‖φ .

heading: K.2 PROOF OF LEMMA 9
text: Proof. We intend to apply Freedman’s inequality (Freedman, 1975) like in (Li et al., 2021, Theorem 4), but in an asynchronous fashion and with Markovian data. Here, reverse experience replay endows our problem with the right filtration structure. Using Equation (9), we can write
〈φ(s, a), N∑ j=1 j+1∏ l=N H̃k,l1,BL̃ k,j(w)〉 = η N∑ j=1 B∑ i=1 Xk,ji (40)
Where Xk,ji := (1 − η)Ñ k,j i (s,a)̃k,ji 1 ( (s̃k,ji , ã k,j i ) = (s, a) ) . This allows us to define the sequence of sigma algebras Fk,ji = σ((s̃k,lm , ãk,lm ) : (l > j and m ∈ [B]) or (l = j and m ≤ i)) - that is, it is the sigma algebra of all states and rewards which appeared before and including (s̃k,ji , ã k,j i ) inside the buffer j and all the states in buffers l > j. Notice that Ñk,ji (s, a) is measurable with
respect to the sigma algebra Fk,ji . Using the fact that the buffers are independent, we conclude that: E [ Xk,ji |F k,j i ] = 0 and
E [ |Xk,ji | 2|Fk,ji ] ≤ 2 [ 1 + γ2VarP (V )(s, a;w) ] 1 ( (s̃k,ji , ã k,j i ) = (s, a) ) (1− η)2Ñ k,j i (s,a) .
It is also clear from our assumptions that |Xj,ki | ≤ 21−γ almost surely. Consider the almost sure inequality for the sum of conditional variances:
W k = N∑ j=1 B∑ i=1 E [ |Xk,ji | 2|Fk,ji ]
≤ 2 [ 1 + γ2VarP (V )(s, a;w) ] K∑ j=1 B∑ i=1 1 ( (s̃k,ji , ã k,j i ) = (s, a) ) (1− η)2Ñ k,j i (s,a) = 2 [ 1 + γ2VarP (V )(s, a;w)
] Ñk(s,a)−1∑ t=0 (1− η)2t ≤ 2 ( 1 + γ2VarP (V )(s, a;w) η ) (41)
We now apply (Li et al., 2021, Equation (144),Theorem 4) with R = 11−γ and σ 2 = 2 (
1+γ2VarP (V )(s,a;w) η
) to conclude the result.

heading: K.3 PROOF OF THEOREM 4
text: Proof. For the sake of convenience, in this proof we will take σ2 := 4(1 + ‖w‖2φ). Suppose λ ∈ R. For 1 ≤ m ≤ N consider: Xm := ηλ 2σ2 〈 x,
N−m+1∏ l=N H̃k,l1,B ( N−m+1∏ l=N H̃k,l1,B )> x 〉 + λ 〈 x, N∑ j=N−m+1 ( j+1∏ l=N H̃k,l1,B ) L̃k,j(w) 〉
X0 := ‖x‖2ηλ2σ2
Here we use the convention that ∏j+1 l=N H̃ k,l 1,B = I whenever j+ 1 > N . We claim that the sequence exp(Xm) forms a super martingale under an appropriate filtration. In this proof only, consider the sigma algebra Fm to be the sigma algebra of all the state action reward tuples in buffersN, . . . , N− m+ 1 and let F0 be the trivial sigma algebra. Notice that exp(Xm) is Fm measurable.
Lemma 15. Fix N ≥ m ≥ 1. Suppose Y ∈ Rd is a Fm−1 measurable random vector. Then,
E [ exp ( ηλ2σ2〈Y, H̃k,N−m+11,B ( H̃k,N−m+11,B )> Y 〉+ λ〈Y, L̃k,N−m+1(w)〉 )∣∣∣∣Fm−1] ≤ exp (ηλ2σ2‖Y ‖2) In particular, taking Y = (∏N−m+2 l=N H̃ k,l 1,B )> x , we conclude that exp(Xm) is a super martingale with respect to the filtration Fm
Proof of Lemma 15. In the proof of this lemma, we will drop the superscripts k,m for the sake of convenience and due to conditioning on Fm−1, we will treat Y as a constant. Now we define the natural filtration on the buffer under consideration (Gi)Bi=1 where Gi is the sigma algebra of the all state-action tuples from (s1, a1), . . . , (si, ai) and rewards (rh)1≤h<i.
Note that by the definition of L̃(w), we write: L̃(w) = ∑B i=1 η̃i(w)H̃1,i−1φ̃i. With this in mind,
for h ∈ [B] define L̃h(w) = ∑h i=1 η̃i(w)H̃1,i−1φ̃i. Now, L̃(w) = η̃B(w)H̃1,B−1φ̃B + L̃B−1(w)
Now, notice that the random variables 〈Y, L̃B−1〉,〈Y, H̃1,B−1φ̃B〉 and 〈Y, H̃k,m1,B ( H̃k,m1,B )> Y 〉 are
GB measureable. Furthermore, we must have: E [ ̃B(w) ∣∣GB] = 0 and |̃B(w)| ≤ 2(1 + ‖w‖φ) ≤√ 2σ. Therefore, applying conditional Hoeffding’s lemma, we have:
E [ exp ( ηλ2σ2〈Y, H̃1,B ( H̃1,B )> Y 〉+ λ〈Y, L̃(w)〉 )∣∣∣∣GB] = exp ( ηλ2σ2〈Y, H̃1,B ( H̃1,B )> Y 〉+ λ〈Y, L̃B−1(w)〉 ) E [ exp ( λη̃B(w)〈Y, H̃1,B−1φ̃B〉
)∣∣∣∣GB] ≤ exp ( ηλ2σ2〈Y, H̃1,B ( H̃1,B )> Y 〉+ λ〈Y, L̃B−1(w)〉 ) exp ( λ2η2σ2|〈Y, H̃1,B−1φ̃B〉|2
) (42)
In the third step we have used the conditional version of Hoeffding’s lemma. Now, consider Z := (H̃1,B−1) >Y . Clearly,
〈Y, H̃1,B ( H̃1,B )> Y 〉+ η|〈Y, H̃1,B−1φ̃B〉|2 = Z>H̃>B,BH̃B,BZ + ηZ>φ̃B(φ̃B)>Z
= Z> [ I − ηφ̃B(φ̃B)> + ‖φ̃B‖2η2φ̃B(φ̃B)> ] Z
≤ ‖Z‖2
Here we have used the fact that η < 1 and ‖φ̃B‖ < 1. Using the bounds above in Equation (42), we conclude:
E [ exp ( ηλ2σ2〈Y, H̃1,B ( H̃1,B )> Y 〉+ λ〈Y, L̃B(w)〉 )∣∣∣∣GB] ≤ exp ( ηλ2σ2〈Y, H̃1,B−1 ( H̃1,B−1 )> Y 〉+ λ〈Y, L̃B−1(w)〉 ) (43)
Using Equation (43) 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 a super martingale with respect to the filtration Fm. Therefore, we must have:
E exp(XN ) ≤ exp(X0) = exp(η‖x‖2λ2σ2) . It is also clear that XN ≥ λ 〈 x, ∑N j=N−m+1 (∏j+1 l=N H̃ k,l 1,B ) L̃k,j(w) 〉 . Applying Chernoff bound
with we conclude that the concentration inequality in Equation (13). We can then directly apply (Vershynin, 2018, Theorem 8.1.6) to Equation (13) in order to obtain uniform concentration bounds.

heading: K.4 PROOF OF LEMMA 10
text: Proof of Lemma 10. By definition of ̃k, we have: w̃ k+1,1 1 = T (w̃ k,1 1 ) + ̃k. Therefore, for any (s, a) ∈ S ×A, we must have:
〈φ(s, a), w̃k+1,11 〉 = R(s, a) + γEs′∼P (·|s,a) sup a′∈A 〈φ(s′, a′), w̃k,11 〉+ 〈φ(s, a), ̃k〉 .
Using the fact that R(s, a) ∈ [0, 1], we conclude:
‖w̃k+1,11 ‖φ ≤ 1 + γ‖w̃ k,1 1 ‖φ + ‖̃k‖φ (44)
By independence of outer-loops for the coupled data, we note that w̃k,11 is independent of the data in buffer k. Therefore we can apply Theorem 4 (and resp. Lemma 8) conditionally with w = w̃k,11
(and resp. g = w̃k,11 − w∗), the bias variance decomposition given in Lemma 5 and the bound on ‖w∗‖φ in Lemma 4 to conclude that with probability at-least 1− δ, for every k ≤ K:
‖̃k‖φ ≤ √ Kκ
δ exp(−ηNBκ )(‖w̃ k,1 1 ‖φ +
1
1− γ )
+ C(1 + ‖w̃k,11 ‖φ) √ η [ CΦ + √ log( 2Kδ ) ] (45)
We now choose constants C1 and C2 in the statement of the Lemma such that Equation 45 implies:
‖̃k‖φ ≤ 1− γ
2 ‖w̃k,11 ‖φ + 1
Using the equation above in Equation (44), we conclude:
‖w̃k+1,11 ‖φ ≤ 2 + 1 + γ
2 ‖w̃k,11 ‖φ .
Unrolling the recursion above and noting w1,11 = 0, we conclude that with probability at-least 1− δ, we must have ‖w̃k,11 ‖φ ≤ 41−γ for every k ≤ K. The bound in item 2 follows by using item 1, Equation (45) and the fact that w̃k,11 is independent of the data in buffer k due to our coupling.

heading: K.5 PROOF OF LEMMA 12
text: Proof. For the sake of convenience, we will take d̄ = |supp(P (·|s, a))| and index supp(P (·|s, a)) by [d̄]. Consider Y ∈ {−1, 1}d̄. We consider the class of random variables indexed by elements of {−1, 1}d̄:
∆(Y ; s, a) = ∑ s′ Ys′ [ P̂k(s ′|s, a)− P̄ (s′|s, a) ]
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 Fk,ji for i ∈ [B] and j ∈ [K] as defined in the proof of Lemma 9. We now define
Xk,ji (Y ) := (1−η) Ñk,ji (s,a) ∑ s′ Ys′ ( 1(s̃k,ji+1 = s ′, s̃k,ji = s, ã k,j i = a)− P (s ′|s, a)1(s̃k,ji = s, ã k,j i = a) ) .
We note that E [ Xk,ji (Y )|F k,j i ] = 0 and |Xk,ji (Y )| ≤ 2 almost surely and a simple calculation
reveals that: E [ |Xk,ji (Y )|2|F k,j i ] ≤ (1− η)2Ñ k,j i 1(s̃k,ji = s, ã k,j i = a)
It is also clear that: ∆(Y ; s, a) = η ∑K j=1 ∑B i=1X k,j i (Y ). Apply Freedman’s concentration inequality, we conclude for any fixed Y ∈ {−1, 1}d̄ and (s, a) ∈ S ×A,
P(|∆(Y ; s, a)| > C √ η log(2/δ) + η log(2/δ)) ≤ δ
Applying a union bound over all Y ∈ −1, 1d, we conclude:
P( sup Y ∈{−1,1}d̄
|∆(Y ; s, a)| > C √ ηd̄ log(4/δ) + ηd̄ log(4/δ)) ≤ δ .
We complete the proof by noting that
sup Y ∈{−1,1}d̄
|∆(Y ; s, a)| = ∑
s′∈supp(P (·|s,a))
|P̂k(s′|s, a)− P̄k(s′|s, a)|

heading: L TECHNICAL LEMMAS

heading: L.1 COUPLING LEMMA
text: We first introduce some useful notation: Let Dk,j (resp. D̃k,j) be the tuple of random variables (sk,ji , a k,j i , r k,j i ) B+1 i=1 (resp. (s̃ k,j i , ã k,j i , r̃ k,j i ) B+1 i=1 ).
Lemma 16. Suppose
u ≥
{ Cτmix log( T δ ) in the tabular setting
Cτmix log( T Cmixδ ) in the general setting
(46)
Then, we can define the sequences (st, at, rt) and (s̃t, ãt, r̃t) on a common probability space such that:
1. The tuples Dk,j and D̃k,j have the same distribution for every (k, j),
2. The sequence D̃k,j for k ≤ N, j ≤ K is i.i.d.
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 et al., 2020). For the general state space case, we apply appropriate modifications as pioneered in (Goldstein, 1979).

heading: L.2 PROOF OF LEMMA 2
text: Proof. The first part follows from the definitions. For the second part, note that: ‖x‖ ≥ ‖x‖φ follows from Cauchy-Schwarz inequality and Assumption 1. For the reverse inequality we use Assumption 4 to show that:
‖x‖2φ ≥ E(s,a)∼µ〈φ(s, a), x〉2 ≥ ‖x‖2
κ

heading: L.3 PROOF OF LEMMA 3
text: Proof. By Definition 1, we have that
Es′∼P (·|s′,a′) sup a′∈A 〈φ(s, a), w0〉 = d∑ i=1 ∫ s′ sup a′∈A 〈φ(s′, a′), w0〉βi(ds′)〈φ(s, a), ei〉
= d∑ i=1 hi〈φ(s, a), ei〉
= 〈h, φ(s, a)〉 (47) Where hi := ∫ s′
supa′∈A〈φ(s′, a′), w0〉βi(ds′). Again, by Definition 1, we have: R(s, a) = 〈θ, φ(s, a)〉. Therefore,R(s, a)+Es′∼P (·|s,a) supa′∈A〈φ(s, a), w0〉 = 〈φ(s, a), θ+h〉. We conclude the result using Assumption 2.

heading: L.4 PROOF OF LEMMA 4
text: Proof. Suppose w0, w̃0 ∈ Rd are arbitrary. Let w1 = T (w0) and w̃1 = T (w̃0). For any φ(s, a), we have:
|〈φ(s, a), w1 − w̃1〉| = γ ∣∣Es′∼P (·|s,a) sup
a′∈A 〈φ(s′, a′), w0〉 − Es′∼P (·|s,a) sup a′∈A 〈φ(s′, a′), w̃0〉
∣∣ (48)
By Assumption 2, for every fixed s′ there exist a′max(s ′), ã′max(s ′) such that
sup a′∈A 〈φ(s′, a′(s′)), w0〉 = 〈φ(s′, ã′max(s′)), w0〉 and sup a′∈A 〈φ(s′, a′), w̃0〉 = 〈φ(s′, ã′max(s′)), w̃0〉.
Therefore for any s′ it holds that,
〈φ(s′, ã′max), w0 − w̃0〉 ≤ sup a′∈A 〈φ(s′, a′), w0〉 − sup a′∈A 〈φ(s′, a′), w̃0〉 ≤ 〈φ(s′, a′max), w0 − w̃0〉
=⇒ ∣∣ sup a′∈A 〈φ(s′, a′), w0〉 − sup a′∈A 〈φ(s′, a′), w̃0〉 ∣∣ ≤ ‖w0 − w̃0‖φ . Combining this with Equation (48), we conclude the γ-contractivity of T . By contraction mapping theorem, T has a unique fixed point we conclude that it is w∗ by considering Q(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) ∈ [0, 1] by assumption and w∗ = T (w∗), we have: |〈φ(s, a), w∗〉| ≤ 1 + γ‖w∗‖φ. Therefore, ‖w∗‖ ≤ 11−γ . The second norm equality follows from Lemma 2.

heading: L.5 PROOF OF LEMMA 5
text: Proof. We write the iteration in the outer-loop k as: w̃k,ji+1 = [ I − ηφ̃k,j−i [φ̃ k,j −i ] > ] w̃k,ji + ηφ̃ k,j −i [ r̃k,j−i + γ sup
a′∈A 〈w̃k,11 , φ(s̃ k,j −(i−1), a
′)〉 ]
Using the fact that 〈w̃k+1,∗, φ̃k,j−i 〉 = R̃ k,j −i + γEs′∼P (·|s̃k,j−i ,ãk,j−i ) supa′∈A〈φ(s ′, a′), w̃k,11 〉, and recalling the notation in (5),(6), we write:
w̃k,ji+1 − w̃ k+1,∗ = [ I − ηφ̃k,j−i [φ̃ k,j −i ] > ] ( w̃k,ji − w k+1,∗ ) + ηφ̃k,j−i k,j −i .
Therefore, w̃k,j+11 − w̃k+1,∗ = H̃ k,j 1,B(w̃ k,j 1 − w̃k+1,∗) + L̃k,j
Unfurling further, and using the fact that w̃k,N+11 = w̃ k+1,1 1 , we conclude the statement of the lemma.

heading: L.6 PROOF OF LEMMA 7
text: We let Ñk,j(s, a) := ∑B i=1 1((s̃ k,j i , ã
k,j i ) = (s, a)). We want to show that the quantity∑N
j=1 Ñ k,j(s, a) concentrates around its expectation. Note that EÑk,j(s, a) = Bµ(s, a) and that Ñk,j(s, a) are i.i.d. for j ∈ [N ]. From the proof of (Paulin, 2015, Theorem 3.4) and the fact that γps ≥ 12τmix , we conclude:
E exp(λ( N∑ j=1 Ñk,j(s, a)−Bµ(s, a))) = N∏ j=1 E exp(λ(Ñk,j(s, a)−Bµ(s, a)))
≤ exp ( 8N(B + 2τmix)µ(s, a)τmixλ 2
1− 20λτmix
) (49)
Following the Chernoff bound in the proof of (Paulin, 2015, Theorem 3.4), we conclude:
P(|Ñk(s, a)−NBµ(s, a)| > t) ≤ 2 exp ( − t 2
16τmix(B + 2τmix)Kµ(s, a) + 40tτmix
) (50)
Taking t = 12NBµ(s, a), whenever B ≥ τmix (by assumption), we must have: P ( Ñk(s, a) ≤ 1
2 NBµ(s, a)
) ≤ 2 exp ( −CKBµ(s,a)τmix ) for some constant C. Further, via a union bound over all state action pairs (s, a), we conclude the statement of the lemma.

heading: L.7 PROOF OF LEMMA 13
text: We first prove a simple consequence of multivariate calculus. Lemma 17. Let f : Rn → R be defined by f(x) = supi xi. Then, for every x, y ∈ Rn, there exists ζ ∈ Rd such that ‖ζ‖1 = 1, ζi ≥ 0 and:
f(x)− f(y) = 〈ζ, x− y〉
Proof. We consider the log-sum-exp function. Given L ∈ R+, define fL(x) := 1 L log ( ∑n i=1 exp(Lxi)). An elementary calculation shows that:
log(n)
L + sup i xi ≥ fL(x) ≥ sup i xi
Therefore, for any fixed x,
lim L→∞ fL(x) = f(x) .
Now, ∇fL(x) = (p1, . . . , pn) where pi = exp(Lxi)∑n j=1 exp(Lxj)
. Clearly, 〈∇fL(x), ei〉 ≥ 0 and ‖∇fL(x)‖1 = 1. By the mean value theorem there exists βL such that:
fL(x)− fL(y) = 〈∇fL(βL), x− y〉 . (51)
Now, the simplex in Rn (denoted by ∆n) is compact. Therefore, there exists a sub-sequence Lk → ∞ such that limk→∞∇fLk(βLk) = ζ ∈ ∆n. Taking limit along the sub-sequence Lk in Equation (51), we conclude the result.
Proof of Lemma 13. In the tabular setting, we have the following expression using Equation (40):
L.H.S = ∣∣∣∣ηγ K∑
j=1 B∑ i=1 (1− η)Ñ k,j i (s,a)1 [ (s̃k,ji , ã k,j i ) = (s, a) ] [ ̃k,ji (w)− ̃ k,j i (v) ]∣∣∣∣ (52) Where
̃k,ji (w) := [ sup a′∈A 〈w, φ(s̃k,ji+1, a ′)〉 − Es′∼P (·|s̃k,ji ,ãk,ji ) supa′∈A 〈φ(s′, a′), w〉 ] Now, by an application of Lemma 17, we show that for some η(·|s′, w, v) ∈ ∆(A), depending only on (s′, w, v), we have:
sup a′∈A 〈w, φ(s′, a′), w〉 − sup a′∈A 〈w, φ(s′, a′), v〉 = ∑ a′∈A ζ(a′|s′, w, v)〈φ(s′, a′), w − v〉
Now, using the definition of P̂k(·|s, a) and P̄ (·|s, a) in the discussion preceding Lemma 12, we can simplify Equation (52) to:
L.H.S. = γ ∣∣∣∣ ∑ s′∈supp(P (·|s,a))
a′∈A
( P̂k(s ′|s, a)− P̄k(s′|s, a) ) ζ(a′|s′, w, v)〈φ(s′, a′), w − v〉 ∣∣∣∣ (53) We conclude the statement of the lemma by an application of the Holder inequality.

heading: L.8 PROOF OF LEMMA 11
text: Proof. We solve for f(u∗) = u∗ to obtain the relation: u∗ = α+ β √ u∗, which after discarding the negative solution for √ u∗ yields the unique solution: u∗ = ( β+ √ β2+4α
2
)2 . To prove the second
part, consider for arbitrary x, y ∈ R+, the following hyper-contractivity:
|f(x)− f(y)| = β| √ x−√y|
≤ β √ |x− y| (54)
The second step follows from the fact that | √ a− √ b| ≤ √ |a− b|. Since u∗ = f(u∗), we apply the inequality above:
|f (t)(u)− u∗| = |f (t)(u)− f (t)(u∗)| ≤ β √ |f (t−1)(u)− f (t−1)(u∗)| (55)
We then conclude the result by induction.

Review summaries:
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. 

The paper provides sample complexity bounds for a Q-learning based algorithm with target Q and experience replay. Contributions: 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.

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.