# Breaking the Sample Size Barrier in
Model-Based Reinforcement Learning with a Generative Model

Gen Li
Tsinghua
Department of Electronic Engineering, Tsinghua University, Beijing 100084,
China. Yuting Wei
CMU
Department of Statistics and Data Science, Carnegie Mellon University,
Pittsburgh, PA 15213, USA. Yuejie Chi
CMU
Department of Electrical and Computer Engineering, Carnegie Mellon University,
Pittsburgh, PA 15213, USA. Yuantao Gu11footnotemark: 1
Tsinghua
Yuxin Chen
Princeton
Department of Electrical Engineering, Princeton University, Princeton, NJ
08544, USA.

###### Abstract

We investigate the sample efficiency of reinforcement learning in a
$\gamma$-discounted infinite-horizon Markov decision process (MDP) with state
space $\mathcal{S}$ and action space $\mathcal{A}$, assuming access to a
generative model. Despite a number of prior work tackling this problem, a
complete picture of the trade-offs between sample complexity and statistical
accuracy is yet to be determined. In particular, prior results suffer from a
sample size barrier, in the sense that their claimed statistical guarantees
hold only when the sample size exceeds at least
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{2}}$ (up to some log factor).
The current paper overcomes this barrier by certifying the minimax optimality
of model-based reinforcement learning as soon as the sample size exceeds the
order of $\frac{|\mathcal{S}||\mathcal{A}|}{1-\gamma}$ (modulo some log
factor). More specifically, a perturbed model-based planning algorithm
provably finds an $\varepsilon$-optimal policy with an order of
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}\log\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)\varepsilon}$
samples for any $\varepsilon\in(0,\frac{1}{1-\gamma}]$. Along the way, we
derive improved (instance-dependent) guarantees for model-based policy
evaluation. To the best of our knowledge, this work provides the first
minimax-optimal guarantee in a generative model that accommodates the entire
range of sample sizes (beyond which finding a meaningful policy is information
theoretically impossible).

Keywords: model-based reinforcement learning, minimaxity, planning, policy
evaluation, instance-dependent guarantees, generative model

###### Contents

  1. 1 Introduction
  2. 2 Problem formulation
    1. 2.1 Models and background
    2. 2.2 Notation
  3. 3 Main results
    1. 3.1 Theoretical guarantees for model-based reinforcement learning
    2. 3.2 Comparisons with prior work and implications
  4. 4 Other related work
  5. 5 Analysis
    1. 5.1 Matrix notation and Bellman equations
    2. 5.2 Analysis: model-based policy evaluation
    3. 5.3 Analysis: model-based planning
      1. 5.3.1 Value function estimation for a policy obeying Bernstein-type conditions
      2. 5.3.2 Decoupling statistical dependency via $(s,a)$-absorbing MDPs
      3. 5.3.3 A tie-breaking argument
      4. 5.3.4 Proof of Theorem 1
  6. 6 Discussion
  7. A Preliminary facts
  8. B Proofs of auxiliary lemmas
    1. B.1 Proofs of Lemma 1 and Lemma 2
      1. B.1.1 Proof of Lemma 8
    2. B.2 Proof of Lemma 3
    3. B.3 Proof of Lemma 4
    4. B.4 Proof of Lemma 5
    5. B.5 Proof of Lemma 6

##  1 Introduction

Reinforcement learning (RL) (Sutton and Barto,, 2018; Szepesvári,, 2010),
which is frequently modeled as learning and decision making in a Markov
decision process (MDP), is garnering growing interest in recent years due to
its remarkable success in practice. A core objective of RL is to search for a
policy — based on a collection of noisy data samples — that approximately
maximizes expected rewards in an MDP, without direct access to a precise
description of the underlying model.111Here and throughout, the “model” refers
to the transition kernel and the rewards of the MDP taken collectively. In
contemporary applications, it is increasingly more common to encounter
environments with prohibitively large state and action space, thus
exacerbating the challenge of collecting enough samples to learn the model. To
enable faithful policy learning in the sample-starved regime (i.e. the regime
where the model complexity overwhelms the sample size), it is crucial to
obtain a quantitative picture of the trade-off between sample complexity and
statistical accuracy, and to design efficient algorithms that provably achieve
the optimal trade-off.

Broadly speaking, there are two common algorithmic approaches: a model-based
approach and a model-free one. In the model-based approach, one first learns
to describe the unknown model using the data samples in hand, and then
leverages the fitted model to perform planning — a task that can be
accomplished by resorting to Bellman’s principle of optimality (Bellman,,
1952; Puterman,, 2014). An advantage of model-based algorithms is their
flexibility: the learned model can be adapted to perform new ad-hoc tasks
without revisiting the data samples. In comparison, the model-free approach
attempts to compute the optimal policy (and the optimal value function)
without learning the model explicitly, which lends itself to scenarios when a
realistic model is difficult to construct or changes on the fly.
Characterizing the sample complexities for both approaches has been the focal
point of a large body of recent work, e.g. Azar et al., (2013); Kearns and
Singh, (1999); Wang, (2019); Sidford et al., 2018a ; Sidford et al., 2018b ;
Tu and Recht, (2018); Jin et al., (2018); Agarwal et al., (2019); Wainwright,
2019a ; Wainwright, 2019b .

In this paper, we pursue a comprehensive understanding of model-based RL,
assuming access to a generative model — that is, a simulator that produces
samples based on the transition kernel of the MDP for each state-action pair
(Kearns and Singh,, 1999; Kakade,, 2003). To allow for more precise
discussions, we focus our attention on an infinite-horizon discounted MDP with
state space $\mathcal{S}$, action space $\mathcal{A}$ and discount factor
$0<\gamma<1$. We obtain $N$ samples per state-action pair by querying the
generative model. For an arbitrary target accuracy level $\varepsilon>0$, a
desired model-based planning algorithm should return an $\varepsilon$-optimal
policy with a minimal number of calls to the generative model. Particular
emphasis is placed on the sub-linear sampling scenario, in which the total
sample size is smaller than the total number $|\mathcal{S}|^{2}|\mathcal{A}|$
of model parameters (so that it might be infeasible to estimate the model
accurately).

##### Motivation: a sample size barrier.

Several prior work was dedicated to investigating model-based RL with a
generative model, which uncovered the minimax optimality of this approach for
an already wide regime (Azar et al.,, 2013; Agarwal et al.,, 2019). However,
the results therein often suffered from a sample complexity barrier that
prevents us from obtaining a complete trade-off curve between sample
complexity and statistical accuracy. For instance, the state-of-the-art result
Agarwal et al., (2019) required the total sample size to at least exceed
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{2}}$ (up to some log factor),
thus restricting the validity of the theory for broader contexts. In truth,
this is not merely an issue for model-based planning; the same barrier already
showed up when analyzing the simpler task of model-based policy evaluation
(Pananjady and Wainwright,, 2019; Agarwal et al.,, 2019). Furthermore, a
similar or even higher barrier emerged in prior theory for model-free methods;
for instance, Sidford et al., 2018b ; Wainwright, 2019b  required the sample
size to exceed $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}}$ modulo some
log factor. In stark contrast, however, no lower bounds developed thus far
preclude us from attaining reasonable statistical accuracy when going below
the aforementioned sample complexity barriers.

##### Our contributions.

Following the model-based approach, we propose to perform planning based on an
empirical MDP learned from samples with mild reward perturbation. The
perturbed model-based algorithm we propose provably finds an
$\varepsilon$-optimal policy with an order of
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}$ samples (up
to log factor), which matches the minimax lower bound (Azar et al.,, 2013).
Our result accommodates the full range of accuracy level $\varepsilon$
(namely, $\varepsilon\in(0,\frac{1}{1-\gamma}]$), thus unveiling the
minimaxity of our algorithm as soon as the sample size exceeds
$\frac{|\mathcal{S}||\mathcal{A}|}{1-\gamma}$ (modulo some log factor);
encouragingly, this covers the full range of sample sizes that enable one to
find a policy strictly better than a random guess. See Table 1 for detailed
comparisons with prior literature. Along the way, we also derive (instance-
dependent) statistical guarantees for policy evaluation, which strengthens
state-of-the-art results by broadening the sample size range.

Our theory is established upon a novel combination of several key ideas: (1) a
high-order expansion of the estimation error for value functions, coupled with
fine-grained analysis for each term in the expansion; (2) the construction of
auxiliary leave-one-out type (state-action-absorbing) MDPs — motivated by
Agarwal et al., (2019) — that help decouple the complicated statistical
dependency between the empirically optimal policy (as opposed to value
functions) and data samples; (3) a tie-breaking argument guaranteeing that the
empirically optimal policy stands out from all other policies under reward
perturbation.

Algorithm | Sample size range | Sample complexity |  $\varepsilon$-range
---|---|---|---
Phased Q-learning | $\big{[}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{5}},\infty)$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{7}\varepsilon^{2}}$$\frac{1^{7^{7}}}{1^{7^{7^{7^{7}}}}}$ | $(0,\frac{1}{1-\gamma}]$
Kearns and Singh, (1999)
Empirical QVI | $\big{[}\frac{|\mathcal{S}|^{2}|\mathcal{A}|}{(1-\gamma)^{2}},\infty)$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}$ $\frac{1^{7^{7}}}{1^{7^{7^{7^{7}}}}}$ | $(0,\frac{1}{\sqrt{(1-\gamma)|\mathcal{S}|}}]$
Azar et al., (2013)
Sublinear randomized value iteration | $\big{[}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{2}},\infty)$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\varepsilon^{2}}$ $\frac{1^{7^{7}}}{1^{7^{7^{7^{7}}}}}$ | $\big{(}0,\frac{1}{1-\gamma}\big{]}$
Sidford et al., 2018b
Variance-reduced QVI | $\big{[}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}},\infty)$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}$ $\frac{1^{7^{7}}}{1^{7^{7^{7^{7}}}}}$ | $(0,1]$
Sidford et al., 2018a
Randomized primal-dual method | $\big{[}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{2}},\infty)$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\varepsilon^{2}}$ $\frac{1^{7^{7}}}{1^{7^{7^{7^{7}}}}}$ | $(0,\frac{1}{1-\gamma}]$
Wang, (2019)
Empirical MDP + planning | $\big{[}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{2}},\infty)$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}$ $\frac{1^{7^{7}}}{1^{7^{7^{7^{7}}}}}$ | $(0,\frac{1}{\sqrt{1-\gamma}}]$
Agarwal et al., (2019)
Perturbed empirical MDP + planning | $\big{[}\frac{|\mathcal{S}||\mathcal{A}|}{1-\gamma},\infty)$ | $\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}$ $\frac{1^{7^{7}}}{1^{7^{7^{7^{7}}}}}$ | $(0,\frac{1}{1-\gamma}]$
This paper
Table 1: Comparisons with prior results (up to log factors) regarding finding
an $\varepsilon$-optimal policy with a generative model. The sample size range
and the $\varepsilon$-range stand for the range of sample size and optimality
gap (e.g. $\varepsilon$-accuracy) for the claimed sample complexity to hold.
Note that the results in (Kearns and Singh,, 1999; Wang,, 2019) only hold for
a restricted family of MDPs satisfying certain ergodicity assumptions. In
addition, Azar et al., (2013) (resp. Wainwright, 2019b ) showed that empirical
QVI (resp. variance-reduced Q-learning) finds an $\varepsilon$-optimal
Q-function estimate with sample complexity
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}$
($\varepsilon\in(0,1]$) in a sample size range
$[\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}},\infty)$, which did not
translate directly to an $\varepsilon$-optimal policy.

##  2 Problem formulation

###  2.1 Models and background

##### Basics of Markov decision processes.

Consider an infinite-horizon discounted MDP represented by a quintuple
$\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\gamma)$, where
$\mathcal{S}:=\\{1,2,\ldots,|\mathcal{S}|\\}$ denotes a finite set of states,
$\mathcal{A}:=\\{1,2,\ldots,|\mathcal{A}|\\}$ is a finite set of actions,
$\gamma\in(0,1)$ stands for the discount factor, and
$r:\mathcal{S}\times\mathcal{A}\mapsto[0,1]$ represents the reward function,
namely, $r(s,a)$ is the immediate reward received upon executing action $a$
while in state $s$ (here and throughout, we consider the normalized setting
where the rewards lie within $[0,1]$). In addition,
$P:\mathcal{S}\times\mathcal{A}\mapsto[0,1]^{|\mathcal{S}|}$ represents the
probability transition kernel of the MDP, where $P(s^{\prime}|s,a)$ denotes
the probability of transiting from state $s$ to state $s^{\prime}$ when action
$a$ is executed.

A deterministic policy is a mapping $\pi:\mathcal{S}\mapsto\mathcal{A}$ that
maps a state to an action. The value function
$V^{\pi}:\mathcal{S}\mapsto\mathbb{R}^{|\mathcal{S}|}$ of a policy $\pi$ is
defined by

$\forall s\in\mathcal{S}:\qquad
V^{\pi}(s):=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s^{t},a^{t})\,\big{|}\,s^{0}=s\right],$
(1)

which is the expected discounted total reward starting from the initial state
$s^{0}=s$, with the actions taken according to the policy $\pi$ (namely,
$a^{t}=\pi(s^{t})$ for all $t\geq 0$) and the trajectory generated based on
the transition kernel (namely, $s^{t+1}\sim P(\cdot|s^{t},a^{t})$). It is
easily seen that $0\leq V^{\pi}(s)\leq\frac{1}{1-\gamma}$. The corresponding
action-value function (or Q-function)
$Q^{\pi}:\mathcal{S}\times\mathcal{A}\mapsto\mathbb{R}^{|\mathcal{S}|}$ of a
policy $\pi$ is defined by

$\forall(s,a)\in\mathcal{S}\times\mathcal{A}:\qquad
Q^{\pi}(s,a):=\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s^{t},a^{t})\,\big{|}\,s^{0}=s,a^{0}=a\right],$
(2)

where the actions are taken according to the policy $\pi$ after the initial
action (i.e. $a^{t}=\pi(s^{t})$ for all $t\geq 1$). It is well-known that
there exists an optimal policy, denoted by $\pi^{\star}$, that simultaneously
maximizes $V^{\pi}(s)$ (resp. $Q^{\pi}(s,a)$) for all states $s\in\mathcal{S}$
(resp. state-action pairs $(s,a)\in(\mathcal{S}\times\mathcal{A})$) (Sutton
and Barto,, 2018). The corresponding value function
$V^{\star}:=V^{\pi^{\star}}$ (resp. action-value function
$Q^{\star}:=Q^{\pi^{\star}}$) is called the optimal value function (resp.
optimal action-value function).

##### A generative model and an empirical MDP.

The current paper focuses on a stylized generative model (also called a
simulator) as studied in Kearns et al., (2002); Kakade, (2003). Assuming
access to this generative model, we collect $N$ independent samples
$s_{s,a}^{i}\sim P(\cdot|s,a)$, $i=1,\ldots,N$ for any state-action pair
$(s,a)$, which allows us to construct an empirical transition kernel
$\widehat{P}$ given by

$\forall
s^{\prime}\in\mathcal{S},\qquad\widehat{P}(s^{\prime}|s,a)=\frac{1}{N}\sum\nolimits_{i=1}^{N}\operatorname{\mathds{1}}\\{s_{s,a}^{i}=s^{\prime}\\},$
(3)

where $\operatorname{\mathds{1}}\\{\cdot\\}$ is the indicator function. In
words, $\widehat{P}(s^{\prime}|s,a)$ counts the empirical frequency of
transitions from $(s,a)$ to state $s^{\prime}$. The total sample size should
be understood as $N^{\mathsf{total}}:=N|\mathcal{S}||\mathcal{A}|$. This leads
to an empirical MDP
$\widehat{\mathcal{M}}=(\mathcal{S},\mathcal{A},\widehat{P},r,\gamma)$
constructed from the data samples. We can define the value function and the
action-value function of a policy $\pi$ for $\widehat{\mathcal{M}}$
analogously, which we shall denote by $\widehat{V}^{\pi}$ and
$\widehat{Q}^{\pi}$, respectively. The optimal policy of
$\widehat{\mathcal{M}}$ is denoted by $\widehat{\pi}^{\star}$, with the
optimal value function and Q-function denoted by
$\widehat{V}^{\star}:=\widehat{V}^{\widehat{\pi}^{\star}}$ and
$\widehat{Q}^{\star}:=\widehat{Q}^{\widehat{\pi}^{\star}}$, respectively.

##### Policy evaluation and planning.

Given a few data samples in hand, the task of policy evaluation aims to
compute or approximate the value function $V^{\pi}$ under a given policy
$\pi$. To be precise, for any target level $\varepsilon>0$, the goal is to
find an $\varepsilon$-accurate estimate $V^{\pi}_{\mathsf{est}}$ such that

$\displaystyle(\text{policy evaluation})\qquad\quad\forall
s\in\mathcal{S}:\qquad\big{|}{V}^{\pi}_{\mathsf{est}}(s)-{V}^{\pi}(s)\big{|}\leq\varepsilon.$
(4)

In contrast, the task of planning seeks to identify a policy that
(approximately) maximizes the expected discounted reward given the data
samples. Specifically, for any target level $\varepsilon>0$, the aim is to
compute an $\varepsilon$-accurate policy ${\pi}_{\mathsf{est}}$ obeying

$\displaystyle(\text{planning})\qquad\quad\forall(s,a)\in\mathcal{S}\times\mathcal{A}:\qquad
V^{{\pi}_{\mathsf{est}}}(s)\geq V^{\star}(s)-\varepsilon,\quad
Q^{{\pi}_{\mathsf{est}}}(s,a)\geq Q^{\star}(s,a)-\varepsilon.$ (5)

Naturally, one would hope to accomplish these tasks with as few samples as
possible. Recall that for the normalized reward setting with $0\leq r\leq 1$,
the value function and Q-function fall within the range
$[0,\frac{1}{1-\gamma}]$; this means that the range of the target level
$\varepsilon$ should be set to $\varepsilon\in[0,\frac{1}{1-\gamma}]$. The
model-based approach typically starts by constructing an empirical MDP
$\widehat{\mathcal{M}}$ based on all collected samples, and then “plugs in”
this empirical model directly into the Bellman recursion to perform policy
evaluation or planning, with prominent examples including Q-value iteration
(QVI) and policy iteration (PI) (Bertsekas,, 2017).

###  2.2 Notation

Let
$\mathcal{X}:=\big{(}|\mathcal{S}|,|\mathcal{A}|,\frac{1}{1-\gamma},\frac{1}{\varepsilon}\big{)}$.
The notation $f(\mathcal{X})=O(g(\mathcal{X}))$ means there exists a universal
constant $C_{1}>0$ such that $f\leq C_{1}g$, whereas the notation
$f(\mathcal{X})=\Omega(g(\mathcal{X}))$ means
$g(\mathcal{X})=O(f(\mathcal{X}))$. In addition, the notation
$\widetilde{O}(\cdot)$ (resp. $\widetilde{\Omega}(\cdot)$) is defined in the
same way as ${O}(\cdot)$ (resp. $\Omega(\cdot)$) except that it ignores
logarithmic factors.

