C-Learning: Learning to Achieve Goals via Recursive Classification
Authors: Benjamin Eysenbach
Ruslan Salakhutdinov
Sergey Levine
Venue: ICLR 2021 Poster (2021)
Keywords: reinforcement learning
goal reaching
density estimation
Q-learning
hindsight relabeling

Abstract: We study the problem of predicting and controlling the future state distribution of an autonomous agent. This problem, which can be viewed as a reframing of goal-conditioned reinforcement learning (RL), is centered around learning a conditional probability density function over future states. Instead of directly estimating this density function, we indirectly estimate this density function by training a classifier to predict whether an observation comes from the future. Via Bayes' rule, predictions from our classifier can be transformed into predictions over future states. Importantly, an off-policy variant of our algorithm allows us to predict the future state distribution of a new policy, without collecting new experience. This variant allows us to optimize functionals of a policy's future state distribution, such as the density of reaching a particular goal state. While conceptually similar to Q-learning, our work lays a principled foundation for goal-conditioned RL as density estimation, providing justification for goal-conditioned methods used in prior work. This foundation makes hypotheses about Q-learning, including the optimal goal-sampling ratio, which we confirm experimentally. Moreover, our proposed method is competitive with prior goal-conditioned RL methods.

Published as a conference paper at ICLR 2021
C-LEARNING: LEARNING TO ACHIEVE GOALS VIA RECURSIVE CLASSIFICATION
Benjamin Eysenbach CMU, Google Brain
Ruslan Salakhutdinov CMU
Sergey Levine UC Berkeley, Google Brain
beysembal cs cmu. edu
ABSTRACT
We study the problem of predicting and controlling the future state distribution of autonomous agent. This problem, which can be viewed reframing of goal-conditioned reinforcement learning (RL), is centered around learning a con- ditional probability density function over future states. Instead of directly estimat- ing this density function, we indirectly estimate this density function by training classifier to predict whether an observation comes from the future. Via Bayes' rule, predictions from our classifier can be transformed into predictions over future states. Importantly, an off off-policy variant of our algorithm allows to predict the future state distribution of new policy, without collecting new experience. This variant allows us to optimize functionals of a policy's future state distribution. such as the density of reaching particular goal state. While conceptually similar to Q-learning, our work lays a principled foundation for goal-conditioned RI. as density estimation, providing justification for goal-conditioned methods used in prior work. This foundation makes hypotheses about Q-learning, including the optimal goal-sampling ratio, which confirm experimentally. Moreover, proposed method is competitive with prior goal-conditioned RL methods
INTRODUCTION
In this paper, aim to reframe the goal-conditioned reinforcement learning (RL) problem one of predicting and controlling the future state of the world. This reframing is useful not only because it suggests new algorithm for goal-conditioned RL, but also because explains commonly used heuristic in prior methods, and suggests how to automatically choose an important hyperparameter. The problem of predicting the future amounts learning a probability density function over future states, agnostic of the time that a future state is reached. The future depends on the actions taken by the policy, so our predictions should depend on the agent's policy. While we could simply witness the future, and fit a density model to the observed states, we will be primarily interested in the following prediction question: Given experience collected from one policy, can we predict what states a different policy will visit? Once we can predict the future states of different policy, we can control the future by choosing a policy that effects a desired future.
While conceptually similar to Q-learning, our perspective is different in that we make reliance on reward functions. Instead, an agent can solve the prediction problem before being given a reward function, similar to models in model-based RL. Reward functions to construct and evaluate, so a fully autonomous agent can learn to solve this prediction problem solve many different
require human supervision
before being provided any human supervision, and reuse its predictions downstream tasks. Nonetheless, when a reward function is provided, the agent can estimate its expected reward under the predicted future state distribution. This perspective different from prior approaches. For example, directly fitting a density model to future states only solves the prediction problem in the on-policy setting, precluding us from predicting where a different policy will go. Model-based approaches, which learn an explicit dynamics model, do allow us to predict future state distribution of different policies, but require a reward function or distance metric to learn goal-reaching policies for controlling the future. Methods based on temporal difference (TD) learning (Sutton 1988) have been used to predict the future state distribution (Dayan 1993.
Project website with videos and code: https::/ben-eyseeeeee thub. 10/ coar__ernning/

---

Published as a conference paper at ICLR 2021
Szepesvari al. 2014 Barreto et al. 2017) and to learn goal-reaching policies (Kaebbiigg 1993
Schaul et al. 2015). Section 3 will explain why these approaches do not learn a true Q function in continuous environments with sparse rewards, and it remains unclear what the learned function corresponds to. In contrast, our method will estimate a well defined classifier.
Since it is unclear how to Q-learning to estimate such a density, we instead adopt a contrastive approach, learning a classifier to distinguish "future states" from random states, akin to Gutmmann & Hyvärinen (2010). After learning this binary classifier, we apply Bayes' rule to obtain probability density function for the future state distribution, thus solving our prediction problem. While this initial approach requires on- on-policy data, we then develop a bootstrapping variant for estimating the future state distribution for different policies. This bootstrapping procedure is the core of our goal- conditioned RI. algorithm.
The main contribution of our paper is a reframing of condiiondi RL. as estimating the probabil- ity density over future states. We derive a method for solving this problem, C-learning, which we use to construct complete algorithm for goal-conditioned RL. Our reframing lends insight into goal- conditioned Q-learning, leading to a hypothesis for the optimal ratio for sampling goals, which we demonstrate empirically. Experiments demonstrate that C-learning more accurately estimates the density over future states, while remaining competitive with recent goal-conditioned RL methods across a suite of simulated robotic tasks.
2
RELATED WORK
Common conditioed RL algorithms are based on behavior cloning (Gosh et al., 2019 Ding
eet al. 2019:
Gupta et al., 2019: Eysenbach et al. 20000
Lynch et al., [020 Oh et al. 2018 Sun
ct al.
2019), model-based approaches (Nair et al.] 2020; Ebert et al.) 2018). Q-learning (Kaelbling
1993 Schaul et al. 2015 Pong et al.] 2018). and semi-parametrie planning (Savinov et al.) 2018
Eysenbach et al.] 2019, Nasiriany et al., 2019 Chaplot et al.] 2020). Most prior work on goal- conditioned RL relies manually-specified reward functions or distance metric, limiting the ap- plicability to high-dimensional tasks. Our method will be most similar to the Q-learning methods, which are applicable off-policy data. These Q-learning methods often employ hindsight relabel- ing (Kaelbling 1993 Andrychowicz et al.) (017). whereby experience is modified by changing the commanded goal. New goals are often taken be a future state or a random state, with the precise ratio being a sensitive hyperparameter. We emphasize that our discussion of goal sampling concerns relabeling previously-collected experience, not on the orthogonal problem of sampling goals for exploration (Pong et al. 2018 Fang et al. 2019 Pitis et al. 2020
Our work is closely related to prior methods that use TD-Icaning to predict the future state distri- bution, such as successor features (Dayan] [1993; Barreto et al. 2017]] (2019) Szepesvari et al.) 2014) and generalized value functions (Sutton & Tanner, [005 [Schaul et |015| Sccrroecke & Isbell, 2020). Our approach bears a resemblance to these prior TD-learnin methods, offering insight into why they work and how hyperparameters such as the goal-sampling ratio should be selected. Our approach differs in that it does not require a reward function or manually designed relabeling strate- gies, with the corresponding components being derived from first principles. While prior work on off-policy evaluation (Liu al. 2018) Nachum al. 2019) also aims to predict the future state distribution, our work differs is that we describe how to control the future state distribution, leading to goal-conditioned RL algorithm.
Our approach is similar to prior work on noise contrastive estimation (Gutmann & H Hyvärinen 2010), mutual-information based representation learning (Oord et al. 2018; Nachum al. [2018). and vari-
ational inference methods (Bickel et al., 2007 Uehara et al. 2016) Dumoulin et al. 2016 Huszár
2017 Sønderby al. (016)) Like prior work on the probabilistic perspective RL Kappen 2005
Todorov 2008 Theodorou et al. 2010 Ziebart [2010) Rawlik et al. [2013] Ortega & Braun 2013
Levine 2018). we treat control as a density estimation problem, but our main contribution or-
thogonal: we propose method for estimating the future state distribution, which can be used as
subroutine in both standard RL and these probabilistic RL methods.
3 PRELIMINARIES
We start by introducing notation and prior approaches to goal-conditioned RL. We define a con- trolled Markov process by an initial state distribution pı (s1) and dynamics function p(s St, at).
2

---

