# Settling the Sample Complexity of
Model-Based Offline Reinforcement Learning

Gen Li
UPenn
Department of Statistics and Data Science, Wharton School, University of
Pennsylvania, Philadelphia, PA 19104, USA. Laixi Shi
CMU
Department of Electrical and Computer Engineering, Carnegie Mellon University,
Pittsburgh, PA 15213, USA. Yuxin Chen11footnotemark: 1
UPenn
Department of Electrical and Systems Engineering, University of Pennsylvania,
Philadelphia, PA 19104, USA. Yuejie Chi22footnotemark: 2
CMU
Yuting Wei11footnotemark: 1
UPenn

(April 2022; Revised: February 2024)

###### Abstract

This paper is concerned with offline reinforcement learning (RL), which learns
using pre-collected data without further exploration. Effective offline RL
would be able to accommodate distribution shift and limited data coverage.
However, prior algorithms or analyses either suffer from suboptimal sample
complexities or incur high burn-in cost to reach sample optimality, thus
posing an impediment to efficient offline RL in sample-starved applications.

We demonstrate that the model-based (or “plug-in”) approach achieves minimax-
optimal sample complexity without burn-in cost for tabular Markov decision
processes (MDPs). Concretely, consider a $\gamma$-discounted infinite-horizon
(resp. finite-horizon) MDP with $S$ states and effective horizon
$\frac{1}{1-\gamma}$ (resp. horizon $H$), and suppose the distribution shift
of data is reflected by some single-policy clipped concentrability coefficient
$C^{\star}_{\mathsf{clipped}}$. We prove that model-based offline RL yields
$\varepsilon$-accuracy with a sample complexity of

$\begin{cases}\frac{SC_{\mathsf{clipped}}^{\star}}{(1-\gamma)^{3}\varepsilon^{2}}&(\text{infinite-
horizon MDPs})\\\
\frac{H^{4}SC_{\mathsf{clipped}}^{\star}}{\varepsilon^{2}}&(\text{finite-
horizon MDPs})\end{cases}$

up to log factor, which is minimax optimal for the entire $\varepsilon$-range.
The proposed algorithms are “pessimistic” variants of value iteration with
Bernstein-style penalties, and do not require sophisticated variance
reduction. Our analysis framework is established upon delicate leave-one-out
decoupling arguments in conjunction with careful self-bounding techniques
tailored to MDPs.

Keywords: offline reinforcement learning, model-based approach, minimax lower
bounds, distribution shift, pessimism in the face of uncertainty

###### Contents

  1. 1 Introduction
    1. 1.1 Challenges: distribution shift and limited data coverage
    2. 1.2 Inadequacy of prior works
    3. 1.3 Main contributions
    4. 1.4 Notation
  2. 2 Algorithm and theory: discounted infinite-horizon MDPs
    1. 2.1 Models and assumptions
    2. 2.2 Algorithm: VI-LCB for infinite-horizon MDPs
    3. 2.3 Performance guarantees
  3. 3 Algorithm and theory: episodic finite-horizon MDPs
    1. 3.1 Models and assumptions
    2. 3.2 A model-based offline RL algorithm: VI-LCB
    3. 3.3 VI-LCB with two-fold subsampling
    4. 3.4 Performance guarantees
  4. 4 Numerical experiments
  5. 5 Related works
  6. 6 Analysis: discounted infinite-horizon MDPs
    1. 6.1 Preliminary facts
    2. 6.2 Proof of Theorem 5
  7. 7 Analysis: episodic finite-horizon MDPs
    1. 7.1 Preliminary facts and notation
    2. 7.2 A crucial statistical independence property
    3. 7.3 Proof of Theorem 3
  8. 8 Discussion
  9. A Proof of auxiliary lemmas: infinite-horizon MDPs
    1. A.1 Proof of Lemma 1
    2. A.2 Proof of Lemma 2
    3. A.3 Proof of Lemma 4
    4. A.4 Proof of Lemma 5
  10. B Proof of auxiliary lemmas: episodic finite-horizon MDPs
    1. B.1 Proof of Lemma 3
    2. B.2 Proof of the instance-dependent statistical bound (65)
  11. C Proof of minimax lower bounds
    1. C.1 Preliminary facts
    2. C.2 Proof of Theorem 2
    3. C.3 Proof of Theorem 4

##  1 Introduction

Reinforcement learning (RL) has recently achieved superhuman performance in
the gaming frontier, such as the game of Go (Silver et al.,, 2017), under the
premise that vast amounts of training data can be obtained. However, limited
capability of online data collection in other real-world applications — e.g.,
clinical trials and online advertising, where real-time data acquisition is
expensive, high-stakes, and/or time-consuming, — presents a fundamental
bottleneck for carrying such RL success over to broader scenarios. To
circumvent this bottleneck, one plausible strategy is to make more effective
use of data collected previously, given that such historical data might
contain useful information that readily transfers to new tasks (for instance,
the state transitions in a historical task might sometimes resemble what
happen in new tasks). The potential of this data-driven approach has been
explored and recognized in a diverse array of contexts including but not
limited to robotic manipulation (Ebert et al.,, 2018), autonomous driving
(Diehl et al.,, 2021), and healthcare (Tang and Wiens,, 2021); see Levine et
al., (2020); Prudencio et al., (2022) for overviews of recent development.
Nowadays, the subfield of reinforcement learning using historical data,
without further exploration of the environment, is commonly referred to as
offline RL or batch RL (Lange et al.,, 2012; Levine et al.,, 2020). A desired
offline RL algorithm would achieve the target statistical accuracy using as
few samples as possible.

###  1.1 Challenges: distribution shift and limited data coverage

In contrast to online exploratory RL, offline RL has to deal with several
critical issues resulting from the absence of active exploration. Below we
single out two representative issues surrounding offline RL.

  * •

Distribution shift. For the most part, the historical data is generated by a
certain behavior policy that departs from the optimal one. A key challenge in
offline RL thus stems from the shift of data distributions: how to leverage
past data to the most effect, even though the distribution induced by the
target policy differs from what we have available?

  * •

Limited data coverage. Ideally, if the dataset contained sufficiently many
data samples for every state-action pair, then there would be hope to
simultaneously learn the performance of every policy. Such a uniform coverage
requirement, however, is oftentimes not only unrealistic (given that we can no
longer change the past data) but also unnecessary (given that we might only be
interested in identifying a single optimal policy).

Whether one can effectively cope with distribution shift and insufficient data
coverage becomes a major factor that governs the feasibility and statistical
efficiency of offline RL.

In order to address the aforementioned issues, a recent strand of works put
forward the principle of pessimism or conservatism (e.g., Buckman et al.,
(2020); Kumar et al., (2020); Jin et al., (2021); Rashidinejad et al., (2022);
Xie et al., (2021); Yin and Wang, (2021); Shi et al., 2022b ; Yan et al.,
(2023); Uehara and Sun, (2021); Liu et al., (2020); Cui and Du, (2022); Chen
et al., 2021a ; Zhong et al., (2022); Zanette et al., (2021)). This is
reminiscent of the optimism principle in the face of uncertainty for online
exploration (Lai and Robbins,, 1985; Jaksch et al.,, 2010; Azar et al.,, 2017;
Bourel et al.,, 2020; Jin et al.,, 2018), but works for drastically different
reasons (as we shall elucidate momentarily). One plausible idea of the
pessimism principle, which has been incorporated into both model-based and
model-free approaches, is to penalize value estimation of those state-action
pairs that have been poorly covered. Informally speaking, insufficient
coverage of a state-action pair inevitably results in low confidence and high
uncertainty in the associated value estimation, and it is hence advisable to
act cautiously by tuning down the corresponding value estimate. Proper use of
pessimism amid uncertainty brings about several provable benefits
(Rashidinejad et al.,, 2022; Xie et al.,, 2021): (i) it allows for a reduced
sample size that adapts to the degree of distribution shift; (ii) as opposed
to uniform data coverage, it only requires coverage of the part of the state-
action space reachable by the target policy. Details to follow momentarily.

###  1.2 Inadequacy of prior works

In the present paper, we evaluate and compare the statistical performance of
offline RL algorithms mainly through the lens of sample complexity — namely,
the number of samples needed for an algorithm to output, with probability
approaching one, a policy whose resultant value function is at most
$\varepsilon$ away from optimal (called “$\varepsilon$-accuracy” throughout).
An ultimate goal is to design an algorithm to achieve the smallest possible
sample complexity.

Despite extensive recent activities, however, existing statistical guarantees
for the above paradigm remain inadequate, as we shall elaborate on below. For
concreteness, our discussions focus on two widely studied Markov decision
processes (MDPs) with $S$ states and $A$ actions (Bertsekas,, 2017): (a)
$\gamma$-discounted infinite-horizon MDPs, with effective horizon
$\frac{1}{1-\gamma}$; (b) finite-horizon MDPs with horizon length $H$ and
nonstationary transition kernels. We shall bear in mind that all of these
salient problem parameters (i.e., $S$, $A$, $\frac{1}{1-\gamma}$, $H$) could
be enormous in modern RL applications. In addition, previous works have
isolated an important parameter $C^{\star}\geq 1$ — called the single-policy
concentrability coefficient (Rashidinejad et al.,, 2022; Xie et al.,, 2021) —
that measures the mismatch of distributions induced by the target policy
against the behavior policy; see Sections 3.1 and 2.1 for precise definitions.
Naturally, the statistical performance of desirable algorithms would degrade
gracefully as the distribution mismatch worsens (i.e., as $C^{\star}$
increases). In the sequel, we shall discuss two dinstinctive RL paradigms —
model-based RL and model-free RL — separately. Throughout this paper, the
standard notation $\widetilde{O}(\cdot)$ indicates the order of a function
with all log terms in $S,A,\frac{1}{1-\gamma},H,\frac{1}{\varepsilon},$ and
$\frac{1}{\delta}$ (with $1-\delta$ the target success probability) hidden.

|
---|---
(a) discounted infinite-horizon MDPs | (b) finite-horizon MDPs
Figure 1:  An illustration of prior works, where (a) is about discounted
infinite-horizon MDPs and (b) is about finite-horizon MDPs. To facilitate
comparisons, we replace $C^{\star}_{\mathsf{clipped}}$ with $C^{\star}$ in our
results when drawing the plots given that $C^{\star}_{\mathsf{clipped}}\leq
C^{\star}$. The shaded regions indicate the state-of-the-art achievability
results. Our work manages to close the gaps between the prior achievable
regions and the minimax lower bounds.

##### Model-based offline RL.

Model-based algorithms — which can be interpreted as a “plug-in” statistical
approach — start by computing an empirical model for the unknown MDP, and
output a policy that is (near)-optimal in accordance with the empirical MDP.
When coupled with the pessimism principle, the model-based approach has been
shown to enjoy the following sample complexity bounds.

  * •

By incorporating Hoeffding-style lower confidence bounds into value iteration,
Rashidinejad et al., (2022); Xie et al., (2021) demonstrated that a sample
complexity of

$\displaystyle\begin{cases}\widetilde{O}\big{(}\frac{SC^{\star}}{(1-\gamma)^{5}\varepsilon^{2}}\big{)}\quad&\text{for
infinite-horizon MDPs}\\\
\widetilde{O}\big{(}\frac{H^{6}SC^{\star}}{\varepsilon^{2}}\big{)}\quad&\text{for
finite-horizon MDPs}\end{cases}$ (1)

suffices to yield $\varepsilon$-accuracy. Such a sample complexity bound,
however, is a large factor of $\frac{1}{(1-\gamma)^{2}}$ (resp. $H^{2}$) above
the minimax lower limit derived for infinite-horizon MDPs (resp. finite-
horizon MDPs) (Rashidinejad et al.,, 2022; Xie et al.,, 2021; Yin and Wang,,
2021).

  * •

In an attempt to optimize the sample complexity, Xie et al., (2021) leveraged
the idea of variance reduction — a powerful strategy originating from the
stochastic optimization literature (Johnson and Zhang,, 2013) — in model-based
RL and obtained a strengthened sample complexity of

$\displaystyle\widetilde{O}\Big{(}\frac{H^{4}SC^{\star}}{\varepsilon^{2}}+\frac{H^{6.5}SC^{\star}}{\varepsilon}\Big{)}$
(2)

for finite-horizon MDPs. This sample complexity bound approaches the minimax
lower limit (i.e., the order of $\frac{H^{4}SC^{\star}}{\varepsilon^{2}}$)
once the sample size exceeds the order of

$\displaystyle\text{(burn-in cost)}\qquad H^{9}SC^{\star};$ (3)

in other words, an enormous burn-in sample size is needed in order to attain
sample optimality.

##### Model-free offline RL.

The model-free approach forms a contrastingly different class of RL
algorithms, which bypasses the model estimation stage and directly learns the
optimal values. Noteworthily, Q-learning and its variants (Watkins and Dayan,,
1992), which apply stochastic approximation (Robbins and Monro,, 1951) based
on the Bellman optimality condition, are among the most widely used model-free
paradigms. The principle of pessimism amid uncertainty has recently been
integrated into model-free algorithms as well, with the state-of-the-art
statistical guarantees listed below (Shi et al., 2022b, ; Yan et al.,, 2023).

  * •

When Q-learning is implemented in conjunction with Hoeffding-style lower
confidence bounds, it has been shown to achieve the same sample complexity as
(1), which is suboptimal by a factor of either $\frac{1}{(1-\gamma)^{2}}$ or
$H^{2}$.

  * •

A variance-reduced variant of pessimistic Q-learning allows for further sample
size benefits, achieving a sample complexity of

$\displaystyle\begin{cases}\widetilde{O}\big{(}\frac{SC^{\star}}{(1-\gamma)^{3}\varepsilon^{2}}+\frac{SC^{\star}}{(1-\gamma)^{4}\varepsilon}\big{)}\quad&\text{for
infinite-horizon MDPs}\\\
\widetilde{O}\big{(}\frac{H^{4}SC^{\star}}{\varepsilon^{2}}+\frac{H^{5}SC^{\star}}{\varepsilon}\big{)}\quad&\text{for
finite-horizon MDPs}\end{cases}$ (4)

for any target accuracy level $\varepsilon$. This means that the algorithm is
guaranteed to be sample-optimal only after the total sample size exceeds the
order of

$\displaystyle\text{(burn-in
cost)}\qquad\begin{cases}\frac{SC^{\star}}{(1-\gamma)^{5}}\quad&\text{for
infinite-horizon MDPs},\\\ H^{6}SC^{\star}\quad&\text{for finite-horizon
MDPs},\end{cases}$ (5)

which again manifests itself as a significant burn-in cost for long-horizon
problems.

##### Summary.

As elucidated above, existing algorithms either suffer from suboptimal sample
complexities, or require sophisticated techniques like variance reduction to
approach minimax optimality. Even when variance reduction is employed, prior
algorithms incur an enormous burn-in cost in order to work optimally, thus
posing an impediment to achieving sample efficiency in data-starved
applications. Table 1 summarizes quantitatively the previous results, whereas
Figure 1 illustrates the gaps between the state-of-the-art upper bounds and
the minimax lower bounds (as derived by Xie et al., (2021); Rashidinejad et
al., (2022)). All this motivates the studies of the following natural
questions:

  * Can we develop an offline RL algorithm that achieves near-optimal sample complexity without burn-in cost? If so, can we accomplish this goal by means of a simple algorithm without resorting to sophisticated schemes like variance reduction?

The current paper answers these questions affirmatively by studying the model-
based approach.

###  1.3 Main contributions

In this paper, we settle the sample complexity of model-based offline RL by
studying a pessimistic variant of value iteration — called VI-LCB — applied to
some empirical MDP. Encouragingly, for both discounted infinite-horizon and
finite-horizon MDPs, the model-based algorithms provably achieve minimax-
optimal sample complexities for any given target accuracy level $\varepsilon$
— namely, any $\varepsilon\in\big{(}0,\frac{1}{1-\gamma}\big{]}$ for
discounted infinite-horizon MDPs and $\varepsilon\in(0,H]$ for finite-horizon
MDPs.

To be more precise, we introduce a slightly modified version
$C^{\star}_{\mathsf{clipped}}$ of the concentrability coefficient $C^{\star}$,
which always satisfies $C^{\star}_{\mathsf{clipped}}\leq C^{\star}$ and shall
be termed the single-policy clipped concentrability coefficient (see Sections
2.1 and 3.1 for more details as well as the advantages of this coefficient).
The introduction of this new parameter leads to slightly improved sample
complexity compared to the one based on $C^{\star}$. The main contributions
are summarized as follows.

  * •

For $\gamma$-discounted infinite-horizon MDPs, we demonstrate that with high
probability, the VI-LCB algorithm with Bernstein-style penalty finds an
$\varepsilon$-optimal policy with a sample complexity of

$\widetilde{O}\bigg{(}\frac{SC^{\star}_{\mathsf{clipped}}}{(1-\gamma)^{3}\varepsilon^{2}}\bigg{)}$
(6)

for any given accuracy level
$\varepsilon\in\big{(}0,\frac{1}{1-\gamma}\big{]}$ (see Theorem 1). Our
algorithm reuses all samples across all iterations in order to achieve data
efficiency, and our analysis builds upon a novel leave-one-out argument to
decouple complicated statistical dependency across iterations. Moreover, the
above sample complexity (6) remains valid if $C^{\star}_{\mathsf{clipped}}$ is
replaced by $C^{\star}$.

  * •

For finite-horizon MDPs with nonstationary transition kernels, we propose a
variant of VI-LCB that adopts the Bernstein-style penalty to enforce pessimism
in the face of uncertainty. We prove that for any given $\varepsilon\in(0,H]$,
the proposed algorithm yields an $\varepsilon$-optimal policy using

$\widetilde{O}\bigg{(}\frac{H^{4}SC^{\star}_{\mathsf{clipped}}}{\varepsilon^{2}}\bigg{)}$
(7)

samples with high probability (see Theorem 3). A key ingredient in the
algorithm design is a two-fold subsampling trick that helps decouple the
statistical dependency along the sample rollouts. Note that the above sample
complexity result (7) continues to hold if one replaces
$C^{\star}_{\mathsf{clipped}}$ with $C^{\star}$.

  * •

To assess the tightness and optimality of our results, we further develop
minimax lower bounds in Theorems 2 and 4, which match the above upper bounds
modulo some logarithmic factors.

Remarkably, our algorithms do not require sophisticated variance reduction
schemes, as long as suitable confidence bounds are adopted. Detailed
theoretical comparisons with prior art can be found in Table 1 and are also
illustrated in Figure 1. Finally, we have conducted a series of numerical
experiments to evaluate the performance of the proposed algorithms in Section
4.

##### Statistical contributions: solving the most sample-hungry regime.

