Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper proposes a re-weighting of the Bellman update for offline RL, using the variance term, that leads to an improved bound for offline RL. The paper is well written and easy to follow, with the key improvement (theoretically) easy to see. The core idea of the algorithm is a simple trick to re-weight the update and the analysis follows as in other offline RL works examining the statistical significance for offline value estimation.



main_review: Overall comments : 

- This paper focuses on the problem of understanding statistical limit of offline RL algorithms, under linear representations. The authots propose a variance aware approach for offline RL, which leads to the pessimistic value estimation. The idea of pessimism has been extensively studied for offline RL recently. 
- The core idea of the algorithm is to use the variance term, to re-weight the Bellman updates - and provide improved bounds for offline RL). The paper exploits the reweighted Bellman update, which leads to the improved bounds. 
- Recent works has studied the statistical limits for offline RL (Wang et al). This paper can be seen as a follow-up along those lines, studying the limits for offline RL under linear MDP assumptions. As pointed out, even though several works already address this (e.g Jin et al 2021), they all use the standard Bellman update leading to the bound for offline RL. In contrast, this paper uses the pessimistic value, based on the variance, and argues that the re-weighting is helpful for improving bounds. The core idea is to modify the LSVI update with a variance weighting term and an additional pessimism bonus.
- The paper is well written, and section 3 is quite easy to follow. Most importantly, it is great to see example 3.1 where the authors clearly state how existing results that equally weighs the samples has dependency on the H factor that this work is trying to avoid. More importantly, the comparisons with previous works are useful to get an understanding of the contributions of this work. 



Few weaknesses of the work  and negative comments : 
- I am not an expert in following the proof details of this work; therefore the comments below are not on the technical details of the proof. 
- My overall impression of a work like this is that - the variance penalty term and the re-weighting of the Bellman update does not necessarily give better insights about offline RL, other than the fact that it helps improve the bound. This is similar to any other empirical works, which can re-weight the Bellman update and claiming to have improved results. 
- What is the key novelty in the paper that leads to the improved bound? Is there a specific technical novelty introduced in the proof that leads to the improved result? Can the authors point this out exactly?
- Otherwise, simply re-weighting the update and following similar analysis as in the vast majority of works studying offline RL theory is not a significant contribution and does not lead to new insights. The Bellman re-werighting idea has been well studied and exploited in many previous empirical works in RL. 
- How does the variance term help for offline RL? To me, it seems like the idea is a nice trick to include the variance term in the update. I do not see any bottlenecks to try this out empirically in any existing offline RL algorithm on any benchmark task like D4RL? I believe this update will be quite easy to plug in, and it would be nice to examine the significance of the variance and re-weighting term. 


summary_of_the_review: I do not think without experiments, the work has enough technical and theoretical novelty (in terms of proof details) for acceptance. Simply improving the bound, by re-weighting the update and following similar analysis as other offline RL works do not, in my opinion, pass the criterion. I may be wrong, as I am not an expert in following the technical proofs of the paper.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies an extension of value-based pessimistic offline RL in linear settings, where variance information is included in the pessimistic penalty to provide a refined quantification of uncertainty. Although a little restricted to the behavior policy setting, careful treatment of uncertainty leads to improved suboptimality bound than the literature, nearly closes the gap in statistical limits of such approach, bringing insights into pessimistic offline RL.
main_review: Strength:
The paper is clearly written. Rigorous theory is backed up by neat intuitions. The presentation is very fluent and readers are able to capture the high-level intuitions smoothly. 
This work contributes to the study of value-basic pessimistic RL by closing the gap in suboptimality bounds. It also related RL to OPE by showing the variance-aware technique in OPE also applies to policy learning. I believe these are important insights towards a complete picture of pessimism. 

