Distributional Distance Classifiers for Goal-Conditioned Reinforcement Learning

Thanks for the valuable feedback. We are pleased to hear positive remarks about the significance of our contributions. In what follows, we will try to answer the questions as best we can:

The problem formulation in this work is not exactly the stochastic shortest path problem as the discounting factor is < 1. Will the analysis still go through if the discounting factor is 1?

The analysis in Sec. 4.2 and Appendix A shows that the (discounted) probability objective used in our work is closely related to the (undiscounted) stochastic shortest path problem. This analysis requires that (discounted) probability objective is a discount factor strictly less than one; we have revised Appendix A to note this. Please let us know if this doesn't make sense, or if we have misunderstood the question.

In related work, please also discuss the relationship between this work and the recent theoretical advancement in goal-conditioned RL

We have added a paragraph to the related work section noting the similarities and differences with our work. We welcome additional suggestions for related work to discuss.

The proposed method has the same spirit as distributional RL. I am wondering whether quantile regression can also be extended to solving goal-oriented RL?

This is a very exciting future direction that is beyond the scope of this paper. The contrastive RL framework offers flexibility to arbitrarily define the bins of the distributional NCE algorithm, as long as their union covers all the future timesteps [1, \infty). Instead of choosing bin boundaries as successive timesteps as we do in the paper (akin to C51), one can choose them to be the quantiles of a normalized distance classifier P(H | s, a, g) (akin to QR-DQN).

I would like to see how the algorithm behaves when H is very small, such as H=1 or 2

In the case of H=1, Distributional NCE reduces to the Contrastive NCE baseline, which is worse than our method (see Fig. 4). However, we also observed that varying the number of bins between 11 and 101 did not significantly impact the performance in Appendix D.6 Fig. 12, which hints that increasing the number of bins beyond a point has diminishing improvements. We have revised the paper (Appendix D.6) to clarify that the performance our method does degrade for very small $H$.

We thank the reviewer for the detailed review. It seems like the reviewer's main concern is about mathematical correctness and precision. We believe that all the theoretical results are correct, and have revised the paper to make the mathematical notion more clear (blue text). We answer specific questions below. Do these revisions and answers fully address the reviewer's concerns? We look forward to continuing the discussion.

I am not sure if propositions 1-3 are correct, the statements themselves are quite vague

We believe that these propositions are correct, and have revised the statements to make the notation and results more clear. Please let us know if there is any notation is ambiguous or confusing, and we would be happy to further revise this section.

what is the argument being made in the proof of proposition 2?

Proposition 2 argues that the MC distance is generally not a valid metric. The proof is a proof by contradiction, so we construct an example where the MC distance is not a valid metric (i.e., it violates the triangle inequality). We have added a note at the start of the proof to highlight that it is a proof by contradiction.

Is the proof for proposition 1 referring to the mdp in figure 1a?

Yes, the proof for Proposition 1 is referring to the mdp in Fig. 1(a). We have revised the proof to clarify this point.

What is a Mount Carlo Distance Function? Does it depend on the policy being played? Is there any expectations or does it just take in raw observations?

We added a formal definition of the Monte Carlo distance function at the start of Sec. 4. Monte Carlo (MC) distance function d(s,a,g) takes as input state-action-goal tuple (s, a, g) and outputs the expected number of steps a policy takes to go from a start state s and action a to a goal state g. As the name suggests, it is computed from Monte-Carlo trajectory rollouts of the policy. MC distance thus depends on the policy and is an expectation.

In the second equation on page 3, why is the expectation on the left of the sum different than the one on the right ?

In this equation ($\arg\min_C \cdots$), the expectations are different because contrastive learning entails sampling positive and negative examples from different distributions. The first expectation in the equation is under a positive distribution (goal states that occur in the future timesteps of (s,a)) with a training label=1 and the second expectation is under the negative distribution (random goal states that have nothing to do with (s,a)) with a training label=0.

Why is Monte-Carlo distance estimation equivalent in the limit to learning a normalized distance classifier?

We have revised Sec. 4.3 to clarify that these are not exactly equivalent. MC distance function can be estimated using a normalized distance classifier as follows:

• MC distance d(s,a,g) = \sum_{i=0}^\infty ( i * P(i | s, a, g) ),

where P(H | s, a, g) is the normalized distance classifier.

Appendix D.4 is empty

We have added a sentence at the start of Appendix D.4 to clarify that this subsection contains just Fig. 10 and the text in its caption.