For any vector $\bm{a}=[a_{i}]_{1\leq i\leq n}\in\mathbb{R}^{n}$, we overload
the notation $\sqrt{\cdot}$ and $|\cdot|$ in an entry-wise manner such that
$\sqrt{\bm{a}}:=[\sqrt{a_{i}}]_{1\leq i\leq n}$ and
$|\bm{a}|:=[|a_{i}|]_{1\leq i\leq n}$. For any vectors $\bm{a}=[a_{i}]_{1\leq
i\leq n}$ and $\bm{b}=[b_{i}]_{1\leq i\leq n}$, the notation
$\bm{a}\geq\bm{b}$ (resp. $\bm{a}\leq\bm{b}$) means $a_{i}\geq b_{i}$ (resp.
$a_{i}\leq b_{i}$) for all $1\leq i\leq n$, and we let
$\bm{a}\circ\bm{b}:=[a_{i}b_{i}]_{1\leq i\leq n}$ represent the Hadamard
product. Additionally, we denote by $\bm{1}$ the all-one vector, and $\bm{I}$
the identity matrix. For any matrix $\bm{A}$, we define the norm
$\|\bm{A}\|_{1}:=\max_{i}\sum_{j}|A_{i,j}|$.

##  3 Main results

###  3.1 Theoretical guarantees for model-based reinforcement learning

As summarized in Table 1, the theory of all prior work required the sample
size per state-action pair to at least exceed
$N\geq\Omega\big{(}\frac{1}{(1-\gamma)^{2}}\big{)}$. In order to break this
sample size barrier, we propose to invoke the model-based planning approach
applied to an empirical MDP with perturbed rewards.

Specifically, for each state-action pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$, let us randomly perturb the immediate
reward to obtain

$r_{\mathrm{p}}(s,a)=r(s,a)+\zeta(s,a),\qquad\zeta(s,a)\overset{\mathrm{i.i.d.}}{\sim}\mathsf{Unif}(0,\xi),$
(6)

where $\mathsf{Unif}(0,\xi)$ denotes the uniform distribution between 0 and
some parameter $\xi>0$ (to be specified momentarily). For any policy $\pi$, we
denote by $\widehat{{V}}^{\pi}_{{\mathrm{p}}}$ the corresponding value
function of the perturbed empirical MDP
$\widehat{\mathcal{M}}_{\mathrm{p}}=(\mathcal{S},\mathcal{A},\widehat{P},{r}_{\mathrm{p}},\gamma)$
with the probability transition kernel $\widehat{P}$ and the perturbed reward
function ${r}_{\mathrm{p}}$. Let $\widehat{\pi}_{\mathrm{p}}^{\star}$
represent the optimal policy of $\widehat{\mathcal{M}}_{\mathrm{p}}$, i.e.

$\displaystyle\widehat{\pi}_{\mathrm{p}}^{\star}:=\arg\max_{\pi}\widehat{{V}}^{\pi}_{{\mathrm{p}}}.$
(7)

Encouragingly, this policy results in a value function
$V^{\widehat{\pi}^{\star}_{\mathrm{p}}}$ (resp. Q-function
$Q^{\widehat{\pi}^{\star}_{\mathrm{p}}}$) that well approximates the true
optimal value function $V^{\star}$ (resp. optimal Q-function $Q^{\star}$), as
asserted by the following theorem.

######  Theorem 1 (Perturbed model-based planning).

There exist some universal constants $c_{0},c_{1}>0$ such that: for any
$\delta>0$ and any $0<\varepsilon\leq\frac{1}{1-\gamma}$, the policy
$\widehat{\pi}_{\mathrm{p}}^{\star}$ defined in (7) obeys

$\displaystyle\forall(s,a)\in\mathcal{S}\times\mathcal{A},\qquad
V^{\widehat{\pi}^{\star}_{\mathrm{p}}}(s)\geq
V^{\star}(s)-\varepsilon\qquad\text{and}\qquad
Q^{\widehat{\pi}^{\star}_{\mathrm{p}}}(s,a)\geq
Q^{\star}(s,a)-\gamma\varepsilon$ (8)

with probability at least $1-\delta$, provided that the perturbation size is
$\xi=\frac{c_{1}(1-\gamma)\varepsilon}{|\mathcal{S}|^{5}|\mathcal{A}|^{5}}$
and that the sample size per state-action pair exceeds

$\displaystyle
N\geq\frac{c_{0}\log\big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)\varepsilon\delta}\big{)}}{(1-\gamma)^{3}\varepsilon^{2}}.$
(9)

In addition, both the empirical QVI and PI algorithms w.r.t.
$\widehat{\mathcal{M}}_{\mathrm{p}}$ (cf. (Azar et al.,, 2013, Algorithms
1-2)) are able to recover $\widehat{\pi}_{\mathrm{p}}^{\star}$ perfectly
within
$O\big{(}\frac{1}{1-\gamma}\log(\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)\varepsilon\delta})\big{)}$
iterations.

######  Remark 1.

Theorem 1 holds unchanged if $\xi$ is taken to be
$\frac{c_{1}(1-\gamma)\varepsilon}{|\mathcal{S}|^{\alpha}|\mathcal{A}|^{\alpha}}$
for any $\alpha\geq 1$.

######  Remark 2.

Perturbation brings a side benefit: one can recover the optimal policy
$\widehat{\pi}^{\star}_{\mathrm{p}}$ of the perturbed empirical MDP
$\widehat{\mathcal{M}}_{\mathrm{p}}$ exactly in a small number of iterations
without incurring further ptimization errors. To give a flavor of the overall
computational complexity, let us take QVI for example Azar et al., (2013).
Recall that each iteration of QVI takes time proportional to the time taken to
read $\widehat{P}$ (which is a matrix with at most
$N|\mathcal{S}||\mathcal{A}|$ nonzeros), hence the resulting computational
complexity can be as low as
${O}\big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{4}\varepsilon^{2}}\log^{2}(\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)\varepsilon\delta})\big{)}$.

The above theorem demonstrates that: the perturbed model-based planning
approach finds an $\varepsilon$-optimal policy as soon as the total sample
complexity exceeds the order of
$\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\varepsilon^{2}}$ (modulo
some log factor). It is worth emphasizing that, compared to prior literature,
our result imposes no restriction on the range of $\varepsilon$ and, in
particular, we allow the accuracy level $\varepsilon$ to go all the way up to
$\frac{1}{1-\gamma}$. Our result is particularly useful in the regime with
small-to-moderate sample sizes, since its validity is guaranteed as long as

$\displaystyle N\geq\widetilde{\Omega}\Big{(}\frac{1}{1-\gamma}\Big{)}.$ (10)

Tackling the sample-limited regime (in particular, the scenario when
$N\in[\frac{1}{1-\gamma},\frac{1}{(1-\gamma)^{2}}]$) requires us to develop
new analysis frameworks beyond prior theory, which we shall discuss in detail
momentarily.

We remark that the work Azar et al., (2013) established a minimax lower bound
of the same order as (9) (up to some log factor) in the regime
$\varepsilon=O(1)$. A closer inspection of their analysis, however, reveals
that their argument and bound hold true as long as
$\varepsilon=O(\frac{1}{1-\gamma})$. This in turn corroborates the minimax
optimality of our perturbed model-based approach for the full
$\varepsilon$-range (which is previously unavailable), and demonstrates the
information-theoretic infeasibility to learn a policy strictly better than a
random guess if $N\leq\widetilde{O}\big{(}\frac{1}{1-\gamma}\big{)}$. Put
another way, the condition (10) contains the full range of “meaningful” sample
sizes.

Finally, we single out an intermediate result in the analysis of Theorem 1
concerning model-based policy evaluation, which might be of interest on its
own. Specifically, for any fixed policy $\pi$ independent of the data, this
task concerns value function estimation via the plug-in estimate
$\widehat{V}^{\pi}$ (i.e. the value function of the empirical $\mathcal{M}$
under this policy). However simple as this might seem, existing theoretical
underpinnings of this approach remain suboptimal, unless the sample size is
already sufficiently large. Our result is the following, which does not
require enforcing reward perturbation.

######  Theorem 2 (Model-based policy evaluation).

Fix any policy $\pi$. There exists some universal constant $c_{0}>0$ such
that: for any $0<\delta<1$ and any $0<\varepsilon<\frac{1}{1-\gamma}$, one has

$\displaystyle\forall
s\in\mathcal{S}:\qquad\big{|}\widehat{V}^{\pi}(s)-V^{\pi}(s)\big{|}\leq\varepsilon$
(11)

with probability at least $1-\delta$, provided that the sample size per state-
action pair exceeds

$\displaystyle N\geq
c_{0}\frac{\log\Big{(}\frac{|\mathcal{S}|\log\frac{e}{1-\gamma}}{\delta}\Big{)}}{(1-\gamma)^{3}\varepsilon^{2}}.$
(12)

In words, this theorem reveals that $\widehat{V}^{\pi}$ begins to outperform a
random guess as soon as
$N\geq\widetilde{\Omega}\Big{(}\frac{1}{1-\gamma}\Big{)}$. The sample
complexity bound (12) enjoys full coverage of the $\varepsilon$-range
$(0,\frac{1}{1-\gamma}]$, and matches the minimax lower bound derived in
(Pananjady and Wainwright,, 2019, Theorem 2(b)) up to only a
$\log\log\frac{1}{1-\gamma}$ factor. In addition, a recent line of work
investigated instance-dependent guarantees for policy evaluation (Pananjady
and Wainwright, (2019); Khamaru et al., (2020)). While this is not our focus,
our analysis does uncover an instance-dependent bound with a broadened sample
size range. See Lemma 1 and the discussion thereafter.

###  3.2 Comparisons with prior work and implications

In order to discuss the novelty of our results in context, we take a moment to
compare them with prior theory. See Table 1 for a more complete list of
comparisons.

##### Prior bounds for planning and policy learning.

None of the prior results with a generative model (including both model-based
or model-free approaches) was capable of efficiently finding the desired
policy while accommodating the full sample size range (10). For instance, the
state-of-the-art analysis for the model-based approach Agarwal et al., (2019)
required the sample size to at least exceed

$\displaystyle N\geq\widetilde{\Omega}\Big{(}\frac{1}{(1-\gamma)^{2}}\Big{)},$
(13)

whereas the theory for the variance-reduced model-free approach Sidford et
al., 2018a ; Wainwright, 2019b  imposed the sample size requirement

$\displaystyle N\geq\widetilde{\Omega}\Big{(}\frac{1}{(1-\gamma)^{3}}\Big{)}.$
(14)

In fact, it was previously unknown what is achievable in the sample size range
$N\in[\frac{1}{1-\gamma},\frac{1}{(1-\gamma)^{2}}]$. In contrast, our results
confirm the minimax-optimal statistical performance of the model-based
approach with full coverage of the $\varepsilon$-range and the sample size
range.

##### Prior bounds for policy evaluation.

Regarding value function estimation for any fixed policy $\pi$, the prior
results Azar et al., (2013); Agarwal et al., (2019); Pananjady and Wainwright,
(2019) for the plug-in approach all operated under the assumption that
$N\geq\widetilde{\Omega}\big{(}\frac{1}{(1-\gamma)^{2}}\big{)}$, which is more
stringent than our result by a factor of at least $\frac{1}{{1-\gamma}}$. In
addition, our sample complexity matches the state-of-the-art guarantees in the
regime where $\varepsilon\leq\frac{1}{\sqrt{1-\gamma}}$ (Agarwal et al.,,
2019; Pananjady and Wainwright,, 2019), while extending them to the range
$\varepsilon\in\big{[}\frac{1}{\sqrt{1-\gamma}},\frac{1}{1-\gamma}\big{]}$
uncovered in these previous papers.

##  4 Other related work

Classical analyses of reinforcement learning algorithms have largely focused
on asymptotic performance (e.g. Tsitsiklis and Van Roy, (1997); Szepesvári,
(1998); Tsitsiklis, (1994); Jaakkola et al., (1994)). Leveraging the toolkit
of concentration inequalities, a number of recent papers have shifted
attention towards understanding the performance in the non-asymptotic and
finite-time settings. A highly incomplete list includes Bhandari et al.,
(2018); Dalal et al., (2018); Lakshminarayanan and Szepesvari, (2018); Srikant
and Ying, (2019); Xu et al., (2019); Mou et al., (2020); Khamaru et al.,
(2020); Kaledin et al., (2020); Kearns and Singh, (1999); Bradtke and Barto,
(1996); Beck and Srikant, (2012); Strehl et al., (2006); Wainwright, 2019b ;
Gupta et al., (2019); Even-Dar and Mansour, (2003); Xu and Gu, (2019); Cai et
al., (2019); Azar et al., (2017); Jin et al., (2018); Shah and Xie, (2018);
Sidford et al., 2018a ; Chen et al., (2020); Qu and Wierman, (2020), a large
fraction of which is concerned with model-free algorithms.

The generative model (or simulator) adopted in this paper was first proposed
in Kearns and Singh, (1999), which has been invoked in Kearns et al., (2002);
Kakade, (2003); Azar et al., (2013); Kearns and Singh, (1999); Sidford et al.,
2018a ; Azar et al., (2012); Sidford et al., 2018b ; Wang, (2019); Wainwright,
2019b ; Khamaru et al., (2020); Pananjady and Wainwright, (2019); Agarwal et
al., (2019); Lattimore and Hutter, (2012), to name just a few. In particular,
Azar et al., (2013) developed the minimax lower bound on the sample complexity
$N={\Omega}\big{(}\frac{|\mathcal{S}||\mathcal{A}|\log(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma)^{3}\varepsilon^{2}}\big{)}$
necessary for finding an $\varepsilon$-optimal policy, and showed that, for
any $\varepsilon\in(0,1)$, a model-based approach (e.g. applying QVI or PI to
the empirical MDP) can estimate the optimal Q-function to within an
$\varepsilon$-accuracy given near-minimal samples. Note, however, that
directly translating this result to the policy guarantees leads to an
additional factor of $\frac{1}{1-\gamma}$ in estimation accuracy and of
$\frac{1}{(1-\gamma)^{2}}$ in sample complexity. In light of this, Azar et
al., (2013) further showed that a near-optimal sample complexity is possible
for policy learning if the sample size is at least on the order of
$\frac{|\mathcal{S}|^{2}|\mathcal{A}|}{(1-\gamma)^{2}}$ which, however, is no
longer sub-linear in the model complexity. A recent breakthrough Agarwal et
al., (2019) substantially improved the model-based guarantee with the aid of
auxiliary state-absorbing MDPs, extending the range of sample complexity to
$[\frac{|\mathcal{S}||\mathcal{A}|\log(|\mathcal{S}||\mathcal{A}|)}{(1-\gamma)^{2}},\infty)$.
Our analysis is motivated in part by Agarwal et al., (2019), but also relies
on several other novel techniques to complete the picture.

Finally, we remark that the construction of state-absorbing MDPs or state-
action-absorbing MDPs falls under the category of “leave-one-out” type
analysis, which is particularly effective in decoupling complicated
statistical dependency in various statistical estimation problems El Karoui,
(2015); Agarwal et al., (2019); Chen et al., (2019); Ma et al., (2020);
Pananjady and Wainwright, (2019). The application of such an analysis
framework to MDPs should be attributed to Agarwal et al., (2019). Other
applications to Markov chains include Chen et al., (2019); Pananjady and
Wainwright, (2019).

##  5 Analysis

This section presents the key ideas for proving our main results, following an
introduction of some convenient matrix notation.

###  5.1 Matrix notation and Bellman equations

It is convenient to present our proof based on some matrix notation for MDPs.
Denoting by
$\bm{e}_{1},\cdots,\bm{e}_{|\mathcal{S}|}\in\mathbb{R}^{|\mathcal{S}|}$ the
standard basis vectors, we can define:

  * •

$\bm{r}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$: a vector representing the
reward function $r$ (so that $r_{(s,a)}=r(s,a)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$).

  * •

$\bm{V}^{\pi}\in\mathbb{R}^{|\mathcal{S}|}$: a vector representing the value
function $V^{\pi}$ (so that ${V}^{\pi}_{s}={V}^{\pi}(s)$ for all
$s\in\mathcal{S}$).

  * •

$\bm{Q}^{\pi}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$: a vector
representing the Q-function $Q^{\pi}$ (so that
${Q}^{\pi}_{(s,a)}={Q}^{\pi}(s,a)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$).

  * •

$\bm{V}^{\star}\in\mathbb{R}^{|\mathcal{S}|}$ and
$\bm{Q}^{\star}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$: representing the
optimal value function $V^{\star}$ and optimal Q-function $Q^{\star}$.

  * •

$\bm{P}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}|}$: a
matrix representing the probability transition kernel $P$, where the
$(s,a)$-th row of $\bm{P}$ is a probability vector representing
$P(\cdot|s,a)$. Denote $\bm{P}_{s,a}$ as the $(s,a)$-th row of the transition
matrix $\bm{P}$.

  * •

$\bm{\Pi}^{\pi}\in\\{0,1\\}^{|\mathcal{S}|\times|\mathcal{S}||\mathcal{A}|}$:
a projection matrix associated with a given policy $\pi$ taking the following
form

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

  * •

$\bm{P}^{\pi}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}||\mathcal{A}|}$
and $\bm{P}_{\pi}\in\mathbb{R}^{|\mathcal{S}|\times|\mathcal{S}|}$: two square
probability transition matrices induced by the policy $\pi$ over the state-
action pairs and the states respectively, defined by

${\bm{P}}^{\pi}:=\bm{P}{\bf\Pi}^{\pi}\qquad\text{and}\qquad{\bm{P}}_{\pi}:={\bf\Pi}^{\pi}\bm{P}.$
(16)

  * •

$\bm{r}_{\pi}\in\mathbb{R}^{|\mathcal{S}|}$: a reward vector restricted to the
actions chosen by the policy $\pi$, namely, $r_{\pi}(s)=r(s,\pi(s))$ for all
$s\in\mathcal{S}$ (or simply, $\bm{r}_{\pi}=\bm{\Pi}^{\pi}\bm{r}$).

Armed with the above matrix notation, we can write, for any policy $\pi$, the
Bellman consistency equation as

$\bm{Q}^{\pi}=\bm{r}+\gamma\bm{P}\bm{V}^{\pi}=\bm{r}+\gamma{\bm{P}}^{\pi}\bm{Q}^{\pi},$
(17)

which implies that

$\displaystyle\bm{Q}^{\pi}=(\bm{I}-\gamma{\bm{P}}^{\pi})^{-1}\bm{r};$ (18)
$\displaystyle\bm{V}^{\pi}=\bm{r}_{\pi}+\gamma{\bm{P}}_{\pi}$
$\displaystyle\bm{V}^{\pi}\qquad\text{and}\qquad\bm{V}^{\pi}=(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\bm{r}_{\pi}.$
(19)

For a vector $\bm{V}=[V_{i}]_{1\leq
i\leq|\mathcal{S}|}\in\mathbb{R}^{|\mathcal{S}|}$, we define the vector
$\mathsf{Var}_{\bm{P}}(\bm{V})\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|}$
whose entries are given by

$\displaystyle\forall(s,a)\in\mathcal{S}\times\mathcal{A},\qquad\big{[}\mathsf{Var}_{\bm{P}}(\bm{V})\big{]}_{(s,a)}:=\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V_{s^{\prime}}^{2}-\Big{(}\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)V_{s^{\prime}}\Big{)}^{2},$

i.e. the variance of $\bm{V}$ w.r.t. $P(\cdot|s,a)$. This can be expressed
using our matrix notation as follows

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

Similarly, for any given policy $\pi$ we define

$\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})=\bm{\Pi}^{\pi}\mathsf{Var}_{\bm{P}}(\bm{V})=\bm{P}_{\pi}(\bm{V}\circ\bm{V})-(\bm{P}_{\pi}\bm{V})\circ(\bm{P}_{\pi}\bm{V})\in\mathbb{R}^{|\mathcal{S}|}.$

