# Regret Bounds for Risk-sensitive Reinforcement Learning with Lipschitz
Dynamic Risk Measures

Hao Liang
School of Science and Engineering
The Chinese University of Hong Kong, Shenzhen
<EMAIL_ADDRESS>
&Zhi-quan Luo
School of Science and Engineering
The Chinese University of Hong Kong, Shenzhen
<EMAIL_ADDRESS>

###### Abstract

We study finite episodic Markov decision processes incorporating dynamic risk
measures to capture risk sensitivity. To this end, we present two model-based
algorithms applied to _Lipschitz_ dynamic risk measures, a wide range of risk
measures that subsumes spectral risk measure, optimized certainty equivalent,
distortion risk measures among others. We establish both regret upper bounds
and lower bounds. Notably, our upper bounds demonstrate optimal dependencies
on the number of actions and episodes, while reflecting the inherent trade-off
between risk sensitivity and sample complexity. Additionally, we substantiate
our theoretical results through numerical experiments.

##  1 Introduction

Standard reinforcement learning (RL) aims to identify an optimal policy that
maximizes the expected return (Sutton and Barto,, 2018). This approach is
commonly known as risk-neutral RL since it prioritizes the mean value of the
uncertain return. However, in domains characterized by high-stakes scenarios,
such as finance (Davis and Lleo,, 2008; Bielecki et al.,, 2000), medical
treatment (Ernst et al.,, 2006), and operations research (Delage and Mannor,,
2010), decision-makers exhibit risk-sensitive behavior and strive to optimize
a risk measure associated with the return.

One classical framework that addresses risk sensitivity in Markov decision
processes (MDPs) is the _static risk measure_. In this framework, the value of
a policy is defined as the static risk measure applied to the cumulative
reward across all stages. Among the commonly used static risk measures are the
entropic risk measure (ERM)Howard and Matheson, (1972); Föllmer and Knispel,
(2011) and the conditional value at risk (CVaR) Rockafellar et al., (2000),
along with several others. However, except for the ERM, the static risk
measure generally does not satisfy the Bellman equation. Consequently,
obtaining the optimal policy becomes computationally challenging, even when
the MDP model is known.

As an extension of the static risk measure, the _dynamic risk measure_ (DRM)
Ruszczyński, (2010) is constructed by recursively applying the risk measure to
the reward at each stage. This recursive formulation naturally allows for the
derivation of a dynamic programming equation and thus circumvents the
computational burden. Furthermore, DRMs have the advantage of yielding time-
consistent optimal policies, a property that is particularly justified in
financial applications Osogami, (2012). By ensuring time consistency, DRMs
provide a more robust framework for decision-making in safety-critical
applications, such as clinical treatment, where risk sensitivity at all stages
is of paramount importance Du et al., (2023).

Our work focuses on studying risk-sensitive reinforcement learning (RSRL) with
a general DRM in the tabular and episodic MDP setting, in which the agent
interacts with an unknown MDP with finite states and actions in an episodic
manner. We make the mildest assumption that the risk measure used is Lipschitz
continuous with respect to certain metric, which we refer to as the Lipschitz
DRM. The Lipschitz risk measure encompasses a wide range of classes of risk
measures in practical applications, including spectral risk measure (SRM),
distortion risk measure, and optimized certainty equivalent (OCE), among
others. Additionally, the Lipschitz DRM is also a broader class of risk
measures compared to convex and coherent measures since any finite convex risk
measure satisfies the Lipschitz property Föllmer and Knispel, (2013). As a
result, our framework encompasses various RL settings, such as risk-neutral
RL, RSRL with ERM, RSRL with dynamic CVaR, and RL with dynamic OCE 111Further
details on these RL settings can be found in Section 1.1.

The use of Lipschitz risk measures introduces additional technical challenges
that need to be addressed. One such challenge arises in the algorithmic design
phase when designing exploration bonuses for generic nonlinear risk measures.
The standard techniques commonly used in risk-neutral settings, such as
Hoeffding inequality or Bernstein-type concentration bounds, are not directly
applicable as they only deal with the concentration of mean values. To
overcome this issue, previous works, such as Du et al., (2023) and Xu et al.,
(2023), design the exploration bonus based on specific properties of the risk
measures they consider. For instance, Du et al., (2023) chooses the
exploration bonus for dynamic CVaR based on a classical concentration bound
specific to CVaR, while Xu et al., (2023) exploits the optimization
representation of OCE and uses the concavity of the utility function to
construct the bonus for OCE. We exploit the Lipschitz property of the risk
measure to relate the value difference to the supremum distance and then apply
DKW inequality to bound the deviation between one distribution and its
empirical version.

Another challenge arises in deriving a recursion of the suboptimality gap
across stages in the proof of regret upper bounds. The standard analysis in
the risk-neutral setting relies on the linearity of the mean to obtain the
recursion, which cannot be directly adapted to the risk-sensitive setting. To
tackle this challenge, we leverage the Lipschitz property to establish a
relationship between the value difference and the Wasserstein distance between
two probability distributions. Specifically, we bound the Wasserstein distance
between two probability mass functions (PMFs) with identical probability mass
but different support by the expected difference between their supports. By
incorporating the Lipschitz property, we obtain a recursion of the
suboptimality gap, where the Lipschitz constant appears as a multiplicative
factor. By addressing these challenges, we are able to design efficient
algorithms and provide regret upper bounds.

We summarize our main contributions in this paper as follows:

1. We propose two model-based algorithms for RSRL with Lipschitz DRM. These algorithms incorporate the principle of optimism in the face of uncertainty (OFU) in different ways to facilitate efficient learning. To the best of our knowledge, this is the first work that investigates RSRL using general DRM without making the simulator assumption.

2. We provide worst-case and gap-dependent regret upper bounds for the proposed algorithms. Notably, the regret bounds are optimal in terms of the number of actions ($A$), and the number of episodes ($K$). They are dependent on the product of the Lipschitz constants of the risk measures at all stages, capturing the inherent trade-off between risk sensitivity and sample complexity.

3. We establish the minimax and gap-dependent lower bounds for episodic MDPs with general DRM. These lower bounds are tight in terms of $A$, $K$, and the number of states ($S$). Moreover, they reveal a constant factor that depends on the specific risk measure employed.

###  1.1 Related Work

##### RSRL without regret bounds.

General DRM applied to MDP is presented in Ruszczyński, (2010); Shen et al.,
(2013); Chu and Zhang, (2014); Asienkiewicz and Jaśkiewicz, (2017); Bäuerle
and Glauner, (2022). However, these works typically assume that the model of
the MDP is known, whereas our paper focuses on studying regret guarantees for
RSRL in the presence of an unknown MDP. While there are studies such as Coache
and Jaimungal, (2021); Coache et al., (2022) that explore RSRL with dynamic
convex risk measures and dynamic spectral risk measures, respectively, their
work does not consider regret guarantees.

##### Regret bounds for RSRL with static risk measures.

Fei et al., (2020) provide the first regret bound for risk-sensitive tabular
MDPs using the ERM. This result is further improved upon by Fei et al.,
(2021), where they remove the exponential factor dependence on the episode
length. Fei and Xu, (2022) present the first gap-dependent regret bounds under
this framework. Liang and Luo, (2022) propose distributional reinforcement
learning algorithms for RSRL with ERM, matching the results obtained in Fei et
al., (2021). Bastani et al., (2022) consider RSRL with the objective of the
spectral risk measure, where conditional value at risk (CVaR) is a special
case. Furthermore, Wang et al., (2023) improve upon the regret bound obtained
in Bastani et al., (2022) in terms of the number of states and episode length.

##### Regret bounds for RSRL with DRMs.

Du et al., (2023) provides the first regret bound for RSRL using DRMs,
specifically focusing on dynamic conditional value at risk (CVaR). A very
recent work Xu et al., (2023) that investigates RSRL using dynamic OCE. OCE is
a class of risk measures that encompasses several well-known measures,
including ERM, CVaR, and mean-variance. They propose a value iteration
algorithm based on the idea of upper confidence bound and derive regret upper
bounds for their algorithm, as well as a minimax lower bound.

Lam et al., (2023) focuses on dynamic coherent risk measures in the context of
non-linear function approximation. They propose an algorithm that leverages
UCB-based value functions with non-linear function approximation and prove a
sub-linear regret upper bound. However, their work relies on the assumption of
a weak simulator, which allows for generating an arbitrary number of next
states from any given state. It remains unclear whether such assumptions can
be removed in the tabular setting. In contrast, our work does not rely on
specific assumptions about the risk measure estimator or concentration bounds.
Additionally, our approach considers a broader class of DRMs by focusing on
Lipschitz DRMs, which encompasses a wider range of risk measures compared to
coherent ones.

Our paper is organized as follows. We first introduce some backgrounds and
problem formulations in Section 2. We then propose our algorithms in Section
3, which is followed by our main results in Section 4. The proof sketch of our
main theorem in given in Section 5. Finally, we conclude our paper in Section
6. The numerical experiments are shown in Appendix A.

##  2 Preliminaries

##### Notations.

We write $[N]:=\\{1,2,...,N\\}$ for any positive integers $N$. We use
$\mathbb{I}\\{\cdot\\}$ to denote the indicator function. We denote by $a\vee
b:=\max\\{a,b\\}$. We use the notation $\tilde{\mathcal{O}}(\cdot)$ to
represent $\mathcal{O}(\cdot)$ with logarithmic factors omitted. For two real
numbers $a<b$, the notation $\mathscr{D}([a,b])$ refers to the space of all
probability distributions that are bounded over the interval $[a,b]$. For a
discrete set $x=\left\\{x_{1},\cdots,x_{n}\right\\}$ and a probability vector
$P=(P_{1},\cdots,P_{n})$, the notation $(x,P)$ represents the discrete
distribution where $\mathbb{P}(X=x_{i})=P_{i}$.

##### Static risk measure.

A (static) risk measure is a mapping $\rho:\mathscr{X}\rightarrow\mathbb{R}$
that assigns a real number to each random variable in the set $\mathscr{X}$,
which satisfies certain properties of the following. It quantifies the risk
associated with a random outcome.

  * •

monotonicity: $X\preceq Y\Rightarrow\rho(X)\leq\rho(Y)$,

  * •

translation-invariance: $\rho(X+c)=\rho(X)+c,\ c\in\mathbb{R}$,

  * •

super-additivity: $\rho(X+Y)\geq\rho(X)+\rho(Y)$,

  * •

positive homogeneity: $\rho(\alpha X)=\alpha\rho(X)$ for $\alpha\geq 0$

  * •

concavity: $\rho(\alpha X+(1-\alpha)Y)\geq\alpha\rho(X)+(1-\alpha)\rho(Y)$

  * •

law-invariance: $F_{X}=F_{Y}\Rightarrow\rho(X)=\rho(Y)$.

Two intrinsic properties of risk measures are monotonicity and translation-
invariance. _Coherent_ risk measures, introduced by Artzner et al., (1999),
are a widely used class of risk measures that satisfy super-additivity and
positive homogeneity in addition. Coherent risk measures capture important
concepts such as diversification and risk pooling. _Concave_ risk measures
generalize coherent risk measures by relaxing the requirements of super-
additivity and positive homogeneity to concavity. Concave risk measures are
more flexible and can capture a wider range of risk preferences.

_Lipschitz_ risk measures, on the other hand, form an even broader class of
risk measures, which encompass both coherent and concave risk measures. They
allow for more general functional forms and provide a flexible framework for
capturing risk in various settings. Lipschitz risk measures satisfy the law-
invariance property, therefore we overload notations and write
$\rho(F_{X}):=\rho(X)$ for $X\sim F_{X}$.

##### Lipschitz continuity.

For two cumulative distribution functions (CDFs) $F$ and $G$, their supremum
distance is defined as

$\left\lVert
F-G\right\rVert_{\infty}\triangleq\sup_{x\in\mathbb{R}}\left\lvert
F(x)-G(x)\right\rvert.$

The Wasserstein distance as well as the $\ell_{1}$ distance between $F$ and
$G$ is defined as

$\displaystyle\left\lVert
F-G\right\rVert_{1}\triangleq\int_{-\infty}^{\infty}\left\lvert
F(x)-G(x)\right\rvert dx.$

A risk measure $\rho$ is said to be Lipschitz continuous with respect to a
distance $\left\lVert\cdot\right\rVert_{p}$ ($p=1$ or $p=\infty$) over the set
of distributions $\mathscr{D}([a,b])$ if

$\rho(F)-\rho(G)\leq L_{p}(\rho,[a,b])\left\lVert F-G\right\rVert_{p},\forall
F,G\in\mathscr{D}([a,b]).$

Here, $L_{p}(\rho,[a,b])$ is the Lipschitz constant associated with the risk
measure $\rho$ over the interval $[a,b]$, and it represents the maximum rate
of change of the risk measure with respect to the distance metric. The
Lipschitz continuity property provides a way to quantify the sensitivity of
the risk measure to changes in the underlying distributions. A larger
Lipschitz constant indicates a greater sensitivity or variability of the risk
measure values with respect to changes in the distributions.

To gain some intuition, we present the Lipschitz constant values for several
popular risk measures over the interval $[0,M]$ in Table 1. For interested
readers, please refer to Appendix B for the formal definitions of the risk
measures and more detailed discussions about the Lipschitz constants.

Table 1: Lipschitz constants of typical risk measures Lipschitz constant | CVaR | distortion risk measure | ERM | OCE222For convenience, we only consider the OCE with concave utility function
---|---|---|---|---
$L_{1}([0,M])$ | $\frac{1}{\alpha}$ | $\max g^{\prime}(x)$ | $\exp(|\beta|M)$ | $u^{\prime}(-M)$
$L_{\infty}([0,M])$ | $\frac{M}{\alpha}$ | $M\max g^{\prime}(x)$ | $\frac{\exp(|\beta|M)-1}{|\beta|}$ | $u(-M)$

##### Episodic MDP.

An episodic MDP is defined by a tuple
$\mathcal{M}\triangleq(\mathcal{S},\mathcal{A},(P_{h})_{h\in[H]},(r_{h})_{h\in[H]},H)$,
where $\mathcal{S}$ is the finite state space with cardinality
$S\triangleq|\mathcal{S}|$, $\mathcal{A}$ the finite action space with
cardinality $A\triangleq|\mathcal{A}|$,
$P_{h}:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\rightarrow[0,1]$ the
probability transition kernel at step $h$,
$r_{h}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ the reward functions at
step $h$, and $H$ the length of one episode. The agent interacts with the
environment for $K$ episodes. At the beginning of episode $k$, an initial
state $s^{k}_{1}$ is arbitrarily selected. In step $h$, the agent takes action
$a^{k}_{h}$ based on the state $s^{k}_{h}$, according to its policy. The
policy is represented by a (deterministic) sequence of functions
$\pi=(\pi_{h})_{h\in[H]}$, where each $\pi_{h}$ maps from $\mathcal{S}$ to
$\mathcal{A}$. The agent observes the reward $r_{h}(s^{k}_{h},a^{k}_{h})$ and
transitions to the next state $s^{k}_{h+1}\sim
P_{h}(\cdot|s^{k}_{h},a^{k}_{h})$. The episode terminates at $H+1$, after
which the agent proceeds to the next episode.

##### Dynamic programming with DRM.

The dynamic risk measure is defined via a recursive application of static risk
measures $(\rho_{h})_{h\in[H-1]}$ Ruszczyński, (2010). The (risk-sensitive)
value function of a policy $\pi$ at step $h$ is defined recursively

$\displaystyle
Q^{\pi}_{h}(s_{h},a_{h})=r_{h}(s_{h},a_{h})+\rho_{h}(V^{\pi}_{h+1}(s_{h+1}))$
(1) $\displaystyle
V^{\pi}_{h}(s_{h})=Q^{\pi}_{h}(s_{h},\pi_{h}(s_{h})),V^{\pi}_{H+1}(s_{H+1})=0.$

where $\rho_{h}$ is taken over the _next-state value_
$V^{\pi}_{h+1}(s_{h+1})$, i.e.,

$V^{\pi}_{h+1}(s_{h+1})\sim\left(V^{\pi}_{h+1},P_{h}(s,a)\right)\Longrightarrow\rho_{h}(V^{\pi}_{h+1}(s_{h+1}))=\rho_{h}\left(\left(V^{\pi}_{h+1},P_{h}(s,a)\right)\right).$

We refer to the distribution of $V^{\pi}_{h+1}(s_{h+1})$ as the _(next-state)
value distribution_ $\left(V^{\pi}_{h+1},P_{h}(s,a)\right)$. For convenience,
we write $\rho(x,P)=\rho((x,P))$, thus we write
$\rho_{h}\left(V^{\pi}_{h+1},P_{h}(s,a)\right)$. By incorporating the risk
measure $\rho_{h}$ into the recursive formulation, the dynamic risk measure
framework provides a way to account for risk preferences and evaluate the
risk-sensitive value function of a policy at each time step. When the risk
measure $\rho_{h}$ specializes in the mean (i.e., taking the expectation),
Equation 1 reduces to the standard Bellman equation.

The (risk-sensitive) optimal policy is defined as the policy that maximizes
the value function, i.e., $\pi^{*}=\arg\max_{\pi}V^{\pi}_{1}$. Consequently,
the optimal value function is defined as $V^{*}_{h}(s)=V^{\pi^{*}}_{h}(s)$ and
$Q^{*}_{h}(s,a)=Q^{\pi^{*}}_{h}(s,a)$. Ruszczyński, (2010) shows that an
optimal Markovian policy exists, and the optimal value functions can be
computed recursively. The Bellman optimality equation is given by

$\displaystyle
Q^{*}_{h}(s_{h},a_{h})=r_{h}(s_{h},a_{h})+\rho_{h}(V^{*}_{h+1},P_{h}(s_{h},a_{h}))$
(2) $\displaystyle
V^{*}_{h}(s_{h})=\max_{a\in\mathcal{A}}Q^{*}_{h}(s_{h},a_{h}),V^{*}_{H+1}(s_{H+1})=0.$

The optimal policy is the greedy policy with respect to the optimal action-
value function, i.e.,
$\pi^{*}_{h}(s)=\arg\max_{a\in\mathcal{A}}Q^{*}_{h}(s,a)$.

##### Regret.

We define the regret of an algorithm alg interacting with an MDP $\mathcal{M}$
for $K$ episodes as

$\displaystyle\text{Regret}(\texttt{alg},\mathcal{M},K)$
$\displaystyle\triangleq\sum_{k=1}^{K}V^{*}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1}).$

The regret quantifies the accumulated suboptimality gap of an algorithm
compared to the optimal policy. It is a random variable due to the randomness
introduced by $\pi^{k}$. We denote the expected regret by
$\mathbb{E}[\text{Regret}(\texttt{alg},\mathcal{M},K)]$. We may omit the
notation $\boldsymbol{\pi}$ and $\mathcal{M}$ when clear from the context.

##  3 Algorithm

In this section, we present two model-based algorithms that incorporate the
OFU principle. They aim to strike a balance between exploration and
exploitation during the learning process. Both algorithms belong to the model-
based algorithm class as they maintain an empirical model of the environment
during the learning process. We make the following assumption on the DRM,
which our algorithms apply to:

######  Assumption 1.

For each $h\in[H]$, $\rho_{h}$ is Lipschitz continuous with respect to the
$\left\lVert\cdot\right\rVert_{1}$ and
$\left\lVert\cdot\right\rVert_{\infty}$, and satisfies
$\rho_{h}:\mathscr{D}([a,b])\rightarrow[a,b]$.

