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: This paper proposed a new algorithm in the setting of MDP with approximate linear value function (for any policy, the value function is approximately linear in l infinity norm with respect to a given feature map) along with a local access simulator. The algorithm CAPI achieves the best known sub-optimality bound along with the best known query cost in the local access setting, previous algorithms achieve only one of them. The algorithm is based on Policy iteration and a new technique of partition the observed state space into layers and planning policies for each layer with a refined accuracies, which maybe of independent interest.
strengths_and_weaknesses: Strengths: The algorithm is highly novel although the key idea of core set is proposed in previous papers. The proof is clean and looks sound to me. The result is pretty great since the algorithm achieve both the best known query complexity and accuracy. (Compared to [Lattimoore et al., 2020] and [Yin et al., 2022])

Weaknesses: Lack a lower bound. A more detailed discussion of why previous algorithm [Yin et al., 2022] cannot achieve the tight bound is recommended. As well as a comparison of computation complexity with previous methods.
questions: (1) Is there a lower bound in the random access setting, how does the result compare to it?

(2) Is it possible to use this idea in the general function approximation setting? 

(3) What can we do if we are not granted with the feature but only have a feature class?
limitations: Yes
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 presents a confidence approximate policy iteration algorithm for discounted MDPs. The authors then prove that the algorithm produces a deterministic stationary policy with an optimal error bound which scales linearly with product of the effective horizon and the worst-case approximation error of the action-value functions of stationary policies.
strengths_and_weaknesses: The authors extend previous works to improve on the performance bounds but it is very similar to previous works by Yin et. al.
questions: Algorithm and proof techniques very similar to existing works, the contribution is not very clear
limitations: Proof techniques very similar to existing works
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 authors consider the linear action value function setting, and in particular the local planning problem with value-based methods.
They obtained an algorithm whose approximation error grows linearly with the horizon all the while returning a stationary policy. In terms of query complexity, they achieve the best known accuracy and query complexity at the same time.
strengths_and_weaknesses: I believe that this is not the first result with an approximation error that scales linearly with the horizon. For example, see what could be inferred from “Q* Approximation Schemes for Batch Reinforcement Learning: A Theoretical Comparison” by Xi et al. (To be clear this work is quite different to the proposal here and does not diminish the novelty of the work submitted).

I believe that although the work strictly improve on prior art, it is nonetheless quite technical and of potential interest to a technical audience.

Question: this work revolves around improving the dependence on the approximation error. However, the definition of approximation error seems is very strong (\ell-infty). In practice, such value is likely to be large. Given that a local access is assumed, can it be relaxed to other more forgiving definitions? In particular, I am referring to non \ell-\infty definitions.
questions: See above
limitations: The work is quite technical and theoretical and could be of interesting to a more narrow audience. Since the work seems to be computationally implementable, it would be nice to have some limited experiments as well (in simulated domains), although this is not standard for this sub-area of RL
review_title: null

Meta-review: metareview: All reviewers and the AC believe this paper makes valuable contributions to the theoretical reinforcement learning community.
confidence: Certain
Decision: Accept