{'fraction_non_alphanumeric': 0.05593794384354856, 'fraction_numerical': 0.01682508467169234, 'mean_word_length': 4.349698032339762, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 6, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Understanding Hindsight Goal Relabeling Requires Rethinking Divergence Minimization

Hindsight goal relabeling has become a foundational technique for multi-goal reinforcement learning (RL). The idea is quite simple: any arbitrary trajectory can be seen as an expert demonstration for reaching the trajectory's end state. Intuitively, this procedure trains a goal-conditioned policy to imitate a sub-optimal expert. However, this connection between imitation and hindsight relabeling is not well understood. Modern imitation learning algorithms are described in the language of divergence minimization, and yet it remains an open problem how to recast hindsight goal relabeling into that framework. In this work, we develop a unified objective for goal-reaching that explains such a connection, from which we can derive goal-conditioned supervised learning (GCSL) and the reward function in hindsight experience replay (HER) from first principles. Experimentally, we find that despite recent advances in goal-conditioned behaviour cloning (BC), multi-goal Q-learning can still outperform BC-like methods; moreover, a vanilla combination of both actually hurts model performance. Under our framework, we study when BC is expected to help, and empirically validate our findings. Our work further bridges goal-reaching and generative modeling, illustrating the nuances and new pathways of extending the success of generative models to RL.


INTRODUCTION
Goal reaching is an essential aspect of intelligence in sequential decision making. Unlike the conventional formulation of reinforcement learning (RL), which aims to encode all desired behaviors into a single scalar reward function that is amenable to learning (Silver et al., 2021), goal reaching formulates the problem of RL as applying a sequence of actions to rearrange the environment into a desired state (Batra et al., 2020). Goal-reaching is a highly flexible formulation. For instance, we can design the goal-space to capture salient information about specific factors of variations that we care about (Plappert et al., 2018); we can use natural language instructions to define more abstract goals (Lynch & Sermanet, 2020;Ahn et al., 2022); we can encourage exploration by prioritizing previously unseen goals (Pong et al., 2019;Warde-Farley et al., 2018;Pitis et al., 2020); and we can even use self-supervised procedures to naturally learn goal-reaching policies without reward engineering (Pong et al., 2018;Nair et al., 2018b;Zhang et al., 2021;OpenAI et al., 2021).
Reward is not enough. Usually, rewards are manually constructed, either through laborious reward engineering, or from task-specific optimal demonstrations, neither of which is a scalable solution. How can RL agents learn useful behaviors from unlabeled reward-free trajectories, similar to how NLP models such as BERT (Devlin et al., 2018) and GPT-3 (Brown et al., 2020) are able to learn language from unlabeled text corpus? Goal reaching is a promising paradigm for unsupervised behavior acquisition, but it is unclear how to write down a well-defined objective for goal-conditioned policies, unlike language models that just predict the next token. This paper aims to define such an objective that unifies many prior approaches and strengthens the foundation of goal-conditioned RL.
We start from the following observation: hindsight goal relabeling (Andrychowicz et al., 2017) can turn an arbitrary trajectory into a sub-optimal expert demonstration. Thus, goal-conditioned RL might be doing a special kind of imitation learning. Currently, divergence minimization is the de facto way to describe imitation learning methods (Ghasemipour et al., 2020), so we should be able to recast hindsight goal relabeling into the divergence minimization framework. On top of that, to tackle the sub-optimality of hindsight-relabeled trajectories, we should explicitly maximize the probability of reaching the desired goal. Following these intuitions, we derive the reward function used in HER from first principles, as well as other behaviour cloning (BC) like methods such as GCSL (Ghosh et al., 2019) and Hindsight BC (HBC) (Ding et al., 2019).
Experimentally, we show that multi-goal Q-learning based on HER-like rewards, when carefully tuned, can still outperform goal-conditioned BC (such as GCSL / HBC). Moreover, a vanilla combination of multi-goal Q-learning and BC (HER + HBC), supposedly combining the best of both worlds, in fact hurts performance. We utilize our unified framework to analyze when a BC loss could help, and propose a modified algorithm named Hindsight Divergence Minimization (HDM) that uses Q-learning to account for the worst while imitating the best. HDM avoids the pitfalls of HER + HBC and improves policy success rates on a variety of self-supervised goal-reaching environments. Additionally, our framework reveals a largely unexplored design space for goal-reaching algorithms and potential paths of importing generative modeling techniques into multi-goal RL.

THE REINFORCEMENT LEARNING (RL) PROBLEM
We first review the basics of RL and generative modeling. A Markov Decision Process (MDP) is typically parameterized by (S, A, ρ 0 , p, r): a state space S, an action space A, an initial state distribution ρ 0 (s), a dynamics function p(s | s, a) which defines the transition probability, and a reward function r(s, a). A policy function µ defines a probability distribution µ : S × A → R + . For an infinite-horizon MDP, given the policy µ, and the state distribution at step t (starting from ρ 0 at t = 0), the state distribution at step t + 1 is given by: The state visitation distribution sums over all timesteps via a geometric distribution Geom(γ): However, the trajectory sampling process does not happen in this discounted manner, so the discount factor γ ∈ (0, 1) is often absorbed into the cumulative return instead (Silver et al., 2014): From 1 and 2, we also see that the future state distribution p + of policy µ, defined as a geometrically discounted sum of state distribution at all future timesteps given current state and action, is given by the following recursive relationship (Eysenbach et al., 2020b;Janner et al., 2020): In multi-goal RL, an MDP is augmented with a goal space G, and we learn a goal-conditioned policy π : S × G × A → R + . Hindsight Experience Replay (HER) (Andrychowicz et al., 2017) gives the agent a reward of 0 when the goal is reached and −1 otherwise, and uses hindsight goal relabeling to increase learning efficiency of goal-conditioned Q-learning by replacing the initial behavioral goals with achieved goals (future states within the same trajectory).

IMITATION LEARNING (IL) AS DIVERGENCE MINIMIZATION
We first review f -divergence between two probability distributions P and Q and its variational bound: where f is a convex function such that f (1) = 0, f * is the convex conjugate of f , and T is an arbitrary class of functions T : X → R. This variational bound was originally derived in (Nguyen et al., 2010) and was popularized by GAN (Goodfellow et al., 2014;Nowozin et al., 2016) and subsequently by imitation learning (Ho & Ermon, 2016;Fu et al., 2017;Finn et al., 2016;Ghasemipour et al., 2020). The equality holds true under mild conditions (Nguyen et al., 2010), and the optimal T is given by . The canonical formulation of imitation learning follows (Ho & Ermon, 2016;Ghasemipour et al., 2020), where ρ exp (s, a) is from the expert: min Because of the policy gradient theorem (Sutton et al., 1999), the policy µ needs to optimize the cumulative return under its own trajectory distribution ρ µ (s, a) with the reward being r(s, a) = f * (T (s, a)). Under this formulation, Jensen-Shannon divergence leads to GAIL (Ho & Ermon, 2016), reverse KL leads to AIRL (Fu et al., 2017). Note that f can in principle be any convex function (we can satisfy f (1) = 0 by simply adding a constant).

GRAPHICAL MODELS FOR HINDSIGHT GOAL RELABELING
Consider the setting: given an environment ξ = (ρ 0 (s), p(s | s, a), ρ + (g)) where we generate a dataset of trajectories D = {(s 0 , a 0 , s 1 , a 1 , · · · )} by sampling from the initial state distribution ρ 0 (s), an unobserved actor policy µ(a | s), and the dynamics p(s | s, a). We aim to train a goal-conditioned policy π(a | s, g) from this arbitrary dataset with relabeled future states as the goals. ρ + (g) is the behavioral goal distribution assumed to be given apriori by the environment. To recast the problem of goal-reaching as imitation learning equation 6, we need to set up an f -divergence minimization where we define the target (expert) distribution and the policy distribution we want to match. The training signal comes from factorizing the joint distribution of state-action-goal differently.
For the relabeled target distribution, we assume an unconditioned actor µ generating a state-action distribution at first, with the goals coming from the future state distribution equation 4 conditioned on the given state and action. For the goal-conditioned policy distribution, behavior goals are given apriori, and the state-action distribution is generated conditioned on the behavioral goals. Thus, the target distribution (see Figure 2) for states, actions, and hindsight goals is: Note that p + µ is given by equation equation 4, and ρ µ (s, a) is similar to ρ exp (s, a) in equation equation 6. In the fashion of behavioral cloning (BC), if we do not care about matching the states, we can write the joint distribution we are trying to match as (see Figure 3): p BC π (s, a, g) = ρ + (g)ρ µ (s)π(a | s, g) In many cases, matching the states is more important than matching state-conditioned actions (Ross et al., 2011;Ghasemipour et al., 2020). The joint distribution for states, actions, behavioral goals for π (see Figure 4) is: p π (s, a, g) = ρ + (g)ρ π (s, a | g) (13) Figure 5: the future state distribution p + π (s + | s, a) of a goal-conditioned policy when starting from a state s visited by µ.
However, it is important to recognize that even after adding this state-matching part, there is still a missing component of the objective. Divergence minimization encourages the agent to stay in the "right" state-action distribution given the benefit of hindsight, but we still need the policy to actually hit the goal (see Figure 1). When we condition the policy on a goal, we should maximize the likelihood of seeing that goal in the future state distribution (see Figure  5). Together with a maximum entropy regularization on the policy H(π) (Ho & Ermon, 2016;Schulman et al., 2017), we propose the following goal-reaching objective: Compared to equation 12 and equation 6, the f -divergence term equation 14(a) swaps the order between the expert and the policy. The coefficient β controls the importance of "hitting the goal". This incentive is already implicit in hindsight-relabeled data, as in many cases a BC objective alone can learn to hit the goal as well (Ding et al., 2019;Ghosh et al., 2019;Lynch et al., 2019;Jang et al., 2021). However, hindsight-relabeled trajectories are often sub-optimal demonstrations: not every action is acting towards achieving the goal. Thus, maximizing the likelihood of achieving the goal is crucial, and it plays a key role in deriving the reward function of HER (Andrychowicz et al., 2017).

BRIDGING GOAL-REACHING AND GENERATIVE MODELING
In this section, we study how to optimize the proposed unifying objective 14. We show that the Q-function trained for goal-reaching Q θ (s, a, g) is implicitly doing generative modeling. Its temporal difference is modeling the density ratio between the hindsight-relabeled distribution and the goalconditioned behavioral distribution. It also approximates an energy-based model for future-state distribution when marginalized over the goal distribution. In section 4.1, we demonstrate how goalconditioned Q-learning does divergence minimization (equation 14(a)). In section 4.2, we show how Q-functions can define an EBM for cumulative future states, which in turn allows the policy to maximize goal likelihood (equation 14 b+c). In section 4.3, we show that combining the derived results yields the HER reward. In section 4.4, we study when a BC loss can help by analyzing the loss terms being left out by the HER reward.

DIVERGENCE MINIMIZATION WITH GOAL-CONDITIONED Q-LEARNING
This section decomposes equation 14(a). We start with the f -divergence bound from equations equation 5 and equation 6.
Now we negate T to get r(s, a, g) = −T (s, a, g), and the divergence minimization problem becomes: max We can interpret r as a GAIL-style (Ho & Ermon, 2016) discriminator or reward. However, we aim to derive a discriminator-free learning process that directly trains the Q-function corresponding to this reward Q θ (s, a, g) = r(s, a, g) + γ · P π Q(s, a, g) where P π is the transition operator: P π Q(s, a, g) = E p(s |s,a)π(a |s ,g) [Q θ (s , a , g)]. Re-writing the equation equation 16 w.r.t Q: Here, the following lemma shows that in the goal-conditioned case, we can use arbitrary offline trajectories to evaluate the expected rewards under goal-conditioned online rollouts: Lemma 4.1 (Online-to-offline transformation for goal reaching). Given a goal-conditioned policy π(a | s, g), its corresponding Q-function Q π (s, a, g), and arbitrary state-action visitation distribution ρ µ (s, a) of another policy µ(a | s), the expected temporal difference for online rollouts under π is: Using Lemma 4.1, the objective in equation 16 now becomes: The function f * is the convex conjugate of f in f -divergence. We can pick almost any convex function as f * as long as ((f * ) * )(1) = 0. For instance, in the tradition of Q-learning, we can use: where r and c are constants. Its convex conjugate is f ( For any r, we can always pick a c that will ensure f (1) = (f * ) * (1) = 0, and c does not affect the learning process. In summary, we have derived a way to minimize the first term D f (p µ (s, a, s + ) p π (s, a, g)) in equation 14 directly using goal-conditioned Q-learning.

EBM FOR PREDICTING (AND CONTROLLING) THE FUTURE
In this section, we study how to maximize the goal likelihood term equation 14(b) by defining an energy-based model (EBM) to predict the future-state distribution for a policy, which the policy can in turn optimize to control the future-state distribution. We start with the Bayes rule: This relationship reflects that, if we define an EBM for ρ π (s, a | s + ) = exp q(s, a, s + )/Z q (s + ) where Z q (s + ) = S×A exp q(s, a, s + )dsda, then we can contrast the dynamics defined in equation 4 with the marginal goal distribution defined in equation 13. In a slightly overloaded notation, we will now define a Q-function as Q θ (s, a, g) = q(s, a, g) − log Z q (g). For now, we shall assume that this Q-function is separate from the one defined in equation 18. Rearranging equation 20 , and setting ρ + (g) to be ρ + (s + ), we see the density ratio can be expressed as: Lemma 4.2 (Gradient of the noise-contrastive term in energy-based goal-reaching). Given the following definition for the logit of a NCE-like binary classifier, with ρ + (g) = ρ + (g): The gradient of the negative NCE term in the density ratio estimation approaches zero as k → ∞: As for the positive classification term in NCE equation 9, we can make a similar argument that ∇ θ log(1 + exp ∆ θ (s, a, s + , k)) k→∞ − −−− → 0 (see appendix B.2). We have: To optimize the above objective on arbitrary behaviour data, we have to consider the fact that we do not have complete access to the distribution of "positive samples" p + π (s + | s, a), as sampling directly from this distribution requires on-policy rollouts. Utilizing importance weights to learn from off-policy data while accounting for hindsight bias yields the following loss minimization instead: where w(s, a, s , g) contrasts the goals that will likely be met by the agent beyond a single step of dynamics p(s | s, a) in the future with other random goals that the agent has seen in the past: w(s, a, s , g) = exp Q(s, a, g) Pushing down the likelihood of the marginal −γ · a exp Q(s , a, g)/|A|

DERIVING HER REWARDS
For a goal-conditioned Q-function Q θ (s, a, g), besides optimizing a Bellman residual as a regular Q(s, a) function would do, it has an additional degree-of-freedom for the goal g which can be used to define an EBM that models the future-state distribution. In such an EBM, the Q-function is used as the negative energy defined in equation 21. Combining the first term in the f -divergence minimization part equation 18 and the single-step dynamics loss term in the EBM learning 24 gives us: The crucial observation here is, given that f * is a quadratic 19, and that there is a stop gradient sign on P π Q because it uses a target network, the loss above can be re-packaged into a single quadratic loss of Bellman residuals for a specific reward thanks to the property of the dynamics defined in 4: r(s, a, s , s + ) = r + β, s = s + r, s = s + See Appendix B.4 for a full derivation. Setting r = −1 and β = 1, we have arrived at the reward function of HER r HER (s, a, s , s + ). The remaining losses that this reward leaves out are the second term in f -divergence minimization part equation 18 and the second term in the EBM training equation 53, which we will analyze in the next section.

WHEN DOES BEHAVIOUR CLONING (BC) HELP?
We now proceed to answer the following question: when does BC help? Our idea is to identify the conditions for a BC-like loss to emerge in the remaining losses unaccounted by the HER reward: a loss term in 18 about pushing Q-values of the current policy down, and the multi-step dynamics term in EBM 54. We may argue that, by not pushing the Q-values of the current policy down, the HER agent becomes more exploratory; by not pushing up the Q-values of the discounted future-state distribution beyond a single step, the HER agent is encouraged to reach a goal sooner rather than later. Nevertheless, we shall see that combining those two remaining terms produces a BC-like term, which imitates the best actions based on how much an action moves the agent closer to the goal.
We start with the following property of Boltzmann policies π(a | s, g) ∝ exp Q(s, a, g) In equation 25, the Q-value of a particular action a is pushed up under the following condition: exp Q(s, a, g) Both denominators on the left and right sides are averaged over all possible behavioral goals, so their values should be roughly the same. Moreover, we approximate the average-exponential operation by using the max operation already computed in the backup operator (either exact (Mnih et al., 2015;Van Hasselt et al., 2016) or approximate (Lillicrap et al., 2015;Haarnoja et al., 2018)) and lower the threshold γ hdm (compared to γ) accordingly. After those changes, the indicator function that decides whether the value of an action a should be pushed up becomes: w(s, a, s , g) = 1(exp Q(s, a, g) − γ hdm · exp max a Q(s , a , g) < 0) Combining with the first term in 29, we arrive at a BC-like loss 12, but with an indicator weighting: Intuitively, this term imitates a particular action when the value functions believe that this action can move the agent closer to the goal by at least − log γ hdm steps. The idea of imitating the best actions is similar to self-imitation learning (SIL) (Oh et al., 2018;Vinyals et al., 2019), but our algorithm 1 operates in a (reward-free) goal-reaching setting, with the advantage function in SIL being replaced by the delta of reachability a particular action can produce in getting closer to the goal.
1: L = MSE(Q(s, a, s + ) − γ max a Q (s , a , s + ), r) r is a constant, default r = −1 2: L = L − β(1 − γ hdm ) · Q(s, a, s ) Push up the values for reaching next states 3: L BC = Q(s, a, s + ) − log A exp Q(s, ·, s + ) Behaviour Cloning like loss 4: L = L − β · 1(Q(s, a, s + ) − max a Q(s , a , s + ) < log γ hdm ) · L BC 5: minimize L, update the target networkQ 5 EXPERIMENTS (e) γhdm = 0.75. As we lower γhdm, the threshold − log γhdm gets higher and fewer actions get imitated, with the remaining imitated actions more concentrated around the goal. HDM uses Q-learning to account for the worst while imitating the best during the goal-reaching process.

SELF-SUPERVISED GOAL-REACHING SETUP
We consider the self-supervised goal-reaching setting for the environments described in GCSL (Ghosh et al., 2019). While the original HER (Andrychowicz et al., 2017) assumes that the agent has direct access to the ground truth binary reward metric (which is used when relabeling is performed), we do not make such an assumption as it can be unrealistic for real-world robot-learning (Lin et al., 2019). Instead, we simply use next-state relabeling to provide positive rewards. As seen in Eq equation 28, a positive reward is provided only when the relabeled hindsight goal is the immediate next state. The benefit of the next-state relabeling reward is that the training procedure is now completely self-supervised, and therefore provides a fair comparison to GCSL (Ghosh et al., 2019).

COMPARISONS AND ABLATIONS
As shown in Table 1  between an algorithm and GCSL. We see that only HER with (−1, 0) rewards and HDM consistently outperform GCSL, while HER + HBC performs worse than HER and sometimes GCSL as well.
is known to improve the robustness of learning (Haarnoja et al., 2018). HDM builds on top of HER with (−1, 0) rewards and adds a BC-like loss with a clipping condition equation 32 such that only the actions that move an agent closer to the goal get imitated (see Figure 6). Indeed, combining HER with HBC (which blindly imitates all actions in hindsight) produces worse results than not imitating at all and only resorting to value learning; HDM allows for better control over what to imitate.
The results in Table 1 and Figure 7 show that HDM achieves the strongest performance on all environments, while reducing variances in success rates. Interestingly, there is no consensus best baseline algorithm, with all five algorithms achieving good results in some environments and subpar performance in others. In Figure 10 of the appendix, we ablate the additional hyper-parameters introduced by HDM: γ hdm in equation 31 and the β term in equation 14. Intuitively, γ hdm controls the threshold that determines when an action is considered good enough for imitation, and β controls the trade-off between minimizing f -divergence and maximizing future goal likelihood in equation 14.
The ablation shows that HDM outperforms HER and GCSL across a variety of γ hdm and β values. In this section, we aim to better understand whether the (underwhelming) performance of hindsight BC had anything to do with our specific setting. We report an interesting metric that correlates with the performance of GCSL / HBC, which can be measured prior to training a policy: initial ag (achieved-goal) change ratio. We define the ag change ratio of π to be: the percentage of trajectories where the achieved goals in initial states s 0 are different from the achieved goals in final states s T under π. Most training signals are only created from ag changes, because they provide examples of how to rearrange an environment. We then define initial ag change ratio to be the ag change ratio of a random-acting policy π 0 . Using notation from 28, it can be computed as E s0···s T ∼π0 [−r HER (·, ·, s 0 , s T )].

WHY DOES HINDSIGHT BC
In Figure 8, we show the relationship between final success rates versus the initial ag (achieved-goal) change ratio, across all environments. The performance of GCSL seems to be upper-bounded by a linear relationship between the two. This makes intuitive sense: a BC-style objective starts off cloning the initially random trajectories, so if initial ag change ratio is low, the policy would not learn to rearrange ag, compounding to a low final performance. HER and HDM are able to surpass this upper ceiling likely because of the additional goal-likelihood term equation 14 besides imitation.
This finding suggests that in order to make goal-reaching easier, we should either modify the initial state distribution ρ 0 (s) such that ag can be easily changed through random exploration (Florensa et al., 2017) (if the policy is training from scratch), or initialize BC from some high-quality demonstrations where ag does change (Ding et al., 2019;Nair et al., 2018a;Lynch et al., 2019).

CONCLUSION
This work presents a unified goal-reaching objective that encompasses a family of goal-conditioned RL algorithms. Our derivation illustrates the connection between hindsight goal relabeling, divergence minimization, and energy-based models. It reveals that there is a largely unexplored design space: we could potentially use other convex functions in f -divergence minimization (Nowozin et al., 2016;Ghasemipour et al., 2020), and improve the optimization of the energy-based model (Du et al., 2020) by going beyond NCE (Grathwohl et al., 2020). The primary limitation of our framework is that it does not account for exploration. Eventually, we would like to incorporate empowerment (Klyubin et al., 2005;Sekar et al., 2020) Discounted future state distribution under policy µ ρ µ (s) State distribution (occupancy measure) visited by policy µ P π Q(s, a, g) Transition operator in (goal-conditioned) Bellman backup. P π Q(s, a, g) = E p(s |s,a)π(a |s ,g) [Q θ (s , a , g)]. f Derivative of function f ρ exp (s, a) State-action visitation distribution of the expert policy ρ µ (s, a) State-action visitation distribution of the policy µ. Note that ρ µ (s, a) = ρ µ (s)µ(a | s).
T (x) Function used in the variational bound of f -divergence. Also appears as T (s, a) or T (s, a, g) in the main text.
ρ + (g) The behaviour goal distribution assumed to be given apriori by the environment.
ρ π (s, a | g) The state-action visitation distribution of goal-conditioned policy π when conditioned on the behavioral goal g E(x) Energy function of an EBM: p θ (x) = exp(−E θ (x))/Z(θ).
The number of times noise samples are sampled more frequently than true data samples in NCE.

∆ θ
The logit of the positive sample classification loss in NCE.
r(s, a, s + ) The (learned) reward in goal-conditioned divergence minimization.
r(s, a, s , s + ) The (generalized) reward used in HER-style multi-goal RL.
r HER (s, a, s , s + ) The reward function used in HER. It equals 0 when s = s + and −1 when s = s + . Also denoted as r HER (·, ·, s , s + ).

C ABLATIONS AND HYPER-PARAMETERS
In this section, we include additional ablations and hyper-parameters. We first describe the goalreaching environments in more details in Figure 9. We use the following thresholds (for Euclidean norms) for determining success: [0.08, 0.08, 0.05, 0.05, 0.1], which are tight thresholds based on our visualizations of the environments. We use the same network architecture, sampling and optimization schedules for all the methods, as described in Table 2. As for γ HDM , we set it to be 0.85 in Four Rooms and Lunar Lander, 0.5 in Sawyer Push and Claw Manipulate, and 0.4 for Door Opening. Ablation on this hyper-parameter can be found in Figure 10. For next state relabeling ratio, we set the default to be 0.2, increase it to 0.5 in Lunar Lander, and 0.6 in Sawyer Push and Door Opening. For the soft-Q-learning (Schulman et al., 2017) + HER baseline, we set the temperature parameter to be 0.2, which we have found to empirically perform well.