Published as a conference paper at ICLR 2021
We control this process by a Markovian policy To (a, |s) with parameters B. We use To(aa St. g) to denote a goal-oriented policy, which is additionally conditioned on a goal g E S. We use $1t to denote the random variable representing future observation, defined by the following distribution: Definition 1. The future "y discounted state density function is
0C
(se+ St, ac) _ (1 7)
Σ
( = Set St, ac),
A=1
where St+A denotes the state exactly A in the future, and constant (1 - ?) ensures that this density function integrates I.
This density reflects the states that an agent would visit if we collected many infinite-length trajec- tories and weighted states in the near-term future more highly. Equivalently, p(s++) can be seen as the distribution over terminal states we would obtain if we (hypothetically) terminated episodes at a random time step, sampled from a geometric distribution. We need not introduce reward function to define the problems of predicting and controlling the future.
In discrete state spaces, we can convert the problem of estimating the future state distribution into RL problem by defining reward function Tat. (s).a) (ss St+), and terminating the episode when the agent arrives at the goal. The Q-function, which typically represents the expected discounted sum of future rewards, can then be interpreted (scaled) probability mass function:
Q" at, S8+) = E Ex're (St, ax) = ->'Pa(Be
1
(se+ St, at)-
However, in continuous state spaces with some stochasticity in the policy dynamics, the proba- bility that any state exactly matches the goal state is zero.
Remark 1. In a stochastic, continuous environment, for any policy π the O-function for the reward function Tek- 1(st = St+) is always zero: Q" (St. aq. Sc+) 0.
This Q-function is not useful for predicting or controlling the future state distribution. Fundamen- tally, this problem arises because the relationship between the reward function, the Q function, and the future state distribution in prior work remains unclear. Prior work avoids this issue by manu- ally defining reward functions (Andrychowicz et al., (017) or distance metrics (Schaul et al. 2015 Pong et al. 2018 Zhao et al.) 2019] Schroecker & Isbell] 2020). An alternative is to use hindsight relabeling, changing the commanded goal to be the goal actually reached. This form of hindsight relabeling does not require a reward function, and indeed learns Q-functions that are not zero (Lin) et al. 2019). However, taken literally, Q-functions learned in this way must be incorrect: they do not reflect the expected discounted reward. An alternative hypothesis is that these Q-functions reflect probability density functions over future states. However, this also cannot be true:
Remark For any MDP with the sparse reward function 1(s, = =s++) where the episode terminates upon reaching the goal, Q-learning with hindsight relabeling acquires Q-function in the range Q*(ss, (St, Se+) E [0, 1}. but the probability density function p4 (su+ 18,, ax) has a range [0, oo).
For example, if the state space is S = [0, 1. then there must exist some state st+ such that (*(ss, ac, St+1) <. < ( s1+ sc, ac). See Appendix H for two worked examples. Thus, Qelernning with hindsight relabeling also fails to learn the future state distribution. In fact, it is un- clear what quantity Q-learning with hindsight relabeling optimizes. In the rest of this paper, we will define goal reaching in continuous state spaces in way that is consistent and admits well-defined solutions (Sec. 4. and then present a practical algorithm for finding these solutions (Sec. 5).
4 FRAMING GOAL CONDITIONED RL AS DENSITY ESTIMATION
This section presents novel framing of the goal-conditioned RL problem, which resolves the ambi- guity discussed in the previous section. Our main idea is to view goal-conditioned RL as a problem of estimating the density pI (st+ St, ax) over future states that policy will visit, problem that Q-lcarning does not solve (see Section Section 5 will then explain how to use this estimated distribution the core of complete goal- coal-conditioned RI algorithm.
Definition 2. Given policy n. the future state density estimation problem is to estimate the y discounted state distribution of π: 17 (St+ St, a4) (St+ St, at).
3

---

Published as a conference paper at ICLR 2021
The next section will show how to estimate fø. Once have found fū we can determine the probability that a future state belongs to a set S1+ by integrating over that set: P(st+ E S(+) = [s+ St, at) [st+ E Sc+)dst+ Appendix [A discusses a similar relationship with partially observed goals. There is a close connection between this integral and goal- coal-conditioned Q-function:
Remark 3. For a goal g, define a reward function as an e-ball around the true goal: rg(St, ar) = (st++ B(g; e)). Then the true Q-fanction is a scaled version of the probability density, integrated over the set Si+ B)g (St, at. 9) = EE, DEr gr a)] = =(1 (1-19 (P) E E)):
C-LEARNING
We now derive an algorithm (C-learning) for solving the future state density estimation problem (Def. 2 First (Sec. [5 assume that the policy fixed, and present on-policy and off-policy solutions. Based on these idcas, Section 5.2 builds a complete goal-conditioned RL algorithm for learning an optimal goal-reaching policy. Our algorithm bears resemblance to Q-learning, and our derivation makes two hypotheses about when and where Q-learning will work best (Sec. 5.3
5.1 LEARNING THE CLASSIFIER
Rather than estimating the future state density di- rectly, we will estimate it indirectly by learning a classifier. Not only is classification generally an eas- ier problem than density estimation, but also it will allow us to develop an off off-policy algorithm in the next section. We will call our approach C-learning- We start by deriving an on-policy Monte Carlo al- gorithm (Monte Carlo C-learning). and then mod- ify it to obtain an off-policy, bootstrapping algorithm (off-policy C-learning). After learning this classifier, we can apply Bayes' rule to convert its binary pre- dictions into future state density estimates. Given a distribution over state action pairs, at), we de- fine the marginal future state distribution p(se+)
Algorithm 1 Monte Carlo C-learning
Input trajectories {Ti
Define p(s, a) k Unif( (s, a (a,a)r):
p(s(+) + Unif( { (s))
while not converged do
Sample Sr, ar ~ p(s, a), 81 ~ p((c+),
(0)
A GBOM(1 7)
(1)
Set goal 88 x 8t+A
F(0) + log C7 (F 1
8t, a2 Si+
(1)
+ log C3 (F= 0 8r: at 8(4)
(0)
0 V.
Return classifier Co
I pI_ (se+ St, a ((st, at ddsd The classifier takes as input a state-action pair (st,ae) together with another state St+. and predicts whether st+ was sampled from the future state density p4 (St+ (t. at) (F 1) or the marginal state density
p(s++) (F = 0). The Bayes optimal classifier is
p7 (St+
St. at)
p(F = St. at,
=
p (st+
St. at) p(se+)
(1)
Thus, using (F = 1 st. a S to denote our learned classifier, we can obtain an estimate fø (st+ St, a,) for the future state density function using our classifier's predictions as follows:
(st+ St, ar) = C% (F Se. at. St+) C% (F = 0 Se. at. Se+)
p(s++).
(2)
While estimated density fo depends the marginal density p(se+), goal-conditioned RL algorithm (Sec. 5.2 will note require estimating this marginal density. In particular, we will learn a policy that chooses the action a that maximizes this density, but the solution to this maximization problem does not depend on the marginal p(se+).
We now present an on-policy approach for learning the classifier, which we call Monte Carlo C- Learning. After sampling a state-action pair (St, at) p(s,, at), we can either sample a future state
(0) si pT (St+ St, at) with a label F 1, or sample set p(((+) with label F = 0. We then train the classifier maximize log likelihood (i.e., the negative cross entropy loss):
F(0) 2 Be, (p) [log C% = St, a,, (1) (11) axr [log C7 (F (F=00 =0 0| St a S }]
(1) stt ~p] (Se+lSe.ne)
12 ~p((+))
4

---

Published as a conference paper at ICLR 2021
To sample future states, we note that the density pI (st+ St. ax) is a weighted mixture of distribu- tions A St. at) indicating the future state exactly steps in the future:
p4 (sL+ St; at)
p(sc+ St, at (()))))))))))))))))
where p(A) (1-7)7²- GEOM(A; -7),
where GEOM is the geometric distribution. Thus, sample future state St+ via ancestral sam- pling: first sample A ~ GEOM(1 - 7) and then, looking at the trajectory containing (St, as return the state that is A steps ahead of (st, a.). We summarize Monte Carlo C-learning in Alg.
While conceptually simple, this algorithm requires on-policy data, as the distribution yZ (sL+ St: ae) depends on the current policy and the commanded goal. Even if fixed the policy parameters, we cannot use experience collected when commanding one goal to learn a classifier for another goal. This limitation precludes an important benefit of goal-conditioned learning: the ability to readily share experience across tasks. To lift this limitation, the next section will develop a bootstrapped version of this algorithm that works with off-policy data.
We now extend the Monte Carlo algorithm introduced above to work in the off-policy setting, so that can estimate the future state density for different policies. In the off-policy setting, we are given a dataset of transitions (st, ag St+1) and a new policy т, which we will use to generate actions for the next time step. at+1 (at+1 St+1). The main challenge is sampling from p (st+ St, at), which depends on the new policy x. We address this challenge in two steps. First, we note a recursive relationship between the future state density at the current time step and the next time step:
S
S Se: ac)
(1 7) p( S5+ St. ac) + B077//pee44_.... a[ (80+1)
[ 8t+ St a
future state density at current time step
environment dynamics
future state density at next time step
(4)
We can now rewrite our classification objective in Eq. 3 as
F(0, x) = E p(ac.as)
a.), ). p(ec (1)e,a)),
[(1 7) C7 (F = 1 St: at, Se+1) + log C3 (F 1|8e: a St,
o =(ar+1 (944)) PT (Fr+ 1ee4 (e-11)
Ep(er,e)). p(++-) [log CJ (F = 0 St: at, St-)]
(5)
This equation is different from the Monte Carlo objective (Eq. 3 because it depends on the new policy, but it still requires sampling from p" (st+ 8t+1, a which also depends on the new policy. Our second step is to observe that we can estimate expectations that use p (St+ | St at) by sampling from the marginal St+ ~ p(S++) ) and then weighting those samples by an importance weight, which can estimate using our learned classifier:
D (St+ Se+1,0t+1)
CF = 1.41:a4-1,50
w (St 1, a,+1,
(6)
p(5++)
CF = St+1 a,.1, St.)
The second equality is obtained by taking Eq. 2 and dividing both sides by p(st+). In effect, these weights account for the effect of the new policy on the future state density. We can now rewrite our objective by substituting the identity in Eq. [6] for the p(st+) term in the expectation in Eq. 5 The written objective is F(0, TT)
ap)s piee-1/se..g ....a.... [(1 7) log Co (F' at, + ? [w(st+1, act1, se+) Mag log Co (F 1 St. at, St+) p(Pe)): (() (P
+ log C7 (F [ss ac,
We use 1-Is as reminder that the gradient of an importance-weighted objective should not de- pend on the gradients of the importance weights. Intuitively, this loss says that be labeled as positive examples, states sampled from the marginal should be labeled as negative examples, but reweighted states sampled from the marginal are positive examples.
next states should
Algorithm summary. Alg 2 reviews off policy C-learning, which takes input policy and dataset of transitions. At each iteration, we sample a (St, a,, St+1) transition from the dataset, a potential future state St+ p(s++) and the next action a++1 T(a+1 St+1, St+). We compute the importance weight using the current estimate from the classifier, and then plug the importance weight into the loss from Eq. 3 We then update the classifier using the gradient of this objective.
5

---

Published as a conference paper at ICLR 2021
Algorithm 2 Off-Policy C-learning
Algorithm 3 Goal-Conditioned C-learning
Input transitions {t,, a, st+1). policy The while not converged do
Input transitions {st, a, 5c-1} while not converged do
Sample (st, at; 8t+1) ~ p(st, des 81+1),
Sample (St. Ot, S1+1) p(st, ae S(+1),
51+ p( ax+1 (ax+1 8e, at)
8et -p(((+) ar+1 ~ π [1t+1 88, Ct 814)
C5 (1
w + stop_grad
(F
w w stop-grad
CF
F(0,x) (1-2) log CJ (F de, Se+1)
F(0, 7) log Cjj (F | 01, 81+1)
+ log Cj =0/s (t+)
+ log Cp (F'= 00s; 0e S1+)
+ log C3 (F== 11st, S6+)
+ log Cp
- - 1/ 1
0 VoF
Return classifier C7
((0) iag Φ - ,
[log O7
Return policy T
C-learning Bellman Equations. In Appendix D.T. we provide a convergence proof for off-policy C-learning the tabular setting. Our proof hinges the fact that the TD C-learning update rule has the same effect as applying the following (unknown) Bellman operator:
Cp (F = St, as, sLt) CT(F== =0 0 Se, at. St+)
= (1 p(s = -t+ St. at)
CJ =1
p(S++)
St+1, as+1, St+)
This equation tells us that C-learning is equivalent to maximizing the reward function Tss, (St, at) p(St+1 Stt St, (a))p((s++) but does without having to estimate either the dynamics p(Se+1 St, ax) or the marginal distribution p(s)).
5.2 GOAL-CONDITIONED RL VIA C-LEARNING
We now build a complete algorithm for goal-conditioned RL based on C-learning, We will derive this algorithm in two steps. First, while Section 5.T shows how to estimate the future state density of a single policy, for goal-conditioned RL we will want to estimate the future state density of conditional policy, which may be conditioned on many goals. Second, we will discuss how to update policy using the learned density.
To acquire classifier for goal-conditioned policy, need apply objective function (Eq. 7 to all policies { ( (a 8, 9. E S). We can do this efficiently by additionally conditioning the classifier and the policy on the commanded goal g S. However, for learning goal-reaching policy, we will only need to query the classifier on inputs where Stt = 9. Thus, we only need to learn classifier conditioned on inputs where Stt g. resulting in the following objective:
E ((), p(ee+1 (s), p(sr+), a(Se+1 (6+1.g=864)
[(1 - 7) log Cj (F = St, ar, St+1) + log CJ ( = 0 St. at. Se+)
+ 7 [w(Ss+ 88y J log CF
St; at: Se+]]
(8)
The difference between this objective and the one derived in Section 5.1 (Eq. is that the next action is sampled from a goal-conditioned policy. The density function obtained from this classifier (Eq. represents the future state density of se+, given that the policy was commanded to reach goal 8 fT (St+ 8t+ St: ax) = y7 (St+ = Sc- St, at. 5c+)-
Now that to optimize the policy w.r.t. this learned density function. We need to define a reward function that says how good particular future state density is for reaching particular goal. While we can use any functional of future state density, natural choice is the KL divergence between a Dirac density centered at the commanded goal and the future state density of the goal-conditioned policy:
estimate the future state density of goal-conditioned policy, our second step is
- -DKI. (Se+ = 9) (St+ St, at, a).))) = log (st..
St, at.
Importantly, computing this KL only requires the future state density of the commanded goal. Since pi (st+ Se. at. = Stt ) is a monotone increasing function of the classifier predictions (see Eq. 2 can write the policy objective in terms of the classifier predictions:
(Ø)) = max E (ar (e)))) [log C2 (F = 1 St, at, St+ = =9]]
If collect new experience during training, then the marginal distribution p(su+) will change throughout training. While this makes the learning problem for the classifier non non-stationary, the learning problem for the policy (whose solution is independent of p(st+) )) remains stationary.

---

Published as a conference paper at ICLR 2021
Sum of probabiliies
y=
X (5.00
18
0.5
1.0
0.5
Error
Glesming (oars)
Unitomm
0.4
0.2
C-learing (owes)
Ostaming w..3
Oseening U
Odeaming (..)
G-learning
il 0.7)
Qsee
U 0.5)
00
0.99
0.99
2.59 6999
Fraction Negative Examples
Fraction Negat ve Examples 50
(a) Hypothesis
Underestimating the density
(b) Hypothesis 2
Optimal goal sampling ratio
Figure 1: Testing Hypotheses about Q-learning: (Left) As predicted. Q-values often sum to less than (Right) The performance of Q-learning is sensitive to the relabeling ratio. Our analysis predicts that the optimal relabeling ratio is approximately À 3 (1 + 7). C-learning (dashed orange) does not require tuning this ratio and outperforms Q-learning, even when the relabeling ratio for Q-learning is optimally chosen.
We summarize approach, which we call goal-conditioned C-learning, in Alg. 3 Given a dataset of transitions, we alternate between estimating the future state density of the goal-conditioned policy and updating the policy to maximize the probability density of reaching the commanded goal. This algorithm is simply to implement by taking a standard actor-critic RI. algorithm and changing the loss function for the critic (a few lines of code). In the tabular setting, goal-conditioned C-learning converges to the optimal policy (proof in Appendix D.3
Algorithm Summary:
5.3 IMPLICATIONS FOR Q-LEARNING AND HINDSIGHT RELABELING
Off-policy C-learning (Alg. 2 bears resemblance Q-learning with hindsight relabeling, so we now compare these two algorithms to make hypotheses about Q-learning, which we will test in Section 6
We start by writing the objective for both methods using the cross-entropy loss, CE(,,)):
Fc.leaming π) = (1 CCC
(F St. at, 1t+1): :. =1
+ +1+ C% St. ar, St+,,
70g WW +1 70% + +(1 C5a
YW
(9)
Foylearning (0, (1 A)CE(QU St, 9 St+1), 1)
XCE
Q7 Se. at. Stt),y y = (sL+1, a141,
(10)
where Cy = CF = 1 1 St+) is the classifier prediction at the next state and where A [0, 1] denotes the relabeling ratio used in Q-learning, corresponding the fraction of goals sampled from p(s++). There are two differences between these equations, which lead us to make two hypotheses about the performance of Q-learning, which will test in Section 6 The first difference is how the predicted targets are scaled for random goals, with Q-learning scaling the prediction by y while C-learning scales the prediction by 7/(70% + (1-C%) Since Q-learning uses smaller scale, we make the following hypothesis:
Hypothesis 1. Q-learning will predict smaller future state densities and therefore underestimate the true future state density function.
This hypothesis is interesting because it predicts that prior methods based on Q-learning will not learn proper density function, and therefore fail solve the future state density estimation prob- lem. The second difference between C-learning and Q-learning is that Q-learning contains tunable parameter A, which controls the ratio with which next-states and random states are used goals. This ratio is equivalent to a weight on the two loss terms, and our experiments will show that Q- learning with hindsight relabeling is sensitive to this parameter. contrast, C-learning does not re- quire specification of this hyperparameter. Matching the coefficients in the Q-learning loss (Eq. TOp with those in our loss (Eq. 9 (i.e., [1 [1 x [1 - 7, 1 + yw)), we make the following hypothesis: Hypothesis 2. Q-learning with hindsight relabeling will most accurately solve the future state den- sity estimation problem (Def. 2 when random future states are sampled with probability X 1+2
Prior work has found that this goal sampling ratio is a sensitive hyperparameter (Andrychowicz et al.) 2017 Pong et al. 2018 Zhao et al. 2019); ; this hypothesis is useful because it offers an automatic way to choose the hyperparameter. The next section will experimentally test these hypotheses.
6
EXPERIMENTS
We aim our experiments at answering the following questions:
Do Q-learning and C-learning accurately estimate the future state density (Problem 2
7

---

Published as a conference paper at ICLR 2021
2. (Hypothesis Does Q-learning underestimate the future state density function ($ 5.3)?
3. (Hypothesis Is the predieted relabeling ratio À (1 + 7)/2 optimal for Q-learning 5.3
4. How does C-learning compare with prior goal-conditioned RL methods on benchmark tasks?
Do Q-learning and C-learning accurately predict the future? Our first experiment studies how well Q-learning and C-learning solve the future state density estimation problem (Def. 2 We use a continuous version of a gridworld for this task and measure how close the predicted future state density the true future state density using a KL divergence. Since this environment continuous and stochastic, Q-learning without hindsight relabelling learns Q 0 on this environment. In the on-policy setting. MC C-learning and TD C-learning perform similarly, while the prediction error for Q-learning (with hindsight relabeling) is more than three times worse. In the off-policy setting, TD C-learnig is more accurate than Q-learning (with hindsight relabeling), achieving a KL divergence that is 14% lower than that of Q-learning. As expected, TD C-learning performs better than MC C-learning in the off-policy setting. These experiments demonstrate that C-learning yields a more accurate solution to the future state density estimation problem, compared with Q-learning. See Appendix G.I for full experimental details and results.
Our next experiment studies the ability of C-learning to predict the future in higher- dimensional continuous control tasks. We col- lected a dataset of experience from agents pre- trained to solve three locomotion tasks from OpenAl Gym. We applied C-learning to each dataset, and used the resulting classifier to pre- dict the expected future state. As a baseline, we trained a Isteep dynamics model on this same dataset and unrolled this model autore- gressively to obtain a prediction for the ex- pected future state. Varying the discount factor, we compared each method on Walker2d-v2 in Fig. 2 and the other tasks in Appendix Fig. 7 The 1-step dynamies model is accurate over short horizons but performance degrades for larger values of y, likely due to prediction errors accumulating over time. In contrast, the predictions obtained by MC C-learning and TD C-learning remain accurate for large values of 7. Appendix G.2 contains for experimental details; Appendix aad the project website contain more visualizations.
Disczmt
(a) Walker2d-v2
(b) Predicted future states
Figure 2: Predicting the Future: C-learning makes
accurate predictions of the expected future state across a range of tasks and discount values. In contrast, Iearn- ing 1-step dynamics model and unrolling that model results in high error for large discount values.
Testing our hypotheses about Q-learning: We now test two hypotheses made in Section 5.3 The first hypothesis is that Q-learning will underestimate the future state density function. compute the sum over the predicted future state density function, Ja.. p St+ st, at), which in theory should equal one. We compared the predictions from MC C-learning and Q-learning using on-policy data (details in Appendix G.T. As shown in Fig, the predictions from C-learning summed to 1, but the predictions from Q-learning consistently summed to less than one, especially for large values of X. However, our next experiment shows that Q-learning works best when using large values of X, suggesting that successful hyperparame- ters for Q-learning are ones for which Q-learning does not learn a proper density function.
To test this hypothesis,
Our second hypothesis is that Q-learning will perform best when the relabeling ratio is chosen to be = (1
72/2 Fig. [b shows the results from this experiment. The performance of Q-learning
is highly sensitive to the relabeling ratio: values of À that are too large or too small result in Q- learning performing poorly, worse than simply predicting uniform distribution. Second, not only does the optimal choice of À increase with 7. but our theoretical hypothesis of A = (1 - 2)/2 almost exactly predicts the optimal value of X. Our third observation is that C-learning, which uses 50-50 sampling ratio, consistently does better than Q-learning, even for the best choice of X. These experiments support our hypothesis for the choice of relabeling ratio while reaffirming that principled approach to future state density estimation obtains more accurate solution.
Coal-Conditioned RL for continuous control tasks: Our last set of experiments apply goal- conditioned C-learning (Alg. 3) to benchmark continuous control tasks from prior work, shown in Fig. 3 These tasks range in difficulty from the 6-dimensional Sawyer Reach task to the 45- dimensional Pen task (see Appendix G). The aim of these experiments is to show that C-learning is competitive with prior goal-conditioned RL methods, without requiring careful tuning of the goal sampling ratio. We compare C-leaming with a number of prior methods based on Q-learning, which
8

---

Published as a conference paper at ICLR 2021
Sauyer searh
Jaro teach
Finger
Hand
03-
Pen
Sawyer Push
Sawyer Drawer
Snwyer Window
0.0
032
Staps
Cleeming
TD3 (Fujimoto 2018]
Ralaballing ling (Lin 2013)
(Andrychowice 2017]
[Andrythowiaz 2017)
Figure 3: Goal-conditioeed RL: C-learning is competitive with prior goal-conditioned RL methods across a suite of benchmark tasks, without requiring careful tuning of the relabeling distribution.
differ in how goals sampled during training: TD3 (Fujimoto et al. 2018) does no relabeling, Lin iet al. (209)) uses 50% next state goals and 50% random goals, and HER (Andrychowicz, et al., 2017 uses final state relabeling (we compare against both 100% and 50% relabeling). None of these methods require a reward function or distance function for training; for evaluation, we use the L2 metric between the commanded goal and the terminal state (the average distance to goal and minimum distance to goal show the same trends). As shown in Fig. 3 C-lcarning is competitive with the best of these baselines across all tasks, and substantially better than all baselines on the Sawyer manipulation tasks. These manipulation tasks are more complex than the others because they require indirect manipulation of objects in the environment. Visualizing the learned policies, we observe that C-learning has discovered regrasping and fine-grained adjustment behaviors, behav- iors that typically require complex reward functions to learn (Popov et al., 2017) 2 On the Sawyer Push and Sawyer Drawer tasks, found that hybrid of TD C-learning and MC C-learning per- formed better than standard C-learning. This variant, which is analogous to an "n-step" version of C-learning. is simple to implement and is described in Appendix [E] In summary, C-learning per- forms as well as prior methods on simpler tasks and better on complex tasks, does not depend on a sensitive hyperparameter (the goal sampling ratio), and maximizes well-defined objective function.
Predicting the goal sampling ratio for goal conditioned RL: While C-learning prescribes precise method for sampling goals, prior hind- sight relabeling methods are sensitive to these parameters. To visualize this, we varied the goal sampling ratio used by [in et al. (2019) on the maze maze2d-uma (2020). As shown in Fig- 4 properly choosing this ratio can result in 50% decrease in final distance. Additionally, our hypothesis that the optimal goal sampling ratio is À (1 7)/2 accurately predicts the best value for this ratio.
À 1+Y
FinalDistance
3.5
1.0
task from Fu et al.)
0.0
Fraction Negative Examples (A)
Figure 4: Q-learning is sensitive the relabeling ratio. Our analysis predicts the optimal relabeling ratio.
CONCLUSION
A goal-oriented agent should be able to predict and control the future state of its environment. In this paper, we used this idea reformulate the standard goal-conditioned RL problem one of estimating and optimizing the future state density function. We showed that Q-learning does not directly solve this problem in (stochastic) environments with continuous states, and hindsight relabeling produces, at best, a mediocre solution for an unclear objective function. In contrast, C- learning yields more accurate solutions. Moreover, our analysis makes two hypotheses about when and where hindsight relabeling will most effectively solve this problem, both of which are validated our experiments. Our experiments also demonstrate that C-learning scales to high-dimensional continuous controls tasks, where performance is competitive with state-of-the-art goal conditioned RL methods while offering an automatic and principled mechanism for hindsight relabeling.
"See the project wehsite for videns: https::/ben-eyysetteee

---

Published as a conference paper at ICLR 2021
ACKNOWLEDGEMENTS
We thank Dibya Ghosh and Vitchyr Pong for discussions about this work, and thank Vincent Vanhouke, Ofir Nachum, and anonymous reviewers for providing feedback on early versions of this work. This work is supported by Fannie and John Hertz Foundation, and the National Science Foundation (DGE-1745016, ISS1763562), and the US Army (F911111900004).
REFERENCES
Marcin Andrychowicz, Filip Wolski, Alex Ray, Jonas Schneider, Rachel Fong, Peter Welinder, Bob McGrew, Josh Tobin, OpenAl Pieter Abbeel, and Wojeiech Zaremha. Hindkight experience replay. In Advances neural information processing systems. pp. 5048 5058, 2017.
André Barreto, Will Dabney, Rémi Munos, Jonathan J Hunt, Tom Schaul, Hado P van Hasselt, and David Silver. Successor features for transfer in reinforcement learning. In Advances neural information processing systems, pp. 4055-4065, 2017.
André Barreto, Diana Borsa, Shaobo Hou, Gheorghe Comanici, Eser Aygün, Philippe Hamel, Daniel Toyama, Shibl Mourad, David Silver, Doina Precup, et al. The option keyboard: Combining skills in reinforcement learning. In Advances in Neural Information Processing Systems, pp. 13052-13062, 2019.
Steffen Bickel, Michael Brückner, and Tobias Scheffer. Diseriminative learning for differing training and test distributions. In Proceedings of the 24th international conference Machine learning, pp. 81-88, 2007.
Devendra Singh Chaplot, Ruslan Salakhutdinov, Abhinav Gupta, and Saurabh Gupta. Neural topological slam for visual navigation. In Proceedings of the IEEE/CVF Conference Computer Vision and Pattern Recog- nition, pp. 12875-12884, 2020.
Peter Dayan. Improving generalization for temporal difference learning: The successor representation. Neural Computation, 5(4):613-224 1993.
Yiming Ding, Carlos Florensa, Pieter Abbecl, and Mariano Phielipp. Goal conditiiid imitation learning. In 2019.
Advances in Neural Information Processing Systems, pp.
Vincent Dumoulin, Ishmael Belghazi, Ben Poole, Olivier Mastropietro, Alex Lamb, Martin Arjovsky, and Aaron Courville. Adversarially learned inference. arXiv preprint arXiv:1606.00700 2016.
Frederik Fhert, Chelsea Finn, Sudeep Dasari, Annie Xie, Alex Lee, and Sergey Levine. Visual fore-
sight: Model-based deep reinforcement learning for vision-based robotic control. arXiv preprint arXiv:/812.00568, 2018.
Benjamin Eysenbach, Russ R Salakhutdinov, and Sergey Levine. Search on the replay huffer: Bridging plan- ning and reinforcement learning. Advances Neural Information Processing Systems, pp. 15246-15257, 2019.
Benjamin Eysenbach, Xinyang Geng, Sergey Levine, and Ruslan Salakhutdinov. Rewriting history with inverse rl: Hindsight inference for policy improvement. arXiv preprint arXiv:2002.1 2020.
Meng Fang, Tianyi Zhou, Yali Du, Lei Han, and Zhengyou Zhang. Curriculum-guided hindsight experience replay. In Advances Neural Information Processing Systems, pp. 12623-12634, 2019.
Justin Fu, Aviral Kumar, Matthew Soh, and Sergey Levine. Diagnosing bottlenecks in deep q-Icarning algo- rithms. arXiv preprint arXiv: (oXivv/90020 000.//02..22222 10250, 2019.
Justin Fu, Aviral Kumar, Ofir Nachum, George Tucker, and Sergey Levine. D4rl: Datasets for deep data-driven reinforcement learning. arXiv preprint arXiv:2004.07219, 2020.
Scott Fujimoto, Herke Van Hoof, and David Meger. Addressing function approximation error actor-critic methods. arXiv preprint 1802:1882.00977 2018.
Dibya Ghosh, Abhishek Gupta, Justin Fu, Ashwin Reddy, Coline Devin, Benjamin Eysenbach, and Sergey Levine. Learning to reach goals without reinforcement learning. arXiv preprint arXiv:1912.06088 2019.
Karol Gregor, George Papamakarios, Frederic Besse, Lars Buesing, and Theophane Weber. Temporal differ- ence variational auto-cncoder. arXiv preprint 106.031806.03077 2018.
Sergio Guadarrama, Anoop Korattikara, Oscar Ramirez, Pablo Castro, Ethan Holly, Sam Fishman, Ke Wang, Ekaaerina Gonina, Neal Wu, Chris Harris, et al. Tf-agents: A library for reinforcement learning in tensorflow, 2018.
10

---

Published as a conference paper at ICLR 2021
Abhishek Gupta, Vikash Kumar, Corey Lynch, Sergey Levine, and Karol Hausman. Relay policy learning: Solving long-horizon tasks via imitation and reinforcement leamnigg. arXiv preprint arXiv:1910.11955 2019.
Michael Gutmann Aapo Hyvärinen. Noise-contrastive estimation: A new estimation principle for unnor- malized statistical models. In Proceedings of the Thirteenth International Conference on Artificial Intelli- gence and Statistics, pp. 297-304, 2010.
Tuomas Haarnoja, Aurick Zhou, Pieter Abbeel, and Sergey Levine. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with stochastic actor. arXiv preprint 181.01900 2018.
Ferenc Huszár. Variational inference using implicit distributions. arXiv preprint arXiv:1702.0686 2017.
Tommi Jaakkola, Michael I Jordan, and Satinder P Singh. On the convergence of stochastic iterative dynamic programming algorithms. Neural computation, 666):1885 1201, 1994.
Leslie Pack Kaelbling. Learning to achieve goals. IJCAI, pp. 1194-1099) Citeseer, 1993.
Hilbert Kappen. Path integrals and symmetry breaking for optimal control theory. Journal of statistical mechanics: theory and experiment, 2005(11):PI 2005.
Sergey Levine. preprint arXiv: 00909, 2018.
Reinforcement learning and control as probabilistic inference: Tutorial and review. arXiv
Xingyu Lin, Harjatin Singh Baweja, and David Held, Reinforcement learning without ground-truth state. arXiv preprint 0rXiv:1905.07960 2019.
Qiang Liu, Lihong Li, Ziyang Tang, and Dengyong Zhou. Breaking the curse of horizon: Infinitehhrizon off-policy estimation. In Advances in Neural Information Processing Systems, pp. 5356-5366, 2018.
Corey Lynch, Mohi Khansari, Ted Xiao, Vikash Kumar, Jonathan Tompson, Sergey Levine, and Pierre Ser- manet. Learning latent plans from play. In Conference on Robot Learning, pp. 1113-1111111 2020.
Ofir Nachum, Shixiang Gu, Honglak Lee, and Sergey Levine. Near-optimal representation learning for hierar- chical reinforcement learning. arXiv preprint 1rXiv:1810001257, 2018.
Ofir Nachum, Yinlam Chow, Bo Dai, and Lihong Li. Dualdice: Bchavior-agnostic estimation of discounted stationary distribution corrections. In Advances in Neural Information Processing Systems, pp. 2318 1-2222,, 2019.
Suraj Nair, Silvio Savarese, and Chelsea Finn. Goal-aware prediction: Learning to model what matters. arXiv preprint arXiv:200..07170, 2020.
Soroush Nasiriany. Vitchyr Pong. Steven Lin, and Sergey Levine. Planning with goal-conditioned policies. In Advances Neural Information Processing Systems, pp. 14843-14854, 2019.
Junhyuk Oh, Yijie Guo. Satinder Singh, and Honglak Lee. Self-imitation learning.
arXiv preprint
arXiv:1806.05633 2018.
Aaron van den Oord, Yazhe Li, and Oriol Vinyals. Representation lcarning with contrastive predictive coding. arXiv preprint arXiv: 1807.03748 2018.
Pedro A Ortega and Daniel A Braun. Thermodynamics as a theory of decision-making with information- processing costs. Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences, 469(2153):201 20683, 2013.
Silviu Pitis, Harris Chan, Stephen Zhao, Bradly Stadie, and Jimmy Ba. Maximum entropy gain exploration for long horizon multi-goal reinforcement learning. arXiv preprint 02X2222000.028832 2020.
Vitchyr Pong, Shixiang Murtaza Dalal, Sergey Levine. Temporal difference models: Model-free deep for based control. arXiv preprint 102.0:180..09081, 2018.
Vitchyr H Pong, Murtaza Dalal, Steven Lin, Ashvin Nair, Shikhar Bahl, and Sergey Levine. Skew-fit: State- covering self sufervuper reinforcement leaminng arXiv preprint 1903.09000003660 2019.
Ivaylo Popov, Nicolas Heess. Timothy Lillicrap. Roland Hafner, Gabriel Barth-Maro Matej Vecerik, Thomas Lampe, Yuval Tassa, Tom Frez, and Martin Riedmiller. Data-efficient deep reinforcement learning for dexterous manipulation. arXiv preprint /74.:3770 2017.

---

Published as a conference paper at ICLR 2021
Konrad Rawlik, Mare Toussaint, and Sethu Vijayakumar. On stochastic optimal control and reinforcement learning by approximate inference. In Twenty-third international joint conference on artificial intelligence. 2013.
Nikolay Savinov, Alexey Dosovitskiy, and Vladlen Koltun. Semi-parametris topological memory for naviga- tion. arXiv preprint arXiv: 180::88030000 806300 2018.
Tom Schaul, Daniel Horgan, Karol Gregor, and David Silver. Universal value function approximators. In International conference on machine learning, pp. 1312-13200 2015.
Yannick Schroecker and Charles Isbell. Universal value density estimation imitation learning and goal- conditioned reinforcement learning. arXiv preprint arXiv:2002.06477 2020.
Evan Shelhamer, Parsa Mahmoudieh, Max Argus, and Trevor Darrell. Loss is its own reward: Self supervissnn for reinforcement learning. arXiv preprint arXiv:1612.07307, 2016.
Casper Kaae Sønderby. Jose Caballero, Lucas Theis, Wenzhe Shi, Ferenc Huszár. Amortised map inference for image super-resolution. arXiv preprint arXiv: 04490, 2016.
Hao Sun, Zhizhong Xiaotong Liu, Bolei Zhou, and Dahua Lin, Policy continuation with hindsight inverse dynamics. In Advances in Neural Information Processing Systems, pp. 10265-10275,0019
Richard Sutton. Learning to predict by methods of temporal differences. Machine learning, 3(1):9444 1988.
Richard Sutton Brian Tanner. cessing systems, pp. 1377-1384, 2005.
networks. In Advances neural information pro-
Csaba Szepesvari, Richard Sutton, Joseph Modayil, Shalabh Bhatnagar, et al. Universal option models. In Advances in Neural Information Processing Systems, pp. 990-998, 2014.
Yuval Tassa, Yolam Doron, Alistair Muldal, Tom Erez, Yazhe Li, Diego de Las Casas, David Budden, Abbas Abdolmaleki, Josh Merel, Andrew Lefrancq, et al. Deepmind control suite. arXiv preprint arXiv: 00690, 2018.
Yuval Tassa, Saran Tunyasuvunakool, Alistair Muldal, Yotam Doron, Sigi Liu, Steven Bohez, Josh Merel, Tom Erez. Timothy Lillicrap. and Nicolas Heess. dm.control: Software and tasks for continuous control. arXiv preprint arXiv:2006. 12983, 2020.
Evangelos Theodorou, Jonas Buchli, and Stefan Schaal. A generalized path integral control approach to rein- forcement learning. The Journal Machine Learning Research, 11:3137-3181 2010.
Emanuel Todorov. General duality between optimal control and estimation. In 2008 47th IEEE Conference on Decision and Control, pp. 4286-4292. IEEE, 2008
Masatoshi Uehara, Issei Sato, Masahiro Suzuki. Kotaro Nakayama, and Yutaka Matsuo. Generative adversarial nets from a density ratio estimation perspective. arXiv preprint arXiv:1610.029200 2016.
Tianhe Yu, Deirdre Quillen, Zhanpeng He, Ryan Julian, Karol Hausman, Chelsea Finn, and Sergey Levine. Meta-world: A benchmark and evaluation for multi-task and meta reinforcement learning. In Conference on Robot Learning, pp. 1094-1100) 2020.
Rui Zhao, Xudong Sun, and Volker Tresp. Maximum entropy-regularizze multi-goal reinforcement learning. arXiv preprint 900.:/905088866 2019.
Brian Zichart. Modeling purposeful adaptive hehavior with the principle of maximum causal entropy. 2010.
12

---

Published as a conference paper at ICLR 2021
A PARTAALLY-OSSERVED GOALS
In many realistic scenarios we have uncertainty over the true goal, with many goals having some probability of being the user's true goal. These scenarios might arise because of sensor noise or because the user wants the agent to focus on a subset of the goal observation (e.g., a rohot's center of mass).
Noisy Goals. In many prior works, this setting approached by assuming that a noisy measure- ment of the goal 2 ~ p(2 St+ g) is observed, and conditioning the Q Q-function on this measure- ment. For example, the measurement might be the VAE latent of the image g (Pong et al., 2019] Gregor et al.) 2018 [h18|Shelhamerr (Selhhaerr et al. 2016). In this setting, we will instead aim to estimate the future discounted measurement distribution,
p(ze+ St. ae) (1 7)
A -plis m)) [p(z+ stta)].
A=0
Whereas the goal-conditioned setting viewed (st+ St. as defining a measure over goals, here we view fø (Z++ St, at) an implicitly-definee distribution over measurements.
Partial Goals. In some settings, the user may want the agent pay attention part of the goal, ignoring certain coordinates or attributes. Applying C-learning to this setting is easy. Let crop(s) be user-provided function that extracts relevant coordinates aspects of the goal state. Then, the user can simply parametrize the C-learning classifier as C% (F St. at 9 crop(st+)).
B ANALYTIC FUTURE STATE DISTRIBUTION
In this section describe how analytically compute the discounted future state distribution for the gridworld examples. We started by creating two matrices:
T E R 25x25
Tis, Σ =())
To E IR 25x4x25
Tis, ass,a,81= (f)((aa) = s'),
where f(s a) denotes the deterministic transition function. The future discounted state distribution then given by:
P= (1 7) [To + + T TT, +...] = (1 - To [ 22 + 373 +...]
=1 Io (1-
The tensor-matrix product T&T is equivalent e einsum ('ijkukk - iijh', To. T). We use the forward KL divergence for estimating the error in our estimate, (RI,( Q), where Q is the tensor of predictions:
Q E IR 25x4xx
Q18, g) = 4(9 a.
C ASSIGNMENT EQUATIONS FOR THE MSE Loss
In Section 5.3 we derived the assignment equations for C-learning under the cross entropy loss. In this section we show that using the mean squared error (MSE) loss results in the same update equations. Equivalently, this be viewed using Gaussian model for values instead of logistic model. This result suggests that the difference in next-state scaling between C-learning and Q-learning is not just quirk of the loss function.
13

---

Published as a conference paper at ICLR 2021
To start, write the loss for C-learning using the MSE and then completing the square.
L(O, () (1- = St. at St+1) - 1)² + yw ( (F' If== = St. at. St+) 1)²
+ (C7 (F = St. at: Sc+1) -02
2
= (1 (1-11 1) (C8 (F St. a St+1) - 1)² + ypu 0% (F = St. ae: Sct)
7WW
7/2 +
W
+ yu
TYW +
constant w.r.t. Ca
The optimal values for Co for both cases of goal are the same as for the cross entropy loss:
s Stt
C (F = 1 Se ae. Set)
otherwise
Additionally, observe that the weights on the two loss terms are the same as for the cross entropy loss: the next-state goal loss is scaled by (1 -?) while the random goal loss is scaled by yw.
D A BELLMAN EQUATION FOR C-LEARNING AND CONVERGENCE GUARANTEES
The aim of this section to show that off-policy C-learning converges, and that the fixed point corresponds the Bayes-optimal classifier. This result guarantees that C-learning will accurate evaluate the future state density of given policy. We then provide a policy improvement theorem, which guarantees that goal-conditioned C-learning converges the optimal goal-conditioned policy.
D.1 BELLMAN EQUATIONS FOR C-LEARNING
We start by introducing a new Bellman equation for C-learning, which will be satisfied by the Bayes optimal classifier. While actually evaluating this Bellman equation requires privileged knowledge of the transition dynamics and the marginal state density, if knew these quantities could turn this Bellman equation into a convergent value iteration procedure. the next section, we will show that the updates of off-polic C-learning equivalent to this value iteration procedure, but do not require knowledge of the transition dynamics or marginal state density. This equivalence allows us conclude that C-learning converges the Bayes-optimal classifier.
Our Bellman equation says that the future state density function fo induced by a classifier Co should satisfy the recursive relationship noted in Eq. 4
Lemma (C-learning Bellman Equation). Lei policy πT ( Se), dynamics function p(St+1 St, at.) and marginal distribution p(st.) be given. If a classifier Cg is the Bayes-optimal classifier, then it satisfies the follow identity for all states St, actions at, and potential future states St+:
C (F
St. at. St+)
(1-7) p(st+1 (1-7)p(st+1
Stt St. at
C (F
St+1
TB p(( ( m1)) (0 18t)
C F 0 St, Bt, S
p((e+)
C. (F
St B St.))
(11)
Proof. If Co is the Bayes-optimal classifier, then fø (SL+ St, a4) (Se+ the definition of fe (Eq. 2) into Eq. 4 we obtain a new Bellman equation:
Se; ae). Substituting
This Bellman equation is similar to the standard Bellman equation with goal-conditioned reward function 7 (st. a,) p(st+1 St+ Se. ( where Q functions represent the ratio I8 (Se+ St, at) p (St+ St, at). However, actually computing this reward function evaluate this Bellman equation requires knowledge of the densities p(s++1 St, ar) and p(st-), both of which we assume are unknown to our agent? Nonetheless, we had this privileged information,
Interesttnngy,, efficiently estimate this reward function by learning next-state classifier, (F Se ar St+1), which distinguishes St-1 p(st+1 Se, a,) from St+1 p(S(+1) p(st+). This classifier
14

---

Published as a conference paper at ICLR 2021
could readily turn this Bellman equation into the following assignment equation: CT (F 1 St, at. St+) C 0 St. St. St+)
(1 (1-7)= p(s6-1 St+ Sc. at)
Co (F St-1, a++1, St+
+- |st (s.)))) " (#e+1 (t))
p(se+)
C3 ( St-1, ät St++)
(12)
Lemma 2. If use labular representation for the ratio C7 (f= then iterating the assignment equation (Eq. 12 converges to the optimal classifier.
Proof. Eq. 12 be viewed as doing value iteration with goal-conditioned Q function Cg and a goal-conditioned reward function
parametrized as ((s at Se+)
+ (St, a²) p( S (s), We can then employ standard convergence proofs for Q-learning 1994 Theorem 1).
p(#++)
guarantee convergence Jaakkola et al.
D.2 OFF-POLICY C-LEARNING CONVERGES
In this section we show that off-policy C-learning converges to the Bayes-optimal classifier, and thus recovers the true future state density function. The main idea is to show that the updates for off- policy C-lcarning have the same effect as the assignment equation above (Eq. 12 without relying on knowledge of the dynamics function or marginal density function.
Lemma 3. Off-policy C-learning results in the same updates to the classifier as the assignment equations for the C-learning Bellman equation (Eq. [2)
Proof. We start by viewing the off- C-learning loss (Eq. 9 as probabilistic assignment equation. given triplet (&r, at, St+) can appear Eq. 9 in two ways:
1. We sample a "positive" Set St+1, which happens with probability (1 7))((((5 = Set St, a,), and results in the label y y
2. We sample a "negative" St., which happens with probability (1 + yw)p((s+) and results Yo
in the label y = 4
Thus, conditioned on the given triplet containing St+, the expected target value is
(1 7)p(s1+1 = Set St, at)) 1 + E
[1 (L+- I
you
Ely St, ac, St+]
7) 7)p( 1t+ SEt
St, a+
[11 7w0 (($t+)
(1 - 7) p(ac 11 =1 |sc.ar) [B[[
p(ae+)
(13)
(1 7) p( 3t 3 [s))
+ >(E[w] +
p(s++)
Note that w is random variable because it depends on St+1 and ast1, so we take its expectation above. We can write the assignment equation for C' (I = 1| St, Se, < Ely St, at. St+].
Noting that the function I-c to the following assignment for the ratio C7 (F=1 ...).
C is strictly monotone increasing, the assignment equation is equivalent
C (F == St. at,
Ely Sc. at, St+]
(1 7) p(Se+) S111 = Stt St, at) + -:Bj)).
C (F = St, St-)
E-
St. ag, Set]
((s++)
The equality follows from substituting Eq. 13 and then simplifying. Substituting our definition of w, observe that the assignment equation for off-policy C-learning is exactly the same as the assignment equationn for the C-learning Bellman equation (Eq, IT:
Cj (F St, Re, St+) +- (1 p( St+ St. at)
CF St+1, 3t+1, CF = St+1. a,+1, 8t,
+
C (F = 0 St, St+))
p(s++)
different from the future state classifier used C-learning. The reward function can then estimated as ra,t (Se, at) [e(F=ilar.au
[0 If we learned this next state classifier, we estimate the future state density and learn goal-reaching policies by applying standard Q-lcarning this reward function.
15

---

Published as a conference paper at ICLR 2021
Since the off-policy C-learning assignments are equivalent to the assignments of the C-learning Bellman equation, any convergence guarantee that applies to the later must apply the former. Thus, Lemma tells us that off- off-policy C-learning must also converge to the Bayes-optimal classifier. We state this final result formally:
Corollary 3.1. If we verges to the Bayes-optimes optimal classifier. In this case, the predicted future state density (Eq. 2 also converges the true future state density.
tabular representation for the classifier, then off off-policy C-learning
D.3 GOAL-CONDITIONED C-LEARNING CONVERGES
In this section we prove that the version of policy improvement done by C-learning is guaranteed improve performance. We start by noting Bellman optimality equation for goal-conditioned C-learning, which indicates whether goal-conditioned policy is optimal:
Lemma 4 (C-learning Bellman Optimality Equation), Let dynamies function p(se+1 st,ca), and marginal distribution p(st+) be given. If a classifier C9 is the Bayes-optimal classifier, then satisfies the follow identity for all states St, actions at, and goals = St
CT 1 Se, at, St+)
(1-7) p(st+1
St+
St, at)
+7 t (s..a)))
max
CF st+1, a St+)
CF 0
Sc. Se+)
p(s+))
C7 0 St
Se+
(14)
We now apply the standard policy improvement theorem to C-learning.
Lemma 5. If the estimate of the future state density is accurate, then updating the policy according Eq. 5.2 guarantees improvement each step.
Proof. We use π to denote the current policy and n' to denote the policy that acts greedily w.r.t. the current density function:
n' a'a Se. Se4) 1(a, = arg max (se+ St, a²))
The proof is quite similar to the standard policy improvement proof for Q-learning. p² (st+
(t)) = E (ma 9 st (p (st+ at))
E [ns st s + (11 - 7) = St+ St, at) + 7pp (st+ (++1)
< Er (ar (e. 7)p(st+1 = St+ 1tt + 7p" (St+ (S411.
Ea 8et [11 7)p(8t+1 = stt at)
+ E (() 1
(T((1 - -7)p(st+1 = Set (5+11, + (stt (442,0442))
E (x. 7)p(S1+1 -tt+ at)
E p( 1(
1y(1 7))(s(+1 st+ | ac+1) ypp (sct 8842, (142))
S pd (se+ ss))
Taken together with the convergence of off-policy C-learning, this proof guarantees that goal- conditioned C-learning converges the optimal goal-reaching policy (w.r.. the functional in Eq. 5.2) in the tabular setting.
E
MIXING TD C-LEARNING WITH MC C-LEARNING
Recall that the main challenge in constructing an off off-policy procedure for learning the classifier was getting samples from the future state distribution of policy. Recall that TD C-learning
16

---

Published as a conference paper at ICLR 2021
(Alg. 3) uses importance weighting estimate expectations under this new distribution, where the importance weights are computed using the learned classifier. However, this approach can result in high-variance, especially when the policy has future state distribution that is very different from the background distribution. In this section we describe how to decrease the variance this importance weighting estimator the cost of increasing bias.
The main idea is to combine TD C-learning with MC C-learning. We will modify off-policy C- learning also use samples p(St+ St, at) from previous policies as positive examples. These samples will be sampled from trajectories in the replay buffer, in the same way that samples were generated for MC C-learning. We will use a mix of these on-policy samples (which are biased because they come from a different policy) and sepoorance-weightee samples (which may have higher variance). Weighting the TD C-learning estimator by À and the MC C-learning estimator by (1 X), we get the following objective:
Bpee als )(11 7) log C(F [[P=11 = St, at, 1t+1) + log C(F 0 Se. ae, SE+)
+ + log C(F = St, ag. Si+)
+ (1 B)
[lo C(F 1 St, a Sit) + log C(F 0 St. ar, St+)l
This method is surprisingly easy to implement. Given batch of B transitions (st, at). we label 2 B with the next state St+1: B with a random state 8tt p(s+)), and - with a state sampled from the empirical future state distribution p(se+ St, at). To make sure that each term in the loss above receives the correct weight, we scale each of the terms by the inverse sampling probability:
2
(Next states):
(X(1 - log C(F 11
St, at; 1
XB
2
(Random states):
((X 1 x) log C(F 0 St. a. Stt) Ayw log C(F st. ac, St+))
(Future states):
(1- (1-- Aylog C(F = Sec at. Sc+)
Without loss of generality, we scale each term by g. Since each of these terms cross entropy loss, we can simply implement this loss weighted cross entropy loss, where the weights and labels are given the table below.
Fraction of batch
Label
Weight
Next states
1
1 1-Y
Future states
1 Aayar
1
Random states
(1 + Xrw)
I4Am
On many tasks, observed that this approach performed differently than TD C-learning. How- ever, we found this strategy to be crucial for learning some of the sawyer manipulation tasks. In our experiments used 0.6 for the Sawyer Push and Sawyer Drawer tasks, and used À 1 (i.e., pure TD C-learning) for all other tasks.
F ADDITIONAL EXPERIMENTS
Comparing C-learning and C-learning for Future State Density Estimation Fig. Fig.55shan showss the results of our comparison of C-learning and Q-learning on the "continuous gridworld" environment, in both the on-policy and off off-policy setting. In both settings, off off-policy C-learning achieves lower emor than Q-learning. As expected, Monte Carlo C-learning performs well in the on-policy setting, but poorly in the off off-policy setting, motivating the use of off-policy C-learning.
Additional Results on Predicting the Goal Sampling Ratio To further test Hypothesis 2 repeated the experiment from Fig. [b across a range of values for y. As shown in Fig. 6 our Hypothesis accurately predicts the optimal goal sampling ratio across wide range of values for 7.
17

---

Published as conference paper at ICLR 2021
0.8
uniform distribution
0.6
Error of uniform distribution
0.6
Error
Error
0.4
0.4
0.2
0.2
0.0
0.0
Monte Carlo
Off-policy C-learning
Q-learning
Monte Carlo
Off-policy C-learning
Q-learning
C-learning
C-learning
(a) On Policy
(b) Off Policy
Figure 5:
use C-learning and Q-learning predict the future state distribution. (Right) In the on-policy setting, both the Monte Carlo and TD versions of C-lcarning achieve significantly lower error than Q-learning. (Right) In the off- off-policy setting, the TD version of C-learning achieves lower error than Q-leaming, while Monte Carlo C-leaming performs poorly, expected.
Y- 0.5
y- 0.8
y- 0.9
y- 0.99
8.5
Cleamring
32
82
02
82
6.33
(.)
Tractinn Negattue
Tracton Negative Ccompien
Frection Negetiow Eourpies
Fraction hagatien
Figure 6: The performance of Q-learning (blue line) is sensitive to the relabeling ratio. Our analysis accurately predicts that the optimal relabeling ratio is approximately À = 1 (1+ 7). Our method, C-learning, does not require tuning this ratio, and outperforms Q-learning, even with the relabeling ratio for Q-learning optimally chosen.
G EXPERIMENTAL DETAILS
G.1 "CONTINUOUS GRIDWORLD" EXPERIMENTS
The "Continuous Gridworld" Environment Our first set of experiments aimed to compare the predictions of Q-learning and C-learning to the true future state density. We carefully chose the environment to conduct this experiment. We want to have stochastic dynamics and a continuous state space, that the true function for the indicator reward is O. On the other hand, evaluate our hypotheses, we want to be able to analytically compute the true future state density. Thus, we use modified current state. Precisely, when the agent is in position (i.j), the agent observes (i + e,. + e,) where 6, çj Unif[ 0.5, 0.5). Note that the observation uniquely identifies the agent's position, so there is no partial observability. We can analytically compute the exact future state density function by first computing the future state density of the underlying gridworld and noting that the density is uniform within each cell (see Appendix B). We generated tabular policy by sampling from Dirichlet(1) distribution, and sampled trajectories of length 100 from this policy.
gridworld environment where the agent observes noisy version of the
On-Policy Experiment We compare C-learning (Algorithms I and Q-learning in the on- policy setting, where we aim to estimate the future state density function of the same policy that collected the dataset. This experiment aims answer whether C-learning and Q-learning solve the future state density estimation problem (Def. 2). Each of the algorithms used 2 layer neural network with a hidden layer of size 32, optimized for 1000 iterations using the Adam optimizer with learning rate of 3e-3 and a batch size of 256. C-learning and Q-learning with hindsight relabeling differ only in their loss functions, and the fact that C-learning acquires a classifier while Q-learning extracted the estimated
predicts continuous Q-value. After training with each of the algorithms, future state distribution f (st+ St, 8t, using Eq, 2 We also normalized the predicted distributions fă (se+ St, a to sum to 1 (i.e., Σ... f (st+ S1t st, at) 1 Vs,, az). For evaluation, computed the KI. divergence with the true future state distribution. We show results in Fig.
18

---

Published as a conference paper at ICLR 2021
Ura rock!
Dedrtton Eno
Poend oo Ertor
Catep model
on.
mode
Discount (Vl
Discount
(a) Walker2d-v2
(b) Hopper-v2
(c) Ant-v2
Figure 7: Predicting the Future with C-Leaanning We ran the experiment from Fig. 2 on three locomotions tasks.
Off-Policy Experiment We use the same "continuous gridworld" environment compare C- learning to Q-learning in the policy setting, where we want to estimate the future state distribu- tion of a policy that is different from the behavior policy. Recall that the motivation for deriving the bootstrapping version of the classifier learning algorithm was precisely to handle this setting. To conduct this experiment, generated two tabular policies by sampling from Dirichlet(1) I) distri- bution, using one policy for data collection and the other for evaluation. We show results in Fig. 5b
Experiment Testing Hypothesis (Fig, la For this experiment, we found that using slightly
larger network improved the results of both methods, so we increased hidden layer size from 32 to 256.
F To test this hypothesis, we used the Q-learning objective in Eq. 10 where À represents probability of sampling a random state as St+. Following prior work (Fu et al., 2019), we reweight the loss function instead of changing the actual sampling probabilities, thereby avoiding additional sampling error. We this experiment in the on-policy setting, using 5 random seeds for each value X. For each trial, we normalized the predicted density function to sum to 1 and then computed the KL divergence with the true future state density function.
Experiment Testing (f
G.2 PREDICTION EXPERIMENTS ON MUJOCO LOCOMOTION TASKS
In this section we provide details for the prediction experiment discussed in Sec. 6 and plotted in
Fig. 2 and Fig. 7
We first describe how we ran the experiment computing the prediction error in Fig. 7a 7
For these
experiments, we used the "expert" data provided for each task in Fu al. (2020). We split these trajectories into train (80%) and test (20%) splits. All methods (MC C-learning, TD C-learning, and
the 1-step dynamics model) used the same architecture (one hidden layer of size 256 with ReLU activation), but C-learning output binary prediction whereas the 1-step dynamics model output vector with the same dimension as the observations. While we could have used larger networks and likely learned more accurate models, the aim of this experiment is to compare the relative perfor- mance of C-learning and the I-step dynamics model when they use similarly-expresse We trained MC C-learning and the 1-step dynamics model for 3e4 batches and trained the TD C- learning model for just 3e3 batches (we observed overfitting after that point). For TD C-learning, we clipped w lie in [0, 20). To evaluate each model, randomly sampled 1000 state-action pairs from the validation set and computed the average MSE with the empirical expected future state. We computed the empirical expected future state by taking geometric- average of the next 100 time steps. We computed the predictions from the -sstep model by unrolling the model for 100 time steps and taking the geometric-weighttd average of these predictions. To compute predictions from the classifier, we evaluate the classifier at 1000 randomly samplee state-action pairs (taken from the same dataset), convert these predictions to importance weights using Eq. [ normalize the importance weights to sum to 1, and then take the weighted average of the randomly-sampled states.
networks.
To visualize the predictions from C-learning (Fig. 2bp, we had to modify these environments to clude the global X coordinate of the agent in the observation. We learned policies for solving these modified tasks by running the SAC (Haarnoja et al., 2018) implementation in (Guadarrama et al.) 2018) using the default hyparameters. We created a dataset of le5 transitions for each environment. We choose the maximum horizon for each task based on when the agent ran out of the frame (200 steps for falfCheetah-22. 1000 steps for Hopper-v2, 1000 steps for Walker2d-v2 and 300 steps for Ant-v2) 22). We then trained TD C-learning on each of these datasets. The hyperparam- eters were the same before, except that trained for 3e4 batches. We evaluated the classifier
19

---

Published as a conference paper at ICLR 2021
K4
Sawyer Reach
Jaco Reach
Finger
Hand
Pen
Sawyer Push
Sawyer Window Sawyer Drawer
Figure Continuous Control Environments
at 1000 randomly-samples state-action pairs taken from a separate validation set, computed the im- portance weights as before, and then took the weighted average of the rendered images of each of states. We normalized the resulting images to be in [0, 255].
these 1000
G.3 GOAL-CONDITIONED RL EXPERIMENTS
In this section we describe the continuous control tasks used in our experiments (shown in Fig. 8 as well as the hyperparameters used in our implementation of goal-conditioned C-learning. One important detail that we used a subset of the state coordinates as the goal in many tasks. For example, in the Jaco Reach task, used just the joint angles, not the joint velocities, as the goal. When C-learning is only conditioned on a subset of the state coordinates, it estimates the marginal future state distribution over just those coordinates. Unless otherwise mentioned, environments used the default episode length. Code will be released.
Jaco Reach This task is based on the manipulation environment in Tassa et al. (2020). We sampled goals by resetting the environment twice, using the state after the first reset the goal. For this task we used just the position, not the velocity, of the joint angles as the goal.
Finger This task is based the F Finger task in Tassa al. (2018). We sampled goals by resetting the environment twice, using the state after the first reset as the goal. For this task we used the position of the spinner the goal.
Hand This task modified version of the door-human-on task Fu et al. (2020), but modified remove the door, so just the hand remains. We sampled goals by taking 50 random actions, recording the current state as the goal, and then resetting the environment. This task used the entire state the goal. Episodes had length 50.
Pen This task based on the ben-human-vo task in Fu et al. (022)). We sampled goals by randomly choosing state from dataset of human demonstrations provided in Fu et al. (2020). For this task we used the position (but not orientation) of the pen as the goal.
Sawyer Reach This task is based the SewyerReechxYZE.. let al. (2020). We used the default goal sampling method, and used the end effector position as the goal. Episodes had length 50.
environment from Yu
Sawyer Push This task is based on the environment from Yu et al. 2020). We sampled goals uniformly from Unif([-O0. 0.1, 0.1], [0.5, 0.9), 00.015, 0.015J), using the same goal for the arm and puck. Episodes had length 150.
environment from Yu et al. (2020). We randomly sampled the initial state and goal state uniformly from the possible positions of the window inside the frame. The goal for the arm was set to be the same the goal for the window. Episodes had length 150.
Sawyer Window This task is based on the
20

---

Published as a conference paper at ICLR 2021
C-learning
TD3 Next State Relabeling
Jaco Reach
0.9
0.99
Finger
0.99
0.99
Hand
0.3
0.8
Pen
0.7
0,99
Sawyer Reach
0.99
0.99
Sawyer Push
0.99
0.99
Sawyer Window
0.99
0.99
Sawyer Drawer
0.99
0.99
Table I: Values of the discount y for C-learning and TD3 with Next State Relabeling
environment from Yu et al. (2020). We randomly sampled the initial state and goal state uniformly from the feasible positions of the drawer. The goal for the arm was set to the same as goal for the window. Episodes had length 150.
Sawyer Drawer This task is based on the wwwverrrraeerpeeEnneee
Our implementation C-learning is based on the TD3 implementation Guadarrama et al. (2018). We learned stochastic policy, but (as expected) found that all methods converged deterministic policy. We list the hyperparameter below, noting that almost all were taken without modification from the SAC implementation in Guadarrama et al. (2018) (the SAC implementation has much more reasonable hyperparameters):
Actor network: 2 fully-connected layers of size 256 with ReL.U activations.
Critic network: 2 fully-connected layers of size 256 with ReLU activations.
Initial data collection steps: le4
Replay buffer size: le6
Target network updates: Polyak averaging at every iteration with 0.005
Batch size: 256. We tried tuning this but found effect.
Optimizer: Adam with learning rate of 3e-4 and default values for B
Data collection: We collect one transition every gradient step.
When training the policy (Eq. ??), we used the same goals that we sampled for classifier (Eq. ??), with 50% being the immediate next state and 50% being random states. The most sensitive hyper- parameter was the discount, 7. We therefore tuned y for both C-learning and the most competitive baseline, TD3 with next state relabeling (Lin al. 2019). The tuned values for shown in T We used 7 = 0.99 for the other baselines.
In our implementation of C-learning, we found that values for the importance weight became quite larger, likely because the classifier was making overconfident predictions. We therefore clipped the values of to be in [0, for most tasks, though later ablation experiments found that the precise value of the upper bound had little effect. We used range of [0, 50] for the finger and Sawyer tasks. Further analysis of the importance weight revealed that effectively corresponds the planning horizon; clipping the importance weight corresponds to ignoring the possibility of reaching goals beyond some horizon. We therefore suggest that 1/(1 (1-7) a reasonable heuristic for choosing the maximum value of w.
H ANALYTIC EXAMPLES OF Q-LEARNING FAILURES
In this section describe few simple MDPs where Qeleanning with hindsight relabeling fails to leamn the true future state distribution. While we describe both examples as discrete state MDPs, we assume that observations continuous and noisy, described in Appendix G
21

---

Published as a conference paper at ICLR 2021
H.1 EXAMPLE 1
The first example is a Markov process with n states. Each state deterministically transitions to itself. We will examine the one state, 81 (all other states are symmetric). If the agent starts at 81, will remain at at every future time step, so p(se+ 8, = =1) = (st+ 81).
We use X, defined above, to denote the relabeling fraction. The only transition including state 81 is (s, $1; St+1 81). We aim to determine Q = Q 8 = 81, St+ = =s1). There are two possible ways we can observe the transition (st = $1, St+ - و1, St+ = 81). First, with probability 1 we sample the next state St+, and the TD target is 1. Second, with probability À sample random state with TD target yQ, and with probability 1/n this random state is 81. Thus, conditioned on St+ S1, the Bellman equation is
1 1
w.p. 1
w.p.
Solving for Q, get Q*
1-y This Q function is clearly different from the true future state 1-
distribution, p(st+ St =1) (St+ 81). First, since A < 1, the Q function is greater than one discrete of states cannot be greater than one. Second,
n
(Q" >> 1), but density function even if we normalized this Q function to be less than one, we observe that the Q function depends on the discount (7), the relabeling ratio (A), and the number of states (n). However, the true future state distribution has no such dependence. Thus, we conclude that even scaling the optimal Q function by a constant (even one that depends on y!) would not yield the true future state distribution.
H.2 EXAMPLE 2
Our second example is a stochastic Markov process with two states, 81 and 82. The transition probabilities
if sttt1 = S1
p(s
St = 81) =
p(st+1 8tc =2) = 1 (8t41 82)
if St+1
We assume that we have observed each transition once. To simplify notation, we will use Qij = Q(s: Si. Stt sz). There three ways to end up with Qn the LHS of a Bellman equation: (1) the next state is $1 and we sample the next state as the goal, (2) the next state is 81 and we sample random state the goal, and (3) the next state is 82 and we sample random state the goal.
w.p. 1 1- X
Qu
7Q11
w.p.
7Q21
w.p.
We can likewise observe Q12 on the LHS in the same three ways: (1) the next state is and we sample the next state as the goal, (2) the next state is $1 and we sample random state as the goal, and (3) the next state is and we sample random state as the goal.
w.p. 1 -
Q12
7Q12
w.p.
(15)
7Q22 22
w.p.
We can only observe Q21 on the LHS in one way: the next state is 82 and we sample we sample random state as the goal:
Qu = {1Q21 w.p. 1.
(16)
We can observe 222 the LHS in two ways: (1) the next state is and sample the next state as the goal, (2) the next state is 82 and we sample random state as the goal:
w.p. 1-x+
Q22
(17)
7222
w.p. 1-
22

---

Published as a conference paper at ICLR 2021
To solve these equations, immediately note that the only solution to Eq. 16jis Q21 0. Intuitively this makes sense, as there is zero probability of transition 82 - 81. We can also solve Eq. 17 directly:
7> 2
2 2A
2 2-x
2- Q2
2
Q22
Q22
2
2
2 2- 7d
Next, we solve Eq.
15
We start by rearranging terms and substituting our solution to Q22:
7> 2
?
72 2A
A 7
(1
Q12 112=1-11
Que = =
+
= -1
2
2 2 - ー
2 2
Rearranging terms, obtain the following:
2(1 - 27
Q12
(2 72)(2 x 7
Finally, we solve for Q1, recalling that our solution Q21 = 0:
1> 2 1Qn = -
71
2
(1
Qz
Q1 = 2-7À
2
To summarize, Q-learning with hindsight relabeling obtains the following Q values:
2(1 A) Q
2(1 - 2y Q21 Q22 - - 2 7
2 - 2A
2 7X Q1
(2 >2) X
For comparison, we compute p(s++ S1 $1). the probability that the agent remains in state 81 in the future. The probability that the agent is in at time step A is 1/2 so the total, discounted probability
p(st+ = s1 (1)) = (1 -1
2 + +...)
A
= =(1 (1-7)) Σ
2
A=0
1-7 2 27 7/2
2 7
Thus, in general, the value Q11 does not equal the future state distribution. One might imagine that Q-learning acquires Q values that are only accurate up to scale, so we should consider the normalized prediction:
Qu
2-
Q1 Q12
1
2- 2-X+7À
4- 4 3yd
However, this normalized Q-learning prediction is also different from the true future state distribu- tion.
23

---

Published as a conference paper at ICLR 2021
1 PREDICTIONS FROM C-LEARNING
Figures 9 and 10 visualizes additional predictions from the C-learning model in See. 6 In each image, the top half shows the current state and the bottom half shows the predicted expected future state. Animations of these results can be found on the project website.
(a) HalfCheetah-v2, 7 0.9
(b) HalfCheetah-v2 v2, 7 = 0.9
(c) Ant-v2, 7 0.5
(d) Ant-v2, = 0.9
(e) Ant-v2, 7 0.99
Figure 9: Predictions from C-learning
24

---

Published as a conference paper at ICLR 2021
(a) Walker2d-v2, ? 0.5
(b) Walker2d-v2. 0.9
(c) Walker2d-v2, 7 = 0.99
(d) Hopper-v2, y 0.5
(e) Hopper-v2, 0.9 Figure 10: More Predictions from C-learning
25


Reviews:
[{"review_id": "X7q8n4pGVow", "reviewer": "AnonReviewer5", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "[summary]\nThis paper studies to predict future state density function by using an indirectly method via classification. The main idea is to sample the future state from two sources: 1) from replay buffer, 2) the actual next state in the trajectory (in off policy setting we only need the next state) and then use a classifier to distinguish them. By Bayesian rule we can recalculate the conditional density function by the ratio of the classifier. The paper compare this method with several baseline and find that they can predict the conditional density function very close to reality.\n\n[originality]\nI really like the idea and the method seems very interesting and novel to me. However, the main concern is the motivation of the classifier. It seems to me that we can classify the true $s_{t,+}$ with any source of distribution of $p(s_{+})$. For example, in your Algorithm 1 or 2, we can replace $p(s+)$ with arbitrary distribution (even the distribution we create), then the whole derivation still hold. I believe it is reasonable to try to distinguish $p(s+)$ with $p(s+|s_t, a_t)$, but did you compare with any other prior distribution of $p(s+)$?\n\n[clarity and theoretical soundness]\nMy major concern of the paper is the clarity which I will explain in the sequel.\n- Notation.\n The main notation of the future state density function is abused the notation of $p$. I think in Definition 1 the right hand side you are defining a new condition density function, not a new future state. So I would recommend to write it as:\n$$p_{+}(s'|s,a) = (1-\\gamma)\\sum_{t=0}^{\\infty}\\gamma^{t}p_{t}(s'|s,a),$$\nwhere $p_t(s'|s,a)$ is the distribution if $s'$ occur $t$ step after the occurrence of the $s,a$ pair.\nMany notations in the main text has this kind of problem where it is hard to distinguish the future distribution with the original distribution.\n- Main message in section 5 is not clear.\nAlgorithm box 1 is confusing. It seems to me that we have double terms of $s_{t,+}$, and they are all used in the loss function (F=1 and F=0). If I understand correctly, we should put $s_{t,+,0} \\sim p(s_{t,+}$ (again I don't like this notation, p can be any other meaning) and $s_{t,+,1} \\gets s_{t+\\delta}$, and the loss function for $F=0$ uses $s_{t,+,0}$ and $F=1$ uses $s_{t,+,1}$. \nAnd without looking at the paragraph in details, it is hard to tell what is $F$ at the first glance. I feel like you can rewrite this section a little bit by motivating the reader why we consider using a classifier.\n-Minor.\n  1. Remark 1 should add some assumption, otherwise we can always think tabular case is a special case of in the continuous state space, where the probability mass function is not 0.\n  2. Eq.(1) should be $p(F=1|s_t, a_t, s_{t,+}) = $XXX, missing a $s_{t,+}$ in left hand side. Similar for the next line.\n  3.The sentence after Eq.(2), why we can get rid of estimating the marginal density? Not clear and no explanation.\n  4. Eq.(4) missing an expectation for $E_{s_{t+1}, a_{t+1}}$.\n  5. Eq.(5), we should put $F(\\theta, \\pi) = $ in the equation not a line above.\n  6. Eq.(5), the subscript of expectation is not standard (compared to Eq.(3)).\n  7. Unclear reason why we want to stop gradient in Eq.(7) and Algorithm 3. Is that stabilized the learning process?\n\n[related work]\nIn the first line of the page 2, I think \"contrastive approach\" is not accurate. I didn't see any contrastive objective in the paper.\nI feel like the density based methods in off-policy evaluation(e.g. Liu et. al. 2018 and DICE family (e.g. Nachum et. al. 2019)) is more relevant to value based method, where we can set the reward function as the indicator function and estimate the average reward of the policy $\\pi$. Their methods are also based on a recursive objective, I think a comparison between that will be beneficial to further clarify your contribution.\n\n[reference]\n1. Qiang Liu, Lihong Li, Ziyang Tang, Dengyong Zhou. Breaking the Curse of Horizon: Infinite-Horizon Off-Policy Estimation\n2. Ofir Nachum, Yinlam Chow, Bo Dai, Lihong Li. DualDICE: Behavior-Agnostic Estimation of Discounted Stationary Distribution Corrections\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "UGXMNEVBVeL", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary:\nThis work presents a goal-conditioned RL, which estimates probability density using a classifier. \n\nStrengths:\n+ The problem is well explained, the logical structure seems adequate. \n+ The paper is well written and clear. \n+ The approach technically sounds and mathematically well-formulated.\n\nWeaknesses:\n- Although the reported evaluation results are competitive to baselines, it would have been even stronger if the performance is substantially improved. Do you have any insight on how better results can be achieved?\n\n ", "extra_scores": {}, "extra_text": {}}, {"review_id": "Thjf-hg76E", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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 authors propose a new algorithm, called C-learning, which tackles goal-conditioned reinforcement learning problems. Specifically, the algorithm converts the future density estimation problem, which goal-conditioned Q learning is inherently performing, to a classification problem. The experiments showed that the modification allows a more precise density estimation than Q-learning, and in turn, a good final policy.\n\nOverall, I like the general idea to use classification as a tool for estimating the future density function. Especially, the idea is valuable in that it allows a better understanding of prior Q-learning based approaches in choosing a sensitive hyperparameter. However, the manuscript can be enhanced much by adapting more precise notations and adding more explanations on equations:\n* $p$ is highly overloaded; it is used to represent future conditional state density function and marginal state density function for both on-policy and off-policy, and transition dynamics.\n* Also, it would be important to notate $\\pi$ in most of the parts, including $p$, $Q$, and $C$ (unless it is very obvious). Especially, the current notation is very confusing when the off-policy algorithm is introduced.\n* Related to this concern, I am not fully convinced of the off-line algorithm due to the marginal future state distribution $p(s_{t+})$. Doesn’t it supposed to be $p^{\\pi_{\\text{eval}}}(s_{t+})$, and therefore, does the marginal distribution also need to be adjusted as $p(s_{t+}|s_{t+1},a_{t+1})$?\n* It would be also helpful if the full derivation for Equation (6) is included in the main manuscript.\n\n-- After rebuttal\n\nI've read the authors' feedbacks and other reviewers' comments. My major concern was the clarity of the manuscript as other reviewers mentioned, and I believe the concern has been resolved during the rebuttal period. I adjusted my ratings representing that.", "extra_scores": {}, "extra_text": {}}, {"review_id": "Eb96jSSfZA", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "This paper explores learning a classifier to predict if a given state/observation will be reached in the future from the current state and action pair. Using this classifier, the paper is able to create a probability density function that could be conditioned on reaching a goal state. This idea is interesting and could leverage large scale self-supervised learning to build the future state probability density function. I have some concerns which are listed below.\n\n1. How does the method work on low dimensional action spaces where the probability of reaching a future state from current state and action is usually higher?\n\n2. How does the method work on high dimensional tasks that have discrete-continuous dynamics due to multiple contacts, such as the pen task. The probability of reaching a future state from the current state + action is very low and the experiments show only training on a human demonstrated dataset. Can the policy be used to control the hand to reach a target pen position very different from the human demonstration?", "extra_scores": {}, "extra_text": {}}, {"review_id": "EHYJOuthYr1", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper studies a problem of predicting future state distribution in an MDP. The approach taken is an indirect approach which first predicts whether an observation comes from the future and transfers this binary prediction via Bayes rule to predictions over future states. \n\nConceptually the paper's appears novel but a previous similar work was very relevant. In UOM paper, Definition 1 is almost exactly the same as the discounted state occupancy function defined the UOM paper, just an extra normalization constant (1-\\gamma). Apparently at this core the idea is not novel. However, the paper's development of casting the prediction problem into two stages (first binary prediction) and using Bayesian to transfer into the future state distribution is novel. The connection of UOM paper is interesting but not discussed unfortunately. In the UOM paper, the authors there appear to focus on reward-less MDPs, where you can generate/compute the value function given a reward function on the fly. Here the paper focuses on more on the estimation of the the discounted state occupancy function, -- this is my interpretation.   \n\nParagraph \"In discrete state spaces\":\nintroducing this reward: again this is just another interpretation of the discounted state occupancy function in UOM (equation 2). \n\nRemark 1:\nI don't understand the point of Remark 1. do you mean for a continuous-state problems, the prob of reaching some particular state is zero? Isn't that that obvious? What is the point here?\n\nHypothesis 1 and 2: I don't know whether they make sense. The paper relies on the experiments to try to make sense of it. I'm not sure this is a sound approach. Why testing these hypotheses is interesting at the first place? At least this isn't clear from the paper. \n\n\nUOM paper (not cited):\nhttps://papers.nips.cc/paper/5590-universal-option-models\n\nI've read the authors' feedbacks and other reviewers' comments. R5's main concerns are the clarity and the motivation of Bayessian classifier and off-policy learning. That should have been resolved from authors' feedbacks. \n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: **Overview**: This paper provides a new clustering-based method to predict future probability density of a policy. It provides comparable performance to prior Q-learning-based methods, but without careful hyper-parameter tuning.

**Pro**: The method of using clustering to estimate future density is novel. Both theory and experiments appear solid. In the rebuttal phase, the authors convinced all the reviewers by addressing their concerns. The reviewers unanimous tend to acceptance.

**Con**: The reviewers had many concerns before the rebuttal. But these were addressed by the authors. 

**Recommendation**: The C-learning method proposed in this paper is novel and can be potentially useful in practice. Both theory and experiments are solid and convincing. Hence the recommendation is accept.     
Decision: Accept (Poster)