Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This work introduces a conditional posterior sampling algorithm that is a model-free posterior sampling reinforcement learning algorithm and can be applied to general Markov decision processes and value function classes. Authors provide theoretical guarantees for the proposed algorithm.  Actually, it has been proved that the worst-case regret of the proposed algorithm is near-optimal and that improves the best known regret bounds for posterior sampling approaches (OPT-RLSVI, UCB-LSVI). The key component of the proposed algorithm is the definition of the likelihood over the collected samples (observations - state, action, reward) given a value function. To conclude, it is a theoretical work that shows that there is no statistical efficiency gap between OFU and posterior sampling algorithms. 
main_review: **Strengths**
- This work introduces a conditional posterior sampling algorithm that is a model-free posterior sampling reinforcement learning algorithm that can be applied to general Markov decision processes.
- Theoretical guarantees for the proposed algorithm are provided. The worst-case regret of the proposed algorithm is near-optimal
- The worst-case regret of the algorithm improves the best known regret bounds for posterior sampling approaches, such as OPT-RLSVI, UCB-LSVI. Apart from that, it has been shown that a posterior sampling method can achieve the same guarantees with the OFU based algorithms.

**Weaknesses**

- The main limitation of this work is the lack of any empirical analysis. It would be of high importance for the reader to be able to check that the theoretical findings are aligned with those of the experiments (even on toy environments). 
- Another open question is if the proposed algorithm is actually applicable in practice.  As mentioned by the authors, the sampling of the posterior is not computationally tractable in its current form (Eq. 3).

To conclude, despite the theoretical guarantees of the proposed conditional posterior sampling algorithm, authors should make clear if this algorithm could be also applied in practice. 

**Minor comments/typos**
- l. 150 pairs. -> pair,
- l. 160: in comparison the the
limitations_and_societal_impact: I think that the limitations of this work have been adequately addressed by the authors
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors propose a posterior-sampling algorithm for RL on a family of MDPs and value-function classes. Although an efficient sampling procedure is not given, the authors derive regret bounds for this family of MDPs that match (or improve) the existing bounds in expectation.
main_review: Overall, the presentation is clear and readable. Although the contribution is mainly theoretical and an efficient implementation of the algorithm is missing, I believe the work is significant enough for publication in NeurIPS.

I did not check the proofs but the results and the arguments seem believable. In comparison with existing results (e.g. UCB-LSVI), it should probably be noted that the regret bound for posterior-sampling presented here is in expectation whereas the bounds in many existing works are with high-probability.

Some minor glitches can be found here and there. I urge the authors to double-check everything. For example, in Line-69 P^h is defined for h=1...H whereas the definition of Q (Line-78) uses P^{h+1} so apparently P is needed for h=2....(H+1). This is distracting for the astute reader.
limitations_and_societal_impact: Yes
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: The work proposes a new Thompson-sampling inspired exploration algorithm for exploration with general function approximation.
main_review: The paper is written clearly and nicely organized.

The TS-inspired algorithm examined in this work can function on most of the recently proposed settings, i.e., Bellman completeness, Bellman Eluder dimension etc.. A new complexity measure (Online decoupling coefficient) is introduced and connects nicely with other definitions.

A Thompson sampling algorithm, when designed correctly, has 3 major benefits beyond ofter superior empirical performance:

- it is computationally efficient, as it requires sampling instead of solving a potentially non convex optimization problem 
- it avoids the construction of confidence intervals, which can be an issue with complex approximators
- a similar algorithmic structure generalizes across different settings

The current proposal here is not computationally efficient. In my opinion, this is a major dealbreaker.

