# Non-stationary Reinforcement Learning without Prior Knowledge:
An Optimal Black-box Approach

Chen-Yu Wei
University of Southern California
<EMAIL_ADDRESS>
Haipeng Luo
University of Southern California
<EMAIL_ADDRESS>
###### Abstract

We propose a black-box reduction that turns a certain reinforcement learning
algorithm with optimal regret in a (near-)stationary environment into another
algorithm with optimal dynamic regret in a non-stationary environment,
importantly without any prior knowledge on the degree of non-stationarity. By
plugging different algorithms into our black-box, we provide a list of
examples showing that our approach not only recovers recent results for
(contextual) multi-armed bandits achieved by very specialized algorithms, but
also significantly improves the state of the art for (generalized) linear
bandits, episodic MDPs, and infinite-horizon MDPs in various ways.
Specifically, in most cases our algorithm achieves the optimal dynamic regret
$\widetilde{\mathcal{O}}(\min\\{\sqrt{LT},\Delta^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}\\})$
where $T$ is the number of rounds and $L$ and $\Delta$ are the number and
amount of changes of the world respectively, while previous works only obtain
suboptimal bounds and/or require the knowledge of $L$ and $\Delta$.

##  1 Introduction

Most existing works on reinforcement learning consider a stationary
environment and aim to find or be comparable to an optimal policy (known as
having low _static regret_). In many applications, however, the environment is
far from being stationary. In these cases, it is much more meaningful to
minimize _dynamic regret_ , the gap between the total reward of the optimal
sequence of policies and that of the learner. Indeed, there is a surge of
studies on this topic recently (Jaksch et al., 2010; Gajane et al., 2018; Li
and Li, 2019; Ortner et al., 2020; Cheung et al., 2020; Fei et al., 2020;
Domingues et al., 2021; Mao et al., 2021; Zhou et al., 2020; Touati and
Vincent, 2020).

One common issue of all these works, however, is that their algorithms
crucially rely on having some prior knowledge on the _degree of non-
stationarity_ of the world, such as how much or how many times the
distribution changes, which is often unavailable in practice. Cheung et al.
(2020) develop a Bandit-over-Reinforcement-Learning (BoRL) framework to relax
this assumption, but it introduces extra overhead and leads to suboptimal
regret. Indeed, as discussed in their work, there are multiple aspects (which
they call _endogeneity_ , _exogeneity_ , _uncertainty_ , and _bandit
feedback_) combined in non-stationary reinforcement learning that make the
problem highly challenging.

For bandit problems, the special case of reinforcement learning, the works of
Auer et al. (2019) and Chen et al. (2019) are the first to achieve near-
optimal dynamic regret without any prior knowledge on the degree of non-
stationarity. The same technique has later been adopted by Chen et al. (2020)
for the case of combinatorial semi-bandits. Their algorithms maintain a
distribution over arms (or policies/super-arms in the contextual/combinatorial
case (Chen et al., 2019, 2020)) with properly controlled variance for all
reward estimators. This approach is generally incompatible with standard
reinforcement learning algorithms, which are usually built upon the _optimism
in the face of uncertainty_ principle and do not maintain a distribution over
policies (see also (Lykouris et al., 2021; Wang et al., 2020) for related
discussions). Another drawback is that their algorithms are very specialized
to their problems, and it is highly unclear whether the ideas can be extended
to other problems.

In this work, we address all these issues and make significant progress in
this direction. Specifically, we propose a general approach that is applicable
to various reinforcement learning settings (including bandits, episodic MDPs,
infinite-horizon MDPs, etc.) and achieves optimal dynamic regret without any
prior knowledge on the degree of non-stationarity. Our approach, called
MASTER, is a black-box reduction that turns any algorithm with optimal
performance in a (near-)stationary environment and additionally some mild
requirements into another algorithm with optimal dynamic regret in a non-
stationary environment, again, without the need of any prior knowledge. For
example, all existing UCB-based algorithms satisfy the conditions of our
reduction and are readily to be plugged into our black-box.

Table 1: A summary of our results and comparisons with the state-of-the-art. Our algorithms are named in the form of “MASTER \+ $X$” where $X$ is the base algorithm used in our reduction. Here, $\text{\rm Reg}_{L}^{\star}=\sqrt{LT}$ and $\text{\rm Reg}_{\Delta}^{\star}=\Delta^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}+\sqrt{T}$, where $T$ is the number of rounds and $L$ and $\Delta$ are the number and amount of changes of the world respectively (dependence on other parameters is omitted). $D_{\max}$ is the maximum diameters of the MDPs.  Setting | Algorithm | Regret in $\widetilde{\mathcal{O}}(\cdot)$ |  Required knowledge
---|---|---|---
Multi-armed bandits |  (Auer et al., 2019) | $\text{\rm Reg}_{L}^{\star}$ |
MASTER \+ UCB1 | $\min\\{\text{\rm Reg}_{L}^{\star},\text{\rm Reg}_{\Delta}^{\star}\\}$ |
Contextual bandits |  (Chen et al., 2019) | $\min\\{\text{\rm Reg}_{L}^{\star},\text{\rm Reg}_{\Delta}^{\star}\\}$ |
MASTER \+ ILTCB |
MASTER \+ FALCON |
Linear bandits |  (Cheung et al., 2018) | $\text{\rm Reg}_{\Delta}^{\star}$ | $\Delta$
(Cheung et al., 2018) | $\text{\rm Reg}_{\Delta}^{\star}+T^{\nicefrac{{3}}{{4}}}$ |
MASTER \+ OFUL | $\min\\{\text{\rm Reg}_{L}^{\star},\text{\rm Reg}_{\Delta}^{\star}\\}$ |
Generalized linear bandits |  (Russac et al., 2020) | $L^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}$ | $L$
(Faury et al., 2021) | $\Delta^{\nicefrac{{1}}{{5}}}T^{\nicefrac{{4}}{{5}}}+T^{\nicefrac{{3}}{{4}}}$ |
MASTER \+ GLM-UCB | $\min\\{\text{\rm Reg}_{L}^{\star},\text{\rm Reg}_{\Delta}^{\star}\\}$ |
Episodic MDPs (tabular case) |  (Mao et al., 2021) | $\text{\rm Reg}_{\Delta}^{\star}$ | $\Delta$
MASTER \+ Q-UCB | $\min\\{\text{\rm Reg}_{L}^{\star},\text{\rm Reg}_{\Delta}^{\star}\\}$ |
Episodic MDPs (linear case) |  (Touati and Vincent, 2020) | $\Delta^{\nicefrac{{1}}{{4}}}T^{\nicefrac{{3}}{{4}}}+\sqrt{T}$ | $\Delta$
MASTER \+ LSVI-UCB | $\min\\{\text{\rm Reg}_{L}^{\star},\text{\rm Reg}_{\Delta}^{\star}\\}$ |
Infinite-horizon communicating MDPs (tabular case) |  (Gajane et al., 2018) | $L^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}$ | $L$
(Cheung et al., 2020) | $\Delta^{\nicefrac{{1}}{{4}}}T^{\nicefrac{{3}}{{4}}}+\sqrt{T}$ | $\Delta$
(Cheung et al., 2020) | $\Delta^{\nicefrac{{1}}{{4}}}T^{\nicefrac{{3}}{{4}}}+T^{\nicefrac{{3}}{{4}}}$ |
MASTER \+ UCRL | $\text{\rm Reg}_{L}^{\star}$ or $\text{\rm Reg}_{\Delta}^{\star}$ |  $L$ or $\Delta$
MASTER \+ UCRL | $\min\\{\text{\rm Reg}_{L}^{\star},\text{\rm Reg}_{\Delta}^{\star}\\}$ |  $D_{\max}$
MASTER \+ UCRL + BoRL |  $\min\\{\text{\rm Reg}_{L}^{\star},\text{\rm Reg}_{\Delta}^{\star}\\}+T^{\nicefrac{{3}}{{4}}}$ |
|  |  |

#### Applications and comparisons

To showcase the versatility of our approach, we provide a list of examples by
considering different settings and applying our reduction with different base
algorithms. These examples, summarized in Table 1, recover the results of Auer
et al. (2019) and Chen et al. (2019) for (contextual) multi-armed bandits, and
more importantly, improve the best known results for (generalized) linear
bandits, episodic MDPs, and infinite-horizon MDPs in various ways. More
specifically, let $L$ and $\Delta$ be the number and amount of changes of the
environment respectively (see Section 2.1 for formal definition). For all
settings except infinite-horizon MDPs, ignoring other parameters, our
algorithms achieve dynamic regret $\min\\{\text{\rm Reg}_{L}^{\star},\text{\rm
Reg}_{\Delta}^{\star}\\}$ without knowing $L$ and $\Delta$, where $\text{\rm
Reg}_{L}^{\star}=\sqrt{LT}$, $\text{\rm
Reg}_{\Delta}^{\star}=\Delta^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}+\sqrt{T}$,
and $T$ is the number of rounds. These bounds are known to be optimal even
when $L$ and $\Delta$ are known, and they improve over (Cheung et al., 2018,
2019; Russac et al., 2019; Kim and Tewari, 2020; Zhao et al., 2020; Zhao and
Zhang, 2021) for linear bandits, (Russac et al., 2020; Faury et al., 2021) for
generalized linear bandits, (Mao et al., 2021) for episodic tabular MDPs, and
(Touati and Vincent, 2020; Zhou et al., 2020) for episodic linear MDPs. For
infinite-horizon MDPs, we achieve the same optimal regret when the maximum
diameter of the MDPs is known, or when $L$ and $\Delta$ are known, improving
over the best existing results by (Gajane et al., 2018) and (Cheung et al.,
2020). When none of them is known, we can still adopt the BoRL technique
(Cheung et al., 2020) with the price of paying extra $T^{3/4}$ regret, which
is suboptimal but still outperforms best known results.

In particular, we emphasize that achieving dynamic regret $\text{\rm
Reg}_{L}^{\star}$ beyond (contextual) multi-armed bandits is one notable
breakthrough we make. Indeed, _even when $L$ is known_, previous approaches
based on restarting after a fixed period, a sliding window with a fixed size,
or discounting with a fixed discount factor, all lead to a suboptimal bound of
$\widetilde{\mathcal{O}}(L^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}})$ at
best (Gajane et al., 2018). Since this bound is subsumed by $\text{\rm
Reg}_{\Delta}^{\star}$, related discussions are also often omitted in previous
works.

For non-stationary linear bandits, although several existing works (Russac et
al., 2019; Kim and Tewari, 2020; Zhao et al., 2020) claim that their
algorithms achieve the bound $\text{\rm Reg}_{\Delta}^{\star}$ (when $\Delta$
is known), there is in fact a technical flaw in all of them, as explained and
corrected recently in (Zhao and Zhang, 2021; Touati and Vincent, 2020). After
the correction, their bounds all deteriorate to
$\Delta^{\nicefrac{{1}}{{4}}}T^{\nicefrac{{3}}{{4}}}+\sqrt{T}$, which is no
longer near-optimal. Recently, Cheung et al. (2018) sidesteps this difficulty
by leveraging adversarial linear bandit algorithms, and achieves the tight
bound of $\text{\rm Reg}_{\Delta}^{\star}$ when $\Delta$ is known. On the
other hand, our approach is based on stochastic linear bandit algorithms;
however, it not only sidesteps the difficulty met in previous works, but also
avoids the requirement of knowing $\Delta$. When dealing with other linear-
structured problems including generalized linear bandits and linear MDPs, our
bounds $\text{\rm Reg}_{\Delta}^{\star}$ is new _even when $\Delta$ is known_.
Previous results (Russac et al., 2020; Faury et al., 2021; Touati and Vincent,
2020; Zhou et al., 2020) cannot achieve the optimal bound due to the same
technical difficulty mentioned above.

#### High-level ideas

The high-level idea of our reduction is to schedule multiple instances of the
base algorithm with different durations in a carefully-designed randomized
scheme, which facilitates non-stationarity detection with little overhead. A
related and well-known approach for non-stationary environments is to maintain
multiple instances of a base algorithm with different parameter tunings or
different starting points and to learn the best of them via another “expert”
algorithm, which can be very successful when learning with full information
(Hazan and Seshadhri, 2007; Luo and Schapire, 2015; Daniely et al., 2015; Jun
et al., 2017) but is suboptimal and has many limitations when learning with
partial information (Luo et al., 2018; Cheung et al., 2019, 2020). Our
approach is different as we do not try to learn the best instance; instead, we
always follow the decision suggested by the instance with the currently
shortest scheduled duration, and also only update this instance after
receiving feedback from the environment. The is because base algorithms with
shorter duration are responsible for detecting larger distribution changes,
and always following the shortest one ensure that it is not blocked by the
longer ones and thus every scale of distribution change is detected in a
timely manner.

Another related approach is _regret balancing_ , developed recently for model
selection in bandit problems (Abbasi-Yadkori et al., 2020; Pacchiano et al.,
2020). The idea is also to run multiple base algorithms in parallel, each with
a putative regret upper bound. The learner executes one of them in each round
which incurs the least regret so far, and also constantly compares the
performance among base algorithms, eliminating those whose putative regret
bounds are violated. While our algorithm resembles regret balancing in some
aspects, the way it chooses the base algorithm in each round is clearly quite
different, which is also crucial for our problem.

#### Other related work

There are also a series of works on learning MDPs with adversarial rewards and
a fixed transition (Even-Dar et al., 2009; Neu et al., 2010; Arora et al.,
2012; Neu et al., 2012; Dekel and Hazan, 2013; Neu et al., 2013; Zimin and
Neu, 2013; Dick et al., 2014; Rosenberg and Mansour, 2019; Cai et al., 2020;
Jin et al., 2020a; Shani et al., 2020; Rosenberg and Mansour, 2020; Lee et
al., 2020; Jin and Luo, 2020; Chen et al., 2021; Lancewicki et al., 2020).
These models can potentially handle non-stationarity in the reward function
but not the transition kernel (in fact, most of these works also only consider
static regret). Lykouris et al. (2021) investigate an episodic MDP setting
where an adversary can corrupt both the reward and the transition for up to
$L^{\prime}$ episodes, and achieve dynamic regret
$\widetilde{\mathcal{O}}(\min\\{L^{\prime}\sqrt{T},L^{\prime}/\textit{gap}\\})$
without knowing $L^{\prime}$, where gap is the minimal suboptimality gap and
could be arbitrarily small. Since corruption of up to $L^{\prime}$ episodes
implies that the world changes at most $L=2L^{\prime}$ times, our result
improves theirs from $\widetilde{\mathcal{O}}(L^{\prime}\sqrt{T})$ to
$\widetilde{\mathcal{O}}(\sqrt{L^{\prime}T})$ when $1/\textit{gap}>\sqrt{T}$.
On the other hand, it is possible that $L$ is much smaller than $L^{\prime}$
(e.g. $L=\Theta(1)$ while $L^{\prime}=\Theta(T)$), in which case our results
are also significantly better.

##  2 Problem Setting, Main Results, and High-level Ideas

Throughout the paper, we fix a probability parameter $\delta$ of order
$1/\text{poly}(T)$, and write $h_{1}(x)=\widetilde{\mathcal{O}}(h_{2}(x))$ or
$h_{2}(x)=\widetilde{\Omega}(h_{1}(x))$ if
$h_{1}(x)=\mathcal{O}\left(\text{poly}(\log(T/\delta))h_{2}(x)\right)$. We say
“with high probability, $h_{1}=\widetilde{\mathcal{O}}(h_{2}(x))$” if “with
probability $1-\delta$, $h_{1}=\widetilde{\mathcal{O}}(h_{2}(x))$”. For an
integer $n$, we denote the set $\\{1,2,\ldots,n\\}$ by $[n]$; and for integers
$s$ and $e$, we denote the set $\\{s,s+1,\ldots,e\\}$ by $[s,e]$.

###  2.1 Problem setting

We consider the following general reinforcement learning (RL) framework that
covers a wide range of problems. Ahead of time, the learner is given a policy
set $\Pi$, and the environment decides $T$ reward functions
$f_{1},\ldots,f_{T}:\Pi\to[0,1]$ unknown to the learner. Then, in each round
$t=1,\ldots,T$, the learner chooses a policy $\pi_{t}\in\Pi$ and receives a
noisy reward $R_{t}\in[0,1]$ whose mean is $f_{t}(\pi_{t})$.111The range
$[0,1]$ is only for simplicity. Our results can be directly extended to the
case with sub-Gaussian noise.  The dynamic regret of the learner is defined as
$\textsc{D-Reg}=\sum_{t=1}^{T}\left(f^{\star}_{t}-R_{t}\right)$, where
$f^{\star}_{t}=\max_{\pi\in\Pi}f_{t}(\pi)$ is the expected reward of the
optimal policy for round $t$.

Many heavily-studied problems fall into this framework. For example, in the
classic multi-armed bandit problem (Lai and Robbins, 1985), it suffices to
treat each arm as a policy; for finite-horizon episodic RL (e.g. (Jin et al.,
2018)), each state-to-action mapping is considered as a policy, and
$f_{t}(\pi)$ is the expected reward of executing $\pi$ in the $t$-th episode’s
MDP with some transition kernel and some reward function. See more examples in
Appendix I. Note that our framework ignores many details of the actual problem
we are trying to solve (e.g. not even mentioning the MDPs for RL). This is
because our results only rely on certain guarantees provided by a base
algorithm, making these details irrelevant to our presentation. There is also
some technicality to fit the infinite-horizon RL problem into our framework,
which we will discuss in detail in Section 4.

#### Non-stationarity measure

A natural way to measure the distribution drift between rounds $t$ and $t+1$
is to see how much the expected reward of any policy could change, that is,
$\max_{\pi\in\Pi}|f_{t}(\pi)-f_{t+1}(\pi)|$. However, to make our results more
general, we take a sligtly more abstract way to define non-stationarity whose
exact form eventually depends on what guarantees the base algorithm can
provide for a concrete problem. To this end, we define the following.

######  Definition 1.

$\Delta:[T]\to\mathbb{R}$ is a non-stationarity measure if it satisfies
$\Delta(t)\geq\max_{\pi\in\Pi}|f_{t}(\pi)-f_{t+1}(\pi)|$ for all $t$. Define
for any interval $\mathcal{I}=[s,e]$,
$\Delta_{\mathcal{I}}=\sum_{\tau=s}^{e-1}\Delta(\tau)$ (note
$\Delta_{[s,s]}=0$) and
$L_{\mathcal{I}}=1+\sum_{\tau=s}^{e-1}\mathbbm{1}[\Delta(\tau)\neq 0]$. With
slight abuse of notation, we write $\Delta=\Delta_{[1,T]}$ and $L=L_{[1,T]}$.

#### Base algorithm and requirements

As mentioned, our approach takes a base algorithm that tackles the problem
when the environment is (near-)stationary, and turns it into another algorithm
that can deal with non-stationary environments. Throughout the paper, we
denote the base algorithm by ALG and assumes that it satisfies the following
mild requirements when run alone.

######  Assumption 1.

ALG outputs an auxiliary quantity $\widetilde{f}_{t}\in[0,1]$ at the beginning
of each round $t$. There exist a non-stationarity measure $\Delta$ and a non-
increasing function $\rho:[T]\to\mathbb{R}$ such that running ALG satisfies
the following: for all $t\in[T]$, as long as $\Delta_{[1,t]}\leq\rho(t)$,
without knowing $\Delta_{[1,t]}$ ALG ensures with probability at least
$1-\frac{\delta}{T}$:

$\displaystyle\widetilde{f}_{t}\geq\min_{\tau\in[1,t]}f_{\tau}^{\star}-\Delta_{[1,t]}\qquad\text{and}\qquad\frac{1}{t}\sum_{\tau=1}^{t}\left(\widetilde{f}_{\tau}-R_{\tau}\right)\leq\rho(t)+\Delta_{[1,t]}.$
(1)

Furthermore, we assume that $\rho(t)\geq\frac{1}{\sqrt{t}}$ and
$C(t)=t\rho(t)$ is a non-decreasing function.

We unpack the meaning of this assumption and explain why this is a mild
requirement via a few remarks below, followed by examples of existing
algorithms that do satisfy our assumption.