We thank the reviewer for the detailed review. It seems like the reviewer's main concern is about (i) the discrepancy in reward functions used in MC distance and contrastive RL frameworks and (ii) including a comparison with prior GCRL methods that perform reward shaping. We have revised the paper to include the reviewer’s suggestions (blue text). We answer specific questions below. Do these revisions and answers fully address the reviewer's concerns? We look forward to continuing the discussion.

It would be interesting to see how this method compares with shaping rewards.

Prior work has shown that reward shaping performs quite poorly on these Fetch environments, even when combined with HER (https://arxiv.org/pdf/1707.01495.pdf, Fig 5, success rates all <10%). We have revised the additional experiments section (Appendix D.1) to note this.

Subtracting -1 from all rewards acts like shaping the reward function which might lead to suboptimality as already shown in several works.

We agree that, in practice, RL methods that maximize a 0/1 return can sometimes work better than those that maximize a -1/0 return (despite these two objectives being mathematically equivalent in the discounted, infinite-horizon setting). Note that none of our baselines explicitly use the -1/0 reward function; rather, they either (i) estimate some form of distance/distribution directly from reward-free data or (ii) use temporal difference learning with a 0/1 reward (e.g. TD3+HER, MBRL baseline in Fig. 6). Our analysis discusses the -1/0 reward because it allows us to draw a connection between the standard RL problem (reward maximization) and the standard stochastic shortest path problem (minimizing expected steps to goal).

It is more common to simply use a shaping reward over the 0/1 reward function.

We have revised Sec. 2 to clarify that, while there are a number of methods that predict distance, it is also a common practice to use shaping reward. Nonetheless, we believe our analysis is useful because we highlight the intricacies and shortcomings of using MC distance functions, and how these shortcomings can be fixed by taking a probabilistic perspective of distances.

Why do MC distance regression methods estimate the Q function? Why can't I use the estimated distance as a reward?

MC distance regression methods [2,3] often use the learned distance function to select actions, similar to how Q functions are used to select actions. However, our theoretical analysis (Proposition 2) show that learned distances are not valid Q functions – they don't correspond to the expected returns of a clear reward function, so selecting actions by minimizing these learned distances may not necessarily correspond to reward maximization.

Prior work has used learned distances as reward [1]. However, from a theoretical perspective, this is a bit tricky, as it's unclear what global objective these methods are optimizing. That is, what does the sum of these temporal distances mean? These prior methods can achieve excellent results. Our method builds on these prior works by offering them a stronger theoretical footing, which can improve results in certain stochastic settings (see Fig. 4 and Appendix Fig. 6 and 7).

In section 4.1, it is unclear in the toy examples when the episode ends.

The episode ends when the agent reaches the goal state. Our revised paper on OpenReview includes this clarification.

Suppose, C(s, a, g)[H] = [0, 0, ...]. Will the estimated distance between s and g be 0?

The MC distance is ill-defined in this case. In practice, this corresponds to the setting where we've never seen any trajectories between s and g, so we cannot estimate the number of steps between them. We've revised Sec. 4.3 in the paper to include example.

If the classifer predicts normalized probabilities, then p(g|s, a, H=1, 2, 3, ...) cannot be equal to [1, 1, 1, ...].

Correct: a _normalized_classifier cannot equal [1, 1, 1, …]. p(g|s, a, H=i) refers to the probability of reaching the goal state g as opposed to some other state at i^th timesteps, and is thus a quantity in [0,1]. On the other hand, p(H=i |s, a, g) refers to the probability of reaching the goal g at i^th timestep, given that the policy reaches the desired goal at some future timestep. Thus,

• \sum_i p(g | s, a, H=i) \neq 1
• \sum_i p(H=i | s, a, g) = 1

The algorithm is not completely clear. What is dt in the algorithm box?

dt refers to the relative time index of the future state which is used to index the corresponding bin of the Distributional NCE classifier. We have updated the algorithm block to include this information.

[1] K. Hartikainen, et al. Dynamical distance learning for semi-supervised and unsupervised skill discovery. arXiv:1907.08225, 2019.

[2] S. Tian, et al. Model-based visual planning with self-supervised functional distances. In ICLR, 2021.

[3] D. Shah, et al. Ving: Learning open-world navigation with visual goals. In IEEE ICRA, 2021.

The responses do clarify some of the concerns. But some of the concerns still stand,

(1) It is true that HER often does not work with shaping rewards but works like [1] have shown good results with shaping rewards and hindsight experience replay. The HER paper considers just a simple shaping reward of L2 distance, but there can be other forms of shaping rewards too.

(2) Are you sure 0/1 and -1/0 are mathematically equivalent?

(3) The distance term $d^\pi(s, a, g)$ can very well be used as rewards. If not as a reward, then definitely as a potential-based shaping reward.

[1] Durugkar et. al., Adversarial Intrinsic Motivation for Reinforcement Learning

I believe that the work does show an interesting perspective of using probabilistic distances rather than MC distances. But, some additional studies are required as there are other ways in which distances are incorporated into policy learning. So, I stand by my rating.

We thank the reviewer for the valuable feedback.

A lot of research in goal-conditioned RL uses probability as criterion. The paper should include a comparison to compare the algorithm in the paper and previous algorithm.

Our experiments in Fig. 4 do compare with prior methods that use probability as a criterion (Contrastive NCE (red), C-Learning (yellow)). We'd welcome suggestions for additional baselines to compare against.

We thank the reviewer for the detailed review. It seems like the reviewer's main concern is about the temporal consistency objective and paper writing. We have revised the paper to include the reviewer’s suggestions (blue text). We answer specific questions below Do these revisions and answers fully address the reviewer's concerns? We look forward to continuing the discussion.

The temporal consistency objective does not make sense in certain reinforcement learning problems. Some goals can have a minimum number of steps needed before they can be reached. For example, in a gridworld where the shortest path to the goal is 10 steps away, P(reaching the goal in 9 steps) = 0, whereas P(reaching in 10) can be high for a good policy. It would be useful to address this aspect of temporal consistency or even highlight it in an experiment with such temporal constraints, or remove it as it does not naturally stem from the main hypothesis of the paper.

Thanks for bringing up this great example; we believe the temporal consistency regularizer does make sense in this example. In this example, let’s imagine a start state s_0, a goal state g, and actions a_i ~ \pi(.|s_i) for all i \in [0, \infty). We further imagine that the goal state can only be reached after 10 steps:

• P(s_0, s_{i}=g,a_0) = 0 for all i < 10 && P(s_0, s_{0 + “10”}=g,a_0) > 0. Nevertheless, the following still holds:
• P(s_0, s_{0 + “10”}=g,a_0) = E_{s_1 ~ p(. | s_0, a_0), a_1 ~ \pi(.|s_1)} [ P(s_1, s_{1 + “9”}=g,a_1) ] Note that the term on the right-hand side refers to a future state that is 9 steps away relative to t=1, i.e. still the 10th timestep w.r.t the starting point t=0. We've revised the paper to include this discussion in Appendix C.

Does the MC distance function already account for the stochasticity in action selection?

The MC distance function is conditioned on the current action, so it does not account for the stochasticity in action selection at current timestep. However, it does account for the stochasticity in action selection at (finite) future timesteps since MC distance is a probabilistic average over the number of finite timesteps to the goal. However, MC distance discards the possibility of never reaching the commanded goal, in which case, the distance to the goal is infinite. In many real-world scenarios, there exists a non-zero probability of failing (a.k.a risk) to reach the goal, which is very important for correct decision-making. We show this in the toy MDP from Fig. 1(a) in the paper. Another example is an autonomous car that needs to cross the intersection but it is red light. MC distance suggests the vehicle to run the red light as it is the minimum-time path to the goal. Alternatively, our probabilistic framework accounts for the non-zero risk of collision with a passing vehicle upon running a red light, which would prevent the car from reaching its goal state, thereby making the right choice to wait until it’s green light.

specify the number of runs that were averaged over in the learning curves. The work should also mention what the shaded area around each curve represents and how they curves were smoothed, if any such technique was applied.

The curves show the mean performance with the shaded region indicatingthe 95% confidence interval computed across 5 random seeds. We do not use any smoothing or filters to post-process the results. These details were in the original submission (Appendix E), but we have revised the main text to point readers to this appendix.

Minor comments

Thanks for the suggestions to improve the paper writing! We have addressed these changes (in blue color) in the revised version of our paper on OpenReview:

• Added a formal definition of the Monte Carlo distance function in Sec. 4
• Revised Sec. 4.1 to better explain the pathological behaviors exhibited by MC distance functions.
• Clarified that NCE stands for Noise Contrastive Estimation.
• Removed duplicate reference to Yecheng et al. 2022 (page 11)