Instance-optimality in optimal value estimation:
Adaptivity via variance-reduced $Q$-learning

Koulik Khamaru†,∗ Eric Xia†,∗,
---
Martin J. Wainwright†,⋆ Michael I. Jordan†,⋆
Department of Statistics†, and
---
Department of Electrical Engineering and Computer Sciences⋆
UC Berkeley, Berkeley, CA 94720
00footnotetext: $\ast$ denotes equal contribution to this work.

###### Abstract

Various algorithms in reinforcement learning exhibit dramatic variability in
their convergence rates and ultimate accuracy as a function of the problem
structure. Such instance-specific behavior is not captured by existing global
minimax bounds, which are worst-case in nature. We analyze the problem of
estimating optimal $Q$-value functions for a discounted Markov decision
process with discrete states and actions and identify an instance-dependent
functional that controls the difficulty of estimation in the
$\ell_{\infty}$-norm. Using a local minimax framework, we show that this
functional arises in lower bounds on the accuracy on any estimation procedure.
In the other direction, we establish the sharpness of our lower bounds, up to
factors logarithmic in the state and action spaces, by analyzing a variance-
reduced version of $Q$-learning. Our theory provides a precise way of
distinguishing “easy” problems from “hard” ones in the context of
$Q$-learning, as illustrated by an ensemble with a continuum of difficulty.

##  1 Introduction

The need for data-driven decision-making has fueled tremendous interest in
Markov decision processes and reinforcement learning (RL). Indeed, such
techniques have found use cases across a wide range of application domains
[22, 10, 17]. An intriguing fact is that in many applications, RL algorithms
behave far better than the theoretical bounds provided by worst-case analyses
would suggest. This gap provides impetus for a more refined _instance-
specific_ analysis, one which highlights the properties of a given instance
that render it “easy” or “difficult.”

Instance-dependent analysis of RL algorithms has become of substantial
interest in recent years [see, e.g., 18, 28, 29, 12, 15, 9]. By now, we have a
fairly refined understanding of instance-dependence for policy evaluation
problems, including work on temporal difference (TD) algorithms under the
$\ell_{2}$-norm [4, 11, 6], as well as bounds for the LSTD estimator in the
$\ell_{\infty}$-norm [15]. A subset of the current authors [9] provided a
sharper instance-dependent $\ell_{\infty}$-bounds for a variance-reduced
version of the TD$(0)$ algorithm, and showed that this algorithm is optimal in
a local non-asymptotic minimax sense.

For TD and LSTD methods, the underlying structure is linear in nature—in
particular, it corresponds to solving a linear system—a property which greatly
facilitates the analysis. In the current paper we undertake a similar
instance-dependent analysis in the more challenging setting of $Q$-learning,
for which the underlying updates are non-linear. Our main contributions are to
identify a natural functional of the problem instance and show that it
controls the fundamental difficulty of estimating optimal $Q$-value functions.
We do so by establishing non-asymptotic lower bounds within a local minimax
framework and matching those bounds, up to logarithmic factors, by analyzing a
version of variance-reduced $Q$-learning [19, 20, 26].

This work is done in the context of Markov decision processes (MDPs) with a
finite set of states $\mathcal{X}$ and a finite set of possible actions
$\mathcal{U}$. We proceed to provide some background and notation to be able
to introduce the functional that plays a central role in our analysis, and
describe our contributions in more detail.

###  1.1 Some background

In a Markov decision process, the state $x$ evolves dynamically in time under
the influence of the actions. More precisely, there is a collection of
probability transition kernels, $\\{\mathbf{P}_{u}(\cdot\mid
x)\mid(x,u)\in\mathcal{X}\times\mathcal{U}\\}$, where
$\mathbf{P}_{u}(x^{\prime}\mid x)$ denotes the transition to the state
$x^{\prime}$ when the action $u$ is taken at the current state $x$. In
addition, an MDP is equipped with a reward function $r$ that maps every state-
action pair, $(x,u)$, to a real number $r(x,u)$. The reward $r(x,u)$ is the
reward received upon performing an action $u$ in the state $x$. Overall, a
given MDP is characterized by the problem pair $(\mathbf{P},r)$, along with a
discount factor $\gamma\in(0,1)$.

A deterministic policy $\pi$ is a mapping $\mathcal{X}\to\mathcal{U}$: the
quantity $\pi(x)\in\mathcal{U}$ indicates the action to be taken in the state
$x$. The value of a policy is defined by the expected sum of discounted
rewards in an infinite sample path. For a given policy $\pi$ and discount
factor $\gamma\in(0,1)$, the $Q$-function is given by

$\displaystyle\theta^{\pi}(x,u)$
$\displaystyle:\,=\mathbb{E}\left[\sum_{k=0}^{\infty}\gamma^{k}r(x_{k},u_{k})\mid
x_{0}=x,\,u_{0}=u\right],\qquad\text{where $u_{k}=\pi(x_{k})$ for all $k\geq
1$.}$ (1)

When both the state space $\mathcal{X}$ and action space $\mathcal{U}$ are
finite, the $Q$-function $\theta$ can be conveniently represented as an
element of $\mathbb{R}^{|\mathcal{X}|\times|\mathcal{U}|}$.

There are various observation models in reinforcement learning, and in this
paper we study the _generative setting_ in which we have the ability to draw
next-state samples from the MDP when initialized with an arbitrary state-
action pair $(x,u)$. More precisely, we are given a collection of $N$ i.i.d.
samples of the form $\\{(\textbf{Z}_{k},R_{k})\\}_{k=1}^{N}$, where both
$\textbf{Z}_{k}$ and $R_{k}$ are random matrices in
$\mathbb{R}^{|\mathcal{X}|\times|\mathcal{U}|}$. For each state-action pair
$(x,u)$, the entry $\textbf{Z}_{k}(x,u)$ is drawn according to the transition
kernel $\mathbf{P}_{u}(\cdot\mid x)$, whereas the entry $R_{k}(x,u)$ is a
zero-mean random variable with mean $r(x,u)$ and $\sigma_{r}$-sub-Gaussian
tails, corresponding to a noisy observation of the reward function. Here the
rewards $\\{R_{k}(x,u)\\}_{(x,u)\in\mathcal{X}\times\mathcal{U}}$ are
independent across the all state-action pairs, and the random rewards
$\\{R_{k}\\}$ are independent of the randomness in $\\{\textbf{Z}_{k}\\}$.

Based on the observations, our goal is to estimate the optimal $Q$-value
function $\theta^{\star}$, along with an optimal policy $\pi^{\star}$. From
the classical theory of MDPs [14, 16, 2], the optimal $Q$-function is a fixed
point of the Bellman (optimality) operator $\mathbf{T}$, a map from
$\mathbb{R}^{|\mathcal{X}|\times|\mathcal{U}|}$ to itself given by

$\displaystyle\mathbf{T}(\theta)(x,u)$
$\displaystyle:\,=r(x,u)+\gamma\sum_{x^{\prime}\in\mathcal{X}}\mathbb{P}_{u}(x^{\prime}\mid
x)\max_{u^{\prime}\in\mathcal{U}}\theta(x^{\prime},u^{\prime}),$ (2)

and an optimal policy $\pi^{\star}$ can be obtained from the optimal
$Q$-function $\theta^{\star}$ via the maximization
$\pi^{\star}(x)\in\arg\max\limits_{u\in\mathcal{U}}\theta^{\star}(x,u)$. In
this paper, we measure the quality of a given estimate $\widehat{\theta}$ in
terms of the $\ell_{\infty}$-norm error:

$\displaystyle\|\widehat{\theta}-\theta^{\star}\|_{\infty}=\max_{(x,u)}|\widehat{\theta}(x,u)-\theta^{\star}(x,u)|.$
(3)

###  1.2 Contributions of this paper

The main contribution of this paper is to show that for a given MDP, the
difficulty of estimating the optimal $Q$-value function in
$\ell_{\infty}$-norm is characterized by a particular functional of the
problem instance $(\mathbf{P},r)$, defined here.

##### An instance-dependent functional:

Given a sample $(\textbf{Z},R)$ from our observation model, we can define the
single-sample empirical Bellman operator

$\displaystyle\widehat{\mathbf{T}}(\theta)$
$\displaystyle:\,=R(x,u)+\gamma\sum_{x^{\prime}\in\mathcal{X}}\textbf{Z}_{u}(x^{\prime}\mid
x)\max_{u^{\prime}\in\mathcal{U}}\theta(x^{\prime},u^{\prime}),$ (4)

where we have introduced $\textbf{Z}_{u}(x^{\prime}\mid
x):\,=\mathbbm{1}_{\textbf{Z}(x,u)=x^{\prime}}$.

Note that for any fixed $Q$-function $\theta$, the difference
$\widehat{\mathbf{T}}(\theta)-\mathbf{T}(\theta)$ is a zero-mean random
matrix, and a key object in this paper is the matrix
$\nu\in\mathbb{R}^{|\mathcal{X}|\times|\mathcal{U}|}$ with entries

$\displaystyle\nu(\pi;\mathbf{P},r,\gamma)(x,u)$
$\displaystyle:\,=\sqrt{\operatorname{Var}\Big{(}\big{(}\mathbf{I}-\gamma\mathbf{P}^{\pi}\big{)}^{-1}\big{(}\widehat{\mathbf{T}}(\theta^{\star})-\mathbf{T}(\theta^{\star})\big{)}\Big{)}}.$
(5)

More explicitly, the quantity $\mathbf{P}^{\pi}$ is a right-linear mapping of
$\mathbb{R}^{|\mathcal{X}|\times|\mathcal{U}|}$ to itself, given by:

$\displaystyle\mathbf{P}^{\pi}\theta(x,u)$
$\displaystyle:\,=\sum_{x^{\prime}\in\mathcal{X}}\mathbf{P}_{u}(x^{\prime}\mid
x)\cdot\theta(x^{\prime},\pi(x^{\prime}))\qquad\mbox{for each
$(x,u)\in\mathcal{X}\times\mathcal{U}$,}$ (6)

and the square-root and variance operators in equation (5) are applied
elementwise.

Let us provide some intuition as to why $\nu(\pi;\mathbf{P},r,\gamma)$ plays a
fundamental role. The appearance of the zero mean term
$\widehat{\mathbf{T}}(\theta^{\star})-\mathbf{T}(\theta^{\star})$ is natural:
it reflects the noise present in the empirical Bellman operator (4) as an
estimate of the population Bellman operator (2). As for the pre-factor
$(\mathbf{I}-\gamma\mathbf{P}^{\pi})^{-1}$, by a von Neumann expansion we can
write

$\displaystyle(\mathbf{I}-\gamma\mathbf{P}^{\pi})^{-1}$
$\displaystyle=\sum_{k=0}^{\infty}(\gamma\mathbf{P}^{\pi})^{k}.$

The sum of the powers of $\gamma\mathbf{P}^{\pi}$ account for the compounded
effect of an initial perturbation when following the Markov chain specified by
the policy $\pi$.

##### Upper and lower bounds:

With these definitions in place, the core of our work involves proving, via a
combination of a lower and an upper bound (matching up to logarithmic
factors), that the instance-specific difficulty of estimating the $Q$-function
is captured by the quantity
$\max_{\pi\in\mathbf{\Pi^{\star}}}\|\nu(\pi;\mathbf{P},r,\gamma)\|_{\infty}$.
Here $\mathbf{\Pi^{\star}}$ denotes the set of all optimal policies for the
MDP instance $(\mathbf{P},r)$. This functional exhibits a wide range of
behaviors: in Example 1 to follow in Section 2.1.2, we exhibit a family of
MDPs $(\mathbf{P}_{\lambda},r_{\lambda})$, parameterized by a scalar
$\lambda\geq 0$ such that

$\displaystyle\max_{\pi\in\mathbf{\Pi^{\star}}}\|\nu(\pi;\mathbf{P}_{\lambda},r_{\lambda},\gamma)\|_{\infty}$
$\displaystyle\asymp\Big{(}\frac{1}{1-\gamma}\Big{)}^{\tfrac{1}{2}-\lambda}.$

The setting $\lambda=0$ recovers a “hard” instance, one for which the global
minimax bound for estimation of $Q$-functions, known from past work [1] on
batched $Q$-learning, is sharp. On the other hand, as $\lambda$ grows, the
problems in this family become progressively easier, so that the global
minimax bound is no longer sharp.

In more detail, we prove a non-asymptotic lower bound, stated as Theorem 1 to
follow, by adapting a particular definition of local minimax risk studied in
past work on shape-constrained estimation [5]. The central challenge in this
proof is that perturbations to the transition matrices of a given MDP change
not only the transitions themselves, but also the structure of the optimal
policies. In order to prove matching upper bounds, given the role of the
empirical operators $\widehat{\mathbf{T}}$ in our lower bound, which are used
in the classical $Q$-learning algorithm [27, 23, 21, 7], a natural thought
would be to analyze this operator directly. However, it is known from past
work [25] that the classical $Q$-learning algorithm is _non-optimal_ , even
when assessed when using the coarser metric of global minimax. Thus, in order
to obtain a sharp upper bound, we turn to variance-reduced forms of
$Q$-learning, as introduced in past work [19, 20, 26] and shown to be optimal
in a globally minimax sense. Our main contribution is to show that under
certain structural conditions and lower bounds on the sample size, there is a
form of variance-reduced $Q$-learning that achieves our local minimax lower
bound up to a logarithmic factor. These upper bounds, stated precisely in
Theorem 2, confirm that our lower bound technique has extracted a useful form
of instance dependence for estimating optimal $Q$-functions.

##### Notation:

For a positive integer $n$, we use the shorthand $[n]:\,=\\{1,2,\ldots n\\}$.
For a finite set $S$, we use $|S|$ to denote its cardinality. We use
$c_{1},c_{2},\ldots$ to denote universal constants that may change from line
to line. For any pair of vectors or matrices $(v,w)$ with matching
dimension(s), we write that $v\succeq w$ to imply $v-w$ has only positive
entries, and $v\preceq w$ is defined similarly. We let $|u|$ denote the
entrywise absolute value of a vector $u\in\mathbb{R}^{n}$ or a matrix
$u\in\mathbb{R}^{m\times n}$; we use $|u|_{+}$ to denote the entry-wise
positive part of $u$. For any vector or matrix $u$, we let $\|u\|_{\infty}$
denote the maximum absolute value taken over all entries of $u$, and
$\|u\|_{\mathrm{span}}=\max_{j}u_{j}-\min_{j}u_{j}$ denote the span seminorm.
For a continuous operator $P:\mathbb{R}^{m\times n}\to\mathbb{R}^{m\times n}$,
we define its $\ell_{\infty}$-operator norm as
$|\\!|\\!|P|\\!|\\!|_{{\infty\rightarrow\infty}}=\sup_{\|u\|_{\infty}=1}\|Pu\|_{\infty}$.
We often identify a $Q$-value function $\theta$ with its matrix representation
and use $\|\theta\|_{\infty}$ to denote the infinity norm (i.e., largest entry
in absolute terms). In the matrix representation of $\theta$, its rows and
columns are indexed via an enumeration of the states and actions,
respectively. We use the symbol $\gtrsim$ to denote a relation that holds up
to logarithmic factors in the problem parameters.

##  2 Main results

We proceed to provide precise statements of the main results of this paper,
along with a discussion of some of their consequences. In Section 2.1, we
define a notion of a local non-asymptotic minimax risk, and then state Theorem
1, which provides such a lower bound for estimating optimal $Q$-value
functions. In Section 2.2, we turn to the complementary problem of deriving
achievable results. Theorem 2 shows that under certain structural conditions
on the policies, there is a form of variance-reduced $Q$-learning that
achieves the local minimax risk up to logarithmic factors.

###  2.1 Instance-dependent lower bounds

In this section, we state a non-asymptotic lower bound for estimating optimal
$Q$-function in the $\ell_{\infty}$-norm. This lower bound, to be stated in
Theorem 1, is instance-dependent, meaning that it depends on the particular
instance of the MDP $(\mathbf{P},r)$ at hand. This dependence should be
contrasted with classical global minimax bounds, which are oblivious to such
local properties.