First, consider choosing $\Delta(t)=\max_{\pi\in\Pi}|f_{t}(\pi)-f_{t+1}(\pi)|$
and see what the assumption means for a stationary environment with $f_{t}=f$
and $\Delta(t)=0$ for all $t$. In this case, Eq. (1) simply becomes
$\widetilde{f}_{t}\geq\max_{\pi\in\Pi}f(\pi)$ and
$\sum_{\tau=1}^{t}\left(\widetilde{f}_{\tau}-R_{\tau}\right)\leq C(t)$, which
are standard properties of _Upper-Confidence-Bound (UCB)-based_ algorithms,
where $\widetilde{f}_{t}$ is an _optimistic_ estimator of the optimal reward
and $C(t)$ is the regret bound usually of order $\sqrt{t}$. In fact, even for
non-UCB-based algorithms that do not explicitly maintain optimistic
estimators, by looking into their analysis, it is still possible to extract a
quantity $\widetilde{f}_{t}$ satisfying these two properties (see our example
for contextual bandits in Appendix I). We also note that this requirement for
the special stationary case is in fact all we need to achieve our claimed
regret bound $\text{\rm Reg}_{L}^{\star}$.

Second, to simultaneously achieve the regret bound $\text{\rm
Reg}_{\Delta}^{\star}$ as well, we require slightly more from the base
algorithm: in a near-stationary environment with $\Delta_{[1,t]}\leq\rho(t)$,
the two aforementioned properties still hold approximately with degradation
$\Delta_{[1,t]}$ (that is, Eq. (1)).222We use
$\min_{\tau\in[1,t]}f_{\tau}^{\star}$ instead of the more natural one
$f_{t}^{\star}$ since the former is weaker and the difference between these
two is at most $\Delta_{[1,t]}$ anyway.  We call this a near-stationary
environment because $\Delta_{[1,t]}$ can be of order $\Theta(t)$ in a highly
non-stationary environment, while here we restrict it to be at most $\rho(t)$,
which is non-increasing in $t$ (and in fact of order $1/\sqrt{t}$ in all our
examples). To the best of our knowledge, all UCB-based algorithms satisfy
Assumption 1 with some suitable choice of $\Delta$. The fact that we only
require Eq. (1) to hold for near-stationary environments is the key to
bypassing the technical difficulty of getting the optimal bound $\text{\rm
Reg}_{\Delta}^{\star}$ met in (Russac et al., 2019; Zhao et al., 2020; Russac
et al., 2020; Faury et al., 2021; Touati and Vincent, 2020; Zhou et al., 2020)
for linear bandits, generalized linear bandits, and linear MDPs, as mentioned
in Section 1.

Finally, noting that $\rho(t)$ and $C(t)$ represent an average and an
cumulative regret bound respectively, the monotonicity requirement on them is
more than natural. The requirement $\rho(t)\geq\frac{1}{\sqrt{t}}$ is also
usually unavoidable without further structures in the problem. Note that while
we write $\rho$ and $C$ as a function of $t$ only, they can depend on
$\log(1/\delta)$, $\log T$, the complexity of $\Pi$, and other problem-
dependent parameters such as the number of states/actions of an MDP.

Following the order in Table 1, we now give a list of existing algorithms that
satisfy Assumption 1 in different problem settings with proper non-
stationarity measure $\Delta$ and regret bound $C$. We defer the concrete form
of $\widetilde{f}_{t}$ (which requires introducing other notations) and all
the proofs to Appendix I.

  * •

UCB1 (Auer et al., 2002a): $C(t)=\widetilde{\mathcal{O}}(\sqrt{At}+A)$ and
$\Delta(t)=\Theta(\|r_{t}-r_{t+1}\|_{\infty})$, where $A$ is the number of
arms, and $r_{t}$ is the expected reward vector at time $t$.

  * •

ILTCB (Agarwal et al., 2014, short for ILOVETOCONBANDITS):
$C(t)=\widetilde{\mathcal{O}}(\sqrt{At\log|\Pi|}+A\log|\Pi|)$ and
$\Delta(t)=\Theta\left(\int_{r}\int_{x}|\mathcal{D}_{t}(x,r)-\mathcal{D}_{t+1}(x,r)|\mathrm{d}x\mathrm{d}r\right)$,
where $A$ is the number of actions and $\mathcal{D}_{t}$ is the joint
distribution of the context-reward pair $(x,r)$ at time $t$.

  * •

FALCON (Simchi-Levi and Xu, 2020):
$C(t)=\widetilde{\mathcal{O}}(\sqrt{At\log|\Phi|}+A\log|\Phi|)$ and
$\Delta(t)=\Theta(\sqrt{A}\max_{x,a}|\phi_{t}^{\star}(x,a)-\phi_{t+1}^{\star}(x,a)|+\int_{x}|\mathcal{D}_{t}(x)-\mathcal{D}_{t+1}(x)|\mathrm{d}x)$,
where $A$ is the number of actions, $\Phi$ is the set of regressors (each of
which maps a context-action pair to a predicted reward),
$\phi^{\star}_{t}\in\Phi$ is the true regressor at time $t$, and
$\mathcal{D}_{t}$ is the distribution of contexts at time $t$.

  * •

OFUL (Abbasi-Yadkori et al., 2011):
$C(t)=\widetilde{\mathcal{O}}\left(d\sqrt{t}\right)$ and
$\Delta(t)=\widetilde{\Theta}(d\|\theta_{t}-\theta_{t+1}\|_{2})$, where $d$ is
the feature dimension and $\theta_{t}\in\mathbb{R}^{d}$ parameterizes the
linear reward function at time $t$.

  * •

GLM-UCB (Filippi et al., 2010):
$C(t)=\widetilde{\mathcal{O}}\left(\frac{k_{\mu}d}{c_{\mu}}\sqrt{t}\right)$
and
$\Delta(t)=\widetilde{\Theta}\left(\frac{k_{\mu}^{2}d}{c_{\mu}}\|\theta_{t}-\theta_{t+1}\|_{2}\right)$,
where $d$ is the feature dimension, $\theta_{t}\in\mathbb{R}^{d}$
parameterizes the linear reward function at time $t$, and $k_{\mu},c_{\mu}$
are the upper and lower bounds of the gradient of the link function.

  * •

Q-UCB (Jin et al., 2018, short for Q-learning UCB-H):333For ease of
comparison, here, the reward range is changed from $[0,1]$ to the more common
$[0,H]$.  $C(t)=\widetilde{\mathcal{O}}(\sqrt{H^{5}SAt}+H^{3}SA)$ and
$\Delta(t)=\Theta(H\sum_{h=1}^{H}\max_{s,a}|r_{h}^{t}(s,a)-r_{h}^{t+1}(s,a)|+H^{2}\sum_{h=1}^{H}\max_{s,a}\|p_{h}^{t}(\cdot|s,a)-p_{h}^{t+1}(\cdot|s,a)\|_{1})$,
where $H$, $S$ and $A$ are the numbers of layers, states, and actions of the
MDP respectively, and $p_{h}^{t}$ and $r_{h}^{t}$ are the transition and
reward functions for layer $h$ of episode $t$.

  * •

LSVI-UCB (Jin et al., 2020b):444Same as Footnote 3.
$C(t)=\widetilde{\mathcal{O}}(\sqrt{d^{3}H^{4}t})$ and
$\Delta(t)=\widetilde{\Theta}(dH\sum_{h=1}^{H}\|\theta_{h}^{t}-\theta_{h}^{t+1}\|_{2}+dH^{2}\sum_{h=1}^{H}\|\mu_{h}^{t}-\mu_{h}^{t+1}\|_{F})$,
where $d$ is the feature dimension, $H$ is the number of layers, and
$\theta_{h}^{t}$ and $\mu_{h}^{t}$ are the parameters of the linear MDP for
layer $h$ of episode $t$.

###  2.2 Main results

Our main result is that, with an algorithm satisfying Assumption 1 at hand,
our proposed black-box reduction, MASTER (Algorithm 3), ensures the following
dynamic regret bound.

######  Theorem 2.

If Assumption 1 holds with $C(t)=c_{1}t^{p}+c_{2}$ for some
$p\in[\frac{1}{2},1)$ and $c_{1},c_{2}>0$, then MASTER (Algorithm 3), without
knowing $L$ and $\Delta$, guarantees with high probability:

$\displaystyle\textsc{D-Reg}=\widetilde{\mathcal{O}}\left(\min\left\\{\left(c_{1}+\frac{c_{2}}{c_{1}}\right)\sqrt{LT},\;\left(c_{1}^{\nicefrac{{2}}{{3}}}+c_{2}c_{1}^{-\nicefrac{{4}}{{3}}}\right)\Delta^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}+\left(c_{1}+\frac{c_{2}}{c_{1}}\right)\sqrt{T}\right\\}\right)$

when $p=\frac{1}{2}$, and
$\textsc{D-Reg}=\widetilde{\mathcal{O}}\left(\min\left\\{c_{1}L^{1-p}T^{p},\;\left(c_{1}\Delta^{1-p}T\right)^{\frac{1}{2-p}}+c_{1}T^{p}\right\\}\right)$
when $p>\frac{1}{2}$ (omitting some lower-order terms).

For ease of presentation, in this theorem we assume that $C(\cdot)$ takes a
certain form that is common in the literature and holds for all our examples
with $p=\frac{1}{2}$. Applying this theorem to all the examples discussed
earlier, we achieve all the optimal $\min\\{\text{\rm
Reg}_{L}^{\star},\text{\rm Reg}_{\Delta}^{\star}\\}$ bounds listed in Table 1
(except for infinite-horizon MDPs which will be discussed in Section 4). Our
definitions of $L$ are the same as in previous works, and our definitions of
$\Delta$ are sometimes larger by some problem-dependent factors (such as $d$
and $H$) in order to fit Assumption 1. More specifically, for (contextual)
bandits, our MASTER combined with UCB1 and ILTCB recovers the same optimal
bounds (in terms of all parameters) achieved by (Auer et al., 2019; Chen et
al., 2019). MASTER with FALCON obtains a similar bound as in (Chen et al.,
2019) but with a different definition of $\Delta$ specific to the regressor
setting. For other settings, we present our results in terms of the common
definition of the non-stationarity measure (denoted by $\widehat{\Delta}$) and
compare them with the state of the art:

  * •

MASTER \+ OFUL:
$\textsc{D-Reg}=\widetilde{\mathcal{O}}(\min\\{d\sqrt{LT},d\widehat{\Delta}^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}+d\sqrt{T}\\})$,
where $\widehat{\Delta}=\sum_{t}\|\theta_{t}-\theta_{t+1}\|_{2}$. This
improves (Cheung et al., 2019; Russac et al., 2019; Kim and Tewari, 2020; Zhao
et al., 2020; Zhao and Zhang, 2021) which get
$\widetilde{\mathcal{O}}(d^{\nicefrac{{7}}{{8}}}\widehat{\Delta}^{\nicefrac{{1}}{{4}}}T^{\nicefrac{{3}}{{4}}}+d\sqrt{T})$
when $\widehat{\Delta}$ is known.

  * •

MASTER \+ GLM-UCB:
$\textsc{D-Reg}=\widetilde{\mathcal{O}}\Big{(}\min\Big{\\{}\frac{k_{\mu}}{c_{\mu}}d\sqrt{LT},\frac{k_{\mu}^{\nicefrac{{4}}{{3}}}}{c_{\mu}}d\widehat{\Delta}^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}+\frac{k_{\mu}}{c_{\mu}}d\sqrt{T}\Big{\\}}\Big{)}$,
where $\widehat{\Delta}=\sum_{t}\|\theta_{t}-\theta_{t+1}\|_{2}$. This
improves (Russac et al., 2020) which gets
$\widetilde{\mathcal{O}}\big{(}\frac{k_{\mu}}{c_{\mu}}d^{\nicefrac{{2}}{{3}}}L^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}\big{)}$
when $L$ is known, and (Faury et al., 2021) which gets
$\widetilde{\mathcal{O}}\big{(}\frac{k_{\mu}}{c_{\mu}}d^{\nicefrac{{9}}{{10}}}\widehat{\Delta}^{\nicefrac{{1}}{{5}}}T^{\nicefrac{{4}}{{5}}}\big{)}$.

  * •

MASTER \+ Q-UCB:
$\textsc{D-Reg}=\widetilde{\mathcal{O}}(\min\\{\sqrt{H^{5}SALT},(H^{7}SA\widehat{\Delta})^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}+\sqrt{H^{5}SAT}\\})$,
where
$\widehat{\Delta}=\sum_{t,h}\max_{s,a}(|r_{h}^{t}(s,a)-r_{h}^{t+1}(s,a)|+\|p_{h}^{t}(\cdot|s,a)-p_{h}^{t+1}(\cdot|s,a)\|_{1})$.555Due
to the scaling mentioned in Footnote 3, here, we first scale down $C(\cdot)$
and $\Delta$ by an $H$ factor, then apply Theorem 2, and finally scale up the
final bound by an $H$ factor.  (Mao et al., 2021, Theorem 3) gets
$\widetilde{\mathcal{O}}((H^{5}SA\widehat{\Delta})^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}+\sqrt{H^{3}SAT})$
when $\widehat{\Delta}$ is known.666The bound reported in (Mao et al., 2021)
is
$(H^{3}SA\widehat{\Delta})^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}+\sqrt{H^{2}SAT}$;
however, their $T$ is the total number of timesteps while our $T$ is the
number of episodes, and we have performed a proper translation between
notations here. Their bound has a better $H$ dependency thanks to the use of
Freedman-style confidence bounds. The same idea unfortunately does not improve
our bound due to the lower-order term $c_{2}$ in the definition of $C(t)$.

  * •

MASTER \+ LSVI-UCB:
$\textsc{D-Reg}=\widetilde{\mathcal{O}}(\min\\{\sqrt{d^{3}H^{4}LT},(d^{4}H^{6}\widehat{\Delta})^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}+\sqrt{d^{3}H^{4}T}\\})$,
where
$\widehat{\Delta}=\sum_{t,h}(\|\theta_{h}^{t}-\theta_{h}^{t+1}\|_{2}+\|\mu_{h}^{t}-\mu_{h}^{t+1}\|_{F})$.
This improves (Zhou et al., 2020; Touati and Vincent, 2020) which get
$\widetilde{\mathcal{O}}((d^{5}H^{8}\widehat{\Delta})^{\nicefrac{{1}}{{4}}}T^{\nicefrac{{3}}{{4}}}+\sqrt{d^{3}H^{4}T})$
when $\widehat{\Delta}$ is known.777The same scaling as in Footnote 5 and
Footnote 6 has been performed here.

###  2.3 High-level ideas

To get a high-level idea of our approach, first consider what could go wrong
when running ALG alone in a non-stationary environment and how to fix that
intuitively. Decompose the dynamic regret as follows:

$\displaystyle\underbrace{\sum_{\tau=1}^{t}\left(f_{\tau}^{\star}-\widetilde{f}_{\tau}\right)}_{\textbf{term}_{1}}+\underbrace{\sum_{\tau=1}^{t}\left(\widetilde{f}_{\tau}-R_{\tau}\right)}_{\textbf{term}_{2}}.$
(2)

As mentioned, in a stationary environment, ALG ensures that
$\textbf{term}_{1}$ is simply non-positive and $\textbf{term}_{2}$ is bounded
by $C(t)$ directly. In a non-stationary environment, however, both terms can
be substantially larger. If we can detect the event that either of them is
abnormally large, we know that the environment has changed substantially, and
should just restart ALG. This detection can be easily done for
$\textbf{term}_{2}$ since both $\widetilde{f}_{\tau}$ and $R_{\tau}$ are
observable, but not for $\textbf{term}_{1}$ since $f_{\tau}^{\star}$ is of
course unknown. Note that, a large $\textbf{term}_{1}$ implies that a policy,
possibly suboptimal in the past, now becomes the optimal one with a much
larger reward. A single instance of ALG run from the beginning thus cannot
detect this because suboptimal polices are naturally selected very
infrequently.

Figure 1: An illustration of how we detect non-stationarity via multiple
instances of ALG

To address this issue, our main idea is to maintain different instances of ALG
to facilitates non-stationarity detection, illustrated via an example in
Figure 1. Here, there is one distribution change that happens in interval
$\mathcal{I}$, making the value of $f_{\tau}^{\star}$ (the blue curve)
drastically increase. If within this interval, we start running another
instance of ALG (the red interval), then its performance (the black curve)
will gradually approach $f_{\tau}^{\star}$ due to its regret guarantee in a
stationary environment. Hypothetically, if another instance of ALG run from
the beginning could coexist with this new instance, we would see that the
latter significantly outperforms the former and infer that the environment has
changed. The issue is that we cannot have multiple instances running and
making decisions simultaneously, and here is where the optimistic estimators
$\widetilde{f}_{\tau}$’s can help. Specifically, since the quantity
$U_{\tau}=\min_{s\leq\tau}\widetilde{f}_{s}$ (the green non-increasing curve)
should always be an upper bound of the learner’s performance in a stationary
environment, if we find that the new instance of ALG significantly outperforms
this quantity at some point (as shown in Figure 1), we can also infer that the
environment has changed, and prevent
$\textbf{term}_{1}\leq\sum_{\tau=1}^{t}(f_{\tau}^{\star}-U_{\tau})$ from
growing too large by restarting.

To formally implement the ideas above, we need to decide when to start a new
instance, how long it should last, which instance should be active if multiple
exist, and others. In Section 3, we propose a randomized multi-scale scheme to
do so, which is reminiscent of the ideas of sampling obligation in (Auer et
al., 2019) and replay phase in (Chen et al., 2019), although their mechanisms
are highly specific to their algorithms and problems.

##  3 Algorithm

In this section, we first introduce MALG, an algorithm that schedules and runs
multiple instances of the base algorithm ALG in a multi-scale manner (Section
3.1). Then, equipping MALG with non-stationarity detection, we introduce our
final black-box reduction MASTER (Section 3.2).

###  3.1 MALG: Running the Base Algorithm with Multiple Scales

We always run MALG for an interval of length $2^{n}$, which we call a _block_
, for some integer $n$ (unless it is terminated by the non-stationarity
detection mechanism). During initialization, MALG uses Procedure 1 to schedule
multiple instances of ALG within the block in the following way: for every
$m=n,n-1,\ldots,0$, partition the block equally into $2^{n-m}$ sub-intervals
of length $2^{m}$, and for each of these sub-intervals, with probability
$\frac{\rho(2^{n})}{\rho(2^{m})}\leq 1$ schedule an instance of ALG (otherwise
skip this sub-interval). We call these instances of length $2^{m}$ _order-
$m$_ instances.

Note that by definition there is always an order-$n$ instance covering the
entire block. We use alg to denote a particular instance of ALG, and use
$\textit{alg}.s$ and $\textit{alg}.e$ to denote its start and end time.

After the initialization, MALG starts interacting with the environment as
follows. In each time $t$, the unique instance covering this time step with
the shortest length is considered as being _active_ , while all others are
_inactive_. MALG follows the decision of the active instance, and update it
after receiving feedback from the environment. All inactive instances do not
make any decisions or updates, that is, they are paused (they might be resumed
at some point though). We use $\widetilde{g}_{t}$ to denote the scalar
$\widetilde{f}_{t}$ output by the active instance. See Algorithm 2 for the
pseudocode.

1 input: $n$, $\rho(\cdot)$

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

3 for  _$m=n,n-1,\ldots,0$_ do

4 If $\tau$ is a multiple of $2^{m}$, with probability
$\frac{\rho(2^{n})}{\rho(2^{m})}$, schedule a new instance alg of ALG

5 that starts at $\textit{alg}.s=\tau+1$ and ends at
$\textit{alg}.e=\tau+2^{m}$.

6

Procedure 1 A procedure that randomly schedules ALG of different lengths
within $2^{n}$ rounds

1 input: $n$, $\rho(\cdot)$

2 Initialization: run Procedure 1 with inputs $n$ and $\rho(\cdot)$.

At each time $t$, let the unique active instance be alg, output
$\widetilde{g}_{t}$ (which is the $\widetilde{f}_{t}$ output by alg), follow
alg’s decision $\pi_{t}$, and update alg after receiving feedback from the
environment.

Algorithm 2 MALG (Multi-scale ALG) Figure 2: An illustration of MALG with
$n=4$ (see detailed explanation in Section 3.1)

For better illustration, we give an example with $n=4$ in Figure 2. Suppose
that the realization of the random scheduling by Procedure 1 is: one order-$4$
instance (red), zero order-$3$ instance, two order-$2$ instances (green), two
order-$1$ instances (blue), and five order-$0$ instances (purple). The bolder
part of the segment indicates the period of time when the instances are
active, while the thinner part indicates the inactive period. For example, the
red order-$4$ instance is active for the first round, then paused for the next
$8$ rounds, and then resumed (from the frozen internal states) for another $3$
rounds before becoming inactive again. The dashed black arrow marked with 1
indicates that ALG is executed as if the two sides of the arrow are
concatenated. On the other hand, as another example, the two purple 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. One can see that at any point of time, the active
instance is always the one with the shortest length.

