# Non-stationary Risk-sensitive Reinforcement Learning: Near-optimal Dynamic
Regret, Adaptive Detection, and Separation Design

Yuhao Ding1, Ming Jin2, Javad Lavaei1

###### Abstract

We study risk-sensitive reinforcement learning (RL) based on an entropic risk
measure in episodic non-stationary Markov decision processes (MDPs). Both the
reward functions and the state transition kernels are unknown and allowed to
vary arbitrarily over time with a budget on their cumulative variations. When
this variation budget is known a prior, we propose two restart-based
algorithms, namely Restart-RSMB and Restart-RSQ, and establish their dynamic
regrets. Based on these results, we further present a meta-algorithm that does
not require any prior knowledge of the variation budget and can adaptively
detect the non-stationarity on the exponential value functions. A dynamic
regret lower bound is then established for non-stationary risk-sensitive RL to
certify the near-optimality of the proposed algorithms. Our results also show
that the risk control and the handling of the non-stationarity can be
separately designed in the algorithm if the variation budget is known a prior,
while the non-stationary detection mechanism in the adaptive algorithm depends
on the risk parameter. This work offers the first non-asymptotic theoretical
analyses for the non-stationary risk-sensitive RL in the literature.

##  1 Introduction

Risk-sensitive RL considers problems in which the objective takes into account
risks that arise during the learning process, in contrast to the typical
expected accumulated reward objective. Effective management of the variability
of the return in RL is essential in various applications in finance (Markowitz
1968), autonomous driving (Garcıa and Fernández 2015) and human behavior
modeling (Niv et al. 2012).

While classical risk-sensitive RL assumes that an agent interacts with a time-
invariant (stationary) environment, both the reward functions and the
transition kernels can be time-varying for many risk-sensitive applications.
For example, in finance (Markowitz 1968), the federal reserve adjusts the
interest rate or the balance sheet in a non-stationary way and the market
participants should adjust their trading policies accordingly. In the medical
treatments (Man et al. 2014), the patient’s health condition and the
sensitivity of the patient’s internal body organs to the medicine vary over
time. This non-stationarity should be accounted for to minimize the risk of
any potential side effects of the treatment.

Despite the importance and ubiquity of non-stationary risk-sensitive RL
problems, the literature lacks provably efficient algorithms and theoretical
results. In this work, we study risk-sensitive RL with an entropic risk
measure (Howard and Matheson 1972) under episodic Markov decision processes
with unknown and time-varying reward functions and state transition kernels.

The non-stationary RL problem with an entropic risk measure has the following
technical challenges. (1) Due to the non-stationarity of the model, any
estimation error of the expectation operator may be tremendously amplified in
the value function when the risk parameter $\beta$ is small. (2) In addition,
the exponential Bellman equation (see Equation (3)) used in our risk-sensitive
analysis associates the instantaneous reward and value function of the next
step in a multiplicative way (Fei et al. 2021). However, this multiplicative
feature of the exponential Bellman equation will also involve the policy
evaluation errors due to the non-stationary drifting as multiplicative terms,
which makes it more difficult to gauge the bounds than the risk-neural non-
stationary setting in which all policy evaluation errors are in an additive
way. (3) Furthermore, the non-linearity of the objective function (see
Equation (1)) makes it difficult to obtain an unbiased estimation of the value
function, which is needed in the design of a non-stationary detection
mechanism in risk-neutral non-stationary RL (Wei and Luo 2021). (4) It is
unclear whether the risk control and the handling of the non-stationarity can
be separately designed when achieving the optimal dynamic regret. To address
these difficulties, we develop a novel analysis to carefully quantify the
effect of the non-stationarity in risk-sensitive RL. Our main theoretical
contributions, summarized in Table 1, are as follows

  * •

When the variation budget is known a prior, we propose two provably efficient
restart algorithms, namely Restart-RSMB and Restart-RSQ, and establish their
dynamic regrets. The stationary version of the model-based method Restart-RSMB
is also the first model-based risk-sensitive algorithm in the stationary
setting in the literature.

  * •

When the variation budget is unknown (parameter-free), we propose a meta-
algorithm that adaptively detects the non-stationarity of the exponential
value functions. The proposed adaptive algorithms, namely Adaptive-RSMB and
Adaptive-RSQ, can achieve the (almost) same dynamic regret as the algorithms
requiring the knowledge of the variation budget.

  * •

We establish a lower bound result for non-stationary RL with entropic risk
measure that certifies the near-optimality of our upper bounds.

  * •

Our results also show that the risk control and the handling of the non-
stationarity can be separately designed if the variation budget is known a
prior, while the non-stationary detection mechanism in the adaptive algorithms
depends on the risk parameter.

Algorithm | D-Regret | Parameter-free | Model-free | Separation
---|---|---|---|---
Restart-RSMB | $\widetilde{\mathcal{O}}\left(e^{|\beta|H}|\mathcal{S}|^{\frac{2}{3}}|\mathcal{A}|^{\frac{1}{3}}H^{2}M^{\frac{2}{3}}B^{\frac{1}{3}}\right)$ | ✗ | ✗ | ✓
Restart-RSQ | $\widetilde{\mathcal{O}}\left(e^{|\beta|H}|\mathcal{S}|^{\frac{1}{3}}|\mathcal{A}|^{\frac{1}{3}}H^{\frac{9}{4}}M^{\frac{2}{3}}B^{\frac{1}{3}}\right)$ | ✗ | ✓ | ✓
Adaptive-RSMB | $\widetilde{\mathcal{O}}\left(e^{|\beta|H}|\mathcal{S}|^{\frac{2}{3}}|\mathcal{A}|^{\frac{1}{3}}H^{2}M^{\frac{2}{3}}B^{\frac{1}{3}}\right)$ | ✓ | ✗ | ✗
Adaptive-RSQ | $\widetilde{\mathcal{O}}\left(e^{|\beta|H}|\mathcal{S}|^{\frac{1}{3}}|\mathcal{A}|^{\frac{1}{3}}H^{\frac{5}{3}}M^{\frac{2}{3}}B^{\frac{1}{3}}\right)$ | ✓ | ✓ | ✗
Lower bound | $\Omega\left(\frac{e^{\frac{2|\beta|H}{3}}-1}{|\beta|}|\mathcal{S}|^{\frac{1}{3}}|\mathcal{A}|^{\frac{1}{3}}M^{\frac{2}{3}}B^{\frac{1}{3}}\right)$ |  |  |
Table 1: We summarize the dynamic regrets and lower bound obtained in this
paper. Here, $\beta$ is the risk parameter, $H$ is the horizon of each
episode, $M$ is the total number of episodes, $B$ is the total variation
measurement, and $|\mathcal{S}|$ and $|\mathcal{A}|$ are the cardinalities of
the state and action spaces.

###  1.1 Related work

Non-stationary RL. Non-stationary RL has been mostly studied in the risk-
neutral setting. When the variation budget is known a prior, a common strategy
for adapting to the non-stationarity is to follow the forgetting principle,
such as the restart strategy (Mao et al. 2020; Zhou et al. 2020; Zhao et al.
2020; Ding and Lavaei 2022), exponential decayed weights (Touati and Vincent
2020), or sliding window (Cheung, Simchi-Levi, and Zhu 2020; Zhong, Yang, and
Szepesvári 2021). In this work, we focus on the restart method mainly due to
its advantage of the simplicity of the the memory efficiency (Zhao et al.
2020) and generalize it to the risk-sensitive RL setting. However, the prior
knowledge of the variation budget is often unavailable in practice. The work
(Cheung, Simchi-Levi, and Zhu 2020) develop a Bandit-over-Reinforcement-
Learning framework to relax this assumption, but it leads to the suboptimal
regret. To achieve a nearly-optimal regret without the prior knowledge of the
variation budget, (Auer, Gajane, and Ortner 2019) and (Chen et al. 2019)
maintain a distribution over bandit arms with properly controlled variance for
all reward estimators. For RL problems, the seminar work (Wei and Luo 2021)
proposes a black-box reduction approach that turns a certain RL algorithm with
optimal regret in a (near-)stationary environment into another algorithm with
optimal dynamic regret in a non-stationary environment. However, the above
works only consider risk-neutral RL and may not apply to the more general
risk-sensitive RL problems.

Risk-sensitive RL. Many risk-sensitive objectives have been investigated in
the literature and applied to RL, such as the entropic risk measure, Markowitz
mean-variance model, Value-at-Risk (VaR), and Conditional Value at Risk (CVaR)
(Moody and Saffell 2001; Chow and Ghavamzadeh 2014; Delage and Mannor 2010; La
and Ghavamzadeh 2013; Di Castro, Tamar, and Mannor 2012; Tamar, Glassner, and
Mannor 2015; Tamar et al. 2015; Howard and Matheson 1972). Our work is closely
related to the entropic risk measure. Following the seminal paper (Howard and
Matheson 1972), this line of work includes (Bäuerle and Rieder 2014; Borkar
2001; Borkar and Meyn 2002; Borkar 2002; Cavazos-Cadena and Fernández-
Gaucherand 2000; Coraluppi and Marcus 1999; Di Masi and Stettner 1999;
Fernández-Gaucherand and Marcus 1997; Fleming and McEneaney 1995; Hernández-
Hernández and Marcus 1996; Osogami 2012; Fleming and McEneaney 1992; Shen,
Stannat, and Obermayer 2013; Fei et al. 2020; Fei, Yang, and Wang 2021; Fei et
al. 2021). In particular, when transitions are unknown and simulators of the
environment are unavailable, the first non-asymptotic regret guarantees are
established under the tabular setting in (Fei et al. 2020) and the function
approximation setting in (Fei, Yang, and Wang 2021). Then, a simple
transformation of the risk-sensitive Bellman equations is proposed in (Fei et
al. 2021), which leads to improved regret upper bounds. However, the above
papers all assume that the environment is stationary, and therefore their
results may quickly collapse in a non-stationary environment.

##  2 Problem formulation

###  2.1 Notations

For a positive integer $n$, let $[n]:=\\{1,2,\ldots,n\\}$. Given a variable
$x$, the notation $a=\mathcal{O}(b(x))$ means that $a\leq C\cdot b(x)$ for
some constant $C>0$ that is independent of $x$. Similarly,
$a=\widetilde{\mathcal{O}}(b(x))$ indicates that the previous inequality may
also depend on the function $\log(x)$, where $C>0$ is again independent of
$x$. In addition, the notation $a=\Omega(b(x))$ means that $a\geq C\cdot b(x)$
for some constant $C>0$ that is independent of $x$.

###  2.2 Episodic MDP and risk-sensitive objective

In this paper, we study risk-sensitive RL in non-stationary environments via
episodic MDPs with adversarial bandit-information reward feedback and unknown
adversarial transition dynamics. At each episode $m$, an episodic MDP is
defined by the finite state space $\mathcal{S}$, the finite action space
$\mathcal{A}$, a collection of transition probability measure
$\\{\mathcal{P}_{h}^{m}\\}_{h=1}^{H}$ specifying the transition probability
$\mathcal{P}_{h}^{m}(s^{\prime}\mid s,a)$ from state $s$ to the next state
$s^{\prime}$ under action $a\in\mathcal{A}$, a collection of reward functions
$\\{r_{h}^{m}\\}_{h=1}^{H}$ where
$r_{h}^{m}:\mathcal{S}\times\mathcal{A}\rightarrow[0,1]$ , and $H>0$ as the
length of episodes. In this paper, we focus on a bandit setting where the
agent only observes the values of reward functions, i.e.,
$r_{h}^{m}(s_{h}^{m},a_{h}^{m})$ at the visited state-action pair
$(s_{h}^{m},a_{h}^{m})$. We also assume that reward functions are
deterministic to streamline the presentation, while our analysis readily
generalizes to the setting where reward functions are random.

For simplicity, we assume the initial state $s_{1}^{m}$ to be fixed as $s_{1}$
in different episodes. We use the convention that the episode terminates when
a state $s_{H+1}$ at step $H+1$ is reached, at which the agent does not take
any further action and receives no reward.

A policy $\pi^{m}=\left\\{\pi_{h}^{m}\right\\}_{h\in[H]}$ of an agent is a
sequence of functions $\pi_{h}^{m}:\mathcal{S}\rightarrow\mathcal{A}$, where
$\pi_{h}^{m}(s)$ is the action that the agent takes in state $s$ at step $h$
at episode $m$. For each $h\in[H]$ and $m\in[M]$, we define the value function
$V_{h}^{\pi,m}:\mathcal{S}\rightarrow\mathbb{R}$ of a policy $\pi$ as the
expected value of the cumulative rewards the agent receives under a risk
measure of exponential utility by executing $\pi$ starting from an arbitrary
state at step $h$. Specifically, we have

$\displaystyle
V_{h}^{\pi,m}(s):=\frac{1}{\beta}\log\left\\{\mathbb{E}_{\pi,\mathcal{P}^{m}}\left[\exp\left(\beta\sum_{i=h}^{H}r^{m}_{i}\left(s_{i},a_{i}\right)\right)\mid
s_{h}=s\right]\right\\}$ (1)

where the expectation $\mathbb{E}_{\pi,\mathcal{P}^{m}}$ is taken over the
random state-action sequence
$\left\\{\left(x_{i}^{m},a_{i}^{m}\right)\right\\}_{i=h}^{H}$, the action
$a_{i}^{m}$ follows the policy $\pi_{i}^{m}\left(\cdot\mid x_{i}^{m}\right)$,
and the next state $x_{i+1}$ follows the transition dynamics
$\mathcal{P}_{i}^{m}\left(\cdot\mid x_{i}^{m},a_{i}^{m}\right)$. Here
$\beta\neq 0$ is the risk parameter of the exponential utility: $\beta>0$
corresponds to a risk-seeking value function, $\beta<0$ corresponds to a risk-
averse value function, and as $\beta\rightarrow 0$ the agent tends to be risk-
neutral and we recover the classical value function $V^{\pi,m}_{h}(s)=$
$\mathbb{E}_{\pi,\mathcal{P}^{m}}\left[\sum_{t=1}^{H}r_{h}^{m}\left(s_{t},a_{t}\right)\mid
s_{0}=s\right]$ in standard RL.

We further define the action-value function
$Q_{h}^{\pi,m}:\mathcal{S}\times\mathcal{A}\rightarrow\mathbb{R}$, for each
$h\in[H]$ and $m\in[M]$, which gives the expected value of the risk measured
by the exponential utility when the agent starts from an arbitrary state-
action pair and follows the policy $\pi$ afterwards; that is,

$\displaystyle Q_{h}^{\pi,m}$ $\displaystyle\coloneqq$
$\displaystyle\frac{1}{\beta}\log\left\\{\exp\left(\beta\cdot
r^{m}_{h}(s,a)\right)\mathbb{E}\left[\exp\left(\beta\sum_{i=h}^{H}r_{i}^{m}\left(s_{t},a_{t}\right)\right)\right.\right.$
$\displaystyle\hskip 142.26378pt\Big{\mid}s_{h}=s,a_{h}=a\Bigg{]}\Bigg{\\}}$
$\displaystyle=$ $\displaystyle
r_{h}^{m}(s,a)+\frac{1}{\beta}\log\left\\{\mathbb{E}\left[\exp\left(\beta\sum_{i=h+1}^{H}r_{i}^{m}\left(s_{t},a_{t}\right)\right)\right.\right.$
$\displaystyle\hskip 142.26378pt\Big{\mid}s_{h}=s,a_{h}=a\Bigg{]}\Bigg{\\}}$

for all $(s,a)\in\mathcal{S}\times\mathcal{A}$. Under some mild regularity
conditions (Bäuerle and Rieder 2014), for each episode $m$, there always
exists an optimal policy, denoted as $\pi^{*,m}$, that yields the optimal
value $V_{h}^{\pi^{*,m},m}(s):=\sup_{\pi}V_{h}^{\pi,m}(s)$ for all
$(h,s)\in[H]\times\mathcal{S}$. For convenience, we denote
$V_{h}^{\pi^{*,m},m}(s)$ as $V_{h}^{*,m}(s)$ when it is clear from the
context.

###  2.3 Exponential Bellman equation

For all $(s,a,h,m)\in\mathcal{S}\times\mathcal{A}\times[H]\times[M]$, the
Bellman equation associated with $\pi$ is given by

$\displaystyle Q_{h}^{\pi,m}(s,a)$
$\displaystyle=r_{h}^{m}(s,a)+\frac{1}{\beta}\log\left\\{\mathbb{E}_{s^{\prime}\sim
P_{h}^{m}(\cdot\mid s,a)}\left[e^{\beta\cdot
V_{h+1}^{\pi,m}\left(s^{\prime}\right)}\right]\right\\},$ (2a) $\displaystyle
V_{h}^{\pi,m}(s)$ $\displaystyle=Q_{h}^{\pi,m}(s,\pi(s)),\quad
V_{H+1}^{\pi,m}(s)=0.$ (2b)

In Equation (2), it can be seen that the action value $Q_{h}^{\pi,m}$ of step
$h$ is a non-linear function of the value function $V_{h+1}^{\pi,m}$ of the
later step. Based on Equation (2), for $h\in[H]$ and $m\in[M]$, the Bellman
optimality equation is given by

$\displaystyle Q_{h}^{*,m}(s,a)$
$\displaystyle=r_{h}^{m}(s,a)+\frac{1}{\beta}\log\left\\{\mathbb{E}_{s^{\prime}\sim
P_{h}^{m}(\cdot\mid s,a)}\left[e^{\beta\cdot
V_{h+1}^{*,m}\left(s^{\prime}\right)}\right]\right\\},$ $\displaystyle
V_{h}^{*,m}(s)$ $\displaystyle=\max_{a\in\mathcal{A}}Q_{h}^{*,m}(s,a),\quad
V_{H+1}^{*,m}(s)=0.$

It has been recently shown in (Fei et al. 2021) that under the risk-sensitive
measurement, it is easier to analyze a simple transformation of the Bellman
equation (by taking exponential on both sides of (2)), which is called
exponential Bellman equation: for every policy $\pi$ and tuple $(s,a,h,m)$, we
have

$\displaystyle e^{\beta\cdot Q_{h}^{\pi,m}(s,a)}=\mathbb{E}_{s^{\prime}\sim
P^{m}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left(r^{m}_{h}(s,a)+V_{h+1}^{\pi,m}\left(s^{\prime}\right)\right)}\right].$
(3)

When $\pi=\pi^{*,m}$, we obtain the corresponding optimality equation

$\displaystyle e^{\beta\cdot Q_{h}^{*,m}(s,a)}=\mathbb{E}_{s^{\prime}\sim
P_{h}^{m}(\cdot\mid
s,a)}\left[e^{\beta\left(r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right)}\right].$
(4)

Note that Equation (3) associates the current and future cumulative utilities
$\left(Q_{h}^{\pi,m}\right.$ and $\left.V_{h+1}^{\pi,m}\right)$ in a
multiplicative way, rather than in an additive way as in the standard Bellman
equations (2).

###  2.4 Non-stationarity and variation budget

In this work, we focus on a non-stationary environment where the transition
function $P_{h}^{m}$ and reward functions $r_{h}^{m}$ can vary over the
episodes. We measure the non-stationarity of the MDP over an interval
$\mathcal{I}$ in terms of its variation in the reward functions and transition
kernels:

$\displaystyle
B_{r,\mathcal{I}}\coloneqq\sum_{m\in\mathcal{I}}\sum_{h=1}^{H}\sup_{s,a}\left|r_{h}^{m}(s,a)-r_{h}^{m+1}(s,a)\right|,$
$\displaystyle
B_{\mathcal{P},\mathcal{I}}\coloneqq\sum_{m\in\mathcal{I}}\sum_{h=1}^{H}\sup_{s,a}\left\|\mathcal{P}_{h}^{m}(\cdot\mid
s,a)-\mathcal{P}_{h}^{m+1}(\cdot\mid s,a)\right\|_{1}.$

Note that our definition of variation only imposes restrictions on the
summation of non-stationarity across different episodes, and does not put any
restriction on the difference between two steps in the same episode. We
further let $B_{r}\coloneqq B_{r,[1,M]}$, $B_{p}\coloneqq B_{p,[1,M]}$, and
$B\coloneqq B_{r}+B_{p}$, and assume $B>0$.

###  2.5 Performance metrics

Since both the reward and the transition dynamics vary over the episodes and
are revealed only after a policy is decided, the agent aims to ensure the
long-term optimality guarantee over some given period of episodes $M$. Suppose
that the agent executes policy $\pi^{m}$ in episode $m$. We now define the
dynamic regret as the difference between the total reward value of policy
$\left\\{\pi^{\star,m}\right\\}_{m=1}^{M}$ and that of the agent’s policy
$\pi^{m}$ over $M$ episodes:

$\operatorname{D-Regret}(M):=\sum_{m=1}^{M}\left(V_{1}^{*,m}-V_{1}^{\pi^{m},m}\right).$

##  3 Restart algorithms with the knowledge of variation budget

###  3.1 Periodically restarted risk-sensitive model-based method

We first present the Periodically Restarted Risk-sensitive Model-based method
(Restart-RSMB) in Algorithm 1. It consists of two main stages: estimation of
value function (line 7-13) with the periodical restart (line 5) and the policy
execution (line 15).

To estimate the value function under the unknown non-stationarity, we take the
optimistic value evaluation to properly handle the exploration-exploitation
trade-off and apply the restart strategy to adapt to the unknown non-
stationarity. In particular, we reset the visitation counters
$N_{h}^{m}\left(s,a,s^{\prime}\right)$ and $N_{h}^{m}(x,a)$ to zero every $W$
episodes (line 5). Then, the reward and transition dynamics are estimated
using only the data from the episode
$\ell^{m}=(\left\lceil{\frac{m}{W}}\right\rceil-1)W+1$ to the episode $m$ by

$\displaystyle\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)=\frac{N_{h}^{m}\left(s,a,s^{\prime}\right)+\frac{\lambda}{|\mathcal{S}|}}{N_{h}^{m}(s,a)+\lambda},$
(5a) $\displaystyle\hskip 85.35826pt\text{ for all
}\left(s,a,s^{\prime}\right)\in\mathcal{S}\times\mathcal{A}\times\mathcal{S},$
$\displaystyle\widehat{r}_{h}^{m}(s,a)=\frac{\sum_{\tau=\ell^{m}}^{m-1}1\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}r^{\tau}_{h}\left(s_{h}^{\tau},a_{h}^{\tau}\right)}{N_{h}^{m}(s,a)+\lambda},$
(5b) $\displaystyle\hskip 71.13188pt\text{ for all
}(s,a)\in\mathcal{S}\times\mathcal{A},$

which are used to compute the estimated cumulative rewards at step $h$ (line
9). To encourage a sufficient exploration in the uncertain environment,
Algorithm 1 applies the counter-based Upper Confidence Bound (UCB). Under the
entropic risk measure, this bonus term takes the form

$\displaystyle\begin{cases}&C_{1}\left(\left(e^{\beta(H-h+1)}-1\right)+e^{\beta(H-h+1)}\beta\right)\sqrt{\frac{\left|\mathcal{S}\right|\log\left(6WH\left|\mathcal{S}\right|\left|\mathcal{A}\right|/p\right)}{N_{h}^{m}(s,a)+1}},\\\
&\hskip 170.71652pt\text{ if }\beta>0,\\\
&C_{1}\left(\left(1-e^{\beta(H-h+1)}\right)-\beta\right)\sqrt{\frac{\left|\mathcal{S}\right|\log\left(6WH\left|\mathcal{S}\right|\left|\mathcal{A}\right|/p\right)}{N_{h}^{m}(s,a)+1}},\\\
&\hskip 170.71652pt\text{ if }\beta<0,\end{cases}$ (6)

for some constant $C_{1}>1$. Bonus terms of the form (6) are called “doubly
decaying bonus” since they shrink deterministically and exponentially across
the horizon steps due to the term $e^{\beta(H-h+1)}$, apart from decreasing in
the visit count. We refer the reader to (Fei, Yang, and Wang 2021) for more
discussion.

Algorithm 1 Periodically Restarted Risk-sensitive Model-based RL (Restart-
RSMB)

1: Inputs: Time horizon $M$, restart period $W$;

2: for $m=1,\ldots,M$ do

3: Set the initial state $x_{1}^{m}=x_{1}$ and
$\ell^{m}=(\left\lceil{\frac{m}{W}}\right\rceil-1)W+1$;

4: if $m=\ell^{m}$ then

5: $Q_{h}^{m}(s,a),V_{h}^{m}(s)\leftarrow H-h+1$ if $\beta>0$,
$Q_{h}^{m}(s,a),V_{h}^{m}(s)\leftarrow 0$ if $\beta<0$,
$N_{h}^{m}(s,a)\leftarrow 0,N_{h}^{m}(s,a,s^{\prime})\leftarrow 0$ for all
$(s,a,s^{\prime},h)\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}\times[H]$
;

6: end if

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

8: for $(s,a)\in\mathcal{S}\times\mathcal{A}$ do

9: $w_{h}^{m}(s,a)=$$\sum_{s^{\prime}}\hat{\mathcal{P}}_{h}^{m}(s^{\prime}\mid
s,a)\left[e^{\beta\left[\hat{r}_{h}^{m}(s,a)+V_{h+1}^{m}\left(s^{\prime}\right)\right]}\right]$
where $\hat{\mathcal{P}}_{h}^{m}$, $\hat{r}_{h}^{m}$ are defined in (5);

10:
$G^{m}_{h}(s,a)\leftarrow$$\begin{cases}\min\left\\{e^{\beta(H-h+1)},w_{h}^{m}(s,a)+\Gamma_{h}^{m}(s,a)\right\\},\text{if
}\beta>0;\\\
\max\left\\{e^{\beta(H-h+1)},w_{h}^{m}(s,a)-\Gamma_{h}^{m}(s,a)\right\\},\text{if
}\beta<0;\end{cases}$ where $\Gamma_{h}^{m}$ is defined in (6);

11: $V_{h}^{m}(s)\leftarrow\max_{a^{\prime}\in\mathcal{A}}\frac{1}{\beta}\log
G_{h}^{m}\left(s,a^{\prime}\right)$;

12: end for

13: end for

14: for $h=1,2,\ldots,H$ do

15: Take an action $a_{h}^{m}\leftarrow\mathop{\rm
argmax}_{a^{\prime}\in\mathcal{A}}\frac{1}{\beta}\log\\{G_{h}^{m}\left(s_{h}^{m},a^{\prime}\right)\\}$,
and observe $r_{h}(s_{h}^{m},a_{h}^{m})$ and $s_{h+1}^{m}$;

16: $N_{h}^{m}(s_{h}^{m},a_{h}^{m})\leftarrow
N_{h}^{m}(s_{h}^{m},a_{h}^{m})+1$;
$N_{h}^{m}(s_{h}^{m},a_{h}^{m},s_{h+1}^{m})\leftarrow
N_{h}^{m}(s_{h}^{m},a_{h}^{m},s_{h+1}^{m},)+1$;

17: end for

18: end for

###  3.2 Periodically restarted risk-sensitive Q-learning

Next, we introduce Periodically Restarted Risk-sensitive Q-learning (Restart-
RSQ) in Algorithm 2, which is model-free and inspired by RSQ2 in (Fei et al.
2021). Similar to Algorithm 1, we use the optimistic value evaluation to
handle the exploration-exploitation trade-off and apply the restart strategy
to adapt to the unknown non-stationarity. In particular, we re-initialize the
value functions $Q_{h}^{m}(s,a),V_{h}^{m}(s)$ and reset the visitation counter
$N_{h}^{m}(x,a)$ to zero every $W$ episodes (line 5). The algorithm then
updates the exponential Q values using the Q-learning style update (line
11-12) for the state action pair that just visited (line 8). The learning rate
$\alpha_{t}$ is defined as $\frac{H+1}{H+t}$, which is motivated by (Jin et
al. 2018) and ensures that only the last $\mathcal{O}(\frac{1}{H})$ fraction
of samples in each epoch is given non-negligible weights when used to estimate
the optimistic Q-values under the non-stationarity. Algorithm 2 also applies
the UCB by incorporating a “doubly decaying bonus” term that takes the form

$\displaystyle\Gamma_{h,t}^{m}(s_{h}^{m},a_{h}^{m})\leftarrow
C_{2}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\frac{|\mathcal{S}|\log(MH|\mathcal{S}||\mathcal{A}|/\delta)}{t}}$
(7)

for some constant $C_{2}>1$.

Algorithm 2 Periodically Restarted Risk-sensitive Q-learning (Restart-RSQ)

1: Inputs: Time horizon $M$, restart period $W$;

2: for $m=1,\ldots,M$ do

3: Set the initial state $x_{1}^{m}=x_{1}$ and
$\ell^{m}=(\left\lceil{\frac{m}{W}}\right\rceil-1)W+1$;

4: if $m=\ell^{m}$ then

5: $Q_{h}^{m}(s,a),V_{h}^{m}(s)\leftarrow H-h+1$ if $\beta>0$,
$Q_{h}^{m}(s,a),V_{h}^{m}(s)\leftarrow 0$ if $\beta<0$,
$N_{h}^{m}(s,a)\leftarrow 0$ for all
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$ ;

6: end if

7: for $h=1,2,\ldots,H$ do

8: Take an action $a_{h}^{m}\leftarrow$ $\mathop{\rm
argmax}_{a^{\prime}\in\mathcal{A}}\frac{1}{\beta}\log\\{G_{h}^{m}\left(s_{h}^{m},a^{\prime}\right)\\}$,
and observe $r_{h}^{m}(s_{h}^{m},a_{h}^{m})$ and $s_{h+1}^{m}$;

9: $N_{h}^{m}(s_{h}^{m},a_{h}^{m})\leftarrow
N_{h}^{m}(s_{h}^{m},a_{h}^{m})+1$; $t\leftarrow
N_{h}^{m}(s_{h}^{m},a_{h}^{m})$;

10: Set $\alpha_{t}=\frac{H+1}{H+t}$ and define
$\Gamma_{h,t}^{m}(s_{h}^{m},a_{h}^{m})$ as in (7);

11: $w_{h}^{m}(s_{h}^{m},a_{h}^{m})=(1-\alpha_{t})\cdot
G_{h}(s_{h}^{m},a_{h}^{m})+\alpha_{t}\cdot\left[e^{\beta\left[{r}_{h}^{m}(s_{h}^{m},a_{h}^{m})+V_{h+1}^{m}\left(s^{\prime}\right)\right]}\right]$
;

12: $G^{m}_{h}(s_{h}^{m},a_{h}^{m})\leftarrow$
$\begin{cases}&\min\left\\{e^{\beta(H-h+1)},w_{h}^{m}(s_{h}^{m},a_{h}^{m})+\alpha_{t}\Gamma_{h,t}^{m}(s_{h}^{m},a_{h}^{m})\right\\},\\\
&\hskip 142.26378pt\text{ if }\beta>0;\\\
&\max\left\\{e^{\beta(H-h+1)},w_{h}^{m}(s_{h}^{m},a_{h}^{m})-\alpha_{t}\Gamma_{h,t}^{m}(s_{h}^{m},a_{h}^{m})\right\\},\\\
&\hskip 142.26378pt\text{ if }\beta<0;\end{cases}$

13:
$V_{h}^{m}(s_{h}^{m})\leftarrow\max_{a^{\prime}\in\mathcal{A}}\frac{1}{\beta}\log
G_{h}^{m}\left(s_{h}^{m},a^{\prime}\right)$;

14: end for

15: end for

###  3.3 Theoretical results and discussions

We now present our main theoretical results for Algorithms 1 and 2.

###### Theorem 3.1

For every $\delta\in(0,1]$, with probability at least $1-\delta$ there exists
a universal constant $c_{1}>0$ (used in Algorithm 1) such that the dynamic
regret of Algorithm 1 with
$W=M^{\frac{2}{3}}B^{-\frac{2}{3}}|\mathcal{S}|^{\frac{2}{3}}|\mathcal{A}|^{\frac{1}{3}}$
is bounded by

$\displaystyle\operatorname{D-Regret(M)}\leq$
$\displaystyle\widetilde{\mathcal{O}}\left(e^{|\beta|H}|\mathcal{S}|^{\frac{2}{3}}|\mathcal{A}|^{\frac{1}{3}}H^{2}M^{\frac{2}{3}}B^{\frac{1}{3}}\right).$

###### Theorem 3.2

For every $\delta\in(0,1]$, with probability at least $1-\delta$ there exists
a universal constant $c_{2}>0$ (used in Algorithm 2) such that the dynamic
regret of Algorithm 2 with
$W=M^{\frac{2}{3}}H^{-\frac{3}{4}}B^{-\frac{2}{3}}|\mathcal{S}|^{\frac{2}{3}}|\mathcal{A}|^{\frac{1}{3}}$
is bounded by

$\displaystyle\operatorname{D-Regret(M)}\leq$
$\displaystyle\widetilde{\mathcal{O}}\left(e^{|\beta|H}|\mathcal{S}|^{\frac{1}{3}}|\mathcal{A}|^{\frac{1}{3}}H^{\frac{9}{4}}M^{\frac{2}{3}}B^{\frac{1}{3}}\right).$

The proofs of the two theorems are provided in Appendices A and B,
respectively. Note that the above results generalize those in the literature
of risk-neutral non-stationary RL. In particular, when $\beta\rightarrow 0$,
we recover the regret bounds with the same dependence on $M$ and $B$ for the
restart model-based RL (Domingues et al. 2021) and restart Q-learning (Mao et
al. 2020).

##  4 Adaptive algorithm without the knowledge of variation budget

In Theorems 3.1 and 3.2, we need to set the restart period to
$W=\mathcal{O}(B^{-\frac{2}{3}}M^{\frac{2}{3}})$, which clearly requires the
variation budget $B$ in advance. To overcome this limitation, we propose a
meta-algorithm that adaptively detects the non-stationarity without the
knowledge of $B$, while still achieving the similar dynamic regret as in
Theorems 3.1 and 3.2. In particular, we generalize the black-box approach (Wei
and Luo 2021) to the risk-sensitive RL setting and design a non-stationarity
detection based on the exponential Bellman equations (3).

Algorithm 3 Risk-sensitive MALG with Stationary Tests and Restarts (Adaptive-
ALG)

1: Inputs: ALG and its associated $\rho(\cdot)$, $\hat{n}=\log_{2}M+1$,
$\hat{\rho}(m)=6\hat{n}\log(\frac{M}{\delta})\rho(m)$;

2: for $n=0,1,\ldots,$ do

3: Set $m_{n}\leftarrow m$ and run MALG-Initialization (Algorithm 4) for the
block $[m_{n},m_{n}+2^{n}-1]$;

4: while $m<m_{n}+2^{n}$ do

5: Identify the unique active instance covering the episode $m$ and denote it
as $alg$;

6: Construct the optimistic estimator $g_{m}$ for the active instance $alg$;

7: Follow $alg$’s decision $\pi_{m}$, receive estimated value
$R_{m}=e^{\beta\sum_{h=1}^{H}r_{h}^{m}}$, and update $alg$;

8: Set $U_{m}=\begin{cases}\min_{\tau\in[m_{n},m]}{g}_{\tau},\text{ if
}\beta>0,\\\ \max_{\tau\in[m_{n},m]}{g}_{\tau},\text{ if }\beta<0;\end{cases}$

9: Perform Test1 and Test2; Increment $t\leftarrow t+1$;

10: If either test returns fail, then restart from Line 2.

11: end while

12: end for

13: Test1: Return fail if $m=alg.e$ for some order-k $alg$
and$\begin{cases}\frac{1}{2^{k}}\sum_{\tau=alg.s}^{alg.e}R_{\tau}-U_{t}\geq
9\hat{\rho}(2^{k}),\text{ if }\beta>0,\\\
U_{t}-\frac{1}{2^{k}}\sum_{\tau=alg.s}^{alg.e}R_{\tau}\geq
9\hat{\rho}(2^{k}),\text{ if }\beta<0;\end{cases}$

14: Test2: Return fail if
$\begin{cases}\frac{1}{m-m_{n}+1}\sum_{\tau=m_{n}}^{m}({g}_{\tau}-R_{\tau})\geq
3\hat{\rho}(m-m_{n}+1),\text{ if }\beta>0,\\\
\frac{1}{m-m_{n}+1}\sum_{\tau=m_{n}}^{m}(R_{\tau}-{g}_{\tau})\geq
3\hat{\rho}(m-m_{n}+1),\text{ if }\beta<0,\end{cases}$

###  4.1 Risk-sensitive non-stationary detection

We first sketch the high-level idea of the black-box reduction approach for
risk-sensitive non-stationary RL with $\beta>0$. Note that the dynamic regret
can be bounded and decomposed as follows:

$\displaystyle\operatorname{D-Regret}(M)$ $\displaystyle\leq$
$\displaystyle\frac{1}{\beta}\underbrace{\sum_{m=1}^{M}\left(e^{\beta
V_{1}^{*,m}}-e^{\beta
V_{1}^{m}}\right)}_{\textbf{R1}}+\frac{1}{\beta}\underbrace{\sum_{m=1}^{M}\left(e^{\beta
V_{1}^{m}}-e^{\beta V_{1}^{\pi^{m},m}}\right)}_{\textbf{R2}}$ (8)

where $V_{1}^{m}$ is an UCB-based optimistic estimator of the value function
as constructed in Algorithms 1 and 2. In a stationary environment with
$\beta>0$, the base algorithms, such as Algorithms 1 and 2 without the restart
mechanism (that is, $W=M$), ensure that R1 is simply non-positive and R2 is
bounded by $\widetilde{\mathcal{O}}(M^{\frac{1}{2}})$. However, in a non-
stationary environment, both terms can be substantially larger. Thus, if we
can detect the event that either of the two terms is abnormally larger than
the promised bound for a stationary environment, we learn that the environment
has changed substantially and should restart the base algorithm. This
detection can be easily performed for R2 since both $e^{\beta V_{1}^{m}}$ and
$e^{\beta V_{1}^{\pi^{m},m}}$ are observable 111More precisely,
$\sum_{m=1}^{M}e^{\beta V_{1}^{\pi^{m},m}}$ can be estimated from
$\sum_{m=1}^{M}e^{\beta\sum_{h=1}^{H}r_{h}^{m}}$ using the Azuma’s
inequality., but not for R1 since $V_{1}^{*,m}$ is unknown. To address this
issue, we fully utilize the fact that $e^{\beta V_{1}^{m}}$ is a UCB-based
optimistic estimator to facilitate non-stationary detection.