Weakness / questions:
The current setting of the paper is well studied and complete, but it might be a little restricted. For example, a nice point of the PEVI paper (Jin et al. 2021b) is that the suboptimality directly depends on the dataset, not restricting to behavior policy. I am interested whether such variance-incorporated ideas can be used for fully data-dependent constructions. This might also be interesting for a better understanding of what a static dataset can provide. 
Invertibility of covariance matrix: the feasibility algorithm of PEVI is actually not influenced by singular covariance matrix, as long as that is in line to the actual optimal policy, or the policy in comparison (i.e., both behavior and optimal policy miss some subspace). I am curious what happens when the covariance matrix is not invertible, so that Lambda_h^* does not exist. It might depend on the relationship between \mu to optimal policy? Not expecting an exact result, but some discussions might be interesting. 

summary_of_the_review: In general, this paper is clearly written and elegantly presented. The combination of rigorous theory and high-level intuitions make it fluent to follow. This work provides a refined treatment of pessimistic penalty functions, which leads to tighter upper bounds and nearly matching lower bounds. Although complete for the current setting, I think the paper can be improved by adding some broader considerations to more general cases to bring more insights beyond the restrictions of fixed behavior policy and well-behaved covariance matrix.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The given work proposes the introduction of a pessimistic lower bound for reinforcement learning agents.The estimated variances are used to re-weight the Bellman residual learning objective, such that the samples with higher uncertainty are correspondingly penalized.


main_review: Strength:
* The paper is well organized, theoretically grounded
* The results seem of reasonable significance.
* The related work in this area is well explained.


Weakness:

*There is a lack of empirical evaluation carried out, to showcase how the lower bound estimation 
* It's hard to follow for those who are not familiar with this sub-field. 


* Minor typo in Introduction(section 1): "stat" -> "state"
summary_of_the_review: Overall, the paper is well motivated, aiming to solve an important problem in the area of offline reinforcement learning. The work is theoretically well grounded, studying offline reinforcement learning for time-inhomogeneous episodic linear Markov decision processes. While the paper is reasonably well organized, it's quite hard to grasp the fundamental concepts especially for those not an expert in this sub-field.
review_title: null

final_score: rating: 8: accept, good paper
review_content: summary_of_the_paper: This paper considers offline policy optimization with linear function approximation that incorporates the variance information into consideration, which eventually leads to a better statistical error and fine-grained statistical analysis.
main_review: The paper is overall clear and easy to follow. Incorporating variance information is a promising direction that can date back to the analysis of UCBVI, which can generally obtain better results.

I have some minor comments:

1. Perhaps it’s better to make some remarks in the algorithm on which step use which parts of data, that can be much more clear compared with current presentation.

2. There are some minor typos in the paper, e.g. in Section 3.3 “the proof can be found in Appendix D” rather than “can be bound in Appendix D”, for Theorem 3.5 the sum term should be in the denominator. Please go through the paper again to eliminate this kind of typo.

3. In the current presentation, it’s not clear where the improvement in Section 3.3 comes from. It’s acceptable due to the space constraint, but I hope there can be some intuitive interpretation on that.

4. Is the lower bound of Theorem 3.5 matches the upper bound of Theorem 3.3 up to logarithm factors and higher order term? I think so, but the authors don’t provide sufficient discussion on this. And I also want to ask if there’s a separation for tabular setting and linear setting, i.e. the worst case of linear setting is beyond the tabular setting?

I hope the authors can continuously improve on these aspects, which will further improve the readability.

summary_of_the_review: The overall idea is clear and easy to follow, but it can be much better if the authors can polish the paper again and provide more discussion.
review_title: null

Meta-review: In this paper, the authors motivate the paper well by the gap between the upper bound of the popular offline RL algorithm and the lower bound of the offline RL. By exploiting the special linear structure, the authors designed a variance-aware pessimistic value iteration, in which the variance estimation is used for reweighting the Bellman loss. Finally, the upper bound of the proposed algorithm in terms of the algorithm quantity is proposed, which is more refined to reflexing the problem-dependency. These results are interesting to the offline RL theoretical community. 

As the reviewers suggested, several improvements can be made to further refinement, e.g., 

- The intuition about the self-normalization in the algorithm exploited to improve the upper bound should be introduced. 
- The discussion in Sec 3.3t about the insight of the improvement of the upper bound is not sufficient. 
- The extra computational cost about the variance should be discussed.
Decision: Accept (Poster)