Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 6: Marginally above the acceptance threshold
review_content: summary: This paper considers the problem of learning to sufficiently explore an MDP in order to effectively provide a generative model that can be used for downstream learning tasks by algorithms that require a generative model. An algorithm is given that leverages SSP results in order to force exploration of certain state-actions that may be required by the arbitrary down-stream algorithm. Sample complexity upper and lower bounds are proved to demonstrate the samples required to meet the budget prescribed by the downstream algorithm. Several example tasks that require non-trivial exploration are shown to make use of the algorithm.
main_review: Overall I think this is a nice paper that presents some interesting theoretical results via both upper and lower bounds on sample complexity. To the best of my knowledge, the algorithm seems new. The principle behind it is fairly straightforward in that it leverages SSP algorithms to do the heavy lifting but in a convenient way to properly explore to meet the budget. The example applications are definitely appreciated and it is promising to see that the algorithm yields competitive results theoretically in these settings. As a result, the work certainly seems thorough and there are some promising directions for future work, for example, by understanding how this extends in the function approximation setting. The related work seems to sufficiently distinguish this paper from others. The experiments are also fairly comprehensive and nicely complement the theory for the most part.

Despite the interesting results, my main reservation regards the applicability of those results. There seems to be a bit of a mismatch between how the problem is motivated in the beginning and how the results are demonstrated in the main content. From the introduction, the impression is that the sampling oracle developed in this paper is to be used along with a generative model algorithm in two stages to solve a particular downstream RL problem that would otherwise require an online algorithm. But to this, my question is: why not just use an online algorithm which is already fairly flexible and skip the two stages? This is the case for the treasure problem. The model estimation task doesn’t really specify a downstream task, so this seems to be in some conflict with the initial motivation of the paper too. The cost-free goal-free task seems to be the most convincing of three since no signal can be used by an online algorithm (but they could still be used for reward-free exploration). In summary, I am not entirely convinced of the general applicability of the results or the potential impact of solving this particular problem. 

In the experiments, for the treasure problem, I am a bit skeptical of setting the budget to 10 as this is not exactly what was advertised in the problem statement in the theory. The algorithm is also only slightly better than UCRL and only in one domain (which is not necessarily a bad thing), but this leaves the reader wondering what the performance on the actual problem would be, burn-in phase and all.

limitations_and_societal_impact: See main review for limitations and suggestions.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper proposes to decouple the exploration problem in RL into an objective-specific part with access to a sampling oracle, and an objective-agnostic exploration part. For the objective-agnostic part, the paper proposes the GOSPRL algorithm with bounds on its sample complexity to meet the sampling requirement. Then GOSPRL is then combined with some sampling oracle-based algorithms to provide sample complexity for three types of RL problems.
main_review: Exploration-exploitation in RL is a very challenging problem, and the paper proposes to tackle the problem by decoupling it into a objective-specific part and an objective-agnostic part. The approach is inspired by the algorithms with sampling oracles in the literature which assume to have access to sampling oracles providing samples for a given state-action pair. Such sampling oracle-based algorithms can be used for the objective-specific part, so the paper focuses on the remaining objective-agnostic exploration part.

The objective-agnostic exploration part can be viewed as an extension of the pure-exploration approach by introducing the sampling requirement function for each state-action pair. By utilizing techniques from stochastic shortest path problems, the paper proposes the GOSPRL algorithm to collect samples specified by the sampling requirement. Sample complexity bounds are provided by connecting the sample collection problem to a sequence of stochastic shortest path problems.

For certain problems when sampling oracle-based algorithms are available, combined with GOSPRL we can get some good sample complexity bounds for these exploration problems. The paper provides three examples: one is the sparse reward discovery problem where the sampling requirement is trivial, another one is model estimation without considering the reward, and the third one is on reward-free exploration which extends prior finite-horizon results. Simulations are provided to verify the theoretical analysis.


limitations_and_societal_impact: The settings where the proposed method works are clearly stated.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The authors introduce a general technique for exploring the MDP in an SSP problem. Their approach extends the notion of reward-free exploration to  an "objective-agnostic" scenario, in which the goal is to generate a prescribed amount of samples from any state and action. The authors analyze the proposed algorithm and provide a sample complexity bound.

Then, the authors show this technique can be leveraged to solve specific scenarios which fit the communicating MDP setup. For these scenarios, the authors show the superiority of their approach with respect to previous works.
main_review: 

