Leveraging Unlabeled Data Sharing through Kernel Function Approximation in Offline Reinforcement Learning
Authors: Yen Ru Lai
Fu-Chieh Chang
Pei-Yuan Wu
Venue: Accepted by TMLR ()

Abstract: Offline reinforcement learning (RL) learns policies from a fixed dataset, but often requires large amounts of data. The challenge arises when labeled datasets are expensive, especially when rewards have to be provided by human labelers for large datasets. In contrast, unlabelled data tends to be less expensive. This situation highlights the importance of finding effective ways to use unlabelled data in offline RL, especially when labelled data is limited or expensive to obtain. In this paper, we present the algorithm to utilize the unlabeled data in the offline RL method with kernel function approximation and give the theoretical guarantee. We present various eigenvalue decay conditions of $\mathcal{H}_k$ which determine the complexity of the algorithm.  In summary, our work provides a promising approach for exploiting the advantages offered by unlabeled data in offline RL, whilst maintaining theoretical assurances.

Published in Transactions on Machine Learning Research (04/2025)
Leveraging Unlabeled Data Sharing through Kernel Function Approximation in Offline Reinforcement Learning
Yen-Ru Lai
r09942079@ntu, edu.
Graduate Institute of Commaniention Engineering, National Taiwan University
Fu-Chich Chang
d099/201 50mttu edu.
Graduate Instibute of Commanication Engineering, National Taiwan University Mediatek Research
Pei- Yuan Wu Graduate Institute of Communication Engineering, National Taiwen University
peiguarens@ntu..o tw
Reviewed on OpenReview: http:://ppaarrrrs...aaa/a/aeeaa.
Abstract
Offinne reinforcement learning (RL) learns policies from a fixed dataset, but often requires large amounts of data. The challenge arises when labeled datasets expensive, especially when rewards have to be provided by human labelers for large datasets. In contrast, unlabelled data tends to be less expensive. This situation highlights the importance of finding effective ways to use unlabelled data in offline RI., especially when labelled data limited or expensive to obtain. In this paper, we present the algorithm to utilize the unlabeled data in the oflline RL method with kernel function approximation and give the theoretical guarantee. We present various eigenvalue decay conditions of the RKHS H4 induced by kernel which determine the complexity of the algorithm. In summary, work provides promising approach for exploiting the advantages offered by unlabeled data in offline RI, whilst maintaining theoretical assurances.
1 Introduction
Reinforcement learning (RL) algorithms have demonstrated empirical success in a variety of domains, including the defeat of Go champions (Silver al. 2016). robot control (Kalashnikov al.) 2018), and the development of large language models (Stiennon al. 2020 In particular, these achievements are largely associated with online reinforcement learning, characterized by dynamic data collection. However, the widespread adoption of online RL faces significant challenges. In many scenarios, active exploration is impractical due to factors such as the high cost data collection (Levine et al. 2020). To this end, in this paper we explore offline reinforcement learning a fully data-driven framework similar to supervised learning. Unfortunately, fully data-driven offline RI. demands large datasots. In more rcalistic scenarios, offline reinforcement lcarning (RL) could allow us to use smaller amount of lask-specific data along with significant amount of lask-agnostic data. This data is not labeled with task rewards, and some of it may not be directly relevant to the task at hand.
Prior works use learned classifiers that discriminate between successes and failures for reward labeling Fu et al. 2018 Singh et al. 2019) in the online RL setting. However, these approaches are unsuitable for the offline RL setting since they require real-time interaction. Alternatively, some rescarch focuses on learning from data without explicit reward labels by directly imitating expert trajectories (Ho Ermon 2016: Kostrikov al. 2019) deriving the reward function through inverse reinforcement learning using

---

