# Online Reinforcement Learning with Uncertain Episode Lengths

Debmalya Mandal
Max Planck Institute for Software Systems
<EMAIL_ADDRESS>
Goran Radanović
Max Planck Institute for Software Systems
<EMAIL_ADDRESS>
Jiarui Gan
University of Oxford
<EMAIL_ADDRESS>
Adish Singla
Max Planck Institute for Software Systems
<EMAIL_ADDRESS>
Rupak Majumdar
Max Planck Institute for Software Systems
<EMAIL_ADDRESS>
###### Abstract

Existing episodic reinforcement algorithms assume that the length of an
episode is fixed across time and known a priori. In this paper, we consider a
general framework of episodic reinforcement learning when the length of each
episode is drawn from a distribution. We first establish that this problem is
equivalent to online reinforcement learning with general discounting where the
learner is trying to optimize the expected discounted sum of rewards over an
infinite horizon, but where the discounting function is not necessarily
geometric. We show that minimizing regret with this new general discounting is
equivalent to minimizing regret with uncertain episode lengths. We then design
a reinforcement learning algorithm that minimizes regret with general
discounting but acts for the setting with uncertain episode lengths. We
instantiate our general bound for different types of discounting, including
geometric and polynomial discounting. We also show that we can obtain similar
regret bounds even when the uncertainty over the episode lengths is unknown,
by estimating the unknown distribution over time. Finally, we compare our
learning algorithms with existing value-iteration based episodic RL algorithms
on a grid-world environment.

##  1 Introduction

We consider the problem of _episodic reinforcement learning_ , where a
learning agent interacts with the environment over a number of episodes
[SB18]. The framework of episodic reinforcement learning usually considers two
types of episode lengths: either each episode has a fixed and invariant length
$H$, or each episode may have a varying length controlled by the learner. The
fixed-length assumption is relevant for recommender systems [Agg+16] where the
platform interacts with a user for a fixed number of rounds. Variable length
episodes arise naturally in robotics [KBP13], where each episode is associated
with a learning agent completing a task, and so the length of the episode is
entirely controlled by the learner. Fixed horizon lengths make the design of
learning algorithms easier, and is the usual assumption in most papers on
theoretical reinforcement learning [AOM17, Jin+18].

In this paper, we take a different perspective on episodic reinforcement
learning and assume that the length of each episode is drawn from a
distribution. This situation often arises in online platforms where the length
of an episode (i.e., the duration of a visit by a user) is not fixed a priori,
but follows a predictable distribution [OSB14]. Additionally, various
econometric and psychological evidence suggest that humans learn by
maintaining a risk/hazard distribution over the future [Soz98], which can be
interpreted as a distribution over the horizon length. Despite a large and
growing literature on episodic reinforcement learning, except for [Fed+19],
uncertain epsiodic lengths or settings with general survival rates of agents
have not been studied before.

Our Contributions: In this paper, we describe reinforcement learning
algorithms for general distributions over episode lengths. Our main
contribution is a general learning algorithm which can be adapted to a given
distribution over episode lengths to obtain sub-linear regret over time. In
particular, our contributions are the following.

  * •

We first establish an equivalence between maximization of expected total
reward with uncertain episode lengths and maximization of expected (general)
discounted sum of rewards over an infinite horizon. In particular, we show
that minimization of regret is equivalent in these two environments.

  * •

Next we design a learning algorithm for the setting with arbitrary
distribution over the episode lengths. Our algorithm generalizes the value-
iteration based learning algorithm of [AOM17] by carefully choosing an
effective horizon length and then updating the backward induction step based
on the distribution over episode lengths. In order to analyze its regret, we
use the equivalence result above, and bound its regret for a setting with
general discounting.

  * •

We instantiate our general regret bound for different types of discounting (or
equivalently episode distributions), including geometric and polynomial
discounting, and obtain sub-linear regret bounds. For geometric discounting
with parameter $\gamma$, we bound regret by
$\widetilde{O}(\sqrt{SAT}/(1-\gamma)^{1.5})$ which matches the recently
established minimax optimal regret for the non-episodic setting [HZG21]. For
the polynomial discounting of the form $h^{-p}$ we upper bound regret by
$\widetilde{O}(\sqrt{SA}T^{\frac{1}{2-1/p}})$.

  * •

