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 studies the gap dependent sample complexity of obtaining the optimal policy in episodic RL with offline data. The authors first define the notions of uniform optimal policy coverage coefficient and the relative optimal policy coverage. The uniform optimal policy coverage characterizes how "explorative" is the offline sampling policy, and relative optimal policy coverage characterizes how different are the offline sampling policy and the optimal policy. Further, the authors establish an upper bound on the sample complexity of offline RL using the optimal coverage coefficient. Next, the authors argue that optimal coverage coefficient might be too small. Hence, they provide a sample complexity based on relative optimal policy coverage coefficient. Next, the authors provide the main proof techniques in their results. Finally, the authors provide a gap dependent lower bound on the sample complexity of their algorithm.
strengths_and_weaknesses: The main strength of the paper is a through study of offline RL in the episodic case. In particular, the authors provide both an upper bound and a lower bound, and they claim that they match up to some polynomial of length of the horizon H. 
The main weakness is on the appearance of gap_m in the sample complexity. Although I understand this is the main motivation of the paper from the beginning, but this quantity can be arbitrary small. The authors might claim that gap_m also appears on the lower bound, and hence their bound is tight. But as I explained before, I am not yet convinced by the lower bound, since it is in terms of expectation rather than high probability. 
Another issue is on the definition of ALG in the lower bound. This notion is not defined anywhere in the paper. This is critical, since it tells us about the kind of lower bound that the authors are claiming. 
questions: - In Assumption 3.1, are you implicitly assuming only deterministic optimal policies? The reason is that you are denoting \pi^*(s), which is the action taken at state s in the deterministic policy \pi^*.
- In the result of Theorem 4.1, why do you hide the dependency on log(1/\delta)? I believe it is more informative if you somehow represent that dependency here.
- In Theorem 7.1 you introduce the notion of ALG, but you have not defined this notion.
- The lower bound on Theorem 7.1 and Corollaries 7.1 and 7.2 are in terms of expectation. But the upper bound in Theorems 5.1 and 5.2 are in high probability. How do you relate these two? 
limitations: As mentioned earlier, the upper bound in the paper is stated in terms of high probability, but the lower bound is in terms of expectation. If the authors address this concern of mine, I am willing to increase my score.
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 provides an analysis of gap-dependent sample complexity in offline reinforcement learning. The main contribution is to show that under the optimal policy coverage assumption, the sample complexity can be improved to $O(1/\epsilon)$, compared to $O(1/\epsilon^2)$ bounds in previous analysis. Nearly matching lower bounds are also provided by the authors. 
strengths_and_weaknesses: Strength:

The paper is well-written and technically sound. Studying instance-dependent analysis for offline RL is a very important topic. 


Weakness:

The proof technique is not very novel. The contributions might have limited impact. 

questions: This paper is well written and technically sound. I tend to vote for reject due to the following concerns and questions. Please address these in the rebuttal and correct me if I misunderstand some critical part of the work. 

1. I am wondering why Theorem 4.1 cannot be implied by previous results by setting $\mathrm{gap}_{\min}=\epsilon$. If the output policy of an algorithm is $\epsilon$-optimal for some $\epsilon$ smaller than the gap, then we know that algorithm can identify the optimal policy. In fact, if I understand correctly, the proof of Theorem 4.1 indeed tries to argue this. 

2. I like the analysis in general. By applying the clip technique, the authors can first upper bound the regret by considering a not-so-pessimistic-MDP, then applying existing techniques to continue the analysis. This makes the proof very clear and easy to follow for readers that are familiar with the literature. My main concern is that the main idea is from existing techniques in the literature. Although the paper argues that the novelty of the analysis is to consider the variance during clipping, this contribution seems to be a marginal contribution to me. 

3. Theorem 5.1 shows the $\tilde{O}(1/\epsilon\mathrm{gap})$ upper bound. The authors argue that this significantly improves the sample complexity of $\epsilon$ is very small compared to the gap. I think this is a very nice contribution as it provides a sharper characterization of the sample complexity. However, I am wondering for $\epsilon>\mathrm{gap}$, does this also mean the proposed bound is actually worse than the existing results? Also, is $\epsilon << \mathrm{gap}$ really interesting? Again, if an algorithm can be $\mathrm{gap}$-optimal, we know it can identify the optimal policy. 

4. I have some question related to the lower bound (Theorem 7.1). In the construction, C^* is fixed to be A. Does that mean this lower bound is only correct for some data collection policies? 