(a) $\beta>0$.

(b) $\beta<0$.

Figure 1: An illustration of the risk-sensitive non-stationarity detection.
Since both $U_{m}$ and learner’s average performance depend on the risk-
sensitive parameter $\beta$ in a non-linear way. The non-stationarity
detection relies on the choice of $\beta$ and thus the risk control and the
handling of the non-stationarity can not be separately designed.

We illustrate the idea of non-stationary detection for risk-sensitive RL in
Figure 1. Here, the value of $V_{1}^{*,m}$ drastically increases which results
to an increase in $e^{\beta V_{1}^{*,m}}$ for $\beta>0$ and an decrease in
$e^{\beta V_{1}^{*,m}}$ for $\beta<0$. If we start running another instance of
base algorithm after this environment change, then its performance will
gradually approach due to its regret guarantee in a stationary environment.
Since the optimistic estimators should always be an upper bound of the
learner’s average performance in a stationary environment for $\beta>0$ or a
lower bound of the learner’s average performance in a stationary environment
for $\beta<0$, if, at some point, we find that the new instance of the base
algorithm significantly outperformances/underperformances (depending on the
value of $\beta$) this quantity, we can infer that the environment has
changed.

###  4.2 Multi-scale ALG (MALG) and Non-stationarity Tests

To detect the non-stationarity at different scales, we schedule and run
instances of the base algorithm ALG in a randomized and multi-scale manner. In
particular, Adaptive-ALG runs MALG in a sequence of blocks with doubling
lengths. Within each block, Adaptive-ALG first initializes a MALG schedule
(Algorithm 4 in Appendix C.1), and then interacts the unique active instance
at each episode with the environment (lines 5-7 in Algorithm 3). At the end of
each episode, Adaptive-ALG performs two non-stationarity tests (line 10 in
Algorithm 3), and if either of them returns fail, the restart is triggered. We
now describe these three parts in detail below.

MALG-initialization. MALG is run for an interval of length $2^{n}$ (unless it
is terminated by the non-stationarity detection), which is called a block.
During the initialization, MALG partions the block equally into $2^{n-k}$ sub-
intervals of length $2^{k}$ for $k=0,1,\ldots,n$, and an instance of based
algorithm (denoted by ALG) is scheduled for each of these sub-intervals with
probability $\frac{\rho(2^{n})}{\rho(2^{k})}$, where $\rho$ is a non-
increasing function associated with the bound on R2 for ALG in a stationary
environment (see Appendix C.3). We refer to these instances of length $2^{k}$
as order-$k$ instances.

MALG-interaction. After the initialization, MALG starts interacting with the
environment as follows. In each episode $m$, the unique instance $alg$ that
covers this episode with the shortest length is considered as active, while
all others are regarded as inactive. MALG follows the decision of the active
instance $alg$ and updates it after receiving the feedback from the
environment. All inactive instances do not make any decisions or updates, that
is, they are paused but may be resumed at some future episode. We refer the
read to Appendix C.2 for an illustrative example for MALG procedure.

Non-stationarity detection For $\beta>0$, two non-stationarity tests are
performed for the two terms in the decomposition (4.1). In particular, Test1
prevents R1 from growing too large by testing if there is some order$-k$
instance’s interval during which the learner’s average performance
$\frac{1}{2^{k}}\sum_{\tau=alg.s}^{alg.e}R_{\tau}$ is larger than the promised
optimistic estimator $U_{m}=\min_{\tau\in[m_{n},m]}{g}_{\tau}$ (for a
stationary environment) by a certain amount. On the other hand, Test2 prevents
R2 from growing too large by directly testing if its average is large than the
promised regret bound. The two non-stationarity tests for $\beta<0$ are
similar but with $\frac{1}{2^{k}}\sum_{\tau=alg.s}^{alg.e}R_{\tau}$ and
$U_{m}$ exchanged in TEST1, as well as with $g_{\tau}$ and $R_{\tau}$
exchanged in TEST2.

###  4.3 Theoretical results and discussions

For simplicity, we denote the revised Algorithms 1 and 2 without the restart
mechanism (that is, $W=M$) as RSMB and RSQ, respectively. We now present our
main theoretical result for Algorithm 3 when the base algorithms are RSMB and
RSQ, respectively.

###### Theorem 4.1

For every $\delta\in(0,1]$, with probability at least $1-\delta$ it holds for
Algorithm 3 that

$\displaystyle\operatorname{D-Regret(M)}\leq\begin{cases}&\widetilde{\mathcal{O}}\left(e^{|\beta|H}|S|^{\frac{2}{3}}|A|^{\frac{1}{3}}H^{2}M^{\frac{2}{3}}B^{\frac{1}{3}}\right),\\\
&\hskip 85.35826pt\text{if ALG is RSMB},\\\
&\widetilde{\mathcal{O}}\left(e^{|\beta|H}|S|^{\frac{2}{3}}|A|^{\frac{1}{3}}H^{\frac{5}{3}}M^{\frac{2}{3}}B^{\frac{1}{3}}\right),\\\
&\hskip 85.35826pt\text{if ALG is RSQ}.\end{cases}$

The above results show that the dynamic regret bound of the adaptive Algorithm
3 (almost) matches that of the restart Algorithms 1-2 that require the
knowledge of the variation budget. The proof of Theorem 4.1 relies on the
results in Theorems 3.1-2 and is provided in Appendix C.4.

##  5 Lower bound

We now present a lower bound on the dynamic regret which complements the upper
bounds in Theorems 3.1, 3.2 and 4.1.

###### Theorem 5.1

For sufficiently large $M$, there exists an instance of non-stationary MDP
with $H$ horizons, state space $\mathcal{S}$, action space $\mathcal{A}$ and
variation budget $B$ such that

$\displaystyle\operatorname{D-Regret(M)}\geq$
$\displaystyle{{\Omega}}\left(\frac{e^{\frac{2|\beta|H}{3}}-1}{|\beta|}|\mathcal{S}|^{\frac{1}{3}}|\mathcal{A}|^{\frac{1}{3}}M^{\frac{2}{3}}B^{\frac{1}{3}}\right).$

Theorem 5.1 shows that the exponential dependence on $|\beta|$ and $H$ in
Theorems 3.1, 3.2 and 4.1 is essentially indispensable and that the results in
Theorems 3.1, 3.2 and 4.1 are nearly optimal in their dependence on
$|\mathcal{A}|,M$ and $B$. When $\beta\rightarrow 0$, we recover the existing
lower bound for the non-stationary risk-neutral episodic MDP problems (Mao et
al. 2020).

The proof is given in Appendix C.4. In the proof, the hard instance we
construct is a non-stationary MDP with piecewise constant dynamics on each
segment of the horizon, and its dynamics experience an abrupt change at the
beginning of each new segment. In each segment, we construct a
$|\mathcal{S}||\mathcal{A}|$-arm bandit model with Bernoulli reward for each
arm. This bandit model can be seen as a special case of our episodic MDP
problem, and then we show the expected regret, in terms of the logarithmic-
exponential objective, that any bandit algorithm has to incur.

##  6 Risk Control Under the Non-stationarity

Risk control in non-stationary RL is more challenging since the rewards and
dynamics are time-varying and unknown. In this section, we discuss some key
ideas behind our methods and proofs.

Normalized dynamics estimation in model-based algorithm. In model-based
algorithms for non-stationary risk-neutral RL, the un-normalized dynamics
estimation (Domingues et al. 2021; Ding and Lavaei 2022) is sufficient for
achieving a near-optimal regret because the effect of the model estimation
error due to the “unnormalization” on the dynamic regret is little. However,
it is critical to use the normalized dynamics estimation (5a) in Algorithm 1.
This is because that a small model estimation error due to the
“unnormalization” may be amplified when $\beta\rightarrow 0$. We note that the
stationary version of our Algorithm 1 is also the first model-based algorithm
with a theoretical guarantee for stationary risk-sensitive RL problems in the
literature.

Multiplicative feature of the exponential Bellman equation. The multiplicative
feature of the exponential Bellman equation will involve the policy evaluation
error as multiplicative terms. These terms are easy to bound in a stationary
environment in light of the optimistic estimator of the exponential value
function. However, due to the non-stationary drifting of the environment, the
estimator $V_{h}^{m}$ may no longer be an optimistic estimator and the errors
of the optimistic estimator are all in the form of a multiplicative way due to
the nature of the exponential Bellman equation. We need to introduce
additional terms to guarantee each multiplicative terms are non-negative as in
the proof of Theorem 3.2.

Non-stationarity detection on the exponential value functions. Different from
non-stationarity detection for risk-neutral RL (Wei and Luo 2021), we design
non-stationarity detection mechanism for the exponential value functions (3)
instead of the value functions (1) in Algorithm 3. This is because the non-
linearity of the risk-sensitive value function makes it difficult to obtain
its unbiased estimation, which is needed in the design of non-stationary
detection mechanism.

Separation design of the risk-control and the non-stationarity. When the
variation budget is known, the risk-control and the handling of the non-
stationarity can be separately designed in the algorithm, that is, the restart
frequency in Algorithms 1 and 2 does not depend on the risk parameter $\beta$
and only depends on the non-stationarity of the environment $B$. If we know
the environment’s variation budget in advance, then we can schedule the
restart frequency ahead no matter the risk-sensitivity. On the other hand,
without such knowledge of the variation budget, the adaptive non-stationary
detection needs to take into account the risk parameter $\beta$ because the
promised regret bound, the optimistic estimator, and the unbiased sample of
the exponential value functions all depend on $\beta$.

##  7 Conclusion and future work

In this paper, we provide strong theoretical analyses for the non-stationary
risk-sensitive RL problem, which is motivated by various risk-sensitive
applications. We propose two restart-based algorithms that require the
knowledge of the variation budget, as well as a black-box approach to turn a
certain risk-sensitive RL algorithm in a (near-)stationary environment into
another algorithm in a non-stationary environment without requiring the
knowledge of the variation budge. The dynamic regret bounds of these
algorithms are obtained and a lower bound is established to verify the near-
optimality of the proposed upper bounds. Our results also reveal the condition
under which the risk control and the handling of the non-stationarity can be
separately designed in the algorithm.

One important future direction lies in extending our results to other notions
of risk, such as the general coherent risk measures (Artzner et al. 1999).
Furthermore, it is useful to study how to adjust the risk sensitivity
parameter adaptively in a non-stationary environment.

## References

  * Abbasi-Yadkori, Pál, and Szepesvári (2011) Abbasi-Yadkori, Y.; Pál, D.; and Szepesvári, C. 2011.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24: 2312–2320.
  * 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.
  * Auer, Gajane, and Ortner (2019) Auer, P.; Gajane, P.; and Ortner, R. 2019.  Adaptively tracking the best bandit arm with an unknown number of distribution changes.  In _Conference on Learning Theory_ , 138–158. PMLR.
  * Bäuerle and Rieder (2014) Bäuerle, N.; and Rieder, U. 2014.  More risk-sensitive Markov decision processes.  _Mathematics of Operations Research_ , 39(1): 105–120.
  * Borkar (2001) Borkar, V. S. 2001.  A sensitivity formula for risk-sensitive cost and the actor–critic algorithm.  _Systems & Control Letters_, 44(5): 339–346.
  * Borkar (2002) Borkar, V. S. 2002.  Q-learning for risk-sensitive control.  _Mathematics of operations research_ , 27(2): 294–311.
  * Borkar and Meyn (2002) Borkar, V. S.; and Meyn, S. P. 2002.  Risk-sensitive optimal control for Markov decision processes with monotone cost.  _Mathematics of Operations Research_ , 27(1): 192–209.
  * Cavazos-Cadena and Fernández-Gaucherand (2000) Cavazos-Cadena, R.; and Fernández-Gaucherand, E. 2000.  The vanishing discount approach in Markov chains with risk-sensitive criteria.  _IEEE Transactions on Automatic Control_ , 45(10): 1800–1816.
  * Chen et al. (2019) Chen, Y.; Lee, C.-W.; Luo, H.; and Wei, C.-Y. 2019.  A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free.  In _Conference on Learning Theory_ , 696–726. PMLR.
  * Cheung, Simchi-Levi, and Zhu (2020) Cheung, W. C.; Simchi-Levi, D.; and Zhu, R. 2020.  Reinforcement learning for non-stationary Markov decision processes: The blessing of (more) optimism.  In _International Conference on Machine Learning_ , 1843–1854. PMLR.
  * Chow and Ghavamzadeh (2014) Chow, Y.; and Ghavamzadeh, M. 2014.  Algorithms for CVaR optimization in MDPs.  _Advances in neural information processing systems_ , 27.
  * Coraluppi and Marcus (1999) Coraluppi, S. P.; and Marcus, S. I. 1999.  Risk-sensitive and minimax control of discrete-time, finite-state Markov decision processes.  _Automatica_ , 35(2): 301–309.
  * 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.
  * Di Castro, Tamar, and Mannor (2012) Di Castro, D.; Tamar, A.; and Mannor, S. 2012.  Policy gradients with variance related risk criteria.  _arXiv preprint arXiv:1206.6404_.
  * Di Masi and Stettner (1999) Di Masi, G. B.; and Stettner, L. 1999.  Risk-sensitive control of discrete-time Markov processes with infinite horizon.  _SIAM Journal on Control and Optimization_ , 38(1): 61–78.
  * Ding and Lavaei (2022) Ding, Y.; and Lavaei, J. 2022.  Provably Efficient Primal-Dual Reinforcement Learning for CMDPs with Non-stationary Objectives and Constraints.  _arXiv preprint arXiv:2201.11965_.
  * Domingues et al. (2021) Domingues, O. D.; Ménard, P.; Pirotta, M.; Kaufmann, E.; and Valko, M. 2021\.  A kernel-based approach to non-stationary reinforcement learning in metric spaces.  In _International Conference on Artificial Intelligence and Statistics_ , 3538–3546. 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.
  * 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.  _arXiv preprint arXiv:2006.13827_.
  * Fei, Yang, and Wang (2021) Fei, Y.; Yang, Z.; and Wang, Z. 2021.  Risk-sensitive reinforcement learning with function approximation: A debiasing approach.  In _International Conference on Machine Learning_ , 3198–3207. PMLR.
  * Fernández-Gaucherand and Marcus (1997) Fernández-Gaucherand, E.; and Marcus, S. I. 1997.  Risk-sensitive optimal control of hidden Markov models: Structural results.  _IEEE Transactions on Automatic Control_ , 42(10): 1418–1422.
  * Fleming and McEneaney (1992) Fleming, W. H.; and McEneaney, W. M. 1992.  Risk sensitive optimal control and differential games.  In _Stochastic theory and adaptive control_ , 185–197. Springer.
  * Fleming and McEneaney (1995) Fleming, W. H.; and McEneaney, W. M. 1995.  Risk-sensitive control on an infinite time horizon.  _SIAM Journal on Control and Optimization_ , 33(6): 1881–1915.
  * Garcıa and Fernández (2015) Garcıa, J.; and Fernández, F. 2015.  A comprehensive survey on safe reinforcement learning.  _Journal of Machine Learning Research_ , 16(1): 1437–1480.
  * Hernández-Hernández and Marcus (1996) Hernández-Hernández, D.; and Marcus, S. I. 1996.  Risk sensitive control of Markov processes in countable state space.  _Systems & control letters_, 29(3): 147–155.
  * Howard and Matheson (1972) Howard, R. A.; and Matheson, J. E. 1972.  Risk-sensitive Markov decision processes.  _Management science_ , 18(7): 356–369.
  * Jin et al. (2018) Jin, C.; Allen-Zhu, Z.; Bubeck, S.; and Jordan, M. I. 2018.  Is Q-learning provably efficient?  _Advances in neural information processing systems_ , 31.
  * La and Ghavamzadeh (2013) La, P.; and Ghavamzadeh, M. 2013.  Actor-critic algorithms for risk-sensitive MDPs.  _Advances in neural information processing systems_ , 26.
  * Lattimore and Szepesvári (2020) Lattimore, T.; and Szepesvári, C. 2020.  _Bandit algorithms_.  Cambridge University Press.
  * Man et al. (2014) Man, C. D.; Micheletto, F.; Lv, D.; Breton, M.; Kovatchev, B.; and Cobelli, C. 2014\.  The UVA/PADOVA type 1 diabetes simulator: new features.  _Journal of diabetes science and technology_ , 8(1): 26–34.
  * Mao et al. (2020) Mao, W.; Zhang, K.; Zhu, R.; Simchi-Levi, D.; and Başar, T. 2020.  Model-Free Non-Stationary RL: Near-Optimal Regret and Applications in Multi-Agent RL and Inventory Control.  _arXiv preprint arXiv:2010.03161_.
  * Markowitz (1968) Markowitz, H. M. 1968.  Portfolio selection.  In _Portfolio selection_. Yale university press.
  * Moody and Saffell (2001) Moody, J.; and Saffell, M. 2001.  Learning to trade via direct reinforcement.  _IEEE transactions on neural Networks_ , 12(4): 875–889.
  * Niv et al. (2012) Niv, Y.; Edlund, J. A.; Dayan, P.; and O’Doherty, J. P. 2012.  Neural prediction errors reveal a risk-sensitive reinforcement-learning process in the human brain.  _Journal of Neuroscience_ , 32(2): 551–562.
  * Osogami (2012) Osogami, T. 2012.  Robustness and risk-sensitivity in Markov decision processes.  _Advances in Neural Information Processing Systems_ , 25.
  * Shen, Stannat, and Obermayer (2013) Shen, Y.; Stannat, W.; and Obermayer, K. 2013.  Risk-sensitive Markov control processes.  _SIAM Journal on Control and Optimization_ , 51(5): 3652–3672.
  * Tamar et al. (2015) Tamar, A.; Chow, Y.; Ghavamzadeh, M.; and Mannor, S. 2015.  Policy gradient for coherent risk measures.  _Advances in neural information processing systems_ , 28.
  * Tamar, Glassner, and Mannor (2015) Tamar, A.; Glassner, Y.; and Mannor, S. 2015.  Optimizing the CVaR via sampling.  In _Twenty-Ninth AAAI Conference on Artificial Intelligence_.
  * Touati and Vincent (2020) Touati, A.; and Vincent, P. 2020.  Efficient learning in non-stationary linear Markov decision processes.  _arXiv preprint arXiv:2010.12870_.
  * Wei and Luo (2021) Wei, C.-Y.; and Luo, H. 2021.  Non-stationary reinforcement learning without prior knowledge: An optimal black-box approach.  In _Conference on Learning Theory_ , 4300–4354. PMLR.
  * Zhao et al. (2020) Zhao, P.; Zhang, L.; Jiang, Y.; and Zhou, Z.-H. 2020.  A simple approach for non-stationary linear bandits.  In _International Conference on Artificial Intelligence and Statistics_ , 746–755. PMLR.
  * Zhong, Yang, and Szepesvári (2021) Zhong, H.; Yang, Z.; and Szepesvári, Z. W. C. 2021.  Optimistic Policy Optimization is Provably Efficient in Non-stationary MDPs.  _arXiv preprint arXiv:2110.08984_.
  * Zhou et al. (2020) Zhou, H.; Chen, J.; Varshney, L. R.; and Jagmohan, A. 2020.  Nonstationary reinforcement learning with linear function approximation.  _arXiv preprint arXiv:2010.04244_.