The starting point of our lower bound development is the two-point framework
introduced by Cai and Low [5] for local minimax bounds for nonparametric
shape-constrained inference; here we adapt it to our current setting. Focusing
on the $\ell_{\infty}$-norm error metric, the local non-asymptotic minimax
risk for $\theta(\mathcal{P})$ at an instance $\mathcal{P}=(\mathbf{P},r)$ is
defined as

$\displaystyle\mathfrak{M}_{N}(\mathcal{P}):\,=\sup_{\mathcal{P}^{\prime}}\inf_{\hat{\theta}_{N}}\max_{\mathcal{Q}\in\\{\mathcal{P},\mathcal{P}^{\prime}\\}}\sqrt{N}\cdot\mathbb{E}_{\mathcal{Q}}\left[\|\hat{\theta}_{N}-\theta(\mathcal{Q})\|_{\infty}\right].$
(7)

Here the infimum is taken over all estimators $\hat{\theta}_{N}$ that are
measurable functions of the $N$ i.i.d. observations drawn according to our
observation model (see Section 1.1).

The intuition underlying the definition (7) is that given an instance
$\mathcal{P}$, the adversary that defines the instance-dependent non-
asymptotic risk $\mathfrak{M}_{N}(\mathcal{P})$ behaves as follows: it
extracts the hardest alternative $\mathcal{P}^{\prime}$ relative to
$\mathcal{P}$, and then measures the worst-case risk over $\mathcal{P}$ and
this alternative $\mathcal{P}^{\prime}$.

####  2.1.1 Lower bounds for $Q$-function estimation

We now turn to the statement of some lower bounds for estimating the optimal
$Q$-function. Recall the definition (6) of the operator $\mathbf{P}^{\pi}$,
along with the functional $\nu(\pi;\mathbf{P},r,\gamma)$ from equation (5). We
let $\nu^{2}(\pi;\mathbf{P},r,\gamma)$ denote the matrix obtained by taking
squares entrywise. Our first step is to provide a decomposition of this matrix
into two separate components, corresponding to the noisiness in the reward
function observation and transition matrix observations, respectively.

In order to deal with the latter source of noise, with a slight abuse of
notation, we use the observed matrix Z to define a stochastic analog of
$\mathbf{P}^{\pi}$—namely, the (random) right-linear operator

$\displaystyle(\textbf{Z}^{\pi}\theta)(x,u)$
$\displaystyle:\,=\sum_{x^{\prime}\in\mathcal{X}}\textbf{Z}_{u}(x^{\prime}\mid
x)\cdot\theta(x^{\prime},\pi(x^{\prime})),\quad\text{where}\quad\textbf{Z}_{u}(x^{\prime}\mid
x):\,=\mathbbm{1}_{\textbf{Z}(x,u)=x^{\prime}}.$ (8)

By assumption, the randomness in our observations of the reward and
transitions are independent, so that for any optimal111Optimality of $\pi$ is
required so that
$\mathbf{T}(\theta^{\star})=r+\gamma\mathbf{P}^{\pi}\theta^{\star}$, with a
similar relation for the empirical Bellman operator. policy $\pi$, we have the
decomposition

$\displaystyle\nu^{2}(\pi;\mathbf{P},r)(x,u)=\gamma^{2}\rho^{2}(\pi;\mathbf{P},r)(x,u)+\sigma^{2}(\pi;\mathbf{P},r)(x,u).$
(9a) Here we define $\displaystyle\rho^{2}(\pi;\mathbf{P},r)$
$\displaystyle:\,=\operatorname{Var}\left((\mathbf{I}-\gamma\mathbf{P}^{\pi})^{-1}(\textbf{Z}^{\pi}-\mathbf{P}^{\pi})\theta^{\star}\right),\qquad\text{and}$
(9b) $\displaystyle\sigma^{2}(\pi;\mathbf{P},r)$
$\displaystyle:\,=\operatorname{Var}\left((\mathbf{I}-\gamma\mathbf{P}^{\pi})^{-1}(R-r)\right),$
(9c)

where we compute the variances in an elementwise sense.

With this notation, we have the following guarantee:

######  Theorem 1.

There exists a universal constant $c>0$ such that for any instance
$\mathcal{P}=(\mathbf{P},r)$, the local non-asymptotic minimax risk is lower
bounded as

$\displaystyle\mathfrak{M}_{N}(\mathcal{P})\geq
c\max_{\pi\in\mathbf{\Pi^{\star}}}\|\nu(\pi;\mathbf{P},r,\gamma)\|_{\infty}.$
(10a) This bound is valid for all sample sizes $N$ that satisfy the lower
bound $\displaystyle N\geq
N_{0}:\,=\max\left\\{\frac{2\gamma^{2}}{(1-\gamma)^{2}},\,\frac{2\|\theta^{\star}\|_{\mathrm{span}}^{2}}{(1-\gamma)^{2}\|\rho^{2}(\pi^{\star};\mathbf{P},r)\|_{\infty}}\right\\},$
(10b)

where
$\pi^{\star}\in\arg\max_{\pi\in\mathbf{\Pi^{\star}}}\|\nu(\pi;\mathbf{P},r)\|_{\infty}$.

We prove this theorem in Section 3. The main take-away is that the functional
$\max\limits_{\pi\in\mathbf{\Pi^{\star}}}\|\nu(\pi;\mathbf{P},r,\gamma)\|_{\infty}$
controls the local minimax risk. In order to gain intuition for this claim, it
is worth exploring the range of possible behaviors exhibited by this
functional.

####  2.1.2 Exploring the range of possible behaviors

One point of comparison is between the instance-dependent lower bound from
Theorem 2 with the existing minimax lower bounds for $Q$-learning. Azar et al.
[1] provided a global minimax lower bound on the $\ell_{\infty}$-norm error
for estimating the optimal $Q$-function. For a $\gamma$-discounted MDP, they
showed that the $\ell_{\infty}$-error of any procedure is lower bounded by the
quantity $\frac{1}{(1-\gamma)^{1.5}}\cdot\frac{1}{\sqrt{N}}$, up to
logarithmic factors in dimension.

This lower bound is optimal in a globally minimax sense, and it is worthwhile
understanding the properties of instances that exhibit this worst-case
behavior—that is, instances for which
$\max_{\pi\in\mathbf{\Pi^{\star}}}\|\nu(\pi;\mathbf{P},r,\gamma)\|_{\infty}\asymp\tfrac{1}{(1-\gamma)^{1.5}}$.
It is also worthwhile understanding the properties of problems that are much
“easier” than this worst-case theory would suggest. The following
construction, which takes inspiration from [15, 9], allows us to explore this
continuum.

######  Example 1 (A continuum of local minimax risks).

Consider an MDP with two states $\\{x_{1},x_{2}\\}$, two actions
$\\{u_{1},u_{2}\\}$, and with transition functions and reward functions given
by

$\displaystyle\mathbf{P}_{u_{1}}=\begin{bmatrix}p&1-p\\\
0&1\end{bmatrix}\quad\mathbf{P}_{u_{2}}=\begin{bmatrix}1&0\\\
0&1\end{bmatrix},\quad\mbox{and}\quad r=\begin{bmatrix}1&0\\\
\tau&0\end{bmatrix}.$ (11)

We assume that there is no randomness in the rewards. Here, the pair
$(p,\tau)$ along with the discount factor $\gamma$ are parameters of the
construction, and we consider a sub-family of these parameters indexed by a
scalar $\lambda\geq 0$. For any such $\lambda$ and discount factor
$\gamma\in(\tfrac{1}{4},1)$, consider the settings

$\displaystyle
p=\frac{4\gamma-1}{3\gamma},\quad\text{and}\quad\tau=1-(1-\gamma)^{\lambda}.$

With these choices, the optimal $Q$-function $\theta^{\star}$ takes the form

$\displaystyle\theta^{\star}=\begin{bmatrix}\frac{1}{4}\cdot\frac{3+\tau}{1-\gamma}&\frac{\gamma}{4}\cdot\frac{3+\tau}{1-\gamma}\\\
\frac{\tau}{1-\gamma}&\frac{\gamma\tau}{1-\gamma}\end{bmatrix},$

with an unique optimal policy $\pi^{\star}(x_{1})=\pi^{\star}(x_{2})=u_{1}$.
We can then compute that

$\displaystyle\max_{\pi^{\star}\in\mathbf{\Pi^{\star}}}\|\nu(\pi^{\star};\mathbf{P}_{\lambda},r_{\lambda})\|_{\infty}=c\cdot\left(\frac{1}{1-\gamma}\right)^{1.5-\lambda}.$
(12)

See Appendix A for the details of this calculation.

Substituting into equation (10a) yields that the local minimax risk is lower
bounded as $\mathfrak{M}_{N}(\mathcal{P})\geq
c\frac{1}{(1-\gamma)^{1.5-\lambda}}$. Consequently, for $\lambda>0$, our lower
bounds suggest it should be possible to estimate the optimal $Q$-function more
accurately by a factor $(1-\gamma)^{\lambda}$; note that this difference is
particularly significant for values of the discount factor $\gamma$ that are
close to one.

###  2.2 Instance-dependent upper bounds

Thus far, we have stated some instance-dependent lower bounds on the sample
complexity of estimating $Q$-value functions. As we saw in the preceding
Example 1, these lower bounds exhibit a wide range of behavior depending on
the structure of the transition functions, discount parameter and reward
functions. However, these differences in the lower bounds are only interesting
if we can show that they are optimal, meaning that there is a (hopefully
practical) algorithm that matches the behavior predicted by the lower bounds.

In this section we close this gap, in particular via a careful analysis of
variance-reduced $Q$-learning (or VR-QL for short). Variance-reduced forms of
$Q$-learning have been proposed and shown to be globally minimax in previous
work [19, 20, 26]; the version analyzed here is motivated from [26]. In
Theorem 2, we show that the VR-QL algorithm is instance-optimal up to
logarithmic factors under two different sets of assumption.

####  2.2.1 From standard to variance-reduced $Q$-learning

The classical $Q$-learning algorithm is a stochastic approximation algorithm
for estimating the unique fixed point $\theta^{\star}$ of the Bellman operator
$\mathbf{T}$. Recall the definition (4) of the empirical Bellman operator
$\widehat{\mathbf{T}}_{k}$. At each iteration $k=1,2,\ldots$, standard
$Q$-learning performs an update of the form

$\displaystyle\theta_{k+1}=(1-\alpha_{k})\theta_{k}+\alpha_{k}\widehat{\mathbf{T}}_{k}(\theta_{k}),$
(13)

where $\alpha_{k}\in(0,1)$ is a stepsize parameter. Appropriately decaying
choices of the stepsize ensure that the estimate $\theta_{k}$ converges to
$\theta^{\star}$. Unfortunately, the convergence rate is known to be non-
optimal, failing to achieve the global minimax rate [25], let alone the finer-
grained instance-dependent requirements in this paper. This non-optimality has
to do with the rate at which variance accumulates as the procedure is run.

Variance reduction is a general principle that can be applied to stochastic
approximation schemes so as to accelerate their convergence. Here we describe
the variance-reduced version of $Q$-learning that we analyze here. Similar to
standard variance-reduced schemes for stochastic optimization [see, e.g., 8],
the algorithm consists of a sequence of epochs. Within each epoch, we run a
re-centered version of the QL update. The re-centering is done in such a way,
using a Monte Carlo approximation of the population Bellman operator
$\mathbf{T}$, so that the re-centered updates have lower variance. We leave
the details of the epochs and Monte Carlo to Section 2.2.4; here let us
describe the basic form of the updates within a given epoch.

Suppose that we run the algorithm using a total of $M$ epochs. At epoch $m$,
the algorithm uses a re-centering point $\overline{\theta}_{m}$ in order to
re-center the update, where $\overline{\theta}_{m}$ acts as the current best
estimate of $\theta^{\star}$. Ideally, we should re-center the operator
$\widehat{\mathbf{T}}_{k}$ using the quantity
$\mathbf{T}(\overline{\theta}_{m})$, but we lack the access to it; instead, we
use the Monte Carlo approximation

$\displaystyle\overline{\mathbf{T}}_{N_{m}}(\overline{\theta}_{m}):\,=\frac{1}{N_{m}}\sum_{i\in\mathcal{D}_{m}}\widehat{\mathbf{T}}_{i}(\overline{\theta}_{m}).$
(14)

Given the pair
$(\overline{\theta}_{m},\overline{\mathbf{T}}_{N_{m}}(\overline{\theta}))$ and
a stepsize parameter $\alpha\in(0,1)$, we define the _variance-reduced
$Q$-learning update_ as follows:

$\displaystyle\begin{split}\theta&\mapsto\mathcal{V}_{k}\left(\theta;\alpha,\overline{\theta}_{m},\overline{\mathbf{T}}_{N_{m}}\right):\,=(1-\alpha)\theta+\alpha\left\\{\widehat{\mathbf{T}}_{k}(\theta)-\widehat{\mathbf{T}}_{k}(\overline{\theta}_{m})+\overline{\mathbf{T}}_{N_{m}}(\overline{\theta}_{m})\right\\},\end{split}$
(15)

where the operator $\widehat{\mathbf{T}}_{k}$ is independent of the set of
operators $\\{\widehat{\mathbf{T}}_{i}\\}_{i\in\mathcal{D}_{m}}$, used to
compute the Monte Carlo approximation $\overline{\mathbf{T}}_{N_{m}}$. As a
result, the stochastic operator $\widehat{\mathbf{T}}_{k}$ is independent of
the re-centering quantity
$\overline{\mathbf{T}}_{N_{m}}(\overline{\theta}_{m})$. See Section 2.2.4 for
the details on how the epoch lengths and re-centering sample sizes
$\mathcal{D}_{m}$ are chosen.

####  2.2.2 Non-asymptotic guarantees for variance-reduced $Q$-learning

In this section, we state some non-asymptotic guarantees for the VR-QL
algorithm. We provide guarantees under two conditions, both of which involve
the structure of the set of optimal policies. We begin by introducing some
definitions that underlie these two conditions.

Given an MDP instance $(\mathbf{P},r)$, we define the _optimality gap_

$\displaystyle\Delta$
$\displaystyle:\,=\min_{\pi\in\mathbf{\Pi}\setminus\mathbf{\Pi^{\star}}}\|\theta^{\star}-\\{r+\gamma\mathbf{P}^{\pi}\theta^{\star}\\}\|_{\infty},$
(16)

where $\theta^{\star},\mathbf{\Pi^{\star}}$, and $\mathbf{\Pi}$, respectively,
denote the optimal $Q$-function, the set of optimal policies, and the set of
all policies for MDP $(\mathbf{P},r)$. Observe that the scalar $\Delta$
captures the difficulty in detecting the set of optimal policies. In other
words, when $\Delta$ is small, it is hard to distinguish an optimal policy
from a suboptimal policy.

Our second set of conditions involves the family of right-linear operators
$\\{\mathbf{P}^{\pi}\;:\;\pi\in\mathbf{\Pi}\\}$ defined in equation (6). For
any $Q$-value function $\theta$, we say that a policy $\pi$ is greedy with
respect to $\theta$ if $\pi(x)\in\arg\max_{u\in\mathcal{U}}\theta(x,u)$ for
all $x\in\mathcal{X}$. Note that any policy $\pi^{\star}$ that is greedy with
respect to the optimal $Q$-value function $\theta^{\star}$ is an optimal
policy. We say that the operators satisfy a _Lipschitz condition_ if there is
a constant $L$ such that for any $Q$-value function $\theta$ and associated
greedy-optimal policy $\pi$, we have

$\displaystyle\|(\mathbf{P}^{\pi}-\mathbf{P}^{\pi^{\star}})\;(\theta-\theta^{\star})\|_{\infty}\leq
L\|\theta-\theta^{\star}\|_{\infty}^{2}.$ (17)