######  Remark 1.

The second condition in Assumption 1 is mild since it is satisfied by common
risk measures. For example, it is easy to check that CVaR and ERM satisfies
this condition.

For simplicity, we drop $\rho$ from the notations and write $L_{p,h}\triangleq
L_{p}(\rho_{h},[0,H-h])$ for $h\in[H-1]$. For two probability mass functions
(PMFs) $P$ and $Q$ with the same support, we overload notations and denote by
$\left\lVert P-Q\right\rVert_{1}:=\sum_{i}|P_{1}-Q_{i}|$ their $\ell_{1}$
distance.

###  3.1 UCBVI-DRM

UCBVI-DRM uses the bonus term to ensure optimism in the estimation of the
value function, considering the nonlinearity of the risk measure. In each step
$h$ of episode $k$, the optimistic value function is obtained by adding a
bonus term $b^{k}_{h}$ to the empirical value. The empirical value is
constructed by approximating the Bellman optimality equation (Equation 2) with
empirical model. To be more specific, the empirical model is maintained and
updated based on the visiting counts

$N^{k}_{h}(s,a):=\sum_{\tau=1}^{k-1}\mathbb{I}\left\\{(s^{\tau}_{h},a^{\tau}_{h})=(s,a)\right\\},\
N^{k}_{h}(s,a,s^{\prime}):=\sum_{\tau=1}^{k-1}\mathbb{I}\left\\{(s^{\tau}_{h},a^{\tau}_{h},s^{\tau}_{h+1})=(s,a,s^{\prime})\right\\}.$

The empirical model $\hat{P}^{k}_{h}$ for step $h$ in episode $k$ is set to be
the visiting frequency

$\hat{P}^{k}_{h}(s^{\prime}|s,a)=\frac{N^{k}_{h}(s,a,s^{\prime})}{N^{k}_{h}(s,a)\vee
1}.$

The bonus term $b^{k}_{h}$ is composed of two factors: the estimation error of
the next-state value distribution and the Lipschitz constant of the risk
measure. The estimation error can be bounded as

$\left\lVert(\hat{P}^{k}_{h},V^{*}_{h+1})-(P_{h},V^{*}_{h+1})\right\rVert_{\infty}\leq\sqrt{\frac{\iota}{2(N^{k}_{h}(\cdot,\cdot)\vee
1)}},$

where $\iota$ is a confidence level to be specified later. This error term
captures the uncertainty in the empirical model. The Lipschitz constant
$L_{\infty,h}$ of the risk measure reflects its sensitivity to changes in the
underlying distributions. Multiplying these two factors together yields the
exploration bonus term, which is added to the empirical value function
estimate. This bonus term encourages exploration in situations where the model
estimation error is large or the risk measure is sensitive. By carefully
designing the bonus term, UCBVI-DRM achieves optimism in its value function
estimates, promoting exploration while considering the nonlinearity of the
risk measure. This allows the algorithm to balance exploration and
exploitation, taking into account the uncertainty in the model and the
smoothness of the risk measure.

Algorithm 1 UCBVI-DRM

1:Input: $\left(\rho_{h}\right)_{h\in[H-1]}$, $T$ and $\delta$

2:Initialize $N^{k}_{h}(\cdot,\cdot)\leftarrow 0$,
$\hat{P}^{k}_{h}(\cdot,\cdot)\leftarrow\frac{1}{S}\textbf{1}$

3:for $k=1:K$ do

4: $V^{k}_{H}(\cdot)\leftarrow\max_{a}r_{H}(\cdot,a)$

5: for $h=H-1:1$ do

6: $b^{k}_{h}(\cdot,\cdot)\leftarrow
L_{\infty,h}\sqrt{\frac{\iota}{2(N^{k}_{h}(\cdot,\cdot)\vee 1)}}$

7: $Q^{k}_{h}(\cdot,\cdot)\leftarrow
r_{h}(\cdot,\cdot)+\rho_{h}(V^{k}_{h+1},\hat{P}^{k}_{h}(\cdot,\cdot))+b^{k}_{h}(\cdot,\cdot)$

8: $V^{k}_{h}(\cdot)\leftarrow\max_{a\in\mathcal{A}}Q^{k}_{h}(\cdot,a)$

9: end for

10: Receive $s^{k}_{1}$

11: for $h=1:H$ do

12: Take action
$a^{k}_{h}\leftarrow\arg\max_{a\in\mathcal{A}}Q^{k}_{h}(s^{k}_{h},a)$ and
transit to $s^{k}_{h+1}$

13: Update $N^{k}_{h}(\cdot,\cdot)$ and $\hat{P}^{k}_{h}(\cdot,\cdot)$

14: end for

15:end for

######  Remark 2.

Algorithm 1 provides a general framework that subsumes other algorithms such
as ICVaR-VI in Du et al., (2023) for dynamic CVaR and OCE-VI in Xu et al.,
(2023) for dynamic OCE. In particular, our bonus term matches theirs by
setting $L_{\infty,h}=(H-h)/\alpha$ for CVaR and $L_{\infty,h}=u(-(H-h))$ for
OCE. Therefore, Algorithm 1 generalizes these algorithms and provides a
unified framework for addressing different risk measures.

###  3.2 OVI-DRM

The OVI-DRM algorithm (see Algorithm 2) is a model-based algorithm which
injects the optimism in the estimated model. It operates at a high level as
follows. For each step $h$ in episode $k$, the algorithm constructs an
optimistically estimated transition model $\tilde{P}^{k}_{h}$ based on a high
probability concentration bound on the empirical transition model
$\hat{P}^{k}_{h}$. This optimistic model allows for exploration and promotes
optimism in the face of uncertainty. Using the optimistic model
$\tilde{P}^{k}_{h}$, the algorithm approximates the Bellman optimality
equation (Equation 2) to obtain optimistic value functions $Q^{k}_{h}$.

The optimistic model $\tilde{P}^{k}_{h}$ is obtained by applying a subroutine
called OM (Optimistic Model) that takes the empirical model
$\hat{P}^{k}_{h}(s,a)$, the value at the next step $V^{k}_{h+1}$, and a
confidence radius $c^{k}_{h}(s,a)$ as input. The subroutine constructs an
optimistic model within an $\ell_{1}$ norm ball around $\hat{P}^{k}_{h}(s,a)$

$\left\lVert P_{h}(s,a)-\hat{P}^{k}_{h}(s,a)\right\rVert_{1}\leq
c^{k}_{h}(s,a).$

$c^{k}_{h}$ represents the confidence radius around the empirical model within
which the true model lies with high probability. Due to the space limit, we
defer the details of the subroutine OM (Algorithm 3) in Appendix C. Note that
OM is computationally efficient with complexity $\mathcal{O}(S\log S)$.

The optimism of the model induces optimism in the value estimates

$(\tilde{P}^{k}_{h}(s,a),V^{k}_{h+1})\succeq(P_{h}(s,a),V^{k}_{h+1})\succeq(P_{h}(s,a),V^{*}_{h+1})\Longrightarrow
Q^{k}_{h}(s,a)\geq Q^{*}_{h}(s,a).$

By using an optimistically estimated model, the OVI-DRM algorithm promotes
exploration and encourages the agent to take actions that have the potential
for higher values.

Algorithm 2 OVI-DRM

1:Input: $\left(\rho_{h}\right)_{h\in[H-1]}$, $T$ and $\delta$

2:Initialize $N^{k}_{h}(\cdot,\cdot)\leftarrow 0$,
$\hat{P}^{k}_{h}(\cdot,\cdot)\leftarrow\frac{1}{S}\textbf{1}$

3:for $k=1:K$ do

4: $V^{k}_{H}(\cdot)\leftarrow\max_{a}r_{H}(\cdot,a)$

5: for $h=H-1:1$ do

6: $c^{k}_{h}(\cdot,\cdot)\leftarrow\sqrt{\frac{2S}{N^{k}_{h}(\cdot,\cdot)\vee
1}\iota}$

7:
$\tilde{P}^{k}_{h}(\cdot,\cdot)\leftarrow\texttt{OM}\left(\hat{P}^{k}_{h}(\cdot,\cdot),V^{k}_{h},c^{k}_{h}(\cdot,\cdot)\right)$

8: $Q^{k}_{h}(\cdot,\cdot)\leftarrow
r_{h}(\cdot,\cdot)+\rho_{h}(V^{k}_{h+1},\tilde{P}^{k}_{h}(\cdot,\cdot))$

9: $V^{k}_{h}(\cdot)\leftarrow\max_{a\in\mathcal{A}}Q^{k}_{h}(\cdot,a)$

10: end for

11: Receive $s^{k}_{1}$

12: for $h=1:H$ do

13: Take action
$a^{k}_{h}\leftarrow\arg\max_{a\in\mathcal{A}}Q^{k}_{h}(s^{k}_{h},a)$ and
transit to $s^{k}_{h+1}$

14: Update $N^{k}_{h}(\cdot,\cdot)$ and $\hat{P}^{k}_{h}(\cdot,\cdot)$

15: end for

16:end for

##  4 Main Results

To simplify notations, we define
$\tilde{L}_{1,t}\triangleq\prod^{t}_{i=1}L_{1,i}$ for $t\in[H]$.

###  4.1 Worst-case Regret Bounds

######  Theorem 1 (Worst-case regret upper bound).

Fix $\delta\in(0,1)$. Suppose Assumption 1 holds. Algorithm 1 and Algorithm 2
satisfies for any MDP $\mathcal{M}$

$\displaystyle\text{Regret}(K)\leq\tilde{\mathcal{O}}\left(\sum^{H-1}_{h=1}L_{\infty,h}\tilde{L}_{1,h-1}\cdot\sqrt{S^{2}AK}\right)$

with probability at least $1-\delta$, where
$\iota\triangleq\log(4SAT/\delta)$.

The proof sketch of Theorem 1 is shown in Section 5.

######  Remark 3.

In the risk-neutral setting, The Lipschitz constants take $L_{\infty,h}=H-h$
and $L_{1,h}=1$, which leads to the bound of
$\tilde{\mathcal{O}}\left(H^{2}\sqrt{S^{2}AK}\right)$.

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

For any algorithm alg, there exists an MDP $\mathcal{M}$ such that for
sufficiently large $K$

$\mathbb{E}[\text{Regret}(\texttt{alg},\mathcal{M},K)]\geq\Omega\left(c_{\rho}H\sqrt{SAT}\right),$

where $c_{\rho}$ is a constant dependent on the risk measure333For more
details, please refer to Appendix E..

The construction of proof is based on Domingues et al., (2021).

##### Comparisons and Discussions.

We compare our regret bounds with that of Xu et al., (2023) in the dynamic OCE
setting. By instantiating the Lipschitz constants of OCE with
$L_{\infty,h}=u(-H+h)$ and $L_{1,h}=u^{\prime}_{-}(-H+h)$, their bound can be
translated into
$\tilde{\mathcal{O}}\left(\sum^{H-1}_{h=1}L_{\infty,h}\sqrt{\tilde{L}_{1,h-1}S^{2}AK}\right)$.
Our bound matches their result with additional factors
$\sqrt{\tilde{L}_{1,h-1}}$. This is because they employ a change-of-measure
technique based on the concave optimization representation of OCE to bound
derive a tighter recursion of value gaps, which cannot be easily extended to
general risk measures. The Algorithm 1, however, still enjoy the same regret
bound as that in Xu et al., (2023) since our algorithm reduces to OCE-VI for
the dynamic OCE. Furthermore, numerical experiments in Appendix E shows that
Algorithm 2 empirically outperforms Algorithm 1 for dynamic CVaR problem. Our
lower bound also matches the lower bound in Xu et al., (2023), both of which
are tight in $S,A,K,H$ and depend on some constant related to the risk
measure.

In the dynamic CVaR setting, which is a special case of dyamic OCE, our upper
bound matches the bound
$\tilde{\mathcal{O}}\left(H^{2}\sqrt{S^{2}AK}/\sqrt{\alpha^{H}}\right)$ in Du
et al., (2023) up to a factor of $1/\sqrt{\alpha^{H}}$. Algorithm 1 subsumes
ICVaR-VI for the dynamic CVaR problem. In contrast to Du et al., (2023) that
provides a algorithm-dependent lower bound, we provide minimax and gap-
dependent lower bound. Furthermore, Lam et al., (2023) considers dynamic
coherent risk measures and non-linear function approximation, and their regret
bounds are derived under the assumption of a weak simulator. As a result, the
regret bounds provided in our work are not directly comparable to theirs, even
if their results are specialized to the tabular MDP setting

Theorem 1 and Theorem 2 imply that RSRL with Lipschitz DRM can achieve regret
bound that is minimax-optimal in terms of $K$ and $A$. Specifically, the gap
between the upper and lower bounds is determined by two factors: $\sqrt{S}$
and a multiplicative Lipschitz constant $\tilde{L}_{1,H}$. we provide more
technical details behind this in the proof sketch. Achieving further
improvements in these factors can be challenging, especially for general risk
measures, under the mild Lipschitz assumption.

###  4.2 Gap-dependent Regret Bounds

Fix $h\in[H]$, $(s,a)\in\mathcal{S}\times\mathcal{A}$, the _sub-optimality
gap_ of $(s,a)$ at step $h$ is defined as $\Delta_{h}(s,a)\triangleq
V^{*}_{h}(s,a)-Q^{*}_{h}(s,a)$. The _minimum sub-optimality gap_ is defined as
the minimum non-zero gap

$\Delta_{\text{min}}\triangleq\min_{h,s,a}\left\\{\Delta_{h}(s,a):\Delta_{h}(s,a)>0\right\\}.$

######  Theorem 3 (Gap-dependent regret upper bound).

Fix $\delta\in(0,1)$. With probability at least $1-\delta$, Algorithm 1 and
Algorithm 2 satisfy

$\displaystyle\text{Regret}(K)$
$\displaystyle\leq\mathcal{O}\left(\frac{S^{2}AH\left(\sum_{h=1}^{H-1}\tilde{L}_{1,h-1}L_{\infty,h}\right)^{2}}{\Delta_{\text{min}}}\log(SAT)\right).$

We follow the standard convention in the literature for the gap-dependent
lower bound. The lower bound is stated for algorithms that have sublinear
worst-case regret. Specifically, we say that an algorithm alg is
$\alpha$-uniformly good if for any MDP $\mathcal{M}$, there exists a constant
$C_{\mathcal{M}}>0$ such that $\text{Regret}(\texttt{alg},\mathcal{M},K)\leq
C_{\mathcal{M}}K^{\alpha}$. The construction of proof is based on Simchowitz
and Jamieson, (2019).

######  Theorem 4 (Gap-dependent regret lower bound).

There exists an MDP $\mathcal{M}$ such that any $\alpha$-uniformly good
algorithm alg satisfies

$\displaystyle\lim_{K\rightarrow\infty}\frac{\text{Regret}(\texttt{alg},\mathcal{M},K)}{\log
K}=\Omega\left((1-\alpha)\sum_{(s,a):\Delta_{1}(s,a)>0}\frac{(c_{\rho}H)^{2}}{\Delta_{1}(s,a)}\right)$

To our knowledge, Theorem 3 provides the first result showing that RSRL with
DRMs can achieve $\log T$-type regret. The lower bound shows that for
sufficiently large $K$, the logarithmic dependence on $K$ is unavoidable.
Notably, it implies that our algorithms have a tight dependency on $A$ and
$K$. Furthermore, the presence of a constant factor in both the upper and
lower bounds suggests that the specific choice of risk measure can
significantly impact their performance.

##  5 Proof Sketch of Theorem 1

For simplicity, we only provide the proof sketch for UCBVI-DRM. The proof
structure builds upon the framework established in Azar et al., (2017), but we
introduce new techniques to address the specific challenges posed by nonlinear
risk measures: (i) the Lipschitz continuity w.r.t.
$\left\lVert\cdot\right\rVert_{\infty}$ together with the DKW inequality to
ensure the optimism (step 1), and (ii) the Lipschitz continuity w.r.t.
$\left\lVert\cdot\right\rVert_{1}$ together with a transport inequality (see
Lemma 1) to obtain recursions of suboptimality gap.

##### Step 1: establish optimism.

We first show that $V^{k}_{1}(s^{k}_{1})\geq V^{*}_{1}(s^{k}_{1}),\forall
k\in[K]$ with high probability. Using the Lipschitz property of $\rho_{h}$
w.r.t. $\left\lVert\cdot\right\rVert_{\infty}$ and the DKW inequality (Fact 5)

$\displaystyle\rho_{h}\left(V^{*}_{h+1},P_{h}(s,a)\right)-\rho_{h}\left(V^{*}_{h+1},\hat{P}^{k}_{h}(s,a)\right)$
$\displaystyle\leq
L_{\infty,H-h}\left\lVert(V^{*}_{h+1},P_{h}(s,a))-\left(V^{*}_{h+1},\hat{P}^{k}_{h}(s,a)\right)\right\rVert_{\infty}$
$\displaystyle\leq L_{\infty,H-h}\sqrt{\frac{\iota}{2(N^{k}_{h}(s,a)\vee
1)}}=b^{k}_{h}(s,a).$

The results follows from the monotonicity of $\rho_{h}$ and induction.

##### Step 2: regret decomposition.

We define $\Delta^{k}_{h}\triangleq
V^{k}_{h}-V_{h}^{\pi^{k}}\in\mathbb{R}^{\mathcal{S}}$ and
$\delta^{k}_{h}\triangleq\Delta^{k}_{h}(s^{k}_{h})$. The optimism implies that
the regret can be bounded by the surrogate regret

$\displaystyle\text{Regret}(K)$
$\displaystyle=\sum^{K}_{k=1}V^{*}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})\leq\sum^{K}_{k=1}V^{k}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})=\sum^{K}_{k=1}\delta^{k}_{1}.$

We write $r^{k}_{h}\triangleq r_{h}(s^{k}_{h},a^{k}_{h})$,
$b^{k}_{h}\triangleq b^{k}_{h}(s^{k}_{h},a^{k}_{h})$, $N^{k}_{h}\triangleq
N^{k}_{h}(s^{k}_{h},a^{k}_{h})$,
$\hat{P}^{k}_{h}(s^{k}_{h})\triangleq\hat{P}^{k}_{h}(s^{k}_{h},a^{k}_{h})$,
and $P^{\pi^{k}}_{h}\triangleq P_{h}(s^{k}_{h},a^{k}_{h})$ for simplicity. For
any $h\in[H-1]$, We decompose $\delta^{k}_{h}$ as follows

$\displaystyle\delta^{k}_{h}$
$\displaystyle=b^{k}_{h}+\underbrace{\rho_{h}\left(V^{k}_{h+1},\hat{P}^{k}_{h}\right)-\rho_{h}\left(V^{k}_{h+1},P^{\pi^{k}}_{h}\right)}_{(a)}+\underbrace{\rho_{h}\left(V^{k}_{h+1},P^{\pi^{k}}_{h}\right)-\rho_{h}\left(V^{\pi^{k}}_{h+1},P^{\pi^{k}}_{h}\right)}_{(b)}.$

Bounding term (a) and term (b) requires new techniques compared with risk-
neutral setting. To deal with the nonlinearity, we relate the two value
difference terms to the distances between value distribution via Lipschitzness
of the risk measure.To bound term (a), we use the Lipschitz property w.r.t.
$\left\lVert\cdot\right\rVert_{\infty}$ to get

