Venue: NeurIPS 2022 Conference

Reviews:

final_score: rating: 6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.
review_content: summary: This paper proposed an optimistic variant of the PSRL algorithm and proved a minimax regret bound, which settles an open problem raised by Agrawal and Jia [2017b]. The main technical contribution is a new sharp anti-concentration inequality for Dirichlet random vector, which may be useful for other settings.  
strengths_and_weaknesses: Strengths:
- This paper proved minimax regret bound for an optimistic variant of the widely used PSRL algorithm, which settles an open problem. 
- The algorithm is simple and clean. 
- The theoretical novelty in developing a tight anti-concentration bound. 

Weaknesses:
- OPSRL is very similar to the algorithm analyzed in Agrawal and Jia [2017b] and the main difference is only in applying the new anti-concentration bound, which simplifies some technical ingredients in Agrawal and Jia [2017b]. 
- OPSRL is still far from the standard PSRL that people use/want to study as multiple posterior sampling is performed at each episode to achieve optimism, which makes the algorithm more similar to UCB algorithm. 
- If the authors compare the anti-concentration used in Agrawal and Jia [2017b] with their approach in more detail, it would be easier to understand why the extra S factor is removed. 

Minors:
The paper (Randomized Exploration in Reinforcement Learning with General Value Function Approximation) might be relevant as it considers optimistic RLSVI.  
questions: - Can authors elaborate more on how OPSRL adapts automatically to the variance of the estimates so that the optimal dependence on H can be achieved?
limitations: I am not aware of any potential negative societal impact.
review_title: null

final_score: rating: 7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper proposed an optimistic posterior sampling algorithm for episodic MDPs and proved that the algorithm has a regret bound matching the lower bound up to poly-log terms. 
strengths_and_weaknesses: Strengths:
- The proposed OPSRL algorithm combines ideas from optimism and posterior sampling. Though there are existing algorithms with a similar algorithmic structure (Fonteneau, Korda, Munos, An optimistic posterior sampling strategy for bayesian reinforcement learning, NIPS 2013 Workshop on Bayesian Optimization), OPSRL is the first one with lower bound matching regret guarantee.

- New technical properties on the Gaussian lower bound for Dirichlet distribution is critical in establishing that the sampled Q-function is optimistic, and the exponential upper bound is used in the concentration results. They are useful in proving regret bounds for the episodic MDP setting, and they might be useful for posterior sampling algorithms in other settings as well.


Weaknesses:
- No numerical experience verifying the theoretical results.
questions: As discussed in the paper, the current proof only works when L posterior samples are drawn and L has some logarithmic dependence on H,S,A,T. Given empirical success of posterior sampling with one sample or a fixed number of samples, it would be very interesting if one can have some theoretical guarantees for these settings. From the proof, the size of L seems to come from the union bound on ensuring optimism for all state at all times. Are there some ideas on how the analysis could be extend to settings when L is a constant?
limitations: The problem setting and limitations are discussed and addressed in the paper.
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposes a novel optimistic posterior sampling algorithm, showing that it can achieve nearly mini-max optimal regret bound with a novel anti-concentration inequality of Dirichlet distribution.

strengths_and_weaknesses: ### Strengths:
* A novel anti-concentration inequality for Dirichlet random vector, which may be of independent interest.

### Weaknesses:
* The application scenario is too limited, as it crucially depends on the Dirichlet distribution. Some artifacts like the pseudo-state $s_0$ may exacerbate this issue.
* No empirical demonstrations of the newly proposed algorithm. The authors claim the benefit of posterior sampling algorithms multiple times (e.g. Line 216-225). Although there are several empirical demonstrations that show that some versions of the optimistic posterior sampling algorithms work better than the empirical counterpart, it’s not clear if such variants can still perform well. Given that this paper is all about tabular settings, I prefer having such an evaluation.
* For me it is much more like an applied math paper, as it does not really solve important questions in reinforcement learning. It mainly show one other potential optimism mechanisms with the anti-concentration of Dirichlet random vector.

questions: * I’m not convinced that this method can be better than the frequentist method, as it implicitly mimics the Bernstein type bonus with a sampling method. Can the authors describe what are the potential benefits of the proposed methods over traditional methods like UCBVI? (I admit that UCBVI focuses on the worst-case guarantee and sampling based methods can be better in constant, but I don't think this can lead to e.g. instance-wise benefits.)

* In Line 182-184, is the proposed algorithm applied to general prior other than Dirichlet, as there is only one anti-concentration result for Dirichlet distribution? If not, I think there is no need for this claim.

* Can the proposed methods be generalized to the case with function approximation? It is much more favorable to provide some insights that can be generalized to more general scenarios (e.g. [1]) rather than sticking to the specific tabular setting and Dirichlet distribution.

[1] Zhang, Tong. "Feel-good thompson sampling for contextual bandits and reinforcement learning." SIAM Journal on Mathematics of Data Science 4.2 (2022): 834-857.
limitations: This is a theoretical paper that does not need to address the potential societal impact.
review_title: null

Meta-review: metareview: The paper propose a variant of posterior sampling RL, namely OPSRL, and provided a minimax regret analysis for this algorithm. This settles an open question in the RL regret theory. The key technical novelty is a new anti-concentration inequality, which can be used to improved the analysis by Agrawal and Jia 17 and closed their gap. Reviewers appreciate this theoretical contribution. Some reviewer questioned the applicability of the method and lack of numerical experiments. The authors supplied experiments after rebuttal, which largely addressed some of these questions. One reviewer raised his score from reject to borderline acceptance. Overall, this is a solid paper with meaningful theoretical contribution to posterior sampling and to RL theory.
confidence: Certain
Decision: Accept