The offline RL problem considered herein is statistical in nature, in that it
seeks to learn from pre-collected data in the face of uncertainty. As far we
know, our theory is the first to identify an offline algorithm that provably
attains minimax-optimal statistical efficiency for the entire
$\varepsilon$-range, which in turn makes clear that no burn-in phase is needed
to achieve optimal statistical accuracy. Achieving this requires developing a
new suite of statistical theory that works all the way to the most data-hungry
regime. It is noteworthy that the existing statistical toolbox — not merely
for offline RL, but for online exploratory RL as well (as we shall detail in
Section 5) — is only guaranteed to work when the total sample size already
exceeds a fairly large threshold, a (often unnecessary) requirement that
substantially simplifies statistical analysis. In this sense, the regime we
aim to solve is reminiscent of the subfield of high-dimensional statistics
(Wainwright, 2019a, ; Donoho et al.,, 2000) that helps extend the frontier of
classical statistics to the sample-starved regime, for which an enriched
statistical toolbox is critically needed.

horizon | algorithm | sample |  $\varepsilon$-range to attain | type
---|---|---|---|---
complexity | sample optimality
infinite | VI-LCB | $\frac{SC^{\star}}{(1-\gamma)^{5}\varepsilon^{2}}$ | —— | model-based
(Rashidinejad et al.,, 2022)
Q-LCB | $\frac{SC^{\star}}{(1-\gamma)^{5}\varepsilon^{2}}$ | —— | model-free
(Yan et al.,, 2023)
VR-Q-LCB | $\frac{SC^{\star}}{(1-\gamma)^{3}\varepsilon^{2}}+\frac{SC^{\star}}{(1-\gamma)^{4}\varepsilon}$ | $(0,1-\gamma]$ | model-free
(Yan et al.,, 2023)
VI-LCB |  |  |
(this paper: Theorem 1) | $\frac{SC^{\star}_{\mathsf{clipped}}}{(1-\gamma)^{3}\varepsilon^{2}}$ ($\leq\frac{SC^{\star}}{(1-\gamma)^{3}\varepsilon^{2}}$) | $\big{(}0,\frac{1}{1-\gamma}\big{]}$ | model-based
|  lower bound |  |  |
| (this paper: Theorem 2) | $\frac{SC^{\star}_{\mathsf{clipped}}}{(1-\gamma)^{3}\varepsilon^{2}}$ | —— | ——
finite | VI-LCB | $\frac{H^{6}SC^{\star}}{\varepsilon^{2}}$ | —— | model-based
(Xie et al.,, 2021)
VPVI | $\frac{H^{5}SC^{\star}}{\varepsilon^{2}}$ | —— | model-based
(Yin and Wang,, 2021)
PEVI-Adv | $\frac{H^{4}SC^{\star}}{\varepsilon^{2}}+\frac{H^{6.5}SC^{\star}}{\varepsilon}$ | $\big{(}0,\frac{1}{H^{2.5}}\big{]}$ | model-based
(Xie et al.,, 2021)
LCB-Q-Advantage | $\frac{H^{4}SC^{\star}}{\varepsilon^{2}}+\frac{H^{5}SC^{\star}}{\varepsilon}$ | $\big{(}0,\frac{1}{H}\big{]}$ | model-free
(Shi et al., 2022b, )
APVI/LCBVI | $\frac{H^{4}SC^{\star}}{\varepsilon^{2}}+\frac{H^{4}}{d^{\mathsf{b}}_{\min}\varepsilon}$ | $(0,SC^{\star}d^{\mathsf{b}}_{\min}]$ | model-based
(Yin and Wang,, 2021)
VI-LCB |  |  |
(this paper: Theorem 3) | $\frac{H^{4}SC^{\star}_{\mathsf{clipped}}}{\varepsilon^{2}}$ ($\leq\frac{H^{4}SC^{\star}}{\varepsilon^{2}}$) | $(0,H]$ | model-based
lower bound |  |  |
(this paper: Theorem 4) | $\frac{H^{4}SC^{\star}_{\mathsf{clipped}}}{\varepsilon^{2}}$ | —— | ——
Table 1: Comparisons with prior results (up to log terms) regarding finding an
$\varepsilon$-optimal policy in offline RL. The $\varepsilon$-range stands for
the range of accuracy level $\varepsilon$ for which the derived sample
complexity is optimal. Here, one always has $C^{\star}_{\mathsf{clipped}}\leq
C^{\star}$; and the parameter
$d^{\mathsf{b}}_{\min}\coloneqq\frac{1}{\min_{s,a,h}\\{d^{\mathsf{b}}_{h}(s,a):\,d^{\mathsf{b}}_{h}(s,a)>0\\}}$
employed in Yin and Wang, (2021) could be exceedingly small, with
$d^{\mathsf{b}}_{h}$ the occupancy distribution of the dataset. While multiple
algorithms are referred to as VI-LCB in the table, they correspond to
different variants of VI-LCB. Our results are the first to achieve sample
optimality for the full $\varepsilon$-range.

###  1.4 Notation

Throughout this paper, we adopt the convention that $0/0=0$. We use
$\Delta(\mathcal{S})$ to indicate the probability simplex over the set
$\mathcal{S}$, and denote by $[H]$ the set $\\{1,\cdots,H\\}$ for any positive
integer $H$. We use $\operatorname{\mathds{1}}(\cdot)$ to represent the
indicator function. For any vector
$x=[x(s,a)]_{(s,a)\in\mathcal{S}\times\mathcal{A}}\in\mathbb{R}^{SA}$, we
overload the notation by letting
$x^{2}=[x(s,a)^{2}]_{(s,a)\in\mathcal{S}\times\mathcal{A}}$. For two vectors
$a=[a_{i}]_{1\leq i\leq n}$ and $b=[b_{i}]_{1\leq i\leq n}$, $a\circ
b=[a_{i}b_{i}]_{1\leq i\leq n}$ denotes their Hadamard product, and $a\geq b$
(resp. $a\leq b$) means $a_{i}\geq b_{i}$ (resp. $a_{i}\leq b_{i}$) for all
$i$. Following the convention in RL (Agarwal et al.,, 2021), the norm
$\|\cdot\|_{1}$ of a matrix $P=[P_{ij}]$ is defined to be
$\|P\|_{1}\coloneqq\max_{i}\sum_{j}|P_{ij}|$. For any probability vector
$q\in\mathbb{R}^{1\times S}$ (which is a row vector) and any vector
$V\in\mathbb{R}^{S}$, define

$\displaystyle\mathsf{Var}_{q}(V)\coloneqq q\big{(}V\circ
V\big{)}-\left(qV\right)^{2}\,\in\mathbb{R}$ (8)

with $qV=\sum_{i}q_{i}V_{i}$, which corresponds to the variance of $V$ w.r.t.
the distribution $q$. The standard notation $O(\cdot)$ is adopted to represent
the orderwise scaling of a function.

##  2 Algorithm and theory: discounted infinite-horizon MDPs

We begin by studying offline RL in discounted infinite-horizon Markov decision
processes. In the following, we shall first introduce the models and
assumptions for discounted infinite-horizon MDPs, followed by algorithm design
and main results.

###  2.1 Models and assumptions

Let us begin with some preliminary concepts and notation of discounted
infinite-horizon MDPs, followed by a concrete setting specific to offline RL.
A more detailed introduction of discounted infinite-horizon MDPs can be found
in classical textbooks like Bertsekas, (2017).

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

Consider a discounted infinite-horizon MDP (Bertsekas,, 2017) represented by a
tuple $\mathcal{M}=\\{\mathcal{S},\mathcal{A},P,\gamma,r\\}$. The key
components of $\mathcal{M}$ are: (i) $\mathcal{S}=\\{1,2,\cdots,S\\}$: a
finite state space of size $S$; (ii) $\mathcal{A}=\\{1,2,\cdots,A\\}$: an
action space of size $A$; (iii)
$P:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$: the transition
probability kernel of the MDP (i.e., $P(\cdot\,|\,s,a)$ denotes the transition
probability from state $s$ when action $a$ is executed); (iv)
$\gamma\in[0,1)$: the discount factor, so that $\frac{1}{1-\gamma}$ represents
the effective horizon; (v) $r:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$:
the deterministic reward function (namely, $r(s,a)$ indicates the immediate
reward received when the current state-action pair is $(s,a)$). Without loss
of generality, the immediate rewards are normalized so that they are contained
within the interval $[0,1]$. Throughout this section, we introduce the
convenient notation

$\displaystyle P_{s,a}\coloneqq P(\cdot\,|\,s,a)\in\mathbb{R}^{1\times S}.$
(9)

##### Policy, value function and Q-function.

A stationary policy $\pi:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ is a
possibly randomized action selection rule; that is, $\pi(a\,|\,s)$ represents
the probability of choosing $a$ in state $s$. When $\pi$ is a deterministic
policy, we abuse the notation by letting $\pi(s)$ represent the action chosen
by the policy $\pi$ in state $s$. A sample trajectory induced by the MDP under
policy $\pi$ can be written as $\\{(s_{t},a_{t})\\}_{t\geq 0}$, with $s_{t}$
(resp. $a_{t}$) denoting the state (resp. action) of the trajectory at time
$t$. To proceed, we shall also introduce the value function $V^{\pi}$ and
Q-value function $Q^{\pi}$ associated with policy $\pi$. Specifically, the
value function $V^{\pi}:\mathcal{S}\rightarrow\mathbb{R}$ of policy $\pi$ is
defined as the expected discounted cumulative reward as follows:

$\displaystyle\forall s\in\mathcal{S}:\qquad
V^{\pi}(s)\coloneqq\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\mid
s_{0}=s;\pi\right],$ (10)

where the expectation is taken over the sample trajectory
$\\{(s_{t},a_{t})\\}_{t\geq 0}$ generated in a way that
$a_{t}\sim\pi(\cdot\,|\,s_{t})$ and $s_{t+1}\sim P(\cdot\,|\,s_{t},a_{t})$ for
all $t\geq 0$. Given that all immediate rewards lie within $[0,1]$, it is
easily verified that $0\leq V^{\pi}(s)\leq\frac{1}{1-\gamma}$ for any policy
$\pi$. The Q-function (or action-state function) of policy $\pi$ can be
defined analogously as follows:

$\displaystyle\forall(s,a)\in\mathcal{S}\times\mathcal{A}:\qquad
Q^{\pi}(s,a)\coloneqq\mathbb{E}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})\mid
s_{0}=s,a_{0}=a;\pi\right],$ (11)

which differs from (10) in that it is also conditioned on $a_{0}=a$.

Let $\rho\in\Delta(\mathcal{S})$ be a given state distribution. If the initial
state is randomly drawn from $\rho$, then we can define the following weighted
value function of policy $\pi$:

$\displaystyle
V^{\pi}(\rho)\coloneqq\mathop{\mathbb{E}}\limits_{s\sim\rho}\big{[}V^{\pi}(s)\big{]}.$
(12)

In addition, we introduce the discounted occupancy distributions associated
with policy $\pi$ as follows:

$\displaystyle\forall s\in\mathcal{S}:\quad d^{\pi}(s;\rho)$
$\displaystyle\coloneqq(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s\mid
s_{0}\sim\rho;\pi),$ (13)
$\displaystyle\forall(s,a)\in\mathcal{S}\times\mathcal{A}:\qquad
d^{\pi}(s,a;\rho)$
$\displaystyle\coloneqq(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\mathbb{P}(s_{t}=s,a_{t}=a\mid
s_{0}\sim\rho;\pi),$ (14)

where we consider the randomness over a sample trajectory that starts from an
initial state $s_{0}\sim\rho$ and that follows policy $\pi$ (i.e.,
$a_{t}\sim\pi(\cdot\,|\,s_{t})$ and $s_{t+1}\sim P(\cdot\,|\,s_{t},a_{t})$ for
all $t\geq 0$).

It is known that there exists at least one deterministic policy — denoted by
$\pi^{\star}$ — that simultaneously maximizes $V^{\pi}(s)$ and $Q^{\pi}(s,a)$
for all state-action pairs $(s,a)\in\mathcal{S}\times\mathcal{A}$ (Bertsekas,,
2017). We use the following shorthand notation to represent respectively the
resulting optimal value and optimal Q-function:

$\displaystyle\forall(s,a)\in\mathcal{S}\times\mathcal{A}:\quad
V^{\star}(s)\coloneqq V^{\pi^{\star}}(s)\quad\text{ and }\quad
Q^{\star}(s,a)\coloneqq Q^{\pi^{\star}}(s,a).$ (15)

Correspondingly, we adopt the notation of the discounted occupancy
distributions associated with $\pi^{\star}$ as:

$\displaystyle\forall(s,a)\in\mathcal{S}\times\mathcal{A}:\quad
d^{\star}(s)\coloneqq d^{\pi^{\star}}(s;\rho)\quad\text{ and }\quad
d^{\star}(s,a)\coloneqq
d^{\pi^{\star}}(s,a;\rho)=d^{\star}(s)\operatorname{\mathds{1}}\big{(}a=\pi^{\star}(s)\big{)},$
(16)

where the last equality is valid since $\pi^{\star}$ is assumed to be
deterministic.

##### Offline/batch data.

Let us work with an independent sampling model as studied in the prior work
Rashidinejad et al., (2022). To be precise, imagine that we observe a batch
dataset $\mathcal{D}=\\{(s_{i},a_{i},s_{i}^{\prime})\\}_{1\leq i\leq N}$
containing $N$ sample transitions. These samples are independently generated
based on a distribution
$d^{\mathsf{b}}\in\Delta(\mathcal{S}\times\mathcal{A})$ and the transition
kernel $P$ of the MDP, namely,

$\displaystyle(s_{i},a_{i})\overset{\mathrm{ind.}}{\sim}d^{\mathsf{b}}\qquad\text{and}\qquad
s_{i}^{\prime}\overset{\mathrm{ind.}}{\sim}P(\cdot\,|\,s_{i},a_{i}),\qquad\quad
1\leq i\leq N.$ (17)

In addition, it is assumed that the learner is aware of the reward function.

In order to capture the distribution shift between the desired occupancy
measure and the data distribution, we introduce a key quantity previously
introduced in Rashidinejad et al., (2022).

######  Definition 1 (Single-policy concentrability for infinite-horizon
MDPs).

The single-policy concentrability coefficient of a batch dataset $\mathcal{D}$
is defined as

$\displaystyle
C^{\star}\coloneqq\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}\,\frac{d^{\star}(s,a)}{d^{\mathsf{b}}(s,a)}.$
(18)

Clearly, one necessarily has $C^{\star}\geq 1$.

In words, $C^{\star}$ measures the distribution mismatch in terms of the
maximum density ratio. The batch dataset can be viewed as expert data when
$C^{\star}$ approaches 1, meaning that the batch dataset is close to the
target policy in terms of the induced distributions. Moreover, this
coefficient $C^{\star}$ is referred to as the “single-policy” concentrability
coefficient since it is concerned with a single policy $\pi^{\star}$; this is
clearly a much weaker assumption compared to the all-policy concentrability
assumption (as adopted in, e.g., Munos, (2007); Farahmand et al., (2010); Fan
et al., (2019); Chen and Jiang, (2019); Ren et al., (2021); Xie and Jiang,
(2021)), the latter of which assumes a uniform density-ratio bound over all
policies and requires the dataset to be highly exploratory.

In the current paper, we also introduce a slightly improved version of
$C^{\star}$ as follows.

######  Definition 2 (Single-policy clipped concentrability for infinite-
horizon MDPs).

The single-policy clipped concentrability coefficient of a batch dataset
$\mathcal{D}$ is defined as

$\displaystyle
C^{\star}_{\mathsf{clipped}}\coloneqq\max_{(s,a)\in\mathcal{S}\times\mathcal{A}}\frac{\min\big{\\{}d^{\star}(s,a),\frac{1}{S}\big{\\}}}{d^{\mathsf{b}}(s,a)}.$
(19)

######  Remark 1.

A direct comparison of Conditions (18) and (19) implies that for a given batch
dataset $\mathcal{D}$,

$C^{\star}_{\mathsf{clipped}}\leq C^{\star}.$ (20)

As we shall see later, while our sample complexity upper bounds will be mainly
stated in terms of $C^{\star}_{\mathsf{clipped}}$, all of them remain valid if
$C^{\star}_{\mathsf{clipped}}$ is replaced with $C^{\star}$. Additionally, in
contrast to $C^{\star}$ that is always lower bounded by 1, we have a smaller
lower bound as follows (directly from the definition (19))

$\displaystyle C^{\star}_{\mathsf{clipped}}\geq 1/S,$ (21)

which is nearly tight.111As a concrete example, suppose that
$d^{\star}(s)=\begin{cases}1-\frac{S-1}{S^{3}}&\text{if }s=1\\\
\frac{1}{S^{3}}&\text{else}\end{cases}$ and
$d^{\mathsf{b}}(s,a)=\begin{cases}1-\frac{S-1}{S^{2}}&\text{if
}a=\pi^{\star}(s)\text{ and }s=1,\\\ \frac{1}{S^{2}}&\text{if
}a=\pi^{\star}(s)\text{ and }s\neq 1,\\\ 0,&\text{else}.\end{cases}$ Then it
can be easily verified that
$C^{\star}_{\mathsf{clipped}}=\frac{1}{S-1+\frac{1}{S}}$. Nonetheless, caution
should be exercised that an exceedingly small $C^{\star}_{\mathsf{clipped}}$
requires highly compressible structure of $d^{\star}$, and the real-world data
often do not fall within this benign range of $C^{\star}_{\mathsf{clipped}}$.
This attribute could lead to sample size saving in some cases, to be detailed
shortly.

Let us take a moment to further interpret the coefficient in Definition 2,
which says that

$\displaystyle
d^{\mathsf{b}}(s,a)\geq\begin{cases}\frac{1}{C^{\star}_{\mathsf{clipped}}}d^{\star}(s,a),\qquad&\text{if
}d^{\star}(s,a)\leq 1/S\\\ \frac{1}{C^{\star}_{\mathsf{clipped}}S},&\text{if
}d^{\star}(s,a)>1/S\end{cases}$ (22)

holds for any pair $(s,a)$. Consider, for instance, the case where
$C^{\star}_{\mathsf{clipped}}=O(1)$: if a state-action pair is infrequently
(or rarely) visited by the optimal policy, then it is fine for the associated
density in the batch data to be very small (e.g., a density proportional to
that of the optimal policy); by contrast, if a state-action pair is visited
fairly often by the optimal policy, then Definition 2 might only require
$d^{\mathsf{b}}(s,a)$ to exceed the order of $1/S$. In other words, the
required level of $d^{\mathsf{b}}(s,a)$ is clipped at the level
$\frac{1}{C^{\star}_{\mathsf{clipped}}S}$ regardless of the value of
$d^{\star}(s,a)$.

##### Goal.