$\displaystyle(a)$ $\displaystyle\leq
L_{\infty,h}\left\lVert\left(V^{k}_{h+1},\hat{P}^{k}_{h}\right)-\left(V^{k}_{h+1},P^{\pi^{k}}_{h}\right)\right\rVert_{\infty}\leq
L_{\infty,h}\left\lVert\hat{P}^{k}_{h}-P^{\pi^{k}}_{h}\right\rVert_{1}\leq
L_{\infty,h}\cdot c^{k}_{h}.$

Due to the linearity of expectation, standard analysis bound term (b) by the
sum of the vale gap at next step $\delta^{k}_{h+1}$ and a martingale noise,
and then the recursion of the value gap is obtained. The derivation of a
recursion in the presence of nonlinear $\rho_{h}$, however, leads to the main
technical challenge. Our key observation to overcome the difficulty is a
simple transport inequality in the following.

######  Lemma 1.

$\left\lVert(x,P)-(y,P)\right\rVert_{1}\leq\sum_{i=1}^{n}P_{i}\left\lvert
x_{i}-y_{i}\right\rvert.$

Together with the Lipschitz property w.r.t.
$\left\lVert\cdot\right\rVert_{1}$, we have

$\displaystyle(b)$ $\displaystyle\leq
L_{1,h}\left\lVert\left(V^{k}_{h+1},P^{\pi^{k}}_{h}\right)-\left(V^{\pi^{k}}_{h+1},P^{\pi^{k}}_{h}\right)\right\rVert_{1}\leq
L_{1,h}\sum_{s^{\prime}\in\mathcal{S}}P^{\pi^{k}}_{h}(s^{\prime})\left\lvert
V^{k}_{h+1}(s^{\prime})-V^{\pi^{k}}_{h+1}(s^{\prime})\right\rvert$
$\displaystyle=L_{1,h}\sum_{s^{\prime}\in\mathcal{S}}P^{\pi^{k}}_{h}(s^{\prime})\left(V^{k}_{h+1}(s^{\prime})-V^{\pi^{k}}_{h+1}(s^{\prime})\right)=L_{1,h}\cdot
P^{\pi^{k}}_{h}\Delta^{k}_{h+1}\triangleq
L_{1,h}(\epsilon^{k}_{h}+\delta^{k}_{h+1}),$

where $\epsilon^{k}_{h}\triangleq
P^{\pi^{k}}_{h}\Delta^{k}_{h+1}-\Delta^{k}_{h+1}(s^{k}_{h+1})$ is a martingale
difference sequence, and the first equality is due to
$V^{k}_{h+1}(s^{\prime})\geq V^{*}_{h+1}(s^{\prime})\geq
V^{\pi^{k}}_{h+1}(s^{\prime})$ for all $s^{\prime}$. Now we can bound
$\delta^{k}_{h}$ recursively

$\displaystyle\delta^{k}_{h}\leq L_{\infty,h}\cdot
c^{k}_{h}+L_{1,h}(\epsilon^{k}_{h}+\delta^{k}_{h+1})+b^{k}_{h}\leq
2L_{\infty,h}\cdot
c^{k}_{h}+L_{1,h}(\epsilon^{k}_{h}+\delta^{k}_{h+1})+c^{k}_{h}.$

##### Step 3: putting together.

Unrolling the recursion and summing up over $K$ episodes yields

$\displaystyle\text{Regret}(K)\leq\sum_{k\in[K]}\delta^{k}_{1}\leq
2\sum^{H-1}_{h=1}L_{\infty,h}\tilde{L}_{1,h-1}\sum_{k=1}^{K}c^{k}_{h}+\sum_{k=1}^{K}\sum^{H-1}_{h=1}\tilde{L}_{1,h}\epsilon^{k}_{h}.$

We bound the first term via a pigeonhole argument and bound the second term by
the Azuma-Hoeffding inequality. The finial result follows from a union bound.

##  6 Conclusions

We propose two model-based algorithms for the broad class of Lipschitz DRMs.
To establish the efficacy of our algorithms, we provide theoretical guarantees
in the form of worst-case and gap-dependent regret upper bounds. To complement
our upper bounds, we also establish regret lower bounds. These lower bounds
demonstrate the inherent difficulty of the problem.

There are several promising future directions. It might be possible to improve
the regret upper bounds by designing new algorithms or improving the analysis.
Currently, our algorithms and analysis are primarily focused on tabular MDPs.
However, extending the results to the setting of function approximation, such
as linear function approximation, is an important and challenging task. The
nonlinearity of risk measures poses a significant obstacle in this context.
One potential approach to address this issue is to leverage techniques like
value-targeted regression, as proposed in Ayoub et al., (2020); Jia et al.,
(2020), and integrate them into our framework.

## References

  * Acerbi, (2002) Acerbi, C. (2002).  Spectral measures of risk: A coherent representation of subjective risk aversion.  Journal of Banking & Finance, 26(7):1505–1518.
  * Acerbi and Tasche, (2002) Acerbi, C. and Tasche, D. (2002).  On the coherence of expected shortfall.  Journal of Banking & Finance, 26(7):1487–1503.
  * Artzner et al., (1999) Artzner, P., Delbaen, F., Eber, J.-M., and Heath, D. (1999).  Coherent measures of risk.  Mathematical finance, 9(3):203–228.
  * Asienkiewicz and Jaśkiewicz, (2017) Asienkiewicz, H. and Jaśkiewicz, A. (2017).  A note on a new class of recursive utilities in markov decision processes.  Applicationes Mathematicae, 44:149–161.
  * Ayoub et al., (2020) Ayoub, A., Jia, Z., Szepesvari, C., Wang, M., and Yang, L. (2020).  Model-based reinforcement learning with value-targeted regression.  In International Conference on Machine Learning, pages 463–474. PMLR.
  * Azar et al., (2017) Azar, M. G., Osband, I., and Munos, R. (2017).  Minimax regret bounds for reinforcement learning.  In International Conference on Machine Learning, pages 263–272. PMLR.
  * Balbás et al., (2009) Balbás, A., Garrido, J., and Mayoral, S. (2009).  Properties of distortion risk measures.  Methodology and Computing in Applied Probability, 11(3):385–399.
  * Bastani et al., (2022) Bastani, O., Ma, J. Y., Shen, E., and Xu, W. (2022).  Regret bounds for risk-sensitive reinforcement learning.  Advances in Neural Information Processing Systems, 35:36259–36269.
  * Bäuerle and Glauner, (2022) Bäuerle, N. and Glauner, A. (2022).  Markov decision processes with recursive risk measures.  European Journal of Operational Research, 296(3):953–966.
  * Ben-Tal and Teboulle, (2007) Ben-Tal, A. and Teboulle, M. (2007).  An old-new concept of convex risk measures: the optimized certainty equivalent.  Mathematical Finance, 17(3):449–476.
  * Bielecki et al., (2000) Bielecki, T. R., Pliska, S. R., and Sherris, M. (2000).  Risk sensitive asset allocation.  Journal of Economic Dynamics and Control, 24(8):1145–1177.
  * Chu and Zhang, (2014) Chu, S. and Zhang, Y. (2014).  Markov decision processes with iterated coherent risk measures.  International Journal of Control, 87(11):2286–2293.
  * Coache and Jaimungal, (2021) Coache, A. and Jaimungal, S. (2021).  Reinforcement learning with dynamic convex risk measures.  arXiv preprint arXiv:2112.13414.
  * Coache et al., (2022) Coache, A., Jaimungal, S., and Cartea, Á. (2022).  Conditionally elicitable dynamic risk measures for deep reinforcement learning.  arXiv preprint arXiv:2206.14666.
  * Davis and Lleo, (2008) Davis, M. and Lleo, S. (2008).  Risk-sensitive benchmarked asset management.  Quantitative Finance, 8(4):415–426.
  * Delage and Mannor, (2010) Delage, E. and Mannor, S. (2010).  Percentile optimization for markov decision processes with parameter uncertainty.  Operations research, 58(1):203–213.
  * Domingues et al., (2021) Domingues, O. D., Ménard, P., Kaufmann, E., and Valko, M. (2021).  Episodic reinforcement learning in finite mdps: Minimax lower bounds revisited.  In Algorithmic Learning Theory, pages 578–598. PMLR.
  * Du et al., (2023) Du, Y., Wang, S., and Huang, L. (2023).  Provably efficient risk-sensitive reinforcement learning: Iterated cvar and worst path.  In The Eleventh International Conference on Learning Representations.
  * Ernst et al., (2006) Ernst, D., Stan, G.-B., Goncalves, J., and Wehenkel, L. (2006).  Clinical data based optimal sti strategies for hiv: a reinforcement learning approach.  In Proceedings of the 45th IEEE Conference on Decision and Control, pages 667–672. IEEE.
  * Fei and Xu, (2022) Fei, Y. and Xu, R. (2022).  Cascaded gaps: Towards logarithmic regret for risk-sensitive reinforcement learning.  In International Conference on Machine Learning, pages 6392–6417. PMLR.
  * Fei et al., (2021) Fei, Y., Yang, Z., Chen, Y., and Wang, Z. (2021).  Exponential bellman equation and improved regret bounds for risk-sensitive reinforcement learning.  Advances in Neural Information Processing Systems, 34:20436–20446.
  * Fei et al., (2020) Fei, Y., Yang, Z., Chen, Y., Wang, Z., and Xie, Q. (2020).  Risk-sensitive reinforcement learning: Near-optimal risk-sample tradeoff in regret.  Advances in Neural Information Processing Systems, 33:22384–22395.
  * Föllmer and Knispel, (2011) Föllmer, H. and Knispel, T. (2011).  Entropic risk measures: Coherence vs. convexity, model ambiguity and robust large deviations.  Stochastics and Dynamics, 11(02n03):333–351.
  * Föllmer and Knispel, (2013) Föllmer, H. and Knispel, T. (2013).  Convex risk measures: Basic facts, law-invariance and beyond, asymptotics for large portfolios.  In Handbook of the fundamentals of financial decision making: Part II, pages 507–554. World Scientific.
  * Garivier et al., (2019) Garivier, A., Ménard, P., and Stoltz, G. (2019).  Explore first, exploit next: The true shape of regret in bandit problems.  Mathematics of Operations Research, 44(2):377–399.
  * Howard and Matheson, (1972) Howard, R. A. and Matheson, J. E. (1972).  Risk-sensitive markov decision processes.  Management science, 18(7):356–369.
  * Huang et al., (2021) Huang, A., Leqi, L., Lipton, Z., and Azizzadenesheli, K. (2021).  Off-policy risk assessment in contextual bandits.  Advances in Neural Information Processing Systems, 34:23714–23726.
  * Jia et al., (2020) Jia, Z., Yang, L., Szepesvari, C., and Wang, M. (2020).  Model-based reinforcement learning with value-targeted regression.  In Learning for Dynamics and Control, pages 666–686. PMLR.
  * Lam et al., (2023) Lam, T., Verma, A., Low, B. K. H., and Jaillet, P. (2023).  Risk-aware reinforcement learning with coherent risk measures and non-linear function approximation.  In The Eleventh International Conference on Learning Representations.
  * Liang and Luo, (2022) Liang, H. and Luo, Z.-Q. (2022).  Bridging distributional and risk-sensitive reinforcement learning with provable regret bounds.  arXiv preprint arXiv:2210.14051.
  * Osogami, (2012) Osogami, T. (2012).  Iterated risk measures for risk-sensitive markov decision processes with discounted cost.  arXiv preprint arXiv:1202.3755.
  * Prashanth and Bhat, (2022) Prashanth, L. and Bhat, S. P. (2022).  A wasserstein distance approach for concentration of empirical risk estimates.  The Journal of Machine Learning Research, 23(1):10830–10890.
  * Rockafellar et al., (2000) Rockafellar, R. T., Uryasev, S., et al. (2000).  Optimization of conditional value-at-risk.  Journal of risk, 2:21–42.
  * Rudloff et al., (2008) Rudloff, B., Sass, J., and Wunderlich, R. (2008).  Entropic risk constraints for utility maximization.  Festschrift in celebration of prof. Dr. Wilfried Grecksch’s 60th birthday, pages 149–180.
  * Ruszczyński, (2010) Ruszczyński, A. (2010).  Risk-averse dynamic programming for markov decision processes.  Mathematical programming, 125(2):235–261.
  * Shen et al., (2013) Shen, Y., Stannat, W., and Obermayer, K. (2013).  Risk-sensitive markov control processes.  SIAM Journal on Control and Optimization, 51(5):3652–3672.
  * Simchowitz and Jamieson, (2019) Simchowitz, M. and Jamieson, K. G. (2019).  Non-asymptotic gap-dependent regret bounds for tabular mdps.  Advances in Neural Information Processing Systems, 32.
  * Sutton and Barto, (2018) Sutton, R. S. and Barto, A. G. (2018).  Reinforcement learning: An introduction.  MIT press.
  * Wang et al., (2023) Wang, K., Kallus, N., and Sun, W. (2023).  Near-minimax-optimal risk-sensitive reinforcement learning with cvar.  arXiv preprint arXiv:2302.03201.
  * Weissman et al., (2003) Weissman, T., Ordentlich, E., Seroussi, G., Verdu, S., and Weinberger, M. J. (2003).  Inequalities for the l1 deviation of the empirical distribution.  Hewlett-Packard Labs, Tech. Rep.
  * Wirch and Hardy, (2001) Wirch, J. L. and Hardy, M. R. (2001).  Distortion risk measures: Coherence and stochastic dominance.  In International congress on insurance: Mathematics and economics, pages 15–17.
  * Xu et al., (2023) Xu, W., Gao, X., and He, X. (2023).  Regret bounds for markov decision processes with recursive optimized certainty equivalents.  arXiv preprint arXiv:2301.12601.

##  Appendix A Experiments

In this section, we provide some numerical results to validate the empirical
performance of our algorithms. We compare our algorithms to the algorithms
UCBVI Azar et al., (2017) for risk-neutral RL and RSVI2 Fei et al., (2021) for
RSRL with ERM.

(a) Comparison of different algorithms for homogeneous CVaR.

(b) Comparison of different algorithms for in-homogeneous CVaR.

In our experiments, we focus on an MDP with $S=3$ states, $A$ actions, and
horizon $H$, which is similar to the construction in Du et al., (2023). The
major difference is that we consider a non-stationary MDP. The MDP consists of
a fixed initial state denoted as state 0, and three additional states denoted
as states 1, 2, and 3. In step $2\leq h\leq H$, the three states generate
reward 1,0 and 0.4, respectively. The agent starts from state $0$ in the first
step, takes action from $[A]$, and then transitions to one of three states
$\\{1,2,3\\}$ in the next step. Any action in $[A-1]$ leads to a uniform
transition to state $1$ and state 2. The optimal action $A$ leads to a
transition to state 2 and state 3 with probability 0.001 and 0.999.

We consider the dynamic CVaR with the homogeneous and in-homogeneous setting.
For the homogeneous CVaR, the coefficients at all steps are identical, while
for the in-homogeneous CVaR, the coefficients at different steps could be
different. We set $\delta=0.005$, $A=5$, $H=5$ and $K=10000$. We set
$\alpha=(0.05,0.05,0.05,0.05)$ and $\alpha=(0.09,0.08,0.07,0.05)$ for the
homogeneous and in-homogeneous CVaR, respectively. We perform 5 independent
runs for each algorithm.

As shown in Figure 1(a), OVI-DRM and UCBVI-DRM enjoy sublinear regret while
the risk-neutral algorithm UCBVI and RSVI2 suffer linear regret. In
particular, OVI-DRM outperforms UCBVI-DRM because it achieves a better balance
between exploration and exploitation. Figure 1(b) only plots the results for
our algorithms. It shows that UCBVI-DRM can also learn the optimal policy in
the in-homogeneous CVaR setting.

##  Appendix B Risk Measures

###  B.1 Definitions

##### Conditional Value at Risk (CVaR)

The CVaR value Rockafellar et al., (2000) at level $\alpha\in(0,1)$ for a
distribution $F$ is defined as

$C_{\alpha}(F)\triangleq\sup_{\nu\in\mathbb{R}}\left\\{\nu-\frac{1}{\alpha}\mathbb{E}_{X\sim
F}[(\nu-X)^{+}]\right\\}.$

Acerbi and Tasche, (2002) showed that when $F$ is a continuous distribution,
$C_{\alpha}(F)=\mathbb{E}_{X\sim F}[X|X\leq F^{-1}(\alpha)]$.

##### Spectral risk measure (SRM)

SRM is class of risk measures that generalizes CVaR via adopting a non-
constant weighting function over the quantiles Acerbi, (2002). The SRM value
of $F$ is defined as

$S_{\phi}(F)\triangleq\int_{0}^{1}\phi(y)F^{-1}(y)dy,$

where $\phi:[0,1]\rightarrow[0,\infty)$ is the weighting function. Acerbi,
(2002) showed that an SRM is coherent if $\phi$ is is decreasing and satisfies
that $\int_{0}^{1}\phi(y)dy=1$. SRM can be viewed as a weighted average of the
quantiles, with weight specified by $\phi(y)$. In fact, $S_{\phi}(F)$
specializes in $C_{\alpha}(F)$ for $\phi(y)=\frac{1}{\alpha}\mathbb{I}\\{0\leq
y\leq\alpha\\}$.

##### Distortion risk measure

For a distribution $F\in\mathscr{D}([0,\infty))$, the distortion risk measure
Balbás et al., (2009); Wirch and Hardy, (2001) $\rho_{g}(F)$ is defined as

$\rho_{g}(F)\triangleq\int_{0}^{\infty}g(1-F(x))dx,$

where $g:[0,1]\rightarrow[0,1]$ is a continuous increasing function with
$g(0)=0$ and $g(1)=1$. We refer to $g$ as the distortion function. Distortion
risk measure is coherent if and only if $g$ is convex. Similar to SRM,
distortion risk measure can also recover CVaR by choosing proper $g$.

##### Entropic risk measure (ERM)

ERM adjusts the risk attitude of the user through the exponential utility
function. In particular, the ERM value of $F$ with coefficient $\beta\neq 0$
is defined as

$U_{\beta}(F)\triangleq\frac{1}{\beta}\log(\mathbb{E}_{X\sim F}[\exp(\beta
X)])=\frac{1}{\beta}\log\left(\int_{\mathbb{R}}\exp(\beta x)dF(x)\right).$

Notably, ERM is the prime example of a convex risk measure which is not
coherent Rudloff et al., (2008).

##### Optimized certainty equivalent (OCE)

The OCE Ben-Tal and Teboulle, (2007) value of $F$ associated with a utility
function $u$ is given by

$C_{u}(F)\triangleq\sup_{\lambda}\left\\{\lambda+\mathbb{E}_{X\sim
F}[u(X-\lambda)]\right\\}=\sup_{\lambda}\left\\{\lambda+\int_{\mathbb{R}}u(x-\lambda)dF(x)\right\\},$

where $u$ is a non-decreasing, closed utility function that satisfies $u(0)=0$
and $1\in\partial u(0)$. THE OCE is risk-averse (risk-seeking) if and only $u$
is concave (convex). OCE subsumes important examples of popular risk measures,
including the ERM and CVaR.

###  B.2 Lipschitz Property

We summarizes the Lipschitz constants of common risk measures over a finite
interval $[a,b]$ in Table 2. Prashanth and Bhat, (2022) provides the Lipschitz
constants of SRM, OCE, and distortion risk measure w.r.t. the Wasserstein
distance or $\left\lVert\cdot\right\rVert_{1}$. Huang et al., (2021) provides
the Lipschitz constants of distortion risk measure w.r.t.
$\left\lVert\cdot\right\rVert_{\infty}$.