Finally, we show that we can obtain similar regret bounds even when the
uncertainty over the episode lengths is unknown, by estimating the unknown
distribution over time. In fact, for geometric discounting, we recover the
same regret bound (i.e. $\widetilde{O}(\sqrt{SAT}/(1-\gamma)^{1.5}$) up to
logarithmic factors, and for the polynomial discounting we obtain a regret
bound of $\widetilde{O}(\sqrt{SA}T^{\frac{p}{1+2p}})$, which asymptotically
matches the previous regret bound.

Our results require novel and non-trivial generalizations of episodic learning
algorithms and straightforward extensions to existing algorithms do not work.
Indeed, a naive approach would be to use the expected episode length as the
fixed horizon length $H$. However, this fails with heavy-tailed distributions
which often appear in practice. Alternately, we could compute an upper bound
on the episode length so that with high probability the lengths of all the $T$
episodes are within this bound. Such an upper bound can be computed with the
knowledge of distribution over episode lengths and using standard
concentration inequalities. However, these upper bounds become loose either
with a large number of episodes or for heavy-tailed distributions.

###  1.1 Related Work

Episodic Reinforcement Learning: Our work is closely related to the UCB-VI
algorithm of [AOM17], which achieves $O(\sqrt{HSAT})$ regret for episodic RL
with fixed horizon length $H$. The main difference between our algorithm and
UCB-VI is that we use a different equation for backward-induction where future
payoffs are discounted by a factor of $\gamma(h+1)/\gamma(h)$ at step $h$,
where $\gamma$ is a general discount function. Beyond [AOM17], several papers
have considered different versions of episodic RL including changing
transition function [Jin+18, JL20], and function approximation [Jin+20, WSY20,
YW20].

General Discounting: Our work is also closely related to reinforcement
learning with general discounting. Even though geometric discounting is the
most-studied discounting because of its theoretical properties [Ber12], there
is a wealth of evidence suggesting that humans use general discounting and
time-inconsistent decision making [Ain75, Maz85, GM04]. In general, optimizing
discounted sum of rewards with respect to a general discounting might be
difficult as we are not guaranteed to have a stationary optimal policy.
[Fed+19] study RL with hyperbolic discounting and learn many $Q$-values each
with a different (geometric) discounting. Our model is more general, and our
algorithm is based on a modified value iteration. We also obtain theoretical
bounds on regret in our general setting. Finally, [Pit19] introduced more
general state, action based discounting but that is out of scope of this
paper.

Stochastic Shortest Path: Our work is related to the stochastic shortest path
(SSP), introduced by [BT91]. In SSP, the goal of the learner is to reach a
designated state in an MDP, and minimize the expected total cost of the policy
before reaching that goal. Recently, there has been a surge of interest in
deriving online learning algorithms for SSP [Ros+20, Coh+21, Tar+21]. Our
setting differs from SSP in two ways. First, the horizon length is effectively
controlled by the learner in SSP, once she has a good approximation of the
model. But in our setting, the horizon length is drawn from a distribution at
the start of an episode by the nature, and is unknown to the learner during
that episode. Second, when the model is known in SSP, different policies
induce different distributions over the horizon length. Therefore, in contrast
to our setting, minimizing regret in SSP is not the same as minimizing regret
under general discounting.

Other Related Work: Note that uncertainty over episode lengths can also be
interpreted as hazardous MDP [HM72], where hazard rate is defined to be the
negative rate of change of log-survival time. [Soz98] showed that different
prior belief over hazard rates imply different types of discounting. We
actually show equivalence between general discounting and uncertain episode
lengths, even in terms of regret bounds. Finally, this setting is captured by
the partially observable Markov decision processes [KLC98], where one can make
the uncertain parameters hidden and/or partially observable.

##  2 Model

We consider the problem of episodic reinforcement learning with uncertain
episode length. An agent interacts with an MDP
$\mathcal{M}=(S,\mathcal{A},r,\mathbb{P},\mathtt{P}_{\mathtt{H}})$, where
$\mathtt{P}_{\mathtt{H}}$ denotes the probability distribution over the
episode length. We assume that the rewards are bounded between $0$ and $1$.
The agent interacts with the environment for $T$ episodes as follows.

  * •

At episode $k\in[T]$, the starting state $x_{k,1}$ is chosen arbitrarily and
the length of the episode $H_{k}\sim\mathtt{P}_{\mathtt{H}}(\cdot)$. 111The
parameter $H_{k}$ is unknown to the learner during episode $k$.

  * •

For $h\in[H_{k}]$, let the state visited be $x_{k,h}$ and the action taken be
$a_{k,h}$. Then, the next state
$x_{k,h+1}\sim\mathbb{P}(\cdot|x_{k,h},a_{k,h})$.

The agent interacts with the MDP $\mathcal{M}$ for $T$ episodes and the goal
is to maximize the expected undiscounted sum of rewards. Given a sequence of
$k$ episode lengths $\\{H_{k}\\}_{k\in[T]}$ the expected cumulative reward of
an agent’s policy $\boldsymbol{\pi}=\\{\pi_{k}\\}_{k\in[T]}$ is given as

$\textrm{Rew}\left(\boldsymbol{\pi};\\{H_{k}\\}_{k\in[T]}\right)=\sum_{k=1}^{T}\mathbb{E}\left[\sum_{h=1}^{H_{k}}r(x_{k,h},a_{k,h})\right]$

Since each $H_{k}$ is a random variable drawn from the distribution
$\mathtt{P}_{\mathtt{H}}(\cdot)$, we are interested in expected reward with
respect to distribution $\mathtt{P}_{\mathtt{H}}$.

$\displaystyle\mathbb{E}\left[\textrm{Rew}\left(\boldsymbol{\pi};\\{H_{k}\\}_{k\in[T]}\right)\right]$
$\displaystyle=\mathbb{E}\left[\sum_{k=1}^{T}\sum_{H_{k}=1}^{\infty}\mathtt{P}_{\mathtt{H}}(H_{k})\sum_{h=1}^{H_{k}}r(x_{k,h},a_{k,h})\right]$
$\displaystyle=\mathbb{E}_{\pi}\left[\sum_{k=1}^{T}\sum_{h=1}^{\infty}\mathtt{P}_{\mathtt{H}}(H\geq
h)r(x_{t,h},a_{t,h})\right]$ (1)

As is standard in the literature on online learning, we will consider the
problem of minimizing regret instead of maximizing the reward. Given an
episode length $H_{k}$ and starting state $x_{k,1}$ let $\pi^{\star}_{k}$ be
the policy that maximizes the expected sum of rewards over $H_{k}$ steps i.e.
$\pi^{\star}_{k}\in\mathrm{argmax}_{\pi}\mathbb{E}_{\pi}\left[\sum_{h=1}^{H_{k}}r(x_{k,h},a_{k,h})\lvert
x_{k,1}\right].$ We will write $V^{\pi_{k}}(x_{k,1};H_{k})$ to write the
(undiscounted) value function of a policy $\pi_{k}$ over $H_{k}$ steps
starting from state $x_{k,1}$. Then $\pi^{\star}_{k}$ is also defined as
$\pi^{\star}_{k}\in\mathrm{argmax}_{\pi}V^{\pi}(x_{k,1};H_{k})$. We will also
write $V^{\star}(x_{k,1};H_{k})$ to denote the corresponding value of the
optimal value function. Now we can define the regret over $T$ steps as
follows.

######  Definition 1.

The regret of a learning algorithm $\boldsymbol{\pi}=\\{\pi_{k}\\}_{k\in[T]}$
over $T$ steps with episode lengths $\\{H_{k}\\}_{k\in[T]}$ is

$\textrm{Reg}\left(\boldsymbol{\pi};\\{H_{k}\\}\right)=\sum_{k\in[T]}V^{\star}(x_{k,1};H_{k})-V^{\pi_{k}}(x_{k,1};H_{k})$
(2)

Note that the regret as defined in eq. 2 is actually a random variable as the
episode lengths are also randomly generated from the distribution
$\mathtt{P}_{\mathtt{H}}(\cdot)$. So we will be interested in bounding the
expected regret. Let $V^{\star}(x_{k,1})$ be the expected value of
$V^{\star}(x_{k,1};H_{k})$ i.e.
$V^{\star}(x_{k,1})=\sum_{\ell}V^{\star}(x_{k,1};\ell)\mathtt{P}_{\mathtt{H}}(\ell)$.
Then the expected regret of a learning algorithm is given as

$\textrm{Reg}(\boldsymbol{\pi};\mathtt{P}_{\mathtt{H}}(\cdot))=\sum_{k\in[T]}V^{\star}(x_{k,1})-\mathbb{E}_{H_{k}}\left[V^{\pi_{k}}(x_{k,1};H_{k})\right]$

###  2.1 An Equivalent Model of General Discounting

We first establish that the problem of minimizing regret in our setting is
equivalent to minimizing regret in a different environment, where the goal is
to minimize discounted reward over an infinite horizon with a general notion
of discounting. By setting $\gamma(h)=\mathtt{P}_{\mathtt{H}}(H\geq h)$, the
expected reward in eq. 1 becomes a sum of $T$ expected rewards under the
general discounting function $\left\\{\gamma(h)\right\\}_{h=1}^{\infty}$.

$\displaystyle\mathbb{E}\left[\textrm{Rew}(\boldsymbol{\pi};\\{H_{k}\\}_{k\in[T]})\right]=\sum_{t=1}^{T}\mathbb{E}\left[\sum_{h=1}^{\infty}\gamma(h)r(x_{t,h},a_{t,h})\lvert
x_{k,1}\right]$

Therefore, we consider the equivalent setting where the agent is interacting
with the MDP $\mathcal{M}=(S,\mathcal{A},r,\mathbb{P},\boldsymbol{\gamma})$
where $\boldsymbol{\gamma}=\left\\{\gamma(h)\right\\}_{h=1}^{\infty}$ is a
general discounting factor. We will require the following two properties from
the discounting factors:

  1. 1.

$\gamma(1)=1$,

  2. 2.

$\sum_{h=1}^{\infty}\gamma(h)\leq M$ for some universal constant $M>0$.

The first assumption is without loss of generality as we can normalize all the
discount factors without affecting the maximization problem. The second
assumption guarantees that the optimal policy is well-defined. Note that this
assumption rules out hyperbolic discounting $\gamma(h)=\frac{1}{1+h}$, but
does allow discount factors of the form $\gamma(h)=h^{-p}$ for any $p>1$.
Finally, note that our original reformulation of
$\gamma(h)=\mathtt{P}_{\mathtt{H}}(H\geq h)$ trivially satisfies the first
assumption. The second assumption essentially ensures that the horizon length
has a finite mean. We will also write $\Gamma(h)$ to define the sum of the
tail part of the series starting at $h$ i.e.

$\Gamma(h)=\sum_{j\geq h}\gamma(j)$ (3)

In this new environment, the learner solves the following episodic
reinforcement learning problem over $T$ episodes.

#### Environment: General Discounting

  1. 1.

The starting state $x_{k,1}$ is chosen arbitrarily.

  2. 2.

The agent maximizes
$\mathbb{E}\left[\sum_{h=1}^{\infty}\gamma(h)r(x_{k,h},a_{k,h})\lvert
x_{k,1}\right]$ over an infinite horizon.

Notice that even though the new environment is episodic, the length of each
episode is infinite. So this environment is not realistic, and we are only
introducing this hypothetical environment to design our algorithm and analyze
its performance.

Suppose that we are given a learning algorithm
$\boldsymbol{\pi}=\\{\pi_{k}\\}_{k\in[T]}$. We allow the possibility that
$\pi_{k}$ is a non-stationary policy as each $\pi_{k}$ is used to maximizing a
discounted sum of rewards with respect to a general discounting factor and in
general the optimal policy need not be stationary. A non-stationary policy
$\pi_{k}$ is a collection of policies $\\{\pi_{k,h}\\}_{h=1}^{\infty}$ where
$\pi_{k,h}:(S\times\mathcal{A})^{h-1}\times S\rightarrow\Delta(\mathcal{A})$.
Given a non-stationary policy $\pi_{k}$ at episode $k$, we define the state-
action $Q$ function and the value function as

$\displaystyle Q^{\pi_{k}}(x,a;\boldsymbol{\gamma})$
$\displaystyle=\mathbb{E}\left[\sum_{h=1}^{\infty}\gamma(h)r(x_{k,h},a_{k,h})\lvert
x_{k,1}=x,a_{k,1}=a\right]$ $\displaystyle V^{\pi_{k}}(x;\boldsymbol{\gamma})$
$\displaystyle=\mathbb{E}\left[\sum_{h=1}^{\infty}\gamma(h)r(x_{k,h},a_{k,h})\lvert
x_{k,1}=x\right]$

Here
$a_{k,h}\sim\pi_{k,h}(x_{k,1},a_{k,1},\ldots,x_{k,h-1},a_{k,h-1},x_{k,h})$. In
this environment, we again measure the regret as the sum of sub-optimality
gaps over the $T$ episodes.

######  Definition 2.

Let the optimal value function be defined as
$V^{\star}(x;\boldsymbol{\gamma})=\sup_{\pi}V^{\pi}(x;\boldsymbol{\gamma})$.
Then we define regret for a learning algorithm
$\boldsymbol{\pi}=\\{\pi_{k}\\}_{k\in[T]}$ as

$\displaystyle\textrm{Reg}(\boldsymbol{\pi},\boldsymbol{\gamma})=\sum_{k=1}^{T}V^{\star}(x_{k,1};\boldsymbol{\gamma})-V^{\pi_{k}}(x_{k,1};\boldsymbol{\gamma})$
(4)

Our next result shows that it is sufficient to minimize regret with respect to
the new environment of episodic reinforcement learning. In fact, if any
algorithm has regret $\mathcal{R}(T)$ with respect to the new benchmark, then
it has regret at most $\mathcal{R}(T)$ with respect to the original
environment with uncertain episode lengths.

######  Lemma 1.

For any learning algorithm $\boldsymbol{\pi}=\\{\pi_{k}\\}_{k\in[T]}$ we have
the following guarantee:

$\textrm{Reg}(\boldsymbol{\pi};\mathtt{P}_{\mathtt{H}}(\cdot))\leq\textrm{Reg}(\boldsymbol{\pi};\boldsymbol{\gamma}).$

We also show that a converse of lemma 1 holds with additional restrictions on
the discount factor $\boldsymbol{\gamma}$.

######  Lemma 2.

Suppose the discount factor $\boldsymbol{\gamma}$ is non-increasing. Then
there exists a distribution $\mathtt{P}_{\mathtt{H}}(\cdot)$ over the episode
lengths so that

$\textrm{Reg}(\boldsymbol{\pi};\boldsymbol{\gamma})\leq\textrm{Reg}(\boldsymbol{\pi};\mathtt{P}_{\mathtt{H}}(\cdot)).$

Because of lemma 1, it is sufficient to bound a learning algorithm’s regret
for the environment with infinite horizon and general discounting. Therefore,
we now focus on designing a learning algorithm that acts in an episodic
setting with uncertain episode lengths, but analyze its regret in the infinite
horizon setting with general discounting.

##  3 Algorithm: Regret Minimization under General Discounting

We now introduce our main algorithm. Given a non-stationary policy $\pi_{k}$,
we define the state-action function and value function at step $h$ as follows.

$\displaystyle Q^{\pi_{k}}_{h}(x,a)$
$\displaystyle=\mathbb{E}\left[\sum_{j=1}^{\infty}\gamma(j)r(x_{k,h+j-1},a_{k,h+j-1})\mid\mathcal{H}_{h-1},x_{k,h}=x,a_{k,h}=a\right]$
$\displaystyle V^{\pi_{k}}_{h}(x)$
$\displaystyle=\mathbb{E}\left[\sum_{j=1}^{\infty}\gamma(j)r(x_{k,h+j-1},a_{k,h+j-1})\mid\mathcal{H}_{h-1},x_{k,h}=x\right]$

where $\mathcal{H}_{h-1}=(x_{k,1},a_{k,1},\ldots,a_{k,h-1})$ and
$a_{k,h+j}\sim\pi_{k,h+j}(\mathcal{H}_{h+j-1},x_{k,h+j})$. Note that, both the
state-action $Q$-function and the value function depend on the history
$\mathcal{H}_{h-1}$. Moreover, conditioned on the history, we are evaluating
the total discounted reward as if the policy $\\{\pi_{k,h+j}\\}_{j\geq 0}$ was
used from the beginning. We first establish some relations regarding the above
state-action and value functions. We drop the episode index $k$ for ease of
exposition. Given a non-stationary policy $\pi=\\{\pi_{h}\\}_{h\geq 1}$ let

$\displaystyle
Q^{\pi}_{h}(x,a)=r(x,a)+\gamma(2)\cdot\mathbb{E}\left[\sum_{j=1}^{\infty}\frac{\gamma(j+1)}{\gamma(2)}r(x_{h+j},a_{h+j})\lvert\mathcal{H}_{h-1},x_{h}=x,a_{h}=a\right]$
$\displaystyle=r(x,a)+\gamma(2)\mathbb{E}_{x_{h+1}\sim\mathbb{P}(\cdot|x,a)}\left[\mathbb{E}\left[\sum_{j=1}^{\infty}\frac{\gamma(j+1)}{\gamma(2)}r(x_{h+j+1},a_{h+j+1})\lvert\mathcal{H}_{h},x_{h+1}\right]\right]$
$\displaystyle=r(x,a)+\gamma(2)\mathbb{E}_{x_{h+1}\sim\mathbb{P}(\cdot|x,a)}\left[V_{h+1}^{\pi}(x_{h+1};\boldsymbol{\gamma}_{2})\right]$

where in the last line we write $\boldsymbol{\gamma}_{2}$ to denote the
discount factor $\boldsymbol{\gamma}_{2}(j)=\frac{\gamma(j+1)}{\gamma(2)}$ and
$V_{h+1}^{\pi}(x_{h+1};\boldsymbol{\gamma}_{2})$ is the value function at
time-step $h$ with respect to the new discount factor
$\boldsymbol{\gamma}_{2}$. By a similar argument one can write the action-
value function with respect to the discount factor $\boldsymbol{\gamma}_{2}$
as the following expression.

$\displaystyle Q^{\pi}_{h}(x,a;\boldsymbol{\gamma}_{2})$
$\displaystyle=r(x,a)+\gamma_{2}(2)\mathbb{E}_{x_{h+1}\sim\mathbb{P}(\cdot|x,a)}\left[V_{h+1}^{\pi}(x_{h+1};\boldsymbol{\gamma}_{2})\right]$
$\displaystyle=r(x,a)+\frac{\gamma(3)}{\gamma(2)}\mathbb{E}_{x_{h+1}\sim\mathbb{P}(\cdot|x,a)}\left[V_{h+1}^{\pi}(x_{h+1};\boldsymbol{\gamma}_{3})\right]$

where the discount factor $\boldsymbol{\gamma}_{3}$ is given as
$\boldsymbol{\gamma}_{3}(j)=\frac{\gamma(j+2)}{\gamma(3)}$. In general, we
have the following relation.

$\displaystyle
Q^{\pi}_{h}(x,a;\boldsymbol{\gamma}_{k})=r(x,a)+\frac{\gamma(k+1)}{\gamma(k)}\mathbb{E}_{x_{h+1}\sim\mathbb{P}(\cdot|x,a)}\left[V_{h+1}^{\pi}(x_{h+1};\boldsymbol{\gamma}_{k+1})\right]$
(5)

where the discount factor $\gamma_{k}$ is defined as
$\gamma_{k}(j)=\frac{\gamma(j+k-1)}{\gamma(k)}$ for $j=1,2,\ldots$. Notice
that when $\boldsymbol{\gamma}$ is a geometric discounting, we only need
equation.

$\displaystyle
Q^{\pi}_{h}(x,a)=r(x,a)+\gamma\mathbb{E}_{x_{h+1}\sim\mathbb{P}(\cdot|x,a)}\left[V_{h+1}^{\pi}(x_{h+1})\right]$
(6)

Input: Discount factor $\\{\gamma(h)\\}_{h=1}^{\infty}$, parameter $\Delta$

$\mathcal{H}\leftarrow\emptyset$.

for  _$h=1,\ldots,N(\Delta)$_ do

Set
$Q_{1,h}(x,a)\leftarrow\sum_{j=1}^{\infty}\gamma_{h}(j)=\frac{1}{\gamma(h)}\sum_{j=1}^{\infty}\gamma(j+h-1)$
for all $x\in S$ and $a\in\mathcal{A}$.

for  _$t=1,\ldots,T$_ do

Update-Q-values($\mathcal{H},\boldsymbol{\gamma},\Delta$).

Receive state $x_{t,1}$.

for  _$h=1,\ldots$_ do

if  _$h\leq N(\Delta)$_ then

Take action $a_{t,h}=\mathrm{argmax}_{a}Q_{t,h}(x_{t,h},a)$

Update $\mathcal{H}=\mathcal{H}\cup(x_{t,h},a_{t,h},x_{t,h+1})$

if  _$x_{t,h+1}$ is a terminal state_ then

Continue to the next episode.

Take an arbitrary action.

ALGORITHM 1 UCB-VI Generalized

#### Description of the Learning Algorithm

: The sequence of recurrence relations eq. 5 motivates our main algorithm (1).
Our algorithm is based on the upper confidence value iteration algorithm
(UCBVI [AOM17]). In an episodic reinforcement learning setting with fixed
horizon length $H$, UCBVI uses backward induction to update the $Q$-values at
the end of each episode, and takes greedy action according to the $Q$-table.

However, in our setting, there is no fixed horizon length and the $Q$-values
are related through an infinite sequence of recurrence relations. So,
algorithm 1 considers a truncated version of the sequence of recurrence
relations eq. 5. In particular, given an input discount factor
$\\{\gamma(h)\\}_{h=1}^{\infty}$222Recall that
$\gamma(h)=\mathtt{P}_{\mathtt{H}}(H\geq h)$. and a parameter $\Delta$,
algorithm 1 first determines $N(\Delta)$ as a measure of effective length of
the horizon. In particular, we set $N(\Delta)$ to be an index so that
$\Gamma(N(\Delta))=\sum_{j\geq N(\Delta)}\gamma(j)\leq\Delta$. Note that, such
an index $N(\Delta)$ always exists as we assumed that the total sum of the
discounting factors converges. Then algorithm 1 maintains an estimate of the
$Q$ value for all possible discount factors up to $N(\Delta)$ i.e.
$\boldsymbol{\gamma}_{k}$ for $k=1,\ldots,N(\Delta)$.

The details of the update procedure is provided in the appendix. In the update
procedure, we first set the $(N(\Delta)+1)$-th $Q$-value to be
$\Delta/\gamma(N(\Delta)+1)$ which is always an upper bound on the $Q$-value
with discount factor $\gamma_{N(\Delta)+1}$ because of the way algorithm 1
sets the value $N(\Delta)$. Then starting from level $N(\Delta)$, we update
the $Q$-values through backward induction and eq. 5.

Note that our algorithm needs to maintain $N(\Delta)$ action-value tables. We
will later show that in order to obtain sub-linear regret we need to choose
$\Delta$ based on the particular discount factor. In particular, for the
geometric discount factor $\gamma(h)=\gamma^{h-1}$ we need to choose
$N(\Delta)=\frac{\log T}{\log(1/\gamma)}$. On the other hand, discounting
factor of the form $\gamma(h)=1/h^{p}$ requires
$N(\Delta)=O\left(T^{1/(2p-1)}\right)$.

##  4 Analysis

The next theorem provides an upper bound on the regret
$\textrm{Reg}(\boldsymbol{\pi};\boldsymbol{\gamma})$. In order to state the
theorem, we need a new notation. Let the function $t:N\rightarrow\mathbb{R}$
be defined as

$t(h)=\left\\{\begin{array}[]{cc}1&\textrm{ if }h=1\\\
\frac{\gamma(h)}{\gamma(1)}\prod_{j=2}^{h}\left(1+\frac{\gamma(j)}{{j^{\beta}}\Gamma(j)}\right)&\textrm{
o.w. }\end{array}\right.$

Note that the function $t$ is parameterized by the parameter $\beta$ and
depends on the discount factor $\gamma(\cdot)$.

######  Theorem 1 (Informal).

With probability at least $1-\delta$, Algorithm 1 has the following regret.

$\displaystyle\textrm{Reg}(\boldsymbol{\pi};\boldsymbol{\gamma})$
$\displaystyle\leq\frac{\Delta
T}{\gamma(N(\Delta)+1)}t(N(\Delta)+1)+\max_{h\in[N(\Delta)]}t(h)\frac{\Gamma(h+1)}{\gamma(h)}\widetilde{O}\left(\sqrt{SATN(\Delta)}\right)$

Theorem 1 states a generic bound that holds for any discount factor. The main
terms in the bound are $O\left(\sqrt{SATN(\Delta)}\right)$, $\Delta T$, and
several factors dependent on the discount factor $\gamma$. We now instantiate
the bound for different discount factors by choosing appropriate value of
$\Delta$ and the parameter $\beta$.

######  Corollary 2.

Consider the discount factor $\gamma(h)=h^{-p}$. For $p\geq 2$ and $T\geq
O(S^{3}A)$ we have

$\textstyle\textrm{Reg}(T)\leq\widetilde{O}\left(S^{1/2}A^{1/2}T^{\frac{1}{2-1/p}}\right)$

and for $1<p<2$ and $T\geq O\left((S^{3}A)^{\frac{2p-1}{p-1}}\right)$ we have

$\textstyle\textrm{Reg}(T)\leq\widetilde{O}\left((p-1)^{-\frac{p}{p-1}}S^{1/2}A^{1/2}T^{\frac{1}{2-1/p}}\right)$

We prove corollary 2 by substituting $\beta=p-1$ and
$\Delta=O\left(T^{-\frac{p-1}{2p-1}}\right)$. Note that this result suggests
that as $p$ increases to infinity, the regret bound converges to
$O(\sqrt{T})$. This also suggests that for exponentially decaying discounting
factor, our algorithm should have exactly $O(\sqrt{T})$ regret. We verify this
claim next.

######  Corollary 3.

Consider the discount factor $\gamma(h)=\gamma^{h-1}$ for $\gamma\in[0,1)$ and
suppose $T\geq\frac{S^{3}A}{(1-\gamma)^{4}}$. Then algorithm 1 has regret at
most

$\textrm{Reg}(T)\leq\widetilde{O}\left({\sqrt{SAT}}/{(1-\gamma)^{1.5}}\right)$

Here we substitute $\beta=3/2$ and $\Delta=T^{-1}/(1-\gamma)$. Our regret
bound for the geometric discounting matches the minimax optimal regret bound
of the non-episodic setting of [HZG21].

#### Proof Sketch of Theorem 1

: We now give an overview of the main steps of the proof. Although the proof
is based upon the proof of the UCB-VI algorithm [AOM17], there are several
differences.

  * •

Let $V^{\star}_{h}(\cdot)$ be the optimal value function under discounting
factor $\gamma_{h}(\cdot)$ i.e.
$V^{\star}_{h}(x)=\sup_{\pi}V^{\pi}(x;\gamma_{h})$. We first show that the
estimates $V_{k,h}$ maintained by Algorithm 1 upper bound the optimal value
functions i.e. $V_{k,h}(x)\geq V^{\star}_{h}(x)$ for any $k,h\in[N(\Delta)]$.

  * •

Let $\widetilde{\Delta}_{k,h}=V_{k,h}-V^{\pi_{k}}_{h}$. Then regret can be
bounded as

$\displaystyle\textrm{Reg}(\boldsymbol{\pi};\boldsymbol{\gamma})=\sum_{k=1}^{T}V^{\star}(x_{k,1})-V^{\pi_{k}}_{1}(x_{k,1})\leq\sum_{k=1}^{T}V_{k,1}(x_{k,1})-V^{\pi_{k}}_{1}(x_{k,1})\leq\sum_{k=1}^{T}\widetilde{\Delta}_{k,1}(x_{k,1})$

  * •

Let $\widetilde{\delta}_{k,h}=\widetilde{\Delta}_{k,h}(x_{k,h})$. Then, the
main part of the proof of theorem 1 is establishing the following recurrent
relation.

$\displaystyle\widetilde{\delta}_{k,h}\leq\frac{\gamma(h+1)}{\gamma(h)}\left(1+\frac{\gamma(h+1)}{(h+1)^{\beta}\Gamma(h+1)}\right)\widetilde{\delta}_{k,h+1}+\sqrt{2L}\overline{\varepsilon}_{k,h}+e_{k,h}+b_{k,h}+\varepsilon_{k,h}+f_{k,h}$

Here $\overline{\varepsilon}_{k,h}$ and $\varepsilon_{k,h}$ are Martingale
difference sequences and $b_{k,h},e_{k,h},f_{k,h}$ are either the bonus term
or behave similarly as the bonus term.

  * •

We complete the proof by summing the recurrence relation above over all the
episodes and from $h=1$ to $N(\Delta)$. Although [AOM17] established a similar
recurrence relation, there are two major differences. First the multiplicative
factor in front of $\widetilde{\delta}_{k,h+1}$ is changing with time-step $h$
and is not a constant. This is because the backward induction step uses eq. 5
in our setting. Second, after expanding the recurrence relation from $h=1$ to
$N(\Delta)$ the final term is no longer zero and an extra $O(\Delta T)$ term
shows up in the regret bound.

Input: Horizon Length $H^{\star}=N(\Delta)$.

Set block length $B=\sqrt{T}\log T\log(\log(T)/\delta)$.

Set $\hat{\gamma}_{0}$ to be an arbitrary discount factor.

for  _$j=0,1,\ldots,\log(T/B)-1$_ do

if  _$j >0$_ then

$\hat{\gamma}_{j}(h)=1-\hat{F}_{H}(h-1)$ forall $h$.

$\hat{\Delta}_{j}=\sum_{h\geq H^{\star}+1}\hat{\gamma}_{j}(h)$.

Run algorithm 1 for $2^{j}B$ episodes with inputs $\hat{\gamma}_{j}$ and
$\hat{\Delta}_{j}$.

/* update empirical distribution function */

$\hat{F}_{H}(h)=\frac{1}{2^{j}B}\sum_{t=0}^{2^{j}B}\mathrm{1}\left\\{H_{t}\leq
h\right\\}$.

ALGORITHM 2 Estimating Unknown Discount Factor

##  5 Estimating the Discount Function

In this section we consider the situation when the discount function
$\gamma(h)=\mathtt{P}_{\mathtt{H}}(H\geq h)$ is not unknown. We start with the
assumption that the optimal value of $N(\Delta)$ (say $H^{\star}$) is known.
The next lemma bounds the regret achieved by running an algorithm with
$N(\Delta)=H^{\star}$ with the true discounting $\gamma$ and an estimate of
the discounting $\hat{\gamma}$. Our algorithm partitions the entire sequence
of $T$ episodes into blocks of lengths $B,2B,2^{2}B,\ldots,2^{s}B$ for
$s=\log(T/B)-1$. At the end of each block the algorithm recomputes an estimate
of $\gamma$. Recall that we defined $\gamma(h)=\Pr(H\geq h)$. Since every
episode we get one sample from the distribution of $H$ (the random length of
the current episode) we can use the empirical distribution function of horizon
length to obtain $\hat{\gamma}$. At the end of block $B$, the algorithm
computes $\hat{\gamma}_{B}$, and runs algorithm 1 with this estimate and
$\hat{\Delta}_{B}=\hat{\Gamma}_{B}(H^{\star}+1)=\sum_{h\geq
H^{\star}+1}\hat{\gamma}_{B}(h)$ for the block $B+1$.

######  Theorem 4 (Informal).

When run with horizon length $H^{\star}$, algorithm 2 has the following regret
bound with probability at least $1-\delta$

$\displaystyle\textrm{Reg}(\pi;\boldsymbol{\gamma})\leq\min_{L\in[T]}\left(T\Gamma(L+1)+2L\log(T)\sqrt{T})\right)+\Gamma(H^{\star})T$
$\displaystyle+\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\Gamma(h+1)\frac{O(T^{-1/4})}{\Gamma(h+1)}\widetilde{O}\left(\sqrt{SATH^{\star}}\right)$

where
$g(h)=\exp\left\\{O\left(\sum_{k=2}^{h}\frac{T^{-1/4}}{\gamma(k)+k^{\beta}\Gamma(k)}\right)\right\\}$.

(a) Geometric, $\gamma=0.9$

(b) Geometric, $\gamma=0.95$

(c) Geometric, $\gamma=0.975$

(d) Polynomial, $p=1.4$

(e) Polynomial, $p=1.6$

(f) Polynomial, $p=2.0$

(g) Quasi-Hyperbolic, $\beta=0.7$

(h) Quasi-Hyperbolic, $\beta=0.8$

(i) Quasi-Hyperbolic, $\beta=0.9$

Figure 1: Comparison of our algorithm with different variants of UCB-VI on the
Taxi environment [Die00]. The regret is measured over $100$ episodes, and the
length of each episode is drawn independently from a given distribution. Each
plot shows average regret and standard error from $10$ trials.

Our proof relies on bounding the estimation error of $\hat{\gamma}$ and
$\hat{\Gamma}$. We can use the classical DKW inequality [DKW56] to bound the
maximum deviation between empirical CDF
($\widehat{\mathtt{P}}_{\mathtt{H}}(\cdot)$) and true CDF
($\mathtt{P}_{\mathtt{H}}$). Through a union bound over the $\log(T)$ blocks,
this immediately provides a bound between
$\left\lVert\hat{\gamma}_{j}-\gamma_{j}\right\rVert_{\infty}$ for all
$j\in[\log(T/B)]$. However, we also need to bound the distance between
$\hat{\Gamma}_{j}(\cdot)$ and $\Gamma(\cdot)$ for all $j$ (defined in (3)). A
naive application of DKW inequality results in an additive bound between
$\hat{\Gamma}_{j}(h)$ and $\Gamma(h)$ that grows at a rate of $h$. This is
insufficient for our case to get a sublinear regret bound. However, we show
that we can use the multiclass fundamental theorem [SB14] to derive an error
bound that grows at a rate of $\sqrt{\log h}$ and this is sufficient for our
proof.

The main challenge in the proof of theorem 4 is controlling the growth of the
term $t(h)/\gamma(h)$. Notice that this term is a product of $h$ terms of the
form $1+\frac{\gamma(k)}{k^{\beta}\Gamma(k)}$, so any error in estimating
$\gamma$ could blow up the product by a factor of $h$. We could show that the
regret is multiplied by an additional function $g(h)$ which is parameterized
by $\beta$. We next instantiate theorem 4 for different discount factors and
show that we can obtain regret bounds similar to corollary 2, and 3 up to
logarithmic factors.

######  Corollary 5.

Consider the discount factor $\gamma(h)=h^{-p}$ for $p\geq 2$. Then the regret
of algorithm 2 is

$\textrm{Reg}(T)\leq\left\\{\begin{array}[]{cc}\widetilde{O}\left(\sqrt{SA}T^{\frac{p+1}{2p}}\right)&\textrm{
if }T\geq O\left((S^{3/2}A^{1/2})^{p}\right)\\\
\widetilde{O}\left(S^{2}AT^{\frac{1}{2-1/p}}\right)&\textrm{ if }T\leq
O\left((S^{3/2}A^{1/2})^{p}\right)\end{array}\right.$

######  Corollary 6.

Consider the geometric discount factor $\gamma(h)=\gamma^{h-1}$ for
$\gamma\in[0,1)$ and suppose
$\frac{T}{\log^{3}T}\geq\frac{S^{3}A}{(1-\gamma)^{4}}$. Then algorithm 2 has
regret at most $\widetilde{O}\left({\sqrt{SAT}}/{(1-\gamma)^{1.5}}\right).$

For the polynomial discounting we get a regret of the order of $T^{(p+1)/2p}$
which is worse than the regret bound of theorem 1 by a factor of $T^{1/2p}$.
However, the difference goes to zero as $p$ increases and approaches the same
limit of $\widetilde{O}(\sqrt{T})$. On the other hand, for geometric
discounting we recover the same regret as corollary 3. Interestingly, [HZG21]
obtained a similar bound on regret for the non-episodic setting where the
learner maximizes her long-term geometrically distributed reward.

Unknown $N(\Delta)$: Note that algorithm 2 takes as input the optimal value of
$N(\Delta)$ or $H^{\star}$. However, this problem can be handled through a
direct application of model selection algorithms in online learning [Cut+21].
Let $\textrm{Reg}(H^{\star})$ be the regret when algorithm 2 is run with true
$H^{\star}$. We now instantiate algorithm 2 for different choices of
$H^{\star}$ and perform model selection over them. In particular, we can
consider $H^{\star}=2,2^{2},\ldots,2^{O(\log T)}$ as it is sufficient to
consider $H^{\star}=O(T)$. Moreover, given true $H^{\star}$ there exists
$\widetilde{H}\leq 2H^{\star}$ for which the regret is increased by at most a
constant. This step requires bounding
$\frac{t(H^{\star})}{\gamma(H^{\star})}/\frac{t(\widetilde{H)}}{\gamma(\widetilde{H})}$
and is constant for the discounting factors considered in the paper. We now
apply algorithm 1 from [Cut+21] to the collection of $O(\log T)$ models and
obtain a regret bound of at most $O\left(\sqrt{\log
T}\textrm{Reg}(\widetilde{H})\right)=\widetilde{O}(\textrm{Reg}(H^{\star}))$.

##  6 Experiments

We evaluated the performance of our algorithm on the Taxi environment, a
$5\times 5$ grid-world environment introduced by [Die00]. The details of this
environment is provided in the appendix, since the exact details are not too
important for understanding the experimental results. We considered $100$
episodes and each episode length was generated uniformly at random from the
following distributions. 333Here $\gamma(h)$ refers to probability that the
episode lengths exceeds $h$ i.e. $\gamma(h)=\Pr(H\geq h)$.

  1. 1.

Geometric discounting $\gamma(h)=\gamma^{h-1}$.

  2. 2.

Polynomial discounting $\gamma(h)=h^{-p}$.

  3. 3.

Quasi-Hyperbolic discounting
$\gamma(h)=\beta^{\mathrm{1}\left\\{h>1\right\\}}\gamma^{h-1}$

Figure 1 shows some representative parameters for three different types of
discounting. For the geometric discounting, we show $\gamma=0.9,0.95$ and
$0.975$. For the polynomial discounting we generated the horizon lengths from
a polynomial with $p\in\left\\{1.4,1.6,2.0\right\\}$ and added an offset of
$20$. Finally, for the Quasi-hyperbolic discounting, we fixed $\gamma$ at
$0.95$ and considered three values of $\beta$: $0.7,0.8$, and $0.9$.

We compared our algorithm (1) with two variants of UCB-VI [AOM17] – (a) UCB-
VI-Hoeffding computes bonus terms using Chernoff-Hoeffding inequality, and (b)
UCB-VI-Bernstein computes bonus terms using Bernstein-Freedman inequality. It
is known that when the horizon length is fixed and known, UCB-VI-Bernstein
achieves minimax optimal regret bounds. We implemented two versions of UCB-VI
with three different assumed horizon lengths.

Figure 1 shows that, for several situations, our algorithm strict improves in
regret compared to all the other variants of UCB-VI. These include Geometric
discounting ($\gamma=0.95$ and $0.975$) and Quasi-Hyperbolic discounting (all
possible choices of $\beta$). For the other scenarios (e.g. polynomial
discounting), our algorithm performs as well as the best version UCB-VI.
Figure 1 also highlights the importance of choosing not only the right horizon
length but also the correct update equation in backward induction. Consider
for example, figure 1(b) for the geometric discounting with $\gamma=0.95$.
Here the expected horizon length is $\frac{1}{1-\gamma}=20$. However,
different UCB-VI variants (horizon lengths $10,20,30$ and Bernstein and
Hoeffding variants) perform worse. Our algorithm benefits by choosing the
right effective horizon length, and also the correct update equation (6).

##  7 Conclusion

In this paper, we have designed reinforcement learning algorithms when the
episode lengths are uncertain and drawn from a fixed distribution. Our general
learning algorithm (1) and result (theorem 1) can be instantiated for
different types of distributions to obtain sub-linear regret bounds. Some
interesting directions of future work include extension of our algorithm to
function approximation [Jin+20], changing probability transition function
[Jin+18], etc. We are also interested in other models of episode lengths. For
example, one can consider a setting where the lengths are adversarially
generated but there is a limit on the total amount of change. This is similar
to the notion of variation budget [BGZ14] considered in the literature on non-
stationary multi-armed bandits.

## Acknowledgements

Goran Radanović acknowledges that his research was, in part, funded by the
Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) – project
number 467367360.

## References

  * [Agg+16] Charu C Aggarwal  “Recommender systems”  Springer, 2016
  * [Ain75] George Ainslie  “Specious reward: a behavioral theory of impulsiveness and impulse control.”  In _Psychological bulletin_ 82.4 American Psychological Association, 1975, pp. 463
  * [AOM17] Mohammad Gheshlaghi Azar, Ian Osband and Rémi Munos  “Minimax regret bounds for reinforcement learning”  In _International Conference on Machine Learning_ , 2017, pp. 263–272  PMLR
  * [Ber12] Dimitri Bertsekas  “Dynamic programming and optimal control: Volume I”  Athena scientific, 2012
  * [BGZ14] Omar Besbes, Yonatan Gur and Assaf Zeevi  “Stochastic multi-armed-bandit problem with non-stationary rewards”  In _Advances in neural information processing systems_ 27, 2014
  * [Bro+16] Greg Brockman et al.  “Openai gym”  In _arXiv preprint arXiv:1606.01540_ , 2016
  * [BT91] Dimitri P Bertsekas and John N Tsitsiklis  “An analysis of stochastic shortest path problems”  In _Mathematics of Operations Research_ 16.3 INFORMS, 1991, pp. 580–595
  * [Coh+21] Alon Cohen, Yonathan Efroni, Yishay Mansour and Aviv Rosenberg  “Minimax regret for stochastic shortest path”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 28350–28361
  * [Cut+21] Ashok Cutkosky et al.  “Dynamic balancing for model selection in bandits and rl”  In _International Conference on Machine Learning_ , 2021, pp. 2276–2285  PMLR
  * [Die00] Thomas G Dietterich  “Hierarchical reinforcement learning with the MAXQ value function decomposition”  In _Journal of artificial intelligence research_ 13, 2000, pp. 227–303
  * [DKW56] Aryeh Dvoretzky, Jack Kiefer and Jacob Wolfowitz  “Asymptotic minimax character of the sample distribution function and of the classical multinomial estimator”  In _The Annals of Mathematical Statistics_ JSTOR, 1956, pp. 642–669
  * [Fed+19] William Fedus et al.  “Hyperbolic discounting and learning over multiple horizons”  In _arXiv preprint arXiv:1902.06865_ , 2019
  * [GM04] Leonard Green and Joel Myerson  “A discounting framework for choice with delayed and probabilistic rewards.”  In _Psychological bulletin_ 130.5 American Psychological Association, 2004, pp. 769
  * [HM72] Ronald A Howard and James E Matheson  “Risk-sensitive Markov decision processes”  In _Management science_ 18.7 INFORMS, 1972, pp. 356–369
  * [HZG21] Jiafan He, Dongruo Zhou and Quanquan Gu  “Nearly minimax optimal reinforcement learning for discounted MDPs”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 22288–22300
  * [Jin+18] Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck and Michael I Jordan  “Is Q-learning provably efficient?”  In _Advances in neural information processing systems_ 31, 2018
  * [Jin+20] Chi Jin, Zhuoran Yang, Zhaoran Wang and Michael I Jordan  “Provably efficient reinforcement learning with linear function approximation”  In _Conference on Learning Theory_ , 2020, pp. 2137–2143  PMLR
  * [JL20] Tiancheng Jin and Haipeng Luo  “Simultaneously learning stochastic and adversarial episodic mdps with known transition”  In _Advances in neural information processing systems_ 33, 2020, pp. 16557–16566
  * [KBP13] Jens Kober, J Andrew Bagnell and Jan Peters  “Reinforcement learning in robotics: A survey”  In _The International Journal of Robotics Research_ 32.11 SAGE Publications Sage UK: London, England, 2013, pp. 1238–1274
  * [KLC98] Leslie Pack Kaelbling, Michael L Littman and Anthony R Cassandra  “Planning and acting in partially observable stochastic domains”  In _Artificial intelligence_ 101.1-2 Elsevier, 1998, pp. 99–134
  * [Mas90] Pascal Massart  “The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality”  In _The annals of Probability_ JSTOR, 1990, pp. 1269–1283
  * [Maz85] James E Mazur  “Probability and delay of reinforcement as factors in discrete-trial choice”  In _Journal of the Experimental Analysis of Behavior_ 43.3 Wiley Online Library, 1985, pp. 341–351
  * [Nat89] Balas K Natarajan  “On learning sets and functions”  In _Machine Learning_ 4.1 Springer, 1989, pp. 67–97
  * [OSB14] Daniel FO Onah, Jane Sinclair and Russell Boyatt  “Dropout rates of massive open online courses: behavioural patterns”  In _EDULEARN14 proceedings_ 1, 2014, pp. 5825–5834
  * [Pit19] Silviu Pitis  “Rethinking the discount factor in reinforcement learning: A decision theoretic approach”  In _Proceedings of the AAAI Conference on Artificial Intelligence_ 33, 2019, pp. 7949–7956
  * [Ros+20] Aviv Rosenberg, Alon Cohen, Yishay Mansour and Haim Kaplan  “Near-optimal regret bounds for stochastic shortest path”  In _International Conference on Machine Learning_ , 2020, pp. 8210–8219  PMLR
  * [SB14] Shai Shalev-Shwartz and Shai Ben-David  “Understanding machine learning: From theory to algorithms”  Cambridge university press, 2014
  * [SB18] Richard S Sutton and Andrew G Barto  “Reinforcement learning: An introduction”  MIT press, 2018
  * [Soz98] Peter D Sozou  “On hyperbolic discounting and uncertain hazard rates”  In _Proceedings of the Royal Society of London. Series B: Biological Sciences_ 265.1409 The Royal Society, 1998, pp. 2015–2020
  * [Tar+21] Jean Tarbouriech et al.  “Stochastic shortest path: Minimax, parameter-free and towards horizon-free regret”  In _Advances in Neural Information Processing Systems_ 34, 2021, pp. 6843–6855
  * [WSY20] Ruosong Wang, Russ R Salakhutdinov and Lin Yang  “Reinforcement learning with general value function approximation: Provably efficient approach via bounded eluder dimension”  In _Advances in Neural Information Processing Systems_ 33, 2020, pp. 6123–6135
  * [YW20] Lin Yang and Mengdi Wang  “Reinforcement learning in feature space: Matrix bandit, kernels, and regret bound”  In _International Conference on Machine Learning_ , 2020, pp. 10746–10756  PMLR

##  Appendix A Pseudocode of Update-Q-Values

Input: Discount factor $\\{\gamma(h)\\}_{h=1}^{\infty}$, parameter $\Delta$,
episode $k$, and dataset $\mathcal{H}$.

$N_{k}(x,a,y)=\sum_{(x^{\prime},a^{\prime},y^{\prime})\in\mathcal{H}}\mathrm{1}\left\\{x^{\prime}=x,a^{\prime}=a,y^{\prime}=y\right\\}$
for all $(x,a,y)\in\mathcal{S}\times\mathcal{A}\times\mathcal{S}$.

$N_{k}(x,a)=\sum_{y}N_{k}(x,a,y)$ for all
$(x,a)\in\mathcal{S}\times\mathcal{A}$.

Set $\hat{P}(y|x,a)=\frac{N_{k}(x,a,y)}{N_{k}(x,a)}$ for all $(x,a)$ s.t.
$N_{k}(x,a)>0$. Otherwise, $\hat{P}(y|x,a)=\frac{1}{S}$

/* Update all the $Q$ values */

$Q_{k,N(\Delta)+1}(x,a)\leftarrow\frac{\Delta}{\gamma\left(N(\Delta)+1\right)}$
for all $x\in S$ and $a\in\mathcal{A}$.

$V_{k,N(\Delta)+1}(x,a)\leftarrow\frac{\Delta}{\gamma\left(N(\Delta)+1\right)}$
for all $x\in S$.

for  _$h=N(\Delta),\ldots,1$_ do

/* Define
$[\hat{P}_{k}V_{k,h+1}](s,a)=\mathbb{E}_{x\sim\hat{P}_{k}(\cdot|s,a)}\left[V_{k,h+1}(x)\right]$
and let $\Gamma(h)=\sum_{j\geq h}\gamma(j)$. */

$\displaystyle\textrm{UCB}_{k,h}(s,a)=\frac{3\Gamma(h+1)}{\gamma(h)}\frac{\ln(SATN(\Delta)/\delta)}{\sqrt{N_{k}(s,a)}}$
$\displaystyle Q_{k,h}(s,a)=\min\left\\{Q_{k-1,h}(s,a),r(s,a)\right.$
$\displaystyle+\left.\frac{\gamma(h+1)}{\gamma(h)}[\hat{P}_{k}V_{k,h+1}](s,a)+\textrm{UCB}_{k,h}(s,a)\right\\}$
$\displaystyle V_{k,h}(s,a)=\max_{a\in\mathcal{A}}Q_{k,h}(s,a)$

ALGORITHM 3 Update-Q-values

##  Appendix B Additional Experimental Details

In the Taxi environment [Die00] environment, there are four randomly chosen
designated locations indicated by Red, Green, Blue, and Yellow. The driver
(learner) starts at a random square and the passenger is at a random location.
The taxi drives to the passenger’s location, picks up the passenger (from one
of the four locations), drives to the passenger’s destination (another one of
the four specified locations), and then drops off the passenger. There are six
actions and the observations include the location of the taxi and the starting
point and the destination of the passenger. Each step incurs a cost of $1$.
There is a reward of $20$ for successfully delivering a passenger, and a
reward of $-10$ for executing pickup and drop-off actions illegally. We used
the Open-AI implementation Taxi-v3 [Bro+16] to interact with the environment.

All experiments were conducted on a computer cluster with machines equipped
with2Intel XeonE5-2667 v2 CPUs with 3.3GHz (16 cores) and 50 GB RAM.

##  Appendix C Equivalence between
$\textrm{Reg}(\boldsymbol{\pi};\boldsymbol{\gamma})$ and
$\textrm{Reg}(\boldsymbol{\pi};\mathtt{P}_{\mathtt{H}}(\cdot))$

###  C.1 Proof of Lemma 1

###### Proof.

Consider any learning algorithm $\boldsymbol{\pi}=\\{\pi_{k}\\}_{k\in[T]}$.

$\displaystyle\mathbb{E}_{H_{k}}\left[V^{\pi_{k}}(x_{k,1};H_{k})\right]$
$\displaystyle=\sum_{\ell}\mathtt{P}_{\mathtt{H}}(\ell)\mathbb{E}\left[V^{\pi_{k}}(x_{k,1};\ell)\right]=\mathbb{E}\left[\sum_{\ell}\mathtt{P}_{\mathtt{H}}(\ell)\sum_{h=1}^{\ell}r(x_{k,h},a_{k,h})\right]$
$\displaystyle=\mathbb{E}\left[\sum_{h=1}^{\infty}\mathtt{P}_{\mathtt{H}}(H_{k}\geq
h)r(x_{k,h},a_{k,h})\right]=\mathbb{E}\left[\sum_{h=1}^{\infty}\gamma(h)r(x_{k,h},a_{k,h})\right]$
$\displaystyle=V^{\pi_{k}}(x_{k,1};\boldsymbol{\gamma})$

Therefore, we have the following result.

$\sum_{k=1}^{T}\mathbb{E}_{H_{k}}\left[V^{\pi_{k}}(x_{k,1};H_{k})\right]=\sum_{k=1}^{T}V^{\pi_{k}}(x_{k,1};\boldsymbol{\gamma})$
(7)

We now upper bound the quantity
$\sum_{\ell}V^{\star}(x_{k,1};\ell)\mathtt{P}_{\mathtt{H}}(\ell)$. Let
$\pi^{\star}_{k,\ell}$ be the policy that maximizes the $\ell$-step value
function i.e.
$V^{\star}(x_{k,1};\ell)=V^{\pi^{\star}_{k,\ell}}(x_{k,1};\ell)$. Let us also
define a new policy $\pi_{\infty}$ as follows.

  1. 1.

At step $h$, draw an index $j\in[h,\infty)$ according to the distribution
$\frac{\mathtt{P}_{\mathtt{H}}(\cdot)}{\mathtt{P}_{\mathtt{H}}(H\geq h)}$.

  2. 2.

Take action
$\pi^{\star}_{k,j}(x_{k,1},a_{k,1},\ldots,x_{k,h-1},a_{k,h-1},x_{k,h})$.

Then the infinite-horizon discounted sum of rewards under the policy
$\pi_{\infty}$ is given as

$\displaystyle\mathbb{E}_{\pi_{\infty}}\left[\sum_{h=1}^{\infty}\gamma(h)r(x_{k,h},a_{k,h})\right]$
$\displaystyle=\mathbb{E}\left[\sum_{h=1}^{\infty}\mathtt{P}_{\mathtt{H}}(H\geq
h)\mathbb{E}_{\pi_{\infty}}\left[r(x_{k,h},a_{k,h})\rvert\mathcal{H}_{h}\right]\right]$
$\displaystyle=\mathbb{E}\left[\sum_{h=1}^{\infty}\mathtt{P}_{\mathtt{H}}(H\geq
h)\sum_{j=h}^{\infty}\frac{\mathtt{P}_{\mathtt{H}}(j)}{\mathtt{P}_{\mathtt{H}}(H\geq
h)}\mathbb{E}_{a_{k,h}\sim\pi^{\star}_{k,j}(\mathcal{H}_{h})}\left[r(x_{k,h},a_{k,h})\rvert\mathcal{H}_{h}\right]\right]$
$\displaystyle=\mathbb{E}\left[\sum_{h=1}^{\infty}\sum_{j=h}^{\infty}{\mathtt{P}_{\mathtt{H}}(j)}\mathbb{E}_{a_{k,h}\sim\pi^{\star}_{k,j}(\mathcal{H}_{h})}\left[r(x_{k,h},a_{k,h})\rvert\mathcal{H}_{h}\right]\right]$
$\displaystyle=\mathbb{E}\left[\sum_{j=1}^{\infty}\mathtt{P}_{\mathtt{H}}(j)\sum_{h=1}^{j}\mathbb{E}_{a_{k,h}\sim\pi^{\star}_{k,j}(\mathcal{H}_{h})}\left[r(x_{k,h},a_{k,h})\rvert\mathcal{H}_{h}\right]\right]$
$\displaystyle=\mathbb{E}\left[\sum_{j=1}^{\infty}\mathtt{P}_{\mathtt{H}}(j)\mathbb{E}_{\pi^{\star}_{k,j}}\left[\sum_{h=1}^{j}r(x_{k,h},a_{k,h})\right]\right]=\sum_{j}V^{\star}(x_{k,1};\ell)\mathtt{P}_{\mathtt{H}}(j)$

Since $\pi_{\infty}$ is one candidate policy for maximizing infinite horizon
sum of discounted rewards, its value function is bounded by the optimal value
function.

$\sum_{k=1}^{T}\sum_{\ell}\mathtt{P}_{\mathtt{H}}(\ell)V^{\star}(x_{k,1};\ell)=\sum_{k=1}^{T}V^{\pi_{\infty}}(x_{k,1};\boldsymbol{\gamma})\leq\sum_{k=1}^{T}V^{\star}(x_{k,1};\boldsymbol{\gamma})$
(8)

Combining equations 7 and 8 we get that the regret under the new general
discounting environment upper bounds the regret under the original environment
i.e.
$\textrm{Reg}(\boldsymbol{\pi};\mathtt{P}_{\mathtt{H}}(\cdot))\leq\textrm{Reg}(\boldsymbol{\pi};\boldsymbol{\gamma})$.
∎

###  C.2 Proof of Lemma 2

###### Proof.

Given a discount factor $\boldsymbol{\gamma}$, we define the following
distribution over episode lengths.

$\displaystyle\mathtt{P}_{\mathtt{H}}(H=h)=\gamma(h)-\gamma(h+1)$

This definition implies that $\Pr(H\geq h)=\gamma(h)$ and under this condition
lemma 1 already shows that
$\sum_{k=1}^{T}\mathbb{E}_{H_{k}}\left[V^{\pi_{k}}(x_{k,1};H_{k})\right]=\sum_{k=1}^{T}V^{\pi_{k}}(x_{k,1};\boldsymbol{\gamma})$.
Therefore, it remains to upper bound the quantity
$\sum_{k=1}^{T}V^{\star}(x_{k,1};\boldsymbol{\gamma})$. Let
$\pi^{\star}=(\pi^{\star}_{1},\pi^{\star}_{2},\ldots)$ be the policy that
maximizes long-term discounted sum of rewards with respect to the discount
factor $\boldsymbol{\gamma}$. Note that one can also play the policy
$\pi^{\star}$ for the finite horizon setting.

$\displaystyle\sum_{\ell}\mathtt{P}_{\mathtt{H}}(\ell)V^{\star}(x_{k,1};\ell)\geq\sum_{\ell}\mathtt{P}_{\mathtt{H}}(\ell)V^{\pi^{\star}}(x_{k,1};\ell)=\sum_{\ell}\mathtt{P}_{\mathtt{H}}(\ell)\mathbb{E}_{\pi^{\star}}\left[\sum_{j=1}^{\ell}r(x_{k,j},a_{k,j})\right]$
$\displaystyle=\mathbb{E}_{\pi^{\star}}\left[\sum_{j=1}^{\infty}\sum_{\ell\geq
j}(\gamma(\ell)-\gamma(\ell+1))r(x_{k,j},a_{k,j})\right]$
$\displaystyle=\mathbb{E}_{\pi^{\star}}\left[\sum_{j=1}^{\infty}\gamma(j)r(x_{k,j},a_{k,j})\right]=V^{\star}(x_{k,1};\boldsymbol{\gamma})$

Since the optimal value under the new environment (episode distribution
$\mathtt{P}_{\mathtt{H}}(\cdot)$) upper bounds the optimal value under the
discount factor $\boldsymbol{\gamma}$, the regret under
$\mathtt{P}_{\mathtt{H}}(\cdot)$ can only get worse. ∎

##  Appendix D Proof of theorem 1 and Related Corollaries

We first show that the $Q$ values at each time-step upper bounds the optimal
$Q$ values.

######  Lemma 3.

With probability at least $1-\delta$, for all $k\in[T]$, $h\in[N(\Delta)]$,
$x\in S$, $a\in\mathcal{A}$, we have

$Q_{k,h}(x,a)\geq Q^{\star}_{h}(x,a),\ V_{k,h}(x)\geq V^{\star}_{h}(x)$

###### Proof.

We prove this statement using induction. First note that we always have
$Q_{k,N(\Delta)+1}(x,a)\geq Q^{\star}_{N(\Delta)+1}(x,a)$ just from the
initialization.Suppose the given claim is true for all $k^{\prime}\leq k-1$
and also $Q_{k,h^{\prime}}(x,a)\geq Q^{\star}_{k}(x,a)$ for all
$h^{\prime}\geq h+1$. We now wish to show that $Q_{k,h}(x,a)\geq
Q^{\star}_{k}(x,a)$. We can assume that $Q_{k,h}(x,a)\neq Q_{k-1,h}(x,a)$
otherwise the claim is true just from the induction hypothesis. Then we have,

$\displaystyle Q_{k,h}(x,a)-Q^{\star}_{h}(x,a)$
$\displaystyle=\frac{\gamma(h+1)}{\gamma(h)}\left([\hat{P}_{k}V_{k,h+1}](x,a)-[PV^{\star}_{h+1}](x,a)\right)+\textrm{UCB}_{k,h}(x,a)$
$\displaystyle\geq\frac{\gamma(h+1)}{\gamma(h)}\left([(\hat{P}_{k}-P)V^{\star}_{h+1}](x,a)\right)+\textrm{UCB}_{k,h}(x,a)$

The last inequality follows because from the induction hypothesis
$V_{k,h+1}(y)\geq V^{\star}_{h+1}(y)$. We now bound Bernstein’s inequality and
union bound to bound the first term. Using the fact that
$V^{\star}_{h+1}(\cdot)$ is uniformly bounded by $\Gamma(h+1)/\gamma(h+1)$, we
get that the following bound holds with probability at least $1-\delta$ for
any $(x,a)\in\mathcal{S}\times\mathcal{A}$, $t\in[T]$, and $h\in[N(\Delta)]$.

$\left|[(\hat{P}_{k}-P)V^{\star}_{h}](x,a)\right|\leq\sqrt{\frac{2\mathbb{V}^{\star}_{h}(x,a)\ln(SATN(\Delta)/\delta)}{N_{k}(x,a)}}+\frac{2\Gamma(h)\ln(SATN(\Delta)/\delta)}{3\gamma(h)N_{k}(x,a)}$

We now bound the variance term $\mathbb{V}^{\star}_{h+1}(x,a)$ by
$(\Gamma(h+1)/\gamma(h+1))^{2}$ and substitute the above bound to obtain the
following bound on the different between $Q$ values.

$\displaystyle Q_{k,h}(x,a)-Q^{\star}_{h}(x,a)$
$\displaystyle\geq-\frac{\Gamma(h+1)}{\gamma(h)}\left(\sqrt{\frac{2\ln(SATN(\Delta)/\delta)}{N_{k}(x,a)}}+\frac{2\ln(SATN(\Delta)/\delta)}{3N_{k}(x,a)}\right)$
$\displaystyle+\textrm{UCB}_{k,h}(x,a)$

Now it follows from the definition of $\textrm{UCB}_{k,h}(x,a)$ that the final
term is non-negative. ∎

###  D.1 Proof of theorem 1

We first provide a formal statement of theorem 1.

######  Theorem 7.

With probability at least $1-\delta$, Algorithm 1 has the following regret.

$\displaystyle\textrm{Reg}(\boldsymbol{\pi};\boldsymbol{\gamma})\leq\frac{\Delta
T}{\gamma(N(\Delta)+1)}t(N(\Delta)+1)+\max_{h\in[N(\Delta)]}t(h)\frac{\gamma(h+1)}{\gamma(h)}O\left(\sqrt{TN(\Delta)\log(TN(\Delta)/\delta)}\right)$
$\displaystyle+\max_{h\in[N(\Delta)]}t(h)\frac{\Gamma(h+1)}{\gamma(h)}{O}\left(\sqrt{SATN(\Delta)}\right)+\max_{h\in[N(\Delta)]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}\widetilde{O}\left({S^{2}A({N(\Delta)})^{\beta}}\right)$

###### Proof.

At episode $k$, time $h$ the algorithm takes the best action according to
$Q_{k,h}(\cdot,\cdot)$. Therefore,
$\pi_{k,h}(x_{k,h})=a_{k,h}\in\mathrm{argmax}_{a}Q_{k,h}(x_{k,h},a)$.
Moreover,
$V^{\pi_{k}}(x_{k,h})=Q^{\pi_{k}}_{h}(x_{k,h},\pi_{k,h}(x_{k,h}))=Q^{\pi_{k}}(x_{k,h},a_{k,h})$.

$\displaystyle\widetilde{\Delta}_{k,h}(x_{k,h})$
$\displaystyle=V_{k,h}(x_{k,h})-V^{\pi_{k}}_{h}(x_{k,h})=Q_{k,h}(x_{k,h},a_{k,h})-Q^{\pi_{k}}_{h}(x_{k,h},a_{k,h})$
$\displaystyle\leq\frac{\gamma(h+1)}{\gamma(h)}[\hat{P}_{k}V_{k,h+1}-PV^{\pi_{k}}_{h+1}](x_{k,h},a_{k,h})+\textrm{UCB}_{k,h}(x_{k,h},a_{k,h})$

Now we proceed similarly as the proof of theorem 1 from [AOM17] and derive a
recurrence relation for
$\widetilde{\delta}_{k,h}=\widetilde{\Delta}_{k,h}(x_{k,h})$.

$\displaystyle\widetilde{\delta}_{k,h}$
$\displaystyle\leq\frac{\gamma(h+1)}{\gamma(h)}[(\hat{P}_{k}-P)(V_{h,k+1}-V^{\star}_{h+1})](x_{k,h},a_{k,h})$
$\displaystyle+\frac{\gamma(h+1)}{\gamma(h)}[P(V_{k,h+1}-V^{\pi_{k}}_{h+1})](x_{k,h},a_{k,h})$
$\displaystyle+\frac{\gamma(h+1)}{\gamma(h)}[(\hat{P}_{k}-P)V^{\star}_{h+1}](x_{k,h},a_{k,h})$
$\displaystyle+\textrm{UCB}_{k,h}(x_{k,h},a_{k,h})$
$\displaystyle=c_{k,h}+\frac{\gamma(h+1)}{\gamma(h)}[P\widetilde{\Delta}_{k,h+1}](x_{k,h},a_{k,h})+e_{k,h}+b_{k,h}$

where in the last line we used the following notations.

$c_{k,h}=\frac{\gamma(h+1)}{\gamma(h)}[(\hat{P}_{k}-P)(V_{k,h+1}-V^{\star}_{h+1})](x_{k,h},a_{k,h})$
(9)
$e_{k,h}=\frac{\gamma(h+1)}{\gamma(h)}[(\hat{P}_{k}-P)V^{\star}_{h+1}](x_{k,h},a_{k,h})$
(10) $b_{k,h}=\textrm{UCB}_{k,h}(x_{k,h},a_{k,h})$ (11)

Finally, writing $\varepsilon_{k,h}$ as the following error term

$\varepsilon_{k,h}=\frac{\gamma(h+1)}{\gamma(h)}[P\widetilde{\Delta}_{k,h+1}](x_{k,h},a_{k,h})-\frac{\gamma(h+1)}{\gamma(h)}\widetilde{\Delta}_{k,h+1}(x_{k,h+1})$
(12)

we get the following recurrence relation for $\widetilde{\delta}_{k,h}$.

$\widetilde{\delta}_{k,h}\leq\frac{\gamma(h+1)}{\gamma(h)}\widetilde{\delta}_{k,h+1}+c_{k,h}+e_{k,h}+b_{k,h}+\varepsilon_{k,h}$
(13)

Let $L=2\ln(SATN(\Delta)/\delta)$. Then we can apply Bernstein’s inequality
(lemma 4) to conclude that with probability at least $1-\delta$ the following
bound holds for each $j\in[N(\Delta)]$ and $k\in[T]$.

$e_{k,j}\leq\frac{\gamma(j+1)}{\gamma(j)}\left(\sqrt{\frac{L\textrm{Var}_{y\sim\mathbb{P}(\cdot|x_{k,j},a_{k,j})}V^{\star}_{j+1}(y)}{N_{k}(x_{k,j},a_{k,j})}}+\frac{L\max_{y}V^{\star}_{j+1}(y)}{3N_{k}(x_{k,j},a_{k,j})}\right)$

Now instantiating the above bound for $j=h$ and using the fact that
$V^{\star}_{h+1}(y)$ is bounded by $\Gamma(h)/\gamma(h)$ we get the following
bound on $e_{k,h}$.

$e_{k,h}\leq\frac{\Gamma(h+1)}{\gamma(h)}\left(\sqrt{\frac{L}{N_{k}(x_{k,h},a_{k,h})}}+\frac{L}{3N_{k}(x_{k,h},a_{k,h})}\right)$

Now we bound the term $c_{k,h}$ defined in eq. 9.

$\displaystyle c_{k,h}$
$\displaystyle=\frac{\gamma(h+1)}{\gamma(h)}\left[(\hat{P}_{k}-P)(V_{h,k+1}-V^{\star}_{h+1})\right](x_{k,h},a_{k,h})$
$\displaystyle=\frac{\gamma(h+1)}{\gamma(h)}\sum_{y}\left(\hat{P}_{k}(y|x_{k,h},a_{k,h})-P(y|x_{k,h},a_{k,h})\right)(V_{k,h+1}(y)-V^{\star}_{h+1}(y))$

We now substitute two bounds. First we can use Bernstein inequality to bound
the difference between estimated probability and actual probability as

$\left|\hat{P}_{k}(y|x_{k,h},a_{k,h})-P(y|x_{k,h},a_{k,h})\right|\leq\sqrt{\frac{2P(y|x_{k,h},a_{k,h})(1-P(y|x_{k,h},a_{k,h}))L}{N_{k}(x_{k,h},a_{k,h})}}+\frac{2L}{3N_{k}(x_{k,h},a_{k,h})}$

Second we bound $V_{k,h+1}(y)-V^{\star}_{h+1}(y)\leq
V_{k,h+1}(y)-V^{\pi_{k}}_{h+1}(y)\leq\widetilde{\Delta}_{k,h+1}(y)$. This
gives us the following bound on $c_{k,h}$.

$\displaystyle c_{k,h}$
$\displaystyle\leq\frac{\gamma(h+1)}{\gamma(h)}\sum_{y}\sqrt{\frac{2P(y|x_{k,h},a_{k,h})L}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(y)+\frac{\gamma(h+1)}{\gamma(h)}\sum_{y}\frac{2L}{3N_{k}(x_{k,h},a_{k,h})}\widetilde{\Delta}_{k,h+1}(y)$
$\displaystyle\leq\frac{\gamma(h+1)}{\gamma(h)}\sqrt{2L}\underbrace{\sum_{y}\sqrt{\frac{P(y|x_{k,h},a_{k,h})}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(y)}_{:=T_{1}}+\frac{2SL\Gamma(h+1)}{3\gamma(h)N_{k}(x_{k,h},a_{k,h})}$

We now bound the term labelled $T_{1}$. Let

$[y]_{k,h}=\left\\{y:P(y|x_{k,h},a_{k,h})N_{k}(x_{k,h},a_{k,h})\geq
2(h+1)^{2\beta}L\left(\frac{\Gamma(h+1)}{\gamma(h+1)}\right)^{2}\right\\}.$
(14)

Here we choose a threshold that is different than [AOM17]. In fact, we require
the additional $\textrm{poly}(h)$ factor to ensure convergence of the final
recurrence relation. Moreover, the threshold is parameterized by the parameter
$\beta$, and can be chosen based on the particular discount factor.

$T_{1}=\sum_{y\in[y]_{k,h}}\sqrt{\frac{P(y|x_{k,h},a_{k,h})}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(y)+\sum_{y\notin[y]_{k,h}}\sqrt{\frac{P(y|x_{k,h},a_{k,h})}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(y)$

The first term can be bounded as

$\displaystyle\sum_{y\in[y]_{k,h}}\sqrt{\frac{P(y|x_{k,h},a_{k,h})}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(y)$
$\displaystyle=\hat{\varepsilon}_{k,h}+\sqrt{\frac{P(x_{k,h+1}|x_{k,h},a_{k,h})}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(x_{k,h+1})\mathrm{1}\left\\{x_{k,h+1}\in[y]_{k,h}\right\\}$
$\displaystyle\leq\hat{\varepsilon}_{k,h}+\frac{\gamma(h+1)}{\sqrt{2L}(h+1)^{\beta}\Gamma(h+1)}\widetilde{\delta}_{k,h+1}$

where $\hat{\varepsilon}_{k,h}$ is an error term defined as follows.

$\displaystyle\hat{\varepsilon}_{k,h}$
$\displaystyle=\sum_{y\in[y]_{k,h}}\sqrt{\frac{P(y|x_{k,h},a_{k,h})}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(y)$
$\displaystyle-\sqrt{\frac{P(x_{k,h+1}|x_{k,h},a_{k,h})}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(x_{k,h+1})\mathrm{1}\left\\{x_{k,h+1}\in[y]_{k,h}\right\\}$
(15)

It can be checked that $\hat{\varepsilon}_{k,h}$ is actually a Martingale
difference sequence. The second term of $T_{1}$ can be bounded as

$\displaystyle\sum_{y\notin[y]_{k,h}}\sqrt{\frac{P(y|x_{k,h},a_{k,h})}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(y)$
$\displaystyle\leq\sum_{y\notin[y]_{k,h}}\frac{\sqrt{P(y|x_{k,h},a_{k,h})N_{k}(x_{k,h},a_{k,h})}}{N_{k}(x_{k,h},a_{k,h})}\widetilde{\Delta}_{k,h+1}(y)$
$\displaystyle\leq\frac{\sqrt{2L}(h+1)^{\beta}S}{N_{k}(x_{k,h},a_{k,h})}\left(\frac{\Gamma(h+1)}{\gamma(h+1)}\right)^{2}$

Substituting the bound on $T_{1}$ in the upper bound on $c_{k,h}$ we get the
following bound.

$\displaystyle c_{k,h}$
$\displaystyle\leq\frac{\gamma(h+1)}{\gamma(h)}\sqrt{2L}\left(\hat{\varepsilon}_{k,h}+\frac{\gamma(h+1)}{\sqrt{2L}(h+1)^{\beta}\Gamma(h+1)}\widetilde{\delta}_{k,h+1}+\frac{\sqrt{2L}(h+1)^{\beta}S}{N_{k}(x_{k,h},a_{k,h})}\left(\frac{\Gamma(h+1)}{\gamma(h+1)}\right)^{2}\right)$
$\displaystyle+\frac{2SL\Gamma(h+1)}{3\gamma(h)N_{k}(x_{k,h},a_{k,h})}$
$\displaystyle\leq\frac{\gamma(h+1)}{\gamma(h)}\sqrt{2L}\hat{\varepsilon}_{k,h}+\frac{(\gamma(h+1))^{2}}{\gamma(h)\Gamma(h+1)(h+1)^{\beta}}\widetilde{\delta}_{k,h+1}+\underbrace{\frac{(h+1)^{\beta}(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}\frac{2LS}{N_{k}(x_{k,h},a_{k,h})}}_{:=f_{k,h}}$

Substituting the previous upper bound on $c_{h,k}$ in eq. 13 and writing
$\overline{\varepsilon}_{k,h}=\gamma(h+1)/\gamma(h)\hat{\varepsilon}_{k,h}$ we
get the final recurrence relation for $\widetilde{\delta}_{k,h}$.

$\widetilde{\delta}_{k,h}\leq\frac{\gamma(h+1)}{\gamma(h)}\left(1+\frac{\gamma(h+1)}{(h+1)^{\beta}\Gamma(h+1)}\right)\widetilde{\delta}_{k,h+1}+\sqrt{2L}\overline{\varepsilon}_{k,h}+e_{k,h}+b_{k,h}+\varepsilon_{k,h}+f_{k,h}$
(16)

Then expanding the recurrence relation eq. 16 from $h=1$ to $h=N(\Delta)$ we
get the following equation.

$\widetilde{\delta}_{k,1}\leq
t(N(\Delta)+1)\widetilde{\delta}_{k,N(\Delta)+1}+\sum_{h=1}^{N(\Delta)}t(h)\left(\sqrt{2L}\overline{\varepsilon}_{k,h}+e_{k,h}+b_{k,h}+\varepsilon_{k,h}+f_{k,h}\right)$
(17)

We now use the fact that
$\widetilde{\delta}_{k,N(\Delta)+1}\leq\Delta/\gamma(N(\Delta)+1)$ and obtain
the following bound on $\widetilde{\delta}_{k,1}$.

$\widetilde{\delta}_{k,1}\leq\frac{\Delta}{\gamma(N(\Delta)+1)}t(N(\Delta)+1)+\sum_{h=1}^{N(\Delta)}t(h)\left(\sqrt{2L}\overline{\varepsilon}_{k,h}+e_{k,h}+b_{k,h}+\varepsilon_{k,h}+f_{k,h}\right)$

Summing over the $T$ episodes the final bound on regret is given as.

$\textrm{Reg}(T)\leq\sum_{k=1}^{T}\widetilde{\delta}_{k,1}\leq\frac{\Delta
T}{\gamma(N(\Delta)+1)}t(N(\Delta)+1)+\sum_{k=1}^{T}\sum_{h=1}^{N(\Delta)}t(h)\left(\sqrt{2L}\overline{\varepsilon}_{k,h}+e_{k,h}+b_{k,h}+\varepsilon_{k,h}+f_{k,h}\right)$
(18)

We now bound the second term. First consider the exploration bonus term
$b_{k,h}$.

$\displaystyle\sum_{k=1}^{T}\sum_{h=1}^{N(\Delta)}t(h)b_{k,h}$
$\displaystyle=\sum_{k=1}^{T}\sum_{h=1}^{N(\Delta)}t(h)\frac{\Gamma(h+1)}{\gamma(h)}\frac{L}{\sqrt{N_{k}(x_{k,h},a_{k,h})}}$
$\displaystyle\leq
L\max_{h\in[N(\Delta)]}t(h)\frac{\Gamma(h+1)}{\gamma(h)}\sum_{k,h}\frac{1}{\sqrt{N_{k}(x_{k,h},a_{k,h})}}$

Using a simple counting argument we can bound the last summation as follows.
Here we use the fact that only the first $N(\Delta)$ steps of each episode are
used to update the $N_{k}(\cdot,\cdot)$ counters.

$\displaystyle\sum_{k=1}^{T}\sum_{h=1}^{N(\Delta)}\frac{1}{\sqrt{N_{k}(x_{k,h},a_{k,h})}}$
$\displaystyle=\sum_{x,a}\sum_{n=1}^{N_{T}(x,a)}\frac{1}{\sqrt{n}}\leq
2\sum_{x,a}\sqrt{N_{k}(x,a)}$ $\displaystyle\leq
2\sqrt{SA}\sqrt{\sum_{x,a}N_{T}(x,a)}=2\sqrt{SATN(\Delta)}$

This result gives us the following bound on the sum of $b_{k,h}$terms.

$\sum_{k=1}^{T}\sum_{h=1}^{N(\Delta)}t(h)b_{k,h}=L\max_{h\in[N(\Delta)]}t(h)\frac{\Gamma(h+1)}{\gamma(h)}{O}\left(\sqrt{SATN(\Delta)}\right)$
(19)

By a similar argument we can prove the following bounds on the $e_{k,h}$ and
$f_{k,h}$ terms.

$\sum_{k=1}^{T}\sum_{h=1}^{N(\Delta)}t(h)e_{k,h}=L\max_{h\in[N(\Delta)]}t(h)\frac{\Gamma(h+1)}{\gamma(h)}{O}\left(\sqrt{SATN(\Delta)}\right)$
(20)

$\sum_{k=1}^{T}\sum_{h=1}^{N(\Delta)}t(h)f_{k,h}\leq
L\max_{h\in[N(\Delta)]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}{O}\left({S^{2}A(N(\Delta))^{\beta}\log(TN(\Delta))}\right)$
(21)

We now consider the martingale differences term $\varepsilon_{k,h}$ and
$\overline{\varepsilon}_{k,h}$. If we write $\mathcal{F}_{k,h}$ to denote the
sigma-algebra generated by the actions, and states until step $h$ of episode
$k$, then we have $\mathbb{E}[\varepsilon_{k,h}|\mathcal{F}_{k,h}]=0$.
Moreover, each $\varepsilon_{k,h}$ is bouned by
$O\left(\frac{\Gamma(h+1)}{\gamma(h)}\right)$. So we can define a new set of
martingales
$\widetilde{\varepsilon}_{k,h}=\epsilon_{k,h}\frac{\gamma(h)}{\Gamma(h+1)}$ so
that $\left|\widetilde{\varepsilon}_{k,h}\right|\leq 1$. Now, we can apply the
Azuma-Hoeffding inequality to get the following result with probability at
least $1-\delta$.

$\displaystyle\sum_{k=1}^{T}\sum_{h=1}^{N(\Delta)}t(h)\varepsilon_{k,h}$
$\displaystyle\leq\max_{h\in[N(\Delta)]}t(h)\frac{\Gamma(h+1)}{\gamma(h)}\sum_{k=1}^{T}\sum_{h=1}^{N(\Delta)}\left|\widetilde{\varepsilon}_{k,h}\right|$
$\displaystyle\leq\max_{h\in[N(\Delta)]}t(h)\frac{\Gamma(h+1)}{\gamma(h)}O\left(\sqrt{TN(\Delta)\log(TN(\Delta)/\delta)}\right)$
(22)

Now recall that we defined
$\overline{\varepsilon}_{k,h}=\frac{\gamma(h+1)}{\gamma(h)}\hat{\varepsilon}_{k,h}$
where $\hat{\varepsilon}_{k,h}$ was defined in equation 15. This gives us the
following expression for $\overline{\varepsilon}_{k,h}$.

$\displaystyle\overline{\varepsilon}_{k,h}$
$\displaystyle=\frac{\gamma(h+1)}{\gamma(h)}\sum_{y\in[y]_{k,h}}\sqrt{\frac{P(y|x_{k,h},a_{k,h})}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(y)$
$\displaystyle-\frac{\gamma(h+1)}{\gamma(h)}\sqrt{\frac{P(x_{k,h+1}|x_{k,h},a_{k,h})}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(x_{k,h+1})\mathrm{1}\left\\{x_{k,h+1}\in[y]_{k,h}\right\\}$

It can be easily verified that
$\mathbb{E}[\varepsilon_{k,h}|\mathcal{F}_{k,h}]=0$. We now establish an upper
bound on $\overline{\varepsilon}_{k,h}$. Consider the first term in the
definition of $\overline{\varepsilon}_{k,h}$.

$\displaystyle\frac{\gamma(h+1)}{\gamma(h)}\sum_{y\in[y]_{k,h}}\sqrt{\frac{P(y|x_{k,h},a_{k,h})}{N_{k}(x_{k,h},a_{k,h})}}\widetilde{\Delta}_{k,h+1}(y)$
$\displaystyle=\frac{\gamma(h+1)}{\gamma(h)}\sum_{y\in[y]_{k,h}}{\frac{P(y|x_{k,h},a_{k,h})}{\sqrt{P(y|x_{k,h},a_{k,h})N_{k}(x_{k,h},a_{k,h})}}}\widetilde{\Delta}_{k,h+1}(y)$
$\displaystyle\leq\frac{1}{\sqrt{2L}(h+1)^{\beta}}\frac{\gamma(h+1)}{\gamma(h)}\frac{\gamma(h+1)}{\Gamma(h+1)}\frac{\Gamma(h+1)}{\gamma(h+1)}\leq\frac{1}{2\sqrt{L}}\frac{\gamma(h+1)}{\gamma(h)}$

The last inequality uses the definition of $[y]_{k,h}$ (eq. 14).The second
term of $\overline{\varepsilon}_{k,h}$ can be bounded similarly. Therefore,
again using Azuma-Hoeffding inequality, we get the following result with
probability at least $1-\delta$.

$\sum_{k=1}^{T}\sum_{h=1}^{N(\Delta)}\sqrt{2L}t(h)\overline{\varepsilon}_{k,h}\leq\max_{h\in[N(\Delta)]}t(h)\frac{\gamma(h+1)}{\gamma(h)}O\left(\sqrt{TN(\Delta)\log(TN(\Delta)/\delta)}\right)$
(23)

Substituting equations 19, 20, 21, 22, 23 in equation 18 we get the final
bound on regret. ∎

######  Lemma 4 (Bernstein’s Inequality).

Let $Z_{1},\ldots,Z_{n}$ be i.i.d. random variables with values bounded by $H$
and let $\delta>0$. Then with probability at least $1-\delta$ we have

$\mathbb{E}Z_{1}-\frac{1}{n}\sum_{i=1}^{n}Z_{i}\leq\sqrt{\frac{2\textrm{Var}(Z_{1})\ln(2/\delta)}{n}}+{\frac{2H\ln(2/\delta)}{3n}}$

###  D.2 Proof of Corollary 2

###### Proof.

Consider the discount factor $\gamma(h)=h^{-p}$ for $p\geq 2$. Recall that we
defined $\Gamma(h)=\sum_{j\geq h}\gamma(j)$. We will use the following bound
on
$\Gamma(h)\in\left[\frac{h^{-p+1}}{p-1},h^{-p}\left(1+\frac{h}{p-1}\right)\right]$.
We substitute $\beta=p-1$ and bound various $\gamma$-dependent constants
appearing in the regret bound.

$\frac{t(N(\Delta)+1)}{\gamma(N(\Delta)+1)}=\prod_{j=2}^{N(\Delta)+1}\left(1+\frac{\gamma(j)}{{j^{\beta}}\Gamma(j)}\right)\leq\prod_{j=2}^{N(\Delta)+1}\left(1+\frac{p-1}{j^{1+\beta}}\right)\leq
e^{(p-1)\sum_{j}j^{-p}}\leq e$
$\displaystyle\max_{h\in[N(\Delta)]}t(h)\frac{\Gamma(h+1)}{\gamma(h)}=\max_{h\in[N(\Delta)]}\Gamma(h+1)\prod_{j=2}^{h}\left(1+\frac{\gamma(j)}{{j^{\beta}}\Gamma(j)}\right)\leq
e\max_{h\in[N(\Delta)]}h^{-p}\left(1+\frac{h}{p-1}\right)=e$

The last inequality follows because the final term is a decreasing function of
$h$ for $p>1$.

$\displaystyle\max_{h\in[N(\Delta)]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}$
$\displaystyle=\max_{h\in[N(\Delta)]}\frac{(\Gamma(h+1))^{2}}{\gamma(h+1)}\prod_{j=2}^{h}\left(1+\frac{\gamma(j)}{{j^{\beta}}\Gamma(j)}\right)$
$\displaystyle\leq
e\max_{h\in[N(\Delta)]}(h+1)^{-p}\left(1+\frac{h+1}{p-1}\right)^{2}\leq e$

Here we use $p\geq 2$ to conclude that the term inside max is non-increasing.
We now bound the term $N(\Delta)$. Recall that $N(\Delta)$ is the value of $h$
such that $\Gamma(h)$ is bounded from above by $\Delta$. Using the lower bound
of $h^{-p+1}/(p-1)$ we get $N(\Delta)$ should be at least
$(\Delta(p-1))^{-1/(p-1)}$.Substituting the value of $N(\Delta)$ and the bound
on the three constants in the expression for regret, we get the following
bound on regret.

$\displaystyle\textrm{Reg}(T)\leq e\Delta T$
$\displaystyle+e\left(\Delta(p-1)\right)^{-\frac{1}{2(p-1)}}\left[\widetilde{O}(\sqrt{SAT})+\widetilde{O}(\sqrt{T})\right]$
$\displaystyle+e\left(\Delta(p-1)\right)^{-\frac{1/2}{p-1}}\widetilde{O}(S^{2}A)$

For $T\geq O(S^{3}A)$ then the last term is dominated by the other terms in
the expression above. Finally, substituting
$\Delta=T^{-\frac{p-1}{2p-1}}(p-1)^{-\frac{1}{2p-1}}$ we get the following
bound on regret.

$\textrm{Reg}(T)\leq(p-1)^{-\frac{1}{2p-1}}S^{1/2}A^{1/2}T^{\frac{p}{2p-1}}=O\left(S^{1/2}A^{1/2}T^{\frac{p}{2p-1}}\right)$

The last equality uses the fact that $p^{-O(1/p)}=O(1)$ for $p\geq 2$.

$1<p<2$: We now substitute $\beta=p-1$. Proceeding similarly as earlier, we
can establish the following inequalities.

$\frac{t(N(\Delta)+1)}{\gamma(N(\Delta)+1)}\leq e^{(p-1)/\beta}=e$
$\max_{h\in[N(\Delta)]}t(h)\frac{\Gamma(h+1)}{\gamma(h)}\leq
e^{2}\max_{h\in[N(\Delta)]}h^{-p}\left(1+\frac{h}{p-1}\right)\leq
e\frac{p}{p-1}$

The third term is different for the case of $1<p<2$.

$\displaystyle\max_{h\in[N(\Delta)]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}$
$\displaystyle\leq
e\max_{h\in[N(\Delta)]}(h+1)^{-p}\left(1+\frac{h+1}{p-1}\right)^{2}$
$\displaystyle\leq
e\max_{h\in[N(\Delta)]}(h+1)^{-p}\left(1+2\frac{h+1}{p-1}+\frac{(h+1)^{2}}{(p-1)^{2}}\right)$
$\displaystyle\leq
e\left(\frac{p}{2(p-1)}+\frac{(1+N(\Delta))^{2-p}}{(p-1)^{2}}\right)\leq\frac{2e}{p-1}(N(\Delta))^{2-p}$

We now substitute the inequalities above and use
$N(\Delta)=(\Delta(p-1))^{-1/(p-1)}$.

$\displaystyle\textrm{Reg}(T)$ $\displaystyle\leq e\Delta
T+e\frac{p}{p-1}\sqrt{SAT}(\Delta(p-1))^{-1/2(p-1)}$
$\displaystyle+\frac{2e}{p-1}(\Delta(p-1))^{-1/(p-1)}S^{2}A\log(T)+e\sqrt{T\log
T}(\Delta(p-1))^{-1/2(p-1)}$

We substitute $\Delta=T^{-\frac{p-1}{2p-1}}$ to get the following bound on
regret.

$\displaystyle\textrm{Reg}(T)$ $\displaystyle\leq
eT^{p/(2p-1)}+e\frac{p}{p-1}(p-1)^{-1/2(p-1)}T^{p/(2p-1)}\sqrt{SA}$
$\displaystyle+\frac{2e}{p-1}(p-1)^{-1/(p-1)}T^{1/(2p-1)}S^{2}A\log
T+e(p-1)^{-1/2(p-1)}T^{p/(2p-1)}\sqrt{\log T}$

If $T\geq O\left((S^{3}A)^{(2p-1)/2(p-1)}\right)$ then the first term
dominates the third term and we get the following bound on regret.

$\textrm{Reg}(T)\leq 4e\frac{p}{p-1}T^{\frac{p}{2p-1}}\sqrt{SA\log
T}(p-1)^{-1/(p-1)}$

∎

###  D.3 Proof of Corollary 3

###### Proof.

For discount factor $\gamma(h)=\gamma^{h-1}$, it is easy to check that
$\Gamma(h)=\gamma^{h-1}/(1-\gamma)$. We will substitute $\beta=3/2$ and use
the following inequality.

$\prod_{j=2}^{h}\left(1+\frac{\gamma(j)}{{j^{\beta}}\Gamma(j)}\right)=\prod_{j=2}^{h}\left(1+\frac{1-\gamma}{{j^{3/2}}}\right)=\exp\left((1-\gamma)\sum_{j=2}^{h}\frac{1}{{j^{3/2}}}\right)\leq
e^{1-\gamma}$

This gives the following bounds on the three constants.

$\frac{t(N(\Delta)+1)}{\gamma(N(\Delta)+1)}=\prod_{j=2}^{N(\Delta)+1}\left(1+\frac{\gamma(j)}{{j^{\beta}}\Gamma(j)}\right)\leq
e^{1-\gamma}$
$\displaystyle\max_{h\in[N(\Delta)]}t(h)\frac{\Gamma(h+1)}{\gamma(h)}$
$\displaystyle=\max_{h\in[N(\Delta)]}\Gamma(h+1)\prod_{j=2}^{h}\left(1+\frac{\gamma(j)}{{j^{\beta}}\Gamma(j)}\right)$
$\displaystyle\leq\max_{h\in[N(\Delta)]}\frac{\gamma^{h}}{1-\gamma}e^{1-\gamma}\leq\frac{\gamma}{1-\gamma}e^{1-\gamma}$

Now let us consider the second constant.

$\displaystyle\max_{h\in[N(\Delta)]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}$
$\displaystyle=\max_{h\in[N(\Delta)]}\frac{(\Gamma(h+1))^{2}}{\gamma(h+1)}\prod_{j=2}^{h}\left(1+\frac{\gamma(j)}{{j^{\beta}}\Gamma(j)}\right)$
$\displaystyle\leq\max_{h\in[N(\Delta)]}\frac{\gamma^{h}}{(1-\gamma)^{2}}e^{1-\gamma}\leq\frac{\gamma}{(1-\gamma)^{2}}e^{1-\gamma}$

Since $\Gamma(h)=\gamma^{h}/(1-\gamma)$, it is easy to show that
$N(\Delta)=\frac{\log(1/\Delta(1-\gamma))}{\log(1/\gamma)}$. Substituting the
bounds on the constants and the bound on $N(\Delta)$ we get the following
bound on the regret.

$\displaystyle\textrm{Reg}(T)$ $\displaystyle\leq e^{1-\gamma}\Delta
T+\frac{e^{1-\gamma}}{1-\gamma}\sqrt{\frac{\log(1/\Delta(1-\gamma))}{\log(1/\gamma)}}\left(\widetilde{O}(\sqrt{SAT})+\widetilde{O}(\sqrt{T})\right)$
$\displaystyle+\frac{e^{1-\gamma}}{(1-\gamma)^{2}}\left(\frac{\log(1/\Delta(1-\gamma))}{\log(1/\gamma)}\right)^{\beta}\widetilde{O}(S^{2}A)$

If $T\geq\frac{1}{(1-\gamma)^{2}}(N(\Delta))^{2}\widetilde{O}(S^{3}A)$ then
the last term in the expression is dominated by the other terms. We further
use the inequality $\log(1/\gamma)\geq 1-\gamma$ to simplify the regret
expression.

$\textrm{Reg}(T)\leq e^{1-\gamma}\Delta
T+\frac{1}{(1-\gamma)^{1.5}}\sqrt{\log(1/\Delta(1-\gamma))}\widetilde{O}(\sqrt{SAT})$

to get a regret bound of
$\widetilde{O}\left(\frac{\sqrt{SAT}}{(1-\gamma)^{1.5}}\right)$. Notice that
we need to satisfy the following bound on $T$.

$T\geq\frac{1}{(1-\gamma)^{2}}\left(\frac{\log(1/\Delta(1-\gamma))}{\log(1/\gamma)}\right)^{2}\widetilde{O}(S^{3}A)$

For $\Delta=T^{-1}/(1-\gamma)$ the above bound is equivalent to the condition
$T\geq\widetilde{O}\left(S^{3}A/(1-\gamma)^{4}\right)$ ∎

##  Appendix E Proof of theorem 4 and Related Corollaries

We first provide a formal statement of theorem 4.

######  Theorem 8.

When run with horizon length $H^{\star}$, algorithm 2 has the following regret
bound with probability at least $1-\delta$

$\displaystyle\textrm{Reg}(\pi;\boldsymbol{\gamma})\leq\min_{L\in[T]}\left(T\Gamma(L+1)+2L\log(T)\sqrt{T})\right)+\Gamma(H^{\star}+1)T+\widetilde{O}\left(\sqrt{T}\right)$
$\displaystyle+\log(T)\frac{t(H^{\star}+1)}{\gamma(H^{\star}+1)}g(H^{\star}+1)+\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\Gamma(h+1)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)\widetilde{O}\left(\sqrt{SATH^{\star}}\right)$
$\displaystyle+\log^{2}(T)\log(TH^{\star})\max_{h\in[H^{\star}]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}g(h)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)^{2}O\left(S^{2}A(H^{\star})^{\beta}\right)$
$\displaystyle+\log^{5/2}(T)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}\gamma(h+1)g(h)\left(1+\frac{O(T^{-1/4})}{\gamma(h+1)}\right)O\left(\sqrt{TH^{\star}\log(TH^{\star}/\delta)}\right)$

where
$g(h)=\exp\left\\{O\left(\sum_{k=2}^{h}\frac{T^{-1/4}}{\gamma(k)+k^{\beta}\Gamma(k)}\right)\right\\}$.

###### Proof.

Since each $\hat{\gamma}_{j}$ is the empirical distribution function, by the
Dvoretzky–Kiefer–Wolfowitz inequality [DKW56, Mas90] and a union bound over
the $\log(T/B)$ blocks the following result holds.

$\Pr\left(\forall
j\sup_{h}\left|\hat{\gamma}_{j}(h)-\gamma(h)\right|>\sqrt{\frac{\log\left(2\log(T/B)/\delta\right)}{2^{j}B}}\right)\leq\delta$

For the remainder of the proof we will assume
$\left\lVert\hat{\gamma}_{j}-\gamma\right\rVert_{\infty}\leq\varepsilon_{j}$
for
$\varepsilon_{j}=\sqrt{\frac{\log\left(2\log(T/B)/\delta\right)}{2^{j}B}}$.
Now consider any $j>1$. Since algorithm 1 is run for $2^{j}B$ episodes with
estimate $\hat{\gamma}_{j}$ we have

$\sum_{k\in
B_{j}}V^{\star}(x_{k,1};\widehat{\boldsymbol{\gamma}}_{j})-V^{\pi_{k}}(x_{k,1};\widehat{\boldsymbol{\gamma}}_{j})\leq\mathcal{R}(H^{\star},\hat{\Delta}_{j},2^{j}B,\widehat{\boldsymbol{\gamma}}_{j})$

Here we write $B_{j}$ to denote the episodes in block $j$ and
$\mathcal{R}(H,\Delta,T,\widehat{\boldsymbol{\gamma}}_{j})$ is the regret
bound derived in theorem 1 with $N(\Delta)=H$ and discount factor
$\widehat{\boldsymbol{\gamma}}_{j}$. We establish a lower bound on
$V^{\star}(x_{k,1};\widehat{\boldsymbol{\gamma}}_{j})$.

$\displaystyle V^{\star}(x_{k,1};\boldsymbol{\gamma})$
$\displaystyle=\mathbb{E}_{\pi^{\star}(\boldsymbol{\gamma})}\left[\sum_{h=1}^{\infty}\gamma(h)r(x_{k,h},a_{k,h})\right]$
$\displaystyle\leq\mathbb{E}_{\pi^{\star}(\boldsymbol{\gamma})}\left[\sum_{h=1}^{L}\gamma(h)r(x_{k,h},a_{k,h})\right]+\Gamma(L+1)$
$\displaystyle\leq\mathbb{E}_{\pi^{\star}(\boldsymbol{\gamma})}\left[\sum_{h=1}^{L}\hat{\gamma}_{j}(h)r(x_{k,h},a_{k,h})\right]+\varepsilon_{j}L+\Gamma(L+1)$
$\displaystyle\leq
V^{\star}(x_{k,1};\widehat{\boldsymbol{\gamma}}_{j})+\varepsilon_{j}L+\Gamma(L+1)$

The first inequality uses the fact that rewards are bounded by $1$ and
$\Gamma(L+1)=\sum_{h\geq L+1}\gamma(h)$. The second inequality uses
$\max_{h}\left|\hat{\gamma}_{j}(h)-\gamma(h)\right|\leq\varepsilon_{j}$. This
gives us the following lower bound.

$V^{\star}(x_{k,1};\widehat{\boldsymbol{\gamma}}_{j})\geq
V^{\star}(x_{k,1};\boldsymbol{\gamma})-\varepsilon_{j}L-\Gamma(L+1)$ (24)

We now derive an upper bound on
$V^{\pi_{k}}(x_{k,1};\widehat{\boldsymbol{\gamma}}_{j})$.

$\displaystyle V^{\pi_{k}}(x_{k,1};\boldsymbol{\gamma})$
$\displaystyle=\mathbb{E}_{\pi^{k}}\left[\sum_{h=1}^{\infty}\gamma(h)r(x_{k,h},a_{k,h})\right]$
$\displaystyle\geq\mathbb{E}_{\pi_{k}}\left[\sum_{h=1}^{L}\gamma(h)r(x_{k,h},a_{k,h})\right]-\Gamma(L+1)$
$\displaystyle\geq\mathbb{E}_{\pi_{k}}\left[\sum_{h=1}^{L}\hat{\gamma}(h)r(x_{k,h},a_{k,h})\right]-\varepsilon_{j}L-\Gamma(L+1)$
$\displaystyle=V^{\pi_{k}}(x_{k,1};\widehat{\boldsymbol{\gamma}}_{j})-\mathbb{E}_{\pi_{k}}\left[\sum_{h=L+1}^{\infty}\hat{\gamma}(h)r(x_{k,h},a_{k,h})\right]-\varepsilon_{j}L-\Gamma(L+1)$
$\displaystyle\geq
V^{\pi_{k}}(x_{k,1};\widehat{\boldsymbol{\gamma}}_{j})-\hat{\Gamma}_{j}(L+1)-\varepsilon_{j}L-\Gamma(L+1)$
(25)

We now use lemma 5 with $D=T$ and a union bound over the $\log(T/B)$ blocks to
get the following bound for all $j\in[\log(T/B)]$ and $h\in[T]$.

$\left|\hat{\Gamma}_{j}(h)-\Gamma(h)\right|\leq\sqrt{\frac{\log
T+\log(\log(T/B)/\delta)}{\left|B_{j}\right|}}\leq\left(1+\sqrt{\log
T}\right)\varepsilon_{j}$

Substituting the above bound in equation 25 and rearranging we get the
following bound.

$\displaystyle V^{\pi_{k}}(x_{k,1};\widehat{\boldsymbol{\gamma}})\leq
V^{\pi_{k}}(x_{k,1};\boldsymbol{\gamma})+\varepsilon_{j}\left(L+1+\sqrt{\log
T}\right)$ (26)

Using equations 24 and 26 we can bound the regret of algorithm 2 during the
episodes of block $B_{j}$.

$\displaystyle\sum_{k\in
B_{j}}V^{\star}(x_{k,1};\boldsymbol{\gamma})-V^{\pi_{k}}(x_{k,1};\boldsymbol{\gamma})$
$\displaystyle\leq\sum_{k\in
B_{j}}V^{\star}(x_{k,1};\widehat{\boldsymbol{\gamma}})-V^{\pi_{k}}(x_{k,1};\widehat{\boldsymbol{\gamma}})+\Gamma(L+1)+\varepsilon_{j}\left(2L+1+\sqrt{\log
T}\right)$
$\displaystyle\leq\mathcal{R}(H^{\star},\hat{\Delta}_{j},2^{j}B,\widehat{\boldsymbol{\gamma}}_{j})+\left|B_{j}\right|\Gamma(L+1)+\left|B_{j}\right|\varepsilon_{j}\left(2L+1+\sqrt{\log
T}\right)$

We use the fact that
$\varepsilon_{j}=\sqrt{\frac{\log(2\log(T/B)/\delta}{\left|B_{j}\right|}}$ and
sum over all $j=1,\ldots,\log(T/B)$.

$\displaystyle\sum_{t=1}^{T}V^{\star}(x_{t,1};\boldsymbol{\gamma})-V^{\pi_{t}}(x_{t,1};\boldsymbol{\gamma})$
$\displaystyle\leq\sum_{j=1}^{\log(T/B)}\mathcal{R}(H^{\star},\hat{\Delta}_{j},2^{j}B,\widehat{\boldsymbol{\gamma}}_{j})$
$\displaystyle+\sum_{j}\left|B_{j}\right|\Gamma(L+1)+\sum_{j=1}^{\log(T/B)}\sqrt{\log(2\log(T/B)/\delta)}{O}\sqrt{\left|B_{j}\right|}\left(2L+1+\sqrt{\log
T}\right)$

Now we use $\sum_{j}\left|B_{j}\right|=T$ and
$\sum_{j}\sqrt{\left|B_{j}\right|}\leq\sqrt{\log(T/B)}\sqrt{\sum_{j}\left|B_{j}\right|}={O}\left(\sqrt{T\log(T/B)}\right)$,
and $B=\sqrt{T}\log T\log(\log(T)/\delta)$ to get the following bound on
regret.

$\displaystyle\sum_{t=1}^{T}V^{\star}(x_{t,1};\boldsymbol{\gamma})-V^{\pi_{t}}(x_{t,1};\boldsymbol{\gamma})$
$\displaystyle\leq\sum_{j=1}^{\log(T/B)}\mathcal{R}(H^{\star},\hat{\Delta}_{j},2^{j}B,\widehat{\boldsymbol{\gamma}}_{j})$
$\displaystyle+\min_{L\in[T]}\left(T\Gamma(L+1)+2L\log(T)\sqrt{T})\right)$

We now bound the first term by substituting the definition of of
$\mathcal{R}(H^{\star},\hat{\Delta}_{j},\left|B_{j}\right|,\widehat{\boldsymbol{\gamma}}_{j})$.

$\displaystyle\begin{split}\sum_{j=1}^{\log(T/B)}\mathcal{R}(H^{\star},\hat{\Delta}_{j},\left|B_{j}\right|,\widehat{\boldsymbol{\gamma}}_{j})&\leq\sum_{j=1}^{\log(T/B)}\frac{\hat{\Delta}_{j}\left|B_{j}\right|}{\hat{\gamma}_{j}(H^{\star}+1)}\hat{t}_{j}(H^{\star}+1)\\\
&+\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\hat{t}_{j}(h)\frac{\hat{\Gamma}_{j}(h+1)}{\hat{\gamma}_{j}(h)}{O}\left(\sqrt{SA\left|B_{j}\right|H^{\star}}\right)\\\
&+\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\hat{t}_{j}(h)\frac{(\hat{\Gamma}_{j}(h+1))^{2}}{\hat{\gamma}_{j}(h)\hat{\gamma}_{j}(h+1)}{O}\left({S^{2}A{H^{\star}}^{\beta}\log(\left|B_{j}\right|H^{\star})}\right)\\\
&+\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\hat{t}_{j}(h)\frac{\hat{\gamma}_{j}(h+1)}{\hat{\gamma}_{j}(h)}O\left(\sqrt{\left|B_{j}\right|H^{\star}\log(\left|B_{j}\right|H^{\star}/\delta)}\right)\end{split}$
(27)

We now bound the four terms separately. We will frequently use the following
two identities.

$\sum_{j=1}^{\log(T/B)}\varepsilon_{j}\leq\sum_{j=1}^{\infty}\frac{\varepsilon_{1}}{(\sqrt{2})^{j-1}}={O}\left(\sqrt{\frac{\log(\log(T/B)/\delta)}{B}}\right)$
(28)

$\displaystyle\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\frac{\hat{t}_{j}(h)}{\hat{\gamma}_{j}(h)}=\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\prod_{k=2}^{h}\left(1+\frac{\hat{\gamma}_{j}(k)}{k^{\beta}\hat{\Gamma}_{j}(k)}\right)$
$\displaystyle\leq\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\prod_{k=2}^{h}\left(1+\frac{\gamma(k)}{k^{\beta}\Gamma(k)}+\frac{2\varepsilon_{j}\sqrt{\log
T}}{k^{\beta}\Gamma(k)}\right)\quad\textrm{[By lemma~{}\ref{lem:ratio-
inequality}]}$
$\displaystyle=\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}\prod_{k=2}^{h}\left(1+\frac{2\varepsilon_{j}\sqrt{\log
T}}{\gamma(k)+k^{\beta}\Gamma(k)}\right)$
$\displaystyle\leq\log(T/B)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}\sum_{j=1}^{\log(T/B)}\prod_{k=2}^{h}\left(1+\frac{2\varepsilon_{j}\sqrt{\log
T}}{\gamma(k)+k^{\beta}\Gamma(k)}\right)$
$\displaystyle\leq\log(T/B)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}\sum_{j=1}^{\log(T/B)}\exp\left\\{\sum_{k=2}^{h}\frac{2\varepsilon_{j}\sqrt{\log
T}}{\gamma(k)+k^{\beta}\Gamma(k)}\right\\}$
$\displaystyle\leq\log(T/B)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}\exp\left\\{\sum_{j=1}^{\log(T/B)}\sum_{k=2}^{h}\frac{2\varepsilon_{j}\sqrt{\log
T}}{\gamma(k)+k^{\beta}\Gamma(k)}\right\\}$
$\displaystyle\leq\log(T/B)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}\exp\left\\{{O}\left(\sqrt{\frac{\log(\log(T/B)/\delta)}{B}}\sum_{k=2}^{h}\frac{2\sqrt{\log
T}}{\gamma(k)+k^{\beta}\Gamma(k)}\right)\right\\}\quad\textrm{[By
eq.~{}\ref{eq:bound-sum-eps}]}$
$\displaystyle\leq\log(T)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}\exp\left\\{{O}\left(\sum_{k=2}^{h}\frac{T^{-1/4}}{\gamma(k)+k^{\beta}\Gamma(k)}\right)\right\\}\quad\textrm{[As
$B=\sqrt{T}\log T\log(\log(T)/\delta)$]}$

Now writing
$g(h)=\exp\left\\{{O}\left(\sum_{k=2}^{h}\frac{T^{-1/4}}{\gamma(k)+k^{\beta}\Gamma(k)}\right)\right\\}$
we get the following inequality.

$\displaystyle\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\frac{\hat{t}_{j}(h)}{\hat{\gamma}_{j}(h)}\leq\log(T)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)$
(29)
$\displaystyle\sum_{j=1}^{\log(T/B)}\frac{\hat{\Delta}_{j}\left|B_{j}\right|}{\hat{\gamma}_{j}(H^{\star}+1)}\hat{t}_{j}(H^{\star}+1)=\sum_{j=1}^{\log(T/B)}\frac{\hat{\Gamma}_{j}(H^{\star}+1)\left|B_{j}\right|}{\hat{\gamma}_{j}(H^{\star}+1)}\hat{t}_{j}(H^{\star}+1)$
$\displaystyle\leq\sum_{j=1}^{\log(T/B)}\left(\Delta^{\star}+2\varepsilon_{j}\sqrt{\log
T}\right)\left|B_{j}\right|\frac{\hat{t}_{j}(H^{\star}+1)}{\hat{\gamma}_{j}(H^{\star}+1)}\quad\textrm{[Since
$\Delta^{\star}=\Gamma(H^{\star}+1)$, and using lemma~{}\ref{lem:bound-
Gamma}]}$
$\displaystyle\leq\sum_{j=1}^{\log(T/B)}\left(\Delta^{\star}+2\varepsilon_{j}\sqrt{\log
T}\right)\left|B_{j}\right|\sum_{j=1}^{\log(T/B)}\frac{\hat{t}_{j}(H^{\star}+1)}{\hat{\gamma}_{j}(H^{\star}+1)}\quad\textrm{[Since
$\sum_{i}a_{i}b_{i}\leq\sum_{i}a_{i}\sum_{i}b_{i}$ for $a_{i},b_{i}\geq 0$.]}$

The first summation can be bounded as follows.

$\displaystyle\sum_{j=1}^{\log(T/B)}\left(\Delta^{\star}+2\varepsilon_{j}\sqrt{\log
T}\right)\left|B_{j}\right|$ $\displaystyle=\Delta^{\star}T+2\sqrt{\log
T}\sum_{j}\varepsilon_{j}\left|B_{j}\right|$
$\displaystyle=\Delta^{\star}T+O\left(\sqrt{\log
T}\sqrt{\log(\log(T/B)/\delta)}\right)\sum_{j}\sqrt{B_{j}}$
$\displaystyle\leq\Delta^{\star}T+O\left(\sqrt{T}\log T\log\log T\right)$

The second summation can be bounded by
$\log(T)\frac{t(H^{\star}+1)}{\gamma(H^{\star}+1)}g(H^{\star}+1)$ by following
the same steps used to derive eq. 29. This gives us the following bound on the
first term in eq. 27.

$\displaystyle\sum_{j=1}^{\log(T/B)}\frac{\hat{\Delta}_{j}\left|B_{j}\right|}{\hat{\gamma}_{j}(H^{\star}+1)}\hat{t}_{j}(H^{\star}+1)\leq\Delta^{\star}T+O\left(\sqrt{T}\log
T\log\log
T\right)+\log(T)\frac{t(H^{\star}+1)}{\gamma(H^{\star}+1)}g(H^{\star}+1)$ (30)

Now we bound the second term in eq. 27.

$\displaystyle\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\hat{t}_{j}(h)\frac{\hat{\Gamma}_{j}(h+1)}{\hat{\gamma}_{j}(h)}$
$\displaystyle\leq\log(T)\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\left({\Gamma}(h+1)+2\varepsilon_{j}\sqrt{\log
T}\right)\quad\textrm{[By inequality~{}\ref{eq:temp-result-2} and
lemma~{}\ref{lem:bound-Gamma}]}$
$\displaystyle\leq\log(T)\log(T/B)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\Gamma(h+1)\left(1+\frac{2\sqrt{\log
T}}{\Gamma(h+1)}\sum_{j=1}^{\log(T/B)}\varepsilon_{j}\right)$
$\displaystyle\leq\log(T)\log(T/B)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\Gamma(h+1)O\left(1+\frac{2\sqrt{\log
T}}{\Gamma(h+1)}\sqrt{\frac{\log(\log(T/B)/\delta)}{B}}\right)$
$\displaystyle\leq\log^{2}(T)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\Gamma(h+1)O\left(1+\frac{T^{-1/4}}{\Gamma(h+1)}\right)\quad\textrm{[As
$B=\sqrt{T}\log T\log(\log(T/B)/\delta)$]}$

Now we have the following bound on the second term in eq. 27.

$\displaystyle\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\hat{t}_{j}(h)\frac{\hat{\Gamma}_{j}(h+1)}{\hat{\gamma}_{j}(h)}O\left(\sqrt{SA\left|B_{j}\right|H^{\star}}\right)$
$\displaystyle\leq\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\hat{t}_{j}(h)\frac{\hat{\Gamma}_{j}(h+1)}{\hat{\gamma}_{j}(h)}\sum_{j=1}^{\log(T/B)}O\left(\sqrt{SA\left|B_{j}\right|H^{\star}}\right)$
$\displaystyle\leq\log^{2}(T)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}\Gamma(h+1)g(h)O\left(1+\frac{T^{-1/4}}{\Gamma(h+1)}\right)\sqrt{\log(T/B)}\sqrt{\sum_{j=1}^{\log(T/B)}SA\left|B_{j}\right|H^{\star}}$
$\displaystyle\leq\log^{5/2}(T)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\Gamma(h+1)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)O\left(\sqrt{SATH^{\star}}\right)$
(31)

