Venue: NeurIPS 2022 Conference

Reviews:

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: This paper studies episodic RL in tabular MDPs in the regret minimization setting, and presents an algorithm, called SSR, which follows the principle of exploration via randomized value functions. The paper presents two variants of SSR that differ in the choice of the noise. The variant that generates noise sequences based on Bernstein’s inequality is shown to achieve a worst-case regret bound (with high probability) that matches the lower bound up to logarithmic factors. This regret bound improves the best known regret bounds for randomized exploration by a factor of $\widetilde O(H\sqrt{S})$. 
strengths_and_weaknesses: The paper studies a classic but important problem in RL. Despite all the recent advances in the theoretical aspects of episodic RL, the studied setup is interesting in view of the empirical success of exploration via randomized value function and considering that the theoretical picture is not yet complete. The paper makes a good step in this direction and thus makes a nice addition to the literature on theoretical episodic RL. 

The paper is written well and admits a good organization. The presentation of the various elements (model, algorithm, and results) is clear and precise. All these makes the paper a nice read. 

Amongst the technical and algorithmic novelties is the use of a single seed for randomization and the use of a new clipping strategy. The latter is shown to maintain both optimism and pessimism, which turns out to be crucial in achieving the improved regret bounds. 

Some weaknesses and questions:

- The regret bound of the Bernstein-type variant in Theorem 2 is stated to hold when $T$ is larger than a (rather large) polynomial of $H$ and $S$, whereas this is not the case for the other variant. Could you elaborate further on this? And what can be said about regret for when $T$ is smaller than this threshold?

- I would like to appreciate the authors to have included the lower order terms in the regret bounds and to have clarified the time after which the desired $\sqrt{T}$-regime kicks in. Under both variants, the lower order terms scale as $H^4S^2A$, so that the desired $\sqrt{T}$-regime kicks in after a rather large $T$ (albeit polynomial in $H$ and $S$). I may urge the authors to compare SSR against state-of-the-art in terms of such critical values of $T$ as well.

- The statement ”UCB-type algorithms … suffer from difficult implementation ...” is not entirely correct. While this statement could be valid for model-based UCB-type algorithms, model-free ones do not require complicated planning procedures (such as EVI in UCRL2 or alike). Rather, they just take actions greedily with a Q-function, which is cheaply implementable. I may ask the authors to further elaborate on this, and if necessary, make the statement more precise. 

- The paper nicely closes the gap between the regret lower and upper bounds, implying that for large enough time horizons, both UCB-type and randomized approaches could achieve the worst-case optimal regret bound. Then the following question naturally arises: In the considered episodic setting, which approach is empirically superior? Unfortunately, the paper does not provide any experimental result, so it remains inconclusive as to whether any of the two approaches provide a superior empirical performance. 

Minor comments:

In several places, it is stated that optimism and pessimism is guaranteed to hold with constant probability. In technical sections (e.g., Section 4 and later), it might be a good idea to explicitly state such a constant probability to enrich the discussion. 

Some typos: 

Line 89: Algorithms …. has been ==> … have been 

Line 130 (and elsewhere): in tabular setting ==> in the tabular setting

Line 158: $h=1, \ldots H$ ==> $h=1, \ldots, H$

Line 162: noisy observation ==> noisy observations 

Line 178: has to large ==> has to be large

Line 188: in suboptimal regret bound ==> in a suboptimal regret bound

Line 192: number of clipping ==> … clippings 

Line 194: is closed to ==> is close to 

Line 198: uncertain-based ==> uncertainty-based

Line 212: … still maintain ==> still maintains

Line 219: Full stop missing

Line 221: noise ==> noises 

------ Post Rebuttal ------

I would like to thank the authors for the rebuttal. My questions and concerns are adequately addressed. As a result, I maintain my score of 7, but with an increased confidence of 4. 

questions: See the weaknesses above. Also address minor comments if relevant.
limitations: There is no negative societal impact associated to this work. The most important limitations of the presented methods in the paper are adequately and clearly discussed in the paper.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper studies a finite state-action MDP setting with time inhomogeneous transitions and costs. The authors then propose a single seed randomization algorithm that . Regret analysis then purports to achieve $\tilde{O}(H\sqrt{SAT})$ bound on regret in the finite MDP setting using randomized algorithms (as opposed to variants of the UCB family for MDPs).

strengths_and_weaknesses: Strengths: 
1. The paper addresses an important lacuna in finite MDP Reinforcement Learning. UCB algorithms have been known to show $\tilde{O}(H\sqrt{SAT})$ regret performance for quite some time now and an extension to Thompson Sampling-type algorithms is quite necessary.

