Reinforcement Learning with Probabilistically Complete Exploration
Authors: Philippe Morere
Tom Blau
Gilad Francis
Fabio Ramos
Venue:  (2020)
Keywords: Reinforcement Learning
Exploration
sparse rewards
learning from demonstration

Abstract: 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.

Under review as a conference paper at ICLR 2020
REINFORCEMENT LEARNING WITH PROBABILISTICALLY COMPLETE EXPLORATION
Anonymous authors Paper under double-blind review
ABSTRACT
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 explo- ration as a search problem and leverage widely-use planning algorithms such as Rapidly-explories Random Tree (RRT) to find initial solutions. These solutions are used as demonstrations to initialize 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.
INTRODUCTION
Reinforcement Learning (RL) studies how agents can learn a desired behaviour by simply using inter- actions with environment and reinforcement signal. Central to RL is the long-standing problem of balancing exploration and exploitation. Agents must first sufficiently explore the environment to identify high-reward behaviours, before this knowledge long-term rewards. Many recent RL successes have been obtained by relying on well-formed reward signals, that provide rich gradient information to guide policy learning. However, designing such informative rewards is challenging, and rewards are often highly specific to the particular task being solved. Sparse rewards, which carry little or no information besides binary success or failure, are much easier to design. This simplicity comes at cost; most rewards are identical, so that there is little gradient information to guide policy learning. this setting, the sample complexity of simple exploration strategies was shown to grow exponentially with state dimension in some cases (Osband) cct al. 2016b). Intuition behind this phenomenon can be gained by inspecting Figure La exploration in regions where the return surface is flat leads to random walk type search. This inefficient search continues until non-zero gradients are found, which can then be followed to a local optimum.
be exploited and refined maximize
Planning algorithms achieve much better exploration performance than random walk by taking search history into account (Lavalle) 1998). These techniques are also often guaranteed to find a solution in finite time if one exists (Karaman & Frazzoli (011). In order to leverage the advantages of these methods, we formulate RI. exploration as a planning problem in the state space. Solutions found by search algorithms are then used as demonstrations for RL algorithms, initializing them in regions of policy parameter space where the return surface is not flat. Figure [ shows the importance of such good initialization; surface gradients can be followed, which greatly facilitates learning.
This paper brings the following contributions. We first formulate RL exploration as a planning problem. This yields a simple and effective method for automatically generating demonstrations without the need for an external expert, solving the planning problem by adapting the classic Rapidly-exploring Random Tree algorithm (RRT) (Kuffner Valle 2000). The demonstrations are then used to initialize an RL policy, which can be refined with a classic RI method such as TRPO (Schulman et al., 2015). We call the proposed method Rapidly Gandomly-exploriin Reinforcement Learning (R3L provide theoretical guarantees for finding successful solutions
"oode will be made available Githuh.

---

Under review as a conference paper at ICLR 2020
100
-84
100
-94
-96
-96
50
50
1008
-108
50
-50
100
-100
-50
-150
168
200
200
0
2
D
2
0o
0o
(b)
Figure 1: Expected returns achieved by linear policy with parameters Sparse MountainCar domain (background). Gradient is O in the dark blue area. Trajectories show the evolution of policy parameters over 1000 iterations of TRPO, with 5 random seeds. Same colors indicate the same random seeds. (a) Random-walk type behaviour observed when parameters are initialized using Glorot initialization (Glorot & Bengio 2010). (b) Convergence observed when parameters are initialized in a region with gradients (1, 40).
and derive bounds for its sampling complexity. Experimentally, we demonstrate R3L improves exploration and outperforms classic and recent exploration techniques, and requires only fraction of the samples while achieving better asymptotic performance. Lastly, we show that R3L lowers the variance of policy gradient methods such as TRPO, and verify that initializing policies in regions with rich gradient information makes them less sensitive to initial conditions and random seed.
The paper is structured as follows: Section 2 analyzes the limitations of classic RL exploration. Section 3 describes R3L and provides theoretical exploration guarantees. Related work discussed in Section followed by experimental results and comments in Section Finally, Section 6 concludes and gives directions for future work.
2 THARSE-REWARDE RL AS RANDOM WALK
Many recent RL methods are based on a policy gradient optimization scheme. This approach optimizes policy parameters with gradient descent, using a loss function L(Ø) (e.g. expected return) and gradient g = V (()) Since computing L(O) exactly is intractable, it is common to use unbiased empirical estimators ((0) and g()), estimated from samples acquired by executing the policy, Optimization then follows the common stochastic gradient descent (SGD) update-rule (Bottou) 2010 Robbins & Monro 1951) 0.+1 = 0n < (0..). where is the learning rate.
The SGD update rule defines discrete-time time stochastic process (Mandt
2017). Note that is the mean of Tyynh i.i.d. samples. Following the central limit theorem, the distribution over is approximately (() ~ (g((), namb (0)), meaning 9 an unbiased estimator of with covariance C(O). Consequently, the update rule can be rewritten as (Mandt et al. 2017
0n+1 = 0n - -00(
((00))+) + C -BAW, Tymb
AW ~ 1)0,
(I)
Here we assume that C(0) = C.
CC i.e. approximately constant w.r.t. 0, and factorizes C B BB".
SGD is efficient for high-dimensional problems as it offers almost dimension independent convergence rates (Nesterov) 2018). However, SGD requires non-zero gradients to guide the search towards the optimum 0* i.c. (0) > Eg. v0 of 0",, Eg IR. In the case of sparse-reward RL problems, such as in Figure I much of the loss surface is flat. This leads to inefficient exploration of parameter space θ BAW.
as the drift component in Eq. (1 g R 0, turning the SGD to random walk in θ; A0
Random walk is guaranteed to wander to infinity when dimensionality de (Pölya 1921 Kakutani 1944). However, the probability of reaching desired region in θ, e.g. where 7 O. depends
heavily problem specific parameters. The probability of f,,, reaching sphere of radius centered at C such that ||C 0oll R > r (Dvoretzky & Erdōs 1951):
de
Pr[ - CII < r. for some n > 0]
<1,
Vdo 2 3.
(2)
R
2

---

Under review as a conference paper at ICLR 2020
In sparse RL problems R. thus the probability of reaching desired region by random walk is smaller than 1, i.c. there are no guarantees of finding any solution, even in infinite time. This is in stark contrast with the R3L exploration paradigm, discussed in Section 3.3
3 R3L: RAPIDLY AND RANDOMIY-EXPLORIE REINFORCEMENT LEARNING
R3L adapts RRT to the RL setting by formulating exploration as a planning problem in state space. Unlike random walk, RRT encourages uniform coverage of the search space and is probabilistically complete, i.c. guaranteed to find a solution (Kleinbort et al. 2019).
R3L is decomposed into three main steps: (i) exploration is first achieved using RRT to generate data-set of successful trajectories, described in Sections and [.3] (ii) successful trajectories are converted to policy using learning from demonstrations (Section 3.4 and (iii) the policy is refined using classic RI methods.
3.1 DEFINITIONS
This work is based on the Markov Decision Process (MDP) framework, defined as tuple < A, R. y >. S and A are spaces of states and actions respectively. T S Axxxxx - [0, 1] is a transition probability distribution so that [s; at 8(41) = p( 18t, az), where the subscript indi- cates the 4h discrete timestep. R: S A - IR is a reward function defining rewards r, associated with transitions (st, at, (++1)- 7 E [0, 1) is discount factor. Solving a MDP is equivalent to finding the optimal policy x² maximizing the expected return J(xx) = Er (Et= 2 R(st, at St+1)] for some time horizon H, where actions are chosen according to a, ' (st).. Lastly, let S be Eu- clidean space, equipped with the standard Euclidean distance metric with an associated norm denoted by |I-II- The space of valid states is denoted by F. C S.
3.2 EXPLORATION AS A PLANNING PROBLEM WITH RRT
The RRT algorithm (La Valle & Kuffner 200T) provides principled approach for planning in problems that cannot be solved directly (c.g. using inverse kinematics), but where it is possible to sample transitions. RRT builds tree of valid transitions between states in F,, grown from root so- As such, the tree T maintains information over valid trajectories. The exploration problem is defined by the pair 8o). ) In RL environments with a known goal set F C (e.g. MountainCar), the exploration problem is defined by (F,s0, 30, Foout).
The RRT algorithm starts by sampling a random state Syand E S, used to encourage exploration in a specific direction in the current iteration. This necessitates the first of two assumptions.
Assumption 1. Random states can be sampled uniformly from the MDP state space S.
Sampled states are not required to be valid, thus sampling a random state is typically equivalent to trivially sampling hyper-rectangle.
Then, the vertex Sncer = arg min Srand Swear is found. RRT attempts to expand the tree T from Sncor toward Srand by sampling action a A according to steering function T S x S + A. In many planning scenarios, T samples randomly from A. A forward step Snew = (Snearr a) is then simulated from Snear using action a, where f is defined by the transition dynamics. Being able to expand the tree from arbitrary Snear relies on another assumption.
Assumption 2. The environment state can be set previously visited state s E T.
Although this assumption largely limits the algorithm to simulators, it has previously been used in Florensa al. (2017); Nair al. (2018); Ecoffet al. (2019) for example; see discussion in Section 6 on overcoming the limitation to simulated environments.
Snew is added process repeats until a sampling budget is exhausted or the goal set is reached (i.e. Snew E Fgoat).
vertex of T, alongside edge (Snear, Snew) with edge information This
Definition 1. A valid trajectory is a sequence (st, Or S1+1) ) is a valid transition and s, E F, Vt E 10. t, Whenever a goal set is defined, a successfid valid trajectory end state satisfies St, F Fooat-
[So, an .1,...,56,-1 -1, -1, Ge, -1 St,] such that
3

---

Under review as a conference paper at ICLR 2020
Algorithm 1: R3L exploration
Input: 80, k: sampling budget
(optional) F goots Pg- goal sampling proh.
Output: 7: successful trajectory
Add root node So to
00
for
do Srand sample random state Srand E S a ~ UO 1) I Py then
-02
-0.5
Srand + sample 8rand from F goo! end
-0.35
-0.33
-0.23
3.55
0325
3.50
2.75
Snear find nearest node Syand in T + sample गy (Snerr Srand - Snear)
Figure 2: Example R3L exploration on sparse MountainCar. Green segments are sampled transitions, executed in simulation. A successful solution found by R3L is dis- played in red. State dimensions are normal- ized to [-1, 1].
10 Snew execute in state Snear
update Ti with ((Snear; Snew Snear ,a)) Add node Snew: and edge (Snear; Snew)
12
13
end
14
trajectory in T with max. cumulated reward
Once planning is finished, successful valid trajectory easily be generated from T by retrieving all nodes between the leaf Steaf E Foot and the root. Because tree grown from valid transitions between states in F, these trajectories are valid by construction.
3.3 R3L EXPLORATION: ADAPTING RRT RL
RRT is not directly applicable to RL problems. This subsection presents the necessary adaptations to the exploration phase of R3I., summed up in Algorithm Figure shows R3L's typical exploration behaviour.
Local policy learning: In classic planning problems, selecting actions extending Snear towards 8rand is easy, as these have geometric interpretation or there is a known steering function. RL state spaces do not benefit from the same geometrie properties, and properly selecting actions be challenging. We solve this problem by defining a local policy which models the distribution of actions to transition from state to a neighbouring goal state. Actions to extend tree branch are sampled as ~ Xi (Sears Srand - Snear). ). We formulate the problem of learning as supervised learning, where inputs are starting states 8, augmented with the difference 8t+1 8t, and targets are actions. The model is learned using transition data collected from previous tree expansion iterations. Results this paper use Bayesian linear regression to represent m, but any supervised learning model can applied instead.
Unknown dynamics: RRT was designed for problems with known continuous dynamics S. but RL features unknown discrete transition dynamics. In R3L, f is replaced with an environment interaction from Snear, with selected action a, resulting in a new state snew- Since (Snears a, 8new) is a real transition, it must be valid, and &new can be added to the tree T.
Biasing search with Fooat Better exploration efficiency can be achieved if goal information is available. Indeed, the RRT framework allows for biasing exploration towards F Fgout, often resulting in faster exploration. This is achieved by sampling Syand from Fgoal instead of with low probability Pg. while the rest of the iteration remains unchanged.
Since R3L uses RRT to explore, the algorithm is most suitable for RL problems that are fully observable, exhibit sparse rewards and have continuous controls. R3L is applicable other RL problems, but may not perform as well as methods tailored to specific cases.
3.4 POLICY INITIALIZATION FROM R3L DEMONSTRATIONS
Upon completion, R3L exploration yields successful trajectory т, which may not be robust to various starting conditions and/or stochastic transitions. Converting successful trajectories into a policy is crucial to achieve robustness and enable further refinement with RL.
Policy initialization is applied to a set of successful trajectories T = {rrh" generated using N runs of R3I. exploration with different starting conditions. An imitation policy no is learned by supervised
4

---

Under review as a conference paper at ICLR 2020
learning transitions from Policy To is then refined using traditional RL algorithms like TRPO. As shown in Figure !
initializing policy parameters in the vicinity of a local optimum is crucial.
3.5 EXPLORATION GUARANTEES
The RL planning environment defines differential constraints of the form:
á (()()) s(1) F a(l) E A.
Therefore, starting so. the trajectory can be generated by forward integrating Eq. (3) with the applied actions. As with many RL problems, a(t) is time-discretized resulting in a piecewise constant control function. This means constructed of n- segments of fixed time duration At such that the overall trajectory duration f n At. Thus, a(t) is defined as a(t) a, E A where t E [[i 1)- At, At) and S S ny, Furthermore, as all transitions between states are known, the trajectory return can be defined as R Et= 0 7 R(s;, Oz, 81+1).
R3L explores state-action/raaeccoryy space instead of policy parameter space. Furthermore, it an effective exploration framework which provides probabilistic completeness (PC):
Definition 2. A probabilistically complete planner finds a feasible solution (if one exists) with a probability approaching in the limit of infinite samples.
With the aforementioned dynamic characteristics, we prove that R3L exploration under the RL setting is PC, This is in stark contrast to the random walk exploration process, discussed in section 2] which is not PC. We begin with the following theorem, a modification of Theorem from Kleinbort et al. (2019). which is applied to kinodynamic RRT where goal set F gool is defined.
Theorem 1. Suppose that there exists a valid trajectory T from Su to Fyoat as defined in definition 7 with corresponding piecewise constant control. The probability that R3L exploration fails to reach F Fooat from 80 after k iterations is bounded by ae bb for some constants a, 0.
The proof, which is modification of Theorem 2 from Kleinbort et al. (2099), be found in Appendix S2 It should be noted that R3L exploration does not require an explicit definition for Fooa in order to explore the space. While in some path planning variants of RRT, F goat is used to bias sampling, the main purpose of F goot is to indicate that solution has been found. Therefore. Fgoal can be replaced by another implicit success criterion. In the RL setting, this can be replaced by return-related criterion.
Theorem 2. Suppose that there exists a trajectory with return R2 > R. R. R. The probability that R3L exploration to find a valid trajectory from so with R, 2 R after lo iterations is bounded by de bk for some constants à, > O.
Proof. The proof is straightforward We augment each state in with the return reach it from sy:
8n
Vn
Rs
where Re,-- Et 7¹ R(s,, 0t 11+1). For consistency we modify the distance metric by simply adding reward distance metrie. With the above change in notation, modify the goal set to goot = {(s, Rs)ls Fyout, Rs 2 R). such that there is an explicit criterion for minimal return as a goal. Consequently, the exploration problem can be written for the augmented representation as (F, RL FFRli) where RL [so, 0] Theorem satisfies that R3L exploration find a feasible solution to this problem within finite time, i.c. PC, and therefore the probability of not reaching JRL gool
after & iterations is upper-bounded bounded by the exponential term âe for some constants à, b > 0
We now state our main result on the sampling complexity of the exploration process. Theorem 3. If trajectory exploration is probabilistically complete and satisfies an exponential convergence bound, the expected sampling complexity is finite and bounded such that
à
E[K]
(5)
4 4sinh 2
where ā, 0.
5

---

Under review as a conference paper at ICLR 2020
Proof. Theorem provides exponential bound for the probability the planner will fail in finding feasible path. Hence, we can compute a bound for the expected number iterations needed to find a solution, L.c. sampling complexity:
E|K
kãe bk
à
de bk
à d
- d k= db eb -1 4
bb
à
(6)
db
db
where we used the relation
Ex
bk
It is worth noting that while the sample complexity is bounded, the above result implies that its complexity varies according to problem-specific properties, which are encapsulated in the value of à and b. Intuitively, depends on the scale of the problem. It grows as F becomes smaller or as the length the solution trajectory becomes longer. b depends on the probability of sampling
states that will expand the tree in the right direction. It therefore shrinks as the dimensionality of S increases. We refer the reader Appendix S2 for more details the meaning of å, b and the derivation of the tail bound in Theorem
4 RELATED WORK
Exploration in RL has been extensively studied. Classic techniques typically rely adding noise to actions (Mnih et al, 2013 Schulman et al., 2013) or to policy parameters (Plappert et al. 2018). However, these methods perform very poorly settings with sparse rewards.
Intrinsic motivation tackles this problem by defining a new reward to direct exploration. Many intrinsic reward definitions were proposed, based on information theory (Oudeyer & Kaplan 2008)
state visit count (Lopes et al. 2012, Bellemare et al., 2016; Szita & Lörinez 2008 Fox et al. 2018
value function posterior variance (Osband et al., 2016a Morere & Ramos 2018). or model prediction
error (Stadie et al., 2015 Pathak et al. 2017). Methods extending intrinsic motivation to continuous
state and action spaces were recently proposed (Houthooft et al., 2016 Morere Ramos 2018).
However, these approaches are less interpretable and offer no guarantees for the exploration of the state space.
Offering exploration guarantees, Bayesian optimization was adapted to RI. in Wilson al. (2014), to search over the space of policy parameters problems with very few parameters. Recent work extends the method to functional policy representations (Vien et al. 2018), but results are still limited to toy problems and specific policy model classes.
Motion planning in robotics is predominantly addressed with sampling- based methods. This type of approach offers a variety of methodologies for exploration and solution space representation (e.g.. Probabilistic roadmaps (PRM) (Kavraki et al. 1996). Expansive space trees (ESP) (Hsu al. 1997) and Rapidly-
random free (RRT) (Kuffner La Valle, 2000)), which have shown excellent performance in path planning in high-dimensional spaces under dynamic constraints (La &
Kuffner 2001 Hsu et al. 2002 Kavraki et al. 1996).
RL was previously combined with sampling-bass -based planning replace core elements of planning algorithms, such as PRM's point-to-point connection (Faust et al. 2018). local RRT steering func- tion (Chiang et al. 2019) or RRT expansion policy (Chen et al. 2019). In contrast, the proposed method bridges the gap in the opposite direction, employing sampling-bar based planner to generate demonstrations that kick-start RL algorithms and enhance their performance.
Accelerating RL by learning from demonstration was investigated in Nickum et al. (2015) Bojarski al. (2016); Torabi al.) (2018). However, these techniques rely on user-generated demonstra- tions or -priooi knowledge of environment parameters. In contrast, R3L automatically generates demonstrations, with no need an external expert.
5 EXPERIMENTS
In this section, we investigate (i) how learning a local policy Ty and biasing search towards F Fgoot with probability Py affects R3I. exploration, (ii) whether separating exploration from policy refinement

---

Under review as a conference paper at ICLR 2020
Table 1: Impact of learning local policy सy and biasing search towards Fgoot with probability Pg on R3L exploration. Results show the mean and standard deviation of successful trajectory length |r] and number of timesteps required, computed over 20 runs.
Goal hias (f2
0.05)
Unbiased (P2
0) Random Ii
Leamed mq
Random m
Learned m
MountainCar
F7]
81.75 = 6-17
131 23190 17.91
86.75 11.82
139.85 18.79
timesteps
895,65
190.70
4303.80 = 681.60
928,90 + 204.0
4417.55 417.10
Peodulum
[7]
73.10 = 12.86
15.35 = 14.50
67.05 # 15.30
17.90 = 12.62
timesteps
1108.65
2171.95 0571.95-00 381.20
1221.35 +: 216.14
2319.20 249.26
Acrobot
[7]
177.55 + 20.66
163.95 + 19.19
173.5 24.22
169.05 17.07
timestops
15/122.00 + 2621116
12675.20 2652.39
15792.65 65 + 3182.77
13133.55 + 2000.51
Carpple Swingup
[7]
217.35 53.09
319.20 58.78
235.70 70.06
348.35 80.09
timestops
17502.76
13923.82
27186,70 70186,70 = 12246.32
23/156 25 + 16792. 11
3/182 20 # 12031.27
Reacher
[7|
32.70 13.35
22.05 8,81
32.25 12.05
25.30 11.02
timesteps
1445.80 1314.48
838.85
846.94
1423.00 1 1030.07
1034.55 1. 1208.67
is viable and robust methodology in RL, (iii) whether R3L reduces the number of exploration samples needed to find good policies, compared with methods using classic and intrinsic exploration. and (iv) how R3L exploration can reduce the variance associated with policy gradient methods. All experiments make use of the Garage (Duan et al., (016) and Gym (Brockman et al.) (016)) frameworks. The experimental setup features the following tasks with sparse rewards: Caripole Swingup (S C IR ; A C RR, MountainCar (S C IR2,, A C R), Acrobot (S C IR A C IR), Pendulum A C R), Reacher (S C R A S I2?) Fetch Reach (S C 1 A S R2),, and Hand Reach (SC R A C 2.) The exact environment and reward definitions are described in Appendix S3
(S C R²
R3L exploration analysis We first analyze the exploration performance of R3L in limited set of RL environments, to determine the impact that learning policy тı has on exploration speed. We also investigate whether R3L exploration is viable in environments where no goal information is available. Table I shows the results of this analysis. Learning πΙ seems to greatly decrease the number of exploration timesteps needed on most environments. However, it significantly increases the number of timesteps on the acrobot and reacher environments. Results also suggest that learning क helps R3L to find shorter trajectories on the same environments, which is a desirable property in many RL problems. Biasing R3L exploration towards the goal set Fooot helps finding successful trajectories faster, as well as reducing their length. However, R3L exploration without goal bias is still viable in all cases. Although goal information is not given in the classic MDP framework, it is often available in real-world problems and can be easily utilized by R3L. Lastly, successful trajectory lengths have low variance, which suggests R3L finds consistent solutions.
Comparison to classic and intrinsic exploration on RL benchmarks We examine the rates at which R3L learns to solve several RL benchmarks, and compare them with state-of-the-art RL algorithms. Performance is measured in terms of undiscounted returns and aggregated over 10 random seeds, sampled at random for each environment. We focus on domains with sparse rewards, which are notoriously difficult to explore for traditional RL methods. Our experiments focus on the widely-used methods TRPO (Schulman et al. 2015) and DDPG (Lillicrap al.) (015). R3L-TRPO and R3L-DDPG are compared to the baseline algorithms with Gaussian action noise. As an additional baseline we include VIME-TRPE (Houthooft et al. 2016). VIME is an exploration strategy based on maximizing information gain about the agent's 's belief of the environment dynamics. It is included to show that R3L can improve on state-of-the-at exploration methods as well as naive ones, even though the return surface for VIME-TRPP is no longer flat, unlike Figure ! The exact experimental setup is described in Appendix S3.2 The R3L exploration phase is first run to generate training trajectories for all environments. The number of environment interactions during this phase is accounted for in the results, displayed as an offset with a vertical dashed black line. The average performance achieved by these trajectories is also reported as guideline, with the exception of Caripole Swingup where doing so does not make sense. RL is then used to refine policy pretrained with these trajectories.
Figure 3 shows the median and interquartile range for all methods. R3L is very competitive with both vanilla and VIME baselines. It converges faster and achieves higher performance at the end of the experiment. In most cases, the upper quartile for our method begins well above the minimum return, indicating that R3L exploration and pre- pre-training are able to produce successful though not optimal policies. R3L-DDPG performance, for the majority of problems, starts significantly above the minimum return, plunges due to the inherent instability of DDPG, but eventually recovers, indicating that R3L pre-training can help mitigate the instability. It is worth noting that R3L's lower quartile is considerabyy higher than that of baselines. Indeed, for many of the baselines the lower quartile
7

---

Under review as a conference paper at ICLR 2020
MountainCar
Cartpole Swingup
-100
-75
-200
125
Return
-200
-200
-175
-100
4400
0.0
0.5
1.0
7.
10
Timestops (1e6)
Timesteps (1e6)
Timestogs (1c6)
-20
-20
Return
Return
-40
-40
10
-00
10
Timesteps (1e6)
Timesteps (1e6)
Timesteps (1e6)
Fetch
(Zoomed)
-20
-20
R3L-TRPO
R3L-DDPG
DDPG
-40
R3L demonstration
VIME-TRPO
-10
0.0
0.2 0.4 0.6
0.8
1.0
Timestaps [1e6)
Timestaps (1e6)
Figure 3: Results for classic control tasks, comparing our proposed method (R3L-TRPO/DDPG) vanilla TRPO/DDPG, and VIME-TRPO. Trendlines are the medians and shaded areas are the interquartile range, taken over 10 randomly chosen seeds. Also shown the average undiscounted return of successful trajectories generated with R3L exploration. The dashed offset at the start of R3L-TRPO/DDPG reflects the number of timesteps spent on R3L exploration.
takes long time to improve on the minimum return, and in some cases it never manages to do so at all. This is common problem sparse reward RL, where there is no alternative but to search the parameter space randomly until the first successful trajectory is found, explained in Section 2 While a few random seeds will by chance find a successful trajectory quickly (represented by the quickly rising upper quartile). others take long time (represented by the much slower rise of the median and lower quartile). In other words, R31-TRPP/DDPG much more robust to random policy initialization and to the random seed than standard RI. methods. This is because R3L is able to use automatically generated demonstrations to initialize RL policy parameters to a region with informative return gradients.
CONCLUSION
We proposed Rapidly Randomly-exploring Reinforcement Learning (R3L), an exploration paradigm for leveraging planing algorithms to automatically generate successful demonstrations, which can be converted policies then refined by classic RL methods. We provided theoretical guarantees of R3L finding solutions, as well as sampling complexity bounds. Empirical results show that R3L outperforms classic and intrinsic exploration techniques, requiring only a fraction of exploration samples and achieving better asymptotic performance.
As future work, R3I. could extended to real-world problems by leveraging recent advances on bridging the gap between simulation and reality (Peng et al. 2018). Respecting Assumption 2 policy would first be trained on a simulator and then transferred to the real-world. Exploration in high-dimensional tasks is also challenging as stated in Theorem 3 and confirmed experimentally by increased R3L exploration timesteps. Exploiting external prior knowledge and/or the structure of the problem can benefit exploration in nigh-dimensional tasks, and help make R3L practical for problems such as Atari games. Lastly, recent advances in RRT (Chiang et al. 2019) and learning from demonstration Torabi et al. 2018) could also improve R3I.
8

---

Under review as a conference paper at ICLR 2020
REFERENCES
R. Arratia and L. Gordon. Tutorial on large deviations for the binomial distribution. Bulletin of Mathematical Biology, 1989.
M. Bellemare, S. Srinivasan, G. Ostrovski, T. Schaul, D. Saxton, and R. Munos. Unifying count-based exploration and intrinsic motivation, In Advances in Neural Information Processing Systems, 2016.
M. Bojarski, Del Testa, Dworakowski, Firner, Flepp, Goyal, L. D. Jackel, M. Monfort, U. Muller, J. Zhang, X. Zhang. J. Zhao, and K. Ziebaand. End to end learning for self-driving cars.
NIPS Deep Learning Symposium, 2016.
L.N. Bottou. Large-scale machine learning with stochastic gradient descent. In International Conference on Computational Statisties, 2010.
G. Brockman, V. Cheung, L. Pettersson, Schneider, J. Schulman, J. Tang, and W. Zaremba. OpenAI Gym, 2016.
B. Chen, B. Dai, and L. Song. Learning to plan via neural exploration-exploiaaee trees. arXiv:1903.00070, 2019.
H. Lewis Chiang, J. Hsu, M. Fiser, L. Tapia, and A. Faust. RL-RRT: Kinodynamic motion planning via learning reachability estimators from RL policies, Robotics and Automation Letters, 4, 2019.
Y. Duan, X. Chen, R. Houthooft, J. Schulman, and P. Abbeel. Benchmarking deep reinforcement learning for continuous control. In International Conference on Machine Learning, 2016.
A. Dvoretzky and P. Erdös. Some problems on random walk in space. In Proceedings of the Second Berkeley Symposium Mathematical Statistics and Probability, 1951.
A. Ecoffet, Huizinga, Lehman, K. O. Stanley, and J. Clune. Go-explore: a new approach for 2019.
hard-exploration problems.
A. Faust, Oslund, Ramirez, A. Francis, L. Tapia, M. Fiser, and J. Davidson. PRM-RL: Long- range robotic navigation tasks by combining reinforcement learning and sampling-base planning. In International Conference on Robotics and Automation, 2018.
C. Florensa, D. Held, M. Wulfmeier, M. Zhang, and P. Abbeel. Reverse curriculum generation for reinforcement learning. In Conference Robot Learning, 2017.
L. Fox, L. Choshen, and Y. Loewenstein. DORA the explorer: Directed outreaching reinforcement action-selection. In International Conference Learning Representations, 2018.
X. Glorot and Y. Bengio. Understanding the difficulty of training deep feedforward neural networks. In International Conference on Artificial Intelligence and Statistics, 2010.
R. Houthooft, X. Chen, Y. Duan, J. Schulman, F. De Turck, and P. Abbeel. Vime: Variational information maximizing exploration. In Advances in Neural Information Processing Systems, 2016.
D. Hsu, J.C. Latombe, and R. Motwani. Path planning expansive configuration spaces. In International Conference Robotics and Automation, 1997.
D. Hsu, R. Kindel, J.C. Latombe, and Rock. Randomized kinodynamic motion planning with moving obstacles. The International Journal of Robotics Research, 2002.
S. Kakutani. On brownian motions in n-space. Proceedings of the Imperial Academy, 1944.
Karaman and Frazzoli. Sampling based algorithms for optimal motion planning. The Interna- tional Journal of Robotics Research, 2011.
basedd
L. E. Kavraki, P. Svestka, J. C. Latombe, and M. H. Overmars. Probabilistic roadmaps for path planning in dighediimsii configuration spaces. Transactions on Robotics and Automation, 1996.

---

Under review as a conference paper at ICLR 2020
M. Kleinbort, K. Solovey, Z. Littlefield, K. E. Bekris, and D. Halperin. Probabilistic completeness of RRT for geometric and kinodynamic planning with forward propagation. Robotics and Automation Letters, 2019.
J. Kuffner and S. M. VaValee. RRT-connect: An efficient approach to single-query path planning. In International Conference on Robotics and Automation, 2000.
M. Lavalle, Rapidly-exploring random trees: new tool for path planning. Technical report, Department of Computer Science. Iowa State University. 1998.
M. LaValle and J. Kuffner. Randomized kinodynamic planning. The International Journal of Robotics Research, 2001.
T. P. Lillicrap, J. J. Hunt, A. Pritzel, N. Heess, al. Continuous control with deep reinforcement learning, arXiv:1509 Sif.00//990099,,,,, 10997,20111 2015.
M. Lopes, T. Lang, M. Toussaint, and P.Y. Oudeyer. Exploration in model-based reinforcement learning by empirically estimating learning progress. In Advances in Neural Information Processing Systems, 2012.
S. Mandt, M. D. Hoffman, and D. M. Blei. Stochastic gradient descent as approximate bayesian inference. The Journal of Machine Learning Research, 18, 2017.
V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Ried- miller, A. K. Fidjeland, G. Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 2015.
P. Morere and F. Ramos. Bayesian RL for goal-only rewards. In Conference Robot Learning, 2018.
A. Nair, B. McGrew, M. Andrychowicz, W. Zaremba, and P. Abbeel. Overcoming exploration in reinforcement learning with demonstrations. International Conference on Robotics and Automation, 2018
Y. Nesterov. Lectures on Convex Optimization. Springer, 2018.
S. Nickum, S. Osentoski, G. Konidaris, S. Chitta, et al. Learning grounded finite-state representations from unstructured demonstrations. The International Journal of Robotics Research, 34, 2015.
I. Osband, C. Blundell, A. Pritzel, and B. Van Roy. Deep exploration via bootstrapped DQN. In Advances in Neural Information Processing Systems, 2016a.
I. Osband, B. Van Roy, and Wen. Generalization and exploration via randomized value functions. In International Conference on Machine Learning, 2016b.
Y. Oudeyer and Kaplan. How can we define intrinsic motivation? In International Conference on Epigenetic Robotics: Modeling Cognitive Development in Robotic Systems, 2008.
D. Pathak, P. Agrawal, A. A. Efros, and T. Darrell. Curiosity-driven exploration by self-supervised prediction. In International Conference on Machine Learning, 2017.
X. B. Peng, M. Andrychowicz. W. Zaremba, and P. Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In International Conference on Robotics and Automation, 2018.
M. Plappert, R. Houthooft, P. Dhariwal, S. Sidor, R. Y. Chen, X. Chen, T. Asfour, P. Abbeel, and
M. Andrychowicz. Parameter space noise for exploration. In International Conference on Learning Representations, 2018.
G. Pólya. Über eine aufgabe der wahnscheinlichheissecnnuug betreffend die irrfahrt im straBennetz. Mathematische Annalen, 1921.
A. Rahimi and B. Recht. Random features for large-scale kernel machines. Advances in Neural Information Processing Systemx, 2008.
10

---

Under review as a conference paper at ICLR 2020
H. Robbins and S. Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 4:00-407110 1951.
J. Schulman, S. Levine, P. Abbeel, M. Jordan, and P. Moritz. Trust region policy optimization. In International Conference Machine Learning, 2015.
B. Stadie, Levine, and Abbeel. Incentivizing exploration in reinforcement learning with deep predictive models. arXiv: 150.000884 2015.
1. Szita and A. LÓrincz. The many faces of optimism: unifying approach. In International Conference on Machine learning, 2008.
Torabi, G. Warnell, and P. Stone. Behavioral cloning from observation. In International Joint Conference Artificial Intelligence, 2018.
C. Urmson and R. Simmons. Approaches for heuristically biasing RRT growth. In International Conference on Intelligent Robots and Systems, 2003.
N. A. Vien, H. Zimmermann, and M. Toussaint. Bayesian functional optimization. In AAAI Conference on Artificial Intelligence, 2018.
A. Wilson, A. Fern, and P. Tadepalli. Using trajectory data to improve bayesian optimization for reinforcement learning. The Journal of Machine Learning Research, 2014.

---

Under review as a conference paper at ICLR 2020
Reinforcement Learning with Probabilistically Complete Exploration: Supplementary Material
S1
APPENDIX A: RRT ALGORITHM PSUEDO-CODE
In this section, we provide pseudo-code of the classic RRT algorithm.
Algorithm S1: Rapidly-cxploring Random Trees (RRT)
Input:
Sinit
:: sampling budget
Pt: Euler integration time interval
Output: T
T.init(S (Sene)
for i 1: do
Srand + WANDOMMUNIFORMINN
if Srand $ F then
pass
end
Snear <- arg min
8near
/* Find nearest vertex */ /* Sample action
(Snnar Srand)
11
Snew 5 Snear + At. (Snears a)
/* Propagate to new state, Eq. 3 *
12
VALID TRANSITION Snear Snow) then
13
Leadd_vertex(ssss neew
14
T.add lededdddgennrrrrrre Snew)
end
end
S2 APPENDIX B: PROOF THEOREM I
This appendix proves Theorem which shows that planning using RRT under differential constraints is probabilistically complete. The following proof is modification of Theorem 2 from Kleinbort et al. (2019), where completeness of RRT in the RI. setting maintained without the need to explicitly sample duration for every action.
Equation 3 defines the environment's differential constraints. In practice, Eq. (3) is approximated by an Euler integration step. With the interval [0,tr] divided into / >> n.r equal time intervals of duration with 6 1- h. Eq. (3 is then approximated by an Euler integration step, where the transition between consecutive time steps is given by:
Sn+1 Sn f(sn, an)
8x+1 E T,
s.t. 1-00,
lim |n T(n h)ll 0.
(SI)
Furthermore, we define (s) as ball with radius centered at for any given state E S. We assume that the planning environment is Lipschitz continuous in both state and action, constraining the rate of change of Eq. (S.. Formally, there exists two positive constants K,, Ka 0, such that Vsg $1 E F, ag, 01 E :
[lf an) - f(so, a1)l < Kallan -alls [lf ao) f(si, ao)l < K, sill-
(S2)
(S3)
Lemma 1. For two trajectories т, T'. where Su = (0) and s/ = (0) such that ||so sbll - 8 with 6, positive constant. Suppose that for each trajectory piecewise constant action is applied,
so that T(t) = a and (t( d' is fixed during a time period 2 0. Then [[(T) - $
K,T 8, + T K KK,cKKT ||a a'l]

---

Under review as a conference paper at ICLR 2020
The proof for Lemma is given in Lemma 2 of (Kleinbort et al. 2019). Intuitively, this bound is derived from compounding worst-case divergence between T and at every Euler step along T which leads to overall exponential dependence.
Using Lemmale ! we want to provide a lower bound on the probability of choosing an action that will expand the tree successfully. We note that this scenario assumes that actions drawn uniformly When better estimations of the steering function are available, as described 3.3 the performance of RRT significantly improves.
from A, f.e. there is no steering function +
Definition 3. A trajectory T is defined as ô-clear if for òcteor > O, Bi (r(t)) E F for all
E [0, t-].
Lemma 2. Suppose that T is valid trajectory from 7(0) = to T T(+>) gool with duration of i- and clearance of Without loss of generality, we assume that actions are fixed for all t (0,
such that (t) E A.
Suppose that RRT expands the tree from a state s/1 E ((rr-c)((o) to a state goot for any Ks E (0,
and e E (0, kō) we can define the following bound:
nō xō-ekalt (mb-c))
2 Giss
Pr(s gout E (x
Katnehari
[A]
Here, 1is = [B1(-) is the Lebesgue measure for unit circle in S.
Proof. We denote 7' trajectory that starts from & and is expanded with an applied random action
Grand: According to Lemma
((ft))r((tt)) s e (atttKKee."llaaanaane
S e Kat (x6-))) K e Grand l
vt E
[0, t+),
where 6g < nő since s6 E (us-e(So). Now, we want to find ||a arand || such that the distance between the goal points of these trajectories, i.c. in the worst-case scenario, is bounded:
(ntt((6 <) + ty Koe Kate I|a arand|l < kō.
After rearranging this formula, obtain bound for ||a arandll: < Kō e Katr (no t) t, Kakkk
Aa Grand ||
Assuming that Orand drawn out of uniform distribution, the probability of choosing the proper action is
r26 666-e Hatr (nd-c)
Siss
4, Ka
(S4)
A
where (sl' is used to account for the degeneracy in action selection due the dimensionality of S. We note that e (0, kō) guarantees p. 2 0. thus valid probability>
Equation S4 provides a lower bound for the probability of choosing the suitable action. The following lemma provides bound the probability of randomly drawing state that will expand the tree toward the goal.
Lemma 3. Let s E S be a state with clearance i.e. BB(s) F. Suppose that for an RRT tree T there exist a vertex E T such that v E Brays(s). Following the definition in Section 3.2 we
denote Snear E T as the closest vertex to Srand. Then, the probability that Snear E BB(ss) is at least [Bays(s)1/(S),
Proof.
Let Srand Bs)5(s). Therefore the distance between Srand and v is upper-bounded by |Srand w|l < 35/5. If there exists vertex Snear such that Snear # and [|5rand Snear S Brand w|I. then Snear E B25ys (8rana) C Bs(s). Hence, by choosing Srand E Bs)s(s), we are guaranteed Snear E Bs(s). As Srand is drawn uniformly, the probability for Srand E (8)s(s) is (B)/(())
'The function steer S S + A returns an action @steer given two states srand and Snear such that Osteer arg min. Brand (Snear + At f(nnear, a)) a.f. At f8 a) n, for prespecified
7 >
Kaaamaan Frazzoli 2011).
2

---

Under review as a conference paper at ICLR 2020
We prove the main theorem.
Theorem 1. Suppose that there exists valid trajectory from So to F Fgoot as defined in definition with corresponding piecewise constant control. The probability that RRT fails reach Fgout from So after k iterations is bounded by ae-bk, bk ber some constants a, b O.
!
Proof. Lemmal 2 puts bound on the probability to find actions that expand the tree from one state to another in given time. As we assume that a valid trajectory exists, we can assume that the probability defined in Lemma D is non-zero, i.c. > O, hence:
kō - e K. e (nō - c) > O,
(S5)
where we set = 2/5 and 5-2 as was also done in Kleinbort et al., 2019). We additionally require that At, which is typically defined as an RL environment parameter, is chosen accordingly so to ensure that Eq. (S5) holds, i.e. K,At < log K8-E
We cover F with balls of radius 5 min ( gooat Setear), where Boyt [ Foaa-- The balls are spaced equally in time with the center of the 1thh ball in G; = r(at i). Ví = m, where m = t, At. Therefore, Co $o and C. gouul We now examine the probability of RRT propagating along т. Suppose that there exists a vertex v E Bes/s(cs), we need to bound the probability that by taking a random sample Srand, there will be a vertex Snear E (B(es) such that Snew
Lemma 3 provides a lower bound for the probability that Snear E (c(),,, given that there exists provide a lower bound for the probability of R, (((66)))))
vertex E (c)) of (s)/(1)) Lemma] 2
Sis Ath Nyar
choosing an an action from Snear to Snew of p
0, where we have substituted
& with At. Consequently, p 2 (|Ba)s(s)] p)/[S].
For RRT to recover т. the transition between consecutive circles must be repeated m times. This stochastic process be described as binomial distribution, where perform k trials (randomly choosing Srand), with m successes (transition between circles) and a transition success probability
p. The probability mass function of binomial distribution is Pr(X
m) Pr(m; p)
(k) (m) - =)*-m We use the cumulative distribution function (CDF) to represent the upper bound for failure, i.e. the process was unable to perform steps, which can be expressed as:
Pr(X < m)
Σ 2=0
1 P''-1-))*+
(S6)
Using Chernoff's inequality we derive the tail bounds of the CDF when m S p k:
1 (kep m)²
Pr(X < m) S exp
(S7)
2p k
m?
= exp
kp
+ m
(S8)
2
kp
< m tpk
bk
(S9)
In the other case, where < m/k < 1, the upper bound is given by (Arratia & Gordon
1989
Pr(X < m) S exp (-&D m
b (1))
(S10)
where D is the relative entropy such that
D
m
p
m
log
+
(1
m
log
1 m
k
p
k
1
p
3

---

Under review as a conference paper at ICLR 2020
Rearranging D, we can rewrite S10
follows:
Pr(X < m)
exp
m7
log
m
h
m
log
E
(S11)
k:
kp
k
1
p
exp
-m log
m
exp
- -lo
m
E
exp
m log
1 - m
E
(S12)
kpp
1 p
1 p
m(1 p)
1 -
m
exp
m log
exp
kt llo
K
(S13)
Ap(1
p
S exp
>og
(S14)
1 1
0.5
S exp
-k
(S15)
p
S e kp = ae
bk
(S16)
where (S14)
is justified for worst-case scenario where p= = m/k: (115) uses the fact that p < m/k
<
0.5, hence m/k > 0.5. The last step, (S16) is derived from the first term of the Taylor expansion of log
1 = و R²
As and m are fixed and independent of k, we show that the expression for Pr(X < m) decays to zero exponentially with k therefore RRT is probabilistically complete.
It worth noting that as expected the failure probability Pr(X < m) depends on problem-specific properties, which give rise to the values of a and b. Intuitively, a depends on the scale of the problem such as volume of the goal set [ and how complex and long the solution needs to be, as evident Therefore, it is a function of the dimensionality of S (through the probability of sampling Srand) and other environment parameters such as clearance (defined by 5) and dynamics (via K,, Ka), as specified in Eq.
in Eq. (S9) More importantly. b depends on the probability
S3 APPENDIX C: EXPERIMENTAL SETUP
All experiments were run using a single 2.2GHz core and a GeForce GTX 1080 Ti GPU.
$3.1 ENVIRONMENTS
All environments made available in supplementary code. Environments based on Gym (Brock) man et al. 2016), with modified sparse reward functions and state spaces. All environments emit a reward per timestep unless noted otherwise. The environments have been further changed from
Gym as follows:
Cartpole Swingup- The state space S R.1 consists of states s [r, 0, si. O where is
cart position, à is cart linear velacity, 0 is pole angle (measuring from the y-axis) and pole angular velocity. Actions A C R are force applied the cart along the aaaxis. The goal space Fyoot is {s E S cos > 0.9}. Note that reaching the goal space does not terminate episode, but yields a reward of cos O. Time horizon H/ 500. Reaching the bounds of the rail does not cause failure but arrests the linear movement of the cart.
MountainCar- The state space S C IR² consists of states [a:, 6) where is car position and à is car velocity. Actions A C RR are force applied by the car engine. The goal space F Fooat is (s S x 2 0.45). Time horizon H 200.
Acrobot- The state space S C g consists states s = To. 0,, 6.. 0i where co 02 are the
angles of the joints (measuring from the y-axis and from the vector parallel to the st link, respectively) and fg 02 are their angular velocities. Actions AA C R are torque applied on the 2nd joint. The goal space F gooa is {s E S cos 6, cos (0o + 01) > 1.9). In other words, the set of states where the end of the second link is at height > 1.9. Time horizon is H = 500.
4

---

Fetch Reach- A high- nigh-dimensional robotic task where the state space S S R13 con- sists of states s [gripper_pos, ffripeer_pos,fingerrre f'nger_pos, gripper_state finger_ _tnger_state,,o _oal__oo] where gripper_pos. gripper_ve vel are the Cartesian coordinates and velocities of the Fetch robot's gripper, forss,ffnn finger_stture sssttttte finger_te _vel are the two-dimensional position and veloc- ity of the gripper fingers, and goal_pos are the Cartesian coordinates of the goal. Ac- tions A C IR. are relative target positions of the gripper and fingers, which the Mu- JoCo controller will try to achieve. The goal space Fooal is the set of states where the end-effector is within a distance of 0.05 from goal_pas Time horizon H = 50. only sample Under review as a conference paper at ICLR 2020
Pendulum- The state space S S I22 consists of states 8 = - 0 where 0 is the joint angle
(measured from the y-axis) and @ is the joint angular velocity. Actions A S IR are torque applied on the joint. The goal space Fooot is {s E S cos 0.99). Note that reaching the goal space does not terminate an episode, but yields reward of cos 0. Time horizon is 100.
Reacher- The state space S C R consists of states = [ 01 x. y0, 0i] where Oo, O
are the angles of the joints, (zz, y) are the coordinates of the target and 0g 01 are the joint angular velocities. Actions A S IR? are torques applied at the 2 joints. The goal space F goa! is the set of states where the end-effector within a distance of 0.01 from the target. Time horizon is H = 50.
Note that this problem is harder than the original version in OpenAI Gym, goal_pos that are far from the gripper's ' initial position.
Hand Reach- high- tigh-dimensional robotic task where the state space S S 78 consists of states = [joint_ _joint_ps,,, joint foint_vel, fingertip phsippppsspp__ pos,goal, logggoolppsss poo__pos] where joint_poss foant_oosjjoiii joint_veiee are the angles and angular velocities the Shadow hand's 24 joints, fingertip_pes are the Cartesian coordinates of the 5 fingertips, and goal pos the Cartesian coordinates of the goal positions for each fingertip. Actions AA S IR are absolute target angles of the 20 controllable joints, which the MuloCo controller will try achieve. The goal space F Fgoat is the set of states where all fingertips are simultaneously within a distance of 0.02 from their respective goals. Time horizon H 50.
S3.2 EXPERIMENTAL SETUP AND HYPER PARAMETER CHOICES
All experiments feature policy with 2 fully-connected hidden layers of 32 units each with tanh activation, with the exception of Reacher, for which a policy network of fully-connected hidden layers of 128 units each with relu activation is used. For all environments baseline for TRPO.
linear feature
Default values are used for most hyperparameters. A discount factor of 0.99 is used in all environments. For VIME, hyperparameters values reported in the original paper are used, and the implementation published by the authors was used.
For TRPO, default hyperparameter values and implementation from Garage are used: KL divergence constraint 5 10-2, and Gaussian action noise (0, 0.3²).
In comparisons with VIME-TRPO and vanilla TRPO, the R3L goal sampling probability Py is set to 0.05, proposed in Urmson & Simmons (2003). Goal sets Fgout defined in Appendix [S3. for each environment. In all experiments, the local policy क. learned during R3L exploration uses Bayesian linear regression with prior precision 0.1 and noise precision 1.0, well 300 random Fourier features (Rahimi & Recht 2008) approximating a square exponential kernel with lengthscale 0.3.
5


Reviews:
[{"review_id": "ryx7EiaBKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Reinforcement Learning with Probabilistically Complete Exploration\n==========================================================\n\nThis paper proposes an exploration technique for planning from simulator.\nRoughly speaking, the algorithm uses some initial budget to sample random states and generate some effective demonstration trajectory.\nOnce this trajectory is found, it can be used to form an initialization for a policy gradient method.\nThis leads to improved performance on some mujoco tasks.\n\n\nThere are several things to like about this paper:\n- 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.\n- The proposed algorithm is sensible, and seems to use a reasonable heuristic from planning to generate good \"kickstart\" for policy gradient methods.\n- The general quality of the writing and presentation is pretty good.\n- It's great to see code released.\n\nHowever, there are some places where this paper falls down:\n- 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).\n  - 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!\n- 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.\n- 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.\n\n\nOverall, I think that there are interesting pieces to the paper, and the underlying algorithm is also interesting.\nFor 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.\nFor this reason, I don't think the paper is ready for publication.\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "S1gNfBxuqB", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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. \n\nThe 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.\n\nThe 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. \n\nFor 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? \n\nThe 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. \n\nMinor issues:\n\n1. 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. \n\n2. 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?\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "H1gMivLjKB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nFirstly, 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.\n\nFurthermore 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.\n\nThe 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).\n\nIn algorithm 1 there are several confusing aspects:\n\n* I don't understand what is meant by \"project srand onto Fg\", what is the projection and how is it performed?\n* 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.\n* 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.\n* \"update π\", update how?\n\nDo 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.\n\nI 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.\n\nAfter SGD I would include a citation to Robbins–Monro, as well as the Leon Bottou one.\n\nIn 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", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

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