Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning
Authors: Gen Li
Wenhao Zhan
Jason D. Lee
Yuejie Chi
Yuxin Chen
Venue: NeurIPS 2023 poster (2023)
Keywords: reward-agnostic reinforcement learning
policy finetuning
offline reinforcement learning
online reinforcement learning

Abstract: This paper studies tabular reinforcement learning (RL) in the hybrid setting, which assumes access to both an offline dataset and online interactions with the unknown environment. A central question boils down to how to efficiently utilize online data to strengthen and complement the offline dataset and enable effective policy fine-tuning. Leveraging recent advances in reward-agnostic exploration and offline RL, we design a three-stage hybrid RL algorithm that beats the best of both worlds --- pure offline RL and pure online RL --- in terms of sample complexities. The proposed algorithm does not require any reward information during data collection. Our theory is developed based on a new notion called **single-policy partial concentrability**, which captures the trade-off between distribution mismatch and miscoverage and guides the interplay between offline and online data.

Reward-agnostic Fine-tuning: Provable Statistical Benefits of Hybrid Reinforcement Learning
Gen Li' CUHK
Wenhao Zhan' Princeton
Jason D. Lee Princeton
Yuejie Chi CMU
Yuxin Chen UPenn
Abstract
This paper studies tabular reinforcement learning (RL) in the hybrid setting, which assumes access both offline dataset and online interactions with the unknown environment. A central question boils down to how to efficiently utilize online data strengthen and complement the offline dataset and enable effective policy fine-tuning. Leveraging recent advances
reward-agnostic exploration and of- fline RL, design a three-stage hybrid RL algorithm that beats the best of both worlds - pure offline RL and pure online RL - in terms of sample complexities. The proposed algorithm does require any reward information during data col- lection. Our theory is developed based on a new notion called single-policy partial concentrability. which captures the trade-off between distribution mismatch and miscoverage and guides the interplay between offline and online data.
1 Introduction
As reinforcement learning (RL) shows promise in achieving super- super-human empirical success across diverse fields (e.g., games (Silver et al., 2016; Vinyals al., 2019; Berner al., 2019; Mnih et al., 2013), robotics (Brambilla et al., 2013), autonomous driving (Shalev-Shwartz et al., 2016)), the- oretical understanding about RI. has also been substantially expanded, with the aim of distilling fundamental principles that can inform and guide practice. Among all sorts of theoretical questions being pursued, how to make the best use of data emerges as question of profound interest for problems with enormous dimensionality.
There are at least two mainstream mechanisms when it comes to data collection: online RL and offline RL. Let us briefly describe their attributes and differences as follows.
Online RL. In this setting, an agent learns how to maximize her cumulative reward through interac- tion with the unknown environment (by, say, executing sequence of adaptively chosen actions and utilizing the instantaneous feedback of the environment). Given that all information about the envi- ronment is obtained through real-time data collection, the main challenge lies in how (optimally) manage the trade-off between exploration and exploitation. Towards this, one popular approach advertises the principle of optimism in the face of uncertainty - c.g., employing upper confidence bounds during value estimation to guide exploration - whose effectiveness has been shown for both the tabular
(Auer and Ortner, 2006; Jaksch al., 2010; Azar al., 2017: Dann et al., 2017: Jin et al., 2018 8; Bai et al., 2019; Dong et al., 2019; Zhang et al., 2020b; Ménard et al., 2021 1b; Li et al., 2021b) and the case with function approximation (Jin et al., 2020b; Zanette et al., 2020: Zhou al., 2021a; Li et al., 2021a; Du et al., 2021: Jin et al., 202 la: Foster et al., 2021: Chen et al., 2022b).
Offline RL. In contrast, offline RL assumee access to a pre-collected dataset, without given permis- sion to perform any further data collection. The feasibility of reliable offline RI. depends heavily
'The first two authors contributed equally.
Corresponding author
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

on the quality of the dataset at hand. A central challenge stems from the presence of distribution shift: the distribution of the offline dataset might differ significantly from that induced by the target policy. Another common challenge arises from insufficient data coverage: nontrivial fraction of the state-action pairs might be inadequately visited in the available dataset, thus precluding one from faithfully evaluating many policies based solely on the offline dataset. To circumvent these obsta- cles, recent works proposed the principle of pessimism in the face of uncertainty, recommending caution when selecting poorly visited actions (Liu et al., 2020; Kumar et al., 2020; Jin et al., 202 lb; Rashidinejad et al., 2021; Uehara and Sun, 2021; Li et al., 2022; Yin et al., 2021; Shi et al., 2022; Cai et al., 2022). Without requiring uniform coverage of all policies, the pessimism approach proves effective as long as the so-called single-policy concentrability is satisfied, which only assumes ade- quate coverage over the part of the state-action space reachable by the desirable policy.
In reality, however, both mechanisms above come with limitations. For instance, even the single- policy concentrability requirement might be too stringent (and hence fragile) for offline RL, as it is not uncommon for the historical dataset miss a small yet essential part of the state-action space. Pure online RL might also be overly restrictive, given that there might be information from past data that could help initialize online exploration and mitigate the burden of further data collection.
All this motivates the studies of hybrid RL, a scenario where the agent has access to an offline dataset while, in the meantime, (limited) online data collection is permitted well. Oftentimes, this scenario is practically not only feasible but also appealing: on the one hand, offline data provides useful information for policy pre-training, while further online exploration helps enrich existing data and allows for effective policy fine-tuning, As a matter of fact, multiple empirical works (Rajeswaran al., 2017: Vecerik et al., 2017; Kalashnikov et al., 2018; Hester et al., 2018; Nair al., 2018, 2020) indicated that combining online RL with offline datasets outperforms both pure online RL and pure offline RL. Nevertheless, theoretical pursuits about hybrid RL, are lagging behind. Two recent works Ross and Bagnell (2012); Xie et al. (2021b) studied restricted setting, where the agent is aware of a Markovian behavior policy (a policy that generates offline data) and can either execute the behavior policy or any other adaptive choice to draw samples in each episode; in this case, Xie et al. (2021b) proved that under the single-policy concentrability assumption of the offline dataset, having perfect knowledge about the behavior policy does not improve online exploration in the minimax sense. Another strand of works Song et al. (2022); Nakamoto et al. (2023); Wagenmaker and Pacchiano (2022) looked at more general offline dataset and investigated how to leverage offline data in online exploration. From the sample complexity viewpoint, Wagenmaker and Pacchiano (2022) studied the statistical benefits of hybrid RL in the presence of linear function approximation; the result therein, however, required strong assumptions on data coverage (i.e., all pll-policy concentrability) and fell short of unveiling provable gains in the tabular case (as we shall elucidate momentarily). In light of such theoretical inadequacy in previous works, this paper is motivated to pursue the following question:
Does hybrid RL allow for improved sample complexity compared to pure online or offline RL in the labular case?
1.1 Main contributions
We deliver an affirmative answer to the above question. Further relaxing the single-policy concen- trability assumption, we introduce a relaxed notation called single-policy partial concentrability (to be made precise in Definition 2), which (i) allows the dataset to miss fraction of the state-action space visited by the optimal policy and (ii) captures the tradeoff between distribution mismatch and lack of coverage. Armed with this notion, our results reveal provable statistical benefits of hybrid RL compared with both pure online and offline RL. The main contributions are summarized below.
A novel three-stage algorithm. We design a new hybrid RL algorithm consisting of three stages. In the first stage, we obtain crude estimation of the occupancy distribution d" w.r.t. any policy π as well as the data distribution doff of the offline dataset. The second stage performs online exploration; in particular, we execute one exploration policy to imitate the offline dataset and another one to explore the inadequately visited part of the unknown environment, with both policies computed by approximately solving convex optimization sub-problems. Notably, these two stages do not count on the availability of reward information, and thus operate in reward-agnostic manner. The final stage then invokes the state-of-the-arr offline RL algorithm for policy learning, on the basis of all data we have available (including both online and offline data).
2

---

