Regioned Episodic Reinforcement Learning
Authors: Jiarui Jin
Cong Chen
Ming Zhou
Weinan Zhang
Rasool Fakoor
David Wipf
Yong Yu
Jun Wang
Alex Smola
Venue:  (2021)
Keywords: Deep Reinforcement Learning
Episodic Memory
Sample Efficiency

Abstract: Goal-oriented reinforcement learning algorithms are often good at exploration, not exploitation, while episodic algorithms excel at exploitation, not exploration. As a result, neither of these approaches alone can lead to a sample efficient algorithm in complex environments with high dimensional state space and delayed rewards. Motivated by these observations and shortcomings, in this paper, we introduce Regioned Episodic Reinforcement Learning (RERL) that combines the episodic and goal-oriented learning strengths and leads to a more sample efficient and ef- fective algorithm. RERL achieves this by decomposing the space into several sub-space regions and constructing regions that lead to more effective exploration and high values trajectories. Extensive experiments on various benchmark tasks show that RERL outperforms existing methods in terms of sample efficiency and final rewards.

Under review as a conference paper at ICLR 2021
REGIONED EPISODIC REINFORCEMENT LEARNING
Anonymous authors Paper under double-bling review
ABSTRACT
Goal-oriented reinforcement learning algorithms are often good at exploration, not exploitation, while episodic algorithms excel at exploitation, not exploration. As a result, neither of these approaches alone can lead to sample-efficient algorithm in complex environments with high dimensional state space and delayed rewards. Motivated by these observations and shortcomings, in this paper, we introduce Regioned Episodic Reinforcement Learning (RERL. that combines the episodic and goal-oriented learning strengths and leads to a more sample efficient and ef- fective algorithm. RERL achieves this by decomposing the space into several sub-space regions and constructing regions that lead to more effective exploration and high values trajectories. Extensive experiments on various benehmark tasks show that RERL outperforms existing methods in terms of sample efficiency and final rewards.
INTRODUCTION
Despite its notable success, the application of reinforcement learning (RL) still suffers from sam- ple efficiency real-world applications. To achieve human-level performance, episodic RL (Pritzel et al. 2017 Lee et al. 2019) is proposed to construct episodic memory, enabling the agent to as- similate new experiences and act upon them rapidly. While episodic algorithms work well for tasks where it is easy to collect valuable trajectories and easy to design dense reward functions, both of these requirements become roadblocks when applying to complex environments with sparse reward. Goal-oriented RL (Andrychowicz et al. 2017 Paul et al. 2019) decomposes the task into several goal-conditioned tasks, where the intrinsic reward is defined as the success probability of reaching each goal by the current policy and the ability to guide the agent to finally reach the target state. These methods intend to explore more unique trajectories and use all trajectories the training pro- cedure, which may involve unrelated ones and result in inefficient exploitation. In this paper, propose a novel framework that can combine the strengths of episodic and goal-oriented algorithms and thus can efficiently explore and rapidly exploit high-value trajectories.
The inefficient learning of deep RL has several plausible explanations. In this work, focus addressing these challenges: (C1) Environments with a sparse reward signal can be difficult to learn, as there may be very few instances where the reward is non-zero. Goal-oriented RL can mitigate this issue by building intrinsic reward signals (Ren et al. 2019), but suffer from the difficulty of gener- ating appropriate goals from sigh-dimessional space. (C2) Training gral-oriented RL models using all historical trajectories rather than selected ones would involve unrelated trajectories in training. The training process of goal generation algorithms could be unstable and inefficient (Kumar et al.) 2019). as data distribution shifts when the goal changes. It can be fairly efficient if updates happen only with highly related trajectories. (C3) Redundant exploration performance as it is inefficient for the agent to explore the same areas repeatedly (Ostrovski et al. 2017). Instead, would be much more sensible for agents to learn to divide the task into several sub-tasks avoid redundant exploration.
another issue that limits the
In this paper, we propose Regioned Episodic Reinforcement Learning (RERL), which tackles the limitations of deep RL listed above and demonstrates dramatic improvements in a wide range of envirouments. Our work is, in part, inspired by studies on psychology and cognitive neuroscience (Lengyel & Dayan 2008 Manns et al.) 22003), which discovers that when we observe an event, we scan through our corresponding memory storing this kind of events and seek experiences related to

---