Following similar steps, we can also bound the fourth term in equation 27.

$\displaystyle\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\hat{t}_{j}(h)\frac{\hat{\gamma}_{j}(h+1)}{\hat{\gamma}_{j}(h)}O\left(\sqrt{\left|B_{j}\right|H^{\star}\log(\left|B_{j}\right|H^{\star}/\delta)}\right)$
$\displaystyle\leq\log^{5/2}(T)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}\gamma(h+1)g(h)\left(1+\frac{O(T^{-1/4})}{\gamma(h+1)}\right)O\left(\sqrt{TH^{\star}\log(TH^{\star}/\delta)}\right)$
(32)

We now consider the third term in equation 27.

$\displaystyle\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\hat{t_{j}(h)}\frac{(\hat{\Gamma}_{j}(h+1))^{2}}{\hat{\gamma}_{j}(h)\hat{\gamma}_{j}(h+1)}$
$\displaystyle\leq\log(T)\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\left(\frac{\Gamma(h+1)}{\gamma(h+1)}+\frac{2\varepsilon_{j}\sqrt{\log
T}}{\gamma(h+1)}\right)\left(\Gamma(h+1)+2\varepsilon_{j}\sqrt{\log T}\right)$
[By inequality 29, and lemma 5, and 7]
$\displaystyle\leq\log(T)\max_{h\in[H^{\star}]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}g(h)\sum_{j=1}^{\log(T/B)}\left(1+\frac{2\varepsilon_{j}\sqrt{\log
T}}{\Gamma(h+1)}\right)\left(1+\frac{2\varepsilon_{j}\sqrt{\log
T}}{\Gamma(h+1)}\right)$
$\displaystyle\leq\log(T)\log(T/B)\max_{h\in[H^{\star}]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}g(h)\left(1+\sum_{j}\frac{2\varepsilon_{j}\sqrt{\log
T}}{\Gamma(h+1)}\right)^{2}$
$\displaystyle\leq\log(T)\log(T/B)\max_{h\in[H^{\star}]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}g(h)\left(1+\frac{2\sqrt{\log
T}}{\Gamma(h+1)}\sqrt{\frac{\log(\log(T/B)/\delta)}{B}}\right)^{2}$
$\displaystyle\leq\log^{2}(T)\max_{h\in[H^{\star}]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}g(h)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)^{2}$

