The Power of Resets in Online Reinforcement Learning

Summary

This paper study the online RL having access to a local simulator with general function approximation. Their results unclock new statistical guarantees. First, $Q^*$ realizability together with coverability assumption are enough for sample-efficient online RL under this setting. Second, their results further implies that the Exogenous Block MDP problem is tractable under this setting. Finally, they complement their theoretical finding with a computationally efficient algorithm.

Strengths

The paper is in general clearly written. The idea of leveraging local simulator to facilitate online RL with general functionn approximation is novel and leads to several important observations that previous works are out of reach.

Weaknesses

Maybe due to space limit, some terms lack of definition or discussion, see questions for details. The algorithm in section 4 is highly technical and somewhat difficult to follow. Based on the current context, it appears that the role played by the local simulator is underexplained. One might question if most parts of the algorithm are adaptations of previous techniques to the general function approximation setting. It would be great if the novelty and insights can be highlighted.

Questions

1. What is the double sampling problem mentioned on line 170? 2. What is the distribution shift mentioned on line 313? 3. What is the $v_h$ on line 16 of Alg 2? Minor issues: 1. Definition of the confidence set in Alg 1, the summation $\sum_{h\leq t}$, is this a typo? 2. Double such that on line 221, and the comma and period in the end.

Rating

7

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Yes.

Summary

The authors show that local simulator access removes Bellman completeness for MDPs with bounded coverability. This generalizes the results of existing works that are limited to low-rank or linear structures. On the statistical front, the authors analyze the sample complexity of SimGOLF using coverability, but the algorithm itself is computationally inefficient. To resolve this they propose RVFS, which is computationally efficient with respect to (1) a regression oracle, and (2) a convex optimization oracle over the value function class $\mathcal{V}$. In order to obtain sample complexity guarantees here, however, stronger assumptions such as pushforward coverability or $Q^\star$ gap are required. (For some context behind the proceeding comments, I am familiar with the analysis of GOLF and its variants [4,31,61], but not with the local simulator literature [38,63,57] beyond a brief glance. )

Strengths

The motivation for the paper is clear, and generalizing RL in local simulators to structures beyond linear is a valuable contribution. SimGOLF/ Thm 3.1 are clean results, and I appreciate that the authors tackled the problem of computational efficiency in RVFS.

Weaknesses

My impression is that the analysis of SimGOLF / Theorem 3.1 has limited technical novelty given [61]. That's not to say it's not a valuable contribution. **Oracle efficiency** My biggest concern is that RVFS does not seem as "oracle-efficient" as claimed, and the discussion on this is somewhat lacking. For example, the authors could have stated more exactly what their definition of computational efficiency is (or is it just that it "reduces to convex optimization"?). They might have also provided an analysis on the # of calls to computational oracles before convergence. In particular, it seems RVFS needs to solve the convex optimization in Line 8 for every $(x,a)$ in the core set, for $N_{test}$ times (which is like $\varepsilon^{-1}$...?), and then for every possible action. Further, RVFS makes recursive calls to itself. Can this avoid $\mathrm{poly}(\mathcal{X}, \mathcal{A}, \varepsilon^{-1})$? More minor, but it seems $\mathcal{V}$ might need to be a convex set for efficient calculation of Line 8 (L355-358), which does not immediately gel with the "holds for general function approximation" or "neural networks" claims? In the grand scheme of things I'm sort of not that bothered by this. **Assumptions for RVFS** I am not opposed to make stronger assumptions for RVFS necessarily, but I would have liked to know more about why. For example, is it possible to give some intuition for why coverability alone is insufficient to analyze RVFS? And how do the gap or pushforward coverability assumptions help with this? **Comparison to existing work** The authors mention that local simulator algorithms utilizing core sets exist for linear value function approximation exist, and I imagine that RVFS might also be applied to these settings. However, I find the consideration of previous literature to be quite limited, and I would have appreciated some discussion on how the sample/computational complexity of the algorithms compare (if they are comparable).

Questions

The questions below also include the specific ones from "weaknesses" that I would like to be answered. I would be happy to raise my score if my concerns are adequately addressed. 1. Is it possible to analyze the complexity of oracle calls required to achieve the learning guarantee in Theorem 4.1? Will it be dependent on $\mathcal{X}$? 2. I imagine RVFS can be applied to the linear $V^\star$ or $Q^\star$ settings from [55,57,38]. Are the guarantees for RVFS comparable? I'm not necessarily looking for "better" performance because RVFS is more general, but just some sense of how big the gap might be (if there is one). Or just some discussion on the topic as I myself am not familiar. 3. Could you comment on the barriers to obtaining guarantees for RVFS under coverability, and/or why gap / pushforward helps? 4. The definition of the confidence set in Algorithm 1 seems a little weird (maybe typo?), particularly the $\sum_{h \le t}$. Currently it seems like you throw samples from previous iterations away, is that intentional?

Rating

7

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

I believe the limitations of RVFS could benefit from greater discussion per my previous comments.

Summary

