Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This work target the setting of offline reinforcement learning with some extra data (without reward) sharing setting. This work proposes a revised reward function to keep the pessimistic property of the algorithm and design the algorithm in linear MDP and general MDP cases. Through different experiments, it shows the performance is better than baselines with some other data-sharing methods.
strength_and_weaknesses: Strength:
1. It proposes a different reward estimation method to keep the pessimistic property of the algorithm and evaluate the proposed method PDS to 3 baselines in many different experimental settings to show the performance.
2. It has a reasonable theoretical analysis of the intuition of why data-sharing works better than no data-sharing in linear MDP cases.

Weaknesses:
1. The theoretical results do not support the main contribution of this work. It seems the main contribution of this work is the designing of the estimated reward minus a confident interval and it works better than other data-sharing methods such as letting the reward be 0 or using a learned reward function to label the reward in the extra dataset. So the theoretical results should support that the proposed reward design in this work will have better results than other data-sharing methods. However, the theoretical results only support that with reward designing, it works better than no data-sharing.
2.  Seeing the main contribution of changing $r(s,a)$ to the reward designing in Equation 15, we know that the proposed reward has an additional parameter $k$ that can be tuned with comparisons to other baselines. But from my understanding, $k$ should keep the same for all the experiments to show that there exists some universal constant that will work in a lot of settings but not need to be tuned a lot for all games. However, it seems different $k$ is used in different games when the proposed methods is conducted to compare with other baselines. This seems not fair. For instance, DQN use the same parameters for all 57 Atari games and works well [1].

[1] Mnih, Volodymyr, et al. "Human-level control through deep reinforcement learning." nature 518.7540 (2015): 529-533. 

clarity,_quality,_novelty_and_reproducibility: -Some minor questions for Clarity:
1. In Definition 3.1, the episodic MDP should be finite as $(S,A,P,r, H)$, so it actually means discounted infinite-horizon MDP?
2. In Page 3: what is $\psi$ under equation 1?
3. In Equation 3: what is the $s'$ come from? Is it determined by $(s,a)$?
4. Does $\Lambda$ under Equation 9 need to be normalized by $N_0$?
5. What is $k$ in Equation 15?

-The writing is clear and easy to follow and the experimental results are provided with a lot of details and seem easy to reproducibility.

-For originality, it seems the main contribution is the design of the reward. However, it seems the performance is not convincing enough since different parameters are required in different games.
summary_of_the_review: This is a very interesting work that targets data sharing in offline RL. However, the experimental performance of the proposed main technical reward design is not convincing enough to show that it can work better than other baselines since it uses different parameters $k$ in different games. The experiments didn't show that there exists a universal $k$ that works generally better than the baselines.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper proposes an offline RL method for the setting where the agent is additionally provided a dataset of reward-free transitions. Different from prior work, this method imputes the rewards for those transitions using a lower confidence bound. Empirically, the proposed method outperforms a prior method that uses 0 for these reward-free transitions. The paper provides theoretical results showing that the suboptimality of the learned policy can be decreased by using these reward-free transitions.
strength_and_weaknesses: Strengths
* The proposed method is very simple
* Empirically, the proposed method achieves great results

Weaknesses
* I'm not sure that the main theorem actually proves the claim in the title (that unsupervised data sharing is provably useful). The issue is that Theorem 4.3 only provides a _bound_ on the suboptimality. The bound decreases when we make use of unlabeled data.
However, if the bound isn't tight, then decreasing the bound doesn't necessarily mean that the unlabeled data is useful. As a toy example, the bound $\frac{2 r_\text{max}}{1 - \gamma} + N_0 + N_1$ is also a valid (and vacuous) bound on the suboptimality. This bound _decreases_ if we reduce the amount of labeled and unlabeled data, suggesting that we should throw away all the data. 
* I'm unsure whether the analysis about the suboptimality ratio in Eq 13/14 is solid, for the same reason as above. If this bound isn't tight, then this ratio might be meaningless.
* The clarity of the writing could be improved (see details below)
* I'm unsure how bad the reward prediction baseline actually is, _if it is very well tuned_. For example, it might be important to use high-a capacity prediction network; it might be important to use the same ensemble as the proposed method; it might be important to use early stopping to prevent overfitting. I think that showing that _even a very tuned_ reward prediction method can fail would strengthen this paper.


