The Power of Resets in Online Reinforcement Learning

Novelty relative to prior work:

The algorithm presented in Section 4 is far from a simple adaptation of previous techniques. We now highlight some of the key algorithmic innovations:

• RVFS builds on the DMQ algorithm by [1]. Unlike the latter, we use a core set of state-action pairs instead of policies. This is crucial for our algorithm to work without the strong hypercontractivity assumption made by [1].
• One of the key algorithmic innovations is the use of Bellman backups (as in line 8 of Algorithm 2) to evaluate whether a new state-action pair should be added to the core set. This technique is unique to our paper and enables handling RL settings beyond linear function approximation. Incorporating Bellman backups in the test at line 8 is essential for proving that the algorithm converges under pushforward coverability.
• Additionally, the modification of RVFS to the exogenous setting, which includes a randomized rounding, is also novel.

Beyond these algorithmic innovations, the analysis of RVFS introduces new proof techniques, especially in the setting without a gap, that could be beneficial for broader applications beyond the settings studied in this paper.

What is double sampling?

What is the double sampling problem mentioned on line 170? The double sampling problem refers to the challenge of estimating $T_h g_{h+1}(x_h,a_h)=\mathbb{E}[g_{h+1}(x_{h+1}) \mid x_h,a_h]$ in (1), which requires more than one next-state sample starting from the state $x_h$. Generating multiple samples from any given state is only possible with resets; in the online setting without resets, a state $x_h$ may only be observed once, allowing only a single next-state sample. See e.g. https://x.com/nanjiang_cs/status/1672702613744410624 for more details on the double sampling problem.

What is distribution shift?

The distribution shift mentioned 313 is a well-known phenomenon the situation where for a new state action pair $(x_{\ell-1},a_{\ell-1})$, the distribution of the next state $x_{\ell}$ puts mass on new regions of the state space where the estimated value function is inaccurate. See e.g., sec 7.3 in https://arxiv.org/pdf/2312.16730 for more detail on the distribution shift phenomenon in RL.

What is the $v_h$ on line 16 of Alg 2?

$v_h$ represents an esitmate of $\mathbb{E}^{\hat\pi}[\sum_{\ell= h}^H r_\ell \mid x_h]$---see how the set $\mathcal{D}_h$ is constructed on line 15.

Technical novelty of SimGOLF in light of [1]

• We agree that the main technique behind our first result, SimGOLF, is quite simple, but we view this as a positive.
• In particular, our result shows that the challenging coverability + realizability setting, which was explicitly left as an open problem in prior work and allows for nonlinear function approximation, is tractable under local simulator access.
• Therefore, even though the proof for the fact that this result is tractable turns out to be remarkably simple, we think that the take-away message of the result is significant enough to merit publication.
• Finally, we view the simplicity as a strength, since it will likely enable other researchers to build on this technique and explore whether it extends to other interesting settings. Notably, this is the starting point for our second main result, RVFS, which attacks the even more challenging problem of designing statistically and computationally efficient algorithms. Indeed, given the complexity of RVFS, it is very difficult to imagine directly proving such a result or designing such an algorithm without already being aware that the setting under consideration is tractable, which is precisely what SimGOLF provides.

Oracle type:

The Oracle we require is precisely the one described on Line 356, which solves a convex optimization problem in function space. We note that similar Oracles have been used in prior works; see e.g. [3] (RegCB).

Number of Oracle calls:

Although not explicitly stated in Theorem 4.1, our analysis shows that the number of Oracle calls is polynomial in $C_{\text{cov}}, H, A, \log |\mathcal{V}|$, and $1/\epsilon$, with no dependence on $|\mathcal{X}|$. This holds despite the recursion in RVFS. We would not consider the algorithm Oracle efficient if the number of Oracle calls depended on $|\mathcal{X}|$. We will include the number of Oracle calls in Theorem 4.1.

Convexity of the function class:

The optimization problem in Line 8 would have the same value if V is replaced by its convex hull. This is because the optimization problem, which is of the form $\sup_{f \in \mathcal{V}_h} |\mathrm{Objective}(f)|$, where $\mathrm{Objective}(f)$ is linear if $f$, can be solved by considering the two subproblems (without the absolute value)

$\sup_{f \in \mathcal{V}_h} \mathrm{Objective}(f)$ and

$\sup_{f \in \mathcal{V}_h} -\mathrm{Objective}(f)$.

Since the $\mathrm{Objective}(f)$ is linear in $f$, the suprema in these subproblems will always be attained at vertecies of $\mathcal{V}_h$, so the convex hull would not change the values of these objectives. We will provide more details on this.

Coverability alone for RVFS:

The SimGolf algorithm uses the concept of global optimism, where the estimated value functions at each iteration are greater than the optimal value function in a pointwise sense; this greatly simplifies the analysis of the coverability setting using SimGolf. In contrast, RVFS does not employ global optimism.