We shall also define $\widehat{\bm{V}}^{\pi}$, $\widehat{\bm{Q}}^{\pi}$,
$\widehat{\bm{V}}^{\star}$, $\widehat{\bm{Q}}^{\star}$, $\widehat{\bm{P}}$,
$\widehat{\bm{P}}^{\pi}$, $\widehat{\bm{P}}_{\pi}$,
$\mathsf{Var}_{\widehat{\bm{P}}}(\bm{V})$,
$\mathsf{Var}_{\widehat{\bm{P}}_{\pi}}(\bm{V})$ w.r.t. the empirical MDP
$\widehat{\mathcal{M}}$ in an analogous fashion.

###  5.2 Analysis: model-based policy evaluation

We start with the simpler task of policy evaluation, which also plays a
crucial role in the analysis of planning. To establish our guarantees in
Theorem 2, we aim to prove the following result. Here, we recall that the true
value function under a policy $\pi$ and the model-based empirical estimate are
given respectively by

$\displaystyle\bm{V}^{\pi}=(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\bm{r}_{\pi}\qquad\text{and}\qquad\widehat{\bm{V}}^{\pi}=(\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi})^{-1}\bm{r}_{\pi}.$
(20)

######  Lemma 1.

Fix any policy $\pi$. Consider any $0<\delta<1$, and suppose
$N\geq\frac{32e^{2}}{1-\gamma}\log\big{(}\frac{4|\mathcal{S}|\log(\frac{e}{1-\gamma})}{\delta}\big{)}$.
Then with probability at least $1-\delta$, the vectors defined in (20) obey

$\displaystyle\big{\|}\widehat{\bm{V}}^{\pi}-\bm{V}^{\pi}\big{\|}_{\infty}$
$\displaystyle\leq
4\gamma\sqrt{\frac{2\log\big{(}\frac{4|\mathcal{S}|\log(\frac{e}{1-\gamma})}{\delta}\big{)}}{N}}\Big{\|}(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{\pi}\big{]}}\Big{\|}_{\infty}+\frac{2\gamma\log\big{(}\frac{4|\mathcal{S}|\log(\frac{e}{1-\gamma})}{\delta}\big{)}}{(1-\gamma)N}\big{\|}\bm{V}^{\pi}\big{\|}_{\infty}$
$\displaystyle\leq
6\sqrt{\frac{2\log\big{(}\frac{4|\mathcal{S}|\log(\frac{e}{1-\gamma})}{\delta}\big{)}}{N(1-\gamma)^{3}}}.$
(21)

###### Proof.

The key proof idea is to resort to a high-order successive expansion of
$\widehat{\bm{V}}^{\pi}-\bm{V}^{\pi}$, followed by fine-grained analysis of
each term up to a certain logarithmic order. See Appendix B.1. ∎

Clearly, Theorem 2 is a straightforward consequence of Lemma 1. Further, we
strengthen the result by providing an additional instance-dependent bound (see
the first line of (21) that depends on the true instance
$\bm{P}_{\pi},\bm{V}^{\pi}$), which is often tighter than the worst-case bound
stated in the second line of (21). Our contribution can be better understood
when compared with Pananjady and Wainwright, (2019). Assuming that there is no
noise in the rewards, our instance-dependent guarantee matches Pananjady and
Wainwright, (2019, Theorem 1(a)) up to some $\log\log\frac{1}{1-\gamma}$
factor, while being capable of covering the full sample size range
$N\geq\widetilde{\Omega}(\frac{1}{1-\gamma})$. In contrast, Pananjady and
Wainwright, (2019, Theorem 1) is only valid when
$N\geq\widetilde{\Omega}(\frac{1}{(1-\gamma)^{2}}$).

##### Proof ideas.

We now briefly and informally describe the key proof ideas. As a starting
point, the elementary identities (20) allow us to obtain

$\displaystyle\widehat{\bm{V}}^{\pi}-\bm{V}^{\pi}$
$\displaystyle=\big{(}\bm{I}-\gamma\widehat{\bm{P}}_{\pi}\big{)}^{-1}\bm{r}_{\pi}-\bm{V}^{\pi}$
$\displaystyle=\big{(}\bm{I}-\gamma\widehat{\bm{P}}_{\pi}\big{)}^{-1}\big{(}\bm{I}-\gamma\bm{P}_{\pi}\big{)}\bm{V}^{\pi}-\big{(}\bm{I}-\gamma\widehat{\bm{P}}_{\pi}\big{)}^{-1}\big{(}\bm{I}-\gamma\widehat{\bm{P}}_{\pi}\big{)}\bm{V}^{\pi}$
$\displaystyle=\gamma\big{(}\bm{I}-\gamma\widehat{\bm{P}}_{\pi}\big{)}^{-1}\big{(}\widehat{\bm{P}}_{\pi}-\bm{P}_{\pi}\big{)}\bm{V}^{\pi}.$
(22)

Due to the complicated dependency between
$(\bm{I}-\gamma\widehat{\bm{P}}_{\pi})^{-1}$ and
$\big{(}\widehat{\bm{P}}_{\pi}-\bm{P}_{\pi}\big{)}\bm{V}^{\pi}$, a natural
strategy is to control these two terms separately and then to combine bounds;
see Agarwal et al., (2019, Lemma 5) for an introduction. This simple approach,
however, leads to sub-optimal statistical guarantees.

In order to refine the statistical analysis, we propose to further expand (22)
in a similar way to deduce

$\displaystyle\eqref{eq:V-basic-expansion}$
$\displaystyle=\gamma\big{(}\bm{I}-\gamma\bm{P}_{\pi}\big{)}^{-1}\big{(}\widehat{\bm{P}}_{\pi}-\bm{P}_{\pi}\big{)}\bm{V}^{\pi}+\gamma\left\\{\big{(}\bm{I}-\gamma\widehat{\bm{P}}_{\pi}\big{)}^{-1}-\big{(}\bm{I}-\gamma\bm{P}_{\pi}\big{)}^{-1}\right\\}\big{(}\widehat{\bm{P}}_{\pi}-\bm{P}_{\pi}\big{)}\bm{V}^{\pi}$
$\displaystyle=\gamma\big{(}\bm{I}-\gamma\bm{P}_{\pi}\big{)}^{-1}\big{(}\widehat{\bm{P}}_{\pi}-\bm{P}_{\pi}\big{)}\bm{V}^{\pi}+\gamma^{2}\big{(}\bm{I}-\gamma\widehat{\bm{P}}_{\pi}\big{)}^{-1}\big{(}\widehat{\bm{P}}_{\pi}-\bm{P}_{\pi}\big{)}\big{(}\bm{I}-\gamma\bm{P}_{\pi}\big{)}^{-1}\big{(}\widehat{\bm{P}}_{\pi}-\bm{P}_{\pi}\big{)}\bm{V}^{\pi},$
(23)

where the last line holds due to the same reason as (22) (basically it can be
seen by replacing $\bm{r}_{\pi}$ with
$\big{(}\widehat{\bm{P}}_{\pi}-\bm{P}_{\pi}\big{)}\bm{V}^{\pi}$ in (22)). This
can be viewed as a “second-order” expansion, with (22) being a “first-order”
counterpart. The advantage is that: the first term in (23) becomes easier to
cope with than its counterpart (22), owing to the independence between
$(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}$ and
$\big{(}\widehat{\bm{P}}_{\pi}-\bm{P}_{\pi}\big{)}\bm{V}^{\pi}$. However, the
second term in (23) remains difficult to control optimally. To remedy this
issue, we shall continue to expand it to higher order (up to some logarithmic
order), which eventually allows for optimal control of the estimation error.

Another crucial issue is that: in order to obtain fine-grained analyses on
each term in the expansion (except for the first-order term), a common
approach is to combine the Bernstein inequality with a classical entrywise
bound on a quantity taking the form
$(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\sqrt{\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})}$
(which dates back to Azar et al., (2013)). Such a classical bound in prior
literature, however, is not sufficiently tight for our purpose, which calls
for refinement; see Lemma 8. Details are deferred to Appendix B.1.

###  5.3 Analysis: model-based planning

This subsection moves on to establishing our theory for model-based planning
(cf. Theorem 1) and outlines the key ideas. In what follows, we shall start by
analyzing the unperturbed version, which will elucidate the role of reward
perturbation in our analysis.

We first make note of the following elementary decomposition:

$\displaystyle{\bm{V}}^{\star}-\bm{V}^{\widehat{\pi}^{\star}}$
$\displaystyle=\big{(}\widehat{\bm{V}}^{\widehat{\pi}^{\star}}-\bm{V}^{\widehat{\pi}^{\star}}\big{)}+\big{(}\widehat{\bm{V}}^{{\pi}^{\star}}-\widehat{\bm{V}}^{\widehat{\pi}^{\star}}\big{)}+\big{(}{\bm{V}}^{\star}-\widehat{\bm{V}}^{{\pi}^{\star}}\big{)}$
$\displaystyle\leq\big{(}\widehat{\bm{V}}^{\widehat{\pi}^{\star}}-\bm{V}^{\widehat{\pi}^{\star}}\big{)}+\big{(}\bm{V}^{{\pi}^{\star}}-\widehat{\bm{V}}^{{\pi}^{\star}}\big{)},$
(24)

where the inequality follows from the optimality of $\widehat{\pi}^{\star}$
w.r.t. $\widehat{\bm{V}}$ (so that
$\widehat{\bm{V}}^{{\pi}^{\star}}\leq\widehat{\bm{V}}^{\widehat{\pi}^{\star}}$)
and the definition $\bm{V}^{\star}=\bm{V}^{{\pi}^{\star}}$. This leaves us
with two terms to control.

##### Step 1: bounding
$\|\bm{V}^{{\pi}^{\star}}-\widehat{\bm{V}}^{{\pi}^{\star}}\|_{\infty}$.

Given that $\pi^{\star}$ is independent of the data, we can carry out this
step using Lemma 1. Specifically, taking $\pi=\pi^{\star}$ in Lemma 1 yields
that, with probability at least $1-\delta$,

$\displaystyle\big{\|}\widehat{\bm{V}}^{\pi^{\star}}-\bm{V}^{\pi^{\star}}\big{\|}_{\infty}$
$\displaystyle\leq
6\sqrt{\frac{2\log\big{(}\frac{4|\mathcal{S}|\log\frac{e}{1-\gamma}}{\delta}\big{)}}{N(1-\gamma)^{3}}}.$
(25)

##### Step 2: bounding
$\|\widehat{\bm{V}}^{\widehat{\pi}^{\star}}-\bm{V}^{\widehat{\pi}^{\star}}\|_{\infty}$.

Extending the result in Step 1 to
$\|\widehat{\bm{V}}^{\widehat{\pi}^{\star}}-\bm{V}^{\widehat{\pi}^{\star}}\|_{\infty}$
is considerably more challenging, primarily due to the complicated statistical
dependency between
$(\bm{V}^{\widehat{\pi}^{\star}},\widehat{\bm{V}}^{\widehat{\pi}^{\star}})$
and the data matrix $\widehat{\bm{P}}$. The recent work Agarwal et al., (2019)
developed a clever “leave-one-out” type argument by constructing some
auxiliary state-absorbing MDPs to decouple the statistical dependency when
$\varepsilon<1/\sqrt{1-\gamma}$. However, their argument falls short of
accommodating the full range of $\varepsilon$. To address this challenge, our
analysis consists of the following two steps, both of which require new ideas
beyond Agarwal et al., (2019).

  * •

Decoupling statistical dependency between $\widehat{\pi}^{\star}$ and
$\widehat{\bm{P}}$. Instead of attempting to decouple the statistical
dependency between $\widehat{\bm{V}}^{\widehat{\pi}^{\star}}$ and
$\widehat{\bm{P}}$ as in Agarwal et al., (2019), we focus on decoupling the
statistical dependency between the policy $\widehat{\pi}^{\star}$ and
$\widehat{\bm{P}}$. If this can be achieved, then the proof strategy adopted
in Step 1 for a fixed policy becomes applicable (see Section 5.3.1). A key
ingredient of this step lies in the construction of a collection of auxiliary
state-action-absorbing MDPs (motivated by Agarwal et al., (2019)), which
allows us to get hold of
$\|\bm{V}^{\widehat{\pi}^{\star}}-\widehat{\bm{V}}^{\widehat{\pi}^{\star}}\|_{\infty}$.
See Section 5.3.2 for details, with a formal bound delivered in Lemma 5.

  * •

Tie-breaking via reward perturbation. A shortcoming of the above-mentioned
approach, however, is that it relies crucially on the separability of
$\widehat{\pi}^{\star}$ from other policies; in other words, the proof might
fail if $\widehat{\pi}^{\star}$ is non-unique or not sufficiently
distinguishable from others. Consequently, it remains to ensure that the
optimal policy $\widehat{\pi}^{\star}$ stands out from all the rest for all
MDPs of interest. As it turns out, this can be guaranteed with high
probability by slightly perturbing the reward function so as to break the
ties. See Section 5.3.3 for details.

In the sequel, we shall flesh out these key ideas.

####  5.3.1 Value function estimation for a policy obeying Bernstein-type
conditions

Before discussing how to decouple statistical dependency, we record a useful
result that plays an important role in the analysis. Specifically, Lemma 1 can
be generalized beyond the family of fixed policies (namely, those independent
of $\widehat{\bm{P}}$), as long as a certain Bernstein-type condition — to be
formalized in (29) — is satisfied. To make it precise, we need to introduce a
set of auxiliary vectors as follows

$\displaystyle\begin{array}[]{ll}\bm{r}^{(0)}:=\bm{r}_{\pi},&\bm{V}^{(0)}:=(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\bm{r}^{(0)},\\\
\bm{r}^{(l)}:=\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(l-1)}\big{]}},&\bm{V}^{(l)}:=(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\bm{r}^{(l)},\qquad
l\geq 1.\end{array}$ (28)

Our generalization of Lemma 1 is as follows, which does not require
statistical independence between the policy $\pi$ and the data
$\widehat{\bm{P}}$. Here, we remind the reader of the notation
$|\bm{z}|:=[|z_{1}|,\cdots,|z_{n}|]^{\top}$ and
$\sqrt{\bm{z}}:=[\sqrt{z_{1}},\cdots,\sqrt{z_{n}}]^{\top}$ for any vector
$\bm{z}\in\mathbb{R}^{n}$.

######  Lemma 2.

Suppose that there exists some quantity $\beta_{1}>0$ such that
$\\{\bm{V}^{(l)}\\}$ (cf. (28)) obeys

$\left|\big{(}{\widehat{\bm{P}}}_{\pi}-{\bm{P}}_{\pi}\big{)}\bm{V}^{(l)}\right|\leq\sqrt{\frac{\beta_{1}}{N}}\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(l)}\big{]}}+\frac{\beta_{1}\left\|\bm{V}^{(l)}\right\|_{\infty}}{N}\bm{1},\qquad\text{for
all }0\leq l\leq\log\Big{(}\frac{e}{1-\gamma}\Big{)}.$ (29)

Suppose that $N>\frac{16e^{2}}{1-\gamma}\beta_{1}$. Then the vectors
$\bm{V}^{\pi}=(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\bm{r}_{\pi}$ and
$\widehat{\bm{V}}^{\pi}=(\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi})^{-1}\bm{r}_{\pi}$
satisfy

$\displaystyle\big{\|}\widehat{\bm{V}}^{\pi}-\bm{V}^{\pi}\big{\|}_{\infty}\leq\frac{6}{1-\gamma}\sqrt{\frac{\beta_{1}}{N(1-\gamma)}}.$
(30)

While the Bernstein-type condition (29) clearly holds for some reasonably
small $\beta_{1}$ if $\pi$ is independent of $\widehat{\bm{P}}$, it might
remain valid if $\pi$ exhibits fairly “weak” statistical dependency on the
data samples. This is a key step that paves the way for our subsequent
analysis of $\widehat{\pi}^{\star}$.

####  5.3.2 Decoupling statistical dependency via $(s,a)$-absorbing MDPs

We are now positioned to demonstrate how to control
$\big{\|}\widehat{\bm{V}}^{\widehat{\pi}^{\star}}-\bm{V}^{\widehat{\pi}^{\star}}\big{\|}_{\infty}$
w.r.t. the optimal policy $\widehat{\pi}^{\star}$ to $\widehat{\bm{V}}.$ A
crucial technical challenge lies in how to decouple the complicated
statistical dependency between the optimal policy $\widehat{\pi}^{\star}$ and
the $\widehat{\bm{V}}^{\star}$ (which heavily relies on the data samples).
Towards this, we resort to a leave-one-row-out argument built upon a
collection of auxiliary MDPs, largely motivated by the novel construction in
(Agarwal et al.,, 2019, Section 4.2). In comparison to Agarwal et al., (2019)
that introduces state-absorbing MDPs (so that a state $s$ is absorbing
regardless of the subsequent actions chosen), our construction is a set of
state-action-absorbing MDPs, in which a state $s$ is absorbing only when a
designated action $a$ is always executed at the state $s$.

##### Construction of $(s,a)$-absorbing MDPs.

For each state-action pair $(s,a)$ and each scalar $u$ with $|u|\leq
1/(1-\gamma)$, we construct an auxiliary MDP $\mathcal{M}_{s,a,u}$ — it is
identical to the original $\mathcal{M}$ except that it is absorbing in state
$s$ if we always choose action $a$ in state $s$. More specifically, the
probability transition kernel associated with $\mathcal{M}_{s,a,u}$ (denoted
by $P_{\mathcal{M}_{s,a,u}}$) can be specified by

$\displaystyle\begin{array}[]{rll}P_{\mathcal{M}_{s,a,u}}(s\mid s,a)&=1,\\\
P_{\mathcal{M}_{s,a,u}}(s^{\prime}\mid s,a)&=0,&\text{for all }s^{\prime}\neq
s,\\\ P_{\mathcal{M}_{s,a,u}}(\cdot\mid
s^{\prime},a^{\prime})&=P_{\mathcal{M}}(\cdot\mid
s^{\prime},a^{\prime}),&\text{for all
}(s^{\prime},a^{\prime})\neq(s,a),\end{array}$ (34)

where $P_{\mathcal{M}}$ is the probability transition kernel w.r.t. the
original $\mathcal{M}.$ Meanwhile, the instant reward received at $(s,a)$ in
$\mathcal{M}_{s,a,u}$ is set to be $u$, while the rewards at all other state-
action pairs stay unchanged. We can define $\widehat{\mathcal{M}}_{s,a,u}$
analogously (so that its probability transition matrix is identical to
$\widehat{\bm{P}}$ except that the $(s,a)$-th row becomes absorbing). The main
advantage of this construction is that: for any fixed $u$, the MDP
$\widehat{\mathcal{M}}_{s,a,u}$ is statistically independent of
$\widehat{\bm{P}}_{s,a}$ (the row of $\widehat{\bm{P}}$ corresponding to the
state-action pair $(s,a)$, determined by the samples collected for the $(s,a)$
pair).

To streamline notation, we let ${\bm{Q}}^{\pi}_{s,a,u}$ represent the
Q-function of $\mathcal{M}_{s,a,u}$ under a policy $\pi$, denote by
${\pi}^{\star}_{s,a,u}$ the optimal policy associated with
$\mathcal{M}_{s,a,u}$, and let ${\bm{Q}}^{\star}_{s,a,u}$ be the Q-function
under this optimal policy ${\pi}^{\star}_{s,a,u}$. The notation
${\bm{V}}^{\pi}_{s,a,u}$ and ${\bm{V}}^{\star}_{s,a,u}$ regarding value
functions, as well as their counterparts (i.e.
$\widehat{\bm{Q}}^{\pi}_{s,a,u}$, $\widehat{\bm{Q}}^{\star}_{s,a,u}$,
$\widehat{\bm{V}}^{\pi}_{s,a,u}$, $\widehat{\bm{V}}^{\star}_{s,a,u}$,
$\widehat{\pi}^{\star}_{s,a,u}$) in the empirical MDP $\widehat{\mathcal{M}}$,
can be defined in an analogous fashion.

