# Online Target Q-learning with Reverse Experience Replay: Efficiently finding
the Optimal Policy for Linear MDPs

Naman Agarwal, Prateek Jain, Praneeth Netrapalli
Google Research
<EMAIL_ADDRESS>&Syomantak Chaudhuri
University of California, Berkeley
<EMAIL_ADDRESS>&Dheeraj Nagaraj
MIT
<EMAIL_ADDRESS>
###### 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 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 (or more generally for MDPs with zero inherent Bellman error
with linear approximation (ZIBEL)) and provide non-asymptotic bounds on sample
complexity – the first such result for a Q-learning method for this class of
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.

##  1 Introduction

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 sub-optimal 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 (or more generally for MDPs
with zero inherent Bellman error with linear function approximation (ZIBEL))
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 a 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 ZIBEL
MDPs, with a 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 a 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.

Paper | Algorithm | Data Type | Sample Complexity
---|---|---|---
(Ghavamzadeh et al., 2011) | Speedy Q-learning | Synchronous | $\frac{|\mathcal{S}||\mathcal{A}|}{\epsilon^{2}(1-\gamma)^{4}}$
(Wainwright, 2019b) |  Variance Reduced Q-learning | Synchronous | $\frac{|\mathcal{S}||\mathcal{A}|}{\epsilon^{2}(1-\gamma)^{3}}$
(Li et al., 2020b) |  Variance Reduced Q-learning | Asynchronous | $\frac{1}{\mu_{\min}\epsilon^{2}(1-\gamma)^{3}}$
(Li et al., 2020b) | Q-learning | Asynchronous | $\frac{1}{\mu_{\min}\epsilon^{2}(1-\gamma)^{5}}$
(Li et al., 2021) | Q-learning | Synchronous | $\frac{|\mathcal{S}||\mathcal{A}|}{\epsilon^{2}(1-\gamma)^{4}}$
This work, Theorem 2 |  Q-learning+ otl \+ rer (Q-Rex) | Asynchronous | $\frac{|\mathcal{S}||\mathcal{A}|}{\epsilon^{2}(1-\gamma)^{4}}$
This work, Theorem 3 |  Q-Rex+ data-reuse (Q-RexDaRe) | Asynchronous | ${\frac{\max\left(\bar{d},\frac{1}{\epsilon^{2}}\right)}{\mu_{\min}(1-\gamma)^{3}}}$

Table 1: Comparison of tabular Q-learning based algorithms.
$\bar{d}\leq|\mathcal{S}|$ is maximum size of support of $P(\cdot|s,a)$. In
the case of asynchronous setting, $\frac{1}{\mu_{\min}}$ is roughly equivalent
to $|\mathcal{S}||\mathcal{A}|$ in the synchronous setting. We use the color
green to represent results with optimal dependence on $(1-\gamma)^{-1}$.

###  1.1 Related Works

##### Tabular Q-learning

Tabular MDPs are the most basic examples of MDPs where the state space
($\mathcal{S}$) and the action space ($\mathcal{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 $\epsilon$ error is
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\epsilon^{2}}$, where
$\gamma$ 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
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\epsilon^{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
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{5}\epsilon^{2}}$. These results
seem unsatisfactory since $\gamma\sim 0.99\text{ (or even }0.999\text{)}$ 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 sub-optimal 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 $\mathcal{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 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 (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 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 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 ER111The
version of ER used in Carvalho et al. (2020) makes the setting completely
synchronous as opposed to the asynchronous setting considered by us. . 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 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 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 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 super-martingale 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).

##  2 Problem Setting

##### Markov Decision Process

We consider non-episodic, i.e. infinite horizon, time homogenous Markov
Decision Processes (MDPs) and we denote an MDP by
MDP($\mathcal{S},\mathcal{A},\gamma,P,R$) where $\mathcal{S}$ denotes the
state space, $\mathcal{A}$ denotes the action space, $\gamma\in[0,1)$
represents the discount factor, $P(s^{\prime}|s,a)$ represents the probability
of transition to state $s^{\prime}$ from the state $s$ on action $a$. We
assume for purely technical reasons that $\mathcal{S}$ and $\mathcal{A}$ are
compact subsets of $\mathbb{R}^{n}$ (for some $n\in\mathbb{N}$).
$R:\mathcal{S}\times\mathcal{A}\to[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 $\pi(s)$, where $\pi:\mathcal{S}\to\mathcal{A}$, at state
$s\in\mathcal{S}$, then $P$ along with the ‘policy’ $\pi$ induces a Markov
chain over $\mathcal{S}$, whose transition kernel is denoted by $P^{\pi}$. We
write the $\gamma$-discounted value function of the MDP starting at state $s$
to be:

$V(s,\pi)=\mathbb{E}[\sum_{t=0}^{\infty}\gamma^{t}R(S_{t},A_{t})|S_{0}=s,A_{t}=\pi(S_{t})\forall
t].$ (1)

It is well-known that under mild assumptions, there exists at least one
optimal policy $\pi^{*}$ such that the value function $V(s,\pi)$ is maximized
for every $s$and that there is an optimal Q-function,
$Q^{*}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$, such that one can find the
optimal policy as
$\pi^{*}(s)=\operatorname*{arg\,max}_{a\in\mathcal{A}}Q^{*}(s,a)$, optimal
value function as $V^{*}(s)=\max_{a\in\mathcal{A}}Q^{*}(s,a)$ and it satisfies
the following fixed point equation.

$Q^{*}(s,a)=R(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}[\max_{a^{\prime}\in\mathcal{A}}Q^{*}(s^{\prime},a^{\prime})]\qquad\forall(s,a)\in\mathcal{S}\times\mathcal{A}.$
(2)

(2) can be alternately viewed as $Q^{*}$ being the fixed point of the Bellman
operator $\mathcal{T}$, where

$\mathcal{T}(Q)(s,a)=R(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}[\max_{a^{\prime}}Q(s^{\prime},a^{\prime})].$

The basic task at hand is to estimate $Q^{*}(s,a)$ from a single trajectory
$(s_{t},a_{t})_{t=1}^{T}$ such that $s_{t+1}\sim P(\cdot|s_{t},a_{t})$ along
with rewards $(r_{t})_{t=1}^{T}$, where $r_{1},\dots,r_{T}$ are random
variables such that $\mathbb{E}\left[r_{t}|s_{t}=s,a_{t}=a\right]=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 $\mathcal{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 $\pi(s)$ for choosing its action at state
$s$.

Given a trajectory $\\{s_{t},a_{t},r_{t}\\}_{t=1}^{T}$ generated using some
unknown behaviour policy $\pi$, 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
Q-learning algorithm. In this online algorithm, we maintain an estimate of
$Q^{*}(s,a)$ at time $t$, $Q_{t}(s,a)$ and the estimate is updated at time $t$
for $(s,a)=(s_{t},a_{t})$ in the trajectory. Formally, with step-sizes given
as $\\{\eta_{t}\\}$, Q-learning performs the following update at time $t$,

$\begin{gathered}Q_{t+1}(s_{t},a_{t})=(1-\eta_{t})Q_{t}(s_{t},a_{t})+\eta_{t}\left[r_{t}+\gamma\max_{a^{\prime}\in\mathcal{A}}Q_{t}(s_{t+1},a^{\prime})\right]\\\
Q_{t+1}(s,a)=Q_{t}(s,a)\quad\forall\;(s,a)\neq(s_{t},a_{t}).\end{gathered}$
(3)

In this work, we focus on two special classes of MDPs which are popular in
literature.

##### Linear Markov Decision Process

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 $\phi(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($\mathcal{S},\mathcal{A},\gamma,\mathbb{P},R$) is a linear MDP with
feature map $\phi:\mathcal{S}\times\mathcal{A}\to\mathbb{R}^{d}$, if

  1. 1.

there exists a vector $\theta\in\mathbb{R}^{d}$ such that
$R(s,a)=\langle\phi(s,a),\theta\rangle$, and

  2. 2.

there exists $d$ unknown (signed) measures over $\mathcal{S}$
$\beta(\cdot)=\\{\beta_{1}(\cdot),\ldots,\beta_{d}(\cdot)\\}$ such that the
transition probability $P(\cdot|s,a)=\langle\phi(s,a),\beta(\cdot)\rangle$.

In the rest of this paper, in the tabular setting we assume that the dimension
$d=|\mathcal{S}\times\mathcal{A}|$ and we use a one hot embedding where we map
$(s,a)\to\phi(s,a)=e_{s,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.

##### Inherent Bellman Error

There is another widely studied class of MDPs which admit a good linear
representation (Zanette et al., 2020; Munos & Szepesvári, 2008; Szepesvári &
Smart, 2004).

######  Definition 2.

(ZIBEL MDP) For an
$\mathcal{M}=\text{MDP}(\mathcal{S},\mathcal{A},\gamma,\mathbb{P},R)$ with a
feature map $\phi:\mathcal{S}\times\mathcal{A}\to\mathbb{R}^{d}$, we define
the inherent Bellman error ($\mathsf{IBE}(\mathcal{M})$) as:

$\sup_{\theta\in\mathbb{R}^{d}}\inf_{\theta^{\prime}\in\mathbb{R}^{d}}\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\bigr{|}\langle\phi(s,a),\theta^{\prime}\rangle-R(s,a)-\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\sup_{a^{\prime}\in\mathcal{A}}\langle\theta,\phi(s^{\prime},a^{\prime})\rangle\bigr{|}$

If $\mathsf{IBE}(\mathcal{M})=0$, then call this MDP a ZIBEL (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^{*}\in\mathbb{R}^{d}$ such that the optimal
Q-function, $Q^{*}(s,a)=\langle\phi(s,a),w^{*}\rangle$ for every
$(s,a)\in\mathcal{S}\times\mathcal{A}$, which can be explicity expressed as a
function of $\theta,\beta$ and $Q^{*}$ (under mild conditions on $R,\beta$ and
$\phi$). More generally, they allow us to lift the Bellman iteration to
$\mathbb{R}^{d}$ _exactly_ and update our estimates for $w^{*}$ values
directly (Lemmas 3, 4).

Hence, we can focus on estimating $Q^{*}$ by estimating $\bm{w}^{*}$. To this
end, the standard Q-Learning approach to learning the Q function can be
extended to the linear case as follows:

$w_{t+1}=w_{t}+\eta_{t}\left[r_{t}+\gamma\max_{a^{\prime}\in\mathcal{A}}\langle\phi(s_{t+1},a^{\prime}),w_{t}\rangle-\langle\phi(s_{t},a_{t}),w_{t}\rangle\right]\phi(s_{t},a_{t}).$

The above update can be seen as a gradient descent step on the loss function
$f(\bm{w}_{t})=(\langle\phi(s_{t},a_{t}),\bm{w}_{t}\rangle-\mathsf{target})^{2}$
where
$\mathsf{target}=r_{t}+\gamma\max_{a^{\prime}}\langle\phi(s_{t+1},a^{\prime}),\bm{w}_{t}\rangle$.
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.

###  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 $\mathcal{M}$ has $\mathsf{IBE}(\mathcal{M})=0$ (Definition 2),
$\|\phi(s,a)\|_{2}\leq 1$. Furthermore, $R(s,a)\in[0,1]$.

######  Assumption 2.

Let $\Phi:=\\{\phi(s,a):(s,a)\in\mathcal{S}\times\mathcal{A}\\}$. $\Phi$ is
compact, $\mathsf{span}(\Phi)=\mathbb{R}^{d}$ and $(s,a)\to\phi(s,a)$ is
measurable.

Even when $\mathsf{span}(\Phi)\neq\mathbb{R}^{d}$, 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
$\mathsf{span}(\Phi)^{\perp}$.

######  Definition 3.

For $r>0$, let $\mathcal{N}(\Phi,\|\cdot\|_{2},r)$ be the $r$-covering number
under the standard Euclidean norm over $\mathbb{R}^{d}$. Define:

$C_{\Phi}:=\int_{0}^{\infty}\sqrt{\log{\mathcal{N}(\Phi,\|\|_{2},r)}}dr$

Observe that since $\Phi$ is a subset of the unit Euclidean ball in
$\mathbb{R}^{d}$, $C_{\Phi}\leq C\sqrt{d}$. However, in the case of tabular
MDPs it is easy to show that $C_{\Phi}\leq C\sqrt{\log d}$.

######  Definition 4.

We define the norm $\|\cdot\|_{\phi}$ over $\mathbb{R}^{d}$ by
$\|x\|_{\phi}=\sup_{(s,a)}|\langle\phi(s,a),x\rangle|$.

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
$\pi:\mathcal{S}\to\Delta(\mathcal{A})$ which selects a random action
corresponding to each state. At each step, given $(s_{t},a_{t})=(s,a)$,
$s_{t+1}\sim P(\cdot|s,a)$ and $a_{t+1}\sim\pi(s_{t+1})$. This gives us a
Markov kernel over $\mathcal{S}\times\mathcal{A}$ which specifies the law of
$(s_{t+1},a_{t+1})$ conditioned on $(s_{t},a_{t})$. We will denote this kernel
by $P^{\pi}$. 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 $\mu$ for the kernel $P^{\pi}$.
Moreover, this Markov chain is exponentially ergodic in the total variation
distance with total variation distance $\tau_{\mathsf{mix}}$. In the general
case, we will take this to mean that there exists a constant
$C_{\mathsf{mix}}$ for every $t\in\mathbb{N}$

$\sup_{x\in\mathcal{S}\times\mathcal{A}}\mathsf{TV}((P^{\pi})^{t}(x,\cdot),\mu)\leq
C_{\mathsf{mix}}\exp(-t/\tau_{\mathsf{mix}})$

In the tabular setting, we will use the standard definition of
$\tau_{\mathsf{mix}}$ instead:

$\tau_{\mathsf{mix}}=\inf\\{t:\sup_{x\in\mathcal{S}\times\mathcal{A}}\mathsf{TV}((P^{\pi})^{t}(x,\cdot),\mu)\leq
1/4\\}\,.$

Here $\mathsf{TV}$ refers to the total variation distance.

######  Assumption 4.

There exists $\kappa>0$ such that:
$\mathbb{E}_{(s,a)\sim\mu}\phi(s,a)\phi^{\top}(s,a)\succeq\frac{I}{\kappa}\,.$

In the tabular setting, Assumption 4 manifests itself as
$\frac{1}{\kappa}=\mu_{\min}:=\min_{(s,a)}\mu(s,a)$ which is also standard (Li
et al., 2020b). Whenever we discuss high probability bounds (i.e, probability
at least $1-\delta$), we assume that $\delta\in(0,1/2)$. Similarly, we will
assume that the discount factor $\gamma\in(1/2,1)$ so that we can absorb
$\mathsf{poly}(1/\gamma)$ factors into constants.

##  3 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 sample efficient variant Q-RexDaRe (Q-Rex
+ data reuse, Algorithm 2) and its episodic variant EpiQ-Rex (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.

Algorithm 1 Q-Rex

1:Input: learning rates $\eta$, horizon $T$, discount factor $\gamma$,
trajectory $X_{t}=\\{s_{t},a_{t},r_{t}\\}$, Buffer size $B$, Buffer gap $u$,
Number of inner loop buffers $N$

2:Total buffer size: $S\leftarrow B+u$, Outer-loop length:
$K\leftarrow\frac{T}{NS}$, Initialization $w_{1}^{1,1}=0$

3:for $k=1,\ldots,K$ do

4: for $j=1,\ldots,N$ do

5: Form buffer $\textsf{Buf}=\\{X^{k,j}_{1},\dots,X^{k,j}_{S}\\}$, where,
$X^{k,j}_{i}\leftarrow X_{NS(k-1)+S(j-1)+i}$

6: Define for all $i\in[1,S]$,
$\phi_{i}^{k,j}\triangleq\phi(s_{i}^{k,j},a_{i}^{k,j})$.

7: for $i=1,\ldots,B$ do

8:
$w_{i+1}^{k,j}=w_{i}^{k,j}+\eta\left[r_{B+1-i}^{k,j}+\gamma\max\limits_{a^{\prime}\in\mathcal{A}}\langle\phi(s_{B+2-i}^{k,j},a^{\prime}),w_{1}^{k,1}\rangle-\langle\phi_{B+1-i}^{k,j},w_{i}^{k,j}\rangle\right]\phi_{B+1-i}^{k,j}$

9: Option I: $w^{k,j+1}_{1}=w^{k,j}_{B+1}$

10: Option II: $w^{k,j+1}_{1}=\frac{1}{B}\sum_{i=1}^{B}w^{k,j}_{i+1}$

11: Option I: $w^{k+1,1}_{1}=w^{k,N+1}_{1}$

12: Option II: $w^{k+1,1}_{1}=\frac{1}{N}\sum_{l=2}^{N+1}w^{k,l}_{1}$

13:Return $w^{K+1,1}_{1}$

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\in[K]$), we checkpoint our current guess of the $Q$
function given by $w_{1}^{k,1}$. Each outer-loop iteration corresponds to an
inner-loop over the buffer collection with $N$ buffers, i.e. at iteration
$j\in[N]$, we collect a buffer of size $B+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

$w_{i+1}^{k,j}=w_{i}^{k,j}+\eta\left[r_{B+1-i}^{k,j}+\gamma\max\limits_{a^{\prime}\in\mathcal{A}}\langle\phi(s_{B+2-i}^{k,j},a^{\prime}),\mathbf{w_{1}^{k,1}}\rangle-\langle\phi_{B+1-i}^{k,j},w_{i}^{k,j}\rangle\right]\phi_{B+1-i}^{k,j}$

Figure 1: Illustration of Online Target Q-learning with Reverse Experience
Replay

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, $w^{1,1}_{1}=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.

##  4 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 an outer-loop iteration, $B$ is the
buffer size and $u$ is the size of the gap. In what follows, we will take
$u=\tilde{O}(\tau_{\mathsf{mix}})$, $B=10u$,
$K=\tilde{O}(\frac{1}{1-\gamma})$. 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 $Q^{K+1,1}_{1}(s,a)$,
we denote $\langle\phi(s,a),w^{K+1,1}_{1}\rangle$ which is our estimate for
the optimal $Q$ function. Here $w^{K+1,1}_{1}$ is the output of either Q-Rex
or Q-RexDaRe at the end of $K$ outer-loop iterations. Define
$\|Q^{K+1,1}_{1}-Q\|_{\infty}:=\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\bigr{|}Q^{K+1,1}_{1}(s,a)-Q^{*}(s,a)\bigr{|}$.

Setting | $K$ | $N$ | $u$ | $B$ | $\eta$
---|---|---|---|---|---
ZIBEL MDP (Theorem 1) | $\geq 1$ | $>\frac{C_{3}}{B}\frac{\kappa}{\eta}\log\left(\frac{K\kappa}{\delta(1-\gamma)}\right)$ | $\geq C_{1}\tau_{\mathsf{mix}}\log(\tfrac{C_{\mathsf{mix}}KN}{\delta})$ | $=10u$ | $<C_{2}\min(\frac{(1-\gamma)^{2}}{C^{2}_{\Phi}+\log(K/\delta))},\tfrac{1}{B})$
Tabular MDP (Theorem 2) | $\geq C_{2}\frac{\bigr{(}\log\bigr{(}\tfrac{1}{1-\gamma}\bigr{)}\bigr{)}^{2}}{1-\gamma}$ | $>\frac{C_{4}}{B}\frac{\tau_{\mathsf{mix}}}{\mu_{\min}}\log(\tfrac{|S||A|K}{\delta})$ | $\geq C_{1}\tau_{\mathsf{mix}}\log(\tfrac{KN}{\delta})$ | $=10u$ | $<\frac{C_{3}}{\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}}$
Tabular MDP (Theorem 3) | $\geq C_{2}\frac{\log\bigr{(}\tfrac{1}{1-\gamma}\bigr{)}}{1-\gamma}$ | $>\frac{C_{4}}{B}\frac{\tau_{\mathsf{mix}}}{\mu_{\min}}\log(\tfrac{|S||A|}{\delta})$ | $\geq C_{1}\tau_{\mathsf{mix}}\log(\tfrac{KN}{\delta})$ | $=10u$ | $<C_{3}\frac{(1-\gamma)^{2}}{\bar{d}\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}$
ZIBEL MDP (Theorem 1) | $\tfrac{\beta_{1}}{(1-\gamma)}$ | $\kappa\beta_{2}\max\bigr{(}\frac{C_{\Phi}^{2}+\beta_{2}}{\epsilon^{2}(1-\gamma)^{4}\tau_{\mathsf{mix}}},1\bigr{)}$ | $\tau_{\mathsf{mix}}\log\left(\tfrac{KN}{\delta}\right)$ | $10u$ | $\min\bigr{(}\frac{(1-\gamma)^{4}\epsilon^{2}}{C_{\Phi}^{2}+\beta_{3}},\frac{1}{B}\bigr{)}$
Tabular MDP (Theorem 2) | $\frac{\beta_{1}^{2}}{1-\gamma}$ | $\frac{1}{\mu_{\min}}\max\left(\beta_{5},\frac{\beta_{1}}{\eta\tau_{\mathsf{mix}}}\bigr{)}\right)$ | $\tau_{\mathsf{mix}}\log\left(\tfrac{KN}{\delta}\right)$ | $10u$ | $\frac{(1-\gamma)^{3}}{\beta_{5}}\min(\epsilon,\epsilon^{2})$
Tabular MDP (Theorem 3) | $\tfrac{\beta_{1}}{(1-\gamma)}$ | $\frac{1}{\mu_{\min}}\max\left(\beta_{5},\frac{\beta_{1}}{\eta\tau_{\mathsf{mix}}}\bigr{)}\right)$ | $\tau_{\mathsf{mix}}\log\bigr{(}\tfrac{KN}{\delta}\bigr{)}$ | $10u$ | $\min\left(\tfrac{\epsilon^{2}(1-\gamma)^{3}}{\beta_{4}},\frac{(1-\gamma)^{2}}{\bar{d}\beta_{5}},\frac{\epsilon(1-\gamma)^{3}}{\sqrt{\bar{d}}\beta_{4}}\right)$

Table 2: Parameter constraints (first 3 rows) and choice for $<\epsilon$ error
(last 3 rows) for our algorithms. Here the poly-log factors $\beta_{i}$ are
given by
$\beta_{1}=\log\bigr{(}\tfrac{1}{(1-\gamma)\min(\epsilon,1)}\bigr{)}$,
$\beta_{3}=\log\bigr{(}\tfrac{1}{(1-\gamma)\delta\min(\epsilon,1)}\bigr{)}$,
$\beta_{2}=\log(\kappa)+\beta_{3}$,
$\beta_{4}=\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}$,
$\beta_{5}=\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}$.

