Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The paper proposes an approach for provably efficient reinforcement learning in linear MDPs that avoids constructing explicit confidence intervals. Instead, akin to posterior sampling, this method only requires sampling from a posterior distribution. The paper proves that this approach still yields optimistic value function estimates and retains the regret rate of optimistic LSVI. Because the algorithm requires only  sampling, the paper further claims that the method can be used more easily with general function approximation but does not provide empirical or theoretical results. 
main_review: Summary: Overall, I like the boostrap idea but it is not clear how it provides any tangible benefit compared to existing approaches. The paper also has clarity issues.

- Originality: I like the idea of using this concrete form of boostrap for constructing optimistic Q functions and to the best of my knowledge, it has not been proposed or analyzed before. That said, there are existing works that construct Q function estimates by maximizing over multiple posterior samples and which provide theoretical guarantees in the tabular MDP setting. 
- Significance: BooVI is likely more conservative than optimistic LSVI, thereby loosing one of the main benefits of RLSVI. This seem to be confirmed by the illustrative experiments in the appendix, where the performance of optimistic LSVI is better or on par than BooVI's. Although the guarantees of BooVI and optimistic LSVI are stronger than that of RLSVI, one would expect it that RLSVI to outperform both without significant parameter tuning. 
- Quality: The feature that BooVI only requires posterior sampling and is thus more suitable for use with general function approximation is presented as one of the main advantages. Yet, the paper does not provide any concrete evidence that BooVI is in fact more suitable with general function approximation, neither empirically nor theoretically. This claim is therefore not substantiated. While it is true that sampling is often easier than constructing confidence intervals, this requires a posterior representation that is accurate or which at least induces sufficient exploration. The paper needs to provide concrete examples for this argument to be convincing.
- Clarity: The paper is not sufficiently clear. Here are a few instances that needs improvement:
a) Specifically, the algorithm description in 3 was unnecessary convoluted with cyclic dependencies. For example, the reader does not know where tilde V come from and the reference to Line 1 in Alg 1 seems incorrect. The reader further wonders what the posterior is in line 122 which will only be make clear later. I suggest to first present the posterior given some target values (including the concrete example with Gaussian prior) and then explain how the optimistic target values are generated from the posterior samples, which is the main innovation in this paper.  
b) I recommend to restate the condition on C_alpha and C_beta in Thm 4.4 and lemmas as alpha = ... and beta = ... to clarify that they are conditions on those algorithm parameters.
c) The quantity \bar \omega is used extensively in the proof sketch of the main paper and the appendix but never introduced. Lemma E.1 should be stated from and center to clarify this.
d) Generally, it would be more useful for the proof sketch to highlight the differences to existing work, concretely the analysis of optimistic LSVI. 


Minor comments and typos:
- Line 168: class MDPs -> class of MDPs
- Alg 1 Ln 7: uising -> using
limitations_and_societal_impact: The paper does not sufficiently discuss the technical limitations of the proposed approach, concretely the challenges around defining good posteriors for settings beyond linear MDPs. 
I do not foresee negative societal impacts of this work.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper studies the low-rank model and proposes a randomized strategy that is competitive in terms of statistical efficiency with the best computationally tractable exploration method for such setting.
main_review: The work makes very strong contributions to randomized algorithms which are notoriously difficult to study theoretically. This ultimately gives a sqrt{dH} improvement compared to the state of the art randomized RL method (Zanette et al, 2020) with a seemingly clearer and more general analysis.

I am not an expert of Langevin dynamics so I went very fast there. I have a direct question for the authors: is the algorithm computationally tractable, meaning that it requires poly(d,A,H,T,1/\delta) elementary operations? (I understand yes but wanted a direct confirmation).

Unfortunately I did not have the time to carefully examine the proof sketch, but if the result is correct without major caveats then the paper is strong.

I have another question for the authors. The work seems to rely on the linear MDP setting a lot; would the analysis still work in setting of low-inherent Bellman error (e.g., Zanette et al ’20)? I suspect no, because the action value function you maintain is not linear, i.e., it cannot be expressed as \phi(s,a)^\top w.  

====

