Improved Sample Complexity Bounds for
Distributionally Robust Reinforcement Learning

Zaiyan Xu∗ Kishan Panaganti∗ Dileep Kalathil

Texas A&M University Texas A&M University Texas A&M University

###### Abstract

We consider the problem of learning a control policy that is robust against
the parameter mismatches between the training environment and testing
environment. We formulate this as a distributionally robust reinforcement
learning (DR-RL) problem where the objective is to learn the policy which
maximizes the value function against the worst possible stochastic model of
the environment in an uncertainty set. We focus on the tabular episodic
learning setting where the algorithm has access to a generative model of the
nominal (training) environment around which the uncertainty set is defined. We
propose the Robust Phased Value Learning (RPVL) algorithm to solve this
problem for the uncertainty sets specified by four different divergences:
total variation, chi-square, Kullback-Leibler, and Wasserstein. We show that
our algorithm achieves
$\tilde{\mathcal{O}}(\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert
H^{5})$ sample complexity, which is uniformly better than the existing results
by a factor of $\left\lvert\mathcal{S}\right\rvert$, where
$\left\lvert\mathcal{S}\right\rvert$ is number of states,
$\left\lvert\mathcal{A}\right\rvert$ is the number of actions, and $H$ is the
horizon length. We also provide the first-ever sample complexity result for
the Wasserstein uncertainty set. Finally, we demonstrate the performance of
our algorithm using simulation experiments.

##  1 Introduction

Training a Reinforcement Learning (RL) algorithm directly on the real-world
system is expensive and possibly dangerous since the standard RL algorithms
need a lot of data samples to learn even a reasonably performing policy. The
traditional solution to this issue is to train the RL algorithm on a simulator
before applying the trained policy to the real-world system. However, there
will inevitably be mismatches between the simulator model and the real-world
system owing to a variety of factors, including approximation errors made
during modeling, changes in the real-world parameters over time, and potential
adversarial disruptions in the real-world. For instance, the mass, friction,
sensor noise, floor terrain, and obstacles parameters of a mobile robot
simulator environment can be different from that of the real-world
environment. Standard RL algorithms often fail to perform well when faced with
even small changes between the training and testing environments (sim-to-real
gap) (Sünderhauf et al.,, 2018; Tobin et al.,, 2017; Peng et al.,, 2018).

Algorithm | Sample Complexity
---|---
TV | chi-square | Kullback-Leibler | Wasserstein
(Yang et al.,, 2021) | $\frac{\left\lvert\mathcal{S}\right\rvert^{2}\left\lvert\mathcal{A}\right\rvert H^{5}}{\rho^{2}\epsilon^{2}}$ | $\frac{(1+\rho)^{2}\left\lvert\mathcal{S}\right\rvert^{2}\left\lvert\mathcal{A}\right\rvert H^{5}}{(\sqrt{1+\rho}-1)^{2}\epsilon^{2}}$ | - | $\frac{\left\lvert\mathcal{S}\right\rvert^{2}\left\lvert\mathcal{A}\right\rvert H^{5}}{\rho^{2}\underline{p}^{2}\epsilon^{2}}$ | -
(Zhou et al.,, 2021) | - | - | $\frac{\mathrm{exp}\left(\mathcal{O}(H)\right)\left\lvert\mathcal{S}\right\rvert^{2}\left\lvert\mathcal{A}\right\rvert H^{5}}{\rho^{2}\epsilon^{2}}$ | - | -
(Shi and Chi,, 2022) | - | - | - | $\frac{\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert H^{5}}{\rho^{2}\underline{p}\epsilon^{2}}$ | -
(Panaganti and Kalathil,, 2022) | $\frac{\left\lvert\mathcal{S}\right\rvert^{2}\left\lvert\mathcal{A}\right\rvert H^{5}}{\epsilon^{2}}$ | $\frac{\rho\left\lvert\mathcal{S}\right\rvert^{2}\left\lvert\mathcal{A}\right\rvert H^{5}}{\epsilon^{2}}$ | $\frac{\mathrm{exp}\left(\mathcal{O}(H)\right)\left\lvert\mathcal{S}\right\rvert^{2}\left\lvert\mathcal{A}\right\rvert H^{5}}{\rho^{2}\epsilon^{2}}$ | - | -
This work | $\frac{\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert H^{5}}{\epsilon^{2}}$ | $\frac{(1+\rho)^{2}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert H^{5}}{(\sqrt{1+\rho}-1)^{2}\epsilon^{2}}$ | $\frac{\mathrm{exp}\left(\mathcal{O}(H)\right)\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert H^{5}}{\rho^{2}\epsilon^{2}}$ | $\frac{\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert H^{5}}{\rho^{2}\underline{p}^{2}\epsilon^{2}}$ | $\frac{(B_{p}+\rho^{p})^{2}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert H^{5}}{\rho^{2p}\epsilon^{2}}$
(Non-robust) Lower bound |
(Li et al.,, 2020) | ${\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert H^{4}}/{\epsilon^{2}}$
Table 1:  Sample complexity result comparison between our work and the
existing works for different uncertainty sets. Here,
$\left\lvert\mathcal{S}\right\rvert$ is number of states,
$\left\lvert\mathcal{A}\right\rvert$ is the number of actions, $H$ is the
horizon length, $\rho$ is the uncertainty parameter, $\epsilon\in(0,H)$ is the
sub-optimality level, $\underline{p}$ is the smallest positive state
transition probability of the nominal model, $p\in[1,\infty)$ is the
Wasserstein distance parameter, and $B_{p}$ is the maximal value of the
Wasserstein distance. Results in the infinite horizon setting are adapted to
finite horizon setting by using $H$ instead of $(1-\gamma)^{-1}$, where
$\gamma$ is the discount factor, and by adding an additional $H$ to
accommodate the non-stationary nature of the nominal model. The sample
complexity result of our work is uniformly better than all the existing works
by a factor of $\left\lvert\mathcal{S}\right\rvert$. Our bound also matches
with the non-robust RL lower bound in all factors, except in $H$.

Learning a policy that is robust against the model parameter mismatches
between the training and testing environments is the goal of distributionally
robust reinforcement learning (DR-RL). The framework of the robust Markov
decision process (RMDP) (Iyengar,, 2005; Nilim and El Ghaoui,, 2005) is used
to address the distributionally robust planning problem. The RMDP formulation
considers a collection of models known as the uncertainty set, as opposed to
the standard non-robust MDP which considers only one model. In DR-RL, the
objective is to learn the optimal robust policy that performs well even under
the worst model in the uncertainty set. The minimization over the uncertainty
set makes the RMDP and DR-RL problems significantly more challenging than
their non-robust counterparts.

The RMDP problem has been well studied in the literature (Xu and Mannor,,
2010; Wiesemann et al.,, 2013; Yu and Xu,, 2015; Mannor et al.,, 2016; Russel
and Petrik,, 2019), taking into account various types of uncertainty sets and
computationally effective techniques. These studies, however, are only
applicable to the planning problem. Learning algorithms have also been
proposed to solve the DR-RL problem (Roy et al.,, 2017; Panaganti and
Kalathil, 2021a, ; Wang and Zou,, 2021), but they only provide asymptotic
convergence guarantees. There are empirical works that address DR-RL problem
using deep RL methods (Pinto et al.,, 2017; Derman et al.,, 2018, 2020;
Mankowitz et al.,, 2020; Zhang et al., 2020a, ). However, these works do not
provide any provable guarantees on the performance of the learned policy.
Recently, there has also been works on using function approximation approaches
with offline data for DR-RL (Panaganti et al.,, 2022).

In this work, we develop a new model-based DR-RL algorithm, Robust Phased
Value Learning (RPVL) algorithm, with provable finite-sample performance
guarantees in the tabular, finite-horizon RMDP setting. We make the standard
generative model assumption used in the model-based non-robust RL literature
(Azar et al.,, 2013; Haskell et al.,, 2016; Agarwal et al.,, 2020; Li et al.,,
2020; Kalathil et al.,, 2021). More precisely, we assume that the algorithm
has access to a generative model that can generate next-state samples for all
state-action pairs according to the nominal model. We address the following
important (sample complexity) question: How many samples from the nominal
model are required to learn an $\epsilon$-optimal robust policy with a high
probability?

The closest to our work in the DR-RL literature are Yang et al., (2021); Zhou
et al., (2021); Panaganti and Kalathil, (2022). All of these works consider
the infinite horizon setting of the DR-RL problem where the nominal model is
stationary and obtains a sample complexity
$\tilde{\mathcal{O}}(\left\lvert\mathcal{S}\right\rvert^{2})$. However, many
real-world application have non-stationary dynamics and are episodic in nature
(Choi et al.,, 2009; Schulman et al.,, 2013; Zhang et al., 2020a, ). So, in
this work, we consider a non-stationary nominal model in a finite horizon
(episodic) DR-RL setting. The sample complexity of our algorithm is
$\tilde{\mathcal{O}}(\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert
H^{5})$, which is superior by a factor $\left\lvert\mathcal{S}\right\rvert$
compared to all the above mentioned existing works. Table 1 provides a
detailed comparison of our result with that of the existing works. We note
that a concurrent work (Shi and Chi,, 2022) also considered the finite horizon
DR-RL problem but in an offline RL setting and only with Kullback-Leibler
uncertainty set. Their sample complexity is
$\tilde{\mathcal{O}}(\left\lvert\mathcal{S}\right\rvert)$ which is similar to
ours.

#### Our Contributions:

$(1)$ We propose a new model-based DR-RL algorithm called RPVL algorithm
inspired by the phased value iteration (Kakade,, 2003, Algorithm 4) that takes
advantage of the non-stationary dynamics in each phase. In addition, we
develop an uncertainty-set-specific covering number argument instead of the
uniform covering number argument used in the prior works. Combining these, we
are able to establish the sample complexity
$\tilde{\mathcal{O}}(\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert
H^{5})$ for our RPVL algorithm. This not only improves the existing results
but also matches with that of the non-robust RL lower bound in
$\left\lvert\mathcal{S}\right\rvert$ and $\left\lvert\mathcal{A}\right\rvert$
(see Table 1).
$(2)$ To the best of our knowledge, we provide the first-ever sample
complexity result for the DR-RL problem with the Wasserstein uncertainty set
(see Table 1).
$(3)$ We demonstrate the performance of our RPVL algorithm on the Gambler’s
Problem for four different uncertainty sets. We demonstrate that the learned
RPVL algorithm policy is robust to changes in the model parameters for all
uncertainty sets. We also show our algorithm converges with regard to the
sample size. Finally, with respect to the optimality gap, we demonstrate its
dependence on the uncertainty set radius parameter.

######  Remark 1.

$(i)$ The term robust RL is now broadly used in a wide variety of
formulations, including in the data corruption setting (Lykouris et al.,,
2021) and in the adversarial learning setting (Pinto et al.,, 2017; Zhang et
al., 2020b, ; Vinitsky et al.,, 2020; Zhang et al., 2020a, ). The problem
addressed in our work is fundamentally different from all these, where we use
the classical RMDP framework (Iyengar, 2005; Nilim and El Ghaoui, 2005), and
compare with the existing works only using this framework. $(ii)$
Distributionally robust optimization is now a well established area (Duchi and
Namkoong,, 2018; Chen et al.,, 2020; Namkoong and Duchi,, 2016), whose
formulation is identical to the classical RMDP formulation. A growing number
works (Zhou et al.,, 2021; Si et al.,, 2020; Shi and Chi,, 2022) in the RL
literature hence use the terminology distributionally robust to clearly
establish this connection and also to avoid possible misinterpretation with
the other broad use of the term robust RL. For the same reasons, we use the
terminology DR-RL instead of robust RL.

##  2 Preliminaries and Problem Formulation

#### Notations:

$\Delta(\mathcal{S})$ denotes the probability simplex over any finite set
$\mathcal{S}$. For any probability vector $P\in\Delta(\mathcal{S})$ and real
vector $V\in\mathbb{R}^{\left\lvert\mathcal{S}\right\rvert}$, let $PV$ denote
the expectation $\mathbb{E}_{s\sim P}\left[V(s)\right]$. For any positive
integer $M$, $[M]$ denotes the set $\\{1,2,\ldots,M\\}$.
$\operatorname{\mathbf{1}}$ denotes the vector of all ones whose dimension is
determined from context. Let
$\mathrm{m}(\mu,\nu)\subseteq\Delta(\mathcal{S}\times\mathcal{S})$ denote the
set of all probability measures on $\mathcal{S}\times\mathcal{S}$ such that
the marginals along first and second dimensions are the distribution $\nu$ and
$\mu$ respectively. That is, for any $\omega\in\mathrm{m}(\mu,\nu)$ we have
$\nu(y)=\int_{x}\omega(x,y)dx$ and $\mu(x)=\int_{y}\omega(x,y)dy$.

A finite-horizon Markov Decision Process (MDP) can be defined as a tuple
$(\mathcal{S},\mathcal{A},(P_{h})_{h=1}^{H},(r_{h})_{h=1}^{H},{H})$, where
$\mathcal{S}$ is the state space, $\mathcal{A}$ is the action space, $H$ is
the horizon length, for any $h\in[H]$,
$r_{h}\colon\mathcal{S}\times\mathcal{A}\to[0,1]$ is a known deterministic
reward function, and
$P_{h}\colon\mathcal{S}\times\mathcal{A}\to\Delta(\mathcal{S})$ is the
transition probability function at time $h$. For any $h\in[H]$, and
$P_{h}(s^{\prime}|s,a)$ represents the probability of transitioning to state
$s^{\prime}$ when action $a$ is taken at state $s$. We use $P_{h,s,a}$ to
denote the $\left\lvert\mathcal{S}\right\rvert$-dimensional probability vector
taking value $P_{h,s,a}(s^{\prime}):=P_{h}(s^{\prime}|s,a)$ for any
$s^{\prime}\in\mathcal{S}$. We assume that
$\left\lvert\mathcal{S}\right\rvert$ and $\left\lvert\mathcal{A}\right\rvert$
are finite. When it is clear from the context, we use the shorthand $P$ for
$(P_{h})_{h=1}^{H}$.

A non-stationary Markov policy $\pi=(\pi_{h})_{h=1}^{H}$ is a sequence of
decision rules such that $\pi_{h}\colon\mathcal{S}\to\Delta(\mathcal{A})$
where $\pi_{h}(a|s)$ specifies the probability of choosing action $a$ in state
$s$ at time $h$. We consider the deterministic Markov policy class $\Pi$. That
is, for any policy $\pi\in\Pi$, $\pi_{h}(s)$ is a deterministic decision rule.
For any state $s\in\mathcal{S}$ and time $h\in[H]$, we define the value
function for policy $\pi$ as
$V_{h}^{\pi,P}(s):=\mathbb{E}_{\pi,P}\left[\sum_{t=h}^{H}r_{t}(s_{t},a_{t})\mid
s_{h}=s,\pi\right]$, where $a_{h}\sim\pi_{h}(s_{h})$ and $s_{h+1}\sim
P_{h}(\cdot|s_{h},a_{h})$. Since we are particularly interested in the value
of a policy starting from $h=1$, we denote $V^{\pi,P}:=V_{1}^{\pi,P}$. The
optimal value function $V^{*,P}_{h}$ and the optimal policy $\pi^{*,P}_{h}$ of
an MDP with the transition dynamics $P$ are defined as

$\displaystyle
V^{*,P}_{h}=\max_{\pi\in\Pi}V_{h}^{\pi,P},~{}\pi^{*,P}_{h}=\operatorname*{argmax}_{\pi\in\Pi}V_{h}^{\pi,P},~{}\forall
h\in[H].$

Since we assume that $r_{h}(s,a)\in[0,1]$ for all
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$, it is straightforward that
any value function is bounded by $V_{\max}:=H$. We denote the set of all value
functions
$\mathcal{V}=\\{V\in\mathbb{R}^{\left\lvert\mathcal{S}\right\rvert}\colon
0\leq\lVert V\rVert_{\infty}\leq H\\}$.

#### (Distributionally) Robust Markov Decision Process:

A finite-horizon distributionally robust MDP (RMDP) can be defined as a tuple
$M=(\mathcal{S},\mathcal{A},\mathcal{P},(r_{h})_{h=1}^{H},H)$. At each time
$h\in[H]$, instead of a single model, we consider the set of models within a
ball centered at the nominal model $P^{o}\equiv(P^{o}_{h})_{h=1}^{H}$.
Formally, we define the uncertainty set as
$\mathcal{P}=\bigotimes_{h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}}\mathcal{P}_{h,s,a}$
such that

$\mathcal{P}_{h,s,a}=\left\\{P\in\Delta(\mathcal{S})\colon
D(P,P^{o}_{h,s,a})\leq\rho\right\\},$ (1)

where $D(\cdot,\cdot)$ is some distance metric between two probability
measures, and $\rho$ defines the radius of the uncertainty set. We note that,
by construction, the uncertainty set $\mathcal{P}$ satisfies
$(s,a)$-rectangularity condition (Iyengar,, 2005).

#### Choices of Uncertainty Sets:

We focus on four different uncertainty sets - three corresponding to different
$f$-divergences and one corresponding to Wasserstein metric.

$(i)$ Total variation uncertainty set: Let
$\mathcal{P}^{\mathrm{TV}}=\bigotimes_{h,s,a}\mathcal{P}_{h,s,a}^{\mathrm{TV}}$,
where $\mathcal{P}_{h,s,a}^{\mathrm{TV}}$ is defined as in Eq. 1 with total
variation distance

$D_{\mathrm{TV}}(P,P^{o}_{h,s,a})=(1/2)\left\lVert
P-P^{o}_{h,s,a}\right\rVert_{1}.$ (2)

$(ii)$ Chi-square uncertainty set: Let
$\mathcal{P}^{\chi}=\bigotimes_{h,s,a}\mathcal{P}_{h,s,a}^{\chi}$, where
$\mathcal{P}_{h,s,a}^{\chi}$ is defined as in Eq. 1 with Chi-square distance

$D_{\chi}(P,P^{o}_{h,s,a})=\sum_{s^{\prime}\in\mathcal{S}}\frac{(P(s^{\prime})-P^{o}_{h,s,a}(s^{\prime}))^{2}}{P^{o}_{h,s,a}(s^{\prime})}.$
(3)

$(iii)$ Kullback-Leibler uncertainty set: Let
$\mathcal{P}^{\mathrm{KL}}=\bigotimes_{h,s,a}\mathcal{P}_{h,s,a}^{\mathrm{KL}}$,
where $\mathcal{P}^{\mathrm{KL}}_{h,s,a}$ is defined as in Eq. 1 with
Kullback-Leibler distance