For completeness, we will derive the Lipschitz constants of SRM and OCE w.r.t.
$\left\lVert\cdot\right\rVert_{\infty}$ in the following. Fact 1 offers a
simple way to derive the Lipschitz constant of a risk measure w.r.t.
$\left\lVert\cdot\right\rVert_{1}$ based on that w.r.t. the
$\left\lVert\cdot\right\rVert_{\infty}$. Therefore, the Lipschitz constants of
SRM w.r.t. $\left\lVert\cdot\right\rVert_{\infty}$ can take
$L_{\infty}(M_{\phi},[a,b])=(b-a)\cdot
L_{1}(M_{\phi},[a,b])=(b-a)\max|\phi(x)|$. As a special case, we have
$L_{\infty}(C_{\alpha},[0,M])=\frac{b-a}{\alpha}$.

######  Fact 1.

If a functional $\rho$ has Lipschitz constant $L_{1}([a,b])$ over
$\mathscr{D}([a,b])$, then it has Lipschitz constant
$L_{\infty}([a,b])=L_{1}([a,b])(b-a)$.

###### Proof.

Suppose $\rho$ has Lipschitz constant $L_{1}([a,b])$ over
$\mathscr{D}([a,b])$, then

$|\rho(F)-\rho(G)|\leq L_{1}([a,b])\left\lVert F-G\right\rVert_{1}\leq
L_{1}([a,b])\left\lVert F-G\right\rVert_{\infty}(b-a),\forall
F,G\in\mathscr{D}([a,b]).$

This implies that $L_{\infty}([a,b])=L_{1}([a,b])(b-a)$ is a valid choice. ∎

######  Fact 2.

The Lipschitz constants of OCE w.r.t. $\left\lVert\cdot\right\rVert_{\infty}$
is $L_{\infty}(C_{u},[a,b])=-u(a-b)$ for concave utility function and
$L_{\infty}(C_{u},[a,b])=u(b-a)$ for convex utility function.

###### Proof.

Let $\lambda_{1},\lambda_{2}\in[a,b]$ satisfy

$\displaystyle C_{u}(F)$
$\displaystyle=\lambda_{1}+\int_{a}^{b}u(x-\lambda_{1})dF(x)=\max_{\lambda\in[a,b]}\lambda+\int_{a}^{b}u(x-\lambda)dF(x)$
$\displaystyle C_{u}(G)$
$\displaystyle=\lambda_{2}+\int_{a}^{b}u(x-\lambda_{2})dG(x)=\max_{\lambda\in[a,b]}\lambda+\int_{a}^{b}u(x-\lambda)dG(x).$

Without loss generality, we assume $C_{u}(F)>C_{u}(G)$. It holds that

$\displaystyle C_{u}(F)-C_{u}(G)$
$\displaystyle=\lambda_{1}+\int_{a}^{b}u(x-\lambda_{1})dF(x)-\lambda_{2}-\int_{a}^{b}u(x-\lambda_{2})dG(x)$
$\displaystyle\leq\lambda_{1}+\int_{a}^{b}u(x-\lambda_{1})dF(x)-\lambda_{1}-\int_{a}^{b}u(x-\lambda_{1})dG(x)$
$\displaystyle=\int_{a}^{b}u(x-\lambda_{1})dF(x)-\int_{a}^{b}u(x-\lambda_{1})dG(x)$
$\displaystyle=u(x-\lambda_{1})F(x)|_{a}^{b}-\int_{a}^{b}F(x)du(x-\lambda_{1})-u(x-\lambda_{1})G(x)|_{a}^{b}+\int_{a}^{b}G(x)du(x-\lambda_{1})$
$\displaystyle=\int_{a}^{b}(G(x)-F(x))du(x-\lambda_{1})$
$\displaystyle\leq\int_{a}^{b}du(x-\lambda_{1})\cdot\left\lVert
F-G\right\rVert_{\infty}$
$\displaystyle=(u(b-\lambda_{1})-u(a-\lambda_{1}))\left\lVert
F-G\right\rVert_{\infty}$
$\displaystyle\leq\max_{\lambda\in[a,b]}(u(b-\lambda)-u(a-\lambda))\left\lVert
F-G\right\rVert_{\infty}=L_{\infty}(C_{u},[a,b])\left\lVert
F-G\right\rVert_{\infty},$

where the second inequality is due to that $u$ is non-decreasing. For concave
utility function, we can bound the last term as

$\max_{\lambda\in[a,b]}(u(b-\lambda)-u(a-\lambda))=u(b-b)-u(a-b)=-u(a-b).$

For convex utility function, we can bound the last term as

$\max_{\lambda\in[a,b]}(u(b-\lambda)-u(a-\lambda))=u(b-a)-u(a-a)=u(b-a).$

∎

######  Fact 3.

The Lipschitz constants of OCE w.r.t. $\left\lVert\cdot\right\rVert_{1}$ is
$L_{1}(C_{u},[a,b])=u^{\prime}(a-b)$ for concave utility function and
$L_{1}(C_{u},[a,b])=u^{\prime}(b-a)$ for convex utility function.

###### Proof.

Let $\lambda_{1},\lambda_{2}\in[a,b]$ satisfy

$\displaystyle C_{u}(F)$
$\displaystyle=\lambda_{1}+\int_{a}^{b}u(x-\lambda_{1})dF(x)=\max_{\lambda\in[a,b]}\lambda+\int_{a}^{b}u(x-\lambda)dF(x)$
$\displaystyle C_{u}(G)$
$\displaystyle=\lambda_{2}+\int_{a}^{b}u(x-\lambda_{2})dG(x)=\max_{\lambda\in[a,b]}\lambda+\int_{a}^{b}u(x-\lambda)dG(x).$

Without loss generality, we assume $C_{u}(F)>C_{u}(G)$. It holds that

$\displaystyle C_{u}(F)-C_{u}(G)$
$\displaystyle=\lambda_{1}+\int_{a}^{b}u(x-\lambda_{1})dF(x)-\lambda_{2}-\int_{a}^{b}u(x-\lambda_{2})dG(x)$
$\displaystyle\leq\int_{a}^{b}u(x-\lambda_{1})dF(x)-\int_{a}^{b}u(x-\lambda_{1})dG(x)$
$\displaystyle=\int_{a}^{b}(G(x)-F(x))du(x-\lambda_{1})$
$\displaystyle=\int_{a}^{b}(G(x)-F(x))u^{\prime}(x-\lambda_{1})dx$
$\displaystyle\leq\max_{\lambda\in[a,b],x\in[a,b]}u^{\prime}(x-\lambda)\int_{a}^{b}|G(x)-F(x)|dx$
$\displaystyle=L_{1}(C_{u},[a,b])\left\lVert F-G\right\rVert_{1},$

where the second inequality is due to the non-negativity of $u^{\prime}$. For
concave utility function, we can bound the last term as

$\max_{\lambda\in[a,b],x\in[a,b]}u^{\prime}(x-\lambda)=u^{\prime}(a-b).$

For convex utility function, we can bound the last term as

$\max_{\lambda\in[a,b],x\in[a,b]}u^{\prime}(x-\lambda)=u^{\prime}(b-a).$

∎

OCE subsumes ERM when $u(x)=\frac{\exp(\beta x)-1}{\beta}$. In particular,
$L_{\infty}(U_{\beta},[a,b])=-u(a-b)=-\frac{\exp(\beta(a-b))-1}{\beta}=\frac{\exp(|\beta|(b-a))-1}{|\beta|}$
for concave utility ($\beta<0$) and
$L_{\infty}(U_{\beta},[a,b])=u(b-a)=\frac{\exp(\beta(b-a))-1}{\beta}$ for
convex utility ($\beta>0$).

Table 2: Lipschitz constants of common risk measures Lipschitz constant | CVaR | SRM | distortion risk measure | OCE444For convenience, we only list OCE with concave risk measure.
---|---|---|---|---
$L_{1}([a,b])$ | $\frac{1}{\alpha}$ | $\max\phi(x)$ | $\max g^{\prime}(x)$ | $u^{\prime}(a-b)$
$L_{\infty}([a,b])$ | $\frac{b-a}{\alpha}$ | $(b-a)\max\phi(x)$ | $(b-a)\max g^{\prime}(x)$ | $-u(a-b)$

##  Appendix C Subroutine

We present the subroutine OM used in Algorithm 2 in this section. Fix an
$(s,a,k,k)$, OM takes the empirical model $\hat{P}^{k}_{h}(s,a)$, the value at
the next step $V^{k}_{h+1}$, and a confidence radius $c^{k}_{h}(s,a)$ as input
and outputs the optimistic model $\tilde{P}^{k}_{h}(s,a)$. For a PMF $P$ and a
real number $c>0$, denote by
$B_{1}(P,c)\triangleq\left\\{P^{\prime}|\left\lVert
P^{\prime}-P\right\rVert_{1}\leq c\right\\}$ the $\ell_{1}$ norm ball centered
at $P$ with radius $c$.

Algorithm 3 OM

1:Input: $P=(P(s_{1}),\dots,P(s_{S}))$, $V=(V(s_{1}),\dots,V(s_{S}))$ and
$c>0$

2:Sorting: let $V^{\prime}=(V(s_{(1)}),\cdots,V(s_{(S)}))$ such that
$V(s_{(1)})\leq V(s_{(2)})\leq\cdots\leq V(s_{(S)})$

3:Permutation: let $P^{\prime}=(P(s_{(1)}),\cdots,P(s_{(S)}))$

4:Transport: sequentially move probability mass $\frac{c}{2}\land 1$ of the
leftmost states to $s_{(S)}$

Recall that we $F\succeq G$ denotes that $F(x)\leq G(x),\forall
x\in\mathbb{R}$. Lemma 2 shows that OM can output an optimistic model
$\tilde{P}$ whose value distribution dominates those generated by the model
within the concentration ball.

######  Lemma 2.

Let $P,V,c$ be the input of OM and $\tilde{P}$ be the output. It holds that

$(\tilde{P},V)\succeq(Q,V),\forall Q\in B_{1}(P,c).$

###### Proof.

For simplicity, let $P=(P_{1},\cdots,P_{n})$, $V\in\mathbb{R}^{n}$ satisfying
$V_{1}\leq V_{2}\cdots\leq V_{n}$. Observe that the CDF $(P,V)$ is a piecewise
constant function. Hence it suffices to show that

$\sum_{j=1}^{i}\tilde{P}_{j}\leq\sum_{j=1}^{i}Q_{j},\forall i\in[n],\forall
Q\in B_{1}(P,c).$

Let $l\triangleq\min\left\\{i|\sum_{j=1}^{i}P_{j}\geq\frac{c}{2}\right\\}$.
There are two cases.

Case 1: $P_{n}+\frac{c}{2}\leq 1$. Since $\sum_{j=1}^{l-1}P_{j}<\frac{c}{2}$
and $\sum_{j=1}^{l}P_{j}\geq\frac{c}{2}$, we have

$\tilde{P}_{i}=\begin{cases}0,i\in[l-1]\\\
\sum_{j=1}^{l}P_{j}-\frac{c}{2},i=l\\\ P_{i},l+1\leq i\leq n-1\\\
P_{n}+\frac{c}{2},i=n\end{cases}$

and thus

$\sum_{j=1}^{i}\tilde{P}_{j}=\begin{cases}0,i\in[l-1]\\\
\sum_{j=1}^{l}P_{j}-\frac{c}{2},l\leq i\leq n-1\\\ 1,i=n\end{cases}$

For any $Q\in B_{1}(P,c)$, it holds that

$\sum_{j=1}^{i}\tilde{P}_{j}\leq\sum_{j=1}^{i}Q_{j},\forall i\in[n].$

Otherwise $\sum_{j=1}^{k}Q_{j}<\sum_{j=1}^{k}P_{j}-\frac{c}{2}$ for some
$l\leq k\leq n-1$, which implies
$\sum_{j=k+1}^{n}Q_{j}=1-\sum_{j=1}^{k}Q_{j}>1-\sum_{j=1}^{k}P_{j}+\frac{c}{2}=\sum_{j=1}^{k}P_{j}+\frac{c}{2}$.
This leads to a contradiction $\left\lVert
P-Q\right\rVert_{1}=\sum_{j\in[n]}|P_{j}-Q_{j}|\geq|\sum_{j=1}^{k}P_{j}-\sum_{j=1}^{k}Q_{j}|+|\sum_{j=k+1}^{n}P_{j}-\sum_{j=k+1}^{n}Q_{j}|>c$.

Case 2: $P_{n}+\frac{c}{2}>1$. In this case, $\tilde{P}_{j}=0$ for $j\in[n-1]$
and $\tilde{P}_{n}=1$. It is obvious that

$\sum_{j=1}^{i}\tilde{P}_{j}\leq\sum_{j=1}^{i}Q_{j},\forall i\in[n],\forall
Q\in B_{1}(P,c).$

Therefore, we have

$(\tilde{P},V)\succeq(Q,V),\forall Q\in B_{1}(P,c).$

∎

Lemma 2 together with the monotonicity of $\rho_{h}$ implies that the output
$\tilde{P}^{k}_{h}(s,a)$ satisfies

$\rho_{h}(\tilde{P}^{k}_{h}(s,a),V^{k}_{h+1})\geq\rho_{h}(P^{\prime},V^{k}_{h+1}),\
\forall P^{\prime}\in B_{1}(\hat{P}^{k}_{h}(s,a),c^{k}_{h}(s,a)).$

In Appendix D, we will show that $P_{h}(s,a)\in
B_{1}(\hat{P}^{k}_{h}(s,a),c^{k}_{h}(s,a))$ with high probability. Suppose
$V^{k}_{h+1}(s)\geq V^{*}_{h+1}(s),\forall s$. It follows that

$\displaystyle Q^{k}_{h}(s,a)$
$\displaystyle=r_{h}(s,a)+\rho_{h}(\tilde{P}^{k}_{h}(s,a),V^{k}_{h+1})\geq
r_{h}(s,a)+\rho_{h}(P_{h}(s,a),V^{k}_{h+1})$ $\displaystyle\geq
r_{h}(s,a)+\rho_{h}(P_{h}(s,a),V^{*}_{h+1})=Q^{*}_{h}(s,a),\forall(s,a).$

The second inequality is due to the monotonicity of $\rho_{h}$ together with
the fact that

$V^{k}_{h+1}\geq
V^{*}_{h+1}\Longrightarrow(P_{h}(s,a),V^{k}_{h+1})\succeq(P_{h}(s,a),V^{*}_{h+1}).$

Then we have $V^{k}_{h}(s)=\max Q^{k}_{h}(s,a)\geq\max
Q^{*}_{h}(s,a)=V^{*}_{h}(s),\forall s$. By induction, we obtain

$V^{k}_{h}(s)\geq V^{*}_{h}(s),\forall(k,h,s).$

This implies that the value functions induced by the optimistic models are
indeed optimistic compared to the optimal value functions. The computational
complexity of OM is $O(S\log(S))$, since the computational complexity of each
step is $O(S\log(S))$, $O(S)$, and $O(S)$.

##  Appendix D Proofs of Regret Upper Bounds

###  D.1 Worst-case Regret Upper Bound

We first prove the worst-case regret upper bound for Algorithm 1.

####  D.1.1 Proof for Algorithm 1

##### Step 1: verify optimism.

Fix an arbitrary $\delta\in(0,1)$. Define the good event
$\mathcal{G}_{\delta}$ as

$\displaystyle\mathcal{G}_{\delta}\triangleq$
$\displaystyle\left\\{\left\lVert\hat{P}^{k}_{h}(\cdot|s,a)-P_{h}(\cdot|s,a)\right\rVert_{1}\leq\sqrt{\frac{2S}{N^{k}_{h}(s,a)\vee
1}\iota},\forall(s,a,k,h)\in\mathcal{S}\times\mathcal{A}\times[K]\times[H]\right\\},$

under which the empirical model concentrates around the true model under
$\left\lVert\cdot\right\rVert_{1}$.

######  Lemma 3 (High probability good event).

The event $\mathcal{G}_{\delta}$ holds with probability at least $1-\delta$.

######  Fact 4 ($\ell_{1}$ concentration bound, Weissman et al., (2003)).

Let $P$ be a probability distribution over a finite discrete measurable space
$(\mathcal{X},\Sigma).$ Let $\widehat{P}_{n}$ be the empirical distribution of
$P$ estimated from $n$ samples. Then with probability at least $1-\delta$,

$\left\|\widehat{P}_{n}-P\right\|_{1}\leq\sqrt{\frac{2|\mathcal{X}|}{n}\log\frac{1}{\delta}}.$

Lemma 3 does not directly follow from a union bound together with Fact 4 since
the case $N^{k}_{h}(s,a)=0$ need to be checked.

###### Proof.

Fix some $(s,a,k,h)\in\mathcal{S}\times\mathcal{A}\times[K]\times[H]$. If
$N^{k}_{h}(s,a)=0$, then we have
$\hat{P}^{k}_{h}(\cdot|s,a)=\frac{1}{S}\textbf{1}$. A simple calculation
yields that for any $P_{h}(\cdot|s,a)$

$\displaystyle\left\lVert\frac{1}{S}\textbf{1}-P_{h}(\cdot|s,a)\right\rVert_{1}\leq
2\leq\sqrt{2S\log(1/\delta)}.$

It follows that

$\displaystyle\mathbb{P}$
$\displaystyle\left(\left\lVert\hat{P}^{k}_{h}(\cdot|s,a)-P_{h}(\cdot|s,a)\right\rVert_{1}\leq\left.\sqrt{\frac{2S}{N^{k}_{h}(s,a)\vee
1}\log(1/\delta)}\right|N^{k}_{h}(s,a)=0\right)=1>1-\delta.$

The event is true for the unseen state-action pairs. Now we consider the case
that $N^{k}_{h}(s,a)>0$. By Fact 4 , we have that for any integer $n\geq 1$

$\displaystyle\mathbb{P}$
$\displaystyle\left(\left\lVert\hat{P}^{k}_{h}(\cdot|s,a)-P_{h}(\cdot|s,a)\right\rVert_{1}\left.\leq\sqrt{\frac{2S}{N^{k}_{h}(s,a)}\log(1/\delta)}\right|N^{k}_{h}(s,a)=n\right)\geq
1-\delta.$

Thus we have

$\displaystyle\mathbb{P}\left(\left\lVert\hat{P}^{k}_{h}(\cdot|s,a)-P_{h}(\cdot|s,a)\right\rVert_{1}\leq\sqrt{\frac{2S\log(1/\delta)}{N^{k}_{h}(s,a)}}\right)$
$\displaystyle=\sum_{n=0,1,\cdots}\mathbb{P}\left(\left\lVert\hat{P}^{k}_{h}(\cdot|s,a)-P_{h}(\cdot|s,a)\right\rVert_{1}\leq\left.\sqrt{\frac{2S\log(1/\delta)}{N^{k}_{h}(s,a)\vee
1}}\right|N^{k}_{h}(s,a)=n\right)\mathbb{P}(N^{k}_{h}(s,a)=n)$
$\displaystyle\geq(1-\delta)\sum_{n=0,1,\cdots}\mathbb{P}(N^{k}_{h}(s,a)=n)=1-\delta.$

Applying a union bound over all $(s,a,k,h)$ and rescaling $\delta$ leads to
the result. ∎