Unchanged after rebuttal
limitations_and_societal_impact: none
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a modified version of LSVI based on bootstrapping, called BooVI. Different from the famous Bootstrapped DQN, it shows that BooVI is provably efficient under linear MDP; meanwhile, although not theoretically supported, an implementation of BooVI also admits general function approximation like neural networks.
main_review: Overall, I consider this paper as a good attempt to theoretically support the power of bootstrapping and posterior sampling in reinforcement learning with function approximation. I also consider the specific usage of bootstrapping and Langevin dynamics as novel. The writing is in general a good flow, although with several potential improvements that will be given in "Suggestions on writing" part.

However, I have several concerns about its significance and technical soundness. In particular, Although one of the advantage of BooVI over other provably efficient algorithms is that it practically admits general function approximation, the provided experiments do not contain this part. Other concerns will be given in "Question" part.

Questions:
- How many steps does the Langevin dynamics take?
- The given worst-case regret bound is not strictly an improvement over [1] beucause [1] considers a slightly more general low-rank MDP. Do you think the regret of BooVI is still applicable to the low-rank MDP?
- In the proof of Lemma B.2, why does $\mathcal{F}^1_1$ not contain $\lbrace\omega_h^{1, i}\rbrace$? More importantly, the claim that $\mathbb{E}\left[\xi^k_h(s_h^k, a_h^k, s_{h+1}^k)\mid \mathcal{F}^k_h\right]=0$ makes me feel wired because I think neither $\mathbb{E}\left[\bar{Q}_h^k-Q_h^{\pi^k}(s_h^k, a_h^k)\mid \mathcal{F}_h^k\right]=0$, since $Q^{\pi^k}_h$ is based on the underlying unknown MDP, nor $\mathbb{E}\left[\bar{V}^k_h(s^k_h)-\bar{Q}^k_h(s_h^k, a_h^k)\mid\mathcal{F}_h^k\right]=0$ holds, since $a_h^k$ does not necessarily maximize $\bar{Q}^k_h(s_h^k, \cdot)$. How do the terms in $\xi^k\_h(s_h^k, a\_h^k, s\_{h+1}^k)$ cancel each other under $\mathbb{E}[\cdot\mid\mathcal{F}_h^k]$?

Suggestions on writing:
- Is line 12 in Algorithm 1 necessary? It seems that $\widetilde{Q}^k_h$'s have been generated at line 7 except $\widetilde{Q}^k_1$.
- The writing of proof for Lemma 5.3 may need some improvements because it uses $\bar{\omega}^k_h$ without defining it and implicitly uses Lemma E.1 without mentioning. I apologize if I simply missed them.
- It is probably better to give a slightly more detailed sketch on how the optimism is ensured through Bootstrapping step in Algorithm 2.

```
[1] ZANETTE, A., BRANDFONBRENER, D., PIROTTA, M. and LAZARIC, A. (2019). Frequentist regret bounds for randomized least-squares value iteration. arXiv preprint arXiv:1911.00567.
```

- - -

Score is increased after rebuttal because the technical concerns are well-addressed.


limitations_and_societal_impact: The authors adequately addressed the limitations of their work in Section 6 by presenting them as potential future works. The potential negative social impact is not addressed, which will generally be all potential malicious usage of any reinforcement learning algorithms.
review_title: null

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper proposes a posterior sampling-based algorithm BooVI, which suffices for general function approximation purposes. In the case of linear MDP setting, it achieves $\tilde{O}\sqrt{d^3H^3T}$ regret with Gaussian posterior sampling. 
main_review: Overall, this paper provides an interesting posterior sampling algorithm BooVI that works for general MDPs. The technique and proofs look sound to me. However, I have the following two questions.

1. The regret obtained for the linear MDP has no improvement over Jin et. al, is that due to the limitation of the technical tools or due to the algorithmic design?

2. The paper would be more complete if you can instantiate more examples, e.g. linear mixture MDP. Could you provide an explanation of what the theoretical result would look like for your algorithm?

Given that the paper provides some nice contributions, I would like to raise my score if the authors can address my concerns.


limitations_and_societal_impact: Yes.
review_title: null

Meta-review: The paper improves the state-of-the-art analysis of randomized RL algorithms with function approximation. The authors should improve the presentation and add more empirical support.
Decision: Accept (Poster)