Reachability Traces for Curriculum Design in Reinforcement Learning
Authors: Thommen Karimpanal George
Majid Abdolshah
Hung Le
Santu Rana
Sunil Gupta
Truyen Tran
Svetha Venkatesh
Venue: ICLR 2022 Submitted (2022)
Keywords: reinforcement learning
curriculum learning
sparse rewards

Abstract: The objective in goal-based reinforcement learning is to learn a policy to reach a particular goal state within the environment. However, the underlying reward function may be too sparse for the agent to efficiently learn useful behaviors. Recent studies have demonstrated that reward sparsity can be overcome by instead learning a curriculum of simpler subtasks. In this work, we design an agent's curriculum by focusing on the aspect of goal reachability, and introduce the idea of a reachability trace, which is used as a basis to determine a sequence of intermediate subgoals to guide the agent towards its primary goal. We discuss several properties of the trace function, and in addition, validate our proposed approach empirically in a range of environments, while comparing its performance against appropriate baselines.

Under review as a conference paper at ICLR 2022
REACHABILITY TRACES FOR CURRICULUM DESIGN IN REINFORCEMENT LEARNING
Anonymous authors Paper under double-blind review
ABSTRACT
The objective in goal-based reinforcement learning is to learn policy reach a particular goal state within the environment. However, the underlying reward function may be too sparse for the agent efficiently learn useful behaviors. Recent studies have demonstrated that reward sparsity can be overcome by instead learning a curriculum of simpler subtasks. In this work, we design an agent's 'ss curriculum by focusing on the aspect of goal reachability, and introduce the idea of reachability trace, which used as a basis to determine a sequence of intermediate subgoals guide the agent towards its primary goal. We discuss several properties of the trace function, and in addition, validate our proposed approach empirically in a range of environments, while comparing its performance against appropriate basclines.
INTRODUCTION
Reinforcement learning (RL) (Sutton & Barto, 1998) has been successfully used to train agents in domains such roboties (Zhu et al., 2019), Atari games (Mnih et al., 2015) and other complex games (Silver et al., 2018). The universal principle underpinning these applications is the maximization of the long term expected rewards that the agent accumulates each interaction, the agent receives a numerical reward, which is (generally) directly or indirectly specified by a human user. The design of such reward functions is critical, as fundamentally affects both the rate of learning (Matignon et al., 2006), as well as the type of behaviors learned.
interacts with its environment. Following
it deprives the agent of the necessary feedback required to improve its behavior. This has been a widely studied problem in RL, and although several potential solutions (Ng et al., 1999; Vecerik et al., 2017: Narvekar al., 2020) have been proposed, it remains an active area of research.
Specifically, a sparse reward function makes learning challenging,
Apart from sparsity, the reward function could also suffer from improper specifications, such as inappropriately chosen reward values for certain states or actions, which could distract the agent from its intended task. The consequences of such mis-specifications have been recorded in works such as Burda et al. (2018), where the RL agent, rewarded for curious behaviors, was shown to become distracted from its original task due to local sources of entropy (A TV with randomly changing channels). Similar effects have also been observed in Clark & Amodei (2016), where the agent, tasked with safely completing a boat race circuit, unexpectedly exploited the improperly designed reward function, and learned undesirable behaviors.
In this work, we propose the idea of reachability traces, which is based solely on the reachability of the goal state, and is independent of other aspects of the reward function. Similar the idea of eligibility traces (Singh & Sutton, 1996) in classical RL, reachability traces model the temporal closeness (i.e., number of steps the goal) of states/state-action pairs leading to the goal by assigning diminishing reachability values (traces) to these states, looking backwards from the goal state. These reachability values are approximated through reachability trace function, which is realized through a simple feedforward neural network, updated online during learning. We also show that alternatively, reachability traces could be learned using an MDP (Markov Decision Process) framework (Puterman, 2014), guaranteeing its convergence in tabular environments. Once learned, the reachability trace provides an indication of the temporal closeness to the goal state, which is used to autonomously determine sequence of achievable subgoals, which are subsequently learned. The sequence of subgoals are chosen in increasing order of their reachability trace values, which ensures that subgoals appearing later in the sequence temporally closer to the goal state, and thus have higher chance

---

Under review as a conference paper at ICLR 2022
of reaching the goal. The corresponding subpolicies, once learned, are used to provide the agent with action advice (Fachamtidis et al., 2019), thereby guiding it towards the goal region. The use of action advice (accompanied by a non-zero probability of random exploration) to guide our off- off-policy agent implies the preservation of its convergence properties in tabular environments. We demonstrate our approach in sparse (discrete as well continuous) goal based RL tasks and compare its performance against several other baselines. We also discuss and empirically demonstrate other use cases of reachability traces, such as in environments with poorly designed reward functions. In summary, the main contributions of this work are:
The idea reachability traces to model the temporal closeness to the goal.
A framework for automatically discovering and learning reachable subgoals.
An empirical comparison of our proposed approach to other baselines in variety of reward sparse environmnents.
2 REACHABILITY TRACES
In goal based tasks, the aim of the agent to learn policy to reach a predetermined goal state. Depending the reward function in question, the probability of reaching such goal state may or may not be correlated with the (action-) value function of the agent. This is because the value function, which is solely designed to maximize the expected return, does not explicitly depend on goal state visits. For example, value function based learning would need to account for non- goal rewards. which (if improperly specified) could distract the agent from its intended task (Burda et al., 2018; Clark& & Amodei, 2016). Particularly in environments where the goal rewards are sparse, we posit that it is more beneficial exploit the rare trajectories that lead to the goal state, by learning about their goal-reaching properties, and subsequently using this knowledge to guide the agent's ' exploration. We posit that this goal-reaching property be characterized through reachability traces, which is solely based on the temporal distance to the goal state under the agent's behavior policy.
In classical RL, concept that models the idea of temporal closeness eligibility traces (Singh Sutton, 1996). Although the primary motivation behind eligibility traces was to address the credit assignment problem, was designed in a way that states/state-action pairs that were temporally more closely related to an event (a state or action), were assigned higher trace values compared to those that were temporally further away. Here, we use a similar idea to build a reachability trace function using historically successful trajectories. Unlike eligibility traces, reachability traces are learned as a neural network and are concerned solely with reaching the goal state, and modeling the temporal distance to the goal, which in this work, is used evaluate the suitability of potential subgoals.
Assuming a behavior policy æ, we consider a successful trajectory Ts- = (tt....tkkk ...ttN } which terminates at St+N (goal state). For each $+++ Ts, we assign a reachability trace label e, ($14s) as:
ex (s = N co
where eg (set to 1) is the highest possible trace label and À (0 < A < 1) is the trace decay parameter. It to be noted that traces are updated looking backwards from the terminal/goal state as per Equation 1. Trace labels are assigned to ensure that states temporally closer to the goal state are associated with higher trace values, and those further away are associated with lower values. States in unsuccessful trajectories are assigned a trace label of O. These assigned trace labels are then be used to learn a reachability trace function dz (s) s + e, (s), which maps states (or state-action pairs) to their corresponding trace labels. Given enough successful trajectories, the learned reachability trace (ss) would converge to the expected trace value:
=x co]
Our assumption is that prior to learning the trace function, our agent encounters at least one successful trajectory. We do not require that this trajectory be optimal; only that enounters the goal state G and terminates. As obtain trace labels for multiple states upon visiting the goal, even a single successful trajectory could help build a rough estimate of the trace function. Our approach is also suitable be used in the availability of (suboptimal) demonstrations, described in Appendix D.
2

---