$D_{\mathrm{KL}}(P,P^{o}_{h,s,a})=\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime})\mathrm{log}\left(\frac{P(s^{\prime})}{P^{o}_{h,s,a}(s^{\prime})}\right).$
(4)

$(iv)$ Wasserstein uncertainty set: Let
$\mathcal{P}^{\mathrm{W}}=\bigotimes_{h,s,a}\mathcal{P}_{h,s,a}^{\mathrm{W}}$,
where $\mathcal{P}^{\mathrm{W}}_{h,s,a}$ is defined as in Eq. 1 with
Wasserstein distance

$D_{\mathrm{W}}(P,P^{o}_{h,s,a})=\inf_{\nu\in\mathrm{m}(P,P^{o}_{h,s,a})}\int
d^{p}(x,y)d\nu(x,y),$ (5)

where the integration is over $(x,y)\in\mathcal{S}\times\mathcal{S}$,
$p\in[1,\infty)$, and $\mathrm{m}(P,P^{o}_{h,s,a})$ denotes all probability
measures on $\mathcal{S}\times\mathcal{S}$ with marginals $P$ and
$P^{o}_{h,s,a}$. In addition, we set
$B_{p}:=\max_{s,s^{\prime}}d^{p}(s,s^{\prime})$.

#### Robust Dynamic Programming:

Under the RMDP setting, for a policy $\pi\in\Pi$ the robust value function
$V^{\pi}$ is defined as (Iyengar,, 2005; Nilim and El Ghaoui,, 2005)

$\displaystyle V_{h}^{\pi}(s)$
$\displaystyle=\inf_{P\in\mathcal{P}}V_{h}^{\pi,P}(s),~{}~{}\forall(h,s)\in[H]\times\mathcal{S}.$
(6)

The interpretation is that we evaluate a policy using the worst possible model
in the uncertainty set. For consistency, we set $V_{H+1}^{\pi}=0$ for any
$\pi\in\Pi$.

The optimal robust value function and the optimal policy are defined as,
$\forall(h,s)\in[H]\times\mathcal{S}$,

$\displaystyle V^{*}_{h}(s)$
$\displaystyle=\sup_{\pi\in\Pi}V_{h}^{\pi}(s),~{}~{}\pi^{*}_{h}=\arg\sup_{\pi\in\Pi}V_{h}^{\pi}(s),$
(7)

It is known that there exists at least one optimal deterministic Markov policy
(Iyengar,, 2005, Theorem 2.2).

To simplify the notations, denote

$\displaystyle L_{\mathcal{P}_{h,s,a}}V=\inf\\{PV\colon
P\in\mathcal{P}_{h,s,a}\\}.$ (8)

The optimal robust value function satisfies the following robust Bellman
equation (Iyengar,, 2005, Theorem 2.1),

$\displaystyle V^{*}_{h}(s)$
$\displaystyle=\max_{a\in\mathcal{A}}\\{r_{h}(s,a)+L_{\mathcal{P}_{h,s,a}}V^{*}_{h+1}\\},$
(9)

for $\forall(h,s)\in[H]\times\mathcal{S}$. From the optimal robust value
function, the optimal robust policy can be calculated as

$\displaystyle\pi^{*}_{h}(s)$
$\displaystyle=\operatorname*{argmax}_{a\in\mathcal{A}}\\{r_{h}(s,a)+L_{\mathcal{P}_{h,s,a}}V^{*}_{h+1}\\},$
(10)

for $\forall(h,s)\in[H]\times\mathcal{S}$. The robust dynamic programming
method involves performing the backward iteration using Eq. 9-Eq. 10 to find
$V^{*}=(V^{*})^{H}_{h=1}$ and $\pi^{*}=(\pi^{*})^{H}_{h=1}$.

We also have the robust Bellman consistency equation (Iyengar,, 2005, Theorem
2.1) which is the extension of its counterpart in standard MDP. For any
$\pi\in\Pi$ and $\forall h\in[H]$,

$\displaystyle
V^{\pi}_{h}(s)=r_{h}(s,\pi_{h}(s))+L_{\mathcal{P}_{h,s,\pi_{h}(s)}}V^{\pi}_{h+1},~{}\forall
s\in\mathcal{S}.$ (11)

##  3 Algorithm and Sample Complexity

In order to compute $V^{*}$ and $\pi^{*}$, the robust dynamic programming
method requires the knowledge of the nominal model $P^{o}$ and the radius of
the uncertainty set $\rho$. Although $\rho$ could be a design parameter, in
most practical applications, we do not have access to the analytical form of
the nominal model $P^{o}$. So, we assume that the nominal model $P^{o}$ is
unknown. Instead, similar to the standard non-robust RL setting, we assume
that we only have access to samples from a generative model, which, given the
state-action $(s,a)$ and time $h$ as inputs, will produce samples of the next
state $s^{\prime}$ according to $P^{o}_{h,s,a}$. We propose a model-based
algorithm called Robust Phased Value Learning (RPVL) algorithm (Algorithm 1)
to learn the optimal robust policy.

RPVL algorithm is inspired by the phased value iteration in non-robust RL
(Kakade,, 2003, Algorithm 4). We first get a maximum likelihood estimate
$\widehat{P}^{o}_{h}$ of the nominal non-stationary model $P^{o}_{h}$ for each
$h\in[H]$ by following the standard approach in the literature (Kakade,, 2003,
Algorithm 4) (Azar et al.,, 2013, Algorithm 3). The term phased indicates that
we use different independent samples to estimate the nominal non-stationary
model $P^{o}_{h}$ for each step (phase) $h\in[H]$. Formally, for each
$h\in[H]$, we generate $N$ next-state samples corresponding to each state-
action pairs. Let $N_{h}(s,a,s^{\prime})$ be the count of the state
$s^{\prime}$ in the $N$ total transitions from the state-action pair $(s,a)$
in step $h\in[H]$. Now, the maximum likelihood estimate is given by
$\widehat{P}^{o}_{h,s,a}(s^{\prime})={N_{h}(s,a,s^{\prime})}/{N}$. Given
$\widehat{P}^{o}$, we can get an empirical estimate of the uncertainty set
$\mathcal{P}$ as,

$\displaystyle\widehat{\mathcal{P}}=$
$\displaystyle\bigotimes_{h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}}\widehat{\mathcal{P}}_{h,s,a},~{}\text{where},$
(12)
$\displaystyle\widehat{\mathcal{P}}_{h,s,a}=\left\\{P\in\Delta(\mathcal{S})\colon
D(P,\widehat{P}^{o}_{h,s,a})\leq\rho\right\\},$

where $D$ is one of the metrics specified in Eq. 2 \- Eq. 5.

For finding an approximately optimal robust policy, we now consider the
empirical RMDP
$\widehat{M}=(\mathcal{S},\mathcal{A},\widehat{\mathcal{P}},(r_{h})_{h=1}^{H},H)$
and perform robust dynamic programming as given in Eq. 9-Eq. 10. We formally
give our proposed approach in Algorithm 1.

Algorithm 1 Robust Phased Value Learning (RPVL)

1: Input: Uncertainty radius $\rho$

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

3: for $h=H,\ldots,1$ do

4: Compute the empirical uncertainty set $\widehat{\mathcal{P}}_{h,s,a}$ for
all $(s,a)\in(\mathcal{S},\mathcal{A})$ according to Eq. 12

5:
$\widehat{V}_{h}(s)=\max_{a}(r(s,a)+L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}),~{}\forall
s\in\mathcal{S}$

6:
$\widehat{\pi}_{h}(s)=\operatorname*{argmax}_{a}(r(s,a)+L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}),~{}\forall
s\in\mathcal{S}$

7: end for

8: Output: $\widehat{\pi}=(\widehat{\pi}_{h})_{h=1}^{H}$

###  3.1 Sample Complexity Results

Now we give the sample complexity results for all uncertainty sets based on
the metrics specified in Eq. 2 \- Eq. 5. We note that the total number of
samples needed in the RPVL algorithm is
$N_{\mathrm{total}}=N\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert
H$.

######  Theorem 1 (TV uncertainty set.).

Consider a finite-horizon RMDP with a total variation uncertainty set
$\mathcal{P}^{\mathrm{TV}}$. Fix $\delta\in(0,1)$, $\rho>0$, and
$\epsilon\in(0,8H)$. Consider the RPVL algorithm, with the total number of
samples $N_{\mathrm{total}}\geq N_{\mathrm{TV}}$, where

$N_{\mathrm{TV}}=\frac{8H^{5}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert}{\epsilon^{2}}\cdot\mathrm{log}\left(\frac{32H^{3}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert}{\epsilon\delta}\right).$

Then, $\lVert V^{*}_{1}-V^{\widehat{\pi}}_{1}\rVert_{\infty}\leq\epsilon$,
with probability at least $1-\delta$.

######  Remark 2 (Comparison with the sample complexity of the non-robust RL).

It is known from the non-robust non-stationary RL literature (Azar et al.,,
2013) that, for $\epsilon\in(0,1)$, no algorithm can learn an
$\epsilon$-optimal policy with fewer than
$\tilde{\Omega}({\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert
H^{4}}/{\epsilon^{2}})$ samples. Recently, Li et al., (2020) settled this
sample complexity question with a matching lower and upper bound
$\tilde{\Theta}({\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert
H^{4}}/{\epsilon^{2}})$ for the full range of accuracy level
$\epsilon\in(0,H)$. Our sample complexity bound given in Theorem 1 for the
distributionally robust RL is
$\tilde{\mathcal{O}}(\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert
H^{5}/\epsilon^{2})$, which matches with that of the non-robust RL bound in
$\left\lvert\mathcal{S}\right\rvert$, $\left\lvert\mathcal{A}\right\rvert$ and
also accommodates the full range of accuracy level $(0,H)$, albeit worse by a
factor $H$.

######  Theorem 2 (Chi-square uncertainty set).

Consider a finite-horizon RMDP with a chi-square uncertainty set
$\mathcal{P}^{\chi}$. Fix $\delta\in(0,1)$, $\rho>0$, and $\epsilon\in(0,8H)$.
Consider the RPVL algorithm, with the total number of samples
$N_{\mathrm{total}}\geq N_{\chi}$, where

$N_{\chi}=\frac{128C_{\rho}^{4}H^{5}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert}{(C_{\rho}-1)^{2}\epsilon^{2}}\cdot\mathrm{log}\left(\frac{2H\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert(1+\frac{8C_{\rho}H^{2}}{\epsilon(C_{\rho}-1)})}{\delta}\right),$

and where $C_{\rho}=\sqrt{1+\rho}$. Then, $\lVert
V^{*}-V^{\widehat{\pi}}\rVert_{\infty}\leq\epsilon$ with probability at least
$1-\delta$.

We note that Remark 2 holds for the above theorem also.

For KL uncertainty set, we present two results.

######  Theorem 3 (KL uncertainty set).

Consider a finite-horizon RMDP with a KL uncertainty set
$\mathcal{P}^{\mathrm{KL}}$. Fix $\delta\in(0,1)$, $\rho>0$, and
$\epsilon\in(0,H)$. Consider the RPVL algorithm, with the total number of
samples $N_{\mathrm{total}}\geq N_{\mathrm{KL}}$, where

$N_{\mathrm{KL}}=\frac{2\mathrm{exp}\left(3H/\underline{\lambda}\right)H^{5}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert}{\rho^{2}\epsilon^{2}}\cdot\mathrm{log}\left(\frac{8H\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert}{\underline{\lambda}\delta}\right),$

and $\underline{\lambda}$ is a problem dependent parameter independent of
$N_{\mathrm{KL}}$, then $\lVert
V^{*}-V^{\widehat{\pi}}\rVert_{\infty}\leq\epsilon$ with probability at least
$1-\delta$.

We note that the sample complexity of the above result for the KL uncertainty
set is worse by a term $\mathrm{exp}\left(3H/\underline{\lambda}\right)$ when
compared to Theorem 1 and Theorem 2. We note that this exponential dependence
on $H$ is observed in the prior works also (Panaganti and Kalathil,, 2022;
Zhou et al.,, 2021). We can, however, replace the exponential dependence on
horizon with a problem dependent constant as stated in the the results below.

######  Theorem 4 (KL uncertainty set).

Consider a finite-horizon RMDP with a KL uncertainty set
$\mathcal{P}^{\mathrm{KL}}$. Fix $\delta\in(0,1)$, $\rho>0$, and
$\epsilon\in(0,H)$. Consider the RPVL algorithm, with the total number of
samples $N_{\mathrm{total}}\geq N^{\prime}_{\mathrm{KL}}$, where

$N^{\prime}_{\mathrm{KL}}=\frac{2H^{5}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert}{\rho^{2}\underline{p}^{2}\epsilon^{2}}\cdot\mathrm{log}\left(\frac{2H\left\lvert\mathcal{S}\right\rvert^{2}\left\lvert\mathcal{A}\right\rvert}{\delta}\right),$

and where
$\underline{p}=\min_{s^{\prime},s,a,h:P^{o}_{h}(s^{\prime}|s,a)>0}P^{o}_{h}(s^{\prime}|s,a)$.
Then, $\lVert V^{*}-V^{\widehat{\pi}}\rVert_{\infty}\leq\epsilon$ with
probability at least $1-\delta$.

The sample complexity of the RPVL algorithm with the KL uncertainty set here
is
$\tilde{\mathcal{O}}({\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert
H^{5}}/{\rho^{2}\underline{p}^{2}\epsilon^{2}})$. We note that $\underline{p}$
is a problem dependent constant and can be arbitrarily low. So,
$1/\underline{p}^{2}$ can even be larger than
$\mathrm{exp}\left(3H/\underline{\lambda}\right)$. So, this also does not
offer a definitive answer to the question of finding a problem-independent
sample complexity bound for the KL uncertainty set, which is still an open
question. We, however, emphasize that our sample complexity bounds given in
Theorem 3 and Theorem 4 are superior compared to the existing results by a
factor of $\left\lvert\mathcal{S}\right\rvert$ (see Table 1 for details). In
addition, Remark 2 holds for both Theorem 3 and Theorem 4.

######  Theorem 5 (Wasserstein uncertainty set).

Consider a finite-horizon RMDP with a Wasserstein uncertainty set
$\mathcal{P}^{\mathrm{W}}$. Fix $\delta\in(0,1)$, $\rho>0$, and
$\epsilon\in(0,H)$. Consider the RPVL algorithm, with the total number of
samples $N_{\mathrm{total}}\geq N_{\mathrm{W}}$, where

$\displaystyle N_{\mathrm{W}}=$
$\displaystyle\frac{8H^{5}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert(B_{p}+\rho^{p})^{2}}{\rho^{2p}\epsilon^{2}}\cdot$
$\displaystyle\hskip
28.45274pt\mathrm{log}\left(\frac{16H^{2}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert(HB_{p}+(H\vee\rho^{p}))}{\rho^{p}\delta\epsilon}\right).$

Then, $\lVert V^{*}-V^{\widehat{\pi}}\rVert_{\infty}\leq\epsilon$ with
probability at least $1-\delta$.

We note that Remark 2 also holds for the Wasserstein uncertainty set case as
the sample complexity here is
$\tilde{\mathcal{O}}({(B_{p}+\rho^{p})^{2}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert
H^{5}}/{\rho^{2p}\epsilon^{2}})$.

##  4 Sample Complexity Analysis

Here we briefly explain the key analysis ideas of RPVL algorithm for obtaining
the sample complexity in Theorem 1 \- Theorem 5. The complete proofs are
provided in Section B.1 \- Section B.5.

Step 1: To bound $\lVert V^{*}_{1}-V^{\widehat{\pi}}_{1}\rVert_{\infty}$, we
split it up using the RPVL algorithm value function $\widehat{V}_{1}$ as
$\lVert V_{1}^{*}-V_{1}^{\widehat{\pi}}\rVert_{\infty}\leq\lVert
V_{1}^{*}-\widehat{V}_{1}\rVert_{\infty}+\lVert\widehat{V}_{1}-V_{1}^{\widehat{\pi}}\rVert_{\infty}.$
This split is useful since it is easier to bound these individually. We now
state a result (Yang et al.,, 2021; Panaganti and Kalathil,, 2022; Shi and
Chi,, 2022) which shows Lipschitz property of operators
$L_{\mathcal{P}_{h,s,a}}$ and $L_{\widehat{\mathcal{P}}_{h,s,a}}$ for all
$h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}$.

######  Lemma 1 (Panaganti and Kalathil,, 2022, Lemma 1).

For any $h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}$ and for any
$V_{1},V_{2}\in\mathbb{R}^{\left\lvert\mathcal{S}\right\rvert}$, we have
$\lvert
L_{\mathcal{P}_{h,s,a}}V_{1}-L_{\mathcal{P}_{h,s,a}}V_{2}\rvert\leq\lVert
V_{1}-V_{2}\rVert_{\infty}$ and $\lvert
L_{\widehat{\mathcal{P}}_{h,s,a}}V_{1}-L_{\widehat{\mathcal{P}}_{h,s,a}}V_{2}\rvert\leq\lVert
V_{1}-V_{2}\rVert_{\infty}$.

Using this and the robust Bellman equations Eq. 9 and Eq. 11 in tandem, we can
establish the recursion

$\displaystyle\lVert V_{h}^{*}-\widehat{V}_{h}\rVert_{\infty}$
$\displaystyle\leq\lVert V_{h+1}^{*}-\widehat{V}_{h+1}^{*}\rVert_{\infty}$
$\displaystyle\hskip 28.45274pt+\max_{h,s,a}\left\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert,$
$\displaystyle\lVert V_{h}^{\widehat{\pi}}-\widehat{V}_{h}\rVert_{\infty}$
$\displaystyle\leq\lVert
V_{h+1}^{\widehat{\pi}}-\widehat{V}_{h+1}\rVert_{\infty}$ $\displaystyle\hskip
28.45274pt+\max_{h,s,a}\left\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert.$

Using the consistency of robust value functions at $H+1$, i.e.,
$V_{H+1}^{\pi}=0$ for any $\pi\in\Pi$ and $\widehat{V}_{H+1}=0$, from the
recursion on $h$, we finally obtain

$\displaystyle\lVert V_{1}^{*}-$ $\displaystyle
V_{1}^{\widehat{\pi}}\rVert_{\infty}\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad$
$\displaystyle\leq 2H\max_{h,s,a}\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\rvert.$
(13)