Intuitively, this condition means that the operator difference
$\mathbf{P}^{\pi}-\mathbf{P}^{\pi^{\star}}$ is small whenever the underlying
$Q$-value functions that induce the policies are close. Conditions of this
type were introduced by Puterman and Brumelle [13] in their classical analysis
of the convergence rates of policy iteration algorithms for exact dynamic
programming.

With these definitions in place, we can specify the two settings under which
we provide upper bounds on the VR-QL algorithm:

Setting UNQ:

There is a unique optimal policy $\pi^{\star}$, and the sample size $N$ is
lower bounded as

$\displaystyle\frac{N}{(\log N)^{2}}\geq
c_{2}\log(D/\delta)\cdot\frac{(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{2}}{(1-\gamma)^{3}}\cdot\max\\{1,\,\frac{1}{\Delta^{2}(1-\gamma)^{\beta}}\\}\quad\text{for
some}\;\;\beta>0.$ (18)

Setting LIP:

The Lipschitz condition (17) condition holds, and the sample size is lower
bounded as

$\displaystyle\frac{N}{(\log N)^{2}}\geq
c_{2}\log(D/\delta)\frac{(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{2}}{(1-\gamma)^{3+\beta}}\cdot\min\\{\frac{L^{2}}{(1-\gamma)^{2}},\,\frac{1}{\Delta^{2}}\\}\qquad\mbox{for
some $\beta>0$.}$ (19)

In all cases, we assume that we are given an initial point
$\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}$ such that

$\displaystyle\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}-\theta^{\star}\|_{\infty}\leq\frac{\|r\|_{\infty}}{\sqrt{1-\gamma}}.$
(20)

Such an initial condition has already been used in the literature [26], and it
can be ensured by first running Algorithm VR-QL for a total of
$\frac{1}{(1-\gamma)^{3}}$ samples (up to logarithmic factor corrections).

######  Theorem 2.

Under either settings (UNQ) or (LIP), there are choices of epoch parameters
such that given any discount parameter $\gamma\in[\frac{1}{2},1)$ and an
initial point $\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}$ satisfying the
initialization condition (20), Algorithm VR-QL run for
$M:\,=\log_{4}\left(\frac{N(1-\gamma)^{2}}{8\log((16D/\delta)\cdot\log
N)}\right)$ epochs yields an estimate $\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{M+1}$ such that

$\displaystyle\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{M+1}-\theta^{\star}\|_{\infty}$
$\displaystyle\leq
c_{0}\cdot\sqrt{\frac{\log_{4}(8DM/\delta)}{N}}\max_{\pi^{\star}\in\mathbf{\Pi^{\star}}}\|\nu(\pi^{\star};\mathbf{P},r,\gamma)\|_{\infty}+c_{1}\cdot\frac{\log_{4}(8DM/\delta)}{N}\cdot\frac{\|\theta^{\star}\|_{\mathrm{span}}}{1-\gamma},$
(21)

with probability exceeding $1-\delta$.

See Section 4 for the proof of this claim.

##### Comparing the upper and lower bounds:

Assuming the sample size lower bound from Theorem 1 are valid, we see that the
second term in the bound (21) is of smaller order. In this case, the upper
bound from Theorem 2 and the lower bound from Theorem 1 matches, and we
conclude that the VR-QL algorithm is _instance optimal_.

Although the guarantee (21) involves the same $1/\sqrt{N}$ rate and complexity
term
$\max_{\pi^{\star}\in\mathbf{\Pi^{\star}}}\|\nu(\pi^{\star};\mathbf{P},r,\gamma)\|_{\infty}$
as the lower bound in Theorem 1, it should be noted that the sample size lower
bounds required for Theorem 2 are more stringent than that in Theorem 1.
Moreover, our lower bound does not require the side conditions—either the
unique optima or Lipschitz conditions—that are imposed in Theorem 2. Closing
these remaining differences between the two results is a worthwhile goal for
future work.

####  2.2.3 Confirming the theoretical predictions

Some numerical experiments are helpful in order to illustrate instance-
adaptive behavior guaranteed by Theorem 2. Recall the family of MDPs (11) from
Example 1. Suppose that we set $\lambda=0.5$ and for each choice of
$\gamma\in(1/2,1)$, we collect $N=\lceil\frac{16\cdot
32}{9}\frac{1}{(1-\gamma)^{3}\cdot}\rceil$ samples, and then run the VR-QL
algorithm over a range of discount parameters $\gamma$, using the settings
from Theorem 2 and Section 2.2.4, thereby obtaining an estimate
$\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{M+1}$.

Figure 1(a) plots the evolution of log $\ell_{\infty}$-norm error of the
estimate over time as the algorithm proceeds; the form of these curves show
the epoch-based nature of the convergence. See Section 2.2.4 for more details
on the parameters of the epochs, including the base parameter illustrated
here. Plotted as blue circles in panel (b) of Figure 1 are the logarithm of
the $\ell_{\infty}$-norm error of the final output; that is,
$\log\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{M+1}-\theta^{\star}\|_{\infty}$,
versus the logarithm of the discount complexity, $\log(1/(1-\gamma))$. Each
point in this plot represents an average over 1000 trials.

In terms of theory, with the settings given above, existing worst-case bounds
[1, 26] predict that the log $\ell_{\infty}$-norm error remains constant as
the log discount complexity grows; accordingly, we have plotted a dotted red
line with slope zero to illustrate the worst-case guarantee. On the other
hand, for the MDP instance (11) with $\lambda=0.5$, a simple calculation
yields that for the instance (11) the suboptimality gap $\Delta$ satisfies
${\Delta=1-\frac{(1-\gamma)^{\lambda}}{4}\geq\frac{3}{4}}$. In our experiment,
we set the sample size to be
$N=\lceil\frac{32}{(1-\gamma)^{3}}\cdot\frac{4^{2}}{3^{2}}\rceil\geq\frac{32}{(1-\gamma)^{3}\cdot\Delta^{2}}$;
as a result, the bounds from Theorems 1 and 2 are valid.

|  |
---|---|---
(a) |  | (b)
Figure 1: (a) $\lambda=0.5,\quad
N=\lceil\frac{32}{(1-\gamma)^{3}\cdot}\cdot\frac{4^{2}}{3^{2}}\rceil$
$\gamma=0.9$. Illustration of the qualitative behavior of Algorithm VR-QL
applied on the MDP (1) along with instance dependent and the worst case
bounds. The figure plots the $\log$ $\ell_{\infty}$-error
$\|\bar{\theta}_{M+1}-\theta^{\star}\|_{\infty}$ against the log discount
complexity factor $\log(\frac{1}{1-\gamma})$ with $\lambda=0.5$. We have also
plotted the least-squares fit through these points, and the instance-dependent
lower bound from Theorem 1, the instance-dependent upper bound from Theorem 2,
and the worst-case bound [26]. (b) Behavior of the VR-QL algorithm with
different choices of the base $b$. The plot demonstrates that different
choices of the base $b$ yield similar behavior.

With the setting $\lambda=0.5$, our calculations from Example 1 yield

$\displaystyle\max_{\pi^{\star}\in\mathbf{\Pi^{\star}}}\|\nu(\pi^{\star};\mathbf{P},r,\gamma)\|_{\infty}$
$\displaystyle\asymp\Big{(}\tfrac{1}{1-\gamma}\Big{)}^{-0.5}.$

Thus, with the choice of sample size $N$ given above, our theory predicts that
the log $\ell_{\infty}$-norm error should exhibit the scaling

$\displaystyle\log\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{M+1}-\theta^{\star}\|_{\infty}\asymp\log\left(\frac{1}{\sqrt{N}}\max_{\pi^{\star}\in\mathbf{\Pi^{\star}}}\|\nu(\pi^{\star};\mathbf{P},r,\gamma)\|_{\infty}\right)\;\asymp\;c-0.5\log\big{(}\tfrac{1}{1-\gamma}\big{)},$

where $c$ is a constant. In Figure 1(b), we plot the lower bound from Theorem
1 as a solid red line, and the upper bound from Theorem 2 as a dashed green
line. (While these lines both have slope $-0.50$, the intercept term $c$ is
different due to the additional logarithmic factors in dimension present in
the upper bound.)

In order to test how the empirical behavior conforms to the theoretical
prediction, we did an ordinary least-squares fit of the log
$\ell_{\infty}$-norm error versus the log discount complexity; this fit yields
a line with slope $\widehat{\beta}=-0.45$, and is plotted in solid blue. This
test shows good agreement between the theoretical prediction and the practical
behavior.

####  2.2.4 Details of the epochs and procedure

In this section, we provide the complete details of the algorithm used in our
version of variance-reduced $Q$-learning.

##### A single epoch:

A single epoch of the overall variance-reduced QL algorithm involves repeated
applications of the basic variance-reduced update $\mathcal{V}_{k}$ from
equation (15). The epochs are indexed with integers $m=1,2,\ldots,M$, where
$M$ corresponds to the total number of epochs to be run. Each epoch $m$
requires the following four inputs:

  * •

an element $\overline{\theta}$, which is chosen to be the output of the
previous epoch $m-1$;

  * •

a positive integer $K$ denoting the number of steps within the given epoch;

  * •

a positive integer $N_{m}$ denoting the batch size used to calculate the Monte
Carlo update (14);

  * •

a set of fresh operators
$\\{\widehat{\mathbf{T}}_{i}\\}_{i\in\mathcal{C}_{m}}$, with
$|\mathcal{C}_{m}|=N_{m}+K$. The set $\mathcal{C}_{m}$ is partitioned into two
subsets having sizes $N_{m}$ and $K$, respectively. The first subset, of size
$N_{m}$, which we call $\mathcal{D}_{m}$, is used to construct the Monte Carlo
approximation (14). The second subset, of size $K$ is used to run the $K$
steps within the epoch.

We summarize a single epoch in pseudocode form in Algorithm SingleEpoch.

Algorithm SingleEpoch RunEpoch
$(\overline{\theta};K,N_{m},\\{\widehat{\mathbf{T}}_{i}\\}_{i\in\mathcal{C}_{m}})$

1: Given (a) Epoch length $K$, (b) Re-centering vector $\overline{\theta}$,
(c) Re-centering batch size $N_{m}$, (d) Operators
$\\{\widehat{\mathbf{T}}_{i}\\}_{i\in\mathcal{C}_{m}}$

2: Compute the re-centering quantity
$\displaystyle\overline{\mathbf{T}}_{N_{m}}(\overline{\theta}):\,=\frac{1}{N_{m}}\sum\limits_{i\in\mathcal{D}_{m}}\widehat{\mathbf{T}}_{i}(\overline{\theta})$

3: Initialize $\theta_{1}=\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}$

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

5: Compute the variance-reduced update:  $\displaystyle\theta_{k+1}$
$\displaystyle=\mathcal{V}_{k}(\theta_{k};\alpha_{k},\overline{\theta},\overline{\mathbf{T}}_{N_{m}})\quad\text{with
stepsize }\,\alpha_{k}=\frac{1}{1+(1-\gamma)k}.$

6: end for

7: return $\theta_{K+1}$

##### Overall algorithm:

The overall algorithm, denoted by VR-QL for short, has five inputs: (a) an
initialization $\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}$, (b) an integer
$M$, denoting the number of epochs to be run, (c) an integer $K$, denoting the
length of each epoch, (d) a sequence of batch sizes $\\{N_{m}\\}_{m=1}^{K}$,
denoting the number of operators used for re-centering in the $M$ epochs, and
(e) sample batches
$\\{\\{\widehat{\mathbf{T}}_{i}\\}_{i\in\mathcal{C}_{m}}\\}_{m=1}^{M}$ to be
used in the $M$ epochs. Given these five inputs, the overall procedure can be
summarized as in Algorithm VR-QL.

Algorithm VR-QL

1: Given (a) Initialization $\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}$, (b) Number of
epochs, $M$, (c) Epoch length $K$, (d) Re-centering sample sizes
$\\{N_{m}\\}_{m=1}^{M}$, (e) Sample batches
$\\{\widehat{\mathbf{T}}_{i}\\}_{i\in\mathcal{C}_{m}}$ for $m=1,\ldots,M$

2: Initialize at $\overline{\theta}_{1}$

3: for $m=1,2,\ldots,M$ do

4:
$\overline{\theta}_{m+1}=\text{RunEpoch}(\overline{\theta}_{m};K,N_{m},\\{\widehat{\mathbf{T}}_{i}\\}_{i\in\mathcal{C}_{m}})$

5: end for

6: return $\overline{\theta}_{M+1}$ as final estimate

##### Settings for Theorem 2:

Given a tolerance probability $\delta\in(0,1)$ and the number of available
i.i.d. samples $N$, we run Algorithm VR-QL with a total of
$M:\,=\log_{4}\left(\frac{N(1-\gamma)^{2}}{8\log((16D/\delta)\cdot\log
N)}\right)$ epochs, along with the following parameter choices:

Re-centering sizes:
$\displaystyle\begin{split}N_{m}=c_{1}\frac{4^{m}}{(1-\gamma)^{2}}\cdot\log_{4}(16MD/\delta)\end{split}$
(22a) Sample batches: $\displaystyle\begin{split}&\text{Partition the $N$
samples to obtain $\\{\widehat{\mathbf{T}}_{i}\\}_{i\in\mathcal{C}_{m}}$ for
$m=1,\ldots,M$}\end{split}$ (22b) Epoch length: $\displaystyle
K=\frac{N}{2M}.$ (22c)

##  3 Proof of Theorem 1

Given an MDP instance $\mathcal{P}=(\mathbf{P},r)$, we start by introducing
the following two classes of alternative MDPs:

$\displaystyle\mathcal{S}_{1}=\\{\mathcal{P}^{\prime}=(\mathbf{P}^{\prime},r^{\prime})\mid
r^{\prime}=r\\},\quad\text{and}\quad\mathcal{S}_{2}=\\{\mathcal{P}^{\prime}=(\mathbf{P}^{\prime},r^{\prime})\mid\mathbf{P}^{\prime}=\mathbf{P}\\}.$
(23)

We consider the restricted version of the local minimax risk at the instance
$\mathcal{P}^{\prime}$ to the classes $\mathcal{S}_{i}$:

$\displaystyle\mathfrak{M}_{N}(\mathcal{P};\mathcal{S}_{i}):\,=\sup_{\mathcal{P}^{\prime}\in\mathcal{S}_{i}}\inf_{\hat{\theta}_{N}}\max_{\mathcal{Q}\in\\{\mathcal{P},\mathcal{P}^{\prime}\\}}\mathbb{E}_{\mathcal{P}}[\sqrt{N}\|\hat{\theta}_{N}-\theta(\mathcal{Q})\|_{\infty}],\quad
i=1,2.$ (24)

The main part of the proof involves showing that there exists a universal
constant $c>0$ such that

$\displaystyle\mathfrak{M}_{N}(\mathcal{P};\mathcal{S}_{1})$
$\displaystyle\geq
c\cdot\max_{\pi\in\mathbf{\Pi^{\star}}}\|\gamma\rho(\pi;\mathbf{P},r)\|_{\infty},\quad\text{and}$
(25a) $\displaystyle\mathfrak{M}_{N}(\mathcal{P};\mathcal{S}_{2})$
$\displaystyle\geq
c\cdot\max_{\pi\in\mathbf{\Pi^{\star}}}\|\sigma(\pi;\mathbf{P},r)\|_{\infty},$
(25b)

where $\mathbf{\Pi^{\star}}$ denotes the optimal policy set for
$(\mathbf{P},r)$. We can then conclude

