C-Learning: Horizon-Aware Cumulative Accessibility Estimation
Authors: Panteha Naderian
Gabriel Loaiza-Ganem
Harry J. Braviner
Anthony L. Caterini
Jesse C. Cresswell
Tong Li
Animesh Garg
Venue: ICLR 2021 Poster (2021)
Keywords: reinforcement learning
goal reaching
Q-learning

Abstract: Multi-goal reaching is an important problem in reinforcement learning needed to achieve algorithmic generalization. Despite recent advances in this field, current algorithms suffer from three major challenges: high sample complexity, learning only a single way of reaching the goals,  and difficulties in solving complex motion planning tasks. In order to address these limitations, we introduce the concept of cumulative accessibility functions, which measure the reachability of a goal from a given state within a specified horizon. We show that these functions obey a recurrence relation, which enables learning from offline interactions. We also prove that optimal cumulative accessibility functions are monotonic in the planning horizon. Additionally, our method can trade off speed and reliability in goal-reaching by suggesting multiple paths to a single goal depending on the provided horizon. We evaluate our approach on a set of multi-goal discrete and continuous control tasks. We show that our method outperforms state-of-the-art goal-reaching algorithms in success rate, sample complexity, and path optimality. Our code is available at https://github.com/layer6ai-labs/CAE, and additional visualizations can be found at https://sites.google.com/view/learning-cae/.

Published as a conference paper at ICLR 2021
C-LEARNING: HORIZON-AWARE CUMULATIVE ACCESSIBILITY ESTIMATION
Pantcha Naderian, Gabriel Loaiza-Ganem, Harry J. Braviner, Anthony L. Caterini, Jesse C. Cresswell Tong Li
Layer 6 AI (panteha, gabriel, harry, anthony, jesse, tong)elayer6. ai
Animesh Garg
University of Toronto, Vector Institute, Nvidia gargêcs toronto.....ooooooo edu
ABSTRACT
Multi-goal reaching is an important problem in reinforcement learning needed achieve algorithmic generalization. Despite recent advances in this field, current algorithms suffer from three major challenges: high sample complexity, learning only a single way of reaching the goals, and difficulties in solving complex motion planning tasks. In order to address these limitations, we introduce the concept of cumulative accessibility functions, which measure the reachability of goal from given state within a specified horizon. We show that these functions obey re- currence relation, which enables learning from offline interactions. We also prove that optimal cumulative accessibility functions are monotonic in the planning hori- Additionally, method can trade off speed and reliability in goal-reaching by suggesting multiple paths to a single goal depending on the provided horizon. We evaluate approach trol tasks. We show that our method outperforms state-of-the-ar goal-reaching algorithms in success rate, sample complexity, and path optimality. Our code is available at hstpp:: //gittttbbbbb com lammm/aayerraaa 6ai -aai-aallsalslaeeeaaaeeaaeaaaaae CAE, and addi- tional visualizations can be found at httpt:tt/////m //sites//ttssee google. com/view. Learning-cae/
set of multi-goal discrete and continuous con-
INTRODUCTION
Multi-goal reinforcement learning tackles the challenging problem of reaching multiple goals, and as a result, is an ideal framework for real-world agents that solve a diverse set of tasks. Despite progress in this field (Kaelbling] 1993] Schaul al. 2015 Andrychowicz inability to find multiple paths to goal, high sample complexity, and poor results in complex motion planning tasks. In this paper we propose C-learning, a method which addresses all of these shortcomings.
al. [017 Ghosh al.)
2019) current algorithms suffer from set of limitations:
Many multi-goal reinforcement learning algorithms are limited by learning only single policy (a)s,g) over actions a to reach goal from state s. There is an unexplored trade-off between reaching the goal reliably and reaching it quickly. We illustrate this shortcoming in Figure Ta| which represents an environment where an agent must reach a goal on the opposite side of some predator. Shorter paths can reach the goal faster at the cost of higher probability of being caten. Existing algorithms do not allow dynamic choice of whether to act safely or quickly at test time.
The second limitation is sample complexity. Despite significant improvements (Andrychowicz et al., 2017 Ghosh et al. 2019), multi-goal reaching still requires very large amount of environment interactions for effective learning. We argue that the optimal Q-function must be learned to high accuracy for the agent to achieve reasonable performance, and this leads to sample inefficiency. The same drawback of optimal Q-functions often causes agents to learn sub-optimal ways of reaching the intended goal. This issue is particularly true for motion planning tasks (Qureshi et al.) 2020), where current algorithms struggle.

---

Published as a conference paper at ICLR 2021
Predator
Agent
Goel
Low It High Risk
('6ig,a 6.00
Balanoe
("(s. a.) Ra 0.93
Risk
(a)
(b)
Figure 1: (a) continuous spectrum of paths allow the mouse to reach its goal faster, at an increased risk of disturbing the cat and being eaten. (b) Q" (with y = 0.99) needs to be learned more accurately than C to act optimally. The goal g can be reached in h' = 5 steps from so that (* (" g.a") = 0.99 and Q' 0.99"; while C' (s,a",g,,) = 1 and C* as,a-,g, h²) O.
We propose to address these limitations by learning horizon-aware policies T[a|s, g. ht. which should be followed reach goal g from state s in at most steps. The introduction of time horizon h naturally allows us to tune the speed/reliability trade-off, as an agent wishing to reach the goal faster should select policy with a suitably small value. To learn these policies, we introduce the optimal cumulative accessibility function a,, This is generalization of the state-action value function and corresponds to the probability of reaching goal g from state after at most h steps if action is taken, and the agent acts optimally thereafter. Intuitively it is similar to the optimal Q-function, but Q-functions rarely correspond to probabilities, whereas the C* -function does by construction. We derive Bellman backup update rules for C", which allow it to be learned via minimization of unbiased estimates of the cross- cross-yntropy loss - this is in contrast Q-learning, which optimizes biased estimates of the squared error. Policies π [als, g. h) can then be recovered from the C* function. We call our method cumulative accessibility estimation, or C- learning. Pong et al. (2018) proposed TDMs, method involving horizon-awe aware policies. We point out that their method is roughly related to a con-cumulative version of ours with different loss that does not enable the spced/reliability trade-off and is ill-suited for sparse rewards. We include detailed discussion of TDMs in section
One might expect that adding extra dimension to the learning task, namely h, would increase the difficulty as C effectively contains the information of several optimal Q-functions for different discount factors. However, argue that C" does not need to be learned to the same degree of accuracy as the optimal Q-function for the agent to solve the task. As a result, learning C* is more efficient, and converges in fewer environmental interactions. This property, combined with our proposed goal sampling technique and replay buffer used during training, provides empirical improvements over Q-function based methods.
In addition to these advantages, learning C* itself useful, containing information that the horizon- aware policies do not. It estimates whether goal is reachable from the current state within h steps. In contrast, (a]s, g, it) simply returns some action, even for unreachable goals. We show that C* can be used to determine reachability with examples in a nonholonomic environment.
Summary of contributions: (i) introducing C-functions and cumulative accessibility estimation for both discrete and continuous action spaces; (di) highlighting the importance of the speed vs re- liability trade-off in finite horizon reinforcement learning; (iit) introducing novel replay buffer specially tailored for learning C* which builds on HER (Andrychowicz et al., 2017);; and (iv) em- pirically showing the effectiveness of our method for goal-reaching as compared existing alterna- tives, particularly in the context of complex motion planning tasks.
BACKGROUND AND RELATED WORK
Let us extend the Markov Decision Process (MDP) formalism (Sutton et al. 1998) for geal-neaching.
We consider set of actions A, state space S, and goal set G. We assume access to goal checking
function x g + {0. 1} such that G(s, g) = 1 if and only state s achieves goal g. For example, achieving the goal could mean exactly reaching certain state, in which case G S and
2

---

Published as a conference paper at ICLR 2021
Figure 2: Graphical model depicting trajectories from Px(1--g.1)( (-)o)))))))s a,a0 a). Gray nodes denote fixed val- ues, and white nodes stochastic ones. Nodes a, g and s are non-stochastic simply because they are conditioned on, not because they are always fixed within the environment. Note that the values of h decrease deterministically. Nodes corre- sponding horizons could be separated from states, but not for a more concise graph.
g( (s g). For many continuous state-spaces, hitting state exactly has zero probability. Here we can still take G = S, but let G(s,g) 9) (d(s,g) I <) for some radius and metric d. More general choices are possible. For example, in the Dubins' Car environment which we describe in more detail later, the state consists of both the location and orientation of the car: S = IR² x S We take g 2R and G(s, g) checks that the location of the car within some small radius of g. ignoring the direction entirely. For fixed G(s,g) can be thought of as sparse reward function.
In the goal-reaching setting, policy xS P(A), where ((A) denotes the set of distributions over A, maps state- stte-gooa pairs to an action distribution. The environment dynamics are given by a starting distribution p(so: .)., usually taken p(5))p(g). and transition probabilities p($,+1|s,, a.). States for which G(s, 9) = are considered terminal.
Q-Learning: A Q-function Watkins & Dayan 1992) for multi-goal reaching. Q SXGxA + R, defined by Q" (&t, 9, a+) 1= 1= ? St. 9) ()18, ar), where y E [0, a discount factor and the expectation is with respect to state-action trajectories obtained by using π (a]s; (ssg). g). If n" is
an optimal policy in the sense that Q* (s, 9, a) 2 Q 9, a) for every æ and (8,g, a) E ExgxA.
then Q" matches the optimal Q-function, Q", which obeys the Bellman equation:
(s, Ex-pp(llaa)
G(s,g) + max Q" (s'. a'EA
(1)
In deep Q-learning (Miih et al., 2015), Q' is parameterized with neural network and learn- ing is achieved by enforcing the relationship from equation [ This is done by minimizing Σ, E(Q" (st, It, a.), y:). where y corresponds to the expectation in equation [ and is estimated using replay buffer of stored tuples (st, 0,, (a, s)). Note that s is the state the environment transitioned to after taking action a; from state 8i, and determines the value of yi- Typically L is chosen
squared error loss, and the dependency of y; Q' is ignored for backprop- agation order to stabilize training. Once Q" is learned, the optimal policy is recovered by (als,g) (a arg max, (" a'))
There is ample work extending and improving upon deep Q-learning (Haarnoja et al. 2018). For example, [illierap et al. (2015) extend it to the continuous action space setting, and Fujimoto et al. (2018) further stabilize training. These improvements are fully compatible with goal reaching (Pong et al. 2019| (Bharadhwaj et al. 2020aa Ghosh et al. 2019). Andrychowicz et al. (2017) proposed Hindsight Experience Replay (HER), which relabels past experience as achieved goals, and allows sample efficient learning from sparse rewards (Nachum et al. 2018).
3 CUMULATIVE ACCESSIBILITY FUNCTIONS
We now consider horizon-aware policies accessibility function C* (s. a, g, h), or C'-function, as the probability of reaching goal from state in at most h steps by taking action and following the policy thereafter. By "following the policy π thereafter" we mean that after o, the next action 41 is sampled from TT- T-|181.0 h 1), 02 is sampled from æ (- (-|82.9 g, h- 2) and so See Figure 2 for graphical model depiction of how these trajectories are obtained. Importantly, an agent need not always act the same way at a particular state in order reach a particular goal, thanks horizon-awarenes. We use P (r(-l-g.h)( (-150 5, ao a) to denote probabilities in which actions are drawn in this manner and transitions are drawn according the environment p($ 19,, a). More formally, C is given by:
P(A), and define the cumulative
(= g, h) = (xx(he.)))) max G( g) = = 8, 8,00 = aa)
(2)
3

