Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This work studies instance-dependent regret bound in episodic tabular MDP. The main observation is that the gaps in state-action pairs that can only be reached by optimal/suboptimal policy should have little contribution in the regret. Based on this observation, the authors defined a new notion "return gap", which is never smaller than the original gap notion. Then the authors proved that STRONGEULER enjoys a regret upper bound that only depends on return gap. In addition, instance-dependent regret lower bound based on return gap is provided.
main_review: This work proposes a new gap notion and provides corresponding instance-dependent regret upper bound and lower bound. The paper is well-written and structured. It also includes a detailed related work and proof. 

From my point of view, instance-dependent regret bound focuses on the structure of the MDP and provides tighter regret bound than instance-independent bound on specific MDPs. In this work, the authors make the observation that not every gap in the MDP is of equal importance and some of them can be avoided in the regret bound because the algorithm can quickly find out that it is in a suboptimal trajectory. This observation is interesting and exploits the inside structure of the MDP better than current analyses. 

In addition, the authors provides both regret upper bound and lower bound based on their new gap notion, which makes the work quite complete. However, the upper bound and lower bound are not matched by a factor of H. It would be great if this gap can be closed.

Though the work is lack of algorithmic contribution, I believe this is a minor issue. The main contribution of this work is the novel observation and if existing algorithm can be proved to enjoy a tighter regret based on the new gap notion, it varifies the observation.


limitations_and_societal_impact: The paper does not clearly show how the proof for the new upper bound differs from the existing proof. Is the proof a direct generalization or there is some novel techniques? Also is there technical novelty in the proof of lower bound?

Another question is that does the lower order terms in the regret upper bound only includes return gap? In addition, it would be great if the authors can conduct some numerical experiments to varify their result (small gaps in suboptimal trajectories will not affect the regret much).
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper is on instance-dependent regret bounds for RL in finite episodic MDPs. The authors observe that existing bounds fail to capture some fundamental properties of the problem. Specifically, bounds based on value function gaps $gap(s,a)=V^{\star}(s)-Q^{\star}(s,a)$ ignore the fact that only state-action pairs that are relevant from telling optimal policies apart from suboptimal ones should contribute to the regret. So, the authors introduce a new concept of gap, the return gap, denoted $\overline{gap}(s,a)$, that is the average gap encountered up to reaching $(s,a)$ through some suboptimal action.
Regret upper bounds are established for the StrongEuler algorithm by Simchowitz and Jamieson (2019). The main result replaces the inverse dependence on value function gaps with (larger) return gaps, and eliminates the dependence on the minimum gap. When transitions are deterministic, the result can be improved by ruling out state-action pairs that can only be reached by optimal policies. These results are complemented by an example MDP that shows why existing bounds can predict a much larger regret.
The authors also provide asymptotic lower bounds for consistent algorithms. First they provide a general bound expressed in terms of an abstract optimization problem. Then they consider two special cases. For the case when every state is visited by some optimal policy, they lower bound the regret in terms of value function gaps, generalizing a result by Simchowitz and Jamieson (albeit for a worse dependence on the horizon). For MDPs with deterministic transitions, the lower bound is in terms of the return gaps, and only state-actions pairs that are not visited by any optimal policy count. The corresponding upper bound pays for these pairs if they can also be visited after playing a suboptimal action. This shows the intrinsic limitations of optimistic algorithms.
main_review: The problem of online learning in finite MDPs is well understood at this point. However, this work has some elements of originality. The concept of return gaps allows to better capture the complexity of the learning problem, as made clear by the discussion of the theoretical results and the concrete MDP examples.
However, the work also heavily relies on existing results, especially by Simchowitz and Jamieson. Lemmas from this previous work are often used in the proofs without much discussion, which makes the proofs hard to follow at times. I think the paper would be better if it was more self-contained. Notice, for instance, that the StrongEuler algorithm is never described in detail.
The more "adaptive" results also require more complicated formulations and more care in analyzing the subtle differences between the results, but I think the improved understanding of the problem is worth the effort. The authors make a good job in making the notation clear, providing intuitions, and carefully discussing the implications of their results. 

