algorithmic

# Efficient Online Learning with Offline Datasets for Infinite Horizon MDPs: A
Bayesian Approach

Dengwang Tang  University of Southern California  Rahul Jain  University of
Southern California  Botao Hao  DeepMind  Zheng Wen  DeepMind

###### Abstract

In this paper, we study the problem of efficient online reinforcement learning
in the infinite horizon setting when there is an offline dataset to start
with. We assume that the offline dataset is generated by an expert but with
unknown level of competence, i.e., it is not perfect and not necessarily using
the optimal policy. We show that if the learning agent models the behavioral
policy (parameterized by a competence parameter) used by the expert, it can do
substantially better in terms of minimizing cumulative regret, than if it
doesn’t do that. We establish an upper bound on regret of the exact informed
PSRL algorithm that scales as $\tilde{O}(\sqrt{T})$. This requires a novel
prior-dependent regret analysis of Bayesian online learning algorithms for the
infinite horizon setting. We then propose an approximate Informed RLSVI
algorithm that we can interpret as performing imitation learning with the
offline dataset, and then performing online learning.

##  1 Introduction

The original vision of Reinforcement Learning (RL) was that of a learning
agent taking actions, getting state and reward feedback and learning from it.
The learning agent may have some prior information but learning mostly happens
from these online interactions. This requires carefully-crafted strategies
that balance exploration and exploitation, including the need for deep
exploration in many sequential decision-making problems. This was regarded as
a difficult problem for a long time. Fortunately, over the last decade or so,
substantial progress has been made on the online reinforcement learning (ORL)
problem. Unfortunately, ORL Algorithms tend to be rather “data-hungry”, i.e.,
they require a lot more interaction data than other types of learning methods.

In some ORL problem settings, offline datasets are available. There is thus a
possibility of improving learning efficiency by using offline datasets for
pre-training, and then the learning agent does further fine-tuning upon
deployment for online learning. For example, such offline could be
demonstrations from an expert, or even a sub-expert. This allows for
addressing the distribution shift problem with the offline reinforcement
learning methods, i.e., policy learnt offline do not perform well because the
distribution of the system upon deployment is different from the one
encountered offline. One can also expect that when such offline datasets are
available for pre-training, it would improve online learning efficiency (in
terms of cumulative regret). The question is by how much, and how does it
depend on the dataset quality, and indeed how do we even quantify dataset
quality. Furthermore, even with the same dataset, a question arises on how to
extract the most from such a given dataset.

An important reason via a combination of offline and online learning is
important is that reinforcement learning from offline datasets can often
suffer from the _distribution shift_ problem, i.e. the distribution of the
system upon deployment is different from the one encountered offline, and
hence the policy learnt offline do not perform well upon deployment. Learning
from offline dataset first followed by online learning allows for adaptation
of learnt policies to different distributions of the underlying environment.

In this paper, we develop a systematic method to incorporate expert
demonstrations into online learning algorithms to facilitate faster learning
for infinite horizon MDPs. We first propose the idealized _infinite-horizon
informed Posterior Sampling based Reinforcement Learning_ (inf-iPSRL)
algorithm. Under some mild assumptions on the underlying MDP, we show that the
algorithm achieves $O(1)+\tilde{O}(\sqrt{\varepsilon T})$ where $\varepsilon$
is the estimation error probability of the optimal policy given the offline
data, and $T$ is the learning horizon. The regret bound also has polynomial
dependence on problem parameters of the underlying MDP. We also show that, if
the offline data is generated by an expert with suitably high competence
level, under certain assumptions, the regret of the inf-iPSRL algorithm goes
to $O(1)$ as the size of the demonstration dataset goes to infinity. We would
also like to point out the inf-iPSRL algorithm has a simpler design compared
to the TSDE algorithm in Ouyang et al. (2017), since the TSDE algorithm uses a
visitation-count-based episode schedule while the inf-iPSRL algorithm uses
fixed episode schedules. However, the inf-iPSRL algorithm is still impractical
due to the complicated nature of exact posterior updates. Therefore we
introduce the _informed randomized least-squares value iteration_ (inf-iRLSVI)
algorithm which replaces exact posterior sampling with an approximation
procedure. Just like the RSVI algorithm of Osband et al. (2019) (from which we
borrowed the name), the inf-iRLSVI algorithm generates approximate posterior
samples via optimizing a randomly perturbed loss function.

Related Work. Recently, offline reinforcement learning, where offline datasets
are incorporated (Levine et al., 2020), has attracted some interest due to the
widespread practice of pre-training with offline datasets in large language
models (Brown et al., 2020; Thoppilan et al., 2022; Hoffmann et al., 2022).
One fundamental challenge in this line of research is the _distribution shift_
problem, where the policy learnt from offline data performs poorly in the real
world. To address this problem, Jin et al. (2021); Rashidinejad et al. (2021);
Xie et al. (2021a) adopted the _pessimistic_ approach, which can be overly
conservative in practice. In Uehara and Sun (2021); Rashidinejad et al.
(2021); Xie et al. (2021a); Agarwal and Zhang (2022), the authors identified
sufficient conditions on the dataset that guarantees a certain level of
performance for offline RL algorithms. However, determining whether the
dataset meets these conditions can be a complicated problem itself, hence
making these results impractical (Kumar et al., 2020; Nair et al., 2020;
Argenson and Dulac-Arnold, 2020; Levine et al., 2020; Kostrikov et al., 2021;
Wagenmaker and Pacchiano, 2022).

On the other hand, there have been many works on online reinforcement learning
(See Russo et al. (2018) for a survey). Among these works, there are two
prominent approaches: the optimism under the face of uncertainty (OFU)
approach (Auer et al., 2008) and posterior sampling (PS) approach (Osband et
al., 2013; Russo and Van Roy, 2016; Ouyang et al., 2017). Most work in online
RL focuses on the online dataset and does not consider leveraging the offline
dataset. Closely related to the idea of using the offline dataset is the
concept of imitation learning (Schaal, 1996; Hester et al., 2018; Beliaev et
al., 2022), where one aims to learn the behavioral policy of the expert from
the offline dataset. No online finetuning is present in these works. In Ernst
et al. (2005); Vecerik et al. (2017); Rashidinejad et al. (2021); Hansen et
al. (2022); Kumar et al. (2022); Lee et al. (2022), the authors combine
imitation learning with more traditional offline RL methods. In (Schrittwieser
et al., 2021; Uehara and Sun, 2021; Xie et al., 2021b; Agarwal and Zhang,
2022; Song et al., 2022; Fang et al., 2022; Wan et al., 2022; Ball et al.,
2023), the authors combined offline RL with limited online policy fine-tuning
to minimize the simple regret.

##  2 Preliminaries

We first formally introduce our model, assumptions and problem statement.

We assume that a learning agent interacts with a time-homogeneous controlled
Markov chain over time, where an instantaneous reward is generated at each
time. The process is represented by a tuple
$\mathcal{M}=(\mathcal{S},\mathcal{A},P,r,\nu)$, where $\mathcal{S}$ is the
state space; $\mathcal{A}$ is the action space;
$P:\mathcal{S}\times\mathcal{A}\mapsto\Delta(\mathcal{S})$ is the transition
kernel (where $\Delta(\mathcal{S})$ represents the set of distributions on
$\mathcal{S}$); $r:\mathcal{S}\times\mathcal{A}\mapsto[0,1]$ is the
instantaneous reward function; $\nu\in\Delta(\mathcal{S})$ is the distribution
of the initial state. At time $t=0$, the initial state $s_{0}$ is drawn from
$\nu$. At each time $t\in\mathbb{Z}_{+}$, the agent chooses an action
$a_{t}\in\mathcal{A}$, and the next state $s_{t+1}$ is chosen according to the
distribution $P(\cdot|s_{t},a_{t})$. The objective of the agent is to choose a
policy $\pi$ to maximize the expected average reward over the infinite
horizon, i.e. maximizing

$\bar{r}^{\pi}:=\lim_{T\rightarrow\infty}\dfrac{1}{T}\mathbb{E}^{\pi}\left[\sum_{t=0}^{T-1}r(s_{t},a_{t})\right]$
(1)

From standard literature on MDPs (Bertsekas, 1995), we know that if the
controlled Markov chain is _communicating_ (i.e., for any pair of states
$s,s^{\prime}\in\mathcal{S}$, there exists a stationary Markov policy $\pi$
and an integer $k\in\mathbb{N}$ such that
$\mathbb{P}_{\theta}^{\pi}(s_{k}=s^{\prime}|s_{0}=s)>0$), the optimal expected
average reward and an optimal policy can be obtained though total discounted
rewards: Let $\gamma\in(0,1)$ be the discount factor. Define
$V_{\gamma}^{*}(s):=\max_{\pi}\mathbb{E}^{\pi}\left[\sum_{t=0}^{\infty}\gamma^{t}r(s_{t},a_{t})|s_{0}=s\right]$
to be the optimal total discounted reward when the initial state is
$s\in\mathcal{S}$. Let $\hat{s}\in\mathcal{S}$ be an arbitrary reference
state, then we have

$\displaystyle\bar{r}^{*}$ $\displaystyle:=\lim_{\gamma\rightarrow
1}(1-\gamma)V_{\gamma}^{*}(\hat{s})$ (2)

to be the optimal expected average reward for this MDP with any starting
state. Furthermore, an optimal policy can be recovered as follows. Define the
relative state value function

$\displaystyle v(s)$ $\displaystyle:=\lim_{\gamma\rightarrow
1}[V_{\gamma}^{*}(s)-V_{\gamma}^{*}(\hat{s})]\qquad\forall s\in\mathcal{S}$
(3)

which represents the long-term difference of the optimal expected total reward
if the MDP starts at $s$ comparing to starting at $\hat{s}$ (Bertsekas, 1995).
Standard results show that $\bar{r}^{*}$ and $v^{*}$ satisfy the Bellman
equation (Bertsekas, 1995):

$\bar{r}^{*}+v(s)=\max_{a\in\mathcal{A}}\left[r(s,a)+\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)v(s^{\prime})\right]$
(4)

for every $s\in\mathcal{S}$. Define the relative state-action value function

$q(s,a):=r(s,a)+\sum_{s^{\prime}\in\mathcal{S}}P(s^{\prime}|s,a)v(s^{\prime})$
(5)

then any deterministic stationary Markov policy $\pi$ such that
$\pi(s)\in\operatorname*{arg\,max}_{a\in\mathcal{A}}q(s,a)$ for every
$s\in\mathcal{S}$ maximizes the expected average reward.

We assume that the learning agent does not possess full knowledge about the
environment $\mathcal{M}$. The agent may however, have complete or partial
prior knowledge about certain parameters of $\mathcal{M}$. To provide a
general model for such prior knowledge, we use $\mathcal{M}(\theta)$ to denote
an environment parameterized by some parameter $\theta$ that lies in the set
$\varTheta$. The true environment is given by a random variable $\theta^{*}$
with distribution $\mu_{0}\in\Delta(\varTheta)$. We make the following
assumptions on the environment.

######  Assumption 2.1.

For all $\theta\in\varTheta$, $\mathcal{M}(\theta)$ is a communicating MDP.

In a general infinite horizon MDP, it is possible that one decision made at a
certain time can have an irreversible effect on the total reward: It is
possible that one enters a communicating class with suboptimal average reward.
Assumption 2.1 ensures that one could explore the MDP using any policy since
there’s always a pathway to return to the “optimal part” of the state space.
See Ouyang et al. (2017) for more discussions.