This gives the following bound on the third term.

$\displaystyle\sum_{j=1}^{\log(T/B)}\max_{h\in[H^{\star}]}\hat{t_{j}(h)}\frac{(\hat{\Gamma}_{j}(h+1))^{2}}{\hat{\gamma}_{j}(h)\hat{\gamma}_{j}(h+1)}O\left(S^{2}A(H^{\star})^{\beta}\log(\left|B_{j}\right|H^{\star})\right)$
$\displaystyle\leq\log^{2}(T)\log(TH^{\star})\max_{h\in[H^{\star}]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}g(h)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)^{2}O\left(S^{2}A(H^{\star})^{\beta}\right)$
(33)

Substituting bounds 30, 31, 33, and 32 in eq. 27 we get the following bound.

$\displaystyle\sum_{j=1}^{\log(T/B)}\mathcal{R}(H^{\star},\hat{\Delta}_{j},\left|B_{j}\right|,\widehat{\boldsymbol{\gamma}}_{j})\leq\Delta^{\star}T+O\left(\sqrt{T}\log
T\log\log
T\right)+\log(T)\frac{t(H^{\star}+1)}{\gamma(H^{\star}+1)}g(H^{\star}+1)$
$\displaystyle+\log^{5/2}(T)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\Gamma(h+1)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)O\left(\sqrt{SATH^{\star}}\right)$
$\displaystyle+\log^{2}(T)\log(TH^{\star})\max_{h\in[H^{\star}]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}g(h)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)^{2}O\left(S^{2}A(H^{\star})^{\beta}\right)$
$\displaystyle+\log^{5/2}(T)\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}\gamma(h+1)g(h)\left(1+\frac{O(T^{-1/4})}{\gamma(h+1)}\right)O\left(\sqrt{TH^{\star}\log(TH^{\star}/\delta)}\right)$