##  Appendix A Proof of Theorem 3.1

###  A.1 Preliminaries

First, we set some notations and definitions. Define
$\iota:=\log(6H|\mathcal{S}||\mathcal{A}|W/p)$ for a given $p\in(0,1]$. We
adopt the shorthand notations
$\mathbb{1}_{h}^{m}(s,a):=\mathbb{1}\left\\{\left(s_{h}^{m},a_{h}^{m}\right)=(s,a)\right\\}$
and $r_{h}^{m}:=r_{h}\left(s_{h}^{m},a_{h}^{m}\right)$ for
$(m,h)\in[M]\times[H]$. The epoch is defined as an interval that starts at the
first episode after a restart and ends at the first time when the restart is
triggered. In Algorithm 1, the restart mechanism divides $M$ episodes into
$\left\lceil{\frac{M}{W}}\right\rceil$ epochs.

For every $(m,h)\in[M]\times[H]$, and
$\left(s,a,s^{\prime}\right)\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$,
we define two visitation counters $N_{h}^{m}\left(s,a,s^{\prime}\right)$ and
$N_{h}^{m}(x,a)$ at step $h$ in episode $m$ as follows:

$\displaystyle\begin{aligned}
N_{h}^{m}\left(s,a,s^{\prime}\right)=&\sum_{\tau=\ell^{m}}^{m-1}1\left\\{\left(s,a,s^{\prime}\right)=\left(s_{h}^{\tau},a_{h}^{\tau},s_{h+1}^{\tau}\right)\right\\},\\\
N_{h}^{m}(s,a)=&\sum_{\tau=\ell^{m}}^{m-1}1\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}.\end{aligned}$
(9a)

This allows us to estimate the transition kernel $\mathcal{P}_{h}^{m}$ and
reward function $r^{m}$ for episode $m$ using only the data from the episode
$\ell^{m}=(\left\lceil{\frac{m}{W}}\right\rceil-1)W+1$ to the episode $m$ by

$\displaystyle\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)=\frac{N_{h}^{m}\left(s,a,s^{\prime}\right)+\frac{\lambda}{|\mathcal{S}|}}{N_{h}^{m}(s,a)+\lambda},\text{
for all
}\left(s,a,s^{\prime}\right)\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$
(10a)
$\displaystyle\widehat{r}_{h}^{m}(s,a)=\frac{1}{N_{h}^{m}(s,a)+\lambda}\sum_{\tau=\ell^{m}}^{m-1}1\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}r^{\tau}_{h}\left(s_{h}^{\tau},a_{h}^{\tau}\right),\text{
for all }(s,a)\in\mathcal{S}\times\mathcal{A},$ (10b)

where $\lambda>0$ is the regularization parameter. We denote by $V_{h}^{m}$,
$G_{h}^{m},\Gamma_{h}^{m}$ the values of $V_{h},G_{h},\Gamma_{h}$ after the
updates in step $h$ of episode $m$, respectively. We also set
$Q_{h}^{m}=\frac{1}{\beta}\log\left\\{G_{h}^{m}\right\\}.$

Let us fix a pair $(s,a)\in\mathcal{S}\times\mathcal{A}$. Recall from
Algorithm 1 that

$w_{h}^{m}(s,a)=\sum_{s^{\prime}}\hat{\mathcal{P}}_{h}^{m}(s^{\prime}\mid
s,a)\left[e^{\beta\left[\hat{r}_{h}^{m}(s,a)+V_{h+1}^{m}\left(s^{\prime}\right)\right]}\right].$

We define

$\displaystyle q_{h,1}^{m,+}(s,a)$
$\displaystyle:=\begin{cases}w_{h}^{m}(s,a)+\Gamma_{h}^{m}(s,a),&\text{ if
}\beta>0\\\ w_{h}^{m}(s,a)-\Gamma_{h}^{m}(s,a),&\text{ if }\beta<0\end{cases}$
$\displaystyle q_{h,1}^{m}(s,a)$
$\displaystyle:=\begin{cases}\min\left\\{q_{h,1}^{m,+}(s,a),e^{\beta(H-h+1)}\right\\},&\text{
if }\beta>0\\\
\max\left\\{q_{h,1}^{m,+}(s,a),e^{\beta(H-h+1)}\right\\},&\text{ if
}\beta<0\end{cases}$

and

$\displaystyle
q_{h,2}^{m}(s,a):=\mathbb{E}_{s^{\prime}\sim\mathcal{P}_{h}^{m}\left(\cdot\mid
s,a\right)}\left[e^{\beta\left[r_{h}^{m}(s,a)+V_{h+1}^{m}\left(s^{\prime}\right)\right]}\right],$
(11)

as well as the following for a policy $\pi$,

$\displaystyle
q_{h,3}^{m,\pi}(s,a):=\mathbb{E}_{s^{\prime}\sim\mathcal{P}_{h}^{m}\left(\cdot\mid
s,a\right)}\left[e^{\beta\left[r_{h}^{m}(s,a)+V_{h+1}^{\pi,m}\left(s^{\prime}\right)\right]}\right]$
(12)

###  A.2 Model prediction errors

###### Lemma A.1

Define
$\overline{\mathcal{V}}_{h+1}:=\left\\{\bar{V}_{h+1}:\mathcal{S}\rightarrow\mathbb{R}\mid\forall
s\in\mathcal{S},\bar{V}_{h+1}(s)\in[0,H-h]\right\\}$. For any $p\in(0,1]$,
with probability $1-p/2$, we have

$\displaystyle\left|\sum_{s^{\prime}\in\mathcal{S}}\left(\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}\right)\right|$
$\displaystyle\leq$
$\displaystyle\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}$

for every $(s,a,m,h)\in\mathcal{S}\times\mathcal{A}\times[M]\times[H]$ and
$\bar{V}\in\overline{\mathcal{V}}_{h+1}$, where $\Gamma_{h}^{m}$ is defined in
(6).

Proof. For the ease of notation, we denote
$\sum_{s^{\prime}\in\mathcal{S}}\mathcal{P}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}$
as
$\left(\mathcal{P}_{h}^{m}e^{\beta\left[r_{h}^{m}+\bar{V}\right]}\right)(s,a)$.
Then, for every $\bar{V}\in\mathcal{V}_{h+1}$, we consider the difference
between
$\sum_{s^{\prime}\in\mathcal{S}}\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid\cdot,\cdot\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}$
and
$\sum_{s^{\prime}\in\mathcal{S}}\mathcal{P}_{h}^{m}\left(s^{\prime}\mid\cdot,\cdot\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}$
as follows:

$\displaystyle\left(N_{h}^{m}(s,a)+\lambda\right)\left|\sum_{s^{\prime}\in\mathcal{S}}\left(\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}\right)\right|$
(13) $\displaystyle=$
$\displaystyle\left|\sum_{s^{\prime}\in\mathcal{S}}\left(N_{h}^{m}\left(s,a,s^{\prime}\right)+\frac{\lambda}{|\mathcal{S}|}\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\left(N_{h}^{m}(s,a)+\lambda\right)\left(\mathcal{P}_{h}^{m}e^{\beta\left[r_{h}^{m}+\bar{V}\right]}\right)(s,a)\right|$
$\displaystyle\leq$
$\displaystyle\left|\sum_{s^{\prime}\in\mathcal{S}}N_{h}^{m}\left(s,a,s^{\prime}\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-N_{h}^{m}(s,a)\left(\mathcal{P}_{h}^{m}e^{\beta\left[r_{h}^{m}+\bar{V}\right]}\right)(s,a)\right|$
$\displaystyle+\lambda\left|\frac{1}{\left|\mathcal{S}\right|}\sum_{s^{\prime}\in\mathcal{S}}e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}e^{\beta\left[r_{h}^{m}+\bar{V}\right]}(s,a)\right|$
$\displaystyle=$
$\displaystyle\left|\sum_{\tau=\ell^{m}_{Q}}^{m-1}\mathbb{1}\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}\left(e^{\beta\left[r_{h}^{m}(s_{h}^{\tau},a_{h}^{\tau})+\bar{V}\left(s_{h+1}^{\tau}\right)\right]}-\left(\mathcal{P}_{h}^{m}e^{\beta\left[r_{h}^{m}+\bar{V}\right]}\right)(s,a)\right)\right|$
$\displaystyle+\lambda\left|\frac{1}{\left|\mathcal{S}\right|}\sum_{s^{\prime}\in\mathcal{S}}e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}e^{\beta\left[r_{h}^{m}+\bar{V}\right]}(s,a)\right|$
$\displaystyle=$
$\displaystyle\left|\sum_{\tau=\ell^{m}_{Q}}^{m-1}\mathbb{1}\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}e^{\beta
r_{h}^{m}(s_{h}^{\tau},a_{h}^{\tau})}\left(e^{\beta\bar{V}\left(s_{h+1}^{\tau}\right)}-\left(\mathcal{P}_{h}^{m}e^{\beta\bar{V}}\right)(s,a)\right)\right|$
$\displaystyle+\lambda\left|\frac{1}{\left|\mathcal{S}\right|}\sum_{s^{\prime}\in\mathcal{S}}e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}e^{\beta\left[r_{h}^{m}+\bar{V}\right]}(s,a)\right|$
$\displaystyle\leq$
$\displaystyle\left|\sum_{\tau=\ell^{m}_{Q}}^{m-1}\mathbb{1}\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}e^{\beta
r_{h}^{m}(s_{h}^{\tau},a_{h}^{\tau})}\left(e^{\beta\bar{V}\left(s_{h+1}^{\tau}\right)}-\left(\mathcal{P}_{h}^{\tau}e^{\beta\bar{V}}\right)(s,a)\right)\right|$
(14)
$\displaystyle+\left|\sum_{\tau=\ell^{m}_{Q}}^{m-1}\mathbb{1}\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}e^{\beta
r_{h}^{m}(s_{h}^{\tau},a_{h}^{\tau})}\left(\left(\mathcal{P}_{h}^{\tau}e^{\beta\bar{V}}\right)(s,a)-\left(\mathcal{P}_{h}^{m}e^{\beta\bar{V}}\right)(s,a)\right)\right|$
(15)
$\displaystyle+\lambda\left|\frac{1}{\left|\mathcal{S}\right|}\sum_{s^{\prime}\in\mathcal{S}}e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}e^{\beta\left[r_{h}^{m}+\bar{V}\right]}(s,a)\right|$
(16)

for every $(m,h)\in[M]\times[H]$ and $(s,a)\in\mathcal{S}\times\mathcal{A}$.

To analyze the term in (14), we let
$\eta_{h}^{\tau}:=e^{\beta[r_{h}^{m}(s_{h}^{\tau},a_{h}^{\tau})+\bar{V}\left(s_{h+1}^{\tau}\right)]}-\left(\mathcal{P}_{h}^{\tau}e^{\beta[r_{h}^{m}+\bar{V}]}\right)(s_{h}^{\tau},a_{h}^{\tau}).$
Conditioning on the filtration $\mathcal{F}_{h,1}^{m}$, the term
$\eta_{h}^{\tau}$ is a zero-mean and $\left|e^{\beta(H-h+1)}-1\right|$-sub-
Gaussian random variable. By Lemma E.2, we use $Y=\lambda I$ and
$X_{\tau}=\mathbb{1}\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}$
and thus with probability at least $1-\delta$ it holds for every $m\in[M]$
that

$\displaystyle\left(N_{h}^{m}(s,a)+\lambda\right)^{-1/2}\left|\sum_{\tau=\ell^{m}_{Q}}^{m-1}\mathbb{1}\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}\left(e^{\beta[r_{h}^{m}(s_{h}^{\tau},a_{h}^{\tau})+\bar{V}]\left(s_{h+1}^{\tau}\right)}-\left(\mathcal{P}_{h}^{\tau}e^{\beta[r_{h}^{m}+\bar{V}]}\right)(s_{h}^{\tau},a_{h}^{\tau})\right)\right|$
$\displaystyle\leq\sqrt{\frac{(e^{\beta(H-h+1)}-1)^{2}}{2}\log\left(\frac{\left(N_{h}^{m}(s,a)+\lambda\right)^{1/2}\lambda^{-1/2}}{\delta}\right)}$
$\displaystyle\leq\sqrt{\frac{(e^{\beta(H-h+1)}-1)^{2}}{2}\log\left(\frac{W}{\delta}\right)}$

where $W$ is the restart period.

For the term in (15), by the definition of $B_{\mathcal{P},\mathcal{E}}$ and
$N_{h}^{m}$, we have

$\displaystyle\left|\sum_{\tau=\ell^{m}_{Q}}^{m-1}\mathbb{1}\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}\left(\left(\mathcal{P}_{h}^{\tau}e^{\beta[r_{h}^{m}+\bar{V}]}\right)(s,a)-\left(\mathcal{P}_{h}^{m}e^{\beta[r_{h}^{m}+\bar{V}]}\right)(s,a)\right)\right|$
$\displaystyle=$
$\displaystyle\left|\sum_{\tau=\ell^{m}_{Q}}^{m-1}\mathbb{1}\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}\left(\left(\mathcal{P}_{h}^{\tau}\left(e^{\beta[r_{h}^{m}+\bar{V}]}-{1}\right)\right)(s,a)-\left(\mathcal{P}_{h}^{m}\left(e^{\beta[r_{h}^{m}+\bar{V}]}-{1}\right)\right)(s,a)\right)\right|$
$\displaystyle\leq$
$\displaystyle\left|\sum_{\tau=\ell^{m}_{Q}}^{m-1}\mathbb{1}\left\\{(s,a)=\left(s_{h}^{\tau},a_{h}^{\tau}\right)\right\\}\right|\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}$
$\displaystyle\leq$
$\displaystyle\left(N_{h}^{m}(s,a)+\lambda\right)\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}.$

where the first equality is due to
$\mathcal{P}_{h}^{m}{1}=\mathcal{P}_{h}^{\tau}{1}$ for all
$\tau\in[\ell^{m},m-1]$. For the term in (16), we have

$\displaystyle\lambda\left|\frac{1}{\left|\mathcal{S}\right|}\sum_{s^{\prime}\in\mathcal{S}}e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}e^{\beta\left[r_{h}^{m}+\bar{V}\right]}(s,a)\right|\leq$
$\displaystyle\frac{\lambda}{\left|\mathcal{S}\right|}\sum_{s^{\prime}\in\mathcal{S}}\left|e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}e^{\beta\left[r_{h}^{m}+\bar{V}\right]}(s,a)\right|$
$\displaystyle\leq$ $\displaystyle{\lambda}\left|e^{\beta(H-h+1)}-1\right|.$

By returning to (13) and setting $\lambda=1$, with probability at least
$1-\delta$ it holds that

$\displaystyle\left|\sum_{s^{\prime}\in\mathcal{S}}\left(\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}\right)\right|$
$\displaystyle\leq$
$\displaystyle\left(N_{h}^{m}(s,a)+\lambda\right)^{-\frac{1}{2}}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\frac{1}{2}\left(\log\left(\frac{W}{\delta}\right)\right)}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+\left|e^{\beta(H-h+1)}-1\right|$
$\displaystyle\leq$ $\displaystyle
C_{1}\left(N_{h}^{m}(s,a)+\lambda\right)^{-\frac{1}{2}}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\left(\log\left(\frac{W}{\delta}\right)\right)}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}$

for all $m\in[M]$ and for some constant $C_{1}>1$.

Furthermore, let
$d\left(V,V^{\prime}\right)=\max_{s\in\mathcal{S}}\left|V(s)-V^{\prime}(s)\right|$
be a distance on $\mathcal{V}_{h+1}.$ For every $\epsilon$, an
$\epsilon$-covering $\mathcal{V}^{\epsilon}_{h+1}$ of $\mathcal{V}_{h+1}$ with
respect to distance $d(\cdot,\cdot)$ satisfies
$\left|\mathcal{V}_{h+1}^{\epsilon}\right|\leq\left(\frac{1}{\epsilon}\right)^{|\mathcal{S}|}.$
Then, for every $V\in\mathcal{V}_{h+1}$, there exists
$V^{\prime}\in\mathcal{V}_{h+1}^{\epsilon}$ such that
$\max_{s\in\mathcal{S}}\left|V(s)-V^{\prime}(s)\right|\leq\epsilon$, which
further implies that

$\displaystyle\max_{s,a,s^{\prime}}\left|e^{\beta\left[r_{h}^{m}(s,a)+{V}\left(s^{\prime}\right)\right]}-e^{\beta\left[r_{h}^{m}(s,a)+{V}^{\prime}\left(s^{\prime}\right)\right]}\right|\leq$
$\displaystyle g_{h}(\beta)\epsilon,$

where

$\displaystyle g_{h}(\beta)=\begin{cases}e^{\beta(H-h+1)}\beta,&\text{ if
}\beta>0,\\\ -\beta,&\text{ if }\beta<0.\end{cases}$ (17)

Thus, by the triangle inequality and $\eqref{eq: hat P V -P V tabular}$, we
have

$\displaystyle\left|\sum_{s^{\prime}\in\mathcal{S}}\left(\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+{V}\left(s^{\prime}\right)\right]}\right)\right|$
$\displaystyle\leq$
$\displaystyle\left|\sum_{s^{\prime}\in\mathcal{S}}\left(\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+{V}^{\prime}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+{V}^{\prime}\left(s^{\prime}\right)\right]}\right)\right|+2g_{h}(\beta)\beta\epsilon$
$\displaystyle\leq$ $\displaystyle
C_{1}\left(N_{h}^{m}(s,a)+\lambda\right)^{-1/2}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\log\left(\frac{W}{\delta}\right)}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+2g_{h}(\beta)\epsilon.$

Then, by choosing
$\delta=(p/2)/\left(\left|\mathcal{V}^{\epsilon}_{h+1}\right|H\left|\mathcal{S}\right|\left|\mathcal{A}\right|\right)$,
$\epsilon=\frac{1}{4\sqrt{W}}$, and taking a union bound over
$V\in\mathcal{V}_{h+1}^{\epsilon}$ and
$(s,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$, it holds with probability
at least $1-p/2$ that

$\displaystyle\sup_{V\in\mathcal{V}_{h+1}}\left\\{\left|\sum_{s^{\prime}\in\mathcal{S}}\left(\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+{V}\left(s^{\prime}\right)\right]}\right)\right|\right\\}$
$\displaystyle\leq$ $\displaystyle
C_{1}\left(N_{h}^{m}(s,a)+\lambda\right)^{-1/2}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\left(\log\left(\frac{6W\left|\mathcal{V}^{\epsilon}_{h+1}\right|H\left|\mathcal{S}\right|\left|\mathcal{A}\right|}{p}\right)\right)}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}$
$\displaystyle+2g_{h}(\beta)\epsilon$ $\displaystyle\leq$ $\displaystyle
C_{1}\left(N_{h}^{m}(s,a)+\lambda\right)^{-1/2}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\left|\mathcal{S}\right|\left(\log\left(\frac{6WH\left|\mathcal{S}\right|\left|\mathcal{A}\right|}{p}\right)\right)}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}$
$\displaystyle+g_{h}(\beta)W^{-1/2}$ $\displaystyle\leq$
$\displaystyle\left(C_{1}\left|e^{\beta(H-h+1)}-1\right|+g_{h}(\beta)\right)\left(N_{h}^{m}(s,a)+\lambda\right)^{-1/2}\sqrt{\left|\mathcal{S}\right|\left(\log\left(\frac{6WH\left|\mathcal{S}\right|\left|\mathcal{A}\right|}{p}\right)\right)}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}$
$\displaystyle\leq$ $\displaystyle
C_{1}\left(\left|e^{\beta(H-h+1)}-1\right|+g_{h}(\beta)\right)\left(N_{h}^{m}(s,a)+\lambda\right)^{-1/2}\sqrt{\left|\mathcal{S}\right|\left(\log\left(\frac{6WH\left|\mathcal{S}\right|\left|\mathcal{A}\right|}{p}\right)\right)}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}$

