Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies offline RL problems with perturbed rewards. In particular, the Q function will be parametrized as the minimum of $M$ neural networks, trained on $M$ perturbed datasets. The benefit of the proposed algorithm, compared to the UCB-based method is reducing the time complexity of action selection. On a technical side, the authors propose a data splitting analysis technique to improve dependence on log covering the number in the sample complexity result.
strength_and_weaknesses: Strength:

The proposed neural network-based offline RL algorithm is new. In appendix B3 the authors compare with existing literature on the sample complexity results. 

Weakness:

I did not spot any major errors in the paper. However, I have several minor technical questions:

Q1. In line 10 of Algorithm 1, shouldn't we take argmax over action space?

Q2. A related question is, how is the argmax implemented in code since we are considering the large space-action space?

clarity,_quality,_novelty_and_reproducibility: The paper is clearly written with sufficient novelty.
summary_of_the_review: The idea of learning Q functions from the perturbed datasets and thus implicitly implementing the pessimism principle is neat. Theoretical analysis and preliminary experiments illustrate the potential usefulness of the proposed algorithm. I suggest a marginally accept. However, I'm not familiar with the main related papers cited in this work, so I choose a confidence score of 2.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper looks at the problem of reinforcement learning from offline data.
They authors introduce PERVI, which uses "randomized value functions" to generate an approximate posterior distribution over value functions, and then acts pessimistically with respect to those estimates for safety.
The authors support their new algorithm through an analysis in tabular MDPs, as well as more empirical evaluation with neural network function approximation.
strength_and_weaknesses: There are several things to like about this paper:
- The problem of RL and decision making with offline data is an important one for the community.
- The PERVI algorithm passes a "sanity check" intuitively... by this I mean that it's not just an algorithm for a proof... but you have a sense this is something close to something someone would actually want to use.
- The quality of the writing and presentation in the paper overall is very high.
- The paper has a progression of intuition, to hard theoretical guarantees in simple settings, to empirical success in more complex settings. I like the way of analysing problems with overparameterized NTK!
- Discussion of related work and the key intuitions for the approach appear to be pretty comprehensive for a short paper, although I am likely missing important pieces.

There are some places where the paper probably could be further strengthened:
- In some sense, many of the results and analyses are sort of incremental. The application of randomized value functions plus pessimism has existed before, but this is a slightly new twist on that as opposed to a "game changing" new perspective.
- Some of the ways the Theorems are presented are really messy... you need to read through lines and lines of bizarre constants/terms to even get to the result!
- Something must be missing (at a high level) from these theorems, since they don't really expose clearly a dependence on the *quality* of the offline data... an algorithm should be able to learn very differently when the demonstration data is very good, versus when it is very bad... and a good algorithm should be able to kind of work that out and leverage it.
- Why do you use the term "SubOpt" instead of regret?
- Does PERVI (pervy?) raise some of the issues that NeurIPS (nips) had to deal with?
clarity,_quality,_novelty_and_reproducibility: Overall I think the paper scores highly across these attributes.
summary_of_the_review: This paper presents PERVI, a combination of randomized value functions with pessimism for offline reinforcement learning.
The paper takes mostly-existing concepts but combines them in a more elegant and coherent framework than previous papers I have seen.
The resultant algorithm is sane and sensible, and the progression of support from intuition to analysis to empirical results is comprehensive.

In terms of "the grand challenge" of offline RL I think this algorithm leaves potentially a lot of value on the table.
However, I do think this is a valuable piece of the literature and will be useful to the conference.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes the PEturbed-Reward Value Iteration (PERVI) which combines the randomized value function idea with the pessimism principle. PERVI only needs $O(1)$ time complexity for action selection while LCB-based algorithms require at least $\Omega(K^2)$, where $K$ is the total number of trajectories in the offline data. It proposes a novel data splitting technique that helps remove the potentially large log covering number in the learning bound. PERVI yields a provable uncertainty quantifier with overparameterized neural networks and achieves an $\tilde{O}(\frac{\kappa H^{5/2}\tilde{d}}{\sqrt{K}})$ sub-optimality. statistical and computational efficiency of PERVI is validated with an empirical evaluation in a wide set of synthetic and real-world datasets.
strength_and_weaknesses: Strength: This paper combines the randomized value function idea and the pessimism principle. In addition, this paper proposes a novel data splitting technique that helps remove the dependence on the potentially large log covering number in the learning bound. The authors empirically corroborate the statistical and computational efficiency of our proposed algorithm in a wide set of synthetic and real-world datasets. 

