Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studies deployment-efficient reward-free exploration problems in the linear MDP setting. The authors propose an algorithm that can achieve optimal deployment efficiency.
strength_and_weaknesses: Strength:

The theoretical results seem to be sound although I did not check all the details. The writing is clear and the discussion about prior work is sufficient.

Weakness:

I think this paper is a combination of several existing RL theory works. Reward-free exploration problems with linear function approximation have been studied in the literature. Deployment-efficient (similar to low-switching cost RL) problems have also been studied. This paper combines all the ingredients and resolves some additional technical difficulties to obtain the new results. This is good but I feel the novelty is not significant.
clarity,_quality,_novelty_and_reproducibility: I think the paper is overall well-written. The results appear to be new in the literature, although not novel enough.
summary_of_the_review: I think this paper is good overall. I did not check the details of the proof so I don't have high confidence in my assessment.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: This paper studies the problem of deployment efficient reinforcement learning with linear function approximation under the reward-free exploration setting. The authors propose a new algorithm that achieves optimal deployment complexity and near-optimal sample complexity at the same time. Their techniques include an exploration-preserving policy discretization and a generalized G-optimal experiment design, which makes incremental contributions to the RL theory community.
strength_and_weaknesses: Strength
S1: The proposed algorithm achieves SOTA sample complexity and preserves optimal deployment complexity simultaneously.
S2: The proposed exploration-preserving policy discretization looks novel.

Weakness
S1: The proposed algorithm appears to be only making limited improvement compared to existing works in (Huang et al. 2022). Specifically, the paper considered a well-formulated dedicated problem, yet only makes a factor of d improvement on sample complexity, compared to that in (Huang et al. 2022). Besides, the proposed algorithm is computationally inefficient.
S2: The technical contribution of this paper is limited and below the threshold of ICLR. The basic algorithm framework looks similar to that in (Huang et al. 2022), except upgrading the policy set and estimating the value functions instead of optimism, as pointed out in Appendix G. Besides, the idea of estimating the value functions instead of optimism has already been proposed in (Chen et al. 2021) for reward-free exploration in linear mixture MDPs.
S3: The overall writing is not very clear such that readers are hard to follow the technical points, while this paper focuses on algorithm techniques. It is strongly recommended that authors could provide more details about G-optimal design in the main body of the paper.

(Chen et al. 2021) Chen, Xiaoyu, Jiachen Hu, Lin F. Yang, and Liwei Wang. "Near-optimal reward-free exploration for linear mixture mdps with plug-in solver." arXiv preprint arXiv:2110.03244 (2021).

Comments and Questions
C1: The writing of the introduction looks similar to that in (Huang et al. 2022) and does not provide much further information.
C2: The linear MDP definition in (Jin et al., 2020b)’ paper is different from this paper. There $\mu_h$ is a matrix, not a vector.
C3: Assumption 2.1 is very strong and limits the generality of the algorithm, as those in (Zanette et al., 2020b; Wagenmaker & Jamieson, 2022). Since under linear MDP, if some direction is hard to encounter, we do not necessarily need to gather much information on this direction. Besides, I do not find analogous assumptions in (Huang et al., 2022).
C4: It is more common to say different “stages” of $h$, instead of “layer”
C5: The full-text layout is poor since the authors manually decrease the margin between paragraphs and sections. For example, there is an overlapping between the text and the footnote line.
C6: In the paragraph below Theorem 7.1, what is the “mild assumption” to recover the best-known result from (Qiao et al. 2022).
C7: As stated in Section 7.2, why the computational issue of the algorithm is usually not considered as a fundamental barrier? A computationally-inefficient algorithm largely hurts the significance of the proposed algorithm.

clarity,_quality,_novelty_and_reproducibility: The writing of the paper can be improved. The authors should also further highlight the novelty of their results, in particular, compared to that in (Huang et al. 2022). 
summary_of_the_review: The paper considers a well-formulated theoretical problem and makes incremental improvements to existing algorithms. Although some parts of the algorithm and proof are novel, the proposed algorithm is computationally-inefficient, and the proposed techniques are dedicated to the DE linear MDP. Thus, the overall contributions are marginally below the ICLR threshold.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper studies reward-free learning for linear MDPs. In particular, the authors focus on reducing the number of deployment (or switching cost). The proposed algorithm achieves a sample complexity of $\tilde{O}(d^2H^5/\epsilon^2)$ and deployment complexity $O(H)$, where the order of $d,\epsilon$ are near-optimal in the sample complexity, and the deployment complexity is tight up to constant factors.
strength_and_weaknesses: Strengths: As stated above, the theorectical results of this paper are non-trivial. In technique, the major contribution is  utilizing the G-optimal design to reduce the order of $d$. There are also some interesting by-products, e.g., resutls in Section 7.


Weakness: My major concern is the computational cost of the proposed algorithm. The authors also admit that the optimization problem (1) is computational intractable. In my opinion it should not be neglected. For the tabular case, recent work [Zhang et. al.] has achieved a computational efficient algorithm to minimize the number of batches (or deployments), where the authors manage to avoid enumeration over the policy space. So it is natural to ask whether efficient algorithm for linear MDPs is possible.

Reference: [Zhang et. al.]  Near-Optimal Regret Bounds for Multi-batch Reinforcement Learning
clarity,_quality,_novelty_and_reproducibility: The paper is well presented. There is no numerical experiments.
summary_of_the_review: Given the considerations above, the paper is on my broaderline. I tend to accept it currently.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper studied the deployment efficient reinforcement learning in linear MDP. The authors proposed new algorithms with improved sample complexity bound than previous papers as well as the near-optimal deployment complexity.
strength_and_weaknesses: # Strength

The sample complexity to state of the art, to my knowledge. The algorithm also seems interesting and somewhat novel.


# Weakness

I think the main issue is whether it is appropriate to claim the algorithm does not require the knowledge of $\lambda^*$. It seems to me that the main reason the algorithm does not use the knowledge of $\lambda^*$ is because the authors assumed that the accuracy level $\epsilon$ is smaller comparing with $\lambda^*$. From this perspective, it is kind of misleading to claim this paper get rid of knowledge of $\lambda^*$. Or maybe the authors should include discussion about how to avoid knowledge of $\lambda^*$ for arbitrary $\epsilon$.

Minor issues:

(1) the linear MDP is kind of restrictive, although more general than tabular setting.

(2) when $\lambda^*$ is extremely small, the algorithm can only success when choosing a extremely small $\epsilon$.

(3) algorithm seems not computationally efficient
clarity,_quality,_novelty_and_reproducibility: The paper writing is clear and the proof seems correct. The algorithms and parts of the analysis are novel to me.
summary_of_the_review: Although some weakness in this paper, I still found the results interesting, and I recommend for the acceptance.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: This paper presents a novel algorithm that simultaneously achieves nearly tight sample complexity and switching cost in reward-free linear MDP. The theoretical result is solid. Multiple new theoretical tools, including policy discretization and a generalized G-optimal experiment design, are introduced to enable tighter analysis, and they can be of independent interest. One weakness is that the proposed algorithm is computationally inefficient. In my opinion, this is an example of the troubling ongoing trend in RL theory research. Many theory papers propose algorithms that sacrifice computational traceability for statistical gains, and in my opinion, such trends should not be encouraged. Therefore, I will only recommend a weak acceptance.
justification_for_why_not_higher_score: The contribution is nitch and not likely to be of great interest to the general RL community.
justification_for_why_not_lower_score: NA.
Decision: Accept: poster