Bridging Imitation and Online Reinforcement Learning: An Optimistic Tale
Authors: Botao Hao
Rahul Jain
Dengwang Tang
Zheng Wen
Venue: Accepted by TMLR ()

Abstract: In this paper, we address the following problem: Given an offline demonstration dataset from an imperfect expert, what is the best way to leverage it to bootstrap online learning performance in MDPs. We first propose an Informed Posterior Sampling-based RL (iPSRL) algorithm that uses the offline dataset, and information about the expert's behavioral policy used to generate the offline dataset. Its cumulative Bayesian regret goes down to zero exponentially fast in $N$, the offline dataset size if the expert is competent enough. Since this algorithm is computationally impractical, we then propose the iRLSVI algorithm that can be seen as a combination of the RLSVI algorithm for online RL, and imitation learning. Our empirical results show that the proposed iRLSVI algorithm is able to achieve significant reduction in regret as compared to two baselines: no offline data, and offline dataset but used without suitably modeling the generative policy.
Our algorithm can be seen as bridging online RL and imitation learning.

Published in Transactions on Machine Learning Research (10/2023)
Bridging Imitation and Online Reinforcement Learning: An Optimistic Tale
Botao Hao Google Deep
bhao @google.coommmoo
Rahul Jain
rahul.jain edu
University of Southern California Google DeepMind"
Dengwang Tang Universily of Southern California
dengwang&usc... edu
Zheng Wen
thenguen@@google.com
Google DeepMind
Reviewed on OpenReview: https: // openreview. net/ forum? id- Xam6fX0M6C
Abstract
In this paper, we address the following problem: Given an offline demonstration dataset from an imperfect expert, what the best way to leverage to bootstrap online learning performance in MDPs. We first propose an Informed Posterior Sampling based RL (iPSRL) algorithu that uses the offline dataset, and information about the expert's behavioral policy used to generate the offline dataset. Its cumulative Bayesian regret gocs down to zero exponentially fast in N, the oflline dataset size if the expert is competent enough. Since this algorithm is computationally impractical, we then propose the iRLSVI algorithm that can be seen as a combination of the RLSVI algorithm for online RI, and imitation lcarning. Our empirical results show that the proposed iRLSVI algorithm is able to achieve significant reduction in regret as compared to two baselines: no offline data, and offline dataset but used without suitably modeling the generative policy. Our algorithm can be seen bridging online RL and imitation learning.
1 Introduction
An early vision of the Reinforcement Learning (RL) field is to design learning agent that when let loose in unknown environment, learns by interacting with it. Such an agent starts with blank slate (with possibly, arbitrary initialization). takes actions, receives state and reward observations, and thus learns by "reinforcement". This remains a goal but at the same time, it is recognized that in this paradigm learning is too slow, inefficient and often impractical. Such a learning agent takes too long to learn near-optimal policies way beyond practical time horizons of interest. Furthermore, deploying an agent that learns by exploration over long time periods may simply be impractical.
In fact, reinforcement learning is often deployed to solve complicated engineering problems by first collecting offline data using behavioral policy, and then using off-polic, reinforcement learning, imitation learning methods (if the goal is to imitate the policy that generated the offline datasct) on such datasets to learn a policy. This often suffers from the distribulion-shif! problem, i.e, the learnt policy upon deployment often performs poorly on out-of-distribution state-action space. Thus, there is a need for adaptation and fine-tuning upon deployment.
* Work done while Google DeepMind.

---