Published in Transactions on Machine Learning Research (04/2025)
expert dataset (Fu et al. 2017 Finn et al. 2016). However, in real-world scenarios, these approaches may face challenges due to the resource-ineensive and costly nature of the expert trajectory acquisition and reward labelling process.
Yu et al. [2022] has revealed the challenges associated with learning to predict rewards, highlighting the surprising efficacy of setting the reward to zero. Despite these findings, the impact of reward prediction methods on performance and the potential demonstrable benefits of reward-free data in offline reinforcement
learning (RL) remain unclear. In response to this, Hu et al. 2023) have introduced novel model-free approach named Provable Data Sharing (PDS), PDS incorporates uncertainty penalties into the learned reward functions, maintaining conservative algorithm. This method allows PDS to take advantage of unlabeled data for offline RL, especially in linear MDPs. However, the linear MDP assumption is inflexible and rarely is fulfilled in practice. This question naturally arises.
How can we enhance the performance of offline RL algorithms that use kernel function approximation by effectively using reward-free data?
This work focuses the episodic Markov decision process (MDP). The reward function and value function are both represented by kernel functions. Inspired by the Provable Data Sharing (PDS) (Hu et al. 2023 framework, we propose new algorithm. The PDS algorithm has two main components. First, it pessimistically estimates rewards by applying additional penalties to the reward function learned from labeled data. This augmentation is designed to prevent overestimation, thus ensuring a conservative algorithm. The second part of the PDS algorithm uses the Possimistic Value Iteration (PEVI) algorithm introduced by Jin al. 2021 to derive the policy. Our main contribution is that
Extension of PDS framework: We expand the applicability of the Provable Data Sharing (PDS) framework, initially introduced by Hu et al. (2023). This extension goes beyond the original linear Markov Decision Process (MDP) setting, incorporating kernel function approximation. This expansion enhances the versatility of the PDS framework, making it applicable to broader range of scenarios. Our derivation is influenced by methodologies proposed for kernelized contextual bandits (Chowdhury & Gopalan 2017 Valko et al. 2013 Srinivas et al. 2009). as well as techniques such as pessimistic value iteration (PEVI) (Jin et al. 2021 and the kernel optimum least squares value iteration algorithm (KOVI) (Yang et al.) 2020
While Hu et al. (2023) focuses on discounted infinite-horizon MDPs, work shifts attention to horizon MDPs, which introduce unique challenges due to their horizon-dependent reward and transition functions. Unlike the discounted setting, where strong coverage assumptions such as finite concentrability coefficients are often required, our framework does not rely on such uniform data coverage.
Focus on finite-horizon MDPs:
Feature coverage asscssment via concentratability cocfficient: In contrast to Hu et al. 2023) which relies on a bounded concentratability coefficient to assess coverage over the stale-action space, we introduce a global coverage assumption (Assumption 4.7 based on the spectrum of feature covariance matrices. This approach (Wang al., (020aa), widely used in supervised learning, is particularly well-suited for settings with linear function approximation. Unlike single-policy coverage, our assumption requires sulficient data coverage across all policies in the considered class, ensuring broader applicability.
Enhance the suboptimality: By employing the data-splitting technique discussed by Xie et al. (202)), the suboptimality can be enhanced by a factor of vd, which depends on the choice of kernel. This enhancement comes at the cost of VH, a constant inherent in the MDP. Nevertheless, with an appropriate selection of kernel, the overall algorithmic performance can be significantly improved.
Our research provides a thooretical guarantce for effectively utilizing the benefits of reward-free data offiine RL. We aim to enhance the robustness of offline RL methods by maintaining theoretical guarantees, which offers valuable contribution to the ongoing development of more resilient and efficient RI. frameworks.
2

---

Published in Transactions on Machine Learning Research (04/2025)
2
Related Works
The issue of suboptimality in discounted and episodic MDP with model has been considered in linear and kernel settings. The results are presented in Table [ In the episodic MDP setting, we have the dataset with N trajectories of horizon H, and the suboptimality dependent on N and H. On the other hand, in a discounted MDP setting, we have the dataset with length N, and suboptimality dependent on and the discount factor y. The PEVI algorithm (Jin el al. 2021 serves as the foundational algorithm within Hu et al. (2023) and our work. If we assume that the infinite horizon MDP should conclude within H steps (referred to the effective horizon) (Yan et al., 2022). we set the discount factor 7 such that H = 1/(1 ?)-
Consequently, the suboptimality for the PDS algorithm is expressed as O(dHt2 +) where N₂ is the mumber of trajectories for the unlabeled dataset. Similar to Hu et al. (2023), we incorporate unsupervised data sharing to enhance the offline RL algorithm. The linear setting is a special case of the kernel setting with a linear kernel. In this case, we can recover the suboptimality as Ö(H N, NT where N1 is the number of trajectories for the labeled dataset, as provided in Hu et al. (2023). A notable difference between PEVT and PDS lies in PDS's utilization of data sharing to improve the suboptimality through an unlabeled dataset. It's important to note that N₂ > N1 in general. When comparing PDS with our approach in linear sctting, the H-folds data splitting in our algorithm enhances the suboptimality by a factor of Vd. However, this improvement comes with a tradeoff, as our algorithm introduces a suboptimality increment by a factor of VII because we need to partition the data set into H folds. As a result, each estimated value function is derived from only N2 H episodes of data.
Table 1:
The existing suboptimality under weak convergence (see Assumption 4.7 (except for the last row), discussed in Section 2 Here, the labeled dataset is represented as {(s a' ho r ") unlabeled
dataset is represented as {(stT+ +N+ N ",,, Denote G( the maximum information gain, SD maxne[M] E. (D,, 81 = so] represents a maximum amount of information from the dataset D and D where D' is the combination of 'D and observed data 2, and Cp max Ex, (G.(( Df) 81 80]
where the definition of Dj, is shown in Theorem 4.3 v v=1+ +, A= 1+ N and N N₁ + N2. In a linear MDP setting, it is stated that the transition probability can be represented linearly in feature map of state-action with d dimensions.
Algorithm
MDP
Setting
SubOpt
PEVI Jin et al.
2021
Episodic
Linear
Ö(dH2
PDS
Hu al.,
2023
Discounted
Linear
odd(1-7)-2N, O(Hd) O(HidiN
kernel-based, d-finite spectrum
Our work
Episodic
kernel-based, general setting
Our work
Episodic
O(H/G(NN, + O(H² V
2.1
Offline Reinforcement Learning
In offline reinforcement learning (RL), the goal is to learn a policy from a static data set collected previously without interacting with the environment. Current approaches in offline RI. (Levine et al. 2020) can be broadly classified into dynamic programming methods and model-based methods. Dynamic programming methods aim to learn state action value function, known the Q function. Subsequently, this value function is used either to directly find the optimal policy or, in the case of actor-critic methods, to estimate gradient for the expected returns of policy. The offline dynamic programming algorithm operates in a labular setting (Jin et al. 2018). However, algorithms designed for labular settings have limitations when applied to function approximation settings with a large number of effective states. Recent work has centered around the functional approximation setting, especially in the lincar setting, where the value function (or transition model) can be represented using a linear function of known feature mapping (Jin et al. 2021 Cai et al. 2020 Zanette et al. 2021). As the linear Markov decision process (MDP) assumption is rigid and
3

---

Published in Transactions on Machine Learning Research (04/2025)
rather restrictive in practice, Wang et al. (2020b) explores the kernel optimal least squares value iteration (KOVT) algorithm (Yang et al. 2020) for general function approximation. In contrast, model-based methods rely on their ability to estimate the transition function using parameterized model, such as neural network. Instead of employing dynamic programming methods to fit the model, model-based approaches leverage their ability to effectively utilize large and diverse datasets to estimate the transition function (Yu el al.) 2021b Janner et al. 2019; [Chara & Sun, 2021). Both of the methods presented above require a large amount of data to learn a state-action or transition function. In our work, we use reward-free data (i.e., unlabeled data) to improve the performance of learning a state-action function. On the theoretical front, Yin et al. (202bb) explore offline reinforcement learning with differentiable function class approxinations, extending to non-linear function approximation. [lanchet et al. (2024) investigate distributionally robust offline reinforcement learning (robust ofliie RL), which aims to identify an optimal policy from oflline datasets that remains effective in perturbed environments. Meanwhile, Hu et al. (2024) addresses the fundamental challenge of transitioning from offline learning to online fine-tuning.
2.2 Offline Data Sharing
Data sharing strategies in multi-task reinforcement learning (RL) have shown effectiveness, as observed in works such as Yu et al. (2021a); Eysenbach et al. (2020): Chen et al. (2021). This involves reusing data across different tasks by relabeling rewards, thereby enhancing performance in multi-rask offline RL scenarios. Prior work has employed various relabeling strategies. These include uniform labeling (Kalashnikov et al.] 2021), labeling based on metrics such as estimated Q-values (Yu et al., 2021a), and labeling based on distances to states in condiiond settings (Chen et al. 2021]. p. However, these approaches either necessitate access to the functional form of the reward for relabeling or are confined to goal-conditioned settings. On the other hand, Yu et al. (2022) proposes a straightforward strategy by assigning zero rewards to unlabeled data, On the other hand, Hu et al. (2023) employs linear regression to label rewards for unlabeled data. These approaches present alternative and potentially simpler methods for relabeling, especially in scenarios where direct access to the reward function is challenging or unavailable. In our work, we propose kernel ridge regression to exploit unlabeled data which under certain conditions can be reduced to linear regression.
3 Background
3.1 Episodic Markov Decision Process
Consider an episodic MDP (Yang et al. 2020 Sutton & Barto 2018), denoted as = A,, with state space S, action space A, horizon H, transition function P = (Pn he and reward function r = fra fnememm- We assumne that the reward function is bounded, that is, Th E [o, 1]. For any policy и = { he and h [H], we define the state-value function VTT S + R and the action-valued function (Q- (Q-nunction)
Q7: SSSAAA+ R as (s) = E,, E> (()),))))))) = and QT a) E, [E re(Se, ae)lsh = s, a, a These two functions satisfy the well-known Bellman equation: V7((s) (QT(s,)), Tx 8)) and ()), E [rn (sh, an) + V (86+1) 8h = 8, = =a]. For any function S ++ R. we define the transition operator at each step h E [M] as (Pn.)) (s,a) = (sh+1) Sh = 8,0, = a), and define the Bellman operator as (Brl) (s.a) = E [rn (sh, az) 8n = 8,44 = al + (PP.) (8, a). Similarly, for all h E [H], the Bellman optimality equations defined as (s(() = sup Q7 and (s, = (Bn Vitra) (s, a). Meanwhile, the optimal policy x" satisfics o s) = argmax (Q) -), (.( ,)) and (s) = (Q7 -), x- {)) Reinforcement lcarning
aims to learn a policy maximizing expected cumulative reward. Accordingly, we define the performance metric(i.e., suboptimality) as
SubOpt(T;;) = VT (s) - Vs)
(1)
3.2 Assumption of Offline Data
In offline RL setting, a learner uses pre-collected dataset D, which consists of N trajectories N.H {"TT,,"% 7 generated by some fixed but unknown MDP M under the behavior policy x in the
following manner: Si ~ ,aT Th (: 8'7) and *++1 ~ Ph ( S To a'T) 1 < h & H. Here p represents
4

---

Published in Transactions on Machine Learning Research (04/2025)
predetermined initial state distribution associated with the static dataset. The learner may also have partial ob- servations of the reward in addition to the above state-action observations. More elaborately, we assume access N..H to both labeled dataset D1= {s a ho r2) 7, and an unlabeled dataset D2
{(5 ( ahh (.rtMi J,,==i'
Na.l
We utilize the estimated reward function with parameter 0, as determined equation ion D2- The relabeled dataset, denoted as D1 = { s o No . (s', ,00 ))) T
( to relabel dataset. Ng.
3.3 Reproducing Kernel Hilbert Space
Consider a reproducing kernel Hilbert space (RKHS) function space. For simplicity, let == (s, denote a state-action pair and denote Z = S x A. Without loss of generality, we regard Z as a compact subset of RT,, where the dimension m is fixed. Let k: Z x Z + R be a positive definite continuous kernel and its corresponding Gram matrix [K],, = 2,), V E [m]. Note that K is positive semi-definite, Define H4 as the RKHS induced by k; containing a family of functions defined in 2. Let (s,) Hr x Hr - R and || 1|H, Hr + R denote the inner product and the norm on He, respectively. According to the reproducing properly, for all f E Ha. and 2, holds [(=) = (f, kt, 2)) H. For more details and different. characterizations of RKHS, see Aronszajn 1950 Berlinet & Thomas Agnan 2011). Without loss of generality, we assume that sup=cz k(2, 2) 1
Let (2) be the set of square-integrabbee functions on 2 with respect to the Lebesgue measure and let (, c) be the inner product on (Z). The kernel function induces an integral operator T. (3 (Z defined as [=) = f2 k (2, z/) f (z') d2' for all f E (2). . By Morcer's thcorem (Steinwart & Christmann 2008 the integral operator T3 has countable and positive eigenvalues farte21 and the corresponding eigenlunctions (1/) Then, the kernel function admits spectral expansion k (2) = Ei (n)l())) (z'). Morcover, the RKHS Hg can be written
subset of (Z) such that H4 = = (T(((()) (i (f. vile < s0). and the inner product of Hr also can be written as (f.9'H, = =E (1/a,) (f, the) (g. 12) for all f.g He. With the above construction, the scaled eigenfunctions {Vo,0) form orthonormal basis for Hr. We define the mapping & :2 + k(2,-) to transform data from 2 = S x A to the (possibly anfnite-dimensions RKHS HA, which satisfies =(z,=')= (0(=), o(=')H,, for all 2, 2 с 2 (Steinwart & Christmann 2008 Lemma 4.19). We define the maximum information gain (Srinivas et al. 2009) to describe the complexity of Hy:
G(n, = sup { log
log det + KD/A) : D C 2Z S I
where KD is the Gram matrix for the set D. Furthermore, the magnitude of maximal information gain G(n, X) depends on how rapidly the eigenvalues decay to zero, serving as a proxy dimension of H in the case of an infinte-diimeniinall space. If Hr is finite rank, we have that G(n, = (dg (Yang et al. 2020 where d is the rank of Hr- referred as the d-finite spectrum. In the following, we present several cond conditions
that are often used in the analysis of the RKHS property of Hd (Yang et al. 2020 Vakili et al. 2021 Yeh et al. 2023 characterizing the cigenvalue docay of H4.
Assumption 3.1. The integral operator Tk has eigenvalues {azbı21 and the associated eigenfunctions f0y121 We assume that {ā,}ı21 satisfies one of the following conditions for some constant d > 0.
d-finite spectrum: oj = 0,0, > d, where d is a positive integer.
d-eaponential decay: there erists some constants C1, C2 > O such that oj S C₁ exp (-C2- jd). Vj 2 1, where d O.
d- poloynomiall decay: there ezists some constants C₁ > 0 such that o₁ S C1 . Vj 2 L,, where d d> 1.
For both d-exponential decay and d- d-polynomial decay, we assume that there ezists Co such that sup Tj. (y)()) E Cs holds for all j and 1/2).
5

---

Published in Transactions on Machine Learning Research (04/2025)
For instance, let Z C Rd and assume the kernel function 222,2') 1, the Squared Exponential kernel, defined
88
z'F
1(z,z') exp
(3)
212
where is a lengthscale parameter, exhibits d-exponential decay. Similarly, the Matérn kernel, given by
21-6 Te (r)r), where T(v)
V2v 2 2/1,
2(2,2") [(v)
is characterized by d-polynomial decay. Here, determines the smoothness of sample paths (with smaller v producing rougher paths), and (r) is the modified Bessel function. Theorem 5 in Srinivas et al. (2009)
provides detailed proof for these kernel properties.
We assume that the Bellman operator maps any bounded function onto a bounded RKHS norm ball, which is a common assumption used in the function approximation (Vang et al. 2020; Jin et al. 2018).
Assumption 3.2. Define the function class Q = {f E Hz : [lHlH, & Ro H) for some fixed constant RQ > 0.
Then, for any & E [H] and any Q : A + [0, HJ. it holds that B, V Q" for V(s) maxaed Q(8 a).
A sufficient condition for Assumption 3.2 to hold is when S = [0, 1]mh and that rn(:))). PA (s' :.))) E {f E Hy : Ilf lm $ 1} for all h E [H], integrable V > [0, H) holds,
E S. To see this, suppose this condition holds, then for any
|| + PA Vila S ||rallze + 1| $1+ $1+1//r Pa(d'l,.)V(''') do
YES
7e
< 1 + JeES |Pa(d Fe ds' ds'= 1+ /ses SES
|| (P'(ssss V (s')l,, ds'
S S1+H
ds' = =
WEs
Note that under the assumptions of measurability and boundedness on the kernel k, VIPAVIIe E Hk, which is given in Muandet et al. (2017) section 3.1). Thus, Assumption 3.2 holds with RQ = 2. This assumption is mild and also used in Yang et al. (2020). Similar assumptions are used in lincar MDP's, which are much stricter (Jin et al. 2021
Zanette et. al. 2020
3.4 Pessimistic Value Iteration and Kernel Setting
We consider the pessimistic value iteration, i.e., PEVT (Jin et al., 2021 algorithm, described in Algorithm as the backbone algorithm. This is a model-free, theoretically guaranteed offline algorithm. The fundamental insight of PEVI lies in the incorporation of penalty function, which essentially introduces sense of pessimism, into the value iteration algorithm. The key challenge extend PEVI kernel setting is that the dimension (even effective dimension) of the kernel based model (when interpreted as lincar model) is divergent.
In addition, we apply the data splitting method (Rashidinejad et al. 2021 Xie et al. 2021). As introduced in Rashidinejad et al. (2021), data splitting makes sure that the estimated value Vh+1 and estimated Bellman operator B,, are estimated using different subsets of D, this yields conditional independence that is required in bounding concentration terms of the form (Bn. BB)) Vh+1, and hence the suboptimality can be reduced by factor of Vd. However, applied naively, this data splitting induces one undesired VH factor in the optimality as we need to split D into И folds and thus each IB, is estimated using only N/H episodes of data. Further details of the PEVI algorithm can be found in Appendix B
4 Unsupervised Data Sharing
Our algorithm comprises two main components. The first part involves employing kernel ridge regression learn the reward function using the labeled dataset and constructing the confidence set.. Next, to mitigate

---

Published in Transactions on Machine Learning Research (04/2025)
overestimation in reward prediction, construct the pessimism reward parameter 0 within the confidence set. Section 4.1 discusses this in more detail. The second part involves using the pessimistic reward estimator 0 to relabel the entire dataset, which is combination of the labeled dataset and the relabeled dataset. Following this, we employ the PEVI algorithm with kernel approximation and data splitting (refer to Algorithm g to determine the optimal policy. The detailed steps of the algorithm are outlined Algorithm [
Algorithm Data Sharing, Kernel Approximation
1: Data: Labeled dalasel D1, and unlabeled datasel D2- 2: Input: Parameter Ba(5), 6, B, X.
Learn the reward function 01,- On from Dj with
Ni Σ
0n argmin H.EHa
rh The (5 (1) + vl10n lire.
4: Construct the pessimistic reward function with parameter 0 ;= 10 satisfy
pn (s.a) max (B. -3((d) (AP o(s a) ((s50))|mm.000 .0}
(4)
5: Annotate the reward in D with parameter = θ, where D combination of the labeled dataset D and the unlabeled dataset Dg. Learn the policy from the dataset DJ using Algorithm in Appendix:
H + PEVI (D', B.A (
Result: â
H [
4.1 Pessimistic Reward Estimation
We utilize labeled dataset D1 to train a reward function Fhi using it to label the unlabeled data. Assume that the observed reward is generated as r/ = rn (s a W) + of where rn : (s, + 0f,, a)) satisfies (s, E [0, 1] for all (s,a) a) S A, and c are i.i.d. centered 1-SubGaussian noisc. Here 6% E Hr is an unknown parameter, and S A Ha is known feature map defined in Section 3.3 Furthermore, we assume that ||0]|| 8. We learn the reward function from labeled data through kernel ridge regression problem. Using the fcature representation, we write
0n argmin
Σ
1 - The (6 (o ah))
vil0n 11
(5)
0, Ha.
where P as a)s.a),,.))) 0,) Ne with parameter 6,. However, this method leads to an overestimation of predicted reward values, as highlighted in Yu al. (2022). A novel algorithum called Provable Data Sharing (PDS) is introduced in Hu et al. (2023) to mitigate this problem. PDS incorporates uncertainty penalties into the learned reward functions and integrates scamlessly with existing offline R.L algorithms in linear MDP setting. We extend the application of this algorithm to the kernel setting.
To address the problem of overestimating predicted rewards, we analyze the uncertainty in the learned reward function. The previous solution defines the center of the ellipsoidal confidence set:
(b) = {0 E Ho ||0 - 0n S =.100).
(6)
where [|01],p = -0..AR.0) Me AP
and AR = MM, o6s d' No(s'h + +II is positive definite operator, and (0) is its radius which follows the following proposition.
7

---

Published in Transactions on Machine Learning Research (04/2025)
Proposition 4.1. We define (a( with the labeled data set D1 by 3a(6) = vv8 + Vlog log det 1 where 52
Kh is the Gram matric constructed from the dalaset D1 as (hh n, 1.,-- for T, E [Ni] and for each h [H] and d (0,
- k(= 2/h,1 where z' = (5 aTT)
Then, with prolubility at least 1 - ó have |0h Shh-@:lllss oillap S (,((6), where 0o is the solution of equation (5). Furthermore, consider the information gaan
G(N,V), defined in equation 2 of the matria P and set v == 1+ 1/N1, (a) can rewrillen as
3n(0) VB8 2G( + log 82
Morcover, defone Cr(o) {0- Hi: |00 Ōn |ap) S &Ba(o)).
}: we have P (0% Ck())) 2 1
Proof. Please refer to Appendix B.1 for detailed proof.
In Proposition 4.1 the uncertainty of the learned reward function depends on the maximum information gain of the Gram matrix KY However, finding the optimal parameter within the confidence set is computationally inefficient. To address this challenge, Hu et al. (0223) proposes an approach that preserves the pessimistic property of the offline algorithm. This method uses pessimistic estimation, allowing the algorithm to remain pessimistic while mitigating computational challenges. Formally, we construct the pessimistic reward function pde (s, a) for the paramcter 0 as
F The (s, a) = max ((n, Ha
-A - a) .) He
The equation (8) is direct consequence of the following lemma derived from Cauchy-Schwary inequalities. Lemma 4.2. (On (s, a)) Hx
for any On E Cx(,), [H]. s Bn(() (AP 20(s, - a) Hv
The equation
g provides a lower bound for the reward function within the confidence set C(0). When the labeled data scarce, or when there significant shift in the distribution between the labeled and unlabeled data, the confidence interval becomes wider and then the equation ( degenerates 0, which is reduced to the UDS algorithm Yuu et al. 2022 Hu et al. 2023
4.2 Theoretical Analysis
The suboptimality of the Algorithm D is characterized by the following theorem.
Theorem 4.3. Consider the MDP described in Section 3.1 Under Assumption 3.1 and Assumption
2. and suppose the labeled dataset DD and unlabeled dataset D2 are defined in Section 3.2 Define
DO_ = ((8,,) a7, The (5%, ( N.H which is combination of labeled dataset Dj and unlabeled dataset DG with
N N₁ + Ng. We partition dataset D into H disjoint and equally sized sub dataset (Di) H h=11 where 1D
NH N/H. Let In {NH 1)-1)+1,, Nu h} = "T Nh.N satisfy Df. {(5 oh, rT))eEI where
We set x 1 N. 1 + in Algorithm 7
N 8+ + VC . log Ni + log )
d- d-finite spectrum,
(0) =
S + VC (log N1) + log( 1b)
d d-eeponential decay,
Mi
18 Cc (N1)
m=m log(N1) + log( )b)
d d-polynomial decay.
Cn H. Vd (N/8)
d d-finile spectrum, d d-exponential decay, d- d-polynomsal decay.
B =
Cg H. (log N/8) 11//
C2 N 2(2+m) H² 2d-m
log( (N/8)
8

---

Published in Transactions on Machine Learning Research (04/2025)
Here, C1, C2 0 are absolute constants that does not depend N1,N, nor H. E S, with probability - 28, the policy a generated by Algorithm solisfies
Then, for fized initial state
SubOpt(ft; 80) s
(5) [ an an)laas 181 = $0
H
+ 2B
E
(1((0)) an)l (A,
18 = 80
A=1
Proof. For detailed proof, see Appendix B.2
Two key terms express the suboptimality bound. The first term is the reward bias introduced by uncertainties in estimating rewards. This term reflects the challenges and inaccuracies associated with predicting or estimating rewards in given environment. The second term represents the offline algorithm and optimal policy x² error.
Remark 4.4. We use the Lemma C.2 to rewrite the term of (6) and B in the Theorem 4.3 as (n( O6 G( )) and B O( G(N.
By this remark, both (8) and B depend on the kernel function class. It is worth noting that lØ(sn, an)l(())) can be expressed as an information quantity for the datasct D, as outlined in the following proposition.
Proposition 4.5. For all h E [H], we partition dalaset D inlo H disjoint and equally sized sub dalasels | where D (15 o7 Nи = N/H. Denote the operator + Dn. Hx + RN,, and Ps Hr -> Ht as
( ThIEEE, with In {NH (h- L...., Nu h} {Th,1, Th,NH and
te (1
A Ph = x Ix + (T
To.NN
k (:22 ThiN
2/
Define Gram matria K, = 10/0 (2) (.)).. Then, for any 2 E Z, we have
d(=) (A 0(2) 2. [ det
T+ (T+ Kb 1/) log det (T+ K /A)
(9)
where Dj, is the combination of dataset Dr, and which satisfies APt A +
Proof. For a detailed proof, see Appendix B3
Remark 4.6. In Proposition 4.5 Hl can be infinite dimensional. However, for the sake of clarity, represent P..h matrix and dbz%)) a column veclor for all T E In.
Here, define
(D' 2 log det (T+ K (R'A) - log det (T KR ////
(10)
as the maximal information amount between the dataset D' and D. Proposition 4.5 states that if the training data set is well known about z, then equation (10) will be close to zero. On the other hand, if the training
data set is not well known about 2, then equation 110 will be large.
We specialize the d- finite spectrum case of Theorem under weak data coverage assumption to better understand the convergence of Algorithm 1
9

---

Published in Transactions on Machine Learning Research (04/2025)
Assumption 4.7 (Weak Convergence). Suppose the dataset D ((s: 0he rT)) consists of N trajectories, for all E , the trajectories are drawn independently and identically from distributions induced by some fixed behavior policy ß such that there evists a constant Cmán > 0 satisfying inf Infllfll =1 ( Ba (σ(z))((z)) Cmin for any h E [
Intuitively, Assumption 4.7 posits that the collected data should be relatively well distributed throughout the state action space. Notably, Assumption 4.7 shares similarities with other explorability assumptions common in reinforcement learning literature, such as those in Yin et al. (2022a); Wagenmaker & Pacchiano (2023)
Corollary 4.8 (Well-Explorod Datasct). In the d-finite spectrum case, assume that the Assumption 7.7 holds
under the same condilions as Theorem 4.3 Then for Ni ((log(dH/0) and N 2 H 2(oog(dH ()), with
probability at least 1 - 6, we have
SubOpt(f;;) s) < 23k(8) H c/ S/VN +2B H C//NHH
(11)
SO(H V + +H
Nº
In the d-finite spoctrum case, a significant difference between our present study and previous work (Hu et al, 2023) lies in the incorporation of factors vd and vH, introduced by the implementation of the data splitting technique (Xie et al. 2021). This technique plays crucial role in the linear case, influencing the overall convergence behavior of the lcarned policy. If we aim to transform the feature mapping from dimensionality of d to d', where d' > d, the data partitioning method can help mitigate the convergence of the error bound. Finally, we combine the result. in Therorem
4.3 Remark 4.4 and Corollary 4.8 to get. Table D
Remark 4.9. For Assumption 4.7 7 the scenarios involving d- eeeeoonentill and d d-polynomial decay are not generally valid. If Assumption 4.7 holds true, by integrating Lemma B. Lemma
B.3 and equation 89 we
can deduce the explicit form of SubOpt(fr s) as
HNT + + (HHN5 HN,
d d-exponential decay,
SubOpt(f;
1 ml
+ Ô
(H2-2 2(d+m)) N₂
1 mil
2(d=m)
d- polyyoommal decay.
(12)
Nonetheless, Assumption T does not hold under scrutiny. To demonstrate this, let's assume that Assumption 4.7 true. It meons that for every f within the set fl]fl =1}, satisfies E=Iff, ((Z))((2))) fll Cuin- Then, we express & and f as o Ee a.y;s and -Ee bey's respectively, where (w:)721 is orthonormal basis of Hr. Given that I can vepresent anyy function salisfying I1 =1, let be any vector such that J by4y for an arbitrary j. Consequently, for all j, the expectation IE ((z))) f)] at 2 Cmin is satisfied, which resulls in paradox because the norm should be fonile; however, l| Ei= ag Ei= Cmin oc.
5 Experiments
In the following experiments, execute Algorithm I to obtain the policy गे and the corresponding value function V/" (s), where 8 is sampled from the initial distribution p(s). For our experiment, we select the Squared Exponential kernel from equation (3) as the kernel function k(z, By applying the kernel trick, the pessimistic reward function p&A (s, a), as defined in equation (8, can be computed using the following expression:
-0n (s) (h (s,a)) (KP) + tut) yh
1/2
(b((0) 1- (N((s,.), k (s, (KP) vll) kb (s, (s,
where hRth and yh defined in equation 17 and 18). respectively. We implemented our algorithm using
Python's 's NumPy library. To ensure reproducibility our experimental code is publicly accessibld
10

---

Published in Transactions on Machine Learning Research (04/2025)
5.1 Asymptotic Behavior of (s)
In this experiment, we investigate the asymptotic behavior of (s). Although we are unable to theoretically
validate the correctness of equation (12) due to the violation of Assumption 4.7 we provide empirical evidence that, when the kernel function is the Squared Exponential kernel satisfying d-exponential decay, its asymptotic behavior closely aligns with equation (12). We create an toy example RL environment which meets Assumption 3.2] ensuring bounded RKHS norms for ra(:.)) and P(sl)..). The MDP M (S,A, HrP,)
for this toy example is as follows.
S s= C] A= - 10.,,..., C2 H=C, Pa(s' s00) exp[-a (s' - ((s + a) mod 07)²| //Ta/a
r(s,a) = exp -a (s -012))) /x/a.
where a and C are constants, set a 3 and C= 8 in our experiment. To ensure that remains within the state space S, we replace s by "s' mod C" after sampling s ~ Pr-(ss, a). To examine the asymptotic varied the parameters N1 and N₂ and plotted the resulting values of VF in the left column of Fig. 1 For asymptotic approximation, using equation 12 (T((s) can be expressed in the
behavior of (TT(s,,
following form:
(T) co -CN c2N, -
where co C1, and 02 are constants. By applying linear regression to the experimental data (left column of Fig- [. estimated these constants and plotted the corresponding curve in the right column of Fig. [ The strong agreement between the experimental results and the asymptotic approximation validates our hypothesis that the asymptotic behavior of V conforms to our theorctical predictions.
Experimental Values of (+)
Asymptotic Approximation (+)
N: 10
N1 10
N;
N: 50
N; 50
Ni 100
N1 100
100
300
400
500
Ng
Ng
Figure 1: Comparison of experimental values and asymptotic approximation of V (s).
5.2 Comparison between Finite Dimensional Features and Kernel Features
In this experiment, present real-world example demonstrating the superior performance of our kernel- based offline RT. method compared to finttediimensional feature representations Φ, which follows the setting of Hu et al. (2023) but in a finite-horizon scenario. We select the CartPole environment from OpenAl Gyn as our test environment. To implement the & with diite-dimensional feature representations, we consider three different realizations of 6(s, linnear,, quadratic, and cubic- denoted as Plins &quad, and deub, respectively, which are defined as follows:
Φnn = (1, I1, T2,
,n)) where Ei, In is the elements in the concatenation of (s,
quadd = (1, T2,
In, 12
-nn-1pps 2
dcub (1, In,
2
212243. -nn-2 1 J n- 2 22)
-In-I
11

---

Published in Transactions on Machine Learning Research (04/2025)
We compare these three finite-dimensionall feature representations with kernel-based RL method using the Squared Exponential kernel feature, denoted as Φx, under various configurations of Ni and N2- The results are presented in Fig. 2 Our findings suggest that, the kernel-based Øx generally outperforms alternative fnite-dimensional & approaches when N2 I 500. The performance gap between Øж and other e becomes more pronounced when N₂ S 100. This indicates that kernel methods, with their more flexible function approximation, better capture the reward and transition dynamics synamics-particnlalyy particularly when unlabeled data is scarce resulting in higher (s) compared to Enite-dimensionall representations.
Values of V/ (s) when N1 = 20
Values of Vf when N1 50
10
40
Pxx (=)
(x
(cub(2)
deub(2)
20
Aquae (x)
(2)
(=)
0
N2
N2
Values of (s) when N₁ 100
Values of (s) when No 200
60
60
40
40
(x)=)
(x(
(z)b(2)
Poub (=)
20
20
quaad (=)
dquaa
Winn (*)
Ohi (x)
100
200
300
400
500
100
200
300
400
500
Figure Comparison the values of V/" (s) between finite dimensional features and kernel features.
6 Conclusion
In this paper, we demonstrate that incorporating unlabeled data into offline RL can greatly improve offline RL performance. Our theoretical analysis shows how unlabeled data can improve the performance of offline RL, especially in a more general function approximalion setting, in contrast to the results in Hu et al. (2023). Our analysis is based on the common offline RL assumption about the dataset, providing comprehensive examination of the algorithm's performance under these conditions. In future work, it may be interesting extend to the discounted MDP setting to deal with more category problems and the low-rank MDP @Uehara)
et al.
2021
Acknowledgments
This work supported in part by the Ministry of Education (MOE) of Taiwan under Grant NTU-111L891406, the Asian Office of Acrospace Rescarch and Development (AOARD) under Grant NTU-112HT91 1020, the Center of Data Intelligence: Technologies, Applications, and Systems, National Taiwan University (grant nos. 111L900901/ 1111900002/111100000
from the Featured Areas Research Center Program within the framework of the Higher Education Sprout, the Ministry Education (MOE) of Taiwan, and the financial supports from the Featured Area Research Center Program within the framework of the Higher Education Sprout Project by the Ministry of Education (111.900001//111.0000005
12

---

Published in Transactions on Machine Learning Research (04/2025)
References
Yasin Abbasi-Yadken Dávid Pál, and Csaba Szepesvári. Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24, 2011.
Nachman Aronszajn. Thcory of reproducing kernels. Transactions of the American mathematical socicty, (3):337-404, 1950.
Alain Berlinet and Christine Thomas-Agnan Reproducing kernel Hilbert spaces in probability and statistics. Springer Science & Business Media, 2011.
Jose Blanchet, Miao Lu, Tong Zhang, and Han Zhong. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36, 2024.
Qi Cai, Zhuoran Yang, Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy optimization. In International Conference on Machine Learning, pp. 1283-1299 PMLR, 2020.
Annie S Chen, Suraj Nair, and Chelsea Finn. Learning generalizable robotic reward functions from in-the-wild' human videos. Robotics: Science and Systems (RSS), 2021.
Sayak Ray Chowdhury and Aditya Gopalan, On kernelized multi-armed bandits. In International Conference
Machine Learning, pp. 844 853. PMLR, 2017.
Yaqi Duan, Zeyu Jia, and Mengdi Wang. Minimax-optimal off-policy evaluation with linear function approximation. In International Conference on Machine Learning, pp. 2701-2709. PMLR, 2020.
Ben Eysenbach, Xinyang Geng, Sergey Levine, and Russ R Salakhutdinov. Rewriting history with inverse rl: Hindsight inference for policy improvement. Advances in neural information processing systems, 33: 17773-14795, 2020.
Chelsea Finn, Sergey Levine, and Pieter Abbeel. Guided cost learning: Deep inverse optimal control via policy optimization. In International conference on mochine learning, pp. 49 58. PMLR, 2016.
Justin Fu, Katie Luo, and Sergey Levine. Learning robust rewards with adversarial inverse reinforcement learning. In International Conference on Learning Representations, 2017.
Justin Fu, Avi Singh, Dibya Ghosh, Larry Yang, and Sergey Levine. Variational inverse control with events: A general framework for data-driven reward definition. Advances in neural information processing systems, 31, 2018.
Jonathan Ho and Stefano Ermon. Generative adversarial imitation learning. Advonces in neural information processing systems, 29, 2016.
Hao Hu, Yiqin Yang, Qianchuan Zhao, and Chongjie Zhang. The provable benefits of unsupervised data sharing for offline reinforcement learning. In The Eleventh International Conference on Learning Representations, 2023. URL htttps://openreviee httpp////pppeeeeeeeeee//ororrrre met//forru//dd-MTPPLewww.
Hao Hu, Yigin Yang, Jianing Ye, Chengjie Wu, Ziqing Mai, Yujing Hu, Tangiie Lv, Changjie Fan, Qianchuan Zhao, and Chongjie Zhang. Bayesian design principles for offlnne-to-onlne reinforcement learning. arXiv preprint ar Xrx::2240.. 209844, 2024.
Michael Janner, Justin Fu, Marvin Zhang, and Sergey Levine. When to trust your model: Model-based policy optimization. Advances in neural information processing systems, 32, 2019.
Chi Jin, Zeyuan Allen-Zhu, Sebastien Bubeck, and Michael I Jordan. Is q-carning provably efficient? Advances in neural information processing systems, 31, 2018.
Ying Jin, Zhuoran Yang, and Zhaoran Wang. Is pessimism provably efficient for offline rI? In International Conference Machine Learning, pp. 5084-5096. PMLR, 2021.
13

---

Published in Transactions on Machine Learning Research (04/2025)
Dmitry Kalashnikov, Alex Irpan, Peter Pastor, Julian Ibarz, Alexander Herzog, Eric Jang, Deirdre Quillen, Ethan Holly, Mrinal Kalakrishnan, Vincent Vanhoucke, et al. Scalable deep reinforcement learning for vision-based robotic manipulation. In Conference on Robot Learning, pp. 651 673. PMLR, 2018
Dmitry Kalashnikov, Jacob Varley, Yevgen Chebotar, Benjamin Swanson, Rico Jonschkowski, Chelsea Finn, Sergey Levine, and Karol Hansman. Mt-opt: Continuous multi-task robotic reinforcement learning at scale. arXiv preprint arXim:2104..888 2021.
Nya Kostrikov, Ofrr Nachum, and Jonathan Tompson. Imitation learning via off-policy distribution matching. In International Conference on Learning Represenlations, 2019.
Sergey Levine, Aviral Kumar, George Tucker, and Justin Fu. Offline reinforcement learning: Tutorial, review, and perspectives on open problems. arXiv preprint arXiv:2005. NXX:22005006443 01643, 2020.
Krikamol Muandet, Kenji Fukumizu, Bharath Sriperunbudur, Bernhard Schölkopf, et al. Kernel mean embedding of distributions: A review and beyond. Foundations and Trendso in Machine Learning, 10(1-2): 1-141, 2017.
Paria Rashidinejad, Banghua Zhu, Cong Ma, Jiantao Jiao, and Stuart Russell, Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances in Neural Information Processing Systems, 34:11702 11716, 2021.
David Silver, Aja Huang, Chris Maddison, Arthur Guez, Laurent Sifre, George Van Den Driessche, Julian Schrittwieser, Ioannis Antonoglou, Veda Panneershelvam, Mare Lanctot, et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7788):484 -89, 2016.
Avi Singh, Larry Yang, Kristian Hartikainen, Chelsea Finn, and Sergey Levine. End-to-end robotic reinforce- ment learning without reward engineering. environment (eg, by placing additional sensors), 2019.
Niranjan Srinivas, Andreas Krause, Sham M Kakade, and Matthias Seeger. Gaussian process optimization in the bandit setting: No regret and experimental design. In Proceedings of the 27th International Conference on Machine Learning, 2009.
Ingo Steinwart and Andreas Christmann. Support vector machines. Springer Science & Business Media, 2008.
Nisan Stiennon, Long Ouyang, Jeffrey Wu, Daniel Ziegler, Ryan Lowe, Chelsea Voss, Alec Radford, Dario Amodci, and Paul F Christiano. Learning to summarize with human feedback. Advances in Newral Information Processing Systems, 33:3008 3021, 2020.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Joel A Tropp et al. An introduction to matrix concentration inequalities. Foundations and Trends0 in Machine Learning, 8(1-2):1 230, 2015.
Masatoshi Uehara and Wen Sun. Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint Xix::1107.00 062662 2021.
Masatoshi Uchara, Xuczhou Zhang, and Wen Sun. Representation learning for online and offline in low-rank idps. In International Conference on Learning Represenlations, 2021.
Sattar Vakili, Kia Khezeli, and Victor Picheny. On information gain and regret bounds in gaussian process bandits. In International Conference on Artificial Intelligence and Stalistics, pp. 82 90. PMLR, 2021.
Michal Valko, Nathaniel Korda, Rémi Munos, Ilias Flaounas, and Nelo Cristianini. Finite-time analysis of kernelised contextual bandits. In Uncertainty in Artificial Intelligence, 2013.
Andrew Wagenmaker and Aldo Pacchiano. Leveraging offine data in online reinforcement learning. In International Conference on Machine Learning, pp. 35300-35338. PMLR, 2023.
Ruosong Wang, Dean P Foster, and Sham M Kakade. What are the statistical limits of offline rl with linear function approximation? Tn International Conference Learning Representations, 2020a.
14

---

Published in Transactions on Machine Learning Research (04/2025)
Ruosong Wang, Ruslan Salakhutdinov, and Lin F Yang. Provably efficient reinforcement learning with general value function approximation. arXiv preprint urXi::2005. 10804, 2020b.
Tengyang Xie, Nan Jiang, Huan Wang, Caiming Xiong, and Yu Bai. Policy finetuning: Bridging sample- efficient offline and online reinforcement learning. Aduances in neural information processing systems, 34: 27395-27400 2021.
Yuling Yan, Gen Li, Yuxin Chen, and Jianqing Fan. Model-based reinforcement learning is minimax-optimal for offline zero-sum markov games, arXiv preprint orXiv:2206.04000 2022.
Zhuoran Yang, Chi Jin, Zhaoran Wang, Mengdi Wang, and Michael I Jordan. On function approximation in reinforcement learning: Optimism in the face of large state spaces. arXiv preprinl arXiv:2011. 2iv:20011004222 04622, 2020.
Sing- Yuag Yeh, Fu-Chich Chang, Chang- Wei Yuch, Pui-Yuan Wu, Alberto Bernacchia, and Sattar Vakili. Sample complexity of kernel-based q-learning. In International Conference on Artāficial Intelligence and Statistics, pp. 453 469..469.600 PMLR, 2023.
Ming Yin, Yaqi Duan, Mengdi Wang, and Yu-Xiang Wang. Near-optimal offline reinforcement learning with lincar reprosentation: Leveraging variance information with pessimism. In International Conference Learning Represenlations, 2022a.
Ming Yin, Mengdi Wang, and Yu-Xiang Wang. Offline reinforcement learning with differentiable function approximation provably efficient. arXiv preprint arXio:2210.000 00750, 2022b.
Tianhe Yu, Aviral Kumar, Yevgen Chebotar, Karol Hausman, Sergey Levine, and Chelsea Finn. Conservative data sharing for multi-task offline reinforcement learning. Advances in Neural Information Processing Systems, 34:11501 11516, 2021a.
Tianhe Yu, Aviral Kumar, Rafael Rafailov, Aravind Rajeswaran, Sergey Levine, and Chelsea Finn. Combo: Conservative offline model-based policy optimization. Advances in neural information processing systems, 34:28954 21228954-28667, 2021b.
Tianhe Yu, Aviral Kumar, Yevgen Chebotar, Karol Hausman, Chelsea Finn, and Sergey Levine. How to leverage unlabeled data in offline reinforcement learning. In International Conference on Machine Learning, pp. 25611 25635. PMLR, 2022.
Andrea Zanette, David Brandfonbrener, Emma Brunskill, Matteo Pirotta, and Alessandro Lazaric. Frequentist regret bounds for randomized least-squares value iteration. In International Conference Artificial Intelligence and Stulistics, pp. 1954 1964. PMLR, 2020.
Andrea Zanette, Ching-An Cheng, and Alckh Agarwal. Cautiously optimistic policy optimization and exploration with linear function approximation. In Conference Learning Theory, pp. 4473 4525. PMLR, 2021.
15

---

Published in Transactions on Machine Learning Research (04/2025)
A Pessimistic Value Iteration
The Possimistic Value Iteration (Jin et al. 2021 (PEVI) algorithm constructs an estimated Bellman operator
B, based on the dataset D so that B, A++ S + R is an estimated value function based on D. Define an uncertainty quantifier with the confidence parameter & E (0, 1) as follows.
V. h+1 S A I approximates B, VP k+11 S A - R. Here
Definition A.1 (f-Uncertainty Quantifier). We say (T'l (T': :8 x A A R) is E-uncertainty quantifier if the event
(BA (it1) (s,a)-(1B3) E 3 {
- Vpt (B, (s &IN(s,a), V(s,a) A. e [H]]
(13)
satisfics P(E)21-5
Algorithm 2 Pessimistic Value Iteration (PEVI): General MDP
Input: Dataset D ((8%) 07 7. 0.
K.H.
Initialization: Set 1
for step h 11 - ,,...,, do
4: Construct [B, 1/1 (.5)) and (a().) based on D.
5: Set (-((,)) + Vn+11 (.,)) - -n,(t))
6: Set (?((;)) f- min (QP( (,, - 13
7: Set 7t | s) + arg max
(s, ( 18))
Set (-) +- (ØR(()) (3.)), ax (.(((11)) 11))
9: end for
10: Output: Pess(D) = { At 3 11 { (VP) Jh=1"
By equation 13
Гa quantifies the uncertainty, which allows us to develop the meta-algorithm in Algorithm Now we introduce the PEVT with the data splitting and the kernel setting. Suppose we have the dataset.
2
Algorithm PEVI: Kernel Approximation with Data Split
K.H Input: Dataset D {s1 ah. T and parameter B and X.
Data split: Randomly split dataset D into disjoint and equally sub-datasots (DA, 1
3: Initialization: Set DDD=+1" (+) + 0. #+1 4: for step h= , do
5: Compute the Gram matrix Th function h and response vector yh defined in equation 17 and
18). respoctively.
Set l(n((,)) 3-B- B. 1-121/22 1/2 (k(().)))) - k (T.)T (K + +11) 2 2.. 1/2
Set 2. (.,-) Pi (T,,) (K +11) y/ In(l..).
8: Set PPau (.,.) f- min Q (..t H - h
(QRaill (s, ( (8))
Set (- 5) -- arg maXa:
10: Set 1/ Pm:H (.) + (Q ).+((-1)))
11: end for
12: Output: Pess(D) (D) = |
Dain H (V.
D (8%, a/., (1)r()) HNN K. we partition the dataset D into H disjoint and equally sub-datasets (Dx 1 and
16

---

Published in Transactions on Machine Learning Research (04/2025)
DAl No N/H for all h [H]. Consider the index set I, {Nu (h - + Nu h}
[Th,1,--- "Th,"" } such that Dn {(5 of rier. To simplify notation, let Dh.1f U Dj for h E [H] Note that DA:Hf if h H. Then, we construct the pessimistic value iterations (Jin al. 2021 with
BR 14-11 Ih and DP Note that DD O. Define the empirical mean squared Bellman error (MSBE) as
H+1
Ma = E
1 ( PaI (sh+1) (6h. (5) h+1
2
(14)
TEIh
each step h [M] and for all f E Hk. Corresponding, we set
Bn Da h+1
(z) = fr(:;)
where fn. arg argmin Ma) A A-I1fl JEHz
(15)
for À > 0. Moreover, we construct TA via
(=(2) B- 1/2 ((
kn
(KR- + 21) -1 A/ (2)
1/2
(16)
where > scaling parameter. Note that it a bonus function defined (Yang et al. it is clearly a & quantifier. Here, the Gram matrix K,P E RRNuxNn and the function ki
2020 and that
+ R Nu as
lo (2) Th.1 ,2)
K
= 1o 2h/ (3h12²7)
k 2h (2)
E ERNH,
(17)
ThNNH x)
nn
for T, In. The entry of yh E R NN corresponding to E In is
[un], = r% +
DD (sh+1).
(18)
h+1
We construct the pessimistic value iteration with kernel approximation with kernel by
h 1. (z) BB V. (2) - [T,(2),
Q Patii 1 (z) = min
Q Patil (2), H - h
R.(. 8) arg max
Q Phi1i 11:8
1s)
T
D
1:11 (s)
Q
Da+nin (s,
h
The algorithm summarizes the entire PEVI algorithm with data splitting.
B Proof of Main Result
B.1 Proof of Proposition 4.1
We present generalization of (Abbasi- Yadkori et al. 2011 (Theorem 1). Its proof closely mirrors that of the special case where H4 has linear kernel. To simplify notation, denote the labeled dataset N,. D, = (8%, 0% 1 Subsequently, we address the following problem:
Σ (10, (sh. ai) - -rī)² -1110112
02 E arg min BEP
(19)
17

---

Published in Transactions on Machine Learning Research (04/2025)
Here, 0(sh. is column vector for all h E [H] and t > 0. The solution for the above equation T
is that 09 = (())))))))))) (T;) where Ai. = (o,)) o6 + vln, 2 = (o (s), a))) ,.. , (s) mt) [
and V I .r]- Denote Fy = "., , and Ky = 4 ( We then determine the upper bound with
10% Oallag. We write
0 = ((9))
T 0/ + (0x)) + E.)
= ((0)) Top, + =lx)) 0/ + +1nn - vIn)0% + (0)) E -(0%) 0% + +//////)))))))))))))) ((1) Ej + 0" =((()) 0 + +vlx) 0 - (AA)) TE), Ex + +0 - -
(20)
That implies
x. NT x T6 = 30==xTAA)) -=AA) E7. ux T (A1))- 0
(21)
= (xx, (0%) EB) (1))) - v(x,0" ((
where (x, (/ -'y and Aj is positive dcfinite, then (A1))-1/2 S y-1/2, Using Cauchy-Schwarz inequality, we get
=A(()))) x 0%
10 S [[]l( BXlKA
(((0))))((((0))")E0))=0==>=> 1/10% (+)))))))
(22)
< (101(1)))-((((00))) - +011001114))
where the second inequality uses the fact that
10%llag)- ((.))) 1m2.
1
S
10 S V He
vv
Next, show that with probability at least 1 1-6
[(0%) EAll(Ag) S H² log del [V] + Ki] + 2H log(1/0).
(23)
Following Valko et al. 2013). we will use the following identities:
((09) o + wIH) (0%) (0%) (#)())) + vI)
A (Tb)) =(+%) (K) + +UT)
(0)) (Kr + vl) -1= = =(A T(
With the basic operation, we get
[1(*1) T E 1P = (EA) (0 Eg (EE) (1,) (KF + vl) -1 Ei
(24)
((E)) (K) + +I)= E
Setting v 1 + 17, for some 77 > O, we have
(K) + 1) [ (1 n)) -1- (K)++ + 7) [T+ (K) + 1)]
(25)
= [KS + 1) 1|
which implies
(E T Ky (KA + +vII= -1 "E < (E T (K. + 1) (K) + (1+ E
(26)
= (E T
[kt + + = E
18

---

Published in Transactions on Machine Learning Research (04/2025)
with o² 1, we obtain the following result: with probability of at least 1 - 8, the given condition holds simultaneously for all 1 1
Applying Lemma C.1
(EE) [K) + n. 1)- + r] | Fj log det [1 + 1)) - K%] + (1gg)))),
for any 1j > and (0, 1). Combine equation 24 and 26 for any 0, we gel.
I1(%)) Eillag)- Vlog log det [1 7) I ++ K
(27)
8²
with probability at least 1 - 5. Therefore, combine the equation (2 and 27
one also has
1x 0 - -x S [|allka))= (V (V10g log det [11 + 11) I Ky
(28)
82
for all t 2 0. Plugging in x == (0,, 0%), we get
100% 0illag I (0) - 0 1y00 log del [11 + 1))
I + K%
+ /
(29)
82
Now, 10 -%%lla = (0 o dividing both sides by 110 0% lla; get
10, - l7llag 1 (v log det (1 11) I+ K
+ vvi10% (lxw)
(30)
82
Finally, we fix t = N2 and let 0y =6,, Ar = Ab and Kb = kh where D₁ is offline labeled dataset, we get
det [VI [ + KP
11ō 0fllAn I ve110%114 +1 log
(31)
82
Furthermore, observed that det (vI+ kT. det (I (I+V-IK3) dot(vI). Thus, we have
log (det (TT + (T++K) )) = log ddet Clot(I+ve (I+0**17)) + N₁ logu S 2G(N), +N - 1),, where v > 1. Thus, set v = 1 + 1/N1, we have
(32)
1 - S /21l07lxa + + 12G(M,,++1Nb) + 1 log 82
(33)
B.2 Proof of Theorem
The proof of Theorem 4.3 and the related supporting lemmas are given in this part. Recall that we denote the labeled dataset D1, unlabeled dataset Dé and D {(8%, 07 7he (8% ())) N. which is a combination of labeled datasct D, and unlabeled datasct DĀ and = N₁ N2. We partition dataset D into H disjoint and equally sized sub dataset {D where [D]] Nи = N/H. Let I, (N (h (h-1) 1) + 1,..., NH h}
[TH,1,... ... -h,NNH } satisfy 2/ = ((5 ah, PA (5% a))))rr Denote (V, (D, J as the estimated value function constructed by PEVI. These estimations are based on datasets DroH, where rewards have been relabeled using the parameter 0 = (0r | Furthermore, let. Vi be the value function associated with policy and the estimated reward function with parameter 0. From equation in Algorithm [ for all E [H], we have
D Thhn (so) V.Phu (so), vOn Co))).
(34)
19

---

Published in Transactions on Machine Learning Research (04/2025)
where so is an unique initial state and 0 = {0m is the pessimistic estimation of 9.
Let E be the event 0% (o), then we have P(&)) 2 1 from Proposition 4.1
Denote (VA WVR Pess(D) from algorithm 3
Let & be the event where the following inequality holds for
each dataset Dj, and
Ba BA
PhttiN ) (8.a)-
Ditin h+1
) (s,a) s [T((s,)),(ss,d) ES A
Bn
(35)
h-1
where a)) = B)|ø(s,a)]
:0 and
(A
C2 H v dlo (N/5)
d-finite spectrum, d-cxponential decay,
B
C2 H V. flog 1/0) 1+1/a
(36)
C2 N 2(aim H adim
(lg((N/8) d-polynomial docay,
where C > O does not depend on N1 nor H and C2 > O does not depend on N nor H. Then, apply Lemma B.3 such that P(E2)= 2 1
Condition on & n E2, we have
VT .0' (so) Vi (50) VT 0' (s0) 1 Pi (5o) + 1.P1i1(
-/=.0' (sn)
S ViTh (so) 1.Diin (so)
VIT "r (5o) VI (30) + +V7 (7''0(s)) VP (50) + (/Pir(so) - -ipiir (30)
S VT (5b) Vi ((5)) + VV, 10 ((su) - 1.p.. "(o))(so)
VIT 0' (so) V 8 (30) + V/"" 0 (ss) V2" :0 (30) + 1/" V/"", ((0) -1p9.11 (so)
(37)
< VTth (so) Vi 00 (ss) + 1 0 (su) V1" 1 (s0)
+ V1" (so) -ipi.. (su)
H
< 2
[1o(5n, (8)
an))a,
1/81 = 80
h=1
"
[ an)ll
+ 2B
Em
[1 80
(A
for so is the unique initial state and (6) is
N. St + /o,- - d- log N1 + log t
d-finite spectrum, d-exponential decay,
(x(
S + VC (log N1) "+ + log( (
H Va (N1) d+1 4m (1) + log( (
d- d-polynomial decay.
Note that the first inequality follows Lemma 34 and the last incquality follows Lemma
B.
while the second inequality follows directly from equation
B.2 and Theorem B.4
Lemma B.l. Under the event Ez, we have
Pf (so) -V.-.0" (su) S 0,
where 8o is the unique initial state.
20

---

Published in Transactions on Machine Learning Research (04/2025)
Vi piiin (so) and VT vit:0(s0))
Proof. For simplicity, denote (so(s)) x' = and (2P) Th=1 constructed by PEVI (Algorithm 3 we have
(so). By Lemma C.3 with
H
(so) VI (5o) = Σ 3
@h
(sh, an)
(Ba (sh, an) 81 = 80]
h=1
Recall that QR a) is defined in line 6 in Algorithm implies (s, = 0. Then
3
For all h E [H] and all (s,a) A. Q7 (s, a) <0,
(x, B,, h+t (8, = - -BB, (B, (2t11 (8, a) < <0,
as Th E 1]. Otherwise, 07 a) 2 0, we have
(s) BB vitta) (s, Q2 - (Ba hh+1 (s,a)
= [Bx (ht1) ) (s. - (Ba (B ( (s.a) - ax( $o.
Finally, we have
(50 ((T(5)) s
(38)
Lemma B.2. For policy n², and offline dataset D ((5 oh r and any reward function parameter On E C,) we have
IVT 0 (so) VT ((0)) S Σ Br( [[60(5), [I an)lkag)-1 |s so
(39)
where So is the unique initial state and (8) defined equation holds, then Br) can be wrillen as
Moreover, suppose Assumption
3.1
8 + Vi log N + log( (2))
d-finile spectrum,
(8)
S + Va- (log N) + + log( )z2
d- d-enponential decay,
(40)
1+ & + /c-- (N) s+m log((N) + log (2)
d-polynomial decoy.
Proof. From the definition, we have
1 (s, a) - 50h (s, a)l = [6s,, a) To, - a) 0y
110 Gulla (ll((s
(41)
BB((d) as) (AP)
Then, we have
1 0 (so)
-V,
-V=""((0))
Ex-
Th 1 (s,a) - ( 81 = so
h=1
112 (s, a) -..h (s) |1 =0
E
(42)
(n) (1)())))-((s))))))) an) 181 80
(o)
(O)
[10(shaa))l(app) = 80
R=1
21

---

Published in Transactions on Machine Learning Research (04/2025)
Recall that (6( vDS
1 z2 log + (2
defined in equation 7 Setting v = 1+1/N and applying
Lemma C.2
we obtain
1 + 1 18+1 v Vi d log N log( (a)
d-finite spectrum,
(k(6)
V 8 + v C (log / log( (og()=))
d-exponential decay,
(43)
No
N + C1 (N) m=L
logg(N) + log( (z)
d-polynomial decay,
for some sufficient large C1 and C1 is an absolute constant that does not depend N1 H.
Lemma B.3. Suppose Assumplion 3.2 and 3.1 hold, with dataset D {(8% o (1) 1 and B satisfies
H,N hi we set A 1 1/N
2(1 + N R 8G 1/N) (
(44)
in Algorithmm 3 Then (8) = B [lo(s, a)ll - is a E-quantifier where Dr is defined in Theorem 4.3
That is, for dalaset D, the following inequality holds,
(BA DDnan h+1
) (8,
( DaDun ) (s,a) & <Ta(s, V(s,a) E A A [M]
BA (BAV h+1
(45)
with P(E2) 2 1- - E, where &g is defined in equation 35
In particular, B is given by d-finite spectrum, d- d-exponential decay, d d-polynomial decay,
C.H Vdlog (N/E)
B =
C H V (log (lggN/E) +1/4
(46)
C. Natttm H' 2(dtm)
log (//E)
for some absolute constant C that does not depend on N nor H.
Proof. We present the offline reinforcement setting of (Yang et al 2020) and combine the data split skill
from (ii et al. 2021 (Rashidincjad et al. 2021 J. Recall that we partition datasct 'D into H disjoint and
equally sized sub dataset {Dr) where [Dul Nn N/H. Let I, (Nr (h - 1) + 1,...; Nu h)
{Th..."" Th,NH satisfy Dr {(5), agr FrEE Denote the operator Dh H2 + RN and AP Hr + H..
(2
l (1)
s Ph
Dh A = x 11 + &
Dr.
(47)
Nn.N T
N
2
For notation simplicity, let K₁ KP,
Kn (2)
Da (2), and Ao = AR.. For h E [H), the solution fa of the
kernel ridge regression in equation (15) is that
fa()=
Σ
[an, k(2 1% Ch
(48)
TEIn
where σi
(KΛ + A 1) Note that both matrix T + A and TT + X Ix are positive definite, following Valko et al. 2013), we have
Φ DT
(0) th + x- A-IH) TT.
(49)
Then, the fitted value function B, P. is that
[n(=)) (Ph, k(,, 2),, = kn(2) oi..
Tan.
(50)
22

---

Published in Transactions on Machine Learning Research (04/2025)
Furthermore, in combination with the equation
49
(2(2) can be written k2,2)) = Lnd(2), we have
6(2) , AnØ(z)
A [ 4n [He x1z)
An " 12O(2)) + AA 66())
(51)
= (KA + + x +
0 6(2)
2 + 1) -z) +A ((2),
where the forth equality follows equation 49
Recall that @ " (z) = min min (Q PiIN (
- h 13+
min miinkaa22 (2) Cn -T((),, H - h 11 in Algorithm
3 Since Q Pa-1. E [0, H] for all h E [H], by Assumption
N++
3.2 have BA 1 O- i.e.,
Bn B DRLLH
Roll. There exists fn Q such that fn B,
Pa
h+1
141
P
and B, 1 1: (z) = kn, 2))H4. ==(= Sh by the feature representation of RKHS. For any h E [H]:
h+1
Bi DDNi 11) ) (s..a) B Di (s.
Fa(s,a) a(s,a)T Ful
(52)
[na(2) [Kn (Ka+ +.. (). 1)- KiT (=) A. 11 Xx(=)) A AT
< [KA(2) (Kn + 1---))>>n (yn -
-nffal + (ΔO()) A77 fial
$ (A) + (B),
where the second equality follows equation incquality,
51 Next, we bound (A) and (B) separately. By Sauchy-Schwarl
(B) = Ab(2)) T A l/l A(A (M=))
SA. ||T d(2) Ne -I.fm 11
= x. |7~ A, 1/2 x1=))
-Ilallm
(53)
Hu
S Roll X1/2. |A, o(z)
Hh
RRH 21/2 [|((=))l
Furthermore, yh. is defined in equation
18 and Section
3.1 the 7-th entry of (yn. Pn) can be written as
[un], [Bafh]=
r7. + Dinuin
(sh+1) - (
= =r + V (sh+1) - BB h+1 (8h, a%)
(54)
D- (5h+1) PA P D.Puii (sh, al) + ch-
With equation 44 and (2) Φn)(2), (A) can be written as
(A) (x) T (K₁ + 1) 11 (yh Dnff
()(s,)) [T] (Kn + + 1). (un &nJm)
(8(8,a)T A/* T (y - -tffal
(A,,
((ss Σ o (8h, o/))
TyTuuin (5h+1) - -Ph h+1
V
D.D
(5h a7) + t
(55)
TeT,
< $10(s, (lssa)))la?
Σ rEZn
(shh a/)
[ (sh+1) IP,,
D.
(8h, a/) + +
h+1
23

---

Published in Transactions on Machine Learning Research (04/2025)
where the last incquality uses Cauchy-Schwarz inequality. For h E H 1], we define the filtration
F =
where a() the o-algebra generated by the set of random variables. Let
DDDann (sh+1) + 6 - Pa Pa Dutii
E, = h+1
h+1 (sh 0))
is adapted to the filtration {Fu+1 h==
H-1
Then
E
P (sh+1) + c% h+1
Fh
E3
Durii h+1
(sh+1) + + 9h =8%, an a/
= Pn h+1
Phti (s%,
Thus, we have E [
Fi]
Applying Lemma C.1 to 6, 5% and 0² 2H2
D 1. (sh+1) - PA V 1: (5% a7,) E H H],
(56)
and 67, is 1-sub Gaussian noise, for any 1) and 0, it holds probability least 1 E/H that
ER (Kn + 11 1)
En.
(57)
2112. log det [[1 n) Ki] 4H² log(H/EE.
Jh.1 F/
where En=
Using the equation (57), we gel
TH b
Σ TEZ
+ (87 an) c%
E dr. (0) 24 + 11x) #T7 En
A,
(58)
E DT ( +) En.
-T Kn (Kn + X. 1)- Fn.
For A == 1 1 and 17 > 0, we have
Eg Kn (Kn + A 1)
En ET Kn. (Kn. + (1 1)= En.
- ET (Kn + 1 1) (Kn + (1 + 11+1 11.1))1 1)- En
(59)
= =E (Kn + + 1) 1)= +1] En.
where the first. equality follows the fact.
(K + 17 1) 1)
+ 1)--
= (Kr + T) (Kr + +n)) - For any
fixed g >> O, combining equation
57
58
and
19 we gel
Σ Φ (8h a c
2H log [A 1+ Ka] 4H2 .lg (og(H)))
(60)
holds simultaneously for all h E [H] with probability at least 1 - E. Clearly, A- + Kr (A (1 + Kn/A), then
log det (A + Ks)) = NH log A + log det (1 + Kn/X)
(61)
$ (A - 1) + log det (T + K,/2),
24

---

Published in Transactions on Machine Learning Research (04/2025)
where Na
I N/H. Hence, for any and À 1,
Σ TEZA
① (shs ah) Eh
< 2112 log det /1 + KA/A HH 1)++ 412 log(H/())
(62)
Ax
holds simultaneously for all h [H] with probability at least - &. Finally, combine equation 522
53
55 and 62) and take = 1 No we get
(
(Ba
Da- h+1
(z) BB V. Pa-L1H (2) h+1
< <11Ø{=)lAa)
ROH VX+
Σ
Φ (8h ah) 6%
TEZx
2
1/2
s <|0(()]|A,
2112 11 +2
Σ
Φ (5h E
(63)
TEZ
< <|[0()]|A>
22R H + 8H2 G(N/H, + + 1) 1/2
1/2
< [|0(=)lA
2(1 + R H2 + 8HP G(N/H, 14 + 2H + 8H2 1og(HH53
- B- B- (l = I'n(2,, Vz E
where the second inequality follows from Ve + V +2 Thus, (Taheej a f-uncertainty quantifier. To give explicit expressions for B, we distinguish three cases according to the spectrum of k.
Case I (d-finite spectrum): By Lemina
have G(N/H, 1/N) S C. dlog(N/H), where Ca.
is absolute constant that depends on m, and d. Then, 8 equals to
1 2(1 + _ RR + 8112 1//)H, + 2H + 8112 (og(H/E) - 4R2 11 + 8H2 Cs dlog(N/H)+ 2H + 8H (og(H/E)
(64)
C ....log(///) (NEE)
for sufficient large C' > 0. Hence, we take B=C- - ld (N/E).
Case II (d-cxponential decay): By Lemma C.2
get
G(N/H, s C (log(N/H)))*1/
(65)
where Cie is absolute constant that only depends m and d. Then, B² equals to
2(1 + N R2 + +8 1(N/ + 21 8H2 log(H/E)
< 42 + 8H² C. (lo((//H))) + 22 + 8 log(HHEE)
$ 0² 2² H² (10
(66)
S 22 logg
$ 0² 112 [log 1-1/
for sufficient large C > 0. Hence, we take B C. H. / (log 2/1
25

---

Published in Transactions on Machine Learning Research (04/2025)
Case III: (d-polynomial decay) By Lemma
C.2 get
G(N/H,1 + 1/N) - C. (N/H) mt1
(gg(N/H),
(67)
where Cj absolute constant that only depends on m and d. Then, B² equals to
2(1 + N Ro + 8H2 G(N/H, 1/N) + 2H + 8H loog H/E)
< 4R2 11 + 8112 C. (N/H) mii
(o/((/H))))))) + 2H- 8H2 log (H/E)
(68)
C² H2 H2--+m m+1 N d+m Tog( N/H) + log ())
s C H
log(N/E)))
for sulficient large C 0. Thus, suffices to choose B C N mm H
v Mog(NN/))
Theorem B.4. Under Assumption 3.2 and 3.1 with probability at least. 1 - E, it holds that
we set X = 1+ 1/N and B is defined as equation
46
Then
H
(p-0((0)) - 1iPim (5o) S 2B
Ex
[|o(sh, an)ll
~ (A, ")
81 = 80
(69)
Proof. Recall that the E-quantifier satisfies the following inequality with probability at least 1 - &:
BA
V. h+1
Di (s,a) BA
Piih h+1
) (s. s (s(s,)),
(70)
as the policy such that 1/ Di (s) =
for all a) E S A, E [H]. Define
{ 1H
o Phi (s, m. 8)
Phann ) (s. - ofhn (s, Apply-
For simplicity, we denote da = BB
h+1
A ing Lemma C.3 with π = î., and '' n², we have
K0RR" (su. (-1 - - (-
1.Dim (so) Vi V.T (50)
Σ Ex
(-18h)
[1 80
h=1
Hf
Exg
Qh Phae (sn, an) - BA D. W++
(sn, an)
111 = 50
h=1
(71)
H
{
(0 (0this () 5, (s)))) - -mh( (- (11sh)
Σ Ex
81 8p
h=1
Exs [8n (s) |81 so],
where E,, is taken with respect to the trajectory generated by π². Since è is greedy with respect to Q Phan then
h =
VT (5o) - -v,0i.. (so)
Ex (sn 1 |1 sol
h=1
Ex K0RRt
Phu (sn5 .,, o (: (h)) Fx (-1 (-1sh)
|s
80
(72)
1=1
A
H
<
Ex (8h, an) I 81 = =so]-
1=1
26

---

Published in Transactions on Machine Learning Research (04/2025)
Recall that the construction of Q a in Line 5 in Algorithm 2 For all h E [H] and all (s.a) E S x A, we have
bill (s, a) BB D
(s,0) (n(s,a)
h+l
(73)
Pitt S 1 h+1
(s,0) S 1 +
where the first incquality follows the definition of (s a) and the second incquality follows that ra E [0.
and Paati (s,a) S h. Then, we have h+1
D Phat (8,0) = max @ (1,)0) 2 (s, (8,
Qn
(74)
Then, (s, a) be written
DD+1 (s, = BA h+1
(s, Q (s,a)
B h+1
D
(s,a) DD.A (s,
(75)
Pu4t h+1
BB Di h+1
B,
(8,
(s. + +Nn(s, S (s,
where the inequality follows line 4 in Algorithm equation 722 and equation
(s, a). Combine Lemma Hence we have ōn(s, 2
B.3
75
we get
H
1 (so) - 1.Pi. (so) I 2
Σ
E, [T an) 81 = sul
hm1
(76)
< 2B
Ex
||0(sh, an)ll
81 = 80
h=1
(),1)-1
where B satisfies equation
44
B.3 Proof of Proposition 4.5
Denote Ad A A/ A Di and K₁ D'b Note that A is a self-adjoint operator, then
M₁ = 11/22 (IH. + -==11=(((00)))))) A 1/2) A!!2
(77)
We take log det on both sides with the equation
77 then
log det (AA, log det (An) + log det (InLe +A,, 1/2 ((2)((2) (A,,
(78)
log det (AA) + log (1 662) (((2)),,]] A
Note that det (AA) det (AI + K₁), and det (AA) det (AI K²)) for A 2 because 6(2)TA7 ((2) < 1, we have
(b2) A (x)) < 2 log (1 + <(2) A (b)))
2 [log det. (M,) log det (Aa))
2 [log det (I K2/A\ log det (I + KR/A)]
Moreover, by equation
2 we have
(() A ((2) 2. [log det (T K2/A) det det Kn/A)]-
(79)
27

---

Published in Transactions on Machine Learning Research (04/2025)
B.4 Proof of Corollary 4.8
The proof is inspired from [Jin et al. 2021 Duan et al. 2020 Recall that we denote De N.H. {(5% 0% & (5h (7))),, which is a combination of labeled dataset D1 and unlabeled dataset D We
partition dataset D into H disjoint and equally sized sub dataset {Di where [D]] Nu N/H. Let
In (NH (h- 1) + I.................. No h = (Th,1:"" ; .hh.Nu satisty Di {(8h % 7hh (5% af))r Define
A = o 6 a o (5% añ) En. Zn = Σ A
(80)
TEI
where Σn = Es O (sh, an) (sh: as)
| for all h [H]. Clearly, Ea [A]] from equation (80). Note that E, is taken with respect to the trajectory induced by the fixed behavior policy क in the underlying MDP, and the set {Af]eez, is i.dd. and centered for all E [H].
As shown in Section 3.3 the feature mapping Φ : Z satisfies
6(2)
Σ j=1
Jo by (2) 13 Σ (5()) (Vo, v,)
(81)
Let be any positive integer and let II, H H denote the projection onto the subspace spanned by jem) i.e., IT, [d))] = ビ Jj 1/5(2)) v/..
For d-ninite Spectrum case, consider the case where of for all j > d. Then, 6(2) IalØ(2)] for any E 2. That is, A7, can be written as
A = WI - Who Zn = Σ AT= Σ
W
Wh.
(82)
TEZn
TEI
where Wg. = +(2))((27)) as a d x d matrix, and WA = Ex ((()))(Z)) By the boundness of kernel supzez k(z,z) S 1), we have [}(()) < 1, E 2. By Jensen's 's inequality, we have
and (sh, an))
and 71100]
p s Ex
Similarly, for all h e [H] and all e In, as it holds that
|A S |WPllup + I|Wnllop 2
have
E 12, Zn llop
NH B
(AR) Añ
7 op
$ N₂
E*
A5, (AA)
4NH.
Similarly, we have
(A4)] A5 op < [[A
T
11
11p S 4 and E 1 Zz 1lap
S 4NH.
Applying Lemma C.4 for Zn defined in equation
80) for any fixed h E [H] and any / 2 0, we have
P (IZalllop >1)= =P
Σ FE
A
>1
< 2d exp (- (- 4NH + 21/3
2d
12/2
op
For all 5 E (0,1), we sct 1= / 10 log( (d)) for sufficiently large Nμ 2 5 5log we obtain 7 llop I vnnNn log(4dH/8) holds with probability at least. 8/2H.
28

---

Published in Transactions on Machine Learning Research (04/2025)
Moreover, Zn defined in equation 80
can be written
Zn
Σ TEZh
o NH En = (An - 1) - -H En.
(83)
Recall that there exist posilive constant Cmin such that infi f1xx =1 (J, Ennd'Ha 2 Cmin- For sufficiently large NH 2 4Ca log (6) we have
inf (f, An fi
Zn (Er NH
A 1 fizee
inf (f,
+ En +
M1b, =1 NH
IIS hug =1
NH
inf
(f, Znnima +
inf I1lll =1
(f, Enfr
Nu 1
(84)
1
Zz llop 2 Cmin V
log (4HG 1)16)
Cmin
Gmin
Nh
Nh
Hence, it holds that
2
| S No Cmin
(85)
for all h E [H. This implics that
| $ (s, s al0(s S //N
(86)
where d' = 2 and using the fact that (10(s,))lm, S for all (8, E S A.
We define the event
E = {IA ( o(s a)). s <c/VNH Nu for all (s.a) S x A and all h [H]]
By equation 86 we have P(E1)= 2 1 5/2 for No
40² 3
log (4dH/5). Recall that for d-finite spectrum case,
we have
(a(6) = 1+ N1 St V G1 d log N1 + log( 82 )
(87)
B C= H Vdlog (N/6).
Use big tilde O notation, they can be written as
(6) O(Va),
(88)
B = O(Ha))
Combining the result in Theorem 4.3 and equation
188 with d= -8/4, we have
H
SubOpt(#; 8) < 2
(5)
[1o an an)l( 181 81 =
h=1
H
+ 2B
Ey-
((o(s))a)) an)ll
81
(89)
(1, (1
h=1
< (,)
d dd/N N1 + 2B H d Nu
d Ö(H Õ(H²
d
N
V Nh
where the last equality follows from the fact that N N/H and N N₁ + N₂ for all [M].
29

---

Published in Transactions on Machine Learning Research (04/2025)
C Sufficient Lemma
(Chowdhury & Gopalan 2017 ). Let H be on RKHS defined over X S Ra with kernel function k(.,-) : x x R. Let {Ir| C & be discrete time stochastic process that is adapted to the filtration (Fi)t=o- Let {<r) be a real-valued stochastic process such that (i) E is F,- measuraall and (ii) E is zero-mean and Sub-Gauussian conditioning on F--1, i.e,,
Lemma C.1 (Concentration of Self--Normllize Processes in RKHS
E [ | 1P20 Y.ER.
Ber F+-1]= =0,
Moreover, for any 1. 2 2, let E. (e1 (el.-..,, (0-) RC-1 and K, E (((--1)((--1) be the Gram matrix of {ar) Then for any ni > O and any d (0,1), with probability at least 6, it holds simcaltaneously for all t 2 that
El (K₁ + .) + 1] E, S o². log det (1+ I K,] 20 log(1/5).
Proof. Please refer to Theorem in (Chowdhury & Gopalan 2017
Lemma C.2 (Lemma D.5 in (Yang al., 2020)). Let Z be a compact subset of Ba and k the RKHS kernel of H. We assume & is bounded kernel so that supsez k(2,2) S 1, and k is continuously differentiable Z x Z. Moreover, let Th be the integral operalor induced by l and the Lebesgue measure Z, such that [z) = fo lo (2, 2²) (z')dz', e (2)... Let {azt be the con-increasing sequence of eigenvalues of Tk. Recall the definition of marimal information gain in equation salisfies one of the following eigenvalue decay condilions:
be
We assume {oz},zı
--finite spectrum: o, =0 for all j > 7, where y is a posilive inleger.
y-exponential decay: there erists some constants C1, C2 > 0 such that o, S C1 exp (-C2 j7) for all 2 1, where > 0 is a positive constant.
7-polynomial decoy: there exists some constants C1 > 0, E (0,1/2) and Cs > such that oj S
G.-j- and sup:ez (,(()) S Cw for all 2 1, where 7 >
Suppose X E [et, for absolute constants e2, Then have 02.
C. log N
7-finite spectrum, ?- expponenniall decay, 7-polymomial decay,
G(N,A)
C (log 2)
C. N(d+1/66))) log N
where C is absolute constant that only depends on d, C1 C2, C,C.C. en and c2-
Proof. Please refer to Lemma D.5 in Yang et al. 2020 for detailed proof.
Lemma C.3 (Extended Value Difference (Cai et al. 2020 Let π = { and n' { any " two policies and let { h=n be any estimated Q Q-functions. For all h E [H], we define the estimated value function Vn S + R by setting Vn(x)= = (@x Tn(. 12)( for all x E S. For all x E S, we have
- (x) 2h=1 Exi (Qxx (Shy :), n (- (1)))) Thh ( (1888))))))) (s))an) an) (Is, Vnti)) (oh, ap) x
81
H. Σn Eny @2 (sn:
where Eyr is taken with respect to the trajectory generated by n', while Bd is the Bellman operator defined in
Section 9.1
30

---

Published in Transactions on Machine Learning Research (04/2025)
Proof. Fix h [H]. Denote that = Q; - -B,V1+1 For all i e [h, H] and S, have
(s:)) VI" (8:) 8/1
E
E
(066)) Te (: 8:)) Q7 (sts T (x
(-(8)))) (1188)) st) (11 s.) + (²) (5t, QF (5t1 ..4 (- (11s))
8h =
sh
(0: (st) 1. (-1s)) 7| (- s.)) | = s)
+ E
( 4 (86.) + Vit1 (8t, (r: (8s, P, P.V (st. :)) Th. (: sil)
s/ =
(90)
E
( (s4s) ); ,
85) - n.{ 8.)
88 = 5) + Er [6x (8i, ai) sp = s)
P. (V++1 Vit1] (8t, a:) sh =
+ Exr
E
(0x (8i,) 1) , 8:) - m|| (- 8:)
8h = 8 + Er [6s (8t, ai) | 8h = s)
+ Ey [i+ (81+1) - ViL ($:+1) Sh = $
where P. is the transition operator defined in Section 3.1 Rewrite equation (90). we have
Eny (s:) - V.¹ (s:) sh = =s] E
V ($(+1) Vi+1 ($(+1) sn =
(91)
E, ((: (81, ) (: s:) - a (- s:)) 8h =}] + B (1s (si, a;) | |hh 8).
Taking E on equation
91 then
VA - V (s)
Σ E,
(Q: (z (.1
T/( (ss)) sn
kmh
(92)
H
B Qn (Sis (si, ai) - B, Di (si, a;) 8h =
i=
letting h = 1 completes the proof.
Lemma C.4 (Matrix Bernstein Inequality (Tropp et al. 2015 ). Suppose that {Au]i=t are independent
and centered random matrices in Red xd2, that is, [AA 0 for all &s [n]. Also, suppose that such random
malrices are uniformly upper bounded in the malria operator norm, that is, ||Ax lop L for all [n]. Let
Z Ek= Aş and
2 = max {| 22
12 ol | [B[22TZ [2_2]11pp) max Σ
A A
Σ
For all t 1 0, we have
12/2
P (1l 1) < (di d2) exp v(2) + I.33
Proof. See Tropp al.
2015 Theorem 1.6.2) for detailed proof.
31


Reviews:
[{"review_id": "9zPDrRLEZf", "reviewer": "Reviewer_Qc77", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strength \n1. On the technical part, the paper clearly discussed the connection to previous work, for example, the usage of each technique is introduced in which previous paper, the assumption of the kernel function approximation and the eigenvalue decay assumption and their connection to the previous papers, so that the reader can better contextualize the results. \n2. The paper is technically sound, with the generalization from linear mdp to kernel function approximation. \n3. The paper proposes a sharper concentration of kernel ridge regression (proposition 4.1) for the estimation of the learned reward function, which shares the similar spirit of the previous sharp concentration on the linear ridge regression studied for linear-ucb. But I am a little bit skeptical that this is never proved in the kernel bandit setting.\n\n## Weakness \nOverall I am a little bit doubtful about the list of contributions that the authors claimed: \n1. About the second contribution, focus on finite horizon setting: maybe I am missing something, but what is the technical significance of the finite vs. discounted setting in the proposed algorithm? Or on the other hand, does the previous Hu et al. paper not trivially extend to the finite horizon setting?\n2. The third contribution, the weaker coverage assumption, if I understand correctly, the coverage assumption required by Hu et al. seems only concerns that the offline data cover the optimal policy's traces, instead of a global coverage assumption. However, the proposed coverage assumption 4.8 seems to require certain global coverage assumption in the sense that it needs to cover all direction in the RKHS that we care about? \n3. I am also confused about listing the data splitting trick as a contribution, as mentioned in the paper, it is used by previous Xie et al. paper to obtain a sharper rate in offline RL. However, the previous analysis is more careful so that it avoids the $d$ vs. $H$ tradeoff (although it is in the tabular setting but there was no tradeoff), but the current paper seems to just apply the trick naively and maybe caused the suboptimal rate in $H$. I think if this is listed as a contribution, then the analysis needs to be conducted more carefully. \n4. One thing that is not super clear to me is that what is the point of relabeling the labeled offline data after the learned reward function. My guess is that if you do not relabel $D_1$, there is still no difference in the rate? But it would be nice to have a short discussion on this matter. \n5. Finally this is a critique on the unsupervised data sharing method overall: I think the point of the setting is such that we can have a better rate on the labeled offline data. But as far as I know, both the rate of the previous linear mdp paper, or the rate of this paper reduced to the linear mdp setting, are no better than the currently sharpest rate on the canonical offline rl with linear mdp (for example, [1]). Thus unless a sharper analysis is conducted (which I think is very likely), I do not see much contribution of the current works. \n\n### Reference \n[1] Xiong, Wei, et al. \"Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game.\" arXiv preprint arXiv:2205.15512 (2022).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies how to leverage unlabeled data (i.e., only has transition information but does not have reward information) in the offline RL setting, which is practical given more and more video demonstrations and human labeling is expensive. The hope is that, with help from a small amount of labeled data, we can label a large amount of unlabeled data to reduce the amount of labeled data. The previous paper considers linear mdp setting, and they proposed the unsupervised data sharing method where one first fits a reward function on the labeled data and then use it to label the unlabeled data. Compared with the canonical baseline, the requirement on the labeled data is reduced by $O(H \\sqrt{d})$. \n\nThis paper extends the unsupervised data sharing method into the kernel setting and also incorporates it with the data splitting scheme. It archives guarantees both on the d-finite spectrum kernel setting and general kernel setting, and when reduced to linear mdp setting, it compares with the previous method with a $H$ and $d$ tradeoff.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. I think the paper needs to highlight the real contribution of the paper, i.e., what is the new assumption considered, and how do they really compares with the previous literature, and more importantly, what are the new techniques introduced in the paper what would possible benefit the community. From the current writing this is unclear to me. \n2. As the paper only considers the kernel function approximation setting, I think it would be beneficial to move the structure assumption (beginning of section 4.1) and the combined structure and function approximation assumption (assumption 4.3) before the introduction of the analysis and even the algorithm, otherwise it confuses the reading while reading the algorithmic choices. \n3. (I don't think this is necessary but) the authors should put an effort into at least removing the suboptimal $\\sqrt{H}$ introduced by the naive application of the data splitting trick. \n4. nit: $\\mathcal{H}$ is not defined in the abstract; there are some inconsistencies across the paper on different notations of $\\theta$, for example, at the end of section 3.2, in the definition of $D^\\theta_2$, should it be $D^{\\hat{\\theta}}_2$?", "broader_impact_concerns": "n/a", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "OeQzjkMT2d", "reviewer": "Reviewer_HXF3", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: \n\n1. This paper is well-written and easy to follow.\n\n2. The theoretical analysis in this paper is very solid.\n\n3. This paper investigates an important issue, the data utilization problem in offline RL. This paper extends an important method, PDS, to a broader range of scenarios.\n\nWeaknesses: \n\n1. This paper is purely theoretical analysis and lacks some experiments for validation.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper explores the challenges of offline reinforcement learning (RL), which relies on a static dataset for policy learning but typically demands extensive data. The paper addresses the issue of high costs associated with obtaining large labeled datasets, particularly when human labelers are required to provide rewards. The authors emphasize the value of leveraging unlabeled data, which is more cost-effective, in offline RL scenarios where labeled data is either scarce or prohibitively expensive.\n\nThe paper introduces an algorithm that incorporates unlabeled data into offline RL using kernel function approximation and offers theoretical guarantees for its effectiveness. It discusses various conditions related to eigenvalue decay of the Hk matrix, which influence the algorithm's complexity. Overall, the study presents a promising method for capitalizing on the benefits of unlabeled data in offline RL while ensuring theoretical assurances of performance.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. If possible, a few small experiments could be added to validate the theoretical results.\n\n2. I have no additional suggestions for revising this paper. Considering the importance of the research direction, the solid theoretical analysis, and the interesting theoretical results of this work, I recommend accepting the paper.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "j7eBxurZgI", "reviewer": "Reviewer_CUaV", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n\n- The paper addresses a significant problem in offline reinforcement learning by exploring how unlabelled data can be leveraged to enhance performance.\n\n- It extends the PDS framework to kernel settings, broadening the applicability of the PDS framework.\n\n- The paper provides an insightful theoretical analysis, and demonstrating that the assumption of weak convergence in offline RL may conflict with the kernel regularity assumption typically used in online RL.\n\nWeaknesses:\n\n- The paper lacks empirical validation. While it is primarily theoretical, including experiments on illustrative problems would help demonstrate the effectiveness of the proposed kernel-based method. Additionally, a more detailed discussion on the implementation aspects, such as how to compute the pessimistic reward function in kernel settings, would be beneficial.\n\n- The related work section is somewhat limited in scope. For instance, there are several works on offline RL theory that explore general function approximation, which are not adequately discussed, such as [1,2,3,4].\n\n- The paper would benefit from a more thorough discussion of the assumptions. For example, providing concrete examples where the conditions outlined in Assumption 3.1 hold would enhance the clarity and applicability of the theoretical results.\n\n- The discussion following Corollary 4.9 regarding the assumptions on weak convergence and kernel regularity is intriguing but lacks depth. Expanding this discussion, particularly on the type of assumptions required for the offline data coverage to achieve concrete performance bounds in cases of $d$-exponential decay and $d$-polynomial decay, would significantly strengthen the paper.\n\n\n[1] Uehara, Masatoshi, and Wen Sun. \"Pessimistic model-based offline reinforcement learning under partial coverage.\" arXiv preprint arXiv:2107.06226 (2021).\n\n[2] Yin, Ming, Mengdi Wang, and Yu-Xiang Wang. \"Offline reinforcement learning with differentiable function approximation is provably efficient.\" arXiv preprint arXiv:2210.00750 (2022).\n\n[3] Blanchet, Jose, et al. \"Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage.\" Advances in Neural Information Processing Systems 36 (2024).\n\n[4]  Hu, Hao, et al. \"Bayesian Design Principles for Offline-to-Online Reinforcement Learning.\" arXiv preprint arXiv:2405.20984 (2024).", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper considers enhancing offline reinforcement learning (RL) by incorporating unlabeled (no rewards) offline data. The authors propose an algorithm that utilizes kernel function approximation to leverage unlabeled data, particularly when obtaining labeled data is costly or limited. The paper provides theoretical guarantees for the algorithm's performance and discusses various conditions of eigenvalue decay and coverage of the offline dataset that determine the algorithm's overall complexity.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "See above.", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: Among the detailed reviews, one was more critical of this paper, while one was somewhat positive. On the positive side, as mentioned by Reviewer CUaV, "extends the PDS framework to kernel settings, broadening the applicability of the PDS framework." As mentioned under "Audience", the use of unlabeled data to get better theoretical performance is of sufficient interest to the RL Theory community.

On the negative side, some of the author responses to Reviewer Qc77’s questions did not get at the heart of the questions, which makes it difficult give fairly assess this work in its current form.

First, the reviewer asked why the previous work of Hu et al. does not extend to the finite-horizon setting. The authors respond by first saying that the discounted setting requires a stronger structural assumption (what is this structural assumption?), and then they say that their (the authors') use of non-stationary transition and reward functions makes things more complicated. I cannot draw any clear conclusion from this response. Are the authors saying that the discounted setting is more difficult, or that their (non-stationary) setting is more difficult? In your revision, please carefully (and by all means, clearly) address this comment by Reviewer Qc77:
>> It would be great if the paper can spell out the extra structural assumption required in the discounted setting which could be a motivation for the non-stationary setting studied in this work. It will also be great for the paper to further highlight the additional complexity introduced by the finite horizon setting. As far as I know, in general the analysis for discounted case is usually no easier than the finite horizon setting (e.g. the FQI analysis).

Second, Reviewer Qc77 asked the authors about their Assumption 4.7 (originally Assumption 4.8), wondering if this is a global coverage assumption (which it seems would be a stronger assumption than single policy coverage). The authors response did not address this question. Instead, the authors responded by saying that their assumption allows to compare across all policies, which I stress again is not a proper response to the question. In your revision, please clearly discuss whether your Assumption 4.7 is a global coverage assumption.

Also, from my read of the paper, your theoretical guarantee (Theorem 4.3) only compares against the optimal policy. I apologize if I missed something. If you wish to claim as an advantage that you compare to all policies, then I think you should state the result in a more general way (which, in particular, shows better guarantees for comparing against non-optimal policies, presumably with a bound that depends on some characteristic of the policy being compared to). 

I think the other questions from the reviewer were adequately addressed, and I tend to agree with the authors regarding the distinction between labeled and unlabeled datasets.

I am willing to accept this paper with a "minor revision", but I stress that "minor" is nominal. I want to see the authors very well address the points mentioned above, and this will be a condition for acceptance. Revising in this way should improve how your work is received and will ultimately benefit you.
Decision: Accept (poster)