For a communicating MDP $\mathcal{M}(\theta)$, we use
$\bar{r}^{*}(\theta),v(\cdot;\theta)$, and $q(\cdot,\cdot;\theta)$ to denote
their corresponding $\bar{r}^{*},v^{*},$ and $q^{*}$ functions, as defined in
(2), (3) and (5) respectively. We also make Assumption 2.2, which is the same
as that in Ouyang et al. (2017).

######  Assumption 2.2.

There exists $\bar{v}\in\mathbb{R}_{+}$ such that
$\max_{s\in\mathcal{S}}v(s;\theta)-\min_{s\in\mathcal{S}}v(s;\theta)\leq\bar{v}$
for all $\theta\in\varTheta$.

Under the above assumptions we consider the canonical settings of tabular MDPs
as well as linear value function generalization for non-tabular MDPs, i.e.,
the Q-value function is representable in a subspace spanned by a given set of
features.

The learning agent has access to an _offline dataset_
$\mathcal{D}_{0}=\\{(\bar{s}_{0},\bar{a}_{0},\cdots,\bar{s}_{N-1},\bar{a}_{N-1},\bar{s}_{N})\\}$
generated by another agent, called the expert, who interacts with the same
environment before the learning agent started. The trajectory is generated
from applying a randomized stationary Markov policy on the true MDP
$\mathcal{M}(\theta^{*})$. The initial state $\bar{s}_{0}$ is assumed to be a
fixed, non-random state. We will describe the expert’s policy and the learning
agent’s knowledge about it later in this section. During the learning process,
the learning agent has access to the trajectory generated so far, which we
call the _online dataset_ and denote as
$\mathcal{H}_{t}=\\{(s_{0},a_{0},\cdots,s_{t-1},a_{t-1},s_{t})\\}$. At time
$t$, the learning agent’s information is given by
$\mathcal{D}_{t}:=\mathcal{D}_{0}\cup\mathcal{H}_{t}$.

The learning agent utilizes a learning algorithm $\phi$ to interact with the
environment, which at each time $t$ chooses a possibly randomized action based
on full or partial information in the dataset $\mathcal{D}_{t}$. Under the
environment $\mathcal{M}(\theta)$, the learning regret is defined as

$\mathfrak{R}_{T}(\phi;\theta):=T\bar{r}^{*}(\theta)-\mathbb{E}_{\theta}^{\phi}\left[\sum_{t=0}^{T-1}r_{t}(s_{t},a_{t})\right],$
(6)

where $\mathbb{E}_{\theta}^{\phi}$ denotes the expectation under the possible
trajectories generated by applying algorithm $\phi$ on the environment
$\mathcal{M}(\theta)$. The Bayesian regret is defined as

$\mathfrak{BR}_{T}(\phi):=\mathbb{E}_{\theta^{*}\sim\mu_{0}}[\mathfrak{R}_{T}(\phi;\theta^{*})]$
(7)

We model the expert’s policy in the following way. First, consider that the
expert, who generated the offline dataset, has perfect knowledge about the
underlying environment $\theta^{*}$ but uses an approximately optimal policy
in the demonstration. Then, the expert’s policy $\pi^{\beta}$ is modelled as:

$\pi^{\beta}(a|s):=\dfrac{\exp(\beta(s)q(s,a;\theta^{*}))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\beta(s)q(s,a^{\prime};\theta^{*}))}$
(8)

where $\beta(s)\geq 0$ is called the state-dependent deliberateness parameter:
$\beta(s)=0$ means that the expert takes actions uniformly randomly at state
$s$; A large $\beta(s)>0$ means that the expert uses a close-to-optimal policy
at state $s$.

Then, we consider a general model wherein the expert only knows a noisy
version of the optimal $q$-function. The expert uses the policy (8), except
that $q^{*}$ is replaced by $\tilde{q}$, the expert’s perceived state-action
value function. The vector $\tilde{q}$ follows Gaussian distribution with mean
$q^{*}$ and covariance $\mathbb{I}/\lambda^{2}$, where $\lambda>0$ is the
_knowledgeability_ parameter. The two parameters $(\beta,\lambda)$ together
will be referred to as the competence of the expert. In this case, we denote
the expert’s (stationary) policy as $\pi^{\beta,\lambda}$. Such a model was
first introduced in Hao et al. (2023).

The learning agent knows the form of the expert’s policy and the
knowledgeability parameter $\lambda$ but may not know the deliberateness
parameter $\beta$. When $\beta$ is unknown to the learning agent, we will
assume an independent exponential prior for the sake of analytical simplicity,
$f_{2}(\beta(s))=\lambda_{2}\exp(-\lambda_{2}\beta(s))$ over $\beta(s)$ where
$\lambda_{2}>0$ is the same for all $s$.

##  3 The Infinite-horizon Informed PSRL Algorithm for Average MDPs

We now introduce the _Informed Posterior Sampling-based Reinforcement
Learning_ (inf-iPSRL) algorithm (Algorithm 1) for infinite-horizon average
MDPs that combines the offline data with the powerful posterior sampling
method (Osband et al., 2013; Ouyang et al., 2017). We assume that the expert
knows the exact $q(\cdot,\cdot;\theta^{*})$ function and follows the policy
$\pi^{\beta}$ given by (8) with $\beta(s)=\beta>0$ for all $s\in\mathcal{S}$.
We assume that the learning agent knows $\beta$ but not $\theta^{*}$.
Therefore, the posterior distribution of $\theta^{*}$ given the offline data
$\mathcal{D}_{0}$ is given by

$\mu_{1}(\theta^{*}\in\cdot)\propto\int_{\theta\in\cdot}\mathbb{P}_{\theta}^{\pi^{\beta}}(\mathcal{D}_{0})\mathrm{d}\mu_{0}(\theta),$
(9)

where

$\mathbb{P}_{\theta}^{\pi^{\beta}}(\mathcal{D}_{0}):=\prod_{t=0}^{N-1}\theta(\bar{s}_{t+1}|\bar{s}_{t},\bar{a}_{t})\dfrac{\exp(\beta
q(\bar{s}_{t},\bar{a}_{t};\theta))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\beta
q(\bar{s}_{t},a^{\prime};\theta))}.$ (10)

In the inf-iPSRL algorithm we assume the availability of an planning oracle,
called MDPSolve, to output an optimal policy for the MDP $\mathcal{M}(\theta)$
given input $\theta$: We assume that MDPSolve is a deterministic mapping from
the space of parameters $\varTheta$ to the space of deterministic stationary
Markov strategies $\Pi$ with the following property:
$\pi=\texttt{MDPSolve}(\theta)$ satisfies
$\pi(s)\in\operatorname*{arg\,max}_{a\in\mathcal{A}}q(s,a;\theta)$ for all
$s\in\mathcal{S}$. Note that various dynamic programming algorithms such as
value iteration, policy iteration, etc. can be used in MDPSolve.

The inf-iPSRL algorithm divides the learning process into episodes, with
possibly different lengths. The episode lengths $\\{T_{k}\\}_{k=1}^{K}$ are
fixed and given as an input to the algorithm. Let
$t_{k}:=\sum_{j=1}^{k-1}T_{k}$ denote the starting time of episode $k$. At the
beginning of episode $k$, the learning agent randomly samples a new
environment $\tilde{\theta}^{k}$, uses the planning oracle MDPSolve to find an
average-reward maximizing policy $\tilde{\pi}^{k}$ for $\tilde{\theta}^{k}$,
and apply the policy $\tilde{\pi}^{k}$ for the duration of episode $k$.
Finally, after applying $\tilde{\pi}^{k}$ for $T_{k}$ steps, the learning
agent updates the posterior distribution of $\theta^{*}$ via

$\mu_{k+1}(\theta^{*}\in\cdot)\propto\int_{\theta\in\cdot}\prod_{t=t_{k}}^{t_{k+1}-1}\theta(s_{t+1}|s_{t},a_{t})\mathrm{d}\mu_{k}(\theta).$
(11)

Algorithm 1 inf-iPSRL Algorithm

Input: Prior $\mu^{0}\in\Delta(\varTheta)$; Offline data $\mathcal{D}_{0}$;
Episode schedule $\\{T_{k}\\}_{k=1}^{K}$

$t_{1}\leftarrow 0$

Compute $\mu_{1}$ with (9)

for $k=1$ to $K$ do

Sample $\tilde{\theta}^{k}\sim\mu^{k}$

$\tilde{\pi}^{k}\leftarrow\texttt{MDPSolve}(\tilde{\theta}^{k})$

$t_{k+1}\leftarrow t_{k}+T_{k}$

for $t=t_{k}$ to $t_{k+1}-1$ do

Take action $a_{t}=\tilde{\pi}^{k}(s_{t})$

end for

Compute $\mu_{k+1}$ with (10)

end for

###  3.1 Prior Dependent Bound

In this section, we develop a prior-dependent regret bound for the inf-iPSRL
algorithm on the tabular RL setting. The regret bound depends on the prior
distribution $\mu_{1}$ through the _initial mismatch probability_
$\varepsilon=\mathbb{P}(\tilde{\pi}^{1}\neq\pi^{*})$, where
$\pi^{*}=\texttt{MDPSolve}(\theta^{*})$ is the optimal policy of the
underlying true MDP consistent with planning oracle we used in the inf-iPSRL
algorithm. Intuitively, if the offline data is more informative, then the
initial posterior distribution on the optimal policy $\pi^{*}$ is more
concentrated, and then it’s more likely that the initial policy obtained from
posterior sampling is actually the optimal policy, meaning that $\varepsilon$
is small. We will formalize this at the end of this section.

######  Theorem 3.1.

Let $K_{T}:=\max\\{k:\sum_{l=1}^{k-1}T_{k}<T\\}$. The Bayesian regret for inf-
iPSRL algorithm satisfies

$\mathfrak{BR}_{T}(\phi^{\mathrm{iPSRL}})\leq
3\bar{v}+2\bar{v}(R_{1}+R_{2}+R_{3}),$ (12)

where

$\displaystyle R_{1}$ $\displaystyle:=\varepsilon K_{T},$ (13) $\displaystyle
R_{2}$ $\displaystyle:=\sqrt{\varepsilon
S^{2}AT\log(2SAK_{T}T)\left[1+\log\left(\frac{T}{SA}+1\right)\right]},$ (14)
$\displaystyle R_{3}$ $\displaystyle:=\min\left\\{\varepsilon
T,SA\left(\max_{k\in[K_{T}]}T_{k}\right)\log_{2}\left(\frac{T}{SA}+1\right)\right\\}.$
(15)

Note that the right-hand side of (12) depends on the episode schedule only
through (i) total number of episodes with time $T$, and (ii) the maximum
length of an episode within time $T$. Therefore, the best regret bound, in
general, can be obtained by setting both quantities to be roughly
$\Theta(\sqrt{T})$, which can be achieved when $T_{k}=\Theta(k)$. We formalize
this in the following two corollaries.

######  Corollary 3.2.

Consider the episode schedule $T_{k}=k$. Then,

$\mathfrak{BR}_{T}(\phi^{\mathrm{iPSRL}})\leq\tilde{O}(\bar{v}SA\sqrt{T}),$
(16)

where $\tilde{O}$ hides the logarithmic terms in $S,A,$ and $T$. Furthermore,
for fixed $\bar{v},S,A,T$ we also have an $O(1)+O(\sqrt{\varepsilon})$ regret
bound:

$\mathfrak{BR}_{T}(\phi^{\mathrm{iPSRL}})\leq
3\bar{v}+2\varepsilon\bar{v}T+\sqrt{\varepsilon}\bar{v}\cdot\tilde{O}(\sqrt{S^{2}AT}).$
(17)

######  Remark 3.3.

The only difference between the episode schedule of the TSDE algorithm in
Ouyang et al. (2017) and inf-iPSRL algorithm with $T_{k}=k$ is a stopping
criteria based on visitation count of all state-action pairs. Our result here
shows that the Bayesian regret is still $\tilde{O}(\sqrt{T})$ if one removes
the visitation count based stopping criteria in the TSDE algorithm.

When $\varepsilon$ is small, one can obtain a better regret bound for large
$T$ by designing episode lengths accordingly.

######  Corollary 3.4.

Let $\hat{\varepsilon}\geq\varepsilon$. Consider the episode schedule
$T_{k}=\lceil\hat{\varepsilon}k\rceil$. Then,

$\mathfrak{BR}_{T}(\phi^{\mathrm{iPSRL}})\leq
3\bar{v}+\tilde{O}(\bar{v}SA\sqrt{\hat{\varepsilon}T}).$ (18)

To better interpret the dependence of the regret on the prior distribution, we
note that the initial mismatch probability can be bounded through the
estimation error of the optimal policy given the offline data.

######  Lemma 3.5.

Let $\hat{\pi}^{*}$ be any estimator of $\pi^{*}$ constructed from
$\mathcal{D}_{0}$, then $\mathbb{P}(\tilde{\pi}^{1}\neq\pi^{*})\leq
2\mathbb{P}(\hat{\pi}^{*}\neq\pi^{*})$.

###### Proof.

If $\tilde{\pi}^{1}\neq\pi^{*}$, then either
$\hat{\pi}^{*}\neq\tilde{\pi}^{1}$ or $\hat{\pi}^{*}\neq\pi^{*}$ must be true.
Conditioning on $\mathcal{D}_{0}$, $\tilde{\pi}^{1}$ is identically
distributed as $\pi^{*}$ while $\hat{\pi}^{*}$ is deterministic, therefore

$\displaystyle\mathbb{P}(\tilde{\pi}^{1}\neq\pi^{*})\leq\mathbb{P}(\hat{\pi}^{*}\neq\tilde{\pi}^{1})+\mathbb{P}(\hat{\pi}^{*}\neq\pi^{*})=2\mathbb{P}(\hat{\pi}^{*}\neq\pi^{*})$

∎

###  3.2 Bounding the Estimation Error of Optimal Policy

We now provide a bound on the estimation error of the optimal policy given the
offline data. In addition to Assumption 2.1 and 2.2, we make the following
additional assumptions.

######  Assumption 3.6.

There exists a number $\Delta>0$ such that for all $\theta\in\varTheta$ and
all $s\in\mathcal{S}$, there exists $a^{*}\in\mathcal{A}$ such that
$q(s,a^{*};\theta)-q(s,a;\theta)\geq\Delta$ for all $a\neq a^{*}$.

######  Assumption 3.7.

There exists a number $\delta>0$ such that for all $\theta\in\varTheta$ and
all $s,s^{\prime}\in\mathcal{S}$, there exists a stationary Markov policy such
that

$\mathbb{P}_{\theta,\pi}(\exists 0<t\leq
S,s_{t}=s^{\prime}|s_{0}=s)\geq\delta.$ (19)

Here, $S$ is the number of states. Assumption 3.7 can be interpreted as
requiring all MDPs to be “uniformly communicating”: If we allow $\delta$ to be
dependent on $\theta$ in Assumption 3.7, then Assumption 3.7 is the same as
Assumption 2.1, i.e. all $\mathcal{M}(\theta)$ are communicating.

######  Lemma 3.8.

For a sufficiently large $\beta(s)=\beta$ and any $N\in\mathbb{N}$, there
exists an estimator $\hat{\pi}^{*}$ such that

$\mathbb{P}(\hat{\pi}^{*}\neq\pi^{*})\leq\varepsilon_{N}:=S(1+1.06N)\exp(-cN)$
(20)

where $c>0$ is a constant dependent on $(S,A,\bar{v},\Delta,\delta,\beta)$.

##  4 An Approximate Bayesian Algorithm

###  4.1 The Informed RLSVI Algorithm for average-reward MDPs

The inf-iPSRL algorithm introduced in the previous section assumes that the
posterior updates can be done exactly. In practice, the posterior update in
(9) is challenging due to the loss of conjugacy while using the Bayes rule.
Thus, we must find a computationally efficient way to do approximate posterior
updates (and obtain samples from it) to enable practical implementation.
Hence, we propose a novel approach based on Bayesian bootstrapping to obtain
approximate posterior samples. The key idea is to perturb the loss function
for the maximum a posterior (MAP) estimate and use the point estimate as a
surrogate for the exact posterior sample.

Note that in the ensuing, we regard $\beta$ as also unknown to the learning
agent (and $\lambda=\infty$ for simplicity). Thus, the learning agent must
form a belief over both $\theta$ and $\beta$ via a joint posterior
distribution conditioned on the offline dataset $\mathcal{D}_{0}$ and the
online data at time $t$, $\mathcal{H}_{t}$. We denote the prior pdf over
$\theta$ by $f(\cdot)$ and prior pdf over $\beta$ by $f_{2}(\cdot)$.

Consider the average-reward Bellman optimality eq.:

$\bar{r}^{*}+q^{*}(s,a;\theta)=r(s,a)+\mathbb{E}[\max_{b}q^{*}(s^{\prime},b;\theta)].$

For the sake of compact notation, we denote $q^{*}(s,a;\theta)$ as
$q^{\theta}_{t}(s,a)$ in this section. Now, consider the offline dataset,

$\mathcal{D}_{0}=\\{(s_{k},a_{k},\check{s}_{k},r_{k})_{k=0}^{N-1}\\}$

and let $\theta$ denote the parameterization of the relative q-value function.
We introduce the temporal difference error ${\mathcal{E}}_{k}$ (parameterized
by a given $q^{\theta}$),

$\mathcal{E}_{k}(q^{\theta}):=\left(r_{k}+\max_{b}q^{\theta}(\check{s}_{k},b)-q^{\theta}(s_{k},a_{k})-\bar{r}_{k}\right),$

and define recursively,

$\bar{r}_{k+1}:=(1-\eta_{k})\bar{r}_{k}+\eta_{k}r_{k},~{}~{}\bar{r}_{0}:=r_{0}.$

We use this to construct a parameterized offline dataset,

$\mathcal{D}_{0}(q^{\theta})=\\{(s_{k},a_{k},\check{s}_{k},\bar{r}_{k},\mathcal{E}_{k}(q^{\theta}))_{k=0}^{N-1}\\}.$

A parameterized online dataset at time $t$, $\mathcal{H}_{t}(q^{\theta})$ can
be similarly defined. To ease notation, we will regard the time $t$ during the
online phase as the $(N+t)$ time. Thus,

$\mathcal{H}_{t}(q^{\theta})=\\{(s_{k},a_{k},\check{s}_{k},\bar{r}_{k},\mathcal{E}_{k}(q^{\theta}))_{k=N}^{N+t}\\}\\},$

the online dataset available at time $t$.

Note that $q^{\theta}$ is to be regarded as a parameter. Now, at time $t$, we
would like to obtain a MAP estimate for $(\theta,\beta)$ by solving the
following:

$\begin{split}\textbf{MAP:}~{}~{}~{}\arg\max_{\theta,\beta}~{}&\log
P(\mathcal{H}_{t}(q^{\theta})|\mathcal{D}_{0}(q^{\theta}),\theta,\beta)+\log
P(\mathcal{D}_{0}(q^{\theta})|\theta,\beta)+\log f(\theta)+\log
f_{2}(\beta).\end{split}$ (21)

Denote a perturbed version of the $q^{\theta}$-parameterized offline dataset
by

$\tilde{\mathcal{D}}_{0}(q^{\theta})=\\{(s_{k},\tilde{a}_{k},\check{s}_{k},\bar{r}_{k},\tilde{\mathcal{E}}_{k})_{k=0}^{N-1}\\}$

where we add the following random perturbations: (i) actions have perturbation
$w_{l}^{h}\sim\exp(1)$, (ii) rewards have perturbations
$z_{k}\sim\mathcal{N}(0,\sigma^{2})$, and (iii) the prior
$\tilde{\theta}\sim\mathcal{N}(0,\Sigma_{0})$.

Note that the first and second terms involving $\mathcal{H}_{t}$ and
$\mathcal{D}_{0}$ in (21) are independent of $\beta$ when conditioned on the
actions. Thus, we have a sum of log-likelihood of TD error, transition and
action as follows:

$\begin{split}&\quad~{}\log
P(\tilde{\mathcal{D}}_{0}(q^{\theta})|q^{\theta})\\\
&=\sum_{k=0}^{N-1}\left(\log
P(\tilde{\mathcal{E}}_{k}|\check{s}_{k},a_{k},s_{k},\bar{r}_{k},q^{\theta})+\log
P(\check{s}_{k}|a_{k},s_{k},q^{\theta})+\log
P(a_{k}|s_{k},q^{\theta})\right)\\\ &\leq\sum_{k=0}^{N-1}\left(\log
P(\tilde{\mathcal{E}}_{k}|\check{s}_{k},a_{k},s_{k},\bar{r}_{k},q^{\theta})+\log\pi^{\beta}(a_{k}|s_{k},q^{\theta})\right).\end{split}$

By ignoring the log-likelihood of the transition term (akin to optimizing an
upper bound on the negative loss function), we are actually being optimistic.

For the terms in the upper bound above, under the random perturbations assumed
above, we have

$\begin{split}&\log
P(\tilde{\mathcal{E}}_{k}|\check{s}_{k},a_{k},s_{k},\bar{r}_{k},q^{\theta})=-\frac{1}{2}(r_{k}+z_{k}+\max_{b}q^{\theta}(\check{s}_{k},b)-q^{\theta}(s_{k},a_{k})-\bar{r}_{k})^{2}+\text{constant}\end{split}$

and

$\begin{split}\log\pi^{\beta}(a_{k}|s_{k},q^{\theta}_{t})&=w_{k}\left(\beta
q^{\theta}(s_{k},a_{k})-\log\sum_{b}\exp\left(\beta
q^{\theta}(s_{k},b)\right)\right).\end{split}$

Now, denote a perturbed version of the $q^{\theta}$-parameterized online
dataset by

$\tilde{\mathcal{H}}_{t}(q^{\theta})=\\{(s_{k},a_{k},\check{s}_{k},\bar{r}_{k},\tilde{\mathcal{E}}_{k})_{k=N:N+t}\\},$

and thus similar to before, we have

$\begin{split}&\quad~{}\log
P(\tilde{\mathcal{H}}_{t}(q^{\theta})|\tilde{\mathcal{D}}_{0}(q^{\theta}),q^{\theta})\\\
&=\sum_{k=N}^{N+t}\left(\log
P(\tilde{\mathcal{E}}_{k}(q^{\theta})|\check{s}_{k},a_{k},s_{k},\bar{r}_{k},q^{\theta})+\log
P(\check{s}_{k}|a_{k},s_{k},q^{\theta})\right),\\\ &\leq\sum_{k=N}^{N+t}\log
P(\tilde{\mathcal{E}}_{k}|\check{s}_{k},a_{k},s_{k},\bar{r}_{k},q^{\theta}),\\\
\end{split}$