Armed with the batch dataset $\mathcal{D}$, the objective of offline RL in
this case is to find a policy $\widehat{\pi}$ that attains near-optimal value
functions — with respect to a given test state distribution
$\rho\in\Delta(\mathcal{S})$ — in a sample-efficient manner. To be precise,
for a prescribed accuracy level $\varepsilon$, we seek to identify an
$\varepsilon$-optimal policy $\widehat{\pi}$ satisfying

$\displaystyle V^{\star}(\rho)-V^{\widehat{\pi}}(\rho)\leq\varepsilon$ (23)

with high probability, using a batch dataset $\mathcal{D}$ (cf. (17))
containing as few samples as possible. Particular emphasis is placed on
achieving minimal sample complexity for the entire range of accuracy levels
(namely, for any $\varepsilon\in\big{(}0,\frac{1}{1-\gamma}\big{]}$).

###  2.2 Algorithm: VI-LCB for infinite-horizon MDPs

In this subsection, we introduce a model-based offline RL algorithm that
incorporates lower concentration bounds in value estimation. The algorithm,
called VI-LCB, applies value iteration (based on some pessimistic Bellman
operator) to the empirical MDP, with the key ingredients described below.

##### The empirical MDP.

Recall that we are given $N$ independent sample transitions
$\\{(s_{i},a_{i},s_{i}^{\prime})\\}_{i=1}^{N}$ in the dataset $\mathcal{D}$.
For any given state-action pair $(s,a)$, we denote by

$\displaystyle
N(s,a)\coloneqq\sum_{i=1}^{N}\operatorname{\mathds{1}}\big{(}(s_{i},a_{i})=(s,a)\big{)}$
(24)

the number of samples transitions from $(s,a)$. We then construct an empirical
transition matrix $\widehat{P}$ such that

$\displaystyle\widehat{P}(s^{\prime}\,|\,s,a)=\begin{cases}\frac{1}{N(s,a)}\sum\limits_{i=1}^{N}\mathds{1}\big{\\{}(s_{i},a_{i},s_{i}^{\prime})=(s,a,s^{\prime})\big{\\}},&\text{if
}N(s,a)>0\\\ \frac{1}{S},&\text{else}\end{cases}$ (25)

for each $(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$.

##### The pessimistic Bellman operator.

Our offline algorithm is developed based on finding the fixed point of some
variant of the classical Bellman operator. Let us first introduce this key
operator and eludicate how the pessimism principle is enforced. Recall that
the Bellman operator
$\mathcal{T}(\cdot):\mathbb{R}^{SA}\rightarrow\mathbb{R}^{SA}$ w.r.t. the
transition kernel $P$ is defined such that for any vector
$Q\in\mathbb{R}^{SA}$,

$\displaystyle\mathcal{T}(Q)(s,a)\coloneqq r(s,a)+\gamma
P_{s,a}V\qquad\text{for all }(s,a)\in\mathcal{S}\times\mathcal{A},$ (26)

where $V=[V(s)]_{s\in\mathcal{S}}$ with $V(s)\coloneqq\max_{a}Q(s,a)$. We
propose to penalize the original Bellman operator w.r.t. the empirical kernel
$\widehat{P}$ as follows:

$\displaystyle\widehat{\mathcal{T}}_{\mathsf{pe}}(Q)(s,a)\coloneqq\max\Big{\\{}r(s,a)+\gamma\widehat{P}_{s,a}V-b(s,a;V),0\Big{\\}}\qquad\text{for
all }(s,a)\in\mathcal{S}\times\mathcal{A},$ (27)

where $b(s,a;V)$ denotes the penalty term employed to enforce pessimism amid
uncertainty. As one can anticipate, the properties of the fixed point of
$\widehat{\mathcal{T}}_{\mathsf{pe}}(\cdot)$ relies heavily upon the choice of
the penalty terms $\\{b_{h}(s,a;V)\\}$, often derived based on certain
concentration bounds. In this paper, we focus on the following Bernstein-style
penalty to exploit the importance of certain variance statistics:

$\displaystyle
b(s,a;V)\coloneqq\min\Bigg{\\{}\max\bigg{\\{}\sqrt{\frac{c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{N(s,a)}\mathsf{Var}_{\widehat{P}_{s,a}}(V)},\,\frac{2c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{(1-\gamma)N(s,a)}\bigg{\\}},\,\frac{1}{1-\gamma}\Bigg{\\}}+\frac{5}{N}$
(28)

for every $(s,a)\in\mathcal{S}\times\mathcal{A}$, where $c_{\mathsf{b}}>0$ is
some numerical constant (e.g., $c_{\mathsf{b}}=144$), and $\delta\in(0,1)$ is
some given quantity (in fact, $1-\delta$ is the target success probability).
Here, for any vector $V\in\mathbb{R}^{S}$, we recall that
$\mathsf{Var}_{\widehat{P}_{s,a}}(V)$ is the variance of $V$ w.r.t. the
distribution $\widehat{P}_{s,a}$ (see (8)).

We immediately isolate several useful properties as follows, whose proof is
postponed to Appendix A.1.

######  Lemma 1.

For any $\gamma\in[\frac{1}{2},1)$, the operator
$\widehat{\mathcal{T}}_{\mathsf{pe}}(\cdot)$ (cf. (27)) with the Bernstein-
style penalty (28) is a $\gamma$-contraction w.r.t. $\|\cdot\|_{\infty}$, that
is,

$\displaystyle\big{\|}\widehat{\mathcal{T}}_{\mathsf{pe}}(Q_{1})-\widehat{\mathcal{T}}_{\mathsf{pe}}(Q_{2})\big{\|}_{\infty}\leq\gamma\|Q_{1}-Q_{2}\|_{\infty}$
(29)

for any $Q_{1},Q_{2}\in\mathbb{R}^{S\times A}$ obeying
$Q_{1}(s,a),Q_{2}(s,a)\in\big{[}0,\frac{1}{1-\gamma}\big{]}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. In addition, there exists a unique
fixed point $\widehat{Q}_{\mathsf{pe}}^{\star}$ of the operator
$\widehat{\mathcal{T}}_{\mathsf{pe}}(\cdot)$, which also obeys
$0\leq\widehat{Q}_{\mathsf{pe}}^{\star}(s,a)\leq\frac{1}{1-\gamma}$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

In words, even though $\widehat{\mathcal{T}}_{\mathsf{pe}}(\cdot)$ integrates
the penalty terms, it still preserves the $\gamma$-contraction property and
admits a unique fixed point, thereby resembling the classical Bellman operator
(26).

1 input: dataset $\mathcal{D}$; reward function $r$; target success
probability $1-\delta$; max iteration number $\tau_{\max}$.

2 initialization: $\widehat{Q}_{0}=0$, $\widehat{V}_{0}=0$.

3construct the empirical transition kernel $\widehat{P}$ according to (25).

4

5for  _$\tau=1,2,\cdots,\tau_{\max}$_ do

6

7 for  _$s\in\mathcal{S},a\in\mathcal{A}$_ do

8 compute the penalty term $b\big{(}s,a;\widehat{V}_{\tau-1}\big{)}$ according
to (28).

9 set
$\widehat{Q}_{\tau}(s,a)=\max\big{\\{}r(s,a)+\gamma\widehat{P}_{s,a}\widehat{V}_{\tau-1}-b\big{(}s,a;\widehat{V}_{\tau-1}\big{)},0\big{\\}}$.

10

11

12 for  _$s\in\mathcal{S}$_ do

13 set $\widehat{V}_{\tau}(s)=\max_{a}\widehat{Q}_{\tau}(s,a)$.

14

output: $\widehat{\pi}$ s.t.
$\widehat{\pi}(s)\in\arg\max_{a}\widehat{Q}_{\tau_{\max}}(s,a)$ for any
$s\in\mathcal{S}$.

Algorithm 1 Offline value iteration with LCB (VI-LCB) for discounted infinite-
horizon MDPs

##### The VI-LCB algorithm.

We are now positioned to introduce the VI-LCB algorithm, which can be regarded
as classical value iteration applied in conjunction with pessimism.
Specifically, the algorithm applies the Bernstein-style pessimistic operator
$\widehat{\mathcal{T}}_{\mathsf{pe}}$ (cf. (27)) iteratively in order to find
its fixed point:

$\displaystyle\widehat{Q}_{\tau}(s,a)=\widehat{\mathcal{T}}_{\mathsf{pe}}\big{(}\widehat{Q}_{\tau-1}\big{)}(s,a)=\max\Big{\\{}r(s,a)+\gamma\widehat{P}_{s,a}\widehat{V}_{\tau-1}-b\big{(}s,a;\widehat{V}_{\tau-1}\big{)},0\Big{\\}},\qquad\tau=1,2,\cdots$
(30)

We shall initialize it to $\widehat{Q}_{0}=0$, implement (30) for
$\tau_{\max}$ iterations, and output $\widehat{Q}=\widehat{Q}_{\tau_{\max}}$
as the final Q-estimate. The final policy estimate $\widehat{\pi}$ is chosen
on the basis of $\widehat{Q}$ as follows:

$\displaystyle\widehat{\pi}(s)\in\arg\max_{a}\widehat{Q}(s,a)\qquad\text{for
all }s\in\mathcal{S},$ (31)

with the whole algorithm summarized in Algorithm 1.

Let us pause to explain the rationale of the pessimism principle on a high
level. If a pair $(s,a)$ has been insufficiently visited in $\mathcal{D}$
(i.e., $N(s,a)$ is small), then the resulting Q-estimate
$\widehat{Q}_{\tau}(s,a)$ could suffer from high uncertainty and become
unreliable, which might in turn mislead value estimation. By enforcing
suitable penalization $b(s,a;\widehat{V}_{\tau-1})$ based on certain lower
confidence bounds, we can suppress the negative influence of such poorly
visited state-action pairs. Fortunately, suppressing these state-action pairs
might not result in significant bias in value estimation when
$C^{\star}_{\mathsf{clipped}}$ is small; for instance, when the behavior
policy $\pi^{\mathsf{b}}$ resembles $\pi^{\star}$, the poorly visited state-
action pairs correspond primarily to suboptimal actions (as they are not
selected by $\pi^{\star}$), making it acceptable to neglect these pairs.

Interestingly, Algorithm 1 is guaranteed to converge rapidly. In view of the
$\gamma$-contraction property in Lemma 1, the iterates
$\\{\widehat{Q}_{\tau}\\}_{\tau\geq 0}$ converge linearly to the fixed point
$\widehat{Q}_{\mathsf{pe}}^{\star}$, as asserted below.

######  Lemma 2.

Suppose $\widehat{Q}_{0}=0$. Then the iterates of Algorithm 1 obey

$\displaystyle\widehat{Q}_{\tau}\leq\widehat{Q}_{\mathsf{pe}}^{\star}\qquad\text{and}\qquad\big{\|}\widehat{Q}_{\tau}-\widehat{Q}_{\mathsf{pe}}^{\star}\big{\|}_{\infty}\leq\frac{\gamma^{\tau}}{1-\gamma}\qquad\quad\text{for
all }\tau\geq 0,$ (32)

where $\widehat{Q}_{\mathsf{pe}}^{\star}$ is the unique fixed point of
$\widehat{\mathcal{T}}_{\mathsf{pe}}$. As a consequence, by choosing
$\tau_{\max}\geq\frac{\log\frac{N}{1-\gamma}}{\log(1/\gamma)}$ one fulfills

$\displaystyle\big{\|}\widehat{Q}_{\tau_{\max}}-\widehat{Q}_{\mathsf{pe}}^{\star}\big{\|}_{\infty}\leq
1/N.$ (33)

The proof of this lemma is deferred to Appendix A.2.

##### Algorithmic comparison with Rashidinejad et al., (2022).

VI-LCB has been studied in the prior work Rashidinejad et al., (2022). The
difference between our algorithm and the version therein is two-fold:

  * •

Sample reuse vs. $\widetilde{O}\big{(}\frac{1}{1-\gamma}\big{)}$-fold sample
splitting. Our algorithm reuses the same set of samples across all iterations,
which is in sharp contrast to Rashidinejad et al., (2022) that employs fresh
samples in each of the $\widetilde{O}\big{(}\frac{1}{1-\gamma}\big{)}$
iterations. This results in considerably better usage of available
information.

  * •

Bernstein-style vs. Hoeffding-style penalty. Our algorithm adopts the
Bernstein-type penalty, as opposed to the Hoeffding-style penalty in
Rashidinejad et al., (2022). This choice leads to more effective exploitation
of the variance structure across time.

##### Pessimism vs. optimism in the face of uncertainty.

The careful reader might also notice the similarity between the pessimism
principle and the optimism principle utilized in online RL. A well-developed
paradigm that balances exploration and exploitation in online RL is optimistic
exploration based on uncertainty quantification (Lai and Robbins,, 1985). The
earlier work Jaksch et al., (2010) put forward an algorithm called UCRL2 that
computes an optimistic policy with the aid of Hoeffding-style confidence
regions for the probability transition kernel. Later on, Azar et al., (2017)
proposed to build upper confidence bounds (UCB) for the optimal values
instead, which leads to significantly improved sample complexity; see, e.g.,
Wang et al., (2019); He et al., (2021) for the application of this strategy to
discounted infinite-horizon MDPs. Note, however, that the rationales behind
optimism and pessimism are remarkably different. In offline RL (which does not
allow further data collection), the uncertainty estimates are employed to
identify, and then rule out, poorly-visited actions; this stands in sharp
contrast to the online counterpart where poorly-visited actions might be more
favored during exploration.

###  2.3 Performance guarantees

When the Bernstein-style concentration bound (28) is adopted, the VI-LCB
algorithm in Algorithm 1 yields $\varepsilon$-accuracy with a near-minimal
number of samples, as stated below.

######  Theorem 1.

Suppose $\gamma\in[\frac{1}{2},1)$, and consider any $0<\delta<1$ and
$\varepsilon\in\big{(}0,\frac{1}{1-\gamma}\big{]}$. Suppose that the total
number of iterations exceeds
$\tau_{\max}\geq\frac{1}{1-\gamma}\log\frac{N}{1-\gamma}$. With probability at
least $1-2\delta,$ the policy $\widehat{\pi}$ returned by Algorithm 1 obeys

$\displaystyle V^{\star}(\rho)-V^{\widehat{\pi}}(\rho)\leq\varepsilon,$ (34)

provided that $c_{\mathsf{b}}$ (cf. the Bernstein-style penalty term in (28))
is some sufficiently large numerical constant and the total sample size
exceeds

$\displaystyle
N\geq\frac{c_{1}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)^{3}\varepsilon^{2}}$
(35)

for some large enough numerical constant $c_{1}>0$, where
$C^{\star}_{\mathsf{clipped}}$ is introduced in Definition 2. In addition, the
above result continues to hold if $C^{\star}_{\mathsf{clipped}}$ is replaced
with $C^{\star}$ (introduced in Definition 1).

######  Remark 2.

Regarding the numerical constants in Theorem 1, a conservative yet concrete
sufficient condition is that $c_{\mathsf{b}}\geq 144$ and
$c_{1}=21000c_{\mathsf{b}}$, which we shall rigorize in the proof.

The proof of this theorem is postponed to Section 6. In general, the total
sample size characterized by Theorem 1 could be far smaller than the ambient
dimension (i.e., $S^{2}A$) of the transition kernel $P$, thus precluding one
from estimating $P$ in a reliable fashion. As a crucial insight from Theorem
1, the model-based (or plug-in) approach enables reliable offline learning
even when model estimation is completely off.

Before discussing key implications of Theorem 1, we develop matching minimax
lower bounds that help confirm the efficacy of the proposed model-based
algorithm, whose proof can be found in Appendix C.2.

######  Theorem 2.

For any $(\gamma,S,C^{\star}_{\mathsf{clipped}},\varepsilon)$ obeying
$\gamma\in\big{[}\frac{2}{3},1\big{)},$ $S\geq 2$,
$C^{\star}_{\mathsf{clipped}}\geq\frac{8\gamma}{S}$, and
$\varepsilon\leq\frac{1}{42(1-\gamma)}$, one can construct two MDPs
$\mathcal{M}_{0},\mathcal{M}_{1}$, an initial state distribution $\rho$, and a
batch dataset with $N$ independent samples and single-policy clipped
concentrability coefficient $C^{\star}_{\mathsf{clipped}}$ such that

$\inf_{\widehat{\pi}}\max\left\\{\mathbb{P}_{0}\big{(}V^{\star}(\rho)-V^{\widehat{\pi}}(\rho)>\varepsilon\big{)},\,\mathbb{P}_{1}\big{(}V^{\star}(\rho)-V^{\widehat{\pi}}(\rho)>\varepsilon\big{)}\right\\}\geq\frac{1}{8},$

provided that

$N\leq\frac{c_{2}SC^{\star}_{\mathsf{clipped}}}{(1-\gamma)^{3}\varepsilon^{2}}$

for some numerical constant $c_{2}>0$. Here, the infimum is over all estimator
$\widehat{\pi}$, and $\mathbb{P}_{0}$ (resp. $\mathbb{P}_{1}$) denotes the
probability when the MDP is $\mathcal{M}_{0}$ (resp. $\mathcal{M}_{1}$).

######  Remark 3.

As a more concrete (yet conservative) condition for $c_{2}$, Theorem 2 is
valid when $c_{2}=1/25088$.

##### Implications.

In the following, we take a moment to interpret the above two theorems and
single out several key implications about the proposed model-based algorithm.

  * •

Optimal sample complexities. In the presence of the Bernstein-style penalty,
the total number of samples needed for our algorithm to yield
$\varepsilon$-accuracy is

$\widetilde{O}\bigg{(}\frac{SC^{\star}_{\mathsf{clipped}}}{(1-\gamma)^{3}\varepsilon^{2}}\bigg{)}.$
(36)

This taken together with the minimax lower bound asserted in Theorem 2
confirms the optimality of the proposed model-based approach (up to some
logarithmic factor). In comparison, the sample complexity derived in
Rashidinejad et al., (2022) exhibits a worse dependency on the effective
horizon (i.e., $\frac{1}{(1-\gamma)^{5}}$). Theorem 2 also enhances the lower
bound developed in Rashidinejad et al., (2022) to accommodate the scenario
where $C^{\star}_{\mathsf{clipped}}$ can be much smaller than $C^{\star}$,
i.e., $C^{\star}_{\mathsf{clipped}}=O(1/S)$.

  * •

No burn-in cost. The fact that the sample size bound (35) holds for the full
$\varepsilon$-range (i.e., any given
$\varepsilon\in\big{(}0,\frac{1}{1-\gamma}\big{]}$) means that there is no
burn-in cost required to achieve sample optimality. This not only drastically
improves upon, but in fact eliminates, the burn-in cost of the best-known
sample-optimal result (cf. (5)), the latter of which required a burn-in cost
at least on the order of $\frac{SC^{\star}}{(1-\gamma)^{5}}$. Accomplishing
this requires one to tackle the sample-hungry regime, which is statistically
challenging to cope with.

  * •

No need of sample splitting. It is noteworthy that prior works typically
required sample splitting. For instance, Rashidinejad et al., (2022) analyzed
the VI-LCB algorithm with fresh samples employed in each iteration, which
effectively split the data into
$\widetilde{O}\big{(}\frac{1}{1-\gamma}\big{)}$ disjoint subsets. In contrast,
the algorithm studied herein permits the reuse of all samples across all
iterations. This is an important feature in sample-starved applications to
effectively maximize information utilization, and is a crucial factor that
assists in improving the sample complexity compared to Rashidinejad et al.,
(2022).

  * •

Sample size saving when $C^{\star}_{\mathsf{clipped}}<1$. In view of Theorem
1, the sample complexity of the proposed algorithm can be as low as

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

when $C^{\star}_{\mathsf{clipped}}$ is on the order of $1/S$. This might seem
somewhat surprising at first glance, given that the minimax sample complexity
for policy evaluation is at least
$\widetilde{O}\big{(}\frac{S}{(1-\gamma)^{3}\varepsilon^{2}}\big{)}$ even in
the presence of a simulator (Azar et al.,, 2013). To elucidate this, we note
that the condition $C^{\star}_{\mathsf{clipped}}=O(1/S)$ implicitly imposes
special — in fact, highly compressible — structure on the MDP that enables
sample size reduction. As we shall see from the lower bound construction in
Theorem 2, the case with $C^{\star}_{\mathsf{clipped}}=O(1/S)$ might require
$d^{\star}(s,a)$ to concentrate on one or a small number of important states,
with exceedingly small probability assigned to the remaining ones. If this
occurs, then it often suffices to focus on what happens on these important
states, thus requiring much fewer samples.

##### Comparisons with prior statistical analysis.

Before concluding this section, we highlight the innovations of our
statistical analysis compared to past theory when it comes to discounted
infinite-horizon MDPs. To begin with, our sample size improvement over
Rashidinejad et al., (2022) stems from the two algorithmic differences
mentioned in Section 2.2: the sample-reuse feature allows one to improve a
factor of $\frac{1}{1-\gamma}$, while the use of Bernstein-style penalty
yields an additional gain of $\frac{1}{1-\gamma}$. In addition, while the
design of data-driven Bernstein-style bounds has been extensively studied in
online RL in discounted MDPs (e.g., Zhang et al., 2021b ; He et al., (2021)),
all of these past results were either sample-suboptimal, or required a huge
burn-in sample size (e.g., $\frac{S^{3}A^{2}}{(1-\gamma)^{4}}$ in He et al.,
(2021)). In other words, sample optimality was not previously achieved in the
most data-hungry regime. In comparison, our theory ensures optimality of our
algorithm even for the most sample-constrained scenario, which relies on much
more delicate statistical tools. In a nutshell, our statistical analysis is
built upon at least two ideas: (i) a leave-one-out analysis framework that
allows to decouple complicated statistical dependency across iterations
without losing statistical tightness; (ii) a delicate self-bounding trick that
allows us to simultaneously control multiple crucial statistical quantities
(e.g., empirical variance) in the most sample-starved regime.

##  3 Algorithm and theory: episodic finite-horizon MDPs

In this section, we turn attention to the studies of offline RL for episodic
finite-horizon MDPs.

###  3.1 Models and assumptions

As before, we briefly state some preliminaries about finite-horizon MDPs,
before moving on to the sampling model and the goal. The readers can consult
Bertsekas, (2017) for more details about finite-horizon MDPs.

##### Basics of finite-horizon MDPs.

Consider the setting of a finite-horizon Markov decision process, as denoted
by $\mathcal{M}=\\{\mathcal{S},\mathcal{A},H,P,r\\}$. It consists of the
following key components: (i) $\mathcal{S}=\\{1,\cdots,S\\}$: a state space of
size $S$; (ii) $\mathcal{A}=\\{1,\cdots,A\\}$: an action space of size $A$;
(iii) $H$: the horizon length; (iv) $P=\\{P_{h}\\}_{1\leq h\leq H}$, with
$P_{h}:\mathcal{S}\times\mathcal{A}\rightarrow\Delta(\mathcal{S})$ denoting
the probability transition kernel at step $h$ (namely, $P_{h}(\cdot\,|\,s,a)$
stands for the transition probability of the MDP at step $h$ when the current
state-action pair is $(s,a)$); (v) $r=\\{r_{h}\\}_{1\leq h\leq H}$, with
$r_{h}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ denoting the reward
function at step $h$ (namely, $r_{h}(s,a)$ indicates the immediate reward
gained at step $h$ when the current state-action pair is $(s,a)$). It is
assumed without loss of generality that the immediate rewards fall within the
interval $[0,1]$ and are deterministic. Conveniently, we introduce the
following $S$-dimensional row vector

$P_{h,s,a}\coloneqq P_{h}(\cdot\,|\,s,a)$ (37)

for any $(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$.

A (possibly randomized) policy $\pi=\\{\pi_{h}\\}_{1\leq h\leq H}$ with
$\pi_{h}:\mathcal{S}\rightarrow\Delta(\mathcal{A})$ is an action selection
rule, such that $\pi_{h}(a\,|\,s)$ specifies the probability of choosing
action $a$ when in state $s$ and step $h$. When $\pi$ is a deterministic
policy, we overload the notation and let $\pi_{h}(s)$ represent the action
selected by $\pi$ in state $s$ at step $h$. We can generate a sample
trajectory $\\{(s_{h},a_{h})\\}_{1\leq h\leq H}$ by implementing policy $\pi$
in the MDP $\mathcal{M}$, where $s_{h}$ and $a_{h}$ denote the state and the
action in step $h$, respectively. We then introduce the value function
$V^{\pi}=\\{V_{h}^{\pi}\\}_{1\leq h\leq H}$ and the Q-function
$Q^{\pi}=\\{Q_{h}^{\pi}\\}_{1\leq h\leq H}$ associated with policy $\pi$;
specifically, the value function $V_{h}:\mathcal{S}\rightarrow\mathbb{R}$ of
policy $\pi$ at step $h$ is defined to the be the expected cumulative reward
from step $h$ on as a result of policy $\pi$, namely,

$\displaystyle\forall s\in\mathcal{S}:\qquad
V_{h}^{\pi}(s)\coloneqq\mathbb{E}\left[\sum_{t=h}^{H}r_{t}(s_{t},a_{t})\mid
s_{h}=s;\pi\right],$ (38)

where the expectation is taken over the randomness over the sample trajectory
$\\{(s_{t},a_{t})\\}_{t=h}^{H}$ when policy $\pi$ is implemented (i.e.,
$a_{t}\sim\pi_{t}(\cdot\,|\,s_{t})$ and $s_{t+1}\sim
P_{t}(\cdot\,|\,s_{t},a_{t})$ for all $t\geq h$). Correspondingly, the
Q-function of policy $\pi$ at step $h$ is defined to be

$\displaystyle\forall(s,a)\in\mathcal{S}\times\mathcal{A}:\qquad
Q_{h}^{\pi}(s,a)\coloneqq\mathbb{E}\left[\sum_{t=h}^{H}r_{t}(s_{t},a_{t})\mid
s_{h}=s,a_{h}=a;\pi\right]$ (39)

when conditioned on the state-action pair $(s,a)$ at step $h$. If the initial
state is drawn from a distribution $\rho\in\Delta(\mathcal{S})$, we find it
convenient to define the following weighted value function of policy $\pi$:

$V_{1}^{\pi}(\rho)\coloneqq\mathop{\mathbb{E}}_{s\sim\rho}\big{[}V^{\pi}_{1}(s)\big{]}.$
(40)

Additionally, we introduce the following occupancy distributions associated
with policy $\pi$ at step $h$:

$\displaystyle d_{h}^{\pi}(s;\rho)$
$\displaystyle\coloneqq\mathbb{P}\big{(}s_{h}=s\mid s_{1}\sim\rho;\pi\big{)},$
(41a) $\displaystyle d_{h}^{\pi}(s,a;\rho)$
$\displaystyle\coloneqq\mathbb{P}\big{(}s_{h}=s,a_{h}=a\mid
s_{1}\sim\rho;\pi\big{)}=d_{h}^{\pi}(s;\rho)\pi(a\,|\,s),$ (41b)

which are conditioned on the initial state distribution $s_{1}\sim\rho$ and
the event that all actions are selected according to $\pi$. In particular, it
is self-evident that

$d_{1}^{\pi}(s;\rho)=\rho(s)\qquad\text{for any policy }\pi\text{ and any
state }s\in\mathcal{S}.$ (42)

It is well known that there exists at least one deterministic policy that
simultaneously maximizes the value function and the Q-function for all
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$ (Bertsekas,, 2017). In light
of this, we shall denote by $\pi^{\star}=\\{\pi^{\star}_{h}\\}_{1\leq h\leq
H}$ an optimal deterministic policy throughout this paper; this allows us to
employ $\pi^{\star}_{h}(s)$ to indicate the corresponding optimal action
chosen in state $s$ at step $h$. The resulting optimal value function and
optimal Q-function are denoted respectively by
$V^{\star}=\\{V^{\star}_{h}\\}_{1\leq h\leq H}$ and
$Q^{\star}=\\{Q^{\star}_{h}\\}_{1\leq h\leq H}$:

$\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]:\qquad
V_{h}^{\star}\coloneqq V_{h}^{\pi^{\star}}\qquad\text{and}\qquad
Q_{h}^{\star}\coloneqq Q_{h}^{\pi^{\star}}.$

Furthermore, we adopt the following notation for convenience:

$\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]:\quad
d_{h}^{\star}(s)\coloneqq d_{h}^{\pi^{\star}}(s;\rho)\quad\text{and}\quad
d_{h}^{\star}(s,a)\coloneqq
d_{h}^{\pi^{\star}}(s,a;\rho)=d_{h}^{\star}(s)\mathds{1}\\{a=\pi^{\star}(s)\\},$
(43)

where the last identity holds given that $\pi^{\star}$ is assumed to be
deterministic.

##### Offline/batch data.

Suppose that we have access to a batch dataset (or historical dataset)
$\mathcal{D}$, which comprises a collection of $K$ i.i.d. sample trajectories
generated by a behavior policy
$\pi^{\mathsf{b}}=\\{\pi^{\mathsf{b}}_{h}\\}_{1\leq h\leq H}$. More
specifically, the $k$-th sample trajectory ($1\leq k\leq K$) consists of a
data sequence

$\displaystyle\big{(}s_{1}^{k},a_{1}^{k},s_{2}^{k},a_{2}^{k},\ldots,s_{H}^{k},a_{H}^{k},s_{H+1}^{k}\big{)},$
(44)

which is generated by the MDP $\mathcal{M}$ under the behavior policy
$\pi^{\mathsf{b}}$ in the following manner:

$\displaystyle s_{1}^{k}\sim\rho^{\mathsf{b}},\qquad
a_{h}^{k}\sim\pi^{\mathsf{b}}_{h}(\cdot\,|\,s_{h}^{k})\qquad\text{and}\qquad
s_{h+1}^{k}\sim P_{h}(\cdot\,|\,s_{h}^{k},a_{h}^{k}),\qquad 1\leq h\leq H.$
(45)

Here and throughout, $\rho^{\mathsf{b}}$ stands for some predetermined initial
state distribution associated with the batch dataset. In addition to the above
dataset (cf. (44) for all $1\leq k\leq K$), the learner also has access to the
reward function. For notational simplicity, we introduce the following short-
hand notation for the occupancy distribution w.r.t. the behavior policy
$\pi^{\mathsf{b}}$:

$\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]:\qquad
d^{\mathsf{b}}_{h}(s)\coloneqq
d_{h}^{\pi^{\mathsf{b}}}(s;\rho^{\mathsf{b}})\quad\text{and}\quad
d^{\mathsf{b}}_{h}(s,a)\coloneqq
d_{h}^{\pi^{\mathsf{b}}}(s,a;\rho^{\mathsf{b}}).$ (46)