---

Published as a conference paper at ICLR 2021
Proposition 1: C can be framed Q-function within the MDP formalism, and if x² is optimal
in the sense that C*" (8, a, g, h) 2 C* (s, 0, 9, h) for every a and (8, a, 9, h)) E x A x G x N, then C matches the optimal C-function, C², which obeys the following equation:
(,,), Bxrpptleaa) G(s,g)
max C* ('s, a'EA
(++.).) h1)) if
and h 2 1,
(3)
otherwise.
See appendix A for a detailed mathematical proof of this proposition. The proof proceeds by first deriving a recurrence relationship that holds for any C* In an analogous manner to the Bellman equation in Q-learming, this recurrence involves an expectation over T-|ss' g. 1), which, when replaced by a max returns the recursion for C*.
Proposition relevant as it allows us to learn C", enabling goal-reaching policies to be recovered:
π (a|s, g. h)) 1 a arg max C* a' 1,)
(4)
a'
C* itselff is useful for determining reachability. After maximizing over actions, it estimates whether given goal reachable from a state within some horizon. Comparing these probabilities for different horizons allows us to make a speed / reliability trade-off for reaching goals.
We observe that an optimal C C"*-functin is non-decreasing in h, but this does not necessarily hold for non-optimal C-ffunctonss. For example, a horizon-awarr policy could actively try to avoid the goal for high values of h, and the C*-function constructed from it would show lower probabilities of success for larger h. See appendix A for a concrete example of this counter-intuitive behavior.
Proposition 2: C* is non-decreasing in h. See [ppendix[A] fA] a detailed mathematical proof. Intuitively, the proof consists of showing that an optimal policy can not exhibit the pathology mentioned above. Given optimal policy x² ra(aas. solg g, h) for a fixed horizon h we construct a policy गे for h + 1 which always performs better, and lower bounds the performance of x (alss g, h 1).
In addition to being an elegant theoretical property, proposition 2 suggests that there is additional structure in a C* function which mitigates the added complexity from using horizon-aware poli- cies. Indeed, in our preliminary experiments we used non-cumulative version of C-functions (see section 3.3) and obtained significantly improved performance upon changing to C'ffunctonss. More- over, monotonicity could be encoded in the architecture of C* (Sill 1998 Wehenkel & Louppe) 2019). However, we found that actively doing so hurt empirical performance (appendix
3.1 SHORTCOMINGS OF Q-LEARNING
Before describing our method for learning C*, we highlight shortcoming of Q-learnig, Consider a 2D navigation environment where an agent can move deterministically in the cardinal directions, and fix and g. For an optimal action a", the optimal Q function will achieve some value Q" 9, a*) E [0, 1] in the sparse reward setting. Taking sub-optimal action am initially results in the agent taking two extra steps to reach the intended goal, given that the agent acts optimally after the first action, so >²Q" (s, 9, a²) The value of is typically chosen close to 1, for example 0.99, to ensure that future rewards are not too heavily discounted. As a consequence 72 as 1 and thus the value of Q' at the optimal action is very close to its value sub-optimal action. We illustrate this issue in Figure [b] In this scenario, recovering an optimal policy requires that the error between the learned Q-function and Q" should be at most (1 /22/; this is reflected empirically by Q-learning having high sample complexity and learning sub-optimal paths. This shortcoming surfaces in any environment where taking a sub-optimal action results in a slightly longer path than an optimal one,
that Q" (s, 9, a=)
as in c.g. motion planning tasks.
The C* function does not have this shortcoming. Consider the same 2D navigation example, and let h" be the smallest horizon for which g can be reached from s. ht* can be easily obtained from C* as the smallest h such that max, C* (s, a, g, h) = 1. Again, denoting a" as optimal action and a as a sub-optimal one, we have that C* (s, a.,g,""... hh) = 1 whereas C* a"" is illustrated in Figure lb] Therefore, the threshold for error is much higher when learning the C* function. This property results in fewer interactions with the environment needed to learn C* and more efficient solutions.
9, h²) ) = O, which
4

---

Published as a conference paper at ICLR 2021
3.2 HORIZON-INDEPENDEN POLICIES
Given a c'--funcionn, equation 4 lets us recover a horizon-awarr policy, At test time, using small val- ues of h can achieve goals faster, while large values of h will result in safe policies. However, nat- ural question arises: how small is small and how large is large? In this section we develop a method quantitatively recover reasonable values of h which adequately balance the speed/reliability trade- off. First, a safety threshold a E (0, 1] is chosen, which indicates the percentage of the maximum value of C* we are willing to accept safe enough. Smaller values of will thus result in quicker policies, while larger values will result in safer ones. Then we consider range of viable horizons, H. and find the maximal C* value, M(. 9) = maxkeH,,E.. Cs O, g. h). We then compute:
ha (1, g) = arg min max C* (s,a, a.a.g,h) h):
max (8, mmx a, h) 2 aM (s,g))
(5)
NEW aeA
aEA
and take T. (als, g) 1 (a mag, C' a', g. (s. g))). This procedure also allows to recover worizon-independen policies from C" by using a fixed value of a, which makes comparing against horizon-unawanl methods straightforward. We used horizon-unawan policies with added randomness as the behaviour policy when interacting with the environment for exploration.
3.3 ALTERNATIVE RECURSIONS
One could consider defining a non-cumulative version of the C-function, which we call an A- function for "accessibility" (not for "advantage"), yielding the probability of reaching goal in exactly h steps. However, this version is more susceptible to pathological behaviors that hinder learning for certain environments. For illustration, consider agent that must move step at time in the cardinal directions on a checkerboard. Starting on a dark square, the probability of reach- ing light square in even number of steps is always zero, but may be non-zero for odd numbers. An optimal A-function would fluctuate wildly as the step horizon f is increased, resulting in a harder target to learn. Nonetheless, A-functions admit a similar recursion to equation
[8] which we include in appendix for completeness. In any case, the C'-unction provides a notion of reachability which
more closely tied to related work (Savinov al. 2018: Venkattaramanujan al., 2019 Ghosh
et al. 2018 Bharadhwajj et al. 2020a).
In Q-learning, discount factors close to 1 encourage safe policies, while discount factors close to o encourage fast policies. One could then also consider discount-condittonel policies a(a ((als,,g g. 7) as way to achieve horizon-awareness. In appendix D we introduce D-functions (for "discount"), Dss, a. 9. 7); which allow recovery of from the same limitation as Q-functions that they need to be learned a high degree of accuracy.
policies. However D-functions suffer
CUMULATIVE ACCESSIBILITY ESTIMATION
Our training algorithm, which we call cumulative accessibility estimation (CAB), or C-learning, is detailed in algorithm 1. Similarly to Q-learning, the C" function be modelled neural network with parameters 0, denoted Cý, which can be learned by minimizing:
Σ Wy log (s;, az 0g. h4) + (1 - y:) log (1 - Cs as Is, h4))],
(6)
where Yt corresponds to a stochastic estimate of the right hand side of equation [8| The sum is over tuples (st, as, 8/ gt. h2) drawn from a replay buffer which we specially tailor to successfully learn C². Since C* corresponds to a probability, we change the usual squared loss to be the binary cross entropy loss. Note that even if the targets y/ are not necessarily binary, the use of binary cross entropy still justified as it equivalent to minimizing the KL divergence between Bernoulli distributions with parameters yi and Cp azs 9i, h2) (Bellemare et al. 2017). Since the targets used do not correspond to the right-hand side of equation 18 but to a stochastic estimate (through s)) of it, using this loss instead of the square loss results in an wabiased estimate of Σ, LCC (s;, dg, 9t. h;), gfrue), ), where y!t corresponds to the right-hand side of equation 18 at (st, ag h:) (see appendix for detailed explanation). This confers another benefit of C-learning over Q-learning, as passing stochastic estimate of equation through the typical squared loss results biased estimators. As in Double Q-learning (Van Hasselt et al. 2015). ), we
second network C2 to compute the y, targets, and do not minmize equation 6 with respect to 0'. We periodically update 6' to match 8. We now explain our algorithmic details.
5

