# Is Q-Learning Minimax Optimal?
A Tight Sample Complexity Analysis

Gen Li
Princeton ECE
Department of Electrical and Computer Engineering, Princeton University,
Princeton, NJ 08544, USA. Changxiao Cai
UPenn Biostatistics
Department of Biostatistics, University of Pennsylvania, Philadelphia, PA
19104, USA. Yuxin Chen11footnotemark: 1
Princeton ECE
Yuantao Gu
Tsinghua EE
Department of Electronic Engineering, Tsinghua University, Beijing 100084,
China Yuting Wei
UPenn Statistics
Department of Statistics and Data Science, The Wharton School, University of
Pennsylvania, Philadelphia, PA 19104, USA. Yuejie Chi
CMU ECE
Department of Electrical and Computer Engineering, Carnegie Mellon University,
Pittsburgh, PA 15213, USA.

(February 2021; Revised: November 2021)

###### Abstract

Q-learning, which seeks to learn the optimal Q-function of a Markov decision
process (MDP) in a model-free fashion, lies at the heart of reinforcement
learning. When it comes to the synchronous setting (such that independent
samples for all state-action pairs are drawn from a generative model in each
iteration), substantial progress has been made towards understanding the
sample efficiency of Q-learning. Consider a $\gamma$-discounted infinite-
horizon MDP with state space $\mathcal{S}$ and action space $\mathcal{A}$: to
yield an entrywise $\varepsilon$-approximation of the optimal Q-function,
state-of-the-art theory for Q-learning requires a sample size exceeding the
order of $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{5}\varepsilon^{2}}$,
which fails to match existing minimax lower bounds. This gives rise to natural
questions: what is the sharp sample complexity of Q-learning? Is Q-learning
provably sub-optimal? This paper addresses these questions for the synchronous
setting: (1) when $|\mathcal{A}|=1$ (so that Q-learning reduces to TD
learning), we prove that the sample complexity of TD learning is minimax
optimal and scales as $\frac{|\mathcal{S}|}{(1-\gamma)^{3}\varepsilon^{2}}$
(up to log factor); (2) when $|\mathcal{A}|\geq 2$, we settle the sample
complexity of Q-learning to be on the order of
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\varepsilon^{2}}$ (up to log
factor). Our theory unveils the strict sub-optimality of Q-learning when
$|\mathcal{A}|\geq 2$, and rigorizes the negative impact of over-estimation in
Q-learning. Finally, we extend our analysis to accommodate asynchronous
Q-learning (i.e., the case with Markovian samples), sharpening the horizon
dependency of its sample complexity to be $\frac{1}{(1-\gamma)^{4}}$.

Keywords: Q-learning, temporal difference learning, effective horizon, sample
complexity, minimax optimality, lower bound, over-estimation

###### Contents

  1. 1 Introduction
    1. 1.1 Main contributions
    2. 1.2 Related works
  2. 2 Background and algorithms
  3. 3 Main results: sample complexity of synchronous Q-learning
    1. 3.1 Minimax optimality of TD learning
    2. 3.2 Tight sample complexity and sub-optimality of Q-learning
  4. 4 Key analysis ideas (the synchronous case)
    1. 4.1 Vector and matrix notation
    2. 4.2 Proof outline for Theorem 2
    3. 4.3 Proof outline for Theorem 3
  5. 5 Extension: sample complexity of asynchronous Q-learning
    1. 5.1 Markovian samples and asynchronous Q-learning
    2. 5.2 Sample complexity of asynchronous Q-learning
  6. 6 Concluding remarks
  7. A Freedman’s inequality
  8. B Upper bounds for Q-learning (Theorem 2)
    1. B.1 Preliminaries
    2. B.2 Proof of Lemma 1
    3. B.3 Proof of Lemma 2
    4. B.4 Solving the recurrence relation regarding $\bm{\Delta}_{t}$
    5. B.5 Proof of Lemma 5
  9. C Analysis for TD learning (Theorem 1)
    1. C.1 Preliminary facts
    2. C.2 Proof of Theorem 7
  10. D Lower bound: sub-optimality of Q-learning (Theorem 3)
    1. D.1 Key quantities related to learning rates
    2. D.2 Preliminary calculations
    3. D.3 Lower bounds for three cases
    4. D.4 Proof of Lemma 3
  11. E Analysis for asynchronous Q-learning (Theorem 4)
    1. E.1 Notation and preliminary facts
    2. E.2 Main steps for proving Theorem 4
    3. E.3 Proofs of technical lemmas

##  1 Introduction

Q-learning is arguably one of the most widely adopted model-free algorithms
(Watkins,, 1989; Watkins and Dayan,, 1992). Characterizing its sample
efficiency lies at the core of the statistical foundation of reinforcement
learning (RL) (Sutton and Barto,, 2018). While classical convergence analyses
for Q-learning (Tsitsiklis,, 1994; Szepesvári,, 1998; Jaakkola et al.,, 1994;
Borkar and Meyn,, 2000) focused primarily on the asymptotic regime — in which
the number of iterations tends to infinity with other problem parameters held
fixed — recent years have witnessed a paradigm shift from asymptotic analyses
towards a finite-sample / finite-time framework (Even-Dar and Mansour,, 2003;
Kearns and Singh,, 1999; Beck and Srikant,, 2012; Chen et al.,, 2020;
Wainwright, 2019b, ; Lee and He,, 2018; Qu and Wierman,, 2020; Xiong et al.,,
2020; Chen et al.,, 2021; Li et al., 2021b, ; Weng et al., 2020a, ). Drawing
insights from high-dimensional statistics (Wainwright, 2019a, ), a modern non-
asymptotic framework unveils more clear and informative impacts of salient
problem parameters upon the sample complexity, particularly for those
applications with enormous state/action space and long horizon. Motivated by
its practical value, a suite of non-asymptotic theory has been recently
developed for Q-learning to accommodate multiple sampling mechanisms (Even-Dar
and Mansour,, 2003; Beck and Srikant,, 2012; Jin et al.,, 2018; Wainwright,
2019b, ; Qu and Wierman,, 2020; Li et al., 2021b, ).

In this paper, we revisit the sample complexity of Q-learning for tabular
Markov decision processes (MDPs). For concreteness, let us consider the
synchronous setting, which assumes access to a generative model or a simulator
that produces independent samples for all state-action pairs in each iteration
(Kearns et al.,, 2002; Kakade,, 2003); this setting is termed “synchronous” as
the estimates w.r.t. all state-action pairs are updated at once. We
investigate the $\ell_{\infty}$-based sample complexity, namely, the number of
samples needed for synchronous Q-learning to yield an entrywise
$\varepsilon$-accurate estimate of the optimal Q-function. Despite a number of
prior works tackling this setting, the dependence of the sample complexity on
the effective horizon $\frac{1}{1-\gamma}$ remains unsettled. Take
$\gamma$-discounted infinite-horizon MDPs for instance: the state-of-the-art
sample complexity bounds (Wainwright, 2019b, ; Chen et al.,, 2020) scale on
the order of
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{5}\varepsilon^{2}}$ (up to some
log factor), where $\mathcal{S}$ and $\mathcal{A}$ represent the state space
and the action space, respectively. However, it is unclear whether this
scaling is sharp for Q-learning, and whether it can be further improved via a
more refined theory. On the one hand, the minimax lower limit for this setting
has been shown to be on the order of
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}$ (up to some
log factor) (Azar et al.,, 2013); this limit is achievable by model-based
approaches (Agarwal et al.,, 2020; Li et al.,, 2020) and apparently smaller
than prior sample complexity bounds for Q-learning. On the other hand,
Wainwright, 2019c  argued through numerical experiments that “the usual
Q-learning suffers from at least worst-case fourth-order scaling in the
discount complexity $\frac{1}{1-\gamma}$, as opposed to the third-order
scaling $\ldots$”, although no rigorous justification was provided therein.
Given the gap between the achievability bounds and lower bounds in the status
quo, it is natural to seek answers to the following questions:

What is the tight sample complexity characterization of Q-learning?

How does it compare to the minimax sample complexity limit?

paper | learning rates | sample complexity
---|---|---
Even-Dar and Mansour, (2003) | linear: $\frac{1}{t}$ | $2^{\frac{1}{1-\gamma}}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\varepsilon^{2}}$
Even-Dar and Mansour, (2003) | polynomial: $\frac{1}{t^{\omega}}$, $\omega\in(1/2,1)$ | $|\mathcal{S}||\mathcal{A}|\Big{\\{}\big{(}\frac{1}{(1-\gamma)^{4}\varepsilon^{2}}\big{)}^{1/\omega}+\big{(}\frac{1}{1-\gamma}\big{)}^{\frac{1}{1-\omega}}\Big{\\}}$
Beck and Srikant, (2012) | constant: $\frac{(1-\gamma)^{4}\varepsilon^{2}}{|\mathcal{S}||\mathcal{A}|}$ | $\frac{|\mathcal{S}|^{2}|\mathcal{A}|^{2}}{(1-\gamma)^{5}\varepsilon^{2}}$
Wainwright, 2019b  | rescaled linear: $\frac{1}{1+(1-\gamma)t}$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{5}\varepsilon^{2}}$
Wainwright, 2019b  | polynomial: $\frac{1}{t^{\omega}}$, $\omega\in(0,1)$ | $|\mathcal{S}||\mathcal{A}|\Big{\\{}\big{(}\frac{1}{(1-\gamma)^{4}\varepsilon^{2}}\big{)}^{1/\omega}+\big{(}\frac{1}{1-\gamma}\big{)}^{\frac{1}{1-\omega}}\Big{\\}}$
Chen et al., (2020) | rescaled linear: $\frac{1}{\frac{1}{(1-\gamma)^{2}}+(1-\gamma)t}$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{5}\varepsilon^{2}}$
Chen et al., (2020) | constant: $(1-\gamma)^{4}\varepsilon^{2}$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{5}\varepsilon^{2}}$
this work (Q-learning, $|\mathcal{A}|\geq 2$) | rescaled linear: $\frac{1}{1+(1-\gamma)t}$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\varepsilon^{2}}$
this work (Q-learning, $|\mathcal{A}|\geq 2$) | constant: $(1-\gamma)^{3}\varepsilon^{2}$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\varepsilon^{2}}$
this work (TD learning, $|\mathcal{A}|=1$) | rescaled linear: $\frac{1}{1+(1-\gamma)t}$ | $\frac{|\mathcal{S}|}{(1-\gamma)^{3}\varepsilon^{2}}$
this work (TD learning, $|\mathcal{A}|=1$) | constant: $(1-\gamma)^{3}\varepsilon^{2}$ | $\frac{|\mathcal{S}|}{(1-\gamma)^{3}\varepsilon^{2}}$
Table 1: Comparisons of existing sample complexity upper bounds of synchronous
Q-learning and TD learning for an infinite-horizon $\gamma$-discounted MDP
with state space $\mathcal{S}$ and action space $\mathcal{A}$, where
$0<\varepsilon<1$ is the target accuracy level. Here, sample complexity refers
to the total number of samples needed to yield either
$\max_{s,a}|\widehat{Q}(s,a)-{Q}^{\star}(s,a)|\leq\varepsilon$ with high
probability or
$\mathbb{E}\big{[}\max_{s,a}|\widehat{Q}(s,a)-{Q}^{\star}(s,a)|\big{]}\leq\varepsilon$,
where $\widehat{Q}$ is the estimate returned by Q-learning. All logarithmic
factors are omitted in the table to simplify the expressions.

###  1.1 Main contributions

Focusing on $\gamma$-discounted infinite-horizon MDPs with state space
$\mathcal{S}$ and action space $\mathcal{A}$, this paper settles the
$\ell_{\infty}$-based sample complexity of synchronous Q-learning. Here and
throughout, the standard notation $f(\cdot)=\widetilde{O}(g(\cdot))$ (resp.
$f(\cdot)=\widetilde{\Omega}(g(\cdot))$) means that $f(\cdot)$ is orderwise no
larger than (resp. no smaller than) $g(\cdot)$ modulo some logarithmic
factors. Our main contributions regarding synchronous Q-learning are
summarized below.

  * •

When $|\mathcal{A}|=1$, Q-learning coincides with temporal difference (TD)
learning in a Markov reward process. For any $0<\varepsilon<1$, we prove that
a total sample size of

$\widetilde{O}\Big{(}\frac{|\mathcal{S}|}{(1-\gamma)^{3}\varepsilon^{2}}\Big{)}$
(1)

is sufficient for TD learning to guarantee $\varepsilon$-accuracy in an
$\ell_{\infty}$ sense; see Theorem 1. This is sharp and minimax optimal (up to
some log factor).

  * •

Moving on to the case with $|\mathcal{A}|\geq 2$, we demonstrate that a sample
size of

$\widetilde{O}\Big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\varepsilon^{2}}\Big{)}$
(2)

suffices for Q-learning to yield $\varepsilon$-accuracy in an $\ell_{\infty}$
sense for any $0<\varepsilon<1$; see Theorem 2. Conversely, we construct a
hard MDP instance with 4 states and 2 actions, for which Q-learning provably
requires at least

$\widetilde{\Omega}\Big{(}\frac{1}{(1-\gamma)^{4}\varepsilon^{2}}\Big{)}$ (3)

iterations to achieve $\varepsilon$-accuracy in an $\ell_{\infty}$ sense; see
Theorem 3. These two theorems taken collectively lead to the first sharp
characterization of the sample complexity of Q-learning, strengthening prior
theory (Wainwright, 2019b, ; Chen et al.,, 2020) by a factor of
$\frac{1}{1-\gamma}$. In addition, the discrepancy between our sharp
characterization and the minimax lower bound makes clear that Q-learning is
not minimax optimal when $|\mathcal{A}|\geq 2$, and is outperformed by, say,
the model-based approaches (Agarwal et al.,, 2020; Li et al.,, 2020) in terms
of the sample efficiency.

Our results cover both rescaled linear and constant learning rates; see Table
1 for more detailed comparisons with previous literature. On the technical
side, (i) our analysis for the upper bound relies on a sort of crucial error
decompositions and variance control that are previously unexplored, which
might shed light on how to pin down the finite-sample efficacy of other
variants of Q-learning such as double Q-learning; (ii) the development of our
lower bound, which is inspired by Azar et al., (2013); Wainwright, 2019c ,
puts the negative impact of over-estimation on sample efficiency on a rigorous
footing.

Finally, we extend our analysis framework to accommodate the asynchronous
setting, in which the samples are non-i.i.d. and take the form of a single
Markovian trajectory. We show for the first time that the sample complexity of
asynchronous Q-learning exhibits a $\frac{1}{(1-\gamma)^{4}}$ scaling w.r.t.
the effective horizon, improving upon the prior state-of-the-art Li et al.,
2021b .

###  1.2 Related works

There is a growing literature dedicated to analyzing the non-asymptotic
behavior of value-based model-free RL algorithms in a variety of scenarios. In
the discussion below, we subsample the literature and discuss a couple of
papers that are the closest to ours.

##### Finite-sample $\ell_{\infty}$-based guarantees for synchronous
Q-learning and TD learning.

The sample complexities derived in prior literature often rely crucially on
the choices of learning rates. Even-Dar and Mansour, (2003) studied the sample
complexity of Q-learning with linear learning rates $1/t$ or polynomial
learning rates $1/t^{\omega}$, which scales as
$\widetilde{O}(\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{5}\varepsilon^{2.5}})$
when optimized w.r.t. the effective horizon (attained when $\omega=4/5$). The
resulting sample complexity, however, is sub-optimal in terms of its
dependency on not only $\frac{1}{1-\gamma}$ but also the target accuracy level
$\varepsilon$. Beck and Srikant, (2012) investigated the case of constant
learning rates; however, their result suffered from an additional factor of
$|\mathcal{S}||\mathcal{A}|$, which could be prohibitively large in practice.
More recently, Wainwright, 2019b ; Chen et al., (2020) further analyzed the
sample complexity of Q-learning with either constant learning rates or
linearly rescaled learning rates, leading to the state-of-the-art bound
$\widetilde{O}\big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{5}\varepsilon^{2}}\big{)}$.
However, this result remains sub-optimal in terms of its scaling with
$\frac{1}{1-\gamma}$. See Table 1 for details. In the special case with
$|\mathcal{A}|=1$, the recent works Khamaru et al., (2020); Mou et al., (2020)
developed instance-dependent results for TD learning with Polyak-Ruppert
averaging, and studied the local (sub)-optimality of TD learning in a
different local minimax framework.

##### Finite-sample $\ell_{\infty}$-based guarantees for asynchronous
Q-learning and TD learning.

Moving beyond the synchronous model, Even-Dar and Mansour, (2003); Beck and
Srikant, (2012); Qu and Wierman, (2020); Li et al., 2021b ; Shah and Xie,
(2018); Chen et al., (2021) developed non-asymptotic convergence guarantees
for the asynchronous setting, where the data samples take the form of a single
Markovian trajectory (following some behavior policy) and only a single state-
action pair is updated in each iteration. A similar scaling of
$\widetilde{O}\big{(}\frac{1}{(1-\gamma)^{5}}\big{)}$ also showed up in the
state-of-the-art sample complexity bounds for asynchronous Q-learning (Li et
al., 2021b, ), and our theory is the first to sharpen it to
$\widetilde{O}\big{(}\frac{1}{(1-\gamma)^{4}}\big{)}$. When it comes to the
special case with $|\mathcal{A}|=1$, the non-asymptotic performance guarantees
TD learning with Markovian sample trajectories (assuming that the behavior
policy coincides with the target policy) have been recently derived by
Bhandari et al., (2021); Srikant and Ying, (2019); Mou et al., (2020).

##### Finite-sample $\ell_{\infty}$-based guarantees of other Q-learning
variants.

With the aim of alleviating the sub-optimal dependency on the effective
horizon in vanilla Q-learning and improving sample efficiency, several
variants of Q-learning have been proposed and analyzed. Azar et al., (2011)
proposed speedy Q-learning, which achieves a sample complexity of
$\widetilde{O}\big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\varepsilon^{2}}\big{)}$
at the expense of doubling the computation and storage complexity. Our result
on vanilla Q-learning matches that of speedy Q-learning in an order-wise
sense. In addition, Wainwright, 2019c  proposed a variance-reduced Q-learning
algorithm that is shown to be minimax optimal in the range $\epsilon\in(0,1)$
with a sample complexity
$\widetilde{O}\big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}\big{)}$,
which was subsequently generalized to the asynchronous setting by Li et al.,
2021b . The $\ell_{\infty}$ statistical bounds for variance-reduced TD
learning have been investigated in Khamaru et al., (2020) for the synchronous
setting, and in Li et al., 2021b  for the asynchronous setting. Last but not
least, Xiong et al., (2020) established the finite-sample convergence of
double Q-learning following the framework of Even-Dar and Mansour, (2003);
however, it is unclear whether double Q-learning can provably outperform
vanilla Q-learning in terms of the sample efficiency.

##### Others.

There are also several other strands of related papers that tackle model-free
algorithms but do not pursue $\ell_{\infty}$-based non-asymptotic guarantees.
For instance, Bhandari et al., (2018); Lakshminarayanan and Szepesvari,
(2018); Srikant and Ying, (2019); Gupta et al., (2019); Doan et al., (2019);
Wu et al., (2020); Xu et al., 2019a ; Chen et al., (2019); Xu et al., 2019b
developed finite-sample (weighted) $\ell_{2}$ convergence guarantees for
several model-free algorithms, which also allow one to accommodate linear
function approximation as well as off-policy evaluation. Another line of
recent work (Jin et al.,, 2018; Li et al., 2021a, ; Bai et al.,, 2019; Zhang
et al.,, 2020) considered the sample efficiency of Q-learning type algorithms
paired with proper exploration strategies (e.g., upper confidence bounds)
under the framework of regret analysis. The asymptotic behaviors of some
variants of Q-learning, e.g., double Q-learning (Weng et al., 2020b, ) and
relative Q-learning (Devraj and Meyn,, 2020) are also studied. The effect of
more general function approximation schemes (e.g., certain families of neural
network approximations) has been studied in Fan et al., (2019); Murphy,
(2005); Cai et al., (2019); Wai et al., (2019); Xu and Gu, (2020) as well.
These are beyond the scope of the present paper.

