# Fundamental Limits of Reinforcement Learning in Environment with Endogeneous
and Exogeneous Uncertainty

Rongpeng Li R. Li is with College of Information Science & Electronic
Engineering, Zhejiang University, Hangzhou 310027, China (email:
lirongpeng@zju.edu.cn). Part of this work is done when R. Li was a visiting
scholar at College of Computer Science and Technology, The University of
Cambridge, UK.

###### Abstract

Online reinforcement learning (RL) has been widely applied in information
processing scenarios, which usually exhibit much uncertainty due to the
intrinsic randomness of channels and service demands. In this paper, we
consider an un-discounted RL in general Markov decision processes (MDPs) with
both endogeneous and exogeneous uncertainty, where both the rewards and state
transition probability are unknown to the RL agent and evolve with the time as
long as their respective variations do not exceed certain dynamic budget
(i.e., upper bound). We first develop a variation-aware Bernstein-based upper
confidence reinforcement learning (VB-UCRL), which we allow to restart
according to a schedule dependent on the variations. We successfully overcome
the challenges due to the exogeneous uncertainty and establish a regret bound
of saving at most $\sqrt{S}$ or $S^{\frac{1}{6}}T^{\frac{1}{12}}$ compared
with the latest results in the literature, where $S$ denotes the state size of
the MDP and $T$ indicates the iteration index of learning steps.

###### Index Terms:

Reinforcement learning, regret bound, Markov decision process, endogeneous and
exogeneous uncertainty

##  I Introduction

Reinforcement learning (RL) [1], one category of machine learning, has
manifested itself in empowering an agent to interact with an environment with
much uncertainty. Besides its success in AlphaGo [2], RL has been widely
applied in solving information processing problems in areas including wireless
communications & networking [3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16,
17], computer vision and robot navigation [18, 19]. Typically, the RL
formalizes this interaction between the agent and the environment in these
scenarios through an “economic” perspective [20]. In other words, RL often
models the problem as a Markov decision process (MDP), consisting of a tuple
of state, action, reward (or equivalently loss) and transition probability,
and an RL agent tries to maximize the cumulative rewards or minimizing the
cumulative loss, by observing the environment as a state and taking an action
accordingly. For example, [3] and [11] try to achieve larger throughput, by
considering the networking factors (e.g., goodput, average round-trip time
(RTT), data rate) as the state and learning a RL policy to adjust the
congestion window of transmission control protocol (TCP). Meanwhile, [12] aims
to maximize the rate by regarding the channel information as the state and
leveraging RL to make channel assignment and power allocation actions. Note-
worthily, in these scenarios, online RL emerges as a popular option.
Therefore, it naturally raises a question what is the fundamental performance
limit of online RL-based solutions regardless of the specific RL applications?

The difficulty to know this limit mainly lies in the _endogeneous_ and
_exogeneous_ uncertainty in the MDP. Specifically, in the classical time-
homogeneous MDP settings, only endogeneous uncertainty is considered. In other
words, at each time-step, the reward follows a reward distribution and the
subsequent state follows a state transition distribution. Both distributions
solely depend on the current state and action and remain fixed along with the
temporal variations. Unfortunately, the aforementioned scenarios often face
time-varying reward and transition probability distributions, due to non-
stationary channels [16] and service demands. Therefore, the exogeneous
uncertainty has to be taken into account. Typically, in order to unveil the
uncertainty in the MDP, the RL agent has to explore the MDP to accumulate the
related knowledge of those poorly-visited states and actions. As any decision
of RL affects the subsequent observations, more exploration usually produces
long-term impact yet affects short-term exploitation efficiency, which is also
termed as the _exploration-exploitation dilemma_ [1] originally discussed in
the literature of multi-arm bandit (MAB) [21].

There has been intense research interest towards understanding the performance
limit of online RL-based solutions for an time-homogeneous MDP. For example,
[22] talked about the performance of a learned policy, while Jaksch et al.
gave the performance limit of an RL algorithm during the learning [23], which
is more meaningful for online RL in information processing scenarios.
Specifically, Jaksch et al. proposed a UCRL2 algorithm (upper confidence bound
for reinforcement learning) for un-discounted reinforcement learning in
communicating MDPs. In other words, UCRL2 implements the paradigm of “optimism
in the face of uncertainty” and construct plausible MDPs in confidence
interval based on the Hoeffding inequality [24] and proves that the total
regret of an RL algorithm with respect to an optimal policy could be bounded
by $\tilde{O}(DS\sqrt{AT})$, where $\tilde{\mathcal{O}}(\cdot)$ hides the
logarithmic factors, $S$ and $A$ denote the size of the state space and action
space of the MDP, respectively. $D$ is the diameter of the communicating MDP,
indicating the minimal expected number of steps from each state to another
state in MDP. Besides, $T$ denotes the iteration of learning steps. Based on
UCRL2, many variants have been proposed to generate tighter bounds. [25]
proved a more efficient posterior sampling for episodic reinforcement learning
and established an $\tilde{O}(\iota S\sqrt{AT})$ bound on the expected regret
with the episode length $\iota$. [26] proposed a non-parametric and data-
dependent algorithm based on the multiplier bootstrap for MAB. [27] proposed a
UCCRL algorithm to derive sublinear regret bounds for finite-horizon un-
discounted reinforcement learning in continuous state space. Later, [28]
focused on an infinite-horizon un-discounted setting and used an exploration
bonus to achieve the same regret bound as UCCRL [27].

Until recently, there emerges few light shed on MDP with both endogeneous and
exogeneous uncertainty. [29] and [30] talked about online learning for MDP in
this non-stationary environment and provided the dynamic regret analysis for
exogeneous uncertainty only. [31] extended UCRL2 to a variation-aware
algorithm and provided performance guarantees for the regret evaluated against
the optimal non-stationary policy. [32] and [33] gave a more comprehensive
study of the dynamic regret, and derived a bound of
$\tilde{O}\left((V_{r}^{T}+V_{p}^{T})^{1/4}S^{2/3}A^{1/2}T^{3/4}\right)$,
where $V_{r}$ and $V_{p}$ are the dynamic budget (i.e., upper bound) of
variations in reward and transition probability functions.

Compared with the aforementioned research, the contribution of this paper can
be summarized as follows.

  * •

We focus on the RL for MDP with both endogeneous and exogeneous uncertainty,
which has significant applications in information processing scenarios.

  * •

We propose a variation-aware Bernstein-based upper confidence reinforcement
learning (VB-UCRL) algorithm, which restarts according to a schedule dependent
on the variations in the MDP and leverages the empirical Bernstein inequality
[34] to give a tighter bound.

  * •

We prove that the VB-UCRL gives a regret bound of
$\tilde{O}\left((V_{r}+V_{p})^{1/3}T^{2/3}\sqrt{\Gamma SA}\right)$, where
$\Gamma$ denotes the maximal number of reachable states for any state-action
pair in the MDP. As discussed in Section V, this bound is tighter than the
latest results in [31, 33].

The remainder of the paper is organized as follows. In Section II, we
introduce some fundamentals of MDPs and useful concentration inequalities. In
Section III and Section IV, we formulate the regret problem of RL for MDP with
both endogeneous and exogeneous uncertainty, and prove the related results for
the proposed VB-UCRL. Section V discusses the aforementioned results, by
comparing with the state-of-the-art results in the literature. We conclude the
paper in Section VI.

##  II Preliminaries

###  II-A Fundamentals of MDPs

In a time-homogeneous MDP $M=<\mathcal{S},\mathcal{A},r,p,s_{1}>$ with state
space $\mathcal{S}$, action space $\mathcal{A}$ and the initial state $s_{1}$.
Every state-action-pair is characterized by a reward distribution with mean
$r(s,a)\in[0,r_{\max}]$ over next states. For simplicity of representation, we
denote the size of state space and action space as $S=|\mathcal{S}|$ and
$A=|\mathcal{A}|$, respectively. Furthermore, we assume the number of
reachable states for a state-action pair $(s,a)$ as
$\Gamma(s,a)=\|p(\cdot|s,a)>0\|_{0}$ and $\Gamma=\max_{s,a}\Gamma(s,a)$.
Notably, in the time-homogeneous MDP, the mean rewards and transition
probabilities only depend on the current state and the chosen action. An MDP
is called communicating, if for any two states $s$, $s^{\prime}$, when
starting in $s$ it is possible to reach $s^{\prime}$ with positive probability
choosing appropriate actions.

We primarily focus on the infinite-horizon un-discounted MDP settings and try
to learn a policy $\pi$ that maximizes

$\sup_{\pi\in\Pi}\left\\{\liminf_{T\rightarrow+\infty}\mathbb{E}_{s}^{\pi}\left[\frac{1}{T}\sum_{t=1}^{T}r(s_{t},a_{t})\bigg{|}s_{1}\sim\mu_{1}\right]\right\\}$
(1)

where $\mu_{1}$ is the state probability of the starting state $s_{1}$. The
set of stationary randomized (resp. deterministic) policies is denoted by
$\Pi^{\text{SR}}$ (resp. $\Pi^{\text{SD}})$111A Markov randomized decision
rule $d:\mathcal{S}\rightarrow\mathcal{P}(\mathcal{A})$ maps states to
distributions over actions while a Markov deterministic decision rule
$d:\mathcal{S}\rightarrow\mathcal{A}$ maps states to actions.. The subset of
Markov randomized decision rules is denoted $D^{\text{MR}}$, while the subset
of Markov deterministic decision rules is denoted $D^{\text{MD}}$. For any
Markov decision rule $d\in D^{\text{MR}}$, $P_{d}\in\mathbb{R}^{S\times S}$
and $r_{d}\in\mathbb{R}^{S}$ denote the transition matrix and reward vector
associated with $d$ i.e.,
$P_{d}(s^{\prime}|s)\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum_{a\in\mathcal{A}_{s}}d(a|s)p(s^{\prime}|s,a)$
and
$r_{d}(s)\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum_{a\in\mathcal{A}_{s}}d(a|s)r(s,a)$,
for all $s,s\in\mathcal{S}$, where $d(a|s)$ is the probability to sample $a$
in state $s$ when using $d$.

For a stationary policy, i.e., $\pi\in\Pi^{\text{SR}}$, the lim inf in (1)
actually matches the lim sup and the limit is well defined (Section 8.2.1,
[35]). In other words, any policy $\pi\in\Pi^{\text{SR}}$ has an associated
long-term average reward (or gain) $g^{\pi}(s)$ and a bias function $h(s)$,
which is defined as

$\displaystyle
g^{\pi}(s)\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\lim_{T\rightarrow+\infty}\mathbb{E}_{s}^{\pi}\big{[}\frac{1}{T}\sum_{t=1}^{T}r(s_{t},a_{t})\big{]}$
(2)

and

$\displaystyle h^{\pi}(s)$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\underset{T\rightarrow+\infty}{C\textendash\lim}\mathbb{E}_{s}^{\pi}\left[\sum_{t=1}^{T}\left(r\left(s_{t},a_{t}\right)-g^{\pi}\left(s_{t}\right)\right)\right]$
(3)
$\displaystyle=\lim_{T\rightarrow+\infty}\frac{1}{T}\sum_{k=1}^{T}\mathbb{E}_{s}^{\pi}\left[\sum_{t=1}^{k}\left(r\left(s_{t},a_{t}\right)-g^{\pi}\left(s_{t}\right)\right)\right],$
(4)

respectively. Here, ${E}_{s}^{\pi}$ takes an expectation over trajectories
generated starting from $s_{1}=s$ with action $a_{t}\sim\pi(s_{t})$. The bias
$h^{\pi}(s)$ measures the expected total diﬀerence between the reward and the
stationary reward in Cesaro-limit (denoted by $C\textendash\lim$)222The
Cesaro-limit is always well-deﬁned unlike the “classical” limit as the series
may cycle i.e., have several accumulation points or “cluster points”. Note
that for policies with an aperiodic chain, the standard limit exists. Another
useful theorem for this limit is the theorem of Cesaro Means, that is, if the
limit of a sequence $a_{1},\cdots,a_{n}$ exists
$\lim_{n\rightarrow\infty}a_{n}=a$, let $b_{n}=n^{-1}\sum_{i}^{n}a_{i}$, then
$\lim_{n\rightarrow\infty}b_{n}=a$..

Accordingly, the difference of bias $h^{\pi}(s^{\prime})-h^{\pi}(s)$
quantifies the (dis-)advantage of starting from the state $s^{\prime}$ rather
than $s$ under policy $\pi$. Denote
$sp(h^{\pi})\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\max_{s}h^{\pi}(s)-\min_{s}h^{\pi}(s)$.
We have the following useful propositions.

######  Proposition 1 (Theorem 8.2.6 of [35]).

For any policy $\pi=d^{\infty}\in\Pi^{\text{SR}}$, the gain $g^{\pi}$ and bias
$h^{\pi}$ satisfy the following system of _Bellman evaluation equations_ :

$g=P_{d}g\ \text{and}\ h+g=L_{d}h$ (5)

where $L_{d}h\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}r+P_{d}h$.
Conversely, if $(g,h)\in\mathbb{R}\times\mathbb{R}^{S}$ is a solution to (5),
then $g=g^{\pi}$ and $h=h^{\pi}+u$ where $u=P_{d}u$. Finally, if $P_{d}h=0$,
then $h=h^{\pi}$.

######  Proposition 2 (Chapter 9 of [35] and Theorem 1 of [36]).

Let $M$ be a weakly communicating MDP and denote $\Pi^{*}\in\Pi^{\text{SD}}$
be the set of policies maximizing (1). If any of the following assumptions
hold:

  * •