To sum up, I think this is a valid and interesting paper that would greatly benefit from a more self-contained structure. I think it has some original ideas but the way they are presented gives the impression they are just a series of "supplementary" results to a well established theory. 

More detailed comments/questions follow:
1. Can you provide some intuition on why Theorem 3.2 removes the dependence on H w.r.t. [29]? The "scale" of the gap w.r.t. the horizon seems to be the same. So was the H factor in [29] an artifact of the proof?
2. Line 197: where do you prove this equivalent expression for $\overline{gap}(s,a)$?
3. Line 220: "the LHS evaluates to..." why the extra H in the denominator?
4. Lemma 4.3: how can an optimal policy visit a state-action pair with positive gap? I would understand if it was just the state, but if you also include the action then $a=\pi^{\star}(s)$ and the gap should be zero. Am I missing something?
5. In the proof of Theorem C.1 there are several quantities that are not defined: $I_k$ (sequence of trajectories?), $Y_k$ (a single trajectory?) $\psi(I_k)$ (strategy learned from the first $k$ trajectories?)

Minor comments:
- line 276: "irreducability"
- line 328: $\mathcal{X}$ is not defined
- (10) $\Lambda$ should be $\Lambda'$
- line 570: any measurable $Z$: with respect to what?
- line 576: "a uniformly good [policy]"
- line 687: I would include this discussion in the main paper
- line 769: missing a $-1$ superscript?
- I would at least mention tree-structured MDPs in the main paper
limitations_and_societal_impact: This is a purely theoretical work and it does not propose new algorithms, just improve the understanding of existing problems and algorithms.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies regret minimization in episodic tabular MDPs. First, the authors derive a novel instance-dependent regret upper bound for the StrongEuler algorithm. The proposed bound scales with a novel notion of sub-optimality gap, called return gap, which is defined as the maximum between the standard value-function gap at some s,a and the expected average of such gaps along the path to reach such s,a. This notion of gap allows to better characterize the complexity of this setting wrt existing works, eg, by formalizing the intuition that a good algorithm should not pay regret for learning optimal actions in states that are not reachable by optimal policies. These results are complemented with an information-theoretic lower bound that holds for a large class of MDPs. The lower bound is written in the form of an implicit optimization problem, and a closed-form expression in terms of sub-optimality gaps is provided for the specific cases of deterministic MDPs and MDPs where each state is reachable by an optimal policy.
main_review: Understanding the complexity of regret minimization in MDPs (especially from an instance-dependent) perspective is a relevant open problem and this paper provides novel significant results in this direction. I agree with the authors that properly analyzing and combining both value-function gaps and gaps between policy returns is a key step towards better characterizing the complexity of this setting. In this sense, I found quite interesting the definition of return gap considered in this paper and the role it plays in the analysis and in the final regret bound. Moreover, the instance dependent lower bound, while not very informative in the general case (where it is written as an optimization problem whose solution is not clear), provides further intuitions in the specific cases considered in Section 4 and in the appendix.

I found the paper very well-written. Despite the many terms that needed to be introduced, I think the authors did a good job in stating all results without over-complicating the notation and in providing intuition behind every formal claim. Maybe one downside is that some of the key results in the main paper (especially Theorem 3.2) are a little bit sketchy and one needs to take a look at the appendix for the details, which in turn is more than 30 pages of very technical content.

Overall I think this is a good paper with new insights on regret minimization in episodic RL and I tend to vote for acceptance. My detailed comments follow.


1. In the evaluation of the regret bound from [29] on the MDP of Figure 1 (Line 126), the S dependence in the third term arises by counting all state-action pairs with zero gap. This is indeed by evaluating the bound as it is written in [29]. Still, to be fair, I believe that states with a unique possible action should not be counted, and in that MDP there are only two states with more than one action.

