Offline reinforcement learning aims to find the optimal policy from a pre-collected dataset without active exploration. This problem is faced with major challenges, such as a limited amount of data and distribution shift.  Existing studies employ the principle of pessimism in face of uncertainty, and penalize rewards for less visited state-action pairs.  In this paper, we directly model the uncertainty in the transition kernel using an uncertainty set, and then employ the approach of distributionally robust optimization that optimizes the worst-case performance over the uncertainty set. We first design a Hoeffding-style uncertainty set, which guarantees that the true transition kernel lies in the uncertainty set with high probability. We theoretically prove that it achieves an $\epsilon$-accuracy with a sample complexity of $\mathcal{O}\left((1-\gamma)^{-4}\epsilon^{-2}SC^{\pi^*} \right)$, where $\gamma$ is the discount factor, $C^{\pi^*}$ is the single-policy concentrability for any comparator policy $\pi^*$, and $S$ is the number of states. We further design a Bernstein-style uncertainty set, which does not necessarily guarantee the true transition kernel lies in the uncertainty set. We show an improved and near-optimal sample complexity of $\mathcal{O}\left((1-\gamma)^{-3}\epsilon^{-2}\left(SC^{\pi^*}+(\mu_{\min})^{-1}\right) \right)$, where $\mu_{\min}$ denotes the minimal non-zero entry of the behavior distribution. In addition, the computational complexity of our algorithms is the same as one of the LCB-based methods in the literature. Our results demonstrate that distributionally robust optimization method can also efficiently solve offline reinforcement learning.

§ INTRODUCTION

Reinforcement learning (RL) has achieved impressive empirical success, e.g., in the gaming domain [38, 56]. Nonetheless, most of the success stories rely on the premise that the agent can actively explore the environment and receive feedback to further promote policy improvement. This  trial-and-error procedure can be costly, unsafe, or even prohibitory in many real-world applications, e.g., autonomous driving [28] and health care [72]. To address the challenge, offline (or batch) reinforcement learning [31, 32] was developed, where the aim is to learn a competing policy from a pre-collected dataset without access to online exploration.

A straightforward idea for offline RL is to
use the pre-collected dataset to learn an estimated model of the environment, and then learn an optimal policy for this model. However, the learned policy may not perform well due to the challenge of distribution shift [27, 49, 33]. Specifically, the pre-collected dataset is often restricted to a small subset of state-action pairs, e.g., for insulin management of diabetes, not all possible actions are safe, and

the behavior policy used to collect the dataset in general induces a  state-action visitation distribution that is different from the one induced by the optimal policy. This distribution shift and the limited amount of data lead to uncertainty in the environment transition kernel and/or reward function.

To address the above challenge, one natural approach is to first quantify the uncertainty, and further take a pessimistic (conservative) approach in face of uncertainty. Despite of the fact that the uncertainty exists in the transition kernel estimate and/or the reward function estimate, existing studies mostly take the approach to penalize the reward function for less-visited state-action pairs, e.g., Lower Confidence Bound (LCB) approaches [47, 33, 54, 69]. In this paper, we focus on a direct approach to analyzing the uncertainty in the transition kernel by constructing a statistically plausible set of transition kernels, known as uncertainty set, and optimizing the worst-case performance over the uncertainty set. This principle is referred to as "distributionally robust optimization (DRO)" or "robust Markov decision process" in the literature. Our work demonstrates that the DRO approach offers an efficient solution to the offline RL problem.

In [58], an uncertainty set of transition kernels is constructed based on some concentration argument ensuring that the true transition kernel lies within the uncertainty set with high probability (Hoeffding-style). Then, the algorithm optimizes the worst-case value function over the uncertainty set. But, the way the uncertainty set was designed makes the max-min optimization problem in [58] NP-hard [64]. Alternatively, heuristic adversarial training methods that relax the max-min problem to a two-player zero-sum game were developed [6, 11, 22, 75, 48]. Nevertheless, there is no theoretical guarantee that these heuristic methods will converge to the solution of the max-min problem. In this paper, we address the above two limitations: 1) we design computationally efficient DRO-based algorithms for offline RL; and 2) we derive the theoretical sample complexity guarantee. We summarize our major contributions in the following section.

§.§ Main Contributions

For the approach of DRO, the uncertainty set is typically designed to guarantee that with high probability, the true distribution lies within the uncertainty set centered at the empirical distribution [43, 70, 68, 45]. Then, optimizing the worst-case performance over the uncertainty set provides a worst-case performance guarantee under the true distribution.
We first construct a  Hoeffding-style uncertainty set, which  guarantees that with high probability the true transition kernel falls into the designed uncertainty set.

Instead of an in-expectation style of uncertainty set in [6, 11, 22, 75, 48],
we construct an $(s,a)$-rectangular uncertainty set (see details in <Ref>),
which enables easy solutions using the robust dynamic programming approach developed for robust MDP in [23, 42].
In this way, our algorithm is computationally efficient with per-iteration complexity of $S^2A\log(S)$, where $S$ and $A$ are numbers of states and actions, respectively.
We show that robust dynamic programming [23, 42] with the designed Hoeffding-style uncertainty set  achieves a sample complexity of $\mathcal{O}\left(\frac{ SC^{\pi^*}  }{(1-\gamma)^{4}\epsilon^{2}}\right)$ (up to log factor),  where $\epsilon$ is the desired accuracy level, $\gamma$ is the discount factor, and $C^{\pi^*}$ is the single-policy concentrability for any comparator policy $\pi^*$. This sample complexity matches with the best-known complexity of the LCB and Hoeffding-style method [47], which demonstrates that  offline RL can be solved efficiently by directly tackling the model uncertainty and applying the DRO-based  method.

Though the above Hoeffding-style approach is capable of reaching a small optimality gap, it tends to be overly conservative as it underperforms the best-known sample complexity for offline RL in [33] by a factor of  $(1-\gamma)^{-1}$. To close this gap, we find out that requiring the true transition kernel to be in the uncertainty set with high probability, i.e., the true transition kernel and the worst-case transition kernel are close, is not necessary. What is essentially needed is that the expectation of the value function under the two transition kernels is close.

We then further design a less conservative Bernstein-style uncertainty set, which has an order-level smaller radius than the Hoeffding-style uncertainty set. This is motivated by the studies of the LCB methods where a Bernstein-style design of the bonus term leads to an improved sample complexity in terms of the dependence on $(1-\gamma)$.
However, the Bernstein-style uncertainty set makes the analysis challenging. This is because with a smaller radius, the true transition kernel may not necessarily fall into the uncertainty set. We theoretically derive an improved and  near-optimal sample complexity of $\mathcal{O}\left(\frac{ SC^{\pi^*}+(\mu_{\min})^{-1} }{(1-\gamma)^{3}\epsilon^{2}}\right)$, where $\mu_{\min}=\min_{s,a}\{\mu(s,a)| \mu(s,a)>0\}$ is the minimal positive entry of behavior policy $\mu$. Compared to the best-known sample complexity of LCB methods, which is also minimax optimal, our Bernstein-style design achieves an optimal dependence on $(1-\gamma)$ and $\epsilon$.

In summary, we show that under the most general partial coverage condition, our DRO-based approach is able to reach a target accuracy level in a computationally and sample-efficient way. In addition, many existing results require a large burn-in cost [67, 21, 69]. Specifically, their claimed sample complexity can only be achieved when the number of samples exceeds the burn-in cost. In contrast, our result needs no burn-in phase to achieve the optimal sample complexity. Our results demonstrate that the DRO approach can efficiently solve the offline RL problem.

§.§ Related Works

There has been a proliferation of works on offline RL. In this section, we discuss works on model-based approaches. There are also model-free approaches, e.g., [36, 30, 2, 69, 54], which are not the focus of this paper.

Global coverage.
Existing studies on offline RL often make assumptions on the coverage of the dataset. This can be measured by the distribution shift between the behavior policy and the occupancy measure induced by the target policy, which is referred to as the concentrability coefficient [39, 47].

Many previous works, e.g.,  [52, 9, 25, 60, 34, 35, 76, 40, 57, 13, 66, 32, 3, 14], assume that the density ratio between the above two distributions is finite  for all state-action pairs and policies, which is known as global coverage. This assumption essentially requires the behavior policy to be able to visit all possible state-action pairs,
which is often violated in practice [19, 2, 15].

Partial coverage.
Recent studies relax the above assumption of global coverage to partial coverage or single-policy concentrability. Partial coverage assumes that the density ratio between the distributions induced by a single target policy and the behavior policy is bounded for all state-action pairs. Therefore, this assumption does not require the behavior policy to be able to visit all possible state-action pairs, as long as it can visit those state-actions pairs that the target policy will visit. This partial coverage assumption is more feasible and applicable in real-world scenarios. In this paper, we focus on this practical partial coverage setting. Existing approaches under the partial coverage assumption can be divided into three categories as follows.

Regularized Policy Search.
The first approach regularizes the policy so that the learned policy is close to the behavior policy [17, 65, 24, 46, 55, 63, 29, 16, 18, 41, 78, 77]. Thus,  the learned policy is similar to the behavior policy which generates the dataset, hence this approach works well when the dataset is collected from experts [65, 15].

Reward Penalization.
One of the most widely used approaches is to penalize the reward in face of uncertainty, e.g.,  [27, 74, 73, 7, 26, 67, 71, 36, 12, 10, 79]. The most popular approach VI-LCB  [47] penalizes the reward with a bonus term that is inversely proportional to the number of samples. The tightest sample complexity is obtained in  [33] by designing a Bernstein-style penalty term, which matches the minimax lower bound in [47].

DRO-based Approach.
Another popular approach is to first construct a set of “statistically plausible” MDP models based on the empirical transition kernel, and then find the policy that optimizes the worst-case performance over this set [75, 58, 48, 6, 20, 22, 8]. These works, however, either are NP-hard or use heuristic approximations without theoretical optimality guarantee. Our work falls into this category, but our method is computationally efficient and has a near-optimal sample complexity.

Robust MDPs.
In this paper, our algorithm is based on the framework of robust MDP [23, 42, 5, 51, 64], which finds the policy with the best worst-case performance over the uncertainty set. Under the model-based setting, the problem can be solved by robust dynamic programming. It is further extended to the model-free setting under different fashions including online setting [50, 61, 62], generative model setting [70, 68, 45], and offline setting [44, 53]. Note that the analyses therein cannot be applied to our problem, since we focus on the optimality gap from the target policy and consider the challenging partial coverage setting.

§ PRELIMINARIES

§.§ Markov Decision Process (MDP)

