ifaamas [AAMAS ’21]Proc. of the 20th International Conference on Autonomous
Agents and Multiagent Systems (AAMAS 2021)May 3–7, 2021London, UKU. Endriss,
A. Nowé, F. Dignum, A. Lomuscio (eds.) 2021 2021 University of Waterloo
Waterloo, Ontario University of Waterloo Waterloo, Ontario University of
Alberta
Alberta Machine Intelligence Institute (Amii) Edmonton, Alberta

# The Effect of Q-function Reuse on the Total Regret of Tabular, Model-Free,
Reinforcement Learning

Volodymyr Tkachuk<EMAIL_ADDRESS>,  Sriram Ganapathi Subramanian
<EMAIL_ADDRESS>and  Matthew E. Taylor<EMAIL_ADDRESS>
###### Abstract.

Some reinforcement learning methods suffer from high sample complexity causing
them to not be practical in real-world situations. $Q$-function reuse, a
transfer learning method, is one way to reduce the sample complexity of
learning, potentially improving usefulness of existing algorithms. Prior work
has shown the empirical effectiveness of $Q$-function reuse for various
environments when applied to model-free algorithms. To the best of our
knowledge, there has been no theoretical work showing the regret of
$Q$-function reuse when applied to the tabular, model-free setting. We aim to
bridge the gap between theoretical and empirical work in $Q$-function reuse by
providing some theoretical insights on the effectiveness of $Q$-function reuse
when applied to the $Q$-learning with UCB-Hoeffding algorithm. Our main
contribution is showing that in a specific case if $Q$-function reuse is
applied to the $Q$-learning with UCB-Hoeffding algorithm it has a regret that
is independent of the state or action space. We also provide empirical results
supporting our theoretical findings.

###### Key words and phrases:

Reinforcement Learning, Transfer Learning

##  1\. Introduction

In reinforcement learning (RL), an agent interacts with an environment and
tries to maximize its expected sum of rewards. Many algorithms, such as
Q-learning with $\epsilon$-greedy exploration Sutton and Barto (2018), can
suffer from poor sample complexity Kearns and Singh (2002). This is a problem
in real-world situations where an agent may receive a limited amount of
samples to learn an optimal policy. Such real-world environments serve as
motivation to reduce the sample complexity of RL algorithms.

Transfer learning (TL) is a method used in RL as one way to reduce an agent’s
training time Taylor and Stone (2009). The key idea is that an agent can learn
a target task faster by transferring information from a previously learned
source task, similar to how humans can learn algebra more quickly by
transferring knowledge from previous tasks that require addition and
multiplication. Although the concept of TL is intuitively appealing, its
effectiveness has been mostly shown through empirical studies Zhu et al.
(2020). As such, we aim to provide new theoretical results for one TL method
in RL, $Q$-function reuse.

$Q$-function reuse is the process of training an agent on a simple _source_
Markov decision process (MDP) $\mathcal{M}_{S}$ and then transferring its
learned $Q$-function to a more complex, yet related _target_ MDP
$\mathcal{M}_{T}$. The goal is to improve the sample complexity when compared
to just training in $\mathcal{M}_{T}$ from the start. Sample complexity is
loosely defined as how much data an agent must collect in order to learn a
good policy Kakade et al. (2003). If the agent was trained in
$\mathcal{M}_{S}$ until convergence to the optimal policy, transferring the
$Q$-function from $\mathcal{M}_{S}$ to $\mathcal{M}_{T}$ can sometimes be
thought of as a near-optimal $Q$-function initialization in $\mathcal{M}_{T}$,
since $\mathcal{M}_{S}$ is related to $\mathcal{M}_{T}$. Therefore, we propose
that one method to study $Q$-function reuse is to study the effectiveness of
near-optimal $Q$-function initialization.

Since the effectiveness of $Q$-function reuse has been mostly shown in the
model-free setting Zhu et al. (2020), and it is easier to perform a
theoretical analysis in the tabular domain, we choose to study the effects of
$Q$-function reuse on a tabular, model-free algorithm that is provably
efficient, $Q$-learning with UCB-Hoeffding Jin et al. (2018). In this work we
study the setting where we are given the $Q$-function from some agent that has
previously been trained on a simple MDP $\mathcal{M}_{S}$. We refer to this
$Q$-function as the pre-trained $Q$-function from $\mathcal{M}_{S}$. We will
answer the following question:

Will the total regret of the $Q$-learning with UCB-Hoeffding algorithm be
lower in a complex (target) MDP $\mathcal{M}_{T}$, if it is initialized with a
pre-trained $Q$-function from a related, but simpler (source) MDP
$\mathcal{M}_{S}$?

For our analysis, we assume the $Q$-function initialization is optimal for all
but one value. Although this is a rather strong assumption, we believe it
provides useful insights and a promising starting point for future work. In
general, the $Q$-function initialization in a target MDP after $Q$-function
reuse has some nearly optimal $Q$-values and some $Q$-values that are far from
optimal. Therefore, to address the general case of $Q$-function reuse, future
work might include increasing the number of not optimal $Q$-values to more
than one and relaxing the optimal $Q$-function initialization for the
remaining $Q$-values to some notion of sub-optimality. To the best of our
knowledge, there has not been any theoretical work showing the total regret of
$Q$-function reuse applied on a tabular, model-free algorithm. We perform a
regret analysis, showing that the $Q$-learning with the UCB-Hoeffding
algorithm Jin et al. (2018), along with our initialization assumptions
achieves a total regret of only $O(\sqrt{H^{2}T\iota^{\prime}})$ (independent
of the state and action space), while regular $Q$-learning with UCB-Hoeffding
suffers a regret of $O(\sqrt{H^{4}SAT\iota})$ Jin et al. (2018). Empirical
results are presented to support these theoretical claims.

##  2\. Preliminaries

We borrow standard notations from Jin et al. (2018), that we will include in
this section for quick reference. To provide a fair comparison between our
algorithm and the $Q$-learning with UCB-Hoeffding algorithm, proposed by Jin
et al. (2018), we maintain a similar problem setting. Extending this work to
other settings (e.g., stochastic reward, terminating states, discounting,
etc.) is left for future work. We begin by describing the Markov decision
process, MDP$(\mathcal{S},\mathcal{A},H,\mathbb{P},r)$. The set of states is
$\mathcal{S}$, with $|\mathcal{S}|=S$. The set of actions is $\mathcal{A}$,
with $|\mathcal{A}|=A$. The number of steps per episode (horizon) is $H$. The
transition dynamics are given by $\mathbb{P}$, where
$\mathbb{P}_{h}(\cdot|x,a)$ gives the next state distribution if action $a$
was taken in state $x$ at step $h\in[H]$. The deterministic reward function is
$r_{h}(x,a)$, which provides a reward in the range $[0,1]$ for taking action
$a$ in state $x$ at step $h$. The agent acts in this MDP for $K$ episodes. We
let $T=KH$ denote the total number of steps the agent takes in the MDP.