##  2 Background and algorithms

This paper concentrates on discounted infinite-horizon MDPs (Bertsekas,,
2017). We shall start by introducing some basics of tabular MDPs, followed by
a description of both Q-learning and TD learning. Throughout this paper, we
denote by $\mathcal{S}=\\{1,\cdots,|\mathcal{S}|\\}$ and
$\mathcal{A}=\\{1,\cdots,|\mathcal{A}|\\}$ the state space and the action
space of the MDP, respectively, and let $\Delta(\mathcal{S})$ represent the
probability simplex over the set $\mathcal{S}$.

##### Basics of discounted infinite-horizon MDPs.

Consider an infinite-horizon MDP as represented by a quintuple
$\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\gamma)$, where $\gamma\in(0,1)$
indicates the discount factor,
$P:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ represents the
probability transition kernel (i.e., $P(s^{\prime}\,|\,{s,a})$ is the
probability of transiting to state $s^{\prime}$ from a state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$), and
$r:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ stands for the reward
function (i.e., $r(s,a)$ is the immediate reward collected in state
$s\in\mathcal{S}$ when action $a\in\mathcal{A}$ is taken). Note that the
immediate rewards are assumed to lie within $[0,1]$ throughout this paper.
Moreover, we let $\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ represent a
policy, so that $\pi(\cdot\,|\,s)\in\Delta(\mathcal{A})$ specifies the
(possibly randomized) action selection rule in state $s$. If $\pi$ is a
deterministic policy, then we denote by $\pi(s)$ the action selected by $\pi$
in state $s$.

A common objective in RL is to maximize a sort of long-term rewards called
value functions or Q-functions. Specifically, given a policy $\pi$, the
associated value function and Q-function of $\pi$ are defined respectively by

$\displaystyle
V^{\pi}(s)\coloneqq\mathbb{E}\left[\sum_{k=0}^{\infty}\gamma^{k}r(s_{k},a_{k})\,\Big{|}\,s_{0}=s\right]$

for all $s\in\mathcal{S}$, and

$Q^{\pi}(s,a)\coloneqq\mathbb{E}\left[\sum_{k=0}^{\infty}\gamma^{k}r(s_{k},a_{k})\,\Big{|}\,s_{0}=s,a_{0}=a\right]$

for all $(s,a)\in\mathcal{S}\times\mathcal{A}$. Here,
$\\{(s_{k},a_{k})\\}_{k\geq 0}$ is a trajectory of the MDP induced by the
policy $\pi$ (except $a_{0}$ when evaluating the Q-function), and the
expectations are evaluated with respect to the randomness of the MDP
trajectory. Given that the immediate rewards fall within $[0,1]$, it can be
straightforwardly verified that $0\leq V^{\pi}(s)\leq\frac{1}{1-\gamma}$ and
$0\leq Q^{\pi}(s,a)\leq\frac{1}{1-\gamma}$ for any $\pi$ and any state-action
pair $(s,a)$. The optimal value function $V^{\star}$ and optimal Q-function
$Q^{\star}$ are defined respectively as

$V^{\star}(s)\coloneqq\max_{\pi}V^{\pi}(s),\qquad
Q^{\star}(s,a)\coloneqq\max_{\pi}Q^{\pi}(s,a)$

for any state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$. It is well
known that there exists a deterministic optimal policy, denoted by
$\pi^{\star}$, that attains $V^{\star}(s)$ and $Q^{\star}(s,a)$ simultaneously
for all $(s,a)\in\mathcal{S}\times\mathcal{A}$ (Sutton and Barto,, 2018).

##### Algorithms: Q-learning and TD learning (the synchronous setting).

The synchronous setting assumes access to a generative model (Kearns and
Singh,, 1999; Sidford et al.,, 2018) such that: in each iteration $t$, we
collect an independent sample $s_{t}(s,a)\sim P(\cdot\,|\,s,a)$ for every
state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$.

With this sampling model in place, the Q-learning algorithm (Watkins and
Dayan,, 1992) maintains a Q-function estimate
$Q_{t}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$ for all $t\geq 0$;
in each iteration $t$, the algorithm updates all entries of the Q-function
estimate at once via the following update rule

$Q_{t}=(1-\eta_{t})Q_{t-1}+\eta_{t}\mathcal{T}_{t}(Q_{t-1}).$ (4)

Here, $\eta_{t}\in(0,1]$ denotes the learning rate or the step size in the
$t$-th iteration, and $\mathcal{T}_{t}$ denotes the empirical Bellman operator
constructed by samples collected in the $t$-th iteration, i.e.,

$\displaystyle\mathcal{T}_{t}(Q)(s,a)$ $\displaystyle\coloneqq
r(s,a)+\gamma\max_{a^{\prime}\in\mathcal{A}}Q(s_{t},a^{\prime}),\qquad
s_{t}\equiv s_{t}(s,a)\sim P(\cdot\,|\,s,a)$ (5)

for each state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$. Obviously,
$\mathcal{T}_{t}$ is an unbiased estimate of the celebrated Bellman operator
$\mathcal{T}$ given by

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

Note that the optimal Q-function $Q^{\star}$ is the unique fixed point of the
Bellman operator (Bellman,, 1952), that is,
$\mathcal{T}(Q^{\star})=Q^{\star}$. Viewed in this light, synchronous
Q-learning can be interpreted as a stochastic approximation scheme (Robbins
and Monro,, 1951) aimed at solving this fixed-point equation. Throughout this
work, we initialize the algorithm in a way that obeys $0\leq
Q_{0}(s,a)\leq\frac{1}{1-\gamma}$ for every state-action pair $(s,a)$. In
addition, the corresponding value function estimate
$V_{t}:\mathcal{S}\rightarrow\mathbb{R}$ in the $t$-th iteration is defined as

$\displaystyle\forall s\in\mathcal{S}:\qquad
V_{t}(s):=\max_{a\in\mathcal{A}}Q_{t}(s,a).$ (6)

The complete description of Q-learning is summarized in Algorithm 1.

1: inputs: learning rates $\\{\eta_{t}\\}$, number of iterations $T$, discount
factor $\gamma$, initial estimate $Q_{0}$.

2: for $t=1,2,\cdots,T$ do

3: Draw $s_{t}(s,a)\sim P(\cdot\,|\,s,a)$ for each
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

4: Compute $Q_{t}$ according to (4) and (5).

5: end for

Algorithm 1 Synchronous Q-learning for infinite-horizon discounted MDPs.

As it turns out, TD learning (Sutton,, 1988; Tsitsiklis and Van Roy,, 1997;
Bhandari et al.,, 2021) in the synchronous setting can be viewed as a special
instance of Q-learning when the action set $\mathcal{A}$ is a singleton (i.e.,
$|\mathcal{A}|=1$). In such a case, the MDP reduces to a Markov reward process
(MRP) (Bertsekas,, 2017), and we shall abuse the notation to use
$P:\mathcal{S}\rightarrow\Delta(\mathcal{S})$ to describe the probability
transition kernel, and employ $r:\mathcal{S}\rightarrow[0,1]$ to represent the
reward function (with $r(s)$ indicating the immediate reward gained in state
$s$). The TD learning algorithm maintains an estimate
$V_{t}:\mathcal{S}\rightarrow\mathbb{R}$ of the value function in each
iteration $t$,111There is no need to maintain additional Q-estimates, as the
Q-function and the value function coincide when $|\mathcal{A}|=1$.  and
carries out the following iterative update rule

$\displaystyle V_{t}(s)$
$\displaystyle=(1-\eta_{t})V_{t-1}(s)+\eta_{t}\big{(}r(s)+\gamma
V_{t-1}(s_{t})\big{)},\qquad s_{t}\equiv s_{t}(s)\sim P(\cdot\,|\,s)$ (7)

for each state $s\in\mathcal{S}$. As before, $\eta_{t}\in(0,1]$ is the
learning rate at time $t$, the initial estimate $V_{0}(s)$ is taken to be
within $\big{[}0,\frac{1}{1-\gamma}\big{]}$, and in each iteration, the
samples $\\{s_{t}(s)\,|\,s\in\mathcal{S}\\}$ are generated independently. The
whole algorithm of TD learning is summarized in Algorithm 2.

1: inputs: learning rates $\\{\eta_{t}\\}$, number of iterations $T$, discount
factor $\gamma$, initial estimate $V_{0}$.

2: for $t=1,2,\cdots,T$ do

3: Draw $s_{t}(s)\sim P(\cdot\,|\,s)$ for each $s\in\mathcal{S}$.

4: Compute $V_{t}$ according to (7).

5: end for

Algorithm 2 Synchronous TD learning for infinite-horizon discounted MRPs.

Finally, while synchronous Q-learning is the main focal point of this paper,
we shall also discuss extension to the asynchronous Q-learning, which we will
elaborate on in Section 5.

##  3 Main results: sample complexity of synchronous Q-learning

With the above backgrounds in place, we are in a position to state formally
our main findings in this section, concentrating on the synchronous setting.

###  3.1 Minimax optimality of TD learning

We start with the special with $|\mathcal{A}|=1$ and characterize the
$\ell_{\infty}$-based sample complexity of synchronous TD learning.

######  Theorem 1.

Consider any $\delta\in(0,1)$, $\varepsilon\in(0,1]$, and $\gamma\in[1/2,1)$.
Suppose that for any $0\leq t\leq T$, the learning rates satisfy

$\frac{1}{1+\frac{c_{1}(1-\gamma)T}{\log^{2}T}}\leq\eta_{t}\leq\frac{1}{1+\frac{c_{2}(1-\gamma)t}{\log^{2}T}}$
(8a) for some small enough universal constants $c_{1}\geq c_{2}>0$. Assume
that the total number of iterations $T$ obeys
$T\geq\frac{c_{3}\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}|T}{\delta}\big{)}}{(1-\gamma)^{3}\varepsilon^{2}}$
(8b) for some sufficiently large universal constant $c_{3}>0$.

If the initialization obeys $0\leq{V}_{0}(s)\leq\frac{1}{1-\gamma}$ for all
$s\in\mathcal{S}$, then with probability at least $1-\delta$, Algorithm 2
achieves

$\max_{s\in\mathcal{S}}\big{|}{V}_{T}(s)-{V}^{\star}(s)\big{|}\leq\varepsilon.$

######  Remark 1.

This high-probability bound immediately translates to a mean estimation error
guarantee. Recognizing the crude upper bound
$\big{|}{V}_{T}(s)-{V}^{\star}(s)\big{|}\leq\frac{1}{1-\gamma}$ (see (97) in
Section C.1) and taking $\delta\leq{\varepsilon(1-\gamma)}$, we reach

$\mathbb{E}\Big{[}\max_{s}\big{|}{V}_{T}(s)-{V}^{\star}(s)\big{|}\Big{]}\leq\varepsilon(1-\delta)+\delta\frac{1}{1-\gamma}\leq
2\varepsilon,$ (9)

provided that
$T\geq\frac{c_{3}(\log^{3}T)\big{(}\log\frac{|\mathcal{S}|T}{\varepsilon(1-\gamma)}\big{)}}{(1-\gamma)^{3}\varepsilon^{2}}$.

Given that each iteration of synchronous TD learning makes use of
$|\mathcal{S}|$ samples, Theorem 1 implies that the sample complexity of TD
learning is at most

$\widetilde{O}\bigg{(}\frac{|\mathcal{S}|}{(1-\gamma)^{3}\varepsilon^{2}}\bigg{)}$
(10)

for any target accuracy level $\varepsilon\in(0,1]$. This non-asymptotic
result is valid as long as the learning rates are chosen to be either a proper
constant or rescaled linear (see (8a)). Compared to a large number of prior
works studying the performance of TD learning (Borkar and Meyn,, 2000;
Bhandari et al.,, 2021; Khamaru et al.,, 2021; Wainwright, 2019b, ; Chen et
al.,, 2020; Lakshminarayanan and Szepesvari,, 2018), Theorem 1 strengthens
prior results by uncovering an improved scaling (i.e.,
$\frac{1}{(1-\gamma)^{3}}$) in the effective horizon. In fact, prior results
on plain TD learning were only able to obtain a scaling as
$\frac{1}{(1-\gamma)^{5}}$ (Wainwright, 2019b, ).

To assess the tightness of the above result, we take a moment to compare it
with the minimax lower bound recently established in the context of value
function estimation. Specifically, Pananjady and Wainwright, (2020, Theorem
2(b)) asserted that no algorithm whatsoever can obtain an entrywise
$\varepsilon$ approximation of the value function—in a minimax sense—unless
the total sample size exceeds

$\widetilde{\Omega}\bigg{(}\frac{|\mathcal{S}|}{(1-\gamma)^{3}\varepsilon^{2}}\bigg{)}.$
(11)

In turn, this taken together with Theorem 1 unveils the minimax optimality of
the sample complexity (modulo some logarithmic factor) of TD learning for the
synchronous setting. While prior works have demonstrated how to attain the
minimax limit (11) using model-based methods or variance-reduced model-free
algorithms (e.g., Azar et al., (2013); Pananjady and Wainwright, (2020); Li et
al., (2020); Khamaru et al., (2021)), our theory provides the first rigorous
evidence that plain TD learning alone is already minimax optimal, without the
need of Polyak-Ruppert averaging or variance reduction.

###  3.2 Tight sample complexity and sub-optimality of Q-learning

Next, we move on to the more general case with $|\mathcal{A}|\geq 2$ and study
the performance of Q-learning. As it turns out, Q-learning with
$|\mathcal{A}|\geq 2$ is considerably more challenging to analyze than the TD
learning case, due to the presence of the nonsmooth max operator. Our
$\ell_{\infty}$-based sample complexity bound for Q-learning is summarized as
follows, strengthening the state-of-the-art results.

######  Theorem 2.

Consider any $\delta\in(0,1)$, $\varepsilon\in(0,1]$, and $\gamma\in[1/2,1)$.
Suppose that for any $0\leq t\leq T$, the learning rates satisfy

$\frac{1}{1+\frac{c_{1}(1-\gamma)T}{\log^{3}T}}\leq\eta_{t}\leq\frac{1}{1+\frac{c_{2}(1-\gamma)t}{\log^{3}T}}$
(12a) for some small enough universal constants $c_{1}\geq c_{2}>0$. Assume
that the total number of iterations $T$ obeys
$T\geq\frac{c_{3}\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{4}\varepsilon^{2}}$
(12b) for some sufficiently large universal constant $c_{3}>0$.

If the initialization obeys $0\leq{Q}_{0}(s,a)\leq\frac{1}{1-\gamma}$ for any
$(s,a)\in\mathcal{S}\times\mathcal{A}$, then Algorithm 1 achieves

$\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}\big{|}{Q}_{T}(s,a)-{Q}^{\star}(s,a)\big{|}\leq\varepsilon$

with probability at least $1-\delta$.

######  Remark 2.

Repeating exactly the same argument as in Remark 1, one can readily translate
this high-probability bound into the following mean estimation error
guarantee:

$\mathbb{E}\Big{[}\max_{s,a}\big{|}{Q}_{T}(s,a)-{Q}^{\star}(s,a)\big{|}\Big{]}\leq\varepsilon(1-\delta)+\delta\frac{1}{1-\gamma}\leq
2\varepsilon,$ (13)

holds as long as
$T\geq\frac{c_{3}(\log^{4}T)\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\varepsilon(1-\gamma)}\big{)}}{(1-\gamma)^{4}\varepsilon^{2}}$.

In a nutshell, Theorem 2 develops a non-asymptotic bound on the iteration
complexity of Q-learning in the presence of the synchronous model. A few
remarks and implications are in order.

##### Sample complexity and sharpened dependency on $\frac{1}{1-\gamma}$.

Recognizing that $|\mathcal{S}||\mathcal{A}|$ independent samples are drawn in
each iteration, we can see from Theorem 2 the following sample complexity
bound

$\widetilde{O}\Big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\varepsilon^{2}}\Big{)}$
(14)

in order for Q-learning to attain $\varepsilon$-accuracy ($0<\varepsilon<1$)
in an entrywise sense. To the best of our knowledge, this is the first result
that breaks the
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{5}\varepsilon^{2}}$ barrier
that is present in all state-of-the-art analyses for vanilla Q-learning (Beck
and Srikant,, 2012; Wainwright, 2019b, ; Chen et al.,, 2020; Qu and Wierman,,
2020; Li et al., 2021b, ).

##### Learning rates.

Akin to the TD learning case, our result accommodates two commonly adopted
learning rate schemes (cf. (12a)): (i) linearly rescaled learning rates
$\frac{1}{1+\frac{c_{2}(1-\gamma)}{\log^{2}T}t}$, and (ii) iteration-invariant
learning rates $\frac{1}{1+\frac{c_{1}(1-\gamma)T}{\log^{2}T}}$ (which depend
on the total number of iterations $T$ but not the iteration number $t$). In
particular, when the sample size is
$T=\frac{c_{3}(\log^{4}T)\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{4}\varepsilon^{2}}$,
the constant learning rates can be taken to be on the order of

$\eta_{t}\equiv\widetilde{O}\big{(}(1-\gamma)^{3}\varepsilon^{2}\big{)},\qquad
0\leq t\leq T,$

which depends almost solely on the discount factor $\gamma$ and the target
accuracy $\varepsilon$. Interestingly, both learning rate schedules lead to
the same $\ell_{\infty}$-based sample complexity bound (in an order-wise
sense), making them appealing for practical use.

##### A matching lower bound and sub-optimality.

The careful reader might remark that there remains a gap between our sample
complexity bound for Q-learning and the minimax lower bound (Azar et al.,,
2013). More specifically, the minimax lower bound scales on the order of
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}$ and is
achievable — up to some logarithmic factor — by the model-based approach and
variance-reduced methods (Azar et al.,, 2013; Agarwal et al.,, 2020; Li et
al.,, 2020; Wainwright, 2019c, ). This raises natural questions regarding
whether our sample complexity bound can be further improved, and whether there
is any intrinsic bottleneck that prevents vanilla Q-learning from attaining
optimal performance. To answer these questions, we develop the following
algorithm-dependent lower bound, which confirms the sharpness of Theorem 2 and
reveals the sub-optimality of vanilla Q-learning.

######  Theorem 3.

Assume that $3/4\leq\gamma<1$ and that $T\geq\frac{c_{3}}{(1-\gamma)^{2}}$ for
some sufficiently large constant $c_{3}>0$. Suppose that the initialization is
$Q_{0}\equiv 0$, and that the learning rates are taken to be either (i)
$\eta_{t}=\frac{1}{1+c_{\eta}(1-\gamma)t}$ for all $t\geq 0$, or (ii)
$\eta_{t}\equiv\eta$ for all $t\geq 0$. There exists a $\gamma$-discounted MDP
with $|\mathcal{S}|=4$ and $|\mathcal{A}|=2$ such that Algorithm 1 — with any
$c_{\eta}>0$ and any $\eta\in(0,1)$ — obeys

$\max_{s}\mathbb{E}\Big{[}\big{|}V_{T}(s)-V^{\star}(s)\big{|}^{2}\Big{]}\geq\frac{c_{\mathsf{lb}}}{(1-\gamma)^{4}T\log^{2}T},$

where $c_{\mathsf{lb}}>0$ is some universal constant.

As asserted by this theorem, it is impossible for Q-learning to attain
$\varepsilon$-accuracy (in the sense that
$\max_{s}\mathbb{E}\big{[}\big{|}V_{T}(s)-V^{\star}(s)\big{|}^{2}\big{]}\leq\varepsilon^{2}$)
unless the number of iterations exceeds the order of

$\frac{1}{(1-\gamma)^{4}\varepsilon^{2}}$

up to some logarithmic factor. Consequently, the upper bound in Theorem 2 is
tight in terms of its dependency on the effective horizon
$\frac{1}{1-\gamma}$, which is larger than the minimax limit (Azar et al.,,
2013) by a factor of $\frac{1}{1-\gamma}$. As a consequence, we need to resort
to more sophisticated tricks like variance reduction in order to attain
minimax optimality when $|\mathcal{A}|\geq 2$ (Wainwright, 2019c, ; Li et al.,
2021b, ).

##  4 Key analysis ideas (the synchronous case)

