# Provably Efficient Risk-Sensitive Reinforcement Learning: Iterated CVaR and
Worst Path

Yihan Du
Institute for Interdisciplinary Information Sciences
Tsinghua University
Beijing, China
<EMAIL_ADDRESS>
&Siwei Wang
Microsoft Research
Beijing, China
<EMAIL_ADDRESS>
Longbo Huang
Institute for Interdisciplinary Information Sciences
Tsinghua University
Beijing, China
<EMAIL_ADDRESS>Corresponding author.

###### Abstract

In this paper, we study a novel episodic risk-sensitive Reinforcement Learning
(RL) problem, named Iterated CVaR RL, which aims to maximize the tail of the
reward-to-go at each step, and focuses on tightly controlling the risk of
getting into catastrophic situations at each stage. This formulation is
applicable to real-world tasks that demand strong risk avoidance throughout
the decision process, such as autonomous driving, clinical treatment planning
and robotics. We investigate two performance metrics under Iterated CVaR RL,
i.e., Regret Minimization and Best Policy Identification. For both metrics, we
design efficient algorithms $\mathtt{ICVaR\mbox{-}RM}$ and
$\mathtt{ICVaR\mbox{-}BPI}$, respectively, and provide nearly matching upper
and lower bounds with respect to the number of episodes $K$. We also
investigate an interesting limiting case of Iterated CVaR RL, called Worst
Path RL, where the objective becomes to maximize the minimum possible
cumulative reward. For Worst Path RL, we propose an efficient algorithm with
constant upper and lower bounds. Finally, our techniques for bounding the
change of CVaR due to the value function shift and decomposing the regret via
a distorted visitation distribution are novel, and can find applications in
other risk-sensitive RL problems.

##  1 Introduction

Reinforcement Learning (RL) (Kaelbling et al., 1996; Szepesvári, 2010; Sutton
& Barto, 2018) is a classic online decision-making formulation, where an agent
interacts with an unknown environment with the goal of maximizing the obtained
reward. Despite the empirical success and theoretical progress of recent RL
algorithms, e.g., (Szepesvári, 2010; Agrawal & Jia, 2017; Azar et al., 2017;
Zanette & Brunskill, 2019), they focus mainly on the risk-neutral criterion,
i.e., maximizing the expected cumulative reward, and can fail to avoid rare
but disastrous situations. As a result, existing algorithms cannot be applied
to tackle real-world risk-sensitive tasks, such as autonomous driving (Wen et
al., 2020) and clinical treatment planning (Coronato et al., 2020), where
policies that ensure low risk of getting into catastrophic situations at all
decision stages are strongly preferred.

Motivated by the above facts, we investigate Iterated CVaR RL, a novel
episodic RL formulation equipped with an important risk-sensitive criterion,
i.e., Iterated Conditional Value-at-Risk (CVaR) (Hardy & Wirch, 2004). Here,
CVaR (Artzner et al., 1999) is a popular static (single-stage) risk measure
which stands for the expected tail reward. Iterated CVaR is a dynamic (multi-
stage) risk measure defined upon CVaR by backward iteration, and focuses on
the worst portion of the reward-to-go at each stage. In the Iterated CVaR RL
problem, an agent interacts with an _unknown_ episodic Markov Decision Process
(MDP) in order to maximize the worst $\alpha$-portion of the reward-to-go at
each step, where $\alpha\in(0,1]$ is a given risk level. Under this model, we
investigate two important performance metrics, i.e., Regret Minimization (RM),
where the goal is to minimize the cumulative regret over all episodes, and
Best Policy Identification (BPI), where the performance is measured by the
number of episodes required for identifying an optimal policy.

Compared to existing CVaR MDP model, e.g., (Boda & Filar, 2006; Ott, 2010;
Bäuerle & Ott, 2011; Chow et al., 2015), which aims to maximize the CVaR
(i.e., the worst $\alpha$-portion) of the _total_ reward, our Iterated CVaR RL
concerns the worst $\alpha$-portion of the reward-to-go _at each step_ , and
prevents the agent from getting into catastrophic states more carefully.
Intuitively, CVaR MDP takes more cumulative reward into account and prefers
actions which have better performance in general, but can have larger
probabilities of getting into catastrophic states. Thus, CVaR MDP is suitable
for scenarios where bad situations lead to a higher cost instead of fatal
damage, e.g., finance. In contrast, our Iterated CVaR RL prefers actions which
have smaller probabilities of getting into catastrophic states. Hence,
Iterated CVaR RL is suitable for _safety-critical_ applications, where
catastrophic states are unacceptable and need to be carefully avoided, e.g.,
clinical treatment planning (Wang et al., 2019) and unmanned helicopter
control (Johnson & Kannan, 2002). For example, consider the case where we fly
an unmanned helicopter to complete some task. There is a small probability
that, at each time during execution, the helicopter encounters a sensing or
control failure and does not take the scheduled action. To guarantee the
safety of surrounding workers and the helicopter, we need to make sure that
even if the failure occurs, the taken policy ensures that the helicopter does
not crash and cause fatal damage (see Appendix C.2, C.3 for more detailed
comparisons with existing risk-sensitive MDP models).

Iterated CVaR RL faces several unique challenges as follows. (i) The
importance (contribution to regret) of a state in Iterated CVaR RL is not
proportional to its visitation probability. Specifically, there can be states
which are critical (risky) but have a small visitation probability. As a
result, the regret for Iterated CVaR RL cannot be decomposed into the
estimation error at each step with respect to the visitation distribution, as
in standard RL analysis (Jaksch et al., 2010; Azar et al., 2017; Zanette &
Brunskill, 2019). (ii) In Iterated CVaR RL, the calculation of estimation
error involves bounding the change of CVaR when the true value function shifts
to optimistic value function, which is very different from typically bounding
the change of expected rewards as in existing RL analysis (Jaksch et al.,
2010; Azar et al., 2017; Jin et al., 2018). Therefore, Iterated CVaR RL
demands brand-new algorithm design and analytical techniques. To tackle the
above challenges, we design two efficient algorithms
$\mathtt{ICVaR\mbox{-}RM}$ and $\mathtt{ICVaR\mbox{-}BPI}$ for the RM and BPI
metrics, respectively, equipped with delicate CVaR-adapted value iteration and
exploration bonuses to allocate more attention on rare but potentially
dangerous states. We also develop novel analytical techniques, for bounding
the change of CVaR due to the value function shift and decomposing the regret
via a distorted visitation distribution. Lower bounds for both metrics are
established to demonstrate the optimality of our algorithms with respect to
the number of episodes $K$. Moreover, we present experiments to validate our
theoretical results and show the performance superiority of our algorithm (see
Appendix A).

We further study an interesting limiting case of Iterated CVaR RL when
$\alpha$ approaches $0$, called Worst Path RL, where the goal becomes to
maximize the minimum possible cumulative reward (optimize the worst path).
This setting corresponds to the scenario where the decision maker is extremely
risk-adverse and concerns the worst situation (e.g., in clinical treatment
planning (Coronato et al., 2020), the worst case can be disastrous). We
emphasize that Worst Path RL cannot be directly solved by taking $\alpha\to 0$
in Iterated CVaR RL’s results, as the results there have a dependency on
$\frac{1}{\alpha}$ in both upper and lower bounds. To handle this limiting
case, we design a simple yet efficient algorithm $\mathtt{MaxWP}$, and obtain
constant upper and lower regret bounds which are independent of $K$.

The contributions of this paper are summarized as follows.

  * •

We propose a novel Iterated CVaR RL formulation, where an agent interacts with
an unknown environment, with the objective of maximizing the worst
$\alpha$-percent tail of the reward-to-go at each step. This formulation
enables one to tightly control risk throughout the decision process, and is
most suitable for applications where such safety-at-all-time is critical.

  * •

We investigate two important metrics of Iterated CVaR RL, i.e., Regret
Minimization (RM) and Best Policy Identification (BPI), and propose efficient
algorithms $\mathtt{ICVaR\mbox{-}RM}$ and $\mathtt{ICVaR\mbox{-}BPI}$. We
establish nearly matching regret/sample complexity upper and lower bounds with
respect to $K$. Moreover, we develop novel techniques to bound the change of
CVaR due to the value function shift and decompose the regret via a distorted
visitation distribution, which can be applied to other risk-sensitive decision
making problems.

  * •

We further investigate a limiting case of Iterated CVaR RL when $\alpha$
approaches $0$, called Worst Path RL, where the objective is to maximize the
minimum possible cumulative reward. We develop a simple and efficient
algorithm $\mathtt{MaxWP}$, and provide constant regret upper and lower bounds
(independent of $K$).

Due to space limit, we defer all proofs and experiments to Appendix.

##  2 Related Work

Below we review the most related works, and defer a full literature review to
Appendix B.

CVaR-based MDPs (Known Transition). Boda & Filar (2006); Ott (2010); Bäuerle &
Ott (2011); Chow et al. (2015) study the CVaR MDP where the objective is to
minimize the CVaR of the total cost, and show that the optimal policy for CVaR
MDP is history-dependent (see Appendix C.2 for a detailed comparison with CVaR
MDP). Hardy & Wirch (2004) firstly define the Iterated CVaR measure, and
Osogami (2012); Chu & Zhang (2014); Bäuerle & Glauner (2022) consider iterated
coherent risk measures (including Iterated CVaR) in MDPs, and demonstrate the
existence of Markovian optimal policies. The above works focus mainly on the
planning side, i.e., proposing algorithms and error guarantees for MDPs with
_known_ transition, while our work develops RL algorithms (interacting with
the environment) and regret/sample complexity results for _unknown_
transition.

Risk-sensitive Reinforcement Learning (Unknown Transition). Tamar et al.
(2015); Keramati et al. (2020) study CVaR MDP with unknown transition and
provide convergence analysis. Borkar & Jain (2014); Chow & Ghavamzadeh (2014);
Chow et al. (2017) investigate RL with CVaR-based constraints. Heger (1994);
Coraluppi & Marcus (1997; 1999) consider minimizing the worst-case cost in RL
and design heuristic algorithms.  Fei et al. (2020; 2021a; 2021b) study risk-
sensitive RL with the exponential utility criterion, which takes all successor
states into account with an exponential reweighting scheme. In contrast, our
Iterated CVaR RL primarily concerns the worst $\alpha$-portion successor
states, and focuses on optimizing the performance under bad situations (see
Appendix C.3 for a detailed comparison).

##  3 Problem Formulation

In this section, we present the problem formulations of Iterated CVaR RL and
Worst Path RL.

Conditional Value-at-Risk (CVaR). We first introduce two risk measures, i.e.,
Value-at-Risk (VaR) and Conditional Value-at-Risk (CVaR). Let $X$ be a random
variable with cumulative distribution function $F(x)=\Pr[X\leq x]$. Given a
risk level $\alpha\in(0,1]$, the VaR at risk level $\alpha$ is the
$\alpha$-quantile of $X$, i.e.,
$\textup{VaR}^{\alpha}(X)=\min\\{x|F(x)\geq\alpha\\}$, and the CVaR at risk
level $\alpha$ is defined as (Rockafellar et al., 2000):

$\displaystyle\textup{CVaR}^{\alpha}(X)=\sup_{x\in\mathbb{R}}\Big{\\{}x-\frac{1}{\alpha}\mathbb{E}\left[(x-X)^{+}\right]\Big{\\}},$

where $(x)^{+}:=\max\\{x,0\\}$. If there is no probability atom at
$\textup{VaR}^{\alpha}(X)$, CVaR can also be written as
$\textup{CVaR}^{\alpha}(X)=\mathbb{E}[X|X\leq\textup{VaR}^{\alpha}(X)]$
(Shapiro et al., 2021). Intuitively, $\textup{CVaR}^{\alpha}(X)$ is a
distorted expectation of $X$ conditioning on its $\alpha$-portion tail, which
depicts the average value when bad situations happen. When $\alpha=1$,
$\textup{CVaR}^{\alpha}(X)=\mathbb{E}[X]$, and when $\alpha\to 0$,
$\textup{CVaR}^{\alpha}(X)$ tends to $\min(X)$ (Chow et al., 2015).

Iterated CVaR RL. We consider an episodic Markov Decision Process (MDP)
$\mathcal{M}(\mathcal{S},\mathcal{A},H,p,r)$. Here $\mathcal{S}$ is the state
space, $\mathcal{A}$ is the action space, and $H$ is the length of horizon in
each episode. $p$ is the transition distribution, i.e., $p(s^{\prime}|s,a)$
gives the probability of transitioning to $s^{\prime}$ when starting from
state $s$ and taking action $a$. $r:\mathcal{S}\times\mathcal{A}\mapsto[0,1]$
is a reward function, and $r(s,a)$ gives a deterministic reward for taking
action $a$ in state $s$. A policy $\pi$ is defined as a collection of $H$
functions, i.e., $\pi=\\{\pi_{h}:\mathcal{S}\mapsto\mathcal{A}\\}_{h\in[H]}$,
where $[H]:=\\{1,2,...,H\\}$.

The _episodic_ RL game is as follows. In each episode $k$, an agent chooses a
policy $\pi^{k}$, and starts from a fixed initial state $s_{1}$, i.e.,
$s^{k}_{1}:=s_{1}$, as assumed in many prior RL works (Fiechter, 1994;
Kaufmann et al., 2021; Ménard et al., 2021). At each step $h\in[H]$, the agent
observes the state $s^{k}_{h}$ and takes an action
$a^{k}_{h}=\pi^{k}_{h}(s^{k}_{h})$. After that, it receives a reward
$r(s^{k}_{h},a^{k}_{h})$ and transitions to a next state $s^{k}_{h+1}$
according to the transition distribution $p(\cdot|s^{k}_{h},a^{k}_{h})$. The
episode ends after $H$ steps and the agent enters the next episode.

In Iterated CVaR RL, for any risk level $\alpha\in(0,1]$ and a policy $\pi$,
we use value function $V^{\alpha,\pi}_{h}:\mathcal{S}\mapsto\mathbb{R}$ and
Q-value function
$Q^{\alpha,\pi}_{h}:\mathcal{S}\times\mathcal{A}\mapsto\mathbb{R}$ to denote
the cumulative reward that can be obtained when the agent transitions to the
worst $\alpha$-portion states at each step, starting from $s$ and $(s,a)$ at
step $h$, respectively. For simplicity of notation, when the value of $\alpha$
is clear, we omit the superscript $\alpha$ and use the notations $V^{\pi}_{h}$
and $Q^{\pi}_{h}$. Formally, $Q^{\pi}_{h}$ and $V^{\pi}_{h}$ are recurrently
defined in Eq. (i) below. Since $\mathcal{S}$, $\mathcal{A}$ and $H$ are
finite and the maximization of $V^{\pi}_{h}(s)$ in Iterated CVaR RL satisfies
the optimal substructure property, there exists an optimal policy $\pi^{*}$
which gives the optimal value $V^{*}_{h}(s)=\max_{\pi}V^{\pi}_{h}(s)$ for all
$s\in\mathcal{S}$ and $h\in[H]$ (Chu & Zhang, 2014). Therefore, the Bellman
equation and the Bellman optimality equation are given in Eqs. (i),(ii) below,
respectively (Chu & Zhang, 2014).

$\left\\{\begin{aligned}
\\!Q^{\pi}_{h}(s,a)&=\\!r(s,a)\\!+\\!\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}\\!(V^{\pi}_{h+1}(s^{\prime}))\\\
\\!V^{\pi}_{h}(s)&=Q^{\pi}_{h}(s,\pi_{h}(s))\\\ \\!V^{\pi}_{H+1}(s)&=0,\
\forall s\in\mathcal{S},\hskip
70.0001pt\textup{(i)}\end{aligned}\right.\left\\{\begin{aligned}
\\!Q^{*}_{h}(s,a)&=\\!r(s,a)\\!+\\!\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}\\!(V^{*}_{h+1}(s^{\prime}))\\\
\\!V^{*}_{h}(s)&=\max_{a\in\mathcal{A}}Q^{*}_{h}(s,a)\\\
\\!V^{*}_{H+1}(s)&=0,\ \forall s\in\mathcal{S},\hskip
70.0001pt\textup{(ii)}\end{aligned}\right.$

where $\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V^{\pi}_{h+1}(s^{\prime}))$ denotes the CVaR value of random
variable $V^{\pi}_{h+1}(s^{\prime})$ with $s^{\prime}\sim p(\cdot|s,a)$ at
risk level $\alpha$.  We also provide the expanded version of value function
definitions for Iterated CVaR RL (Eqs. (i), (ii)) in Appendix C.1.

We consider two performance metrics for Iterated CVaR RL, i.e., Regret
Minimization (RM) and Best Policy Identification (BPI). In Iterated CVaR RL-
RM, the agent aims to minimize the cumulative regret in $K$ episodes, defined
as

$\displaystyle\mathcal{R}(K)=\sum_{k=1}^{K}\left(V^{*}_{1}(s_{1})-V^{\pi_{k}}_{1}(s_{1})\right).$
(1)

In Iterated CVaR RL-BPI, given a confidence parameter $\delta\in(0,1]$ and an
accuracy parameter $\varepsilon>0$, the agent needs to use as few trajectories
(episodes) as possible to identify an $\varepsilon$-optimal policy
$\hat{\pi}$, which satisfies $V^{\hat{\pi}}_{1}(s_{1})\geq
V^{*}_{1}(s_{1})-\varepsilon$, with probability as least $1-\delta$. That is,
the performance of BPI is measured by the number of trajectories used, i.e.,
sample complexity.

Worst Path RL. Furthermore, we investigate an interesting limiting case of
Iterated CVaR RL when $\alpha$ approaches $0$, called Worst Path RL. In this
case, the objective becomes maximizing the minimum possible reward (Heger,
1994). The Bellman (optimality) equations become