######  Lemma 4 (Range of $V^{*}$).

For any MDP, it holds that $V^{*}_{h}(s)\in[0,H+1-h]$ for all
$(s,h)\in\mathcal{S}\times[H+1]$.

###### Proof.

The proof follows from induction and Assumption 1. Observe that
$V^{*}_{H+1}=0$. Suppose $V^{*}_{h+1}(s)\in[0,H-h]$ for any $s$, then we have

$\displaystyle 0\leq
Q^{*}_{h}(s,a)=r_{h}(s,a)+\rho_{h}(V^{*}_{h+1},P_{h}(s,a))\leq 1+H-h,$

where the inequalities are due to the Assumption 1. Then we have
$V^{*}_{h}(s)=\max_{a}Q^{*}_{h}(s,a)\in[0,H+1-h]$. The induction is completed.
∎

######  Fact 5 (DKW inequality for discrete distribution).

Let $\hat{P_{n}}$ be the empirical PMF for $(x,P)$ with $n$ samples, then w.p.
at least $1-\delta$

$\left\lVert(x,P)-(x,\hat{P}_{n})\right\rVert_{\infty}\leq\sqrt{\frac{\log(2/\delta)}{2n}}.$

We remark that we can also derive a bound by Fact 6: w.p. $1-\delta$

$\left\lVert(x,P)-(x,\hat{P}_{n})\right\rVert_{\infty}\leq\left\lVert
P-\hat{P}_{n}\right\rVert_{1}\leq\sqrt{\frac{2m\log(2/\delta)}{n}}.$

However, this bound is looser than that from Fact 5 with a factor of
$\sqrt{m}$.

######  Lemma 5 (Optimistic value function).

Conditioned on event $\mathcal{G}_{\delta}$, the sequence
$\\{V^{k}_{1}(s^{k}_{1})\\}_{k\in[K]}$ produced by Algorithm 1 satisfies
$V^{k}_{1}(s^{k}_{1})\geq V^{*}_{1}(s^{k}_{1}),\forall k\in[K]$.

###### Proof.

The proof follows from induction. Fix $k\in[K]$. It is evident that the
inequality holds when $h=H+1$. Suppose the inequality holds for $h+1$. It
follows that for any $(s,a)$

$\displaystyle Q^{k}_{h}(s,a)$
$\displaystyle=r_{h}(s,a)+\rho_{h}\left(V^{k}_{h+1},\hat{P}^{k}_{h}(s,a)\right)+b^{k}_{h}(s,a)$
$\displaystyle\geq
r_{h}(s,a)+\rho_{h}\left(V^{*}_{h+1},\hat{P}^{k}_{h}(s,a)\right)+b^{k}_{h}(s,a)$
$\displaystyle\geq
r_{h}(s,a)+\rho_{h}(V^{*}_{h+1},P_{h}(s,a))=Q^{*}_{h}(s,a).$

The first inequality is due to the monotonicity of $\rho_{h}$ and the
induction hypothesis, and the second one follows from that

$\displaystyle\rho_{h}(V^{*}_{h+1},P_{h}(s,a))-\rho_{h}(V^{*}_{h+1},\hat{P}^{k}_{h}(s,a))$
$\displaystyle\leq
L_{\infty}(\rho_{h},H-h)\left\lVert(V^{*}_{h+1},P_{h}(s,a))-\left(V^{*}_{h+1},\hat{P}^{k}_{h}(s,a)\right)\right\rVert_{\infty}$
$\displaystyle\leq
L_{\infty}(\rho_{h},H-h)\sqrt{\frac{\iota}{2(N^{k}_{h}(s,a)\vee
1)}}=b^{k}_{h}(s,a),$

where the first inequality follows from the Lipschitz property of $\rho_{h}$
and Lemma 4, and the second one is due to the DKW inequality (Fact 5). ∎

######  Fact 6.

Let $(x,P)$ and $(x,Q)$ be two discrete distributions with the same support
$x=(x_{1},\cdots,x_{m})$ and $F,G$ be their CDFs respectively. It holds that

$\left\lVert F-G\right\rVert_{\infty}\leq\left\lVert P-Q\right\rVert_{1}.$

###### Proof.

Without loss of generality, we assume that $x_{1}\leq x_{2}\cdots\leq x_{n}$.
By definition,

$\displaystyle\left\lVert F-G\right\rVert_{\infty}$
$\displaystyle=\sup_{x\in\mathbb{R}}\left\lvert
F(x)-G(x)\right\rvert=\max_{i\in[n]}\left\lvert
F(x_{i})-G(x_{i})\right\rvert=\max_{i\in[n]}\left\lvert\sum_{j\in[i]}P_{j}-\sum_{j\in[i]}Q_{j}\right\rvert$
$\displaystyle\leq\max_{i\in[n]}\sum_{j\in[i]}\left\lvert
P_{j}-Q_{j}\right\rvert=\sum_{j\in[n]}\left\lvert
P_{j}-Q_{j}\right\rvert=\left\lVert P-Q\right\rVert_{1}.$

The second equality is due to that $F$ and $G$ are piecewise constant
functions that only differ at $x_{1},\cdots,x_{n}$. This would lead a worse
bonus term with a factor of $\sqrt{S}$. ∎

######  Remark 4.

Alternatively, we have

$\displaystyle\rho_{h}(V^{*}_{h+1},P_{h}(s,a))-\rho_{h}(V^{*}_{h+1},\hat{P}^{k}_{h}(s,a))$
$\displaystyle\leq
L_{\infty}(\rho_{h},H-h)\left\lVert(V^{*}_{h+1},P_{h}(s,a))-\left(V^{*}_{h+1},\hat{P}^{k}_{h}(s,a)\right)\right\rVert_{\infty}$
$\displaystyle\leq L_{\infty}(\rho_{h},H-h)\left\lVert
P_{h}(s,a)-\hat{P}^{k}_{h}(s,a)\right\rVert_{1}$ $\displaystyle\leq
L_{\infty}(\rho_{h},H-h)\sqrt{\frac{2S}{(N^{k}_{h}(s,a)\vee 1)}\iota},$

where the second inequality is due to Fact 6, the third inequality is due to
Lemma 3.

##### Step 2: regret decomposition.

We introduce the key technical lemma here.

######  Lemma 6.

Let $(x,P)$ and $(y,P)$ be two discrete distributions, where
$x=(x_{1},\cdots,x_{n})$ and $y=(y_{1},\cdots,y_{n})$. It holds that

$\left\lVert(x,P)-(y,P)\right\rVert_{1}\leq\sum_{i\in[n]}P_{i}\left\lvert
x_{i}-y_{i}\right\rvert.$

###### Proof.

By the definition of Wasserstein distance between two discrete distributions,
we have

$\displaystyle\left\lVert F-G\right\rVert_{1}$
$\displaystyle=\inf_{\sum_{j}\lambda_{i,j}=P_{i},\sum_{i}\lambda_{i,j}=P_{j}}\sum_{i}\sum_{j}\lambda_{i,j}\left\lvert
x_{i}-y_{j}\right\rvert$
$\displaystyle\leq\sum_{i}\sum_{j}\delta_{i,j}P_{i}\left\lvert
x_{i}-y_{j}\right\rvert$
$\displaystyle=\sum_{i}P_{i}\sum_{j}\delta_{i,j}\left\lvert
x_{i}-y_{i}\right\rvert$ $\displaystyle=\sum_{i}P_{i}\left\lvert
x_{i}-y_{i}\right\rvert.$

The inequality holds since $\\{\delta_{i,j}P_{i}\\}_{i,j}$ is a valid coupling

$\sum_{j}\delta_{i,j}P_{i}=P_{i},\ \sum_{i}\delta_{i,j}P_{i}=P_{j}.$

∎

We define $\Delta^{k}_{h}\triangleq
V^{k}_{h}-V_{h}^{\pi^{k}}\in[-(H+1-h),H+1-h]^{\mathcal{S}}$ and
$\delta^{k}_{h}\triangleq\Delta^{k}_{h}(s^{k}_{h})$. For any $(s,h)$ and any
$\pi$, we let $P^{\pi}_{h}(\cdot|s)\triangleq P_{h}(\cdot|s,\pi_{h}(s))$. The
regret can be bounded as

$\displaystyle\text{Regret}(K)$
$\displaystyle=\sum^{K}_{k=1}V^{*}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})=\sum^{K}_{k=1}V^{*}_{1}(s^{k}_{1})-V^{k}_{1}(s^{k}_{1})+V^{k}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})$
$\displaystyle\leq\sum^{K}_{k=1}V^{k}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})=\sum^{K}_{k=1}\delta^{k}_{1}.$

For simplicity, we write $r^{k}_{h}\triangleq
r_{h}(s^{k}_{h},\pi^{k}_{h}(s^{k}_{h}))$, $b^{k}_{h}\triangleq
b^{k}_{h}(s^{k}_{h},\pi^{k}_{h}(s^{k}_{h}))$, $N^{k}_{h}\triangleq
N^{k}_{h}(s^{k}_{h},\pi^{k}_{h}(s^{k}_{h}))$ and
$\hat{P}^{k}_{h}(s^{k}_{h})\triangleq\hat{P}^{k}_{h}(s^{k}_{h},\pi^{k}_{h}(s^{k}_{h}))$.
For any $h\in[H-1]$, we decompose $\delta^{k}_{h}$ as follows

$\displaystyle\delta^{k}_{h}$
$\displaystyle=\rho_{h}\left(V^{k}_{h+1},\hat{P}^{k}_{h}(s^{k}_{h})\right)+b^{k}_{h}-\rho_{h}\left(V^{\pi^{k}}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)$
$\displaystyle=\underbrace{\rho_{h}\left(V^{k}_{h+1},\hat{P}^{k}_{h}(s^{k}_{h})\right)-\rho_{h}\left(V^{k}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)}_{(a)}+\underbrace{\rho_{h}\left(V^{k}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)-\rho_{h}\left(V^{\pi^{k}}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)}_{(b)}+b^{k}_{h}.$

Using the Lipschitz property of $\rho_{h}$,

$\displaystyle(a)$ $\displaystyle\leq
L_{\infty}(\rho_{h},H-h)\left\lVert\left(V^{k}_{h+1},\hat{P}^{k}_{h}(s^{k}_{h})\right)-\left(V^{k}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)\right\rVert_{\infty}$
$\displaystyle\leq
L_{\infty}(\rho_{h},H-h)\left\lVert\hat{P}^{k}_{h}(s^{k}_{h})-P^{\pi^{k}}_{h}(s^{k}_{h})\right\rVert_{1}$
$\displaystyle\leq L_{\infty}(\rho_{h},H-h)\sqrt{\frac{2S}{N^{k}_{h}\vee
1}\iota}.$

Applying Lemma 6 yields that

$\displaystyle(b)$ $\displaystyle\leq
L_{1}(\rho_{h},H-h)\left\lVert\left(V^{k}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)-\left(V^{\pi^{k}}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)\right\rVert_{1}$
$\displaystyle\leq
L_{1}(\rho_{h},H-h)\sum_{s^{\prime}\in\mathcal{S}}P^{\pi^{k}}_{h}(s^{\prime}|s^{k}_{h})\left\lvert
V^{k}_{h+1}(s^{\prime})-V^{\pi^{k}}_{h+1}(s^{\prime})\right\rvert$
$\displaystyle=L_{1}(\rho_{h},H-h)\sum_{s^{\prime}\in\mathcal{S}}P^{\pi^{k}}_{h}(s^{\prime}|s^{k}_{h})\left(V^{k}_{h+1}(s^{\prime})-V^{\pi^{k}}_{h+1}(s^{\prime})\right)$
$\displaystyle=L_{1}(\rho_{h},H-h)\left[P^{\pi^{k}}_{h}\Delta^{k}_{h+1}\right](s^{k}_{h})$
$\displaystyle\triangleq
L_{1}(\rho_{h},H-h)(\epsilon^{k}_{h}+\delta^{k}_{h+1}),$

where
$\epsilon^{k}_{h}\triangleq[P^{\pi^{k}}_{h}\Delta^{k}_{h+1}](s^{k}_{h})-\Delta^{k}_{h+1}(s^{k}_{h+1})$
is a martingale difference sequence with $\epsilon^{k}_{h}\in[-2(H-h),2(H-h)]$
a.s. for all $(k,h)\in[K]\times[H]$. The first equality is due to that
$V^{k}_{h+1}(s^{\prime})\geq V^{*}_{h+1}(s^{\prime})\geq
V^{\pi^{k}}_{h+1}(s^{\prime})$ for all $s^{\prime}$.

Now we can bound $\delta^{k}_{h}$ recursively

$\displaystyle\delta^{k}_{h}\leq
L_{\infty}(\rho_{h},H-h)\sqrt{\frac{2S}{N^{k}_{h}\vee
1}\iota}+L_{1}(\rho_{h},H-h)(\epsilon^{k}_{h}+\delta^{k}_{h+1})+L_{\infty}(\rho_{h},H-h)\sqrt{\frac{\iota}{2(N^{k}_{h}\vee
1)}}$ $\displaystyle\leq
2L_{\infty}(\rho_{h},H-h)e^{k}_{h}+L_{1}(\rho_{h},H-h)(\epsilon^{k}_{h}+\delta^{k}_{h+1}),$

where we define $e^{k}_{h}\triangleq\sqrt{\frac{2S}{N^{k}_{h}\vee 1}\iota}$ in
the last line. Repeating the procedure, we obtain

$\displaystyle\delta^{k}_{1}$ $\displaystyle\leq
2\sum^{H-1}_{h=1}L_{\infty}(\rho_{h},H-h)\prod^{h-1}_{i=1}L_{1}(\rho_{i},H-i)e^{k}_{h}+\sum^{H-1}_{h=1}\prod^{h}_{i=1}L_{1}(\rho_{i},H-i)\epsilon^{k}_{h}+\prod^{H-1}_{h=1}L_{1}(\rho_{h},H-h)\delta^{k}_{H}$
$\displaystyle=2\sum^{H-1}_{h=1}L_{\infty}(\rho_{h},H-h)\prod^{h-1}_{i=1}L_{1}(\rho_{i},H-i)e^{k}_{h}+\sum^{H-1}_{h=1}\prod^{h}_{i=1}L_{1}(\rho_{i},H-i)\epsilon^{k}_{h},$

where the last step is because
$\delta^{k}_{H}=Q^{k}_{H}-Q^{*}_{H}=r_{H}-r_{H}=0$.

##### Step 3: putting together.

The total regret is bounded as

$\displaystyle\text{Regret}(K)\leq\sum_{k\in[K]}\delta^{k}_{1}\leq
2\sum^{H-1}_{h=1}L_{\infty}(\rho_{h},H-h)\prod^{h-1}_{i=1}L_{1}(\rho_{i},H-i)\sum_{k=1}^{K}e^{k}_{h}+\sum_{k=1}^{K}\sum^{H-1}_{h=1}\prod^{h}_{i=1}L_{1}(\rho_{i},H-i)\epsilon^{k}_{h}.$

The first term can be bounded as

$\displaystyle
2\sum^{H-1}_{h=1}L_{\infty}(\rho_{h},H-h)\prod^{h-1}_{i=1}L_{1}(\rho_{i},H-i)\sum_{k=1}^{K}e^{k}_{h}$
$\displaystyle=2\sum^{H-1}_{h=1}L_{\infty}(\rho_{h},H-h)\prod^{h-1}_{i=1}L_{1}(\rho_{i},H-i)\sum_{k=1}^{K}\sqrt{\frac{2S}{N^{k}_{h}\vee
1}\iota}$ $\displaystyle\leq
4\sum^{H-1}_{h=1}L_{\infty}(\rho_{h},H-h)\prod^{h-1}_{i=1}L_{1}(\rho_{i},H-i)\sqrt{S^{2}AK\iota}$
$\displaystyle\triangleq
4\sum^{H-1}_{h=1}L_{\infty,h}\prod^{h-1}_{i=1}L_{1,i}\sqrt{S^{2}AK\iota}$
$\displaystyle\triangleq
4\sum^{H-1}_{h=1}L_{\infty,h}\tilde{L}_{1,h-1}\sqrt{S^{2}AK\iota},$

where we denote by $L_{\infty,h}=L_{\infty}(\rho_{h},H-h)$ and
$\tilde{L}_{1,h-1}=\prod^{h-1}_{i=1}L_{1,i}$ for simplicity. We can bound the
second term by Azuma-Hoeffding inequality: with probability at least
$1-\delta^{\prime}$, the following holds

$\displaystyle\sum_{k=1}^{K}\sum^{H-1}_{h=1}\prod^{h}_{i=1}L_{1}(\rho_{i},H-i)\epsilon^{k}_{h}$
$\displaystyle=\sum_{k=1}^{K}\sum^{H-1}_{h=1}\tilde{L}_{1,h}\epsilon^{k}_{h}\leq\sqrt{\sum_{k=1}^{K}\sum^{H-1}_{h=1}\frac{(2(H-h)\tilde{L}_{1,h})^{2}}{2}\log(1/\delta^{\prime})}$
$\displaystyle=\sqrt{\sum^{H-1}_{h=1}(H-h)^{2}\tilde{L}^{2}_{1,h}}\sqrt{2K\log(1/\delta^{\prime})}$

Using a union bound and let $\delta=\delta^{\prime}=\frac{\tilde{\delta}}{2}$,
we have that with probability at least $1-\delta$,

$\displaystyle\text{Regret}(K)$ $\displaystyle\leq
4\sum^{H-1}_{h=1}L_{\infty,h}\tilde{L}_{1,h-1}\sqrt{S^{2}AK\iota}+\sqrt{\sum^{H-1}_{h=1}(H-h)^{2}\tilde{L}^{2}_{1,h}}\sqrt{2K\log(1/\delta^{\prime})}$
$\displaystyle=\tilde{\mathcal{O}}\left(\sum^{H-1}_{h=1}L_{\infty,h}\tilde{L}_{1,h-1}\sqrt{S^{2}AK}\right).$

The equality is due to that

$\displaystyle\sum^{H-1}_{h=1}L_{\infty,h}\tilde{L}_{1,h-1}$
$\displaystyle\geq\sqrt{\sum^{H-1}_{h=1}L^{2}_{\infty,h}\tilde{L}^{2}_{1,h-1}}=\sqrt{\sum^{H-1}_{h=1}((H-h)L_{1,h})^{2}\tilde{L}^{2}_{1,h-1}}$
$\displaystyle=\sqrt{\sum^{H-1}_{h=1}(H-h)^{2}\tilde{L}^{2}_{1,h}},$

where the first inequality comes from the non-negativity of
$L_{\infty,h}\tilde{L}_{1,h-1}$, and the first equality is due to the choice
$L_{\infty,h}=L_{1,h}(H-h)$.

######  Remark 5.

The following statement is not true

$\left\lVert(x,P)-(y,P)\right\rVert_{1}\leq\left\lvert\sum_{i\in[n]}P_{i}(x_{i}-y_{i})\right\rvert.$