Additional comments
*  Title -- I'm not sure "Provable" is being used correctly. Typically it refers to a claim that could be proven; saying "this provable theorem" is grammatically correct, if redundant. I'd recommend changing the title to something like "The Provable Benefits of..." or "Theoretical Gaurantees for ...." or "A Theoretical Justification for ..." [Though, see comment above about the correctness of these claims.]
* "obviating" -> "reducing" -- Presumably, the method still needs some annotations.
* "merit" -- Which merit? Perhaps rewrite as "Like self-supervised methods in other areas of ML, we would like self-supervised RL methods that can ..."
* "in a supervised manner" (in abstract and intro) -- I found this statement a bit strange, as it it were arguing that offline RL were equivalent to supervised learning. Perhaps behavioral cloning methods can argue this, but I don't think most offline RL methods are "supervised" in this way.
* "is highly preferred" -- Preferred to what alternative?
* "can be costly and requires huge human efforts" -- Cite.
* "CV, NLP" -- No need to define acronyms if they aren't used again
* "which is even worse than labeling the unsupervised dataset with all zeros" -- I might be misremembering the UDS paper, but this seems like a misrepresentation of this prior work. I'd recommend a more generous statement (e.g., "Prior work has shown the learning to predict the rewards can be challenging, and that the simple approach of setting the reward to zero can achieve good results.")
* "How can we leverage unlabeled data" -- Perhaps clarify that "unlabeled" means reward-free, not action-free.
* "reduced to some sort of linear bandits" -- I didn't understand this during the first pass; perhaps add more context, or wait to introduce this to the theoretical section.
* "as shown in Algorithm 3" -- Broken reference? Algorithm 3 doesn't appear in the main text.
* "The coverage coefficient represents the maximum ratio ..." -- How does this relate to the ratio of the state occupancy measures, $\rho(s, a)$?
* "How to leverage" -> "How can we leverage"
* "we have the following lemma" -- I would highly recommend adding a few sentences describing what the result will say and providing some intuition, before stating the formal result.
* "Lemma 4.1" -> "Lemma 4.1 [Abbasi-Yadkori]" -- Make clear that this is not a contribution of this paper
* Eq. 8 -- Where is $\hat{\theta}$ defined?
* "model-based approach with different amounts of pessimism" -- This "strawman" approach is described on page 4 and in the introduction. I found it a bit odd because it was unclear whether this was referring to a specific prior method. I'd probably just cut this, and direct the comparison to be with UDS/CDS.
* "summarized in Algorithm 1" -- Add a paragraph introducing the method first. Something like "We now introduce our method. We do ... We summarize our approach in Algorithm 1."
* "set as in Equatoin 11" -- Broken reference? Eq 11 hasn't appeared yet.
* "bi-level optimization problem" -- I'd recommend writing out what this problem is. As written, Eq 11 doesn't look like a bilevel optimization problem.
* Eq. 9 -- Why do we need to clip the reward $\hat{r}$ to be positive? Is this motivated by the theory?
* Lemma 4.2 -- I'd recommend writing out the result in words, before stating the math.
* Eq. 11 -- Where is $\hat{V}$ defined? (I.e., is it the solution to some other optimization problem/procedure?)
* Theorem 4.3 -- Does this make the linear MDP assumption? If so, I'd recommend mentioning it.
* Theorem 4.3 -- Does this theorem also apply to simple (non-pessimistic) reward prediction methods?
* Theorem 4.3 -- When is this bound non-vacuous? E.g., if $\sqrt{d^2 \zeta_2 / (N_0 C_0)} > 1$, then this is vacuous; so, when will this square root be much less than 1?
* "This means that ..." -- Great intuition!
* Eq 15, Eq 16 -- I was confused which method was used in the analysis, and which was used for the main experiments.
* For all experiments, I'd recommend increasing the number of random seeds to 5.
* Table 2 -- It's a bit non-standard to show separate performance numbers for different goals. I'd recommend just showing the standard evaluation numbers, so that they are comparable with the numbers reported in prior work.
* Fig -- Increase figure resolution. What is the "Learn" line?
* Fig 2 -- I was a bit confused what to learn from this plot; at face value, it seems to indicate that UDS is the best
* "statistics(exact" -- Missing space in one of the citations.
* "Training agent for first-person" -- Missing journal/identifier in this citation.
* Table 4 -- This table seems to indicate that CDS+UDS is the strongest baseline. I'd highly recommend including the strongest baselines in the main text.
* Table 4 -- What does the "Learn" method correspond to?
clarity,_quality,_novelty_and_reproducibility: Clarify -- Generally the paper is easy to follow. I have left some writing suggestions above.

Quality -- I really like the simplicity of the underlying idea. I have a few issues with some of the claims (e.g., do they actually show that unsupervised data sharing is good? do they also apply to the reward prediction baseline) that would be good to clarify.

Novelty -- The method is a novel extension of prior reward prediction methods.