Computationally efficient subroutines. Throughout the first two stages of the algorithm, we need to solve couple of convex sub-problems with exponentially large dimensions. In order to attain paradigms to solve the sub-problent
computational efficiency, we design efficient Frank-Wolfe-te approximately, which run in polynomial time. This plays a crucial role in ensuring computational tractability of the proposed three-stage algorithm.
Improved sample complexity. We characterize the sample complexity of our algorithm (see Theo- rem 1), which provably improves upon both pure online and offline RL. On the one hand, hybrid RL achieves strictly enhanced performance compared to pure offline RL (assuming the same sample size) when the offiin data falls short of covering all state-action pairs reachable by the desired pol- icy. On the other hand, the sample size allocated to online exploration in our algorithm might only need to be proportional to the fraction a of the state-action space uncovered by the offline dataset, thus resulting in sample size saving in general compared to pure online RL (a case with = 1).
Notation. Let us also introduce several useful notation. For integer m > O, we let [m]] represent the set (1,... m). For any set B, we denote by 8 its complement. For any policy mo, we let 1 mp II + {0, be an indicator function such that 1. (T) = 1 lf = To and 1 xo( (T) = 0 otherwise, For any finite set A. we denote by ((A) the probability simplex over A. Letting X' = (S, A, H, _ 4). we use the notation f(X) Ogg(Z)) or f(X) I g(X) to indicate the existence of a universal
constant Ci > 0 such that f < Cig. the notation f(x) Z g(t) to indicate that g(X) (x)))),
and the notation f(x) x g(X) to mean that f(x) S g(x) and f(x) Z g(X) hold simultaneously.
The notation Ō(-) is defined in the same way as O()) except that it hides logarithmic factors.
2 Preliminaries and problem settings
Episodic finite-horizon MDPs. We study episodic finite-horizon Markov decision processes with S states, A actions, and horizon length H. We use M = (S, H, {Pr } h= = {rr [r>H) to represent such an MDP, where S = [S] and A [AA] represent the state space and the action space, respectively. For each step h E [H] we let PA. : S x A + ASS) represent the transition probability this step, such that taking action a in state from the distribution (. s, a): throughout the paper, we often employ the shorthand notation Ph.s.a == Ps (-|ss, u). Another ingredient the reward function specified by rh : x A - [o, 1] at step h;; namely, the agent will receive an immediate reward rx rx a) upon executing action in state 8 at step It is assumed that the reward function is fully revealed upon completion of online data collection. Additionally, assume throughout that each episode of the MDP starts from initial state independently generated from some (unknown) initial state distribution E A(S).
step yields a transition to the next state drawn
A time-inhomogencouu Markovian policy is often denoted by π = {mA) I with TT : - A(A), where TT. (- s) characterizes the (randomized) action selection probability of the agent in state at step h. If π is a deterministic policy, then we often abuse the noation and let nV (s)s) represent the action selected in state s at step h. We find it convenient to introduce the following notation:
π == the set of all deterministic policies.
(1)
We also need to handle mixed deterministic policies (i.e., each realization of the policy is randomly drawn from a mixture of deterministic policies). A mixed deterministic policy n mixed is denoted by
mixed
Σ ((T) = Ex~ [T]
for some μ E A(II).
Moreover, for any policy we define its associated value function (resp. Q-function) as follows, representing the expected cumulative rewards conditioned on an initial state (resp. an initial state- action pair):
V (s) = Ex Enengwga (s) 8h =
VsES;
@7 = Ex Emangwsn Phr(s, a) 8n = 8, 8, = a
V(s,a) ESXA
Here, the expectation is over the length- H sample trajectory (81, 01, 82, ..,..., 8H, an) when exe- cuting policy æ in M, where sy (resp. as) denotes the state (resp. action) at step h of this trajectory.
3

---

When the initial state is drawn from we further augment the notation and denote
(p) Be-p (s)(
Importantly, there exists at least one deterministic policy, denoted by nt throughout, that able to maximize (s) and Q2% (s, a) simultancously for all (h, s, a) E [H] x S x A: namely,
(+) = V (s) max Vi((()
(= == Q (s, a) max Q% (s, ((s,a)
Moving beyond value functions and Q-functions, we would like to define, for each policy x, the associated state-action occupancy distribution d' = [d%] IshSH such that
dR (8, a) == P(s; =, on a T), a( E S x A [H];
in other words, this is the probability of the state-action pair (8,a) S x A being visited by a at step h. We shall also overload d' represent the state occupancy distribution such that
(s) = Σ aEA (. a) = P(sn = s x),
V(s, h) E S x [H].
(3)
Given that each episode always starts with state drawn from p. it is easily seen that di p(s) for any policy π and any S.
Sampling mechanism. We consider a hybrid RL setting that assumes access to historical dataset as well as the ability to further explore the environment via real-time sampling, as detailed below.
Offline data. Suppose that we have available a historical dataset (also called an offline dataset)
Doff = JigAgKo"
(4)
containing kfff sample trajectories each length H. Here, the k-th trajectory in Doff denoted by (s o.ff
rk.off
a k.off
k.off ,a k.off). S
(5)
where s k.off and dn assumed that each trajectory y* , is drawn independently using policy of which takes the form of mixture of deterministic policies
of indicate respectively the state and action at step this trajectory ,,,ff
off
E
[
with off E A(II.
(6)
Note that the learner only has access to the data samples but not of Throughout the paper, we use doff ( Jishh represent the occupancy distribution of this offline dataset such that
of k.off da (s,a) a) == (s an
a)), Vs, a, h) E S A [H].
Online exploration. In addition to the offfine dataset, the learner is allowed to interact with the unknown environment and collect more data real time, in the hope of compensating for the insuf- ficiency of the pre-collected data at hand and fine-tuning the policy estimate. More specifically, the learner is able sample Koon trajectories sequentially. each sample trajectory,
the initial state is generated independently from an (unknown) distribution E A(S);
the learner selects policy to execute the MDP, obtaining sample trajectory length H.
The total number of sample trajectories is thus given by
== Koff
Kron
Concentrability assumptions for the offline dataset. To quantify the quality of the historical dataset, prior offline RL literature introduced the following single-policy concentrability coefficient based on certain density ratio interest; see, e.g., Rashidinejad et al. (2021); Li et al. (2022).
Definition (Single-policy concentrability). The single-policy concentrability coefficient C* of the offline dataset Doft is defined as
dF (s. a) 2 (s, a)
C*
max (Ex
(9)

---

In words, C* employs the loc -orm of the density ratio d= /d to capture the shift of distributions between the occupancy distribution induced by the desired policy x* and the data distribution at hand. The terminology "single-policy" underscores that Definition 1 only compares the offline data distribution against the one generated by a single policy x², which stands in stark contrast to other all-policy concentrability coefficients that are defined to account for all policies simultaneously.
One notable fact about Definition is that: for C be finite, the historical data distribution needs to cover all state-action-step tuples reachable by π². This requirement is, in general, inevitable if only the offline dataset is available; see the minimax lower bounds in Rashidinejad Li et al. (2022) for more precise justifications. However, a requirement of this kind could be overly stringent for the hybrid setting considered herein, as the issue of incomplete coverage can potentially be overcome with the aid of online data collection. In light of this observation, we generalize Definition to account for the trade-offs between distributional mismatch and partial coverage.
al. (2021);
Definition 2 (Single-poliey partial concentrability). For any a E [0. 1}, the single-policy partial concentrability coefficient (a) of the offline dataset Doff is defined as
Tf (s,a)
H E Ello).
(*( = min
max max IShS (s.0)E9,
foff (8,0)
(10)
where
( { [G C8XA
H Σ Σ h= (s.a)EE.
oh 5o.
(1I)
In Definition 2, we allow fraction of the state-action space reachable by n² to be insufficiently covered (as reflected in the definition of ((r) measured by the state-action occupancy distribution) - hence the terminology "partial". Intuitively, Gn corresponds to a set of state-action pairs that undergo reasonable distribution shift (so that the corresponding density ratio does not rise above (+))) whereas the total occupancy density of its complement subset 9j induced by x* is under control (i.c., no larger than a when averaged across steps). As a self-evident fact, (a) is non- increasing in this means that as increases, we might incur less severe distribution shift in restricted part, at the price of less coverage. In this sense, C* (ar reflects certain tradeoffs between distribution shift and coverage. Clearly, C*((a) reduces C* in Definition 1 by taking 0.
Goal. Given a historical dataset Doff containing kfff sample trajectories, we would like to design an online exploration scheme, in conjunction with the accompanying policy learning algorithm, so as to achieve desirable policy learning (or policy fine-tuning) in a data-efficient manner. Ideally, we would expect a hybrid RL algorithm to harvest provable statistical benefits compared both purely online RL. and purely offline RL. approaches.
3 Algorithm
In this section, we propose a new algorithm tackle the hybrid RL setting. Our algorithm design leverages recent ideas developed in offline RL and reward-agnostie exploration to improve sample efficiency. Our algorithm consists of three stages to be described shortly; informally, the first two stages conduct awward-agnsstc exploration to imitate and complement the offline dataset, whereas the third stage invokes a sample-optimal offline RL. algorithm to compute near-optimal policy.
In the sequel, we split the offline dataset Doff into two halves:
Doff.1
and
Doff.2
(12)
where D (resp. 2 consists of the first (resp. last) Koff/ /2 independent trajectories from Doff As we shall also see momentarily, online exploration in the proposed algorithm which collects Knn trajectories in total - can be divided into three parts, collecting Kan prepare Kann I and Kan sample trajectories, respectively. Throughout this paper, for simplicity we choose
explore
Kon
Kon imitate
Kran
explore Kon/3.
(13)
prepare
5

---

3.1 A three-stage algorithm
We now elaborate on the three stages of the proposed algorithm. Due to space limitation, the pseu- docode of the complete algorithm is provided in Appendix B.
Stage 1: estimation of the occupancy distributions. As a preparatory step for reward-agnostic exploration, first attempt to estimate the occupancy distribution induced by any policy well as the occupancy distribution doff associated with the historical dataset, as described below.
Estimating d' for any policy In this step, would like to sample the environment and collect a set of sample trajectories, in a way that allows for reasonable estimation of the occupancy distri- bution dt induced by any policy For this purpose. we invoke the exploration strategy and the accompanying estimation scheme developed in Li et al. (2023). Working forward (i.e., from = to H), this approach collects, for each step h, set of N sample trajectories in order to facilitate estimation of the occupancy distributions, which amounts to total number of
NH =: Kon prepare
K
(14)
sample trajectories collected in this stage. See Algorithm in Appendix D. for a precise description of this strategy. Noteworthily, while Algorithm 3 specifies how to estimate d² for any policy æ, we won't It need to compute it explicitly unless this policy и is encountered during the subsequent steps of the algorithm; other words, de should be viewed as a sort of "function handle" that will only be executed when called later.
Estimating doff for the historical dataset Doff In addition, we are in need of estimating the oceu- pancy distribution d=tt_ Towards this end, we propose the following empirical estimate using the K /2 sample trajectories from Doff.1:
2N (s,a), Koff
( (No (s.a) (ofoff
log Kfff
HSA 3
H A
log
HSA
SA1)
SA
})
2eth (s.
1
Koff
Coff
N
K on
(15)
for all (s. S x A. where coff 0 some universal constant. Here, success probability, and
8 indicates the target
K 12
N (s, a)
Σ
(s)
offff
kfoff 8, ah
a), ((s,a) E SS
(16)
In other words, deff (s, a) is taken to be the empirical visitation frequency of (s, a) in Deft.1 if (s. is adequately visited, and zero otherwise. The cutoff threshold will be made clear in our analysis.
Stage 2: online exploration. Armed with the above estimates of the occupancy distributions, we can readily proceed to compute the desired exploration policies and sample the environment. We seek devise two exploration strategies, with one strategy selected to imitate the offline dataset, and the other one employed to explore the insufficiently visited territory. As a preliminary fact, if we have dataset containing K independent trajectories generated independently from a mixture of deterministic policies with occupancy distribution db - then it has been shown previously (see, e.g., Li al. (2023, Section 3.3)) that the model-basee offline approach is able to compute a policy f obeying
v)) ΣΣ
di (s. 1 s.a
1/ Kon (s,a)
(17)
This upper bound in (17) provides a guideline regarding how to design a sample-efficient peaple--fficiennexplrratttoo scheme.
Imitating the offline dataset. The offline dataset Doff most informative when contains expert data, a scenario when the data distribution resembles the distribution induced by the optimal policy t If this is the case, then it is desirable to find policy similar to off in (6) (the mixed policy gen- crating Doff) and employ it to collect new data, in order to retain and further strength the benefits of

---

which is clearly equivalent to such offline data. To do so, we attempt to approximate d' by doff in (17) when attempting to mini- mize (17). In fact, we would like to compute mixture of deterministic policies by (approximately) solving the following optimization problem:
H Σ
h (s, a) K + En N (d (s.a)]
H
imitate
arg
min (EI(II
max aEA
(18)
h=l
H
2off (s, a) E [d (s, (s.
14 iimitace so arg min max [M) #ES
Eaway (-18)
(19)
MEA(I))
K=H
In order solve this minimax problem (19) (note that its objective function is convex in (4), resort to the Follow-The-Reee Tee-TTh-egglarized---aaaa (FTRL) strategy from the online learning literature (Shalev- Shwartz, 2012); more specifically, we perform the following updates iteratively for / 1,... Tmax:
joft (of E mupk
Th (.18) x exp
1
Vs E
(20a)
[o (s.-))
K
Tofl (8, a)
+ arg min (EA(I))
E
B (-16)
(20b)
K + EN
( (8, a)]
h=1 PES
where y) denotes the learning rate be specified later. We shall discuss how to solve the optimization sub-problen (20b) in Appendix C. The output of this step is mixture of deterministic policies taking the following form:
T
max
π imitate
E
piimitatttt [T]]
with e imitate
(21)
T Tiax
t=1
Exploring the unknown environment. In addition to mimicking the behavior of the historical dataset, we shall also attempt to explore the environment in way that complements pre-collected data. Towards this end, it suffices to invoke the reward-agnostic online exploration scheme proposed in Li al. (2023), whose precise description will be provided in Algorithm Appendix D.2 to make the paper self-contained. The resulting policy mixture is denoted by
π explore
E Eajeeetee [T]]
(22)
with y explore E (II) representing the associated weight vector.
With the above two exploration policies (21) and (22) in place, we execute the MDP to obtain sample trajectories as follows:
1) Execute the MDP K times using policy iimittte to obtain a dataset containing Kon imitate Kon /3 independent sample trajectories, denoted by Don Dimitatee
2) Execute the MDP Keellrre times using policy explore obtain a dataset containing Kon
Keelore K /3 independent sample trajectories, denoted by explore
Stage 3: policy learning via offline RL. Once the above online exploration process is completed, we are positioned to compute a near-optimal policy on the basis of the data hand. More precisely,
Let us look at the following dataset
D = 2 Don imitate
Den explore
(23)
In light the complicated statistical dependency between offf.1 and Dontate U Den only include the second half Doff. of the offline dataset Doff so to exploit the fact that Doff.2 statistically independent from Don Don U DDon explore
explore we
We invoke the pessimistic model-based offline RI. algorithm proposed in et al. (2022) to compute the final policy estimate 7; see Algorithm 6 in Appendix D.3 for more details.
7

---

Main results
As it turns out, Algorithm I is capable of achieving provable sample efficiency, demonstrated in the following theorem. Here and below, we recall that K K + K
Theorem 1. Consider 8 E (0, 1) and é E (0, H.. Choose the algorithmic parameters such that
log A
and
Tmax 2 2(Kx0 log A.
27 max (n H)
Suppose that
K
+ offf
H (O)
log
K
(24a)
62
Hd SA
K
K Z Ci
log
(24b)
for some large enough constant > 0. Then with probability at least 1 - 6, the policy स returned by Algorithm 1 satisfies
Vi(
S
provided that K and Koft both exceed some polynomial Holy(H,S,AA) (o)) $ dent =).
(indepen-
The proof is deferred Appendix E. In nutshell, Theorem uncovers that our algorithm yields e-accuracy as long as
(C) K
K + Koff off 7
log
2
(25a)
62
8
K H min Ho,
K
log
(25b)
g2
8
ignoring lower-order terms. Several implications of this result are as follows.
Sample complexity benefits compared with pure online or pure offline RL. To make apparent its advantage compared with both pure offline and online RI, we make comparisons with several most relevant works. Discussions of other related works are deferred to Appendix A.
Sample complexity with balanced online and offline data. For the case of presentation, let us look at simple case where Kfff Kon K/2. The the sample complexity bound (25) in this case simplifies to
SA min Ho, [E
(0)C E2
}) =:
δ min
min Fmixed (a) [E(0..1
(26)
g²
Comparisons with pure online RL. We now look at pure online RL, corresponding to the case where K = K (so that all sample episodes are collected via online exploration). In this case, the minimax-optimal sample complexity for computing an e-optimal policy known to (Azar et al., 2017; Li et al., 2023)
(H)SA) 82
(f
(27)
assuming that E is sufficiently small, which is clearly worse than (26). For instance, if there exists some very small < 1/H obeying C*(a) $ 1, then the ratio of (26) to (27) is most Ho + <
(28)
thus resulting in substantial sample size savings.
Comparisons with pure offline RI. In contrast, in the pure offline where K K'off the minimax sample complexity is known to be (Li et al., 2022) ( (0))
δ (H'
(29)
E2
for any target accuracy level e, which is apparently larger than (26) in general. In particular, recog- nizing that (0) in the presence of incomplete coverage of the state-action space reachable by n², we might harvest enormous sample size benefits (by exploiting the ability of online RI. to visit the previously uncovered state-action-step tuples).

---

Comparison with Wagenmaker and Pacchiano (2022). It is worth noting that Wagenmaker and Pacchiano (2022) also considered policy fine-tuning and proposed a method called FTPedel to tackle linear MDPs. The results therein, however, were mainly instance instance-dependent, thus making it difficult to compare in general. That being said, we would like to clarify two points:
Wagenmaker and Pacchiano (2022) imposed all-policy concentrability assumptions, requr- ing the combined dataset (i.e., the offline and online data altogether) to cover certain feature vectors for all linear softmax policies (see Wagenmaker and Pacchiano (2022, Definition 4.1)). In contrast, our results only assume single-policy (partial) concentrability, which is much weaker than the all-policy counterpart.
When specializing Wagenmaker and Pacchiano (2022, Corollary 1) to the tabular cases, the sample complexity therein becomes Ö(H7 5 A² /e²), which is much larger than our result.
Miscellaneous properties of the proposed algorithm. In addition to the sample complexity ad- vantages, the proposed hybrid RL enjoys several attributes that could practically appealing.
Adaptivity to unknown optimal σ. While we have introduced the parameter to capture incomplete coverage, our algorithm does not rely on any knowledge of a. Take the balanced case described around (26) for instance: our algorithm automatically identifies the optimal a that minimizes the function fmixed (o) over all E [0, 1]. In other words, Algorithm is able to automatically identify the optimal trade-offs between distribution mismatch and inadequate coverage.
Reward-agnostic data collection. It is noteworthy that the online exploration procedure employed in Algorithm 1 does not require any prior information about the reward function. In other words, it is mainly designed to improve coverage of the state-action space, a property independent from the reward function. In truth, the reward function is only queried at the last step output the learned policy. This enables us to perform hybrid RL in a reward-agnostic manner, which is particularly intriguing in practice, as there is no shortage of scenarios where the reward functions might be engineered subsequently to meet different objectives.
Strengthening behavior cloning. Another notable feature is that our algorithm does not rely prior knowledge about the policies generating the offline dataset Doff; in fact, it is capable of finding a mixed exploration policy π .imitate that inherits the advantages of the unknown behavior policy offf This could be of particular interest for behavior cloning, where the offline dataset Doff is generated by an expert policy, with C* (0) ~ 1, i.e. the expert policy covers the optimal one. In this situation, the supplement of online data collection improves behavior cloning by lowering the statistical error from
HPSC- to HSSC. together with an executable learned policy n imitate Kat
Kat Kan
Computational complexity. We now take moment to discuss the computational cost of the pro- posed algorithm. In Stage 1, we need to first estimate the transition matrices ( {Pr which can be accomplished with runtime O(K')). In the ensuing stages, we call Algorithm to estimate d' for each π we encounter. When computing iimitate, we need calculate d' for Ti TmxxTy times, where T2 denotes the number of iterations for calculating y in Eq. (20b); in comparison, the computational cost of estimating d to yield eeplore in Eq. (22) is much smaller. For each d= it needs (HS2² A) computation. With a slight modification on the target Eq. (19) as follows
imitate
of (s, a)
arg min (EA(TT)
ΣΣ
max aEA
0
doft
(s,a) +
E I/ pomppre
d (s, + E x'uup
[dg (s, a)]
K=
KH
(30)
can find a good enough n imitate with Tmax Ō(H252) for n HĀ5z and S A2) Frank- Wolfe updates for म.डन These taken collectively lead the following computational complexity for each stage: O(Kon H7 8 13 + Kolf H) for Stage O A3) for Stage 2, and O(H) for Stage 3.

---

5
Discussion
We have studied the policy fine-tuning problem practical interest, where one allowed exploit pre-collected historical data to facilitate and improve online RL. We have proposed three-stage algorithm tailored to the tabular setting, which attains provable sample size savings compared with both pure online RL and pure offline RL algorithms. Our algorithm design has leveraged key insights from recent advances in both model- based offline RL and aanootc online RL.
While the proposed algorithm achieves provable sample efficiency, this cannot be guaranteed unless the sample size already surpasses fairly large threshold (in other words, the algorithm imposes a high burn-in cost). It would be of great interest to see whether one can achieve sample opti- mality for the entire e-range. Another issue arises from the computation side: even though the proposed algorithm can be implemented in polynomial time, the computational complexity of the subroutine might already be too expensive for solving problems with enormous dimensionality. Can we hope to further accelerate it to make it practically more appealing? Finally, it might also be interesting to study sample-efficiene hybrid RL in the presence of complexex function approximation, in the hope of further reducing sample complexity.
Acknowledgements
Y. Chen is supported in part by the Alfred P. Sloan Research Fellowship, the Google Research Scholar Award, the AFOSR grant 109550-22-1-0198, the ONR grant N00014-22-1-2354 and the NSF grants CCF-222 22222022229222 and CCF-1907661. Y. Chi are supported in part by the grants ONR N00014-11-11240% NSF CCF-2106778, DMMS21344800 and CNS-2148212. J. D. Lee acknowl- edges support of the ARO under MURI Award W911NF-L1-1-0304 the Sloan Research Fellowship, the NSF grants CCF 2002272, IIS 2107304 and CIF 2212262, the ONR Young Investigator Award, and the NSF CAREER Award 2144994.
References
Agarwal, A., Kakade, S., Krishnamurthy, A., and Sun, W. (2020). Flambe: Structural complexity and representation learning of low rank mdps. arXiv preprint arXiv:2006.
Alon, N. and Spencer, J. H. (2016). The probabilistic method. John Wiley & Sons.
Auer, P. and Ortner, R. (2006). Logarithmic online regret bounds for undiscounted reinforcement learning. Advances neural information processing systems, 19.
Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In Proceedings of the 34th International Conference on Machine Learning- Volume 70, pages 263-272 JMLR. org.
Bai, Y., Xie, T., Jiang, N., and Wang, Y.-X. (2019). Provably efficient q-learning with low switching cost. In Advances in Neural Information Processing Systems, volume 32, pages 8002-8011.
Berner, C., Brockman, G., Chan, B., Cheung, V., Debiak, P., Dennison, C., Farhi, D., Fischer, Q., Hashme, S., Hesse, C., al. (2019). Dota 2 with large scale deep reinforcement learning. arXiv preprint arXiv: 1XXi:1912.066800
Bertsekas, D. P. (2017). Dynamic programming and optimal control (4th edition). Athena Scientific.
Brafman, R. I. and Tennenholtz, M. (2002). R-max-a general polynomial time algorithm for near- optimal reinforcement learning. Journal of Machine Learning Research, 3(Oct):213-231.
Brambilla, M., Ferrante, E., Birattari, M., and Dorigo, M. (2013). Swarm robotics: a review from the swarm engineering perspective. Swarm Intelligence, 701::141.
Bubeck, S. (2015). Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8(3-4):231-357.
Cai, C., Cai, T. T., and Li, H. (2022). Transfer learning for contextual multi-armed bandits. arXiv preprint 2r1 122612.
10

---

Chen. J. and Jiang, N. (2019). Information- theoretic considerations in batch reinforcement learning. In Proceedings of the 36th International Conference on Machine Learning. volume 97, pages 1042-1051.
Chen, J., Modi, A., Krishnamurthy, A., Jiang, N., and Agarwal, A. (2022a). On the statistical efficiency of reward-free exploration in non-linear rl. arXiv preprint arXiv:2206.1077 10770.
Chen, Z., Li, J., Yuan, A., Gu, Q. and Jordan, M. I. (2022b). A general framework for sample- efficient function approximation reinforcement learning, arXiv preprint arXiv:2209.156:4
Cui, Q. and Du, S. S. (2022). When offline two-player zero-sum Markov game solvable? arXiv preprint arXiv:2201.0333
Dann, C., Lattimore, T., and Brunskill, (2017). Unifying pac and regret: Uniform pac bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 30.
Domingues, O. D.. Ménard, P., Kaufmann, E., and Valko, M. (2021). Episodic reinforcement learn- ing in finite mdps: Minimax lower bounds revisited. In Algorithmic Learning Theory, pages 578-598. PMLR.
Dong, K., Wang, Y., Chen, X., and Wang. L. (2019). Q-learnng with UCB exploration is sample efficient for aninite-horizon MDP. arXiv preprint 1rXiv:1901.09311
Du, S. S., Kakade, S. M., Lee, J. D., Lovett, S., Mahajan, G., Sun, W., and Wang, R. (2021). Bilinear classes: A structural framework for provable generalization in
Foster, D. J., Kakade, S. M., Qian, J., and Rakhlin, A. (2021). The statistical complexity of interac- tive decision making. arXiv preprint arXiv:2112.1345:
Hester, T., Vecerik, M., Pietquin, O., Lanctot, M., Schaul, T., Piot, B., Horgan, D., Quan, J., Sendonaris, A., Osband, I., et al. (2018). Deep Q-learning from demonstrations. In Proceed- ings of the AAAI Conference on Artificial Intellignce, volume 32.
Huang, R., Yang, J., and Liang. Y. (2022). Safe exploration incurs nearly no additional sample complexity for reward-free RL. arXiv preprint urXiv:2206.10057.
Jaksch, T., Ortner, R., and Auer, P. (2010). Near-optimal regret bounds for reinforcement learning. Journal of Machine Learning Research.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is Q-learning provably efficient? In Advances in Neural Information Processing Systems, pages 4863-4873.
Jin, C., Krishnamurthy, A., Simchowitz, M., and Yu, T. (2020a). Reward-free exploration for rein- forcement learning. In International Conference on Machine Learning, pages 4870-4879, 48L..
Jin, C., Liu, Q., and Miryoosefi, S. (2021a). Bellman eluder dimension: New rich classes of RL problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2020b). Provably efficient reinforcement learning with linear function approximation. Conference on Learning Theory, pages 2137-2143. PMLR.
Jin, Y., Yang, Z., and Wang, Z. (2020c). Is pessimism provably efficient for offline ri? arXiv preprint 2rXiv:2012.15085.
Jin, Y., Yang, Z., and Wang, (2021b). Is pessimism provably efficient for offline RL2 Interna- tional Conference on Machine Learning, pages 5084-5096. PMLR.
Kalashnikov, D., Irpan, A., Pastor, P., Ibarz, J., Herzog, A., Jang, E., Quillen, D., Holly, E., Kalakr- ishnan, M., and Vanhoucke, V. (2018). Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on Robot Learning, pages 651-673 PMLR.
Kaufmann, E., Ménard, P., Domingues, O. D., Jonsson, A., Leurent, E., and Valko, M. (2021). Adaptive reward-free exploration. In Algorithmic Learning Theory, pages 865-891. PMLR.
11

---

Kumar, A., Zhou, A., Tucker, G., and Levine, S. (2020). Conservative q-learning for offline rein- forcement learning. In Conference on Neural Information Processing Systems (NeurIPS).
Li, G., Chen, Y., Chi, Y., Gu, Y. and Wei, Y. (2021a). Sample-efficient reinforcement learning is feasible for linearly realizable MDPs with limited revisiting. Advances in Neural Information Processing Systems, 34:16671-16685.
Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. (2022). Settling the sample complexity of model-based offline reinforcement learning, arXiv preprint arXiv:220.005275.
Li, G., Shi, L., Chen, Y., Gu, Y., and Chi, Y. (2021b). Breaking the sample complexity barrier to regret-optimal model-free reinforcement learning. Advances in Neural Information Processing Systems, 34:17762-17776
Li, G., Yan, Y., Chen, Y., and Fan, J. (2023). Minimax-optimal reward-agnostic exploration in reinforcement learning. arXiv preprint arX2v:2304.0727.
Liu, Y., Swaminathan, A., Agarwal, A., and Brunskill. E. (2020). Provably good batch reinforcement learning without great exploration. arXiv preprint arXiv:2007.08202.
Ménard. P., Domingues, O. D., Jonsson, A., Kaufmmmnn E., Leurent, E., and Valko, M. (2021a). Fast active learning for pure exploration reinforcement learning. In International Conference on Machine Learning, pages 7599-7608, PMLR.
Ménard, P., Domingues, O. D., Shang, X., and Valko, M. (2021b). UCB momentum Q-learning: Correcting the bias without forgetting. In International Conference on Machine Learning, pages 7609-7618.
Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., and Riedmiller, M. (2013). Playing atari with deep reinforcement learning, arXiv preprint 1rXiv:13122
Munos, R. and Szepesvári, C. (2008). Finite-time bounds for fitted value iteration. In Journal of Machine Learning Research, volume 9, pages 815-857.
Nair, A., Gupta, A., Dalal, M., and Levine, S. (2020). Awac: Accelerating online reinforcement learning with offline datasets. arXiv preprint 200v:22000009559
Nair, A., McGrew, B., Andrychowicz, M., Zaremba, W., and Abbecl, P. (2018). Overcoming explo- ration in reinforcement learning with demonstrations. In 2018 IEEE international conference robotics and automation (ICRA), pages 6292-6299. IEEE.
Nakamoto, M., Zhai, Y., Singh, A., Mark, M. S., Ma, Y., Finn, C., Kumar, A., and Levine, S. (2023). Cal-QL: Calibrated offline RL pre-training for efficient online fine-tuning, arXiv preprint arXiv:2303.05479,
Qiao, D. and Wang, Y.-.. (2022). Near-optimal deployment efficiency in reward-free reinforcement learning with linear function approximation. arXiv preprint arXiv:2210.00701.
Rajeswaran, A., Kumar, V., Gupta, A., Vezzani, G., Schulman, J., Todorov, E., and Levine, S. (2017). Learning complex dexterous manipulation with deep reinforcement learning and demonstrations. arXiv preprint arXiv: 11101709000000 10087.
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., and Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances Neural Information Processing Systems, 34:1 1702-11716.
Ross, S. and Bagnell, A. (2012). Agnostic system identification for model-based reinforcement learning. International Conference on Machine learning.
Shalev-Shwarte S. (2012). Online learning and online convex optimization. Foundations and Trends Machine Learning, 4(29:107-194.
Shalev-Shwartz, S., Shammah, S., and Shashua, A. (2016). Safe, multi-agent, reinforcement learn- ing for autonomous driving. arXiv preprint arXiv: 1610.03295.
12

---

Shi, L. and Chi, Y. (2022). Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint 0rXiv:2208.05767.
Shi, L.. Li, G., Wei, Y. Chen, Y. and Chi, (2022). Pessimistic Q-learning for offline reinforcement learning: Towards optimal sample complexity. In International Conference on Machine Learning, PMLR.
pages
Silver, D., Huang, A., Maddison, C. J., Guez, A., Sifre, L.,, Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvam, V., Lanctot, M., et al. (2016). Mastering the game of Go with deep neural networks and tree search. nature, 529(7587):484 489.
Song, Y., Zhou, Y., Sekhari, A., Bagnell, A., Krishnamurthy, A., and Sun, (2022). Hybrid RL: Using both offline and online data can make RI. efficient. arXiv preprint arXiv:2110.067/8
Uehara, M. and Sun, W. (2021). Pessimistic model- based offline RL: PAC bounds and posterior sampling under partial coverage. In arXiv preprint 1rXiv:2107.0000 107.06226.
Vecerik, M., Hester, T., Scholz, J., Wang, F., Pietquin, O., Piot, B., Heess, N., Rothörl, T., Lampe, T., and Riedmiller, M. (2017). Leveraging demonstrations for deep reinforcement learning on robotics problems with sparse rewards. arXiv preprint 1707,08777..881111
Vinyals, O., Babuschkin, I., Czarnecki, W. M., Mathieu, M., Dudzik, A., Chung, J., Choi, D. H., Powell, R., Ewalds, T., Georgiev, P., et al. (2019). Grandmaster level in starcraft ii using multi- agent reinforcement learning. Nature, 575(7782)3350-35
Wagenmaker, A. and Pacchiano, A. (2022). Leveraging offline data in online reinforcement learning- arXiv preprint arXiv:22 I I.4974.
Wagenmaker, A. J., Chen, Y., Simehowitz, M., Du, S., and Jamieson, K. (2022). Reward -reee RL is no harder than reward-aware RL in linear Markov decision processes. In International Conference on Machine Learning, pages 22430-22456
Wang, R., Du, S. S., Yang. L.,, and Salakhutdinov, R. R. (2020). On reward-free reinforcement learning with linear function approximation. Advances in neural information processing systems, 33:178 1-726..
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2021a). Bellman-consistent pes- simism for offline reinforcement learning. arXiv preprint arXiv:2106.06926.
Xie, T., Jiang, N., Wang, H., Xiong, C., and Bai, (2021b). Policy finetuning: Bridging sample- efficient offline and online reinforcement learning, arXiv preprint arXiv:2106.04880
Yan, Y. Li, G., Chen, Y., and Fan, J. (2022). Model-based reinforcement learning is minimax- optimal for offline zero-sum Markov games. arXiv preprint urXiv:2206.0 04044.
Yan, Y., Li, G., Chen, Y., and Fan, (2023). The efficacy of pessimism in asynchronous Q-learning- IEEE Transactions Information Theory.
Yin, M., Bai, Y., and Wang, Y.-.. (2021). Near-optimal offline reinforcement learning via double variance reduction. Advances in neural information processing systems, 34:7677-7688.
Zanette, A., Lazaric, A., Kochenderfer, M., and Brunskill, E. (2020). Learning near optimal policies with low inherent bellman error. In International Conference on Machine Learning, pages 10978- 10989. PMLR.
Zhan, W. Huang, B., Huang, A., Jiang. N., and Lee, J. (2022). Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pages 2730-2775. PMLR.
Zhang, W., Zhou, D., and Gu, Q. (2021a). Reward-free model-based reinforcement learning with linear function approximation. Advances in Neural Information Processing Systems, 34:1582- 1593.
Zhang, Ma, Y., and Singla, A. (2020a). Task-agnostic exploration reinforcement learning. Advances in Neural Information Processing Systems, 33:1 1774-11743.
13

---

Zhang, Z., Chen, Y. Lee, J. D., and Du, S. S. (2023). Settling the sample complexity of online reinforcement learning. arXiv preprint arXiv:2307.13586.
Zhang, Z., Du, S., and Ji, X. (2021b). Near optimal reward-free reinforcement learning. Interna- lional Conference on Machine Learning, pages 12402-12412. PMLR.
Zhang, Z., Zhou, Y., and Ji, X. (2020b). Model-free reinforcement learning: from clipped pseudo- regret to sample complexity. arXiv preprint arXiv:2006.03866.
Zhou, D., Gu, Q. and Szepesvari, C. (2021a). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes. In Conference on Learning Theory, pages 4532-4576. PMLR.
Zhou, Z., Zhou, Z., Bai, Q., Qiu, L., Blanchet, J., and Glynn, P. (2021b). Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. International Conference on Artificial Intelligence and Statistics, pages 3331-3339. PMLR.
14

---

A Other related works
In this section, we briefly discuss a small set of additional prior works related to the current paper.
(Reward-aware) online RL. In online RL, an agent seeks to find a near-optimal policy by se- quentially and adaptively interacting with the unknown environment, without having access any additional offline dataset. The extensive studies of online RL gravitate around how to optimally trade off exploration against exploitation, for which the principle of optimism in the face of uncertainty plays a crucial role (Auer and Ortner, 2006; Jaksch et al., 2010; Azar et al., 2017; 7; Dann et al., 2017; Jin al., 2018: Bai al., 2019; Dong et al., 2019; Zhang et al., 2020b; Ménard al., 2021b; Li coommatioonthhoreete regret lower bounds have been established
et al., 2021b; Zhang et al., 2023). by Domingues et al. (2021); Jin et al. (2018), which are shown be achievable (up to log factor) by the model-based approach for arbitrary sample sizes (Zhang et al., 2023). A further strand of works extended these studies to the case with function approximation, including both linear function ap- proximation (Jin et al., 2020b; Zanette et al., 2020: Zhou et al., 2021 Li et al., 202 la) and other more general families of function approximation (Du et al., 2021; Jin et al., 2021a; Foster et al., 2021).
Offiine RL. In contrast to online RL, offline RL assumes access to a pre-collected offline dataset and precludes active interactions with the environment. Given the absence of further data collection, the sample complexity of pure offline RL depends heavily upon the quality of the offline dataset at hand, which has often been characterized via some sorts of concentrability coefficients in prior works (Rashidinejad et al., 2021; Zhan et al., 2022). Earlier works (Munos and Szepesvári, 2008; Chen and Jiang, 2019) typically operated under the assumption of all-policy concentrability the assumption that the dataset covers the visited state-action pairs of all possible policies - thus imposing a stringent requirement for the offline dataset to be highly explorative. To circumvent this stringent assumption, Liu et al. (2020); Kumar et al. (2020); Jin et al. (2021b); Rashidinejad et al. (2021); Uchara and Sun (2021); Li et al. (2022); Yin et al. (2021); Shi et al. (2022); Yan et al. (2023) incorporated the pessimism principle amid uncertainty into the algorithm designs and, as a result, required only single-polics concentrability (so that the dataset only needs to cover the part of the state-action space reachable by the optimal policy). With regards to the basic tabular case, Li et al. (2022) proved that the pessimistic model-basee offline algorithm is capable of achieving minimax- optimal sample complexity for the full e-range, accommodating both the episodic finite-horizon case and the discounted infinie-hhorizn analog. Moving beyond single-agent tabular settings, a recent line of works investigated offiine RI. in the presence of general function approximation (Jin et al., 2020c; Xie et al., 2021a; Zhan et al., 2022), environment shift (Zhou et al., 2021b: Shi and Chi, 2022), and in the context of zero-sum Markov games (Cui and Du, 2022; Yan et al., 2022).
namely,
Hybrid RL. While there were number of empirical works (Rajeswaran al., 2017; Vecerik et al., 2017; Kalashnikov et al., 2018; Hester et al., 2018; 8; Nair et al., 2018, 2020) suggesting the perfromance gain of combining online RL with offline datasets (compared to pure online or offline learning), rigorous theoretical evidence remained highly limited. Ross and Bagnell (2012); Xie et al. (2021b) attempted develop theoretical understanding by looking at one special hybrid scenario, where the agent can perform either of the following in each episode: (i) collecting a new online episode; and (ii) executing prescribed and fixed reference policy to generate sample episode. In this setting, Xie et al. (2021b) showed that in the minimax sense, combining online learning with samples generated by such a reference policy is not advantageous in comparison with pure online or offline RL. Note that our results do not contradict with the lower bound in Xie et al. (2021b), given that we exploit "partial" single-policy concentrability that implies additional structure except for the worst case. Akin to the current paper, Song et al. (2022); Wagemmaker and Pacchiano (2022) studied online RI. with additional access to an offline dataset. Nevertheless, Song et al. (2022) mainly focused on the issue of computational efficiency, and the algorithm proposed therein does not come with improved sample complexity. In contrast, Wagenmaker and Pacchiano (2022) focused attention on statistical efficiency, although the sample complexity derived therein is highly suboptimal when specialized to the tabular setting.
Reward-fres free and task-agnostic exploration. Reward-free and task-agnostic exploration, which refer to the scenario where the agent first collects online trajectories without guidance of any information about the reward function(s), has garnered much recent attention (Brafman and
sample
15

---

Tennenholtz, 2002; Jin et al., 2020a; Zhang et al., 2020a, 2021b; Huang et al., 2022). Focusing on the tabular case, the earlier work Jin (2020a) put forward reward-free exploration scheme that achieves minimax optimality in terms of the dependency on S, A and 1/e, with the horizon dependency further improved by subsequent works (Kaufmann et al., 2021; Ménard al., 2021a; Li et al., 2023). In particular, the exploration scheme proposed in Li et al. (2023) was shown to achieve minimax-optiman sample complexity when there exist a polynomial number pre-determined but unseen reward functions of interest, which inspires the algorithm design of the present paper. More- over, reward- RL has been extended to account for function approximation, including both linear (Wang et al., 2020; Agarwal et al., 2020; Qiao and Wang. 2022; Zhang et al., 202 Wagenmaker et al., 2022) and nonlinear function classes (Chen et al., 2022a).
B Pseudocode of Algorithm
In this section, we provide the whole procedure for the proposed hybrid RL algorithm, with several subroutines deferred to Appendix and Appendix D.
Algorithm 1: The proposed hybrid RL algorithm.
Input: offline dataset Doftt (containing Kfff trajectories), parameters N, K maxx learning
rate 1).
Initialize: T/ s) = 1/A for any (s, h); K Koff + K split Deff into two halves Doff, and Doff.2
/* Estimation of occupancy distributions for any policy
3 Call Algorithm 3, which allows one to specify (s, a) for any deterministic policy a and any (s, h).
/* Estimation of occupancy distributions of the historical data.
Use the dataset D to compute
2Nooft (s, a)
Nooti (s, a) Koff
log HSA
A HSA
SA
d% (s.a) a) = Koff
1
2 Coff
+
Koff
N
Kon
for any (s, h), where (s, a) absolute constant.
> 12
(s/) 8, o a) and Coff > 0 is some
(* Compute general sample-efficient online exploration scheme.
Call Algorithm with estimators d= to compute policy म explore and the associated weight
, explare
Compute online exploration scheme tailored to the offline dataset.
*/
for f = 1,... Tmax do
Compute je using Algorithm 2. Update * s) for all (s, h) S x Ax [H]
such that:
n E
2 (s.a)
exp
Ror +E kypk di (m.a)
++1 (al ()
Th
Enee exp
11
=k==
Jolf (s,a²
Reny B 2 2 (a(ar))
Set imitate
Trae Lt=l nt and x imitate Expepiintuee (T].
Tiae
Sampling using the above two exploration policies.
10 Collect iron imitate (resp. Kron Koollrr) sample trajectories using a imitate (resp. x explore) to form a imittat (resp. Don Despirre.
dataset Don
/* Run the model-based offline algorithm.
11 Apply Algorithm to the dataset D Doff. U Don Don
explore to compute a policy R.
12 Output: policy
16

---

C Subroutine for solving the subproblem (20b)
While (20b) is a convex optimization subproblem, it involves optimization over a parameter space with exponentially large dimensions. In order solve it in a computationally feasible manner, we propose a tailored subroutine based on the Frank-Wolfe algorithm (Bubeck, 2015).
Before proceeding, recall that when specifying d' in Algorithm 3, we draw N independent tra- a.A
jectories { 01 nhh ..... sh+1 hisnN and compute an empirical estimate Ph. of the probability transition kernel step such that
((, > x) Pa |s,a)= max (8, a): 13
N
Σ
n.h 1(sh
n.h n.k s, s,ah a, sht1 =s),
n=1
(31)
where ah 118 = s, 0h a}.
The proposed Frank- Wolfe-type algorithm. With this set of notation in place and with an initial
guess taken to be the indicator function y(()) 1 1mm for an arbitrary policy Tinit E 11, the k-th iteration of our iterative procedure for solving (20b) can be described as follows.
Computing a search direction. The search direction of the Frank- algorithm is typi- cally taken to be a feasible direction that maximizes its correlation with the gradient of the objective function (Bubeck, 2015). When specialized to the current sub-prut sub-problem (20b), the search direction can be taken to be the Dirac measure 5,00, where
T (s, a)d (s, a))a) (R*H + Bringal [dk (8, a))
TEll T arg max fTT (1))
Ba (-1a) (-1a)
h=1
(32)
As it turns out, this optimization problem (32) can be efficiently solved by applying dy- namic programming (Bertsekas, 2017) to an augmented MDP Mooff constructed as follows.
Introduce an augmented fnite-horizon MDP M (S U {saug). ). A, H, Paug, yoff) where Sang is an augmented state. We choose the reward function to be
m ++ (a| s)az (s,a)
if (). if (s, h) E {saug) x Ax x H
[H],
off (s,
र +3, (k)))) d (s.a))
0.
(33)
and the probability transition kernel as
Pa a),
if S
PanB (s,a)= { -vEss Pa 18,a),
for all (s,a, E x A [H]
if = Saug
(34a)
Pauu (8' Saug: a) = (s' = 8aug)
for all (a, E A x [H].
(34b)
Frank- Wolfe updates. We then update the iterate μ (k++)) as convex combination of the current iterate and the direction found in the previous step:
(++1) (1 ()) 1 1.0)
(35)
where the stepsize chosen to be
S a (Kon
(36)
17

---

Stopping rule. It is also necessary to specify the stopping rule of the above iterative procedure. Throughout this paper, the above subroutine will terminate as long as
Toll (8, ())
ΣΣ h=S
108SH,
(37)
amaR (-18)
K H + E (x d7 (8, (8,a)]
with the final output taken to be n pl))) We shall justify the feasibility this stopping rule (namely, the fact that this stopping criterion can be met by some mixed policy) in Appendix F.
Iteration complexity. Encouragingly, the above subroutine in conjunction with the stopping rule (37) leads to an iteration complexity no larger than
O (KomH) H)*
(iteration complexity)
(38)
$2
The proof of this claim is postponed to Section F.
Algorithm 2: Subroutine for solving the sub-problem (20b).
Initialize: (1) 1 mii for an arbitrary policy Tinit II.
for k = 1,2. ... do
Exit for-loop the following condition is met: // stopping criterion
(s,a) KOH + ( (0) (d,
dift
A=1 am e+1 (:10)
Σ
108SH.
(39)
(s, a)]
/* Find the search direction */
Compute the optimal deterministic policy x ((k),aug of the MDP Mofi = (S J {saug): A, H, Paug Tofr), where Saug is an augmented state,
xn (al (a))))
if (s. S Ax [H],
off (s, a)
godry +B ( ( (sa))))
(40)
if (s,,,,)) E {Saug) x A x [H],
and the augmented probability transition kernel is given by
iard (s' ss,a)= = Pa (((s'sss))) a),
if s' E
for (s, E A x [H]
Eves (a 18,a), if s' Saug
(41a)
B (s') Saug; a1) = 11 (s (6''= = 8aug)
for all (a, E EA [
(41b)
Let (*) be the corresponding optimal deterministic policy of (A) in the original state space.
Update // Frank-Wolfe update
S
(*+1) = (1-a)u( +a all,, where a (Kon
Output: the policy mixture = (k).
D Useful algorithmic subroutines from prior works
In this section, provide precise descriptions of several useful algorithmic subroutines that have been developed in recent works. The algorithm procedures are directly quoted from these prior works, with slight modification.
18

---

D.1 Subroutine: occupancy estimation for any policy
The first subroutine we'd like to describe concerned with estimating the occupancy distribution d induced by any policy и,, based on a carefully designed exploration strategy. This algorithm, proposed by Li et al. (2023), seeks to estimate {dī step by step (i.e., from = ,,..., H). For each h. it computes an appropriate exploration policy @xplore._ to adequately explore what happens between step h and step h + and then collect N sample trajectories using ı explore..A, These turns allow us to estimate the occupancy distribution d for step h + 1. See Algorithm 3 for precise description.
Algorithm 3: Subroutine for estimating occupancy distributions for any policy (Li al., 2023).
target success probability - 6, threshold { cq H A (og((HAA/)) /* Estimate occupancy distributi ons for step 1. */
Input:
2 Draw N independent episodes (using arbitrary policies), whose initial states are i..d. drawn
from st Lid. (1 S n S N). Define the following functions
N
1
(s)
Σ
1
p. = =},
(s, (s))T((aa)))
(42)
N
1=
for any deterministic policy S. functions are defined for future use and not computed for the moment, as we have not specified policy πT.)
[H] + A(A) and any (s, a) A. (Note that these
Estimate occupancy distributions for steps ,, H.
for to H 1 do
/* Collect N sample trajectories using suitable exploration policy,
*/
Call Algorithm compute exploration policy explore, and compute estimate P, of the true transition kernel Pr.
/* Specify how to compute d for any policy n. */
For any deterministic policy π : S [H] + A(A) and any (s, E S A, define
(5) (P((s ) o )) (h, (S) (a|s).
(43)
We note, however, that Algorithm requires another subroutine to compute a suitable exploration policy explore. As it turns out, this can be accomplished by approximately solving the following problem
arg max PEA(II)
Σ
log
E xnpp
(s.
(44)
KH
(s.a)ESxA
via the Frank-Wolfe algorithm and returning explore, Erapp [T]. See Algorithm 4 for details.
D.2 Subroutine: reward-agnostic online exploration
Based on the estimated occupancy distributions specified in Algorithm 3. Li et al. (2023) proposed a neward-independern online exploration scheme that proves useful in exploring an unknown envi- romment. In a nutshell, this scheme computes a desired exploration policy by approximately solving the following optimization sub-problem:
H Σ
explore arg max
Σ
log
+
Er [Th (s,
(47)
(EA(T)
Kon
f=1 (s.))ESxA
again using Frank- Wolfe algorithm; the resulting policy takes the form of mixture of deter- ministic policies, as given by explore = -E-zz-po (T]. This exploration policy is then employed to execute the MDP for number of times in order to collect enough information about the unknowns. See Algorithm 5 for the whole procedure.
19

---

Algorithm 4: Subroutine for computing the exploration policy for step h in occupancy estima- tion (Li et al., 2023).
Initialize: 10 = nm for an arbitrary policy Tinit E II, Tixx [)) for 0 T max do
/* find the optimal policy */
Compute the optimal deterministic policy (())bb of the augmented MDP
M = (S [Saug)..44 H, Paug, ; where Saug is an augmented state,
(s, {
if (s, a. E Ax {h),
Roy ma [T]() 0,
(45)
if Saug or j # h.
and the augmented probability transition kernel is defined as
(,) ss)a),
if E S
Pangci (s' (8,0)
for all (s, E E
[M]]
[ 1 Eves ()))),
if s' 8ang
(46a)
Gaug (5' 8 - 1(8' = -aag))
if 8 Saug or > h. (46b)
Let (4) the corresponding optimal deterministic policy of (()).b the original state space.
Compute // choose the stepsize
1x (())
KOH + di (s, a)
0g g(0(1), d. v(t)) -1 where g( (c,d,p)
Σ
(s, KmH + E ( (s,
Here, d7(s, a) is computed via (42) for h and (43) for h 2 2. If g(((() d, (1) < 2SA then exit for-loop. // stopping rule Update // Frank-Wolfe update
u (142) (1 ar) ( + az m
Set explore, 1 [T] with fht n The final exploration policy for step h.
/* Draw samples using explore, to estimate the transition kernel.
11 Draw N independent trajectories {si a.A S....,st1iinne using policy π explore, and compute
Pr(5'( 1(N, > 2) max N, (s. a), 1] where (s) = Σ,= 1 18
E1(5h s, ah a, a,s s'),
8, ah n,h a}.
Output: the exploration policy explore, the weight fh, and the estimated kernel Pr..
D.3
Subroutine: pessimistic model-based offline RI
Given a historical dataset containing a collection of statistically independent sample trajectories, Li al. (2022) came up with model-based approach that enjoys provable minimax optimality. This approach first employs two-fold subsampling trick in order to decouple the statistical dependency across different steps of a single trajectory. After this subsampling step, this approach resorts to the principle of pessimism in the face of uncertainty, which employs value iteration but penalizes the updates via proper variance-aware penalization (i.e., Bernstein-style lower confidence bounds). Details can be found in Algorithm 6.
20

---

Algorithm 5: Subroutine for computing the desired online exploration policy (Li et al., 2023).
Initialize: H4g 8m.. for an arbitrary policy Tinit E II, Tmax |00AAH log( K KH).
for t = 0 to maax do
/* find the optimal policy */
Compute the optimal deterministic policy x ((1,b of the MDP
Mb (S (Saug) A H, pauR, rb), where Saug is augmented state,
if (ss,a,)) E A [H], if as, E {Saug} x A [M]],
(b)
ाo +B
(o.0) euub
(48)
0,
and the augmented probability transition kernel is given by
P (s' (s,a)= = (s's a)
if E S
for all (s, E S A x [H]:
Eves Pa 18,a), if s' Saug
(49a)
Gunrs (5') (aug, a) 1l (s' Saug)
for all (a, h) A [M]:
(49b)
Let (()) be the corresponding optimal deterministic policy of (()).b in the original state space.
Compute // choose the stepsize
(,) (1) - 02 g((((1), d, 2,14 )
KOH + d (s, a)
where g( d, μ)
Σ
Σ
h= (a,a)ESxA K=H + BNZZ [J% (8,a))
Here, d7, a) is computed via (42) for h and (43) for 2. If g(((() d, (.
(t) < 2HSA then exit for-loop. // stopping rule
Update // Frank-Wolfe update
(1+1) (1 - ar) 1b (t) + 1l , Pb
10 Output: the exploration policy explore E B (1 [π] and the associated weight explore 14b
(1)
Algorithm 6: A pessimistic model-based offline RL algorithm (Li et al., 2022).
Input: a dataset D; reward function r. Let Ko denote the number of sample trajectories D.
2 Subsampling: run the following procedure to generate the subsampled dataset Dtrim
1) Data splitring. Split D into two halves: Dmain (which contains the first Ko/2 trajectories), and Daux (which contains the remaining Kn/2 trajectories); we let N (s) (resp. (s)) denote the number of sample transitions in Dmmin (resp. Da that transition from state at step
2) Lower bounding { (Nmaiin(s (s)) using Daux For each S and h H, compute
HS trri (s) = max Naux 10 N (s) log 000
(50)
3) Random subsampling, Let DDmain' be the set of all sample transitions (i.e., the quadruples taking the form (s, a. h. s')) from Dmain, Subsample DDmain to obtain Dtrim such that for each (s, h) E S x H.) Dtrim contains min(NNrrmm (s), (rTaainss) sample transitions
randomly drawn from D (We shall also let Nyri (s, a) denote the number of samples that visits (s, a, h) in Derim
3 Run VI-LCB: set D, = Dtrim, run Algorithm to compute a policy म.
21

---

Algorithm 7: Offline value iteration with lower confidence bounds (Li et al., 2022).
Input: dataset Do: reward function r;; target success probability 6. Initialization: VH++1 = 0. 3 for h H.... ..... , do
compute the empirical transition kernel Pn. as
if on Na(c.)) Σ a hi, = (s,,,,,))),
Pa 18,a)
(51)
clse,
where (n(s, = 1 ( ai, (i) (s, a, h)} and
(s)s)= = E [{ h:) = (s.1)).
for s E a do compute the penalty term (s, a) as
V(s,a, E Ax [H] (, a) min { cb log & (s
K
Vara (Vnt2) + aHH log K &
{V
Nn(s,a)
H.
for some universal constant cb > 0 (e.g. cb 16); set (s, a) max (ra(s, Pa V (, a), 0}.
for S do set (s))) max, (8, a) and (8) E max, Qn (8, a).
Output: {
E Analysis of Theorem
In this section, we present the proof for our main result in Theorem 1. Throughout the proof, we let (9h)ishs denote sequence of subsets obeying
d (s, = (a) and
H H h= (s.a)eSn.
max max HS (8.0)E9,
doll (8, a)
Σ
d (s, So,
(52)
out, K > Ci HASA log for some large enough constant ç₁ >> 0, then the claimed result in Theorem follows immediately from the main theory in Li al. (2023) developed for pure online exploration. As result, it sufficies prove the theorem by replacing Condition (24b) with
motivated by Definition 2. As
S 22
K log
K
(53)
8
throughout this section.
On high level, our proof comprises the following three steps:
Establish the proximity of joff (resp. d=)) and doff (resp. d²).
Show that the mixed policy iimitate is able to mimic and strengthen the offline dataset Doff while the mixed policy x explore is capable of exploring the part of the state-action space that has not been adequately visited by Dooff
Derive the sub-optimality of the policy returned by the offline RL algorithm (i.e., Algo- rithm 6) when applied to the hybrid dataset = Doff. Dinitatte U Den explore
In the sequel, shall claborate these three steps.
22

---

E.1 Step 1: establishing the proximity of बh (resp. ddtt) and d' (resp. d
To begin with, the goodness of the occupancy distribution estimators dM (ef. Algorithm 3) has been analyzed in Li et al. (2023, Lemma 4), which come with the following performance guarantees.
Lemma (Li al. (2023)). Recall that H A log HSA for some large enough constant > O. With probability at least - ö, the estimated occupancy distributions specified in Algorithm satisfy
E
E
(h a)
() S 2d (s, (e (8)
(54)
2
4N
4N
simultaneously for all (8, a. h) E A [H] and all deterministic policy E IT, provided that A log
HSA
k 2 Cw 1 g14
(55)
6
for some large enough constant CN > Here, (8, is some non-negative sequence satisfying
2SA
A3S
Σ (e)ssaa -
for all h E [H] and all deterministic Markov policy π.
Kon
N
(56)
We now turn to the estimator doff (cf. (15)) for the occupancy distribution of the offline dataset, for which begin with the following lemma concerning the proximity of da and do. The proof of this lemma deferred to Section G.I.
Lemma 2. Suppose that cott 2 48. With probability at least 58/3, one has
1 Joff (8, 3 hh ( a) S dh
log Koff
HSA 8
H4 log
HSA 8
SA K
joff a) < dh
Joff (8, a) + 5coff
+
(57)
N
simultaneously for all (s, (s,a, h) h) E Ax HH..
This lemma implies that: when deff (s,a) S log RSA H' log H54 SA the estimator Jeff (s, a)
Kot
K
might be unable to track do (s, a) in faithful manner. This motivates to single the following two subsets state-action pairs for which Joff (s, a) might become problematic at step h:
the set 9j (see (11) for the definition of Gi),, which corresponds to the set of optimal state- action pairs that even the true data distribution do.l cannot cover adequately;
another set 7,.m smalll defined as
Ta =
= (s.a): (s, S 10coff
log Koff
HSA 0
H'S
HSA
SA K
}
(58)
N
comprising those state-action pairs for which deft (s, a) might not be a faithful estimator of (off(s (s, a).
In what follow, we shall adopt the notation:
Tn = G U T.mllll
(59)
straightforward to demonstrate that:
For any (s, a) & T.small it is seen from Lemma 2 that
d (8, a) < 2ot (8, a) + 2
d off (s,a)
deth (s,a) < 2.pp (8,a).
(60)
For any (s, a) E Gn. Condition (52) tells us that
di (s) < (o)ad (s,
(61)
23

---

As consequence, any a) $ Th necessarily obeys
d (s, a) S C* (o)) (s,0) s 20 (a)ak,
a (8, a).
(62)
Another useful observation that we can readily make is follows:
H
1
11 Σ
Σ
Σ
dh (8
Σ
th (s,
E
(8,a)
h=1 (s.n)ETR
h=1
(s.0)
1=1 (T,
< Ho Σ
Σ
(8,a)
1=
Ho Hoo
E
plf (s,a) (a xs))
(T.a)
log HSA
H A log
HSA
SA
Ho + CC 10coff
Koff
Ko
(C
HSA
4C* 5$ A log
HSA
S Ho + 10coff
= ō.
Koff
Kon
(63)
Here, the second and the third lines arise from Condition (52), the penultimate line invokes the definition (58) of T., whereas the last line is valid since N = K /3HH (see (14)).
E.2 Step 2: showing that imitate (resp. π explore) covers golf (resp. dm adequately
In this step, aim demonstrate the quality of the two exploration policies mimitate and π explore designed for different purposes.
Goodness of x imitate We begin by assessing the quality of the exploration policy imittate Towards this, we first make note the following crude bound:
( a)
< K H =; L. (s,a) a)
KmH + E Exiing (s)a)
RCH
In view of the convergence guarantees for FTRL ShwartzS 2012, Corollary 2.16), 2T Hya then running FTRL for Tmax iterations results in
that: if 1 2Tmu
log A
log
Tru
Joll (s, a)
Tmax
(s, a)
(a (8)
max a
T
Exway [df (s,)))))
T
K=H + E Exarge (d (s,
1=1
K HJ
1= aEA
2 2log A
KonH H
(64)
Tmax
for all E S and 1 < h z H. Therefore, recalling that 1 imitatte Jensen's 's inequality yield
1 Tmax n² and applying Time 21=1
H
Joff (s, a)
max aEA
+ E iimieess [d (s,
A=1
SES
Kon
H
Time
Joff (s.a) a)
max aEA Tiax
RoH + E Exae'' d as)
h=1 S
Tra
Toll (8, a)
2 2log A
(a s)
+ Ko H2
(65)
RoH + E Ex (8,
Tmax
h= (x.a)ESxA
t=1
24

---

where the second inequality results from (64). In addition, it follows from the stopping rule (37) that
d (s. ())
(a 8)
KmH + Bx (8, I 108SH.
(66)
N=1 (x
As consequence, combining (65) and (66) yields
do (s, a)
log A
Σ max aEA K + E Exx inhare do (s)
S 108SH + K=
max < 109SH, (67)
hE[H] #ES
provided that Tmax 2 2(KK0H log A. The fact that the left-hand side of (67) well-controlled
suggests that 7 imiitatee is able to cover doft adequately, crucial fact we shall rely on in the subsequent analysis.
Goodness of axplore Next, we turn attention to the other exploration policy axplore computed via Algorithm 5. The following performance guarantees have been established in Li et (2023, Section 3.2).
Lemma 3. The distribution yeepllore E (IT) returned by Algorithm 5 satisfies
H
dh a)
max
< 2HSA
KoOH + Egg cxpier [ (s, a)
1=1 (A.))ESAA
In light of the performance bound (17) for the subsequent offline RI approach, Lemma 3 suggests that x explore able to explore well with regards to the visitation of any policy т including the optimal policy n..
E.3 Step 3: establishing the performance of offline RL
Now, we can readily proceed analyze the performance of the model-based offline procedure de- scribed in Algorithm In this subsection, we abuse the notation to represent the empirical tran- sition kernel constructed within the offline subroutine in Algorithm 7, Additionally, we introduce S-dimensional vector di == [4h (s)]aEs.
E.3.1 Step 3.1: error decomposition
To begin with, we convert the sub-optimality gap of the policy estimate गे into several terms that shall be controlled separately. The following two preliminary facts, which have been established in Li at. (2022), prove useful for this purpose.
Lemma 4. With probability exceeding 1 5/3, has
Nmmain N
(s, a) 2 N
and
V V E
1 h H,
hib 8,a
where (s, a) is defined in line 7 of Algorithm 7. In view of Lemma 4, we can derive, for all j [H].
(d) V2
2
Σ
Σ
d (s, (8. 2 Σ
8.0
1sh22
2 Σ
Σ
V 2d0 (z) (s.) +2 Σ Σ
+2
of (s,
hxb2j st (S. (T)
hih2d (s.n)ET
2 Σ
Σ
2d (x)+
hch2j 81 (T)
25

---

S12SA Kon
53c 5 A"
1SA log 8
+4Σ Σ Jch2 (s.0)ET,
The (s,
N
Here, the second line comes from (62), whereas the third line is due to Lemma 1 and the basic fact that bn (s, a) I H (see line 7 of Algorithm 7). Substituting the definition of by, (see line 7 of Algorithm 7) into the above display and applying Lemma 4, we arrive at
(Cy' -F S Σ
Σ
V Sd (s, (,,,)CC(o))dd) (8, a)-
max a:(8.0)Th
h:h21
K Co log tx4 (ntimss,
OoHl log H No. (s,
}
min
(V
Var (al)o (vo+1) +
Cb log K 5
SH Kon
53cg 11 St A
K log
+4H
Σ Σ
Th (s,0))
N (8, a) +
N
8
lob25 (s.a)eT
(68)
where we recall that 9b > 0 is also an absolute constant used to specify (n(s, a). is worth noting that the right-hand side of (68) involves a variance term Var P. (11s.)) (Vi+1) w.r.t the empirical model P. As it turns out, the following lemma established in Li et al. (2022, Lemma 8) makes apparent the intimate connection between Var V. (Ve+1) and Varpa(-)e.a) (V++1)-
Lemma 5, With probability exceeding 1 1 8/3, we have, for all (s, (s, E S Ax x [H].
Var s,0) (V++1) - 2Varr (Pn+1)= + 10H2 log K 8
3.77.i a)
Substituting the result of Lemma 5 into (68) leads to
8H2SA K
530g H A1
log K
Vi vリa S n + 72
+
(69)
N
where
m = ΣΣ
max a:(s,0)ETr
2 2d (s,
(s, a) min {
{V
Narim (s,
2cp log o Var Varpa (v++1) +
40p H log H
Ntrim (s, a)
hib2j
cb log K 3 Nerim (s, a) +
72 = 4H Σ Σ
The (o)a)
Jch2j (s.0)TT,
This leaves with two terms to bound, which we shall accomplish separately in the ensuing two steps.
E.3.2 Step 3.2: controlling 71 in (69)
Regarding the first term 71 on the right-hand side of (69), let first define the set In as follows:
IA = { (s.a)) Eganyyitton [J (8, a)
2
(70)
N
where we remind the reader that & = c. 53 13 log this set, we can deduce that
HSA for some constant C9 > 0. Armed with 3
Σ Σ
V 2d (8, (s.a)(((a))) (o))
max Ti
hch2j
Σ hcb2j
Σ²
(a(o)ddf (s.a)
ai(s,a)EIa
26

---

joft h s, a)
< 20)
+
Σ
Σ
max
KonH
N
hch2j
Ko
1t - mimiittt
d
(s)
(O)
& N
K
where the first inequality arises from (62), the penulminate line utilizes the definition (70) of In. and the last line comes from (67). This in turn allows us to upper bound "1 as follows:
HK 2cb log 5 --rrpp(-lsaa) (Vnt1) + (iiii(s,0) a)
40,H log B H N a)
n Σ 1ch2
E² 2 max a:(s.a)EZz
22 (s, (s, a) min {
Σ (.
22 (s, (d) (s,a)
max
hch2j 8
V (s,,) (i) {v
2cg log HK Nitim(s, Varp, (Vut1) + 4opH log H No.i (s, a)
$ ΣΣ Σ max a(s.a)EIz
1:h2) &
1
+ 436611
+
N
Kon
(a (Vh+1) +
K
< 16cb Σ
max a:(s,a)EZn.
Joft 220% (s, (o))) (s. (s.a)V
Ntrim (s. a) + 1/H
log?
6
kih2j
+ 436111
(o)
5 N
(71)
K
where the last line makes use of the elementary fact that min { y #1 I ztu for any x, y. u, w > 0.
yow
In addition, note that for any obeying E
Bragimmt [s) 2 E/N, we have
( [s)]
rfff zoff (s) + KonB
[d7 + Ko
upior (d% (s)]
6
6
HSA log 8
K B Sppiititnne
[d)(s)]
K
2 Ce
H
A
N
where the last line invokes the definition of In and the choice NH k forwardly justified using elementary concentration inequalities (see, e.g., Alon and Spencer (2016, Appendix A.))) that: with probability exceeding 8/10.
then be straight-
1 ([(EE"(s) (s)]
1 S A log 8 _
HSA
N (s)
2
holds simultancously for all (s, h) S [H]. and result,
Nari (s) 2 Nau (s) 10 Na log 2
HS 1 Na)
(s)
1 E[
1
2
1 Kon E Eniiiiio [s)].
24
Moreover, for any (s, E In (ef. (70)), one can invoke Lemma obtain
E
E inittrn (x)
inittaee (T)
3N
Applying the same concentration of measurement argument as above further reveals that:
N (s,a) 2 K on E Eangiiitnn [dh (s, a)] 2
Kong E Bangimmtttn
[1% (8. a)]
24
72
any (s, a) E In. Substitution into (71) then gives
Var Varpa(-le,a) (v++1)+ +
log² 2 K
71 S 16cb Σ Σ
max 20 (s, (O) (s.a) a:(s.ajEI,
1/H
K'on Tiagemmttn (x,
8
hihbj
72
27

---

+ 4436112 (0)
1
(72)
N KonH)
By virtue of the Cauchy-Schwarz inequality, we can further derive
Pa (Vn+1) H
Σ
Σ
max Vax (o) (s,a),
1/H
1 Konny bitbare (3. 72
h:h2i
( Joft (s,a)
Σ Jch2s
Σ 5,a
(Patz)+ dh (s, (8) (Var (Var) + H):
Σ hzhad
Σ
max
1/H
Kon Kon Exaaginion (x,
72
(73)
To further control this term, we resort to the following lemma, whose proof is deferred to Sec- tion G.2.
Lemma 6. With probability at least - 5/6, we have, for all j E [H].
Σ E
dh (a, (Vn+1) s 5H?
h.h25 8,0
provided that
K 2 cII (11 A 1155 A1" log K
K
Keff (n A) log
for some sufficiently large constant C11 0. Putting Lemma 6 together with (67) and (73), we obtain
Var Pr(l.a))) (Vn+1) + H
H3SC(
Σ E max (s,a) a)
2
1/H + 7/ Koon Eejiiiiina [d (s, a))
Kon
(74)
Substitution into (72) results in
H3SC'(a) log K 8 + (C
71 S
Kon
Kon
(75)
Akin to (72) and (75), we can also focus on the offline dataset and obtain
(O)C*(O)
K
(H&SCC
71
Kfff
log
Koff H
(76)
Combine (75) and (76) to arrive
(a)
K
HaSC
K log²
+ HH2 E +
71 miin
log²
2
Kon
8
Koli
8
minf Mon, Kfff }
(²)C*(a)
log² 2 K
24
max Kon, Koffj
min (Kon, Koft H
(O)
K 8 + (0)
K + Koff
log²
N
min{ Kon KoffH
(77)
E.3.3 Step 3.3: controlling 72 in (69)
We now turn attention to the term 722 the right-hand side of (69). Akin to (72), we can deduce that
log
72 < 16
Σ
Σ
c (s)
+ +436H²
+
T cpppion (3,
N
Kon
1xh2d (T.R)ETH
73
(78)
28

---

The Cauchy-Schwerd inequality then tells us that
Σ
Σ
Th. (s,a),
KonE,
pppto d (s.
h:b2) (T,a)ETa
72
dy (s, a)
Σ E Mihiz (H,a)ETa
E (
1 +
72
1 KONTE x pappore
hihi (a,a)eTs
2HSA
6V K
Σ
(s,a)
hih2i (s,a)ETa
22SA(22 + HSE/N)
s 16
Kon
where ā is defined in (63). Here, the penultimate line invokes Lemma 3, and the last line is valid since (according to Lemma and (63))
Σ Σ (s, = Σ
Σ
The (s,
1cbid (s.a)eTa
hch2 a1,, (s))
HSE N
2 Σ
Σ
df (s, (s))
h:b2j (a))
HSE
$ 28 +
N
Substitution of the above inequality into (78) yields
2H²SA + HSE/N)
HK +
E N
1
72 S 960b
log
436H²
+
(79)
Kon
5
Kon
E.3.4 Step 3.4: putting all pieces together
To finish up, combining (69).(77) and (79) reveals that: with probability at least 5, one has
(T(() - (p) (d VT V$)
1 (3 K 5
H log K 8
H* K Koll Kon
24
Kon + Koff
Kon
H8 (O K
H+ AC
log K 8
oK
KK
S A H A3C
K (O) A)
log
+
N
8
min min(Kon KOn Koff) }
H3SC* (a) log² K
HASAo #r Kon
HOS A + H051AAC*
H²S(C*(a) + A)
+
log +
Kon + Kolf
Kon
Kolf
(80)
where the last inequality holds true long min Kolf Kon) Z HSA. Taking the right-hand side of (80) to no larger than E, we immediately establish Theorem under the sample complexity assumption in this theorem.
29

---

Proof for the stopping criterion and the iteration complexity for solving (20b)
Feasibility of the stopping rule (37). We first demonstrate that the stopping rule (37) can be satisfied by some mixed policy, namely,
H
Joft (8, a) Ex [d (s,aa)
min (TT(T
B Bawa et (1s))
S 108SH.
(81)
h=1
KH
Towards this end, we focus attention on analyzing a specific choice of the mixed policy μ - the one that represents the mixed policy that generates the offline dataset. Making use of the definition (15) of joff gives
2N a))
(s,a) Kofff
log HSA 8
H A log o
HSA
SA K
})
joff dh (s,
1
2 Coff
Koff
Koff
N
3
log USA
H A log
HSA
SA
K ))
S 3d (s, (..
ch
(s, Coff
Koff
N
2
H A log
HSA 8
SA
S 3dh (s, a)
off Ch
a)
Coff
(82)
N
K
where the second line relies (94). This combined with Lemma 1 results in
Toff (s, a) dh
(a
E
non (d)(s, a)]
(xa)ESXA
KH
(aaa 3d (s,a) a) 1 ( (s,a) 2 conl { 11'"A log
N
+
SA
KJ
(83)
1 KH + Errnyon (s, 20% (s,
(s.0)ESxA
Moreover, inequality (56) tells us that: when do (s, 2 foff large enough constant coff > O, we have
1145 A log
B54
SA K
for some
N
B di (0) (z. &
4SA K'on
27 4 H
log
HSA 8
1
2 E
d% (8)
2
h roff
(s,
4N
N
2
(84)
In turn, this implies that
3d (s, )) I (s, f { 1155 A log HSA
Σ
{a(ass) 8)
N
KH + Brayer (d% (s, 20 (8, a)
(s,a)ESxA
4N
3d loff (s. o) 2 3 coff {
11 H+ A log
N
K
KH + doff (s,a)
(sa)ESxA
30 (s,a)
Σ (
(a
12S.
(85)
off (s.a)
Consequently, combine (83) and (85) to yield
joff (s,
ΣΣ E (1())
12SH,
(86)
E Eawyor [d (s, a)]
KH
which clearly validates the claim (81) (with an even better pre-constant).
Before moving forward, we single out one useful property that arises from the above arguments:
Exnyer [T] a)) > jff (s,a).
(87)
12
To prove the validity of this claim (87), it suffices to make the following two observations:
30

---

14 A log a84
When da (s, a) 2 3 Coff
+ k ) it has been shown in (83) and (84) in
3
N
conjunction with (82) that
Exanyor 1o (8, a)] 2 11 (s,a) 2 M (s,
(88)
12
When di (s, a) < 3 Coff H" log uga
$.1 Kun
one sees from (82) that deff (s, a) 0,
and hence (87) holds true trivially.
Iteration complexity. Suppose that the stopping criterion (37) is not yet met in the k-th iteration, namely,
Joff (s, a)
E Ba (o (11e)
108SH.
(89)
KH + E 22))0))))) 0% (s. (s.
1=1 SES
It can be easily that
KH + Tm( (s, a)) ( (s,
1
E
Ba
+
(115)
KKH Bainaact) [d (s, as))
b=1
H
KH Bxanuo (dh a)] 2 as,a)
B
aaw (e (11s)
KH + BRi-a(t) [d (s)
A=lsES
(drt (s., a))²
1
E
aomth (11b)
KH + E Batnpalts
[dg (s)
h=1
H
Joff (s,a)
Joff (s. a)
3
E
SoonT (11))
KH + E Exingte
12% (s(
KH + E Exg
lo
d (s.
> 36
1=1
SES
Jo.t (s,a)
3
Σ
E
c- (11)
KH + E (upte) 12% (s,
SES
H
2olt (s,a)
goff (s, a)
3
E
(-1s)
11
$ 36
RH + Eximaat)
10% (s,
KH + B Barngelt) d (s,
Aml
SES
To. (s, a)
3
E
108SH
(11a)
E (iptt)
(d% (s,
SES
H
Joff (8,
2
2
E Pawn
(-la)
KH + Earoypt0)
[2h (s, a)]_
(90)
7=
SES
where the first inequality follows from the choice (32) of π (R), the second inequality is a consequence of the relation (87), and the last line makes use of (89). This in turn allows one to demonstrate that
(2 (k) (s,a) E. Ex
2i (s. a)) a)))aa (s) (s,
E
am
+
(+1s)
(K'H + +E, E
[o (s, (s,a)))
h
SES
H
(KH + Th (s, a) (o (s,
(1)
H
(1rr + E Br 1 (s, a)) J (s, a)
Σ
Σ SES
a (-18)
(R2m + Exeraaess 1 (8, (s,a))
amm (+1o)
(R2 + Exe [dpz (s, ss,a))
SES
H
( (s,
E
Bawn (+1s)
108SH,
1
(dy. (s, a)]
Am SES
KH
where the last line results from (90) and the condition (89). We can then readily derive
doft (s, a)
Joff (s, a
aann (11))
E amm 1t (+1+))
KH + E B ddy (s, a))
1 E E ((+)) [d (s, a)]
h=1.ES
h=
RH
31

---

H
E (ximuttt (s, Bxi (d% (s, a)] )
aapt (s
x (-1b)
KH + B day (s,a)] K B Bx (6 (s,
4=1 SES
H
a (dh
d (M) (s, a) Exing(nn) [d] (s, a]] dh
(s,a)
E3
amit (-1s)
KH + Bxtraps))) (ay (s, a)]
KH + +B ( 1% (s, a)))
H
4/ (s, Exinalta)
(1)
[d% (s, do (s,
aooth (11s
KH + 1 (p(((()) [ (s,a)]}
h=
a² (dhh
(k) (s,a) Exengils [dt]' (s, a)]) 2off (s,a)
E
(-10)
1
+ ( [d] (s,
+ E I'
[d] (s a)])
1=1 SES
KH
KH
108.$
S
107S²
2 10888SH 10 a2
(91)
K3H²
K
K
where the third line relies on the update rule (35), and the last line utilizes the choice (36) of a.
In summary, the above argument reveals that: before the stopping criterion is met, each iteration is able to make progress at least as large as (91). Recognizing the crude bound
H
Roff (s) + u [d (s, [s.a)]
H
E RaNy (-1a)
S
KKH
E
B
(-1s)
2o (s,a) S KH2
A= SES
KH
h= sES
that holds for any μ E (TI), one can combine this with (91) to conclude that: the proposed proce- iterations, as claimed.
dure terminates within O K* H²)
$2
G Proofs of technical lemmas
G.1 Proof of Lemma 2
The Bernstein inequality combined with the union bound tells us that, with probability at least
1 - 6/3,
2. (s, a) Kon
dell (s. (ss.a)log-
log
HSA 5
6 6log HSA
ooff (s, a) s 6/
Koff
Kofff
coff
(s)
24 HSA 8
(92)
2
Koff
holds simultaneously for all (s, a) E 8 A x [H) where the last line invokes the AM-GM inequality. This in turn reveals that
4Nofff (s,a) 16 16log HSA
4Noff (s,a)
48 18g HSA
I 0h (s. <
off
(93)
offff
Koff
Koff
Koff
As result, we can show that:
If No. (s.a) (s.a)
log USA Ka
H* A log
HS4
SA Km for some Coff 2 48, then one has
Coff
N
2Nooff (s,
(s,a)
I doll (s,a)
and
Golt (s,
(94a)
offfff
Kfff
Koff
Joff dn
(s, a) < do (s, a) S 3d (s,a).
(94b)
3
If instead Ng (s.a) R
log USA
+ H H log Uad
Rw). then one has Joft (s. a) = 0.
< Coff
Rat
and therefore,
1 201l
coll (s, 20= h (s,a),
32

---

4. (s, a)
48 log Kofi
HSA
log
HSA
H A
log
HSA
SA
4 (s,a) v
Scoff
5
+
Koff
Koff
N
K
llog Koff
HSA
S log
HSA
SA Kon
dg (s. a) + Bcolf
N
Taken collectively, these inequalities demonstrate that
{ log off
HSA 8
H4 A log
HSA
SA
80 ( (s. S ditt (s, a) S بेh (s.a) 5comf {
(95)
N
Kon
provided that Coff 0 is sufficiently large.
G.2 Proof of Lemma 6
Before embarking on the proof, let us introduce several notation. For each 1 S h I H, define
Ph E RR5 and di E R$ such that: for all S,
Ph (s, Ph |s,
(s))
and
(s) dz (s, (s)). (s)).
(96)
To begin with, it can be easily seen from (69) and the basic fact Var Pa( (V++1) I H² that
log K 8 Nirim a) +
V4'' V
8H Σ
(2, (s, a)
max a:(s,a)EI,,
4H E
Σ
The (s,a) Nerim (s, a) +1
log K 8
Hlc
log 8
K
(97)
1ch2j (T.0)ET
holds for any j E Note that we have bounded in (79). We then need to bound 73.
With regards to the term 73: invoking similar arguments for (72) leads to
7s S 64
Σ
Σ
max y 22d (s..))((a)) (s)
log K
+ +4H+SS
1
1/H
1 K
Kon R Emii (1 (8,
Kon
h:h21
72
K (a) Foll (s, a) log 5
2 Σ
Σ
dh (8,
ΣΣ
max
1/H +
1 KoKK E Emiiesse d7 (s,a)
-4H2SC
N +
Kon
kch2j
5,a
72
13HASC* (T)
K log 5 + +4H
E N
< 768cb]
(98)
Kon
Kon
where the second step invokes the Cauchy-Schwart inequality, and the last line comes from (67). Similarly, repeating the above argument but focusing on the offline dataset, we can derive (which omit for the sake of brevity)
33 S 64c, H Σ
Σ>
Σ
max / V2dg.' (s, (o) a
Joff (s.a)
log K
& + +4H 4HH
1/ H +
K
off ooff (s,a)
N
Koff
72
E max (o ). (s. a) log 8 + 4H
< 64ccH
2 Σ
Σ
d ())
Σ
Σ
(
+
1/H + 72 k joff (s,
Kof
hch2j
8,a
< <768cb
6H+SC* (a)
K log 8
+ 4H2
E +
(99)
Koff
N
Rof
where the last line makes use of (86).
33

---

Combining (98), (99) and (79) with (97), we can show that
(ds V vØ S min
768cb
13H
log 8
K
+H
SC
$ N
1 )
7680b
6H*SC*
log
K
K
Koff
2H3 + HSE/N)
HK
96cb
log
+ 436HH
Kon
N
m
(Kon Kof)H
Glce S
Aa
K
log
N
8
1
(100)
for all 1 isjs H, with the proviso that
S=
K I C10
log"
K
5
(a)
K
8 S C10
K
HSC*(o) K
á S C10
Kofi
HSAlog K
S C10
Koff
for some sufficiently small constant c10 > 0. As a consequence, we can demonstrate that di (s, (s,a) Varaaaaattl (V++1)
Σ Σ
h:h2 8,0
Σ
di (s, a) (1snn) Var (Vitt Vo+t))
hehij
8,0
$ 2 +
di (s, (s)) BPa, [Vi+1 Vitt]]
kch2.
41 + H Σ (d%.) PF [Vitt Vn+1]
kch2)
4H² + Σ (dF
[Vi+1
Vat1 S S5H2
(101)
for all 1 $ H. Here, the third line in (101) applies the following fact
ΣΣ dh (s, aar,, (Vi+1)
Σ Th Th (s, (PP (s, Vitt1 Vitti) - ((P) (s, Vi+t)))
=
Σ Σ CR (s, (P (s.-), Vit vi+1) - -(Vi(s) - r T (
Σ dn (s) (PF (s.-), Vidi Vitt) - (V)) 2H
Σ (dF') P (Vi+z Vi+ti) Σ (d T (V, vit) 2H
Σ ( (Vi Vitt) Σ (ax') T (V, Vi 2H²
< 2H2
where the second identity comes from the Bellman equation; the third relation uses the fact that V < H, and the penultimate line holds since (d))) Pp = (() the penultimate step in (101) is due to (100); and the line in (101) holds true since (d%)) pg (d
34


Reviews:
[{"review_id": "0JmKqgmMQH", "reviewer": "Reviewer_Lcd6", "summary": "This paper studies hybrid RL (online RL with offline data) in the specialized setting of tabular MDPs, while providing tighter bounds than prior works. Namely, they seem to propose a novel and weaker concentrability notion called single-policy partial concentrability. The algorithm takes three stages: 1. estimate occupancy distribution, 2. perform online exploration, 3. invoke offline RL for policy learning. ", "questions": "1. How is f_{mixed} is defined in Eq. 26 and 27? I couldn't find a clear definition.\n2. For Eq. 27, isn't the minimax-optimal result by Azar supposed to be $H^2 SA/\\epsilon^2$ trajectories? \n3. Where does the current analysis break when extending to more general MDPs, like linear MDPs? ", "limitations": "See above.", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "1. A weaker notion of partial coverage for hybrid RL is proposed in Def 2.\n2. While I'm not familiar with all previous hybrid RL works, this paper seems to be one of the first that obtains better sample complexity in online RL, in the tabular setting. ", "weaknesses": "1. While the paper is reasonably clear, I think the presentation is a bit incomplete and can be made more succinct. For instance, the main algorithm of the paper is not even in the main paper and requires reading the appendix.\n2. The algorithm runs in three stages and is quite complicated for solving the tabular MDP problem. Also, I feel uneasy about Stage 1 of the algorithm, since estimating occupancy distributions is a hard problem in practice, eg. the hardness of DICE algorithms in offline RL is precisely due to this.\n3. Can you discuss the computationally complexity of each stage, compared to optimal tabular methods like UCBVI? In Line 340, it says the FW subroutine might be expensive, but can you be more concrete and derive a big-Oh running time? My worry is that this paper, while obtaining better instance-dependent statistical bounds sacrifice the practicality of the algorithm. There are also no experiments to validate the practicality of the new coverage assumption.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for the helpful comments and valuable feedback. \nPlease find below our point-to-point response, which will also be incorporated into the final paper.\n\n1. In the original submission, the main algorithm was included in the appendix due to the page limit. \nIn the final version, we believe that we will have more space, and will definitely include the main algorithm in the main text.\n\n2. Since we do not need an explicit expression for all occupancy distributions, this stage for estimating $d^{\\pi}$ is actually not harder than the remaining stages with respect to both the sample and computational complexities.\nSpecifically, for estimating $d^{\\pi}$, the sample and computational complexities are $O(K^{\\mathsf{on}})$ and $O(K^{\\mathsf{on}} + H^7S^8A^3)$, respectively.\nIn comparison, the sample and computational complexities of Stage 3 of the offline RL procedure are $O(K)$ and $O(KH)$, respectively. \nLet us explain these complexities of our algorithm in a little more detail below. \n\n (1). According to Eq. 14, we collect $O(K^{\\mathsf{on}})$ trajectories for this procedure, which implies its sample efficiency.\nNote that the current number of trajectories used for this stage is chosen for ease of presentation, and it suffices to use even a even smaller sample size to estimate $d^{\\pi}$.\n\t\n (2). As for the computational complexity of the occupancy measure in Stage 1, we need to first estimate the transition matrices $P_h$'s with $O(K^{\\mathsf{on}})$ complexity. In the following stages, we need to call Algorithm 3 to estimate $\\widehat{d}^{\\pi}$  for each $\\pi$ we encounter. When computing $\\pi^{\\mathsf{imitate}}$, we need to calculate $\\widehat{d}^{\\pi}$ for  $T_1=T_{\\mathsf{max}}\\times T_2$ times, where $T_2$ denotes the number of iterations for calculating $\\mu^{t+1}$ in Eq. 20b; \n\t\tin comparison, the number of estimating $d^{\\pi}$ to yield $\\pi^{\\mathsf{explore}}$ in Eq. 22 is much smaller.\nFor each $\\widehat{d}^{\\pi}$, it needs $O(HS^2A)$ computation. \nAs discussed in the following item, with a slight modification on the target Eq. 18, we can make $T_{\\mathsf{max}} = \\widetilde{O}(H^2S^2)$, and it takes $T_2=O(H^4S^4A^2)$ iterations for calculating $\\mu^{t+1}$.\nIn summary, the total computational complexity is $O(K^{\\mathsf{on}} + H^7S^8A^3)$.\n\t\t\n\n3. With a slight modification on the target Eq. 18 as follows\n\\begin{align}\n\\mu^{\\mathsf{imitate}}\\approx\\arg\\min_{\\mu\\in\\Delta(\\Pi)}\\sum_{h=1}^{H}\\sum_{s\\in\\mathcal{S}} \\max_{a \\in \\mathcal{A}}\\frac{\\widehat{d} _ {h}^{\\mathsf{off}}(s,a)}{\\frac{1}{KH} + O\\big(\\frac{1}{SH}\\big)\\widehat{d} _ {h}^{\\mathsf{off}}(s,a) + \\mathbb{E} _ {\\pi^{\\prime}\\sim\\mu^{\\mathsf{explore}}}\\big[\\widehat{d} _ {h}^{\\pi^{\\prime}}(s,a)\\big] + \\mathbb{E} _ {\\pi^{\\prime}\\sim\\mu}\\big[\\widehat{d} _ {h}^{\\pi^{\\prime}}(s,a)\\big]},\n\\end{align}\nwe can find a good enough $\\pi^{\\mathsf{imitate}}$ with $T_{\\mathsf{max}} = \\widetilde{O}(H^2S^2)$ for $\\eta \\asymp \\frac{1}{H^2S^2}$ and $O(H^4S^4A^2)$ Frank-Wolfe updates for $\\alpha \\asymp \\frac{1}{H^3S^3A^2}$.\nThen we have the following computational complexity for each stage: $O(K^{\\mathsf{on}} + H^7S^8A^3 + K^{\\mathsf{off}}H)$ for Stage 1, $O(H^7S^7A^3)$ for Stage 2, and $O(KH)$ for Stage 3.\nHence, compared to the typical offline RL algorithms like UCB-VI (which has $O(KHS^2A)$ computational complexity(, the computational complexity of our algorithm is better when $K $ becomes sufficiently large. \nWe will add a remark to discuss the computational runtime in the final paper.\n\n4. $f_{\\mathsf{mixed}}$ is defined on the left-hand side of Eq. 26 as follows: \n\\begin{align}\nf_{\\mathsf{mixed}} := \\frac{H^3SA\\min\\\\{H\\sigma, 1\\\\}}{\\varepsilon^2} + \\frac{H^3SC^{\\star}(\\sigma)}{\\varepsilon^2}.\n\\end{align}\nWe will make this definition more clear in the revised paper.\n\n5. Regarding the minimax sample complexity limit, we note that: (i) for time-homogeneous MDPs (so that the transition matrix is the same across all steps), the minimax sample complexity is $H^2SA/\\varepsilon^2$; \n(ii) for time-inhomogeneous MDPs, the minimax sample complexity should be $H^3SA/\\varepsilon^2$, which is the case considered herein. \n\n\n6. It is possible to extend the idea developed in this work to accommodate linear MDPs. \nThere are several important steps needed. Firstly, we need to find an efficient estimation method for the transition kernels of  the linear MDP. Secondly, we need to use the estimated MDP to imitate the behavior policy of the offline dataset and also learn a good exploration policy.\nFinally, we need to invoke (or develop) a sample-optimal offline RL algorithm in the case of linear MDPs to find the optimal policy based on the collected sample trajectories.\nAccomplishing all these details needs substantial efforts, which we leave for future work. "}, {"review_id": "Q8jpoXpqLW", "reviewer": "Reviewer_Ukmm", "summary": "This paper studies a tabular reinforcement learning setting where the agent tries to learn the optimal policy by both offline data (obtained by exploiting the optimal policy) and online exploration. A three-stage algorithm is proposed to obtain such a policy, which has lower sample complexity compared to pure online and pure offline reinforcement learning algorithms.", "questions": "Line 120: what do the authors mean by a \"unknown\" initial state distribution? Does its value depend on specific applications?\n\nLine 126-127: What is the difference between a mixed deterministic policy and a randomized one? Could the author provide a small example to elucidate their difference?\n\nDefinition 1: I think the definition of $C^\\star$ is associated with some policy $\\pi^\\star$. If so, the authors should specify this.\n\nLine 195: How should one decide which samples belong to the first/second half? Or can we divide the two halves arbitrarily?\n\nIn the \"Imitating the offline dataset\" step, the authors appear to assume that the offline dataset is obtained by executing an optimal policy. (1) If so, I think the authors should formalize this assumption. (2) Also, this assumption is strong (where the information of the optimality is leaked to the decision maker). Could the authors justify this assumption?\n\nIt feels fishy that authors claimed that \"Towards this end, it suffices to invoke the reward-agnostic online exploration scheme\" in line 250, while they assumed that \"the reward function is fully revealed upon completion of online data collection\" in line 118.", "limitations": "Please see the weaknesses above.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 3, "strengths": "This paper proposes the first algorithm for the hybrid RL setting that can achieve lower sample complexity than pure online and pure offline algorithms, which is innovative and inspiring. Overall, The writing is clear.", "weaknesses": "There are a few crucial technique details that are not clear enough, which should be well justified. Please see my questions below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for the helpful comments and valuable feedback. \nPlease find below our point-to-point response, which will also be incorporated into the final paper.\n\n1.  When we say the initial state distribution is ``unknown'', we mean that this distribution is not revealed to the learner {\\em a priori}. \nAnd yes, the unknown initial state distribution could depend on specific applications. We will make these more clear in the final paper. \n\n2. For the bandit case with horizon length $H = 1$, a mixed deterministic policy is equivalent to a randomized one.\nWhen $H > 1$, these two cases are not equivalent.\nFor example, the mixed deterministic policy $\\mu(\\pi^1) = \\mu(\\pi^2) = \\frac{1}{2}$ has no corresponding randomized one,\nwhere\n\\begin{align}\n\\pi_1^1(a_0 | s) = 1,\n\\pi_2^1(a_0 | s) = 1,\n\\qquad\\text{and}\\qquad\n\\pi_1^1(a_1 | s) = 1,\n\\pi_2^1(a_1 | s) = 1,\n\\end{align}\nfor $S = 1, A = 2, H = 2$ with $P(s | 0, \\cdot) = 1$, \nwhich yields $P_{\\mu}(\\{s, a_0, s, a_0, s\\}) = P_{\\mu}(\\{s, a_1, s, a_1, s\\}) = \\frac{1}{2}$. \nWe will discuss these differences in the final paper. \n\n3. Yes, $C^{\\star}$ is defined with respect to some $\\pi^{\\star}$. We will specify this more clearly in the final paper.\n\n4. As defined in Eq. 12 in the original paper, $\\mathcal{D}^{\\mathsf{off}, 1}$ (resp. $\\mathcal{D}^{\\mathsf{off}, 2}$) consists of the first (resp. last) $K^{\\mathsf{off}}/2$ independent trajectories from $\\mathcal{D}^{\\mathsf{off}}$. And yes, we can divide the two halves arbitrarily and independently.\n\n5. Thanks for raising this point. It is noteworthy that we didn't assume that the offline dataset is obtained by executing an optimal policy. \nIn fact, we impose no requirement on the offline dataset, and our algorithm works for an arbitrarily given dataset. \nWe shall make these points more clear in the revised paper. \n\n6. Note that in prior RL literature, \"reward-agnostic'' or \"reward-free'' refers to the case where online data collection does not utilize any reward information (but reward information is revealed in the final policy learning stage). This is consistent with our setting and algorithm: in Stage 1 and 2, we do not utilize any information about the reward, while reward information is only provided in Stage 3 to compute the optimal policy via offline RL. We will make these terminology more clear in the final paper. "}, {"review_id": "0GrfeOmToN", "reviewer": "Reviewer_GVvQ", "summary": "This paper investigates tabular reinforcement learning (RL) in a hybrid setting, where both an offline dataset and online interactions with an unknown environment are available. The main question addressed is how to effectively use online data to enhance and complement the offline dataset for policy fine-tuning. The authors propose a three-stage hybrid RL algorithm that outperforms pure offline RL and pure online RL in terms of sample complexity. The algorithm does not require reward information during data collection.\n", "questions": "- Empirical estimation of the occupancy distribution in Sec. 3.1 can have high variance. How does the proposed approach handle this issue?\n- Why do we need to imitate the offline dataset? What if the dataset is collected with random policies?\n- The analyses are conducted in the tabular case? How to extend them to continuous state/action spaces?\n", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- Innovative approach: The paper introduces a novel three-stage hybrid RL algorithm that combines online and offline data to improve sample complexity in tabular RL.\n- Theoretical contributions: The authors develop a new notion, single-policy partial concentrability, which captures the trade-off between distribution mismatch and lack of coverage. They provide theoretical results that demonstrate the statistical benefits of hybrid RL compared to pure online and offline RL.\n", "weaknesses": "- The paper provides no empirical evaluations or demonstrations of the proposed algorithm. Neither does it shed light on the design of practical algorithms.\n- There remain some issues unsolved in the paper. See the questions for details.\n\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for the helpful comments and valuable feedback. \nPlease find below our point-to-point response, which will also be incorporated into the final paper.\n\n1. This work is mainly our theoretical attempt towards understanding the provable benefits of hybrid setting. \nWhile the current algorithm is not yet practically efficient, \nwe hope that our design principle might shed light on the design of more practical yet sample-efficient solutions. \n\n2. We use the estimation method proposed in Li et al. 2023, which is completed through estimating the transition probability model $P_h$ by exploring all state-action pairs. \nThis approach turns out to be sufficient in handling the variance issue.  \n\n3. In some applications, the offline dataset might be obtained by \"experts'', meaning that it might have (much) higher quality than random dataset. \nIf this happens, it becomes beneficial for us to imitate the behavior of offline dataset. \nAs a more technical example, if $C^{\\star}(\\sigma)$ defined in Eq. 10 is small (corresponding to near-expert data), then we can benefit through imitating the offline dataset (see the discussion below our main theorem).\nOn the other hand, we also agree that if the dataset is collected with random policies and when $C^{\\star}(\\sigma)$ is large, there is no need to imitate the offline dataset. \nIt boils down to how to balance the effort spent on imitation and the effort spent on exploration. \nOur scheme turns out to be provably order-wide sample efficient for this purpose. \n\n\n4. Yes, we focus on the tabular case here. \nOne way to deal with the continuous state/action spaces is to resort to function approximation. \nIt is possible to extend the idea developed in this work to accommodate linear MDPs. \nThere are several important steps needed. Firstly, we need to find an efficient estimation method for the transition kernels of  the linear MDP. Secondly, we need to use the estimated MDP to imitate the behavior policy of the offline dataset and also learn a good exploration policy.\nFinally, we need to invoke (or develop) a sample-optimal offline RL algorithm in the case of linear MDPs to find the optimal policy based on the collected sample trajectories.\nAccomplishing all these details needs substantial efforts, which we leave for future work. \n\n\nReference:\n\n[Li et al. 2023] Li, G., Yan, Y., Chen, Y., and Fan, J. (2023). Minimax-optimal reward-agnostic exploration in reinforcement learning. arXiv preprint arXiv:2304.0727."}, {"review_id": "nG3pKxA5N4", "reviewer": "Reviewer_R4EB", "summary": "This paper studies hybrid reinforcement learning under tabular MDPs, where the agent has access to both a given offline dataset and online interaction with environment. This paper first proposes an interesting notion of single-policy partial concentrability, which relaxs previous concentrability assumption and accounts for the trade offs between distributional mismatch and partial converage. Then this paper proposes a novel three stage algorithm, which can automatically identify the optiaml trade offs. Then the paper provides a sample complexity upper bound. The sample complexity result shows the benefit of hybrid RL compared with pure online or offline RL.", "questions": "As listed in weakness.", "limitations": "There is no negative impact in this work.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The notion of single-policy partial concentrability is interesting and reasonable to me and relaxs previous concentrability assumption. \n\n2. This paper proposes a novel three-stage algorithm for hybrid RL, which can automatically identify the optiaml trade offs between distributional mismatch and partial converage. Intuitively, the agent can imitate the offline dataset to collect partial informative data, and explore the unknown data which is not covered by offline dataset.\n\n3. When compared to pure online or offline results, the samplexity complexity result shows the benefit of hybrid RL. \n\n", "weaknesses": "1. This paper mentions Frank-Wolfe-type subroutine in introduction and conclusion in main body. However the Frank-Wolfe-type subroutine is even not discussed in main body. Also, pseudocode of algorithm 1 is deferred in Appendix, which make it not easy to read and follow the idea of algorithm.\n\n2. This paper only provides theoretical results without experiment results.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for the helpful comments and valuable feedback. \nPlease find below our point-to-point response, which will also be incorporated into the final paper.\n\n1. Frank-Wolfe-type method is an efficient first-order iterative algorithm to solve constrained convex optimization problems. We will make sure to introduce it in more detail in the final version. In the original submission, the main algorithm was included in the appendix due to the page limit. \nIn the final version, we believe that we will have more space, and will definitely include the main algorithm in the main text.\n\n\n2. This work is mainly our theoretical attempt towards understanding the provable benefits of hybrid setting. \nWhile the current algorithm is not yet practically efficient, \nwe hope that our design principle might shed light on the design of more practical yet sample-efficient solutions. "}, {"review_id": "6RHLWmAlVD", "reviewer": "Reviewer_Vg7V", "summary": "The paper proposes a new three step algorithm in the hybrid RL setting for tabular MDPs that improves in terms of sample complexity on the pure online and as well as the pure offline setting. The notion of single-policy partial concentrability is introduced which offers an intuitive concept that connects the sample complexity of pure online and pure offline RL. The algorithm leverages results from reward agnostic exploration to explore the parts of the state-action space that are missing from the offline dataset and then applies an offline learning algorithm to  find an $\\epsilon$-suboptimal policy. The sample complexity result is compared to existing results and the algorithms advantages and limitations are discussed.  ", "questions": "How does the sample complexity result from \"Hybrid RL: Using Both Offline and Online Data Can Make RL Efficient\" (Song et al., 2023) compare to the presented result? The mentioned paper looks at bilinear models so similarly to Wagenmaker and Pacchiano is not specifically designed for the tabular case. ", "limitations": "The limitations are discussed. An empirical comparison of the presented algorithm with other hybrid RL algorithms would have been interesting but seems out of scope of the presented work.  \n\nNegative Societal Impact - Not Applicable", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "The paper is well written and reads itself easily, the algorithm and the sample complexity result are introduced in a digestible manner without loss in rigor.\n\nThe concept of single-policy partial concentrability captures the two problems with offline datasets well (lack of coverage and mismatch with the state-action distribution of the optimal policy) and provides a neat connection between sample complexity results of pure online and pure offline approaches. \n\nFor the tabular setting without function approximation the sample complexity result is SOTA. \n\nThe advantages and limitations of the algorithms are extensively discussed.", "weaknesses": "The motivation/intuition why the number of samples coming from the offline dataset distribution needs to be increased with the imitation exploration policy is not clear to me. Why is the offline dataset and the dataset collected with $\\pi^{explore}$ not enough ?\n\nI find the notation used for the single-policy partial concentrability coefficient slightly confusing: \n\n- In equation 10 I would write $\\\\{G_{h}\\\\}_{1 \\leq h \\leq H} \\in G(\\sigma)$\n- in equation 11 I would write $G(\\sigma) \\coloneqq \\\\{ \\\\{ G_{h}\\\\}_{1 \\leq h \\leq H} | \\forall 1 \\leq h \\leq H , G_h \\subseteq S \\times A, ... \\\\} $", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for the helpful comments and valuable feedback. \nPlease find below our point-to-point response, which will also be incorporated into the final paper.\n\n1. If the number of the newly explored samples is smaller than the number of offline data samples, then the offline dataset and the dataset collected using $\\pi^{\\mathsf{explore}}$ are enough. \nIn comparison, if the number of the newly explored samples is larger than the number of offline data samples, then the offline dataset is not enough in achieving our performance bounds. \nFor instance, if $C^{\\star}(\\sigma) < A$ for some $\\sigma < 1/H$, then we need the newly explored dataset to include some imitation effort in order to enlarge the offline dataset and achieve better performance.\nWe will make this point clear in the revised paper. \n\n2. Thanks for pointing out the notational issue, which we will revise accordingly in the revised paper. \n\n3. We have compared our result with this reference in Appendix A with the following text ``Song et al. (2022) mainly focused on the issue of computational efficiency, and the algorithm proposed therein does not come with improved sample complexity.''\nWe will add more discussion and comparison with this reference in the revised paper. \n\n4. Yes, our current work is mainly our theoretical attempt towards understanding the provable benefits of hybrid setting. \nWhile the current algorithm is not yet practically efficient, \nwe hope that our design principle might shed light on the design of more practical yet sample-efficient solutions. \n"}, {"review_id": "OfOhE5KRs1", "reviewer": "Reviewer_sEvV", "summary": "The authors prove that augmenting an offline dataset with online data collection leads to improved sample complexity compared to online and offline RL in the tabular setting, under the condition of single-policy partial concentrability. This is an extension of previous work on single-policy concentrability, relaxing the requirement that the offline dataset cover the full state-action space of the optimal policy. The authors propose a three step algorithm, given a budget of $K^{on}$ online data collection steps - spend the first third estimating occupancy distributions, the next two thirds on imitating the provided dataset and an exploration focused policy respectively, and finally finding a policy using standard offline RL on the original and collected datasets. This algorithm can be run in polynomial time using a Frank-Wolfe approximation to find the optimal policies in the second step. ", "questions": "- What is the definition of $f_{mixed}$ in section 4?\n- Intuitively, what do the terms $\\gamma_1$ and $\\gamma_2$ represent? ", "limitations": "Yes", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The algorithm and proof are both novel to the best of my knowledge, and address an important question in RL theory. \n- The result is a general improvement over previous work, relaxing the coverage requirements without imposing new constraints or significant additional computation.  \n- The paper is generally well written without many typos or errors. ", "weaknesses": "- Some of the choices in the algorithm could be better justified in the main text. Without referring to the Appendix the motivation for the imitation and exploration datasets is difficult to understand. \n- While the Frank-Wolfe updates proposed include a polynomial stopping rule, it's not clear how feasible this bound would be in any realistic task.\n\nMinor:\n- Section 2 (Line 123): noation -> notation", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thanks a lot for the helpful comments and valuable feedback. \nPlease find below our point-to-point response, which will also be incorporated into the final paper.\n\n1. In the original submission, the main algorithm and several associated discussions were included in the appendix due to the page limit. \nIn the final version, we believe that we will have more space, and will definitely include the main algorithm and more discussion in the main text.\n\n2. We would like to note that: while this polynomial stopping looks complicated, it is actually easily computable and checkable. \nIn addition, we have also discussed the feasibility of the bound Eq. 36 for solving Eq. 20b in Appendix F. \nNote that our paper is mainly to show that there exists a polynomial time algorithm that can achieve provable statistical benefits; in practice, there could be more flexible stopping rules that achieve even more appealing performance.  \n\n\n3. We note that $f_{\\mathsf{mixed}}$ is defined on the left-hand side of Eq. 26, which is given by \n\\begin{align}\nf_{\\mathsf{mixed}} := \\frac{H^3SA\\min\\\\{H\\sigma, 1\\\\}}{\\varepsilon^2} + \\frac{H^3SC^{\\star}(\\sigma)}{\\varepsilon^2}.\n\\end{align}\nWe will make this definition more clear in the final paper. \n\n4. Informally, $\\gamma_1$ represents the error from the state-action pairs that are well explored by offline dataset,\nand $\\gamma_2$ represents the error from the state-action pairs that are poorly covered by offline dataset.\n\nReference:\n\n[Li et al. 2023] Li, G., Yan, Y., Chen, Y., and Fan, J. (2023). Minimax-optimal reward-agnostic exploration in reinforcement learning. arXiv preprint arXiv:2304.0727.\n\n"}]

Author rebuttal:

Meta-review: This work studies the setting of hybrid RL by providing tighter than existing bounds for tabular MDPs in the case that offline data and online interactions are allowed. The bounds are based on a novel and weaker than existing concentrability notion called single-policy partial concentrability that characterizes the statistical complexity of Hybrid RL in this scenario. Although there was no uniform agreement, the reviewers generally believed this to be a worthwhile contribution to appear at Neurips 2023.
Decision: Accept (poster)