We first consider the performance of Q-Rex with data derived from a linear MDP
(Defintion 1) or a ZIBEL MDP (Definition 2) and satisfying the Assumptions in
Section 2.1.

######  Theorem 1 (ZIBEL /Linear MDP).

Suppose we run Q-Rex using Option I with data from an MDP with
$\mathsf{IBE}=0$. There exists constants $C_{1},C_{2},C_{3},C_{4},C_{5}>0$
such that whenever the parameter bounds given in Table 2 (row 1) are
satisfied, then with probability at-least $1-\delta$, we must have:

$\displaystyle\|Q^{K+1,1}_{1}-Q^{*}\|_{\infty}$
$\displaystyle\leq\tfrac{\gamma^{K}}{1-\gamma}+C_{4}\sqrt{\tfrac{K\kappa}{\delta(1-\gamma)^{4}}}\exp\left(-\tfrac{\eta
NB}{\kappa}\right)+C_{5}\sqrt{\tfrac{\eta\left[C_{\Phi}^{2}+\log\left(\tfrac{K}{\delta}\right)\right]}{(1-\gamma)^{4}}}$

Given $\epsilon\in(0,\tfrac{1}{(1-\gamma)}]$, and the parameters as given in
Table 2 (row 4)(up to constant factors), then with probability at-least
$1-\delta$: $\|Q^{K+1,1}_{1}(s,a)-Q^{*}(s,a)\|_{\infty}<\epsilon$. This has a
sample complexity

$\Theta(NKB)=\tilde{O}\left(\kappa\max\left(\tfrac{C_{\Phi}^{2}+1}{(1-\gamma)^{5}\epsilon^{2}},\tfrac{\tau_{\mathsf{mix}}}{1-\gamma}\right)\right)$

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:

  1. 1.