Step 2: This is the crucial step where we develop concentration inequality
bounds for $\max_{h,s,a}\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\rvert$
in Section 4. We emphasize that this step is different and depends on the
structure of $L_{\mathcal{P}_{h,s,a}}$ and $L_{\widehat{\mathcal{P}}_{h,s,a}}$
for all uncertainty sets considered in this work.

Obtaining a bound for $\max_{h,s,a}\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\rvert$
is the most challenging part of our analysis. In the non-robust setting, this
will be equivalent to the error term $P^{o}_{h,s,a}V-\widehat{P}_{h,s,a}V$,
which is unbiased and can be easily bounded using concentration inequalities.
In the distributionally robust setting, establishing such a concentration is
not immediate because the nonlinear nature of the function $L(\cdot)$ leads to
$\mathbb{E}[L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}]\neq
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}$. We note that the previous works
(Panaganti and Kalathil, 2021b, ; Yang et al.,, 2021; Zhou et al.,, 2021;
Panaganti and Kalathil,, 2022; Shi and Chi,, 2022) also develop such
concentration inequalities for the distributionally robust setting. But all of
them rely on developing the uniform bounds over the value function space
yielding worse sample complexity with an extra
$\left\lvert\mathcal{S}\right\rvert$ factor. Instead, our strategy is to get
amenable concentration inequalities with novel covering number arguments
Propositions 2, 4, 6 and 9. In our analyses, we also make use of an important
RPVL algorithm property that $\widehat{V}_{h+1}$ is independent of
$\widehat{P}^{o}_{h,s,a}$ by construction. We emphasize that this is the first
work to use this property in the DR-RL literature. This technique is inspired
by (Kakade,, 2003, Theorem 2.5.1) in robust RL literature. Below, we outline
the analysis of the Step 2 separately for all the uncertainty sets.

#### Total Variation Uncertainty Set:

We first state a result which gives an equivalent dual form characterization
for the optimization problem $L_{\mathcal{P}_{h,s,a}}V$, where
$\mathcal{P}_{h,s,a}$ is the total variation uncertainty set
$\mathcal{P}^{\mathrm{TV}}_{h,s,a}$.

######  Proposition 1 (Panaganti et al.,, 2022, Lemma 5 ).

Consider an RMDP $M$ with the total variation uncertainty set
$\mathcal{P}^{\mathrm{TV}}$. Fix any
$h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}$. For any value function
$V\in\mathcal{V}$, the inner optimization problem
$L_{\mathcal{P}^{\mathrm{TV}}_{h,s,a}}V$ has the following equivalent form

$\displaystyle
L_{\mathcal{P}^{\mathrm{TV}}_{h,s,a}}V=-\inf_{\eta\in[0,2H/\rho]}\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot|s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]$
$\displaystyle\hskip
99.58464pt+\big{(}\eta-\inf_{s^{\prime\prime}\in\mathcal{S}}V(s^{\prime\prime})\big{)}_{+}\cdot\rho-\eta.$

######  Remark 3.

We remark that the dual form of the optimization problem
$L_{\mathcal{P}^{\mathrm{TV}}_{h,s,a}}V$ above is a single variable convex
optimization problem. This result hence is useful for both the analysis of
sample complexity bound and for the practical implementation of our RPVL
algorithm.

Now we develop our main concentration inequality result based on Proposition 1
and the RPVL algorithm property that $\widehat{V}_{h+1}$ is independent of
$\widehat{P}^{o}_{h,s,a}$ by construction.

######  Proposition 2.

Fix any $h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}$. For any
$\theta,\delta\in(0,1)$ and $\rho\in(0,1]$, we have, with probability at least
$1-\delta$, $\lvert
L_{\mathcal{P}^{\mathrm{TV}}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}^{\mathrm{TV}}_{h,s,a}}\widehat{V}_{h+1}\rvert\leq
2\theta+\sqrt{{H^{2}\mathrm{log}\left({4H}/{(\theta\delta)}\right)}/{(2N)}}.$

######  Remark 4.

We note that the $\theta$ here is a covering number argument parameter (see
Lemma 6) which is a novel development made in this work which also enabled us
to improve the sample complexity.

Finally, the proof of Theorem 1 is now complete by the application of uniform
bound over the $[H]\times\mathcal{S}\times\mathcal{A}$ space, combined with
Section 4.

#### Chi-square Uncertainty Set:

We first develop the dual reformulation version of
$L_{\mathcal{P}^{\chi}_{h,s,a}}V$ by adapting the techniques from
distributionally robust optimization (Duchi and Namkoong,, 2018).

######  Proposition 3.

Consider an RMDP $M$ with the chi-square uncertainty set $\mathcal{P}^{\chi}$.
Fix any $h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}$. For any value
function $V\in\mathcal{V}$, the inner optimization problem
$L_{\mathcal{P}^{\chi}_{h,s,a}}V$ has the following equivalent form

$\displaystyle L_{\mathcal{P}^{\chi}_{h,s,a}}V$
$\displaystyle=-\inf_{\eta\in\Xi}\left\\{C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot|s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}-\eta\right\\},$

where $\Xi=[0,C_{\rho}H/(C_{\rho}-1)]$ and $C_{\rho}=\sqrt{\rho+1}$.

Remark 3 hold here as well. Now we develop our main concentration inequality
result based on Proposition 3 and the RPVL algorithm property that
$\widehat{V}_{h+1}$ is independent of $\widehat{P}^{o}_{h,s,a}$ by
construction.

######  Proposition 4.

Fix any $h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}$. For any
$\theta,\delta\in(0,1)$ and $\rho>0$, we have, with probability at least
$1-\delta$,

$\displaystyle\lvert
L_{\mathcal{P}^{\chi}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}^{\chi}_{h,s,a}}\widehat{V}_{h+1}\rvert\leq
2\theta+$
$\displaystyle\frac{\sqrt{2}C_{\rho}^{2}H}{(C_{\rho}-1)\sqrt{N}}\big{(}\sqrt{\mathrm{log}\left(\frac{2(1+C_{\rho}H/(\theta(C_{\rho}-1)))}{\delta}\right)}+1\big{)}.$

Remark 4 holds here as well (see Lemma 10). Finally, the proof of Theorem 2 is
now complete by the application of uniform bound over the
$[H]\times\mathcal{S}\times\mathcal{A}$ space, combined with Section 4.

#### KL Uncertainty Set:

Here also, the first step is to formulate the dual version of
$L_{\mathcal{P}^{\mathrm{KL}}_{h,s,a}}V$ as given below.

######  Proposition 5.

Consider an RMDP $M$ with the chi-square uncertainty set
$\mathcal{P}^{\mathrm{KL}}$. Fix any
$h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}$. For any value function
$V\in\mathcal{V}$, the inner optimization problem
$L_{\mathcal{P}^{\mathrm{KL}}_{h,s,a}}V$ has the following equivalent form

$\displaystyle
L_{\mathcal{P}^{\mathrm{KL}}_{h,s,a}}V=-\inf_{\lambda\in[0,H/\rho]}\big{(}\lambda\rho$
$\displaystyle\hskip
42.67912pt+\lambda\mathrm{log}\left(\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot|s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]\right)\big{)}.$

Now we develop our main concentration inequality result based on Proposition 5
and the RPVL algorithm property that $\widehat{V}_{h+1}$ is independent of
$\widehat{P}^{o}_{h,s,a}$ by construction.

######  Proposition 6.

Fix any $h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}$. For any
$\theta,\delta\in(0,1)$ and $\rho>0$, we have, with probability at least
$1-\delta$, $\lvert
L_{\mathcal{P}^{\mathrm{KL}}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}^{\mathrm{KL}}_{h,s,a}}\widehat{V}_{h+1}\rvert\leq\frac{H}{\rho}\mathrm{exp}\left(H/\underline{\lambda}\right)\mathrm{exp}\left(\theta
H\right)\sqrt{{\mathrm{log}\left(4/(\theta\underline{\lambda}\delta)\right)}/{(2N)}}.$

Remark 4 holds here as well (see Lemma 14). Finally, the proof of Theorem 3 is
now complete by the application of uniform bound over the
$[H]\times\mathcal{S}\times\mathcal{A}$ space, combined with Section 4.

To prove Theorem 4, we follow similar steps above. We develop our main
concentration inequality result based on Proposition 5, which now depends on
$\underline{p}$, and the RPVL algorithm property that $\widehat{V}_{h+1}$ is
independent of $\widehat{P}^{o}_{h,s,a}$ by construction.

######  Proposition 7.

Fix any $h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}$. For any
$\delta\in(0,1)$ and $\rho>0$, we have, with probability at least $1-\delta$,
$\lvert
L_{\mathcal{P}^{\mathrm{KL}}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}^{\mathrm{KL}}_{h,s,a}}\widehat{V}_{h+1}\rvert\leq({H}/{\rho})\sqrt{{\mathrm{log}\left(2\left\lvert\mathcal{S}\right\rvert/\delta\right)}/{(2N\underline{p}^{2})}}.$

We note that the covering number argument is avoided for this result. Finally,
the proof of Theorem 4 is now complete by the application of uniform bound
over the $[H]\times\mathcal{S}\times\mathcal{A}$ space, combined with Section
4.

#### Wasserstein Uncertainty Set:

We make use of the recent results (Gao and Kleywegt,, 2022) on Wasserstein
distributionally robust optimization in order to develop the dual
reformulation of $L_{\mathcal{P}^{\mathrm{W}}_{h,s,a}}V$ as given below.

######  Proposition 8.

Consider an RMDP $M$ with the Wasserstein uncertainty set
$\mathcal{P}^{\mathrm{W}}$. Fix any
$h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}$. For any value function
$V\in\mathcal{V}$, the inner optimization problem
$L_{\mathcal{P}^{\mathrm{W}}_{h,s,a}}V$ has the following equivalent form

$\displaystyle
L_{\mathcal{P}^{\mathrm{W}}_{h,s,a}}V=-\inf_{\lambda\in[0,H/\rho^{p}]}\big{(}\lambda\rho^{p}$
$\displaystyle\hskip 28.45274pt-\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot|s,a)}[\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}]\big{)}.$

Now we develop our main concentration inequality result based on Proposition 8
and the RPVL algorithm property that $\widehat{V}_{h+1}$ is independent of
$\widehat{P}^{o}_{h,s,a}$ by construction.

######  Proposition 9.

Fix any $h,s,a\in[H]\times\mathcal{S}\times\mathcal{A}$. For any
$\theta,\delta\in(0,1)$ and $\rho>0$, we have, with probability at least
$1-\delta$,

$\displaystyle\lvert
L_{\mathcal{P}^{\mathrm{W}}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}^{\mathrm{W}}_{h,s,a}}\widehat{V}_{h+1}\rvert\leq
2\theta+$ $\displaystyle\hskip
56.9055pt\frac{H(B_{p}+\rho^{p})}{\rho^{p}}\sqrt{\frac{\mathrm{log}\left(\frac{2HB_{p}+2(H\vee\rho^{p})}{\rho^{p}\theta\delta}\right)}{2N}}.$

Remark 4 holds here as well (see Lemma 16). The proof of Theorem 5 is now
complete by the application of uniform bound over the
$[H]\times\mathcal{S}\times\mathcal{A}$ space, combined with Section 4.

##  5 Experiments

We evaluate the performance of our algorithm on the Gambler’s Problem
environment (Sutton and Barto,, 2018, Example 4.3). This environment is also
used in the prior DR-RL works (Zhou et al.,, 2021; Panaganti and Kalathil,
2021b, ; Shi and Chi,, 2022).

#### Gambler’s Problem:

In the gambler’s problem, a gambler starts with a random balance and makes
bets on a sequence of coin flips, winning the stake with heads and losing with
tails. The game allows $H$ total number of bets. The game also ends when the
gambler’s balance is either $0$ or $50$. This problem can be formulated as an
episodic finite-horizon MDP, with a state space
$\mathcal{S}=\\{0,1,\dots,50\\}$ and an action space
$\mathcal{A}=\\{0,1,\dots,\min\\{s,50-s\\}\\}$ at each state $s$. We set the
horizon as $H=50$. We denote the heads-up probability as $p_{h}$. Note that
this particular MDP has a stationary transition kernel: $p_{h}$ remains the
same for all $h\in\mathcal{H}$. The gambler receives a reward of $1$ if
$s=50$. The reward is $0$ for all other cases. We use $p_{h}^{o}=0.6$ as the
nominal model for training the algorithm unless we mention otherwise.

Figure 1: Convergence of RPVL algorithm. The left plot shows the rate of
convergence with respect to the number of sample $N$. The middle plot shows
the level of robustness of Wasserstein robust policies in testing environments
with perturbed model parameter $p_{h}$. The right plot shows how sub-
optimality gap changes with respect to the robustness parameter $\rho$. Figure
2: Robustness fairness. In each of the four plots, policies are trained with
the nominal heads-up probability $p_{h}^{o}$. Each plot shows the level of
robustness of the policies in perturbed testing environments with different
heads-up probability $p_{h}$.

We study the following characteristics of the RPVL:
$(1)$ Convergence rate of the RPVL algorithm with respect to number of samples
$N$. For each uncertainty set, we train the RPVL policy $\widehat{\pi}(N)$
with sample sizes $N=100,300,1000,3000,5000$. We demonstrate the convergence
by plotting the sub-optimality gap $\lVert V^{*}-V^{\widehat{\pi}(N)}\rVert$
against $N$. We also plot $1/\sqrt{N}$ for reference as our results show that
the sub-optimality gap is upper bounded by some function of order $1/\sqrt{N}$
with different coefficients for different uncertainty sets. Hence, we
normalize the sub-optimality gap values of each uncertainty set by dividing
maximum gap value respectively. As shown in the left plot in Fig. 1, the
robust policies of all four uncertainty sets converge to their respective
robust optimal policies when $N$ increases.
$(2)$ Effect of robustness parameter $\rho$. To show this, we consider the
Wasserstein uncertainty set. We fix $N=1000$ and train policies with
$p_{h}^{o}=0.6$ and $\rho=0.05,0.1,0.2,0.3$. In the middle plot in Fig. 1, it
can be seen that the policies trained with lower $\rho$ perform similarly to
how non-robust optimal policy performs. As $\rho$ increases, robust policies
achieve better winning rate across the perturbed testing environments with
$p_{h}\leq 0.5$. When $p_{h}=0.6$, the testing environment coincides with the
training environment, and the optimality of non-robust optimal policy
guarantees its optimal performance.
$(3)$ Dependence on $\rho$. When proving the main theorems, we find that the
upper bound of the sub-optimality gap is some function of $\rho$, i.e., of
order $1/\rho$ for TV, KL, and Wasserstein and of order
$\frac{\rho+1}{\sqrt{\rho+1}-1}$ for Chi-square. We fix $N=100$ and perform
policy evaluation on the RPVL policies trained with robustness parameter
$\rho$ in $\\{0.1,0.15,\dots,0.4\\}$. Note that these upper bounds have
different coefficients for different uncertainty sets. Hence, we normalize the
sub-optimality gap values in the same way as we do in (1). As shown in the
right plot of Fig. 1, the upper bound for sub-optimality gap is indeed of the
order we theorize in the proofs.

$(4)$ Why is robust policy robust? Our answer follows from the analysis of
Gambler’s Problem in (Zhou et al.,, 2021). When the training $p^{o}_{h}$ is
less than $0.5$, there is a family of optimal policies that achieve a winning
ratio that equals to the testing $p_{h}$, and both the non-robust dynamic
programming and RPVL algorithm find such strategy (as shown in the 1st plot in
Fig. 2). However, when $p_{h}^{o}\geq 0.5$, there is a unique non-robust
optimal policy: simply bet one dollar at each coin flip. This explains that
when the testing $p_{h}$ increases, the winning ratio increases fast for the
non-robust optimal policy, and hence it has an S-shaped curve. On the other
hand, for all the robust policies with $\rho=0.2$, the uncertainty sets
contain adversarial models with $p_{h}<0.5$. Thus, all four robust policies
still learn the conservative betting strategy (as shown in 2nd plot in Fig.
2). Next, when the training $p_{h}^{o}=0.7$, an uncertainty set with radius
$\rho=0.2$ may or may not include the adversarial model with $p_{h}<0.5$
depending on how it measures the distance between probability measures and
hence produces policies behaving differently (as shown in 3rd plot in Fig. 2).
Lastly, in 4th plot in Fig. 2, since the uncertainty sets are centered way
beyond $p_{h}=0.5$, all four robust policies converge to the strategy used by
non-robust optimal policy. This tells us an important characteristic of robust
policies: if uncertainty set is well designed so that it includes meaningful
adversarial models, then the corresponding robust policy will manifest
robustness.

######  Remark 5.

We would like to emphasize that our work is primarily a theoretical
contribution, addressing the fundamental sample complexity question of
_tabular_ (finite state and finite action) distributionally robust RL. So, the
goal of this experiments section is mainly to validate the performance our
RPVL algorithm in _tabular environment_. High dimensional continuous control
tasks, such as the MuJoCo environment used in deep RL works, are not tabular
and cannot be solved by the tabular methods, including ours. So, we do not
consider such continuous control benchmark tasks in this works. We note that
the prior works in DR-RL have also considered only tabular environments for
experiments (Zhou et al.,, 2021; Panaganti and Kalathil, 2021b, ; Shi and
Chi,, 2022).

##  6 Conclusion

In this paper, we propose the Robust Phased Value Learning algorithm. Our RPVL
algorithm approximates the robust Bellman updates in the standard robust
dynamic programming, which is a model-based robust reinforcement learning
algorithm. For four distinct uncertainty sets - total variation, chi-square,
Kullback-Leibler, and Wasserstein - we present sample complexity results of
the learned policy with regard to the optimal robust policy. In order to
highlight the theoretical features of the RPVL algorithm, we showcase its
performance on the Gambler’s Problem environment.

This work aims to provide tighter sample complexity results for the finite-
horizon robust reinforcement learning problem in the finite state space and
action space regime. In comparison to other known prior works, the analyses of
our RPVL algorithm provide an improvement in the sample complexity by a factor
of $|\mathcal{S}|$ uniformly for all uncertainty sets. We leave the
investigation for factor $H$ improvement to our future work.

##  7 Acknowledgements

The authors would like to thank Ruida Zhou for the valuable feedback at an
earlier version. This work was supported in part by the National Science
Foundation (NSF) grants NSF-CAREER-EPCN-2045783 and NSF ECCS 2038963. Any
opinions, findings, and conclusions or recommendations expressed in this
material are those of the authors and do not necessarily reflect the views of
the sponsoring agencies.