#### Regret analysis of MALG

The multi-scale nature of MALG allows the learner’s regret to also enjoy a
multi-scale structure, as shown in the next lemma (proof deferred to Appendix
B).

######  Lemma 3.

Let $\widehat{n}=\log_{2}T+1$ and
$\widehat{\rho}(t)=6\widehat{n}\log(T/\delta)\rho(t)$. MALG with input
$n\leq\log_{2}T$ guarantees the following: for any instance alg that MALG
maintains and any $t\in[\textit{alg}.s,\textit{alg}.e]$, as long as
$\Delta_{[\textit{alg}.s,t]}\leq\rho(t^{\prime})$ where
$t^{\prime}=t-\textit{alg}.s+1$, we have with probability at least
$1-\frac{\delta}{T}$:

$\displaystyle\widetilde{g}_{t}\geq\min_{\tau\in[\textit{alg}.s,t]}f_{\tau}^{\star}-\Delta_{[\textit{alg}.s,t]},\qquad\frac{1}{t^{\prime}}\sum_{\tau=\textit{alg}.s}^{t}\left(\widetilde{g}_{\tau}-R_{\tau}\right)\leq\widehat{\rho}(t^{\prime})+\widehat{n}\Delta_{[\textit{alg}.s,t]},$
(3)

and the number of instances started within $[\textit{alg}.s,t]$ is upper
bounded by $6\widehat{n}\log(T/\delta)\frac{C(t^{\prime})}{C(1)}$.

Note that Eq. (3) is essentially the analogue of Eq. (1) (up to logarithmic
terms) with the starting time changed from $1$ to $\textit{alg}.s$. It shows
that even if we have multiple instances interleaving in a complicated way, the
regret for a specific interval is still almost the same as running ALG alone
on this interval, thanks to the carefully chosen probability in Procedure 1.
Recall that there is always an order-$n$ instance starting from the beginning
of the block, so MALG is always providing a stronger multi-scale guarantee
compared to running ALG alone. This richer guarantee facilitates non-
stationarity detection as we show next.

###  3.2 MASTER: Equipping MALG with Stationarity Tests

We are now ready to present our final algorithm MASTER, short for MALG with
Stationarity TEsts and Restarts (see Algorithm 3). MASTER runs MALG in a
sequence of blocks with doubling lengths ($2^{0},2^{1},\ldots$). Within each
block of length $2^{n}$ (with $t_{n}$ being the starting time), MASTER simply
runs a new instance of MALG and records the minimum optimistic predictor thus
far for this block $U_{t}=\min_{\tau\in[t_{n},t]}\widetilde{g}_{\tau}$. At the
end of each time, MASTER performs two tests (Test 1 and Test 2), and if either
of them returns fail, MASTER restarts from scratch.

The two tests exactly follow the ideas described in Section 2.3 (recall Figure
1). Following Eq. (2), we decompose the regret on $[t_{n},t]$ as
$\textbf{term}_{1}+\textbf{term}_{2}$ where
$\textbf{term}_{1}=\sum_{\tau=t_{n}}^{t}\left(f_{\tau}^{\star}-\widetilde{g}_{\tau}\right)$
and
$\textbf{term}_{2}=\sum_{\tau=t_{n}}^{t}\left(\widetilde{g}_{\tau}-R_{\tau}\right)$.
Test 1 prevents
$\textbf{term}_{1}\leq\sum_{\tau=t_{n}}^{t}\left(f_{\tau}^{\star}-U_{\tau}\right)$
from growing too large by testing if there is some order-$m$ instance’s
interval during which the learner’s average performance
$\frac{1}{2^{m}}\sum_{\tau=\textit{alg}.s}^{\textit{alg}.e}R_{\tau}$ is larger
than the promised performance upper bound $U_{t}$ by an amount of
$9\widehat{\rho}(2^{m})$. On the other hand, Test 2 presents
$\textbf{term}_{2}$ from growing too large by directly testing if its average
is large than something close to the promised regret bound
$3\widehat{\rho}(t-t_{n}+1)$.

1 input: $\widehat{\rho}(\cdot)$ (defined in Lemma 3)

2 Initialize: $t\leftarrow 1$

3 for  _$n=0,1,\ldots$_ do

4 Set $t_{n}\leftarrow t$ and initialize an MALG (Algorithm 2) for the block
$[t_{n},t_{n}+2^{n}-1]$.

5 while  _$t <t_{n}+2^{n}$_ do

6 Receive $\widetilde{g}_{t}$ and $\pi_{t}$ from MALG, execute $\pi_{t}$, and
receive reward $R_{t}$.

7 Update MALG with any feedback from the environment, and set
$U_{t}=\min_{\tau\in[t_{n},t]}\widetilde{g}_{\tau}$.

8 Perform Test 1 and Test 2 (see below). Increment $t\leftarrow t+1$.

9 if  _either test returns fail_ then restart from Line 3.

10

11

Test 1: If $t=\textit{alg}.e$ for some order-$m$ alg and
$\frac{1}{2^{m}}\sum_{\tau=\textit{alg}.s}^{\textit{alg}.e}R_{\tau}\geq
U_{t}+9\widehat{\rho}(2^{m})$, return fail.

Test 2: If
$\frac{1}{t-t_{n}+1}\sum_{\tau=t_{n}}^{t}\left(\widetilde{g}_{\tau}-R_{\tau}\right)\geq
3\widehat{\rho}(t-t_{n}+1)$, return fail.

Algorithm 3 MALG with Stationarity TEsts and Restarts (MASTER)

It is now clear that MASTER indeed does not require the knowledge of $L$ or
$\Delta$ at all. To analyze MASTER, we prove the following key lemma that
bounds the regret on a single block $[t_{n},E_{n}]$ where $E_{n}$ is either
$t_{n}+2^{n}-1$ or something smaller in the case where a restart is triggered.

######  Lemma 4.

With high probability, the dynamic regret of MASTER on any block
$\mathcal{J}=[t_{n},E_{n}]$ where $E_{n}\leq t_{n}+2^{n}-1$ is bounded as

$\displaystyle\sum_{\tau\in\mathcal{J}}\left(f_{\tau}^{\star}-R_{\tau}\right)\leq\widetilde{\mathcal{O}}\left(\sum_{i=1}^{\ell}C(|\mathcal{I}_{i}^{\prime}|)+\sum_{m=0}^{n}\frac{\rho(2^{m})}{\rho(2^{n})}C(2^{m})\right).$
(4)

where $\\{\mathcal{I}_{1}^{\prime},\ldots,\mathcal{I}_{\ell}^{\prime}\\}$ is
any partition of $\mathcal{J}$ such that
$\Delta_{\mathcal{I}_{i}^{\prime}}\leq\rho(|\mathcal{I}_{i}^{\prime}|)$ for
all $i$.

See Appendix C for the proof. When $\rho(t)=\Theta(1/\sqrt{t})$ (as in all our
examples), the first term is
$\widetilde{\mathcal{O}}(\sum_{i=1}^{\ell}\sqrt{|\mathcal{I}_{i}^{\prime}|})=\widetilde{\mathcal{O}}(\sqrt{\ell|\mathcal{J}|})$
by Cauchy-Schwarz; the second term is of order
$\widetilde{\mathcal{O}}(\sqrt{2^{n}})$. To derive a bound in terms of $L$, we
can simply choose the partition
$\\{\mathcal{I}_{1}^{\prime},\ldots,\mathcal{I}_{\ell}^{\prime}\\}$ in a way
such that $\Delta_{\mathcal{I}_{i}^{\prime}}=0$ and $\ell=L_{\mathcal{J}}$,
while to derive a bound in terms of $\Delta$, the partition needs to be chosen
more carefully depending on the value of $\Delta_{\mathcal{J}}$. Noting that
the number of blocks between two restarts is always at most $\log_{2}T$, to
finally prove Theorem 2, it remains to bound the number of restarts, which
intuitively should scale with $L$ or $\Delta$ because by design a restart will
not be triggered when the environment is stationary. The complete proof is
deferred to Appendix D–Appendix F.

##  4 Extension to Reinforcement Learning in Infinite-horizon Communicating
MDPs

As mentioned, applying our results to infinite-horizon RL (Jaksch et al.,
2010) requires some extra care and extensions. We refer the reader to (Cheung
et al., 2020) for a thorough introduction on the problem setup of infinite-
horizon RL in time-varying communicating MDPs. Here, we only highlight its
difference compared to episode RL and explain how to fit it into our
framework. Specifically, in episodic RL, we have treated each episode
(consisting of multiple steps in an MDP) as one round of our framework, each
state-to-action mapping as a policy $\pi$, and the expected reward of
executing $\pi$ in the MDP for round $t$ as $f_{t}(\pi)$. In infinite-horizon
RL, while the meaning of $\pi$ and $f_{t}$ remains the same, there is no
episode any more and the learner interacts with the changing MDP from the
start to the end without any reset on her state. In this case, we treat each
step (that is, each state transition) in the MDP as one round in our
framework, and the meaning of the reward feedback $R_{t}$ has now changed from
a noisy observation of the policy’s reward $f_{t}(\pi_{t})$ to just the reward
of $\pi_{t}$ for this single step. With this change, the dynamic regret
definition remains the same.

Due to the black-box nature of our approach, if one has a base algorithm that
satisfies something close to Assumption 1 within this setup, then it is not
hard to imagine that the same idea of MASTER can be applied. In Section 4.1,
we provide such a base algorithm, and in Section 4.2, we combine it with
appropriate multi-scale scheduling and detection to obtain our final results.

###  4.1 UCRL with Adaptive Confidence Widening

Our base algorithm, UCRL-ACW, is an improvement of the standard UCRL algorithm
(Jaksch et al., 2010) and its variant UCRL-CW (Cheung et al., 2020). The
pseudocode is shown in Algorithm 4 (Appendix A), where we highlight the
differences compared to UCRL and UCRL-CW in blue.

The first difference is the explicit mention that the next state of the
learner might sometime be arbitrarily assigned instead of following the
transition of the current MDP (Line 4). This is necessary because of the
multi-scale scheduling of MALG. Indeed, recall that in MALG, an instance of
the base algorithm can sometimes be paused and then resumed later. In the
infinite-horizon RL setup, this means that the instance can be resumed from an
arbitrary state. Other than making this detail explicit, however, nothing
really needs to be changed in the algorithm, since this happens infrequently
and only incurs small additional regret due to the communicating property of
the MDPs.

The second key difference is an adaptive version of the Confidence Widening
technique of (Cheung et al., 2020) (see Line 4–Line 4). As pointed out in
(Cheung et al., 2020), in non-stationary environments, the Extended Value
Iteration (EVI) subroutine of UCRL might return a bias vector
($\widetilde{h}_{k}$) with span much larger than $D_{\max}$, the maximum
diameters of all the MDPs. To address this issue, their confidence widening
technique adds a constant $\eta$, tuned based on $\Delta$, to the confidence
level of the confidence set $\mathcal{P}_{k}$, which eventually leads to sub-
optimal regret $\Delta^{\nicefrac{{1}}{{4}}}T^{\nicefrac{{3}}{{4}}}$. Our
_adaptive confidence widening_ , on the other hand, adaptively selects the
value of $\eta$ in a doubling manner, so that in a relatively stationary
environment we only widen the confidence set slightly, while in a more non-
stationary environment the widening is more significant. To avoid incurring
too much additional regret in the latter case, we also monitor the cumulative
widening amount and terminate the algorithm if it exceeds a certain threshold
(Line 4–Line 4), because this implies that the environment is highly non-
stationary. (This termination will also be a restart signal for MASTER.)

Finally, notice that our black-box approach requires knowing the regret bound
$\rho(\cdot)$ of the base algorithm, which in this case depends on $D_{\max}$,
a potentially unknown quantity. To deal with this issue, UCRL-ACW takes a
guess $\overline{D}$ on the value of $D_{\max}$ as an additional input. In the
next subsection, we discuss how MASTER decides the value of $\overline{D}$
when $D_{\max}$ is unknown.

With all these modifications, our base algorithm UCRL-ACW indeed provides a
guarantee similar to Eq. (1) of Assumption 1; see Lemma 11.

###  4.2 Multi-scale UCRL-ACW and Its Combination with MASTER

Now, we use the same idea as in Section 3.1 to create a multi-scale version of
UCRL-ACW, under a fixed input $\overline{D}$. The resulted algorithm is called
Multi-scale UCRL-ACW or MUCRL for short (see Algorithm 5). MUCRL is basically
identical to MALG with UCRL-ACW as the base algorithm, except that we let
MUCRL terminate whenever the currently active UCRL-ACW instance makes a
restart signal (due to having an abnormally large cumulative widening amount).
The guarantee for MUCRL is provided in Lemma 12, which parallels Lemma 3.

Next, as in Section 3.2, we further combine MUCRL with non-stationarity tests,
leading to MASTER-UCRL (see Algorithm 6). The only difference compared to
MASTER is an additional condition to restart (highlighted in blue) — when
MUCRL terminates due to a restart signal from an UCRL-ACW instance. We provide
a single-block regret bound guarantee for MASTER-UCRL under a fixed
$\overline{D}$ in Lemma 13, which parallels Lemma 4. Finally, we discuss three
different cases with knowledge of different parameters (if any), leading to
the three results listed in Table 1.

#### Known $D_{\max}$

When $D_{\max}$ is known, we simply set $\overline{D}=D_{\max}$. In this case,
all restarts of MASTER-UCRL are due to non-stationarity, and we can bound
their number in terms of $L$ or $\Delta$. Together with the single-block
regret guarantee from Lemma 13, we prove that MASTER-UCRL’s dynamic regret is
$\widetilde{\mathcal{O}}(\min\\{\text{\rm Reg}_{L}^{\star},\text{\rm
Reg}_{\Delta}^{\star}\\})$; see Theorem 28 for the dependence on other
parameters.

#### Unknown $D_{\max}$ and Known $L$ or $\Delta$

When $D_{\max}$ is unknown, we unfortunately require the knowledge of $L$ to
get $\text{\rm Reg}_{L}^{\star}$ and the knowledge of $\Delta$ to get
$\text{\rm Reg}_{\Delta}^{\star}$. However, as shown in Table 1, this still
significantly improves over the best existing bounds
$\widetilde{\mathcal{O}}(L^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}})$ and
$\widetilde{\mathcal{O}}(\Delta^{\nicefrac{{1}}{{4}}}T^{\nicefrac{{3}}{{4}}})$
when $L$ and $\Delta$ are known. Specifically, we apply a doubling trick to
set the value of $\overline{D}$ following the strategy below, where we call
the interval between two restarts an epoch:

  1. 1.

Initialize $\overline{D}\leftarrow 1$.

  2. 2.

Run MASTER-UCRL with $\overline{D}$. If the number of epochs exceeds
$\overline{N}$, then double $\overline{D}$ and repeat this step. Here,
$\overline{N}$ is set to $L$ if $L$ is known or
$1+3(S^{-2}A^{-1}\Delta^{2}T)^{\nicefrac{{1}}{{3}}}$ if $\Delta$ is known.

The rationale behind monitoring the number of epochs is that, when
$\overline{D}$ is too small, UCRL-ACW might have an abnormally large
cumulative widening amount and signal a restart even in a fairly stationary
environment. In Lemma 26, we show that if $\overline{D}\geq D_{\max}$, the
number of epochs produced by MASTER-UCRL is upper bounded by the value of
$\overline{N}$ set above. Therefore, if it exceeds this number, we can infer
$\overline{D}<D_{\max}$ and double its value. This allows us to prove the
regret bound $\text{\rm Reg}_{L}^{\star}$ or $\text{\rm Reg}_{\Delta}^{\star}$
again; see Theorem 29 for the details.

#### No prior knowledge at all

When nothing is known, we apply the Bandit-over-Reinforcment-Learning (BoRL)
framework of (Cheung et al., 2019, 2020) to get a suboptimal bound of order
$\widetilde{\mathcal{O}}(\min\\{\text{\rm Reg}_{L}^{\star},\text{\rm
Reg}_{\Delta}^{\star}\\}+T^{\nicefrac{{3}}{{4}}})$. BoRL also serves as a
black-box reduction to obtain parameter-free algorithms (albeit suboptimal),
so applying it to our algorithm is straightforward. We omit the details and
only give the concrete bound in Appendix H. We leave the question of whether
the optimal bound is achievable when $L$, $\Delta$, and $D_{\max}$ are all
unknown as a future direction.

##  5 Conclusion and Future Directions

In this work, we study reinforcement learning in non-stationary environments.
We propose a general black-box approach that can convert an algorithm with
near-optimal regret in a (near-)stationary environment to another algorithm
with near-optimal dynamic regret in a non-stationary environment. Prior to our
work, the bound of
$\widetilde{\mathcal{O}}(\Delta^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}})$
is only achievable with the knowledge of $\Delta$, and no algorithm achieves
the bound of $\widetilde{\mathcal{O}}(\sqrt{LT})$ even with the knowledge of
$L$. Our algorithm achieves both bounds simultaneously without any prior
knowledge.

It would be interesting to see whether algorithms with data-dependent bounds
work with our black-box approach. Previous work in this direction (Wei et al.,
2016) achieves an improved dynamic regret bound for multi-armed bandits when
the cumulative variance of the loss is small; however, their approach
crucially relies on the knowledge on the degree of non-stationarity as well as
the cumulative variance. On the other hand, there are some immediate
difficulties in applying our black-box approach to data-dependent algorithms.
For example, the monotonicity of the the average regret $\rho(\cdot)$ may not
hold anymore, and it is unclear how to set the probability of initiating a new
base algorithm. Therefore, the task of achieving data-dependent dynamic bounds
without prior knowledge seems to be challenging and requires other
innovations.

Another future direction is to study a class of contextual bandit problems
where the context is adversarially generated (Abbasi-Yadkori et al., 2011;
Cheung et al., 2019; Foster and Rakhlin, 2020). In this case, the expected
reward of the optimal policy changes over time even if the environment is
stationary, so our current algorithm cannot be directly applied. For linear
contextual bandits with adversarial contexts (Abbasi-Yadkori et al., 2011;
Cheung et al., 2019), the fix is straightforward though: instead of requiring
the base algorithm to generate a scalar $\widetilde{f}_{t}$ in each round, we
let it generate a _confidence set_ for the hidden parameter, and check the
inconsistency of the confidence set over time. However, for general contextual
bandits with adversarial contexts, where algorithms do not necessarily
maintain a confident set for the hidden parameter (Foster and Rakhlin, 2020),
the extension is less clear and is left for future investigation.

Finally, we are not aware of any near-optimal _convex bandit_ algorithm
satisfying our Assumption 1, so achieving near-optimal dynamic regret bound in
general convex bandits is also left open.

#### Acknowledgments

We thank Peng Zhao for pointing out the technical flaw made in previous works
on non-stationary linear bandits as well as a fix in (Zhao and Zhang, 2021),
and thank Ruihao Zhu for informing us their non-stationary linear bandit
algorithm with the $\text{\rm Reg}_{\Delta}^{\star}$ bound (Cheung et al.,
2018). We also thank anonymous reviewers for pointing out the relation between
our algorithm and regret balancing (Abbasi-Yadkori et al., 2020; Pacchiano et
al., 2020). This work is supported by NSF Award IIS-1943607 and a Google
Faculty Research Award.