$\left\\{\begin{aligned} Q^{\pi}_{h}(s,a)&=r(s,a)+\min_{s^{\prime}\sim
p(\cdot|s,a)}(V^{\pi}_{h+1}(s^{\prime}))\\\
V^{\pi}_{h}(s)&=Q^{\pi}_{h}(s,\pi_{h}(s))\\\ V^{\pi}_{H+1}(s)&=0,\ \forall
s\in\mathcal{S},\end{aligned}\right.\ \left\\{\begin{aligned}
Q^{*}_{h}(s,a)&=r(s,a)+\min_{s^{\prime}\sim
p(\cdot|s,a)}(V^{*}_{h+1}(s^{\prime}))\\\
V^{*}_{h}(s)&=\max_{a\in\mathcal{A}}Q^{*}_{h}(s,a)\\\ V^{*}_{H+1}(s)&=0,\
\forall s\in\mathcal{S},\end{aligned}\right.$ (2)

where $\min_{s^{\prime}\sim p(\cdot|s,a)}(V^{\pi}_{h+1}(s^{\prime}))$ denotes
the minimum value of random variable $V^{\pi}_{h+1}(s^{\prime})$ with
$s^{\prime}\sim p(\cdot|s,a)$. From Eq. (2), one sees that

$\displaystyle
Q^{\pi}_{h}(s,a)=\\!\\!\\!\min_{(s_{t},a_{t})\sim\pi}\\!\\!\left[\sum_{t=h}^{H}r(s_{t},a_{t})\Big{|}s_{h}=s,a_{h}=a,\pi\right]\\!,\
V^{\pi}_{h}(s)=\\!\\!\\!\min_{(s_{t},a_{t})\sim\pi}\\!\\!\left[\sum_{t=h}^{H}r(s_{t},a_{t})\Big{|}s_{h}=s,\pi\right]\\!.$

Thus, $Q^{\pi}_{h}(s,a)$ and $V^{\pi}_{h}(s)$ denote the minimum possible
cumulative reward under policy $\pi$, starting from $(s,a)$ and $s$ at step
$h$, respectively. The optimal policy $\pi^{*}$ maximizes the minimum possible
cumulative reward (i.e., optimizes the worst path) for all starting states and
steps. Formally, $\pi^{*}$ gives the optimal value
$V^{*}_{h}(s)=\max_{\pi}V^{\pi}_{h}(s)$ for all $s\in\mathcal{S}$ and
$h\in[H]$.

For Worst Path RL, in this paper we mainly consider the regret minimization
setting, where the regret is defined the same as Eq. (1). Note that this case
cannot be directly solved by taking $\alpha\to 0$ in Iterated CVaR RL, as the
results there have a dependency on $\frac{1}{\alpha}$. Thus, changing from
$\textup{CVaR}(\cdot)$ to $\min(\cdot)$ in Worst Path RL requires a different
algorithm design and analysis.

The best policy identification setting of Worst Path RL, on the other hand, is
very challenging. This is because we cannot establish confidence intervals
under the $\min(\cdot)$ operation, and it is difficult to determine when the
estimated optimal policy is accurate enough and when the algorithm should
stop. We will further investigate this setting in future work.

##  4 Iterated CVaR RL with Regret Minimization

In this section, we consider regret minimization (Iterated CVaR RL-RM). We
propose an algorithm $\mathtt{ICVaR\mbox{-}RM}$ with CVaR-adapted exploration
bonuses, and demonstrate its sample efficiency.

###  4.1 Algorithm $\mathtt{ICVaR\mbox{-}RM}$ and Regret Upper Bound

We propose a value iteration-based algorithm $\mathtt{ICVaR\mbox{-}RM}$
(Algorithm 1), which adopts Brown-type (Brown, 2007) (CVaR-adapted)
exploration bonuses and delicately pays more attention to rare but risky
states. Specifically, in each episode $k$, $\mathtt{ICVaR\mbox{-}RM}$ computes
the empirical CVaR for the values of next states
$\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\bar{V}^{k}_{h+1}(s^{\prime}))$
and Brown-type exploration bonuses
$\frac{H}{\alpha}\sqrt{\frac{L}{n_{k}(s,a)}}$. Here $n^{k}(s,a)$ is the number
of times $(s,a)$ was visited up to episode $k$, and
$\hat{p}^{k}(s^{\prime}|s,a)$ is the empirical estimate of transition
probability $p(s^{\prime}|s,a)$. Then, $\mathtt{ICVaR\mbox{-}RM}$ constructs
optimistic Q-value function $\bar{Q}^{k}_{h}(s,a)$, optimistic value function
$\bar{V}^{k}_{h}(s)$, and a greedy policy $\pi^{k}$ with respect to
$\bar{Q}^{k}_{h}(s,a)$. After calculating the value functions and policy,
$\mathtt{ICVaR\mbox{-}RM}$ plays episode $k$ with policy $\pi^{k}$, observes a
trajectory, and updates $n_{k}(s,a)$ and $\hat{p}^{k+1}(s^{\prime}|s,a)$. The
calculation of CVaR (Line 1) can be implemented efficiently, and costs
$O(S\log S)$ computation complexity (Shapiro et al., 2021).

We summarize the regret performance of $\mathtt{ICVaR\mbox{-}RM}$ as follows.

Input: $\delta$, $\alpha$, $\delta^{\prime}:=\frac{\delta}{5}$,
$L:=\log(\frac{KHSA}{\delta^{\prime}})$, $\bar{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
$\bar{Q}^{k}_{h}(s,a)\\!\leftarrow\\!\min\\{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{L}{n_{k}(s,a)}},H\\}$,
$\forall(s,a)\\!\in\\!\mathcal{S}\\!\times\\!\mathcal{A}$;

4 $\bar{V}^{k}_{h}(s)\leftarrow\max_{a\in\mathcal{A}}\bar{Q}^{k}_{h}(s,a)$,
$\pi^{k}_{h}(s)\leftarrow\operatornamewithlimits{argmax}_{a\in\mathcal{A}}\bar{Q}^{k}_{h}(s,a)$,
$\forall s\in\mathcal{S}$;

5

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

7

Algorithm 1 $\mathtt{ICVaR\mbox{-}RM}$

######  Theorem 1 (Regret Upper Bound).

With probability at least $1-\delta$, the regret of algorithm
$\mathtt{ICVaR\mbox{-}RM}$ is bounded by

$\displaystyle
O\Bigg{(}\bm{\min}\Bigg{\\{}\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}}}\Bigg{\\}}\cdot\frac{HS\sqrt{KHA}}{\alpha}\log\left(\frac{KHSA}{\delta}\right)\Bigg{)},$

where $w_{\pi,h}(s)$ denotes the probability of visiting state $s$ at step $h$
under policy $\pi$.

Remark 1. The regret depends on the _minimum_ between an MDP-intrinsic
visitation factor $(\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s))^{-\frac{1}{2}}$ and
$\frac{1}{\sqrt{\alpha^{H-1}}}$. When $\alpha$ is small, the first term
dominates the bound, which stands for the minimum probability of visiting an
available state under any feasible policy. Note that $\min_{\pi,h,s:\
w_{\pi,h}(s)>0}w_{\pi,h}(s)$ takes the minimum over only the policies under
which $s$ is reachable, and thus, this factor will never be zero. Indeed, this
factor also exists in the lower bound (see Section 4.2). Thus, it
characterizes the essential problem hardness, i.e., when the agent is highly
risk-adverse, her regret will be heavily influenced by exploring critical but
hard-to-reach states.

When $\alpha$ is large, $\frac{1}{\sqrt{\alpha^{H-1}}}$ instead dominates the
bound. The intuition behind the factor $\frac{1}{\sqrt{\alpha^{H-1}}}$ is that
for any state-action pair, the ratio of the visitation probability
conditioning on transitioning to bad successor states over the original
visitation probability can be upper bounded by $\frac{1}{\alpha^{H-1}}$. This
ratio is critical and will appear in the regret bound (see Lemma 9 for a
formal statement).

In the special case when $\alpha=1$, our Iterated CVaR RL problem reduces to
the classic RL formulation, and our regret bound becomes
$\tilde{O}(HS\sqrt{KHA})$, which matches the result in existing classic RL
work (Jaksch et al., 2010). This bound has a gap of $\sqrt{HS}$ to the state-
of-the-art regret bound for classic RL (Azar et al., 2017; Zanette &
Brunskill, 2019). This is because our algorithm is mainly designed for general
risk-sensitive cases (which require CVaR-adapted exploration bonuses), and
does not use the Bernstein-type exploration bonuses (which only work for
classic expectation maximization criterion). Such phenomenon also appears in
existing risk-sensitive RL works (Fei et al., 2020; 2021a). Designing an
algorithm which achieves an optimal regret simultaneously for both risk-
sensitive cases and classic expectation maximization case is still an open
problem, which we leave for future work. To validate our theoretical analysis,
we also conduct experiments to exhibit the influences of parameters $\alpha$,
$\delta$, $H$, $S$, $A$ and $K$ on the regret of $\mathtt{ICVaR\mbox{-}RM}$ in
practice, and the empirical results well match our theoretical bound (see
Appendix A).

_Challenges and Novelty in Regret Analysis._ The analysis of Iterated CVaR RL
faces several challenges. (i) First of all, in Iterated CVaR RL, the
contribution of a state to the regret is not proportional to its visitation
probability as in standard RL analysis (Jaksch et al., 2010; Azar et al.,
2017; Zanette & Brunskill, 2019). Instead, the regret is influenced more by
risky but hard-to-reach states. Thus, the regret cannot be decomposed into
estimation error with respect to visitation distribution. (ii) Second, unlike
existing RL analysis (Jaksch et al., 2010; Azar et al., 2017; Jin et al.,
2018) which typically calculates the change of expected rewards between
optimistic and true value functions, in Iterated CVaR RL, we need to instead
analyze the change of CVaR when the true value function shifts to an
optimistic value function. To tackle these challenges, we develop a new
analytical technique to bound the change of CVaR due to the value function
shift via conditional transition probabilities, which can be applied to other
CVaR-based RL problems. Furthermore, we establish a novel regret decomposition
for Iterated CVaR RL via a distorted (conditional) visitation distribution,
and quantify the deviation between this distorted visitation distribution and
the original visitation distribution.

Below we present a proof sketch for Theorem 1 (see Appendix D.1 for a complete
proof).

_Proof sketch of Theorem 1._ First, we introduce a key inequality (Eq. (3)) to
bound the change of CVaR when the true value function shifts to an optimistic
one. To this end, let $\beta^{\alpha,V}(\cdot|s,a)\in\mathbb{R}^{S}$ denote
the conditional transition probability conditioning on transitioning to the
worst $\alpha$-portion successor states $s^{\prime}$, i.e., with the lowest
values $V(s^{\prime})$. It satisfies that
$\sum_{s^{\prime}\in\mathcal{S}}\beta^{\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime})=\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V(s^{\prime})).$ Then, for any $(s,a)$ and value functions
$\bar{V},V$ such that $\bar{V}(s^{\prime})\geq V(s^{\prime})$ for any
$s^{\prime}\in\mathcal{S}$, we have

$\displaystyle\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(\bar{V}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V(s^{\prime}))\leq\beta^{\alpha,V}(\cdot|s,a)^{\top}\left(\bar{V}-V\right).$
(3)

Eq. (3) implies that the deviation of CVaR between optimistic and true value
functions can be bounded by their value deviation under the conditional
transition probability, which resolves the aforementioned challenge (ii), and
serves as the basis of our recurrent regret decomposition.

Now, since $\bar{V}^{k}_{h}$ is an optimistic estimate of $V^{*}_{h}$, we
decompose the regret in episode $k$ as

$\displaystyle\\!\bar{V}^{k}_{1}(s^{k}_{1})\\!-\\!V^{\pi^{k}}_{1}(s^{k}_{1})\\!\overset{\textup{(a)}}{\leq}$
$\displaystyle\frac{H}{\alpha}\sqrt{\frac{L}{n_{k}(s^{k}_{1},a^{k}_{1})}}+\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s^{k}_{1},a^{k}_{1})}(\bar{V}^{k}_{2}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s^{k}_{1},a^{k}_{1})}(\bar{V}^{k}_{2}(s^{\prime}))$
$\displaystyle+\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s^{k}_{1},a^{k}_{1})}(\bar{V}^{k}_{2}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s^{k}_{1},a^{k}_{1})}(V^{\pi^{k}}_{2}(s^{\prime}))$
$\displaystyle\overset{\textup{(b)}}{\leq}$
$\displaystyle\frac{H}{\alpha}\sqrt{\frac{L}{n_{k}(s^{k}_{1},a^{k}_{1})}}+\frac{4H}{\alpha}\sqrt{\frac{SL}{n_{k}(s^{k}_{1},a^{k}_{1})}}+\beta^{\alpha,V^{\pi^{k}}_{2}}(\cdot|s^{k}_{1},a^{k}_{1})^{\top}(\bar{V}^{k}_{2}-V^{\pi^{k}}_{2})$
$\displaystyle\overset{\textup{(c)}}{\leq}$
$\displaystyle\sum_{h=1}^{H}\sum_{(s,a)}w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}\\!\\!(s,a)\cdot\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha\sqrt{n_{k}(s,a)}}$
(4)

Here $w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}\\!\\!(s,a)$ denotes the
conditional probability of visiting $(s,a)$ at step $h$ of episode $k$,
conditioning on transitioning to the worst $\alpha$-portion successor states
$s^{\prime}$ (i.e., with the lowest $\alpha$-portion values
$V^{\pi^{k}}_{h^{\prime}+1}(s^{\prime})$) at each step
$h^{\prime}=1,\dots,h-1$. Intuitively,
$w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}\\!\\!(s,a)$ is a distorted
visitation probability under the conditional transition probability
$\beta^{\alpha,V^{\pi^{k}}}(\cdot|\cdot,\cdot)$. Inequality (b) uses the
concentration of CVaR and Eq. (3). Inequality (c) follows from recurrently
applying steps (a)-(b) to unfold
$\bar{V}^{k}_{h}(\cdot)-V^{\pi^{k}}_{h}(\cdot)$ for $h=2,\dots,H$, and the
fact that $w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}\\!\\!(s,a)$ is the
visitation probability under conditional transition probability
$\beta^{\alpha,V^{\pi^{k}}}(\cdot|\cdot,\cdot)$. Eq. (4) decomposes the regret
into estimation error at all state-action pairs via the distorted
(conditional) visitation distribution
$w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}\\!\\!(s,a)$, which overcomes the
aforementioned challenge (i).

Summing Eq. (4) over all episodes $k\in[K]$ and using the Cauchy–Schwarz
inequality, we have

$\displaystyle\mathbb{E}[\mathcal{R}(K)]\leq$
$\displaystyle\frac{5H\sqrt{SL}}{\alpha}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)}\frac{w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)}{n_{k}(s,a)}}\cdot\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)}w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)}$
$\displaystyle\overset{\textup{(d)}}{=}$
$\displaystyle\frac{5H\sqrt{SL}\cdot\sqrt{KH}}{\alpha}\\!\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)}\frac{w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)}{w_{kh}(s,a)}\cdot\frac{w_{kh}(s,a)}{n_{k}(s,a)}\cdot\mathbbm{1}\left\\{w_{kh}(s,a)\neq
0\right\\}}$ $\displaystyle\overset{\textup{(e)}}{\leq}$
$\displaystyle\frac{5H\sqrt{KHSL}}{\alpha}\\!\\!\sqrt{\min\\!\bigg{\\{}\\!\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a)},\frac{1}{\alpha^{H-1}}\\!\bigg{\\}}\sum_{k=1}^{K}\\!\sum_{h=1}^{H}\\!\sum_{(s,a)}\\!\frac{w_{kh}(s,a)}{n_{k}(s,a)}},$

Here $w_{kh}(s,a)$ denotes the probability of visiting $(s,a)$ at step $h$ of
episode $k$, and  $w_{\pi,h}(s,a)$ denotes the probability of visiting $(s,a)$
at step $h$ under policy $\pi$. Equality (d) uses the facts that
$\sum_{(s,a)}w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)=1$, and if the
visitation probability $w_{kh}(s,a)=0$, the conditional visitation probability
$w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)$ must be 0 as well. Inequality
(e) is due to that
$w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)/w_{kh}(s,a)$ can be bounded by
both $1/\min_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a)$ and $1/\alpha^{H-1}$.
Specifically, the bound $1/\min_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a)$ follows from
$\min_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a)\leq w_{kh}(s,a)$, and the bound
$1/\alpha^{H-1}$ comes from the fact that the conditional visitation
probability $w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)$ is at most
$1/\alpha^{H-1}$ times the visitation probability $w_{kh}(s,a)$. Having
established the above, we can use a similar analysis as that in classic RL
(Azar et al., 2017; Zanette & Brunskill, 2019) to bound
$\sum_{k=1}^{K}\\!\sum_{h=1}^{H}\\!\sum_{(s,a)}\\!\frac{w_{kh}(s,a)}{n_{k}(s,a)}$,
and then, we can obtain Theorem 1. $\hfill\square$

###  4.2 Regret Lower Bound

We now present a regret lower bound to demonstrate the optimality of algorithm
$\mathtt{ICVaR\mbox{-}RM}$.

######  Theorem 2 (Regret Lower Bound).

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

$\displaystyle\Omega\Bigg{(}H\sqrt{\frac{AK}{\alpha\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}}\Bigg{)}.$ (5)

In addition, there exists an instance of Iterated CVaR RL-RM, where
$\alpha^{H-1}>\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)$ and the regret of any algorithm is
at least $\Omega(\sqrt{\frac{AK}{{\alpha}^{H-1}}})$.

Remark 2. Theorem 2 demonstrates that when $\alpha$ is small, the factor
$\min_{\pi,h,s:\ w_{\pi,h}(s)>0}w_{\pi,h}(s)$ is inevitable in general. This
reveals the intrinsic hardness of Iterated CVaR RL, i.e., when the agent is
highly sensitive to bad situations, she must suffer a regret due to exploring
risky but hard-to-reach states. This lower bound also validates that
$\mathtt{ICVaR\mbox{-}RM}$ is near-optimal with respect to $K$.

Figure 1: Instance for the lower bound.