## References

  * Agarwal et al., (2020) Agarwal, A., Kakade, S., and Yang, L. F. (2020).  Model-based reinforcement learning with a generative model is minimax optimal.  In Conference on Learning Theory, pages 67–83.
  * Azar et al., (2013) Azar, M. G., Munos, R., and Kappen, H. J. (2013).  Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model.  Mach. Learn., 91(3):325–349.
  * Boucheron et al., (2013) Boucheron, S., Lugosi, G., and Massart, P. (2013).  Concentration Inequalities: A Nonasymptotic Theory of Independence.  OUP Oxford.
  * Chen et al., (2020) Chen, R., Paschalidis, I. C., et al. (2020).  Distributionally robust learning.  Foundations and Trends® in Optimization, 4(1-2):1–243.
  * Choi et al., (2009) Choi, J. J., Laibson, D., Madrian, B. C., and Metrick, A. (2009).  Reinforcement learning and savings behavior.  The Journal of finance, 64(6):2515–2534.
  * Csiszár, (1963) Csiszár, I. (1963).  Eine informationstheoretische Ungleichung und ihre Anwendung auf den Beweis der Ergodizität von Markoffschen Ketten.  Magyar Tud. Akad. Mat. Kutató Int. Közl., 8:85–108.
  * Derman et al., (2020) Derman, E., Mankowitz, D., Mann, T., and Mannor, S. (2020).  A bayesian approach to robust reinforcement learning.  In Uncertainty in Artificial Intelligence, pages 648–658.
  * Derman et al., (2018) Derman, E., Mankowitz, D. J., Mann, T. A., and Mannor, S. (2018).  Soft-robust actor-critic policy-gradient.  In AUAI press for Association for Uncertainty in Artificial Intelligence, pages 208–218.
  * Duchi and Namkoong, (2018) Duchi, J. and Namkoong, H. (2018).  Learning models with uniform performance via distributionally robust optimization.  arXiv preprint arXiv:1810.08750.
  * Gao and Kleywegt, (2022) Gao, R. and Kleywegt, A. (2022).  Distributionally robust stochastic optimization with wasserstein distance.  Mathematics of Operations Research.
  * Haskell et al., (2016) Haskell, W. B., Jain, R., and Kalathil, D. (2016).  Empirical dynamic programming.  Mathematics of Operations Research, 41(2):402–429.
  * Iyengar, (2005) Iyengar, G. N. (2005).  Robust dynamic programming.  Mathematics of Operations Research, 30(2):257–280.
  * Kakade, (2003) Kakade, S. M. (2003).  On the Sample Complexity of Reinforcement Learning.  Phd thesis, University of College London.
  * Kalathil et al., (2021) Kalathil, D., Borkar, V. S., and Jain, R. (2021).  Empirical Q-Value Iteration.  Stochastic Systems, 11(1):1–18.
  * Li et al., (2020) Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020).  Breaking the sample size barrier in model-based reinforcement learning with a generative model.  In Advances in Neural Information Processing Systems, volume 33, pages 12861–12872.
  * Lykouris et al., (2021) Lykouris, T., Simchowitz, M., Slivkins, A., and Sun, W. (2021).  Corruption-robust exploration in episodic reinforcement learning.  In Conference on Learning Theory, pages 3242–3245.
  * Mankowitz et al., (2020) Mankowitz, D. J., Levine, N., Jeong, R., Abdolmaleki, A., Springenberg, J. T., Shi, Y., Kay, J., Hester, T., Mann, T., and Riedmiller, M. (2020).  Robust reinforcement learning for continuous control with model misspecification.  In International Conference on Learning Representations.
  * Mannor et al., (2016) Mannor, S., Mebel, O., and Xu, H. (2016).  Robust mdps with k-rectangular uncertainty.  Mathematics of Operations Research, 41(4):1484–1509.
  * Moses and Sundaresan, (2011) Moses, A. K. and Sundaresan, R. (2011).  Further results on geometric properties of a family of relative entropies.  In 2011 IEEE International Symposium on Information Theory Proceedings, pages 1940–1944.
  * Namkoong and Duchi, (2016) Namkoong, H. and Duchi, J. C. (2016).  Stochastic gradient methods for distributionally robust optimization with f-divergences.  Advances in neural information processing systems, 29.
  * Nilim and El Ghaoui, (2005) Nilim, A. and El Ghaoui, L. (2005).  Robust control of markov decision processes with uncertain transition matrices.  Operations Research, 53(5):780–798.
  * (22) Panaganti, K. and Kalathil, D. (2021a).  Robust reinforcement learning using least squares policy iteration with provable performance guarantees.  In Proceedings of the 38th International Conference on Machine Learning, pages 511–520.
  * (23) Panaganti, K. and Kalathil, D. (2021b).  Sample complexity of model-based robust reinforcement learning.  In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2240–2245. IEEE.
  * Panaganti and Kalathil, (2022) Panaganti, K. and Kalathil, D. (2022).  Sample complexity of robust reinforcement learning with a generative model.  In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pages 9582–9602. PMLR.
  * Panaganti et al., (2022) Panaganti, K., Xu, Z., Kalathil, D., and Ghavamzadeh, M. (2022).  Robust reinforcement learning using offline data.  Advances in Neural Information Processing Systems.
  * Peng et al., (2018) Peng, X. B., Andrychowicz, M., Zaremba, W., and Abbeel, P. (2018).  Sim-to-real transfer of robotic control with dynamics randomization.  In 2018 IEEE international conference on robotics and automation (ICRA), pages 3803–3810. IEEE.
  * Pinto et al., (2017) Pinto, L., Davidson, J., Sukthankar, R., and Gupta, A. (2017).  Robust adversarial reinforcement learning.  In International Conference on Machine Learning, pages 2817–2826.
  * Roy et al., (2017) Roy, A., Xu, H., and Pokutta, S. (2017).  Reinforcement learning under model mismatch.  In Advances in Neural Information Processing Systems, pages 3043–3052.
  * Russel and Petrik, (2019) Russel, R. H. and Petrik, M. (2019).  Beyond confidence regions: Tight bayesian ambiguity sets for robust mdps.  Advances in Neural Information Processing Systems.
  * Schulman et al., (2013) Schulman, J., Ho, J., Lee, A. X., Awwal, I., Bradlow, H., and Abbeel, P. (2013).  Finding locally optimal, collision-free trajectories with sequential convex optimization.  In Robotics: science and systems, volume 9, pages 1–10. Citeseer.
  * Shapiro, (2017) Shapiro, A. (2017).  Distributionally robust stochastic programming.  SIAM Journal on Optimization, 27(4):2258–2275.
  * Shi and Chi, (2022) Shi, L. and Chi, Y. (2022).  Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity.  arXiv preprint arXiv:2208.05767.
  * Si et al., (2020) Si, N., Zhang, F., Zhou, Z., and Blanchet, J. (2020).  Distributionally robust policy evaluation and learning in offline contextual bandits.  In International Conference on Machine Learning, pages 8884–8894.
  * Sünderhauf et al., (2018) Sünderhauf, N., Brock, O., Scheirer, W., Hadsell, R., Fox, D., Leitner, J., Upcroft, B., Abbeel, P., Burgard, W., Milford, M., et al. (2018).  The limits and potentials of deep learning for robotics.  The International journal of robotics research, 37(4-5):405–420.
  * Sutton and Barto, (2018) Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Tobin et al., (2017) Tobin, J., Fong, R., Ray, A., Schneider, J., Zaremba, W., and Abbeel, P. (2017).  Domain randomization for transferring deep neural networks from simulation to the real world.  In 2017 IEEE/RSJ international conference on intelligent robots and systems (IROS), pages 23–30.
  * Vinitsky et al., (2020) Vinitsky, E., Du, Y., Parvate, K., Jang, K., Abbeel, P., and Bayen, A. (2020).  Robust reinforcement learning using adversarial populations.  arXiv preprint arXiv:2008.01825.
  * Wang and Zou, (2021) Wang, Y. and Zou, S. (2021).  Online robust reinforcement learning with model uncertainty.  Advances in Neural Information Processing Systems, 34:7193–7206.
  * Wiesemann et al., (2013) Wiesemann, W., Kuhn, D., and Rustem, B. (2013).  Robust Markov decision processes.  Mathematics of Operations Research, 38(1):153–183.
  * Xu and Mannor, (2010) Xu, H. and Mannor, S. (2010).  Distributionally robust Markov decision processes.  In Advances in Neural Information Processing Systems, pages 2505–2513.
  * Yang et al., (2021) Yang, W., Zhang, L., and Zhang, Z. (2021).  Towards theoretical understandings of robust markov decision processes: Sample complexity and asymptotics.  arXiv preprint arXiv:2105.03863.
  * Yu and Xu, (2015) Yu, P. and Xu, H. (2015).  Distributionally robust counterpart in Markov decision processes.  IEEE Transactions on Automatic Control, 61(9):2538–2543.
  * (43) Zhang, H., Chen, H., Boning, D. S., and Hsieh, C.-J. (2020a).  Robust reinforcement learning on state observations with learned optimal adversary.  In International Conference on Learning Representations.
  * (44) Zhang, K., Hu, B., and Basar, T. (2020b).  On the stability and convergence of robust adversarial reinforcement learning: A case study on linear quadratic systems.  Advances in Neural Information Processing Systems, 33.
  * Zhou et al., (2021) Zhou, Z., Bai, Q., Zhou, Z., Qiu, L., Blanchet, J., and Glynn, P. (2021).  Finite-sample regret bound for distributionally robust offline tabular reinforcement learning.  In International Conference on Artificial Intelligence and Statistics, pages 3331–3339.

☕ Supplementary Materials ☕

##  Appendix A Technical Results

######  Lemma 2 (Hoeffding’s inequality (see Boucheron et al.,, 2013, Theorem
2.8)).

Let $X_{1},\dots,X_{n}$ be independent random variables such that $X_{i}$
takes its values in $[a_{i},b_{i}]$ almost surely for all $i\leq n$. Let

$S=\sum_{i=1}^{n}(X_{i}-\mathbb{E}\left[X_{i}\right]).$

Then for every $t>0$,

$\mathbb{P}\left(S\geq
t\right)\leq\mathrm{exp}\left(-\frac{2t^{2}}{\sum_{i=1}^{n}(b_{i}-a_{i})^{2}}\right).$

Furthermore, if $X_{1},\dots,X_{n}$ are a sequence of independent, identically
distributed random variables with mean $\mu$. Let
$\overline{X}_{n}=\frac{1}{n}\sum_{i=1}^{n}X_{i}$. Suppose that
$X_{i}\in[a,b]$, $\forall i$. Then for all $t>0$

$\mathbb{P}\left(\left\lvert\overline{X}_{n}-\mu\right\rvert\geq t\right)\leq
2\mathrm{exp}\left(-\frac{2nt^{2}}{(b-a)^{2}}\right).$

######  Lemma 3 (Boucheron et al.,, 2013, Theorem 6.10).

Let $h\colon\mathbb{R}^{n}\to\mathbb{R}$ be convex or concave and
$L$-Lipschitz with respect to $\left\lVert\cdot\right\rVert_{2}$. Let $Z_{i}$
be independent random variables with $Z_{i}\in[a,b]$. $Z_{1:n}$ denotes the
data vector $(Z_{1},\dots,Z_{n})^{T}$. For $t\geq 0$,

$\mathbb{P}\left(\lvert h(Z_{1:n})-\mathbb{E}\left[h(Z_{1:n})\right]\rvert\geq
t\right)\leq 2\mathrm{exp}\left(-\frac{t^{2}}{2L^{2}(b-a)^{2}}\right).$

######  Lemma 4 (Duchi and Namkoong,, 2018, Lemma 7).

The map $\mathbb{R}^{n}\ni y\mapsto(\frac{1}{n}\sum_{i=1}^{n}\lvert
y_{i}\rvert^{k_{*}})^{\frac{1}{k_{*}}}$ is $n^{-\frac{1}{k_{*}\vee
2}}$-Lipschitz with respect to $\left\lVert\cdot\right\rVert_{2}$.

######  Lemma 5 (Duchi and Namkoong,, 2018, Lemma 8).

Let $k_{*}\in[1,\infty)$ and let $Y_{i}$ be an i.i.d. sequence of random
variables satisfying $\mathbb{E}\left[\lvert Y\rvert^{2k_{*}}\right]\leq
C^{k_{*}}\mathbb{E}\left[\lvert Y\rvert^{k_{*}}\right]$ for some
$C\in\mathbb{R}_{+}$. For any $k_{*}\in[1,\infty)$, we have

$\mathbb{E}\left[\left(\frac{1}{n}\sum_{i=1}^{n}\lvert
Y_{i}\rvert^{k_{*}}\right)^{\frac{1}{k_{*}}}\right]\geq\mathbb{E}\left[\left\lvert
Y\right\rvert^{k_{*}}\right]^{\frac{1}{k_{*}}}-\frac{2}{k}\sqrt{C}n^{-\frac{1}{k_{*}\vee
2}},$

where $k=k_{*}/(k_{*}-1)$ is the conjugate exponent of $k_{*}$.

###  A.1 Distributionally Robust Optimization (DRO) Results

The Total Variation, Chi-square, and Kullback-Liebler uncertainty sets are
constructed with the $f$-divergence. The $f$-divergence between the
distributions $P$ and $P^{o}$ is defined as

$D_{f}\left(P\;\|\;P^{o}\right)=\int f\left(\frac{dP}{dP^{o}}\right)dP^{o},$
(14)

where $f$ is a convex function (Csiszár,, 1963; Moses and Sundaresan,, 2011).
We obtain different divergences for different forms of the function $f$,
including some well-known divergences. For example, $f(t)=|t-1|/2$ gives Total
Variation, $f(t)=(t-1)^{2}$ gives chi-square, and
$f(t)=t\mathrm{log}\left(t\right)$ gives Kullback-Liebler.

Let $P^{o}$ be a distribution on the space $\mathcal{X}$ and let
$l:\mathcal{X}\to\mathbb{R}$ be a loss function. We have the following result
from the distributionally robust optimization literature, see e.g., (Duchi and
Namkoong,, 2018, Proposition 1) and (Shapiro,, 2017, Section 3.2).

######  Proposition 10.

Let $D_{f}$ be the $f$-divergence as defined in (14). Then,

$\displaystyle\sup_{D_{f}(P\|P^{o})\leq\rho}\mathbb{E}_{P}\left[l(X)\right]=\inf_{\lambda>0,\eta\in\mathbb{R}}~{}~{}\mathbb{E}_{P^{o}}\left[\lambda
f^{*}\left(\frac{l(X)-\eta}{\lambda}\right)\right]+\lambda\rho+\eta,$ (15)

where $f^{*}(s)=\sup_{t\geq 0}\\{st-f(t)\\}$ is the Fenchel conjugate.

Note that on the right hand side of (15), the expectation is taken only with
respect to $P^{o}$. We will use the above result to derive the dual
reformulation of the robust Bellman operator.

##  Appendix B Proof of the Theorems

###  B.1 Proof of Theorem 1

Here we provide the proofs of supporting lemmas and that of Theorem 1.

######  Lemma 6 (Covering number (TV)).

Given a value function $V\in\mathcal{V}$, let
$\mathcal{U}_{V}=\\{(\eta\cdot\operatorname{\mathbf{1}}-V)_{+}\colon\eta\in[0,H]\\}$.
Fix any $\theta\in(0,1)$. Denote

$\mathcal{N}_{V}(\theta)=\left\\{(\eta\cdot\operatorname{\mathbf{1}}-V)_{+}\colon\eta\in\left\\{\theta,2\theta,\dots,N_{\theta}\cdot\theta\right\\}\right\\},$

where $N_{\theta}=\left\lceil H/\theta\right\rceil$. Then
$\mathcal{N}_{V}(\theta)$ is a $\theta$-cover for $\mathcal{U}_{V}$ with
respect to $\left\lVert\cdot\right\rVert_{\infty}$, and its cardinality is
bounded as $\left\lvert\mathcal{N}_{V}(\theta)\right\rvert\leq 2H/\theta$.
Furthermore, for any $\nu\in\mathcal{N}_{V}(\theta)$, we have
$\left\lVert\nu\right\rVert_{\infty}\leq H$.

###### Proof.

First, $N_{\theta}=\left\lceil H/\theta\right\rceil$ is the minimal number of
subintervals of length $\theta$ needed to cover $[0,H]$. Denote
$J_{i}=[(i-1)\theta,i\theta)$ to be the $i$-th subinterval, $1\leq i\leq
N_{\theta}$. Fix some $\mu\in\mathcal{U}_{V}.$ Then
$\mu=(\eta\cdot\operatorname{\mathbf{1}}-V)_{+}$. Without loss of generality,
assume this particular $\eta\in J_{i}$. Let
$\nu=((i\theta)\cdot\operatorname{\mathbf{1}}-V)_{+}$. Now, for any
$s\in\mathcal{S}$,

$\displaystyle\left\lvert\nu(s)-\mu(s)\right\rvert$
$\displaystyle=\left\lvert(i\theta-V(s))_{+}-(\eta-V(s))_{+}\right\rvert$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left\lvert
i\theta-V(s)-\eta+V(s)\right\rvert$ $\displaystyle\leq\left\lvert
i\theta-(i-1)\theta\right\rvert=\theta,$

where $(a)$ follows from $i\theta>\eta$ and the fact that
$\max\left\\{x,0\right\\}-\max\left\\{y,0\right\\}\leq x-y$ , if $x>y$. Taking
maximum with respect to $s$ on both sides, we get
$\left\lVert\nu-\mu\right\rVert_{\infty}\leq\theta$. Since
$\nu\in\mathcal{N}_{V}(\theta)$, this suggests $\mathcal{N}_{V}(\theta)$ is a
$\theta$-cover for $\mathcal{U}_{V}$. The cardinality bound directly follows
from

$\left\lvert\mathcal{N}_{V}(\theta)\right\rvert=N_{\theta}=\left\lceil
H/\theta\right\rceil\leq H/\theta+1\leq 2H/\theta,$

where the last inequality is due to $0<\theta<1\leq H$. Now, for any
$\nu\in\mathcal{N}_{V}(\theta)$, we can establish the following

$\nu=(\eta\cdot\operatorname{\mathbf{1}}-V)_{+}\leq\left(H\operatorname{\mathbf{1}}-V\right)_{+}\leq
H,$