## References

  * Abbasi-Yadkori et al. [2011] Yasin Abbasi-Yadkori, Dávid Pál, and Csaba Szepesvári.  Improved algorithms for linear stochastic bandits.  _Advances in neural information processing systems_ , 24:2312–2320, 2011.
  * Abbasi-Yadkori et al. [2020] Yasin Abbasi-Yadkori, Aldo Pacchiano, and My Phan.  Regret balancing for bandit and rl model selection.  _arXiv preprint arXiv:2006.05491_ , 2020.
  * Agarwal et al. [2014] Alekh Agarwal, Daniel Hsu, Satyen Kale, John Langford, Lihong Li, and Robert Schapire.  Taming the monster: A fast and simple algorithm for contextual bandits.  In _International Conference on Machine Learning_ , pages 1638–1646, 2014.
  * Arora et al. [2012] Raman Arora, Ofer Dekel, and Ambuj Tewari.  Deterministic mdps with adversarial rewards and bandit feedback.  In _Proceedings of the Twenty-Eighth Conference on Uncertainty in Artificial Intelligence_ , pages 93–101, 2012.
  * Auer et al. [2002a] Peter Auer, Nicolo Cesa-Bianchi, and Paul Fischer.  Finite-time analysis of the multiarmed bandit problem.  _Machine learning_ , 47(2-3):235–256, 2002a.
  * Auer et al. [2002b] Peter Auer, Nicolo Cesa-Bianchi, Yoav Freund, and Robert E Schapire.  The nonstochastic multiarmed bandit problem.  _SIAM journal on computing_ , 32(1):48–77, 2002b.
  * Auer et al. [2019] Peter Auer, Pratik Gajane, and Ronald Ortner.  Adaptively tracking the best bandit arm with an unknown number of distribution changes.  In _Conference on Learning Theory_ , pages 138–158, 2019.
  * Cai et al. [2020] Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang.  Provably efficient exploration in policy optimization.  In _International Conference on Machine Learning_ , pages 1283–1294. PMLR, 2020.
  * Chen et al. [2021] Liyu Chen, Haipeng Luo, and Chen-Yu Wei.  Minimax regret for stochastic shortest path with adversarial costs and known transition.  In _Conference on Learning Theory_ , 2021.
  * Chen et al. [2020] Wei Chen, Liwei Wang, Haoyu Zhao, and Kai Zheng.  Combinatorial semi-bandit in the non-stationary environment.  _arXiv preprint arXiv:2002.03580_ , 2020.
  * Chen et al. [2019] Yifang Chen, Chung-Wei Lee, Haipeng Luo, and Chen-Yu Wei.  A new algorithm for non-stationary contextual bandits: Efficient, optimal and parameter-free.  In _Conference on Learning Theory_ , pages 696–726, 2019.
  * Cheung et al. [2018] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu.  Hedging the drift: Learning to optimize under non-stationarity.  _Available at SSRN 3261050_ , 2018.
  * Cheung et al. [2019] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu.  Learning to optimize under non-stationarity.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pages 1079–1087. PMLR, 2019.
  * Cheung et al. [2020] Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu.  Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism.  In _International Conference on Machine Learning_ , pages 1843–1854. PMLR, 2020.
  * Daniely et al. [2015] Amit Daniely, Alon Gonen, and Shai Shalev-Shwartz.  Strongly adaptive online learning.  In _International Conference on Machine Learning_ , pages 1405–1411, 2015.
  * Dekel and Hazan [2013] Ofer Dekel and Elad Hazan.  Better rates for any adversarial deterministic mdp.  In _International Conference on Machine Learning_ , pages 675–683, 2013.
  * Dick et al. [2014] Travis Dick, Andras Gyorgy, and Csaba Szepesvari.  Online learning in markov decision processes with changing cost sequences.  In _International Conference on Machine Learning_ , pages 512–520, 2014.
  * Domingues et al. [2021] Omar Darwiche Domingues, Pierre Ménard, Matteo Pirotta, Emilie Kaufmann, and Michal Valko.  A kernel-based approach to non-stationary reinforcement learning in metric spaces.  In _International Conference on Artificial Intelligence and Statistics_ , pages 3538–3546. PMLR, 2021.
  * Even-Dar et al. [2009] Eyal Even-Dar, Sham M Kakade, and Yishay Mansour.  Online markov decision processes.  _Mathematics of Operations Research_ , 34(3):726–736, 2009.
  * Faury et al. [2021] Louis Faury, Yoan Russac, Marc Abeille, and Clément Calauzènes.  Regret bounds for generalized linear bandits under parameter drift.  _arXiv preprint arXiv:2103.05750_ , 2021.
  * Fei et al. [2020] Yingjie Fei, Zhuoran Yang, Zhaoran Wang, and Qiaomin Xie.  Dynamic regret of policy optimization in non-stationary environments.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Filippi et al. [2010] Sarah Filippi, Olivier Cappé, Aurélien Garivier, and Csaba Szepesvári.  Parametric bandits: the generalized linear case.  In _Proceedings of the 23rd International Conference on Neural Information Processing Systems-Volume 1_ , pages 586–594, 2010.
  * Foster and Rakhlin [2020] Dylan Foster and Alexander Rakhlin.  Beyond ucb: Optimal and efficient contextual bandits with regression oracles.  In _International Conference on Machine Learning_ , pages 3199–3210. PMLR, 2020.
  * Gajane et al. [2018] Pratik Gajane, Ronald Ortner, and Peter Auer.  A sliding-window algorithm for markov decision processes with arbitrarily changing rewards and transitions.  _arXiv preprint arXiv:1805.10066_ , 2018.
  * Hazan and Seshadhri [2007] Elad Hazan and Comandur Seshadhri.  Adaptive algorithms for online decision problems.  In _Electronic colloquium on computational complexity (ECCC)_ , volume 14, 2007.
  * Jaksch et al. [2010] Thomas Jaksch, Ronald Ortner, and Peter Auer.  Near-optimal regret bounds for reinforcement learning.  _Journal of Machine Learning Research_ , 11(4), 2010.
  * Jin et al. [2018] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan.  Is q-learning provably efficient?  In _Advances in neural information processing systems_ , pages 4863–4873, 2018.
  * Jin et al. [2020a] Chi Jin, Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu.  Learning adversarial markov decision processes with bandit feedback and unknown transition.  In _International Conference on Machine Learning_ , pages 4860–4869. PMLR, 2020a.
  * Jin et al. [2020b] Chi Jin, Zhuoran Yang, Zhaoran Wang, and Michael I Jordan.  Provably efficient reinforcement learning with linear function approximation.  In _Conference on Learning Theory_ , pages 2137–2143. PMLR, 2020b.
  * Jin and Luo [2020] Tiancheng Jin and Haipeng Luo.  Simultaneously learning stochastic and adversarial episodic mdps with known transition.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Jun et al. [2017] Kwang-Sung Jun, Francesco Orabona, Stephen Wright, and Rebecca Willett.  Improved strongly adaptive online learning using coin betting.  In _Artificial Intelligence and Statistics_ , pages 943–951, 2017\.
  * Kim and Tewari [2020] Baekjin Kim and Ambuj Tewari.  Randomized exploration for non-stationary stochastic linear bandits.  In _Uncertainty in Artificial Intelligence_ , 2020.
  * Lai and Robbins [1985] Tze Leung Lai and Herbert Robbins.  Asymptotically efficient adaptive allocation rules.  _Advances in applied mathematics_ , 6(1):4–22, 1985.
  * Lancewicki et al. [2020] Tal Lancewicki, Aviv Rosenberg, and Yishay Mansour.  Learning adversarial markov decision processes with delayed feedback.  _arXiv preprint arXiv:2012.14843_ , 2020.
  * Lee et al. [2020] Chung-Wei Lee, Haipeng Luo, Chen-Yu Wei, and Mengxiao Zhang.  Bias no more: high-probability data-dependent regret bounds for adversarial bandits and mdps.  _Advances in Neural Information Processing Systems_ , 33, 2020.
  * Li and Li [2019] Yingying Li and Na Li.  Online learning for markov decision processes in nonstationary environments: A dynamic regret analysis.  In _2019 American Control Conference (ACC)_ , pages 1232–1237. IEEE, 2019.
  * Luo and Schapire [2015] Haipeng Luo and Robert E Schapire.  Achieving all with no parameters: Adanormalhedge.  In _Conference on Learning Theory_ , pages 1286–1304, 2015.
  * Luo et al. [2018] Haipeng Luo, Chen-Yu Wei, Alekh Agarwal, and John Langford.  Efficient contextual bandits in non-stationary worlds.  In _Conference On Learning Theory_ , pages 1739–1776. PMLR, 2018\.
  * Lykouris et al. [2021] Thodoris Lykouris, Max Simchowitz, Aleksandrs Slivkins, and Wen Sun.  Corruption robust exploration in episodic reinforcement learning.  In _Conference on Learning Theory_ , 2021.
  * Mao et al. [2021] Weichao Mao, Kaiqing Zhang, Ruihao Zhu, David Simchi-Levi, and Tamer Başar.  Is model-free learning nearly optimal for non-stationary rl?  In _International Conference on Machine Learning_ , 2021.
  * Neu et al. [2010] Gergely Neu, András György, and Csaba Szepesvári.  The online loop-free stochastic shortest-path problem.  In _COLT_ , volume 2010, pages 231–243. Citeseer, 2010.
  * Neu et al. [2012] Gergely Neu, Andras Gyorgy, and Csaba Szepesvári.  The adversarial stochastic shortest path problem with unknown transition probabilities.  In _Artificial Intelligence and Statistics_ , pages 805–813, 2012\.
  * Neu et al. [2013] Gergely Neu, András György, Csaba Szepesvári, and András Antos.  Online markov decision processes under bandit feedback.  _IEEE Transactions on Automatic Control_ , 59(3):676–691, 2013.
  * Ortner et al. [2020] Ronald Ortner, Pratik Gajane, and Peter Auer.  Variational regret bounds for reinforcement learning.  In _Uncertainty in Artificial Intelligence_ , pages 81–90. PMLR, 2020\.
  * Pacchiano et al. [2020] Aldo Pacchiano, Christoph Dann, Claudio Gentile, and Peter Bartlett.  Regret bound balancing and elimination for model selection in bandits and rl.  _arXiv preprint arXiv:2012.13045_ , 2020.
  * Rosenberg and Mansour [2019] Aviv Rosenberg and Yishay Mansour.  Online convex optimization in adversarial markov decision processes.  In _International Conference on Machine Learning_ , pages 5478–5486, 2019.
  * Rosenberg and Mansour [2020] Aviv Rosenberg and Yishay Mansour.  Stochastic shortest path with adversarially changing costs.  _arXiv preprint arXiv:2006.11561_ , 2020.
  * Russac et al. [2019] Yoan Russac, Claire Vernade, and Olivier Cappé.  Weighted linear bandits for non-stationary environments.  _Advances in Neural Information Processing Systems_ , 2019.
  * Russac et al. [2020] Yoan Russac, Olivier Cappé, and Aurélien Garivier.  Algorithms for non-stationary generalized linear bandits.  _arXiv preprint arXiv:2003.10113_ , 2020.
  * Shani et al. [2020] Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor.  Optimistic policy optimization with bandit feedback.  In _International Conference on Machine Learning_ , pages 8604–8613. PMLR, 2020.
  * Simchi-Levi and Xu [2020] David Simchi-Levi and Yunzong Xu.  Bypassing the monster: A faster and simpler optimal algorithm for contextual bandits under realizability.  _Available at SSRN_ , 2020.
  * Touati and Vincent [2020] Ahmed Touati and Pascal Vincent.  Efficient learning in non-stationary linear markov decision processes.  _arXiv preprint arXiv:2010.12870_ , 2020.
  * Wang et al. [2020] Ruosong Wang, Simon S Du, Lin F Yang, and Sham M Kakade.  Is long horizon reinforcement learning more difficult than short horizon reinforcement learning?  _Advances in Neural Information Processing Systems_ , 2020.
  * Wei et al. [2016] Chen-Yu Wei, Yi-Te Hong, and Chi-Jen Lu.  Tracking the best expert in non-stationary stochastic environments.  _Advances in neural information processing systems_ , 29:3972–3980, 2016.
  * Zhao and Zhang [2021] Peng Zhao and Lijun Zhang.  Non-stationary linear bandits revisited.  _arXiv preprint arXiv:2103.05324_ , 2021.
  * Zhao et al. [2020] Peng Zhao, Lijun Zhang, Yuan Jiang, and Zhi-Hua Zhou.  A simple approach for non-stationary linear bandits.  In Silvia Chiappa and Roberto Calandra, editors, _Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics_ , volume 108 of _Proceedings of Machine Learning Research_ , pages 746–755. PMLR, 26–28 Aug 2020.
  * Zhou et al. [2020] Huozhi Zhou, Jinglin Chen, Lav R Varshney, and Ashish Jagmohan.  Nonstationary reinforcement learning with linear function approximation.  _arXiv preprint arXiv:2010.04244_ , 2020.
  * Zimin and Neu [2013] Alexander Zimin and Gergely Neu.  Online learning in episodic markovian decision processes by relative entropy policy search.  _Advances in neural information processing systems_ , 26:1583–1591, 2013.

##  Appendix A Omitted Algorithms and Main Results in Section 4

1 input: $\overline{D}\geq 1$

2 $t\leftarrow 1$. $N_{1}(s,a)\leftarrow 0$ for all $s,a$. $\Gamma\leftarrow
0$

3 for  _episode $k=1,\ldots,$_ do

4 Set $t_{k}=t$, $\nu_{k}(s,a)=0$ for all $s,a$.

5 Define for all $s,a$:  $\displaystyle\widehat{p}_{k}(s^{\prime}|s,a)$
$\displaystyle=\frac{\sum_{\tau=1}^{t-1}\mathbbm{1}[(s_{\tau},a_{\tau},s_{\tau+1}^{\prime})=(s,a,s^{\prime})]}{N_{k}^{+}(s,a)},$
$\displaystyle\widehat{r}_{k}(s,a)$
$\displaystyle=\frac{\sum_{\tau=1}^{t-1}R_{\tau}\mathbbm{1}[(s_{\tau},a_{\tau})=(s,a)]}{N_{k}^{+}(s,a)}.$

6 and for any $\eta$:  $\displaystyle\mathcal{P}_{k}^{\eta}(s,a)$
$\displaystyle=\left\\{\widetilde{p}(\cdot|s,a)\in\Delta_{S}:\|\widetilde{p}(\cdot|s,a)-\widehat{p}_{k}(\cdot|s,a)\|_{1}\leq\sqrt{S}\cdot\textit{conf}_{k}(s,a)+\eta\right\\}$
$\displaystyle\mathcal{R}_{k}(s,a)$
$\displaystyle=\left\\{\widetilde{r}(s,a)\in[0,1]:|\widetilde{r}(s,a)-\widehat{r}_{k}(s,a)|\leq\textit{conf}_{k}(s,a)\right\\}$
where $\textit{conf}_{k}(s,a)\triangleq
8\sqrt{\frac{\log(SAT/\delta)}{N_{k}^{+}(s,a)}}$ and
$N_{k}^{+}(s,a)=\max\\{1,N_{k}(s,a)\\}$.

7

8 $\eta\leftarrow\frac{1}{T}$

9 while  _true_ do

10 Perform EVI on $(\mathcal{P}_{k}^{\eta},\mathcal{R}_{k})$ with error
parameter $\epsilon_{k}=\sqrt{\frac{1}{t}}$, and obtain $\widetilde{\pi}$,
$\widetilde{h}$, $\widetilde{J}$.

11 if  _$\text{sp}(\widetilde{h})\leq 2\overline{D}$_ then break

12 $\eta\leftarrow 2\eta$

13 $\pi_{k}\leftarrow\widetilde{\pi},\ \
\widetilde{h}_{k}\leftarrow\widetilde{h},\ \
\widetilde{J}_{k}\leftarrow\widetilde{J},\ \ \eta_{k}\leftarrow\eta$

$\triangleleft$ Adaptive confidence widening

14

15 while  _$\nu_{k}(s,a) <N_{k}^{+}(s,a)$ for all $s,a$_ do

16 Choose action $a_{t}\sim\pi_{k}(s_{t})$.

17 $\nu_{k}(s_{t},a_{t})\leftarrow\nu_{k}(s_{t},a_{t})+1$

18 $\Gamma\leftarrow\Gamma+\eta_{k}$

19 if  _$\Gamma >4S\sqrt{At\log(SAT/\delta)}$_ then terminate and signal
restart

$\triangleleft$ Early termination

20 Observe the reward $R_{t}$ with $\mathbb{E}[R_{t}]=r_{t}(s_{t},a_{t})$

21 Observe $s_{t+1}^{\prime}\sim p_{t}(\cdot|s_{t},a_{t})$.

22 The next state $s_{t+1}$ is either equal to $s_{t+1}^{\prime}$, or re-
assigned as an arbitrary state

23

$\triangleleft$ The next state might be re-assigned

24 $t\leftarrow t+1$

25 $N_{k+1}(s,a)\leftarrow N_{k}(s,a)+\nu_{k}(s,a)$ for all $s,a$.

Algorithm 4 UCRL with Adaptive Confidence Widening (UCRL-ACW)

1 input: $n$, $\rho_{{\small\textsf{{UCRL}}}}(\cdot~{};\overline{D})$,
$\overline{D}$

2 Initialization: run Procedure 1 with base algorithm UCRL-ACW and inputs $n$
and $\rho_{{\small\textsf{{UCRL}}}}$.

3

4At each time $t$, let the unique active instance be alg, output
$\widetilde{g}_{t}$ (which is the quantity $\widetilde{J}_{k(t)}$ of alg),
follow alg’s decision, and update alg after receiving feedback from the
environment. Additionally, terminate if the alg signals restart.

Algorithm 5 Multi-scale UCRL-ACW (MUCRL)

1 input: $\rho_{{\small\textsf{{UCRL}}}}(\cdot~{};\overline{D})$,
$\overline{D}$

2 Initialize: $t\leftarrow 1$

3 for  _$n=0,1,\ldots$_ do

4 Set $t_{n}\leftarrow t$ and initialize an MUCRL (Algorithm 5) for the block
$[t_{n},t_{n}+2^{n}-1]$.

5 while  _$t <t_{n}+2^{n}$_ do

6 Receive $\widetilde{g}_{t}$ and $\pi_{t}$ from MUCRL, execute $\pi_{t}$, and
receive reward $R_{t}$.

7 Update MUCRL with any feedback from the environment, and set
$U_{t}=\min_{\tau\in[t_{n},t]}\widetilde{g}_{\tau}$.

8 Perform Test 1 and Test 2 (see below). Increment $t\leftarrow t+1$.

9 if  _either test returns fail or MUCRL terminates _ then restart from Line
6.

10

11

12Test 1: If $t=\textit{alg}.e$ for some order-$m$ alg and
$\frac{1}{2^{m}}\sum_{\tau=\textit{alg}.s}^{\textit{alg}.e}R_{\tau}\geq
U_{t}+9\widehat{\rho}_{{\small\textsf{{UCRL}}}}(2^{m};\overline{D})$, return
fail.

13Test 2: If
$\frac{1}{t-t_{n}+1}\sum_{\tau=t_{n}}^{t}\left(\widetilde{g}_{\tau}-R_{\tau}\right)\geq
3\widehat{\rho}_{{\small\textsf{{UCRL}}}}(t-t_{n}+1;\overline{D})$, return
fail.

Algorithm 6 MASTER-UCRL

The following is the main result for the infinite-horizon MDP case. Its proof
requires several lemmas in the rest of this section, in addition to those from
Appendix B–Appendix E whose ideas are mostly aligned with the standard
setting. The final analysis is done in Appendix G and Appendix H (see Theorem
28, Theorem 29, and the discussions in Appendix H). Note that to be consistent
with prior works in this setting, we adopt the notation $J_{t}(\pi)$, which is
the expected average reward of executing $\pi$ under the MDP for time $t$, and
corresponds to the notation $f_{t}(\pi)$ we use in our general framework.
Similarly, define $J^{\star}_{t}=\max_{\pi}J_{t}(\pi)$.

######  Theorem 5.

Define non-stationarity measures

$\displaystyle\Delta$
$\displaystyle=\sum_{t=1}^{T-1}\left(\max_{s,a}|r_{t}(s,a)-r_{t+1}(s,a)|+\max_{s,a}\|p_{t}(\cdot|s,a)-p_{t+1}(\cdot|s,a)\|_{1}\right),$
$\displaystyle L$
$\displaystyle=1+\sum_{t=1}^{T-1}\mathbbm{1}\left\\{\max_{s,a}|r_{t}(s,a)-r_{t+1}(s,a)|+\max_{s,a}\|p_{t}(\cdot|s,a)-p_{t+1}(\cdot|s,a)\|_{1}\neq
0\right\\}.$

There exists an algorithm that takes $D_{\max}$ as input and achieves

$\displaystyle\sum_{t=1}^{T}\left(J^{\star}_{t}-R_{t}\right)=\widetilde{\mathcal{O}}\left(\min\left\\{D_{\max}S\sqrt{ALT},\
\
D_{\max}S^{\frac{2}{3}}A^{\frac{1}{3}}\Delta^{\frac{1}{3}}T^{\frac{2}{3}}+D_{\max}S\sqrt{AT}\right\\}\right)$

without knowing $L$ or $\Delta$. There is also an algorithm that takes $L$ or
$\Delta$ as input and achieves

$\displaystyle\sum_{t=1}^{T}\left(J^{\star}_{t}-R_{t}\right)=\widetilde{\mathcal{O}}\left(D_{\max}S\sqrt{ALT}\right)\quad\text{or}\quad\sum_{t=1}^{T}\left(J^{\star}_{t}-R_{t}\right)=\widetilde{\mathcal{O}}\left(D_{\max}S^{\frac{2}{3}}A^{\frac{1}{3}}\Delta^{\frac{1}{3}}T^{\frac{2}{3}}+D_{\max}S\sqrt{AT}\right)$