_Lower Bound Analysis._ Here we provide the proof idea of the first lower
bound (Eq. (5)) in Theorem 2, and defer the full proof to Appendix D.2. We
construct an instance with a hard-to-reach bandit state (which has an optimal
action and multiple sub-optimal actions), and show that this state is critical
for minimizing the regret, but difficult for any algorithm to learn. As shown
in Figure 1, we consider an MDP with $A$ actions, $n$ regular states
$s_{1},\dots,s_{n}$ and three absorbing states $x_{1},x_{2},x_{3}$, where
$n<\frac{1}{2}H$. The reward function $r(s,a)$ depends only on the states,
i.e., $s_{1},\dots,s_{n}$ generate zero reward, and $x_{1},x_{2},x_{3}$
generate rewards $1$, $0.8$ and $0.2$, respectively. Let $\mu$ be a parameter
such that $0<\alpha<\mu<\frac{1}{3}$. Under all actions, state $s_{1}$
transitions to $s_{2},x_{1},x_{2},x_{3}$ with probabilities $\mu$, $1-3\mu$,
$\mu$ and $\mu$, respectively, and state $s_{i}$ ($2\leq i\leq n-1$)
transitions to $s_{i+1},x_{1}$ with probabilities $\mu$ and $1-\mu$,
respectively. For the bandit state $s_{n}$, under the optimal action, $s_{n}$
transitions to $x_{2},x_{3}$ with probabilities $1-\alpha+\eta$ and
$\alpha-\eta$, respectively. Under sub-optimal actions, $s_{n}$ transitions to
$x_{2},x_{3}$ with probabilities $1-\alpha$ and $\alpha$, respectively.

In this MDP, under the Iterated CVaR criterion, the value function mainly
depends on the path $s_{1}\rightarrow s_{2}\rightarrow\dots\rightarrow
s_{n}\rightarrow x_{2}/x_{3}$, and especially on the action choice in the
bandit state $s_{n}$. Thus, to distinguish the optimal action in $s_{n}$, any
algorithm must suffer a regret dependent on the probability of visiting
$s_{n}$, which is exactly the minimum visitation probability over all
reachable states $\min_{\pi,h,s:\ w_{\pi,h}(s)>0}w_{\pi,h}(s)$. Note that in
this instance, $\min_{\pi,h,s:\ w_{\pi,h}(s)>0}w_{\pi,h}(s)=\mu^{n-1}$, which
does not depend on $\alpha$ and $H$. This demonstrates that there is an
essential dependency on $\min_{\pi,h,s:\ w_{\pi,h}(s)>0}w_{\pi,h}(s)$ in the
lower bound.

##  5 Iterated CVaR RL with Best Policy Identification

In this section, we design an efficient algorithm $\mathtt{ICVaR\mbox{-}BPI}$,
and establish sample complexity upper and lower bounds for Iterated CVaR RL
with best policy identification (BPI).

###  5.1 Algorithm $\mathtt{ICVaR\mbox{-}BPI}$ and Sample Complexity Upper
Bound

Algorithm $\mathtt{ICVaR\mbox{-}BPI}$ introduces a novel distorted
(conditional) empirical transition probability to construct estimation error,
which effectively assigns more attention to bad situations and fits the main
focus of the Iterated CVaR criterion. Due to space limit, we defer the pseudo-
code and detailed description of $\mathtt{ICVaR\mbox{-}BPI}$ to Appendix E.1.
Below we present the sample complexity of $\mathtt{ICVaR\mbox{-}BPI}$.

######  Theorem 3 (Sample Complexity Upper Bound).

The number of trajectories used by algorithm $\mathtt{ICVaR\mbox{-}BPI}$ to
return an $\varepsilon$-optimal policy with probability at least $1-\delta$ is
bounded by

$\displaystyle O\bigg{(}$
$\displaystyle\bm{\min}\Big{\\{}\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}}\Big{\\}}\frac{H^{3}S^{2}A}{\varepsilon^{2}\alpha^{2}}\cdot
C\bigg{)},$

where $C:=\log^{2}(\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{HSA}{\varepsilon\alpha\delta})$.

Similar to Theorem 1, $\min_{\pi,h,s:\ w_{\pi,h}(s)>0}w_{\pi,h}(s)$ and
$\alpha^{H-1}$ dominate the bound for a large $\alpha$ and a small $\alpha$,
respectively. When $\alpha=1$, the problem reduces to the classic RL
formulation with best policy identification, and our sample complexity becomes
$\tilde{O}(\frac{H^{3}S^{2}A}{\varepsilon^{2}})$, which recovers the result in
prior classic RL work (Dann et al., 2017). Similar to Theorem 1, this bound
has a gap of $HS$ to the state-of-the-art sample complexity for classic RL
(Ménard et al., 2021). This gap is due to the fact that the result in (Ménard
et al., 2021) is obtained using the Bernstein-type exploration bonuses, which
are more fine-grained for the classic RL problem but do not work for general
risk-sensitive cases, because it cannot be used to quantify the estimation
error of CVaR.

To validate the tightness of Theorem 3, we further provide sample complexity
lower bounds
$\Omega(\frac{H^{2}A}{\varepsilon^{2}\alpha\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)}\log\left(\frac{1}{\delta}\right))$
and
$\Omega(\frac{A}{\alpha^{H-1}\varepsilon^{2}}\log\left(\frac{1}{\delta}\right))$
for different instances, which demonstrate that the factor
$\min\\{1/\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s),\ 1/\alpha^{H-1}\\}$ is
indispensable in general (see Appendix E.3 for a formal statement of lower
bound).

Input: $\delta$, $\delta^{\prime}:=\frac{\delta}{2}$,
$L:=\log(\frac{SA}{\delta^{\prime}})$, $\hat{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 $\hat{Q}^{k}_{h}(s,a)\leftarrow
r(s,a)+\min_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(\hat{V}^{k}_{h+1}(s^{\prime}))$,
$\forall(s,a)\in\mathcal{S}\times\mathcal{A}$;

4 $\hat{V}^{k}_{h}(s)\leftarrow\max_{a\in\mathcal{A}}\hat{Q}^{k}_{h}(s,a)$,
$\pi^{k}_{h}(s)\leftarrow\operatornamewithlimits{argmax}_{a\in\mathcal{A}}\hat{Q}^{k}_{h}(s,a)$,
$\forall s\in\mathcal{S}$;

5

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

7

Algorithm 2 $\mathtt{MaxWP}$

##  6 Worst Path RL

In this section, we investigate an interesting limiting case of Iterated CVaR
RL when $\alpha\to 0$, called Worst Path RL, in which case the agent aims to
maximize the minimum possible cumulative reward.

Worst Path RL has a _unique feature_ that, the value function (Eq. (2))
concerns only the minimum value of successor states, which are independent of
specific transition probabilities. Therefore, once we learn the connectivity
among states, we can perform a planning to compute the optimal policy. Yet,
this feature does not make the Worst Path RL problem trivial, because it is
still challenging to distinguish whether a successor state is hard to reach or
does not exist. As a result, a careful scheme is needed to both explore
undetected successor states and exploit observations to minimize regret.

###  6.1 Algorithm $\mathtt{MaxWP}$ and Regret Upper Bound

We design an algorithm $\mathtt{MaxWP}$ (Algorithm 2) based on a simple and
efficient empirical Q-value function, which makes full use of the unique
feature of Worst Path RL, and simultaneously explores undetected successor
states and exploits the current best action. Specifically, in episode $k$,
$\mathtt{MaxWP}$ constructs empirical Q-value/value functions
$\hat{Q}^{k}_{h}(s,a),\hat{V}^{k}_{h}(s)$ using the estimated lowest value of
next states, and then, takes a greedy policy $\pi^{k}_{h}(s)$ with respect to
$\hat{Q}^{k}_{h}(s,a)$ in this episode.

The intuition behind $\mathtt{MaxWP}$ is as follows. Since the Q-value
function for Worst Path RL uses the $\min$ operator, if the Q-value function
is not accurately estimated, it can only be over-estimated (not under-
estimated). If over-estimation happens, $\mathtt{MaxWP}$ will be exploring an
over-estimated action and urging its empirical Q-value to get back to its true
Q-value. Otherwise, if the Q-value function is already accurate,
$\mathtt{MaxWP}$ just selects the optimal action. In other words,
$\mathtt{MaxWP}$ combines the exploration of over-estimated actions (which
lead to undetected successor states) and exploitation of current best actions.
Below we provide the regret guarantee for algorithm $\mathtt{MaxWP}$.

######  Theorem 4.

With probability at least $1-\delta$, the regret of algorithm $\mathtt{MaxWP}$
is bounded by

$\displaystyle
O\bigg{(}\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\frac{H}{\min_{\begin{subarray}{c}\pi:\
\upsilon_{\pi}(s,a)>0\end{subarray}}\upsilon_{\pi}(s,a)\cdot\min_{s^{\prime}\in\textup{supp}(p(\cdot|s,a))}p(s^{\prime}|s,a)}\log\Big{(}\frac{SA}{\delta}\Big{)}\bigg{)},$

where $\upsilon_{\pi}(s,a)$ denotes the probability $(s,a)$ is visited at
least once in an episode under policy $\pi$.

Remark 3. The factor $\min_{\pi:\ \upsilon_{\pi}(s,a)>0}\upsilon_{\pi}(s,a)$
stands for the minimum probability of visiting $(s,a)$ at least once in an
episode over all feasible policies, and
$\min_{s^{\prime}\in\textup{supp}(p(\cdot|s,a))}p(s^{\prime}|s,a)$ denotes the
minimum transition probability over all successor states of $(s,a)$. Note that
this result cannot be implied by Theorem 1, because the result for Iterated
CVaR RL there depends on $\frac{1}{\alpha}$, and simply taking $\alpha\to 0$
leads to a vacuous bound.

Theorem 4 demonstrates that algorithm $\mathtt{MaxWP}$ enjoys a constant
regret with respect to $K$. This constant regret is made possible by the
unique feature of Worst Path RL that, under the worst path metric, once the
agent determines the connectivity among states, she can accurately estimate
the value function and find the optimal policy. Furthermore, determining the
connectivity among states (with a given confidence) only requires a number of
samples independent of $K$. $\mathtt{MaxWP}$ effectively utilizes this problem
feature, and efficiently explores the connectivity among states.

To validate the optimality of our regret upper bound, we also provide a lower
bound $\Omega(\max_{(s,a):\exists h,\
a\neq\pi^{*}_{h}(s)}\frac{H}{\min_{\pi:\upsilon_{\pi}(s,a)>0}\upsilon_{\pi}(s,a)\cdot\min_{s^{\prime}\in\textup{supp}(p(\cdot|s,a))}p(s^{\prime}|s,a)})$
for Worst Path RL, which demonstrates the tightness of the 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)$.

##  7 Conclusion

In this paper, we investigate a novel Iterated CVaR RL problem with the regret
minimization and best policy identification metrics. We design two efficient
algorithms $\mathtt{ICVaR\mbox{-}RM}$ and $\mathtt{ICVaR\mbox{-}BPI}$, and
provide nearly matching regret/sample complexity upper and lower bounds with
respect to $K$. We also study an interesting limiting case called Worst Path
RL, and propose a simple and efficient algorithm $\mathtt{MaxWP}$ with
rigorous regret guarantees. There are several interesting directions for
future work, e.g., further closing the gap between upper and lower bounds, and
extending our model and results from the tabular setting to the function
approximation framework.

## Acknowledgements

The work of Yihan Du and Longbo Huang is supported by the Technology and
Innovation Major Project of the Ministry of Science and Technology of China
under Grant 2020AAA0108400 and 2020AAA0108403, the Tsinghua University
Initiative Scientific Research Program, and Tsinghua Precision Medicine
Foundation 10001020109. The work of Siwei Wang was supported in part by the
National Natural Science Foundation of China Grant 62106122.

## References

  * Agrawal & Jia (2017) Shipra Agrawal and Randy Jia.  Optimistic posterior sampling for reinforcement learning: worst-case regret bounds.  _Advances in Neural Information Processing Systems_ , 30, 2017.
  * Artzner et al. (1999) Philippe Artzner, Freddy Delbaen, Jean-Marc Eber, and David Heath.  Coherent measures of risk.  _Mathematical Finance_ , 9(3):203–228, 1999.
  * Auer et al. (2002) Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E. Schapire.  The non-stochastic multi-armed bandit problem.  _SIAM Journal on Computing_ , 32(1):48–77, 2002\.
  * Azar et al. (2017) Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos.  Minimax regret bounds for reinforcement learning.  In _International Conference on Machine Learning_ , pp. 263–272. PMLR, 2017.
  * Bäuerle & Glauner (2022) Nicole Bäuerle and Alexander Glauner.  Markov decision processes with recursive risk measures.  _European Journal of Operational Research_ , 296(3):953–966, 2022.
  * Bäuerle & Ott (2011) Nicole Bäuerle and Jonathan Ott.  Markov decision processes with average-value-at-risk criteria.  _Mathematical Methods of Operations Research_ , 74(3):361–379, 2011.
  * Boda & Filar (2006) Kang Boda and Jerzy A Filar.  Time consistent dynamic risk measures.  _Mathematical Methods of Operations Research_ , 63(1):169–186, 2006.
  * Borkar & Jain (2014) Vivek Borkar and Rahul Jain.  Risk-constrained markov decision processes.  _IEEE Transactions on Automatic Control_ , 59(9):2574–2579, 2014.
  * Borkar (2001) Vivek S Borkar.  A sensitivity formula for risk-sensitive cost and the actor–critic algorithm.  _Systems & Control Letters_, 44(5):339–346, 2001.
  * Borkar (2002) Vivek S Borkar.  Q-learning for risk-sensitive control.  _Mathematics of Operations Research_ , 27(2):294–311, 2002.
  * Brown (2007) David B Brown.  Large deviations bounds for estimating conditional value-at-risk.  _Operations Research Letters_ , 35(6):722–730, 2007.
  * Cheng et al. (2019) Richard Cheng, Gábor Orosz, Richard M Murray, and Joel W Burdick.  End-to-end safe reinforcement learning through barrier functions for safety-critical continuous control tasks.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 33, pp. 3387–3395, 2019.
  * Chow & Ghavamzadeh (2014) Yinlam Chow and Mohammad Ghavamzadeh.  Algorithms for CVaR optimization in MDPs.  In _Advances in Neural Information Processing Systems_ , volume 27, 2014.
  * Chow et al. (2015) Yinlam Chow, Aviv Tamar, Shie Mannor, and Marco Pavone.  Risk-sensitive and robust decision-making: a CVaR optimization approach.  In _Advances in Neural Information Processing Systems_ , volume 28, 2015.
  * Chow et al. (2017) Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone.  Risk-constrained reinforcement learning with percentile risk criteria.  _Journal of Machine Learning Research_ , 18(1):6070–6120, 2017.
  * Chu & Zhang (2014) Shanyun Chu and Yi Zhang.  Markov decision processes with iterated coherent risk measures.  _International Journal of Control_ , 87(11):2286–2293, 2014.
  * Coraluppi & Marcus (1997) Stefano P Coraluppi and Steven I Marcus.  Mixed risk-neutral/minimax control of markov decision processes.  In _Proceedings 31st Conference on Information Sciences and Systems_. Citeseer, 1997.
  * Coraluppi & Marcus (1999) Stefano P Coraluppi and Steven I Marcus.  Risk-sensitive and minimax control of discrete-time, finite-state markov decision processes.  _Automatica_ , 35(2):301–309, 1999.
  * Coronato et al. (2020) Antonio Coronato, Muddasar Naeem, Giuseppe De Pietro, and Giovanni Paragliola.  Reinforcement learning for intelligent healthcare applications: A survey.  _Artificial Intelligence in Medicine_ , 109:101964, 2020\.
  * Dann & Brunskill (2015) Christoph Dann and Emma Brunskill.  Sample complexity of episodic fixed-horizon reinforcement learning.  In _Advances in Neural Information Processing Systems_ , pp. 2818–2826, 2015.
  * Dann et al. (2017) Christoph Dann, Tor Lattimore, and Emma Brunskill.  Unifying PAC and regret: Uniform PAC bounds for episodic reinforcement learning.  In _Advances in Neural Information Processing Systems_ , volume 30, 2017.
  * Di Castro et al. (2012) Dotan Di Castro, Aviv Tamar, and Shie Mannor.  Policy gradients with variance related risk criteria.  _arXiv preprint arXiv:1206.6404_ , 2012.
  * Fatemi et al. (2019) Mehdi Fatemi, Shikhar Sharma, Harm Van Seijen, and Samira Ebrahimi Kahou.  Dead-ends and secure exploration in reinforcement learning.  In _International Conference on Machine Learning_ , pp. 1873–1881. PMLR, 2019.
  * Fatemi et al. (2021) Mehdi Fatemi, Taylor W Killian, Jayakumar Subramanian, and Marzyeh Ghassemi.  Medical dead-ends and learning to identify high-risk states and treatments.  _Advances in Neural Information Processing Systems_ , 34:4856–4870, 2021.
  * Fei et al. (2020) Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang, and Qiaomin Xie.  Risk-sensitive reinforcement learning: Near-optimal risk-sample tradeoff in regret.  In _Advances in Neural Information Processing Systems_ , volume 33, pp. 22384–22395, 2020.
  * Fei et al. (2021a) Yingjie Fei, Zhuoran Yang, Yudong Chen, and Zhaoran Wang.  Exponential bellman equation and improved regret bounds for risk-sensitive reinforcement learning.  In _Advances in Neural Information Processing Systems_ , volume 34, 2021a.
  * Fei et al. (2021b) Yingjie Fei, Zhuoran Yang, and Zhaoran Wang.  Risk-sensitive reinforcement learning with function approximation: A debiasing approach.  In _International Conference on Machine Learning_ , pp. 3198–3207. PMLR, 2021b.
  * Fiechter (1994) Claude-Nicolas Fiechter.  Efficient reinforcement learning.  In _Conference on Computational Learning Theory_ , pp. 88–97, 1994\.
  * Garcıa & Fernández (2015) Javier Garcıa and Fernando Fernández.  A comprehensive survey on safe reinforcement learning.  _Journal of Machine Learning Research_ , 16(1):1437–1480, 2015.
  * Hardy & Wirch (2004) Mary R Hardy and Julia L Wirch.  The iterated CTE: a dynamic risk measure.  _North American Actuarial Journal_ , 8(4):62–75, 2004.
  * Haskell & Jain (2015) William B Haskell and Rahul Jain.  A convex analytic approach to risk-aware markov decision processes.  _SIAM Journal on Control and Optimization_ , 53(3):1569–1598, 2015.
  * Heger (1994) Matthias Heger.  Consideration of risk in reinforcement learning.  In _International Conference on Machine Learning_ , pp. 105–111. Elsevier, 1994.
  * Jaksch et al. (2010) Thomas Jaksch, Ronald Ortner, and Peter Auer.  Near-optimal regret bounds for reinforcement learning.  _Journal of Machine Learning Research_ , 11(4), 2010.
  * Jin et al. (2018) Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.  Is Q-learning provably efficient?  In _Advances in Neural Information Processing Systems_ , volume 31, 2018.
  * Johnson & Kannan (2002) Eric Johnson and Suresh Kannan.  Adaptive flight control for an autonomous unmanned helicopter.  In _AIAA Guidance, Navigation, and Control Conference and Exhibit_ , pp. 4439, 2002.
  * Kaelbling et al. (1996) Leslie Pack Kaelbling, Michael L Littman, and Andrew W Moore.  Reinforcement learning: A survey.  _Journal of Artificial Intelligence Research_ , 4:237–285, 1996.
  * Kaufmann et al. (2021) Emilie Kaufmann, Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Edouard Leurent, and Michal Valko.  Adaptive reward-free exploration.  In _Algorithmic Learning Theory_ , pp. 865–891. PMLR, 2021.
  * Keramati et al. (2020) Ramtin Keramati, Christoph Dann, Alex Tamkin, and Emma Brunskill.  Being optimistic to be conservative: Quickly learning a cvar policy.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 34, pp. 4436–4443, 2020.
  * La & Ghavamzadeh (2013) Prashanth La and Mohammad Ghavamzadeh.  Actor-critic algorithms for risk-sensitive MDPs.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Ménard et al. (2021) Pierre Ménard, Omar Darwiche Domingues, Anders Jonsson, Emilie Kaufmann, Edouard Leurent, and Michal Valko.  Fast active learning for pure exploration in reinforcement learning.  In _International Conference on Machine Learning_ , pp. 7599–7608. PMLR, 2021.
  * Osogami (2012) Takayuki Osogami.  Iterated risk measures for risk-sensitive markov decision processes with discounted cost.  _arXiv preprint arXiv:1202.3755_ , 2012.
  * Ott (2010) Jonathan Theodor Ott.  A markov decision model for a surveillance application and risk-sensitive markov decision processes.  2010\.
  * Rockafellar et al. (2000) R Tyrrell Rockafellar, Stanislav Uryasev, et al.  Optimization of conditional value-at-risk.  _Journal of Risk_ , 2:21–42, 2000.
  * Shapiro et al. (2021) Alexander Shapiro, Darinka Dentcheva, and Andrzej Ruszczynski.  _Lectures on stochastic programming: modeling and theory_.  SIAM, 2021.
  * Sutton & Barto (2018) Richard S Sutton and Andrew G Barto.  _Reinforcement learning: An introduction_.  MIT press, 2018.
  * Szepesvári (2010) Csaba Szepesvári.  Algorithms for reinforcement learning.  _Synthesis Lectures on Artificial Intelligence and Machine Learning_ , 4(1):1–103, 2010.
  * Tamar et al. (2015) Aviv Tamar, Yonatan Glassner, and Shie Mannor.  Optimizing the CVaR via sampling.  In _AAAI Conference on Artificial Intelligence_ , 2015.
  * Thomas & Learned-Miller (2019) Philip Thomas and Erik Learned-Miller.  Concentration inequalities for conditional value-at-risk.  In _International Conference on Machine Learning_ , pp. 6225–6233. PMLR, 2019.
  * Wang et al. (2019) Chunhao Wang, Xiaofeng Zhu, Julian C Hong, and Dandan Zheng.  Artificial intelligence in radiotherapy treatment planning: present and future.  _Technology in cancer research & treatment_, 18:1533033819873922, 2019.
  * Weissman et al. (2003) Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger.  Inequalities for the $\ell$1 deviation of the empirical distribution.  _Hewlett-Packard Labs, Tech. Rep_ , 2003.
  * Wen et al. (2020) Lu Wen, Jingliang Duan, Shengbo Eben Li, Shaobing Xu, and Huei Peng.  Safe reinforcement learning for autonomous vehicles through parallel constrained policy optimization.  In _IEEE International Conference on Intelligent Transportation Systems_ , pp. 1–7. IEEE, 2020.
  * Zanette & Brunskill (2019) Andrea Zanette and Emma Brunskill.  Tighter problem-dependent regret bounds in reinforcement learning without domain knowledge using value function bounds.  In _International Conference on Machine Learning_ , pp. 7304–7312. PMLR, 2019.