∎

######  Lemma 5.

Let $H_{1},\ldots,H_{n}$ be iid according to a distribution $\mathcal{D}$. For
$h\in\left\\{1,\ldots,D\right\\}$ let $\hat{\Gamma}_{n}(h)=\sum_{u\geq
h}\hat{\gamma}_{n}(h)$. Then with probability at least $1-\delta$ the
following holds.

$\max_{h\in\left\\{1,\ldots,D\right\\}}\left|\hat{\Gamma}_{n}(h)-\Gamma(h)\right|\leq\sqrt{\frac{\log
D+\log(1/\delta)}{n}}$

###### Proof.

We will prove this statement by first constructing a class of functions, and
proving uniform convergence over this class. In particular the class consists
of a finite number of multi-valued functions, and we will use the bounded
Natarajan dimension [Nat89] of this class to derive uniform convergence
guarantees.

Let $h_{v}:\mathbb{N}\rightarrow\mathbb{N}$ be defined by
$f_{v}(x)=\max\\{0,x-v\\}$. Consider the class of functions
$\mathcal{H}=\left\\{f_{v}:v\in\left\\{1,2,\ldots,D\right\\}\right\\}$. Let
$H_{1},\ldots,H_{n}$ be $n$ random variables drawn i.i.d. from some
distribution $\mathcal{D}$. Then for any $h\in\left\\{1,\ldots,D\right\\}$ we
have