respectively, without knowing $D_{\max}$. Finally, there is an algorithm that
achieves

$\displaystyle\sum_{t=1}^{T}\left(J^{\star}_{t}-R_{t}\right)=\widetilde{\mathcal{O}}\left(D_{\max}(S^{2}A)^{\nicefrac{{1}}{{4}}}T^{\nicefrac{{3}}{{4}}}+\min\left\\{D_{\max}S\sqrt{ALT},\
\
D_{\max}(S^{2}A)^{\frac{1}{3}}\Delta^{\frac{1}{3}}T^{\frac{2}{3}}\right\\}\right)$

without knowing $L,\Delta$, or $D_{\max}$.

###  A.1 Auxiliary Lemmas related to Extended Value Iteration and Bellman
Equation

In this subsection, we provide auxiliary lemmas related to EVI and Bellman
Equation. The results are extracted from [Jaksch et al., 2010, Cheung et al.,
2020, Ortner et al., 2020]. We restate them here for completeness.

######  Lemma 6 (Properties 1 and 2 in [Cheung et al., 2020]).

Let $\widetilde{J}$, $\widetilde{h}$, and $\widetilde{\pi}$ be the set of
solution obtained from EVI with confidence set $\mathcal{R}$ and $\mathcal{P}$
for reward and transition respectively, and error parameter $\epsilon$. Then

$\displaystyle\widetilde{J}+\widetilde{h}(s)$
$\displaystyle\geq\max_{a}\left(\max_{\widetilde{r}\in\mathcal{R}(s,a)}\widetilde{r}(s,a)+\max_{\widetilde{p}\in\mathcal{P}(s,a)}\sum_{s^{\prime}}\widetilde{p}(s^{\prime}|s,a)\widetilde{h}(s^{\prime})\right),$
(5) $\displaystyle\widetilde{J}+\widetilde{h}(s)$
$\displaystyle\leq\max_{\widetilde{r}\in\mathcal{R}(s,\widetilde{\pi}(s))}\widetilde{r}(s,\widetilde{\pi}(s))+\max_{\widetilde{p}\in\mathcal{P}(s,\widetilde{\pi}(s))}\sum_{s^{\prime}}\widetilde{p}(s^{\prime}|s,\widetilde{\pi}(s))\widetilde{h}(s^{\prime})+\epsilon.$
(6)

######  Lemma 7 (Lemma 2 of [Cheung et al., 2020]).

Let $\widetilde{J}$, $\widetilde{h}$, and $\widetilde{\pi}$ be the set of
solution obtained from EVI with confidence set $\mathcal{R}$ and $\mathcal{P}$
for reward and transition respectively. If $\mathcal{P}$ and $\mathcal{R}$
contain an MDP with diameter upper bounded by $D$, then
$\text{sp}(\widetilde{h})\leq 2D$.

######  Lemma 8 (Eq. (16) of [Cheung et al., 2020]).

Let $r,p$ define the reward function and the transition kernel for a
communicating MDP, respectively. Let
$\widetilde{J}\in\mathbb{R},\widetilde{h}\in\mathbb{R}^{S}$ be bounded and
satisfy

$\displaystyle\widetilde{J}+\widetilde{h}(s)\geq
r(s,a)+\sum_{s^{\prime}}p(s^{\prime}|s,a)\widetilde{h}(s^{\prime})$

for all $s$ and $a$. Then $\widetilde{J}\geq J^{\star}$, where $J^{\star}$ is
the average reward of the optimal policy under the MDP.

###  A.2 Guarantees of the UCRL-ACW Algorithm (when running alone with an
input $\overline{D}$)

######  Definition 9.

Define $\Delta^{r}(t)\triangleq\max_{s,a}|r_{t}(s,a)-r_{t+1}(s,a)|$,
$\Delta^{p}(t)\triangleq\max_{s,a}\|p_{t}(\cdot|s,a)-p_{t+1}(\cdot|s,a)\|_{1}$,
$\Delta^{J}(t)\triangleq\max_{\pi}|J_{t}(\pi)-J_{t+1}(\pi)|$. Similar to
Definition 1, define
$\Delta_{\mathcal{I}}^{\Box}=\sum_{\tau=s}^{e-1}\Delta^{\Box}(\tau)$ for
interval $\mathcal{I}=[s,e]$, where $\Box=r,p$, or $J$. Finally, we define
$\Delta_{\mathcal{I};\overline{D}}\triangleq\Delta_{\mathcal{I}}^{r}+2\overline{D}\Delta_{\mathcal{I}}^{p}+\Delta_{\mathcal{I}}^{J}$.

######  Lemma 10 (Theorem 1 of [Ortner et al., 2020]).

$\Delta^{J}(t)\leq\Delta^{r}(t)+D_{\max}\Delta^{p}(t)$.

######  Lemma 11 (c.f. Assumption 1).

When run alone, Algorithm 4 with input $\overline{D}$ guarantees for all $t$
before it terminates:

$\displaystyle\widetilde{J}_{k(t)}$
$\displaystyle\geq\min_{\tau\in[1,t]}J^{\star}_{\tau}-\Delta_{[1,t];\overline{D}}$
$\displaystyle\frac{1}{t}\sum_{\tau=1}^{t}\left(\widetilde{J}_{k(\tau)}-R_{\tau}\right)$
$\displaystyle\leq\rho_{{\small\textsf{{UCRL}}}}\left(t;\overline{D}\right)+\frac{2}{t}\overline{D}\textit{disc}_{[1,t]}+\Delta_{[1,t];\overline{D}},$

where
$\rho_{{\small\textsf{{UCRL}}}}(t;\overline{D})=\widetilde{\Theta}\left(\min\Big{\\{}\overline{D}S\sqrt{\frac{A}{t}}+\frac{\overline{D}SA}{t},\
\ \overline{D}\Big{\\}}\right)$,
$\textit{disc}_{\mathcal{I}}\triangleq\sum_{t\in\mathcal{I}}\mathbbm{1}[s_{t}\nsim
p_{t-1}(\cdot|s_{t-1},a_{t-1})]$ is the number of state re-assignments within
$\mathcal{I}$ (Line 4 of Algorithm 4), and $k(t)$ is the index of the episode
time $t$ belongs to.

###### Proof.

Suppose that at time $t$ the algorithm has not terminated. For any episode $k$
that starts before $t$, we have

$\displaystyle\overline{r}_{k}(s,a)=\frac{\sum_{\tau=1}^{t_{k}-1}r_{\tau}(s,a)\mathbbm{1}[(s_{\tau},a_{\tau})=(s,a)]}{N_{k}^{+}(s,a)},\quad\overline{p}_{k}(s^{\prime}|s,a)=\frac{\sum_{\tau=1}^{t_{k}-1}p_{\tau}(s^{\prime}|s,a)\mathbbm{1}[(s_{\tau},a_{\tau})=(s,a)]}{N_{k}^{+}(s,a)}.$

By Azuma’s inequality, $\overline{r}_{k}(s,a)\in\mathcal{R}_{k}(s,a)$ and
$\overline{p}_{k}(\cdot|s,a)\in\mathcal{P}_{k}^{\eta_{k}}(s,a)$ with high
probability for all $k,s,a$.

To show the first part of the lemma, we lower bound the right-hand side of Eq.
(5):

$\displaystyle\widetilde{J}_{k}+\widetilde{h}_{k}(s)$
$\displaystyle\geq\overline{r}(s,a)+\sum_{s^{\prime}}\overline{p}(s^{\prime}|s,a)\widetilde{h}_{k}(s^{\prime})$
$\displaystyle\geq
r_{\tau}(s,a)+\sum_{s^{\prime}}p_{\tau}(s^{\prime}|s,a)\widetilde{h}_{k}(s^{\prime})-\left(\Delta^{r}_{[1,t]}+2\overline{D}\Delta^{p}_{[1,t]}\right),$
(for any $\tau\in[1,t]$)

where in the last inequality we use
$|\overline{r}(s,a)-r_{\tau}(s,a)|\leq\Delta_{[1,t]}^{r}$ and
$\sum_{s^{\prime}}|\overline{p}(s^{\prime}|s,a)-p_{\tau}(s^{\prime}|s,a)|\widetilde{h}_{k}(s^{\prime})\leq\|\overline{p}(\cdot|s,a)-p_{\tau}(\cdot|s,a)\|_{1}\text{sp}(\widetilde{h}_{k})\leq
2\Delta_{[1,t]}^{p}\overline{D}$. Using Lemma 8, we get

$\widetilde{J}_{k}+\Delta_{[1,t];\overline{D}}\geq\widetilde{J}_{k}+\left(\Delta^{r}_{[1,t]}+2\overline{D}\Delta^{p}_{[1,t]}\right)\geq
J_{\tau}^{\star},$

implying the first part of the lemma.

To show the second part of the lemma, starting from Eq. (6), we have with high
probability

$\displaystyle\widetilde{J}_{k}+\widetilde{h}_{k}(s)$ (7)
$\displaystyle\leq\overline{r}_{k}(s,\pi_{k}(s))+\sum_{s^{\prime}}\overline{p}_{k}(s^{\prime}|s,\pi_{k}(s))\widetilde{h}_{k}(s^{\prime})+2\overline{D}\sqrt{S}\cdot\textit{conf}_{k}(s,\pi_{k}(s))+2\overline{D}\eta_{k}+\epsilon_{k}$
($\overline{r}_{k}(s,a)\in\mathcal{R}_{k}(s,a)$ and
$\overline{p}_{k}(s,a)\in\mathcal{P}_{k}(s,a)$) $\displaystyle\leq
r_{\tau}(s,\pi_{k}(s))+\sum_{s^{\prime}}p_{\tau}(s^{\prime}|s,\pi_{k}(s))\widetilde{h}_{k}(s^{\prime})+2\overline{D}\sqrt{S}\cdot\textit{conf}_{k}(s,\pi_{k}(s))+\left(\Delta^{r}_{[1,t]}+2\overline{D}\Delta^{p}_{[1,t]}\right)+2\overline{D}\eta_{k}+\epsilon_{k}.$
(8)

Now, we apply Eq. (8) with
$(k,\tau,s)=\\{k(\tau),\tau,s_{\tau}\\}_{\tau=1}^{t}$ respectively, and sum
them up. Notice that $a_{\tau}=\pi_{k(\tau)}(s_{\tau})$. Then we get

$\displaystyle\sum_{\tau=1}^{t}\left(\widetilde{J}_{k(\tau)}-R_{\tau}\right)$
$\displaystyle\leq\sum_{\tau=1}^{t}\left(\sum_{s^{\prime}}p_{\tau}(s^{\prime}|s_{\tau},a_{\tau})\widetilde{h}_{k(\tau)}(s^{\prime})-\widetilde{h}_{k(\tau)}(s_{\tau})\right)+\sum_{\tau=1}^{t}\left(r_{\tau}(s_{\tau},a_{\tau})-R_{\tau}\right)$
$\displaystyle\quad+\sum_{\tau=1}^{t}2\overline{D}\sqrt{S}\cdot\textit{conf}_{k(\tau)}(s_{\tau},a_{\tau})+t\Delta_{[1,t];\overline{D}}+2\overline{D}\sum_{\tau=1}^{t}\eta_{k(\tau)}+\sum_{\tau=1}^{t}\epsilon_{k(\tau)}.$

We bound the terms on the right-hand side individually: for the first term,
notice that when there is no state-reassignment at time $\tau+1$,
$\mathbb{E}_{\tau}[\widetilde{h}_{k(\tau)}(s_{\tau+1})]=\sum_{s^{\prime}}p_{\tau}(s^{\prime}|s_{\tau},a_{\tau})\widetilde{h}_{k(\tau)}(s^{\prime})$.
Therefore,

$\displaystyle\sum_{\tau=1}^{t}\left(\sum_{s^{\prime}}p_{\tau}(s^{\prime}|s_{\tau},a_{\tau})\widetilde{h}_{k(\tau)}(s^{\prime})-\widetilde{h}_{k(\tau)}(s_{\tau})\right)$
$\displaystyle\leq\sum_{\tau=1}^{t}\left(\mathbb{E}_{\tau}\left[\widetilde{h}_{k(\tau)}(s_{\tau+1})\right]-\widetilde{h}_{k(\tau)}(s_{\tau})\right)+2\overline{D}\textit{disc}_{[1,t]}$
$\displaystyle\leq
2\overline{D}\sqrt{t\log(SAT)}+2\overline{D}\sum_{\tau=1}^{t}\mathbbm{1}\left[\widetilde{h}_{k(\tau)}\neq\widetilde{h}_{k(\tau+1)}\right]+2\overline{D}\textit{disc}_{[1,t]}$
(by Azuma’s inequality) $\displaystyle\leq
2\overline{D}\sqrt{t\log(SAT)}+2\overline{D}SA\log_{2}T+2\overline{D}\textit{disc}_{[1,t]},$

where in the last inequality we use the fact that the number of episodes
cannot exceed $SA\log_{2}T$. For the other terms:
$\sum_{\tau=1}^{t}\left(r_{\tau}(s_{\tau},a_{\tau})-R_{\tau}\right)\leq\widetilde{\mathcal{O}}\left(\sqrt{t}\right)$
by Azuma’s inequality;
$\sum_{\tau=1}^{t}2\overline{D}\sqrt{S}\cdot\textit{conf}_{k(\tau)}(s_{\tau},a_{\tau})=\widetilde{\mathcal{O}}\left(\overline{D}S\sqrt{At}\right)$
by the standard pigeonhole argument;
$2\overline{D}\sum_{\tau=1}^{t}\eta_{k(\tau)}=\widetilde{\mathcal{O}}\left(\overline{D}S\sqrt{At}\right)$
by the termination condition specified in Line 4;
$\sum_{\tau=1}^{t}\epsilon_{k(\tau)}$ is also upper bounded by
$\widetilde{\mathcal{O}}\left(\overline{D}S\sqrt{At}\right)$ by the way we
choose the error parameter. Combining all the above arguments, we get

$\displaystyle\sum_{\tau=1}^{t}\left(\widetilde{J}_{k(\tau)}-R_{\tau}\right)\leq\widetilde{\mathcal{O}}\left(\overline{D}S\sqrt{At}+\overline{D}SA\right)+2\overline{D}\textit{disc}_{[1,t]}+t\Delta_{[1,t];\overline{D}}$

with high probability. On the other hand,
$\sum_{\tau=1}^{t}\left(\widetilde{J}_{k(\tau)}-R_{\tau}\right)\leq\overline{D}t$
is trivially true. Combining them we get the second claim of the lemma. ∎

##  Appendix B Analysis for the Multi-scale Algorithms

###### Proof.

of Lemma 3 Below, we fix an alg and fix a
$t\in[\textit{alg}.s,\textit{alg}.e]$, and consider the case
$\Delta_{[\textit{alg}.s,t]}\leq\rho(t^{\prime})$ as specified in the lemma
statement. For the first part of the lemma, note that $\widetilde{g}_{t}$ of
MALG is defined as $\widetilde{f}_{t}^{\textit{alg}^{\prime}}$ where
$\textit{alg}^{\prime}$ is the active instance of ALG at round $t$. By
Procedure 1, $\textit{alg}^{\prime}$ can only be an instance that starts
within $[\textit{alg}.s,t]$ (i.e.,
$\textit{alg}^{\prime}.s\geq\textit{alg}.s$). Therefore, the distribution
drift undergone by $\textit{alg}^{\prime}$ up to $t$ is upper bounded by
$\Delta_{[\textit{alg}.s,t]}\leq\rho(t^{\prime})$, which is further upper
bounded by $\rho(t^{\prime\prime})$ where $t^{\prime\prime}$ is the number of
active rounds $\textit{alg}^{\prime}$ runs within $[\textit{alg}.s,t]$,
because $\rho(\cdot)$ is a decreasing function. Therefore, the conditions in
Assumption 1 is satisfied for this $\textit{alg}^{\prime}$, and thus we have

$\displaystyle\widetilde{g}_{t}=\widetilde{f}_{t}^{\textit{alg}^{\prime}}\geq\min_{\tau\leq
t:~{}\textit{alg}^{\prime}\text{\ is active at
$\tau$}}f_{\tau}^{\star}-\Delta_{[\textit{alg}^{\prime}.s,t]}\geq\min_{\tau\in[\textit{alg}.s,t]}f_{\tau}^{\star}-\Delta_{[\textit{alg}.s,t]},$

proving the first part.

Next, we prove the second part of the lemma. We use $S_{m}$ to denote the set
of order-$m$ instances which start within $[\textit{alg}.s,t]$. Note that

$\displaystyle\sum_{\tau=\textit{alg}.s}^{t}\left(\widetilde{g}_{\tau}-R_{\tau}\right)$
$\displaystyle=\sum_{\tau=\textit{alg}.s}^{t}\sum_{m=0}^{n}\sum_{\textit{alg}^{\prime}\in
S_{m}}\mathbbm{1}[\textit{alg}^{\prime}\ \text{is active at\
}\tau]\left(\widetilde{f}_{\tau}^{\textit{alg}^{\prime}}-R_{\tau}\right)$
$\displaystyle=\sum_{m=0}^{n}\underbrace{\sum_{\textit{alg}^{\prime}\in
S_{m}}\sum_{\tau=\textit{alg}.s}^{t}\mathbbm{1}[\textit{alg}^{\prime}\
\text{is active at\
}\tau]\left(\widetilde{f}_{\tau}^{\textit{alg}^{\prime}}-R_{\tau}\right)}_{(*)}.$
(9)

The first equality holds because $\widetilde{g}_{\tau}$ of MALG is defined as
the $\widetilde{f}_{\tau}$ of the active instance at round $t$.

Next, we focus on a specific $m$, and bound the $(*)$ term in Eq. (9). Let
$|S_{m}|=\ell$ and
$S_{m}=\left\\{\textit{alg}_{1}^{\prime},\ldots,\textit{alg}_{\ell}^{\prime}\right\\}$,
and let
$\mathcal{I}_{i}\triangleq[\textit{alg}_{i}^{\prime}.s,\textit{alg}_{i}^{\prime}.e]\cap[\textit{alg}.s,t]$
for $i=1,\ldots,\ell$ (i.e., $\mathcal{I}_{i}$ are the rounds within
$[\textit{alg}.s,t]$ where $\textit{alg}_{i}^{\prime}$ is scheduled). Clearly,
$|\mathcal{I}_{i}|\leq\min\\{\textit{alg}^{\prime}_{i}.e-\textit{alg}^{\prime}_{i}.s+1,t-\textit{alg}.s+1\\}=\min\left\\{2^{m},t^{\prime}\right\\}$.
By Assumption 1, we have

$\displaystyle(*)$
$\displaystyle=\sum_{i=1}^{\ell}\sum_{\tau=\textit{alg}.s}^{t}\mathbbm{1}[\textit{alg}_{i}^{\prime}\text{\
is active at
$\tau$}]\left(\widetilde{f}_{\tau}^{\textit{alg}_{i}^{\prime}}-R_{\tau}\right)$
$\displaystyle\leq\sum_{i=1}^{\ell}\left(C(|\mathcal{I}_{i}|)+|\mathcal{I}_{i}|\Delta_{\mathcal{I}_{i}}\right)$
$\displaystyle\leq\ell
C(\min\\{2^{m},t^{\prime}\\})+t^{\prime}\Delta_{[\textit{alg}.s,t]},$ (10)

where in the first inequality we use Assumption 1, and that
$\textit{alg}_{i}^{\prime}$ updates for no more than $|\mathcal{I}_{i}|$
rounds in the interval $[\textit{alg}.s,t]$ (also, the condition in Assumption
1 is satisfied because
$\Delta_{\mathcal{I}_{i}}\leq\Delta_{[\textit{alg}.s,t]}\leq\rho(t^{\prime})\leq\rho(|\mathcal{I}_{i}|)$).
In the last inequality, for the first term, we use that $C(\cdot)$ is
increasing; for the second term, we use $|\mathcal{I}_{i}|\leq t^{\prime}$,
and that
$\Delta_{\mathcal{I}_{1}}+\cdots+\Delta_{\mathcal{I}_{\ell}}\leq\Delta_{[\textit{alg}.s,t]}$
since $\mathcal{I}_{1},\ldots,\mathcal{I}_{\ell}$ are non-overlapping
intervals lying within $[\textit{alg}.s,t]$.

By Procedure 1, for every $m$, the expected number of order-$m$ ALG’s that
starts within the interval $[\textit{alg}.s,t]$ can be upper bounded as