where we again ignored the transition term to obtain an optimistic upper
bound.

Given the random perturbations above, we have

$\begin{split}&\quad~{}\log
P(\tilde{\mathcal{E}}_{k}(q^{\theta})|\check{s}_{k},a_{k},s_{k},\bar{r}_{k},q^{\theta})\\\
&=-\frac{1}{2}\left(r_{k}+z_{k}+\max_{b}q^{\theta}(\check{s}_{k},b)-q^{\theta}(s_{k},a_{k})-\bar{r}_{k}\right)^{2}+\text{constant}.\end{split}$

The prior over $\beta$, $f_{2}(\beta)$ is assumed to be an exponential pdf
$\lambda_{2}\exp(-\lambda_{2}\beta),\beta\geq 0$, while that over $\theta$ is
assumed Gaussian. Thus, putting it all together, we get the following
optimistic loss function (to minimize over $\theta$ and $\beta$),

$\begin{split}\tilde{\mathcal{L}}(\theta,\beta)&=\frac{1}{2\sigma^{2}}\sum_{k=0}^{N+T-1}\left(r_{k}+z_{k}+\max_{b}q^{\theta}(\check{s}_{k},b)-q^{\theta}(s_{k},a_{k})-\bar{r}_{k}\right)^{2}\\\
&-\sum_{t=0}^{T-1}w_{k}\left(\beta
q^{\theta}(s_{t},a_{t})-\log\sum_{b}\exp\left(\beta
q^{\theta}(s_{t},b)\right)\right)+\frac{1}{2}(\theta-\tilde{\theta})^{\top}\Sigma_{0}(\theta-\tilde{\theta})+\lambda_{2}\beta.\end{split}$
(22)

The above loss function is difficult to optimize in general due to the $\max$
operation, and the $Q$-value function in general having a nonlinear form.

######  Remark 4.1.

Note that the loss function in (22) can be hard to jointly optimize over
$\theta$ and $\beta$. In particular, estimates of $\beta$ can be quite noisy
when $\beta$ is large, and the near-optimal expert policy only covers the
state-action space partially. Thus, we consider other methods of estimating
$\beta$ that are more robust, which can then be plugged into the loss function
in (22). Specifically, we could simply look at the entropy of the empirical
distribution of the actions in the offline dataset. Suppose the empirical
distribution of $\\{\bar{a}_{0}^{l},\ldots\bar{a}_{k}\\}_{l=1}^{L}$ is
$\mu_{A}$. Then we use $c_{0}/\mathcal{H}(\mu_{A})$ as an estimation for
$\beta$, where $c_{0}>0$ is a hyperparameter. The intuition is that for
smaller $\beta$, the offline actions tend to be more uniform and thus the
entropy will be large. This is an unsupervised approach and agnostic to
specific offline data generation process.

######  Remark 4.2.

In the loss function in (22), the parameter $\theta$ appears inside the $\max$
operation. Thus, it can be quite difficult to optimize over $\beta$. Since the
loss function is typically optimized via an iterative algorithm such as a
gradient descent method, a simple and scalable solution that works well in
practice is to use the parameter estimate $\theta$ from the previous iteration
inside the $\max$ operation, and thus optimize over $\theta$ only in the other
terms.

###  4.2 inf-iRLSVI bridges Online RL and Imitation Learning