Under review as a conference paper at ICLR 2022
((s)
H
Adg
X 8g
0
Figure Illustration reachability trace network that maps states on the successful trajectory
(left) of a hypothetical navigation environment to their trace labels.
Algorithm Learning a reachability trace function
Input:
2: Trace decay parameter X, stored trajectory length L, trace function @(s, f), goal state G
3: Initialize state 80, successful trace buffer Døs and unsuccessful trace buffer Day
4: Output: Learned trace function Ø
5: while True
6: Interact with environment: take action a, observe s
7: Store latest states
8: if Successful episode (G is reached) then
9: for i from 1 to I. do
C; = X 11: end for
10:
Move the labels and corresponding states into the buffer Døg
13: else
for from 1 to L do = end for
15:
17:
Move the trace labels and corresponding states into the buffer Dau end if
18:
19:
Sample set of state and trace labels (#samp: Esamp), obtaining each sample from either Dos Deu with equal probability
20:
Minimize (Esamp ((ssamp; 0))² with respect to trace network parameters
21:
+-= s'
22:
end while
Since the trace function is indicative of closeness the goal state G, is used basis for generating subsequent subgoals that are likely to be closer to G. In this work, the reachability trace is realized through simple feedforward neural network, trained data of states and corresponding trace labels generated from successful and unsuccessful trajectories, which are stored in separate buffers. The steps to be followed learn trace function have been described in Algorithm 1. Here, successful and unsuccessful trajectories are sampled with equal probability, which causes the learned trace to be biased estimate of that mentioned in Equation 2. Despite this bias, we find that the learned reachability trace serves as an approximate measure of temporal proximity, and is still a useful basis for selecting subgoals. In addition, our approach does not require generated suboals lie on the optimal path, the use of this biased estimate is justified. Although reachability traces have been described only in terms of states (for the sake of simplicity), similar the case eligibility traces, can also be extended to state-action pairs (ó.,, (s,a)). a)).
SUBGOAL GENERATION AND CURRICULUM BUILDING
Once an appropriate trace function & has been learned, we use to identify and learn potential subgoals of increasing difficulty. The intuition is that when goal rewards sparse, high value
3

---

Under review as a conference paper at ICLR 2022
of ((s) or Ó(s, a) indicates that the state is temporally close the goal state, and thus may be less reachable (from the starting state), while a low & value may indicate that the state is further away from the goal state (and thus temporally closer to the starting state), and thus may consitute an easier subgoal to be learned. In this work, we treat this temporal proximity as a proxy for subgoal difficulty, basis for building task curriculum (Portelas et al., 2020; Narvekar al., 2020) in
and use it sparse reward problems. The idea is to first learn simple subgoals (low Φ) and progressively move to more difficult ones till the main task is solved.
We consider sparse-reward MDP (main task) M - R, 50), with state space S, action space A, reward function R, and transition function T. sy and G represent the start and terminal goal states respecitvely, Under the standard learning scenario, learning an optimal policy ग' to solve this sparse reward MDP may become prohibitively sample inefficient. However, if we have learned a trace function Φ, .M can be simplified into a sequence of subtasks M = [M....M....M. such that each M, E M a subtask MDP M, = (S, A, R, T;, 9s: } sharing the same state-action space, with its own reward function R, start state 5; and terminal goal state g,. The starting state for the subsequent subtask is set as the goal state of the previous one; that is, 8; = 9i-1- The transition function T; is assumed to be identical to T, except that as per T3 Ii is terminal, whereas T assumes termination at G. The subtask sequence is such that for any two subtasks M, M,. where j > i, ((g)) > (oo(gg)). ). Lo (2 1) is a subgoal trace scaling factor. Choosing large values of La would result in subgoals spaced temporally farther, while smaller values of La could be expected to return subgoals that are temporally close to one another. Guidelines for selecting to are described in Appendix B. The reward (s) corresponding to the reward function R& for each subtask is binary, such that:
ry (;()) = {
s= gi otherwise
In order identify subgoals online, the agent is allowed to interact with the environment in an episodic manner, till it encounters a state Smar corresponding to the highest ó value experienced during the episode, which also exceeds the trace value of the latest subgoal state gi- That is, if Φ(smaz) > tgp();) Sman is considered to be the new subgoal (9i4-),, and accordingly, subtask M,+1 is generated with high rewards corresponding to state gi+-1, and 0 rewards for all other states. For each such subtask, corresponding subpolicy is learned, following which the same process is repeated to generate the next subtask, and so on till the goal state G is reached. The fact that only previously visited states chosen as subgoals ensures that the chosen subgoals are indeed reachable. At this point, the main task M would be decomposed into several subtasks consisting of subgoals of progressively increasing difficulty (Figure 6, Appendix B), whose subpolicies are learned in sequence. Although these subpolicies are used to guide the agent towards the goal (described in Section 4), they can also potentially be reused (Fernández & Veloso, 2006) aid transfer learning (Appendix E). The processes involved for subgoal generation and curriculum building are described in Algorithm 2.
CURRICULUM GUIDED LEARNING
Once a curriculum C' of subpolicies have been learned as described in Algorithm 2, the learned subpolicies are simply used in sequence to guide the exploration of the agent till the goal state G is reached. It is to be noted that although the approach described in Algorithm 2 generates subgoals of increasing difficulty/trace values, does not guarantee that they lie on the optimal path to the goal state G. However, in this work, as the subpolicies only serve to guide the agent via action advice, it is guaranteed to eventually converge (in the tabular case) to the optimal policy.
To learn the main policy, the corresponding Q-function Q(s, a) is updated online with off policy updates (DQN or DDPG for instance), using guided actions from the learned subpolicies Q
The process of action advising involves extracting greedy actions from the relevant subpolicy Qaub- and executing it with a probability e (while maintaining a small non-zero probability 8 >> 0 of taking random actions), and otherwise acting greedily with respect to Q. The requirement of 6 > 0 is enforced to ensure sufficient exploration in the case of highly suboptimal subgoals. Once the subgoal of the corresponding subpolicy is reached, the agent receives subsequent advice from the next subpolicy, and so on till the main goal G is reached, with Q(s, a) being updated with off-po updates at every step. The overall curriculum- guided learning is described in Algorithm 3.
4

---

Under review as a conference paper at ICLR 2022
Algorithm 2 Subgoal generation and curriculum building
Input:
2: discount factor 7/ goal state G, subgoal trace scaling factor fg. No. of episodes Ne
3: state So, Initialize agent Q- function Q a), Full curriculum found t- 0, Opree Initialize curriculum C, initialize list of all subgoal states 9alt
4: Output: Curriculum C, subgoal states golt
5: while _cc_rriccuuu__ooiii
= do
6: Interact with environment: take action a, observe r,
7: Update ((s,a)
8: if G is reached then
Update trace function (fs,0) using Algorithm 10: end if
9:
Initialize subpolicy Q-function Quubi subgoal_ for ranging from to N₂ do
12:
if subgoal_ found == 0 then
14:
Execute episode i
Find state Smar from episode i corr. to maximum & value if (8mmax) ) > L.@0pre then
16:
< 9: 6- 8mazi subgoal_founn 1: < Ioll U g Oreev ((5max)
18:
19:
if == G then
20:
end ltt__crrrcuuum_fouree
Full
21:
22:
end if
23:
else
Update Qaub during episode
25:
end if
end for
27:
C C-CQQ.u.
end while
(a)
(b)
(c)
(d)
(e)
Figure 2: The (a) Gridworld environment (b) U-shaped, (c) S-shaped, (d) w-shheed and (c) II-shaped maze environments used for evaluation, where the red marker denotes the goal position.
5 EXPERIMENTS
We evaluate our proposed approach first a simple tabular environment shown in Figure (a), followed by number of continuous state and continuous action enviromments shown in Figure (b)-(e), which were previously also used in (Chane-Sane et al., 2021).
The environment in Figure 2 (a) consists of Q-lennning (Watkins, 1989) agent starting at the state 8g, with a goal state G. The agent can take actions to move in the four cardinal directions (up, down, left and right). It receives a reward of () for each transition, except those that lead to the terminal goal state, for which it receives a reward of +1. 1. When it encounters an obstacle, the agent's state remains unchanged. Episodes terminate after fixed episode horizon upon reaching the goal state. The agent interacts with the world using an e-greedy strategy, with a linearly decaying e, and the agent's state is reset after each episode. Other associated hyperparameters H. In this sparse reward setting, our approach first interacts with the environment till the goal state is visited, following which it learns (Algorithm 1) trace function (depicted in Figure (center). Using
specified in Appendix
5

---

Under review as a conference paper at ICLR 2022
Algorithm 3 Curriculum-based action advising
Input:
2: Learned curriculum C, maximum steps Na agent's Q- function (ss, a), goal state G, set of
subgoals 9all. goal index
3: state = So, step t 0, Quub C(O), [a4[k]
4: Output: Optimal -fuunctio Q*
5: while slep S Nman do
6: if not found then
7: Get action asub from Qeub
8: e>rand() then
9:
Execute asub (random exploration with small probability 6)
10:
else
Greedy action w.r.t. Q
12:
end if
Observe r, s' resulting from the executed action
14:
step step +
else
16:
k k +
and = C(k),, g Iau [k] end if
18:
19:
Update Q using an off-policy update (Eg: Q Q-learning)
20:
if G is reached then
21:
s + Su
22:
else
23:
8 +- 5
end if
25:
end while
Figure 3: The trace function (center) is used to identify subgoals 90-91 and g2. corresponding to which policies go ae and ga are learned. The colors respresent the trace values (for the center image) or scaled value functions (for images corresponding to goo Tg, and gT.)
this trace function, we generate subgoals (Algorithm 2) based on the temporal closeness to the goal state. The corresponding subpolicies (visualized Figure 3) are learned and subsequently used to guide the actions of the agent (Algorithm 3).
As depicted in Figure 3 (a), our approach is effective at obtaining high rewards for these environments where higher rewards are associated with higher frequency of goal state visits. As seen in the figure, standard Q-learning performs poorly in this environment due to its reward-sparg nature. Other approaches such Episodic Backward Update (EBU) (Lee al., 2019) performs relatively better, due to quicker credit assignment facilitated by the backward nature of the updates. Prioritized Experience Replay (PER) (Schaul et al., 2016) benefits from sequencing the transitions be replayed.

---

Under review as a conference paper at ICLR 2022
0.08
Trace oukum (Oun))
Traée Curriculum (0ur)
Q leamiing
DUMS
Average reward per step
0.05
RS
EBU
Average reward step
PER
KS
PER
0.05
0.00
o.
8.02
-0.05
-010
0.02
Steps
Steps
105
(b)
Figure 4: Performances in (a) the gridworld environment and (b) the U-Maze environment over 10 and 5 trials respectively.
Trace Curriculum (Ours)
DDPG/Q-leaming
R1S
PER
EBU
Gridwoeld
30725
26744
6698
12334
U-Maze
18791
10403
12200
8941
S Maze
1280
1022
w-Maze
2287
IT.Mare
1262
102
1273
186
Table 1: Average goal visits across environments and baselines at the end of training for the Gridworld (10 trials) and Point Mujoco Maze (5 trials) environments. Bold numbers indicate best performance.
The approach of Reinforcement learning with Imagined Subgoals (RIS) (Chane-Sane et al., 2021) performs well, as similar to our approach, it also generates a sequence subgoals that lead towards the goal state. However, out based on the reachability trace function, whose goal-oriented nature, coupled with the backward propagation of the reachability values results in superior performance.
approach benefits from the fact that the subgoal generation is carried
Similar results can be seen in the Point U-Maze environment, where a DDPG agent (Lillicrap et al., 2016) receives reward of for reaching the goal state, and penalty of -0.1 for all other transitions. The EBU baseline, designed for discrete action environments, was omitted for the maze tasks. The performance of the agent (in terms of total goal visits) in all the environments and across other baselines is also shown in Table 3. The performance plots for other environments are shown in Appendix J. These results suggest that our algorithm is well-suited handle sparse rewards, even relative to other competing curriculum learning approaches.
5.1 THE CASE OF POORLY DESIGNED REWARD FUNCTIONS
So far, we have discussed the utility of reachability traces in sol sparse reward problems. However, they could also be to useful in specific scenarios such dealing with poorly designed reward functions (which could lead the 'couch potato' effect (Burda al., 2018)). We consider another navigation environment with goal G shown in Figure 5 (a). However, apart from the goal rewards at G. the agent also receives receives small positive reward the non-terminal state sT- When this reward is set to high enough value. it distracts reward maximizing agents learn policies that move towards SNT, resulting in a low frequency of goal state visits, which is the actual metric of interest. The "distractive' reward is assumed be caused due to mis-specification of the reward either due to human error or due to unforeseen properties of the simulation environment.
In the environment of Figure 5 (a), the agent receives reward of after which it terminates. The "distraction' reward for visiting state snt is set to 0.02, and for all other transitions, the agent receives living penalty of -0.5. With episode horizon of 200 steps and 7 strictly reward maximizing

---

Under review as a conference paper at ICLR 2022
0.32
Trace Curriculum
0.10
Q-leanning
ANY
Averatge goal visits per
RIS
0.00
0.00
0.00
0.4
0.8
Steps
(a)
(b)
Figure 5: (a) Environment with starting state So. goal G and non-ten non-terminal rewards at SNT, and (b)
corresponding performance over 5 trials.
agents move towards 8NT and remain there, receiving reward of 0.02 until the episode terminates (optimal episode return= 3.65). In contrast to this, the shortest path towards the goal state would only result in return of -1. 1. This causes reward maximizing agents become distracted, and learn policies that lead them towards SNT. However, with the use reachability traces, the agent primarily concerned with task completion (visiting the goal state), and result, ignores 8NT distrative reward. As our approach relies on the reachability trace function generate subgoals, it increases the likelihood that subsequently generated subgoals lie temporally closer to the goal state. This is not the case even in other soal-conditioned approaches like RIS, for example, where subgoal generation is dependent on the agent's value function. As result, the RIS baseline tends to generate subgoals in high value regions (i.e., around sNT) and hence experiences noisy performance initially. However, RIS being goal-conditioned approach, eventually discovers paths leading to the goal state. For these reasons, our approach results in faster and more stable learning in the environment in Figure 5 (a), leading a higher frequency of goal state visits.
despite the presence
6 RELATED WORK
Several works have attempted to resolve the sparse reward problem. Reward shaping (Ng et al., 1999) was among the earliest of such approaches wherein the original reward function the agent was made less sparse by appending it with special shaping term which left the resulting policy unaffected. Directed and curiosity- based exploration (Thrun, 1992; Burda et al., 2018: Savinov al., 2018) is another family of approaches designed to speed up learning in general, including in reward-sparse environments. However, these methods are generally designed for better exploration, and not specifically for goal-directed behaviors.
For long-horizon tasks, hierarchical RL (Dayan & Hinton, 1993; Wiering & Schmidhuber, 1997; Levy et al., 2017; Zhang al., 2021) a suitable approach, where often, high level policy controls the execution of several low-level intermediate subpolicies. However, as mentioned in Nachum al. (2018), the joint learning of these policies can be problematic, and lead non-stationarity and instability. Although we follow similar approach of decomposing a goal into multiple subgoals, we use the corresponding subpolicies only guide the learning of the main policy.
The subgoals generated in our approach is based on the trace function, whose trace values are propagated backwards following successful trajectory. Lee et (2019) proposed similar backward updates in discrete action environments, but the updates were performed on the action value function itself. Although these backward updates were demonstrated to result in faster learning in environments with discrete action spaces, they failed to account for reachability, making them susceptible to failure in environments with poorly designed rewards. Similar to our approach, Savinov et al. (2018) explored the idea of reachability, where neural network was used to estimate the number of steps separating the current observation from past observations. This prediction was used to generate a bonus reward encourage exploration into novel regions. Our proposed reachability traces approach,
8

---

Under review as a conference paper at ICLR 2022
although based similar ideas of modeling temporal closeness, is specifically designed to achieve goal-directed behaviors, while also serving as a basis for the choice of subgoal states.
Among curriculum learning approaches. RIS (Chane-Sane et al., 2021) is the most closely related. The authors aim to Iearn a high-level policy by generating subgoals based on a value function as a reachability metrie. The idea is to pick intermediate goal states that are halfway (as per the value function distance metric) to the goal location. Although our approach also relies on a higher-level function determine subgoals, we choose our subgoals based on the learned trace function, which benefits from the backward propagation of trace values, making it a better choice compared to the value function. Choosing subgoals based on value functions could also fail in cases where the reward function is poorly designed. The trace function, which is based on reachability, does not suffer from such issues. In addition, our subgoal selection strategy to pick reachable state with a trace value that is higher than that of the previous subgoal. We believe that this reachability-fouseee approach is more grounded than the arbitrary criterion of halfway distances.
Other related curriculum learning approaches include Florensa et al. (2018), where subgoals were generated to produce returns between arbitrarily chosen maximum and minimum return thresholds. Apart from subgoal sequencing, algorithms such as prioritized experience replay (Schaul et al., 2016) could also be considered a form of curriculum learning, where the transition samples are sequenced.
7
CONCLUSION
We presented reachability trace functions, novel approach for designing a task curriculum to overcome problems posed by sparse rewards in goal based tasks. We showed how this function approximates the temporal closeness to the goal state, and described how it can be used to construct task curriculum. Through several discrete as well and continuous maze navigation environments, we empirically demonstrated the ability of our approach to efficiently handle sparse rewards. Finally, we also briefly discussed and empirically demonstrated an alternative use-case of our approach handling environments with poorly designed reward functions, where reward maximizing agents fail.
REFERENCES
Marcin Andrychowicz. Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremba. Hindsight experience replay. In Advances in Neural Information Processing Systems, pp. 5048-5058, 2017.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym. arXiv preprint arXiv: 540, 2016.
Yuri Burda, Harri Edwards, Deepak Pathak, Amos Storkey, Trevor Darrell, and Alexei Efros. Large-scale study of curiosity-driven learning. International Conference on Learning Representations, 2018.
Elliot Chane-Sane, Cordelia Schmid, and Ivan Laptev. Goal-conditioned reinforcement learning with imagined subgoals. In International Conference on Machine Learning, pp. 1430-1440. PMLR, 2021.
Jack Clark and Dario Amodei. Faulty reward functions in the wild. Internet: hmps://blog. openai. com/fiuult- reward-finctionn 2016.
P Dayan and GE Hinton. Feudal reinforcement learning. nips(pp. 271-278), 1993.
Anestis Fachantidis, Matthew E. Taylor, and Ioannis Vlahavas. Learning teach reinforcement learning agents. Machine Learning and Knowledge Extraction, 1(1):21-43 2019.
Fernándo Fernández and Manuela Veloso. Probabilistic policy reuse in reinforcement learning agent. In Proceedings of the fifth international joint conference on Autonomous agents and multiagent systems, pp. 720-727. ACM, 2006. URL http: //l acm.
Carlos Florensa, David Held, Xinyang Geng, and Pieter Abbeel. Automatic goal generation for reinforcement learning agents. In International conference on machine learning, pp. 1515-1528. PMLR, 2018
David Isele and Akansel Cosgun. Selective experience replay for lifelong learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.

---

Under review as a conference paper at ICLR 2022
Tommi Jaakkola, Michael I Jordan, and Satinder P Singh. On the convergence of stochastic iterative dynamic programming algorithms. Neural computation, 1800:1185-220 1994.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint arXiv: 1412.6980, 2014.
Su Young Lee, Sungik Choi, and Sac-Young Chung. Sample-efficient deep reinforcement learning via episodic backward update. In Proceedings of the 33rd International Conference Neural Information Processing Systems, pp. 2112-1121, 2019.
Andrew Levy, George Konidaris, Robert Platt, and Kate Saenko. Learning multi-level hierarchies with hindsight. arXiv preprint (eXiv:/712.00944/ 2017.
Timothy P Lillicrap. Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez. Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. ICLR (Poster), 2016.
Laëtitia Matignon, Guillaume J Laurent, and Nadine Le Fort-Piat. Reward function and initial values: Better choices for accelerated goal-directed reinforcement learning. In International Conference on Artificial Neural Networks, pp. 840-849 (400-84..9. Springer, 2006.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei Rusu, Joel Veness, Mare G Bellemare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. Nature, 518(7540):529, 2015.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. Advances in Neural Information Processing Systems, 31:3303-3313, 2018.
Sanmit Narvekar. Bei Peng, Mateo Leonetti, Jivko Sinapov, Matthew E Taylor, and Peter Stone. Curriculum learning for reinforcement learning domains: A framework and survey. arXiv preprint arXiv:2003. 049960 2020.
Andrew Y Ng. Daishi Harada, and Stuart Russell. Policy invariance under reward transformations: Theory and application reward shaping. In ICML, volume 99, pp. 278-287, 1999.
Rémy Portelas, Cédric Colas, Lilian Weng, Katja Hofmann, and Pierre-Yver Yves Oudeyer. Automatic curriculum learning for deep rl: A short survey, arXiv preprint 2033040003,4464, 2020.
Martin I. Puterman, Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
Nikolay Savinov, Anton Raichuk. Damien Vincent, Raphael Marinier, Mare Pollefeys. Timotyy Lillicrap. and Sylvain Gelly. Episodic curiosity through reachability. In International Conference on Learning Representations, 2018.
Tom Schaul, John Quan, Joannis Antonoglou, and David Silver. Prioritized experience replay. In International Conference on Learning Representations, pp- 1, Puerto Rico, 2016.
David Silver, Thomas Huhert, Julian Schritwieser, Toannis Antonoglou, Matthew Lai, Arthur Guez, Marc Lanctot, Laurent Sifre, Dharshan Kumaran, Thore Graepel, et al. A general reinforcement learning algorithm that masters chess, shogi, and go through self-play. Science, 362(6419):1 11164499):110-11440 140-1144, 144,, 2018.
Satinder P Singh and Richard S Sutton. Reinforcement learning with replacing eligibility traces. Machine learning, 22(1):123-158, 1996.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction, volume 1. MIT press Cambridge, 1998.
Sebastian B. Thrun. Efficient exploration in reinforcement learning. Technical report, 1992.
Mel Vecerik, Todd Hester, Jonathan Scholz, Fumin Wang, Olivier Pietquin, Bilal Piot, Nicolas Heess, Thomas Rothörl, Thomas Lampe, and Martin Riedmiller. Leveraging demonstrations for deep reinforcement learning on robotics problems with sparse rewards. arXiv preprint arXiv: /07.08777..08877 2017.
CJCH Watkins. Learningfrom delayed rewards. PhDthesis, Cambridge University, Cambridge, England, 1989.
Marco Wiering and Jürgen Schmidhuber. Hq-learning. Adaptive Behavior, 6(2):219-246, 1997.
Jesse Zhang, Haonan Yu, and Wei Xu. Hierarchical reinforcement learning by discovering intrinsic options. arXiv preprint arXiv:2 101.0621,, 2021.
Henry Zhu, Justin Yu, Abhishek Gupta, Dhruv Shah, Kristian Hartikainen, Avi Singh, Vikash Kumar, and Sergey Levine. The ingredients of real world robotic reinforcement learning. In International Conference on Learning Representations, 2019.
10

---

Under review as a conference paper at ICLR 2022

---

Under review as a conference paper at ICLR 2022
APPENDIX
A LEARNING THE REACHABILITY TRACE VIA REINFORCEMENT LEARNING
Although we described approximating the reachability trace function via a neural network, we note that it could also potentially be learned using a reinforcement learning approach.
The reachability trace function ((s) with trace decay parameter X and maximum trace label eo equivalent the optimal value function of an MDP Ma =,S,A, T, T,,,, so) with start state Su. goal state G, state space S, action space A, transition function TT and reward function Rs with binary rewards:
Proposition 1.
coo 8 ==G G ro(s)
otherwise
and converges to the optimal goal reaching policy with probability under standard convergence
conditions Σat a oc and Σ a, < co, where as is the learning rate hyperparameter at time step t
t=1 the value function update equation for solving Ma-
t=1
Proof. In RL, the value function (sx) associated with state 8, can be represented as the discounted sum of rewards (as generated by reward function R) obtained by following a policy π. That is:
V(s:) = Err + TT+t1 + t...'' rett + +... r++N]
rr is the terminal goal state reward, with all other transitions being associated with a reward of 0, and the agent reaches the goal at step & + N, the above relation would simplify
V (st) E
(4)
As the trace function is given by ((s)) (N%eol (Equation 2). we observe its similarity with Equation 4, and surmise that the optimal reachability function (0s) is equivalent to the optimal value function corresponding to hypothetical MDP with terminal reward eg and discount factor X. This interpretation allows reachability traces to also potentially be learned via standard RL algorithms. Doing so can guarantee that the learned reachability traces converge the optimal goal reaching policy (as the binary reward re is solely associated with reaching the goal state G), subject to standard
20
2o
convergence criteria Σ at = oo and Σ of < oo (Jaakkola et al., 1994). As analogous results can
t=1
[=1
function of state-action pairs, this interpretation allows the reachability traces o(s, a) of statc-action pairs to potentially be learned in an off-policy manner, in parallel with the learning of a policy corresponding to the agent's primary task. We note that learning the reachability trace in this manner would avoid the biases that would otherwise occur when learning the reachability trace. However, it may become infeasible to learn reward sparse environments. Methods such as replaying transitions associated with large rewards (Isele & Cosgun, 2018) could help counter this.
be obtained for traces when represented
B SELECTING THE SUBGOAL TRACE SCALING FACTOR to
As described Section our approach selects subsequent subgoals Inezt by comparing its trace value with that of the most recent subgoal 9cuer using the condition: o(Inezt) > tto(Sewrr). The scaling factor to thus must be set minimum value of to ensure that the subsequent subgoal corresponds to higher reachability trace value. Increasing values of f.g. would tend to produce subgoals that are further apart from each other, causing the total number of subgoals (and subpolicies) to drop in numbers. This effect is observed in Figure 7, where lower scaling factors ls are shown (over 20 trials in the U-Maze environment) to generally produce a larger number of subpolicies (which implies many closely spaced subgoals). Although lower number of subgoals is desirable, using to > 1 bears a risk of agents being unable to find states satisfying the required reachability trace threshold. In such scenarios, inaccuracies in the approximated reachability trace may get exploited
12

---

Under review as a conference paper at ICLR 2022
1st Subgool Subpool Sungral
Figure Distribution subgoals over 30 runs the U-Maze environment
4-12
No. of occurrences
12.
No. of subpolicies
Figure 7: Number of subpolicies learned using reachability traces over 20 runs each for different subgoal trace scaling factor La in the U-Maze environment
(for example, a subgoal with high but inaccurate reachability trace could get selected), leading to poor distribution of subgoals. Hence, despite the potential advantages of using high l.. we suggest the use of scaling factor to 1.
C SENSITIVITY TO STORED TRAJECTORY LENGTH
We ablate the effect of the stored trajectory length parameter I. of Algorithm in the environment shown in Figure 2 (a). As observed from Figure 8, increasing L accelerates learning, This probably occurs due the quicker learning of the trace function owing to training on longer trajectories.
D AVAILABILITY OF DEMONSTRATIONS
As noted Section 2, our approach relies on there being at least one successful trajectory that reaches the goal state. Hence, our method can also be used in the case of available demonstrations. Such demonstrations need not be optimal, and could be fed in either manually, through other learning approaches or through random exploration. Figure shows the comparison of demonstration based (using a single successful demonstration trajectory) vs demonstration for the environment Figure 2 (a). As evident from Figure 9, our algorithm performs marginally better in the presence of demonstrations, owing to the fact that the provided demonstrations are used to construct the trace function as soon as the agent starts interacting with the environment. This is in contrast the demonstration free case, where the agent is required to first discover successful trajectories through interaction. Nevertheless, our approach can be used either with or without demonstrations. All results reported in the main text correspond learning without demonstrations.
versions of our algorithm
13

---

Under review as a conference paper at ICLR 2022
L=10
Average reward per step
L-40
0.05
0.04
0.03
0.02
Steps
1ed
Figure 8: Variation of performance with different stored trajectory lengths over trials
Curriculum
Traze Curricuuum with damonatrctions
0.06
Average reward
0.05
0.04
0.03
0.02
Steps
led
Figure 9: Comparison our approach with and without the availability of demonstrations over 10 trials in the gridworld environment of Figure (a).
14

---

Since the reachability traces are essentially indicative of the temporal closeness of a state to the goal state, its value increases for states that lie temporally closer to the goal state. This nature of the reachability trace function can be exploited by using it as an exploration bonus, which can be very effective in sparse-rewe environment reward at state given by r(s) is augmented with the trace function Ø(s), which acts as an exploration bonus, such that the total reward r(s) + Φ(s). As observed from the figure, the Under review as a conference paper at ICLR 2022
$o
Average reward per step
0.04
0.02
Traster (PP)
Q-leaming
100
200
500
600
Steps
le]
(a)
(b)
Figure 10: (a) The environment from Figure 2(a) with new goal location and (b) comparison of the corresponding performances of standard Q-learning vs the policy reuse baseline (PPR), where subpolicies from Figure 3 reused.
E REUSE OF LEARNED SUBPOLICIES
Once our agent uses the trace function to identify and learn subgoals, the corresponding subpolicies used guide the agent's s goal reaching policy. Although is the main focus of this work, these subpolicies could also serve as source policies for policy reuse scenario. Figure 10 depicts such case, where the goal state in Figure 2 (a) is changed, with all other environment properties preserved. In such a case, we demonstrate that reusing previously learned subpolicies through probabilistic policy reuse (Fernández & Veloso, 2006) can significantly accelerate learning. Although this type of reuse is possible even with subpolicies learned via other curriculum learning approaches, believe our method enables the learning of subpolicies whose subgoals are temporally sufficiently apart, making the corresponding subpolicies considerably different from each other. We contend that this could potentially be beneficial for learning (via policy reuse) a wide variety of tasks.
F USING REACHABILITY TRACES AS AN EXPLORATION BONUS
scenarios. Figure/ 11 shows the performance an agent that whose
agent with the exploration bonus ((s) is able to significantly outperform other learning approaches, indicating that the trace function also serves as a useful exploration bonus. We note that the rewards
shown in the figure only correspond to the environment rewards obtained by the agent.
G VISUALIZATION OF TRACES
Figures 12 and 13 depict the visualization of traces the point UMaze and in the MountainCar-vo environment of OpenAl gym (Brockman et al., 2016). As evident from the figures, the trace values increase with proximity to the terminal goal location.
15

---

Under review as a conference paper at ICLR 2022
0.10
Q-learning
Average reward per step
0.08
EBU
PER
Reachability trace as exploration bonus
0.06
20
Steps
1e4
Figure 11: The performance of reachability traces used as an exploration bonus, compared to other approaches averaged over 10 trials in the gridworld environment of Figure 2 (a).
189
Figure 12: (b) Visualization of traces in the (a) UMaze Environment
4.5
P23t00
(a)
Figure 13: (b) Visualization of traces in the (a) Mountain Car-v0 environment
Hyperparameters
Gridworld
Point U-Maze
Other Point mazes
learning rate
0.05
le
5
le
5
discount factor 7
0.95
0.95
0.95
Episode horizon //
200
500
50K
Total steps
le6
2e5
le6
Stored trajectory length
40
2K
Size of trace buffer
500
300
10K
Subgoal trace scaling factor io
Epochs for training ø
100
10K
10K
Trace decay parameter
0.9
0.99
0.9999
Table 2: Hyperparameter values for approach.
16

---

Under review as a conference paper at ICLR 2022
Traces Curicuuuum (Ours)
4.00
RI5
DOPG
CWNAA 5a0 3013
2.322
PER
-0.01
StNck
(a)
(b)
(c)
Figure 14: Performances in the point (a) S-Maze, (b) w- sa-a and (c) π æ-Maze environment overs over trials.
H HYPERPARAMETER SETTINGS
In these environments, the exploration parameter decayed linearly from 1 to a minimum of 0.1. The DDPG base agent used in the continuous maze tasks used the Adam optimizer (Kingma & Ba, 2014) and a critic and target networks as multi-layer perceptrons of 3 and 2 layers respectively, with the former having 1024, 512 and 300 nodes in its three layers, and the latter with 512 and 128 nodes in its layers. The polyak averaging hyperparameter used was set to T = 0.01. For the PER baseline, we used proportional prioritization with a temperature parameter of 0.01. Each continuous maze environment was performed on an Nvidia Tesla V100 (32GB) GPU, and on average, took about 6 hours per trial for U-Maze and about 12 hours per trial for the other continuous mazes.
The trace network used is feedforward neural network with two hidden relu layers, each containing 128 nodes. The optimizer used is Adam with a learning rate of le 3.
I OTHER IMPLEMENTATION DETAILS
Efficient Trace Updates:As per the procedures outline in Algorithm 1, we train the trace network at each step. However, this may become prohibitively expensive, and thus impractical in terms of wall-clock time. In order to counter this issue, we keep track of the latest interaction that led the goal state, at which point we set spiking signal to 1. This spiking signal is then subsequently decayed exponentially as G+1 = dL,, where d, the decay rate set 0.9. The trace network is then updated with a probability Ç, such that immediately after goal state visit, the trace network is updated frequently, following which it is updated progressively less frequently.
Off-policy updates: As our learning agent is updated in off-policy manner, its action values can simultaneuosly be updated parallel during the environment interactions Algorithm and 2, and not just in Algorithm 3.
Curriculum guidance:In Algorithm 3, although we use a fixed value of e = 0.1, as per standard practice, could be set to decay with time, decreasing the reliance subpolicies with more learning updates. A potential drawback of this strategy is that the agent may receive less frequent advice from subpolicies further down the sequence. However, the agent, having been guided by subpoliciies earlier in the sequence, likely to be closer to the goal state at this stage, and is thus less likely to be affected by the low frequency of advice.
Baseline implementation: For fair comparison, in all our experiments, the RIS baselines only used the subgoal generation strategy from Chane-Sane et al. (2021) without the use of hindsight experience replay (Andrychowicz et al., 2017).
J OTHER PERFORMANCES
Figures 14 (a)-(c) show the performance plots in other point Mujoco maze environments (S-Maze, w-Maze and -Mzze).
17

---

Under review as a conference paper at ICLR 2022
Thace Curriculam (Ours)
DDPG/Q-Jearning
RIS
PER
Gridworld
0.052 + 0.006
1s 5 1 le
0.037 1: 0.006
0.014 = 0.004
0.031 : 2e 5
U-Maze
0.061 + 0.004
-0.014 0.011
0.046 0.024
-0.035 = 0.024
S-Maze
-0.0933 + 3e
-0.0999
0.0976 1: 6c
-..0988 + 9c 5
w Maze
0.0937 1 7c 4
-0.0999 1: 9c
0.0958 1. 2c
0.0995 1 2c
II-Maze
0.0064 + Ge
-0,0999
0..996
00.0997 + 2e
Table Average reward per step (meantstandard deviation) across environments and baselines the end of training for the Gridworld (10 trials) and Point Mujoco Maze (5 trials) environments. The bold values indicate the best performance. The averaging window size used for U-Maze is 1000, and for other mazes. it is 10000.
18


Reviews:
[{"review_id": "iVdaIImeec0", "reviewer": "Reviewer_WVWS", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Using the Neurips rubrics:\n\nOriginality: To me the idea of using reachability traces seemed reasonably novel, but not a stunning new insight. It is a natural follwup to the idea of using the value functions to define sub-goals in the Chane-Shane paper, but connecting to reachability traces in the old RL literature is a non-trivial contribution. I am not an expert on the latest work in CL in RL so can't judge from that perspective. The authors did seem to survey the related work carefully and situated their work well within it as being a new approach. One minor novelty in the experimental section was the idea of experimenting with misspecified reward function.\n\nQuality/Correctness:  There are 2 problems:\n\na. Proposition 1 just seems wrong to me and the statement of it kind of meaningless. The reachability trace is a function of the policy $\\pi$  and it's claimed to be equivalent to a \"solution\" (optimal value function?) of an MDP, without any policy specified [also what does \"converges to\" mean in this context? what sequence converges? ] . This can't be correct and looking at the proof, I think the error is clear.  The authors observe that 2 equations are \"similar\" but they are actually referencing 2 different policies, 1 the original policy and the other is the optimal policy for this MDP. The expectations will be different. The best that you can say is that the trace function is the value function for the exploratory policy $\\pi$. The rest of the discussion in the \"proof\" isn't really a proof  but a discussion which doesnt apply anymore since we aren't talking about an optimal policy.\n\nb. I think the kind of tasks that this is being applied to are making it much easier for this CL method. In all the environments there is \"topologically\" speaking one path from start to goal. there are no loops to choose between. So what this means is that the first reachability trace path will lay out roughly the right path to the goal. In loopy environments I suspect you will find more cases of CL hurting. Fig 5a has a loop, but there's only one, and it looks very symmetrical so either path would lead to a good goal policy.\n\nc. The thoroughness of experiments is maybe slightly below par for an ICLR paper. I would have liked to see a little more variety in problem types (rather than just gridworld), also a few more variations e.g. what happens if you use more than one trace at a time?\n\nA counter to the argument from authors that their method works better when rewards are mis-specified: wouldn't RIS then work better when rewards are well-specified?\n\nClarity: Mostly clear. One clarification I would appreciate is the perceived role the reward function in a setting like this. If you have a goal, but a reward function that is \"mis-specified\", what does that mean? Ordinarily the reward function by definition is the source of truth for the task. So perhaps the authors are conceiving of reward functions constructed by reward-shaping or something similar?\n   Eq is kind of misleading. It looks like the expression in the brackets is a constant until you realize it actually is a function of s_t and is the variable that the expectation is taken over. $\\phi$ is originally defined (declared?) as relative to $\\pi$ but that dependence on $\\pi$ is dropped later, which is confusing.\n \n\n", "summary_of_the_paper": "The paper introduces a new method of doing curriculum learning for goal-directed RL. It uses a notion of reachability traces to model \"temporal closeness\" of states to a goal state. The reachability trace function is then used to define a sequence of sub-goals for which policies are learned iteratively, and then the final policy is learned  using advice from the decomposed sub-policies. \n\nExperiments are run on a few gridworld like experiments showing favorable performance vs other CL methods, it is also shown that the method may be more robust when reward function is poorly misspecified.", "summary_of_the_review": "An interesting, somewhat novel approach, but experiments not thorough enough to show that method is truly robust; theoretical contribution seems completely wrong.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "XcZI1AgF9UP", "reviewer": "Reviewer_zxez", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "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": "The high level idea proposed by the paper is very intuitive and interesting — use an initial suboptimal policy to find a (suboptimal) path to goal from all states in the environment, find a subgoal sequence using this coarse map, and use it to build a curriculum that eventually learns to reach the goal. The idea of learning the reachability traces is quite nice and I believe it can be very useful in many contexts. However, I have concerns regarding the purpose of the proposed method (and hence the contributions) and the empirical evaluations. I list my concerns below:\n\n1. [On the overall method] It is not clear to me what the entire subgoal generation + curriculum building exercise “gets us”. Looking at the choice of hyperparameters, [Appendix A] setting $t_\\phi=1$ is practically saying that the subgoal generation process is simply leading the agent in direction of the goal as per an increasing $\\phi$ trajectory. I am wondering if the authors tried using $\\phi$ simply as an exploration bonus without doing any curriculum design. Having learned the reachability traces somewhat gives you a “densification” of the reward, with the catch that it gives you a densification of a suboptimal trajectory. My hunch right now is that this along would be a pretty useful signal to guide the agent towards the goal (which is also what the subgoal sequence is doing) without having to involve so many steps. My general unhappiness with this is that there’s a lot of moving parts that would need tuning and careful reimplementation for new environments/tasks, and it feels over-engineered.\n2. [On empirical evaluation] When doing the empirical evaluations, do the other baselines (RIS, Q-learning etc.) have access to the behavior policy/demonstrations used by the the proposed method in Alg 1 and Alg 2? The performance curves seem to only be about the Alg 3 part of the story and if that is the case, the performance is a bit unfair. Bootstrapping any of the baselines with a pool of initial data can greatly accelerate the performance.\n3. [On “contributions”] I am not entirely convinced that the contributions [Section 1] are fairly evaluated in the experiments. The paper would greatly benefit by a set of explicit ablation studies that evaluate the usefulness of (say) the reachability traces in isolation from the proposed framework. One way to do this would be, as suggested above, just use the learned $\\phi$ as a signal for guiding the agent, and just use the subgoal proposal framework in isolation with some other dense metric for generating subgoals (e.g. IRL rewards etc.). This goes back to my concern about not being convinced whether the multiple moving parts of the algorithm are actually beneficial.\n4. This is less of a concern with the paper and more of a discussion — the learning of $\\phi$ in Section 2 seems very close to doing IRL using the behavioral policy/demonstrations/offline data. If a connection can be made, a lot of the interesting ideas from the several decades of progress in IRL can be used to improve what $\\phi$ can mean, and perhaps, be useful to the overall performance (or standalone). A discussion by the authors (response and in the paper, for the general quality of prose) would be quite useful.\n5. [On evaluation environments] The simplistic nature of tasks considered in the empirical evaluations — the gridworld and 2D navigation tasks — is a bit unappealing to me and it is unclear if the insights drawn from these tasks is reflective of the broader set of environments of interest in the RL community. While this is mostly a choice the authors are free to make, I would strongly urge them to include results from a broader set of tasks to make the results appealing to a wider community.\n6. [On the nature of tasks] The authors address the task of curriculum generation for single-goal RL, and that feels a bit restrictive, and extensions of the proposed method to the general goal-conditioned, or multi-task, RL framework is not obvious to me. This, coupled with the choice of environments evaluated in, makes the prospects of future directions or applications in complex, real-world domains a lot harder to follow. If it’s something the authors have thought above, the paper would really benefit from a discussion on how reachability traces may be extended to multi-task/goal-conditioned cases (e.g. using hindsight relabeling or a tuple of reachability traces, or a reachability map that maintains arbitrary A to B connections).\n\n\n\nI also have another small concern that does not affect my review but would be nice to have some clarification on:  \n7. [Figure 3] Is this figure showing a learned reachability map (for the center fig) or a visualization using an oracle map? Either way, I am a bit confused as to why value drops in the bottom right corner but is still high in the 3rd column from the right. Any path taken by a behavioral policy can not have crossed the black walls and hence, the middle of the grid (despite being closer to the goal in grid difference) should be farther away than the bottom right corner, similar to what the figure for $\\pi_{g_2}$ shows. Is this a mistake or am I missing something?\n\n---\n\n*Update*: Updating my recommendation to reflect the discussion by the others.", "summary_of_the_paper": "The paper tackles the problem of curriculum design for single-task/single-goal reinforcement learning problems with sparse rewards. The primary contribution of the work is a method to generate a subgoal curriculum using reachability traces — a learned metric that captures the distance to goal using under a pre-determined behavioral policy. The recipe can be summarized as follows: (i) Use an _available_ behavioral policy $\\pi$, or demonstrations, to obtain interactions from the environment, some of which reach the goal; learn a reachability function $\\phi(s)$ that creates a connectivity map, (ii) generate a sequence subgoals using this connectivity map, eventually leading up to the final goal G, (iii) use the subgoal curriculum to learn to reach goals.\n", "summary_of_the_review": "The paper presents an interesting idea of using reachability traces that is implemented with a lot of moving parts and evaluations on simplistic domains. I have some concerns regarding the empirical evaluations and the usefulness of the entire approach and look forward to engaging with the authors in the discussion period.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IJITyHBPri-", "reviewer": "Reviewer_8Hsg", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "* Pros\n  * The idea of discovering a sequence of subgoals and using it as a curriculum is interesting. \n\n* Cons\n  * The notion of reachability is not particularly novel.\n  * The proposed method is not technically sound and requires several strong assumptions.\n  * Lack of discussion and comparison to related work.\n  * The empirical results are not convincing. \n\n---\n\n- The notion of reachability function is not much interesting because it is equivalent to value function with a particular reward function (i.e., 0 for all non-goal states and $e_0$ for goal state) as acknowledged by the paper. It seems like the underlying claim of this paper is that it is useful to use the particular reward function for goal-based RL, which is in fact a standard setting in goal-based RL. Instead of claiming a new concept, it would be clearer to say that this paper shows how this particular reward function can be used for curriculum design in goal-based RL.\n\n- There is a large body of prior work on dealing with sparse rewards in goal-based reinforcement learning (e.g., HER and its follow-up work). This paper does not discuss how this work is related to the prior work. The experiments are also missing comparison to the related prior work.\n\n- The proposed algorithm does not seem technically sound and requires strong assumptions for the following reasons.\n\n  1. Algorithm 1 for learning reachability function seems inconsistent with Equation 2, because the data for training the reachability function is sampled from successful trajectories and unsuccessful trajectories with **equal probability**. However, the data needs to be sampled according to the policy $\\pi$ in order to estimate Equation 2. In other words, Algorithm 1 would lead to a biased estimation of Equation 2.\n\n  2. The proposed method requires a randomly-initialized policy to generate at least one successful episodes even before the proposed algorithm is applied. Thus, the proposed algorithm is restricted to relatively easier sparse-reward problems unlike the prior work (e.g., HER) that is expected to work in harder settings, where random exploration does not reach the main goal.  \n\n  3. The paper says \"a low $\\phi$ value may indicate that the state is further away from the goal state (and perhaps closer to the starting state), and thus may consitute an easier subgoal to be learned.\" This seems to assume that the starting state is the farthest state from the goal state, which is not necessarily true. ​Imagine a length-N chain MDP where $s_i$ is connected to $s_{i-1}$ and $s_{i+1}$. If the goal state is $s_N$ and the initial state is very close (say $s_{N-1}$), the reachability function of the initial state ($\\phi(s_{N-1})$) would be very high, while the $\\phi(s_0)$ would be very low. In this case, the proposed algorithm would learn to reach the farthest state ($s_0$) as the first subgoal because it has the lowest $phi$ value. It would is not only difficult to learn but also could hinder learning about the main goal. Although this is an adversarial example, the paper needs to clarify this underlying assumption.\n\n  4. Algorithm 3 goes through the sequence of discovered subgoals and moves on to the next subgoal whenever the current goal is reached by the agent. This seems to assume that subgoals are on the optimal path towards the main goal. Otherwise, if the subgoal is not a part of the optimal path towards the final goal, the subpolicy corresponding the current subgoal could hinder learning by choosing actions that lead to states that are even farther away from the main goal state. It is important to either show that the assumption holds or propose a way to overcome this issue. \n\n- The experimental results are not convincing. \n  1. Does the x-axis in Figure 4 include the amount of data used for Algorithm 1 (reachability learning) and Algorithm 2 (subgoal learning)? If not, it is not a fair comparison. If yes, it is important to show how much data is used for each step (algorithm 1, 2, 3) and how they are determined. \n  2. The experiment design for poorly designed reward function (Section 5.1) does not sound reasonable. According to the reward structure, it is optimal to stay at the $S_{NT}$ rather than reaching the goal state. It is a bit unreasonable to compare different algorithms under different reward functions (e.g., baselines given the poorly designed reward function and the proposed method given a good reward function). This result shows nothing more than saying that the reachability reward function (i.e., 0 for all non-goal states and a positive reward for goal state) is a reasonable reward design for goal-based RL. ", "summary_of_the_paper": "This paper considers a sparse reward goal-based RL problem and introduces a notion of reachability trace for reinforcement learning, which intuitively approximates how reachable (or how far) the goal state is from the current state. The proposed idea is to divide the whole learning problem into three phases: 1) learning a reachability function w.r.t. the main goal state, 2) finding a sequence of subgoals that are gradually closer to the main goal, 3) learning a main policy while using the sequence subgoals (corresponding subpolicies) as an exploratory policy in epsilon-greedy action sampling. The empirical results on grid worlds and several maze environments show that the proposed method outperforms DDPG, RIS, PER, and EBU. ", "summary_of_the_review": "Both exploration in sparse-reward goal-based RL and subgoal discovery are important topics in RL. Although this paper contains an interesting idea for subgoal discovery and curriculum design, the proposed algorithm requires several strong assumptions does not technically sound, and the empirical results are not convincing enough and lacks comparison to important baselines. \n\n---\n**Update after the rebuttal**\n\nI'm not entirely convinced by the author's rebuttal for the following reasons. Thus, I will keep my original score. \n1. If the reachability learning algorithm is biased and not consistent with Proposition 1, I do not see why Proposition 1 is needed from the first place.\n2. The author's justification for not comparing against HER is not convincing. Single-goal RL is just a special case of multi-goal RL. In fact, HER has been shown to be effective in a single-goal RL setting (see Section 4.3 of the HER paper). So, I believe that it is important to compare against this baseline. \n3. The authors should have clearly showed how much data each algorithm (1, 2, 3) consumes in the plots and how the switching points are determined. The fact that the total amount of data is reflected in the x-axis doesn't address my concern.\n4. I'm still not sure why Section 5.1 is needed. My initial comment about \"This result shows nothing more than saying that the reachability reward function (i.e., 0 for all non-goal states and a positive reward for goal state) is a reasonable reward design for goal-based RL.\" is not addressed by the author's response. The author's response seems to repeat exactly what I wrote above. This paper seems to propose a proper reward design (reachability) as a solution, but my comment was that a proper reward design seems to be on the problem side rather than on the solution side.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "1: The main claims of the paper are incorrect or not at all supported by theory or empirical results.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "9Cedk-HQzhP", "reviewer": "Reviewer_psX9", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "This paper is one of the papers that try to automatically propose a curriculum learning to improve the sample efficiency of the RL algorithms. Similar ideas has been intensively explored by many papers. See a new review paper https://arxiv.org/pdf/2003.04664.pdf. The algorithm this paper proposed has a strong limitation. It only works when there is one final goal. If the goal of the learning is to train an agent that can reach multiple different goals, one has to learn the trace function multiple times. I also have the following concerns.\n\n1. The proposition 1 is not clear. I am not sure what it means by \"the reachability trace function is a solution to an MDP\". And when the author say \"converges to the optimal goal reaching policy\", which specific algorithm are we talking about? Is it supposed to be $\\mathcal{R}_{\\phi}$ instead of $r_{\\phi}$ in Proposition 1?  By reading the proof of Proposition 1, it is very vague. It is not clear what the authors mean by \"This interpretation allows reachability traces to also potentially be learned via standard RL algorithms.\"\n\n2. I don't agree with the statement at the start of section 3. When $\\phi(s)$ is high, it may be less reachable from the starting state. However, $\\phi(s)$ is low, it only indicates that $s$ is far from goal state, it does not necessarily mean it is close to the starting state. For example, in a navigation problem, your starting state is in the middle of the map and goal state is on the right corner. Then any state on the left corner could also have a low $\\phi(s)$ while they are not good subgoals.\n\n3. Algorithm does not show a significant improvement over RIS. The authors should compare to more baseline algorithms. At least, HER (hindsight experience replay) is an important method for multi-goal learning and it should be compared.\n\n\n\n\n", "summary_of_the_paper": "This paper proposed an automatic curriculum learning design method for goal-orientated Reinforcement Learning. The idea is to learn a reachability trace function to measure the temporal difference between a state and the final goal state. Then a curriculum is learnt based on the reachability trace function. The algorithm is evaluated on tabular and continuous robotic control environments.", "summary_of_the_review": "I believe the idea behind the paper is not very novel and the performance is not very significant. The theory is poorly written. I recommend rejection.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors present a method for creating a curriculum for goal-conditioned reinforcement learning. In particular, they propose to use reachability traces to define a sequence of sub-goals that aid learning. During the review process, the reviewers mentioned the novelty of the proposed approach and the intuitive explanations provided by the authors. However, the reviewers also pointed out that the experiments could be more thorough, errors in the theoretical justification of the method as well as simplicity of the evaluation environments, among others. Some of the reviewers increased their score after the authors' rebuttal but it was not enough to advocate for acceptance of the paper. I encourage the authors to incorporate reviewers' feedback in the next version of the paper.
Decision: Reject