An MDP  can be characterized by a tuple  $(\mathcal{S},\mathcal{A}, \kp,r)$, where $\mcs$ and $\mca$ are the state and action spaces, $\mathsf P=\left\{\kp^a_s \in \Delta(\mcs), a\in\mca, s\in\mcs\right\}$[$\Delta(\mcs)$ denotes the probability simplex defined on $\mcs$.] is the transition kernel, $r:\mcs\times\mca\to [0,1]$ is the deterministic reward function, and $\gamma\in[0,1)$ is the discount factor. Specifically, $\kp^a_s=(p^a_{s,s'})_{s'\in\mathcal S}$, where $p^a_{s,s'}$ denotes the probability that the environment transits to state $s'$ if taking action $a$ at state $s$. The reward of taking action $a$ at state $s$ is given by $r(s,a)$.
A stationary policy $\pi$ is a mapping from $\mcs$ to a distribution over $\mca$, which indicates the probabilities of the agent taking actions at each state. At each time $t$, an agent takes an action $a_t\sim\pi(s_t)$ at state $s_t$, the environment then transits to the next state $s_{t+1}$ with probability $ p^{a_t}_{s_t,s_{t+1}}$, and the agent receives reward $r(s_t,a_t)$.

The value function of a policy $\pi$ starting from any initial state $s\in\mcs$ is defined as the expected accumulated discounted reward by following $\pi$:

\begin{align}
V^\pi_{\kp}(s)\triangleq\mathbb{E}_\kp\left[\sum_{t=0}^{\infty}\gamma^t   r(S_t,A_t )|S_0=s,\pi\right],
\end{align}

where $\mE_{\kp}$ denotes the expectation when the state transits according to $\kp$
Let $\rho$ denote the initial state distribution, and denote by $V^\pi_{\kp}(\rho)=\mE_{s\sim\rho}[V^\pi_{\kp}(s)]$.

§.§ Robust Markov Decision Process

In the robust MDP, the transition kernel is not fixed and lies in some uncertainty set $\cp$.

Define the robust value function of a policy $\pi$ as the worst-case expected accumulated discounted reward  among all transition kernels in the uncertainty set:

\begin{align}\label{eq:value}
V^{\pi}_\cp(s)\triangleq\min_{\kp\in\cp} \mathbb{E}_{ \kp}\left[\sum_{t=0}^{\infty}\gamma^t   r(S_t,A_t )|S_0=s,\pi\right].
\end{align}

Similarly, the robust action-value function for a policy $\pi$ is defined as
Q^{\pi}_\cp(s,a)=\min_{\kp\in\cp}\mathbb{E}_{ \kp}\left[\sum_{t=0}^{\infty}\gamma^t r(S_t,A_t )|S_0=s,A_0=a,\pi\right].
The goal of robust RL is to find the optimal robust policy that maximizes the worst-case accumulated discounted reward, i.e.,

\begin{align}\label{eq:goal}
\pi_r=\arg\max_{\pi} V^\pi_\cp(s), \forall s\in\mcs.
\end{align}

It is shown in [23, 42, 64] that the optimal robust value function is the unique solution to the optimal robust Bellman equation

\begin{align}
V^{\pi_r}_\cp(s)=\max_a \{r(s,a)+\gamma\sigma_{\cp^a_s}(V^{\pi_r}_\cp)\},
\end{align}

where $\sigma_{\cp^a_s}(V)\triangleq \min_{p\in {\cp^a_s}} p^\top V$ denotes the support function of $V$ on a set $\cp^a_s$ and the corresponding robust Bellman operator is a $\gamma$-contraction.

§.§ Offline Reinforcement Learning

Under the offline setting, the agent cannot interact with the MDP and instead is given a pre-collected dataset $\mathcal{D}$ consisting of $N$ tuples $\{(s_i,a_i,s'_i,r_i): i=1,...,N \}$, where $r_i=r(s_i,a_i)$ is the deterministic reward, and $s'_i\sim\kp^{a_i}_{s_i}$ follows the transition kernel $\kp$ of the MDP. The $(s_i,a_i)$ pairs in $\mathcal{D}$ are generated i.i.d. according to an unknown data distribution $\mu$ over the state-action space. In this paper, the reward functions $r$ is deterministic and unknown. We denote the number of samples transitions from $(s,a)$ in $\mathcal{D}$ by $N(s,a)$, i.e., $N(s,a)=\sum_{i=1}^N \textbf{1}_{(s_i,a_i)=(s,a)}$ and $\textbf{1}_{X=x}$ is the indicator function.

The goal of offline RL is to find a policy $\pi$  which optimizes the value function $V^\pi_\kp$ based on the offline dataset $\mathcal{D}$. Let $d^{\pi}$ denote the discounted occupancy distribution associated with $\pi$:
d^\pi(s)=(1-\gamma)\sum^\infty_{t=0} \mathbb{P}(S_t=s|S_0\sim\rho, \pi,\kp).
In this paper, we focus on the partial coverage setting and adopt the following definition from [33] to measure the distribution shift between the dataset distribution and desired occupancy measures:
(Single-policy clipped concentrability)
The single-policy clipped concentrability coefficient of a policy $\pi^*$ is defined as

\begin{align}
C^{\pi^*}\triangleq \max_{s,a}\frac{\min\{d^{\pi^*}(s,a), \frac{1}{S} \}}{\mu(s,a)},
\end{align}

where $S\triangleq |\mcs|$ denotes the number of states.

We note another unclipped version of $C^{\pi^*}$ [47, 58] is also commonly used in the literature, and is defined as

\begin{align}
\tilde{C}^{\pi^*}\triangleq \max_{s,a}\frac{d^{{\pi^*}}(s,a)}{\mu(s,a)}.
\end{align}

It is straightforward to verify that $C^{\pi^*} \leq \tilde{C}^{\pi^*}$, and all of our results remain valid if $C^{\pi^*}$ is replaced by $\tilde{C}^{\pi^*}$. A more detailed discussion can be found in [33, 53].

The goal of this paper is to find a policy $\pi$ which minimizes the sub-optimality gap compared to a comparator policy $\pi^*$ under some initial state distribution $\rho$:

§  OFFLINE RL VIA DISTRIBUTIONALLY ROBUST OPTIMIZATION

In this section, we present our DRO-based framework to solve the offline RL problem.

Model-based methods for offline RL typically first estimate the transition kernel using the empirical transition kernel. Due to  the challenges  of distribution shift and insufficient amount of data, there exists uncertainty in the estimate of the transition kernel [33, 69].

In this paper, we directly quantify the uncertainty in the empirical estimate of the transition kernel, and

construct a set of "statistically possible" transition kernels. We then apply the DRO approach and optimize the worst-case performance among these possible models. Note that this essentially leads to a robust MDP problem as we reviewed in <Ref>.

In the following, we will first introduce a straightforward Hoeffding-style uncertainty set construction, where the true transition kernel lies in the uncertainty set with high probability, and present the robust value iteration algorithm to solve the robust MDP problem. We theoretically characterize the bound on the optimality gap, and the sample complexity to achieve an $\epsilon$-optimality gap is $\mathcal{O}((1-\gamma)^{-4}\epsilon^{-2} SC^{\pi^*})$. This matches with the best-known sample complexity for the LCB method using the Hoeffding-style bonus term. We then further design a less conservative Bernstein-style uncertainty set, where the true transition kernel may not necessarily lie in the uncertainty set. We theoretically bound the optimality gap, and show that our approach achieves an improved and near-optimal sample complexity of $\mathcal{O}\left((1-\gamma)^{-3}\epsilon^{-2}\left( SC^{\pi^*}+\frac{1}{\mu_{\min}}\right)\right)$. This sample complexity has the optimal dependence on $1-\gamma$ and $\epsilon$ according to the minimax lower bound [47]. These results demonstrate that the proposed DRO framework can also effectively and efficiently solve the offline RL problem.

We first learn an empirical model of the transition kernel and reward from the dataset as follows.

For any $(s,a)$, if $N(s,a)>0$, set

\begin{align}
\hat{\kp}^a_{s,s'}=\frac{\sum_{i\leq N}\textbf{1}_{(s_i,a_i,s'_i)=(s,a,s')}}{N(s,a)}, \hat{r}(s,a)=r_i(s,a);
\end{align}

And if $N(s,a)=0$, set

\begin{align}
\hat{\kp}^a_{s,s'}=\textbf{1}_{s'=s}, \hat{r}(s,a)=0.
\end{align}

The MDP $\hat{\mathsf{M}}=(\mcs,\mca,\hat{\kp},\hat{r})$ with the empirical transition kernel $\hat{\kp}$ and empirical reward $\hat{r}$ is referred to as the empirical MDP. For unseen state-action pairs $(s,a)$ in the offline dataset, we take a conservative approach and let the estimated $\hat r(s,a)=0$, and set $s$ as an absorbing state if taking action $a$. Then the action value function at $(s,a)$ for the empirical MDP shall be zero, which discourages the choice of action $a$ at state $s$.

For each state-action pair $(s,a)$, we construct an uncertainty set centered at the empirical transition kernel $\hat{\kp}^a_s$, with a radius inversely proportional to the number of samples in the dataset. Specifically, set the uncertainty set as $\hat{\cp}=\bigotimes_{s,a}\hat{\cp}^a_s$ and

\begin{align}\label{eq:uncertaintyset}
\hat{\cp}^a_s=\left\{q\in\Delta(\mcs): \|q-\hat{\kp}^a_s\|\leq  R^a_s \right\},
\end{align}

where $R^a_s$ is the radius of the uncertainty set, and $\|\cdot\|$ denotes the $l_1$-norm.
Then $\hat{\mathcal{M}}=(\mcs,\mca,\hat{\cp},\hat{r})$ is a robust MDP. We want to highlight that the distance  used to construct the uncertainty set in <ref> is not unique, and other distances, e.g., Chi-square, Kullback-Leibler (KL) divergence, can also be used.

In our construction in <ref>, the uncertainty set is $(s,a)$-rectangular, i.e., for different state-action pairs, the corresponding uncertainty sets are independent. With this rectangular structure, the corresponding robust value iteration at each step can be solved in polynomial time [64], and the optimal policy of $(s,a)$-rectangular robust MDP is deterministic [42, 23]. In contrast, the uncertainty set constructed in  previous works e.g.,  [58, 6]  is defined as $\mathcal{T}=\{\kq: \mE_{\mathcal{D}}[\|\hat{\kp}^a_s-\kq^a_s\|^2]\leq \zeta\}$. As shown in [64], solving a robust MDP with such an uncertainty set is NP-hard. Existing approaches are largely based on the heuristic approach of adversarial training, and therefore lack of theoretical guarantee.

We will then utilize tools from robust MDP to find a robust policy for $\hat{\mathcal{M}}$:

\begin{align}\label{eq:robustmdpobj}
\pi_r=\arg\max_\pi \min_{\mathsf P\in\mathcal P} V_{\mathsf P}^\pi(s), \forall s\in\mcs.
\end{align}

The problem in <ref> can be efficiently solved by the robust value iteration algorithm in <Ref> [42, 23]. The algorithm converges with a linear rate since the robust Bellman operator is a $\gamma$-contraction. At each iteration, the term $\sigma_{\hat{\cp}^a_s}(V)$ in Line
3 can be equivalently solved by solving its dual, which is a convex optimization problem:

\begin{align}\label{eq:dual}
\max_{0\leq \mu\leq V} \{\hat{\kp}^a_s(V-\mu)-R_s^a \text{Span}(V-\mu)\},
\end{align}

where $\text{Span}(X)=\max_i X(i)-\min_i X(i)$ is the span semi-norm of vector $X$. The computational complexity of solving <ref> is $S\log(S)$ [23], and leads to a total complexity of $S^2A\log (S)$ per iteration. Note that this computational complexity also matches the complexity  of the VI-LCB approach [33].

INPUT: $\hat{r},\hat{\cp}, V, \mathcal{D}$
[1]
$s \in\mcs$
$V(s)\leftarrow \max_{a}\{ \hat{r}(s,a)+\gamma \sigma_{\hat{\cp}^a_s}(V)\}$
$\pi_r(s)\in \arg\max_{a\in\mca}\{ \hat{r}(s,a)+\gamma \sigma_{\hat{\cp}^a_s}(V)\}\} $

Output: $\pi_r$
Robust Value Iteration [42, 23]

§.§ Hoeffding-style Radius

A remaining question is how shall we choose the radius $R_s^a$. We first present a Hoefdding-style radius choice. Specifically, let
$$R_s^a\triangleq\min\left\{ 2, \sqrt{\frac{\log\frac{SA}{\delta}}{2N(s,a)}}\right\}.$$

Note that the radius is inversely proportional to the number of samples. Fewer samples result in a larger uncertainty set and imply that we should be more conservative in estimating the transition dynamics at this state-action pair.

We then show that with this Hoeffding-style radius, the true transition kernel falls into the uncertainty set with high probability.

With probability at least $1-\delta$, it holds that for any $s,a$,  $\kp^a_s\in\hat{\cp}^a_s$.

Lemma 1 can be proved using the standard concentration argument. This result implies that the real environment $\kp$ falls into the uncertainty set $\hat{\cp}$ with high probability, and hence finding the optimal robust policy of $\hat{\mathcal{M}}$ provides a worst-case performance guarantee. We further present our result of the optimality gap in the following theorem.

Consider an arbitrary deterministic comparator policy $\pi^*$. Then the optimal robust policy $\pi_r$ to $\hat{\mathcal M}$ satisfies that with probability at least $1-2\delta$,

\begin{align}\label{eq:bound1}
V^{\pi^*}_\kp(\rho)-V^{\pi_r}_\kp(\rho)  \leq \frac{1}{(1-\gamma)^2}\frac{16SC^{\pi^*}\log\frac{NS}{\delta}}{N}+\frac{1}{(1-\gamma)^2}\sqrt{\frac{96SC^{\pi^*}\log\frac{SA}{\delta}}{N}}.
\end{align}

To achieve an $\epsilon$-optimality gap, a dataset of size

\begin{align}
N=\mathcal{O}\left((1-\gamma)^{-4}\epsilon^{-2} SC^{\pi^*} \right)
\end{align}

is required for a Hoeffding-style uncertainty model. This sample complexity matches with the best-known sample complexity for  LCB methods with Hoeffding-style  bonus term [47]. However, there is still a gap between this sample complexity and the minimax lower bound in [47] and the best-known sample complexity of LCB-based method [33], which is $\mathcal{O}\left((1-\gamma)^{-3}\epsilon^{-2} SC^{\pi^*}\right) $.

§.§ Bernstein-style Radius

As we can observe from <Ref>, using a Hoeffding-style radius is able to achieve a small optimality gap, however, requires an unnecessarily large sample complexity.

This gap is mainly because the Hoeffding-style radius is overly conservative.
The idea of Hoeffding-style radius can be viewed as distribution based. That is, to construct the uncertainty set $\hat{\cp}$ centered at $\hat{\kp}$ large enough such that the true transition kernel $\kp$ falls into $\hat{\cp}$ with high probability (Lemma <ref>). Therefore, it holds that $V^{\pi_r}_{\hat{\cp}}\leq V^{\pi_r}_\kp$ and the sub-optimality gap can be bounded as

\begin{align}
V^{\pi^*}_\kp-V^{\pi_r}_\kp=\underbrace{V^{\pi^*}_\kp-V^{\pi_r}_{\hat{\cp}}}_{\Delta_1}+\underbrace{V^{\pi_r}_{\hat{\cp}}-V^{\pi_r}_\kp}_{\Delta_2}\leq \Delta_1.
\end{align}

However, $\Delta_2=\min_{q\in\hat{\cp}}\mE_{q}[\sum \gamma^tr_t]-\mE_{\kp}[\sum \gamma^tr_t]$ is in fact the difference between  expectations under two different distributions, and as we will show later, $\kp\in\hat{\cp}$ is not necessary  to bound $\Delta_2$. With this idea in mind, we design a Bernstein-style radius as follows.

With the empirical MDP $\hat{\mathcal{M}}$, we set the
radius as

\begin{align}
R^a_s=\min\left\{2, \frac{\log \frac{N}{\delta}}{N(s,a)}\right\},
\end{align}

and estimated uncertainty sets as
\hat{\cp}^a_s=\left\{ q\in\Delta(\mcs): \|q-\hat{\kp}^a_s\|\leq R^a_s \right\}.
The corresponding robust MDP  $\hat{\mathcal{M}}=(\mcs,\mca, \hat{\cp},\hat{r})$  can be solved by <Ref>.

INPUT: $\hat{r},\hat{\cp}, V,\mathcal{D}$
[1]
$s \in\mcs$
$N(s)\leftarrow \sum^N_{i=1} \textbf{1}_{(s_i)=s}$
$V(s)\leftarrow \max_{a}\{ \hat{r}(s,a)+\gamma \sigma_{\hat{\cp}^a_s}(V)\}$
$\pi_r(s)\in \{\arg\max_{a\in\mca}\{ \hat{r}(s,a)+\gamma \sigma_{\hat{\cp}^a_s}(V)\}\} \cap \{a: N(s,a)>0 \}$
$\pi_r(s)\in \arg\max_{a\in\mca}\{ \hat{r}(s,a)+\gamma \sigma_{\hat{\cp}^a_s}(V)\}\} $

Output: $\pi_r$
Robust Value Iteration

We note that the output policy of <Ref> is slightly modified from the one of <Ref>.
Specifically, the output policy $\pi_r$ in Algorithm <ref> is set to be the greedy policy satisfying $N(s,a)>0$ if $N(s)>0$. The existence of such a policy is proved in Lemma <ref> in the appendix. This is to guarantee that when there is a tie of taking greedy actions, we will take an action that has appeared in the pre-collected dataset $\mathcal D$.

We then characterize the optimality gap of  <Ref> in the following theorem.

Consider an arbitrary deterministic comparator policy $\pi^*$. The output policy $\pi_r$ of Algorithm <ref> satisfies that with probability at least $1-4\delta$,

\begin{align}\label{eq:bound}
V^{\pi^*}_\kp(\rho)-V^{\pi_r}_\kp(\rho)&\leq \frac{SK_1C^{\pi^*}\log\frac{NS}{\delta}}{(1-\gamma)^2N} +\sqrt{\frac{K_2SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)^3N}}+\frac{K_3\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)^2N\mu_{\min}}\nn\\
&\quad+ \sqrt{\frac{K_4\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)^3N\mu_{\min}}},
\end{align}

where $\mu_{\min}\triangleq \min\{\mu(s,a): (s,a)\in\mcs\times\mca, \mu(s,a)>0\}$ is the smallest positive entry of the distribution $\mu$, and $K_1,K_2,K_3,K_4$ are some universal constants.

Compared to the Hoeffding-style radius, the Bernstein-style radius has a smaller radius of uncertainty set. In this case, the real transition kernel $\kp$ may not belong to $\hat{\cp}$, and the analysis in <Ref> cannot be applied.

For any $\epsilon\in\left(0,\frac{1}{1-\gamma}\right]$, to achieve an $\epsilon$-optimality gap, a dataset of size

\begin{align}
N=\mathcal{O}\left(\frac{1}{(1-\gamma)^{3}\epsilon^{2}}\left(  SC^{\pi^*} + \frac{1}{\mu_{\min}}\right)\right)
\end{align}

is required. Our result obtains the optimal dependence on $(1-\gamma)$ and $\epsilon$ according to the minimax lower bound in [47]. Denote the minimal positive entry of $\mu$ by $\mu(s_\mu,a_\mu)=\mu_{\min}$. If $d^{\pi^*}(s_\mu,a_\mu)\geq \frac{1}{S}$, then our sample complexity is $N=\mathcal{O}\left(\frac{ SC^{\pi^*} }{(1-\gamma)^{3}\epsilon^{2}}\right)$, which exactly matches minimax lower bound in [47].

In many existing studies, enormous burn-in samples are needed in order to achieve their claimed sample optimality, e.g., $H^9SC^{\pi^*}$ in [67], $\frac{S^3A^2}{(1-\gamma)^4}$ in [21], and $\frac{SC^{\pi^*}}{(1-\gamma)^5}$ in [69], whereas our results require no such burn-in cost. Moreover, our result holds for the full $\epsilon$-range, i.e., any $\epsilon\in\left(0,\frac{1}{1-\gamma}\right]$. In contrast, many previous works only obtain guarantees for a limited $\epsilon$-range, e.g., [69, 67, 71].

§ CONCLUSION

In this paper, we revisit the problem of offline reinforcement learning from the angle of distributional robustness. We develop a DRO-based framework to solve offline reinforcement learning. Our approach directly incorporates conservatism in estimating the transition dynamics instead of penalizing the reward of less-visited state-action pairs. Our algorithms are based on the robust dynamic programming approach, which is computationally efficient.
We focus on the challenging partial coverage setting, and develop two uncertainty sets: the Hoeffding-style and  the less conservative Bernstein-style. For the Hoeffding-style uncertainty set, we
theoretically characterize its sample complexity, and show it matches with the best one of the LCB-based approaches using the Hoeffding-style bonus term. For the Bernstein-style uncertainty set, we show its sample complexity matches with the minimax lower bound in terms of the dependence on $(1-\gamma)$ and $\epsilon$.
Our results provide an alternative DRO-based framework to efficiently and effectively solve the problem of offline reinforcement learning as the LCB-based approaches.

Limitations: Our method is a model-based approach for the tabular setting. It is of future interest to study the offline RL together with function approximation and in the model-free setting.