In particular, it is easily seen that
$d^{\mathsf{b}}_{1}(s)=\rho^{\mathsf{b}}(s)$ for all $s\in\mathcal{S}$. Note
that the initial state distribution $\rho^{\mathsf{b}}$ of the batch dataset
might not coincide with the test state distribution $\rho$.

Akin to Definition 1, prior works (e.g., Xie et al., (2021)) have introduced
the following concentrability coefficient to capture the distribution shift
between the desired distribution and the one induced by the behavior policy.

######  Definition 3 (Single-policy concentrability for finite-horizon MDPs).

The single-policy concentrability coefficient of a batch dataset $\mathcal{D}$
is defined as

$\displaystyle
C^{\star}\coloneqq\max_{(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]}\,\frac{d_{h}^{\star}(s,a)}{d^{\mathsf{b}}_{h}(s,a)},$
(47)

which clearly satisfies $C^{\star}\geq 1$.

Similar to the discounted infinite-horizon counterpart, $C^{\star}$ employs
the largest density ratio (using the occupancy distributions defined above) to
measure the distribution mismatch; it concerns the behavior policy vs. a
single policy $\pi^{\star}$, and does not require uniform coverage of the
state-action space (namely, it suffices to cover the part reachable by
$\pi^{\star}$). As before, we further introduce a slightly modified version of
$C^{\star}$ as follows.

######  Definition 4 (Single-policy clipped concentrability for finite-horizon
MDPs).

The single-policy clipped concentrability coefficient of a batch dataset
$\mathcal{D}$ is defined as

$\displaystyle
C^{\star}_{\mathsf{clipped}}\coloneqq\max_{(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]}\frac{\min\big{\\{}d_{h}^{\star}(s,a),\frac{1}{S}\big{\\}}}{d^{\mathsf{b}}_{h}(s,a)}.$
(48)

From the definition above, it holds trivially that

$\displaystyle C^{\star}_{\mathsf{clipped}}\leq
C^{\star}\qquad\text{and}\qquad C^{\star}_{\mathsf{clipped}}\geq\frac{1}{S}.$
(49)

As we shall see shortly, while all sample complexity upper bounds developed
herein remain valid if we replace $C^{\star}_{\mathsf{clipped}}$ with
$C^{\star}$, the use of $C^{\star}_{\mathsf{clipped}}$ might yield some sample
size reduction when $C^{\star}_{\mathsf{clipped}}$ drops below 1.

##### Goal.

With the above batch dataset $\mathcal{D}$ in hand, our aim is to compute, in
a sample-efficient fashion, a policy $\widehat{\pi}$ that results in near-
optimal values w.r.t. a given test state distribution
$\rho\in\Delta(\mathcal{S})$. Formally speaking, the current paper focuses on
achieving

$V_{1}^{\star}(\rho)-V_{1}^{\widehat{\pi}}(\rho)\leq\varepsilon$

with high probability using as few samples as possible, where $\varepsilon$
stands for the target accuracy level. We seek to achieve sample optimality for
the full $\varepsilon$-range, i.e., for any $\varepsilon\in(0,H]$.

###  3.2 A model-based offline RL algorithm: VI-LCB

Suppose for the moment that we have access to a dataset $\mathcal{D}_{0}$
containing $N$ sample transitions
$\\{(s_{i},a_{i},h_{i},s_{i}^{\prime})\\}_{i=1}^{N}$, where
$(s_{i},a_{i},h_{i},s_{i}^{\prime})$ denotes the transition from state $s_{i}$
at step $h_{i}$ to state $s_{i}^{\prime}$ in the next step when action $a_{i}$
is taken. We now describe a pessimistic variant of the model-based approach on
the basis of $\mathcal{D}_{0}$.

##### Empirical MDP.