This section outlines the key ideas for the establishment of our main results
of Q-learning for the synchronous case, namely Theorem 2 and Theorem 3. The
proof for TD learning is deferred to Appendix C. Before delving into the proof
details, we first introduce convenient vector and matrix notation that shall
be used frequently.

###  4.1 Vector and matrix notation

To begin with, for any matrix $\bm{M}$, the notation
$\|\bm{M}\|_{1}:=\max_{i}\sum_{j}|M_{i,j}|$ is defined as the largest row-wise
$\ell_{1}$ norm of $\bm{M}$. For any vector
$\bm{a}=[a_{i}]_{i=1}^{n}\in\mathbb{R}^{n}$, we define $\sqrt{\cdot}$ and
$|\cdot|$ in a coordinate-wise manner, i.e.
$\sqrt{\bm{a}}:=[\sqrt{a_{i}}\,]_{i=1}^{n}\in\mathbb{R}^{n}$ and
$|\bm{a}|:=[|a_{i}|]_{i=1}^{n}\in\mathbb{R}^{n}$. For a set of vectors
$\bm{a}_{1},\cdots,\bm{a}_{m}\in\mathbb{R}^{n}$ with
$\bm{a}_{k}=[a_{k,j}]_{j=1}^{n}$ ($1\leq k\leq m$), we define the $\max$
operator in an entrywise fashion such that $\max_{1\leq k\leq
m}\bm{a}_{k}\coloneqq[\max_{k}a_{k,j}]_{j=1}^{n}$. For any vectors
$\bm{a}=[a_{i}]_{i=1}^{n}\in\mathbb{R}^{n}$ and
$\bm{b}=[b_{i}]_{i=1}^{n}\in\mathbb{R}^{n}$, the notation $\bm{a}\leq\bm{b}$
(resp. $\bm{a}\geq\bm{b}$) means $a_{i}\leq b_{i}$ (resp. $a_{i}\geq b_{i}$)
for all $1\leq i\leq n$. We also let
$\bm{a}\circ\bm{b}=[a_{i}b_{i}]_{i=1}^{n}$ denote the Hadamard product. In
addition, we denote by $\bm{1}$ (resp. $\bm{e}_{i}$) the all-one vector (resp.
the $i$-th standard basis vector), and let $\bm{I}$ be the identity matrix.

We shall also introduce the matrix
$\bm{P}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}|}$ to
represent the probability transition kernel $P$, whose $(s,a)$-th row
$\bm{P}_{s,a}$ is a probability vector representing $P(\cdot\,|\,s,a)$.
Additionally, we define the square probability transition matrix
$\bm{P}^{\pi}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|}$
(resp. $\bm{P}_{\pi}\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}|}$) induced
by a deterministic policy $\pi$ over the state-action pairs (resp. states) as
follows:

$\bm{P}^{\pi}\coloneqq\bm{P}\bm{\Pi}^{\pi}\qquad\text{and}\qquad\bm{P}_{\pi}\coloneqq\bm{\Pi}^{\pi}\bm{P},$
(15)

where
$\bm{\Pi}^{\pi}\in\\{0,1\\}^{|\mathcal{S}|\times|\mathcal{S}||\mathcal{A}|}$
is a projection matrix associated with the deterministic policy $\pi$:

$\displaystyle\bm{\Pi}^{\pi}$
$\displaystyle=\begin{pmatrix}\bm{e}_{\pi(1)}^{\top}\\\
&\bm{e}_{\pi(2)}^{\top}\\\ &&\ddots\\\
&&&\bm{e}_{\pi(|\mathcal{S}|)}^{\top}\end{pmatrix}$ (16)

with $\bm{e}_{i}$ the $i$-th standard basis vector. Moreover, for any vector
$\bm{V}\in\mathbb{R}^{|\mathcal{S}|}$, we define
$\mathsf{Var}_{\bm{P}}(\bm{V})\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$ as
follows:

$\displaystyle\mathsf{Var}_{\bm{P}}(\bm{V})=\bm{P}(\bm{V}\circ\bm{V})-(\bm{P}\bm{V})\circ(\bm{P}\bm{V}).$
(17)

In other words, the $(s,a)$-th entry of $\mathsf{Var}_{\bm{P}}(\bm{V})$
corresponds to the variance $\mathsf{Var}_{s^{\prime}\sim
P(\cdot|s,a)}(V(s^{\prime}))$ w.r.t. the distribution $P(\cdot\,|\,s,a)$.

Moreover, we use the vector $\bm{r}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$
to represent the reward function $r$, so that for any
$(s,a)\in\mathcal{S}\times\mathcal{A}$, the $(s,a)$-th entry of $\bm{r}$ is
given by $r(s,a)$. Analogously, we shall employ the vectors
$\bm{V}^{\pi}\in\mathbb{R}^{|\mathcal{S}|}$,
$\bm{V}^{\star}\in\mathbb{R}^{|\mathcal{S}|}$,
$\bm{V}_{t}\in\mathbb{R}^{|\mathcal{S}|}$,
$\bm{Q}^{\pi}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$,
$\bm{Q}^{\star}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$ and
$\bm{Q}_{t}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$ to represent $V^{\pi}$,
$V^{\star}$, $V_{t}$, $Q^{\pi}$, $Q^{\star}$ and $Q_{t}$, respectively.
Additionally, we define $\pi_{t}$ to be the policy associated with $Q_{t}$
such that for any state-action pair $(s,a)$,

$\displaystyle\pi_{t}(s)=\min\Big{\\{}a^{\prime}\,\big{|}\,Q_{t}(s,a^{\prime})=\max_{a^{\prime\prime}}Q_{t}(s,a^{\prime\prime})\Big{\\}}.$
(18)

In other words, for any $s\in\mathcal{S}$, the policy $\pi_{t}$ picks out the
smallest indexed action that attains the largest Q-value in the estimate
$Q_{t}(s,\cdot)$. As an immediate consequence, one can easily verify

$Q_{t}\big{(}s,\pi_{t}(s)\big{)}=V_{t}(s)\qquad\text{and}\qquad\bm{P}\bm{V}_{t}=\bm{P}^{\pi_{t}}\bm{Q}_{t}\geq\bm{P}^{\pi}\bm{Q}_{t}$
(19)

for any $\pi,$ where $\bm{P}^{\pi}$ is defined in (15). Further, we introduce
a matrix
$\bm{P}_{t}\in\\{0,1\\}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}|}$ such
that

$\bm{P}_{t}\big{(}(s,a),s^{\prime}\big{)}:=\begin{cases}1,&\text{if
}s^{\prime}=s_{t}(s,a)\\\ 0,&\text{otherwise}\end{cases}$ (20)

for any $(s,a)$, which is an empirical transition matrix constructed using
samples collected in the $t$-th iteration.

Finally, let
$\mathcal{X}\coloneqq\big{(}|\mathcal{S}|,|\mathcal{A}|,\frac{1}{1-\gamma},\frac{1}{\varepsilon}\big{)}$.
The notation $f(\mathcal{X})=O(g(\mathcal{X}))$ or $f(\mathcal{X})\lesssim
g(\mathcal{X})$ (resp. $f(\mathcal{X})\gtrsim g(\mathcal{X})$) means that
there exists a universal constant $C_{0}>0$ such that $|f(\mathcal{X})|\leq
C_{0}|g(\mathcal{X})|$ (resp. $|f(\mathcal{X})|\geq C_{0}|g(\mathcal{X})|$).
The notation $f(\mathcal{X})\asymp g(\mathcal{X})$ means
$f(\mathcal{X})\lesssim g(\mathcal{X})$ and $f(\mathcal{X})\gtrsim
g(\mathcal{X})$ hold simultaneously. We define $\widetilde{O}(\cdot)$ in the
same way as $O(\cdot)$ except that it hides logarithmic factors.

###  4.2 Proof outline for Theorem 2

We are now positioned to describe how to establish Theorem 2, towards which we
first express the Q-learning update rule (4) and (5) using the above matrix
notation. As can be easily verified, Q-learning employs the samples in
$\bm{P}_{t}$ (cf. (20)) to perform the following update

$\displaystyle\bm{Q}_{t}$
$\displaystyle=(1-\eta_{t})\bm{Q}_{t-1}+\eta_{t}(\bm{r}+\gamma\bm{P}_{t}\bm{V}_{t-1})$
(21)

in the $t$-th iteration. In the sequel, we denote by

$\bm{\Delta}_{t}\coloneqq\bm{Q}_{t}-\bm{Q}^{\star}$ (22)

the error of the Q-function estimate in the $t$-th iteration.

####  4.2.1 Basic decomposition

We start by decomposing the estimation error term $\bm{\Delta}_{t}$. In view
of the update rule (21), we arrive at the following elementary decomposition:

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle=\bm{Q}_{t}-\bm{Q}^{\star}=(1-\eta_{t})\bm{Q}_{t-1}+\eta_{t}\big{(}\bm{r}+\gamma\bm{P}_{t}\bm{V}_{t-1}\big{)}-\bm{Q}^{\star}$
$\displaystyle=(1-\eta_{t})\big{(}\bm{Q}_{t-1}-\bm{Q}^{\star}\big{)}+\eta_{t}\big{(}\bm{r}+\gamma\bm{P}_{t}\bm{V}_{t-1}-\bm{Q}^{\star}\big{)}$
$\displaystyle=(1-\eta_{t})\bm{\Delta}_{t-1}+\eta_{t}\gamma\big{(}\bm{P}_{t}\bm{V}_{t-1}-\bm{P}\bm{V}^{\star}\big{)}$
$\displaystyle=(1-\eta_{t})\bm{\Delta}_{t-1}+\eta_{t}\gamma\big{\\{}\bm{P}(\bm{V}_{t-1}-\bm{V}^{\star})+(\bm{P}_{t}-\bm{P})\bm{V}_{t-1}\big{\\}},$
(23)

where the third line exploits the Bellman equation
$\bm{Q}^{\star}=\bm{r}+\gamma\bm{P}\bm{V}^{\star}$. Further, the term
$\bm{P}(\bm{V}_{t-1}-\bm{V}^{\star})$ can be linked with $\bm{\Delta}_{t-1}$
using the definition (18) of $\pi_{t}$ as follows

$\displaystyle\bm{P}(\bm{V}_{t-1}-\bm{V}^{\star})$
$\displaystyle=\bm{P}^{\pi_{t-1}}\bm{Q}_{t-1}-\bm{P}^{\pi^{\star}}\bm{Q}^{\star}\leq\bm{P}^{\pi_{t-1}}\bm{Q}_{t-1}-\bm{P}^{\pi_{t-1}}\bm{Q}^{\star}=\bm{P}^{\pi_{t-1}}\bm{\Delta}_{t-1},$
(24a) $\displaystyle\bm{P}(\bm{V}_{t-1}-\bm{V}^{\star})$
$\displaystyle=\bm{P}^{\pi_{t-1}}\bm{Q}_{t-1}-\bm{P}^{\pi^{\star}}\bm{Q}^{\star}\geq\bm{P}^{\pi^{\star}}\bm{Q}_{t-1}-\bm{P}^{\pi^{\star}}\bm{Q}^{\star}=\bm{P}^{\pi^{\star}}\bm{\Delta}_{t-1},$
(24b)

where we have made use of the relation (19). Substitute (24) into (23) to
reach

$\displaystyle\begin{array}[]{l}\bm{\Delta}_{t}\leq(1-\eta_{t})\bm{\Delta}_{t-1}+\eta_{t}\gamma\big{\\{}\bm{P}^{\pi_{t-1}}\bm{\Delta}_{t-1}+(\bm{P}_{t}-\bm{P})\bm{V}_{t-1}\big{\\}};\\\
\bm{\Delta}_{t}\geq(1-\eta_{t})\bm{\Delta}_{t-1}+\eta_{t}\gamma\big{\\{}\bm{P}^{\pi^{\star}}\bm{\Delta}_{t-1}+(\bm{P}_{t}-\bm{P})\bm{V}_{t-1}\big{\\}}.\end{array}$
(27)

Applying these relations recursively, we obtain

$\displaystyle\begin{array}[]{l}\bm{\Delta}_{t}\leq\eta_{0}^{(t)}\bm{\Delta}_{0}+\sum\limits_{i=1}^{t}\eta_{i}^{(t)}\gamma\big{\\{}\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}+(\bm{P}_{i}-\bm{P})\bm{V}_{i-1}\big{\\}},\\\
\bm{\Delta}_{t}\geq\eta_{0}^{(t)}\bm{\Delta}_{0}+\sum\limits_{i=1}^{t}\eta_{i}^{(t)}\gamma\big{\\{}\bm{P}^{\pi^{\star}}\bm{\Delta}_{i-1}+(\bm{P}_{i}-\bm{P})\bm{V}_{i-1}\big{\\}},\end{array}$
(30)

where we define

$\eta_{i}^{(t)}\coloneqq\begin{cases}\prod_{j=1}^{t}(1-\eta_{j}),&\text{if
}i=0,\\\ \eta_{i}\prod_{j=i+1}^{t}(1-\eta_{j}),&\text{if }0<i<t,\\\
\eta_{t},&\text{if }i=t.\end{cases}$ (31)

##### Comparisons to prior approaches.

We take a moment to discuss how prior analyses handle the above elementary
decomposition. Several prior works (e.g., Wainwright, 2019b ; Li et al., 2021b
) tackled the second term on the right-hand side of the relation (27) via the
following crude bounds:

$\displaystyle\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}$
$\displaystyle\leq\big{\|}\bm{P}^{\pi_{i-1}}\big{\|}_{1}\|\bm{\Delta}_{i-1}\|_{\infty}\bm{1}=\|\bm{\Delta}_{i-1}\|_{\infty}\bm{1},$
$\displaystyle\bm{P}^{\pi^{\star}}\bm{\Delta}_{i-1}$
$\displaystyle\geq-\big{\|}\bm{P}^{\pi^{\star}}\big{\|}_{1}\|\bm{\Delta}_{i-1}\|_{\infty}\bm{1}=-\|\bm{\Delta}_{i-1}\|_{\infty}\bm{1},$

which, however, are too loose when characterizing the dependency on
$\frac{1}{1-\gamma}$. By contrast, expanding terms recursively without the
above type of crude bounding and carefully analyzing the aggregate terms
(e.g., $\sum_{i=1}^{t}\eta_{i}^{(t)}\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}$) play
a major role in sharpening the dependence of sample complexity on the
effective horizon.

####  4.2.2 Key intertwined relations underlying
$\\{\|\bm{\Delta}_{t}\|_{\infty}\\}$

By exploiting the crucial relations (30) derived above, we proceed to upper
and lower bound $\bm{\Delta}_{t}$ separately. To be more specific, defining

$\displaystyle\beta\coloneqq\frac{c_{4}(1-\gamma)}{\log T}$ (32)

for some constant $c_{4}>0$, one can further decompose the upper bound in (30)
into several terms:

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\leq\underbrace{\eta_{0}^{(t)}\bm{\Delta}_{0}+\sum_{i=1}^{(1-\beta)t}\eta_{i}^{(t)}\gamma\big{(}\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}+(\bm{P}_{i}-\bm{P})\bm{V}_{i-1}\big{)}}_{=:\,\bm{\zeta}_{t}}$
(33)
$\displaystyle\qquad\qquad+\underbrace{\sum_{i=(1-\beta)t+1}^{t}\eta_{i}^{(t)}\gamma(\bm{P}_{i}-\bm{P})\bm{V}_{i-1}}_{=:\,\bm{\xi}_{t}}+\sum_{i=(1-\beta)t+1}^{t}\eta_{i}^{(t)}\gamma\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}.$
(34)

Let us briefly remark on the effect of the first two terms:

  * •

Each component in the first term $\bm{\zeta}_{t}$ is fairly small, given that
$\eta_{i}^{(t)}$ is sufficiently small for any $i\leq(1-\beta)t$ (meaning that
each component has undergone contraction — the ones taking the form of
$1-\eta_{j}$ — for sufficiently many times). As a result, the influence of
$\bm{\zeta}_{t}$ becomes somewhat negligible.

  * •

The second term $\bm{\xi}_{t}$, which can be controlled via Freedman’s
inequality (Freedman,, 1975) due to its martingale structure, contributes to
the main variance term in the above recursion. Note, however, that the
resulting variance term also depends on $\\{\bm{\Delta}_{i}\\}$.

In summary, the right-hand side of the above inequality can be further
decomposed into some weighted superposition of $\\{\bm{\Delta}_{i}\\}$ in
addition to some negligible effect. This is formalized in the following two
lemmas, which make apparent the key intertwined relations underlying
$\\{\bm{\Delta}_{i}\\}$.

######  Lemma 1.

Suppose that $c_{1}c_{2}\leq c_{4}/8$. With probability at least $1-\delta$,

$\displaystyle\bm{\Delta}_{t}$ $\displaystyle\leq
30\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\Big{(}1+\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}}\ \bm{1}$

holds simultaneously for all $t\geq\frac{T}{c_{2}\log T}$.

######  Lemma 2.

Suppose that $c_{1}c_{2}\leq c_{4}/8$. With probability at least $1-\delta$,

$\bm{\Delta}_{t}\geq-30\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\Big{(}1+\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}}\ \bm{1}$

holds simultaneously for all $t\geq\frac{T}{c_{2}\log T}$.

###### Proof.

The proofs of Lemma 1 and Lemma 2 are deferred to Appendices B.2 and B.3,
respectively. As a remark, our analysis collects all the error terms accrued
through the iterations — instead of bounding them individually — by conducting
a high-order nonlinear expansion of the estimation error through recursion,
followed by careful control of the main variance term leveraging the structure
of the discounted MDP. ∎

Putting the preceding bounds in Lemmas 1 and 2 together, we arrive at

$\displaystyle\|\bm{\Delta}_{t}\|_{\infty}$ $\displaystyle\leq
30\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\bigg{(}1+\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bigg{)}}$ (35)

for all $t\geq\frac{T}{c_{2}\log T}$ with probability exceeding $1-2\delta$,
which forms the crux of our analysis. Employing elementary analysis tailored
to the above recursive relation, one can demonstrate that

$\displaystyle\|\bm{\Delta}_{T}\|_{\infty}\leq
O\bigg{(}\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{4}T}}+\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{4}T}\bigg{)}$
(36)

with probability at least $1-2\delta$, which in turn allows us to establish
the advertised result under the assumed sample size condition. The details are
deferred to Appendix B.4.

###  4.3 Proof outline for Theorem 3

##### Construction of a hard instance and its property

Let us construct an MDP $\mathcal{M}_{\mathsf{hard}}$ with state space
$\mathcal{S}=\\{0,1,2,3\\}$ (see a pictorial illustration in Figure 1). We
shall denote by $\mathcal{A}_{s}$ the action space associated with state $s$.
The probability transition kernel and reward function of
$\mathcal{M}_{\mathsf{hard}}$ are specified as follows

$\displaystyle\mathcal{A}_{0}=\\{1\\},$ $\displaystyle P(0\,|\,0,1)$
$\displaystyle=1,$ $\displaystyle r(0,1)=0,$ (37a)
$\displaystyle\mathcal{A}_{1}=\\{1,2\\},$ $\displaystyle P(1\,|\,1,1)$
$\displaystyle=p,$ $\displaystyle P(0\,|\,1,1)=1-p,$ $\displaystyle r(1,1)=1,$
(37b) $\displaystyle P(1\,|\,1,2)$ $\displaystyle=p,$ $\displaystyle
P(0\,|\,1,2)=1-p,$ $\displaystyle r(1,2)=1,$ (37c)
$\displaystyle\mathcal{A}_{2}=\\{1\\},$ $\displaystyle P(2\,|\,2,1)$
$\displaystyle=p,$ $\displaystyle P(0\,|\,2,1)=1-p,$ $\displaystyle r(2,1)=1,$
(37d) $\displaystyle\mathcal{A}_{3}=\\{1\\},$ $\displaystyle P(3\,|\,3,1)$
$\displaystyle=1,$ $\displaystyle r(3,1)=1,$ (37e)

where the parameter $p$ is taken to be

$\displaystyle p=\frac{4\gamma-1}{3\gamma}.$ (38)

Figure 1: The constructed hard MDP instance used in the analysis of Theorem 3,
where $p=\frac{4\gamma-1}{3\gamma}$ and the specifications are described in
(37).