Consider the case that $(x,P)=((0,1),(\frac{1}{3},\frac{2}{3})$ and
$(y,P)=((\frac{1}{3},\frac{5}{6}),(\frac{1}{3},\frac{2}{3}))$. A simple
calculation yields that $\sum_{i\in[n]}P_{i}(x_{i}-y_{i})=0$.

####  D.1.2 Proof for Algorithm 2

##### Step 1: verify optimism.

######  Lemma 7 (Optimistic value function).

Conditioned on event $\mathcal{G}_{\delta}$, the sequence
$\\{V^{k}_{1}(s^{k}_{1})\\}_{k\in[K]}$ produced by Algorithm 2 satisfies
$V^{k}_{1}(s^{k}_{1})\geq V^{*}_{1}(s^{k}_{1}),\forall k\in[K]$.

###### Proof.

The proof follows from Appendix C. ∎

##### Step 2: regret decomposition.

The regret can be bounded as

$\displaystyle\text{Regret}(K)$
$\displaystyle=\sum^{K}_{k=1}V^{*}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})\leq\sum^{K}_{k=1}V^{k}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})=\sum^{K}_{k=1}\delta^{k}_{1}.$

For any $h\in[H-1]$, we decompose $\delta^{k}_{h}$ as follows

$\displaystyle\delta^{k}_{h}$
$\displaystyle=\rho_{h}\left(V^{k}_{h+1},\tilde{P}^{k}_{h}(s^{k}_{h})\right)-\rho_{h}\left(V^{\pi^{k}}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)$
$\displaystyle=\underbrace{\rho_{h}\left(V^{k}_{h+1},\tilde{P}^{k}_{h}(s^{k}_{h})\right)-\rho_{h}\left(V^{k}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)}_{(a)}+\underbrace{\rho_{h}\left(V^{k}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)-\rho_{h}\left(V^{\pi^{k}}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)}_{(b)}.$

Using the Lipschitz property of $\rho_{h}$,

$\displaystyle(a)$ $\displaystyle\leq
L_{\infty}(\rho_{h},H-h)\left\lVert\left(V^{k}_{h+1},\tilde{P}^{k}_{h}(s^{k}_{h})\right)-\left(V^{k}_{h+1},P^{\pi^{k}}_{h}(s^{k}_{h})\right)\right\rVert_{\infty}$
$\displaystyle\leq
L_{\infty}(\rho_{h},H-h)\left\lVert\tilde{P}^{k}_{h}(s^{k}_{h})-P^{\pi^{k}}_{h}(s^{k}_{h})\right\rVert_{1}$
$\displaystyle\leq
L_{\infty}(\rho_{h},H-h)\left(\left\lVert\tilde{P}^{k}_{h}(s^{k}_{h})-\hat{P}^{\pi^{k}}_{h}(s^{k}_{h})\right\rVert_{1}+\left\lVert\hat{P}^{k}_{h}(s^{k}_{h})-P^{\pi^{k}}_{h}(s^{k}_{h})\right\rVert_{1}\right)$
$\displaystyle\leq 2L_{\infty}(\rho_{h},H-h)\sqrt{\frac{2S}{N^{k}_{h}\vee
1}\iota}.$

Using arguments similar to the proof for Algorithm 1

$\displaystyle(b)$ $\displaystyle\leq
L_{1}(\rho_{h},H-h)(\epsilon^{k}_{h}+\delta^{k}_{h+1}),$

Now we can bound $\delta^{k}_{h}$ recursively

$\displaystyle\delta^{k}_{h}$ $\displaystyle\leq
2L_{\infty}(\rho_{h},H-h)\sqrt{\frac{2S}{N^{k}_{h}\vee
1}\iota}+L_{1}(\rho_{h},H-h)(\epsilon^{k}_{h}+\delta^{k}_{h+1})$
$\displaystyle=2L_{\infty}(\rho_{h},H-h)e^{k}_{h}+L_{1}(\rho_{h},H-h)(\epsilon^{k}_{h}+\delta^{k}_{h+1}).$

Repeating the procedure, we obtain

$\displaystyle\delta^{k}_{1}$ $\displaystyle\leq
2\sum^{H-1}_{h=1}L_{\infty}(\rho_{h},H-h)\prod^{h-1}_{i=1}L_{1}(\rho_{i},H-i)e^{k}_{h}+\sum^{H-1}_{h=1}\prod^{h}_{i=1}L_{1}(\rho_{i},H-i)\epsilon^{k}_{h}.$

##### Step 3: putting together.

The results follows from analogous arguments of the proof for Algorithm 1.

###  D.2 Gap-dependent Regret Upper Bound

##### Step 1: regret decomposition.

The regret of each episode can be rewritten as the expected sum of sub-
optimality gaps for each action:

$\displaystyle(V^{*}_{1}-V^{\pi^{k}}_{1})(s^{k}_{1})$
$\displaystyle=V^{*}_{1}(s^{k}_{1})-Q^{*}_{1}(s^{k}_{1},a^{k}_{1})+(Q^{*}_{1}-Q^{\pi^{k}}_{1})(s^{k}_{1},a^{k}_{1})$
$\displaystyle=\Delta_{1}(s^{k}_{1},a^{k}_{1})+[P_{2}(V^{*}_{2}-V^{\pi^{k}}_{2})](s^{k}_{2},a^{k}_{2})$
$\displaystyle=\cdots=\mathbb{E}\left[\sum_{h=1}^{H}\Delta_{h}(s^{k}_{h},a^{k}_{h})\right].$

##### Step 2: optimism.

######  Lemma 8.

With probability at least $1-\delta$, the following event holds

$0\leq(Q^{k}_{h}-Q^{*}_{h})(s,a)\leq
2b^{k}_{h}(s,a)+L_{1,h}[P_{h}(V^{k}_{h+1}-V^{*}_{h+1})](s,a).$

###### Proof.

$\displaystyle(Q^{k}_{h}-Q^{*}_{h})(s,a)=r_{h}(s,a)+\rho_{h}\left(V^{k}_{h+1},\hat{P}^{k}_{h}(s,a)\right)+b^{k}_{h}(s,a)-r_{h}(s,a)-\rho_{h}\left(V^{*}_{h+1},P_{h}(s,a)\right)$
$\displaystyle=\underbrace{\rho_{h}\left(V^{k}_{h+1},\hat{P}^{k}_{h}(s,a)\right)-\rho_{h}\left(V^{k}_{h+1},P_{h}(s,a)\right)}_{(a)}+\underbrace{\rho_{h}\left(V^{k}_{h+1},P_{h}(s,a)\right)-\rho_{h}\left(V^{*}_{h+1},P_{h}(s,a)\right)}_{(b)}+b^{k}_{h}(s,a)$
$\displaystyle\leq
L_{\infty,h}\left\lVert(V^{k}_{h+1},\hat{P}^{k}_{h}(s,a))-(V^{k}_{h+1},P_{h}(s,a))\right\rVert_{\infty}+L_{1,h}\left\lVert(V^{k}_{h+1},P_{h}(s,a))-(V^{*}_{h+1},P_{h}(s,a))\right\rVert_{1}+b^{k}_{h}(s,a)$
$\displaystyle\leq
L_{\infty,h}\left\lVert\hat{P}^{k}_{h}(s,a)-V^{k}_{h+1},P_{h}(s,a)\right\rVert_{1}+L_{1,h}[P_{h}(V^{k}_{h+1}-V^{*}_{h+1})](s,a)+b^{k}_{h}(s,a)$
$\displaystyle\leq
2b^{k}_{h}(s,a)+L_{1,h}[P_{h}(V^{k}_{h+1}-V^{*}_{h+1})](s,a)$

∎

##### Step 3: bound number of steps in each interval

######  Lemma 9.

For any $n\in[N]$,

$C^{n}\triangleq\left\lvert\left\\{(k,h):(Q^{k}_{h}-Q^{*}_{h})(s^{k}_{h},a^{k}_{h})\in[2^{n-1}\Delta_{\text{min}},2^{n}\Delta_{\text{min}})\right\\}\right\rvert\leq\mathcal{O}\left(\frac{HS^{2}A\iota\left(\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{\infty,h^{\prime}}\right)^{2}}{4^{n}\Delta_{\text{min}}^{2}}\right).$

###### Proof.

For every $n\in[N]$, $h\in[H]$, define

$\displaystyle w^{(n,h)}_{k}$
$\displaystyle\triangleq\mathbb{I}\left\\{(Q^{k}_{h}-Q^{*}_{h})(s^{k}_{h},a^{k}_{h})\in[2^{n-1}\Delta_{\text{min}},2^{n}\Delta_{\text{min}})\right\\}$
$\displaystyle C^{(n,h)}$
$\displaystyle\triangleq\sum_{k=1}^{K}w^{(n,h)}_{k}.$

Observe that $w^{(n,h)}_{k}\leq 1$ and $(w^{(n,h)}_{k})^{2}=w^{(n,h)}_{k}$ .
Now we bound
$\sum_{k=1}^{K}w^{(n,h)}_{k}(Q^{k}_{h}-Q^{*}_{h})(s^{k}_{h},a^{k}_{h})$ from
both sides. On the one hand, by Lemma ,

$\displaystyle\sum_{k=1}^{K}w^{(n,h)}_{k}(Q^{k}_{h}-Q^{*}_{h})(s^{k}_{h},a^{k}_{h})$
$\displaystyle\leq 4\sqrt{S^{2}A\iota
C^{(n,h)}}\cdot\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{\infty,h^{\prime}}+\sqrt{2C^{(n,h)}\log\frac{1}{\delta^{\prime}}}\cdot\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{1,h^{\prime}}(H-h^{\prime})$
$\displaystyle=\mathcal{O}\left(\sqrt{S^{2}A\iota
C^{(n,h)}}\cdot\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{\infty,h^{\prime}}\right).$

On the other hand, by the definition of $w^{(n,h)}_{k}$,

$\sum_{k=1}^{K}w^{(n,h)}_{k}(Q^{k}_{h}-Q^{*}_{h})(s^{k}_{h},a^{k}_{h})\geq\sum_{k=1}^{K}w^{(n,h)}_{k}2^{n-1}\Delta_{\text{min}}=2^{n-1}\Delta_{\text{min}}\cdot
C^{(n,h)}.$

Combining the two inequalities, we obtain

$C^{(n,h)}\leq\mathcal{O}\left(\frac{S^{2}A\iota\left(\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{\infty,h^{\prime}}\right)^{2}}{4^{n}\Delta_{\text{min}}^{2}}\right)$

Finally, we have

$C^{(n)}=\sum_{h=1}^{H}C^{(n,h)}\leq\mathcal{O}\left(\frac{S^{2}A\iota\sum_{h=1}^{H}\left(\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{\infty,h^{\prime}}\right)^{2}}{4^{n}\Delta_{\text{min}}^{2}}\right)\leq\mathcal{O}\left(\frac{S^{2}A\iota
H\left(\sum_{h^{\prime}=1}^{H-1}\tilde{L}_{1,h^{\prime}-1}L_{\infty,h^{\prime}}\right)^{2}}{4^{n}\Delta_{\text{min}}^{2}}\right)$

∎

######  Lemma 10.

For any positive sequence $\\{w_{k}\\}_{k\in[K]}$, it holds that for any
$h\in[H]$

$\sum_{k=1}^{K}w_{k}(Q^{k}_{h}-Q^{*}_{h})(s^{k}_{h},a^{k}_{h})\leq
4\sqrt{wS^{2}A\iota\sum^{K}_{k=1}w_{k}}\cdot\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{\infty,h^{\prime}}+\sqrt{2\sum_{k=1}^{K}w^{2}_{k}\log\frac{1}{\delta^{\prime}}}\cdot\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{1,h^{\prime}}(H-h^{\prime}).$

###### Proof.

By Lemma 5,

$\displaystyle\sum_{k=1}^{K}w_{k}(Q^{k}_{h}-Q^{*}_{h})(s^{k}_{h},a^{k}_{h})$
$\displaystyle\leq\sum_{k=1}^{K}w_{k}\left(2L_{\infty,h}\sqrt{\frac{2S\iota}{N^{k}_{h}}}+L_{1,h}[P_{h}(V^{k}_{h+1}-V^{*}_{h+1})](s^{k}_{h},a^{k}_{h})\right)$
$\displaystyle=\underbrace{2L_{\infty,h}\sum_{k=1}^{K}w_{k}\sqrt{\frac{2S\iota}{N^{k}_{h}\vee
1}}}_{(a)}+\underbrace{L_{1,h}\sum_{k=1}^{K}w_{k}\epsilon^{k}_{h}}_{(b)}+L_{1,h}\sum_{k=1}^{K}w_{k}(V^{k}_{h+1}-V^{*}_{h+1})(s^{k}_{h+1})$
$\displaystyle\leq(a)+(b)+L_{1,h}\sum_{k=1}^{K}w_{k}(Q^{k}_{h+1}-Q^{*}_{h+1})(s^{k}_{h+1},a^{k}_{h+1}),$

where
$\epsilon^{k}_{h}\triangleq[P_{h}(V^{k}_{h+1}-V^{*}_{h+1})](s^{k}_{h},a^{k}_{h})-(V^{k}_{h+1}-V^{*}_{h+1})](s^{k}_{h+1})\in[-2(H-h),2(H-h)]$
is a martingale difference sequence w.r.t. $\mathcal{F}^{k}_{h}$ for any
$h\in[H]$, i.e.,
$\mathbb{E}\left[\epsilon^{k}_{h}|\mathcal{F}^{k}_{h}\right]=0$. Define
$k(s,a,t)\triangleq\min\\{k:N^{k}_{h}(s,a)\geq t\\}$ the episode when $(s,a)$
is visited $t$ times at step $h$. We can bound term $(a)$ as

$\displaystyle(a)=2L_{\infty,h}\sum_{k=1}^{K}w_{k}\sqrt{\frac{2S\iota}{N^{k}_{h}}}$
$\displaystyle=2L_{\infty,h}\sqrt{2S\iota}\sum_{s,a}\sum_{k=1}^{K}\mathbb{I}\\{(s^{k}_{h},a^{k}_{h})=(s,a)\\}\frac{w_{k}}{\sqrt{N^{k}_{h}(s,a)\vee
1}}$
$\displaystyle=2L_{\infty,h}\sqrt{2S\iota}\sum_{s,a}\sum_{t=1}^{N^{K}_{h}(s,a)}\frac{w_{k(s,a,t)}}{\sqrt{t}}$
$\displaystyle\leq
2L_{\infty,h}\sqrt{2S\iota}\sum_{s,a}\sum_{t=1}^{C_{s,a}/w}\frac{w}{\sqrt{t}}$
$\displaystyle\leq 4L_{\infty,h}\sqrt{S\iota}\sum_{s,a}\sqrt{C_{s,a}w}$
$\displaystyle\leq 4L_{\infty,h}\sqrt{wS^{2}A\iota\sum^{K}_{k=1}w_{k}},$

where $C_{s,a}\triangleq\sum_{t=1}^{N^{K}_{h}(s,a)}w_{k(s,a,t)}$ and
$w_{k}\leq w$ for any $k$, and the last inequality follows from that
$\sum_{s,a}C_{s,a}=\sum_{s,a}\sum_{t=1}^{N^{K}_{h}(s,a)}w_{k(s,a,t)}=\sum^{K}_{k=1}w_{k}$.

Since $\\{\epsilon^{k}_{h}\\}_{k\in[K]}$ is a MDS with $|\epsilon^{k}_{h}|\leq
2(H-h)$, we can bound term $(b)$ by Azuma-Hoeffding inequality: w.p.
$1-\delta^{\prime}$

$\displaystyle(b)=L_{1,h}\sum_{k=1}^{K}w_{k}\epsilon^{k}_{h}\leq
L_{1,h}(H-h)\sqrt{2\sum_{k=1}^{K}w^{2}_{k}\log\frac{1}{\delta^{\prime}}}.$

Thus we can get a recursive bound

$\displaystyle\sum_{k=1}^{K}w_{k}(Q^{k}_{h}-Q^{*}_{h})(s^{k}_{h},a^{k}_{h})\leq
4L_{\infty,h}\sqrt{wS^{2}A\iota\sum^{K}_{k=1}w_{k}}+L_{1,h}(H-h)\sqrt{2\sum_{k=1}^{K}w^{2}_{k}\log\frac{1}{\delta^{\prime}}}$
$\displaystyle+L_{1,h}\sum_{k=1}^{K}w_{k}(Q^{k}_{h+1}-Q^{*}_{h+1})(s^{k}_{h+1},a^{k}_{h+1}).$

Unrolling the inequality yields

$\displaystyle\sum_{k=1}^{K}w_{k}(Q^{k}_{h}-Q^{*}_{h})(s^{k}_{h},a^{k}_{h})\leq\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}\left(4L_{\infty,h^{\prime}}\sqrt{wS^{2}A\iota\sum^{K}_{k=1}w_{k}}+L_{1,h^{\prime}}(H-h^{\prime})\sqrt{2\sum_{k=1}^{K}w^{2}_{k}\log\frac{1}{\delta^{\prime}}}\right)$
$\displaystyle=4\sqrt{wS^{2}A\iota\sum^{K}_{k=1}w_{k}}\cdot\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{\infty,h^{\prime}}+\sqrt{2\sum_{k=1}^{K}w^{2}_{k}\log\frac{1}{\delta^{\prime}}}\cdot\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{1,h^{\prime}}(H-h^{\prime})$

∎

##### Step 4: Bound the regret

Denote by $\tau\triangleq(s^{k}_{h},a^{k}_{h})_{k,h}$ the trajectory. Define
$\text{clip}[x|\delta]\triangleq x\mathbb{I}\\{x\geq\delta\\}$. Observe that

$V^{*}_{h}(s^{k}_{h})=\max_{a}Q^{*}_{h}(s^{k}_{h},a)\leq\max_{a}Q^{k}_{h}(s^{k}_{h},a)=Q^{k}_{h}(s^{k}_{h},a^{k}_{h}),$

thus we get

$\Delta_{h}(s^{k}_{h},a^{k}_{h})=\text{clip}[V^{*}_{h}(s^{k}_{h})-Q^{*}_{h}(s^{k}_{h},a^{k}_{h})|\Delta_{\text{min}}]\leq\text{clip}[(Q^{k}_{h}-Q^{*}_{h})(s^{k}_{h},a^{k}_{h})|\Delta_{\text{min}}].$
$\displaystyle\text{Regret}(K)$
$\displaystyle=\mathbb{E}\left[\sum_{k=1}^{K}\sum_{h=1}^{H}\Delta_{h}(s^{k}_{h},a^{k}_{h})\right]=\sum\mathbb{P}(\tau)\sum_{k=1}^{K}\sum_{h=1}^{H}\Delta_{h}(s^{k}_{h},a^{k}_{h}|\tau)$
$\displaystyle\leq\sum_{\tau\in
E}\mathbb{P}(\tau)\sum_{k=1}^{K}\sum_{h=1}^{H}\text{clip}[(Q^{k}_{h}-Q^{*}_{h})(s^{k}_{h},a^{k}_{h}|\tau)|\Delta_{\text{min}}]+\sum_{\tau\in
E^{c}}\mathbb{P}(\tau)KH^{2}$
$\displaystyle\leq\mathbb{P}(E)\sum_{n=1}^{N}2^{n}\Delta_{\text{min}}C^{(n)}+\mathbb{P}(E^{c})KH^{2}$
$\displaystyle\leq\sum_{n=1}^{N}\mathcal{O}\left(\frac{HS^{2}A\iota\left(\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{\infty,h^{\prime}}\right)^{2}}{2^{n}\Delta_{\text{min}}}\right)+H$
$\displaystyle=\mathcal{O}\left(\frac{HS^{2}A\iota\left(\sum_{h^{\prime}=h}^{H-1}\prod_{i=h}^{h^{\prime}-1}L_{1,i}L_{\infty,h^{\prime}}\right)^{2}}{\Delta_{\text{min}}}\right).$