the action space $A$ is _finite_ ,

  * •

$\Pi^{*}\neq\emptyset$, and $\sup_{\pi\in\Pi^{*}}<+\infty$,

then there exists a solution $(g^{*},h^{*})\in\mathbb{R}\times\mathbb{R}^{S}$
to be the fixed point equation $h^{*}+g^{*}e=Lh^{*}$, where $e$ denotes an
all-one vector. Moreover, for any such solution $(g^{*},h^{*})$ and for all
$s\in\mathcal{S}$,

$g^{*}=\max_{\pi\in\Pi}\left\\{\liminf_{T\rightarrow+\infty}\mathbb{E}_{s}^{\pi}\left[\frac{1}{T}\sum_{t=1}^{T}r(s_{t},a_{t})\bigg{|}s_{1}\sim\mu_{1}\right]\right\\}$
(6)

Finally, any stationary policy $\pi^{*}=(d^{*})^{\infty}$ satisfying
$d^{*}\in\arg\max_{d}\\{r_{d}+P_{d}h^{*}\\}$ (i.e., greedy policy) is optimal,
i.e., $\pi^{*}\in\Pi^{*}$.

Notably, [35] shows that the optimal average reward $g^{*}$ in communicating
MDPs is independent of the initial state $s_{1}$ and cannot be increased when
using non-stationary policies.

######  Proposition 3 (Theorem 9.4.5 of [35] and extension by Theorem 7 of
[23]).

Consider the sequences of vectors $(v_{n})_{n\in\mathbb{N}}$ and Markov
decision rules $(d_{n})_{n\in\mathbb{N}}$ obtained while executing the value
interactions in Alg. 1. If Prop. 2 holds and either of the following
conditions:

  * •

every average optimal stationary deterministic policy has an aperiodic
transition matrix,

  * •

the transition matrices $P_{d_{n}}$ are aperiodic for all $n\geq 1$

for all $n\geq 1$, then there exists $h^{*}\in\mathbb{R}^{S}$ such that the
limit of the value function $\lim_{n\rightarrow\infty}v_{n}=h^{*}$ (where $v$
is defined using operators $L:\mathbb{R}^{S}\rightarrow\mathbb{R}^{S}$ as
$Lv\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\max_{d\in
D^{\text{MR}}}\\{r_{d}+P_{d}v\\}$) and $Lh^{*}=h^{*}+g^{*}e$, where $e$
denotes a all-one vector.

Algorithm 1 (Relative) Value Iteration

Input: Operators $L:\mathbb{R}^{S}\rightarrow\mathbb{R}^{S}$ as
$Lv\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\max_{d\in
D^{\text{MR}}}\\{r_{d}+P_{d}v\\}$ and $G:\mathbb{R}^{S}\rightarrow D$ as
$Gv\in\arg\max_{d\in D^{\text{MR}}}\\{L_{d}v\\}$, accuracy
$\epsilon\in(0,r_{\max})$, initial vector $v_{0}\in\mathbb{R}^{S}$, arbitrary
reference state $s\in\mathcal{S}$,

1:Initialize $n=0$,
$v_{1}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}Lv_{0}$

2:while $sp(v_{n+1}-v_{n})>\epsilon$ do $\triangleright$ Loop until
termination

3: Increment $n\leftarrow n+1$

4: Update $v_{n}\leftarrow v_{n}-v_{n}(\bar{s})e$ $\triangleright$ Avoids
numerical instability ($v_{n}\nrightarrow\infty$)

5:
$(v_{n+1},d_{n})\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}(Lv_{n},Gv_{n})$
$\triangleright$ $Lv_{n}$ and $Gv_{n}$ can be computed simultaneously

6:end while

7:Set
$g\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\frac{1}{2}\max\\{v_{n+1}-v_{n}\\}+\min\\{v_{n+1}-v_{n}\\})$,
$h\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}v_{n}$ and
$\pi\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}(d_{n})^{\infty}$.

Output: Gain $g\in[0,r_{\max}]$, bias vector $h\in\mathbb{R}^{S}$ and
stationary deterministic policy $\pi\in\Pi^{\text{SD}}$.

Also, the operator $L$ is denoted as the optimal Bellman operator. Finally,
$D=\max_{s\neq s^{\prime}}\\{\tau(s\rightarrow s^{\prime})\\}$ denotes the
diameter of $M$, where $\tau(s\rightarrow s^{\prime})=\inf\\{t\geq
1:s_{t}=s^{\prime}|s\\}$ is the minimal expected steps required from $s$ to
$s^{\prime}$. Furthermore, for all $s\in\mathcal{S}$ and the related value
function $v\in\mathbb{R}^{S}$, we define the extended optimal Bellman operator
with aperiodic transformation (Proposition 8.5.8, [35]) as

$\displaystyle L^{\alpha}_{k}v(s)$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\max_{a\in\mathcal{A}_{s}}\left\\{\max_{r\in
B_{r}^{k}(s,a)}\\{r\\}+\alpha\cdot\max_{p\in
B_{p}^{k}(s,a)}\left\\{p^{T}v\right\\}\right\\}+(1-\alpha)\cdot v(s)$ (7)

where $\alpha$ is the coefficient of the aperiodic transformation. By
properties of the aperiodic transformation, the optimal gains of
$\mathcal{M}_{k}^{\alpha}$ and $\mathcal{M}_{k}$ are equal (denoted by
$g_{k}^{*}$). The aperiodic transformation makes the extended value iteration
in Alg. 1 meet the condition in Prop. 3. Also, as shown by Prop. 8.5.8 of
[35], this transformation does not affect the gain of any stationary policy.
In other words, for any $\pi\in\Pi^{\text{SR}}$,
$g^{\alpha,\pi}=g^{\pi}$333The transformation introduced by (Section 8.5.4,
[35]) is slightly diﬀerent as the rewards are all multiplied by $\alpha$.
Therefore, Proposition 8.5.8 of [35] states that the gain is also multiplied
by $\alpha$. i.e., $g^{\alpha,\pi}=\alpha\cdot g^{\pi}$. However, it is
straightforward to adapt the proof of Proposition 8.5.8 of [35] to our case..

######  Proposition 4 (Theorem 4 of [24]).

Let $M$ be a communicating MDP with non-negative rewards and $(g^{*},h^{*})$ a
solution of the Bellman optimality equation (i.e., $Lh^{*}=h^{*}+g^{*}e$). For
any states $s$ and $s^{\prime}$ and any stationary policy
$\pi\in\Pi^{\text{SR}}$, we have

$\displaystyle h^{*}(s^{\prime})-h^{*}(s)\leq
g^{*}\mathbb{E}^{\pi}[\tau(s^{\prime}-1)|s].$ (8)

Proposed in Chapter 2, [37], the stochastic shortest path helps to understand
the difficulty for an agent to navigate between the states of an MDP. Let us
consider an MDP
$M^{\prime}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\\{\mathcal{S},\mathcal{A},p,r^{\prime}\\}$
with identical state and action space, and transition probabilities as the
true MDP $M$ but a reward
$r^{\prime}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}-r$ for all
state-action pairs, which could be further interpreted as the required time or
distance before reaching the next state in the MDP. The goal of the stochastic
shortest path problem is to find the shortest expected distance between states
$s$ and $s^{\prime}$ in the MDP, that is,

$\displaystyle\sup\limits_{\pi\in\Pi}\bigg{\\{}\mathbb{E}^{\pi}\big{[}\sum_{t=1}^{\tau(s^{\prime})-1}r^{\prime}\big{|}s\big{]}\bigg{\\}}$
(9)

Though (9) appears quite different from the original problem in (1), these two
problems are related through the Bellman optimality equation with the shortest
path problem is regarded as finding a bias-optimal policy with the optimal
gain $g^{*}=0$, thus re-writing the optimality equation as $Lh^{*}=h^{*}$. We
have the following proposition.

######  Proposition 5 (Proposition 2.8 of [20]).

Let
$M^{\prime}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\\{\mathcal{S},\mathcal{A},p,r^{\prime}\\}$
be communicating MDP (finite or compact $\mathcal{A}$) with
$r^{\prime}\in[-r_{\max},0]$ for all $(s,a)\in\mathcal{S}\times\mathcal{A}$.
For any state $s\in\mathcal{S}$, consider the _Bellman shortest path operator_
$L_{\mapsto s}:\mathbb{R}^{S}\mapsto\mathbb{R}^{S}$ defined for all
$v\in\mathbb{R}^{S}$ as $\forall x\in\mathcal{S}$, we have (12), and define
$h_{\mapsto s^{\prime}}^{*}$ as the (component-wise) maximal non-positive
solution of the Bellman shortest path optimality equation $L_{\mapsto
s^{\prime}}h_{\mapsto s^{\prime}}^{*}=h_{\mapsto s^{\prime}}^{*}$. Moreover,
if $d_{\mapsto s^{\prime}}^{*}$ is a greedy decision rule with respect to
$h_{\mapsto s^{\prime}}^{*}$, namely, $d_{\mapsto
s^{\prime}}^{*}=\arg\max_{a\in\mathcal{A}_{s}}\left\\{r^{\prime}(s,a)+\sum_{y\in
S}p(y|s,a)h_{\mapsto s^{\prime}}^{*}(y)\right\\}$ for all $s\neq s^{\prime}$,
then $\pi_{\mapsto
s^{\prime}}^{*}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}(d_{\mapsto
s^{\prime}}^{*})^{\infty}$ is an optimal solution to (9).