$\displaystyle\begin{split}\mathfrak{M}_{N}(\mathcal{P})&\geq\max\\{\mathfrak{M}_{N}(\mathcal{P};\mathcal{S}_{1}),\mathfrak{M}_{N}(\mathcal{P};\mathcal{S}_{2})\\}\\\
&\geq\frac{1}{2}\left(\mathfrak{M}_{N}(\mathcal{P};\mathcal{S}_{1})+\mathfrak{M}_{N}(\mathcal{P};\mathcal{S}_{2})\right)\\\
&\geq\frac{c}{2}\max_{\pi\in\mathbf{\Pi^{\star}}}\|\gamma\rho(\pi;\mathbf{P},r)\|_{\infty}+\frac{c}{2}\max_{\pi\in\mathbf{\Pi^{\star}}}\|\sigma(\pi;\mathbf{P},r)\|_{\infty}\\\
&\geq\frac{c}{2}\max_{\pi\in\mathbf{\Pi^{\star}}}\|\nu(\pi;\mathbf{P},r)\|_{\infty}.\end{split}$

The last inequality above follows from the decomposition (9a). It remains to
prove the claims (25a) and (25b). More precisely, the core of our proof
involves proving the following two lemmas:

######  Lemma 1.

For all $\mathcal{S}\in\\{\mathcal{S}_{1},\mathcal{S}_{2}\\}$, we have that
$\mathfrak{M}_{N}(\mathcal{P};\mathcal{S})\geq\frac{1}{8}\underline{\mathfrak{M}}_{N}(\mathcal{P};\mathcal{S})$
where we define

$\displaystyle\underline{\mathfrak{M}}_{N}(\mathcal{P};\mathcal{S}):\,=\sup_{\mathcal{P}^{\prime}\in\mathcal{S}}\left\\{\sqrt{N}\cdot\|\theta(\mathcal{P})-\theta(\mathcal{P}^{\prime})\|_{\infty}\mid
d_{\text{Hel}}\left(\mathcal{P},\mathcal{P}^{\prime}\right)\leq\frac{1}{2\sqrt{N}}\right\\}.$

This lemma follows as a fairly straightforward consequence of the standard
reduction from estimation to testing; see Appendix B.1 for the details.

Our next lemma requires more effort to prove, and leverages the specific
structure of the problem at hand:

######  Lemma 2.

Given any MDP instance $\mathcal{P}=(\mathbf{P},r)$:

  * (a)

There exists an instance
$\mathcal{P}_{1}=(\mathbf{P}^{\prime},r)\in\mathcal{S}_{1}$ such that
$d_{\text{Hel}}\left(\mathcal{P},\mathcal{P}_{1}\right)\leq\frac{1}{2\sqrt{N}}$
and

$\displaystyle\sqrt{N}\cdot\|\theta(\mathcal{P})-\theta(\mathcal{P}_{1})\|_{\infty}\geq
c\cdot\max_{\pi\in\mathbf{\Pi^{\star}}}\|\gamma\rho(\pi;\mathbf{P},r)\|_{\infty}.$

  * (b)

There exists an instance
$\mathcal{P}_{2}=(\mathbf{P},r^{\prime})\in\mathcal{S}_{2}$ such that
$d_{\text{Hel}}\left(\mathcal{P},\mathcal{P}_{2}\right)\leq\frac{1}{2\sqrt{N}}$
and

$\displaystyle\sqrt{N}\cdot\|\theta(\mathcal{P})-\theta(\mathcal{P}_{2})\|_{\infty}\geq
c\cdot\max_{\pi\in\mathbf{\Pi^{\star}}}\|\sigma(\pi;\mathbf{P},r)\|_{\infty}.$

Note that the bounds (25a)–(25b) stated in Theorem 1 follow by combining the
claims of Lemmas 1 and 2. The remainder of our proof focuses on establishing
Lemma 2.

###  3.1 Proof of Lemma 2

In this section, we prove the two parts of Lemma 2.

####  3.1.1 Proof of Lemma 2(a)

Throughout the proof, we use $z$ to denote a generic element of the state-
action set $\mathcal{X}\times\mathcal{U}$. Let $\theta$ be the true
$Q$-function for the MDP $\mathcal{P}=(\mathbf{P},r)$. We adopt the shorthands

$\displaystyle{\pi_{1}}\in\arg\max_{\pi\in\mathbf{\Pi^{\star}}}\|\rho(\pi;\mathbf{P},r)\|_{\infty},\quad\bar{z}\in\arg\max_{z\in\mathcal{X}\times\mathcal{U}}\rho({\pi_{1}};\mathbf{P},r),\quad\tilde{\rho}(z):\,=\rho({\pi_{1}};\mathbf{P},r)(z),$
(26a)
$\displaystyle\mathbf{U}:\,=(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}\quad\text{and}\quad\varphi^{2}(z):\,=\text{Var}\left(\textbf{Z}^{\pi_{1}}\theta(z)\right).$
(26b)

To explain this notation, we chose ${\pi_{1}}$ to be the optimal policy that
achieves the largest $\ell_{\infty}$-norm across $\rho(\pi^{*};\mathbf{P},r)$
for optimal policies $\pi^{*}$, we let $\bar{z}$ is the state-action pair
index that achieves the maximal entry of $\rho({\pi_{1}};\mathbf{P},r)$, and
we use $\tilde{\rho}$ as convenient shorthand to refer to the values of
$\rho({\pi_{1}};\mathbf{P},r)$. This choice of notation implies that

$\displaystyle\tilde{\rho}(\bar{z})=\max_{\pi\in\mathbf{\Pi^{\star}}}\|\rho(\pi;\mathbf{P},r)\|_{\infty}.$

Additionally, note that $\mathbf{U}$ is a linear transformation from
$\mathbb{R}^{|\mathcal{X}|\times|\mathcal{U}|}$ to itself, so we can express
the action of $\mathbf{U}$ on $\theta$ as

$\displaystyle(\mathbf{U}\theta)(z)=\sum_{z^{\prime}\in\mathcal{X}\times\mathcal{U}}\mathbf{U}_{z,z^{\prime}}\theta(z^{\prime}).$

Note moreover that

$\displaystyle\varphi^{2}(z)=\sum_{x^{\prime}}\mathbf{P}_{x^{\prime},z}(\theta(x^{\prime},{\pi_{1}}(x^{\prime}))-(\mathbf{P}^{\pi_{1}}\theta)(z))^{2}\quad\text{and}\quad\tilde{\rho}^{2}(z)=\sum_{z^{\prime}}(\mathbf{U}_{z,z^{\prime}})^{2}\varphi^{2}(z^{\prime}).$
(27)

With these definitions, we now define $\bar{\mathbf{P}}_{y,z}$ as follows (we
will prove that this choice is a valid probability transition kernel shortly):

$\displaystyle\bar{\mathbf{P}}_{y,z}=\mathbf{P}_{y,z}+\frac{1}{\tilde{\rho}(\bar{z})\sqrt{2N}}\mathbf{P}_{y,z}\mathbf{U}_{\bar{z},z}\cdot(\theta(y,{\pi_{1}}(y))-(\mathbf{P}^{\pi_{1}}\theta)(z)).$
(28)

Here, we have used the shorthand $\mathbf{P}_{y,z}\equiv\mathbf{P}_{u}(y\mid
x)$, where $z=(x,u)\in\mathcal{X}\times\mathcal{U}$. Let
$\theta:\,=\theta(\mathbf{P},r)$, and
$\bar{\theta}:\,=\theta(\bar{\mathbf{P}},r)$ be the optimal $Q$ functions for
MDP instances $(\mathbf{P},r)$ and $(\bar{\mathbf{P}},r)$ respectively. In the
rest of the proof, we use the following properties of $\bar{\mathbf{P}}$.

######  Lemma 3.

For any MDP $\mathcal{P}=(\mathbf{P},r)$ and the optimal policy ${\pi_{1}}$
defined in equation (26), the corresponding $\bar{\mathbf{P}}$ has the
following properties:

  * (a)

The $\bar{\mathbf{P}}$ is a probability transition kernel.

  * (b)

The MDP instances $\mathcal{P}=(\mathbf{P},r)$ and
$\mathcal{P}_{1}=(\bar{\mathbf{P}},r)$ satisfy
$d_{\text{Hel}}\left(\mathcal{P},\mathcal{P}_{1}\right)\leq\frac{1}{2\sqrt{N}}$
and
${|\\!|\\!|\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}}|\\!|\\!|_{{\infty\rightarrow\infty}}\leq\frac{1}{\sqrt{2N}}}$.

  * (c)

Each entry of
$(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}[\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}}]\theta$
is non-negative.

See Appendix B.2 for a proof of this lemma.

Equipped with these tools, we are now ready to lower bound the norm
$\|\theta-\bar{\theta}\|_{\infty}$. The optimal $Q$-functions $\theta$ and
$\bar{\theta}$ satisfy the following Bellman equations:

$\displaystyle\theta=r+\gamma\mathbf{P}^{\pi_{1}}\theta\qquad\text{and}\qquad\bar{\theta}=r+\gamma\bar{\mathbf{P}}^{\bar{\pi}}\bar{\theta},$
(29)

where ${\pi_{1}}\in\mathbf{\Pi^{\star}}$ is the optimal policy that achieves
$\max_{\pi\in\mathbf{\Pi^{\star}}}\|\rho(\pi;\mathbf{P},r)\|_{\infty}$, and
$\bar{\pi}$ is an optimal policy for $(\bar{\mathbf{P}},r)$. By the optimality
of policy $\bar{\pi}$ and the $Q$-function $\bar{\theta}$, we have the
entrywise inequality
$\bar{\mathbf{P}}^{\bar{\pi}}\bar{\theta}\succeq\bar{\mathbf{P}}^{\pi_{1}}\bar{\theta}$,
which implies
$(\mathbf{I}-\gamma\bar{\mathbf{P}}^{\pi_{1}})\bar{\theta}\succeq(\mathbf{I}-\gamma\bar{\mathbf{P}}^{\bar{\pi}})\bar{\theta}=r$.
Thus, using the identity
$A_{1}^{-1}-A_{0}^{-1}=A_{1}^{-1}(A_{0}-A_{1})A_{0}^{-1}$ for invertible
operators $A_{0}$ and $A_{1}$, we have

$\displaystyle\begin{split}\bar{\theta}-\theta&\succeq\left[(\mathbf{I}-\gamma\bar{\mathbf{P}}^{\pi_{1}})^{-1}-(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}\right]r\\\
&=(\mathbf{I}-\gamma\bar{\mathbf{P}}^{\pi_{1}})^{-1}\left[(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})-(\mathbf{I}-\gamma\bar{\mathbf{P}}^{\pi_{1}})\right](\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}r\\\
&=\gamma(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}\left[\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}}\right](\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}r\\\
&\quad+\gamma\left((\mathbf{I}-\gamma\bar{\mathbf{P}}^{\pi_{1}})^{-1}-(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}\right)(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}r\\\
&=\gamma(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}\left[\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}}\right]\theta\\\
&\quad+\gamma\left((\mathbf{I}-\gamma\bar{\mathbf{P}}^{\pi_{1}})^{-1}-(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}\right)(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta,\end{split}$

where the final equation follows from the Bellman optimality condition (29).
Lemma 3(c) guarantees that the entries of
$(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}[\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}}]\theta$
are non-negative, and therefore we conclude

$\displaystyle\|\bar{\theta}-\theta\|_{\infty}\geq\gamma\|(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}[\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}}]\theta\|_{\infty}-\gamma\|((\mathbf{I}-\gamma\bar{\mathbf{P}}^{\pi_{1}})^{-1}-(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1})(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta\|_{\infty}.$
(30)

Consider the second term
$T_{2}:\,=\|(\mathbf{I}-\gamma\bar{\mathbf{P}}^{\pi_{1}})^{-1}-(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1})(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta\|_{\infty}$.
We have

$\displaystyle T_{2}$
$\displaystyle=\|[(\mathbf{I}-\gamma\bar{\mathbf{P}}^{\pi_{1}})^{-1}(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})-\mathbf{I}](\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta\|_{\infty}$
$\displaystyle\leq|\\!|\\!|(\mathbf{I}-\gamma\bar{\mathbf{P}}^{\pi_{1}})^{-1}(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})-\mathbf{I}|\\!|\\!|_{{\infty\rightarrow\infty}}\cdot\|(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta\|_{\infty}$
$\displaystyle=\gamma|\\!|\\!|(\mathbf{I}-\gamma\bar{\mathbf{P}}^{\pi_{1}})^{-1}(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})|\\!|\\!|_{{\infty\rightarrow\infty}}\cdot\|(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta\|_{\infty}$
$\displaystyle\leq\frac{\gamma}{1-\gamma}|\\!|\\!|\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}}|\\!|\\!|_{{\infty\rightarrow\infty}}\cdot\|(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta\|_{\infty}$
$\displaystyle\leq\frac{\gamma}{2}\|(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta\|_{\infty},$

where the last inequality uses Lemma 3(b) and the first part of the minimum
sample size assumption (10b). Combining this result with the bound (30) we
conclude

$\displaystyle\|\bar{\theta}-\theta\|_{\infty}\geq\frac{\gamma}{2}\|(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta\|_{\infty}.$

With this result in hand, substituting the value of the transition kernel
$\bar{\mathbf{P}}$ from equation (28) and recalling the definition of state-
action pair $z$ from equation (26) we have

$\displaystyle\sqrt{N}\cdot\|\bar{\theta}-\theta\|_{\infty}\geq\frac{\gamma\sqrt{N}}{2}\cdot(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta(\bar{z})$
$\displaystyle=\frac{\gamma\sqrt{N}}{2\sqrt{2}}\cdot\sum_{z}\mathbf{U}_{\bar{z},z}\cdot(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta(z)$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\geq}}\frac{\gamma}{4\tilde{\rho}(\bar{z})}\sum_{z}(\mathbf{U}_{\bar{z},z})^{2}\varphi^{2}(z)$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{=}}\frac{\gamma\tilde{\rho}(\bar{z})}{4}=\frac{1}{4}\cdot\max_{\pi\in\mathbf{\Pi^{\star}}}\|\gamma\rho(\pi;\mathbf{P},r)\|_{\infty},$

where step (i) follows by substituting the value of the transition kernel
$\bar{\mathbf{P}}$ (cf. Proof of Lemma 3 part (c)), and step (ii) follows by
using the expression (27). This completes the proof of part (a) of Lemma 2.

####  3.1.2 Proof of Lemma 2(b)

Borrowing the notation from part (a) of the proof, let $z$ denote a generic
element of the state-action set $\mathcal{X}\times\mathcal{U}$. Let
${\pi_{2}}\in\arg\max_{\pi\in\mathbf{\Pi^{\star}}}\|\sigma(\pi;\mathbf{P},r)\|_{\infty}$.
We use the shorthands

$\displaystyle\sigma^{2}(\bar{z}):\,=\max_{\pi\in\mathbf{\Pi^{\star}}}\|\sigma(\pi;\mathbf{P},r)\|_{\infty}^{2}=\|\sigma({\pi_{2}};\mathbf{P},r)\|_{\infty}^{2},\qquad\text{and}\quad\mathbf{U}:\,=(\mathbf{I}-\gamma\mathbf{P}^{\pi_{2}})^{-1}.$
(31)

We define our perturbed reward function to be

$\displaystyle\bar{r}(z)=r(z)+\frac{1}{\sigma(\bar{z})\sqrt{2N}}\mathbf{U}_{\bar{z},z}\sigma_{r}^{2}\quad\text{for}\quad
z\in\mathcal{X}\times\mathcal{U}.$ (32)

For $\mathcal{P}_{2}:\,=(\mathbf{P},\bar{r})$, a short computation shows that
the Hellinger distance between the components of the instance pair
$(\mathcal{P},\mathcal{P}_{2})$ takes the form

$\displaystyle d_{\text{Hel}}\left(\mathcal{P},\mathcal{P}_{2}\right)^{2}\leq
D_{KL}(\mathcal{N}(r,\sigma_{r}^{2}\mathbf{I})\mid\mathcal{N}(\bar{r},\sigma_{r}^{2}\mathbf{I}))=\frac{1}{2\sigma_{r}^{2}}\|r-\bar{r}\|_{2}^{2}.$

Substituting the value of the reward $\bar{r}$ from equation (32) yields

$\displaystyle
d_{\text{Hel}}\left(\mathcal{P},\mathcal{P}_{2}\right)^{2}\leq\frac{1}{2\sigma_{r}^{2}}\|\bar{r}-r\|_{2}^{2}=\frac{1}{\sigma^{2}(\bar{z})\cdot
4N}\sum_{z}(\mathbf{U}_{\bar{z},z})^{2}\sigma_{r}^{2}=\frac{1}{4N},$

where the last equality uses the definition of the term $\sigma^{2}(\bar{z})$,
i.e.,

$\displaystyle\sigma^{2}(\bar{z})=\sum_{z^{\prime}}(\mathbf{U}_{\bar{z},z^{\prime}})^{2}\sigma_{r}^{2}.$
(33)

It remains to prove a lower bound on the $\ell_{\infty}$-norm between the
optimal $Q$-functions for instances $\mathcal{P}$ and $\mathcal{P}_{2}$.

Let $\theta:\,=\theta(\mathbf{P},r)$, and
$\bar{\theta}:\,=\theta(\mathbf{P},\bar{r})$ be the optimal $Q$ functions for
MDP instances $\mathcal{P}:\,=(\mathbf{P},r)$ and
$\mathcal{P}_{2}:\,=(\mathbf{P},\bar{r})$, respectively. Note that $\theta$
and $\bar{\theta}$ satisfy the Bellman equations

$\displaystyle\theta=r+\gamma\mathbf{P}^{\pi_{2}}\theta,\quad\mbox{and}\quad\bar{\theta}=\bar{r}+\gamma\mathbf{P}^{\bar{\pi}}\bar{\theta},$
(34)

where $\bar{\pi}$ is an optimal policy for the MDP instance
$(\mathbf{P},\bar{r})$. By the optimality of policy $\bar{\pi}$, we have the
entrywise inequality
$\mathbf{P}^{\bar{\pi}}\bar{\theta}\succeq\mathbf{P}^{\pi_{2}}\bar{\theta}$;
as a result, we have

$\displaystyle(\mathbf{I}-\gamma\mathbf{P}^{\pi_{2}})\bar{\theta}\succeq\bar{r}\implies\bar{\theta}\succeq(\mathbf{I}-\gamma\mathbf{P}^{\pi_{2}})^{-1}\bar{r},$

where the last step uses the fact that
$(\mathbf{I}-\gamma\mathbf{P}^{\pi_{2}})^{-1}$ is entry-wise non-negative.
Combining the last inequality with the Bellman equation (34) we have that

$\displaystyle\bar{\theta}-\theta\succeq(\mathbf{I}-\gamma\mathbf{P}^{\pi_{2}})^{-1}(\bar{r}-r)$
(35)

and that

$\displaystyle\|(\mathbf{I}-\gamma\mathbf{P}^{\pi_{2}})^{-1}(\bar{r}-r)\|_{\infty}\geq(\mathbf{I}-\gamma\mathbf{P}^{\pi_{2}})^{-1}(\bar{r}-r)(\bar{z})$
$\displaystyle=\frac{1}{\sigma(\bar{z})\sqrt{2N}}\sum_{z}(\mathbf{U}_{\bar{z},z})^{2}\sigma_{r}^{2}$
$\displaystyle=\frac{\sigma(\bar{z})}{\sqrt{2N}},$

where the last equality uses the relation (33). Putting together the pieces,
we have shown that

$\displaystyle\|\bar{\theta}-\theta\|_{\infty}\geq\frac{\sigma(\bar{z})}{\sqrt{2N}}=\frac{1}{\sqrt{2N}}\cdot\max_{\pi\in\mathbf{\Pi^{\star}}}\|\sigma(\pi;\mathbf{P},r)\|_{\infty},$

as desired.

##  4 Proof of Theorem 2

In the section, we provide a proof of the upper bounds stated in Theorem 2.
Throughout the proof, we adopt the following shorthands

$\displaystyle\kappa=\frac{\|\theta^{\star}\|_{\mathrm{span}}}{(1-\gamma)}\cdot\log(8DM/\delta),\qquad\tau^{*}=\max_{\pi^{\star}\in\mathbf{\Pi^{\star}}}\|\nu(\pi^{\star};\mathbf{P},r)\|_{\infty}\cdot\sqrt{\log(8DM/\delta)},$
$\displaystyle\qquad\text{and}\qquad\tau_{\max}=\frac{1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma}}{(1-\gamma)^{1.5}}\cdot\sqrt{\log(8DM/\delta)}.$
(36)

###  4.1 Proof of Theorem 2(a)

Our proof is based on the following two lemmas characterizing the behavior of
VR-QL across epochs.

######  Lemma 4.

Under the assumptions of Theorem 2, for each epoch $m=1,\ldots,M$, we have

$\displaystyle\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m+1}-\theta^{\star}\|_{\infty}\leq\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}}{16}+c\left(\frac{\tau_{\max}}{\sqrt{N_{m}}}+\frac{\kappa}{N_{m}}\right),$
(37)