For each $(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, we denote by

$\displaystyle N_{h}(s,a)$
$\displaystyle\coloneqq\sum_{i=1}^{N}\mathds{1}\big{\\{}(s_{i},a_{i},h_{i})=(s,a,h)\big{\\}}$
(50a) $\displaystyle N_{h}(s)$
$\displaystyle\coloneqq\sum_{i=1}^{N}\mathds{1}\big{\\{}(s_{i},h_{i})=(s,h)\big{\\}}$
(50b)

the total number of sample transitions at step $h$ that transition from
$(s,a)$ and from $s$, respectively. We can then compute the empirical estimate
$\widehat{P}=\\{\widehat{P}_{h}\\}_{1\leq h\leq H}$ of the transition kernel
$P$ as follows:

$\displaystyle\widehat{P}_{h}(s^{\prime}\,|\,s,a)=\begin{cases}\frac{1}{N_{h}(s,a)}\sum\limits_{i=1}^{N}\mathds{1}\big{\\{}(s_{i},a_{i},h_{i},s_{i}^{\prime})=(s,a,h,s^{\prime})\big{\\}},&\text{if
}N_{h}(s,a)>0\\\ \frac{1}{S},&\text{else}\end{cases}$ (51)

for each
$(s,a,h,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times[H]\times\mathcal{S}$.

##### The VI-LCB algorithm.

With this estimated model in place, the VI-LCB algorithm (i.e., value
iteration with lower confidence bounds) maintains the value function estimate
$\\{\widehat{V}_{h}\\}$ and Q-function estimate $\\{\widehat{Q}_{h}\\}$, and
works backward from $h=H$ to $h=1$ as in classical dynamic programming with
the terminal value $\widehat{V}_{H+1}=0$ (Xie et al.,, 2021; Jin et al.,,
2021). Specifically, the algorithm adopts the following update rule:

$\displaystyle\widehat{Q}_{h}(s,a)=\max\Big{\\{}r_{h}(s,a)+\widehat{P}_{h,s,a}\widehat{V}_{h+1}-b_{h}(s,a),0\Big{\\}},$
(52)

where $\widehat{P}_{h,s,a}$ is the empirical estimate of $P_{h,s,a}$ (cf.
(37)),

$\widehat{V}_{h+1}(s)=\max_{a}\widehat{Q}_{h+1}(s,a),$ (53)

and $b_{h}(s,a)\geq 0$ denotes some penalty term that is a decreasing function
in $N_{h}(s,a)$ (as we shall specify momentarily). In addition, the policy
$\widehat{\pi}$ is selected greedily in accordance to the Q-estimate:

$\displaystyle\forall(s,h)\in\mathcal{S}\times[H]:\qquad\widehat{\pi}_{h}(s)\in\arg\max_{a}\widehat{Q}_{h}(s,a).$
(54)

In a nutshell, the VI-LCB algorithm — as summarized in Algorithm 2 — applies
the classical value iteration approach to the empirical model $\widehat{P}$,
and in addition, implements the principle of pessimism via certain lower
confidence penalty terms $\\{b_{h}(s,a)\\}$.

1 input: dataset $\mathcal{D}_{0}$; reward function $r$; target success
probability $1-\delta$.

2 initialization: $\widehat{V}_{H+1}=0$.

3

4for  _$h=H,\cdots,1$_ do

5 compute the empirical transition kernel $\widehat{P}_{h}$ according to (51).

6 for  _$s\in\mathcal{S},a\in\mathcal{A}$_ do

7 compute the penalty term $b_{h}(s,a)$ according to (55).

8 set
$\widehat{Q}_{h}(s,a)=\max\big{\\{}r_{h}(s,a)+\widehat{P}_{h,s,a}\widehat{V}_{h+1}-b_{h}(s,a),0\big{\\}}$.

9

10 for  _$s\in\mathcal{S}$_ do

11 set $\widehat{V}_{h}(s)=\max_{a}\widehat{Q}_{h}(s,a)$ and
$\widehat{\pi}_{h}(s)\in\arg\max_{a}\widehat{Q}_{h}(s,a)$.

12

13

output: $\widehat{\pi}=\\{\widehat{\pi}_{h}\\}_{1\leq h\leq H}$.

Algorithm 2 Offline value iteration with LCB (VI-LCB) for finite-horizon MDPs.

##### The Bernstein-style penalty terms.

As before, we adopt Bernstein-style penalty in order to better capture the
variance structure over time; that is,

$\displaystyle\forall(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]:\;b_{h}(s,a)=\min\Bigg{\\{}\sqrt{\frac{c_{\mathsf{b}}\log\frac{NH}{\delta}}{N_{h}(s,a)}\mathsf{Var}_{\widehat{P}_{h,s,a}}\big{(}\widehat{V}_{h+1}\big{)}}+c_{\mathsf{b}}H\frac{\log\frac{NH}{\delta}}{N_{h}(s,a)},\,H\Bigg{\\}}$
(55)

for some universal constant $c_{\mathsf{b}}>0$ (e.g., $c_{\mathsf{b}}=16$).
Here, $\mathsf{Var}_{\widehat{P}_{h,s,a}}\big{(}\widehat{V}_{h+1}\big{)}$
corresponds to the variance of $\widehat{V}_{h+1}$ w.r.t. the distribution
$\widehat{P}_{h,s,a}$ (see the definition (8)). Note that we choose
$\widehat{P}$ as opposed to $P$ (i.e.,
$\mathsf{Var}_{P_{h,s,a}}\big{(}\widehat{V}_{h+1}\big{)}$) in the variance
term, mainly because we have no access to the true transition kernel $P$.

Finally, it is worth noting that the Bernstein-style uncertainty estimates
have been widely studied when performing online exploration in episodic
finite-horizon MDPs (e.g., Fruit et al., (2020); Azar et al., (2017); Talebi
and Maillard, (2018); Jin et al., (2018); Li et al., (2021); Zhang et al.,
(2020)). Once again, the main purpose therein is to encourage exploration of
the insufficiently visited states/actions, a mechanism that is not applicable
to offline RL due to the absence of further data collection.

###  3.3 VI-LCB with two-fold subsampling

Given that the batch dataset $\mathcal{D}$ is composed of several sample
trajectories each of length $H$, the sample transitions in $\mathcal{D}$
cannot be viewed as being independently generated (as the sample transitions
at step $h$ might influence the sample transitions in the subsequent steps).
As one can imagine, the presence of such temporal statistical dependency
considerably complicates analysis.

In order to circumvent this technical difficulty, we propose a two-fold
subsampling trick that allows one to exploit the desired statistical
independence. Informally, we propose the following steps:

  * •

First of all, we randomly split the dataset into two halves
$\mathcal{D}^{\mathsf{main}}$ and $\mathcal{D}^{\mathsf{aux}}$, where
$\mathcal{D}^{\mathsf{main}}$ consists of $N^{\mathsf{main}}_{h}(s)$ sample
transitions from state $s$ at step $h$.

  * •

For each $(s,h)\in\mathcal{S}\times[H]$, we use the dataset
$\mathcal{D}^{\mathsf{aux}}$ to construct a high-probability lower bound
$N^{\mathsf{trim}}_{h}(s)$ on $N^{\mathsf{main}}_{h}(s)$, and then subsample
$N^{\mathsf{trim}}_{h}(s)$ sample transitions w.r.t. $(s,h)$ from
$\mathcal{D}^{\mathsf{main}}$; this results in a new subsampled dataset
$\mathcal{D}^{\mathsf{trim}}$.

  * •

Run VI-LCB on the subsampled dataset $\mathcal{D}^{\mathsf{trim}}$ (i.e.,
Algorithm 2).

The whole procedure is detailed in Algorithm 3. A few important features are
worth highlighting, under the assumption that the sample trajectories in
$\mathcal{D}$ are independently generated from the same distribution.

  * •

Given that $\\{N^{\mathsf{trim}}_{h}(s)\\}$ are computed on the basis of the
dataset $\mathcal{D}^{\mathsf{aux}}$ and that $\mathcal{D}^{\mathsf{trim}}$ is
subsampled from another dataset $\mathcal{D}^{\mathsf{main}}$, one can clearly
see that $\\{N^{\mathsf{trim}}_{h}(s)\\}$ are statistically independent from
the sample transitions in $\mathcal{D}^{\mathsf{trim}}$.

  * •

As we shall justify in the analysis (i.e., Section 7.2), the samples in
$\mathcal{D}^{\mathsf{trim}}$ can almost be treated as being statistically
independent, a key attribute resulting from the subsampling trick.

  * •

The proposed algorithm only splits the data into two subsets, which is in
stark contrast to prior variants of VI-LCB that perform $H$-fold sample
splitting (e.g., Xie et al., (2021)). Eliminating the $H$-fold splitting
requirement plays a crucial role in enabling optimal sample complexity.

1 input: a dataset $\mathcal{D}$; reward function $r$.

2

3subsampling: run the following procedure to generate the subsampled dataset
$\mathcal{D}^{\mathsf{trim}}$.

  * 1)

Data splitting. Split $\mathcal{D}$ into two halves:
$\mathcal{D}^{\mathsf{main}}$ (which contains the first $K/2$ trajectories),
and $\mathcal{D}^{\mathsf{aux}}$ (which contains the remaining $K/2$
trajectories); we let $N^{\mathsf{main}}_{h}(s)$ (resp.
$N^{\mathsf{aux}}_{h}(s)$) denote the number of sample transitions in
$\mathcal{D}^{\mathsf{main}}$ (resp. $\mathcal{D}^{\mathsf{aux}}$) that
transition from state $s$ at step $h$.

  * 2)

Lower bounding $\\{N^{\mathsf{main}}_{h}(s)\\}$ using
$\mathcal{D}^{\mathsf{aux}}$. For each $s\in\mathcal{S}$ and $1\leq h\leq H$,
compute

$\displaystyle N^{\mathsf{trim}}_{h}(s)$
$\displaystyle\coloneqq\max\left\\{N^{\mathsf{aux}}_{h}(s)-10\sqrt{N^{\mathsf{aux}}_{h}(s)\log\frac{HS}{\delta}},\,0\right\\};$
(56)

  * 3)

Random subsampling. Let ${\mathcal{D}^{\mathsf{main}}}^{\prime}$ be the set of
all sample transitions (i.e., the quadruples taking the form
$(s,a,h,s^{\prime})$) from $\mathcal{D}^{\mathsf{main}}$. Subsample
${\mathcal{D}^{\mathsf{main}}}^{\prime}$ to obtain
$\mathcal{D}^{\mathsf{trim}}$, such that for each
$(s,h)\in\mathcal{S}\times[H]$, $\mathcal{D}^{\mathsf{trim}}$ contains
$\min\\{N^{\mathsf{trim}}_{h}(s),N^{\mathsf{main}}_{h}(s)\\}$ sample
transitions randomly drawn from ${\mathcal{D}^{\mathsf{main}}}^{\prime}$.

run VI-LCB: set $\mathcal{D}_{0}=\mathcal{D}^{\mathsf{trim}}$; run Algorithm 2
to compute a policy $\widehat{\pi}$.

4

5

Algorithm 3 Subsampled VI-LCB for episodic finite-horizon MDPs

Before proceeding, we formally justify that $N^{\mathsf{trim}}_{h}(s)$ — as
computed in (56) — is a valid lower bound on $N^{\mathsf{main}}_{h}(s)$. Here
and below, we denote by $N^{\mathsf{trim}}_{h}(s,a)$ the number of sample
transitions in $\mathcal{D}^{\mathsf{trim}}$ that are associated with the
state-action pair $(s,a)$ at step $h$. The proof of this lemma can be found in
Appendix B.1.

######  Lemma 3.

Suppose that the $K$ trajectories in $\mathcal{D}$ are generated in an i.i.d.
fashion (see Section 3.1). With probability at least $1-8\delta$, the
quantities constructed in (56) obey

$\displaystyle N^{\mathsf{trim}}_{h}(s)$ $\displaystyle\leq
N^{\mathsf{main}}_{h}(s),$ (57a) $\displaystyle N^{\mathsf{trim}}_{h}(s,a)$
$\displaystyle\geq\frac{Kd^{\mathsf{b}}_{h}(s,a)}{8}-5\sqrt{Kd^{\mathsf{b}}_{h}(s,a)\log\frac{KH}{\delta}}$
(57b)

simultaneously for all $1\leq h\leq H$ and all
$(s,a)\in\mathcal{S}\times\mathcal{A}$.

###  3.4 Performance guarantees

In what follows, we characterize the sample complexity of Algorithm 3, as
formalized below.

######  Theorem 3.

Consider any $\varepsilon\in(0,H]$ and any $0<\delta<1$. With probability
exceeding $1-12\delta,$ the policy $\widehat{\pi}$ returned by Algorithm 3
obeys

$\displaystyle V^{\star}_{1}(\rho)-V^{\widehat{\pi}}_{1}(\rho)\leq\varepsilon$
(58)

as long as the penalty terms are chosen according to the Bernstein-style
quantity (55) for some large enough numerical constant $c_{\mathsf{b}}>0$, and
the total number of sample trajectories exceeds

$\displaystyle
K\geq\frac{c_{\mathsf{k}}H^{3}SC^{\star}_{\mathsf{clipped}}\log\frac{KH}{\delta}}{\varepsilon^{2}}$
(59)

for some sufficiently large numerical constant $c_{\mathsf{k}}>0$, where
$C^{\star}_{\mathsf{clipped}}$ is introduced in Definition 4. Additionally,
the above result continues to hold if $C^{\star}_{\mathsf{clipped}}$ is
replaced with $C^{\star}$ (introduced in Definition 3).

######  Remark 4.

One concrete yet conservative requirement on $c_{\mathsf{b}}$ and
$c_{\mathsf{k}}$ for Theorem 3 to hold is: $c_{\mathsf{b}}\geq 16$ and
$c_{\mathsf{k}}=12800c_{\mathsf{b}}$, as we shall solidify in the proof of
Theorem 3.

The proof of this result is postponed to Section 7. In general, the total
sample size characterized by Theorem 3 could be far smaller than the ambient
dimension (i.e., $S^{2}AH$) of the probability transition kernel $P$, thus
precluding one from estimating $P$ in a reliable fashion. As a crucial insight
from Theorem 3, the model-based (or plug-in) approach enables reliable policy
learning even when model estimation is completely off. Our analysis of Theorem
3 relies heavily on (i) suitable decoupling of complicated statistical
dependency via subsampling, and (ii) careful control of the variance terms in
the presence of Bernstein-style penalty.

In order to help assess the tightness and optimality of Theoerem 3, we further
develop a minimax lower bound as follows; the proof can be found in Appendix
C.3.

######  Theorem 4.

For any $(H,S,C^{\star}_{\mathsf{clipped}},\varepsilon)$ obeying $H\geq 12$,
$C^{\star}_{\mathsf{clipped}}\geq 8/S$ and $\varepsilon\leq c_{3}H$, one can
construct a collection of MDPs
$\\{\mathcal{M}_{\theta}\mid\theta\in\Theta\\}$, an initial state distribution
$\rho$, and a batch dataset with $K$ independent sample trajectories each of
length $H$, such that

$\displaystyle\inf_{\widehat{\pi}}\max_{\theta\in\Theta}\mathbb{P}_{\theta}\left\\{V_{1}^{\star}(\rho)-V_{1}^{\widehat{\pi}}(\rho)\geq\varepsilon\right\\}\geq\frac{1}{4},$
(60)

provided that the total sample size

$\displaystyle
N=KH\leq\frac{c_{4}C^{\star}_{\mathsf{clipped}}SH^{4}}{\varepsilon^{2}}.$ (61)

Here, $c_{3},c_{4}>0$ are some small enough numerical constants, the infimum
is over all estimator $\widehat{\pi}$, and $\mathbb{P}_{\theta}$ denotes the
probability when the MDP is $\mathcal{M}_{\theta}$.

######  Remark 5.

More concretely, one (conservative) condition regarding $c_{3}$ and $c_{4}$
that is sufficient for the validity of Theorem 4 is: $c_{3}=1/2^{14}$ and
$c_{4}=1/2^{36}$, as we shall see in the proof.

##### Implications.

In what follows, let us take a moment to discuss several other key
implications of Theorem 3.

  * •

Near-optimal sample complexities. In the presence of the Bernstein-style
penalty, the total number of samples (i.e., $KH$) needed for our algorithm to
yield $\varepsilon$-accuracy is

$\widetilde{O}\bigg{(}\frac{H^{4}SC^{\star}_{\mathsf{clipped}}}{\varepsilon^{2}}\bigg{)}.$
(62)

This confirms the optimality of the proposed model-based approach (up to some
logarithmic term) when Bernstein-style penalty is employed, since Theorem 4
reveals that at least
$\frac{H^{4}SC^{\star}_{\mathsf{clipped}}}{\varepsilon^{2}}$ samples are
needed regardless of the algorithm in use.

  * •

Full $\varepsilon$-range and no burn-in cost. The sample complexity bound (59)
stated in Theorem 3 holds for an arbitrary $\varepsilon\in(0,H]$. In other
words, no burn-in cost is needed for the algorithm to work sample-optimally.
This improves substantially upon the state-of-the-art results for model-based
and model-free offline algorithms, both of which require a significant level
of burn-in sample size ($H^{9}SC^{\star}$ and $H^{6}SC^{\star}$,
respectively).

  * •

Sample reduction and model compressibility when
$C^{\star}_{\mathsf{clipped}}<1$. Given that $C^{\star}_{\mathsf{clipped}}$
might drop below 1, the sample complexity of our algorithm might be as low as
$\widetilde{O}\big{(}\frac{H^{4}S}{\varepsilon^{2}}\big{)}$. In fact,
recognizing that $C^{\star}_{\mathsf{clipped}}$ can be as small as
$\frac{1+o(1)}{S}$, we see that the sample complexity can sometimes be reduced
to

$\widetilde{O}\bigg{(}\frac{H^{4}}{\varepsilon^{2}}\bigg{)},$ (63)

resulting in significant sample size saving compared to prior works. Caution
needs to be exercised, however, that this sample size improvement is made
possible as a result of certain model compressibility implied by a small
$C^{\star}_{\mathsf{clipped}}$. For instance,
$C^{\star}_{\mathsf{clipped}}=O(1/S)$ might happen when a small number of
states accounts for a dominant fraction of probability mass in
$d^{\star}_{h}(s)$, with the remaining states exhibiting vanishingly small
occupancy probability (see also the lower bound construction in the proof of
Theorem 4); if this happens, then it often suffices to focus on learning those
dominant states.

##### (In)-feasibility of estimating $C^{\star}_{\mathsf{clipped}}$.

With the sample complexity (62) in mind, one natural question arises as to
whether it is possible to estimate $C^{\star}_{\mathsf{clipped}}$ from the
batch dataset. Unfortunately, this is in general infeasible, as demonstrated
by the following example.

  * •

(A hard example) Consider an MDP with horizon $H=2$. In step $h=1$, we have a
singleton state space $\mathcal{S}_{1}=\\{0\\}$ and an action space
$\mathcal{A}_{1}=\\{0,1\\}$, whereas in step $h=2$, we have a state space
$\mathcal{S}_{2}=\\{0,1\\}$ and a singleton action space
$\mathcal{A}_{2}=\\{0\\}$. The reward function and the transition kernel are
given by:

$\displaystyle r_{1}(0,0)=0,\quad r_{1}(0,1)=0,\quad r_{2}(0,0)=0,\quad
r_{2}(1,0)=1$ $\displaystyle P_{1}(0\,|\,0,0)$ $\displaystyle=0.5,\quad
P_{1}(1\,|\,0,0)=0.5,\quad P_{1}(0\,|\,0,1)=p,\quad P_{1}(1\,|\,0,1)=1-p$

for some unknown parameter $p\in(0,1)$. We have $K$ independent trajectories
as usual, and let

$d^{\mathsf{b}}_{1}(0,0)=1-\frac{1}{K}\qquad\text{and}\qquad
d^{\mathsf{b}}_{1}(0,1)=\frac{1}{K}.$ (64)

Elementary calculation then reveals that: $C^{\star}_{\mathsf{clipped}}=K$
when $p<\frac{1}{2}$, and $C^{\star}_{\mathsf{clipped}}=1+\frac{1}{K-1}$ when
$p>\frac{1}{2}$. Such a remarkable difference in
$C^{\star}_{\mathsf{clipped}}$ depends on the value of $p$, which is only
reflected in $(s,a)=(0,1)$ at step 1. However, by construction, there is
nonvanishing probability (i.e.,
$\big{(}1-d^{\mathsf{b}}_{1}(0,1)\big{)}^{K}\approx 1/e$ for large $K$) such
that the dataset does not visit $(s,a)=(0,1)$ in step $h=1$ at all, which in
turn precludes one from distinguishing
$C^{\star}_{\mathsf{clipped}}=1+\frac{1}{K-1}$ from
$C^{\star}_{\mathsf{clipped}}=K$ given only the available dataset.

Fortunately, implementing our algorithm does not require prior knowledge of
$C^{\star}_{\mathsf{clipped}}$ at all, and the algorithm succeeds once the
task becomes feasible. On the other hand, we won’t be able to tell how large a
sample size is enough a priori, but this is in general information-
theoretically infeasible as illustrated by the above example.

##### Towards instance optimality.

While the primary focus of the current paper is minimax-optimal algorithm
design, the theoretical framework developed herein enables instance-dependent
analysis as well. Take episodic finite-horizon MDPs for example: our analysis
framework directly leads to the following instance-dependent guarantee for
Algorithm 3:

$\displaystyle
V_{h}^{\star}(\rho)-V_{h}^{\widehat{\pi}}(\rho)=\big{\langle}d_{1}^{\star},V_{1}^{\star}-V_{1}^{\widehat{\pi}}\big{\rangle}$
$\displaystyle\quad\leq
12\sum_{j=h}^{H}\sum_{s}d_{j}^{\star}(s)\sqrt{\frac{c_{\mathsf{b}}\log\frac{NH}{\delta}}{Kd^{\mathsf{b}}_{j}\big{(}s,\pi_{j}^{\star}(s)\big{)}}\mathsf{Var}_{P_{j,s,\pi^{\star}_{j}(s)}}(V_{j+1}^{\star})}+\Big{(}\frac{100c_{\mathsf{b}}H^{3}SC^{\star}\log\frac{NH}{\delta}}{K}\Big{)}^{3/4},$
(65)