To my understanding, all optimization based works (e.g., Zanette et al ‘20, Jin et al. '21 etc) that are computationally intractable admit an easy randomized version which is also computationally intractable: simply sample from the feasible set until a near-optimal solution is found. One can check, that a good enough solution is normally found after exponentially (in d,H for the simple linear case) many samples.

In this light, I'm not sure how this work differs from those that are intractable and do not explicitly introduce randomization; randomization here seems to be an ineffective way to solve a complex problem and does not bring advantages compared to non-randomized methods. I think the work looses the spirit of TS algorithms and does not make significant algorithmic or analytical contribution into the correct design and use of randomization to tackle complex reinforcement learning problems.

limitations_and_societal_impact: not applicable
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In this paper, the authors study the model-free posterior sampling algorithm for the episodic RL problem. A novel algorithm and analysis are proposed. The regret guarantee is proved, and specifically it depends on a term related to the function class, a term related to the structural complexity measure (decoupling coefficient), and other parameters. The authors also show the decoupling coefficient is small for linear MDPs, generalized linear MDPs, and Bellman-Eluder Dimension. When specialized to linear MDP, the regret bound matches Zanette et al. [2020b], thus statistically efficient. However, the algorithm suffers from computationally inefficiency.


-----
I have read the response and other reviews. I'll keep my original rating.
main_review: I really enjoy reading the paper and would like to thank the authors. As we know that most TS related algorithms are restricted to the linear MDP setting, this paper makes significant contribution by extending the framework to the more general settings. The definition of the prior and the likelihood function, and the analysis are new to me. Though the regret bound in Theorem 1 is hard to parse, the authors then instantiate that to the linear MDP setting and compare them with the existing results. Overall, the main text is easy to follow. The technical part is dense. I don’t have time to check the proof, so I am not able to evaluate the correctness of the result.

-	Recently, we have seen a boom of paper beyond the linear MDP setting in theoretical RL research. However, most algorithms are not related to TS. The authors propose a new algorithm that can handle the more general setting. They also introduce new quantities about the function class and the structural complexity measures and bring new analysis to the community. I think this initial step may boost the research in the related subarea.
-	I notice that the optimistic prior is not symmetric for all level h since it only includes $\exp(\lambda f^1(x^1))$. Can you comment on why this special definition is helpful for the analysis?
-	Theorem 1 itself is hard to parse, since we generally don’t know how large the $\kappa$ terms and the decompiling coefficient terms are. I think the magnitude of $\kappa$ is only investigated for the linear MDP case. Is it possible to obtain similar bounds of $\kappa$ for other settings?
-	One limitation of the algorithm is the computationally inefficiency. Besides, I think the algorithm requires the know ledge of $\kappa$ and decompiling coefficient terms. Is this true? If so, is it possible to extend to the unknown case?
-	In Corollary 2, it seems that the priors are assumed to chosen uniformly so that a bound on $\kappa$ can be achieved. Is there any difficulty to extend it to more general priors?
-	The regret bounds are the expected regret bounds. It is generally believed that the high-probability regret bound is stronger. Have you thought about proving high-probability regret bounds?
-	Probably because I didn’t check the proof in appendix carefully, I personally don’t find the proof sketch in Section 5 to be very helpful. It is still hard for me to digest the high-level idea of the proof after reading it. Maybe the authors can think about reorganizing this part or cutting some part of this section (for example some detail about how to bound $F_t^\kappa$ term) and leave the space for other discussions.
-	Regarding the related literature, [1] and [2] are also quite related recent TS type algorithms. And currently there might be some technical issues in Xiong et al. [2021] as claimed by the authors.
-	It would be better to discuss the tightness of the bound when specialized to the linear MDP setting. I think there are a few results about the lower bound in linear MDP, e.g. [3].

[1] Agrawal, Priyank, Jinglin Chen, and Nan Jiang. "Improved Worst-Case Regret Bounds for Randomized Least-Squares Value Iteration." Proceedings of the AAAI Conference on Artificial Intelligence. Vol. 35. No. 8. 2021.
[2] Jafarnia-Jahromi, Mehdi, et al. "Online Learning for Stochastic Shortest Path Model via Posterior Sampling." arXiv preprint arXiv:2106.05335 (2021).
[3] Zhou, Huozhi, et al. "Nonstationary reinforcement learning with linear function approximation." arXiv preprint arXiv:2010.04244 (2020).
limitations_and_societal_impact: NA
review_title: null

Meta-review: This is a well-written and interesting paper.  However, as multiple reviewers pointed out, its not clear whether the approach considered is computationally viable.  As one of the reviewers suggests, this could be a dealbreaker.  At the same time, I do appreciate that the work in sorting out sample complexity for value function sampling under these idealized conditions.  After thinking about this some, I am inclined to recommend accepted.
Decision: Accept (Poster)