for every $(s,a,m,h)\in\mathcal{S}\times\mathcal{A}\times[M]\times[H]$. By our
choice of $\Gamma_{h}^{m}$, with probability at least $1-p/2$ it holds that

$\displaystyle\left|\sum_{s^{\prime}\in\mathcal{S}}\left(\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}\right)\right|$
$\displaystyle\leq\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}$

for every $(s,a,m,h)\in\mathcal{S}\times\mathcal{A}\times[M]\times[H]$. $\Box$

###### Lemma A.2

For every $(s,a,m,h)\in\mathcal{S}\times\mathcal{A}\times[M]\times[H]$ and
$\bar{V}\in\overline{\mathcal{V}}_{h+1}$, we have

$\displaystyle\left|\sum_{s^{\prime}\in\mathcal{S}}\left({\widehat{\mathcal{P}}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[\hat{r}_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}\right)\right|\leq\Gamma_{h}^{m}+g_{h}(\beta)B_{r,\mathcal{E}}$

where $g_{h}(\beta)$ is defined in (17).

Proof. Since

$\displaystyle|e^{\beta x}-e^{\beta y}|\leq\begin{cases}\beta e^{\beta
u}|x-y|,&\text{ if }\beta>0,\\\ -\beta|x-y|,&\text{ if }\beta<0\end{cases}$

for every $0\leq x\leq u$ and $0\leq y\leq u$ where $u>0$ is some constant, it
holds that

$\displaystyle\left|\sum_{s^{\prime}\in\mathcal{S}}\left({\widehat{\mathcal{P}}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[\hat{r}_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[r_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}\right)\right|$
$\displaystyle\leq$ $\displaystyle
g_{h}(\beta)\left|\hat{r}_{h}^{m}(s,a)-{r}_{h}^{m}(s,a)\right|.$ (18)

Furthermore, by our estimation $\hat{r}_{h}^{m}(x,a)$, we have

$\displaystyle\left|\hat{r}_{h}^{m}(x,a)-r_{h}^{m}(x,a)\right|$
$\displaystyle=$
$\displaystyle\left|\hat{r}_{h}^{m}(x,a)-r_{h}^{m}{(x,a)}\right|$
$\displaystyle=$
$\displaystyle\left(n_{h}^{m}(x,a)+\lambda\right)^{-1}\left|\sum_{\tau=\ell^{m}}^{m-1}1\left\\{(x,a)=\left(x_{h}^{\tau},a_{h}^{\tau}\right)\right\\}\left(r_{h}^{\tau}{\left(x_{h}^{\tau},a_{h}^{\tau}\right)}-r_{h}^{m}{(x,a)}\right)-\lambda
r_{h}^{m}{(x,a)}\right|$ $\displaystyle\leq$ $\displaystyle
B_{r,\mathcal{E}}+\left(n_{h}^{m}(x,a)+\lambda\right)^{-1}\left|\lambda
r_{h}^{m}{(x,a)}\right|$ $\displaystyle\leq$ $\displaystyle
B_{r,\mathcal{E}}+\left(n_{h}^{m}(x,a)+\lambda\right)^{-1}\lambda$
$\displaystyle\leq$ $\displaystyle
B_{r,\mathcal{E}}+\left(n_{h}^{m}(x,a)+\lambda\right)^{-1/2}\lambda$

By substituting the above inequality into (A.2) and setting $\lambda=1$, we
obtain the desired results. $\Box$

###### Lemma A.3

For every $p\in(0,1]$, with probability $1-p/2$, we have

$\displaystyle\left|\sum_{s^{\prime}\in\mathcal{S}}\left(\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[\hat{r}_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[{r}_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}\right)\right|$
$\displaystyle\leq$ $\displaystyle
2\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}$

where $g_{h}(\beta)$ is defined in (17), for every
$(s,a,m,h)\in\mathcal{S}\times\mathcal{A}\times[M]\times[H]$ and
$\bar{V}\in\overline{\mathcal{V}}_{h+1}$.

Proof. The proof follows from Lemma A.1, Lemma A.2 and Cauchy-Schwartz
inequality. $\Box$

###  A.3 Value difference bounds

###### Lemma A.4

Recall the definition of $\Gamma_{h}^{m}$ from Algorithm 1. For all
$(m,h,s,a)\in[M]\times[H]\times\mathcal{S}\times\mathcal{A}$, the following
statement holds with probability at least $1-p/2$:

  * •

If $\beta>0$:

$\displaystyle-\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}-g_{h}(\beta)B_{r,\mathcal{E}}\leq$
$\displaystyle\left(q_{h,1}^{m}-q_{h,2}^{m}\right)(s,a)$ $\displaystyle\leq$
$\displaystyle
4\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}.$

  * •

If $\beta<0$:

$\displaystyle-\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}-g_{h}(\beta)B_{r,\mathcal{E}}\leq$
$\displaystyle\left(q_{h,2}^{m}-q_{h,1}^{m}\right)(s,a)$ $\displaystyle\leq$
$\displaystyle
4\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}.$

(Note that $g_{h}(\beta)$ is defined in (17)).

Proof. We focus on the case of $\beta>0$ since the proof for $\beta<0$ is
similar. We first fix a tuple
$(m,h,s,a)\in[M]\times[H]\times\mathcal{S}\times\mathcal{A}$. By the
definitions of $q_{h,1}^{m,+}$ and $q_{h,2}^{m}$, one can compute

$\displaystyle\left|\left(q_{h,1}^{m,+}-2\Gamma_{h}^{m}-q_{h,2}^{m}\right)(s,a)\right|$
$\displaystyle=\left|\left(w_{h}^{m}-q_{h,2}^{m}\right)(s,a)\right|$
$\displaystyle=\left|\sum_{s^{\prime}\in\mathcal{S}}\left(\widehat{\mathcal{P}}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[\hat{r}_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}-\mathcal{P}_{h}^{m}\left(s^{\prime}\mid
s,a\right)e^{\beta\left[{r}_{h}^{m}(s,a)+\bar{V}\left(s^{\prime}\right)\right]}\right)\right|$
$\displaystyle\leq
2\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}$

where the last step holds by Lemma A.1. Then, we have

$\displaystyle-\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}-g_{h}(\beta)B_{r,\mathcal{E}}\leq$
$\displaystyle\left(q_{h,1}^{m,+}-q_{h,2}^{m}\right)(s,a)$ $\displaystyle\leq$
$\displaystyle
4\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}.$

Furthermore, if $q_{h,1}^{m,+}\leq e^{\beta(H-h+1)}$, one can write

$q_{h,1}^{m,+}-q_{h,2}^{m}=q_{h,1}^{m}-q_{h,2}^{m}\geq-\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}-g_{h}(\beta)B_{r,\mathcal{E}}.$

If $q_{h,1}^{m,+}\geq e^{\beta(H-h+1)}$, we have
$q_{h,1}^{m,+}-q_{h,2}^{m}=e^{\beta(H-h+1)}-q_{h,2}^{m}\geq 0$. In addition,
since $q_{h,1}^{m,+}\geq q_{h,1}^{m}$, it holds that
$q_{h,1}^{m}-q_{h,2}^{m}\leq q_{h,1}^{m,+}-q_{h,2}^{m}$. This completes the
proof.

$\Box$

###### Lemma A.5

On the event of Lemma A.4, for all
$(m,h,s,a)\in[M]\times[H]\times\mathcal{S}\times\mathcal{A}$ and every policy
$\pi$:

  * •

If $\beta>0$:

$e^{\beta\cdot Q_{h}^{m}(s,a)}-e^{\beta\cdot
Q_{h}^{\pi,m}(s,a)}\geq-(H-h+1)\left[\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right].$

  * •

If $\beta<0$:

$e^{\beta\cdot Q_{h}^{m}(s,a)}-e^{\beta\cdot
Q_{h}^{\pi,m}(s,a)}\leq(H-h+1)\left[\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right].$

Proof. We focus on the case of $\beta>0$ since the proof for $\beta<0$ is
similar. For the purpose of the proof, we set
$Q_{H+1}^{\pi,m}(s,a)=Q_{H+1}^{*,m}(s,a)=0$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. We fix a tuple $(m,s,a)\in$
$[M]\times\mathcal{S}\times\mathcal{A}$ and use strong induction on $h$. The
base case for $h=H+1$ is satisfied since $e^{\beta\cdot
Q_{H+1}^{m}(s,a)}=e^{\beta\cdot Q_{H+1}^{\pi,m}(s,a)}=1$ for all $m\in[M]$ by
definition. Now, we fix an index $h\in[H]$ and assume that

$e^{\beta\cdot Q_{h+1}^{m}(s,a)}-e^{\beta\cdot
Q_{h+1}^{\pi,m}(s,a)}\geq-(H-h)\left[\left|e^{\beta(H-h)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right].$

Moreover, by the induction assumption, we have

$\displaystyle e^{\beta\cdot V_{h+1}^{m}(s)}$
$\displaystyle=\max_{a^{\prime}\in\mathcal{A}}e^{\beta\cdot
Q_{h+1}^{m}\left(s,a^{\prime}\right)}$
$\displaystyle\geq\max_{a^{\prime}\in\mathcal{A}}e^{\beta\cdot
Q_{h+1}^{\pi,m}\left(s,a^{\prime}\right)}-(H-h)\left[\left|e^{\beta(H-h)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right]$
$\displaystyle\geq e^{\beta\cdot
V_{h+1}^{\pi,m}(s)}-(H-h)\left[\left|e^{\beta(H-h)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right].$
(19)

By the definitions of $q_{h,2}^{m}$ and $q_{h,3}^{m,\pi}$, it follows from
(A.3) that

$q_{h,2}^{m}-q_{h,3}^{m,\pi}\geq-(H-h)\left[\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right].$

In addition, on the event of Lemma A.4, we also have

$q_{h,1}^{m}-q_{h,2}^{m}\geq-\left[\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right].$

Therefore, it follows that

$\displaystyle\left(e^{\beta\cdot Q_{h}^{m}}-e^{\beta\cdot
Q_{h}^{\pi,m}}\right)(s,a)=$
$\displaystyle\left(q_{h,1}^{m}-q_{h,3}^{m,\pi}\right)(s,a)$ $\displaystyle=$
$\displaystyle\left(q_{h,1}^{m}-q_{h,2}^{m}\right)(s,a)+\left(q_{h,2}^{m}-q_{h,3}^{m,\pi}\right)(s,a)$
$\displaystyle\geq$
$\displaystyle-(H-h+1)\left[\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right]$

which completes the induction. $\Box$

###### Lemma A.6

For all $(m,h,s)\in[M]\times[H]\times\mathcal{S}$, policy $\pi$ and
$\delta\in(0,1]$, with probability at least $1-\delta/2$:

  * •

If $\beta>0$:

$e^{\beta\cdot V_{h}^{m}(s,a)}-e^{\beta\cdot
V_{h}^{\pi,m}(s,a)}\geq-(H-h+1)\left[\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right].$

  * •

If $\beta<0$:

$e^{\beta\cdot V_{h}^{m}(s,a)}-e^{\beta\cdot
V_{h}^{\pi,m}(s,a)}\leq(H-h+1)\left[\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right].$

Proof. The result follows from Lemma A.5 and Equation (A.3).

###  A.4 Proof of Theorem 3.1

We first consider $\beta>0$. For $h\in[H]$, we define

$\displaystyle\delta_{h}^{m}$ $\displaystyle:=e^{\beta
V_{h}^{m}\left(s_{h}^{m}\right)}-e^{\beta
V_{h}^{\pi^{m},m}\left(s_{h}^{m}\right)},$ (20a)
$\displaystyle\zeta_{h+1}^{m}$
$\displaystyle:=q_{h,2}^{m}-q_{h,3}^{m}-e^{\beta
r_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)}\delta_{h+1}^{m}$ (20b)
$\displaystyle=\left[P_{h}^{m}\left(e^{\beta\left[r_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)+V_{h+1}^{m}\left(s^{\prime}\right)\right]}-e^{\beta\left[r_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)+V_{h+1}^{\pi^{m},m}\left(s^{\prime}\right)\right]}\right)\right]\left(s_{h}^{m},a_{h}^{m}\right)-e^{\beta
r_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)}\delta_{h+1}^{m},$

where $\left[P_{h}^{m}f\right](s,a):=\mathbb{E}_{s^{\prime}\sim
P_{h}^{m}(|\cdot|s,a)}\left[f\left(s^{\prime}\right)\right]$ for every
$f:\mathcal{S}\rightarrow\mathbb{R}$ and
$(s,a)\in\mathcal{S}\times\mathcal{A}$. Then, for every
$(m,h)\in[M]\times[H]$, we have

$\displaystyle\delta_{h}^{m}\stackrel{{\scriptstyle(i)}}{{=}}$
$\displaystyle\left(e^{\beta\cdot Q_{h}^{m}}-e^{\beta\cdot
Q_{h}^{\pi^{m},m}}\right)\left(s_{h}^{m},a_{h}^{m}\right)$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{=}}$ $\displaystyle
q_{h,1}^{m}\left(s_{h}^{m},a_{h}^{m}\right)-q_{h,2}^{m}\left(s_{h}^{m},a_{h}^{m}\right)+q_{h,2}^{m}\left(s_{h}^{m},a_{h}^{m}\right)-q_{h,3}^{m}\left(s_{h}^{m},a_{h}^{m}\right)$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\leq}}$ $\displaystyle
4\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}+q_{h,2}^{m}\left(s_{h}^{m},a_{h}^{m}\right)-q_{h,3}^{m}\left(s_{h}^{m},a_{h}^{m}\right)$
$\displaystyle=$ $\displaystyle
4\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}+e^{\beta\cdot
r_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)}\delta_{h+1}^{m}+\zeta_{h+1}^{m}.$
(21)

In the above equation, step (i) holds by the construction of Algorithm 1 and
the definition of $V_{h}^{\pi^{m}}$ in Equation (2b); step (ii) holds by
Equations (11) and (12); step (iii) holds on the event of Lemma A.4; the last
step follows from the definition of $\delta_{h}^{m}$ and $\zeta_{h}^{m}$ in
Equations 20a and 20b.

Using the fact that $V_{H+1}^{m}(s)=V_{H+1}^{\pi^{m}}(s)=0$, we can expand the
recursion in Equation (21) to obtain

$\displaystyle\delta_{1}^{m}\leq$
$\displaystyle\sum_{h\in[H]}e^{\beta\sum_{i=1}^{h-1}r_{i}^{m}}\zeta_{h+1}^{m}+\sum_{h\in[H]}e^{\beta\sum_{i=1}^{h-1}r_{i}^{m}}\left(4\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right)$
$\displaystyle\leq$
$\displaystyle\sum_{h\in[H]}e^{\beta\sum_{i=1}^{h-1}r_{i}^{m}}\zeta_{h+1}^{m}+\sum_{h\in[H]}e^{\beta(h-1)}\left(4\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right).$

where the last step follows from $r_{h}^{m}(\cdot,\cdot)\in[0,1]$. Summing the
above display over $m\in[M]$ gives

$\displaystyle\sum_{m\in[M]}\delta_{1}^{m}$ $\displaystyle\leq$
$\displaystyle\sum_{m\in[M]}\sum_{h\in[H]}e^{\beta\sum_{i=1}^{h-1}r_{i}^{m}}\zeta_{h+1}^{m}+\sum_{m\in[M]}\sum_{h\in[H]}e^{\beta(h-1)}\left(4\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right)$
$\displaystyle=$
$\displaystyle\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\sum_{h\in[H]}\left(e^{\beta\sum_{i=1}^{h-1}r_{i}^{m}}\zeta_{h+1}^{m}+e^{\beta(h-1)}\left(4\Gamma_{h}^{m}+\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{h}(\beta)B_{r,\mathcal{E}}\right)\right)$
$\displaystyle=$
$\displaystyle\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\sum_{h\in[H]}\left(e^{\beta\sum_{i=1}^{h-1}r_{i}^{m}}\zeta_{h+1}^{m}+4e^{\beta(h-1)}\Gamma_{h}^{m}\right)+WH\left(\left|e^{\beta
H}-1\right|B_{\mathcal{P}}+g_{1}(\beta)B_{r}\right).$ (22)

We aim to control the terms in (22). Since
$\left\\{e^{\beta\sum_{i=1}^{h-1}r_{i}^{m}}\zeta_{h+1}^{m}\right\\}$ is a
martingale difference sequence satisfying
$\left|e^{\beta\sum_{i=1}^{h-1}r_{i}^{m}}\zeta_{h+1}^{m}\right|\leq 2|e^{\beta
H}-1|$ for all $(m,h)\in[M]\times[H]$, by the Azuma-Hoeffding inequality, we
have:

$\mathcal{P}\left(\sum_{m\in[M]}\sum_{h\in[H]}e^{\beta\sum_{i=1}^{h-1}r_{i}^{m}}\zeta_{h+1}^{m}\geq
t\right)\leq\exp\left(-\frac{t^{2}}{8HM\left(e^{\beta
H}-1\right)^{2}}\right),\quad\forall t>0.$

Hence, with probability $1-\delta/2$, it holds that

$\displaystyle\sum_{k\in[K]}\sum_{h\in[H]}e^{\beta(h-1)}\zeta_{h+1}^{m}\leq\left(e^{\beta
H}-1\right)\sqrt{2HM\log(2/\delta)}\leq 2\left(e^{\beta
H}-1\right)\sqrt{2HM\iota},$ (23)

where
$\iota=\log(6H\left|\mathcal{S}\right|\left|\mathcal{A}\right|W/\delta)$.
Furthermore, recall the definition of $\Gamma_{h}^{m}$, we can derive

$\displaystyle\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\sum_{h\in[H]}e^{\beta(h-1)}\Gamma_{h}^{m}$
$\displaystyle\leq\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\sum_{h\in[H]}\left(C_{1}\left|e^{\beta(H-h+1)}-1\right|+g_{h}(\beta)\right)\sqrt{\left|\mathcal{S}\right|\iota}\sqrt{\frac{1}{N_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)+1}}$
$\displaystyle\leq\left(C_{1}\left|e^{\beta
H}-1\right|+g_{1}(\beta)\right)\sqrt{\left|\mathcal{S}\right|\iota}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\sum_{h\in[H]}\sqrt{\frac{1}{N_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)+1}}$
$\displaystyle\stackrel{{\scriptstyle(i)}}{{\leq}}\left(C_{1}\left|e^{\beta
H}-1\right|+g_{1}(\beta)\right)\sqrt{\left|\mathcal{S}\right|\iota}\sum_{h\in[H]}\sqrt{W}\sqrt{\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\frac{1}{N_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)+1}}$
$\displaystyle\leq\left(C_{1}\left|e^{\beta
H}-1\right|+g_{1}(\beta)\right)\sqrt{\left|\mathcal{S}\right|\iota}\sqrt{2H^{2}|S||A|W\iota}$