Negative societal impact: To the best of the authors’ knowledge, this study does not have any potential negative impact on society.

[1]
A. Agarwal, S. Kakade, and L. F. Yang.
Model-based reinforcement learning with a generative model is minimax
In Conference on Learning Theory, pages 67–83. PMLR, 2020.

[2]
R. Agarwal, D. Schuurmans, and M. Norouzi.
An optimistic perspective on offline reinforcement learning.
In International Conference on Machine Learning, pages
104–114. PMLR, 2020.

[3]
A. Antos, C. Szepesvári, and R. Munos.
Fitted Q-iteration in continuous action-space MDPs.
In Proc. Advances in Neural Information Processing Systems
(NIPS), volume 20, pages 9–16, 2007.

[4]
T. Archibald, K. McKinnon, and L. Thomas.
On the generation of Markov decision processes.
Journal of the Operational Research Society, 46(3):354–361,

[5]
J. A. Bagnell, A. Y. Ng, and J. G. Schneider.
Solving uncertain Markov decision processes.
Citeseer, 09 2001.

[6]
M. Bhardwaj, T. Xie, B. Boots, N. Jiang, and C.-A. Cheng.
Adversarial model for offline reinforcement learning.
arXiv preprint arXiv:2302.11048, 2023.

[7]
J. Buckman, C. Gelada, and M. G. Bellemare.
The importance of pessimism in fixed-dataset policy optimization.
arXiv preprint arXiv:2009.06799, 2020.

[8]
J. D. Chang, M. Uehara, D. Sreenivas, R. Kidambi, and W. Sun.
Mitigating covariate shift in imitation learning via offline data
without great coverage.
arXiv preprint arXiv:2106.03207, 2021.

[9]
J. Chen and N. Jiang.
Information-theoretic considerations in batch reinforcement learning.
In International Conference on Machine Learning, pages
1042–1051. PMLR, 2019.

[10]
M. Chen, Y. Li, E. Wang, Z. Yang, Z. Wang, and T. Zhao.
Pessimism meets invariance: Provably efficient offline mean-field
multi-agent RL.
Advances in Neural Information Processing Systems, 34, 2021.

[11]
C.-A. Cheng, T. Xie, N. Jiang, and A. Agarwal.
Adversarially trained actor-critic for offline reinforcement
In International Conference on Machine Learning, pages
3852–3878. PMLR, 2022.

[12]
Q. Cui and S. S. Du.
When is offline two-player zero-sum Markov game solvable?
arXiv preprint arXiv:2201.03522, 2022.

[13]
Y. Duan, Z. Jia, and M. Wang.
Minimax-optimal off-policy evaluation with linear function
In Proc. International Conference on Machine Learning (ICML),
pages 2701–2709. PMLR, 2020.

[14]
A. M. Farahmand, R. Munos, and C. Szepesvári.
Error propagation for approximate policy and value iteration.
In Advances in Neural Information Processing Systems, 2010.

[15]
J. Fu, A. Kumar, O. Nachum, G. Tucker, and S. Levine.
D4RL: Datasets for deep data-driven reinforcement learning.
arXiv preprint arXiv:2004.07219, 2020.

[16]
S. Fujimoto, E. Conti, M. Ghavamzadeh, and J. Pineau.
Benchmarking batch deep reinforcement learning algorithms.
arXiv preprint arXiv:1910.01708, 2019.

[17]
S. Fujimoto, D. Meger, and D. Precup.
Off-policy deep reinforcement learning without exploration.
In International Conference on Machine Learning, pages
2052–2062. PMLR, 2019.

[18]
S. K. S. Ghasemipour, D. Schuurmans, and S. S. Gu.
EMaQ: Expected-max Q-learning operator for simple yet effective
offline and online RL.
arXiv preprint arXiv:2007.11091, 2020.

[19]
C. Gulcehre, Z. Wang, A. Novikov, T. L. Paine, S. G. Colmenarejo, K. Zolna,
R. Agarwal, J. Merel, D. Mankowitz, C. Paduraru, et al.
RL unplugged: Benchmarks for offline reinforcement learning.
arXiv preprint arXiv:2006.13888, 2020.

[20]
K. Guo, S. Yunfeng, and Y. Geng.
Model-based offline reinforcement learning with pessimism-modulated
dynamics belief.
Advances in Neural Information Processing Systems, 35:449–461,

[21]
J. He, D. Zhou, and Q. Gu.
Nearly minimax optimal reinforcement learning for discounted MDPs.
Advances in Neural Information Processing Systems,
34:22288–22300, 2021.

[22]
M. Hong, Y. Wu, and Y. Xu.
Pessimistic model-based actor-critic for offline reinforcement
learning: Theory and algorithms, 2023.

[23]
G. N. Iyengar.
Robust dynamic programming.
Mathematics of Operations Research, 30(2):257–280, 2005.

[24]
N. Jaques, A. Ghandeharioun, J. H. Shen, C. Ferguson, A. Lapedriza, N. Jones,
S. Gu, and R. Picard.
Way off-policy batch deep reinforcement learning of implicit human
preferences in dialog.
arXiv preprint arXiv:1907.00456, 2019.

[25]
N. Jiang.
On value functions and the agent-environment boundary.
arXiv preprint arXiv:1905.13341, 2019.

[26]
Y. Jin, Z. Yang, and Z. Wang.
Is pessimism provably efficient for offline RL?
In International Conference on Machine Learning, pages
5084–5096, 2021.

[27]
R. Kidambi, A. Rajeswaran, P. Netrapalli, and T. Joachims.
MOReL: Model-based offline reinforcement learning.
Advances in neural information processing systems,
33:21810–21823, 2020.

[28]
B. R. Kiran, I. Sobh, V. Talpaert, P. Mannion, A. A. Al Sallab, S. Yogamani,
and P. Pérez.
Deep reinforcement learning for autonomous driving: A survey.
IEEE Transactions on Intelligent Transportation Systems,
23(6):4909–4926, 2021.

[29]
A. Kumar, J. Fu, G. Tucker, and S. Levine.
Stabilizing off-policy Q-learning via bootstrapping error
arXiv preprint arXiv:1906.00949, 2019.

[30]
A. Kumar, A. Zhou, G. Tucker, and S. Levine.
Conservative Q-learning for offline reinforcement learning.
arXiv preprint arXiv:2006.04779, 2020.

[31]
S. Lange, T. Gabel, and M. Riedmiller.
Batch reinforcement learning.
In Reinforcement learning, pages 45–73. Springer, 2012.

[32]
S. Levine, A. Kumar, G. Tucker, and J. Fu.
Offline reinforcement learning: Tutorial, review, and perspectives
on open problems.
arXiv preprint arXiv:2005.01643, 2020.

[33]
G. Li, L. Shi, Y. Chen, Y. Chi, and Y. Wei.
Settling the sample complexity of model-based offline reinforcement
in preparation, 2022.

[34]
P. Liao, Z. Qi, and S. Murphy.
Batch policy learning in average reward Markov decision processes.
arXiv preprint arXiv:2007.11771, 2020.

[35]
B. Liu, Q. Cai, Z. Yang, and Z. Wang.
Neural trust region/proximal policy optimization attains globally
optimal policy.
In Proc. Advances in Neural Information Processing Systems
(NeurIPS), 2019.

[36]
Y. Liu, A. Swaminathan, A. Agarwal, and E. Brunskill.
Provably good batch reinforcement learning without great exploration.
arXiv preprint arXiv:2007.08202, 2020.

[37]
Z. Liu, Q. Bai, J. Blanchet, P. Dong, W. Xu, Z. Zhou, and Z. Zhou.
Distributionally robust Q-learning.
In International Conference on Machine Learning, pages
13623–13643. PMLR, 2022.

[38]
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare,
A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, et al.
Human-level control through deep reinforcement learning.
nature, 518(7540):529–533, 2015.

[39]
R. Munos.
Performance bounds in $\ell_p$-norm for approximate value iteration.
SIAM journal on control and optimization, 46(2):541–561, 2007.

[40]
R. Munos and C. Szepesvari.
Finite-time bounds for fitted value iteration.
Journal of Machine Learning Research, 9:815–857, May 2008.

[41]
O. Nachum, B. Dai, I. Kostrikov, Y. Chow, L. Li, and D. Schuurmans.
AlgaeDICE: Policy gradient from arbitrary experience.
arXiv preprint arXiv:1912.02074, 2019.

[42]
A. Nilim and L. El Ghaoui.
Robustness in Markov decision problems with uncertain transition
In Proc. Advances in Neural Information Processing Systems
(NIPS), pages 839–846, 2004.

[43]
K. Panaganti and D. Kalathil.
Sample complexity of robust reinforcement learning with a generative
arXiv preprint arXiv:2112.01506, 2021.

[44]
K. Panaganti and D. Kalathil.
Sample complexity of robust reinforcement learning with a generative
In International Conference on Artificial Intelligence and
Statistics, pages 9582–9602. PMLR, 2022.

[45]
K. Panaganti, Z. Xu, D. Kalathil, and M. Ghavamzadeh.
Robust reinforcement learning using offline data.
arXiv preprint arXiv:2208.05129, 2022.

[46]
X. B. Peng, A. Kumar, G. Zhang, and S. Levine.
Advantage-weighted regression: Simple and scalable off-policy
reinforcement learning.
arXiv preprint arXiv:1910.00177, 2019.

[47]
P. Rashidinejad, B. Zhu, C. Ma, J. Jiao, and S. Russell.
Bridging offline reinforcement learning and imitation learning: A
tale of pessimism.
Advances in Neural Information Processing Systems,
34:11702–11716, 2021.

[48]
M. Rigter, B. Lacerda, and N. Hawes.
Rambo-rl: Robust adversarial model-based offline reinforcement
arXiv preprint arXiv:2204.12581, 2022.

[49]
S. Ross and J. A. Bagnell.
Agnostic system identification for model-based reinforcement
arXiv preprint arXiv:1203.1007, 2012.

[50]
A. Roy, H. Xu, and S. Pokutta.
Reinforcement learning under model mismatch.
In Proc. Advances in Neural Information Processing Systems
(NIPS), pages 3046–3055, 2017.

[51]
J. K. Satia and R. E. Lave Jr.
Markovian decision processes with uncertain transition
Operations Research, 21(3):728–740, 1973.

[52]
B. Scherrer.
Approximate policy iteration schemes: A comparison.
In Proc. International Conference on Machine Learning (ICML),
pages 1314–1322, 2014.

[53]
L. Shi and Y. Chi.
Distributionally robust model-based offline reinforcement learning
with near-optimal sample complexity.
arXiv preprint arXiv:2208.05767, 2022.

[54]
L. Shi, G. Li, Y. Wei, Y. Chen, and Y. Chi.
Pessimistic Q-learning for offline reinforcement learning: Towards
optimal sample complexity.
International Conference on Machine Learning, pages
19967–20025, 2022.

[55]
N. Y. Siegel, J. T. Springenberg, F. Berkenkamp, A. Abdolmaleki, M. Neunert,
T. Lampe, R. Hafner, and M. Riedmiller.
Keep doing what worked: Behavioral modelling priors for offline
reinforcement learning.
arXiv preprint arXiv:2002.08396, 2020.

[56]
D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche,
J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, et al.
Mastering the game of Go with deep neural networks and tree search.
nature, 529(7587):484–489, 2016.

[57]
M. Uehara, J. Huang, and N. Jiang.
Minimax weight and Q-function learning for off-policy evaluation.
In Proc. International Conference on Machine Learning (ICML),
pages 9659–9668. PMLR, 2020.

[58]
M. Uehara and W. Sun.
Pessimistic model-based offline reinforcement learning under partial
arXiv preprint arXiv:2107.06226, 2021.

[59]
R. Vershynin.
High-dimensional probability: An introduction with applications
in data science, volume 47.
Cambridge university press, 2018.

[60]
L. Wang, Q. Cai, Z. Yang, and Z. Wang.
Neural policy gradient methods: Global optimality and rates of
In International Conference on Learning Representations, 2019.

[61]
Y. Wang and S. Zou.
Online robust reinforcement learning with model uncertainty.
In Proc. Advances in Neural Information Processing Systems
(NeurIPS), volume 34, pages 7193–7206, 2021.

[62]
Y. Wang and S. Zou.
Policy gradient method for robust reinforcement learning.
In Proc. International Conference on Machine Learning (ICML),
volume 162, pages 23484–23526. PMLR, 2022.

[63]
Z. Wang, A. Novikov, K. Zolna, J. S. Merel, J. T. Springenberg, S. E. Reed,
B. Shahriari, N. Siegel, C. Gulcehre, N. Heess, et al.
Critic regularized regression.
Advances in Neural Information Processing Systems, 33, 2020.

[64]
W. Wiesemann, D. Kuhn, and B. Rustem.
Robust Markov decision processes.
Mathematics of Operations Research, 38(1):153–183, 2013.

[65]
Y. Wu, G. Tucker, and O. Nachum.
Behavior regularized offline reinforcement learning.
arXiv preprint arXiv:1911.11361, 2019.

[66]
T. Xie and N. Jiang.
Batch value-function approximation with only realizability.
arXiv preprint arXiv:2008.04990, 2020.

[67]
T. Xie, N. Jiang, H. Wang, C. Xiong, and Y. Bai.
Policy finetuning: Bridging sample-efficient offline and online
reinforcement learning.
Advances in neural information processing systems,
34:27395–27407, 2021.

[68]
Z. Xu, K. Panaganti, and D. Kalathil.
Improved sample complexity bounds for distributionally robust
reinforcement learning.
In International Conference on Artificial Intelligence and
Statistics, pages 9728–9754. PMLR, 2023.

[69]
Y. Yan, G. Li, Y. Chen, and J. Fan.
The efficacy of pessimism in asynchronous Q-learning.
arXiv preprint arXiv:2203.07368, 2022.

[70]
W. Yang, L. Zhang, and Z. Zhang.
Towards theoretical understandings of robust Markov decision
processes: Sample complexity and asymptotics.
arXiv preprint arXiv:2105.03863, 2021.

[71]
M. Yin and Y.-X. Wang.
Towards instance-optimal offline reinforcement learning with
Advances in neural information processing systems, 34, 2021.

[72]
C. Yu, J. Liu, S. Nemati, and G. Yin.
Reinforcement learning in healthcare: A survey.
ACM Computing Surveys (CSUR), 55(1):1–36, 2021.

[73]
T. Yu, A. Kumar, R. Rafailov, A. Rajeswaran, S. Levine, and C. Finn.
COMBO: Conservative offline model-based policy optimization.
arXiv preprint arXiv:2102.08363, 2021.

[74]
T. Yu, G. Thomas, L. Yu, S. Ermon, J. Y. Zou, S. Levine, C. Finn, and T. Ma.
MOPO: Model-based offline policy optimization.
Advances in Neural Information Processing Systems,
33:14129–14142, 2020.

[75]
A. Zanette, M. J. Wainwright, and E. Brunskill.
Provable benefits of actor-critic methods for offline reinforcement
Advances in neural information processing systems, 34, 2021.

[76]
J. Zhang, A. Koppel, A. S. Bedi, C. Szepesvari, and M. Wang.
Variational policy gradient method for reinforcement learning with
general utilities.
In Proc. Advances in Neural Information Processing Systems
(NeurIPS), volume 33, pages 4572–4583, 2020.

[77]
J. Zhang, J. Lyu, X. Ma, J. Yan, J. Yang, L. Wan, and X. Li.
Uncertainty-driven trajectory truncation for model-based offline
reinforcement learning.
arXiv preprint arXiv:2304.04660, 2023.

[78]
S. Zhang, B. Liu, and S. Whiteson.
GradientDICE: Rethinking generalized offline estimation of
stationary values.
arXiv preprint arXiv:2001.11113, 2020.

[79]
H. Zhong, W. Xiong, J. Tan, L. Wang, T. Zhang, Z. Wang, and Z. Yang.
Pessimistic minimax value iteration: Provably efficient equilibrium
learning from offline datasets.
arXiv preprint arXiv:2202.07511, 2022.