---

Published as a conference paper at ICLR 2021
Algorithm 1: Training C-learning Network
Parameter: Nexplore: Number random exploration episodes
Parameter: NGD: Number of goal-directed episodes
Parameter: Nirain: Number of batches train on per goal-directed episode
Parameter: NNoop:: Number of batches between target network updates
Parameter: a: Learning rate
0 < Initial weights for Cg
< 0
// Copy weights to target network // Initialize experience replay buffer // Counter for training batches
D [ Wb + 0
repeat Nexplore times
& + get.roolooutTTraddoor D.append(E)
// Do random rollout // Save the rollout to the buffer
repeat NGD times
f goal smmplemm)))))))
// Sample a goal 11 Try to reach the goal // Save the rollout
10
+ get.rollout( (Teehavirr))
D.append(E)
11
12
repeat Nurin times
13
if nh mod Ne = then
14
// Copy weights periodically :: {si; O1 81 9i, h4) B - sample batch(D) // Est imatee RHS of equation 18 L+ 1 E yi log Cp (0,, 0n 9b: 0, h2) (1 - y1) log (1 (,,
0' +
// Sample batch
{8: |
|8| + get.targets(B.0)
16
17
18
- Vo
// Update weights
nbb ub +1
// Trained one batch
Reachability-guidee sampling: When sampling a batch (line 15 of algorithm 1), for each i first sample an episode from D, and then a transition (s;, a; s;)) from that episode. We sample h; favoring smaller h's the beginning of training. We achieve this by selecting h; h with probability proportional to h kaaD/Nee, where RGD is the current episode number, NND the total number of episodes, and K is a hyperparameter. For deterministic environments, we follow HER (Andrychowicz et al.] (207)) and select 9, uniformly at random from the states observed in the episode after 8,. For stochastic environments we use a slightly modified version, which addresses the bias incurred by HER (Matthias et al., 2018) in the presence of stochasticity. All details included in appendix
Extension to continuous action spaces: Note that constructing the targets yi requires taking maximum over the action space. While this is straightforward in discrete action spaces, not so for continuous actions. [illicrap et al. (2015) proposed DDPG, method enabling deep Q-learning in continuous action spaces. Similarly, Fujimoto et al.) (2018) proposed TD3, a method for further stabilizing Q-learning. We note that C'-earring is compatible with the ideas underpinning both of these methods. We present a TD3 version of C-learning in appendix
We finish this section by highlighting differences between C-learning and related work. Ghosh al. (2019) proposed GCSL, method for goal-reaching inspired by supervised learning. In their derivations, they also include a horizon h which their policies can depend on, but they drop this dependence in their experiments as they did not see practical benefit by including h. We find the opposite for C-learning. TDMs (Pong et al.) (018) use horizon-aware policies and similar recursion to ours. In practice they use negative T., distance reward, which significantly differs from goal-reaching indicators. This is an important difference as TDMs operate under dense rewards, while we use sparse rewards, making the problem significantly more challenging. Additionally, distance between states in nonholonomic environments is very poorly described by L1 distance, resulting in TDMs being ill-suited for motion planning tasks. We also highlight that even the reward in TDMs was swapped with goal checking function G, the resulting objective would be much closer to the non-cumulative version of C-learning presented in appendix C TDMs recover policies from their horizon-aware Q-function in different manner to ours, not allowing speed vs reliability trade-off. The recursion presented for TDMs is used by definition, whereas we have

---

Published as a conference paper at ICLR 2021
Experimental environments. from left to right: frozen lake, Dubins' car, FetchPickAnndPlace-V and MaandManipulateePeaulllyy Arrows represent actions (only their direction should be considered. their magnitude not representative of the distance travelled by agent taking an action). See text for description.
Figure 3:
provided mathematical derivation of the Bellman equation for C'ffunctonss along with proofs of additional structure. As a result the C-function being probability we use a different loss function (binary cross-entropy) which results in unbiased estimates of the objective's gradients. Finally, point out that TDMs sample horizons uniformly at random, which differs from our specifically tailored replay buffer.
EXPERIMENTS
5.1
SETUP
Our experiments are designed to show that (i) C-learning enables the speed vs reliability trade-off, (ii) the C" function recovered through C-learning meaningfully matches reachability nonholo- nomic environments, and (iii) C-learning scales to complex and high- nigh-dimensional motion planning tasks, resulting in improved sample complexity and goal-reaching. We use success rate (percentage of trajectories which reach the goal) and path length (average, over trajectories and goals, number of steps needed to achieve the goal among successful trajectories) as metrics.
We compare C-learning against GCSL (Ghosh et al. 2019) (for discrete action states only) and deep Q-learning with HER (Andrychowicz al.) (017)) across several environments, which depicted in Figure 3 All experimental details and hyperparameters are given in appendix We also provide ablations, and comparisons against TDMs and the alternative recursions from section 3.3 in appendix
We evaluate C--leanning on the following domains:
1. Frozen lake is 2D navigation environment where the agent must navigate without falling in the holes (dark blue). Both the state space (7 x 5 grid, with two holes) and the action state are discrete. Falling in hole terminates an episode. The agent's actions correspond to intended directions. The agent moves in the intended direction with probability 0.8, and in perpendicular directions with probabilities 0.1 each. Moving against the boundaries of the environment has effect. We take G and G(s, g) = [1 s).
2. Dubins' car is a more challenging deterministic 2D navigation environment, where the agent drives car which cannot turn by more than 10 The states, with spatial coordinates in [0, 15)², are continuous and include the direction of the There are 7 actions: the 6 combinations of [left 10º, straight, right 10º) } x {forward 1, reverse 1}. and the option to not move. As such, the set of reachable states is not simply ball around the current state. The environment also has walls through which the car cannot drive. We take g = [0, 15]2 and the goal is considered to be reached when the car is within Lxx distance of 0.5 from the goal, regardless of its orientation.
(Brockman et al. 2016) a complex, higher-dimensional environment in which robotic arm needs to pick up block and move it to the goal location. Goals are defined by their 3-dimensional coordinates. The state space is 25-dimensional, and the action space is continuous and 4-dimensional.
PetchPickAndPlce....
(Brockman al. 2016) realistic environment known the difficult real-ngg problem, where deep Qelarniig with HER shows very limited success (Plap- pert al. 2018). The environment has continuous action space of dimension 20, a 63-dimensional state space, and 7-dimensional goals. Note that we are considering the more challenging version of the environment where both target location and orientation are chosen randomly.
HaudMannipulateeeeFulll

---