$\displaystyle\mathbb{E}[|S_{m}|]$
$\displaystyle\leq\frac{\rho(2^{n})}{\rho(2^{m})}\left\lceil\frac{t^{\prime}}{2^{m}}\right\rceil\leq\frac{\rho(2^{n})}{\rho(2^{m})}\left(\frac{t^{\prime}}{2^{m}}+1\right)\leq\frac{\rho(2^{n})}{\rho(2^{m})}\frac{t^{\prime}}{2^{m}}+1$
(11)

By Bernstein’s inequality, with probability $1-\frac{\delta}{T}$,
$|S_{m}|\leq\mathbb{E}[|S_{m}|]+\sqrt{2\mathbb{E}[|S_{m}|]\log(T/\delta)}+\log(T/\delta)\leq
2\mathbb{E}[|S_{m}|]+2\log(T/\delta)$. Thus, continuing from Eq. (10), we have
with probability at least $1-\frac{\delta}{T}$,

$\displaystyle(*)$ $\displaystyle\leq
2\cdot\left(\frac{\rho(2^{n})}{\rho(2^{m})}\frac{t^{\prime}}{2^{m}}+1\right)C(\min\\{2^{m},t^{\prime}\\})+2\log(T/\delta)C(\min\\{2^{m},t^{\prime}\\})+t^{\prime}\Delta_{[\textit{alg}.s,t]}$
$\displaystyle\leq
2\left(\frac{C(t^{\prime})}{C(2^{m})}+2\right)\log(T/\delta)C(\min\\{2^{m},t^{\prime}\\})+t^{\prime}\Delta_{[\textit{alg}.s,t]}$
$\displaystyle\leq
6C(t^{\prime})\log(T/\delta)+t^{\prime}\Delta_{[\textit{alg}.s,t]}$
($C(\cdot)$ is an increasing function)

Finally, using this in Eq. (9), we get the second claim of the lemma: with
probability at least $1-\frac{\delta}{T}$,

$\displaystyle\sum_{\tau=\textit{alg}.s}^{t}\left(\widetilde{g}_{\tau}-R_{\tau}\right)$
$\displaystyle\leq
6(n+1)C(t^{\prime})\log(1/\delta)+t^{\prime}(n+1)\Delta_{[\textit{alg}.s,t]}.$
(13)

For the third part of the lemma, as we calculated above, with probability at
least $1-\frac{\delta}{T}$, the number of instances started within
$[\textit{alg}.s,t]$ is upper bounded by

$\displaystyle\sum_{m=0}^{n}2\cdot\left(\frac{\rho(2^{n})}{\rho(2^{m})}\frac{t^{\prime}}{2^{m}}+2\right)\log(T/\delta)\leq
2\widehat{n}\left(\frac{C(t^{\prime})}{C(1)}+2\right)\log(T/\delta)\leq
6\widehat{n}\frac{C(t^{\prime})}{C(1)}\log(T/\delta)$

where we use $\rho(2^{m})2^{m}=C(2^{m})\geq C(1)$ and
$\rho(2^{n})t^{\prime}\leq\rho(t^{\prime})t^{\prime}=C(t^{\prime})$. ∎

######  Lemma 12 (c.f. Lemma 3).

Before MUCRL terminates, for every alg and
$t\in[\textit{alg}.s,\textit{alg}.e]$, MUCRL guarantees with high probability

$\displaystyle\widetilde{g}_{t}$
$\displaystyle\geq\min_{\tau\in[\textit{alg}.s,t]}J_{\tau}^{\star}-\Delta_{[\textit{alg}.s,t];\overline{D}}$
$\displaystyle\frac{1}{t^{\prime}}\sum_{\tau=\textit{alg}.s}^{t}\left(\widetilde{g}_{\tau}-R_{\tau}\right)$
$\displaystyle\leq\widehat{\rho}_{{\small\textsf{{UCRL}}}}\left(t^{\prime};\overline{D}\right)+\widehat{n}\Delta_{[\textit{alg}.s,t];\overline{D}}$

where $t^{\prime}=t-\textit{alg}.s+1$, $\widehat{n}=\log_{2}T+1$, and
$\widehat{\rho}_{{\small\textsf{{UCRL}}}}\left(t;\overline{D}\right)=18\widehat{n}\log(T/\delta)\rho_{{\small\textsf{{UCRL}}}}(t;\overline{D})$.

###### Proof.

This proof is similar to that of Lemma 3. For the first part of the lemma, we
can simply follow the proof of the first part of Lemma 3, with
$\widetilde{f}_{t}$ replaced by $\widetilde{J}_{k(t)}$, and
$\Delta_{[\textit{alg}.s,t]}$ by $\Delta_{[\textit{alg}.s,t];\overline{D}}$.

For the second part, the analysis still tightly follows that of Lemma 3, but
we need to add the additional cost caused by state re-assignment (i.e., the
$\overline{D}\textit{disc}_{[1,t]}$ term in Lemma 11). Following the same
arguments as in proof as in Eq. (9) and Eq. (10), we get

$\displaystyle\sum_{\tau=\textit{alg}.s}^{t}\left(\widetilde{g}_{\tau}-R_{\tau}\right)$
$\displaystyle=\sum_{m=0}^{n}\sum_{\textit{alg}^{\prime}\in
S_{m}}\sum_{\tau=\textit{alg}.s}^{t}\mathbbm{1}[\textit{alg}^{\prime}\
\text{is active at\
}\tau]\left(\widetilde{f}_{\tau}^{\textit{alg}^{\prime}}-R_{\tau}\right)$
($S_{m}\triangleq$ the set of order-$m$ ALG initiated within
$[\textit{alg}.s,t]$)
$\displaystyle\leq\sum_{m=0}^{n}\sum_{i=1}^{|S_{m}|}\sum_{\tau=\textit{alg}.s}^{t}\mathbbm{1}[\textit{alg}_{m,i}^{\prime}\
\text{is active at\
}\tau]\left(\widetilde{f}_{\tau}^{\textit{alg}_{m,i}^{\prime}}-R_{\tau}\right)$
(Let
$S_{m}=\\{\textit{alg}^{\prime}_{m,1},\textit{alg}^{\prime}_{m,2},\ldots\\}$)
$\displaystyle\leq\sum_{m=0}^{n}\sum_{i=1}^{|S_{m}|}\left(C_{{\small\textsf{{UCRL}}}}(|\mathcal{I}_{m,i}|;\overline{D})+|\mathcal{I}_{m,i}|\Delta_{\mathcal{I}_{m,i};\overline{D}}+2\overline{D}\textit{disc}_{\mathcal{I}_{m,i}}^{\textit{alg}_{m,i}^{\prime}}\right)$
(by Lemma 11) (14)

where in the last expression, we denote
$\mathcal{I}_{m,i}=[\textit{alg}^{\prime}_{m,i}.s,\textit{alg}^{\prime}_{m,i}.e]\cap[\textit{alg}.s,t]$
(the time within $[\textit{alg}.s,t]$ where $\textit{alg}^{\prime}_{m,i}$ is
scheduled), and $\textit{disc}^{\textit{alg}^{\prime}}_{\mathcal{I}}$ is the
total number of times within $\mathcal{I}$ when $\textit{alg}^{\prime}$
encounters state-reassignments.

For a fixed $m$, observe that all order-$m$ instances are non-overlapping.
Also, the aggregated number of state re-assignment for all order-$m$ instances
started within $[\textit{alg}.s,t]$ is upper bounded by the total number of
new instances of order not larger than $m-1$ started within
$[\textit{alg}.s,t]$. The latter is further upper bounded by
$6\widehat{n}\log(T/\delta)\frac{C_{{\small\textsf{{UCRL}}}}(t^{\prime};\overline{D})}{C_{{\small\textsf{{UCRL}}}}(1;\overline{D})}$
according to the last claim of Lemma 3. In other words, for every $m$, with
probability $1-\frac{\delta}{T}$,

$\displaystyle\sum_{i=1}^{|S_{m}|}\textit{disc}_{\mathcal{I}_{m,i}}^{\textit{alg}_{m,i}^{\prime}}=6\widehat{n}\log(T/\delta)\frac{C_{{\small\textsf{{UCRL}}}}(t^{\prime};\overline{D})}{C_{{\small\textsf{{UCRL}}}}(1;\overline{D})}.$

Following the same calculation as in Eq. (10), Eq. (11) and Eq.
(LABEL:eq:_upper_bound_star), we also have that for every $m$, with
probability $1-\frac{\delta}{T}$,

$\displaystyle\sum_{i=1}^{|S_{m}|}\left(C_{{\small\textsf{{UCRL}}}}(|\mathcal{I}_{m,i}|;\overline{D})+|\mathcal{I}_{m,i}|\Delta_{\mathcal{I}_{m,i};\overline{D}}\right)\leq
6\widehat{n}\log(T/\delta)C_{{\small\textsf{{UCRL}}}}(t^{\prime};\overline{D})+t^{\prime}\Delta_{[\textit{alg}.s,t];\overline{D}}.$

Using the above two bounds in Eq. (14), we get

$\displaystyle\sum_{\tau=\textit{alg}.s}^{t}\left(\widetilde{g}_{\tau}-R_{\tau}\right)$
$\displaystyle=6\widehat{n}\log(T/\delta)C_{{\small\textsf{{UCRL}}}}(t^{\prime};\overline{D})+\widehat{n}t^{\prime}\Delta_{[\textit{alg}.s,t];\overline{D}}+2\overline{D}\times
6\widehat{n}\log(T/\delta)\frac{C_{{\small\textsf{{UCRL}}}}(t^{\prime};\overline{D})}{C_{{\small\textsf{{UCRL}}}}(1;\overline{D})}$
$\displaystyle=18\widehat{n}\log(T/\delta)C_{{\small\textsf{{UCRL}}}}(t^{\prime};\overline{D})+\widehat{n}t^{\prime}\Delta_{[\textit{alg}.s,t];\overline{D}}$

where we use $C_{{\small\textsf{{UCRL}}}}(1;\overline{D})\geq\overline{D}$ (by
the definition of $\rho_{{\small\textsf{{UCRL}}}}(\cdot~{},\overline{D})$ in
Lemma 11). Dividing both sides by $t^{\prime}$ finishes the proof. ∎

##  Appendix C Single-block Regret Analysis I

In this section, we focus on the regret in a block of index $n$. The analysis
applies to both the standard case (Lemma 4), and the infinite-horizon RL case
summarized in the following lemma.

######  Lemma 13 (c.f. Lemma 4).

In a block of index $n$ that starts from $t_{n}$ and ends on $E_{n}$ ($E_{n}$
could be equal to $t_{n}+2^{n}-1$, or smaller, if any stationarity test fails
or MUCRL terminates), we have

$\displaystyle\sum_{\tau=t_{n}}^{E_{n}}\left(f_{\tau}^{\star}-R_{\tau}\right)\leq\widetilde{\mathcal{O}}\left(\sum_{i=1}^{\ell}C_{{\small\textsf{{UCRL}}}}(|\mathcal{I}_{i}^{\prime}|;\overline{D})+\sum_{m=0}^{n}\frac{\rho(2^{m};\overline{D})}{\rho(2^{n};\overline{D})}C_{{\small\textsf{{UCRL}}}}(2^{m};\overline{D})\right)$

where $\mathcal{I}_{1}^{\prime},\ldots,\mathcal{I}_{\ell}^{\prime}$ are
intervals that partition $[t_{n},E_{n}]$ such that
$\Delta_{\mathcal{I}_{i}^{\prime};\overline{D}}\leq\rho_{{\small\textsf{{UCRL}}}}(|\mathcal{I}_{i}^{\prime}|;\overline{D})$
for all $i$.

Throughout this section, if infinite-horizon RL is considered,
$\rho(\cdot)\triangleq\rho_{{\small\textsf{{UCRL}}}}(\cdot~{};\overline{D})$,
$\widehat{\rho}(\cdot)\triangleq\widehat{\rho}_{{\small\textsf{{UCRL}}}}(\cdot~{};\overline{D})$,
$\Delta_{\mathcal{I}}\triangleq\Delta_{\mathcal{I};\overline{D}}=\Delta^{r}_{\mathcal{I}}+2\overline{D}\Delta^{p}_{\mathcal{I}}+\Delta^{J}_{\mathcal{I}}$
with a fixed $\overline{D}$, and $f^{\star}_{t}\triangleq J^{\star}_{t}$.

For the purpose of conducting analysis, we divide $[t_{n},t_{n}+2^{n}-1]$ into
consecutive intervals
$\mathcal{I}_{1}=[s_{1},e_{1}],\mathcal{I}_{2}=[s_{2},e_{2}],\ldots,\mathcal{I}_{K}=[s_{K},e_{K}]$
($s_{1}=t_{n}$, $e_{i}+1=s_{i+1}$, $e_{K}=t_{n}+2^{n}-1$) in a way such that
for all $i$:

$\displaystyle\Delta_{\mathcal{I}_{i}}\leq\rho(|\mathcal{I}_{i}|)$ (15)

One simple way to divide the intervals is to let $\Delta_{\mathcal{I}_{i}}=0$
in each $\mathcal{I}_{i}$. Then the number of intervals $K$ would be upper
bounded by the number of stationary intervals within $[t_{n},t_{n}+2^{n}-1]$.
Intuitively, the number of intervals can also be related to
$\Delta_{[t_{n},t_{n}+2^{n}-1]}$. We defer the calculation of the required
number of intervals to Lemma 19. For now, we only need the fact that the
partition satisfies Eq. (15). From a high level, this partition makes the
distribution in each interval close to stationary. Notice that this partition
is independent of the learner’s behavior in block $n$.

For convenience, we further define the following quantities that depend on the
learner’s behavior in block $n$:

######  Definition 14.

Define $E_{n}$ as the index of the last round in block $n$. Since the block
might terminate earlier than planned, we have $E_{n}\leq t_{n}+2^{n}-1$. Let
$\ell\in[K]$ be such that $E_{n}\in\mathcal{I}_{\ell}$ (that is, $\ell$ is the
index of the interval where block $n$ ends). Define
$e_{i}^{\prime}=\min\\{e_{i},E_{n}\\}$ and
$\mathcal{I}_{i}^{\prime}=[s_{i},e_{i}^{\prime}]$ (therefore,
$\mathcal{I}_{i}^{\prime}=\emptyset$ for $i>\ell$).

Recall the definition of $\widehat{n}$ and $\widehat{\rho}(t)$ from Lemma 3
(or Lemma 12). For simplicity, we define $\alpha_{m}\triangleq\rho(2^{m})$,
$\widehat{\alpha}_{m}\triangleq\widehat{\rho}(2^{m})$, and also
$\widehat{C}(t)\triangleq t\widehat{\rho}(t)$. Furthermore, we define the
following technical quantities.

######  Definition 15.

For every $i\in\\{1,\ldots,K\\}$, and every
$m\in\left\\{0,1,\ldots,n\right\\}$, define

$\displaystyle\tau_{i}(m)=\min\left\\{\tau\in\mathcal{I}_{i}^{\prime}:~{}f_{\tau}^{\star}-\widetilde{g}_{\tau}\geq
12\widehat{\alpha}_{m}\right\\};$

that is, $\tau_{i}(m)$ is the first time $\tau$ in
$\mathcal{I}_{i}^{\prime}=\mathcal{I}_{i}\cap[t_{n},E_{n}]$ such that
$f_{\tau}^{\star}-\widetilde{g}_{\tau}$ exceeds $12\widehat{\alpha}_{m}$. If
such $\tau$ does not exist or $\mathcal{I}_{i}^{\prime}$ is empty, we let
$\tau_{i}(m)=\infty$.

Besides, we define $\xi_{i}(m)=[e_{i}^{\prime}-\tau_{i}(m)+1]_{+}$ where
$[a]_{+}=\max\\{0,a\\}$ (which is the length of the interval
$[\tau_{i}(m),e_{i}^{\prime}]$ when $\tau_{i}(m)$ is not $\infty$).

The intuition for $\tau_{i}(m)$ and $\xi_{i}(m)$ is as follows. Suppose that
block $n$ has not ended at $\tau$. If there exists some
$\tau\in\mathcal{I}_{i}$ such that $f_{\tau}^{\star}-\widetilde{g}_{\tau}\geq
12\widehat{\alpha}_{m}$ (which first happens at $\tau_{i}(m)$), and if
$\mathcal{I}_{i}$ is long enough (i.e., $\xi_{i}(m)$ is large enough) so that
after $\tau_{i}(m)$, an order-$m$ instance of ALG can run entirely within
$\mathcal{I}_{i}$, then the learner is able to discover the fact that
$f_{\tau}^{\star}-\widetilde{g}_{\tau}$ is large, and then restart. This
coincides with our explanation in Figure 1. The derivation in this section
will formalize this intuition.

######  Lemma 16.

Let the high-probability events described in Lemma 3 (or Lemma 12) hold. Then
with high probability,

$\displaystyle\sum_{\tau=t_{n}}^{E_{n}}\left(\widetilde{g}_{\tau}-R_{\tau}\right)$
$\displaystyle\leq 4\widehat{C}(2^{n}),$
$\displaystyle\sum_{\tau=t_{n}}^{E_{n}}\left(f_{\tau}^{\star}-\widetilde{g}_{\tau}\right)$
$\displaystyle\leq
96\widehat{n}\sum_{i=1}^{\ell}\widehat{C}(|\mathcal{I}_{i}^{\prime}|)+60\sum_{m=0}^{n}\frac{\alpha_{m}}{\alpha_{n}}\widehat{C}(2^{m})\log(T/\delta)$

(notations are defined at the beginning of this section).

###### Proof.

$\sum_{\tau=t_{n}}^{E_{n}}\left(\widetilde{g}_{\tau}-R_{\tau}\right)$ is
trivially upper bounded by $3\widehat{C}(E_{n}-t_{n}+1)+1\leq
4\widehat{C}(2^{n})$ because it is guarded by Test 2. Below we focus on the
second claim.

Note that we can write for all $i=1,\ldots,K$,

$\displaystyle\sum_{\tau\in\mathcal{I}_{i}^{\prime}}\left(f_{\tau}^{\star}-\widetilde{g}_{\tau}\right)$
$\displaystyle\leq
12\sum_{\tau\in\mathcal{I}_{i}^{\prime}}\left(\mathbbm{1}\Big{[}f_{\tau}^{\star}-\widetilde{g}_{\tau}\leq
12\widehat{\alpha}_{n}\Big{]}\widehat{\alpha}_{n}+\sum_{m=1}^{n}\mathbbm{1}\Big{[}12\widehat{\alpha}_{m}<f_{\tau}^{\star}-\widetilde{g}_{\tau}\leq
12\widehat{\alpha}_{m-1}\Big{]}\widehat{\alpha}_{m-1}+\mathbbm{1}\Big{[}f_{\tau}^{\star}-\widetilde{g}_{\tau}>12\widehat{\alpha}_{0}\Big{]}1\right)$
$\displaystyle\leq
12\left(|\mathcal{I}_{i}^{\prime}|\widehat{\alpha}_{n}+\sum_{m=1}^{n}\widehat{\alpha}_{m-1}\xi_{i}(m)+\rho(1)\xi_{i}(0)\right)$
($\rho(1)\geq 1$ by Assumption 1) $\displaystyle\leq
12|\mathcal{I}_{i}^{\prime}|\widehat{\alpha}_{n}+24\sum_{m=0}^{n}\widehat{\alpha}_{m}\xi_{i}(m)$
($\widehat{\alpha}_{m}=\frac{\widehat{C}(2^{m})}{2^{m}}\leq\frac{\widehat{C}(2^{m+1})}{2^{m}}=2\widehat{\alpha}_{m+1}$)

where in the second-to-last inequality we use
$\sum_{\tau\in\mathcal{I}_{i}^{\prime}}\mathbbm{1}\big{[}f_{\tau}^{\star}-\widetilde{g}_{\tau}\geq
12\widehat{\alpha}_{m}\big{]}=\sum_{\tau\in[\tau_{i}(m),e_{i}^{\prime}]}\mathbbm{1}\big{[}f_{\tau}^{\star}-\widetilde{g}_{\tau}\geq
12\widehat{\alpha}_{m}\big{]}\leq\xi_{i}(m)$ by the definition of
$\tau_{i}(m)$.

Summing the above over intervals $i$ and notice that
$\sum_{i=1}^{\ell}|\mathcal{I}_{i}^{\prime}|\leq 2^{n}$, we get

