$\displaystyle\frac{1}{A}\sum_{j=1}^{A}\mathbb{E}_{unif}[N_{s_{n},a_{j}}]+\frac{K\eta}{2A}\sqrt{A\sum_{j=1}^{A}\frac{c_{1}}{\alpha}\cdot
w(s_{n})\cdot\mathbb{E}_{unif}[N_{s_{n},a_{j}}]}$ $\displaystyle\leq$
$\displaystyle\frac{K}{A}+\frac{K\eta}{2}\sqrt{\frac{c_{1}\cdot
w(s_{n})K}{\alpha A}}$ (17)

By plugging Eq. (17) into Eq. (16), we have

$\displaystyle\mathbb{E}\left[\mathcal{R}(K)\right]\geq
0.6(H-n)\cdot\frac{\eta}{\alpha}\cdot\left(K-\frac{K}{A}-\frac{K\eta}{2}\sqrt{\frac{c_{1}\cdot
w(s_{n})K}{\alpha A}}\right).$

Let $\eta=c_{2}\sqrt{\frac{\alpha A}{w(s_{n})K}}$ for a small enough constant
$c_{2}$. We have

$\displaystyle\mathbb{E}\left[\mathcal{R}(K)\right]=$
$\displaystyle\Omega\left(H\sqrt{\frac{A}{\alpha\cdot w(s_{n})K}}\cdot
K\right)$ $\displaystyle=$
$\displaystyle\Omega\left(H\sqrt{\frac{AK}{\alpha\cdot w(s_{n})}}\right)$

Recall that $n<\frac{1}{2}H$ and $0<\alpha<\mu<\frac{1}{3}$. Thus, we have
that $\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)=w(s_{n})=\mu^{n-1}>\alpha^{H-1}$,
and

$\displaystyle\mathbb{E}\left[\mathcal{R}(K)\right]=$
$\displaystyle\Omega\left(H\sqrt{\frac{AK}{\alpha\cdot\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}}\right).$

Figure 7: Instance of lower bounds (Theorems 2 and 5) for the
$\alpha^{H-1}>\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)$ case.

Next, we construct another instance where
$\alpha^{H-1}>\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)$, and prove that on this instance
any algorithm must suffer a $\Omega(\sqrt{\frac{AK}{\alpha^{H-1}}})$ regret.

Consider the instance shown in Figure 7:

The state space is
$\mathcal{S}=\\{s_{1},\dots,s_{n},s^{\prime}_{2},\dots,s^{\prime}_{n},x_{1},x_{2},x_{3},x_{4}\\}$,
where $n=H-1$ and $s_{1}$ is the initial state. Let $0<\alpha<\frac{1}{4}$.

The reward functions are as follows. For any $a\in\mathcal{A}$,
$r(x_{1},a)=r(x_{4},a)=1$, $r(x_{2},a)=0.8$ and $r(x_{3},a)=0.2$. For any
$i\in[n]$ and $a\in\mathcal{A}$, $r(s_{i},a)=0$. For any $i\in\\{2,\dots,n\\}$
and $a\in\mathcal{A}$, $r(s^{\prime}_{i},a)=0$.

The transition distributions are as follows. For any $a\in\mathcal{A}$,
$p(s_{2}|s_{1},a)=\alpha$, $p(s^{\prime}_{2}|s_{1},a)=\gamma$ and
$p(x_{1}|s_{1},a)=1-\gamma-\alpha$. For any $i\in\\{2,\dots,n-1\\}$ and
$a\in\mathcal{A}$, $p(s_{i+1}|s_{i},a)=\alpha$ and
$p(x_{1}|s_{i},a)=1-\alpha$. For any $i\in\\{2,\dots,n-1\\}$ and
$a\in\mathcal{A}$, $p(s^{\prime}_{i+1}|s^{\prime}_{i},a)=\gamma$ and
$p(x_{1}|s^{\prime}_{i},a)=1-\gamma$. For any $a\in\mathcal{A}$,
$p(x_{4}|s^{\prime}_{n},a)=\gamma$ and $p(x_{1}|s^{\prime}_{n},a)=1-\gamma$.
$x_{1}$, $x_{2}$, $x_{3}$ and $x_{4}$ are absorbing states, i.e., for any
$a\in\mathcal{A}$ and $i\in[4]$, $p(x_{i}|x_{i},a)=1$. Let $a_{J}$ be the
optimal action in state $s_{n}$, which is uniformly drawn from $\mathcal{A}$.
For the optimal action $a_{J}$, $p(x_{2}|s_{n},a_{J})=1-\alpha+\eta$ and
$p(x_{3}|s_{n},a_{J})=\alpha-\eta$, where $\eta$ is a parameter which
satisfies $0<\eta<\alpha$ and will be chosen later. For any suboptimal action
$a\in\mathcal{A}\setminus\\{a_{J}\\}$, $p(x_{2}|s_{n},a)=1-\alpha$ and
$p(x_{3}|s_{n},a)=\alpha$.

According to the definition of the value function for Iterated CVaR RL, we
have that

$\displaystyle V^{*}_{1}(s_{1})=$
$\displaystyle\frac{0.2(\alpha-\eta)+0.8\eta}{\alpha},$

and for any policy $\pi$,

$\displaystyle V^{\pi}_{1}(s_{1})=$
$\displaystyle\frac{0.2(\alpha-\eta)+0.8\eta}{\alpha}\cdot\mathbbm{1}\left\\{\pi(s_{n})=a_{J}\right\\}+0.2\left(1-\mathbbm{1}\left\\{\pi(s_{n})=a_{J}\right\\}\right).$

If $J=j$, for any policy $\pi$,

$\displaystyle
V^{*}_{1}(s_{1})-V^{\pi}_{1}(s_{1})=\frac{0.6\eta}{\alpha}\left(1-\mathbbm{1}\left\\{\pi(s_{n})=a_{j}\right\\}\right),$
(18)

and summing over all episodes $k\in[K]$, we have

$\displaystyle\mathbb{E}_{j}\left[\mathcal{R}(K)\right]=$
$\displaystyle\sum_{k=1}^{K}\left(V^{*}_{1}(s_{1})-V^{\pi^{k}}_{1}(s_{1})\right)$
$\displaystyle=$
$\displaystyle\frac{0.6\eta}{\alpha}\cdot\left(K-\sum_{k=1}^{K}\mathbbm{1}\left\\{\pi(s_{n})=a_{j}\right\\}\right)$
$\displaystyle=$
$\displaystyle\frac{0.6\eta}{\alpha}\cdot\left(K-\mathbb{E}_{j}[N_{s_{n},a_{j}}]\right)$

Therefore, we have

$\displaystyle\mathbb{E}\left[\mathcal{R}(K)\right]=$
$\displaystyle\frac{1}{A}\sum_{j=1}^{A}\sum_{k=1}^{K}\left(V^{*}_{1}(s_{1})-V^{\pi^{k}}_{1}(s_{1})\right)$
$\displaystyle=$
$\displaystyle\frac{1}{A}\sum_{j=1}^{A}\frac{0.6\eta}{\alpha}\left(K-\mathbb{E}_{j}[N_{s_{n},a_{j}}]\right)$
$\displaystyle=$
$\displaystyle\frac{0.6\eta}{\alpha}\left(K-\frac{1}{A}\sum_{j=1}^{A}\mathbb{E}_{j}[N_{s_{n},a_{j}}]\right)$
(19)

Recall that $0<\alpha<\frac{1}{4}$. For any $j\in[A]$, we have that
$\textup{KL}(p_{unif}(s_{n},a_{j})\|p_{j}(s_{n},a_{j}))=\textup{KL}(\mathtt{Ber}(\alpha)\|\mathtt{Ber}(\alpha-\eta))\leq\frac{\eta^{2}}{(\alpha-\eta)(1-\alpha+\eta)}\leq\frac{c_{1}\eta^{2}}{\alpha}$
for some constant $c_{1}$ and small enough $\eta$. Then, using Lemma A.1 in
(Auer et al., 2002), we have that for any $j\in[A]$,

$\displaystyle\mathbb{E}_{j}[N_{s_{n},a_{j}}]\leq$
$\displaystyle\mathbb{E}_{unif}[N_{s_{n},a_{j}}]+\frac{K}{2}\sqrt{\mathbb{E}_{unif}[V_{s_{n},a_{j}}]\cdot\textup{KL}\left(p_{unif}(s_{n},a_{j})||p_{j}(s_{n},a_{j})\right)}$
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{unif}[N_{s_{n},a_{j}}]+\frac{K}{2}\sqrt{w(s_{n})\cdot\mathbb{E}_{unif}[N_{s_{n},a_{j}}]\cdot\frac{c_{1}\eta^{2}}{\alpha}}$

Then, using $\sum_{j=1}^{A}\mathbb{E}_{unif}[N_{s_{n},a_{j}}]=K$ and the
Cauchy–Schwarz inequality, we have

$\displaystyle\frac{1}{A}\sum_{j=1}^{A}\mathbb{E}_{j}[N_{s_{n},a_{j}}]\leq$
$\displaystyle\frac{1}{A}\sum_{j=1}^{A}\mathbb{E}_{unif}[N_{s_{n},a_{j}}]+\frac{K\eta}{2A}\sum_{j=1}^{A}\sqrt{\frac{c_{1}}{\alpha}\cdot
w(s_{n})\cdot\mathbb{E}_{unif}[N_{s_{n},a_{j}}]}$ $\displaystyle\leq$
$\displaystyle\frac{1}{A}\sum_{j=1}^{A}\mathbb{E}_{unif}[N_{s_{n},a_{j}}]+\frac{K\eta}{2A}\sqrt{A\sum_{j=1}^{A}\frac{c_{1}}{\alpha}\cdot
w(s_{n})\cdot\mathbb{E}_{unif}[N_{s_{n},a_{j}}]}$ $\displaystyle\leq$
$\displaystyle\frac{K}{A}+\frac{K\eta}{2}\sqrt{\frac{c_{1}\cdot
w(s_{n})K}{\alpha A}}$ (20)

By plugging Eq. (20) into Eq. (19), we have

$\displaystyle\mathbb{E}\left[\mathcal{R}(K)\right]\geq$
$\displaystyle\frac{0.6\eta}{\alpha}\cdot\left(K-\frac{K}{A}-\frac{K\eta}{2}\sqrt{\frac{c_{1}\cdot
w(s_{n})K}{\alpha A}}\right).$

Let $\eta=c_{2}\sqrt{\frac{\alpha A}{w(s_{n})K}}$ for a small enough constant
$c_{2}$. We have

$\displaystyle\mathbb{E}\left[\mathcal{R}(K)\right]=$
$\displaystyle\Omega\left(\sqrt{\frac{A}{\alpha\cdot w(s_{n})K}}\cdot
K\right)$ $\displaystyle=$
$\displaystyle\Omega\left(\sqrt{\frac{AK}{\alpha\cdot w(s_{n})}}\right)$

Recall that $0<\gamma<\alpha$ and $n=H-1$. Thus, we have
$\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)=w(x_{4})=\gamma^{H-1}<\alpha^{H-1}$.
In addition, since $w(s_{n})=\alpha^{n-1}=\alpha^{H-2}$, we have

$\displaystyle\mathbb{E}\left[\mathcal{R}(K)\right]=$
$\displaystyle\Omega\left(\sqrt{\frac{AK}{\alpha\cdot\alpha^{H-2}}}\right)$
$\displaystyle=$
$\displaystyle\Omega\left(\sqrt{\frac{AK}{\alpha^{H-1}}}\right).$

∎

Input: $\varepsilon$, $\delta$, $\alpha$, $\delta^{\prime}:=\frac{\delta}{7}$,
$\tilde{L}(k):=\log(\frac{2HSAk^{3}}{\delta^{\prime}})$ for any $k>0$,
$J^{k}_{H+1}(s)=\bar{V}^{k}_{H+1}(s)=\underline{V}^{k}_{H+1}(s)=0$ for any
$k>0$ and $s\in\mathcal{S}$.

