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 PAC reinforcement learning, where an agent is required to identify an $\epsilon$-optimal policy with probability $1-\delta$. The instance-dependent complexity remains elusive in episodic Markov decision processes (MDPs). In this paper, the nearly matching upper and lower bounds on the sample complexity of PAC RL in deterministic episodic MDPs with finite state and action spaces. In particular, our bounds feature a new notion of sub-optimality gap for state-action pairs that we call the deterministic return gap. The design and analyses employ novel ideas, including graph-theoretical concepts (minimum flows) and a new maximum-coverage exploration strategy.
strengths_and_weaknesses: **Strgenths** This paper provides fine-grained solution for PAC reinforcement learning with the deterministic MDP setting. The Proposed algorithm is based on the elimination rule and the resulting complexity is expressed in terms of min flow with linear program formulation. The experiment is motivate. 

**Weakness**

- The claimed optimality actually differs from the upper bound by a factor of $H^2$, therefore the gap is still there. While notice the discussion about this from 327-332, I still wondering if it is possible to improve horizon dependence for EPRL? Current analysis seems based on Hoeffding's technique eon(5), could some (empirical) Bernstein bonus be designed  for EPRL?

- The key procedure for EPRL is the policy elimination. How do you conduct efficient procedure for this elimination step to make algorithm practical? Especially the policy set can be exponential large?

- Deterministic MDP is a simpler setting comparing to stochastic MDPs since each state action only needs to be experienced and the problem size is $SA$ (instead of $S^2A$ for the stochastic case). Hence, it is expected to have faster convergence than the general tabular MDP problem. How do you interpret the $O(\frac{SAH^2}{\epsilon^2})$ sample complexity as the optimal complexity for deterministic MDP? Is there a minimax lower bound for that? Indeed, in the offline case, it has been noted learning deterministic MDPs can have faster convergence with rate $\frac{1}{n}$ instead of the standard statistical rate $\sqrt{\frac{1}{n}}$ due to its instance dependent nature [Yin&Wang,21]. I believe it is very necessary to refer [Yin&Wang,21] and discuss potential connections to the current work, for example, can instance-dependent online RL also achieve smaller regret comparing to the standard $\sqrt{T}$?

[Yin&Wang,21] Towards Instance-optimal Offline Reinforcement Learning with Pessimism, NeurIPS 21.


questions: I have already provided all the comments in above. 
limitations: Yes.
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: This paper studies instance-dependent optimality of PAC reinforcement learning in tabular deterministic episodic MDP. 
It first introduces a new notion of sub-optimality gap called deterministic return gap, then characterizes an instance-dependent lower bound in terms of this new definition. The paper also proposes an algorithm based on maximum coverage sampling and confidence-based elimination, and prove that it can match the lower bound up to a $H^2$ factor. Finally, the paper also provides empirical evaluation on synthetic MDPs.  


strengths_and_weaknesses: Strength:

I vote for acceptance as this paper presents solid contributions and novel proving techniques. 

Instance-dependent analysis is a very important topic in RL theory and this paper provides some really contributions. In general I really enjoying reading this paper. One of the main contribution is to include graph-theoretical concepts in the lower bound analysis: it first proves a lower bound on minimum number of visitation for each state-action pair, the instance-dependent lower bound follows immediately by realizing that the visitation counts follows a feasible flow. I think this novel technique also has potential application in  other analysis of RL problems. 

Weakness:

Some notations and definitions can be improved. 


questions: 
Here are some question that I hope the authors can answer in the rebuttal. 

1. There is a factor $H^2$ gap between upper and lower bound. It seems to be the mismatch is caused by the lower bound as it is hard to get explicit dependence on the $H$ factor (because the lower bound is between max and sum over all horizons). Is there a room to improve this? 

2. How can the lower bound be generalized to the stochastic setting? I guess most part of the analysis (or the high level strategy) will remain unchanged. Basically one only needs to argue for the KL decomposition used in the proofs in Section C. But I am not sure if there are other difficulties. 

I also have some small suggestions. 

1. The notations can be improved somehow. For example, what's $n^\tau_h(s,a)$ in equation (3)? What is $\hat{pi}$ in line 727? Maybe all of these definitions are given somewhere in the paper, but it's hard for the readers to check back and forth to find them. After reading carefully I can understand the meaning of the notations, but it will be very helpful if the authors can add a some explanation in the proof. 

2. Lemma 1 from Kaufmann et al., 2016 has been used quite often in the proof of lower bound. Maybe it's helpful to include that in the appendix for completeness? 

3. Some discussion in the main paper about how to prove instance-dependent lower bound will be useful. 
limitations: Please see the above section.
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: This paper studies PAC RL in tabular deterministic MDPs with known transitions but unknown (stochastic) rewards. An instance-dependent lower bound is presented which bounds the sample complexity in terms of the solution to a min-flow problem where the edge function is related to (the inverse) of a newly-defined deterministic return gap. A new algorithm is presented (EPRL) which is worst-case minimax optimal and matches the instance-dependent lower bound up to an H^2 term and logarithmic factors.
strengths_and_weaknesses: Significance: There has been quite a lot of work lately on instance-dependent results for RL. This paper adds nicely to that body of work. Unfortunately, the setting is restricted to known deterministic transitions, and there is quite a large gap between the lower bound and the upper bound (H^2, ignoring logarithmic factors). As a first instance-dependent PAC result, this is still a nice result. The experimental results and the discussion is interesting as well. For want of time I have not checked the proofs for any mistakes.

Originality: The connections with minimum flow are interesting. The EPRL algorithm is novel. 