$\displaystyle\sum_{\tau=t_{n}}^{E_{n}}\left(f_{\tau}^{\star}-\widetilde{g}_{\tau}\right)$
$\displaystyle\leq 12\cdot
2^{n}\widehat{\alpha}_{n}+24\sum_{m=0}^{n}\sum_{i=1}^{\ell}\widehat{\alpha}_{m}\xi_{i}(m)=12\widehat{C}(2^{n})+24\sum_{m=0}^{n}\sum_{i=1}^{\ell}\widehat{\alpha}_{m}\xi_{i}(m).$
(16)

Next, we upper bound $\sum_{i=1}^{\ell}\widehat{\alpha}_{m}\xi_{i}(m)$ for
each $m$.

$\displaystyle\sum_{i=1}^{\ell}\widehat{\alpha}_{m}\xi_{i}(m)$
$\displaystyle=\sum_{i=1}^{\ell}\widehat{\alpha}_{m}\min\left\\{\xi_{i}(m),4\cdot
2^{m}\right\\}+\sum_{i=1}^{\ell}\widehat{\alpha}_{m}\left[\xi_{i}(m)-4\cdot
2^{m}\right]_{+}.$ (17)

The first term on the right-hand side of Eq. (17) can be bounded as below:

$\displaystyle\sum_{i=1}^{\ell}\widehat{\alpha}_{m}\min\left\\{\xi_{i}(m),4\cdot
2^{m}\right\\}$ $\displaystyle\leq
4\sum_{i=1}^{\ell}\widehat{\rho}(2^{m})\times\min\left\\{\xi_{i}(m),2^{m}\right\\}$
$\displaystyle\leq
4\sum_{i=1}^{\ell}\widehat{\rho}(\min\\{\xi_{i}(m),2^{m}\\})\times\min\left\\{\xi_{i}(m),2^{m}\right\\}$
($\widehat{\rho}(\cdot)$ is a decreasing function)
$\displaystyle=4\sum_{i=1}^{\ell}\widehat{C}(\min\\{\xi_{i}(m),2^{m}\\})$
$\displaystyle\leq 4\sum_{i=1}^{\ell}\widehat{C}(|\mathcal{I}_{i}^{\prime}|).$
($\widehat{C}(\cdot)$ is an increasing function)

The second term on the right-hand side of Eq. (17) is bounded using Lemma 17
below. Combining them into Eq. (16) finishes the proof. ∎

######  Lemma 17.

Let the high probability events described in Lemma 3 (or Lemma 12) hold. Then
with high probability,

$\displaystyle\sum_{i=1}^{\ell}\widehat{\alpha}_{m}\left[\xi_{i}(m)-4\cdot
2^{m}\right]_{+}\leq\frac{2\alpha_{m}}{\alpha_{n}}\widehat{C}(2^{m})\log(T/\delta).$

###### Proof.

Using the fact that $[[a]_{+}-b]_{+}=[a-b]_{+}$ when $b\geq 0$, we have

$\displaystyle[\xi_{i}(m)-4\cdot
2^{m}]_{+}=\left[e_{i}^{\prime}-\tau_{i}(m)+1-4\cdot 2^{m}\right]_{+}.$ (18)

Next, we consider the following quantity: “the number of rounds in the
interval $[\tau_{i}(m),e_{i}^{\prime}-2\cdot 2^{m}B]$ which are candidate
starting points of an order-$m$ ALG”. By Procedure 1, this quantity can be
written and lower bounded as

$\displaystyle
A_{i}\triangleq\sum_{t\in\mathcal{I}_{i}}\mathbbm{1}\Big{[}t\in[\tau_{i}(m),~{}e_{i}^{\prime}-2\cdot
2^{m}],\quad(t-t_{n})\text{\ mod\
}2^{m}=0\Big{]}\geq\frac{\left[e_{i}^{\prime}-\tau_{i}(m)+1-4\cdot
2^{m}\right]_{+}}{2^{m}}$

where we use the fact in an interval of length $w$, there are at least
$\frac{w+2-2u}{u}$ points whose indices are multiples of $u$. Notice that the
right-hand side is related to what we want to upper bound in the lemma
according to Eq. (18). Thus we continue to upper bound the left-hand side
above. We define the following events:

$\displaystyle W_{t}$ $\displaystyle=\left\\{\tau_{i}(m)\leq t\leq
e_{i}-2\cdot 2^{m}\text{\ where\ }i\text{\ is such that\
}t\in\mathcal{I}_{i}\right\\},$ $\displaystyle X_{t}$
$\displaystyle=\left\\{t\leq E_{n}-2\cdot 2^{m}\right\\},$ $\displaystyle
Y_{t}$ $\displaystyle=\left\\{t\leq E_{n}\text{\ and\ }(t-t_{n})\text{\ mod\
}2^{m}=0\right\\},$ $\displaystyle Z_{t}$
$\displaystyle=\left\\{\exists\text{\ order-$m$\ }\textit{alg}\text{\ such
that\ }\textit{alg}.s=t\right\\},$ $\displaystyle V_{t}$
$\displaystyle=\left\\{\exists\tau\in[t_{n},t]\text{\ such that\ }W_{\tau}\cap
Y_{\tau}\cap Z_{\tau}\right\\}.$

Then we can write (recall the definition of $K$ in the beginning of this
section)

$\displaystyle\sum_{i=1}^{\ell}A_{i}=\sum_{i=1}^{K}A_{i}$
$\displaystyle=\sum_{t=t_{n}}^{t_{n}+2^{n}-1}\mathbbm{1}[W_{t},X_{t},Y_{t}]\leq\underbrace{\sum_{t=t_{n}}^{t_{n}+2^{n}-1}\mathbbm{1}[W_{t},Y_{t},\overline{V_{t}}]}_{\textbf{term}_{3}}+\underbrace{\sum_{t=t_{n}}^{t_{n}+2^{n}-1}\mathbbm{1}[X_{t},V_{t}]}_{\textbf{term}_{4}}$

For $\textbf{term}_{3}$, notice that conditioned on $W_{t}\cap Y_{t}$, the
event $Z_{t}$ happens with a constant probability
$\frac{\alpha_{n}}{\alpha_{m}}$ (by Procedure 1). Therefore,
$\textbf{term}_{3}$ counts the number of trials up to the first success in a
repeated trial with success probabiliy $\frac{\alpha_{n}}{\alpha_{m}}$.
Therefore, with probability $1-\frac{\delta}{T}$, $\textbf{term}_{3}\leq
1+\frac{\log(T/\delta)}{-\log\left(1-\frac{\alpha_{n}}{\alpha_{m}}\right)}\leq\frac{2\alpha_{m}}{\alpha_{n}}\log(T/\delta)$.

Next, we deal with $\textbf{term}_{4}$. Below we show that
$\textbf{term}_{4}=0$. The event $V_{t}$ implies that there exists some
order-$m$ alg which starts at $\textit{alg}.s=t^{\star}$, where $t^{\star}\leq
t$ and $\tau_{i}(m)\leq t^{\star}\leq e_{i}-2\cdot 2^{m}$. Therefore, we have
$\textit{alg}.e=\textit{alg}.s+2^{m}-1=t^{\star}+2^{m}-1\leq
e_{i}-2^{m}-1<e_{i}$, and thus
$[\textit{alg}.s,\textit{alg}.e]\subseteq\mathcal{I}_{i}$. Together with
$X_{t}$, the event $V_{t}\cap X_{t}$ implies that
$\textit{alg}.e=\textit{alg}.s+2^{m}-1\leq t+2^{m}-1<E_{n}$, and therefore,
and time $\textit{alg}.e$, block $n$ has not ended.

Since at time $\textit{alg}.e$, block $n$ is still on-going, the learner
performs Test 1. By Lemma 3 (or Lemma 12 for the infinite-horizon RL case),
with high probability, we have

$\displaystyle\frac{1}{2^{m}}\sum_{\tau=\textit{alg}.s}^{\textit{alg}.e}R_{\tau}$
$\displaystyle\geq\frac{1}{2^{m}}\sum_{\tau=\textit{alg}.s}^{\textit{alg}.e}\widetilde{g}_{\tau}-\widehat{\alpha}_{m}-\widehat{n}\Delta_{[\textit{alg}.s,\textit{alg}.e]}$
(Lemma 3 or Lemma 12)
$\displaystyle\geq\min_{\tau\in\mathcal{I}_{i}}f_{\tau}^{\star}-\widehat{\alpha}_{m}-(\widehat{n}+1)\Delta_{\mathcal{I}_{i}}$
(because $[\textit{alg}.s,\textit{alg}.e]\subseteq\mathcal{I}_{i}$)
$\displaystyle\geq
f^{\star}_{\tau_{i}(m)}-\widehat{\alpha}_{m}-(\widehat{n}+3)\Delta_{\mathcal{I}_{i}}$
($|\min_{\tau\in\mathcal{I}_{i}}f_{\tau}^{\star}-f^{\star}_{\tau_{i}(m)}|\leq
2\Delta_{\mathcal{I}_{i}}$)
$\displaystyle\geq\widetilde{g}_{\tau_{i}(m)}+12\widehat{\alpha}_{m}-2\widehat{\alpha}_{m}$
(by the definition of $\tau_{i}(m)$ and
$\Delta_{\mathcal{I}_{i}}\leq\rho(|\mathcal{I}_{i}|)\leq\rho(2^{m})\leq\frac{\widehat{\alpha}_{m}}{6\widehat{n}}$)
$\displaystyle\geq U_{\textit{alg}.e}+10\widehat{\alpha}_{m}$ (Because
$\textit{alg}.e\geq\tau_{i}(m)$,
$U_{\textit{alg}.e}\leq\widetilde{g}_{\tau_{i}(m)}$ by the algorithm)

This should trigger the restart at time $\textit{alg}.e<E_{n}$, contradicting
the definition of $E_{n}$. Therefore, $\mathbbm{1}[X_{t},V_{t}]=0$.

Finally, combining all previous arguments, we have that with high probability,

$\displaystyle\sum_{i=1}^{\ell}\widehat{\alpha}_{m}\left[\xi_{i}(m)-4\cdot
2^{m}\right]_{+}$
$\displaystyle=\sum_{i=1}^{\ell}\widehat{\alpha}_{m}\left[e_{i}^{\prime}-\tau_{i}(m)+1-4\cdot
2^{m}\right]_{+}\leq\widehat{\alpha}_{m}2^{m}\sum_{i=1}^{\ell}A_{i}$
$\displaystyle=\widehat{C}(2^{m})\sum_{i=1}^{\ell}A_{i}\leq\frac{2\alpha_{m}}{\alpha_{n}}\widehat{C}(2^{m})\log(T/\delta),$

finishing the proof. ∎

##  Appendix D Single-block Regret Analysis II (under a Special Form of
$C(\cdot)$)

In Appendix C, we have derived the regret bound in a single block for both the
standard setting and the infinite-horizon MDP setting (Lemma 4 and Lemma 13).
They are both of the form

$\displaystyle\sum_{\tau\in\mathcal{J}}(f_{\tau}^{\star}-R_{\tau})=\widetilde{\mathcal{O}}\left(\sum_{i=1}^{\ell}C(|\mathcal{I}_{i}^{\prime}|)+\sum_{m=0}^{n}\frac{\rho(2^{n})}{\rho(2^{m})}C(2^{m})\right).$
(19)

(replacing $C(\cdot)$ and $\rho(\cdot)$ by
$C_{{\small\textsf{{UCRL}}}}(\cdot;\overline{D})$ and
$\rho(\cdot;\overline{D})$ for the case of infinite-horizon MDP).

In this section, we further derive more concrete dynamic regret bounds for
both cases by assuming that $C(\cdot)$ is of some specific form. The form of
$C(\cdot)$ we consider in this section is defined as follows:

######  Definition 18.

We define a form of $C(t)$ as $C(t)=\min\\{c_{1}t^{p}+c_{2},c_{3}t\\}$ for
some $p\in[\frac{1}{2},1)$ and some $c_{1}$, $c_{2}$, $c_{3}$ ($c_{3}\geq 1$)
that capture dependencies on $\log(T/\delta)$ and other problem-dependent
constants.

In fact, usually, a regret bound is only written in the form of
$c_{1}t^{p}+c_{2}$. However, since the reward is bounded between $0$ and $1$,
the regret bound of $\min\\{c_{1}t^{p}+c_{2},t\\}$ is also trivially correct.
Definition 18 is slightly more general than this by allowing a coefficient
$c_{3}\geq 1$ (the regret bound would still be trivially correct). In some
cases, we make $c_{1},c_{2},c_{3}$ larger than their tightest possible values
to make the final regret bound better — notice that the choice of
$c_{1},c_{2},c_{3}$ affects the probability specified in Procedure 1, and thus
smaller $c_{1},c_{2},c_{3}$ does not necessarily make the final regret bound
smaller. This subtle issue can be observed from the analysis.

To get a concrete bound, we also need to decide the number $\ell$ in the
single-block regret bound above. In Appendix C, we have stated the condition
(i.e., Eq. (15)) that should be satisfied by
$\mathcal{I}_{1}^{\prime},\ldots,\mathcal{I}_{\ell}^{\prime}$ (or
$\mathcal{I}_{1},\ldots,\mathcal{I}_{K}$). In the next lemma, we upper bound
the value of $\ell$ that is required to fulfill the condition.

######  Lemma 19.

Let $\mathcal{J}=[t_{n},E_{n}]$. Then we have $\ell\leq L_{\mathcal{J}}$.
Furthermore, if $C(t)$ is in the form specified in Definition 18, we also have
$\ell\leq
1+2\left(c_{1}^{-1}\Delta_{\mathcal{J}}|\mathcal{J}|^{1-p}\right)^{\frac{1}{2-p}}+c_{3}^{-1}\Delta_{\mathcal{J}}$.

###### Proof.

The fact that $\ell\leq L_{\mathcal{J}}$ is straightforward to see (and has
been explained in Appendix C): to satisfy the condition Eq. (15), one way to
divide the block is to make each $\mathcal{I}_{i}$ a stationary interval,
which makes $\Delta_{\mathcal{I}_{i}}=0$ for all $i\in[K]$. This way of
division leads to $\ell\leq L_{\mathcal{J}}$.

For the second claim, we follow the same procedure as decribed in the proof of
Lemma 5 in [Chen et al., 2019]. Basically, the procedure divides
$[t_{n},t_{n}+2^{n}-1]$ in a greedy way, making all
$\mathcal{I}_{i}=[s_{i},e_{i}]$ satisfy
$\Delta_{[s_{i},e_{i}]}\leq\rho(e_{i}-s_{i}+1)$ and
$\Delta_{[s_{i},e_{i}+1]}>\rho(e_{i}-s_{i}+2)$ for all $i\in[K-1]$ (i.e.,
except for the last interval). Then we have

$\displaystyle\Delta_{\mathcal{J}}$
$\displaystyle\geq\sum_{i=1}^{\ell-1}\Delta_{[s_{i},e_{i}+1]}$ (by the
definition of $\Delta_{[\cdot,\cdot]}$)
$\displaystyle>\sum_{i=1}^{\ell-1}\rho(e_{i}-s_{i}+2)$
$\displaystyle\geq\sum_{i=1}^{\ell-1}\min\left\\{c_{1}(e_{i}-s_{i}+2)^{p-1},c_{3}\right\\}$
(by Definition 18)
$\displaystyle\geq\sum_{i=1}^{\ell-1}\min\left\\{\frac{1}{2}c_{1}(e_{i}-s_{i}+1)^{p-1},c_{3}\right\\}$
($(x+2)^{p-1}\geq\left(2(x+1)\right)^{p-1}\geq\frac{1}{2}(x+1)^{p-1}$ for any
$x\geq 0$ and $p\leq 1$)
$\displaystyle=\frac{1}{2}\sum_{i=1}^{\ell_{1}}c_{1}(e_{i}-s_{i}+1)^{p-1}+\sum_{i=1}^{\ell_{2}}c_{3}$

where in the last equality we separate the intervals where
$\min\left\\{\frac{1}{2}c_{1}(e_{i}-s_{i}+1)^{p-1},c_{3}\right\\}$ takes the
former or the latter value. Note that $\ell_{1}+\ell_{2}=\ell-1$.

The above inequality implies that $\Delta_{\mathcal{J}}$ upper bounds both
$\frac{1}{2}\sum_{i=1}^{\ell_{1}}c_{1}(e_{i}-s_{i}+1)^{p-1}$ and
$\sum_{i=1}^{\ell_{2}}c_{3}$. Thus, $\ell_{2}\leq
c_{3}^{-1}\Delta_{\mathcal{J}}$, and by Hölder’s inequality,

$\displaystyle\ell_{1}$
$\displaystyle\leq\left(\sum_{i=1}^{\ell_{1}}(e_{i}-s_{i}+1)^{p-1}\right)^{\frac{1}{2-p}}\left(\sum_{i=1}^{\ell_{1}}(e_{i}-s_{i}+1)\right)^{\frac{1-p}{2-p}}\leq\left(\frac{2\Delta_{\mathcal{J}}}{c_{1}}\right)^{\frac{1}{2-p}}|\mathcal{J}|^{\frac{1-p}{2-p}}.$

Combining them finishes the proof. ∎

In the following Lemma 20, we bound the regret within a block by combining Eq.
(19) and Lemma 19. We will frequently use the following two properties: let
$\\{\mathcal{S}_{1},\mathcal{S}_{2},\ldots,\mathcal{S}_{K}\\}$ be a partition
of the interval $\mathcal{S}$. Then

$\displaystyle\sum_{i=1}^{K}L_{\mathcal{S}_{i}}$ $\displaystyle\leq
L_{\mathcal{S}}+(K-1),$ (20)
$\displaystyle\sum_{i=1}^{K}\Delta_{\mathcal{S}_{i}}$
$\displaystyle\leq\Delta_{\mathcal{S}}.$ (21)

They can be derived using the definitions of $L_{[\cdot,\cdot]}$ and
$\Delta_{[\cdot,\cdot]}$.

######  Lemma 20.

If $C(t)$ is of the form specified in Definition 18, then

$\displaystyle\sum_{\tau=t_{n}}^{E_{n}}(f_{\tau}^{\star}-R_{\tau})\leq\widetilde{\mathcal{O}}\left(\min\Big{\\{}\text{\rm
Reg}_{L}(\mathcal{J}),\text{\rm
Reg}_{\Delta}(\mathcal{J})\Big{\\}}+c_{1}2^{np}+\frac{c_{2}c_{3}}{c_{1}}2^{n(1-p)}+\frac{c_{2}^{2}}{c_{3}}\right),$

where $\text{\rm Reg}_{L}(\mathcal{J})\triangleq
c_{1}L_{\mathcal{J}}^{1-p}|\mathcal{J}|^{p}+c_{2}L_{\mathcal{J}}$ and

$\displaystyle\text{\rm Reg}_{\Delta}(\mathcal{J})$
$\displaystyle\triangleq\left(c_{1}\Delta_{\mathcal{J}}^{1-p}|\mathcal{J}|\right)^{\frac{1}{2-p}}+c_{1}|\mathcal{J}|^{p}+c_{1}(c_{3}^{-1}\Delta_{\mathcal{J}})^{1-p}|\mathcal{J}|^{p}+c_{2}\left(c_{1}^{-1}\Delta_{\mathcal{J}}|\mathcal{J}|^{1-p}\right)^{\frac{1}{2-p}}+c_{2}+c_{2}c_{3}^{-1}\Delta_{\mathcal{J}}.$

###### Proof.

We bound each term in Eq. (19) using Definition 18. First, notice that

$\displaystyle\widetilde{\mathcal{O}}\left(\sum_{i=1}^{\ell}C(|\mathcal{I}_{i}^{\prime}|)\right)$
$\displaystyle=\widetilde{\mathcal{O}}\left(\sum_{i=1}^{\ell}\min\left\\{c_{1}|\mathcal{I}_{i}^{\prime}|^{p}+c_{2},\
c_{3}t\right\\}\right)$
$\displaystyle\leq\widetilde{\mathcal{O}}\left(\sum_{i=1}^{\ell}(c_{1}|\mathcal{I}_{i}^{\prime}|^{p}+c_{2})\right)\leq\widetilde{\mathcal{O}}\left(c_{1}\ell^{1-p}|\mathcal{J}|^{p}+c_{2}\ell\right).$
(22)

Using the first upper bound for $\ell$ given in Lemma 19, Eq. (22) can be
bounded by $\widetilde{\mathcal{O}}\left(\text{\rm
Reg}_{L}(\mathcal{J})\right)$; using the second upper bound, Eq. (22) can be
bounded by $\widetilde{\mathcal{O}}\left(\text{\rm
Reg}_{\Delta}(\mathcal{J})\right)$. Next, we have