1 for  _$k=1,2,\dots,K$_ do

2 for  _$h=H,H-1,\dots,1$_ do

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

4 for  _$a\in\mathcal{A}$_ do

5
$\bar{Q}^{k}_{h}(s,a)\leftarrow\min\Big{\\{}r(s,a)+\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\bar{V}^{k}_{h+1}(s^{\prime}))+\frac{H}{\alpha}\sqrt{\frac{\tilde{L}(k)}{n_{k}(s,a)}},\
H\Big{\\}}$;

6
$\underline{Q}^{k}_{h}(s,a)\leftarrow\max\Big{\\{}r(s,a)+\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\underline{V}^{k}_{h+1}(s^{\prime}))-\frac{4H}{\alpha}\sqrt{\frac{S\tilde{L}(k)}{n_{k}(s,a)}},\
0\Big{\\}}$;

7
$G^{k}_{h}(s,a)\leftarrow\min\Big{\\{}\frac{H(1+4\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s,a)}}+\hat{\beta}^{k;\alpha,\underline{V}^{k}_{h+1}}(\cdot|s,a)^{\top}J^{k}_{h+1},\
H\Big{\\}}$;

8

9
$\pi^{k}_{h}(s)\leftarrow\operatornamewithlimits{argmax}_{a\in\mathcal{A}}\bar{Q}^{k}_{h}(s,a)$.
$\bar{V}^{k}_{h}(s)\leftarrow\max_{a\in\mathcal{A}}\bar{Q}^{k}_{h}(s,a)$.
$\underline{V}^{k}_{h}(s)\leftarrow\underline{Q}^{k}_{h}(s,\pi^{k}_{h}(s))$.
$J^{k}_{h}(s)\leftarrow G^{k}_{h}(s,\pi^{k}_{h}(s))$;

10

11

12 if  _$J^{k}_{1}(s)\leq\varepsilon$_ then

13 return $\pi^{k}(s)$

14 else

15 Play the episode $k$ with policy $\pi^{k}$, and update $n_{k+1}(s,a)$ and
$\hat{p}^{k+1}(s^{\prime}|s,a)$

16

Algorithm 3 $\mathtt{ICVaR\mbox{-}BPI}$

##  Appendix E Proofs for Iterated CVaR RL with Best Policy Identification

In this section, we present the pseudo-code and detailed description of
algorithm $\mathtt{ICVaR\mbox{-}BPI}$, and formally state the sample
complexity lower bound for Iterated CVaR-BPI (Theorem 5). We also give the
proofs of sample complexity upper and lower bounds (Theorems 3 and 5).

###  E.1 Algorithm $\mathtt{ICVaR\mbox{-}BPI}$

Algorithm $\mathtt{ICVaR\mbox{-}BPI}$ (Algorithm 3) constructs optimistic and
pessimistic value functions, estimation error, and a hypothesized optimal
policy in each episode, and returns the hypothesized optimal policy when the
estimation error shrinks within $\varepsilon$. Specifically, in each episode
$k$, $\mathtt{ICVaR\mbox{-}BPI}$ calculates the empirical CVaR for values of
next states
$\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\bar{V}^{k}_{h+1}(s^{\prime})),\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\underline{V}^{k}_{h+1}(s^{\prime}))$
and exploration bonuses
$\frac{H}{\alpha}\sqrt{\frac{\tilde{L}(k)}{n_{k}(s,a)}},\frac{4H}{\alpha}\sqrt{\frac{S\tilde{L}(k)}{n_{k}(s,a)}}$,
to establish the optimistic and pessimistic Q-value functions
$\bar{Q}^{k}_{h}(s,a)$ and $\underline{Q}^{k}_{h}(s,a)$, respectively.
$\mathtt{ICVaR\mbox{-}BPI}$ further maintains a hypothesized optimal policy
$\pi^{k}$, which is greedy with respect to $\bar{Q}^{k}_{h}(s,a)$. Let
$\hat{\beta}^{k;\alpha,\underline{V}^{k}_{h+1}}(\cdot|s,a)$ denote the
conditional empirical transition probability in episode $k$, conditioning on
transitioning to the worst $\alpha$-portion successor states $s^{\prime}$
(i.e., with the worst $\alpha$-portion values
$\underline{V}^{k}_{h+1}(s^{\prime})$), and it satisfies
$\sum_{s^{\prime}\in\mathcal{S}}\hat{\beta}^{k;\alpha,\underline{V}^{k}_{h+1}}(s^{\prime}|s,a)\cdot\underline{V}^{k}_{h+1}(s^{\prime})=\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\underline{V}^{k}_{h+1}(s^{\prime}))$
(Line 3). Then, $\mathtt{ICVaR\mbox{-}BPI}$ computes estimation error
$G^{k}_{h}(s,a)$ and $J^{k}_{h}(s)$ using conditional transition probability
$\hat{\beta}^{k;\alpha,\underline{V}^{k}_{h+1}}(\cdot|s,a)$. Once estimation
error $J^{k}_{h}(s)$ shrinks within accuracy parameter $\varepsilon$,
$\mathtt{ICVaR\mbox{-}BPI}$ returns the hypothesized optimal policy $\pi^{k}$.

###  E.2 Proofs of Sample Complexity Upper Bound

####  E.2.1 Concentration

In the best policy identification analysis, we introduce several useful lemmas
and concentration events. Different from the regret minimization analysis
where the logrithmic factor $\log(\frac{KHSA}{\delta^{\prime}})$ in the
exploration bonuses is an universal constant, here the logrithmic factor
$\log(\frac{2k^{3}HSA}{\delta^{\prime}})$ will increase as the index of the
episode $k$ increases.

######  Lemma 12 (Concentration for $V^{*}$ – BPI).

It holds that