Published as a conference paper at ICLR 2021
u8o0 won non solos miis uide mils
(a)
(b)
(d)
Figure 4: (a) Multimodal policies recovered by C-learning in frozen lake for different values of h for reaching (G) from (8) (top): unimodal policies recovered by GCSL and HER (bottom). (b) Heatmaps over the goal space of max, C as,a, h) with fixed and h for Dubins' car, with h and = 25 (bottom). (c) Trajectories learned by C-learning (top), GCSL (middle) and HER (bottom) Dubins' car. (d) Success rate throughout the training for Dubins' car (top), FetchPickAnPPlace-W (middle) and #tanMannipulateeenFulll (bottom) for C-leaaning (blue). HER (red) and GCSL (green).
(top). h 15 (middle)
5.2 RESULTS
Speed vs reliability trade-off: We use frozen lake to illustrate this trade-off. test time, we set the starting state and goal as shown in Figure 4a Notice that, given enough time, agent reach the goal with near certainty by going around the holes on the right side of the lake. However, the agent is time-constrained, the optimal policy must accept the risk of falling in hole. We that C-learning does indeed learn both the risky and safe policies. Other methods, as previously explained, can only learn one. To avoid re-plotting the environment for every horizon, plotted arrows in Figure 4a corresponding to arg max, TT" (a)so, 90, h), arg max, ा (a|s1, 9, 1), arg max, n" (alss. g, 22) and on, where $1+1 obtained from the previous state and action while ignoring the randomness in the environment (i.e. Se+1 arg max, p(s]st, at)). In other words, we are plotting the most likely trajectory of the agent. When given the minimal amount of time to reach the goal (h 6), the CAE agent learns correctly to accept the risk of falling in hole by taking the direct path. When given four times as long (h 24), the agent takes safer path by going around the hole. Notice that the agent makes single mistake at the upper right corner, which quickly corrected when the value of decreased. On the other hand, we can see on the bottom panel that both GCSL and HER recover single policy, thus not enabling the speed vs reliability trade-off. Surprisingly, GCSL learss to take the high-risk path, despite Ghosh et al. (209)'s intention incentivize paths that guaranteed reach the goal.
have
(a)
Reachability learning: To demonstrate that we are adequately learning reachability, we removed the walls from Dubins' car and further restricted the turning angles to 5", thus making the dumbbell shape of the true reachable region more extreme. Figure(4b) we show that our learned C* function correctly learns which goals are reachable from which states for different time horizons in Dubins' car: not only is the learned C* function increasing h, but the shapes are as expected. None of the competing alternatives recover this information any way, and thus comparisons As previously mentioned, the optimal C* -f-function in this task not trivial. Reachability is defined by the "geodesics" " in = [0, 15)² x S that are constrained by the finite turning radius, and thus follow more intricate structure than ball in R22
not available.
8

---