Clarity: The paper is well written overall. One complaint is that, since the upper bounds and the lower bounds differ by a factor of H^2, the claims that the algorithm nearly matches the lower bound is misleading and should be modified. Another misleading claim is that the transition function can be learned "with only an additional constant" (this constant would give an additional dependence on SAH). Lastly, the claim that this is "the first instance-dependent lower bound for the PAC setting in episodic MDPs" is technically true, but there are some instance-dependent bounds for best-policy identification in the cited papers [44] and [4] (a restricted case of PAC), as well as several instance-dependent regret bounds in cited papers [13] and [40] which should be mentioned. 

Smaller complaints:
- The notation and naming for the different instance-dependent functions are quite similar to each other, making it difficult to easily remember which is which (e.g. value gap, return gap, deterministic return gap, and the notations  \Delta, \tilde\Delta, \bar\Delta). 
- The definition of Pi^t should be included in the pseudo-code of Algorithm 1 for readability

Typos:
- Line 182 "mimixal optimal"

questions: - How much is the assumption that transitions are known matter? It seems like it is mainly used in Line 7 of the algorithm (to calculate Pi_{s,a,h}). Can the algorithm be modified or this assumption be removed? 
limitations: Limitations: See "Strengths and Weaknesses" section above.

Potential negative societal impacts: N/A
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 work studies the PAC RL problem in the tabular finite horizon setting for deterministic transition MDPs. The paper derives instance dependent lower bounds and an algorithm which nearly matches the lower bounds.
strengths_and_weaknesses: Strengths:

1.) Originality -- the paper shows some interesting results in terms of relating the MaxCoverage function in Algorithm 1, to the StaticMaxCoverage in Algorithm 3. In particular the observation that the MaxCoverage function behaves similarly to computing a minimum cover of the remaining (not eliminated) state-actions pairs and playing according to this cover (as done in the StaticMaxCoverage) is interesting and could potentially lead to imporved PAC RL algorithms for more general settings.

2.) Quality -- the paper is technically sound and provides some interesting new ideas as mentioned above. Further, the paper improves on prior work lower bounds by a polynomial factor of the horizon.

3.) Clarity and significance -- the paper is well written and mostly clear and easy to understand.

Weaknesses:

1.) Originality -- while the authors claim to propose a new notion of sub-optimality gap, this notion already exists in prior work up to a normalization factor of horizon. The novel contributions of the paper seem to mostly be in terms of removing spurious factors of horizon in upper and lower bounds from prior work. It is worth mentioning that the lower bound stated in Theorem 1 can not be directly compared to regret minimization lower bounds in prior work as the regret minimization lower bounds are asymptotic and regret minimization and PAC RL are not really aligned in their objectives as pointed out by Wagenmaker et al. 2022.

2.) Clarity and significance -- I do not find the claims of matching upper and lower bounds true. It is important to note that Theorem 1 holds in a different setting from Theorem 3, that is in Theorem 1 there are no assumptions made about boundedness of the rewards, and in fact this is a very important part of the proof, making the result similar in spirit to the lower bound in Theorem 4.5  (Dann et al. 2021). The results in Theorem 3, in my understanding, hold for the more standard setting of bounded rewards. It is important to note that there could be a large gap between the two settings, making the claims of matching upper and lower bounds inaccurate. In particular, for the bounded rewards setting, there exist MDPs in which state-action pairs need not be visited even once for to be eliminated. This is due to the fact, that it is possible to eliminate all actions on paths to such state-action pairs before ever visiting such state-action pairs and hence there is no alternative MDP as in Lemma 8 of the current paper.

Given that the paper does not really establish lower bounds in the more interesting setting of bounded rewards and the upper bounds mostly seem to remove horizon dependent factors, I am unsure of how strong the contributions of this work are.

References: 

Wagenmaker, Andrew J., Max Simchowitz, and Kevin Jamieson. "Beyond no regret: Instance-dependent pac reinforcement learning." Conference on Learning Theory. PMLR, 2022.

Dann, Christoph, et al. "Beyond value-function gaps: Improved instance-dependent regret bounds for episodic reinforcement learning." Advances in Neural Information Processing Systems 34 (2021): 1-12.
questions: Given the discussion regarding computing a minimum policy cover through min-flow/max-cut (Algorithm 2) and the fact that once all paths to a state-action pair are eliminated, e.g., by eliminating all incomming edges into the state-action pair, will Algorithm 3 ever select a policy which visits the state-action pair with no incomming edges? Further, will Algorithm 1 play a policy which visits such a state-action pair?

Do the authors think they can derive a meaningful lower bound, maybe in terms of a min-flow LP, for the setting of bounded rewards?


limitations: This work is theoretical in nature and future societal impacts are hard to judge.
review_title: null

Meta-review: metareview: The paper studies PAC reinforcement learning in tabular episodic MDPs with deterministic transitions and provides upper and lower bounds on the sample-complexity that match up to horizon and log-factors.
Overall, all reviewers rate this paper positively (after the authors' responses and discussion). They view the contribution of a fine-grained instance-dependent guarantees in this setting as significant and particularly appreciated the novel insights, e.g., relating the MaxCoverage function in Algorithm 1, to the StaticMaxCoverage in Algorithm 3 or the inclusion of graph-theoretical concepts in the lower bound analysis. There were also several limitations raised, in particular the deterministic transition assumption and the reward range assumption used in the lower bound. However, some of these can be addressed by clarification and more detailed discussion in the camera ready. All in all, this is a solid paper and is recommended to be accepted.
confidence: Certain
Decision: Accept