where step (i) follows the Cauchy-Schwarz inequality and the last step holds
by the pigeonhole principle. Thus, it holds that

$\displaystyle\sum_{m\in[M]}\sum_{h\in[H]}e^{\beta(h-1)}\Gamma_{h}^{m}\leq\left(C_{1}\left|e^{\beta
H}-1\right|+e^{\beta
H}\left|\beta\right|\right)\sqrt{2H^{2}|S|^{2}|A|\iota^{2}}\frac{M}{\sqrt{W}}.$
(24)

Substituting (23) and (24) into (22) yields that

$\displaystyle\sum_{m\in[M]}\delta_{1}^{m}\leq$ $\displaystyle 2\left|e^{\beta
H}-1\right|\sqrt{2HM\iota}+\left(C_{1}\left|e^{\beta
H}-1\right|+g_{1}(\beta)\right)\sqrt{2H^{2}|S|^{2}|A|\iota^{2}}\frac{M}{\sqrt{W}}$
(25) $\displaystyle+WH\left(\left|e^{\beta
H}-1\right|B_{\mathcal{P}}+g_{1}(\beta)B_{r}\right)$

For $\beta>0$, we have that $g_{1}(\beta)=e^{\beta H}\beta$ and the dynamic
regret can be decomposed based on Lemma E.1:

$\displaystyle\operatorname{D-Regret}(M)$ $\displaystyle\leq$
$\displaystyle\sum_{m\in[M]}\frac{1}{\beta}\left[e^{\beta\cdot
V_{1}^{*,m}\left(s_{1}^{m}\right)}-e^{\beta\cdot
V_{1}^{m}\left(s_{1}^{m}\right)}\right]+\sum_{m\in[M]}\frac{1}{\beta}\left[e^{\beta\cdot
V_{1}^{m}\left(s_{1}^{m}\right)}-e^{\beta\cdot
V_{1}^{\pi^{m},m}\left(s_{1}^{m}\right)}\right]$ $\displaystyle\leq$
$\displaystyle\frac{1}{\beta}\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}H\left(\left|e^{\beta
H}-1\right|B_{\mathcal{P},\mathcal{E}}+g_{1}(\beta)B_{r,\mathcal{E}}\right)+\sum_{m\in[M]}\frac{1}{\beta}\left[e^{\beta\cdot
V_{1}^{m}\left(s_{1}^{m}\right)}-e^{\beta\cdot
V_{1}^{\pi^{m},m}\left(s_{1}^{m}\right)}\right]$ $\displaystyle\leq$
$\displaystyle\frac{1}{\beta}WH\left(\left|e^{\beta
H}-1\right|B_{\mathcal{P}}+g_{1}(\beta)B_{r}\right)+\frac{1}{\beta}\sum_{m\in[M]}\delta_{1}^{m}$
$\displaystyle\leq$ $\displaystyle\frac{1}{\beta}\left(2\left(e^{\beta
H}-1\right)\sqrt{2HM\iota}+\left(C_{1}\left(e^{\beta H}-1\right)+e^{\beta
H}\beta\right)\sqrt{2H^{2}|S|^{2}|A|\iota^{2}}\frac{M}{\sqrt{W}}\right.$
$\displaystyle\left.+WH\left(\left(e^{\beta
H}-1\right)B_{\mathcal{P}}+e^{\beta H}\beta B_{r}\right)\right)$
$\displaystyle\leq$ $\displaystyle 2e^{\beta H}H\sqrt{2HM\iota}+e^{\beta
H}\left(C_{1}H+1\right)\sqrt{2H^{2}|S|^{2}|A|\iota^{2}}\frac{M}{\sqrt{W}}+WHe^{\beta
H}\left(HB_{\mathcal{P}}+B_{r}\right)$ $\displaystyle\leq$ $\displaystyle
2e^{\beta H}H\sqrt{2HM\iota}+(C_{1}+1)e^{\beta
H}H\sqrt{2H^{2}|S|^{2}|A|\iota^{2}}\frac{M}{\sqrt{W}}+WH^{2}e^{\beta
H}\left(B_{\mathcal{P}}+B_{r}\right)$ (26)

where the second inequality follows from Lemma A.6, the third inequality holds
because of the definition of $B_{\mathcal{P}}$, $B_{{r}}$ and
$\delta_{1}^{m}$, the forth inequality is due to (25), and the fifth
inequality follows from $e^{\beta H}-1\leq\beta He^{\beta H}$ for $\beta>0$.

Finally, by setting
$W=M^{\frac{2}{3}}\left(B_{\mathcal{P}}+B_{r}\right)^{-\frac{2}{3}}|S|^{\frac{2}{3}}|A|^{\frac{1}{3}}$,
we conclude that

$\displaystyle\operatorname{D-Regret(M)}\leq$
$\displaystyle\widetilde{\mathcal{O}}\left(e^{\beta
H}|S|^{\frac{2}{3}}|A|^{\frac{1}{3}}H^{2}M^{\frac{2}{3}}\left(B_{\mathcal{P}}+B_{r}\right)^{\frac{1}{3}}\right).$

The proof of $\beta<0$ follows a similar procedure and is therefore omitted.

##  Appendix B Proof of Theorem 3.2

###  B.1 Preliminaries

We first lay out some additional notations to facilitate our proof. Let
$N_{h}^{m},G_{h}^{m},V_{h}^{m}$ be $N_{h},G_{h},V_{h}$ at the beginning of
episode $m$, before $t$ is updated. We also set
$Q_{h}^{m}:=\frac{1}{\beta}G_{h}^{m}$. Let $\widehat{P}_{h}^{m}(\cdot\mid
s,a)$ denote the delta function centered at $s_{h+1}^{m}$ for all
$(m,h,s,a)\in[M]\times[H]\times\mathcal{S}\times\mathcal{A}$. This means that
$\mathbb{E}_{s^{\prime}\sim\widehat{P}_{h}^{m}(\cdot\mid
s,a)}\left[f\left(s^{\prime}\right)\right]=f\left(s_{h+1}^{m}\right)$ for
every $f:\mathcal{S}\rightarrow\mathbb{R}$. Denote by
$n_{h}^{m}:=N_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)$. Recall from Algorithm
2 that the learning rate is defined as

$\alpha_{t}:=\frac{H+1}{H+t}$

for $t\in\mathbb{Z}$. We also define

$\displaystyle\alpha_{t}^{0}:=\prod_{j=1}^{t}\left(1-\alpha_{j}\right),\quad\alpha_{t}^{i}:=\alpha_{i}\prod_{j=i+1}^{t}\left(1-\alpha_{j}\right)$
(27)

for integers $i,t\geq 1$. We set $\alpha_{t}^{0}=1$ and
$\sum_{i\in[t]}\alpha_{t}^{i}=0$ if $t=0$, and $\alpha_{t}^{i}=\alpha_{i}$ if
$t<i+1$.

The epoch is defined as an interval that starts at the first episode after a
restart and ends at the first time when the restart is triggered. In Algorithm
2, the restart mechanism divides $M$ episodes into
$\left\lceil{\frac{M}{W}}\right\rceil$ epochs.

Define the shorthand notation
$\iota:=\log(|\mathcal{S}||\mathcal{A}|MH/\delta)$ for $\delta\in(0,1]$. We
fix a tuple $(m,h,s,a)\in[M]\times[H]\times$ $\mathcal{S}\times\mathcal{A}$
with $m_{i}^{\mathcal{E}}\leq M$ being the episode in which $(s,a)$ is visited
the $i$-th time at step $h$ in epoch $\mathcal{E}$. Let us define

$\displaystyle
q_{h,1}^{m,+}(s,a):=\alpha_{t}^{0}e^{\beta(H-h+1)}+\begin{cases}\sum_{i\in[t]}\alpha_{t}^{i}\left[e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}+\Gamma_{h,i}\right],&\text{
if }\beta>0,\\\
\sum_{i\in[t]}\alpha_{t}^{i}\left[e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-\Gamma_{h,i}\right],&\text{
if }\beta<0,\end{cases}$ $\displaystyle
q_{h,1}^{m}(s,a):=\begin{cases}\min\left\\{q_{h,1}^{m,+}(s,a),e^{\beta(H-h+1)}\right\\},&\text{
if }\beta>0,\\\
\max\left\\{q_{h,1}^{m,+}(s,a),e^{\beta(H-h+1)}\right\\},&\text{ if
}\beta<0,\end{cases}$

and

$\displaystyle
q_{h,2}^{m,\circ}(s,a):=\alpha_{t}^{0}e^{\beta(H-h+1)}+\sum_{i\in[t]}\alpha_{t}^{i}\left[e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}\right]$
$\displaystyle
q_{h,2}^{m,+}(s,a):=\alpha_{t}^{0}e^{\beta(H-h+1)}+\begin{cases}\sum_{i\in[t]}\alpha_{t}^{i}\left[e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}+\Gamma_{h,i}\right],&\text{
if }\beta>0\\\
\sum_{i\in[t]}\alpha_{t}^{i}\left[e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-\Gamma_{h,i}\right],&\text{
if }\beta<0\end{cases}$ $\displaystyle
q_{h,2}^{m}(s,a):=\begin{cases}\min\left\\{q_{h,2}^{m,+}(s,a),e^{\beta(H-h+1)}\right\\},&\text{
if }\beta>0\\\
\max\left\\{q_{h,2}^{m,+}(s,a),e^{\beta(H-h+1)}\right\\},&\text{ if
}\beta<0\end{cases}$

and

$q_{h,3}^{m}(s,a):=\alpha_{t}^{0}e^{\beta\cdot
Q_{h}^{*,m}(s,a)}+\sum_{i\in[t]}\alpha_{t}^{i}\left[\mathbb{E}_{s^{\prime}\sim
P^{m}_{h}(\cdot\mid
s,a)}e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}\right].$

By the definition of $q_{h,2}^{m,\circ}$, $q_{h,2}^{m,+}$ and $q_{h,2}^{m}$,
it can be seen that $q_{h,2}^{m,\circ}\leq q_{h,2}^{m}$ if $\beta>0$, and
$q_{h,2}^{m,\circ}\geq q_{h,2}^{m}$ if $\beta<0$. In addition, by definition,
we have $\left(e^{\beta\cdot Q_{h}^{m}}-e^{\beta\cdot
Q_{h}^{*,m}}\right)(s,a)=\left(q_{h,1}^{m}-q_{h,3}^{m}\right)(s,a)$.

###  B.2 Value difference bounds

###### Lemma B.1

For every triple $(s,a,h)$ and episodes $m_{1},m_{2}$ in the epoch
$\mathcal{E}$, it holds that
$\left|V_{h}^{*,m_{1}}(s)-V_{h}^{*,m_{2}}(s)\right|\leq
B_{r,\mathcal{E}}+HB_{\mathcal{P},\mathcal{E}}$.

Proof. Let $a_{1}=\mathop{\rm argmax}_{a}Q_{h}^{*,m_{1}}(s,a)$ and
$a_{2}=\mathop{\rm argmax}_{a}Q_{h}^{*,m_{2}}(s,a)$, it holds that

$\displaystyle V_{h}^{*,m_{1}}(s)=Q_{h}^{*,m_{1}}(s,a_{1})\geq
Q_{h}^{*,m_{1}}(s,a_{2})\geq$ $\displaystyle
Q_{h}^{*,m_{2}}(s,a_{2})-B_{r,\mathcal{E}}-HB_{\mathcal{P},\mathcal{E}}$
$\displaystyle=$ $\displaystyle
V_{h}^{*,m_{2}}(s)-B_{r,\mathcal{E}}-HB_{\mathcal{P},\mathcal{E}}$

where the second inequality follows from (Mao et al. 2020, Lemma 1).
Similarly, we have

$\displaystyle V_{h}^{*,m_{2}}(s)\geq
V_{h}^{*,m_{1}}(s)-B_{r,\mathcal{E}}-HB_{\mathcal{P},\mathcal{E}}.$

This completes the proof. $\Box$

###### Lemma B.2

For every $(m,h,s,a)\in[M]\times[H]\times\mathcal{S}\times\mathcal{A}$ and
$m_{1},\ldots,m_{t}<m$ with $t=N_{h}^{m}(s,a)$, we have

$\displaystyle\left|\sum_{i\in[t]}\alpha_{t}^{i}\left[e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-\mathbb{E}_{s^{\prime}\sim
P^{m}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}\right]\right]\right|$
$\displaystyle\leq$
$\displaystyle\Gamma_{h,t}+2g_{h}(\beta)B_{r,\mathcal{E}}+\left(g_{h}(\beta)H+\left|e^{\beta(H-h+1)}-1\right|\right)B_{\mathcal{P},\mathcal{E}}$

with probability at least $1-\delta$, and

$\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}\in\left[\Gamma_{h,t},2\Gamma_{h,t}\right],$

where $\Gamma_{h,t}$ is defined in (7).

Proof. For every $(m,h,s,a)\in$
$[M]\times[H]\times\mathcal{S}\times\mathcal{A}$, we have the following
decomposition:

$\displaystyle
e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-\mathbb{E}_{s^{\prime}\sim
P^{m}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}\right]$
$\displaystyle=$ $\displaystyle
e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}$
(28a)
$\displaystyle+e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}$
(28b)
$\displaystyle+e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-\mathbb{E}_{s^{\prime}\sim
P^{m_{i}^{\mathcal{E}}}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}\right]$
(28c) $\displaystyle+\mathbb{E}_{s^{\prime}\sim
P^{m_{i}^{\mathcal{E}}}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}\right]-\mathbb{E}_{s^{\prime}\sim
P^{m}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}\right].$
(28d)

For the terms in (28a), it holds that

$\displaystyle\left|e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}\right|\leq$
$\displaystyle
g_{h}(\beta)\left|{r}_{h}^{m_{i}^{\mathcal{E}}}(s,a)-{r}_{h}^{m}(s,a)\right|$
$\displaystyle\leq$ $\displaystyle g_{h}(\beta){B}_{r,\epsilon},$ (29)

where the first inequality follows from the Lipschitz continuity of $e^{\beta
x}$ with respect to $x$ and the second inequality is due to the definition of
the local variation budget ${B}_{r,\epsilon}$.

For the terms in (28b), it holds that

$\displaystyle\left|e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}\right|\leq$
$\displaystyle
g_{h}(\beta)\left|V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)-V_{h+1}^{*,m}(s_{h+1}^{m_{i}^{\mathcal{E}}})\right|$
$\displaystyle\leq$ $\displaystyle
g_{h}(\beta)\left(B_{r,\mathcal{E}}+HB_{\mathcal{P},\mathcal{E}}\right)$ (30)

where the second inequality follows from Lemma B.1.

For the terms in (28d), we have

$\displaystyle\left|\mathbb{E}_{s^{\prime}\sim
P^{m_{i}^{\mathcal{E}}}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}\right]-\mathbb{E}_{s^{\prime}\sim
P^{m}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}\right]\right|$
$\displaystyle=\left|\mathbb{E}_{s^{\prime}\sim
P^{m_{i}^{\mathcal{E}}}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}-1\right]-\mathbb{E}_{s^{\prime}\sim
P^{m}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}-1\right]\right|$
$\displaystyle\leq\left|e^{\beta(H-h+1)}-1\right|B_{\mathcal{P},\mathcal{E}}$
(31)

where the first step follows from
$\mathcal{P}_{h}^{m}{1}(s,a)=\mathcal{P}_{h}^{\tau}{1}(s,a)$ for all
$\tau\in[\ell^{m},m-1]$ and the last step holds by the definition of
$B_{\mathcal{P},\mathcal{E}}$.

We now analyze the terms in (28c). For every
$(m,h,s,a)\in[M]\times[H]\times\mathcal{S}\times\mathcal{A}$, we define

$\displaystyle\psi(i,m,h,s,a)\coloneqq
e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-\mathbb{E}_{s^{\prime}\sim
P^{m_{i}^{\mathcal{E}}}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}\right].$

For a fix tuple $(m,h,s,a)\in[M]\times[H]\times\mathcal{S}\times\mathcal{A}$,
$\left\\{\psi(i,m,h,s,a)\right\\}_{i\in[t]}$ with $t=N_{h}^{m}(s,a)$ is a
martingale difference sequence. By the Azuma-Hoeffding inequality, with
probability at least $1-\delta/(HM|\mathcal{S}||\mathcal{A}|)$, it holds that

$\displaystyle\left|\sum_{i\in[t]}\alpha_{t}^{i}\cdot\psi(i,m,h,s,a)\right|\leq\frac{C_{2}}{2}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\iota\sum_{i\in[t]}\left(\alpha_{t}^{i}\right)^{2}}\leq
C_{2}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\frac{H\iota}{t}}$

where $C_{2}>0$ is some universal constant, the first step holds since
$r_{h}(s,a)+V_{h+1}^{*}\left(s^{\prime}\right)\in[0,H-h+1]$ for
$s^{\prime}\in\mathcal{S}$, and the last step follows from the second property
in Lemma E.3. Then, applying the union bound over
$(m,h,s,a)\in[M]\times[H]\times\mathcal{S}\times\mathcal{A}$, we have that the
following holds for all
$(m,h,s,a)\in[M]\times[H]\times\mathcal{S}\times\mathcal{A}$ with probability
at least $1-\delta$ :

$\displaystyle\left|\sum_{i\in[t]}\alpha_{t}^{i}\cdot\psi(i,m,h,s,a)\right|\leq
C_{2}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\frac{H\iota}{t}},$ (32)

where $t=N_{h}^{m}(s,a)$.

Finally, by combining Equations (29)-(32) and noticing that
$\sum_{i\in[t]}\alpha_{t}^{i}=1$ from the forth property in Lemma E.3, we have

$\displaystyle\left|\sum_{i\in[t]}\alpha_{t}^{i}\left[e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-\mathbb{E}_{s^{\prime}\sim
P^{m}_{h}(\cdot\mid
s,a)}\left[e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}\right]\right]\right|$
$\displaystyle\leq$ $\displaystyle
C_{2}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\frac{H\iota}{t}}+2g_{h}(\beta)B_{r,\mathcal{E}}+\left(g_{h}(\beta)H+\left|e^{\beta(H-h+1)}-1\right|\right)B_{\mathcal{P},\mathcal{E}}$

For bounds on $\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}$, we recall the
definition of $\left\\{\Gamma_{h,t}\right\\}$ in (7) and compute

$\displaystyle\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}$
$\displaystyle=C_{2}\left|e^{\beta(H-h+1)}-1\right|\sum_{i\in[t]}\alpha_{t}^{i}\sqrt{\frac{H\iota}{i}}$
$\displaystyle\in\left[C_{2}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\frac{H\iota}{t}},2C_{2}\left|e^{\beta(H-h+1)}-1\right|\sqrt{\frac{H\iota}{t}}\right]$