$\displaystyle\Pr\Bigg{[}$
$\displaystyle\left|\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V^{*}_{h}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V^{*}_{h}(s^{\prime}))\right|\leq\frac{H}{\alpha}\sqrt{\frac{\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall k>0,\ \forall h\in[H],\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{]}\geq 1-2\delta^{\prime}.$

###### Proof of Lemma 12.

Using the same analysis as Lemma 1, we have that for a fixed $k$,

$\displaystyle\Pr\Bigg{[}$
$\displaystyle\left|\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V^{*}_{h}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V^{*}_{h}(s^{\prime}))\right|\leq\frac{H}{\alpha}\sqrt{\frac{\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall h\in[H],\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{]}\geq
1-2\cdot\frac{\delta^{\prime}}{2k^{2}}.$

By a union bound over $k=1,2,\dots$, we have

$\displaystyle\Pr\Bigg{[}$
$\displaystyle\left|\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V^{*}_{h}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V^{*}_{h}(s^{\prime}))\right|\leq\frac{H}{\alpha}\sqrt{\frac{\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall k>0,\ \forall h\in[H],\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{]}$ $\displaystyle\geq$
$\displaystyle
1-2\cdot\sum_{k=1}^{\infty}\left(\frac{\delta^{\prime}}{2k^{2}}\right)$
$\displaystyle\geq$ $\displaystyle 1-2\delta^{\prime}.$

∎

######  Lemma 13 (Concentration for any $V$ – BPI).

It holds that

$\displaystyle\Pr\Bigg{[}$
$\displaystyle\left|\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V(s^{\prime}))\right|\leq\frac{2H}{\alpha}\sqrt{\frac{2S\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall V:\mathcal{S}\mapsto[0,H],\ \forall k>0,\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{]}\geq 1-2\delta^{\prime}.$

###### Proof of Lemma 13.

Using the same analysis as Lemma 2, we have that for a fixed $k$,

$\displaystyle\Pr\Bigg{[}$
$\displaystyle\left|\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V(s^{\prime}))\right|\leq\frac{2H}{\alpha}\sqrt{\frac{2S\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall V:\mathcal{S}\mapsto[0,H],\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{]}\geq
1-2\cdot\frac{\delta^{\prime}}{2k^{2}}.$

By a union bound over $k=1,2,\dots$, we have

$\displaystyle\Pr\Bigg{[}$
$\displaystyle\left|\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V(s^{\prime}))\right|\leq\frac{2H}{\alpha}\sqrt{\frac{2S\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall V:\mathcal{S}\mapsto[0,H],\ \forall k>0,\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{]}$ $\displaystyle\geq$
$\displaystyle
1-2\cdot\sum_{k=1}^{\infty}\left(\frac{\delta^{\prime}}{2k^{2}}\right)$
$\displaystyle\geq$ $\displaystyle 1-2\delta^{\prime}.$

∎

For any risk level $\alpha\in(0,1]$, function
$V:\mathcal{S}\mapsto\mathbb{R}$, $k>0$ and
$(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}$,
$\beta^{\alpha,V}(s^{\prime}|s,a)$ and
$\hat{\beta}^{k;\alpha,V}(s^{\prime}|s,a)$ are the conditional transition
probability from $(s,a)$ to $s^{\prime}$ and the conditional empirical
transition probability from $(s,a)$ to $s^{\prime}$ in episode $k$,
conditioning on transitioning to the worst $\alpha$-portion successor states
$s^{\prime}$ (i.e., with the lowest $\alpha$-portion values $V(s^{\prime})$),
respectively. $\mu^{\alpha,V}(s^{\prime}|s,a)$ and
$\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)$ denote how large the transition
probability of successor state $s^{\prime}$ and the empirical transition
probability of successor state $s^{\prime}$ in episode $k$ belong to the worst
$\alpha$-portion, respectively. It holds that

$\frac{\mu^{\alpha,V}(s^{\prime}|s,a)}{\alpha}=\beta^{\alpha,V}(s^{\prime}|s,a),$

and

$\frac{\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)}{\alpha}=\hat{\beta}^{k;\alpha,V}(s^{\prime}|s,a).$

######  Lemma 14 (Concentration for conditional transition probability).

It holds that

$\displaystyle\Pr\Bigg{[}$
$\displaystyle\left|\hat{\beta}^{k;\alpha,V}(s^{\prime}|s,a)-\beta^{\alpha,V}(s^{\prime}|s,a)\right|\leq\frac{2}{\alpha}\sqrt{\frac{2S\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall V:\mathcal{S}\mapsto\mathbb{R},\ \forall k>0,\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{]}\geq 1-2\delta^{\prime}.$

###### Proof of Lemma 14.

Using the analysis of Eq. (7), we have that for any risk level
$\alpha\in(0,1]$, function $V:\mathcal{S}\mapsto\mathbb{R}$, $k>0$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$,

$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\left|\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right|\leq
2\sum_{s^{\prime}\in\mathcal{S}}\left|\hat{p}^{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\right|.$
(21)

Using Eq. (55) in (Zanette & Brunskill, 2019) (originated from (Weissman et
al., 2003)), we have that for any fixed $k$, with probability at least
$1-2\cdot(\frac{\delta^{\prime}}{2k^{2}})$, for any
$(s,a)\in\mathcal{S}\times\mathcal{A}$,

$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\left|\hat{p}^{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\right|\leq\sqrt{\frac{2S\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$

and thus,

$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\left|\hat{\beta}^{k;\alpha,V}(s^{\prime}|s,a)-\beta^{\alpha,V}(s^{\prime}|s,a)\right|=$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\left|\frac{\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)}{\alpha}-\frac{\mu^{\alpha,V}(s^{\prime}|s,a)}{\alpha}\right|$
$\displaystyle=$
$\displaystyle\frac{\sum_{s^{\prime}\in\mathcal{S}}\left|\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right|}{\alpha}$
$\displaystyle\leq$
$\displaystyle\frac{2\sum_{s^{\prime}\in\mathcal{S}}\left|\hat{p}^{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\right|}{\alpha}$
$\displaystyle\leq$
$\displaystyle\frac{2}{\alpha}\sqrt{\frac{2S\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}}$

By a union bound over $k=1,2,\dots$, we have

$\displaystyle\Pr\Bigg{[}$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\left|\hat{\beta}^{k;\alpha,V}(s^{\prime}|s,a)-\beta^{\alpha,V}(s^{\prime}|s,a)\right|\leq\frac{2}{\alpha}\sqrt{\frac{2S\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall V:\mathcal{S}\mapsto\mathbb{R},\ \forall k>0,\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{]}$ $\displaystyle\geq$
$\displaystyle
1-2\cdot\sum_{k=1}^{\infty}\left(\frac{\delta^{\prime}}{2k^{2}}\right)$
$\displaystyle\geq$ $\displaystyle 1-2\delta^{\prime}.$

∎

To sum up, we define the following concentration events and recall event
$\mathcal{E}_{3}$.

$\displaystyle\mathcal{F}_{1}:=$
$\displaystyle\Bigg{\\{}\left|\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V^{*}_{h}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V^{*}_{h}(s^{\prime}))\right|\leq\frac{H}{\alpha}\sqrt{\frac{\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall k>0,\ \forall h\in[H],\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{\\}}$
$\displaystyle\mathcal{F}_{2}:=$
$\displaystyle\Bigg{\\{}\left|\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V(s^{\prime}))\right|\leq\frac{2H}{\alpha}\sqrt{\frac{2S\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall V:\mathcal{S}\mapsto[0,H],\ \forall k>0,\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{\\}}$
$\displaystyle\mathcal{F}_{3}:=$
$\displaystyle\Bigg{\\{}\left|\hat{\beta}^{k;\alpha,V}(s^{\prime}|s,a)-\beta^{\alpha,V}(s^{\prime}|s,a)\right|\leq\frac{2}{\alpha}\sqrt{\frac{2S\log\left(\frac{2k^{3}HSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall V:\mathcal{S}\mapsto\mathbb{R},\ \forall k>0,\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{\\}}$
$\displaystyle\mathcal{E}_{3}:=$
$\displaystyle\Bigg{\\{}n_{k}(s,a)\geq\frac{1}{2}\sum_{k^{\prime}=1}^{k-1}\sum_{h=1}^{H}w_{k^{\prime}h}(s,a)-H\log\left(\frac{HSA}{\delta^{\prime}}\right),\
\forall k>0,\ \forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{\\}}$
$\displaystyle\mathcal{F}:=$
$\displaystyle\mathcal{F}_{1}\cap\mathcal{F}_{2}\cap\mathcal{F}_{3}\cap\mathcal{E}_{3}$

######  Lemma 15.

Letting $\delta^{\prime}=\frac{\delta}{7}$, it holds that

$\displaystyle\Pr\left[\mathcal{F}\right]\geq 1-\delta.$

###### Proof of Lemma 15.

This lemma can be obtained by combining Lemmas 12-14 and 3. ∎

####  E.2.2 Optimism and Estimation Error

For any $k>0$, let
$\tilde{L}(k):=\log\left(\frac{2HSAk^{3}}{\delta^{\prime}}\right)$.

######  Lemma 16 (Optimism and Pessimism).

Suppose that event $\mathcal{F}$ holds. Then, for any $k>0$, $h\in[H]$ and
$s\in\mathcal{S}$,

$\displaystyle\bar{V}^{k}_{h}(s)$ $\displaystyle\geq V^{*}_{h}(s),$
$\displaystyle\underline{V}^{k}_{h}(s)$ $\displaystyle\leq
V^{\pi^{k}}_{h}(s).$

###### Proof of Lemma 16.

The proof of $\bar{V}^{k}_{h}(s)\geq V^{*}_{h}(s)$ is similar to Lemma 5.
Below we prove $\underline{V}^{k}_{h}(s)\leq V^{\pi^{k}}_{h}(s)$ by induction.

First, for any $k>0$, $s\in\mathcal{S}$, it holds that
$\underline{V}^{k}_{H+1}(s)=V^{\pi^{k}}_{H+1}(s)=0$.

Then, for any $k>0$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, if
$\underline{Q}^{k}_{h}(s,a)=0$, $\underline{Q}^{k}_{h}(s,a)\leq
Q^{\pi^{k}}(s,a)$ trivially holds, and otherwise,

$\displaystyle\underline{Q}^{k}_{h}(s,a)=$ $\displaystyle
r(s,a)+\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\underline{V}^{k}_{h+1}(s^{\prime}))-\frac{4H}{\alpha}\sqrt{\frac{S\tilde{L}(k)}{n_{k}(s,a)}}$
$\displaystyle\overset{\textup{(a)}}{\leq}$ $\displaystyle
r(s,a)+\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V^{\pi^{k}}_{h+1}(s^{\prime}))-\frac{4H}{\alpha}\sqrt{\frac{S\tilde{L}(k)}{n_{k}(s,a)}}$
$\displaystyle\overset{\textup{(b)}}{\leq}$ $\displaystyle
r(s,a)+\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V^{\pi^{k}}_{h+1}(s^{\prime}))$
$\displaystyle-\left(\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V^{\pi^{k}}_{h+1}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V^{\pi^{k}}_{h+1}(s^{\prime}))\right)$ $\displaystyle=$
$\displaystyle r(s,a)+\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V^{\pi^{k}}_{h+1}(s^{\prime}))$ $\displaystyle=$ $\displaystyle
Q^{\pi^{k}}(s,a),$

where (a) uses the induction hypothesis, and (b) comes from Lemma 2.

Thus, we have

$\displaystyle\underline{V}^{k}_{h}(s)=\underline{Q}^{k}_{h}(s,\pi^{k}_{h}(s))\leq
Q^{\pi^{k}}_{h}(s,\pi^{k}_{h}(s))=V^{\pi^{k}}_{h}(s),$

which concludes the proof. ∎

For any risk level $\alpha\in(0,1]$, $k>0$, $h\in[H]$ and
$(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}$,
$\hat{\beta}^{k;\alpha,\underline{V}^{k}_{h+1}}(s^{\prime}|s,a)$ is the
conditional empirical transition probability from $(s,a)$ to $s^{\prime}$ in
episode $k$, conditioning on transitioning to the worst $\alpha$-portion
successor states $s^{\prime}$ (i.e., with the lowest $\alpha$-portion values
$\underline{V}^{k}_{h+1}(s^{\prime})$). It holds that
$\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\underline{V}^{k}_{h+1}(s^{\prime}))=\sum_{s^{\prime}\in\mathcal{S}}\hat{\beta}^{k;\alpha,\underline{V}^{k}_{h+1}}(s^{\prime}|s,a)\cdot\underline{V}^{k}_{h+1}(s^{\prime})$.

######  Lemma 17 (Estimation Error).

Suppose that event $\mathcal{F}$ holds. Then, for any $k>0$,

$\displaystyle V^{*}_{1}(s_{1})-V^{\pi^{k}}_{1}(s_{1})\leq J^{k}_{1}(s_{1}).$

###### Proof of Lemma 17.

In the following, we prove by induction that for any $k>0$, $h\in[H]$ and
$s\in\mathcal{S}$,

$\displaystyle\bar{V}^{k}_{h}(s)-\underline{V}^{k}_{h}(s)\leq J^{k}_{h}(s).$
(22)

First, for any $k>0$ and $s\in\mathcal{S}$, it holds that
$\bar{V}^{k}_{H+1}(s)-\underline{V}^{k}_{H+1}(s)=J^{k}_{H+1}(s)=0$.

Then, for any $k>0$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, if
$G^{k}_{h}(s,a)=H$, $\bar{Q}^{k}_{h}(s,a)-\underline{Q}^{k}_{h}(s,a)\leq
G^{k}_{h}(s,a)$ holds trivially, and otherwise,

$\displaystyle\bar{Q}^{k}_{h}(s,a)-\underline{Q}^{k}_{h}(s,a)=$
$\displaystyle\frac{H}{\alpha}\sqrt{\frac{\tilde{L}(k)}{n_{k}(s,a)}}+\frac{4H}{\alpha}\sqrt{\frac{S\tilde{L}(k)}{n_{k}(s,a)}}$
$\displaystyle+\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\bar{V}^{k}_{h+1}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\underline{V}^{k}_{h+1}(s^{\prime}))$
$\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\frac{H\sqrt{\tilde{L}(k)}(1+4\sqrt{S})}{\alpha\sqrt{n_{k}(s,a)}}+\hat{\beta}^{k;\alpha,\underline{V}^{k}_{h+1}}(\cdot|s,a)^{\top}\left(\bar{V}^{k}_{h+1}-\underline{V}^{k}_{h+1}\right)$
$\displaystyle\overset{\textup{(b)}}{\leq}$
$\displaystyle\frac{H\sqrt{\tilde{L}(k)}(1+4\sqrt{S})}{\alpha\sqrt{n_{k}(s,a)}}+\hat{\beta}^{k;\alpha,\underline{V}^{k}_{h+1}}(\cdot|s,a)^{\top}J^{k}_{h+1}$
$\displaystyle=$ $\displaystyle G^{k}_{h}(s,a),$

where (a) uses Lemma 11 with empirical transition probability
$\hat{p}^{k}(\cdot|s,a)$, conditional empirical transition probability
$\hat{\beta}^{k;\alpha,\underline{V}^{k}_{h+1}}(\cdot|s,a)$, and values
$\bar{V}^{k}_{h+1},\underline{V}^{k}_{h+1}$, and (b) is due to the induction
hypothesis.

Thus,

$\displaystyle\bar{V}^{k}_{h}(s)-\underline{V}^{k}_{h}(s)=\bar{Q}^{k}_{h}(s,\pi^{k}_{h}(s))-\underline{Q}^{k}_{h}(s,\pi^{k}_{h}(s))\leq
G^{k}_{h}(s,\pi^{k}_{h}(s))=J^{k}_{h}(s),$

which completes the proof of Eq. (22).

Hence, for any $k>0$,

$\displaystyle\bar{V}^{k}_{1}(s_{1})-\underline{V}^{k}_{1}(s_{1})\leq
J^{k}_{1}(s_{1}).$

Using Lemma 16, we have

$\displaystyle
V^{*}_{1}(s)-V^{\pi^{k}}_{1}(s_{1})\leq\bar{V}^{k}_{1}(s_{1})-\underline{V}^{k}_{1}(s_{1})\leq
J^{k}_{1}(s_{1}).$

∎

####  E.2.3 Proof of Theorem 3

###### Proof of Theorem 3.

Suppose that event $\mathcal{F}$ holds.

First, we prove the correctness. Using Lemma 17, when algorithm
$\mathtt{ICVaR\mbox{-}BPI}$ stops, we have

$\displaystyle V^{*}_{1}(s_{1})-V^{\pi^{k}}_{1}(s_{1})\leq
J^{k}_{1}(s_{1})\leq\varepsilon.$

Thus, the output policy $\pi^{k}$ is $\varepsilon$-optimal.

Next, we prove the sample complexity.

Unfolding $J^{k}_{1}(s_{1})$, we have

$\displaystyle J^{k}_{1}(s_{1})\overset{\textup{(a)}}{=}$
$\displaystyle\min\left\\{\frac{H(1+4\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s_{1},a_{1})}}+\sum_{s_{2}\in\mathcal{S}}\hat{\beta}^{k;\alpha,\underline{V}^{k}_{2}}(s_{2}|s_{1},a_{1})\cdot
J^{k}_{2}(s_{2}),\ H\right\\}$ $\displaystyle=$
$\displaystyle\min\Bigg{\\{}\frac{H(1+4\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s_{1},a_{1})}}+\sum_{s_{2}\in\mathcal{S}}\beta^{\alpha,\underline{V}^{k}_{2}}(s_{2}|s_{1},a_{1})\cdot
J^{k}_{2}(s_{2})$
$\displaystyle\qquad\quad+\sum_{s_{2}\in\mathcal{S}}\left(\hat{\beta}^{k;\alpha,\underline{V}^{k}_{2}}(s_{2}|s_{1},a_{1})-\beta^{\alpha,\underline{V}^{k}_{2}}(s_{2}|s_{1},a_{1})\right)\cdot
J^{k}_{2}(s_{2}),\ H\Bigg{\\}}$ $\displaystyle\overset{\textup{(b)}}{\leq}$
$\displaystyle\min\Bigg{\\{}\frac{H(1+4\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s_{1},a_{1})}}+\sum_{s_{2}\in\mathcal{S}}\beta^{\alpha,\underline{V}^{k}_{2}}(s_{2}|s_{1},a_{1})\cdot
J^{k}_{2}(s_{2})$
$\displaystyle\qquad\quad+H\sum_{s_{2}\in\mathcal{S}}\left|\left(\hat{\beta}^{k;\alpha,\underline{V}^{k}_{2}}(s_{2}|s_{1},a_{1})-\beta^{\alpha,\underline{V}^{k}_{2}}(s_{2}|s_{1},a_{1})\right)\right|,\
H\Bigg{\\}}$ $\displaystyle\overset{\textup{(c)}}{\leq}$
$\displaystyle\min\Bigg{\\{}\frac{H(1+4\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s_{1},a_{1})}}+\sum_{s_{2}\in\mathcal{S}}\beta^{\alpha,\underline{V}^{k}_{2}}(s_{2}|s_{1},a_{1})\cdot
J^{k}_{2}(s_{2})+\frac{4H}{\alpha}\sqrt{\frac{S\cdot\tilde{L}(k)}{n_{k}(s_{1},a_{1})}},\
H\Bigg{\\}}$ $\displaystyle\overset{\textup{(d)}}{\leq}$
$\displaystyle\min\left\\{\frac{H(1+8\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s_{1},a_{1})}},\
H\right\\}+\sum_{s_{2}\in\mathcal{S}}\beta^{\alpha,\underline{V}^{k}_{2}}(s_{2}|s_{1},a_{1})\cdot
J^{k}_{2}(s_{2})$ $\displaystyle\overset{\textup{(e)}}{\leq}$
$\displaystyle\min\left\\{\frac{H(1+8\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s_{1},a_{1})}},\
H\right\\}+\sum_{s_{2}\in\mathcal{S}}\beta^{\alpha,\underline{V}^{k}_{2}}(s_{2}|s_{1},a_{1})\cdot$
$\displaystyle\left(\min\left\\{\frac{H(1+8\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s_{2},a_{2})}},\
H\right\\}+\sum_{s_{3}\in\mathcal{S}}\beta^{\alpha,\underline{V}^{k}_{3}}(s_{3}|s_{2},a_{2})\cdot
J^{k}_{3}(s_{3})\right)$ $\displaystyle\overset{\textup{(f)}}{\leq}$
$\displaystyle\min\left\\{\frac{H(1+8\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s_{1},a_{1})}},\
H\right\\}+\sum_{s_{2}\in\mathcal{S}}\beta^{\alpha,\underline{V}^{k}_{2}}(s_{2}|s_{1},a_{1})\cdot$
$\displaystyle\Bigg{(}\min\left\\{\frac{H(1+8\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s_{2},a_{2})}},\
H\right\\}+\sum_{s_{3}\in\mathcal{S}}\beta^{\alpha,\underline{V}^{k}_{3}}(s_{3}|s_{2},a_{2})\cdot$
$\displaystyle\Bigg{(}\dots\sum_{s_{H}\in\mathcal{S}}\beta^{\alpha,\underline{V}^{k}_{H}}(s_{H}|s_{H-1},a_{H-1})\cdot\min\left\\{\frac{H(1+8\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s_{H},a_{H})}},\
H\right\\}\Bigg{)}\Bigg{)}$ $\displaystyle\overset{\textup{(g)}}{=}$
$\displaystyle\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}w^{\textup{CVaR},\alpha,\underline{V}^{k}}_{kh}(s,a)\cdot\min\left\\{\frac{H(1+8\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s_{H},a_{H})}},\
H\right\\}$ $\displaystyle\leq$
$\displaystyle\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}w^{\textup{CVaR},\alpha,\underline{V}^{k}}_{kh}(s,a)\cdot\frac{H(1+8\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s,a)}}+\sum_{h=1}^{H}\sum_{(s,a)\notin\mathcal{L}_{k}}w^{\textup{CVaR},\alpha,\underline{V}^{k}}_{kh}(s,a)\cdot
H$