with the proviso that $K\geq
100c_{\mathsf{b}}HSC^{\star}\log\frac{NH}{\delta}$. Encouragingly, the
dominate term (i.e., the first term in the bound (65)) matches the instance-
dependent lower bound established in (Yin and Wang,, 2021, Theorem 4.3), thus
confirming the instance optimality of the proposed algorithm for a large
enough sample size. The proof of (65) can be found in Appendix B.2.

##### Comparisons with prior statistical analysis.

We now briefly discuss the novelty of our statistical analysis compared with
past theory. Perhaps the most related prior work is Xie et al., (2021), which
proposed two algorithms. The first algorithm therein is VI-LCB with $H$-fold
sample splitting and Hoeffding-style penalty, and each of these two features
adds an $H$ factor to the total sample complexity. The second algorithm
therein combines VI-LCB with variance reduction, which leads to optimal sample
complexity for sufficiently small $\varepsilon$ (i.e., a large burn-in cost is
required). Note, however, that none of the existing statistical tools for
variance reduction is able to work without imposing a large burn-in cost,
regardless of the sampling mechanism in use (e.g., generative model, offline
RL, online RL) (Sidford et al.,, 2018; Zhang et al.,, 2020; Li et al.,, 2021;
Xie et al.,, 2021). In contrast, our theory makes apparent that variance
reduction is unnecessary, which leads to both simpler algorithm and tighter
analysis. Additionally, while Bernstein-style confidence bounds have been
deployed in online RL for finite-horizon MDPs (Fruit et al.,, 2020; Azar et
al.,, 2017; Jin et al.,, 2018; Zhang et al.,, 2020), none of these works was
able to yield optimal sample complexity without a large burn-in cost (e.g.,
Azar et al., (2017) incurred a burn-in cost as large as $S^{3}AH^{6}$). This
in turn underscores the power of our statistical analysis when coping with the
most data-hungry regime.

##  4 Numerical experiments

|  |
---|---|---
(a) Value gap versus states | (b) Value gap versus sample size | (c) Value gap dependency w.r.t. $N$
Figure 2: The performances of the proposed method VI-LCB and the baseline
value iteration (VI) in the gambler’s problem. It shows that VI-LCB
outperforms VI by taking advantage of the pessimism principle and achieves
approximately $1/\sqrt{N}$ sample complexity dependency w.r.t. the sample size
$N$.

To confirm the practical applicability of the proposed VI-LCB algorithm, we
evaluate its performance in the gambler’s problem (Sutton and Barto,, 2018;
Zhou et al.,, 2021; Panaganti and Kalathil,, 2022; Shi and Chi,, 2022). The
code can be accessed at:

https://github.com/Laixishi/Model-based-VI-LCB.

##### Gambler’s problem.

We start by introducing the formulation of the gambler’s problem and its
underlying MDP. An agent plays a gambling game in which she bets on a sequence
of random coin flips, winning when the coins are heads and losing when they
are tails. To bet on each random clip, the agent’s policy chooses an integer
number of dollars based on an initial balance. If the number of bets hits the
maximum length $H$, or if the agent reaches $50$ dollars (win) or $0$ dollars
(lose), the game ends. Without loss of generality, the problem can be
formulated as an episodic finite-horizon MDP. Here, $\mathcal{S}$ is the state
space $\\{0,1,\cdots,50\\}$ and the associated accessible actions obey
$a\in\big{\\{}0,1,\cdots,\min\\{s,50-s\\}\big{\\}}$, $H=100$ is the horizon
length, the reward is set to $0$ for all other states unless $s=50$. For the
transition kernel, we fix the probability of heads as $p_{\mathrm{head}}=0.45$
at all steps $h\in[H]$ in the episode. Moreover, the initial state/balance
distribution of the agent $\rho$ is taken as a uniform distribution over
$\mathcal{S}$. The offline historical dataset is constructed by collecting $N$
independent samples drawn randomly over each state-action pair and time step.

##### Evaluation results.

First, we evaluate the performance of our proposed method VI-LCB (cf.
Algorithm 2) with comparisons to the well-known value iteration (VI) method
without the pessimism principle. To begin with, Fig. 2(a) shows the average
and standard derivations of the performance gap
$V_{1}^{\star}(s)-V_{1}^{\widehat{\pi}}(s)$ over all states $s\in\mathcal{S}$,
over $10$ independent experiments with a fixed sample size $N=50$. The results
indicate that the proposed VI-LCB method outperforms the baseline VI method
uniformly over the entire state space, showing that pessimism brings
significant advantages in this sample-scarce regime. Secondly, we evaluate the
performance gap $V_{1}^{\star}(\rho)-V_{1}^{\widehat{\pi}}(\rho)$ with varying
sample size
$N\in\big{\\{}54,90,148,\cdots,22026\\}\approx\\{e^{4},e^{4.5},e^{5},\cdots,e^{10}\\}$,
over $10$ independent trials. Note that throughout the experiments, we fix the
parameter $c_{\mathsf{b}}=0.05$, which determines the level of the pessimism
penalty of VI-LCB (cf. (55)). Fig. 2(b) shows the average and standard
derivations of the performance gap
$V_{1}^{\star}(\rho)-V_{1}^{\widehat{\pi}}(\rho)$ with respect to the sample
size $N$. Clearly, as the sample size increases, both our method VI-LCB and
the baseline VI method perform better. Moreover, our VI-LCB method
consistently outperforms the baseline VI method over the entire range of the
sample size $N$, especially in the sample-starved regime. In addition, to
corroborate the scaling of the sample size on the performance gap, we plot the
sub-optimality performance gap of VI-LCB w.r.t. the sample size on a log-log
scale in Fig. 2(c). Fitting using linear regression leads to a slope estimate
of $-0.502$, with the corresponding fitted line plotted in Fig. 2(c) as well.
This nicely matches the finding of Theorem 3, which says the performance gap
of VI-LCB scales as $N^{-1/2}$.

##  5 Related works

In this section, we provide further discussions about prior art, with an
emphasis on settings that are most relevant to the current paper.

##### Off-policy evaluation and offline RL.

Broadly speaking, at least two families of problems have been investigated in
the literature that tackle offline batch data: off-policy evaluation, where
the goal is to estimate the value function of a target policy that deviates
from the behavior policy used in data collection; and offline policy learning,
where the goal is to identify a near-optimal policy (or at least an improved
one compared to the behavior policy). Our work falls under the second
category. A topic of its own interest, off-policy evaluation has been
extensively studied in the recent literature; we excuse ourselves from
enumerating the works in that space but only provide pointers to a few
examples including Uehara et al., (2020); Li et al., (2014); Yang et al.,
(2020); Duan et al., (2020); Jiang and Li, (2016); Jiang and Huang, (2020);
Kallus and Uehara, (2020); Duan et al., (2021); Xu et al., (2021); Ren et al.,
(2021); Thomas and Brunskill, (2016).

##### Offline RL with the pessimism principle.

The prior works that are the most relevant to this paper are Rashidinejad et
al., (2022); Xie et al., (2021); Jin et al., (2021); Shi et al., 2022b ; Yan
et al., (2023); Yin and Wang, (2021), which incorporated lower confidence
bounds into value estimation in order to avoid overly uncertain regions not
covered by the target policy. In addition to the ones discussed in Section 1.2
that focus on minimax performance, the recent works Yin and Wang, (2021); Yin
et al., (2022) further developed instance-dependent statistical guarantees for
the pessimistic model-based approach. The results in Yin and Wang, (2021),
however, required a large burn-in sample size
$\frac{H^{4}}{SC^{\star}(d^{\mathsf{b}}_{\min})^{2}}$ (since
$d^{\mathsf{b}}_{\min}$ could be exceedingly small), thus preventing it from
attaining minimax optimality for the entire $\varepsilon$-range. It is
noteworthy that the principle of pessimism has been incorporated into policy
optimization and actor-critic methods as well by searching for some least-
favorable models (e.g., Uehara and Sun, (2021); Zanette et al., (2021)), which
is quite different from the approach studied herein. On the empirical side,
model-based algorithms (Yu et al.,, 2020; Kidambi et al.,, 2020) have been
shown to achieve superior performance than their model-free counterpart for
offline RL. In addition, a number of recent works studied offline RL under
various function approximation assumptions, e.g., Jin et al., (2021); Yin et
al., (2022); Nguyen-Tang et al., (2021); Uehara and Sun, (2021); Uehara et
al., (2022); Zhan et al., (2022); Zanette et al., (2021), which are beyond the
scope of the current paper. Recently, the insights gleaned from the studies of
offline RL have inspired improved algorithm designs for online and hybrid RL
as well (Li et al.,, 2023; Li et al., 2024c, ).

##### Online RL and the optimism principle.

The optimism principle in the face of uncertainty has received widespread
adoption from bandits to online RL (Lai and Robbins,, 1985; Lattimore and
Szepesvári,, 2020; Agarwal et al.,, 2021). In the context of online RL, Jaksch
et al., (2010) constructed confidence regions for the probability transition
kernel to help select optimistic policies in the setting of weakly
communicating MDPs, based on a variant (called UCRL2) of the UCRL algorithm
originally proposed in Auer and Ortner, (2006); see also Filippi et al.,
(2010); Bourel et al., (2020); Talebi and Maillard, (2018) for other variants
of UCRL. When applied to episodic finite-horizon MDPs, the regret bound in
Jaksch et al., (2010) was suboptimal by a factor of at least $\sqrt{H^{2}S}$;
see discussion in Azar et al., (2017); Jin et al., (2018). Fruit et al.,
(2020) developed an improved regret bound for UCRL2 by using empirical
Bernstein-style bounds, which however was still suboptimal by a factor of at
least $\sqrt{HS}$ when specialized to episodic finite-horizon MDPs. In
comparison, a more sample-efficient paradigm is to build Bernstein-style UCBs
for the optimal values to help select exploration policies, which has been
recently adopted in both model-based (Azar et al.,, 2017; Zhang et al.,, 2023)
and model-free algorithms (Jin et al.,, 2018). Note that Bernstein-style
uncertainty estimation alone is not enough to ensure regret optimality in
model-free algorithms, thereby motivating the design of more sophisticated
variance reduction strategies (Li et al.,, 2021; Zhang et al.,, 2020).
Finally, the optimism principle has been studied in undiscounted infinite-
horizon MDPs too (e.g., Qian et al., (2019)), which is beyond the scope of
this paper.

##### Model-based RL.

The algorithms studied herein fall under the category of model-based RL, which
decouples the model estimation and the planning. This popular paradigm has
been deployed and studied under various data collection mechanisms beyond
offline RL, including but not limited to the generative model (or simulator)
setting (Azar et al.,, 2013; Agarwal et al.,, 2020; Li et al., 2024b, ; Li et
al.,, 2020) and the online exploratory setting (Azar et al.,, 2017; Jin et
al.,, 2020; Zhang et al., 2021a, ; Zhang et al.,, 2023). The leave-one-out
analysis (and the construction of absorbing MDPs) adopted in the proof of
Theorem 1 has been inspired by several recent works Agarwal et al., (2020); Li
et al., 2024b ; Pananjady and Wainwright, (2020); Cui and Yang, (2021), and
has recently been shown to be effective for multi-agent offline RL as well
(Yan et al.,, 2022).

##### Model-free RL.

Another widely used paradigm is model-free RL, which attempts to learn the
optimal value function without explicit construction of the model. Arguably
the most famous example of model-free RL is Q-learning, which applies the
stochastic approximation paradigm to find the fixed point of the Bellman
operator (Watkins and Dayan,, 1992; Even-Dar and Mansour,, 2003; Beck and
Srikant,, 2012; Szepesvári,, 1998; Murphy,, 2005; Qu and Wierman,, 2020; Li et
al., 2024a, ; Li et al.,, 2022; Xiong et al.,, 2020; Shi et al., 2022a, ; Chen
et al.,, 2020). It is worth noting that the asynchronous Q-learning, which
aims to learn the optimal Q-function from a data trajectory collected by
following a certain behavior policy, shares some similarity with offline RL;
note that prior results on vanilla asynchronous Q-learning require a strong
uniform coverage requirement (Qu and Wierman,, 2020; Li et al., 2024a, ; Chen
et al., 2021b, ), which is stronger than the single-policy concentrability
considered herein. Moreover, Q-learning alone is known to be sub-optimal in
terms of the sample complexity in various settings (Li et al., 2024a, ; Jin et
al.,, 2018; Shi et al., 2022b, ; Wainwright, 2019b, ; Bai et al.,, 2019). This
motivates the incorporation of the variance reduction in order to further
improve the sample complexity (Wainwright, 2019c, ; Shi et al., 2022b, ; Yan
et al.,, 2023; Li et al.,, 2021; Du et al.,, 2017; Zhang et al., 2021b, ; Li
et al.,, 2022; Zhang et al.,, 2020). Note, however, variance-reduced model-
free RL typically requires a large burn-in cost in order to operate in a
sample-optimal fashion, and is hence outperformed by the model-based approach
under multiple sampling mechanisms.

##  6 Analysis: discounted infinite-horizon MDPs

This section is devoted to establishing Theorem 1. Towards this end, we claim
that it is sufficient to prove the following theorem.

######  Theorem 5.

Consider any $0<\delta<1$ and any $\gamma\in[\frac{1}{2},1)$. Suppose that the
penalty terms are set to be (28) for any numerical constant
$c_{\mathsf{b}}\geq 144$. Then with probability exceeding $1-2\delta,$ for any
estimate $\widehat{Q}$ obeying
$\big{\|}\widehat{Q}-\widehat{Q}^{\star}_{\mathsf{pe}}\big{\|}_{\infty}\leq
1/N$ one has

$\displaystyle V^{\star}(\rho)-V^{\widehat{\pi}}(\rho)\leq
120\sqrt{\frac{c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)^{3}N}}+\frac{3464c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)^{2}N},$
(66)

where $\widehat{\pi}(s)\in\arg\max_{a}\widehat{Q}(s,a)$ for any
$s\in\mathcal{S}$.

As we have demonstrated in Lemma 2, the output of Algorithm 1 satisfies
$\big{\|}\widehat{Q}-\widehat{Q}^{\star}_{\mathsf{pe}}\big{\|}_{\infty}\leq
1/N$ once the iteration number exceeds
$\tau_{\max}\geq\frac{\log\frac{N}{1-\gamma}}{\log(1/\gamma)}$, thus making
Theorem 5 applicable. Taking the right-hand side of (66) to be no larger than
$\varepsilon$ reveals that:
$V^{\star}(\rho)-V^{\widehat{\pi}}(\rho)\leq\varepsilon$ holds as long as $N$
exceeds

$\displaystyle
N\geq\frac{21000c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)^{3}\varepsilon^{2}},$
(67)

given that $\varepsilon\in\big{(}0,\frac{1}{1-\gamma}\big{]}$.

The remainder of this section is thus dedicated to establishing Theorem 5.
Throughout the proof, it suffices to focus on the case where

$\displaystyle
N\geq\frac{c_{3}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{1-\gamma}$
(68)

for some large constant $c_{3}\geq 2880000$; otherwise the claim (66) follows
directly since
$V^{\star}(\rho)-V^{\widehat{\pi}}(\rho)\leq\frac{1}{1-\gamma}$.

###  6.1 Preliminary facts

Before embarking on the proof, we collect a couple of preliminary facts that
will be used multiple times.

##### Properties of $N(s,a)$.

To begin with, the quantity $N(s,a)$ — the total number of sample transitions
from $(s,a)$ — can be bounded through the following lemma; the proof is
provided in Appendix A.3.

######  Lemma 4.

Consider any $\delta\in(0,1)$. With probability at least $1-\delta$, the
quantities $\\{N(s,a)\\}$ in (24) obey

$\displaystyle\max\Big{\\{}N(s,a),\frac{2}{3}\log\frac{N}{\delta}\Big{\\}}$
$\displaystyle\geq\frac{Nd^{\mathsf{b}}(s,a)}{12}$ (69)

simultaneously for all $(s,a)\in\mathcal{S}\times\mathcal{A}$.

##### Properties about $\widehat{V}$ and $\widehat{V}^{\star}_{\mathsf{pe}}$.

First of all, note that the assumption

$\displaystyle\big{\|}\widehat{Q}-\widehat{Q}^{\star}_{\mathsf{pe}}\big{\|}_{\infty}\leq\frac{1}{N}$
(70)

has the following direct consequence:

$\displaystyle\big{\|}\widehat{V}-\widehat{V}^{\star}_{\mathsf{pe}}\big{\|}_{\infty}=\max_{s}\left|\max_{a}\widehat{Q}(s,a)-\max_{a}\widehat{Q}^{\star}_{\mathsf{pe}}(s,a)\right|\leq\big{\|}\widehat{Q}-\widehat{Q}^{\star}_{\mathsf{pe}}\big{\|}_{\infty}\leq\frac{1}{N}.$
(71)

Given the proximity of $\widehat{V}$ and $\widehat{V}^{\star}_{\mathsf{pe}}$,
we can bound the difference of the corresponding variance terms as follows:

$\displaystyle\left|\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}_{\mathsf{pe}}^{\star}\big{)}-\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}\big{)}\right|$
$\displaystyle\overset{\mathrm{(i)}}{=}\left|\widehat{P}_{s,a}\big{(}\widehat{V}_{\mathsf{pe}}^{\star}\circ\widehat{V}_{\mathsf{pe}}^{\star}\big{)}-\widehat{P}_{s,a}\big{(}\widehat{V}\circ\widehat{V}\big{)}+\big{(}\widehat{P}_{s,a}\widehat{V}\big{)}^{2}-\big{(}\widehat{P}_{s,a}\widehat{V}_{\mathsf{pe}}^{\star}\big{)}^{2}\right|$
$\displaystyle=\left|\widehat{P}_{s,a}\Big{(}\big{(}\widehat{V}+\widehat{V}_{\mathsf{pe}}^{\star}\big{)}\circ\big{(}\widehat{V}_{\mathsf{pe}}^{\star}-\widehat{V}\big{)}\Big{)}+\left(\widehat{P}_{s,a}\big{(}\widehat{V}+\widehat{V}_{\mathsf{pe}}^{\star}\big{)}\right)\left(\widehat{P}_{s,a}\big{(}\widehat{V}_{\mathsf{pe}}^{\star}-\widehat{V}\big{)}\right)\right|$
$\displaystyle\leq\big{\|}\widehat{P}_{s,a}\big{\|}_{1}\big{\|}\widehat{V}+\widehat{V}_{\mathsf{pe}}^{\star}\big{\|}_{\infty}\big{\|}\widehat{V}_{\mathsf{pe}}^{\star}-\widehat{V}\big{\|}_{\infty}+\big{\|}\widehat{P}_{s,a}\big{\|}_{1}^{2}\big{\|}\widehat{V}+\widehat{V}_{\mathsf{pe}}^{\star}\big{\|}_{\infty}\big{\|}\widehat{V}_{\mathsf{pe}}^{\star}-\widehat{V}\big{\|}_{\infty}$
$\displaystyle\leq\left(\big{\|}\widehat{P}_{s,a}\big{\|}_{1}+\big{\|}\widehat{P}_{s,a}\big{\|}_{1}^{2}\right)\left(2\big{\|}\widehat{V}\big{\|}_{\infty}+\big{\|}\widehat{V}_{\mathsf{pe}}^{\star}-\widehat{V}\big{\|}_{\infty}\right)\big{\|}\widehat{V}_{\mathsf{pe}}^{\star}-\widehat{V}\big{\|}_{\infty}$
$\displaystyle\leq\frac{2}{N}\left(\frac{2}{1-\gamma}+\frac{1}{N}\right)\leq\frac{6}{(1-\gamma)N}.$
(72)