In the previous subsection, we derived inf-iRLSVI, a Bayesian-bootstrapped
algorithm. We now present interpretation of the algorithm as bridging online
RL (via commonality with the RLSVI algorithm (Osband et al., 2016) and
imitation learning, and hence a way for its generalization.

Consider the RLSVI algorithm for online reinforcement learning as introduced
in Osband et al. (2019). It draws its inspiration from the posterior sampling
principle for online learning, and has excellent cumulative regret
performance. The RLSVI algorithm, that uses all of the data available at the
end of episode $t$, including any offline dataset involves minimizing the
corresponding loss function at each time step:

$\begin{split}\tilde{\mathcal{L}}_{\text{RLSVI}}(\theta)&=\frac{1}{2\sigma^{2}}\sum_{k=1}^{L+t}\sum_{h=0}^{H-1}\left(r_{k}+\max_{b}Q^{\theta}_{t+1}(\check{s}_{k},b)-q^{\theta}_{t}(s_{k},a_{k})\right)^{2}\\\
&+\frac{1}{2}({\theta_{0:H}}-{\tilde{\theta}_{0:H}})^{\top}\Sigma_{0}({\theta_{0:H}}-{\tilde{\theta}_{0:H}}).\end{split}$

Now, let us consider an imitation learning setting. Let
$\tau_{l}=(s_{k},a_{k},\check{s}_{k})_{h=0}^{H-1}$ be the trajectory of the
$l$th episode. Let $\hat{\pi}_{t}(a|s)$ denote the empirical estimate of
probability of taking action $a$ in state $s$ at time $h$, i.e., an empirical
estimate of the expert’s randomized policy. Let $p(\tau)$ denote the
probability of observing the trajectory under the policy $\hat{\pi}$.

Let $\pi_{t}^{\beta,\theta}(\cdot|s)$ denote the parametric representation of
the policy used by the expert. And let $p^{\beta,\theta}(\tau)$ denote the
probability of observing the trajectory $\tau$ under the policy
${\pi}^{\beta,\theta}$. Then, the loss function corresponding to the KL
divergence between $\Pi_{l=1}^{L}p(\tau_{l})$ and
$\Pi_{l=1}^{L}p^{\beta,\theta}(\tau_{l})$ is given by

$\displaystyle\tilde{\mathcal{L}}_{\text{IL}}(\beta,\theta)$
$\displaystyle=D_{KL}\left(\Pi_{l=1}^{L}p(\tau_{l})||\Pi_{l=1}^{L}p^{\beta,\theta}(\tau_{l})\right)=\int\Pi_{l=1}^{L}p(\tau_{l})\log\frac{\Pi_{l=1}^{L}p(\tau_{l})}{\Pi_{l=1}^{L}p^{\beta}(\tau_{l})}$
(23) $\displaystyle=\sum_{l=1}^{L}\int
p(\tau_{l})\log\frac{p(\tau_{l})}{p^{\beta,\theta}(\tau_{l})},=\sum_{l=1}^{L}\sum_{h=0}^{H-1}\log\frac{\hat{\pi}_{t}(a_{k}|s_{k})}{\pi^{\beta,\theta}_{t}(a_{k}|s_{k})}$
(24)
$\displaystyle=\sum_{l=1}^{L}\sum_{h=0}^{H-1}[\log\hat{\pi}_{t}(a_{k}|s_{k})-\log\pi_{t}^{\beta,\theta}(a_{k}|s_{k})]$
(25) $\displaystyle=-\sum_{l=1}^{L}\sum_{h=0}^{H-1}\left(\beta
q^{\theta}_{t}(s_{k},a_{k})-\log\sum_{b}\exp\left(\beta
q^{\theta}_{t}(s_{k},b)\right)\right)+\text{constant}.$ (26)

######  Remark 4.3.

(i) The loss function $\tilde{\mathcal{L}}_{\text{IL}}(\beta,\theta)$ is the
same as the second (action-likelihood) term in (22) while the loss function
$\tilde{\mathcal{L}}_{\text{RLSVI}}(\theta)$ is the same as the first and
third terms there (except for perturbation) and minus the $\lambda_{2}\beta$
term that corresponds to the prior over $\beta$. (ii) Note that while we used
the more common KL divergence for the imitation learning loss function, use of
log loss would yield the same outcome.

Thus, the inf-iRLSVI loss function can be viewed as

$\tilde{\mathcal{L}}(\beta,\theta)=\tilde{\mathcal{L}}_{\text{RLSVI}}(\theta)+\tilde{\mathcal{L}}_{\text{IL}}(\beta,\theta)+\lambda_{2}\beta,$
(27)

thus establishing that the proposed algorithm may be viewed as bridging Online
RL with Imitation Learning. Note that the last term corresponds to the prior
over $\beta$. If $\beta$ is known (or uniform), it will not show up in the
loss function above.

The above also suggests a possible way to generalize and obtain other online
learning algorithms that can bootstrap by use of offline datasets. Namely, at
each step, they can optimize a general loss function of the following kind:

$\tilde{\mathcal{L}}_{\alpha}(\beta,\theta)=\alpha\tilde{\mathcal{L}}_{\text{ORL}}(\theta)+(1-\alpha)\tilde{\mathcal{L}}_{\text{IL}}(\beta,\theta)+\lambda_{2}\beta,$
(28)

where $\tilde{\mathcal{L}}_{\text{ORL}}$ is a loss function for an Online RL
algorithm, $\tilde{\mathcal{L}}_{\text{IL}}$ is a loss function for some
Imitation Learning algorithm, and factor $\alpha\in[0,1]$ provides a way to
tune between emphasizing the offline imitation learning and the online
reinforcement learning.

##  5 Conclusions

In this paper, we have introduced an ideal Bayesian online reinforcement
learning algorithm, inf-iPSRL, that naturally uses any offline data available
for pre-training to boot-strap online learning. The algorithm is agnostic to
whether we have a small or large amount of data, or a small or large window
for online learning. It is also useful in the special case of no offline data
but not for the ‘pure’ offline RL setting when there is no online learning
phase. A key aspect of the proposed algorithm is that unlike past PSRL
algorithms, our algorithm takes the episode length as an input. Our analysis
then shows what type of episodic schedules result in near-optimal regret. The
analysis involves several novel elements and depends on prior-dependent regret
analysis, which is known to be quite challenging and itself a novelty.

We then presented an approximate Bayesian online learning algorithm, inf-
iRLSVI that can be seen as naturally bridging online reinforcement learning
and imitation learning. In prior work (Osband et al., 2019), such algorithms
are well-known to be computationally practical in problems that need deep
exploration.

We note that while it should be possible to design non-Bayesian algorithms for
the problem we address in this paper, and analyze its frequentist regret, it
is much less natural to incorporate information derived from offline datasets
in such algorithms, and hence our choice to focus on Bayesian algorithms with
a guarantee on their Bayesian regret.

A number of future directions are possible: The performance of the inf-iRLSVI
algorithm can be empirically and theoretically be analyzed. Theoretical
analysis is expected to be a combination of analysis of RLSVI in Osband et al.
(2019) along with novel elements we have introduced in the analysis of the
inf-iPSRL algorithm in this paper. This is left as a useful exercise for
aspiring student researchers. Yet another future direction is design of
universal RL algorithms which can specialize to Online RL, or be seen as
Offline RL or Imitation Learning algorithms in suitable settings, or anything
in between. Currently, we have to design RL algorithms separately for the
three settings.

## References

  * Agarwal and Zhang (2022) A. Agarwal and T. Zhang.  Model-based RL with optimistic posterior sampling: Structural conditions and sample complexity.  _arXiv preprint arXiv:2206.07659_ , 2022.
  * Argenson and Dulac-Arnold (2020) A. Argenson and G. Dulac-Arnold.  Model-based offline planning.  _arXiv preprint arXiv:2008.05556_ , 2020.
  * Auer et al. (2008) P. Auer, T. Jaksch, and R. Ortner.  Near-optimal regret bounds for reinforcement learning.  _Advances in neural information processing systems_ , 21, 2008.
  * Ball et al. (2023) P. J. Ball, L. Smith, I. Kostrikov, and S. Levine.  Efficient online reinforcement learning with offline data.  _arXiv preprint arXiv:2302.02948_ , 2023.
  * Beliaev et al. (2022) M. Beliaev, A. Shih, S. Ermon, D. Sadigh, and R. Pedarsani.  Imitation learning by estimating expertise of demonstrators.  _Proceedings of the 39th International Conference on Machine Learning_ , 162:1732–1748, 2022.
  * Bertsekas (1995) D. Bertsekas.  _Dynamic programming and optimal control: Volume II_ , volume 2.  Athena scientific, 1995.
  * Brown et al. (2020) T. Brown, B. Mann, N. Ryder, M. Subbiah, J. D. Kaplan, P. Dhariwal, A. Neelakantan, P. Shyam, G. Sastry, A. Askell, et al.  Language models are few-shot learners.  _Advances in neural information processing systems_ , 33:1877–1901, 2020.
  * Ernst et al. (2005) D. Ernst, P. Geurts, and L. Wehenkel.  Tree-based batch mode reinforcement learning.  _Journal of Machine Learning Research_ , 6, 2005.
  * Fang et al. (2022) K. Fang, P. Yin, A. Nair, and S. Levine.  Planning to practice: Efficient online fine-tuning by composing goals in latent space.  _arXiv preprint arXiv:2205.08129_ , 2022.
  * Hansen et al. (2022) N. Hansen, Y. Lin, H. Su, X. Wang, V. Kumar, and A. Rajeswaran.  MoDem: Accelerating visual model-based reinforcement learning with demonstrations.  _arXiv preprint arXiv:2212.05698_ , 2022.
  * Hao et al. (2023) B. Hao, R. Jain, T. Lattimore, B. Van Roy, and Z. Wen.  Leveraging demonstrations to improve online learning: Quality matters.  _arXiv preprint arXiv:2302.03319_ , 2023.
  * Hester et al. (2018) T. Hester, M. Vecerik, O. Pietquin, M. Lanctot, T. Schaul, B. Piot, D. Horgan, J. Quan, A. Sendonaris, I. Osband, et al.  Deep Q-learning from demonstrations.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32(1), 2018.
  * Hoffmann et al. (2022) J. Hoffmann, S. Borgeaud, A. Mensch, E. Buchatskaya, T. Cai, E. Rutherford, D. d. L. Casas, L. A. Hendricks, J. Welbl, A. Clark, et al.  Training compute-optimal large language models.  _arXiv preprint arXiv:2203.15556_ , 2022.
  * Jin et al. (2021) Y. Jin, Z. Yang, and Z. Wang.  Is pessimism provably efficient for offline RL?  In _International Conference on Machine Learning_ , pages 5084–5096. PMLR, 2021.
  * Kostrikov et al. (2021) I. Kostrikov, A. Nair, and S. Levine.  Offline reinforcement learning with implicit Q-learning.  _arXiv preprint arXiv:2110.06169_ , 2021.
  * Kumar et al. (2020) A. Kumar, A. Zhou, G. Tucker, and S. Levine.  Conservative Q-learning for offline reinforcement learning.  _Advances in Neural Information Processing Systems_ , 33:1179–1191, 2020.
  * Kumar et al. (2022) A. Kumar, J. Hong, A. Singh, and S. Levine.  When should we prefer offline reinforcement learning over behavioral cloning?  _arXiv preprint arXiv:2204.05618_ , 2022.
  * Lee et al. (2022) S. Lee, Y. Seo, K. Lee, P. Abbeel, and J. Shin.  Offline-to-online reinforcement learning via balanced replay and pessimistic Q-ensemble.  In _Conference on Robot Learning_ , pages 1702–1712. PMLR, 2022.
  * Levin and Peres (2017) D. A. Levin and Y. Peres.  _Markov chains and mixing times_ , volume 107.  American Mathematical Soc., 2017.
  * Levine et al. (2020) S. Levine, A. Kumar, G. Tucker, and J. Fu.  Offline reinforcement learning: Tutorial, review, and perspectives on open problems.  _arXiv preprint arXiv:2005.01643_ , 2020.
  * Nair et al. (2020) A. Nair, A. Gupta, M. Dalal, and S. Levine.  AWAC: Accelerating online reinforcement learning with offline datasets.  _arXiv preprint arXiv:2006.09359_ , 2020.
  * Osband et al. (2013) I. Osband, D. Russo, and B. Van Roy.  (More) efficient reinforcement learning via posterior sampling.  _Advances in Neural Information Processing Systems_ , 26, 2013.
  * Osband et al. (2016) I. Osband, C. Blundell, A. Pritzel, and B. Van Roy.  Deep exploration via bootstrapped dqn.  _Advances in neural information processing systems_ , 29, 2016.
  * Osband et al. (2019) I. Osband, B. Van Roy, D. J. Russo, Z. Wen, et al.  Deep exploration via randomized value functions.  _J. Mach. Learn. Res._ , 20(124):1–62, 2019.
  * Ouyang et al. (2017) Y. Ouyang, M. Gagrani, A. Nayyar, and R. Jain.  Learning unknown markov decision processes: A thompson sampling approach.  _Advances in neural information processing systems_ , 30, 2017.
  * Rashidinejad et al. (2021) P. Rashidinejad, B. Zhu, C. Ma, J. Jiao, and S. Russell.  Bridging offline reinforcement learning and imitation learning: A tale of pessimism.  _Advances in Neural Information Processing Systems_ , 34:11702–11716, 2021.
  * Russo and Van Roy (2016) D. Russo and B. Van Roy.  An information-theoretic analysis of thompson sampling.  _The Journal of Machine Learning Research_ , 17(1):2442–2471, 2016.
  * Russo et al. (2018) D. J. Russo, B. Van Roy, A. Kazerouni, I. Osband, Z. Wen, et al.  A tutorial on thompson sampling.  _Foundations and Trends® in Machine Learning_ , 11(1):1–96, 2018.
  * Schaal (1996) S. Schaal.  Learning from demonstration.  _Advances in neural information processing systems_ , 9, 1996.
  * Schrittwieser et al. (2021) J. Schrittwieser, T. Hubert, A. Mandhane, M. Barekatain, I. Antonoglou, and D. Silver.  Online and offline reinforcement learning by planning with a learned model.  _Advances in Neural Information Processing Systems_ , 34:27580–27591, 2021.
  * Song et al. (2022) Y. Song, Y. Zhou, A. Sekhari, J. A. Bagnell, A. Krishnamurthy, and W. Sun.  Hybrid RL: Using both offline and online data can make RL efficient.  _arXiv preprint arXiv:2210.06718_ , 2022.
  * Thoppilan et al. (2022) R. Thoppilan, D. De Freitas, J. Hall, N. Shazeer, A. Kulshreshtha, H.-T. Cheng, A. Jin, T. Bos, L. Baker, Y. Du, et al.  Lamda: Language models for dialog applications.  _arXiv preprint arXiv:2201.08239_ , 2022.
  * Uehara and Sun (2021) M. Uehara and W. Sun.  Pessimistic model-based offline reinforcement learning under partial coverage.  _arXiv preprint arXiv:2107.06226_ , 2021.
  * Vecerik et al. (2017) M. Vecerik, T. Hester, J. Scholz, F. Wang, O. Pietquin, B. Piot, N. Heess, T. Rothörl, T. Lampe, and M. Riedmiller.  Leveraging demonstrations for deep reinforcement learning on robotics problems with sparse rewards.  _arXiv preprint arXiv:1707.08817_ , 2017.
  * Wagenmaker and Pacchiano (2022) A. Wagenmaker and A. Pacchiano.  Leveraging offline data in online reinforcement learning.  _arXiv preprint arXiv:2211.04974_ , 2022.
  * Wan et al. (2022) R. Wan, B. Kveton, and R. Song.  Safe exploration for efficient policy evaluation and comparison.  _arXiv preprint arXiv:2202.13234_ , 2022.
  * Weissman et al. (2003) T. Weissman, E. Ordentlich, G. Seroussi, S. Verdu, and M. J. Weinberger.  Inequalities for the L1 deviation of the empirical distribution.  _Hewlett-Packard Labs, Tech. Rep_ , 2003.
  * Xie et al. (2021a) T. Xie, C.-A. Cheng, N. Jiang, P. Mineiro, and A. Agarwal.  Bellman-consistent pessimism for offline reinforcement learning.  _Advances in neural information processing systems_ , 34:6683–6694, 2021a.
  * Xie et al. (2021b) T. Xie, N. Jiang, H. Wang, C. Xiong, and Y. Bai.  Policy finetuning: Bridging sample-efficient offline and online reinforcement learning.  _Advances in neural information processing systems_ , 34:27395–27407, 2021b.

##  Appendix A Proof of Theorem 3.1

Recall that $t_{k}=\sum_{l=1}^{k-1}T_{k}$ is the starting time of learning
episode $k$. Let
$\tilde{\mathcal{D}}_{k}:=\mathcal{D}_{0}\cup\\{(s_{0},a_{0},\cdots,s_{t_{k}-1},a_{t_{k}-1},s_{t_{k}})\\}$
denote the offline and online data the learning agent used to form a posterior
to sample the environment for the $k$-th learning episode. For simplicity of
notation, let
$\mathbb{P}_{k}(\cdot)=\mathbb{P}(\cdot|\tilde{\mathcal{D}}_{k})$ and
$\mathbb{E}_{k}[\cdot]=\mathbb{E}[\cdot|\tilde{\mathcal{D}}_{k}]$. Also define
$\tilde{\mathbb{E}}_{k}^{*}[\cdot]=\mathbb{E}[\cdot|\tilde{\mathcal{D}}_{k},\theta^{*},\tilde{\theta}^{k}]$.

For convenience, we fix $T$ and write $K=K_{T}$. For the sake of this proof,
if the last episode goes beyond time $T-1$, we “cut off” the episode after
time $T-1$ and define $T_{K}=T-1-t_{K}$ and $t_{K+1}=T$.

Without loss of generality, by choosing an appropriate reference state
$\hat{s}$ in (3) we can assume that $v(s;\theta)\in[0,\bar{v}]$.

We will start with the following lemma which bounds all the mismatch
probabilities by the initial mismatch probability.

######  Lemma A.1.

$\mathbb{P}(\tilde{\pi}^{k}\neq\pi^{*})\leq\mathbb{P}(\tilde{\pi}^{1}\neq\pi^{*})$
for all $k\geq 1$.

###### Proof.

Define $f(x)=x(1-x)$. We have

$\displaystyle\mathbb{P}(\tilde{\pi}^{k}\neq\pi^{*})$
$\displaystyle=\mathbb{E}[\mathbb{P}_{k}(\tilde{\pi}^{k}\neq\pi^{*})]=\mathbb{E}\left[\sum_{\pi\in\varPi}\mathbb{P}_{k}(\tilde{\pi}^{k}=\pi,\pi^{*}\neq\pi)\right]$
(29)
$\displaystyle=\mathbb{E}\left[\sum_{\pi\in\varPi}f(\mathbb{P}_{k}(\pi^{*}=\pi))\right]$
(30)
$\displaystyle=\mathbb{E}\left[\sum_{\pi\in\varPi}\mathbb{E}_{1}[f(\mathbb{P}_{k}(\pi^{*}=\pi))]\right]\leq\mathbb{E}\left[\sum_{\pi\in\varPi}f(\mathbb{E}_{1}[\mathbb{P}_{k}(\pi^{*}=\pi)])\right]$
(31)
$\displaystyle=\mathbb{E}\left[\sum_{\pi\in\varPi}f(\mathbb{P}_{1}(\pi^{*}=\pi))\right]=\mathbb{E}\left[\sum_{\pi\in\varPi}\mathbb{P}_{1}(\tilde{\pi}^{1}=\pi,\pi^{*}\neq\pi)\right]$
(32) $\displaystyle=\mathbb{P}(\tilde{\pi}^{1}\neq\pi^{*})$ (33)

where the inequality is due to Jensen’s Inequality and the fact that $f$ is a
concave function. ∎

Define the episode $k$ regret $Z_{k}$ as

$Z_{k}=T_{k}\bar{r}^{*}(\theta^{*})-\sum_{t=t_{k}}^{t_{k+1}-1}r(s_{t},a_{t}).$
(34)

Then we can write
$\mathfrak{BR}_{T}(\phi^{\mathrm{iPSRL}})=\sum_{k=1}^{K}\mathbb{E}[Z_{k}]$.

If the event $\\{\tilde{\pi}^{k}=\pi^{*}\\}$ is true, then for $t_{k}\leq
t<t_{k+1}$, we have $a_{t}=\pi^{*}(s_{t})$ and
$v(s_{t};\theta^{*})+\bar{r}^{*}(\theta^{*})=r(s_{t},a_{t})+\sum_{s^{\prime}\in\mathcal{S}}\theta^{*}(s^{\prime}|s_{t},a_{t})v(s^{\prime};\theta^{*})$
due to the assumption on the planning oracle MDPSolve. Therefore,

$Z_{k}\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*}\\}}=\sum_{t=t_{k}}^{t_{k+1}-1}\left(\sum_{s^{\prime}\in\mathcal{S}}\theta^{*}(s^{\prime}|s_{t},a_{t})v(s^{\prime};\theta^{*})-v(s_{t};\theta^{*})\right)\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*}\\}}$
(35)