§ EXPERIMENTS

In this section, we numerically verify that our DRO framework can efficiently solve offline reinforcement learning.

§.§ Garnet Problems

We adapt our DRO framework under a Garnet problem $\mathcal{G}(30,20)$ [4]. There are $30$ states and $20$ actions. The transition kernel $\kp=\{ \kp^a_s,s\in\mcs,a\in\mca \}$ is randomly generated by a normal distribution: $\kp^a_s \sim \mathcal{N}(\omega^a_s,\sigma^a_s)$ and then normalized, and the reward function $r(s,a)\sim \mathcal{N}(\nu^a_s,\psi^a_s)$, where $\omega^a_s,\sigma^a_s,\nu^a_s,\psi^a_s \sim \textbf{Uniform}[0,100]$.

We consider datasets satisfying both global coverage and partial coverage, specifically, in <ref> we generate an offline dataset with uniform distribution $\mu(s,a)=\frac{1}{SA}$, and in <ref>, the dataset is generated according to $\mu(s,a)=\frac{1}{2}\textbf{1}_{a=\pi^*(s)}+\frac{1}{2}\textbf{1}_{a=\eta}$, where $\eta$ is an action randomly chosen from the action space $\mca$.

At each time step, we generate an offline dataset and deploy our DRO framework on it. We also use the LCB approach [47, 33] and non-robust model-based dynamic programming [1] as the baselines. We run the algorithms independently 10 times and plot the average value of the sub-optimality gap over all 10 trajectories. We also plot the 95th and 5th percentiles of the 10 curves as the upper and lower envelopes of the curves. It can be seen from the results that both our DRO approach and LCB find the optimal policy and obtain a small sub-optimality gap. To compare, the non-robust DP approaches can also find the optimal policy, but with a much larger amount of data.

[Global Coverage]

[Partial Coverage]

Garnel problem  $\mathcal{G}(30,20)$.

§ NOTATIONS

We first introduce some notations that are used in our proofs.

We denote the numbers of states and actions by $S,A$, i.e., $|\mcs|=S$, $|\mca|=A$.

For a transition kernel $\kp$ and a policy $\pi$, $\kp^\pi$ denotes the transition matrix induced by them, i.e., $\kp^\pi(s)=\sum_a \pi(a|s)\kp^{a}_s\in \mathbb{R}^{S}$.

For any vector $V\in\mathbb{R}^S$, $V\circ V \in\mathbb{R}^S$ denotes the entry-wise multiplication, i.e., $V\circ V (s)=V(s)*V(s)$. For a distribution $q\in\Delta(\mcs)$, it is straightforward to verify that the variation of $V$ w.r.t. $q$ can be rewritten as $\var_q(V)=q(V\circ V)-(qV)^2$.

§ A STRAIGHTFORWARD ANALYSIS: HOEFFDING'S INEQUALITY

With probability at least $1-\delta$, it holds that for any $s,a$,  $\kp^a_s\in\hat{\cp}^a_s$.

If $2<\sqrt{\frac{\log\frac{SA}{\delta}}{2N(s,a)}}$ (including the case $N(s,a)=0$), the statement holds naturally due to the fact $\|p-q\|\leq 2$ for any $p,q\in\Delta(\mcs)$.

If $2\geq \sqrt{\frac{\log\frac{SA}{\delta}}{2N(s,a)}}$, first by Hoeffding's inequality [37], we have that

\begin{align}
\mathbb{P}(\|\hat{\kp}^a_s-\kp^a_s \|\geq k) \leq \textbf{exp}\left( -2N(s,a){k^2} \right).
\end{align}

Plugging in $k=\sqrt{\frac{\log\frac{SA}{\delta}}{2N(s,a)}}$, we have that

\begin{align}
\mathbb{P}\left(\|\hat{\kp}^a_s-\kp^a_s \|\geq \sqrt{\frac{\log\frac{SA}{\delta}}{2N(s,a)}}\right) &\leq \textbf{exp}\left( -2N(s,a) {\frac{\log\frac{SA}{\delta}}{2N(s,a)}} \right) = \frac{\delta}{SA},
\end{align}

which indicates the probability of $\kp^a_s\in\hat{\cp}^a_s$ for any $(s,a)$-pair is larger than $1-\frac{\delta}{SA}$. Hence the probability of $\kp^a_s\in\hat{\cp}^a_s$ holding simultaneously for any $(s,a)$-pair is at least $1-\delta$, which completes the proof.

(Restatement of Thm <ref>)
With probability at least $1-2\delta$, it holds that

\begin{align}
V^{\pi^*}_\kp(\rho)-V^{\pi_r}_\kp(\rho)  \leq \frac{2}{(1-\gamma)^2}\frac{8SC^{\pi^*}\log\frac{NS}{\delta}}{N}+\frac{2}{(1-\gamma)^2}\sqrt{\frac{24SC^{\pi^*}\log\frac{SA}{\delta}}{N}},
\end{align}

To obtain an $\epsilon$-optimal policy, a dataset of size

\begin{align}
N=\mathcal{O}\left(\frac{SC^{\pi^*}}{(1-\gamma)^4\epsilon^2} \right)
\end{align}

is required.

In the following proof, we only focus on the case when

\begin{align}\label{eq:N large1}
\end{align}

Otherwise, (<ref>) follows directly from the trivial bound $V^{\pi^*}_\kp(\rho)-V^{\pi_r}_\kp(\rho)\leq \frac{1}{1-\gamma}$.

According to <Ref>, with probability at least $1-\delta$, $\kp\in\hat{\cp}$. Moreover, due to the fact $r(s,a)\geq \hat{r}(s,a)$, hence

\begin{align}
V^\pi_\kp(s)\geq V^\pi_{\hat{r},\kp}(s) \geq V^\pi_{\hat{r},\hat{\cp}}(s)=V^\pi_{\hat{\cp}}(s)
\end{align}

for any $\pi$ and $s\in\mcs$, where $V^\pi_{\hat{r},\kp}$ denotes the value function w.r.t. $\kp$ and reward $\hat{r}$. Thus  $V^\pi_\kp\geq V^\pi_{\hat{\cp}}$ for any policy $\pi$.

\begin{align}\label{eq:3}
&\leq  V^{\pi^*}_\kp(s)-V^{\pi_r}_{\hat{\cp}}(s)\nn\\
&= r(s,\pi^*(s))+\gamma \kp^{\pi^*(s)}_s V^{\pi^*}_\kp- V^{\pi_r}_{\hat{\cp}}(s)\nn\\
&\overset{(a)}{\leq }r(s,\pi^*(s))-\hat{r}(s,\pi^*(s))+\gamma \kp^{\pi^*(s)}_s V^{\pi^*}_\kp-\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})\nn\\
&=r(s,\pi^*(s))-\hat{r}(s,\pi^*(s))+\gamma \kp^{\pi^*(s)}_s V^{\pi^*}_\kp-\gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}+\gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})\nn\\
&=r(s,\pi^*(s))-\hat{r}(s,\pi^*(s))+\gamma \kp^{\pi^*(s)}_s (V^{\pi^*}_\kp-V^{\pi_r}_{\hat{\cp}})+ \gamma (\kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}}))\nn\\
&\triangleq \gamma \kp^{\pi^*(s)}_s (V^{\pi^*}_\kp-V^{\pi_r}_{\hat{\cp}})+  b^*(V^{\pi_r}_{\hat{\cp}}),
%&\leq \frac{1}{1-\gamma}\left\langle d^{\pi^*}, b^*(V^{\pi_r}_{\hat{\cp}}) \right\rangle,
\end{align}

where $(a)$ is from $V^{\pi_r}_{\hat{\cp}}(s)=\max_a Q^{\pi_r}_{\hat{\cp}}(s,a)\geq Q^{\pi_r}_{\hat{\cp}}(s,\pi^*(s))=\hat{r}(s,\pi^*(s))+\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})$, and $b^*(V)(s)\triangleq r(s,\pi^*(s))-\hat{r}(s,\pi^*(s))+ \gamma\kp^{\pi^*(s)}_s V -\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V)$.

Recursively applying this inequality further implies

\begin{align}
V^{\pi^*}_\kp(\rho)-V^{\pi_r}_\kp(\rho)\leq \frac{1}{1-\gamma}\left\langle d^{\pi^*}, b^*(V^{\pi_r}_{\hat{\cp}}) \right\rangle,
\end{align}

where $d^{\pi^*}(\cdot)=(1-\gamma)\sum^\infty_{t=0} \mathbb{P}(S_t=\cdot|S_0\sim\rho,\pi^*,\kp)$ is the discounted visitation distribution induced by $\pi^*$ and $\kp$.

To bound the term in (<ref>), we introduce the following notations.

\begin{align}
\mcs_{s}&\triangleq \left\{s: N\mu(s,\pi^*(s))\leq 8\log\frac{NS}{\delta} \right\},\\
\mcs_{l}&\triangleq \left\{s: N\mu(s,\pi^*(s))> 8\log\frac{NS}{\delta} \right\}.
\end{align}

For $s\in\mcs_s$, from (<ref>), we have that

\begin{align}
\min \left\{d^{\pi^*}(s), \frac{1}{S}\right\}\leq C^{\pi^*}\mu(s,\pi^*(s))\leq \frac{8C^{\pi^*}\log\frac{NS}{\delta}}{N}<\frac{1}{S},
\end{align}

which further implies that $d^{\pi^*}(s)\leq \frac{8C^{\pi^*}\log\frac{NS}{\delta}}{N}$. Hence

\begin{align}\label{eq:6}
\sum_{s\in\mcs_s} d^{\pi^*}(s)b^*(V^{\pi_r}_{\hat{\cp}})(s)\leq \frac{2}{1-\gamma}\frac{8SC^{\pi^*}\log\frac{NS}{\delta}}{N},
\end{align}

which is due to $b^*(V)(s)\triangleq r(s,\pi^*(s))-\hat{r}(s,\pi^*(s))+ \gamma\kp^{\pi^*(s)}_s V -\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V)\leq 1+ \frac{\gamma}{1-\gamma}\leq \frac{2}{1-\gamma}$.

We then consider $s\in\mcs_l$. From the definition, $N\mu(s,\pi^*(s))>8\log\frac{NS}{\delta}$. According to <Ref>, with probability $1-\delta$,

\begin{align}\label{eq:7}
\max \{12N(s,\pi^*(s)),8\log\frac{NS}{\delta} \}\geq N\mu(s,\pi^*(s))>8\log\frac{NS}{\delta},
\end{align}

hence $\max \{12N(s,\pi^*(s)),8\log\frac{NS}{\delta} \}=12N(s,\pi^*(s))$ and $N(s,\pi^*(s))\geq \frac{2}{3}\log\frac{NS}{\delta}>0.$ This hence implies that for any $s\in\mcs_l$, $N(s,\pi^*(s))>0$ and $\hat{r}(s,\pi^*(s))=r(s,\pi^*(s))$. Thus

\begin{align}\label{eq:9}
|b^*(V^{\pi_r}_{\hat{\cp}})(s)|&=\gamma|\kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\sigma_{\hat{\cp}^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}}) |\nn\\
%&=|\kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}-\hat{\kp}^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}+\hat{\kp}^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\sigma_{\hat{\cp}^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}}) |\nn\\
%&\leq \|\kp^{\pi^*(s)}_s-\hat{\kp}^{\pi^*(s)}_s\| \|V^{\pi_r}_{\hat{\cp}}\|+ |\hat{\kp}^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\sigma_{\hat{\cp}^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}}) |\nn\\
&\leq \|\kp^{\pi^*(s)}_{s}-\kq^{\pi^*(s)}_{s} \|_1\|V^{\pi_r}_{\hat{\cp}} \|_\infty\nn\\
&\leq \frac{2}{1-\gamma} \min\left\{ 2, \sqrt{\frac{\log\frac{SA}{\delta}}{2N(s,\pi^*(s))}}\right\}\nn\\
&\leq \frac{1}{1-\gamma}  \sqrt{\frac{2\log\frac{SA}{\delta}}{N(s,\pi^*(s))}}.
\end{align}

Moreover, from (<ref>),

\begin{align}\label{eq:10}
\frac{1}{N(s,\pi^*(s))}\leq \frac{12}{N\mu(s,\pi^*(s))}\leq \frac{12C^{\pi^*}}{N\min\{d^{\pi^*}(s),\frac{1}{S}\}} \leq \frac{12C^{\pi^*}}{N}\left( \frac{1}{d^{\pi^*}(s)}+S\right).
\end{align}

Combining with (<ref>) further implies

\begin{align}
|b^*(V^{\pi_r}_{\hat{\cp}})(s)|&\leq \frac{1}{1-\gamma}\sqrt{2\log\frac{SA}{\delta}}\sqrt{\frac{12C^{\pi^*}}{N}\left(\frac{1}{d^{\pi^*}(s)},S\right)}\nn\\
&\leq \frac{1}{1-\gamma}\sqrt{2\log\frac{SA}{\delta}}\sqrt{\frac{12C^{\pi^*}}{N}\frac{1}{d^{\pi^*}(s)}}+\frac{1}{1-\gamma}\sqrt{2\log\frac{SA}{\delta}}\sqrt{\frac{12C^{\pi^*}}{N}S}.
\end{align}

\begin{align}\label{eq:14}
\sum_{s\in\mcs_l} d^{\pi^*}(s)b^*(V^{\pi_r}_{\hat{\cp}})(s)&\leq \frac{1}{1-\gamma}\sqrt{\frac{24C^{\pi^*}\log\frac{SA}{\delta}}{N}}\sum_{s}\sqrt{d^{\pi^*}(s)}+ \frac{1}{1-\gamma}\sqrt{\frac{24SC^{\pi^*}\log\frac{SA}{\delta}}{N}}\nn\\
&\leq  \frac{1}{1-\gamma}\sqrt{\frac{24SC^{\pi^*}\log\frac{2}{\delta}}{N}}+ \frac{1}{1-\gamma}\sqrt{\frac{24SC^{\pi^*}\log\frac{SA}{\delta}}{N}}\nn\\
\end{align}

Thus combining (<ref>) and (<ref>) implies

\begin{align}
&\leq \frac{1}{1-\gamma}\left\langle d^{\pi^*}, b^*(V^{\pi_r}_{\hat{\cp}}) \right\rangle \nn\\
&\leq \frac{2}{(1-\gamma)^2}\frac{8SC^{\pi^*}\log\frac{NS}{\delta}}{N}+\frac{2}{(1-\gamma)^2}\sqrt{\frac{24SC^{\pi^*}\log\frac{SA}{\delta}}{N}},
\end{align}

which completes the proof.

§ A REFINED ANALYSIS: BERNSTEIN'S INEQUALITY

In this section, we provide a refined analysis of the sub-optimality gap using Bernstein's Inequality.
(Restatement of Thm <ref>)
Consider the robust MDP $\hat{\mathcal{M}}$, there exist an optimal policy $\pi_r$ such that there exists some universal constants $K_1,K_2,K_3,K_4$, such that with probability at least $1-4\delta$, it holds that

\begin{align}
&\leq \frac{SK_1C^{\pi^*}\log\frac{NS}{\delta}}{(1-\gamma)^2N} +\sqrt{\frac{K_2SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)^3N}}+\frac{K_3\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)^2N\mu_{\min}}+ \sqrt{\frac{K_4\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)^3N\mu_{\min}}},
\end{align}

where $K_1=2c_2+80c_1$, $K_2=442368$, $K_3=16c_5+2c_4$ and $K_4=32c_5$.

We first have that

\begin{align}
\end{align}

In the following proof, we only focus on the case when

\begin{align}\label{eq:N large}
\end{align}

Otherwise, (<ref>) follows directly from the trivial bound $V^{\pi^*}_\kp(\rho)-V^{\pi_r}_\kp(\rho)\leq \frac{1}{1-\gamma}$.

We note that Lemma 8 of [53] states that under (<ref>), with probability $1-\delta$, for any $(s,a)$ pair,