Under review as a conference paper at ICLR 2021
this one. Our agent regionalizes the historical trajectories into several region- bason- memories At each timestep, the region controller will evaluate each region and select one for further exploration and exploitation. Each memory binds specific goal and series of goal-oriented trajectories and uses a value-based look-up to retrieve highly related and high-quality trajectories when updating the value function. We adopt hindsight (i.e., the goal state is always generated from visited states in the memory) and diversity (i.e., goal state should be distant from previous goal states in other mem- ories) constraints in goal generation for goal reachability and agent exploration. This architecture conveys several benefits: (1) We can automatically construct region-based memory by goal-ori goal-oriented exploration, where trajectories guided by the same goal share one memory (see Section [.1]. (2)
Within each memory, we alleviate the high-dimensional issue (C1) by enforcing that the goal space a set of visited states (see Section 3.2). (3) order to improve efficiency in exploitation (C2), our architecture stabilizes training using trajectories within the memory instead of randomly selected transitions (see Section 3.3 for details). (4) Our algorithm takes previous goals in other memories when generating goal in current memory. Specifically, propose the diversity constraint to en- courage the agent to explore unknown states (see Section 3.2, which aims at improving exploration efficiency (C3).
The contributions of this paper are as follows: (1) We introduce RERL, novel framework that combines the strengths of episodic RL and goal-oriented RL for efficient exploration and exploita- tion. (2) We propose hindsight and diversity constraints in goal generation, which allows the agents to construct and update the regioned memories automatically. (3) We evaluate RERL in challeng- ing robotic environments and show that our method can naturally handle sparse reward environ- ments without any additional prior knowledge and manually modified reward function. RERL can be closely incorporated with various policy networks such as deep deterministic policy gradient (DDPG (Lillicrap et al. 2015) and proximal policy optimization (PPO (Schulman et al., (017 Further, ablation studies demonstrate that our exploration strategy is robust across a wide set of hyper-parameters.
PRELIMINARIES
In RL (Sutton& & Barto 2018), the goal of an agent is to maximize its expected cumulative reward by interacting with given environment. The RL problem can be formulated
Markov Decision Process (MDP) by a tuple (S,A, rP,r,7), 7). where S is the state space, A is the action space, P : S x A + A(S) is the state transition probability distribution, r S A + [0, 1] the reward function, and 7 E [0, 1) is the discount factor for future rewards. Our objective is to find a stochastic policy S A - [0, 1) that maximizes the expected cumulative reward R, E >*r4+* within the MDP, where T is the episode length. In the finite-horizon setting, the state-action value function Q3 (s, TE| [s 8, a) is the expected return for executing action a state s and following श afterward. The value function can be defined as
(T((s) = E En (rrnaa |tt = s,
Vs S,
(1)
where T is the episode length and the goal of the agent is to maximize the expected return of each state s, Deep Q Network (DQN, (Mnih et al. 2015)) utilizes an off- off-policy learning strategy, which samples (st, dz, T2,, 1)) tuples from a replay buffer for training. It is a typical parametric RL method and suffers from sample inefficiency due slow gradient-based updates. The key idea of episodic RL is to store good past experiences in a tabular- non non- parametric memory and rapidly latch onto past successful policies when encountering similar states, instead of waiting for many optimization steps. However, in environments with sparse rewards, there may be very few instances where the reward is non-zero, making it difficult for an agent to find good past experiences. In order to address this issue, goal-oriented RL is proposed. In the goal-conditioned setting that we use here, the policy and the reward are also conditioned on a goal g E G (Schaul et al. 2015). The distance function d (used to define goal completion and generate sparse reward upon the completion of goal) may be exposed as a shaped intrinsic reward without any additional domain knowledge: r(st, arlg) 1, if d(((- g) I 8, and r(s,, ag ag)g) -d(o(-|s(+))
otherwise, where ø
'The common idea our method shares with neuroscience is utilizing highly related information to promote learning efficiency. The difference is that memories are regioned according to the generated goals in this paper, and fictions in cognitive neuroscience.
2

---

Under review as a conference paper at ICLR 2021
Region Region-based Memory
Algorithm Framework of RERI.
Trajectory t
1:
repeat
Exploration
Exploitation
State 5
2: Select Region together with Region-based
Memory.
[ ..
Environment
Generate goals for exploration with Goal- oriented RL.
Goal Generator
Policy Network
Action
4:
Interact with the Environment.
5:
Store historical trajectories into Memory. Update value estimation for exploitation with Episodic RL.
Goal 8.8
6:
Figure 1: An illustration of RERL where we propose region-based memory for efficient exploration and exploitation.
7:
until Q function Converges.
S - G known and tractable mapping[] While we expect that cooperation of goal generation and distance function themselves to lead the agent to the final state (global optimum), in practice, we need consider that there exist local optima due state space structure or transition dynamics Trott et al. 2019). Once we can generate appropriate goal g and anti-goal 9. we are able to redefine intrinsic reward function as:
d(o((1544).9) 8
(88t, Ge () = min - (a000,,-(((11)) d((((184+2)99) + d((((18441).)))
(2)
otherwise,
where 8t41 ~ St. at) denotes the next state; Φ S + G is the extended joint generation for both goal and anti-goal generations: 9 E G is the anti-goal and acts as a state that the agent should avoid, which prevents the policy from getting stuck at the local optimum and enables the agent to learn to reach the goal location quickly: Trott et 2019 6 given threshold indicating whether the goal is considered to be reached (Plappert et al. 2018 To make use of r(st, 4t 0z1g,9) in practice, we require method to dynamically estimate the local optima that frustrate learning without relying on domain-expertiss or hand-picked estimations.
The idea of the universal value function (Schaul et al. 2015) is to use universal functional ap- proximator to represent large number of value functions. In the goal-oriented scenario, the value function conditioned any given goal of g and anti-goal ğ can be defined
T
V (= ==
C'r Σ
Let X' (x x x= (8. denote the joint set over state and goal spaces. Specifically, we define r* X' over initial state 8p S. initial goal g" E and initial anti-goal g" E G. At the start of every goal-oriented task (Plappert et al. 2018), an initial-terminal states pair will be drawn from the task distribution. In this paper, we regard the terminal state as the original goal g" and set the original anti-goal ğ" the initial state to encourage the agent to explore at the beginning. In this setting, the agent tries to find policy т that maximizes the expectation of discounted cumulative reward V (a=). From the comparison of Eqs. 11) and (3), one see that the critical points for goal-oriented RI. are to generate appropriate goals. However, as stated in (Ren et al. 2019), in goal- oriented RI,, the value function V (xr) is optimized with respect shifting goal-conditioned task distribution, which makes learning unstable. This issue requires RL algorithms to rapidly obtain value estimation under current goal-conditioned tasks, which the strength of episodic RL. For convenience, we replace all (s, 9, tuples with in the following context.
REGIONED EPISODIC REINFORCEMENT LEARNING
'The definition of 6 depends on the definitions state and goal, and varys when encountering the different environments (Ren et al. 2019). For example, the goal only indicates the designated position of the destination in the Ant Maze environment (see Figure(4(h).. thus, the mapping is defined as mapping from system state the position of the destination in this case.
3

---

Under review as a conference paper at ICLR 2021
condicond value
The basic idea behind this paper is to 'divide-and- conquer exploration and exploitation problems in RL. Firstly, we adopt goal-oriented RL to 'divide' the state space into several regions, where a specific goal identifies each region. We then utilize episodic RL to "conquer', where we store and learn from highly related and high-quality trajectories in region- based memories. The overall framework is called Region Episodic Reinforcement Learning (RERL).
Goal Generator
automatically generate region vid goal generation
Region-based Memory
goal-conditioned trajectories
Figure 2: An illustration for motivation.
We provide the overall algorithm in Algorithm Tand illustration in Figure I which combines the strengths of goal-oriented RL and episodic RL to per- form efficient exploration (illustrated as orange part in Figure and exploitation (illustrated as blue part in Figure 2) In the following section, we first introduce the definition of regions together with region- basoon memories in Section 3.1 In order to automatically obtain regions during exploration, generate appropriate goals to guide the agent under hindsight and diversity constraints in Sec- tion 3.2 Since the goal of any RL agent is to learn a policy that can maximize the expected return, show the value estimation update formulation based region- regien-basedd memory in Section
3.1 CONSTRUCT REGION-BASED MEMORY
Following (Florensa et al., 2017), many previous goal-oriented RL works (Ren al. 2019 Asadi
ct al. 2018) adopt Assumption to guarantees continuous goal-space representation.
Assumption 1. value function (x) has Lipschitz continuity over goal g and anti-goal g. which can be formulated as
V=)))) L. d(x,xx),
(4)
where L denotes the Lipschitz constant. Considering that this Lipschitz continuity may not hold for every x E X. we partition the joint set X into several subsets. If d(z x²) is not too large within each sub-set, generally speaking, it is reasonable to claim that the bound Eq. (4) holds for most scenarios. In this paper, we define these sub-spaces regions. We formulate the definition follows:
Definition 1. Considering that X' satisfies X' = U. X, and X, N = 0, Vi.j = 1,2, N and # j. we define each subset X, as a region, where N the number of regions.
An ideal partition strategy should divide state space into several parts, and each part leads one meaningful goal (e.g., in the case of exploring a large house, ideal partition strategy should divide the house into separated rooms). RI. algorithms explore each par- tition while ignoring other state space, thus significantly reducing exploration complexity. However, one should note that it is imprac- tical to find the perfect partition strategy without any aask-specific manual engineering. One possible solution to automatically gener- ate these regions is to bind each region with a series of goals. In other words, we can design a region-based goal generation where at each timestep, we pick up one region and update the goal within the region. This architecture conveys several advantages: (1) al- lows the agent to solve complex environment through 'divide-and- conquer'. (2) Goal generation is modified within a sub-space, which can improve the stability.
Region Controller
Region 1
Region 2
Key
Value
Key Kry Ney
Ney Key
Value
Memory
Memory
Figure 3: An illustration for region-based memory.
In order to achieve this, we construct region-based memories based on historical trajectories. Specifically, for each region-based memory Mn.wwe have simple memory module M,
(x),,, V (x)), where x E Xn. K(x) = (d(-)s), 9.)99) g) is the key of the memory and (xx) is the value of the memory. As shown in Figure g each memory binds specific region. At each episode, the region controller selects the region-based memory containing the highest value state for further exploration and exploitation. The motivation behind this is very intuitive that the agent always focuses on the region with the highest potential. However, directly adopting this greedy operation may lead to the phenomena of rich-get-richer (Salganik et al. 2006). Instead, we adopt
Different from traditional divide-and-conquee algorithms, we 'divide and conquer' the problem with only one round of problem division instead of using a recursive way.
4

---

Under review as a conference paper at ICLR 2021
Boltzmann softmax to select region Xn, We use X, to denote division of joint set X, which is conceptual and not accessible. In the practice, we use the trajectories stored in M, instead.
Selected-M, exp(maxme.M Vm/1t
(5)
exp(maxmEM, Vm/t)
where denotes the temperature hyper-paramese to control the exploration rate, Vn is the value of the sampled memory m, and N is the number of regions. In practice, we set the initial temperature at 1.0, then gradually reduce the temperature 0.01 to limit region level exploration. After selecting a region X,, the agent will focus on performing efficient exploration and exploitation upon the historical experience in its associated memory M,, We here prove that the value optimization problem in region-based setting is a relaxed lower bound for the original one through Proposition]]
Proposition 1. Given the joint sel X' and several region-based sets (i.e. sub-sets) Xm, where nt 1,2,..., N and N is the number of regions, we have
VT, max V (x) x
max
(*)),, where In = arg max V* (In). EnEA,
(6)
2E(,).22..,.2
Proof.
The proof of Proposition provided in Appendix C.I
3.2 EXPLORE WITH GOAL-ORIENTED REINFORCEMENT LEARNING
In this section, we aim to find uppropriate goals for exploration. In this paper, we analyze that ap- propriate goals should have the following three properties, namely (1) high value (close to terminal state), (2) reachability (appropriate for current policy), and (3) exploratory potential (explore unvis- ited states). To this end, we search for vilue states, according to Eq. (3). under hindsight and diversity constraints. Based on Assumption I.
we can easily derive that
VIn E Nu E Xn, V" (²(,") L. d(zn,
Jointly considering Eqs. 9 and optimizing cumulative rewards in Eq. can relaxed into the following surrogate problem:
max T, (1r1 #y
V (*x), where vn arg max (Z.) -d-Ln E.,,
1,2, N, (8)
Note that this new objective function is intuitive. Instead of directly optimizing with xr, which is likely to be hard, we hope to find a collection of surrogate sets x E X, which benefit the exploration, ease the optimization, and are close to or converge towards x². However, stated in (Ren et al., 2019). the joint optimization of π and x is non-trivial due to high- high-ddmeesiioal observation and shifting distribution during optimization. In order to find appropriate states for goal generation and make the system stable, we then introduce two constraints, namely hindsight constraint for reachability and diversity constraint for exploratory potential.
Hindsight Constraint. In order to guarantec goal reachability and improve learning stability, adopt the idea hindsight goals (Andrychowicz et al. 2017), which means g C S. We first enforce X' finite set of Z particles that only be from those already achieved states from trajectories {r} in the current memory Mr. which means that the support of X' should be base on Mn,
Deep Q Network (DQN, (Mnih et al. 2015)) parameterizes the action-valee function by deep neural networks (s a) using Q-learning Watkins & Dayan 1992) learn which action is the best to take at the timestep I. According to Eq. (8), one can see that we are aiming to find high-value states with similar goal-conditioned tasks. Based the components of region-based memories, we rank
and select top-Z trajectories {Tr) where T2 { corresponding to goal-oriented task 2g, to maximize D w(x2, Tz), where w(22, Ts) is defined
(10((1s2)) - 9"'l v((()))
1 [
w(Ie, == a d(zz, x²) min REE..
(9)
where the first term is to measure the goal-conditioned task similarity with the key in the memory, and the second term is to select high-value states, and a is the hyperparameter to balance these two terms.
5

---

Under review as a conference paper at ICLR 2021
Diversity Constraint. In order to encourage the agent to explore unvisited states and avoid the overlapping among the regions, we adopt the diversity constraint in goal generation. Then, we can re-formulate Eq. (9
(1((1s)) 5²ll (*
11 B
w(F2, T2) = - d(z,, x²) + min
Σ (1lo(-18)) g JE
(10)
where 3 adjusts the weight of the diversity constraint, and -n denotes the set of index except n. The motivation behind this is that considering that goals in goal-oriented RL indicate the direction for exploration, the generated goal is expected to be different from historical goals in other regions. Therefore, the formulation of our goal generation can be easily derived from Eq. (TO), which can be formulated as
9 = . min | E
(in((l((1s))))) - 5"1l V (,T
11 (1'((1)))) 3N JE-n
(1I)
where is obtained through maximizing Σ w(22; T2). where w(x2, T=) is defined according to Eq. (1O). For the anti-goat generation, we directly assign the visited state with the average value in the region the anti-goal. The original motivation for the anti-goal setting avoid local optima, which and can be further described as reward shaping technique (Trott et al. 2019). An illustrated
example the goal generation is shown Appendix B.1
3.3 EXPLOIT WITH EPISODIC REINFORCEMENT LEARNING
Similar to previous episodic RL algorithms (Lin et al. 2018 Zhu et. 2019), we adopt region-based memories to maintain the historically highest values (((x, for each joint state-goal distribution and
action pair. When encountering a new state, the agent will look up and update the corresponding memory according the following equation:
max (V* (I+)), Rt),, if xe satisfies (x( MM.
V V=(x,)
(12)
Re.
otherwise
When the goal is changing (g - g¹), the agent is required to conduct goal relabeling, similar to (Andrychowicz al., 2017). That is, the agent needs to firstly update the key (K(x) + K K(x'), then re-calculate the reward (R, + R2) and update the value according to Eq. (12). Note that RERL enables the agent to rapidly assimilate new experiences improve sample efficiency by looking up the region-based memory. Furthermore, slowly changing goal-conditioned tasks guarantees stability by restricting goal updating within each region. Based on the up-to-date region-basee memories, algorithm be adapted to various RL training algorithms. We give proof of convergence in Appendix C.2 our algorithm can converge to a unique optimal point when using Q-learning for value learning.
Overall Algorithm. We provide the overall algorithm in Algorithm in Appendix 2 We also pro- vide some other views, including curriculum learning and maximum entropy reinforcement learning, to better understand how RERL works. Please refer to Appendix B.2 and B.3 for details.
EXPERIMENTS
In this section, we perform an experimental evaluation of the proposed method of learning from trajectories and compare it with other state-of-the-and art methods. We also perform an ablation study
Irioastic
(a) Free Ant Locomotion
(b) Maze Ant Locomotion
(c) Multi-Path Point Mass
(d) N-dimension Point Mass
Figure& 4: In (a)-(c), the red areas are goals reachable by the orange agent. In (d) any point within the blue frame is feasible goal (purple balls) and the rest are unfeasible (black triangles).

---

Under review as a conference paper at ICLR 2021
(a) Free Ant Locomotion
(b) Maze And Locomotion
Path Point Mass
nomalled qptade aNCINA SCTLII
2.0
RCAL-FPO
HGG ponn
SaRAC
6.8
0.0
Skwino
TEPG
m
S6-PTO
0.6
0.4
0.2
0.0
25
50
100
125
5K
25K
50K
75K
100K
125k
100
125
Rerraiin
Lecation
(d) 3 dimension Point Mass
(c) Comparison with Curricalam Learning
(3) A.Alattion Study
1.0
1.0
0.5
nommalas www.ede.eeeooooooooooo.ooooo Avergee
0.8
0.5
0.5
0.5
0.4
0.4
0.
0.2
0.0
30
75
100
125
5K
25K
50K
75K
100K
123K
5K
23K
50K
73K
100K
125K
Feraaion
(heration
Femntion
(g) Hypee-parameter L
(h) Hyper-pararmeter N
Pong
20mma Tomdaloodeee wpw.odde--ee..... avermgg returr
Ritm
1.0
epocdd arenuge
0-2
Me500
0.8
0.6
normaloee cpicode
0.4
Sealt
0.2
0.2
XEEL- MoGsal
INDon
0.0
0.0
0.0
125K
2000K
S0O0K
Benstion
Serstion
Figure 5: Learning curves of RERL, HGG, HER, SR, AutoGG, EMDQN and POINT on various environments, where the solid curves depict the mean, the shaded areas indicate the standard devia- tion, and dashed horizontal lines show the asymptotic performance. Several curves are omitted due to page limitations. A full version is deferred Appendix E.1
of different settings of our framework. In this section, we provide the experimental results to answer the following questions:
Can our RERL approach obtain better convergence in various environments?
2. Can our goal generation enhance the RL method to achieve asymptotic performance with higher efficiency?
3. Can our RERL tackle complex multi-path goal distribution?
4. Can our RERL scale to higher-dimensional goal-spaces?
5. Do generated goals really encourage exploration?
To answer the first two questions, demonstrate method in two challenging robotic locomotion tasks (see Figure5(a))b) (b)). To answer the third question, we train an ant agent to reach any position within multi-path maze (see Figure ())). To answer the fourth question, method performs with the dimension of goal-space an environment (see Figure d) for the 3D case). To answer the final question, conduct visualization study (see Figure (6 on generated goals. Specifically, we conduct extensive experiments with existing approaches:
investigate how
HER: AAnrychowicc et al. (017)) introduced Hindsight Experience Replay which constructs
imaginary goals simple heuristic way tackle the sparse reward issue.
HGG: Ren et al. (2019) proposed a Hindsight Goal Generation incorporating with DDPG Gilli
crap et al. 2015) that generates valuable hindsight goals to guide the agent.
AutoGG: Florensa et al. (2017) leveraged Least-Squares GAN (Mao et al. 2018) to mimic the
set of Goals of Intermediate Difficulty as an automatic goal generator.
SR: Trott et al. (2019) proposed novel framework named Sibling Rivalry accompanied by PPO
Schulman et al. (0017) for learning from sibling trajectories with self-balancing reward.
POINT:
Finnaa Jinnai et al. (2019) proposed to extend covering options to large state spaces, automati- cally discovering task -ggoosii options that encourage exploration.
EMDQN: Lin et al. (2018) leverages episodic memory supervise agent during training.
Note that RERL can be closely incorporated with policy networks such A2C (Mnih al. 2016),
DDPG (Liliirapp et al. 2015), TRPO (Schulman et al. 2013). PPO (Schulman et al.) 2017). Soft-
AC (Haamoja al. 2018), etc. The detailed description of experiment settings and implementation

---

Under review as a conference paper at ICLR 2021
details can be found in Appendix D.1 and D.3 In this paper, implement HGG+DDPG and SR+PPO, as initially proposed.
Ant Locomotion. We test RERL two challenging environments a complex robotic agent navigating either free space (Free Ant, Figure. 4 a)) or U-shaped maze (Maze Ant, Figure. 4b). Duan et al. (2016) described the task of trying to reach the other end of the U-turn, and they show that standard RL methods
unable to solve it. We further extend the task evaluate whether the agent able to reach any given position (c-balls depicted in red) within the maze for Maze Ant or within the target square for Free Ant. As showed in Figure Figure5)a))b aa))),, the performance of our approach exceeds that of the baselines above.
Multi-Path Point-Mass Maze. We show that RERL is efficient at tracking clearly multi-path dis- tributions of goals. To this end, we introduce a maze environment with multiple paths, as illustrated in Figure[ic) As in the experiment above, our task is to learn a policy that can reach any feasible center of the mass (z. y) corresponding e-balls in state space, like the one depicted red. As shown in Figure our approach obtains better performance even in multi-pat path environment where goal distribution is naturally more complex than previous environments (see Appendix F.2 for demonstration).
N N-dimensional Point-Mass Maze. We use an N N-dimensional Point-Mass to demonstrate the per- formance of our method as the state space dimension increases. As shown Figure d(d), our approach outperforms strong baselines in the high-dimensional experiment.
Atari Game Pong We evaluate RERL in Atari Game, where several episodic RL algorithms (Ba- dia al. 2020; Lin et al., 2018) have achieved good performance. In the previous goal-oriented environments such as Maze, both state and goal have physical meaning (e.g., location in the maze). Therefore, it is easy for us to define the distance between two states, which denotes the physical distance in the maze. However, in the Atari Game environment, both state and goal are the image. Hence, the distance here has no physical meaning, which implies that directly attending the goal- oriented setting will result in bad performance. In order to verify the analysis above. directly the extrinsic reward from environment (denoted as RERL=+POO+NGGoa) and then gradually (i.e., 5%, 20%, 50%) add the intrinsic reward in the reward function (denoted RERL PERL+PPO+Goal5,, ERL+PPO+Goa120, ERL+PPO+Goal50, respectively). We present the result in Figure 5ii). Results show that the goal-oriented setting of RERL is suitable for the environment like Atari Game Also, in the Atari Game environment, there are less sparse rewards than the Ant Maze environ- ment. Therefore, simple episodic RL algorithm such as EMDQN can obtain better performance than RERL.
More experimental results of environments above can be found in Appendix E.
state
anti-goal
goal
normalized episode average
(a) iteration=50
iteration=50
(c) iteration=
(d) iteration=150
Figure 6: Each grid cell in U-maze is colored according the expected return success rate when fixing its center as the target state.
Visualization Study on Generated Goals. In order to investigate whether the generated goals, served as curriculum in curriculum learning, truly guide the agent to the target state and are at an appropriate difficulty level, we show the distribution of generated goals at different training stages. Results in Figure 6 show that the generated goals are approaching as the training proceeds, and appropriate success rate level, where the hindsight constraint helps the agent aim at feasible positions while our diversity constraint encourages the agent to approach the target state. More results of visualization study be found in Appendix E.2
Comparison with Explicit Curriculum Learning. Since method can be seen explicit curriculum learning for exploration in Appendix [B.2, we also compare our method with another recently proposed automatic curriculum learning method for goal-oriented RI. (see Appendix E.3
8

---

Under review as a conference paper at ICLR 2021
for the detailed experiment). The result in Figure 5 indicates that RERL substantiilll outperforms this explicit curriculum learning approach even with GOID.
Impact of Goal Generation. To further investigate the performance gain from RERL, we design the ablation study goal generation. We incorporate the goal generator with various RL algorithms and evaluate their performance in the Maze Ant Locomotion environment. Results in Figure 5 illustrate that RERL significantly helps the RI. method obtain effective and stable performance.
Impact of Hyper-parameter Selection. Also, we study the effect of hyper-parameter selection here, i.c., Lipschitz constant L. number of regions N, number of trajectories Z, diversity weight a and hindsight weight B. We conduct the experiments on the Maze Ant Locomotion environment and report the results in Figure/3e and (b). Refer to Appendix E.4 for detailed information.
RELATED WORK
Goal-oriented Reinforcement Learning, Goal-oriented RL allows an agent to learn goal- conditioned policy, which takes the current state and goal state as the input and predicts a sequence of actions to reach the goal (Florensa et a 2018 Paul et al., 2019). Recent attempts (Andrychow- icz et al. 2017 Ren et al., [019] Pong et al., 2018)) combine off-policy RL algorithms with goal- relabelling to efficiently generate appropriate goals from the visited states and guarantee goal reach- ability using a hindsight constraint. In this paper, we divide the state space into several regions. Within each region, our algorithm learns a goal-conditioned policy to reach the generated goal. While most previous methods (Wu et al., 2018 Drummond] 2002) perform goal-oriented RL on top of the explored trajectories, our method utilizes a diversity constraint in the goal generation procedure to enhance exploration and automatically structure region-based memory.
Episodic Reinforcement Learning. Episode RL is proposed by cognitive studies of episodic mem- ory (Sutherland & Rudy 1989; Marr et al. 1991 Lengyel & Dayan (2088) in human decision making (Gilboa & Schmeidler 1995). Recent works have investigated integrating episodic memory with deep Q networks (DQNs) in non-aarametric (Blundell et al. (016)) and parametric (Pritzel et al. 2017) ways. In order to fully utilize the episodic memory, value propagation methods (Hansen et al, 2018 Zhu et al. 2019) have been proposed to obtain trajectory-centre value estimates. A common theme in recent work is finding similar historical trajectories to estimate the value function. While most methods use look-up operations (Pritzel et al.. 2017) graph structure (Zhu et al. 2019). our algorithm explicitly divides trajectories sharing the same goal into one region.
Hierarchical Reinforcement Learning. Hierarchical RL learns a set of primitive tasks that together help agent learn the complex task. There are mainly two lines of work. One class of algorithms (Shang et al. 2019 Nachum et al., 2018; [acon et al.) 2017]] Frans et al., 2018; Vezhnevets et al., jointly learn a low-level policy together with high-level policy, where the lower-level policy interacts directly with the environment to achieve each task, while the higher-level policy instructs the lower-level policy via high-level actions or goals sequence these tasks into the complex task. The other class of methods [Drummond] 2002 Fox et al. 2017 Simşek et al., 2005) focuses on discovering sub-tasks or sub-goals that are easy to reach short time and can guide the agent to the terminal state. Recently, several option-discovery approaches (Jinnai et al., 2019; Machado jet al., 2017, Bagaria & Konidaris] 2019 Konidaris & Barto 2009) are proposed to find a set of options to reduce the environment' s cover time. Different from these works, the idea of our work is similar to curriculum learning where the sub-tasks are geting harder during the training procedure. As stated by (Nachum et al. 2018), while jointly learning high-level and low-level policies can be unstable, we sidestep the problem by constraining goal generation to be within a specific region under hindsight constraint.
6 CONCLUSION
In this paper, we present framework that incorporates episodic RL with goal-oriented RL to im- prove the efficiency of exploration and exploitation. RERL does not require any additional reward engineering or domain expertise. For future work, it would be interesting to further investigate to in- corporate our work with representation learning to obtain better representation of the environment and imitation learning to enhance the learning efficiency with expert knowledge.

---

Under review as a conference paper at ICLR 2021
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAI Picter Abbeel, and Wojeiech Zaremba. Hindsight experience re- play. In NewrIPS, 2017.
Kavosh Asadi, Dipendra Misra, and Michael I. Littman. Lipschitz continuity in model-based rein- forcement learning. In ICML, 2018.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. AAAI, 2017.
Adrià Puigdomènech Badia, Bilal Piot, Steven Kapturowski, Pablo Sprechmann, Alex Vitvitskyi, Daniel Guo, and Charles Blundell. Agent57: Outperforming the atari human benchmark. In ICML, 2020.
Akhil Bagaria and George Konidaris. Option discovery using deep skill chaining. In ICLR, 2019.
Richard Bellman. Dynamic programming. Science, 1966.
Yoshua Bengio, Jérôme Louradour, Ronan Collobert, and Jason Weston. Curriculum learning. In ICML, 2009.
Dimitri P Bertsekas, Dimitri P Bertsekas, Dimitri P Bertsekas, and Dimitri P Bertsekas. Dynamic programming and optimal control. Athena scientific Belmont, MA, 1995.
Charles Blundell, Benigno Uria, Alexander Pritzel, Yazhe Li, Avraham Ruderman, Joel Z Leibo, Jack Rae, Daan Wierstra, and Demis Hassabis. Model-free episodic control. arXiv, 2016.
Chris Drummond. Accelerating reinforcement learning by composing solutions of automatically identified subtasks. Journal of Artificial Intelligence Research, 2002.
Yan Duan, Xi Chen, Rein Houthooft, John Schulman, and Pieter Abbeel. Benchmarking deep reinforcement learning for continuous control. In ICMI., 2016.
Benjamin Eysenbach, Xinyang Geng, Sergey Levine, and Ruslan Salakhutdinov. Rewriting history with inverse rl: Hindsight inference for policy improvement. arXiv preprint 1088 2020.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. ICML, 2017.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In ICML, 2018.
Roy Fox, Sanjay Krishnan, Ion Stoica, and Ken Goldberg. Multi-level discovery of deep options. In arXiv, 2017.
Kevin Frans, Jonathan Ho, Xi Chen, Pieter Abbeel, and John Schulman. Meta learning shared hierarchies. In ICLR, 2018.
Itzhak Gilboa and David Schmeidler. Case-based decision theory. The quarterly Journal of eco- nomicy, 1995.
Tuomas Haarooja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with a stochastic actor. arXiv preprint arXiv:1801.0 0100001290, 2018.
Guy Hacohen and Daphna Weinshall. On the power of curriculum learning in training deep net- works. arXiv preprint arXiv:/904.038 2019.
Steven Hansen, Alexander Pritzel, Pablo Sprechmann, André Barreto, and Charles Blundell. Fast deep reinforcement learning using online adjustments from the past. In NewrIPS, 2018.
Yuu Jinnai, Jee Won Park, Marlos C Machado, and George Konidaris. Exploration in reinforcement learning with deep covering options. In ICLR, 2019.
10

---

Under review as a conference paper at ICLR 2021
George Konidaris and Andrew Barto. Skill discovery in continuous reinforcement learning domains using skill chaining. NeurIPS, 2009.
Aviral Kumar, Justin Fu, Matthew Soh, George Tucker, and Sergey Levine. Stabilizing off-policy q-learning via bootstrapping error reduction. In NeurlPS, 2019.
Su Young Lee, Choi Sungik, and Sae-Young Chung. Sample-efficient deep reinforcement learning via episodic backward update. In NeurlPS, 2019.
Máté Lengyel and Peter Dayan. Hippocampal contributions to control: the third way. In NeurIPS, 2008.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv, 2015.
Zichuan Lin, Tianqi Zhao, Guangwen Yang, and Lintao Zhang. Episodic memory deep q-networks. arXiv preprint arXiv: arXiv:/805.076033 2018.
Marlos C Machado, Clemens Rosenbaum, Xiaoxiao Guo, Miao Liu, Gerald Tesauro, and Murray Campbell. Eigenoption discovery through the deep successor representation. arXiv preprint 17Xiv: 1089, 2017.
Joseph R Manns, Ramona O Hopkins, and Larry R Squire. Semantic memory and the human hippocampus. Neuron, 38(1), 2003.
Xudong Mao, Qing Li, Haoran Xie, Raymond YK Lau, Zhen Wang, and Stephen Paul Smolley. On the effectiveness of least squares generative adversarial networks. IEEE transactions patlern analysis and machine intelligence, 41(12):2947-290 2018
David Marr, David Willshaw, and Bruce McNaughton. Simple memory: theory for archicortex. In From the Retina to the Neocortex. 1991.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare G Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, (18(7750):559-5533 2015.
2015.
Volodymyr Mnih, Adria Puigdomenech Badia, Mehdi Mirza, Alex Graves, Timothy Lillicrap, Tim Harley, David Silver, and Koray Kavukcuoglu. Asynchronous methods for deep reinforcement learning. In ICML, 2016.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In NeurIPS, 2018.
Georg Ostrovski, Mare G Bellemare, Aaron van den Oord, and Rémi Munos. ration with neural density models. In ICML, 2017.
Count-based explo-
Sujoy Paul, Jeroen Vanbaar, and Amit Roy-Chowdhury. Learning from trajectories via subgoal discovery. In NeurlPS, 2019.
Matthias Plappert, Marcin Andrychowicz, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, et al. Multi-goal reinforcement learning: Challenging robotics environments and request for research. arXiv, 2018.
Vitchyr Pong. Shixiang Gu, Murtaza Dalal, and Sergey Levine. Temporal difference models: Model- free deep rl for model-based control. In ICML, 2018
Alexander Pritzel, Benigno Uria, Sriram Srinivasan, Adria Puigdomenech, Oriol Vinyals, Demis Hassabis, Daan Wierstra, and Charles Blundell. Neural episodic control. In ICML, 2017.
Zhizhou Ren, Kefan Dong, Yuan Zhou, Qiang Liu, and Jian Peng. Exploration via hindsight goal generation. In NewrlPS, 2019.
Matthew J Salganik, Peter Sheridan Dodds, and Duncan Watts. Experimental study of inequality and unpredictability in an artificial cultural market. science, 311, 2006.
11

---

Under review as a conference paper at ICLR 2021
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approxima- tors. In ICML, 2015.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region policy optimization. In ICML, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv:/707.06:: 2017.
Wenling Shang, Alex Trott, Stephan Zheng, Caiming Xiong, and Richard Socher. Learning world graphs to accelerate hierarchical reinforcement learning. In ICML Workshop, 2019.
Özgür Şimşek, Alicia P Wolfe, and Andrew G Barto. Identifying useful subgoals in reinforcement learning by local graph partitioning. In ICMI, 2005.
Robert Sutherland and Jerry W Rudy. Configural association theory: The role of the hippocampal formation in learning, memory, and amnesia. Psychobiology, 1989.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Alexander Trott, Stephan Zheng, Caiming Xiong, and Richard Socher. Keeping your distance: Solving sparse reward tasks using self-balancing shaped rewards. In NeurlPS, 2019.
Alexander Sasha Vezhnevets, Simon Osindero, Tom Schaul, Nicolas Heess, Max Jaderberg, David Silver, and Koray Kavukcuoglu. Feudal networks for hierarchical reinforcement learning. In ICML, 2017.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, 8(3-4):279-292, 1992.
Yifan Wu, George Tucker, and Ofir Nachum. The laplacian in rl: Learning representations with efficient approximations. In ICLR, 2018.
Guangxiang Zhu, Zichuan Lin, Guangwen Yang, and Chongjie Zhang. Episodic reinforcement learning with associative memory. In ICLR, 2019.
12

---

Under review as a conference paper at ICLR 2021
A ALGORITHM
Algorithm Regioned Episodic Reinforcement Learning (RERL)
1: Initialize n, g as terminal state, 9" as inital state
2: Initialize region-based memories {MMn)n by random sample
.., E do 4: Select region according to Eq. (5)
3: for episode = 1, ...
5: Collect trajectories {-=) for each M, that maximize E w(12, T2) according to
Eq. (TO)
6:
Construct intermediate goal g according to Eq. 11 9 for each Mn with & of average value
7:
for t = 1,2. .......,T7 do ,
8:
a, s (.
9:
8t+1 ~ P(-18t,
10:
Ft 4 r(),g. according Eq.
11:
Mn MM (s. 9
Update M,, according to Eq. 12
13: Sample minibatch à from Mn
Update policy on minibatch using DDPG or PPO
15:
end for
16:
end for
the initialization procedure, we set the terminal state the initial goal and initial state as the initial anti-goal, and sample trajectories into each memory. At each episode e, the agent selects one region that is most promising to lead to the terminal state in line We construct goal based the historical trajectories in line [ We take previous goals in other memories into consideration in the goal generation in line 6 From to line 12] the agent interacts with environment and update the memory. Our work focuses how to build an efficient exploration and exploitation mechanism that is naturally complementary with policy networks such as deep deterministic policy gradient (DDPG (Lillicrap al. 2015)) and proximal policy optimization (PPO (Schulman et al., 2017 in line 14
The overall description of our algorithm shown in Algorithm 2
B DICUSSIONS
B.1 EXAMPLE FOR GOAL GENERATION
Previous works Florensa et al., 2018 Vezhn- evets et al. 2017) adopt goal generator con- struct immediate intrinsic rewards according to the previous states. However, they often suf- fer lot from balancing the efficiency of explo- ration and exploitation and stability in training. In the first episode, the agent explores two tra- jectories in different directions, with the closest one Tia to the target state labeled as the goal gi and the farthest one Ti6 the anti-goal ØI. In the second episode, the agent evaluates the highest value states the regions and selects one according to Eq. (5). The agent does explo- ration under the guided by @1 (illustrated as sun icon in blue region) and ÿ1 (illustrated as moon icon in blue region). If the agent selects the re- gion 2, following the similar procedures, the agent will explore the region guided by g2 (illustrated as sun icon in green region) and 92 (illustrated as moon icon in green region). Note that goal will direct the exploration. Hence, in the goal generation, take the historical goals in the other regions into consideration by the diversity constraint. However, for the anti-goal generation, there no need consider other region data described in Section
goal
2b
anti-goal
1b
tarpet state
2a
region
10
region
trajectory memoor (region 1)
trajectory at memory 2 (region
Figure 7: An illustration of exploration strategy.
13

---

Under review as a conference paper at ICLR 2021
B.2 RELATIONSHIP TO CURRICULUM LEARNING
In order better understand why method can work in complex environments and can excel other traditional methods more intuitively, we further investigate the relationship between our algorithm from Eq. (3) and empirical utility maximization formulation proposed in (Hacohen & Weinshall] 2019). We provide theoretical analysis that under some assumptions, optimizing our objection func- tion can be similar to optimizing a curriculum algorithm under additional constraints.
Following Section 2 we formulated reinforcement learning problem as Markov Decision Process (MDP) by a tuple (S,A,P, 7), where S is the state space, A is the action space, P S x A - (SS) is the state transition probability distribution, r : AA - [0.
is the reward function, and 7 [0, 1) is the discount factor for future rewards. The utility function is defined as the expected sum of the immediate and long-time utility U~ (s) under the policy x : S -> factor E [0, 1), which can be formulated as:
[0, 1), and discount
(s) == = ((.s,,))))
Σ Er((snn
(I)
where T is the episode length. We can utilize (s) to represent the long-time reward (i.e., episode reward). In order to formulate the short-time reward, similarly, we define U, (s:) by Un (s;) == 7'r(st, az). In similar manner with the Empirical Risk Minimization (ERM) frame-
work, we choose to maximize the average utility, which is defined as follows:
T
π = arg max (TT), where
= B(U>) = - Un(ss)
(2)
Hindsight Constraint. We define the scoring function, i.e. pacing function in curriculum learning (Bengio et al., 2009) with & S -> G x G which is a known and tractable mapping- ø effectively provides a Bayesian prior g E 9 for data sampling, namely, exploration, where g denotes goal and G denotes goal space. Based on the analysis above, we can formulate Eq. {
1 Σ Un Usi) T
1
(s))-)((()ss)
where <(-(s:) denotes the induced prior probability conditioned on 8,. In order to guarantee the convergence, ((()))) should always be a non-increasing function of the difficulty level of 8t. In algorithm, we define the goal space G set of visited states in state space S (i.e., hindsight constraint in Section (3), which guarantees each goal/anti-gos is sampled from previous states. This proves the following result:
Proposition The difference between the expected utility function with and without prior g (i.e. Ug (T) and (())) is the covariance between utility function Uz (s) and goal generation @(-[s).
Proof. The proof of Proposition can be found in Appendix
Diversity Constraint. However, should be noted that goal g here is sampled from previous states, which guarantees the reachability of the goal but also limits potential exploration. To address this issue, we adopt diversity measure Hregion (T)) to encourage the exploration between different region (diversity constraint in Section3iis a simple implementation). Combining the aforementioned hindsight and diversity constraints, we define our objective as
π arg max ( (T), under hindsight and diversity constraints.
(4)
which can be easily derive as equivalence to Eq. (
Proposition 2. The modified optimization landscape induced by curriculum learning has the same global optimum x² as the original problem.
Proof. The proof of Proposition 2 can be found in Appendix C.4
According to the analysis, we can conclude that our algorithm can be regarded as a novel curriculum learning approach in goal-oriented setting, which can be proved to have the same global optimum as the original problem. In Section 4 we conduct experiments to prove that the goals are generated at different levels as the eurriculum to guide the agent in curriculum learning.
14

---

Under review as a conference paper at ICLR 2021
B.3 RELATIONSHIP WITH MAXIMUM ENTROPY RL
In this section, we consider multi-goal RL as goal-oriented policy learning (Schaul et al., 2015 Plap- pert al., 2018). We further discuss the motivation behind these two constraints, namely hindsight and diversity constraints, and the relationships between our work and inverse maximum entropy reinforcement learning.
Preliminaries. We begin with some notations and previous motivations maximum entropy re- inforcement learning (Eysenbach et al. 2020). The likelihood of a trajectory т := {sr)?= under policy x can be formulated as ((s) ((50) II. P(s:41|5t, at) (a((())) the goal-oriented RL, can re- cr-rrtte it as
[(s,g) P(s0) II
(5)
where the initial state is sampled 80 P(so) and subsequent states are governed by dynamic distribution $1+1 ~ P(s++1|$t az). As we discuss in Appendix B.2 goal-oriented RL can be re- garded regular RL with prior knowledge generated by mapping function & based Hence, the target joint distribution over goals and states is
((-1s)
Larger
(, (8,
P(so) II P (1 ae) 7(g)
(6)
where Csarga(s, g) be the joint distribution over state S, goal g G; and Z(g) is the factor of normalization.
Diversity Constraint. We can express the multi-goals RL objective as the reverse KL divergence
between the joint state-goal distributions:
max- H(s, () = max -
(s.g))
where the joint distribution of likelihood L and prior information g of trajectory 7 is defined as C(s.g) g) := C(slg) @(-ss). Then, we rewrite Eq. regularized) reward of goal-conditioned policy L(slg):
7 as maximizing the expected (entropy-
T Σ
r(s,, a (g) log (() (19) log Z(g)
E Eg s(-(())))
(8)
Hindsight Constraint. Since the distribution over goals is fixed, we can ignore the log Z(g) term for optimization. A less common more intriguing choice to factor L(s, 0(1ss) B(s), where B(r) is represented non parametrically as a distribution over previously-observe Therefore, @(-1s) is formulated a hindsight relabeling distribution. In this implementation, sample goals from previous states in the region-based memory to present B(s).
states.
C PROOFS
C. PROOF OF PROPOSITION
I
Proposition 3. Given the joint set X and several region-based sets (Le., sub-sets) Xn, where 1, 1,2,..., N and N the number of regions, we have
Vn, max V(x) 2 ZEN
max #E Ba..
V(z), where F,, arg max ((x)).
(9)
æt E
In this section, we provide the proof of Proposition I The motivation of Proposition to find relaxed lower bound of V(x), æ E X' based on the definition of the region.
15

---

Under review as a conference paper at ICLR 2021
Proof. By Eq.
B VT we have
T
max V(x)
= max B.ESig. sEA
Σ (1l
sE
rr(ss (rrst,ar, acs
max 2
{ max B mi
2 (2.
(10)
Σ Er'r acs s
max ESESW i EyEAN
max EE (21.
(z) where arg max V ((In), 12= 1,,,,, ...,, 2,E7;
The intuition behind the proposition is easy to understand. Since we have partitioned the joint set X' into several region-based sets (i.e., sub-sets) {X, We effectively avoid the agent switch- ing among regions, meanwhile removing these trajectories out of the original candidate trajectory family.
C.2 PROOF OF PROPOSITION 4
Proposition 4. Denote the Bellman backup operator in Q learning with goal as B || + R[S|||A|X[GI and a mapping Q S x A G -> TR. ||X|| with |S| < oo and |A| < co. Repeated applications of the operator B for our goal-oriented state-action value estimate Q converges to a unique optimal value Q*
Proof. The proof of Proposition is done in two main steps. The first step is to show that our goal g can converge the terminal state. In the second step, we prove that given goal g. our goal- oriented approach can converge to a unique optimal value Q" In other words, we need to prove that
g + g" in the first step and Q + Q" in the second step.
Step Our algorithm aims find the high-value previous states for goal generation. At the begin- ning of the task, the terminal state will be regarded as the final goal since it has the highest value. Hence, the terminal state, if it has been visited once, will be assigned as the goal. Assume that the agent can conduct plenty of exploration. Then, we can say that the generated goal will keep approaching the terminal state g"
Step II. Note that the proof of convergence for our grie-tri RL quite similar to Q-learning [Bellman] 1966 Berttekas et al. 1995. Sutton & Barto 2018). The differences between our ap- proach and Q-learning are that Q- value Q(s, a, 9. 9) is also conditioned on goal g and anti-goal g. As introduced in Section 3 anti-goal works like reward shaping technique, which is proposed to avoid local optima [Trott et al. 2019). Hence, we omit 9 in the following proof. We provide detailed proof follows:
We can obtain goal g E G approaching the terminal state from Step I. Based on that, our estimated goal-conditioned action-value function Q can be defined
(Q(s, R(s, a, g) + max
Σ P(s'ss. (il5,a))Q($$,d..)))) (().)
(11)
a'EA
e'ES
For any action-value function estimates Q1, Q?, we study that
BBQ' (s, a) BQ² a.
=7. max d'EA
Σ P(s'ss,,)) ()) ('((' ,'
max
Σ P(s|ss,,)) (
a' d'EA
5. max a'EA
Σ P(s'(s,a) ('
Σ P(5'(s,a) (s d' e'ES
(12)
Σ P(s'|ss,)) (s', (s',
= max a'EA S'E
=mm
S 5. max eES,
(((( (s,
16

---

Under review as a conference paper at ICLR 2021
Combining Step I and II, conclude that roal-conditioned estimated state-action value Q can converge to a unique optimal value Q" leading to the terminal state g
C.3 PROOF OF PROPOSITION
In this section, we provide proof of Proposition From Eq. B Ug(a is a function π which is determined by the correlation between Ux and ((g) (i.e. @ s)). We can rewrite Eq. (3) as
Ug(Tt) 1 T
(s)) [(U)))(((o) [() T Bl,,)
(13)
T [CoviUm, of + [ooo]
T [u(T)) + Cov[Un.
This derivation can be found in Appendix C.6 We can find that curriculum learning changes the landscape of the optimization function over the policy π from ((T) to (z)... Intuitively, the above equation also suggests that if the induced goal g. which defines a latent variable over the goal space G, is positively correlated with the optimal utility (s), and more so than with any other U- (s), then the gradients in the direction of the optimal policy π in the new optimization landscape may be overall steeper.
Hence, this is necessary to design task-related goals. However, it is infeasible to obtain appropriate goals through handcrafted design and manual generation. In this paper, we introduce hindsight and diversity constraints to help the agent learn from achieved task-related information (previous states) and unknown task-related information (unexplored states) respectively.
C.4 PROOF OF PROPOSITION 2
In this section, we provide proof of Proposition In order to prove that the modified optimization function in the state-space-related parameter space has the property that the global maximum at m more pronounced, we derive the objective function based on Proposition [ We can assume that optimal policy л maximizes the covariance between ((g) (i.e., ((-(s)) and utility U₂ (s). namely
arg max(((T) = arg max Cov[Un.. Ø) n
(14)
The proof of the assumption can be found in Appendix C.3 We introduce Lemma heer, the proof of which can be found in Appendix C..5
Lemma 1. (Florensa et al. (2017)) For any curriculum satisfying Eq.
14
x arg max (TT) = arg max, ((TT) 2. (T(")) Uy 2 - VT
Lemma Thas proposed two claims. The first one presents that the problem of maximizing the co- variance between ((g) and utility (s) shares the same optimal solution with the original problem. In addition, the modified optimization function in the original parameter space without goal has the property that the global maximum with goal g is pronounced.
C.5 PROOF OF LEMMA I
In this section, we provide the proof of Lemma Claim in Lemma can be derived directly from Eq. [14,, while for the claim 2, we have
Proof.
Ur(TT') (T(TT) = = U(=) Cov(Un..9)
2 Ug(TT) - -U(T) - -oov(Ur-,g))
(15)
U(x=)) -U(TT)
17

---

Under review as a conference paper at ICLR 2021
C.6 DETAILED DERIVATION OF EQ.
13
In this section, provide the detailed derivation of Eq. (T) in Eq. (3) and try to obtain that in Eq. 3
13
We begin from the formulation of
Proof.
1 (T)
1 (Ux(s)) B(U,))((())))) B(o)) + T B[U,)
T
t=1
Σ (U)(6))(()))) Σ (S.)E)))) Σ (oG.)E + + BU,]] + 7 R [
7
Σ (U=(+))((:)) [[U)]B[o] Σ ((GG))E(US) + BTUJ)EE + EU E
7
7 Σ (U)(())((a)) 7 (T- EUU+]E[0! Σ (o(a)) E
(16)
Since BiØ] = + ( have
r (T( T
Σ (+(o)(((a)) 1
t (T E[U T B[U]][[o]
(17)
T (s.))(()))
D EXPERIMENT
D.1 MODIFIED ENVIRONMENTS
Ant Locomotion. In this part, we introduce two environments based Ant Locomotion, namely Free Ant and Ant Maze. The ant quadruped with actuated joint, 2 for each leg. The en- vironment is implemented in Mujoco. Besides the coordinates of the center of mass, the joint angles and joint velocities are also con- tained in the observation of the agent. Considering the high degrees of freedom, navigation in this quite complex task requires motor coordination. More details can be found in Duan al. (2016), and the only difference is that in our goal-oriented version of Ant, we extend the observation with the goals. The reward still a sparse indicator function being 1 only when the center of mass (z, of 0.5 positions corresponding to e-balls in state
the Ant is within space. For the Free Ant experiments, the objective is to reach any di-
Figure 8: An illustration for Maze Ant Locomotion envi- ronment.
position in the square [-5. 5/2. Therefore the goal space mensional, the state-space is 41 dimensional. and the action space dimensional. As for the Ant Maze environment, the agent is constrained move within the maze environment, U-maze in this case, and the size of all the blocks in the maze is x 8. The maze consists a totally 18 blocks.
Multi-Path Point Maze. All the experiment setting is similar to the Ant Maze environment. We replace the Ant agent with Point-Mass and change the maze into multi-path one. The action of the Point-Mass is a velocity vector, namely, the 2 dimension.
N didimensional Point-Mass Maze. In the N N-dimensional only move within small subset of the state space. In the two-dimensional case, the set of feasible states corresponds to the 5-5, 5] x [-1, rectangle, making up 20% of the full space. For N 2, the feasible space is the Cartesian product of this 2D strip with [-e, N22 where 0.3.
Sint-Maas maze experiment, the agent
18

---

Under review as a conference paper at ICLR 2021
(a) Pree Ant Locomotion
(b) Maze Ant Locomotion
(c) Multi-Path Path Point Mass
nonnalzee spande sgg rdlun
nomalized opinnde average return
1.0
1.0
0.8
0.8
0.8
0.6
0.6
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
5k
25K
50K
75K
100K
125R
5K
25K
50K
75K
100K
125K
50
75
100
125
Acration
Deration
Frematoo
2-dimension
(+) 3-dimension Point Mass
1.0
RPRL+PPO
conmalized aoodd-3regge
0.8
0.8
SR-PPO
HSG-DOPP
0.5
0.6
TRPO
A/C
0.4
0.4
HER
AutoGG
PPO
0.0
25
50
75
100
125
25
100
125
Renition
Resation
Figure 9: Learning curves of RERL,, HGG, HER, SR and AutoGG on various environments, where the solid curves depict the mean, the shaded areas indicate the standard deviation, and dashed hori- zontal lines show the asymptotic performance.
In this higher-dimensional environment, our agent receives reward of when moves within EN = .. of the goal state, to account for the increase in average 1.2 distance between points in higher dimensions. In these experiments, the full state-space of the N-dimensional Point Mass is the hypercube [-5,5] 5J
v2
D.2 EVALUATION DETAILS
We adopt HGG (Ren et al. 2019) incorporating with DDPG (Lillicrap et al. 2015). SR (Trott et al, 2019) accompanying with PPO (Schulman et al.) (017)) as these models are originally proposed. All curves presented in this paper are plotted from 12 runs with random task initializations and seeds. Following the regular procedure if the agent obtain 1 as the reward according to Eq. 2 where 5 stays the same for all the approaches. However, in the practice, we conduct reward as the r(st, Ge (g, g) = min(0, -d((()+ (8++1), 1).1) + d(o(r++ 18)+1). to accelerate the training process.
ooienteie RL, an episode is considered successful if and only
D.3 IMPLEMENTATION DETAILS
Almost all hyper--praee parameters using DDPG (Lilicrrap et al. 2015). TRPO (Schulman et al. 2015),
PPO (Schulman et al.) 2017), Soft-AC (Haarnoja et al. 2018 are kept the same benchmark results. Specifically, we list our hyper-parameters as here. number of MPI workers: 1; buffer size: 10 trajectories; number of regions N: in agent level; batch size: 256, number of trajectories Z: 50, Lipschitz constant L: 5; learning rate: 10 in the network level; discount factor: 0.99;
interpolation factor Polyak averaging (if there is): 0.995; scale of additive Gaussian noise: 0.2:
probability of HER (Andrychowicz et al. 2017) experience replay: 0.8.
E RESULTS
E. ADDITIONAL EVALUATION ON STANDARD TASKS
In this section, we provide additional results on comparisons between RERL and various baselines. In order to answer the first two questions, we demonstrate our method in two challenging robotic locomotion tasks, where the goals are the (z, position of the center of mass of dynamically complex quadruped agent. In the first example, the agent has no constraints, and in the second one, the agent is inside U-maze (see Section 4 for details). Results in Figure 9 (b) demonstrate that the performance of our approach exceeds that of the strong baselines mentioned in Section 4 To answer the third question, train ant agent reach any position within multi-path maze. As
19

---

Under review as a conference paper at ICLR 2021
shown in Figure (), approach obtains better performance even in the multi-pate calli-ppath environment where goal distribution is naturally more complex than previous environments. To answer the fourth question, investigate how our method performs with the dimension of goal-space in envi- ronment where the goal space grows dimension within the feasible region, egg. 2D and 3D. As shown in Figure d), our approach outperforms strong baselines in both low- and high-dimensional environments.
E.2 ADDITIONAL RESULTS VISUALIZATION OF GENERATED GOALS
To answer the final question, we conduct visualization study on generated goals to investigate whether goals encourage the agent the target state, and anti-goals can prevent the agent from local optima. The visualization of goals can also represent the effect diversity and hindsight constraints through exploration and reachability of generated goals.
gnal
antiggaal
bege state
(a) seration
iteration=150
(c) #eration=400
Figure 10: Generated goals and anti-goals visualized as the blue and green points respectively.
Results in Figure T0 show that the hindsight constraint helps the agent aim at feasible positions while our diversity constraint encourages the agent to approach the target state. Specifically, from and one note that the agent is pulled by its goal and pushed by its anti-goal and goals from the other regions. Hence, once a region is leading to a wrong direction, it also can encourage exploration via diversity constraint.
state
banget state
nommalied glande
(a) iteration=00
(b) iteration=150
iteration=409
Figure 11: Each grid cell in U-maze is colored according to the expected return success rate when fixing its center as the target state.
As illustrated in Figure [T] the generated goals are approaching as the training proceeds, and an appropriate success rate level, which is accorded with the curriculum in the curriculum learning (see Appendix B.2 for details).
stat state
antiggoal
state
(a) ixeration=5
(b) iteration=15
(c) iteration=40
Figure 12: Generated goals and anti-goals visualized as the blue and green points respectively.
Results showed in Figure 13 and 12 are similar with that Figure and 10 respectively, which actually confirm the analysis above.
20

---

Under review as a conference paper at ICLR 2021
366
target state
aemalized episade avenge retum
(a) 5
(b) itcration=15
(c) itcration=40
Figure 13:
Each grid cell in Multi-path maze is colored according to the expected return success rate when fixing its center as the target state.
E.3 EXPERIMENT ON THE COMPARISON WITH EXPLICIT CURRICULUM LEARNING
In (Florensa et al. 2017 GOID is defined as a goal set as GOID(")) = (o a (1 a} where f 9) represents the average success rate in small region closed by goal g. In order to construct the GOID set, we follow its definition and sample generated goals from GOID(T)) via rejection sampling.
<
(a) Hyper parameter
(b) Hyper parameter
NV
Hypen parameter
nesialized eptocd srenac rrem
comallze eptccde SVSURE retur
1.0
0.8
1-10
0.8
Yox
Zw120
0.6
0.6
gytsode
0.6
0.4
0.4
0.4
0.2
0.2
0.2
0.0
5K
23K
50C
75K
1O0K
125K
5K
23K
50K
75K
100K
125k
5K
23K
50K
75K
100K
125K
Besstion
nocmsiiod avenge sttum
(d) prrpe--rrrmeter
Dommklos epsode arengg retur
(e) Hyper-parameter f
belamb2
0.8
0.8
<2he-2
belam2
0.6
0.6
0.4
0.4
0.2
0.2
0.0
9K
23K
5DC
75K
1OOK
125K
5x
25K
50K
75K
100K
125K
lheration
Figure 14: Learning curves of ablation study on parameters: N, and B. where the solid curves depict the mean, the shaded areas indicate the standard deviation, and dashed horizontal lines show the asymptotic performance.
E.4 ADDITIONAL RESULTS ON ABLATION STUDY
In this section, selection of Lipschitz constant task-dependent since it is highly related to the scale of the value function and goal distance. For the robotics tasks tested in this paper (i.e., Ant Maze Locomotion), as showed in Figure [[)a), we find that the performance of RERL is reasonable as long as L is not too small. Similar to the selection of the number of regions N is also theoretically task-specific. We test few choices on Ant Maze Locomotion and find range of N that works well. As Figure 14 illustrates, appears that the RERL is reasonable as long as N is not too large. As for the number of trajectories Z, we plot the curve on different Z in Figure 14] and find that for the simple tasks, the choice of not critical. Parameters a and 3 together define the trade-off between value function. diversity, and hindsight constraints. Results in Figure 14 d)(e) show that the choice of and B is indeed robust.
up of ablation on several hypae-parameters used in the RERL. The
21


Reviews:
[{"review_id": "zRFrglt43nf", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "Authors present an approach to partition the state space by generating a diverse set of goals, and to explore the state space effectively by finding policies that can reach to these goals effectively.\n\nAt each step, the algorithm chooses a region (or a goal) to explore by sampling from a Boltzmann soft (arg) max distribution with an annealing temperature parameter.\n\nThe goal generation strategy is strengthened by two heuristic ideas, namely adding hindsight and diversity constraints.\n\nOverall, while I think breaking a large RL problem to several tractable sub-problems is an interesting direction, I think that the paper is not doing a good job of justifying the specific way in which this is performed. \n\nAt a high-level, the approach could be thought of as finding a set of options (along with finding option goals and initiation sets), and then searching for the kind of behavior that maximizes option value. With this in mind, I expect the authors to better situate their work in comparison with option-discovery approaches in RL such as \"Eigenoption discovery through the deep successor representation\" Machado et al., \"Option Discovery using Deep Skill Chaining\" Bagaria and Konidaris, and \"Exploration in reinforcement learning with deep covering options\" Jinnai et al., to name a few.\n\nSome additional comments and questions:\n\n- To say that \"the application of reinforcement learning (RL) is still impractical in terms of sample efficiency\" is inaccurate. Sample inefficiency is definitely an issue that can plague RL in some applications, but that does not mean that RL is impractical regardless of the application in question.\n\n- I don't understand what it means to say some RL algorithms \"neglect the exploitation part\". Surely, goal-oriented RL performs reward maximization in some sense, right?\n\n- The instability of RL is, to the best of my knowledge, not related to sparse rewards (C1). Among other things, it is related to convergence guarantees (or lack thereof) when using nonlinear approximators and highly-correlated updates. Can you provide citations that refute my claim and support yours?\n\n- I don't even understand C2 in introduction.\n\n- with C3, I understand what you are trying to say, but maybe you can rephrase it? Maybe say, breaking a task to a bunch of sub-tasks can avoid redundant exploration?\n\n- wrong citation for DDPG.\n\n- in general I find frequent typos and mistakes. For example, from related work, you say \"value propagation methods have proposed ...\" Humans propose to use value propagation methods that obtain trajectory-centric values estimates.\n\n- why is the range for the reward signal open? Why can't R be 1?\n\n- You consider domains with continuous actions, which means that the policy outputs a pdf over continuous space. It is then, not accurate to say that the policy output is bounded above by 1.\n\n- In equation (1), the notation for reward is off.\n\n-\"However, as stated in (Pritzel et al., 2017), in the environment with sparse rewards, there may be very few instances where the reward is non-zero, making it difficult for an agent to find good past experiences. \" Does this incredibly obvious point require a citation?!\n\n- From Definition 1, can you clarify what even is a \"perfect\" partition? We should be able to define it before attempting to find it.\n\n- In equation 5, how is max computed if the space is continuous?\n\n- In formulation 10, why did you choose this specific way of promoting diversity? It is not justified, and there is no theoretical evidence to demonstrate that this indeed gives us the diversity that you tout it would.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "mAlEspMgdd", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "**Summary:**\nThis paper presents a new algorithm called Regioned Episodic Reinforcement Learning (RERL), which combines ideas from episodic memory, with automatic sub-goal creation or “goal-oriented” RL. The method works by dividing the state space into regions, where a different goal identifies each region. Then, using an episodic memory technique, the agent is able to learn about new experiences in a sample efficient way. This allows the agent to explore effectively, and learn a good policy quickly in problems where there are sparse rewards. The paper provides some theoretical justification for the new algorithm, and provides some empirical results that demonstrate its effectiveness. \n\n**Strengths:**\nThe paper combines two RL techniques in a novel way to address important issues in deep rl. The experiments demonstrate that RERL can achieve good performance on challenging problems. The paper also presents a good background overview of related work, which is useful to get appropriate context.\n\n**Weaknesses:**\nThe use of the term episodic is a bit ambiguous, especially in the introduction. The word “episodic”, as it refers to “episodic memory” from neuroscience, needs to be clearly disambiguated the from the “episodic setting” in RL, which is something completely different. Additional clarification in abstract/introduction would do a lot to reduce confusion.\n\nThe paper has many experiments on a variety of domains, but only a few of the results are included in the main text. I think including more of the results in the main paper would strengthen the conclusions and be more convincing for the reader. Also, some important experiment details are missing, like how many training steps was each agent trained for (what do \"iterations\" correspond to in Figure 5)? The number of independent runs (seeds) for each algorithm should also be listed. This information should be included so that the reader can better evaluate the variance of each method, and make more confident conclusions.\n\n**Recommendation:**\nI vote to accept this paper. I think this paper presents a novel and interesting idea that is sufficiently supported by the empirical experiments. The challenges that the new methods attempts to address and important and central to good performance in deep RL, thus the papers results would be of interest to RL experimentalists and practitioners. However, I think the paper could be made stronger improving the clarity, and by including more of the experiments in the main text.\n\n**Questions:**\nHow many independent runs (seeds) were used in the experiments?\n\nIt was not clear to me whether the anti-goal $\\bar g$ is new in this paper, or if it is something that has been used before.\n\nMore about $\\bar g$: the paper states that it “prevents the policy from getting stuck at the local optimum and enables the agent to learn to reach the goal location quickly,” but does not offer an explanation why. Why does it keep the agent from getting stuck at a local optimum? And why does it help the agent reach the goal location quickly?\n\n**Minor Comments:**\n-I find the hyperlink highlighting in the text (the green and red boxes) to very distracting. I think removing them would improve the overall presentation of the paper.\n-The in text citation style could be improved. When citing an author and using their name in the text, they should be cited like “Foo et al. (2020) propose a new method…”, and not like “(Foo et al., 2020) propose a new method…”\n(For more details see: https://owl.purdue.edu/owl/research_and_citation/apa_style/apa_formatting_and_style_guide/in_text_citations_the_basics.html, for example.)\n-There is a missing figure reference on page 7.\n\n**After Author Response and Discussion:** Thanks to the authors for their responses. After reading the other reviews and the author responses, I am lowering my score to 5. I agree with the other reviewers about the experiments: they feel rushed, and the design and presentation is not as careful as it could be. I think the paper could be greatly improved by a little more attention the presentation of the experiments and their analysis in the main text.", "extra_scores": {}, "extra_text": {}}, {"review_id": "hLX4I_TbeDa", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "### Summary\nThis work proposes a curriculum learning in RL that combines goal-oriented RL and episodic RL in order to achieve a sample efficient exploration-exploitation trade-off. \n\nClarity: The paper could benefit from a clear presentation in order to help properly understand the proposed methods and all its components.\n\n### Contributions\n- The paper designs an intrinsic reward to encourage exploration while avoiding local optima policies.\n- Exploitation is leveraged through a region-based memory.\n- The paper proposes a goal sampling scheme that combines hindsight constraint for reachability and diversity constraint for exploratory behaviour.\n\n### Concerns\n- \\mathcal{X} is sometimes used as a set sometimes as a distribution. This might raise some confusion for the reader.\n- The mapping \\phi is quite central to you method, but I failed to understand which type of mapping was used in your experiments. Consequently, which metric was adopted ?\n- \"we directly assign the visited state with the average value in the region as the anti-goal.\": Does this mean, the anti-goal is always in the same region as the visited state ? Can you please clarify this point/choice of anti-goal?\n- In eq.9, how does V^\\pi(x_s) depend on s_t (is it integrated to the inner minimization)?\n- \"slowly changing goal-conditioned tasks to guarantee stability by restricting goal updating within each region\": Do we need to guarantee slow (spatial) changing of the sampled region too for this stability to hold ? If yes, how is this enforced in the algorithm?\n- How were the existing approaches trained ? With which reward ? the one from eq.2 (i.e. using the region-based goal and anti-goal sampling ) ?\n- \"We further extend the task to evaluate whether the agent is able to reach any given position (\\epsilon-balls depicted in red) within the maze for Maze Ant\": What was the size of the agent (Ant) compared to the width of the corridor ? *Ant Maze look tight around agent, i.e if it learns to reach the end of the maze it can’t miss any intermediate goal.*\n- From the goals and anti-goals visualizations, anti-goals seems to be always generated further ahead on the path to the target, while it was mentioned that the anti-goal is set to the average value in the region ? When getting closer to the target, won't these anti-goals between the reachable goals and the target keep the agent away from reaching it ? Can you please clarify this ?\n- Can you elaborate on the goal generation ablation study ? This seem to deserve more attention to better evaluate the algorithm.\n\n### Minor comments\n- Some notations are defined later in the paper than where they were first introduced.\n- In eq.9, should the argument be x_z ?\n- There is a problem with some figures and appendices references.\n- Did you try higher dimensional Point-Mass ?  ", "extra_scores": {}, "extra_text": {}}, {"review_id": "RMROtQRVKwo", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "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": "The paper proposes a reinforcement-learning scheme intended to strike a productive balance between exploration and exploitation by way of decomposing the state space into regions and developing policies for \"solving\" each region.\n\nAlthough the paper claims to include \"extensive experiments\", the design and analysis of the method was rather coarse. In particular, the results presented in Figure 5 seem solid. But, based on the presentation up to this point, I was expecting to see a comparison on an environment that is good for goal-oriented methods and one that is good for episodic algorithms. I thought you'd show your approach working well in both, while the other methods struggle when used outside of their ideal setting.\n\nMy main frustration was that a lot of the paper was spent presenting the algorithm and then the experiments were presented only very briefly. For an algorithm like this, its utility is measured in its ability to work according to its design. I agree that showing the algorithm outperforming state-of-the-art algorithms on the ant problems is a good thing. But, we wouldn't expect that the algorithm would outperform the others in ALL environments, would we? If not, then seeing some assurance that the reason that it is working well is because the problem structure somehow matches the algorithm structure would be very valuable. Then, we can see it's not just luck but its DESIGN that is the cause of its experimental success. The way the results are currently presented, I'm left with the feeling that the algorithm is clever but perhaps limited in scope. More detailed experiments would help allay this fear.\n\nThe paper needs a detailed editing pass. Comments (hopefully helpful!) follow.\n\nDetailed comments:\n\n\"by current policy\" -> \"by the current policy\"?\n\n\"these methods investigating to explore useful trajectories efficiently\" -> \"these methods intended to explore useful trajectories efficiently\"?\n\n\"suffer from generating appropriate goals\" -> \"suffer from the difficulty of generating appropriate goals\"?\n\nC2: Perhaps reword it? I wasn't able to interpret what is being said. I think there is a lot of important background being left unsaid.\n\n\"also make substantial contributions to improve\" -> \"also make substantial contributions that improve\"?\n\n\"when updating value function\" -> \"when updating the value function\"?\n\n\"enforcing goal space to be\" -> \"enforcing that the goal space be\"?\n\n\"a subset of state space\": As opposed to what? Doesn't the state space include ALL states? So, any set of states is a subset of the state space...?\n\n\"exploration issue automatically\" -> \"exploration automatically\"?\n\n\"with hindsight constraint\" -> \"using a hindsight constraint\"\n\n\"the whole exploration space\": What's an exploration space? Is it the entire state space?\n\n\"perform the goal-oriented RL on\" -> \"perform goal-oriented RL on\" or \"execute the goal-oriented RL algorithm on\"?\n\n\"utilizes diversity constraint in goal generation procedure\" -> \"utilizes a diversity constraint in the goal generation procedure\"\n\n\"in human decision-making procedure\" -> \"in human decision making\"\n\n\"investigated to integrate\" -> \"investigated integrating\"\n\n\"with deep Q network (DQN)\" -> \"with deep Q networks (DQNs)\"\n\n\"have proposed\" -> \"have been proposed\"\n\n\"to estimate value function\" -> \"to estimate value functions\"?\n\n\"use look-up operation\" -> \"use look-up operations\"\n\n\"There are mainly two folds\" -> \"There are mainly two lines of work\"?\n\n\"via high-level actions or goal\" -> \"via high-level actions or goals\"\n\n\"discovering these sub-tasks or sub-goals, which is easy to reach\" -> \"discovering sub-tasks or sub-goals that are easy to reach\"\n\n\"in (Nachum et al., 2018),\" -> \"by Nachum et al. (2018),\"\n\n\"constraining the goal generation within a specific region under hindsight constraint.\" -> \"constraining goal generation to within a specific region under a hindsight constraint.\"?\n\n\"RL problem can\" -> \"The RL problem can\"?\n\n\"In the setting of finite horizon\" -> \"In the finite-horizon setting\"\n\n\"state-value function Q\" -> \"state-action value function Q\"\n\n\"tuple from a replay\" -> \"tuples from a replay\"?\n\n\"training, which is a typical parametric RL methods, suffering from sample inefficiency\" -> \"training. It is a typical parametric RL method and suffers from sample inefficiency\"\n\n\"in the environment with sparse\" -> \"in environments with sparse\"\n\n\"compute sparse reward\"?\n\n\"an agent ... yields sparse rewards\"? Maybe I'm not understanding how you are using the phrase \"sparse rewards\"? I interpret it as an environment where most rewards are zero, so I don't see how they are \"computed\" or \"yielded\".\n\n\"Specially,\" -> \"Specifically,\"?\n\n\"should base on\" -> \"should be based on\"?\n\n\"of diversity constraint\" -> \"of the diversity constraint\"\n\n\"avoid the local optima\" -> \"avoid local optima\"\n\n\"can be further explained by\" -> \"and can be further described as\"\n\n\"Appendix B.1\" -> \"Appendix B.1.\"\n\n\"tasks to guarantee stability\" -> \"tasks guarantees stability\"?\n\n\"be well adaptive with\" -> \"adapted to\"?\n\n\"etc.\": Redundant, given \"such as\"? (Twice.)\n\n\"(see Figure ??)\"?\n\n\"accompanying with\" -> \"accompanying\" or \"with\" or \"accompanied by\"\n\n\"One should be noted\" -> \"Note\"\n\n\"can be proved as\" -> \"can be shown to be\"? Not quite. I'm not sure how to reword it, but some rewording is needed.\n\nIn terms of related work, I was hoping to hear how you see your work relating to Konidaris' work on skill discovery. There definitely seems to be some echoes in terms of overall algorithmic strategy.", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces Regioned Episodic Reinforcement Learning (RERL), which partitions the state space by generating a diverse set of goals and then explores the state space by learning policies that reach those goals. This idea is a combination of episodic memory techniques and “goal-oriented” reinforcement learning. 

After the authors’ responses and the discussion phase, all reviewers converged to recommending the rejection of this paper. The main concerns regarding this paper are:

* Presentation. The proposed approach is not that well justified, some of the claims in the paper are quite imprecise, and there’s relevant related work missing.
* Evaluation. The evaluation sometimes feels rushed and is not held in a diverse enough set of tasks, not capturing important properties one would want to capture.

I recommend the authors to pay close attention to presentation, as well as the experiments and analysis in order to make the paper stronger.

Decision: Reject