2. Opportunity O.1 states that we should not pay an extra 1/gap_min dependence for playing optimal actions at states that are reachable *only* by playing optimal policies. However, the lower bound seems to suggest that the same should hold for states that are reachable by *some* optimal policy. In this sense, the upper bound seems to be sub-optimal in that dependence. This is partially discussed in Section 4 for the case of deterministic MDPs. Do the authors think that it would be impossible for an optimistic algorithm like StrongEuler to have a regret without any extra 1/gap_min dependences at all states reachable by an optimal policy? Is this already implied by the construction of the lower bound for optimistic algorithms of Theorem C.11? Or a more refined definition of return gap and/or of the analysis might yield such result?

3. The work of [31] is labeled as concurrent and discussed in only a few lines. Since [31] has been around since a few months before the NeurIPS deadline, I would have liked to see more discussion and comparison between the two works. In particular, as in this paper, [31] builds on top of the clipping-based analysis of [29] using the classic notion of value-function gaps. I would be curious to see what is the result of analyzing the algorithm of [31] with the return gaps defined here. If the answer to the previous question is negative, so that optimistic algorithms cannot avoid paying 1/gap_min dependences in certain states that are visited by optimal policies, could the algorithm in [31] achieve so? Or do the authors think that new algorithmic techniques are needed to get closer to matching the information-theoretic lower bound?

4. More generally, a question that is left open by this work (and which should be explicitly mentioned somewhere) is how and whether it is possible to build an algorithm that (nearly) matches the information-theoretic lower bound of Theorem 4.2. This is quite unclear since the lower bound is in a very implicit form except for specific MDP classes

5. One limitation of Theorem 4.4 is that the set of confusing MDPs that are used to compute the lower bound differ from \theta only in the immediate rewards. This basically means that, even by relaxing the assumption of "value functions bounded by 1" to "value functions bounded by H", the lower bound is likely not to show any dependence on H. On the other hand, I was expecting to see a H^2 dependence at the numerator (the counterpart of the squared span of the bias function in Ok. et al [26]). Related question: where is the assumption that value functions are bounded by 1 needed in the proof?

6. It is mentioned that the second term in Definition 3.1 is an average of the gaps along some path. So does the normalizing term always need to be H or could it be \kappa(s)?

7. Theorem 4.2 assumes that v_\theta^\star \leq 1 for all MDPs \theta. I could not find where that assumption is needed for proving the general lower bound

8. Unrelated comment: there are a few papers that appeared concurrently to this submission that might be of interest to the authors:
   - Tirinzoni et al. "A Fully Problem-Dependent Regret Lower Bound for Finite-Horizon MDPs", which derives similar instance-dependent lower bounds for the episodic setting
   - Tranos & Proutiere. "Regret Analysis in Deterministic Reinforcement Learning", which studies instance-dependent lower bounds for deterministic MDPs in the infinite-horizon (average-reward) setting
   - Marjani et al. "Navigating to the Best Policy in Markov Decision Processes", which studies best-policy identification in the infinite-horizon (discounted) setting

Typos and other minor comments:

- Line 22: I am not sure I understand what "more optimistic" means
- Line 31: irreducible?
- Caption of Figure 1: "a our"
- Line 99: it would be clearer to write V^\pi(s) = V^*(s) \forall s
- Line 105: I guess \chi denotes the indicator. That should be stated explicitly 
- Line 113: P was introduced without \mathbb
- Line 118: StrongEuler is a only a slight variant of the Euler algorithm from [33], so I would also mention that paper there instead of only attributing the algorithm to [29]
- LHS of the equation below line 328: there is an X instead of Z
limitations_and_societal_impact: Limitations are discussed. I do not see any societal impact.
review_title: null

Meta-review: This work proposes a new gap notion and provides corresponding instance-dependent regret upper bound and lower bound. The new gap definition gives a better characterization of the complexity of an RL problem. The paper is well-written and structured. The reviewers believe the paper is good for publication in NeurIPS.
Decision: Accept (Spotlight)