##  Appendix A Experiments

In this section, we provide experimental results to evaluate the empirical
performance of our algorithm $\mathtt{ICVaR\mbox{-}RM}$, and compare it to the
state-of-the-art algorithms $\mathtt{EULER}$ (Zanette & Brunskill, 2019) and
$\mathtt{RSVI2}$ (Fei et al., 2021a) for classic RL and risk-sensitive RL,
respectively.

In our experiments, we consider an $H$-layered MDP with $S=3(H-1)+1$ states
and $A$ actions. There is a single state $s_{0}$ (initial state) in layer $1$.
For any $2\leq h\leq H$, there are three states $s_{3(h-2)+1},s_{3(h-2)+2}$
and $s_{3(h-2)+3}$ in layer $h$, which induce rewards $1,0$ and $0.4$,
respectively. The agent starts from $s_{0}$ in layer 1, and for each step
$h\in[H]$, she takes an action from $\\{a_{1},\dots,a_{A}\\}$, and then
transitions to one of three states in the next layer. For any
$a\in\\{a_{1},\dots,a_{A-1}\\}$, action $a$ leads to $s_{3(h-1)+1}$ and
$s_{3(h-1)+2}$ with probabilities $0.5$ and $0.5$, respectively. Action
$a_{A}$ leads to $s_{3(h-1)+2}$ and $s_{3(h-1)+3}$ with probabilities $0.001$
and $0.999$, respectively.

We set $\alpha\in\\{0.05,0.1,0.15\\}$, $\delta\in\\{0.5,0.005,0.00005\\}$,
$H\in\\{2,5,10\\}$, $S\in\\{7,13,25\\}$, $A\in\\{3,5,12\\}$ and
$K\in[0,10000]$ (the change of $K$ can be seen from the X-axis in Figure 2).
We take $\alpha=0.05$, $\delta=0.005$, $H=5$, $S=13$, $A=5$ and $K=10000$ as
the basic setting, and change parameters $\alpha$, $\delta$, $H$, $S$, $A$ and
$K$ to see how they affect the empirical performance of algorithm
$\mathtt{ICVaR\mbox{-}RM}$. For each algorithm, we perform $20$ independent
runs and report the average regret across runs with $95\%$ confidence
intervals.

As shown in Figure 2, our algorithm $\mathtt{ICVaR\mbox{-}RM}$ achieves a
significantly lower regret than the other algorithms $\mathtt{EULER}$ (Zanette
& Brunskill, 2019) and $\mathtt{RSVI2}$ (Fei et al., 2021a), which
demonstrates that $\mathtt{ICVaR\mbox{-}RM}$ can effectively control the risk
under the Iterated CVaR criterion and shows performance superiority over the
baselines. Moreover, the influences of parameters $\alpha$, $\delta$, $H$,
$S$, $A$ and $K$ on the regret of algorithm $\mathtt{ICVaR\mbox{-}RM}$ match
our theoretical bounds. Specifically, as $\alpha$ or $\delta$ increases, the
regret of $\mathtt{ICVaR\mbox{-}RM}$ decreases. As $H,S$ or $A$ increases, the
regret of $\mathtt{ICVaR\mbox{-}RM}$ increases as well. As the number of
episodes $K$ increases, the regret of $\mathtt{ICVaR\mbox{-}RM}$ increases at
a sublinear rate.

(a) $\alpha=0.05$

(b) $\alpha=0.1$

(c) $\alpha=0.15$

(d) $\delta=0.00005$

(e) $\delta=0.005$

(f) $\delta=0.5$

(g) $H=2$

(h) $H=5$

(i) $H=10$

(j) $S=7$

(k) $S=13$

(l) $S=25$

(m) $A=3$

(n) $A=5$

(o) $A=12$

Figure 2: Experimental results for Iterated CVaR RL.

##  Appendix B Related Work

Below we present a complete review of related works.

CVaR-based MDPs (Known Transition). Boda & Filar (2006); Ott (2010); Bäuerle &
Ott (2011); Haskell & Jain (2015); Chow et al. (2015) study the CVaR MDP
problem where the objective is to minimize the CVaR of the total cost with
known transition, and demonstrate that the optimal policy for CVaR MDP is
history-dependent (not Markovian) and is inefficient to exactly compute. Hardy
& Wirch (2004) firstly define the Iterated CVaR measure, and prove that it is
a coherent dynamic risk measure, and applicable to equity-linked insurance.
Osogami (2012); Chu & Zhang (2014); Bäuerle & Glauner (2022) investigate
iterated coherent risk measures (including Iterated CVaR) in MDPs, and prove
the existence of Markovian optimal policies for these MDPs. The above works
focus mainly on designing planning algorithms and derive planning error
guarantees for _known_ transition, while our work develops RL algorithms
(interacting with the environment online) and provides regret and sample
complexity guarantees for _unknown_ transition.

Risk-Sensitive Reinforcement Learning (Unknown Transition). Heger (1994);
Coraluppi & Marcus (1997; 1999) consider minimizing the worst-case cost in RL,
and present dynamic programming of value functions and heuristic algorithms
without theoretical analysis. Borkar (2001; 2002) study risk-sensitive RL with
the exponential utility measure, and design algorithms based on actor–critic
learning and Q-learning, respectively. Di Castro et al. (2012); La &
Ghavamzadeh (2013) investigate variance-related risk measures, and devise
policy gradient and actor-critic-based algorithms with convergence analysis.
Tamar et al. (2015) consider maximizing the CVaR of the total reward, and
propose a sampling-based estimator for the CVaR gradient and a stochastic
gradient decent algorithm to optimize CVaR.  Keramati et al. (2020) also
investigate optimizing the CVaR of the total reward, and design an algorithm
based on an optimistic version of the distributional Bellman operator. Borkar
& Jain (2014); Chow & Ghavamzadeh (2014); Chow et al. (2017) study how to
minimize the expected total cost with CVaR-based constraints, and develop
policy gradient, actor-critic and stochastic approximation-style algorithms.
The above works mainly give convergence analysis, and do not provide finite-
time regret and sample complexity guarantees as in our work.

To our best knowledge, there are only a few risk-sensitive RL works which
provide finite-time regret analysis (Fei et al., 2020; 2021a; 2021b). Fei et
al. (2020) consider risk-sensitive RL with the exponential utility criterion,
and propose algorithms based on logarithmic-exponential transformation and
least-squares updates. Fei et al. (2021a) further improve the regret bound in
(Fei et al., 2020) by developing an exponential Bellmen equation and a Bellman
backup analytical procedure. Fei et al. (2021b) extend the model and results
in (Fei et al., 2020; 2021a) from the tabular setting to the function
approximation framework. Our work is very different from the above works (Fei
et al., 2020; 2021a; 2021b) in formulation, algorithms and results. The above
works (Fei et al., 2020; 2021a; 2021b) use the exponential utility criterion
to characterize the risk and take all successor states into account in
decision making. They design algorithms based on exponential Bellmen equations
and doubly decaying exploration bonuses. In contrast, we interpret the risk by
the Iterated CVaR criterion, which primarily concerns the worst
$\alpha$-portion successor states. We develop algorithms using CVaR-adapted
exploration bonuses.

The works we discuss above fall in the literature of RL with risk-sensitive
criteria. There are also other RL works which focus on state-wise safety.
Cheng et al. (2019) utilize control barrier functions (CBFs) to ensure the
agent within a set of safe sets and guide the learning by constraining
explorable polices. Fatemi et al. (2019; 2021) define the notion of dead-end
states (which lead to suboptimal terminal state with probability $1$ in finite
steps) and aim to avoid getting into dead-end states. The formulations and
algorithms in these works greatly differ from ours, and they do not provide
finite-time regret and sample complexity analysis as us. We refer interested
readers to the survey (Garcıa & Fernández, 2015) for detailed categorization
and discussion on safe RL.

##  Appendix C More Discussion on Iterated CVaR RL

In this section, we first present the expanded value function definitions for
Iterated CVaR RL. Then, we compare Iterated CVaR RL with existing risk-
sensitive MDP models, including CVaR MDP (Boda & Filar, 2006; Ott, 2010;
Bäuerle & Ott, 2011; Chow et al., 2015) and the exponential utility-based RL
(Fei et al., 2020; 2021a).

###  C.1 Value Function Definitions for Iterated CVaR RL

The value function definition for Iterated CVaR RL, i.e., Eq. (i) in Section
3, can be expanded as

$\displaystyle Q^{\pi}_{h}(s,a)$
$\displaystyle=r(s,a)+\textup{CVaR}^{\alpha}_{s_{h+1}\sim
p(\cdot|s,a)}\bigg{(}r(s_{h+1},\pi_{h+1}(s_{h+1}))$
$\displaystyle\\!\\!\\!+\textup{CVaR}^{\alpha}_{s_{h+2}\sim
p(\cdot|s_{h+1},\pi_{h+1}(s_{h+1}))}\Big{(}\dots\textup{CVaR}^{\alpha}_{s_{H}\sim
p(\cdot|s_{H-1},\pi_{H-1}(s_{H-1}))}(r(s_{H},\pi_{H}(s_{H})))\Big{)}\bigg{)},$
$\displaystyle V^{\pi}_{h}(s)$
$\displaystyle=r(s,\pi_{h}(s))+\textup{CVaR}^{\alpha}_{s_{h+1}\sim
p(\cdot|s,\pi_{h}(s))}\bigg{(}r(s_{h+1},\pi_{h+1}(s_{h+1}))$
$\displaystyle\\!\\!\\!+\textup{CVaR}^{\alpha}_{s_{h+2}\sim
p(\cdot|s_{h+1},\pi_{h+1}(s_{h+1}))}\Big{(}\dots\textup{CVaR}^{\alpha}_{s_{H}\sim
p(\cdot|s_{H-1},\pi_{H-1}(s_{H-1}))}(r(s_{H},\pi_{H}(s_{H})))\Big{)}\bigg{)}.$

Similarly, the optimal value function definition, e.g., Eq. (ii) in Section 3,
can be expanded as

$\displaystyle
Q^{*}_{h}(s,a)\\!=\\!\max_{\pi}\\!\Bigg{\\{}r(s,a)+\textup{CVaR}^{\alpha}_{s_{h+1}\sim
p(\cdot|s,a)}\bigg{(}r(s_{h+1},\pi_{h+1}(s_{h+1}))$
$\displaystyle+\textup{CVaR}^{\alpha}_{s_{h+2}\sim
p(\cdot|s_{h+1},\pi_{h+1}(s_{h+1}))}\Big{(}\\!\dots\\!\textup{CVaR}^{\alpha}_{s_{H}\sim
p(\cdot|s_{H-1},\pi_{H-1}(s_{H-1}))}(r(s_{H},\pi_{H}(s_{H})))\Big{)}\bigg{)}\Bigg{\\}},$
$\displaystyle
V^{*}_{h}(s)\\!=\\!\max_{\pi}\\!\Bigg{\\{}r(s,\pi_{h}(s))+\textup{CVaR}^{\alpha}_{s_{h+1}\sim
p(\cdot|s,\pi_{h}(s))}\bigg{(}r(s_{h+1},\pi_{h+1}(s_{h+1}))$
$\displaystyle+\textup{CVaR}^{\alpha}_{s_{h+2}\sim
p(\cdot|s_{h+1},\pi_{h+1}(s_{h+1}))}\Big{(}\\!\dots\\!\textup{CVaR}^{\alpha}_{s_{H}\sim
p(\cdot|s_{H-1},\pi_{H-1}(s_{H-1}))}(r(s_{H},\pi_{H}(s_{H})))\Big{)}\bigg{)}\Bigg{\\}}.$
(6)

From the above value function definitions, we can see that, Iterated CVaR RL
aims to maximize the worst $\alpha$-portion tail of the reward-to-go at each
step, i.e., taking the CVaR operator on the reward-to-go at each step.
Intuitively, Iterated CVaR RL wants to optimize the performance even when bad
situations happen at each decision stage.

###  C.2 Comparison with CVaR MDP

Figure 3: Illustrating example for the comparison between CVaR MDP and
Iterated CVaR RL.

The objective of CVaR MDP, e.g., (Boda & Filar, 2006; Ott, 2010; Bäuerle &
Ott, 2011; Chow et al., 2015), is to maximize the worst $\alpha$-portion of
the _total_ reward, which is formally defined as

$\displaystyle\max_{\pi}\ \textup{CVaR}^{\alpha}_{(s_{h},a_{h})\sim
p,\pi}\left(\sum_{h=1}^{H}r(s_{h},a_{h})\right).$

Compared to our Iterated CVaR RL (Eq. (6) and Eq. (ii) in Section 3) which
concerns bad situations _at each step_ , CVaR MDP takes more cumulative reward
into account and prefers actions which have better performance in general, but
can have larger probabilities of getting into catastrophic states. Thus, CVaR
MDP is suitable for scenarios where bad situations lead to a higher cost but
not fatal damage, e.g., finance. In contrast, Iterated CVaR RL prefers actions
which have smaller probabilities of getting into catastrophic states. Hence,
Iterated CVaR RL is most suitable for safety-critical applications, where
catastrophic states are unacceptable and need to be carefully avoid, e.g.,
clinical treatment planning.