with probability at least $1-\frac{\delta}{M}$.

Lemma 4 follows by an argument similar to that used in the proof of Theorem 1
of the paper [26], so we omit the details here. See also the proof of Lemma 5
for some relevant arguments.

######  Lemma 5.

Under the assumptions of Theorem 2, for epochs $m$ such that the re-centering
sample size $N_{m}$ satisfies the bound
$N_{m}\geq\log_{4}(8DM/\delta)\frac{(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{2}}{\Delta^{2}(1-\gamma)^{3}}$,
we have

$\displaystyle\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m+1}-\theta^{\star}\|_{\infty}\leq\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}}{16}+c\cdot\left(\frac{\tau^{*}}{\sqrt{N_{m}}}+\frac{\kappa}{N_{m}}\right),$
(38)

with probability at least $1-\frac{\delta}{M}$.

See Section 4.1.2 for the proof of Lemma 5.

####  4.1.1 Completing the proof

Using the two lemmas above, we can now complete the proof of Theorem 2(a).
Recalling the epoch sample size formula (22a), we see that the bound (38)
holds for all epochs

$\displaystyle m\geq
m^{*}:\,=\log_{2}\frac{1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma}}{\Delta\sqrt{1-\gamma}}.$

Observe that the minimum sample size requirement from Theorem 2 ensures that
$M\geq m^{*}$. Now, applying the recursions (38) and (37) we obtain

$\displaystyle\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{M+1}-\theta^{\star}\|_{\infty}$
$\displaystyle\leq\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{M}-\theta^{\star}\|_{\infty}}{16}+c\left(\frac{\tau^{*}}{\sqrt{N_{M}}}+\frac{\kappa}{N_{M}}\right)$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m^{*}}-\theta^{\star}\|_{\infty}}{16^{M-m^{*}}}+c\cdot\left(\sum_{k=0}^{M-m^{*}}\frac{\tau^{*}}{16^{k}\sqrt{N_{M-k}}}+\frac{\kappa}{16^{k}\cdot
N_{M-k}}\right)$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}-\theta^{\star}\|_{\infty}}{16^{M}}+c\cdot\left(\sum_{k=0}^{M-m^{*}}\frac{\tau^{*}}{16^{k}\sqrt{N_{M-k}}}+\sum_{k=M-m^{*}+1}^{M}\frac{\tau_{\max}}{16^{k}\sqrt{N_{M-k}}}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad+c\cdot\sum_{k=0}^{M}\frac{\kappa}{16^{k}N_{M-k}}$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\leq}}\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}-\theta^{\star}\|_{\infty}}{16^{M}}+c\cdot\left(\frac{\tau_{\max}}{8^{M-m^{*}}\cdot\sqrt{N_{M}}}+\frac{\tau^{*}}{\sqrt{N_{M}}}+\frac{\kappa}{N_{M}}\right).$

Inequality (i) follows via repeated application of the recursion (38),
inequality (ii) follows via repeated application of the recursion (37), and
inequality (iii) utilizes the relation ${N_{M-k}\cdot 4^{k}=N_{M}}$ (cf.
definition (22a)). Via the union bound, the above inequalities hold
simultaneously with probability at least $1-\delta$. Next, note that by our
choice of $N_{m}$, we have the inequality $2N_{M}\leq N\leq\frac{8}{3}N_{M}$.
Putting together the pieces, we conclude that

$\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{M+1}-\theta^{\star}\|_{\infty}\leq
c\cdot\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}-\theta^{\star}\|_{\infty}\cdot\frac{\log^{2}((8D/\delta)\cdot\log
N)}{N^{2}(1-\gamma)^{4}}+c\cdot\frac{(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{4}}{(1-\gamma)^{1.5}\sqrt{N}}\cdot\frac{\log^{2}((8D/\delta)\cdot\log
N)}{N^{3/2}(1-\gamma)^{\frac{9}{2}}\Delta^{3}}\\\
+c\cdot\left(\sqrt{\frac{\log_{4}(8DM/\delta)}{N}}\max_{\pi^{\star}\in\mathbf{\Pi^{\star}}}\|\nu(\pi^{\star};\mathbf{P},r,\gamma)\|_{\infty}+\frac{\log_{4}(8DM/\delta)}{N}\cdot\frac{\|\theta^{\star}\|_{\mathrm{span}}}{1-\gamma}\right).$
(39)

Substituting the lower bound condition

$\displaystyle\frac{N}{\log^{2}(N)}\geq
c\log(D/\delta)\frac{(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{2}}{(1-\gamma)^{3}}\cdot\max\left\\{1,\frac{1}{\Delta^{2}\cdot(1-\gamma)^{\beta}}\right\\}$

yields the claimed bound. All that remains is to verify the choice of batch
sizes $\\{N_{m}\\}_{M=1}^{M}$ is a valid choice, i.e., we need to verify that
the algorithm VR-QL with parameter choices (22) uses at most $N$ samples.
Recall that the total number of samples used in the $M$ epochs is given by
$KM+\sum_{m=1}^{M}N_{m}$. Substituting the values of $N_{m}$ and $M$ from
equations (22) we obtain

$\displaystyle KM+\sum_{M=1}^{M}N_{m}$ $\displaystyle\leq
c\cdot\log_{4}(8DM/\delta)\cdot\sum_{m=1}^{M}\frac{4^{m}}{(1-\gamma)^{2}}+\frac{N}{2}$
$\displaystyle\leq
c^{\prime}\cdot\log_{4}(8DM/\delta)\cdot\frac{4^{M}}{(1-\gamma)^{2}}\leq\frac{N}{2}+\frac{N}{2}\leq
N.$

This completes the proof of Theorem 2(a).

##### Comment on the lower-order terms:

Here, we argue that the first two terms in the right-hand side of the bound
(39) are of lower order. A careful look at the proof reveals that for any
$p\geq 1$ by increasing our choice of $N_{m}$ by a constant factor depending
on $p$, we can bound the first term by

$\displaystyle c_{1}\cdot\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}-\theta^{\star}\|_{\infty}}{N^{p}}\cdot\frac{\log^{p}((8D/\delta)\cdot\log
N)}{(1-\gamma)^{2p}},$

and the second term by

$\displaystyle
c_{2}\cdot\frac{(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{3q+1}}{(1-\gamma)^{1.5}\sqrt{N}}\cdot\frac{\log^{2q}((8D/\delta)\cdot\log
N)}{N^{3q/2}(1-\gamma)^{\frac{9q}{2}}\Delta^{3q}},$

where $q=\frac{2}{3}p-\frac{1}{3}$, and $(c_{1},c_{2})$ are universal
constants only depending on $(p,q)$. The number of samples satisfies
$N\gtrsim\frac{(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{2}}{\Delta^{2}(1-\gamma)^{3+\beta}}$
by assumption, and consequently, the two terms can be made arbitrarily small
by increasing $(p,q)$ appropriately. The equation (39) displays the bound for
the pair $(p,q)=(2,1)$.

The only remaining detail is to prove Lemma 5.

####  4.1.2 Proof of Lemma 5

Recall that the update within an epoch takes the form (cf. SingleEpoch)

$\displaystyle\theta_{k+1}=(1-\alpha_{k})\theta_{k}+\alpha_{k}\left\\{\widehat{\mathbf{T}}_{k}(\theta)-\widehat{\mathbf{T}}_{k}(\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m})+\overline{\mathbf{T}}_{N_{m}}(\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m})\right\\},$

where $\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}$ represents the
input into epoch $m$. We define the shifted operators and noisy shifted
operators for epoch $m$ by

$\displaystyle\mathbf{J}(\theta)=\mathbf{T}(\theta)-\mathbf{T}(\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m})+\overline{\mathbf{T}}_{N_{m}}(\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m})\quad\text{and}\quad\widehat{\mathbf{J}}_{k}(\theta)=\widehat{\mathbf{T}}_{k}(\theta)-\widehat{\mathbf{T}}_{k}(\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m})+\overline{\mathbf{T}}_{N_{m}}(\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}).$ (40)

Since both of the operators $\mathbf{T}$ and $\widehat{\mathbf{T}}_{k}$ are
$\gamma$-contractive in the $\ell_{\infty}$-norm, the operators $\mathbf{J}$
and $\widehat{\mathbf{J}}_{k}$ are also $\gamma$-contractive operators in the
same norm. Let $\widehat{\theta}_{m}$ denote the unique fixed point of the
operator $\mathbf{J}$. The roadmap of the proof is to show that at the end of
epoch $m$, the estimate $\theta_{K+1}$ is close to the fixed point
$\widehat{\theta}_{m}$ for sufficiently large value of the epoch length $K$
and that the fixed point $\widehat{\theta}_{m}$ is closer to $\theta^{\star}$
than the epoch initialization $\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}$ for sufficiently
large $N_{m}$.

The proof of Lemma 5 relies on two auxiliary lemmas that formalize this
intuition. Lemma 6 characterizes the progress of Algorithm VR-QL within an
epoch, and Lemma 7 addresses the progress of Algorithm VR-QL over the epochs.

######  Lemma 6.

Given an epoch length $K$ lower bounded as $K\geq
c_{2}\frac{\log(ND/\delta)}{(1-\gamma)^{3}}$, we have

$\displaystyle\|\theta_{K+1}-\widehat{\theta}_{m}\|_{\infty}\leq\frac{1}{33}\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}+\frac{1}{33}\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty},$

with probability exceeding $1-\frac{\delta}{2M}$.

Lemma 6 is borrowed from the paper [9]; see the proof of Lemma 2 in that paper
for details.

Our next lemma bounds the difference between the epoch fixed point
$\widehat{\theta}_{m}$ and the optimal value function $\theta^{\star}$.

######  Lemma 7.

Assume that $N_{m}$ satisfies the bound $N_{m}\geq
c\log_{4}(8DM/\delta)\frac{(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{2}}{\Delta^{2}(1-\gamma)^{3}}$.
Then we have

$\displaystyle\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}\leq\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}}{33}+c_{4}\left\\{\frac{\tau^{*}}{\sqrt{N_{m}}}+\frac{\kappa}{N_{m}}\right\\},$

with probability exceeding $1-\frac{\delta}{2M}$.

See Appendix C.1 for a proof of this lemma.

With these two auxiliary results in hand, completing the proof of Lemma 5 is
relatively straightforward. By the triangle inequality, we have

$\displaystyle\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m+1}-\theta^{\star}\|_{\infty}\equiv\|\theta_{K+1}-\theta^{\star}\|_{\infty}$
$\displaystyle\leq\|\theta_{K+1}-\widehat{\theta}_{m}\|_{\infty}+\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\left\\{\frac{1}{32}\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}+\frac{1}{32}\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}\right\\}+\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}$
$\displaystyle=\frac{1}{32}\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}+\frac{33}{32}\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\frac{1}{32}\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}+\frac{1}{32}\left\\{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}\right\\}+c\left(\frac{\tau^{*}}{\sqrt{N_{m}}}+\frac{\kappa}{N_{m}}\right)$
. $\displaystyle\leq\frac{1}{16}\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}++c\left(\frac{\tau^{*}}{\sqrt{N_{m}}}+\frac{\kappa}{N_{m}}\right).$
(41)