Weakness: 1. Your assumption 5.1 requires for any $H+1$-bounded function, Bellman update maps it to $Q^*$. What will happen if your function has $\epsilon$-misspecified error, i.e. $\inf_{V}\sup_{||V'||_\infty\leq H+1}\|\|B_h V-V'\|\|_\infty \leq \epsilon$, how will the $\epsilon$ model error affect your results? You don't need to derive the result for this case but explain in a few sentences is fine.

2. While Appendix B.1 already provide a nice comparison with Xu&Liang,2022, they consider a different setting where only trajectory reward is observed. If the per-step award is aware, how would their result be like and how would it compare to PERVI? I am asking this since in your setting per-step reward is aware, so I am wondering which of the two methods would be better under this case.

Minor: The recent paper https://arxiv.org/pdf/2210.00750.pdf also considers the pessimism offline RL with parametric function class. How is your result compared to theirs since both results contain the similar measurement $\sum_{h=1}^H ||g(x;W_0)||_{\Lambda_h^{-1}}$ in the suboptimality bound? 

clarity,_quality,_novelty_and_reproducibility: The writing of this paper is clear and the quality of this paper is high. 
summary_of_the_review: This paper overall has a high quality and provides complete study of neural network approximation for offline RL. If the authors can address my concern in above, I am happy to keep my score.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper proposes a novel approach to pessimism-based offline RL. Instead of the standard practice of explicitly constructing a lower confidence bound for value functions, this new approach uses perturbed rewards to implicitly quantify the training uncertainty and construct lower confidence bounds for the ground truth. Such an approach is argued to improve the practicality of pessimistic offline RL especially in situations where the value functions are approximated by large neural networks, whence the large scale model elucidates traditional theoretical analysis. The theoretical property of this approach is studied in overparametrized neural networks with gradient descent training. Empirical experiments are conducted to show the favorable performance of the proposed approach. 
strength_and_weaknesses: Strengths:

1. A novel algorithm to pessimism. 

This work contributes to the literature of offline RL by proposing a solid and practical approach to constructing confidence lower bounds. This idea is clever and refreshing. It is both practically useful and theoretically interesting. 

2. Solid theoretical results.

This paper provides solid theoretical analysis. It is quite invovled but I think it will be useful for future works in the literature. 


Weaknesses:

1. Clarity of results. 

A drawback (which I think can be resolved to some extent) is that although the overall idea is clean, the presentation is way too overwhelming. For example, it will help the readers if important steps in the algorithms can be explained / highlighed / commented, or given more wording in explaining their roles. Also, Theorem 1 poses a huge challenge to the whole flow as the conditions are too complicated. I will suggest replacing it with an informal theorem, and put all these conditions to the appendix. 

2. Relation to the literature. 

Although the authors generally did a good job in relating to the literature, more discussion on the novelty of this idea can further improve this work and posit this paper appropriately in the literature. For instance, 1) how does the construction of uncertainty quantification differ from that in the online setting (e.g., Jia et al. 2022)? Is there special tricks for dealing with distribution shift? 2) how does the analysis of 2-layer neural networks rely on existing ones, and which parts are specific to the new offline setting? etc.

Questions:

1. Since $\mathcal{Q}^*$ is used for fitting the networks, I am curious about the definition of $\mathcal{Q}^*$. Is it equivalent to the class of 2-layer neural networks with ReLU activation, or is it a superset of it? 

2. What is the relationship between $\mathcal{H}_{ntk}$ and the class of 2-layer NN with ReLU activation? Please clarify this to help the readers.

3. The conditions in Theorem 1 are too lengthy. Is it possible to reduce it to a cleaner version (potentially with some harmless relaxation)?

4. It will help if there is a sketch or overview of the key theoretical techniques in Theorem 1. For example, why do the randomized rewards lead to a valid uncertainty quantifier. 

Minor issues: 

1. The last sentence in Section 4 is difficult to read. What does it mean by `` with a provable implicit uncertainty quantifier and $\tilde{\mathcal{O}}(1/\sqrt{K})$''?

2. Remark 1 is a bit difficult to read. What does it mean by ``data-dependent quantity that measures the number principle dimensions over which the.."?

3. What does $\sigma'$ mean in Definition 1? Please provide a formal definition.


clarity,_quality,_novelty_and_reproducibility: This paper is of high quality in general. The theoretical analysis and empirical results are solid. 

The paper is clearly written and properly posited in the literature. 

Though the idea of randomized rewards and pessimism have appeared in the literature, the idea of combining them and the theoretical / practical considerations therein are fresh. 
summary_of_the_review: I find this to be a strong paper. The idea of using randomized rewards in pessimism-based offline RL is clever, and the theoretical analysis is nontrivial and solid. Empirical studies are conducted to support the arguments. However, I think the presentation of the results can be improved, and more discussion on the relation to the literature is need.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This work considers an offline RL policy search which fuses randomized value function estimation with the pessimism principle to develop a unique algorithm for this setting. It exhibits strictly tighter sample complexity than prior results, and exhibits explicit dependence on the data quality of offline data. Reviewers consistently concluded the merits of the technical execution both theoretically and in experiments. 
justification_for_why_not_higher_score: NA
justification_for_why_not_lower_score: NA
Decision: Accept: notable-top-25%