This paper tackles the question of how to learn the transition model up to a prescribed accuracy (in terms of amount of samples). 
In terms of originality, the proposed method combines two established ideas in the RL community, reward-free exploration (in finite horizon MDPs), and exploration in the SSP problem. Therefore, the path to the analysis is quite clear and incremental in nature. Still, the problem at hand is interesting and the solution is natural and clean, so this is not necessarily a flaw. Furthermore, the authors extend the notion of reward free exploration, generalizing it to a wider set of possible tasks.
Thus, overall this paper is significant - as it provides a simple provable methodology to solve many different tasks in the SSP regime.

An interesting question regarding this approach is whether it can be interestingly extended to a case where there are several (sequential/simultaneous) tasks at hand. Indeed, in the finite horizon setting, reward-free exploration is usually analyzed to allow for a "zero-shot" solution of the MDP for any (known) reward function. Yet, in the scenario discussed in this paper, where there are no-resets and the horizon is infinite, it is worthwhile to understand what happens when there is more than one task. Do the authors have any thoughts or comments regarding this question?

Experiments: Can you add the experiment with the original treasure problem? I did not understand the comment about the "burn-in" phase, is there something fundamental here? Is it still problematic when the MDP gets bigger?

Clarity:
I enjoyed reading this paper. It is well written, the main points are well-developed and coherent and the discussions are informative and discuss the related literature properly.


Small typo:
- Lines 204,353 - "Finally,"
limitations_and_societal_impact: Yes.
review_title: null

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper showcases a polynomial sample complexity for the problem of simulating a generative model through online interactions with a communicating MDP. The approach works as follows: It first prescribes the samples to be taken in each state-action pair for a specific objective, and it actively collects these samples by addressing a sequence of SSP problems. The paper includes a numerical validation in illustrative domains.
main_review: This work provides a simple paradigm to translate any generative-model algorithm into a provable efficient online learning procedure, effectively bridging the gap between two fundamental settings of theoretical RL. 
The paper is clean, the approach and the problem are well-motivated, and the related discussion is really thorough. It also includes the analysis of a bunch of relevant objectives that can be targeted with the proposed procedure. Especially, the goal-free and cost-free exploration setting (Sect. 4.3), which generalizes the reward-free exploration framework to infinite-horizon and goal-conditioned RL, might be of independent interest, and a nice direction for future works developing objective-specific approaches.
Overall, I think that this work will provide a strong contribution to the theoretical RL field, and I recommend accepting it.
Some additional comments and questions to the authors can be found below.

SAMPLE COMPLEXITY AND THE LOWER BOUND

The paper reports a lower bound of $\Omega(BD)$ samples for simulating the generative model, and the sample complexity of GOSPRL is upper bounded by $\widetilde{O} (B D + D^{3/2} S^2 A)$. Whereas the authors note that with large sample requirements the term $\widetilde{O} (B D)$ is dominating, I am wondering under which assumptions on b(s, a) the term $\widetilde{O} (S^2 A)$ is unavoidable. Do the authors think that a careful construction might give a lower bound with an explicit dependence on $S^2 A$, which would tie the sampling problem to the one of estimating the transition model for every $(s,a)$ up to a certain confidence?

MODEL-FREE APPROACHES

The GOSPRL algorithm is inherently model-based, as it relies on empirical transitions to instantiate each SSP problem $M_k$, and the analysis is also based on concentrating empirical transitions around the real model. I am wondering if the model-based feature is really a requirement of the nature of the problem or just how the analysis is carried out. Do the authors think that it is possible to address this setting with model-free approaches?

RELATION WITH RF-RL-EXPLORE AND FUTURE DIRECTIONS

From my understanding, the GOSPRL algorithm and RF-RL-EXPLORE [30] are built on similar ideas (in a significantly different context), as they both learn policies to seek for a specific state-action pair in the inner loop. The crucial difference is that RF-RL-EXPLORE solves finite-horizon problems (with EULER) as opposed to SSP problems in GOSPRL.
Subsequent works in reward-free exploration [30, 31, 39, 64] have adopted alternative schema to improve sample complexity upper bounds. Do the authors think that similar routes could be followed for the sample collection problem?
In addition, a direct analysis of the sample complexity that GOSPRL would achieve in the (finite-horizon) reward-free exploration could draw an interesting connection between the two settings.
limitations_and_societal_impact: I think the limitations are well-discussed in the paper and the appendix, which provide details on how to relax the main assumption (communicating MDP) and how to improve the empirical performance of GOSPRL.
review_title: null

Meta-review: This paper was well-received by the reviewers who all agreed that the paper studies an interesting problem and offers a solid solution. There were only minor concerns raised by one reviewer, but these were adequately addressed in the author response. Eventually, the reviewers all agreed that the paper should be accepted for publication at the conference.
Decision: Accept (Spotlight)