where the inequality is element-wise. ∎

######  Lemma 7.

Fix any $(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$. Fix any value
function $V\in\mathcal{V}$. Let $\mathcal{N}_{V}(\theta)$ be the
$\theta$-cover of
$\mathcal{U}_{V}=\\{(\eta\cdot\operatorname{\mathbf{1}}-V)_{+}\colon\eta\in[0,H]\\}$
as described in Lemma 6. We then have

$\sup_{\eta\in[0,H]}\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]-\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]\right\rvert\leq\max_{\nu\in\mathcal{N}_{V}(\theta)}\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\rvert+2\theta.$

###### Proof.

For any $\mu\in\mathcal{U}_{V}$, there exists $\nu\in\mathcal{N}_{V}(\theta)$
such that $\left\lVert\mu-\nu\right\rVert_{\infty}\leq\theta$. Now for such
particular $\mu$ and $\nu$, we have

$\displaystyle\lvert\widehat{P}^{o}_{h,s,a}\mu-P^{o}_{h,s,a}\mu\rvert$
$\displaystyle\leq\lvert\widehat{P}^{o}_{h,s,a}\mu-\widehat{P}^{o}_{h,s,a}\nu\rvert+\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\rvert+\left\lvert
P^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\mu\right\rvert$
$\displaystyle\leq\lVert\widehat{P}^{o}_{h,s,a}\rVert_{1}\left\lVert\mu-\nu\right\rVert_{\infty}+\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\rvert+\left\lVert
P^{o}_{h,s,a}\right\rVert_{1}\left\lVert\nu-\mu\right\rVert_{\infty}$
$\displaystyle\leq\max_{\nu\in\mathcal{N}_{V}(\theta)}\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\rvert+2\theta.$

Taking maximum over $\mathcal{U}_{V}$ on both sides, we get

$\sup_{\mu\in\mathcal{U}_{V}}\lvert\widehat{P}^{o}_{h,s,a}\mu-P^{o}_{h,s,a}\mu\rvert\leq\max_{\nu\in\mathcal{N}_{V}(\theta)}\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\rvert+2\theta.$

Now note that by the definition of $\mathcal{U}_{V}$, we have

$\sup_{\eta\in[0,H]}\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]-\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]\right\rvert=\sup_{\mu\in\mathcal{U}_{V}}\lvert\widehat{P}^{o}_{h,s,a}\mu-P^{o}_{h,s,a}\mu\rvert.$

The desired result directly follows. ∎

######  Lemma 8.

Fix any value function $V\in\mathcal{V}$ and fix
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$. For any
$\theta,\delta\in(0,1)$ and $\rho>0$, we have, with probability at least
$1-\delta$,

$\left\lvert
L_{\mathcal{P}_{h,s,a}}V-L_{\widehat{\mathcal{P}}_{h,s,a}}V\right\rvert\leq\sqrt{\frac{H^{2}\mathrm{log}\left(4H/\theta\delta\right)}{2N}}+2\theta,$

where $N$ is the number of samples used to approximate $P^{o}_{h,s,a}$.

###### Proof.

Fix any value function $V\in\mathcal{V}$ and
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$. From Proposition 1, we have

$\displaystyle L_{\mathcal{P}_{h,s,a}}V$
$\displaystyle=-\inf_{\eta\in[0,2H/\rho]}\left\\{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]+\Big{(}\eta-\inf_{s^{\prime\prime}\in\mathcal{S}}V(s^{\prime\prime})\Big{)}_{+}\cdot\rho-\eta\right\\},$
$\displaystyle L_{\widehat{\mathcal{P}}_{h,s,a}}V$
$\displaystyle=-\inf_{\eta\in[0,2H/\rho]}\left\\{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]+\Big{(}\eta-\inf_{s^{\prime\prime}\in\mathcal{S}}V(s^{\prime\prime})\Big{)}_{+}\cdot\rho-\eta\right\\}.$

Fix any $\rho>0$. Now it follows that

$\displaystyle\left\lvert
L_{\mathcal{P}_{h,s,a}}V-L_{\widehat{\mathcal{P}}_{h,s,a}}V\right\rvert$
$\displaystyle=\Bigg{\lvert}\inf_{\eta\in[0,2H/\rho]}\left\\{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]+\Big{(}\eta-\inf_{s^{\prime\prime}\in\mathcal{S}}V(s^{\prime\prime})\Big{)}_{+}\cdot\rho-\eta\right\\}$
$\displaystyle\quad-\inf_{\eta\in[0,2H/\rho]}\left\\{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]+\Big{(}\eta-\inf_{s^{\prime\prime}\in\mathcal{S}}V(s^{\prime\prime})\Big{)}_{+}\cdot\rho-\eta\right\\}\Bigg{\rvert}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sup_{\eta\in[0,2H/\rho]}\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]-\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]\right\rvert$
$\displaystyle\leq\max\Bigg{\\{}\sup_{\eta\in[0,H]}\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]-\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]\right\rvert,$
$\displaystyle\quad\sup_{\eta\in[H,2H/\rho]}\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]-\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]\right\rvert\Bigg{\\}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\max\Bigg{\\{}\sup_{\eta\in[0,H]}\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]-\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid s,a)}\left[(\eta-V(s^{\prime}))_{+}\right]\right\rvert,$
$\displaystyle\quad\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[V(s^{\prime})\right]-\mathbb{E}_{s^{\prime}\sim P^{o}_{h}(\cdot\mid
s,a)}\left[V(s^{\prime})\right]\right\rvert\Bigg{\\}}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\max\left\\{\max_{\nu\in\mathcal{N}_{V}(\theta)}\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\rvert+2\theta,\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[V(s^{\prime})\right]-\mathbb{E}_{s^{\prime}\sim P^{o}_{h}(\cdot\mid
s,a)}\left[V(s^{\prime})\right]\right\rvert\right\\},$ (16)

where $(a)$ follows from the fact that
$\left\lvert\inf_{x}f(x)-\inf_{x}g(x)\right\rvert\leq\sup_{x}\left\lvert
f(x)-g(x)\right\rvert$. For $(b)$, recall that $\lVert V\rVert_{\infty}\leq H$
for any $V\in\mathcal{V}$. Hence, the term $\eta-V(s^{\prime})$ is always non-
negative for $\eta\in[H,2H/\rho]$, which cancels out by linearity of the
expectation. $(c)$ follows from applying Lemma 7 to the first term. Recall
that all $\nu\in\mathcal{N}_{V}(\theta)$ is upper bounded by $\nu_{\max}:=H$.
Now we can apply Hoeffding’s inequality (Lemma 2) to the first term in Eq. 16:

$\mathbb{P}\left(\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\rvert\geq\epsilon\right)\leq
2\mathrm{exp}\left(-\frac{2N\epsilon^{2}}{\nu_{\max}^{2}}\right)=2\mathrm{exp}\left(-\frac{2N\epsilon^{2}}{H^{2}}\right),\qquad\forall\epsilon>0.$

Now choose
$\epsilon=\sqrt{\frac{H^{2}\mathrm{log}\left(2\left\lvert\mathcal{N}_{V}(\theta)\right\rvert/\delta\right)}{2N}}$
and recall that $\left\lvert\mathcal{N}_{V}(\theta)\right\rvert\leq 2H/\theta$
from Lemma 6. We have

$\displaystyle\mathbb{P}\left(\left\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\right\rvert\geq\sqrt{\frac{H^{2}\mathrm{log}\left(4H/\theta\delta\right)}{2N}}\right)$
$\displaystyle\leq\mathbb{P}\left(\left\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\right\rvert\geq\sqrt{\frac{H^{2}\mathrm{log}\left(2\left\lvert\mathcal{N}_{V}(\theta)\right\rvert/\delta\right)}{2N}}\right)$
$\displaystyle\leq\frac{\delta}{\left\lvert\mathcal{N}_{V}(\theta)\right\rvert}.$

Applying a union bound over $\mathcal{N}_{V}(\theta)$, we get

$\max_{\nu\in\mathcal{N}_{V}(\theta)}\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\rvert\leq\sqrt{\frac{H^{2}\mathrm{log}\left(4H/\theta\delta\right)}{2N}},$
(17)

with probability at least $1-\delta$. Now we can also apply Hoeffding’s
inequality to the second term in Eq. 16. Recall that any value function is
bounded by $V_{\max}:=H$. We have

$\lvert\widehat{P}^{o}_{h,s,a}V-P^{o}_{h,s,a}V\rvert\leq\sqrt{\frac{H^{2}\mathrm{log}\left(2/\delta\right)}{2N}},$
(18)

with probability at least $1-\delta$. Combining Eq. 16 \- Eq. 18 completes the
proof. ∎

######  Corollary 1.

Lemma 8 holds true for any random vector $\widehat{V}$ independent of
$\widehat{P}_{h,s,a}^{o}$.

###### Proof.

Note that Lemma 8 holds true for any fixed value function $V$. It is then true
for any realization of the random vector $\widehat{V}$. Now since
$\widehat{V}$ is independent of $\widehat{P}_{h,s,a}^{o}$, the result directly
follows from the law of total probability. ∎

###### Proof of Proposition 2.

Recall that $\widehat{V}_{h+1}$ is independent of $\widehat{P}^{o}_{h,s,a}$ by
construction. The result directly follows from Lemma 8 and Corollary 1. ∎

We now have all the ingredients to prove our main result.

###### Proof of Theorem 1.

The proof is inspired by the proof of (Kakade,, 2003, Theorem 2.5.1). Recall
that the optimal robust value function of the RMDP
$M=(\mathcal{S},\mathcal{A},\mathcal{P},(r_{h})_{h=1}^{H},[H])$ is
characterized by a set of functions $\\{V_{h}^{*}\\}_{h=1}^{H}$. Also, at each
time $h$, the RPVL algorithm outputs $\widehat{\pi}_{h}$ and
$\widehat{V}_{h}$. Now,

$\lVert V_{1}^{*}-V_{1}^{\widehat{\pi}}\rVert_{\infty}\leq\lVert
V_{1}^{*}-\widehat{V}_{1}\rVert_{\infty}+\lVert\widehat{V}_{1}-V_{1}^{\widehat{\pi}}\rVert_{\infty}.$
(19)

Step 1: bounding $V_{1}^{*}-\widehat{V}_{1}$ in Eq. 19. For any state
$s\in\mathcal{S}$ and time $h\in[H]$, we have

$\displaystyle\left\lvert V_{h}^{*}(s)-\widehat{V}_{h}(s)\right\rvert$
$\displaystyle=\left\lvert\max_{a}\left\\{r_{h}(s,a)+L_{\mathcal{P}_{h,s,a}}V^{*}_{h+1}\right\\}-\max_{a}\left\\{r_{h}(s,a)+L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\\}\right\rvert$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\max_{a}\left\lvert
L_{\mathcal{P}_{h,s,a}}V^{*}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert$
$\displaystyle\leq\max_{a}\left\lvert
L_{\mathcal{P}_{h,s,a}}V^{*}_{h+1}-L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}\right\rvert+\max_{a}\left\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\left\lVert
V^{*}_{h+1}-\widehat{V}_{h+1}\right\rVert_{\infty}+\max_{a}\left\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert$
$\displaystyle\leq\left\lVert
V^{*}_{h+1}-\widehat{V}_{h+1}\right\rVert_{\infty}+\max_{h,s,a}\left\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert,$

where $(a)$ follows from $\lvert\max_{x}f(x)-\max g(x)\rvert\leq\max_{x}\lvert
f(x)-g(x)\rvert$. $(b)$ follows from Lemma 1. Taking maximum over
$\mathcal{S}$, we get

$\left\lVert V_{h}^{*}-\widehat{V}_{h}\right\rVert_{\infty}\leq\left\lVert
V_{h+1}^{*}-\widehat{V}_{h+1}\right\rVert_{\infty}+\max_{h,s,a}\left\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert.$
(20)

Now we use the trivial fact that $V_{H+1}^{*}=0=\widehat{V}_{H+1}$ and
recursively apply Eq. 20 to get

$\left\lVert V_{1}^{*}-\widehat{V}_{1}\right\rVert_{\infty}\leq
H\max_{h,s,a}\left\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert.$
(21)

Step 2: bounding $\widehat{V}_{1}-V_{1}^{\widehat{\pi}}$ in Eq. 19. Again, fix
any $s\in\mathcal{S}$ and time $h\in[H]$. Note that $\widehat{\pi}_{h}$ is the
greedy policy with respect to $\widehat{V}_{h+1}$ as defined in the REVI
algorithm. Recall the robust Bellman (consistency) equation (Eq. 11). For any
deterministic policy $\pi=(\pi_{h})_{h\in[H]}$, we have
$V_{h}^{\pi}(s)=r_{h}(s,\pi_{h}(s))+L_{\mathcal{P}_{h,s,\pi_{h}(s)}}V_{h+1}^{\pi}$.
Now using these, we have

$\displaystyle\left\lvert
V_{h}^{\widehat{\pi}}(s)-\widehat{V}_{h}(s)\right\rvert$
$\displaystyle=\left\lvert
r_{h}(s,\widehat{\pi}_{h}(s))+L_{\mathcal{P}_{h,s,\widehat{\pi}_{h}(s)}}V^{\widehat{\pi}}_{h+1}-r_{h}(s,\widehat{\pi}_{h}(s))-L_{\widehat{\mathcal{P}}_{h,s,\widehat{\pi}_{h}(s)}}\widehat{V}_{h+1}\right\rvert$
$\displaystyle=\left\lvert
L_{\mathcal{P}_{h,s,\widehat{\pi}_{h}(s)}}V^{\widehat{\pi}}_{h+1}-L_{\mathcal{P}_{h,s,\widehat{\pi}_{h}(s)}}\widehat{V}_{h+1}+L_{\mathcal{P}_{h,s,\widehat{\pi}_{h}(s)}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,\widehat{\pi}_{h}(s)}}\widehat{V}_{h+1}\right\rvert$
$\displaystyle\leq\left\lvert
L_{\mathcal{P}_{h,s,\widehat{\pi}_{h}(s)}}V^{\widehat{\pi}}_{h+1}-L_{\mathcal{P}_{h,s,\widehat{\pi}_{h}(s)}}\widehat{V}_{h+1}\right\rvert+\max_{h,s,a}\left\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert$
$\displaystyle\leq\left\lVert
V_{h+1}^{\widehat{\pi}}-\widehat{V}_{h+1}\right\rVert_{\infty}+\max_{h,s,a}\left\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert.$

Similar to the step 1, after taking maximum over $\mathcal{S}$ and unrolling
the recursion, we get

$\left\lVert V_{1}^{\widehat{\pi}}-\widehat{V}_{1}\right\rVert_{\infty}\leq
H\max_{h,s,a}\left\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert.$
(22)

Step 3: concentration on $\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\rvert$.
Applying Proposition 2 and taking a union bound over
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$, we get

$\max_{h,s,a}\left\lvert
L_{\mathcal{P}_{h,s,a}}\widehat{V}_{h+1}-L_{\widehat{\mathcal{P}}_{h,s,a}}\widehat{V}_{h+1}\right\rvert\leq\sqrt{\frac{H^{2}\mathrm{log}\left(4H^{2}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert/\theta\delta\right)}{2N}}+2\theta,$
(23)

with probability at least $1-\delta$. Now, plugging Eq. 21-Eq. 23 into Eq. 19,
we get

$\left\lVert V_{1}^{*}-V_{1}^{\widehat{\pi}}\right\rVert_{\infty}\leq
2H\sqrt{\frac{H^{2}\mathrm{log}\left(4H^{2}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert/\theta\delta\right)}{2N}}+4H\theta,$
(24)

with probability at least $1-\delta$. We can choose $\theta=\epsilon/(8H)$.
Note that since $\epsilon\in(0,8H)$, this particular $\theta$ is in $(0,1)$.
Now, if we choose

$N\geq\frac{8H^{4}\mathrm{log}\left(32H^{3}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert/\epsilon\delta\right)}{\epsilon^{2}},$

we get $\lVert V_{1}^{*}-V_{1}^{\widehat{\pi}}\rVert_{\infty}\leq\epsilon$
with probability at least $1-\delta$. ∎

###  B.2 Proof of Theorem 2

Here we provide the proofs of supporting lemmas and that of Theorem 2.

######  Lemma 9.

Let $D_{f}$ be defined as in Eq. 14 with the convex function $f(t)=(t-1)^{2}$
corresponding to the Chi-square uncertainty set. Then

$\inf_{D_{f}\left(P\;\|\;P^{o}\right)\leq\rho}\mathbb{E}_{P}\left[l(X)\right]=-\inf_{\eta\in\mathbb{R}}\left\\{\sqrt{\rho+1}\sqrt{\mathbb{E}_{P^{o}}\left[(\eta-l(X))^{2}\right]}-\eta\right\\}.$

###### Proof.

We first get the Fenchel conjugate of Chi-square divergence. We have

$f^{*}(s)=\sup_{t\geq 0}(st-(t-1)^{2})=\sup_{t\geq 0}(-t^{2}+(s+2)t-1).$

It is easy to see that for $s\leq-2$, we have $f^{*}(s)=-1$. Whenever $s>-2$,
from Calculus, the optimal $t$ for this optimization problem is $(s+2)/2$.
Hence we get $f^{*}(s)=\max\left\\{s^{2}/4+s,-1\right\\}$. Now, from
Proposition 10 we get,

$\displaystyle\sup_{D_{f}(P\|P^{o})\leq\rho}\mathbb{E}_{P}\left[l(X)\right]$
$\displaystyle=\inf_{\lambda>0,\eta\in\mathbb{R}}\\{\mathbb{E}_{P^{o}}[\lambda
f^{*}(\frac{l(X)-\eta}{\lambda})]+\lambda\rho+\eta\\}$
$\displaystyle=\inf_{\lambda,\eta:\lambda>0,\eta\in\mathbb{R}}\\{\lambda\mathbb{E}_{P^{o}}[\max\\{\frac{(l(X)-\eta)^{2}}{4\lambda^{2}}+\frac{l(X)-\eta}{\lambda},~{}-1\\}]+\lambda\rho+\eta\\}$
$\displaystyle=\inf_{\lambda,\eta:\lambda>0,\eta\in\mathbb{R}}\\{\mathbb{E}_{P^{o}}[\max\\{\frac{(l(X)-\eta)^{2}}{4\lambda}+l(X)-\eta,-\lambda\\}]+\lambda\rho+\eta\\}$
$\displaystyle=\inf_{\lambda,\eta:\lambda>0,\eta\in\mathbb{R}}\\{\mathbb{E}_{P^{o}}[(\frac{(l(X)-\eta)^{2}}{4\lambda}+l(X)-\eta+\lambda)_{+}-\lambda]+\lambda\rho+\eta\\}$
$\displaystyle=\inf_{\lambda,\eta:\lambda>0,\eta\in\mathbb{R}}\\{\frac{1}{4\lambda}\mathbb{E}_{P^{o}}[(l(X)-\eta+2\lambda)^{2}]+\lambda(\rho-1)+\eta\\}$
$\displaystyle=\inf_{\lambda,\eta^{\prime}:\lambda>0,\eta^{\prime}\in\mathbb{R}}\\{\frac{1}{4\lambda}\mathbb{E}_{P^{o}}[(l(X)-\eta^{\prime})^{2}]+\lambda(\rho+1)+\eta^{\prime}\\},$

