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: The paper studies the instance-dependent logarithmic regret bounds on the RL problem with general function approximation. The paper introduces the notation of “adaptivity complexity”. The paper designs two RL algorithms with general function approximation separately in model-based and model-free settings that archive the logarithmic regret bounds and logarithmic adaptivity complexity simultaneously.
strengths_and_weaknesses: Logarithmic instance-dependent regret bounds and logarithmic switching cost has been studied in tabular RL and RL with linear function approximation. The idea is not novel, but this paper is the first work that establishes a logarithmic instance-dependent regret and logarithmic switching cost guarantee for RL with general function approximation. This is a good paper. The paper is well-written and clearly delivers the message. Related work is covered well. The paper makes strong use of the theoretical results published in a previous paper [KSWY21] but presents novel and important generalizations to model-based RL.


questions: I think this paper is somewhat missing an assessment of the tractability of the proposed algorithm, especially the computational complexity of the optimization problems involved in Algorithms 2 and 3. Can the author clarify this?
limitations: The assumptions and limitations are stated in Section 2.
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: The paper considers the reinforcement learning problem with 
general function classes and general model classes. In a specific
setting with a strictly positive optimality gap, the authors show 
logarithmic regret can be achieved (in contrast to the minimax 
optimal regret $\sqrt{T}$). Moreover, the proposed algorithm 
only switches policies for polylog times. The results are established
in both the model-based and model-free settings.
strengths_and_weaknesses: 1. The paper is well-written, with an extensive literature review
and a clear exposition of the proposed method; the analysis of 
the algorithm is complemented with explanation and intuitions.

2. Technically, the paper is solid to my knowledge and the extension of the method is nontrivial. 

3. It might help if this paper could show numerical results
illustrating the claims made in theories.
questions: In bandit problems, the optimal number of batches/switches
is of the order $\log\log{T}$. Is the number of switches $\log{T}$ optimal
in RL, or is it the same as in the bandit problem?

limitations: The authors have adequately addressed the limitations and potential negative societal impact of their work.
review_title: null

final_score: rating: 4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.
review_content: summary: The paper studies the problem of regret minimization for episodic RL with general function approximation. Under both model-free and model-based settings, logarithmic regret and policy switch results are presented. 
strengths_and_weaknesses: Pros: The paper is very well written, and all the results are presented clearly. The background and the related works of this work are also discussed sufficiently. The results presented are new and important to RL as well.

Cons: The results are not very surprising given the prior works on RL with logarithmic regret and RL with general function approximation. The peeling techniques for regret decomposition are also used to obtain logarithmic regret for RL under linear function approximation. The other parts of the proof for the main theorem and the sub-sampling method mainly follow from results for RL under general function approximation [KSWY21]. By the property of the sub-sampled dataset, and as Lemma C.3 pointed out, logarithmic policy switching is a direct result.
questions: Could you elaborate on the technical improvements made in this paper over previous results? I would also suggest discuss Theorem 3.1 and Theorem 3.2 in context of previous results of log regret for RL under tabular/linear function approximations. 
limitations: The authors discussed this and I agree that this is a theoretical work, which has no potential societal impact.
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: Regret in the RL setting has been extensively studied for linear approximations but not for other families of functions. In addition, it is more typical to have episode specific policies which is clearly undesirable. The authors study regret for a general set of functions and with a switching cost of policies among episodes. They exhibit an algorithm with optimal regret by showing an upper bound on regret of their algorithm and a lower bound of the same order. 

Minor typos: line 57: to model-based 
line 129: of the optimal policy
strengths_and_weaknesses: Although this is an analytical paper, it would be great to showcase practical performance of their algorithm. 
The introduction is slightly misleading as it doesn't mention that the regret bounds are in the probabilistic sense. 

The paper has many contributions, including the algorithm and the underlying non-trivial analyses. 
questions: Theorems 3.1 and 3.2 use tau and delta. The statements hold for any non-negative values of these two parameters. It's never discussed what value should they have in order to minimize the regret bound. 
limitations: This being analytical work, there are no clear societal negative impacts.
review_title: null

Meta-review: metareview: Reviewers are generally positive about the paper and I see that this paper's techniques are differentiated from KSWY 21. Please make sure you address all the reviewers' comments and incorporate them (and any new experimental results, if applicable) in your camera-ready.
confidence: Certain
Decision: Accept