Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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. 
strength_and_weaknesses: 
$\textbf{Strength:}$

The 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.




$\textbf{Questions and suggestions:}$


The organization of this paper could be improved. I think this paper needs better motivation on the math problem it attempts to address. In particular,

$\textbf{Q1}$
Why 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. 

$\textbf{Q2}$
In 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.


Besides, the extensions with the Bernstein-type technique and linear MDPs are less important and can be put into the appendix.

In addition, I have several inquiries.

$\textbf{Q3}$
The 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]?

$\textbf{Q5}$
Is the achieved sample complexity in Theorem 1 optimal? What would be the lower bound for such a type of problem?

$\textbf{Q5}$
(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?

[1] Jin et al., Is Pessimism Provably Efficient for Offline RL? (2021)
[2] Rashidinejad et al., Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimism. (2021)
[3] Ming et al., Near-optimal offline reinforcement learning with linear representation: Leveraging variance information with pessimism. (2022)
clarity,_quality,_novelty_and_reproducibility: See questions above. The reproducibility of proof is justified by the appendix.
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.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
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.  
Moreover, 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.

 [1] Shrestha, A., Lee, S., Tadepalli, P., & Fern, A. (2021). DeepAveragers: Offline Reinforcement Learning by Solving Derived Non-Parametric MDPs. ArXiv, abs/2010.08891.
clarity,_quality,_novelty_and_reproducibility: -
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: 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.
strength_and_weaknesses: **Strengths:**
- 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.
- Rigorous theoretical study of the heterogeneous setting is presented. The main technical contribution is an aggregation of sample uncertainties and source uncertainties.
- 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.

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

**Questions/Comments:**
- What happens if the data sources are hidden (e.g. it is unknown whether a trajectory comes from a particular source)?
- Providing information-theoretic lower bounds and comparing with upper bound on HetPEVI-Adv in this setting strengthens the paper.
- 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.
clarity,_quality,_novelty_and_reproducibility: The paper is relatively clear and the results are rigorous and sound. The novelty and technical contributions of the paper are limited. 
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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: 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.
strength_and_weaknesses: Strength: The paper studies the offline heterogeneous data sources setting, which is more practical than previous works.
Weakness: 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. 


clarity,_quality,_novelty_and_reproducibility: As stated above, the paper problem setting of the paper is not clear enough for the reviewer to evaluate the strength of the results. With a rough guess of the problem setting, the reviewer believe that the result does not bring any insight. The design of the pessimistic algorithm is not novel given previous works in offline RL.
summary_of_the_review: Given the weakness of the paper stated above, the reviewer believes that the paper is not ready to be accepted.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper addresses offline reinforcement learning with the heterogeneous data source, where each MDP is considered as sampled iid from and underlying MDP.  The proposed HetPEVI algorithm accounts for both the sample uncertainty per data source and the source uncertainty.  An improvement called HetPEVI-Adv was further proposed that employs Bernstein penalty and reference-advantage decomposition.  Extension to linear function approximation was also presented.

The paper addresses an important setting in offline RL.  The presentation needs much improvement, including the exact problem setting.  The technical contribution and novelty also requires better clarification.  Overall, the paper needs another round of revision and review.
justification_for_why_not_higher_score: The presentation needs much improvement, including the exact problem setting.  The technical contribution and novelty also requires better clarification.  Overall, the paper needs another round of revision and review.
Decision: Reject