Here inequality (i) follows from Lemma 6, whereas inequality (ii) follows from
Lemma 7. Finally, the two bounds hold jointly with probability at least
$1-\frac{\delta}{M}$ via a union bound.

###  4.2 Proof of Theorem 2(b)

This argument follows the same structure as the proof of part (a) of Theorem
2; we retain the same shorthands from equation (36). Our proof uses Lemma 4
along with the following modification of Lemma 5.

######  Lemma 8.

Under the conditions of Theorem 2(b), for epochs $m$ such that the re-
centering sample size $N_{m}$ satisfies the bound
$N_{m}\geq\log_{4}(8DM/\delta)\frac{L^{2}(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{2}}{(1-\gamma)^{5}}$,
we have

$\displaystyle\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m+1}-\theta^{\star}\|_{\infty}\leq\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}}{16}+c\cdot\left(\frac{\tau^{*}}{\sqrt{N_{m}}}+\frac{\kappa}{N_{m}}\right),$
(42)

with probability at least $1-\frac{\delta}{M}$.

See Appendix C.3 for a proof of this lemma.

Observe that Lemma 8 holds for all epochs $m\geq
m^{*}:\,=\log_{2}\frac{L(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})}{(1-\gamma)^{3/2}}$.
Invoking Lemma 4 for all $m<m^{*}$ and Lemma 8 for all epochs $m\geq m^{*}$,
and doing a calculation similar to the proof of part (a), yields

$\displaystyle\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{M+1}-\theta^{\star}\|_{\infty}\leq\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}-\theta^{\star}\|_{\infty}}{16^{M}}+c\cdot\left(\frac{\tau_{\max}}{8^{M-m^{*}}\sqrt{N_{M}}}+\frac{\tau^{*}}{\sqrt{N_{M}}}+\frac{\kappa}{N_{M}}\right),$

with probability exceeding $1-\delta$. Finally, our choice of the epoch size
$N_{m}$ (cf. definition (22a)) ensures $2N_{M}\leq N\leq\frac{8}{3}N_{M}$, and
substituting the values of the triple $(N_{m},m^{*},M)$ we conclude that

$\displaystyle\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{M+1}-\theta^{\star}\|_{\infty}$
$\displaystyle\leq c\cdot\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}-\theta^{\star}\|_{\infty}\cdot\frac{\log^{2}((8D/\delta)\cdot\log
N)}{N^{2}(1-\gamma)^{4}}+c\cdot\frac{L^{3}(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{4}}{(1-\gamma)^{1.5}\sqrt{N}}\cdot\frac{\log^{2}((8D/\delta)\cdot\log
N)}{N^{1.5}(1-\gamma)^{7.5}}$
$\displaystyle+c\cdot\left(\sqrt{\frac{\log_{4}(8DM/\delta)}{N}}\max_{\pi^{\star}\in\mathbf{\Pi^{\star}}}\|\nu(\pi^{\star};\mathbf{P},r,\gamma)\|_{\infty}+\frac{\log_{4}(8DM/\delta)}{N}\cdot\frac{\|\theta^{\star}\|_{\mathrm{span}}}{1-\gamma}\right),$

##### Comment on the lower-order terms:

For any $p\geq 1$ by increasing our choice of $N_{m}$ by a constant factor
depending on $p$, we can bound the first term via

$\displaystyle c_{1}\cdot\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}-\theta^{\star}\|_{\infty}}{N^{p}}\cdot\frac{\log^{p}((8D/\delta)\cdot\log
N)}{(1-\gamma)^{2p}},$

and the second term by

$\displaystyle
c_{2}\cdot\frac{L^{3q}(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{3q+1}}{(1-\gamma)^{1.5}\sqrt{N}}\cdot\frac{\log^{3q/2}((8D/\delta)\cdot\log
N)}{N^{3q/2}(1-\gamma)^{15q/2}},$

with $q=\frac{2}{3}p-\frac{1}{3}$. The number of samples satisfies
$N\gtrsim\frac{L^{2}(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{2}}{(1-\gamma)^{5+\beta}}$
by assumption, so the two can be made arbitrarily small by increasing $(p,q)$
appropriately. This completes the proof of Theorem 2(b).

##  5 Discussion

In this paper, we presented an analysis of $Q$-learning through the instance-
dependent framework in the synchronous setting. For $\gamma$-discounted MDPs
with finite state space $\mathcal{X}$ and action space $\mathcal{U}$, we have
proved a local non-asymptotic lower bound for estimating the $Q$-function
dependent on a functional $\nu(\cdot;\mathbf{P},r)$ of the MDP instance
$(\mathbf{P},r)$ that measures the variance of solving for the $Q$-function.
In addition, we have provided an analysis of a form of variance-reduced
$Q$-learning and obtained instance-dependent guarantees on the
$\ell_{\infty}$-error for sample sizes $\frac{N}{(\log N)^{2}}\geq
c\cdot\frac{\log(D/\delta)}{(1-\gamma)^{3}\Delta^{@}}$ and $\frac{N}{(\log
N)^{2}}\geq c\frac{\log(D/\delta)}{(1-\gamma)^{5}}$ on Lipschitz MDPs that
match the corresponding lower bound, establishing instance-optimality. We
conjecture that optimality of Algorithm VR-QL still remains true for general
MDPs and sample sizes $N\geq\frac{\log(D/\delta)}{(1-\gamma)^{3}}$, and is
left for further endeavours.

##  Appendix A Calculations for Example 1

Here we derive the bound (12). Letting $V^{\star}$ denote the value function
of the optimal policy $\pi^{\star}$, we have

$\displaystyle(\textbf{Z}^{\pi^{\star}}-\mathbf{P}^{\pi^{\star}})\theta=\begin{bmatrix}|&|\\\
(\textbf{Z}_{u_{1}}-\mathbf{P}_{u_{1}})V^{\star}&0\\\ |&|\end{bmatrix}.$ (43)

Letting
$\mathbf{W}=(\mathbf{I}-\gamma\mathbf{P}_{u_{1}})^{-1}(\textbf{Z}_{u_{1}}-\mathbf{P}_{u_{1}})\theta_{\pi^{\star}}$
and solving for
$(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})\textbf{Y}=\gamma(\textbf{Z}^{\pi^{\star}}-\mathbf{P}^{\pi^{\star}})\theta$
gives

$\displaystyle\textbf{Y}=\gamma\cdot\begin{bmatrix}|&|\\\
\mathbf{W}&\gamma\mathbf{W}\\\ |&|\end{bmatrix}.$ (44)

Thus, we have

$\displaystyle\|\nu(\pi^{\star};\mathbf{P}_{\lambda},r_{\lambda})\|_{\infty}$
$\displaystyle:\,=\max_{(x,u)}\;|\nu(\pi^{\star};\mathbf{P}_{\lambda},r_{\lambda})(x,u)|=\max_{(x,u)}\;|\sqrt{\operatorname{Var}(\textbf{Y})(x,u)}|\leq
c\cdot\frac{1}{(1-\gamma)^{1.5-\lambda}}$

The second equality above follows from the definition (5) of the matrix
$\nu(\pi^{\star};\mathbf{P}_{\lambda},r_{\lambda})$, and the last step via
some simple calculations.

##  Appendix B Auxiliary lemmas for Theorem 1

In this section, we prove the auxiliary lemmas that are the used in the proof
of Theorem 1.

###  B.1 Proof of Lemma 1

This proof uses standard arguments, in particular following the usual avenue
of reducing estimation to testing [3, 24]. For completeness, we provide the
details here. We use $\theta$ and $\theta^{\prime}$ to denote the optimal
$Q$-functions for problem $\mathcal{P}$ and $\mathcal{P}^{\prime}$
respectively. We first lower bound the minimax risk over
$\mathcal{P},\mathcal{P}^{\prime}$ by the averaged risk as follows:

$\displaystyle\inf_{\hat{\theta}_{N}}\max_{\mathcal{Q}\in\\{\mathcal{P},\mathcal{P}^{\prime}\\}}\mathbb{E}_{\mathcal{P}}\left[\|\theta-\theta(\mathcal{Q})\|_{\infty}\right]\geq\frac{1}{2}\left(\mathbb{E}_{\mathcal{P}^{N}}\left[\|\hat{\theta}_{N}-\theta\|_{\infty}\right]+\mathbb{E}_{(\mathcal{P}^{\prime})^{N}}\left[\|\hat{\theta}_{N}-\theta^{\prime}\|_{\infty}\right]\right).$

Here $\mathcal{P}^{N}$ is a product measure that yields $N$ i.i.d. samples
from $\mathcal{P}$. Then, for any $\delta\geq 0$, we have by Markov’s
inequality

$\displaystyle\mathbb{E}_{\mathcal{P}^{N}}\left[\|\hat{\theta}_{N}-\theta\|_{\infty}\right]+\mathbb{E}_{(\mathcal{P}^{\prime})^{N}}\left[\|\hat{\theta}_{N}-\theta^{\prime}\|_{\infty}\right]\geq\delta\left[\mathcal{P}^{N}\left(\|\hat{\theta}_{N}-\theta\|_{\infty}\geq\delta\right)+(\mathcal{P}^{\prime})^{N}\left(\|\hat{\theta}_{N}-\theta^{\prime}\|_{\infty}\geq\delta\right)\right].$

Define $\delta_{01}:\,=\frac{1}{2}\|\theta-\theta^{\prime}\|_{\infty}$, we
have

$\displaystyle\|\hat{\theta}_{N}-\theta\|_{\infty}<\delta_{01}\implies\|\hat{\theta}_{N}-\theta^{\prime}\|_{\infty}>\delta_{01},$

yielding

$\displaystyle\mathbb{E}_{\mathcal{P}^{N}}\left[\|\hat{\theta}_{N}-\theta\|_{\infty}\right]+\mathbb{E}_{(\mathcal{P}^{\prime})^{N}}\left[\|\hat{\theta}_{N}-\theta\|_{\infty}\right]$
$\displaystyle\geq\delta_{01}\left[1-\mathcal{P}^{N}\left(\|\hat{\theta}_{N}-\theta\|_{\infty}<\delta_{01}\right)+(\mathcal{P}^{\prime})^{N}\left(\|\hat{\theta}_{N}-\theta^{\prime}\|_{\infty}\geq\delta_{01}\right)\right]$
$\displaystyle\geq\delta_{01}\left[1-\mathcal{P}^{N}\left(\|\hat{\theta}_{N}-\theta^{\prime}\|_{\infty}\geq\delta_{01}\right)+(\mathcal{P}^{\prime})^{N}\left(\|\hat{\theta}_{N}-\theta^{\prime}\|_{\infty}\geq\delta_{01}\right)\right]$
$\displaystyle\geq\delta_{01}\left[1-\|\mathcal{P}^{N}-(\mathcal{P}^{\prime})^{N}\|_{\text{TV}}\right]$
$\displaystyle\geq\delta_{01}\left[1-\sqrt{2}d_{\text{Hel}}\left(\mathcal{P}^{N},(\mathcal{P}^{\prime})^{N}\right)^{2}\right].$

Via the tensorization property of the Hellinger distance for independent
random variables we have

$\displaystyle
d_{\text{Hel}}\left(\mathcal{P}^{N},(\mathcal{P}^{\prime})^{N}\right)^{2}=1-\left(1-d_{\text{Hel}}\left(\mathcal{P},\mathcal{P}^{\prime}\right)^{2}\right)^{N}\leq
Nd_{\text{Hel}}\left(\mathcal{P},\mathcal{P}^{\prime}\right)^{2}.$

Putting together the pieces, we have that

$\displaystyle\inf_{\hat{\theta}_{N}}\max_{\mathcal{Q}\in\\{\mathcal{P},\mathcal{P}^{\prime}\\}}\mathbb{E}_{\mathcal{Q}}\left[\|\theta-\theta(\mathcal{Q})\|_{\infty}\right]\geq\frac{1}{4}\|\theta(\mathcal{P})-\theta(\mathcal{P}^{\prime})\|_{\infty}\cdot\left(1-\sqrt{2}N\cdot
d_{\text{Hel}}\left(\mathcal{P},\mathcal{P}^{\prime}\right)^{2}\right)_{+}.$

The desired result then follows from taking a supremum over all positive
alternative $\mathcal{P}^{\prime}\in\mathcal{S}$ and a simple calculation.

###  B.2 Proof of Lemma 3

We devote a subsection to each of the three parts of this lemma.

####  B.2.1 Proof of Lemma 3(a)

In order to establish that $\bar{\mathbf{P}}$ is a transition kernel, we
observe that

$\displaystyle\sum_{x^{\prime}}\bar{\mathbf{P}}_{x^{\prime},z}=1+\frac{1}{\tilde{\rho}(\bar{z})\sqrt{2N}}\mathbf{U}_{\bar{z},z}\cdot\left(\sum_{x^{\prime}}\mathbf{P}_{x^{\prime},z}(\theta(x^{\prime},{\pi_{1}}(x^{\prime}))-(\mathbf{P}^{\pi_{1}}\theta)(z))\right)=1,$

where the last equality above follows by noting that
$(\mathbf{P}^{\pi_{1}}\theta)(z)=\sum_{x^{\prime}}\mathbf{P}_{x^{\prime},z}\theta(x^{\prime},{\pi_{1}}(x^{\prime}))$.
To check non-negativity of entries of $\bar{\mathbf{P}}$ note we have
$|\mathbf{U}_{z,z^{\prime}}|\leq\frac{1}{1-\gamma}$, and
$2\|\theta\|_{\mathrm{span}}\geq|\theta(x^{\prime},{\pi_{1}}(x^{\prime}))-(\mathbf{P}^{\pi_{1}}\theta)(z)|$.
Combining the last two observation along with the sample size requirement
(10b) implies

$\displaystyle\bar{\mathbf{P}}_{x^{\prime},z}\geq
1-\frac{1}{\tilde{\rho}(\bar{z})\sqrt{2N}}\cdot\frac{\|\theta\|_{\mathrm{span}}}{1-\gamma}\geq
0,$

establishing that $\bar{\mathbf{P}}$ defines a valid set of transition
kernels.

####  B.2.2 Proof of Lemma 3(b)

The proof of part (b) follows by first providing a general upper bound on the
Hellinger distance $d_{\text{Hel}}\left(\mathcal{P},\mathcal{P}_{1}\right)$,
and then substituting the values of instances $\mathcal{P}$ and
$\mathcal{P}_{1}$. Concretely, we prove

$\displaystyle
d_{\text{Hel}}^{2}(\mathcal{P},\mathcal{P}_{1})\;\;\stackrel{{\scriptstyle\textnormal{(a)}}}{{\mathstrut{\leq}}}\;\;\frac{1}{2}\cdot\sum_{z,x^{\prime}}\frac{(\mathbf{P}_{x^{\prime},z}-\bar{\mathbf{P}}_{x^{\prime},z})^{2}}{\mathbf{P}_{x^{\prime},z}}\;\;\stackrel{{\scriptstyle\textnormal{(b)}}}{{\mathstrut{\leq}}}\;\;\frac{1}{4N}.$
(45)

With this result in hand, the claimed bound on
$|\\!|\\!|\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}}|\\!|\\!|_{{\infty\rightarrow\infty}}$
is immediate. Indeed,

$\displaystyle|\\!|\\!|\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}}|\\!|\\!|_{{\infty\rightarrow\infty}}^{2}\leq\sum_{z,x^{\prime}}(\mathbf{P}_{x^{\prime},z}-\bar{\mathbf{P}}_{x^{\prime},z})^{2}\leq\sum_{z,x^{\prime}}\frac{(\mathbf{P}_{x^{\prime},z}-\bar{\mathbf{P}}_{x^{\prime},z})^{2}}{\mathbf{P}_{x^{\prime},z}}\leq\frac{1}{2N}.$

It remains to prove the bounds (45)(a) and (45)(b).

##### Proof of (4545):