Furthermore, using the fact that
$\tilde{\mathbb{E}}_{k}^{*}[v(s_{t+1};\theta^{*})|s_{t},a_{t}]=\sum_{s^{\prime}\in\mathcal{S}}\theta^{*}(s^{\prime}|s_{t},a_{t})v(s^{\prime};\theta^{*})$,
we have

$\displaystyle\quad~{}\tilde{\mathbb{E}}_{k}^{*}[Z_{k}\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*}\\}}]$
(36)
$\displaystyle=\tilde{\mathbb{E}}_{k}^{*}\left[\sum_{t=t_{k}}^{t_{k+1}-1}\left(\sum_{s^{\prime}\in\mathcal{S}}\theta^{*}(s^{\prime}|s_{t},a_{t})v(s^{\prime};\theta^{*})-v(s_{t};\theta^{*})\right)\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*}\\}}\right]$
(37)
$\displaystyle=\tilde{\mathbb{E}}_{k}^{*}\left[\sum_{t=t_{k}}^{t_{k+1}-1}\left(\sum_{s^{\prime}\in\mathcal{S}}\theta^{*}(s^{\prime}|s_{t},a_{t})v(s^{\prime};\theta^{*})-v(s_{t};\theta^{*})\right)\right]\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*}\\}}$
(38)
$\displaystyle=\tilde{\mathbb{E}}_{k}^{*}\left[\sum_{t=t_{k}}^{t_{k+1}-1}\left(v(s_{t+1};\theta^{*})-v(s_{t};\theta^{*})\right)\right]\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*}\\}}$
(39)
$\displaystyle=\tilde{\mathbb{E}}_{k}^{*}\left[v(s_{t_{k+1}};\theta^{*})-v(s_{t_{k}};\theta^{*})\right]\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*}\\}}$
(40)
$\displaystyle=\tilde{\mathbb{E}}_{k}^{*}\left[\left[v(s_{t_{k+1}};\theta^{*})-v(s_{t_{k}};\theta^{*})\right]\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*}\\}}\right]$
(41)

Taking the sum over all episodes $k$, we have

$\displaystyle\quad~{}\sum_{k=1}^{K}\mathbb{E}\left[Z_{k}\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*}\\}}\right]$
(42)
$\displaystyle=\mathbb{E}\left[\sum_{k=1}^{K}[v(s_{t_{k+1}};\theta^{*})-v(s_{t_{k}};\theta^{*})]\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*}\\}}\right]$
(43)
$\displaystyle=\mathbb{E}\left[v(s_{t_{K+1}};\theta^{*})\bm{1}_{\\{\tilde{\pi}^{K}=\pi^{*}\\}}-v(s_{t_{1}};\theta^{*})\bm{1}_{\\{\tilde{\pi}^{1}=\pi^{*}\\}}\right]$
(44)
$\displaystyle\quad+\mathbb{E}\left[\sum_{k=1}^{K-1}v(s_{t_{k+1}};\theta^{*})\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*},\tilde{\pi}^{k+1}\neq\pi^{*}\\}}-\sum_{k=2}^{K}v(s_{t_{k}};\theta^{*})\bm{1}_{\\{\tilde{\pi}^{k-1}\neq\pi^{*},\tilde{\pi}^{k}=\pi^{*}\\}}\right]$
(45)
$\displaystyle\leq\bar{v}+\bar{v}\mathbb{E}\left[\sum_{k=1}^{K-1}\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*},\tilde{\pi}^{k+1}\neq\pi^{*}\\}}\right]\leq\bar{v}+\bar{v}\sum_{k=1}^{K-1}\mathbb{P}(\tilde{\pi}^{k+1}\neq\pi^{*})$
(46) $\displaystyle\leq\bar{v}+\bar{v}(K-1)\varepsilon$ (47)

where we used Lemma A.1 in the last inequality.

In general, for $t_{k}\leq t<t_{k+1}$, since $a_{t}=\tilde{\pi}^{k}(s_{t})$,
we have
$v(s_{t};\tilde{\theta}^{k})+\bar{r}^{*}(\tilde{\theta}^{k})=r(s_{t},a_{t})+\sum_{s^{\prime}\in\mathcal{S}}\tilde{\theta}^{k}(s^{\prime}|s_{t},a_{t})v(s^{\prime};\tilde{\theta}^{k})$
due to the assumption on the planning oracle MDPSolve. Therefore,

$\displaystyle Z_{k}$
$\displaystyle=T_{k}\bar{r}^{*}(\theta^{*})-\sum_{t=t_{k}}^{t_{k+1}-1}\left(\bar{r}^{*}(\tilde{\theta}^{k})+v(s_{t};\tilde{\theta}^{k})-\sum_{s^{\prime}\in\mathcal{S}}\tilde{\theta}^{k}(s^{\prime}|s_{t},a_{t})v(s^{\prime};\tilde{\theta}^{k})\right)$
(48)
$\displaystyle=\underbrace{T_{k}\left[\bar{r}^{*}(\theta^{*})-\bar{r}^{*}(\tilde{\theta}^{k})\right]}_{Z_{k,0}}+\underbrace{\sum_{t=t_{k}}^{t_{k+1}-1}\left(\sum_{s^{\prime}\in\mathcal{S}}\theta^{*}(s^{\prime}|s_{t},a_{t})v(s^{\prime};\tilde{\theta}^{k})-v(s_{t};\tilde{\theta}^{k})\right)}_{Z_{k,1}}$
(49)
$\displaystyle\quad+\underbrace{\sum_{t=t_{k}}^{t_{k+1}-1}\sum_{s^{\prime}\in\mathcal{S}}[\tilde{\theta}^{k}(s^{\prime}|s_{t},a_{t})-\theta^{*}(s^{\prime}|s_{t},a_{t})]v(s^{\prime};\tilde{\theta}^{k})}_{Z_{k,2}}.$
(50)

We will analyze the three terms in (50) separately. First, we have

$\mathbb{E}_{k}[Z_{k,0}\bm{1}_{\\{\tilde{\pi}^{k}\neq\pi^{*}\\}}]=T_{k}\left(\mathbb{E}_{k}[\bar{r}^{*}(\theta^{*})\bm{1}_{\\{\tilde{\pi}^{k}\neq\pi^{*}\\}}]-\mathbb{E}_{k}[\bar{r}^{*}(\tilde{\theta}^{k})\bm{1}_{\\{\pi^{*}\neq\tilde{\pi}^{k}\\}}]\right)=0$
(51)

since $\theta^{*}$ and $\tilde{\theta}^{k}$ are i.i.d. given
$\tilde{\mathcal{D}}_{k}$. Following similar steps as (41) we have

$\tilde{\mathbb{E}}_{k}^{*}[Z_{k,1}\bm{1}_{\\{\tilde{\pi}^{k}\neq\pi^{*}\\}}]=\tilde{\mathbb{E}}_{k}^{*}\left[v(s_{t_{k+1}};\tilde{\theta}^{k})-v(s_{t_{k}};\tilde{\theta}^{k})\right]\bm{1}_{\\{\tilde{\pi}^{k}\neq\pi^{*}\\}}\leq\bar{v}\bm{1}_{\\{\tilde{\pi}^{k}\neq\pi^{*}\\}}$
(52)

and hence

$\mathbb{E}[Z_{k,1}\bm{1}_{\\{\tilde{\pi}^{k}\neq\pi^{*}\\}}]\leq\bar{v}\mathbb{P}(\tilde{\pi}^{k}\neq\pi^{*})\leq\bar{v}\varepsilon.$
(53)

where we used Lemma A.1. Combining (47)(50)(51)(53), we have

$\displaystyle\sum_{k=1}^{K}\mathbb{E}[Z_{k}]$
$\displaystyle=\sum_{k=1}^{K}\mathbb{E}[Z_{k}\bm{1}_{\\{\tilde{\pi}^{k}=\pi^{*}\\}}]+\sum_{k=1}^{K}\mathbb{E}[(Z_{k,0}+Z_{k,1}+Z_{k,2})\bm{1}_{\\{\tilde{\pi}^{k}\neq\pi^{*}\\}}]$
(54)
$\displaystyle\leq\bar{v}+\bar{v}(K-1)\varepsilon+\sum_{k=1}^{K}\mathbb{E}[Z_{k,1}\bm{1}_{\\{\tilde{\pi}^{k}\neq\pi^{*}\\}}]+\sum_{k=1}^{K}\mathbb{E}[Z_{k,2}\bm{1}_{\\{\tilde{\pi}^{k}\neq\pi^{*}\\}}]$
(55)
$\displaystyle\leq\bar{v}+\bar{v}(2K-1)\varepsilon+\sum_{k=1}^{K}\mathbb{E}[Z_{k,2}\bm{1}_{\\{\tilde{\pi}^{k}\neq\pi^{*}\\}}]$
(56)

Now we bound the summation term in (56). For convenience, define
$I_{k}=\bm{1}_{\\{\tilde{\pi}^{k}\neq\pi^{*}\\}}$. First, since
$v(s;\theta)\in[0,\bar{v}]$, we have