$\displaystyle L_{\mapsto
s^{\prime}}v(s)\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\left\\{\begin{array}[]{ll}\max_{a\in\mathcal{A}_{s}}\left\\{r(s,a)+\sum_{y\in
S}p(y|s,a)v(y)\right\\}&\text{ if }s\neq s^{\prime}\\\ v(s)&\text{ otherwise
}\end{array}\right.$ (12)

######  Proposition 6 (Theorem 7.3.2. of [35]).

Let
$M^{\prime}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\\{\mathcal{S},\mathcal{A},p,r^{\prime}$
be communicating MDP (finite or compact $\mathcal{A}$) with negative rewards
$r^{\prime}$. For any state $s\in\mathcal{S}$, consider the Bellman shortest
path operator $L_{\mapsto s}$ in (12) with maximal non-positive fixed point
$h_{\mapsto s}^{*}$ in Prop. 5. If there exists $h\in\mathbb{R}^{S}$ such that
$h\leq 0$ and $L_{\mapsto s}h\geq h$, then $h_{\mapsto s}^{*}\geq h$.

###  II-B Useful Concentration Inequalities

Ihe the following, we will repeatedly use the following concentration
inequalities.

######  Proposition 7 (Hoeffding Inequality, Theorem 2.8 of [38]).

Let $(X_{i})_{1\leq i\leq n}$ be a collection of independent random variables
subject to $i\in{1,\cdots,n}$, $\mathbb{P}(X_{i}\in[a_{i},b_{i}])=1$, and
$\mathbb{E}[X_{i}]=\mu_{i}$, then with a probability at least $1-\delta$ it
holds that

$\bigg{|}\sum_{i=1}^{n}(X_{i}-\mu_{i})\bigg{|}\leq\sqrt{\frac{1}{2}\sum_{i=1}^{n}(b_{i}-a_{i})^{2}\ln\bigg{(}\frac{2}{\delta}\bigg{)}}$
(13)

######  Proposition 8 (Azuma’s inequality).

Let $(X_{n},\mathcal{F}_{n})_{n\in\mathbb{N}}$ be a Martingale difference
sequence (MDS) such as $|X_{n}|\leq a$ almost sure for all $n\in\mathbb{N}$.
Then for all $\delta\in(0,1]$,

$\mathbb{P}\left(\sum_{i=1}^{n}X_{i}\geq
a\sqrt{2n\ln\left(\frac{1}{\delta}\right)}\right)\leq\delta$ (14)

######  Proposition 9 (Emperical Bernstein’s Inequality, Theorem 1 of [34]).

Let $(X_{i})_{1\leq i\leq n}$ be a collection of independent identical
distributed random variables subject to $i\in{1,\cdots,n}$,
$\mathbb{P}(X_{i}\in[a,b])=1$, and $\mathbb{E}[X_{i}]=\mu$, then with a
probability at least $1-\delta$ it holds that

$\bigg{|}\frac{1}{n}\sum_{i=1}^{n}(X_{i}-\mu_{i})\bigg{|}\leq\sqrt{\frac{2V_{n}(X)\ln(3/\delta)}{n}}+\frac{3(b-a)\ln(3/\delta)}{n}$
(15)

where $V_{n}(X)$ is the probability variance444Notably, the probability
variance is not an unbiased estimator while the sample variance
$V_{n}^{\prime}(X)\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\frac{1}{n}\sum_{i=1}^{n-1}\left(X_{i}-\frac{1}{n}\sum_{i=1}^{n}X_{i}\right)^{2}$
is unbiased.
$V_{n}(X)\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\frac{1}{n}\sum_{i=1}^{n}\left(X_{i}-\frac{1}{n}\sum_{i=1}^{n}X_{i}\right)^{2}$.

##  III Problem Formulation and VB-UCRL Solution

###  III-A Problem Formulation

In the problem setting, we consider the underlying MDP contains both
endogeneous and exogeneous uncertainty. Specifically, the mean rewards and
transition probabilities depend on the current step $t$, which are denoted as
$r_{t}(s,a)$ and $p_{t}(s^{\prime}|s,a)$ respectively. Accordingly, the time-
heterogeneous MDP at step $t$ can be written as
$M_{t}=<\mathcal{S},\mathcal{A},r_{t},p_{t},s_{1}>$. All MDPs $M_{t}$ are
communicating with diameter $D_{t}\leq D$, where $D$ denotes a common upper
bound.

Let $M_{t}$ be the true MDP. We consider the learning problem where
$\mathcal{S}$, $\mathcal{A}$ and $r_{\max}$ are known, where reward $r_{t}$
and transitions $p_{t}$ are unknown and need to be estimated online. We try to
evaluate the performance of a learning algorithm $\mathfrak{A}$ after $T$
time-steps by its cumulative regret

$\Delta(\mathfrak{A},T)=v^{*,T}(s_{1})-\sum_{t=1}^{T}r_{t}(s_{t},a_{t})$ (16)

where $v^{*,T}(s_{1})$ denotes the optimal $T$-step average reward starting
from $s_{1}$555Interesting readers could refer to Page 338 of [35] for the
relationship between $v$ and $h$..

We assume that the _variations_ in mean rewards and transition probabilities
are bounded in the $T$ steps.
$V^{T}_{r}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum_{t=1}^{T-1}\max_{s,a}|r_{t+1}(s,a)-r_{t}(s,a)|$,
and
$V_{T}^{p}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum_{t=1}^{T-1}\max_{s,a}\|\bar{p}_{t+1}(\cdot|s,a)-\bar{p}_{t}(\cdot|s,a)\|_{1}$.

###  III-B Variation-aware Bernstein-based Upper Confidence Reinforcement
Learning (VB-UCRL)

For RL in the changing MDP settings, we propose the variation-aware Bernstein-
based upper confidence reinforcement learning (VB-UCRL), which is a variant of
UCRL2 [23], implements the paradigm of “optimism in the face of uncertainty”
and constructs MDPs in confidence interval based on the empirical Bernstein
inequality in Prop. 9 [34] rather than the Hoeffding inequality for UCRL2 in
Prop. 7 [38].

VB-UCRL proceeds through episodes $k=1,2,\cdots$. Without loss of generality,
$t_{k}$ is the starting time of episode $k$. $N_{k}(s,a)$ is the number of
visits in $(s,a)$ before episode $k$. Here, VB-UCRL enters into a new episode
$k+1$ after once there exists one state-action pair $(s,a)$ having just been
played satisfies $\nu_{k}(s,a)=N_{k}^{+}(s,a)$, where $\nu_{k}(s,a)$ denotes
the number of visits to $(s,a)$ in episode $k$ and
$N_{k}^{+}(s,a)=\max\\{1,N_{k}(s,a)\\}$. For episode $k+1$, for all state-
action pairs, $N_{k+1}(s,a)=N_{k}(s,a)+\nu_{k}(s,a)$. Besides, $t_{k}$ is
defined as the starting time of episode $k$, that is,
$t_{k+1}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\inf\bigg{\\{}T\geq
t>t_{k}:\sum_{\tau=1}{t-1}\mathbbm{1}\\{(s_{\tau},a_{\tau})=(s_{t},a_{t})\\}\geq\max\big{\\{}1,2\mathbbm{1}\\{(s_{\tau},a_{\tau})=(s_{t},a_{t})\\}\big{\\}}\bigg{\\}}$
and $t_{1}=1$.

At the beginning of each episode $k$, VB-UCRL computes a set $\mathcal{M}$ of
statistically plausible MDPs given the observations so far, that is,

$\displaystyle\mathcal{M}_{k}=$
$\displaystyle\bigg{\\{}M=<\mathcal{S},\mathcal{A},\tilde{r},\tilde{p}>:\tilde{r}(s,a)\in\mathcal{B}_{r}^{k}(s,a),$
(17)
$\displaystyle\quad\tilde{p}(s,a)\in\mathcal{B}_{p}^{k}(s,a),\sum_{s^{\prime}}\tilde{p}(s^{\prime}|s,a)=1\bigg{\\}},$

where $\mathcal{B}_{r}^{k}$ and $\mathcal{B}_{p}^{k}$ are high-probability
(adapted) confidence intervals on the rewards and transition probabilities of
the true MDP $M$. Specifically,

$\displaystyle\mathcal{B}_{p}^{k}(s,a,s^{\prime})=[0,1]\cap\left[\hat{p}(s^{\prime}|s,a)-\beta_{p,k}^{sas^{\prime}}-\hat{V}_{p},\hat{p}(s^{\prime}|s,a)+\beta_{p,k}^{sas^{\prime}}+\hat{V}_{p}\right]$
(18)

where $\hat{p}$ is set as an estimate of transitions, that is,

$\hat{p}_{k}(s,a)=\frac{1}{N_{k}(s,a)}\sum_{t=1}^{t_{k}-1}\mathbbm{1}\\{(s_{t},a_{t})=(s,a)\\}$
(19)

and $\hat{V}_{p}\leq V_{p}^{T}$ is an estimate over the variations on the
transition probabilities. Moreover, using empirical Bernstein inequality [34],

$\displaystyle\beta_{p,k}^{sas^{\prime}}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}$
$\displaystyle
2\sqrt{\frac{\hat{\sigma}_{p,k}^{2}(s^{\prime}|s,a)}{N_{k}^{+}(s,a)}\ln\big{(}\frac{6SAN_{k}^{+}(s,a)}{\delta}\big{)}}+\frac{6\ln\big{(}\frac{6SAN_{k}^{+}(s,a)}{\delta}\big{)}}{N_{k}^{+}(s,a)}$
(20)

where $\delta\in(0,1)$. Similarly,

$\mathcal{B}_{r}^{k}(s,a)=\left[\hat{r}(s,a)-\beta_{r,k}^{sa}-\hat{V}_{r},\hat{r}(s,a)+\beta_{r,k}^{sa}+\hat{V}_{r}\right]\cap[0,r_{\max}]$
(21)

where

$\displaystyle\beta_{r,k}^{sa}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}$
$\displaystyle
2\sqrt{\frac{\hat{\sigma}_{r,k}^{2}(s,a)}{N_{k}^{+}(s,a)}\ln\big{(}\frac{6SAN_{k}^{+}(s,a)}{\delta}\big{)}}+\frac{6r_{\max}\ln\big{(}\frac{6SAN_{k}^{+}(s,a)}{\delta}\big{)}}{N_{k}^{+}(s,a)}$
(22)

and $\hat{V}_{r}$ is an estimate over the variations on the mean rewards.
$\hat{r}_{k}$ is the empirical average of rewards, namely

$\hat{r}_{k}(s,a)=\frac{1}{N_{k}(s,a)}\sum_{t=1}^{t_{k}-1}\mathbbm{1}\\{(s_{t},a_{t})=(s,a)\\}\cdot
r_{t}$ (23)

The estimated transition probability $\hat{p}_{k}(s^{\prime}|s,a)$ corresponds
to the sample mean of independent identical Bernouilli random variable with
mean $p(s^{\prime}|s,a)$ and the population variance can be approximately
computed as
$\hat{\sigma}_{p,k}^{2}(s^{\prime}|s,a)=\hat{p}_{k}(s^{\prime}|s,a)(1-\hat{p}_{k}(s^{\prime}|s,a))$.
The population variance of the reward can be computed recursively at the end
of every episode as

$\displaystyle\hat{\sigma}_{r,k+1}^{2}(s,a)$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\frac{1}{N_{k+1}^{+}(s,a)}\left(\sum_{l=1}^{k}S_{l}(s,a)\right)-\left(\hat{r}_{k+1}(s,a)\right)^{2}$
$\displaystyle=\frac{N_{k}(s,a)}{N_{k+1}^{+}(s,a)}\left(\hat{\sigma}_{r,k}^{2}(s,a)+\left(\hat{r}_{k}(s,a)\right)^{2}\right)+\frac{S_{k}(s,a)}{N_{k+1}^{+}(s,a)}-\left(\hat{r}_{k+1}(s,a)\right)^{2}$
(24)

where
$S_{k}(s,a)\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum_{t=1}^{t_{k}-1}\mathbbm{1}\\{(s_{t},a_{t})=(s,a)\\}\cdot
r_{t}^{2}$. As pointed out by Section 3.1.1 of [23], any bounded parameter MDP
can be equivalently represented by an extended MDP $\tilde{M}_{k}^{+}$, by
combining all plausible MDPs constructed above into a single MDP with
identical state space $\mathcal{S}$ but with an extended compact action space
$\mathcal{A}^{+}=\cup_{a\in\mathcal{A}_{s}}{a}\times B_{r}(s,a)\times
B_{p}(s,a)$.

Moreover, the extended greedy operator is defined as

$G_{k}v(s)\in\underset{a\in\mathcal{A}_{s}}{\max}\left\\{\max_{r\in
B_{r}^{k}(s,a)}r+\max_{p\in B_{p}^{k}(s,a)}p^{T}v\right\\}$ (25)

Afterwards, VB-UCRL chooses an optimistic MDP $M_{k}$ (with respect to the
achievable average reward) among these plausible MDPs $\mathcal{M}_{k}$, and
executes a policy $\pi_{k}$ which is (nearly) optimal for the optimistic MDP
$M_{k}$, that is,

$\max_{\pi\in\Pi^{\mathrm{SD}}}\left\\{\sup_{M^{\prime}\in\mathcal{M}_{k}}g_{M^{\prime}}^{\pi}\right\\}=\sup_{M^{\prime}\in\mathcal{M}_{k}}\left\\{\max_{\pi\in\Pi^{\mathrm{SD}}}g_{M^{\prime}}^{\pi}\right\\}=\sup_{M^{\prime}\in\mathcal{M}_{k}}g_{M^{\prime}}^{*}$
(26)

######  Proposition 10 (Proposition 2.7 of [20]).

Consider the gain $g$ and bias $h$ returned by Alg. 1. Under the same
assumptions as Prop. 3, $|g-g^{*}|\leq\epsilon/2$ and for all
$s\in\mathcal{S}$, $|Lh(s)-h(s)-g|\leq\epsilon$, where
$\epsilon\in(0,r_{\max})$ is the accuracy given as input of Alg. 1.

By Prop. 10, if we run extended value iteration in Alg. 1 on $M_{k}^{+}$ with
accuracy $\epsilon_{k}=r_{\max}/t_{k}$, we have that

$|g_{k}-g_{k}^{*}|\leq\epsilon_{k}/2=\frac{r_{\max}}{2t_{k}}$ (27)

and

$\|L^{\alpha}_{k}h_{k}-h_{k}-g_{k}e\|_{\infty}\leq\epsilon_{k}=\frac{r_{\max}}{t_{k}}$
(28)

where
$(g_{k},h_{k},\pi_{k})=EVI(L_{k}^{\alpha},G_{k}^{\alpha},\frac{r_{\max}}{t_{k}},0,s_{1})$.
$r_{k}$ and $p_{k}$ are denoted as the optimistic reward and transitions at
episode $k$.

We first summarize the VB-UCRL without variation-aware restarts as Alg. 2.

Algorithm 2 VB-UCRL without Variation-Aware Restarts

Input: Confidence $\delta\in(0,1)$, $r_{\max}$, $\mathcal{S}$,
$\mathcal{A}^{+}$.

1:Initialize $t\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}1$ and
observe $s_{1}$ and for any
$\left(s,a,s^{\prime}\right)\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$:
$N_{1}(s,a)=0$, $\hat{p}_{1}\left(s^{\prime}|s,a\right)=0$,
$\hat{r}_{1}(s,a)=0$, $\hat{\sigma}_{p,1}^{2}\left(s^{\prime}|s,a\right)=0$,
$\hat{\sigma}_{r,1}^{2}(s,a)=0$.

2:for episodes $k=1,2,\ldots$ do

3: Set $t_{k}\leftarrow t$ and episode counters $\nu_{k}(s,a)\leftarrow 0$.

4: Compute the upper-confidence bounds (18) and (21) and the extended MDP
$\mathcal{M}_{k}^{+}$ as in (17).

5: Compute an $r_{\max}/t_{k}$-approximation $\pi_{k}$ of (26)
$(g_{k},h_{k},\pi_{k})=EVI\left(\mathcal{L}^{\alpha}_{k},\mathcal{G}^{\alpha}_{k},\frac{r_{\max}}{t_{k}},0,s_{1}\right)$.

6: Sample action $a_{t}\sim\pi_{k}\left(\cdot|s_{t}\right)$.

7: while $t_{k}=t$ or
$\nu_{k}\left(s_{t},a_{t}\right)\leq\max\left\\{1,N_{k}\left(s_{t},a_{t}\right)\right\\}$
do

8: Execute $a_{t},$ obtain reward $r_{t},$ and observe $s_{t+1}$.

9: Sample action $a_{t+1}\sim\pi_{k}\left(\cdot|s_{t+1}\right)$.

10:
$\operatorname{Set}\nu_{k}\left(s_{t},a_{t}\right)\leftarrow\nu_{k}\left(s_{t},a_{t}\right)+1$
and set $t\leftarrow t+1$.

11: end while

12: $\operatorname{Set}N_{k+1}(s,a)\leftarrow N_{k}(s,a)+\nu_{k}(s,a)$.

13: Update statistics (i.e.,
$\left(\hat{p}_{k+1},\hat{r}_{k+1},\hat{\sigma}_{p,k+1}^{2},\hat{\sigma}_{r,k+1}^{2}\right)$.

14:end for

Next, we can formally give VB-UCRL in Alg. 3. In particular, we restart Alg. 2
in phases by continuously tuning the confidence parameter
$\frac{\delta}{2t^{2}}$ according to a schedule dependent on the variations.

Algorithm 3 VB-UCRL with Restarts

Input: State space $\mathcal{S}$, action space $\mathcal{A}$, confidence
parameter $\delta$, variation terms $V_{r}^{T}$ and $V_{p}^{T}$.

1:Initialization: Set current time step
$\tau\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}1$.

