Offline RL of the Underlying MDP from Heterogeneous Data Sources
Authors: Chengshuai Shi
Wei Xiong
Cong Shen
Jing Yang
Venue: Submitted to ICLR 2023 (2023)
Keywords: RL Theory
Offline RL
Underlying MDP
Heterogeneous Data Sources
Provable Efficiency

Abstract: Most of the existing offline reinforcement learning (RL) studies assume the available dataset is sampled directly from the target environment. However, in some practical applications, the available data are often coming from several related but heterogeneous environments. A theoretical understanding of efficient learning from heterogeneous offline datasets remains lacking. In this work, we study the problem of learning a (hidden) underlying Markov decision process (MDP) based on heterogeneous offline datasets collected from multiple randomly perturbed data sources. A novel HetPEVI algorithm is proposed, which jointly considers two types of uncertainties: sample uncertainties from the finite number of data samples per data source, and source uncertainties due to a finite number of data sources. Building on HetPEVI, we further incorporate reference-advantage decompositions and Bernstein-type penalties to propose the HetPEVI-Adv algorithm. Theoretical analysis not only proves the effectiveness of both HetPEVI and HetPEVI-Adv but also demonstrates the advantage of the latter. More importantly, the results explicitly characterize the learning loss due to the finite heterogeneously realized environments compared with sampling directly from the underlying MDP. Finally, we extend the study to MDPs with linear function approximation and propose the HetPEVI-Lin algorithm that provides additional efficiency guarantees beyond the tabular case.

Under review as a conference paper at ICLR 2023
OFFLINE REINFORCEMENT LEARNING FROM RAN- DOMLY PERTURBED DATA SOURCES
Anonymous authors Paper under double-blind blind review
ABSTRACT
Most of the existing offline reinforcement learning (RL) studies assume the avail- able dataset is sampled directly from the target task. However, in some practical applications, the available data are often coming from several related but hetero- geneous environments, A theoretical understanding of efficient learning from het- erogeneous offline datasets remains lacking. In this work, we study the problem of offline RL based on multiple data sources that are randomly perturbed ver- sions of the target Markov decision process (MDP). novel HetPEVI algorithm is first proposed, which simultaneously considers two types of uncertainties: sam- ple uncertainties from a finite number of data samples per data source, and source uncertainties due to a finite number of data sources. In particular, the sample un- certainties from all data sources are jointly aggregated, while an additional penalty term is specially constructed to compensate for the source uncertainties. Theoret- ical analysis demonstrates the near-optimal performance of HetPEVI. More im- portantly, the costs and benefits of learning with randomly perturbed data sources are explicitly characterized: on one hand, an unavoidable performance loss occurs due to the indirect access to the target MDP; on the other hand, efficient learning is achievable as long as the sources collectively (instead of individually) provides good data coverage. Finally, we extend the study to linear function approxima- tion and propose the HetPEVI-Lin algorithm that provides additional efficiency guarantees beyond the tabular cases.
INTRODUCTION
Offline reinforcement learning (RL) (Levine et al. 2020). a.k.a. batch RL (Lange et al. 2012), has received growing interest in the recent years. It aims at training RL agents using accessible datasets collected priori and thus avoids expensive online interactions. Along with its tremendous empirical successes (Kidambi et al.) (020). recent studies have also established theoretical understandings of
offline RL (Rashidinejad et al. 2021 Jin et al. 2021b Duan et al. 2021 Uehara & Sun 2021).
Despite these advances, the majority of offline RI. research focuses learning via data collected exactly from the target task environment (Kumar et al., (020). However, in practice, it is difficult ensure that all such data are perfectly from one source environment. Instead, in many cases, is more reasonable to assume that data are collected from different sources that are perturbed versions of the target task. For example, when training chatbot (Jaques al. 2020), the offline dialogue datasets typically consist of short conversations between different people, who naturally have vary- ing language habits. The training objective is the common underlying language structure, e.g., basic grammar, which however cannot be reflected in any individual dialogue but must be holistically learned from the aggregation of them. More examples can be found in healthcare (Tang Wiens, 2021), autonomous driving (Sallab et al. (017)) and others. While few empirical investigations under the offline meta-RL framework have been reported (Dorfman et al. 2021 Lin et al. 2022] Mitchell et al. 2021). theoretical understandings of effectively and efficiently learning the underly- ing task using datasets from multiple heterogeneous sources are largely lacking.
Motivated by both practical and theoretical limitations, this work makes progress in the under- explored RL problem of learning the target task using data from heterogeneously perturbed data sources. In particular, study the problem of learning target Markov decision process (MDP)

---