$\displaystyle Z_{k,2}$
$\displaystyle\leq\bar{v}\sum_{t=t_{k}}^{t_{k+1}-1}\sum_{s^{\prime}\in\mathcal{S}}(\tilde{\theta}^{k}(s^{\prime}|s_{t},a_{t})-\theta^{*}(s^{\prime}|s_{t},a_{t}))_{+}$
(57)
$\displaystyle=\bar{v}\sum_{t=t_{k}}^{t_{k+1}-1}\frac{1}{2}\|\tilde{\theta}^{k}(\cdot|s_{t},a_{t})-\theta^{*}(\cdot|s_{t},a_{t})\|_{1}$
(58)

Following Osband et al. (2013); Ouyang et al. (2017), define
$N_{t}(s,a):=\sum_{\tau=0}^{t-1}\bm{1}_{\\{(s_{\tau},a_{\tau})=(s,a)\\}}$ to
be the number of occurrences of the state-action pair $(s,a)$ from time $0$ to
time $t-1$.

Claim: For any $k,t$ such that $t_{k}\leq t<t_{k+1}$ and any $\delta\in(0,1)$,

$\displaystyle\quad~{}\mathbb{E}\left[\frac{1}{2}\|\tilde{\theta}^{k}(\cdot|s_{t},a_{t})-\theta^{*}(\cdot|s_{t},a_{t})\|_{1}\cdot
I_{k}\right]$ (59)
$\displaystyle\leq\mathbb{E}\left[\min\left\\{\sqrt{\dfrac{(2\log
2)S+2\log(1/\delta)}{N_{t_{k}}(s_{t},a_{t})}},2\right\\}\cdot
I_{k}\right]+2t_{k}SA\delta$ (60)

For $t_{k}\leq t<t_{k+1}$, define the event

$\mathcal{E}_{t}=\\{N_{t}(s_{t},a_{t})>2N_{t_{k}}(s_{t},a_{t})\\}$ (61)

We can decompose the first term in (60) by

$\displaystyle\quad~{}\min\left\\{\sqrt{\dfrac{(2\log
2)S+2\log(1/\delta)}{N_{t_{k}}(s_{t},a_{t})}},2\right\\}I_{k}$ (62)
$\displaystyle\leq\min\left\\{\sqrt{\dfrac{(2\log
2)S+2\log(1/\delta)}{N_{t_{k}}(s_{t},a_{t})}},2\right\\}I_{k}\bm{1}_{\mathcal{E}_{t}^{c}}+2I_{k}\bm{1}_{\mathcal{E}_{t}}$
(63) $\displaystyle\leq\min\left\\{\sqrt{\dfrac{(4\log
2)S+4\log(1/\delta)}{N_{t}(s_{t},a_{t})}},2\right\\}I_{k}\bm{1}_{\mathcal{E}_{t}^{c}}+2I_{k}\bm{1}_{\mathcal{E}_{t}}$
(64) $\displaystyle\leq\underbrace{\sqrt{\dfrac{(4\log
2)S+4\log(1/\delta)}{\max\\{N_{t}(s_{t},a_{t}),1\\}}}}_{\beta_{t}}I_{k}+2I_{k}\bm{1}_{\mathcal{E}_{t}}$
(65)

Combining (58)(60)(65) and set $\delta=(SAKT)^{-1}$, we have

$\displaystyle\quad~{}\sum_{k=1}^{K}\mathbb{E}[Z_{k,2}I_{k}]$ (66)
$\displaystyle\leq\bar{v}\mathbb{E}\left[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}\beta_{t}I_{k}\right]+2\bar{v}\mathbb{E}\left[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}I_{k}\bm{1}_{\mathcal{E}_{t}}\right]+2\bar{v}SA\delta\sum_{k=1}^{K}t_{k}$
(67)
$\displaystyle\leq\bar{v}\mathbb{E}\left[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}\beta_{t}I_{k}\right]+2\bar{v}\mathbb{E}\left[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}I_{k}\bm{1}_{\mathcal{E}_{t}}\right]+2\bar{v}$
(68)

By Cauchy-Schwatz inequality, we have

$\displaystyle\quad~{}\mathbb{E}\left[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}\beta_{t}I_{k}\right]$
(69)
$\displaystyle\leq\sqrt{\mathbb{E}\left[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}I_{k}^{2}\right]}\sqrt{\mathbb{E}\left[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}\beta_{t}^{2}\right]}$
(70)
$\displaystyle=\sqrt{\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}\mathbb{E}[I_{k}]}\sqrt{\mathbb{E}\left[\sum_{t=0}^{T-1}\beta_{t}^{2}\right]}\stackrel{{\scriptstyle(a)}}{{\leq}}\sqrt{\varepsilon
T}\sqrt{\mathbb{E}\left[\sum_{t=0}^{T-1}\beta_{t}^{2}\right]}$ (71)
$\displaystyle=\sqrt{\varepsilon T[(4\log
2)S+4\log(SAKT)]\mathbb{E}\left[\sum_{t=0}^{T-1}\left(\max\\{N_{t}(s_{t},a_{t}),1\\}\right)^{-1}\right]}$
(72)

where in $(a)$ we have used Lemma A.1.

Furthermore, we have

$\displaystyle\quad~{}\sum_{t=0}^{T-1}\left(\max\\{N_{t}(s_{t},a_{t}),1\\}\right)^{-1}=\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\sum_{j=0}^{N_{T}(s,a)-1}\left(\max\\{j,1\\}\right)^{-1}$
(73)
$\displaystyle\leq\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\left[1+\log(N_{T}(s,a)+1)\right]\leq
SA\left[1+\log\left(\frac{T}{SA}+1\right)\right]$ (74)

where the last inequality is due to the concavity of the function
$f(x)=\log(x+1)$.

Fix a state-action pair $(s,a)\in\mathcal{S}\times\mathcal{A}$, let
$k_{1}<k_{2}<...<k_{m}$ be the first $m$ episodes such that the event
$\\{N_{t}(s,a)>2N_{t_{k}}(s,a)\\}$ occurs. Let $\bar{\tau}_{l}:=t_{k_{l}+1}-1$
denote the last timestamp in episode $k_{l}$. Using induction, it can be shown
that $N_{\bar{\tau}_{l}}(s,a)\geq 2^{l}-1$ for $1\leq l\leq m$. Therefore, the
above event can occur in no more than $\log_{2}(N_{T}(s,a)+1)$ episodes.
Therefore, we have

$\displaystyle\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}\bm{1}_{\mathcal{E}_{t}}$
$\displaystyle\leq\sum_{(s,a)\in\mathcal{S}\times\mathcal{A}}\left(\max_{k\in[K]}T_{k}\right)\log_{2}(N_{T}(s,a)+1)$
(75) $\displaystyle\leq
SA\left(\max_{k\in[K]}T_{k}\right)\log_{2}\left(\frac{T}{SA}+1\right).$ (76)

where the last inequality is due to the concavity of the function
$f(x)=\log(x+1)$.

Also note that one can obtain a prior-dependent bound on the second term in
(68) can be bounded with Lemma A.1:

$\displaystyle\mathbb{E}\left[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}I_{k}\bm{1}_{\mathcal{E}_{t}}\right]\leq\mathbb{E}\left[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}I_{k}\right]=\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}\mathbb{E}\left[I_{k}\right]\leq\varepsilon
T$ (77)

Therefore, we conclude that

$\displaystyle\mathbb{E}\left[\sum_{k=1}^{K}\sum_{t=t_{k}}^{t_{k+1}-1}I_{k}\bm{1}_{\mathcal{E}_{t}}\right]\leq\min\left\\{\varepsilon
T,SA\left(\max_{k\in[K]}T_{k}\right)\log_{2}\left(\frac{T}{SA}+1\right)\right\\}$
(78)

Finally, combining (56)(68)(72)(74)(78), we have

$\displaystyle\quad~{}\sum_{k=1}^{K}\mathbb{E}[Z_{k}]$ (79)
$\displaystyle\leq\bar{v}+\bar{v}\varepsilon(2K-1)+\bar{v}\sqrt{\varepsilon
T[(4\log 2)S+4\log(SAKT)]SA\left[1+\log\left(\frac{T}{SA}+1\right)\right]}+$
(80) $\displaystyle+2\bar{v}\min\left\\{\varepsilon
T,SA\left(\max_{k\in[K]}T_{k}\right)\log_{2}\left(\frac{T}{SA}+1\right)\right\\}+2\bar{v}$
(81) $\displaystyle\leq 3\bar{v}+2\bar{v}(R_{1}+R_{2}+R_{3})$ (82)

where

$\displaystyle R_{1}$ $\displaystyle:=\varepsilon K$ (83) $\displaystyle
R_{2}$ $\displaystyle:=\sqrt{\varepsilon
S^{2}AT\log(2SAKT)\left[1+\log\left(\frac{T}{SA}+1\right)\right]}$ (84)
$\displaystyle R_{3}$ $\displaystyle:=\min\left\\{\varepsilon
T,SA\left(\max_{k\in[K]}T_{k}\right)\log_{2}\left(\frac{T}{SA}+1\right)\right\\}$
(85)

###### Proof of Claim.

Let $\check{\theta}^{n}(\cdot|s,a)$ be the empirical distribution of the next
states of the state-action pair $(s,a)$ after observing $(s,a)$ exactly $n$
times. By the $L_{1}$ concentration inequality for empirical distributions
(Weissman et al., 2003), we have

$\displaystyle\mathbb{P}_{\theta^{*}}(\|\check{\theta}^{n}(\cdot|s,a)-\theta^{*}(\cdot|s,a)\|_{1}>\lambda)\leq
2^{S}\exp\left(-\frac{1}{2}n\lambda^{2}\right)$ (86)

for any $\lambda>0$. For $\delta>0$, define
$\xi(n,\delta):=\min\left\\{\sqrt{\frac{(2\log
2)S+2\log(1/\delta)}{n}},2\right\\}$, we have

$\displaystyle\mathbb{P}_{\theta^{*}}\left(\|\check{\theta}^{n}(\cdot|s,a)-\theta^{*}(\cdot|s,a)\|_{1}>\xi(n,\delta)\right)\leq\delta.$
(87)

Define

$\displaystyle\hat{\theta}^{t}(\cdot|s,a):=\begin{cases}\frac{1}{t}\sum_{\tau=0}^{t-1}\bm{1}_{\\{(s_{\tau},a_{\tau})=(s,a),s_{\tau+1}=\cdot\\}}&t>0\\\
\text{uniform}&t=0\end{cases}$ (88)

to be the empirical distribution of next states of $(s,a)$ in the first $t$
steps. Define

$\displaystyle\hat{\varTheta}^{k}$
$\displaystyle=\left\\{\theta:\|\hat{\theta}^{t_{k}}(\cdot|s,a)-\theta(\cdot|s,a)\|_{1}\leq\xi(N_{t_{k}}(s,a),\delta)~{}~{}\forall
s\in\mathcal{S},a\in\mathcal{A}\right\\}$

Then, we have $\mathbb{P}(\theta^{*}\not\in\hat{\varTheta}^{k})=0$ if
$t_{k}=0$ (since $\xi(0,\delta)=2$) and

$\displaystyle\quad~{}\mathbb{P}(\theta^{*}\not\in\hat{\varTheta}^{k})$ (89)
$\displaystyle\leq\mathbb{P}\left(\exists
n\in[t_{k}],s\in\mathcal{S},a\in\mathcal{A}~{}~{}\|\check{\theta}^{n}(\cdot|s,a)-\theta^{*}(\cdot|s,a)\|_{1}>\xi(n,\delta)\right)$
(90) $\displaystyle\leq t_{k}SA\delta$ (91)