There are RL settings that are only known to be statistically tractable using a global optimism approach; for example, the linear Bellman complete and the linear Q*/V* settings (see e.g. [3]). Our paper shows that a local simulator makes the coverability setting statistically tractable using global optimism (through SimGolf). It is unclear if the stronger pushforward-coverability assumption is necessary for algorithms that do not employ global optimism, like RVFS. We could not find a way to make the analysis of RVFS work with full coverability; the reasons for this are deeply rooted in the analysis of RVFS.

Handling the linear $Q^\star/V^\star$ settings:

RVFS can be slightly modified to handle the linear $V^\star$ and $Q^\star$ settings. Similar to existing results for these settings, the corresponding sample complexity would be polynomial in $d$, $1/\epsilon$, and $H$, without any dependence on $|A|$ or $|X|$. However, we have not worked out the exact exponents of $d$, $1/\epsilon$, and $H$ in the sample complexity. We would be happy to include such an extension in the final version. With the additional page available in the camera-ready version, we will provide a more detailed comparison to existing results.

Summation in the confidence set of Algorithm 1:

The sum in the definition of the confidence set of simGolf contains a typo indeed. We will correct this in the camera-ready version.

[1] Xie, Tengyang, Dylan J. Foster, Yu Bai, Nan Jiang, and Sham M. Kakade. "The role of coverage in online reinforcement learning." arXiv preprint arXiv:2210.04157 (2022).

[2] Foster, Dylan J., Alexander Rakhlin, David Simchi-Levi, and Yunzong Xu. "Instance-dependent complexity of contextual bandits and reinforcement learning: A disagreement-based perspective." arXiv preprint arXiv:2010.03104 (2020).

[3] Kane, Daniel, et al. "Computational-statistical gap in reinforcement learning." Conference on Learning Theory. PMLR, 2022.

Paper format:

Thank you for your feedback. We understand the importance of adhering to a standard format; however, we chose to prioritize a detailed explanation of our novel and complex algorithm to ensure that its intricacies were fully conveyed. We believe this approach still aligns with the presentation style of other papers accepted at NeurIPS. With the additional page available for the camera-ready version, we will include a more detailed discussion section and suggestions for future work to further enhance the clarity and completeness of our paper.

Experimental results:

While we acknowledge the importance of empirical results, these are beyond the scope of the current paper. Our focus is to understand the sample and computational complexity of RL when a local simulator is available. In terms of understanding the theoretical limitations of RL, we believe the results presented here are significant on their own. However, our paper does pave the way for new empirical questions, which we are excited to explore in future works, as we will highlight in the future works section.

How does SimGolf perform in practical environments compared to regular RL and MCTS?

SimGolf was never intended to be a practical algorithm. Its primary purpose is to demonstrate that the coverability setting, which we argue is a general RL setting, is statistically tractable under resets—a fact that was not previously known. For practical applications, RVFS, which shares similarities with MCTS and Go-Explore, is the more viable algorithm. We discuss the similarities between RVFS and MCTS in detail on page 9, under the section ‘Connection to empirical algorithms.’

What specific types of environments are expected to benefit most from SimGolf?

SimGolf operates under the coverability assumption, an intrinsic structural property of the underlying MDP. Therefore, environments expected to benefit most from SimGolf include Low-Rank MDPs and (Exogenous) Block MDPs, both of which satisfy coverability. These environments exhibit high-dimensional state spaces and require nonlinear function approximation. Exogenous Block MDPs, described in Section 3.3, capture real-world RL settings where observations include a high-dimensional, time-correlated signal irrelevant to the RL task. Learning to ‘ignore’ this signal in a sample-efficient manner is extremely challenging, an issue explicitly left as an open problem in previous work. However, we demonstrate in this paper that SimGolf and RVFS make this possible when resets are available. Additionally, we expect RVFS to perform well even in settings that do not strictly satisfy coverability, including those where MCTS has been used. RVFS can be viewed as a more principled version of MCTS.

Using our algorithms for 'pre-training':

As the cost of simulating real-world environments decreases, efficient algorithms like ours, which utilize a local simulator, will become extremely valuable for pretraining. One of the key points of our paper is to demonstrate that a local simulator enables the development of both statistically and computationally efficient algorithms for challenging RL settings, such as the Exogenous Block MDP setting.

Differentiation from existing methods:

We would like to reiterate that the primary objective of our paper and the algorithms we present is not to propose a competitor to MCTS. The goal is to understand the sample and computational complexity of RL under coverability when a local simulator is available. That said, your understanding of online RL and the workings of MCTS appears correct. We would like to add that MCTS has several major limitations compared to RVFS, including:

• MCTS requires finite states to iterate over all possible child nodes of each state, making it inapplicable in environments with continuous states, unlike SimGolf and RVFS.
• MCTS does not come with any provable sample-complexity guarantees and can fail even in simpler tabular RL settings. One reason for this is that MCTS (or some versions of it) uses rollouts with a fixed default policy (usually a policy that takes random actions), and the estimated value will correspond to this rollout policy. In contrast, our work reveals (through RVFS) that one needs to use the policy induced by the current estimated value function for rollouts. This approach is key for proving the sample complexity guarantees of RVFS. This simple idea can potentially be used to modify MCTS for better performance.

We will include a more detailed comparison between RVFS and MCTS in the camera-ready version.