Here (b) is due to that for any $k>0$, $h\in[H]$ and $s\in\mathcal{S}$,
$J^{k}_{h}(s)\in[0,H]$. (c) comes from Lemma 14. (e) and (f) follow from
recurrently applying steps (a)-(d). (g) uses the fact that
$w^{\textup{CVaR},\alpha,\underline{V}^{k}}_{kh}(s,a)$ is defined as the
probability of visiting $(s,a)$ at step $h$ of episode $k$ under the
conditional transition probability
$\beta^{\alpha,\underline{V}_{h^{\prime}+1}^{k}}(\cdot|\cdot,\cdot)$ for each
step $h^{\prime}=1,\dots,h-1$.

Let $\tau$ denote the episode in which algorithm $\mathtt{ICVaR\mbox{-}BPI}$
stops ($\mathtt{ICVaR\mbox{-}BPI}$ will not sample any trajectory in the
stopping episode $\tau$). Then, for any $k<\tau$, we have
$\varepsilon<J^{k}_{1}(s_{1})$. Summing over $k<\tau$, we have

$\displaystyle(\tau-1)\cdot\varepsilon<$
$\displaystyle\sum_{k=1}^{\tau-1}J^{k}_{1}(s_{1})$ $\displaystyle\leq$
$\displaystyle\sum_{k=1}^{\tau-1}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}w^{\textup{CVaR},\alpha,\underline{V}^{k}}_{kh}(s,a)\cdot\frac{H(1+8\sqrt{S})\sqrt{\tilde{L}(k)}}{\alpha\sqrt{n_{k}(s,a)}}$
$\displaystyle+\sum_{k=1}^{\tau-1}\sum_{h=1}^{H}\sum_{(s,a)\notin\mathcal{L}_{k}}w^{\textup{CVaR},\alpha,\underline{V}^{k}}_{kh}(s,a)\cdot
H$ $\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\frac{H(1+8\sqrt{S})\sqrt{\tilde{L}(\tau-1)}}{\alpha}\sqrt{\sum_{k=1}^{\tau-1}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}\frac{w^{\textup{CVaR},\alpha,\underline{V}^{k}}_{kh}(s,a)}{n_{k}(s,a)}}\cdot$
$\displaystyle\sqrt{\sum_{k=1}^{\tau-1}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}w^{\textup{CVaR},\alpha,\underline{V}^{k}}_{kh}(s,a)}$
$\displaystyle+\min\left\\{\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)},\
\frac{1}{\alpha^{H-1}}\right\\}\left(4SAH^{2}\log\left(\frac{HSA}{\delta^{\prime}}\right)+5SAH^{2}\right)$
$\displaystyle\overset{\textup{(b)}}{\leq}$
$\displaystyle\frac{H(1+8\sqrt{S})\sqrt{\tilde{L}(\tau-1)}}{\alpha}\cdot\sqrt{(\tau-1)H}\cdot\sqrt{\sum_{k=1}^{\tau-1}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}\frac{w^{\textup{CVaR},\alpha,\underline{V}^{k}}_{kh}(s,a)}{n_{k}(s,a)}}$
$\displaystyle+\min\left\\{\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)},\
\frac{1}{\alpha^{H-1}}\right\\}\left(4SAH^{2}\log\left(\frac{HSA}{\delta^{\prime}}\right)+5SAH^{2}\right)$
$\displaystyle\overset{\textup{(c)}}{\leq}$
$\displaystyle\frac{(1+8\sqrt{S})H\sqrt{H\cdot\tilde{L}(\tau-1)\cdot(\tau-1)}}{\alpha}\cdot$
$\displaystyle\sqrt{\sum_{k=1}^{\tau-1}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}\frac{w^{\textup{CVaR},\alpha,\underline{V}^{k}}_{kh}(s,a)}{w_{kh}(s,a)}\cdot\frac{w_{kh}(s,a)}{n_{k}(s,a)}\mathbbm{1}\left\\{w_{kh}(s,a)\neq
0\right\\}}$
$\displaystyle+\min\left\\{\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)},\
\frac{1}{\alpha^{H-1}}\right\\}\left(4SAH^{2}\log\left(\frac{HSA}{\delta^{\prime}}\right)+5SAH^{2}\right)$
$\displaystyle\leq$
$\displaystyle\frac{(1+8\sqrt{S})H\\!\sqrt{H\\!\cdot\\!\tilde{L}(\tau-1)\\!\cdot\\!(\tau-1)}}{\alpha}\\!\cdot\\!\min\Bigg{\\{}\\!\frac{1}{\sqrt{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}},\frac{1}{\sqrt{\alpha^{H-1}}}\\!\Bigg{\\}}\cdot$
$\displaystyle\sqrt{\sum_{k=1}^{\tau-1}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}\frac{w_{kh}(s,a)}{n_{k}(s,a)}}+\min\left\\{\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)},\
\frac{1}{\alpha^{H-1}}\right\\}\cdot$
$\displaystyle\left(4SAH^{2}\log\left(\frac{HSA}{\delta^{\prime}}\right)+5SAH^{2}\right)$
$\displaystyle\overset{\textup{(d)}}{\leq}$
$\displaystyle\frac{(1+8\sqrt{S})H\sqrt{H\cdot\tilde{L}(\tau-1)\cdot(\tau-1)}}{\alpha}\min\Bigg{\\{}\frac{1}{\sqrt{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}},\frac{1}{\sqrt{\alpha^{H-1}}}\Bigg{\\}}\cdot$
$\displaystyle
2\sqrt{SA\tilde{L}(\tau-1)}+\min\left\\{\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)},\
\frac{1}{\alpha^{H-1}}\right\\}\cdot$
$\displaystyle\left(4SAH^{2}\log\left(\frac{HSA}{\delta^{\prime}}\right)+5SAH^{2}\right)$
$\displaystyle\leq$
$\displaystyle\min\left\\{\frac{1}{\sqrt{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}},\
\frac{1}{\sqrt{\alpha^{H-1}}}\right\\}\frac{18SH\cdot\tilde{L}(\tau-1)\sqrt{HA(\tau-1)}}{\alpha}$
$\displaystyle+\min\left\\{\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)},\
\frac{1}{\alpha^{H-1}}\right\\}\left(4SAH^{2}\log\left(\frac{HSA}{\delta^{\prime}}\right)+5SAH^{2}\right),$

where (a) is due to Lemma 10, (b) uses the fact that for any risk level
$\alpha\in(0,1]$, $k>0$ and $h\in[H]$,
$\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}w_{kh}^{CVaR,\alpha,\underline{V}^{k}}(s,a)=1$,
(c) comes from Lemma 8, and (d) is due to Lemma 7.

Thus, when $\log\left(\frac{HSA}{\delta^{\prime}}\right)\geq 1$, we have