Published as a conference paper at ICLR 2021
Table I: Comparison of C-Learning against relevant benchmarks in three environments, averaged across five random seeds. Runs in bold are either the best the given metric that environment, have within the error bars of the best.
ENVIRONMENT
METHOD
SUCCESS RATE
PATH LENGTH
CAB
86.15% = 2.44%
16.45 + 0.99
Dubins' Car
GCSL
79.69% 1 6.35%
32.64 + 6.16
HER
51.25% + 6.48%
20.13 = 1.66
CAE (TD3)
99.34% 1 0.27%
8.53 1 0.09
FetchPickAndPlace-vl
HER (TD3)
98.25% 1: 2.51%
8.86 + 0.14
CAE (TD3)
39.83% 1 1.64%
7.68 1 0.90
HandManiipolacceooFulll-
HER (TD3)
21.99% = 2.46%
15.03 = 0.71
Motion planning and goal-reaching: For a qualitative comparison of performance for goal- reaching, Figure [4c shows trajectories for C-learning and competing alternatives for Dubins' car. We can see that C-learning finds the optimal route, which a combination of forward and backward movement, while other methods find inefficient paths. We also evaluated our method on challenging goal reaching environments, and observed that C-learning achieves state-of-the-art results both in sample complexity and success rate. Figure 4d shows that C-learning is able to learn considerably faster in the FetchPickAndPlace-V environment. More importantly, C-learning achieves an abso- lute 20% improvement in its success rate over the current state-of-the-art algorithm HER (TD3) in the HandMManipulateeen Penllll-eee environment. Quantitative results are shown in Table ] On Dubins' car, also note that C-learning ends up with smaller final Loe distance to the goal: 0.93 = 0.15 vs. 1.28 + 0.51 for GCSL.
6 DISCUSSION
We have shown that C-learning enables simultancous learning of how to reach goals quickly and how to reach them safely, which current methods cannot do. We point out that reaching the goal safely in our setting means doing so at test time, and is different to what is usually considered in the safety literature where safe exploration is desired (Chow et al. 2018 [hharadwwaj et al. 2020b). Additionally, learning C* effectively learns reachability within an environment, and could thus naturally lends itself to incorporation into other frameworks, for example, in goal setting for hierarchical RL tasks (Nachum et al. 2018) where intermediate, reachable goals need to be selected sequentially. We believe further investigations on using C-functions on safety-critical environments requiring adaptation (Peng et al. 2018 Zhang et al. 2020), or for hierarchical RI., are promising directions for further research.
We have also argued that C-functions are more tolerant of errors during learning than Q-functions which increases sample efficiency. This is verified empirically in that C-learning is able solve goal-reaching tasks earlier on in training than Q-learning.
We finish by noticing parallel between C-learning and the options framework (Sutton et al. 1999 Bacon et al., 2017), which introduces temporal abstraction and allows agents to not always follow the same policy when at given state 8. However, our work does not fit within this framework, as options evolve stochastically and new options are selected according only to the current state, while horizons evolve deterministically and depend on the previous horizon only, not the state. Additionally, and unlike C-learning, nothing encourages different options to learn safe or quick policies, and there is no reachability information contained in options.
7 CONCLUSIONS
In this paper we introduced C-learning, a Q-learning-inspired method for goal-reaching. Unlike previous approaches, we propose the use of borizon-aware policies, and show that not only can these policies be tuned to reach the goal faster more reliably, but they also outperform horizon- unaware approaches for goal-reaching on complex motion planning tasks. We hope our method will inspire further research into horizon-aware policies and their benefits.
9

---

Published as a conference paper at ICLR 2021
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, Pieter Abbeel, and Wojciech Zaremba. Hindsight experience replay. In Advances in neural information processing systems, pp. 5048-500800 5058, 2017.
Pierre-Luc Bacon, Jean Harb, and Doina Precup. The option-critic architecture. In Thirty-First AAAI Conference on Artificial Intelligence, 2017.
Mare Bellemare, Will Dabney, and Rémi Munos. distributional perspective on reinforcement learning. arXiv preprini arXiv: / 770700687, 2017.
Homanga Bharadhwaj, Animesh Garg, and Florian Shkurti. Leaf: Latent exploration along the frontier. arXiv preprint arXiv:2005.00334, 2020a.
Homanga Bharadhwaj, Aviral Kumar, Nicholas Rhinehart, Sergey Levine, Florian Shkurti, and Ani- mesh Garg. Conservative safety critics for exploration. arXiv preprint WVXiv:2010.14497, 2020b.
Greg Brockman, Vicki Cheung, Ludwig Pettersson, Jonas Schneider, John Schulman, Jie Tang, and Wojciech Zaremba. Openai gym, 2016.
Yinlam Chow, Ofir Nachum, Edgar Duenez-Guzman, and Mohammad Ghavamzadeh. Iyapunov- based approach safe reinforcement learning. In Advances in neural information processing systems, pp. 0092-8101, 2018.
Scott Fujimoto, Herke Van Hoof, and David Meger. Addressing function approximation error in actor-critic methods. arXiv preprint arXiv: 1802. 09007,
Dibya Ghosh, Abhishek Gupta, and Sergey Levine. Learning actionable representations with goal- conditioned policies. arXiv preprint arXiv: 181 1.07819, 2018
Dibya Ghosh, Abhishek Gupta, Ashwin Reddy, Justin Fu, Coline Devin, Benjamin Eysenbach, and Sergey Levine. Learning to Reach Goals via Iterated Supervised Learning. arXiv e-prints, art. arXiv:1912.06088, December 2019.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off- policy maximum entropy deep reinforcement learning with stochastic actor. arXiv preprint arXiv:1801.01290 2018.
Leslie Pack Kaelbling. Learning to achieve goals. In IJCAI, pp. 1094-1099. Citeseer, 1993.
Timothy Lillicrap, Jonathan Hunt, Alexander Pritzel, Nicolas Heess, Tom Erez, Yuval Tassa, David Silver, and Daan Wierstra. Continuous control with deep reinforcement learning. arXiv preprint WwX:::159000277000 2015.
Plappert Matthias, Marcin Andrychowiez, Alex Ray, Bob McGrew, Bowen Baker, Glenn Powell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, Vikash Kumar, and Wojciech Zaremba. Multi-goal reinforcement learning: Challenging robotics environments and request for research. arXiv preprint arXiv: (00.iv//802.094666 2018.
Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Andrei A Rusu, Joel Veness, Mare Belle- mare, Alex Graves, Martin Riedmiller, Andreas K Fidjeland, Georg Ostrovski, et al. Human-level control through deep reinforcement learning. nature, 51 8(7540):529-533 2015.
Ofir Nachum, Shixiang Shane Gu, Honglak Lee, and Sergey Levine. Data-efficient hierarchical reinforcement learning. In Advances in Neural Information Processing Systems, pp. 3303-3313, 2018.
Xue Bin Peng, Marcin Andrychowicz, Wojeiech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamics randomization. In 2018 IEEE international conference on robotics and automation (ICRA), pp. 1-8. IEEE, 2018.
10

---

Published as a conference paper at ICLR 2021
Matthias Plappert, Marcin Andrychowicz. Alex Ray, Bob McGrew, Bowen Baker, Glenn Pow- ell, Jonas Schneider, Josh Tobin, Maciek Chociej, Peter Welinder, et al. Multi-goal reinforce- ment learning: Challenging robotics environments and request for research. arXiv preprint /802.09900 2018.
Vitchyr Pong. Shixiang Gu, Murtaza Dalal, and Sergey Levine. Temporal difference models: Model- free deep for model-based control. arXiv preprint arXiv:1802.0908/ 2018.
Vitchyr H Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew- fit: State-covering self-supervised reinforcement learning. arXiv preprint arXiv: urXiv:1903.03698 2019.
Ahmed Qureshi, Yinglong Miao, Anthony Simeonov, and Michael Yip. Motion planning net- works: Bridging the gap between learning-based and classical motion planners. arXiv preprint arXiv:1907.00013 2020.
Nikolay Savinov, Anton Raichuk, Raphaël Marinier, Damien Vincent, Mare Pollefeys, Timo- thy Lillicrap, and Sylvain Gelly. Episodic curiosity through reachability. arXiv preprint arXiv: 2018.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approxima- tors. In International conference on machine learning, pp. 1312-1320, 2015.
Joseph Sill. Monotonic networks. In Advances in neural information processing systems, pp. 661- 667, 1998.
Richard S Sutton, Andrew G Barto, et Introduction to reinforeement learning, volume 135. MIT press Cambridge, 1998.
Richard S Sutton, Doina Precup, and Satinder Singh. Between mdps and semi-mdps: A frame- work for temporal abstraction in reinforcement learning. Artificial intelligence, 112(1-2):181- 211. 1999.
Hado Van Hasselt, Arthur Guez, and David Silver. Deep reinforcement learning with double q- learning. arXiv preprint arXiv: 509.06461, 2015.
Srinivas Venkattaramanujam, Eric Crawford, Thang Doan, and Doina Precup. Self-supervised learning of distance functions for goal-conditioned reinforcement learning. arXiv preprint 197.091907.00299,, 2019.
Christopher JCH Watkins and Peter Dayan. Q-learning. Machine learning, $(3-4):279-292: 1992.
Antoine Wehenkel and Gilles Louppe. Unconstrained monotonic neural networks. In Advances in Neural Information Processing Systems, pp. 1545-1555, 2019.
Jesse Zhang, Brian Cheung, Chelsea Finn, Sergey Levine, and Dinesh Jayaraman. Cautious adapta- tion for reinforcement learning in safety-critict settings. arXiv preprint arXiv:2008 06622, 2020.

---

Published as a conference paper at ICLR 2021
A PROOFS OF PROPOSITIONS
Proposition 1: C can be framed Q-function within the MDP formalism, and if x² is optimal in the sense that C*" (8, a, g, h) 2 C* (s, h) for every π and (8, a, 9, ht) E x A x G x N. then C matches the optimal C-function, C", which obeys the following equation:
Ex-pt-lana) G(s,g)
max C* (s', a'EA
if G and 1,
a,))),
otherwise.
Proof:
First, we frame C-functions within the MDP formalism. Consider a state space given by S' 8 G N. where states corresponding to reached goals (i.e. G(s,g) 1) with last
coordinate equal to 0 (i.e. = 0) are considered terminal. The dynamics in this environment are given by:
11 1141 St. St. hr, a.) = p(5 18t, az) (ge+1 = g 1 = 1)
That is, states evolve according to the original d dynamics, while goals remain unchanged and horizons decrease by one at every step. The initial distribution is given by:
so 9o, ho) p(so)p(go. holso).
(8)
where p(sg) corresponds to the original starting distribution and p(go, hy 8q) needs to be specified beforehand. Together, the initial distribution and the dynamics, along with policy = h) properly define a distribution over trajectories, and again, we use IP -g to denote probabilities with respect to this distribution. The reward function r : S' A - IR is given by:
r(s, a, g, h) = G(s.g).
By taking the discount factor to be 1, and since we take states for which G(*,g) = 1 to be terminal, the return (sum of rewards) over trajectory (so. s1....) with ho is given by:
max G(s,,g). t=
(10)
For notational simplicity we take G(st,, g) = 0 whenever t is greater than the length of the trajec- tory to properly account for terminal states. Since the return is binary, its expectation matches its probability of being equal to 1, so that indeed, the Q-functions in this MDP correspond to C*:
Ca (s, a, g, h) = P. (x(hha.))) max G(S g) = 80 0,00 :=0,....f
Now, we derive the Bellman equation for our C-functions. Trivially:
(s, a. g, h) = G(s,g),
(11)
whenever g) = 1 h O. For the rest of the derivation,
assume that G(s.g) 0 and
2 1. We note that the probability of reaching 9 from s in at most steps is given by the probability of reaching it in exactly one step. plus the probability of not reaching it in the first step and reaching it in at most 1 steps thereafter. Formally:
C as,
(12)
O" -", 1) + Be(mp(-)saa) [(1 (4a (s', h, 1)]]
Ex G(s' G(sss, g)] + (sspp()s,,) [[1 G(s', [. [C" a' g. 1)]]
-xr=p()ls,a) (1 (C d' 1)]]
where the last equality follows from the fact that (*'(s', a', h - whenever G(s',g) g) = 1. Putting everything together, we obtain the Bellman equation for C":
C (",s,,,g,1 h)) [Bern(((saa) [Ba' ( (OT((' (s',d', d', ,. h 1)]] if G(*,)) = 0 and h 2 1, (((,g)
otherwise.
(13)
Recall that the optimal policy is defined by the fact that C* > C for any arguments and for any policy π. We can by maximizing equation 13 that, given the C' (1. h 1) values, the optimal policy values horizon h must be nr" (a (a 1) = (a = arg max C* C* (,,,,g,, 1))-
12

---

Published as a conference paper at ICLR 2021
We thus obtain:
C"(s,a,g,h)= Bx-pt-)baa)
max a'EA C''s'' h
-1) if G(8,9) - and 2 1,
G(s,g)
otherwise.
Note that, in Q-learning, the Bellman equation for the optimal policy has been obtained by placing the expectation with respect to a' with max.
Proposition 2: C is non-decreasing in h.
As mentioned in the main manuscript, one might naively think that this monotonicity property should hold for C for any и. However this is not quite the case, as a depends on h and per- verse policy may actively avoid the goal for large values of h. Restricting to optimal C**ffunctons, such pathologies are avoided. As an example, consider an environment with three states, {0, 1,2), and two actions +-1,+1}. The transition rule is 82+1 max(0, min 8t at)). that is, the agent moves deterministically in the direction of the action unless doing so would move it out of the do- main. Goals are defined states. Let π be such that rTals 1,g 2, h 1) [1 1) and sals 1,9 2, 2) = I(a = -1). While clearly a terrible policy, π is such that
C (= 0.a 1,g 2, 2) and C* 0, a 1.g h 3) 0, that C can decrease with h.
Proof: Fix distribution p on the action space. For any policy π (als, g. h), we define new policy T as:
[ h), if (p(a)
i(als, g, h +
(14)
otherwise.
The new policy से acts the same ı for the first steps and the last step it samples an action from the fixed distribution p. The final step can only increase the cumulative probability of reaching the goal, therefore:
C*
Ca (s,,,g.1).
(15)
Since equation 15 holds for all policies n, taking the maximum over policies gives:
C", 1) 2 max (s
2 max (",
C
(16)
B UNBIASEDNESS OF THE CROSS ENTROPY LOSS
For given Sis as Is and h2 from the replay buffer, we denote the right-hand side of equation as
y! rree
Ey Barpp mnar)
max (3 a', d',,;, hi,h; h, - 1) G(ss (s) = 0 and h; 2 1,
y
true
a'EAA
(17)
G()
otherwise.
Note that y/"h tree cannot be evaluated exactly, as the expectation over s' would require knowledge of the environment dynamics to compute in closed form. However, using s/, the next state after in the replay buffer, we can obtain single-sample Monte Carlo estimate of y frue yi as:
max Cā (s6, a' gi, hy 1) if G(si.g)) 0 and h; 2 d'EA G(s..g))
y/
(18)
otherwise.
Clearly y an unbiased estimate of tre However, the optimization objective given by:
Σ C(C as gi, h4), u. rue
(19)
13

---

Published as a conference paper at ICLR 2021
where the sum is over tuples in the replay buffer and C is the loss being used. Simply replacing of with its estimate Vi. while commonly done in Q-learning, will in general result in biased
estimate of the loss:
E on 9b. bf yi "
E (( az 9r, h.). Exllsn,, al....... (B4])
Σ Lellss [C(C] ai Ir, h.), v4)l
(20)
since in general the expectation of function need match the functtion of the expectation. In other words, pulling the expectation with respect to s outside of the loss will in general incur in bias. However, if linear in its second argument, is the case with binary cross entropy but not with the squared loss, then one indeed recovers:
[ (8i, di, Iv, h4), V/ "
Σ Ballena, (8(C ai 9i, ha), 16)
(21)
so that replacing the with y, does indeed recover an unbiased estimate the loss.
C NON-CUMULATIVE CASE
We originally considered a non con-cuuulative version of the C-function, giving the probability of reaching the goal in exactly h steps. We call this function the accessibility function, A" (despite our notation, this is unrelated to the commonly used advantage function), defined by:
A (s, a, 9, h) = I (.)))gg.)) (G(s 9) = 1/50 = s, 5, = a).
(22)
Here the trivial case is only when / = O, where we have:
A (* 0) G(s,g)
(23)
If h >
obtain similar recursion to that of the C-ffnctions. Here no longer assume that states which reach the goal are terminal. The probability of reaching the goal in exactly h steps is equal to the probability of reaching it in h 1 steps after taking the first step. After the first action a, subsequent actions are sampled from the policy n.
A (s, a. h)
F (().g.)) (G(sh. 9) 1|50 = a)
E Eg'r<((lle.a)
E [a''a((1''gghh-11 P (G(sn, = 1/81 = ==aa=aaaa)) =d')]]
FF [a'' [P (((--e--) (G($h-1,9) 1/80 50000 - a d')]]
Es
([ [A" (s', a', .. 1)]]
(24)
By the same argument we employed in proposition 1, the recursion for the optimal A-function, A obtained by replacing the expectation with respect to a' with max. Putting this together with the base case, we have:
Eg s.a)
max ( alss,,,g,, aaggh-h 1) if 2 d'EA
as.
(25)
G(s,g)
otherwise.
Note that this recursion extremely similar to that C", and differs only in the base cases for the recursion. The difference is empirically relevant however for the two reasons that make C* easier to learn: C* is monotonic in h, and the cumulative probability is more well-behaved generally.
D DISCOUNTED CASE
Another approach which would allow a test-time trade-off between speed and reliability to learn the following D-function (D standing for "discounted accessibility"".
(= a, g, 7) = Ex -- = s, 8,00 =
(26)
where the random variable T is the smallest positive number such that G(st g) 1. If no such state occurs during an episode then 7T interpreted as zero. This is the discounted future return of environment in which satisfying the goal returns reward of 1 and terminates the episode.
14

---

Published as a conference paper at ICLR 2021
We may derive recursion relation for this formalism too
G(s'.g) (00)++((1s5)s))0 G(s (1) En [---21 l1s [.. ]d]
(",... (ss
(s,,a) G(s'.g) + +1 -
Ro [D (D'
(27)
By the same argument employed for the C' and A functions, the D-function of the optimal policy is obtained by replacing the expectation over actions with a max, giving
Dd a, (xs.a()s..)) G(s'.g) + +1(1 G(s' 1)) max D' D'd''" (..
(28)
Learning such a D-function would allow test time trade-off between speed and reliability, and might well be more efficient than training independent models for different values of 7. We did not pursue this experimentally for two reasons. Firstly, our initial motivation was to allow some higher-level operator (either human or controlling program) to trade off speed for reliability, and a hard horizon is usually more interpretable than discounting factor. Secondly, we noticed that C-learning performs strongly at goal-reaching in deterministic environments, and we attribute this to the hard horizon allowing the optimal policy to be executed even with significant errors in the C-value. Conversely, Q-learning can typically only tolerate small errors before the actions selected become sub-optimal. D-Jearning would suffer from the same issue.
E CONTINUOUS ACTION SPACE CASE
As mentioned in the main manuscript, C-learning is compatible with the ideas that underpin DDPG and TD3 (Lillicrap et al. 2013 Fujimoto et al. 2018), allowing it to be used in continuous action spaces. This requires the introduction of another neural network approximating deterministic policy, H4 S x G x N + A, which is intended to return juss, 9, h) = arg max, as, h). This network is trained alongside Cj as detailed in Algorithm 2.
We do point out that the procedure obtain horizon-agnostic policy, and thus Abebavior: is also modified from the discrete version. Here, M(s.) g) = maxлеи C" p(s, g. h). h), and:
(s, 9) arg min (*, ((,, ht, g. h): (s, 9, h) 2 (s,
(29)
where we now take ,., (a [a]s s, g) as a point mass at u(s,g, (s.
F ADDITIONAL EXPERIMENTS
In this section study the performance of C-learning across different types of goals. We first evaluate C-learning for the Mini maze and Dubins' car environments, and partition their goal space into easy, medium and hard as shown in Figure [ We experiments for (Mini maze) (Dubins' car) choices of random seed and take the average for each metric and goal stratification, plus/minus the standard deviation across runs.
The Mini maze results are shown in Table 2 We see that C-learning beats GCSL on success rate, although only marginally, with the bulk of the improvement observed on the reaching of hard goals. Both methods handily beat HER on success rate, and note that the path length results in the HER section are unreliable because very few runs reach the goal.
The Dubins' results are shown in Table 3 We that C-learning is the clear winner here across the board, with GCSL, achieving a somewhat close success rate, and HER ending up with paths which are almost as efficient. Note that this result is the quantitative counterpart to the qualitative trajectory visualizations from Figure 4c, As mentioned in the main manuscript, we also tried ex- plicitly enforcing monotonicity of our C-functions using the method Sill (1998), but we obtained success rates below 50% in Dubins' car when doing so.
We also compare C-learning to naive horizon-awarc Q-learning, where instead of sampling h as in C-learning, where consider as part of the state space and thus sample it along the state in the replay buffer. Results are shown in the left panel of Figure 6 We see that our sampling of h achieves the same performance in roughly half the time. Additionally, we compare against sampling h uniformly in the right panel of Figure and observe similar results.
15

---

Published as a conference paper at ICLR 2021
Algorithm 2: Training C-learning (TD3) Version
Parameter: Nexplore: Number of random exploration episodes
Parameter: NGD: Number of goal-directed episodes
Parameter: Nurai: Number of batches train on per goal-directed episode
Parameter: Neopy: Number of batches between target network updates
Parameter: at Learning rate
0, 0g + Initial weights for Ca. C
0, 8/2 f 4-.1... 82. 02
// Copy weights to target network
4- Initial weights for ph
DD- []
1/ Initialize experience replay buffer // Counter for training batches
nbb +0
repeat Nexplore times
+ get rollout((Tradaa
// Do a random rollout // Save the rollout to the buffer
D.append(E)
repeat NGn times
10
g f goal_sample(ng
// Sample a goal 11 Try reach the goal // Save the rollout
E < get.rollout
(Tehavior) (Tbeavvvvo))))
D.append(E))
12
repeat Ntrain times
14
= {s,, Oj Sy 9b. h B1 + samplebbatch(2
// Sample a batch
{ |8| t get.targets
15
Estimate RHS equation 18 log Cū2 (st, ai It, h2) + (1 14) log (1 Cū (s,,4,0,, h,)) We log Cū₁ (st, ai, Gi, h₂) + (1 11:))))) log (1 - Cū (si, ai Pi ai, h:))
|8| s-ll
16
Lg
17
18
0 + VV 21
// Update weights
19
0g + 02 aoLL
// Update weights
20
mb mod policy_delay 0 then
Lactor - B
1 Cū, (8i, Mo 9r, hi), gi, h4)
21
22
② x- Φ - 0 V # Lecttor
// Update actor weight
0' 01
T) + 0f
// Update target networks
24
0 + 0g * - T) + 02 x
Φ Φ (1 - r) + 0'
25
27
Rb + 74b +1 1
// Trained one batch
Figure 5: Partitioning environments into easy (green), medium (yellow) and hard (red) goals to reach from given starting state (blue). The left panel shows mini maze, and the right shows Dubins' car.
16

---

Published as a conference paper at ICLR 2021
Table 2: Relevant metrics for the Mini maze environment, stratified by difficulty of goal (see Figure S (left) from appendix F Runs in bold are either the best on the given metric in that environment, have score within the error bars of the best.
METHOD CAR
SUCCESS
EASY
44%
79%
8F. 5255 =t 0,8055
M8 5817%
97%
86 89%
5.85 0.02
14.84 0.05
25.76 i:
a: 0.80
OCSL.
17%
725 18%
74%
1.40%
84 00%
0.61%
5.05
0.02
23.46 + 0.22
13:10 0.02
HER
22.78% 75%
23.63 + 9.685
5.01% 7.70%
17.87% 7.50%
4.73 + 0.63
13.94 1.40
28.50 0.00
11.58 2.12
Table 3: Relevant metrics the Dubins' car environment, stratified by difficulty goal (see Figure S (right) from appendix F Runs in bold are either the best on the given metric in that environment, or have mean score within the eτrоr bars of the best.
METHOD CAE
EASY
MED
SUCCESS RATE
HARD
ALL 79.09%
EASY
MED
PATH LENGTH
HARD
ALL
97.44%
2.23%
86.1655
0.00
6114%
1550
0.90 20.13 à 1,66
GCSL
50.85% 4.70%
76.02%
7.11%
70.88%
11.05%
6,355
17.58
9.50
HER
51.79% 12.6005
55.38%
3.77%
47.95%
10.20%
51.25%
6.48%
25.72
We also compare C-learning against TDMs Pong et al. ( for motion planning tasks. Results are in Figure 7 As mentioned the main manuscript, TDMs assume dense reward function, which C-learning does not have access to. In spite of this, C--laaming significantly outperforms TDMs.
Finally, we also compare against the non-cumulative version of C-learning (A-learning), and the discount-based recursion (D-learning) in Dubins' car. For D-learning, we selected y uniformly at random in [0, 1]. Results are shown in table We can see that indeed, C-learming outperforms both alternatives. Curiously, while underperformant, A-learning and D-learning seem to obtain shorter paths among successful trials.
G EXPERIMENTAL DETAILS
C-learning for stochastic environments: As mentioned in the main manuscript, we modify the replay buffer in order to avoid the bias incurred by HER sampling (Matthias et al.) 2018) in non- deterministic environments. We sample goals independently from the chosen episode. We sample Ii to be a potentially reachable goal from s; in h2 steps. For example, if given access to distance d between states and goals such that the distance can be decreased at most by 1 unit after a single step, we sample gi from the set of g's 's such that d(s;; g) < h, Moreover, when constructing yi (line of algorithm 1), if we know for a fact that Si cannot be reached from sf in h; 1 steps, we output O instead of max.' Ci-(s) (6/, a', Di. hy 1). For example, d(s', 9:) > h2 - allows to set y 0. We found this practice, combined with the sampling of gi described above, to significantly improve performance. While this requires some knowledge of the environment, for example a metric over states, this knowledge is often available in many environments. For frozen lake, we use the L1 metric to determine if goal is not reachable from state, while ignoring the holes in the environment so as to not use too much information about the environment.
100
80-
60-
CleemtingTD33
CleamiigiT03) (oanmiigTT33)jnnattt
celeerniig//nnnzee incl.
0.0
0.6
0.6
1.0
0.0
0.4
0.6
1.0
stop
cnv stop
Figure 6: Success rate throughout training of C-learning (blue) and naive horizon-aware Qllearning (red) on PetchPiikAndPlacce- (left); and C-leaming (blue) and C-learning with uniform h sampling (red) on FetchPickAndPlacevI (right).
17

---

For all methods, we train for 300 episodes, each one of maximal length 50 steps, we use learning rate 10-3 3, a batch size of size 256, and train for 64 gradient steps per episode. We use a 0-1-greyy for the behavior policy. We use neural network with two hidden layers of respective sizes 60 and 40 with ReLU activations. We use 15 fully random exploration episodes before we start training. We take p(so) as uniform among non-hole states during training, and set it a point mass at (1,0) for testing. We set p(g) as uniform among states during training, and we evaluate at every goal during testing. For C-learning, we use ε = and copy the target network every 10 steps. We take the metric d to be the L1 norm, completely ignoring the holes so as to not use too much environment information. For the prrizon-innependeed point out that, while C-learning did manage to recover the safe path for large h, it did not do always Published as a conference paper at ICLR 2021
100
ClgamingT03)
35
30
60-
15-
20
CleaninggTD3
TDM
0.0
0.5
1.0
1.3
2.0
2.5
3.0
ep.sodes
145
Figure 7: Success rate throughout training C-Jearning (blue) and TDMs (red) FeechPickAndPPacee-W (left) and MaandMaaiulateeeeFFllll (right).
Table 4: Relevant metrics for the Dubins' car environment, stratified by difficulty of goal (see Figure 5 (right) from appendix F Runs in bold are either the best on the given metric in that environment, have mean within the error hars of the hest.
METHOD
EASY
SUCCESS RATE
ALL
FASY
HARD
C-leaming
97 44% 2 23% 03.
86 66.16% 4.06%
$1.14%
1 4.02%
86 16%
34%
1
16 1.16110 1-07
21
16.45 0.59
A-leaming D-learning
3.905
84.74 1. 4.41%
62.89
16.50%
6.7%%
5.84
13:29 0.22
1694 1
12:3 1283100.3 7.01 1.082
66.325 4 12.27%
36.9995
15.71%
2.27%
3.1%
50.11%
6.47%
5.02 0.25
11.44:1000
13.97 0.000
G.1 FROZEN LAKE
policy, we used H {1, 2........ 50) and a = 0.9. We do
do so: we suspect that the policy of going directly up more likely to be explored. However, we never observed GCSL. taking the safe path.
G.2 MINI MAZE
We again train for 3000 episodes, now of maximal length 200. We train 32 gradient steps per episode, and additionally decay the exploration noise of the C-learning behavior policy throughout training according to (15/(1 + naD h 1000). The network we used has two hidden layers of size 200 and 100 with ReLU activations, respectively. While the environment is deterministic, we use the same replay buffer as for frozen lake, and take the metric d to be the Lı norm, completely ignoring walls. We found this helped improve performance and allowed C-learning to still learn to reach far away goals. We also define H(s,g) g) = {Ils gll1, ||s gll1 + 1, 1..... hmax), ). with hmax = 50, as the set of horizons over which we will check when rolling out the policies. We take p(5o) as a point mass both for training and testing. We use p(g) during training as specified in Algorithm
and evaluate all the methods on a fixed set of goals. Additionally, we lower the learning rate by a factor of 10 after 2000 episodes. All the other hyperparameters are in frozen lake. Figure 5 shows the split between easy, medium, and hard goals.
G.3 DUBINS' CAR
We train for 4500 episodes, each one with a maximal length of 100 steps and using 80 gradient steps per episode. We use neural network with two hidden layers of respective sizes 400 and 300 with ReLU activations. We take the metric to be the Los norm, completely ignoring walls, which we only use decide whether or have reached the goal. We take p(so) as point mass both for
18

---

Published as a conference paper at ICLR 2021
training and testing. We use p(g) during training specified in Algorithm 1, and evaluate all the methods on a fixed set of goals. All other hyperparameters are as frozen lake. The partition of goals into easy, medium and hard is specified in Figure where the agent always starts at the upper left corner.
G.4 FETCHPICKANDPLACE-V
We train with a learning rate of 0.0001 and batch size of 256. We take 64 gradient steps per episode, and only update & with half the frequency of B. We use 40000 episodes for FetchPick.AnnPPlce-V/ All the other hyperparameters are as in Dubins' car.
G.5 HANDMANIULLATPPEFFULLYY
We train with learning of 0.0001 and batch size of 256. We take 80 gradient steps per episode, and only update ø with half the frequency of f. We use 60000 episodes for HandManipuultteeoFFul vO, All the other hyperparameters are in Dubins' car.
19


Reviews:
[{"review_id": "Wpah49Rxi1_", "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": "The paper proposes C-learning, which is an essentially a horizon aware Q-learning. In a nutshell, the authors proposes changing the Q function from Q(s, a) to C(s, a, h) where s is the state, a is the action and h is allowed time horizon i.e. the agent should get to the goal state using less than h states. Since C can be framed as a modified Q, the authors demonstrate that familiar Q-learning properties such as Bellman property and backprop can be used for C-learning. \n\nThe paper is generally well-written and is easy to understand. The authors evaluated the performance of the proposed method on multiple hand crafted tasks which allow for multiple way of reaching to the goal with a varying hard time limit. The authors compared their method with GCSL (Ghosh et al., 2019) and HER (Andrychowicz et al., 2017) demonstrating an improved performance. The included website includes extra evaluations on a few robotic tasks.\n\nThe paper is suffering from multiple shortcomings:\n1) Motivation. Although I agree that the proposed problem is important, the authors could provide more motivation. The listed examples demonstrate the problem however there is no real life example that visualizes the *importance* of the problem. \n\n2) Comparison with existing goal reaching methods. As mentioned by the authors, the reachability problem can be formulated as in an existing RL framework and therefore the proposed method can also be compared with existing RL methods. The comparison section tries to do this but unfortunately it falters. I believe the comparison section should include existing methods with modified RL formulation so they are horizon aware (e.g. by including the horizon limit as input and training them by randomly selecting it). Doing this will highlight *why* C-learning is required and a simple Q-learning method cannot solve the problem at hand. There are other issues in Section 4 as well. For example Fig 7 has incomplete curves, the metrics are not clearly defined and it is not clear how the baselines have been evaluated. \n\n3) Task selection. The paper evaluated the performance of their model on toy environments which is always a good idea. That enables the authors to clearly differentiate their proposed method from previous work (which is missing as I mentioned in 2). But, at the end of the day, it is important to visualize that the proposed method works on real challenges which is missing. I should mention that the website includes more realistic tasks and addresses this problem to some sense but the paper in its current form lacks.\n\nOverall, I think the paper can use clearer motivation, comparison and evaluation.\n\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "RAclMCQYkeW", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "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 highlights a problem in existing goal-reaching RL agents, in that they do not explicitly allow for trading off speed (how fast you reach the goal) and reliability (how often you reach the goal). While this tradeoff is implicitly determined by the discount factor in training, the paper asserts that in practice the ability to more flexibly determine this during inference is more desirable. Given this shortcoming of existing work, the paper then proposes \"C-Learning\" which learns a policy conditioned on both a goal and a desired horizon (h) -- i.e., a time limit on the policy. The paper presents favorable results of C-Learning on a few simulated domains compared to existing goal-reaching RL agents.\n\nStrengths:\n\n-- The proposed problem in standard goal-reaching agents is convincing.\n\n-- I appreciate the level of detail in the algorithmic description along with the pseudocode. It was mostly easy to follow, except in a few small places (see weaknesses).\n\n-- The experiments appear to have been performed carefully, with a helpful demonstration of the trade-off enabled by the proposed algorithm.\n\nWeaknesses:\n\n-- I found the small section about \"Horizon Independent Policies\" very confusing. For example, in the definition of M, since we know C* is increasing with h, does the max_h just reduce to setting h=infty. And if so, isn't the maximal value simply either 0 or 1 (measuring reachability)? And how is this max efficiently computed? More generally, why is this specific gamma-conditioned behavior policy necessary?\n\n-- The various algorithmic details in 3.1 are worrying, as they suggest that a number of things beyond the basic C-Learning paradigm are necessary in practice. While I understand that this is unavoidable in any algorithm, some of these algorithmic details are exceedingly specific to the domain. For example, \"C-function clipping\" relies on knowing reachability in the environment, which is arguably as difficult as learning a goal-reaching policy in many cases!\n\n-- The introduction mentions evaluating on domains from Nachum 2018, Peng 2018, and Zhang 2020. However, as far as I can tell, none of these domains are actually evaluated on? If you're not going to evaluate on these domains, I suggest removing this sentence from the paper.\n\n-- While I am convinced of the problem the paper claims to solve, I am not convinced that C-learning is necessarily the best solution. I can imagine a number of other approaches which may perform better, worse, or about the same. For example, why not simply learn a policy pi(a|s, g, gamma) for all possible gamma in [0, 1)? Or alternatively, why not use one of the risk-sensitive policy learning approaches in the safe RL or constrained MDP literature (e.g., Lyapunov Safe RL)?\n\n-- Learning a horizon-conditioned Q function was also proposed in TDM (https://arxiv.org/abs/1802.09081). How does C-learning relate and compare to this existing technique?", "extra_scores": {}, "extra_text": {}}, {"review_id": "LDPbTxIm-3", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "# Update after the rebuttal\n\nThank you for including the comparison to TDMs - the results are now much more convincing.\nI think this should be one of the main results in the paper (which should be presented in the main text rather than in the appendix).\nAlso, I'd suggest revising the paper to highlight new contributions compared to TDMs in the intro/method section. \nI increased the score assuming that the authors will reflect my final suggestions.\n\nRegarding distributional RL and cross-entropy loss, distributional RL does allow a probability distribution as target (not just either 0 or 1 and just like yours). I'd suggest the authors to take a closer look at the paper and clarify differences (I still think the cross entropy loss is a special case of distributional RL with discount factor of 1).\n\n# Summary \nThis paper proposes cumulative accessibility functions that estimate horizon-aware value function for goal-reaching RL problems. Specifically, the proposed C-function estimates the probability of reaching the goal state within a time budget (say $h$ steps). The paper derives Bellman-equation for C-function along with several properties. The experimental results on several continuous control domains show that the proposed method can balance between reliability and speed at test-time. \n\nPros\n* The paper presents a new method that can balance between reliability and speed for goal-reaching RL problems.\n\nCons\n* The novelty seems limited because the proposed method is quite similar to [1]. \n* Comparison to HER and GCSL is not fully convincing. \n\n# Novelty\n* My major concern is that this paper does not cite or discuss the most relevant prior work [1]. The proposed C-function seems like a special case of the TD model proposed by [1], which also learns Q(s, a, g, t) as a distance estimation ||s-g||. The TD model has almost the same Bellman equation as Equation (3) and it can also trade-off reliability and speed at test-time. It seems like the only difference is the definition of the reward function (distance v.s. 1/0). It is important for this paper to compare against [1] throughout the paper.\n* The cross entropy loss (Equation 5) is not particularly novel, because it can be viewed as Distributional RL without discounting. \n\n# Quality\n* The empirical result shows the trade-off between reliability and speed nicely, which motivates the proposed method well. \n* The comparison to HER and CGSL was mostly conducted on non-standard domains. The claim about faster learning would be more convincing if the experiment was conducted on more standard domains (e.g., MuJoCo, robotics manipulation) \n\n# Clarity\n* The motivation behind using a horizon-independent policy for behavior is not clear. \n* The problem considered in this paper is not clearly defined. Is this self-supervised learning setting (where there is no final goal) or goal-reaching RL setting? The Algorithm 1 sounds like the former, while the experiment seems like the latter.\n\n[1] Vitchyr Pong et al., Temporal Difference Models: Model-Free Deep RL for Model-Based Control.\n[2] Marc G. Bellemare et al., A Distributional Perspective on Reinforcement Learning.\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EeyVnsLatJ0", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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\nThe paper proposes learning horizon-aware goal conditioned policies by integrating horizon dependency in value-based methods. The new formalism defines the value function (cumulative accessibility function) as the probability of reaching a certain goal from a given state within a fixed horizon. This allows trading-off speed and reliability.\n\n### Main contributions\n- The C-learning is a different approach to integrate temporal abstractions in value-based method.\n- The derivation of the cumulative accessibility function in analogy to the standard Q-learning is principled and very interesting.\n- The proposed approach is compatible with the algorithmic adaptations of Q-learning to continuous action spaces.\n\n### Main concerns (and comments)\n- The exploration problem has been ignored in this work while it is quite central. The standard Q-learning (if in the undiscounted return like your case) would go for the higher expected return which would correspond to the policy of the highest success probability, when provided with a satisfying exploration. In addition to this, alternative standard methods are horizon-penalized (e.g. through the discount factor). These point should be considered in this study and in the comparison to other methods.\n- It is claimed that encoding monotonicity in h in the architecture hurt performance. A hypothesis is provided by not tested. More importantly, did the monotonicity emerge naturally from training ?\n- Regarding C-function clipping. How is \"if we know for a fact that g_i cannot be reached ...\" implemented practically ? It is acknowledged that this requires \"some knowledge of the environment, for example a metric over states\". However, such a metric even when available does not always say how many steps separate the states (i.e continuous spaces).\n- \"[...] but also shown its monotonicity, a crucial component which facilitates neural network learning in the higher-dimensional goal-horizon space\" : can you elaborate on this ? Is this claim referring to some property or known result on \"neural network learning\" ? If so any references ?\n- \"Surprisingly, GCSL learns to take the high-risk path, despite Ghosh et al.’s intention to incentivize paths that are guaranteed to reach the goal\": Does your method uses a goal sampling strategy that provides more options to the agent (like a richer exploration would do) ? In other words, how much of the performance depends on the goal sampling strategy (ablation study) ?\n- In Dubin's car, the set of reachable goals from a given state within some horizon does not have a trivial structure, how was the goal sampling implemented here ?\n- Regarding the C-function clipping, can we imagine a goal conditioned Q-learning baseline that would be trained with a similar clipping, i.e how much of the performance is explained by this inductive bias (the C-clipping) ?\n- \"This is also impressive, as we are learning a more complicated objective, which contains information not recoverable by the alternatives.\" : This comment is misleading. Even if the objective is more complicated, the proposed method learns a more structured function and benefits (for free) from valuable information (like the C-function Clipping) while \"alternatives\" have to implicitly learn such information.\n- \"We did train for longer and observed decreased performance\" : Does this mean the performance decreases for all the curves that were not plotted till convergence ? How do you explain this ? Also, Figure 7 shows averages without standard deviations.\n- \"We also note that, strangely, while C-learning dominates easy and medium goals in mini maze, it struggles to reach hard goals. We found this particularly puzzling given the good performance in the more challenging environments.\" : This deserves more attention and might suggest to consider the exploration problem (mentioned in the first comment) more seriously.\n\n### Minor comment\n- The objective (eq. 5) is quite confusing. Should it be minimized or maximized ?\n- How does this compare to planning with options over different horizons ?", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper introduces C-learning, an approach to integrate temporal abstractions to value-based methods. Specifically, it uses accessibility functions that estimate horizon-aware value functions for goal-reaching RL problems. Such an approach allows trading-off reliability and speed. After careful consideration I’m recommending the acceptance of this paper. The main weaknesses raised by the reviewers were addressed during the rebuttal, including the improvement of presentation and the introduction of new experiments and baselines. There were not many actionable criticisms left after the discussion and the reviewers acknowledged that the paper has improved since its first version.

For the final version of the manuscript, I recommend the authors to further take R2’s comments/suggestions into consideration. Further incorporating the discussion about TDMs in the main text will improve clarity, better position the paper, and increase its likelihood of having impact.

Decision: Accept (Poster)