Before moving forward to analyze the behavior of Q-learning, we first
characterize the optimal value function and Q-function of this MDP; the proof
is postponed to Section D.4.

######  Lemma 3.

Consider the MDP $\mathcal{M}_{\mathsf{hard}}$ constructed in (37). One has

$\displaystyle V^{\star}(0)=Q^{\star}(0,1)=0;$ (39a) $\displaystyle
V^{\star}(1)=Q^{\star}(1,1)=Q^{\star}(1,2)=V^{\star}(2)=Q^{\star}(2,1)=\frac{1}{1-\gamma
p}=\frac{3}{4(1-\gamma)};$ (39b) $\displaystyle
V^{\star}(3)=Q^{\star}(3,1)=\frac{1}{1-\gamma}.$ (39c)

Recognizing the elementary decomposition

$\mathbb{E}\left[\big{(}V^{\star}(s)-V_{T}(s)\big{)}^{2}\right]=\big{(}\mathbb{E}\left[V^{\star}(s)-V_{T}(s)\right]\big{)}^{2}+\mathsf{Var}\big{(}V_{T}(s)\big{)}$
(40)

for any state $s$, our proof consists of lower bounding either the squared
bias term $\big{(}\mathbb{E}[V^{\star}(s)-V_{T}(s)]\big{)}^{2}$ or the
variance term $\mathsf{Var}\big{(}V_{T}(s)\big{)}$. In short, we shall
primarily analyze the dynamics w.r.t. state 2 to handle the case when the
learning rates are either too small or too large, and analyze the dynamics
w.r.t. state 1 to cope with the case with medium learning rates (with state 3
serving as a helper state to simplify the analysis). The latter case —
corresponding to the learning rates adopted in establishing the upper bounds —
is the most challenging: critically, from state 1 the agent can take one of
two identical actions, whose value tends to be estimated with a high positive
bias due to maximizing over the empirical state-action values, highlighting
the well-recognized “over-estimation” issue of Q-learning in practice
(Hasselt,, 2010). The complete proof is deferred to Appendix D.

##  5 Extension: sample complexity of asynchronous Q-learning

Moving beyond the synchronous setting, another scenario of practical
importance is the case where the acquired samples take the form of a single
Markovian trajectory (Tsitsiklis,, 1994). In this section, we extend our
analysis framework for synchronous Q-learning to accommodate Markovian
non-i.i.d. samples.

###  5.1 Markovian samples and asynchronous Q-learning

##### Markovian sample trajectory.

Suppose that we obtain a Markovian sample trajectory
$\\{(s_{t},a_{t},r_{t})\\}_{t=0}^{\infty}$, which is generated by the MDP of
interest when a stationary behavior policy $\pi_{\mathsf{b}}$ is employed; in
other words,

$a_{t}\sim\pi_{\mathsf{b}}(\cdot\,|\,s_{t}),\quad r_{t}=r(s_{t},a_{t}),\quad
s_{t+1}\sim P(\cdot\,|\,s_{t},a_{t}),\qquad t\geq 0.$ (41)

When $\pi_{\mathsf{b}}$ is stationary, the trajectory
$\\{(s_{t},a_{t})\\}_{t=0}^{\infty}$ can be viewed as a sample path of a time-
homogeneous Markov chain; in what follows, we shall denote by
$\mu_{\pi_{\mathsf{b}}}$ the stationary distribution of this Markov chain.
Note that the behavior policy $\pi_{\mathsf{b}}$ can often be quite different
from the target optimal policy $\pi^{\star}$.

##### Asynchronous Q-learning.

In the presence of a single Markovian sample trajectory, the Q-learning
algorithm implements the following iterative update rule

$\displaystyle Q_{t}(s_{t-1},a_{t-1})$
$\displaystyle=(1-\eta_{t})Q_{t-1}(s_{t-1},a_{t-1})+\eta_{t}\Big{\\{}r(s_{t-1},a_{t-1})+\gamma\max_{a^{\prime}\in\mathcal{A}}Q_{t-1}(s_{t},a^{\prime})\Big{\\}},$
(42a) $\displaystyle Q_{t}(s,a)$ $\displaystyle=Q_{t-1}(s,a)\qquad\text{for
all }(s,a)\neq(s_{t-1},a_{t-1})$ (42b)

for all $t\geq 1$, where $0<\eta_{t}\leq 1$ stands for the learning rate at
time $t$. It is often referred to as asynchronous Q-learning, as only a single
state-action pair is updated in each iteration (in contrast, synchronous
Q-learning updates all state-action pairs simultaneously in each iteration).
This also leads to the following estimate for the value function at time $t$:

$\displaystyle
V_{t}(s)\coloneqq\max_{a\in\mathcal{A}}Q_{t}(s,a)\qquad\text{for all
}s\in\mathcal{S}.$ (43)

As can be expected, the presence of Markovian non-i.i.d. data considerably
complicates the analysis for asynchronous Q-learning.

##### Assumptions.

In order to ensure sufficient coverage of the sample trajectory over the
state/action space, we make the following assumption throughout this section,
which is also commonly imposed in prior literature.

######  Assumption 1.

The Markov chain induced by the behavior policy $\pi_{\mathsf{b}}$ is
uniformly ergodic.222See Paulin, (2015, Section 1.2) for the definition of
uniform ergodicity.

In addition, there are two crucial quantities concerning the sample trajectory
that dictate the performance of asynchronous Q-learning. The first one is the
minimum state-action occupancy probability of the sample trajectory, defined
formally as

$\mu_{\mathsf{min}}\coloneqq\min_{(s,a)\in\mathcal{S}\times\mathcal{A}}\mu_{\pi_{\mathsf{b}}}(s,a).$
(44)

This metric captures the information bottleneck incurred by the least visited
state-action pair. The second key quantity is the mixing time associated with
the sample trajectory, denoted by

$t_{\mathsf{mix}}\coloneqq\min\Big{\\{}t\,\Big{|}\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}d_{\mathsf{TV}}\big{(}P^{t}(\cdot\,|\,s,a),\mu_{\pi_{\mathsf{b}}}\big{)}\leq\frac{1}{4}\Big{\\}}.$
(45)

Here,
$d_{\mathsf{TV}}(\mu,\nu)\coloneqq\frac{1}{2}\sum_{x\in\mathcal{X}}|\mu(x)-\nu(x)|$
indicates the total variation distance between two measures $\mu$ and $\nu$
over $\mathcal{X}$ (Tsybakov and Zaiats,, 2009), whereas
$P^{t}(\cdot\,|\,s,a)$ stands for the distribution of $(s_{t},a_{t})$ when the
sample trajectory is initialized at $(s_{0},a_{0})=(s,a)$. In words, the
mixing time reflects the time required for the Markov chain to become nearly
independent of the initial states. See Li et al., 2021b (, Section 2) for a
more detailed account of these quantities and assumptions.

###  5.2 Sample complexity of asynchronous Q-learning

While a number of previous works have been dedicated to understanding the
performance of asynchronous Q-learning, its sample complexity bound remains
loose when it comes to the dependency on the effective horizon
$\frac{1}{1-\gamma}$. Encouragingly, the analysis framework laid out in this
paper allows us to tighten the dependency on $\frac{1}{1-\gamma}$, as stated
below.

######  Theorem 4.

Consider any $\delta\in(0,1)$, $\varepsilon\in(0,1]$, and $\gamma\in[1/2,1)$.
Suppose that for any $0\leq t\leq T$, the learning rates satisfy

$\eta_{t}\equiv\eta=\frac{c_{1}\log^{3}T}{(1-\gamma)T\mu_{\mathsf{min}}}$
(46a) for some universal constants $0<c_{1}\leq 1$. Assume that the total
number of iterations $T$ obeys
$T\geq\frac{c_{2}\log^{2}\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}}{\mu_{\mathsf{min}}}\max\bigg{\\{}\frac{\log^{3}T}{(1-\gamma)^{4}\varepsilon^{2}},\frac{t_{\mathsf{mix}}}{1-\gamma}\bigg{\\}}$
(46b) for some sufficiently large universal constant $c_{2}>0$.

If the initialization obeys $0\leq{Q}_{0}(s,a)\leq\frac{1}{1-\gamma}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$, then asynchronous Q-learning (cf.
(42)) satisfies

$\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}\big{|}{Q}_{T}(s,a)-{Q}^{\star}(s,a)\big{|}\leq\varepsilon$

with probability at least $1-\delta$.

######  Remark 3.

Similar to Remark 1 and Remark 2, one can immediately translate the above
high-probability result into the following mean estimation error bound:

$\mathbb{E}\Big{[}\max_{s,a}\big{|}{Q}_{T}(s,a)-{Q}^{\star}(s,a)\big{|}\Big{]}\leq\varepsilon(1-\delta)+\delta\frac{1}{1-\gamma}\leq
2\varepsilon,$ (47)

which holds as long as
$T\geq\frac{c_{2}\log^{2}\frac{|\mathcal{S}||\mathcal{A}|T}{\varepsilon(1-\gamma)}}{\mu_{\mathsf{min}}}\max\Big{\\{}\frac{\log^{3}T}{(1-\gamma)^{4}\varepsilon^{2}},\frac{t_{\mathsf{mix}}}{1-\gamma}\Big{\\}}$
for some large enough constant $c_{2}>0$.

This theorem demonstrates that with high probability, the total sample size
needed for asynchronous Q-learning to yield entrywise $\varepsilon$ accuracy
is

$\displaystyle\widetilde{O}\bigg{(}\frac{1}{\mu_{\mathsf{min}}(1-\gamma)^{4}\varepsilon^{2}}+\frac{t_{\mathsf{mix}}}{\mu_{\mathsf{min}}(1-\gamma)}\bigg{)},$
(48)

provided that the learning rates are taken to be some proper constant (see
(46a)). The first term in (48) resembles our sample complexity
characterization of synchronous Q-learning (cf. (14)), except that we replace
the number $|\mathcal{S}||\mathcal{A}|$ of state-action pairs in (14) with
$1/\mu_{\mathsf{min}}$ in order to account for non-uniformity across state-
action pairs. The second term in (48) is nearly independent of the target
accuracy (except for some logarithmic scaling), and can be viewed as the burn-
in time taken for asynchronous Q-learning to mimic synchronous Q-learning
despite Markovian data.

We now pause to compare Theorem 4 with prior non-asymptotic theory for
asynchronous Q-learning. As far as we know, all existing sample complexity
bounds (Beck and Srikant,, 2012; Qu and Wierman,, 2020; Li et al., 2021b, ;
Even-Dar and Mansour,, 2003; Chen et al.,, 2021) scale at least as
$\frac{1}{(1-\gamma)^{5}}$ in terms of the dependency on the effective
horizon, with Theorem 4 being the first result to sharpen this dependency to
$\frac{1}{(1-\gamma)^{4}}$. In particular, our sample complexity bound
strengthens the state-of-the-art result Li et al., 2021b  by a factor up to
$\frac{1}{1-\gamma}$, while improving upon Qu and Wierman, (2020) by a factor
of at least
$\frac{|\mathcal{S}||\mathcal{A}|}{1-\gamma}\min\big{\\{}t_{\mathsf{mix}},\frac{1}{(1-\gamma)^{3}\varepsilon^{2}}\big{\\}}$.333The
sample complexity of Li et al., 2021b  scales as
$\widetilde{O}\big{(}\frac{1}{\mu_{\mathsf{min}}(1-\gamma)^{5}\varepsilon^{2}}+\frac{t_{\mathsf{mix}}}{\mu_{\mathsf{min}}(1-\gamma)}\big{)}$,
while the sample complexity of Qu and Wierman, (2020) scales as
$\widetilde{O}\big{(}\frac{t_{\mathsf{mix}}}{\mu_{\mathsf{min}}^{2}(1-\gamma)^{5}\varepsilon^{2}}\big{)}$.
It is worth noting that $1/\mu_{\mathsf{min}}\geq|\mathcal{S}||\mathcal{A}|$
and is therefore a large factor.

##  6 Concluding remarks

In this paper, we have settled the sample complexity of synchronous Q-learning
in $\gamma$-discounted infinite-horizon MDPs, which is shown to be on the
order of
$\widetilde{O}\big{(}\frac{|\mathcal{S}|}{(1-\gamma)^{3}\varepsilon^{2}}\big{)}$
when $|\mathcal{A}|=1$ and
$\widetilde{O}\big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\varepsilon^{2}}\big{)}$
when $|\mathcal{A}|\geq 2$. A matching lower bound has been developed when
$|\mathcal{A}|\geq 2$ through studying the dynamics of Q-learning on a hard
MDP instance, which unveils the negative impact of an inevitable over-
estimation issue. Our theory has been further extended to accommodate
asynchronous Q-learning, resulting in tight dependency of the sample
complexity on the effective horizon. The analysis framework developed
herein—which exploits novel error decompositions and variance control that
differ substantially from prior approaches—might suggest a plausible path
towards sharpening the sample complexity of, as well as understanding the
algorithmic bottlenecks for, other model-free algorithms (e.g., double
Q-learning (Hasselt,, 2010)).

## Acknowledgements

G. Li and Y. Chen are supported in part by the AFOSR YIP award
FA9550-19-1-0030, the ONR grant N00014-19-1-2120, the ARO YIP award
W911NF-20-1-0097, the NSF grants CCF-2106739, CCF-1907661, DMS-2014279,
IIS-1900140 and IIS-2100158. Y. Wei is supported in part by the NSF grants
CCF-2007911 and DMS-2015447. Y. Gu is supported in part by the grant
NSFC-61971266. Y. Chi is supported in part by the grants ONR N00014-18-1-2142
and N00014-19-1-2404, the NSF grants CCF-1806154 and CCF-2007911. The authors
are grateful to Laixi Shi for helpful discussions about the lower bound, and
thank Shaocong Ma for pointing out some errors in an early version of this
work. Part of this work was done while G. Li, Y. Chen and Y. Wei were visiting
the Simons Institute for the Theory of Computing.

##  Appendix A Freedman’s inequality

The analysis of this work relies heavily on Freedman’s inequality (Freedman,,
1975), which is an extension of the Bernstein inequality and allows one to
establish concentration results for martingales. For ease of presentation, we
include a user-friendly version of Freedman’s inequality as follows.

######  Theorem 5.

Suppose that $Y_{n}=\sum_{k=1}^{n}X_{k}\in\mathbb{R}$, where $\\{X_{k}\\}$ is
a real-valued scalar sequence obeying

$\left|X_{k}\right|\leq
R\qquad\text{and}\qquad\mathbb{E}\left[X_{k}\mid\left\\{X_{j}\right\\}_{j:j<k}\right]=0\quad\quad\quad\text{for
all }k\geq 1.$

Define

$W_{n}\coloneqq\sum_{k=1}^{n}\mathbb{E}_{k-1}\left[X_{k}^{2}\right],$

where we write $\mathbb{E}_{k-1}$ for the expectation conditional on
$\left\\{X_{j}\right\\}_{j:j<k}$. Then for any given $\sigma^{2}\geq 0$, one
has

$\mathbb{P}\left\\{\left|Y_{n}\right|\geq\tau\text{ and
}W_{n}\leq\sigma^{2}\right\\}\leq
2\exp\left(-\frac{\tau^{2}/2}{\sigma^{2}+R\tau/3}\right).$ (49)

In addition, suppose that $W_{n}\leq\sigma^{2}$ holds deterministically. For
any positive integer $K\geq 1$, with probability at least $1-\delta$ one has

$\left|Y_{n}\right|\leq\sqrt{8\max\Big{\\{}W_{n},\frac{\sigma^{2}}{2^{K}}\Big{\\}}\log\frac{2K}{\delta}}+\frac{4}{3}R\log\frac{2K}{\delta}.$
(50)

###### Proof.

See Freedman, (1975); Tropp, (2011) for the proof of (49). As an immediate
consequence of (49), one has

$\mathbb{P}\left\\{\left|Y_{n}\right|\geq\sqrt{4\sigma^{2}\log\frac{2}{\delta}}+\frac{4}{3}R\log\frac{2}{\delta}\text{
and }W_{n}\leq\sigma^{2}\right\\}\leq\delta.$ (51)

Next, we turn attention to (50). Consider any positive integer $K$. As can be
easily seen, the event

$\mathcal{H}_{K}\coloneqq\Bigg{\\{}\left|Y_{n}\right|\geq\sqrt{8\max\Big{\\{}W_{n},\frac{\sigma^{2}}{2^{K}}\Big{\\}}\log\frac{2K}{\delta}}+\frac{4}{3}R\log\frac{2K}{\delta}\Bigg{\\}}$

is contained within the union of the following $K$ events

$\mathcal{H}_{K}\subseteq\bigcup_{0\leq k<K}\mathcal{B}_{k},$

where we define

$\displaystyle\mathcal{B}_{k}$
$\displaystyle\coloneqq\left\\{\left|Y_{n}\right|\geq\sqrt{\frac{4\sigma^{2}}{2^{k-1}}\log\frac{2K}{\delta}}+\frac{4}{3}R\log\frac{2K}{\delta}\text{
and }\frac{\sigma^{2}}{2^{k}}\leq
W_{n}\leq\frac{\sigma^{2}}{2^{k-1}}\right\\},\qquad 1\leq k\leq K-1,$
$\displaystyle\mathcal{B}_{0}$
$\displaystyle\coloneqq\left\\{\left|Y_{n}\right|\geq\sqrt{\frac{4\sigma^{2}}{2^{K-1}}\log\frac{2K}{\delta}}+\frac{4}{3}R\log\frac{2K}{\delta}\text{
and }W_{n}\leq\frac{\sigma^{2}}{2^{K-1}}\right\\}.$

Invoking inequality (51) with $\sigma^{2}$ set to be
$\frac{\sigma^{2}}{2^{k-1}}$ and $\delta$ set to be $\frac{\delta}{K}$, we
arrive at $\mathbb{P}\left\\{\mathcal{B}_{k}\right\\}\leq\delta/K$. Taken this
fact together with the union bound gives

$\mathbb{P}\left\\{\mathcal{H}_{K}\right\\}\leq\sum_{k=0}^{K-1}\mathbb{P}\left\\{\mathcal{B}_{k}\right\\}\leq\delta.$

This concludes the proof. ∎

##  Appendix B Upper bounds for Q-learning (Theorem 2)

In this section, we fill in the details for the proof idea outlined in Section
4.2 for synchronous Q-learning. In fact, our proof strategy leads to a more
general version that accounts for the full $\varepsilon$-range
$\varepsilon\in\big{(}0,\frac{1}{1-\gamma}\big{]}$, as stated below.

######  Theorem 6.

Consider any $\gamma\in(0,1)$ and any
$\varepsilon\in\big{(}0,\frac{1}{1-\gamma}\big{]}$. Theorem 2 continues to
hold if

$T\geq\frac{c_{3}\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}\min\\{\varepsilon^{2},\varepsilon\\}}$
(52)

for some large enough universal constant $c_{3}>0$.

######  Remark 4.

Clearly, Theorem 6 subsumes Theorem 2 as a special case.

As one can anticipate, the proof of Theorem 6 for Q-learning includes many key
ingredients for establishing Theorem 1 for TD learning. We will elaborate on
how to modify the proof argument to establish Theorem 1 in Section C.

###  B.1 Preliminaries

To begin with, we gather a few elementary facts that shall be used multiple
times in the proof.

##### Ranges of $\bm{Q}_{t}$ and $\bm{V}_{t}$.

When properly initialized, the Q-function estimates and the value function
estimates always fall within a suitable range, as asserted by the following
lemma.

######  Lemma 4.

Suppose that $0\leq\eta_{t}\leq 1$ for all $t\geq 0$. Assume that
$\bm{0}\leq\bm{Q}_{0}\leq\frac{1}{1-\gamma}\bm{1}$. Then for any $t\geq 0$,

$\bm{0}\leq\bm{Q}_{t}\leq\frac{1}{1-\gamma}\bm{1}\qquad\text{and}\qquad\bm{0}\leq\bm{V}_{t}\leq\frac{1}{1-\gamma}\bm{1}.$
(53)

###### Proof.

We shall prove this by induction. First, our initialization trivially obeys
(53) for $t=0$. Next, suppose that (53) is true for the $(t-1)$-th iteration,
namely,