if $t_{k}>0$.

Since $\theta^{*}$ and $\tilde{\theta}^{k}$ are i.i.d. given
$\tilde{\mathcal{D}}_{k}$, and the random set $\hat{\varTheta}^{k}$ is
measurable with respect to $\tilde{\mathcal{D}}_{k}$, we have
$\mathbb{P}(\theta^{*}\not\in\hat{\varTheta}^{k})=\mathbb{P}(\tilde{\theta}^{k}\not\in\hat{\varTheta}^{k})$.
Therefore we have

$\displaystyle\quad~{}\mathbb{E}\left[\|\tilde{\theta}^{k}(\cdot|s_{t},a_{t})-\theta^{*}(\cdot|s_{t},a_{t})\|_{1}\cdot
I_{k}\right]$ (92)
$\displaystyle\leq\mathbb{E}\left[\|\tilde{\theta}^{k}(\cdot|s_{t},a_{t})-\theta^{*}(\cdot|s_{t},a_{t})\|_{1}\cdot
I_{k}\bm{1}_{\\{\theta^{*},\tilde{\theta}^{k}\in\hat{\varTheta}^{k}\\}}\right]+$
(93)
$\displaystyle+\mathbb{E}\left[\|\tilde{\theta}^{k}(\cdot|s_{t},a_{t})-\theta^{*}(\cdot|s_{t},a_{t})\|_{1}\cdot
I_{k}\left(\bm{1}_{\\{\theta^{*}\not\in\hat{\varTheta}^{k}\\}}+\bm{1}_{\\{\tilde{\theta}^{k}\not\in\hat{\varTheta}^{k}\\}}\right)\right]$
(94) $\displaystyle\leq\mathbb{E}[2\xi(N_{t_{k}}(s_{t},a_{t}),\delta)\cdot
I_{k}]+2\left(\mathbb{P}(\theta^{*}\not\in\hat{\varTheta}^{k})+\mathbb{P}(\tilde{\theta}^{k}\not\in\hat{\varTheta}^{k})\right)$
(95) $\displaystyle\leq 2\mathbb{E}[\xi(N_{t_{k}}(s_{t},a_{t}),\delta)\cdot
I_{k}]+4t_{k}SA\delta$ (96)

∎

##  Appendix B Proof of Lemma 3.8

In this proof, let $\mathbb{P}_{\theta^{*}}$ be the distribution induced by
the expert’s policy $\pi^{\beta}$ conditioning on $\theta^{*}$.

Under Assumption 2.2, we have $q(s,a^{\prime};\theta)-q(s,a;\theta)\leq
r(s,a^{\prime})-r(s,a)+\bar{v}\leq 1+\bar{v}$ for any
$s\in\mathcal{S},a,a^{\prime}\in\mathcal{A}$. Therefore, for any
$s\in\mathcal{S},a\in\mathcal{A}$, we have

$\displaystyle\pi^{\beta}(a|s)$ $\displaystyle:=\dfrac{\exp(\beta
q(s,a;\theta^{*}))}{\sum_{a^{\prime}\in\mathcal{A}}\exp(\beta
q(s,a^{\prime};\theta^{*}))}$ (97)
$\displaystyle=\dfrac{1}{\sum_{a^{\prime}\in\mathcal{A}}\exp[\beta(q(s,a^{\prime};\theta^{*})-q(s,a;\theta^{*}))]}$
(98) $\displaystyle\geq\dfrac{1}{1+(A-1)\exp(\beta(1+\bar{v}))}=:\pi_{\min}$
(99)

Combining (99) with Assumption 3.7, for any $s,s^{\prime}\in\mathcal{S}$,

$\mathbb{P}_{\theta^{*}}(\exists 0<k\leq
S,s_{k}=s^{\prime}|s_{0}=s)\geq\delta(\pi_{\min})^{S}=:\tilde{\delta}$ (100)

Let $X_{s,s^{\prime}}$ be a random variable that represents the hitting time
of $s^{\prime}$ starting from $s$, i.e. it follows the conditional
distribution of $\min\\{t>0:s_{t}=s^{\prime}\\}$ given $s_{0}=s$. Following
the same derivation of Equation (1.18) of Levin and Peres (2017), we have

$\mathbb{P}_{\theta^{*}}(X_{s,s^{\prime}}>kS)\leq(1-\tilde{\delta})^{k}\quad\forall
k\in\mathbb{N}$ (101)

Therefore, for any $u>0$,

$\displaystyle\mathbb{P}(X_{s,s^{\prime}}>u)\leq(1-\tilde{\delta})^{\lfloor
u/S\rfloor}\leq(1-\tilde{\delta})^{\frac{u}{S}-1}$ (102)

Set $\lambda=-\frac{1}{2S}\log(1-\tilde{\delta})>0$, we have

$\displaystyle\mathbb{E}[\exp(\lambda X_{s,s^{\prime}})]$
$\displaystyle=\int_{0}^{\infty}\mathbb{P}(\exp(\lambda
X_{s,s^{\prime}})>x)\mathrm{d}x$ (103)
$\displaystyle=1+\int_{1}^{\infty}\mathbb{P}(\exp(\lambda
X_{s,s^{\prime}})>x)\mathrm{d}x$ (104)
$\displaystyle=1+\lambda\int_{0}^{\infty}\mathbb{P}(\exp(\lambda
X_{s,s^{\prime}})>\exp(\lambda u))\exp(\lambda u)\mathrm{d}u$ (105)
$\displaystyle\leq
1+\lambda\int_{0}^{\infty}(1-\tilde{\delta})^{\frac{u}{S}-1}\exp(\lambda
u)\mathrm{d}u$ (106)
$\displaystyle=1+\lambda\int_{0}^{\infty}(1-\tilde{\delta})^{\frac{u}{2S}-1}\mathrm{d}u=:\exp(\tilde{\lambda}).$
(107)

Next, we establish that with high probability, each state must be visited at
least $c_{1}N$ times in an $N$-step trajectory for some constant $c_{1}>0$.
Let $\bar{N}(s):=\sum_{t=0}^{N-1}\bm{1}_{\\{\bar{s}_{t}=s\\}}$ be the number
of visits to state $s$ in the offline data (excluding the final state
$\bar{s}_{N}$). Let $X_{\bar{s}_{1},s;0},X_{s,s;1},X_{s,s;2},X_{s,s;3},\cdots$
be mutually independent random variables representing hitting times. For any
$K\in\mathbb{N}$ we have

$\displaystyle\mathbb{P}_{\theta^{*}}(\bar{N}(s)<K)$
$\displaystyle\leq\mathbb{P}_{\theta^{*}}\left(X_{\bar{s}_{1},s;0}+\sum_{k=1}^{K-1}X_{s,s;k}\geq
N\right)$ (108) $\displaystyle=\mathbb{P}_{\theta^{*}}\left(\exp\left(\lambda
X_{\bar{s}_{1},s;0}+\lambda\sum_{k=1}^{K-1}X_{s,s;k}\right)\geq\exp(\lambda
N)\right)$ (109) $\displaystyle\leq\exp(-\lambda
N)\mathbb{E}\left[\exp\left(\lambda
X_{\bar{s}_{1},s;0}+\lambda\sum_{k=1}^{K-1}X_{s,s;k}\right)\right]$ (110)
$\displaystyle\leq\exp(-\lambda N)[\exp(\tilde{\lambda})]^{K}=\exp(-(\lambda
N-\tilde{\lambda}K)).$ (111)

Set $K=\lfloor\frac{\lambda}{2\tilde{\lambda}}N\rfloor$, we have
$\mathbb{P}_{\theta^{*}}(\bar{N}(s)<K)\leq\exp(-\lambda N/2)$.

Fix $s\in\mathcal{S}$ and let $a_{s}^{*}:=\pi^{*}(s)$. Under Assumption 3.6 we
have

$\displaystyle\pi^{\beta}(a_{s}^{*}|s)$ $\displaystyle=\dfrac{\exp(\beta
q(s,a_{s}^{*};\theta^{*}))}{\sum_{a\in\mathcal{A}}\exp(\beta
q(s,a;\theta^{*}))}$ (112)
$\displaystyle=\dfrac{1}{\sum_{a\in\mathcal{A}}\exp[\beta(q(s,a;\theta^{*})-q(s,a_{s}^{*};\theta^{*}))]}$
(113) $\displaystyle\geq\dfrac{1}{1+(A-1)\exp(-\beta\Delta)}.$ (114)

For the rest of the proof, we assume that $\beta\geq\log(2(A-1))/\Delta$. Then
$\pi^{\beta}(a_{s}^{*}|s)\geq\frac{2}{3}$.

For $L\in\mathbb{N}$, define $\mathcal{F}_{L}(s)$ to be the event that in the
first $L$ visits to the state $s$, the action $\pi^{*}(s)$ is chosen $\leq
L/2$ times. We have

$\mathbb{P}_{\theta^{*}}(\mathcal{F}_{L})\leq\mathbb{P}(\mathcal{B}(L,2/3)\leq
L/2)\leq\exp\left(-\frac{L}{18}\right)$ (115)

where $\mathcal{B}(L,p)$ is a binomial random variable with parameters $L$ and
$p$. The last inequality in (115) can be established with Hoeffding’s
inequality.

Now, consider a construction of $\hat{\pi}^{*}$ as follows: For each
$s\in\mathcal{S}$ and $a\in\mathcal{A}$, let
$\bar{N}(s,a):=\sum_{t=1}^{N}\bm{1}_{\\{\bar{s}_{t}=s,\bar{a}_{t}=a\\}}$.
Define
$\hat{\pi}^{*}(s)=\operatorname*{arg\,max}_{a\in\mathcal{A}}\bar{N}(s,a)$
(ties are broken following a fixed ordering on $\mathcal{A}$). Now we have

$\displaystyle\mathbb{P}_{\theta^{*}}(\hat{\pi}^{*}(s)\neq\pi^{*}(s))$
$\displaystyle\leq\mathbb{P}(\bar{N}(s,a_{s}^{*})\leq\bar{N}(s)/2)$ (116)
$\displaystyle\leq\mathbb{P}_{\theta^{*}}(\bar{N}(s)<K)+\mathbb{P}_{\theta^{*}}(\bar{N}(s)\geq
K,\bar{N}(s,a_{s}^{*})\leq\bar{N}(s)/2)$ (117)
$\displaystyle\leq\mathbb{P}_{\theta^{*}}(\bar{N}(s)<K)+\sum_{L=K}^{N}\mathbb{P}_{\theta^{*}}(\mathcal{F}_{L})$
(118) $\displaystyle\leq\exp\left(-\dfrac{\lambda
N}{2}\right)+N\exp\left(-\frac{K}{18}\right)\leq\left(1+e^{1/18}N\right)\exp(-cN)$
(119)

where $c:=\min\\{\frac{\lambda}{2},\frac{\lambda}{36\tilde{\lambda}}\\}$.

Note that $c$ is a function of $(S,A,\bar{v},\Delta,\delta,\beta)$, in
particular, it is independent of $\theta^{*}$. Therefore we conclude that

$\displaystyle\mathbb{P}(\hat{\pi}^{*}\neq\pi^{*})\leq\sum_{s\in\mathcal{S}}\mathbb{P}(\hat{\pi}^{*}(s)\neq\pi^{*}(s))\leq
S(1+1.06N)\exp(-cN)$ (120)