$\displaystyle\frac{1}{n}\sum_{i=1}^{n}f_{h}(H_{i})$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\max\\{H_{i}-h,0\\}=\frac{1}{n}\sum_{i=1}^{n}\sum_{u=h}^{\infty}\mathrm{1}\left\\{H_{i}>u\right\\}$
$\displaystyle=\frac{1}{n}\sum_{i=1}^{n}\sum_{u=h}^{\infty}\left(1-\mathrm{1}\left\\{H_{i}\leq
h\right\\}\right)=\sum_{u=h}^{\infty}\frac{1}{n}\sum_{i=1}^{n}\left(1-\mathrm{1}\left\\{H_{i}\leq
u\right\\}\right)$
$\displaystyle=\sum_{u=h}^{\infty}\left(1-\hat{F}_{n}(u)\right)=\sum_{u=h}^{\infty}\hat{\gamma}_{n}(u)=\hat{\Gamma}_{n}(h)$

Similarly one can show that
$\mathbb{E}_{H\sim\mathcal{D}}[f_{h}(H)]=\Gamma(h)$. Then by the multiclass
fundamental theorem [SB14] the following result holds as long as
$n\geq\frac{\textrm{Ndim}(\mathcal{H})\log(D)+\log(1/\delta)}{\varepsilon^{2}}$.