######  Remark 3.

The careful reader will remark that the instant reward $u$ is constrained to
reside within $[-\frac{1}{1-\gamma},\frac{1}{1-\gamma}]$ rather than the usual
range $[0,1]$. Fortunately, none of the subsequent steps that involve $u$
requires $u$ to lie within $[0,1]$.

##### Intimate connections between the auxiliary MDPs and the original MDP.

In the following, we introduce a result that connects the Q-function and the
value function of the absorbing MDP with those of the original MDP. The idea
is motivated by Agarwal et al., (2019, Lemma 7).

######  Lemma 3.

Setting $u^{\star}:=r(s,a)+\gamma(\bm{P}{\bm{V}}^{\star})_{s,a}-\gamma
V^{\star}(s)$, one has

$\displaystyle{\bm{Q}}^{\star}_{s,a,u^{\star}}={\bm{Q}}^{\star}\qquad\text{and}\qquad{\bm{V}}^{\star}_{s,a,u^{\star}}={\bm{V}}^{\star}.$
(35)

###### Proof.

See Appendix B.2. ∎

######  Remark 4.

Lemma 3 does not rely on the particular form of $\bm{P}$, and can be directly
generalized to the empirical model $\widehat{\bm{P}}$ and the auxiliary MDPs
built upon $\widehat{\bm{P}}.$

In words, by properly setting the instant reward $u=u^{\star}$ (which can be
easily shown to reside within $[-\frac{1}{1-\gamma},\frac{1}{1-\gamma}]$), one
guarantees that the $(s,a)$-absorbing MDP and the original MDP have the same
Q-function and value function under the respective optimal policies.

##### Representing $\widehat{\pi}^{\star}$ via a small set of policies
independent of $\widehat{\bm{P}}_{s,a}$.

With Lemma 3 in place, it is tempting to use
$\widehat{\mathcal{M}}_{s,a,\widehat{u}^{\star}}$ with
$\widehat{u}^{\star}:=r(s,a)+\gamma(\widehat{\bm{P}}\widehat{\bm{V}}^{\star})_{s,a}-\gamma\widehat{V}^{\star}(s)$
to replace the original $\widehat{\mathcal{M}}$. The rationale is simple:
given that the probability transition matrix of
$\widehat{\mathcal{M}}_{s,a,\widehat{u}^{\star}}$ does not rely upon
$\widehat{\bm{P}}_{s,a}$, the statistical dependency between
$\widehat{\mathcal{M}}_{s,a,\widehat{u}^{\star}}$ and $\widehat{\bm{P}}_{s,a}$
is now fully embedded into a single parameter $\widehat{u}^{\star}$. This
motivates us to decouple the statistical dependency effectively by
constructing an epsilon-net (see, e.g., Vershynin, (2018)) w.r.t. this single
parameter. The aim is to locate a point $u_{0}$ over a small fixed set such
that _(i)_ it is close to $\widehat{u}^{\star}$, and _(ii)_ its associated
optimal policy is identical to the original optimal policy
$\widehat{\pi}^{\star}$.

It turns out that this aim can be accomplished as long as the original
Q-function $\widehat{\bm{Q}}^{\star}$ satisfies a sort of separation condition
(which indicates that there is no tie when it comes to the optimal policy). To
make it precise, given any $0<\omega<1$, our separation condition is
characterized through the following event

$\displaystyle\mathcal{B}_{\omega}:=\Big{\\{}\widehat{Q}^{\star}(s,\widehat{\pi}^{\star}(s))-\max_{a:a\neq\widehat{\pi}^{\star}(s)}\widehat{Q}^{\star}(s,a)\geq\omega\leavevmode\nobreak\
\leavevmode\nobreak\ \text{for all }s\in\mathcal{S}\Big{\\}}.$ (36)

Clearly, on the event $\mathcal{B}_{\omega}$, the optimal policy
$\widehat{\pi}^{\star}$ is unique, since for each $s$ the action
$\widehat{\pi}^{\star}(s)$ results in a strictly higher Q-value compared to
any other action. With this separation condition in mind, our result is stated
below. Here and throughout, we define an epsilon-net of the interval
$[-\frac{1}{1-\gamma},\frac{1}{1-\gamma}]$ as follows

$\displaystyle\mathcal{N}_{\epsilon}:=\big{\\{}-n_{\epsilon}\epsilon,\ldots,-\epsilon,0,\epsilon,\ldots,n_{\epsilon}\epsilon\big{\\}},\qquad\text{for
the largest integer }n_{\epsilon}\text{ obeying
}n_{\epsilon}\epsilon<\frac{1}{1-\gamma},$ (37)

which has cardinality at most $\frac{2}{(1-\gamma)\epsilon}$.

######  Lemma 4.

Consider any $\omega>0$, and suppose the event $\mathcal{B}_{\omega}$ (cf.
(36)) holds. Then for any pair $(s,a)\in\mathcal{S}\times\mathcal{A}$, there
exists a point $u_{0}\in\mathcal{N}_{(1-\gamma)\omega/4}$, such that

$\displaystyle\widehat{\pi}^{\star}=\widehat{\pi}^{\star}_{s,a,u_{0}}.$ (38)

###### Proof.

See Appendix B.3. ∎

##### Deriving an optimal error bound under the separation condition.

Armed with the above bounds, we are ready to derive the desired error bound by
combining Lemma 2 and Lemma 4.

######  Lemma 5.

Given $0<\omega<1$ and $\delta>0$, suppose that $\mathcal{B}_{\omega}$
(defined in (36)) occurs with probability at least $1-\delta$. Then with
probability at least $1-3\delta$,

$\displaystyle\big{\|}\widehat{\bm{V}}^{\widehat{\pi}^{\star}}-\bm{V}^{\widehat{\pi}^{\star}}\big{\|}_{\infty}$
$\displaystyle\leq
6\sqrt{\frac{2\log\big{(}\frac{32|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\omega\delta}\big{)}}{N(1-\gamma)^{3}}}\quad\text{and}\quad{\bm{V}}^{\star}-\bm{V}^{\widehat{\pi}^{\star}}\leq
12\sqrt{\frac{2\log\big{(}\frac{32|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\omega\delta}\big{)}}{N(1-\gamma)^{3}}}\,\bm{1},$
(39)

provided that
$N\geq\frac{c_{0}\log\big{(}\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)\delta\omega}\big{)}}{1-\gamma}$
for some sufficiently large constant $c_{0}>0$.

###### Proof.

See Appendix B.4. ∎

####  5.3.3 A tie-breaking argument

Unfortunately, the separation condition specified in $\mathcal{B}_{\omega}$
(cf. (36)) does not always hold. In order to accommodate all possible MDPs of
interest without imposing such a special separation condition, we put forward
a perturbation argument allowing one to generate a new MDP that (i) satisfies
the separation condition, and that (ii) is sufficiently close to the original
MDP.

Specifically, let us represent the proposed reward perturbation (6) in a
vector form as follows

$\displaystyle\bm{r}_{\mathrm{p}}:=\bm{r}+\bm{\zeta},$ (40)

where $\bm{\zeta}=[\,\zeta(s,a)\,]_{(s,a)\in|\mathcal{S}|\times|\mathcal{A}|}$
is an $|\mathcal{S}||\mathcal{A}|$-dimensional vector composed of independent
entries with each
$\zeta(s,a)\overset{\mathrm{i.i.d.}}{\sim}\mathsf{Unif}(0,\xi)$. We aim to
show that: by randomly perturbing the reward function, we can “break the tie”
in the Q-function and ensure sufficient separation of Q-values associated with
different actions.

To formalize our result, we find it convenient to introduce additional
notation. Denote by $\pi_{\mathrm{p}}^{\star}$ the optimal policy of the MDP
$\mathcal{M}_{\mathrm{p}}=(\mathcal{S},\mathcal{A},\bm{P},\bm{r}_{\mathrm{p}},\gamma)$,
and $Q_{\mathrm{p}}^{\star}$ its optimal state-action value function. We can
define $\widehat{Q}_{\mathrm{p}}^{\star}$ and
$\widehat{\pi}_{\mathrm{p}}^{\star}$ analogously for the MDP
$\widehat{\mathcal{M}}_{\mathrm{p}}=(\mathcal{S},\mathcal{A},\widehat{\bm{P}},\bm{r}_{\mathrm{p}},\gamma)$.
Our result is phrased as follows.

######  Lemma 6.

Consider the perturbed reward vector defined in expression (40). With
probability at least $1-\delta$,

$\displaystyle\forall(s,a)\in\mathcal{S}\times\mathcal{A}\text{ with
}a\neq\pi_{\mathrm{p}}^{\star}(s):\qquad
Q_{{\mathrm{p}}}^{\star}(s,\pi_{\mathrm{p}}^{\star}(s))-Q_{{\mathrm{p}}}^{\star}(s,a)>\frac{\xi\delta(1-\gamma)}{4|\mathcal{S}||\mathcal{A}|^{2}}.$
(41)

This result holds unchanged if
$(Q_{{\mathrm{p}}}^{\star},\pi_{\mathrm{p}}^{\star})$ is replaced by
$(\widehat{Q}_{{\mathrm{p}}}^{\star},\widehat{\pi}_{\mathrm{p}}^{\star})$.

###### Proof.

See Appendix B.5. ∎

Lemma 6 reveals that at least a polynomially small degree of separation
($\omega=\frac{\xi\delta(1-\gamma)}{4|\mathcal{S}||\mathcal{A}|^{2}}$) arises
upon random perturbation (with size $\xi$) of the reward function. As we shall
see momentarily, this level of separation suffices for our purpose.

####  5.3.4 Proof of Theorem 1

Let us consider the randomly perturbed reward function as in (40). For any
policy $\pi$, we denote by $\bm{V}^{\pi}_{{\mathrm{p}}}$ (resp.
$\widehat{\bm{V}}^{\pi}_{{\mathrm{p}}}$) the corresponding value function
vector in the MDP with probability transition matrix $\bm{P}$ (resp.
$\widehat{\bm{P}}$) and reward vector $\bm{r}_{\mathrm{p}}$. Note that
${\pi}_{\mathrm{p}}^{\star}$ (resp. $\widehat{\pi}_{\mathrm{p}}^{\star}$)
denotes the optimal policy that maximizes ${\bm{V}}^{\pi}_{{\mathrm{p}}}$
(resp. $\widehat{\bm{V}}^{\pi}_{{\mathrm{p}}}$).

In view of Lemma 6, with probability at least $1-\delta$ one has the
separation

$\displaystyle\Big{|}\widehat{Q}_{{\mathrm{p}}}^{\star}(s,\widehat{\pi}_{\mathrm{p}}^{\star}(s))-\widehat{Q}_{{\mathrm{p}}}^{\star}(s,a)\Big{|}>\frac{\xi\delta(1-\gamma)}{4|\mathcal{S}||\mathcal{A}|^{2}}$
(42)

uniformly over all $s$ and $a\neq\widehat{\pi}_{\mathrm{p}}^{\star}(s)$. With
this separation in place, taking
$\omega:=\frac{\xi\delta(1-\gamma)}{4|\mathcal{S}||\mathcal{A}|^{2}}$ in Lemma
5 yields

$\displaystyle\left\|\bm{V}_{\mathrm{p}}^{{\pi}_{\mathrm{p}}^{\star}}-\bm{V}_{\mathrm{p}}^{\widehat{\pi}_{\mathrm{p}}^{\star}}\right\|_{\infty}\leq
12\sqrt{\frac{2\log\big{(}\frac{128|\mathcal{S}|^{2}|\mathcal{A}|^{3}}{(1-\gamma)^{4}\xi\delta^{2}}\big{)}}{N(1-\gamma)^{3}}}.$
(43)

In addition, the value functions under any policy $\pi$ obeys

$\bm{V}^{\pi}-\bm{V}_{\mathrm{p}}^{\pi}={\bf\Pi}^{\pi}\Big{(}(\bm{I}-\bm{P}^{\pi})^{-1}\bm{r}-(\bm{I}-\bm{P}^{\pi})^{-1}\bm{r}_{\mathrm{p}}\Big{)},$

which taken collectively with the facts
$\|\bm{r}-\bm{r}_{\mathrm{p}}\|_{\infty}\leq\xi$ and
$\|(\bm{I}-\gamma\bm{P}^{\pi})^{-1}\|_{1}\leq\frac{1}{1-\gamma}$ gives

$\displaystyle\big{\|}\bm{V}^{\pi}-\bm{V}_{\mathrm{p}}^{\pi}\big{\|}_{\infty}$
$\displaystyle\leq\|(\bm{I}-\gamma\bm{P}^{\pi})^{-1}\|_{1}\|\bm{r}-\bm{r}_{\mathrm{p}}\|_{\infty}\leq\frac{1}{1-\gamma}\xi.$

Specializing the above relation to $\pi^{\star}$ and
$\widehat{\pi}^{\star}_{\mathrm{p}}$ gives

$\displaystyle\big{\|}\bm{V}^{\pi^{\star}}-\bm{V}_{\mathrm{p}}^{\pi^{\star}}\big{\|}_{\infty}\leq\frac{1}{1-\gamma}\xi\qquad{\text{and}}\qquad\big{\|}\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}-\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}_{\mathrm{p}}\big{\|}_{\infty}\leq\frac{1}{1-\gamma}\xi.$
(44)

Now let us consider the following decomposition

$\displaystyle\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}-{\bm{V}}^{\star}$
$\displaystyle=\big{(}\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}-\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}_{\mathrm{p}}\big{)}+\big{(}\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}_{\mathrm{p}}-\bm{V}^{{\pi}^{\star}_{\mathrm{p}}}_{\mathrm{p}}\big{)}+\big{(}\bm{V}^{{\pi}^{\star}_{\mathrm{p}}}_{\mathrm{p}}-\bm{V}^{{\pi}^{\star}}_{\mathrm{p}}\big{)}+\big{(}\bm{V}^{{\pi}^{\star}}_{\mathrm{p}}-{\bm{V}}^{\star}\big{)}$
$\displaystyle\geq\big{(}\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}-\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}_{\mathrm{p}}\big{)}+\big{(}\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}_{\mathrm{p}}-\bm{V}^{{\pi}^{\star}_{\mathrm{p}}}_{\mathrm{p}}\big{)}+\big{(}\bm{V}^{{\pi}^{\star}}_{\mathrm{p}}-{\bm{V}}^{\star}\big{)},$

where the last step follows from the optimality of
${\pi}^{\star}_{\mathrm{p}}$ w.r.t. $\bm{V}_{\mathrm{p}}$. Taking this
collectively with the inequalities (43) and (44), one shows that with
probability greater than $1-3\delta$,

$\displaystyle\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}-{\bm{V}}^{\star}\geq-\Bigg{(}\frac{2}{1-\gamma}\xi+12\sqrt{\frac{2\log\big{(}\frac{128|\mathcal{S}|^{2}|\mathcal{A}|^{3}}{\xi(1-\gamma)^{4}\delta^{2}}\big{)}}{N(1-\gamma)^{3}}}\Bigg{)}\,\bm{1}$

By taking
$\xi=\frac{(1-\gamma)\varepsilon}{3|\mathcal{S}|^{5}|\mathcal{A}|^{5}}$ and
$N\geq\frac{c_{0}\log\left(\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)\delta\varepsilon}\right)}{(1-\gamma)^{3}\varepsilon^{2}}$
for some constant $c_{0}>0$ large enough, we can ensure that
$\bm{0}\geq\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}-{\bm{V}}^{\star}\geq-\varepsilon\bm{1}$
as claimed. Regarding the Q-functions, the Bellman equation gives

$\displaystyle\bm{Q}^{\widehat{\pi}^{\star}_{\mathrm{p}}}-{\bm{Q}}^{\star}=\bm{r}+\gamma\bm{P}\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}-\big{(}\bm{r}+\gamma\bm{P}\bm{V}^{\star}\big{)}=\gamma\bm{P}(\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}-{\bm{V}}^{\star}).$

Consequently, one has

$\displaystyle\bm{Q}^{\widehat{\pi}^{\star}_{\mathrm{p}}}-{\bm{Q}}^{\star}\geq-\big{(}\gamma\|\bm{P}\|_{1}\|\bm{V}^{\widehat{\pi}^{\star}_{\mathrm{p}}}-{\bm{V}}^{\star}\|_{\infty}\big{)}\,\bm{1}\geq-\gamma\varepsilon\bm{1}.$

Finally, we demonstrate that both the empirical QVI and PI w.r.t.
$\widehat{\mathcal{M}}_{\mathrm{p}}$ are guaranteed to find
$\widehat{\pi}^{\star}_{\mathrm{p}}$ in a few iterations. Suppose for the
moment that we can obtain a policy $\pi_{k}$ obeying

$\displaystyle\|\widehat{\bm{Q}}_{\mathrm{p}}^{\pi_{k}}-\widehat{\bm{Q}}_{\mathrm{p}}^{\star}\|_{\infty}<\frac{\xi\delta(1-\gamma)}{8|\mathcal{S}||\mathcal{A}|^{2}}.$
(45)

Then for any $s\in\mathcal{S}$ and any action
$a\neq\widehat{\pi}_{\mathrm{p}}^{\star}(s)$ one has

$\displaystyle\widehat{\bm{Q}}_{\mathrm{p}}^{\pi_{k}}\big{(}s,\widehat{\pi}_{\mathrm{p}}^{\star}(s)\big{)}$
$\displaystyle-\widehat{\bm{Q}}_{\mathrm{p}}^{\pi_{k}}(s,a)$
$\displaystyle=\widehat{\bm{Q}}_{\mathrm{p}}^{\star}\big{(}s,\widehat{\pi}_{\mathrm{p}}^{\star}(s)\big{)}-\widehat{\bm{Q}}_{\mathrm{p}}^{\star}(s,a)+\Big{(}\widehat{\bm{Q}}_{\mathrm{p}}^{\pi_{k}}\big{(}s,\widehat{\pi}_{\mathrm{p}}^{\star}(s)\big{)}-\widehat{\bm{Q}}_{\mathrm{p}}^{\star}\big{(}s,\widehat{\pi}_{\mathrm{p}}^{\star}(s)\big{)}\Big{)}-\Big{(}\widehat{\bm{Q}}_{\mathrm{p}}^{\pi_{k}}(s,a)-\widehat{\bm{Q}}_{\mathrm{p}}^{\star}(s,a)\Big{)}$
$\displaystyle\geq\widehat{\bm{Q}}_{\mathrm{p}}^{\star}\big{(}s,\widehat{\pi}_{\mathrm{p}}^{\star}(s)\big{)}-\widehat{\bm{Q}}_{\mathrm{p}}^{\star}(s,a)-2\big{\|}\widehat{\bm{Q}}_{\mathrm{p}}^{\pi_{k}}-\widehat{\bm{Q}}_{\mathrm{p}}^{\star}\big{\|}_{\infty}$
$\displaystyle>\frac{\xi\delta(1-\gamma)}{4|\mathcal{S}||\mathcal{A}|^{2}}-2\cdot\frac{\xi\delta(1-\gamma)}{8|\mathcal{S}||\mathcal{A}|^{2}}=0,$