2:for phase $i=1,2,\ldots$ do

3: Perform VB-UCRL in Algorithm 2 with confidence parameter
$\delta/2{\tau}^{2}$ for
$\theta_{i}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\lceil\frac{i^{2}}{(2V_{r}^{T}+V_{p}^{T})^{2}}\rceil$
steps.

4: Update $\tau\leftarrow\tau+\theta_{i}$.

5:end for

##  IV Fundamental Limit of VB-UCRL

In Section, we first derive the upper regret bound of VB-UCRL without
variation-aware restarts and then extend it to VB-UCRL with restarts.

###  IV-A Upper Regret Bound of VB-UCRL without Variation-Aware Restarts

The following theorem gives the limits of regret bound in (16) for VB-UCRL
without variation-aware restarts666For simplicity of representation, in this
part, we slightly abuse the notations for VB-UCRL with and without variation-
aware restarts..

######  Theorem 1.

There exists a numerical constant $\beta>0$ such that for any communicating
MDP, if $\hat{V}_{p}$ and $\hat{V}_{r}$ are set as the true values $V_{p}^{T}$
and $V_{r}^{T}$, with probability at least $1-\delta$, it holds that for all
initial state distributions $\nu_{1}\in\Delta_{s}$ ($\Delta_{s}$ denotes a
$S$-dimensional simplex.) and for all time horizons $T\geq SA$

$\displaystyle\Delta(\text{VB-UCRL},T)\leq$ (29)
$\displaystyle\max(r_{\max},Dr_{\max})\bigg{(}86\sqrt{T\ln\big{(}\frac{T}{\delta}\big{)}\sum_{s,a}\Gamma(s,a)}+144S^{2}A\ln\big{(}\frac{T}{\delta}\big{)}\ln(T)\bigg{)}+Dr_{\max}TV_{p}^{T}+2TV_{r}^{T}$

where
$\Gamma(s,a)\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\|p(\cdot|s,a)\|_{0}=\sum_{s^{\prime}\in\mathcal{S}}\mathbbm{1}\\{p(s^{\prime}|s,a)>0\\}$
and
$\Gamma\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\max_{s,a\in\mathcal{S}\times\mathcal{A}}\Gamma(s,a)$.

###### Proof.

By Lemma 1, which shows that under the event where the true MDP falls into the
scope of plausible MDPs, the $T$-step reward in the changing MDP settings
could be bounded by the optimistic average reward $g^{*}$. So, we have

$\displaystyle\Delta(\text{VB-UCRL},T)$ $\displaystyle=$ $\displaystyle
v^{*,T}(s_{1})-\sum_{t=1}^{T}r_{t}(s_{t},a_{t})$ (30) $\displaystyle\leq$
$\displaystyle\sum_{t=1}^{T}\big{(}g^{*}-r_{t}(s_{t},a_{t}))\big{)}+Dr_{\max}$

where
$g^{*}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\min_{k}g^{*}_{k}$,
and
$g^{*}_{k}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\max_{\pi,M\in\mathcal{M}_{k}}g^{*}_{k}(M)$.

By Lemma 2, which can be interpreted as removing all the randomness due to the
stochasticity of the observed rewards and the executed policy, at the expense
of $\tilde{\mathcal{O}}(\sqrt{T})$, with a probability at least
$1-\frac{\delta}{6}$, $\Delta(\text{VB-UCRL},T)$ could be rewritten as

$\displaystyle\Delta(\text{VB-
UCRL},T)\leq\sum_{t=1}^{T}\big{(}g^{*}-r_{t}(s_{t},a_{t})\big{)}$
$\displaystyle\leq\sum_{t=1}^{T}\bigg{(}g^{*}-\sum_{a\in
A_{s_{t}}}\pi_{k_{t}}(s_{t},a)r(s_{t},a)\bigg{)}+2r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}$
(31)
$\displaystyle=\sum_{t=1}^{k_{T}}\sum_{s\in\mathcal{S}}\nu_{k}(s)\bigg{(}g^{*}-\sum_{a\in
A_{s}}\pi_{k}(a|s)r(s,a)\bigg{)}+2r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}$
$\displaystyle\overset{(a)}{=}\sum_{t=1}^{k_{T}}\Delta_{k}+2r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}$

where the equation $(a)$ comes after
$\Delta_{k}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum_{s\in\mathcal{S}}\nu_{k}(s)\bigg{(}g^{*}-\sum_{a\in
A_{s}}\pi_{k}(a|s)r(s,a)\bigg{)}$, and
$k_{t}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sup\\{k\geq 1:t\geq
t_{k}\\}$ denotes the integer-valued random variable indexing the current
episode at time $t$. By Prof. 15, $k_{T}\leq
SA\log_{2}\big{(}\frac{8T}{SA}\big{)}$ is bounded for $T\geq SA$.

Next, we derive the bound for $\Delta_{k}$ with a high probability. By Lemma
3, if the true MDP falls into the scope of plausible MDPs
($M\in\mathcal{M}_{k},\forall k$), $\Delta_{k}$ could be upper bounded by

$\Delta_{k}\leq\Delta_{k}^{p}+\Delta_{k}^{r}+\frac{3\epsilon_{k}}{2}\sum_{s\in\mathcal{S}}\nu_{k}(s)$
(32)

where

$\Delta_{k}^{p}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\alpha\sum\limits_{s\in\mathcal{S}}\nu_{k}(s)\bigg{(}\sum\limits_{\begin{subarray}{c}a\in\mathcal{A}_{s}\\\
s^{\prime}\in\mathcal{S}\end{subarray}}\pi_{k}(a|s)p_{k}\big{(}s^{\prime}|s,a\big{)}h_{k}\big{(}s^{\prime}\big{)}-h_{k}(s)\bigg{)}$

and

$\Delta_{k}^{r}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum\limits_{s\in\mathcal{S}}\sum\limits_{a\in\mathcal{A}_{s}}\nu_{k}(s)\pi_{k}(a|s)\big{(}r_{k}(s,a)-r(s,a)\big{)}.$

We further decompose $\Delta_{k}^{p}$ into two parts
$\Delta_{k}^{p}=\Delta_{k}^{p1}+\Delta_{k}^{p2}$, where

$\Delta_{k}^{p1}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\alpha\sum\limits_{s,a,s^{\prime}}\nu_{k}(s)\pi_{k}(a|s)\bigg{(}p_{k}\big{(}s^{\prime}|s,a\big{)}-p\big{(}s^{\prime}|s,a\big{)}\bigg{)}h_{k}\big{(}s^{\prime}\big{)}$

and

$\Delta_{k}^{p2}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\alpha\sum\limits_{s}\nu_{k}(s)\bigg{(}\sum\limits_{\begin{subarray}{c}a,s^{\prime}\end{subarray}}\pi_{k}(a|s)p\big{(}s^{\prime}|s,a\big{)}h_{k}\big{(}s^{\prime}\big{)}-h_{k}(s)\bigg{)},$

and bound them in Lemma 4, Lemma 5, and Lemma 6. Accordingly, with a
probability $1-\frac{\delta}{3}$,

$\displaystyle\sum\limits_{k=1}^{k_{T}}\Delta_{k}^{p}$ $\displaystyle\leq
Dr_{\max}\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\nu_{k}(s,a)(\beta_{p,k}^{sa}+V_{p}^{T})+6Dr_{\max}\sqrt{T\ln\big{(}\frac{6T}{\delta}\big{)}}+k_{T}Dr_{\max}$
(33) $\displaystyle\leq
Dr_{\max}\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\nu_{k}(s,a)\beta_{p,k}^{sa}+Dr_{\max}TV_{p}^{T}+6Dr_{\max}\sqrt{T\ln\big{(}\frac{6T}{\delta}\big{)}}+k_{T}Dr_{\max}$

where
$\beta_{p,k}^{sa}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum_{s^{\prime}}\beta_{p,k}^{sas^{\prime}}$.
Similarly, by Lemma 7, with probability at least $1-\frac{\delta}{6}$, we have

$\displaystyle\sum\limits_{k=1}^{k_{T}}\Delta_{k}^{r}\leq
4r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}+2\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\nu_{k}(s,a)\beta_{r,k}^{sa}+2TV_{r}^{T}$
(34)

As proved in Thm 3, the event that the true MDP falls into the scope of
plausible MDPs occurs with a probability at least $1-\frac{\delta}{3}$.
Merging (32), (33), (34) into (31), with a probability at least
$1-\frac{5\delta}{6}$, for all $T\geq SA$, we have (36) as

$\displaystyle\Delta(\text{VB-UCRL},T)$ $\displaystyle\leq
2r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}+\sum\limits_{k=1}^{k_{T}}\frac{3\epsilon_{k}}{2}\sum_{s}\nu_{k}(s)+Dr_{\max}\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\nu_{k}(s,a)\beta_{p,k}^{sa}+Dr_{\max}TV_{p}^{T}$
(35)
$\displaystyle\quad+6Dr_{\max}\sqrt{T\ln\big{(}\frac{6T}{\delta}\big{)}}+k_{T}Dr_{\max}$
$\displaystyle\quad+4r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}+2\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\nu_{k}(s,a)\beta_{r,k}^{sa}+2TV_{r}^{T}$
(36) $\displaystyle\leq
6r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}+6Dr_{\max}\sqrt{T\ln\big{(}\frac{6T}{\delta}\big{)}}+Dr_{\max}SA\log_{2}\big{(}\frac{T}{SA}\big{)}+Dr_{\max}TV_{p}^{T}+2TV_{r}^{T}$
$\displaystyle\quad+r_{\max}\sum\limits_{k=1}^{k_{T}}\frac{3}{2t_{k}}\sum_{s}\nu_{k}(s)+2\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\nu_{k}(s,a)\beta_{r,k}^{sa}+Dr_{\max}\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\nu_{k}(s,a)\beta_{p,k}^{sa}$

As for the last three terms in (36), we have

  * •

Since $t_{k}\geq N_{k}^{+}(s,a)$ for all $(s,a)$, we have

$\displaystyle
r_{\max}\sum\limits_{k=1}^{k_{T}}\frac{3}{2t_{k}}\sum_{s}\nu_{k}(s)=\frac{3r_{\max}}{2}\sum_{s,a}\sum\limits_{k=1}^{k_{T}}\frac{\nu_{k}(s,a)}{t_{k}}$
$\displaystyle\leq$
$\displaystyle\frac{3r_{\max}}{2}\sum_{s,a}\sum\limits_{k=1}^{k_{T}}\frac{\nu_{k}(s,a)}{N_{k}^{+}(s,a)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$
$\displaystyle\frac{3r_{\max}}{2}\sum_{s,a}2+2\ln\big{(}N_{k_{T}+1}^{+}(s,a)\big{)}$
(37) $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$
$\displaystyle\frac{3r_{\max}}{2}SA\bigg{(}2+2\ln\big{(}\frac{\sum_{s,a}N_{k_{T}+1}^{+}(s,a)}{SA}\big{)}\bigg{)}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}$
$\displaystyle\frac{3r_{\max}SA}{2}\bigg{(}2+2\ln\big{(}\frac{T}{SA}\big{)}\bigg{)}$
$\displaystyle\leq$ $\displaystyle 3r_{\max}SA\bigg{(}1+\ln T\bigg{)}$

where the equation $(a)$ comes from Prop. 13, while the inequality $(b)$
leverages the concavity of a logarithmic function and the Jensen inequality.
The equation $(c)$ is due to that $\sum_{s,a}N_{k+1}^{+}(s,a)\leq T$.

  * •

Taking account of the definition of $\beta_{r,k}^{sa}$,

$\displaystyle
2\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\nu_{k}(s,a)\beta_{r,k}^{sa}$
$\displaystyle=$ $\displaystyle
4\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\bigg{[}\nu_{k}(s,a)\sqrt{\frac{\hat{\sigma}_{r,k}^{2}(s,a)}{N_{k}^{+}(s,a)}\ln\big{(}\frac{6SAN_{k}^{+}(s,a)}{\delta}\big{)}}+3r_{\max}\ln\big{(}\frac{6SAN_{k}^{+}(s,a)}{\delta}\big{)}\frac{\nu_{k}(s,a)}{N_{k}^{+}(s,a)}\bigg{]}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$ $\displaystyle
4r_{\max}\sqrt{\ln\big{(}\frac{6SAT}{\delta}\big{)}}\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\bigg{[}\frac{\nu_{k}(s,a)}{\sqrt{N_{k}^{+}(s,a)}}\bigg{]}+12r_{\max}\ln\big{(}\frac{6SAT}{\delta}\big{)}\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\frac{\nu_{k}(s,a)}{N_{k}^{+}(s,a)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$ $\displaystyle
4r_{\max}\sqrt{\ln\big{(}\frac{6SAT}{\delta}\big{)}}\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\bigg{[}\frac{\nu_{k}(s,a)}{\sqrt{N_{k}^{+}(s,a)}}\bigg{]}+12r_{\max}\ln\big{(}\frac{6SAT}{\delta}\big{)}\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\frac{\nu_{k}(s,a)}{N_{k}^{+}(s,a)}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}$ $\displaystyle
12r_{\max}\sqrt{SAT\ln\big{(}\frac{6SAT}{\delta}\big{)}}+24r_{\max}SA\ln\big{(}\frac{6SAT}{\delta}\big{)}(1+\ln
T)$

where the equation $(a)$ comes from $\hat{\sigma}_{r,k}^{2}(s,a)\leq
r_{\max}^{2}$ and
$\ln\big{(}\frac{6SAN_{k}^{+}(s,a)}{\delta}\big{)}\leq\ln\big{(}\frac{6SAT}{\delta}\big{)}$,
the inequality $(b)$ comes from Prop. 13, and the inequality $(c)$ comes from
similar deduction as the previous term.

  * •