$\displaystyle\tau-1\leq$
$\displaystyle\\!\min\\!\Bigg{\\{}\\!\frac{1}{\sqrt{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}},\frac{1}{\sqrt{\alpha^{H-1}}}\\!\Bigg{\\}}\frac{18SH\sqrt{HA}}{\varepsilon\alpha}\\!\cdot\\!\sqrt{\tau-1}\\!\cdot\\!\log\left(\frac{2HSA(\tau-1)^{3}}{\delta^{\prime}}\right)$
$\displaystyle+\min\left\\{\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)},\
\frac{1}{\alpha^{H-1}}\right\\}\frac{4SAH^{2}\log\left(\frac{HSA}{\delta^{\prime}}\right)+5SAH^{2}}{\varepsilon}$
$\displaystyle\leq$
$\displaystyle\\!\min\\!\Bigg{\\{}\\!\frac{1}{\sqrt{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}},\frac{1}{\sqrt{\alpha^{H-1}}}\\!\Bigg{\\}}\frac{54SH\sqrt{HA}}{\varepsilon\alpha}\\!\cdot\\!\sqrt{\tau-1}\\!\cdot\\!\log\left(\frac{2HSA(\tau-1)}{\delta^{\prime}}\right)$
$\displaystyle+\min\left\\{\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)},\
\frac{1}{\alpha^{H-1}}\right\\}\frac{9SAH^{2}}{\varepsilon}\log\left(\frac{HSA}{\delta^{\prime}}\right)$

Using Lemma 24 with $A=1$, $B=0$,
$C=\min\\{\frac{1}{\sqrt{\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}},\
\frac{1}{\sqrt{\alpha^{H-1}}}\\}\frac{54SH\sqrt{HA}}{\varepsilon\alpha}$,
$D=\min\\{\frac{1}{\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)},\
\frac{1}{\alpha^{H-1}}\\}\frac{9SAH^{2}}{\varepsilon}$, $E=0$,
$\beta=\frac{2HSA}{\delta^{\prime}}$ and $T=\tau-1$, and recalling that
algorithm $\mathtt{ICVaR\mbox{-}BPI}$ does not sample any trajectory in the
stopping episode $\tau$, we have that the number of used trajectories is
bounded by

$\displaystyle\tau-1=O\Bigg{(}$
$\displaystyle\min\Bigg{\\{}\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)},\
\frac{1}{\alpha^{H-1}}\Bigg{\\}}\frac{H^{3}S^{2}A}{\varepsilon^{2}\alpha^{2}}\cdot$
$\displaystyle\log^{2}\Bigg{(}\min\Bigg{\\{}\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)},\
\frac{1}{\alpha^{H-1}}\Bigg{\\}}\frac{HSA}{\varepsilon\alpha\delta}\Bigg{)}\Bigg{)}.$

∎

###  E.3 Sample Complexity Lower Bound

Below we present the sample complexity lower bound for Iterated CVaR RL-BPI
and provide its proof.

We say algorithm $\mathcal{A}$ is $(\delta,\varepsilon)$-correct if
$\mathcal{A}$ returns an $\varepsilon$-optimal policy $\hat{\pi}$ such that
$V^{\hat{\pi}}_{1}(s_{1})\geq V^{*}_{1}(s_{1})-\varepsilon$ with probability
$1-\delta$.

######  Theorem 5 (Sample Complexity Lower Bound).

There exists an instance of Iterated CVaR RL-BPI, where
$\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)>\alpha^{H-1}$ and the number of
trajectories used by any $(\delta,\varepsilon)$-correct algorithm is at least

$\displaystyle\Omega\Bigg{(}\frac{H^{2}A}{\varepsilon^{2}\alpha\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}\log\left(\frac{1}{\delta}\right)\Bigg{)}.$

In addition, there also exists an instance of Iterated CVaR RL-BPI, where
$\alpha^{H-1}>\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)$ and the number of trajectories used
by any $(\delta,\varepsilon)$-correct algorithm is at least

$\displaystyle\Omega\Bigg{(}\frac{A}{\alpha^{H-1}\varepsilon^{2}}\log\left(\frac{1}{\delta}\right)\Bigg{)}.$

Theorem 5 corroborates that when $\alpha$ is small, the factor
$\min_{\pi,h,s:\ w_{\pi,h}(s)>0}w_{\pi,h}(s)$ is unavoidable in general. This
reveals the intrinsic hardness of Iterated CVaR RL, i.e., when the agent is
highly risk-sensitive, she needs to spend a number of trajectories on
exploring critical but hard-to-reach states in order to identify an optimal
policy.

###### Proof of Theorem 5.

This proof uses a similar analytical procedure as Theorem 2 in (Dann &
Brunskill, 2015).

First, we consider the instance in Figure 6 as in the proof of Theorem 2,
where $\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)>\alpha^{H-1}$. Below we prove that
on this instance any algorithm must suffer a
$O(\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}\cdot\frac{H^{3}S^{2}A}{\varepsilon^{2}\alpha^{2}}\log(\frac{1}{\delta}))$
regret.

Fix an algorithm $\mathcal{A}$. Define
$\mathcal{E}_{s_{n}}:=\\{\hat{\pi}(s_{n})=a_{J}\\}$ as the event that the
output policy $\hat{\pi}$ of algorithm $\mathcal{A}$ chooses the optimal
action in state $s_{n}$.

Using the similar analysis as in the proof of Theorem 2 (Eq. (15)), we have

$\displaystyle V^{*}_{1}(s_{1})-V^{\pi}_{1}(s_{1})=$ $\displaystyle
0.6(H-n)\cdot\frac{\eta}{\alpha}\cdot(1-\mathbbm{1}\left\\{\mathcal{E}_{s_{n}}\right\\}).$

For $\pi$ to be $\varepsilon$-optimal, we need

$\displaystyle\varepsilon\geq
V^{*}_{1}(s_{1})-V^{\pi}_{1}(s_{1})=0.6(H-n)\cdot\frac{\eta}{\alpha}\cdot(1-\mathbbm{1}\left\\{\mathcal{E}_{s_{n}}\right\\}),$

which is equivalent to

$\displaystyle\mathbbm{1}\left\\{\mathcal{E}_{s_{n}}\right\\}\geq
1-\frac{\varepsilon\alpha}{0.6(H-n)\cdot\eta}.$

Let $\eta=\frac{8e^{4}\varepsilon\alpha}{0.6c_{0}(H-n)}$ for some constant
$c_{0}$ and small enough $\varepsilon$. Then, for $\pi$ to be
$\varepsilon$-optimal, we need

$\displaystyle\mathbbm{1}\left\\{\mathcal{E}_{s_{n}}\right\\}\geq
1-\frac{c_{0}}{8e^{4}}.$

Let $\phi:=1-\frac{c_{0}}{8e^{4}}$. For algorithm $\mathcal{A}$ to be
$(\varepsilon,\delta)$-correct, we need

$\displaystyle 1-\delta\leq$ $\displaystyle\Pr[V^{*}-V^{\pi}\geq\varepsilon]$
$\displaystyle\leq$
$\displaystyle\Pr[\mathbbm{1}\left\\{\mathcal{E}_{s_{n}}\right\\}\geq\phi]$
$\displaystyle\leq$
$\displaystyle\frac{\mathbb{E}[\mathcal{E}_{s_{n}}]}{\phi}$
$\displaystyle\leq$ $\displaystyle\frac{1}{\phi}\Pr[\mathcal{E}_{s_{n}}],$

which is equivalent to

$\displaystyle\Pr[\bar{\mathcal{E}}_{s_{n}}]=1-\Pr[\mathcal{E}_{s_{n}}]\leq
1-\phi+\phi\delta.$

Recall that $0<\alpha<\frac{1}{3}$. For any $j\in[A]$,
$\textup{KL}(p_{unif}(s_{n},a_{j})\|p_{j}(s_{n},a_{j}))=\textup{KL}(\mathtt{Ber}(\alpha)\|\mathtt{Ber}(\alpha-\eta))\leq\frac{\eta^{2}}{(\alpha-\eta)(1-\alpha+\eta)}\leq\frac{c_{1}\cdot\eta^{2}}{\alpha}$
for some constant $c_{1}$ and small enough $\eta$. Let $V_{s_{n}}$ be the
number of times that algorithm $\mathcal{A}$ visited state $s_{n}$. To ensure
$\Pr[\bar{\mathcal{E}}_{s_{n}}]\leq 1-\phi+\phi\delta$, we need

$\displaystyle\mathbb{E}[V_{s_{n}}]\geq$
$\displaystyle\sum_{j=1}^{A}\frac{1}{\textup{KL}(p_{unif}(s_{n},a_{j})\|p_{j}(s_{n},a_{j}))}\log\left(\frac{c_{2}}{1-\phi+\phi\delta}\right)$
$\displaystyle\geq$ $\displaystyle\frac{\alpha
A}{c_{1}\cdot\eta^{2}}\log\left(\frac{c_{2}}{1-\phi+\phi\delta}\right)$
$\displaystyle=$ $\displaystyle\frac{\alpha A\cdot
0.6^{2}c_{0}^{2}(H-n)^{2}}{c_{1}\cdot
64e^{8}\varepsilon^{2}\alpha^{2}}\log\left(\frac{c_{2}}{\frac{c_{0}}{8e^{4}}+\delta}\right)$

for some constant $c_{2}$.

Let $c_{0}$ be a small constant such that $\frac{c_{0}}{8e^{4}}<\delta$. Let
$w(s_{n})$ denote the probability of visiting $s_{n}$ in an episode, and this
probability is the same for all policies. Let $\tau$ denote the number of
trajectories required by $\mathcal{A}$ to be $(\varepsilon,\delta)$-correct.
Then, $\tau$ must satisfy

$\displaystyle\tau\geq$ $\displaystyle\frac{A\cdot
0.6^{2}c_{0}^{2}(H-n)^{2}}{c_{1}\cdot 64e^{8}\varepsilon^{2}\alpha\cdot
w(s_{n})}\log\left(\frac{c_{2}}{\frac{c_{0}}{8e^{4}}+\delta}\right)$
$\displaystyle=$
$\displaystyle\Omega\left(\frac{H^{2}A}{\varepsilon^{2}\alpha\cdot
w(s_{n})}\log\left(\frac{1}{\delta}\right)\right).$

Recall that $n<\frac{1}{2}H$ and $0<\alpha<\mu<\frac{1}{3}$. Thus, in the
constructed instance (Figure 6), we have that
$\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)=w(s_{n})=\mu^{n-1}>\alpha^{H-1}$,
and

$\displaystyle\tau=$
$\displaystyle\Omega\left(\frac{H^{2}A}{\varepsilon^{2}\alpha\cdot\min\limits_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}\log\left(\frac{1}{\delta}\right)\right).$

Next, we consider the instance in Figure 7 as in the proof of Theorem 2, where
$\alpha^{H-1}>\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)$. Below we prove that on this
instance any algorithm must suffer a
$O(\frac{1}{\alpha^{H-1}}\cdot\frac{H^{3}S^{2}A}{\varepsilon^{2}\alpha^{2}}\log(\frac{1}{\delta}))$
regret.

Define $\mathcal{E}_{s_{n}}:=\\{\hat{\pi}(s_{n})=a_{J}\\}$ as the event that
the output policy $\hat{\pi}$ of algorithm $\mathcal{A}$ chooses the optimal
action in state $s_{n}$.

Using the similar analysis as in the proof of Theorem 2 (Eq. (18)), we have

$\displaystyle V^{*}_{1}(s_{1})-V^{\pi}_{1}(s_{1})=$
$\displaystyle\frac{0.6\eta}{\alpha}\cdot(1-\mathbbm{1}\left\\{\mathcal{E}_{s_{n}}\right\\}).$

For $\pi$ to be $\varepsilon$-optimal, we need

$\displaystyle\varepsilon\geq
V^{*}_{1}(s_{1})-V^{\pi}_{1}(s_{1})=\frac{0.6\eta}{\alpha}\cdot(1-\mathbbm{1}\left\\{\mathcal{E}_{s_{n}}\right\\}),$

which is equivalent to