where the last line results from (42) and (45). In other words, we can
perfectly recover the policy $\widehat{\pi}_{\mathrm{p}}^{\star}$ from the
estimate $\widehat{\bm{Q}}_{\mathrm{p}}^{\pi_{k}}$, provided that (45) is
satisfied. In addition, it has been shown that (Azar et al.,, 2013, Lemma 2)
the greedy policy induced by $k$-th iteration of both algorithms — denoted by
$\pi_{k}$ — satisfies
$\big{\|}\widehat{\bm{Q}}_{{\mathrm{p}}}^{\pi_{k}}-\widehat{\bm{Q}}_{{\mathrm{p}}}^{\star}\big{\|}_{\infty}\leq\frac{2\gamma^{k+1}}{(1-\gamma)^{2}}$.
Taking
$\xi=\frac{c_{1}(1-\gamma)\varepsilon}{|\mathcal{S}|^{5}|\mathcal{A}|^{5}}$
and
$k=\frac{c_{2}}{1-\gamma}\log(\frac{|\mathcal{S}||\mathcal{A}|}{(1-\gamma)\varepsilon\delta})$
for some constant $c_{2}>0$ large enough, one guarantees that $\pi_{k}$
satisfies (45), which in turn ensures perfect recovery of
$\widehat{\pi}^{\star}_{\mathrm{p}}$.

##  6 Discussion

This paper demonstrates that a perturbed model-based planning algorithm
achieves the minimax sample complexity in a generative model, as soon as the
sample size exceeds the order of $\frac{|\mathcal{S}||\mathcal{A}|}{1-\gamma}$
(modulo some log factor). Compared to prior literature, our result
considerably broadens the sample size range, allowing us to pin down a
complete trade-off curve between sample complexities and statistical accuracy.

The present work opens up several directions for future investigation, which
we discuss in passing below.

  * •

Is perturbation necessary? The planning algorithm analyzed here is applied to
a perturbed variant of the original empirical MDP. This, however, gives rise
to a natural question regarding the necessity of perturbation: can we achieve
optimal planning performance directly using the original empirical MDP without
perturbation? While we conjecture that the answer is affirmative, settling
this conjecture requires developing new analysis techniques beyond the scope
of this paper.

  * •

Improved analysis for model-free algorithms. As mentioned previously, sample
complexity barriers exist in prior theory for model-free approaches (e.g.
Wainwright, 2019b ; Sidford et al., 2018a ). Our analysis might shed light on
how to break such barriers for model-free approaches.

  * •

Episodic finite-horizon MDPs. This work concentrates on infinite-horizon
discounted MDPs, and we expect that the insights analysis can be extended to
study the finite-horizon setting as well, where the samples are drawn in an
episodic fashion (Dann and Brunskill, (2015); Jiang and Agarwal, (2018)). We
leave this extension to future work.

  * •

Beyond the tabular setting. This current paper focuses on the tabular setting
with finite state and action spaces. While we improve the sample size range,
the sample complexities might still be prohibitive when $|\mathcal{S}|$ and
$|\mathcal{A}|$ are enormous. Therefore, it is desirable to further
investigate settings where function approximation is employed to improve the
efficiency (e.g. Jin et al., (2019); Duan and Wang, (2020)).

## Acknowledgements

Y. Chi is supported in part by the grants ONR N00014-18-1-2142 and
N00014-19-1-2404, ARO W911NF-18-1-0303, and NSF CCF-1806154 and CCF-2007911.
Y. Chen is supported in part by the grants AFOSR YIP award FA9550-19-1-0030,
ONR N00014-19-1-2120, ARO YIP award W911NF-20-1-0097, ARO W911NF-18-1-0303,
NSF CCF-1907661 and IIS-1900140, and the Princeton SEAS Innovation Award. We
thank Shicong Cen, Chen Cheng and Cong Ma for numerous discussions about
reinforcement learning.

##  Appendix A Preliminary facts

We begin by recording a few elementary facts about $\bm{P}^{\pi}$ and
$\bm{P}_{\pi}$ (see definitions in (16)). These are standard results and we
omit the proofs for brevity.

######  Lemma 7.

For any policy $\pi$, any probability transition matrix
$\bm{P}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}|}$ and any
$0<\gamma<1$, one has

  * (a)

$(\bm{I}-\gamma\bm{P}_{\pi})^{-1}=\sum_{i=0}^{\infty}(\gamma\bm{P}_{\pi})^{i}$;

  * (b)

All entries of the matrix $(\bm{I}-\gamma\bm{P}_{\pi})^{-1}$ are non-negative;

  * (c)

$\|(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\|_{1}\leq 1/(1-\gamma)$;

  * (d)

$(1-\gamma)(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\bm{1}=\bm{1}$;

  * (e)

For any non-negative vectors $\bm{0}\leq\bm{r}_{1}\leq\bm{r}_{2}$ of
compatible dimension, one has
$\bm{0}\leq(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\bm{r}_{1}\leq(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\bm{r}_{2}$.

The above results continue to hold if $\bm{P}_{\pi}$ is replaced by
$\bm{P}^{\pi}$.

##  Appendix B Proofs of auxiliary lemmas

###  B.1 Proofs of Lemma 1 and Lemma 2

##### Auxiliary notation and preliminaries.

Before proceeding, we define several $|\mathcal{S}|$-dimensional auxiliary
vectors $\bm{r}^{(i)},\bm{V}^{(i)},\widehat{\bm{V}}^{(i)}$ ($1\leq i\leq m$)
recursively as follows

$\displaystyle\begin{array}[]{lll}\bm{r}^{(0)}:=\bm{r}_{\pi},&\bm{V}^{(0)}:=(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\bm{r}^{(0)},&\widehat{\bm{V}}^{(0)}:=(\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi})^{-1}\bm{r}^{(0)},\\\
\bm{r}^{(1)}:=\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(0)}\big{]}},&\bm{V}^{(1)}:=(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\bm{r}^{(1)},&\widehat{\bm{V}}^{(2)}:=(\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi})^{-1}\bm{r}^{(1)},\\\
\quad\quad\quad\vdots&\quad\quad\quad\vdots&\quad\quad\quad\vdots\\\
\bm{r}^{(m)}:=\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(m-1)}\big{]}},&\bm{V}^{(m)}:=(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\bm{r}^{(m)},&\widehat{\bm{V}}^{(m)}:=(\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi})^{-1}\bm{r}^{(m)},\end{array}$
(50)

where $m$ will be specified momentarily.

A crucial quantity that appears repeatedly in analyzing the above terms is
$\|(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\sqrt{\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})}\|_{\infty}$,
whose importance was already made apparent in the work Azar et al., (2013). A
widely used upper bound on this quantity, originally due to (Azar et al.,,
2013, Lemma 8), is given by

$\left\|(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\sqrt{\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})}\right\|_{\infty}\leq\frac{2\log
2}{\gamma(1-\gamma)^{1.5}}\left\|\bm{r}\right\|_{\infty}.$ (51)

This bound turns out to be loose for our purpose, and we develop an improved
bound as follows, whose proof is deferred to Appendix B.1.1.

######  Lemma 8.

Consider any policy $\pi$ and any probability transition matrix
$\bm{P}\in\mathbb{R}^{|\mathcal{S}||\mathcal{A}|\times|\mathcal{S}|}$. Let
$\bm{V}$ be a vector obeying
$\bm{V}=(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\bm{r}_{\pi}$ for some
$|\mathcal{S}|$-dimensional vector $\bm{r}_{\pi}\geq\bm{0}$. For any
$0<\gamma<1$, one has

$\left\|(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\sqrt{\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})}\right\|_{\infty}\leq\frac{4}{\gamma\sqrt{1-\gamma}}\left\|\bm{V}\right\|_{\infty}.$
(52)

######  Remark 5.

In comparison to the bound (51) derived in (Azar et al.,, 2013, Lemma 8),
Lemma 8 offers an improved upper bound stated directly in terms of the
properties of $\bm{V}$ rather than those of $\bm{r}$.

As it turns out, Lemma 8 allows us to obtain an entrywise bound for
$\bm{V}^{(l)}$ $(1\leq l\leq m)$. To begin with, the first term $\bm{V}^{(1)}$
satisfies

$\big{\|}\bm{V}^{(1)}\big{\|}_{\infty}=\Big{\|}(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(0)}\big{]}}\Big{\|}_{\infty}$
(53)

since
$\bm{r}^{(1)}=\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(0)}\big{]}}$.
Next, for any $l>1$ one has

$\displaystyle\big{\|}\bm{V}^{(l)}\big{\|}_{\infty}$
$\displaystyle=\big{\|}(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\bm{r}^{(l)}\big{\|}_{\infty}=\Big{\|}(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(l-1)}\big{]}}\Big{\|}_{\infty}$
$\displaystyle\leq\frac{4}{\gamma\sqrt{1-\gamma}}\big{\|}\bm{V}^{(l-1)}\big{\|}_{\infty},$

where the second identity results from the definition of $\bm{r}^{(l)}$, and
the last inequality comes from Lemma 8. As a consequence, applying this
inequality recursively gives

$\displaystyle\big{\|}\bm{V}^{(l)}\big{\|}_{\infty}\leq\Big{(}\frac{4}{\gamma\sqrt{1-\gamma}}\Big{)}^{l-1}\big{\|}\bm{V}^{(1)}\big{\|}_{\infty}.$
(54)

##### Main proof.

Equipped with the above facts, we are now in a position to prove the lemmas,
for which we start with the more general one — Lemma 2. Consider any $0\leq
l\leq m$. We first observe that

$\displaystyle\widehat{\bm{V}}^{(l)}-\bm{V}^{(l)}$
$\displaystyle=(\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi})^{-1}\bm{r}^{(l)}-\bm{V}^{(l)}$
$\displaystyle=\big{(}\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi}\big{)}^{-1}\big{(}\bm{I}-\gamma{\bm{P}}_{\pi}\big{)}\bm{V}^{(l)}-\big{(}\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi}\big{)}^{-1}\big{(}\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi}\big{)}\bm{V}^{(l)}$
$\displaystyle=\gamma\big{(}\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi}\big{)}^{-1}\big{(}{\widehat{\bm{P}}}_{\pi}-{\bm{P}}_{\pi}\big{)}\bm{V}^{(l)},$
(55)

where the second line follows since, by definition,
$\big{(}\bm{I}-\gamma{\bm{P}}_{\pi}\big{)}\bm{V}^{(l)}=\bm{r}^{(l)}$. Suppose
that there exists some quantity $\beta_{1}>0$ such that the following
condition

$\Big{|}\big{(}{\widehat{\bm{P}}}_{\pi}-{\bm{P}}_{\pi}\big{)}\bm{V}^{(l)}\Big{|}\leq\sqrt{\frac{\beta_{1}}{N}}\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(l)}\big{]}}+\frac{\big{\|}\bm{V}^{(l)}\big{\|}_{\infty}\beta_{1}}{N}\bm{1}$
(56)

holds uniformly for all $0\leq l\leq m$. Then this combined with (55) gives

$\displaystyle\big{\|}\widehat{\bm{V}}^{(l)}-\bm{V}^{(l)}\big{\|}_{\infty}$
$\displaystyle=\gamma\Big{\|}\big{(}\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi}\big{)}^{-1}\big{(}{\widehat{\bm{P}}}_{\pi}-{\bm{P}}_{\pi}\big{)}\bm{V}^{(l)}\Big{\|}_{\infty}$
$\displaystyle\overset{(\mathrm{i})}{\leq}\gamma\Big{\|}\big{(}\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi}\big{)}^{-1}\Big{|}\big{(}{\widehat{\bm{P}}}_{\pi}-{\bm{P}}_{\pi}\big{)}\bm{V}^{(l)}\Big{|}\Big{\|}_{\infty}$
$\displaystyle\overset{(\mathrm{ii})}{\leq}\gamma\sqrt{\frac{\beta_{1}}{N}}\Big{\|}\big{(}\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi}\big{)}^{-1}\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(l)}\big{]}}\Big{\|}_{\infty}+\frac{\gamma\big{\|}\bm{V}^{(l)}\big{\|}_{\infty}\beta_{1}}{N}\Big{\|}\big{(}\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi}\big{)}^{-1}\bm{1}\Big{\|}_{\infty}.$

Here, (i) follows since
$\big{(}\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi}\big{)}^{-1}$ is a non-negative
matrix, (ii) comes from (56) and the triangle inequality. Recalling the
definition of $\bm{r}^{(l)}$ and $\widehat{\bm{V}}^{(l)}$ and invoking Lemma
7(d), we can further bound the above as

$\displaystyle\big{\|}\widehat{\bm{V}}^{(l)}-\bm{V}^{(l)}\big{\|}_{\infty}$
$\displaystyle\leq\gamma\sqrt{\frac{\beta_{1}}{N}}\big{\|}\widehat{\bm{V}}^{(l+1)}\big{\|}_{\infty}+\frac{\gamma\big{\|}\bm{V}^{(l)}\big{\|}_{\infty}\beta_{1}}{(1-\gamma)N}$
$\displaystyle\leq\gamma\sqrt{\frac{\beta_{1}}{N}}\big{\|}\widehat{\bm{V}}^{(l+1)}-\bm{V}^{(l+1)}\big{\|}_{\infty}+\gamma\sqrt{\frac{\beta_{1}}{N}}\big{\|}\bm{V}^{(l+1)}\big{\|}_{\infty}+\frac{\gamma\beta_{1}}{(1-\gamma)N}\big{\|}\bm{V}^{(l)}\big{\|}_{\infty},$
(57)

where the last inequality is a consequence of the triangle inequality.

The above inequality (57) provides a recursive relation that in turn allows
for an effective upper bound. Specifically, combining the inequalities (54)
and (57) leads to

$\displaystyle\big{\|}\widehat{\bm{V}}^{(0)}-\bm{V}^{(0)}\big{\|}_{\infty}$
$\displaystyle\leq\gamma\sqrt{\frac{\beta_{1}}{N}}\big{\|}\widehat{\bm{V}}^{(1)}-\bm{V}^{(1)}\big{\|}_{\infty}+\gamma\sqrt{\frac{\beta_{1}}{N}}\big{\|}\bm{V}^{(1)}\big{\|}_{\infty}+\frac{\gamma\beta_{1}}{(1-\gamma)N}\big{\|}\bm{V}^{(0)}\big{\|}_{\infty}$
$\displaystyle=:b_{1}\big{\|}\widehat{\bm{V}}^{(1)}-\bm{V}^{(1)}\big{\|}_{\infty}+b_{1}\big{\|}\bm{V}^{(1)}\big{\|}_{\infty}+\frac{\gamma\beta_{1}}{(1-\gamma)N}\big{\|}\bm{V}^{(0)}\big{\|}_{\infty},$

and for $l\geq 1$,

$\displaystyle\big{\|}\widehat{\bm{V}}^{(l)}-\bm{V}^{(l)}\big{\|}_{\infty}$
$\displaystyle\leq\gamma\sqrt{\frac{\beta_{1}}{N}}\big{\|}\widehat{\bm{V}}^{(l+1)}-\bm{V}^{(l+1)}\big{\|}_{\infty}+\left(4\sqrt{\frac{\beta_{1}}{(1-\gamma)N}}+\frac{\gamma\beta_{1}}{(1-\gamma)N}\right)\left(\frac{4}{\gamma\sqrt{1-\gamma}}\right)^{l-1}\|\bm{V}^{(1)}\|_{\infty}$
$\displaystyle=:b_{1}\big{\|}\widehat{\bm{V}}^{(l+1)}-\bm{V}^{(l+1)}\big{\|}_{\infty}+b_{2}b_{3}^{l-1}\|\bm{V}^{(1)}\|_{\infty}.$

Here for notational simplicity, we introduce

$\displaystyle b_{1}:=\gamma\sqrt{\frac{\beta_{1}}{N}},\qquad
b_{2}:=4\sqrt{\frac{\beta_{1}}{(1-\gamma)N}}+\frac{\gamma\beta_{1}}{(1-\gamma)N},\qquad
b_{3}:=\frac{4}{\gamma\sqrt{1-\gamma}}.$

Invoking the above recursive relation, we can arrange terms to reach

$\displaystyle\big{\|}\widehat{\bm{V}}^{(0)}-\bm{V}^{(0)}\big{\|}_{\infty}$
$\displaystyle\leq\underbrace{b_{1}^{m}\big{\|}\widehat{\bm{V}}^{(m)}-\bm{V}^{(m)}\big{\|}_{\infty}}_{=:\alpha_{1}}+\underbrace{\Big{(}b_{1}b_{2}\sum_{l=0}^{m-2}(b_{1}b_{3})^{l}+b_{1}\Big{)}}_{=:\alpha_{2}}\big{\|}\bm{V}^{(1)}\big{\|}_{\infty}+\frac{\gamma\beta_{1}}{(1-\gamma)N}\big{\|}\bm{V}^{(0)}\big{\|}_{\infty}.$
(58)

Controlling the quantity $\alpha_{2}$. Now it suffices to control the two
terms on the right-hand side of the inequality (58) separately, towards which
we shall start with the quantity $\alpha_{2}.$ Assuming that $N\geq
64\beta_{1}/(1-\gamma)$, one can easily verify $b_{1}b_{3}\leq 1/2$. The
summation of the geometric sequence thus gives

$\displaystyle\alpha_{2}$
$\displaystyle:=b_{1}b_{2}\sum_{l=0}^{m-2}(b_{1}b_{3})^{l}+b_{1}\leq\frac{b_{1}b_{2}}{1-b_{1}b_{3}}+b_{1}\leq
2b_{1}b_{2}+b_{1}$
$\displaystyle=\gamma\sqrt{\frac{\beta_{1}}{N}}\left\\{1+8\sqrt{\frac{\beta_{1}}{(1-\gamma)N}}+\frac{2\gamma\beta_{1}}{(1-\gamma)N}\right\\}\leq
3\gamma\sqrt{\frac{\beta_{1}}{N}},$ (59)

where the last step holds with the assumption
$N\geq\frac{64\beta_{1}}{1-\gamma}$.

Controlling the quantity $\alpha_{1}$. Next, we proceed to the quantity
$\alpha_{1}$, which requires the control of
$\big{\|}\widehat{\bm{V}}^{(m)}-\bm{V}^{(m)}\big{\|}_{\infty}$. In view of the
identity (55), we obtain

$\displaystyle\big{\|}\widehat{\bm{V}}^{(m)}-\bm{V}^{(m)}\big{\|}_{\infty}$
$\displaystyle=\gamma\big{\|}(\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi})^{-1}({\bm{P}}_{\pi}-{\widehat{\bm{P}}}_{\pi})\bm{V}^{(m)}\big{\|}_{\infty}$
$\displaystyle\leq\gamma\Bigg{\|}(\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi})^{-1}\Bigg{(}\sqrt{\frac{\beta_{1}}{N}}\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(m)}\big{]}}+\frac{\big{\|}\bm{V}^{(m)}\big{\|}_{\infty}\beta_{1}}{N}\bm{1}\Bigg{)}\Bigg{\|}_{\infty},$

where the last inequality follows from the Bernstein-type condition (56) and
the fact that $\big{(}\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi}\big{)}^{-1}$ has
non-negative entries. By virtue of the simple relation
$\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(m)}\big{]}}\leq\big{\|}\bm{V}^{(m)}\big{\|}_{\infty}$
and the fact that
$\|\big{(}\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi}\big{)}^{-1}\|_{1}\leq\frac{1}{1-\gamma}$
(cf. Lemma 7(c)), it is further guaranteed that