$\bm{0}\leq\bm{Q}_{t-1}\leq\frac{1}{1-\gamma}\bm{1}\qquad\text{and}\qquad\bm{0}\leq\bm{V}_{t-1}\leq\frac{1}{1-\gamma}\bm{1},$
(54)

and we intend to justify the claim for the $t$-th iteration. Recognizing that
$\bm{0}\leq\bm{r}\leq\bm{1}$, $\bm{P}_{t}\geq\bm{0}$ and
$\|\bm{P}_{t}\|_{1}=1$, one can straightforwardly see from the update rule
(21) and the induction hypothesis (54) that

$\bm{Q}_{t}=(1-\eta_{t})\bm{Q}_{t-1}+\eta_{t}(\bm{r}+\gamma\bm{P}_{t}\bm{V}_{t-1})\geq\bm{0}$

and

$\displaystyle\bm{Q}_{t}$
$\displaystyle=(1-\eta_{t})\bm{Q}_{t-1}+\eta_{t}(\bm{r}+\gamma\bm{P}_{t}\bm{V}_{t-1})$
$\displaystyle\leq(1-\eta_{t})\,\|\bm{Q}_{t-1}\|_{\infty}\bm{1}+\eta_{t}\big{(}\|\bm{r}\|_{\infty}+\gamma\|\bm{P}_{t}\|_{1}\|\bm{V}_{t-1}\|_{\infty}\big{)}\bm{1}$
$\displaystyle\leq(1-\eta_{t})\frac{1}{1-\gamma}\bm{1}+\eta_{t}\Big{(}1+\frac{\gamma}{1-\gamma}\Big{)}\bm{1}=\frac{1}{1-\gamma}\bm{1}.$

In addition, from the definition $V_{t}(s):=\max_{a}Q_{t}(s,a)$ for all $t\geq
0$ and all $s\in\mathcal{S}$, it is easily seen that

$\bm{0}\leq\bm{V}_{t}\leq\frac{1}{1-\gamma}\bm{1},$

thus establishing (53) for the $t$-th iteration. Applying the induction
argument then concludes the proof. ∎

As a result of Lemma 4 and the fact
$\bm{0}\leq\bm{Q}^{\star}\leq\frac{1}{1-\gamma}\bm{1}$, we have

$\|\bm{Q}_{t}-\bm{Q}^{\star}\|_{\infty}\leq\frac{1}{1-\gamma}\qquad\text{for
all }t\geq 0,$ (55)

which also confirms that $0\leq\varepsilon\leq\frac{1}{1-\gamma}$ is the full
$\varepsilon$-range we need to consider. Further, we make note of a direct
consequence of the claimed iteration number (52) when
$\varepsilon\leq\frac{1}{1-\gamma}$:

$T=\frac{c_{3}\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{4}\min\\{\varepsilon,\varepsilon^{2}\\}}\geq\frac{c_{3}\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{3}},$
(56)

which will be useful for subsequent analysis.

##### Several facts regarding the learning rates.

Next, we gather a couple of useful bounds regarding the learning rates
$\\{\eta_{t}\\}$. To begin with, we find it helpful to introduce the following
related quantities introduced previously in (31):

$\eta_{i}^{(t)}\coloneqq\begin{cases}\prod_{j=1}^{t}(1-\eta_{j}),&\text{if
}i=0,\\\ \eta_{i}\prod_{j=i+1}^{t}(1-\eta_{j}),&\text{if }0<i<t,\\\
\eta_{t},&\text{if }i=t.\end{cases}$ (57)

We now take a moment to bound $\eta_{i}^{(t)}$. From our assumption (12a) and
the condition (56), we know that the learning rate obeys

$\frac{1}{2c_{1}(1-\gamma)T/\log^{3}T}\leq\frac{1}{1+c_{1}(1-\gamma)T/\log^{3}T}\leq\eta_{t}\leq\frac{1}{1+c_{2}(1-\gamma)t/\log^{3}T}\leq\frac{1}{c_{2}(1-\gamma)t/\log^{3}T}$
(58)

for some constants $c_{1},c_{2}>0$. Recalling that

$\beta\coloneqq\frac{c_{4}(1-\gamma)}{\log T}$ (59)

for some universal constant $c_{4}>0$ and considering any $t$ obeying

$t\geq\frac{T}{c_{2}\log T},$ (60)

we shall bound $\eta_{i}^{(t)}$ by looking at two cases separately.

  * •

For any $0\leq i\leq(1-\beta)t$, we can use (58) to show that

$\displaystyle\eta_{i}^{(t)}$
$\displaystyle\leq\Big{(}1-\frac{1}{2c_{1}(1-\gamma)T/\log^{3}T}\Big{)}^{\beta
t}\leq\Big{(}1-\frac{1}{2c_{1}(1-\gamma)T/\log^{3}T}\Big{)}^{\frac{c_{4}(1-\gamma)T}{c_{2}\log^{2}T}}$
$\displaystyle=\Bigg{(}\Big{(}1-\frac{1}{2c_{1}(1-\gamma)T/\log^{3}T}\Big{)}^{\frac{2c_{1}(1-\gamma)T}{\log^{3}T}}\Bigg{)}^{\frac{c_{4}\log
T}{2c_{1}c_{2}}}<\frac{1}{2T^{2}},$ (61a) where the last inequality holds as
long as $c_{1}c_{2}\leq c_{4}/8$.

  * •

When it comes to the case with $i>(1-\beta)t\geq t/2$, one can upper bound

$\eta_{i}^{(t)}\leq\eta_{i}\leq\frac{1}{c_{2}(1-\gamma)i/\log^{3}T}<\frac{2}{c_{2}(1-\gamma)t/\log^{3}T}\leq\frac{2\log^{4}T}{(1-\gamma)T},$
(61b)

where we have used the constraint (60).

Moreover, the sum of $\eta_{i}^{(t)}$ over $i$ obeys

$\displaystyle\sum_{i=0}^{t}\eta_{i}^{(t)}$
$\displaystyle=\prod_{j=1}^{t}(1-\eta_{j})+\eta_{1}\prod_{j=2}^{t}(1-\eta_{j})+\eta_{2}\prod_{j=3}^{t}(1-\eta_{j})+\cdots+\eta_{t-1}(1-\eta_{t})+\eta_{t}$
$\displaystyle=\prod_{j=2}^{t}(1-\eta_{j})+\eta_{2}\prod_{j=3}^{t}(1-\eta_{j})+\cdots+\eta_{t-1}(1-\eta_{t})+\eta_{t}=\cdots$
$\displaystyle=(1-\eta_{t})+\eta_{t}=1.$ (62)

Repeating the same argument further allows us to derive

$\displaystyle\sum_{i=\tau}^{t}\eta_{i}^{(t)}$
$\displaystyle=1-\prod_{j=\tau}^{t}(1-\eta_{j})$ (63)

for any $\tau\leq t$.

###  B.2 Proof of Lemma 1

We shall exploit the relation (34) to prove this lemma. One of the key
ingredients of our analysis lies in controlling the terms $\bm{\zeta}_{t}$ and
$\bm{\xi}_{t}$ introduced in (34), which in turn enables us to apply (34)
recursively to control $\bm{\Delta}_{t}$.

##### Step 1: bounding $\bm{\zeta}_{t}$.

We start by developing an upper bound on $\bm{\zeta}_{t}$ (cf. (34)) for any
$t$ obeying $\frac{T}{c_{2}\log T}\leq t\leq T$. Invoking the preceding upper
bounds (61) on $\eta_{i}^{(t)}$ implies that

$\displaystyle\|\bm{\zeta}_{t}\|_{\infty}$
$\displaystyle\leq\eta_{0}^{(t)}\|\bm{\Delta}_{0}\|_{\infty}+t\max_{i\leq(1-\beta)t}\eta_{i}^{(t)}\max_{1\leq
i\leq(1-\beta)t}\big{(}\|\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}\|_{\infty}+\|\bm{P}_{i}\bm{V}_{i-1}\|_{\infty}+\|\bm{P}\bm{V}_{i-1}\|_{\infty}\big{)}$
$\displaystyle\leq\eta_{0}^{(t)}\|\bm{\Delta}_{0}\|_{\infty}+t\max_{i\leq(1-\beta)t}\eta_{i}^{(t)}\max_{1\leq
i\leq(1-\beta)t}\Big{\\{}\|\bm{P}^{\pi_{i-1}}\|_{1}\|\bm{\Delta}_{i-1}\|_{\infty}+\big{(}\|\bm{P}_{i}\|_{1}+\|\bm{P}\|_{1}\big{)}\|\bm{V}_{i-1}\|_{\infty}\Big{\\}}$
$\displaystyle\overset{(\mathrm{i})}{=}\eta_{0}^{(t)}\|\bm{\Delta}_{0}\|_{\infty}+t\max_{i\leq(1-\beta)t}\eta_{i}^{(t)}\max_{1\leq
i\leq(1-\beta)t}\big{(}\|\bm{\Delta}_{i-1}\|_{\infty}+2\,\|\bm{V}_{i-1}\|_{\infty}\big{)}$
$\displaystyle\overset{(\mathrm{ii})}{\leq}\frac{1}{2T^{2}}\cdot\frac{1}{1-\gamma}+\frac{1}{2T^{2}}\cdot
t\cdot\frac{3}{1-\gamma}$ $\displaystyle\leq\frac{2}{(1-\gamma)T}.$

Here, (i) holds since
$\|\bm{P}^{\pi_{i-1}}\|_{1}=\|\bm{P}_{i}\|_{1}=\|\bm{P}\|_{1}=1$ (as they are
all probability transition matrices), whereas (ii) arises from the previous
bound (61a).

##### Step 2: bounding $\bm{\xi}_{t}$.

Moving on to the term $\bm{\xi}_{t}$, let us express it as

$\bm{\xi}_{t}=\sum_{i=(1-\beta)t+1}^{t}\bm{z}_{i}\qquad\text{with
}\bm{z}_{i}\coloneqq\eta_{i}^{(t)}\gamma(\bm{P}_{i}-\bm{P})\bm{V}_{i-1},$

where the $\bm{z}_{i}$’s satisfy

$\mathbb{E}\left[\bm{z}_{i}\,|\,\bm{V}_{i-1},\cdots,\bm{V}_{0}\right]=\bm{0}.$

This motivates us to invoke Freedman’s inequality (see Theorem 5) to control
$\bm{\xi}_{t}$ for any $t$ obeying $\frac{T}{c_{2}\log T}\leq t\leq T$.
Towards this, we need to calculate several quantities.

  * •

First, it is seen that

$\displaystyle B$ $\displaystyle:=\max_{(1-\beta)t<i\leq
t}\|\bm{z}_{i}\|_{\infty}\leq\max_{(1-\beta)t<i\leq
t}\|\eta_{i}^{(t)}(\bm{P}_{i}-\bm{P})\bm{V}_{i-1}\|_{\infty}$
$\displaystyle\leq\max_{(1-\beta)t<i\leq
t}\eta_{i}^{(t)}\big{(}\|\bm{P}_{i}\|_{1}+\|\bm{P}\|_{1}\big{)}\|\bm{V}_{i-1}\|_{\infty}\leq\frac{4\log^{4}T}{(1-\gamma)^{2}T},$

where the last inequality is due to (61b), Lemma 4, and the fact
$\|\bm{P}_{i}\|_{1}=\|\bm{P}\|_{1}=1$.

  * •

Next, we turn to certain variance terms. For any vector $\bm{a}=[a_{j}]$, let
us use $\mathsf{Var}\big{(}\bm{a}\,|\,\bm{V}_{i-1},\cdots,\bm{V}_{0}\big{)}$
to denote a vector whose $j$-th entry is given by
$\mathsf{Var}\big{(}a_{j}\,|\,\bm{V}_{i-1},\cdots,\bm{V}_{0}\big{)}$. With
this notation in place, and recalling the notation
$\mathsf{Var}_{\bm{P}}(\bm{z})$ in (17), we obtain

$\displaystyle\bm{W}_{t}$
$\displaystyle:=\sum_{i=(1-\beta)t+1}^{t}\mathsf{Var}\big{(}\bm{z}_{i}\,|\,\bm{V}_{i-1},\cdots,\bm{V}_{0}\big{)}=\gamma^{2}\sum_{i=(1-\beta)t+1}^{t}\big{(}\eta_{i}^{(t)}\big{)}^{2}\mathsf{Var}\Big{(}(\bm{P}_{i}-\bm{P})\bm{V}_{i-1}\,|\,\bm{V}_{i-1}\Big{)}$
$\displaystyle=\gamma^{2}\sum_{i=(1-\beta)t+1}^{t}\big{(}\eta_{i}^{(t)}\big{)}^{2}\mathsf{Var}_{\bm{P}}\big{(}\bm{V}_{i-1}\big{)}$
$\displaystyle\leq\Big{(}\max_{(1-\beta)t\leq i\leq
t}\eta_{i}^{(t)}\Big{)}\Big{(}\sum_{i=(1-\beta)t+1}^{t}\eta_{i}^{(t)}\Big{)}\max_{(1-\beta)t\leq
i<t}\mathsf{Var}_{\bm{P}}\big{(}\bm{V}_{i}\big{)}$
$\displaystyle\leq\frac{2\log^{4}T}{(1-\gamma)T}\max_{(1-\beta)t\leq
i<t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i}),$ (64)

where the last inequality relies on the previous bounds (61b) and (62).

  * •

In the meantime, Theorem 4 leads us to the following trivial upper bound:

$\big{|}\bm{W}_{t}\big{|}\leq\frac{2\log^{4}T}{(1-\gamma)T}\cdot\frac{1}{(1-\gamma)^{2}}\bm{1}=\frac{2\log^{4}T}{(1-\gamma)^{3}T}\bm{1}\eqqcolon\sigma^{2}\bm{1}.$

By setting $K=\left\lceil 2\log_{2}\frac{1}{1-\gamma}\right\rceil$, one has

$\frac{\sigma^{2}}{2^{K}}\leq\frac{2\log^{4}T}{(1-\gamma)T}.$ (65)

With the above bounds in place, applying the Freedman inequality in Theorem 5
and invoking the union bound over all the $|\mathcal{S}||\mathcal{A}|$ entries
of $\bm{\xi}_{t}$ demonstrate that

$\displaystyle|\bm{\xi}_{t}|$
$\displaystyle\leq\sqrt{8\Big{(}\bm{W}_{t}+\frac{\sigma^{2}}{2^{K}}\bm{1}\Big{)}\log\frac{8|\mathcal{S}||\mathcal{A}|T\log\frac{1}{1-\gamma}}{\delta}}+\Big{(}\frac{4}{3}B\log\frac{8|\mathcal{S}||\mathcal{A}|T\log\frac{1}{1-\gamma}}{\delta}\Big{)}\cdot\bm{1}$
$\displaystyle\leq\sqrt{16\Big{(}\bm{W}_{t}+\frac{2\log^{4}T}{(1-\gamma)T}\bm{1}\Big{)}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}}+\Big{(}3B\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\Big{)}\cdot\bm{1}$
$\displaystyle\leq\sqrt{\frac{32\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)T}\Big{(}\max_{(1-\beta)t\leq
i<t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})+\bm{1}\Big{)}}+\frac{12\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{2}T}\bm{1}$

with probability at least $1-\delta/T.$ Here, the second line holds due to
(65) and the fact
$\log\frac{8|\mathcal{S}||\mathcal{A}|T\log\frac{1}{1-\gamma}}{\delta}\leq
2\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}$ (cf. (56)), whereas the last
inequality makes use of the relation (64).

##### Step 3: using the bounds on $\bm{\zeta}_{t}$ and $\bm{\xi}_{t}$ to
control $\bm{\Delta}_{t}$.

Let us define

$\bm{\varphi}_{t}\coloneqq
64\frac{\log^{4}T\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}}{(1-\gamma)T}\bigg{(}\max_{\frac{t}{2}\leq
i\leq t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})+\bm{1}\bigg{)}$ (66)

In view of the upper bounds derived in Steps 1 and 2, and $\beta$ defined in
(59), we have — with probability exceeding $1-\delta$ — that

$|\bm{\zeta}_{k}|+|\bm{\xi}_{k}|\leq\sqrt{\bm{\varphi}_{t}}\qquad\text{for all
}\leavevmode\nobreak\ 2t/3\leq k\leq t,$ (67)

provided that
$T\geq\frac{c_{9}(\log^{4}T)\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{3}}$
for some sufficiently large constant $c_{9}>0$. Substituting (67) into (34),
we can upper bound $\bm{\Delta}_{t}$ as follows

$\displaystyle\bm{\Delta}_{k}$
$\displaystyle\leq\sqrt{\bm{\varphi}_{t}}+\sum_{i=(1-\beta)k+1}^{k}\eta_{i}^{(k)}\gamma\bm{P}^{\pi_{i-1}}\bm{\Delta}_{i-1}=\sqrt{\bm{\varphi}_{t}}+\sum_{i=(1-\beta)k}^{k-1}\eta_{i+1}^{(k)}\gamma\bm{P}^{\pi_{i}}\bm{\Delta}_{i}\qquad\text{for
all }\leavevmode\nobreak\ 2t/3\leq k\leq t.$ (68)

Further, we find it convenient to define $\big{\\{}\alpha_{i}^{(t)}\big{\\}}$
as follows

$\displaystyle\alpha_{i}^{(t)}:=\frac{\eta_{i+1}^{(t)}}{\sum_{j=(1-\beta)t}^{t-1}\eta_{j+1}^{(t)}}.$
(69)

Clearly, this sequence satisfies

$\alpha_{i}^{(t)}\geq\eta_{i+1}^{(t)}\qquad\text{and}\qquad\sum_{i=(1-\beta)t}^{t-1}\alpha_{i}^{(t)}=1$
(70)

for any $t$, where the first inequality results from (62). With these in
place, we can write (68) as

$\bm{\Delta}_{k}\leq\sqrt{\bm{\varphi}_{t}}+\sum_{i_{1}=(1-\beta)k}^{k-1}\eta_{i_{1}+1}^{(k)}\gamma\bm{P}^{\pi_{i_{1}}}\bm{\Delta}_{i_{1}}=\sum_{i_{1}=(1-\beta)k}^{k-1}\Big{(}\alpha_{i_{1}}^{(k)}\sqrt{\bm{\varphi}_{t}}+\eta_{i_{1}+1}^{(k)}\gamma\bm{P}^{\pi_{i_{1}}}\bm{\Delta}_{i_{1}}\Big{)}\qquad\text{for
all }2t/3\leq k\leq t.$ (71)

Given that $(1-\beta)t\geq 2t/3$ (see (59)), we can invoke this relation
recursively to yield

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\leq\sum_{i_{1}=(1-\beta)t}^{t-1}\Big{(}\alpha_{i_{1}}^{(t)}\sqrt{\bm{\varphi}_{t}}+\eta_{i_{1}+1}^{(t)}\gamma\bm{P}^{\pi_{i_{1}}}\bm{\Delta}_{i_{1}}\Big{)}$
$\displaystyle\leq\sum_{i_{1}=(1-\beta)t}^{t-1}\Bigg{[}\alpha_{i_{1}}^{(t)}\sqrt{\bm{\varphi}_{t}}+\eta_{i_{1}+1}^{(t)}\gamma\bm{P}^{\pi_{i_{1}}}\sum_{i_{2}=(1-\beta)i_{1}}^{i_{1}-1}\Big{(}\alpha_{i_{2}}^{(i_{1})}\sqrt{\bm{\varphi}_{t}}+\eta_{i_{2}+1}^{(i_{1})}\gamma\bm{P}^{\pi_{i_{2}}}\bm{\Delta}_{i_{2}}\Big{)}\Bigg{]}$
$\displaystyle\leq\sum_{i_{1}=(1-\beta)t}^{t-1}\alpha_{i_{1}}^{(t)}\sqrt{\bm{\varphi}_{t}}+\sum_{i_{1}=(1-\beta)t}^{t-1}\sum_{i_{2}=(1-\beta)i_{1}}^{i_{1}-1}\alpha_{i_{1}}^{(t)}\alpha_{i_{2}}^{(i_{1})}\big{(}\gamma\bm{P}^{\pi_{i_{1}}}\big{)}\sqrt{\bm{\varphi}_{t}}$
$\displaystyle\qquad\qquad+\sum_{i_{1}=(1-\beta)t}^{t-1}\sum_{i_{2}=(1-\beta)i_{1}}^{i_{1}-1}\eta_{i_{1}+1}^{(t)}\eta_{i_{2}+1}^{(i_{1})}\prod_{k=1}^{2}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\big{)}\bm{\Delta}_{i_{2}}$
$\displaystyle=\sum_{i_{1}=(1-\beta)t}^{t-1}\sum_{i_{2}=(1-\beta)i_{1}}^{i_{1}-1}\alpha_{i_{1}}^{(t)}\alpha_{i_{2}}^{(i_{1})}\left\\{\bm{I}+\gamma\bm{P}^{\pi_{i_{1}}}\right\\}\sqrt{\bm{\varphi}_{t}}+\sum_{i_{1}=(1-\beta)t}^{t-1}\sum_{i_{2}=(1-\beta)i_{1}}^{i_{1}-1}\eta_{i_{1}+1}^{(t)}\eta_{i_{2}+1}^{(i_{1})}\prod_{k=1}^{2}\big{(}\gamma\bm{P}^{\pi_{i_{k}}}\big{)}\bm{\Delta}_{i_{2}},$
(72)