Weaknesses:
1. I'm not convinced the setting of the problem is entirely natural. Essentially, the model is one where the agent interacts with the environment over H trajectories, and the exact same sequence of transition matrices and reward functions materializes every time.
- Using a model just because it has been previously used does _not_ constitute sufficient justification.

2. The algorithm and its analysis are lacking in novelty, in my opinion. 
- The concept of clipping and are introduced in [2, Algorithm 1] (see line 15) 
- With regards to $\sigma^k_{ty}$ in Step 6: Moving from Hoeffding to Bernstein type randomization is rather dated and can be found in  UCB-type algorithms previously proposed in the literature.
- It appears to me that using a single seed for the trajectory is the only truly novel idea.
questions: 1. Steps are missing in Algorithm 1. 
    - Trajectory generation must be mentioned somewhere between Steps 5 and 6.
    - Please point to equations 5 and 6 to show how $\sigma^k_{ty}$ is generated. I was searching around for an expression for $\sigma^k_{ty}$ for quite some time.

2. In line 225, you claim that "the main advantage of randomized exploration lies in the algorithm component." Yet, the results show that it is the other point, i,e, the Bernstein noise that really does the $H^{1.5}$ to $H$ reduction. In light of this, how would you justify your claim in Line 225?

3. Can you say anything about expected regret?
     -  I cannot find any numerical results in the paper. In the absence of simulations, how does one compare SSR empirically with other randomized (and UCB-based) algorithms? Regret analysis only provides upper bounds which could be rather loose.
    - Moreover, simulations could also shed light on the matter of **expected regret**. The present analysis says nothing about what happens on the complement, i.e., the subset of sample paths with measure $\approx \delta.$
limitations: The work is theoretical and I cannot find any potential negative societal impact.
review_title: null

final_score: rating: 8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.
review_content: summary: The paper considers the problem of regret minimization in RL using randomized algorithms. For this, the authors provide a single-seed-based algorithm that is able to obtain $\tilde{O}(H\sqrt{SAT})$ regret bound using Bernstein concentration-based variance scaling.
strengths_and_weaknesses: Strength: The result of the paper and the simplicity of the algorithm using a single seed in an episode is the biggest result. Further, providing an analysis based on absolute value analysis of the difference between the optimal policy of the true problem setup and of the optimal policy of the sampled value function is interesting and can be used in many future works working on sampled MDPs.

Weakness: 

1. The additive term of $O(H^4S^2A)$ is quite large. 
2. The paper does not addresses the works in the area of Thompson Sampling and worst-case regret bounds for posterior sampling based algorithms. 
questions: How does the SSR algorithm compare against the PSRL algorithm by [5,6]?
limitations: Yes.
review_title: null

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: Authors propose novel algorithm for reinforcement learning with randomized exploration. Algorithm achieves minimax optimal regret bound up to poly-logarithmic factors, and it is the first such result for RL algorithms based not on the principle of Optimism in the face of Uncertainty. The most crucial algorithmic features that allow authors to achieve their result are
1) use a single Gaussian noise up to scaling for all transitions;
2) specific Bernstein-shaped magnitude of noise;
3) novel clipping procedure that was used at the first time for algorithms with randomized exploration.
strengths_and_weaknesses: Strengths:

1) The first algorithm based on randomized exploration that achieves minimax optimal regret; It vastly extends the theoretical perspectives of randomized exploration.

2) Novel proof technique that allows to control pessimism error for randomized algorithms;

Weaknesses:

1) Lack of empirical study. Authors claimed that use of single seed can significantly increase the stability of the algorithm, and it would be very interesting to observe this effect practically on tabular environment with non-trivial exploration problem (N-rooms for example).
questions: - The main suggestion was listed in the section on Strength and Weaknesses: it would be very nice to have an additional empirical comparison between SSR algorithm and other baselines such as UCBVI, classical RLSVI, and PSRL.
- Additionally there are several small issues with the text in the appendix:
    - In the formula after line 577 $\alpha_k$ was used without definition except the table of notations;
    - In Lemma 10 it could be great to make $z$ a parameter of function $f$;
    - In the beginning of the section of regret decomposition there was a lot of added subscript $k$ into value function that corresponds to $V^\pi$.
limitations: Authors addressed all the limitations of their paper.
review_title: null

Meta-review: metareview: Thank the authors for their submission.

The paper studies regret minimization in finite-horizon tabular Markov decision processes. 
It is the first to show an optimal (up to logarithmic factors) regret bound of $\widetilde O(H \sqrt{|S| |A| T)}$ to Thompson sampling-type algorithms. A good addition to the TS literature, showing another case in which TS algorithms can have the same regret guarantees as optimistic algorithms. The paper is well-written.
confidence: Certain
Decision: Accept