where the last step holds by the first property in Lemma E.3. $\Box$

###### Lemma B.3

For all $(m,h,s,a)$ and $\delta\in(0,1]$, the following statements hold with
probability at least $1-\delta$:

  * •

If $\beta>0$:

$\displaystyle-2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}-\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\leq
q_{h,2}^{m}(s,a)-q_{h,3}^{m}(s,a)$
$\displaystyle\leq\alpha_{t}^{0}\left(e^{\beta(H-h+1)}-1\right)+2\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}+2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}.$

  * •

If $\beta<0$:

$\displaystyle 2\beta B_{r,\mathcal{E}}-\left(-\beta
H+\left(1-e^{\beta(H-h+1)}\right)\right)B_{\mathcal{P},\mathcal{E}}\leq
q_{h,3}^{m}(s,a)-q_{h,2}^{m}(s,a)$
$\displaystyle\leq\alpha_{t}^{0}\left(1-e^{\beta(H-h+1)}\right)+2\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}-2\beta
B_{r,\mathcal{E}}+\left(-\beta
H+\left(1-e^{\beta(H-h+1)}\right)\right)B_{\mathcal{P},\mathcal{E}}.$

Proof. We focus on the case where $\beta>0$ and the case for $\beta<0$ can be
proved similarly. By the definition of $q_{h,2}^{m,+}$ and $q_{h,3}^{m}$, it
holds that

$\displaystyle q_{h,2}^{m,+}-q_{h,3}^{m}=$
$\displaystyle\alpha_{t}^{0}\left(e^{\beta(H-h+1)}-e^{\beta
Q_{h}^{*,m}(s,a)}\right)$
$\displaystyle+\sum_{i\in[t]}\alpha_{t}^{i}\left[e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}+\Gamma_{h,i}-\mathbb{E}_{s^{\prime}\sim
P^{m}_{h}(\cdot\mid
s,a)}e^{\beta\left[r^{m}_{h}(s,a)+V_{h+1}^{*,m}\left(s^{\prime}\right)\right]}\right].$

Due to $e^{\beta(H-h+1)}\geq e^{\beta Q_{h}^{*,m}(s,a)}\geq 1$ and Lemma B.2,
we have

$\displaystyle q_{h,2}^{m,+}-q_{h,3}^{m}\geq$
$\displaystyle-2g_{h}(\beta)B_{r,\mathcal{E}}-\left(g_{h}(\beta)H+\left|e^{\beta(H-h+1)}-1\right|\right)B_{\mathcal{P},\mathcal{E}}$

and

$\displaystyle q_{h,2}^{m,+}-q_{h,3}^{m}\leq$
$\displaystyle\alpha_{t}^{0}\left(e^{\beta(H-h+1)}-1\right)+2\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}$
$\displaystyle+2g_{h}(\beta)B_{r,\mathcal{E}}+\left(g_{h}(\beta)H+\left|e^{\beta(H-h+1)}-1\right|\right)B_{\mathcal{P},\mathcal{E}}.$

Furthermore, if $q_{h,2}^{m,+}\leq e^{\beta(H-h+1)}$, then we have
$q_{h,2}^{m}=q_{h,2}^{m,+}$. On the other hand, if $q_{h,2}^{m,+}\geq
e^{\beta(H-h+1)}$, then $q_{h,2}^{m}=e^{\beta(H-h+1)}\leq q_{h,2}^{m,+}$.
Thus, it holds that $0\leq q_{h,2}^{m}-q_{h,3}^{m}\leq
q_{h,2}^{m,+}-q_{h,3}^{m}$. This completes the proof. $\Box$

The next two lemmas compare the iterate $e^{\beta\cdot Q_{h}^{m}}$ (and
$e^{\beta\cdot V_{h}^{m}}$ ) with the optimal exponential value function
$e^{\beta\cdot Q_{h}^{*,m}}$ (and $e^{\beta\cdot V_{h}^{*,m}})$.

###### Lemma B.4

For all $(m,h,s,a)$ and $\delta\in(0,1]$, it holds with probability at least
$1-\delta$:

  * •

If $\beta>0$:

$\displaystyle(e^{\beta Q_{h}^{m}}-e^{\beta Q_{h}^{*,m}})(s,a)$
$\displaystyle\geq$ $\displaystyle-(H-h+1)\left(2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right).$

  * •

If $\beta<0$:

$\displaystyle(e^{\beta Q_{h}^{m}}-e^{\beta
Q_{h}^{*,m}})(s,a)\leq(H-h+1)\left(-2\beta B_{r,\mathcal{E}}+\left(-\beta
H+\left(1-e^{\beta(H-h+1)}\right)\right)B_{\mathcal{P},\mathcal{E}}\right).$

Proof. We focus only on the case where $\beta>0$ since the proof for $\beta<0$
is similar. For the purpose of the proof, we set
$Q_{H+1}^{m}(s,a)=Q_{H+1}^{*}(s,a)=0$ for all
$(m,s,a)\in[M]\times\mathcal{S}\times\mathcal{A}$. We fix a pair
$(s,a)\in\mathcal{S}\times\mathcal{A}$ and use strong induction on $m$ and
$h$. Without loss of generality, we assume that there exists a pair $(m,h)$
such that $(s,a)=\left(s_{h}^{m},a_{h}^{m}\right)$ (that is, $(s,a)$ has been
visited at some point in Algorithm 2), since otherwise $e^{\beta\cdot
Q_{h}^{m}(s,a)}=e^{\beta(H-h+1)}\geq e^{\beta\cdot Q_{h}^{*}(s,a)}$ for all
$(m,h)\in[M]\times[H]$ and we are done.

The base case for $m=1$ and $h=H+1$ is satisfied since $e^{\beta\cdot
Q_{H+1}^{m^{\prime}}(s,a)}=e^{\beta\cdot Q_{H+1}^{*,m}(s,a)}$ for
$m^{\prime}\in[M]$ by definition. We fix a pair $(m,h)\in[M]\times[H]$ and
assume that

$\displaystyle e^{\beta\cdot Q_{h+1}^{m_{i}^{\mathcal{E}}}(s,a)}-e^{\beta\cdot
Q_{h+1}^{*,m_{i}^{\mathcal{E}}}(s,a)}\geq-(H-h)\left(2e^{\beta(H-h)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h)}\beta
H+\left(e^{\beta(H-h)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$

for each $m_{1}^{\mathcal{E}},\ldots,m_{t}^{\mathcal{E}}$ (here
$t=N_{h}^{m}(s,a)$ ). We have for $i\in[t]$ that

$\displaystyle e^{\beta\cdot V_{h+1}^{m_{i}^{\mathcal{E}}}(s)}=$
$\displaystyle\max_{a^{\prime}\in\mathcal{A}}e^{\beta\cdot
Q_{h+1}^{m_{i}^{\mathcal{E}}}\left(s,a^{\prime}\right)}-(H-h)\left(2e^{\beta(H-h)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h)}\beta
H+\left(e^{\beta(H-h)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$
$\displaystyle\geq$ $\displaystyle\max_{a^{\prime}\in\mathcal{A}}e^{\beta\cdot
Q_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s,a^{\prime}\right)}-(H-h)\left(2e^{\beta(H-h)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h)}\beta
H+\left(e^{\beta(H-h)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$
$\displaystyle=$ $\displaystyle e^{\beta\cdot
V_{h+1}^{*,m_{i}^{\mathcal{E}}}(s)}-(H-h)\left(2e^{\beta(H-h)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h)}\beta
H+\left(e^{\beta(H-h)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$ (33)

where the first equality holds by the update procedure in Algorithm 2. Then,
it holds that

$\displaystyle(q_{h,1}^{m,+}-q_{h,2}^{m})(s,a)$
$\displaystyle\geq(q_{h,1}^{m,+}-q_{h,2}^{m,+})(s,a)$
$\displaystyle\geq\sum_{i\in[t]}\alpha_{t}^{i}\left[e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}\right]$
$\displaystyle=\sum_{i\in[t]}\alpha_{t}^{i}e^{\beta
r^{m_{i}^{\mathcal{E}}}_{h}(s,a)}\left[e^{\beta\left[V_{h+1}^{m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-e^{\beta\left[V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}\right]$
$\displaystyle\geq-(H-h)\sum_{i\in[t]}\alpha_{t}^{i}e^{\beta}\left(2e^{\beta(H-h)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h)}\beta
H+\left(e^{\beta(H-h)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$
$\displaystyle\geq-(H-h)\sum_{i\in[t]}\alpha_{t}^{i}\left(2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$
$\displaystyle\geq-(H-h)\left(2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$

where the first inequality follows from the definitions of $q_{h,1}^{m,+}$,
$q_{h,2}^{m,+}$, the second inequality holds by the induction hypothesis, the
third inequality follows from $e^{\beta}>1$ for $\beta>0$, and the last
inequality holds by $\sum_{i\in[t]}\alpha_{t}^{i}\leq 1$ from Lemma E.3.
Furthermore, when $q_{h,1}^{m}=e^{\beta(H-h+1)}\leq q_{h,1}^{m,+}$, we have
$q_{h,1}^{m}-q_{h,2}^{m}\geq 0$ since $q_{h,2}^{m}\leq e^{\beta(H-h+1)}$ by
definition. Thus, we can conclude that

$\displaystyle(q_{h,1}^{m}-q_{h,2}^{m})(s,a)$
$\displaystyle\geq-(H-h)\left(2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$
(34)

In addition, from Lemma B.3 , we also have

$\displaystyle(q_{h,2}^{m}-q_{h,3}^{m})(s,a)\geq-2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}-\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}$ (35)

Finally, by combining (34) and (35), we obtain

$\displaystyle(e^{\beta Q_{h}^{m}}-e^{\beta Q_{h}^{*,m}})(s,a)$
$\displaystyle=$
$\displaystyle(q_{h,1}^{m}-q_{h,2}^{m})(s,a)+(q_{h,2}^{m}-q_{h,3}^{m})(s,a)$
$\displaystyle\geq$ $\displaystyle-(H-h+1)\left(2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right).$

The induction is completed. $\Box$

###### Lemma B.5

For all $(m,h,s,a)$ and $\delta\in(0,1]$, it holds with probability at least
$1-\delta$:

  * •

If $\beta>0$:

$\displaystyle(e^{\beta Q_{h}^{m}}-e^{\beta Q_{h}^{*,m}})(s,a)$
$\displaystyle\leq$ $\displaystyle\sum_{i\in[t]}\alpha_{t}^{i}e^{\beta
r^{m_{i}^{\mathcal{E}}}_{h}(s,a)}\left[e^{\beta\left[V_{h+1}^{m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-e^{\beta\left[V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}\right]+3\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}$
$\displaystyle+\alpha_{t}^{0}\left(e^{\beta(H-h+1)}-1\right)+2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}.$

  * •

If $\beta<0$:

$\displaystyle(e^{\beta Q_{h}^{m}}-e^{\beta Q_{h}^{*,m}})(s,a)$
$\displaystyle\geq$ $\displaystyle\sum_{i\in[t]}\alpha_{t}^{i}e^{\beta
r^{m_{i}^{\mathcal{E}}}_{h}(s,a)}\left[e^{\beta\left[V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-e^{\beta\left[V_{h+1}^{m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}\right]-3\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}$
$\displaystyle-\alpha_{t}^{0}\left(1-e^{\beta(H-h+1)}\right)+2\beta
B_{r,\mathcal{E}}-\left(-\beta
H+\left(1-e^{\beta(H-h+1)}\right)\right)B_{\mathcal{P},\mathcal{E}}.$

Proof. We focus on the case where $\beta>0$ since the case for $\beta<0$ can
be proved similarly. By the definition of $q_{h,1}^{m}$ and $q_{h,2}^{m}$, we
have

$\displaystyle\left(q_{h,1}^{m}-q_{h,2}^{m}\right)(s,a)\leq$
$\displaystyle\left(q_{h,1}^{m,+}-q_{h,2}^{m,\circ}\right)(s,a)$
$\displaystyle\leq$
$\displaystyle\sum_{i\in[t]}\alpha_{t}^{i}\left[e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-e^{\beta\left[r^{m_{i}^{\mathcal{E}}}_{h}(s,a)+V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}\right]+\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}$
$\displaystyle=$ $\displaystyle\sum_{i\in[t]}\alpha_{t}^{i}e^{\beta
r^{m_{i}^{\mathcal{E}}}_{h}(s,a)}\left[e^{\beta\left[V_{h+1}^{m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-e^{\beta\left[V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}\right]+\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}$

where the first inequality follows from $q_{h,1}^{m}\leq q_{h,1}^{m,+}$ and
$q_{h,2}^{m}\geq q_{h,2}^{m,\circ}$, and the second inequality holds by the
definition of $q_{h,1}^{m,+}$ and $q_{h,2}^{m,\circ}$. Then, by Lemma B.3, we
obtain

$\displaystyle(e^{\beta Q_{h}^{m}}-e^{\beta Q_{h}^{*,m}})(s,a)$
$\displaystyle=$
$\displaystyle(q_{h,1}^{m}-q_{h,2}^{m})(s,a)+(q_{h,2}^{m}-q_{h,3}^{m})(s,a)$
$\displaystyle\leq$ $\displaystyle\sum_{i\in[t]}\alpha_{t}^{i}e^{\beta
r^{m_{i}^{\mathcal{E}}}_{h}(s,a)}\left[e^{\beta\left[V_{h+1}^{m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}-e^{\beta\left[V_{h+1}^{*,m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)\right]}\right]+3\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}$
$\displaystyle+\alpha_{t}^{0}\left(e^{\beta(H-h+1)}-1\right)+2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}.$

This completes the proof. $\Box$

###  B.3 Proof of Theorem 3.2

For now, we consider the case for $\beta>0$. We define the following
quantities to ease the notations for the proof:

$\displaystyle\delta_{h}^{m}$ $\displaystyle:=e^{\beta\cdot
V_{h}^{m}\left(s_{h}^{m}\right)}-e^{\beta\cdot
V_{h}^{\pi^{m}}\left(s_{h}^{m}\right)},$ $\displaystyle\phi_{h}^{m}$
$\displaystyle:=e^{\beta\cdot V_{h}^{m}\left(s_{h}^{m}\right)}-e^{\beta\cdot
V_{h}^{*,m}\left(s_{h}^{m}\right)},$ $\displaystyle\xi_{h+1}^{m}$
$\displaystyle:=\left[\left(\mathcal{P}^{m}_{h}-\widehat{\mathcal{P}}_{h}^{m}\right)\left(e^{\beta\cdot
V_{h+1}^{*,m}}-e^{\beta\cdot
V_{h+1}^{\pi^{m}}}\right)\right]\left(s_{h}^{m},a_{h}^{m}\right)$

For each fixed $(m,h)\in[M]\times[H]$, we let
$t=N_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)$. Then, it holds that

$\displaystyle\delta_{h}^{m}\stackrel{{\scriptstyle(i)}}{{=}}$ $\displaystyle
e^{\beta\cdot Q_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)}-e^{\beta\cdot
Q_{h}^{\pi^{m},m}\left(s_{h}^{m},a_{h}^{m}\right)}$ $\displaystyle=$
$\displaystyle\left[e^{\beta\cdot
Q_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)}-e^{\beta\cdot
Q_{h}^{*,m}\left(s_{h}^{m},a_{h}^{m}\right)}\right]+\left[e^{\beta\cdot
Q_{h}^{*,m}\left(s_{h}^{m},a_{h}^{m}\right)}-e^{\beta\cdot
Q_{h}^{\pi^{m}}\left(s_{h}^{m},a_{h}^{m}\right)}\right]$
$\displaystyle\stackrel{{\scriptstyle(ii)}}{{=}}$
$\displaystyle\left[e^{\beta\cdot
Q_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)}-e^{\beta\cdot
Q_{h}^{*,m}\left(s_{h}^{m},a_{h}^{m}\right)}\right]+e^{\beta\cdot
r^{m}_{h}\left(s_{h}^{m},a_{h}^{m}\right)}\left[\mathcal{P}^{m}_{h}\left(e^{\beta\cdot
V_{h+1}^{*,m}}-e^{\beta\cdot
V_{h+1}^{\pi^{m},m}}\right)\right]\left(s_{h}^{m},a_{h}^{m}\right)$
$\displaystyle\stackrel{{\scriptstyle(iii)}}{{\leq}}$
$\displaystyle\left[e^{\beta\cdot
Q_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)}-e^{\beta\cdot
Q_{h}^{*,m}\left(s_{h}^{m},a_{h}^{m}\right)}\right]+e^{\beta}\left[\mathcal{P}^{m}_{h}\left(e^{\beta\cdot
V_{h+1}^{*,m}}-e^{\left.\beta\cdot
V_{h+1}^{\pi^{m},m}\right)}\right)\left(s_{h}^{m},a_{h}^{m}\right)\right.$
$\displaystyle=$ $\displaystyle\left[e^{\beta\cdot
Q_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)}-e^{\beta\cdot
Q_{h}^{*,m}\left(s_{h}^{m},a_{h}^{m}\right)}\right]+e^{\beta}\left(\delta_{h+1}^{m}-\phi_{h+1}^{m}+\xi_{h+1}^{m}\right)$
$\displaystyle\stackrel{{\scriptstyle(iv)}}{{\leq}}$
$\displaystyle\alpha_{t}^{0}\left(e^{\beta(H-h+1)}-1\right)+3\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}+\sum_{i\in[t]}\alpha_{t}^{i}\cdot
e^{\beta\cdot
r^{m_{i}^{\mathcal{E}}}_{h}\left(s_{h}^{m},a_{h}^{m}\right)}\left[e^{\beta\cdot
V_{h+1}^{m_{i}^{\mathcal{E}}}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)}-e^{\beta\cdot
V_{h+1}^{*}\left(s_{h+1}^{m_{i}^{\mathcal{E}}}\right)}\right]$
$\displaystyle+2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}$
$\displaystyle+e^{\beta}\left(\delta_{h+1}^{m}-\phi_{h+1}^{m}+\xi_{h+1}^{m}\right)$
$\displaystyle=$
$\displaystyle\alpha_{t}^{0}\left(e^{\beta(H-h+1)}-1\right)+\sum_{i\in[t]}\alpha_{t}^{i}\cdot
e^{\beta\cdot
r^{m_{i}^{\mathcal{E}}}_{h}\left(s_{h}^{m},a_{h}^{m}\right)}\phi_{h+1}^{m_{i}^{\mathcal{E}}}+e^{\beta}\left(\delta_{h+1}^{m}-\phi_{h+1}^{m}+\xi_{h+1}^{m}\right)$
(36)
$\displaystyle+3\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}+2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}$ (37)

where step $(i)$ holds since
$V_{h}^{m}\left(s_{h}^{m}\right)=\max_{a^{\prime}\in\mathcal{A}}Q_{h}^{m}\left(s_{h}^{m},a^{\prime}\right)=Q_{h}^{m}\left(s_{h}^{m},a_{h}^{m}\right)$
and
$V_{h}^{\pi^{m},m}\left(s_{h}^{m}\right)=Q_{h}^{\pi^{m},m}\left(s_{h}^{m},\pi_{h}^{m}\left(s_{h}^{m}\right)\right)=$
$Q_{h}^{\pi^{m},m}\left(s_{h}^{m},a_{h}^{m}\right)$; step (ii) holds by the
exponential Bellman equation (3); step (iii) holds since $V_{h+1}^{*,m}\geq$
$V_{h+1}^{\pi^{m},m}$ implies $e^{\beta\cdot V_{h+1}^{*,m}}\geq e^{\beta\cdot
V_{h+1}^{\pi^{m},m}}$ given that $\beta>0$; step (iv) holds on the event of
Lemma B.5.

We bound each term in (36) and (37) one by one. First, we have

$\displaystyle\sum_{m\in[M]}\alpha_{n_{h}^{m}}^{0}\left(e^{\beta(H-h+1)}-1\right)$
$\displaystyle=\left(e^{\beta(H-h+1)}-1\right)\sum_{m\in[M]}\mathbb{1}\left\\{n_{h}^{m}=0\right\\}$
$\displaystyle\leq\left(e^{\beta(H-h+1)}-1\right)|\mathcal{S}||\mathcal{A}|.$

To bound the second term in (36), we first define

$\displaystyle\hat{\phi}_{h+1}^{m_{i}^{\mathcal{E}}\left(s_{h}^{m},a_{h}^{m}\right)}\coloneqq{\phi}_{h+1}^{m_{i}^{\mathcal{E}}\left(s_{h}^{m},a_{h}^{m}\right)}+(H-h)\left(2e^{\beta(H-h)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h)}\beta
H+\left(e^{\beta(H-h)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$

which is non-negative from Lemma B.4 and (33):

$\displaystyle\sum_{m\in[M]}\left(\sum_{i\in[t]}\alpha_{t}^{i}\cdot
e^{\beta\cdot
r^{m_{i}^{\mathcal{E}}}_{h}\left(s_{h}^{m},a_{h}^{m}\right)}\phi_{h+1}^{m_{i}^{\mathcal{E}}}\right)=$
$\displaystyle\sum_{m\in[M]}\left(\sum_{i\in\left[n_{h}^{m}\right]}\alpha_{n_{h}^{m}}^{i}\cdot
e^{\beta\cdot
r^{m_{i}^{\mathcal{E}}}_{h}\left(s_{h}^{m},a_{h}^{m}\right)}\phi_{h+1}^{m_{i}^{\mathcal{E}}\left(s_{h}^{m},a_{h}^{m}\right)}\right)$
$\displaystyle\leq$ $\displaystyle
e^{\beta}\sum_{m\in[M]}\left(\sum_{i\in\left[n_{h}^{m}\right]}\alpha_{n_{h}^{m}}^{i}\hat{\phi}_{h+1}^{m_{i}^{\mathcal{E}}\left(s_{h}^{m},a_{h}^{m}\right)}\right)$

where $m_{i}^{\mathcal{E}}\left(s_{h}^{m},a_{h}^{m}\right)$ denotes the
episode in which $\left(s_{h}^{m},a_{h}^{m}\right)$ was taken at step $h$ for
the $i$-th time in the epoch $\mathcal{E}$. We re-group the above summation by
changing the order of the summation. For every $\hat{m}^{\mathcal{E}}$ in the
epoch $\mathcal{E}$, the term $\phi_{h+1}^{\hat{m}^{\mathcal{E}}}$ appears in
the summand with $m>\hat{m}^{\mathcal{E}}$ if and only if
$\left(s_{h}^{m},a_{h}^{m}\right)=\left(s_{h}^{m^{\prime}},a_{h}^{m^{\prime}}\right)$
and the episode $m$ is in the epoch $\mathcal{E}$. Since the inverse of the
mapping $i\rightarrow m_{i}^{\mathcal{E}}(s_{h}^{m},a_{h}^{m})$ is
$\hat{m}^{\mathcal{E}}\rightarrow n_{h}^{\hat{m}^{\mathcal{E}}}$, we can
continue the above display as

$\displaystyle
e^{\beta}\sum_{m\in[M]}\left(\sum_{i\in\left[n_{h}^{m}\right]}\alpha_{n_{h}^{m}}^{i}\hat{\phi}_{h+1}^{m_{i}^{\mathcal{E}}\left(s_{h}^{m}a_{h}^{m}\right)}\right)$
$\displaystyle\leq
e^{\beta}\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\left(\sum_{i\in\left[n_{h}^{m}\right]}\alpha_{n_{h}^{m}}^{i}\hat{\phi}_{h+1}^{m_{i}^{\mathcal{E}}\left(s_{h}^{m}a_{h}^{m}\right)}\right)$
$\displaystyle\leq
e^{\beta}\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m^{\prime}=(\mathcal{E}-1)W}^{\mathcal{E}W}\hat{\phi}_{h+1}^{m^{\prime}}\left(\sum_{t\geq
n_{h}^{m^{\prime}}+1}\alpha_{t}^{n_{h}^{m^{\prime}}}\right)$
$\displaystyle\leq
e^{\beta}\left(1+\frac{1}{H}\right)\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m^{\prime}=(\mathcal{E}-1)W}^{\mathcal{E}W}\hat{\phi}_{h+1}^{m^{\prime}}$

where the last step follows the third property in Lemma E.3. Collecting the
above results and substituting them into (36)-(37), we have

$\displaystyle\sum_{m\in[M]}\delta_{h}^{m}\leq$
$\displaystyle\left(e^{\beta(H-h+1)}-1\right)|\mathcal{S}||\mathcal{A}|+\left(1+\frac{1}{H}\right)e^{\beta}\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\hat{\phi}_{h+1}^{m}$
$\displaystyle+\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}e^{\beta}\left(\delta_{h+1}^{m}-\phi_{h+1}^{m}+\xi_{h+1}^{m}\right)+3\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}$
$\displaystyle+\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\left(2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$
$\displaystyle\leq$
$\displaystyle\left(e^{\beta(H-h+1)}-1\right)|\mathcal{S}||\mathcal{A}|+\left(1+\frac{1}{H}\right)\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}e^{\beta}\delta_{h+1}^{m}$
$\displaystyle+\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\left(3\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}+e^{\beta}\xi_{h+1}^{m}\right)$
$\displaystyle+3(H-h)\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\left(2e^{\beta(H-h+1)}\beta
B_{r,\mathcal{E}}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$
$\displaystyle\leq$
$\displaystyle\left(e^{\beta(H-h+1)}-1\right)|\mathcal{S}||\mathcal{A}|+\left(1+\frac{1}{H}\right)\sum_{m\in[M]}e^{\beta}\delta_{h+1}^{m}$
$\displaystyle+3\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}+\sum_{m\in[M]}e^{\beta}\xi_{h+1}^{m}$
$\displaystyle+3(H-h)\left(2e^{\beta(H-h+1)}\beta
WB_{r}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)WB_{\mathcal{P}}\right)$

where the second step holds since $\delta_{h+1}^{m}\geq\phi_{h+1}^{m}$ (due to
the fact that $\beta>0$ and $V_{h+1}^{*,m}\geq V_{h+1}^{\pi^{m},m}$ ) and the
definition of $\hat{\phi}_{h+1}^{m}$; the last step follows from the
definition of $B_{r}$ and $B_{\mathcal{P}}$. Now, we unroll the quantity
$\sum_{m\in[M]}\delta_{h}^{m}$ recursively in the form of Equation (36), and
get

$\displaystyle\sum_{m\in[M]}\delta_{1}^{m}$ (38) $\displaystyle\leq$
$\displaystyle\sum_{h\in[H]}\left[\left(1+\frac{1}{H}\right)e^{\beta}\right]^{h-1}\left[\left(e^{\beta(H-h+1)}-1\right)|\mathcal{S}||\mathcal{A}|+3\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}+\sum_{m\in[M]}\left(e^{\beta}\xi_{h+1}^{m}\right)\right.$
$\displaystyle\left.+3(H-h)\left(2e^{\beta(H-h+1)}\beta
WB_{r}+\left(e^{\beta(H-h+1)}\beta
H+\left(e^{\beta(H-h+1)}-1\right)\right)WB_{\mathcal{P}}\right)\right]$
$\displaystyle\leq$
$\displaystyle\sum_{h\in[H]}\left(1+\frac{1}{H}\right)^{h-1}\left[\left(e^{\beta
H}-1\right)|\mathcal{S}||\mathcal{A}|+3\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}e^{\beta(h-1)}\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}+\sum_{m\in[M]}e^{\beta
h}\xi_{h+1}^{m}\right.$ $\displaystyle\left.+3(H-h)\left(2e^{\beta H}\beta
WB_{r}+\left(e^{\beta H}\beta H+\left(e^{\beta
H}-1\right)\right)WB_{\mathcal{P}}\right)\right]$ $\displaystyle\leq$
$\displaystyle e\left[\left(e^{\beta
H}-1\right)H|\mathcal{S}||\mathcal{A}|+3e\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\sum_{h\in[H]}e^{\beta(h-1)}\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}\right]+\sum_{h\in[H]}\sum_{m\in[M]}\left(1+\frac{1}{H}\right)^{h-1}e^{\beta
h}\xi_{h+1}^{m}$ $\displaystyle+3eH^{2}\left(2e^{\beta H}\beta
WB_{r}+\left(e^{\beta H}\beta H+\left(e^{\beta
H}-1\right)\right)WB_{\mathcal{P}}\right)$

where the first step uses the fact that $\delta_{H+1}^{m}=0$ for $m\in[M]$;
the last step holds since $(1+1/H)^{h}\leq$ $(1+1/H)^{H}\leq e$ for all
$h\in[H]$. Furthermore, the definition of $\Gamma_{h,i}$ and Lemma E.3 imply
that

$\displaystyle\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}\leq
C_{2}\left(e^{\beta(H-h+1)-1}\right)\sqrt{\frac{H\iota}{t}}.$

for some constant $C_{2}>0$. By the pigeonhole principle, for any $h\in[H]$ we
have

$\displaystyle\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\sum_{h\in[H]}e^{\beta(h-1)}\sum_{i\in[t]}\alpha_{t}^{i}\Gamma_{h,i}$
$\displaystyle\leq C_{2}\left(e^{\beta
H}-1\right)\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\sqrt{\frac{H\iota}{n_{h}^{m}}}$
$\displaystyle\leq C_{2}\left(e^{\beta
H}-1\right)\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sqrt{W}\sqrt{\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}\frac{H\iota}{n_{h}^{m}}}$
$\displaystyle\leq C_{2}\left(e^{\beta
H}-1\right)M\sqrt{H|\mathcal{S}||\mathcal{A}|\iota/W}$ (39)

