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: In this paper, the optimization of instance-dependent sample complexity for reinforcement learning (RL) under linear MDP is studied. The PAC policy learning setting is considered, which is to identify the best policy among all. An elimination-style algorithm with a novel exploration strategy is proposed. The key idea lies in using online Frank-Wolfe to explore the directions which reduce the sample variances most. The algorithm achieves the first instance-dependent sample complexity guarantee for linear MDP. The analysis also shows that low-regret algorithms can be sub-optimal in certain instances, showing the advantage of the proposed algorithm.
strengths_and_weaknesses: Strengths:

1. The paper proposes an algorithm that is the first to achieve the instance-dependent sample complexity guarantee under linear MDP. The result is original and novel.

2. The exploration strategy based on online Frank-Wolfe is interesting and can be of independent interest for other bandit learning problems.

Weaknesses:

1. According to the algorithm, it is implicitly assumed that the policy set has finite cardinality. This assumption is not reasonable. Since there are infinite states in a linear MDP, the number of all policies should also be infinite. I think this is a major limitation of the proposed algorithm and analysis.

2. Another limitation is that the instance-dependent term in Theorem 1 does not have a clear explanation. It is not easy to think out which kind of linear MDP the proposed algorithm can be advantageous. 

3. I also have some doubts about the exploration step. In Line 6 of Algorithm 1, the number of data to collect is set to $K_{h, l}$, which is closely related to the overall sample complexity, but there is no explanation of how this number is set. Furthermore, the sample complexity of Algorithm 2 is proposed in Theorem 6, which is of order $O(1/\epsilon_{exp}$. But there is no definition of $\epsilon_{exp}$ in the paper. Is $\epsilon_{exp}=\epsilon$? If this is true, I can't understand why the instance-dependent bound in Theorem 1 can hold, since as a step of Algorithm 1, Algorithm 2 has already required $O(1/\epsilon_{exp})$ instances.

4. I think some proofreading needs to be done to improve the notational explanations. There are some notations without defining previously or immediately after their first appearance. 

Overall, I think the paper proposes interesting and novel results. But the weaknesses discussed above are not ignorable for me currently.

---
after rebuttal:

I increase my score since the responses address most of my doubts. I suggest including the explanations in the paper to improve clarity.

questions: Please feel free to point out the errors in the weaknesses that I proposed above.


limitations: The limitations and potential negative societal impact are properly discussed.
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: This paper studies the problem of sample complexity of RL with linear function approximation. Recent works have extensively studied this problem with a range of results for different versions and structural assumptions. However, this paper presents the first instance dependent sample complexity analysis for the linear MDP setting. The proposed algorithm is based on a policy elimination scheme which iteratively maintains a set of policies which lie within a $2^{-l}$ optimality gap from the optimal policy. The update step for this algorithm is based on a novel online experiment-design procedure which guarantees the collection of a sufficiently 'exploratory' dataset of state-action pairs at each step.

In terms of the formal results, the authors show the first instance-dependent sample complexity analysis for linear MDPs which can be shown to also yield a dimension-optimal rate in the worst case. Further, it is formally shown that there exists instances where the instance-dependent rate improves over the sample complexity of worst case optimal PAC-RL algorithms. Lastly, it is shown that the instance-dependent rate for the linear case recovers the instance-dependent rate for deterministic MDPs whereas it gives another instance-dependent rate for tabular MDP which can be provably better or worse than previous instance-dependent rates for specific instances. 
strengths_and_weaknesses: Overall, this paper is very well written and shows important and novel results for linear MDPs. I especially like the thoroughness of this paper where multiple aspects of instance-dependence are explored:
1. Instance-dependent analysis for linear MDPs: The algorithm is well explained and a novel method for the experiment design objective in (4.1) is also proposed and analysed. In the final rate, the authors show that the rate depends on factors which relate to hardness of exploring any direction in the feature space $\phi$, a policy gap term for the input policy class. A final result is obtained by showing that a policy class can be constructed for linear MDPs whose size exponentially scales with $d$ to derive the instance-dependent guarantee with respect to the optimal policy.
2. Demonstrating the utility of the instance-dependent rate: The authors show using Prop. 3 that there exists linear MDPs such that the instance dependent rate improves over the worst case rate by a factor of $d^2$. Further, it is shown that no existing PAC-optimal algorithm will get a polylog(d) rate for this problem.
3. Discussions for tabular and deterministic MDPs: I especially like the result in Prop. 5 which shows that the sample comeplxity for their algorithm is in fact another possible instance-dependent rate for tabular domains and can improve over previously shown instance-adaptive algorithms or in some cases perform worse than them. It brings an interesting question of unifying these different instance-dependent measure of complexity, and highlights possibilities of improvement even for the linear MDP case. For deterministic MDPs, previously known rate can be recovered upto $H$ factors.

**Weakness**:
This is a strong first result in this direction and hence has certain aspects which can possibly be improved:
1. Computational efficiency: Since the algorithm follows a policy elimination template, for establishing a guarantee wrt optimal policy, an exponentially large policy set needs to be constructed. The experiment design objective then iterates over the expected feature vectors for each policy to eliminate sub-optimal candidates. As such, it is not clear if a computationally efficient version of the solution can be derived.
2. Dependence on explorability parameter: The authors need to assume that there exists a policy which generates a full rank covariance matrix for the state-action features. In my understanding, this also affects the algorithm as the covariance matrices constructed in the experiment design steps are guaranteed to be non-singular using this assumption. Can the authors comment about the necessity of this assumption or potential ways to remove this?
questions: Please see the comments about computational efficiency and $\lambda_{\min}^*$ above.
In addition, I was wondering if there is a more intuitive interpretation of the complete instance-dependent term in theorem 1 instead of just the individual terms.
limitations: The authors do discuss the potential improvements in the conclusion and formally show that their algorithm does not yield the best sample complexity for some tabular domains. As such, I do not have any concerns about the discussions of the limitations.
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: This paper considers instance-dependent complexity of learning under linear MDPs. Based on a novel online experiment design in linear MDPs, the author proposes an algorithm whose sample complexity scaling with the instance-dependent complexity. This algorithm is worst-case optimal and beats any low-regret algorithm on an explicit example constructed by the author. 
strengths_and_weaknesses: Strengths:
- Interesting question. The question of obtaining worst-case optimal algorithms with linear function approximation has been well-studied recently. When it comes to instance-dependent RL, most of the recent work focuses on the tabular setting. Obtaining computationally efficient algorithms with tight instance-dependent sample complexity under linear MDPs is still an open question in RL.
- Great novelty. The author uses an online experiment design-based procedure to reduce the uncertainty of their algorithm.
- Enough comparison with the previous work. In Section 4.3, the author reduces their result to tabular and deterministic MDPs and carefully compares their results with the existing results.
- Well-written and easy to follow. Clear algorithms, definitions, assumptions and theorems.

Weaknesses:
- Lack of tightness. The paper does not show if the algorithm obtains tight instance-dependence.
- Computationally inefficient algorithm. 

questions: - Is the result in Theorem 1 tight with respect to the policy gap and the uncertainty? Does a general lower bound exist? Does the upper and lower bound match?
- Can the algorithm be applied to linear mixture MDPs setting? 

limitations: Lack of tightness w.r.t instance-dependence. Not tight w.r.t $H$ dependence. Computationally inefficient. The sample complexity result scales with the hardest-to-reach direction.
review_title: null

Meta-review: metareview: This paper considers instance-dependent complexity of learning under linear MDPs. Based on a novel online experiment design in linear MDPs, the author proposes an algorithm whose sample complexity scaling with the instance-dependent complexity. This algorithm is worst-case optimal and beats any low-regret algorithm on an explicit example constructed by the author. All reviewers are convinced by the contribution of this paper, and we recommend acceptance.
confidence: Certain
Decision: Accept