For each episode $k\in[K]$ an initial state $x_{1}^{k}$ is chosen randomly. At
each step $h$ and episode $k$ the agent observes a state $x_{h}^{k}$, takes
action $a_{h}^{k}$, receives reward $r_{h}(x_{h}^{k},a_{h}^{k})$, and then
transitions to its next state drawn from the distribution
$\mathbb{P}_{h}(\cdot|x_{h}^{k},a_{h}^{k})$. The transition dynamics and
reward function were chosen to depend on the step $h$ for generality and to
remain consistent with prior work Jin et al. (2018). Note that if dependence
on $h$ is not required then the transition dynamics and reward function can be
set the same for all $h$ and all the results shown in this work will still
hold. The episode ends when $x_{H+1}^{k}$ is reached.

There is a separate policy $\pi_{h}$ for each step
$\\{\pi_{h}:\mathcal{S}\to\mathcal{A}\\}_{h\in[H]}$. We use
$V_{h}^{\pi}:\mathcal{S}\to\mathbb{R}$ to denote the value function at step
$h$ under policy $\pi$. The expected sum of rewards under policy $\pi$, from
$x_{h}=x$ until the end of the episode is given by $V_{h}^{\pi}(x)$. This is
represented as:

$V_{h}^{\pi}(x):=\mathbb{E}\left[\sum_{h^{\prime}=h}^{H}r_{h^{\prime}}(x_{h^{\prime}},\pi_{h^{\prime}}(x_{h^{\prime}}))|x_{h}=x\right]$

Similarly, we define the state-action value function as
$Q_{h}^{\pi}:\mathcal{S}\times\mathcal{A}\to\mathbb{R}$. The expected sum of
rewards under policy $\pi$, from state $x_{h}=x$ after taking action $a_{h}=a$
until the end of the episode is given by $Q_{h}^{\pi}(x,a)$. This is
represented as:

$Q_{h}^{\pi}(x,a):=r_{h}(x,a)+\mathbb{E}\left[\sum_{h^{\prime}=h+1}^{H}r_{h^{\prime}}(x_{h^{\prime}},\pi_{h^{\prime}}(x_{h^{\prime}}))|x_{h}=x,a_{h}=a\right]$

Since the state space, action space, and horizon are all finite, there always
exists an optimal policy $\pi^{*}$ which gives the optimal value
$V_{h}^{*}(x):=\text{sup}_{\pi}V_{h}^{\pi}(x)$, for all $x\in\mathcal{S}$ and
$h\in[H]$ Azar et al. (2017). To simplify notation we will denote
$[\mathbb{P}_{h}V_{h+1}](x,a):=\mathbb{E}_{x^{\prime}\sim\mathbb{P}(\cdot|x,a)}V_{h+1}(x^{\prime})$.
Using this notation we have the Bellman equations and Bellman optimality
equations as follows:

$\begin{cases}V_{h}^{\pi}(x)=Q_{h}^{\pi}(x,\pi_{h}(x))\\\
Q_{h}^{\pi}(x,a)=(r_{h}+\mathbb{P}_{h}V_{h+1}^{\pi})(x,a)\\\
V_{H+1}^{\pi}(x)=0\quad\forall x\in\mathcal{S}\end{cases}\\\
\begin{cases}V_{h}^{*}(x)=\text{max}_{a\in\mathcal{A}}Q_{h}^{*}(x,a)\\\
Q_{h}^{*}(x,a):=(r_{h}+\mathbb{P}_{h}V_{h+1}^{*})(x,a)\\\
V_{H+1}^{*}(x)=0\quad\forall x\in\mathcal{S}\end{cases}$ (1)

We will use $\pi_{h}^{k}$ to denote the agent’s policy at episode $k$.
Finally, the performance metric of interest is the total regret, defined as:

$\text{Regret}(K)=\sum_{k=1}^{K}[V_{1}^{*}(x_{1}^{k})-V_{1}^{\pi_{h}^{k}}(x_{1}^{k})]$

##  3\. Results

In this section we present our algorithm, $Q$-learning with UCB-Hoeffding and
Max-Optimal Initialization, a modified version of Algorithm 1 from Jin et al.
(2018). We also introduce a theorem that shows the total regret of our
algorithm is $O(\sqrt{H^{2}T\iota^{\prime}})$.