where the second inequality relies on (71), the third line uses the inequality
$\eta_{i_{1}+1}^{(t)}\leq\alpha_{i_{1}}^{(t)}$ in (70), and the fourth line is
valid since $\sum_{i_{2}=(1-\beta)i_{1}}^{i_{1}-1}\alpha_{i_{2}}^{(i_{1})}=1$
(see (70)).

We intend to continue invoking (71) recursively — similar to how we derive
(72) — in order to control $\bm{\Delta}_{t}$. To do so, we are in need of some
preparation. First, let us define

$H\coloneqq\frac{\log
T}{1-\gamma}\qquad\text{and}\qquad\alpha_{\\{i_{k}\\}_{k=1}^{H}}:=\alpha_{i_{1}}^{(t)}\alpha_{i_{2}}^{(i_{1})}\ldots\alpha_{i_{H}}^{(i_{H-1})}\geq
0$ (73)

for any $t>i_{1}>i_{2}>\cdots>i_{H}$, which clearly satisfies (see (70))

$\alpha_{\\{i_{k}\\}_{k=1}^{H}}\geq\eta_{i_{1}+1}^{(t)}\eta_{i_{2}+1}^{(i_{1})}\ldots\eta_{i_{H}+1}^{(i_{H-1})}.$
(74)

In addition, defining the index set

$\mathcal{I}_{t}\coloneqq\Big{\\{}\left(i_{1},\cdots,i_{H}\right)\,|\,(1-\beta)t\leq
i_{1}\leq t-1,\ \forall 1\leq j<H:(1-\beta)i_{j}\leq i_{j+1}\leq
i_{j}-1\Big{\\}},$ (75)

we have

$\sum_{\left(i_{1},\cdots,i_{H}\right)\in\mathcal{I}_{t}}\alpha_{\\{i_{k}\\}_{k=1}^{H}}=1.$
(76)

Additionally, recalling that $\beta=c_{4}(1-\gamma)/\log T$, we see that this
choice of $H$ satisfies

$(1-\beta)^{H}=\left(1-\frac{c_{4}(1-\gamma)}{\log T}\right)^{\frac{\log
T}{1-\gamma}}\geq\frac{2}{3}$

for $c_{4}$ small enough, thus implying that

$i_{1}>i_{2}>\cdots>i_{H}\geq(1-\beta)^{H}t\geq 2t/3\qquad\text{for all
}(i_{1},\cdots,i_{H})\in\mathcal{I}_{t}.$

This is an important property that allows one to invoke the relation (71).
With these in place, applying the preceding relation (71) recursively — in a
way similar to (72) — further leads to

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\leq\sum_{\left(i_{1},\cdots,i_{H}\right)\in\mathcal{I}_{t}}\alpha_{\\{i_{k}\\}_{k=1}^{H}}\Bigg{\\{}\bigg{(}\bm{I}+\sum_{h=1}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\bigg{)}\sqrt{\bm{\varphi}_{t}}+\gamma^{H}\prod_{k=1}^{H}\bm{P}^{\pi_{i_{k}}}\big{|}\bm{\Delta}_{i_{H}}\big{|}\Bigg{\\}}$
$\displaystyle\leq\max_{\left(i_{1},\cdots,i_{H}\right)\in\mathcal{I}_{t}}\Bigg{\\{}\underbrace{\bigg{(}\bm{I}+\sum_{h=1}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\bigg{)}\sqrt{\bm{\varphi}_{t}}}_{=:\,\bm{\beta}_{1}}+\underbrace{\gamma^{H}\prod_{k=1}^{H}\bm{P}^{\pi_{i_{k}}}\big{|}\bm{\Delta}_{i_{H}}\big{|}}_{=:\,\bm{\beta}_{2}}\Bigg{\\}}$
(77)

for all $t\geq\frac{T}{c_{2}\log T}$, where we recall the definition of the
entrywise $\max$ operator in Section 4.1. Here, the last inequality relies on
the fact that
$\sum_{\left(i_{1},\cdots,i_{H}\right)\in\mathcal{I}_{t}}\alpha_{\\{i_{k}\\}_{k=1}^{H}}=1$
(see (76)). It remains to control $\bm{\beta}_{1}$ and $\bm{\beta}_{2}$, which
we shall accomplish separately in the next two steps.

##### Step 4: bounding $\bm{\beta}_{2}$.

The term $\bm{\beta}_{2}$ defined in (77) is relatively easier to control.
Observing that $\prod_{k=1}^{H}\bm{P}^{\pi_{i_{k}}}$ is still a probability
transition matrix, we can derive

$\displaystyle|\bm{\beta}_{2}|$ $\displaystyle=\gamma^{H}\prod_{1\leq k\leq
h}\bm{P}^{\pi_{i_{k}}}\big{|}\bm{\Delta}_{i_{H}}\big{|}\leq\gamma^{H}\bigg{\|}\prod_{1\leq
k\leq
h}\bm{P}^{\pi_{i_{k}}}\bigg{\|}_{1}\|\bm{\Delta}_{i_{H}}\|_{\infty}=\gamma^{H}\|\bm{\Delta}_{i_{H}}\|_{\infty}$
$\displaystyle\overset{(\mathrm{i})}{\leq}\frac{1}{1-\gamma}\gamma^{H}\overset{(\mathrm{ii})}{\leq}\frac{1}{(1-\gamma)T},$

where (i) results from the crude bound (55). To justify the inequality (ii),
we recall the definition (73) of $H$ to see that

$\gamma^{H}\overset{(\mathrm{ii})}{=}\big{(}1-(1-\gamma)\big{)}^{\frac{1}{1-\gamma}\log
T}\leq e^{-\log T}=\frac{1}{T},$

where the inequality comes from the elementary fact that
$\gamma^{\frac{1}{1-\gamma}}\leq e^{-1}$ for any $0<\gamma<1$.

##### Step 5: bounding $\bm{\beta}_{1}$.

When it comes to the term $\bm{\beta}_{1}$ defined in (77), we can upper bound
the entrywise square of $\bm{\beta}_{1}$ — denoted by $|\bm{\beta}_{1}|^{2}$ —
as follows

$\displaystyle|\bm{\beta}_{1}|^{2}$
$\displaystyle=\bigg{|}\Big{(}\sum_{h=0}^{H-1}\gamma^{h}\prod_{1\leq k\leq
h}\bm{P}^{\pi_{i_{k}}}\Big{)}\sqrt{\bm{\varphi}_{t}}\bigg{|}^{2}\overset{(\mathrm{i})}{\leq}\bigg{|}\sum_{h=0}^{H-1}\gamma^{h/2}\cdot\gamma^{h/2}\sqrt{\prod_{1\leq
k\leq h}\bm{P}^{\pi_{i_{k}}}\bm{\varphi}_{t}}\,\bigg{|}^{2}$
$\displaystyle\overset{(\mathrm{ii})}{\leq}\sum_{h=0}^{H-1}\gamma^{h}\cdot\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\bm{\varphi}_{t}$
$\displaystyle\overset{(\mathrm{iii})}{\leq}\frac{1}{1-\gamma}\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\frac{64\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)T}\bigg{(}\max_{\frac{t}{2}\leq
i<t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})+\bm{1}\bigg{)}$
$\displaystyle\overset{(\mathrm{iv})}{\leq}\frac{64\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{2}T}\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\max_{\frac{t}{2}\leq
i<t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})+\frac{64\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{3}T}\bm{1}.$

Here, (i) follows from Jensen’s inequality and the fact that
$\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}$ is a probability transition matrix; (ii)
holds due to the Cauchy-Schwarz inequality; (iii) utilizes the definition of
$\bm{\varphi}_{t}$ in (66); (iv) follows since $\prod_{1\leq k\leq
h}\bm{P}^{\pi_{i_{k}}}\bm{1}=\bm{1}$ and $\sum_{0\leq
h<H}\gamma^{h}\leq\frac{1}{1-\gamma}$. To further control the right-hand side
of the above inequality, we resort to the following lemma.

######  Lemma 5.

Suppose that $t\geq\frac{T}{c_{2}\log T}$. For any
$\left(i_{1},\cdots,i_{H}\right)\in\mathcal{I}_{t}$, the following holds:

$\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\max_{\frac{t}{2}\leq
i<t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})\leq\frac{4}{\gamma^{2}(1-\gamma)^{2}}\Big{(}1+2\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}\bm{1}.$ (78)

###### Proof.

This lemma, which is inspired by but significantly more complicated than Azar
et al., (2013, Lemma 8), plays a key role in shaving one $\frac{1}{1-\gamma}$
factor. See Section B.5 for the proof.∎

Therefore, the above result directly implies that

$\displaystyle|\bm{\beta}_{1}|^{2}$
$\displaystyle\leq\frac{320\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\Big{(}1+2\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}\bm{1}.$ (79)

##### Step 6: putting all this together.

Substituting the preceding bounds for $\bm{\beta}_{1}$ and $\bm{\beta}_{2}$
into (77), we can demonstrate that: with probability at least $1-\delta$,

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\leq\frac{1}{(1-\gamma)T}\bm{1}+\sqrt{\frac{320\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\Big{(}1+2\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}}\ \bm{1}$ $\displaystyle\leq
30\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\Big{(}1+\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}}\ \bm{1}$ (80)

holds simultaneously for all $t\geq\frac{T}{c_{2}\log T}$, where the second
line is valid since
$\frac{1}{(1-\gamma)T}\leq\sqrt{\frac{(\log^{4}T)\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{4}T}}$
under our sample size condition (56).

###  B.3 Proof of Lemma 2

Next, we move forward to develop an lower bound on $\bm{\Delta}_{t}$, which
can be accomplished in an analogous manner as for the above upper bound.
Applying a similar argument for (77) (except that we need to replace $\pi_{i}$
with $\pi^{\star}$), one can deduce that

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle\geq-\max_{\left(i_{1},\cdots,i_{H}\right)\in\mathcal{I}_{t}}\left\\{\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi^{\star}}\sqrt{\bm{\varphi}_{t}}+\gamma^{H}\prod_{k=1}^{H}\bm{P}^{\pi^{\star}}\big{|}\bm{\Delta}_{i_{H}}\big{|}\right\\}$
(81)

for any $t\geq\frac{c_{2}T}{\log\frac{1}{1-\gamma}}$. It is straightforward to
bound the second term on the right-hand side of (81) as

$\gamma^{H}\prod_{1\leq k\leq
H}\bm{P}^{\pi^{\star}}\big{|}\bm{\Delta}_{i_{H}}\big{|}\leq\gamma^{H}\bigg{\|}\prod_{1\leq
k\leq
H}\bm{P}^{\pi^{\star}}\bigg{\|}_{1}\|\bm{\Delta}_{i_{H}}\|_{\infty}\bm{1}\leq\frac{1}{(1-\gamma)T}\bm{1},$

where the second inequality makes use of (55) as well as the fact that
$\prod_{k}\bm{P}^{\pi^{\star}}$ is a probability transition matrix (so that
$\|\prod_{k}\bm{P}^{\pi^{\star}}\big{\|}_{1}=1$). As for the first term on the
right-hand side of (81), we can invoke a similar argument for (79) to obtain

$\displaystyle\bigg{|}\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi^{\star}}\sqrt{\bm{\varphi}_{t}}\bigg{|}^{2}$
$\displaystyle\leq
320\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\bigg{(}1+2\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bigg{)}\bm{1}.$

Taking these two bounds together, we see that with probability at least
$1-\delta$,

$\bm{\Delta}_{t}\geq-30\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\bigg{(}1+\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bigg{)}}\ \bm{1}$ (82)

holds simultaneously for all $t\geq\frac{T}{c_{2}\log T}$.

###  B.4 Solving the recurrence relation regarding $\bm{\Delta}_{t}$

Recall from (35) that with probability exceeding $1-2\delta$, the following
recurrence relation

$\displaystyle\|\bm{\Delta}_{t}\|_{\infty}$ $\displaystyle\leq
30\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\bigg{(}1+\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bigg{)}}\qquad\text{for all}\qquad
t\geq\frac{T}{c_{2}\log T}$ (83)

holds, which plays a crucial role in establishing the desired estimation error
bound. Specifically, for any $k\geq 0$, let us define

$u_{k}:=\max\left\\{\|\bm{\Delta}_{t}\|_{\infty}\ \Big{|}\
2^{k}\frac{T}{c_{2}\log T}\leq t\leq T\right\\}.$ (84)

To bound this sequence, we first obtain a crude bound as a result of (55):

$u_{0}\leq\frac{1}{1-\gamma}.$ (85)

Next, it is directly seen from (83) and the definition of $u_{k}$ that

$u_{k}\leq
c_{6}\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\left(1+u_{k-1}\right)},\qquad
k\geq 1$ (86)

for some constant $c_{6}=20/\gamma>0$. In order to analyze the size of
$u_{k}$, we divide into two cases.

  * •

If $u_{k}\leq 1$ for some $k\geq 1$, then (86) tells us that

$u_{k+1}\leq
c_{6}\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\left(1+u_{k}\right)}\leq
c_{6}\sqrt{\frac{2\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}}\leq
1,$

as long as
$T\geq\frac{2c_{6}^{2}\log^{4}T\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}}{\gamma^{2}(1-\gamma)^{4}}$.
In other words, once $u_{k-1}$ drops below $1$, then all subsequent quantities
will remain bounded above by 1, namely, $\max_{j:j\geq k}u_{j}\leq 1$. As a
result,

$u_{j}\leq
c_{6}\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\left(1+u_{j-1}\right)}\leq
c_{6}\sqrt{\frac{2\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}}\qquad\text{for
all }j>k.$

  * •

Instead, suppose that $u_{j}>1$ for all $0\leq j\leq k$. Then it is seen from
(86) that

$u_{j+1}\leq
c_{6}\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\left(1+u_{j}\right)}\leq
c_{6}\sqrt{\frac{2\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}u_{j}}\qquad\text{for
all }j\leq k.$

This is equivalent to saying that

$\log u_{j+1}\leq\log\alpha_{u}+\frac{1}{2}\log u_{j}\qquad\text{for all
}j\leq k,$

where
$\alpha_{u}=c_{6}\sqrt{\frac{2\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}}.$
Invoking a standard analysis strategy for this type of recursive relations
yields

$\log u_{j+1}-2\log\alpha_{u}\leq\frac{1}{2}\left(\log
u_{j}-2\log\alpha_{u}\right)\qquad\text{for all }j\leq k,$

and hence

$\log u_{j+1}\leq 2\log\alpha_{u}+\left(\frac{1}{2}\right)^{j+1}\left(\log
u_{0}-2\log\alpha_{u}\right)\qquad\text{for all }j\leq k.$

This is equivalent to saying that

$u_{j}\leq\alpha_{u}^{2}\left(\frac{u_{0}}{\alpha_{u}^{2}}\right)^{1/2^{j}}=\left(\alpha_{u}^{2}\right)^{1-1/2^{j}}\left(u_{0}\right)^{1/2^{j}}\qquad\text{for
all }j\leq k+1.$

Putting the above two cases together and using (85), we conclude that

$\displaystyle u_{k}$
$\displaystyle\leq\sqrt{\frac{2c_{6}^{2}\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}}+\Big{(}\frac{2c_{6}^{2}\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\Big{)}^{1-1/2^{k}}u_{0}^{1/2^{k}}$
$\displaystyle\leq\sqrt{\frac{2c_{6}^{2}\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}}+\Big{(}\frac{2c_{6}^{2}\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\Big{)}^{1-1/2^{k}}\left(\frac{1}{1-\gamma}\right)^{1/2^{k}},\qquad
k\geq 1.$

In particular, as long as $k\geq c_{7}\log\log\frac{1}{1-\gamma}$ for some
constant $c_{7}>0$, one has $\big{(}\frac{1}{1-\gamma}\big{)}^{1/2^{k}}\leq
O(1)$ and

$\Big{(}\frac{2c_{6}^{2}\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{(1-\gamma)^{4}T}\Big{)}^{1-1/2^{k}}\leq\max\left\\{\sqrt{\frac{2c_{6}^{2}\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}},\frac{2c_{6}^{2}\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\right\\}.$

As a result, the above bound simplifies to

$\displaystyle u_{k}$ $\displaystyle\leq
c_{8}\bigg{(}\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}}+\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\bigg{)},\qquad
k\geq c_{7}\log\log\frac{1}{1-\gamma}$

for some constant $c_{8}>0$.

Consequently, taking $t=T$ and choosing $k=c_{7}\log\log\frac{1}{1-\gamma}$
for some appropriate constant $c_{7}>0$ (so as to ensure
$2^{k}\frac{T}{c_{2}\log T}<T$), we immediately see from the definition (84)
of $u_{k}$ that

$\|\bm{\Delta}_{T}\|_{\infty}\leq
c_{8}\bigg{(}\sqrt{\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}}+\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\bigg{)}.$
(87)

with probability at least $1-2\delta$. To finish up, we note that the sample
size assumption (52) is equivalent to

$\frac{\big{(}\log^{4}T\big{)}\big{(}\log\frac{|\mathcal{S}||\mathcal{A}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{4}T}\leq\frac{\min\\{\varepsilon^{2},\varepsilon\\}}{c_{3}}.$

When $c_{3}>0$ is sufficiently large, substituting this relation into (87)
gives

$\displaystyle\|\bm{\Delta}_{T}\|_{\infty}$
$\displaystyle\leq\frac{1}{2}\sqrt{\min\\{\varepsilon^{2},\varepsilon\\}}+\frac{1}{2}\min\\{\varepsilon^{2},\varepsilon\\}=\begin{cases}\frac{1}{2}\varepsilon+\frac{1}{2}\varepsilon^{2}&\text{if
}\varepsilon\leq 1\\\
\frac{1}{2}\sqrt{\varepsilon}+\frac{1}{2}\varepsilon\quad&\text{if
}\varepsilon>1\end{cases}$ $\displaystyle\leq\varepsilon$

as claimed in Theorem 6.

###  B.5 Proof of Lemma 5

We first claim that

$\max_{\frac{t}{2}\leq
i<t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})-\mathsf{Var}_{\bm{P}}(\bm{V}^{\star})\leq\frac{4}{1-\gamma}\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bm{1}.$ (88)

If this claim were valid (which we shall justify towards the end of this
subsection), then it would lead to

$\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\max_{\frac{t}{2}\leq
i<t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})\leq\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\mathsf{Var}_{\bm{P}}(\bm{V}^{\star})+\frac{4}{(1-\gamma)^{2}}\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bm{1}.$ (89)

It then boils down to bounding the first term on the right-hand side of (89).
Let us first upper bound the variance term involving $\bm{V}^{\star}$. For any
$0\leq h<H$, one can express (see (17))

$\displaystyle\mathsf{Var}_{\bm{P}}(\bm{V}^{\star})$
$\displaystyle=\bm{P}(\bm{V}^{\star}\circ\bm{V}^{\star})-(\bm{P}\bm{V}^{\star})\circ(\bm{P}\bm{V}^{\star})$
$\displaystyle\overset{(\mathrm{i})}{=}\bm{P}^{\pi_{i_{h+1}}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})+\bm{P}(\bm{V}^{\star}\circ\bm{V}^{\star})-\bm{P}^{\pi_{i_{h+1}}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})-\frac{1}{\gamma^{2}}(\bm{Q}^{\star}-\bm{r})\circ(\bm{Q}^{\star}-\bm{r})$
$\displaystyle=\bm{P}^{\pi_{i_{h+1}}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})+\bm{P}^{\pi^{\star}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})-\bm{P}^{\pi_{i_{h+1}}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})-\frac{1}{\gamma^{2}}(\bm{Q}^{\star}-\bm{r})\circ(\bm{Q}^{\star}-\bm{r})$
$\displaystyle\leq\bm{P}^{\pi_{i_{h+1}}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})+\big{\|}\bm{P}^{\pi^{\star}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})-\bm{P}^{\pi_{i_{h+1}}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})\big{\|}_{\infty}\bm{1}-\frac{1}{\gamma^{2}}(\bm{Q}^{\star}-\bm{r})\circ(\bm{Q}^{\star}-\bm{r})$
$\displaystyle\overset{(\mathrm{ii})}{\leq}\bm{P}^{\pi_{i_{h+1}}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})+\frac{4}{1-\gamma}\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bm{1}-\frac{1}{\gamma^{2}}(\bm{Q}^{\star}-\bm{r})\circ(\bm{Q}^{\star}-\bm{r})$
$\displaystyle=\frac{1}{\gamma^{2}}\big{(}\gamma^{2}\bm{P}^{\pi_{i_{h+1}}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})-\bm{Q}^{\star}\circ\bm{Q}^{\star}\big{)}+\frac{4}{1-\gamma}\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bm{1}-\frac{1}{\gamma^{2}}\bm{r}\circ\bm{r}+\frac{2}{\gamma^{2}}\bm{Q}^{\star}\circ\bm{r}$
$\displaystyle\overset{(\mathrm{iii})}{\leq}\frac{1}{\gamma}\big{(}\gamma\bm{P}^{\pi_{i_{h+1}}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})-\bm{Q}^{\star}\circ\bm{Q}^{\star}\big{)}+\frac{2}{\gamma^{2}}\bm{Q}^{\star}\circ\bm{r}+\frac{4}{1-\gamma}\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bm{1},$ (90)

