Balancing exploration and exploitation remains a key challenge in reinforcement learning (RL). State-of-the-art RL algorithms suffer from high sample complexity, particularly in the sparse reward case, where they can do no better than to explore in all directions until the first positive rewards are found. To mitigate this, we propose Rapidly Randomly-exploring Reinforcement Learning (R3L). We formulate exploration as a search problem and leverage widely-used planning algorithms such as Rapidly-exploring Random Tree (RRT) to find initial solutions. These solutions are used as demonstrations to initialize a policy, then refined by a generic RL algorithm, leading to faster and more stable convergence. We provide theoretical guarantees of R3L exploration finding successful solutions, as well as bounds for its sampling complexity. We experimentally demonstrate the method outperforms classic and intrinsic exploration techniques, requiring only a fraction of exploration samples and achieving better asymptotic performance.
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?