Reproducibility -- The appendix does not contain details/hyperparameters, but the supplemental material contains code with documentation.
summary_of_the_review: Overall, I think the proposed method seems quite promising -- a really simple way for making use of reward-free data. I appreciate that the paper contains theoretical results, too, to supplement the empirical results. I have a few concerns/questions noted above. If these are addressed, I will vote for accepting the paper.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes provable data sharing (PDS) for leveraging reward-free data for offline RL. The algorithm amounts to constructing a pessimistic estimate of the reward function, relabeling all available data with those pessimistic rewards, and then running standard offline RL. This is shown to be provably efficient in linear MDPs and extended to the deep RL setting via an ensemble of reward models to estimate the pessimistic reward. Empirical results show improvements over MLE reward models and the UDS algorithm which labels all new data with zero reward.
strength_and_weaknesses: ### Strengths

1. The paper provides a novel and simple approach to the important problem of leveraging reward-free data for offline RL. In particular, it is novel and useful to show that a simple reward penalty can suffice to incorporate reward-free data into offline RL.

2. The paper provides a theoretical analysis of the algorithm in linear MDPs that shows the provable benefits in a simplified setting.

3. The paper also is able to scale the algorithm up to a deep RL variant that shows strong empirical performance on a substantial variety of tasks.

### Weaknesses 

1. The theory is not quite complete. The proof of the main novel contribution bounding the gap between the estimated reward and true reward that yields the asymptotic term in the result is omitted "for simplicity" in Appendix B/C. I think that this shouldn't be a serious problem, as intuitively the result seems to hold, but a complete proof ought to be provided. In particular, my understanding is that the bound that is omitted is to bound the difference between the V^{\pi^*}_{\theta^*} - V^{\pi^*}_{\tilde \theta} (also there is a typo in the appendix, in the last line of the align in appendix B, it should be $ d^2$ in the first term instead of $d$ to match the main text, but this is also the term where the proof is missing). Intuitively, this can be bounded by unrolling $\pi^*$ and bounding the difference between true and estimates rewards at each step, yielding some term that depends on $ \alpha $ times the sum of the feature norms, but this needs to be worked out explicitly. It is also a bit confusing to me why so much space in the appendix is spent proving Lemmas C.1 and C.3, which seem to not be novel to this paper and could perhaps be cited from prior work(let me know if I missed some detail that makes them different). 

2. There is an issue with hyperparameter tuning in the experiments. Essentially, the two main baselines are UDS and prediction which correspond to special cases of the proposed PDS algorithm (UDS is PDS with $ k = \infty$ and prediction is PDS with $k = 0$). This itself is not a problem, as it is nice to have more general algorithms with improved capabilities. The problem is that it seems that the experiments rely on (potentially extensive) tuning of the $ k$ hyperparameter for PDS while the baselines have no such hyperparameter since they correspond to special cases. First, I would like to see a better description of how the hyperparameter was tuned. Appendix G lists the final values that were used, and they seem to be unique for almost every task, suggesting that some tuning method was used, but no explanation is given. Second, I think there ought to be a more straightforward discussion in the presentation of the algorithm that PDS is a generalization/unification of UDS and prediction and that thus it is not surprising that tuning $k$ yields better results than either baseline.
clarity,_quality,_novelty_and_reproducibility: The presentation is clear, high quality, and novel up to the issues raised above.

In terms of reproducibility, the code is included and hyperparameters are included in the appendix to reproduce the results, but I have not tried to run it myself.
summary_of_the_review: Overall, I really liked the core idea of the paper and think that the presentation is solid. There are two key weaknesses that I raised in my review. The issue with the theory should be easy to resolve. The issue with hyperparameter tuning seems to be somewhat more fundamental and should be addressed, but is not a fatal flaw. I will rate the paper as a weak reject for now, but am happy to improve the score to accept if the authors address the issues I raised.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: Strength: 

---"It proposes a different reward estimation method to keep the pessimistic property of the algorithm and evaluate the proposed method PDS to 3 baselines in many different experimental settings to show the performance."
--- It has a reasonable theoretical analysis of the intuition of why data-sharing works better than no data-sharing in linear MDP cases.


Weakness: 

---"The clarity of the writing could be improved"

--- "The theory is not quite complete."

--- "There is an issue with hyperparameter tuning in the experiments."


In particular, at least two reviewers mentioned the issues with different hyperparameters for different environments. 
justification_for_why_not_higher_score:  At least two reviewers mentioned the issues with different hyperparameters for different environments. Also two reviewers mentioned that "the theory is not quite complete." Therefore, the reviewers are not as excited by the paper as the averaging score indicates. 
justification_for_why_not_lower_score: Strength: 

---"It proposes a different reward estimation method to keep the pessimistic property of the algorithm and evaluate the proposed method PDS to 3 baselines in many different experimental settings to show the performance."
--- It has a reasonable theoretical analysis of the intuition of why data-sharing works better than no data-sharing in linear MDP cases.
Decision: Accept: poster