Similarly, by the definition of $\beta_{p,k}^{sa}$,

$\displaystyle
Dr_{\max}\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\nu_{k}(s,a)\beta_{p,k}^{sa}$
$\displaystyle\leq$ $\displaystyle
2Dr_{\max}\sqrt{\ln\left(\frac{6SAT}{\delta}\right)}\sum_{s,a}\sum_{k=1}^{k_{T}}\frac{\nu_{k}(s,a)}{\sqrt{N_{k}^{+}(s,a)}}\cdot\sum_{s^{\prime}\in
S}\sqrt{\widehat{p}_{k}\left(s^{\prime}\mid
s,a\right)\left(1-\hat{p}_{k}\left(s^{\prime}\mid s,a\right)\right)}$
$\displaystyle+6Dr_{\max}S\ln\left(\frac{6SAT}{\delta}\right)\sum_{s,a}\sum_{k=1}^{k_{T}}\frac{\nu_{k}(s,a)}{N_{t}^{+}(s,a)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}$ $\displaystyle
6Dr_{\max}\sqrt{\ln\left(\frac{6SAT}{\delta}\right)}\sum_{s,a}\sqrt{(\Gamma(s,a)-1)N_{k_{T}+1}(s,a)}$
$\displaystyle+12Dr_{\max}S^{2}A\ln\left(\frac{6SAT}{\delta}\right)(1+\ln T)$
(38) $\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}$ $\displaystyle
6Dr_{\max}\sqrt{\ln\left(\frac{6SAT}{\delta}\right)}\sqrt{\sum_{s,a}\Gamma(s,a)\sum_{s,a}N_{k_{T}+1}(s,a)}$
$\displaystyle+12Dr_{\max}S^{2}A\ln\left(\frac{6SAT}{\delta}\right)(1+\ln T)$
$\displaystyle\leq$ $\displaystyle
6Dr_{\max}\sqrt{\ln\left(\frac{6SAT}{\delta}\right)}\sqrt{\left(\sum_{s,a}\Gamma(s,a)\right)T}$
$\displaystyle+12Dr_{\max}S^{2}A\ln\left(\frac{6SAT}{\delta}\right)(1+\ln T)$

where the inequality $(a)$ comes from Prop. 13 while the inequality $(b)$
comes from Cauchy-Schwartz inequality.

In summary, (36) could be written as (39).

$\displaystyle\Delta(\text{VB-UCRL},T)$ $\displaystyle\leq
6r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}+6Dr_{\max}\sqrt{T\ln\big{(}\frac{6T}{\delta}\big{)}}+Dr_{\max}SA\log_{2}\big{(}\frac{8T}{SA}\big{)}+Dr_{\max}TV_{p}^{T}+2TV_{r}^{T}$
$\displaystyle\quad+3r_{\max}SA\bigg{(}1+\ln
T\bigg{)}+12r_{\max}\sqrt{SAT\ln\big{(}\frac{6SAT}{\delta}\big{)}}+24r_{\max}SA\ln\big{(}\frac{6SAT}{\delta}\big{)}(1+\ln
T)$ (39)
$\displaystyle\quad+6Dr_{\max}\sqrt{\ln\left(\frac{6SAT}{\delta}\right)}\sqrt{\left(\sum_{s,a}\Gamma(s,a)\right)T}+12Dr_{\max}S^{2}A\ln\left(\frac{6SAT}{\delta}\right)(1+\ln
T)$

By Prop. 16, (39) could be further simplified as

$\displaystyle\Delta(\text{VB-UCRL},T)$ $\displaystyle\leq$
$\displaystyle\max(r_{\max},Dr_{\max})\bigg{(}43\sqrt{T\ln\big{(}\frac{T}{\delta}\big{)}\sum_{s,a}\Gamma(s,a)}+72S^{2}A\ln\big{(}\frac{T}{\delta}\big{)}\ln(T)\bigg{)}+Dr_{\max}TV_{p}^{T}+2TV_{r}^{T}$

∎

###  IV-B Upper Regret Bound of VB-UCRL

######  Theorem 2.

After any $T$ steps, the regret of VB-UCRL with restarting in Algorithm 3 is
bounded by

$\displaystyle
155\max(r_{\max},Dr_{\max})(V_{r}^{T}+V_{p}^{T})^{1/3}T^{2/3}\cdot\sqrt{\ln\big{(}\frac{2T^{3}}{\delta}\big{)}\sum_{s,a}\Gamma(s,a)}$
(40) $\displaystyle\
+144\max(r_{\max},Dr_{\max})S^{2}A\ln\big{(}\frac{2T^{3}}{\delta}\big{)}\ln(2T^{3})$

###### Proof.

Inspired by the proof of Theorem 2 of [31], we write $V_{r}^{(i)}$ and
$V_{p}^{(i)}$ for the variation of rewards and transition probabilities in
Phase $i$ and abbreviate
$V^{(i)}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}V_{r}^{(i)}+2V_{p}^{(i)}$,
$V\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}2V_{r}+V_{p}$ and
$\theta_{i}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\lceil\frac{i^{2}}{V^{2}}\rceil$.

If the number of phases up to $T$ is $N$. We have

$\sum_{i=1}^{N-1}\lceil\frac{i^{2}}{V^{2}}\rceil<T\leq\sum_{i=1}^{N}\lceil\frac{i^{2}}{V^{2}}\rceil$
(41)

Recalling that $\sum_{i=1}^{N}i^{2}=\frac{1}{6}N(N+1)(2N+1)>\frac{1}{3}N^{3}$,
we have

$T>\sum_{i=1}^{N-1}\lceil\frac{i^{2}}{V^{2}}\rceil>\sum_{i=1}^{N-1}\frac{i^{2}}{V^{2}}>\frac{(N-1)^{3}}{3V^{2}}$
(42)

In other words, $N<1+\sqrt[3]{3V^{2}T}$.

Denoting $\tau_{i}$ as the initial step of phase $i$ and $s_{\tau_{i}}$ as the
state visited by the optimal T-step policy at step $\tau_{i}$, we can
decompose the regret as

$\displaystyle\Delta(\text{VB-UCRL},T)$
$\displaystyle=v_{T}^{*}\left(s_{1}\right)-\sum_{t=1}^{T}r_{t}$
$\displaystyle=\sum_{i=1}^{N}\left(\mathbb{E}\left[v_{\theta_{i}}^{*}\left(s_{\tau_{i}}\right)\right]-\sum_{t=\tau_{i}}^{\tau_{i}-1}r_{t}\right)$
(43)

By Theorem 1 and a union bound over all possible values for state
$s_{\tau_{i}}$, the $i$-th summand ($i=1,\cdots,N$) in (29) with probability
$1-\frac{\delta}{2(\tau^{i})^{2}}$ is bounded by

$\displaystyle\max(r_{\max},Dr_{\max})\bigg{(}86\sqrt{\ln\big{(}\frac{2T^{3}}{\delta}\big{)}\sum_{s,a}\Gamma(s,a)}\cdot\sqrt{\theta_{i}}$
$\displaystyle\quad+144S^{2}A\ln\big{(}\frac{2T^{3}}{\delta}\big{)}\ln(2T^{3})\bigg{)}+Dr_{\max}V^{(i)}\theta_{i}$

If $\sqrt[3]{3V^{2}T}<1$, we have $3V^{2}T<1$ and hence $3V^{2}T^{2}<T$ and
$VT<\sqrt{3}VT<\sqrt{T}$. Furthermore, in this case $N=1$ with $\theta_{1}=T$
and $V^{(1)}=V$, so the regret bound is

$\displaystyle\max(r_{\max},Dr_{\max})\bigg{(}86\sqrt{\ln\big{(}\frac{2T^{3}}{\delta}\big{)}\sum_{s,a}\Gamma(s,a)}\cdot\sqrt{T}$
$\displaystyle\quad+144S^{2}A\ln\big{(}\frac{2T^{3}}{\delta}\big{)}\ln(2T^{3})\bigg{)}+Dr_{\max}VT$
$\displaystyle=$ $\displaystyle
86\max(r_{\max},Dr_{\max})\sqrt{\ln\big{(}\frac{2T^{3}}{\delta}\big{)}\sum_{s,a}\Gamma(s,a)}\cdot\sqrt{T}$
$\displaystyle\
+Dr_{\max}VT+144\max(r_{\max},Dr_{\max})S^{2}A\ln\big{(}\frac{2T^{3}}{\delta}\big{)}\ln(2T^{3})$

which is upper bounded by the claimed regret bound.

On the other hand, if $\sqrt[3]{3V^{2}T}\geq 1$, then $N<2\sqrt[3]{3V^{2}T}$
and summing over all $N$ phases yields from (41) that with a probability
$\sum_{i}\frac{\delta}{2(\tau^{(i)})^{2}}<\sum_{t}\frac{\delta}{2t^{2}}<\delta$,
the regret is bounded by

$\displaystyle\max(r_{\max},Dr_{\max})\bigg{(}86\sqrt{\ln\big{(}\frac{2T^{3}}{\delta}\big{)}\sum_{s,a}\Gamma(s,a)}\cdot\sum_{i=1}^{N}\sqrt{\theta_{i}}$
$\displaystyle+144S^{2}A\ln\big{(}\frac{2T^{3}}{\delta}\big{)}\ln(2T^{3})\bigg{)}+Dr_{\max}\sum_{i=1}^{N}V^{(i)}(\frac{i^{2}}{V^{2}}+1)$

Noting that using Jensen’s inequality
$\sum_{i=1}^{N}\sqrt{\theta_{i}}\leq\sqrt{NT}\leq 1.7\cdot V^{1/3}T^{2/3}$ and
$\sum_{i=1}^{N}V^{(i)}(\frac{i^{2}}{V^{2}}+1)\leq\sum_{i=1}^{N}V^{(i)}(\frac{N^{2}}{V^{2}}+1)\leq\frac{N^{2}}{V}+V<8.33V^{1/3}T^{2/3}+V$,
we have the bound. ∎

##  V Discussions

To our best knowledge, [31] and [33] give the closest regret bound of RL in
MDP with both endogeneous and exogeneous uncertainty. In particular, [31]
shows that if we ignore logarithmic terms (i.e.,regarding the logarithmic
terms as a constant), up to a multiplicative numerical constant, the regret
bound of variation-aware UCRL in [31] is bounded by

$\tilde{O}\left(Dr_{\max}(V_{r}^{T}+V_{p}^{T})^{1/3}T^{2/3}S\sqrt{A}\right).$

Meanwhile, [33] shows that a regret bound of

$\tilde{O}\left(Dr_{\max}(V_{r}^{T}+V_{p}^{T})^{1/4}S^{2/3}A^{1/2}T^{3/4}\right).$

Similarly, taking account of $\sum_{s,a}\Gamma(s,a)\leq\Gamma SA$, the regret
bound of VB-UCRL could be

$\tilde{O}\left(Dr_{\max}(V_{r}^{T}+V_{p}^{T})^{1/3}T^{2/3}\sqrt{\Gamma
SA}\right)$

as in Theorem 1. Since by definition $\Gamma\leq S$, the regret bound of VB-
UCRL is no greater than that in [31]. However, as $\Gamma$ is usually equal to
$\mathcal{O}(1)$ and significantly smaller than $S$, our bound is superior
than [31] and [33]. In particular, it can save at most $\sqrt{S}$ than [31]
and $S^{\frac{1}{6}}T^{\frac{1}{12}}$ than [33], respectively.

##  VI Conclusion

In this paper, we studied the problem of online RL for MDP with both
endogeneous and exogeneous uncertainty, where the unknown reward and state
transition distributions vary within some variation budgets. We first proposed
a variation-aware Bernstein-based upper confidence reinforcement learning
algorithm. In particular, we allowed UCRL to restart according to a schedule
based on the variations, and replaced the commonly used Hoeffding inequality
by Bernstein inequality. Our approach achieved tighter regret bounds than
those in the literature. Given the wide application of RL, our approach could
contribute to the understanding of RL-based optimization performance.

## Appendix

###  VI-A Relationship between the True MDP and the Extended MDP

We use the Theorem 3.1 of [20] to establish the relationship between the true
MDP and the extended MDP.

######  Theorem 3 (Theorem 3.1 of [20]).

The probability that the true MDP $M$ does not belong to the set of plausible
MDPs $\mathcal{M}_{k}$ defined by (18) and (21) for any $k\geq 1$, is at most
$\frac{\delta}{3}$, that is,

$\mathbb{P}(\exists k\geq 1,s.t.M\notin\mathcal{M}_{k})\leq\frac{\delta}{3}$
(44)

###  VI-B Stochastic Shortest Path of the Extended MDP

As shown in Prop. 8.5.8 of [35], the aperiodic transformation does not affect
the gain of any stationary policy. In other words, for any
$\pi\in\Pi^{\text{SR}}$, $g^{\alpha,\pi}=g^{\pi}$. We next explain the impact
of aperiodic transformation on stochastic shortest path.

######  Proposition 11 (Theorem 2.1 of [20]).

Let time-homogeneous MDP $M$ satisfy the assumptions of Prop. 5. Let
$\alpha\in(0,1]$ and $M_{\alpha}$ be the MDP obtained after applying the
aperiodic transformation of parameter $\alpha$ to $M$, which satisfies the
assumptions of Prop. 5 as well. So, $h_{\mapsto s}^{\alpha*}$ is well-defined
for all $a\in\mathcal{S}$. Moreover, $\alpha\cdot h_{\mapsto
s}^{\alpha*}=h_{\mapsto s}^{*}$.