Published in Transactions on Machine Learning Research (10/2023)
In this paper, we propose systematic way to use offline datasets to bootstrap online RL algorithms. Performance of online learning agents is often measured in terms of cumulative (expected) regret. We show that, as expected, there is a gain in performance (reflected in reduction in cumulative regret) of the learning agent as compared to when it did not use such an offiine dataset. We call such an online learning agent as being partially informed. However, somewhat surprisingly, if the agent is further informed about the behavioral policy that generated the offline datasct, such an informed (online learning) agent can do substantially better, reducing cumulative regret significantly. In fact, we also show that if the behavioral policy is suitably parameterized by competence parameter, wherein the behavioral policy is asymptotically the optimal policy, then the higher the "competence" level, the better the performance in terms of regret reduction over the baseline case of no offline dataset.
We first propose an ideal (informed) iPSRL (posterior sampling based RL) algorithm and show via theoretical analysis that under some mild assumptions, its expected cumulative regret bounded as Õ(VT) where T is the number of episodes. In fact, we show that if the competence of the expert is high enough (quantificd in terms of parameter we int roduce), the regret goes to zero exponentially fast. as N, the offline dataset size grows. This is accomplished through novel prior-dependent regret analysis of the PSRL algorithm, the first such result to the best of our knowledge. Unfortunately, posterior updates in this algorithm can be computationally impractical. Thus, we introduce a Bayesian-bootstrappe posterior sampling, called the (informed) iRLSVI algorithm (due to its commonality with the RLSVI algo- rithm introduced in Osband et al. (2019)). ) The iRLSVI algorithm involves optimizing a loss function that is an optimístic upper bound on the loss function for MAP estimates for the unknown parameters. Thus, while inspired by the posterior sampling principle, it also has an optimism flavor to it. Through, numeri- cal experiments, we show that the iRLSVI algorithm performs substantially better than both the partially informed-RLSVI (which uses the offline dataset naively) as well as the uninformed-RLSVT algorithm (which doesn't use it at all).
algorithm for approximate
Wc also show that the iRLSVI algorithm can be seen as bridging online reinforcement learning with imitation learning since its loss function can be seen as combination of an online learning term as well as an imitation learning term. And if there no offline dataset, it essentially behaves like an online RL algorithm. Of course, in various regimes in the middle it is able to interpolate scamlessly.
Related Work. Because of the surging use of ofline dalasels for pre-training (e.g., in Large Language models (LLMs), e.g., see Brown et al. (2020); Thoppilan et al.
2022 there has been a lot of interest in Offline RL, i.e., RL using offline datasets Levine et al.] (020). A fundamental issue
(2022] : Hoffmann et al.
this literature addresses is RL algorithm design (Nair et al. 2020 Kostrikov et al. 2021
Kumar et al. 2020
Nguyen- Taang & Arora 2023 Fujimoto et al. 2019; Fujimoto & Gu |021] Ghosh et al.
2022 and analysis
to best address the "outtof-distribution" (OOD) problem, i.e., policies learnt from offline datasets may not perform well upon deployment. The dominant design approach is based on 'pessimism' (Jin et al. 2021:
Xie et al. 2021a Rashidinejad et al., (021]) which often results in conservative performance in practice. Some of the thcoretical literature (Xie et al. 2021a Rashidinejad et al.] 2021 Uchara & Sun 2021 Agarwal & Zhang 2022) has focused on investigation of sulficient conditions such as "concentrability measures" " under which such offline RL algorithms can have guaranteed performance. Unfortunately, such measures of offline
dataset quality are hard to compute, and of limited practical relevance (Argenson & Dulac- 2020
Nair et al. 2020 Kumar et al. 2020 Levine et al. 2020 Kostrikov et al., 2021 2022
Wagenmaker & Pacchiano
There is of course, a large body of literature online RL (Dann et al. 2021 Tiapkin et al. 2022
Ecoffet
ct al. 2021 Guo et al. 2022 Ecoffet et al.
2019 Osband et al. 2019h with two dominant design philosophies: algo-
Optimism-Die based algorithms such as UCRL2
in Auer et al. (2008) ; and Posterior Sampling
rithms such as PSRL (Osband et al. 2013
Ouyang et al.
2017p, etc. (Osband et al. 2016a b 2019 Russo &
Van Roy| 2018 Zanette Sarkar 2017
Wen et al. 2020 Hao & Lattimore) 2022). However, none of these
algorithms consider starting the learning agent with an offline dataset. Of course, imitation learning (Hester
et al. 2018 [Beliacy et al.) 2022 Schaal 1996) is exactly concerned with learning the expert's behavioral
policy (which may not be optimal) from the offline datasets but with no online finetuning of the policy learnt.
Several papers have actually studied bridging offline RL and imitation learning (Ernst et al.] 2005 Kumar
lt al.
2022 Rashidinejad et al.
2021 Hansen et al. 2022
Vecerik et al.
2017
Lee et al. 2022 Some have
2

---

Published in Transactions on Machine Learning Research (10/2023)
also studied offine RL followed by small amount of policy fine-tuning (Song et al 2022 Fang et al. 2022;
Xie et al. 2021b; Wan et al., 2022 Schriitwieser et al.] 2021 Ball et al. 2023 Uehara & Sun 2021
Xie
let al. 2021b
Agarwal & Zhang 2022) with the goal of finding policies that optimize simple regret.
The problem we study in this paper is motivated by a similar question: Namely, given an offline demonstration dataset from an imperfect expert, what is the best way to leverage to bootstrap online learning performance in MDPs? However, our work different in that it focuses on cumulative regret as a measure of online learning performance. This requires smart exploration strategies while making maximal use of the offline dataset to achieve the best regret reduction possible over the case when offline dataset is not available. Of course, this will depend on the quality and quantity of the demonstrations. And the question is what kind of algorithms can one devise to achieve this objective, and what information about the oflline -onlase--geneattion process is helpful? What is the best regret reduction that is achievable by use of offline datasets? How it depends on the quality and quantity of demonstrations, and what algorithms can one devise to achieve them? And does any information about the offline-dtasct generation process help in regret reduction? We answer some of these questions in this paper.
2 Preliminaries
Episodic Reinforcement Learning. Consider a sccnario where an agent repeatedly interacts with an enviromment modelled as a finite-horizon MDP, and refer to each interaction as an episode. The finite-horizon MDP is represented by a tuple M = (S, p.r, H, v), where is a finite state space (of size S), A is a finite action space (of size A), P encodes the transition probabilities, r is the reward function, H is the time horizon length, and is the initial state distribution. The interaction protocol is as follows: the beginning of each episode 4, the initial state s is independently drawn from Then, al each period h in episode t, if the agent takes action af, E A at the current state sh. E S, then it will receive a reward Th (sf, af)) and transit to the next state s/411 E (- af). An episode terminates once the agent arrives at state H in period H and receives a reward ( ). We abuse notation for the sake of simplicity, and just use rn (s' ( instead of rn (8"),, though no action taken at period H. The objective is to maximize its expected total reward over T episodes.
H -
Let Qi and Vi respectively denote the optimal state-action value and state value functions at period h. Then, the Bellman equation for MDP M is
@ī(s,a) = as) + Σ a))
where (s') == max; 1h+1 b), if h < H and (s') = 0, 1- We define policy æ mapping from state-period pair to probability distribution over the action space A. A policy x² is optimal if (-1s) E arg max,, E. 07 (s, (als(a for all s S and all h.
Agent's Prior Knowledge about M. We assume that the agent does not fully know the environment M; otherwise, there is no need for learning and this problem reduces to an optimization problem. However, the agent usually has some prior knowledge about the unknown part of M. For instance, the agent might know that M lies in a low-dimensional subspace, or may have a prior distribution over M. We use the notation M(0) where 0 parameterizes the unknown part of the MDP. When we want to emphasize il as a random quantity, we will denote by H* with a prior distribution no. Of course, different assumptions about the agent's 's prior knowledge lead to different problem formulations and algorithm designs. As first step, we consider two canonical settings:
Tabular RL:
The agent knows S,A,r, H and v, but does not know P. That is, 0" = P in this setting. We also assume that the agent has a prior over P, and this prior is independent across state-period-action triples.
Linear value function generalization: The agent knows S,A, H and v, but does not know P and r. Moreover, the agent knows that for all h Q lies in a low-dimensional subspace span(
3

---

Published in Transactions on Machine Learning Research (10/2023)
where 4 E Rili|-Aidd is known matrix. In other words, Q% = 4n6% for some 0% Rd. Thus, in this setting 0" 10 , T. We also assume that the agent has a Gaussian prior over 0*
As we will discuss later, the insights developed in this paper could potentially be extended more general cases.
Offline Datasets. We denote offline dataset with L episodes as Do {( (()))) where N = HT. denotes the dataset size in terms of number of observed transitions. For the sake of simplicity, we assume we have complete trajectories in the dataset but it can easily be generalized if not. We denote an online dataset with episodes as Hr = {( ag. ... , and D. = Do @ H4.
The Notion of Regret. A online learning algorithm ø is a map for each episode t, and time h, Φt, : Dr + AA, the probability simplex over actions. We define the Bayesian regret of an online learning algorithm e over T episodes as
T
H Σ Enassh h=0
Emalshdd) d )]
BRT (0)
E
(o
where the (sf, a's'ss are the state-action tuples from using the learning algorithm &, and the expectation is over the sequence induced by the interaction of the learning algorithm and the environment, the prior distributions over the unknown parameters l" and the offline dataset Do-
Expert's behavioral policy and competence. We assume that the expert that generated the offline demonstrations may not be perfect, i.., the actions it takes are only approximately optimal with respect to the optimal Q-value function. To that end, we model the expert's policy by use of the following generative model,
(33()))))77s.a)
T (als) E.
(2)
Σ. cxp(
where 3(s) 2 0 called the depeedde deliberateness parameter, e.g., when B(s) = 0, the expert behaves naively in state s, and takes actions uniformly randomly. When B(s) + oo, the expert uses the optimal policy when in state s. When B(-) is unknown, we will assumne an independent exponential prior for the sake of analytical simplicity, f2(3(s)) X2 exp(-)g9(s)) over B(s) where de 0 is the same for all In our experiments, we will regard ((s) as being the same for all states, and hence a single paramcter.
The above assumes the expert. is know ledgleeee about Q" However, it may know it only approximately. To model that, we introduce knowledgeabiiity parameter À 2 0. The expert then knows Q which distributed as NV"",, I/>?) conditioned on f, and selects actions according the softmax policy Eq. (2), with the Q" replaced by Q. The two parameters (3, logether will be referred to as the compelence the expert. In this case, we denote the expert's policy as n 8.A
Remark 2.1. While the form of the generative policy in Eq. 2 seemss specific, (-Is) (s) is a random vector with support over the entire probability simplex. In particular, one regards B(s) and (s, as parameters that parameterize the policy, the softmax policy structure in Eq. [2) is enough to realize any stationary policy.
Furthermore, we note that our main objective here is to yield clear and useful insights when information is available to be able to model the expert's behavioral policy with varying competence levels. Other forms of generative policies can also be used including e-optimal policies introduced in (Beliaev et al. 2022). and the framework extended.
3
The Informed PSRL Algorithm
We now introduce simple Informed Posterior Sampling-basel Reinforcement Learning (1PSRL) algorithm that naturally uses the offline dataset Du and action generation information construct an informed prior distribution over 0*. The realization of 0* is assumed known to the expert (but not the learning agent) with
4

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm iPSRL
Input: Prior μo: Initial state distribution y
for f = 1, T do
(A1) Update posterior, 1, using Bayes' rule
(A2) Sample 0 ~
Compute optimal policy (-(+s) == x)(=s;0,,) (for all h) by using any DP or other algorithm Sample initial state s/ ~ V
for h= 0,...
do Take action a 7 (1+%)
Observe (5 (s)++)) end for end for
-()-;))==) Q(.:0')), and [(s) = 3 2 0 (i.e,, it is state-invariant) is also known to the expert. Thus, the lcarning agent's ' posterior distribution over 8" given the offline datasct is,
11 ==) (Do) p -)) E.
/ II
1-1
(3)
= P(O" E.)
by Df a (
1 0)v(s() d0.
Joc.
h=0
A PSRL agent (Osband et al. 2013 Ouyang al. 2017 takes this as the prior, and then updates the posterior distribution over 8* as online observation tuples, {(5), ai si = become available. Such an agent is really an ideal agent with assumed posterior distribution updates being exact. In practice, this is computationally intractable and we will need to get samples from an approximate posterior distribution, an issue which we will address the next section. We will denote the posterior distribution over 0* given the online observations by episodes and the oflline dataset by Pt.
We note the key steps (A1)-(A2) in the algorithm above where we both offline dataset Do and online observations H4 to compute the posterior distribution over H by use of the prior
3.1 Prior-dependent Regret Bound
It natural expect some regret reduction if oflline demonstration dataset is available to warm-start the online learning. However, the degree of improvement must depend the "quality" of demonstrations, for example through the competence parameter B. Further note that the role of the offline dataset is via the prior distribution the PSRL algorithm uses. Thus, theoretical analysis involves obtaining a prior-dependent regret. bound, which we obtain next.
Lemma 3.1. Let = P(#* + x²), ie. the probability that the stralegy used for the first episode, #1 is not optimal. Then,
BAr PPSRL O(VEHAA5AATTTI + log(T)))
(4)
The proof can be found in the Appendix. Note that this Lemma provides prior dependent-bound in terms of e.
In the rest the section, we provide an upper bound on = = P(# * T*) for Algorithm 1 iPSRL. We first show that e can be bounded terms of estimation error the optimal stratogy given the offline data. Lemma 3.2. Let R be any estimator of x² constructed from Do, then P(#* + x²) & 2P *x*)
Proof. If 11 * x², then either ** + # or 4x # x* must be true. Conditioning on Do, ** is identically distributed while 4 is deterministic, therefore
P(# x**) < IP + # + 1P("" **¹) 21P xT)
5

---

Published in Transactions on Machine Learning Research (10/2023)
We now bound the estimation error of x² We assume the following about the prior distribution of 0r. Assumption 3.3. There exists a > 0 such that for all 0 θ, h h= 0, .. H an a' A such that Qx a;; 0) 2 Qn d'; + A Va' E A\faa)
.H-1. - 1, and s E S, there exists
Define (s; 0) p (0) (5h 2), where x² (0) denotes the optimal policy under model 0. Assumption 3.4. The infimum probability of any reachable non-final state, defined as
P in OSS H. E 5,8 O (,(ss) > 0}
satisfies p > 0.
We now describe a procedure to construct an estimator of the optimal policy, ** from Do so that F(** F(*** 4*) is small. Fix an integer L, and choose a (0, For each 0 E θ, define a deterministic Markov policy x =0) = (1)))) sequentially through
arg max, (s,s, if Po (0) = 8) 0,
if Paria 10) = 8) > 0
(s;
(5)
Co.
where the tiebreaker for the argmax operation is based on fixed order on actions, and ão E A is fixed action in A. It is clear that n" (f) is an optimal policy for the MDP 0. Furthermore, for those states that are impossible to be visited, we choose to lake a fixed action āo. Although the choice of action at those states doesn't matter, our construction will be helpful for the proofs.
Construction of #*: Let (s) (resp. (s, a)) be the number of times state s (resp. statc-action pair (8,a) a)) appears at time h in dataset Do- Define #* to be such that:
(s) = arg maxaeA NE(s,,) a) (ties are broken through some fixed ordering of actions) whenever
(s) 2 SL;
Ag do whenever (s)s) < ,L. on fixed action in A that was used in the definition of x (0).
The idea of the proof is that for sufficiently large 3 and L, we can choose a 5 E (0, such that
Claim 1: If E S is probable at time h under x" =0),, then Ns(s) 2 8L with large probability. Furthermore, (s) arg maxaeA (N a) with large probability as well.
Claim 2: If E S is improbable at time h under (0), then Nx(s) < dL with large probability;
then conclude that the probability of x² * * is small via standard union bound argument. The arguments are formalized in Lemma A.2 We now present the upper bound on Bayesian regret for Algorithm [ iPSRL.
Given the two claims,
Thcorem 3.5. For sufficiently large 3 independent of L, we have
(P = HLVEL (T)(
(6)
where
Lp²
Lp
$ = min
1, 2SH
exp
+ exp
18
36
Proof. The result follows from Lemmn 3.1
Lemma
3.2 and Lemma
A.2
We note that the right-hand side of Eq. 6 converges to zero exponentially fast as N LH - oc.
Remark 3.6. (a) For fixed N, and large S and A, the regret bound is O(H'SVAT)), which possibly could be improved in H. (b) For a suitably large 3, the regret bound obtained goes zero exponentially fast as the number of episodes in the offline dataset, goes infinity thus indicating the online learning algorithm's ability to learn via imitation of the expert.

---

Published in Transactions on Machine Learning Research (10/2023)
4 Approximating iPSRL
4.1 The Informed RLSVI Algorithm
The iPSRL algorithm introduced in the previous section assumes that posterior updates can be done exactly. In practice, the posterior update in Eq- (3) 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 basod on Bayesian bootstrapping to obtain approximate posterior samples. The key idea is to perturb the loss function for the maximum posterior (MAP) estimate and use the point estimate surrogate for the exact posterior sample.
Note that in the emsuing, we regard B as also unknown to the learning agent (and A = oo for simplicity). Thus, the learning agent must form a belief over both 9 and / via a joint posterior distribution conditioned on the offline dataset Do and the online data at time t, Hz. We denote the prior pdf over by f(-) and prior pdf over by f2(-).
For the sake of compact notation, we denote (s, a; 0) as (s) in this section. Now, consider the offline dataset,
Du = {((s), oh $ N
and denote 0 = (0=) We introduce the temporal difference error EY (parameterized by given Q"),
(())))= == (1h max (5h.b (h(
We will regard 0% to only be parameterized by On, i.e. 2he but abuse notation for the sake of simplicity. We use this construct a parometerized offline dataset,
Do(29) = [((s),, ar,, She E% (l(()))) -0)))))))))))))
A parametrized online dataset Hcr after episode t can be similarly defined. To ease notation, we will regard the jth episode during the online phase as the (L j)th observed episode. Thus,
H₂(Q²) {((s) al,, sh (2") (Q")))=onn
the dataset observed during the online phase by episode t.
Note that Q" is to be rogarded as parameter. Now, at time t, we would like to obtain MAP estimate for (0,3) B) by solving the following:
MAP:
arg max log 0,8
log f(0) + log (8).
(7)
Denote perturbed version of the Ql-parameterized offline datasct by
1o( = {((s)) a/,, sh 1.)
where random perturbations are added: (i) actions have perturbation w/ ~ exp(1), (ii) rewards have per- turbations 21, ~ (O( o²), and (iii) the prior Ø N N0,0 Eo).
Note that the first and second terms involving H, and Do in Eq. 7 are independent of when conditioned on the actions. Thus, we have a sum of lokelikelihood of TD error, transition and action as follows:
log P(Po(Q9))
Σ
log P(E dh. sh (b.))+log log P( lah sh. Qb.H) + log P(a Oo.H)
L
Σ
log P( 1/, dr. sh 1 ) + log 1/h. 0.))
h