We emphasize that Iterated CVaR is _not equivalent to_ simply taking the worst
$\alpha^{H}$-portion of the total reward. In fact, the good
$(1-\alpha^{H})$-portion of the total reward also contributes to Iterated
CVaR. This is because Iterated CVaR accounts bad situations for all states
(both good and bad states) in its iterated computation, instead of just
considering bad situations upon bad states.

Below we provide an example of clinical treatment planning to illustrate the
difference between Iterated CVaR and CVaR MDP. Here we interpret the objective
as cost minimization for ease of understanding, and set the risk level
$\alpha=0.05$.

Consider a 4-layered binary tree-structured MDP shown in Figure 3. The state
sets in layers 1, 2, 3 and 4 are $\\{s_{1}\\}$, $\\{s_{2},s_{3}\\}$,
$\\{s_{4},\dots,s_{7}\\}$ and $\\{s_{8},\dots,s_{15}\\}$, respectively. There
are two actions $a_{1},a_{2}$ in each state, and $a_{1},a_{2}$ have the same
transition distribution in all states except the initial state $s_{1}$. Thus,
a policy is to decide whether to choose $a_{1}$ or $a_{2}$ in state $s_{1}$,
which leads to different subsequent costs.

The agent starts from the initial state $s_{1}$ in layer 1. If the agent takes
action $a_{1}$, she will transition to state $s_{2}$ deterministically, and
goes into the left sub-tree. On the other hand, if the agent takes action
$a_{2}$ in state $s_{1}$, she will transition to state $s_{3}$
deterministically, and enters the right sub-tree.

If the agent goes into the left sub-tree (state $s_{2}$) in layer 2, she will
transition to $s_{4}$ and $s_{5}$ in layer 3 with probabilities $0.05$ and
$0.95$, respectively. Then, if she starts from state $s_{4}$ in layer 3, she
will transition to $s_{8}$ and $s_{9}$ in layer 4 with probabilities $0.05$
and $0.95$, respectively. Otherwise, if she starts from state $s_{5}$ in layer
3, she will transition to $s_{10}$ and $s_{11}$ in layer 4 with probabilities
$0.05$ and $0.95$, respectively.

On the other hand, if the agent goes into the right sub-tree (state $s_{3}$)
in layer 2, she will transition to $s_{6}$ and $s_{7}$ in layer 3 with
probabilities $0.01$ and $0.99$, respectively. Then, if she starts from state
$s_{6}$ in layer 3, she will transition to $s_{12}$ and $s_{13}$ in layer 4
with probabilities $0.01$ and $0.99$, respectively. Otherwise, if she starts
from state $s_{7}$ in layer 3, she will transition to $s_{14}$ and $s_{15}$ in
layer 4 with probabilities $0.01$ and $0.99$, respectively.

The costs are state-dependent, and only the states in layer 4 produce non-zero
costs. To be concrete, we use the clinical trial example and the costs
represent the patient status. Specifically, in layer 4, $s_{8}$ and $s_{12}$
give costs 1, which denote _death_. $s_{13}$ and $s_{14}$ produce costs 0.5,
which means the patient is _getting better_. $s_{9}$ and $s_{10}$ induce costs
0.4, which denote that the patient _gets much better_. $s_{11}$ and $s_{15}$
produce costs 0, which stand for that the patient is _fully cured_.

Under the CVaR criterion, we have that

$Q^{\textup{CVaR},\alpha}(s_{1},a_{1})=\frac{0.0025}{0.05}\cdot
1+\frac{0.05-0.0025}{0.05}\cdot 0.4=0.43,$

and

$Q^{\textup{CVaR},\alpha}(s_{1},a_{2})=\frac{0.0001}{0.05}\cdot
1+\frac{0.05-0.0001}{0.05}\cdot 0.5=0.501.$

Thus, CVaR MDP will choose action $a_{1}$ (and goes into the left sub-tree),
since $a_{1}$ leads to better medium states $s_{9}$ and $s_{10}$, which give a
lower cost $0.4$ than the cost $0.5$ produced by the right sub-tree.

On the other hand, under the Iterated CVaR criterion, we have that

$Q^{\textup{ICVaR},\alpha}(s_{1},a_{1})=\frac{0.05}{0.05}\cdot
Q^{\textup{ICVaR},\alpha}(s_{4},\cdot)=\frac{0.05}{0.05}\cdot\left(\frac{0.05}{0.05}\cdot
Q^{\textup{ICVaR},\alpha}(s_{8},\cdot)\right)=\frac{0.05}{0.05}\cdot\left(\frac{0.05}{0.05}\cdot
1\right)=1,$

and

$\displaystyle Q^{\textup{ICVaR},\alpha}(s_{1},a_{2})$ $\displaystyle=$
$\displaystyle\frac{0.01}{0.05}\cdot
Q^{\textup{ICVaR},\alpha}(s_{6},\cdot)+\frac{0.05-0.01}{0.05}\cdot
Q^{\textup{ICVaR},\alpha}(s_{7},\cdot)$ $\displaystyle=$
$\displaystyle\frac{0.01}{0.05}\cdot\left(\frac{0.01}{0.05}\cdot
Q^{\textup{ICVaR},\alpha}(s_{12},\cdot)+\frac{0.05-0.01}{0.05}\cdot
Q^{\textup{ICVaR},\alpha}(s_{13},\cdot)\right)$
$\displaystyle+\frac{0.05-0.01}{0.05}\cdot\left(\frac{0.01}{0.05}\cdot
Q^{\textup{ICVaR},\alpha}(s_{14},\cdot)+\frac{0.05-0.01}{0.05}\cdot
Q^{\textup{ICVaR},\alpha}(s_{15},\cdot)\right)$ $\displaystyle=$
$\displaystyle\frac{0.01}{0.05}\cdot\left(\frac{0.01}{0.05}\cdot
1+\frac{0.05-0.01}{0.05}\cdot
0.5\right)+\frac{0.05-0.01}{0.05}\cdot\left(\frac{0.01}{0.05}\cdot
0.5+\frac{0.05-0.01}{0.05}\cdot 0\right)$ $\displaystyle=$ $\displaystyle
0.2.$

Thus, Iterated CVaR RL will instead choose action $a_{2}$, because $a_{2}$ has
a smaller probability of going into the bad left direction (which leads to the
catastrophic state $s_{12}$).

The above example shows that, Iterated CVaR RL prefers actions with a smaller
probability of getting into catastrophic states. In contrast, CVaR MDP favors
actions with better average therapeutic effects, but has a larger probability
of causing death.

Note that the above example also demonstrates that Iterated CVaR is _not
equivalent_ to the worst $\alpha^{H}$-portion of the total cost. To see this,
we have that (here we consider $\alpha^{3}$ because there are $3$ transition
steps):

$Q^{\textup{CVaR},\alpha^{3}}(s_{1},a_{2})=\frac{0.0001}{0.000125}\cdot
1+\frac{0.000125-0.0001}{0.000125}\cdot 0.5=0.9,$

and

$\displaystyle Q^{\textup{ICVaR},\alpha}(s_{1},a_{2})$ $\displaystyle=$
$\displaystyle\frac{0.01}{0.05}\cdot\left(\frac{0.01}{0.05}\cdot
1+\frac{0.05-0.01}{0.05}\cdot
0.5\right)+\frac{0.05-0.01}{0.05}\cdot\left(\frac{0.01}{0.05}\cdot
0.5+\frac{0.05-0.01}{0.05}\cdot 0\right)$ $\displaystyle=$ $\displaystyle
0.2.$

In addition, one can see that, the good state which gives cost 0 (i.e.,
$s_{15}$) also contributes to $Q^{\textup{ICVaR},\alpha}(s_{1},a_{2})$, which
shows that the good $(1-\alpha^{H})$-portion of the total cost also matters
for Iterated CVaR.

###  C.3 Comparison with exponential utility-based risk-sensitive RL

The Bellman optimality equation for risk-sensitive RL with the exponential
utility criterion (Fei et al., 2020; 2021a) is defined as

$Q^{*}_{h}(s,a)=r_{h}(s,a)+\frac{1}{\beta}\log\\{\mathbb{E}_{s^{\prime}\sim
p(\cdot|s,a)}[\exp(\beta\cdot V^{*}_{h+1}(s^{\prime}))]\\},$

which takes all successor states $s^{\prime}$ into account, i.e., all
successor states $s^{\prime}$ contribute to the computation of the Q-value.
Here $\beta<0$ is a risk-sensitivity parameter.

In contrast, in Iterated CVaR RL, the Bellman optimality equation is defined
as

$Q^{*}_{h}(s,a)=r(s,a)+\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V^{*}_{h+1}(s^{\prime})),$

which focuses only on the worst $\alpha$-portion successor states $s^{\prime}$
(i.e., with the lowest $\alpha$-portion values $V^{*}_{h+1}(s^{\prime})$),
i.e., only the worst $\alpha$-portion successor states $s^{\prime}$ contribute
to the computation of the Q-value.

Besides the formulation, our algorithm design and results are also very
different from those in (Fei et al., 2020; 2021a). The algorithms in (Fei et
al., 2020; 2021a) are based on exponential Bellman equations and doubly
decaying exploration bonuses, and their results depend on $\exp(|\beta|H)$. In
contrast, our algorithms are based on value iteration for Iterated CVaR with
CVaR-adapted exploration bonuses, and our results depend on the minimum
between an MDP-intrinsic visitation measure
$1/\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)$ and a risk-level-dependent factor
$1/\alpha^{H-1}$.

##  Appendix D Proofs for Iterated CVaR RL with Regret Minimization

In this section, we present the proofs of regret upper and lower bounds
(Theorems 1 and 2) for Iterated CVaR RL-RM.

###  D.1 Proofs of Regret Upper Bound

####  D.1.1 Concentration

For any $k>0$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, let
$n_{kh}(s,a)$ denote the number of times that $(s,a)$ was visited at step $h$
before episode $k$, and let $n_{k}(s,a):=\sum_{h=1}^{H}n_{kh}(s,a)$ denote the
number of times that $(s,a)$ was visited before episode $k$.

######  Lemma 1 (Concentration for $V^{*}$).

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{KHSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall k\in[K],\ \forall h\in[H],\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{]}\geq 1-2\delta^{\prime}.$

###### Proof of Lemma 1.

Using Brown’s inequality (Brown, 2007) (Theorem 2 in (Thomas & Learned-Miller,
2019)) and a union bound over $(s,a)\in\mathcal{S}\times\mathcal{A}$ and
$n_{k}(s,a)\in[KH]$, we can obtain this lemma. ∎

For any risk level $\alpha\in(0,1]$, function $V:\mathcal{S}\mapsto\mathbb{R}$
and $(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}$,
$\beta^{\alpha,V}(s^{\prime}|s,a)$ is the conditional transition probability
from $(s,a)$ to $s^{\prime}$, conditioning on transitioning to the worst
$\alpha$-portion successor states $s^{\prime}$ (i.e., with the lowest
$\alpha$-portion values $V(s^{\prime})$). Let $\mu^{\alpha,V}(s^{\prime}|s,a)$
denote how large the transition probability of successor state $s^{\prime}$
belongs to the worst $\alpha$-portion, which satisfies that
$\frac{\mu^{\alpha,V}(s^{\prime}|s,a)}{\alpha}=\beta^{\alpha,V}(s^{\prime}|s,a)$
and $\sum_{s^{\prime}\in\mathcal{S}}\mu^{\alpha,V}(s^{\prime}|s,a)=\alpha$. In
addition, for any risk level $\alpha\in(0,1]$, function
$V:\mathcal{S}\mapsto\mathbb{R}$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,

$\displaystyle\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V(s^{\prime}))=$
$\displaystyle\frac{\sum_{s^{\prime}\in\mathcal{S}}\mu^{\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime})}{\alpha}=\sum_{s^{\prime}\in\mathcal{S}}\beta^{\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime}).$

######  Lemma 2 (Concentration for any $V$).

It holds that

$\displaystyle\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{KHSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall V:\mathcal{S}\mapsto[0,H],\ \forall k\in[K],\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{]}\geq 1-2\delta^{\prime}.$

Figure 4:  Illustrating example for Lemma 2. For each
$s^{\prime}\in\\{s_{1},s_{2},s_{3},s_{4}\\}$, the height of the bar denotes
the value $V(s^{\prime})$ (fixed), and the width of the bar denotes the
transition probability $p(s^{\prime}|s,a)$ or $\hat{p}^{k}(s^{\prime}|s,a)$.
The colored part of the bars denotes the worst $\alpha$-portion successor
states (i.e., with the lowest $\alpha$-portion values $V(s^{\prime})$). In
this example, $\alpha=0.5$.

###### Proof of Lemma 2.

As shown in Figure 4, we sort all successor states $s^{\prime}\in\mathcal{S}$
by $V(s^{\prime})$ in ascending order (from the left to the right). Add a
virtual line at the $\alpha$-quantile, denoted by _$\alpha$ -quantile line_.
Fix the value function $V(\cdot)$, and the transition probability changes from
$p(\cdot|s,a)$ to $\hat{p}^{k}(\cdot|s,a)$.

Without loss of generality, below we consider the case where as the transition
probability changes from $p(\cdot|s,a)$ to $\hat{p}^{k}(\cdot|s,a)$, the
$\alpha$-quantile line shifts from left to right (the analysis of the contrary
case can also be obtained by interchanging $p(\cdot|s,a)$ and
$\hat{p}^{k}(\cdot|s,a)$). We use _original $\alpha$-quantile line_ and
_shifted $\alpha$-quantile line_ to denote the $\alpha$-quantile line before
and after the shift, respectively.

We divide the successor states $s^{\prime}\in\mathcal{S}$ into five subsets as
follows. Let $\mathcal{S}_{left}$ and $\mathcal{S}_{right}$ denote the sets of
states which are always on the left and right sides of the original and
shifted $\alpha$-quantile lines, respectively. Let $\mathcal{S}_{middle}$
denote the set of states which are in the middle of the original and shifted
$\alpha$-quantile lines. Let $s_{line\mbox{-}l}$ and $s_{line\mbox{-}r}$
denote the states which lie on the original and shifted $\alpha$-quantile
lines, respectively.

For any $s^{\prime}\in\mathcal{S}_{left}$, we have that
$\mu^{\alpha,V}(s^{\prime}|s,a)=p(s^{\prime}|s,a)$ and
$\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)=\hat{p}^{k}(s^{\prime}|s,a)$.

For any $s^{\prime}\in\mathcal{S}_{right}$, we have
$\mu^{\alpha,V}(s^{\prime}|s,a)=\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)=0$.

For any $s^{\prime}\in\mathcal{S}_{middle}$, we have that
$\mu^{\alpha,V}(s^{\prime}|s,a)=0$ and
$\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)=\hat{p}^{k}(s^{\prime}|s,a)$.

For state $s_{line\mbox{-}l}$, we have that
$\mu^{\alpha,V}(s_{line\mbox{-}l}|s,a)=p(s_{line\mbox{-}l}|s,a)-(\sum_{s^{\prime}\in\mathcal{S}_{left}}p(s^{\prime}|s,a)+p(s_{line\mbox{-}l}|s,a)-\alpha)$
and
$\hat{\mu}^{k;\alpha,V}(s_{line\mbox{-}l}|s,a)=\hat{p}^{k}(s_{line\mbox{-}l}|s,a)$.

For state $s_{line\mbox{-}r}$, we have that
$\mu^{\alpha,V}(s_{line\mbox{-}r}|s,a)=0$ and
$\hat{\mu}^{k;\alpha,V}(s_{line\mbox{-}r}|s,a)=\alpha-\sum_{s^{\prime}\in\mathcal{S}_{left}}\hat{p}^{k}(s^{\prime}|s,a)-\sum_{s^{\prime}\in\mathcal{S}_{middle}}\hat{p}^{k}(s^{\prime}|s,a)-\hat{p}^{k}(s_{line\mbox{-}l}|s,a)$.

Then, we obtain