$\displaystyle\big{\|}\widehat{\bm{V}}^{(m)}-\bm{V}^{(m)}\big{\|}_{\infty}$
$\displaystyle\leq\gamma\|(\bm{I}-\gamma{\widehat{\bm{P}}}_{\pi})^{-1}\|_{1}\cdot\Bigg{\|}\sqrt{\frac{\beta_{1}}{N}}\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(m)}\big{]}}+\frac{\big{\|}\bm{V}^{(m)}\big{\|}_{\infty}\beta_{1}}{N}\bm{1}\Bigg{\|}_{\infty},$
$\displaystyle\leq\frac{\gamma}{1-\gamma}\Bigg{(}\sqrt{\frac{\beta_{1}}{N}}+\frac{\beta_{1}}{N}\Bigg{)}\big{\|}\bm{V}^{(m)}\big{\|}_{\infty},$

which combined with the bound (54) yields

$\displaystyle\big{\|}\widehat{\bm{V}}^{(m)}-\bm{V}^{(m)}\big{\|}_{\infty}$
$\displaystyle\leq\frac{\gamma}{1-\gamma}\Bigg{(}\sqrt{\frac{\beta_{1}}{N}}+\frac{\beta_{1}}{N}\Bigg{)}\Big{(}\frac{4}{\gamma\sqrt{1-\gamma}}\Big{)}^{m-1}\|\bm{V}^{(1)}\|_{\infty}.$

Putting the above bounds together yields

$\displaystyle\alpha_{1}:=b_{1}^{m}\big{\|}\widehat{\bm{V}}^{(m)}-\bm{V}^{(m)}\big{\|}_{\infty}$
$\displaystyle\leq\left(\gamma\sqrt{\frac{\beta_{1}}{N}}\right)^{m}\frac{\gamma}{1-\gamma}\Bigg{(}\sqrt{\frac{\beta_{1}}{N}}+\frac{\beta_{1}}{N}\Bigg{)}\Big{(}\frac{4}{\gamma\sqrt{1-\gamma}}\Big{)}^{m-1}\|\bm{V}^{(1)}\|_{\infty}$
$\displaystyle=\left(\sqrt{\frac{16\beta_{1}}{N(1-\gamma)}}\right)^{m-1}\Bigg{(}\sqrt{\frac{\beta_{1}}{N}}+1\Bigg{)}\frac{\gamma^{2}\beta_{1}}{(1-\gamma)N}\|\bm{V}^{(1)}\|_{\infty}$
$\displaystyle\leq\left(\frac{1}{e}\right)^{m-1}\frac{1.1\gamma^{2}\beta_{1}}{(1-\gamma)N}\|\bm{V}^{(1)}\|_{\infty},$
(60)

where the last inequality holds provided that
$N>\frac{16e^{2}}{1-\gamma}\beta_{1}$.

Putting all this together. Combining the inequalities (58), (59) and (60)
gives

$\displaystyle\big{\|}\widehat{\bm{V}}^{(0)}-\bm{V}^{(0)}\big{\|}_{\infty}\leq\frac{\gamma\beta_{1}}{(1-\gamma)N}\big{\|}\bm{V}^{(0)}\big{\|}_{\infty}+\left\\{3\gamma\sqrt{\frac{\beta_{1}}{N}}+\left(\frac{1}{e}\right)^{m-1}\frac{1.1\gamma^{2}\beta_{1}}{(1-\gamma)N}\right\\}\|\bm{V}^{(1)}\|_{\infty}.$

To finish up, set $m=\log(\frac{e}{1-\gamma})$ and assume that
$N>\frac{16e^{2}}{1-\gamma}\beta_{1}$. Recognizing that
$\bm{V}^{(0)}=\bm{V}^{\pi}$ and
$\widehat{\bm{V}}^{(0)}=\widehat{\bm{V}}^{\pi}$, we arrive at

$\displaystyle\big{\|}\widehat{\bm{V}}^{\pi}-\bm{V}^{\pi}\big{\|}_{\infty}=\big{\|}\widehat{\bm{V}}^{(0)}-\bm{V}^{(0)}\big{\|}_{\infty}$
$\displaystyle\leq\frac{\gamma\beta_{1}}{(1-\gamma)N}\big{\|}\bm{V}^{(0)}\big{\|}_{\infty}+\left\\{3\gamma\sqrt{\frac{\beta_{1}}{N}}+\left(\frac{1}{e}\right)^{m-1}\frac{1.1\gamma^{2}\beta_{1}}{(1-\gamma)N}\right\\}\|\bm{V}^{(1)}\|_{\infty}$
$\displaystyle\leq\frac{\gamma\beta_{1}}{(1-\gamma)N}\big{\|}\bm{V}^{\pi}\big{\|}_{\infty}+4\gamma\sqrt{\frac{\beta_{1}}{N}}\Big{\|}(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{\pi}\big{]}}\Big{\|}_{\infty},$
(61)

provided that $N\geq\frac{16e^{2}\beta_{1}}{1-\gamma}$.

##### Proof of Lemma 2.

Invoking the inequality (51) to bound the second term of (61), we reach

$\displaystyle\big{\|}\widehat{\bm{V}}^{\pi}-\bm{V}^{\pi}\big{\|}_{\infty}\leq\frac{\gamma\beta_{1}}{(1-\gamma)N}\big{\|}\bm{V}^{\pi}\big{\|}_{\infty}+8\log
2\sqrt{\frac{\beta_{1}}{N(1-\gamma)^{3}}}\|\bm{r}\|_{\infty}\leq
6\sqrt{\frac{\beta_{1}}{N(1-\gamma)^{3}}}\|\bm{r}\|_{\infty},$ (62)

where the last inequality uses the elementary fact that
$\big{\|}\bm{V}^{\pi}\big{\|}_{\infty}\leq\frac{1}{1-\gamma}\|\bm{r}\|_{\infty}$
and the assumption that $N>\frac{16e^{2}}{1-\gamma}\beta_{1}$. We complete the
proof of Lemma 2.

##### Proof of Lemma 1.

Finally, to establish Lemma 1, we observe that: for any fixed policy $\pi$,
the vector $\bm{V}^{(l)}$ is independent of ${\widehat{\bm{P}}}_{\pi}$. The
Bernstein inequality (e.g. (Agarwal et al.,, 2019, Lemma 6)) then reveals that
with probability at least $1-\delta$,

$\Big{|}\big{(}{\widehat{\bm{P}}}_{\pi}-{\bm{P}}_{\pi}\big{)}\bm{V}^{(l)}\Big{|}\leq\sqrt{\frac{2\log\big{(}\frac{4m|\mathcal{S}|}{\delta}\big{)}}{N}}\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{(l)}\big{]}}+\frac{\big{\|}\bm{V}^{(l)}\big{\|}_{\infty}\log\big{(}\frac{4m|\mathcal{S}|}{\delta}\big{)}}{N}\bm{1}$
(63)

holds uniformly for all $0\leq l\leq m$. This means that we can take
$\beta_{1}:=2\log\big{(}\frac{4m|\mathcal{S}|}{\delta}\big{)}$ with
$m=\log(\frac{e}{1-\gamma})$ for this case. Combining this with the inequality
(61), we derive the advertised instance-dependent bound

$\displaystyle\big{\|}\widehat{\bm{V}}^{\pi}-\bm{V}^{\pi}\big{\|}_{\infty}$
$\displaystyle\leq\frac{2\gamma\log\big{(}\frac{4|\mathcal{S}|\log\frac{e}{1-\gamma}}{\delta}\big{)}}{(1-\gamma)N}\big{\|}\bm{V}^{\pi}\big{\|}_{\infty}+4\gamma\sqrt{\frac{2\log\big{(}\frac{4|\mathcal{S}|\log\frac{e}{1-\gamma}}{\delta}\big{)}}{(1-\gamma)N}}\,\Big{\|}(\bm{I}-\gamma{\bm{P}}_{\pi})^{-1}\sqrt{\mathsf{Var}_{{\bm{P}}_{\pi}}\big{[}\bm{V}^{\pi}\big{]}}\Big{\|}_{\infty}.$

Further, this taken collectively with (51) and the crude bound
$\|\bm{V}^{\pi}\|_{\infty}\leq\frac{1}{1-\gamma}\|\bm{r}\|_{\infty}$ gives

$\displaystyle\big{\|}\widehat{\bm{V}}^{\pi}-\bm{V}^{\pi}\big{\|}_{\infty}$
$\displaystyle\leq\frac{2\gamma\log\big{(}\frac{4|\mathcal{S}|\log\frac{e}{1-\gamma}}{\delta}\big{)}}{(1-\gamma)^{2}N}\big{\|}\bm{r}\big{\|}_{\infty}+8\log
2\sqrt{\frac{2\log\big{(}\frac{4|\mathcal{S}|\log\frac{e}{1-\gamma}}{\delta}\big{)}}{(1-\gamma)^{3}N}}\,\|\bm{r}\|_{\infty}$
$\displaystyle\leq
6\sqrt{\frac{2\log\big{(}\frac{4|\mathcal{S}|\log\frac{e}{1-\gamma}}{\delta}\big{)}}{(1-\gamma)^{3}N}}\,\|\bm{r}\|_{\infty},$

with the proviso that
$N\geq\frac{32e^{2}}{1-\gamma}\log\big{(}\frac{4|\mathcal{S}|\log\frac{e}{1-\gamma}}{\delta}\big{)}.$

####  B.1.1 Proof of Lemma 8

To begin with, we make the observation that

$\displaystyle\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})$
$\displaystyle=\bm{P}_{\pi}(\bm{V}\circ\bm{V})-(\bm{P}_{\pi}\bm{V})\circ(\bm{P}_{\pi}\bm{V})$
$\displaystyle=\bm{P}_{\pi}(\bm{V}\circ\bm{V})-\frac{1}{\gamma^{2}}(\bm{V}-\bm{r}_{\pi})\circ(\bm{V}-\bm{r}_{\pi})$
(64)
$\displaystyle=\bm{P}_{\pi}(\bm{V}\circ\bm{V})-\frac{1}{\gamma^{2}}\bm{V}\circ\bm{V}+\frac{2}{\gamma^{2}}\bm{V}\circ\bm{r}_{\pi}-\frac{1}{\gamma^{2}}\bm{r}_{\pi}\circ\bm{r}_{\pi}$
$\displaystyle\leq\frac{1}{\gamma^{2}}(\gamma^{2}\bm{P}_{\pi}-\bm{I})(\bm{V}\circ\bm{V})+\frac{2}{\gamma^{2}}\bm{V}\circ\bm{r}_{\pi},$
(65)

where the identity (64) makes use of the relation
$\bm{V}=\bm{r}_{\pi}+\gamma\bm{P}_{\pi}\bm{V}$. In addition, one can deduce
that

$\displaystyle\left\|(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\sqrt{\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})}\right\|_{\infty}$
$\displaystyle=\frac{1}{1-\gamma}\left\|(1-\gamma)(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\sqrt{\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})}\right\|_{\infty}$
$\displaystyle\overset{(\mathrm{i})}{\leq}\frac{1}{\sqrt{1-\gamma}}\left\|\sqrt{(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})}\right\|_{\infty}$
$\displaystyle\overset{(\mathrm{ii})}{\leq}\frac{1}{\sqrt{1-\gamma}}\sqrt{\left\|2(\bm{I}-\gamma^{2}\bm{P}_{\pi})^{-1}\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})\right\|_{\infty}}.$

Here, (i) comes from Jensen’s inequality (so that
$\mathbb{E}[\sqrt{v}]\leq\sqrt{\mathbb{E}[v]}$) recognizing that each row of
$(1-\gamma)(\bm{I}-\gamma\bm{P}_{\pi})^{-1}$ is a probability distribution,
and Lemma 7(d), (ii) is an elementary fact established in (Agarwal et al.,,
2019, Lemma 4). Combining Lemma 7(e) and the inequality (65) further yields

$\displaystyle\left\|(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\sqrt{\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})}\right\|_{\infty}$
$\displaystyle\leq\frac{1}{\sqrt{1-\gamma}}\sqrt{\left\|2(\bm{I}-\gamma^{2}\bm{P}_{\pi})^{-1}\left(\frac{1}{\gamma^{2}}\Big{(}\gamma^{2}\bm{P}_{\pi}-\bm{I}\Big{)}(\bm{V}\circ\bm{V})+\frac{2}{\gamma^{2}}\bm{V}\circ\bm{r}_{\pi}\right)\right\|_{\infty}}$
$\displaystyle\leq\frac{1}{\gamma\sqrt{1-\gamma}}\sqrt{2\left\|\bm{V}\circ\bm{V}\right\|_{\infty}}+\frac{2}{\gamma\sqrt{1-\gamma}}\sqrt{\left\|(\bm{I}-\gamma^{2}\bm{P}_{\pi})^{-1}\left(\bm{V}\circ\bm{r}_{\pi}\right)\right\|_{\infty}}.$
(66)

where the last step arises from the triangle inequality and
$\sqrt{a+b}\leq\sqrt{a}+\sqrt{b}$. This leaves us with two terms to deal with.

Regarding the first term of (66), we observe that
$\left\|(\bm{V}\circ\bm{V})\right\|_{\infty}=\left\|\bm{V}\right\|_{\infty}^{2}$.
When it comes to the second term of (66), it is seen that