Under review as a conference paper at ICLR 2023
from offline datasets sampled from multiple heterogeneously realized source MDPs. Several prov- ably efficient designs are proposed, targeting both tabular and linear MDPs. To the best of our knowledge, this is the first work that proposes provably efficient offline RL algorithms to handle perturbed data sources, which can benefit relevant applications and further shed light on the theoret- ical understanding of offline meta-RI. The contributions are summarized as follows:
We study a new offline RL problem where the datasets are collected from multiple heterogeneous source MDPs, with possibly different reward and transition dynamics, instead of directly from the target MDP. Motivated by practical applications, the data source MDPs are modeled as random perturbations of the target MDP. Compared with studies of offline RL using data directly from the target MDP (Rashidinejad et al. [021] Jin et al.) (0211). we face new challenges of jointly consid- ering uncertainties caused by the finite number data samples per source (referred to as the sample uncertainties) and by the finite number of data sources (referred to as the source uncertainties).
A novel HetPEVI algorithm is proposed, which generalizes the idea of pessimistic value iteration [Jin et al. (02 and uses carefully crafted penalty terms to address the sample and source uncer- tainties simultaneously. Specifically, in the HeIPEVI, the specially designed penalty term contains two parts: one aggregating the sample uncertainties associated with each dataset, and the other term compensating the source uncertainties. The combination of these two parts jointly characterizes the uncertainty associated with the collected datasets.
Theoretical analysis proves the effectiveness of HetPEVI with a corresponding lower bound, which first demonstrates that even with finite randomly perturbed MDPs and finite data samples from each of them, it is feasible to efficiently learn the target MDP. More importantly, the analysis reveals that learning with multiple perturbed data sources brings both costs and benefits. On one hand, due to indirect access to the target MDP, an unavoidable learning cost occurs. This cost scales only with the number of data sources and cannot be reduced by increasing the size of datasets, which highlights the importance of the diversity of data sources. On the other hand, effective learning only requires that the datasets collectively (instead of individually) provide a good coverage of the optimal policy, which may provide additional insights for practical data collections.
Moreover, we extend the study to linear function approximation where offline data are collected from linear MDPs with a shared feature mapping but heterogeneously realized system dynamics. The HelPEVI-Lin algorithm is developed to jointly consider the sample and source uncertainties while incorporating the linear structure. Theoretical analysis demonstrates the effectiveness of HetPEVI-Lin and verifies the sufficiency of a good collective coverage.
Related Works. With the empirical success of offline RL (Levine al. 2020). its theoretical under- standings have been gradually established in recent years. In particular, the principle of "pessimism" is incorporated and proved efficient for offline RL (Jin et al.
2021b Rashidinejad et al. 2021 Fol-
lowing this line, Xie et al. (2021b;; Li et al. y Shi et al. (2022) further fine-tune the designs for the tabular setting and Zanette al. (2021) Min et al. (2021) Yin et al. (2022): Xiong et al. (2022)
for linear MDPs (Jin et al. 2020). These theoretical advances are mainly focused on learning with data directly from the target task. However, in the practical studies of RI, growing interests have been made to utilize data from heterogencous sources, c.g., offline meta-RL (Mitchell et al.) 202T Dorfman et al.) [ Lin et al. 2022. Li et al. 2020b). This work thus motivated to provide theoretical understanding of how to extract information about the target task from multiple sources. more detailed literature review regarding both online and offline RL with single or heterogeneous
environments is provided in Appendix A.
2 PROBLEM FORMULATION
Preliminaries of RL. We consider an RL problem characterized by an episodic MDP M (H, SP r). In this tuple, H the length of each episode, S is the state space, A is the ac- tion space, IP is the transition matrix that PA (s'|s, a) gives the probability of transiting to state s' if action a is taken for state s at step h, and rb (s, a) is the deterministic reward in the interval of [0, 1] of taking action a for state at step h Specifically, in each episode, starting from initial state $1, at each step h E [H) the agent observes state 8) E S, picks action O₁ E A, receives reward
'The assumption of deterministic rewards is standard in theoretical analysis of RI. Jin et al. 2018 2020 the uncertainties estimating rewards are dominated by those in estimating transitions.
2

---

Under review as a conference paper at ICLR 2023
(s,, an), and then transits to next state Sh+1 the tabular RL setting, the state and action spaces are finite with S = S and A == |A].
Pa((|sh, (,)) The episode ends after H steps. In
A policy := {Ta(--s) (s, h) S x [f]} consists of distributions Ta (-Is) over the action space A. whose value functions can be defined as (s)(s) == B...IEE - Th (shr, ar )ss s) and (s, a) := Ex .MxMMii - The ((s):.ar))as))) (ss) 8, az a] for each (s, a, h) E S x A x [M], where the expectation E..MI is with respect to (W..t.) the random trajectory induced by policy x on MDP M. The optimal policy x' maximizes the value function, i.e., π²' == arg max V (s). For convenience, we denote (s) := V (s) and (s, == Q7 (s, a) for (s, a, h) E Ax [H], and use (s) to refer to the chosen action for state 8 at step for deterministic policy x.
2.1 THE LEARNING TARGET AND OFFLINE DATASETS
The Target Task. This work considers a target task modeled by an MDP M = (H, which can be any task of interest (e.g., chatbot training in Sec. [ The goal to find good output policy i with small sub-optimality gap on the target MDP M, which is measured as:
G = (i( - (si))
Note that an output policy &t is called s-optimal if Gap(f; S e.
Multiple Data Sources. The agent has access datasets from L sources, i..., D : (Di, vI E [4])- Each dataset Dj := {sh,1 oh rh,s rh,1s : k E [K], E [/]} consists of K tuples for each step h E [H] sampled by a (possibly different) unknown behavior policy Pt on a unknown data source MDP denoted as M; = (H, A, . In particular, for each step h E: [H], the behavior policy Pt performs K times sampling over the state-action space S x A following a distribution denoted as (.), i.., for each & [K], (sh ah,)) ) ~ ()).()). Then, for a sampled pair (sh. af..). the reward ri. = (s of..) and $411 ~ Ph, (..1) realized from the date source MDP Mi collected and aggregated
tuple (sf o Th. .% for the dataset Dr. To ease the presentation, all the sampled tuples are assumed to be independent of each other. Such independence can be ensured by applying the sub-sampling technique in Li et al. (0022 to trajectories induced by behavior policies while maintaining the order of the dataset size.
2.2 THE TASK- RELATIONSHIP
On one hand, motivated by Sec. D each data source MDP MM may not exactly match the target task M. Concretely, while having the same episodic length, state space, and action space, their transition and reward dynamics are not necessarily aligned, i.e., (-, a) # (-(-ss, a), (s, a) * nh (s, a).
On the other hand, in practical applications, while being heterogencous, the data source MDPs often still related to the target task (e.g., dialogue datasets in Sec. D. In particular, data sources in offiine meta-RI. are often assumed to be sampled from certain distribution (Mitchell al. 202T) Thus, the following relationship between the target MDP and the data source MDPs is assumed.
Assumption 1 (Task-source Relationship). Data source MDPs (Mi : L [L]] are independently sampled from an unknown distribution g such that for each (I, s,,,,a, h) E [L] x S x x [H), the reward (s, a) is a random variable with mean ru(s, a), and the transition vector ( (s a random vector with mean Pi, (-Is, a). In particular, random variables and random vectors {ra,((s, a), (Paa(-)ss a): (s, a. 1) E S x A [H] x [L]] are independent with each other.
The requirement that rewards are random samples with the expectation as the target model is com- monly adopted bandits literature (Shi Shen 2021 Zhu & Kveton 2022), and the same require- ment the transition vectors is natural extension, where one representative example is to have them follow a Dirichlet distribution (Marchal & Arbel (017).
Miscellaneous. Notations without subscripts generally refer to the target MDP M, while sub- scripts / are always added when discussing each individual source Mi. For a clear presentation, the notation is used throughout the paper with varing values to represent a poly-logarithmic term of or- der O (poolylogg LHS SA/6)) for the tabular setting and O(poly(oog(La)) (LH/))) for the linear setting, where 8 E (0, 1) is confidence parameter. Additionally, for x E RR x= denotes max max(x,0) (z, 0}.
3

---

Under review as a conference paper at ICLR 2023
For any function f S + R. the transition operator and Bellman operator of the target MDP M at each step E [ are defined, respectively, as (Pn.f)(s, a) := =]f((''|s |s. al and (B, = (s, a) + (P,.f(s, a), where the expectation is w.r.t the transition s' (- a). Expectation Ea.Ml [+] is over the trajectory induced by on the MDP M starting from 81, and d (s. a) denotes the probability of visiting state-action pair (s, a) step with policy on M starting from 81.
Algorithm HetPEVI
Input: Dataset D = (Dr E []]; (s) 0, Vs E 1: For each (1, a, h) E [L] x S x A x [H], estimate fn,((,,) = (n)(s,a)l(MMu(ss.) + No.1(s,,,s')
and Ph.,(5'|s,
(s..(s
2: For each (s,0, hi) E A x [H], aggregate (n(8,)) 1 Chezzpinile a) and (s(
1. EiEL1] (s
3: for h -.,, do
Perform updates for all (s, a) S A as Eqn. i with (B,, Vh+ ( = an(,, +
4:
(Px (s)) a) and (n( = cv EiE(A) (NNNII
n
ev
5: end for
Output: policy ã = (s) (s,h) E S [
3 THE HETPEVI ALGORITHM
In this section, the HetPEVI algorithm is introduced for the tabular MDP setting (presented in Algo- rithm T). HetPEVI follows the principle of pessimistic value iterations (PEVI) (Rashidinejad et al., 2021 Jin et al. 2021b), which is first briefly introduced, while the key challenges and our novel design in learning the target MDP from randomly perturbed data sources are then illustrated.
The HetPEVI algorithm begins by counting the number of visitations for each tuple (s, a, h, s') x A x [H] x S in each dataset 1 E [L]. Especially, we denote N,,, a) and N,.1 o, s') as the amount of visitations (s, a, h)) and (s, a, h, s') in dataset Di, respectively. Empirical estimations
of rewards and transitions are then given for all (1, a, h) E [L] x S x A x [H] as
(s, Nu,(s, a')) Nn.i a) V1
(s, a) (s, a) (Na, a) # 0);
These individual estimates are then aggregated into overall estimates as:
(s, L (ELL] fn,((s,)) a); PP(8'1s,a)= 1 Eness PP (s,))
Σ
With these estimations, HetPEVI iterates backward from the last step the first step
(s. min { {B, V1+1) a) (s, h+1
(I)
Vs((s) = max.EA (s,a),, tx (s) = arg max. (s,
with VH+1(s)= 0, Vs S, and the empirical Bellman operator iB, is defined
(Br (s.) a) = (s. + (P,, (s))))))
where (PANn))) a) is the empirical version of (Px 1) (s, a) using the estimated P (-1s,, a).
The essence of the above procedure is that instead of directly setting (s, a) as (B,, 1s, (as in the standard value iteration), a penalty term (s, a) is subtracted, which serves the important role keeping the estimations (s) and Qu (s, a) pessimistic. Especially, the penalty term [ a) should be carefully designed such that with high probability, it holds that
[B, Vo. (s, a) (Ba Vx (s, a) (s,,a)),
V(s.a,) ES H
Technical Challenges. Previous offline RL studies (Jin et al. 20216 Rashidinejad et al. 2021 Yin et al. 2022 Xie al. 2021b) only deal with one single target data source and only type
4

---

Under review as a conference paper at ICLR 2023
of uncertainties (finite data samples) to ensure Eqn. 2. In this work, the agent needs to process multiple heterogeneous datasets, while none of them indiiiuualy characterizes the learning target. As result, the agent faces two coupled challenges. First, the uncertainties due to the finite sample sizes still needs to he considered. This is referred to as the sample uncertainties, but the key difference is that now the agent needs jointly consider and aggregate uncertainties associated with all data sources, Second, even with perfect knowledge of each data source, the target MDP may not be fully revealed. Thus, the agent also needs consider the uncertainties from the limited number of data sources, which are referred to as the source uncertainties.
To address the two uncertainties, the penalty term is designed have two parts as follows:
Ta a) (s, a) + (s,
where (s, a) aggregates the sample uncertainties from each data source while (s, a) accounts for the source uncertainties. Both of them are further elaborated on in the following.
Penalties to Aggregate Sample Uncertainties. For the first part of the penalty, i.e., (s, a). since the agent faces data from multiple heterogeneous sources, the penalty term needs to jointly consider the individual uncertainties from sources. In HetPEVI, the following penalty term is proposed, which originates from the Hoeffding inequality:
H (2Nn,(s.d))VL + ov L
H
(s) =c
Σ [E[T.
Note that instead of treating each source individually and directly summing up their sample uncer- tainties (as e EieLL /V Ni.,(s.a)vi) ). the adopted penalty term is a joint measure of sample uncer- tainties from all sources. This would lead to O(VL) speed-up in the performance guarantees.
H²
Penalties to Account for Source Uncertainties. The second part of the penalty r (s, a) serves the important role of measuring the uncertainties due to the limited amount of data sources. With the observation that (IB,, (s) (s,a)) a) is a bounded random variable with mean of (B, Vs,)) a), the following penalty term is proposed:
H2 (s, cV T.
Intuitively, it shrinks with the number of datasets, i.e., L. as more sources provide more information about the target task.
Remark 1. With the two-part penalty term, with high probability, for all (s, a, h) E S x A x [H], it simultaneously holds that [(i,, (s, a) (B,, (ss a) < rg a) and (IB V (s, a.) (B, (s, a)l = (f. a), which jointly ensure Equ. (2)
Remark 2.
The adopted source uncertainty penalty r (s, a) is intended to accommodate any un- known variance between sources. However, if there prior knowledge of the variance, it feasible to incorporate such information. In particular, if the rewards and transition vectors are generated via --sub-Gaussian distributions, the penalty can be designed as r (x, a) c222.
4 THEORETICAL ANALYSIS
4.1 INDIVIDUALLY GOOD COVERAGE
Previous offline RL studies typically require that the behavior policy should provide information for all the state-action pairs that may be visited by the optimal policy on the target MDP, e.g., Rashidinejad et al. (2021 ; Xie et al. (2021b). Particularizing this requirement to each individual data source considered in this work leads to the following assumption, which requires each individual dataset covers the optimal policy on the target MDP.
Assumption 2 (Individual Coverage). There exists constant C* < such that for all a, h,
S A x [H] [T), it holds that dy (s, C (s,
5

---

Under review as a conference paper at ICLR 2023
Under this assumption, minimax lower bound is first established as follows.
Theorem (Lower Bound; Individual Coverage), For any C* 2 2,5 2 2, it holds that
DeMe(1)) (Gap( M)] = C² CHS LK
H2
inf MED. (at.:..eo..oe(eeeeee..... (
sup
VV
L
where W = (M is the family of all possible target MDPs, B Ag: MMMgglle [L]] satisfies Assumption 7 is a family of data source generation distributions, and (BC) (pp E [4]} Assumption holds with C C} is family of behavior policies.
The first term in this lower bound is the same as the lower bound of standard offline RL with LK data samples directly from the target MDP (Rashidnejad et al. 202T). which represents the perfor- mance loss originating from finite data samples. The second term is unique for the setting studied in this work, as it represents the loss caused by learning with finite randomly perturbed data sources. Especially, it can be observed that the second term only scales with the number of data sources, i... L, and cannot be mitigated via sampling more data from each data source, i.c., increasing K. On one hand, this observation verifies the intuition that using data sampled from multiple randomly perturbed data sources poses additional learning difficulties. On the other hand, it also highlights the importance of the diversity of data sources, i.e., it is more important to involve more sources instead of more data from each source. This is reasonable as involving more data sources provides additional population coverage while also adding more data.
With the information-theoreti lower bound established, the performance guarantee of HetPEVI is also provided in the following theorem, which highlights its effectiveness and efficiency.
Theorem 2 (HetPEVI; Individual Coverage). Under Assumptions 7 policy ât of HeiPEVI satisfies
w.p. at least - 5, the output
Gt) - =0(
C' HAS
H
LK +
T.
This result first illustrates that even with finite randomly perturbed MDPs and finite data samples from each of them, it is still feasible to efficiently learn the target. Compared with the lower bound in Theorem T it can be observed that HetPEVI is optimal (up to logarithmie factors) on the dependency of I., K, C and S. The additional / H factor in the first term (from the sample uncertainties) can be removed by invoking a carefully designed Bernstein-type penalty term to incorporate the variance information, which is deferred to Appendix [ due to the space limitation. However, it is currently unclear how to alleviate the additional I/ factor in the second term (from the source uncertainties), which is left open to be further investigated.
Additionally, Thm. L iindicaess that to obtain an e-optimal policy, HetPEVI requires the overall num- ber of samples T = LK to be of order Ô(C* H (/S/=²) and the available number of data sources L to be of order Ö (H*/e")) /E?). Note that the first requirement can be viewed as the sample complexity while the second one is on the source diversity.
4.2 COLLECTIVELY GOOD COVERAGE
can be noticed that Assumption 2 requires each data source to provide good coverage. With access to only one data source in previous offline RL studies, this requirement is intuitive as information about the optimal policy needs to be obtained. However, the multiple available datasets in this work provide opportunities to avoid this strong assumption via their aggregated information. In this section, the scenario where the datasets collectively provide a good coverage is discussed. In particular, characterize the collective coverage, the following assumption is proposed.
Assumption 3 (Collective Coverage). There exist constants L >> 0 and Ct 00 such that for all (s, a, h) E S x x H), it holds that [1 [Z] : di (s,a) S Ctafi a)l 2 Lt.
It can be observed that Assumption
1 is weaker than Assumption 2 as the latter implies the former with Li = L and C = C*. Morcover, instead of requiring each data source individually covers the optimal policy, Assumption leverages their collective coverage. In particular, for each different

---

Under review as a conference paper at ICLR 2023
state-action pair possibly visited by the optimal policy (i.e., dī, (s.a) a) potentially varying datasets cover it. In other words, different parts of the optimal policy can be covered by different datasets, which is highly practical consideration. Under Assumption B] the following performance guarantee of HetPEVI can be further obtained.
0), it is sufficient to have
Theorem (HetPEVI; Collective Coverage). Under Assumptions w.p. at least 5,, the output policy it of HerPEVI satisfies
Gap(f;:M)= (V CIHAS LK
(L +
LT L
+
Compared with Theorem 2 Theorem B is more general and also more practically useful it implies the former and indicates that good collective coverage is sufficient for efficient learning. Moreover, from another perspective, the performance dependence on L also highlights the importance of collecting high-quality datasets.
As summary of the obtained observations, learning via randomly perturbed datasets brings both costs and benefits. Especially, an unavoidable performance loss occurs due to the indirect access the target MDP. This loss can only be reduced by increasing the diversity of data sources, i.c., larger L, but cannot be mitigated by collecting a larger dataset from each data source, i.c., a larger K. Despite bringing the additional loss, the access to multiple heterogeneous datasets provides an opportunity to leverage their aggregated information, which is concretely reflected that efficient learning only requires a good collective (instead of individual) coverage.
EXTENSION TO OFFLINE LINEAR MDP
Lastly, we extend the study from tabular RL to incorporating function approximations, Especially, the following linear MDP model is considered.
(H,S,A,P, is linear MDP with feature map S x A + Rd if there exist d unknown measures Ph (1/ S and an unknown vector On R s.t. (a(s']s, a) (ő(s.a), pn(ss)) and ra(s, a) (Ø(s, a)ss,a,,e 0n) for all (s, a, 8') E S x A x S at each step E [H] Without loss of generality, is assumed that [lo(s, a) 2 < 1 for all (s, E S x A and max (S)12,, |100|l]] S for all h E [H]. where (5) = Is (I ds. For simplicity, we denote M (H A.H, ò.
Definition (Linear MDP (Jin et al. 2020 2021b)). An MDP == =
(d)
Hh over
With this definition, consider the problem that the target MDP .M is linear MDP, i.e., M (H, S,A, d, μu 0). Correspondingly, the data source MDPs (M, : / E [L]] are also assumed to be linear MDPs, which are denoted as {Mi (H, o. Mr, data source MDPs are assumed to share the same feature dimension d and feature mapping á as the target MDP: however, their system dynamics may be different. We note that this shared feature mapping is commonly adopted in federated linear bandits (Huang et al., 2021 Li & Wang 2022), which naturally extends to linear MDP. Then, similarly as Assumption in the tabular MDP, the following task-source relationship is assumed for the linear MDP to model that the data sources are randomly perturbed versions of the target MDP.
mr,0t) 0:)
[L]]. In particular, the
Assumption 4 (Task-source Relationship: Linear MDP). Data source MDPs { : E [ are independently sampled from unknown distributions g such that for each (I, h) E [4] x [d x [H]
the vector 0n,1 is random vector with mean On. and the measure Pa, is random measure with mean 2h
(3)
(4) In particular, random vectors and measures (Oh,1, Mh. i,, [H] [d [L]]
(8)
independent with each other.
Note that when treating the tabular setting as d = SAA and Φ(s,a) a) = ((s,a), where ( denotes a canonical basis in Rdd Assumption 4 returns to Assumption
5.1 HETPEVI-LIN FOR LINEAR MDPS
From the linear MDP definition, it can be shown that the Bellman operators of each data source MDP and the target MDP are all linear (but with different weights).
7

---

Under review as a conference paper at ICLR 2023
Algorithm 2 HetPEVI-Lin
Input: Dataset D (Di :LE [[]; VH+1(8) 0s
1: Estimate Wh, <- An [kE(K] (5 (h11)) (rhe + Vntz(sh+zi) 1) E [H] x [4]
2: Set ih + Lie(n] Wh, L. vh E [H]
3: for h = H, H - 1,.., do
4:
Perform updates for all (s,a) a) E S x A as Equ. 1 with (B, (s,)) = -2i d(s, a) and
as) = /v dH²
V /Eie (0(s,))]
Az c dha
5: end for
Output: policy म = (8) (8, E S [M]
Lemma 1. With any function f S + R, there exists twhy E B E [M] E [b]] and twy Rd h E [H] such that for any (s, 0, b)) E S SxAx it holds that (Bn,,f((s, a) (ø(s, a), ()(s,a), w for each E [L] and (B,
(0(s, a), w
Furthermore, the following lemma can be established for the sample average MDP M (H, S, A.,,Pr), r), where a)) = L. EieLo Pn,,(-ls,a) and Fn (s. a) = 1 Σiely (s, states that M is also linear MDP and the weights associated with its Bellman operator the average of weights from each individual data source MDP.
Lemma 2. The average MDP M is a linear MDP of dimension d with feature mapping Φ. Also, for any function f S:S R and any (s, a, h) S with weights (wh) Eie(r) W L: : E [M]]
[H], holds that (Bnf)(s, (Ø(s, a), w/))
With the above observations, the HetPEVI-Lin algorithm is proposed (presented in Algorithm First, for each step E [H] and each data source E [L], the weight th,, is estimated via a ridge regression:
Whh1 = arg WiR Exeio [rhi + Vetz(sh+1.) oi a
Tw]
1 + L
||00
= =N Eneexy Mih (hi (1he Vits(oh
with Ar. = EKE(K) Mohi af ( ( +1/L. The agent aggregates ún Eie(ry wn.//L which provides an estimation of the weight Wn associated with the average MDP M. The PEVI in Equ. 11 is then performed with the empirical Bellman operator defined as (B,, VA,,))))ss,0 = (o(s, a), wh)) and a two-part penalty term ('x(s, a) 1% (s, (s,aa)a+ (s, a) illustrated in the following.
Penaltics to Aggregate Sample Uncertainties. The first part of the penalty term aggregates the sample uncertainties from each data source, which is designed
d.H T22
(s( a) -
Enete
())(s,)))l
While this penalty term shares a similar format as those in linear bandits (Li et al. 2010: Abbasi- Yadkori et al., 2011) and linear MDPs (Jin al. 2020 2021b), its novelty comes from jointly considering the uncertainties of different sources. Especially, this design avoids applying the self- al. 2011 to each data source (which leads an infe- rior dependency on L) by leveraging the statistical independence among the split datasets.
normalized concentration Abbbasi-Yadkon
Penalties to Account for Source Uncertainties. Besides the sample uncertainties, the following
penalty is designed to measure the source uncertainties:
dH (s, = L
Note that compared with the tabular design, an additional d factor appears, which is from the cover- ing argument over the d-dimensional feature space.
8

---

Under review as a conference paper at ICLR 2023
5.2 THEORETICAL ANALYSIS
Similar to the tabular setting, previous offline RL studies with linear MDPs often requires the be- havior policy cover the optimal policy (Jin al.) 202 Xiong al. 2022) (or even stronger, to cover the entire feature space (Yin et al., [002] Min et al. 2021]). Hence, following Sec. 4 we first discuss the scenario with good individual coverage characterized by the following assumption.
Assumption 5 (Individual Coverage; Linear MDP). There exists a constant D such that for all (h E [H] x [L], it holds that Ex MM(o(s8 an (1))((8h 0h) 0b) MPp.,,,,s(( (n))(8h; a.
Theorem (HetPEVI-Lin; Individual Coverage). Under Assumptions 15 and assuming the matri- ces (Eie(r) An, h [ are invertible, w.p. at least 1 5, the output policy & of HetPEVI-Lin satisfies
0 D KT. +
Gap(f::M= Gup(#:M)= 00
dH T.
Similar to Thm. 2 the two terms Thm. Aoriginate from the finite data samples and the limited data sources, respectively. However, note that the gap guarantee in Thm. does dom. not have dependency on the number of states (which appears in the tabular analysis), instead it depends on the feature di- mension d, thanks to the careful design that incorporates linear function approximation. As result, to output s-optimal policy, the sample complexity requirement is T KL Ö df 1* 2e²) while the source diversity requirement is L = OddH+/E))
One important observation from the tabular setting is that efficient learning only requires a good collective (instead of individual) coverage. To further verify this claim, the following collective coverage assumption is considered for linear MDPs, which shares a similar format as Assumption
Assumption 6 (Collective Coverage; Linear MDP). There exist constants L > and D
oo such that for all h E [M]. it holds that I E [4] EM(sM( an (6()))(())))) as)"l
D' PeL,,,o(shs ())) un)) []] Lt.
It can be observed that Assumption 5 iimplies Assumption 6 with Lt = T. and DJ D With this relatively weaker collective coverage assumption, the following theorem can be established.
Theorem (HetPEVI-Lin; Collective Coverage). Under Assumptions B assuming the matri-
(Eeety A h [H]} invertible, w.p. least 5, the output policy & of HetPEVI-Lin
satisfies
Gap(#;M)= ( Did-Ha KL
d(L + 1 - L4)HA
KL
+
can be observed that Thm. shares a similar form as Thm. both of which illustrate that as long as the datasets collectively cover the optimal policy, efficient learning is achievable.
CONCLUSIONS
This work studied novel problem of efficient offline RL with randomly perturbed data sources. In particular, motivated by practical applications, the available offline datasets are assumed to be collected from multiple randomly perturbed versions of the target MDP. The HetPEVI algorithm is proposed, where novel penalty terms were designed to jointly consider the uncertainties from the finite data samples and the limited amount of data sources. Theoretical analyses proved its near- optimal performance. More importantly, the costs and benefits of offline RL via randomly perturbed data sources are explicitly characterized. On one hand, an additional unavoidable performance loss occurs due to the finite data sources, which cannot be reduced by involving more data samples from each source. On the other hand, as long as the datasets collectively (instead of individually) provide a good data coverage, efficient learning is achievable. Lastly, linear function approximation was considered, and the HetPEVI-Lin algorithm was developed with penalties carefully designed to consider both uncertainties and incorporate the linear structure. Its analysis again verifies the importance of source diversity and the sufficiency of collective coverage.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Abbasi-Yadkori, Y., Pál, D., & Szepesvári, C. (2011). Improved algorithms for linear stochastic bandits. Advances in neural information processing systems, 24.
Agarwal, A., Jiang, N., Kakade, M., & Sun, W. (2019), Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle. WA, USA, Tech. Rep.
Azar, M. G., Osband, I., & Munos, R. (2017). Minimax regret bounds for reinforcement learning. In International Conference on Machine Learning (pp. 263-272), PMLR.
Brunskill, E. & Li, L. (2013). Sample complexity of multi-task reinforcement learning. In Uncer- tainty in Artificial Intelligence (pp. 122).: Citeseer.
Chua, K., Lei, Q. & Lee, J. D. (2021). Provable hierarchy-based meta-reinforcemmen learning, arXiv preprint arXiv: 10.005077
Dann, C., Mohri, M., Zhang, T., & Zimmert, (2021). A provably efficient model-free posterior sampling method for episodic reinforcement learning. Advances in Neural Information Process- ing Systems, 34.
Dorfman, R., Shenfeld, I., & Tamar, A. (2021), Offline meta reinforcement ieetiing-identifibbiiii challenges and effective data collection strategies. Advances in Neural Information Processing Systems, 34.
Duan, Y., Jin, C., Li, Z. (2021). Risk bounds and rademacher complexity in batch reinforcement learning. International Conference on Machine Learning (pp. 2892-2902).: PMLR.
Fallah, A., Georgiev, K., Mokhtari, A., & Ozdaglar, A. (2021). On the convergence theory of de- biased model-agnostic meta-reinforcement learning. Advances in Neural Information Processing Systems, 34.
Gupta, A., Mendonca, R., Liu, Y., Abbeel, P., & Levine, S. (2018). Meta-reinforcement learning of structured exploration strategies. Advances in neural information processing systems, 31.
Hallak, A., Di Castro, D., & Mannor, S. (2015). Contextual markov decision processes. arXiv
preprint Att:15502.02299
Huang, R., Wu, W., Yang, J., & Shen, C. (2021). Federated linear contextual bandits. Proceedings of the 35th Conference Neural Information Processing Systems (NeurIPS).
Jaques, N., Shen, J. H., Ghandeharioun, A., Ferguson, C., Lapedriza, A., Jones, N., Gu, S., & Picard, R. W. (2020). Human-centric dialog training via offline reinforcement learning. In EMNLP (1).
Jiang. N., Krishnamurthy, A., Agarwal, A., Langford, J., & Schapire, R. E. (2017). Contextual decision processes with low bellman rank are pac-learnable In International Conference on Machine Learning (pp. 1703-1713). PMLR.
Jin, C., Allen-Zhu, Z., Bubeck, S., & Jordan, M. (2018). Is q-learning provably efficient? Ad- vances in neural information processing systems, 31.
Jin, C., Liu, Q. & Miryoosefi, S. (2021a). Bellman eluder dimension: New rich classes of problems, and sample-efficient algorithms. Advances in Neural Information Processing Systems, 34.
Jin, C., Yang, Z.,, Wang, Z.,, & Jordan, M. I. (2020). Provably efficient reinforcement learning with linear function approximation. In Conference Learning Theory (pp. 2137-2143): PMLR.
Jin, H., Peng, Y. Yang, W., Wang. S., & Zhang, Z. (2022). Federated reinforcement learning with environment heterogeneity. In International Conference on Artificial Intelligence and Statistics (pp. 18-37). PMLR.
Jin, Y., Yang, Z. Wang, Z. (2021b). Is pessimism provably efficient for offline rl? In International Conference Machine Learning (pp. 5084-50840000 5086-5006).: PMLR.
10

---

Under review as a conference paper at ICLR 2023
Kidambi, R., Rajeswaran, A., Netrapalli, P., & Joachims, T. (2020). Morel: Model-based offline
reinforcement learning. Advances in neural information processing systems, 33, 11810-218223
Kumar, A., Zhou, A., Tucker, G., & Levine, S. (2020). Conservative q-learning for offline reinforce-
ment learning. Advances in Neural Information Processing Systems, 33, 1179-1191.
Kwon, J., Efroni, Y., Caramanis, C., Mannor, S. (2021a). Reinforcement learning in reward- mixing mdps. Advances in Neural Information Processing Systems, 34.
Kwon, J., Efroni, Y., Caramanis, C., Mannor, S. (2021b), RI for latent mdps: Regret guarantees and a lower bound. Advances in Neural Information Processing Systems, 34.
Lange, S., Gabel, T. & Riedmiller, M. (2012). Batch reinforcement learning. In Reinforcement learning (pp. 45-73). Springer.
Levine, S., Kumar, A., Tucker, G., & Fu, J. (2020). Offline reinforcement learning: Tutorial, review, and perspectives open problems. arXiv preprint AXXiv:2005.06643
Li, C. & Wang, H. (2022). Asynchronous upper confidence bound algorithms for federated linear bandits. In International Conference on Artificial Intelligence and Statistics (pp. 6529-6553).; PMLR.
Li, G., Shi, L., Chen, Y., Chi, Y., & Wei, Y. (2022). Settling the sample complexity of model-based offline reinforcement learning, arXiv preprint arXiv:220..05275.
Li, J., Vuong, Q., Liu, S., Liu, M., Ciosek, K., Christensen, H., Su, H. (2020a). Multi-task batch reinforcement learning with metric learning, Advances in Neural Information Processing Systems, 33, 6197-6210.
Li, L., Chu, W., Langford, J., & Schapire, R. E. (2010). A contextual- bandit approach to personal- ized news article recommendation. In Proceedings of the 19th international conference on World wide web (pp. 661-670).
Li, L.. Yang, R., & Luo, D. (2020b). Focal: Efficient fully-ofiline meta-reinforceement learning via distance metric learning and behavior regularization. arXiv preprint arXiv:2010.01112.
Lin, S., Wan, J., Xu, T., Liang, Y., & Zhang, J. (2022). Model-based offline meta-reinffrceement learning with regularization. arXiv preprint arXiv:2202.022
Lu, R., Huang, G., & Du, S. (2021). On the power of multitask representation learning in linear mdp. arXiv preprint arXiv: 106.0005330.
Marchal, O. & Arbel, J. (2017). On the sub-gaussianity of the beta and dirichlet distributions. Electronic Communications in Probability, 22, 1-14.
Maurer, A. & Pontil, M. (2009). Empirical bernstein bounds and sample variance penalization. arXiv preprint urXiv:0907.37400
Min, Y., Wang, T., Zhou, D., & Gu, Q. (2021). Variance-aware off-polic evaluation with linear
function approximation. Advances in neural information processing systems, 34.
Mirsky, L. (1975). trace inequality of john von neumann. Monatshefte für mathematik, 79(4), 303-306.
Mitchell, E., Rafailov, R., Peng. X. B.. Levine, S., & Finn, C. (2021). Offline meta-reinforcement
learning with advantage weighting. In International Conference on Machine Learning (pp. 7780- 7791).: PMLR.
Panaganti, Kalathil, (2022). Sample complexity of robust reinforcement learning with generative model. In International Conference on Artificial Intelligence and Statistics (pp. 9582- 9602).: PMLR.
Panaganti, K., Xu, Z., Kalathil, D., & Ghavamzadeh. M. (2022). Robust reinforcement learning using offline data. arXiv preprint 2rXiv:2208.05/29

---

Under review as a conference paper at ICLR 2023
Rashidinejad, P., Zhu, B., Ma, C., Jiao, J., & Russell, S. (2021). Bridging offline reinforcement learning and imitation learning: A tale of pessimism. Advances Neural Information Processing Systems, 34.
Sæmundsson, S., Hofmann, K., Deisenroth, M. (2018). Meta reinforcement learning with la- tent variable gaussian processes. In 34th Conference Uncertainty in Artificial Intelligence 2018, UAI 2018, volume 34 (pp. (42)) Association for Uncertainty in Artificial Intelligence (AUAI).
Sallab, E., Abdou, M., Perot, E., & Yogamani, S. (2017). Deep reinforcement learning framework for autonomous driving. Electronic Imaging, 2017(19), 70-76.
Shi, C. Shen, C. (2021). Federated multi-armed bandits. In Proceedings of the 35th AAAI Con- ference on Artificial Intelligence (AAAI).
Shi, L. Chi, Y. (2022). Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprini arXiv:2208.05767.
Shi, L., Li, G., Wei, Y., Chen, Y., & Chi, Y. (2022). Pessimistic q-learning for offline reinforcement learning: Towards optimal sample complexity. arXiv preprint arXiv:2202.13880.
Shrestha, A., Lee, S., Tadepalli, P., & Fern, A. (2020). Deepaveragers: offline reinforcement learning by solving derived paraameeiiiic mdps. arXiv preprint arXiv:2010.08891
Si, N., Zhang, F. Zhou, Z., & Blanchet, J. (2020). Distributionally robust policy evaluation and learning offline contextual bandits. In International Conference on Machine Learning (pp. 8884 (884-8894).: PMLR.
Sutton, R. & Barto, A. G. (2018). Reinforcement learning: An introduction. MIT press.
Tang, S. & Wiens, J. (2021). Model selection for offline reinforcement learning: Practical con- siderations for healthcare settings. In Machine Learning for Healthcare Conference (pp. 2-35): PMLR.
Tch, Y., Bapst, V., Czarnecki, W. M., Quan, J., Kirkpatrick, J., Hadsell, R., Heess, N., & Pascanu, R. (2017). Distral: Robust multitask reinforcement learning. Advances in neural information processing systems, 30.
Uehara, M. & Sun, W. (2021). Pessimistic model-based offline reinforcement learning under partial coverage. arXiv preprint arXi::2107.06226
Vershynin, R. (2018). High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press.
Wainwright, M. J. (2019). High-dimensional statistics: A non-asymptotic viewpoint, volume 48. Cambridge University Press.
Xie, T., Cheng, C.-A., Jiang, N., Mineiro, P., & Agarwal, A. (2021a). Bellman-consistent pessimism for offline reinforcement learning, Advances in neural information processing systems, 34.
Xie, T., Jiang. N., Wang, H., Xiong, C., & Bai, Y. (2021b). Policy finetuning: Bridging sample- efficient offline and online reinforcement learning. Advances neural information processing systems, 34.
Xiong. W., Zhong, H.. Shi, C., Shen, C., Wang, L., Zhang, T. (2022). Nearly minimax optimal offline reinforcement learning with linear function approximation: Single-agent mdp and markov game. arXiv preprint arXiv:2205. 155/2.
Yang, J.. Hu, W., Lee, J. D.. & Du, S. S. (2020). Impact of representation learning in linear bandits. In International Conference on Learning Representations.
Yang, J., Lei, Q., Lee, D., & Du, S. (2022). Nearly minimax algorithms for linear bandits with shared representation. arXiv preprint arXiv:2203. 15664.
12

---

Under review as a conference paper at ICLR 2023
Yang, W., Zhang, L., & Zhang, Z. (2021). Towards theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. arXiv preprint arXiv:2105.033: 0..663......
Yin, M. Duan, Y., Wang, M., & Wang, Y-X. (2022). Near-optimal offline reinforcement learn- ing with linear representation: Leveraging variance information with pessimism. arXiv preprint arXiv:2203.05804
Yu, T., Kumar, A., Chebotar, Y., Hausman, K., Levine, S., & Finn, C. (2021). Conservative data sharing for multi-task offline reinforcement learning. Advances Neural Information Processing Systems, 34.
Yu, T., Thomas, G., Yu, L., Ermon, S., Zou, J. Y., Levine, S., Finn, C.,, & Ma, T. (2020). Mopo: Model-based offline policy optimization. Advances in Neural Information Processing Systems, 33, 14129-14142.
Zanette, A., Wainwright, M. J., & Brunskill, E. (2021). Provable benefits of actor-critic methods for offline reinforcement learning, Advances in neural information processing systems, 34.
Zhang, C. & Wang. Z. (2021). Provably efficient multi-task reinforcement learning with model transfer. Advances Neural Information Processing Systems, 34.
Zhang, K., Yang, Z., & Başar, T. (2021). Multi-agent reinforcement learning: selective overview of theories and algorithms. Handbook of Reinforcement Learning and Control, (pp. 321-384).
Zhang, Z. Zhou, Y., Ji, X. (2020). Almost optimal model-free reinforcement learning via reference-advantage decomposition. Advances in Neural Information Processing Systems, 33, 15198 15207.
Zhou, Z., Zhou, Z., Bai, Q.. Qiu, L., Blanchet, J., & Glynn, P. (2021). Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference Artificial Intelligence and Statisties (pp. 3331-3339); PMLR.
Zhu, R. & Kveton, B. (2022). Random effect bandits. In International Conference on Artificial Intelligence and Statistics (pp. 3091-3107): PMLR.
Zhuo, H. H.. Feng W., Lin, Y., Xu, Q.. & Yang. Q. (2019). Federated deep reinforcement learning. arXiv preprint 18X.0.990..08277.
13

---

Under review as a conference paper at ICLR 2023
A
ADDITIONAL DISCUSSIONS
A.1 RELATED WORKS
RL has seen much progress over the past few years, particularly in its theoretical understanding (see the recent monograph (Agarwal et al., 2019) for an overview). We will discuss the most related papers in the following, with particular focus on the theoretical aspect as well as the offiin setting.
Online RL with One Environment. The majority of RL studies focus on the online setting (Sutton & Barto 2018), where the agent consistently improves her algorithm via online interactions with the environment. In recent years, many advances have deepened the theoretical understandings of online RL in interacting with a fixed and stable environment, with provably efficient designs (Azar al.
2017 Jin et al. 2018: 2020 [021a Zhang et al.) 2020; Jiang al., 2017 Dann et al. 1021).
Online RL with Heterogeneous Environments. The importance of handling heterogeneous envi- ronments well recognized. Especially, federated RL (Zhuo al., 2019) and the general multi- agent RL (Zhang et al. 2021) study the setting with multiple agents in the system, while each of them may view an agent-depend environment (Jin et al., (022). In contrast, meta-RL. ALta-RL (Sæemnndsoon) et al. 2018 Gupta et al. 2018 FFllah et al. [021] Chua et al. (021) focuses on extracting knowl- edge from previous tasks and adapting them to new (potentially different) tasks. Also, multi-task RL (Tch et al. 2017) attempts to handle multiple tasks together via information shared among tasks
(Brunskill & Li 2013 Zhang & Wang 2021 Lu et al.
2021]] Yang et al., 2020, (020,2022) or distinguish-
ing the latent structure associated with each task via past observations (Hallak et al. 2015 Kwon
jet al. b).
Offline RL with Single-source Datasets. Offline RL (Levine al.
2020) attempts to avoid poten-
tially expensive interactions with the environment as in online RL but instead use available offline
datasets collected previously. Inspired by empirical advances Yuu et al. 2020 Kumar et al.. 2020
the principle of "pessimism" is incorporated and proved efficient for offline RL (Jin et al. 2021b
Rashidinejad et al.) 2021). Especially, it illustrated that nearly optimal policy can be learned via a dataset collected by behavior policy that covers the trajectories of the optimal policy.
Following this line, Xie al. (2021b); Li et al.
2022); Shi et (2022) further fine-tune tune the designs Zanette et al. (2021); Min et al. (2021): Yin et al.
for the tabular setting, and Jin et al.
(2021b);
(2022) ; Xiong et al. (2022) for the linear MDP. For the general function approximation, additional attempts are reported in Xie et al. (2021a); Uehara & Sun (021). However, these results are mostly
information-theorrtiiaal as computational intractable optimizations are required in general.
Besides the above discussions, one particular line of research that relates to this work is under the category of offline robust RL (Zhou et al., 2021 Yang et al. 2021 Panaganti et al. 2022; Panaganti & Kalathil 2022 Si et al. 2020; Shi & Chi (022). Especially, offline robust RL learns via data sampled from one MDP and tries to output policy that is robustly good for a family of MDPs; however, our work attempts learning the hidden task from data sampled from a family of MDPs. Nevertheless, we note that it would be an interesting question to investigate whether having access to multiple data source MDPs in the target family would make offline robust RL easier.
Another conceptually relative work is Shrestha et al. (2020). In particular, it looks for similar state- action pairs with small distances in the dataset, which can be thought of as available data sources in this work. Then, the Lipschitz continuity assumption is posed, which serves a similar role as As- sumption to establish the connection between desired task information with the available datasets. From this perspective, the first term in Theorem 3.1 (Shrestha et al., 2020) can be interpreted as coming from the source uncertainty while the second term is from the sample uncertainty. How- ever, we also note that the Lipschitz continuity assumption is worst-case consideration that would not characterize the concentration of involving more data sources, which however is the key of this work.
Offline RL with Multi-source Datasets. The aforementioned advances on offline RL are mainly focused on learning from a single data source, which limits their applicability. In the offline domain, growing interests have been made to utilize data from heterogeneous sources. The most related literature falls under the framework of "offline meta-RL" or "offline multi-task RL" (Mitchell et al.) 2021 Dorfman et al. 2021; Lin et al. 2022, Li et al, 2020bbaa Yu et al., 202T). Especially, the target MDP can be viewed as learning target for the "meta-training" process of offline meta-
14

---

Under review as a conference paper at ICLR 2023
RL (Mitchell et al. 2021), which aims extract information from the available data (of multiple sources). In addition to "meta-traine mneta-trainnng". the empirically studied offline meta-RL systems often feature another step of "meta-testing", which further utilizes the learned information and applies them to a specific task. Thus, we believe this work may contribute the (currently lacking) theoretical understanding of offline meta-RL. systems, especially the meta-training process, which may also serve as the foundation for studies on the meta-testing process.
A.2 FUTURE WORKS
Coverage Assumptions. While the collective coverage assumption of Assumptions and 6 G rela- tively weak, it is still of major interest to further explore how to perform offline RI. (especially with heterogeneous data sources) under weaker assumptions. This direction particularly interesting with multiple data sources since the heterogeneous sources naturally enrich the data diversity.
Unknown Source Identities. This work considers the scenario where each data sample known to belong to particular source. One interesting direction is to investigate the scenarios without such information, i.c., unknown source identities. A potential solution is to first cluster the data samples and then adopt the algorithms proposed in this work. However, it is challenging to design provable clustering algorithms. One candidate clustering technique is developed in Kwon et al. (2021b) for the study of latent MDP, which however relies strong assumptions of prior knowledge about the source MDPs.
Personalization. As mentioned in the discussions of related work, this work can be viewed as targeting at the "meta-training" process of offline meta-RL (Mitchell et al.) (021), which extracts common knowledge from available data of multiple sources. While the extracted common knowl- edge have individual values, in many applications, an additional step of personalization is performed further use such knowledge to benefit specific task, which called the "meta-testing" process of offline meta-RI. (Mitchell et al. (021]. Based on this work, it would be valuable to further study how to perform such a personalization step with theoretical guarantees.
B LOWER BOUND ANALYSIS
Lemma 3. For any C* 2 2, it holds that
(1 C'SH3
inf
= MM]= (e.N.ge..((cl())eeee D(M..) [Gap(ft; M)] Ma)
sup
LK
Proof. We consider the case where y always generates M, M, and #1 = = Pr. = p. Then, the problem degenerates to offline RI. with one dataset directly from the target. Thus, results from the case of C* 2 in Theorem of Rashidinejad et al. (2021) can be applied to obtain the final result.
Lemma 4. For any C* 2 2, it holds that
H² L
inf $ M (ee...ee...oddelleeeeecc.. Preet))) (Cap(f;MM) =Ω
sup
Proof. This lemma is established with the following construction.
Target MDP M. We design the following family of target MDPs with two states denoted as = { 5 and two actions denotes as A = {a.g a for all steps (8) can be fixed to be 8q), which can be easily generalized to accommodate any number of states and actions:
(8g Sg (g) = p. Pn (
= 1--
(1 oz) = Pi (s as) = 0.5, wh [H];
(s)s,, = V(s, E Ax [2, H]:
T,(*, a) 1, (, a) 0, V(a, h) E A x [H].. A target MDP M with parameter p in 21 is referred M(p)
15

---

Under review as a conference paper at ICLR 2023
Data source generation distribution 9. For target M(p), the data source generation, denoted as (()), is designed as follows: with probability p. the generated MDP has P1 (1. Qg) = 1, L, (spls, (g) O; otherwise it has PP (s ag) 0, IP (Salsg 0.)) 1. The other parame-
ters of the generated MDP are the same as M.
Behavior policy Pt- For all I [L], the behavior policy Pt is specified follows: Pa.((als) dy (dls).V(e a, h) 8 A x [H]. which ensures Assumption with any C* 2
Then, with p1 = 5 and P2
6, it can be obtained that
(LMM---ooon.DDr-MMMMee [Gap R; M(p:)) = (H
(aa));
E ((Mi-ssdo)..R-MMMillee) [Gap Rt M(pz)) (H ( () [m,)))
which leads
(MMiro(o). ((p)) + ((p2)
- (BLM:-olo)) [[=]] B(Mrrolos [1 TT (a,)))
Furthermore, it holds that
E
[T (ax) + (MMarnddoo) T (ag))
2 v KL ( (M pttp://:..aaallPPPmmarooa..----. (M /2.
We explicitly write down the ratio between the two desired probabilities
P (MMregt)))D-Maeee))) (fM,, ((M,, : [L]) (P1)" (1 pI)
P (P Dj: [4]] (p2)" (1 [1 22)
where x = -iE(r
1).
As result, with ph [ 21, wh E
[ it holds that
KL (P(Miro(n)))
P1
P1
B(Meng(en)
log
+ (L - x) log
P2
1
-ppi log
P1
+ (I. Loi)
1
P1
P2
1 p2
L(p p2)
P2(1 P2)
< 16L(p) - p2)
Finally, with 5
16 v / it holds that
B(Mingle D.D (av)] (Mrr [1 - nT (ay))
1 KL (L((MMrolor1..DMMMMMlllll P (amep)).ee)l /2
which concludes the proof as
E(M J.DD [Gap( M(pi))) + E(Mi-ofoe)) B
[Gap(#; M(p2))]
1
2
H2
(II - 1) V L
Ω
L
16

---

Under review as a conference paper at ICLR 2023
C UPPER BOUND ANALYSIS: OVERVIEW
In this section, we provide an overview with the steps shared in the proof's of each proposed algo- rithm. In other words, the following results are stated for all three proposed algorithms in general. The more challenging and specific proofs for our designs are illustrated in the following sections. The basic logistics here follow the seminal work of Jin et al. (202Ib) in provably efficient offline RL.
The first step is to establish the validness of the pessimism. For different settings, various styles of pessimism are incorporated. Specifically, in this work, three penalty constructions are adopted in HetPEVI, HctPEVI-Ady and HetPEVI-Lin, respectively, As an abstraction, the validness of pessimism induced by penalties (T'((s,) a) (s, a, h) E S x A [H]] is defined in the following.
Definition 2 (Validness of Pessimism). For pessimistic value iterations using an estimated Bellman operator By and penalties (T) (8, E S x [H], valid pessimism is induced if the following event happens
3 = (Ba (1B. Vh+1 (8 BB Bwt1)))) (s, (s) S (5.
With a valid pessimism, we can obtain the following lemma.
Lemma 5. Suppose that event in Definition 2 happens, it holds that
a) = Vn+11 (s, an(s,a) E [0,2T
Proof. We observe that for any (s,a, E S x A [H], with the adopted pessimistic value iteration, it holds that
(n(s,a) = (Bn (u+1) (s, -n(ssa)
(Ba (s,a) min ( {(B2 (8, o),, - -1-1 13 min { (s. (Ba (s, + In(ss a), (Bnthtz) (s,a)}
0,
where the last inequality is due event E. Similar, for the other direction, it holds that
a)
(BaVnt) a) Qn(s,a)
(Ba Vott)) ()) - min (BB (s,a) (s - -1+ -n(( I max { BB (Br (s, a) (BaVn+z)) (s.a)+ (Bu (s, as,a)-(H -( - -H--h +1}
< 22Tx(s,a).
where the last inequality is due to event & and the fact that (BAN)+)((saa) - - - h+1.
Furthermore, the suboptimality gap the target MDP M between the output policy म and the optimal policy nt" can be generally bounded via the following lemma.
Lemma 6. Suppose that event in Definition 2 happens, it holds that
Gap(f;; <
E M (1a(sh,a))) KE[H]
Σ
Proof. It holds that
Gap(i;; (a)
Σ
EA,M (Sn, + Σ
E m ISa (Sh, ax)
he (H)
he(H]
17

---

Under review as a conference paper at ICLR 2023
Σ
Ex MM ( - (n (sN)))
+
hE(H]
(6)
2
E M (sn,
where equation (a) is from Lemma 3.1 in (Jin al. 2021b) (provided Lemma 23 and inequality
(b) is due to Lemma together with the fact that Qn (8h, takes maximum at 4n (5a) in the proposed algorithms.
ft; .M) bounded via the sum of penalties [n an) along the expected trajectory of optimal policy x²' on the target MDP M.
In other words, G
D THE HETPEVI ALGORITHM
D.1 GOOD EVENT
Lemma 7. The following event holds with probability at least 1 for HetPEVI
G = { (i) The penalties (T'((s,0)3 induce valid pessimism;
(i) (s,(s, 2 (
Proof. Part (I) is from Lemma and part (II) obtained via Lemma
Lemma 8, The penalty
H
H²
an(s,a)= =c
Σ [E[L]
+ ov (I)
T
HetPEVI induces valid pessimism with probability at least 5.
Proof. For a fixed (s, a, ft), holds that
(BAVtt) (s,a) - BA [Ba ())
fn(ss + (Ph (8) rn(,
(Ph ) (s,
Σ (r) + (Phn (s,a))= Σ
(Tn)(s,a)= + (Pr. (3)
[E[L]
[E[2]
Σ
L (T).((,a))+ + (Ph.Vn+1) (5,0)) (Iu(s,a) + IP (Pinttss,
1
le|L]
V
Σ
1
rm)(s,a)+
Σ
I
N))(s,
(e)))=
kE(K)
Σ
+ (Ph. (Tn)(s,))
(s)
L
Σ
(Pn. (s,()) (ra(s,a) + (h
L
[e[L]
(n+i(sh+ta)
Σ
1
Σ
(PheVant) (s,a)
I
ot (s.a)
18

---

Under review as a conference paper at ICLR 2023
Σ le[L]
(Tha(s,a)+ + (PhaVhez) (s.a)) (Iu(s,a) + (P (P
L
E 7, (malle,a) (PanViNt) a))
Then, via Hoeffding inequality, can be recognized that with probability at least 1 - 6,
[Br Vn+i
(8, a)
[B Vn (s, a)
Σ
H²
H +oV
Σ
H
cc
+
(3
L
L
(e(4):Na..(s.0)20
H +
H
H
Σ
+o
+
(2NN,(s,,)
L
L
(e(L))M..(s.0000
Ve(.):Nu..Gs.aa--)
H²
H²
H²
Σ
E
+ e\
(3N,,1(8,a)
L
H² ev
H2
aL
L
KE(Z]
Lemma 9. With probability at least 6, it holds that,
(s) 2 cKddf, (s. v(I,s,a, E [L] x A [H].
Proof. The proof can be done similarly as in Lemma B.3 of (Xie et al. 2021
D.2 SUBOPTIMAITY GAP
Proof of Theorems 2 and 3
By Lemma 6 and 7 with probability at least 6, it holds that
Gap(#; M)
Eg .M (sn, ax)]
AE[M]
With the individual coverage assumption (i.c., Assumption
2 it holds that
H2 (L) + V
H2
Σ Σ
(s,
L
k (s.a)ESxA
LETL
H²
H2
Σ
(8)
+ +1 V VL (KKd)((,,)))
( (EIL)
hE(H] (x.))ExxA
C-H'S
H
LK
where incquality (a) is from (ii) of event G in Lemma and equality (b) uses Assumption 2 Suuchy-Schwarz inequality.
and
With the overall coverage assumption (i.c., Assumption 3, it can be similarly obtained that
Σ Σ (s,a)
Σ LETL]
H2
H2
+ tV
(I
19

---

Under review as a conference paper at ICLR 2023
H
H
H2
Σ
Σ
th (s)
Σ
L2Kd +
Σ
N
hE[H] (s.
(ElLi (s,0))=
(c)
H
E
Σ
E
(a==T(6) (s,a)
(L Lt)Hz
+
H
LK
L
hE|H]
(s.a)Exx
=0(V
CHH
-++1-L1t Li)H
LK
L
where inequality (c) is from Assumption
E THE HETPEVI-ADV ALGORITHM
E.I ALGORITHM DESIGN
HetPEVI-Adv is designed as enhanced version of HetPEVI with Bernstein-type penalty term the sample uncertainties. Especially, it shares the same procedure as HetPEVI except that the adopted penalty is
2
(R( =c
Σ [E[L]
+
Σ (ELL)
I,2N,,(8,
(N
where (Vn.Va+) (s. a) is the empirical variance of VA+I(s) with s' ~ Pa,(,ls, a). Note that compared with HetPEVI, the variance information is incorporated HelPEVI-Adv.
E.2 THEORETICAL ANALYSIS
Theorem 6. Under Assumptions 7 satisfies
w.p. at least 6, the oulput policy & of HeiPEVI-Adv
G)) (V
C*H LK
C'H'S
CCHHS
H4
+ +VL
VLK
L2K
It is noted that the first three terms come from finite samples and the last term from finite sources. Furthermore, when LK is sufficiently larger, the first term dominates the other second and third terms; thus, in this regime, it can be observed that HetPEVI-Adv has tight performance loss to finite samples. However, the performance loss due to finite data sources still has an additional H factor, which is left open for further investigations.
E.3 GOOD EVENT
Lemma 10. Under Assumptions Z with probability at least 8, the following good event G happens, where
g= (i) The penalties (T h) ES Ax [H} induce a valid pessimism;
(8) (8) V/((s) - (
C-11' -V KT.
H14 +VT.)
((s,h) Ex [H];
(ii) (3, 2 (s, V(l, [4] x S A [I]:
(iv) (Vnif) (s, < (Va,ff +
H
V(I,s,, E [L] [H]:
Nn.(s,
(vi) (Vaf) (8, (V,J) (8, + T, h(s,a,))) 1m]
H
where f is any fixed function: S A - [- H, H..
20

---

Under review as a conference paper at ICLR 2023
Proof. Part (i) can be obtained similarly Lemma& using the enhanced Bernstein inequality proved in Lemma 26 and the rest parts are established in the following lemmas.
Lemma 11. Under Assumptions 1 with probability of at least 1 6, the following crude bound of the outpul value of HeiPEVI-Ady holds
(v
C-HAS KL +
H
(s) - Va(s)= =0
[V
V(s,a) E x [H]
Proof. It can be observed that
(Vn.Vet)
H²
H
())
Σ [E(L)
L'(Na((s,))) Sc
(2N
[E(L]
[E[L]
Using the above upper bound of (n,,a)) the lemma be obtained via similar steps of Theorem
Lemma 12. With probability least 1 ô, the following events happen, Na,((8,)) a) 2 cK (s,,),
V(I, 81,
[Z] x [H]
Proof. The proof can be done similarly in Lemma B.3 of (Xie et al. 2021b).
Lemma 13. With probability at least for a functions : S x A - H, H) the following events happen
(Tnaf) (s, & (s,a) + V Nn.(s,a)'
H1
[ [
Proof. With a union bound over (s, as a, S x Ax [H], according to Hoeffding inequality, with probability at least 1 - 5, it holds that
(Vnif) (s, - -(Vni))ss,))
(PPh - -Ph.) /²] (s,a) + (PPne-PPs)) 5l a)) [PPr + Phn)) s| (s,a)
scV (s)(s,a)
which concludes the proof.
Lemma 14. With probability at least 5. for a functions f A the following events happen
H
Proof. With union bound (s, h) E x Ax [H), according to Hoeffding inequality, with probability at least 1 - ō, it holds that
(Vna)) (8,a) (Vr,s) (s,
= [(PA - Pw) (x, + [(Pr - PP) (s, [(Pr + PP)) l (s,a)
H sc I
which concludes the proof.
21

---

Under review as a conference paper at ICLR 2023
E.4 SUBOPTIMAITY GAP
Lemma 15. holds that
Σ
Σ
0f (s.o)VAV a) H².
he[z]] (s,0)ESxA
Proof. The proof can be found in Lemma C.4 in Xie et al. (021b).
Lemma 16. It holds that
Σ
(Vn, (8,a) S L (Va (1 (s,a).
[E(T]
Proof. This lemma is a direct consequence of Lemma 28
Lemma 17. With event G happening, it holds that
C*HSSL
Σ
Σ
LHP + +oV Σ dh (8,a) (Vn.Vat1) (0,a) S (s,0)
+ cV H
K
hE(m] (5.))SxAAEET)
Proof. First, the left-hand side can be decomposed as
E
Σ
Σ
di (s, a) (Vo, (s,a)
AE[H]
=E
Σ
(s, (VnV (s,
hE[H] (s,a)
lerm (I)
+ Σ
Σ
di (s) (VaVi+t) (Va (VaVitt) (8,
AC(M] (s.0)SxAA
tern (T)
Σ
Σ
(s,0)
Σ
(V (VniV (s. (V, (s.a)
hE[H] (sa)ESxA
[E[L]
==torm (III
Σ
Σ
Σ di (s,
[VVnnVntt) (s,a) (Vn, (s,
AE[M] (s.))SSAAE(LL
:=term (IV)
Then, for term (I), with Lemma
15 it holds that
term (I) < LH?
For term (II), with event (vii) in Lemma
holds that
term (II)
Σ Σ
di (s, a ((VnVitz) (8,a) (VaVitz) (s.a))
NE(H] (s.0)ESxA
11aa L
<
Σ
di (s, L)
hE(M (s.0)ESXAA
H
cv 1
For term (III), with Lemma 16 it holds that
term (III) < 0.
22

---

Under review as a conference paper at ICLR 2023
For term (IV), obtain that
term (IV) = Σ Σ
Σ
dh (s, (Van (s,0) - -V (s,a)
NE(M (5,0)ESx.AIEjA
(a)
4H
Σ
Σ
dh (8,u) 1h-1()-
he[H]
(e.))ESxAIE())
(V
CCHHHS
C-H'S
H
cH
Σ
E
Σ
dh (s,a)-
+
LK
L
hE[H| (e.))ESxAIE(L)
C HPSL K
+ HVL
where inequality (a) is from simple algebraic based on the definition variance and inequality (b) is from part (ii) of even G in Lemma I0
Proof of Theorem 6 By Lemma and 10
with probability at least 1 - 6, it holds that
Gap(R; S
Σ
E .M (Sh, a:)].
kE[#]
Furthermore, it can be obtained that
(VnaVata) (s,a)
H
(sn, an) -
Σ
tc
Σ [E(2]
(2Nn1(8,a)
LE(T)
VnnVnn+1 ())
H²
H² (2)
Σ [E[L]
+c
+
12Nn,((,a)
I2(Nu,(s, a))3//2
(E(A]
LE(L)
as,
ce
Σ
h+1
Σ L2Nn,(s,a) + [E(L]
H
L2Nn,i(s,a)
L2(Nnu(s,a))
[E[L]
[E[L)
where inequality (a) is from event (iv) of Lemma 10
Then, for each separate term, it holds that
V (s,a)
term (I) c Σ
Σ
dh
(s,
(8,ra
he [] (s,a)E5xA
LE(L]
(Vn,Vn+t (s,
c Σ Σ
di (s,
Σ
L [2Kdf (s,
WE HE (s,0)ESXA
(ELL)
CHHS
Σ
Σ
Σ
(s) (5)} (Vadthta) (8,
IPK
hE[H] (A
C'HS
C HLSL +VH3L K
LH
L2K
CH
C'H'SL
LHH +
H
LPK
K
H²H'S
CHHSS VTK
C-HTS
+ev
LK
I2K
term := c Σ Σ
d (s.
Σ
12Nn,1(8a)
he H] (s.a)E5XA
|E(T]]
23

---

Under review as a conference paper at ICLR 2023
Se Σ
Σ
(s,a)
Σ
K
hE|H] (s,a)ESxA
[E[L]
E
Σ
(
KT.
HE (s.))Sxx
C H'S
$ vV
LK
H (N))nsss)))
term (l.c) = E E
tn (s.a)
E NE[L]
hE H| (s,0)ESxd
H4
Σ
E
of (s,a)
Σ
c
( (s,
hE[H]
(s,0)ESXA
[E|L
(
c E E
(s) = a
L2K2
he(#f] (s,a)E8XA
[E[L]
SH
VLK where inequalities (a), (c) and (d) are from event (iv) of Lemma T0 and inequality (b) is from Lemma
By aggregating these three terms together and adding the sum of source uncertainties, it can be observed that
Gap(#;:M) (V C.HOS
(VV C'H + +V
C.H'S L2K +
H
LK VLK
L
F THE HETPEVI-LIN ALGORITHM
F.1 PROPERTIES OF LINEAR MDPs
Proof of Lemmal 7 This proof is standard for studies in linear MDPs (Tin et al. 2020 2021b). We include it here for completeness and to facilitate the analysis of the next lemma. Based on the Bellman equation, it holds that
(Br.f)(s, = as) + (Pr,ff(s, ()(s,a). On. + f(s') (o(s, du)(s)))
where means that (B,,))((s (d(s, what with wh,, On,1 + Ss f(s') dun,(ss). Similar arguments hold for (B,,)(s, = (Ø(s, w/) with w/, =0 + Is f(s') dpn(s)).
First, it can be observed that the transition and reward of the sample average MDP M is linear since
Proof of Lemma 2
PA (s'(ss = Σ Pn a),
Σ
(6(s,
a), an()))
LE|L]
LE[4]
a)) Σ
Thals,al a)/L= Σ (d(s, 0n.) (6(s.)),
[E(2]
[1
where
(=)) = Σ (nn(s')/TT
0, = Σ
Ona/h T..
LE[L]
[E(L]
24

---

Under review as a conference paper at ICLR 2023
Then, verify the constraints in Definition D
||ø(s,a)]l2 - 1,
V(s,a) ESxA,
and
max(l]
||0 [2] max
Σ (E(L)
MAR (S)/L
Σ
0n.lLL
(E(N)
1
< max
II
Σ
110.1112/4
EE(L
1E(Z]
s Vd,
vh {H).
Moreover, it holds that
(B, = Fn(s, + (Pnf)(s,a)
(o(s, 0n) + / f(5') dz)n())
((s.a), Σ 0mllT.) + 5(0') ((l,,)) Σ du)n((s)/L
[E(4]
((s,a), E
(0ns+ Js 5(6') d(m))))))))))) /
LE(L]
((s,a), Σ
whi/h
(E(L]
((s a), w²h)
which proves the claim.
F.2 GOOD EVENT
Lemma 18. The following event holds with probability at least 1 8 for HetPEVI-Lin
g = (i) The penalties (T'((s,)) a}} induce valid pessimism;
(ii) ||E - End s sev K
v(,A) E x 1m]
where
Ex,1 = Epi.e [o(sn, an [
E = Σ
af (s T
KE|K]
Proof. The part (i) holds according to Lemma and and the part (ii) can be observed via the Lemma 30
In the following, for all E [H]. based on the assumption that the matrix ElE(e) Aj is invertible, we denote that
Y = (Evera Amal) "
m = Σ Enery Ar
25

---

Under review as a conference paper at ICLR 2023
With the penalties (s) ell (Vz
Lemma 19.
V //4 || ar),, in HeiPEVI-Lin,
with probability at least 1 holds that all as h)) E S A [#]
( (BhV (s, (B (1, (s, - (s,
Proof. For a fixed h and a fixed function Vn+1(-)) S - R, with Lemma 2 such that
there exists wh E R
[B Vh+1) (s, a) (ó(s, a), wn))
E
With (Ie, 1) a) (0(s, a), wn)) it holds that
BB h1 a)) a) and thus we can instead control
(Bn Vn+2 h+1 (s, a) 1(0(s, C. w.Yl [|o(s, a) a)),,, 2/,0 (00,,,
| ~/ IT, For this purpose, can observe that
||m .ullT. (wi un. (Tx)
where
(wp wn (T2)
X
E esa-1
|
06 I
With Lemma 29 we can find a e-covering C. over g with CC S (3/z)d, Using Lemma 20 and union bound, we can have that with probability 1 5, V(u, h) E C. x [H]. it holds that
((TN)) wn wa)
scH
log H (cl0))
V T.
dd
||(T,))/P/) (
1,2
doog H/(e))
dx
cc
+
L
L
With this event happening, for any E Sd-1, there exists y E Ce such that || v112 S and further it holds that
i wn lr,
max 2E84-1
(wp
uRs 1/2)
min zE84-1 yEC.
max
(whn wh. (In)) (2n) + (w0
un (Tn) -3)}
cH (Va /dlogg H (E6))
d1 V
max min 1 yEC,
+
+ +110n
-.n lrr || - 1
L2
L
dlogg dlog(H/ (Eō))
dA
< cHl
+ E ||
2x wx ll.
L
L
Thus, with E = 1/2, with probability at least - 6, vh E [H], it holds that
(1 (V 1.2 +
||w, wollT, S
scH cH
Thus, for any ()) E A. holds that
(Ba (s,a) (Ba (5+2)))) (s,a) < [|0(,, 1/lw wallTa
(VE=
d
d)
cH
+ V
With union bound over h E [M), the lemma is proved.
26

---

Under review as a conference paper at ICLR 2023
Lemma 20. For fixed vector I and fixed h E [H], with probability at least 1 8, it holds that
(ee, th - -wa)l (V
2
1log(2/8)
|0||T="
1.2
T.
Proof. It holds that
T (wh
(b..)
= x
Σ
Wh./L E
NE[L]
(E[L]
(a)
T
Σ
Moh oh (o ohi Xl wha
L
hd
[E(T.]
kE(K]
ol ah.1) (r%, + V Vati(shitall)
x
LE|L]
RE[K]
Ax
Ard who
[E|L]
term (1)
Σ KE(K]
olhha ah, (0(sh. ahi)) Twnn (rh. + Vatzloh+le))
+ x
L
[E[L]
lerm (II)
where the definition of As. and win used equation (a). For term (I), we have
> -| rr,
x
Ar.
Wha
=
Σ x T AA S L
Σ
LE(L)
[E[L]
[E|L)
(a)
dH2A
|=
AH'Ld/X= = VV
||0||| ||
where inequality (a) based on the fact that |wn,ull2 S 2H V(I, [L] [H] (which can be proved similarly to Lemma B.1 in Jin et al. (2020)) and the following observation:
Wh, ( Wh, Wh. S || 1 1 4d112/A.
For term (II), with
H V 2x Tr, log (2g))
L
conditioned on the state-action pairs at step h. have
P
L --
Σ
p(s ahi,) (d(sh, ahi Twna- - (ri + Phra(Shrii)) 22
LE[T.]
kE[K]
21
< eexp
4H EH ExE[K] to xx ATTAAoosss of ofr.))
x Ty x log(2/0)
< exxp
EiE(o) ExE[K] x. A of ( aFr)) T A
27

---

Under review as a conference paper at ICLR 2023
rr log(2/5)
< expp
ΣlE[L] ΣNE[K] x An, (b(h) ah (0,,))((0 ( o + 21) A x n 1 log (2/0)
< 2 exp
x Y x
which leads to the claim.
Lemma 21. For the penalties (s, a) oV dHz HeiPEVI, with probability at least 1 6,
holds that for all (8, a. E S A x [H]
( BBn Vh+11 (5, (
(Bn (Ba (s, a) S (s.
Proof. For fixed ((s,a) Rd and a fixed Vh+1, since (Ba,, (s, a) is bounded between [0, H and has an expectation of (IB, (s, a), then a 2018). Thus, it holds that
random variable /eeshynin
(BB (s,a) (B, vh+1) (s, a)
H2 log log(2H/6)
ev
S 8,
4h E [H].
Similarly as in Lemma 19 using a covering argument, it holds that
P (B. (s, [Bn Vnttit) (s.a) ov
dHH2
88,
( [M).
L
which concludes the proof.
Lemma 22. The penalties (+) = (x + ( (s. (s. a, h): (s, E ESX A [H)) in HetPEVI induce a valid pessimism with probability least 8 with respect to the estimated Bellman operator B, as (B,, (s) == (Ø(s, a), wn).
Proof. This result can be obtained by combining Lemmas 19 and 21
F.3 SUBOPTIMALITY GAP
Proof of Theorems
By Lemma 6 and 18
with probability at least 1 - 8, it holds that
Gap f;; M) < 2
Σ
E. (s,,
hE[#]
We denote
Σn EM (0sn, an)nnnn)sssa an)
which is positive semi-definite as En and Êr,1 for all E [H]. Correspondingly, we denote Rank, Rank(E,,) for E [H]. Also, for a positive semi-definite matrix E Rdxd we denote its ordered eigenvalues
m (Σ) 2 (E) ... 2 7d (E) 0.
With Assumption 5 when K 2 emaxn.1
{
(D')²
and À 1/T. it holds that
(Trmm (2nn))z
V
dH²
dH2
Σ E.T.M .M NE(H]
| ((sh, +
2
L
(a)
dH²
dH4
Σ
Σ Tr
FE (o(s,, an (on, Tn) A +
I
he(M]
[E(2]
28

---

Under review as a conference paper at ICLR 2023
dH
dHA
Σ [E(T] RE(d)
L he(m
m((An))
L
dHz
m(Ei/KK 1/(KL) + (E(A))
LHb
Σ
Σ
L
L
he(m]
[E[L] iE [Ranki]
dH
Σ
Σ
Σ
(En//KKK 1/(KL) +x((E// L
HHP
L
kE(m)
[E[L] ie [Ranka]
dH
LK
L
L
where inequality (a) is from the Cauchy-Schward inequality, inequality (b) is from the Von Neu- mann's 's trace inequality (Mirsky 1975) and removes the zero eigenvalues of Σn from the sum. Fur- thermore, for Rank, (implying % (En) > 0), inequality (d) from the following observation
(e) % (E 2 (EE,) - 1 - E,,lle 2 (Ex.)) VK
S
(g)
(((E)) D
C (b) (E(E))) 2
VK
D
where inequality (e) is from the Weyl's inequality (see e.g., Chapter 8 in (Wainwright, 2019 incquality (f) is from (ii) of event G in Lemma [8] inequality (g) is from the Assumption 5 D**x(En,1) from the Weyl's inequality), and inequality (h) is due to 75 (Ex) > 0, Vi E [Rank]] and the sufficiently large K.
(which implies 76 (ex)))
With Assumption 6 we can similarly obtain
V
dH² L
dH²
Σ
ExT,, .M
llo(s) anll, +
L
NE(H)
dH²
dHa
Σ
L
1/(KL) + ((()))
hE]m]
[E|L] Ve [Ranke]
dH²
D'dL
dHa
Σ
d(L - Lt)L+
+
T
K
T.
hE(M
de D*
1 LI)H
cV
LK
L
G SUPPORTING LEMMAS
H SUPPORTING LEMMAS
H.1 SUBOPTIMALITY DECOMPOSITION
The suboptimality gap between an output policy â from an offline RL algorithm and the optimal policy n² can be decomposed as follows.
Lemma 23 (Lemma 3.1 in Jin al. (2021b). Let â (nnhneun be the policy such that (n(ss)
(Qn(s,)). (-(s)) For any â and E S it holds that
Gap(#; = Σ E.M (Sh an)(s1 (0a)s1=00 = = =]+ + Σ ETT. ISn (8h5 s)
hE(H]
hE[H]
Σ NE(H]
Ex .n (Qu(sh))) x* (-1sa) tT (1((1s))) 1s1 =
29

---

Under review as a conference paper at ICLR 2023
where the expectations Ex,M and Ex .M are with respect to the trajectories induced by and n²,
and
(s)
(s,sa))
is the model evaluation envor at (s, h) E x [H].
H.2 ENHANCED EMPIRICAL BERNSTEIN INEQUALITY
In following, an enhanced version of empirical Bernstein inequality is derived. First, the famous Bernstein inequality is presented, which serves as starting point of the later generalization.
Lemma 24 (Bernstein Inequality). Let Z1, Zz. Zn be independent random variables with val-
ues Z, - E[2 I Co. Then, it holds that
(- (-
12
P
Σ
Z.
2 i=1
E
Zdl
2t 2t==20m
2> 2im1 V(Z,) + (ett
where V(Z.) denotes the variance of random variable Zz-
noted that the true variance is required in the original form of Bernstein inequality, which is hard to be obtained in practice. Thus, Maurer & Pontil (2009) established an empirical version of Bernstein inequality, where estimated variance is used instead of the true variance.
Lemma 25 (Empirical Bernstein Inequality; Theorem in Maurer Pontil 2009 Let
Z. Z1, Zz.... Zn be i.i.d. random variables and let > 0 with values 2 E I Cu. Then, with probability at least holds that
1 n1
2V(Z) In(4/)
7cp In(4/5)
E
Ze
S
n
3n
where VZ) denotes the empirical variance of Z with samples Zi, Zn
However, in Lemma 25 the samples Z.,..., Zn are i.i.d, i.e., from the same source, which do not meet the need of handling data from heterogeneous sources in this work. Thus, further enhanced version is provided in the following.
Lemma 26 (Enhanced Empirical Bernstein Inequality). Let Zi, Zz, ZZ,,, Zen be i.i.d. ran- dom variables with values Zi E 10 respectively for each I [L]. and let > Then, denoting
Σ
E
24
[E[L]
[E
1=1
with probability at least holds that
(Zi) log( 2(++))
36 (log( 2(1.+41)
ml S
12
I.2(n1)2
EE(L]
where (Z,) denotes the empirical variance of Zí with samples Zr 722.s Znnel
Proof.
With Ruin minuetr] {mu} and
4V(Z)) log! 2(L+1)
4 logg( 2(L+1)
t:
LPng
3LMmio
[E(L)
which implies that
2 2 2IELL) En ((Z))/(L'n)) + (t/Lnn)
30

---

Under review as a conference paper at ICLR 2023
12 max (iE())) V(Zi)/ (LZ))) 4t/L3mm)
22 + 1)
<log
from Lemma 24 it holds that
f 2 Di V(Z)/((Pnt) + 21/(3
P P(n 2 t) 2 exxp
I +.1 1
Furthermore, with Lemma 27 and union bound, with probability at least
L6 L+1
it holds that
2 2 Lel1
VV(z) & ViZz))
VI E [4].
the above event happens, it holds that
41 log( 2(1+1)
4 log 2(L+1)
122m.
3LMmin
LE(T)
4 (VVIZ)++ +
log LT 1
log( 2(L++1)
log 2(1+1)
12
3Lomin
[E(A]
(Z1) log( 2(1++))
16 llog( 211gt12
log( 2(+++1))
L2m
L2(n))2
3Lnmin
[ELL]
LELL]
32 (log( 2 2
(Z)) log(
2(1++1)
32 log( 211gt1)
L
L2(n))²
9L22
[ELL]
[E[L]
36 (log( (16
(Z))) log( 2(1+1))
L
L2(n))²
[ELL]
[ELL]
Combining this the bound of t with the concentration inequality proved above, the lemma is proved.
Lemma 27 (Theorem 10 in (Maurer & Pontil 2009)). Let 7, 71, ... 7n be i.i.d. random variables with values in [0, 1], and
O, with probability at least
8, it holds that
VV(Z) < ((Z)+
2 1n(
n
H.3 VARIANCE OF MIXTURE MODELS
Lemma 28. With random variable X₁ following distribution Pi for each 1 E [L], the random variable X is assumed to follow the distribution mixture, especially, Exe(n) afPi, where = "ao,",,,,, E Ar, the followings holds
CV(X) Σ af (X))) [E(L)
if
C2 ΣIED) VXi) Eie(1) (Xi)
31

---

Under review as a conference paper at ICLR 2023
Proof. For each side of the desired inequality, have
LHS = CV(X) -
Σ
B[
Σ
[x
[E(4]
HE[L]
RHS
Σ
v(x))
Σ
of
Σ
of ExX?
TE(M]
TE(T]
EE(T]
With the above expressions, can further obtain that
LHS
RHS- =
Σ
an(C - oz) - C
Σ
+ Σ
of EEX]
[E[T]
Σ ar)
of
2
a1a, E [[
LE|L]
NE[2]
Lghn
EX, 12 + EX,]
an ai [|\
Σ
af C)
atan
[E|L]
[E[L]
ai(C - a1)BB +
Σ
of C) - C Σ
04 - an) [EX)
[E[L]
[E[L]
LE|4]
Σ
(n 01) [x}
LE]L]
EE[4]
Σ - ar:C-a:)((Xi))
[EIL]
which leads to the lemma.
H.4 MISCELLANEOUS
Lemma 29 (Covering Number of a Euclidean Ball; Lemma D.5 of Jin al. 2020 ). There exists
set Ce E Rd with C. < (1 + 2R/s)* such that for all E Sd-1 x IR
|x|1a S R} there
exists a y C. with x yl12 S.
Lemma 30 (Lemma H.4 of Min et al. (2021)). Let vh S A Rd satisfying |I,s,, a)ll < cor all (s, a) E S A. For any T >> O and k > O, define GT = Ereryy 18s",, a" moss" aa)) + slaa
where (sT "'''s are i.i.d. samples from some distribution v over S x A. Then, for any E (0,
with probability at least 6, it holds that
GT
GT
4v2C²
2d log
1/2
E,
VT
32


Reviews:
[{"review_id": "kQKZi6Gacks", "reviewer": "Reviewer_HaHm", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies offline reinforcement learning with heterogeneous data sources. The paper propose a new algorithm applying pessimism to handle the randomness from both the sample and the source. It proves the sample efficiency of such an algorithm. The theoretical analysis is based on tabular and linear MDPs.", "summary_of_the_review": "Given the weakness of the paper stated above, the reviewer believes that the paper is not ready to be accepted.", "strength_and_weaknesses": "Strength: The paper studies the offline heterogeneous data sources setting, which is more practical than previous works.\nWeakness: The statement of the problem setting (learning target) is not very clear. The theoretical result seems a direct application of previous approaches on offline RL for tabular/linear MDPs. In particular, I believe the definition of underlying MDP in Definition 1 is rather confusing. From the statement, it is not clear what the reward and transition kernel of such an MDP are. Are they the reward and transition kernels of a random $ \\mathcal{M}_l$? From Definition 1, it seems that the answer is yes and the sampled $l$ can be different across different time step $h$ according to the i.i.d. statement. If this is true, it is hard to understand the real meaning of the learning target defined in Section 2.3 since such an MDP is not what will happen in the real world, but a somewhat mixture model only existing in imagination. \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "ID_IehlScjD", "reviewer": "Reviewer_LDfB", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper theoretically studies offline RL in the setting where the offline dataset is collected from multiple related but heterogeneous environments. The authors start by studying tabular setting. The paper presents the HetPEVI algorithm that combines the pessimistic value iteration (PEVI) algorithm with penalty terms that involves an aggregation of uncertainties that stem from both source and sample uncertainties. A finite-sample upper bound is proved for the HetPEVI algorithm. The authors then analyze a variant of the algorithm called HetPEVI-Adv that uses the Bernstein penalty and reference-advantage decomposition technique of Zhang et al 2020. Lastly, the authors extend the algorithm to the linear MDP setting and prove a performance upper bound for it.", "summary_of_the_review": "Despite the rigor and soundness of the problem statement, algorithmic design, and theoretical results, the insights and technical contributions of this work are limited. ", "strength_and_weaknesses": "**Strengths:**\n- The setting considered in this paper is reasonable (used in prior works such as bandit literature and Mitchell et al. 2021) and relevant to practice. Indeed, in practical settings, the offline dataset is likely to be collected from various sources.\n- Rigorous theoretical study of the heterogeneous setting is presented. The main technical contribution is an aggregation of sample uncertainties and source uncertainties.\n- Theoretical analysis provides an interesting insight into data source diversity: based on the performance upper bound, collecting samples from more data sources appears to be more helpful than collecting more data from a single source.\n\nWeaknesses:\n- Despite the fact that the exact setting considered in this work has not been studied in the past, the technical contributions and novelty are limited. In particular, the algorithm is a straightforward extension of pessimistic value iteration (PEVI) to the setting considered in this paper. Moreover, techniques such as reference-advantage decomposition and Bernstein-type penalties have been widely used in prior work.\n\n**Questions/Comments:**\n- What happens if the data sources are hidden (e.g. it is unknown whether a trajectory comes from a particular source)?\n- Providing information-theoretic lower bounds and comparing with upper bound on HetPEVI-Adv in this setting strengthens the paper.\n- It seems better to mention the paper's technical contributions on top of the Bernstein penalty and reference-advantage decomposition (such as aggregation) instead of these two techniques in the abstract.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "Fsw4YdEVMlK", "reviewer": "Reviewer_hDmb", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper aims to tackle the offline MDP challenge with the heterogeneous data source. To this end, the authors propose an underlying MDP setup where the offline data are sampled from an (iid) variation of the underlying MDP. The authors further present several algorithms and the associated analyses (for both tabular case and linear MDP case) to show that the proposed algorithms are sample efficient. ", "summary_of_the_review": "The problem is interesting but the underlying math model needs better motivation. The presentation could be improved to highlight the motivation and the technical challenges of the paper.", "strength_and_weaknesses": "\n$\\textbf{Strength:}$\n\nThe offline MDP challenge with the heterogeneous data source is important and has potential usage in practice. The algorithms are well-motivated and ready for practical realization. The analyses are well presented, with all the results discussed thoroughly.\n\n\n\n\n$\\textbf{Questions and suggestions:}$\n\n\nThe organization of this paper could be improved. I think this paper needs better motivation on the math problem it attempts to address. In particular,\n\n$\\textbf{Q1}$\nWhy do we want to solve a \"mean MDP\" (the underlying MDP) problem? How does solving such an underlying MDP contribute to the agent's performance in local environments (which the agent is supposed to serve)? Why not consider transitions and rewards with the variation that aligns with data source behavior? An ordinary (offline) RL algorithm should be able to handle such a problem. \n\n$\\textbf{Q2}$\nIn Definition 1, why are $r_{h, \\ell}$ (same for $P_{g, \\ell}$) identically distributed across (h, \\ell)? Does the analysis hinge on such an identical assumption? Given the motivation in the introduction, I think a more natural setting is if $r_{h, \\ell}$ are different distributions for different $\\ell$ due to the data source preference. They could still share the same mean, though. In addition, Definition 1 casts restrictions on the set of MDPs (iid distribution), so it is not exactly a definition of underlying MDP but a definition of both underlying MDP and the associated MDP set. The authors may clarify such a point for revisions to avoid misunderstanding.\n\n\nBesides, the extensions with the Bernstein-type technique and linear MDPs are less important and can be put into the appendix.\n\nIn addition, I have several inquiries.\n\n$\\textbf{Q3}$\nThe technical contribution seems marginal, given the results in, e.g., [1][2][3] (and the numerous previous Hoeffding- and Bernstein- type analyses of tabular and linear MDPs) and that all the rewards and transitions are iid distributed. Could the authors highlight their analysis's technical challenges and subtle parts, comparing against [1][2][3]?\n\n$\\textbf{Q5}$\nIs the achieved sample complexity in Theorem 1 optimal? What would be the lower bound for such a type of problem?\n\n$\\textbf{Q5}$\n(Minor) Assumption 1 seems strong for such a problem. Is it necessary that data collected from each element of the MDP set has to explore the environment sufficiently well? Is it possible that they do not have good coverage individually but together cover the underlying MDP sufficiently well?\n\n[1] Jin et al., Is Pessimism Provably Efficient for Offline RL? (2021)\n[2] Rashidinejad et al., Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism. (2021)\n[3] Ming et al., Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. (2022)", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "BzRjr3yFSn8", "reviewer": "Reviewer_cUra", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper sheds some theoretical light on the problem offline RL with data sets from heterogeneous sources; which closely relates to the field of meta- Reinforcement Learning. Here they pose this problem as learning an underlying Markov Decision Process (MDP) M from samples of multiple randomly perturbed variation of M. To this end the authors propose, HetPEVI as a method to jointly consider the uncertainties that arise from the limited data samples as well as the limited number of perturbed MDPs that we sampled the data from. The authors build on HetPEVI to propose HetPEVI-Adv which theoretically allows for less conservative estimates by incorporating priors for sample independence and shared variance information. Finally, HetPEVI-Lin is introduces as a specialized adaptation of HetPEVI for linear MDPs that builds on the linear formulations of original PEVI and uncertainity quantification of HetPEVI.", "summary_of_the_review": "Overall the paper nicely extends the original work of PEVI to the setting of heterogeneous datasets in a principled manner. I am leaning towards accepting the paper as it provides principled theoretical foundations for offline RL with heterogeneous sources albeit having some empirical results for some real world problems would bolster the paper greatly.", "strength_and_weaknesses": "I am curious on how these theoretical results compare to other offline RL theory that lower-bounds the  on the Value with lipschitz continuity assumptions over the transition and reward dynamics, i.e. the DeepAveragers framework[1]. As the Averagers framework already treats the seen rewards as samples of the underlying MDP, the Lipschitz constant over the formulation with heterogeneous datasets will simply be the max(Constant from Sample Uncertainity, Constant from source uncertainty). This also points out to the underlying notion that given the Constant for Sample uncertainty may be higher and hence it may be better to have diverse data sources over larger data samples. I would love to know your thoughts on how and if these two lower bounding approaches connect with each other.  \nMoreover, I understand that the limited data sources incur an additional performance loss that cannot be reduced by increasing the amount of data samples. However, It would be nice to know if there was some elaboration on when is it very important to have data from multiple sources. For example I can imagine that if the variance between sources is zero, the data samples from a new source or an old source should count the same.\n\n [1] Shrestha, A., Lee, S., Tadepalli, P., & Fern, A. (2021). DeepAveragers: Offline Reinforcement Learning by Solving Derived Non-Parametric MDPs. ArXiv, abs/2010.08891.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}]

Author rebuttal:

Decision: Reject