Under the event that the true MDP $M$ fall into the scope of plausible MDPs
$\mathcal{M}_{k}$, $L^{k}_{\mapsto s}h_{\mapsto s}^{*}\geq L_{\mapsto
s}h_{\mapsto s}^{*}=h_{\mapsto s}^{*}$, with the last equality comes from the
definition in Prop. 5. Hence, by Prop. 6, $h_{\mapsto s}^{k*}\geq h_{\mapsto
s}^{*}$. Together with the implications of Prop. 11,
$D_{k}^{a}lpha=\frac{D}{\alpha}\leq D$. Since $g^{\alpha*}_{k}=g^{*}\leq
r_{\max}$, together with Prop. 4,
$sp(h_{k}^{\alpha})\leq\frac{Dr_{\max}}{\alpha}$.

###  VI-C Relation between Optimal T-step Reward $v^{*,T}(s_{1})$ and Average
Reward $g^{*}$

The following lemma manifests that the $T$-step reward in the changing MDP
settings could be bounded by the optimistic average reward $g^{*}$ as follows.

######  Lemma 1 (Lemma 10 of [31]).

Under the event where the true MDP falls into the scope of plausible MDPs, for
all $k$ and all $s$,

$\displaystyle v^{*,T}(s)\leq Tg^{*}_{k}+D$ (45)

where
$g^{*}_{k}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\max_{\pi,M\in\mathcal{M}_{k}}g^{*}_{k}(M)$.

###  VI-D Lemmas for Section IV

######  Lemma 2.

With a probability at least $1-\frac{\delta}{6}$, $\forall T\geq 1$,

$\displaystyle-\sum_{t=1}^{T}r_{t}\leq$
$\displaystyle-\sum_{t=1}^{T}\sum_{a\in
A_{s_{t}}}\pi_{k_{t}}(s_{t},a)r(s_{t},a)+2r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}$
(46)

###### Proof.

For any $t\geq 1$, the $\sigma$-algebra induced by the past history of state-
action pairs and rewards up to time $t$ is denoted as
$\mathcal{F}=\sigma(s_{1},a_{1},r_{1},\cdots,s_{t},a_{t},r_{t},s_{t+1})$ where
by convention $\mathcal{F}_{0}=\sigma(\emptyset)$ and
$\mathcal{F}_{\infty}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\cup_{t\geq
0}\mathcal{F}_{t}$. Trivially, for all $t\geq 0$,
$\mathcal{F}_{t}\geq\mathcal{F}_{t+1}$ and the filtration $(F_{t})_{t\geq 0}$
is denoted by $\mathbb{F}$. Since $k_{t}$ is the integer-valued random
variable indexing the current episode at time $t$, $k_{t}$ is
$\mathcal{F}_{t-1}$-measurable i.e., the past sequence
$(s_{1},a_{1},r_{1},\cdots,s_{t},a_{t},r_{t},s_{t+1})$ fully determines the
ongoing episode at time $t$. Consequently, the stationary (randomize) policy
executed at time $t$ is also $\mathcal{F}_{t-1}$-measurable.

Let us consider a stochastic process
$X_{t}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}r_{t}(s_{t},a_{t})-\sum_{a\in
A_{s_{t}}}\pi_{k_{t}}(s_{t},a)r(s_{t},a)$. The term $\sum_{a\in
A_{s_{t}}}\pi_{k_{t}}(s_{t},a)r(s_{t},a)$ is $\mathcal{F}_{t-1}$-measurable
and $\mathbb{E}[r_{t}(s_{t},a_{t})|\mathcal{F}_{t-1}]=\sum_{a\in
A_{s_{t}}}\pi_{k_{t}}(s_{t},a)r(s_{t},a)$. Since $|X_{t}|\leq r_{\max}$,
$(X_{t},\mathcal{F}_{t})_{t\geq 1}$ is an MDS and we can apply Azuma’s
inequality in Prop. 8, namely

$\displaystyle\mathbb{P}\bigg{(}\sum_{t=1}^{T}\big{(}r_{t}-\sum_{a\in
A_{s_{t}}}\pi_{k_{t}}(s_{t},a)r(s_{t},a)\big{)}\leq-2r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}\bigg{)}\leq(\frac{\delta}{4T})^{2}\leq\frac{\delta}{16T^{2}}$
(47)

Recalling that $\sum_{n=1}^{\infty}\frac{1}{n^{2}}=\frac{\pi^{2}}{6}$ and
taking a union bound for all $T\geq 1$, we have the probability at least
$1-\sum_{T=1}^{\infty}\frac{\delta}{16T^{2}}=1-\frac{\pi^{2}\delta}{96}\geq
1-\frac{\pi}{6}$ and conclude the proof. Notably, the MDS-based proof is
different from the proof in [23], where the authors claim (without proof) that
given state-action counts $N(s,a)$ after $T$ steps, the $r_{t}$ are
independent random variables and apply the Hoeffding inequality in Prof. 7. ∎

######  Lemma 3.

Under the event that the true MDP falls into the scope of plausible MDPs
($M\in\mathcal{M}_{k},\forall k$), $\Delta_{k}$ could be upper bounded by

$\Delta_{k}\leq\Delta_{k}^{p}+\Delta_{k}^{r}+\frac{3\epsilon_{k}}{2}\sum_{s\mathcal{S}}\nu_{k}(s)$
(48)

where

$\Delta_{k}^{p}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\alpha\sum\limits_{s\in\mathcal{S}}\nu_{k}(s)\bigg{(}\sum\limits_{\begin{subarray}{c}a\in\mathcal{A}_{s}\\\
s^{\prime}\in\mathcal{S}\end{subarray}}\pi_{k}(a|s)p_{k}\big{(}s^{\prime}|s,a\big{)}h_{k}\big{(}s^{\prime}\big{)}-h_{k}(s)\bigg{)}$

and

$\Delta_{k}^{r}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum\limits_{s\in\mathcal{S}}\sum\limits_{a\in\mathcal{A}_{s}}\nu_{k}(s)\pi_{k}(a|s)\big{(}r_{k}(s,a)-r(s,a)\big{)}.$

Recalling that
$\Delta_{k}^{p1}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\alpha\sum_{s,a,s^{\prime}}\nu_{k}(s)\pi_{k}(a|s)\big{(}p_{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\big{)}h_{k}(s^{\prime})$.
If we define
$\Delta_{k}^{p3}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\alpha\sum\limits_{s,a,s^{\prime}}\nu_{k}(s,a)\bigg{(}p_{k}\big{(}s^{\prime}|s,a\big{)}-p\big{(}s^{\prime}|s,a\big{)}\bigg{)}h_{k}\big{(}s^{\prime}\big{)}$,
$p_{k}(s^{\prime}|s)\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum_{a}\pi_{k}(a|s)p_{k}(s^{\prime}|s,a)$,
$\bar{p}_{k}(s^{\prime}|s)\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum_{a}\pi_{k}(a|s)p(s^{\prime}|s,a)$,
and
$\bar{p}_{k}(s^{\prime}|s)\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum_{a}\pi_{k}(a|s)p(s^{\prime}|s,a)$,
we can have the following lemma.

######  Lemma 4.

Under the case where the true MDP falls into the scope of plausible MDPs
($M\in\mathcal{M}_{k},\forall k$), with probability at least
$1-\frac{\delta}{6}$, we have
$\sum\limits_{k=1}^{k_{T}}\Delta_{k}^{p1}\leq\sum\limits_{k=1}^{k_{T}}\Delta_{k}^{p3}+4Dr_{\max}\sqrt{T\ln\big{(}\frac{6T}{\delta}\big{)}}$.

###### Proof.

The proof is similar to that of Lemma 2.

Let us consider a stochastic process $X_{t}$ defined as

$\displaystyle X_{t}$
$\displaystyle\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\alpha\sum_{a,s^{\prime}}\pi_{k_{t}}(a|s_{t})p_{k_{t}}(s^{\prime}|s_{t},a)h_{k_{t}}(s^{\prime})-\alpha\sum_{s^{\prime}}p_{k_{t}}(s^{\prime}|s_{t},a_{t})h_{k_{t}}(s^{\prime})$
(49)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\alpha\sum_{a,s^{\prime}}\pi_{k_{t}}(a|s_{t})p_{k_{t}}(s^{\prime}|s_{t},a)w_{t}(s^{\prime})-\alpha\sum_{s^{\prime}}p_{k_{t}}(s^{\prime}|s_{t},a_{t})w_{t}(s^{\prime})$

where
$w_{t}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}h_{k_{t}}+\lambda_{t}e$
with $\lambda_{t}$ being any constant. The equation $(a)$ comes from the fact
that for a given $s_{t}$,
$\sum_{a,s^{\prime}}\pi_{k_{t}}(a|s_{t})p_{k_{t}}(s^{\prime}|s_{t},a)=1$ and
$\sum_{s^{\prime}}p_{k_{t}}(s^{\prime}|s_{t},a_{t})=1$. If we take
$\lambda_{t}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}-\frac{1}{2}(\min
h_{k_{t}}+\max h_{k_{t}})$, by Prop. 4 and Prop. 11,
$\|w_{t}(s^{\prime})\|_{\infty}\leq\frac{sp(h_{k_{t}}^{\alpha})}{2}=\frac{Dr_{\max}}{2\alpha}$,
we have $|X_{t}|\leq 2\alpha\|w_{t}(s^{\prime})\|_{\infty}\leq Dr_{\max}$
almost sure for all $t$. Notably,

$\displaystyle\sum_{t=1}^{T}X_{t}=\alpha\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a,s^{\prime}}\left(\nu_{k}(s)\pi_{k}(a|s)-\nu_{k}(s,a)\right)p_{k}(s^{\prime}|s,a)h_{k}(s^{\prime})$
(50)

Similar to Lemma 2, by Azuma’s inequality,

$\displaystyle\mathbb{P}\left(\sum_{t=1}^{T}X_{t}\geq
2Dr_{\max}\sqrt{T\ln\big{(}\frac{6T}{\delta}\big{)}}\right)\leq\frac{\delta}{36T^{2}}$
(51)

Similarly, replacing $p_{k}$ in $X_{t}$ by $p$, we have a similar bound.

Therefore, for a fixed $T$, with a probability at least
$\frac{\delta}{36T^{2}}$,

$\displaystyle\sum\limits_{k=1}^{k_{T}}\Delta_{k}^{p1}\leq\sum\limits_{k=1}^{k_{T}}\Delta_{k}^{p3}+4Dr_{\max}\sqrt{T\ln\big{(}\frac{6T}{\delta}\big{)}}$
(52)

Taking a union bound on $T$, we have with a probability at least
$1-\sum_{T=1}^{\infty}\frac{\delta}{36T^{2}}\geq 1-\frac{\delta}{6}$, we have

$\displaystyle\sum\limits_{k=1}^{k_{T}}\Delta_{k}^{p1}\leq\sum\limits_{k=1}^{k_{T}}\Delta_{k}^{p3}+4Dr_{\max}\sqrt{T\ln\big{(}\frac{6T}{\delta}\big{)}}$
(53)

∎

######  Lemma 5.

Under the case where the true MDP falls into the scope of plausible MDPs
($M\in\mathcal{M}_{k},\forall k$), if $\hat{V}_{p}$ is set as the true value
$V_{p}^{T}$, $\Delta_{k}^{p3}\leq
Dr_{\max}\sum\limits_{s,a}\nu_{k}(s,a)\beta_{p,k}^{sa}$, where
$\beta_{p,k}^{sa}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum_{s^{\prime}}\beta_{p,k}^{sas^{\prime}}$.

###### Proof.

We bound $\Delta_{k}^{p3}$ as

$\displaystyle\Delta_{k}^{p3}$
$\displaystyle=\alpha\sum\limits_{s,a,s^{\prime}}\nu_{k}(s,a)\bigg{(}p_{k}\big{(}s^{\prime}|s,a\big{)}-p\big{(}s^{\prime}|s,a\big{)}\bigg{)}h_{k}\big{(}s^{\prime}\big{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\alpha\sum\limits_{s,a,s^{\prime}}\nu_{k}(s,a)\big{(}p_{k}(s^{\prime}|s,a)-p(s^{\prime}|s,a)\big{)}w_{k}^{s}\big{(}s^{\prime}\big{)}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{\leq}}\alpha\sum\limits_{s,a}\nu_{k}(s,a)|p_{k}(\cdot|s,a)-p(\cdot|s,a)|_{1}\|w_{k}^{s}(\cdot)\|_{\infty}$
$\displaystyle\stackrel{{\scriptstyle(c)}}{{\leq}}\frac{Dr_{\max}}{2}\sum\limits_{s,a}\nu_{k}(s,a)|p_{k}(\cdot|s,a)-p(\cdot|s,a)|_{1}$
$\displaystyle\stackrel{{\scriptstyle(d)}}{{\leq}}Dr_{\max}\sum\limits_{s,a}\nu_{k}(s,a)\beta_{p,k}^{sa}$

where the equation $(a)$ comes by applying a constant shift same as in Proof
of Lemma 4 with
$\lambda_{k}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}-\frac{1}{2}(\min
h_{k_{t}}+\max h_{k_{t}})$ and
$w_{k}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}h_{k}+\lambda_{k}e$.
The inequality $(b)$ comes from the Hölder inequality and the inequality $(c)$
is due to $\|w_{k}\|_{\infty}\leq\frac{Dr_{\max}}{2}$. Based on the triangle
inequality, we have the inequality $(d)$ as