where the fourth equality follows form the fact that
$\max\\{x,y\\}=(x-y)_{+}+y$ for any $x,y\in\mathbb{R}$, and the last equality
follows by making the substitution $\eta^{\prime}=\eta-2\lambda.$ Taking the
optimal value of $\lambda$, i.e.,
$\lambda=\sqrt{\mathbb{E}_{P^{o}}[(l(X)-\eta^{\prime})^{2}]}/(2\sqrt{\rho+1})$,
we get

$\displaystyle\sup_{D_{f}(P\|P^{o})\leq\rho}\mathbb{E}_{P}[l(X)]=\inf_{\eta^{\prime}\in\mathbb{R}}\\{\sqrt{\rho+1}\sqrt{\mathbb{E}_{P^{o}}[(l(X)-\eta^{\prime})^{2}]}+\eta^{\prime}\\}.$

Now,

$\displaystyle\inf_{D_{f}(P\|P^{o})\leq\rho}\mathbb{E}_{P}[l(X)]$
$\displaystyle=-\sup_{D_{f}(P\|P^{o})\leq\rho}\mathbb{E}_{P}[-l(X)]$
$\displaystyle=-\inf_{\eta^{\prime}\in\mathbb{R}}\\{\sqrt{\rho+1}\sqrt{\mathbb{E}_{P^{o}}[(-l(X)-\eta^{\prime})^{2}]}+\eta^{\prime}\\}$
$\displaystyle=-\inf_{\eta\in\mathbb{R}}\\{\sqrt{\rho+1}\sqrt{\mathbb{E}_{P^{o}}[(l(X)-\eta)^{2}]}-\eta\\},$

which completes the proof. ∎

###### Proof of Proposition 3.

Applying Lemma 9 to value function, we get

$L_{\mathcal{P}_{h,s,a}}V=-\inf_{\eta\in\mathbb{R}}\left\\{\sqrt{\rho+1}\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}-\eta\right\\}.$ (25)

Now let $h(\eta)=\sqrt{\rho+1}\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}-\eta$. $h$ is
convex in dual variable $\eta$. Now observe that $h(\eta)\geq 0$ when
$\eta\leq 0$ and $h(\frac{\sqrt{\rho+1}}{\sqrt{\rho+1}-1}H)\geq 0$. Hence it
is sufficient to consider $\eta\in[0,\frac{\sqrt{\rho+1}}{\sqrt{\rho+1}-1}H]$.
Setting $C_{\rho}=\sqrt{\rho+1}$, we get the desired result. ∎

######  Lemma 10.

Fix any $(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$. Let
$\mathcal{N}_{\rho}(\theta)$ be the $\theta$-cover of the interval
$[0,C_{\rho}H/(C_{\rho}-1)]$, where $C_{\rho}=\sqrt{1+\rho}$. For any value
function $V\in\mathcal{V}$ and $\eta\in[0,C_{\rho}H/(C_{\rho}-1)]$, we have

$\displaystyle\sup_{\eta\in[0,C_{\rho}H/(C_{\rho}-1)]}$
$\displaystyle\bigg{\lvert}\sqrt{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}-\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}\bigg{\rvert}$
$\displaystyle\leq\max_{\nu\in\mathcal{N}_{\rho}(\theta)}\left\lvert\sqrt{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}-\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}\right\rvert+2\theta.$

Furthermore, we have
$\left\lvert\mathcal{N}_{\rho}(\theta)\right\rvert\leq\frac{C_{\rho}H}{(C_{\rho}-1)\theta}+1$.

###### Proof.

Fix any $\eta\in[0,C_{\rho}H/(C_{\rho}-1)]$. Then there exists a
$\nu\in\mathcal{N}_{\rho}(\theta)$ such that $\lvert\eta-\nu\rvert\leq\theta$.
Let $X$ be a random variable that takes values in
$\\{V(1),\dots,V(\left\lvert\mathcal{S}\right\rvert)\\}$ with probability
$\mathbb{P}\left(X=V(s^{\prime})\right)=P^{o}_{h}(s^{\prime}\mid s,a)$, for
all $s^{\prime}\in\mathcal{S}$. We use $\lVert\cdot\rVert_{p,P}$ to denote the
$L^{p}$ norm in the measure space on $\mathcal{S}$ possessing a measure
determined by the probability mass function $P$. It leads to the $L^{p}$ norm
of a random variable: $\lVert X\rVert_{p,P}=(\mathbb{E}_{P}\lvert
X\rvert^{p})^{1/p}$. Now using these definitions, for the particular $\eta$
and $\nu$ we picked, we have

$\displaystyle\bigg{\lvert}$
$\displaystyle\sqrt{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}-\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}\bigg{\rvert}=\left\lvert\left\lVert\eta-X\right\rVert_{2,\widehat{P}^{o}_{h,s,a}}-\left\lVert\eta-X\right\rVert_{2,P^{o}_{h,s,a}}\right\rvert$
$\displaystyle\leq\left\lvert\left\lVert\eta-X\right\rVert_{2,\widehat{P}^{o}_{h,s,a}}-\left\lVert\nu-X\right\rVert_{2,\widehat{P}^{o}_{h,s,a}}\right\rvert+\left\lvert\left\lVert\nu-X\right\rVert_{2,\widehat{P}^{o}_{h,s,a}}-\left\lVert\nu-X\right\rVert_{2,P^{o}_{h,s,a}}\right\rvert+\left\lvert\left\lVert\nu-X\right\rVert_{2,P^{o}_{h,s,a}}-\left\lVert\eta-X\right\rVert_{2,P^{o}_{h,s,a}}\right\rvert$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left\lVert\eta-X-\nu+X\right\rVert_{2,\widehat{P}^{o}_{h,s,a}}+\left\lvert\left\lVert\nu-X\right\rVert_{2,\widehat{P}^{o}_{h,s,a}}-\left\lVert\nu-X\right\rVert_{2,P^{o}_{h,s,a}}\right\rvert+\left\lVert\nu-X-\eta+X\right\rVert_{2,P^{o}_{h,s,a}}$
$\displaystyle\leq\max_{\nu\in\mathcal{N}_{\rho}(\theta)}\left\lvert\left\lVert\nu-X\right\rVert_{2,\widehat{P}^{o}_{h,s,a}}-\left\lVert\nu-X\right\rVert_{2,P^{o}_{h,s,a}}\right\rvert+2\left\lvert\nu-\eta\right\rvert$
$\displaystyle\leq\max_{\nu\in\mathcal{N}_{\rho}(\theta)}\left\lvert\sqrt{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}-\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}\right\rvert+2\theta,$

where $(a)$ is due to reverse triangle inequality. Taking supremum over
$\eta\in[0,C_{\rho}H/(C_{\rho}-1)]$ on the both sides of the above, we have
the desired result. For the cardinality, it is trivial that

$\left\lvert\mathcal{N}_{\rho}(\theta)\right\rvert\leq\left\lceil\frac{C_{\rho}H}{(C_{\rho}-1)\theta}\right\rceil\leq\frac{C_{\rho}H}{(C_{\rho}-1)\theta}+1.$
(26)

∎

######  Lemma 11.

Fix any value function $V\in\mathcal{V}$ and fix
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$. We have the following
inequality with probability at least $1-\delta$:

$\left\lvert
C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}-C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}\right\rvert\leq\frac{\sqrt{2}C_{\rho}^{2}H}{(C_{\rho}-1)\sqrt{N}}\left(\sqrt{\mathrm{log}\left(2/\delta\right)}+1\right),$

where $C_{\rho}=\sqrt{1+\rho}$.

###### Proof.

Fix any $(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$,
$\eta\in[0,C_{\rho}H/(C_{\rho}-1)]$, and $V\in\mathcal{V}$ independent of
$P^{o}_{h,s,a}$. Consider a sequence of i.i.d. samples $\\{X_{i}\\}_{i=1}^{N}$
generated from $P^{o}_{h,s,a}$. Recall that we use the outcomes of this
sequence of random variables to construct $\widehat{P}^{o}_{h,s,a}$. Besides,
we denote $Y_{i}=(\eta-V(X_{i}))$. Note that $Y$ is upper bounded by
$Y_{\max}:=C_{\rho}H/(C_{\rho}-1)$. To ease notation, denote
$g(\eta;P)=C_{\rho}(\mathbb{E}_{P}\left[Y^{2}\right])^{1/2}$.

Lemma 4 implies that
$g(\eta;\widehat{P}^{o}_{h,s,a})=C_{\rho}(\frac{1}{N}\sum_{i=1}^{N}Y_{i}^{2})^{1/2}$
is a $\frac{C_{\rho}}{\sqrt{N}}$-Lipschitz function of the vector
$(Y_{1},\dots,Y_{N})^{T}$ with respect to $\left\lVert\cdot\right\rVert_{2}$.
Applying Lemma 3, we get

$\left\lvert
g(\eta;\widehat{P}^{o}_{h,s,a})-\mathbb{E}_{P^{o}_{h,s,a}}[g(\eta;\widehat{P}^{o}_{h,s,a})]\right\rvert\leq\frac{\sqrt{2}C_{\rho}^{2}H}{(C_{\rho}-1)\sqrt{N}}\sqrt{\mathrm{log}\left(2/\delta\right)},$
(27)

with probability at least $1-\delta$. It remains to see that
$\mathbb{E}_{P^{o}_{h,s,a}}[g(\eta;\widehat{P}^{o}_{h,s,a})]$ and
$g(\eta;P^{o}_{h,s,a})$ are close. Note that the random variable $Y$ satisfies
$\mathbb{E}[\left\lvert Y\right\rvert^{4}]\leq
Y_{\max}^{2}\mathbb{E}[\left\lvert Y\right\rvert^{2}]$. Since
$\mathbb{E}_{P^{o}_{h,s,a}}[(\frac{1}{N}\sum_{i=1}^{N}Y_{i}^{2})^{1/2}]\leq(\mathbb{E}\left[Y^{2}\right])^{1/2}$
by Jensen’s inequality, Lemma 5 implies that

$\left\lvert\mathbb{E}_{P^{o}_{h,s,a}}[g(\eta;\widehat{P}^{o}_{h,s,a})]-g(\eta;P^{o}_{h,s,a})\right\rvert\leq\frac{\sqrt{Y_{\max}}}{\sqrt{N}}=\sqrt{\frac{C_{\rho}H}{C_{\rho}-1}}\frac{1}{\sqrt{N}}\leq\frac{C_{\rho}^{2}\sqrt{H}}{(C_{\rho}-1)\sqrt{N}}.$
(28)

Combining Eq. 27 and Eq. 28, we get

$\left\lvert
C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}-C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}\right\rvert\leq\frac{\sqrt{2}C_{\rho}^{2}H}{(C_{\rho}-1)\sqrt{N}}\left(\sqrt{\mathrm{log}\left(2/\delta\right)}+1\right),$

with probability at least $1-\delta$. ∎

######  Lemma 12.

Fix any value function $V\in\mathcal{V}$ and
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$. For any
$\theta,\delta\in(0,1)$ and $\rho>0$, we have, with probability at least
$1-\delta$,

$\left\lvert
L_{\mathcal{P}_{h,s,a}}V-L_{\widehat{\mathcal{P}}_{h,s,a}}V\right\rvert\leq\frac{\sqrt{2}C_{\rho}^{2}H}{(C_{\rho}-1)\sqrt{N}}\left(\sqrt{\mathrm{log}\left(\frac{2(1+C_{\rho}H/(\theta(C_{\rho}-1))}{\delta}\right)}+1\right)+2\theta,$

where $C_{\rho}=\sqrt{1+\rho}$ and $N$ is the number of samples used to
approximate $P^{o}_{h,s,a}$.

###### Proof.

From Proposition 3, we get

$\displaystyle L_{\mathcal{P}_{h,s,a}}V$
$\displaystyle=-\inf_{\eta\in[0,C_{\rho}H/(C_{\rho}-1)]}\left\\{C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}-\eta\right\\},$ $\displaystyle
L_{\widehat{\mathcal{P}}_{h,s,a}}V$
$\displaystyle=-\inf_{\eta\in[0,C_{\rho}H/(C_{\rho}-1)]}\left\\{C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}-\eta\right\\}.$

Now for any $\rho>0$, we have

$\displaystyle\left\lvert
L_{\mathcal{P}_{h,s,a}}V-L_{\widehat{\mathcal{P}}_{h,s,a}}V\right\rvert$
$\displaystyle=\bigg{\lvert}\inf_{\eta\in[0,C_{\rho}H/(C_{\rho}-1)]}\left\\{C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}-\eta\right\\}$
$\displaystyle\quad-\inf_{\eta\in[0,C_{\rho}H/(C_{\rho}-1)]}\left\\{C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}-\eta\right\\}\bigg{\rvert}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sup_{\eta\in[0,C_{\rho}H/(C_{\rho}-1)]}\left\lvert
C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}-C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid s,a)}\left[(\eta-V(s^{\prime}))^{2}\right]}\right\rvert$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\max_{\nu\in\mathcal{N}_{\rho}(\theta)}\left\lvert
C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}-C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}\right\rvert+2\theta,$ (29)

where $(a)$ is from $\lvert\inf_{x}f(x)-\inf_{x}g(x)\rvert\leq\sup_{x}\lvert
f(x)-g(x)\rvert$. $(b)$ is due to Lemma 10.

Now using Lemma 11 and applying a union bound over
$\nu\in\mathcal{N}_{\rho}(\theta)$, we get the following inequalities with
probability at least $1-\delta$

$\displaystyle\max_{\nu\in\mathcal{N}_{\rho}(\theta)}\bigg{\lvert}C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}$ $\displaystyle-
C_{\rho}\sqrt{\mathbb{E}_{s^{\prime}\sim P^{o}_{h}(\cdot\mid
s,a)}\left[(\nu-V(s^{\prime}))^{2}\right]}\bigg{\rvert}$
$\displaystyle\leq\frac{\sqrt{2}C_{\rho}^{2}H}{(C_{\rho}-1)\sqrt{N}}\left(\sqrt{\mathrm{log}\left(\frac{2\left\lvert\mathcal{N}_{\rho}(\theta)\right\rvert}{\delta}\right)}+1\right)$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{\sqrt{2}C_{\rho}^{2}H}{(C_{\rho}-1)\sqrt{N}}\left(\sqrt{\mathrm{log}\left(\frac{2(1+C_{\rho}H/(\theta(C_{\rho}-1))}{\delta}\right)}+1\right),$
(30)

where $(a)$ follows from Eq. 26. Combining Section B.2 and Section B.2, we get
the desired inequality. ∎

###### Proof of Proposition 4.

Recall that $\widehat{V}_{h+1}$ is independent of $\widehat{P}^{o}_{h,s,a}$ by
construction. Similar to Corollary 1 and Proposition 2, the result directly
follows from Lemma 12 and the law of total probability. ∎

We now have all the ingredients to prove our main result.

###### Proof of Theorem 2.

The proof is almost identical to that of Theorem 1. By applying Proposition 4
and taking a union bound over
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$, we have

$\left\lVert
V_{1}^{*}-V_{1}^{\widehat{\pi}}\right\rVert_{\infty}\leq\frac{2\sqrt{2}C_{\rho}^{2}H^{2}}{(C_{\rho}-1)\sqrt{N}}\left(\sqrt{\mathrm{log}\left(\frac{2H\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert(1+\frac{C_{\rho}H}{\theta(C_{\rho}-1)})}{\delta}\right)}+1\right)+4H\theta,$

with probability at least $1-\delta$. We can choose $\theta=\epsilon/(8H)$.
Note that since $\epsilon\in(0,8H)$, this particular $\theta$ is in $(0,1)$.
Now, if we choose

$N\geq\frac{32C_{\rho}^{4}H^{4}}{(C_{\rho}-1)^{2}}\frac{1}{\epsilon^{2}}\left(\sqrt{\mathrm{log}\left(\frac{2H\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert(1+\frac{8C_{\rho}H^{2}}{\epsilon(C_{\rho}-1)})}{\delta}\right)}+1\right)^{2}$

we get $\lVert V_{1}^{*}-V_{1}^{\widehat{\pi}^{*}}\rVert_{\infty}\leq\epsilon$
with probability at least $1-\delta$. To simplify the above, consider the
elementary inequality $(a+b)^{2}\leq 2(a^{2}+b^{2})$, for any non-negative
real number $a$ and $b$. With this, we get our final sample complexity result:

$H\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert
N\geq\frac{64C_{\rho}^{4}}{(C_{\rho}-1)^{2}}\frac{H^{5}\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert}{\epsilon^{2}}\left(\mathrm{log}\left(\frac{2H\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert(1+\frac{8C_{\rho}H^{2}}{\epsilon(C_{\rho}-1)})}{\delta}\right)+1\right).$

∎

###  B.3 Proof of Theorem 3

Here we provide the proofs of supporting lemmas and that of Theorem 3.

######  Lemma 13.

Let $D_{f}$ be defined as in Eq. 14 with the convex function
$f(t)=t\mathrm{log}\left(t\right)$ corresponding to the KL uncertainty set
$\mathcal{P}^{KL}$. Then

$\inf_{D_{f}\left(P\;\|\;P^{o}\right)\leq\rho}\mathbb{E}_{P}\left[l(X)\right]=-\inf_{\lambda\geq
0}\left\\{\lambda\rho+\lambda\mathrm{log}\left(\mathbb{E}_{P^{o}}\left[\mathrm{exp}\left(\frac{-l(X)}{\lambda}\right)\right]\right)\right\\}.$

###### Proof.

We first derive the Fenchel conjugate of $f$. We have $f^{*}(s)=\sup_{t\geq
0}\\{st-t\mathrm{log}\left(t\right)\\}$. From calculus, the optimal $t$ for
this optimization problem is $\mathrm{exp}\left(s-1\right)$. Plugging this
back into the conjugate, we get $f^{*}(s)=\mathrm{exp}\left(s-1\right)$. From
Proposition 10, we get

$\displaystyle\sup_{D_{f}(P\|P^{o})\leq\rho}\mathbb{E}_{P}\left[l(X)\right]$
$\displaystyle=\inf_{\lambda>0,\eta\in\mathbb{R}}\mathbb{E}_{P^{o}}\left[\lambda
f^{*}\left(\frac{l(X)-\eta}{\lambda}\right)\right]+\lambda\rho+\eta$
$\displaystyle=\inf_{\lambda\geq
0,\eta\in\mathbb{R}}\left\\{\mathbb{E}_{P^{o}}\left[\lambda\mathrm{exp}\left(\frac{l(X)-\eta}{\lambda}-1\right)\right]+\lambda\rho+\eta\right\\}$
$\displaystyle=\inf_{\lambda\geq
0}\left\\{\lambda\rho+\lambda\mathrm{log}\left(\mathbb{E}_{P^{o}}\left[\mathrm{exp}\left(\frac{l(X)}{\lambda}\right)\right]\right)\right\\},$

where the last equality is from infimizing over $\eta$. That is, the optimal
$\eta=\lambda\mathrm{log}\left(\mathbb{E}_{P^{o}}\left[\mathrm{exp}\left(\frac{l(X)}{\lambda}-1\right)\right]\right)$.
Now this implies that

$\displaystyle\inf_{D_{f}(P\|P^{o})\leq\rho}\mathbb{E}_{P}\left[l(X)\right]$
$\displaystyle=-\sup_{D_{f}(P\|P^{o})\leq\rho}\mathbb{E}_{P}\left[-l(X)\right]$
$\displaystyle=-\inf_{\lambda\geq
0}\left\\{\lambda\rho+\lambda\mathrm{log}\left(\mathbb{E}_{P^{o}}\left[\mathrm{exp}\left(\frac{-l(X)}{\lambda}\right)\right]\right)\right\\}.$

This completes the proof. ∎

###### Proof of Proposition 5.

Applying Lemma 13 to value function, we get

$L_{\mathcal{P}_{h,s,a}}V=-\inf_{\lambda\geq
0}\left\\{\lambda\rho+\lambda\mathrm{log}\left(\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]\right)\right\\}.$