$\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|$
$\displaystyle\leq$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}_{left}}\left|\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right|+\sum_{s^{\prime}\in\mathcal{S}_{right}}\left|\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right|$
$\displaystyle+\sum_{s^{\prime}\in\mathcal{S}_{middle}}\left|\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right|+\left|\hat{\mu}^{k;\alpha,V}(s_{line\mbox{-}l}|s,a)-\mu^{\alpha,V}(s_{line\mbox{-}l}|s,a)\right|$
$\displaystyle+\left|\hat{\mu}^{k;\alpha,V}(s_{line\mbox{-}r}|s,a)-\mu^{\alpha,V}(s_{line\mbox{-}r}|s,a)\right|$
$\displaystyle\leq$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}_{left}}\left|\hat{p}^{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\right|+\sum_{s^{\prime}\in\mathcal{S}_{middle}}\hat{p}^{k}(s^{\prime}|s,a)$
$\displaystyle+\left|\hat{p}^{k}(s_{line\mbox{-}l}|s,a)-p(s_{line\mbox{-}l}|s,a)+\left(\sum_{s^{\prime}\in\mathcal{S}_{left}}p(s^{\prime}|s,a)+p(s_{line\mbox{-}l}|s,a)-\alpha\right)\right|$
$\displaystyle+\left(\alpha-\sum_{s^{\prime}\in\mathcal{S}_{left}}\hat{p}^{k}(s^{\prime}|s,a)-\sum_{s^{\prime}\in\mathcal{S}_{middle}}\hat{p}^{k}(s^{\prime}|s,a)-\hat{p}^{k}(s_{line\mbox{-}l}|s,a)\right)$
$\displaystyle\leq$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}_{left}}\left|\hat{p}^{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\right|+\sum_{s^{\prime}\in\mathcal{S}_{middle}}\hat{p}^{k}(s^{\prime}|s,a)$
$\displaystyle+\left|\hat{p}^{k}(s_{line\mbox{-}l}|s,a)-p(s_{line\mbox{-}l}|s,a)\right|+\left|\sum_{s^{\prime}\in\mathcal{S}_{left}}p(s^{\prime}|s,a)+p(s_{line\mbox{-}l}|s,a)-\alpha\right|$
$\displaystyle+\left(\alpha-\sum_{s^{\prime}\in\mathcal{S}_{left}}\hat{p}^{k}(s^{\prime}|s,a)-\sum_{s^{\prime}\in\mathcal{S}_{middle}}\hat{p}^{k}(s^{\prime}|s,a)-\hat{p}^{k}(s_{line\mbox{-}l}|s,a)\right)$
$\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}_{left}}\left|\hat{p}^{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\right|+\sum_{s^{\prime}\in\mathcal{S}_{middle}}\hat{p}^{k}(s^{\prime}|s,a)$
$\displaystyle+\left|\hat{p}^{k}(s_{line\mbox{-}l}|s,a)-p(s_{line\mbox{-}l}|s,a)\right|+\left(\sum_{s^{\prime}\in\mathcal{S}_{left}}p(s^{\prime}|s,a)+p(s_{line\mbox{-}l}|s,a)-\alpha\right)$
$\displaystyle+\left(\alpha-\sum_{s^{\prime}\in\mathcal{S}_{left}}\hat{p}^{k}(s^{\prime}|s,a)-\sum_{s^{\prime}\in\mathcal{S}_{middle}}\hat{p}^{k}(s^{\prime}|s,a)-\hat{p}^{k}(s_{line\mbox{-}l}|s,a)\right)$
$\displaystyle=$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}_{left}}\left|\hat{p}^{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\right|+\left|\hat{p}^{k}(s_{line\mbox{-}l}|s,a)-p(s_{line\mbox{-}l}|s,a)\right|$
$\displaystyle+\sum_{s^{\prime}\in\mathcal{S}_{left}}p(s^{\prime}|s,a)-\sum_{s^{\prime}\in\mathcal{S}_{left}}\hat{p}^{k}(s^{\prime}|s,a)+p(s_{line\mbox{-}l}|s,a)-\hat{p}^{k}(s_{line\mbox{-}l}|s,a)$
$\displaystyle\leq$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}_{left}}\left|\hat{p}^{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\right|+\left|\hat{p}^{k}(s_{line\mbox{-}l}|s,a)-p(s_{line\mbox{-}l}|s,a)\right|$
$\displaystyle+\sum_{s^{\prime}\in\mathcal{S}_{left}}\left|p(s^{\prime}|s,a)-\hat{p}^{k}(s^{\prime}|s,a)\right|+\left|p(s_{line\mbox{-}l}|s,a)-\hat{p}^{k}(s_{line\mbox{-}l}|s,a)\right|$
$\displaystyle\leq$ $\displaystyle
2\sum_{s^{\prime}\in\mathcal{S}}\left|\hat{p}^{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\right|,$
(7)

where (a) is due to
$\sum_{s^{\prime}\in\mathcal{S}_{left}}p(s^{\prime}|s,a)+p(s_{line\mbox{-}l}|s,a)-\alpha\geq
0$ by the definition of state $s_{line\mbox{-}l}$.

Thus, we have

$\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|$ $\displaystyle=$
$\displaystyle\left|\frac{\sum_{s^{\prime}\in\mathcal{S}}\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime})}{\alpha}-\frac{\sum_{s^{\prime}\in\mathcal{S}}\mu^{\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime})}{\alpha}\right|$ $\displaystyle=$
$\displaystyle\frac{\left|\sum_{s^{\prime}\in\mathcal{S}}\left(\hat{\mu}^{k;\alpha,V}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right)\cdot
V(s^{\prime})\right|}{\alpha}$ $\displaystyle\leq$
$\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|\cdot
H}{\alpha}$ $\displaystyle\leq$
$\displaystyle\frac{2\sum_{s^{\prime}\in\mathcal{S}}\left|p^{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\right|\cdot
H}{\alpha}$ (8)

Using Eq. (55) in (Zanette & Brunskill, 2019) (originated from (Weissman et
al., 2003)), we have that with probability at least $1-2\delta^{\prime}$, for
any $k\in[K]$ and $(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{KHSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}}.$
(9)

Plugging Eq. (9) into Eq. (8), we obtain that with probability at least
$1-2\delta^{\prime}$, for any $k\in[K]$,
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and function
$V:\mathcal{S}\mapsto[0,H]$,

$\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{KHSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}}.$

∎

For any $k>0$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, let
$w_{kh}(s,a)$ denote the probability of visiting $(s,a)$ at step $h$ of
episode $k$. Then, it holds that for any $k>0$, $h\in[H]$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$, $w_{kh}(s,a)\in[0,1]$ and
$\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}w_{kh}(s,a)=1$.

######  Lemma 3 (Concentration of Visitation).

It holds that

$\displaystyle\Pr\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{]}\geq
1-\delta^{\prime}.$

###### Proof of Lemma 3.

Applying Lemma F.4 in (Dann et al., 2017), we have that for any fixed
$h\in[H]$,

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

By a union bound over $h\in[H]$, we have

$\displaystyle\Pr\left[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)\right]\geq
1-\delta^{\prime}.$

∎

To sum up, we define several concentration events which will be used in the
following proof.

$\displaystyle\mathcal{E}_{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{KHSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall k\in[K],\ \forall h\in[H],\
\forall(s,a)\in\mathcal{S}\times\mathcal{A}\Bigg{\\}}$
$\displaystyle\mathcal{E}_{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{KHSA}{\delta^{\prime}}\right)}{n_{k}(s,a)}},$
$\displaystyle\forall V:\mathcal{S}\mapsto[0,H],\ \forall k\in[K],\
\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{E}:=$
$\displaystyle\mathcal{E}_{1}\cap\mathcal{E}_{2}\cap\mathcal{E}_{3}$

######  Lemma 4.

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

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

###### Proof of Lemma 4.

This lemma can be obtained by combining Lemmas 1-3. ∎

####  D.1.2 Optimism, Visitation and CVaR Gap

Recall that $L:=\log\left(\frac{KHSA}{\delta^{\prime}}\right)$.

######  Lemma 5 (Optimism).

Suppose that event $\mathcal{E}$ holds. Then, for any $k\in[K]$, $h\in[H]$ and
$s\in\mathcal{S}$, we have

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

###### Proof of Lemma 5.

We prove this lemma by induction.

First, for any $k\in[K]$, $s\in\mathcal{S}$, it holds that
$\bar{V}^{k}_{H+1}(s)=V^{*}_{H+1}(s)=0$.

Then, for any $k\in[K]$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,
if $\bar{Q}^{k}_{h}(s,a)=H$, $\bar{Q}^{k}_{h}(s,a)\geq Q^{*}_{h}(s,a)$
trivially holds, and otherwise,

$\displaystyle\bar{Q}^{k}_{h}(s,a)=$ $\displaystyle
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{L}{n_{k}(s,a)}}$
$\displaystyle\overset{\textup{(a)}}{\geq}$ $\displaystyle
r(s,a)+\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s,a)}(V^{*}_{h+1}(s^{\prime}))+\frac{H}{\alpha}\sqrt{\frac{L}{n_{k}(s,a)}}$
$\displaystyle\overset{\textup{(b)}}{\geq}$ $\displaystyle
r(s,a)+\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V^{*}_{h+1}(s^{\prime}))$ $\displaystyle=$ $\displaystyle
Q^{*}_{h}(s,a),$

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

Thus, we have

$\displaystyle\bar{V}^{k}_{h}(s)\geq\bar{Q}^{k}_{h}(s,\pi^{*}_{h}(s))\geq
Q^{*}_{h}(s,\pi^{*}_{h}(s))=V^{*}_{h}(s),$

which concludes the proof. ∎

Following (Zanette & Brunskill, 2019), for any episode $k>0$, we define the
set of state-action pairs which have sufficient visitations in expectation as
follows.

$\displaystyle\mathcal{L}_{k}:=\left\\{(s,a)\in\mathcal{S}\times\mathcal{A}:\frac{1}{4}\sum_{k^{\prime}=1}^{k-1}\sum_{h=1}^{H}w_{k^{\prime}h}(s,a)\geq
H\log\left(\frac{HSA}{\delta^{\prime}}\right)+H\right\\}.$ (10)

######  Lemma 6 (Sufficient Visitation).

Suppose that event $\mathcal{E}$ holds. Then, for any $k>0$ and
$(s,a)\in\mathcal{L}_{k}$,

$\displaystyle
n_{k}(s,a)\geq\frac{1}{4}\sum_{k^{\prime}=1}^{k}\sum_{h=1}^{H}w_{k^{\prime}h}(s,a).$

###### Proof of Lemma 6.

This proof is the same as that of Lemma 6 in (Zanette & Brunskill, 2019).

Using Lemma 3, we have

$\displaystyle n_{k}(s,a)\geq$
$\displaystyle\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)$
$\displaystyle=$
$\displaystyle\frac{1}{4}\sum_{k^{\prime}=1}^{k-1}\sum_{h=1}^{H}w_{k^{\prime}h}(s,a)+\frac{1}{4}\sum_{k^{\prime}=1}^{k-1}\sum_{h=1}^{H}w_{k^{\prime}h}(s,a)-H\log\left(\frac{HSA}{\delta^{\prime}}\right)$
$\displaystyle\overset{\textup{(a)}}{\geq}$
$\displaystyle\frac{1}{4}\sum_{k^{\prime}=1}^{k-1}\sum_{h=1}^{H}w_{k^{\prime}h}(s,a)+H$
$\displaystyle\overset{\textup{(b)}}{\geq}$
$\displaystyle\frac{1}{4}\sum_{k^{\prime}=1}^{k-1}\sum_{h=1}^{H}w_{k^{\prime}h}(s,a)+\sum_{h=1}^{H}w_{kh}(s,a)$
$\displaystyle=$
$\displaystyle\frac{1}{4}\sum_{k^{\prime}=1}^{k}\sum_{h=1}^{H}w_{k^{\prime}h}(s,a)$

where (a) uses the fact that $(s,a)\in\mathcal{L}_{k}$ and the definition of
$\mathcal{L}_{k}$, and (b) is due to that for any $k>0$, $h\in[H]$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$, $w_{kh}(s,a)\in[0,1]$. ∎

######  Lemma 7 (Standard Visitation Ratio).

For any $K>0$, we have

$\displaystyle\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}\frac{w_{kh}(s,a)}{n_{k}(s,a)}}\leq$
$\displaystyle 2\sqrt{SA\log\left(\frac{KHSA}{\delta^{\prime}}\right)}.$

###### Proof of Lemma 7.

This proof is the same as that of Lemma 13 in (Zanette & Brunskill, 2019).

Recall that for any $k>0$, let
$w_{k}(s,a):=\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}w_{kh}(s,a)$. Then, we
have

$\displaystyle\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}\frac{w_{kh}(s,a)}{n_{k}(s,a)}}=$
$\displaystyle\sqrt{\sum_{k=1}^{K}\sum_{(s,a)\in\mathcal{L}_{k}}\frac{w_{k}(s,a)}{n_{k}(s,a)}}$
$\displaystyle=$
$\displaystyle\sqrt{\sum_{k=1}^{K}\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\frac{w_{k}(s,a)}{n_{k}(s,a)}\cdot\mathbbm{1}\left\\{(s,a)\in\mathcal{L}_{k}\right\\}}$
$\displaystyle\overset{\textup{(a)}}{\leq}$ $\displaystyle
2\sqrt{\sum_{k=1}^{K}\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\frac{w_{k}(s,a)}{\sum_{k^{\prime}=1}^{k}w_{k^{\prime}}(s,a)}\cdot\mathbbm{1}\left\\{(s,a)\in\mathcal{L}_{k}\right\\}}$
$\displaystyle=$ $\displaystyle
2\sqrt{\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\sum_{k=1}^{K}\frac{w_{k}(s,a)}{\sum_{k^{\prime}=1}^{k}w_{k^{\prime}}(s,a)}\cdot\mathbbm{1}\left\\{(s,a)\in\mathcal{L}_{k}\right\\}}$

where (a) is due to Lemma 6.

According to the definition of $\mathcal{L}_{k}$ (Eq. (10)), for any
$(s,a)\in\mathcal{S}\times\mathcal{A}$, once $(s,a)$ satisfies
$(s,a)\in\mathcal{L}_{k}$ in some episode $k$, it will always satisfy
$(s,a)\in\mathcal{L}_{k^{\prime}}$ for all $k^{\prime}\geq k$. For any
$(s,a)\in\mathcal{S}\times\mathcal{A}$, let $k_{0}(s,a)$ denote the first
episode $k$ where $(s,a)\in\mathcal{L}_{k}$.

Then, for any $k>0$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$, if
$(s,a)\in\mathcal{L}_{k}$, we have

$\displaystyle\sum_{k^{\prime}=1}^{k}w_{k^{\prime}}(s,a)=$
$\displaystyle\sum_{k^{\prime}=1}^{k_{0}(s,a)-1}w_{k^{\prime}}(s,a)+\sum_{k^{\prime}=k_{0}(s,a)}^{k}w_{k^{\prime}}(s,a)$
$\displaystyle\overset{\textup{(a)}}{\geq}$ $\displaystyle
H+\sum_{k^{\prime}=k_{0}(s,a)}^{k}w_{k^{\prime}}(s,a),$

where (a) uses the fact that $(s,a)\in\mathcal{L}_{k_{0}(s,a)}$ and the
definition of $\mathcal{L}_{k}$ (Eq. (10)).

Thus, we have

$\displaystyle\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}\frac{w_{kh}(s,a)}{n_{k}(s,a)}}\leq$
$\displaystyle
2\sqrt{\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\sum_{k=k_{0}(s,a)}^{K}\frac{w_{k}(s,a)}{H+\sum_{k^{\prime}=k_{0}(s,a)}^{k}w_{k^{\prime}}(s,a)}}.$

Let $a_{1}:=w_{k_{0}(s,a)}(s,a)$, $a_{2}:=w_{k_{0}(s,a)+1}(s,a)$, $\dots$,
$a_{K-k_{0}(s,a)+1}:=w_{K}(s,a)$. Define function $F(x)=\sum_{i=1}^{\lfloor
x\rfloor}a_{i}+a_{\lceil x\rceil}(x-\lfloor x\rfloor)$, where $0\leq x\leq
K-k_{0}(s,a)+1$. If $x$ is an integer, we have $F(x)=\sum_{i=1}^{x}a_{i}$, and
otherwise, $F(x)$ interpolates between the function values for integers $x$.
The derivative of $F(s)$ is $f(x)=a_{\lceil x\rceil}$.

Hence, we have

$\displaystyle\sum_{k=k_{0}(s,a)}^{K}\frac{w_{k}(s,a)}{H+\sum_{k^{\prime}=k_{0}(s,a)}^{k}w_{k^{\prime}}(s,a)}=$
$\displaystyle\sum_{k=1}^{K-k_{0}(s,a)+1}\frac{f(k)}{H+F(k)}$ $\displaystyle=$
$\displaystyle\int_{0}^{K-k_{0}(s,a)+1}\frac{f(\lceil x\rceil)}{H+F(\lceil
x\rceil)}dx$ $\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\int_{0}^{K-k_{0}(s,a)+1}\frac{f(x)}{H+F(x)}dx$ $\displaystyle=$
$\displaystyle\log\left(H+F(K-k_{0}(s,a)+1)\right)-\log\left(H+F(0)\right)$
$\displaystyle\overset{\textup{(b)}}{\leq}$ $\displaystyle\log\left(KH\right)$
$\displaystyle\leq$
$\displaystyle\log\left(\frac{KHSA}{\delta^{\prime}}\right),$

where (a) uses the fact that for any $0\leq x\leq K-k_{0}(s,a)+1$,
$f(x)=f(\lceil x\rceil)$ and $F(x)\leq F(\lceil x\rceil)$, and (b) is due to
that $k_{0}(s,a)\geq 2$ by the definitions of $\mathcal{L}_{k}$ (Eq. (10)) and
$k_{0}(s,a)$.

Therefore, we have

$\displaystyle\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}\frac{w_{kh}(s,a)}{n_{k}(s,a)}}\leq$
$\displaystyle
2\sqrt{\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\log\left(\frac{KHSA}{\delta^{\prime}}\right)}$
$\displaystyle\leq$ $\displaystyle
2\sqrt{SA\log\left(\frac{KHSA}{\delta^{\prime}}\right)}$

∎

Recall that for any
$(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}$,
$p(s^{\prime}|s,a)$ is the transition probability from $(s,a)$ to
$s^{\prime}$. For any risk level $\alpha\in(0,1]$, function
$V:\mathcal{S}\mapsto\mathbb{R}$ and
$(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}$,
$\beta^{\alpha,V}(s^{\prime}|s,a)$ is the conditional probability of
transitioning to $s^{\prime}$ from $(s,a)$, conditioning on transitioning to
the worst $\alpha$-portion successor states $s^{\prime}$ (i.e., with the
lowest $\alpha$-portion values $V(s^{\prime})$), and it holds that
$\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(s^{\prime}|s,a)}(V(s^{\prime}))=\sum_{s^{\prime}\in\mathcal{S}}\beta^{\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime})$.

For any $k>0$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,
$w_{kh}(s,a)$ is the probability of visiting $(s,a)$ at step $h$ of episode
$k$ (under transition probability $p(\cdot|\cdot,\cdot)$), and it holds that
$w_{kh}(s,a)\in[0,1]$ and
$\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}w_{kh}(s,a)=1$. For any risk level
$\alpha\in(0,1]$, $k>0$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,
$w_{kh}^{CVaR,\alpha,V^{\pi^{k}}}(s,a)$ is the conditional probability of
visiting $(s,a)$ at step $h$ of episode $k$, conditioning on transitioning to
the worst $\alpha$-portion successor states $s^{\prime}$ (i.e., with the
lowest $\alpha$-portion values $V_{h^{\prime}+1}^{\pi^{k}}(s^{\prime})$) at
each step $h^{\prime}=1,\dots,h-1$. Here $\pi^{k}$ is the policy taken in
episode $k$, and $V_{h}^{\pi^{k}}(\cdot):\mathcal{S}\mapsto\mathbb{R}$ is the
value function at step $h$ for policy $\pi^{k}$. Intuitively,
$w_{kh}^{CVaR,\alpha,V^{\pi^{k}}}(s,a)$ is the probability of visiting $(s,a)$
at step $h$ of episode $k$ under conditional transition probability
$\beta^{\alpha,V_{h^{\prime}+1}^{\pi^{k}}}(\cdot|\cdot,\cdot)$ for each step
$h^{\prime}=1,\dots,h-1$. It holds that for any risk level $\alpha\in(0,1]$,
$k>0$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,
$w_{kh}^{CVaR,\alpha,V^{\pi^{k}}}(s,a)\in[0,1]$ and
$\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}w_{kh}^{CVaR,\alpha,V^{\pi^{k}}}(s,a)=1$.