$\displaystyle\left\|(\bm{I}-\gamma^{2}\bm{P}_{\pi})^{-1}\left(\bm{V}\circ\bm{r}_{\pi}\right)\right\|_{\infty}$
$\displaystyle\leq\left\|(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\left(\bm{V}\circ\bm{r}_{\pi}\right)\right\|_{\infty}$
$\displaystyle\leq\|\bm{V}\|_{\infty}\left\|(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\bm{r}_{\pi}\right\|_{\infty}$
$\displaystyle=\|\bm{V}\|_{\infty}^{2}.$

Here, the first inequality holds true since
$(\bm{I}-\gamma^{2}\bm{P}_{\pi})^{-1}=\sum_{i=0}^{\infty}\gamma^{2i}\bm{P}_{\pi}^{i}\leq\sum_{i=0}^{\infty}\gamma^{i}\bm{P}_{\pi}^{i}=(\bm{I}-\gamma\bm{P}_{\pi})^{-1}$,
while the second line holds since $\bm{V}$, $\bm{r}$ and
$(\bm{I}-\gamma\bm{P}_{\pi})^{-1}$ are all non-negative. Substitution into
(66) thus yields

$\displaystyle\left\|(\bm{I}-\gamma\bm{P}_{\pi})^{-1}\sqrt{\mathsf{Var}_{\bm{P}_{\pi}}(\bm{V})}\right\|_{\infty}$
$\displaystyle\leq\frac{\sqrt{2}}{\gamma\sqrt{1-\gamma}}\left\|\bm{V}\right\|_{\infty}+\frac{2}{\gamma\sqrt{1-\gamma}}\left\|\bm{V}\right\|_{\infty}\leq\frac{4}{\gamma\sqrt{1-\gamma}}\left\|\bm{V}\right\|_{\infty}$

as claimed.

###  B.2 Proof of Lemma 3

To establish Lemma 3, it suffices to check that ${\bm{V}}^{\star}$ and
${\bm{Q}}^{\star}$ satisfy the Bellman optimality equations underlying
$\mathcal{M}_{s,a,u^{\star}}$. Towards this end, we study the absorbing state-
action pair $(s,a)$ and other pairs separately. For notational simplicity, we
shall let $\bm{P}^{\mathsf{abs}}$ and $r^{\mathsf{abs}}(\cdot,\cdot)$ denote
respectively the probability transition matrix and the reward function
associated with $\mathcal{M}_{s,a,u^{\star}}$.

First, we observe that, by construction,

$\displaystyle
r^{\mathsf{abs}}(s,a)+\gamma(\bm{P}^{\mathsf{abs}}{\bm{V}}^{\star})_{s,a}=u^{\star}+\gamma
V^{\star}(s).$

Recall that ${\bm{V}}^{\star}$ satisfies the Bellman optimality equation
w.r.t. the original MDP, namely,
$Q^{\star}(s,a)=r(s,a)+\gamma(\bm{P}{\bm{V}}^{\star})_{s,a}$. This together
with our choice of $u^{\star}$ gives

$\displaystyle u^{\star}+\gamma V^{\star}(s)$
$\displaystyle=Q^{\star}(s,a)-\gamma V^{\star}(s)+\gamma
V^{\star}(s)=Q^{\star}(s,a).$

Putting the above identities together, we arrive at

$\displaystyle
Q^{\star}(s,a)=r^{\mathsf{abs}}(s,a)+\gamma(\bm{P}^{\mathsf{abs}}{\bm{V}}^{\star})_{s,a}.$
(67)

Next, consider any state-action pair $(s^{\prime},a^{\prime})\neq(s,a)$.
Recalling again the properties of $\mathcal{M}_{s,a,u^{\star}}$, we reach

$\displaystyle
r^{\mathsf{abs}}(s^{\prime},a^{\prime})+\gamma(\bm{P}^{\mathsf{abs}}{\bm{V}}^{\star})_{s^{\prime},a^{\prime}}=r(s^{\prime},a^{\prime})+\gamma(\bm{P}{\bm{V}}^{\star})_{s^{\prime},a^{\prime}}=Q^{\star}(s^{\prime},a^{\prime}).$
(68)

Here the last identity is due to the Bellman equation w.r.t. the original MDP.
Combining (67) and (68) implies that ${\bm{V}}^{\star}$ and ${\bm{Q}}^{\star}$
satisfy Bellman’s optimality equations in $\mathcal{M}_{s,a,u^{\star}}$, thus
concluding the proof.

###  B.3 Proof of Lemma 4

Our first observation is that $\widehat{\bm{Q}}^{\star}_{s,a,u}$ satisfies
Lipschitz continuity w.r.t. $u$ in the sense that

$\displaystyle\big{\|}\widehat{\bm{Q}}^{\star}_{s,a,u}-\widehat{\bm{Q}}^{\star}_{s,a,u^{\prime}}\|_{\infty}\leq\frac{1}{1-\gamma}|u-u^{\prime}|.$
(69)

The proof of this relation is identical to that of (Agarwal et al.,, 2019,
Lemma 8); we omit here for brevity. In view of Lemma 3, if we set
$\widehat{u}^{\star}:=r(s,a)+\gamma(\widehat{\bm{P}}\widehat{\bm{V}}^{\star})_{s,a}-\gamma\widehat{V}^{\star}(s)$,
then one has

$\displaystyle\widehat{\bm{Q}}^{\star}_{s,a,\widehat{u}^{\star}}=\widehat{\bm{Q}}^{\star}\qquad\text{and
}\leavevmode\nobreak\ \leavevmode\nobreak\
\widehat{\bm{V}}^{\star}_{s,a,\widehat{u}^{\star}}=\widehat{\bm{V}}^{\star}.$

In addition, there exists a point $u_{0}$ in the epsilon-net
$\mathcal{N}_{(1-\gamma)\omega/4}$ such that
$|\widehat{u}^{\star}-u_{0}|\leq(1-\gamma)\omega/4$, which combined with the
Lipschitz continuity property (69) gives

$\displaystyle\big{\|}\widehat{\bm{Q}}^{\star}-\widehat{\bm{Q}}^{\star}_{s,a,u_{0}}\|_{\infty}=\big{\|}\widehat{\bm{Q}}^{\star}_{s,a,\widehat{u}^{\star}}-\widehat{\bm{Q}}^{\star}_{s,a,u_{0}}\|_{\infty}\leq\frac{1}{1-\gamma}|\widehat{u}^{\star}-u_{0}|\leq\frac{\omega}{4}.$
(70)

Additionally, for any $s^{\prime}\in\mathcal{S}$ and any
$a_{1},a_{2}\in\mathcal{A}$ with $a_{1}\neq a_{2}$, we have the following
decomposition

$\displaystyle\widehat{Q}^{\star}_{s,a,u_{0}}(s^{\prime},a_{1})-\widehat{Q}^{\star}_{s,a,u_{0}}(s^{\prime},a_{2})$
$\displaystyle\qquad=\widehat{Q}^{\star}(s^{\prime},a_{1})-\widehat{Q}^{\star}(s^{\prime},a_{2})+\widehat{Q}^{\star}_{s,a,u_{0}}(s^{\prime},a_{1})-\widehat{Q}^{\star}(s^{\prime},a_{1})-\left(\widehat{Q}^{\star}_{s,a,u_{0}}(s^{\prime},a_{2})-\widehat{Q}^{\star}(s^{\prime},a_{2})\right)$
$\displaystyle\qquad\geq\widehat{Q}^{\star}(s^{\prime},a_{1})-\widehat{Q}^{\star}(s^{\prime},a_{2})-2\big{\|}\widehat{\bm{Q}}^{\star}-\widehat{\bm{Q}}^{\star}_{s,a,u_{0}}\|_{\infty}$
$\displaystyle\qquad\geq\widehat{Q}^{\star}(s^{\prime},a_{1})-\widehat{Q}^{\star}(s^{\prime},a_{2})-\frac{\omega}{2},$
(71)

where the last inequality invokes the inequality (70). Moreover, our
separation condition defined in (36) requires that: for any
$s^{\prime}\in\mathcal{S}$ and any
$a_{2}\neq\widehat{\pi}^{\star}(s^{\prime})$, one has
$\widehat{Q}^{\star}(s^{\prime},\widehat{\pi}^{\star}(s^{\prime}))-\widehat{Q}^{\star}(s^{\prime},a_{2})\geq\omega$,
which together with (71) reveals that

$\displaystyle\widehat{Q}^{\star}_{s,a,u_{0}}(s^{\prime},\widehat{\pi}^{\star}(s^{\prime}))-\widehat{Q}^{\star}_{s,a,u_{0}}(s^{\prime},a_{2})\geq\widehat{Q}^{\star}(s^{\prime},\widehat{\pi}^{\star}(s^{\prime}))-\widehat{Q}^{\star}(s^{\prime},a_{2})-\frac{\omega}{2}\geq\frac{\omega}{2}.$
(72)

Given that
$\widehat{\pi}^{\star}_{s,a,u_{0}}(s^{\prime}):=\arg\max_{a^{\prime}}\widehat{Q}^{\star}_{s,a,u_{0}}(s^{\prime},a^{\prime})$,
it is seen from (72) that

$\displaystyle\widehat{\pi}^{\star}_{s,a,u_{0}}(s^{\prime})=\widehat{\pi}^{\star}(s^{\prime}),$

which holds true for all $s^{\prime}\in\mathcal{S}$. This concludes the proof.

###  B.4 Proof of Lemma 5

We start by bounding
$\big{\|}\widehat{\bm{V}}^{\widehat{\pi}^{\star}}-\bm{V}^{\widehat{\pi}^{\star}}\big{\|}_{\infty}$.
Recall the definition of the series $\\{\bm{V}^{(l)}\\}$ in (50). Throughout
this proof, we shall write $\bm{V}_{\pi}^{(l)}$ instead in order to make
apparent the dependency on the policy $\pi$.

For each state-action pair $(s,a)$, let us construct the epsilon-net
$\mathcal{N}_{(1-\gamma)\omega/4}$ as in the expression (37). For every
$u\in\mathcal{N}_{(1-\gamma)\omega/4}$, recall that
$\widehat{\pi}^{\star}_{s,a,u}$ is defined as the optimal policy with respect
to the $(s,a)$-absorbing MDP $\widehat{\mathcal{M}}_{s,a,u}$. By construction,
the set of policies $\widehat{\pi}^{\star}_{s,a,u}$
($u\in\mathcal{N}_{(1-\gamma)\omega/4}$) is independent of
$\widehat{\bm{P}}_{s,a}$. The Bernstein inequality (e.g. (Agarwal et al.,,
2019, Lemma 6)) taken together with the union bound thus guarantees that with
probability at least $1-\delta$,

$\displaystyle\Big{|}(\widehat{\bm{P}}-\bm{P})_{s,a}\bm{V}_{\widehat{\pi}^{\star}_{s,a,u}}^{(l)}\Big{|}\leq\sqrt{\frac{\beta_{1}}{N}}\sqrt{\big{(}\mathsf{Var}_{\bm{P}}\big{[}\bm{V}^{(l)}_{\widehat{\pi}^{\star}_{s,a,u}}\big{]}\big{)}_{s,a}}+\frac{\big{\|}\bm{V}_{\widehat{\pi}^{\star}_{s,a,u}}^{(l)}\big{\|}_{\infty}\beta_{1}}{N}$
(73)

holds uniformly over all $0\leq l\leq\log\frac{e}{1-\gamma}$,
$u\in\mathcal{N}_{(1-\gamma)\omega/4}$,
$(s,a)\in\mathcal{S}\times\mathcal{A}$. Here, $\beta_{1}$ is given by

$\beta_{1}:=2\log\Big{(}\frac{4\log\big{(}\frac{e}{1-\gamma}\big{)}|\mathcal{N}_{(1-\gamma)\omega/4}||\mathcal{S}||\mathcal{A}|}{\delta}\Big{)}\leq
2\log\Big{(}\frac{32}{(1-\gamma)^{2}\omega\delta}|\mathcal{S}||\mathcal{A}|\log\big{(}\frac{e}{1-\gamma}\big{)}\Big{)},$

where we have used the fact
$|\mathcal{N}_{(1-\gamma)\omega/4}|\leq\frac{8}{(1-\gamma)^{2}\omega}$. In
addition, for any $0<\omega<1$, Lemma 4 guarantees that for each state-action
pair $(s,a)\in\mathcal{S}\times\mathcal{A}$, there exists a point
$u_{0}\in\mathcal{N}_{(1-\gamma)\omega/4}$ such that
$\widehat{\pi}^{\star}=\widehat{\pi}^{\star}_{s,a,u_{0}}$. Invoking this
important fact, we obtain

$\displaystyle\left|(\widehat{\bm{P}}-\bm{P})_{s,a}\bm{V}_{\widehat{\pi}^{\star}}^{(l)}\right|$
$\displaystyle=\left|(\widehat{\bm{P}}-\bm{P})_{s,a}\bm{V}^{(l)}_{\widehat{\pi}^{\star}_{s,a,u_{0}}}\right|$
$\displaystyle\leq\sqrt{\frac{\beta_{1}}{N}}\sqrt{\big{(}\mathsf{Var}_{\bm{P}}\big{[}\bm{V}^{(l)}_{\widehat{\pi}^{\star}_{s,a,u_{0}}}\big{]}\big{)}_{s,a}}+\frac{\big{\|}\bm{V}_{\widehat{\pi}^{\star}_{s,a,u_{0}}}^{(l)}\big{\|}_{\infty}\beta_{1}}{N}$
$\displaystyle=\sqrt{\frac{\beta_{1}}{N}}\sqrt{\big{(}\mathsf{Var}_{\bm{P}}\big{[}\bm{V}^{(l)}_{\widehat{\pi}^{\star}}\big{]}\big{)}_{s,a}}+\frac{\big{\|}\bm{V}^{(l)}_{\widehat{\pi}^{\star}}\big{\|}_{\infty}\beta_{1}}{N}.$

The above inequality further allows us to deduce that, with probability
$1-\delta$,

$\displaystyle\Big{|}\big{(}\widehat{\bm{P}}_{\widehat{\pi}^{\star}}-\bm{P}_{\widehat{\pi}^{\star}}\big{)}\bm{V}_{\widehat{\pi}^{\star}}^{(l)}\Big{|}$
$\displaystyle=\Big{|}{\bf\Pi}^{\widehat{\pi}^{\star}}(\widehat{\bm{P}}-\bm{P})\bm{V}_{\widehat{\pi}^{\star}}^{(l)}\Big{|}$
$\displaystyle\leq\sqrt{\frac{\beta_{1}}{N}}\sqrt{{\bf\Pi}^{\widehat{\pi}^{\star}}\mathsf{Var}_{\bm{P}}\big{[}\bm{V}^{(l)}_{\widehat{\pi}^{\star}}\big{]}}+\frac{\big{\|}\bm{V}^{(l)}_{\widehat{\pi}^{\star}}\big{\|}_{\infty}\beta_{1}}{N}\bm{1}$
$\displaystyle=\sqrt{\frac{\beta_{1}}{N}}\sqrt{\mathsf{Var}_{\bm{P}_{\widehat{\pi}^{\star}}}\big{[}\bm{V}^{(l)}_{\widehat{\pi}^{\star}}\big{]}}+\frac{\big{\|}\bm{V}^{(l)}_{\widehat{\pi}^{\star}}\big{\|}_{\infty}\beta_{1}}{N}\bm{1}.$

The above derivation validates the assumption required for Lemma 2. As a
result, if $N>\frac{16e^{2}}{1-\gamma}\beta_{1}$ and $0<\omega<1$, then Lemma
2 leads to the advertised bound

$\displaystyle\big{\|}\widehat{\bm{V}}^{\widehat{\pi}^{\star}}-\bm{V}^{\widehat{\pi}^{\star}}\big{\|}_{\infty}$
$\displaystyle\leq\frac{6}{1-\gamma}\sqrt{\frac{\beta_{1}}{N(1-\gamma)}}\leq\frac{6}{1-\gamma}\sqrt{\frac{2\log\Big{(}\frac{32}{(1-\gamma)^{2}\omega\delta}|\mathcal{S}||\mathcal{A}|\log\big{(}\frac{e}{1-\gamma}\big{)}\Big{)}}{N(1-\gamma)}}$
$\displaystyle\leq
6\sqrt{\frac{2\log\Big{(}\frac{32|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{3}\omega\delta}\Big{)}}{N(1-\gamma)^{3}}}.$
(74)

Finally, we move on to the term
${\bm{V}}^{\star}-\widehat{\bm{V}}^{{\pi}^{\star}}$. Given that $\pi^{\star}$
is independent of $\widehat{\bm{P}}$, invoke Lemma 1 to reach

$\displaystyle\left\|\widehat{\bm{V}}^{{\pi}^{\star}}-{\bm{V}}^{\star}\right\|_{\infty}=\big{\|}\widehat{\bm{V}}^{{\pi}^{\star}}-\bm{V}^{{\pi}^{\star}}\big{\|}_{\infty}$
$\displaystyle\leq
6\sqrt{2}\sqrt{\frac{\log\big{(}\frac{4|\mathcal{S}|}{\delta}\big{)}+\log\log\big{(}\frac{e}{1-\gamma}\big{)}}{N(1-\gamma)^{3}}}$
$\displaystyle\leq
6\sqrt{\frac{2\log\big{(}\frac{32|\mathcal{S}||\mathcal{A}|}{(1-\gamma)^{2}\omega\delta}\big{)}}{N(1-\gamma)^{3}}}$
(75)

with probability at least $1-\delta$. This together with (24) and (74)
immediately establishes Lemma 5.

###  B.5 Proof of Lemma 6

The proofs for $Q_{{\mathrm{p}}}^{\star}$ and
$\widehat{Q}_{{\mathrm{p}}}^{\star}$ are exactly the same; for the sake of
conciseness, we shall only provide the proof for $Q_{{\mathrm{p}}}^{\star}$.
Here we aim to prove a more general result than Lemma 6, namely, with
probability at least $1-\delta$,

$\displaystyle\forall s\in\mathcal{S}\text{ and
}a_{1},a_{2}\in\mathcal{A}\text{ with }a_{1}\neq
a_{2}:\qquad\big{|}Q_{{\mathrm{p}}}^{\star}(s,a_{1})-Q_{{\mathrm{p}}}^{\star}(s,a_{2})\big{|}>\frac{\xi\delta(1-\gamma)}{4|\mathcal{S}||\mathcal{A}|^{2}}.$

Consider any state $s$ and any actions $a_{1}\neq a_{2}$. In what follows, we
allow $r_{\mathrm{p}}(s,a_{1})=\tau$ to vary, while _freezing_ the values of
all other rewards
$\\{r_{\mathrm{p}}(\tilde{s},a)\mid(\tilde{s},a)\neq(s,a_{1})\\}$. To
streamline notation, we define

  * •

$\bm{r}_{\tau}=[r_{\tau}(s,a)]_{(s,a)\in\mathcal{S}\times\mathcal{A}}$: the
reward vector such that

$r_{\tau}(s,a_{1})=\tau\qquad\quad\text{and}\qquad\quad
r_{\tau}(\tilde{s},a)=r_{\mathrm{p}}(\tilde{s},a)\quad\text{for all
}(\tilde{s},a)\neq(s,a_{1});$

  * •

$Q_{\tau}^{\star}$: the optimal Q-function when the reward vector is
$\bm{r}_{\tau}$;

  * •

$V_{\tau}^{\star}$: the optimal value function when the reward vector is
$\bm{r}_{\tau}$;

  * •

$\pi_{\tau}^{\star}$: the optimal policy when the reward vector is
$\bm{r}_{\tau}$.

Additionally, we claim for the moment that there exists a phase transition
boundary $\tau_{\mathrm{th}}$ such that

$\displaystyle\pi_{\tau}^{\star}(s)\neq a_{1},\quad$ $\displaystyle\text{for
all }\tau<\tau_{\mathrm{th}};$ (76a)
$\displaystyle\pi_{\tau}^{\star}(s)=a_{1},\quad$ $\displaystyle\text{for all
}\tau>\tau_{\mathrm{th}}.$ (76b)

The proof of this claim is deferred to the end of this section. To establish
Lemma 6, the idea is to control the size of the set

$\displaystyle\mathcal{I}_{0,\omega}:=\left\\{\tau\mid\big{|}Q_{\tau}^{\star}(s,a_{1})-Q_{\tau}^{\star}(s,a_{2})\big{|}<\omega\right\\},$
(77)

for some $\omega>0$ to be specified shortly. As motivated by (76), we further
break down this set into two parts
$\mathcal{I}_{0,\omega}=\mathcal{I}_{1,\omega}\cup\mathcal{I}_{2,\omega}$,
where

$\displaystyle\mathcal{I}_{1,\omega}$
$\displaystyle:=\left\\{\tau\mid\tau<\tau_{\mathrm{th}},\,\big{|}Q_{\tau}^{\star}(s,a_{1})-Q_{\tau}^{\star}(s,a_{2})\big{|}<\omega\right\\},$
(78a) $\displaystyle\mathcal{I}_{2,\omega}$
$\displaystyle:=\left\\{\tau\mid\tau\geq\tau_{\mathrm{th}},\,\big{|}Q_{\tau}^{\star}(s,a_{1})-Q_{\tau}^{\star}(s,a_{2})\big{|}<\omega\right\\}.$
(78b)

In what follows, we first control the size of each set separately, and then
demonstrate that the probability of these events happening is very small.

##### Step 1.

We begin with $\mathcal{I}_{1,\omega}$ associated with the range
$\tau<\tau_{\mathrm{th}}$. In this case, the value function $V_{\tau}^{\star}$
does not vary with $\tau$, since the reward $r_{\mathrm{\tau}}(s,a_{1})=\tau$
is never active when calculating $V_{\tau}^{\star}$ (by virtue of (76a)).
Thus, the Bellman equation allows us to write

$Q_{\tau}^{\star}(s,a_{1})=\tau+B_{1}\qquad\text{and}\qquad
Q_{\tau}^{\star}(s,a_{2})=B_{2},$

where both quantities $B_{1}$ and $B_{2}$ do not depend on the value of
$\tau$. Armed with this observation, we can easily show that: for any
$\omega>0$, the interval $\mathcal{I}_{1,\omega}$ (cf. (78a)) obeys

$\displaystyle\mathcal{I}_{1,\omega}\subseteq\left\\{\tau\mid|\tau+B_{1}-B_{2}|<\omega\right\\},$

and hence has length (or Lebesgue measure) at most $2\omega$.

##### Step 2.

We then move on to $\mathcal{I}_{2,\omega}$ associated with the range
$\tau>\tau_{\mathrm{th}}$ in which case $\pi_{\tau}^{\star}(s)=a_{1}$. Towards
this, we first establish two properties that are useful for our argument.
Define a policy $\pi$ such that

$\displaystyle\pi(s)=a_{2},\qquad\text{and}\quad\quad\pi(\tilde{s})$
$\displaystyle=\pi_{\tau}^{\star}(\tilde{s})\quad\text{for all }\tilde{s}\neq
s;$ (79)

namely, this policy differs from $\pi_{\tau}^{\star}$ only in state $s$.
Suppose that
$\big{|}Q_{\tau}^{\star}(s,a_{1})-Q_{\tau}^{\star}(s,a_{2})\big{|}<\omega$,
then recalling the definitions of ${\bf\Pi}^{\pi}$ and $\bm{P}^{\pi}$ (cf.
(15) and (16)), one has

$\displaystyle\left\|\bm{P}^{\pi_{\tau}^{\star}}\bm{Q}_{\tau}^{\star}-\bm{P}^{\pi}\bm{Q}_{\tau}^{\star}\right\|_{\infty}$
$\displaystyle=\left\|\bm{P}{\bf\Pi}^{\pi_{\tau}^{\star}}\bm{Q}_{\tau}^{\star}-\bm{P}{\bf\Pi}^{\pi}\bm{Q}_{\tau}^{\star}\right\|_{\infty}\leq\left\|\bm{P}\right\|_{1}\left\|{\bf\Pi}^{\pi_{\tau}^{\star}}\bm{Q}_{\tau}^{\star}-{\bf\Pi}^{\pi}\bm{Q}_{\tau}^{\star}\right\|_{\infty}$
$\displaystyle=\left\|{\bf\Pi}^{\pi_{\tau}^{\star}}\bm{Q}_{\tau}^{\star}-{\bf\Pi}^{\pi}\bm{Q}_{\tau}^{\star}\right\|_{\infty}\leq\left|Q_{\tau}^{\star}(s,a_{1})-Q_{\tau}^{\star}(s,a_{2})\right|<\omega.$
(80)

This further leads to an upper bound

$\displaystyle\left\|\bm{Q}_{\tau}^{\star}-(\bm{I}-\gamma\bm{P}^{\pi})^{-1}\bm{r}_{\tau}\right\|_{\infty}$
$\displaystyle=\left\|(\bm{I}-\gamma\bm{P}^{\pi})^{-1}(\bm{I}-\gamma\bm{P}^{\pi})\bm{Q}_{\tau}^{\star}-(\bm{I}-\gamma\bm{P}^{\pi})^{-1}(\bm{I}-\gamma\bm{P}^{\pi_{\tau}^{\star}})\bm{Q}_{\tau}^{\star}\right\|_{\infty}$
$\displaystyle=\gamma\left\|(\bm{I}-\gamma\bm{P}^{\pi})^{-1}(\bm{P}^{\pi_{\tau}^{\star}}\bm{Q}_{\tau}^{\star}-\bm{P}^{\pi}\bm{Q}_{\tau}^{\star})\right\|_{\infty}$
$\displaystyle\leq\gamma\left\|(\bm{I}-\gamma\bm{P}^{\pi})^{-1}\right\|_{1}\big{\|}\bm{P}^{\pi_{\tau}^{\star}}\bm{Q}_{\tau}^{\star}-\bm{P}^{\pi}\bm{Q}_{\tau}^{\star}\big{\|}_{\infty}\leq\frac{\gamma\omega}{1-\gamma},$
(81)

where the last line comes from the inequality (B.5) and Lemma 7(c). In
addition, by virtue of the identity

$\displaystyle(\bm{I}-\gamma\bm{P}^{\pi})^{-1}\bm{r}_{\tau}$
$\displaystyle=\bm{r}_{\tau}+\sum_{i=1}^{\infty}\gamma^{i}(\bm{P}^{\pi})^{i}\bm{r}_{\tau}=\bm{r}_{\tau}+\sum_{i=1}^{\infty}\gamma^{i}(\bm{P}{\bf\Pi}^{\pi})^{i}\bm{r}_{\tau}=\bm{r}_{\tau}+\left\\{\sum_{i=0}^{\infty}\gamma^{i+1}(\bm{P}{\bf\Pi}^{\pi})^{i}\bm{P}\right\\}\left({\bf\Pi}^{\pi}\bm{r}_{\tau}\right),$

one sees that:

$\text{ the }(\tilde{s},a)\text{-th entry of
}(\bm{I}-\gamma\bm{P}^{\pi})^{-1}\bm{r}_{\tau}\text{ does not depend on the
value of }\tau,\quad\quad\forall\,(\tilde{s},a)\neq(s,a_{1}).$ (82)

This observation holds because ${\bf\Pi}^{\pi}\bm{r}_{\tau}$ under the policy
$\pi$ (cf. (79)) does not pick out the value $\bm{r}_{\tau}(s,a_{1})$ and is
hence not a function of $\tau$. In addition, since

$Q_{\tau}^{\star}(s,a_{1})=r(s,a_{1})+\gamma(\bm{P}\bm{V}_{\tau}^{\star})_{s,a_{1}}=\tau+\gamma(\bm{P}\bm{V}_{\tau}^{\star})_{s,a_{1}}$

and $\bm{V}_{\tau}^{\star}$ is clearly monotonically non-decreasing in $\tau$,
we know that

$Q_{\tau_{2}}^{\star}(s,a_{1})-Q_{\tau_{1}}^{\star}(s,a_{1})\geq\tau_{2}-\tau_{1}$
(83)

for any $\tau_{2}>\tau_{1}\geq\tau_{\mathrm{th}}$. These two observations (cf.
(82) and (83)) play crucial roles in this step.

We are now well equipped to control the size of the set
$\mathcal{I}_{2,\omega}$. In particular, if we define

$\tau_{0}:=\inf\left\\{\tau\mid\tau\geq\tau_{\mathrm{th}},\,\big{|}Q_{\tau}^{\star}(s,a_{1})-Q_{\tau}^{\star}(s,a_{2})\big{|}<\omega\right\\},$

we shall demonstrate that
$\mathcal{I}_{2,\omega}\subseteq\big{[}\tau_{0},\tau_{0}+\frac{2\omega}{1-\gamma}\big{]}.$
To show this, we observe that for any
$\tau\geq\tau_{0}+\frac{2\omega}{1-\gamma}=:\widetilde{\tau}_{0}$, it follows
from (83) that

$Q_{\tau}^{\star}(s,a_{1})\geq Q_{\tau_{0}}^{\star}(s,a_{1})+\tau-\tau_{0}\geq
Q_{\tau_{0}}^{\star}(s,a_{1})+\frac{2\omega}{1-\gamma}.$ (84)

In addition, for any $\tau\geq\widetilde{\tau}_{0}$ obeying

$\big{|}Q_{\tau}^{\star}(s,a_{1})-Q_{\tau}^{\star}(s,a_{2})\big{|}<\omega,$
(85)

the triangle inequality gives

$\displaystyle\left|Q_{\tau_{0}}^{\star}(s,a_{2})-Q_{\tau}^{\star}(s,a_{2})\right|$
$\displaystyle\leq\left\|\bm{Q}_{\tau_{0}}^{\star}-(\bm{I}-\gamma\bm{P}^{\pi})^{-1}\bm{r}_{\tau_{0}}\right\|_{\infty}+|((\bm{I}-\gamma\bm{P}^{\pi})^{-1}\bm{r}_{\tau_{0}})_{s,a_{2}}-((\bm{I}-\gamma\bm{P}^{\pi})^{-1}\bm{r}_{\tau})_{s,a_{2}}|+\left\|(\bm{I}-\gamma\bm{P}^{\pi})^{-1}\bm{r}_{\tau}-\bm{Q}_{\tau}^{\star}\right\|_{\infty}$
$\displaystyle\leq\frac{2\gamma\omega}{1-\gamma},$

where the last inequality invokes the facts (81) and (82). This together with
(76b) and (84) yields

$\displaystyle Q_{\tau}^{\star}(s,a_{1})-Q_{\tau}^{\star}(s,a_{2})$
$\displaystyle\geq\left(Q_{\tau}^{\star}(s,a_{1})-Q_{\tau_{0}}^{\star}(s,a_{1})\right)+\left(Q_{\tau_{0}}^{\star}(s,a_{1})-Q_{\tau_{0}}^{\star}(s,a_{2})\right)-\left|Q_{\tau_{0}}^{\star}(s,a_{2})-Q_{\tau}^{\star}(s,a_{2})\right|$
$\displaystyle\geq\frac{2\omega}{1-\gamma}+0-\frac{2\gamma\omega}{1-\gamma}>\omega,$

which clearly violates (85). In other words, any $\tau\geq\tau_{\mathrm{th}}$
obeying (85) necessarily resides within the interval
$\big{[}\tau_{0},\tau_{0}+\frac{2\omega}{1-\gamma}\big{]}$, namely,
$\mathcal{I}_{2,\omega}\subset\big{[}\tau_{0},\tau_{0}+\frac{2\omega}{1-\gamma}\big{]}.$

##### Step 3.

Putting the above results together, the set $\mathcal{I}_{0,\omega}$ (cf.
(77)) has total length (or Lebesgue measure) at most
$\frac{4\omega}{1-\gamma}$. Given that $r_{\mathrm{p}}(s,a)=r(s,a)+\zeta(s,a)$
with $\zeta(s,a)\sim\mathsf{Unif}(0,\xi)$, one has

$\displaystyle\mathbb{P}\left\\{\big{|}Q_{{\mathrm{p}}}^{\star}(s,a_{1})-Q_{{\mathrm{p}}}^{\star}(s,a_{2})\big{|}<\omega\right\\}$
$\displaystyle\leq\mathbb{P}\left\\{r(s,a)+\zeta(s,a)\in\mathcal{I}_{0,\omega}\right\\}\leq\frac{4\omega}{\xi(1-\gamma)}.$

By setting
$\omega=\frac{\delta(1-\gamma)\xi}{4|\mathcal{S}||\mathcal{A}|^{2}}$, we
arrive at

$\displaystyle\mathbb{P}\left\\{\big{|}Q_{{\mathrm{p}}}^{\star}(s,a_{1})-Q_{{\mathrm{p}}}^{\star}(s,a_{2})\big{|}<\frac{\delta(1-\gamma)\xi}{4|\mathcal{S}||\mathcal{A}|^{2}}\right\\}$
$\displaystyle\leq\frac{\delta}{|\mathcal{S}||\mathcal{A}|^{2}}.$

Finally, taking the union bound over all $s,a_{1},a_{2}$, we conclude that

$\displaystyle\mathbb{P}\left\\{\exists s,a_{1}\neq a_{2}:\text{
}\big{|}Q_{{\mathrm{p}}}^{\star}(s,a_{1})-Q_{{\mathrm{p}}}^{\star}(s,a_{2})\big{|}<\frac{\delta(1-\gamma)\xi}{4|\mathcal{S}||\mathcal{A}|^{2}}\right\\}$
$\displaystyle\leq\delta,$

thus establishing Lemma 6 as long as the claim (76) holds.

###### Proof of the claim (76).

To establish the claim, it suffices to take

$\tau_{\mathrm{th}}=\sup\left\\{u\mid\pi_{\tau}^{\star}(s)\neq a_{1}\text{ for
all }\tau<u\right\\}.$ (86)

It thus suffices to verify (76b) for our choice (86). Towards this, suppose
instead that there exist some
$\tau_{3}<\tau_{\mathrm{th}}\leq\tau_{2}<\tau_{1}$ such that

$\pi_{\tau_{3}}^{\star}(s)\neq
a_{1},\qquad\pi_{\tau_{2}}^{\star}(s)=a_{1},\qquad\text{and}\qquad\pi_{\tau_{1}}^{\star}(s)\neq
a_{1}.$

It is straightforward to see that $V_{\tau_{1}}^{\star}=V_{\tau_{3}}^{\star}$,
since in both cases, the reward $r_{\mathrm{\tau}}(s,a_{1})$ does not enter
the calculation of the optimal value function (while the rewards in other
state-action pairs are identical in both cases). In view of the monotonicity
of the value function w.r.t. the reward vector, we have

$V_{\tau_{1}}^{\star}=V_{\tau_{2}}^{\star}=V_{\tau_{3}}^{\star}.$

However, this contradicts our assumption that $a_{1}$ is the optimal action
for state $s$ at $\tau_{2}$ but not at $\tau_{3}$, since enlarging $\tau_{2}$
to $\tau_{3}$ otherwise will enlarge the optimal value function
$V_{\tau_{3}}^{\star}$. We have thus established (76). ∎

## References

  * Agarwal et al., (2019) Agarwal, A., Kakade, S., and Yang, L. F. (2019).  Model-based reinforcement learning with a generative model is minimax optimal.  arXiv preprint arXiv:1906.03804.
  * Azar et al., (2012) Azar, M. G., Munos, R., and Kappen, B. (2012).  On the sample complexity of reinforcement learning with a generative model.  arXiv preprint arXiv:1206.6461.
  * Azar et al., (2013) Azar, M. G., Munos, R., and Kappen, H. J. (2013).  Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model.  Machine learning, 91(3):325–349.
  * Azar et al., (2017) Azar, M. G., Osband, I., and Munos, R. (2017).  Minimax regret bounds for reinforcement learning.  In Proceedings of the 34th International Conference on Machine Learning-Volume 70, pages 263–272. JMLR. org.
  * Beck and Srikant, (2012) Beck, C. L. and Srikant, R. (2012).  Error bounds for constant step-size Q-learning.  Systems & control letters, 61(12):1203–1208.
  * Bellman, (1952) Bellman, R. (1952).  On the theory of dynamic programming.  Proceedings of the National Academy of Sciences of the United States of America, 38(8):716.
  * Bertsekas, (2017) Bertsekas, D. P. (2017).  Dynamic programming and optimal control (4th edition).  Athena Scientific.
  * Bhandari et al., (2018) Bhandari, J., Russo, D., and Singal, R. (2018).  A finite time analysis of temporal difference learning with linear function approximation.  In Conference On Learning Theory, pages 1691–1692.
  * Bradtke and Barto, (1996) Bradtke, S. J. and Barto, A. G. (1996).  Linear least-squares algorithms for temporal difference learning.  Machine learning, 22(1-3):33–57.
  * Cai et al., (2019) Cai, Q., Yang, Z., Lee, J. D., and Wang, Z. (2019).  Neural temporal-difference learning converges to global optima.  In Advances in Neural Information Processing Systems, pages 11312–11322.
  * Chen et al., (2019) Chen, Y., Fan, J., Ma, C., and Wang, K. (2019).  Spectral method and regularized mle are both optimal for top-k ranking.  Annals of statistics, 47(4):2204.
  * Chen et al., (2020) Chen, Z., Maguluri, S. T., Shakkottai, S., and Shanmugam, K. (2020).  Finite-sample analysis of stochastic approximation using smooth convex envelopes.  arXiv preprint arXiv:2002.00874.
  * Dalal et al., (2018) Dalal, G., Szörényi, B., Thoppe, G., and Mannor, S. (2018).  Finite sample analyses for TD(0) with function approximation.  In Thirty-Second AAAI Conference on Artificial Intelligence.
  * Dann and Brunskill, (2015) Dann, C. and Brunskill, E. (2015).  Sample complexity of episodic fixed-horizon reinforcement learning.  In Advances in Neural Information Processing Systems, pages 2818–2826.
  * Duan and Wang, (2020) Duan, Y. and Wang, M. (2020).  Minimax-optimal off-policy evaluation with linear function approximation.  arXiv preprint arXiv:2002.09516.
  * El Karoui, (2015) El Karoui, N. (2015).  On the impact of predictor geometry on the performance on high-dimensional ridge-regularized generalized robust regression estimators.  Probability Theory and Related Fields, pages 1–81.
  * Even-Dar and Mansour, (2003) Even-Dar, E. and Mansour, Y. (2003).  Learning rates for Q-learning.  Journal of machine learning Research, 5(Dec):1–25.
  * Gupta et al., (2019) Gupta, H., Srikant, R., and Ying, L. (2019).  Finite-time performance bounds and adaptive learning rate selection for two time-scale reinforcement learning.  In Advances in Neural Information Processing Systems, pages 4706–4715.
  * Jaakkola et al., (1994) Jaakkola, T., Jordan, M. I., and Singh, S. P. (1994).  Convergence of stochastic iterative dynamic programming algorithms.  In Advances in neural information processing systems, pages 703–710.
  * Jiang and Agarwal, (2018) Jiang, N. and Agarwal, A. (2018).  Open problem: The dependence of sample complexity lower bounds on planning horizon.  In Conference On Learning Theory, pages 3395–3398.
  * Jin et al., (2018) Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018).  Is Q-learning provably efficient?  In Advances in Neural Information Processing Systems, pages 4863–4873.
  * Jin et al., (2019) Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2019).  Provably efficient reinforcement learning with linear function approximation.  arXiv preprint arXiv:1907.05388.
  * Kakade, (2003) Kakade, S. (2003).  On the sample complexity of reinforcement learning.  PhD thesis, University of London.
  * Kaledin et al., (2020) Kaledin, M., Moulines, E., Naumov, A., Tadic, V., and Wai, H.-T. (2020).  Finite time analysis of linear two-timescale stochastic approximation with Markovian noise.  arXiv preprint arXiv:2002.01268.
  * Kearns et al., (2002) Kearns, M., Mansour, Y., and Ng, A. Y. (2002).  A sparse sampling algorithm for near-optimal planning in large Markov decision processes.  Machine learning, 49(2-3):193–208.
  * Kearns and Singh, (1999) Kearns, M. J. and Singh, S. P. (1999).  Finite-sample convergence rates for Q-learning and indirect algorithms.  In Advances in neural information processing systems, pages 996–1002.
  * Khamaru et al., (2020) Khamaru, K., Pananjady, A., Ruan, F., Wainwright, M. J., and Jordan, M. I. (2020).  Is temporal difference learning optimal? an instance-dependent analysis.  arXiv preprint arXiv:2003.07337.
  * Lakshminarayanan and Szepesvari, (2018) Lakshminarayanan, C. and Szepesvari, C. (2018).  Linear stochastic approximation: How far does constant step-size and iterate averaging go?  In International Conference on Artificial Intelligence and Statistics, pages 1347–1355.
  * Lattimore and Hutter, (2012) Lattimore, T. and Hutter, M. (2012).  PAC bounds for discounted MDPs.  In International Conference on Algorithmic Learning Theory, pages 320–334. Springer.
  * Ma et al., (2020) Ma, C., Wang, K., Chi, Y., and Chen, Y. (2020).  Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion and blind deconvolution.  Foundations of Computational Mathematics, 20(3):451–632.
  * Mou et al., (2020) Mou, W., Li, C. J., Wainwright, M. J., Bartlett, P. L., and Jordan, M. I. (2020).  On linear stochastic approximation: Fine-grained Polyak-Ruppert and non-asymptotic concentration.  arXiv preprint arXiv:2004.04719.
  * Pananjady and Wainwright, (2019) Pananjady, A. and Wainwright, M. J. (2019).  Value function estimation in Markov reward processes: Instance-dependent $\ell_{\infty}$-bounds for policy evaluation.  arXiv preprint arXiv:1909.08749.
  * Puterman, (2014) Puterman, M. L. (2014).  Markov decision processes: discrete stochastic dynamic programming.  John Wiley & Sons.
  * Qu and Wierman, (2020) Qu, G. and Wierman, A. (2020).  Finite-time analysis of asynchronous stochastic approximation and Q-learning.  arXiv preprint arXiv:2002.00260.
  * Shah and Xie, (2018) Shah, D. and Xie, Q. (2018).  Q-learning with nearest neighbors.  In Advances in Neural Information Processing Systems, pages 3111–3121.
  * (36) Sidford, A., Wang, M., Wu, X., Yang, L., and Ye, Y. (2018a).  Near-optimal time and sample complexities for solving Markov decision processes with a generative model.  In Advances in Neural Information Processing Systems, pages 5186–5196.
  * (37) Sidford, A., Wang, M., Wu, X., and Ye, Y. (2018b).  Variance reduced value iteration and faster algorithms for solving Markov decision processes.  In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 770–787. SIAM.
  * Srikant and Ying, (2019) Srikant, R. and Ying, L. (2019).  Finite-time error bounds for linear stochastic approximation and TD learning.  In Conference on Learning Theory, pages 2803–2830.
  * Strehl et al., (2006) Strehl, A. L., Li, L., Wiewiora, E., Langford, J., and Littman, M. L. (2006).  PAC model-free reinforcement learning.  In Proceedings of the 23rd international conference on Machine learning, pages 881–888.
  * Sutton and Barto, (2018) Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Szepesvári, (1998) Szepesvári, C. (1998).  The asymptotic convergence-rate of Q-learning.  In Advances in Neural Information Processing Systems, pages 1064–1070.
  * Szepesvári, (2010) Szepesvári, C. (2010).  Algorithms for reinforcement learning.  Synthesis lectures on artificial intelligence and machine learning, 4(1):1–103.
  * Tsitsiklis and Van Roy, (1997) Tsitsiklis, J. and Van Roy, B. (1997).  An analysis of temporal-difference learning with function approximation.  IEEE Transactions on Automatic Control, 42(5):674–690.
  * Tsitsiklis, (1994) Tsitsiklis, J. N. (1994).  Asynchronous stochastic approximation and Q-learning.  Machine learning, 16(3):185–202.
  * Tu and Recht, (2018) Tu, S. and Recht, B. (2018).  The gap between model-based and model-free methods on the linear quadratic regulator: An asymptotic viewpoint.  arXiv preprint arXiv:1812.03565.
  * Vershynin, (2018) Vershynin, R. (2018).  High-dimensional probability: An introduction with applications in data science, volume 47.  Cambridge university press.
  * (47) Wainwright, M. J. (2019a).  Stochastic approximation with cone-contractive operators: Sharp $\ell_{\infty}$-bounds for Q-learning.  arXiv preprint arXiv:1905.06265.
  * (48) Wainwright, M. J. (2019b).  Variance-reduced Q-learning is minimax optimal.  arXiv preprint arXiv:1906.04697.
  * Wang, (2019) Wang, M. (2019).  Randomized linear programming solves the Markov decision problem in nearly linear (sometimes sublinear) time.  Mathematics of Operations Research.
  * Xu and Gu, (2019) Xu, P. and Gu, Q. (2019).  A finite-time analysis of Q-learning with neural network function approximation.  arXiv preprint arXiv:1912.04511.
  * Xu et al., (2019) Xu, T., Zou, S., and Liang, Y. (2019).  Two time-scale off-policy TD learning: Non-asymptotic analysis over Markovian samples.  In Advances in Neural Information Processing Systems, pages 10633–10643.