$\displaystyle\mathbbm{1}\left\\{\mathcal{E}_{s_{n}}\right\\}\geq
1-\frac{\varepsilon\alpha}{0.6\eta}.$

Let $\eta=\frac{8e^{4}\varepsilon\alpha}{0.6c_{0}}$ for some constant $c_{0}$
and small enough $\varepsilon$. Then, for $\pi$ to be $\varepsilon$-optimal,
we need

$\displaystyle\mathbbm{1}\left\\{\mathcal{E}_{s_{n}}\right\\}\geq
1-\frac{c_{0}}{8e^{4}}.$

Let $\phi:=1-\frac{c_{0}}{8e^{4}}$. For algorithm $\mathcal{A}$ to be
$(\varepsilon,\delta)$-correct, we need

$\displaystyle 1-\delta\leq$ $\displaystyle\Pr[V^{*}-V^{\pi}\geq\varepsilon]$
$\displaystyle\leq$
$\displaystyle\Pr[\mathbbm{1}\left\\{\mathcal{E}_{s_{n}}\right\\}\geq\phi]$
$\displaystyle\leq$
$\displaystyle\frac{\mathbb{E}[\mathcal{E}_{s_{n}}]}{\phi}$
$\displaystyle\leq$ $\displaystyle\frac{1}{\phi}\Pr[\mathcal{E}_{s_{n}}],$

which is equivalent to

$\displaystyle\Pr[\bar{\mathcal{E}}_{s_{n}}]=1-\Pr[\mathcal{E}_{s_{n}}]\leq
1-\phi+\phi\delta.$

Recall that $0<\alpha<\frac{1}{4}$. For any $j\in[A]$,
$\textup{KL}(p_{unif}(s_{n},a_{j})\|p_{j}(s_{n},a_{j}))=\textup{KL}(\mathtt{Ber}(\alpha)\|\mathtt{Ber}(\alpha-\eta))\leq\frac{\eta^{2}}{(\alpha-\eta)(1-\alpha+\eta)}\leq\frac{c_{1}\cdot\eta^{2}}{\alpha}$
for some constant $c_{1}$ and small enough $\eta$. Let $V_{s_{n}}$ be the
number of times that algorithm $\mathcal{A}$ visited state $s_{n}$. To ensure
$\Pr[\bar{\mathcal{E}}_{s_{n}}]\leq 1-\phi+\phi\delta$, we need

$\displaystyle\mathbb{E}[V_{s_{n}}]\geq$
$\displaystyle\sum_{j=1}^{A}\frac{1}{\textup{KL}(p_{unif}(s_{n},a_{j})\|p_{j}(s_{n},a_{j}))}\log\left(\frac{c_{2}}{1-\phi+\phi\delta}\right)$
$\displaystyle\geq$ $\displaystyle\frac{\alpha
A}{c_{1}\cdot\eta^{2}}\log\left(\frac{c_{2}}{1-\phi+\phi\delta}\right)$
$\displaystyle=$ $\displaystyle\frac{\alpha A\cdot
0.6^{2}c_{0}^{2}}{c_{1}\cdot
64e^{8}\varepsilon^{2}\alpha^{2}}\log\left(\frac{c_{2}}{\frac{c_{0}}{8e^{4}}+\delta}\right)$

for some constant $c_{2}$.

Let $c_{0}$ be a small constant such that $\frac{c_{0}}{8e^{4}}<\delta$. Let
$w(s_{n})$ denote the probability of visiting $s_{n}$ in an episode, and this
probability is the same for all policies. Let $\tau$ denote the number of
trajectories required by $\mathcal{A}$ to be $(\varepsilon,\delta)$-correct.
Then, $\tau$ must satisfy

$\displaystyle\tau\geq$ $\displaystyle\frac{A\cdot
0.6^{2}c_{0}^{2}}{c_{1}\cdot 64e^{8}\varepsilon^{2}\alpha\cdot
w(s_{n})}\log\left(\frac{c_{2}}{\frac{c_{0}}{8e^{4}}+\delta}\right)$
$\displaystyle=$ $\displaystyle\Omega\left(\frac{A}{\varepsilon^{2}\alpha\cdot
w(s_{n})}\log\left(\frac{1}{\delta}\right)\right).$

Recall that $n=H-1$. Thus, in the constructed instance (Figure 7), we have
that $w(s_{n})=\alpha^{n-1}=\alpha^{H-2}$, and

$\displaystyle\tau=$
$\displaystyle\Omega\left(\frac{A}{\varepsilon^{2}\alpha\cdot\alpha^{H-2}\log\left(\frac{1}{\delta}\right)}\right)$
$\displaystyle=$
$\displaystyle\Omega\left(\frac{A}{\varepsilon^{2}\alpha^{H-1}\log\left(\frac{1}{\delta}\right)}\right).$

∎

##  Appendix F Proofs for Worst Path RL

In this section, we provide the proofs of regret upper and lower bounds
(Theorems 4 and 6) for Worst Path RL.

###  F.1 Proofs of Regret Upper Bound

####  F.1.1 Concentration

Recall that for any $k>0$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,
$n_{k}(s,a)$ is the number of times that $(s,a)$ was visited before episode
$k$. For any $k>0$ and
$(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}$, let
$n_{k}(s^{\prime},s,a)$ denote the number of times that $(s,a)$ was visited
and transitioned to $s^{\prime}$ before episode $k$.

For any policy $\pi$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, let
$\upsilon_{\pi}(s,a)$ and $\upsilon_{\pi}(s)$ denote the probabilities that
$(s,a)$ and $s$ are visited at least once in an episode under policy $\pi$,
respectively.

######  Lemma 18.

It holds that

$\displaystyle\Pr\left[n_{k}(s,a)\geq\frac{1}{2}\sum_{k^{\prime}=1}^{k-1}\upsilon_{\pi^{k^{\prime}}}(s,a)-\log\left(\frac{SA}{\delta^{\prime}}\right),\
\forall k>0,\ \forall(s,a)\in\mathcal{S}\times\mathcal{A}\right]\geq
1-\delta^{\prime}$

###### Proof of Lemma 18.

For any $k$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, conditioning on the
filtration generated by episodes $1,\dots,k-1$, whether the algorithm visited
$(s,a)$ at least once in episode $k$ is a Bernoulli random variable with
success probability $\upsilon_{\pi^{k}}(s,a)$. Then, using Lemma F.4 in (Dann
et al., 2017), we can obtain this lemma. ∎

######  Lemma 19.

It holds that

$\displaystyle\Pr\Bigg{\\{}n_{k}(s^{\prime},s,a)\geq$
$\displaystyle\frac{1}{2}\cdot n_{k}(s,a)\cdot
p(s^{\prime}|s,a)-2\log\left(\frac{SA}{\delta^{\prime}}\right),$
$\displaystyle\forall k>0,\
\forall(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}\Bigg{\\}}\geq
1-\delta^{\prime}.$

###### Proof of Lemma 19.

For any $k$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,
conditioning on the event $\\{s^{k}_{h}=s,a^{k}_{h}=a\\}$, the indicator
$\mathbbm{1}\left\\{s^{k}_{h+1}=s^{\prime}\right\\}$ is a Bernoulli random
variable with success probability $p(s^{\prime}|s,a)$. Then, using Lemma F.4
in (Dann et al., 2017), we can obtain this lemma. ∎

To summarize, we define some concentration events which will be used in the
following proof.

$\displaystyle\mathcal{G}_{1}:=$
$\displaystyle\Bigg{\\{}n_{k}(s,a)\geq\frac{1}{2}\sum_{k^{\prime}=1}^{k-1}\upsilon_{\pi^{k^{\prime}}}(s,a)-\log\left(\frac{SA}{\delta^{\prime}}\right),\
\forall k>0,\ \forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{\\}}$
$\displaystyle\mathcal{G}_{2}:=$
$\displaystyle\Bigg{\\{}n_{k}(s^{\prime},s,a)\geq\frac{1}{2}\cdot
n_{k}(s,a)\cdot
p(s^{\prime}|s,a)-2\log\left(\frac{SA}{\delta^{\prime}}\right),\ \forall k>0,\
\forall(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}\Bigg{\\}}$
$\displaystyle\mathcal{G}:=$ $\displaystyle\mathcal{G}_{1}\cap\mathcal{G}_{2}$

######  Lemma 20.

Letting $\delta^{\prime}=\frac{\delta}{2}$, it holds that

$\displaystyle\Pr\left[\mathcal{G}\right]\geq 1-\delta.$

###### Proof of Lemma 20.

This lemma can be obtained by combining Lemmas 18 and 19. ∎

####  F.1.2 Overestimation and Good Stage

Recall that in Worst Path RL, for any $k>0$, $h\in[H]$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$,
$Q^{*}_{h}(s,a):=r(s,a)+\min_{s^{\prime}\sim
p(\cdot|s,a)}(V^{*}_{h+1}(s^{\prime}))$ and
$V^{*}_{h}(s):=\max_{a\in\mathcal{A}}Q^{*}_{h}(s,a)$. In addition,
$\hat{Q}^{k}_{h}(s,a):=r(s,a)+\min_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\hat{V}^{k}_{h+1}(s^{\prime}))$
and $\hat{V}^{k}_{h}(s):=\max_{a\in\mathcal{A}}\hat{Q}^{k}_{h}(s,a)$.

######  Lemma 21 (Overestimation).

For any $k>0$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,
$\hat{Q}^{k}_{h}(s,a)\geq Q^{*}_{h}(s,a)$ and $\hat{V}^{k}_{h}(s)\geq
V^{*}_{h}(s)$.

Remark. Lemma 21 shows that if the Q-value of some state-action pair is not
accurately estimated, it can only be overestimated (not underestimated). This
feature is due to the $\min$ metric in the Worst Path RL formulation (Eq.
(2)).

###### Proof of Lemma 21.

We prove this lemma by induction.

For any $k>0$ and $s\in\mathcal{S}$, $\hat{V}^{k}_{H+1}(s)=V^{*}_{H+1}(s)=0$.

For any $k>0$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, since
$r(s,a)$ is known and $\hat{V}^{k}_{h+1}(s)\geq V^{*}_{h+1}(s)$ (due to the
induction hypothesis), if $\hat{p}^{k}(\cdot|s,a)$ has detected all successor
states, then $\hat{Q}^{k}_{h}(s,a)\geq Q^{*}_{h}(s,a)$. Otherwise, if
$\hat{p}^{k}(\cdot|s,a)$ has not detected all successor states, due to the
property of $\min$, we also have $\hat{Q}^{k}_{h}(s,a)\geq Q^{*}_{h}(s,a)$.
Therefore, we have $\hat{V}^{k}_{h}(s)\geq V^{*}_{h}(s)$, which completes the
proof. ∎

######  Lemma 22 (Non-increasing Estimated Value).

For any $k_{1},k_{2}>0$ such that $k_{1}\leq k_{2}$, $h\in[H]$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$,
$\hat{Q}^{k_{1}}_{h}(s,a)\geq\hat{Q}^{k_{2}}_{h}(s,a)$ and
$\hat{V}^{k_{1}}_{h}(s)\geq V^{k_{2}}_{h}(s)$.

###### Proof of Lemma 22.

We prove this lemma by induction.

For any $k_{1},k_{2}>0$ such that $k_{1}\leq k_{2}$ and $s\in\mathcal{S}$,
$\hat{V}^{k_{1}}_{H+1}(s)=V^{k_{2}}_{H+1}(s)=0$.