---

Published in Transactions on Machine Learning Research (10/2023)
By ignoring the log-likelihood of the transition term (akin to optimizing upper bound the negative loss function), are actually being optimistic.
For the terms in the upper bound above, under the random perturbations assumed above, we have
log P(E) oh t/ Pha++1)= - ( rhh z + max 1h+1 (h(h). constant
b
and
log TH (a/,1) 1%) = w/ (3Q log Σ exp (3Q%(sh,
Now, denole a perturbed version of the Q or-aaametrizee online dataset,
H.(Q²)) = {((s), & z
and thus similar to before, we have
L+
log P(24. Qb.n)
Σ
Σ ((E)( at oh, (..))+++ + log of Q%))
k=L+1
L+1
Σ
(log P(Ek1s at, sy Qhatt)),
km 1++1
h
where we again ignored the transition term to obtain an optimistic upper bound.
Given the random perturbations above, we have
log ((E)( of, shi 0hat1)) = 1 (rh 2 + max Q (št. Qh ot:) ) + constant.
The prior over 8, f2(3) is assumed to be an exponential pdf X2 exp(-223), 2 0, while that over is assumed Gaussian. Thus, putting it together, we get the following optimistic loss function (to minimize over and B),
L-1H-1
2 (5 (hh )²
[(0 202
ΣΣ
Th + 2 max 1h
(8)
1 #-1
ΣΣ wh
(BQ (BQR ab) - log Σ exp (3QR
+ 1 + (0) -T_ Eo - 0) + A28.
1=1 h=U
The above loss function difficult optimize in general due the max operation, and the Q-value function in general having nonlinear form.
Now Algorithm 2: iRLSVI can be summarized by replacing steps (A1)-(A2) in Algorithm 1: iPSRL by (B1)-(B2), with the other steps being the same:
(B1) Solve the MAP Problem by minimizing loss function (B2) Get solutions ())
Remark 4.1. Note that the loss function in Eq. { can be hard to jointly optimize over and 3. In particular, estimates of 3 can be quite noisy when / is large, and the near-optimal expert policy only covers the state- action space partially. Thus, we consider other methods of estimating / that are more robust, which can then be plugged into the loss function in Eq. Specifically, could simply look at the entropy of the empirical
8

---

Published in Transactions on Machine Learning Research (10/2023)
distribution of the action in the offline dataset. Suppose the empirical distribution of fob.... dn Hin is pA Then we use Co/ co/H (o/H(μa) as an estimation for 3, where co > O is hyperparameter. The intuition is that for smaller 3, 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 Eq. ( the parameter 0 appears inside the max operation. Thus, it can be quite difficult to optimize over B. 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 to use the parameter estimate 0 from the previous iteration inside the max operation, and thus optimize over 0 only in the other terms.
4.2 iRLSVI bridges Online RL and Imitation Learning
In the previous subsection, we derived iRLSVI, a argesiaanbbootttaappee algorithm. We now present inter- pretation of the algorithm as bridging online RL (via commonality with the RLSVI algorithm OOsand et al. 2016a) and imitation learning, and hence 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. RLSVI, that uses all of the data available at the end of episode t, including any offline datasct involves minimizing the corresponding loss function at cach time step:
(RI.VV(O)= 20
Σ K=U
(1 + Qh+ Qh(sh,
2
2 (00.1 0o.1)) Eo(0n. 0o.1).
1
Now, let us consider an imitation learning setting. Let n = (0/, a/, 3/ be the trajectory the Ith episode. Let tt (a) s) denote the empirical estimate of probability of taking action state time h, i.c., empirical estimate of the expert's randomized policy. Let p(r) denote the probability of observing the trajectory under the policy f.
Th Let 8.0 (-Is) denote the parametric representation of the policy used by the expert. And let (**((T) denote
the probability of observing the trajectory under the policy 3.0 Then, the loss function corresponding to the KL divergence between ((T)) and I//,p".((m is given by
(n, = DRL. (TE (()))) = / ())()) log II P(T) IT (T)
4 p(Ti) log p(T))
Σ 1=1
=
(T))
H-1
#n (a/l1sh) log
3,0 Th (a), s/:))
Am
Dog An (ah ( (sh) log thh (at shh]
L #-1
10% (h) log Σ exp (BQR(sh.
+ constant.
Remark 4.3. (i) The loss function (3, 0) is the same the second Bikelon)))ellhhodd) term in Eq. while the loss function (n)svi(f) is the same as the first and third terms there (except for perturbation) and minus the A term that corresponds to the prior over B. (ii) Note that while we used the more common KL divergence for the imitation learning loss function, use log loss would yield the same outcome.
8
Thus, the iRLSVI loss function can be viewed as
[3300) = (RISVI(O) + (3,00 A2
(9)
thus establishing that the proposed algorithm may be viewed as bridging Online RL with Imitation Learning. Note that the last term corresponds the prior over 3. If / is known (or uniform), will not show up the loss function above.
9

---

Published in Transactions on Machine Learning Research (10/2023)
The above also suggests a possible way to generalize and obtain other online learning algorithms that bootstrap by use of offline datasets. Namely, at each step, they can optimize a general loss function of the following kind:
+ a1 =((o)))
225
(10)
where CORL is loss function for Online RL algorithm, Eu is loss function for some Imitation Learning algorithm, and factor E [0, 1] provides way to tune between emphasizing the offline imitation learning and the online reinforcement learning.
5 Empirical Results
Experimental setup. We now present some empirical results in two prototypical environments: "Deep Sea" and "Maze". Specifically, we compare three variants of the RLSVI agents, which are respectively referred to as informed RLSVI (iRLSVI), partially informed RLSVI (piRLSVI), and uninformed RLSVI (uRLSVI). All three agents are tabular RLSVI agents with similar postcrior sampling-type exploration schemes. However, they differ in whether
and how to exploit the offline dataset. In particular, uRLSVI ignores the offline dataset; PiRLSVI exploits the offline dataset but does not utilize the information about the generative policy; while iRLSVI fully exploits the information in the offline dataset, about both the generative policy and the reward feedback. Please refer to Appendix D.1 for the pseudo-codes of these agents. We note no other algorithms are known for the problem as posed.
Deep Sea (Figure I (sbband et al. 2019) an episodic reinforcement learning problem with state space S = [0, 1,.., M)² and where M is its size. The state at period h in episode is s/, = (xh,, E S,, where of = o...,...,.4 is the horizontal position while di = 0, :,.... M the depth (vertical position). Its action (left,iight and time horizon length is
space is agent chooses an action right in period h H. then will receive a reward -0.1/M, which corresponds to "small cost"; If the agent successfully arrives at state (M, in period H = M, then it will receive reward 1, which corresponds to "big bonus"; otherwise, the agent will receive reward 0. The system dynamics are as follows: for period h < H, the agent's depth in the next period is always increased by 1, i.e, d'+1 = d2 + 1. For the agent's horizontal position, if a left, then 2/41 = max - 1,,0, ie., the agent will move left if possible. On the other hand, if af = right, then we have xh+1 = min(2f, + 1, M) with prob. 1 1/M and #/ = = with prob. 1/M. The initial state of this environment is fixed at state (0, 0). In this section, we fix the size of Deep Sea as M 10.
M. Its reward function is as follows: If the
Figure 1: (i) DeepSea Environment with start state in top left corner, and goal state in botiom right corner. (it) The map for the Maze environment.
Maze (Figure I (ii) is also an episodic reinforcement learning problem, which a variant of a maze problem proposed in D4RL (uu et al. p0200. To fit this problem into the finite-state framework of this paper, we discretize the locations in Figure (ii) into a 6 x 6 grid. Note that excluding the walls, there are 26 valid locations in the maze. We set the time horizon of this problem H 7. Since each state location-period
10

---

Published in Transactions on Machine Learning Research (10/2023)
pair, there 26 7 = 182 states in this problem. Moreover, we assume that this problem has fixed initial state: in each episode, the agent starts at the location denoted by the green dot in Figure (ii).
We assume that the action space for Maze is A = (left, right, up, down, stay). At each period h < H - 1, if the agent takes action left, and it also feasible to go left (i.e. the agent does not hit the wall going left), then the agent will successfully go left with probability 0.95, and fail to go left and stay at the same location with probability 0.05. On the other hand, if it is infeasible to go left, then the agent will stay the same location with probability 1. The state transitions under action right, up, and down are defined similarly, with the same success process/failurrs /failure probabilities. Finally, if the agent takes action stay, then it will stay at the same location with probability 1. The reward function of Maze is as follows: if the agent is at the target location, which is denoted by the red dot in Figure (īi), then the agent will receive a "big bonus' of reward 1; otherwise, the agent will incur a "small cost', which is reward -0.01.
In both environments, the offline datasct generated based on the expert's policy specified in Eq. (2 and we assume (()) (a constant) across all states. We set the size of the oflline dataset Do |aol Ki A S|. where K 2 0 is referred to data ratio.
Experimental results. We run the experiments on Deep Sea for T = 300 episodes, and run the experiments on Maze for T = 200 episodes. For both environments, the empirical cumulative regrets are averaged over 50 simulations. The experimental results are illustrated in Figure 2 and 3 as well as Figure in Appendix D.2
and Figure i in Appendix D.3
data_ data_ratio: ratio:
data ratio: 5.0
100
100
Regret(1)
agent
80
IRLSVI
PiRLSVI
URLSVI
60
60
0.1
100
100
0.1
10
100
B
Figure 2: Cumulaatve regret vs. 3 in Deep Sea.
data_ ratio: 1.0
data_ratio: rati:: 5.0
300
300
(e
agent
IRLSVI
200
200
P/RLSVI
UALSVI
100-
100
0.1
10
100
0.1
10
100
8
Figure 3: Cumulative regret vs. / in Maze.
Specifically, Figure plots the cumulattie regret on Deep Sea in the first T = 300 episodes as a function of the expert's deliberateness 3, for two different data ratios, Æ = l,and 5. There are several interesting obscrvations based on Figure [ (i) Figure 2 shows that iRLSVI and piRLSVI tend to perform much better than uRLSVI, which demonstrates the advantages of exploiting the offine dataset, and this improvement tends to be more dramatic with larger offline dataset. (ii) When we compare iRLSVI and piRLSVI, we note
11

---

Published in Transactions on Machine Learning Research (10/2023)
data ratio: 1.0
ratio: 5.0
100
95
(egret(T)
agent
90
(RLSVI
PIRLSVI
85
URLSVI
80
70
0.1
10
100
0.1
100
B
Figure 4: Robustness of iRLSVI to misspecification.
that their performance is similar when 8 is small, but iRLSVI performs much better than PiRLSVI when B is large. This is because when 8 is small, the expert's generative policy does not contain much information: and as 3 gets larger, contains more information and eventually it behaves like imitation learning and learns the optimal policy as B - co. Note that the error bars denote the standard errors of the empirical cunulative regrets, hence the improvements are statistically significant.
Similarly, Figure plots the cumulative regret on Maze in the first T 200 episodes as function of also for data ratios 1 and 5. Note that have obtained similar results in this experiment, and the improvements are also statistically significant.
Robustness to misspecification of 3. We also investigate the robustness of various RLSVI agents with respect to the possible misspecification B. In particular, we demonstrate empirically that in the Deep Sea environment with M = 10, with oflline dataset is generaled by an expert with deliberateness = 5, the iRLSVI agent is quite robust. to moderate misspecification. Here, the misspecified deliberateness parameter is denoted B. The empirical results are illustrated in Figure where the experiment is run for T 300 episodes and the empirical cumulative regrets averaged over 50 simulations.
Since uRLSVI and PiRLSVI do not use parameter 3. thus, as expected. their performance is constant over 3. On the other hand, iRLSVI explicitly uses parameter B. As Figure 4 shows, the performance of iRLSVI does not vary much as long as 3 has the same order of magnitude as 3. However, there will be significant performance loss when 3 too small, especially when the data ratio is also small. This makes sense since when 3 is too small, iRLSVI will choose ignore all the information about the generative policy and uvlnt reduces to PİRLSVI. Similar results be antieipated for the Maze environment and are omitted to save space.
6 Conclusions
In this paper, have introduced and studied the following problem: Given offline demonstration dataset from an imperfect expert, what is the best way to leverage it to bootstrap online learning performance in MDPs. We have followed a principled approach and introduced two algorithms: the ideal iPSRL algorithm, and the iRLSVI algorithm that is computationally practical and seamlessly bridges online RL and imitation learning in a very natural way. We have shown significant reduction in regret both empirically, and thcoret- ically as compared to two natural baselines. The dependence of the regret bound on some of the parameters (e.g., H) could be improved upon, and is a good direction for future work. In future work, we will also combine the iRLSVI algorithm with deep learning to leverage offline datascts effectively for continuous state and action spaces as well.
12

---

Published in Transactions on Machine Learning Research (10/2023)
References
Alekh Agarwal and Tong Zhang, Model-based RL with optimistic posterior sampling: Structural conditions and sample complexity. arXic preprint arXiv:2206.0766 2022.
Arthur Argenson and Gabriel Dulac-Arnold. Model-basod offline planning. arXiv preprint wrXiv:2008.05556 2020.
Peter Auer, Thomas Jaksch, and Ronald Ortner. Near-optimal regret bounds for reinforcement learning. Advances in neural information processing systems, 21, 2008.
Philip J Ball, Laura Smith, Nya Kostrikov, and Sergey Levine. Efficient online reinforcement learning with offline data. arXiv preprint or Xix:22302 02948, 2023.
Mark Beliaev, Andy Shih, Stefano Ermon, Dorsa Sadigh, and Ramtin Pedarsani. Imitation learning by estimating expertise of demonstrators. Proceedings of the 39th International Conference on Machine Learning, 162:1732-1748, 2022.
Tom Brown, Benjamin Mann, Nick Ryder, Melanie Subbiah, Jared D Kaplan, Prafulla Dhariwal, Arvind Neelakantan, Pranav Shyam, Girish Sastry, Amanda Askell, et al. Language models are few-shot learners. Advances in neural information processing systems, 33:1877-1901, 2020.
Christoph Dann, Mehryar Mohri, Tong Zhang, and Julian Zimmert. A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information Processing Systems, 34:12040-1200 2021.
Adrien EcofTet, Joost Huizinga, Joel Lehman, Kenneth Stanley, and Jell Clune. Go-explore: A new approach for hard-exploration problems. arXiv preprint arXic:1901.1099: 2019.
Adrien Ecoffet, Joost Huizinga, Joel Lehman, Kenneth O Stanley, and Jeff Clune. First return, then explore. Nature, 590)7547):580 586, 2021.
Damien Ernst, Pierre Geurts, and Louis Wehenkel, Tree-based batch mode reinforcement learning. Journal of Machine Learning Research, 6, 2005.
Kuan Fang, Patrick Yin, Ashvin Nair, and Sergey Levine. Planning to practice: Efficient online fine-tuning by composing goals in latent space. arXiv preprint arXiv:2205.08129, 2022.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data- driven reinforcement learning. arXie preprint arXiv:2004007219, 2020.
Scott Fujimoto and Shixiang Shane Gu. A minimalist approach to offline reinforcement learning. Advances neural information processing systems, 34:20132-200 20145, 2021.
Scott Fujimoto, David Meger, and Doina Precup. Off-policy deep reinforcement learning without exploration. In International conference on machine learning, pp. 2052 2062. PMLR, 2019.
Dibya Ghosh, Amurag Ajay, Pulkit Agrawal, and Sergey Levine. Offline RL policics should be trained to be adaptive. In International Conference on Machine Learning, pp. 7513 7530. PMLR, 2022.
Zhaohan Daniel Guo, Shantanu Thakoor, Miruna Pislar, Bernardo Avila Pires, Florent Altché, Corentin Tal- lec, Alaa Saade, Daniele Calandriello, Jean-Bastie Grill, Yunhao Tang, et al. Byol-explore: Exploration by bootstrapped prediction. Xrxiv preprint arXiv:2206.08 08333, 2022.
Nicklas Hansen, Yixin Lin, Hao Su, Xiaolong Wang, Vikash Kumar, and Aravind Rajeswaran. Mo- Dem: Accelcrating visual model-basod reinforcement learning with demonstrations. arXio preprint arXiv:2212.0550 2022.
Botao Hao and Tor Lattimore. Regret bounds for information-directed reinforcement learning. arXiv preprint arXiv:2206.0460 04640, 2022.
13

---

Published in Transactions on Machine Learning Research (10/2023)
Todd Hester, Matej Vecerik, Olivier Pietquin, Mare Lanctot, Tom Schaul, Bilal Piot, Dan Horgan, John Quan, Andrew Sendonaris, Ian Osband, et al. Deep Q-learning from demonstrations. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
Jordan Hoffmannn, Sebastian Borgeaud, Arthur Mensch, Elena Buchatskaya, Trevor Cai, Eliza Rutherford, Diego de Las Casas, Lisa Anne Hendricks, Johannes WelbI, Aidan Clark, et al. Training compute-optimal large language models. Xiv preprinl arXiv:2203.1553 15556, 2022.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimissm provably efficient for oflline RL? In International Conference on Machine Learning, pp. 5084-5096. PMT.R 2021.
Nya Kostrikov, Ashvin Nair, and Sergey Levine Offline reinforcement learning with implicit q-learning.
arXiv preprint arXic:2110.001 06166 2021.
Aviral Kumar, Aurick Zhou, George Tucker, and Sergey Levine. Conservative Q-learning for offline rein- forcement learning. Advances in Neural Information Processing Systems, 33:1179-1191, 2020.
Aviral Kumar, Joey Hong, Anikait Singh, and Sergey Levine. When should we prefer offline reinforcement learning over behavioral cloning? arXiv preprint ar arXiv:2204.05616 2022.
Seunghyun Lee, Younggyo Seo, Kimin Lee, Pieter Abbeel, and Jinwoo Shin. Offine--o-online reinforcement learning via balanced replay and pessimistic q-ensemble. In Conference on Robot Learning, pp. PMLR, 2022.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXa::20050016 643, 2020.
Ashvin Nair, Abhishek Gupta, Murtaza Dalal, and Sergey Levine. AWAC: Accelerating online reinforcement learning with offline datasets. arXiv preprint Xrv: 09359, 2020.
Thanh Nguyen-Tang and Raman Arora. Provably efficient neural offline reinforcement learning via perturbed rewards. Xiv preprinl or Xrx::2200 12780, 2023.
Ian Osband, Daniel Russo, and Benjamin Van Roy. (More) efficient reinforcement learning via posterior sampling. Advances in Neural Information Processing Systems, 26, 2013.
Ian Osband, Charles Blundell, Alexander Pritzel, and Benjamin Van Roy. Deep exploration via bootstrapped DQN. Advances in neural information processing systems, 29, 2016a.
Tan Osband, Benjamin Van Roy, and Zheng Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, pp. 2377 2386. PMLR, 2016b.
lan Osband, Benjamin Van Roy, Daniel Russo, Zheng Wen, et al. Deep exploration via randomized value functions. J. Mach. Learn. Res., 20(124):1-62, 2019.
Yi Ouyang, Mukul Gagrani, Ashutosh Nayyar, and Rahul Jain. Learning unknown Markov decision processes: A thompson sampling approach. Advances in neural information processing systems, 30, 2017.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell. Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:11702 11716, 2021.
Daniel Russo and Benjamin Van Roy. Learning to optimize via information-direeted sampling, Operations Research, 66(1):230-253 2018
Stefan Schaal. Learning from demonstration. Advances in neural information processing systems, 9, 1996.
Julian Schrittwicser, Thomas Hubert, Amol Mandhane, Mohammadamin Barckatain, Ioannis Antonogiou, and David Silver. Online and offline reinforcement learning by planning with a learned model. Advances in Neural Information Processing Systems, 27591, 2021.
14

---

Published in Transactions on Machine Learning Research (10/2023)
Yuda Song, Yifei Zhou, Ayush Sekhari, J Andrew Bagnell, Akshay Krishnamurthy, and Wen Sun. Hybrid RL: Using both offline and online data can make rl efficient. orXiv preprint or Xiv:2210.0077 2022.
Romal Thoppilan, Daniel De Freitas, Jamie Hall, Noam Shazeer, Apoorv Kulshreshtha, Heng- Tze Cheng, Alicia Jin, Taylor Bos, Leslie Baker, Yu Du, et al. Lamda: Language models for dialog applications. arXiv preprint ar arXe:2201.00233) 2022.
Daniil Tiapkin, Denis Belomestny, Daniele Calandriello, Éric Moulines, Remi Munos, Alexey Naunov, Mark Rowland, Michal Valko, and Pierre Ménard. Optimistic posterior sampling for reinforcement learning with few samples and tight guarantees. Xix preprint arXiv:2209. 14, 2022.
Masatoshi Uehara and Wen Sun. Pessimistic model-based oflline reinforcement learning under partial cov- erage. arXiv preprint arXiv:2107.06226, 2021.
Mel Vecerik, Todd Hester, Jonathan Scholz, Fumin Wang, Olivier Pietquin, Bilal Piot, Nicolas Heess, Thomas Rothörl, Thomas Lampe, and Martin Riedmiller. Leveraging demonstrations for deep reinforcement learn- ing on robotics problems with sparse rewards. arXiv preprint 1rXi::107.08811, 2017.
Andrew Wagenmaker and Aldo Pacchiano. Leveraging offline data in online reinforcement learning. arXiv preprinl ar xrx::221110023 2022.
Runzhe Wan, Branislav Kveton, and Rui Song. Safe exploration for efficient policy evaluation and comparison. arXiv preprint 1rX6::2202.1993, 2022.
Tsachy Weissman, Erik Ordentlich, Gadiel Seroussi, Sergio Verdu, and Marcelo J Weinberger. Inequalities for the L1 deviation of the empirical distribution. Hewlett- Hewlett-Packard Labs, Tech. Rep, 2003.
Zheng Wen, Doina Precup, Morteza Ibrahimi, Andre Barreto, Benjamin Van Roy, and Satinder Singh. On efficiency in hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 33: 6708 6718, 2020.
Tengyang Xie, Ching-An Cheng, Nan Jiang, Paul Minciro, and Alckh Agarwal. Bellman-consisteet pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-6683 2021a.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample- efficient offiine and online reinforcement learning. Advances in neural information processing systems, 34: 2021b.
Andrea Zanette and Rahul Sarkar. Information directed reinforcement learning. Tech. Rep., Technical report, Technical report, 2017.
15

---

Published in Transactions on Machine Learning Research (10/2023)
A Auxiliary Lemmas
Lemma A.1. Let X be the sum of L i.i.d Bernoulli random variables with mean (0. 1). Let g E (0,1),
then
P(X Σ (L) - exp - p))) < P(X 2 gL) - exp (-2 ))
i
Proof. Both inequalities can be obtained by applying Hoeffding's Inequality.
Lemma A.2. Let A and p be as in Assumptions 3.3 and 3.4 respectively and let
B = |log 3 log + log H 1) + log(A A 11)/AA)
For any B2 3 and N E N, there erists an estimator ** constructed from Du that satisfies
Lp²
Lp
F( **) < SH
exp
+ exp
18
36
The proof is available in Appendix C
B Proof of Lemma 3.1
Let 0h the environment sampled for the kth episode, and = be the optimal strategy under 0k Recall that Hy-1 is the data available to the iPSRL agent before the start of learning episode k. For notational simplicity, let (-) = P((1HH+11) and [&[1 = B(-1Hx-1). We first prove the following Lemma.
Lemma B.1. P(** # )² = P / x*) for all k 1.
Proof. Define f(x) x01 z²) is concave function. We have
P # π*) = E|P # x' = =E
Σ
Pa(#* = n, # 4m)
(11)
LHEII
E
(TP = x)))
(12)
E
Σ EI[f(PA(TT* x))||
Σ [(E =
(13)
LTE
(TP = 7))
E
=
Σ
Pi(#* = n, TT)
(14)
TEI
LEE
P(#* * x²)
(15)
3.1 Now we proceed to prove Lemma
Let J = Eo, 10 Th. (sh, an) + [s()))] denote the expected total reward under the environment 0 and
the Markov strategy æ. Define
Zy 1 j
(16)
Z: 0 1
(17)
Ig : 7 +
(18)
16

---

Published in Transactions on Machine Learning Research (10/2023)
First, note that Z Zz1y with probability 1, hence
EaIZa Zala]
Exl(Zx 2x] 1xx[[J] -
[x] Ex [J [ 0,
(19)
[x 1 (** (
(20)
where the last equality true since and 8 are independently identically distributed given Dg. Therefore, inequality, we have
we can write the Bayesian regret as E
E k= ZzIz]. By
T
I
T ( BiZA!
L
S
Σ
(21)
Using Lemma B.1
the first part can be bounded by
Σ E Σ
P( # x²) S TP(("' x**) =TT
(22)
The rest of the proof provides a bound on Σ B[Zg]
Let Th be the Bellman operator at time defined by Th, Vi+1(s) == o) (s ())(ss)((ss)
Using Equation (6) of Osband et al. (2013), we have
H-1 Σ
2/ Egg .
1T yg ay ((0-)4411)) The vg"" (+(-2))4++]
(23)
Sk, = =((k-1)(+hh and agsh = 0(k-1)H+h = For convenience, we write Ph = Po =
Recall that the instantaneous reward satisfies (s(s, E [0, 1]. We have
(T gh R Wh+1 (Sk.t)) -T Oe HIIP 8k,h, ak.A) (.(s,,,,,ak,,)) (
Therefore,
B < HE
T th 8
KR h+11 (8k,
- T. o
h+1 (s )
(24)
T-1
< H
Σ
Ph (- an
(25)
where used Cauchy-Schwartz incquality for the first incquality.
Following Osband et al. (203)), define N₂ (s a, h) E
k-1 1 ((era))))==( to be the number of times (s. a)
was sampled at step h in the first (k: 1) episodes.
Claim: For any k, h and any 8 > 0,
l2 2 log(1/8) Mrxx(NNsskon as.t, h1,, 1}
|||l ( ax PT (- a..l < 4E
+ 8(k 1)SA6
(26)
17

---

Published in Transactions on Machine Learning Research (10/2023)
Given the claim, we have
B
(27)
(2 (1g(1/6)
H
4E
+ Σ 8(k 1)5A6
(28)
max(XN&(s...) axa h),1}
1og 2)S 2 (1/0)
< 4
+ 11 (4T2
(29)
max { No (5k,,, 0n h),
[log log(l///o/ooo/ [
(max ag 1),
4
(30)
It remains to bound the expectation term in Eq. (30
We have
T
H
H1 ΣΣ
Nr(s..1-11
Σ
(max aR h), -)
Σ
(31)
max 1}
0=
h=0 #ES aEA
H-1
Σ
(2 lo (o,,,, - HSA(2 log(T))
(32)
(s..)))))
1 7 we have
Combining Eq.
30
and Eq. (22
setting ô =
E B[22]
(33)
$ 8HH.S5554000 S.((Olg 2) + log (1/)) |2+ log(T)) + 4
(34)
SA(loo 2)8 + 2 log(()) [2 log(T)) + SA
(35)
-( lo
(36)
Combining Eq.
21 E....
22
Eq.
36
conclude that
BAy = O(V log(1 + +T))
(37)
Proof of Claim. Let Pr (-Is, a) be the empirical distribution of transitions after sampling (s, a) at step h exactly n times. By the Ln concentration inequality for empirical distributions Weissman et 2003), we have
2 exp (-) nc²
Po- (-ss) Pf (-1s, a)ll > 22
(38)
for any 0. For 8 >>0 0, define (),,0) (2 2)5 ++ log(1/8) have max(n.1)
Pe- (1 - Ph (-1s, E(n, s 8.
(39)
Define 1 (-1s,,)) u) to be the empirical distribution of transitions after sampling (8, a) at step in the first. k episodes. Define
[|P Q (0: [|Ps (-)s.)) PP a) h)), As V UsES, A}
18

---

Published in Transactions on Machine Learning Research (10/2023)
Then, we have
P(O" $ () P In E - &
(40)
E E (1s, P (11s,a))lf > E(n,
(41)
- (k - 1)SA
(42)
Since 0" and 6 are i.i.d given DR, and the random set 6 is measurable to Dr, we have P(6"
P(Oh & ())) Therefore have
E PA (- (-Isk akAA (- a2 ax
(43)
$ E [IPR (-1 IsE.h aea) P, A 1| (o- x
(44)
+ E || P (-)) (M|8,, ax ((00)0)) + (1(0000))) ]
(45)
(S ak,, + (P(0' ²%) p(O & 6%)) s ak,, + 8(A: - 1)8A6
(46)
(47)
C Proof of Lemma A.2
Proof. For convenience, write Po(.) TP(-10))
Define the event En,a (ūn. f aj (5n,ni 0)}, i.e. in the n-th round of demonstration, the expert did not take the optimal action at time h. Given the expert's randomized policy o, we have
I6 (En,nil,n, 1n)
(48)
(49)
1 La exp( (5n,hs 0))
(50)
asta (1)
< (A 1) exp( 3DD =: Kg.
(51)
Define Kg (H 1)8g. Then 3 2 3 means that Kg p/33.
Consider each (h, s) {0, 1...,..... . 1} S, conditioning on there are cases:
If (n 0) > 0 then
2 Po (3 5) (1- ko) pp(s:)) (1-Kg)p 2 3p.
(52)
The first inequality in Eq. 52 can be established via induction on h: First observe that Pe = 8) = po 0) for all s E S by definition. Suppose that we have proved the statement for time h. i.c. Fe(En,n = s) 2 (1 - (1- Pn pm (s; 0) for all s S. Then we have
(s:1('';0) Σ
Po(s' Pa('"'s, (s
(53)
#ES
= =s) 2 Σ
( (s; 0) ( (s: = s)
(54)
#ES
Σ
(1 Kg) Pa(s' 8.
=)
(55)
#ES
2
Σ
(1
Rg
h+1 Po (s:
(56)
*E8
19

---

Published in Transactions on Machine Learning Research (10/2023)
The statement for h + then follows by comparing Eq. [53 and Eq. 56 establishing the induction step.
(s(s;; 0) = O, then if Su,h 8, the expert must have chosen some action that was not optimal before time in the n-th round of demonstration. We conclude that
h-1 Po(E h=1
Po(En,h = = Po
U h=1
m
S Sng S 3
(57)
The above argument shows that there's a separation probability between two types state and time index pairs under the expert's policy (²)) the ones that are probable under the optimal policy =*( and the that not. Using this separation, we will proceed to show that when L is large, we distinguish the two types of state and time index pairs through their appearance counts in Do. This will allow to construct good estimator of x..
Define * to be the estimator of x" constructed with == p/2.. If n" + π, then either one of the following cases happens
There exists an (s, h)) S (0, (0,1,..,, -- pair such that pa (s; 0) > 0 but (x( < <T;
There exists an (s, h)
(0, 1, ,H 13 pair such that pa (s: 0) = but N₂ (s) 2 8L;
There exists an hs E S x {0, --....,-111 -H13 pair such that (s; 0) > 0 and Ns(s) 2 5L, but (;; 0) = at (s; 0) # arg max, N, - *s),
Using union bound, have
Po(m #*)
(58)
Σ
(s( < 88)+
Σ Po(Nn()) 2 8L)
(59)
(#:0)=
(s.b):pa -=:0)=0
+
Σ
Po(N)() 2 (s; arg (s,
(60)
(s:))=p
Let Bin(M,9) 9) denote a binomial random variable with parameters M and E [0, 1]. Notice that conditioning on 0, each (s) is binomial random variable with parameters and (o,x(s) Pa s).
Using equation 52 and Lemma A.
conclude that each term in the first summation of equation 60 satisfies
Po (N. 5L) < ((, < (p/2)L)
(61)
Lp²
s eex((22(pp6)) exp
(62)
18
Using equation 57 and Lemma satisfies
A.1
conclude that each term in the second summation of equation 60
(a) 2 8L) < P(Bin(L, R3)) < (p/2)L)
(63)
2 k3) ks)² )) exp
Tp²
I exp
-2L
(64)
18
20

---

Published in Transactions on Machine Learning Research (10/2023)
Again, using Lemma A.1 each term in the third summation of equation 60 satisfies
Po(N)(s) 2 ,L, ag 0) + arg max Na (s.
(65)
(s;a)((;0)) + arg max (a(5, a) (s) 2 6L)
(66)
I (s(NN(()) - (N. 0)) 2 (s) 2 Ni((s 2 6L) 22 No) 8L)
(67)
(68)
(N 1/3) 2 Ns(s)/2 Ns 2 6L)
(69)
(s)ss
I Eg
exp
(n(s)) OL
(70)
18
8L
Lp
S exp
exp
(71)
18
36
Combining the above we obtain
Lpp
Lp
Po(a"
#**) S SH
exp
+ exp
(72)
18
36
D Empirical Results
D.1 Pseudo-codes for RLSVI agents
In this appendix, we provide the pseudo-codes for iRLSVI, PiRLSVI, and uRLSVI used in experiments Section 5 which are illustrated in Algorithm 2 and 8 Note that all three agents are tabular RLSVI agents with similar posterior sampling-type exploration schemes. However, they differ in whether not and how to exploit the offline dataset. More precisely, they differ in use of the offline dataset Do when computing the RLSVI loss CRISVI (see Algorithm and 3), and if the total loss includes the loss associated with the
expert actions ĆIR (see Algorithm Table summarizes the differences. In all experiments in this paper,
we choose the algorithm parameters of 1, 0.1, and B 20.
agent uRLSVI
use Do in CRISVI?
include LIR?
No
No
piRLSVI
Yes
No
iRLSVI
Yes
Yes
Table 1: Differences between iRLSVI, piRLSVI, and uRLSVI.
D.2 More empirical results on Deep Sea
In this appendix, we provide more empirical results for the Deep Sea experiment described in Section 5 Specifically, for Deep Sea with size M 10, data ratio x = 1,5, and expert's deliberateness B = 1, 10, we plot the cumulative regret of iRLSVI, piRLSVI, and uRLSVI as function of the number of episodes for the first. T 300 episodes. The experiment results are averaged over 50 simulations and illustrated in Figure
As we have discussed in the main body of the paper, when both data ratio and the expert's 's deliberateness B are small, then there are not many oflline data and the expert's generalive policy is also not very informative. In this case, iRLSVI, PİRLSVI, and uRLSVI perform similarly. On the other hand, when the data ratio x is large, 1RLSVI and PiRLSVI tend to perform much better than uRLSVI, which does not use the offline dataset.. Similarly, when the expert's deliberateness 3 is large, then the expert's generative policy informative. this case, iRLSVI performs much better than PiRLSVI and uRLSVI.
21

---

Published in Transactions on Machine Learning Research (10/2023)
Algorithm 2 RLSVI agents for numerical experiments
algorithm parameter og o² > O, deliberateness paramoter / > 0, offline datasct Do, offline buffer size B, agent lype agent
Input:
if agent uRLSVI then initialize data buffer D as an empty set
else
initialize data buffer D +- Do end if
for t = 1........ do
sample state-action value function Q' backwardly based on Algorithm 3 sample initial state s for h = 0,..., H do
take action of ~ Unif (arg max, (sh. a))
observe (5)+ append (s ans h, r the data buffer
end for end for
Algorithm sample Q'
Input: algorithm parameler o o² >> 0, deliberateness parameler 3 > 0, offline dataset Do, data buller D, offline buffer size B, agent type agent
set @11+1 +-
for h H, H 1,... do
Let Q S|S)i|Å| denote the decision variable, then we define the RLSVI loss function
2 + 20 (((s,a) (r wa) max 2i (s')
ÉRLSVI(Q) =
Σ d=(s,a.h'' M) rEE
11Q Quiior I
where for each data entry d = (s, a, s', E D, wa is ii.d. sampled from N(0, Each element in Quiior @R [A] is i.i.d. sampled from N(O, ag) and || denotes the Frobenius norm.
if agent iRLSVI then
sample buffer of B offiine data tuple, B, without replacement from the offiine dataset Do define B, {s, a, s,,,, E B: h' = h define the loss function associated with expert actions as
(u.(Q)= = Σ
log Σ exp (3Q(s,b)) (s(
(s.,,',,' ,BB,
choose Q4 E arg ming [CRLSVI(Q)+ (2)
else
choose Q4 E arg min (Q)
end
end for
Return Q' = (Qt, Qq....
22

---

Published in Transactions on Machine Learning Research (10/2023)
beta: 1.0
beta: data ratio: 5.0
data data_ration ratio: 1.0
100
100
75
75
50
50
cumulative regret
25
0
agent
100
200
300
100
200
300
IRLSVI
beta: 10.0
beta: 10.0
pIRLSVI
data ratio: 1.0
data ratio: 5.0
100
100
URLSVI
75
50
50
25
0-
100
200
300
100
200
300
t
Figure 5: Cumulative regret vs. number of episodes in Deep Sea.
D.3 More empirical results on Maze
In this appendix, we provide more empirical results for the Maze experiment described in Section Specif- ically, for the Maze environment, data ratio 1,5, and expert's deliberateness B 1, 10, plot the cunulative regret of iRLSVI, PiRLSVI, and uRLSVI
function of the number of episodes / for the first T = 200 episodes. The experiment results are averaged over 50 simulations and are illustrated in Figure 6 We have observed similar experiment results as the Deep Sea experiment.
23

---

Published in Transactions on Machine Learning Research (10/2023)
beta: 1.0 data_ratic
beta: 1.0 data_ration
300
300
200
200
100
100
cumulative regret
0
agent
50
100
50
100
IRLSVI
beta: 10.0
beta: 10.0
PIRLSVI
data_ _ata_ratio: 1.0
data_ratio:
data ratio: 5.0
URLSVI
300
300
200
100
100
0-
0
50
100
150
200
50
100
150
200
Figure 6: Cumulative regret vs. number of episodes in Maze.
24


Reviews:
[{"review_id": "Dvz3H9qIbb", "reviewer": "Reviewer_scp5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n\nThe proposed algorithms are interesting and consist of intuitive modifications to their online counterparts.\n\nThe final algorithms in Eqs. 10 and 11 mirror what has been seen in the empirical literature, and their derivations provide another framework for understanding the success of existing work.\n\nThe theory results look reasonable upon a light reading, though the relationship to PSRL and RLSVI is not made explicit.\n\n### Weaknesses\n\nThe paper makes claims in multiple places about being the first work that addresses this setting. In some places those claims are more tightly constrained than in others, but some versions of the statement are patently false. The abstract is perhaps the worst offender, stating that “Our algorithm bridges online RL and imitation learning for the first time.” There are a variety of algorithms in the deep RL community which do this in different ways; see [1] for a particularly well-known example of work which does this algorithmically, or [2] for one which studies this setting. A similar claim appears at the end of the introduction.\n\nIt was not precisely clear to me what information the agent had about the behavior policy in each of these settings and where that information was used. Does the agent know fully $(\\beta, \\lambda)$? Just $\\beta$? In the first paragraph of section 3, it notes that $\\beta$ is known to the expert — was that meant to be, known to the agent? \n\n[1]: Fujimoto, S., & Gu, S.S. (2021). A Minimalist Approach to Offline Reinforcement Learning. *ArXiv, abs/2106.06860*.\n\n[2]: Kostrikov, I., Nair, A., & Levine, S. (2021). Offline Reinforcement Learning with Implicit Q-Learning. *ArXiv, abs/2110.06169*.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This work brings the posterior sampling reinforcement learning (PSRL) and randomized least-squares value iteration (RLSVI) algorithms to the online fine-tuning setting, where the agent has access to a dataset of trajectories collected *a priori* by a behavior policy. It proposes “informed” variants iPSRL and iRLSVI, which leverage this offline dataset and knowledge of the behavior policy. These algorithms show clear benefits over the original algorithms in this setting.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "The claims about this work being the first to bridge online and offline RL, or online RL and imitation learning, need to either be removed or made substantially more specific.\n\nThe second paragraph of the introduction says that offline RL suffers from a “sim2real” problem. I think this was meant to be “distribution shift” or “compounding errors”.\n\nThe notation is quite dense and slow to read. I wonder if the main body of the manuscript might be made clearer by simpler and less precise notation, reserving multiple super/subscripts (e.g. the tuple $(s_h^l, \\tilde{a}_h^l, \\check{s}_h^l, \\tilde{\\mathcal{E}}_h^l)$, page 7) for the appendix where possible. It’s fine if this is not feasible.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "DESy1mkdhe", "reviewer": "Reviewer_TwXf", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The writing in this paper is unclear and leaves out a lot of relevant and important details. It is often unclear whether contributions are novel or imported from prior work. This makes it difficult to judge both the strengths and weaknesses of the paper. This type of paper is not my area, so consider my confidence to be low. \n\n- (Weakness) The claim that this is the first paper to bridge online RL and imitation learning seems very overstated. There are many papers in the Learning from Demonstrations literature (LfD) which do so. There are many papers in the offline RL literature which combine RL and imitation. \n\n- (Weakness) The claim that \"we have introduced and studied a new problem: Given an offline demonstration dataset from an imperfect expert, what is the best way to leverage it to bootstrap online learning performance in MDPs\" seems very overstated. It's unclear to me, if the authors are implying that this is distinct from the offline finetuning setting because there is no offline pre-training, but this seems pedantic at best, as many of these methods are capable, but pre-train as this is logical to do when given offline data. \n\n- (Weakness) The paper seems heavily based on PSRL and RLSVI but are not described or described not in detail. Citations for RLSVI point to several distinct papers, and seemingly (based on the loss function in 4.2) do not refer to the \"least squares\" (the LS in RLSVI) version. This makes it hard to understand what the contributions of the paper are.\n\n- (Weakness) Algorithmic details are missing or out of order. Corollary 3.2 refers to the regret of the iPSRL algorithm, which is only described by eqn (3). There is no description of how the policy is determined. Its possible the policy of iPSRL is determined on page 7, but this is never stated clearly. iRLSVI seems to make use of Remark 4.1/4.2 but any exact details are omitted in the paper. \n\n- (Weakness) Remark 4.1 suggests the authors estimate $\\beta$ by considering the entropy of the dataset. In practice this assumption is completely unrealistic, as the behavior policy could be deterministic, or the expert could be very stochastic.\n\n- (Weakness) The experimental results are unsurprising/meaningless because they do not compare against any competitive baselines. It is obvious that giving more data/more information would improve results. The authors should compare with RLVSI with offline data (and without their adjustments) as well as other offline RL methods, particularly ones used for offline+finetuning.\n\n- (Weakness) There are missing details for reproducibility of the experimental results when regarding the algorithmic details of the method and baselines. I realize this is not the main contribution of the paper, but these details are easy to include and there's no reason to hold theoretically grounded papers to a lower standard on reproducibility. \n\n- (Strength) As a tool for analysis (both theoretical and empirical), the formulation of the expert is a useful contribution, as it is more meaningful then just expert + some noise level. \n\n- (Strength) Theoretical contributions seem interesting but it is unclear to me what is novel over PSRL and RLSVI due to clarity challenges. Hopefully this will be more clear with revisions. \n\nMinor:\n\n- In introduction: \"This often suffers from the sim2real problem\", sim2real refers to the problem from moving from simulation to real world environments. This should be \"distribution shift\" or similar terms since the authors refer to the challenge from moving from offline to online. \n- PSRL/RLSVI are motivated heavily by exploration/optimism, it was unclear to me how that motivation played into the variants proposed in this paper. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The authors introduce a method for learning from an offline dataset while learning online. They first describe a method with unrealistic assumptions but strong regret guarantees, then introduce a more practical approximation. The agent is tested in the Deep Sea environment. ", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See listed weaknesses.", "broader_impact_concerns": "No concerns. A broader impact statement is not needed. ", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "yDweGD4b9s", "reviewer": "Reviewer_UsQL", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength:\n\n1. The paper provides a regret guarantee for both PSRL and iPSRL, which shows how the prior information in offline demonstration dataset can help improve the regret.\n2. The paper also provides an approximate algorithm that can be efficiently implemented.\n3. The paper interprets the new loss as a combination of the loss for online learning and that of imitation learning.\n\nWeakness: \n\n1. I’m confused how Lemma 3.1 is related to the results in the prior work, since PSRL is a standard algorithm with a good amount of theoretical analysis. A more detailed discussion on related work is needed here. \n2. It’s unclear how large the entropy term can be in both Lemma 3.1 and Corollary 3.2. Since the only improvement is in the entropy term, it’s better to have some examples to see when the first term in the minimum can be smaller than the second term in the regret bound of Corollary 3.2.\n3. It’s better to see some discussions on the tightness of Lemma 3.1 and Corollary 3.2. Otherwise one cannot say that iPSRL improves over PSRL since the lower bound for PSRL is missing. \n4. I wonder how the proposed algorithm compares with the simplest baseline: one first trains a policy purely from offline demonstration dataset using imitation learning (and also learn a Q function using max entropy RL), then explores using Q-learning, SAC, or policy-based algorithms. It would be great to see theoretical and empirical comparisons. I understand that the Bayesian algorithm is usually not comparable in theory with existing value-based algorithms since the assumptions are quite different. But an empirical study would be greatly appreciated.  Since such a baseline is the most common practice in the real world, it would be great if the authors can demonstrate the superiority of the proposed algorithm over it. It is also better to see experiments on practical datasets like D4RL.\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies the problem of how one leverages the offline demonstration dataset from an imperfect expert to improve online learning. The authors propose Informed Posterior Sampling-based RL (iPSRL), which incorporates the prior information learned from offline demonstration into the existing PSRL algorithm. Experimental results show that the proposed algorithm improves over the partially informed and uninformed PSRL algorithms.\n", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I think the contribution of the work is not enough for publication on TMLR. However, I think the following change will significantly improve the contribution:\n1. Include lower bounds for both algorithms, and provide analysis to improve the exponential dependency of H as the authors mentioned in the remark.\n2. Add more theoretical and empirical results that compare the proposed algorithm with the standard baseline, which first trains a policy and value function from the offline demonstration dataset, and then explores based on it using Q-learning, SAC, or policy-based algorithms.\n3. Add empirical results on D4RL dataset. \n", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: While the theoretical analysis is good, the empirical analysis is a bit weak, i.e., with only an oversimplified game, tabular case, without baselines. The authors are suggested to enhance empirical studies, e.g.,
- Conduct experiments on D4RL environments. While theoretical analysis with function approximation indeed needs more effort, it will greatly strengthen this paper. Furthermore, even if without theoretical analysis, it is also valuable to conduct experiments over this more challenging setting (continuous/very large state and action space problems)
- Or conduct experiments on several other tabular environments. Although those environments might not be as valuable as D4RL environments, they will still enhance the empirical studies in the paper. 
Decision: Accept (poster)