Venue: ICLR 2020 Conference

Reviews:

final_score: rating: 3: Weak Reject
review_content: This paper proposes a method, R3L, for exploration in reinforcement learning. R3L performs an exploration procedure before policy optimization. In R3L exploration, it considers the task as a planning problem, and applies RRT to find feasible solutions (trajectories). Then it applies a warm start procedure for policy optimization, where the feasible solutions found by RRT are used to initialize the policy by supervised learning. The paper provides theoretical guarantees of R3L exploration finding feasible solutions. Empirically, the algorithmic contribution is demonstrated by comparing with information theoretical exploration methods in benchmark control domains. 

The paper makes two strong assumptions, which are made to guarantee RRT can be successfully applied in the task. However, it is unlikely that these two assumptions can hold in RL problems we consider in general, where the learning agent only have access to the transition data gathered by interactions with the environment. This makes the proposed R3L algorithm not a general method for exploration in RL. Due to this reason I think this paper should be rejected.

The first assumption is that random states can be uniformly sampled from the MDP state space. The author further argue that sampling a random state is typically equivalent to trivially sampling a hyper-rectangle. But isn't this a domain-dependent property? For example, how to sample a random state in Atari games and decide if it is valid? By the method proposed in the paper, one need to sample a random image, then apply a function to decide if the image is valid in the game. How to get such a function? The second assumption is that the environment state can be set to an arbitrary state. This basically assumes the learning agent is available to the transition function, so that a new state can be added to the current search tree. But again, this assumption might not be appropriate in the general RL framework. 

For the theoretical contribution, the paper shows that RRT is complete with high probability, which is a standard result of RRT. In experiments, R3L is compared with VIME. But is this a fair comparison since R3L assumes to have a generative model? The tested domains are picked such that RRT can be directly applied. Can R3L be applied in domains like mujoco or Atari games? 

The main idea of this paper is to deal with exploration using planning algorithms. But once a generative model of the environment is given, the exploration problem will be very different with the exploration considered in RL. I would like to improve my score if the author can demonstrate the efficiency of R3L with a learned generative model. 

Minor issues:

1. Can you give more details about how pi_l is learned in Algorithm 1? In line 9 an action is generated using pi_l(s_near, s_rand-s_near). But in line 11, the action is again updated by ({s_near, s_rand-s_near}, a), which is very confusing. 

2. The notations for state and valid state are very confusing. In 3.1, the transition and reward functions are defined on S. But later in the paper, S contains states that are not valid. What's the transitions and rewards on invalid states?

review_title: Official Blind Review #4

final_score: rating: 6: Weak Accept
review_content: This paper proposes merging the 'Rapidly-exploring Random Tree' algorithm and RL to inform exploration. I think this is an interesting and novel idea, and the paper is quite well written, although some issues remain.

Firstly, is this algorithm applicable to all RL problems? The assumptions seem quite strong, and furthermore it assumes the existence of a 'goal' state, which is not always the case. I would have liked to see the performance on more challenging domains, like the atari suite, to be fully convinced. I think the question of where and when this algorithm is appropriate needs to be significantly expanded upon.

Furthermore it seems that in a more challenging domain the memory requirements would explode, is that correct? In some sense it seems similar to this paper: https://arxiv.org/abs/1606.04460 which should be discussed.

The name 'Rapidly Randomly-exploring Reinforcement Learning' is a bit jarring since there are no theoretical guarantees about the regret of this approach to indicate that this actually is 'rapid' exploration, at least in the sense that people use it in RL (eg, being efficient with respect to data in the exploration-exploitation tradeoff).

In algorithm 1 there are several confusing aspects:

* I don't understand what is meant by "project srand onto Fg", what is the projection and how is it performed?
* How do you "find nearest node to srand in T"? How is nearness measured? Note that in RL two similar states (eg l2 distance) may be very far apart by many metrics.
* What is "πl(snear, srand − snear)"? How is it parameterized? I see the discussion in the appendix but I think it needs more discussion up front.
* "update π", update how?

Do the theoretical results rely on non trivial measure for the goal states and / or compactness? I'm thinking of an example of a single point (ie measure zero) being the goal state and RRT trying to search for it in a continuous state space, how can it guarantee it will find the measure zero point? It seems the discussion about intuition is lacking here.

I was surprised to see no mention of 'Lévy flights', which seem distinct but related, and appear to provide a similar exploration heuristic in animals. It would be good to add a discussion about the similarities and differences to this.

After SGD I would include a citation to Robbins–Monro, as well as the Leon Bottou one.

In the related work section you should mention the use of Bayesian utility theory to guiding exploration, e.g., https://arxiv.org/abs/1807.09647, also some of part of this recent book draft may be relevant: http://www.cse.chalmers.se/~chrdimi/downloads/book.pdf
review_title: Official Blind Review #1

final_score: rating: 3: Weak Reject
review_content: Reinforcement Learning with Probabilistically Complete Exploration
==========================================================

This paper proposes an exploration technique for planning from simulator.
Roughly speaking, the algorithm uses some initial budget to sample random states and generate some effective demonstration trajectory.
Once this trajectory is found, it can be used to form an initialization for a policy gradient method.
This leads to improved performance on some mujoco tasks.


There are several things to like about this paper:
- The problem of efficient exploration in large-scale RL is a big outstanding hole. Particularly finding methods that are compatible with state of the art policy gradient approaches.
- The proposed algorithm is sensible, and seems to use a reasonable heuristic from planning to generate good "kickstart" for policy gradient methods.
- The general quality of the writing and presentation is pretty good.
- It's great to see code released.

However, there are some places where this paper falls down:
- Assumptions 1 (and particularly 2) are *not* part of the standard RL problem... but actually show that this is a proposal for planning given a simulator. This is a different problem setting and the distinction is really not clear from the first (several) pages. Further, although the assumptions are stated clearly, I think that this leads to some unfair comparisons (even if the sampled states are taken from the X-axis budget in plots).
  - Note that this paper is far from the only one that is a bit sloppy on this distinction... and, of course, you can still use an RL *algorithm* to solve the planning *problem*... but it's not clear you can use a planning algorithm to solve the RL problem... and that's what this paper claims... but then Assumption 2 essentially just reduces the RL problem to the planning problem!
- The claims of "probabilistic completeness" are not particularly insightful, in fact, the same is also true of Q-learning with epsilon-greedy dithering! The point of efficient exploration would be that you find this stuff quickly... and I'm not really convinced that this method always would. The quality of \hat{a}, \hat{b} seems like it should be very important... but I don't get much insight to that spelled out in the paper.
- The computational evaluations are not particularly insightful, in that they seems to not give much insight into exactly what is happening. I also wonder whether they are really "fair" comparisons given the planning vs RL distinction.


Overall, I think that there are interesting pieces to the paper, and the underlying algorithm is also interesting.
For me, the confusion between the planning and RL setting is impossible to move past... particularly since the exploration challenges can be distinct in these domains.
For this reason, I don't think the paper is ready for publication.

review_title: Official Blind Review #2

Meta-review: This was a borderline paper, with both pros and cons.  In the end, it was not considered sufficiently mature to accept in its current form.  The reviewers all criticized the assumptions needed, and lamented the lack of clarity around the distinction between reinforcement learning and planning.  The paper requires a clearer contribution, based on a stronger justification of the approach and weakening of the assumptions.  The submitted comments should be able to help the authors strengthen this work.
Decision: Reject