$\Pr\left(\max_{h\in\mathcal{H}}\left|\frac{1}{n}\sum_{i=1}^{n}f_{h}(H_{i})-\mathbb{E}[f_{h}(H)]\right|>\varepsilon\right)\leq\delta$

This also implies that
$\Pr\left(\max_{h\in[D]}\left|\hat{\Gamma}_{n}(h)-\Gamma(h)\right|>\varepsilon\right)\leq\delta$.
We now bound the term $\textrm{Ndim}(\mathcal{H})$ which is the Natarajan
dimension of the class of functions $\mathcal{H}$. In fact, we prove that
$\textrm{Ndim}(\mathcal{H})=1$.

Consider a set $\left\\{a,b\right\\}\subseteq[D]$ shattered by $\mathcal{H}$.
We will assume that $a<b$. This implies there exist two function $f_{0}$ and
$f_{1}$ such that $f_{0}(x)\neq f_{1}(x)$ for $x\in\left\\{a,b\right\\}$.
Moreover, for every $B\subseteq\left\\{a,b\right\\}$ there exists a function
$h\in\mathcal{H}$ such that $h(x)=f_{0}(x)$ for all $x\in B$ and
$h(x)=f_{1}(x)$ for all $x\in B\setminus\left\\{a,b\right\\}$.