$\displaystyle\|p_{k}(\cdot|s,a)-p(\cdot|s,a)\|_{1}$
$\displaystyle\stackrel{{\scriptstyle(e)}}{{\leq}}$
$\displaystyle\|p_{k}(\cdot|s,a)-\hat{p}_{k}(\cdot|s,a)\|_{1}+\|p(\cdot|s,a)-\hat{p}_{k}(\cdot|s,a)|_{1}$
$\displaystyle\stackrel{{\scriptstyle(f)}}{{\leq}}$ $\displaystyle
2\beta_{p,k}^{sa}+\hat{V}_{p}+V_{p}^{T}=2\beta_{p,k}^{sa}+2V_{p}^{T}$ (54)

where the inequality $(e)$ comes from the triangle inequality. Meanwhile, by
construction $p_{k}(\cdot|s,a)\in\mathcal{B}_{p}^{k}$, for any
$s^{\prime}\in\mathcal{S}$,
$|p_{k}(s^{\prime}|s,a)-\hat{p}_{k}(s^{\prime}|s,a)|<\beta_{p,k}^{sas^{\prime}}$.
Hence,
$\|p_{k}(\cdot|s,a)-\hat{p}_{k}(\cdot|s,a)\|_{1}<\beta_{p,k}^{sa}+\hat{V}_{p}$.
On the other hand, since the true MDP falls into the scope of plausible MDPs
($M\in\mathcal{M}_{k},\forall k$), $p(\cdot|s,a)\in\mathcal{B}_{p}^{k}$, we
have $\|p(\cdot|s,a)-\hat{p}_{k}(\cdot|s,a)\|_{1}<\beta_{p,k}^{sa}+V_{p}$.
Therefore, if $\hat{V}_{p}$ is set as the true value $V_{p}^{T}$, we obtain
the inequality $(f)$.

The conclusion comes. ∎

######  Lemma 6.

Under the case where the true MDP falls into the scope of plausible MDPs
($M\in\mathcal{M}_{k},\forall k$), with probability at least
$1-\frac{\delta}{6}$, we have

$\displaystyle\sum_{k=1}^{k_{T}}\Delta_{k}^{p2}$ $\displaystyle\leq
2Dr_{\max}\sqrt{T\ln\big{(}\frac{6T}{\delta}\big{)}}+k_{T}Dr_{\max}$

###### Proof.

$\displaystyle\sum_{k=1}^{k_{T}}\Delta_{k}^{p2}$ (55) $\displaystyle=$
$\displaystyle\alpha\sum_{k=1}^{k_{T}}\sum\limits_{s}\nu_{k}(s)\bigg{(}\sum\limits_{\begin{subarray}{c}a,s^{\prime}\end{subarray}}\pi_{k}(a|s)p\big{(}s^{\prime}|s,a\big{)}h_{k}\big{(}s^{\prime}\big{)}-h_{k}(s)\bigg{)}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}$
$\displaystyle\alpha\sum_{k=1}^{k_{T}}\sum\limits_{s}\nu_{k}(s)\bigg{(}\sum\limits_{\begin{subarray}{c}a,s^{\prime}\end{subarray}}\pi_{k}(a|s)p\big{(}s^{\prime}|s,a\big{)}w_{k}\big{(}s^{\prime}\big{)}-w_{k}(s)\bigg{)}$
$\displaystyle=$
$\displaystyle\alpha\sum_{k=1}^{k_{T}}\sum_{t=t_{k}}^{t_{k+1}-1}\bigg{(}\sum\limits_{\begin{subarray}{c}a,s^{\prime}\end{subarray}}\pi_{k}(a|s)p\big{(}s^{\prime}|s,a\big{)}w_{k}\big{(}s^{\prime}\big{)}-w_{k}(s_{t})\bigg{)}$
$\displaystyle=$
$\displaystyle\alpha\sum_{k=1}^{k_{T}}\sum_{t=t_{k}}^{t_{k+1}-1}\bigg{(}\sum\limits_{\begin{subarray}{c}a,s^{\prime}\end{subarray}}\pi_{k}(a|s)p\big{(}s^{\prime}|s,a\big{)}w_{k}\big{(}s^{\prime}\big{)}-w_{k}(s_{t+1})+w_{k}(s_{t+1})-w_{k}(s_{t})\bigg{)}$
$\displaystyle=$
$\displaystyle\alpha\sum_{k=1}^{k_{T}}\sum_{t=t_{k}}^{t_{k+1}-1}\bigg{(}\sum\limits_{\begin{subarray}{c}a,s^{\prime}\end{subarray}}\pi_{k}(a|s)p\big{(}s^{\prime}|s,a\big{)}w_{k}\big{(}s^{\prime}\big{)}-w_{k}(s_{t+1})\bigg{)}+\alpha\sum_{k=1}^{k_{T}}\big{(}w_{k}(s_{t_{k+1}})-w_{k}(s_{t})\big{)}$

where the equation $(a)$ comes by applying a constant shift same as in Proof
of Lemma 4 with
$\lambda_{k}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}-\frac{1}{2}(\min
h_{k_{t}}+\max h_{k_{t}})$ and
$w_{k}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}h_{k}+\lambda_{k}e$.

Applying similar methodology in Lemma 2 and 4, we have

$\alpha\sum_{k=1}^{k_{T}}\sum_{t=t_{k}}^{t_{k+1}-1}\bigg{(}\sum\limits_{\begin{subarray}{c}a,s^{\prime}\end{subarray}}\pi_{k}(a|s)p\big{(}s^{\prime}|s,a\big{)}w_{k}\big{(}s^{\prime}\big{)}-w_{k}(s_{t+1})\bigg{)}\leq
2Dr_{\max}\sqrt{T\ln\big{(}\frac{6T}{\delta}\big{)}}$

with a probability at least $1-\frac{\delta}{6}$. On the other hand,
$w_{k}(s_{t_{k+1}})-w_{k}(s_{t})\leq\frac{Dr_{\max}}{\alpha}$.

The conclusion comes. ∎

######  Lemma 7.

Under the case where the true MDP falls into the scope of plausible MDPs
($M\in\mathcal{M}_{k},\forall k$), if $\hat{V}_{r}$ is set as the true value
$V_{r}^{T}$, with probability at least $1-\frac{\delta}{6}$, we have
$\sum\limits_{k=1}^{k_{T}}\Delta_{k}^{r}\leq
4r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}+2\sum\limits_{k=1}^{k_{T}}\sum\limits_{s,a}\nu_{k}(s,a)(\beta_{r,k}^{sa}+V_{r}^{T})$.

###### Proof.

The proof is similar to that of Lemma 4.

Denote
$\Delta_{k}^{r1}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\sum\limits_{s\in\mathcal{S},a\in\mathcal{A}_{s}}\nu_{k}(s,a)\big{(}r_{k}(s,a)-r(s,a)\big{)}$.
By Azuma’s inequality in Prop. 8,
$\sum\limits_{k=1}^{k_{T}}\Delta_{k}^{r}\leq\sum\limits_{k=1}^{k_{T}}\Delta_{k}^{r1}+4r_{\max}\sqrt{T\ln\big{(}\frac{4T}{\delta}\big{)}}$.
Meanwhile, analogously to Lemma 5, $\Delta_{k}^{r1}\leq
2\sum\limits_{s,a}\nu_{k}(s,a)(\beta_{r,k}^{sa}+V_{r}^{T})$. ∎

######  Proposition 12.

For any proof $n\geq 1$ and any $n$-tuple
$(a_{1},\cdots,a_{n})\in\mathbb{R}^{n}$, $(\sum_{i}^{n}a_{i})^{2}\leq
n\sum_{i}^{n}(a_{i})^{2}$.

###### Proof.

The statement is trivially true for $n=1$. For $n=2$, we have
$(a_{1}+a_{2})^{2}=a_{1}^{2}+a_{2}^{2}+2a_{1}a_{2}\leq
2(a_{1}^{2}+a_{2}^{2})$. Next we prove results for $n\geq 2$ by induction.
Assume that for $n\geq 2$, $(\sum_{i=1}^{n}a_{i})^{2}\leq
n\sum_{i=1}^{n}(a_{i})^{2}$. Then for $n+1$, we have

$\displaystyle(\sum_{i=1}^{n+1}a_{i})^{2}$
$\displaystyle=(\sum_{i=1}^{n}a_{i}+a_{n+1})^{2}$
$\displaystyle=(\sum_{i=1}^{n}a_{i})^{2}+a_{n+1}^{2}+2a_{n+1}\sum_{i}^{n}a_{i}$
$\displaystyle\leq
n\sum_{i=1}^{n}(a_{i})^{2}+a_{n+1}^{2}+2a_{n+1}\sum_{i=1}^{n}a_{i}$ (56)
$\displaystyle\leq
n\sum_{i=1}^{n}(a_{i})^{2}+a_{n+1}^{2}+\sum_{i=1}^{n}(a_{n+1}^{2}+a_{i}^{2})$
$\displaystyle=(n+1)\sum_{i=1}^{n+1}(a_{i})^{2}$

We conclude the proof. ∎

######  Proposition 13.

For any sequence of numbers $z_{1},\cdots,z_{i},\cdots$ with $0\leq z_{i}\leq
Z_{i-1}\stackrel{{\scriptstyle\text{\tiny\text{def}}}}{{=}}\max\big{\\{}1,\sum_{i=1}^{k-1}z_{i}\big{\\}}$,
we have for $n\geq 1$,

$\displaystyle\sum_{i=1}^{n}\frac{z_{i}}{Z_{i}}\leq 2+2\ln(Z_{n+1})$ (57)

and

$\displaystyle\sum_{i=1}^{n}\frac{z_{i}}{\sqrt{Z_{i}}}\leq 3\sqrt{Z_{i+1}}$
(58)

###### Proof.

We first show that the proposition holds for all $n$ with $Z_{n}\leq 1$. In
this case,
$\sum_{i=1}^{n+1}\frac{z_{i}}{Z_{i}}=\sum_{i=1}^{n}\frac{z_{i}}{Z_{i}}+\frac{z_{n+1}}{Z_{n+1}}\leq
1+1<2+2\ln(Z_{n+1})$. Notably, this implies the proposition holds for $n=1$,
since $Z_{n}=\max\\{1,\sum_{i=1}^{n-1}z_{i}\\}=\max\\{1,0\\}=1$.

Next, we show that the proposition holds by induction. Assume that
$\sum_{i=1}^{n+1}\frac{z_{i}}{Z_{i}}=\sum_{i=1}^{n}\frac{z_{i}}{Z_{i}}+\frac{z_{n+1}}{Z_{n+1}}\leq
1+1<2+2\ln(Z_{n+1})$ holds for $n=k\geq 1$ with $Z_{n}\geq 1$. For $n=k+1$, we
have

$\displaystyle\sum_{i=1}^{k+1}\frac{z_{i}}{Z_{i}}$
$\displaystyle=\sum_{i=1}^{k}\frac{z_{i}}{Z_{i}}+\frac{z_{k+1}}{Z_{k+1}}$
$\displaystyle\leq 2+2\ln(Z_{k+1})+\frac{z_{k+1}}{Z_{k+1}}$
$\displaystyle=\leq 2+2\ln(Z_{k+1})+\frac{Z_{k+2}-Z_{k+1}}{Z_{k+1}}$ (59)
$\displaystyle\stackrel{{\scriptstyle(a)}}{{\leq}}2+2\ln(Z_{k+2})$

where the equation $(a)$ holds since $\frac{Z_{k+2}}{Z_{k+1}}\in[1,2]$ and
$2\ln(t)\geq t-1$ for $t\in[1,2]$.

Similarly, we can have the proof of the latter part. ∎

######  Proposition 14.

It holds almost surely that for all $k\geq 1$ and for all
$(s,a,s^{\prime})\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$:

$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\sqrt{\hat{p}_{k}(s^{\prime}|s,a)(1-\hat{p}_{k}(s^{\prime}|s,a))}\leq\sqrt{\Gamma(s,a)-1}$
(60)

###### Proof.

Define
$\mathcal{S}_{k}^{(s,a)}=\\{s^{\prime}\in\mathcal{S}:\hat{p}_{k}(s^{\prime}|s,a)>0\\}$.
Using Cauchy-Schwarz inequality, we have

$\displaystyle\sum_{s^{\prime}\in\mathcal{S}}\sqrt{\hat{p}_{k}(s^{\prime}|s,a)(1-\hat{p}_{k}(s^{\prime}|s,a))}$
$\displaystyle=$
$\displaystyle\sum_{s^{\prime}\in\mathcal{S}_{k}^{(s,a)}}\sqrt{(1-\hat{p}_{k}(s^{\prime}|s,a))\hat{p}_{k}(s^{\prime}|s,a)}$
$\displaystyle\leq$
$\displaystyle\sqrt{\sum_{s^{\prime}\in\mathcal{S}_{k}^{(s,a)}}(1-\hat{p}_{k}(s^{\prime}|s,a))\sum_{s^{\prime}\in\mathcal{S}_{k}^{(s,a)}}\hat{p}_{k}(s^{\prime}|s,a)}$
$\displaystyle\leq$
$\displaystyle\sqrt{\sum_{s^{\prime}\in\mathcal{S}}(1-\hat{p}_{k}(s^{\prime}|s,a))\sum_{s^{\prime}\in\mathcal{S}_{k}^{(s,a)}}\hat{p}_{k}(s^{\prime}|s,a)}$
$\displaystyle\leq$ $\displaystyle\sqrt{\Gamma(s,a)-1}$

The lemma comes. ∎

######  Proposition 15 (Prop. 18 of [23]).

For all $T\geq SA$, the number of episodes $k_{T}$ up to step $T\geq SA$ is
upper bounded as $SA\log_{2}\big{(}\frac{8T}{SA}\big{)}$.