######  Lemma 8.

For any risk level $\alpha\in(0,1]$, $k>0$, $h\in[H]$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$, if $w_{kh}(s,a)=0$, then
$w_{kh}^{CVaR,\alpha,V^{\pi^{k}}}(s,a)=0$.

###### Proof of Lemma 8.

If $w_{kh}(s,a)=0$, then the algorithm has zero probability to visit $(s,a)$
at step $h$ of episode $k$, which means that $(s,a)$ is unreachable under
transition probability $p(\cdot|\cdot,\cdot)$.

Note that for each step $h^{\prime}=1,\dots,h-1$, the conditional transition
probability $\beta^{\alpha,V_{h^{\prime}+1}^{\pi^{k}}}(s^{\prime}|s,a)$ just
renormalizes the transition probability and assigns more weights to the worst
$\alpha$-portion successor states $s^{\prime}$ (i.e., with the lowest
$\alpha$-portion values $V_{h^{\prime}+1}^{\pi^{k}}(s^{\prime})$), but will
not make an unreachable successor state reachable. Thus, $(s,a)$ is also
unreachable under conditional transition probability
$\beta^{\alpha,V_{h^{\prime}+1}^{\pi^{k}}}(\cdot|\cdot,\cdot)$ for each step
$h^{\prime}=1,\dots,h-1$, and therefore
$w_{kh}^{CVaR,\alpha,V^{\pi^{k}}}(s,a)=0$. ∎

######  Lemma 9.

For any functions $V_{1},\dots,V_{H}:\mathcal{S}\mapsto\mathbb{R}$, $k>0$,
$h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$ such that
$w_{kh}(s,a)>0$,

$\displaystyle\frac{w^{\textup{CVaR},\alpha,V}_{kh}(s,a)}{w_{kh}(s,a)}\leq$
$\displaystyle\min\left\\{\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a)},\
\frac{1}{\alpha^{h-1}}\right\\},$

where $w^{\textup{CVaR},\alpha,V}_{kh}(s,a)$ denotes the conditional
probability of visiting $(s,a)$ at step $h$ of episode $k$, conditioning on
transitioning to the worst $\alpha$-portion successor states $s^{\prime}$
(i.e., with the lowest $\alpha$-portion values $V_{h^{\prime}+1}(s^{\prime})$)
at each step $h^{\prime}=1,\dots,h-1$.

###### Proof of Lemma 9.

Since $w^{\textup{CVaR},\alpha,V}_{kh}(s,a)$ is the conditional probability of
visiting $(s,a)$, we have $w^{\textup{CVaR},\alpha,V}_{kh}(s,a)\in[0,1]$.
Since $w_{kh}(s,a)$ is the probability of visiting $(s,a)$ at step $h$ under
policy $\pi^{k}$ and $\min_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a)$ is the minimum probability of
visiting any reachable $(s,a)$ at any step $h$ over all policies $\pi$, we
have

$\displaystyle w_{kh}(s,a)\geq\min\limits_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a).$

Hence, we have

$\displaystyle\frac{w^{\textup{CVaR},\alpha,V}_{kh}(s,a)}{w_{kh}(s,a)}\leq$
$\displaystyle\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a)}.$ (11)

Let $s_{1}$ be the initial state. Since $w_{kh}(s,a)$ and
$w^{\textup{CVaR},\alpha,V}_{kh}(s,a)$ are the probabilities of visiting
$(s,a)$ at step $h$ with policy $\pi^{k}$ under transition probability
$p(\cdot|\cdot,\cdot)$ and conditional transition probability
$\beta^{\alpha,V_{h^{\prime}+1}}(\cdot|\cdot,\cdot)$ for each step
$h^{\prime}=1,\dots,h-1$, respectively, we have that

$\displaystyle
w_{kh}(s,a)=\sum_{(s_{2},\dots,s_{h-1})\in\mathcal{S}^{h-2}}\prod_{h^{\prime}=1}^{h-1}p(s_{h^{\prime}+1}|s_{h^{\prime}},a_{h^{\prime}})$

and

$\displaystyle w^{\textup{CVaR},\alpha,V}_{kh}(s,a)=$
$\displaystyle\sum_{(s_{2},\dots,s_{h-1})\in\mathcal{S}^{h-2}}\prod_{h^{\prime}=1}^{h-1}\beta^{\alpha,V_{h^{\prime}+1}}(s_{h^{\prime}+1}|s_{h^{\prime}},a_{h^{\prime}}),$

where $s_{1}$ is the initial state, $s_{h}:=s$, and
$a_{h^{\prime}}:=\pi^{k}(s_{h^{\prime}})$ for $h^{\prime}=1,\dots,h-1$.

Recall that for any risk level $\alpha\in(0,1]$, function
$V:\mathcal{S}\mapsto\mathbb{R}$ and
$(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}$,
$\mu^{\alpha,V}(s^{\prime}|s,a)$ denotes how large the transition probability
of successor state $s^{\prime}$ belongs to the worst $\alpha$-portion
successor states (i.e., with the lowest $\alpha$-portion values $V(\cdot)$),
which satisfies that
$\frac{\mu^{\alpha,V}(s^{\prime}|s,a)}{\alpha}=\beta^{\alpha,V}(s^{\prime}|s,a)$
and $0\leq\mu^{\alpha,V}(s^{\prime}|s,a)\leq p(s^{\prime}|s,a)$.

Thus, we have

$\displaystyle w^{\textup{CVaR},\alpha,V}_{kh}(s,a)=$
$\displaystyle\sum_{(s_{2},\dots,s_{h-1})\in\mathcal{S}^{h-2}}\prod_{h^{\prime}=1}^{h-1}\frac{\mu^{\alpha,V_{h^{\prime}+1}}(s_{h^{\prime}+1}|s_{h^{\prime}},a_{h^{\prime}})}{\alpha}$
$\displaystyle\leq$
$\displaystyle\sum_{(s_{2},\dots,s_{h-1})\in\mathcal{S}^{h-2}}\prod_{h^{\prime}=1}^{h-1}\frac{p(s_{h^{\prime}+1}|s_{h^{\prime}},a_{h^{\prime}})}{\alpha}$
$\displaystyle=$
$\displaystyle\frac{1}{\alpha^{h-1}}\sum_{(s_{2},\dots,s_{h-1})\in\mathcal{S}^{h-2}}\prod_{h^{\prime}=1}^{h-1}p(s_{h^{\prime}+1}|s_{h^{\prime}},a_{h^{\prime}})$
$\displaystyle=$ $\displaystyle\frac{1}{\alpha^{h-1}}\cdot w_{kh}(s,a)$

Therefore,

$\displaystyle\frac{w^{\textup{CVaR},\alpha,V}_{kh}(s,a)}{w_{kh}(s,a)}\leq\frac{1}{\alpha^{h-1}}.$
(12)

Combining Eqs. (11) and (12), we obtain this lemma. ∎

######  Lemma 10 (Insufficient Visitation).

It holds that

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\notin\mathcal{L}_{k}}w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)\leq$
$\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\\}\cdot$
$\displaystyle\left(4SAH\log\left(\frac{HSA}{\delta^{\prime}}\right)+5SAH\right).$

###### Proof of Lemma 10.

According to the definition of $\mathcal{L}_{k}$ (Eq. (10)), for any
$(s,a)\in\mathcal{S}\times\mathcal{A}$, once $(s,a)$ satisfies
$(s,a)\in\mathcal{L}_{k}$ in some episode $k$, it will always satisfy
$(s,a)\in\mathcal{L}_{k^{\prime}}$ for all $k^{\prime}\geq k$. For any
$(s,a)\in\mathcal{S}\times\mathcal{A}$, let $\tilde{k}(s,a)$ denote the last
episode $k$ where $(s,a)\notin\mathcal{L}_{k}$. Then, we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\notin\mathcal{L}_{k}}w_{kh}(s,a)=$
$\displaystyle\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\sum_{k=1}^{K}\sum_{h=1}^{H}w_{kh}(s,a)\cdot\mathbbm{1}\left\\{(s,a)\notin\mathcal{L}_{k}\right\\}$
$\displaystyle=$
$\displaystyle\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\sum_{k=1}^{\tilde{k}(s,a)}\sum_{h=1}^{H}w_{kh}(s,a)$
$\displaystyle=$
$\displaystyle\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\left(\sum_{k=1}^{\tilde{k}(s,a)-1}\sum_{h=1}^{H}w_{kh}(s,a)+\sum_{h=1}^{H}w_{\tilde{k}(s,a),h}(s,a)\right)$
$\displaystyle\overset{\textup{(a)}}{<}$
$\displaystyle\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\left(4H\log\left(\frac{HSA}{\delta^{\prime}}\right)+4H+H\right)$
$\displaystyle\leq$ $\displaystyle
4SAH\log\left(\frac{HSA}{\delta^{\prime}}\right)+5SAH,$

where (a) is due to that $(s,a)\notin\mathcal{L}_{\tilde{k}(s,a)}$, and for
any $k>0$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,
$w_{kh}(s,a)\in[0,1]$.

For any policy $\pi$, $h\in[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$,
let $w_{\pi,h}(s,a)$ and $w_{\pi,h}(s)$ denote the probabilities of visiting
$(s,a)$ and $s$ at step $h$ under policy $\pi$, respectively. Then, we have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\notin\mathcal{L}_{k}}w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)$
$\displaystyle\overset{\textup{(a)}}{=}$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\notin\mathcal{L}_{k}}\frac{w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)}{w_{kh}(s,a)}\cdot
w_{kh}(s,a)\cdot\mathbbm{1}\left\\{w_{kh}(s,a)\neq 0\right\\}$
$\displaystyle\overset{\textup{(b)}}{\leq}$
$\displaystyle\min\left\\{\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a)},\
\frac{1}{\alpha^{H-1}}\right\\}\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\notin\mathcal{L}_{k}}w_{kh}(s,a)$
$\displaystyle\overset{\textup{(c)}}{\leq}$
$\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\log\left(\frac{HSA}{\delta^{\prime}}\right)+5SAH\right),$

Here (a) is due to Lemma 8. (b) comes from Lemma 9. (c) uses the fact that for
any deterministic policy $\pi$, $h\in[H]$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$, we have either
$w_{\pi,h}(s,a)=w_{\pi,h}(s)$ or $w_{\pi,h}(s,a)=0$, and thus
$\min_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a)=\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)$. ∎

Figure 5: Illustrating example for Lemma 11. For each
$s^{\prime}\in\\{s_{1},s_{2},s_{3}\\}$, the height of the bar denotes the
value $V(s^{\prime})$ or $\bar{V}(s^{\prime})$, and the width of the bar
denotes the transition probability $p(s^{\prime}|s,a)$ (fixed). The colored
part of the bars denotes the worst $\alpha$-portion successor states (i.e.,
with the lowest $\alpha$-portion values $V(s^{\prime})$ or
$\bar{V}(s^{\prime})$). In this example, $\alpha=0.5$.

Recall that for any risk level $\alpha\in(0,1]$, function
$V:\mathcal{S}\mapsto\mathbb{R}$ and
$(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}$,
$\beta^{\alpha,V}(s^{\prime}|s,a)$ is the conditional probability of
transitioning to $s^{\prime}$ from $(s,a)$, conditioning on transitioning to
the worst $\alpha$-portion successor states $s^{\prime}$ (i.e., with the
lowest $\alpha$-portion values $V(s^{\prime})$), and it holds that
$\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(s^{\prime}|s,a)}(V(s^{\prime}))=\sum_{s^{\prime}\in\mathcal{S}}\beta^{\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime})$.

######  Lemma 11 (CVaR Gap due to Value Function Shift).

For any $(s,a)\in\mathcal{S}\times\mathcal{A}$, distribution
$p(\cdot|s,a)\in\triangle_{\mathcal{S}}$, and functions
$V,\bar{V}:\mathcal{S}\mapsto[0,H]$ such that $\bar{V}(s^{\prime})\geq
V(s^{\prime})$ for any $s^{\prime}\in\mathcal{S}$,

$\displaystyle\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(\bar{V}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V(s^{\prime}))\leq\beta^{\alpha,V}(\cdot|s,a)^{\top}\left(\bar{V}-V\right).$

###### Proof of Lemma 11.

Recall that for any risk level $\alpha\in(0,1]$, function
$V:\mathcal{S}\mapsto\mathbb{R}$ and
$(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}$,
$\beta^{\alpha,V}(s^{\prime}|s,a)$ is the conditional transition probability
from $(s,a)$ to $s^{\prime}$, conditioning on transitioning to the worst
$\alpha$-portion successor states $s^{\prime}$ (i.e., with the lowest
$\alpha$-portion values $V(s^{\prime})$), and $\mu^{\alpha,V}(s^{\prime}|s,a)$
denotes how large the transition probability of successor state $s^{\prime}$
belongs to the worst $\alpha$-portion, which satisfies that
$\frac{\mu^{\alpha,V}(s^{\prime}|s,a)}{\alpha}=\beta^{\alpha,V}(s^{\prime}|s,a)$
and $\sum_{s^{\prime}\in\mathcal{S}}\mu^{\alpha,V}(s^{\prime}|s,a)=\alpha$.
Then, for any risk level $\alpha\in(0,1]$, function
$V:\mathcal{S}\mapsto\mathbb{R}$ and
$(s^{\prime},s,a)\in\mathcal{S}\times\mathcal{S}\times\mathcal{A}$,

$\displaystyle\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V(s^{\prime}))=$
$\displaystyle\frac{\sum_{s^{\prime}\in\mathcal{S}}\mu^{\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime})}{\alpha}=\sum_{s^{\prime}\in\mathcal{S}}\beta^{\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime}),$

As shown in Figure 5, we sort all successor states $s^{\prime}\in\mathcal{S}$
by their values $V(s^{\prime})$ in ascending order (from left to right). Fix
the transition probability $p(\cdot|s,a)$ and the value function shifts from
$V(\cdot)$ to $\bar{V}(\cdot)$. Then, below we divide all successor states
$s^{\prime}\in\mathcal{S}$ into three subsets, i.e., $\mathcal{S}_{up}$,
$\mathcal{S}_{down}$ and $\mathcal{S}_{unch}$, according to how
$\mu^{\alpha,V}(s^{\prime}|s,a)$ changes to
$\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)$ as $V(s^{\prime})$ shifts to
$\bar{V}(s^{\prime})$.

  * •

For any $s^{\prime}\in\mathcal{S}_{up}$,
$\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)<\mu^{\alpha,V}(s^{\prime}|s,a)$, the
rank of $s^{\prime}$ goes up, and the position of $s^{\prime}$ moves to the
right (here “rank” means to rank all successor states
$s^{\prime}\in\mathcal{S}$ by their values $V(s^{\prime})$ or
$\bar{V}(s^{\prime})$ from highest to lowest).

  * •

For any $s^{\prime}\in\mathcal{S}_{down}$,
$\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)>\mu^{\alpha,V}(s^{\prime}|s,a)$, the
rank of $s^{\prime}$ goes down, and the position of $s^{\prime}$ moves to the
left.

  * •

For any $s^{\prime}\in\mathcal{S}_{unch}$,
$\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)=\mu^{\alpha,V}(s^{\prime}|s,a)$, the
rank and position of $s^{\prime}$ keep unchanged.

Then, it holds that

$\displaystyle\sum_{s^{\prime}\in\mathcal{S}_{up}}\left(\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right)+\sum_{s^{\prime}\in\mathcal{S}_{down}}\left(\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right)=0.$
(13)

Next, we have