To the best of our knowledge, Theorem 1 presents the first non-asymptotic
convergence results for Q-learning based methods for ZIBEL MDPs (or 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 $\tau_{\mathsf{mix}}$ in the sample
complexity is also independent of $d$, but this ‘burn in’ type dependence
might be sub-optimal.

  2. 2.

Even though we have considered the ZIBEL case (i.e, $\mathsf{IBE}=0$), we can
extend this analysis to MDPs with small inherent Bellman error under linear
approximation i.e, $\mathsf{IBE}\leq\zeta\in\mathbb{R}^{+}$. In this case, a
simple extension of the methods established in this work would show that under
the conditions of Theorem 1 for $\epsilon$ error, we must have
$\|Q^{K+1,1}_{1}-Q^{*}\|_{\infty}<\epsilon+\tilde{O}\left(\frac{\kappa\zeta}{1-\gamma}\right)$.
We omit this extension for the sake of clarity.

######  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 $C_{1},\dots,C_{5}$, we obtain with probability at-
least $1-\delta$:

$\|Q^{K+1}-Q^{*}\|_{\infty}<C_{5}\left[\tfrac{\gamma^{L}}{1-\gamma}+\tfrac{\exp\bigr{(}-\tfrac{\eta\mu_{\min}NB}{2}\bigr{)}}{(1-\gamma)^{2}}+\tfrac{\eta\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}{(1-\gamma)^{3}}+\sqrt{\tfrac{\eta\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}{(1-\gamma)^{3}}}\right]$

Where $L=\tfrac{b_{1}K}{\log{\tfrac{1}{1-\gamma}}}$. Given
$\epsilon\in(0,\frac{1}{1-\gamma}]$, and the parameters are picked as given in
Table 2 (row 5), then with probability at-least $1-\delta$, we have:
$\|Q^{K+1}-Q^{*}\|_{\infty}<\epsilon\,.$ This gives us a sample complexity of

$\Theta(NKB)=\tilde{O}\left(\tfrac{1}{\mu_{\min}}\max\left(\tfrac{1}{(1-\gamma)^{4}\min(\epsilon,\epsilon^{2})},\tfrac{\tau_{\mathsf{mix}}}{1-\gamma}\right)\right)\,.$

The sample complexity provided in Theorem 2 matches the sample complexity of
_synchronous_ Q-learning 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 $\frac{1}{(1-\gamma)^{3}}$ instead of
$\frac{1}{(1-\gamma)^{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(\cdot|s,a)$ is bounded in most problems of practical interest. Consider the
following assumption:

######  Assumption 5.

Tabular MDP is such that
$|\mathsf{supp}(P(\cdot|s,a))|\leq\bar{d}\in\mathbb{N}$. This holds for every
tabular MDP with $\bar{d}=|\mathcal{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 $C_{1},C_{2},C_{3},C_{4}$ such
that when the parameter values satisfy the bounds in Table 2 (row 3), with
probability at-least $1-\delta$:

$\displaystyle\|Q^{K+1,1}_{1}-Q^{*}\|_{\infty}$ $\displaystyle\leq
C\left[\tfrac{\exp\bigr{(}-\tfrac{\eta\mu_{\min}NB}{2}\bigr{)}+\gamma^{K}}{(1-\gamma)^{2}}+\tfrac{\eta\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}}{(1-\gamma)^{3}}\sqrt{\bar{d}}+\sqrt{\tfrac{\eta}{(1-\gamma)^{3}}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\right]$

Suppose $\epsilon\in(0,\frac{1}{1-\gamma}]$. If we choose the parameters as
per Table 2 (row 6), then with probability at-least $1-\delta$ we have:
$\|Q^{K+1}(s,a)-Q^{*}\|_{\infty}<\epsilon$. The sample complexity in this case
is

$\Theta(NB)=\tilde{O}\left(\tfrac{1}{\mu_{min}}\max\left(\tau_{\mathsf{mix}},\tfrac{1}{\epsilon^{2}(1-\gamma)^{3}},\tfrac{\bar{d}}{(1-\gamma)^{2}},\tfrac{\sqrt{\bar{d}}}{\epsilon(1-\gamma)^{3}}\right)\right).$

Remarks: Theorem 3 obtains near-optimal sample complexity with respect to
$\gamma$. Here again the ‘burn in’ type dependency on $\tau_{mix}$, which
might be sub-optimal, is due to the data being sampled from a Markovian
trajectory.

##  5 Overview of the Analysis

We divide the analysis of Q-Rex and Q-RexDaRe into two parts: Analysis of
$w^{k,1}_{1}$ 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 $w^{k+1,1}_{1}$ such that $\langle
w^{k+1,1}_{1},\phi(s,a)\rangle\approx R(s,a)+\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\sup_{a^{\prime}}\langle
w^{k,1}_{1},\phi(s^{\prime},a^{\prime})\rangle$. Therefore, we write
$w^{k+1,1}_{1}=\mathcal{T}(w^{k,1}_{1})+\epsilon_{k}(w^{k,1}_{1})$, where
$\mathcal{T}$ is the $\gamma$ contractive Bellman operator whose unique fixed
point is $w^{*}$ and $\epsilon_{k}$ is the noise to be controlled. Following a
similar setting in in (Jain et al., 2021b), we control $\epsilon_{k}$ with the
following steps:
(1) We introduce a fictitious coupled process (see Section C)
$(\tilde{s}_{t},\tilde{a}_{t},\tilde{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
$\epsilon_{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 $\epsilon_{k}$ is small enough. RER plays a key role in controlling
the variance term by endowing it with a super-martingale structure, which is
not possible with forward order traversal (see Theorem 4).

The procedure described above allows us to show that
$w^{k+1,1}_{1}\approx\mathcal{T}(w^{k,1}_{1})$ uniformly for $k\leq K$, which
directly gives us a convergence bound to the fixed point of $\mathcal{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 outer-loop iteration 1 in all future outer-loop
iterations $k>1$, $\epsilon_{k}(w^{k,1}_{1})$ might not be small since
$w^{k,1}_{1}$ depends on $\epsilon_{k}(\cdot)$. However, $(w^{k,1}_{1})_{k}$
approximates the deterministic path of the noiseless Bellman iterates:
$\bar{w}^{1,1}_{1}:=w^{1,1}_{1}$ and
$\bar{w}^{k+1,1}_{1}:=\mathcal{T}(\bar{w}^{k,1}_{1})$. Since
$\|\epsilon_{k}(w^{k,1}_{1})\|_{\infty}\leq\|\epsilon^{k}(w^{k,1}_{1})-\epsilon^{k}(\bar{w}^{k,1}_{1})\|_{\infty}+\|\epsilon^{k}(\bar{w}^{k,1}_{1})\|_{\infty}$,
we argue inductively that
$\|\epsilon^{k}(w^{k,1}_{1})-\epsilon^{k}(\bar{w}^{k,1}_{1})\|_{\infty}\approx
0$ since $w^{k,1}_{1}\approx\bar{w}^{k,1}_{1}$ and
$\|\epsilon^{k}(\bar{w}^{k,1}_{1})\|_{\infty}\approx 0$ since
$\bar{w}^{k,1}_{1}$ is a deterministic sequence and hence
$w^{k+1,1}_{1}\approx\bar{w}^{k+1,1}_{1}$.

##  6 Discussion

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 these results to the most general setting of (Carvalho et al., 2020;
Maei et al., 2010) where linear approximation maybe highly misspecified, which
often leads to instability of the algorithm. 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).

#### Acknowledgments

D.N. was supported in part by NSF grant DMS-2022448 and 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 error setting, and providing intuition that our technique
might be applicable in this more general setting (than linear MDP) as well.

## References

  * Agarwal et al. (2020) Alekh Agarwal, Sham Kakade, and Lin F Yang.  Model-based reinforcement learning with a generative model is minimax optimal.  In _Conference on Learning Theory_ , pp. 67–83. PMLR, 2020.
  * Azar et al. (2013) Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen.  Minimax pac bounds on the sample complexity of reinforcement learning with a generative model.  _Machine learning_ , 91(3):325–349, 2013.
  * Baird (1995) Leemon Baird.  Residual algorithms: Reinforcement learning with function approximation.  In _Machine Learning Proceedings 1995_ , pp. 30–37. Elsevier, 1995\.
  * Beck & Srikant (2012) Carolyn L Beck and Rayadurgam Srikant.  Error bounds for constant step-size q-learning.  _Systems & control letters_, 61(12):1203–1208, 2012.
  * Bertsekas (2011) Dimitri P Bertsekas.  Dynamic programming and optimal control 3rd edition, volume ii.  _Belmont, MA: Athena Scientific_ , 2011.
  * Bhandari et al. (2018) 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\.
  * Borkar & Meyn (2000) 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.
  * Boyan & Moore (1995) Justin Boyan and Andrew W Moore.  Generalization in reinforcement learning: Safely approximating the value function.  _Advances in neural information processing systems_ , pp. 369–376, 1995.
  * Bresler et al. (2020) Guy Bresler, Prateek Jain, Dheeraj Nagaraj, Praneeth Netrapalli, and Xian Wu.  Least squares regression with markovian data: Fundamental limits and algorithms.  _arXiv preprint arXiv:2006.08916_ , 2020.
  * Cai et al. (2019) Qi Cai, Zhuoran Yang, Jason Lee, and Zhaoran Wang.  Neural temporal-difference learning converges to global optima.  2019\.
  * Carvalho et al. (2020) Diogo Carvalho, Francisco S. Melo, and Pedro Santos.  A new convergent variant of q-learning with linear function approximation.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 19412–19421. Curran Associates, Inc., 2020.  URL https://proceedings.neurips.cc/paper/2020/file/e1696007be4eefb81b1a1d39ce48681b-Paper.pdf.
  * Chen et al. (2019) Zaiwei Chen, Sheng Zhang, Thinh T Doan, John-Paul Clarke, and Siva Theja Maguluri.  Finite-sample analysis of nonlinear stochastic approximation with applications in reinforcement learning.  _arXiv preprint arXiv:1905.11425_ , 2019.
  * Chen et al. (2020) Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam.  Finite-sample analysis of contractive stochastic approximation using smooth convex envelopes.  _arXiv preprint arXiv:2002.00874_ , 2020.
  * Dalal et al. (2018a) 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_ , 2018a.
  * Dalal et al. (2018b) 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 75 of _Proceedings of Machine Learning Research_ , pp. 1199–1233. PMLR, 06–09 Jul 2018b.  URL https://proceedings.mlr.press/v75/dalal18a.html.
  * Doan et al. (2020) Thinh T Doan, Lam M Nguyen, Nhan H Pham, and Justin Romberg.  Convergence rates of accelerated markov gradient descent with applications in reinforcement learning.  _arXiv preprint arXiv:2002.02873_ , 2020.
  * Even-Dar et al. (2003) Eyal Even-Dar, Yishay Mansour, and Peter Bartlett.  Learning rates for q-learning.  _Journal of machine learning Research_ , 5(1), 2003.
  * Fan et al. (2020) Jianqing Fan, Zhaoran Wang, Yuchen Xie, and Zhuoran Yang.  A theoretical analysis of deep q-learning.  In _Learning for Dynamics and Control_ , pp. 486–489. PMLR, 2020\.
  * Freedman (1975) David A Freedman.  On tail probabilities for martingales.  _the Annals of Probability_ , pp. 100–118, 1975.
  * Ghavamzadeh et al. (2011) Mohammad Ghavamzadeh, Hilbert Kappen, Mohammad Azar, and Rémi Munos.  Speedy q-learning.  _Advances in neural information processing systems_ , 24:2411–2419, 2011.
  * Goldstein (1979) Sheldon Goldstein.  Maximal coupling.  _Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete_ , 46(2):193–204, 1979.
  * Gupta et al. (2019) Harsh Gupta, R. Srikant, and Lei Ying.  Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/e354fd90b2d5c777bfec87a352a18976-Paper.pdf.
  * Jain et al. (2021a) Prateek Jain, Suhas S Kowshik, Dheeraj Nagaraj, and Praneeth Netrapalli.  Near-optimal offline and streaming algorithms for learning non-linear dynamical systems.  _arXiv preprint arXiv:2105.11558_ , 2021a.
  * Jain et al. (2021b) Prateek Jain, Suhas S Kowshik, Dheeraj Nagaraj, and Praneeth Netrapalli.  Streaming linear system identification with reverse experience replay.  _arXiv preprint arXiv:2103.05896_ , 2021b.
  * Jin et al. (2020) Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pp. 2137–2143. PMLR, 2020\.
  * Kearns & Singh (1999) 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.
  * Li et al. (2020a) 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.
  * Li et al. (2020b) Gen Li, Yuting Wei, Yuejie Chi, Yuantao Gu, and Yuxin Chen.  Sample complexity of asynchronous q-learning: Sharper analysis and variance reduction.  In H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin (eds.), _Advances in Neural Information Processing Systems_ , volume 33, pp. 7031–7043. Curran Associates, Inc., 2020b.  URL https://proceedings.neurips.cc/paper/2020/file/4eab60e55fe4c7dd567a0be28016bff3-Paper.pdf.
  * Li et al. (2021) Gen Li, Changxiao Cai, Yuxin Chen, Yuantao Gu, Yuting Wei, and Yuejie Chi.  Is q-learning minimax optimal? a tight sample complexity analysis.  _arXiv preprint arXiv:2102.06548_ , 2021.
  * Lin (1992) Long-Ji Lin.  Self-improving reactive agents based on reinforcement learning, planning and teaching.  _Machine learning_ , 8(3-4):293–321, 1992.
  * Maei et al. (2010) 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 Conference on International Conference on Machine Learning_ , ICML’10, pp. 719–726. Omnipress, 2010.  ISBN 9781605589077.
  * Mnih et al. (2015) Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Marc G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al.  Human-level control through deep reinforcement learning.  _nature_ , 518(7540):529–533, 2015.
  * Munos & Szepesvári (2008) Rémi Munos and Csaba Szepesvári.  Finite-time bounds for fitted value iteration.  _Journal of Machine Learning Research_ , 9(5), 2008.
  * Paulin (2015) Daniel Paulin.  Concentration inequalities for markov chains by marton couplings and spectral methods.  _Electronic Journal of Probability_ , 20:1–32, 2015.
  * Qu & Wierman (2020) Guannan Qu and Adam Wierman.  Finite-time analysis of asynchronous stochastic approximation and $q$-learning.  In _Conference on Learning Theory_ , pp. 3185–3205. PMLR, 2020\.
  * Riedmiller (2005) Martin Riedmiller.  Neural fitted q iteration–first experiences with a data efficient neural reinforcement learning method.  In _European conference on machine learning_ , pp. 317–328. Springer, 2005.
  * Rotinov (2019) Egor Rotinov.  Reverse experience replay.  _arXiv preprint arXiv:1910.08780_ , 2019.
  * Srikant & Ying (2019) Rayadurgam Srikant and Lei Ying.  Finite-time error bounds for linear stochastic approximation andtd learning.  In _Conference on Learning Theory_ , pp. 2803–2830. PMLR, 2019\.
  * Sutton (1988) Richard S Sutton.  Learning to predict by the methods of temporal differences.  _Machine learning_ , 3(1):9–44, 1988.
  * Sutton & Barto (2018) Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Szepesvári & Smart (2004) Csaba Szepesvári and William D Smart.  Interpolation-based q-learning.  In _Proceedings of the twenty-first international conference on Machine learning_ , pp. 100, 2004.
  * Tsitsiklis & Van Roy (1996) John N Tsitsiklis and Benjamin Van Roy.  Feature-based methods for large scale dynamic programming.  _Machine Learning_ , 22(1):59–94, 1996.
  * Tsitsiklis & Van Roy (1997) John N Tsitsiklis and Benjamin Van Roy.  An analysis of temporal-difference learning with function approximation.  _IEEE transactions on automatic control_ , 42(5):674–690, 1997.
  * Vershynin (2018) Roman Vershynin.  _High-dimensional probability: An introduction with applications in data science_ , volume 47.  Cambridge university press, 2018.
  * Wainwright (2019a) Martin J Wainwright.  Stochastic approximation with cone-contractive operators: Sharp $\ell_{\infty}$-bounds for $q$-learning.  _arXiv preprint arXiv:1905.06265_ , 2019a.
  * Wainwright (2019b) Martin J Wainwright.  Variance-reduced $q$-learning is minimax optimal.  _arXiv preprint arXiv:1906.04697_ , 2019b.
  * Watkins & Dayan (1992) Christopher JCH Watkins and Peter Dayan.  Q-learning.  _Machine learning_ , 8(3-4):279–292, 1992.
  * Watkins (1989) Christopher John Cornish Hellaby Watkins.  Learning from delayed rewards.  1989\.
  * Weng et al. (2020) Bowen Weng, Huaqing Xiong, Lin Zhao, Yingbin Liang, and Wei Zhang.  Momentum q-learning with finite-sample convergence guarantee.  _arXiv preprint arXiv:2007.15418_ , 2020.
  * Xu & Gu (2020) Pan Xu and Quanquan Gu.  A finite-time analysis of q-learning with neural network function approximation.  In _International Conference on Machine Learning_ , pp. 10555–10565. PMLR, 2020.
  * Yang & Wang (2019) 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.
  * Zanette et al. (2020) Andrea Zanette, Alessandro Lazaric, Mykel Kochenderfer, and Emma Brunskill.  Learning near optimal policies with low inherent bellman error.  In _International Conference on Machine Learning_ , pp. 10978–10989. PMLR, 2020.
  * Zou et al. (2019) Shaofeng Zou, Tengyu Xu, and Yingbin Liang.  Finite-sample analysis for sarsa with linear function approximation.  In H. Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché-Buc, E. Fox, and R. Garnett (eds.), _Advances in Neural Information Processing Systems_ , volume 32. Curran Associates, Inc., 2019.  URL https://proceedings.neurips.cc/paper/2019/file/9f9e8cba3700df6a947a8cf91035ab84-Paper.pdf.

##  Appendix 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 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 5, we note that the bias decay for EpiQ-Rex
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\times 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 5 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\times 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 $\mathsf{unif}[-0.5,0.5]$ noise to
all rewards to make the problem harder. We run the grid world experiment with
the discount factor $\gamma=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 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 5.

Figure 2: Mountain Car problem

Figure 3: Grid-world problem

Figure 4: 100 State Random Walk

Figure 5: Linear System Problem

##### Baird’s Counter-Example

Consider the famous Baird’s counter-example shown in Figure 7. 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 vector $w$. In the
experiment, we set the problem and algorithmic parameters to be $\gamma=0.99$
and $\eta=0.01/\sqrt{5}$ (the factor of $\sqrt{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.

Figure 6: Feature embedding in the modified Baird’s counter-example;
$\vec{e_{i}}$ represents the $i$-th canonical basis vector in
$\mathbb{R}^{7}$. Each transition shown occurs with probability $1$.

Figure 7: Performance of vanilla Q-learning as compared to OTL+Q-learning,
averaged over 10 independent runs

##### 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 $X_{0}\in\mathbb{R}^{d}$. The state evolves as
$X_{t+1}=AX_{t}+\eta_{t}$, where $A\in\mathbb{R}^{d\times d}$. The reward
obtained for such transition is given by $\langle X_{t},\,\theta\rangle$ for a
fixed $\theta\in\mathbb{R}^{d}$. The maximum singular value of $A$ is chosen
less than $1$ to ensure that the system is stable. The infinite horizon
$\gamma$-discounted expected reward is given by $\langle
X_{0},\sum_{i=0}^{\infty}(\gamma A^{T})^{i}\theta\rangle$. Thus, the expected
reward can be written as $\langle X_{0},w^{*}\rangle$, where

$w^{*}=(I-\gamma A^{T})^{-1}\theta.$

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 $\phi(X_{t})=X_{t}$, the identity mapping. We considered $d=5$,
$\gamma=0.99$, $\eta=0.01$, and a randomly generated normal matrix $A$ and
$\theta$. We Option II for Q-Rex along with $B=75$, $u=25$, and $N=5$ for the
experiments. For OTL+ER+Q-learning, 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.

##  Appendix 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 2 Q-RexDaRe

1:Input: learning rates $\eta$, horizon $T$, discount factor $\gamma$,
trajectory $X_{t}=\\{s_{t},a_{t},r_{t}\\}$, number of outer-loops $K$ buffer
size $B$, buffer gap $u$

2:Total buffer size: $S\leftarrow B+u$

3:Number of buffers loops: $N\leftarrow T/S$

4:$w_{1}^{1,1}=0$ initialization

5:for $k=1,\ldots,K$ do

6: for $j=1,\ldots,N$ do

7: Form buffer $\textsf{Buf}=\\{X^{k,j}_{1},\dots,X^{k,j}_{S}\\}$, where,
$X^{k,j}_{i}\leftarrow X_{S(j-1)+i}$

8: Define for all $i\in[1,S]$,
$\phi_{i}^{k,j}\triangleq\phi(s_{i}^{k,j},a_{i}^{k,j})$.

9: for $i=1,\ldots,B$ do

10:
$w_{i+1}^{k,j}=w_{i}^{k,j}+\eta\left[r_{B+1-i}^{k,j}+\gamma\max_{a^{\prime}\in\mathcal{A}}\langle\phi(s_{B+2-i}^{k,j},a^{\prime}),w_{1}^{k,1}\rangle-\langle\phi_{B+1-i}^{k,j},w_{i}^{k,j}\rangle\right]\phi_{B+1-i}^{k,j}$

11: $w^{k,j+1}_{1}=w^{k,j}_{B+1}$

12: $w^{k+1,1}_{1}=w^{k,N+1}_{1}$

13:Return $w^{T+1}_{0}$

###  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 to inherent randomness.
We do not require a gap here since separate episodes are assumed to be
independent.

Algorithm 3 EpiQ-Rex

1:Input: learning rates $\eta$, number of episodes $T$, discount factor
$\gamma$, Epsiodes
$E_{t}=\\{(s^{t}_{1},a^{t}_{1},r^{t}_{1}),\dots,(s^{y}_{B_{t}},a^{t}_{B_{t}},r^{t}_{B_{t}})\\}$,
Number of buffer per outer-loop iteration N.

2:Number of outer loop iterations: $K\leftarrow T/N$

3:$w_{1}^{1,1}=0$ initialization

4:for $k=1,\ldots,K$ do

5: for $j=1,\ldots,N$ do

6: $t\leftarrow(k-1)*N+j$

7: Collect experience and form buffer
$\textsf{Buf}=\\{X^{t}_{1},\dots,X^{t}_{B_{t}}\\}$, where,
$X^{t}_{i}=(s^{t}_{i},a^{t}_{i},r^{t}_{i})$

8: Define for all $i\in[1,B_{t}-1]$,
$\phi_{i}^{k,j}\triangleq\phi(s_{i}^{k,j},a_{i}^{k,j})$.

9: for $i=1,\ldots,B$ do

10:
$w_{i+1}^{k,j}=w_{i}^{k,j}+\eta\left[r_{B_{t}-i}^{k,j}+\gamma\max_{a^{\prime}\in\mathcal{A}}\langle\phi(s_{B_{t}+1-i}^{k,j},a^{\prime}),w_{1}^{k,1}\rangle-\langle\phi_{B_{t}-i}^{k,j},w_{i}^{k,j}\rangle\right]\phi_{B_{t}-i}^{k,j}$

11: Option I: $w^{k,j+1}_{1}=w^{k,j}_{B_{t}}$

12: Option II:$w^{k,j+1}_{1}=\frac{1}{B_{t}-1}\sum_{i=2}^{B_{t}}w^{k,j}_{i}$

13: $w^{k+1,1}_{1}=w^{k,N+1}_{1}$

14:Return $w^{K,1}_{1}$

##### 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($\mathcal{S},\mathcal{A},\gamma,P,r$) where
$\mathcal{S}$ denotes the state space, $\mathcal{A}$ denotes the action space,
$\gamma$ represents the discount factor, $P(s^{\prime}|s,a)$ represents the
probability of transition to state $s^{\prime}$ from the state $s$ on action
$a$. We assume for purely technical reasons that $\mathcal{S}$ and
$\mathcal{A}$ are compact subsets of $\mathbb{R}^{n}$ for some
$n\in\mathbb{N}$). $r$ is a reward process (not to be confused with Markov
Reward Processes i.e, MRP) indexed by
$\mathcal{S}\times\mathcal{A}\times\mathcal{S}$, such that
$r(s,a,s^{\prime})\in[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 $(r_{t})_{t\in\mathbb{N}}$ can be jointly defined over a Polish
probability space. The function $R:\mathcal{S}\times\mathcal{A}\to[0,1]$
represents the deterministic reward $R(s,a)$ obtained on taking action $a$ at
state $s$ and is defined by $R(s,a)=\mathbb{E}\left[\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}r(s,a,s^{\prime})\right]$. Here the expectation is with respect
to both the randomness in the reward process and in state $s^{\prime}$.

Now, given a trajectory, $(s_{t},a_{t})_{t=1}^{T}$, which is independent of
i.i.d sequence of rewards processes $(r_{t})_{t=1}^{T}$. We observe
$(s_{t},a_{t},r_{t}(s_{t},a_{t},s_{t+1}))_{t=1}^{T}$, and we will henceforth
denote $r_{t}(s_{t},a_{t},s_{t+1})$ by just $r_{t}$.

##### 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\in[K]$ and buffer number $j\in[N]$ inside this outer loop. Further given an
$i\in[S]$ define a time index as $t_{i}^{k,j}=NS(k-1)+S(j-1)+i$. We now denote
the $i$-th state-action-reward tuple inside this buffer by

$(s^{k,j}_{i},a^{k,j}_{i},r^{k,j}_{i})=(s_{t_{i}^{k,j}},a_{t_{i}^{k,j}},r_{t_{i}^{k,j}}).$

Similarly, $R^{k,j}_{i}=R(s^{k,j}_{i},a^{k,j}_{i})$. For conciseness, we
define for all $i,j,k$, $\phi^{k,j}_{i}:=\phi(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:

$s^{k,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}\text{
and }\phi^{k,j}_{-i}:=\phi^{k,j}_{B+1-i}.$

##  Appendix C Coupled Process

It can be seen that the buffers are approximately i.i.d. whenever we take
$u=O(\tau_{\mathsf{mix}}\log\tfrac{T}{\delta})$ 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 $(\tilde{s}_{t},\tilde{a}_{t},\tilde{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 $\mu$. We show
that we can couple this fictitious process (i.e, define it on a common
probability space as the original process $(s_{t},a_{t},r_{t})$) such that

$\mathbb{P}\left(\cap_{k=1}^{K}\cap_{j=1}^{N}\cap_{i=1}^{B+1}\\{(s^{k,j}_{i},r^{k,j}_{i},a^{k,j}_{i})=(\tilde{s}^{k,j}_{i},\tilde{r}^{k,j}_{i},\tilde{a}^{k,j}_{i})\\}\right)\geq
1-\delta\,.$ (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
$(s_{t},a_{t},r_{t})$ is the same as the sequence of iterates obtained by
running the algorithm with the fictitious coupled data
$(\tilde{s}_{t},\tilde{a}_{t},\tilde{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
$(\tilde{s}_{t},\tilde{a}_{t},\tilde{r}_{t})$ and refer to Lemma 16 to carry
over the results to the original data set with high probability. We
analogously define $\tilde{\phi}^{k,j}_{i}$. We will denote the iterates of
the algorithm run with the coupled trajectory as $\tilde{w}^{k,j}_{i}$ 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.

##  Appendix D Basic Structural Lemmas

We first note some basic structural lemmas regarding ZIBEL MDPs under the
assumptions in Section 2.1. 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
Q-RexDaRe, we have that for every $k,j,i$ we have that
$\|\tilde{w}^{k,j}_{i}\|_{\phi}\leq\frac{1}{1-\gamma}$

The lemma above says, in particular, that the Q-value estimate given by our
algorithm never exceeds $\frac{1}{1-\gamma}$ 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 $Q_{w}(s,a):=\langle w,\phi(s,a)\rangle$ and let $Q^{*}(s,a)=\langle
w^{*},\phi(s,a)\rangle$ be the optimal $Q$ function. Then:

$\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}|Q_{w}(s,a)-Q^{*}(s,a)|=\|w-w^{*}\|_{\phi}$

Moreover, we must have: $\|x\|\geq\|x\|_{\phi}\geq\frac{\|x\|}{\sqrt{\kappa}}$
for any $x\in\mathbb{R}^{d}$.

######  Lemma 3.

For any $w_{0}\in\mathbb{R}^{d}$, there exists a unique
$w_{1}\in\mathbb{R}^{d}$ such that

$\langle w_{1},\phi(s,a)\rangle=R(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\sup_{a^{\prime}\in
A}\langle\phi(s^{\prime},a^{\prime}),w_{0}\rangle.$

We will denote this mapping $w_{0}\to w_{1}$ by $w_{1}=\mathcal{T}(w_{0})$.

######  Lemma 4.

$\mathcal{T}:\mathbb{R}^{d}\to\mathbb{R}^{d}$ is $\gamma$ contractive in the
norm $\|\cdot\|_{\phi}$. The unique fixed point of $\mathcal{T}$ is $w^{*}$.
Moreover, we have: $\|w^{*}\|_{\phi}\leq\frac{1}{1-\gamma}$ and
$\|w^{*}\|\leq\frac{\sqrt{\kappa}}{1-\gamma}$.

In view of Lemma 4, we can begin to look at the following noiseless
$Q$-iteration. Let $\bar{w}^{1}=w^{1,1}_{1}=0$ and
$\bar{w}^{k+1}=\mathcal{T}(\bar{w}^{k})$. This converges geometrically to
$w^{*}$ with contraction coefficient $\gamma$ under the norm
$\|\cdot\|_{\phi}$. In our case, however, we only have sample access to the
operator $\mathcal{T}$. Therefore, our Q-iteration at the end of $k$-th outer
loop can be written as
$\tilde{w}^{k+1,1}_{1}=\mathcal{T}(\tilde{w}^{k,1}_{1})+\tilde{\epsilon}_{k}$
where $\tilde{\epsilon}_{k}$ is the error introduced via sampling which needs
to be controlled.

##  Appendix E Bias Variance Decomposition

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 $\eta$, outer loop index $k$ and buffer index $j$, we define
the following contraction matrices for $a,b\in[B]$.

$\tilde{H}_{a,b}^{k,j}:=\prod_{i=a}^{b}\left(I-\eta\tilde{\phi}^{k,j}_{i}[\tilde{\phi}^{k,j}_{i}]^{\top}\right)\,.$
(5)

Whenever $a>b$, we will define $\tilde{H}^{k,j}_{a,b}:=I$. In the tabular
setting, we define for any $(s,a)\in\mathcal{S}\times\mathcal{A}$ by
$\tilde{N}^{k}(s,a)$ to be the number of samples of $(s,a)$ seen in the outer
loop k (excluding the gaps),i.e.

$\tilde{N}^{k}(s,a)=\sum_{j=1}^{N}\sum_{i=1}^{B}\mathbbm{1}((\tilde{s}^{k,j}_{i},\tilde{a}^{k,j}_{i})=(s,a))$

Further we denote by $\tilde{N}^{k,j}_{i}(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,

$\tilde{N}^{k,j}_{i}(s,a):=\sum_{r=1}^{i-1}\mathbbm{1}\left((\tilde{s}^{k,j}_{r},\tilde{a}^{k,j}_{r})=(s,a)\right)+\sum_{l=j+1}^{N}\sum_{r=1}^{B}\mathbbm{1}\left((\tilde{s}^{k,l}_{r},\tilde{a}^{k,l}_{r})=(s,a)\right)\,.$

We define the error term for any $w$:

$\tilde{\epsilon}^{k,j}_{i}(w):=\left[\tilde{r}^{k,j}_{i}-\tilde{R}^{k,j}_{i}+\gamma\sup_{a^{\prime}\in\mathcal{A}}\langle
w,\phi(\tilde{s}^{k,j}_{i+1},a^{\prime})\rangle-\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|\tilde{s}^{k,j}_{i},\tilde{a}^{k,j}_{i})}\sup_{a^{\prime}\in
A}\langle\phi(s^{\prime},a^{\prime}),w\rangle\right]\,.$ (6)

Finally we define the following shorthands for any $i,j,k$:

$\tilde{w}^{k+1,*}:=\mathcal{T}(\tilde{w}^{k,1}_{1})\qquad\tilde{\epsilon}^{k,j}_{i}:=\tilde{\epsilon}^{k,j}_{i}(\tilde{w}^{k,1}_{1})\qquad\tilde{L}^{k,j}:=\eta\sum_{i=1}^{B}\tilde{\epsilon}^{k,j}_{i}\tilde{H}^{k,j}_{1,i-1}\tilde{\phi}^{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,

$\tilde{\epsilon}_{k}:=\tilde{w}^{k+1,1}_{1}-\tilde{w}^{k+1,*}=\prod_{j=N}^{1}\tilde{H}^{k,j}_{1,B}(\tilde{w}^{k,1}_{1}-\tilde{w}^{k+1,*})+\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{k,l}_{1,B}\tilde{L}^{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 $\tilde{H}^{k,l}_{1,B}$
appear towards the left side of the product and further define
$\prod_{l=N}^{N+1}\tilde{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.

##  Appendix 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:

$\langle\phi(s,a),\prod_{j=N}^{1}\tilde{H}^{k,j}_{1,B}(\tilde{w}^{k,1}_{1}-\tilde{w}^{k+1,*})\rangle=(1-\eta)^{\tilde{N}^{k}(s,a)}\langle\tilde{w}^{k,1}_{1}-\tilde{w}^{k+1,*},\phi(s,a)\rangle$

For a particular outer loop $k$, we show that $\tilde{N}^{k}(s,a)$ is
$\Omega(\mu_{\min}NB)$ 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\geq\tau_{\mathsf{mix}}$ and
$NB\geq
C\frac{\tau_{\mathsf{mix}}}{\mu_{\min}}\log(\tfrac{|\mathcal{S}||\mathcal{A}|}{\delta})$,
with probability at least $1-\delta$, we have that for every
$(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\tilde{N}^{k}(s,a)\geq\tfrac{1}{2}\mu(s,a)NB\geq\tfrac{1}{2}\mu_{\min}NB$

###  F.2 ZIBEL MDP Case

######  Lemma 8.

Suppose $g\in\mathbb{R}^{d}$ is fixed and $\eta B<\frac{1}{4}$. Then, the
following hold:

  1. 1.

$\mathbb{E}\|\prod_{j=N}^{1}\tilde{H}^{k,j}_{1,B}g\|^{2}\leq\exp(-\tfrac{\eta
NB}{\kappa})\|g\|^{2}$ (8)

  2. 2.

With probability at-least $1-\delta$, we have:

$\mathbb{E}\|\prod_{j=N}^{1}\tilde{H}^{k,j}_{1,B}g\|_{\phi}\leq\exp(-\tfrac{\eta
NB}{\kappa})\sqrt{\frac{\kappa}{\delta}}\|g\|_{\phi}$

We refer to Section K.1 for the proof.

##  Appendix G Bounding the Variance Term

###  G.1 Tabular Case

In the tabular case, it is clear that:

$\langle\phi(s,a),\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{k,l}_{1,B}\tilde{L}^{k,j}\rangle=\sum_{j=1}^{N}\sum_{i=1}^{B}(1-\eta)^{\tilde{N}^{k,j}_{i}(s,a)}\eta\tilde{\epsilon}^{k,j}_{i}\mathbbm{1}((\tilde{s}^{k,j}_{i},\tilde{a}^{k,j}_{i})=(s,a))$
(9)

Now, we note that $\tilde{N}^{k,j}_{i}(s,a)$ depends on data in buffers $l>j$
and when $i_{1}<i$ inside buffer $j$. Following the discussion in (Li et al.,
2021), we define the vector
$\mathsf{Var}_{P}(V_{k}),\mathsf{Var}_{P}(V^{*})\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$
such that

$\displaystyle\mathsf{Var}_{P}(V_{k})(s,a)$
$\displaystyle=\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\left[\sup_{a^{\prime}\in
A}\langle\phi(s^{\prime},a^{\prime}),\tilde{w}^{k,1}_{1}\rangle-\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\sup_{a^{\prime}\in
A}\langle\phi(s^{\prime},a^{\prime}),\tilde{w}^{k,1}_{1}\rangle\right]^{2}$
(10)

$\displaystyle\mathsf{Var}_{P}(V^{*})(s,a)$
$\displaystyle=\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\left[\sup_{a^{\prime}\in
A}\langle\phi(s^{\prime},a^{\prime}),w^{*}\rangle-\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\sup_{a^{\prime}\in
A}\langle\phi(s^{\prime},a^{\prime}),w^{*}\rangle\right]^{2}$ (11)

More generally, we define

$\mathsf{Var}_{P}(V)(s,a;w)=\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\left[\sup_{a^{\prime}\in
A}\langle\phi(s^{\prime},a^{\prime}),w\rangle-\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\sup_{a^{\prime}\in
A}\langle\phi(s^{\prime},a^{\prime}),w\rangle\right]^{2}$

Similarly, we define $\tilde{L}^{k,j}(w)$ by replacing $w^{k,1}_{1}$ with any
fixed, arbitrary $w$. It is easy to see that:

$\mathbb{E}\left[|\tilde{\epsilon}^{k,j}_{i}(w)|^{2}\biggr{|}(\tilde{s}^{k,j}_{i},\tilde{a}^{k,j}_{i})=(s,a)\right]\leq
2(1+\gamma^{2}\mathsf{Var}_{P}(V)(s,a;w))$ (12)

######  Lemma 9.

In the tabular setting, suppose $w$ is a fixed vector such that $\langle
w,\phi(s,a)\rangle\in[0,\frac{1}{1-\gamma}]$ for every
$(s,a)\in\mathcal{S}\times\mathcal{A}$. Fix
$(s,a)\in\mathcal{S}\times\mathcal{A}$. Then there exists a universal constant
$C$ such that with probability atleast $1-\delta$, we have that:

Then,

$\biggr{|}\langle\phi(s,a),\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{k,l}_{1,B}\tilde{L}^{k,j}(w)\rangle\biggr{|}\leq
C\sqrt{\eta\log(2/\delta)(1+\gamma^{2}\mathsf{Var}_{P}(V)(s,a;w))}+C\frac{\eta\log(2/\delta)}{1-\gamma}$

###  G.2 ZIBEL MDP Case

We will use an appropriate exponential super-martingale to 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 to Section
K.3 for its proof.

######  Theorem 4.

Suppose $x,w\in\mathbb{R}^{d}$ are fixed. Then, there exists a universal
constant $C$ such that with probability at least $1-\delta$, we have:

$\biggr{|}\langle
x,\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{k,l}_{1,B}\tilde{L}^{k,j}(w)\rangle\biggr{|}\leq
C\|x\|\left(1+\|w\|_{\phi}\right)\sqrt{\eta\log(2/\delta)}\,.$ (13)

By a direct application of (Vershynin, 2018, Theorem 8.1.6), we derive the
following corollary. We remind the reader that $C_{\Phi}$ is the covering
number defined in Definition 3.

######  Corollary 1.

Suppose $x,w\in\mathbb{R}^{d}$ are fixed. Then, there exists a universal
constant $C$ such that with probability at least $1-\delta$, we have:

$\biggr{\|}\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{k,l}_{1,B}\tilde{L}^{k,j}(w)\biggr{\|}_{\phi}\leq
C(1+\|w\|_{\phi})\sqrt{\eta}\left[C_{\Phi}+\sqrt{\log(\tfrac{2}{\delta})}\right]\,.$

In order to apply the theorem above, we will need to control
$\|w^{k,1}_{1}\|_{\phi}$ uniformly for all $k$. The following lemma presents
such a bound and we refer to Section K.4 for the proof.

######  Lemma 10.

Suppose $\tilde{w}^{k,1}_{1}$ are the iterates of Q-Rex with coupled data from
a ZIBEL MDP. There exist universal constants $C,C_{1},C_{2}$ such that
whenever
$NB>C_{1}\frac{\kappa}{\eta}\log\left(\frac{K\kappa}{\delta(1-\gamma)}\right)$,
$\eta<C_{2}\frac{(1-\gamma)^{2}}{C_{\phi}^{2}+\log(K/\delta)}$ and $\eta
B<\frac{1}{4}$, with probability at-least $1-\delta$, the following hold:

  1. 1.

For every $1\leq k\leq K$,
$\|\tilde{w}^{k,1}_{1}\|_{\phi}\leq\frac{4}{1-\gamma}$

  2. 2.

For every $1\leq k\leq K$,
$\|\tilde{\epsilon}_{k}\|_{\phi}\leq\sqrt{\frac{25K\kappa}{\delta(1-\gamma)^{2}}}\exp(-\tfrac{\eta
NB}{\kappa})+\frac{C\sqrt{\eta}}{(1-\gamma)}\left[C_{\Phi}+\sqrt{\log(\tfrac{2K}{\delta})}\right]$

##  Appendix H Proof of Theorem 1

###### Proof.

Consider the Q learning iteration:

$\tilde{w}^{k+1,1}_{1}=\mathcal{T}(\tilde{w}^{k,1}_{1})+\tilde{\epsilon}_{k}\,.$

Using Lemma 4, we conclude:
$\tilde{w}^{k+1,1}_{1}-w^{*}=\mathcal{T}(\tilde{w}^{k,1}_{1})-\mathcal{T}(w^{*})+\epsilon_{k}$
and thence:

$\|\tilde{w}^{k+1,1}_{1}-w^{*}\|_{\phi}\leq\gamma\|\tilde{w}^{k,1}_{1}-w^{*}\|_{\phi}+\sup_{l\leq
K}\|\epsilon_{l}\|_{\phi}\,.$

Unrolling the recursion above, we conclude:

$\|\tilde{w}^{K+1,1}_{1}-w^{*}\|_{\phi}\leq\gamma^{K}\|w^{*}\|_{\phi}+\frac{\sup_{l\leq
K}\|\epsilon_{l}\|_{\phi}}{1-\gamma}$

Now, we invoke item 2 of Lemma 10 along with the constraints on $N,B,K,\eta$
and Lemma 2 to conclude the result.

∎

##  Appendix I Proof of Theorem 2

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$,
$\tilde{Q}^{k,1}_{1}\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ and we have
that $\tilde{Q}^{k,1}_{1}(s,a)=\langle\tilde{w}^{k,1}_{1},\phi(s,a)\rangle$.
Since $\phi(s,a)$ are the standard basis vectors, we must have
$\tilde{Q}^{k,1}_{1}=\tilde{w}^{k,1}_{1}$. In the tabular setting, we see by
using Lemmas 5, 6, 7, and 9 that for any $\delta>0$, there exists a universal
constant $C$, whenever $NB\geq
C\frac{\tau_{\mathsf{mix}}}{\mu_{\min}}\log(\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta})$,
with probability at-least $1-\delta$, for every $k\in[K]$ and every
$(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\tilde{Q}^{k+1,1}_{1}=\mathcal{T}\left[\tilde{Q}^{k,1}_{1}\right]+\tilde{\epsilon}_{k}\,,$
(14)

where $\tilde{\epsilon}_{k}\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$ is
such that for all $(s,a)$,

$\displaystyle|\tilde{\epsilon}_{k}(s,a)|$ $\displaystyle\leq
C\sqrt{\eta\log\left(\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\right)(1+\gamma^{2}\mathsf{Var}_{P}(V)(s,a;\tilde{Q}^{k,1}_{1}))}+C\frac{\eta\log(\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta})}{1-\gamma}$
$\displaystyle\quad+(1-\eta)^{\tfrac{\mu_{\min}NB}{2}}\biggr{\|}\tilde{Q}^{k,1}_{1}-\mathcal{T}\left[\tilde{Q}^{k,1}_{1}\right]\biggr{\|}_{\infty}\,.$
(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
$\tilde{Q}^{1,1}_{1}=0$, and $r_{t}\in[0,1]$ almost surely, we can easily show
that $\tilde{Q}^{k,1}_{1}(s,a)\in[0,\tfrac{1}{1-\gamma}]$ for every $k,s,a$.
Therefore, we upper bound
$\biggr{\|}\tilde{Q}^{k,1}_{1}-\mathcal{T}\left[\tilde{Q}^{k,1}_{1}\right]\biggr{\|}_{\infty}\leq\frac{1}{1-\gamma}$
in Equation (15) to conclude that with probability at-least $1-\delta$, for
every $k\in[K]$ and every $(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle|\tilde{\epsilon}_{k}(s,a)|$ $\displaystyle\leq
C\sqrt{\eta\log(\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta})\gamma^{2}\left[\mathsf{Var}_{P}(V_{k})(s,a)\right]}+\alpha_{\eta}$
(16)

Where
$\alpha_{\eta}:=C\frac{\eta\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}{1-\gamma}+C\sqrt{\eta\log\left(\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\right)}+\frac{\exp\bigr{(}-\tfrac{\eta\mu_{\min}NB}{2}\bigr{)}}{1-\gamma}$

Now we define $\Delta_{k}=\tilde{Q}^{k,1}_{1}-Q^{*}$ and
$\pi_{k}:\mathcal{S}\to\mathcal{A}$ to be the deterministic policy given by
$Q^{k,1}_{1}$ i.e,
$\pi_{k}(s):=\arg\sup_{a\in\mathcal{A}}\tilde{Q}^{k,1}_{1}(s,a)$ and $\pi^{*}$
to be optimal policy given by
$\pi^{*}(s):=\arg\sup_{a\in\mathcal{A}}Q^{*}(s,a)$. We use the convention that
we pick a single maximizing action using some rule whenever there are
multiple. Similarly, we let $P^{\pi_{k}},$ to be the Markov transition kernel
over $\mathcal{S}\times\mathcal{A}$ given by
$P^{\pi_{k}}((s,a),(s^{\prime},a^{\prime}))=P(s^{\prime}|s,a)\mathbbm{1}(a^{\prime}=\pi_{k}(s^{\prime}))$.
Similarly, we define $P^{\pi^{*}}$ with respect to the policy $\pi^{*}$. It is
easy to show that:

$\mathcal{T}(\tilde{Q}^{k,1}_{1})=R+\gamma P^{\pi_{k}}\tilde{Q}^{k,1}_{1}\,.$

Similarly,

$Q^{*}=\mathcal{T}(Q^{*})=R+\gamma P^{\pi^{*}}Q^{*}\,.$

Furthermore given any $Q\in\mathbb{R}^{\mathcal{S}\times\mathcal{A}}$, letting
$\pi_{Q}$ being the greedy policy with respect to the function $Q$ we have
that for any policy $\pi$, it can be easily seen from the definitions that
following element-wise inequality follows:

$P^{\pi}Q\leq P^{\pi_{Q}}Q.$

We now use Equation (14) along with the equations above to conclude:

$\gamma P^{\pi^{*}}\Delta_{k}+\tilde{\epsilon}_{k}\leq\Delta_{k+1}\leq\gamma
P^{\pi_{k}}\Delta_{k}+\tilde{\epsilon}_{k}\,.$ (17)

Here, the inequality is assumed to be point-wise. By properties of Markov
transition kernels, we can write:

$\sum_{k=1}^{K}\gamma^{K-k}\left(P^{\pi^{*}}\right)^{K-k}\tilde{\epsilon}_{k}+\gamma^{K}\left(P^{\pi^{*}}\right)^{K}\Delta_{1}\leq\Delta_{K+1}\\\
\leq\sum_{k=1}^{K}\gamma^{K-k}\left(\prod_{l=K}^{k+1}P^{\pi_{l}}\right)\tilde{\epsilon}_{k}+\gamma^{K}\left(\prod_{l=K}^{1}P^{\pi_{l}}\right)\Delta_{1}\,.$
(18)

Here, we use the convention that $\prod_{l=K}^{K+1}P^{\pi_{l}}=I$. We bound
the lower bound and the upper bound given in Equation (18) separately in order
to bound $\|\Delta_{K+1}\|_{\infty}$.

We first consider the lower bound. Using (Azar et al., 2013, Lemma 7), we
have:

$\bigr{\|}(I-\gamma
P^{\pi^{*}})^{-1}\sqrt{\mathsf{Var}_{P}(V^{*})}\bigr{\|}_{\infty}\leq\sqrt{\frac{2}{(1-\gamma)^{3}}}\,.$
(19)

We also note from (Li et al., 2021, Equation 64) and basic calculations that:

$\displaystyle\|\sqrt{\mathsf{Var}_{P}(V_{k})}-\sqrt{\mathsf{Var}_{P}(V^{*})}\|_{\infty}$
$\displaystyle\leq\sqrt{\|\mathsf{Var}_{P}(V_{k})-\mathsf{Var}_{P}(V^{*})\|_{\infty}}$
$\displaystyle\leq\sqrt{\frac{4}{1-\gamma}\|\Delta_{k}\|_{\infty}}\,.$ (20)

Using Equations (15) (16), we conclude that there exist universal constants
$C,C_{1}$ such that with probability at least $1-\delta$ (interpreting the
inequalities as element-wise):

$\displaystyle\Delta_{K+1}$
$\displaystyle\geq-\frac{\alpha_{\eta}+\gamma^{K}}{1-\gamma}-C\sqrt{\eta\gamma^{2}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sum_{k=1}^{K}\gamma^{K-k}\left(P^{\pi^{*}}\right)^{K-k}\sqrt{\mathsf{Var}_{P}(V_{k})}$
$\displaystyle\geq-\frac{\alpha_{\eta}+\gamma^{K}}{1-\gamma}-C\sqrt{\eta\gamma^{2}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sum_{k=1}^{K}\gamma^{K-k}\left(P^{\pi^{*}}\right)^{K-k}\sqrt{\mathsf{Var}_{P}(V^{*})}$
$\displaystyle\quad-
C_{1}\sqrt{\frac{1}{1-\gamma}}\sqrt{\eta\gamma^{2}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sum_{k=1}^{K}\gamma^{K-k}\sqrt{\|\Delta_{k}\|_{\infty}}$
$\displaystyle\geq-\frac{\alpha_{\eta}+\gamma^{K}}{1-\gamma}-C\sqrt{\eta\gamma^{2}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}(I-\gamma
P^{\pi*})^{-1}\sqrt{\mathsf{Var}_{P}(V^{*})}$ $\displaystyle\quad-
C_{1}\sqrt{\frac{1}{1-\gamma}}\sqrt{\eta\gamma^{2}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sum_{k=1}^{K}\gamma^{K-k}\sqrt{\|\Delta_{k}\|_{\infty}}$
$\displaystyle\geq-\frac{\alpha_{\eta}+\gamma^{K}}{1-\gamma}-C\sqrt{\frac{\eta\gamma^{2}}{(1-\gamma)^{3}}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}$
$\displaystyle\quad-
C_{1}\sqrt{\frac{1}{1-\gamma}}\sqrt{\eta\gamma^{2}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sum_{k=1}^{K}\gamma^{K-k}\sqrt{\|\Delta_{k}\|_{\infty}}\,.$
(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-\delta$.

$\displaystyle\Delta_{K+1}$
$\displaystyle\leq\sum_{k=1}^{K}\gamma^{K-k}\left(\prod_{l=K}^{k+1}P^{\pi_{l}}\right)\tilde{\epsilon}_{k}+\gamma^{K}\left(\prod_{l=K}^{1}P^{\pi_{l}}\right)\Delta_{1}$
$\displaystyle\leq\frac{\alpha_{\eta}+\gamma^{K}}{1-\gamma}+C\sqrt{\eta\gamma^{2}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sum_{k=1}^{K}\gamma^{K-k}\left(\prod_{l=K}^{k+1}P^{\pi_{l}}\right)\sqrt{\mathsf{Var}_{P}(V_{k})}$
$\displaystyle\leq\frac{\alpha_{\eta}+\gamma^{K}}{1-\gamma}+C\sqrt{\eta\gamma^{2}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sum_{k=1}^{K}\gamma^{K-k}\sqrt{\left(\prod_{l=K}^{k+1}P^{\pi_{l}}\right)\mathsf{Var}_{P}(V_{k})}$
$\displaystyle=\frac{\alpha_{\eta}+\gamma^{K}}{1-\gamma}+C\sqrt{\eta\gamma^{2}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sum_{k=1}^{K}\gamma^{\tfrac{K-k}{2}}\gamma^{\tfrac{K-k}{2}}\sqrt{\left(\prod_{l=K}^{k+1}P^{\pi_{l}}\right)\mathsf{Var}_{P}(V_{k})}$
$\displaystyle\leq\frac{\alpha_{\eta}+\gamma^{K}}{1-\gamma}+C\sqrt{\eta\gamma^{2}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sqrt{\sum_{k=1}^{K}\gamma^{K-k}}\sqrt{\sum_{k=1}^{K}\gamma^{K-k}\left(\prod_{l=K}^{k+1}P^{\pi_{l}}\right)\mathsf{Var}_{P}(V_{k})}$
$\displaystyle\leq\frac{\alpha_{\eta}+\gamma^{K}}{1-\gamma}+C\sqrt{\frac{\eta\gamma^{2}}{1-\gamma}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sqrt{\sum_{k=1}^{K}\gamma^{K-k}\left(\prod_{l=K}^{k+1}P^{\pi_{l}}\right)\mathsf{Var}_{P}(V_{k})}$
$\displaystyle\leq\frac{\alpha_{\eta}+\gamma^{K}}{1-\gamma}+C\sqrt{\frac{\eta\gamma^{2}}{1-\gamma}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sqrt{\sum_{k=K/2+1}^{K}\gamma^{K-k}\left(\prod_{l=K}^{k+1}P^{\pi_{l}}\right)\mathsf{Var}_{P}(V_{k})+\frac{\gamma^{K/2}}{(1-\gamma)^{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^{\pi}$ is a Markov operator, the
fourth inequality via Cauchy-Schwartz and the last inequality by noting that
that $\|\mathsf{Var}_{P}(V_{k})\|_{\infty}\leq 1/(1-\gamma)^{2}$.

It can now be verified that (Li et al., 2021, Lemma 5) applies in our setting
to conclude that:

$\sum_{k=K/2+1}^{K}\gamma^{K-k}\left(\prod_{l=K}^{k+1}P^{\pi_{l}}\right)\mathsf{Var}_{P}(V_{k})\leq\frac{4}{\gamma^{2}(1-\gamma)^{2}}\left(1+2\max_{K/2+1\leq
k\leq K}\|\Delta_{k}\|_{\infty}\right)\,.$

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-\delta$, we have:

$\|\Delta_{K+1}\|_{\infty}\leq\frac{\alpha_{\eta}+\gamma^{K}}{1-\gamma}+C\sqrt{\frac{\eta}{(1-\gamma)^{3}}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sqrt{1+\max_{K/2+1\leq
k\leq K}\|\Delta_{k}\|_{\infty}+\frac{\gamma^{K/2}}{(1-\gamma)}}$ (23)

We note that this works with every $K$ replaced with $l$ for any $l\leq K$,
importantly under the same event (with probability at least $1-\delta$)
described above for which Equation (23) holds. Define $L=\frac{K}{2^{s}}$ for
some $s=\lceil\log_{2}(1+C\log(\tfrac{1}{1-\gamma}))\rceil$. Under the
conditions of the Theorem, i.e,
$K>C_{2}\frac{1}{(1-\gamma)}\left(\log(\tfrac{1}{1-\gamma})\right)^{2}$, we
have $\frac{\gamma^{L/2}}{1-\gamma}<1$. Therefore we conclude from the
discussion above that for every $K\geq l\geq L$, we must have:

$\displaystyle\|\Delta_{l+1}\|_{\infty}$
$\displaystyle\leq\frac{\alpha_{\eta}+\gamma^{L}}{1-\gamma}+C\sqrt{\frac{\eta}{(1-\gamma)^{3}}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sqrt{1+\max_{l/2+1\leq
k\leq l}\|\Delta_{k}\|_{\infty}}$
$\displaystyle\leq\frac{\alpha_{\eta}+\gamma^{L}}{1-\gamma}+C\sqrt{\frac{\eta\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}{(1-\gamma)^{3}}}+C\sqrt{\frac{\eta\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}{(1-\gamma)^{3}}}\sqrt{\max_{l/2+1\leq
k\leq l}\|\Delta_{k}\|_{\infty}}$ (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 $\alpha,\beta\geq 0$. Consider the function
$f:\mathbb{R}^{+}\to\mathbb{R}^{+}$ given by $f(u)=\alpha+\beta\sqrt{u}$.
Then, $f$ has the unique fixed point:
$u^{*}:=\left(\frac{\beta+\sqrt{\beta^{2}+4\alpha}}{2}\right)^{2}$. For
$t\in\mathbb{N}$, denoting $f^{(t)}$ to be the $t$ fold composition of $f$
with itself, we have for any $u\in\mathbb{R}^{+}$:

$|f^{(t)}(u)-u^{*}|\leq\beta^{(2-\tfrac{1}{2^{t-1}})}|u-u^{*}|^{\tfrac{1}{2^{t}}}\,.$

Now consider for $0\leq a<s$,

$u_{a}:=\sup_{\tfrac{K}{2^{s-a}}\leq l\leq K}\|\Delta_{l+1}\|_{\infty}$

In lemma 11, define $f$ with
$\alpha=\frac{\alpha_{\eta}+\gamma^{L}}{1-\gamma}+C\sqrt{\frac{\eta\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}{(1-\gamma)^{3}}}$
and
$\beta=C\sqrt{\frac{\eta\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}{(1-\gamma)^{3}}}$.
The fixed point $u^{*}$ is such that:

$u^{*}\leq
C\left[\frac{\eta\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}{(1-\gamma)^{3}}+\frac{\alpha_{\eta}+\gamma^{L}}{1-\gamma}+\sqrt{\frac{\eta\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}{(1-\gamma)^{3}}}\right]$
(25)

Clearly, by Equation (24), we have: $u_{a}\leq f(u_{a-1})$ and
$\|\Delta_{K+1}\|\leq f(u_{s-1})$. By monotonicity of $f(\cdot)$ and the fact
that $u_{0}\leq\frac{1}{1-\gamma}$ (Lemma 1):

$u_{s-1}\leq f^{(s-1)}(u_{0})\leq
f^{(s-1)}\left(\tfrac{1}{1-\gamma}\right)\,.$

Therefore,

$\|\Delta_{K+1}\|_{\infty}\leq f(u_{s-1})\leq
f^{(s)}\left(\tfrac{1}{1-\gamma}\right)$

Applying Lemma 11, we conclude:

$\|\Delta_{K+1}\|_{\infty}\leq
u^{*}+\beta^{\left(2-\frac{1}{2^{s-1}}\right)}\bigr{|}\tfrac{1}{1-\gamma}-u^{*}\bigr{|}^{\tfrac{1}{2^{s}}}$
(26)

Note that under the constraints on the parameter $\eta$ and $K$ as stated in
the Theorem, we must have $u^{*}\leq\tfrac{1}{(1-\gamma)^{3}}$. By our choice
of $s$, we must have: $|\frac{1}{(1-\gamma)}-u^{*}|^{\tfrac{1}{2^{s}}}\leq
C^{\prime}$. Using this in Equation 26 and the fact that
$\beta^{\left(2-\frac{1}{2^{s-1}}\right)}\leq\beta+\beta^{2}$, we conclude
that with probability at-least $1-\delta$, we must have:

$\|\Delta_{K+1}\|\leq
C\left[\frac{\eta\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}{(1-\gamma)^{3}}+\frac{\alpha_{\eta}+\gamma^{L}}{1-\gamma}+\sqrt{\frac{\eta\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}{(1-\gamma)^{3}}}\right]$

This proves the first part of the theorem. For the second part, we directly
substitute the values provided to verify that we indeed obtain $\epsilon$
error.

##  Appendix J Proof of Theorem 3

We will now show uniform convergence type result under Assumption 5. For
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and
$s^{\prime}\in\mathsf{supp}(P(\cdot|s,a))$. We define the random variables for
all $k$:

$\begin{gathered}\hat{P}_{k}(s^{\prime}|s,a)=\eta\sum_{j=1}^{N}\sum_{i=1}^{B}(1-\eta)^{\tilde{N}^{k,j}_{i}(s,a)}\mathbbm{1}(\tilde{s}^{k,j}_{i+1}=s^{\prime},\tilde{s}^{k,j}_{i}=s,\tilde{a}^{k,j}_{i}=a)\\\
\bar{P}_{k}(s^{\prime}|s,a):=\eta\sum_{j=1}^{N}\sum_{i=1}^{B}(1-\eta)^{\tilde{N}^{k,j}_{i}(s,a)}P(s^{\prime}|s,a)\mathbbm{1}(\tilde{s}^{k,j}_{i}=s,\tilde{a}^{k,j}_{i}=a).\end{gathered}$

######  Lemma 12.

Suppose Assumption 5 holds. Then, with probability at-least $1-\delta$, we
must have for any fixed $(s,a)$:

$\sum_{s^{\prime}\in\mathsf{supp}(P(\cdot|s,a))}|\hat{P}_{k}(s^{\prime}|s,a)-\bar{P}_{k}(s^{\prime}|s,a)|\leq
C\sqrt{\eta\bar{d}\log(4/\delta)}+C\eta\bar{d}\log(4/\delta)$

We refer to Section K.5 for the proof. We now proceed with the proof of
Theorem 3. Recall the noiseless iteration $\bar{w}^{k}$ defined in the
discussion following the statement of Lemma 4. We define
$\bar{D}_{k}:=w^{k,0}_{0}-\bar{w}^{k}$. Observe that we cannot apply Lemma 9
as in the proof of Theorem 2 where we used $w=w^{k,0}_{0}$ in order to bound
$\|\epsilon_{k}\|_{\infty}$. This is because of data re-use which causes
$w^{k,0}_{0}$ to depend on the ‘variance’ term.

However, note that $\bar{w}^{k}$ is a deterministic sequence and we can apply
Lemma 9 and then use the fact that $\bar{w}^{k}\approx w^{k,0}_{0}$ to show a
similar concentration inequality. To this end, we prove the following lemma:

######  Lemma 13.

In the tabular setting, we have almost surely:

$\displaystyle\biggr{|}\biggr{\langle}\phi(s,a),\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{k,l}_{1,B}\tilde{L}^{k,j}(w)-\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{k,l}_{1,B}\tilde{L}^{k,j}(v)\biggr{\rangle}\biggr{|}$
$\displaystyle\leq\gamma\|w-v\|_{\phi}\sum_{s^{\prime}\in\mathsf{supp}(P(\cdot|s,a))}|\hat{P}_{k}(s^{\prime}|s,a)-\bar{P}_{k}(s^{\prime}|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 $\epsilon_{k}$ in outer loop $k$ is given by
$\epsilon_{1}(\tilde{w}^{k,1}_{1})$

$Q^{k+1,1}_{1}=\mathcal{T}\left[Q^{k,1}_{1}\right]+\epsilon_{1}(\tilde{Q}^{k,1}_{1})\,.$

We also define the noiseless Q iteration such that
$\bar{Q}^{1,1}_{1}=\tilde{Q}^{1,1}_{1}$ and
$\bar{Q}^{k+1,1}_{1}=\mathcal{T}(\bar{Q}^{k,1}_{1})$. Let
$\bar{\Delta}_{k}:=\tilde{Q}^{k,1}_{1}-\bar{Q}^{k,1}_{1}$.

Now, by Lemma 5, we can write down

$\displaystyle\epsilon_{1}(\tilde{Q}^{k,1}_{1})(s,a)=(1-\eta)^{\tilde{N}^{1}(s,a)}(\tilde{Q}^{k,1}_{1}-\tilde{Q}^{k,*})+\langle\phi(s,a),\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{1,l}_{1,B}\tilde{L}^{1,j}(\tilde{Q}^{k,1}_{1})\rangle$
$\displaystyle=(1-\eta)^{\tilde{N}^{1}(s,a)}(\tilde{Q}^{k,1}_{1}-\tilde{Q}^{k,*})+\bigr{\langle}\phi(s,a),\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{1,l}_{1,B}\left(\tilde{L}^{1,j}(\tilde{Q}^{k,1}_{1})-\tilde{L}^{1,j}(\bar{Q}^{k,1}_{1})\right)\bigr{\rangle}$
$\displaystyle\quad+\bigr{\langle}\phi(s,a),\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{1,l}_{1,B}\tilde{L}^{1,j}(\bar{Q}^{k,1}_{1})\bigr{\rangle}$
(28)

We bound each of the terms above separately. By union bound, the following
statements all hold simulataneously with probability at-least $1-\delta$. By
Theorem 7, whenever
$NB>C\frac{\tau_{\mathsf{mix}}}{\mu_{\min}}\log(\tfrac{|\mathcal{S}||\mathcal{A}}{\delta})$,
we must have $\tilde{N}^{(1)}(s,a)\geq\frac{\mu_{\min}}{2}NB$. A simple
observation using recursion shows that
$\tilde{Q}^{k,1}_{1}(s,a),\bar{Q}^{k,1}_{1}(s,a)\in[0,\tfrac{1}{1-\gamma}]$.
Using Lemmas 12 and 13 we conclude that we must have:

$\displaystyle\sup_{(s,a)\in\mathcal{S}\times\mathcal{A}}\biggr{|}\bigr{\langle}\phi(s,a),\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{1,l}_{1,B}\left(\tilde{L}^{1,j}(\tilde{Q}^{k,1}_{1})-\tilde{L}^{1,j}(\bar{Q}^{k,1}_{1})\right)\bigr{\rangle}\biggr{|}$
$\displaystyle\leq
C\|\bar{\Delta}_{k}\|_{\infty}\left[\sqrt{\eta\bar{d}\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}+\eta\bar{d}\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}\right]$
(29)

Now observe that $\bar{Q}^{k,1}_{1}$ is a deterministic sequence. Therefore,
using Lemma 9 uniformly for every $k\leq K$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle\biggr{|}\bigr{\langle}\phi(s,a),\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{1,l}_{1,B}\tilde{L}^{1,j}(\bar{Q}^{k,1}_{1})\bigr{\rangle}\biggr{|}\leq
C\sqrt{\eta\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}(1+\mathsf{Var}_{P}(\bar{V}_{k})(s,a))}+C\frac{\eta\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}}{1-\gamma}$
(30)

Where,
$\mathsf{Var}_{P}(\bar{V}_{k}):=\mathsf{Var}_{P}(V)(s,a;\bar{Q}^{k,1}_{1})$.

We now combine all the above with Equation (28) to show that with probability
at least $(1-\delta)$, we must have uniformly for every $k\leq K$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle|\tilde{\epsilon}_{1}(\tilde{Q}^{k,1}_{1})(s,a)|$
$\displaystyle\leq\frac{1}{1-\gamma}\exp\left(-\tfrac{\eta\mu_{\min}NB}{2}\right)+C\|\bar{\Delta}_{k}\|_{\infty}\left[\sqrt{\eta\bar{d}\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}+\eta\bar{d}\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}\right]$
$\displaystyle\quad+C\sqrt{\eta\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}(1+\mathsf{Var}_{P}(\bar{V}_{k})(s,a))}+C\frac{\eta\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}}{1-\gamma}$
(31)

We will now present a crude bound on $\|\bar{\Delta}_{k}\|_{\infty}$ to reduce
the analysis of Q-RexDaRe to the analysis of Q-Rex.

######  Claim 1.

Whenever $\eta\leq
C_{1}\frac{(1-\gamma)^{2}}{\bar{d}\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}$,
with probability at-least $1-\delta$, we must have for every $k\leq K$
uniformly:

$\|\bar{\Delta}_{k}\|_{\infty}\leq
C\tfrac{\exp\left(-\tfrac{\eta\mu_{\min}NB}{2}\right)}{(1-\gamma)^{2}}+C\sqrt{\tfrac{\eta}{(1-\gamma)^{4}}\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}}$

Applying this directly to Equation (31), we conclude that with probability at
least $(1-\delta)$, we must have uniformly for every $k\leq K$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$:

$\displaystyle|\tilde{\epsilon}_{1}(\tilde{Q}^{k,1}_{1})(s,a)|$
$\displaystyle\leq\frac{C}{(1-\gamma)}\exp\left(-\tfrac{\eta\mu_{\min}NB}{2}\right)+C\frac{\eta\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}}{(1-\gamma)^{2}}\sqrt{\bar{d}}$
$\displaystyle\quad+C\sqrt{\eta\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}(1+\mathsf{Var}_{P}(\bar{V}_{k})(s,a))}+C\frac{\eta\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}}{1-\gamma}$
(32)

###### Proof of Claim 1.

First note that $\mathcal{T}$ is $\gamma$ contractive under the sup norm.
Therefore,

$\displaystyle\|\bar{\Delta}_{k+1}\|_{\infty}$
$\displaystyle=\biggr{\|}\mathcal{T}(\tilde{w}^{k,1}_{1})-\mathcal{T}(\bar{w}^{k,1}_{1})+\tilde{\epsilon}_{k}\biggr{\|}_{\infty}$
$\displaystyle\leq\biggr{\|}\mathcal{T}(\tilde{w}^{k,1}_{1})-\mathcal{T}(\bar{w}^{k,1}_{1})\biggr{\|}_{\infty}+\|\tilde{\epsilon}_{k}\|_{\infty}$
$\displaystyle\leq\gamma\|\bar{\Delta}_{k}\|_{\infty}+\|\tilde{\epsilon}_{k}\|_{\infty}$
(33)

In Equation (31), note that
$\mathsf{Var}_{P}(\bar{V}_{k})(s,a)\leq\frac{1}{(1-\gamma)^{2}}$. Therefore,
under the conditions of this Claim, we can take $C_{1}$ small enough so that
uniformly for every $(s,a)$ and $k\leq K$ with probability at-least
$(1-\delta)$, Equation (31) becomes:

$\|\tilde{\epsilon}_{k}(\tilde{Q}^{k,1}_{1})\|_{\infty}\leq\frac{\exp\left(-\tfrac{\eta\mu_{\min}NB}{2}\right)}{1-\gamma}+\|\bar{\Delta}_{k}\|_{\infty}\left(\frac{1-\gamma}{2}\right)+C\sqrt{\tfrac{\eta}{(1-\gamma)^{2}}\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}}\,.$

Combining the display above and the fact that
$\tilde{\epsilon}_{k}=\tilde{\epsilon}_{1}(\tilde{Q}^{k,1}_{1})$ in Equation
(33), we conclude that with probability at-least $1-\delta$, for every $k\leq
K$ uniformly:

$\displaystyle\|\bar{\Delta}_{k+1}\|_{\infty}\leq\frac{1+\gamma}{2}\|\bar{\Delta}_{k}\|_{\infty}+\tfrac{\exp\left(-\tfrac{\eta\mu_{\min}NB}{2}\right)}{1-\gamma}+C\sqrt{\tfrac{\eta}{(1-\gamma)^{2}}\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}}$
(34)

Unrolling the recursion above and using the fact that
$\|\bar{\Delta}_{1}\|_{\infty}=0$, we conclude the statement of the claim.

∎

We also note that the deterministic iterations $\bar{Q}^{k,1}_{1}$ converges
exponentially in sup norm to $Q^{*}$ due to $\gamma$ contractivity of
$\mathcal{T}$. That is:

$\|\bar{Q}^{k,1}_{1}-Q^{*}\|_{\infty}\leq\frac{\gamma^{k}}{(1-\gamma)}$ (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
$\mathsf{Var}_{P}(\tilde{V}_{k})$ replaced with
$\mathsf{Var}_{P}(\bar{V}_{k})$. Similar to the proof of Theorem 2, we can
control $\mathsf{Var}_{P}(\bar{V}_{k})$ with respect to
$\mathsf{Var}_{P}(V^{*})$ and $\|\bar{Q}^{k,1}_{1}-Q^{*}\|_{\infty}$ along
with Equation (35). We also replace $\alpha_{\eta}$ with

$\alpha_{\eta}^{\mathsf{dr}}:=\frac{C}{(1-\gamma)}\exp\left(-\tfrac{\eta\mu_{\min}NB}{2}\right)+C\frac{\eta\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}}{(1-\gamma)^{2}}\sqrt{\bar{d}}+C\frac{\eta\log\bigr{(}\tfrac{|\mathcal{S}||\mathcal{A}|K}{\delta}\bigr{)}}{1-\gamma}$

Therefore, we conclude a version of Equation (23):

$\|\Delta_{K+1}\|_{\infty}\leq\frac{\alpha^{\mathsf{dr}}_{\eta}+\gamma^{K}}{1-\gamma}+C\sqrt{\frac{\eta}{(1-\gamma)^{3}}\log\bigr{(}\tfrac{K|\mathcal{S}||\mathcal{A}|}{\delta}\bigr{)}}\sqrt{1+\frac{\gamma^{K/2}}{(1-\gamma)}}$
(36)

Where $\Delta_{k}:=Q^{k,1}_{1}-Q^{*}$. Using the bounds on the parameters
given in the statement of the Theorem, we conclude the result.

∎

##  Appendix K Proofs of Concentration Inequalities

###  K.1 Proof of Lemma 8

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 $\eta$) to
$\tilde{H}^{k,j}_{1,B}$. We omit the proof for the sake of clarity.

######  Lemma 14.

Suppose $\eta B<\frac{1}{3}$. Then, the following PSD inequalities hold almost
surely:

$I-2\eta\left(1+\tfrac{\eta B}{1-2\eta
B}\right)\sum_{i=1}^{B}\tilde{\phi}^{k,j}_{i}\left(\tilde{\phi}^{k,j}_{i}\right)^{\top}\preceq\left(\tilde{H}^{k,j}_{1,B}\right)^{\top}\tilde{H}^{k,j}_{1,B}\preceq
I-2\eta\left(1-\tfrac{\eta B}{1-2\eta
B}\right)\sum_{i=1}^{B}\tilde{\phi}^{k,j}_{i}\left(\tilde{\phi}^{k,j}_{i}\right)^{\top}$
(37)

###### Proof of Lemma 8.

We begin by proving the first part. Using Assumption 1 and the fact that the
decoupled trajectory $(\tilde{s},\tilde{a})_{t}$ is assumed to be mixed at the
start of every buffer, we begin by first noting from Lemma 14 that:

$0\preceq\mathbb{E}(\tilde{H}^{k,j}_{1,B})^{\top}\tilde{H}^{k,j}_{1,B}\preceq
I-\eta
B\mathbb{E}_{(s,a)\sim\mu}\phi(s,a)(\phi(s,a))^{\intercal}\preceq(1-\tfrac{\eta
B}{\kappa})I\,.$ (38)

Now, observe that:

$\displaystyle\|\prod_{j=N}^{1}\tilde{H}^{k,j}_{1,B}g\|^{2}=g^{\top}\prod_{j=1}^{N-1}(\tilde{H}^{k,j}_{1,B})^{\top}\left[(\tilde{H}^{k,N}_{1,B})^{\top}\tilde{H}^{k,N}_{1,B}\right]\prod_{j=N-1}^{1}\tilde{H}^{k,j}_{1,B}g$
(39)

Now note that $\tilde{H}^{k,N}_{1,B}$ is independent of
$\tilde{H}^{k,j}_{1,B}$ for $j\leq N-1$. Therefore, taking conditional
expectation conditioned on $H^{k,j}_{1,B}$ for $j\leq N-1$ in Equation (39)
and using Equation (38), we conclude:

$\displaystyle\mathbb{E}\|\prod_{j=N}^{1}\tilde{H}^{k,j}_{1,B}g\|^{2}\leq(1-\tfrac{\eta
B}{\kappa})\mathbb{E}\|\prod_{j=N-1}^{1}\tilde{H}^{k,j}_{1,B}g\|^{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-\delta$:

$\|\prod_{j=N}^{1}\tilde{H}^{k,j}_{1,B}g\|_{\phi}\leq\|\prod_{j=N}^{1}\tilde{H}^{k,j}_{1,B}g\|\leq\tfrac{\exp\left(-\tfrac{\eta
NB}{\kappa}\right)}{\sqrt{\delta}}\|g\|\leq\exp(-\tfrac{\eta
NB}{\kappa})\sqrt{\tfrac{\kappa}{\delta}}\|g\|_{\phi}\,.$

∎

###  K.2 Proof of Lemma 9

###### 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

$\langle\phi(s,a),\sum_{j=1}^{N}\prod_{l=N}^{j+1}\tilde{H}^{k,l}_{1,B}\tilde{L}^{k,j}(w)\rangle=\eta\sum_{j=1}^{N}\sum_{i=1}^{B}X^{k,j}_{i}$
(40)

Where
$X^{k,j}_{i}:=(1-\eta)^{\tilde{N}^{k,j}_{i}(s,a)}\tilde{\epsilon}^{k,j}_{i}\mathbbm{1}\bigr{(}(\tilde{s}^{k,j}_{i},\tilde{a}^{k,j}_{i})=(s,a)\bigr{)}$.
This allows us to define the sequence of sigma algebras
$\mathcal{F}^{k,j}_{i}=\sigma((\tilde{s}^{k,l}_{m},\tilde{a}^{k,l}_{m}):(l>j\text{
and }m\in[B])\text{ or }(l=j\text{ and }m\leq i))$ \- that is, it is the sigma
algebra of all states and rewards which appeared before and including
$(\tilde{s}^{k,j}_{i},\tilde{a}^{k,j}_{i})$ inside the buffer $j$ and all the
states in buffers $l>j$. Notice that $\tilde{N}^{k,j}_{i}(s,a)$ is measurable
with respect to the sigma algebra $\mathcal{F}^{k,j}_{i}$. Using the fact that
the buffers are independent, we conclude that:
$\mathbb{E}\left[X^{k,j}_{i}|\mathcal{F}^{k,j}_{i}\right]=0$ and

$\mathbb{E}\left[|X^{k,j}_{i}|^{2}|\mathcal{F}^{k,j}_{i}\right]\leq
2\left[1+\gamma^{2}\mathsf{Var}_{P}(V)(s,a;w)\right]\mathbbm{1}\bigr{(}(\tilde{s}^{k,j}_{i},\tilde{a}^{k,j}_{i})=(s,a)\bigr{)}(1-\eta)^{2\tilde{N}^{k,j}_{i}(s,a)}\,.$

It is also clear from our assumptions that
$|X^{j,k}_{i}|\leq\frac{2}{1-\gamma}$ almost surely. Consider the almost sure
inequality for the sum of conditional variances:

$\displaystyle W^{k}$
$\displaystyle=\sum_{j=1}^{N}\sum_{i=1}^{B}\mathbb{E}\left[|X^{k,j}_{i}|^{2}|\mathcal{F}^{k,j}_{i}\right]$
$\displaystyle\leq
2\left[1+\gamma^{2}\mathsf{Var}_{P}(V)(s,a;w)\right]\sum_{j=1}^{K}\sum_{i=1}^{B}\mathbbm{1}\bigr{(}(\tilde{s}^{k,j}_{i},\tilde{a}^{k,j}_{i})=(s,a)\bigr{)}(1-\eta)^{2\tilde{N}^{k,j}_{i}(s,a)}$
$\displaystyle=2\left[1+\gamma^{2}\mathsf{Var}_{P}(V)(s,a;w)\right]\sum_{t=0}^{\tilde{N}^{k}(s,a)-1}(1-\eta)^{2t}\leq
2\left(\frac{1+\gamma^{2}\mathsf{Var}_{P}(V)(s,a;w)}{\eta}\right)$ (41)

We now apply (Li et al., 2021, Equation (144),Theorem 4) with
$R=\frac{1}{1-\gamma}$ and
$\sigma^{2}=2\left(\frac{1+\gamma^{2}\mathsf{Var}_{P}(V)(s,a;w)}{\eta}\right)$
to conclude the result. ∎

###  K.3 Proof of Theorem 4

###### Proof.

For the sake of convenience, in this proof we will take
$\sigma^{2}:=4(1+\|w\|_{\phi}^{2})$. Suppose $\lambda\in\mathbb{R}$. For
$1\leq m\leq N$ consider:

$X_{m}:=\eta\lambda^{2}\sigma^{2}\biggr{\langle}x,\prod_{l=N}^{N-m+1}\tilde{H}^{k,l}_{1,B}\left(\prod_{l=N}^{N-m+1}\tilde{H}^{k,l}_{1,B}\right)^{\top}x\biggr{\rangle}+\lambda\biggr{\langle}x,\sum_{j=N-m+1}^{N}\left(\prod_{l=N}^{j+1}\tilde{H}^{k,l}_{1,B}\right)\tilde{L}^{k,j}(w)\biggr{\rangle}$

$X_{0}:=\|x\|^{2}\eta\lambda^{2}\sigma^{2}$

Here we use the convention that $\prod_{l=N}^{j+1}\tilde{H}^{k,l}_{1,B}=I$
whenever $j+1>N$. We claim that the sequence $\exp(X_{m})$ forms a super
martingale under an appropriate filtration. In this proof only, consider the
sigma algebra $\mathcal{F}_{m}$ to be the sigma algebra of all the state
action reward tuples in buffers $N,\dots,N-m+1$ and let $\mathcal{F}_{0}$ be
the trivial sigma algebra. Notice that $\exp(X_{m})$ is $\mathcal{F}_{m}$
measurable.

######  Lemma 15.

Fix $N\geq m\geq 1$. Suppose $Y\in\mathbb{R}^{d}$ is a $\mathcal{F}_{m-1}$
measurable random vector. Then,

$\mathbb{E}\left[\exp\left(\eta\lambda^{2}\sigma^{2}\langle
Y,\tilde{H}^{k,N-m+1}_{1,B}\left(\tilde{H}^{k,N-m+1}_{1,B}\right)^{\top}Y\rangle+\lambda\langle
Y,\tilde{L}^{k,N-m+1}(w)\rangle\right)\biggr{|}\mathcal{F}_{m-1}\right]\leq\exp\left(\eta\lambda^{2}\sigma^{2}\|Y\|^{2}\right)$

In particular, taking
$Y=\left(\prod_{l=N}^{N-m+2}\tilde{H}^{k,l}_{1,B}\right)^{\top}x$ , we
conclude that $\exp(X_{m})$ is a super martingale with respect to the
filtration $\mathcal{F}_{m}$

###### 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 $\mathcal{F}_{m-1}$, we will treat
$Y$ as a constant. Now we define the natural filtration on the buffer under
consideration $(\mathcal{G}_{i})_{i=1}^{B}$ where $\mathcal{G}_{i}$ is the
sigma algebra of the all state-action tuples from
$(s_{1},a_{1}),\dots,(s_{i},a_{i})$ and rewards $(r_{h})_{1\leq h<i}$.

Note that by the definition of $\tilde{L}(w)$, we write:
$\tilde{L}(w)=\sum_{i=1}^{B}\eta\tilde{\epsilon}_{i}(w)\tilde{H}_{1,i-1}\tilde{\phi}_{i}$.
With this in mind, for $h\in[B]$ define
$\tilde{L}_{h}(w)=\sum_{i=1}^{h}\eta\tilde{\epsilon}_{i}(w)\tilde{H}_{1,i-1}\tilde{\phi}_{i}$.
Now,
$\tilde{L}(w)=\eta\tilde{\epsilon}_{B}(w)\tilde{H}_{1,B-1}\tilde{\phi}_{B}+\tilde{L}_{B-1}(w)$

Now, notice that the random variables $\langle
Y,\tilde{L}_{B-1}\rangle$,$\langle Y,\tilde{H}_{1,B-1}\tilde{\phi}_{B}\rangle$
and $\langle
Y,\tilde{H}^{k,m}_{1,B}\left(\tilde{H}^{k,m}_{1,B}\right)^{\top}Y\rangle$ are
$\mathcal{G}_{B}$ measureable. Furthermore, we must have:
$\mathbb{E}\left[\tilde{\epsilon}_{B}(w)\bigr{|}\mathcal{G}_{B}\right]=0$ and
$|\tilde{\epsilon}_{B}(w)|\leq 2(1+\|w\|_{\phi})\leq\sqrt{2}\sigma$.
Therefore, applying conditional Hoeffding’s lemma, we have:

$\displaystyle\mathbb{E}\left[\exp\left(\eta\lambda^{2}\sigma^{2}\langle
Y,\tilde{H}_{1,B}\left(\tilde{H}_{1,B}\right)^{\top}Y\rangle+\lambda\langle
Y,\tilde{L}(w)\rangle\right)\biggr{|}\mathcal{G}_{B}\right]$
$\displaystyle=\exp\left(\eta\lambda^{2}\sigma^{2}\langle
Y,\tilde{H}_{1,B}\left(\tilde{H}_{1,B}\right)^{\top}Y\rangle+\lambda\langle
Y,\tilde{L}_{B-1}(w)\rangle\right)\mathbb{E}\left[\exp\left(\lambda\eta\tilde{\epsilon}_{B}(w)\langle
Y,\tilde{H}_{1,B-1}\tilde{\phi}_{B}\rangle\right)\biggr{|}\mathcal{G}_{B}\right]$
$\displaystyle\leq\exp\left(\eta\lambda^{2}\sigma^{2}\langle
Y,\tilde{H}_{1,B}\left(\tilde{H}_{1,B}\right)^{\top}Y\rangle+\lambda\langle
Y,\tilde{L}_{B-1}(w)\rangle\right)\exp\left(\lambda^{2}\eta^{2}\sigma^{2}|\langle
Y,\tilde{H}_{1,B-1}\tilde{\phi}_{B}\rangle|^{2}\right)$ (42)

In the third step we have used the conditional version of Hoeffding’s lemma.
Now, consider $Z:=(\tilde{H}_{1,B-1})^{\top}Y$. Clearly,

$\displaystyle\langle
Y,\tilde{H}_{1,B}\left(\tilde{H}_{1,B}\right)^{\top}Y\rangle+\eta|\langle
Y,\tilde{H}_{1,B-1}\tilde{\phi}_{B}\rangle|^{2}$
$\displaystyle=Z^{\top}\tilde{H}_{B,B}^{\top}\tilde{H}_{B,B}Z+\eta
Z^{\top}\tilde{\phi}_{B}(\tilde{\phi}_{B})^{\top}Z$
$\displaystyle=Z^{\top}\left[I-\eta\tilde{\phi}_{B}(\tilde{\phi}_{B})^{\top}+\|\tilde{\phi}_{B}\|^{2}\eta^{2}\tilde{\phi}_{B}(\tilde{\phi}_{B})^{\top}\right]Z$
$\displaystyle\leq\|Z\|^{2}$

Here we have used the fact that $\eta<1$ and $\|\tilde{\phi}_{B}\|<1$. Using
the bounds above in Equation (42), we conclude:

$\displaystyle\mathbb{E}\left[\exp\left(\eta\lambda^{2}\sigma^{2}\langle
Y,\tilde{H}_{1,B}\left(\tilde{H}_{1,B}\right)^{\top}Y\rangle+\lambda\langle
Y,\tilde{L}_{B}(w)\rangle\right)\biggr{|}\mathcal{G}_{B}\right]$
$\displaystyle\leq\exp\left(\eta\lambda^{2}\sigma^{2}\langle
Y,\tilde{H}_{1,B-1}\left(\tilde{H}_{1,B-1}\right)^{\top}Y\rangle+\lambda\langle
Y,\tilde{L}_{B-1}(w)\rangle\right)$ (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 $X_{m}$. ∎

By Lemma 15, we conclude that $\exp(X_{m})$ is a super martingale with respect
to the filtration $\mathcal{F}_{m}$. Therefore, we must have:

$\mathbb{E}\exp(X_{N})\leq\exp(X_{0})=\exp(\eta\|x\|^{2}\lambda^{2}\sigma^{2})\,.$

It is also clear that
$X_{N}\geq\lambda\biggr{\langle}x,\sum_{j=N-m+1}^{N}\left(\prod_{l=N}^{j+1}\tilde{H}^{k,l}_{1,B}\right)\tilde{L}^{k,j}(w)\biggr{\rangle}$.
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.

∎

###  K.4 Proof of Lemma 10

###### Proof of Lemma 10.

By definition of $\tilde{\epsilon}_{k}$, we have:
$\tilde{w}^{k+1,1}_{1}=\mathcal{T}(\tilde{w}^{k,1}_{1})+\tilde{\epsilon}_{k}$.
Therefore, for any $(s,a)\in\mathcal{S}\times\mathcal{A}$, we must have:

$\langle\phi(s,a),\tilde{w}^{k+1,1}_{1}\rangle=R(s,a)+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\sup_{a^{\prime}\in
A}\langle\phi(s^{\prime},a^{\prime}),\tilde{w}^{k,1}_{1}\rangle+\langle\phi(s,a),\tilde{\epsilon}_{k}\rangle\,.$

Using the fact that $R(s,a)\in[0,1]$, we conclude:

$\|\tilde{w}^{k+1,1}_{1}\|_{\phi}\leq
1+\gamma\|\tilde{w}^{k,1}_{1}\|_{\phi}+\|\tilde{\epsilon}_{k}\|_{\phi}$ (44)

By independence of outer-loops for the coupled data, we note that
$\tilde{w}^{k,1}_{1}$ is independent of the data in buffer $k$. Therefore we
can apply Theorem 4 (and resp. Lemma 8) conditionally with
$w=\tilde{w}^{k,1}_{1}$ (and resp. $g=\tilde{w}^{k,1}_{1}-w^{*}$), the bias
variance decomposition given in Lemma 5 and the bound on $\|w^{*}\|_{\phi}$ in
Lemma 4 to conclude that with probability at-least $1-\delta$, for every
$k\leq K$:

$\displaystyle\|\tilde{\epsilon}_{k}\|_{\phi}$
$\displaystyle\leq\sqrt{\frac{K\kappa}{\delta}}\exp(-\tfrac{\eta
NB}{\kappa})(\|\tilde{w}^{k,1}_{1}\|_{\phi}+\frac{1}{1-\gamma})$
$\displaystyle\quad+C(1+\|\tilde{w}^{k,1}_{1}\|_{\phi})\sqrt{\eta}\left[C_{\Phi}+\sqrt{\log(\tfrac{2K}{\delta})}\right]$
(45)

We now choose constants $C_{1}$ and $C_{2}$ in the statement of the Lemma such
that Equation 45 implies:

$\|\tilde{\epsilon}_{k}\|_{\phi}\leq\frac{1-\gamma}{2}\|\tilde{w}^{k,1}_{1}\|_{\phi}+1$

Using the equation above in Equation (44), we conclude:

$\|\tilde{w}^{k+1,1}_{1}\|_{\phi}\leq
2+\frac{1+\gamma}{2}\|\tilde{w}^{k,1}_{1}\|_{\phi}\,.$

Unrolling the recursion above and noting $w^{1,1}_{1}=0$, we conclude that
with probability at-least $1-\delta$, we must have
$\|\tilde{w}^{k,1}_{1}\|_{\phi}\leq\frac{4}{1-\gamma}$ for every $k\leq K$.
The bound in item 2 follows by using item 1, Equation (45) and the fact that
$\tilde{w}^{k,1}_{1}$ is independent of the data in buffer $k$ due to our
coupling. ∎

###  K.5 Proof of Lemma 12

###### Proof.

For the sake of convenience, we will take
$\bar{d}=|\mathsf{supp}(P(\cdot|s,a))|$ and index
$\mathsf{supp}(P(\cdot|s,a))$ by $[\bar{d}]$. Consider
$Y\in\\{-1,1\\}^{\bar{d}}$. We consider the class of random variables indexed
by elements of $\\{-1,1\\}^{\bar{d}}$:

$\Delta(Y;s,a)=\sum_{s^{\prime}}Y_{s^{\prime}}\left[\hat{P}_{k}(s^{\prime}|s,a)-\bar{P}(s^{\prime}|s,a)\right]$

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 $\mathcal{F}^{k,j}_{i}$ for $i\in[B]$ and
$j\in[K]$ as defined in the proof of Lemma 9. We now define

$X^{k,j}_{i}(Y):=(1-\eta)^{\tilde{N}_{i}^{k,j}(s,a)}\sum_{s^{\prime}}Y_{s^{\prime}}\left(\mathbbm{1}(\tilde{s}^{k,j}_{i+1}=s^{\prime},\tilde{s}^{k,j}_{i}=s,\tilde{a}^{k,j}_{i}=a)-P(s^{\prime}|s,a)\mathbbm{1}(\tilde{s}^{k,j}_{i}=s,\tilde{a}^{k,j}_{i}=a)\right)\,.$

We note that $\mathbb{E}\left[X^{k,j}_{i}(Y)|\mathcal{F}^{k,j}_{i}\right]=0$
and $|X^{k,j}_{i}(Y)|\leq 2$ almost surely and a simple calculation reveals
that:
$\mathbb{E}\left[|X^{k,j}_{i}(Y)|^{2}|\mathcal{F}^{k,j}_{i}\right]\leq(1-\eta)^{2\tilde{N}^{k,j}_{i}}\mathbbm{1}(\tilde{s}^{k,j}_{i}=s,\tilde{a}^{k,j}_{i}=a)$

It is also clear that:
$\Delta(Y;s,a)=\eta\sum_{j=1}^{K}\sum_{i=1}^{B}X_{i}^{k,j}(Y)$. Apply
Freedman’s concentration inequality, we conclude for any fixed
$Y\in\\{-1,1\\}^{\bar{d}}$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,

$\mathbb{P}(|\Delta(Y;s,a)|>C\sqrt{\eta\log(2/\delta)}+\eta\log(2/\delta))\leq\delta$

Applying a union bound over all $Y\in{-1,1}^{d}$, we conclude:

$\mathbb{P}(\sup_{Y\in\\{-1,1\\}^{\bar{d}}}|\Delta(Y;s,a)|>C\sqrt{\eta\bar{d}\log(4/\delta)}+\eta\bar{d}\log(4/\delta))\leq\delta\,.$

We complete the proof by noting that

$\sup_{Y\in\\{-1,1\\}^{\bar{d}}}|\Delta(Y;s,a)|=\sum_{s^{\prime}\in\mathsf{supp}(P(\cdot|s,a))}|\hat{P}_{k}(s^{\prime}|s,a)-\bar{P}_{k}(s^{\prime}|s,a)|$

∎

##  Appendix L Technical Lemmas

###  L.1 Coupling Lemma

We first introduce some useful notation: Let $D^{k,j}$ (resp.
$\tilde{D}^{k,j}$) be the tuple of random variables
$(s^{k,j}_{i},a^{k,j}_{i},r^{k,j}_{i})_{i=1}^{B+1}$ (resp.
$(\tilde{s}^{k,j}_{i},\tilde{a}^{k,j}_{i},\tilde{r}^{k,j}_{i})_{i=1}^{B+1}$).

######  Lemma 16.

Suppose

$u\geq\begin{cases}C\tau_{\mathsf{mix}}\log(\tfrac{T}{\delta})\text{ in the
tabular setting}\\\
C\tau_{\mathsf{mix}}\log(\tfrac{T}{C_{\mathsf{mix}}\delta})\text{ in the
general setting}\end{cases}$ (46)

Then, we can define the sequences $(s_{t},a_{t},r_{t})$ and
$(\tilde{s}_{t},\tilde{a}_{t},\tilde{r}_{t})$ on a common probability space
such that:

  1. 1.

The tuples $D^{k,j}$ and $\tilde{D}^{k,j}$ have the same distribution for
every $(k,j)$,

  2. 2.

The sequence $\tilde{D}^{k,j}$ for $k\leq N,j\leq K$ is i.i.d.

  3. 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). ∎

###  L.2 Proof of Lemma 2

###### Proof.

The first part follows from the definitions. For the second part, note that:
$\|x\|\geq\|x\|_{\phi}$ follows from Cauchy-Schwarz inequality and Assumption
1. For the reverse inequality we use Assumption 4 to show that:

$\|x\|^{2}_{\phi}\geq\mathbb{E}_{(s,a)\sim\mu}\langle\phi(s,a),x\rangle^{2}\geq\frac{\|x\|^{2}}{\kappa}$

∎

###  L.3 Proof of Lemma 3

###### Proof.

Existence is guaranteed by Definition (2) and uniqueness follows from the
assumption that $\mathsf{span}(\Phi)=\mathbb{R}^{d}$. ∎

###  L.4 Proof of Lemma 4

###### Proof.

Suppose $w_{0},\tilde{w}_{0}\in\mathbb{R}^{d}$ are arbitrary. Let
$w_{1}=\mathcal{T}(w_{0})$ and $\tilde{w}_{1}=\mathcal{T}(\tilde{w}_{0})$. For
any $\phi(s,a)$, we have:

$\displaystyle|\langle\phi(s,a),w_{1}-\tilde{w}_{1}\rangle|=\gamma\bigr{|}\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\sup_{a^{\prime}\in\mathcal{A}}\langle\phi(s^{\prime},a^{\prime}),w_{0}\rangle-\mathbb{E}_{s^{\prime}\sim
P(\cdot|s,a)}\sup_{a^{\prime}\in\mathcal{A}}\langle\phi(s^{\prime},a^{\prime}),\tilde{w}_{0}\rangle\bigr{|}$
(47)

By Assumption 2, for every fixed $s^{\prime}$ there exist
$a^{\prime}_{\max}(s^{\prime}),\tilde{a}^{\prime}_{\max}(s^{\prime})$ such
that

$\sup_{a^{\prime}\in\mathcal{A}}\langle\phi(s^{\prime},a^{\prime}(s^{\prime})),w_{0}\rangle=\langle\phi(s^{\prime},\tilde{a}^{\prime}_{\max}(s^{\prime})),w_{0}\rangle\;\;\text{
and
}\;\;\sup_{a^{\prime}\in\mathcal{A}}\langle\phi(s^{\prime},a^{\prime}),\tilde{w}_{0}\rangle=\langle\phi(s^{\prime},\tilde{a}^{\prime}_{\max}(s^{\prime})),\tilde{w}_{0}\rangle.$

Therefore for any $s^{\prime}$ it holds that,

$\langle\phi(s^{\prime},\tilde{a}^{\prime}_{\max}),w_{0}-\tilde{w}_{0}\rangle\leq\sup_{a^{\prime}\in\mathcal{A}}\langle\phi(s^{\prime},a^{\prime}),w_{0}\rangle-\sup_{a^{\prime}\in\mathcal{A}}\langle\phi(s^{\prime},a^{\prime}),\tilde{w}_{0}\rangle\leq\langle\phi(s^{\prime},a^{\prime}_{\max}),w_{0}-\tilde{w}_{0}\rangle$
$\implies\bigr{|}\sup_{a^{\prime}\in\mathcal{A}}\langle\phi(s^{\prime},a^{\prime}),w_{0}\rangle-\sup_{a^{\prime}\in\mathcal{A}}\langle\phi(s^{\prime},a^{\prime}),\tilde{w}_{0}\rangle\bigr{|}\leq\|w_{0}-\tilde{w}_{0}\|_{\phi}\,.$

Combining this with Equation (47), we conclude the $\gamma$-contractivity of
$\mathcal{T}$. By contraction mapping theorem, $\mathcal{T}$ has a unique
fixed point we conclude that it is $w^{*}$ by considering $Q(s,a):=\langle
w^{*},\phi(s,a)\rangle$ and showing that it satisfies the bellman optimality
condition in Equation (2). For the norm inequality, we note that since
$R(s,a)\in[0,1]$ by assumption and $w^{*}=\mathcal{T}(w^{*})$, we have:
$|\langle\phi(s,a),w^{*}\rangle|\leq 1+\gamma\|w^{*}\|_{\phi}$. Therefore,
$\|w^{*}\|\leq\tfrac{1}{1-\gamma}$. The second norm equality follows from
Lemma 2. ∎

###  L.5 Proof of Lemma 5

###### Proof.

We write the iteration in the outer-loop $k$ as:

$\tilde{w}^{k,j}_{i+1}=\left[I-\eta\tilde{\phi}^{k,j}_{-i}[\tilde{\phi}^{k,j}_{-i}]^{\top}\right]\tilde{w}^{k,j}_{i}+\eta\tilde{\phi}^{k,j}_{-i}\left[\tilde{r}^{k,j}_{-i}+\gamma\sup_{a^{\prime}\in\mathcal{A}}\langle\tilde{w}^{k,1}_{1},\phi(\tilde{s}^{k,j}_{-(i-1)},a^{\prime})\rangle\right]$

Using the fact that
$\langle\tilde{w}^{k+1,*},\tilde{\phi}^{k,j}_{-i}\rangle=\tilde{R}^{k,j}_{-i}+\gamma\mathbb{E}_{s^{\prime}\sim
P(\cdot|\tilde{s}^{k,j}_{-i},\tilde{a}^{k,j}_{-i})}\sup_{a^{\prime}\in
A}\langle\phi(s^{\prime},a^{\prime}),\tilde{w}^{k,1}_{1}\rangle$, and
recalling the notation in (5),(6), we write:

$\tilde{w}^{k,j}_{i+1}-\tilde{w}^{k+1,*}=\left[I-\eta\tilde{\phi}^{k,j}_{-i}[\tilde{\phi}^{k,j}_{-i}]^{\top}\right]\left(\tilde{w}^{k,j}_{i}-w^{k+1,*}\right)+\eta\tilde{\phi}^{k,j}_{-i}\epsilon^{k,j}_{-i}\,.$

Therefore,

$\tilde{w}^{k,j+1}_{1}-\tilde{w}^{k+1,*}=\tilde{H}^{k,j}_{1,B}(\tilde{w}^{k,j}_{1}-\tilde{w}^{k+1,*})+\tilde{L}^{k,j}$

Unfurling further, and using the fact that
$\tilde{w}^{k,N+1}_{1}=\tilde{w}^{k+1,1}_{1}$, we conclude the statement of
the lemma.

∎

###  L.6 Proof of Lemma 7

We let
$\tilde{N}^{k,j}(s,a):=\sum_{i=1}^{B}\mathbbm{1}((\tilde{s}^{k,j}_{i},\tilde{a}^{k,j}_{i})=(s,a))$.
We want to show that the quantity $\sum_{j=1}^{N}\tilde{N}^{k,j}(s,a)$
concentrates around its expectation. Note that
$\mathbb{E}\tilde{N}^{k,j}(s,a)=B\mu(s,a)$ and that $\tilde{N}^{k,j}(s,a)$ are
i.i.d. for $j\in[N]$. From the proof of (Paulin, 2015, Theorem 3.4) and the
fact that $\gamma_{\mathsf{ps}}\geq\frac{1}{2\tau_{\mathsf{mix}}}$, we
conclude:

$\displaystyle\mathbb{E}\exp(\lambda(\sum_{j=1}^{N}\tilde{N}^{k,j}(s,a)-B\mu(s,a)))$