We denote
$h(\lambda)=\lambda\rho+\lambda\mathrm{log}\left(\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]\right).$
Note that $h$ is convex in the dual variable $\lambda$. Now fix any
$\lambda\geq H/\rho$. We have

$\lambda\rho+\lambda\mathrm{log}\left(\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]\right)\geq\lambda\rho+\lambda\mathrm{log}\left({\mathrm{exp}\left(\frac{-H}{\lambda}\right)}\right)\geq
0.$

In addition, observe that $h$ is monotonically increasing in $\lambda$ when
$\lambda\geq H/\rho$. Thus, it is sufficient to optimize $\lambda$ in
$[0,H/\rho]$. This implies that

$L_{\mathcal{P}_{h,s,a}}V=-\inf_{\lambda\in[0,H/\rho]}\left\\{\lambda\rho+\lambda\mathrm{log}\left(\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]\right)\right\\}.$

∎

######  Lemma 14.

Fix any value function $V\in\mathcal{V}$ and
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$. For any
$\theta,\delta\in(0,1)$ and $\rho>0$, we have, with probability at least
$1-\delta$,

$\left\lvert
L_{\mathcal{P}_{h,s,a}}V-L_{\widehat{\mathcal{P}}_{h,s,a}}V\right\rvert\leq\frac{H}{\rho}\mathrm{exp}\left(H/\underline{\lambda}\right)\mathrm{exp}\left(\theta
H\right)\sqrt{\frac{\mathrm{log}\left(4/(\theta\underline{\lambda}\delta)\right)}{2N}},$

where $N$ is the number of samples used to approximate $P^{o}_{h,s,a}$, and
$\underline{\lambda}$ is a problem dependent parameter but independent of $N$.

###### Proof.

Fix any value function $V\in\mathcal{V}$,
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$, and any $\rho>0$. From
Proposition 5, we have

$\displaystyle L_{\mathcal{P}_{h,s,a}}V$
$\displaystyle=-\inf_{\lambda\in[0,H/\rho]}\left\\{\lambda\rho+\lambda\mathrm{log}\left(\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]\right)\right\\},$
$\displaystyle L_{\widehat{\mathcal{P}}_{h,s,a}}V$
$\displaystyle=-\inf_{\lambda\in[0,H/\rho]}\left\\{\lambda\rho+\lambda\mathrm{log}\left(\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]\right)\right\\}.$

Suppose the optimization problem $L_{\mathcal{P}_{h,s,a}}V$ above is achieved
at $\lambda^{*}=0$. It can be shown that when $\lambda^{*}=0$,
$L_{\mathcal{P}_{h,s,a}}V=L_{\widehat{\mathcal{P}}_{h,s,a}}V=V_{\min}$ with
high probability (and hence $\lvert
L_{\mathcal{P}_{h,s,a}}V-L_{\widehat{\mathcal{P}}_{h,s,a}}V\rvert=0$), where
$V_{\min}=\min_{s\in\mathcal{S}}V(s)$, whenever $N$ is greater than some
problem dependent constant but independent of the optimality gap $\epsilon$
defined in Theorem 3. (Nilim and El Ghaoui,, 2005, Appendix C) provided a
proof of this trivial case in terms of robust optimal control. (Panaganti and
Kalathil,, 2022, Lemma 13) adapted the proof to RMDP and provided a detailed
analysis. We omit the proof here and only discuss the case where
$\lambda^{*}\in(0,H/\rho]$.

Now assume the optimal $\lambda^{*}$ is achieved in $(0,H/\rho]$. Define
$\underline{\lambda}=\lambda^{*}/2$ if $\lambda^{*}\in(0,1)$ and
$\underline{\lambda}=1/2$ if $\lambda\geq 1$. We define $\underline{\lambda}$
this way because restricting $\underline{\lambda}\in(0,1)$ can later give us
cleaner expression without compromising its function. Let the optimization
problem $L_{\widehat{\mathcal{P}}_{h,s,a}}V$ be achieved at
$\hat{\lambda}^{*}$. Again from (Zhou et al.,, 2021, Lemma 4) (Panaganti and
Kalathil,, 2022, Lemma 13), it holds that
$\hat{\lambda}^{*}\in(\underline{\lambda},H/\rho]$ whenever $N$ is greater
than some problem dependent constant but independent of the optimality gap
$\epsilon$ defined in Theorem 3, and hence omit this constant for $N$ further
in our analysis. Now it follows that

$\displaystyle\left\lvert
L_{\mathcal{P}_{h,s,a}}V-L_{\widehat{\mathcal{P}}_{h,s,a}}V\right\rvert$
$\displaystyle=\Bigg{\lvert}\inf_{\lambda\in(\underline{\lambda},H/\rho]}\left\\{\lambda\rho+\lambda\mathrm{log}\left(\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]\right)\right\\}$
$\displaystyle\quad-\inf_{\lambda\in(\underline{\lambda},H/\rho]}\left\\{\lambda\rho+\lambda\mathrm{log}\left(\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]\right)\right\\}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sup_{\lambda\in(\underline{\lambda},H/\rho]}\left\lvert\lambda\mathrm{log}\left(\frac{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]}{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]}\right)\right\rvert$
$\displaystyle\leq\frac{H}{\rho}\sup_{\lambda\in(\underline{\lambda},H/\rho]}\left\lvert\mathrm{log}\left(\frac{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]-\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]}{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]}+1\right)\right\rvert$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\frac{H}{\rho}\sup_{\lambda\in(\underline{\lambda},H/\rho]}\frac{\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]-\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]\right\rvert}{\left\lvert\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(\frac{-V(s^{\prime})}{\lambda}\right)\right]\right\rvert}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{H}{\rho}\sup_{\lambda^{\prime}\in[\rho/H,1/\underline{\lambda})}\frac{\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(-\lambda^{\prime}V(s^{\prime})\right)\right]-\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(-\lambda^{\prime}V(s^{\prime})\right)\right]\right\rvert}{\left\lvert\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(-\lambda^{\prime}V(s^{\prime})\right)\right]\right\rvert}$
(31)
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}\frac{H}{\rho}\mathrm{exp}\left(H/\underline{\lambda}\right)\sup_{\lambda^{\prime}\in[\rho/H,1/\underline{\lambda})}\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(-\lambda^{\prime}V(s^{\prime})\right)\right]-\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(-\lambda^{\prime}V(s^{\prime})\right)\right]\right\rvert$
$\displaystyle=\frac{H}{\rho}\mathrm{exp}\left(H/\underline{\lambda}\right)\sup_{\lambda^{\prime}\in[\rho/H,1/\underline{\lambda})}\left\lvert\widehat{P}^{o}_{h,s,a}\mathrm{exp}\left(-\lambda^{\prime}V\right)-P^{o}_{h,s,a}\mathrm{exp}\left(-\lambda^{\prime}V\right)\right\rvert,$
(32)

where $(a)$ follows from the fact that
$\left\lvert\inf_{x}f(x)-\inf_{x}g(x)\right\rvert\leq\sup_{x}\left\lvert
f(x)-g(x)\right\rvert$. $(b)$ is due to
$\lvert\mathrm{log}\left(1+x\right)\rvert\leq\left\lvert x\right\rvert$. $(c)$
is from a substitution of $\lambda^{\prime}=1/\lambda$. $(d)$ is because
$\mathrm{exp}\left(-\lambda^{\prime}V(s^{\prime})\right)$ is lower bounded by
$\mathrm{exp}\left(-H/\underline{\lambda}\right)$, for all
$s^{\prime}\in\mathcal{S}$. In the last equality,
$\mathrm{exp}\left(\cdot\right)$ denotes the element-wise exponential
function.

Now let $\mathcal{N}_{\rho}(\theta)$ be a $\theta$-cover of the interval
$[\rho/H,1/\underline{\lambda})$ with $\theta\in(0,1)$. Recall that we defined
$\underline{\lambda}\in(0,1)$ above. We have
$\left\lvert\mathcal{N}_{\rho}(\theta)\right\rvert\leq(1/\underline{\lambda}-\rho/H)/\theta+1\leq
2/(\theta\underline{\lambda})$. Now fix any
$\lambda\in[\rho/H,1/\underline{\lambda})$, there exists a
$\nu\in\mathcal{N}_{\rho}(\theta)$ such that
$\lvert\lambda-\nu\rvert\leq\theta$. Now for these particular $\lambda$ and
$\nu$, we have

$\displaystyle\left\lvert\widehat{P}^{o}_{h,s,a}\mathrm{exp}\left(-\lambda
V\right)-P^{o}_{h,s,a}\mathrm{exp}\left(-\lambda V\right)\right\rvert$
$\displaystyle=\left\lvert\sum_{s^{\prime}\in\mathcal{S}}\left(\widehat{P}^{o}_{h}(s^{\prime}\mid
s,a)-P^{o}_{h}(s^{\prime}\mid s,a)\right)\mathrm{exp}\left(-\nu
V(s^{\prime})\right)\mathrm{exp}\left((\nu-\lambda)V(s^{\prime})\right)\right\rvert$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\left\lvert\sum_{s^{\prime}\in\mathcal{S}}\left(\widehat{P}^{o}_{h}(s^{\prime}\mid
s,a)-P^{o}_{h}(s^{\prime}\mid s,a)\right)\mathrm{exp}\left(-\nu
V(s^{\prime})\right)\mathrm{exp}\left(\theta V_{\max}\right)\right\rvert$
$\displaystyle=\mathrm{exp}\left(\theta
H\right)\left\lvert\widehat{P}^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)-P^{o}_{h,s,a}\mathrm{exp}\left(-\nu V\right)\right\rvert$
$\displaystyle\leq\mathrm{exp}\left(\theta
H\right)\max_{\nu\in\mathcal{N}_{\rho}(\theta)}\left\lvert\widehat{P}^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)-P^{o}_{h,s,a}\mathrm{exp}\left(-\nu V\right)\right\rvert,$

where $(a)$ is due to $V_{\max}=H$ and
$\left\lvert\nu-\lambda\right\rvert\leq\theta$. Taking maximum over
$\lambda\in[\rho/H,1/\underline{\lambda})$ on both sides, we get

$\sup_{\lambda\in[\rho/H,1/\underline{\lambda})}\left\lvert\widehat{P}^{o}_{h,s,a}\mathrm{exp}\left(-\lambda
V\right)-P^{o}_{h,s,a}\mathrm{exp}\left(-\lambda
V\right)\right\rvert\leq\max_{\nu\in\mathcal{N}_{\rho}(\theta)}\left\lvert\widehat{P}^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)-P^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)\right\rvert\mathrm{exp}\left(\theta H\right).$ (33)

Observe that for all $\nu\in\mathcal{N}_{\rho}(\theta)$ and $s\in\mathcal{S}$,
$\mathrm{exp}\left(-\nu V(s)\right)\leq\mathrm{exp}\left(-\nu 0\right)\leq 1$.
That is, $\lVert\mathrm{exp}\left(-\nu V\right)\rVert_{\infty}\leq 1$. Since
$V$ is independent of $\widehat{P}^{o}_{h,s,a}$, we can apply Hoeffding’s
inequality (Lemma 2):

$\mathbb{P}\left(\left\lvert\widehat{P}^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)-P^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)\right\rvert\geq\epsilon\right)\leq
2\mathrm{exp}\left(-\frac{2N\epsilon^{2}}{\lVert\mathrm{exp}\left(-\nu
V\right)\rVert_{\infty}^{2}}\right)\leq
2\mathrm{exp}\left(-2N\epsilon^{2}\right),\qquad\forall\epsilon>0.$

Now choose
$\epsilon=\sqrt{\frac{\mathrm{log}\left(2\left\lvert\mathcal{N}_{\rho}(\theta)\right\rvert/\delta\right)}{2N}}$.
We have

$\displaystyle\mathbb{P}\left(\left\lvert\widehat{P}^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)-P^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)\right\rvert\geq\sqrt{\frac{\mathrm{log}\left(4/(\theta\underline{\lambda}\delta)\right)}{2N}}\right)$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\leq\mathbb{P}\left(\left\lvert\widehat{P}^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)-P^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)\right\rvert\geq\sqrt{\frac{\mathrm{log}\left(2\left\lvert\mathcal{N}_{\rho}(\theta)\right\rvert/\delta\right)}{2N}}\right)\leq\frac{\delta}{\left\lvert\mathcal{N}_{\rho}(\theta)\right\rvert}.$

Applying a union bound over $\nu\in\mathcal{N}_{\rho,V}(\theta)$, we get

$\max_{\nu\in\mathcal{N}_{\rho}(\theta)}\left\lvert\widehat{P}^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)-P^{o}_{h,s,a}\mathrm{exp}\left(-\nu
V\right)\right\rvert\leq\sqrt{\frac{\mathrm{log}\left(4/(\theta\underline{\lambda}\delta)\right)}{2N}},$
(34)

with probability at least $1-\delta$. Combining Eq. 32-Eq. 34 completes the
proof. ∎

###### Proof of Proposition 6.

Recall that $\widehat{V}_{h+1}$ is independent of $\widehat{P}^{o}_{h,s,a}$ by
construction. Similar to Corollary 1 and Proposition 2, the result directly
follows from Lemma 14 and the law of total probability. ∎

We now have all the ingredients to prove our main result.

###### Proof of Theorem 3.

The proof is almost identical to that of Theorem 1. By applying Proposition 6
and taking a union bound over
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$, we have

$\displaystyle\left\lVert
V_{1}^{*}-V_{1}^{\widehat{\pi}}\right\rVert_{\infty}$
$\displaystyle\leq\frac{2H^{2}}{\rho}\mathrm{exp}\left(H/\underline{\lambda}\right)\mathrm{exp}\left(\theta
H\right)\sqrt{\frac{\mathrm{log}\left(4H\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert/(\theta\underline{\lambda}\delta)\right)}{2N}}$
$\displaystyle\leq\frac{2H^{2}}{\rho}\mathrm{exp}\left(H/\underline{\lambda}+H/2\right)\sqrt{\frac{\mathrm{log}\left(8H\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert/(\underline{\lambda}\delta)\right)}{2N}},$

with probability at least $1-\delta$, and the last inequality is because we
can simply choose $\theta=1/2$. Now if we choose

$N\geq\frac{2\mathrm{exp}\left(3H/\underline{\lambda}\right)}{\rho^{2}}\frac{H^{4}\mathrm{log}\left(8H\left\lvert\mathcal{S}\right\rvert\left\lvert\mathcal{A}\right\rvert/(\underline{\lambda}\delta)\right)}{\epsilon^{2}},$

we get $\lVert V_{1}^{*}-V_{1}^{\widehat{\pi}}\rVert_{\infty}\leq\epsilon$
with probability at least $1-\delta$. ∎

###  B.4 Proof of Theorem 4

Here we provide the proofs of supporting lemmas and that of Theorem 4.

######  Lemma 15.

Fix any value function $V\in\mathcal{V}$ and
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$. For any
$\theta,\delta\in(0,1)$ and $\rho>0$, we have, with probability at least
$1-\delta$,

$\left\lvert
L_{\mathcal{P}_{h,s,a}}V-L_{\widehat{\mathcal{P}}_{h,s,a}}V\right\rvert\leq\frac{H}{\rho}\sqrt{\frac{\mathrm{log}\left(2\left\lvert\mathcal{S}\right\rvert/\delta\right)}{2N\underline{p}^{2}}},$

where $\underline{p}=\min_{s^{\prime},s,a,h\colon P_{h}^{o}(s^{\prime}\mid
s,a)>0}P^{o}_{h}(s^{\prime}|s,a)>0$ and $N$ is the number of samples used to
approximate $P^{o}_{h,s,a}$.

###### Proof.

From Eq. 31, we get

