Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs
Authors: Kevin Tan
Wei Fan
Yuting Wei
Venue: NeurIPS 2024 poster (2024)
Keywords: hybrid RL
reinforcement learning
linear MDPs
minimax
Primary area: reinforcement_learning
TL;DR: We achieve the tightest bounds/regret available in the literature thus far for hybrid RL in linear MDPs, without single-policy concentrability, that improve upon the offline-only and online-only minimax error/regret bounds.

Abstract: Hybrid Reinforcement Learning (RL), where an agent learns from both an offline dataset and online explorations in an unknown environment, has garnered significant recent interest. A crucial question posed by Xie et al. (2022) is whether hybrid RL can improve upon the existing lower bounds established in purely offline and purely online RL without relying on the single-policy concentrability assumption. 
While Li et al. (2023) provided an affirmative answer to this question in the tabular PAC RL case, the question remains unsettled for both the regret-minimizing RL case and the non-tabular case. In this work, building upon recent advancements in offline RL and reward-agnostic exploration, we develop computationally efficient algorithms for both PAC and regret-minimizing RL with linear function approximation, without requiring concentrability on the entire state-action space. We demonstrate that these algorithms achieve sharper error or regret bounds that are no worse than, and can improve on, the optimal sample complexity in offline RL (the first algorithm, for PAC RL) and online RL (the second algorithm, for regret-minimizing RL) in linear Markov decision processes (MDPs), regardless of the quality of the behavior policy. To our knowledge, this work establishes the tightest theoretical guarantees currently available for hybrid RL in linear MDPs.

Hybrid Reinforcement Learning Breaks Sample Size Barriers in Linear MDPs
Kevin Tan, Wei Fan, Yuting Wei Department of Statistics and Data Science The Wharton School, University of Pennsylvania
Abstract
Hybrid Reinforcement Learning (RL), where an agent learns from both an offline dataset and online explorations in an unknown environment, has gameered signif- icant recent interest. A crucial question posed by Xie al. (2022b) is whether hybrid RL can improve upon the existing lower bounds established for purely of- fline or online RI. without requiring that the behavior policy visit every state and action the optimal policy does. While Li et al. (2023b) provided an affirmative answer for tabular PAC RI. the question remains unsettled for both the regret- minimizing and non-tabular cases. In this work, building upon recent advance- ments in offline RL and reward-agnostic exploration, we develop computationally efficient algorithms for both PAC and serett-mnnmizing RL with linear function approximation, without requiring concentrability on the entire state-action space. We demonstrate that these algorithms achieve sharper error regret bounds that are no worse than, and can improve on, the optimal sample complexity in offline RL (the first algorithm, for PAC RL) and online RL (the second algorithm, for regret-ninimizing RL) in linear Markov decision processes (MDPs), regardless of the quality of the behavior policy. To knowledge, this work establishes the tightest theoretical guarantees currently available for hybrid RL in linear MDPs.
1 Introduction
Reinforcement learning (RL) holds great promise in attaining reliable decision -aaking in adaptive environments for broad range of modern applications. Typical RL algorithms often require an enor- mous number of training samples, motivating a line of recent efforts to study the sample efficiency of RI. algorithms. There are two mainstream paradigms of RI., distinguished by how samples are collected: online RI. and offline RL. In online RI,, an agent learns in a real-time manner, exploring the environment to maximize her cumulative rewards by executing a sequence of adaptively chosen policies (e.g. Azar et al. (2017); Jin et al. (2018); Sutton and Barto (2018); Zhang al. (2023)). Whereas, in offline RL, an agent has only access to a pre-collected dataset, and tries to figure out how to perform well in different environment without ever experiencing it (e.g. Jin et al. (2021b); Lange et al. (2012); Levine et al. (2020); Li et al. (2024)). Online methods are often but offline methods often impose stringent requirements on the quality of the pre-collected data.
To address the limitations of both, the setting hybrid RI (Song et al., 2023; Xie al., 20226) has recently received considerable attention from both theoretical and practical perspectives (Amortila et al., 2024; Ball al., 2023; Kausik et al., 2024; Li al., 2023b; Nair al., 2020; Nakamoto al., 2023; Song et al., 2023; Tan and Xu, 2024; Vecerik et al., 2017; Wagenmaker and Pacchiano, 2023; Zhou et al., 2023). In hybrid RL, an agent learns from a combination both offline and online data, extracting information from offline data to enhance online exploration. Theoretical guarantees for hybrid RL algorithms can be categorized on: (1) the type of function approximation considered, (2) the level of coverage required by the behavior policy, (3) whether it improves on the minimax lower bounds for online-only and offline-only learning, and (4) whether they minimize regret or obtain a PAC guarantee. We elaborate below, and summarize the prior art in Table 1.
38th Conference on Neural Information Processing Systems (NeurIPS 2024).

---

Paper
Function Type
Concentrability?
Improvement?
Regret or PAC?
Song et al. (2023)
General
Required
No
Regret
Nakamoto et al. (2023)
Tan and Xu (2024)
General
Not Required
No
Regret
Amortila et al. (2024)
Wagenmaker and Pacchiano (2023)
Linear
Not Required
No
PAC
Li al. (2023b)
Tabular
Not Required
Yes
PAC
This work
Linear
Not Required
Yes
Regret, PAC
Table I: Comparison of our contributions to previous work in hybrid RL.
While much of the prior literature (Amortila et al., 2024; Nakamoto et al., 2023; Song et al., 2023; Tan and Xu, 2024; Zhou et al., 2023) tackles general function approximation in hybrid RL, they either require stringent concentrability assumptions on behavior policy quality, or fail to obtain tight theoretical guarantees. Under such single-policy concentrability assumptions (explained below), Xie et al. (2022b) show the optimal RL algorithm is either a purely offline reduction or a purely online algorithm if the agent can choose the ratio of offline to online samples, rendering the benefits of hybrid RL questionable. Without this assumption, Li et al. (2023b) show guarantees for PAC RL that improve over lower bounds for offline-only and online-only RL, but only for tabular MDPs.
This paper focuses on obtaining sharper theoretical guarantees in the setting of linear function ap- proximation in linear MDPs. First proposed in Jin et al. (2019); Yang and Wang (2019), linear MDPs parameterize the transition probability kernel and reward function by linear functions of known fea- tures (e.g- pre-trained neural embeddings). It has been extensively studied due to its benefits in dimension reduction and mathematical tractability both the online and offline settings (Du et al., 2019; Duan and Wang, 2020; He et al., 2023; Hu et al., 2023; Jin et al., 2019; Li et al., 2021; Min et al., 2021; Qiao and Wang. 2022: Xiong et al., 2023; Yang and Wang. 2019; Yin et al., 2022; Zanette et al., 2021). Despite these efforts, hybrid RL algorithms for linear MDPs (Amortila et al., 2024; Nakamoto et al., 2023; Song et al., 2023; Tan and Xu, 2024; Wagenmaker and Pacchiano, 2023) have suboptimal worst-case guarantees (Table 2), which raises the question:
Is it possible to develop sample efficient RI algorithms in the setting of hybrid RL that are provably better than online-only and offline-only algorithms for linear MDPs?
1.1 Hybrid RL: two approaches
To answer the question above, we introduce two types of approaches addely- in hybrid RL.
The offline-to-online approach: Most of the current literature (c.g. Amortila et al. (2024); Nakamoto et al. (2023); Song et al. (2023); Tan and Xu (2024)) initializes the online dataset with offline samples to perform regret- seigeeimin online RL. We refer to this as the offfine-to to-online ap- proach. This method is simple and natural, and as the algorithm optimizes the reward during each online episode, it is suitable when the agent has to perform well during online exploration.
The mnline-to-offinee approach: However, if our goal is to output a near-optimal policy, espe- cially in real-world situations in medicine and defense, randomizing between policies can be subop- timal or even unethical. Recently, Wagenmaker and Pacchiano (2023) and Li et al. (2023b) propose using aaward-ggoottcc online exploration explore parts of the state space unseen by the behavior policy, to construct a dataset that is especially amenable to leverage the sharp performance guaran- tees of offline RL. We refer to this as the online-to- to-olffie approach. While this approach does not optimize the "true reward"' during online exploration, it avoids the need to deploy mixed policies to achieve a PAC bound, allowing for the deployment of fixed, and thus more interpretable, policies.
1.2 Our contributions
We propose an mnline-to-ofline method called Reward-Agnostic Pessimistic PAC Exploration-iiittaiizee Learning (RAPPEL) in Algorithm 1. It employs reward-agnostic online exploration enhance the offline dataset, then learns a policy through a pessimistic offline RL. algorithm. Algorithm significantly improves upon the sample complexity of the only dedicated hybrid RL algorithm for línear MDPs (Wagenmaker and Pacchiano, 2023) by factor of at least H² This performs no worse than the offline-only minimax- optimal error bound from Xiong et al. (2023), with the potential of significant gains from online data. This is the first work to explore the online-to-offlin approach in linear MDPs. In addition, we propose an offline-to-online method called Hybrid Regression for Upper- Confidence Reinforcement Learning (HYRUL.F) in Algorithm 2, where one warm-starts an
2

---