$\displaystyle\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(\bar{V}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s,a)}(V(s^{\prime}))$ $\displaystyle=$
$\displaystyle\frac{1}{\alpha}\cdot\Bigg{(}\sum_{s^{\prime}\in\mathcal{S}_{up}}\left(\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)\cdot\bar{V}(s^{\prime})-\mu^{\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime})\right)$
$\displaystyle+\sum_{s^{\prime}\in\mathcal{S}_{down}}\left(\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)\cdot\bar{V}(s^{\prime})-\mu^{\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime})\right)$
$\displaystyle+\sum_{s^{\prime}\in\mathcal{S}_{unch}}\left(\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)\cdot\bar{V}(s^{\prime})-\mu^{\alpha,V}(s^{\prime}|s,a)\cdot
V(s^{\prime})\right)\Bigg{)}$ $\displaystyle=$
$\displaystyle\frac{1}{\alpha}\cdot\Bigg{(}\sum_{s^{\prime}\in\mathcal{S}_{up}}\bigg{(}\mu^{\alpha,V}(s^{\prime}|s,a)\cdot\left(\bar{V}(s^{\prime})-V(s^{\prime})\right)\quad+\left(\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right)\cdot\bar{V}(s^{\prime})\bigg{)}$
$\displaystyle+\sum_{s^{\prime}\in\mathcal{S}_{down}}\bigg{(}\mu^{\alpha,V}(s^{\prime}|s,a)\cdot\left(\bar{V}(s^{\prime})-V(s^{\prime})\right)\quad+\left(\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right)\cdot\bar{V}(s^{\prime})\bigg{)}$
$\displaystyle+\sum_{s^{\prime}\in\mathcal{S}_{unch}}\mu^{\alpha,V}(s^{\prime}|s,a)\cdot\left(\bar{V}(s^{\prime})-V(s^{\prime})\right)\Bigg{)}$
$\displaystyle=$
$\displaystyle\frac{1}{\alpha}\cdot\Bigg{(}\sum_{s\in\mathcal{S}}\mu^{\alpha,V}(s^{\prime}|s,a)\cdot\left(\bar{V}(s^{\prime})-V(s^{\prime})\right)-\sum_{s^{\prime}\in\mathcal{S}_{up}}\left(\mu^{\alpha,V}(s^{\prime}|s,a)-\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)\right)\cdot\bar{V}(s^{\prime})$
$\displaystyle+\sum_{s^{\prime}\in\mathcal{S}_{down}}\left(\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right)\cdot\bar{V}(s^{\prime})\Bigg{)}$
$\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\frac{1}{\alpha}\Bigg{(}\sum_{s\in\mathcal{S}}\mu^{\alpha,V}(s^{\prime}|s,a)\cdot\left(\bar{V}(s^{\prime})-V(s^{\prime})\right)-\min_{s^{\prime}\in\mathcal{S}_{up}}\bar{V}(s^{\prime})\cdot\sum_{s^{\prime}\in\mathcal{S}_{up}}\left(\mu^{\alpha,V}(s^{\prime}|s,a)-\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)\right)$
$\displaystyle+\min_{s^{\prime}\in\mathcal{S}_{up}}\bar{V}(s^{\prime})\cdot\sum_{s^{\prime}\in\mathcal{S}_{down}}\left(\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)-\mu^{\alpha,V}(s^{\prime}|s,a)\right)\Bigg{)}$
$\displaystyle\overset{\textup{(b)}}{=}$
$\displaystyle\frac{1}{\alpha}\cdot\sum_{s\in\mathcal{S}}\mu^{\alpha,V}(s^{\prime}|s,a)\cdot\left(\bar{V}(s^{\prime})-V(s^{\prime})\right)$
$\displaystyle=$
$\displaystyle\beta^{\alpha,V}(\cdot|s,a)^{\top}\left(\bar{V}-V\right)$

Here (a) is due to that for any $s^{\prime}\in\mathcal{S}_{up}$,
$\mu^{\alpha,\bar{V}}(s^{\prime}|s,a)<\mu^{\alpha,V}(s^{\prime}|s,a)$, and for
any $s\in\mathcal{S}_{up}$, $s^{\prime}\in\mathcal{S}_{down}$,
$\bar{V}(s)\geq\bar{V}(s^{\prime})$. (b) comes from Eq. (13).

∎

####  D.1.3 Proof of Theorem 1

###### Proof of Theorem 1.

Suppose that event $\mathcal{E}$ holds. Then, for any $k\in[K]$,

$\displaystyle V^{*}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})$
$\displaystyle\overset{\textup{(a)}}{\leq}$
$\displaystyle\bar{V}^{k}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})$
$\displaystyle=$
$\displaystyle\min\left\\{r(s^{k}_{1},a^{k}_{1})+\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s^{k}_{1},a^{k}_{1})}(\bar{V}^{k}_{2}(s^{\prime}))+\frac{H}{\alpha}\sqrt{\frac{L}{n_{k}(s^{k}_{1},a^{k}_{1})}},\
H\right\\}$
$\displaystyle-\left(r(s^{k}_{1},a^{k}_{1})+\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s^{k}_{1},a^{k}_{1})}(V^{\pi^{k}}_{2}(s^{\prime}))\right)$
$\displaystyle\leq$ $\displaystyle
r(s^{k}_{1},a^{k}_{1})+\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s^{k}_{1},a^{k}_{1})}(\bar{V}^{k}_{2}(s^{\prime}))+\min\left\\{\frac{H}{\alpha}\sqrt{\frac{L}{n_{k}(s^{k}_{1},a^{k}_{1})}},\
H\right\\}$
$\displaystyle-\left(r(s^{k}_{1},a^{k}_{1})+\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s^{k}_{1},a^{k}_{1})}(V^{\pi^{k}}_{2}(s^{\prime}))\right)$
$\displaystyle=$
$\displaystyle\min\left\\{\frac{H}{\alpha}\sqrt{\frac{L}{n_{k}(s^{k}_{1},a^{k}_{1})}},\
H\right\\}+\textup{CVaR}^{\alpha}_{s^{\prime}\sim\hat{p}^{k}(\cdot|s^{k}_{1},a^{k}_{1})}(\bar{V}^{k}_{2}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s^{k}_{1},a^{k}_{1})}(\bar{V}^{k}_{2}(s^{\prime}))$
$\displaystyle+\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s^{k}_{1},a^{k}_{1})}(\bar{V}^{k}_{2}(s^{\prime}))-\textup{CVaR}^{\alpha}_{s^{\prime}\sim
p(\cdot|s^{k}_{1},a^{k}_{1})}(V^{\pi^{k}}_{2}(s^{\prime}))$
$\displaystyle\overset{\textup{(b)}}{\leq}$
$\displaystyle\min\left\\{\frac{H}{\alpha}\sqrt{\frac{L}{n_{k}(s^{k}_{1},a^{k}_{1})}},\
H\right\\}\\!+\\!\min\left\\{\frac{4H}{\alpha}\sqrt{\frac{SL}{n_{k}(s^{k}_{1},a^{k}_{1})}},\
H\right\\}\\!+\\!\beta^{\alpha,V^{\pi^{k}}_{2}}(\cdot|s^{k}_{1},a^{k}_{1})^{\top}(\bar{V}^{k}_{2}-V^{\pi^{k}}_{2})$
$\displaystyle\overset{\textup{(c)}}{\leq}$
$\displaystyle\min\left\\{\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha\sqrt{n_{k}(s^{k}_{1},a^{k}_{1})}},\
2H\right\\}+\sum_{s_{2}\in\mathcal{S}}\beta^{\alpha,V^{\pi^{k}}_{2}}(s_{2}|s^{k}_{1},a^{k}_{1})\cdot(\bar{V}^{k}_{2}(s_{2})-V^{\pi^{k}}_{2}(s_{2}))$
$\displaystyle\overset{\textup{(d)}}{\leq}$
$\displaystyle\min\left\\{\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha\sqrt{n_{k}(s^{k}_{1},a^{k}_{1})}},\
2H\right\\}+\sum_{s_{2}\in\mathcal{S}}\beta^{\alpha,V^{\pi^{k}}_{2}}(s_{2}|s^{k}_{1},a^{k}_{1})\cdot$
$\displaystyle\left(\min\left\\{\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha\sqrt{n_{k}(s_{2},a_{2})}},\
2H\right\\}+\sum_{s_{3}\in\mathcal{S}}\beta^{\alpha,V^{\pi^{k}}_{3}}(s_{3}|s_{2},a_{2})\cdot(\bar{V}^{k}_{3}(s_{3})-V^{\pi^{k}}_{3}(s_{3}))\right)$
$\displaystyle\overset{\textup{(e)}}{\leq}$
$\displaystyle\min\left\\{\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha\sqrt{n_{k}(s^{k}_{1},a^{k}_{1})}},\
2H\right\\}+\sum_{s_{2}\in\mathcal{S}}\beta^{\alpha,V^{\pi^{k}}_{2}}(s_{2}|s^{k}_{1},a^{k}_{1})\cdot$
$\displaystyle\Bigg{(}\min\left\\{\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha\sqrt{n_{k}(s_{2},a_{2})}},\
2H\right\\}+\sum_{s_{3}\in\mathcal{S}}\beta^{\alpha,V^{\pi^{k}}_{3}}(s_{3}|s_{2},a_{2})\cdot$
$\displaystyle\quad\left(\dots\sum_{s_{H}\in\mathcal{S}}\beta^{\alpha,V^{\pi^{k}}_{H}}(s_{H}|s_{H-1},a_{H-1})\cdot\left(\min\left\\{\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha\sqrt{n_{k}(s_{H},a_{H})}},\
2H\right\\}\right)\right)\Bigg{)}$ $\displaystyle\overset{\textup{(f)}}{=}$
$\displaystyle\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}w_{kh}^{CVaR,\alpha,V^{\pi^{k}}}(s,a)\cdot\min\left\\{\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha\sqrt{n_{k}(s,a)}},\
2H\right\\}$ $\displaystyle\leq$
$\displaystyle\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}w_{kh}^{CVaR,\alpha,V^{\pi^{k}}}(s,a)\cdot\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha\sqrt{n_{k}(s,a)}}$
$\displaystyle+\sum_{h=1}^{H}\sum_{(s,a)\notin\mathcal{L}_{k}}w_{kh}^{CVaR,\alpha,V^{\pi^{k}}}(s,a)\cdot
2H$ (14)

Here $a_{h}:=\pi^{k}(s_{h})$ for $h=2,\dots,H$. (a) is due to Lemma 5. (b)
uses Lemma 2 and the fact that for any $k>0$, $h\in[H]$ and $s\in\mathcal{S}$,
$\bar{V}^{k}_{h}(s)\in[0,H]$, and thus for any $k>0$, $h\in[H]$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$,
$\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
p(\cdot|s,a)}(\bar{V}^{k}_{h+1}(s^{\prime}))\leq H$, and also uses Lemma 11.
(c) comes from the property of $\min\\{\cdot,\cdot\\}$. (d) and (e) follow
from recurrently applying steps (a)-(c). (f) is due to that
$w_{kh}^{CVaR,\alpha,V^{\pi^{k}}}(s,a)$ is defined as the probability of
visiting $(s,a)$ at step $h$ of episode $k$ under the conditional transition
probability $\beta^{\alpha,V_{h^{\prime}+1}^{\pi^{k}}}(\cdot|\cdot,\cdot)$ for
each step $h^{\prime}=1,\dots,h-1$.

Since the second term in Eq. (14) can be bounded by Lemma 10, below we analyze
the first term.

Recall that for any policy $\pi$, $h\in[H]$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$, $w_{\pi,h}(s,a)$ and $w_{\pi,h}(s)$
denote the probabilities of visiting $(s,a)$ and $s$ at step $h$ under policy
$\pi$, respectively. Summing the first term in Eq. (14) over $k\in[K]$, we
have

$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha\sqrt{n_{k}(s,a)}}$
$\displaystyle\leq$
$\displaystyle\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}\frac{w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)}{n_{k}(s,a)}}\cdot\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)}$
$\displaystyle\overset{\textup{(a)}}{=}$
$\displaystyle\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}\frac{w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)}{n_{k}(s,a)}\cdot\mathbbm{1}\left\\{w_{kh}(s,a)\neq
0\right\\}}\cdot\sqrt{KH}$ $\displaystyle=$
$\displaystyle\frac{(H\sqrt{L}+4H\sqrt{SL})\sqrt{KH}}{\alpha}\sqrt{\sum_{k=1}^{K}\sum_{h=1}^{H}\\!\sum_{(s,a)\in\mathcal{L}_{k}}\\!\\!\\!\\!\frac{w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)}{w_{kh}(s,a)}\\!\cdot\\!\frac{w_{kh}(s,a)}{n_{k}(s,a)}\\!\cdot\\!\mathbbm{1}\left\\{w_{kh}(s,a)\neq
0\right\\}}$ $\displaystyle\overset{\textup{(b)}}{\leq}$
$\displaystyle\frac{(\\!H\sqrt{L}\\!+\\!4H\sqrt{SL})\sqrt{KH}}{\alpha}\\!\\!\\!\\!\sqrt{\\!\min\\!\bigg{\\{}\\!\\!\frac{1}{\min\limits_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a)},\frac{1}{\alpha^{H-1}}\\!\\!\bigg{\\}}\\!\sum_{k=1}^{K}\\!\sum_{h=1}^{H}\\!\sum_{(s,a)\in\mathcal{L}_{k}}\\!\\!\\!\\!\\!\\!\frac{w_{kh}(s,a)}{n_{k}(s,a)}}$
$\displaystyle\overset{\textup{(c)}}{\leq}$
$\displaystyle\frac{(H\sqrt{L}+4H\sqrt{SL})\sqrt{KH}}{\alpha}\cdot
2\sqrt{SAL}\cdot\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\\}$ $\displaystyle\leq$
$\displaystyle\frac{10HSL\sqrt{KHA}}{\alpha}\cdot\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\\}.$

Here (a) is due to Lemma 8 and the fact that for any $k>0$ and $h\in[H]$,
$\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)=1$.
(b) comes from Lemma 9. (c) uses Lemma 7 and the fact that for any
deterministic policy $\pi$, $h\in[H]$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$, we have either
$w_{\pi,h}(s,a)=w_{\pi,h}(s)$ or $w_{\pi,h}(s,a)=0$, and thus
$\min_{\begin{subarray}{c}\pi,h,(s,a):\
w_{\pi,h}(s,a)>0\end{subarray}}w_{\pi,h}(s,a)=\min_{\begin{subarray}{c}\pi,h,s:\
w_{\pi,h}(s)>0\end{subarray}}w_{\pi,h}(s)$.

Then, summing the first and second terms in Eq. (14) over $k\in[K]$ and using
Lemma 10, we have

$\displaystyle\mathcal{R}(K)=$
$\displaystyle\sum_{k=1}^{K}\left(V^{*}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})\right)$
$\displaystyle\leq$
$\displaystyle\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\in\mathcal{L}_{k}}w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)\frac{H\sqrt{L}+4H\sqrt{SL}}{\alpha\sqrt{n_{k}(s,a)}}$
$\displaystyle+\sum_{k=1}^{K}\sum_{h=1}^{H}\sum_{(s,a)\notin\mathcal{L}_{k}}w^{\textup{CVaR},\alpha,V^{\pi^{k}}}_{kh}(s,a)\cdot
2H$ $\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{10HS\sqrt{KHA}}{\alpha}\log\left(\frac{KHSA}{\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\\}\left(8SAH^{2}\log\left(\frac{HSA}{\delta^{\prime}}\right)+10SAH^{2}\right)$

∎

When $K$ is large enough, the first term dominates the bound, and thus we
obtain Theorem 1.

###  D.2 Proof of Regret Lower Bound

Below we prove the regret lower bound (Theorem 2) for Iterated CVaR RL-RM.

###### Proof of Theorem 2.

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

Consider the instance shown in Figure 6 (the same as Figure 1 in the main
text):

The state space is
$\mathcal{S}=\\{s_{1},s_{2},\dots,s_{n},x_{1},x_{2},x_{3}\\}$, where $s_{1}$
is the initial state, and $n=S-3<S<\frac{1}{2}H$.

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. Let $\mu$ be a parameter which
satisfies that $0<\alpha<\mu<\frac{1}{3}$. For any $a\in\mathcal{A}$,
$p(s_{2}|s_{1},a)=\mu$, $p(x_{1}|s_{1},a)=1-3\mu$, $p(x_{2}|s_{1},a)=\mu$ and
$p(x_{3}|s_{1},a)=\mu$. For any $i\in\\{2,\dots,n-1\\}$ and $a\in\mathcal{A}$,
$p(s_{i+1}|s_{i},a)=\mu$ and $p(x_{1}|s_{i},a)=1-\mu$. $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$. 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$.

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

For any $a_{j}\in\mathcal{A}$, let $\mathbb{E}_{j}[\cdot]$ and
$\Pr_{j}[\cdot]$ denote the expectation and probability operators under the
instance with $a_{J}=a_{j}$. Let $\mathbb{E}_{unif}[\cdot]$ and
$\Pr_{unif}[\cdot]$ denote the expectation and probability operators under the
uniform instance where all actions $a\in\mathcal{A}$ in state $s_{n}$ have the
same transition distribution, i.e., $p(x_{2}|s_{n},a)=1-\alpha$ and
$p(x_{3}|s_{n},a)=\alpha$.

Fix an algorithm $\mathcal{A}$. Let $\pi^{k}$ denote the policy taken by
algorithm $\mathcal{A}$ in episode $k$. Let
$N_{s_{n},a_{j}}=\sum_{k=1}^{K}\mathbbm{1}\left\\{\pi^{k}(s_{n})=a_{j}\right\\}$
denote the number of episodes that the policy chooses $a_{j}$ in state
$s_{n}$. Let $V_{s_{n},a_{j}}$ denote the number of episodes that the
algorithm $\mathcal{A}$ visits $(s_{n},a_{j})$. Let $w(s_{n})$ denote the
probability of visiting $s_{n}$ in an episode (the probability of visiting
$s_{n}$ is the same for all policies). Then, it holds that
$\mathbb{E}[V_{s_{n},a_{j}}]=w(s_{n})\cdot\mathbb{E}[N_{s_{n},a_{j}}]$.

Recall that $a_{J}$ is the optimal action in state $s_{n}$. According to the
definition of the value function for Iterated CVaR RL, we have that

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

and for any policy $\pi$,

$\displaystyle V^{\pi}_{1}(s_{1})=$ $\displaystyle\frac{(\alpha-\eta)\cdot
0.2(H-n)+\eta\cdot
0.8(H-n)}{\alpha}\cdot\mathbbm{1}\left\\{\pi(s_{n})=a_{J}\right\\}$
$\displaystyle+0.2(H-n)\cdot\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{\eta\cdot
0.6(H-n)}{\alpha}\cdot\left(1-\mathbbm{1}\left\\{\pi(s_{n})=a_{j}\right\\}\right),$
(15)

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{\eta\cdot
0.6(H-n)}{\alpha}\cdot\left(K-\sum_{k=1}^{K}\mathbbm{1}\left\\{\pi(s_{n})=a_{j}\right\\}\right)$
$\displaystyle=$ $\displaystyle\frac{\eta\cdot
0.6(H-n)}{\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{\eta}{\alpha}\cdot
0.6(H-n)\left(K-\mathbb{E}_{j}[N_{s_{n},a_{j}}]\right)$ $\displaystyle=$
$\displaystyle
0.6(H-n)\cdot\frac{\eta}{\alpha}\cdot\left(K-\frac{1}{A}\sum_{j=1}^{A}\mathbb{E}_{j}[N_{s_{n},a_{j}}]\right)$
(16)

For any $j\in[A]$, using Pinsker’s inequality and $0<\alpha<\frac{1}{3}$, 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$