$\displaystyle\left\lvert
L_{\mathcal{P}_{h,s,a}}V-L_{\widehat{\mathcal{P}}_{h,s,a}}V\right\rvert$
$\displaystyle\leq\frac{H}{\rho}\sup_{\lambda\in[\rho/H,1/\underline{\lambda})}\frac{\left\lvert\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(-\lambda
V(s^{\prime})\right)\right]-\mathbb{E}_{s^{\prime}\sim P^{o}_{h}(\cdot\mid
s,a)}\left[\mathrm{exp}\left(-\lambda
V(s^{\prime})\right)\right]\right\rvert}{\left\lvert\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid s,a)}\left[\mathrm{exp}\left(-\lambda
V(s^{\prime})\right)\right]\right\rvert}$
$\displaystyle\leq\frac{H}{\rho}\sup_{\lambda\in[\rho/H,1/\underline{\lambda})}\frac{\sum_{s^{\prime}\in\mathcal{S}}\left\lvert\widehat{P}^{o}_{h}(s^{\prime}\mid
s,a)-P^{o}_{h}(s^{\prime}\mid s,a)\right\rvert\mathrm{exp}\left(-\lambda
V(s^{\prime})\right)}{\sum_{s^{\prime}\in\mathcal{S}}P^{o}_{h}(s^{\prime}\mid
s,a)\mathrm{exp}\left(-\lambda V(s^{\prime})\right)}$
$\displaystyle\leq\frac{H}{\rho}\sup_{\lambda\in[\rho/H,1/\underline{\lambda})}\frac{\sum_{s^{\prime}\in\mathcal{S}}\left\lvert\widehat{P}^{o}_{h}(s^{\prime}\mid
s,a)-P^{o}_{h}(s^{\prime}\mid s,a)\right\rvert\mathrm{exp}\left(-\lambda
V(s^{\prime})\right)}{\sum_{s^{\prime}\in\mathcal{S}}P^{o}_{h}(s^{\prime}\mid
s,a)\mathrm{exp}\left(-\lambda V(s^{\prime})\right)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\frac{H}{\rho}\max_{s^{\prime}\colon
P^{o}_{h}(s^{\prime}\mid
s,a)>0}\left\lvert\frac{\widehat{P}^{o}_{h}(s^{\prime}\mid
s,a)}{P^{o}_{h}(s^{\prime}\mid s,a)}-1\right\rvert,$ (35)

where $(a)$ follows from
$\sum_{i}a_{i}/\sum_{i}b_{i}\leq\max_{i}\\{a_{i}/b_{i}\\}$, when $b_{i}>0$. We
denote $\underline{p}=\min_{s^{\prime},s,a,h\colon P^{o}_{h}(s^{\prime}\mid
s,a)>0}P^{o}_{h}(s^{\prime}\mid s,a)$. Note that $\underline{p}$ is a problem
dependent constant and not dependent on $(h,s,a)$. Now fix any
$s^{\prime}\in\mathcal{S}$ such that $P^{o}_{h}(s^{\prime}\mid s,a)>0$.
Hoeffding’s inequality tells us

$\mathbb{P}\left(\left\lvert\frac{\widehat{P}^{o}_{h}(s^{\prime}\mid
s,a)}{P^{o}_{h}(s^{\prime}\mid s,a)}-1\right\rvert\geq\epsilon\right)\leq
2\mathrm{exp}\left(-\frac{2N\epsilon^{2}}{(1/\underline{p})^{2}}\right)=2\mathrm{exp}\left(-2N\underline{p}^{2}\epsilon^{2}\right).$

Choosing
$\epsilon=\sqrt{\frac{\mathrm{log}\left(2\left\lvert\mathcal{S}\right\rvert/\delta\right)}{2N\underline{p}^{2}}}$
and applying a union bound over $s^{\prime}\in\mathcal{S}$, we get

$\max_{s^{\prime}\colon P^{o}_{h}(s^{\prime}\mid
s,a)>0}\left\lvert\frac{\widehat{P}^{o}_{h}(s^{\prime}\mid
s,a)}{P^{o}_{h}(s^{\prime}\mid
s,a)}-1\right\rvert\leq\sqrt{\frac{\mathrm{log}\left(2\left\lvert\mathcal{S}\right\rvert/\delta\right)}{2N\underline{p}^{2}}},$

with probability at least $1-\delta$. Combining the above and Eq. 35, we get
the desired result. ∎

###### Proof of Proposition 7.

Recall that $\widehat{V}_{h+1}$ is independent of $\widehat{P}^{o}_{h,s,a}$ by
construction. Similar to Corollary 1 and Proposition 2, the result directly
follows from Lemma 15 and the law of total probability. ∎

We now have all the ingredients to prove our main result.

###### Proof of Theorem 4.

The proof is almost identical to that of Theorem 1. By applying Proposition 7
and taking a union bound over
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$, we have

$\left\lVert
V_{1}^{*}-V_{1}^{\widehat{\pi}}\right\rVert_{\infty}\leq\frac{2H^{2}}{\rho}\sqrt{\frac{\mathrm{log}\left(2H\left\lvert\mathcal{S}\right\rvert^{2}\left\lvert\mathcal{A}\right\rvert/\delta\right)}{2N\underline{p}^{2}}},$

with probability at least $1-\delta$. Now if we choose

$N\geq\frac{2H^{4}}{\rho^{2}\underline{p}^{2}}\frac{\mathrm{log}\left(2H\left\lvert\mathcal{S}\right\rvert^{2}\left\lvert\mathcal{A}\right\rvert/\delta\right)}{\epsilon},$

then we get $\lVert V^{*}-V^{\widehat{\pi}}\rVert_{\infty}\leq\epsilon$ with
probability at least $1-\delta$. ∎

###  B.5 Proof of Theorem 5

Here we provide the proofs of supporting lemmas and that of Theorem 5.

######  Proposition 11 (Gao and Kleywegt,, 2022, Theorem 1).

Let $P^{o}$ be a distribution on the bounded space $\mathcal{X}$ and let
$l\colon\mathcal{X}\to\mathbb{R}$ be a bounded loss function. Then,

$\sup_{D_{W}\left(P\;\|\;P^{o}\right)\leq\rho}\mathbb{E}_{P}\left[l(X)\right]=\inf_{\lambda\geq
0}\mathbb{E}_{Y\sim P^{o}}\left[\sup_{x\in\mathcal{X}}\\{l(x)-\lambda
d^{p}(x,Y)\\}\right]+\lambda\rho^{p}.$

###### Proof of Proposition 8.

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

$\displaystyle L_{\mathcal{P}_{h,s,a}}V$
$\displaystyle=\inf_{D_{W}\left(P\;\|\;P^{o}\right)\leq\rho}\mathbb{E}_{s\sim
P}\left[V(s)\right]=-\sup_{D_{W}\left(P\;\|\;P^{o}\right)\leq\rho}\mathbb{E}_{s\sim
P}\left[-V(s)\right]$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}-\inf_{\lambda\geq
0}\left\\{\mathbb{E}_{s^{\prime}\sim P^{o}_{h}(\cdot\mid
s,a)}\left[\sup_{s^{\prime\prime}\in\mathcal{S}}\left\\{-V(s^{\prime\prime})-\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]+\lambda\rho^{p}\right\\}$
$\displaystyle=\sup_{\lambda\geq 0}\left\\{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]-\lambda\rho^{p}\right\\}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\sup_{\lambda\in[0,H/\rho^{p}]}\left\\{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]-\lambda\rho^{p}\right\\},$

where $(a)$ follows from Proposition 11. For $(b)$, let us first denote any
optimizer in $(a)$ to be $\lambda^{*}$. Observe that since $V$ is non-
negative, it follows that $L_{\mathcal{P}_{h,s,a}}V$ is also non-negative. Now
due to $V_{\max}=H$, we have that

$0\leq-\lambda^{*}\rho^{p}+\mathbb{E}_{s^{\prime}\sim P^{o}_{h}(\cdot\mid
s,a)}\left[\inf_{s^{\prime\prime}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]\leq-\lambda^{*}\rho^{p}+\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid s,a)}\left[V(s^{\prime})+\lambda
d^{p}(s^{\prime},s^{\prime})\right]\leq-\lambda^{*}\rho^{p}+H,$

where in the last inequality we use that the distance metric satisfies
$d(s,s)=0$, for any $s\in\mathcal{S}$. ∎

######  Lemma 16 (Covering number (Wasserstein)).

Fix any value function $V\in\mathcal{V}$, consider the following set of
$\mathbb{R}^{\left\lvert\mathcal{S}\right\rvert}$ vectors:

$\mathcal{U}_{\rho,V}=\left\\{\left(\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},1)\right\\},\dots,\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},\left\lvert\mathcal{S}\right\rvert)\right\\}\right)^{T}\colon\lambda\in[0,H/\rho^{p}]\right\\}.$

Let

$\mathcal{N}_{\rho,V}(\theta)=\left\\{\left(\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},1)\right\\},\dots,\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},\left\lvert\mathcal{S}\right\rvert)\right\\}\right)^{T}\colon\lambda\in\left\\{\frac{\theta}{B_{p}},\frac{2\theta}{B_{p}},\dots,N_{\rho,\theta}\frac{\theta}{B_{p}}\right\\}\right\\},$

where $N_{\rho,\theta}=\left\lceil\frac{HB_{p}}{\rho^{p}\theta}\right\rceil$
and
$B_{p}=\max_{s^{\prime},s^{\prime\prime}}d^{p}(s^{\prime\prime},s^{\prime})$.
Then $\mathcal{N}_{\rho,V}(\theta)$ is a $\theta$-cover of
$\mathcal{U}_{\rho,V}$ with respect to
$\left\lVert\cdot\right\rVert_{\infty}$, and its cardinality is bounded as
$\left\lvert\mathcal{N}_{\rho,V}(\theta)\right\rvert\leq\frac{HB_{p}+(H\vee\rho^{p})}{\rho^{p}\theta}$.
Furthermore, for any $\nu\in\mathcal{N}_{\rho,V}(\theta)$, we have
$\left\lVert\nu\right\rVert_{\infty}\leq\frac{H(B_{p}+\rho^{p})}{\rho^{p}}$.

###### Proof.

Fix any $\theta\in(0,1)$. First note that $N_{\rho,\theta}$ is the minimal
number of subintervals of length $\frac{\theta}{B_{p}}$ needed to cover
$[0,H/\rho^{p}]$. Denote
$J_{i}=[(i-1)\frac{\theta}{B_{p}},i\frac{\theta}{B_{p}})$, $1\leq i\leq
N_{\rho,\theta}$. Fix some $\mu\in\mathcal{U}_{\rho,V}$. Then $\mu$ must takes
the form

$\mu=\left(\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},1)\right\\},\dots,\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},\left\lvert\mathcal{S}\right\rvert)\right\\}\right)^{T},$

for some $\lambda\in[0,H/\rho^{p}]$. Without loss of generality, assume
$\lambda\in J_{i}$. Now we pick

$\nu=\left(\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+i\frac{\theta}{B_{p}}d^{p}(s^{\prime\prime},1)\right\\},\dots,\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+i\frac{\theta}{B_{p}}d^{p}(s^{\prime\prime},\left\lvert\mathcal{S}\right\rvert)\right\\}\right)^{T}.$

Fix any $s^{\prime}\in\mathcal{S}$, we have

$\displaystyle\left\lvert\mu(s^{\prime})-\nu(s^{\prime})\right\rvert$
$\displaystyle=\left\lvert\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}-\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+i\frac{\theta}{B_{p}}d^{p}(s^{\prime\prime},s)\right\\}\right\rvert$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sup_{s^{\prime\prime}\in\mathcal{S}}\left\lvert\left(\lambda-i\frac{\theta}{B_{p}}\right)d^{p}(s^{\prime\prime},s^{\prime})\right\rvert$
$\displaystyle\leq\left\lvert\lambda-i\frac{\theta}{B_{p}}\right\rvert\max_{s^{\prime},s^{\prime\prime}}d^{p}(s^{\prime\prime},s^{\prime})=\left\lvert\lambda-i\frac{\theta}{B_{p}}\right\rvert
B_{p}$
$\displaystyle\leq\left\lvert(i-1)\frac{\theta}{B_{p}}-i\frac{\theta}{B_{p}}\right\rvert
B_{p}=\theta,$

where $(a)$ is due to $\lvert\inf_{x}f(x)-\inf_{x}g(x)\rvert\leq\sup_{x}\lvert
f(x)-g(x)\rvert$. Taking maximum over $s^{\prime}\in\mathcal{S}$ on both
sides, we get $\left\lVert\mu-\nu\right\rVert_{\infty}\leq\theta$. Since
$\nu\in\mathcal{N}_{\rho,V}(\theta)$, this suggests that
$\mathcal{N}_{\rho,V}(\theta)$ is a $\theta$-cover for $\mathcal{U}_{\rho,V}$.

To bound the cardinality of $\mathcal{N}_{\rho,V}(\theta)$, we consider two
cases. If $0<\rho<1$, then $\rho^{p}\theta<1$ and

$\left\lceil\frac{HB_{p}}{\rho^{p}\theta}\right\rceil\leq\frac{HB_{p}}{\rho^{p}\theta}+1\leq\frac{HB_{p}}{\rho^{p}\theta}+\frac{H}{\rho^{p}\theta}=\frac{HB_{p}+H}{\rho^{p}\theta}.$

On the other hand, if $\rho>1$, then since $\theta\in(0,1)$, we have

$\left\lceil\frac{HB_{p}}{\rho^{p}\theta}\right\rceil\leq\frac{HB_{p}}{\rho^{p}\theta}+1=\frac{HB_{p}}{\rho^{p}\theta}+\frac{\rho^{p}\theta}{\rho^{p}\theta}\leq\frac{HB_{p}}{\rho^{p}\theta}+\frac{\rho^{p}}{\rho^{p}\theta}=\frac{HB_{p}+\rho^{p}}{\rho^{p}\theta}.$

Hence, we have
$\left\lvert\mathcal{N}_{\rho,V}(\theta)\right\rvert=N_{\rho,\theta}\leq\frac{HB_{p}+(H\vee\rho^{p})}{\rho^{p}\theta}$.
Now we prove the last claim. Fix any $\nu\in\mathcal{N}_{\rho,V}$. Note that
for any $s^{\prime}\in\mathcal{S}$,

$\nu(s^{\prime})=\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\leq H+\lambda B_{p}\leq
H+\frac{H}{\rho^{p}}B_{p}=\frac{H(B_{p}+\rho^{p})}{\rho^{p}}.$

The result then follows from taking maximum over $s^{\prime}\in\mathcal{S}$ on
both sides. ∎

######  Lemma 17.

Fix any $(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$. Fix any value
function $V\in\mathcal{V}$. Let $\mathcal{N}_{\rho,V}(\theta)$ be the
$\theta$-cover of the set

$\mathcal{U}_{\rho,V}=\left\\{\left(\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},1)\right\\},\dots,\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},\left\lvert\mathcal{S}\right\rvert)\right\\}\right)^{T}\colon\lambda\in[0,H/\rho^{p}]\right\\},$

as described in Lemma 16. We then have

$\displaystyle\sup_{\lambda\in[0,H/\rho^{p}]}$
$\displaystyle\left\lvert\mathbb{E}_{s^{\prime}\sim P^{o}_{h}(\cdot\mid
s,a)}\left[\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]-\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]\right\rvert$
$\displaystyle\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\leq\max_{\nu\in\mathcal{N}_{\rho,V}(\theta)}\left\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\right\rvert+2\theta.$

###### Proof.

The proof is identical to the proof of Lemma 7. ∎

######  Lemma 18.

Fix any value function $V\in\mathcal{V}$ and
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$. For any
$\theta,\delta\in(0,1)$ and $\rho>0$, we have the following inequality with
probability at least $1-\delta$

$\left\lvert
L_{\mathcal{P}_{h,s,a}}V-L_{\widehat{\mathcal{P}}_{h,s,a}}V\right\rvert\leq\frac{H(B_{p}+\rho^{p})}{\rho^{p}}\sqrt{\frac{\mathrm{log}\left(\frac{2HB_{p}+2(H\vee\rho^{p})}{\rho^{p}\theta\delta}\right)}{2N}}+2\theta,$

where
$B_{p}=\max_{s^{\prime},s^{\prime\prime}}d^{p}(s^{\prime\prime},s^{\prime})$.

###### Proof.

Fix any value function $V\in\mathcal{V}$ independent of
$\widehat{P}^{o}_{h,s,a}$ and
$(h,s,a)\in[H]\times\mathcal{S}\times\mathcal{A}$. From Proposition 8, we have

$\displaystyle L_{\mathcal{P}_{h,s,a}}V$
$\displaystyle=\sup_{\lambda\in[0,H/\rho^{p}]}\left\\{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]-\lambda\rho^{p}\right\\},$
$\displaystyle L_{\widehat{\mathcal{P}}_{h,s,a}}V$
$\displaystyle=\sup_{\lambda\in[0,H/\rho^{p}]}\left\\{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]-\lambda\rho^{p}\right\\}.$

Now it follows that

$\displaystyle\left\lvert
L_{\mathcal{P}_{h,s,a}}V-L_{\widehat{\mathcal{P}}_{h,s,a}}V\right\rvert$
$\displaystyle=\bigg{\lvert}\sup_{\lambda\in[0,H/\rho^{p}]}\left\\{\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]-\lambda\rho^{p}\right\\}$
$\displaystyle\quad-\sup_{\lambda\in[0,H/\rho^{p}]}\left\\{\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]-\lambda\rho^{p}\right\\}\bigg{\rvert}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}\sup_{\lambda\in[0,H/\rho^{p}]}\bigg{\lvert}\mathbb{E}_{s^{\prime}\sim
P^{o}_{h}(\cdot\mid
s,a)}\left[\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]$
$\displaystyle\quad-\mathbb{E}_{s^{\prime}\sim\widehat{P}^{o}_{h}(\cdot\mid
s,a)}\left[\inf_{s^{\prime\prime}\in\mathcal{S}}\left\\{V(s^{\prime\prime})+\lambda
d^{p}(s^{\prime\prime},s^{\prime})\right\\}\right]\bigg{\rvert}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\max_{\nu\in\mathcal{N}_{\rho,V}(\theta)}\left\lvert\widehat{P}^{o}_{h,s,a}\nu-P^{o}_{h,s,a}\nu\right\rvert+2\theta,$
(36)

where $(a)$ follows from
$\lvert\sup_{x}f(x)-\sup_{x}g(x)\rvert\leq\sup_{x}\lvert f(x)-g(x)\rvert$.
$(b)$ follows from Lemma 17.

Recall that all $\nu\in\mathcal{N}_{\rho,V}(\theta)$ is bounded by
$\nu_{\max}:=\frac{H(B_{p}+\rho^{p})}{\rho^{p}}$. Now we can apply Hoeffding’s
inequality (Lemma 2):