Here, (i) follows from the definition (8), the penultimate inequality follows
from (71) and the basic facts $\|\widehat{P}_{s,a}\|_{1}=1$ and
$\|\widehat{V}\|_{\infty}\leq\frac{1}{1-\gamma}$, while the last line relies
on (68).

Armed with (72), one can further control the difference of the associated
penalty terms. Note that the definition of $b(s,a;V)$ in (28) tells us that

$\displaystyle\left|b\big{(}s,a;\widehat{V}_{\mathsf{pe}}^{\star}\big{)}-b\big{(}s,a;\widehat{V}\big{)}\right|$
$\displaystyle=\Bigg{|}\min\Bigg{\\{}\max\bigg{\\{}\sqrt{\frac{c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{N(s,a)}\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}_{\mathsf{pe}}^{\star}\big{)}},\frac{2c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{(1-\gamma)N(s,a)}\bigg{\\}},\frac{1}{1-\gamma}\Bigg{\\}}$
$\displaystyle\qquad-\min\Bigg{\\{}\max\bigg{\\{}\sqrt{\frac{c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{N(s,a)}\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}\big{)}},\frac{2c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{(1-\gamma)N(s,a)}\bigg{\\}},\frac{1}{1-\gamma}\Bigg{\\}}\Bigg{|}.$
(73)

If at least one of the variance terms is not too small in the sense that

$\max\left\\{\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}_{\mathsf{pe}}^{\star}\big{)},\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}\big{)}\right\\}\geq\frac{4c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{(1-\gamma)^{2}N(s,a)},$
(74)

then (73) implies that

$\displaystyle\eqref{eq:b-difference-definition-inf}$
$\displaystyle\leq\sqrt{\frac{c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{N(s,a)}}\left|\sqrt{\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}_{\mathsf{pe}}^{\star}\big{)}}-\sqrt{\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}\big{)}}\right|=\sqrt{\frac{c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{N(s,a)}}\frac{\big{|}\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}_{\mathsf{pe}}^{\star}\big{)}-\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}\big{)}\big{|}}{\sqrt{\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}_{\mathsf{pe}}^{\star}\big{)}}+\sqrt{\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}\big{)}}}$
$\displaystyle\overset{\mathrm{(i)}}{\leq}\frac{1-\gamma}{2}\Big{|}\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}_{\mathsf{pe}}^{\star}\big{)}-\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widehat{V}\big{)}\Big{|}\overset{\mathrm{(ii)}}{\leq}\frac{3}{N},$
(75)

where (i) results from (74), and (ii) holds due to (72). On the other hand, if
(74) is not satisfied, then one clearly has
$b\big{(}s,a;\widehat{V}_{\mathsf{pe}}^{\star}\big{)}=b\big{(}s,a;\widehat{V}\big{)}$.
In conclusion, in all cases we have

$\displaystyle\left|b\big{(}s,a;\widehat{V}_{\mathsf{pe}}^{\star}\big{)}-b\big{(}s,a;\widehat{V}\big{)}\right|\leq\frac{3}{N}.$
(76)

###  6.2 Proof of Theorem 5

Armed with the preceding preliminary facts, we can readily turn to the proof
of Theorem 5. By virtue of Lemma 4, our proof shall — unless otherwise noted —
operate on the high-probability event that

$\displaystyle\forall(s,a)\in\mathcal{S}\times\mathcal{A}:\qquad\max\bigg{\\{}N(s,a),\frac{2}{3}\log\frac{SN}{\delta}\bigg{\\}}$
$\displaystyle\geq\frac{Nd^{\mathsf{b}}(s,a)}{12}.$ (77)

In addition, from the sampling model (17), the sample transitions employed to
form $\widehat{P}$ are statistically independent conditional on
$\\{N(s,a)\\}$. Our proof consists of four steps as detailed below.

##### Step 1: Bernstein-style inequalities and leave-one-out decoupling
argument.

We are in need of tight control of the size of
$\big{(}\widehat{P}_{s,a}-P_{s,a}\big{)}\widehat{V}$. However, this becomes
challenging due to the statistical dependency between $\widehat{P}$ and the
value estimate $\widehat{V}$ (given that we reuse samples in all iterations of
Algorithm 1). In order to circumvent this difficulty, we resort to a leave-
one-out argument to decouple the statistical dependency, as motivated by
Agarwal et al., (2020); Li et al., 2024b . The result stated below establishes
Bernstein-style inequalities despite the complicated dependency.

######  Lemma 5.

Suppose that $\gamma\in[\frac{1}{2},1)$, and consider any $\delta\in(0,1)$.
With probability at least $1-\delta$, we have

$\displaystyle\Big{|}\big{(}\widehat{P}_{s,a}-P_{s,a}\big{)}\widetilde{V}\Big{|}$
$\displaystyle\leq
12\sqrt{\frac{\log\frac{2N}{(1-\gamma)\delta}}{N(s,a)}\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widetilde{V}\big{)}}+\frac{74\log\frac{2N}{(1-\gamma)\delta}}{(1-\gamma)N(s,a)},$
(78a)
$\displaystyle\mathsf{Var}_{\widehat{P}_{s,a}}\big{(}\widetilde{V}\big{)}$
$\displaystyle\leq
2\mathsf{Var}_{P_{s,a}}\big{(}\widetilde{V}\big{)}+\frac{41\log\frac{2N}{(1-\gamma)\delta}}{(1-\gamma)^{2}N(s,a)}$
(78b)

simultaneously for all $(s,a)\in\mathcal{S}\times\mathcal{A}$ and all
$\widetilde{V}$ with
$\big{\|}\widetilde{V}-\widehat{V}^{\star}_{\mathsf{pe}}\big{\|}_{\infty}\leq\frac{1}{N}$
and $\|\widetilde{V}\|_{\infty}\leq\frac{1}{1-\gamma}$.

###### High-level proof ideas.

In short, the proof consists of contructing a finite collection of auxiliary
MDPs $\\{\widehat{\mathcal{M}}^{s,u}\\}$ for each state $s$ obeying the
following properties: (i) each $\widehat{\mathcal{M}}^{s,u}$ is constructed
without using any sample transition that comes from state $s$, and is hence
statistically independent from $\widehat{P}_{s,a}$ for all $a\in\mathcal{A}$
(instead, the useful information is embedded into the corresponding immediate
reward, which is a low-dimensional object and easier to control); (ii) at
least one of the MDPs in $\\{\widehat{\mathcal{M}}^{s,u}\\}$ is extremely
close to the true MDP in terms of the resulting value function. With the aid
of these leave-one-out auxiliary MDPs, one can control
$\big{(}\widehat{P}_{s,a}-P_{s,a}\big{)}\widetilde{V}$ by first exploiting the
statistical independence between $\widehat{P}_{s,a}$ and
$\\{\widehat{\mathcal{M}}^{s,u}\\}$ and then transferring the concentration
bound back to the original MDP using the proximity property (ii). The
construction of these auxiliary MDPs and the proof details can be found in
Appendix A.4. ∎

Note that (78a) has been derived only for those pairs $(s,a)$ with $N(s,a)>0$.
For every $(s,a)$ with $N(s,a)=0$, one can directly obtain

$\Big{|}\big{(}\widehat{P}_{s,a}-P_{s,a}\big{)}\widetilde{V}\Big{|}=\big{|}P_{s,a}\widetilde{V}\big{|}\leq\big{\|}P_{s,a}\big{\|}_{1}\big{\|}\widetilde{V}\big{\|}_{\infty}\leq\frac{1}{1-\gamma}.$

Putting these bounds together with the definition (28) of $b(s,a;V)$ reveals
that

$\displaystyle\Big{|}\big{(}\widehat{P}_{s,a}-P_{s,a}\big{)}\widetilde{V}\Big{|}+\frac{5}{N}\leq
b\big{(}s,a;\widetilde{V}\big{)}\qquad\text{for all
}(s,a)\in\mathcal{S}\times\mathcal{A}$ (79)

for all $\widetilde{V}$ obeying
$\big{\|}\widetilde{V}-\widehat{V}^{\star}_{\mathsf{pe}}\big{\|}_{\infty}\leq\frac{1}{N}$
and $\|\widetilde{V}\|_{\infty}\leq\frac{1}{1-\gamma}$, provided that the
constant $c_{\mathsf{b}}$ is sufficiently large. The remainder of the proof
should then also operate on the high-probability events (79) and (78b), in
addition to assuming that the event (77) occurs.

##### Step 2: showing that $\widehat{Q}(s,a)$ is a lower bound on
$Q^{\widehat{\pi}}(s,a)$.

We now justify that $\widehat{Q}(s,a)$ (resp. $\widehat{V}(s)$) is a
“pessimistic” estimate of $Q^{\widehat{\pi}}(s,a)$ (resp.
$V^{\widehat{\pi}}(s)$); this is enabled by the pessimism principle (so that
the algorithm effectively seeks lower estimates of the value iteration) and
the Bernstein-style bounds in Lemma 5 (so that the penalty term always
dominates the uncertainty incurred by using the empirical MDP).

To begin with, recall that $\widehat{Q}^{\star}_{\mathsf{pe}}(s,a)$ is the
unique fixed point of the pessimistic Bellman operator that obeys

$\displaystyle\widehat{Q}^{\star}_{\mathsf{pe}}(s,a)=\max\Big{\\{}r(s,a)+\gamma\widehat{P}_{s,a}\widehat{V}^{\star}_{\mathsf{pe}}-b\big{(}s,a;\widehat{V}^{\star}_{\mathsf{pe}}\big{)},0\Big{\\}}.$
(80)

In the sequel, we divide the set of state-action pairs $(s,a)$ into two types.

  * •

Case 1: $\widehat{Q}^{\star}_{\mathsf{pe}}(s,a)=0$. Given that
$\widehat{Q}_{0}=0$, Lemma 2 tells us that

$\widehat{Q}(s,a)=\widehat{Q}_{\tau_{\max}}(s,a)\leq\widehat{Q}^{\star}_{\mathsf{pe}}(s,a)=0.$

This combined with the basic fact $Q^{\widehat{\pi}}\geq 0$ immediately yields
$0=\widehat{Q}(s,a)\leq Q^{\widehat{\pi}}(s,a)$.

  * •

Case 2:
$\widehat{Q}^{\star}_{\mathsf{pe}}(s,a)=r(s,a)+\gamma\widehat{P}_{s,a}\widehat{V}^{\star}_{\mathsf{pe}}-b\big{(}s,a;\widehat{V}^{\star}_{\mathsf{pe}}\big{)}>0$.
It is first observed that

$\displaystyle\widehat{Q}(s,a)$
$\displaystyle\overset{\text{(i)}}{\leq}\widehat{Q}^{\star}_{\mathsf{pe}}(s,a)+\frac{1}{N}\overset{\text{(ii)}}{=}r(s,a)-b\big{(}s,a;\widehat{V}^{\star}_{\mathsf{pe}}\big{)}+\gamma\widehat{P}_{s,a}\widehat{V}^{\star}_{\mathsf{pe}}+\frac{1}{N}$
$\displaystyle\leq
r(s,a)-b\big{(}s,a;\widehat{V}^{\star}_{\mathsf{pe}}\big{)}+\gamma\widehat{P}_{s,a}\widehat{V}+\frac{1}{N}+\gamma\big{\|}\widehat{P}_{s,a}\big{\|}_{1}\big{\|}\widehat{V}-\widehat{V}_{\mathsf{pe}}^{\star}\big{\|}_{\infty}$
$\displaystyle\overset{\text{(iii)}}{\leq}r(s,a)-b\big{(}s,a;\widehat{V}^{\star}_{\mathsf{pe}}\big{)}+\gamma\widehat{P}_{s,a}\widehat{V}+\frac{2}{N}$
$\displaystyle\leq r(s,a)-b\big{(}s,a;\widehat{V}\big{)}+\gamma
P_{s,a}\widehat{V}+\frac{2}{N}+\gamma\Big{|}\big{(}\widehat{P}_{s,a}-P_{s,a}\big{)}\widehat{V}\Big{|}+\left|b\big{(}s,a;\widehat{V}_{\mathsf{pe}}^{\star}\big{)}-b\big{(}s,a;\widehat{V}\big{)}\right|$
$\displaystyle\overset{\text{(iv)}}{\leq}r(s,a)+\gamma P_{s,a}\widehat{V}.$
(81)

Here, (i) and (iii) arise from the assumption (70), (ii) relies on the fact
that $\widehat{Q}_{\mathsf{pe}}^{\star}$ is the fixed point of the operator
$\widehat{\mathcal{T}}_{\mathsf{pe}}$, whereas (iv) takes advantage of (76)
and (79). Combining (81) with the Bellman equation $Q^{\widehat{\pi}}=r+\gamma
PV^{\widehat{\pi}}$ results in

$\displaystyle Q^{\widehat{\pi}}(s,a)-\widehat{Q}(s,a)\geq r(s,a)+\gamma
P_{s,a}V^{\widehat{\pi}}-\big{(}r(s,a)+\gamma P_{s,a}\widehat{V}\big{)}=\gamma
P_{s,a}\big{(}V^{\widehat{\pi}}-\widehat{V}\big{)}.$ (82)

Suppose for the moment that there exists some $(s,a)$ obeying
$Q^{\widehat{\pi}}(s,a)-\widehat{Q}(s,a)<0$ (which clearly cannot happen in
Case 1), then
$\arg\min_{s,a}\big{[}Q^{\widehat{\pi}}(s,a)-\widehat{Q}(s,a)\big{]}$ must
belong to Case 2. Thus, taking the minimum over $(s,a)$ and using the above
inequality (82) give

$\displaystyle\min_{s,a}\big{[}Q^{\widehat{\pi}}(s,a)-\widehat{Q}(s,a)\big{]}$
$\displaystyle\geq\min_{s,a}\big{[}\gamma
P_{s,a}\big{(}V^{\widehat{\pi}}-\widehat{V}\big{)}\big{]}\overset{\text{(i)}}{\geq}\gamma\min_{s}\big{[}V^{\widehat{\pi}}(s)-\widehat{V}(s)\big{]}$
$\displaystyle=\gamma\min_{s}\big{[}Q^{\widehat{\pi}}\big{(}s,\widehat{\pi}(s)\big{)}-\widehat{Q}\big{(}s,\widehat{\pi}(s)\big{)}\big{]}\geq\gamma\min_{s,a}\big{[}Q^{\widehat{\pi}}(s,a)-\widehat{Q}(s,a)\big{]},$
(83)

where (i) holds since $P_{s,a}\in\Delta(\mathcal{S})$. Given that
$1>\gamma>0$, inequality (83) holds only when
$\min_{s,a}\big{[}Q^{\widehat{\pi}}(s,a)-\widehat{Q}(s,a)\big{]}\geq 0$. We
therefore conclude that in this case, one also has
$Q^{\widehat{\pi}}(s,a)\geq\widehat{Q}(s,a)$.

With the arguments for the above two cases in place, we arrive at

$Q^{\widehat{\pi}}(s,a)\geq\widehat{Q}(s,a)\qquad\text{for all
}(s,a)\in\mathcal{S}\times\mathcal{A},$ (84)

and evidently,

$V^{\star}(s)\geq
V^{\widehat{\pi}}(s)=Q^{\widehat{\pi}}\big{(}s,\widehat{\pi}(s)\big{)}\geq\widehat{Q}\big{(}s,\widehat{\pi}(s)\big{)}=\max_{a}\widehat{Q}(s,a)=\widehat{V}(s)\qquad\text{for
all }s\in\mathcal{S}.$ (85)

##### Step 3: bounding $V^{\star}(s)-V^{\widehat{\pi}}(s)$.

Recall that the Bellman optimality equation gives

$\displaystyle V^{\star}(s)=r\big{(}s,\pi^{\star}(s)\big{)}+\gamma
P_{s,\pi^{\star}(s)}V^{\star}.$ (86)

Before continuing, we make note of the following lower bound on $\widehat{V}$:

$\displaystyle\widehat{V}(s)$
$\displaystyle=\max_{a}\widehat{Q}(s,a)\geq\widehat{Q}\big{(}s,\pi^{\star}(s)\big{)}\overset{\mathrm{(i)}}{\geq}\widehat{Q}^{\star}_{\mathsf{pe}}\big{(}s,\pi^{\star}(s)\big{)}-\frac{1}{N}$
$\displaystyle\overset{\mathrm{(ii)}}{\geq}r\big{(}s,\pi^{\star}(s)\big{)}-b\big{(}s,\pi^{\star}(s);\widehat{V}^{\star}_{\mathsf{pe}}\big{)}+\gamma\widehat{P}_{s,\pi^{\star}(s)}\widehat{V}_{\mathsf{pe}}^{\star}-\frac{1}{N}$
$\displaystyle=r\big{(}s,\pi^{\star}(s)\big{)}-b\big{(}s,\pi^{\star}(s);\widehat{V}^{\star}_{\mathsf{pe}}\big{)}+\gamma\widehat{P}_{s,\pi^{\star}(s)}\widehat{V}-\frac{1}{N}-\gamma\widehat{P}_{s,\pi^{\star}(s)}\big{(}\widehat{V}-\widehat{V}_{\mathsf{pe}}^{\star}\big{)}$
$\displaystyle\overset{\mathrm{(iii)}}{\geq}r\big{(}s,\pi^{\star}(s)\big{)}-b\big{(}s,\pi^{\star}(s);\widehat{V}^{\star}_{\mathsf{pe}}\big{)}+\gamma\widehat{P}_{s,\pi^{\star}(s)}\widehat{V}-\frac{2}{N}$
$\displaystyle\geq
r\big{(}s,\pi^{\star}(s)\big{)}-b\big{(}s,\pi^{\star}(s);\widehat{V}\big{)}+\gamma
P_{s,\pi^{\star}(s)}\widehat{V}-\frac{2}{N}-\gamma\Big{|}\big{(}\widehat{P}_{s,\pi^{\star}(s)}-P_{s,\pi^{\star}(s)}\big{)}\widehat{V}\Big{|}$
$\displaystyle\qquad-\left|b\big{(}s,\pi^{\star}(s);\widehat{V}_{\mathsf{pe}}^{\star}\big{)}-b\big{(}s,\pi^{\star}(s);\widehat{V}\big{)}\right|$
$\displaystyle\overset{\mathrm{(iv)}}{\geq}r\big{(}s,\pi^{\star}(s)\big{)}-2b\big{(}s,\pi^{\star}(s);\widehat{V}\big{)}+\gamma
P_{s,\pi^{\star}(s)}\widehat{V}.$ (87)