where (i) relies on the identity
$\bm{Q}^{\star}=\bm{r}+\gamma\bm{P}\bm{V}^{\star}$, and (iii) holds since
$0<\gamma<1$. To justify (ii), we make the following observation:

$\displaystyle\big{\|}\bm{P}^{\pi_{i_{h+1}}}\big{(}\bm{Q}^{\star}\circ\bm{Q}^{\star}\big{)}-\bm{P}^{\pi^{\star}}\big{(}\bm{Q}^{\star}\circ\bm{Q}^{\star}\big{)}\big{\|}_{\infty}=\big{\|}\bm{P}\bm{\Pi}^{\pi_{i_{h+1}}}\big{(}\bm{Q}^{\star}\circ\bm{Q}^{\star}\big{)}-\bm{P}\bm{\Pi}^{\pi^{\star}}\big{(}\bm{Q}^{\star}\circ\bm{Q}^{\star}\big{)}\big{\|}_{\infty}$
$\displaystyle\quad\overset{(\mathrm{iv})}{\leq}\big{\|}\bm{\Pi}^{\pi_{i_{h+1}}}\big{(}\bm{Q}^{\star}\circ\bm{Q}^{\star}\big{)}-\bm{\Pi}^{\pi^{\star}}\big{(}\bm{Q}^{\star}\circ\bm{Q}^{\star}\big{)}\big{\|}_{\infty}$
$\displaystyle\quad=\big{\|}\big{(}\bm{\Pi}^{\pi_{i_{h+1}}}\bm{Q}^{\star}-\bm{\Pi}^{\pi^{\star}}\bm{Q}^{\star}\big{)}\circ\big{(}\bm{\Pi}^{\pi_{i_{h+1}}}\bm{Q}^{\star}+\bm{\Pi}^{\pi^{\star}}\bm{Q}^{\star}\big{)}\big{\|}_{\infty}$
$\displaystyle\quad\overset{(\mathrm{v})}{\leq}\frac{2}{1-\gamma}\big{\|}\bm{\Pi}^{\pi_{i_{h+1}}}\bm{Q}^{\star}-\bm{\Pi}^{\pi^{\star}}\bm{Q}^{\star}\big{\|}_{\infty}$
$\displaystyle\quad\leq\frac{2}{1-\gamma}\Big{(}\big{\|}\bm{\Pi}^{\pi_{i_{h+1}}}\bm{Q}^{\star}-\bm{\Pi}^{\pi_{i_{h+1}}}\bm{Q}_{i_{h+1}}\big{\|}_{\infty}+\big{\|}\bm{\Pi}^{\pi_{i_{h+1}}}\bm{Q}_{i_{h+1}}-\bm{V}^{\star}\big{\|}_{\infty}\Big{)}$
$\displaystyle\quad\overset{\mathrm{(vi)}}{\leq}\frac{2}{1-\gamma}\Big{(}\big{\|}\bm{Q}^{\star}-\bm{Q}_{i_{h+1}}\big{\|}_{\infty}+\big{\|}\bm{V}_{i_{h+1}}-\bm{V}^{\star}\big{\|}_{\infty}\Big{)}$
$\displaystyle\quad\overset{\mathrm{(vii)}}{\leq}\frac{4}{1-\gamma}\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty},$

where (iv) arises from the fact
$\|\bm{P}\bm{z}\|_{\infty}\leq\|\bm{P}\|_{1}\|\bm{z}\|_{\infty}=\|\bm{z}\|_{\infty}$,
(v) is valid because $\|\bm{Q}^{\star}\|_{\infty}\leq 1/(1-\gamma)$, (vi)
follows from the fact that
$\bm{V}_{i_{h+1}}=\bm{\Pi}^{\pi_{i_{h+1}}}\bm{Q}_{i_{h+1}}$, and (vi) holds
since
$\|\bm{V}_{i_{h+1}}-\bm{V}^{\star}\|_{\infty}\leq\|\bm{Q}_{i_{h+1}}-\bm{Q}^{\star}\|_{\infty}$.

As it turns out, the first term in (90) allows one to build a telescoping sum.
Specifically, invoking (90) allows one to bound

$\displaystyle\sum_{h=0}^{H-1}\prod_{k=1}^{h}\gamma\bm{P}^{\pi_{i_{k}}}\mathsf{Var}_{\bm{P}}(\bm{V}^{\star})$
$\displaystyle\leq\frac{1}{\gamma}\sum_{h=0}^{H-1}\prod_{k=1}^{h}\gamma\bm{P}^{\pi_{i_{k}}}\big{(}\gamma\bm{P}^{\pi_{i_{h+1}}}(\bm{Q}^{\star}\circ\bm{Q}^{\star})-\bm{Q}^{\star}\circ\bm{Q}^{\star}\big{)}$
$\displaystyle\qquad\qquad+\frac{4}{1-\gamma}\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\bm{1}+\frac{2}{\gamma^{2}}\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\left(\bm{Q}^{\star}\circ\bm{r}\right)$
$\displaystyle\overset{(\mathrm{i})}{=}\frac{1}{\gamma}\Big{(}\sum_{h=0}^{H-1}\prod_{k=1}^{h+1}\gamma\bm{P}^{\pi_{i_{k}}}-\sum_{h=0}^{H-1}\prod_{k=1}^{h}\gamma\bm{P}^{\pi_{i_{k}}}\Big{)}\left(\bm{Q}^{\star}\circ\bm{Q}^{\star}\right)$
$\displaystyle\qquad\qquad+\frac{4}{1-\gamma}\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\sum_{h=0}^{H-1}\gamma^{h}\bm{1}+\frac{2}{\gamma^{2}}\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\left(\bm{Q}^{\star}\circ\bm{r}\right)$
$\displaystyle\leq\frac{1}{\gamma}\bigg{(}\prod_{k=1}^{H}\gamma\bm{P}^{\pi_{i_{k}}}-\bm{I}\bigg{)}\left(\bm{Q}^{\star}\circ\bm{Q}^{\star}\right)+\frac{4}{(1-\gamma)^{2}}\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bm{1}$
$\displaystyle\qquad\qquad+\frac{2}{\gamma^{2}}\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\left(\bm{Q}^{\star}\circ\bm{r}\right)$
$\displaystyle\overset{(\mathrm{ii})}{\leq}\bigg{(}\frac{2}{\gamma}\|\bm{Q}^{\star}\|_{\infty}^{2}+\frac{4}{(1-\gamma)^{2}}\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}+\frac{2}{\gamma^{2}}\frac{1}{1-\gamma}\|\bm{Q}^{\star}\|_{\infty}\|\bm{r}\|_{\infty}\bigg{)}\bm{1}$
$\displaystyle\overset{(\mathrm{iii})}{\leq}\frac{1}{(1-\gamma)^{2}}\bigg{(}\frac{2}{\gamma}+4\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}+\frac{2}{\gamma^{2}}\bigg{)}\bm{1}$
$\displaystyle\leq\frac{1}{(1-\gamma)^{2}}\bigg{(}\frac{4}{\gamma^{2}}+4\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bigg{)}\bm{1}.$ (91)

Here, (i) comes from the identity
$\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}\bm{1}=\bm{1}$; (ii) holds because each
row of $\prod_{k=1}^{h}\bm{P}^{\pi_{i_{k}}}$ has unit $\|\cdot\|_{1}$ norm for
any $h$; (iii) arises from the bound $\|\bm{Q}^{\star}\|_{\infty}\leq
1/(1-\gamma)$. This completes the proof, as long as the claim (88) can be
justified.

##### Proof of the inequality (88).

To validate this result, we make the observation that

$\displaystyle\mathsf{Var}_{\bm{P}}(\bm{V}_{i})-\mathsf{Var}_{\bm{P}}(\bm{V}^{\star})$
$\displaystyle=\big{[}\bm{P}(\bm{V}_{i}\circ\bm{V}_{i})-(\bm{P}\bm{V}_{i})\circ(\bm{P}\bm{V}_{i})\big{]}-\big{[}\bm{P}(\bm{V}^{\star}\circ\bm{V}^{\star})-(\bm{P}\bm{V}^{\star})\circ(\bm{P}\bm{V}^{\star})\big{]}$
$\displaystyle=\bm{P}(\bm{V}_{i}\circ\bm{V}_{i}-\bm{V}^{\star}\circ\bm{V}^{\star})+(\bm{P}\bm{V}^{\star})\circ(\bm{P}\bm{V}^{\star})-(\bm{P}\bm{V}_{i})\circ(\bm{P}\bm{V}_{i})$
$\displaystyle=\bm{P}\big{(}(\bm{V}_{i}-\bm{V}^{\star})\circ(\bm{V}_{i}+\bm{V}^{\star})\big{)}+(\bm{P}\bm{V}^{\star}-\bm{P}\bm{V}_{i})\circ(\bm{P}\bm{V}^{\star}+\bm{P}\bm{V}_{i})$
$\displaystyle\leq\Big{\\{}\big{\|}\bm{P}\big{(}(\bm{V}_{i}-\bm{V}^{\star})\circ(\bm{V}_{i}+\bm{V}^{\star})\big{)}\big{\|}_{\infty}+\big{\|}(\bm{P}\bm{V}^{\star}-\bm{P}\bm{V}_{i})\circ(\bm{P}\bm{V}^{\star}+\bm{P}\bm{V}_{i})\big{\|}_{\infty}\Big{\\}}\bm{1}$
$\displaystyle\leq\frac{4}{1-\gamma}\|\bm{\Delta}_{i}\|_{\infty}\bm{1}.$

Here, the last inequality follows since (by applying Lemma 4)

$\big{\|}\bm{P}\big{(}(\bm{V}_{i}-\bm{V}^{\star})\circ(\bm{V}_{i}+\bm{V}^{\star})\big{)}\big{\|}_{\infty}\leq\|\bm{P}\|_{1}\|\bm{V}_{i}-\bm{V}^{\star}\|_{\infty}\|\bm{V}_{i}+\bm{V}^{\star}\|_{\infty}\leq\frac{2}{1-\gamma}\|\bm{\Delta}_{i}\|_{\infty},$
$\text{and}\quad\big{\|}(\bm{P}\bm{V}^{\star}-\bm{P}\bm{V}_{i})\circ(\bm{P}\bm{V}^{\star}+\bm{P}\bm{V}_{i})\big{\|}_{\infty}\leq\|\bm{P}\|_{1}\|\bm{V}_{i}-\bm{V}^{\star}\|_{\infty}\cdot\|\bm{P}\|_{1}\|\bm{V}_{i}+\bm{V}^{\star}\|_{\infty}\leq\frac{2}{1-\gamma}\|\bm{\Delta}_{i}\|_{\infty}.$

##### A useful extension of Lemma 5.

Before concluding, we make note of the following extension that proves useful
for studying asynchronous Q-learning.

######  Lemma 6.

Suppose that $t\geq\frac{T}{c_{2}\log T}$. Then one has

$\sum_{h=0}^{H-1}\gamma^{h}\prod_{k=1}^{h}\bm{P}^{\widehat{\pi}_{k}}\max_{\frac{t}{2}\leq
i<t}\mathsf{Var}_{\bm{P}}(\bm{V}_{i})\leq\frac{4}{\gamma^{2}(1-\gamma)^{2}}\Big{(}1+2\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\Big{)}\bm{1}$ (92)

for any set of policies $\\{\widehat{\pi}_{k}\\}$ obeying
$\\{\widehat{\pi}_{k}\\}\subseteq\Pi$. Here, we define

$\displaystyle\begin{aligned}
\Pi\coloneqq\big{\\{}\pi=[\pi(s)]_{s\in\mathcal{S}}\,\big{|}\,\pi(s)\in\Pi_{s},\forall
s\in\mathcal{S}\big{\\}},\qquad\Pi_{s}\coloneqq\big{\\{}\pi_{i}(s)\mid
i\in[t/2,t)\big{\\}}.\end{aligned}$ (93)

The key difference between Lemma 6 and Lemma 5 is that: the components of
$\widehat{\pi}_{k}$ corresponding to different states can be chosen in a
separate manner. The proof follows from an identical argument as the above
proof of Lemma 5, and is hence omitted.

##  Appendix C Analysis for TD learning (Theorem 1)

As it turns out, if $|\mathcal{A}|=1$ (which reduces to the case of TD
learning), we can further modify the previous analysis in Section B to yield
an improved $\frac{1}{(1-\gamma)^{3}}$ scaling. This forms the main content of
this section, which leads to the proof of Theorem 1 for TD learning. Akin to
the Q-learning case, we proceed to establish a more general version of Theorem
1 that covers the full $\varepsilon$-range. This is formally stated below,
which subsumes Theorem 1 as a special case.

######  Theorem 7.

Consider any $\gamma\in(0,1)$ and any
$\varepsilon\in\big{(}0,\frac{1}{1-\gamma}\big{]}$. Theorem 1 continues to
hold if

$T\geq\frac{c_{3}\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{3}\min\\{\varepsilon,\varepsilon^{2}\\}}$
(94)

for some sufficiently large universal constant $c_{3}>0$.

###  C.1 Preliminary facts

Before embarking on the analysis, we begin by presenting several useful
preliminary facts. The first one is a direct consequence of the claimed
iteration complexity (94) when $\varepsilon\leq\frac{1}{1-\gamma}$:

$T\geq\frac{c_{3}\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{3}\min\\{\varepsilon,\varepsilon^{2}\\}}\geq\frac{c_{3}\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{2}},$
(95)

a simple fact that will be used multiple times. In addition, the update rule
(7) of TD learning can be expressed using vector/matrix notation as follows

$\displaystyle\bm{V}_{t}=(1-\eta_{t})\bm{V}_{t-1}+\eta_{t}(\bm{r}+\gamma\bm{P}_{t}\bm{V}_{t-1})\qquad\text{for
all }t\geq 1,$ (96)

where the matrix $\bm{P}_{t}\in\\{0,1\\}^{|\mathcal{S}|\times|\mathcal{S}|}$
obeys

$\bm{P}_{t}(s,s^{\prime})\coloneqq\begin{cases}1,\quad&\text{if
}s^{\prime}=s_{t}(s)\\\ 0,&\text{else}\end{cases}$

for any $s,s^{\prime}\in\mathcal{S}$. In the sequel, we collect a few other
facts concerning the range of $\bm{V}_{t}$ and learning rates.

##### Range of $\bm{V}_{t}$.

We claim that: when the initialization $\bm{V}_{0}$ obeys
$\bm{0}\leq\bm{V}_{0}\leq\frac{1}{1-\gamma}\bm{1}$, the TD learning iterates
obey

$\displaystyle\bm{0}\leq\bm{V}_{t}\leq\frac{1}{1-\gamma}\bm{1}\qquad\text{and}\qquad\|\bm{V}_{t}-\bm{V}^{\star}\|_{\infty}\leq\frac{1}{1-\gamma}\qquad\text{for
all }t\geq 0,$ (97)

provided that $0\leq\eta_{t}\leq 1$ for all $t\geq 0$. The proof follows
immediately by repeating the proof of Lemma 4 (see Section B.1) with
$|\mathcal{A}|=1$, and is hence omitted for brevity.

##### Learning rates.

We shall also collect several useful results concerning the learning rates
$\\{\eta_{t}\\}$. Let us abuse the notation by defining the following crucial
quantities:

$\eta_{k}^{(t)}\coloneqq\begin{cases}\prod_{i=1}^{t}\big{(}1-\eta_{i}(1-\gamma)\big{)},&\text{if
}k=0,\\\ \eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}(1-\gamma)\big{)},&\text{if
}0<k<t,\\\ \eta_{t},&\text{if }k=t.\end{cases}$ (98)

Note that this definition (98) differs from the one (57) used for Q-learning,
and will only be employed in this section. Consider any iteration number $t$
satisfying

$t\geq\frac{T}{c_{2}\log T}.$ (99)

Clearly, the learning rate $\eta_{t}$ under Assumption (8a) obeys

$(1-\gamma)\eta_{t}\geq\frac{1-\gamma}{1+\frac{c_{1}(1-\gamma)T}{\log^{2}T}}\geq\frac{1-\gamma}{\frac{2c_{1}(1-\gamma)T}{\log^{2}T}}=\frac{\log^{2}T}{2c_{1}T}.$
(100)

In what follows, we intend to bound $\eta_{k}^{(t)}$ for two cases separately.

  * •

For any $i$ obeying $0\leq i\leq t/2$, it is easily seen from (100) that

$\displaystyle\eta_{i}^{(t)}$
$\displaystyle\leq\big{(}1-\eta_{t/2}(1-\gamma)\big{)}^{t/2}\leq\Big{(}1-\frac{\log^{2}T}{2c_{1}T}\Big{)}^{t/2}\leq\Big{(}1-\frac{\log^{2}T}{2c_{1}T}\Big{)}^{\frac{T}{2c_{2}\log
T}}$
$\displaystyle=\left\\{\Big{(}1-\frac{\log^{2}T}{2c_{1}T}\Big{)}^{\frac{2c_{1}T}{\log^{2}T}}\right\\}^{\frac{\log
T}{4c_{1}c_{2}}}\leq\frac{1}{T^{2}},$ (101a) where the last inequality holds
as long as $c_{1}c_{2}\leq 1/8$ and (95) holds.

  * •

When it comes to the case with $i>t/2$, we can develop the following upper
bound

$\eta_{i}^{(t)}\leq\eta_{i}\leq\frac{1}{c_{2}(1-\gamma)i/\log^{2}T}<\frac{2\log^{3}T}{(1-\gamma)T},$
(101b)

which relies on Assumption (8a).

In addition, given that $\bm{P}^{k}\bm{1}=\bm{1}$ for any integer $k>0$, it
can be easily verified that

$\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\bm{1}=\prod_{i=k+1}^{t}\big{(}1-\eta_{i}(1-\gamma)\big{)}\bm{1},$

and as a result,

$\displaystyle\Bigg{\|}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\Bigg{\|}_{1}=\prod_{i=k+1}^{t}\big{(}1-\eta_{i}(1-\gamma)\big{)}.$
(102)