\begin{align}\label{eq: N(s,a)>0}
N(s,a)\geq \frac{N\mu(s,a)}{8\log\frac{4SA}{\delta}}.
\end{align}

This moreover implies that  with probability $1-\delta$,  if $\mu(s,a)>0$, then $N(s,a)>0$.  We hence focus on the case when this event holds.

The remaining proof can be completed by combining the following two lemmas.

With probability at least $1-2\delta$, it holds that

\begin{align}
\rho^\top\Delta_1\leq  {\frac{2c_2SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)^2N}}+\frac{80Sc_1C^{\pi^*}\log\frac{NS}{\delta}}{(1-\gamma)^2N} +\frac{48}{\gamma}\sqrt{\frac{48SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)^3N}}.
\end{align}

We first define the following set:

\begin{align}
\mcs_0\triangleq \{ s: d^{\pi^*}(s)=0\}.
\end{align}

And for $s\notin \mcs_0$, it holds that $d^{\pi^*}(s)>0$.

We first consider $s\notin \mcs_0$. Due to the fact $d^{\pi^*}(s)>0$,
hence $d^{\pi^*}(s,\pi^*(s))=d^{\pi^*}(s)\pi^*(\pi^*(s)|s)>0$. Thus it implies that $\mu(s,\pi^*(s))>0$, and (<ref>) further implies $N(s,\pi^*(s))>0$ and $\hat{r}(s,\pi^*(s))=r(s,\pi^*(s))$. Hence we have that

\begin{align}\label{eq:27}
V^{\pi^*}_\kp(s)-V^{\pi_r}_{\hat{\cp}}(s)&= r(s,\pi^*(s))+\gamma \kp^{\pi^*(s)}_s V^{\pi^*}_\kp- V^{\pi_r}_{\hat{\cp}}(s)\nn\\
&\overset{(a)}{\leq }\gamma \kp^{\pi^*(s)}_s V^{\pi^*}_\kp-\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})\nn\\
&=\gamma \kp^{\pi^*(s)}_s V^{\pi^*}_\kp-\gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}+\gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})\nn\\
&=\gamma \kp^{\pi^*(s)}_s (V^{\pi^*}_\kp-V^{\pi_r}_{\hat{\cp}})+ \gamma (\kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})),
%&\triangleq \gamma \kp^{\pi^*(s)}_s (V^{\pi^*}_\kp-V^{\pi_r}_{\hat{\cp}})+ b^*(V^{\pi_r}_{\hat{\cp}})(s),
\end{align}

where $(a)$ is from $V^{\pi_r}_{\hat{\cp}}(s)=\max_a Q^{\pi_r}_{\hat{\cp}}(s,a)\geq Q^{\pi_r}_{\hat{\cp}}(s,\pi^*(s))=\hat{r}(s,\pi^*(s))+\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})=r(s,\pi^*(s))+\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})$.

For $s\in\mcs_0$, it holds that

\begin{align}\label{eq:281}
V^{\pi^*}_\kp(s)-V^{\pi_r}_{\hat{\cp}}(s)&= r(s,\pi^*(s))+\gamma \kp^{\pi^*(s)}_s V^{\pi^*}_\kp- V^{\pi_r}_{\hat{\cp}}(s)\nn\\
&\overset{(a)}{\leq }\gamma \kp^{\pi^*(s)}_s V^{\pi^*}_\kp-\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})+r(s,\pi^*(s))-\hat{r}(s,\pi^*(s))\nn\\
&\leq \gamma \kp^{\pi^*(s)}_s (V^{\pi^*}_\kp-V^{\pi_r}_{\hat{\cp}})+ \gamma (\kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}}))+1,
%&\triangleq \gamma \kp^{\pi^*(s)}_s (V^{\pi^*}_\kp-V^{\pi_r}_{\hat{\cp}})+ b^*(V^{\pi_r}_{\hat{\cp}})(s),
\end{align}

where $(a)$ follows similarly from (<ref>), and the last inequality is from $r(s,\pi^*(s))\leq 1$.

Hence combining (<ref>) and (<ref>) implies

\begin{align}\label{eq:delta 1 rec}
V^{\pi^*}_\kp(s)-V^{\pi_r}_{\hat{\cp}}(s)\leq \gamma \kp^{\pi^*(s)}_s (V^{\pi^*}_\kp-V^{\pi_r}_{\hat{\cp}})+ b^*(V)(s),
\end{align}

where $b^*(V)(s)\triangleq \gamma\kp^{\pi^*(s)}_s V -\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V)$ if $s\notin\mcs_0$, and  $b^*(V)(s)\triangleq 1+\gamma\kp^{\pi^*(s)}_s V -\gamma\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V)$ for $s\in\mcs_0$.

Moreover we set
\begin{align}
\tilde{b}(V^{\pi_r}_{\hat{\cp}})(s)=\max\{0, b^*(V^{\pi_r}_{\hat{\cp}})(s)\},
\end{align}

then it holds that $b^*(V^{\pi_r}_{\hat{\cp}})\leq \tilde{b}(V^{\pi_r}_{\hat{\cp}})$.

Then apply (<ref>) recursively and we have that

\begin{align}
\rho^\top\Delta_1\leq   \frac{1}{1-\gamma}\left\langle d^{\pi^*}, \tilde{b}(V^{\pi_r}_{\hat{\cp}}) \right\rangle,
\end{align}

Not that for $s\in\mcs_0$, it holds that $d^{\pi^*}(s)=0$, and

\begin{align}
\left\langle d^{\pi^*},\tilde{b}(V^{\pi_r}_{\hat{\cp}}) \right\rangle=\sum_{s\notin\mcs_0} d^{\pi^*}(s) \tilde{b}(V^{\pi_r}_{\hat{\cp}})(s).
\end{align}

This implies that we only need to focus on $s\notin\mcs_0$. We further defined the following sets:

\begin{align}
\mcs_{s}&\triangleq \left\{s\notin \mcs_0: N\mu(s,\pi^*(s))\leq 8\log\frac{NS}{\delta} \right\},\\
\mcs_{l}&\triangleq \left\{s\notin \mcs_0: N\mu(s,\pi^*(s))> 8\log\frac{NS}{\delta} \right\}.
\end{align}

For $s\in\mcs_s$, we have that

\begin{align}
\min \left\{d^{\pi^*}(s), \frac{1}{S}\right\}\leq C^{\pi^*}\mu(s,\pi^*(s))\leq \frac{8C^{\pi^*}\log\frac{NS}{\delta}}{N}\overset{(a)}{<}\frac{1}{S},
\end{align}

where $(a)$ is due to the fact (<ref>).

This further implies that $d^{\pi^*}(s)\leq \frac{8C^{\pi^*}\log\frac{NS}{\delta}}{N}$. Hence

\begin{align}\label{eq:21}
\sum_{s\in\mcs_s} d^{\pi^*}(s)\tilde{b}(V^{\pi_r}_{\hat{\cp}})(s)\leq \frac{2}{1-\gamma}\frac{8SC^{\pi^*}\log\frac{NS}{\delta}}{N},
\end{align}

which is due to $\|\kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})\|\leq \frac{2}{1-\gamma}$.

We then consider $s\in\mcs_l$. Note that from the definition and (<ref>), it holds that $N(s,\pi^*(s))>0$ for $s\in\mcs_l$.

Therefore it holds that

\begin{align}\label{eq:24}
\tilde{b}(V^{\pi_r}_{\hat{\cp}})(s)&\leq |\gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\gamma \sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})|\nn\\
&\leq |\gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}-\gamma \hat{\kp}^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}| +|\gamma \hat{\kp}^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\gamma \sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})|\nn\\
&\leq \gamma \big| \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}-\hat{\kp}^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}\big|+\frac{1}{1-\gamma}\frac{\log\frac{N}{\delta}}{N(s,\pi^*(s))},
\end{align}

where the last inequality is because $\hat{\kp}^{\pi^*(s)}_s\in \hat{\cp}^a_s$, and

\begin{align}
\hat{\kp}^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})&\triangleq \hat{\kp}^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\kq V^{\pi_r}_{\hat{\cp}}\nn\\
&\leq \|\hat{\kp}^{\pi^*(s)}_s-\kq\|_1 \|V^{\pi_r}_{\hat{\cp}}\|_\infty\nn\\
%&\leq \frac{1}{1-\gamma}\sqrt{D(\kq||\hat{\kp}^{\pi^*(s)}_s)}\nn\\
&\leq \frac{1}{1-\gamma}\frac{\log\frac{N}{\delta}}{N(s,\pi^*(s))}.
\end{align}

To bound the first term in (<ref>), we invoke <Ref> and have that

\begin{align}\label{eq:26}
&\big| \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}-\hat{\kp}^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}\big|\nn\\
&\leq 12\sqrt{\frac{\textbf{Var}_{\hat{\kp}^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})\log\frac{4N}{\delta}}{N(s,\pi^*(s))}}+\frac{74\log\frac{4N}{\delta}}{(1-\gamma)N(s,\pi^*(s))}\nn\\
&\leq 12\sqrt{\frac{\log\frac{4N}{\delta}}{N(s,\pi^*(s))}\left( 2\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})+\frac{41\log\frac{4N}{\delta}}{(1-\gamma)^2N(s,\pi^*(s))}\right)}+\frac{74\log\frac{4N}{\delta}}{(1-\gamma)N(s,\pi^*(s))}\nn\\
&\leq 12\sqrt{\frac{2\log\frac{4N}{\delta}}{N(s,\pi^*(s))}\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}+\frac{(74+12\sqrt{41})\log\frac{4N}{\delta}}{(1-\gamma)N(s,\pi^*(s))},
\end{align}

where the last inequality is from $\sqrt{x+y}\leq \sqrt{x}+\sqrt{y}$.

Combine (<ref>) and (<ref>), we further have that

\begin{align}\label{eq:25}
\tilde{b}(V^{\pi_r}_{\hat{\cp}})(s)&\leq 12\sqrt{\frac{2\log\frac{4N}{\delta}}{N(s,\pi^*(s))}\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}+\frac{(74+12\sqrt{41})\log\frac{4N}{\delta}}{(1-\gamma)N(s,\pi^*(s))}+\frac{\log\frac{N}{\delta}}{(1-\gamma)N(s,\pi^*(s))}\nn\\
&\leq 12\sqrt{\frac{2\log\frac{4N}{\delta}}{N(s,\pi^*(s))}\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}+\frac{c_1\log\frac{4N}{\delta}}{(1-\gamma)N(s,\pi^*(s))},
\end{align}

where $c_1=75+12\sqrt{41}$.

Note that in (<ref>), we showed that $\frac{1}{N(s,\pi^*(s))}\leq \frac{12C^{\pi^*}}{N}(S+\frac{1}{d^{\pi^*}(s)})$. Hence plugging in (<ref>) implies that

\begin{align}
&\tilde{b}(V^{\pi_r}_{\hat{\cp}})(s)\leq  12\sqrt{\frac{24C^{\pi^*}\log\frac{4N}{\delta}}{N}\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}\left(\sqrt{S}+\frac{1}{\sqrt{d^{\pi^*}(s)}}\right)\nn\\
&\quad +\frac{12c_1C^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)N}\left(S+\frac{1}{d^{\pi^*}(s)}\right).
\end{align}

Firstly we have that

\begin{align}
&\sum_{s\in\mcs_l} 12d^{\pi^*}(s) \sqrt{\frac{24C^{\pi^*}\log\frac{4N}{\delta}}{N}\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}\left(\sqrt{S}+\frac{1}{\sqrt{d^{\pi^*}(s)}}\right)\nn\\
&=\sum_{s\in\mcs_l} 12d^{\pi^*}(s) \sqrt{\frac{24SC^{\pi^*}\log\frac{4N}{\delta}}{N}\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}+\sum_{s\in\mcs_l} 12\sqrt{d^{\pi^*}(s)} \sqrt{\frac{24C^{\pi^*}\log\frac{4N}{\delta}}{N}\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}\nn\\
&=12 \sqrt{\frac{24C^{\pi^*}\log\frac{4N}{\delta}}{N}} \left(\sum_{s\in\mcs_l}\sqrt{d^{\pi^*}(s) \var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})} +\sum_{s\in\mcs_l}\sqrt{d^{\pi^*}(s)}\sqrt{Sd^{\pi^*}(s)\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}\right)\nn\\
&\overset{(a)}{\leq} 12 \sqrt{\frac{24C^{\pi^*}\log\frac{4N}{\delta}}{N}} \left(\sqrt{S}\sqrt{\sum_{s\in\mcs_l}d^{\pi^*}(s)\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}+\sqrt{\sum_{s\in\mcs_l} Sd^{\pi^*}(s) \var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})} \right)\nn\\
&=24 \sqrt{\frac{24SC^{\pi^*}\log\frac{4N}{\delta}}{N}}\sqrt{\sum_{s\in\mcs_l}d^{\pi^*}(s)\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})},
\end{align}

where $(a)$ is from Cauchy's inequality and the fact $\sum_{s\in\mcs_l}d^{\pi^*}(s)\leq 1$.

In addition, we have that

\begin{align}
\sum_{s\in\mcs_l} d^{\pi^*}(s)\frac{12c_1C^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)N}\left(S+\frac{1}{d^{\pi^*}(s)}\right)\leq \frac{24c_1SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)N}.
\end{align}

Combine the two inequalities above and we have that

\begin{align}\label{eq:29}
&\sum_{s\in\mcs_l} d^{\pi^*}(s)\tilde{b}(V^{\pi_r}_{\hat{\cp}})(s)\nn\\
&\leq 24\sqrt{\frac{24SC^{\pi^*}\log\frac{4N}{\delta}}{N}}\sqrt{\sum_{s\in\mcs_l}d^{\pi^*}(s)\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}+ \frac{24Sc_1C^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)N}.
\end{align}

Then we combine (<ref>) and (<ref>), and it implies that

\begin{align}\label{eq:d* b}
&\langle d^{\pi^*}, \tilde{b}(V^{\pi_r}_{\hat{\cp}})\rangle\nn\\
&= \sum_{s\in\mcs_s} d^{\pi^*}(s)\tilde{b}(V^{\pi_r}_{\hat{\cp}})(s)+\sum_{s\in\mcs_l} d^{\pi^*}(s)\tilde{b}(V^{\pi_r}_{\hat{\cp}})(s)\nn\\
&\leq \frac{16SC^{\pi^*}\log\frac{NS}{\delta}}{(1-\gamma)N} +24\sqrt{\frac{24SC^{\pi^*}\log\frac{4N}{\delta}}{N}}\sqrt{\sum_{s\in\mcs_l}d^{\pi^*}(s)\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}+ \frac{24Sc_1C^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)N}\nn\\
&\leq \frac{40c_1SC^{\pi^*}\log\frac{NS}{\delta}}{(1-\gamma)N} +24\sqrt{\frac{24SC^{\pi^*}\log\frac{4N}{\delta}}{N}}\sqrt{\sum_{s\in\mcs}d^{\pi^*}(s)\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}.
\end{align}

We then bound the term $\sum_{s\in\mcs}d^{\pi^*}(s)\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})$. We first claim the following inequality:

\begin{align}\label{eq:31}
V^{\pi_r}_{\hat{\cp}}-\gamma \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}}+2\tilde{b}(V^{\pi_r}_{\hat{\cp}})\geq 0.
\end{align}

To prove (<ref>), we note that

\begin{align}
V^{\pi_r}_{\hat{\cp}}(s)&=\max_a Q^{\pi_r}_{\hat{\cp}}(s,a)\nn\\
&\geq Q^{\pi_r}_{\hat{\cp}}(s,\pi^*(s))\nn\\
&=\hat{r}(s,\pi^*(s))+\gamma \sigma_{\hat{\cp}^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})\nn\\
&=\hat{r}(s,\pi^*(s))+\gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}-\gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} +\gamma \sigma_{\hat{\cp}^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})\nn\\
&\overset{(a)}{\geq} \hat{r}(s,\pi^*(s))+\gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}-b^*(V^{\pi_r}_{\hat{\cp}})(s)\nn\\
&\geq \hat{r}(s,\pi^*(s))+\gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}-2\tilde{b}(V^{\pi_r}_{\hat{\cp}})(s),
\end{align}