For any $k_{1},k_{2}>0$ such that $k_{1}\leq k_{2}$, $h\in[H]$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$, since $r(s,a)$ is known and
$\hat{V}^{k_{1}}_{h+1}(s)\geq V^{k_{2}}_{h+1}(s)$ (due to the induction
hypothesis), if $\hat{p}^{k_{1}}(\cdot|s,a)$ has detected all successor
states, then $\hat{Q}^{k_{1}}_{h}(s,a)\geq\hat{Q}^{k_{2}}_{h}(s,a)$.
Otherwise, if $\hat{p}^{k_{1}}(\cdot|s,a)$ has not detected all successor
states, due to the $\min$ metric and that $\hat{p}^{k_{2}}(\cdot|s,a)$ will
detect more (or the same) successor states than $\hat{p}^{k_{1}}(\cdot|s,a)$,
we also have $\hat{Q}^{k_{1}}_{h}(s,a)\geq\hat{Q}^{k_{2}}_{h}(s,a)$.
Therefore, we have $\hat{V}^{k_{1}}_{h}(s)\geq V^{k_{2}}_{h}(s)$, which
completes the proof. ∎

Remark. Combining Lemmas 21 and 22, we have that as the episode $k$ increases,
the estimated value $\hat{Q}^{k}_{h}(s,a)$ ($\hat{V}^{k}_{h}(s)$) will
decrease to its true value $Q^{*}_{h}(s,a)$ ($V^{*}_{h}(s)$) or keep the same.

Let $\mathcal{S}_{*}:=\\{s\in\mathcal{S}:v_{\pi^{*}}(s)>0\\}$ denote the set
of states which are reachable for an optimal policy.

######  Lemma 23 (Good Stage).

If there exists some episode $\bar{k}>0$ which satisfies that for any
$h\in[H]$ and $s\in\mathcal{S}_{*}$, $\hat{V}^{\bar{k}}_{h}(s)=V^{*}_{h}(s)$
and $\pi^{\bar{k}}_{h}(s)$ suggests an optimal action, then we have that for
any $k\geq\bar{k}$, $h\in[H]$ and $s\in\mathcal{S}_{*}$,
$\hat{V}^{k}_{h}(s)=V^{*}_{h}(s)$ and $\pi^{k}_{h}(s)$ suggests an optimal
action, and thus for any $k\geq\bar{k}$, algorithm $\mathtt{MaxWP}$ takes an
optimal policy.

Remark. Lemma 23 reveals that if in some episode $\bar{k}$, for any step $h$
and state $s\in\mathcal{S}_{*}$, algorithm $\mathtt{MaxWP}$ estimates the
V-value accurately and chooses an optimal action, then hereafter, algorithm
$\mathtt{MaxWP}$ always takes an optimal policy.

We say algorithm $\mathtt{MaxWP}$ enters a _good stage_ , if starting from
some episode $\bar{k}$, for any $k\geq\bar{k}$, $h\in[H]$ and
$s\in\mathcal{S}_{*}$, $\hat{V}^{k}_{h}(s)=V^{*}_{h}(s)$ and $\pi^{k}_{h}(s)$
suggests an optimal action.

###### Proof of Lemma 23.

Suppose that in episode $\bar{k}$, we have that for any $h\in[H]$ and
$s\in\mathcal{S}_{*}$, $\hat{V}^{\bar{k}}_{h}(s)=V^{*}_{h}(s)$ and
$\pi^{\bar{k}}_{h}(s)$ suggests an optimal action. This is equivalent to the
statement that in episode $\bar{k}$, for any $h\in[H]$ and
$s\in\mathcal{S}_{*}$, for each optimal action $a$ (such that
$Q^{*}_{h}(s,a)=V^{*}_{h}(s)$), $\hat{Q}^{\bar{k}}_{h}(s,a)=Q^{*}_{h}(s,a)$,
and for each suboptimal action $a$ (such that $Q^{*}_{h}(s,a)<V^{*}_{h}(s)$),
$Q^{*}_{h}(s,a)\leq\hat{Q}^{\bar{k}}_{h}(s,a)<V^{*}_{h}(s)$.

Using Lemmas 21 and 22, we have that for any $h\in[H]$ and
$s\in\mathcal{S}_{*}$, as $k$ increases, $\hat{Q}^{k}_{h}(s,a)$ will either
decrease to the true value $Q^{*}_{h}(s,a)$ or keep the same. Therefore, we
have that for any $k\geq\bar{k}$, $h\in[H]$ and $s\in\mathcal{S}_{*}$, for
each optimal action $a$, $\hat{Q}^{\bar{k}}_{h}(s,a)=Q^{*}_{h}(s,a)$, and for
each suboptimal action $a$,
$Q^{*}_{h}(s,a)\leq\hat{Q}^{\bar{k}}_{h}(s,a)<V^{*}_{h}(s)$, which completes
the proof.

∎

####  F.1.3 Proof of Theorem 4

###### Proof of Theorem 4.

Suppose that event $\mathcal{G}$ holds.

Let

$\bar{T}:=\sum\limits_{(s,a)}\frac{1}{\min\limits_{\begin{subarray}{c}\pi:\
\upsilon_{\pi}(s,a)>0\end{subarray}}\upsilon_{\pi}(s,a)\cdot\min\limits_{s^{\prime}\in\textup{supp}(p(\cdot|s,a))}p(s^{\prime}|s,a)}\cdot
8\left(2\log\left(\frac{SA}{\delta}\right)+1\right).$

For any $(s,a)\in\mathcal{S}\times\mathcal{A}$, let

$\bar{T}(s,a):=\frac{1}{\min\limits_{\begin{subarray}{c}\pi:\
\upsilon_{\pi}(s,a)>0\end{subarray}}\upsilon_{\pi}(s,a)\cdot\min\limits_{s^{\prime}\in\textup{supp}(p(\cdot|s,a))}p(s^{\prime}|s,a)}\cdot
8\left(2\log\left(\frac{SA}{\delta}\right)+1\right).$

It holds that
$\bar{T}=\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\bar{T}(s,a)$.

According to Lemma 23, in order to prove Theorem 4, it suffices to prove that
in episode $\bar{T}+1$, for any $h\in[H]$ and $s\in\mathcal{S}_{*}$,
$\hat{V}^{\bar{T}+1}_{h}(s)=V^{*}_{h}(s)$ and $\pi^{\bar{T}+1}_{h}(s)$
suggests an optimal action, i.e., algorithm $\mathtt{MaxWP}$ has entered the
good stage in episode $\bar{T}+1$. We prove this statement by contradiction.

Suppose that in episode $\bar{T}+1$, there exists some $h\in[H]$ and some
$s\in\mathcal{S}_{*}$ which satisfy that
$\hat{V}^{\bar{T}+1}_{h}(s)>V^{*}_{h}(s)$ (the value function can only be
overestimated) or $\pi^{\bar{T}+1}_{h}(s)$ suggests a suboptimal action.

If the policy $\pi^{\bar{T}+1}$ taken in episode $\bar{T}+1$ is optimal, then
there exists some $h\in[H]$, some $s\in\mathcal{S}_{*}$ and some optimal
action $a$ which satisfy that $v_{\pi^{\bar{T}+1}}(s)>0$ and
$\hat{Q}^{\bar{T}+1}_{h}(s,a)>Q^{*}_{h}(s,a)$. Otherwise, if the policy
$\pi^{\bar{T}+1}$ taken in episode $\bar{T}+1$ is suboptimal, then there
exists some $h\in[H]$, some $s\in\mathcal{S}_{*}$ and some suboptimal action
$a$ which satisfy that $v_{\pi^{\bar{T}+1}}(s)>0$ and
$\hat{Q}^{\bar{T}+1}_{h}(s,a)>Q^{*}_{h}(s,a)$. Hence, no matter which of the
above cases happen, we have that there exists some $h\in[H]$ and some
$(s,a)\in\mathcal{S}\times\mathcal{A}$ which satisfy that
$v_{\pi^{\bar{T}+1}}(s,a)>0$ and
$\hat{Q}^{\bar{T}+1}_{h}(s,a)>Q^{*}_{h}(s,a)$.

Under the $\min$ metric in Worst Path RL, the overestimation of a Q-value
comes from the following reasons: (i) Algorithm $\mathtt{MaxWP}$ has not
detected the successor state with the lowest V-value. (ii) The V-values of
successor states at the next step are overestimated.

If the overestimation of $\hat{Q}^{\bar{T}+1}_{h}(s,a)$ comes from the
overestimation of the V-values at the next step (reason (ii)), then we have
that at the next step, there exists some state-action pair whose Q-value is
overestimated. Then, we can trace the overestimation from $(s,a)$ at step $h$
to some $(s^{\prime},a^{\prime})$ at some step $h^{\prime}\geq h$, which
satisfies that
$\hat{Q}^{\bar{T}+1}_{h^{\prime}}(s^{\prime},a^{\prime})>Q^{*}_{h^{\prime}}(s^{\prime},a^{\prime})$
and $\hat{V}^{\bar{T}+1}_{h^{\prime}+1}(x)=V^{*}_{h^{\prime}+1}(x)$ for any
$x\in\mathcal{S}$. In other words, the overestimation of
$\hat{Q}^{\bar{T}+1}_{h^{\prime}}(s^{\prime},a^{\prime})$ is purely due to
that at $(s^{\prime},a^{\prime})$, algorithm $\mathtt{MaxWP}$ has not detected
the successor state $x$ with the lowest value $V^{*}_{h^{\prime}+1}(x)$.

For any $k>0$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, let
$\mathcal{T}^{k}(s,a)=\\{k^{\prime}<k:\upsilon_{\pi^{k^{\prime}}}(s,a)>0\\}$
denote the set of episodes where $(s,a)$ is reachable before episode $k$. We
consider the following two cases according to whether
$|\mathcal{T}^{\bar{T}+1}(s^{\prime},a^{\prime})|$ is large enough to detect
all successor states of $(s^{\prime},a^{\prime})$.

##### Case (1):

If
$|\mathcal{T}^{\bar{T}+1}(s^{\prime},a^{\prime})|\geq\bar{T}(s^{\prime},a^{\prime})$,
using Lemma 18, we have

$\displaystyle n_{k}(s^{\prime},a^{\prime})\geq$
$\displaystyle\frac{1}{2}\sum_{k^{\prime}=1}^{k-1}\upsilon_{\pi^{k^{\prime}}}(s^{\prime},a^{\prime})-\log\left(\frac{SA}{\delta^{\prime}}\right)$
$\displaystyle\geq$
$\displaystyle\frac{1}{2}\cdot\bar{T}(s^{\prime},a^{\prime})\cdot\min\limits_{\begin{subarray}{c}\pi:\
\upsilon_{\pi}(s^{\prime},a^{\prime})>0\end{subarray}}\upsilon_{\pi}(s^{\prime},a^{\prime})-\log\left(\frac{SA}{\delta}\right)$
$\displaystyle=$
$\displaystyle\frac{4\left(2\log\left(\frac{SA}{\delta}\right)+1\right)}{\min\limits_{s^{\prime}\in\textup{supp}(p(\cdot|s,a))}p(s^{\prime}|s,a)}-\log\left(\frac{SA}{\delta}\right)$
$\displaystyle\geq$
$\displaystyle\frac{2\left(2\log\left(\frac{SA}{\delta}\right)+1\right)}{\min\limits_{s^{\prime}\in\textup{supp}(p(\cdot|s,a))}p(s^{\prime}|s,a)}$

Then, using Lemma 19, we have that for any
$s\in\textup{supp}(p(\cdot|s^{\prime},a^{\prime}))$,

$\displaystyle n_{k}(s,s^{\prime},a^{\prime})\geq$
$\displaystyle\frac{1}{2}\cdot
n_{k}(s^{\prime},a^{\prime})\cdot\min\limits_{s\in\textup{supp}(p(\cdot|s^{\prime},a^{\prime}))}p(s|s^{\prime},a^{\prime})-2\log\left(\frac{SA}{\delta}\right)$
$\displaystyle\geq$ $\displaystyle\frac{1}{2}\cdot
2\left(2\log\left(\frac{SA}{\delta}\right)+1\right)-2\log\left(\frac{SA}{\delta}\right)$
$\displaystyle=$ $\displaystyle 1$