We will use the following property of the class $\mathcal{H}$. Any function
$f_{v}\in\mathcal{H}$ is characterized by a vector of the following form
$(0,0,\ldots,0,1,2,\ldots,B-v)$ where the $i$-th entry is $f_{v}(i)$. Since
all functions take value $0$ at point $1$, $a$ cannot be zero. Otherwise,
either $f_{0}(a)$ or $f_{1}(a)$ must be non-zero, and there doesn’t exist a
function that takes that non-zero value at $a$. This contradicts the fact that
the set $\left\\{a,b\right\\}$ is shattered by $\mathcal{H}$.

Therefore, suppose $a\geq 2$. First observe that $f_{0}(b)-f_{0}(a)\leq b-a$,
as there does not exist any function $f\in\mathcal{H}$ that jumps by more than
$b-a$ as input changes from $a$ to $b$. By the same argument we must have
$f_{1}(b)-f_{1}(a)\leq b-a$. Moreover, as the set is shattered by
$\mathcal{H}$ there must exist a function $f\in\mathcal{H}$ such that
$f(a)=f_{0}(a)$ and $f(b)=f_{1}(b)$. This implies $f_{1}(b)-f_{0}(a)\leq b-1$.
Similarly we have $f_{0}(b)-f_{1}(a)\leq b-a$.

We now consider two cases. First, $f_{0}(a)=0$. Then $f_{1}(a)\geq 1$, and
moreover $f_{1}(b)=f_{1}(a)+b-a\geq b-a+1$ as any function taking non-zero
value at $a$ must increase by $1$ every step. However, this is a
contradiction, as $f_{1}(b)-f_{0}(a)\geq b-a+1$.

For the second case, suppose $f_{0}(a)\geq 1$. In that case,
$f_{1}(a)=f_{0}(a)+b-a$. We suppose $f_{1}(a)\geq f_{0}(a)+1$. This is without
loss of generality as the case $f_{1}(a)\leq f_{0}(a)-1$ can be covered by
exchanging the roles of $f_{0}$ and $f_{1}$. Since $f_{1}(a)\geq 1$, we must
have $f_{1}(b)=f_{1}(a)+b-a$. But this leads to a contradiction as
$f_{1}(b)-f_{0}(a)=f_{1}(a)-f_{0}(a)+b-a\geq b-a+1$. Therefore, the set
$\left\\{a,b\right\\}$ cannot be shattered by the function class
$\mathcal{H}$. ∎

######  Lemma 6.

Suppose $\left|\hat{\gamma}_{j}(h)-\gamma(h)\right|\leq\varepsilon_{j}$ and
$\left|\hat{\Gamma}_{j}(h)-\Gamma(h)\right|\leq\varepsilon_{j}(1+\sqrt{\log
T})$ then we have

$\left|\frac{\hat{\gamma}_{j}(h)}{\hat{\Gamma}_{j}(h)}-\frac{\gamma(h)}{\Gamma(h)}\right|\leq\frac{\varepsilon_{j}(2+\sqrt{\log
T})}{\Gamma(h)}$

###### Proof.

$\displaystyle\left|\frac{\hat{\gamma}_{j}(h)}{\hat{\Gamma}_{j}(h)}-\frac{\gamma(h)}{\Gamma(h)}\right|$
$\displaystyle=\frac{\left|\hat{\gamma}_{j}(h)\Gamma(h)-\gamma(h)\hat{\Gamma}_{j}(h)\right|}{\Gamma(h)\hat{\Gamma}_{j}(h)}$
$\displaystyle\leq\frac{\hat{\gamma}_{j}(h)\left|\Gamma(h)-\hat{\Gamma}_{j}(h)\right|+\hat{\Gamma}_{j}(h)\left|\hat{\gamma}_{j}(h)-\gamma(h)\right|}{\Gamma(h)\hat{\Gamma}_{j}(h)}$
$\displaystyle\leq\frac{\hat{\gamma}_{j}(h)\varepsilon_{j}(1+\sqrt{\log
T})}{\Gamma(h)\hat{\Gamma}_{j}(h)}+\frac{\varepsilon_{j}}{\Gamma(h)}\leq\frac{\varepsilon_{j}(2+\sqrt{\log
T})}{\Gamma(h)}$

The last line uses $\hat{\gamma}_{j}(h)\leq\hat{\Gamma}_{j}(h)$. ∎

######  Lemma 7.

Suppose $\left|\hat{\gamma}_{j}(h)-\gamma(h)\right|\leq\varepsilon_{j}$ and
$\left|\hat{\Gamma}_{j}(h)-\Gamma(h)\right|\leq\varepsilon_{j}(1+\sqrt{\log
T})$ then we have

$\left|\frac{\hat{\Gamma}_{j}(h)}{\hat{\gamma}_{j}(h)}-\frac{\Gamma(h)}{\gamma(h)}\right|\leq\frac{\varepsilon_{j}(1+\sqrt{\log
T})}{\gamma(h)}$

###### Proof.

$\displaystyle\left|\frac{\hat{\Gamma}_{j}(h)}{\hat{\gamma}_{j}(h)}-\frac{\Gamma(h)}{\gamma(h)}\right|$
$\displaystyle=\frac{\left|\hat{\Gamma}_{j}(h)\gamma(h)-\Gamma(h)\hat{\gamma}_{j}(h)\right|}{\gamma(h)\hat{\gamma}_{j}(h)}$
$\displaystyle\leq\frac{\hat{\Gamma}_{j}(h)\left|\gamma(h)-\hat{\gamma}_{j}(h)\right|+\hat{\gamma}_{j}(h)\left|\hat{\Gamma}_{j}(h)-\Gamma(h)\right|}{\gamma(h)\hat{\gamma}_{j}(h)}$
$\displaystyle\leq\frac{\hat{\Gamma}_{j}(h)}{\hat{\gamma}_{j}(h)}\frac{\varepsilon_{j}}{\gamma(h)}+\frac{\varepsilon_{j}(1+\sqrt{\log
T})}{\gamma(h)}$

This gives us the following bound.

$\displaystyle\frac{\hat{\Gamma}_{j}(h)}{\hat{\gamma}_{j}(h)}-\frac{\Gamma(h)}{\gamma(h)}\leq\frac{\hat{\Gamma}_{j}(h)}{\hat{\gamma}_{j}(h)}\frac{\varepsilon_{j}}{\gamma(h)}+\frac{\varepsilon_{j}(1+\sqrt{\log
T})}{\gamma(h)}$

Rearranging we get the following inequality.

$\displaystyle\frac{\hat{\Gamma}_{j}(h)}{\hat{\gamma}_{j}(h)}\leq\frac{\Gamma(h)}{\gamma(h)+\varepsilon_{j}}+\frac{\varepsilon_{j}(1+\sqrt{\log
T})}{\gamma(h)+\varepsilon_{j}}\leq\frac{\Gamma(h)}{\gamma(h)}+\frac{\varepsilon_{j}(1+\sqrt{\log
T})}{\gamma(h)}$

∎

###  E.1 Proof of Corollary 6

###### Proof.

For the geometric discount factor we have $\gamma(k)=\gamma^{k-1}$ and
$\Gamma(k)=\gamma^{k-1}/(1-\gamma)$. We substitute $\beta=3/2$ and get the
following bound on $g(h)$.

$\displaystyle g(h)$
$\displaystyle=\exp\left\\{O\left(\sum_{k=2}^{h}\frac{T^{-1/4}}{\gamma(k)+k^{\beta}\Gamma(k)}\right)\right\\}$
$\displaystyle=\exp\left\\{O\left(\sum_{k=2}^{h}\frac{1}{\gamma^{k-1}}\frac{T^{-1/4}}{1+k^{3/2}/(1-\gamma)}\right)\right\\}$
$\displaystyle\leq\exp\left\\{O\left(\frac{T^{-1/4}}{\gamma^{h-1}}\sum_{k=2}^{h}\frac{1}{1+k^{3/2}/(1-\gamma)}\right)\right\\}$
$\displaystyle\leq\exp\left\\{O\left(\frac{T^{-1/4}}{\gamma^{h-1}}\int_{k=2}^{h}\frac{(1-\gamma)dk}{k^{3/2}}\right)\right\\}\leq\exp\left\\{O\left(\frac{T^{-1/4}(1-\gamma)h^{-1/2}}{\gamma^{h-1}}\right)\right\\}$

In corollary 3 we showed that $\frac{t(h)}{\gamma(h)}\leq e^{1-\gamma}$ for
any $h$. We also substitute $H^{\star}=\frac{\log T}{2\log(1/\gamma)}$. This
gives us the following bounds.

$\displaystyle\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\Gamma(h+1)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)$
$\displaystyle\leq
e^{1-\gamma}\max_{h\in[H^{\star}]}\exp\left\\{O\left(\frac{T^{-1/4}(1-\gamma)h^{-1/2}}{\gamma^{h-1}}\right)\right\\}\left(\frac{\gamma^{h}}{1-\gamma}+O(T^{-1/4})\right)$
$\displaystyle\leq\frac{2\gamma
e^{1-\gamma}}{1-\gamma}\max_{h\in[H^{\star}]}\exp\left\\{O\left(\frac{T^{-1/4}(1-\gamma)h^{-1/2}}{\gamma^{h-1}}\right)\right\\}$
(34)

Now we observe that the function $f(h)=\frac{h^{-1/2}}{\gamma^{h-1}}$ is a
decreasing function of $h$ for $2h\log h>\log(1/\gamma)$. Otherwise $f$ is
increasing in $h$. This implies
$\max_{h\in[H^{\star}]}\frac{h^{-1/2}}{\gamma^{h-1}}\leq\max\left\\{1,T^{1/4}\sqrt{\frac{2\log(1/\gamma)}{\log
T}}\right\\}\leq T^{1/4}\sqrt{\frac{2\log(1/\gamma)}{\log T}}$ as long as
$T\geq\frac{\log^{2}T}{4(1-\gamma)^{2}}$. Substituting this bound in eq. 34 we
get

$\displaystyle\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\Gamma(h+1)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)$
$\displaystyle\leq\frac{2\gamma
e^{1-\gamma}}{1-\gamma}\exp\left\\{O\left({\gamma}(1-\gamma)\sqrt{\frac{\log(1/\gamma)}{\log
T}}\right)\right\\}\leq\frac{2\gamma
e^{1-\gamma}}{1-\gamma}\exp\left\\{O\left(\sqrt{\gamma}(1-\gamma)\right)\right\\}=O\left(\frac{\gamma
e^{1-\gamma}}{1-\gamma}\right)$ (35)

By a similar argument we can prove the following bounds.

$\displaystyle\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\gamma(h+1)\left(1+\frac{O(T^{-1/4})}{\gamma(h+1)}\right)\leq
O\left(\frac{\gamma e^{1-\gamma}}{1-\gamma}\right)$ (36)
$\displaystyle\max_{h\in[H^{\star}]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}g(h)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)^{2}$
$\displaystyle\leq\max_{h\in[H^{\star}]}e^{1-\gamma}\left(\frac{\gamma^{h/2}}{1-\gamma}+\gamma^{h/2}O(T^{-1/4})\right)^{2}g(h)=O\left(\frac{\gamma
e^{1-\gamma}}{(1-\gamma)^{2}}\right)$ (37)

Finally, we bound the remaining term in the regret expression from theorem 4:
$\min_{L\in[T]}T\Gamma(L+1)+2L\log(T)\sqrt{T}$. In particular we substitute
$L=\frac{\log T}{2\log(1/\gamma)}$ to get the following bound on this term.

$\displaystyle\frac{\sqrt{T}}{1-\gamma}+\frac{\sqrt{T}\log^{2}T}{\log(1/\gamma)}=O\left(\frac{\sqrt{T}\log^{2}T}{1-\gamma}\right)$
(38)

Note that this choice of $L$ requires $L\leq T$ which is satisfied as long as
$T\geq O(1/(1-\gamma)^{2})$. Substituting bounds 38, 37, 36, and 35 in the
regret expression from theorem 4 we get the following bound on regret.

$\displaystyle\textrm{Reg}(\pi;\boldsymbol{\gamma})\leq$ $\displaystyle
O\left(\frac{\sqrt{T}\log^{2}T}{1-\gamma}\right)+O\left(\sqrt{T}\log T\log\log
T\right)+\log^{5/2}(T)O\left(\frac{e^{1-\gamma}}{1-\gamma}\sqrt{SAT\frac{\log
T}{\log(1/\gamma)}}\right)$ $\displaystyle+\log^{2}(T)\log\left(\frac{T\log
T}{\log(1/\gamma)}\right)O\left(\frac{e^{1-\gamma}}{(1-\gamma)^{2}}S^{2}A\left(\frac{\log
T}{\log(1/\gamma)}\right)^{3/2}\right)$ $\displaystyle\leq
O\left(\frac{\sqrt{T}\log^{2}T}{1-\gamma}\right)+O\left(\frac{\sqrt{SAT}\log^{3}T}{(1-\gamma)^{3/2}}\right)+O\left(\frac{S^{2}A\log^{9/2}T}{(1-\gamma)^{7/2}}\right)$
$\displaystyle\leq
O\left(\frac{\sqrt{SAT}\log^{3}T}{(1-\gamma)^{3/2}}\right)\quad\textrm{[If
$T/\log^{3}T\geq S^{3}A/(1-\gamma)^{4}$]}$

∎

###  E.2 Proof of Corollary 5

###### Proof.

For the polynomial discount factor we have $\gamma(k)=k^{-p}$ and
$\Gamma(k)\in\left[\frac{k^{-p+1}}{p-1},k^{-p}\left(1+\frac{k}{p-1}\right)\right]$.
We substitute $\beta=p-1$ and get the following bound on $g(h)$.

$\displaystyle g(h)$
$\displaystyle=\exp\left\\{O\left(\sum_{k=2}^{h}\frac{T^{-1/4}}{\gamma(k)+k^{\beta}\Gamma(k)}\right)\right\\}=\exp\left\\{O\left(\sum_{k=2}^{h}\frac{T^{-1/4}}{k^{-p}+1/(p-1)}\right)\right\\}$
$\displaystyle\leq\exp\left\\{O\left({T^{-1/4}}\sum_{k=2}^{h}\frac{k^{p}}{1+k^{p}/(p-1)}\right)\right\\}\leq\exp\left\\{O\left({T^{-1/4}}\frac{h^{p+1}}{1+h^{p}/(p-1)}\right)\right\\}$

The last inequality follows because the function $k^{p}/(1+k^{p}/(p-1))$ is an
increasing function of $k$. In corollary 2 we showed that
$\frac{t(h)}{\gamma(h)}\leq e$ for any $h$ and $p>1$. We also substitute
$H^{\star}=T^{1/2p}$. This gives us the following bounds.

$\displaystyle\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\Gamma(h+1)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)$
$\displaystyle\leq
e\max_{h\in[H^{\star}]}\exp\left\\{O\left({T^{-1/4}}\frac{h^{p+1}}{1+h^{p}/(p-1)}\right)\right\\}\left((h+1)^{-p}\left(1+\frac{h+1}{p-1}\right)+O(T^{-1/4})\right)$
$\displaystyle\leq
e\left(1+\frac{2^{-(p-1)}}{p-1}\right)\max_{h\in[H^{\star}]}\exp\left\\{O\left({T^{-1/4}}\frac{h^{p+1}}{1+h^{p}/(p-1)}\right)\right\\}$

For $p\geq 2$, $h^{p+1}/(1+h^{p}/(p-1))\leq 2h$. This gives the following
bound on the term above.

$\displaystyle\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\Gamma(h+1)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)\leq
2e\exp\left\\{O(T^{-1/4}+T^{1/2p})\right\\}\leq 2e$ (39)

By a similar argument we can prove the following bounds.

$\displaystyle\max_{h\in[H^{\star}]}\frac{t(h)}{\gamma(h)}g(h)\gamma(h+1)\left(1+\frac{O(T^{-1/4})}{\gamma(h+1)}\right)\leq
2e$ (40)
$\displaystyle\max_{h\in[H^{\star}]}t(h)\frac{(\Gamma(h+1))^{2}}{\gamma(h)\gamma(h+1)}g(h)\left(1+\frac{O(T^{-1/4})}{\Gamma(h+1)}\right)^{2}$
$\displaystyle\leq\max_{h\in[H^{\star}]}e(p-1)(h+1)^{-p}\left(1+\frac{h+1}{p-1}\right)^{2}\max_{h\in[H^{\star}]}g(h)$
$\displaystyle\leq 2e\quad\textrm{[As $p\geq 2$]}$ (41)

Finally, we bound the remaining term in the regret expression from theorem 4:
$\min_{L\in[T]}T\Gamma(L+1)+2L\log(T)\sqrt{T}$. We substitute $L=T^{1/2p}$ and
get the following bound on the final term.

$\displaystyle 2T^{1/2p}\log T+T\cdot
T^{-1/2}\left(1+\frac{T^{1/2p}}{p-1}\right)=O\left(T^{\frac{1+p}{2p}}\right)$
(42)

Substituting bounds 39, 40, 41, and 42 in the regret expression from theorem 4
we get the following bound on regret.

$\displaystyle\textrm{Reg}(\pi;\boldsymbol{\gamma})$ $\displaystyle\leq
T^{\frac{p+1}{2p}}+T\left(T^{-1/2}+\frac{T^{-(1-p)/2p}}{p-1}\right)+O\left(\sqrt{T}\log
T\right)$
$\displaystyle+\log^{5/2}(T)O\left(\sqrt{SAT^{(2p+1)/2p}}\right)+\log^{3}(T)\cdot
O\left(S^{2}AT^{(p-1)/2p}\right)$ $\displaystyle+\log^{5/2}(T)\cdot
O\left(\sqrt{T^{(2p+1)/2p}\log T}\right)$

If $T>(S^{3/2}A^{1/2})^{p}$ then the first and the fourth term dominates and
regret is at most $O(\sqrt{SA}T^{(p+1)/2p})$. On the other hand, if
$T<(S^{3/2}A^{1/2})^{p}$ then the fifth term dominates and regret is at most
$\widetilde{O}\left(S^{2}AT^{(p-1)/2p}\right)$. ∎