$\displaystyle\widetilde{\mathcal{O}}\left(\frac{\rho(2^{m})}{\rho(2^{n})}C(2^{m})\right)=\widetilde{\mathcal{O}}\left(c_{1}2^{np}+\frac{c_{2}c_{3}}{c_{1}}2^{n(1-p)}+\frac{c_{1}^{2}}{c_{3}}2^{m(2p-1)}+\frac{c_{2}^{2}}{c_{3}}2^{-m}\right).$

by Lemma 21 below. Notice that because $c_{3}\geq 1$ and $p\geq\frac{1}{2}$,
$\frac{c_{1}^{2}}{c_{3}}2^{m(2p-1)}\leq c_{1}^{2}2^{n(2p-1)}\leq c_{1}2^{np}$
when $c_{1}\leq 2^{n(1-p)}$. This is indeed the regime we care about since if
$c_{1}>2^{n(1-p)}$ then the first term $c_{1}2^{np}>2^{n}$, which is a vacuous
bound for the regret of block $n$. Therefore, we can drop this term. Thus, the
dynamic regret in block $n$ can be summarized as the following based on Eq.
(19):

$\displaystyle\widetilde{\mathcal{O}}\left(\min\Big{\\{}\text{\rm
Reg}_{L}(\mathcal{J}),\text{\rm
Reg}_{\Delta}(\mathcal{J})\Big{\\}}+c_{1}2^{np}+\frac{c_{2}c_{3}}{c_{1}}2^{n(1-p)}+\frac{c_{2}^{2}}{c_{3}}\right),$
(23)

finishing the proof. ∎

######  Lemma 21.

Let $C(t)$ be of the form in Definition 18. Then

$\displaystyle\frac{\rho(2^{m})}{\rho(2^{n})}C(2^{m})=\mathcal{O}\left(c_{1}2^{np}+\frac{c_{2}c_{3}}{c_{1}}2^{n(1-p)}+\frac{c_{1}^{2}}{c_{3}}2^{m(2p-1)}+\frac{c_{2}^{2}}{c_{3}}2^{-m}\right).$

###### Proof.

This is by direct calculation:

$\displaystyle\frac{\rho(2^{m})}{\rho(2^{n})}C(2^{m})$
$\displaystyle=\frac{C(2^{m})^{2}}{C(2^{n})}2^{n-m}$
$\displaystyle=\mathcal{O}\left(\frac{\min\\{c_{1}^{2}2^{2mp}+c_{2}^{2},\ \
c_{3}^{2}2^{2m}\\}}{c_{1}2^{np}+c_{2}}2^{n-m}+\frac{\min\\{c_{1}^{2}2^{2mp}+c_{2}^{2},\
\ c_{3}^{2}2^{2m}\\}}{c_{3}2^{n}}2^{n-m}\right)$
$\displaystyle=\mathcal{O}\left(\min\left\\{c_{1}2^{np}2^{(n-m)(1-2p)}+\frac{c_{2}^{2}}{c_{1}}2^{n(1-p)-m},\
\
\frac{c_{3}^{2}}{c_{1}}2^{n(1-p)+m}\right\\}+\frac{c_{1}^{2}}{c_{3}}2^{m(2p-1)}+\frac{c_{2}^{2}}{c_{3}}2^{-m}\right)$
$\displaystyle=\mathcal{O}\left(c_{1}2^{np}+\min\left\\{\frac{c_{2}^{2}}{c_{1}}2^{n(1-p)-m},\
\
\frac{c_{3}^{2}}{c_{1}}2^{n(1-p)+m}\right\\}+\frac{c_{1}^{2}}{c_{3}}2^{m(2p-1)}+\frac{c_{2}^{2}}{c_{3}}2^{-m}\right)$
$\displaystyle=\mathcal{O}\left(c_{1}2^{np}+\frac{c_{2}c_{3}}{c_{1}}2^{n(1-p)}+\frac{c_{1}^{2}}{c_{3}}2^{m(2p-1)}+\frac{c_{2}^{2}}{c_{3}}2^{-m}\right).$

∎

##  Appendix E Single-epoch Regret Analysis

We call $[t_{0},E]$ an _epoch_ if $t_{0}$ is the first step after restart (or
$t_{0}=1$), and $E$ is the first time after round $t_{0}$ when the restart is
triggered. In this section, we continue the discussion in Appendix D and bound
the regret in a single epoch. Recall that the we consider cases where the
single-block regret can be written as Eq. (19) and $C(\cdot)$ is in the form
of Definition 18. This holds both for the case of the standard setting and the
infinite-horizon MDP setting.

######  Lemma 22.

Let $\mathcal{E}$ be an epoch. Then

$\displaystyle\sum_{\tau\in\mathcal{E}}\leq\widetilde{\mathcal{O}}\left(\min\big{\\{}\text{\rm
Reg}_{L}(\mathcal{E}),\text{\rm
Reg}_{\Delta}(\mathcal{E})\big{\\}}+\frac{c_{2}c_{3}}{c_{1}}|\mathcal{E}|^{1-p}+\frac{c_{2}^{2}}{c_{3}}\right)$

($\text{\rm Reg}_{L}(\cdot)$ and $\text{\rm Reg}_{\Delta}(\cdot)$ are defined
in Lemma 20)

###### Proof.

Let $\mathcal{E}$ be an epoch whose last block is indexed by $n$. Then
$|\mathcal{E}|=\Theta(2^{n})$. Let $\mathcal{J}_{1},\ldots,\mathcal{J}_{n}$ be
blocks in $\mathcal{E}$. Then by Lemma 20, the dynamic regret in $\mathcal{E}$
is upper bounded by

$\displaystyle\widetilde{\mathcal{O}}\left(\min\left\\{\sum_{m=0}^{n}\text{\rm
Reg}_{L}(\mathcal{J}_{m}),\ \sum_{m=0}^{n}\text{\rm
Reg}_{\Delta}(\mathcal{J}_{m})\right\\}+c_{1}\sum_{m=0}^{n}2^{mp}+\frac{c_{2}c_{3}}{c_{1}}\sum_{m=0}^{n}2^{m(1-p)}+\sum_{m=0}^{n}\frac{c_{2}^{2}}{c_{3}}\right).$

By Hölder’s inequality,

$\displaystyle\sum_{m=0}^{n}\text{\rm Reg}_{L}(\mathcal{J}_{m})$
$\displaystyle=c_{1}\left(\sum_{m=0}^{n}L_{\mathcal{J}_{m}}\right)^{1-p}\left(\sum_{m=0}^{n}|\mathcal{J}_{m}|\right)^{p}+c_{2}\sum_{m=0}^{n}L_{\mathcal{J}_{m}}$
$\displaystyle\leq
c_{1}\left(L_{\mathcal{E}}+n\right)^{1-p}|\mathcal{E}|^{p}+c_{2}\left(L_{\mathcal{E}}+n\right)$
(using Eq. (20))
$\displaystyle\leq\widetilde{\mathcal{O}}\left(c_{1}L_{\mathcal{E}}^{1-p}|\mathcal{E}|^{p}+c_{2}L_{\mathcal{E}}\right)=\widetilde{\mathcal{O}}\left(\text{\rm
Reg}_{L}(\mathcal{E})\right)$ (because $n=\mathcal{O}(\log
T)=\widetilde{\mathcal{O}}(1)$)

Similarly, $\sum_{m=0}^{n}\text{\rm
Reg}_{\Delta}(\mathcal{J}_{m})=\widetilde{\mathcal{O}}\left(\text{\rm
Reg}_{\Delta}(\mathcal{E})\right)$. On the other hand,
$c_{1}\sum_{m=0}^{n}2^{mp}+\frac{c_{2}c_{3}}{c_{1}}\sum_{m=0}^{n}2^{m(1-p)}+\sum_{m=0}^{n}\frac{c_{2}^{2}}{c_{3}}=\widetilde{\mathcal{O}}\left(c_{1}2^{np}+\frac{c_{2}c_{3}}{c_{1}}2^{n(1-p)}+\frac{c_{2}^{2}}{c_{3}}\right)=\widetilde{\mathcal{O}}\left(c_{1}|\mathcal{E}|^{p}+\frac{c_{2}c_{3}}{c_{1}}|\mathcal{E}|^{1-p}+\frac{c_{2}^{2}}{c_{3}}\right)$.
In summary, the dynamic regret within an epoch is of order

$\displaystyle\widetilde{\mathcal{O}}\left(\min\big{\\{}\text{\rm
Reg}_{L}(\mathcal{E}),\text{\rm
Reg}_{\Delta}(\mathcal{E})\big{\\}}+\frac{c_{2}c_{3}}{c_{1}}|\mathcal{E}|^{1-p}+\frac{c_{2}^{2}}{c_{3}}\right)$
(24)

(the $c_{1}|\mathcal{E}|^{p}$ term is absorbed into $\min\left\\{\text{\rm
Reg}_{L}(\mathcal{E}),\text{\rm Reg}_{\Delta}(\mathcal{E})\right\\}$). ∎

##  Appendix F Proof of Theorem 2

We are now ready to prove Theorem 2 after showing the following two lemmas.

######  Lemma 23.

Let $t$ be in an epoch starting from $t_{0}$. If
$\Delta_{[t_{0},t]}\leq\rho(t-t_{0}+1)$, then with high probability, no
restart would be triggered at time $t$.

###### Proof.

We first verify that Test 1 would not fail with high probability. Let
$t=\textit{alg}.e$ where alg is any order-$m$ ALG in block $n$. Then with high
probability,

$\displaystyle U_{t}$
$\displaystyle=\min_{\tau\in[t_{n},t]}\widetilde{g}_{\tau}$
$\displaystyle\geq\min_{\tau\in[t_{n},t]}f^{\star}_{\tau}-\Delta_{[t_{n},t]}$
(by Lemma 3)
$\displaystyle\geq\frac{1}{2^{m}}\sum_{\tau\in[\textit{alg}.s,t]}f^{\star}_{\tau}-3\Delta_{[t_{n},t]}$
($[\textit{alg}.s,t]\subseteq[t_{n},t]$)
$\displaystyle\geq\frac{1}{2^{m}}\sum_{\tau\in[\textit{alg}.s,t]}R_{\tau}-2\sqrt{\frac{\log(T/\delta)}{2^{m}}}-3\rho(t-t_{0}+1)$
($\mathbb{E}[R_{\tau}]=\mathbb{E}[f_{\tau}(\pi_{t})]\leq f_{\tau}^{\star}$ and
we use Azuma’s inequality)
$\displaystyle\geq\frac{1}{2^{m}}\sum_{\tau\in[\textit{alg}.s,t]}R_{\tau}-\widehat{\rho}(2^{m})-3\rho(t-t_{0}+1)$
(By Assumption 1, $\widehat{\rho}(2^{m})\geq 6\log(T/\delta)\rho(2^{m})\geq
6\log(T/\delta)\sqrt{\frac{1}{2^{m}}}$)
$\displaystyle\geq\frac{1}{2^{m}}\sum_{\tau\in[\textit{alg}.s,t]}R_{\tau}-2\widehat{\rho}(2^{m}).$
($\rho(t-t_{0}+1)\leq\rho(2^{m})$ because $\rho(\cdot)$ is decreasing)

So with high probability, Test 1 will not return fail.

Furthermore, by Lemma 3, with high probability,

$\displaystyle\frac{1}{t-t_{n}+1}\sum_{\tau=t_{n}}^{t}\left(\widetilde{g}_{\tau}-R_{\tau}\right)\leq\widehat{\rho}(t-t_{n}+1)+\Delta_{[t_{n},t]}\leq
2\widehat{\rho}(t-t_{n}+1).$

Therefore, with high probability, Test 2 will not return fail either. ∎

######  Lemma 24.

With high probability, the number of epochs is upper bounded by $L$. If
$C(\cdot)$ is in the form of Definition 18, the number of epochs is also upper
bounded by $1+2\left(c_{1}^{-1}\Delta
T^{1-p}\right)^{\frac{1}{2-p}}+c_{3}^{-1}\Delta$.

###### Proof.

By Lemma 23, if $[t_{0},E]$ is not the last epoch, then
$\Delta_{[t_{0},E]}>\rho(E-t_{0}+1)$ with high probability. Then following the
exact same arguments as in Lemma 19 proves the lemma. ∎

###### Proof of Theorem 2.

If $C(t)=c_{1}t^{p}+c_{2}$ satisfies Assumption 1, then
$C(t)=\min\\{c_{1}t^{p}+c_{2},t\\}$ also satisfies it (since the reward is
bounded in $[0,1]$). Below we use $C(t)=\min\\{c_{1}t^{p}+c_{2},t\\}$ as the
input to our algorithm. Notice that this is in the form of Definition 18 with
$c_{3}=1$. Let $\mathcal{E}_{1},\ldots,\mathcal{E}_{N}$ be epochs in $[1,T]$.
Then by Lemma 22, the dynamic regret in $[1,T]$ is upper bounded by

$\displaystyle\widetilde{\mathcal{O}}\left(\min\left\\{\sum_{i=1}^{N}\text{\rm
Reg}_{L}(\mathcal{E}_{i}),\sum_{i=1}^{N}\text{\rm
Reg}_{\Delta}(\mathcal{E}_{i})\right\\}+\frac{c_{2}}{c_{1}}\sum_{i=1}^{N}|\mathcal{E}_{i}|^{1-p}+c_{2}^{2}N\right).$
(25)

By Hölder’s inequality and Eq. (20),

$\displaystyle\sum_{i=1}^{N}\text{\rm
Reg}_{L}(\mathcal{E}_{i})\leq\widetilde{\mathcal{O}}\left(c_{1}\left(L+N-1\right)^{1-p}T^{p}+c_{2}(L+N-1)\right)\leq\widetilde{\mathcal{O}}\left(c_{1}L^{1-p}T^{p}+c_{2}L\right),$

where in the last inequality we use Lemma 24 to bound $N$.

Similarly,

$\displaystyle\sum_{i=1}^{N}\text{\rm Reg}_{\Delta}(\mathcal{E}_{i})$
$\displaystyle\leq\widetilde{\mathcal{O}}\left(\left(c_{1}\Delta^{1-p}T\right)^{\frac{1}{2-p}}+c_{1}N^{1-p}T^{p}+c_{1}\Delta^{1-p}T^{p}+c_{2}\left(c_{1}^{-1}\Delta
T^{1-p}\right)^{\frac{1}{2-p}}+c_{2}N+c_{2}\Delta\right)$
$\displaystyle\leq\widetilde{\mathcal{O}}\left(\left(c_{1}\Delta^{1-p}T\right)^{\frac{1}{2-p}}+c_{1}T^{p}+c_{1}\Delta^{1-p}T^{p}+c_{2}\left(c_{1}^{-1}\Delta
T^{1-p}\right)^{\frac{1}{2-p}}+c_{2}+c_{2}\Delta\right).$ (using Lemma 24 to
bound $N$)

Then we deal with the second term in Eq. (25):

$\displaystyle\frac{c_{2}}{c_{1}}\sum_{i=1}^{N}|\mathcal{E}_{i}|^{1-p}\leq\frac{c_{2}}{c_{1}}N^{p}T^{1-p},$

which can be either bounded by
$\widetilde{\mathcal{O}}\left(\frac{c_{2}}{c_{1}}L^{p}T^{1-p}\right)$ or

$\displaystyle\widetilde{\mathcal{O}}\left(\frac{c_{2}}{c_{1}}T^{1-p}+\frac{c_{2}}{c_{1}}\left(c_{1}^{-p}\Delta^{p}T^{2-2p}\right)^{\frac{1}{2-p}}+\frac{c_{2}}{c_{1}}\Delta^{p}T^{1-p}\right)$

using the upper bound for $N$ in Lemma 24. Finally, the third term in Eq. (25)
can be upper bounded either by
$\widetilde{\mathcal{O}}\left(c_{2}^{2}L\right)$ or

$\displaystyle\widetilde{\mathcal{O}}\left(c_{2}^{2}+c_{2}^{2}\left(c_{1}^{-1}\Delta
T^{1-p}\right)^{\frac{1}{2-p}}+c_{2}^{2}\Delta\right).$

With all terms expanded, below, we collect the dominant terms for the cases of
$p=\frac{1}{2}$ and $p>\frac{1}{2}$. We say term $a(T)$ is dominated by $b(T)$
if $\lim_{T\rightarrow\infty}a(T)/b(T)=0$ under any sublinear growth rate of
$L$ or $\Delta$ (e.g., $\sqrt{\Delta T}$ is dominated by
$\Delta^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}$ and $L$ is dominated by
$\sqrt{LT}$). And below we only write down terms that are not dominated by
other terms.

#### The case for $p=\frac{1}{2}$:

$\displaystyle\widetilde{\mathcal{O}}\left(\min\left\\{\left(c_{1}+\frac{c_{2}}{c_{1}}\right)\sqrt{LT},\quad\left(c_{1}^{\nicefrac{{2}}{{3}}}+c_{2}c_{1}^{-\nicefrac{{4}}{{3}}}\right)\Delta^{\nicefrac{{1}}{{3}}}T^{\nicefrac{{2}}{{3}}}+\left(c_{1}+\frac{c_{2}}{c_{1}}\right)\sqrt{T}\right\\}\right);$

#### The case for $p>\frac{1}{2}$:

$\displaystyle\widetilde{\mathcal{O}}\left(\min\left\\{c_{1}L^{1-p}T^{p},\quad\left(c_{1}\Delta^{1-p}T\right)^{\frac{1}{2-p}}+c_{1}T^{p}\right\\}\right).$

This finishes the proof. ∎

##  Appendix G Main Results for Infinite-horizon MDP

######  Lemma 25 (c.f. Lemma 23).

Let $t$ be in an epoch started from round $t_{0}$. If
$\Delta_{[t_{0},t];\overline{D}}<\overline{D}S\sqrt{\frac{A}{t-t_{0}+1}}$ and
$\overline{D}\geq D_{\max}$, then with high probability, no restart will be
triggered at time $t$.

###### Proof.

To verify that Test 1 will not fail with high probability, we follow very
similar steps as in Lemma 23. Let $t=\textit{alg}.e$ where alg is an order-$m$
ALG in block $n$. Then with high probability (the following calculation is
same as that in the proof of Lemma 23 except for the third inequality),

$\displaystyle U_{t}$
$\displaystyle=\min_{\tau\in[t_{n},t]}\widetilde{g}_{\tau}$
$\displaystyle\geq\min_{\tau\in[t_{n},t]}J^{\star}_{\tau}-\Delta_{[t_{n},t];\overline{D}}$
(by Lemma 12)
$\displaystyle\geq\frac{1}{2^{m}}\sum_{\tau\in[\textit{alg}.s,t]}J^{\star}_{\tau}-3\Delta_{[t_{n},t];\overline{D}}$
($[\textit{alg}.s,t]\subseteq[t_{0},t]$)
$\displaystyle\geq\frac{1}{2^{m}}\sum_{\tau\in[\textit{alg}.s,t]}R_{\tau}-4\overline{D}\sqrt{\frac{\log(T/\delta)}{2^{m}}}-4\Delta_{[t_{n},t];\overline{D}}$
(explained below)
$\displaystyle\geq\frac{1}{2^{m}}\sum_{\tau\in[\textit{alg}.s,t]}R_{\tau}-4\widehat{\rho}_{\small\textsf{{UCRL}}}(2^{m};\overline{D})-4\rho_{\small\textsf{{UCRL}}}(t-t_{0}+1;\overline{D})$
$\displaystyle\geq\frac{1}{2^{m}}\sum_{\tau\in[\textit{alg}.s,t]}R_{\tau}-8\widehat{\rho}_{\small\textsf{{UCRL}}}(2^{m};\overline{D}).$
($\rho(t-t_{0}+1)\leq\rho(2^{m})$ because $\rho(\cdot)$ is decreasing)

where the third inequality is based on the following calculation: for all
$\tau\in[\textit{alg}.s,t]$,

$\displaystyle J_{t}^{\star}$
$\displaystyle=r_{t}(s_{\tau},a_{\tau})+\sum_{s^{\prime}}p_{t}(s^{\prime}|s_{\tau},a_{\tau})h_{t}^{\star}(s^{\prime})-h_{t}^{\star}(s_{\tau})$
$\displaystyle\geq
r_{\tau}(s_{\tau},a_{\tau})+\sum_{s^{\prime}}p_{\tau}(s^{\prime}|s_{\tau},a_{\tau})h_{t}^{\star}(s^{\prime})-h_{t}^{\star}(s_{\tau})-\left(\Delta^{r}_{[\textit{alg}.s,t]}+D_{\max}\Delta^{p}_{[\textit{alg}.s,t]}\right)$
$\displaystyle\geq