As a starting point to answering our question, presented in the introduction,
we propose using an ideal $Q$-function initialization to model a possible pre-
trained $Q$-function we might receive. We call this Max-Optimal Initialization
because it is the maximum number of assumptions that can be made before the
$Q$-function initialization becomes the optimal $Q$-function for all states,
actions, and steps. In words, we initialize the $Q$-function to the optimal
$Q$-function for all $(x,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$ except
for state $x1$, action $a1$ and step $h=1$, which is initialized to $H$ (as
per the $Q$-learning with UCB-Hoeffding algorithm). Since updating the
$Q$-function at any of the optimal states, actions, and steps could
potentially make it sub-optimal, we make the additional assumption that the
$Q$-function is only updated for $(x1,a1,h=1)$. We only keep track of how many
times $(x1,a1,h=1)$ was visited using a counter $N_{1}(x1,a1)$ initialized to
$0$. Since the $Q$-function is not updated for any other $(x,a,h)$, there is
no need to keep track of how many times any other $(x,a,h)$ is visited. In
mathematical notation the initialization can be stated as follows:

$\displaystyle Q_{1}(x1,a1)\leftarrow H\ \text{and}\ N_{1}(x1,a1)\leftarrow 0$
(2) $\displaystyle Q_{h}(x,a)\leftarrow Q^{*}_{h}(x,a)\ \text{for all}\
(x,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]\backslash(x1,a1,h=1)$

The Max-Optimal initialization can model the scenario where an agent is
trained on some simple MDP $\mathcal{M}_{0}$ until convergence, but then a new
action $a1$ is introduced at state $x1$ and step $h=1$ (MDP
$\mathcal{M}_{F}$). In $\mathcal{M}_{F}$ the agent is essentially initialized
with an optimal $Q$-function for all $(x,a,h)$, except $(x1,a1,h=1)$. We would
like to highlight that in this scenario $\mathcal{M}_{0}$ is considered
related to MDP $\mathcal{M}_{F}$ since it has the same transition dynamics and
reward function for all but one state, action, and step. $\mathcal{M}_{0}$ is
also considered simpler than $\mathcal{M}_{F}$ since it is exactly
$\mathcal{M}_{F}$, except without $(x1,a1,h=1)$. We present Algorithm 1,
$Q$-learning with UCB-Hoeffding and Max-Optimal Initialization, which combines
the $Q$-learning with UCB-Hoeffding algorithm with the Max-Optimal
Initialization assumptions. The modifications we made to the $Q$-learning with
UCB-Hoeffding algorithm are shown in blue in Algorithm 1.

We now describe the steps performed in our algorithm. The $Q$-function and
step counter $N_{1}(x1,a1)$ are initialized using Max-Optimal initialization.
For each episode $k\in[K]$ the agent starts in a random state $x_{1}^{k}$.
Then, for each step $h\in[H]$ and state $x_{h}^{k}\in\mathcal{S}$ the agent
selects the action $a\in\mathcal{A}$ that maximizes its current estimate of
$Q_{h}(x,a)$. The next state $x_{h+1}^{k}\in\mathcal{S}$ is sampled from
$\mathbb{P}_{h}(\cdot|x,a)$. If the current state, action and step
$(x_{h}^{k},a_{h}^{k},h)$ is $(x1,a1,h=1)$, the agent updates its $Q$-function
using the following rule:

$Q_{h}(x_{h}^{k},a_{h}^{k})\leftarrow(1-\alpha_{t})Q_{h}(x_{h}^{k},a_{h}^{k})+\alpha_{t}[r_{h}(x_{h}^{k},a_{h}^{k})+V_{h+1}(x_{h+1}^{k})+b_{t}]$
(3)

where $t$ is the step counter for how many times the agent has visited
$(x1,a1)$ at step $h=1$, $b_{t}$ is the confidence bonus indicating the agents
confidence in its $Q$-value at $(x1,a1,h=1)$, and the learning rate $\alpha$
is $\alpha_{t}:=\frac{H+1}{H+t}$. This choice of learning rate $\alpha_{t}$ is
crucial to obtain a total regret that is not exponential in $H$ Jin et al.
(2018).

We removed the update
$V_{h}(x_{h})\leftarrow\min\\{H,\max_{a^{\prime}\in\mathcal{A}}Q_{h}(x_{h},a^{\prime})\\}$
since the $Q$-function in our algorithm is only updated for $(x1,a1,h=1)$,
which requires knowledge of $V_{h+1}^{k}(x_{h+1}^{k})$. But
$V_{h+1}^{k}(x_{h+1}^{k})=V_{h+1}^{*}(x_{h+1}^{k})$ for $h\geq 1$ due to the
Max-Optimal initialization, meaning we never need to update
$V_{h+1}^{k}(x_{h+1}^{k})$.

We present the following theorem for the $Q$-learning with UCB-Hoeffding and
Max-Optimal Initialization algorithm:

######  Theorem 1 (Hoeffding Max-Optimal).

There exists an absolute constant $c>0$ such that, for any $p\in(0,1)$, if we
choose $b_{t}=c\sqrt{H^{3}\iota^{\prime}/t}$, then with probability $1-p$ the
total regret of $Q$-learning with UCB-Hoeffding and Max-Optimal Initialization
(Algorithm 1) is at most $O(\sqrt{H^{2}T\iota^{\prime}})$, where
$\iota^{\prime}:=log(K/p)$.

Note that we reserve $\iota$ for when we refer to the $Q$-learning with UCB-
Hoeffding algorithm, where $\iota:=log(SAT/p)$. In our algorithm this term is
reduced to $\iota^{\prime}:=log(K/p)$ due to our added assumptions.

1 Initialize $Q_{1}(x1,a1)\leftarrow H$ and $N_{1}(x1,a1)\leftarrow 0$

2 Initialize $Q_{h}(x,a)\leftarrow Q^{*}_{h}(x,a)$ for all
$(x,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]\backslash(x1,a1,h=1)$

3 for  _episode $k=1,...,K$_ do

4 receive $x_{1}^{k}$

5 for  _step $h=1,...,H$_ do

6 Take action
$a_{h}^{k}\leftarrow\operatorname{argmax}_{a^{\prime}}{Q_{h}(x_{h}^{k},a^{\prime})}$,
and observe $x_{h+1}^{k}$

7 if  _$x_{h}^{k}=x1$ and $a_{h}^{k}=a1$ and $h=1$_ then

8 $t=N_{h}(x_{h}^{k},a_{h}^{k})\leftarrow N_{h}(x_{h}^{k},a_{h}^{k})+1$;
$b_{t}\leftarrow c\sqrt{H^{3}\iota^{\prime}/t}$

9
$Q_{h}(x_{h}^{k},a_{h}^{k})\leftarrow(1-\alpha_{t})Q_{h}(x_{h}^{k},a_{h}^{k})+\alpha_{t}[r_{h}(x_{h}^{k},a_{h}^{k})+V_{h+1}(x_{h+1}^{k})+b_{t}]$

10

11 end if

12

13 end for

14

15 end for

Algorithm 1 $Q$-learning with UCB-Hoeffding and Max-Optimal Initialization

##  4\. Proof for Q-learning with UCB-Hoeffing and Max-Optimal Initialization

We provide a full proof of Theorem 1, following similar steps and notation to
that mentioned in Jin et al. (2018). We first introduce some notation for
convenience.

We denote by $\mathbb{I}[A]$ as the indicator function for an event $A$.
Recall that
$[\mathbb{P}_{h}V_{h+1}](x,a):=\mathbb{E}_{x^{\prime}\sim\mathbb{P}_{h}(\cdot|x,a)}V_{h+1}(x^{\prime})$.
We now introduce its empirical counterpart,
$[\hat{\mathbb{P}}_{h}^{k}V_{h+1}](x,a):=V_{h+1}(x_{h+1}^{k})$, which is
defined only for $(x,a)=(x_{h}^{k},a_{h}^{k})$. Recalling that
$\alpha_{t}=\frac{H+1}{H+t}$, we introduce the following:

$\alpha_{t}^{0}=\prod_{j=1}^{t}(1-\alpha_{j}),\qquad\alpha_{t}^{i}=\alpha_{i}\prod_{j=i+1}^{t}(1-\alpha_{j})$
(4)

Recall that $\sum_{j}^{t<j}(\cdot)=0$ and $\prod_{j}^{t<j}(\cdot)=1$.
Therefore, the following properties hold:

$\sum_{i=1}^{t}\alpha_{t}^{i}=1\ \text{and}\ \ \alpha_{t}^{0}=0\ \text{for}\
t\geq 1,\ \sum_{i=1}^{t}\alpha_{t}^{i}=0\ \text{and}\ \alpha_{t}^{0}=1\
\text{for}\ t=0$

The motivation for introducing this notation is to simplify the recursive
$Q$-function update formula (as seen in equation (3)). From equation (3) and
equation (4) we have:

$Q_{h}^{k}(x,a)=\alpha_{t}^{0}H+\sum_{i=1}^{t}\alpha_{t}^{i}[r_{h}(x,a)+V_{h+1}^{*}(x_{h+1}^{k_{i}})+b_{i}]$
(5)

which only applies for $(x1,a1,h=1),\ \forall k\in[K]$, as discussed in
equation (3).

### Proof Details

We now introduce some Lemmas that will help us in the proof of Theorem 1. For
completeness we repeat Lemme 4.1 exactly as stated in Jin et al. (2018).

######  Lemma 4.1.

The following properties hold for $\alpha_{t}^{i}$:

  1. (a)

$\frac{1}{\sqrt{t}}\leq\sum_{i=1}^{t}\frac{\alpha_{t}^{i}}{\sqrt{i}}\leq\frac{2}{\sqrt{t}}$
for every $t\geq 1$

  2. (b)

$\max_{i\in[t]}\alpha_{t}^{i}\leq\frac{2H}{t}$ and
$\sum_{i=1}^{t}(\alpha_{t}^{i})^{2}\leq\frac{2H}{t}$ for every $t\geq 1$

  3. (c)

$\sum_{t=1}^{\infty}\alpha_{t}^{i}=1+\frac{1}{H}$ for every $i\geq 1$

###### Proof.

See proof of Lemma 4.1 in Jin et al. (2018) ∎

We now present modified versions of Lemma 4.2 and Lemma 4.3 from Jin et al.
(2018), which we will use in our proof of Theorem 1.

######  Lemma 4.2 (Difference in Q).

For $(x1,a1,h=1)\in\mathcal{S}\times\mathcal{A}\times[H]$ and episode
$k\in[K]$, let $t=N_{1}^{k}(x1,a1)$ and suppose $(x1,a1)$ was previously taken
at step h=1 of episode $k_{1},...,k_{t}<k$. Then:

$\displaystyle(Q_{1}^{k}-Q_{1}^{*})(x1,a1)=$
$\displaystyle\alpha_{t}^{0}(H-Q_{1}^{*}(x1,a1))$
$\displaystyle+\sum_{i=1}^{t}\alpha_{t}^{i}\left[[(\hat{\mathbb{P}}_{1}^{k_{i}}-\mathbb{P}_{1})V_{2}^{*}](x1,a1)+b_{i}\right]$

###### Proof of Lemma 4.2.

From the Bellman optimality equation we have
$Q_{h}^{*}(x,a)=(r_{h}+\mathbb{P}_{h}V_{h+1}^{*})(x,a)$. Recalling that
$[\hat{\mathbb{P}}_{h}^{k}V_{h+1}](x,a):=V_{h+1}(x_{h+1}^{k})$, and the fact
that $\sum_{i=0}^{t}\alpha_{t}^{i}=1$, we have:

$\displaystyle Q_{h}^{*}(x,a)=\ $ $\displaystyle
r_{h}(x,a)+[\mathbb{P}_{h}V_{h+1}^{*}](x,a)$ $\displaystyle=\ $
$\displaystyle\alpha_{t}^{0}Q_{h}^{*}(x,a)+\sum_{i=1}^{t}\alpha_{t}^{i}\left[r_{h}(x,a)+[\mathbb{P}_{h}V_{h+1}^{*}](x,a)\right]$
$\displaystyle=\ $ $\displaystyle\alpha_{t}^{0}Q_{h}^{*}(x,a)$
$\displaystyle+\sum_{i=1}^{t}\alpha_{t}^{i}\left[r_{h}(x,a)+[(\mathbb{P}_{h}-\hat{\mathbb{P}}_{h}^{k_{i}})V_{h+1}^{*}](x,a)+V_{h+1}^{*}(x_{h+1}^{k_{i}})\right]$

which is true for all $(x,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$.
Subtracting the above equation from formula (5) for $(x1,a1,h=1)$, we obtain
Lemma 4.2:

$\displaystyle(Q$ ${}_{1}^{k}-Q_{1}^{*})(x1,a1)$ $\displaystyle=\ $
$\displaystyle\alpha_{t}^{0}(H-Q_{1}^{*}(x1,a1))$
$\displaystyle+\sum_{i=1}^{t}\alpha_{t}^{i}\left[(V_{2}^{k_{i}}-V_{2}^{*})(x_{2}^{k_{i}})+[(\hat{\mathbb{P}}_{1}^{k_{i}}-\mathbb{P}_{1})V_{2}^{*}](x1,a1)+b_{i}\right]$
$\displaystyle\stackrel{{\scriptstyle\leavevmode\hbox to5.36pt{\vbox
to5.36pt{\pgfpicture\makeatletter\hbox{\hskip 2.68126pt\lower-2.68126pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.48126pt}{0.0pt}\pgfsys@curveto{2.48126pt}{1.37038pt}{1.37038pt}{2.48126pt}{0.0pt}{2.48126pt}\pgfsys@curveto{-1.37038pt}{2.48126pt}{-2.48126pt}{1.37038pt}{-2.48126pt}{0.0pt}\pgfsys@curveto{-2.48126pt}{-1.37038pt}{-1.37038pt}{-2.48126pt}{0.0pt}{-2.48126pt}\pgfsys@curveto{1.37038pt}{-2.48126pt}{2.48126pt}{-1.37038pt}{2.48126pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{=}}\ $
$\displaystyle\alpha_{t}^{0}(H-Q_{1}^{*}(x1,a1))$
$\displaystyle+\sum_{i=1}^{t}\alpha_{t}^{i}\left[[(\hat{\mathbb{P}}_{1}^{k_{i}}-\mathbb{P}_{1})V_{2}^{*}](x1,a1)+b_{i}\right]$

Where ① holds because $V_{h}^{k}(x_{h}^{k})=V_{h}^{*}(x_{h}^{k})$ for $h\geq
2,\forall k\in[K]$ ∎

Next, we present a modified version of Lemma 4.3 from Jin et al. (2018), for
$(x1,a1,h=1)$, which shows that $Q_{1}^{k}$ is an upper bound on $Q_{1}^{*}$
with high probability.

######  Lemma 4.3 (bound on $(Q^{k}_{1}-Q^{*}_{1})(x1,a1)$).

There exists an absolute constant $c>0$ such that, for any $p\in(0,1)$,
letting $b_{t}=c\sqrt{H^{3}\iota^{\prime}/t}$, we have
$\beta_{t}=2\sum_{i=1}^{t}\alpha_{t}^{i}b_{i}\leq
4c\sqrt{H^{3}\iota^{\prime}/t}$, where $\iota^{\prime}=log(K/p)$, and with
probability at least $1-p$, the following holds for $(x1,a1,h=1),\ \forall
k\in[K]$:

$0\leq(Q_{1}^{k}-Q_{1}^{*})(x1,a1)\leq\alpha_{t}^{0}H+\beta_{t}$

where $t=N_{1}^{k}(x1,a1)$ and $k_{1},...,k_{t}<k$ are the episodes where
$(x1,a1)$ was taken at step $h=1$.

###### Proof of Lemma 4.3.

For $(x1,a1,h=1)$, let us denote $k_{0}=0$ and denote

$k_{i}=\min\left(\\{k\in[K]\ |\ k\geq
k_{i-1}\wedge(x_{1}^{k},a_{1}^{k})=(x1,a1)\\}\cup\\{K+1\\}\right)$

In words, this means that $k_{i}$ is the episode when $(x1,a1)$ was taken at
step $h=1$ for the $i$th time, and $k_{i}$ equals $K+1$ if $(x1,a1)$ was taken
for fewer than $i$ times. The random variable $k_{i}$ can be thought of as a
stopping time. If we let $\mathcal{F}_{i}$ (filtration) be the
$\sigma$-algebra generated by all the random variables until episode $k_{i}$,
and step $h=1$. Then, $\big{(}\mathbb{I}[k_{i}\leq
K]\cdot[(\hat{\mathbb{P}}_{1}^{k_{i}}-\mathbb{P}_{1})V_{2}^{*}](x1,a1)\big{)}_{i=1}^{\tau}$
is a Martingale difference sequence w.r.t. the filtration
$\\{\mathcal{F}_{i}\\}_{i\geq 0}$. In words, the filtration
$\\{\mathcal{F}_{i}\\}_{i\geq 0}$ can be thought of as a sequence of
increasing information about state $x1$, action $a1$ at step $h=1$, where the
filtration satisfies
$\mathcal{F}_{1}\subseteq\mathcal{F}_{2}...\subseteq\mathcal{F}_{i}$ and the
three properties that define a $\sigma$-algebra. By Azuma-Hoeffding and a
union bound, we have with probability at least $1-p$:

$\displaystyle\forall\tau\in[K]$ $\displaystyle:\
\left|\sum_{i=1}^{\tau}\alpha_{\tau}^{i}\cdot\mathbb{I}[k_{i}\leq
K]\cdot[(\hat{\mathbb{P}}_{1}^{k_{i}}-\mathbb{P}_{1})V_{2}^{*}](x1,a1)\right|$
$\displaystyle\leq\frac{cH}{2}\sqrt{\sum_{i=1}^{\tau}(\alpha_{\tau}^{i})^{2}\cdot\iota^{\prime}}\leq
c\sqrt{\frac{H^{3}\iota^{\prime}}{\tau}}$ (6)

for some absolute constant c. Because inequality (4) holds for all fixed
$\tau\in[K]$ uniformly, it also holds for $\tau=t=N_{1}^{k}(x1,a1)\leq K$,
which is a random variable, where $k\in[K]$. Also note $\mathbb{I}[k_{i}\leq
K]=1$ for all $i\leq N_{1}^{k}(x1,a1)$. We now have:

$\left|\sum_{i=1}^{t}\alpha_{\tau}^{i}\cdot[(\hat{\mathbb{P}}_{1}^{k_{i}}-\mathbb{P}_{1})V_{2}^{*}](x1,a1)\right|\leq
c\sqrt{\frac{H^{3}\iota^{\prime}}{\tau}}\ \ \text{where}\ \
t=N_{1}^{k}(x1,a1)$ (7)

If we choose $b_{t}=c\sqrt{H^{3}\iota^{\prime}/t}$ for the same constant $c$
as in inequality (7), we have
$\beta_{t}/2=\sum_{i=1}^{t}\alpha_{t}^{i}b_{i}\in[c\sqrt{H^{3}\iota^{\prime}/t},2c\sqrt{H^{3}\iota^{\prime}/t}]$
according to Lemma 4.1.a. Then the right-hand side of Lemma 4.3 follows
immediately from Lemma 4.2 and inequality (7). The left-hand side also follows
from Lemma 4.2. ∎

We are now ready to prove Theorem 1.

###### Proof of Theorem 1.

We follow a similar procedure to Jin et al. (2018), except we do not have to
decompose the regret into a recursive form in $h$ since we are interested in a
fixed $h=1$. We denote $\delta_{1}^{k}:=(V_{1}^{k}-V_{1}^{\pi_{1}^{k}})(x1)$.

By Lemma 4.3, we have that with at least $1-p$ probability,
$Q_{1}^{k}(x1,a1)\geq Q_{1}^{*}(x1,a1)$ and thus $V_{1}^{k}(x1)\geq
V_{1}^{*}(x1)$. We also know that $Q_{1}^{k}(x,a)=Q_{1}^{*}(x,a),\
\forall(x,a)\in\mathcal{S}\times\mathcal{A}\backslash(x1,a1)$ and thus
$V_{1}^{k}(x)=V_{1}^{*}(x),\ \forall x\in\mathcal{S}\backslash x1$. The regret
can be upper bounded:

$\displaystyle\text{Regret}(K)$
$\displaystyle=\sum_{k=1}^{K}(V_{1}^{*}-V_{1}^{\pi_{1}^{k}})(x_{1}^{k})\leq\sum_{k=1}^{K}(V_{1}^{k}-V_{1}^{\pi_{1}^{k}})(x_{1}^{k})$
$\displaystyle\stackrel{{\scriptstyle\leavevmode\hbox to5.36pt{\vbox
to5.36pt{\pgfpicture\makeatletter\hbox{\hskip 2.68126pt\lower-2.68126pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.48126pt}{0.0pt}\pgfsys@curveto{2.48126pt}{1.37038pt}{1.37038pt}{2.48126pt}{0.0pt}{2.48126pt}\pgfsys@curveto{-1.37038pt}{2.48126pt}{-2.48126pt}{1.37038pt}{-2.48126pt}{0.0pt}\pgfsys@curveto{-2.48126pt}{-1.37038pt}{-1.37038pt}{-2.48126pt}{0.0pt}{-2.48126pt}\pgfsys@curveto{1.37038pt}{-2.48126pt}{2.48126pt}{-1.37038pt}{2.48126pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{\leq}}\sum_{k=1}^{K}(V_{1}^{k}-V_{1}^{\pi_{1}^{k}})(x1)=\sum_{k=1}^{K}\delta_{1}^{k}$
(8)

where inequality ① holds because
$\sum_{k=1}^{K}(V_{1}^{k}-V_{1}^{\pi_{1}^{k}})(x_{1}^{k})=0,\ \forall
x\in\mathcal{S}\backslash x1$.

For any fixed $k,\ \in[K]$, let $t=N_{1}^{k}(x1,a1)$ and suppose $(x1,a1)$ was
previously taken at step $h=1$ of episode $k_{1},...,k_{t}<k$, Then we have:

$\displaystyle\delta_{1}^{k}$
$\displaystyle=(V_{1}^{k}-V_{1}^{\pi_{1}^{k}})(x1)\stackrel{{\scriptstyle\leavevmode\hbox
to5.36pt{\vbox to5.36pt{\pgfpicture\makeatletter\hbox{\hskip
2.68126pt\lower-2.68126pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.48126pt}{0.0pt}\pgfsys@curveto{2.48126pt}{1.37038pt}{1.37038pt}{2.48126pt}{0.0pt}{2.48126pt}\pgfsys@curveto{-1.37038pt}{2.48126pt}{-2.48126pt}{1.37038pt}{-2.48126pt}{0.0pt}\pgfsys@curveto{-2.48126pt}{-1.37038pt}{-1.37038pt}{-2.48126pt}{0.0pt}{-2.48126pt}\pgfsys@curveto{1.37038pt}{-2.48126pt}{2.48126pt}{-1.37038pt}{2.48126pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{=}}(Q_{1}^{k}-Q_{1}^{\pi_{1}^{k}})(x1,a_{1}^{k})$
$\displaystyle=(Q_{1}^{k}-Q_{1}^{*})(x1,a_{1}^{k})+(Q_{1}^{*}-Q_{1}^{\pi_{1}^{k}})(x1,a_{1}^{k})$
$\displaystyle\stackrel{{\scriptstyle\leavevmode\hbox to5.36pt{\vbox
to5.36pt{\pgfpicture\makeatletter\hbox{\hskip 2.68126pt\lower-2.68126pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.48126pt}{0.0pt}\pgfsys@curveto{2.48126pt}{1.37038pt}{1.37038pt}{2.48126pt}{0.0pt}{2.48126pt}\pgfsys@curveto{-1.37038pt}{2.48126pt}{-2.48126pt}{1.37038pt}{-2.48126pt}{0.0pt}\pgfsys@curveto{-2.48126pt}{-1.37038pt}{-1.37038pt}{-2.48126pt}{0.0pt}{-2.48126pt}\pgfsys@curveto{1.37038pt}{-2.48126pt}{2.48126pt}{-1.37038pt}{2.48126pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{2}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{=}}(Q_{1}^{k}-Q_{1}^{*})(x1,a1)+(Q_{1}^{*}-Q_{1}^{\pi_{1}^{k}})(x1,a1)$
$\displaystyle\stackrel{{\scriptstyle\leavevmode\hbox to5.36pt{\vbox
to5.36pt{\pgfpicture\makeatletter\hbox{\hskip 2.68126pt\lower-2.68126pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.48126pt}{0.0pt}\pgfsys@curveto{2.48126pt}{1.37038pt}{1.37038pt}{2.48126pt}{0.0pt}{2.48126pt}\pgfsys@curveto{-1.37038pt}{2.48126pt}{-2.48126pt}{1.37038pt}{-2.48126pt}{0.0pt}\pgfsys@curveto{-2.48126pt}{-1.37038pt}{-1.37038pt}{-2.48126pt}{0.0pt}{-2.48126pt}\pgfsys@curveto{1.37038pt}{-2.48126pt}{2.48126pt}{-1.37038pt}{2.48126pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{3}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{\leq}}\alpha_{t}^{0}H+\beta_{t}+[\mathbb{P}_{1}(V_{2}^{*}-V_{2}^{\pi_{1}^{k}})](x1,a1)$
$\displaystyle\stackrel{{\scriptstyle\leavevmode\hbox to5.36pt{\vbox
to5.36pt{\pgfpicture\makeatletter\hbox{\hskip 2.68126pt\lower-2.68126pt\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.48126pt}{0.0pt}\pgfsys@curveto{2.48126pt}{1.37038pt}{1.37038pt}{2.48126pt}{0.0pt}{2.48126pt}\pgfsys@curveto{-1.37038pt}{2.48126pt}{-2.48126pt}{1.37038pt}{-2.48126pt}{0.0pt}\pgfsys@curveto{-2.48126pt}{-1.37038pt}{-1.37038pt}{-2.48126pt}{0.0pt}{-2.48126pt}\pgfsys@curveto{1.37038pt}{-2.48126pt}{2.48126pt}{-1.37038pt}{2.48126pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{4}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{=}}\alpha_{t}^{0}H+\beta_{t}$
(9)

where $\beta=2\sum\alpha_{t}^{i}b_{i}\leq O(1)\sqrt{H^{3}\iota^{\prime}/t}$.
Equality ① holds because
$V_{1}^{k}(x1)=\max_{a^{\prime}\in\mathbb{A}}Q_{1}^{k}(x1,a^{\prime})=Q_{1}^{k}(x1,a_{1}^{k})$.
Equality ② holds because $Q_{1}^{k}(x1,a_{1}^{k})=Q_{1}^{*}(x1,a_{1}^{k}),\
\forall a_{1}^{k}\in\mathcal{A}\backslash a1$ and
$Q_{1}^{*}(x1,a_{1}^{k})=Q_{1}^{\pi_{h}^{k}}(x1,a_{1}^{k}),\ \forall
a_{1}^{k}\in\mathcal{A}\backslash a1$. Inequality ③ holds with at least $1-p$
probability by Lemma 4.3 and the Bellman equations (1). Finally, equality ④
holds since $[\mathbb{P}_{h}(V_{h+1}^{\pi_{h}^{k}}-V_{h+1}^{*})](x1,a1)=0$ for
$\ h\geq 1,\forall k\in[K]$. We now compute the summation
$\sum_{k=1}^{K}\delta_{1}^{k}$. Denoting $n_{1}^{k}=N_{1}^{k}(x1,a1)$, we
have:

$\sum_{k=1}^{K}\alpha_{n_{1}^{k}}^{0}H=\sum_{k=1}^{K}H\cdot\mathbb{I}[n_{1}^{k}=0]\leq
H$ (10)

We also have:

$\sum_{k=1}^{K}\beta_{n_{1}^{k}}\leq
O(1)\cdot\sum_{k=1}^{K}\sqrt{\frac{H^{3}\iota^{\prime}}{n_{1}^{k}}}=O(1)\sum_{n=1}^{N_{1}^{K}(x1,a1)}\sqrt{\frac{H^{3}\iota^{\prime}}{n}}\stackrel{{\scriptstyle\leavevmode\hbox
to5.36pt{\vbox to5.36pt{\pgfpicture\makeatletter\hbox{\hskip
2.68126pt\lower-2.68126pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.48126pt}{0.0pt}\pgfsys@curveto{2.48126pt}{1.37038pt}{1.37038pt}{2.48126pt}{0.0pt}{2.48126pt}\pgfsys@curveto{-1.37038pt}{2.48126pt}{-2.48126pt}{1.37038pt}{-2.48126pt}{0.0pt}\pgfsys@curveto{-2.48126pt}{-1.37038pt}{-1.37038pt}{-2.48126pt}{0.0pt}{-2.48126pt}\pgfsys@curveto{1.37038pt}{-2.48126pt}{2.48126pt}{-1.37038pt}{2.48126pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{\leq}}O(\sqrt{H^{2}T\iota^{\prime}})$
(11)

where inequality ① is true because the left-hand side of ① is maximized when
$N_{1}^{k}(x1,a1)=K$, and $\sum_{n=1}^{K}\sqrt{\frac{1}{n}}$ can be bounded by
$O(\sqrt{K})$. Taking the sum from $k=1$ to $K$ for (4) and plugging in (10)
and (11) we have:

$\sum_{k=1}^{K}\delta_{1}^{k}\leq
O(H+\sqrt{H^{2}T\iota^{\prime}})\stackrel{{\scriptstyle\leavevmode\hbox
to5.36pt{\vbox to5.36pt{\pgfpicture\makeatletter\hbox{\hskip
2.68126pt\lower-2.68126pt\hbox to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{
}\pgfsys@setlinewidth{0.4pt}\pgfsys@invoke{ }\nullfont\hbox
to0.0pt{\pgfsys@beginscope\pgfsys@invoke{
}{{}}{{}}\hbox{\hbox{{\pgfsys@beginscope\pgfsys@invoke{
}{{}{{{}}}{{}}{}{}{}{}{}{}{}{}{}{{}\pgfsys@moveto{2.48126pt}{0.0pt}\pgfsys@curveto{2.48126pt}{1.37038pt}{1.37038pt}{2.48126pt}{0.0pt}{2.48126pt}\pgfsys@curveto{-1.37038pt}{2.48126pt}{-2.48126pt}{1.37038pt}{-2.48126pt}{0.0pt}\pgfsys@curveto{-2.48126pt}{-1.37038pt}{-1.37038pt}{-2.48126pt}{0.0pt}{-2.48126pt}\pgfsys@curveto{1.37038pt}{-2.48126pt}{2.48126pt}{-1.37038pt}{2.48126pt}{0.0pt}\pgfsys@closepath\pgfsys@moveto{0.0pt}{0.0pt}\pgfsys@stroke\pgfsys@invoke{
} }{{{{}}\pgfsys@beginscope\pgfsys@invoke{
}\pgfsys@transformcm{0.7}{0.0}{0.0}{0.7}{-1.22499pt}{-1.57887pt}\pgfsys@invoke{
}\hbox{{\definecolor{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@rgb@stroke{0}{0}{0}\pgfsys@invoke{
}\pgfsys@color@rgb@fill{0}{0}{0}\pgfsys@invoke{ }\hbox{{1}}
}}\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope }\pgfsys@endscope}}}
\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope{}{}{}\hss}\pgfsys@discardpath\pgfsys@invoke{\lxSVG@closescope
}\pgfsys@endscope\hss}}\lxSVG@closescope\endpgfpicture}}}}{{=}}O(\sqrt{H^{2}T\iota^{\prime}})$

where ① is true since $\sqrt{H^{2}T\iota^{\prime}}\geq H$.

Recall that Lemma 4.3 was applied twice in this proof (once in equation (8)
and once in ③ in equation (4)). Note that $(1-p)^{2}=1-2p+p^{2}\geq 1-2p$,
where the last inequality is applied because the $p^{2}$ term is small when
compared to $2p$. In summary, we have that $\sum_{k=1}^{K}\delta_{1}^{k}\leq
O(\sqrt{H^{2}T\iota^{\prime}})$ holds with probability at least $1-2p$. Note
the term $p$ cannot be greater than $1/2$ to ensure the probability $1-2p$ is
non-negative. This can be achieved by re-scaling $p\to p/2$ to reduce it’s
range from $[0,1]$ to $[0,1/2]$. As such, re-scaling $p$ to $p/2$ finishes the
proof. ∎

##  5\. Experimental Setup

Figure 1. The environment the agent was trained in can be seen in (a). For the
purpose of simplifying the image we use the notation $r(x1)=0$, $r(x2)=0$, and
$r(x3)=1$ to represent the reward the agent receives for transitioning into
states $x1,x2,x3$ respectively. The optimal policy is shown in (b).

In the previous section we proved the theoretical total regret of the
$Q$-learning with Max-Optimal Initialization algorithm is bounded by
$O(\sqrt{H^{2}T\iota^{\prime}})$, while the total regret of the $Q$-learning
with UCB-Hoeffding algorithm is bounded by $O(\sqrt{H^{4}SAT\iota})$ Jin et
al. (2018). This result implies that our statement of interest holds true
theoretically. In this section our goal is to empirically show that results
are consistent with our theoretical findings. We do this by choosing a simple
tabular environment to compare both algorithms. The simple environment will
allow for easier interpretation of results. We expect the empirical results to
hold for larger and more complex environments.

The environment used is a 1-dimensional gridworld, with $3$ states, and $2$
actions (see Figure 1 (a)). The actions are left and right, and when the agent
takes an action that causes it to hit a wall it remains in the same state. All
transitions and rewards are deterministic. The agent receives a reward of $1$
if its next state is the right most state and a reward of $0$ otherwise. The
agent interacts with the environment for exactly $3$ steps each episode. The
optimal policy is to go right ($a2$) in all states for all steps (See Figure 1
(b)). Formally this setting can be represented by a
MDP$(\mathcal{S},\mathcal{A},H,\mathbb{P},r)$, where there are $3$ states
$\mathcal{S}=\\{x1,x2,x3\\}$, $2$ actions $\mathcal{A}=\\{a1,a2\\}$, the
horizon is $H=3$, and the transition dynamics and reward function are as
follows for all $h\in[H]=\\{1,2,3\\}$:

$\begin{cases}\mathbb{P}_{h}(x1|x1,a1)=1\\\ \mathbb{P}_{h}(x2|x1,a2)=1\\\
\mathbb{P}_{h}(x1|x2,a1)=1\\\ \mathbb{P}_{h}(x3|x2,a2)=1\\\
\mathbb{P}_{h}(x2|x3,a1)=1\\\ \mathbb{P}_{h}(x3|x3,a2)=1\\\
\end{cases}\quad\text{and}\quad\begin{cases}r_{h}(x1,a1)=0\\\
r_{h}(x1,a2)=0\\\ r_{h}(x2,a1)=0\\\ r_{h}(x2,a2)=1\\\ r_{h}(x3,a1)=0\\\
r_{h}(x3,a2)=1\\\ \end{cases}$

Recall that our algorithm makes two important changes to the $Q$-learning with
UCB-Hoeffding algorithm from Jin et al. (2018). Namely, the initialization is
changed according to equation (LABEL:Initialization_equations) and the
$Q$-function is only updated if the current state, action, and step is
$(x1,a1,h=1)$. We refer to these two changes as assumption 1 (A1) and
assumption 2 (A2) respectively. We train an agent using three different
algorithms:

  1. (1)

$Q$-learning with UCB-Hoeffding Jin et al. (2018)

  2. (2)

$Q$-learning with UCB-Hoeffding and Max-Optimal Initialization without A2

  3. (3)

$Q$-learning with UCB-Hoeffding and Max-Optimal Initialization (Algorithm 1)

From the above enumeration, points 1 and 3 have already been discussed in
detail and are shown explicitly as Algorithm 1 and Algorithm 1 in Jin et al.
(2018) respectively. The goal of point 2 is to show that A2 is crucial for our
theoretical regret bound (as seen in Theorem 1). Since A2 is removed in point
2, we expect the total regret to be greater than that of our algorithm. An
important detail is that the $Q$-learning with UCB-Hoeffding and Max-Optimal
Initialization without A2 algorithm is the same as our algorithm except with
A2 removed, but also with $N_{h}(x,a)$ initialized to $0$ for all
$(x,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]$. Since now the $Q$-function
is updated for all states, actions, and steps, a visit count $N_{h}(x,a)$ must
be kept for all $(x,a,h)$.

An agent was trained using each algorithm for $500$ episodes, $K=500$. We set
the probability term $p=0.05$, corresponding to a probability of at least
$1-p=0.95$ of obtaining a total regret of $O(\sqrt{H^{2}T\iota^{\prime}})$ as
mentioned in Theorem 1. The constant used for the bonus $b_{t}$ was set to
$c=0.1$. For the $Q$-learning with UCB-Hoeffding and Max-Optimal
initialization algorithm we set $(x1,a1,h=1)$ as the non-optimal $Q$-value.

Recall that going left ($a1$) in the left-most state $x1$ causes the agent to
hit a wall and remain in state $x1$. Action $a1$ is not the optimal action in
state $x1$, since the agent will only receive a reward of $1$ for
transitioning into the right-most state, which going left, $a1$ does not help
achieve. The optimal action is for the agent to go right ($a2$) from state
$x1$. Intuitively, the above initialization causes the agent to have low
confidence in $(x1,a1,h=1)$ and therefore the agent will explore $(x1,a1,h=1)$
until it is confident enough that $(x1,a1)$ actually provides it with less
total reward than $(x1,a2)$ at step $h=1$.

As a way to measure performance per episode we introduce:

$\text{Per Episode
Regret}=\text{PER}(k)=V_{1}^{*}(x_{1}^{k})-V_{1}^{\pi_{h}^{k}}(x_{1}^{k})$

When the PER is summed over all episodes it gives the total regret. In our
experiments, the PER was averaged over $50$ independent runs for each
algorithm.

##  6\. Experimental Results

Figure 2. A Per Episode Regret plot of algorithm UCB-H, UCB-H MO, and UCB-H MO
A2 averaged over $50$ independent runs. The shaded regions represent a 95%
confidence interval.

Figure 2 shows the results of training an agent in the setting mentioned in
the previous section. For convenience, we will refer to the $Q$-learning with
UCB-Hoeffding and Max-Optimal Initialization algorithm as UCB-H MO, and the
$Q$-learning with UCB-Hoeffding and Max-Optimal Initialization without A2
algorithm as UCB-H MO A2, and to the $Q$-learning with UCB-Hoeffding as UCB-H.
In Figure 2 we observe that the per episode regret converges to zero fastest
for UCB-H MO. A faster convergence to zero implies that the total regret of
UCB-H MO is lower than that of UCB-H MO A2 and UCB-H, since the total regret
is just the sum of the PER over all episodes. Recall from the theoretical
results that the total regret of UCB-H MO is $O(\sqrt{H^{2}T\iota^{\prime}})$,
while UCB-H has a total regret of $O(\sqrt{H^{4}SAT\iota})$. Therefore, this
is the expected behaviour of UCB-H MO when compared to UCB-H based on our
theoretical results. Since UCB-H MO also converges faster than UCB-H MO A2 it
supports our earlier claim that A2 is crucial to the theoretical regret bound
we obtain (see Theorem 1).

##  7\. Discussion and Future Work

In summary, we showed that the total regret of $Q$-learning with UCB-Hoeffding
and Max-Optimal Initialization is upper bounded by
$O(\sqrt{H^{2}T\iota^{\prime}})$. This total regret bound is tighter than that
of the $Q$-learning with UCB-Hoeffding algorithm, $O(\sqrt{H^{4}SAT\iota})$
Jin et al. (2018). This result provides theoretical justification for applying
$Q$-function reuse on the $Q$-function with UCB-Hoeffding algorithm. Although
we make the strong assumption that all but one of the Q-values are optimal, we
believe that this provides a solid starting point for future work to build
upon.

We believe some interesting future directions are:

  1. (1)

Increasing the number of non-optimal $Q$-values. In this work it was assumed
that the $Q$-function was optimal for all but one state, action, and step
$(x1,a1,h=1)$. One possible next step would be to assume that the $Q$-values
of two or more states, actions, and steps are non-optimal. This might make the
analysis more complex because the proof of Lemma 4.2 assumed that
$V_{h}^{k}(x_{h}^{k})=V_{h}^{*}(x_{h}^{k})$ for $h\geq 2,\forall k\in[K]$
which would no longer be true if one of the non-optimal $Q$-values occurred
for $h\geq 2$.

  2. (2)

Relaxing the $Q$-function optimality assumption for some
$(x,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]\backslash(x1,a1,h=1)$ to some
notion of near-optimality. This work assumes that the $Q$-functions was
optimal for all but one state, action, and step $(x1,a1,h=1)$. This assumption
is generally unrealistic for a transferred $Q$-function because an agent
rarely learns the optimal $Q$-function in an environment (instead, it often
only reaches a near-optimal one). Such cases can potentially be modelled by
assuming some sub-optimality of the $Q$-function initialization. For instance,
for some subset of states, actions, and steps it could be assumed that
$Q_{h}(x,a)\geq Q^{*}_{h}(x,a)-\epsilon,\ \forall(x,a,h),\epsilon\geq 0$

  3. (3)

Allowing the $Q$-function to be updated for some
$(x,a,h)\in\mathcal{S}\times\mathcal{A}\times[H]\backslash(x1,a1,h=1)$. In
this work it was assumed that we had prior knowledge of which states, actions,
and steps the $Q$-function was optimally initialized (i.e.
$Q_{h}(x,a)=Q^{*}_{h}(x,a),\
\forall\mathcal{S}\times\mathcal{A}\times[H]\backslash(x1,a1,h=1)$) and
therefore we were able to explicitly choose to not perform $Q$-function
updates at those states, actions and steps. It may not always be the case that
this information is known. As such, the algorithm would not update the
$Q$-function for all states, actions and steps. Modifications to the analysis
done in this work would have to be made to provide an upper bound on the
regret of such an algorithm because a $Q$-function update performed at an
optimal state, action, and step might depend on the $Q$-function at a non-
optimal state, action, and step. Such an update can potentially change the
value of the $Q$-function at the optimal state, action, and step, causing for
an increase in the number of non-optimal $Q$-values.

This work has taken place in the Intelligent Robot Learning (IRL) Lab at the
University of Alberta, which is supported in part by research grants from the
Alberta Machine Intelligence Institute (Amii) and NSERC, as well as a Canada
CIFAR AI Chair.

## References

  * (1)
  * Azar et al. (2017) Mohammad Gheshlaghi Azar, Ian Osband, and Rémi Munos. 2017\.  Minimax regret bounds for reinforcement learning.  _arXiv preprint arXiv:1703.05449_ (2017).
  * Jin et al. (2018) Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. 2018.  Is Q-learning provably efficient. In _Advances in Neural Information Processing Systems_. 4863–4873.
  * Kakade et al. (2003) Sham Machandranath Kakade et al. 2003\.  _On the sample complexity of reinforcement learning_.  Ph.D. Dissertation. University of London London, England.
  * Kearns and Singh (2002) Michael Kearns and Satinder Singh. 2002.  Near-optimal reinforcement learning in polynomial time.  _Machine learning_ 49, 2-3 (2002), 209–232.
  * Sutton and Barto (2018) Richard S Sutton and Andrew G Barto. 2018.  _Reinforcement learning: An introduction_.  MIT press.
  * Taylor and Stone (2009) Matthew E Taylor and Peter Stone. 2009.  Transfer learning for reinforcement learning domains: A survey.  _Journal of Machine Learning Research_ 10, 7 (2009).
  * Zhu et al. (2020) Zhuangdi Zhu, Kaixiang Lin, and Jiayu Zhou. 2020.  Transfer Learning in Deep Reinforcement Learning: A Survey.  _arXiv preprint arXiv:2009.07888_ (2020).