###  C.2 Proof of Theorem 7

##### Step 1: decomposing the error $\bm{V}_{t}-\bm{V}^{\star}$.

Taking $\bm{\Delta}_{t}\coloneqq\bm{V}_{t}-\bm{V}^{\star}$, via the basic
relation (23), the TD learning update rule can be written as

$\displaystyle\bm{\Delta}_{t}$
$\displaystyle=(1-\eta_{t})\bm{\Delta}_{t-1}+\eta_{t}\gamma\big{(}\bm{P}\bm{\Delta}_{t-1}+(\bm{P}_{t}-\bm{P})\bm{V}_{t-1}\big{)}$
$\displaystyle=\big{(}\bm{I}-\eta_{t}(\bm{I}-\gamma\bm{P})\big{)}\bm{\Delta}_{t-1}+\eta_{t}\gamma(\bm{P}_{t}-\bm{P})\bm{V}_{t-1}.$
(103)

Invoking the above relation recursively then leads to

$\displaystyle\bm{\Delta}_{t}=\prod_{i=1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\bm{\Delta}_{0}+\underbrace{\sum_{k=1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\gamma(\bm{P}_{k}-\bm{P})\bm{V}_{k-1}}_{\eqqcolon\,\bm{\xi}_{t}}.$
(104)

##### Step 2: controlling the first term of (104).

With regards to the first term of (104), we make the observation that

$\displaystyle\Big{\|}\prod_{i=1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\bm{\Delta}_{0}\Big{\|}_{\infty}$
$\displaystyle\leq\Big{\|}\prod_{i=1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\Big{\|}_{1}\left\|\bm{\Delta}_{0}\right\|_{\infty}$
$\displaystyle=\left\\{\prod_{i=1}^{t}\big{(}1-\eta_{i}(1-\gamma)\big{)}\right\\}\left\|\bm{\Delta}_{0}\right\|_{\infty}$
$\displaystyle\leq\eta_{0}^{(t)}\cdot\frac{1}{1-\gamma}\leq\frac{1}{(1-\gamma)T^{2}},$
(105)

where the second line arises from (102), and the last inequality holds true
due to (101a) as long as $t\geq\frac{T}{c_{2}\log T}.$

##### Step 3: controlling the second term of (104).

We then move on to the second term $\bm{\xi}_{t}$ in (104), which admits the
following expression

$\displaystyle\bm{\xi}_{t}=\sum_{k=1}^{t}\bm{z}_{k}\qquad\text{with
}\bm{z}_{k}\coloneqq\eta_{k}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\gamma(\bm{P}_{k}-\bm{P})\bm{V}_{k-1}.$
(106)

Here, the summands $\\{\bm{z}_{k}\\}$ clearly satisfy

$\mathbb{E}\big{[}\bm{z}_{k}\,|\,\bm{V}_{k-1},\cdots,\bm{V}_{0}\big{]}=\bm{0}.$

We then attempt to invoke the Freedman inequality (see Theorem 5) to control
this term. Towards this end, there are several quantities that need to be
calculated.

  * •

First of all, we observe that

$\displaystyle B$ $\displaystyle\coloneqq\max_{1\leq k\leq
t}\|\bm{z}_{k}\|_{\infty}\leq\max_{1\leq k\leq
t}\Big{\|}\eta_{k}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\gamma(\bm{P}_{k}-\bm{P})\bm{V}_{k-1}\Big{\|}_{\infty}$
$\displaystyle\leq\max_{1\leq k\leq
t}\Big{\|}\eta_{k}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\Big{\|}_{1}\big{\|}(\bm{P}_{k}-\bm{P})\bm{V}_{k-1}\big{\|}_{\infty}$
$\displaystyle=\max_{1\leq k\leq
t}\left\\{\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}(1-\gamma)\big{)}\right\\}\big{\|}(\bm{P}_{k}-\bm{P})\bm{V}_{k-1}\big{\|}_{\infty}$
$\displaystyle\leq\max_{1\leq k\leq
t}\eta_{k}^{(t)}\big{(}\|\bm{P}_{k}\|_{1}+\|\bm{P}\|_{1}\big{)}\|\bm{V}_{k-1}\|_{\infty}\leq\frac{4\log^{3}T}{(1-\gamma)^{2}T},$
(107)

where the third line again makes use of the relation (102) and the last line
follows the facts $\|\bm{P}_{k}\|_{1}=\|\bm{P}\|_{1}=1$,
$\|\bm{V}_{k-1}\|_{\infty}\leq 1/(1-\gamma)$, as well as the properties (101).

  * •

The next step is to control certain variance terms. Towards this, we first
make note of a userful fact. For any given non-negative vector
$\bm{u}=[u_{i}]_{1\leq i\leq|\mathcal{S}|}\geq\bm{0}$ and any vector $\bm{v}$,
it is easily seen that

$\displaystyle\mathsf{Var}\Big{(}\bm{u}^{\top}(\bm{P}_{k}-\bm{P})\bm{v}\Big{)}$
$\displaystyle=\sum_{i=1}^{|\mathcal{S}|}u_{i}^{2}\mathsf{Var}\Big{(}(\bm{P}_{k}-\bm{P})_{i,\cdot}\bm{v}\Big{)}\leq\Big{\\{}\max_{i}|u_{i}|\Big{\\}}\big{[}u_{1},\cdots,u_{|\mathcal{S}|}\big{]}\mathsf{Var}_{\bm{P}}\left(\bm{v}\right)$
$\displaystyle\leq\|\bm{u}\|_{1}\bm{u}^{\top}\mathsf{Var}_{\bm{P}}\left(\bm{v}\right),$
(108)

where we remind the reader of the notation $\mathsf{Var}_{\bm{P}}(\bm{v})$ in
(17). Additionally, for any vector $\bm{a}=[a_{j}]$, let us employ the
notation $\mathsf{Var}\big{(}\bm{a}\,|\,\bm{V}_{k-1},\cdots,\bm{V}_{0}\big{)}$
to represent a vector whose $j$-th entry is given by
$\mathsf{Var}\big{(}a_{j}\,|\,\bm{V}_{k-1},\cdots,\bm{V}_{0}\big{)}$. Armed
with this notation, we obtain

$\displaystyle\mathsf{Var}\big{(}\bm{z}_{k}\,|\,\bm{V}_{k-1},\cdots,\bm{V}_{0}\big{)}$
$\displaystyle\leq\gamma^{2}\Big{\|}\eta_{k}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\Big{\|}_{1}\left\\{\eta_{k}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\right\\}\mathsf{Var}_{\bm{P}}\left(\bm{V}_{k-1}\right)$
$\displaystyle=\gamma^{2}\left\\{\eta_{k}\prod_{i=k+1}^{t}\big{(}1-\eta_{i}(1-\gamma)\big{)}\right\\}\left\\{\eta_{k}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\right\\}\mathsf{Var}_{\bm{P}}\left(\bm{V}_{k-1}\right)$
$\displaystyle\leq\eta_{k}\eta_{k}^{(t)}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\mathsf{Var}_{\bm{P}}\left(\bm{V}_{k-1}\right),$
(109)

where the first inequality is a consequence of (108) and the definition of
$\bm{z}_{k}$ (cf. (106)), the second line arises from (102), and the last
relation results from the definition of $\eta_{k}^{(t)}$. This in turn allows
us to compute

$\displaystyle\bm{W}_{t}$
$\displaystyle\coloneqq\sum_{k=1}^{t}\mathsf{Var}\big{(}\bm{z}_{k}\,|\,\bm{V}_{k-1},\cdots,\bm{V}_{0}\big{)}\leq\sum_{k=1}^{t}\eta_{k}\eta_{k}^{(t)}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\mathsf{Var}_{\bm{P}}\left(\bm{V}_{k-1}\right)$
$\displaystyle\leq\sum_{k=1}^{t/2}\eta_{k}^{(t)}\Big{\|}\eta_{k}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\Big{\|}_{1}\|\bm{V}_{k-1}\|_{\infty}^{2}\bm{1}+\sum_{k=t/2+1}^{t}\eta_{k}\eta_{k}^{(t)}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\mathsf{Var}_{\bm{P}}\left(\bm{V}_{k-1}\right)$
$\displaystyle\leq\sum_{k=1}^{t/2}\big{(}\eta_{k}^{(t)}\big{)}^{2}\frac{1}{(1-\gamma)^{2}}\bm{1}+\Big{\\{}\max_{k:\,t/2<k\leq
t}\eta_{k}^{(t)}\Big{\\}}\sum_{k=t/2+1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\mathsf{Var}_{\bm{P}}\left(\bm{V}_{k-1}\right)$
$\displaystyle\leq\frac{1}{2(1-\gamma)^{2}T^{3}}\bm{1}+\frac{2\log^{3}T}{(1-\gamma)T}\Bigg{(}\sum_{k=t/2+1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\Bigg{)}\max_{k:\,t/2\leq
k<t}\mathsf{Var}_{\bm{P}}\big{(}\bm{V}_{k}\big{)}$
$\displaystyle\leq\frac{1}{2(1-\gamma)^{2}T^{3}}\bm{1}+\frac{2\log^{3}T}{(1-\gamma)T}(\bm{I}-\gamma\bm{P})^{-1}\max_{k:\,t/2\leq
k<t}\mathsf{Var}_{\bm{P}}\big{(}\bm{V}_{k}\big{)},$ (110)

where the penultimate inequality results from (101); to see why the last
inequality holds, observe that

$\displaystyle\sum_{k=t/2+1}^{t}\eta_{k}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}$
$\displaystyle\qquad\qquad=(\bm{I}-\gamma\bm{P})^{-1}\sum_{k=t/2+1}^{t}\eta_{k}(\bm{I}-\gamma\bm{P})\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}$
$\displaystyle\qquad\qquad=(\bm{I}-\gamma\bm{P})^{-1}\sum_{k=t/2+1}^{t}\bigg{[}\prod_{i=k+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}-\prod_{i=k}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\bigg{]}$
$\displaystyle\qquad\qquad=(\bm{I}-\gamma\bm{P})^{-1}-(\bm{I}-\gamma\bm{P})^{-1}\prod_{i=t/2+1}^{t}\big{(}\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})\big{)}\leq(\bm{I}-\gamma\bm{P})^{-1},$

where we have used the fact that all entries of $(\bm{I}-\gamma\bm{P})^{-1}$
and $\bm{I}-\eta_{i}(\bm{I}-\gamma\bm{P})$ are non-negative.

  * •

In addition, we also derive the following trivial upper bound based on (110):

$\displaystyle\big{|}\bm{W}_{t}\big{|}$
$\displaystyle\leq\frac{1}{2(1-\gamma)^{2}T^{3}}\bm{1}+\frac{2\log^{3}T}{(1-\gamma)T}\big{\|}(\bm{I}-\gamma\bm{P})^{-1}\big{\|}_{1}\max_{k:\,t/2\leq
k<t}\big{\|}\mathsf{Var}_{\bm{P}}\big{(}\bm{V}_{k}\big{)}\big{\|}_{\infty}\bm{1}$
$\displaystyle\leq\frac{1}{2(1-\gamma)^{2}T^{3}}\bm{1}+\frac{2\log^{3}T}{(1-\gamma)^{4}T}\bm{1}\leq\frac{3\log^{3}T}{(1-\gamma)^{4}T}\bm{1}\eqqcolon\sigma^{2}\bm{1},$
(111)

where we have invoked the fact that
$\|(\bm{I}-\gamma\bm{P})^{-1}\|_{1}=1/(1-\gamma)$. Therefore, by setting
$K=\big{\lceil}2\log_{2}\frac{1}{1-\gamma}\big{\rceil}$, one arrives at

$\frac{\sigma^{2}}{2^{K}}\leq\frac{3\log^{3}T}{(1-\gamma)^{2}T}.$ (112)

Equipped with the preceding bounds, let us apply the Freedman inequality in
Theorem 5 and invoke the union bound over all entries of $\bm{\xi}_{t}$ to
show that

$\displaystyle|\bm{\xi}_{t}|$
$\displaystyle\leq\sqrt{8\Big{(}\bm{W}_{t}+\frac{\sigma^{2}}{2^{K}}\bm{1}\Big{)}\log\frac{8|\mathcal{S}|T\log\frac{1}{1-\gamma}}{\delta}}+\Big{(}\frac{4}{3}B\log\frac{8|\mathcal{S}|T\log\frac{1}{1-\gamma}}{\delta}\Big{)}\bm{1}$
$\displaystyle\leq\sqrt{16\Big{(}\bm{W}_{t}+\frac{3\log^{3}T}{(1-\gamma)^{2}T}\bm{1}\Big{)}\log\frac{|\mathcal{S}|T}{\delta}}+\Big{(}3B\log\frac{|\mathcal{S}|T}{\delta}\Big{)}\bm{1}$
$\displaystyle\leq\sqrt{\frac{32\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}|T}{\delta}\big{)}}{(1-\gamma)T}\Big{(}(\bm{I}-\gamma\bm{P})^{-1}\max_{k:\,t/2\leq
k<t}\mathsf{Var}_{\bm{P}}\big{(}\bm{V}_{k}\big{)}+\frac{2}{1-\gamma}\bm{1}\Big{)}}+\frac{12\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}|T}{\delta}\big{)}}{(1-\gamma)^{2}T}\bm{1}$

with probability at least $1-\delta/T.$ Here, the second line follows since

$\log\frac{8|\mathcal{S}|T\log\frac{1}{1-\gamma}}{\delta}\leq
2\log\frac{|\mathcal{S}|T}{\delta}$

as long as $\frac{|\mathcal{S}|T}{\delta}\geq 8\log\frac{1}{1-\gamma}$,
whereas the last line holds by using (107), (110) and (112). Further, we make
the observation that

$\displaystyle(\bm{I}-\gamma\bm{P})^{-1}\mathsf{Var}_{\bm{P}}\big{(}\bm{V}^{\star}\big{)}$
$\displaystyle=(\bm{I}-\gamma\bm{P})^{-1}\Big{(}\bm{P}(\bm{V}^{\star}\circ\bm{V}^{\star})-(\bm{P}\bm{V}^{\star})\circ(\bm{P}\bm{V}^{\star})\Big{)}$
$\displaystyle=(\bm{I}-\gamma\bm{P})^{-1}\left(\bm{P}(\bm{V}^{\star}\circ\bm{V}^{\star})-\frac{1}{\gamma^{2}}(\bm{V}^{\star}-\bm{r})\circ(\bm{V}^{\star}-\bm{r})\right)$
$\displaystyle\leq(\bm{I}-\gamma\bm{P})^{-1}\left(\bm{P}(\bm{V}^{\star}\circ\bm{V}^{\star})-\frac{1}{\gamma^{2}}\bm{V}^{\star}\circ\bm{V}^{\star}+\frac{2}{\gamma^{2}}\bm{r}\circ\bm{V}^{\star}\right)$
$\displaystyle\leq(\bm{I}-\gamma\bm{P})^{-1}\left(\bm{P}(\bm{V}^{\star}\circ\bm{V}^{\star})-\frac{1}{\gamma}\bm{V}^{\star}\circ\bm{V}^{\star}+\frac{2}{\gamma^{2}}\bm{r}\circ\bm{V}^{\star}\right)$
$\displaystyle=\frac{1}{\gamma}(\bm{I}-\gamma\bm{P})^{-1}\left(\gamma\bm{P}-\bm{I}\right)\left(\bm{V}^{\star}\circ\bm{V}^{\star}\right)+\frac{2}{\gamma^{2}}(\bm{I}-\gamma\bm{P})^{-1}\left(\bm{r}\circ\bm{V}^{\star}\right)$
$\displaystyle\leq\frac{2}{\gamma^{2}}(\bm{I}-\gamma\bm{P})^{-1}\left(\bm{r}\circ\bm{V}^{\star}\right)\leq\frac{2}{\gamma^{2}(1-\gamma)^{2}}\bm{1},$

where the second line makes use of the basic relation
$\bm{V}^{\star}=\bm{r}+\gamma\bm{P}\bm{V}^{\star}$. As a consequence, we
conclude

$\displaystyle(\bm{I}-\gamma\bm{P})^{-1}\max_{k:\,t/2\leq
k<t}\mathsf{Var}_{\bm{P}}\big{(}\bm{V}_{k}\big{)}$
$\displaystyle\leq(\bm{I}-\gamma\bm{P})^{-1}\Big{(}\mathsf{Var}_{\bm{P}}\big{(}\bm{V}^{\star}\big{)}+\frac{4}{1-\gamma}\max_{k:\,t/2\leq
k<t}\|\bm{\Delta}_{k}\|_{\infty}\bm{1}\Big{)}$
$\displaystyle\leq\frac{2}{\gamma(1-\gamma)^{2}}\Big{(}1+2\max_{k:\,t/2\leq
k<t}\|\bm{\Delta}_{k}\|_{\infty}\Big{)}\bm{1}.$ (113)

Here, the first inequality arises from (88), while the second inequality holds
due to the facts that
$\big{\|}(\bm{I}-\gamma\bm{P})^{-1}\big{\|}_{1}=1/(1-\gamma)$.

##### Step 4: putting everything together.

Consequently, substituting the bounds in Steps 2-3 into (104) yields

$\displaystyle\|\bm{\Delta}_{t}\|_{\infty}$ $\displaystyle\leq
30\sqrt{\frac{\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{3}T}\bigg{(}1+\max_{\frac{t}{2}\leq
i<t}\|\bm{\Delta}_{i}\|_{\infty}\bigg{)}}\qquad\text{for all}\quad
t\geq\frac{T}{c_{2}\log T}.$ (114)

Repeating the same argument as in Section B.4, we see that

$\displaystyle\|\bm{\Delta}_{T}\|_{\infty}$ $\displaystyle\leq
c_{9}\bigg{(}\sqrt{\frac{\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{3}T}}+\frac{\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{3}T}\bigg{)}$
(115)

holds with probability at least $1-\delta$, where $c_{9}>0$ is some universal
constant. As a result, one has

$\displaystyle\|\bm{\Delta}_{T}\|_{\infty}$
$\displaystyle\leq\frac{1}{2}\bigg{(}\sqrt{\min\\{\varepsilon,\varepsilon^{2}\\}}+\min\\{\varepsilon,\varepsilon^{2}\\}\bigg{)}=\frac{1}{2}\left(\varepsilon+\varepsilon^{2}\right)\mathds{1}\\{\varepsilon\leq
1\\}+\frac{1}{2}\left(\varepsilon+\varepsilon^{2}\right)\mathds{1}\\{\varepsilon>1\\}\leq\varepsilon,$

as long as the sample size satisfies the following

$\frac{\big{(}\log^{3}T\big{)}\big{(}\log\frac{|\mathcal{S}|T}{\delta}\big{)}}{\gamma^{2}(1-\gamma)^{3}T}\leq\frac{\min\\{\varepsilon,\varepsilon^{2}\\}}{c_{3}},$

for some constant $c_{3}\geq\max\\{1,2c_{9}\\}$. This requirement is
equivalent to condition (94) as claimed.

##  Appendix D Lower bound: sub-optimality of Q-learning (Theorem 3)

In this section, we establish the lower bound claimed in Theorem 3 by
analyzing Q-learning for the MDP instance constructed in Section 4.3. Without
loss of generality, we assume

$\log T\leq\frac{1}{1-\gamma}$ (116)

throughout the proof; otherwise the lower bound in Theorem 3 is worse than the
minimax lower bound $\frac{1}{(1-\gamma)^{3}T}$ in Azar et al., (2013).

Throughout, we shall use $P_{t}$ to represent the sample transitions such that
for any triple $(s,a,s^{\prime})$,

$\displaystyle P_{t}(s^{\prime}\,|\,s,a)\coloneqq\begin{cases}1,\quad&\text{if
}s_{t}(s,a)=s^{\prime},\\\ 0,&\text{otherwise},\end{cases}$ (117)

where $s_{t}(s,a)$ stands for the sample collected in the $t$-th iteration
(see (5)). Recognizing that state 2 is associated with a singleton action
space, we shall often write

$P_{t}(s^{\prime}\,|\,2)\coloneqq P_{t}(s^{\prime}\,|\,2,1)$

for notational simplicity.