##  Appendix E Proofs of Regret Lower Bounds

###  E.1 Minimax Lower Bound

We make the following assumption Domingues et al., (2021).

######  Assumption 2.

Assume $S\geq 6,A\geq 2$, and there exists an integer $d$ such that
$S=3+\frac{A^{d}-1}{A-1}$. We further assume that $H\geq 3d$ and
$\bar{H}\triangleq\frac{H}{3}\geq 1$.

######  Theorem 5.

Assume Assumption 2 holds. For any algorithm $\mathscr{A}$, there exists an
MDP $\mathcal{M}_{\mathscr{A}}$ such that for sufficiently large $K$

$\mathbb{E}[\text{Regret}(\mathscr{A},\mathcal{M}_{\mathscr{A}},K)]\geq\frac{\sqrt{p}}{27\sqrt{6}}c_{\rho,1}H\sqrt{SAT}.$

##### Step 1.

Fix an arbitrary algorithm $\mathscr{A}$. We introduce three types of special
states for the hard MDP class: a waiting state $s_{w}$ where the agent starts
and may stay until stage $\bar{H}$, after that it has to leave; a good state
$s_{g}$, which is absorbing and is the only rewarding state; a bad state
$s_{b}$ that is absorbing and provides no reward. The rest of $S-3$ states are
part of a $A$-ary tree of depth $d-1$. The agent can only arrive $s_{w}$ from
the root node $s_{root}$ and can only reach $s_{g}$ and $s_{b}$ from the
leaves of the tree. Let $\bar{H}\in[H-d]$ be the first parameter of the MDP
class. We define $\tilde{H}:=\bar{H}+d+1$ and $H^{\prime}:=H+1-\tilde{H}$. We
denote by $\mathcal{L}:=\\{s_{1},s_{2},...,s_{\bar{L}}\\}$ the set of
$\bar{L}$ leaves of the tree. For each
$u^{*}:=\left(h^{*},\ell^{*},a^{*}\right)\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}$,
we define an MDP $\mathcal{M}_{u^{*}}$ as follows. The transitions in the tree
are deterministic, hence taking action $a$ in state $s$ results in the $a$-th
child of node $s$. The transitions from $s_{w}$ are defined as

$P_{h}\left(s_{\mathrm{w}}\mid
s_{\mathrm{w}},a\right):=\mathbb{I}\left\\{a=a_{\mathrm{w}},h\leq\bar{H}\right\\}\quad\text{
and }\quad P_{h}\left(s_{\text{root }}\mid
s_{\mathrm{w}},a\right):=1-P_{h}\left(s_{\mathrm{w}}\mid
s_{\mathrm{w}},a\right).$

The transitions from any leaf $s_{i}\in\mathcal{L}$ are specified as

$P_{h}\left(s_{g}\mid
s_{i},a\right):=p+\Delta_{u^{*}}\left(h,s_{i},a\right)\quad\text{ and }\quad
P_{h}\left(s_{b}\mid
s_{i},a\right):=1-p-\Delta_{u^{*}}\left(h,s_{i},a\right),$

where
$\Delta_{u^{*}}\left(h,s_{i},a\right):=\epsilon\mathbb{I}\\{(h,s_{i},a)=(h^{*},s_{\ell^{*}},a^{*})\\}$
for some constants $p\in[0,1]$ and $\epsilon\in[0,\min(1-p,p)]$ to be
determined later. $p$ and $\epsilon$ are the second and third parameters of
the MDP class. Observe that $s_{g}$ and $s_{b}$ are absorbing, therefore we
have $\forall a,P_{h}\left(s_{g}\mid s_{g},a\right):=P_{h}\left(s_{b}\mid
s_{b},a\right):=1$. The reward is a deterministic function of the state

$r_{h}(s,a):=\mathbb{I}\\{s=s_{g},h\geq\tilde{H}\\}.$

Finally, we define a reference MDP $\mathcal{M}_{0}$ which differs from the
previous MDP instances only in that $\Delta_{0}(h,s_{i},a):=0$ for all
$(h,s_{i},a)$. For each $\epsilon,p$ and $\bar{H}$, we define the MDP class

$\mathcal{C}_{\bar{H},p,\epsilon}:=\mathcal{M}_{0}\cup\\{\mathcal{M}_{u^{*}}\\}_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}.$

For an MDP $\mathcal{M}_{u^{*}}$, the optimal policy
$\pi^{*,\mathcal{M}_{u^{*}}}$ starts to traverse the tree at step $h^{*}-d$
then chooses to reach the leaf $s_{l^{*}}$ and performs action $a^{*}$. The
optimal value in any of these MDPs is the same

$\displaystyle V^{*,\mathcal{M}_{u^{*}}}_{1}$
$\displaystyle=V^{*,\mathcal{M}_{u^{*}}}_{h^{*}}(s_{l^{*}})=Q^{*,\mathcal{M}_{u^{*}}}_{h^{*}}(s_{l^{*}},a^{*})=r_{h}(s_{l^{*}},a^{*})+\rho_{h^{*}}(V^{*,\mathcal{M}_{u^{*}}}_{h^{*}+1},P_{h}(s_{l^{*}},a^{*}))$
$\displaystyle=\rho_{h^{*}}((V^{*,\mathcal{M}_{u^{*}}}_{h^{*}+1}(s_{g}),V^{*,\mathcal{M}_{u^{*}}}_{h^{*}+1}(s_{b})),(p+\epsilon,1-p-\epsilon)).$

For simplicity, we may drop $\mathcal{M}_{u^{*}}$ from the notations. Notice
that the agent must be in either of the absorbing states at step
$h\geq\tilde{H}=\bar{H}+d+1$. Observe that
$V^{*,\mathcal{M}_{u^{*}}}_{H}(s_{g})=r_{H}(s_{g},a)=1$ since
$r_{h}(s_{g},a)=1$ for any $a$ and any $h\geq\tilde{H}$, and
$V^{*,\mathcal{M}_{u^{*}}}_{H}(s_{b})=0$. Thus we have:

$Q^{*,\mathcal{M}_{u^{*}}}_{H-1}(s_{g},a)=r_{H-1}(s_{g},a)+\rho_{H-1}((V^{*,\mathcal{M}_{u^{*}}}_{h^{*}+1}(s_{g}),V^{*,\mathcal{M}_{u^{*}}}_{h^{*}+1}(s_{b})),(1,0))=1+V^{*,\mathcal{M}_{u^{*}}}_{h^{*}+1}(s_{g})=2,\forall
a,$

where the second equality follows from that $\rho_{h}(c)=c$ for a
deterministic constant $c$. Therefore
$V^{*,\mathcal{M}_{u^{*}}}_{H-1}(s_{g})=2$. Similarly we can get
$V^{*,\mathcal{M}_{u^{*}}}_{H-1}(s_{b})=0$. It follows from inductions that
$V^{*,\mathcal{M}_{u^{*}}}_{h}(s_{g})=H+1-h$ and
$V^{*,\mathcal{M}_{u^{*}}}_{h}(s_{b})=0$ for $h\geq\tilde{H}$. Moreover,
observe that

$V^{*,\mathcal{M}_{u^{*}}}_{\tilde{H}-1}(s_{g})=0+\rho_{\tilde{H}-1}((V^{*,\mathcal{M}_{u^{*}}}_{\tilde{H}}(s_{g}),V^{*,\mathcal{M}_{u^{*}}}_{\tilde{H}}(s_{b})),(1,0))=V^{*,\mathcal{M}_{u^{*}}}_{\tilde{H}}(s_{g})=H+1-\tilde{H}=H^{\prime}$

and $V^{*,\mathcal{M}_{u^{*}}}_{\tilde{H}-1}(s_{b})=0$. Then
$V^{*,\mathcal{M}_{u^{*}}}_{h^{*}+1}(s_{g})=\cdots=V^{*,\mathcal{M}_{u^{*}}}_{\tilde{H}-1}(s_{g})=H^{\prime}$
and
$V^{*,\mathcal{M}_{u^{*}}}_{h^{*}+1}(s_{b})=\cdots=V^{*,\mathcal{M}_{u^{*}}}_{\tilde{H}-1}(s_{b})=0$.
Thus the optimal value

$\displaystyle V^{*,\mathcal{M}_{u^{*}}}_{1}$
$\displaystyle=\rho_{h^{*}}((V^{*,\mathcal{M}_{u^{*}}}_{h^{*}+1}(s_{g}),V^{*,\mathcal{M}_{u^{*}}}_{h^{*}+1}(s_{b})),(p+\epsilon,1-p-\epsilon))$
$\displaystyle=\rho_{h^{*}}((V^{*,\mathcal{M}_{u^{*}}}_{\tilde{H}}(s_{g}),V^{*,\mathcal{M}_{u^{*}}}_{\tilde{H}}(s_{b})),(p+\epsilon,1-p-\epsilon))$
$\displaystyle=\rho_{h^{*}}((H^{\prime},0),(p+\epsilon,1-p-\epsilon))$

Consider the case that policy $\pi^{k}\neq\pi^{*}$. Then we have
$(s^{k}_{h^{*}},a^{k}_{h^{*}})\neq(s_{l^{*}},a^{*})$. Analogously, we can get

$V^{\pi^{k}}_{h}(s_{g})=H+1-h,\ V^{*,\mathcal{M}_{u^{*}}}_{h}(s_{b})=0$

for $h\geq\tilde{H}$. Suppose $\pi^{k}$ arrives at the leaf node
$s^{k}_{l^{k}}$ in step $l^{k}\in[1+d,\tilde{H}-1]$, then
$V^{\pi^{k}}_{l^{k}+1}(s_{g})=\cdots=V^{\pi^{k}}_{\tilde{H}}(s_{g})=H+1-\tilde{H}=H^{\prime}$
and $V^{\pi^{k}}_{l^{k}+1}(s_{b})=\cdots=V^{\pi^{k}}_{\tilde{H}}(s_{b})=0$.
Since $P_{l^{k}}(s_{g}|s^{k}_{l^{k}},a^{k}_{h})=p$,

$\displaystyle
V^{\pi^{k}}_{1}=\rho_{l^{k}}((V^{\pi^{k}}_{l^{k}+1}(s_{g}),V^{\pi^{k}}_{l^{k}+1}(s_{b})),(p,1-p))=\rho_{l^{k}}((H^{\prime},0),(p,1-p))$

Denote by $x^{k}_{h}:=(s^{k}_{h},a^{k}_{h})$ for each $(k,h)$,
$x^{*}:=(s_{\ell^{*}},a^{*})$ and
$N_{K}(u^{*}):=\sum_{k=1}^{K}\mathbb{I}\\{x^{k}_{h^{*}}=x^{*}\\}$. It follows
that

$V^{\pi^{k}}_{1}=\mathbb{I}\\{x^{k}_{h^{*}}=x^{*}\\}V^{*}_{1}+\mathbb{I}\\{x^{k}_{h^{*}}\neq
x^{*}\\}\rho_{l^{k}}((H^{\prime},0),(p,1-p))$

Define $c_{\rho}$ as the constant that satisfies

$\displaystyle\rho((H,0),(p,1-p))-\rho((H,0),(q,1-q))$ $\displaystyle\geq
c_{\rho}\left\lVert((H,0),(p,1-p))-((H,0),(q,1-q))\right\rVert_{1}$
$\displaystyle=c_{\rho}H|p-q|.$

The expected regret of $\mathscr{A}$ in $\mathcal{M}_{u^{*}}$ can be bounded
as

$\displaystyle\ \ \ \
\mathbb{E}_{\mathscr{A},\mathcal{M}_{u^{*}}}[\text{Regret}(\mathscr{A},\mathcal{M}_{u^{*}},K)]$
$\displaystyle=\mathbb{E}_{\mathscr{A},\mathcal{M}_{u^{*}}}\left[\sum^{K}_{k=1}V^{*}_{1}-V^{\pi^{k}}_{1}\right]$
$\displaystyle=\mathbb{E}_{\mathscr{A},\mathcal{M}_{u^{*}}}\left[\sum_{k=1}^{K}\mathbb{I}\\{x^{k}_{h^{*}}\neq
x^{*}\\}\left(\rho_{h^{*}}((H^{\prime},0),(p+\epsilon,1-p-\epsilon))-\rho_{l^{k}}((H^{\prime},0),(p,1-p))\right)\right]$
$\displaystyle\geq\mathbb{E}_{\mathscr{A},\mathcal{M}_{u^{*}}}\left[\sum_{k=1}^{K}\mathbb{I}\\{x^{k}_{h^{*}}\neq
x^{*}\\}c_{\rho}\left\lVert((H^{\prime},0),(p+\epsilon,1-p-\epsilon))-((H^{\prime},0),(p,1-p))\right\rVert_{1}\right]$
$\displaystyle=\mathbb{E}_{\mathscr{A},\mathcal{M}_{u^{*}}}\left[\sum_{k=1}^{K}\mathbb{I}\\{x^{k}_{h^{*}}\neq
x^{*}\\}c_{\rho}H^{\prime}\epsilon\right]$ $\displaystyle=c_{\rho}\epsilon
H^{\prime}(K-\mathbb{E}_{\mathscr{A},\mathcal{M}_{u^{*}}}[N_{K}(u^{*})]),$

##### Step 2.

The maximum of the regret can be bounded below by the mean over all instances
as

$\displaystyle\max_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}\text{Regret}(\mathscr{A},\mathcal{M}_{u^{*}},K)$
$\displaystyle\geq\frac{1}{\bar{H}\bar{L}A}\sum_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}\text{Regret}(\mathscr{A},\mathcal{M}_{u^{*}},K)$
$\displaystyle\geq
c_{\rho,1}H^{\prime}K\epsilon\left(1-\frac{1}{\bar{L}AK\bar{H}}\sum_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}\mathbb{E}_{u^{*}}[N_{K}(u^{*})]\right).$

Observe that it can be further bounded if we can obtain an upper bound on
$\sum_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}\mathbb{E}_{u^{*}}[N_{K}(u^{*})]$,
which can be done by relating each expectation to the expectation under the
reference MDP $\mathcal{M}_{0}$.

######  Fact 7 (Lemma 1,Garivier et al., (2019)).

Consider a measurable space $(\Omega,\mathcal{F})$ equipped with two
distributions $\mathbb{P}_{1}$ and $\mathbb{P}_{2}$. For any
$\mathcal{F}$-measurable function $Z:\Omega\rightarrow[0,1]$, we have

$\mathrm{KL}\left(\mathbb{P}_{1},\mathbb{P}_{2}\right)\geq\mathrm{kl}\left(\mathbb{E}_{1}[Z],\mathbb{E}_{2}[Z]\right),$

where $\mathbb{E}_{1}$ and $\mathbb{E}_{2}$ are the expectations under
$\mathbb{P}_{1}$ and $\mathbb{P}_{2}$ respectively.

######  Fact 8 (Lemma 5, Domingues et al., (2021)).

Let $\mathcal{M}$ and $\mathcal{M}^{\prime}$ be two MDPs that are identical
except for their transition probabilities, denoted by $P_{h}$ and
$P_{h}^{\prime}$, respectively. Assume that we have $\forall(s,a)$,
$P_{h}(\cdot\mid s,a)\ll P_{h}^{\prime}(\cdot\mid s,a).$ Then, for any
stopping time $\tau$ with respect to $\left(I_{k}\right)_{k\geq 1}$ that
satisfies $\mathbb{P}_{\mathcal{M}}[\tau<\infty]=1$

$\mathrm{KL}\left(\mathbb{P}_{\mathcal{M}},\mathbb{P}_{\mathcal{M}^{\prime}}\right)=\sum_{(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H-1]}\mathbb{E}_{\mathcal{M}}\left[N^{\tau}_{h}(s,a)\right]\mathrm{KL}\left(P_{h}(\cdot\mid
s,a),P_{h}^{\prime}(\cdot\mid s,a)\right).$

######  Fact 9 (Lemma 28, Liang and Luo, (2022)).

If $\epsilon\geq 0$, $p\geq 0$ and $p+\epsilon\in[0,\frac{1}{2}]$, then
$\operatorname{kl}(p,p+\epsilon)\leq\frac{\epsilon^{2}}{2p(1-p)}\leq\frac{\epsilon^{2}}{p}$.

By applying Fact 7 with $Z=\frac{N_{K}(u^{*})}{K}\in[0,1]$, we have

$\operatorname{kl}\left(\frac{1}{K}\mathbb{E}_{0}\left[N_{K}(u^{*})\right],\frac{1}{K}\mathbb{E}_{u^{*}}[N_{K}(u^{*})]\right)\leq\operatorname{KL}\left(\mathbb{P}_{0},\mathbb{P}_{u^{*}}\right).$

By Pinsker’s inequality, it implies that

$\frac{1}{K}\mathbb{E}_{u^{*}}[N_{K}(u^{*})]\leq\frac{1}{K}\mathbb{E}_{0}\left[N_{K}(u^{*})\right]+\sqrt{\frac{1}{2}\operatorname{KL}\left(\mathbb{P}_{0},\mathbb{P}_{u^{*}}\right)}.$

Since $\mathcal{M}_{0}$ and $\mathcal{M}_{u^{*}}$ only differs at stage
$h^{*}$ when $(s,a)=x^{*}$, it follows from Fact 8 that

$\operatorname{KL}\left(\mathbb{P}_{0},\mathbb{P}_{u^{*}}\right)=\mathbb{E}_{0}\left[N_{K}(u^{*})\right]\mathrm{kl}(p,p+\varepsilon).$

By Fact 9, we have $\operatorname{kl}(p,p+\epsilon)\leq\frac{\epsilon^{2}}{p}$
for $\epsilon\geq 0$ and $p+\epsilon\in[0,\frac{1}{2}]$. Consequently,

$\displaystyle\ \ \ \
\frac{1}{K}\sum_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}\mathbb{E}_{u^{*}}[N_{K}(u^{*})]$
$\displaystyle\leq\frac{1}{K}\mathbb{E}_{0}\left[\sum_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}N_{K}(u^{*})\right]+\frac{\epsilon}{\sqrt{2p}}\sum_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}\sqrt{\mathbb{E}_{0}\left[N_{K}(u^{*})\right]}$
$\displaystyle\leq 1+\frac{\epsilon}{\sqrt{2p}}\sqrt{\bar{L}AK\bar{H}},$

where the second inequality is due to the Cauchy-Schwartz inequality and that
$\sum_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}N_{K}(u^{*})=K$.
It follows that

$\displaystyle\max_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}\text{Regret}(\mathscr{A},\mathcal{M}_{u^{*}},K)\geq
c_{\rho,1}H^{\prime}K\epsilon\left(1-\frac{1}{\bar{L}A\bar{H}}-\frac{\frac{\epsilon}{\sqrt{2p}}\sqrt{\bar{L}AK\bar{H}}}{\bar{L}A\bar{H}}\right).$

##### Step 3.

Choosing
$\epsilon=\sqrt{\frac{p}{2}}(1-\frac{1}{LA\bar{H}})\sqrt{\frac{LA\bar{H}}{K}}$
maximizes the lower bound

$\displaystyle\max_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}\text{Regret}(\mathscr{A},\mathcal{M}_{u^{*}},K)\geq\frac{\sqrt{p}}{2\sqrt{2}}c_{\rho,1}H^{\prime}\left(1-\frac{1}{\bar{L}A\bar{H}}\right)^{2}\sqrt{\bar{L}AK\bar{H}}.$