We use $(\textbf{Z},R)$ (respectively $(\textbf{Z}^{\prime},R^{\prime})$) to
denote a sample drawn from the distribution $P$ (respectively $P^{\prime}$),
and $P_{\textbf{Z}},P_{R}$ (respectively
$P_{\textbf{Z}}^{\prime},P_{R}^{\prime}$) to denote the marginal distribution
of $\textbf{Z},R$ (respectively $\textbf{Z}^{\prime},R^{\prime}$). By
independence of Z and $R$ (and likewise for $\textbf{Z}^{\prime},R^{\prime}$)
we have

$\displaystyle P=P_{\textbf{Z}}\otimes P_{R},\quad\text{and}\quad
P^{\prime}=P_{\textbf{Z}}^{\prime}\otimes P_{R}^{\prime}.$ (46)

Let $\mathcal{P}^{\prime}=(\mathbf{P}^{\prime},r^{\prime})\in\mathcal{S}_{1}$
(so $r^{\prime}=r$). Via the independence between Z and $R$, we have

$\displaystyle
d_{\text{Hel}}^{2}(P,P^{\prime})=d_{\text{Hel}}^{2}(P_{\textbf{Z}},P_{\textbf{Z}}^{\prime}).$
(47)

For state-action pairs $(x,u)$, $\textbf{Z}(x,u)$ are independent (and
likewise for $\textbf{Z}^{\prime}$) so

$\displaystyle
d_{\text{Hel}}^{2}(P_{\textbf{Z}},P_{\textbf{Z}}^{\prime})=1-\prod_{x,u}\left(1-d_{\text{Hel}}(P_{\textbf{Z}(x,u)},P_{\textbf{Z}^{\prime}(x,u)})\right)^{2}\leq\sum_{x,u}d_{\text{Hel}}^{2}(P_{\textbf{Z}(x,u)},P_{\textbf{Z}^{\prime}(x,u)}).$

Note that $\textbf{Z}(x,u)$ and $\textbf{Z}^{\prime}(x,u)$ have multinomial
distribution with parameters $\mathbf{P}_{u}(\cdot\mid x)$ and
$\mathbf{P}_{u}^{\prime}(\cdot\mid x)$ respectively. Therefore,

$\displaystyle
d_{\text{Hel}}^{2}(P_{\textbf{Z}(x,u)},P_{\textbf{Z}^{\prime}(x,u)})\leq\frac{1}{2}D_{\chi^{2}}\left(P_{\textbf{Z}^{\prime}(x,u)}\|P_{\textbf{Z}(x,u)}\right)=\frac{1}{2}\sum_{x^{\prime}}\frac{(\mathbf{P}_{x^{\prime},z}-\bar{\mathbf{P}}_{x^{\prime},z})^{2}}{\mathbf{P}_{x^{\prime},z}}.$

##### Proof of (4545):

We have

$\displaystyle\sum_{z,x^{\prime}}\frac{(\mathbf{P}_{x^{\prime},z}-\bar{\mathbf{P}}_{x^{\prime},z})^{2}}{\mathbf{P}_{x^{\prime},z}}$
$\displaystyle=\frac{1}{2N\tilde{\rho}^{2}(\bar{z})}\sum_{z}\sum_{x^{\prime}}\mathbf{P}_{x^{\prime},z}(\mathbf{U}_{\bar{z},z})^{2}(\theta(x^{\prime},{\pi_{1}}(x^{\prime}))-(\mathbf{P}^{\pi_{1}}\theta)(z))^{2}$
$\displaystyle=\frac{1}{2N\tilde{\rho}^{2}(\bar{z})}\sum_{z}(\mathbf{U}_{\bar{z},z})^{2}\cdot\left(\sum_{x^{\prime}}\mathbf{P}_{x^{\prime},z}(\theta(x^{\prime},{\pi_{1}}(x^{\prime}))-(\mathbf{P}^{\pi_{1}}\theta)(z))^{2}\right)$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{=}}\frac{1}{2N\tilde{\rho}^{2}(\bar{z})}\sum_{z}(\mathbf{U}_{\bar{z},z})^{2}\varphi^{2}(z)$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{=}}\frac{1}{2N},$

Equality (i) follows from the definition

$\displaystyle\varphi^{2}(z)=\text{Var}\left(\textbf{Z}^{\pi_{1}}\theta(z)\right)=\sum_{x^{\prime}}\mathbf{P}_{x^{\prime},z}(\theta(x^{\prime},{\pi_{1}}(x^{\prime}))-(\mathbf{P}^{\pi_{1}}\theta)(z))^{2},$
(48)

whereas equality (ii) follows from the definition (26), which ensures that

$\displaystyle\tilde{\rho}^{2}(\bar{z})=\text{Var}\left((\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}\textbf{Z}^{\pi_{1}}\theta(\bar{z})\right)=\sum_{z^{\prime}}(\mathbf{U}_{z,z^{\prime}})^{2}\varphi^{2}(z^{\prime}).$

####  B.2.3 Proof of Lemma 3(c)

The entries of the matrix
$\mathbf{U}:\,=(\mathbf{I}-\gamma\mathbf{P}^{\pi_{1}})^{-1}$ are positive, so
that it suffices to show that the vector
$(\bar{\mathbf{P}}^{\pi}-\mathbf{P}^{\pi})\theta$ is entry-wise positive. We
have

$\displaystyle(\bar{\mathbf{P}}^{\pi_{1}}-\mathbf{P}^{\pi_{1}})\theta(z)$
$\displaystyle=\sum_{x^{\prime}}(\bar{\mathbf{P}}_{x^{\prime},z}-\mathbf{P}_{x^{\prime},z})\theta(x^{\prime},{\pi_{1}}(x^{\prime}))$
$\displaystyle=\sum_{x^{\prime}}(\bar{\mathbf{P}}_{x^{\prime},z}-\mathbf{P}_{x^{\prime},z})(\theta(x^{\prime},{\pi_{1}}(x^{\prime}))-(\mathbf{P}^{\pi_{1}}\theta)(z))$
$\displaystyle=\frac{1}{\tilde{\rho}(\bar{z})\sqrt{2N}}\mathbf{U}_{\bar{z},z}\sum_{x^{\prime}}\mathbf{P}_{x^{\prime},z}(\theta(x^{\prime},{\pi_{1}}(x^{\prime}))-(\mathbf{P}^{\pi_{1}}\theta)(z))^{2}$
$\displaystyle=\frac{1}{\tilde{\rho}(\bar{z})\sqrt{2N}}\mathbf{U}_{\bar{z},z}\varphi^{2}(z)\geq
0,$

where the second equality follows from the fact that
$\sum_{x^{\prime}}\bar{\mathbf{P}}_{x^{\prime},z}=\sum_{x^{\prime}}\mathbf{P}_{x^{\prime},z}=1$,
the third equality follows by substituting the value of $\bar{\mathbf{P}}$
from equation (28), and the equality in the last line follows from the
definition (48). This completes the proof of part (c).

##  Appendix C Auxiliary lemmas for Theorem 2

In this section, we prove the auxiliary lemmas that are used in the proof of
Theorem 2.

###  C.1 Proof of Lemma 5

This section is devoted to the proof of Lemma 5 which underlies the proof of
Theorem 2. In order to simplify notation, we drop the epoch number $m$ from
$\widehat{\theta}_{m}$ and $\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}$ throughout the
remainder of the proof. Let $\widehat{\pi}$ and $\pi^{\star}$ denote the
greedy policies with respect to the $Q$ functions $\widehat{\theta}$ and
$\theta^{\star}$, respectively. Concretely,

$\displaystyle\pi^{\star}(x)=\arg\max_{u\in\mathcal{U}}\;\;\theta^{\star}(x,u)\qquad\widehat{\pi}(x)=\arg\max_{u\in\mathcal{U}}\;\;\widehat{\theta}(x,u).$
(49)

Ties in the $\arg\max$ are broken by choosing the action $u$ with smallest
index.

By the optimality of the policies $\widehat{\pi}$ and $\pi^{\star}$ for the
$Q$-functions $\widehat{\theta}$ and $\theta^{\star}$, respectively, we have

$\displaystyle\theta^{\star}=r+\gamma\mathbf{P}^{\pi^{\star}}\theta^{\star}\quad\text{and}\quad\widehat{\theta}=\widetilde{r}+\gamma\mathbf{P}^{\widehat{\pi}}\widehat{\theta},\quad\text{where}\quad\widetilde{r}:\,=r+\overline{\mathbf{T}}_{N_{m}}(\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta})-\mathbf{T}(\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}).$ (50)

In order to complete the proof, we require the following auxiliary result.

######  Lemma 9.

We have

$\displaystyle\|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}(\widetilde{r}-r)\|_{\infty}$
$\displaystyle\leq\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}-\theta^{\star}\|_{\infty}}{33}+4\cdot\sqrt{\frac{\log_{4}(8DM/\delta)}{N_{m}}}\cdot\max_{\pi\in\mathbf{\Pi^{\star}}}\|\nu(\pi;\mathbf{P},r)\|_{\infty}$
$\displaystyle\qquad\qquad+4\cdot\frac{\log_{4}(8DM/\delta)}{N_{m}}\cdot\frac{\|\theta^{\star}\|_{\mathrm{span}}}{(1-\gamma)},$

with probability exceeding $1-\frac{\delta}{8M}$.

See Appendix C.2 for the proof.

It remains to prove that under the assumptions of Lemma 5, the following bound
holds with probability $1-\frac{\delta}{M}$:

$\displaystyle\|\widehat{\theta}-\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}\|_{\infty}\leq\|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}(\widetilde{r}-r)\|_{\infty}.$
(51)

We establish this claim by first showing that the policy $\widehat{\pi}$ is an
optimal policy, which is achieved in the following lemma.

######  Lemma 10.

Given two $Q$-functions $\theta^{\star}$ and $\widehat{\theta}$ and the
associated optimal policies $\pi^{\star}$ and $\widehat{\pi}$, we have

$\displaystyle\mathbf{P}^{\widehat{\pi}}\theta^{\star}(x,u)\geq\mathbf{P}^{\pi^{\star}}\theta^{\star}(x,u)-2\|\widehat{\theta}-\theta^{\star}\|_{\infty}\quad\text{for
all}\quad(x,u)\in\mathcal{X}\times\mathcal{U}.$

Moreover, if the batch size satisfies the lower bound $N_{m}\geq
c_{3}\frac{(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{2}}{(1-\gamma)^{3}}\cdot\frac{\log(DM^{2}/\delta)}{\Delta^{2}}$,
then $\widehat{\pi}$ is an optimal policy with probability at least
$1-\frac{\delta}{M}$. Hence, under the unique optimal policy (UNQ) condition
or Lipschitz (LIP) condition, we have
$\mathbf{P}^{\widehat{\pi}}=\mathbf{P}^{\pi^{\star}}$.

We prove this lemma in Appendix C.4. In order to prove the bound (51), it
suffices to prove the following elementwise inequalities:

$\displaystyle\theta^{\star}-\widehat{\theta}$
$\displaystyle\preceq(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}(r-\widetilde{r})$
(52a) $\displaystyle\widehat{\theta}-\theta^{\star}$
$\displaystyle\preceq(\mathbf{I}-\gamma\mathbf{P}^{\widehat{\pi}})^{-1}(r-\widetilde{r})$
(52b)

Indeed, we have

$\displaystyle|\theta^{\star}-\widehat{\theta}|\preceq\max\\{|\theta^{\star}-\widehat{\theta}|_{+},|\widehat{\theta}-\theta^{\star}|_{+}\\}\preceq|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}(r-\widetilde{r})|,$

where the maximum operator $\max\\{\cdot,\cdot\\}$ is applied entry-wise.
Combining the last two bounds with Lemma 10, and using the lower bound
assumption on the epoch sample size $N_{m}$ we obtain

$\displaystyle|\theta^{\star}-\widehat{\theta}|\preceq\max\\{|\theta^{\star}-\widehat{\theta}|_{+},|\widehat{\theta}-\theta^{\star}|_{+}\\}$
$\displaystyle\preceq|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}(r-\widetilde{r}),(\mathbf{I}-\gamma\mathbf{P}^{\widehat{\pi}})^{-1}(r-\widetilde{r})|$
$\displaystyle\preceq|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}(r-\widetilde{r})|,$

where the last inequality uses
$\mathbf{P}^{\pi^{\star}}=\mathbf{P}^{\widehat{\pi}}$ (cf. Lemma 10). It
remains to prove the bounds (52a) and (52b).

##### Proof of bounds (52a) and (52b):

By optimality of policies $\widehat{\pi}$ and $\pi^{\star}$ for $Q$-functions
$\widehat{\theta}$ and $\theta^{\star}$, respectively, we have

$\displaystyle\theta^{\star}=r+\gamma\mathbf{P}^{\pi^{\star}}\theta^{\star}\succeq
r+\gamma\mathbf{P}^{\pi^{\star}}\widehat{\theta}\quad\text{and}\quad\widehat{\theta}=\widetilde{r}+\gamma\mathbf{P}^{\widehat{\pi}}\widehat{\theta}\succeq\widetilde{r}+\gamma\mathbf{P}^{\widehat{\pi}}\theta^{\star}.$
(53)

This yields:

$\displaystyle\theta^{\star}-\widehat{\theta}$
$\displaystyle=r-\widetilde{r}+\gamma(\mathbf{P}^{\pi^{\star}}\theta^{\star}-\mathbf{P}^{\widehat{\pi}}\widehat{\theta})\preceq
r-\widetilde{r}+\gamma\mathbf{P}^{\pi^{\star}}(\theta^{\star}-\widehat{\theta}).$
(54)

Rearranging the last inequality, and using the non-negativity of the entries
of $(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}$ we conclude

$\displaystyle(\theta^{\star}-\widehat{\theta})\preceq(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}(r-\widetilde{r}).$

This completes the proof of the bound (52a). The proof of bound (52b) is
similar.

###  C.2 Proof of Lemma 9

Recall the definition
$\widetilde{r}:\,=\widehat{R}+\gamma(\widehat{\textbf{Z}}^{\overline{\pi}}-\mathbf{P}^{\overline{\pi}})\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}$, where
$\overline{\pi}$ a policy greedy with respect to $\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}$; that is,
$\overline{\pi}(x)=\arg\max_{u\in\mathcal{U}}\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}(x,u)$, where we break
ties in the $\arg\max$ by choosing the action $u$ with smallest index. We have

$\displaystyle\|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}(\widetilde{r}-r)\|_{\infty}$
$\displaystyle\leq\|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}\left\\{(\widehat{R}-r)+\gamma(\widehat{\textbf{Z}}^{\pi^{\star}}-\mathbf{P}^{\pi^{\star}})\theta^{\star}\right\\}\|_{\infty}$
$\displaystyle\qquad+\gamma\|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}\left\\{(\widehat{\textbf{Z}}^{\overline{\pi}}\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}-\widehat{\textbf{Z}}^{\pi^{\star}}\theta^{\star})-(\mathbf{P}^{\overline{\pi}}\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}-\mathbf{P}^{\pi^{\star}}\theta^{\star})\right\\}\|_{\infty}.$

Observe that the random variable $\widehat{R}$ and $\widehat{\textbf{Z}}$ are
averages of $N_{m}$ i.i.d. random variables $\\{R_{i}\\}$ and
$\\{\widehat{\textbf{Z}}_{i}\\}$, respectively. Additionally, entrywise, the
random reward is a Gaussian random variable with variance $\sigma_{r}^{2}$,
and by the generative model assumption, the randomness in the random rewards
$\\{R_{i}\\}$ is independent of the randomness in
$\\{\widehat{\textbf{Z}}_{i}\\}$. Consequently, applying Hoeffding’s bound on
the term involving $\\{R_{i}\\}$, a Bernstein bound on the term involving
$\\{\widehat{\textbf{Z}}_{i}\\}$ and a union bound yields the following result
which holds with probability at least $1-\frac{\delta}{4M}$:

$\displaystyle\|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}\left\\{(\widehat{R}-r)+\gamma(\widehat{\textbf{Z}}^{\pi^{\star}}-\mathbf{P}^{\pi^{\star}})\theta^{\star}\right\\}\|_{\infty}$
$\displaystyle\qquad\leq\frac{4}{\sqrt{N_{m}}}\cdot\|\nu(\pi^{\star};\mathbf{P},r)\|_{\infty}\cdot\sqrt{\log_{4}(8DM/\delta)}+\frac{4\|\theta^{\star}\|_{\mathrm{span}}}{(1-\gamma)N_{m}}\cdot\log_{4}(8DM/\delta)$
$\displaystyle\qquad\leq\frac{4}{\sqrt{N_{m}}}\cdot\max_{\pi\in\mathbf{\Pi^{\star}}}\|\nu(\pi;\mathbf{P},r)\|_{\infty}\cdot\sqrt{\log_{4}(8DM/\delta)}+\frac{4\|\theta^{\star}\|_{\mathrm{span}}}{(1-\gamma)N_{m}}\cdot\log_{4}(8DM/\delta).$

Finally, for each state-action pair $(x,u)$ the random variable
$(\widehat{\textbf{Z}}^{\overline{\pi}}\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}-\widehat{\textbf{Z}}^{\pi^{\star}}\theta^{\star})(x,u)$
has expectation $(\mathbf{P}^{\overline{\pi}}\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}-\mathbf{P}^{\pi^{\star}})(x,u)$
with entries uniformly bounded by $2\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}-\theta^{\star}\|_{\infty}$.
Consequently, by a standard application of Hoeffding’s inequality combined
with the lower bound $N_{m}\geq
c_{3}\frac{4^{m}}{(1-\gamma)^{2}}\log_{4}(8DM/\delta)$, we have

$\displaystyle\frac{\gamma}{1-\gamma}\cdot\|(\widehat{\textbf{Z}}^{\overline{\pi}}\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}-\widehat{\textbf{Z}}^{\pi^{\star}}\theta^{\star})-(\mathbf{P}^{\overline{\pi}}\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}-\mathbf{P}^{\pi^{\star}}\theta^{\star})\|_{\infty}\leq\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}-\theta^{\star}\|_{\infty}}{33},$

with probability exceeding $1-\frac{\delta}{4M}$. The statement then follows
from combining these two high-probability statements with a union bound.

###  C.3 Proof of Lemma 8

By Lemma 6 and Lemma 9, it suffices to show

$\displaystyle\|\widehat{\theta}_{m}-\theta^{\star}_{m}\|_{\infty}\leq\frac{1}{2}\|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}(\widetilde{r}-r)\|_{\infty}$

Recalling the bounds (52a)–(52b), we have

$\displaystyle\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}$
$\displaystyle\leq\|(\mathbf{I}-\gamma^{\pi^{\star}})^{-1}(\widetilde{r}-r)\|_{\infty}+\gamma\|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}(\mathbf{P}^{\widehat{\pi}}-\mathbf{P}^{\pi^{\star}})(\widehat{\theta}_{m}-\theta^{\star})\|_{\infty}$
$\displaystyle\leq\|(\mathbf{I}-\gamma\mathbf{P}^{\pi^{\star}})^{-1}(\widetilde{r}-r)\|_{\infty}+\frac{L\gamma}{1-\gamma}\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}^{2}$

where the last inequality uses the Lipschitz condition (17). If we can show
${\frac{L\gamma}{1-\gamma}\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}\leq\frac{1}{2}}$,
we are done. In order to do so, we require the following auxiliary result:

######  Lemma 11.

Given a batch size $N_{m}$ lower bounded as $N_{m}\geq
c_{3}\frac{\log_{4}(8DM/\delta)}{(1-\gamma)^{2}}$, we have

$\displaystyle\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}\leq
c_{1}\cdot\frac{1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma}}{\sqrt{N_{m}}(1-\gamma)^{1.5}}\cdot\log_{4}(8DM^{2}/\delta)$

with probability at least $1-\frac{\delta}{4M}$.

With the above lemma at hand and using $N_{m}\geq
c\log_{4}(8DM/\delta)\frac{L^{2}(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{2}}{(1-\gamma)^{5}}$
we conclude

$\displaystyle\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}\leq\frac{1-\gamma}{2L},$

as desired. It remains to prove Lemma 11.

##### Proof of Lemma 11:

This proof exploits the result of Lemma 4, that with probability at least
$1-\frac{\delta}{M^{2}}$, we have

$\displaystyle\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}\leq\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}}{33}+\frac{1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma}}{(1-\gamma)^{1.5}}\sqrt{\frac{\log(8DM^{2}/\delta)}{N_{m}}}+\frac{\log(8DM^{2}/\delta)}{N_{m}}\cdot\frac{\|\theta^{\star}\|_{\mathrm{span}}}{1-\gamma}.$
(55)

Following an argument similar to the proof of Theorem 2, we have

$\displaystyle\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m+1}-\theta^{\star}\|_{\infty}$
$\displaystyle\leq\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{m}-\theta^{\star}\|_{\infty}}{16}+c\left\\{\frac{1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma}}{(1-\gamma)^{1.5}}\sqrt{\frac{\log(8DM^{2}/\delta)}{N_{m}}}+\frac{\log(8DM^{2}/\delta)}{N_{m}}\cdot\frac{\|\theta^{\star}\|_{\mathrm{span}}}{1-\gamma}\right\\}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\frac{\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}-\theta^{\star}\|_{\infty}}{16^{m}}+2c\left\\{\frac{1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma}}{(1-\gamma)^{1.5}}\sqrt{\frac{\log(8DM^{2}/\delta)}{N_{m}}}+\frac{\log(8DM^{2}/\delta)}{N_{m}}\cdot\frac{\|\theta^{\star}\|_{\mathrm{span}}}{1-\gamma}\right\\}$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{\leq}}\frac{\|r\|_{\infty}}{\sqrt{1-\gamma}}\cdot\frac{1}{(1-\gamma)\sqrt{N_{m}}}\cdot\frac{1}{4^{m}}$
$\displaystyle\qquad\quad+2c\left\\{\frac{1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma}}{(1-\gamma)^{1.5}}\sqrt{\frac{\log(8DM^{2}/\delta)}{N_{m}}}+\frac{\log(8DM^{2}/\delta)}{N_{m}}\cdot\frac{\|\theta^{\star}\|_{\mathrm{span}}}{1-\gamma}\right\\},$
(56)

with probability at least $1-\frac{\delta}{4M}$. Inequality (ii) follows by
recursing the first inequality; the last inequality uses the initialization
condition $\|\makebox[0.0pt][l]{\hskip
2.08334pt\rule[8.23611pt]{2.48053pt}{0.43057pt}}{\theta}_{1}-\theta^{\star}\|_{\infty}\leq\frac{\|r\|_{\infty}}{\sqrt{1-\gamma}}$,
and $N_{m}\geq\frac{4^{m}}{(1-\gamma)^{2}}$. Combining the bounds (55) and
(56) and using the bounds
$\|\theta^{\star}\|_{\infty}\leq\frac{\|r\|_{\infty}}{1-\gamma}$ and
$\|\theta^{\star}\|_{\mathrm{span}}\leq 2\|\theta^{\star}\|_{\infty}$, we find
that

$\displaystyle\|\widehat{\theta}_{m}-\theta^{\star}\|_{\infty}\leq
8c\cdot\frac{1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma}}{\sqrt{N_{m}}(1-\gamma)^{1.5}}\cdot\log(8DM^{2}/\delta),$

with probability at least $1-\frac{\delta}{4M}$. This completes the proof.

###  C.4 Proof of Lemma 10

The proof of this lemma exploits the optimality of the policies $\pi^{\star}$
and $\widehat{\pi}$ with respect to the $Q$-functions $\theta^{\star}$ and
$\widehat{\theta}$, respectively. Accordingly, we have for all state action
pair $(x,u)\in\mathcal{X}\times\mathcal{U}$

$\displaystyle\mathbf{P}^{\widehat{\pi}}\theta^{\star}(x,u)$
$\displaystyle=\mathbf{P}^{\widehat{\pi}}\widehat{\theta}(x,u)+\mathbf{P}^{\widehat{\pi}}\theta^{\star}(x,u)-\mathbf{P}^{\widehat{\pi}}\widehat{\theta}(x,u)$
$\displaystyle\geq\mathbf{P}^{\pi^{\star}}\widehat{\theta}(x,u)-\|\theta^{\star}-\widehat{\theta}\|_{\infty}$
$\displaystyle=\mathbf{P}^{\pi^{\star}}\theta^{\star}(x,u)+\mathbf{P}^{\pi^{\star}}\widehat{\theta}(x,u)-\mathbf{P}^{\pi^{\star}}\theta^{\star}(x,u)-\|\theta^{\star}-\widehat{\theta}\|_{\infty}$
$\displaystyle\geq\mathbf{P}^{\pi^{\star}}\theta^{\star}(x,u)-2\|\theta^{\star}-\widehat{\theta}\|_{\infty}.$
(57)

The first inequality follows from the optimality of the policy $\widehat{\pi}$
with respect to the $Q$-function $\widehat{\theta}$. This completes the proof
of the first part of the lemma.

Turning to the second part, invoking Lemma 11 with a batch size
$N_{m}\geq\frac{(1+\|r\|_{\infty}+\sigma_{r}\sqrt{1-\gamma})^{2}}{(1-\gamma)^{3}}\cdot\frac{\log(DM^{2}/\delta)}{\Delta^{2}}$
guarantees that

$\displaystyle 2\|\theta^{\star}-\widehat{\theta}\|_{\infty}$
$\displaystyle<\Delta.$

This inequality, combined with the bound (57) and the definition of the
optimality gap $\Delta$, implies that $\widehat{\pi}$ is an optimal policy,
and hence $\mathbf{P}^{\widehat{\pi}}=\mathbf{P}^{\pi^{\star}}$ under the
unique policy or Lipschitz assumptions.

## References

  * AMK [13] Mohammad Gheshlaghi Azar, Rémi Munos, and Hilbert J Kappen, _Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model_ , Machine Learning 91 (2013), no. 3, 325–349.
  * Ber [09] Dimitri P. Bertsekas, _Neuro-dynamic programming_ , Springer US, Boston, MA, 2009.
  * Bir [83] Lucien Birgé, _Approximation dans les espaces métriques et théorie de l’estimation_ , Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 65 (1983), no. 2, 181–237.
  * BRS [18] Jalaj Bhandari, Daniel Russo, and Raghav Singal, _A finite time analysis of temporal difference learning with linear function approximation_ , Conference On Learning Theory, PMLR, 2018, pp. 1691–1692.
  * CL [15] T Cai and Mark Low, _A framework for estimation of convex functions_ , Statistica Sinica 25 (2015), 423–456.
  * DSTM [18] Gal Dalal, Balázs Szörényi, Gugan Thoppe, and Shie Mannor, _Finite sample analyses for TD (0) with function approximation_ , AAAI Conference on Artificial Intelligence, vol. 32, 2018, pp. 6144–6153.
  * JJS [94] Tommi Jaakkola, Michael I Jordan, and Satinder P Singh, _On the convergence of stochastic iterative dynamic programming algorithms_ , Neural Computation 6 (1994), no. 6, 1185–1201.
  * JZ [13] Rie Johnson and Tong Zhang, _Accelerating stochastic gradient descent using predictive variance reduction_ , Advances in Neural Information Processing Systems, vol. 26, 2013, pp. 315–323.
  * KPR+ [20] Koulik Khamaru, Ashwin Pananjady, Feng Ruan, Martin J Wainwright, and Michael I Jordan, _Is temporal difference learning optimal? an instance-dependent analysis_ , arXiv preprint arXiv:2003.07337 (2020), 1–38.
  * LFDA [16] Sergey Levine, Chelsea Finn, Trevor Darrell, and Pieter Abbeel, _End-to-end training of deep visuomotor policies_ , Journal of Machine Learning Research 17 (2016), no. 1, 1334–1373.
  * LS [18] Chandrashekar Lakshminarayanan and Csaba Szepesvari, _Linear stochastic approximation: How far does constant step-size and iterate averaging go?_ , AISTATS: Conference on AI and Statistics, vol. 21, PMLR, 2018, pp. 1347–1355.
  * MMM [14] Odalric-Ambrym Maillard, Timothy A Mann, and Shie Mannor, _How hard is my MDP? ”The distribution-norm to the rescue”_ , Advances in Neural Information Processing Systems, vol. 27, 2014, pp. 1835–1843.
  * PB [79] Martin L. Puterman and Shelby L. Brumelle, _On the convergence of policy iteration in stationary dynamic programming_ , Mathematics of Operations Research 4 (1979), no. 1, 60–69.
  * Put [14] Martin L Puterman, _Markov Decision Processes: Discrete stochastic dynamic programming_ , John Wiley & Sons, 2014.
  * PW [20] A. Pananjady and M. J. Wainwright, _Instance-dependent $\ell_{\infty}$-bounds for policy evaluation in tabular reinforcement learning_, IEEE Transactions on Information Theory 67 (2020), no. 1, 566–585.
  * SB [18] Richard S. Sutton and Andrew G. Barto, _Reinforcement learning: An introduction_ , second ed., The MIT Press, 2018.
  * SHM+ [16] David Silver, Aja Huang, Chris J Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, and Marc Lanctot, _Mastering the game of Go with deep neural networks and tree search_ , Nature 529 (2016), no. 7587, 484–489.
  * SJ [19] Max Simchowitz and Kevin Jamieson, _Non-asymptotic gap-dependent regret bounds for tabular MDPs_ , Advances in Neural Information Processing Systems, vol. 33, 2019, pp. 1153–1162.
  * SWW+ [18] Aaron Sidford, Mengdi Wang, Xian Wu, Lin F Yang, and Yinyu Ye, _Near-optimal time and sample complexities for solving markov decision processes with a generative model_ , Advances in Neural Information Processing Systems, vol. 33, 2018, pp. 5192–5202.
  * SWWY [18] Aaron Sidford, Mengdi Wang, Xian Wu, and Yinyu Ye, _Variance reduced value iteration and faster algorithms for solving markov decision processes_ , ACM-SIAM Symposium on Discrete Algorithms, vol. 29, SIAM, 2018, pp. 770–787.
  * Sze [97] Csaba Szepesvári, _The asymptotic convergence-rate of $Q$-learning_, Advances in Neural Information Processing Systems, vol. 10, 1997, pp. 1064–1070.
  * TFR+ [17] Josh Tobin, Rachel Fong, Alex Ray, Jonas Schneider, Wojciech Zaremba, and Pieter Abbeel, _Domain randomization for transferring deep neural networks from simulation to the real world_ , International Conference on Intelligent Robots and Systems (IROS), IEEE, 2017, pp. 23–30.
  * Tsi [94] John N Tsitsiklis, _Asynchronous stochastic approximation and $Q$-learning_, Machine Learning 16 (1994), no. 3, 185–202.
  * [24] Martin J. Wainwright, _High-dimensional statistics: A non-asymptotic viewpoint_ , Cambridge Series in Statistical and Probabilistic Mathematics, Cambridge University Press, 2019.
  * [25] Martin J Wainwright, _Stochastic approximation with cone-contractive operators: Sharp $\ell_{\infty}$-bounds for $Q$-learning_, Tech. report, 2019, arXiv preprint arXiv:1905.06265.
  * [26] , _Variance-reduced $Q$-learning is minimax optimal_, Tech. report, 2019, arXiv preprint arXiv:1906.04697.
  * WD [92] Christopher JCH Watkins and Peter Dayan, _$Q$ -learning_, Machine Learning 8 (1992), no. 3-4, 279–292.
  * ZB [19] Andrea Zanette and Emma Brunskill, _Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds_ , International Conference on Machine Learning, PMLR, 2019, pp. 7304–7312.
  * ZKB [19] Andrea Zanette, Mykel J Kochenderfer, and Emma Brunskill, _Almost horizon-free structure-aware best policy identification with a generative model_ , Advances in Neural Information Processing Systems, vol. 32, 2019, pp. 5625–5634.