Upper Bound
Lower Bound
Offline (Error)
vd= E Ext I (St, an Ixa
dd 2h-1 By (0 da Minggr
CC H /Not (Xiong al., 2023)
C & H Noot (Xiong al., 2023)
Online (Regret)
WP (He al., 2023)
V (Zhou al., 2021)
Result
Hybrid
d' / (Wggemmakrr and Pacchiano, 2023)
(Online-to-oflinee Emrrr)
Cost (Naa JdH min Gost (Nat). H//Nest + v dogd min H) H//oon (Alg. 1)
Hybrid
O vd H' (Nakamoto al., 2023; Song al., 2023)
(Offlin-tt-onling Regret)
vIC* Con (Zn(X)))) (X))) H (Amortila al.. 2024)
v (Kon )dH' /Na + ydndd Non (Tan and Xu, 2024)
N Ventt (o (Xoa) |2dH /NoR + Vooodd (Alg. 2)
Table 2: Comparisons of our results the best upper and lower bounds for offline and online RL, and existing results for hybrid RL, in linear MDPs. Often, offline data is cheaper or easier to obtain. When this happens, Noff
Non. and the online term in our results (depending on Non) dominates.
online RL algorithm with parameters estimated from offline data. In addition to improving the ambient dimension dependence, this algorithm enjoys a regret (or sample complexity) bound that is worse than the online-only minimax optimal bound, with the potential of significant gains the offline dataset is of high quality (Agarwal et al., 2022; He et al., 2023; Hu et al., 2023; Zhou et al., 2021). Our result demonstrates the provable benefits of hybrid RI. in scenarios where offine samples are much cheaper or much easier to acquire.
To the best of our knowledge, bounds of hybrid RL algorithms (in the same vein as Li et al. (2023b)) in the presence of function approximation, without any explicit requiremen requirements the quality of the behavior policy, and with both the offline-to-online and online-to-offlin approaches. Our results are also, at the point of writing, the best bounds available in the literature for hybrid RL in linear MDPs (see Table 2).
are the first to show improvements over the aforementioned lower
Technical contributions. In this work, build on recent advancements in offline and online RL, demonstrating that intuitive modifications suffice to achieve state-of-the-ar sample complexity for hybrid RL in linear MDPs. At a high level, our sample efficiency gains are achieved by decomposing the error of interest into offline and online partitions, and optimizing them respectively, following the same idea in Tan and Xu (2024). Below, we summarize our specific technical contributions.
1.
We sharpen the dimensional dependence from d to d and Can(X via projections onto those partitions. The former is accomplished in Algorithm 1 by Kiefer- Wolfowitz in Lemma 1, and in Algorithm 2 by proving sharper variant of Lemma B.1 from Zhou and Gu (2022) in Lemma 18, using this in Lemma 14 to reduce the dimensional dependence in the summation of bonuses, which helps achieve the desired result.
2. We maintain H dependence for the eтror or regret for both algorithms, which is non- trivial, in Algorithm I and for the offline partition in Algorithm 2 by combining the total variance lemma with novel truncation argument for "bad" trajectories in Lemma 17,
2 Preliminaries
2.1 Basics of Markov decision processes
An episodic MDP is tuple M = (8, A, H. (PA) (ra) where S is the state space, A the action space, H the horizon, (Pr) k-1 the collection of transition probability kernels TP, 8 A ASS), and (rx H the collection of reward functions Thk S A - [o. 1]. A(-) is the collection of distributions over a set. At each h E [H] = (1,..., H). an agent observes the current state Sy. E S, takes action a A according to Ta S - A(AA) and observes the reward Th and next state 8h+1 Pn( (-1 8h, a.). We write II for the set of policies π = {mn) with value and Q-functions
for every (s, E S x [M]: and for every (8, a, h) E S
(T(()) = E. E rwlsp = s], A x [M] (7 a)
E M Tw/sh 8, a, a).
(2)
n = [ 1ー-1 is the optimal policy attaining the highest value and Q-functions, and we write V* = ( and Q* = {Q+) for the optimal value and Q-functions. We consider the setting of hybrid RL, where an agent has access two sources of data:
3

---

Nof independent episodes of length H collected by a behavior policy T where the n-th
sample trajectory is a sequence of data (s(") aa") ri SH .H ,H' ( 1);
(n) (n) (n)
oon sequential episodes of online data, where at each episode n. = 1, Non. the algorithm
has knowledge of the Not offline episodes and the previous online episodes 1,.... n
The quality of the behavior policy Tr is measured by the all-policy and single-policy concentrability coefficients proposed by Xie et al. (2023); Zhan et al. (2022):
Definition 1 (Oceupancy Measure). For policy π {m its occupancy measure d'
hd corresponds to the collection of distributions over states and actions induced by running within M, where for some initial distribution and $1 ~ p, we have
dy (s, == P(s = s. s,
$1 p.
Definition 2 (Concentrabilitty Coefficient). The all-policy and single-policy concentrability coeffi- cients of ग with regard to the occupancy measure μ = [un) of a behavior policy Th ure
Call == sup sup (%(s,a) h,a, (s) and C* sup h.s, (s,
(s.a)
(4)
Policy learning and regret minimization. Hybrid RL aims to either learn an e-optimal policy Ω such that V - -v² < with high probability, to minimize the regret. Here, the regret of an online algorithm L : H - II is (T) := E (V* - r( We write T Non interchangeably for the number of episodes taken by regret-minimizing online RL algorithm.
2.2 Linear MDPs
Throughout this paper, we study linear MDPs, where the transition probabilities and rewards are linearly parametrizable as functions of known features. This was first proposed by Jin et al. (2019); Yang and Wang (2019), and further studied in He et al. (2023); Hu al. (2023); Wagenmaker and Jamieson (2023); Wagenmaker and Pacchiano (2023); Xiong et al. (2023); Zanette et al. (2021).
Assumption (Linear MDP, Jin et al. (2019)). There exists a known feature map o S x A - Rd, d unknown signed measures jhh (p (1) ,... ((((()) over S for each h, and an unknown vector On RR such that for any s, a, we have Pa(- s, a) <(o(s, a), (n(()), rn(ss,) = (ő(s, a), 0n) Assume [Ø(s, a)ll & for all s, a, and max (S)Il 10,
for all h.
This allows for sample-efficient RL for a few reasons. Firstly, linear MDPs are Bellman complete (Jin et al., 2021 a common assumption for sample-efficient RL in the literature (Duan and Wang. 2020: Fan et al., 2020: Munos and Szepesvári. 2008). Secondly, the value and Q-functions are linearly parametrizable in the features, allowing one to learn them via ridge regression. This allows for sample-efficient online (He al., 2023; Hu al., 2023) and offline (Xiong et al., 2023; Yin et al., 2022) RL with function approximation. However, existing guarantees for hybrid RL in linear MDPs (Wagenmaker and Pacchiano, 2023) are loose (Li et al., 2023b), inspiring our work.
Further notation. Write 6n, = o(s)), ,aa%)) for the feature vector at episode n and hori- >n &n, + AI be the co-
zon h. Let As >n @n, n.A + AI and Aoff,h variance matrices of the entire dataset and the offline dataset respectively, and Ω the set of all covariates. We consider two kinds of variance-weighted covariance matrices, namely Et n,h = E On. [V Vitaa (5), ag) + AI and Σ,,,- = Σx n.A On, + AI, where [VA 1 a max {1, [ary, Vi++1] (s, a)} is the truncated variance of the optimal value function (where s, are random variables) and a-2 is the variance estimator from He et al. (2023).
n.h
2.3 Exploring the state-action space
We aim develop efficient hybrid RL algorithms for linear MDPs that do not rely on single-policy concentrability over the entire state-action space, which entails that the behavior policy covers every state-action pair that F visits. A natural idea from Li et al. (2023b) to partition this space into a component that is well-covered by the behavior policy, which we call the offline partition Xon. and a component requiring further exploration, which we call the online partition Xon- Based on this partition, similarly to Tan and Xu (2024), the estimation error or regret of hybrid RL algorithm can be analyzed on each component separately. We define Xmu U Xoi = [H] x S A, with their images under the feature map offf = Span( (xXot,,))))))] ]e][H] S Rd and o = Rdd being subspaces of dimension doft and don respectively. Write Part Pon for the orthogonal projection operators onto these subspaces respectively. Let > denote the k-th largest eigenvalue
(X)o,,))))(() S

---

Algorithm Reward-AAgnan Agnostic Pessimistic PAC Exploration-iiitiaiizee Learning (RAPPEL)
1: Input: Offline dataset Duft, samples sizes Non, Nott feature maps @%, tolerance parameter for reward-agnostic exploration т.
2: Initialize: 1/1)) Ø vh E [H], X = 1/2../..... Ö(vd).
3: for horizon = L, H do
4: Run exploration algorithm (OPTCOV, Wagenmaker and Jamieson (2023)) to collect co-
variates A, such that max ex 6% (A,, + AI + Aoit,))=' T.
5: end for
6: Output: के from running a pessimistic offline RL algorithm (LinPEVI-ADV+, Xiong et al.
(2023)) with hyperparameters X, 32 on the combined dataset Dott u (D/, Non)
he[H]]
of a symmetric matrix M. We borrow the definition of partial offline all all-policy concentrability.'
(on)) == max 1/ Ad., (E,,, (Ponn (Poft (Potth)) (b.) ]T),
(5)
from Tan and Xu (2024), where we use the convention that Coff (2) the inverse of the don-th largest eigenvalue of the covariance matrix of the projected feature maps. Similarly, the partial all-policy analogue the coverability coefficient from Xie al. (2022a) is Con (Xaa) == inf max 1/>a... (Ea; [(Po[ on (Pono))) (o)
0. This corresponds to
(6)
As we shall see, these quantities characterize the estimation enror of our proposed algorithms.
3 Algorithms and main results
We provide two algorithms with improved statistical guarantees to tackle the unsolved (Table 2) problem of achieving sharp guarantees with hybrid RL in linear MDPs, with different approaches:
1. Performing reward-agnostic online exploration (Wagenmaker and Pacchiano, 2023) to aug- ment the offline data, then invoking offline RL (Xiong et al., 2023) to learn an e-optimal policy on the combined dataset, in the same vein of Li et al. (2023b). This is Algorithm 1.
2. Warm-starting an online RI. algorithm (He et al., 2023) with parameters estimated from an offline dataset to minimize regret, in Song et al. (2023), with details in Algorithm 2.
3.1 Offline RL after online exploration
Algorithm collects online samples informed by the degree of coverage (or lack thereof) of the offline dataset Doe with reward-agnostic online exploration algorithm called OPTCOV from Wa- genmaker and Jamieson (2023). OPTCOV explores so that the smallest eigenvalue of the covari- ance matrix, Amin (Ax), is no smaller than a tolerance parameter 1/T. We then learn policy from the combined dataset using a minimax-optimal pessimistic offiin RL algorithm from Xiong et al. (2023), LinPEVI-ADV+. To employ OPTCOV, one requires modified analogue of the full-rank covariate assumption from Wagenmaker and Pacchiano (2023) that ensures that the MDP is "ex- plorable" enough. This assumption only imposed for Algorithm 1.
Assumption 2 (Full Rank Projected Covariates). For any partition Non U X.at [H] x SxA. Con (Xon) < oc, or equivalently that inf min Ad_., (Laz, [[Eaal(Ponn (P))o
= X > 0.
Informally, this states that for any partition, there exists some "optimal exploration policy" that ensures that the projected covariates onto the online partition have the same rank its dimension at every timestep. In practice, this is achievable for any linear MDP via projecting the features onto the cigenspace corresponding the nonzero singular values. We can then establish the following:
Lemma (Partial Coverability Is Bounded In Linear MDPs). For any partition Xott: Xmn. it satisfies that Con (X.n)) don- Also, there exists least one partition such that Cott (Xatt) = O(d).
The proof of this lemma is deferred to Appendix D. This result allows us to bound the error on the offline and online partitions by the dimensionality of the partitions, instead of the coverability coefficient. Define aoll == Non/ N, Gon == Non/ N, and the minimal online samples for exploration
N (* min N s.t. inf max ot (N A1) Aoo) Φ
Aet 0e
We now have, with full proof in Appendix B and sketch at the end of the subsection, the following:
'Some authors regard "partial" as synonym of "single- "single-policy" and "full" a synonym of "all- call-policy". We use the term "partial" to refer to concentrability or coverability over only part of the state-action space. There is always a partition so that the partial all polpioyy concentrability coefficient is less than the full single-polis concentrability coefficient (with larger online partition), and the former can be finite when the latter is infinite.
5

---

Theorem 1 (Error Bound for RAPPEL, Algorithm 1). For every 8 E (0,1) and any partition
Nott Non, when choosing T & (mmxx(dou/ Non, Coft (NoH) N/t }), RAPPEL achieves w.p. 1 1 8:
H s * || sh an an)ll ( bnnn)
Vi2 vs x vd
& vd
E [lo(s an) x
Conf (Xon))H
dondH4
Coff (Zon)
d d
1/" - Vs x min
(8)
Noft
Non
Nottoofff
Non
given N 2 max fa dou' Coft (Xot))=3 max (ax)NN*()) poly(d, H, coft (Kot); log 1/5))- This result, when applied to tabular MDPs with finite states and actions, yields:
Corollary 1. In tabular MDPs, for every ô E (0,1), 1), it satisfies that with probability at least 1 - 8,
(1) - (s) & S (V (oft(())t)) //ott + V Non
In sum, Theorem shows that with a poly(d, H) burn-in cost that is no smaller than N (the minimal online samples for any algorithm to achieve our choice of OPTCOV tolerance), we require only Coll (Non) d min(coa (Noa). H3/e² + d min H)/e²
trajectories to learn an (())-(((in))) policy. N from Wagenmaker and Pacchiano (2023), is essen- tially unavoidable in reward-agnostic exploration for linear MDPs. To compare with prior literature, our result leads to a better worst-case guarantee than the error bound of / /d=HT/N attained in Wa- genmaker and Pacchiano (2023) (by at least factor of H3/2), ) the only other work on hybrid RL in linear MDPs thus far. While we employ the same online exploration procedure, we combine our ex- ploration phase with an offline learning algorithm LinPEVI-ADV+ from Xiong et al. (2023) and con- duct careful analysis. When comparing with the offline-only and online-only settings, Theorem improves upon the offline-only minimax-optimal error bound of vd -
E, vd E on) I1 from Xiong et al. (2023) as consequence of Lff + oo Af the best offline-only er- ror bound is / /dH obtained under the "well-covered" assumption (Corollary 4.6, Jin et al. (2021b)) that Amin (Af,oft) >= (((/d)), Theorem 1 enjoys better dimension and horizon dependence as there is always partition such that doa Coft (Nus) < d and don min H) < d
The literature has experienced considerable difficulty in sharpening the horizon dependence to H in offline RL for linear MDPs. While Yin et al. (2022) and Xiong et al. (2023) provide minimax- optimal algorithms for offline RL linear MDPs, both only manage to achieve a H3 horizon de- pendence in the special case of tabular MDPs, even under the aforementioned "well-covered" as- sumption. We provide the same result in Corollary with proof deferred to Appendix C, but encour- agingly, hybrid RI. lets us bypass the "well-covered" assumption. In Appendix B and G. we use a novel truncation argument and the total variance lemma (Lemma C.5 of Jin et al. (2018)) to improve the dependence on H, but our result falls slightly short of / (Xott /Nott + dddddd/////
Computational efficiency. In terms of computational efficiency, Algorithm 1 inherits the computational costs of the previous proposed algorithms OPTCOV and LinPEVI-ADV+ (Wa- genmaker and Jamieson (2023); Xiong et al. (2023). OPTCOV runs in polynomial time poly(d, H. Con con (Kou), log 1/5), and LinPEVI-ADV+ runs in Ó(CHANIA)) time when the action space is discrete. Algorithm therefore remains computationally efficient in this case.
Requirement of choosing don. There is the caveat that we require the user choose the tolerance for OPTCOV. In practice, one can achieve this by performing SVD on the offline dataset and looking the plot of eigenvalues. One can also choose a tolerance of (dd/ min Noft, Nom)). but this would not achieve the reduction in the dependence on dimension from d² to Cotl (Xaa) )d, dond.
Practical benefits of the online-toooflliee approach. Algorithm outputs a fixed policy satisfy- ing a PAC bound. This enables policies to be deployed in critical real-world applications, such as in medicine or defense, where randomized policies from regret minimization are unacceptable.
Algorithm 1 works for reward-agnostic hybrid RL. The use of reward-agnoss online explo- ration in Algorithm enables one to use the hybrid dataset D to learn policies for different reward functions offline. As the online exploration is not influenced by any single reward function, the col- lected data satisfies good coverage for any possible reward function even if is revealed only after exploration, enabling one to use single dataset to achieve success on many diffferent tasks. This therefore also serves as an algorithm for the related setting of reward function is unknown during online exploration and only revealed to the agent after it.
hybrid RL, where the

---

Algorithm 2 Hybrid Regression for Upper-Confidence Reinforcement Learning (HYRULE)
1: Input: Offline dataset Duft, samples sizes Non. Nott feature maps Φh. Regularization parame- ter À > 0, confidence radii B, B, just = O.
2: Initialize: For h [H], estimate WI,,, W W1, Q1 1I,, from Doft and assign 1 + AI.
Σu, = Σ1, of + AI = EN EM= o T
3: for episodes = ..., T do
4: Update optimistic and pessimistic weights Wenh. We.h for all h.
5: if there exists a stage h' E {H] such that det (Ee,e)) 32 det (Eima .V) then
6: Update optimistic and pessimistic Q-functions (8, a), Qr (8, a), set last t.
7: end if
8:
for horizon h L...., H. do
9: Play action (t) < arg max, Qu,(
(1) a). receive reward h next state 8h-1 Estimate Tr or,h - max VH, 2d H 1 (1(()) on
(c)
11 P. update E,+1.h.
11: end for end for
12:
13:
Output: Greedy policy â = 7n,, Unif(T ...,, π QT..)
for PAC guarantee.
Proof sketch. The relation (7) in Theorem follows from invoking Theorem 2 from Xiong et al. (2023) with N > (2d A 1/H2, 31 = =(vvd. To establish (8), we first bound
(T) - (s) vd vv 1h dretPon
E"= max Vol / Φn + vVa max dn
V V dr.
As 1x-1 3 H² (see Xiong al. (2023)), it therefore boils down to controlling maxoned 0n AT,A on. Towards this, first, we make the observation that Lemma I suggests that Cou (oa) & dou- we run OPTCOV with tolerance O(max(don/Noo) con con (Xon) ) (oa)) on partitions where the above hold, in Lemma 5, we prove that maxøşed 0 A, On $ max (Noot//NNN don/Nan). This yields the cost (A )XoH)) dondH4 result.
To tighten the horizon dependence to H3, we employ an useful truncation argument. More specifically, from the total variance lemma (Lemma C.5 of Jin et al. (2018)), the average vari- ance V V is asymptotically on the order of H. We therefore define the sets of trajectories En(Os) {T E D DV VitVi (5% a > 111+bh. The cardinality of each set can be bounded Nuw Na))
by (& & NHH-5n, and so truncating at the level where N min( con don 1
leads ming.e4 07 oj NH min(
cust (xatt) dun )2. Putting things together yields the last Coff (Kort) ,d d result needed, and the theorem then follows.
Not
3.2 Online regret minimization
Thus far, we deseribed an online-to-offline strategy which collects online samples to augment the of- fline dataset. However, in certain critical cases, such as with doctor treating patients, performance- agnostic online exploration is untenable. One may wish to minimize the regret of the online actions taken while learning policy. We therefore explore another approach inspired by the work of Song et al. (2023); Tan and Xu (2024) that of warm-starting an online RL algorithm with parameters estimated from an offline dataset. We describe this in Algorithm 2, and show that hybrid RL enables provable gains over minimax-optimg online-only regret bounds in the offline-to tiline-to-online case as well.
In order to warm-start an online RL algorithm with an offline dataset, we modify LSVI-UCB++ from He et al. (2023) by estimating its parameters from Doft with the same formulas it would use as if it had experienced the Noff offline episodes itself. As Tan and Xu (2024) suggest, this can be understood as including the offline episodes in the "experience replay buffer" that the algorithm uses to learn parameters. The full version can be found in Appendix E Algorithm 4. Doing allows us prove a regret bound depending on the partial all-policy concentrability coefficient. Below we state our theoretical guarantees for this algorithm. The proof of this result is deferred to Appendix E, and a brief proof sketch is provided at the end of this subsection.
'He et al. (2023) write 0t, <- max(or,,, H, H..... not / VH. which we believe a typo. In the proof of Lemma B. after equation D.7, they state that 0 & o, H/H In the proof of Lemma B.5, the argument after equation D.22, particularly that |oo (sh. at.) & | (sh. 1 //H H, only holds if this is vH.
7

---

Theorem 2 (Regret Bound for HYRULE, Algorithm 2). Given any & E (0,1), 1), for every partition
Nott Xon if Non: Nott H2(1 the regret of HYRULE is bounded w.p. at least 1 - 8 by
Vcost (Xon) 2dH3 /n/ Not + d3 Reg( (on) S inf
Nou
Corollary By the
Algorithm achieves a sub-optimality gap w.p. 1 1-6:
(+) - (x) & inf ( S + don //on Nott.Nos
To understand this result, we first note that bounding the regret over all possible partitions yields an improvement over the vd H regret bound obtained by He al. (2023), as we can take Xnn bound. In the scenario where offline samples are abundant NoH = Ø to recover the vd (where Nofl Non), it is possible to achieve significant improvements over online-only learning. Furthermore, in view of Lemma 1, there always exists a partition such that Cofl Con(Xoo) (Rorr), don < d. This result therefore yields provable improvements over the minimax-optimml online regret bound in linear MDPs (Agarwal et al., 2022; He et al., 2023; Hu et al., 2023; Zhou et al., 2021).
Additionally, Theorem shows that Algorithm 2 attains the best known regret bound in hybrid RL for linear MDPs, as we illustrate in Table 2. The current best known result is that of Tan and Xu (2024), with dependence of /Cair (Kott) dH /Nott + dd Notably, we achieve the same reduction in the dimension dependence on the online partition from &f to don that Tan and Xu (2024) do by proving a sharper variant of Lemma B.1 from Zhou and Gu (2022) in Lemma 18, using this in Lemma 14 to reduce the dimensional dependence in the summation of bonuses. Song et al. (2023) and Amortila et al. (2024), on the other hand, have bounds on the order of C V and V(C* + Con (x)) dd H No. respectively. We produce a better bound than Amortila et al. (2024); Song et al. (2023); Tan and Xu (2024) by at least a factor of H by combining the total variance lemma and novel truncation argument that rules out "bad" trajectories in Lemma 17, which allows us to maintain a desirable 3 dependence on both partitions.
Computational efficiency. When the action space is finite and of cardinality |.A], the compu- tational complexity Algorithm 2 of order Ô (d H N N[A)).. as outlined He et al. (2023). Algorithm 2 is therefore computationally efficient and runs in polynomial time in this case. When the action space is continuous, one may need to solve an optimization problem over the continuous action space, making the computational complexity highly problem-depentee
Algorithm is unaware of the partition. Unlike Algorithm I, Algorithm 2 is fully unaware of the choice of partition, and there is therefore no need to estimate dou or any relevant analogue to the choice of tolerance for OPTCOV. The regret bound therefore automatically adapts to the best possible partition, even though Algorithm 2 unaware it.
Practical benefits of the offline-to-onliee approach. While Algorithm 2 only satisfies PAC bound with a randomized policy, it minimizes the regret of the actions it takes. This enables the algorithm to be deployed in situations where its performance during online exploration is of critical importance, c.g. in applications like mobile health (Nahum- Shanni et al., 2017).
Technical challenges. Although Algorithm 2 is straightforward generalization of LSVI-UCB++ in He et al. (2023), with En initialized with the offline dataset, we had to decompose the regret into the regret on the offline and online partitions to achieve the regret guarantee in Theorem 2. In the process, we faced the following challenges:
Bounding the regret the offline partition was challenging, the argument of He et al. (2023) was not applicable. Instead, we used truncation argument in Lemma 17 to bound the maximum eigenvalue of Eofl, maintaining a H dependence the offline partition. Bounding the regret the online partition allowed us to use analysis that was close to that of He et al. (2023). However, directly following their argument would have left us with a 3 dependence. To reduce the dimensional dependence to dond, we prove sharper variant of Lemma B.1 from Zhou and Gu (2022) in Lemma 18. We use this in Lemma 14 to reduce the dimensional dependence in the sum of bonuses, achieving the desired result. Without the above two techniques, one could have used a simpler analysis to achieve a far looser / Coft (xoH) H8N2 on. /Not + / d2 H regret bound by using the maximum magni- tude of the variance weights for the offline partition and the analysis from He et al. (2023) verbatim for the online partition, but this would not have yielded the same improvement.
We accordingly provide proof sketch below.
8

---

Proof sketch. We first adopt the regret decomposition as in He et al. (2023) and bound (())
(Tg(T)) & VT B 1/2 (1(2% an ]xx l2 + En, ي 2, (s% an (0) )xxx)xx 12.
1/2 (1)
then boils down to controlling the second and third terms separately. in Lemma 12 that the sum of bonuses on the offline partition can be bounded by Σn V dNou Non ma 0% Eod Further, Σn max V 10 Son &n & con (oon) Non
We prove
by Lemma 13. Putting things together, the second term can be controlled as Noff
3E 1 (s(h (())) 1 1l2 X
(1)
With respect to the third term, Lemma 14 (a sharpened version of Lemma E.I in He et al. (2023)), combined with the Cauchy-Sehhe Schwartz incquality, yields
En 12, 1/2 Lh dn (8h 4h L lla & d H + Bd H + Bv /ddonn HT + don H Ei, oi
(1) (1)
By the total variance lemma (Appendix B, He al. (2023)), En, or & Ö + 5 H1o). Taking everything collectively establishes the desired result.
4 Numerical experiments
To demonstrate the benefits of hybrid RL in the offline-to-onling and online-to-offline settings, we implement Algorithms and 2 on scaled-down Tetris environment (as in Tan and Xu (2024)). For the purposes of brevity, we defer the details of the environment to Appendix H.
Figure depicts the coverage (defined by 1/Amin 1/ (Aott), 1/Ad.n (Aon) )) achieved by the reward-agnostic exploration algorithm, OPTCOV, when initialized with 200 trajectories from (1) a uniform behavioral policy, (2) an adversarial behavior policy obtained by the negative of the weights of a fully-trained agent under Algorithm 1, and (3) no offline trajectories at all. Although hybrid RL with the uniform behavior policy achieves the best coverage throughout as expected. hybrid RL with even adversarially collected offline data achieves better coverage than online-onll exploration. This demonstrates the potential hybrid RL as a tool for taking advantage of poor quality offline data.
Figure shows the benefits of hybrid RL in the online-to-offiln setting when the behavior policy is of poor quality. When applying LinDEVI-ADV to the hybrid dataset of 200 trajectories and 100 on- line trajectories, 300 trajectories of adversarially collected offline data, and 300 trajectories of online data under reward-agnostic exploration, we see that the hybrid dataset is most conducive for learn- ing. Additionally, without a warm-start from offline data, online-only reward-agnostic exploration performs worse than the adversarially collected offline data due significant burn-in costs. Hybrid RL, in this instance, performs better than both offline-only and online-only learning alone. Figure 3 compares the performances of LSVI-UCB++ and Algorithm 2. Initializing regret- minimizzin online algorithm (LSVI-UCB++, (He et al., 2023)) with an offline dataset as in Algorithm 2 yields lower regret than LSVI-UCB++ without an offline dataset. This shows that even nearly minimax- optimal online learning algorithm can stand to benefit from offline data.
Coverage Over Feature Space, Reward- Agnostic Exploration Offine Partiie
Entiic Space
101s
10th_
Orline Pn
1ou.
1015
10
10a
1012
10a
Hybrl RUsiforet Hyorl Undvessonall all
10a
Hyordd 10 snfomm
109
Hyarld Undversor all
10a
Oniie-O-iy O-ly
Ontine Only
105
10a.
102
101-
syorts (U-)om)
100
Hyorls (Adversar al
Ontine Only
25
50
75
100
Onlino
Figure 1:
Coverage achieved by OPTCOV with 200 trajectories of offline data collected under a uniform and adversarial behavior policy, and with no offline data. Results averaged over 30 trials, with the shaded area depicting 1.96-standard errors. Lower is better.
'For ease of implementation, we implement LSVI-UCB+ (He et al., 2023) for Algorithm 2 as-is, while substituting LSVI-UCB (Jin et al., 2019) for FORCE (Wagenmaker et al., 2022) within OPTCOV and LinPEVI- ADV for LiDV (Xiong al., 2023). The code can be found at github. githbb.comhheaakkkiinyybbddii.

---

Hybrid Expleration
Offline Only Learnin
Online-Only Exploration
-0
-60
-55
-50
-45
-40
-35
-30
-2
Value
Figure 2: Value of policies learned by applying LinPEVI-ADV the hybrid, offline, and online datasets, with an adversarial behavior policy. The reward is negative as it is the negative of the excess height. Results over 30 trials. Higher is better.
Cumulativve Regret Over Timesteps
Hord
Online Eplacdes
Average Episode Reward Online Timesteps
Aaerag Sarvend
100
Ostin Eprcdes
Figure 3: Comparison of LSVI-UCB++ and Algorithm 2 over 10 trials, with 1 s.d. error bars.
5 Discussion, limitations and future work
In this paper, we develop two hybrid RL algorithms for linear MDPs with desirable statistical guar- antees for the online-to-offine and offline-to-online settings. Both algorithms demonstrate provable gains over the Mimimax-optimma rates in offline or online-only reinforcement learning, and provide the sharpest worst-case bounds for the performance of hybrid RL in linear MDPs thus far.
Throughout this paper, we have used both optimism and pessimism in our algorithm design. Other work in hybrid RI. (Amortila et al., 2024; Li et al., 2023b; Nakamoto et al., 2023; Song et al., 2023; Tan and Xu, 2024; Wagenmaker and Pacchiano, 2023) uses optimism, pessimism, or sometimes even neither. We conjecture that optimism is still helpful in aiding online exploration within hybrid RL and that pessimism helps in hybrid RL when learning from a combined dataset. However, determining if or when optimism or pessimism beneficial in hybrid RL remains an open question.
Achieving 3 horizon dependence in offline RL for linear MDPs has proven challenging. Even under strong coverage assumptions, Yin al. (2022) and Xiong al. (2023) only manage to achieve a 3 horizon dependence for tabular MDPs. Obtaining a / H3/N bound an open problem.
A result depending on a partial single-policy concentrability coefficient would be desirable, but may take the infimum over partitions. A good offline partition for the
provide only limited benefits partial all-policy concentrability contains the portion of the state-action space well-covered by the offline dataset, while the same for the partial single-policy concentrability would be well-covered by both the offline dataset and the optimal policy. The smaller size of the latter offline partition may be offset by the larger size of the latter's online partition, and as such any gains may be limited.
Furthermore, while Algorithm 1 improves upon the offlinc-only error lower bound in Xiong et al. (2023) and Algorithm 2 improves upon the online-only regret lower bound in Zhou et al. (2021), we still desire a single algorithm that improves upon both the best possible offline-only and online-only rates at once. Additionally, the burn-in costs for Algorithms I and 2 are nontrivial. The former is inherited from OPTCOV (Wagenmaker and Jamieson, 2023), while the latter is inherited from He et al. (2023) and the truncation argument. Improving the former by devising new reward-agnostic exploration algorithms for linear MDPs, perhaps in the vein of Li et al. (2023a), would be welcome.
While we tackle the setting of linear MDPs, it remains a first step towards showing that hybrid RI. breaks mipimal-optimal barriers the presence of function approximation. Further work in this vein other types of function approximation would be interesting contribution to the literature.
10

---

Acknowledgements
Y. Wei is supported in part by the NSF grant CCF-2106778, CCF-2418156 and the CAREER award DMS-2143215.
References
Abbasi-yadkori, Y., Pál, D., and Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. In Shawe-Taylor, J., Zemel, R., Bartlett, Pereira, F., and Weinberger, K., editors, Advances in Neural Information Processing Systems, volume 24. Curran Associates, Inc.
Agarwal, A., Jin, Y., and Zhang. T. (2022). Vogl: Towards optimal regret in model-free rl with nonlinear function approximation.
Amortila, P., Foster, D. J., Jiang, N., Sekhari, A., and Xie, T. (2024). Harnessing density ratios for online reinforcement learning.
Azar, M. G., Osband, I., and Munos, R. (2017). Minimax regret bounds for reinforcement learning. In International conference on machine learning, pages 263-272. PMLR.
Ball, P. J., Smith, L.. Kostrikov, I., and Levine, S. (2023). Efficient online reinforcement learning with offline data. In International Conference on Machine Learning, pages 1577-1594. PMLR.
Du, S., Kakade, M., Wang, R., and Yang, F. (2019). Is a good representation sufficient for sample efficient reinforcement learning? arXiv preprint (rXiv:/910.033)
Duan, Y. and Wang, M. (2020). Minimax-optimal off-policy evaluation with linear function approx- imation.
Fan, J., Wang, Z., Xie, Y., and Yang, Z. (2020). theoretical analysis of deep q-learning.
He, J., Zhao, H., Zhou, D., and Gu, Q. (2023). Nearly minimax optimal reinforcement learning for linear markov decision processes.
Hu, P., Chen, Y., and Huang. L. (2023). Nearly minimax optimal reinforcement learning with linear function approximation.
Jin, C., Allen-Zhu, Z., Bubeck, S., and Jordan, M. I. (2018). Is q-learning provably efficient? Advances in neural information processing systems, 31.
Jin, C., Liu, Q., and Miryoosefi, S. (2021a). Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms.
Jin, C., Yang, Z., Wang, Z., and Jordan, M. I. (2019). Provably efficient reinforcement learning with linear function approximation.
Jin, Y., Yang, Z., and Wang, Z. (2021b). Is pessimism provably efficient for offline rl? In Interna- tional Conference on Machine Learning, pages 5084-5096. PMLR.
Kausik, C., Tan, K., and Tewari, A. (2024). Leveraging offline data in linear latent bandits. arXiv
preprint 2rXiv:2405.1733
Lange, S., Gabel, T., and Riedmiller, M. (2012). Batch reinforcement learning. In Reinforcement learning: State-of-the-ary pages 45-73. Springer.
Lattimore, T., Szepesvari, C., and Weisz, G. (2020). Learning with good feature representations in bandits and in with generative model.
Levine, S.. Kumar, A.. Tucker, G., and Fu, (2020). Offline reinforcement learning: Tutorial, review, and perspectives on open problems.
Li, G., Chen, Y., Chi, Y., Gu, Y., and Wei, Y. (2021). Sample-efficient reinforcement learning is feasible for linearly realizable mdps with limited revisiting. Advances Neural Information Processing Systems, 34:16671-16685.

---

Li, G., Shi, L., Chen, Y., Chi, Y., and Wei, Y. (2024). Settling the sample complexity of model-based offline reinforcement learning. The Annals of Statistics, (660)223-260.
Li, G., Yan, Y. Chen, Y., and Fan, J. (2023a). Minimax-optimal reward-agnostic exploration in reinforcement learning.
Li, G., Zhan, W., Lee, J. D.. Chi, Y., and Chen, Y. (2023b). Reward-agnostic fine-tuning: Provable statistical benefits of hybrid reinforcement learning. arXiv preprint arXiv:2305. 10282.
Min, Y., Wang, T., Zhou, D., and Gu, Q (2021). Variance-aware off-policy evaluation with linear function approximation. Advances in neural information processing systems, 34:7598-7610.
Munos, R. and Szepesvári, C. (2008). Finite-time bounds for fitted value iteration. Journal of Machine Learning Research, 9(77):15-855)
Nahum-Shann I., Smith, S. N., Spring, B. Collins, L. M., Witkiewitz, K. A., Tewari, A., and Mur- phy. S. A. (2017). Just-in-time adaptive interventions (jitais) in mobile health: Key components and design principles for ongoing health behavior support. Annals of Behavioral Medicine: A Publication of the Society of Behavioral Medicine, 52:446-461
Nair, A., Gupta, A., Dalal, M., and Levine, S. (2020). Awac: Accelerating online reinforcement learning with offline datasets. arXiv preprint 2006.2000009355
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.
Qiao, D. and Wang, Y.-. (2022). Near-optimal deployment efficiency in reward-free reinforcement learning with linear function approximation. arXiv preprint arXiv:2210.00701.
Song, Y., Zhou, Y., Sekhari, A., Bagnell, J. A., Krishnamurthy, A., and Sun, W. (2023). Hybrid rl: Using both offline and online data can make rl efficient.
Sutton, R. S. and Barto, A. G. (2018). Reinforcement Learning: An Introduction. The MIT Press, second edition.
Tan, K. and Xu, Z. (2024), A natural extension to online algorithms for hybrid RL with limited coverage. Reinforcement Learning Journal, 1.
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 arXiv: 087
Wagenmaker, A., Chen, Y., Simehowitz, M., Du, S. S., and Jamieson, K. (2022). First-order regret in reinforcement learning with linear function approximation: A robust estimation approach.
Wagenmaker, A. and Jamieson, K. (2023). Instance dependen near-optimal policy identification in linear mdps via online experiment design.
Wagenmaker, A. and Pacchiano, A. (2023). Leveraging offline data in online reinforcement learning-
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., and Agarwal, A. (2023). Bellman-ccnsistent pestianm for offline reinforcement learning.
Xie, T., Foster, D. J., Bai, Y., Jiang, N., and Kakade, S. M. (2022a). The role of coverage in online reinforcement learning. arXiv preprint trXiv:2210.0415::
Xie, T., Jiang, N., Wang, H., Xiong, C., and Bai, Y. (2022b). Policy finetuning: Bridging sample- efficient offline and online reinforcement learning.
Xiong. W. Zhong, H., Shi, C., Shen, C., Wang, L., and Zhang, T. (2023). Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game.
Yang, F. and Wang, M. (2019). Sample-optimal parametric q-learning using linearly additive features.
12

---

Yin, M., Duan, Y., Wang, M., and Wang, Y.-.. (2022). Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism.
Zanette, A., Wainwright, M. J., and Brunskill, (2021). Provable benefits of actor-critic methods for offline reinforcement learning.
Zhan, W., Huang, B., Huang, A., Jiang, N., and Lee, D. (2022). Offline reinforcement learning with realizability and single-policy concentrability.
Zhang, Z., Chen, Y. Lee, J. D., and Du, S. S. (2023). Settling the sample complexity of online reinforcement learning. arXiv preprint arXiv:2307.1:586
Zhou, D. and Gu, Q. (2022). Computationally efficient horizon-free reinforcement learning for linear mixture mdps.
Zhou, D., Gu, Q. and Szepesvari, C. (2021). Nearly minimax optimal reinforcement learning for linear mixture markov decision processes.
Zhou, Y., Sekhari, A., Song, Y., and Sun, W. (2023). Offline data enhanced on-policy policy gradient with provable guarantees.
13

---

A Unabridged versions of our algorithms
Algorithm 3 Reward-Agnostic Exploration-initiaiizee Pessimistic PAC Learning (RAPPEL,, Full) 1: Input: Offline dataset Dot.. samples sizes Non. Nof, feature maps Oh, tolerance parameter for award-agnostic exploration т.
2: Initialize: / Ø vh [M]. A = 1/112 B2 Ö(Vū). Set functions to optimize f((A) = 7): log (Zico exp(m (Il (A))) AA. = A (T;K,) + Aott) for some
oo, satisfying Ao.i 2 Ao for all i, and = 22//5
Exploration Phase: Run an exploration algorithm (OPTCOV, Wagenmaker and Jamieson (2023)) to collect covariates A such that max 0 (An + AI AofI.) Φh & T.
for
i 1, 3, 3.. do
4: Set the number of iterates T; + 2', episodes per iterate K; - 2'.
5: Play any policy for K; episodes to collect covariates To and data Do.
6:
Initialize covariance matrix A < To/ K.
7:
for t 1, 1.... T; do
8:
E KjKr > Non then
9:
break end if
10:
Run FORCE (Wagenmaker et al., 2022) or another regret-minimizing algorithm on the
exploration-fooe fociused synthetic reward 9h. (s,
Collect covariates r,, data Dr,
13:
Perform Frank-Wolfe update: T++1 (1 *+1 A + E- D.KK,
14:
end for Assign Ait t- AT:+1, D; of Dr
16:
Set A = Ai,h Don = D..
if (A, K then
18:
break end if end for
20:
Planning Phase: Estimate using a pessimistic offline RL algorithm (LinPEVI-ADV+, Xiong et al. (2023)) with hyperparameters A, 92 on the combined dataset Don u (D( (an)
be[H]]
Split the dataset Dor U (on)) he[[H] into D and D'. Estimate, on D',
(No))
21:
Br.2 = argmin Σ
(ol (8) , (Di+1)² (5h+1) ] + 2lllkk
SERd
reD
Br.1 argmin
Σ
( (sh ap) Pia 1 (sh+1) *1131/1.
DeRd
reD
(8, a) = max 1, 11,[0(5,0) a) (Tn.saa)BBn2ll.... - (((s,a)TB,,11 33.11P0.H11 - dH3 VNn
for h 1,..., do
23:
Compute covariance matrix En, E d (87 ah)
168 (8h, ah) + Ala-
24:
Compute weights C. Σn ETED 2 (8%,
Compute pessimistic penalty ('n(-.)) 32l(o(..)) 122""
Compute pessimistic Q-function Qx(:.)) - (d(:,.) "wh -
26:
27:
Set (- I) arg maxxi, (Qn(:.),,)) ( .,)2 Vi(.) (Qn(:-), (1)()))))
end for
29:
Output: a.
14

---

Algorithm 4 Hybrid Regression for Upper-Confidence Reinforcement Learning (HYRULE, Full)
1: Input: Offline dataset Dust, samples sizes Non: Nott feature maps @h- Regularization parame- ter À > 0, confidence radii B, B, B, just = 0.
2: Initialize: For h [H]] estimate Wi, W1,h Q1, L1, 11,; 11 from Dott with the same
formulas outlined below, and assign Eo,h Σ1, = Eoll + AI = EN= σ n.h 0n, n. + AI.
3: for episodes = 1.... T do
4: Receive the initial state 81
5: for horizon / 1,... H do
(6) (0 6: Wa,A = Σ, t.h - 1.4 2 an Wenta(
7: Wr.h- = 1. 2i-1 L. (
hh an
( 1 h+1)
(9)
8:
if there exists stage h [H] such that det (E(,v) 2/ 2 det (E .e) then (ss, a)
9:
Q1,4(1, min (r( a)
/
(5 (T
(s. (1
H).
(s) max (r(ss ( a) ),
11:
Set the last updating episode linst L.
12:
else
13:
end Qs,((s,)) Qu-Ln(s,a), (s, @1,1))),a)
14:
Vi,((s) max, (s, (s) max, (s, end for
15:
16:
17:
for horizon h 1, ...,
H do
Play action dj (6)
arg max, Qr, (0) (.)))
18:
19:
Estimate oCh
Ven Vennta
8/1 [1
(8)
+ Ei, + De, + H, setting Es,, and De
E.A = min 3
Σ
1/2
( (t)
.H2 + min 2HH M (s5h 2 .H2
1/2
(8)
DL. min
4d
W
w w., ((5)
(1) (0)
+ 2
(1) (0) Σ
(1)
(1)
1 H3
1/2
20:
0thh max
Tz,h, H. 2d 12
8/
(1)
(1)
21:
E111h = Σi, + J.
(t)
(t)
Φ
a
(0)
Receive reward (0) next state 8h+1'
22:
23:
end for
24:
end for
25:
Output: Greedy policy â = 7rrA Unit(T 9r, .... π. Prin) for PAC guarantee.
*He et al. (2023) write 7t + max(ar,n, H,...) instead VH. We believe that this a typo in their paper,
given that in the proof of Lemma B.1, they state right after equation D.7 that 0 & न, 1/ H. Moreover, in the proof of Lemma B.5 the array of equations right after equation D.22, particularly | 0 (sh. ob)], & j (s), di)) )), (HH, only holds true if this is VH.
15

---

B Proofs for Theorem 1
The proof of Theorem 1 follows from a series of distinct results, presented three lemmas below. The first lemma demonstrates that RAPPEL achieves no higher error than LinPEVI-ADV+ itself, the second produces d error bound, while the third produces d dg error bound via slightly different truncation argument. We will prove Equation 7 in Lemma 2, which act as general statistical guarantee for RAPPEL. We show the validity of the instance-dependent bound developed from Equation 7 in Lemmas and 4. We observe that Theorem follows immediately after.
Lemma (General Statistical Guarantee for RAPPEL, Algorithm 1). For every E (0, 1) and any partition Xoff, Non, with probability at least 8, RAPPEL achieves
H v Vd
Σ E |o((k) an)l -E on,
& Vd Σ h=1
B (10(11) and an)ll
Proof. Before we proof the desired result, first recall that
An =
Σ o (sh, a o (5) + la.
(10)
D
Σ
o (8% a (5% an) [VaVital (s), + Als.
(11)
TED
Then, by invoking Theorem from Xiong et al. (2023) with N > ((d 1/112, O(Vd), we see that
- S vd Ex* [|d(s)
[W]lxx anllx |s|
v Ex [ ( a + bm..)) 11 81 =
as Σn D
offf + 1* A + E hn on Therefore,
Noting that E is positive semi-definite, it then follows Σ h 3
H vd > Σ E. (oo(sn anll (Eta. +
vd
E |lo(sn owlls
h=1
and the inequality holds.
Lemma 3 (First Error Bound for RAPPEL, Algorithm 1). For every (0, 1) and any partition Xott. Xon with probability at least 8, RAPPEL achieves
Coll (d+ Nott
d
- V
where
Non
N > max fo d-1 4 Coff (oott) -13 . -pol((d, H, cont Con (oo)). log 1/5),, where we define
Nott the quantilies Clff N aon Non. and the minimal samples for coverage -N,
N min C-N s.1. inf max TT (N(A + X1) + AOt) -1 Φ & (mmxx(oon/ Non, Coff Coft (KoH) Nott)). N
AEf de#
Proof. Let Noit, Xon be an arbitrary partition of S A x [H] Let leave the choice of OPTCOV tolerance unspecified for the moment, and simply assume for now that we have data D collected under the success event of Lemma 16.
We now invoke Theorem from Xiong et al. (2023) on this dataset. As we choose > H6), A 1/112 and 31 O(vd), we obtain the suboptimality gap decomposition below:
H
(s) v S Vd
Σ
Es# [1((sh
an)l2g-1 81 = =8]
16

---

This decomposition can be further decomposed into the sum of bonuses on the offline and online partitions Roft and Xon respectively:
[0(sh, an)) 1 1181 =
--1
H
vd
Σ
(1o((s) 1x $1 + +,7
|ō(sk an)lxx 1x $1 = ss)
h=1
H1
vd
Σ
E
TE
(ost lxmn 181
H
+ vd
TE E
(n) (8h, an) Xox
We can further upper bound the above expectations under the optimal policy n* by taking the max- imum of the quadratic form over each partition, yielding
E B
[lo(sp; on) an)lxx 8s
H
d
max dhs Paa V 0/ Ix on 1 x.. + Vd
max one
@n 128--op
"nn
1x.r
H
$ v
da El V 1/ tb + vd
max
TTS+-1
max
V
1/ 1 oh.
From Xiong et al. (2023), as [V (s.)) H.) the weighted covariance matrix is uniformly upper bounded by the unweighted covariance matrix in the following manner:
Σ m = HAA
which leads to our conclusion that
" 12 A Øn + va
- - S Vd
Σ
Σ
H A on.
max PAE
max 0.
We now further bound the above two quadratic forms over the online and offline partitions respec- tively. By Lemma I, the partial online coverage coefficient bounded by the dimensionality of online partition:
Con (Xon) = inf max 0% E, ( dx aaa
-o & don-
As we have Non online episodes, the optimal covariates for online exploration would then yield inf max TT A -1 'on Con (Non)/ don/ Non.
A erE
Conversely, we also have access to Noff episodes of offline data with the following guarantee that follows from application of Matrix Chernoff:
o,, A.Atton & con (Non)/Noa.
max 01
Therefore, by Lemma 5, we can conclude that on its success event, running OPTCOV with tolerance O(max(don/ Non, Codl (Xoa), / Non))) }), provides us covariates such that
max oT A th I max (con (Nor)/ Nott, don/ Non). $..0
yielding the desired result.
17

---

It now remains to work out the burn-in cost from running OPTCOV. The following quantity of the minimal online samples any algorithm requires to establish coverage was first proposed in Wagen- maker and Pacchiano (2023):
O(max/don/ Nonnnn Coll (o (Not))))(/)))))) (onl)
N min C-N s.t. inf max oJ (N(A XI) + Aot) - Arf de
We can use this as follows. Invoking Lemma 16, we see that OPTCOV incurs
( Noft
4/5
Non
4/5
max
max N poly(d, H, corl con (Kon), 1/8))
Coff (Xott)
don
episodes of online exploration, for an overall burm-in cost of
ann at
Noff + Non e max
max
poly(d, H, Coll coft (Xont) log 1/6)}
dg
Coff (RoH)
episodes, where Offf
Naft Nou
and aon
Non
Nott
Nox+
Note that the more even the proportion of offline to online samples, the smaller Coff Gon are. In fact, as a a [0.0625, 1]. this term contributes no more than a constant factor that no greater than to the final sample complexity.
We then have that
Cont (donn )d Noff
don don
-
inf Xost von
N
with probability least 1-6, when N max
Cudf (ott(
max poll(d, HI cot (Kor), log 1/6)).
Lemma 4 (Second Error Bound for RAPPEL, Algorithm 1). For every & E (0, 1) and any partition Nott Xon with probability least 8. RAPPEL achieves
Cott (Xon))
de dH'
-
where
NoHOratt
Non
N > max (oo dos Coff( (Not) (Not)=a) max (N* (oon(,y H, cott (No)), ). log 1/0)}, we define the quantities Ofoff Nutt N Qon New N.
and the minimal samples for coverage is
N min C-N s.t. inf max o (N(A AI) + Aoa) O(max|dom/ con con (Noa)/
Proof. First, we set up some preliminaries. Following the same argument as the proof of Lemma 3, can establish that, for arbitrary partition X' Xon U Not,, we have
Con (onn) & don:
and running OPTCOV with tolerance Ö(max (oon/ Non. Coll (on)/Noa)) yields:
max T A dn S max (XoH)/)) Nott, don/ No.) d
This incurs
(Noot Noft Coff (Xoa)
4/6
Non
4/5
max
max N* poly(d, d, H, can (Xoot) 1/8))
don
episodes of online exploration, for an overall burn-in cost of
an di
a
Nof + Non e max
max{N** poly(d, H, cott cott (Kott), log 1/0))
Coff
(
18

---

episodes.
To tighten the horizon dependence even further from the result of Lemma turn the total variance lemma. i.e. Lemma C.5 in Jin et al. (2018), indicating that
1 NH
EEΣ [VVV aR) (
(H+
H
TED
Then, we directly apply Lemma 17 with max (don/ Nou: Coff (ooft) // //H and H + H²/N, we will then obtain that
don
Coft (coot))
H N
max Σ ONEO
V
oh
h
on
Non
+
Notf
11 N
don
Coff (coot)
+
NNH + 11a
Non
Notf
Coff Coff (2
Coff (2oR))
d2 H3
de H4 N2
(12)
Nottoofff
Noi
Non
Coff (2
d2 HB Non
$
(13)
Noftooff
which leads to our final result:
(v
(Ccom (on
den dH3
(+) -
$ inf Noft Natt
Noff
Non
where Ctff Noft/N and Coon Non/ /.
C Proof of Corollary 1
Proof. In tabular case, we set (b a) ssa and = [A]. Let (s,s,, a) the number of visits to specific state-action pair (8, h). As the exploration algorithm OPTCOV ensures that
don Non Nott
(on(
max s,a
N& a) & max
we bound the error in the following way follows from Lemma 2,
(i*(s) - (s)
d
Σ
E E+ [lo(sk an)l(
h=1
V V+ (s.
&
V
ΣΣ
ds,
(x
1-1 8,0
where the last inequality follows from the fact that 2/ diag (Nng(NN(s,, a)/ [VA Vittal (s,a)) "ES
We will then decompose the sate-action, space into You and Xon. and bound the two parts seperately based on the tolerance level of ОPTCOV,
H
[V V2 ]
(8,a)
(T( - vF(s) S
V SIA
1xx0
(s)
H Σ
VAV* h+ (s. a)
S
Σ ds a)
1x
a)
h=
S SS (KoH))
H
Σ
Σ
Nott
19

---

S) SllLAlonn
11
(x, V
V h+1
(8,
Non
8.a
(V
(oot (Kott) Noil
< VISIIA
don Non
Σ
Σ
a VV Wi (s,
V
As the optimal policy x² executes deterministic action n" (7(ss for any state the inequality can be further bounded as
(v
Coff (Xott) Nott
don Non
H
(*((s) (f((s) VISIAA
d (s, n (s)) [Va (s)
(v
Coft (ool))
dou Non
H|
Σ Σ d (8, Tr" (8)) [V (8, (s))
Noft
h-1
Cotf (Koft)
don Non
$ H|S
Σ B(oaa)dd.- [VaV (s,
Noft
(V
Coff (Noft)
don Non
< H
(14)
Noff
where the last inequality follows from the proof of Lemma C.5. in Jin et al. (2018).
D On concentrability and coverability
For any partition Xott, Non we have that Con Con (Non) don- Similarly, there exists partition such that cat (Koft) = (d).
Lemma 1.
Proof. This proof follows similar strategy to that of Lemma B.10 in Wagenmaker and Jamieson (2023), except that we exploit the projections onto don to get a bound that depends on don < d, instead of d. We wish bound
Con (oon) inf max
Ad... (Eaz [(Pon th ((Pnn "J)
Pon Radd has rank don d, can decompose this with the thin SVD into Pon UT on where Uon e Rdxdon, It then holds that
Aaan (Bag [(P (h (Ponth))) JJ Amin Amin (UUn) I)),
and from Lemma 20 that
Con (Xon) = inf sup e0
1n Uon Eay (N (1 th-
Apply Jensen's inequality to find that for any th Pon.
2y Unn [[U (U on) TT vn 2 2if Uon -d IU On vay [nTTON U
Then, we can bound
Con (Xan)) inf sup v.
ToJ Unn Far (1) - 2/
< inf sup 2n Uon (Er~op Ee -a [UT on Exg dz [U on II] UT Uh.
By Kiefer- Wolfowitz (Lattimore et al., 2020), this is bounded by don-
20

---

Similarly,
inf
Coff (oot)
inf max
Xom Kon
Kon h Adan (E (Po (P P
inf max Non Amin(Epu [[U (U
(dd).
where the upper bound achieved when, for instance, we choose Xott such that Poff Span ((vh,1...,, th (e(m)) where oh is the i-th largest eigenvector of E & Notr Dee (n( (f) aT)", and Uh,6, is the cigenvector corresponding the largest eigenvalue An, ((1/kp). The largest eigenvalue A is always ((1/d) for non-null features, so there always exists such partition where doff is at least 1.
Informally, one can choose the offline partition be the span of the large eigenvectors of the covari- ance matrix, so the smallest eigenvalue of the projected covariance matrix, i.e. the partial all policy concentrability coefficient, is no larger than the dimension of the partition.
Lemma 5 (Maximum Eigenvalue Bound with OPTCOV). On any partition Nott Nans we run OPTCOV with tolerance Ommx don/Nons Con (Not) Now) 1), this partition also have that
max 0 Ar db $ max (cost (KaHt Nost, don/ Non
Proof. By Lemma 1, for any partition, we have that
Con (oon) inf max 0..0
0 -o
1o & dons
Applying Matrix Chernoff, we have that with probability at least 1 1- 5,
-1
( 4d
max 0% h On QeE
max 0 B -,, 1 + N= -on 1 1 V
log
Noir
and similarly for Con (Nou) also have that
2
4d
inf max @ A on & inf max π one
Ez [or 1'n
(1-V
log
)
T onefon
Non
8
As A An.nn
Ans have
max 6.
0 A on = max
max Pre
T A Sn, max @n A on
$ max
Coff (Kott)
/offf
max
0) A on
where the last step follows from the choice of partition. So suffices to run OPTCOV with tolerance Ö (max((onn/ Non, Coff (Xott). Nott))
to find that there exists at least one partition such that
max 01 A On I max (oott/)ot)// Nott don/ Non )
OLED
Lemma (Coverability Coefficient Bounded In Tabular MDPs). If underlying MDP is tabular, for any partition Xoit Xon, we have that con (Xoa) & don-
21

---

Proof. First, we write the concentrability coefficient in terms of densities.
Con (ooo)) = min max h Adaa (Eag [(P on ) (Ponoa)
1x
min max b ming a),
1 1x
min max h,a (7 xx..
By the same trick that Xie et al. (2022a) use in their Lemma 3,
X
1 1 sup (8, (8, Xam/ Ev sup dh (8',a) 1 Nmn Ega sup, dh (s,0) Lxon
di (s, Xon
sup, di (s, 0) Lxon
< don.
E
Proofs for Algorithm
E.1
Setup
We consider the same state-action space splitting framework of Tan and Xu (2024), Let Xon Xott [H] x S x A. Then, their images under the feature map Poft Span( (ooH,))))emM S R2 and Don = Span( of ())ee)) = I2 are subspaces of X with dimension dof and dons respectively. We denote Poat Pon as the orthogonal projection operators onto these subspaces respectively, The partial offline all-policy concentrability coefficient
Coll (Xon) = max
h
Adaas (B,,, [P
bounded by the inverse of the do largest eigenvalue of the covariance matrix the projected feature maps onto the offline partition, where A is the k-th largest eigenvalue. Write 1 1x,, as shorthand for ((ss, a, h)) E X.n), and similarly for Xxu-
Now, we work through the analysis of He et al. (2023) to ensure that their result holds in our setting, where the regret decomposes into online part | 1/2 (s 1 llz and offline part | (n(*)) 1x-1/2<nn((
(t) .0) 1x ll2 respectively, instead of E> on (8) ,4h )||2-
1/2
(4)
t,h
E.2 High-probability events
We define several "high probability" events which are similar to those defined in He et al. (2023).
We define We, as the solution of the weighted ridge regression problem for the squared value function
Wr. E Σ 2 o
(15)
We define E as the event where the following inequalities hold for all s, s,a,t, Ax [T] [d]]
[P i & & (ss T
(16)
WT w.
[ (8, & B TT
(8,
(17)
22

---

W Wr, a) - [TP Ph (s, & BVoo(s, T
(18)
3 3-0
Log
- = o H Hvdx + V H2 (dH (OHNN((6A)
This is the "coarse event" as mentioned in their paper, where concentration holds for the value and squared value function with all three estimators.
We define εn as the event that for all episodes e [T]. stages h & ht' & H and state-action
pairs (s, a) E S x A, the weight vector We, satisfies
W r, O a) - PPA
BB (
(19)
where
== o H HVdX y + dNHH((O))
Furthermore, let E & denotes the event that (19) holds for all stages h E [H]. This is the fine event where concentration for w is tighter than that required in (16) (18).
Equipped with these definitions, we recall the following lemmas from He et al. (2023):
Lemma (Lemma B. He et al. (2023)). holds with probability at least 76.
Lemma 8 (Lemma B.2, He et al. (2023)). On the event & and + for each episode t E [T]] and stage h, the estimated variance satisfies
Vv V.
hh 0n
(1) (8)
(VAVe
5h :0h"
(1)
< Ee,,.
V
5h 0
(1) (4)
[VAV
Sh a
(6) (0)
$ Ea,
De,--
Lemma (Lemma B.3, He et al. (2023)). On the event & and Entr, 1. for any episode t and >> t, have
VV (Va441 Vi++1]] (6h (t) < Drna/ (d)
Lemma 10 (Lemma B.4, He al. (2023)). On the event & and Enr for all episodes t [T] and stuges 1/ & H, we have Qr,(s,a) (7) Qua(+, a). addition, we have Vr,(() > (s) > (s).
Lemma (Lemma B.5, He al. (2023)). On event &, event E holds with probubility at least 5.
E.3 Regret decomposition
(8) From He et al. (2023), based on Lemma B.4 of their paper, (s, (1))) ie. optimism holds for all episodes and timesteps. Therefore,
T
H
Reg(T)
Σ
Ph
(Ve,h+1
(Venta (s/t2) Veh4i (c(1)
(//t1))
T
H
on (1)
(5 . 12
+
Accordingly, given partition Xoit, Xon of [H] S x A. we can further decompose this into the fraction of episodes where each partition is visited,
1/2 (n E
112
Ei 1/2 on
(n a (1) Xoa 2
12 Σ
1/2 or
(s a (4)
Lx 12
b.t
h.t
He et al. (2023) define the events
23

---

T
H
=
4h e H Σ
Ph
Ve.h+1
Virh (1% .0."))
(2)
[=1
-/=h
H
Vin+1 (Sh+1)
Vaal)) (t)
(htt)) & 2v 22/2HHT H1)8)
(=1 h
T
H
&
wh E [H]
Σ
Σ
Ph
(Ven+1- - -ea+t)
(1) (1)
[=1
-/=h
H (VLAt (sht1) Ve,t+1
(htt)) & 2/ 2H3T log( H/)))
1h-h
which they show that by Hoeff-ng,,,, both hold with probability 1- each. As such, we have that
Reg( & v Hog
Σ 8 Σ
1/2 on
(s
0h 1 2
1/2
a (2) Lx
h,
Here, we denote Regon
(T)
1/2 Σ 1 on
(1)
(2)
x l
Reg (T)
0n(5% B|
1/2
(1) )x
h.t
as the offline regret and online regret, respectively.
E.4 Offfine regret control
Now, we bound the regret on the offline partition. We first perform similar argument to that in Tan and Xu (2024); Xie al. (2022a) show that the sum of bonuses be controlled by the maximum eigenvalue of the inverse weighted average covariance matrix in Lemma 12. We will then show that the maximum eigenvalue can be nicely bounded in Lemma 13.
Lemma 12 (Sum of Bonuses on Offline Partition). For any partition Nott Xon. we can bound the sum of bonuses on the offline purtition with the following:
H
dN2
Regon (T) $
Σ
max 0) oweloot
TE-1 S th:
Not
where Dosth (Eog.h Mo/Not and T Non-
Proof. is sufficient show the following holds true
dN2 on Noff
E 1/2 dn (5
(1) l V
max 0% T-- Loll Pho
ds Edhn
then the desired inequality directly follows. With a direct calculation, one may observe that
1/2 (0) L. (5(s) 0h
1
(1) (T (1) (1) 1 "D)E,honss .
aa 1x
1 1T (5
(1) ) AII (b (0 a ( L
X
where the last inequality holds Yodl Ee.. As result, inequality with the maximum eigenvalue of the inverse weighted matrix,
able to bound the desired
Σ
Σ
1/2 h pn(s
(0)
1 & Nong Oh
max (T + 1oon OnEton
Non
Non Not on e
max of To
24

---

where Mogl (Softh h + Aof/Noff As As = Ö(vd), we obtain the bound we desired:
Non max 0f o,
? $1(s) oh (1) 1xxrlll < V/
VdNou Notl one
Lemma 13 (Partial Concentrability Bound). For any partition Nott, Ron, we have that
Cottl V0% T on I /ooi (Xon)
max eoorr
when Non, Noft 3/ (2 H where we define Dofthh (Fofth \l/ Nott.
Proof. Similar the definition of Yodth. we define Aotl, (A /No in a similar way.
Then, one may observe that
m
max On offff
(0) A off 1
max Efffff
Φh
Σ
In Inch AT
Noft
-1
2 Noff
4d
max 1..4
0) Epn [AotT
1- on
1-1
1
log
8
where the last line holds by an application of the Matrix Chernoff inequality. Then, we may further bound the quantity with the partial offline all-policy concentrability coefficient,
max (0) ( ott
x
inf max Adoo (Po((oo))))PooOO)))
oneMoff
Xait Xon
inf max Non h
Amin
coa
To tighten the dependence of the regret of the offline partition H. again employ truncation argument that used in Lemma 4. Recall that in Section of the appendix in He et al. (2023), by the total variance lemma Jin al. (2019), holds that
oi & O 20.5 16
Again, recall that we have
Σ h.t
Σ th on
1/2
(8h
) 1xall
an
(8)
Non
Noff
max H2 Not one
df
Nott
σ n.h
n.h
+ AI
As 02 max 02 H, 4 H 110 A1s }. Consider the sets
{n E [NoH]] Vh 02 o max(o? 11),
Ie If
Here, Iz roughly correspond to the "bad" set of trajectories where there exists some timestep h such that Rh > max(o? H). and In to be the "good" set of trajectories where the monotonic variance estimator is controlled.
25

---

We need to bound the cardinality of the latter before employing our truncation argument on the estimated variances. As we note that for all n I2 we have that mäXhe]H] / /6,, Dn, 2 1/(4d H)), which indicates that
min (1, 16d "0,,, 2n On 2 1.
and so we can conclude that
Σ min (1, 16d 11 2n, Pn. d 11 log(1 + N/d),
by Lemma D.5 of Zhou and Gu (2022) and the fact that //m.k//n,..l & 1/H2. As we require in Theorem that Non: Noff (2 H we come to the following result
on & 8d H log(1 + N/d//Not o(1), [Il//oo = 1 6(1).
Informally, this means that the proportion of trajectories in the "bad set" Iz is asymptotically zero, and the proportion in the "good set" I, is asymptotically one. As for every n In we have that for any h [H].
TT
max 69
Natt
max tn
@h
Σ
n.h n AI
211)
Φn
Noff
n=1
max onelofff
Not
Φn
Σ
n.h
Hn An,h + AI
Φh
1=
max
Non
ΦN
Σ
n.h
+ AI
Φn
H
DET
Now we invoke the total variance lemma. Recall that in Section B of the appendix in He et al. (2023), by the total variance lemma Jin al. (2019), Not t (0 H114), (110055444))
holds that
Noft
Ō (H² 2 1 /NoH) Ō (H²).
NO
With a direct application of Lemma 17, as we set T' = Ö(H) and 7 = Coff (Nott) / //off we will then get
Coft (Nott H
conf (Yon) H3 Noil
max due Patt
Σ- dn x
V VN
Nosl
which indicates that
-T Dott S V cotf (Kon
max ohef
Now, from Lemmas 12 and 13, for any partition Yon, Xon. the offline regret satisfies
Non
N
Reg (T)*s E
dNoa Non one
max of TT $ Vean(Kan)
(dd 2dH Non
Noi
26

---

E,5
Online regret control
We will then bound the online term, Regon (T). He al. (2023) show in Lemma E.1 that it is possible to use Cauchy-Schward to bound this by
Regon (T) = Ō 0 ( + Bd + / dHT dH
T
H
Σ
of
and in Section B of the appendix, state that by the total variance lemma of Jin al. (2019),
Σ
o < ( 100.5116) H16)
We will seek to the online partition tighten the dimensional dependence in the first result accordingly.
Lemma (Modified Lemma E.1 al. (2023)). For any parameters 3' è and C 3 1, and any partition Xott: Xon the summation of bonuses the online partition is upper bounded by
min (
(5/
.0h 1x C
(1)
T
& Hd 103' d H 23'
2don'
02 + H
where: log(1 N/(d))).
Proof. For each horizon h [M, first note that the summation can be bounded by the sum of two terms, where the first term is tight-bounded and the second term stands for a tail event where o E-E gets large.
3 vo
5% (o)
E (sh aq))))))) 1xam: C
T
8l min
10(5 (0.
a 1xmm Eg (
r
((() (0
(1)) T EnAe (5l (0) Ixo0 > =1}
+ C
(100
We first bound ΣT= 3r
min
Egie (10 (1)
xxm,
using a variant of
Lemma B.1 from Zhou and Gu (2022) in Lemma 18. With this, we have that
Vo
8 min
(0) a
Eg (5h) a(a") Xx
Nott+1
B' min
\
ob (1))
(2)
(dm, (onn (xwnd + Ala
& (.%0 ,a
(1)
Ix
n=1
10 05 H+, 2
2don' Σ
oh H).
where l (/d)))..
27

---

From this, it suffices to follow the rest of the proof of Lemma E. from He et al. (2023) to bound the remaining term by
Σ
0h (
(1 ( :0 )x.n 2 =1}
1 & 4d 11
As result, we obtain the following bound for the online regret
Regon (T) & d' H + BV dondHHT..
E.6
Putting everything together
Combining our results in E.4 and E.5, we come the bound of total regret that
Non
Reg((Non) v No (6)
(ort(Ho
Notf + 3 + d H1.
When we set Nou, Not 2(d (l1) and choose Nott Nou be the partition that minimize the right hand side, we have
Reg( Nou) S inf Non (Venn(Kon)ddHNN)
N
V 3 Non
Noil
proving Theorem 2.
F OPTCOV from Wagenmaker and Jamieson (2023)
We lean the OPTCOV algorithm from Wagenmaker and Pacchiano (2023) for reward-agnostic exploration, first proposed in Wagenmaker and Jamieson (2023), as well as the Frank Wolfe sub- routine used, for completeness.
Algorithm Collection Optimal Covariates (OPTCOV), Wagenmaker and Pacchiano (2023)
1: Input: functions to optimize (Jt).. constraint tolerance confidence 8.
2: for 1,2,3,
3: Set the number of iterates T, < 2 episodes per iterate K; <- 2
4: Play any policy for K; episodes to collect covariates To and data Do.
5: Initialize covariance matrix A₁ To/K.
6: for 1,.... do
7:
Run FORCE (Wagenmaker et al., 2022) another regret-minimizing algorithm the
exploration-foeee focused synthetic reward 5h (s, (ss,))ce (e)atr((VVVlll A
8: Collect covariates Ir, data D,.
9: Perform Frank-Wolfe update: T + (1 + )r + L./KK
10:
end for Assign A; AT,+1, Di
11:
if (A, K,T,c then
13:
Return: A, K,
14: end if
15:
end for
The algorithm essentially performs the doubling trick to determine how many samples to collect, terminating when the minimum eigenvalue of the covariance matrix above the tolerance.
Wagenmaker and Pacchiano (2023) then prove the following guarantee for OPTCOV in the hybrid setting:
28

---

Lemma 15 (Termination of OPTCOV, Lemma C.2 (Wagenmaker and Pacchiano, 2023)), Ler
f((A) log
Σ T BE
E
A.(A) = A oo, + T:K;
Afff
T,K,
for some An,i satisfying Ao,; = Ao for all i, and 1Js 22//5 Let (Bi, M,) denote the smoothness and magnitude constants for ft. Let (3, M) be some values such that & ni M4 & M for all Then, if we run OPTCOV on (fi); with constraint tolerance e and confidence ó, we have that with probability least 6, it will run for most
max
min 16N
inf max TJ (NA Ao Aoft) 2 6 Aet de
poly d, H, M, log 1/8) 4/5
episodes, and will return data ( with covariance EN E of such that
f (N [N-'EN) Ne
where is the iteration on which OPTCOV terminates.
We use this to obtain a modified guarantee for OPTCOV that does not require a call to the CONDI- TIONEDCOV algorithm of Wagenmaker and Jamieson (2023).
Lemma 16 (Modified Bound OPTCOV, Theorem 4, Wagenmaker and Pacchiano (2023)), Con- sider running OPTCOV with some txxp > 0 and functions Ja as defined Lemma 15, instantiated with the regularization À = O. Then with probability 5, this procedure will collect at most
eexp poly (d, H, Con (Nun), log 1/5)
min - s.l. inf max TJ (N(A+ XI) Aoft) Φ &
max
Aef deb
4/5
6exp
episodes, and will produce covariates E such that
max Φn ( XI Φ.Et
Aoti)
Φn & coxp-
Proof. This is essentially the proof of Theorem 4 in Wagenmaker and Pacchiano (2023), except where we chase around a few terms that differ in the analysis. By Lemma D.5 of Wagenmaker and Jamieson (2023), it suffices to bound the smoothness constants of fs(A) by
M, () 2 3
L =
X
B
=
1
X
Assume that the termination condition of OPTCOV is met for i satisfying
(L_ H, log 1/6, con (Kon), ))
i x log
poly
Eexp
We assume this holds and justify it the conclusion of the proof. For notational convenience, define
=
poly
loog
.d, H, log Co (Xon)
Cexp
Given this upper bound on 7, set
1
L M
B:=L
X2'
With this choice of L, M, B, have L; M, M, B < n.8 for all i
29

---

Now apply Lemma 15 with Ao = À and get that, with probability at least 1 - 6, OPTCOV terminates after most
max min 16N
s.t.
inf max of (NA+ Aoft) Aet DeD
Φ Cexp
poly (d, H. X, Con (Noa), log 1/Eexp: log 1/6)
4/5
Coxp
episodes, and returns data ( with covariance Σ ΣN Φ. such that
(N-11) & Neexp
where is the iteration on which OPTCOV terminates.
By Lemma D.I of Wagenmaker and Jamieson (2023) we have ( A + Aoo)
Φn E (N-((N
N max Oh P.
and the upper bound on the tolerance follows from Lemma D.8 of Wagenmaker and Jamieson (2023).
It remains to justify the bound on i. We do so with the same argument that Wagenmaker and Pacchiano (2023) use. Note that by the definition of OPTCOV, if run for a total N episodes, we can bound & 3 (og2(N). However, we see that the bound on i given above upper bounds (og)(N)) for N the upper bound on the number of samples collected by OPTCOV stated above. Thus, the bound on is valid.
G Miscellanous lemmas
Lemma 17. Let + = Rdd be linear subspace. Suppose ( Me(N) be a collection of unit vectors and (e] IR,, be collection of positive real numbers with mean
σ HN En. Th, Suppose it holds that maxse[H] max (0) Nj. (n)) & Y then the following result satisfies
H Σ D
max
V
9h -
on & THIVNO,
with
An Σ
2h o hn + Alss
Σn
Ala-
Thhn
n=1
Proof. First, we denote o₁ = N Σ,, Th,n- Informally, this implies that most individuals of on, asymptotically on the order of oh, with only a small amount of individuals being higher in order. To rule out the effect of the "large" ones, we group them into the following collection of sets:
(Cr) = (n e [N] Th,n C..r).
Here, we leave the choice of the truncation level C₁. open for now, but note that we allow the truncation levels C₁ vary across different timesteps h and related to σд- It follows by definition that Σ 0 Ho. From an application of Markov's Inequality, the cardinality of set E (Ck) can be upper bounded as
N C₁
We now choose the truncation level C₁, To do so, we follow the steps below quantify the effect induced by the trajectories with high variance (i.e. those that belong to &, (Ca)):
min Φ Mj or min of d
Φh
Th.
30

---

Ph.nPhin
Σ
min th 9.ED
NE(MTTEn(CA))
min &n C₂ PaE
Ph Phi Φh-
ne (C,)
We now utilize basic matrix inequality that for any matrix A, B, we have
min 6 Adr
min @ (A B)on on b
max 0 Bon.
24
which allows us to further bound ming, A 0 Mj on as
min on min 27,00 2 Chân
Σ
bn + Ald on
ONED
max 1h Chōn UnEt
Σ
@h.whhn + Ald on
(CW)
N
->).
2 Chōn
Ch
This leads the following result:
Coff (oft)))))
don
min 07 An min ( due
0h) o1) -o)A))o))=-
max
Noff
Non
where the first equality holds because A, is a linear transformation on the subspace O. Equivalently, this holds from the variational characterization of the eigenvalues and the fact that the largest abso- lute eigenvalue is equal to the inverse of the smallest absolute eigenvalue of the inverse. As a result, in order to rule the effect of the "high variance trajectories", we select the truncation level d; such that N/C, = O))=1), implying CA = O(Nx). Hence, we obtain the following lower bound:
min कn on 2 NaNOR 0,
Finally, we note that
max SLED V ph h
Φh
Σ
min
V
VØl
S SWN N Von & No.o.
oxeb
Lemma 18 (Modified Lemma 1. from Zhou and Gu (2022)). Let Nost , Xon be a partition of S Ax [H), such that their images under the feature map, Doft, Don are subspaces of dimension dott, don respectively. Let (0,,3k) 3k]aal be sequence of non-negative numbers, a, Y 0, [Xx]a21 C Rd and xxell2 & L. Let (Za)az and (ōx)12) be recursively defined as follows: Z₁ XI + Zoft for some symmetric matrix Zoot. where N Noft + K, and we have
Vk > 1,0x max (oRs a, a Xxx [x
Zet1
Zz + 1x Xxx 1/0
Let = log (1 + / (dta))) Then we have
K
K 36 (of + 02).
min (1, 1, 1|xlo, 1xmm
2dont + 2 max 2 + 2 don'y kE[K]
Proof. The proof roughly follows that of Lemma B. in Zhou and Gu (2022), except that we have to make modifications as necessary to tighten the dimension dependence to d and incorporate the offline data.
31

---

Decompose the set [ into a union of two disjoint subsets [K] I U Iz.
I k
[K] ||x//ox " xx.. > 1 1I = [1]
Then the following upper bound of [Z,] holds, where the projector Pon onto 4 has the decompo- sition Pon = Un by the thin SVD, and we write u₁ xx:
1
Σ
min {1, 1/xx ox 0x112 1xam
k
K
min { 2 1xn
K
min {1,0x²x Zr= Zz xx Non
K
Σ
min {1, (UonU xx) TZp (UonU xx)x
K
Σ min (1, x Unn Unn xxx 1xam
K
min
1, 1, Lon
Ix Xxx + Ala
VonVon X Ixon
By Lemma 20, we can take the Uon inside the inverse and conclude that
k Xxx, + Ala UnnUdiXall xx
min
1, 1 UN on
Σ
N or
1==1
K min
k
1, x Uon
Σ xx on - Xn x Uoa + AIdin
Uni 1xo
Intuitively, this because all the 1x Unixn and Lxo. Xn are both in Pon. and in that case the projection is just the identity.
Writing u, UT and invoking Lemma D.5 of Zhou and Gu (2022) (which is restatement of Lemma 11 Abbasi-yadkor et al. (2011)) and the fact that [|x// & L/a, it holds that
Σ min
1, x 1, Von
Σ
INe.
U Xnxxxx Uon + Addoa
Unix Xou
min
T 1, ug
1x o u, u + ALddnn Σ
un Xon
k=1
2dont,
as desired, and conclude that [Za| 2dont.
The rest the proof follows Zhou and Gu (2022) more closely. By the same argument that Zhou and Gu (2022) use,
Σ
min 1, Bk |xxll... Ixom| }
2dout
Σ kEIz
BLōn |x//oxl 1 x
RE[A]
Decompose I, = Ji J2, where
Jn (k Ig 5z ok u u a a
k Ig σx 111x112 Ixem
32

---

Similar to Zhou and Gu (2022),
Σ keTT
Ba |x*/ōxll2; 0x Il Non
Bu (ox a) xx.. min (1, x on l, Xx
ke
k
Bi (ox + ain
min {I, x oxllo Lxaa|
K
K
2
[o + +a?) 6
min { || oā 2n 1.11x0 X Σ
x=1
< 2,
Σ
B (o + a22) dont.
k=1
and as for k T2 have that 0x
72 /xx//Tx zz 1 Non
Σ Bkōu |xa/ōn| z.
Non
72.
Σ
Bu |xa/ /x//oullz, 1x
NEJa
kE
K
2
Σ
Be min { 1, Xx ///x////l22; /xl22 X
& max 3x7 dont. kE[K]
Therefore,
min L, BB ||xbl 2x 1xam < 2dont
dout + 22 donty max kE[K]
38 +
Lemma 19 (Modified Version of Theorem 4.3, Zhou and Gu (2022)). Let (9n) be filtration, and (Xn: Mn)n=1 be a stochastic process such that Xn E Rdd meamsuaule and Th E R mets--easuabbe. Let L, o. X, > O, n* Rd. Arrange the datapoints from the offline and online samples as follows, 1,... Not. Na# + 1.... Non + Non- For = I...., N. let yn. = <4 .x) + and suppose that l/ Xn also satisfy
E Pm
Gn] & 02,1m & R, 1x & L. 9m] = 0, E. The
For n 1,..., N. let Z,, AI Σ X b, Ei= yi:;; Un. Z b and
8n - 12 lod (1 + n I/2/((dA)) log (32 R/c) + 1)m2/8)
+ 24 log (32(log( (t/e) + 1)n²/0) Isien
max
{Ind min { 1, |xille
+ log (32(log( R/c) + 1)n"/8)c c.
Then, for any 0 < < 1, we have with probability at least 1 that,
Vn = 1
N.
Σ
x
& Bn, Imn
11" 11 lla, & Bnn v/ ||
Proof. The proof is merely small wrapper over Theorem 4.3 of Zhou and Gu (2022), where adapt this to our setting the same way that Tan and Xu (2024) do Lemma 1 of their paper. That is, we pre-append the offline data the online data, and generate the Zn. bn Pas 3n accordingly.
As Lemma of Tan and Xu (2024), let arbitrarily, to form episodes 1,... Nott and then begin the online episodes from episode Not + I,..., N. Then, we can directly apply Theorem 4.3 of Zhou and Gu (2022) to recover the desired result.
Noff + Nmn. Order the Noff offline episodes
D
33

---

Lemma 20. Suppose that W . and V R", where < m. Let U W V be a linear transformation and that S (U U.,. As v, ,,,...... Un have
-1 v U U + + VTTTU Σ v )mm)
&
-1
Uv
Proof. For projection matrix U, there exists orthogonal matrix Q Rmxm and diagonal matrix D (In: (m-(m=))) such that U = DQ. We further define u = Uv = Qu. u, = Uv and 0; Qu; for & & n. Then, we note that as v E S, we have v = U = Q AQu. Ač. As result, we may conclude that
where A diag( I, Om-n), which equivalent öT (u On..))
Therefore, with a direct calculation, one will see that
Σ v T + Amm)
0.0 Q Am Amm)
Q
0 + Am Q
Q
Σx 1 u.u.
AI
Q
Amm-n
Q
uau!
AIn)
Q.
0
X I
This will establish our desired conclusion
k Σ
1 TJ ( i + AIn)
LHS
+XIm)
0
i
x I Immn
j=1
u i + AIn)
Σ
u RHS.
H Further details on the numerical experiments
The environment, as in Tan and Xu (2024), a 6-piece wide Tetris board with pieces no larger than 2 x 2, where the action space consists of four actions, differentiated by the degree of rotation in 90 degree intervals and the reward is given by penalizing any increases the height of the stack from tolerance of blocks. As in Tan and Xu (2024), generate feature vectors by projecting the 640-dimensional one-hot state-action encoding onto a 60-dimensional subspace spanned by the top 60 eigenvectors of the feature covariance matrix under 200 trajectories from the uniform behavior policy.
All experiments were single computer with Intel i9- CPU, 128 GB of RAM, and a NVIDIA RTX3090 GPU, in no more than a couple hours.
34

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? Answer: [Yes]
Justification: We claim that our algorithms achieve sharper error or regret bounds that are no worse than, and can improve on, (1) the optimal sample complexity in offline RL (the first algorithm. for PAC RL) and online RL (the second algorithm, for regret-minimizing RL) in linear Markov decide processes (MDPs), and (2) that this work establishes the tight- est theoretical guarantees currently available for hybrid RL in linear MDPs. Theorems and 2, and the accompanying discussion, support claim (1) by being no worse than the associated bounds from Xiong et al. (2023) and He et al. (2023) respectively. Table 2 sup- ports claim (2) by showcasing our improvement over existing hybrid RL methods for linear MDPs.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results
be expected to generalize other settings. It is fine to include aspirational goals as motivation as long as it is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? [Yes]
Answer:
Justification: We include discussion of the limitations of our algorithms and analysis in Section 5 and in the discussion immediately after Theorems and 2. The latter also
contains discussion on the computational efficiency of our algorithms. Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might violated practice and what the implications would be.
The authors should reflect on the scope of the claims made, c.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the ap- proach. For example, a facial recognition algorithm may perform poorly when image resolution is low images taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to ad- dress problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
35

---

Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Ys]]
Justification: Our assumptions and setting are outlined Assumptions and 2, and Sec- tion 2. Any further conditions are outlined in the statement of our theorems and lemmas.
Though we provide proof sketches in the main body, the proof of Theorem is found in Appendix B, and the proof of Theorem 2 is found in Appendix E. Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theo- rems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple-
mented by formal proof' provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Ys]
Justification: The code is available on GitHub github..oomhttaaakiinnnyyriiiii The full details are in Section 4 and Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution is a specific model and empirical evaluation, it may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how replicate the results, access a hosted model (e.g., in the case of a large language model), releasing of a model checkpoint, or other means that are appropriate the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) the contribution primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architccture clearly and fully.
(c) the contribution is a new model (c.g., a large language model), then there should either be way to access this model for reproducing the results or way to produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results. 5. Open access to data and code
36

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: The code is available on GitHub at gitub..com/hetakkvvviyyybbiiiii Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips) cc/
public/guide httss//ooSSuumiiiioiiiii
for more details.
While we encourage the release code and data, we understand that this might not be possible, so "No" is acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for a new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
//nips. cc/ cccppblic//gee wtwp///g/////eeeececeo/cc/.cc Seaiideee//eebbbn (CodeSubmisse wwwssssolliiii onPolicy) for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. If only subset of experiments are reproducible, they should state which ones are omitted from the script and why. At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted. 6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: The full details are in Section 4 and Appendix H.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: One standard deviation error bars are displayed.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi-
dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula,
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
37

---

For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out of range (e.g. negative
error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures or tables in the text. 8. Experiments Compute Resources
Question: For each experiment, does the paper provide sufficient information the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Answer: [Yes]
Justification: All experiments were
single computer with Intel 19-13900k CPU, 128 GB of RAM, and a NVIDIA RTX3090 GPU, in no more than a couple of hours.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g.. preliminary or failed experiments that didn't 't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics https: Answer:
[Yes]
Justification: We have read and reviewed the code of ethics. Our paper is theoretical contribution to the field of reinforcement learning theory, and as such conforms to the guidelines outlined.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed? Answer: [Yes]
Justification: Our paper is theoretical contribution to the field of reinforcement learning theory, and as such any socictal impact will at the very least be second-order impacts not directly tied to our work. Having said that, we discuss that Algorithm I does not randomize over policies, allowing learned policies to be deployed in critical real-world applications, and Algorithm 2 minimizes regret over the online samples, allowing it to be used in situa- tions where aerformance-agnoste online exploration is untenable, such as medicine. Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative socictal impacts include potential malicious unintended uses (c.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact spe- cific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out, For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic al algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
38

---

The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (c.g,, gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)? Answer: [NA]
Question:
Justification: Our paper poses no such risks. Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by re- quiring that users adhere usage guidelines or restrictions access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification: Our paper does not use existing assets. Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include a URL.
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the pack- age should be provided. For popular datasets, paperswithcode com/ datasets has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re- re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided. this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documenta- tion provided alongside the assets?
Answer: [NA]
Justification: Our paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodll as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
39

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution of the paper involves human subjects, then much detail possible should be included the main paper.
According the NeurIPS Code of Ethies, workers involved in data collection, cura- tion, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: Our paper does not involve crowdsourcing nor research with human subjects. Guidelines:
The answer NA means that the paper does not involve crowdsoureing nor research with human subjects.
Depending on the country in which research conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
40


Reviews:
[{"review_id": "swXQgDKSmh", "reviewer": "Reviewer_SSHJ", "summary": "The paper presents studies Hybrid Reinforcement Learning for linear MDPs, where Hybrid RL addresses the limitations of purely offline and online methods by combining offline data and online exploration. The paper introduces two specific algorithms: Reward-Agnostic Pessimistic PAC Exploration-initialized Learning (RAPPEL) and Hybrid Regression for Upper-Confidence Reinforcement Learning (HYRULE). RAPPEL is a online-to-offline approach where one first perform reward agnostic exploration to increase the coverage of the existing data and then perform offline RL method, and HYRULE performs offline-to-online method by starting LSVI_UCB++ with the offline data. Both methods shows improvement over preivous methods, and no worse than offline minimax and online minimax rate, respectively.", "questions": "see above", "limitations": "n/a", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The paper is well-organized, and the literature review is thorough. \n\n2. The proposed method clearly improves on the previous hybrid RL method for linear MDPs, and the online part of the rate indeed of Alg.2 matches the online minimax rate of linear mdps. Overall the improvement of the result is solid. \n\n3. The improvement of the result leverages existing algorithms that are (relatively) well-known as subroutines with intuitive modifications (plus sharper analysis at certain part), which are easy to relate to the literature and intuitive.", "weaknesses": "1. There is no clear new techniques introduced in the paper. \n\n2. The offline rates match the minimax rate only up to the coverage term - the minimax coveage is the single policy coverage, while the proposed algorithm and analysis depends on the all policy coverage.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing helpful comments to our paper! We are glad that you believe our paper is well-organized with a thorough literature review and that our methods are a solid improvement upon previous algorithms in the literature. We have revised our paper based on the suggestions from the reviewers. Please feel free to check on our inclusion of numerical experiments and comments.\n\n**Response to Weaknesses and Questions**\n\n**Q1: There is no clear new techniques introduced in the paper.**\n\nA1: Thanks for raising this question! In fact, there are several technical innovations in our theoretical analysis compared to previous literature. To summarize:\n- Our results are accomplished by decomposing the error onto the offline and online partitions, sharpening the dimensional dependence to $d_{\\text{on}}$ and $c_{off}(\\mathcal{X}_{\\text{off}})$ via projections onto those partitions. \n  - The former is accomplished by Kiefer-Wolfowitz in Algorithm 1, and by proving a sharper variant of Lemma B.1 from Zhou and Gu (2022) in Lemma 16, using this in Lemma 14 to reduce the dimensional dependence in the summation of bonuses enough to achieve the desired result. \n- We maintain a $H^3$ dependence for the error or regret for Algorithms 1 and 2, which is non-trivial. \n  - We accomplish this in Algorithm 1 and for the offline partition in Algorithm 2 by combining the total variance lemma and a novel truncation argument that rules out “bad” trajectories, which allows us to maintain a desirable $H^3$ dependence on both partitions for both algorithms. \n- Algorithmically, the reviewer notes that we use well-known existing algorithms with intuitive modifications to show that one can use common methods for RL in linear MDPs to achieve state-of-the-art sample complexity in the hybrid setting. Despite that, this is the first work to explore the online-to-offline approach in linear MDPs, and although algorithmic novelty is not our key focus, we believe that our work possesses some degree of algorithmic novelty as a result. \n\n**Q2: The offline rates match the minimax rate only up to the coverage term - the minimax coverage is the single policy coverage, while the proposed algorithm and analysis depends on the all policy coverage.**\n\nA2: We agree that a result depending on the partial single-policy concentrability coefficient would have been desirable, and in fact this is addressed in the discussion section of Tan and Xu (2024). That said, it is not entirely clear to us that a partial single-policy concentrability coefficient would be significantly better than a partial all-policy concentrability coefficient, particularly when we take the infimum over partitions in the way we and Tan and Xu (2024) do. This is because a good offline partition for the partial all-policy concentrability would correspond to the portion of the state-action space well-covered by the offline dataset, while the same for the partial single-policy concentrability would be well-covered by offline dataset and the optimal policy. The smaller size of the latter offline partition may be offset by the larger size of the latter’s online partition, and as such any gains may be limited in this analysis of the hybrid setting.\n\nWe also note that our offline rates do indeed match the offline-only minimax rate – our result in equation 6 is no worse than the (nearly) minimax rate achieved by Xiong et al. (2023) that depends on the expected features under the optimal policy. That said, our result falls short of a $c^*_{\\text{off}}(\\mathcal{X}_{\\text{off}})dH^3$ rate. However, it is unclear whether that rate is even possible, and if it is, it is unclear to us how it can be achieved. To our knowledge, there is no $d^xH^y$-style minimax rate for offline RL in linear MDPs available in the literature, and solving that problem would be out of the scope of this paper.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "TeCgIwbr8K", "reviewer": "Reviewer_6qEJ", "summary": "In this work, the authors develop sample and computationally efficient hybrid RL algorithms that are provably better than online-only and offline-only algorithms for linear MDPs. Without relying on the single-policy concentrability assumption, the authors take both online-to-offline and offline-to-online approaches to achieve no worse than optimal sample complexity, regardless of the quality of the behavior policy.", "questions": "Q: I am not familiar with Assumption 2: Full Rank Projected Covariates. Is it a common assumption? How practical is it in downstream applications?\n\nQ: HYRULE seems to be a straightforward generalization of existing algorithms. Could you please list the challenges in proving its regret guarantee?\n\nQ: It would be helpful if there is an experimental plan to verify the algorithms. A simple toy experiment plan should suffice.\n\nMinor suggestion:\n\nAs mentioned in line 241, OPTCOV requires tolerance parameter. Should this parameter also listed in the input of RAPPEL (Algorithm 1)?", "limitations": "Same as weakness. This work focuses on the setting of linear MDPs, where the techniques may not be generalizable to other types of function approximations.", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "This work demonstrates a thorough discussion of all relevant literature, while the results are extensively compared with existing methods.\n\nThis work provides no worse than optimal sample complexity for two types of hybrid RL methods, which is non-trivial.\n\nThe presentation is generally clear, and the appendix is well-organized. The proof appears sound from a quick skim.", "weaknesses": "The assumption regarding Full Rank Projected Covariates seems to implicitly impose some constraints. \n\nNo experimentation or code is included with the work, making it difficult to examine whether the proposed algorithms are efficient in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for providing helpful comments to our paper! We also thank the reviewer for believing that our contribution is non-trivial, and for confirming the soundness of the proofs. We have revised our paper based on your suggestions, including new numerical experiments. If you think our responses adequately address your concerns, we will be glad if you choose to increase your score.\n\n**Response to Weaknesses and Questions**\n\n**Q1: I am not familiar with Assumption 2: Full Rank Projected Covariates. Is it a common assumption? How practical is it in downstream applications?**\n\nA1: This assumption is inherited from Wagenmaker and Jamieson (2022) and Wagenmaker and Pacchiano (2023). Wagenmaker and Jamieson (2022) stated that this is analogous to other explorability assumptions in the literature (Zanette et al. (2020), Hao et al. (2021), and Agarwal et al. (2021)). It essentially requires that there is some policy that collects covariates that span the entire feature space. In practice, this is achievable for any linear MDP via a transformation of the features that amounts to a projection onto the eigenspace corresponding to the nonzero singular values. For example, this is performed for the numerical simulations attached in the pdf file for the global response – as in Tan et al. (2024), the feature vectors are generated by projecting the 640-dimensional one-hot state-action encoding onto a 60-dimensional subspace spanned by the top 60 eigenvectors of the covariance matrix of the offline dataset. \n\n**Q2: HYRULE seems to be a straightforward generalization of existing algorithms. Could you please list the challenges in proving its regret guarantee?**\n\nA2: We agree that HYRULE is a straightforward generalization of LSVI-UCB++ in He et. al (2023), with $\\Sigma_0$ initialized with the offline dataset. However, to achieve the regret guarantee in Theorem 2, we had to decompose the regret into the regret on the offline and online partitions. In the process, we faced the following challenges:\n1. Bounding the regret on the offline partition was challenging, as we were not able to utilize the technique that was used in He et. al (2023). Instead, we bounded the regret with the maximum eigenvalue of $\\Sigma_{off,h}^{-1}$. To maintain a H^3 dependence on the offline partition, we had to use a truncation argument in Lemma 13 that we also deployed in proving the regret guarantee of Algorithm 1 (RAPPEL). \n2. Bounding the regret on the online partition allowed us to use an analysis that was close to that of He et. al (2023). However, directly following the argument of He et al. (2023) would have left us with a d^2H^3 dependence in Theorem 2. To reduce the dimensional dependence to d_{on}dH^3, we prove a sharper variant of Lemma B.1 from Zhou and Gu (2022) in Lemma 16, using this in Lemma 14 to reduce the dimensional dependence in the summation of bonuses enough to achieve the desired result. \nWithout the above two techniques, one could have used a simpler analysis to achieve a far looser $\\sqrt{c_{off}(X_{off})^2d^6H^8 N_{on}^2/N_{off}} + \\sqrt{d^2H^3}$ regret bound by using the maximum magnitude of the variance weights for the offline partition and the analysis from He et al. verbatim for the online partition, but this would not have yielded the same improvement.\n\n**Q3: It would be helpful if there is an experimental plan to verify the algorithms. A simple toy experiment plan should suffice.**\n\nA3: We thank the reviewer for this helpful suggestion! We have added numerical simulations and report our results in the pdf file attached. The global response contains a more detailed summary of our findings, but in brief we show that:\n1. Although reward-agnostic hybrid exploration with the uniform behavior policy achieves the best coverage throughout as expected, even reward-agnostic hybrid exploration with adversarially collected offline data achieves better coverage than online-only exploration. (Fig. 1)\n2. When learning from a dataset collected by reward-agnostic exploration as in Algorithm 1, hybrid exploration outperforms offline-only learning and online-only reward-agnostic exploration when the behavior policy is adversarial. (Fig. 2)\n3. Initializing a regret-minimizing online RL algorithm (LSVI-UCB++) with offline data from a uniform behavior policy as in Algorithm 2 yields lower regret than LSVI-UCB++ without an offline dataset. This shows that even a nearly minimax-optimal online learning algorithm can stand to benefit from being initialized with offline data. (Fig. 3)\n\n**Q4: As mentioned in line 241, OPTCOV requires tolerance parameter. Should this parameter also be listed in the input of RAPPEL (Algorithm 1)?**\n\nA4: We thank the reviewer for this suggestion! We agree that the parameter should be listed in the input of RAPPEL, and have made the change. \n\n**Q5: This work focuses on the setting of linear MDPs, where the techniques may not be generalizable to other types of function approximations.**\n\nA5: We agree that some of the specific techniques used may not translate to the general function approximation setting. That said, many of the general techniques and methods will still be very applicable. For instance, the offline-to-online approach is studied by Tan and Xu (2024) in the general function approximation setting, and one could use a similar analysis in spirit to our analysis of Algorithm 2 in order to attain better regret bounds than that found by Tan and Xu (2024) by e.g. analyzing the OLIVE algorithm of Du et al. (2021), sharpening dependencies whenever possible while decomposing the error onto the offline and online partitions. Another example lies in the online-to-offline approach in the context of general function approximation, where using a reward-agnostic exploration algorithm like RF-OLIVE or RF-GOLF, followed by a pessimistic offline algorithm like A-CRAB from Zhu et al. (2023) is one potential way forward that uses a similar analysis to our analysis of Algorithm 1.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "5lSTa17cGv", "reviewer": "Reviewer_stbS", "summary": "This paper studies the hybrid reinforcement learning problem in the linear MDP setting. It provides two algorithms (one focused on improving the offline error and the other on improving the online error) with theoretical analysis on their sample complexity. Though the algorithms are not optimal in terms of sample complexity with respect to some problem parameters, it appears to be the state-of-the-art in the literature for the linear setting.", "questions": "It would be nice to discuss how Algorithm 1 compares with Algorithm 2, aside from the difference in approach (e.g., why isn’t one clearly better than the other).\n\nWhy is $|A|$ in Line 303? If that is not a typo, then it seems to be another weakness of Algorithm 2, since the action space might not be discrete.", "limitations": "N/A", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper is clearly written; the problem formulation and assumptions are clearly stated. The theoretical results seem sound.", "weaknesses": "Aside from the suboptimality in $d$ and $H$ already pointed out by the authors, another weakness is that Algorithm 2 has a pretty large minimum requirement for the size of the offline dataset.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their comments and questions. We are glad that the reviewer confirms the soundness of our results and that our result is state-of-the-art for the hybrid linear MDP setting. We answer your questions below. \n\n**Response to Weaknesses and Questions**\n\n**Q1: Aside from the suboptimality in d and H already pointed out by the authors, another weakness is that Algorithm 2 has a pretty large minimum requirement for the size of the offline dataset.**\n\nA1: We agree that the minimum requirement for the size of the offline dataset in the analysis is large. This issue is linked to the high burn-in cost that LSVI-UCB++ requires in general. This is hard to improve, as it arises from the use of the total variance lemma in the analysis (in various places). However, we believe that this issue pales in comparison to the similarly large requirement on online episodes that the burn-in cost imposes, as in many situations offline data is cheaper and more plentiful than online data (motivating the setting of hybrid RL in general). Fortunately, this issue seems to be limited to the analysis and does not necessarily occur in practice – within the new numerical simulations attached to the pdf in the global response, we find that with only 200 episodes of offline data, Algorithm 2 achieves a much-improved regret compared to the online-only LSVI-UCB++ within the Tetris environment of Tan and Xu (2024). Experimentally, this also extends to as few as 50 episodes, though we do not report those results for brevity.\n\n**Q2: It would be nice to discuss how Algorithm 1 compares with Algorithm 2, aside from the difference in approach (e.g., why isn’t one clearly better than the other).**\n\nA2: We thank the reviewer for raising this good question! Actually, Algorithm 1 and Algorithm 2 both enjoy their own advantages and also suffer from their own drawbacks. We will discuss them in detail here.\n- Algorithm 1 is an online-to-offline algorithm where the final policy is given by an offline RL algorithm, which is deterministic, and this allows the algorithm to be deployed in some critical regimes that randomization is not allowed. Besides, as Algorithm 1 performs reward agnostic exploration, we are able to use the combined dataset to learn tasks with different reward functions. \n- Algorithm 2 is an offline-to-online algorithm which is fully unaware of partition, so we don’t need to estimate $d_{\\text{on}}$ at the beginning before performing the algorithm. The algorithm provides a regret guarantee, which can be deployed in some specific scenarios where minimizing the regret is important.\n- As for why neither algorithm achieves a much better error bound compared to the other, we bring the reviewer’s attention to the tabular case to illustrate. Li et al. (2023) use the online-to-offline approach to achieve an error of $\\inf_{\\sigma \\in [0,1]} O(\\sqrt{H^3SA\\min(\\sigma H, 1)} + \\sqrt{H^3SC^*(\\sigma)})$, while the result of Tan and Xu (2024) and our analysis suggests that one could possibly use a similar approach to our Algorithm 2 to achieve a regret bound not too far from $O(\\sqrt{H^3Sc_{\\text{off}}(X_{\\text{off}}) N_{\\text{on}}^2/N_{\\text{off}}} + \\sqrt{H^3SAN_{\\text{on}}})$ by modifying the algorithm of Azar et al. (2017) to accommodate the use of offline data. As such, one can achieve sample size gains over purely offline and purely online learning with either approach. It is therefore our opinion that neither approach is conclusively better with regard to sample efficiency than the other, and considerations like those stated in the previous two bullet points should govern the deployment of either instead. \n\n**Q3: Why is |A| in Line 303? If that is not a typo, then it seems to be another weakness of Algorithm 2, since the action space might not be discrete.**\n\nA3: As the reviewer notes correctly, that is the cardinality of the action space. However, this does not correspond to a weakness of Algorithm 2. The action space need not be discrete, as one can similarly search over all possible actions with a continuous action space with e.g. projected gradient descent or a random search. We simply performed the computational complexity analysis, with results in Line 303, with a discrete action space for simplicity, in line with that of He et al. (2023). However, we agree that this was not stated as clearly as it perhaps should have been, and apologize for the confusion.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "OvXopUguZd", "reviewer": "Reviewer_ujdT", "summary": "This paper studies hybrid RL in linear MDPs, aiming to address the problem of whether hybrid RL can improve upon the existing lower bounds established in purely offline and purely online settings, without relying on the single-policy concentrability assumption. By combining offline dataset with online interaction, authors introduce computationally efficient algorithms which achieve sharper error bound and regret bound in offline and online settings.", "questions": "1. Could you highlight the main technical techniques / reason why Alg. 2 can achieve better regret compared to Tan and Xu, 2024 and Amortila et al., 2024 for the linear MDP case?\n\n2. In the studied setting, if we consider general function approximation or a more general class of MDPs with linear structure, do you envision the current analysis and results can be utilized to improve existing bounds?\n\n3. Could you comment on the optimality of the provided bounds, whether dependence on the parameters involved can be further improved?\n\n4. Could you provide an intuitive explanation of concentrability coefficient? And what is the range that indicates good concentrability? In line 135, does $d^*$ represent the occupancy measure of the optimal policy?", "limitations": "This is a theoretical work, no negative social impact.", "rating": 6, "confidence": 3, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "Existing theoretical works of hybrid RL under function approximation mainly focus on PAC guarantees which are not tight and require stringent concentrability assumptions on the quality of the behavior policy. Motivated by the question of whether hybrid RL is useful (i.e. improving upon the existing lower bounds established in purely offline and purely online RL without relying on the single-policy concentrability assumption, which is raised by Xie et al. (2022b)), authors provide computationally efficient algorithms for both PAC and regret-minimizing RL for linear MDPs, without relying on single-policy concentrability.\n\n\nIn particular, this work exhibits several interesting findings:\n1.  Algorithmically, two types of hybrid RL algorithms are introduced: an online-to-offline algorithm, which involves reward-agnostic online exploration followed by a pessimistic offline algorithm to learn an optimal policy; and additionally, an offline-to-online method that utilizes offline data to warm start an online algorithm.\n\n2. Theoretically, authors show both algorithms improve upon existing sample complexity, which is measured with respect to either the PAC framework or the regret.\n\nThis work demonstrates clear rationale and compelling motivation, while clearly articulates its main ideas throughout the draft. Thorough discussion of related works have been provided. It develops a better theoretical understanding of hybrid RL in linear MDPs, which potentially benefits future works for hybrid RL with functional approximation in this context.", "weaknesses": "Below are several potential improvements that authors are suggested to consider:\n\n1. It is better to summarize and highlight the main technical novelties in the main text. There exist extensive theoretical studies in either linear MDPs or in hybrid RL. It is still not quite clear throughout the main text what the main technical challenges are in achieving the optimal policy in the studied context and what the technical novelties are in improving existing theoretical results. It seems to me that the proofs closely follow Xiong et al. (2023) in offline RL,  Wagenmaker and Pacchiano (2023) in reward-agnostic exploration and He et al. (2023) in linear MDPs. As a result, it is important to point out how the studied settings can be technically challenging, and what novel arguments are developed compared to existing works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for their helpful comments. We are glad that you find our findings interesting, and further thank the reviewer for their kind words that our motivation is compelling, our rationale is clear, and that our work has potential downstream impact. We address the reviewer’s questions and concerns below. If you think the responses adequately address your concerns, we will be glad if you choose to increase your score.\n\n**Response to Weaknesses**\n\n**W1: It is better to summarize and highlight the main technical novelties in the main text.**\n\nA1: We thank the reviewer for raising this concern! We agree with the reviewer in that it is better to include this in the main text, and will do so in an updated version. Regarding the second half of the reviewer’s comment, although we use well known existing algorithms with intuitive modifications, obtaining regret guarantees in our paper is not trivial if we just simply follow the previous arguments. We highlight several technical innovations in our paper within the global rebuttal, and also elaborate further in our answer to Question 1 below. \n \n**Responses to Questions**\n\n**Q1: Could you highlight the main technical techniques / reason why Alg. 2 can achieve better regret compared to Tan and Xu, 2024 and Amortila et al., 2024 for the linear MDP case?**\n\nA1: There are two main reasons why we achieve better regret with Algorithm 2. \n1. The first is in our choice of online learning algorithm – we use LSVI-UCB++, which possesses a minimax-optimal $\\sqrt{d^2H^3N_{on}}$ online-only regret bound. In contrast, the GOLF algorithm that Tan and Xu (2024) use incurs an extra factor of H^2 due to the use of the squared Bellman error and lack of variance-weighting. Amortila et al. (2024) require a weight function class, incurring an extra dH dependence, in total having $\\sqrt{d^3H^6N_{on}}$ regret.\n2. The second is in our careful analysis in the proof of Theorem 2. The truncation argument in Lemma 13 allows us to incur only a H^3 dependence in the offline portion of the regret bound, while we sharpen the dimensional dependence in the online part of the bound by proving a sharper variant of Lemma B.1 from Zhou and Gu (2022) in Lemma 16, using this in Lemma 14 to reduce the dimensional dependence in the summation of bonuses enough to achieve the desired $d_{on}dH^3N_{on}$ term. Without the above two techniques, one could have used a simpler analysis to achieve a much looser $\\sqrt{c_{off}(X_{off})^2 d^6 H^8 N_{on}^2/N_{off}} + \\sqrt{d^2H^3}$ regret bound by using the maximum magnitude of the variance weights for the offline partition and the analysis from He et al. verbatim for the online partition. Doing so would have still yielded an improvement over Tan and Xu (2024) and Amortila et al. (2024), but would not have yielded the same improvement that we managed to achieve.\n\n**Q2: In the studied setting, if we consider general function approximation or a more general class of MDPs with linear structure, do you envision the current analysis and results can be utilized to improve existing bounds?**\n\nA2: Absolutely! While some of the fine-grained techniques used in the analysis may not translate to the general function approximation setting, we believe that many of the general techniques will still be very applicable. For instance, one could use a similar analysis in spirit to our analysis of Algorithm 2 in order to attain better regret bounds than that found by Tan and Xu (2024) by e.g. analyzing the OLIVE algorithm of Du et al. (2021) and sharpening dependencies whenever possible while decomposing the error onto the offline and online partitions.\n\nThe analysis for a more general class of MDPs with linear structure is far more straightforward. We believe that for the case of linear mixture MDPs, for instance, one could use a similar analysis to Theorem 2 on the UCRL-VTR+ algorithm by Zhou et al. (2020) to achieve a similar result. \n\n**Q3: Could you comment on the optimality of the provided bounds, whether dependence on the parameters involved can be further improved?**\n\nA3: The error bound for Algorithm 1 is no worse than the offline-only minimax rate, as our result in equation 6 is no worse than the (nearly) minimax rate achieved by Xiong et al. (2023) that depends on the expected features under the optimal policy. Our guess is that it could maybe be sharpened to be as low as a $O(c^*_{off}(\\mathcal{X}) d H^3)$ rate previously mentioned, but it is unclear to us how to achieve this even in the context of purely offline RL. To our knowledge, there is no $d^xH^y$-style minimax rate for offline RL in linear MDPs available in the literature that would inform us as to whether that is possible. \n\nRegarding the regret bound for Algorithm 2, the online $d_{on}dH^3$ portion of the regret bound is as good as it gets. It may be possible to shave off a factor of $c_{off}(X_{off})$ from the offline $c_{off}(\\mathcal{X}_{off})^2dH^3$ portion, but it is unclear to us how that can be done. Despite that, we emphasize that the existing regret bound for Algorithm 2 is already no worse than the online-only minimax regret, and as such we already show provable gains over online-only learning in Theorem 2.\n\n**Q4: Could you provide an intuitive explanation of concentrability coefficient? And what is the range that indicates good concentrability? In line 135, does $d^{\\star}$ represent the occupancy measure of the optimal policy?**\n\nA4: One can think of the concentrability coefficient as an “inflation factor’’ on the number of offline samples collected. $N_{off}/c_{off}(\\mathcal{X}_{off})$, or the number of offline samples divided by the concentrability coefficient, may be thought of as an ``effective sample size’’. If the concentrability coefficient is low, think 1-10, that is as good as it gets – each offline sample is approximately as good as an online sample.\n\n$d^{\\star}$ does indeed represent the occupancy measure of the optimal policy.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:
We thank the reviewers for their comments and suggestions on our paper. We also thank the reviewers for their kind comments that our findings were interesting and our results were sound and nontrivial. 

**Technical Contributions**

For the benefit of everyone, we provide a summary of our technical contributions. 
1. Our results are accomplished by decomposing the error onto the offline and online partitions.
2. We sharpen the dimensional dependence from $d$ to $d_{\text{on}}$ and $c_{\text{off}}(\mathcal{X}_{\text{off}})$ via projections onto those partitions. 
  a. The former is accomplished in Algorithm 1 by Kiefer-Wolfowitz, and in Algorithm 2 by  proving a sharper variant of Lemma B.1 from Zhou and Gu (2022) in Lemma 16, using this in Lemma 14 to reduce the dimensional dependence in the summation of bonuses enough to achieve the desired result. 
3. We maintain a $H^3$ dependence for the error or regret for Algorithms 1 and 2, which is non-trivial. 
  a. We accomplish this in Algorithm 1 and for the offline partition in Algorithm 2 by combining the total variance lemma and a novel truncation argument that rules out “bad” trajectories.
4. Algorithmically, we use well-known existing algorithms with intuitive modifications to show that one can use common methods for RL in linear MDPs to achieve state-of-the-art sample complexity in the hybrid setting. This is also the first work to explore the online-to-offline approach in linear MDPs.

**Numerical Experiments**

Upon the request of one reviewer, we also provide a series of numerical experiments, in order to demonstrate the benefits of hybrid RL in the offline-to-online and online-to-offline settings. We implement Algorithms 1 and 2 on the scaled-down Tetris environment from Tan et al. (2024). This is a $6$-piece wide Tetris board with pieces no larger than $2 \times 2$, where the action space consists of four actions, differentiated by the degree of rotation in 90 degree intervals and the reward is given by penalizing any increases in the height of the stack from a tolerance of $2$ blocks. The offline dataset consists of $200$ trajectories generated from a uniform behavior policy. As in Tan et al. (2024), the feature vectors are generated by projecting the $640$-dimensional one-hot state-action encoding onto a $60$-dimensional subspace spanned by the top $60$ eigenvectors of the covariance matrix of the offline dataset. 
1. Figure 1 depicts the coverage (defined by $1/\lambda_{\min}(\Lambda), 1/\lambda_{d_{\text{off}}}(\Lambda_{\text{off}}), 1/\lambda_{d_{\text{on}}}(\Lambda_{\text{on}})$) achieved by the reward-agnostic exploration algorithm, OPTCOV, when initialized respectively with $200$ trajectories from (1) a uniform behavioral policy, (2) an adversarial behavior policy obtained by the negative of the weights of a fully-trained agent under Algorithm 1, and (3) no offline trajectories at all for fully online learning. It shows that although hybrid RL with the uniform behavior policy achieves the best coverage throughout as expected, even hybrid RL with adversarially collected offline data achieves better coverage than online-only exploration. This demonstrates the potential of hybrid RL as a tool for taking advantage of poor quality offline data. 
2. In Figure 2, one can observe that hybrid RL demonstrates strong benefits in the online-to-offline setting when the behavior policy is of poor quality. When applying offline learning to the hybrid dataset of $200$ trajectories and $100$ online trajectories, $300$ trajectories of adversarially collected offline data, and $300$ trajectories of online data under reward-agnostic exploration, we see that the hybrid dataset is most conducive for learning. Additionally, without a warm-start from offline data, online-only reward-agnostic exploration performs worse than the adversarially collected offline data due to significant burn-in costs. Hybrid RL therefore, in this instance, performs better than both offline-only and online-only learning alone.
3. In Figure 3, we compare the performances of LSVI-UCB++ and Algorithm 2. It can be seen from the figure that initializing a regret-minimizing online algorithm (LSVI-UCB++, He et al. (2023)) with an offline dataset as in Algorithm 2 yields lower regret than the same algorithm without an offline dataset. This shows that even a nearly minimax-optimal online learning algorithm can stand to benefit from being initialized with offline data.

Meta-review: This paper on hybrid (online/offline) RL for linear MDPs presents online-to-offline and offline-to-online algorithms with improved theoretical guarantees.

Although observing that the algorithmic contribution is limited, being based on modifications of existing algorithms, the reviewers agree that the theoretical contribution is significant and sound, and praise the thorough discussion of related works.

Some important points were clarified in the discussion phase. In particular, for the paper to be ready for publication, it is fundamental that the authors make the following additions to the camera-ready version:

- Better highlight the technical contributions, as done in responding to multiple reviewers

- Add the new experiments, which were requested and later judged valuable by one reviewer

In addition, I strongly recommend to further clarify the point on "partial single-policy" vs "partial all-policy" concentrability. In the current version of the manuscript, the claim that theoretical guarantees are obtained "without single-policy concentrability" could be misleading. In fact, it is not clear whether partial all-policy concentrability is always preferable to full *single*-policy concentrability, nor whether a partial single-policy concentrability result would yield a significant improvement. A discussion on this is needed, but something on the lines of the answer to Q2 of Reviewer SSHJ should suffice. 

The meaning of the terms "partial" and "full" in the paper should also be clearly explained at the beginning of the manuscript, since in the offline RL literature "partial" is sometimes used as a synonym of "single-policy" and "full" as a synonym of "all-policy". Clearly, this could be confusing for some readers without a proper disclaimer.
Decision: Accept (poster)