Since $S\geq 6$ and $A\geq 2$, we have
$\bar{L}=(1-\frac{1}{A})(S-3)+\frac{1}{A}\geq\frac{S}{4}$ and
$1-\frac{1}{\bar{L}A\bar{H}}\geq 1-\frac{1}{\frac{6}{4}\cdot 2}=\frac{2}{3}$.
Choose $\bar{H}=\frac{H}{3}$ and use the assumption that $d\leq\frac{H}{3}$ to
obtain that $H^{\prime}=H-d-\bar{H}\geq\frac{H}{3}$. Now we choose arbitrary
$p\leq\frac{1}{4}$ and
$\epsilon=\sqrt{\frac{p}{2}}(1-\frac{1}{\bar{L}A\bar{H}})\sqrt{\frac{LA\bar{H}}{K}}<\frac{1}{2\sqrt{2}}\sqrt{\frac{\bar{L}A\bar{H}}{K}}\leq\frac{1}{4}$
if $K\geq 2\bar{L}A\bar{H}$. Such choice of $p$ and $\epsilon$ guarantees the
assumption of Fact 9. Finally we use the fact that
$\sqrt{\bar{L}AK\bar{H}}\geq\frac{1}{2\sqrt{3}}\sqrt{SAKH}$ to obtain

$\max_{u^{*}\in[d+1:\bar{H}+d]\times\mathcal{L}\times\mathcal{A}}\text{Regret}(\mathscr{A},\mathcal{M}_{u^{*}},K)\geq\frac{\sqrt{p}}{27\sqrt{6}}c_{\rho}H\sqrt{SAKH}.$

###  E.2 Gap-dependent Lower Bound

######  Theorem 6 (Gap-dependent regret lower bound).

Let $S\geq 2$ and $A\geq 2$, and let
$\\{\delta_{s,a}\\}_{{s,a}\in\mathcal{S}\times\mathcal{A}}\subset(0,\frac{H}{8})$
denote a set of gaps. For any $h\geq 1$, there exists an MDP $\mathcal{M}$
with $\mathcal{S}=[S+2]$ and $\mathcal{A}=[A]$ such that any
$\alpha$-uniformly good algorithm alg satisfies

$\displaystyle\lim_{K\rightarrow\infty}\frac{\text{Regret}(\texttt{alg},\mathcal{M},K)}{\log
K}=\Omega\left((1-\alpha)\sum_{(s,a):\Delta_{1}(s,a)>0}\frac{(c_{\rho}H)^{2}}{\Delta_{1}(s,a)}\right)$

We first fix an arbitrary $\alpha$-uniformly good algorithm $\mathscr{A}$. For
simplicity, we may drop $\mathscr{A}$ from the notations, e.g.,
$\mathbb{E}_{\mathcal{M}}=\mathbb{E}_{\mathcal{M},\mathscr{A}}$.

##### Step 1: construction of the hard instance.

Our construction mirrors the lower bounds in . However, their instance is
suited for homogeneous/stationary MDP. Define an MDP $\mathcal{M}$ with
$\mathcal{S}=\\{0\\}\cup[S+2]$ and $\mathcal{A}=[A]$. Without loss of
generality, we consider the case $H\geq 2$. Otherwise, it reduces to a bandit
setting. We first specify the transition kernels. For the convenience of
analysis, we introduce $s_{0}=0$ at stage $h=0$ with $P_{0}(s|0)=\frac{1}{S}$
for any $s\in[S]$. In other words, the initial state $s_{1}$ is uniformly
distributed over $[S]$. For $(s,a)\in[S]\times[A]$, let

$P_{1}(S+1|s,a)=\frac{3}{4}-\frac{2\delta_{s,a}}{H-1}=:\frac{3}{4}-\tilde{\delta}_{s,a},\
P_{1}(S+1|s,a)=1-P_{1}(S+1|s,a).$

Thus at stage 1, each state $s\in[S]$ can only transit to either state $S+1$
or $S+2$. Furthermore, we set state $S+1$ and $S+2$ to be absorbing state,
i.e.

$P_{h}(S+1|S+1,a)=P_{h}(S+2|S+2,a)=1,\ \forall h\in[2:H-1],a\in[A].$

Finally, we set the reward functions as

$R(x,a):=\begin{cases}1&(x,a)=(S+1,1)\\\ \frac{1}{2}&(x,a)=(S+2,1)\\\
0&\text{otherwise}.\end{cases}$

We assume that there exists a unique action $\pi^{*}(s)$ for each $s\in[S]$
such that $\delta_{s,\pi^{*}(s)}=0$. We will see that such action is the
optimal action. Note that $S+1$ and $S+2$ are absorbing states and the only
two rewarding states, hence $V^{*}_{h}(S+1)=H+1-h$ and
$V^{*}_{h}(S+2)=\frac{H+1-h}{2}$ for $h\in[2:H]$. It follows that for
$x\in[S]$,

$\displaystyle V^{*}_{h}(s)$
$\displaystyle=0+\rho_{h}(V^{*}_{h+1},P_{h}(s,\pi^{*}_{h}(s)))=\rho_{h}\left(\left(H-h,\frac{H-h}{2}\right),\left(\frac{3}{4},\frac{1}{4}\right)\right),$
$\displaystyle Q^{*}_{h}(s,a)$
$\displaystyle=0+\rho_{h}(V^{*}_{h+1},P_{h}(s,a))=\rho_{h}\left(\left(H-h,\frac{H-h}{2}\right),\left(\frac{3}{4}-\tilde{\delta}_{s,a},\frac{1}{4}+\tilde{\delta}_{s,a}\right)\right),$

which implies that

$\displaystyle\Delta_{h}(s,a)$
$\displaystyle=\rho_{h}\left(\left(H-h,\frac{H-h}{2}\right),\left(\frac{3}{4},\frac{1}{4}\right)\right)-\rho_{h}\left(\left(H-h,\frac{H-h}{2}\right),\left(\frac{3}{4}-\tilde{\delta}_{s,a},\frac{1}{4}+\tilde{\delta}_{s,a}\right)\right)$
$\displaystyle\geq
c_{\rho}\left\lVert\left(\left(H-h,\frac{H-h}{2}\right),\left(\frac{3}{4},\frac{1}{4}\right)\right)-\left(\left(H-h,\frac{H-h}{2}\right),\left(\frac{3}{4}-\tilde{\delta}_{s,a},\frac{1}{4}+\tilde{\delta}_{s,a}\right)\right)\right\rVert_{1}$
$\displaystyle=c_{\rho}\frac{H-h}{2}\tilde{\delta}_{s,a}.$

In particular, we have $\Delta_{1}(s,a)\geq
c_{\rho}\frac{H-1}{2}\tilde{\delta}_{s,a}=c_{\rho,1}\delta_{s,a}$. Note that
$\Delta_{1}(s,a)$ is only defined for $s\in[S]$.

##### Step 2: regret decomposition.

The regret for algorithm $\mathscr{A}$ over MDP $\mathcal{M}$ can be
decomposed as follows

$\displaystyle\text{Regret}(\mathscr{A},\mathcal{M},K)$
$\displaystyle=\mathbb{E}\left[\sum^{K}_{k=1}V^{*}_{1}(s^{k}_{1})-V^{\pi^{k}}_{1}(s^{k}_{1})\right]$
$\displaystyle=\mathbb{E}\left[\sum^{K}_{k=1}\sum_{h=1}^{H}\Delta_{h}(s^{k}_{h},a^{k}_{h})\right]$
$\displaystyle=\mathbb{E}\left[\sum^{K}_{k=1}\sum_{h=1}^{H}\sum_{s,a}\mathbb{I}\left\\{s^{k}_{h}=s,a^{k}_{h}=a\right\\}\Delta_{h}(s^{k}_{h},a^{k}_{h})\right]$
$\displaystyle=\sum_{h=1}^{H}\sum_{s,a}\mathbb{E}\left[\sum^{K}_{k=1}\mathbb{I}\left\\{s^{k}_{h}=s,a^{k}_{h}=a\right\\}\right]\Delta_{h}(s,a)$
$\displaystyle=\sum_{h=1}^{H}\sum_{s,a}\mathbb{E}\left[N^{K}_{h}(s,a)\right]\Delta_{h}(s,a)$
$\displaystyle=\sum_{h=1}^{H}\sum_{s\in[S],a}\mathbb{E}\left[N^{K}_{h}(s,a)\right]\Delta_{h}(s,a).$

where the last equality is due to that $\Delta_{h}(s,a)$ is only defined over
$[S]$. For our hard instance, observe that
$\mathbb{I}\left\\{s^{k}_{h}=s\right\\}=0$ for $s\in[S]$ and $h\neq 1$.
Therefore $N^{K}_{h}(s,a)=0$ for $s\in[S]$ and $h\neq 1$, which implies

$\text{Regret}(\mathscr{A},\mathcal{M},K)=\sum_{s\in[S],a}\mathbb{E}\left[N^{K}_{1}(s,a)\right]\Delta_{1}(s,a).$

We claim that for any $(s,a)$ such that $s\in[S]$ and $\Delta_{1}(s,a)>0$, and
any $K\geq K_{0}(\mathcal{M})$, it holds that

$\mathbb{E}_{\mathscr{A},\mathcal{M}}\left(N^{K}_{1}(s,a)\right)\geq\Omega\left(\frac{1}{\tilde{\delta}_{s,a}^{2}}\log
K\right)=\Omega\left(\frac{(c_{\rho,1}H)^{2}}{\Delta_{1}(s,a)^{2}}\log
K\right).$

It follows that

$\text{Regret}(\mathscr{A},\mathcal{M},K)\geq\Omega\left(\sum_{s\in[S],a:\Delta_{1}(s,a)>0}\frac{(c_{\rho,1}H)^{2}}{\Delta_{1}(s,a)}\log
K\right).$

##### Step 3: bounding $\mathbb{E}\left[N^{K}_{h}(s,a)\right]$.

Observe that
$\tilde{\delta}_{s,a}=\frac{2}{H-1}\delta_{s,a}\in(0,\frac{1}{2})$ due to the
assumption that $\delta_{s,a}\in(0,\frac{H}{8})$. By Fact 7 and Fact 8, let
$Z$ be a $\mathcal{F}^{K}$-measurable random variable, then it holds that

$\mathrm{kl}\left(\mathbb{E}_{\mathcal{M}}[Z],\mathbb{E}_{\mathcal{M}^{\prime}}[Z]\right)\leq\sum_{(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H-1]}\mathbb{E}_{\mathcal{M}}\left[N^{K}_{h}(s,a)\right]\mathrm{KL}\left(P_{h}(s,a),P_{h}^{\prime}(s,a)\right).$

Now fix an arbitrary $(s,a)\in[S]\times[A]$. Define an MDP
$\mathcal{M}^{\prime}_{s,a}$ which differs from $M$ only in that
$P_{1}(S+1|s,a)=\frac{3}{4}+\eta$, where
$\eta=\min\\{\frac{1}{8},\tilde{\delta}_{s,a}\\}$. For simplicity, we write
$\mathcal{M}^{\prime}=\mathcal{M}^{\prime}_{s,a}$. The following holds

$\mathrm{kl}\left(\mathbb{E}_{\mathcal{M}}[Z],\mathbb{E}_{\mathcal{M}^{\prime}}[Z]\right)\leq\mathbb{E}_{\mathcal{M}}\left[N^{K}_{1}(s,a)\right]\mathrm{KL}\left(P_{1}(s,a),P_{1}^{\prime}(s,a)\right)=\mathbb{E}_{\mathcal{M}}\left[N^{K}_{1}(s,a)\right]\mathrm{kl}\left(\frac{3}{4}-\tilde{\delta}_{s,a},\frac{3}{4}+\eta\right).$

Observe that
$\frac{1}{4}<\frac{3}{4}-\tilde{\delta}_{s,a}<\frac{3}{4}+\eta<\frac{7}{8}$
and $\eta+\tilde{\delta}_{s,a}\leq 2\tilde{\delta}_{s,a}$, it follows from
Fact 9 that

$\mathrm{kl}\left(\frac{3}{4}-\tilde{\delta}_{s,a},\frac{3}{4}+\eta\right)\leq\frac{(\eta+\tilde{\delta}_{s,a})^{2}}{2(\frac{3}{4}-\tilde{\delta}_{s,a})(1-\frac{3}{4}-\eta)}<64\tilde{\delta}_{s,a}^{2}.$

Now we have

$\mathbb{E}_{\mathcal{M}}\left[N^{K}_{1}(s,a)\right]\geq\frac{1}{64\tilde{\delta}_{s,a}^{2}}\mathrm{kl}\left(\mathbb{E}_{\mathcal{M}}[Z],\mathbb{E}_{\mathcal{M}^{\prime}}[Z]\right)\geq\frac{(c_{\rho,1}(H-1))^{2}}{256\Delta_{1}^{2}(s,a)}\mathrm{kl}\left(\mathbb{E}_{\mathcal{M}}[Z],\mathbb{E}_{\mathcal{M}^{\prime}}[Z]\right).$

We set $Z=\sum_{k=1}^{K}\frac{\mathbb{I}\\{\pi^{k}_{1}(s)=a\\}}{K}\in[0,1]$.
Note that $Z$ is indeed $\mathcal{F}^{K}$-measurable random variable since
$\pi^{k}$ is $\mathcal{F}^{K}$-measurable and $(s,a)$ is fixed. Denote by
$\Delta^{\prime}$ the gap for MDP $\mathcal{M}^{\prime}$. Observe that for
$a^{\prime}\neq a$,

$\displaystyle\Delta_{1}^{\prime}(s,a^{\prime})$
$\displaystyle=\rho_{h}\left(\left(H-1,\frac{H-1}{2}\right),\left(\frac{3}{4}+\eta,\frac{1}{4}-\eta\right)\right)-\rho_{h}\left(\left(H-1,\frac{H-1}{2}\right),\left(\frac{3}{4}-\tilde{\delta}_{s,a^{\prime}},\frac{1}{4}+\tilde{\delta}_{s,a^{\prime}}\right)\right)$
$\displaystyle\geq
c_{\rho}\frac{H-1}{2}(\eta+\tilde{\delta}_{s,a^{\prime}})\geq
c_{\rho}\frac{H-1}{2}\eta.$

Under MDP $\mathcal{M}^{\prime}$, action $a$ is the unique optimal action for
$s$, thus

$\displaystyle\text{Regret}(\mathscr{A},\mathcal{M}^{\prime},K)$
$\displaystyle\geq\sum_{a^{\prime}\neq
a}\mathbb{E}_{\mathcal{M}^{\prime}}\left[N^{K}_{1}(s,a^{\prime})\right]\Delta^{\prime}_{1}(s,a^{\prime})$
$\displaystyle\geq c_{\rho}\frac{H-1}{2}\eta\sum_{a^{\prime}\neq
a}\mathbb{E}_{\mathcal{M}^{\prime}}\left[N^{K}_{1}(s,a^{\prime})\right]$
$\displaystyle=c_{\rho}\frac{H-1}{2}\eta\mathbb{E}_{\mathcal{M}^{\prime}}\left[\sum_{k=1}^{K}\sum_{a^{\prime}\neq
a}\mathbb{I}\left(s^{k}_{1}=s,\pi^{k}_{1}(s^{k}_{1})=a\right)\right]$
$\displaystyle=c_{\rho}\frac{H-1}{2}\eta\mathbb{E}_{\mathcal{M}^{\prime}}\left[\sum_{k=1}^{K}\left(\mathbb{I}\left(s^{k}_{1}=s\right)-\mathbb{I}\left(s^{k}_{1}=s,\pi^{k}_{1}(s^{k}_{1})=a\right)\right)\right]$
$\displaystyle=c_{\rho}\frac{H-1}{2}\eta\left(\frac{K}{S}-\mathbb{E}_{\mathcal{M}^{\prime}}\left[\sum_{k=1}^{K}\mathbb{I}\left(s^{k}_{1}=s\right)\mathbb{I}\left(\pi^{k}_{1}(s)=a\right)\right]\right)$
$\displaystyle=c_{\rho}\frac{H-1}{2}\eta\left(\frac{K}{S}-\sum_{k=1}^{K}\mathbb{E}_{\mathcal{M}^{\prime}}\left[\mathbb{I}\left(s^{k}_{1}=s\right)\right]\mathbb{E}_{\mathcal{M}^{\prime}}\left[\mathbb{I}\left(\pi^{k}_{1}(s)=a\right)\right]\right)$
$\displaystyle=c_{\rho}\frac{H-1}{2}\frac{K}{S}\left(1-\mathbb{E}_{\mathcal{M}^{\prime}}\left[Z\right]\right),$

where the second to the last equality is due to the dependence between
$s^{k}_{1}$ and $\pi^{k}_{1}$. Since $\mathscr{A}$ is $\alpha$-uniformly good
algorithm, there exists $C_{\mathcal{M}^{\prime}}>0$ such that

$c_{\rho}\frac{H-1}{2}\frac{K}{S}\left(1-\mathbb{E}_{\mathcal{M}^{\prime}}\left[Z\right]\right)\leq\text{Regret}(\mathscr{A},\mathcal{M}^{\prime},K)\leq
C_{\mathcal{M}^{\prime}}K^{\alpha},$

implying

$1-\mathbb{E}_{\mathcal{M}^{\prime}}\left[Z\right]\leq\frac{2C_{\mathcal{M}^{\prime}}S}{c_{\rho,1}(H-1)K^{1-\alpha}}.$

We can also get

$\displaystyle
C_{\mathcal{M}}K^{\alpha}\geq\text{Regret}(\mathscr{A},\mathcal{M},K)$
$\displaystyle\geq\mathbb{E}_{\mathcal{M}}\left[N^{K}_{1}(s,a)\right]\Delta_{1}(s,a)\geq\frac{K\Delta_{1}(s,a)}{S}\mathbb{E}_{\mathcal{M}}\left[Z\right],$

which implies that
$\mathbb{E}_{\mathcal{M}}\left[Z\right]\leq\frac{C_{\mathcal{M}}S}{\Delta_{1}(s,a)K^{1-\alpha}}$.
By [],

$\mathrm{kl}(x,y)\geq(1-x)\log\frac{1}{1-y}-\log 2.$

It follows that

$\mathrm{kl}\left(\mathbb{E}_{\mathcal{M}}\left[Z\right],\mathbb{E}_{\mathcal{M}^{\prime}}\left[Z\right]\right)\geq\left(1-\frac{C_{\mathcal{M}}S}{\Delta_{1}(s,a)K^{1-\alpha}}\right)\left((1-\alpha)\log
K-\log\frac{2C_{\mathcal{M}^{\prime}}S}{c_{\rho,1}(H-1)}\right)-\log 2.$

##### Step 4.

We can also prove for the case $h\neq 1$ by modifying the transition kernels
for state 0. For $h\neq 1$, we set the transition kernels as

$P_{l}(0|0,a)=1,\forall l\in[0:h-2],\forall a\in[A],\
P_{h-1}(s|0,a)=\frac{1}{S},\forall s\in[S],\forall a\in[A].$

In other words, the MDP is randomly initialized over $[S]$ at stage $h$ rather
than stage 1. For $(s,a)\in[S]\times[A]$, let

$P_{h}(S+1|s,a)=\frac{3}{4}-\frac{2\delta_{s,a}}{H-1}=:\frac{3}{4}-\tilde{\delta}_{s,a},\
P_{h}(S+1|s,a)=1-P_{h}(S+1|s,a).$

Finally, we still set $S+1,S+2$ to be absorbing states. Using similar
arguments concludes the proof.