where the second step follows from the Cauchy-Schwarz inequality, the third
step holds since $\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}N_{h}^{m}(s,a)=W$
and the right-hand side of the second step is maximized when
$N_{h}^{m}(s,a)=W/(|\mathcal{S}||\mathcal{A}|)$ for all
$(s,a)\in\mathcal{S}\times\mathcal{A}$. Finally, the Azuma-Hoeffding
inequality and the fact that $\left|\left(1+\frac{1}{H}\right)^{h-1}e^{\beta
h}\xi_{h+1}^{m}\right|\leq e\left(e^{\beta H}-1\right)$ for $h\in[H]$ together
imply that with probability at least $1-\delta$, we have

$\displaystyle\left|\sum_{h\in[H]}\sum_{m\in[M]}\left(1+\frac{1}{H}\right)^{h-1}e^{\beta
h}\xi_{h+1}^{m}\right|\leq C_{3}\left(e^{\beta H}-1\right)\sqrt{HM\iota}$ (40)

for some constant $C_{3}>0$. Plugging Equations (39) and (40) into (38), we
have

$\displaystyle\sum_{m\in[M]}\delta_{1}^{m}\leq$
$\displaystyle\mathcal{O}\left(\left(e^{\beta
H}-1\right)M\sqrt{H|\mathcal{S}||\mathcal{A}|\iota/W}+\left(e^{\beta
H}-1\right)\sqrt{HM\iota}\right.$ $\displaystyle\left.+H^{2}\left(2e^{\beta
H}\beta WB_{r}+\left(e^{\beta H}\beta H+\left(e^{\beta
H}-1\right)\right)WB_{\mathcal{P}}\right)\right)$ (41)

when $M$ is large enough. Invoking Lemma E.1 yields that

$\displaystyle\operatorname{D-Regret}(M)$ $\displaystyle\leq$
$\displaystyle\sum_{m\in[M]}\frac{1}{\beta}\left[e^{\beta\cdot
V_{1}^{*,m}\left(s_{1}^{m}\right)}-e^{\beta\cdot
V_{1}^{m}\left(s_{1}^{m}\right)}\right]+\sum_{m\in[M]}\frac{1}{\beta}\left[e^{\beta\cdot
V_{1}^{m}\left(s_{1}^{m}\right)}-e^{\beta\cdot
V_{1}^{\pi^{m},m}\left(s_{1}^{m}\right)}\right]$ $\displaystyle\leq$
$\displaystyle\frac{1}{\beta}\sum_{\mathcal{E}=1}^{\left\lceil{\frac{M}{W}}\right\rceil}\sum_{m=(\mathcal{E}-1)W}^{\mathcal{E}W}H\left(2e^{\beta
H}\beta B_{r,\mathcal{E}}+\left(e^{\beta H}\beta H+\left(e^{\beta
H}-1\right)\right)B_{\mathcal{P},\mathcal{E}}\right)$
$\displaystyle+\sum_{m\in[M]}\frac{1}{\beta}\left[e^{\beta\cdot
V_{1}^{m}\left(s_{1}^{m}\right)}-e^{\beta\cdot
V_{1}^{\pi^{m},m}\left(s_{1}^{m}\right)}\right]$ $\displaystyle\leq$
$\displaystyle\frac{1}{\beta}WH\left(2e^{\beta H}\beta B_{r}+\left(e^{\beta
H}\beta H+\left(e^{\beta
H}-1\right)\right)B_{\mathcal{P}}\right)+\frac{1}{\beta}\sum_{m\in[M]}\delta_{1}^{m}$
$\displaystyle\leq$ $\displaystyle\frac{1}{\beta}WH\left(2e^{\beta H}\beta
B_{r}+\left(e^{\beta H}\beta H+\left(e^{\beta
H}-1\right)\right)B_{\mathcal{P}}\right)$
$\displaystyle+\frac{1}{\beta}\mathcal{O}\left(\left(e^{\beta
H}-1\right)M\sqrt{H|\mathcal{S}||\mathcal{A}|\iota/W}+\left(e^{\beta
H}-1\right)\sqrt{HM\iota}\right.$ $\displaystyle\left.+\hskip
19.91684ptH^{2}\left(2e^{\beta H}\beta WB_{r}+\left(e^{\beta H}\beta
H+\left(e^{\beta H}-1\right)\right)WB_{\mathcal{P}}\right)\right)$
$\displaystyle\leq$ $\displaystyle\mathcal{O}\left(e^{\beta
H}HM\sqrt{H|\mathcal{S}||\mathcal{A}|\iota/W}+e^{\beta
H}H\sqrt{HM\iota}+H^{2}e^{\beta H}W\left(B_{r}+HB_{\mathcal{P}}\right)\right)$
(42) $\displaystyle\leq$ $\displaystyle\widetilde{\mathcal{O}}\left(e^{\beta
H}M\sqrt{H^{3}|\mathcal{S}||\mathcal{A}|/W}+e^{\beta
H}\sqrt{H^{3}M}+H^{3}e^{\beta H}W\left(B_{r}+B_{\mathcal{P}}\right)\right)$
(43)

where the second step holds by (33), the third inequality holds because of the
definition of $B_{\mathcal{P}}$, $B_{{r}}$ and $\delta_{1}^{m}$, the forth
inequality is due to (41), and the fifth inequality follows from $e^{\beta
H}-1\leq\beta He^{\beta H}$ for $\beta>0$. Finally, by setting
$W=M^{\frac{2}{3}}H^{-\frac{3}{4}}\left(B_{\mathcal{P}}+B_{r}\right)^{-\frac{2}{3}}|S|^{\frac{1}{3}}|A|^{\frac{1}{3}}$,
we conclude that

$\displaystyle\operatorname{D-Regret(M)}\leq$
$\displaystyle\widetilde{\mathcal{O}}\left(e^{\beta
H}|S|^{\frac{1}{3}}|A|^{\frac{1}{3}}H^{\frac{9}{4}}M^{\frac{2}{3}}\left(B_{\mathcal{P}}+B_{r}\right)^{\frac{1}{3}}\right).$

The proof is similar for the case of $\beta<0$, and one only needs to exchange
the role of $V_{h}^{m}$, $V_{h}^{\pi^{m},m}$ and $V_{h}^{*,m}$ in the
definitions of $\delta_{h}^{m},\phi_{h}^{m},\xi_{h}^{m}$:

$\displaystyle\delta_{h}^{m}$ $\displaystyle:=e^{\beta\cdot
V_{h}^{\pi^{m}}\left(s_{h}^{m}\right)}-e^{\beta\cdot
V_{h}^{m}\left(s_{h}^{m}\right)},$ $\displaystyle\phi_{h}^{m}$
$\displaystyle:=e^{\beta\cdot V_{h}^{*,m}\left(s_{h}^{m}\right)}-e^{\beta\cdot
V_{h}^{m}\left(s_{h}^{m}\right)},$ $\displaystyle\xi_{h+1}^{m}$
$\displaystyle:=\left[\left(\mathcal{P}^{m}_{h}-\widehat{\mathcal{P}}_{h}^{m}\right)\left(e^{\beta\cdot
V_{h+1}^{\pi^{m}}}-e^{\beta\cdot
V_{h+1}^{*,m}}\right)\right]\left(s_{h}^{m},a_{h}^{m}\right)$

to derive the counterparts of (36) and (37), and complete the remaining
analysis.

##  Appendix C Proof of Theorem 4.1

###  C.1 Multi-scale ALG Initialization

Algorithm 4 Multi-scale ALG Initialization (MALG-initialization)

1: Inputs: ALG and its associated $\rho(\cdot)$, n;

2: for $\tau=0,\ldots,2^{n}-1$ do

3: for k=n,n-1,…,0 do

4: If $\tau$ is a multiple of $2^{k}$, with probability
$\frac{\rho(2^{n})}{\rho(2^{k})}$, schedule a new instance $alg$ of ALG that
starts at $alg.s=\tau+1$ and ends at $alg.e=\tau+2^{k}$

5: end for

6: end for

###  C.2 An illustrative example

For better illustration, we give an example with $n=4$. This example has also
been shown in (Wei and Luo 2021) and we present here for completeness. By
Algorithm 4, one possible realization of the MALG initialization is shown in
Figure 2 with one order-4 instance (red), zero order-3 instance, two order-2
instances (green), two order-1 instances (purple) and five order-0 instances
(blue). The bolder part of the segment indicates the period of time when the
instances are active, while the thinner part indicates the inactive period. At
any point of time, the active instance is always the one with the shortest
length. The dashed arrow marked with 1 indicates that ALG is executed as of
the two sides of the arrow are concatenated. On the other hand, the two blue
instances on the two sides of the dashed line marked with 2 are two different
order-0 instances, so the second one should start from scratch even though
they are consecutive.

Figure 2: An illustrate example of MALG with $n=4$.

###  C.3 Preliminaries