where $(a)$ is from $b^*(V^{\pi_r}_{\hat{\cp}})(s)\geq \gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}} -\gamma \sigma_{\hat{\cp}^{\pi^*(s)}_{s}}(V^{\pi_r}_{\hat{\cp}})$.

Hence for any $s\in\mcs$,

\begin{align}
V^{\pi_r}_{\hat{\cp}}(s)-\gamma \kp^{\pi^*(s)}_s V^{\pi_r}_{\hat{\cp}}+2\tilde{b}(V^{\pi_r}_{\hat{\cp}})(s)\geq \hat{r}(s,\pi^*(s))\geq 0,
\end{align}

which proves (<ref>).

Now with (<ref>), we first note that

\begin{align}\label{eq:34}
&(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})- (\gamma \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}})\circ(\gamma \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}})\nn\\
&=(V^{\pi_r}_{\hat{\cp}}-\gamma \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}})\circ (V^{\pi_r}_{\hat{\cp}}+\gamma \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}})\nn\\
&\leq (V^{\pi_r}_{\hat{\cp}}-\gamma \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}}+2\tilde{b}(V^{\pi_r}_{\hat{\cp}}))\circ (V^{\pi_r}_{\hat{\cp}}+\gamma \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}})\nn\\
&\leq \frac{2}{1-\gamma} (V^{\pi_r}_{\hat{\cp}}-\gamma \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}}+2\tilde{b}(V^{\pi_r}_{\hat{\cp}})),
\end{align}

where the last inequality is due to the fact $\|V^{\pi_r}_{\hat{\cp}}+\gamma \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}}\|\leq \frac{2}{1-\gamma}$ and (<ref>).

We then have that

\begin{align}\label{eq:var}
&=\langle d^{\pi^*}, \kp^{\pi^*}(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})- ( \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}})\circ( \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}})\rangle\nn\\
&\overset{(a)}{\leq} \left\langle d^{\pi^*}, \kp^{\pi^*}(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})-\frac{1}{\gamma^2} (V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})+\frac{2}{\gamma^2(1-\gamma)}(V^{\pi_r}_{\hat{\cp}}-\gamma \kp^{\pi^*} V^{\pi_r}_{\hat{\cp}}+ 2\tilde{b}(V^{\pi_r}_{\hat{\cp}}))\right\rangle\nn\\
&\overset{(b)}{\leq} \left\langle d^{\pi^*}, \kp^{\pi^*}(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})-\frac{1}{\gamma} (V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})+\frac{2}{\gamma^2(1-\gamma)}(I-\gamma\kp^{\pi^*}) V^{\pi_r}_{\hat{\cp}}+ \frac{4}{\gamma^2(1-\gamma)}\tilde{b}(V^{\pi_r}_{\hat{\cp}}))\right\rangle\nn\\
&=\left\langle d^{\pi^*}, \frac{1}{\gamma}(\gamma\kp^{\pi^*}-I)(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})+\frac{2}{\gamma^2(1-\gamma)}(I-\gamma\kp^{\pi^*}) V^{\pi_r}_{\hat{\cp}}+ \frac{4}{\gamma^2(1-\gamma)}\tilde{b}(V^{\pi_r}_{\hat{\cp}}))\right\rangle\nn\\
&= (d^{\pi^*})^\top(I-\gamma\kp^{\pi^*})\left(-\frac{1}{\gamma}(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})+\frac{2}{\gamma^2(1-\gamma)}V^{\pi_r}_{\hat{\cp}} \right)+\frac{4}{\gamma^2(1-\gamma)}\langle d^{\pi^*}, \tilde{b}(V^{\pi_r}_{\hat{\cp}}) \rangle\nn\\
&\overset{(c)}{=} (1-\gamma)\rho^\top\left(-\frac{1}{\gamma}(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})+\frac{2}{\gamma^2(1-\gamma)}V^{\pi_r}_{\hat{\cp}} \right)+\frac{4}{\gamma^2(1-\gamma)}\langle d^{\pi^*}, \tilde{b}(V^{\pi_r}_{\hat{\cp}}) \rangle\nn\\
&\leq \frac{2}{\gamma^2}\rho^\top V^{\pi_r}_{\hat{\cp}}+\frac{4}{\gamma^2(1-\gamma)}\langle d^{\pi^*}, \tilde{b}(V^{\pi_r}_{\hat{\cp}}) \rangle\nn\\
&\leq \frac{2}{\gamma^2(1-\gamma)}+\frac{4}{\gamma^2(1-\gamma)}\langle d^{\pi^*}, \tilde{b}(V^{\pi_r}_{\hat{\cp}}) \rangle,
\end{align}

where $(a)$ is from (<ref>), $(b)$ is due to $\gamma<1$, $(c)$ is from the definition of visitation distribution.

Hence by plugging (<ref>) in (<ref>), we have that

\begin{align} \label{eq:36}
&\langle d^{\pi^*}, \tilde{b}(V^{\pi_r}_{\hat{\cp}})\rangle\nn\\
&\leq \frac{40c_1SC^{\pi^*}\log\frac{NS}{\delta}}{(1-\gamma)N} +24\sqrt{\frac{24SC^{\pi^*}\log\frac{4N}{\delta}}{N}}\sqrt{\sum_{s\in\mcs}d^{\pi^*}(s)\var_{\kp^{\pi^*(s)}_s}(V^{\pi_r}_{\hat{\cp}})}\nn\\
&\leq \frac{40c_1SC^{\pi^*}\log\frac{NS}{\delta}}{(1-\gamma)N} +24\sqrt{\frac{24SC^{\pi^*}\log\frac{4N}{\delta}}{N}}\sqrt{\frac{2}{\gamma^2(1-\gamma)}+\frac{4}{\gamma^2(1-\gamma)}\langle d^{\pi^*}, \tilde{b}(V^{\pi_r}_{\hat{\cp}}) \rangle}\nn\\
&\leq \frac{40c_1SC^{\pi^*}\log\frac{NS}{\delta}}{(1-\gamma)N} +\frac{24}{\gamma}\sqrt{\frac{48SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)N}}+\frac{24}{\gamma}\sqrt{\frac{96SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)N}}\sqrt{\langle d^{\pi^*}, \tilde{b}(V^{\pi_r}_{\hat{\cp}}) \rangle}\nn\\
&\overset{(a)}{\leq} \frac{1}{2}\langle d^{\pi^*}, \tilde{b}(V^{\pi_r}_{\hat{\cp}}) \rangle+ c_2{\frac{SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)N}}+\frac{40Sc_1C^{\pi^*}\log\frac{NS}{\delta}}{(1-\gamma)N} +\frac{24}{\gamma}\sqrt{\frac{48SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)N}},
\end{align}

where $(a)$ is from $x+y\geq 2\sqrt{xy}$ and $c_2=8*24^3=110592$. This inequality moreover implies that

\begin{align}
&\langle d^{\pi^*}, \tilde{b}(V^{\pi_r}_{\hat{\cp}})\rangle{\leq}2c_2{\frac{SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)N}}+\frac{80Sc_1C^{\pi^*}\log\frac{NS}{\delta}}{(1-\gamma)N} +\frac{48}{\gamma}\sqrt{\frac{48SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)N}}.
\end{align}

Recall the definition of $\Delta_1$, we hence have that

\begin{align}
\rho^\top\Delta_1\leq  {\frac{2c_2SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)^2N}}+\frac{80Sc_1C^{\pi^*}\log\frac{NS}{\delta}}{(1-\gamma)^2N} +\frac{48}{\gamma}\sqrt{\frac{48SC^{\pi^*}\log\frac{4N}{\delta}}{(1-\gamma)^3N}}.
\end{align}

This hence completes the proof of the lemma.

With probability at least $1-2\delta$, it holds that

\begin{align}\label{eq:48}
\rho^\top\Delta_2\leq {\frac{4c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{\gamma^2(1-\gamma)^2N\mu_{\min}}}+  \frac{2c_4\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)^2N\mu_{\min}}+\frac{2}{\gamma}\sqrt{\frac{2c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)^3N\mu_{\min}}}.
\end{align}

We first define the following set:

\begin{align}
\mcs^0\triangleq \{s\in\mcs: N(s)=0 \}.
\end{align}

Note that $N(s)=\sum_a N(s,a)$, hence it holds that $N(s,a)=0$ for any $s\in\mcs^0$, $a\in\mca$.

We moreover construct an absorbing MDP $\Bar{M}=(\mcs,\mca,\hat{r},\Bar{\kp})$ as follows. For $s\in\mcs^0$, $\Bar{\kp}^a_{s,x}=\textbf{1}_{x=s}$; And for $s\notin\mcs^0$, set $\Bar{\kp}^a_{s,x}=\kp^a_{s,x}$.

Then for any $s\in\mcs^0$, from <Ref>, it holds that $V^{\pi_r}_{\hat{\cp}}(s)=0$, and hence

\begin{align}
V^{\pi_r}_{\hat{\cp}}(s)-V^{\pi_r}_{\kp}(s)\leq 0.
\end{align}

It further implies that

\begin{align}\label{eq:50}
V^{\pi_r}_{\hat{\cp}}(s)-V^{\pi_r}_{\kp}(s)=\Bar{\kp}^{\pi_r(s)}_s (V^{\pi_r}_{\hat{\cp}}-V^{\pi_r}_{\kp}) \leq \gamma\Bar{\kp}^{\pi_r(s)}_s (V^{\pi_r}_{\hat{\cp}}-V^{\pi_r}_{\kp}).
\end{align}

On the other hand, for $s\notin\mcs^0$, <Ref> implies that $N(s,\pi_r(s))>0$, hence (<ref>) implies $N(s,\pi_r(s))>0$, $\hat{r}(s,\pi_r(s))=r(s,\pi_r(s))$. Hence

\begin{align}\label{eq:51}
V^{\pi_r}_{\hat{\cp}}(s)-V^{\pi_r}_{\kp}(s)&\overset{(a)}{=}\gamma\sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})- \gamma\kp^{\pi_r(s)}_s V^{\pi_r}_\kp\nn\\
&=\gamma (\sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})- \kp^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}}+\kp^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}}-\kp^{\pi_r(s)}_s V^{\pi_r}_\kp)\nn\\
&=\gamma \kp^{\pi_r(s)}_s (V^{\pi_r}_{\hat{\cp}}-V^{\pi_r}_\kp)+ \gamma (\sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})- \kp^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}})\nn\\
&\triangleq \gamma \Bar{\kp}^{\pi_r(s)}_s (V^{\pi_r}_{\hat{\cp}}-V^{\pi_r}_\kp)+c(s),
\end{align}

where $(a)$ is from $r(s,\pi_r(s))=\hat{r}(s,\pi_r(s))$, and $c(s)\triangleq \gamma (\sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})- \kp^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}})$.

Combine (<ref>) and (<ref>), then

\begin{align}\label{eq:53}
V^{\pi_r}_{\hat{\cp}}(s)-V^{\pi_r}_{\kp}(s)\leq \gamma \Bar{\kp}^{\pi_r(s)}_s (V^{\pi_r}_{\hat{\cp}}-V^{\pi_r}_\kp)+\tilde{c}(s),
\end{align}

\begin{align}
\tilde{c}(s)=\left\{ \begin{array}{lr}
\max\{ |\gamma (\hat{\kp}^{\pi_r(s)}_s-\kp^{\pi_r(s)}_s)V^{\pi_r}_{\hat{\cp}}|, |\gamma \sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})-\gamma\kp^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}}|\},   & s\notin \mcs^0  \\
0,  & s\in\mcs^0
\end{array}
\right.
\end{align}

Applying (<ref>) recursively further implies

\begin{align}
\rho^\top \Delta_2 \leq \frac{1}{1-\gamma} \langle \bar{d}^{\pi_r}, \tilde{c} \rangle,
\end{align}

where $\bar{d}^{\pi_r}$ is the discounted visitation distribution induced by $\pi_r$ and $\Bar{\kp}$.

Note that from definition of $\tilde{c}$, we have that

\begin{align}\label{eq:44}
\sum_{s\in\mcs} \bar{d}^{\pi_r}(s)\tilde{c}(s)&\leq \sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s)\gamma|\hat{\kp}_s^{\pi_r(s)}V^{\pi_r}_{\hat{\cp}}-{\kp}_s^{\pi_r(s)}V^{\pi_r}_{\hat{\cp}}|\nn\\
&\quad+\sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s)|\gamma \sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})-\gamma\kp^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}}|\nn\\
&\leq 2\sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s)\gamma|\hat{\kp}_s^{\pi_r(s)}V^{\pi_r}_{\hat{\cp}}-{\kp}_s^{\pi_r(s)}V^{\pi_r}_{\hat{\cp}}|\nn\\
&\quad+\sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s)|\gamma \sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})-\gamma\hat{\kp}^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}}|,
\end{align}

which is because $\max\{|a|,|b|\}\leq |a|+|b|.$

Note that (<ref>) and Lemma 8 of [53] states that with probability $1-\delta$, for any $(s,a)$ pair,

\begin{align}
N(s,a)\geq \frac{N\mu(s,a)}{8\log\frac{4SA}{\delta}}.
\end{align}

Hence under this event, combining with (<ref>) and <Ref> further implies that with probability at least $1-2\delta$,

\begin{align} \label{eq:49}
&\sum_{s\in\mcs} \bar{d}^{\pi_r}(s)\tilde{c}(s)\nn\\
&\leq 2\sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s)|\hat{\kp}_s^{\pi_r(s)}V^{\pi_r}_{\hat{\cp}}-{\kp}_s^{\pi_r(s)}V^{\pi_r}_{\hat{\cp}}|+\sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s)|\gamma \sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})-\gamma\hat{\kp}^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}}|\nn\\
&\overset{(a)}{\leq} \sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s)\bigg( 12\sqrt{\frac{\log\frac{4N}{\delta}}{N(s,{\pi_r(s)})}}\sqrt{2\var_{\kp^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})+\frac{41\log\frac{4N}{\delta}}{(1-\gamma)^2N(s,{\pi_r(s)})}}+\nn\\
&\quad +\frac{74\log\frac{4N}{\delta}}{(1-\gamma)N(s,{\pi_r(s)})}\bigg)+2\sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s)\frac{1}{1-\gamma}\frac{\log\frac{N}{\delta}}{N(s,\pi_r(s))}\nn\\
%&\leq \sum_{s\in\mcs} \bar{d}^{\pi_r}(s)\frac{592\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu(s,\pi_r(s))}+\sum_{s\in\mcs} \bar{d}^{\pi_r}(s){\frac{c_3\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu(s,\pi_r(s))}}\nn\\
%&\quad + \sum_{s\in\mcs} \bar{d}^{\pi_r}(s) \sqrt{\frac{1152\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{N\mu(s,\pi_r(s))}\var_{\kp^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})}\nn\\
&\leq \sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s) \frac{(76+12\sqrt{41})\log\frac{4N}{\delta}}{(1-\gamma)N(s,\pi_r(s))}+ \sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s) \sqrt{\frac{288\log\frac{4N}{\delta}}{N(s,\pi_r(s))}\var_{\kp^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})}\nn\\
&\leq  \sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s) \frac{c_4\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu_{\min}}+  \sqrt{\frac{c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{N\mu_{\min}}\sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s) \var_{\kp^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})},
\end{align}

where $(a)$ is due to invoking <Ref> and the fact $\hat{\kp}^{\pi_r(s)}_s\in\hat{\cp}^{\pi_r(s)}_s$ for $s\notin\mcs^0$, and the last inequality is due to (<ref>) and Cauchy's inequality:

\begin{align}\label{eq:47}
\sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s) \sqrt{\var_{\kp^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})}\leq \sqrt{ \sum_{s\notin \mcs^0} \bar{d}^{\pi_r}(s)\var_{\kp^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})},
\end{align}

with constants defined as $c_4=8(76+12\sqrt{41})$, $c_5=48^2$.