which contradicts that $\hat{Q}^{k}_{h^{\prime}}(s^{\prime},a^{\prime})$ is
overestimated.

##### Case (2):

If
$|\mathcal{T}^{\bar{T}+1}(s^{\prime},a^{\prime})|<\bar{T}(s^{\prime},a^{\prime})$,
we say the overestimation in episode $\bar{T}+1$ is due to the insufficient
visitation on $(s^{\prime},a^{\prime})$. Then, among episodes
$1,\dots,\bar{T}$, we exclude the episodes contained in
$\mathcal{T}^{\bar{T}+1}(s^{\prime},a^{\prime})$, i.e., we ignore the episodes
where $(s^{\prime},a^{\prime})$ is reachable and can be the source of the
overestimation. Then, the number of excluded episodes due to
$(s^{\prime},a^{\prime})$ is
$|\mathcal{T}^{\bar{T}+1}(s^{\prime},a^{\prime})|<\bar{T}(s^{\prime},a^{\prime})$.

According to Lemma 23, since episode $\bar{T}+1$ has not entered the good
stage, for any $k\leq\bar{T}$, episode $k$ has also not entered the good
stage. Then, for any $k\leq\bar{T}$, there exists some $h\in[H]$ and some
$s\in\mathcal{S}_{*}$ which satisfy that $\hat{V}^{k}_{h}(s)>V^{*}_{h}(s)$ or
$\pi^{k}_{h}(s)$ suggests a suboptimal action. This implies that there exists
some $h\in[H]$ and some $(s,a)\in\mathcal{S}\times\mathcal{A}$ which satisfy
that $v_{\pi^{k}}(s,a)>0$ and $\hat{Q}^{k}_{h}(s,a)>Q^{*}_{h}(s,a)$.

Consider the last episode $k$ among episodes $1,\dots,\bar{T}$ which is not
excluded. Using the above argument, let $(s^{k},a^{k})$ denote the source of
overestimation in episode $k$ which satisfies that
$\hat{Q}^{k}_{h^{\prime}}(s^{\prime},a^{\prime})>Q^{*}_{h^{\prime}}(s^{\prime},a^{\prime})$
and $\hat{V}^{k}_{h^{\prime}+1}(x)=V^{*}_{h^{\prime}+1}(x)$ for any
$x\in\mathcal{S}$. Since we have excluded all the episodes where
$(s^{\prime},a^{\prime})$ is reachable among episodes $1,\dots,\bar{T}$ and
episode $k$ is not excluded, it holds that
$(s^{k},a^{k})\neq(s^{\prime},a^{\prime})$. We repeat the above analysis on
$\mathcal{T}^{k}(s^{k},a^{k})$. If Case (1) happens, i.e.,
$|\mathcal{T}^{k}(s^{k},a^{k})|\geq\bar{T}(s^{k},a^{k})$, then we can derive a
contradiction and complete the proof. If Case (2) happens, i.e.,
$|\mathcal{T}^{k}(s^{k},a^{k})|<\bar{T}(s^{k},a^{k})$, we exclude episode $k$
and the episodes contained in $\mathcal{T}^{k}(s^{k},a^{k})$. Then, the number
of excluded episodes due to $(s^{k},a^{k})$ among episodes $1,\dots,\bar{T}$
is at most $|\mathcal{T}^{k}(s^{k},a^{k})|+1\leq|\bar{T}(s^{k},a^{k})|$.

We repeat the above procedure. Once Case (1) happens, we can derive a
contradiction and complete the proof. Otherwise, if Case (2) keeps happening,
we will exclude the episodes due to the reachability and possible
overestimation of $(s,a)$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$, and
the total number of excluded episodes is strictly smaller than
$\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\bar{T}(s,a)=\bar{T}$. Thus, there
exists some episode $k_{0}$ among episodes $1,\dots,\bar{T}$ which satisfies
that for any $(s,a)\in\mathcal{S}\times\mathcal{A}$,
$\upsilon_{\pi^{k_{0}}}(s,a)=0$, which gives a contradiction. ∎

###  F.2 Regret Lower Bound

In the following, we establish a regret lower bound for Worst Path RL and give
its proof.

To exclude trivial instance-specific algorithms and formally state our lower
bound, we first define an $o(K)$-consistent algorithm as an algorithm which
guarantees an $o(K)$ regret on any instance of Worst Path RL.

######  Theorem 6.

There exists an instance of Worst Path RL, for which the regret of any
$o(K)$-consistent algorithm is at least

$\displaystyle\Omega\Bigg{(}\max_{(s,a):\ \exists h,\
a\neq\pi^{*}_{h}(s)}\frac{H}{\min\limits_{\pi:\
\upsilon_{\pi}(s,a)>0}\upsilon_{\pi}(s,a)\cdot\min\limits_{s^{\prime}\in\textup{supp}(p(\cdot|s,a))}p(s^{\prime}|s,a)}\Bigg{)},$

where $\max_{\begin{subarray}{c}(s,a):\exists h,\
a\neq\pi^{*}_{h}(s)\end{subarray}}$ takes the maximum over all $(s,a)$ such
that $a$ is sub-optimal in state $s$ at some step.

The intuition behind this lower bound is as follows. For a critical but hard-
to-reach state $s$, any $o(K)$-consistent algorithm must explore all actions
$a$ in state $s$, in order to detect their induced successor states
$s^{\prime}$ and distinguish the optimal action. This process incurs a regret
dependent on factors $\min_{\pi:\upsilon_{\pi}(s,a)>0}\upsilon_{\pi}(s,a)$ and
$\min_{s^{\prime}\in\textup{supp}(p(\cdot|s,a))}p(s^{\prime}|s,a)$, and hence
the lower bound.

Figure 8: The instance for lower bound under the $\min$ metric (Theorem 6).

###### Proof of Theorem 6.

Consider the instance $\mathcal{I}$ as shown in Figure 8:

The action space contains two actions, i.e., $\mathcal{A}=\\{a_{1},a_{2}\\}$.
The state space is
$\mathcal{S}=\\{s_{1},s_{2},\dots,s_{n},x_{1},x_{2},x_{3}\\}$, where $n=S-3$
and $s_{1}$ is the initial state. Let $H\gg S$ and $0<\alpha<\frac{1}{4}$.

The reward functions are as follows. For any $a\in\mathcal{A}$,
$r(x_{1},a)=1$, $r(x_{2},a)=0.8$ and $r(x_{3},a)=0.2$. For any $i\in[n]$ and
$a\in\mathcal{A}$, $r(s_{i},a)=0$.

The transition distributions are as follows. For any $a\in\mathcal{A}$,
$p(s_{2}|s_{1},a)=\alpha$, $p(x_{1}|s_{1},a)=1-3\alpha$,
$p(x_{2}|s_{1},a)=\alpha$ and $p(x_{3}|s_{1},a)=\alpha$. For any
$i\in\\{2,\dots,n-1\\}$ and $a\in\mathcal{A}$, $p(s_{i+1}|s_{i},a)=\alpha$ and
$p(x_{1}|s_{i},a)=1-\alpha$. $x_{1}$, $x_{2}$ and $x_{3}$ are absorbing
states, i.e., for any $a\in\mathcal{A}$, $p(x_{1}|x_{1},a)=1$,
$p(x_{2}|x_{2},a)=1$ and $p(x_{3}|x_{3},a)=1$. The state $s_{n}$ is a bandit
state, which has an optimal action and a suboptimal action. Let $a_{*}$ denote
the optimal action in state $s_{n}$, which is uniformly drawn from
$\\{a_{1},a_{2}\\}$, and let $a_{sub}$ denote the other sub-optimal action in
state $s_{n}$. For the optimal action $a_{*}$, $p(x_{2}|s_{n},a_{*})=1$. For
the sub-optimal action $a_{sub}$, $p(x_{2}|s_{n},a_{sub})=1-\alpha$ and
$p(x_{3}|s_{n},a_{sub})=\alpha$.

Fix an $o(K)$-consistent algorithm $\mathcal{A}$, which guarantees a sub-
linear regret on any instance of Worst Path RL. We have that $\mathcal{A}$
needs to observe the transition from $(s_{n},a_{sub})$ to $x_{3}$ at least
once. Otherwise, without any observation of the transition from
$(s_{n},a_{sub})$ to $x_{3}$, $\mathcal{A}$ can only trivially choose $a_{1}$
or $a_{2}$ in state $s_{n}$, and no matter $\mathcal{A}$ chooses $a_{1}$ or
$a_{2}$, it will suffer a linear regret in the counter instance where the
unchosen action is optimal.

Thus, any $o(K)$-consistent algorithm must observe the transition from
$(s_{n},a_{sub})$ to $x_{3}$ at least once, and needs at least

$\frac{1}{\upsilon_{\pi_{sub}}(s_{n},a_{sub})\cdot p(x_{3}|s_{n},a_{sub})}$

episodes with sub-optimal policies. Here $\pi_{sub}$ denotes a policy which
chooses $a_{sub}$ in state $s_{n}$, and $\upsilon_{\pi_{sub}}(s_{n},a_{sub})$
denotes the probability that $(s_{n},a_{sub})$ is visited at least once in an
episode under policy $\pi_{sub}$.

Once the agent takes a sub-optimal policy in an episode, she will suffer
regret $0.6(H-n)$ in this episode.

Therefore, $\mathcal{A}$ needs to suffer at least

$\Omega\left(\frac{1}{\upsilon_{\pi_{sub}}(s_{n},a_{sub})\cdot
p(x_{3}|s_{n},a_{sub})}\cdot 0.6(H-n)\right)$

regret in expectation.

Since in the constructed instance (Figure 8)

$\displaystyle\max_{\begin{subarray}{c}(s,a):\ \exists h,\
a\neq\pi^{*}_{h}(s)\end{subarray}}\frac{1}{\min\limits_{\begin{subarray}{c}\pi:\
\upsilon_{\pi}(s,a)>0\end{subarray}}\upsilon_{\pi}(s,a)\cdot\min\limits_{s^{\prime}\in\textup{supp}(p(\cdot|s,a))}p(s^{\prime}|s,a)}=\frac{1}{\upsilon(s_{n},a_{sub})\cdot
p(x_{3}|s_{n},a_{sub})},$

we have that $\mathcal{A}$ needs to suffer at least

$\displaystyle\Omega\left(\max_{\begin{subarray}{c}(s,a):\ \exists h,\
a\neq\pi^{*}_{h}(s)\end{subarray}}\frac{H}{\min\limits_{\begin{subarray}{c}\pi:\
\upsilon_{\pi}(s,a)>0\end{subarray}}\upsilon_{\pi}(s,a)\cdot\min\limits_{s^{\prime}\in\textup{supp}(p(\cdot|s,a))}p(s^{\prime}|s,a)}\right)$

regret. ∎

##  Appendix G Technical Tool

In this section, we present a useful technical tool.

######  Lemma 24 (Lemma 13 in (Ménard et al., 2021)).

Let $A,B,C,D,E$ and $\beta$ be positive scalars such that $1\leq B\leq E$ and
$\beta\geq e$. If $T\geq 0$ satisfies

$\displaystyle T\leq C\sqrt{T\left(A\log\left(\beta
T\right)+B\log^{2}\left(\beta T\right)\right)}+D\left(A\log\left(\beta
T\right)+E\log^{2}\left(\beta T\right)\right),$

then we have

$\displaystyle T\leq
C^{2}\left(A+B\right)C_{1}^{2}+\left(D+2\sqrt{D}C\right)\left(A+E\right)C_{1}^{2}+1,$

where

$\displaystyle
C_{1}=\frac{8}{5}\log\left(11\beta^{2}\left(A+E\right)\left(C+D\right)\right).$