Here, (i) results from the assumption (70), (ii) relies on (80), (iii) is
valid since
$\widehat{P}_{s,\pi^{\star}(s)}\big{(}\widehat{V}-\widehat{V}_{\mathsf{pe}}^{\star}\big{)}\leq\big{\|}\widehat{P}_{s,\pi^{\star}(s)}\big{\|}_{1}\big{\|}\widehat{V}-\widehat{V}_{\mathsf{pe}}^{\star}\big{\|}_{\infty}\leq
1/N$, whereas (iv) holds by virtue of (76) and (79). Armed with the results in
(86) and (87), we can readily show that

$\displaystyle\big{\langle}\rho,V^{\star}-\widehat{V}\big{\rangle}$
$\displaystyle=\sum_{s\in\mathcal{S}}\rho(s)\big{(}V^{\star}(s)-\widehat{V}(s)\big{)}$
$\displaystyle\leq\sum_{s\in\mathcal{S}}\rho(s)\left\\{r\big{(}s,\pi^{\star}(s)\big{)}+\gamma
P_{s,\pi^{\star}(s)}V^{\star}-\left(r\big{(}s,\pi^{\star}(s)\big{)}-2b\big{(}s,\pi^{\star}(s);\widehat{V}\big{)}+\gamma
P_{s,\pi^{\star}(s)}\widehat{V}\right)\right\\}$
$\displaystyle\leq\gamma\sum_{s\in\mathcal{S}}\rho(s)P_{s,\pi^{\star}(s)}\big{(}V^{\star}-\widehat{V}\big{)}+2\sum_{s\in\mathcal{S}}\rho(s)b\big{(}s,\pi^{\star}(s);\widehat{V}\big{)}.$
(88)

For notational convenience, let us introduce a matrix
$P^{\star}\in\mathbb{R}^{S\times S}$ and a vector
$b^{\star}\in\mathbb{R}^{S\times 1}$ whose $s$-th row are given respectively
by

$\displaystyle\big{[}P^{\star}\big{]}_{s,\cdot}\coloneqq
P_{s,\pi^{\star}(s)}\qquad\text{and}\qquad b^{\star}(s)\coloneqq
b\big{(}s,\pi^{\star}(s);\widehat{V}\big{)}\qquad\quad\text{for all
}s\in\mathcal{S}.$ (89)

This allows us to rewrite (88) in the following matrix/vector form:

$\displaystyle\rho^{\top}\big{(}V^{\star}-\widehat{V}\big{)}\leq\gamma\rho^{\top}P^{\star}\big{(}V^{\star}-\widehat{V}\big{)}+2\rho^{\top}b^{\star}.$
(90)

Note that this relation holds for any arbitrary $\rho$. Apply it recursively
to arrive at

$\displaystyle\rho^{\top}\big{(}V^{\star}-\widehat{V}\big{)}$
$\displaystyle\leq\big{(}\gamma\rho^{\top}P^{\star}\big{)}\big{(}V^{\star}-\widehat{V}\big{)}+2\rho^{\top}b^{\star}$
$\displaystyle\leq\gamma\big{(}\gamma\rho^{\top}P^{\star}\big{)}P^{\star}\big{(}V^{\star}-\widehat{V}\big{)}+2\big{(}\gamma\rho^{\top}P^{\star}\big{)}b^{\star}+2\rho^{\top}b^{\star}$
$\displaystyle=\gamma^{2}\rho^{\top}\big{(}P^{\star}\big{)}^{2}\big{(}V^{\star}-\widehat{V}\big{)}+2\gamma\rho^{\top}P^{\star}b^{\star}+2\rho^{\top}b^{\star}$
$\displaystyle\leq\cdots\leq\left\\{\lim_{i\rightarrow\infty}\gamma^{i}\rho^{\top}\big{(}P^{\star}\big{)}^{i}\big{(}V^{\star}-\widehat{V}\big{)}\right\\}+2\rho^{\top}\bigg{\\{}\sum_{i=0}^{\infty}\gamma^{i}\big{(}P^{\star}\big{)}^{i}\bigg{\\}}b^{\star}$
$\displaystyle\overset{\mathrm{(i)}}{=}2\rho^{\top}\bigg{\\{}\sum_{i=0}^{\infty}\gamma^{i}\big{(}P^{\star}\big{)}^{i}\bigg{\\}}b^{\star}=2\rho^{\top}\big{(}I-\gamma
P^{\star}\big{)}^{-1}b^{\star}$ $\displaystyle=\frac{2}{1-\gamma}\langle
d^{\star},b^{\star}\rangle,$ (91)

where (i) holds since
$\lim_{i\to\infty}\gamma^{i}\rho^{\top}\big{(}P^{\star}\big{)}^{i}\big{(}V^{\star}-\widehat{V}\big{)}=0$
(given that $\lim_{i\rightarrow\infty}\gamma^{i}=0$ and
$\|\rho^{\top}\big{(}P^{\star}\big{)}^{i}\|_{1}=1$ for any $i\geq 0$), and the
last equality results from the definition of $d^{\star}$ (see (16)) expressed
in the following matrix/vector form:

$\displaystyle\big{(}d^{\star}\big{)}^{\top}=(1-\gamma)\sum_{t=0}^{\infty}\gamma^{t}\rho^{\top}\big{(}P^{\star}\big{)}^{t}=(1-\gamma)\rho^{\top}\big{(}I-\gamma
P^{\star}\big{)}^{-1}.$ (92)

Combine the above inequality with (85) to reach

$\displaystyle\big{\langle}\rho,V^{\star}-V^{\widehat{\pi}}\big{\rangle}\leq\big{\langle}\rho,V^{\star}-\widehat{V}\big{\rangle}\leq\frac{2\big{\langle}d^{\star},b^{\star}\big{\rangle}}{1-\gamma}.$
(93)

##### Step 4: using concentrability to control
$\big{\langle}d^{\star},b^{\star}\big{\rangle}$.

We shall control $\big{\langle}d^{\star},b^{\star}\big{\rangle}$ by dividing
the state set $\mathcal{S}$ into the following two disjoint subsets:

$\displaystyle\mathcal{S}^{\mathsf{small}}\coloneqq\bigg{\\{}s\in\mathcal{S}\mid
Nd^{\mathsf{b}}\big{(}s,\pi^{\star}(s)\big{)}\leq
8\log\frac{NS}{(1-\gamma)\delta}\bigg{\\}};$ (94a)
$\displaystyle\mathcal{S}^{\mathsf{large}}\coloneqq\bigg{\\{}s\in\mathcal{S}\mid
Nd^{\mathsf{b}}\big{(}s,\pi^{\star}(s)\big{)}>8\log\frac{NS}{(1-\gamma)\delta}\bigg{\\}}.$
(94b)

  * •

To begin with, consider any state $s\in\mathcal{S}^{\mathsf{small}}$. Applying
Definition 2 and the definition of $\mathcal{S}^{\mathsf{small}}$ yields

$\displaystyle\min\Big{\\{}d^{\star}(s),\frac{1}{S}\Big{\\}}\leq
C^{\star}_{\mathsf{clipped}}d^{\mathsf{b}}\big{(}s,\pi^{\star}(s)\big{)}\leq\frac{8C^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{N}<\frac{1}{S},$
(95)

provided that
$N>8SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}$ (see (68)).
This inequality necessarily implies that

$\displaystyle
d^{\star}(s)\leq\frac{8C^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{N}<\frac{1}{S}.$
(96)

Combining the preceding inequality with the following fact (see the definition
(28))

$\displaystyle b^{\star}(s)\coloneqq
b\big{(}s,\pi^{\star}(s);\widehat{V}\big{)}\leq\frac{1}{1-\gamma}+\frac{5}{N},$
(97)

we arrive at

$\displaystyle\sum_{s\in\mathcal{S}^{\mathsf{small}}}d^{\star}(s)b^{\star}(s)$
$\displaystyle\leq\sum_{s\in\mathcal{S}^{\mathsf{small}}}\left(\frac{8C^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}+d^{\star}(s)\frac{5}{N}\right)\leq\frac{8SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}+\frac{5}{N}.$
(98)

  * •

Next, we turn to any state $s\in\mathcal{S}^{\mathsf{large}}$. Using the
definition (28) of $b(s,a;V)$, we obtain

$\displaystyle b^{\star}(s)$
$\displaystyle=b\big{(}s,\pi^{\star}(s);\widehat{V}\big{)}\leq\sqrt{\frac{c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{N\big{(}s,\pi^{\star}(s)\big{)}}\mathsf{Var}_{\widehat{P}_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}}+\frac{2c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{(1-\gamma)N\big{(}s,\pi^{\star}(s)\big{)}}+\frac{5}{N}$
$\displaystyle\overset{\mathrm{(i)}}{\leq}\sqrt{\frac{c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{N\big{(}s,\pi^{\star}(s)\big{)}}\left(2\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}+\frac{41\log\frac{2N}{(1-\gamma)\delta}}{(1-\gamma)^{2}N\big{(}s,\pi^{\star}(s)\big{)}}\right)}+\frac{2c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{(1-\gamma)N\big{(}s,\pi^{\star}(s)\big{)}}+\frac{5}{N}$
$\displaystyle\overset{\mathrm{(ii)}}{\leq}\sqrt{\frac{2c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{N\big{(}s,\pi^{\star}(s)\big{)}}\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}}+\frac{4c_{\mathsf{b}}\log\frac{N}{(1-\gamma)\delta}}{(1-\gamma)N\big{(}s,\pi^{\star}(s)\big{)}},$
(99)

where (i) arises from Lemma 5 and (71), (ii) applies the elementary inequality
$\sqrt{x+y}\leq\sqrt{x}+\sqrt{y}$ for any $x,y\geq 0$ and the fact $N\geq
N(s,a)$, in addition to assuming that $c_{\mathsf{b}}$ is large enough. To
continue, we observe that

$\displaystyle\frac{1}{N\big{(}s,\pi^{\star}(s)\big{)}}\overset{\mathrm{(i)}}{\leq}\frac{12}{Nd^{\mathsf{b}}\big{(}s,\pi^{\star}(s)\big{)}}\overset{\mathrm{(ii)}}{\leq}\frac{12C^{\star}_{\mathsf{clipped}}}{N\min\big{\\{}d^{\star}(s),\frac{1}{S}\big{\\}}}\leq\frac{12C^{\star}_{\mathsf{clipped}}}{N}\left(\frac{1}{d^{\star}(s)}+S\right),$
(100)

where (i) follows from the assumption (77) and the definition of
$\mathcal{S}^{\mathsf{large}}$, and (ii) results from Assumption 2.
Substitution into (99) yields

$\displaystyle b^{\star}(s)$
$\displaystyle\leq\underset{\eqqcolon\,\alpha_{1}(s)}{\underbrace{\sqrt{\frac{24c_{\mathsf{b}}C^{\star}_{\mathsf{clipped}}\log\frac{N}{(1-\gamma)\delta}}{N}\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}}\left(\frac{1}{\sqrt{d^{\star}(s)}}+\sqrt{S}\right)}}+\underset{\eqqcolon\,\alpha_{2}(s)}{\underbrace{\frac{48c_{\mathsf{b}}C^{\star}_{\mathsf{clipped}}\log\frac{N}{(1-\gamma)\delta}}{(1-\gamma)N}\left(\frac{1}{d^{\star}(s)}+S\right)}},$
(101)

where the last line comes from the elementary inequality
$\sqrt{x+y}\leq\sqrt{x}+\sqrt{y}$ for any $x,y\geq 0$.

To proceed, observe that the sum of the first terms in (101) satisfies

$\displaystyle\sum_{s\in\mathcal{S}^{\mathsf{large}}}d^{\star}(s)\alpha_{1}(s)$
$\displaystyle\quad=\sqrt{\frac{24c_{\mathsf{b}}C^{\star}_{\mathsf{clipped}}\log\frac{N}{(1-\gamma)\delta}}{N}}\left(\sum_{s\in\mathcal{S}^{\mathsf{large}}}\sqrt{d^{\star}(s)\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}}+\sum_{s\in\mathcal{S}^{\mathsf{large}}}\sqrt{d^{\star}(s)}\sqrt{Sd^{\star}(s)\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}}\right)$
$\displaystyle\quad\overset{\mathrm{(i)}}{\leq}\sqrt{\frac{24c_{\mathsf{b}}C^{\star}_{\mathsf{clipped}}\log\frac{N}{(1-\gamma)\delta}}{N}}\Bigg{(}\sqrt{S}\cdot\sqrt{\sum_{s\in\mathcal{S}^{\mathsf{large}}}d^{\star}(s)\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}}+\sqrt{\sum_{s\in\mathcal{S}^{\mathsf{large}}}Sd^{\star}(s)\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}}\Bigg{)}$
$\displaystyle\quad=\sqrt{\frac{96c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{N}{(1-\gamma)\delta}}{N}}\sqrt{\sum_{s\in\mathcal{S}^{\mathsf{large}}}d^{\star}(s)\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}},$
(102)

where (i) arises from the Cauchy-Schwarz inequality and the fact
$\sum_{s}d^{\star}(s)=1$. In addition, it is easily verified that the sum of
the second terms in (101) obeys

$\displaystyle\sum_{s\in\mathcal{S}^{\mathsf{large}}}d^{\star}(s)\alpha_{2}(s)\leq\frac{96c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{N}{(1-\gamma)\delta}}{(1-\gamma)N},$
(103)

which also makes use of the identity $\sum_{s}d^{\star}(s)=1$. Combining (102)
and (103) with (101) gives

$\displaystyle\sum_{s\in\mathcal{S}^{\mathsf{large}}}d^{\star}(s)b^{\star}\big{(}s,\pi^{\star}(s)\big{)}\leq\sum_{s\in\mathcal{S}^{\mathsf{large}}}d^{\star}(s)\alpha_{1}(s)+\sum_{s\in\mathcal{S}^{\mathsf{large}}}d^{\star}(s)\alpha_{2}(s)$
$\displaystyle\qquad\leq\sqrt{\frac{96c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{N}{(1-\gamma)\delta}}{N}}\sqrt{\sum_{s\in\mathcal{S}^{\mathsf{large}}}d^{\star}(s)\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}}+\frac{96c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{N}{(1-\gamma)\delta}}{(1-\gamma)N}.$
(104)

The above results (98) and (104) taken collectively give

$\displaystyle\big{\langle}d^{\star},b^{\star}\big{\rangle}=\sum_{s\in\mathcal{S}^{\mathsf{large}}}d^{\star}(s)b^{\star}(s)+\sum_{s\in\mathcal{S}^{\mathsf{small}}}d^{\star}(s)b^{\star}(s)$
$\displaystyle\quad\leq\sqrt{\frac{96c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{N}{(1-\gamma)\delta}}{N}}\sqrt{\sum_{s\in\mathcal{S}^{\mathsf{large}}}d^{\star}(s)\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}}+\frac{96c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{N}{(1-\gamma)\delta}}{(1-\gamma)N}$
$\displaystyle\quad\qquad+\frac{8SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}+\frac{5}{N}$
$\displaystyle\quad\overset{\mathrm{(i)}}{\leq}\sqrt{\frac{96c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{N}}\sqrt{\sum_{s\in\mathcal{S}}d^{\star}(s)\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}}+\frac{98c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}$
$\displaystyle\quad\overset{\mathrm{(ii)}}{\leq}\frac{2}{\gamma}\sqrt{\frac{96c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}\big{\langle}d^{\star},b^{\star}\big{\rangle}}+\frac{1}{\gamma}\sqrt{\frac{192c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}}+\frac{98c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N},$
$\displaystyle\quad\overset{\mathrm{(iii)}}{\leq}4\sqrt{\frac{96c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}\big{\langle}d^{\star},b^{\star}\big{\rangle}}+2\sqrt{\frac{192c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}}+\frac{98c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N},$
$\displaystyle\quad\overset{\mathrm{(iv)}}{\leq}\frac{1}{2}\big{\langle}d^{\star},b^{\star}\big{\rangle}+\frac{768c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}+\sqrt{\frac{768c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}}+\frac{98c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}.$

Here, (i) follows when $c_{\mathsf{b}}$ is sufficiently large and
$C^{\star}_{\mathsf{clipped}}\geq 1/S$ (see (21)), (ii) would hold as long as
the following inequality could be established:

$\displaystyle\sum_{s\in\mathcal{S}}d^{\star}(s)\mathsf{Var}_{P_{s,\pi^{\star}(s)}}\big{(}\widehat{V}\big{)}\leq\frac{2}{\gamma^{2}(1-\gamma)}+\frac{4}{\gamma^{2}(1-\gamma)}\big{\langle}d^{\star},b^{\star}\big{\rangle};$
(105)

(iii) is valid since $\gamma\in[\frac{1}{2},1)$, and (iv) follows from the
elementary inequality $2xy\leq x^{2}+y^{2}$. Rearranging terms, we are left
with

$\displaystyle\big{\langle}d^{\star},b^{\star}\big{\rangle}$
$\displaystyle\leq\sqrt{\frac{3072c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N}}+\frac{1732c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)N},$
(106)

which combined with (93) yields

$\displaystyle\big{\langle}\rho,V^{\star}-V^{\widehat{\pi}}\big{\rangle}\leq\frac{2\big{\langle}d^{\star},b^{\star}\big{\rangle}}{1-\gamma}\leq
120\sqrt{\frac{c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)^{3}N}}+\frac{3464c_{\mathsf{b}}SC^{\star}_{\mathsf{clipped}}\log\frac{NS}{(1-\gamma)\delta}}{(1-\gamma)^{2}N}.$
(107)

This concludes the proof, as long as the inequality (105) can be established.

##### Proof of inequality (105).

To begin with, we make the observation that

$\displaystyle\big{(}\widehat{V}\circ\widehat{V}\big{)}-\big{(}\gamma
P^{\star}\widehat{V})\circ\big{(}\gamma P^{\star}\widehat{V})$
$\displaystyle=\big{(}\widehat{V}-\gamma