By replacing $\kp^{\pi^*}$ by $\Bar{\kp}^{\pi_r}$, $\tilde{b}$ by $\tilde{c}$ in (<ref>), it can be shown that

\begin{align}\label{eq:r1}
V^{\pi_r}_{\hat{\cp}}\circ V^{\pi_r}_{\hat{\cp}} - (\gamma\Bar{\kp}^{\pi_r}V^{\pi_r}_{\hat{\cp}})\circ(\gamma\Bar{\kp}^{\pi_r}V^{\pi_r}_{\hat{\cp}}) \leq \frac{2}{1-\gamma}(V^{\pi_r}_{\hat{\cp}}-\gamma\Bar{\kp}^{\pi_r}V^{\pi_r}_{\hat{\cp}}+2\tilde{c}),
\end{align}

as long as it holds that

\begin{align}\label{eq:v-pv+c>0}
V^{\pi_r}_{\hat{\cp}}-\gamma\Bar{\kp}^{\pi_r}V^{\pi_r}_{\hat{\cp}}+2\tilde{c}\geq 0.\end{align}

To prove (<ref>), we note that for $s\notin \mcs^0$,

\begin{align}
&V^{\pi_r}_{\hat{\cp}}(s)-\gamma\bar{\kp}^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}} +2\tilde{c}(s)\nn\\
&=V^{\pi_r}_{\hat{\cp}}(s)-\gamma\kp^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}} +2\tilde{c}(s)\nn\\
&=\hat{r}(s,\pi_r(s))+\gamma\sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})-\gamma{\kp}^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}} +2\tilde{c}(s)\nn\\
&\geq  \hat{r}(s,\pi_r(s))+\gamma\sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})-\gamma{\kp}^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}}+2|\gamma\sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})-\gamma{\kp}^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}}|\nn\\
&\geq  0;
\end{align}

And for $s\in\mcs^0$, since $\Bar{\kp}^{\pi_r(s)}_s=\textbf{1}_{s}$, hence

\begin{align}
&V^{\pi_r}_{\hat{\cp}}(s)-\gamma\kp^{\pi_r(s)}_sV^{\pi_r}_{\hat{\cp}} +2\tilde{c}(s)\nn\\
&=V^{\pi_r}_{\hat{\cp}}(s)-\gamma V^{\pi_r}_{\hat{\cp}}(s)+0\nn\\
&= (1-\gamma)V^{\pi_r}_{\hat{\cp}}(s)\nn\\
\end{align}

which hence implies (<ref>) and (<ref>).

From the construction of $\Bar{M}$, it is straightforward to verify that

\begin{align}
&\var_{\Bar{\kp}^{\pi_r(s)}_s}(V)=0, \text{ for } s\in\mcs^0,\\
&\var_{\Bar{\kp}^{\pi_r(s)}_s}(V)=\var_{\kp^{\pi_r(s)}_s}(V), \text{ for } s\notin\mcs^0.
\end{align}

Hence similarly to (<ref>), we have that

\begin{align}\label{eq:57}
&\sum_{s\notin\mcs^0} \bar{d}^{\pi_r}(s)\var_{\Bar{\kp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})\nn\\
&=\sum_{s\in\mcs} \bar{d}^{\pi_r}(s)\var_{\Bar{\kp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})\nn\\
&=\langle \bar{d}^{\pi_r}, \Bar{\kp}^{\pi_r}(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})- ( \Bar{\kp}^{\pi_r} V^{\pi_r}_{\hat{\cp}})\circ( \Bar{\kp}^{\pi_r} V^{\pi_r}_{\hat{\cp}})\rangle\nn\\
&\overset{(a)}{\leq} \left\langle \bar{d}^{\pi_r}, \Bar{\kp}^{\pi_r}(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})-\frac{1}{\gamma^2} (V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})+\frac{2}{\gamma^2(1-\gamma)}(V^{\pi_r}_{\hat{\cp}}-\gamma \Bar{\kp}^{\pi_r} V^{\pi_r}_{\hat{\cp}}+ 2\tilde{c})\right\rangle\nn\\
&{\leq} \left\langle \bar{d}^{\pi_r}, \Bar{\kp}^{\pi_r}(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})-\frac{1}{\gamma} (V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})+\frac{2}{\gamma^2(1-\gamma)}(I-\gamma\Bar{\kp}^{\pi_r}) V^{\pi_r}_{\hat{\cp}}+ \frac{4}{\gamma^2(1-\gamma)}\tilde{c})\right\rangle\nn\\
&=\left\langle \bar{d}^{\pi_r}, \frac{1}{\gamma}(\gamma\Bar{\kp}^{\pi_r}-I)(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})+\frac{2}{\gamma^2(1-\gamma)}(I-\gamma\Bar{\kp}^{\pi_r}) V^{\pi_r}_{\hat{\cp}}+ \frac{4}{\gamma^2(1-\gamma)}\tilde{c})\right\rangle\nn\\
&= (\bar{d}^{\pi_r})^\top(I-\gamma\Bar{\kp}^{\pi_r})\left(-\frac{1}{\gamma}(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})+\frac{2}{\gamma^2(1-\gamma)}V^{\pi_r}_{\hat{\cp}} \right)+\frac{4}{\gamma^2(1-\gamma)}\langle \bar{d}^{\pi_r}, \tilde{c} \rangle\nn\\
&\overset{(b)}{=} (1-\gamma)\rho^\top\left(-\frac{1}{\gamma}(V^{\pi_r}_{\hat{\cp}} \circ V^{\pi_r}_{\hat{\cp}})+\frac{2}{\gamma^2(1-\gamma)}V^{\pi_r}_{\hat{\cp}} \right)+\frac{4}{\gamma^2(1-\gamma)}\langle \bar{d}^{\pi_r}, \tilde{c} \rangle\nn\\
&\leq \frac{2}{\gamma^2}\rho^\top V^{\pi_r}_{\hat{\cp}}+\frac{4}{\gamma^2(1-\gamma)}\langle \bar{d}^{\pi_r}, \tilde{c} \rangle\nn\\
&\leq \frac{2}{\gamma^2(1-\gamma)}+\frac{4}{\gamma^2(1-\gamma)}\langle \bar{d}^{\pi_r}, \tilde{c}\rangle,
\end{align}

where $(a)$ is from (<ref>) and (b) is from the definition of $\Bar{d}^{\pi_r}$.
Combine (<ref>) and (<ref>), similarly to (<ref>), we further have that

\begin{align}
&\langle \bar{d}^{\pi_r}, \tilde{c}  \rangle\nn\\
&=\sum_{s\in\mcs} \bar{d}^{\pi_r}(s)\tilde{c}(s)\nn\\
&\overset{(a)}{\leq} \sum_{s\notin\mcs^0} \bar{d}^{\pi_r}(s)\frac{c_4\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu_{\min}}+  \sqrt{\frac{c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{N\mu_{\min}}}\sqrt{\frac{2}{\gamma^2(1-\gamma)}+\frac{4}{\gamma^2(1-\gamma)}\langle \bar{d}^{\pi_r}, \tilde{c}\rangle}\nn\\
%&\leq \frac{c_4\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu(s,\pi_r(s))}+  \sqrt{\frac{c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{N\mu(s,\pi_r(s))}}\sqrt{\frac{2}{\gamma^2(1-\gamma)}+\frac{4}{\gamma^2(1-\gamma)}\langle \bar{d}^{\pi_r}, \tilde{c}\rangle} \nn\\
&\overset{(b)}{\leq} \frac{c_4\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu_{\min}}+\frac{1}{\gamma}\sqrt{\frac{2c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu_{\min}}}+\frac{2}{\gamma}\sqrt{\frac{c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu_{\min}}}\sqrt{\langle \bar{d}^{\pi_r}, \tilde{c} \rangle}\nn\\
&{\leq} \frac{1}{2}\langle \bar{d}^{\pi_r}, \tilde{c}  \rangle+  {\frac{2c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{\gamma^2(1-\gamma)N\mu_{\min}}}+\frac{c_4\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu_{\min}}+\frac{1}{\gamma}\sqrt{\frac{2c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu_{\min}}},
\end{align}

where $(a)$ is from invoking (<ref>), $(b)$ is from $\sqrt{x+y}\leq \sqrt{x}+\sqrt{y}$, and the last inequality is from $x+y\geq \frac{\sqrt{xy}}{2}$.

Hence we have that with probability at least $1-2\delta$,

\begin{align}
\langle \bar{d}^{\pi_r}, \tilde{c}  \rangle\leq {\frac{4c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{\gamma^2(1-\gamma)N\mu_{\min}}}+\frac{2c_4\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu_{\min}}+\frac{2}{\gamma}\sqrt{\frac{2c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)N\mu_{\min}}}.
\end{align}

Finally, it implies that with probability at least $1-2\delta$,

\begin{align}
\rho^\top\Delta_2\leq {\frac{4c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{\gamma^2(1-\gamma)^2N\mu_{\min}}}+ \frac{2c_4\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)^2N\mu_{\min}}+\frac{2}{\gamma}\sqrt{\frac{2c_5\log\frac{4SA}{\delta}\log\frac{4N}{\delta}}{(1-\gamma)^3N\mu_{\min}}},
\end{align}

which completes the proof.

§.§ Auxiliary Lemmas

For any $\delta$, with probability $1-\delta$, $\max \{12N(s,a),8\log\frac{NS}{\delta} \}\geq N\mu(s,a)$, $\forall s,a$.

For any $(s,a)$ pair with $N(s,a)>0$, if $V$ is an vector independent of $\hat{\kp^a_s}$  obeying $\|V\|\leq \frac{1}{1-\gamma}$, then with probability at least $1-\delta$,

\begin{align}
|(\hat{\kp}^a_s-\kp^a_s)V|&\leq \sqrt{\frac{48\textbf{Var}_{\hat{\kp}^a_s}(V)\log\frac{4N}{\delta}}{N(s,a)}}+\frac{48\log\frac{4N}{\delta}}{(1-\gamma)N(s,a)},\\
\var_{\hat{\kp}^a_s}(V)&\leq 2\var_{\kp^a_s}(V)+\frac{5\log\frac{4N}{\delta}}{3(1-\gamma)^2N(s,a)}.
\end{align}

Suppose $\gamma\in[0.5,1)$, with probability at least $1-\delta$, it holds

\begin{align}
|(\hat{\kp}^a_s-\kp^a_s)V^{\pi_r}_{\hat{\cp}}|&\leq 12\sqrt{\frac{\textbf{Var}_{\hat{\kp}^a_s}(V^{\pi_r}_{\hat{\cp}})\log\frac{4N}{\delta}}{N(s,a)}}+\frac{74\log\frac{4N}{\delta}}{(1-\gamma)N(s,a)},\\
\var_{\hat{\kp}^a_s}(V^{\pi_r}_{\hat{\cp}})&\leq 2\var_{\kp^a_s}(V^{\pi_r}_{\hat{\cp}})+\frac{41\log\frac{4N}{\delta}}{(1-\gamma)^2N(s,a)}.
\end{align}

simultaneously for any pair $(s,a)\in\mcs\times\mca$.

When $N(s,a)=0$, the results hold naturally. We hence only consider $(s,a)$ with $N(s,a)>0$.
Part 1.

Recall that $\hat{\mathsf{M}}=(\mcs,\mca,\hat{\kp}, \hat{r})$ is the estimated MDP. For any state $s$ and positive scalar $u>0$, we first construct an auxiliary state-absorbing MDP $\hat{\mathsf{M}}^{s,u}=(\mcs,\mca,\kp^{s,u}, r^{s,u})$ as follows.

For all states except $s$, the MDP structure of $\hat{\mathsf{M}}^{s,u}$ is identical to $\hat{\mathsf{M}}$, i.e., for any $x\neq s$ and $a\in\mca$,

\begin{align}
(\kp^{s,u})^a_{x,\cdot}=\hat{\kp}^a_{x,\cdot}, r^{s,u}(x,a)=\hat{r}(x,a);
\end{align}

State $s$ is an absorbing state in $\hat{\mathsf{M}}^{s,u}$, namely, for any $a\in\mca$,

\begin{align}
(\kp^{s,u})^a_{s,x}=\textbf{1}_{x=s}, r^{s,u}(s,a)=u.
\end{align}

We then define a robust MDP $\mathcal{M}^{s,u}=(\mcs,\mca,\cp^{s,u},r^{s,u})$ centered at $\hat{\mathsf{M}}^{s,u}$ as following: the uncertainty set $\cp^{s,u}$ is defined as $\hat{\cp}=\bigotimes_{x,a}(\cp^{s,u})_x^a$, where if $x\neq s$,

\begin{align}
(\cp^{s,u})^a_x=\left\{ q\in\Delta(\mcs): \|q-(\kp^{s,u})^a_x\|\leq \min\left\{2, \frac{\log \frac{N}{\delta}}{N(x,a)}\right\}\right\}
\end{align}

\begin{align}
\end{align}

The optimal robust value function of $\mathcal{M}^{s,u}$ is denoted by $V^{s,u}$.

Part 2.
We claim that if we choose $u^*=(1-\gamma)V^{\pi_r}_{\hat{\cp}}(s)$, then $V^{s,u^*}=V^{\pi_r}_{\hat{\cp}}$. We prove this as follows.

Firstly note that the function $V^{s,u^*}$ is the unique fixed point of the operator $\mathbf{T}^{s,u^*}(V)(x)=\max_a \{r^{s,u^*}(x,a)+\gamma \sigma_{(\cp^{s,u^*})^a_x}(V) \}$.

For $x\neq s$, we note that

\begin{align}\label{eq:28}
\mathbf{T}^{s,u^*}(V^{\pi_r}_{\hat{\cp}})(x)&=\max_a \{r^{s,u^*}(x,a)+\gamma \sigma_{(\cp^{s,u^*})^a_x}(V^{\pi_r}_{\hat{\cp}})  \}\nn\\
&= \max_a \{\hat{r}(x,a)+\gamma \sigma_{\hat{\cp}^a_x}(V^{\pi_r}_{\hat{\cp}})\}\nn\\
\end{align}

which is because $r^{s,u^*}(x,a)=\hat{r}(x,a)$ and $(\cp^{s,u^*})^a_x=\hat{\cp}^a_x$ for $x\neq s$.

For $s$, we have that

\begin{align}\label{eq:30}
\mathbf{T}^{s,u^*}(V^{\pi_r}_{\hat{\cp}})(s)&=\max_a \{r^{s,u^*}(s,a)+\gamma \sigma_{(\cp^{s,u^*})^a_s}(V^{\pi_r}_{\hat{\cp}})  \}\nn\\
&= \max_a \{u^*+\gamma \sigma_{(\cp^{s,u^*})^a_s}(V^{\pi_r}_{\hat{\cp}})\}\nn\\
&= \max_a \{ (1-\gamma)V^{\pi_r}_{\hat{\cp}}(s)+\gamma (V^{\pi_r}_{\hat{\cp}})(s)\}\nn\\
\end{align}

which from $(\cp^{s,u^*})^a_s=\{\textbf{1}_s\}$.

Hence combining with (<ref>) implies that $V^{\pi_r}_{\hat{\cp}}$ is also a fixed point of $ \mathbf{T}^{s,u^*}$, and hence it must be identical to $V^{s,u^*}$, which proves our claim.

Part 3.
Define a set $U_c\triangleq \left\{ \frac{i}{N}| i=1,...,N\right\}$. Clearly, $U_c$ is a $\frac{1}{N}$-net [59, 33] of the interval $[0,1]$.

Note that for any $u\in U_c$,  $\cp^{s,u}$ is independent with $\hat{\kp}^a_s$, hence $V^{s,u}$ is also independent with $\hat{\kp}^a_s$. Also, since $u\leq 1$, $\|V^{s,u}\|\leq \frac{1}{1-\gamma}$.

Then invoking <Ref> implies that for any $N(s,a)>0$, with probability at least $1-\delta$,  it holds simultaneously for all $u\in U_c$ that

\begin{align}
|(\hat{\kp}^a_s-\kp^a_s)V^{s,u}|&\leq \sqrt{\frac{48\textbf{Var}_{\hat{\kp}^a_s}(V^{s,u})\log\frac{4N^2}{\delta}}{N(s,a)}}+\frac{48\log\frac{4N^2}{\delta}}{(1-\gamma)N(s,a)},\\
\var_{\hat{\kp}^a_s}(V^{s,u})&\leq 2\var_{\kp^a_s}(V^{s,u})+\frac{5\log\frac{4N^2}{\delta}}{3(1-\gamma)^2N(s,a)}.
\end{align}

Part 4. Since $u^*=(1-\gamma)V^{\pi_r}_{\hat{\cp}}\leq 1$, then there exists $u_0\in U_c$, such that $|u_0-u^*|\leq \frac{1}{N}$. Moreover, we claim that

\begin{align}\label{eq:40}
\|V^{s,u^*}-V^{s,u_0}\|\leq \frac{1}{N(1-\gamma)}.
\end{align}

To prove (<ref>), first note that

\begin{align}\label{eq:35}
|V^{s,u^*}(s)-V^{s,u_0}(s)|&\leq \max_a |(u^*-u_0)+\gamma (\sigma_{(\cp^{s,u^*})^a_s}(V^{s,u^*})-\sigma_{(\cp^{s,u_0})^a_s}(V^{s,u_0}))|\nn\\
&\overset{(a)}{\leq} |u^*-u_0|+ \gamma \max_a |\sigma_{(\cp^{s,u^*})^a_s}(V^{s,u^*})-\sigma_{(\cp^{s,u^*})^a_s}(V^{s,u_0})|\nn\\
&\overset{(b)}{\leq} |u^*-u_0|+ \gamma \|V^{s,u^*}-V^{s,u_0}\|,
\end{align}

where $(a)$ is because $(\cp^{s,u_0})^a_s=(\cp^{s,u^*})^a_s=\{\textbf{1}_s\}$, and $(b)$ is due to the non-expansion of the support function (Lemma 1, [44]).

For $x\neq s$, we have that

\begin{align}\label{eq:366}
|V^{s,u^*}(x)-V^{s,u_0}(x)|&\leq \max_a |\hat{r}(x,a)-\hat{r}(x,a)+\gamma (\sigma_{\hat{\cp}^a_x}(V^{s,u^*})-\sigma_{\hat{\cp}^a_x}(V^{s,u_0}))|\nn\\
&\leq \gamma \|V^{s,u^*}-V^{s,u_0}\|.
\end{align}

Thus by combining (<ref>) and (<ref>), we have that

\begin{align}
\|V^{s,u^*}-V^{s,u_0}\|\leq \frac{1}{N}+\gamma\|V^{s,u^*}-V^{s,u_0}\|,
\end{align}

and hence proof the claim (<ref>).

\begin{align}
&\var_{\kp^a_s}(V^{s,u_0})-  \var_{\kp^a_s}(V^{s,u^*})\nn\\
&=\kp^a_s\left( (V^{s,u_0}-\kp^a_sV^{s,u_0})\circ (V^{s,u_0}-\kp^a_sV^{s,u_0}) - (V^{s,u^*}-\kp^a_sV^{s,u^*})\circ (V^{s,u^*}-\kp^a_sV^{s,u^*}) \right)\nn\\
&\overset{(a)}{\leq} \kp^a_s\left( (V^{s,u_0}-\kp^a_sV^{s,u^*})\circ (V^{s,u_0}-\kp^a_sV^{s,u^*}) - (V^{s,u^*}-\kp^a_sV^{s,u^*})\circ (V^{s,u^*}-\kp^a_sV^{s,u^*}) \right)\nn\\
&\leq \kp^a_s\left( (V^{s,u_0}-\kp^a_sV^{s,u^*}+V^{s,u^*}-\kp^a_s V^{s,u^*})\circ (V^{s,u_0}-V^{s,u^*})\right)\nn\\
&\leq \frac{2}{1-\gamma}|\kp^a_s (V^{s,u_0}-V^{s,u^*})|\nn\\
&\leq \frac{2}{N(1-\gamma)^2},
\end{align}

where $(a)$ is due to the fact $\mE[X]=\arg\min_c \mE[(X-c)^2]$, and the last inequality is due to $\|V^{s,u_0}\|\leq \frac{1}{1-\gamma}, \|V^{s,u^*}\|\leq \frac{1}{1-\gamma}$.

Similarly, swapping $V^{s,u_0}$ and $V^{s,u^*}$ implies

\begin{align}
\var_{\kp^a_s}(V^{s,u^*})-\var_{\kp^a_s}(V^{s,u_0})
\leq \frac{2}{N(1-\gamma)^2},
\end{align}

and further

\begin{align}\label{eq:86}
\leq \frac{2}{N(1-\gamma)^2}.
\end{align}

We note that (<ref>) is exactly identical to (159) in Section A.4 of [33], and hence the remaining proof can be obtained by following the proof in Section A.4 in  [33], and are omitted here.

(1). For any policy $\pi$ and $s\in\mcs^0$, $V^\pi_{\hat{\cp}}(s)=0$;

(2). There exists a deterministic robust optimal policy $\pi_r$, such that for any $s\notin \mcs^0$, $N(s,\pi_r(s))>0$.

Proof of (1).

For any $s\in\mcs^0$, it holds that $N(s,a)=0$ for any $a\in\mca$. Hence $\hat{r}(s,a)=0$ and $\hat{\cp}^a_s=\Delta(\mcs)$.

Then for any policy $\pi$ and $a\in\mca$, it holds that

\begin{align}
Q^\pi_{\hat{\cp}}(s,a)=\hat{r}(s,a)+\gamma\sigma_{\hat{\cp}^a_s}(V^\pi_{\hat{\cp}})\leq \gamma V^\pi_{\hat{\cp}}(s).
\end{align}

\begin{align}
V^\pi_{\hat{\cp}}(s)=\sum_a \pi(a|s)Q^\pi_{\hat{\cp}}(s,a) \leq \gamma V^\pi_{\hat{\cp}}(s),
\end{align}

which implies $V^\pi_{\hat{\cp}}(s)=0$ together with $V^\pi_{\hat{\cp}}\geq 0$.

Proof of (2).

We prove Claim (2) by contradiction. Assume that for any optimal policy $\pi_r$, there exists $s\notin \mcs^0$ such that $N(s,\pi_r(s))=0$. We then consider a fixed pair ($\pi_r,s$).

$N(s,\pi_r(s))=0$ further implies $\hat{r}(s,\pi_r(s))=0$, $\hat{\cp}^{\pi_r(s)}_s=\Delta(\mcs)$,  and

\begin{align}\label{eq:98}
V^{\pi_r}_{\hat{\cp}}(s)=\max_a Q^{\pi_r}_{\hat{\cp}}(s,a)= Q^{\pi_r}_{\hat{\cp}}(s,\pi_r(s))=\hat{r}(s,\pi_r(s))+\gamma\sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})\leq \gamma V^{\pi_r}_{\hat{\cp}}(s),
\end{align}

where the last inequality is from $\hat{\cp}^{\pi_r(s)}_s=\Delta(\mcs)$, $\hat{r}(s,\pi_r(s))=0$, and $\sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})\leq \textbf{1}_s V^{\pi_r}_{\hat{\cp}}=V^{\pi_r}_{\hat{\cp}}(s)$.
This further implies that $V^{\pi_r}_{\hat{\cp}}(s)=0$ because $V^{\pi_r}_{\hat{\cp}}\geq 0$.

