Hybrid Reinforcement Learning Breaks Sample Size Barriers In Linear MDPs

Authors: kevin  tan
wei  fan
yuting  wei
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-14 23:40:33

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.

Main paper: 
 introduction: 
 Reinforcement learning (RL) holds great promise in attaining reliable decision-making in adaptive environments for a broad range of modern applications. Typical RL algorithms often require an enormous number of training samples, motivating a line of recent efforts to study the sample efficiency of RL algorithms. There are two mainstream paradigms of RL, distinguished by how samples are collected: online RL and offline RL. In online RL, 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 et 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 a 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 sample-hungry, but offline methods often impose stringent requirements on the quality of the pre-collected data.To address the limitations of both, the setting of hybrid RL (Song et al., 2023; Xie et al., 2022b) has recently received considerable attention from both theoretical and practical perspectives (Amortila et al., 2024; Ball et al., 2023; Kausik et al., 2024; Li et al., 2023b; Nair et al., 2020; Nakamoto et 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 of 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 . 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 approximation 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 features (e.g. pre-trained neural embeddings). It has been extensively studied due to its benefits in dimension reduction and mathematical tractability in 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 RL algorithms in the setting of hybrid RL that are provably better than online-only and offline-only algorithms for linear MDPs?To answer the question above, we introduce two types of approaches widely-adopted in hybrid RL.The offline-to-online approach: Most of the current literature (e.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-minimizing online RL. We refer to this as the offline-to-online approach. 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 online-to-offline approach: However, if our goal is to output a near-optimal policy, especially in real-world situations in medicine and defense, randomizing between policies can be suboptimal or even unethical. Recently, Wagenmaker and Pacchiano (2023) and Li et al. (2023b) propose using reward-agnostic online exploration to explore parts of the state space unseen by the behavior policy, to construct a dataset that is especially amenable to leverage the sharp performance guarantees of offline RL. We refer to this as the online-to-offline 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.• We propose an online-to-offline method called Reward-Agnostic Pessimistic PAC Exploration-initialized Learning (RAPPEL) in Algorithm 1. It employs reward-agnostic online exploration to enhance the offline dataset, then learns a policy through a pessimistic offline RL algorithm. Algorithm 1 significantly improves upon the sample complexity of the only dedicated hybrid RL algorithm for linear MDPs (Wagenmaker and Pacchiano, 2023 ) by a factor of at least H 3 . This performs no worse than the offline-only minimaxoptimal 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-offline approach in linear MDPs. c off pX off qdH 3 mintc off pX off q, Hu{N off `ad on dH 3 mintd on , Hu{N on (Alg. 1) Hybrid C ˚?d 2 H 6 N on (Nakamoto et al., 2023; Song et al., 2023 ) (Offline-to-online Regret) a pC ˚`c on pX qqd 3 H 6 N on (Amortila et al., 2024 ) a c off pX off qdH 5 N 2 on {N off `?d on dH 5 N on (Tan and Xu, 2024 ) a c off pX off q 2 dH 3 N 2 on {N off `ad on dH 3 N on (Alg. 2)Table 2 : Comparisons of our results to 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, N off " N on , and the online term in our results (depending on N on ) 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 no worse than the online-only minimax optimal bound, with the potential of significant gains if 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 RL in scenarios where offline samples are much cheaper or much easier to acquire. To the best of our knowledge, we are the first to show improvements over the aforementioned lower bounds of hybrid RL algorithms (in the same vein as Li et al. (2023b) ) in the presence of function approximation, without any explicit requirements on the quality of the behavior policy, and with both the offline-to-online and online-to-offline 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 ).Technical contributions. In this work, we build on recent advancements in offline and online RL, demonstrating that intuitive modifications suffice to achieve state-of-the-art 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 on and c off pX off q via projections onto those partitions. The former is accomplished in Algorithm 1 by Kiefer-Wolfowitz in Lemma 1, and in Algorithm 2 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, which helps achieve the desired result. 2. We maintain a H 3 dependence for the error or regret for both algorithms, which is nontrivial, in Algorithm 1 and for the offline partition in Algorithm 2 by combining the total variance lemma with a novel truncation argument for "bad" trajectories in Lemma 17. 
basics of markov decision processes: 
 An episodic MDP is a tuple M " `S, A, H, pP h q H h"1 , pr h q H h"1 ˘, where S is the state space, A the action space, H the horizon, pP h q H h"1 the collection of transition probability kernels P h : S ˆA Ñ ∆pSq, and pr h q H h"1 the collection of reward functions r h : S ˆA Ñ r0, 1s. ∆p¨q is the collection of distributions over a set. At each h P rHs " t1, ..., Hu, an agent observes the current state s h P S, takes an action a h P A according to π h : S Ñ ∆pAq, and observes the reward r h and next state s h`1 " P h p¨| s h , a h q. We write Π for the set of policies π " tπ h u H h"1 , with value and Q-functions for every ps, hq P S ˆrHs :EQUATIONand for every ps, a, hq P S ˆA ˆrHs :Q π h ps, aq :" E π r ř H h 1 "h r h 1 |s h " s, a h " as. (2)π ˚" tπ ˚uH h"1 is the optimal policy attaining the highest value and Q-functions, and we write V ˚" tV h u H h"1 and Q ˚" tQ hu H h"1 for the optimal value and Q-functions. We consider the setting of hybrid RL, where an agent has access to two sources of data: • N on sequential episodes of online data, where at each episode n " 1, ..., N on , the algorithm has knowledge of the N off offline episodes and the previous online episodes 1, ..., n ´1. The quality of the behavior policy π b is measured by the all-policy and single-policy concentrability coefficients proposed by Xie et al. (2023); Zhan et al. (2022) : Definition 1 (Occupancy Measure). For a policy π " tπ h u H h"1 , its occupancy measure d π " td π h u H h"1 corresponds to the collection of distributions over states and actions induced by running π within M, where for some initial distribution ρ and s 1 " ρ, we have d π h ps, aq :" Pps h " s, a h " a | s 1 " ρ, πq.(3) Definition 2 (Concentrability Coefficient). The all-policy and single-policy concentrability coefficients of π with regard to the occupancy measure µ " tµ h u Policy learning and regret minimization. Hybrid RL aims to either learn an ϵ-optimal policy p π such that V ˚´V p π ď ϵ with high probability, or to minimize the regret. Here, the regret of an online algorithm L :H Ñ Π is Reg L pT q :" Er ř T t"1 pV 1 psThis allows for sample-efficient RL for a few reasons. Firstly, linear MDPs are Bellman complete (Jin et al., 2021a) , 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 et al., 2023; Hu et 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 ϕ n,h " ϕps pnq h , a pnq h q for the feature vector at episode n and horizon h.Let Λ h " ř N n"1 ϕ n,h ϕ J n,h `λI and Λ off,h " ř N off n"1 ϕ n,h ϕ J n,h`λI be the covariance 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, namelyEQUATIONis the truncated variance of the optimal value function (where s, a are random variables) and σ´2 n,h is the variance estimator from He et al. (2023) .We aim to 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 π ˚visits. A natural idea from Li et al. (2023b) is to partition this space into a component that is well-covered by the behavior policy, which we call the offline partition X off , and a component requiring further exploration, which we call the online partition X on . Based on this partition, similarly to Tan and Xu (2024) , the estimation error or regret of a hybrid RL algorithm can be analyzed on each component separately. We define X on Y X off " rHs ˆS ˆA, with their images under the feature map Φ off " SpanpϕpX off,h qq hPrHs Ď R d and Φ on " SpanpϕpX on,h qq hPrHs Ď R d being subspaces of dimension d off and d on respectively. Write P off , P on for the orthogonal projection operators onto these subspaces respectively. Let λ k pM q denote the k-th largest eigenvalue Run an exploration algorithm (OPTCOV, Wagenmaker and Jamieson (2023) ) to collect covariates Λ h such that max ϕ h PΦ ϕ J h pΛ h `λI `Λoff,h q ´1ϕ h ď τ. of a symmetric matrix M. We borrow the definition of partial offline all-policy concentrability,1 c off pX off q :" maxEQUATIONfrom Tan and Xu (2024) . This corresponds to the inverse of the d off -th largest eigenvalue of the covariance matrix of the projected feature maps. Similarly, the partial all-policy analogue of the coverability coefficient from Xie et al. ( 2022a) is c on pX on q :" infEQUATIONAs we shall see, these quantities characterize the estimation error of our proposed algorithms.Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes] Justification: We include a discussion of the limitations of our algorithms and analysis in Section 5 and in the discussion immediately after Theorems 1 and 2. The latter also contains a 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 a 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 authors should reflect on how these assumptions might be violated in practice and what the implications would be. • The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with a 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 approach. For example, a facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-text system might not be used reliably to provide closed captions for online lectures because it 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 address problems of privacy and fairness. • While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an important role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations. 
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 augment the offline data, then invoking offline RL (Xiong et al., 2023) to learn an ϵ-optimal policy on the combined dataset, in the same vein of Li et al. (2023b) . This is Algorithm 1. 2. Warm-starting an online RL algorithm (He et al., 2023) with parameters estimated from an offline dataset to minimize regret, as in Song et al. (2023) , with details in Algorithm 2.Algorithm 1 collects online samples informed by the degree of coverage (or lack thereof) of the offline dataset D off with a reward-agnostic online exploration algorithm called OPTCOV from Wagenmaker and Jamieson (2023) . OPTCOV explores so that the smallest eigenvalue of the covariance matrix, λ min pΛ h q, is no smaller than a tolerance parameter 1{τ . We then learn a policy from the combined dataset using a minimax-optimal pessimistic offline RL algorithm from Xiong et al. (2023) , LinPEVI-ADV+. To employ OPTCOV, one requires a modified analogue of the full-rank covariate assumption from Wagenmaker and Pacchiano (2023) that ensures that the MDP is "explorable" enough. This assumption is only imposed for Algorithm 1. Assumption 2 (Full Rank Projected Covariates). For any partition X on Y X off " rHs ˆS ˆA, c on pX on q ă 8, or equivalently that inf π min h λ don pE d π h rpP on ϕ h qpP on ϕ h q J sq " λ don ą 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 as its dimension at every timestep. In practice, this is achievable for any linear MDP via projecting the features onto the eigenspace corresponding to the nonzero singular values. We can then establish the following: Lemma 1 (Partial Coverability Is Bounded In Linear MDPs). For any partition X off , X on , it satisfies that c on pX on q ď d on . Also, there exists at least one partition such that c off pX off q " Opdq. 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 α off :" N off {N , α on :" N on {N , and the minimal online samples for explorationN ˚pτ q :" min N N s.t. inf ΛPΩ max ϕPΦ ϕ J `N pΛ `λIq `Λoff ˘´1 ϕ ď τ.We now have, with full proof in Appendix B and sketch at the end of the subsection, the following:Theorem 1 (Error Bound for RAPPEL, Algorithm 1). For every δ P p0, 1q and any partition X off , X on , when choosing τ ď Õpmaxtd on {N on , c off pX off q{N off uq, RAPPEL achieves w.p. 1 ´δ:EQUATIONgiven N ě max ␣ α 4 on d ´4 on , α 4 off c off pX off q ´4( maxtN ˚pτ q, polypd, H, c off pX off q, log 1{δqu. This result, when applied to tabular MDPs with finite states and actions, yields: Corollary 1. In tabular MDPs, for every δ P p0, 1q, it satisfies that with probability at least 1 ´δ,EQUATIONIn sum, Theorem 1 shows that with a polypd, Hq 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 c off pX off qdH 3 mintc off pX off q, Hu{ϵ 2 `don dH 3 mintd on , Hu{ϵ 2 trajectories to learn an Opϵq-optimal policy. N ˚, from Wagenmaker and Pacchiano (2023) , is essentially 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 a d 2 H 7 {N attained in Wagenmaker and Pacchiano (2023) (by at least a factor of H 3{2 ), the only other work on hybrid RL in linear MDPs thus far. While we employ the same online exploration procedure, we combine our exploration phase with an offline learning algorithm LinPEVI-ADV+ from Xiong et al. (2023) and conduct a careful analysis. When comparing with the offline-only and online-only settings, Theorem 1 improves upon the offline-only minimax-optimal error bound of (2021b) ) that λ min pΛ h,off q ě Ωp1{dq, Theorem 1 enjoys better dimension and horizon dependence as there is always a partition such that d on , c off pX off q ď d and d on H 3 mintd on , Hu ď d 2 H 4 .? d ř H h"1 E π ˚||ϕps h , a h q|| Σ ˚´1 off,The literature has experienced considerable difficulty in sharpening the horizon dependence to H 3 in offline RL for linear MDPs. While Yin et al. (2022) and Xiong et al. (2023) provide minimaxoptimal algorithms for offline RL in linear MDPs, both only manage to achieve a H 3 horizon dependence in the special case of tabular MDPs, even under the aforementioned "well-covered" assumption. We provide the same result in Corollary 1 with proof deferred to Appendix C, but encouragingly, hybrid RL 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 a c off pX off qdH 3 {N off `ad on dH 3 {N on . Computational efficiency. In terms of computational efficiency, Algorithm 1 inherits the computational costs of the previous proposed algorithms OPTCOV and LinPEVI-ADV+ (Wagenmaker and Jamieson (2023); Xiong et al. (2023) . OPTCOV runs in polynomial time polypd, H, c on pX on q, log 1{δq, and LinPEVI-ADV+ runs in Õpd 3 HN |A|q time when the action space is discrete. Algorithm 1 therefore remains computationally efficient in this case. Requirement of choosing d on . There is the caveat that we require the user to choose the tolerance for OPTCOV. In practice, one can achieve this by performing SVD on the offline dataset and looking at the plot of eigenvalues. One can also choose a tolerance of Opd{ mintN off , N on uq, but this would not achieve the reduction in the dependence on dimension from d 2 to c off pX off qd, d on d. Practical benefits of the online-to-offline approach. Algorithm 1 outputs a fixed policy satisfying 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-agnostic online exploration in Algorithm 1 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 collected data satisfies good coverage for any possible reward function even if it is revealed only after exploration, enabling one to use a single dataset to achieve success on many different tasks. This therefore also serves as an algorithm for the related setting of reward-agnostic hybrid RL, where the reward function is unknown during online exploration and only revealed to the agent after it.Algorithm 2 Hybrid Regression for Upper-Confidence Reinforcement Learning (HYRULE) 1: Input: Offline dataset D off , samples sizes N on , N off , feature maps ϕ h . Regularization parameter λ ą 0, confidence radii β, β, β, t last " 0. 2: Initialize: For h P rHs, estimate p w 1,h , q w 1,h , Q 1,h , q Q 1,h , σ 1,h , σ1,h from D off , and assignΣ 0,h " Σ 1,h " Σ off `λI " ř N off n"1 σ´2 n,h ϕ n,h ϕ J n,h `λI. 3: for episodes t " 1, ..., T do 4:Update optimistic and pessimistic weights p w t,h , q w t,h for all h.if there exists a stage h 1 P rHs such that det pΣ t,h 1 q ě 2 det pΣ tlast ,h 1 q then 6:Update optimistic and pessimistic Q-functions Q t,h ps, aq, q Q t,h ps, aq, set t last " t.end iffor horizon h " 1, ..., H do 9:Play action aptq h Ð arg max a Q t,h ps ptq h , aq, receive reward r ptq h , next state s ptq h`1 10: Estimate σ t,h , σt,h Ð maxtσ t,h , ? H, 2d 3 H 2 ||ϕps ptq h , a ptq h q|| 1{2 Σ ´1 t,h u 2 , update Σ t`1,h . 11:end for 12: end for 13: Output:Greedy policy p π " π Q T ,h , Unifpπ Q 1,h , ..., π Q T ,h q for PAC guarantee.Proof sketch. The relation ( 7) in Theorem 1 follows from invoking Theorem 2 from Xiong et al. (2023) with N ą Ωpd 2 H 6 q, λ " 1{H 2 , β 1 " Op ? dq. To establish (8), we first boundV 1 psq ´V p π 1 psq ď ? d ÿ H h"1 max ϕ h PΦon b ϕ J h Σ ˚´1 h ϕ h `?d ÿ H h"1 max ϕ h PΦ off b ϕ J h Σ ˚´1 h ϕ h . As Σ ˚´1 h ĺ H 2 Λ ´1 h (see Xiong et al. (2023)), it therefore boils down to controlling max ϕ h PΦ ϕ J h Λ ´1 h ϕ h .Towards this, first, we make the observation that Lemma 1 suggests that c on pX on q ď d on . If we run OPTCOV with tolerance Õpmaxtd on {N on , c off pX off q{N off uq on partitions where the above hold, in Lemma 5, we prove that max ϕ h PΦ ϕ J h Λ ´1 h ϕ h À max tc off pX off q{N off , d on {N on u . This yields the c off pX off qdH 4 , d on dH 4 result.To tighten the horizon dependence to H 3 , we employ an useful truncation argument. More specifically, from the total variance lemma (Lemma C.5 of Jin et al. (2018) ), the average variance V h V h`1 is asymptotically on the order of H. We therefore define the sets of trajectories E h pδ h q " tτ P D :" V h V h`1 ‰ ps τ h , a τ h q ě H 1`δ h u.The cardinality of each set can be bounded by |E h pδ h q| À N H 1´δ h , and so truncating at the level where N H 1´δ h « minp N off c off pX off q , Non don q leads to minϕ h PΦ ϕ J h Σ ‹ h ϕ h Á 1 N H 2 minp N off c off pX off q , Non don q 2 .Putting things together yields the last c off pX off q 2 dH 3 , d 2 on dH 3 result needed, and the theorem then follows.Thus far, we described an online-to-offline strategy which collects online samples to augment the offline dataset. However, in certain critical cases, such as with a doctor treating patients, performanceagnostic online exploration is untenable. One may wish to minimize the regret of the online actions taken while learning a 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-optimal online-only regret bounds in the offline-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 D off with the same formulas it would use as if it had experienced the N off 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 as Algorithm 4. Doing so 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. › › ›σ ´1 i,h ϕ `si h , a i h ˘› › › 2 ď › › ϕ `si h , a i h ˘› › 2 { ? H, only holds if this is ? H.Theorem 2 (Regret Bound for HYRULE, Algorithm 2). Given any δ P p0, 1q, for every partition X off , X on , if N on , N off " Ωpd 13 H 14 q, the regret of HYRULE is bounded w.p. at least 1 ´δ by RegpN on q À inf X off ,Xon a c off pX off q 2 dH 3 N 2 on {N off `ad on dH 3 N on .Corollary 2. By the regret-to-PAC conversion, Algorithm 2 achieves a sub-optimality gap w.p. 1´δ:V 1 psq ´V p π 1 psq À inf X off ,Xon a c off pX off q 2 dH 3 {N off `ad on dH 3 {N on .To understand this result, we first note that bounding the regret over all possible partitions yields an improvement over the ? d 2 H 3 N on regret bound originally obtained by He et al. (2023) , as we can simply take X on " X 1 on " X to recover this result. In the scenario where offline samples are abundant (where N off " N on ), it is possible to achieve significant improvements over online-only learning. Furthermore, in view of Lemma 1, there always exists a partition such that c off pX off q, d on ď d. This result therefore yields provable improvements over the minimax-optimal online regret bound in linear MDPs (Agarwal et al., 2022; He et al., 2023; Hu et al., 2023; Zhou et al., 2021) .Additionally, Theorem 2 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 a dependence of a c off pX off q dH 5 N 2 on {N off `?d on dH 5 N on . Notably, we achieve the same a reduction in the dimension dependence on the online partition from d 2 to d on d 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 ˚?d 2 H 6 N on and a pC ˚`c on pX qqd 3 H 6 N on 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 2 by combining the total variance lemma and a novel truncation argument that rules out "bad" trajectories in Lemma 17, which allows us to maintain a desirable H 3 dependence on both partitions. Computational efficiency. When the action space is finite and of cardinality |A|, the computational complexity of Algorithm 2 is of order r O `d4 H 3 N |A| ˘, as outlined in 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-dependent. Algorithm 2 is unaware of the partition. Unlike Algorithm 1, Algorithm 2 is fully unaware of the choice of partition, and there is therefore no need to estimate d on 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 is unaware of it. Practical benefits of the offline-to-online approach. While Algorithm 2 only satisfies a 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, e.g. in applications like mobile health (Nahum-Shani et al., 2017) . Technical challenges. Although Algorithm 2 is a straightforward generalization of LSVI-UCB++ in He et al. (2023) , with Σ 0 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 on the offline partition was challenging, as the argument of He et al. (2023) was not applicable. Instead, we used a truncation argument in Lemma 17 to bound the maximum eigenvalue of Σ ´1 off,h , maintaining a H 3 dependence on the offline partition. • 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 their argument would have left us with a d 2 H 3 dependence. To reduce the dimensional dependence to d on d, we prove a 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 a c off pX off q 2 d 6 H 8 N 2 on {N off `?d 2 H 3 regret bound by using the maximum magnitude 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 a proof sketch below.Proof sketch. We first adopt the regret decomposition as in He et al. (2023) We prove in Lemma 12 that the sum of bonuses on the offline partition can be bounded by ř h b dN on Non N off max ϕ h PΦ off ϕ J h Σ´1 off,h ϕ h . Further, ř h max ϕ h PΦ off b ϕ J h Σ´1 off,h ϕ h À c off pX off q 2 H• For asymmetric distributions, the authors should be careful not to show in tables or figures error bars would yield results that are out of range (e.g. negative error rates). Justification: We have read and reviewed the code of ethics. Our paper is a 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 consideration 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 a theoretical contribution to the field of reinforcement learning theory, and as such any societal impact will at the very least be second-order impacts not directly tied to our work. Having said that, we discuss that Algorithm 1 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 situations where performance-agnostic online exploration is untenable, such as in medicine.Guidelines:• The answer NA means that there is 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 societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific 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 algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.Some authors regard "partial" as a synonym of "single-policy" and "full" as a synonym of "all-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-policy concentrability coefficient is less than the full single-policy concentrability coefficient (with a larger online partition), and the former can be finite when the latter is infinite.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 LinPEVI-ADV+(Xiong et al., 2023). The code can be found at github.com/hetankevin/hybridlin. 
numerical experiments: 
 To demonstrate the benefits of hybrid RL in the offline-to-online and online-to-offline settings, we implement Algorithms 1 and 2 on a 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. 3Figure 1 depicts the coverage (defined by 1{λ min pΛq, 1{λ d off pΛ off q, 1{λ don pΛ on q) 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-only exploration. This demonstrates the potential of hybrid RL as a tool for taking advantage of poor quality offline data.Figure 2 shows the benefits of hybrid RL in the online-to-offline setting when the behavior policy is of poor quality. When applying LinPEVI-ADV 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, 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 a regret-minimizing 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 a nearly minimaxoptimal online learning algorithm can stand to benefit from offline data.  
discussion, limitations and future work: 
 In this paper, we develop two hybrid RL algorithms for linear MDPs with desirable statistical guarantees for the online-to-offline and offline-to-online settings. Both algorithms demonstrate provable gains over the minimax-optimal 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 RL (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 is beneficial in hybrid RL remains an open question. A result depending on a partial single-policy concentrability coefficient would be desirable, but may provide only limited benefits as we take the infimum over partitions. A good offline partition for the 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. Ð H @h P rHs, λ " 1{H 2 , β 2 " Õp ?dq. Set functions to optimizef i pΛq " η ´1 i log ´řϕPΦ exppη i }ϕ} 2AipΛq ´1 q ¯, A i pΛq " Λ`pT i K i q ´1pΛ 0,i `Λoff q for some Λ 0,i satisfying Λ 0,i ľ Λ 0 for all i, and η i " 2 2i{5 .Exploration Phase: Run an exploration algorithm (OPTCOV, Wagenmaker and Jamieson ( 2023)) to collect covariates Λ h such that max ϕ h PΦ ϕ J h pΛ h `λI `Λoff,h q ´1ϕ h ď τ. 3: for i " 1, 2, 3, ... do 4:Set the number of iterates T i Ð 2 i , episodes per iterate K i Ð 2 i .Play any policy for K i episodes to collect covariates Γ 0 and data D 0 .Initialize covariance matrix Λ 1 Ð Γ 0 {K.for t " 1, ..., T i do 8:if ř i j"1 T j K j ě N on then 9:break 10:end if 11:Run FORCE (Wagenmaker et al., 2022) or another regret-minimizing algorithm on the exploration-focused synthetic reward g ptq h ps, aq9trp´∇ Λ f i pΛq| Λ"Λtϕps,aqϕps,aq J q.12:Collect covariates Γ t , data D t .Perform Frank-Wolfe update:Γ t`1 Ð p1 ´1 t`1 qΛ t `1 t`1 Γ t {K i . 14: end for 15: Assign y Λ i,h Ð Λ Ti`1 , D i Ð Y Ti t"0 D t .Set Λ h " y Λ i,h , D on " D i . 17: if f i p x Λ i q ď K i T i τ thenr β h,2 " argmin βPR d ÿ τ PD 1 " xϕ ps τ h , a τ h q , βy ´`p V 1 h`1 ˘2 `sτ h`1 ˘ı2 `λ}β} 2 2 , r β h,1 " argmin βPR d ÿ τ PD 1 " xϕ ps τ h , a τ h q , βy ´p V 1 h`1 `sτ h`1 ˘ı2 `λ}β} 2 2 . p σ 2 h ps, aq :" max ! 1, " ϕps, aq J r β h,2 ‰ r0,H 2 s ´"ϕps, aq J r β h,1 ‰ 2 r0,Hs ´Õ ´dH 3 ? N κ ¯).22: for h " 1, ..., H do 23:Compute covariance matrix Σ h " ř τ PD ϕ ps τ h , a τ h q ϕ ps τ h , a τ h q J {p σ 2 h ps τ h , a τ h q `λI d .Compute weights pw h " Σ ´1 h ´řτPD ϕ ps τ h , a τ h q r τ h `p V h`1p s τ h`1 q p σ 2 h ps τ h ,a τ h q ¯.Compute pessimistic penalty Γ h p¨, ¨q Ð β 2 }ϕp¨, ¨q} Receive the initial state s ptq 1 .for horizon h " 1, ..., H do 6:p w k,h " Σ ´1 t,h ř t´1 i"1 σ´2 i,h ϕps piq h , a piq h qV t,h`1 ps piq h`1 q. 7: q w t,h " Σ ´1 t,h ř t´1 i"1 σ´2 i,h ϕps piq h , a piq h q q V t,h`1 ps piq h`1 q. 8:if there exists a stage h 1 P rHs such that det pΣ t,h 1 q ě 2 det pΣ tlast ,h 1 q then 9:Q t,h ps, aq " min ! r h ps, aq `p w J t,h ϕps, aq `βb ϕps, aq J Σ ´1 t,h ϕps, aq, Q t´1,h ps, aq, H) .10:q Q t,h ps, aq " max ! r h ps, aq `q w J t,h ϕps, aq ´β b ϕps, aq J Σ ´1 t,h ϕps, aq, q Q t´1,h ps, aq, 0) .11:Set the last updating episode t last " t.12:else 13:Q t,h ps, aq " Q t´1,h ps, aq, q Q t,h ps, aq " q Q t´1,h ps, aq.end if 15:V t,h psq " max a Q t,h ps, aq, q V t,h psq " max a q Q t,h ps, aq.end for 17:for horizon h " 1, ..., H do 18:Play action a end for 24: end for 25: Output: Greedy policy p π " π Q T ,h , Unifpπ Q 1,h , ..., π Q T ,h q for PAC guarantee. ptq h Ð arg max a Q t,h ps ptq h , aq. 19: Estimate σ t,h " c " V t,h V t,h`1 ‰ ´sptq h , a ptq h ¯`E t,h `Dt,h `H, setting E t,h and D t,h : E t,h " min ! r β › › ›Σ ´1{2 t,h ϕps ptq h , a ptq h q › › › 2 , H 2 ) `min ! 2H β › › ›Σ ´1{2 t,h ϕps ptq h , a ptq h q › › › 2 , H 2 ) , D t,h " min # 4d 3 H 2 ˜p w J t,The proof of Theorem 1 follows from a series of distinct results, presented as three lemmas below.The first lemma demonstrates that RAPPEL achieves no higher error than LinPEVI-ADV+ itself, the second produces a d on dH 4 error bound, while the third produces a d 2 on dH 3 error bound via a slightly different truncation argument. We will prove Equation 7 in Lemma 2, which act as a general statistical guarantee for RAPPEL. We show the validity of the instance-dependent bound developed from Equation 7in Lemmas 3 and 4. We observe that Theorem 1 follows immediately after. Lemma 2 (General Statistical Guarantee for RAPPEL, Algorithm 1). For every δ P p0, 1q and any partition X off , X on , with probability at least 1 ´δ, RAPPEL achievesV 1 psq ´V p π 1 psq À ? d H ÿ h"1 E π ˚||ϕps h , a h q|| pΣ off,h `Σo n,h q ´1 ď ? d H ÿ h"1 E π ˚||ϕps h , a h q|| Σ ˚´1 off,h.Proof. Before we proof the desired result, we first recall thatEQUATIONEQUATIONThen, by invoking Theorem 2 from Xiong et al. (2023) with N ą Ωpd 2 H 6 q, λ " 1{H 2 , β 1 " Op ? dq, we see thatV 1 psq ´V p π 1 psq À ? d H ÿ h"1 E π ˚"}ϕps h , a h q} Σ ˚´1 h | s 1 " s ı " ? d H ÿ h"1 E π ˚"}ϕps h , a h q} pΣ off,h `Σo n,h q ´1 | s 1 " s ı , as Σ h " Σ off,h `Σo n,h . Noting that Σ on,h is positive semi-definite, it then follows Σ off,h ĺ Σ off,h `Σo n,h . Therefore, ? d H ÿ h"1 E π ˚||ϕps h , a h q|| pΣ off,h `Σo n,h q ´1 ď ? d H ÿ h"1 E π ˚||ϕps h , a h q|| Σ ˚´1 off,h, and the inequality holds.Lemma 3 (First Error Bound for RAPPEL, Algorithm 1). For every δ P p0, 1q and any partition X off , X on , with probability at least 1 ´δ, RAPPEL achievesEQUATIONN ě max ␣ α 4 on d ´4 on , α 4 off c off pX off q ´4(maxtN ˚, polypd, H, c off pX off q, log 1{δqu, where we define the quantities α off " N off N , α on " Non N , and the minimal samples for coverage isN ˚" min N C¨N s.t. inf ΛPΩ max ϕPΦ ϕ J `N pΛ `λIq `Λoff ˘´1 ϕ ď Õpmaxtd on {N on , c off pX off q{N off uq.Proof. Let X off , X on be an arbitrary partition of S ˆA ˆrHs. Let us 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 2 from Xiong et al. (2023) on this dataset. As we choose N ą Ωpd 2 H 6 q, λ " 1{H 2 and β 1 " Op ? dq, we obtain the suboptimality gap decomposition below:V 1 psq ´V p π 1 psq À ? d H ÿ h"1 E π ˚"}ϕps h , a h q} Σ ˚´1 h | s 1 " s ı .This decomposition can be further decomposed into the sum of bonuses on the offline and online partitions X off and X on , respectively:? d H ÿ h"1 E π ˚"}ϕps h , a h q} Σ ˚´1 h | s 1 " s ı " ? d H ÿ h"1 ´Eπ ˚"}ϕps h , a h q} Σ ˚´1 h 1 Xon | s 1 " s ı `Eπ ˚"}ϕps h , a h q} Σ ˚´1 h 1 X off | s 1 " s ı" ? d H ÿ h"1 E π ˚"b ϕps h , a h q J Σ ˚´1 h ϕps h , a h q1 Xon | s 1 " s ȷ `?d H ÿ h"1 E π ˚"b ϕps h , a h q J Σ ˚´1 h ϕps h , a h q1 X off | s 1 " s ȷ .We can further upper bound the above expectations under the optimal policy π ˚by taking the maximum of the quadratic form over each partition, yielding? d H ÿ h"1 E π ˚"}ϕps h , a h q} Σ ˚´1 h | s 1 " s ı " ? d H ÿ h"1 max ϕ h PΦon b ϕ J h Σ ˚´1 h ϕ h 1 Xon `?d H ÿ h"1 max ϕ h PΦ off b ϕ J h Σ ˚´1 h ϕ h 1 X off ď ? d H ÿ h"1 max ϕ h PΦon b ϕ J h Σ ˚´1 h ϕ h `?d H ÿ h"1 max ϕ h PΦ off b ϕ J h Σ ˚´1 h ϕ h . From Xiong et al. (2023), as " V h V h`1 ‰ p¨, ¨q P " 1, H 2 ‰, the weighted covariance matrix is uniformly upper bounded by the unweighted covariance matrix in the following manner:Σ ˚´1 h ĺ H 2 Λ ´1 h , which leads to our conclusion that V 1 psq ´V p π 1 psq À ? d H ÿ h"1 max ϕ h PΦon b H 2 ϕ J h Λ ´1 h ϕ h `?d H ÿ h"1 max ϕ h PΦ off b H 2 ϕ J h Λ ´1 h ϕ h .We now further bound the above two quadratic forms over the online and offline partitions respectively. By Lemma 1, the partial online coverage coefficient is bounded by the dimensionality of the online partition:c on pX on q " inf π max ϕ h PΦon ϕ J h E φh "d π h r φh φJ h s ´1ϕ h ď d on .As we have N on online episodes, the optimal covariates for online exploration would then yieldinf Λ max ϕ h PΦon ϕ J h Λ ´1ϕ h À c on pX on q{N on ď d on {N on .Conversely, we also have access to N off episodes of offline data with the following guarantee that follows from an application of Matrix Chernoff:max ϕ h PΦ off ϕ J h Λ ´1 off ϕ h À c off pX off q{N off .Therefore, by Lemma 5, we can conclude that on its success event, running OPTCOV with tolerance Õpmaxtd on {N on , c off pX off q{N off uq, provides us covariates such that * maxtN ˚, polypd, H, c off pX off q, log 1{δqu episodes, where α off " N off N off `Non and α on " Non N off `Non . Note that the more even the proportion of offline to online samples, the smaller α off , α on are. In fact, as α 4 off , α 4 on P r0.0625, 1s, this term contributes no more than a constant factor that is no greater than 1 to the final sample complexity.max ϕ h PΦ ϕ J h Λ ´1 h ϕ h À maxWe then have that ) maxtN ˚, polypd, H, c off pX off q, log 1{δqu.V 1 psq ´V p π 1 psq À infLemma 4 (Second Error Bound for RAPPEL, Algorithm 1). For every δ P p0, 1q and any partition X off , X on , with probability at least 1 ´δ, RAPPEL achievesV 1 psq ´V p π 1 psq À d c off pX off q 2 dH 3 N off α off `d d 2 on dH 3 N on α on , where N ě max ␣ α 4 on d ´4 on , α 4 off c off pX off q ´4(maxtN ˚, polypd, H, c off pX off q, log 1{δqu, we define the quantities α off " N off N , α on " Non N , and the minimal samples for coverage isN ˚" min N C¨N s.t. inf ΛPΩ max ϕPΦ ϕ J `N pΛ `λIq `Λoff ˘´1 ϕ ď Õpmaxtd on {N on , c off pX off q{N off uq.Proof. First, we set up some preliminaries. Following the same argument as the proof of Lemma 3, we can establish that, for arbitrary partition X " X on Y X off , we have c on pX on q ď d on , and running OPTCOV with tolerance Õpmaxtd on {N on , c off pX off q{N off uq, yields: * maxtN ˚, polypd, H, c off pX off q, log 1{δqu episodes.max ϕ h PΦ ϕ J h Λ ´1 h ϕ h À max tc off pX off q{N off , d on {N on u .To tighten the horizon dependence even further from the result of Lemma 3, we turn to the total variance lemma. i.e. Lemma C.5 in Jin et al. (2018) , indicating that1 N H ÿ τ PD H ÿ h"1 " V h V h`1 ‰ ps τ h , a τ h q À Õ ˆH `H2 N ˙.Then, we directly apply Lemma 17 with γ " max td on {N on , c off pX off q{N off u and σ " H `H2 {N , we will then obtain thatEQUATIONwhich leads to our final result:V 1 psq ´V p π 1 psq À inf X off ,Xon ˜d c off pX off q 2 dH 3 N off α off `d d 2 on dH 3 N on α on ¸,where α off " N off {N and α on " N on {N .Proof. In tabular case, we set ϕps, aq " 1 s,a and d " |S| ¨|A|. Let N h ps, aq be the number of visits to a specific state-action pair ps, a, hq. As the exploration algorithm OPTCOV ensures that max s,a,h1 N h ps, aq ď max ˆdon N on , c off pX off q N off ˙,we bound the error in the following way follows from Lemma 2,V 1 psq ´V p π 1 psq À ? d H ÿ h"1 E π ˚||ϕps h , a h q|| pΣ off,h `Σo n,h q ´1 ď a |S||A| H ÿ h"1 ÿ s,a d ‹ h ps, aq d " V h V h`1 ‰ ps, aq N h ps, aq ,where the last inequality follows from the fact that Σ ‹ h " diag `Nh ps, aq{" V h V h`1‰ ps, aq ˘sPS,aPA . We will then decompose the state-action space into X off and X on , and bound the two parts seperately based on the tolerance level of OPTCOV,V 1 psq ´V p π 1 psq À a |S||A| H ÿ h"1 ÿ s,a d ‹ h ps, aq d " V h V h`1 ‰ ps, aq N h ps, aq 1 X off `a|S||A| H ÿ h"1 ÿ s,a d ‹ h ps, aq d " V h V h`1 ‰ ps, aq N h ps, aq 1 Xon ď d |S||A|c off pX off q N off H ÿ h"1 ÿ s,a d ‹ h ps, aq b " V h V h`1 ‰ ps, aq1 X off `d |S||A|d on N on H ÿ h"1 ÿ s,a d ‹ h ps, aq b " V h V h`1 ‰ ps, aq1 Xon ď a |S||A| ˜d c off pX off q N off `c d on N on ¸H ÿ h"1 ÿ s,a b d ‹ h ps, aq " V h V h`1 ‰ ps, aq.As the optimal policy π ‹ executes a deterministic action π ‹ psq for any state s, the inequality can be further bounded asEQUATION)where the last inequality follows from the proof of Lemma C.5. in Jin et al. (2018) .Lemma 1. For any partition X off , X on , we have that c on pX on q ď d on . Similarly, there exists a partition such that c off pX off q " Opdq.Proof. This proof follows a similar strategy to that of Lemma B.10 in Wagenmaker and Jamieson (2023) , except that we exploit the projections onto d on to get a bound that depends on d on ď d, instead of d. We wish to bound c on pX on q " inf π max h 1 λ don pE d π h rpP on ϕ h qpP on ϕ h q J sq .P on P R dˆd has rank d on ď d, so we can decompose this with the thin SVD into P on " U on U J on , where U on P R dˆdon . It then holds that λ don pE d π h rpP on ϕ h qpP on ϕ h q J sq " λ min pE d π h rpU J on ϕ h qpU J on ϕ h q J sq, and from Lemma 20 thatc on pX on q " inf π sup v h PΦon v J h U on E d π h rpU J on ϕ h qpU J on ϕ h q J s ´1U J on v h .Apply Jensen's inequality to find that for any v h P Φ on ,v J h U on E d π h rpU J on ϕ h qpU J on ϕ h q J sU J on v h ě v J h U on E ϕ h "d π h rU J on ϕ h sE ϕ h "d π h rU J on ϕ h s J U J on v h .Then, we can boundc on pX on q " inf π sup v h PΦon v J h U on E d π h rpU J on ϕ h qpU J on ϕ h q J s ´1U J on v h ď inf ρ sup v h PΦon v J h U on `Eπ"ρ " E ϕ h "d π h rU J on ϕ h sE ϕ h "d π h rU J on ϕ J h s ‰˘´1 U J on v h .By Kiefer-Wolfowitz (Lattimore et al., 2020) , this is bounded by d on .Similarly,inf X off ,Xon c off pX off q " inf X off ,Xon max h 1 λ d off pE µ h rpP off ϕ h qpP off ϕ h q J sq " inf X off ,Xon max h 1 λ min pE µ h rpU J off ϕ h qpU J off ϕ h q J sq ď Opdq.where the upper bound is achieved when, for instance, we choose X off such that Φ off " Span `pv h,1 , ..., v h,k h q hPrHs ˘, where v h,i is the i-th largest eigenvector ofE µ rϕ h ϕ J h s « 1 N off ř τ PD off ϕ h ps τ h , a τ h qϕ h ps τ h , a τ h q J ,and v h,k h is the eigenvector corresponding to the largest eigenvalue λ h,k h ě Ωp1{k h q. The largest eigenvalue λ h,1 is always Ωp1{dq for non-null features, so there always exists such a partition where d off is at least 1.Informally, one can choose the offline partition to be the span of the large eigenvectors of the covariance 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 X off , X on , if we run OPTCOV with tolerance Õpmaxtd on {N on , c off pX off q{N off uq, on this partition we also have thatmax ϕ h PΦ ϕ J h Λ ´1 h ϕ h À max tc off pX off q{N off , d on {N on u .Proof. By Lemma 1, for any partition, we have thatc on pX on q " inf π max ϕ h PΦon ϕ J h E φh "d π h r φh φJ h s ´1ϕ h ď d on ,Applying Matrix Chernoff, we have that with probability at least 1 ´δ,max ϕ h PΦ off ϕ J h Λ ´1 h,off ϕ h ď max ϕ h PΦ off ϕ J h E φh "µ h r φh φJ h `N ´1 off Is ´1ϕ h N ´1 off ˜1 ´d 2 N off log ˆ4d δ ˙¸´1 ,and similarly for c on pX on q we also have thatinf π max ϕ h PΦon ϕ J h Λ ´1 h,π ϕ h ď inf π max ϕ h PΦon ϕ J h E φh "µ h r φh φJ h s ´1ϕ h N ´1 on ˜1 ´d 2 N on log ˆ4d δ ˙¸´1 .As Λ h,off `Λh,on " Λ h , we havemax ϕ h PΦ ϕ J h Λ ´1 h ϕ h " max " max ϕ h PΦ off ϕ J h Λ ´1 h ϕ h , max ϕ h PΦon ϕ J h Λ ´1 h ϕ h * À max " c off pX off q{N off , max ϕ h PΦon ϕ J h Λ ´1 h ϕ h * ,where the last step follows from the choice of partition. So it suffices to run OPTCOV with tolerance Õpmaxtd on {N on , c off pX off q{N off uq, to find that there exists at least one partition such that maxϕ h PΦ ϕ J h Λ ´1 h ϕ h À max tc off pX off q{N off , d on {N on u .Lemma 6 (Coverability Coefficient Is Bounded In Tabular MDPs). If the underlying MDP is tabular, for any partition X off , X on , we have that c on pX on q ď d on .Proof. First, we write the concentrability coefficient in terms of densities.c on pX on q " min π max h 1 λ don pE d π h rpP on ϕ h qpP on ϕ h q J sq ď min 1 Xon d π h ps, aq1 Xon ď 1 Xon sup π 2 d π 2 h ps, aq1 Xon { ř s 1 ,a 1 sup π 1 d π 1 h ps 1 , a 1 q 1 Xon ď ř s,a sup π d π h ps, aq 1 Xon sup π d π h ps, aq 1 Xon ď d on .E Proofs for Algorithm 2We consider the same state-action space splitting framework of Tan and Xu (2024) . Let X on YX off " rHs ˆS ˆA. Then, their images under the feature map Φ off " SpanpϕpX off,h qq hPrHs Ď R d and Φ on " SpanpϕpX on,h qq hPrHs Ď R d are subspaces of X with dimension d off and d on , respectively. We denote P off , P on as the orthogonal projection operators onto these subspaces respectively. The partial offline all-policy concentrability coefficientc off pX off q " max h 1 λ d off pE µ h rpP off ϕ h qpP off ϕ h q J sq ,is bounded by the inverse of the d off -th largest eigenvalue of the covariance matrix of the projected feature maps onto the offline partition, where λ k is the k-th largest eigenvalue. Write 1 Xon as shorthand for 1pps, a, hq P X on q, and similarly for 1 X off . Now, we work through the analysis of He et al. (2023) We define several "high probability" events which are similar to those defined in He et al. (2023) .• We define r w t,h as the solution of the weighted ridge regression problem for the squared value functionEQUATION)• We define E as the event where the following inequalities hold for all s, a, t, h P S ˆA rT s ˆrHs: 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 r E h as the event that for all episodes t P rT s, stages h ď h 1 ď H and state-action pairs ps, aq P S ˆA, the weight vector p w t,h satisfies ˇˇp w J t,h 1 ϕps, aq ´rP h V t,h 1 `1s ps, aq ˇˇď β b ϕps, aq J Σ ´1 t,h 1 ϕps, aq,ˇˇp w J t,whereβ " O ˆH? dλ `bd log 2 p1 `dN H{pδλqq ˙.Furthermore, let r E " r E 1 denotes the event that ( 19) holds for all stages h P rHs. This is the fine event where concentration for ŵ is tighter than that required in ( 16) to ( 18).Equipped with these definitions, we recall the following lemmas from He et al. ( 2023): Lemma 7 (Lemma B.1, He et al. (2023) ). E holds with probability at least 1 ´7δ.Lemma 8 (Lemma B.2, He et al. (2023) ). On the event E and r E h`1 , for each episode t P rT s and stage h, the estimated variance satisfies He et al. (2023) ). On the event E and r E h`1 , for any episode t and i ą t, we haveˇˇ"VhVt,h`1 ‰ ´sptq h , a ptq h ¯´rV h V t,h`1 s ´sptq h , a ptq h ¯ˇˇď E t,h , ˇˇ"VhVt,h`1 ‰ ´sptq h , a ptq h ¯´" V h V h`1 ‰ ´sptq h , a ptq h ¯ˇˇď E t,h `Dt,h . Lemma 9 (Lemma B.3," V h `Vi,h`1 ´V h`1 ˘‰ ´sptq h , a ptq h ¯ď D t,h { `d3 H ˘.Lemma 10 (Lemma B.4, He et al. (2023) ). On the event E and r E h , for all episodes t P rT s and stages h ď h 1 ď H, we have Q t,h ps, aq ě Q hps, aq ě q Q t,h ps, aq. In addition, we have V t,h psq ě V h psq ě q V t,h psq.Lemma 11 (Lemma B.5, He et al. ( 2023)). On event E, event r E holds with probability at least 1 δ.From He et al. ( 2023), based on Lemma B.4 of their paper, Q t,h ps ptq h , a ptq h q " V t,h ps ptq h q ě V h ps ptq h q, i.e. optimism holds for all episodes and timesteps. Therefore,RegpT q À T ÿ t"1 H ÿ h"1 !" P h ´Vt,h`1 ´V π ptq t,h`1 ¯ı ´sptq h , a ptq h ¯´´V t,h`1 ´sptq h`1 ¯´V π ptq t,h`1 ´sptq h`1 ¯¯) `β T ÿ t"1 H ÿ h"1 }Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q} 2 .Accordingly, given a partition X off , X on of rHs ˆS ˆA, we can further decompose this into the fraction of episodes where each partition is visited,T ÿ t"1 H ÿ h"1 }Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q} 2 " ÿ h,t }Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q1 X off } 2 `ÿ h,t }Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q1 Xon } 2 .He et al. ( 2023) define the eventsE 1 " # @h P rHs, T ÿ t"1 H ÿ h 1 "h " P h ´Vt,h`1 ´V π ptq t,h`1 ¯ı ´sptq h , a ptq h T ÿ t"1 H ÿ h 1 "h ´Vt,h`1 ´sptq h`1 ¯´V π ptq t,h`1 ´sptq h`1 ¯¯ď 2 a 2H 3 T logpH{δq + , E 2 " # @h P rHs, T ÿ t"1 H ÿ h 1 "h " P h ´Vt,h`1 ´q V t,h`1 ¯ı ´sptq h , a ptq h T ÿ t"1 H ÿ h 1 "h ´Vt,h`1 ´sptq h`1 ¯´q V t,h`1 ´sptq h`1 ¯¯ď 2 a 2H 3 T logpH{δq + ,which they show that by Azuma-Hoeffding, both hold with probability 1 ´δ each. As such, we have thatRegpT q À a H 3 T logpH{δq`ÿ h,t β › › Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q1 X off › › 2 `ÿ h,t β › › Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q1 Xon › › 2 .Here, we denoteReg off pT q " ÿ h,t β › › Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q1 X off › › 2 , Reg on pT q " ÿ h,t β › › Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q1 Xon › › 2 ,as the offline regret and online regret, respectively.Now, we bound the regret on the offline partition. We first perform a similar argument to that in Tan and Xu (2024); Xie et al. (2022a) to show that the sum of bonuses can 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 X off , X on , we can bound the sum of bonuses on the offline partition with the following:Reg off pT q À H ÿ h"1 d dN 2 on N off max ϕ h PΦ off ϕ J h Σ´1 off,h ϕ h ,where Σoff,h " pΣ off,h `λIq{N off and T " N on .Proof. It is sufficient to show the following holds trueÿ t β › › Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q1 X off › › 2 ď d dN 2 on N off max ϕ h PΦ off ϕ J h Σ´1 off,h ϕ h ,then the desired inequality directly follows. With a direct calculation, one may observe that}Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q1 X off } 2 " b ϕ J h ps ptq h , a ptq h qΣ ´1 t,h ϕ h ps ptq h , a ptq h q1 X off À b ϕ J h ps ptq h , a ptq h qpΣ off,h `λIq ´1ϕ h ps ptq h , a ptq h q1 X off ,where the last inequality holds as Σ off,h ĺ Σ t,h . As a result, we are able to bound the desired inequality with the maximum eigenvalue of the inverse weighted matrix,ÿ t }Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q1 X off } 2 ď N on c max ϕ h PΦ off ϕ J h pΣ off,h `λIq ´1ϕ h " d N on N on N off max ϕ h PΦ off ϕ J h Σ´1 off,h ϕ h ,where Σoff,h " pΣ off,h `λIq{N off . As β " Õp ? dq, we obtain the bound we desired:ÿ t β}Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q1 X off } 2 ď d dN on N on N off max ϕ h PΦ off ϕ J h Σ´1 off,h ϕ h .Lemma 13 (Partial Concentrability Bound). For any partition X off , X on , we have thatH ÿ h"1 max ϕ h PΦ off b ϕ J h Σ´1 off,h ϕ h À a c off pX off q 2 H 3 ,when N on , N off ě Ωpd 13 H 14 q, where we define Σoff,h " pΣ off,h `λIq{N off .Proof. Similar to the definition of Σoff,h , we define Λoff,h " pΛ off,h `λIq{N off in a similar way. Then, one may observe thatmax ϕ h PΦ off ´ϕJ h Λ´1 off,h ϕ h ¯" max ϕ h PΦ off ¨ϕJ h ˜1 N off ˜Noff ÿ n"1 ϕ n,h ϕ J n,h `λI ¸¸´1 ϕ h ‚ ď max ϕ h PΦ off ϕ J h E µ h r Λoff,h s ´1ϕ h ˜1 ´d 2 N off log ˆ4d δ ˙¸´1 ,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 ϕ h PΦ off ´ϕJ h Λ´1 off,h ϕ h ¯À inf X off ,Xon max h 1 λ d off pE µ pP off ϕ h qpP off ϕ h q J q " inf X off ,Xon max h 1 λ min `Eµ pU J off ϕ h qpU J off ϕ h q J " c off pX off q.To tighten the dependence of the regret of the offline partition on H, we again employ a truncation argument that used in Lemma 4. Recall that in Section B of the appendix in He et al. (2023) , by the total variance lemma of Jin et al. (2019) , it holds thatT ÿ t"1 H ÿ h"1 σ 2 t,h ď r O `H2 T `d10.5 H 16 ˘.Again, recall that we haveÿ h,t }Σ ´1{2 t,h ϕ h ps ptq h , a ptq h q1 X off } 2 À g f f f eH 2 N on N on N off max ϕ h PΦ off ¨ϕJ h ˜1 N off ˜Noff ÿ n"1 σ´2 n,h ϕ n,h ϕ J n,h `λI ¸¸´1 ϕ h ‚. As σ2 n,h " max ! σ 2 n,h , H, 4d 6 H 4 ||ϕ n,h || Σ ´1 n,h) . Consider the setsI 1 " ␣ n P rN off s : @h : σ2 n,h " maxpσ 2 n,h , Hq ( , I 2 " I c 1 .Here, I 2 roughly correspond to the "bad" set of trajectories where there exists some timestep h such that σ2 n,h ą maxtσ 2 n,h , Hu, and I 1 to be the "good" set of trajectories where the monotonic variance estimator is controlled.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 P I 2 we have that max hPrHs bϕ J n,h Σ ´1 n,h ϕ n,h ě 1{p4d 6 H 2 q, which indicates that H ÿ h"1 min ␣ 1, 16d 12 H 4 ϕ J n,h Σ ´1 n,h ϕ n,h ( ě 1,and so we can conclude that|I 2 | ď H ÿ h"1 N off ÿ n"1 min ␣ 1, 16d 12 H 4 ϕ J n,h Σ ´1 n,h ϕ n,h ( À d 13 H 5 logp1 `N {dq,by Lemma D.5 of Zhou and Gu ( 2022) and the fact that ||ϕ n,h {σ n,h || 2 ď 1{H 2 . As we require in Theorem 2 that N on , N off " Ωpd 13 H 14 q, we come to the following result|I 2 |{N off À 8d 13 H 5 logp1 `N {dq{N off " õp1q, |I 1 |{N off " 1 ´õp1q.Informally, this means that the proportion of trajectories in the "bad set" I 2 is asymptotically zero, and the proportion in the "good set" I 1 is asymptotically one. As for every n P I 1 we have that for any h P rHs,max ϕ h PΦ off ´ϕJ h Σ´1 off,h ϕ h " max ϕ h PΦ off ¨ϕJ h ˜1 N off ˜Noff ÿ n"1 σ´2 n,h ϕ n,h ϕ J n,h `λI ¸¸´1 ϕ h ‚ " max ϕ h PΦ off N off ¨ϕJ h ˜Noff ÿ n"1 σ´2 n,h ϕ n,h ϕ J n,h `λI ¸´1 ϕ h ‚ ď max ϕ h PΦ off N off ¨ϕJ h ˜ÿ nPI1 ϕ n,h ϕ J n,h σ 2 n,h `H `λI ¸´1 ϕ h ‚.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 of Jin et al. (2019) , if N off ě Ωpd 10.5 H 14 q, it holds that1 N off N off ÿ n"1 H ÿ h"1 σ 2 n,h " r O `H2 `d10.5 H 16 {N off ˘" r O `H2 ˘.With a direct application of Lemma 17, as we set T " ÕpHq and γ " c off pX off q{N off , we will then get toH ÿ h"1 max ϕ h PΦ off b ϕ J h Σ ´1 off,h ϕ h À c off pX off qH N off a N off H " d c off pX off qH 3 N off , which indicates that H ÿ h"1 max ϕ h PΦ off b ϕ J h Σ´1 off,h ϕ h À a c off pX off q 2 H 3 .Now, from Lemmas 12 and 13, for any partition X off , X on , the offline regret satisfiesReg off pT q À H ÿ h"1 d dN on N on N off max ϕ h PΦ off ϕ J h Σ´1 off,h ϕ h À c c off pX off q 2 dH 3 N on N on N off .We will then bound the online term, Reg on pT q. He et al. (2023) show in Lemma E.1 that it is possible to use Cauchy-Schwarz to bound this by Reg on pT q " r O ¨d4 H 8 `βd 7 H 5 `βgf f e dHT `dH T ÿ t"1 H ÿ h"1 σ 2 t,h ‚,and in Section B of the appendix, state that by the total variance lemma of Jin et al. (2019) ,T ÿ t"1 H ÿ h"1 σ 2 t,h ď r O `H2 T `d10.5 H 16We will seek to use the online partition to tighten the dimensional dependence in the first result accordingly. Lemma 14 (Modified Lemma E.1 in He et al. (2023) ). For any parameters β 1 ě 1 and C ě 1, and any partition X off , X on , the summation of bonuses on the online partition is upper bounded byT ÿ t"1 min ˜β1 c ϕ ´sptq h , a ptq h ¯J Σ ´1 t,h ϕ ´sptq h , a ptq h ¯1Xon , C ḑ 4d 4 H 6 Cι `10β 1 d 5 on H 4 ι `2β 1 g f f e 2d on ι T ÿ t"1 ´σ2 t,h`Hw here ι " logp1 `N {pdλqq.Proof. For each horizon h P rHs, we 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 ϕ T Σ ´1ϕ gets large. pϕ n,h 1 Xon qpϕ n,h 1 Xon q J `λI d ¸´1 ϕ ´sptq h , a ptq h ¯1Xon , 1 ‹ ‚ ď 10β 1 d 5 on H 4 ι `2β 1 g f f e 2d on ι K ÿ k"1 ´σ2 k,h `H¯,where ι " logp1 `N {pdλqq.From this, it suffices to follow the rest of the proof of Lemma E.1 from He et al. (2023) to bound the remaining term byT ÿ t"1 1 #c ϕ ´sptq h , a ptq h ¯J Σ ´1 t,h ϕ ´sptq h , a ptq h ¯1Xon ě 1 + ď 4d 4 H 6 Cι.As a result, we obtain the following bound for the online regret Reg on pT q À d 7 H 9 `βa d on dH 3 T .Combining our results in E.4 and E.5, we come to the bound of total regret that RegpN on q À a H 3 N on logpH{δq `cc off pX off q 2 dH 3 N on N on N off `ad on dH 3 N on `d7 H 9 .When we set N on , N off " Ωpd 13 H 14 q and choose X off , X on be the partition that minimize the right hand side, we have RegpN on q À inf X off ,Xonˆcc off pX off q 2 dH 3 N on N on N off `ad on dH 3 N on ˙,proving Theorem 2.F OPTCOV from Wagenmaker and Jamieson (2023) We lean on 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 subroutine used, for completeness.Algorithm 5 Collection of Optimal Covariates (OPTCOV), Wagenmaker and Pacchiano (2023) 1: Input: functions to optimize pf i q i , constraint tolerance ϵ, confidence δ.2: for i " 1, 2, 3, ... do 3:Set the number of iterates T i Ð 2 i , episodes per iterate K i Ð 2 i .Play any policy for K i episodes to collect covariates Γ 0 and data D 0 .Initialize covariance matrix Λ 1 Ð Γ 0 {K.for t " 1, ..., T i do 7:Run FORCE (Wagenmaker et al., 2022) or another regret-minimizing algorithm on the exploration-focused synthetic reward g ptq h ps, aq9trp´∇ Λ f i pΛq| Λ"Λtϕps,aqϕps,aq J q.Collect covariates Γ t , data D t . 9:Perform Frank-Wolfe update:Γ t`1 Ð p1 ´1 t`1 qΛ t `1 t`1 Γ t {K i . 10: end for 11: Assign x Λ i Ð Λ Ti`1 , D i Ð Y Ti t"0 D t .12:if f i p x Λ i q ď K i T i ϵ then 13: Return: p Λ, K i T i , D i . 14:end if 15: end forThe algorithm essentially performs the doubling trick to determine how many samples to collect, terminating when the minimum eigenvalue of the covariance matrix is above the set tolerance. Wagenmaker and Pacchiano (2023) then prove the following guarantee for OPTCOV in the hybrid setting:Lemma 15 (Termination of OPTCOV, Lemma C.2 (Wagenmaker and Pacchiano, 2023) ). Letf i pΛq " 1 η i log ˜ÿ ϕPΦ e ηi}ϕ} 2 A i pΛq ´1 ¸, A i pΛq " Λ `1 T i K i Λ 0,i `1 T i K i Λ offfor some Λ 0,i satisfying Λ 0,i ľ Λ 0 for all i, and η i " 2 2i{5 . Let pβ i , M i q denote the smoothness and magnitude constants for f i . Let pβ, M q be some values such that β i ď η i β, M i ď M for all i.Then, if we run OPTCOV on pf i q i with constraint tolerance ϵ and confidence δ, we have that with probability at least 1 ´δ, it will run for at most max" min N 16N s.t. inf ΛPΩ max ϕPΦ ϕ J pN Λ `Λ0 `Λoff q ´1 ϕ ď ϵ 6 , polypβ, d, H, M, log 1{δq ϵ 4{5 * .episodes, and will return datatϕ τ u N τ "1 with covariance p Σ N " ř N τ "1 ϕ τ ϕ J τ such that f î ´N ´1 p Σ N ¯ď N ϵwhere p i 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 on OPTCOV, Theorem 4, Wagenmaker and Pacchiano ( 2023)). Consider running OPTCOV with some ϵ exp ą 0 and functions f i as defined in Lemma 15, instantiated with the regularization λ ě 0. 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 f i pΛq byL i " 1 λ2 , β i " 2 λ3 ´1 `ηi λ ¯, M i " 1 λ2 .Assume that the termination condition of OPTCOV is met for p i satisfying p i ď log ˆpoly ˆ1 ϵ exp , d, H, log 1{δ, c on pX on q, λ˙˙.We assume this holds and justify it at the conclusion of the proof. For notational convenience, define ι :" poly ˆlog 1 ϵ exp , d, H, log 1{δ, c on pX on q, λ˙.Given this upper bound on p i, setL " M :" 1 λ2 , β :" ι.With this choice of L, M, β, we have L i ď L, M i ď M, β i ď η i β for all i ď p i. u N τ "1 with covariance p Σ " ř N τ "1 ϕ τ ϕ J τ such that f î ´N ´1 p Σ ¯ď N ϵ expwhere p i is the iteration on which OPTCOV terminates.By Lemma D.1 of Wagenmaker and Jamieson (2023) we haveN ¨max ϕ h PΦ ϕ h ´p Σ `Λî ,0 `Λoff ¯´1 ϕ h ď f î ´N ´1 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 p i. We do so with the same argument that Wagenmaker and Pacchiano (2023) use. Note that by the definition of OPTCOV, if we run for a total of N episodes, we can bound p i ď 1 4 log 2 p N q. However, we see that the bound on p i given above upper bounds 1 4 log 2 p N q for N the upper bound on the number of samples collected by OPTCOV stated above. Thus, the bound on î is valid.Lemma 17. Let Φ Ă R d be a linear subspace. Suppose tϕ h,n u hPrHs,nPrN s P Φ be a collection of unit vectors and tσ h,n u hPrHs,nPrN s P R `be a collection of positive real numbers with mean σ " pN Hq ´1 ř h,n σ h,n . Suppose it holds that max hPrHs max ϕ h PΦ pϕ T h Λ ´1 h ϕ h q ď γ, then the following result satisfiesH ÿ h"1 max ϕ h PΦ b ϕ T h Σ ´1 h ϕ h À γH ? N σ, with Λ h " N ÿ n"1 ϕ h,n ϕ T h,n `λI d , Σ h " N ÿ n"1 ϕ h,n ϕ T h,n σ h,n `λI d .Proof. First, we denote σh " N ´1 ř n σ h,n . Informally, this implies that most individuals of σ h,ï s asymptotically on the order of σh , 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:E h pC h q " tn P rN s : σ h,n ě C h σh u.Here, we leave the choice of the truncation level C h open for now, but note that we allow the truncation levels C h vary across different timesteps h and related to σh . It follows by definition that ř H h"1 σh " H σ. From an application of Markov's Inequality, the cardinality of set E h pC h q can be upper bounded as|E h pC h q| ď N C h .We now choose the truncation level C h . To do so, we follow the steps below to quantify the effect induced by the trajectories with high variance (i.e. those that belong to E h pC h q):min ϕ h PΦ ϕ J h Σ ‹ h ϕ h ě min ϕ h PΦ ϕ J h ˜N ÿ n"1 ϕ h,n ϕ T h,n σ h,n ¸ϕh ě min ϕ h PΦ ϕ J h ˆÿ nPrN szE h pC h q ϕ h,n ϕ T h,n σ h,n ˙ϕh ě 1 C h σh min ϕ h PΦ ϕ J h ˆÿ nPrN szE h pC h q ϕ h,n ϕ T h,n ˙ϕh .We now utilize a basic matrix inequality that for any matrix A, B, we havemin ϕ h PΦ ϕ J h Aϕ h ě min ϕ h PΦ ϕ J h pA `Bqϕ h ´max ϕ h PΦ ϕ J h Bϕ h , which allows us to further bound min ϕ h PΦ ϕ J h Σ ‹ h ϕ h as min ϕ h PΦ ϕ J h Σ ‹ h ϕ h ě 1 C h σh min ϕ h PΦ ϕ J h ˆN ÿ n"1 ϕ h,n ϕ T h,n `λI d ˙ϕh ´1 C h σh max ϕ h PΦ ϕ J h ˆÿ nPE h pC h q ϕ h,n ϕ T h,n `λI d ˙ϕh Á 1 C h σh ˆγ´1 ´N C h ´λ˙,This leads to the following result:min ϕ h PΦ ϕ J h Λ h ϕ h " min ϕ h PΦ pϕ J h Λ ´1 h ϕ h q ´1 Á " max ˆcoff pX off q N off , d on N on ˙*´1 " γ ´1,where the first equality holds because Λ h is a linear transformation on the subspace Φ. Equivalently, this holds from the variational characterization of the eigenvalues and the fact that the largest absolute eigenvalue is equal to the inverse of the smallest absolute eigenvalue of the inverse. As a result, in order to rule out the effect of the "high variance trajectories", we select the truncation level δ h such that N {C h " Θpγ ´1q, implying C h " ΘpN γq. Hence, we obtain the following lower bound:min ϕ h PΦ ϕ J h Σ ‹ h ϕ h Á 1 γ 2 N σh .Finally, we note thatH ÿ h"1 max ϕ h PΦ b ϕ J h Σ ‹ h ´1ϕ h " H ÿ h"1 ˆmin ϕ h PΦ b ϕ J h Σ ‹ h ϕ h ˙´1 À γ ? N H ÿ h"1 ? σh ď γH ? N σ.Lemma 18 (Modified Lemma B.1 from Zhou and Gu (2022)). Let X off , X on be a partition of SˆAr Hs, such that their images under the feature map, Φ off , Φ on are subspaces of dimension d off , d on respectively. Let tσ k , β k u kě1 be a sequence of non-negative numbers, α, γ ą 0, tx k u kě1 Ă R d and }x k } 2 ď L. Let tZ k u kě1 and tσ k u kě1 be recursively defined as follows: Z 1 " λI `Zoff for some symmetric matrix Z off , where N " N off `K, and we have@k ě 1, σk " max ! σ k , α, γ }x k } 1{2 z ´1 k ) , Z k`1 " Z k `1Xon x k x J k {σ 2 k Let ι " log `1 `N L 2 { `dλα 2 ˘˘. Then we have K ÿ k"1 min ! 1, β k }x k } z ´1 k 1 Xon ) ď 2d on ι `2 max kPrKs β k γ 2 d on ι `2a d on ι g f f e K ÿ k"1 β 2 k pσ 2 k `α2 q.Proof. The proof roughly follows that of Lemma B.1 in Zhou and Gu (2022) , except that we have to make modifications as necessary to tighten the dimension dependence to d on and incorporate the offline data.Similar to Zhou and Gu (2022),ÿ kPJ1 β k σk }x {σ k z ´1 k 1 Xon ď ÿ kPJ1 β k pσ k `αq 1 Xon min ! 1, }x k {σ k } z ´1 k 1 Xon ) ď K ÿ k"1 β k pσ k `αq min ! 1, }x k {σ k } z ´1 k 1 Xon ) ď g f f e 2 K ÿ k"1 pσ 2 k `α2 q β 2 k g f f e K ÿ k"1 min ! 1, }x k {σ k } z ´1 k 1 Xon ) 2 ď 2 g f f e K ÿ k"1 β 2 k pσ 2 k `α2 q a d on ι,and as for k P J 2 we have that σk "γ 2 }x k {σ k } Z ´1 k 1 Xon , ÿ kPJ2 β k σk }x k {σ k } Z ´1 k 1 Xon " γ 2 ¨ÿ kPJ1 β k }x k {σ k } 2 Z ´1 k 1 Xon " γ 2 ¨K ÿ k"1 β k min ! 1, }x k {σ k } 2 Z ´1 k 1 Xon ) ď 2 max kPrKs β k γ 2 d on ι. Therefore, K ÿ k"1 min ! 1, β k }x k } z ´1 k 1 Xon ) ď 2d on ι `2 max kPrKs β k γ 2 d on ι `2a d on ι g f f e K ÿ k"1 β 2 k pσ 2 k `α2 q.Lemma 19 (Modified Version of Theorem 4.3, Zhou and Gu (2022)). Let tG n u N n"1 be a filtration, and tx n , η n u N n"1 be a stochastic process such that x n P R d is G n -measurable and η n P R is G n`1 -measurable. Let L, σ, λ, ϵ ą 0, µ ˚P R d . Arrange the datapoints from the offline and online samples as follows, 1, ..., N off , N off `1, ..., N off `Non . For n " 1, ..., N , let y n " xµ ˚, x n y `ηn and suppose that η n , x n also satisfyEQUATIONEQUATION))`6 log `32plogpR{ϵq `1qn 2 {δ ˘ϵ.Then, for any 0 ă δ ă 1, we have with probability at least 1 ´δ that, @n " 1, ..., N,› › › › › n ÿ i"1 x i η i › › › › › z ´1 n ď β n , }µ n ´µ˚} zn ď β n `?λ }µ ˚}2Proof. The proof is merely a small wrapper over Theorem 4.3 of Zhou and Gu (2022), where we adapt this to our setting in the same way that Tan and Xu (2024) do in Lemma 1 of their paper. That is, we pre-append the offline data to the online data, and generate the Z n , b n , µ n , β n accordingly.As in Lemma 1 of Tan and Xu (2024) , let N " N off `Non . Order the N off offline episodes arbitrarily, to form episodes 1, ..., N off , and then begin the online episodes from episode N off 1, ..., N . Then, we can directly apply Theorem 4.3 of Zhou and Gu (2022) to recover the desired result.Lemma 20. Suppose that W " R m and V " R n , where n m. Let : W Þ Ñ V be a linear transformation and that S " pU J U qW . As v, v 1 , . . . , v n P S, we havev J U J U ´k ÿ j"1 v i v J i `λI m ¯´1 U J U v " v J U J ´k ÿ j"1 U v i v J i U J `λI n ¯´1 U vProof. For projection matrix U , there exists orthogonal matrix Q P R mˆm and diagonal matrix D " pI n , 0 nˆpm´nq q such that U " DQ. We further define u " U v, ṽ " Qv, u i " U v i and ṽi " Qv i for 1 ď i ď n. Then, we note that as v P S, we have v " U J U v " Q J ΛQv, where Λ " diagpI n , 0 m´n q, which is equivalent to ṽ " Λṽ. As a result, we may conclude that ṽJ " pu J , 0 m´n q.Therefore, with a direct calculation, one will see that´k ÿ j"1 v i v J i `λI m ¯´1 " ´k ÿ j"1 Q J ṽi ṽJ i Q `λI m ¯´1 " Q J ´k ÿ j"1 ṽi ṽJ i `λI m ¯´1 Q " Q J ˆřk i"1 u i u J i `λI n 0 0 λI m´n ˙´1 Q " Q J ˜´ř k j"1 u i u J i `λI n ¯´1 0 0 λ ´1I m´n ¸Q.This will establish our desired conclusionLHS " v J ´k ÿ j"1 v i v J i `λI m ¯´1 v " ṽJ ˜´ř k j"1 u i u J i `λI n ¯´1 0 0 λ ´1I m´n ¸ṽ " u J ´k ÿ j"1 u i u J i `λI n ¯´1 u " RHS.The environment, as in Tan and Xu (2024) , is a 6-piece wide Tetris board with pieces no larger than 2 ˆ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. As in Tan and Xu (2024) , we 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 run on a single computer with an Intel i9-13900k CPU, 128 GB of RAM, and a NVIDIA RTX3090 GPU, in no more than a couple of hours.1. Claims Question: Do the main claims made in the abstract and introduction accurately reflect the contributions and 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 tightest theoretical guarantees currently available for hybrid RL in linear MDPs. Theorems 1 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 supports 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 in 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 can be expected to generalize to 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. 
 
 Appendix:  


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: 1. There is no clear new techniques introduced in the paper. 

2. 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.
questions: questions: see above
limitations: limitations: n/a
paper_summary: paper_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.
strength_weakness: strength_weakness: The assumption regarding Full Rank Projected Covariates seems to implicitly impose some constraints. 

No experimentation or code is included with the work, making it difficult to examine whether the proposed algorithms are efficient in practice.
questions: 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?

Q: HYRULE seems to be a straightforward generalization of existing algorithms. Could you please list the challenges in proving its regret guarantee?

Q: It would be helpful if there is an experimental plan to verify the algorithms. A simple toy experiment plan should suffice.

Minor suggestion:

As mentioned in line 241, OPTCOV requires tolerance parameter. Should this parameter also listed in the input of RAPPEL (Algorithm 1)?
limitations: 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.
paper_summary: paper_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.
strength_weakness: strength_weakness: 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.
questions: 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).

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.
limitations: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: Below are several potential improvements that authors are suggested to consider:

1. 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.
questions: 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?

2. 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?

3. Could you comment on the optimality of the provided bounds, whether dependence on the parameters involved can be further improved?

4. 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: limitations: This is a theoretical work, no negative social impact.

Comments: title: Rebuttal follow up
Rebuttal follow up
Rebuttal follow up
Rebuttal follow up
comment: I appreciate the author's efforts in addressing my concerns and improving the submission. I would appreciate if the techincal contributions can be highlighted more in the revised version. On that regard I would like to increase my score.
I thank the authors for their detailed response.

The studied settings are indeed interesting, and I do think the results of this paper will inspire future works in this direction. The current draft will absolutely benefit from incorporating the responses and clarification provided during rebuttal, which do contain a lot of useful information that was not captured in the initial draft. 

As a result, authors are suggested to carefully revise the draft and address the concerns raised by all reviewers. I am happy to raise my score for support, and look forward to your revision!
Thank authors for the careful responses and interesting additional experiments.  The clarification of the assumptions sounds reasonable and consistent with the experiment design. Given the thoroughness of the rebuttal, I have no further questions and am pleased to increase the score.
Dear Reviewer ujdT,

Again, we thank you for your effort in reviewing our paper and for your helpful comments! We have carefully considered your questions and addressed them in our response. We would like to know whether our response has appropriately addressed your questions and concerns about our paper. If we have fully addressed your concerns, we would appreciate it if you considered increasing your score for our paper. Please let me know if you have further comments or concerns about our paper. Thanks!
Dear Reviewer stbS,

Again, we thank you for your effort in reviewing our paper and for your helpful comments! We have carefully considered your questions and addressed them in our response. We would like to know whether our response has appropriately addressed your questions and concerns about our paper. If we have fully addressed your concerns, we would appreciate it if you considered increasing your score for our paper. Please let me know if you have further comments or concerns about our paper. Thanks!
Dear Reviewer 6qEJ,

Again, we thank you for your effort in reviewing our paper and for your helpful comments! We have carefully considered your questions and addressed them in our response. We would like to know whether our response has appropriately addressed your questions and concerns about our paper. If we have fully addressed your concerns, we would appreciate it if you considered increasing your score for our paper. Please let me know if you have further comments or concerns about our paper. Thanks!
Dear Reviewer SSHJ,

Again, we thank you for your effort in reviewing our paper and for your helpful comments! We have carefully considered your questions and addressed them in our response. We would like to know whether our response has appropriately addressed your questions and concerns about our paper. If we have fully addressed your concerns, we would appreciate it if you considered increasing your score for our paper. Please let me know if you have further comments or concerns about our paper. Thanks!