######  Proposition 16.

(39) could be further simplified as

$\displaystyle\Delta(\text{VB-UCRL},T)$ $\displaystyle\leq$
$\displaystyle\max(r_{\max},Dr_{\max})\bigg{(}43\sqrt{T\ln\big{(}\frac{T}{\delta}\big{)}\sum_{s,a}\Gamma(s,a)}$
(61)
$\displaystyle\quad+72S^{2}A\ln\big{(}\frac{T}{\delta}\big{)}\ln(T)\bigg{)}+Dr_{\max}TV_{p}^{T}+2TV_{r}^{T}$

###### Proof.

For $T<6SA$, we can directly have

$\displaystyle\Delta(\text{VB-UCRL},T)$ $\displaystyle\leq
r_{\max}T=r_{\max}\sqrt{T}\sqrt{T}$ (62) $\displaystyle\leq
r_{\max}\sqrt{6SAT}\leq\sqrt{6T\sum_{s,a}\Gamma(s,a)}$

Also, if $1\leq T\leq 43^{2}A\log\big{(}\frac{T}{\delta}\big{)}$, we have
$T^{2}\leq 43^{2}AT\log\big{(}\frac{T}{\delta}\big{)}$ (or
$T\leq\sqrt{AT\log\big{(}\frac{T}{\delta}\big{)}}$), thus $\Delta(\text{VB-
UCRL},T)\leq r_{\max}\sqrt{AT\log\big{(}\frac{T}{\delta}\big{)}}$.

For $T\geq 6SA$, we have $6SAT\leq T^{2}$, thus
$\ln\big{(}\frac{6SAT}{\delta}\big{)}\leq\ln\big{(}\frac{T^{2}}{\delta}\big{)}\leq
2\ln\big{(}\frac{T}{\delta}\big{)}$. Similarly, if $T\geq
43^{2}A\log\big{(}\frac{T}{\delta}\big{)}$, we have
$A\leq\frac{\sqrt{AT\log\big{(}\frac{T}{\delta}\big{)}}}{43\log\big{(}\frac{T}{\delta}\big{)}}$.
Together with $\log(8T)\leq 2\log(T)$,
$\log(\frac{8T}{SA})\leq\frac{2}{43}\sqrt{AT\log\big{(}\frac{T}{\delta}\big{)}}$

Thus, we can simplify (39) as

$\displaystyle\Delta(\text{VB-UCRL},T)$ $\displaystyle\leq$
$\displaystyle\max(r_{\max},Dr_{\max})\bigg{(}\sqrt{T\ln\big{(}\frac{T}{\delta}\big{)}\sum_{s,a}\Gamma(s,a)}\times(6\sqrt{2}+6\sqrt{2}+12\sqrt{2}+\frac{2}{43})$
(63)
$\displaystyle\quad+S^{2}A\ln\big{(}\frac{T}{\delta}\big{)}\ln(T)(24+48)\bigg{)}+Dr_{\max}TV_{p}^{T}+2TV_{r}^{T}$
$\displaystyle\leq$
$\displaystyle\max(r_{\max},Dr_{\max})\bigg{(}43\sqrt{T\ln\big{(}\frac{T}{\delta}\big{)}\sum_{s,a}\Gamma(s,a)}$
$\displaystyle\quad+72S^{2}A\ln\big{(}\frac{T}{\delta}\big{)}\ln(T)\bigg{)}+Dr_{\max}TV_{p}^{T}+2TV_{r}^{T}$

Replacing $\delta^{\prime}=\frac{5}{6}\delta$, and taking account of
$\log\big{(}\frac{T}{\delta^{\prime}}\big{)}=\log\big{(}\frac{6T}{5\delta}\big{)}<2\log\big{(}\frac{T}{\delta}\big{)}$,
we have the conclusion. ∎

## References

  * [1] R. Sutton and A. Barto, _Reinforcement Learning: An Introduction_. Cambridge University Press, 1998.
  * [2] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. van den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, S. Dieleman, D. Grewe, J. Nham, N. Kalchbrenner, I. Sutskever, T. Lillicrap, M. Leach, K. Kavukcuoglu, T. Graepel, and D. Hassabis, “Mastering the game of Go with deep neural networks and tree search,” _Nature_ , vol. 529, no. 7587, pp. 484–489, Jan. 2016.
  * [3] Z. Xu, J. Tang, C. Yin, Y. Wang, and G. Xue, “Experience-driven congestion control: When multi-path tcp meets deep reinforcement learning,” _IEEE J. Sel. Area. Comm._ , vol. 37, no. 6, pp. 1325–1336, Jun. 2019.
  * [4] Y. He, C. Liang, R. Yu, and Z. Han, “Trust-based social networks with computing, caching and communications: A deep reinforcement learning approach,” _IEEE Trans. Netw. Sci. Eng._ , vol. 7, no. 1, pp. 66–79, Jan. 2020.
  * [5] S. O. Somuyiwa, A. György, and D. Gündüz, “A reinforcement-learning approach to proactive caching in wireless networks,” _IEEE J. Sel. Area. Comm._ , vol. 36, no. 6, pp. 1331–1344, Jun. 2018.
  * [6] Y. S. Nasir and D. Guo, “Multi-agent deep reinforcement learning for dynamic power allocation in wireless networks,” _IEEE J. Sel. Area. Comm._ , vol. 37, no. 10, pp. 2239–2250, Oct. 2019.
  * [7] Y. He, F. R. Yu, N. Zhao, V. C. M. Leung, and H. Yin, “Software-defined networks with mobile edge computing and caching for smart cities: A big data deep reinforcement learning approach,” _IEEE Commun. Mag._ , vol. 55, no. 12, pp. 31–37, Dec. 2017.
  * [8] Y. Yu, T. Wang, and S. C. Liew, “Deep-reinforcement learning multiple access for heterogeneous wireless networks,” _IEEE J. Sel. Area. Comm._ , vol. 37, no. 6, pp. 1277–1290, Jun. 2019.
  * [9] R. S. Istepanian, N. Y. Philip, and M. G. Martini, “Medical QoS provision based on reinforcement learning in ultrasound streaming over 3.5G wireless systems,” _IEEE J. Sel. Area. Comm._ , vol. 27, no. 4, pp. 566–574, May 2009.
  * [10] H. Xu, X. Liu, W. Yu, D. Griffith, and N. Golmie, “Reinforcement learning-based control and networking co-design for industrial internet of things,” _IEEE J. Sel. Area. Comm._ , vol. 38, no. 5, pp. 885–898, May 2020\.
  * [11] W. Li, H. Zhang, S. Gao, C. Xue, X. Wang, and S. Lu, “SmartCC: A reinforcement learning approach for multipath TCP congestion control in heterogeneous networks,” _IEEE J. Sel. Area. Comm._ , vol. 37, no. 11, pp. 2621–2633, Nov. 2019.
  * [12] C. He, Y. Hu, Y. Chen, and B. Zeng, “Joint power allocation and channel assignment for NOMA with deep reinforcement learning,” _IEEE J. Sel. Area. Comm._ , vol. 37, no. 10, pp. 2200–2210, Oct. 2019.
  * [13] X. Chen, Z. Zhao, C. Wu, M. Bennis, H. Liu, Y. Ji, and H. Zhang, “Multi-tenant cross-slice resource orchestration: A deep reinforcement learning approach,” _IEEE J. Sel. Area. Comm._ , vol. 37, no. 10, pp. 2377–2392, Oct. 2019.
  * [14] F. Tang, Y. Zhou, and N. Kato, “Deep reinforcement learning for dynamic uplink/downlink resource allocation in high mobility 5G HetNet,” _IEEE J. Sel. Area. Comm._ , vol. 38, no. 12, pp. 2773–2782, Dec. 2020.
  * [15] N. C. Luong, D. T. Hoang, S. Gong, D. Niyato, P. Wang, Y.-C. Liang, and D. I. Kim, “Applications of deep reinforcement learning in communications and networking: A survey,” _IEEE J. Sel. Area. Comm._ , vol. 21, no. 4, pp. 3133–3174, Fourthquarter 2019.
  * [16] Y. Hua, R. Li, Z. Zhao, X. Chen, and H. Zhang, “GAN-powered deep distributional reinforcement learning for resource management in network slicing,” _IEEE J. Sel. Area. Comm._ , vol. 38, no. 2, pp. 334–349, Feb. 2020.
  * [17] R. Li, Z. Zhao, X. Zhou, G. Ding, Y. Chen, Z. Wang, and H. Zhang, “Intelligent 5G: When cellular networks meet artificial intelligence,” _IEEE Wireless Commun._ , vol. 24, no. 5, pp. 175–183, Oct. 2017.
  * [18] A. V. Bernstein, E. V. Burnaev, and O. N. Kachan, “Reinforcement learning for computer vision and robot navigation,” in _Machine Learning and Data Mining in Pattern Recognition_ , ser. Lecture Notes in Computer Science, P. Perner, Ed. Cham: Springer International Publishing, 2018, pp. 258–272.
  * [19] A. V. Bernstein and E. V. Burnaev, “Reinforcement learning in computer vision,” in _Proc. ICMV 2017_ , Vienna, Austria, Apr. 2018.
  * [20] R. Fruit, “Exploration-exploitation dilemma in Reinforcement Learning under various form of prior knowledge,” Ph.D. dissertation, Université de Lille 1, Sciences et Technologies; CRIStAL UMR 9189, Nov. 2019.
  * [21] T. Lai and H. Robbins, “Asymptotically efficient adaptive allocation rules,” _Adv. Appl. Math._ , vol. 6, no. 1, pp. 4–22, Mar. 1985.
  * [22] M. Kearns and S. Singh, “Near-optimal reinforcement learning in polynomial time,” _Machine Learning_ , vol. 49, no. 2, pp. 209–232, Nov. 2002.
  * [23] T. Jaksch, R. Ortner, and P. Auer, “Near-optimal regret bounds for reinforcement learning,” _J. Mach. Learn. Res._ , vol. 11, pp. 1563–1600, Aug. 2010.
  * [24] P. L. Bartlett and A. Tewari, “REGAL: A regularization based algorithm for reinforcement learning in weakly communicating MDPs,” in _Proc. UAI 2009_ , Montreal, Quebec, Canada, Jun. 2009.
  * [25] I. Osband, D. Russo, and B. Van Roy, “(More) Efficient reinforcement learning via posterior sampling,” in _Proc. NIPS 2013_ , Lake Tahoe, Nevada, USA, Dec. 2013.
  * [26] B. Hao, Y. Abbasi Yadkori, Z. Wen, and G. Cheng, “Bootstrapping Upper Confidence Bound,” in _Proc. NIPS 2019_ , H. Wallach, H. Larochelle, A. Beygelzimer, F. d\textquotesingle Alché-Buc, E. Fox, and R. Garnett, Eds. Vancouver, Canada: Curran Associates, Inc., 2019, pp. 12 123–12 133.
  * [27] R. Ortner and D. Ryabko, “Online Regret Bounds for Undiscounted Continuous Reinforcement Learning,” in _Proc. NIPS 2012_ , Stateline, NV, USA, Dec. 2012.
  * [28] J. Qian, R. Fruit, M. Pirotta, and A. Lazaric, “Exploration bonus for regret minimization in discrete and continuous average reward mdps,” in _Proc. NIPS 2019_ , Vancouver, Canada, Dec. 2019.
  * [29] Y. Li and N. Li, “Online markov decision processes with time-varying transition probabilities and rewards,” in _Proc. ICML 2019 (Real-World Sequential Decision Making Workshop)_ , Long Beach, CA, USA, Jun. 2019.
  * [30] ——, “Online learning for markov decision processes in nonstationary environments: A dynamic regret analysis,” in _Proc. ACC 2019_ , Philadelphia, PA, USA, Jul. 2019.
  * [31] P. Gajane, R. Ortner, and P. Auer, “Variational regret bounds for reinforcement learning,” in _Proc. UAI 2019_ , Tel Aviv-Yafo, Israel, May 2019.
  * [32] W. C. Cheung, D. Simchi-Levi, and R. Zhu, “Learning to optimize under non-stationarity,” in _Proc. AISTATS 2019_ , Naha, Okinawa, Japan, Apr. 2019, pp. 1079–1087.
  * [33] ——, “Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism,” in _Proc. ICML 2020_ , Vienna, Austria, Jul. 2020.
  * [34] J.-Y. Audibert, R. Munos, and C. Szepesvári, “Exploration–exploitation tradeoff using variance estimates in multi-armed bandits,” _Theor. Comput. Sci.,_ , vol. 410, no. 19, pp. 1876–1902, Apr. 2009.
  * [35] M. L. Puterman, _Markov Decision Processes: Discrete Stochastic Dynamic Programming_ , 1st ed. John Wiley & Sons, Ltd, Apr. 1994.
  * [36] P. J. Schweitzer, “On undiscounted markovian decision processes with compact action spaces,” _RAIRO \- Operations Research - Recherche Opérationnelle_ , vol. 19, no. 1, pp. 71–86, 1985.
  * [37] D. P. Bertsekas, _Dynamic Programming and Optimal Control_ , 4th ed. Athena scientific Belmont, 2012, vol. 2.
  * [38] S. Boucheron, G. Lugosi, and P. Massart, _Concentration Inequalities: A Nonasymptotic Theory of Independence_. Oxford University Press, May 2013.


[datatype=bibtex, overwrite] [fieldset=address, null] [fieldset=editor, null]
[fieldset=location, null]

# Learning Memory Kernels in Generalized Langevin Equations

Quanjun Lang, Jianfeng Lu