On the other hand, since $s\notin\mcs^0$, there exists another action $b\neq\pi_r(s)$ such that $N(s,b)>0$, and hence $\hat{r}(s,b)=r(s,b)$. We consider the following two cases.

(I). If $r(s,b)>0$, then

\begin{align}
Q^{\pi_r}_{\hat{\cp}}(s,b)=\hat{r}(s,b)+\gamma\sigma_{\hat{\cp}^{b}_s}(V^{\pi_r}_{\hat{\cp}})> 0=Q^{\pi_r}_{\hat{\cp}}(s,\pi_r(s)),
\end{align}

which is contradict to $V^{\pi_r}_{\hat{\cp}}(s)=\max_a Q^{\pi_r}_{\hat{\cp}}(s,a)= Q^{\pi_r}_{\hat{\cp}}(s,\pi_r(s))$.

(II). If $r(s,b)=0$, <Ref> then implies the modified policy $f^s_b(\pi_r)$ is also optimal, and satisfies $N(x,f^s_b(\pi_r)(x))=N(x,\pi_r(x))$ for any $x\neq s$, and $N(s,f^s_b(\pi_r)(s))>0$.

Then consider the modified policy ${f^s_b(\pi_r)}$.

If there still exists $s'\notin \mcs^0$ such that $N(s',{f^s_b(\pi_r)}(s'))=0$, then similarly,
there exists another action $b'\neq {f^s_b(\pi_r)}(s')$ such that $N(s',b')>0$. Then whether $r(s',b')>0$, which falls into Case (I) and leads to a contradiction, or applying <Ref> again implies another optimal policy $f^{s'}_{b'}(f^s_b(\pi_r))$, such that $N(s,f^{s'}_{b'}(f^s_b(\pi_r))(x))=N(s,f^s_b(\pi_r)(x))>0$ for $x\notin \{s,s'\}$,  $N(s,f^{s'}_{b'}(f^s_b(\pi_r))(s))=N(s,f^s_b(\pi_r)(s))>0$ and $N(s',f^{s'}_{b'}(f^s_b(\pi_r))(s'))>0$.

Repeating this procedure recursively further implies there exists an optimal policy $\pi$, such that $N(s,\pi(s))>0$ for any $s\notin\mcs^0$, which is a contraction to our assumption.

Therefore it completes the proof.

For a robust optimal policy $\pi_r$, if there exists a state $s\notin\mcs^0$ and an action $b$ such that $N(s,\pi_r(s))=0$, $r(s,b)=0$ and $N(s,b)>0$, define a modified policy $f^s_b(\pi_r)$ as

\begin{align}
{f^s_b(\pi_r)}(x)&=\pi_r(x), \text{ for } x\neq s.
\end{align}

Then the modified policy $f^s_b(\pi_r)$ is also optimal, and satisfies $N(s,f^s_b(\pi_r)(s))>0$, $N(x,f^s_b(\pi_r)(x))=N(x,\pi_r(x)), \forall x\neq s$.

Recall that $\hat{\cp}^{\pi_r(s)}_s=\Delta(\mcs)$ and $\hat{\cp}^b_s\subset \Delta(\mcs)$,
we have that

\begin{align}\label{eq:>}
V^{{f^s_b(\pi_r)}}_{\hat{\cp}} \geq V^{{f^s_b(\pi_r)}}_{\hat{\cp^b_s}},
\end{align}

where $\hat{\cp^b_s}$ is a modified uncertainty set defined as

\begin{align}
(\hat{\cp^b_s})^a_x&=\hat{\cp}^a_x, \text{ for } (x,a)\neq (s,b).
\end{align}

Now we have that

\begin{align}
V^{{f^s_b(\pi_r)}}_{\hat{\cp^b_s}}(s)=Q^{{f^s_b(\pi_r)}}_{\hat{\cp^b_s}}(s,b)=r(s,b)+\gamma\sigma_{(\hat{\cp^b_s})^b_s}(V^{{f^s_b(\pi_r)}}_{\hat{\cp^b_s}})\leq \gamma V^{{f^s_b(\pi_r)}}_{\hat{\cp^b_s}}(s),
\end{align}

which further implies $V^{{f^s_b(\pi_r)}}_{\hat{\cp^b_s}}(s)=0$. Note that in (<ref>), we have shown $V^{\pi_r}_{\hat{\cp}}(s)=0$, hence $V^{{f^s_b(\pi_r)}}_{\hat{\cp^b_s}}(s)=V^{\pi_r}_{\hat{\cp}}(s)=0$.

Now consider the two robust Bellman operator $\mathbf{T}_b^sV(x)=\sum_a {f^s_b(\pi_r)}(a|x) ( \hat{r}(x,a)+\gamma \sigma_{(\hat{\cp^b_s})^a_x}(V))$ and $\mathbf{T}V(x)=\hat{r}(x,\pi_r(x))+\gamma \sigma_{\hat{\cp}^{\pi_r(x)}_x}(V)$. It is known that   $V^{{f^s_b(\pi_r)}}_{\hat{\cp^b_s}}$ is the unique fixed point of the robust Bellman operator $\mathbf{T}_b^s$ and $V^{\pi_r}_{\hat{\cp}}$ is the unique fixed point of $\mathbf{T}$.

When $x\neq s$,

\begin{align}\label{eq:x not s}
\mathbf{T}_b^s V^{\pi_r}_{\hat{\cp}}(x)&=\sum_a {f^s_b(\pi_r)}(a|x) ( \hat{r}(x,a)+\gamma \sigma_{(\hat{\cp^b_s})^a_x}(V^{\pi_r}_{\hat{\cp}}))\nn\\
&\overset{(a)}{=}\sum_a \pi_r(a|x) ( \hat{r}(x,a)+\gamma \sigma_{(\hat{\cp^b_s})^a_x}(V^{\pi_r}_{\hat{\cp}}))\nn\\
&=\hat{r}(x,\pi_r(x))+\gamma \sigma_{(\hat{\cp^b_s})^{\pi_r(x)}_x}(V^{\pi_r}_{\hat{\cp}})\nn\\
&\overset{(b)}{=}\hat{r}(x,\pi_r(x))+\gamma \sigma_{\hat{\cp}^{\pi_r(x)}_x}(V^{\pi_r}_{\hat{\cp}})\nn\\
\end{align}

where $(a)$ is from ${f^s_b(\pi_r)}(x)=\pi_r(x)$ when $x\neq s$, $(b)$ is from $(\hat{\cp^b_s})^{\pi_r(x)}_x=\hat{\cp}^{\pi_r(x)}_x$.

And for $s$, it holds that

\begin{align}\label{eq:s}
\mathbf{T}_b^s V^{\pi_r}_{\hat{\cp}}(s)&= \hat{r}(s,b)+\gamma \sigma_{(\hat{\cp^b_s})^b_s}(V^{\pi_r}_{\hat{\cp}})\nn\\
&\overset{(a)}{=} \hat{r}(s,\pi_r(s))+\gamma \sigma_{\Delta(\mcs)}(V^{\pi_r}_{\hat{\cp}})\nn\\
&\overset{(b)}{=} \hat{r}(s,\pi_r(s))+\gamma \sigma_{\hat{\cp}^{\pi_r(s)}_s}(V^{\pi_r}_{\hat{\cp}})\nn\\
\end{align}

where $(a)$ is from $(\hat{\cp^b_s})^b_s=\Delta(\mcs)$ and $\hat{r}(s,b)=r(s,b)=0=\hat{r}(s,\pi_r(s))$, and $(b)$ follows from the fact $\hat{\cp}^{\pi_r(s)}_s=\Delta(\mcs)$.

(<ref>) and (<ref>) further imply that $V^{\pi_r}_{\hat{\cp}}$ is also a fixed point of $\mathbf{T}_b^s$. Hence it must be identical to $V^{{f^s_b(\pi_r)}}_{\hat{\cp^b_s}}$, i.e., $V^{{f^s_b(\pi_r)}}_{\hat{\cp^b_s}}=V^{\pi_r}_{\hat{\cp}}$.

Combine with (<ref>), we have

\begin{align}
V^{{f^s_b(\pi_r)}}_{\hat{\cp}} \geq V^{{f^s_b(\pi_r)}}_{\hat{\cp^b_s}}=V^{\pi_r}_{\hat{\cp}},
\end{align}

which implies that ${f^s_b(\pi_r)}$ is also optimal with $N(s,{f^s_b(\pi_r)}(s))=N(s,b)>0$. And since $f^s_b(\pi_r)(x)=\pi_r(x)$ for $x\neq s$, then $N(x,{f^s_b(\pi_r)}(x))=N(x,\pi_r(x))$. This thus completes the proof.