5. One reason we prefer instance (or gap) dependent analysis over minimax analysis is that it can tell us if an algorithm is adaptively optimal. That is, if the algorithm is optimal for both hard and easy problem instances. However, as a recent paper pointed out, no algorithm can be instance-dependent optimal in offline RL (Xiao el al., 2021). This makes the contribution of this paper less interesting. Also, I think the paper should give some discussion about how the gap-dependent analysis considered in the paper is different with the instance-dependent analysis used in the literature (Lattimore and Szepesvari, 2020)


Xiao, C., Wu, Y., Mei, J., Dai, B., Lattimore, T., Li, L., Szepesvari, C. and Schuurmans, D., 2021, July. On the optimality of batch policy optimization algorithms. In International Conference on Machine Learning (pp. 11362-11371). PMLR.

Lattimore, T. and Szepesvári, C., 2020. Bandit algorithms. Cambridge University Press.


limitations: Please see the previous section.
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 gap-dependent bounds for offline tabular RL. In particular, they show that under the optimal policy coverage assumption and the minimum positive gap, pessimistic algorithms achieve the rate of $1/N$. In the additional condition that the density of the behavior policy is uniformly lower bouned at the reachable states of an optimal policy, pessimistic algorithms precisely identify an optimal policy using finite samples. They also accompany with their upper bounds with nearly-matching lower bounds for each case. The paper also proposes the so-called deficit thresholding technique, based on the technique in an online counterpart, to analyze offline tabular RL with gap information. 
strengths_and_weaknesses: ## Strengths: 
- the problem is novel and interesting 
- the theoretical claims are sound and interesting to the offline RL community 
- the analysis is quite general and neat, with a new technique called deficit thresholding that seems interesting 
- every upper bound is backed up by nearly-matching lower bounds 

## Weaknesses: 
- The results and the techniques are only limited to tabular representation and require independence assumption on the episodes of the offline data. 
- It is sometimes not trivial to locate the proof of the main result in the paper
questions: - Lemma 6.1 is particularly interesting as it gives a stronger upper bound on the sub-optimality when pessimism and gap information is used than when the gap information is ignored. However, I seem not to be able to locate the proof of Lemma 6.1 in the appendix. Do I miss something?
- Intuitively, what is the role of subsampling in Algorithm 2 and how does it contribute to the final bound?
limitations: See the weakness section.
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: In this paper, the authors considers the offline MDP problem with an episodic setting. For this type of problem, existing works provide a minimax optimal sample complexity of  $O(H^3 S C^* \epsilon^{-2})$, given a finite single policy concentrability coefficient $C^*$. In this paper, the authors further extend the discussion on the problem based additional structure of a lower bounded Q-function gap or a lower bounded visitation probability of the behavioral policy on the support of the optimal policy. Based on these additional structures, $O(\frac{C^*}{\epsilon \cdot gap_{min}})$ or $O(\frac{1}{P \cdot gap_{min}^2})$ sample complexity are derived. Lower bounds are established and almost matches the provided upperbounds except for a factor of $H^2$. 

Overall, the reviewer think this is a good submission that complete a missing part of the offline RL when the problem is simple (in terms of well lower bounded gaps). The discussion is complete and the presentation is clear. 
strengths_and_weaknesses: Strength #1. This paper complete a missing part of the offline RL when the problem has some strictly lower bounded gaps in optimal Q function or behavioral policy. 

Strength #2. The discussion is complete in the sense that both lower and upper bounds are provided. 

Strength #3. The presentation is clear and easy to follow. 

Weakness: no obvious weakness found from the reviewer point of view. 
questions: The reviewer may need to make some more explanation of what the subsampled VI-LCB (Algorithm 2) is doing. In particular, it will be helpful if the authors could add some intuitive discussion on why it is needed instead of simply applying the VI-LCB. 
limitations: NA. This is a pure theoretical result.
review_title: null

Meta-review: metareview: This paper studies gap-dependent sample complexity in offline tabular RL. The authors show that when there is a gap in the optimal Q-function (and the density ratio between optimal and behavior policies is upper-bounded), the sample complexity can be improved from $O(1/\epsilon^2)$ to $O(1/\epsilon)$ using a pessimistic algorithm. The authors also provide gap-dependent lower bounds. 

The work seems correct and well-executed. It is of somewhat limited impact given the strong assumptions (tabular MDP, coverage) but fills a gap (pun intended) in the literature and the results are interesting enough to warrant acceptance.

confidence: Certain
Decision: Accept