The paper introduces the SimGolf algorithm, which leverages local simulator access to reset to previously visited states and sample multiple trajectories. This approach enhances sample efficiency and accuracy in value function approximation, particularly in high-dimensional MDPs. The SimGolf algorithm uses local simulator access to achieve new statistical guarantees, allowing for efficient learning in environments with low coverability. Additionally, the paper presents RVFS (Recursive Value Function Search), a computationally efficient algorithm that achieves sample complexity guarantees under a strengthened statistical assumption known as pushforward coverability.

Strengths

- Introduces a novel approach that uses reset capability in reinforcement learning to significantly improve sample efficiency. - Provides strong theoretical analysis and new statistical guarantees for reinforcement learning with local simulator access. - Proposes two innovative algorithms (SimGolf and RVFS) with clear theoretical benefits. - The paper is generally well-written and explains the new algorithms and their theoretical foundations clearly. - Addresses a significant problem in reinforcement learning by enhancing sample efficiency and providing robust theoretical guarantees.

Weaknesses

- The paper breaks with the expected shape of a NeurIPS paper (numbered list in abstract, missing discussion or future work). While deviations are acceptable if justified, the current format lacks some important aspects. - The abstract includes references and attempts to serve as a conclusion, which is unconventional and detracts from its clarity. The abstract should be a short, plain summary of the paper It is also not the place to reference other works, as the abstract should be self contained. - The paper lacks a dedicated conclusion or discussion section, which would be crucial for contextualizing results and suggesting future work. - There is no experimental data provided (which is fine for a theory paper), but there should then at least be a discussion on expected practical benefits and an outline of plans for empirical validation as part of a future works section. In the area of RL we observe a significant gap between the theoretical understanding of performance guarantees and the actual observed performance of certain setups in practice. I would therefore regard the benefit of a paper, that restricts itself to only theoretical work itself as limited; actual experiments are needed to validate the practical applicability of the new findings. Please outline such in a future works section.

Questions

- How does SimGolf perform in practical environments compared to regular RL and MCTS? - What specific types of environments are expected to benefit most from SimGolf? - Are there any preliminary empirical results or plans for validation in real-world applications? - The training process produces a final policy and set of Q functions. It should therefore be possible to use the presented algorithm for 'pre-training' in a simulator with reset capabilities, but then continue training with a SAC-like approach on real world data? - The paper lacks an explicit differentiation from existing methods. Is the following summary correct for contextualizing the work? (This is mostly just for my own understanding of the presented work) - Regular RL requires only the ability to take actions and observe resulting new states, enabling linear rollouts. It performs single, uninterrupted rollouts without the ability to reset. - MCTS (Monte Carlo Tree Search) requires a complete and known transition function, allowing iteration over all possible child nodes from each state. It builds and expands a search tree incrementally by iterating over all possible actions and simulating outcomes. This method utilizes comprehensive exploration through rollouts and backpropagation within the search tree, resulting in high accuracy of value estimation. However, it is computationally intensive and requires full knowledge of the transition dynamics. - SimGolf strikes a balance between the simplicity of regular RL and the higher performance of MCTS. It requires the ability to reset to previously visited states and resample the next state under the same or different actions. This method does not necessitate complete iteration over all possible actions and transitions. Instead, it enhances sample efficiency by allowing targeted resampling after initial rollouts (under the same or different actions). The agent can reset to critical states identified during the initial exploration and simulate multiple future trajectories from those states, improving the accuracy of value function estimation. SimGolf uses the reset capability to gather multiple samples from key state-action pairs, updating a confidence set of value functions based on empirical Bellman error estimates, combining the benefits of comprehensive exploration with more modest demands on the environment. I was assigned to this paper after the regular review period so I did not have time to go through the presented math inn detail. Rely on the other reviews to check those.

Rating

6

Confidence

2

Soundness

3

Presentation

2

Contribution

3

Limitations

- The lack of experimental validation means the practical benefits and real-world performance of the algorithm remain uncertain. - A discussion on future work and plans for empirical validation would be beneficial, detailing how the authors intend to demonstrate practical improvements.

Summary

The paper presents some theoretical results for new reinforcement learning algorithms with a sophisticated approach to a simulator environment.

Strengths

Paper presents an extensive theoretical study.

Weaknesses

Practical applications of the algorithm remain questionable. The modifications themselves might seem trivial.

Questions

A clarification of the application of the algorithms and their implementation might improve the paper.

Rating

4

Confidence

1

Soundness

2

Presentation

2

Contribution

2

Limitations

I don't think there's any negative societal impact.

Follow-up re: number of oracle calls

Thank you for your detailed reply, which has addressed most of my comments. However, my primary concern was the number of Oracle calls required (which is important for computational efficiency), and I'd like to ask one follow-up question about this. The rebuttal states that RVFS requires only polynomial in $C_{\mathrm{cov}}$, not $|\mathcal{X}|$, calls. Does the analysis currently in the paper show this, and is there a section or result that I can reference to see this (or at least get a sense of the argument)? I wasn't able to find this given a brief scan of the appendix, and I apologize if I've missed it. Thank you.