# Formatting Instructions For NeurIPS 2020

Léonard Blier
Inria, Université Paris Saclay, FAIR Yann Ollivier
FAIR

#  Unbiased Methods for Multi-Goal RL

Léonard Blier
Inria, Université Paris Saclay, FAIR Yann Ollivier
FAIR

###### Abstract

In multi-goal reinforcement learning (RL) settings, the reward for each goal
is sparse, and located in a small neighborhood of the goal. In large
dimension, the probability of reaching a reward vanishes and the agent
receives little learning signal. Methods such as _Hindsight Experience Replay_
(HER) tackle this issue by also learning from realized but unplanned-for
goals. But HER is known to introduce bias (Plappert et al., 2018), and can
converge to low-return policies by overestimating chancy outcomes. First, we
vindicate HER by proving that it is actually unbiased in _deterministic_
environments, such as many optimal control settings. Next, for stochastic
environments in continuous spaces, we tackle sparse rewards by directly taking
the infinitely sparse reward limit. We fully formalize the problem of multi-
goal RL with infinitely sparse Dirac rewards at each goal. We introduce
unbiased deep $Q$-learning and actor-critic algorithms that can handle such
infinitely sparse rewards, and test them in toy environments.

Most standard _reinforcement learning_ (RL) methods fail when faced with very
sparse reward signals. Multi-task reinforcement learning attempts to solve
this problem by presenting agents with a diverse set of tasks and learn a
task-dependent policy in the hope that the agent could leverage knowledge from
some tasks on others (Jaderberg et al., 2016; Hausman et al., 2018; Nagabandi
et al., 2019). _Multi-goal_ reinforcement learning is a sub-field of multi-
task RL, where the different tasks consist in reaching particular _goals_ in
the environment.

_Universal Value Function Approximators_ (UVFA) (Schaul et al., 2015) extend
the classical Q-learning and Temporal Difference (TD) algorithms to the multi-
goal setting. It learns the goal-conditioned value-function $V^{\pi}(s,g)$ or
$Q$-function $Q^{\ast}(s,a,g)$ for every state-goal pair, with function
approximation, via a TD algorithm. Still, no learning occurs until a reward is
observed, and UVFA fails in many high dimensional environments, when the
probability of reaching the target goal is low and the agent almost never gets
any learning signal.

_Hindsight Experience Replay_ (HER) (Andrychowicz et al., 2017) is a possible
solution to this issue. It leverages information between goals via the
following principle: trajectories aiming at a goal $g$ but reaching a goal
$g^{\prime}$ can be used for learning exactly as if the trajectory had been
aiming at $g^{\prime}$ from start. This strategy has proved successful in
practice, but is known to be _biased_ (Manela & Biess, 2021; Lanka & Wu,
2018). In their request for research for robotic multi-goal environments,
Plappert et al. (2018) list the necessity for an unbiased version of HER, as
such bias can lead to low-return policies.

Our contributions are:

  * •

We show that in _deterministic_ environments, HER is actually unbiased
(Theorem 2). This case covers many standard control or robotic environments,
in which HER is known to perform well. This result strengthens HER
theoretically.

  * •

We show that sparse rewards in a multi-goal setting can be handled, counter-
intuitively, by dealing directly with the infinitely sparse reward limit: then
the sparse reward contribution can be computed algebraically instead of
sampled. The resulting Q-learning and actor-critic algorithms are unbiased
even in the stochastic case and handle multi-goal RL without having to observe
sparse rewards, although their variance is higher than HER. For this, we fully
formalize the problem of multi-goal RL with infinitely sparse rewards.

##  1 Multi-Goal Reinforcement Learning and Vanishing Rewards

#### Definition.

We define a multi-goal RL environment as a variant of a Markov decision
process (MDP) including a goal space. The MDP is defined by a state-space
$\mathcal{S}$, an action space $\mathcal{A}$ (discrete or continuous), a
discount factor $\gamma$, and a transition probability measure
$P(\operatorname{d}\\!{}s^{\prime}|s,a)$ which describes the probability that
the next state is $s^{\prime}$ after taking action $a$ in state $s$; for
stochastic continuous environments, this is generally a continuous probability
distribution over $s^{\prime}$, hence the notation
$\operatorname{d}\\!{}s^{\prime}$ which represents the probability to be in an
infinitesimal set $\operatorname{d}\\!{}s^{\prime}$ around $s^{\prime}$.

The goal space is a set $\mathcal{G}$ together with a function
$\varphi\colon\mathcal{S}\rightarrow\mathcal{G}$ defining for every state $s$
a corresponding goal $g=\varphi(s)$, which is the goal _achieved_ by state
$s$. The objective of the agent is to _reach_ a goal $g$. This is usually
formalized by defining a reward function $R_{\varepsilon}(s,g)$ as $1$ when a
given distance between the achieved goal $\varphi(s)$ and the target $g$ is
lower than a fixed value $\varepsilon$:
$R_{\varepsilon}(s,g)\mathrel{\mathop{:}}=\mathbbm{1}_{\|\varphi(s)-g\|\leqslant\varepsilon}$
for a fixed norm $\|.\|$ on $\mathcal{G}$. Thus, each goal $g\in\mathcal{G}$
defines an ordinary MDP with reward $R(s,g)$, and $Q$ and value functions
$Q^{\ast}_{\varepsilon}(s,a,g)$, $V^{\pi}_{\varepsilon}(s,g)$. A goal-
conditioned policy $\pi(a|s,g)$ is a probability distribution over the action
space $\mathcal{A}$ for every $(s,g)\in\mathcal{S}\times\mathcal{G}$.

We assume that, for a multi-goal policy $\pi(a|s,g)$, we are able to sample
trajectories in the environment by sampling a goal
$g\sim\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$, a starting state
$s_{0}\sim\rho_{0}(\operatorname{d}\\!{}s_{0}|g)$, and then by sampling at
step $t$ the action $a_{t}\sim\pi(a|s_{t},g)$ and the next state $s_{t+1}\sim
P(\operatorname{d}\\!{}s^{\prime}|s_{t},a_{t})$. We use the notation
$P^{\pi}(\operatorname{d}\\!{}s^{\prime}|s,g)\mathrel{\mathop{:}}=\int_{a}\pi(a|s,g)P(\operatorname{d}\\!{}s^{\prime}|s,a)$.

#### Universal Value Function Approximations.

UVFA (Schaul et al., 2015) allow for learning the value function
$V_{\varepsilon}^{\pi}(s,g)=\mathbb{E}_{a_{t}\sim\pi(.|s_{t},g),s_{t+1}\sim
P(.|s_{t},a_{t})}\left[\sum_{t\geqslant
0}\gamma^{t}R_{\varepsilon}(s_{t},g)|s_{0}=s\right]$ and the optimal
$Q$-function $Q^{\ast}_{\varepsilon}(s,a,g)$. Formally, $Q$-learning with UVFA
can be defined as standard $Q$-learning on the augmented state space
$\tilde{\mathcal{S}}\mathrel{\mathop{:}}=\mathcal{S}\times\mathcal{G}$, with
the transition distribution $\tilde{P}$ defined as follows: if action $a$ is
performed in state $(s,g)$, the next state $\tilde{s}^{\prime}$ is
$(s^{\prime},g)$ with $s^{\prime}\sim P(\operatorname{d}\\!{}s^{\prime}|s,a)$.
The augmented environment is not a multi-goal environment, and the policy
$\pi(a|s,g)=\pi(a|\tilde{s})$ becomes a standard non-goal-dependent policy in
$\tilde{\mathcal{S}}$. The UVFA Q-learning update corresponds to standard
parametric $Q$-learning on the augmented environment.

In practice, we consider a parametric function $Q_{\theta}(s,g)$, and we want
to learn $\theta$ such that $Q_{\theta}(s,g)$ approximates
$Q^{\ast}_{\varepsilon}(s,g)$. If $\theta$ is our current estimate and
$Q_{\mathrm{tar}}$ a target $Q$-function the Q-learning UVFA stochastic update
$\widehat{\delta\theta}_{\mathrm{UVFA}}$ is defined as follows. We consider an
exploration policy $\pi_{\mathrm{expl}}(a|s,g)$. When a transition
$(s,a,s^{\prime},g)$ is observed, with $a\sim\pi_{\mathrm{expl}}(.|s,g)$ and
$s^{\prime}\sim P(.|s,g)$, $\widehat{\delta\theta}_{\mathrm{UVFA}}$ is:

$\displaystyle\widehat{\delta\theta}_{\mathrm{UVFA}}(s,a,s^{\prime},g)$
$\displaystyle\mathrel{\mathop{:}}=-\frac{1}{2}\partial_{\theta}\left(Q_{\theta}(s,a,g)-R_{\varepsilon}(s,g)-\gamma\sup_{a^{\prime}}Q_{{\mathrm{tar}}}(s^{\prime},a^{\prime},g)\right)^{2}$
(1)

Then, we update $\theta$ with
$\theta\leftarrow\theta+\eta\widehat{\delta\theta}_{\mathrm{UVFA}}$, where
$\eta$ is the learning rate. The update
$\widehat{\delta\theta}_{\mathrm{UVFA}}$ is an unbiased estimate of
$\nicefrac{{1}}{{2}}\partial_{\theta}\|Q_{\theta}-T\cdot
Q_{{\mathrm{tar}}}\|^{2}$ where $T$ is the optimal Bellman operator, $T\cdot
Q(s,a,g)=R_{\varepsilon}(s,g)+\gamma\mathbb{E}_{s^{\prime}\sim
P(.|s,a)}\left[\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},g)\right]$, whose
unique fixed point is $Q^{\ast}_{\varepsilon}$. In particular, in the tabular
setting, this guarantees that a function $Q_{\infty}$ is a fixed point of UVFA
if and only if $T\cdot Q_{\infty}=Q_{\infty}$, which means
$Q_{\infty}=Q^{\ast}_{\varepsilon}$.

#### UVFA and vanishing rewards.

A major problem with multi-goal setups is the low probability with which each
specific goal $g$ is achieved, since rewards are observed only in a ball of
radius $\varepsilon$ around the goal. In a continuous noisy environment of
dimension $n$, reaching a goal up to precision $\varepsilon$ becomes almost
surely impossible when $\varepsilon\to 0$. With noise in dimension $n$, the
probability to exactly reach a predefined goal $g$ scales like
$O(\varepsilon^{n})$. In particular, the $Q$ and value functions vanish like
$O(\varepsilon^{n})$ when $\varepsilon$ is small. The situation is different
in continuous deterministic environments. If it is possible to reach a goal
exactly by selecting the right action, then the optimal $Q$-function
$Q^{\ast}_{\varepsilon}$ does not vanish, even if $\varepsilon=0$.

With the UVFA update, the probability to observe a reward
$\mathbbm{1}_{\|\varphi(s)-g\|\leqslant\varepsilon}$ vanishes like
$O(\varepsilon^{n})$ for continuous exploration policies. So even if
$Q^{\ast}_{\varepsilon}$ itself does not vanish, the learning algorithm for
$Q^{\ast}_{\varepsilon}$ may vanish. In practice, in an environment of
dimension $n=6$, UVFA is not able to learn anymore (experiment in Fig. 1).
This vanishing issue cannot be solved solely by an exploration strategy: the
issue is not the lack of diversity in visited states but rather the state
space is too large to be visited by an exploration trajectory (Andrychowicz et
al., 2017). Solving the issue of sparse rewards requires gathering some
information even from _failing trajectories_ which do not reach their initial
goal, namely, leveraging the structure of multi-goal environments by using
that every state achieves _some_ goal. This the case in HER but not UVFA.

In this work we study algorithms which leverage the multi-goal structure and
do not vanish even in the limit $\varepsilon\to 0$. We will focus on
_unbiased_ algorithms, which ensure that the true $Q$ or value function is
indeed a fixed point, by stochastic gradient arguments. UVFA is unbiased but
vanishes when $\varepsilon\to 0$. HER does not vanish, but is known to be
biased. In Section 2 we prove that HER is unbiased in deterministic
environments. Sections 3.2 and 3.4 present non-vanishing, unbiased algorithms
for stochastic environments; however, they are less efficient than HER in
deterministic environments.

##  2 Hindsight Experience Replay in Stochastic or Deterministic Environments

_Hindsight Experience Replay_ (HER) (Andrychowicz et al., 2017) is a way to
solve the issue of sparse rewards for multi-goal environments by leveraging
the mutual information between goals. The principle is the following:
trajectories aiming at a goal $g$ but reaching a goal $g^{\prime}$ can be used
for learning exactly as if the trajectory had been aiming for $g^{\prime}$
from start. Formally, when observing a trajectory
$\tau=(g,s_{0},a_{0},s_{1},a_{1},...)$, HER samples two random integers
$0\leqslant K\leqslant L$, and performs a $Q$-learning update at step $s_{K}$,
but for a re-sampled goal $g^{\prime}$ that is, with some probability, either
$g^{\prime}=g$ or $g^{\prime}=\varphi(s_{L})$, the goal achieved by the $L$-th
state in the trajectory:
$\widehat{\delta\theta}_{\mathrm{HER}}(\tau,K,L)\mathrel{\mathop{:}}=\frac{1}{2}\partial_{\theta}\left(Q_{\theta}(s_{K},a_{K},g^{\prime})-R_{\varepsilon}(s_{K},g^{\prime})-\gamma\sup_{a^{\prime}}Q_{{\mathrm{tar}}}(s_{K+1},a^{\prime},g^{\prime})\right)^{2}$.
In particular, the HER update does not vanish even for $\varepsilon=0$: with
nonzero probability, $K=L$ and $g^{\prime}=\varphi(s_{L})$, so that
$R_{\varepsilon}(s_{K},g^{\prime})=1$.

#### Bias of HER in stochastic environments.

HER is known to be biased in a general setting (Manela & Biess, 2021; Lanka &
Wu, 2018; Plappert et al., 2018), and this bias corresponds to a well-known
psychological bias (Fischhoff, 1975). Here is a simple way to design _counter-
examples_ environments which exhibit this HER bias. Consider a finite multi
goal environment and add a single action $a^{\ast}$ which, from any state $s$,
sends the agent to a uniform random state $s^{\prime}$ and then _freezes_ it,
which means the agent will always stay at $s^{\prime}$.

Both in theory and practice, HER will learn to always select the action
$a^{\ast}$ (third plot in Fig. 1). The intuition is the following: when the
agent acts with $a^{\ast}$ and reaches a random state $s^{\prime}$, HER
reinforces $a^{\ast}$ as a good way to reach $s^{\prime}$ from $s$, while this
was purely random. Formally, the following statement (proof in Appendix B.2)
shows that HER will overestimate the value of action $a^{\ast}$. We say that
$Q_{\infty}$ is a _fixed point_ of HER if
$\mathbb{E}_{\tau,K,L}\left[\widehat{\delta\theta}_{\mathrm{HER}}(\tau,K,L)\right]=0$
when $Q_{\theta}=Q_{\mathrm{tar}}=Q_{\infty}$.

###### Theorem 1.

Let $\mathcal{M}$ be any finite multi-goal environment, and
$\tilde{\mathcal{M}}$ the modified environment with the _freeze_ action
$a^{\ast}$. Then $\tilde{\mathcal{M}}$ is a _counter-example_ to HER, which is
biased in this environment. Namely, if $Q_{\infty}$ is a fixed point of HER
for $\tilde{\mathcal{M}}$, then for every _unfrozen_ state $s$ and goal $g$,
$Q_{\infty}$ will _overestimate_ the value of $a^{\ast}$:
$Q_{\infty}(s,a^{\ast},g)>Q^{\ast}(s,a^{\ast},g)$ where $Q^{\ast}$ is the true
value function.

Generally, HER is overestimating chancy outcomes, by estimating that any
action (even random) that led to some goal was a good way to reach that goal.
This is clear in the example of the freeze-after-random-jump actions in
Theorem 1. Thus, HER has no reason to learn reliably in a stochastic
environment. Other hindsight methods such as (Rauber et al., 2019) experience
a similar bias.

#### HER is unbiased in deterministic environments.

Despite its bias, HER is efficient in practice, especially in continuous
control environments. We vindicate HER theoretically by showing that HER is
unbiased in _deterministic_ environments. We say that an environment is
_deterministic_ is the next state $s_{t+1}$ is uniquely determined by the
current state $s_{t}$ and an action $a_{t}$. This covers many usual
environments such as robotic environments.

###### Theorem 2.

In a deterministic multi-goal environment such that every target state is
reachable from any starting state, HER is an unbiased Q-learning method.
Namely, there is a Euclidean norm $\|.\|_{\mathrm{HER}}$ such that if
$Q_{\theta}$ is the current estimate of $Q^{\ast}$, the HER update
$\widehat{\delta\theta_{\text{HER}}}$ is an unbiased stochastic estimate of
the gradient step between $Q_{\theta}$ and the target function
$TQ_{\mathrm{tar}}$:
$\mathbb{E}\left[\widehat{\delta\theta}_{\text{HER}}\right]=\nicefrac{{1}}{{2}}\partial_{\theta}\|Q_{\theta}-TQ_{\mathrm{tar}}\|_{\mathrm{HER}}^{2}$.
In particular, the true $Q$-function $Q^{\ast}$ is a fixed point of HER in
expectation: if $Q_{\theta}$ and $Q_{\mathrm{tar}}$ are equal to $Q^{\ast}$
then $\mathbb{E}\left[\widehat{\delta\theta}_{\text{HER}}\right]=0$.

The proof and a more detailed statement are given in Appendix B.1. This result
vindicates HER for deterministic environments: HER leverages the structure of
multi-goal environments, is not vanishing when the rewards are sparse, and is
mathematically well-grounded.

##  3 Multi-Goal RL via Infinitely Sparse Rewards

###  3.1 Taking the Infinitely Sparse Reward Limit

In Section 2, we saw that while HER is well-founded in deterministic
environments, it is biased in the stochastic case and can learn low-return
policies (Figure 1). We now introduce unbiased methods for multi-goal RL in
the general setting, including stochastic environments.

In continuous state spaces, the reward is usually defined as
$R_{\varepsilon}(s,g)=\mathbbm{1}_{\|\varphi(s)-g\|\leqslant\varepsilon}$.
When $\varepsilon\rightarrow 0$, the probability of reaching the reward with a
stochastic policy goes to $0$, and for any stochastic policy, the value
function $V^{\pi}_{\varepsilon}(s,g)$ converges to $0$ as well. To avoid this
vanishing issue, we need a scaling factor, and consider the reward
$\frac{1}{\lambda(\varepsilon)}R_{\varepsilon}(s,g)$, with
$\lambda(\varepsilon)$ the volume of the ball of size $\varepsilon$ in goal
space. When $\varepsilon\rightarrow 0$, this rescaled reward _converges_ to
the _Dirac reward_ :

$R(s,\operatorname{d}\\!{}g)\mathrel{\mathop{:}}=\delta_{\varphi(s)}(\operatorname{d}\\!{}g),$
(2)

where $\delta_{x}$ is the Dirac measure at $x$. Intuitively, the Dirac reward
$R(s,\operatorname{d}\\!{}g)$ is infinite if the goal is reached
($\varphi(s)=g$) and $0$ elsewhere. Formally, the reward is not a function but
a _measure_ on the goal space $\mathcal{G}$ parametrized by the state $s$.

However, even after such a scaling, the UVFA update still vanishes with high
probability for small $\varepsilon$ (this just scales things by
$1/\lambda(\varepsilon)$). We will build algorithms that work directly in the
limit $\varepsilon=0$: replacing the sparse reward $R_{\varepsilon}(s,g)$ by
the _infinitely sparse_ reward
$R(s,\operatorname{d}\\!{}g)=\delta_{\varphi(s)}(\operatorname{d}\\!{}g)$ will
allow us to leverage the Dirac structure to remove the vanishing rewards
issue.

#### Computing the exact contribution of sparse rewards.

We now explain how to leverage the multi-goal sparse reward structure. The key
idea is that, with $\varepsilon=0$, the contribution of the reward term in the
Bellman equation can be computed exactly in expectation. Infinitely sparse
rewards can be treated algebraically. This derivation is informal; the formal
proof is in Appendix C.2.

Let us start with the expectation of the UVFA update (1) with $\varepsilon>0$
and rewards rescaled by $1/\lambda(\varepsilon)$:

$\displaystyle\delta\theta_{\mathrm{UVFA}}=\mathbb{E}_{s,a,s^{\prime},g}\left[\widehat{\delta\theta}_{\mathrm{UVFA}}(s,a,s^{\prime},g)\right]$
$\displaystyle=-\frac{1}{2}\partial_{\theta}\mathbb{E}_{{s,a,g,s^{\prime}}}\left[\left(Q_{\theta}(s,a,g)-\frac{1}{\lambda(\varepsilon)}R_{\varepsilon}(s,g)-\gamma\max_{a^{\prime}}Q_{{\mathrm{tar}}}(s^{\prime},a^{\prime},g)\right)^{2}\right]$
$\displaystyle=\mathbb{E}_{{s,a,g}}\left[\partial_{\theta}Q_{\theta}(s,a,g)\frac{1}{\lambda(\varepsilon)}R_{\varepsilon}(s,g)\right]-\mathbb{E}_{{s,a,g,s^{\prime}}}\left[\partial_{\theta}Q_{\theta}(s,a,g)\left(Q_{\theta}(s,a,g)-\gamma\max_{a^{\prime}}Q_{{\mathrm{tar}}}(s^{\prime},a^{\prime},g)\right)\right].$

This update cannot be used for small $\varepsilon$, because
$R_{\varepsilon}(s,g)$ is $0$ most of the time, even though the expectation is
nonzero and a huge $1/\lambda(\varepsilon)$ reward is observed with low
probability.

But when $\varepsilon\to 0$, the rescaled reward
$\frac{1}{\lambda(\varepsilon)}R_{\varepsilon}(s,g)$ converges to the Dirac
reward $\delta_{\varphi(s)}$. Therefore, we can rewrite this first term as

$\displaystyle\frac{1}{\lambda(\varepsilon)}\mathbb{E}_{{s,a,g}}\left[\partial_{\theta}Q_{\theta}(s,a,g)R_{\varepsilon}(s,g)\right]$
$\displaystyle\rightarrow_{\varepsilon\rightarrow
0}\mathbb{E}_{{s,a,g}}\left[\partial_{\theta}Q_{\theta}(s,a,g)\delta_{\varphi(s)}(\operatorname{d}\\!{}g)\right]$
$\displaystyle=\mathbb{E}_{s,a}\left[\partial_{\theta}Q_{\theta}(s,a,\varphi(s))\right].$

In this expression, sparse reward issues are avoided, just by taking the goal
$g=\varphi(s)$ associated with the currently visited state $s$. Instead of
waiting to reach a goal to update the $Q$-function, this updates the
$Q$-function for the currently realized goal.

The resulting algorithm, $\delta$-DQN, is described in Theorem 4 and Algorithm
1. The proper mathematical treatment (below and in the Appendix) of the Dirac
limit shows that this actually estimates, not $Q$ itself, but the _density_
$q(s,a,g)$ of the distribution of realized goals with respect to the goal
sampling distribution $\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$ of the
environment. This density $q$ can be used to rank actions (indeed, the scaling
by $\rho_{\mathcal{G}}$ between $q$ and $Q$ only depends on the goal $g$, so
for a fixed goal, states and actions are ranked the same way). In general,
working with probability densities is the only way that makes sense in the
presence of noise, as the probability to exactly reach a goal will be $0$.

A similar treatment holds for policy gradient (Sections 3.3–3.4).

###  3.2 Unbiased Multi-Goal Q-learning with Infinitely Sparse Rewards

Our goal here is to formally define multi-goal $Q$-learning with infinitely
sparse rewards. In general, the probability of reaching any goal _exactly_ is
$0$: instead we will learn the probability _distribution_ of the goals reached
by a policy, and compute the probability to reach each infinitesimal element
$\operatorname{d}\\!{}g$ in goal space. This is done by treating everything as
measures over $\mathcal{G}$: the reward
$\delta_{\varphi(s)}(\operatorname{d}\\!{}g)$ is a measure, and the value
functions $V^{\pi}(s,\operatorname{d}\\!{}g)$ or optimal action-value function
$Q^{\ast}(s,a,\operatorname{d}\\!{}g)$ are measures on $\mathcal{G}$ as well.
In the following, we define these objects in detail, and show how to learn
them in practice.

First, we define an _optimal Bellman operator_ $T$ on _action-value measures_
, and the optimal action-value measure $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$.
Then, we derive $\delta$-DQN, a deep Q-learning algorithm with infinitely
sparse rewards for multi-goal RL.

#### Optimal Bellman equation and optimal Q-function.

We first define $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$, the _optimal action-
value measure_ , the mathematical object corresponding to the usual optimal
$Q$-function $Q^{\ast}$ but infinitely sparse rewards. The following theorem
defines the optimal Bellman operator for action-value measures, and
$Q^{\ast}(s,a,\operatorname{d}\\!{}g)$ as its fixed point. It is formallly
stated in Appendix C.1.

###### Definition-Theorem 3.

Let $Q(s,a,\operatorname{d}\\!{}g)$ a measure on $\mathcal{G}$ parametrized by
$s,a\in\mathcal{S}\times\mathcal{A}$. We define the optimal Bellman operator
$T$ which sends $Q$ to $T\cdot Q$ with

$(T\cdot
Q)(s,a,\operatorname{d}\\!{}g)\mathrel{\mathop{:}}=\delta_{\varphi(s)}(\operatorname{d}\\!{}g)+\gamma\,\mathbb{E}_{s^{\prime}\sim
P(\operatorname{d}\\!{}s^{\prime}|s,a)}\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},\operatorname{d}\\!{}g)$
(3)

where $\delta_{\varphi(s)}$ is the Dirac measure at
$\varphi(s)\in\mathcal{G}$. We define the _optimal action-value measure_
$Q^{\ast}$ as follows. Set
$Q_{0}(s,a,\operatorname{d}\\!{}g)\mathrel{\mathop{:}}=0$, and
$Q_{n+1}\mathrel{\mathop{:}}=TQ_{n}$. Then $Q_{n}(s,a,\operatorname{d}\\!{}g)$
converges to some $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$. Moreover, this
$Q^{\ast}(s,a,\operatorname{d}\\!{}g)$ solves the fixed point equation
$TQ^{\ast}=Q^{\ast}$.

####  $Q$-learning with function approximations, with infinitely sparse
rewards.

From the fixed point equation for $Q^{\ast}$, we would like to learn a model
of $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$ with function approximation. We will
represent measures over goals via their _density_ with respect to the goal
sampling function $\rho_{\mathcal{G}}$ of the environment. Namely, we will
approximate $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$ by a model
$Q_{\theta}(s,a,\operatorname{d}\\!{}g)=q_{\theta}(s,a,g)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
where $q_{\theta}(s,a,g)$ is an ordinary function, and learn $q_{\theta}$.
Hence, $q_{\theta}$ may be approximated by any parametric model, such as a
neural network.

The following theorem properly defines an unbiased stochastic
$\delta\text{-}\mathrm{DQN}$ update with infinitely sparse rewards for the
density $q_{\theta}(s,a,g)$:

###### Theorem 4.

Let
$Q_{\theta}(s,a,\operatorname{d}\\!{}g)=q_{\theta}(s,a,g)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
be a current estimate of $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$. Let likewise
$Q_{\mathrm{tar}}(s,a,\operatorname{d}\\!{}g)=q_{\mathrm{tar}}(s,a,g)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
be a target $Q$-function, and consider the following update to bring
$Q_{\theta}$ closer to $TQ_{\mathrm{tar}}$ with $T$ the optimal Bellman
operator.

Let $(s,a,s^{\prime})$ be a sample of the environment such that
$s^{\prime}\sim P(s^{\prime}|s,a)$ and $g\sim\rho_{\mathcal{G}}$ is sampled
independently. Let
$\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}(s,a,s^{\prime},g)$ be

$\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}(s,a,s^{\prime},g)\mathrel{\mathop{:}}=\partial_{\theta}q_{\theta}(s,a,\varphi(s))+\partial_{\theta}q_{\theta}(s,a,g)\left(\gamma\max_{a^{\prime}}q_{\mathrm{tar}}(s^{\prime},a^{\prime},g)-q_{\theta}(s,a,g)\right)$
(4)

Then $\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}$ is an unbiased
estimate of the Bellman error:
$\mathbb{E}\left[\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}\right]=\frac{1}{2}\partial_{\theta}\|Q_{\theta}-TQ_{\mathrm{tar}}\|^{2}$,
where the Euclidean norm $\left\lVert\cdot\right\rVert$ on measures is defined
in Theorem 11 (Appendix C.2).

In particular, the true optimal state-action measure $Q^{\ast}$ is a fixed
point of this update: if $Q_{\theta}=Q_{\mathrm{tar}}=Q^{\ast}$ then
$\mathbb{E}\left[\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}\right]=0$.

This update leads to $\delta$-DQN (Algorithm 1, which corresponds to standard
DQN with infinitely sparse rewards. For continuous actions, $\delta$-DQN can
be modified similarly to DDPG (Lillicrap et al., 2016).

#### Example: the tabular case.

The tabular case highlights the difference between UVFA and
$\delta\text{-}\mathrm{DQN}$. When a transition $(s,a,s^{\prime},g)$ is
observed, the UVFA update is:

$Q(s,a,g)\leftarrow
Q(s,a,g)+\eta\left(\mathbbm{1}_{\varphi(s)=g}+\gamma\max_{a^{\prime}}Q(s^{\prime},a^{\prime},g)-Q(s,a,g)\right)$
(5)

where $\eta$ is the learning rate. The only modified value is $Q(s,a,g)$.

With $\delta\text{-}\mathrm{DQN}$, we learn the density $q$ of
$Q(s,a,\operatorname{d}\\!{}g)$ with respect to $\rho_{\mathcal{G}}$. Assume
that $\rho_{\mathcal{G}}(g)$ is the uniform measure over the finite goal space
$\mathcal{G}$. Then we learn $q(s,a,g)=|\mathcal{G}|\times Q(s,a,g)$. For a
tabular model, the $\delta$-DQN update in Equation (87) is

$\displaystyle q(s,a,\varphi(s))$ $\displaystyle\leftarrow
q(s,a,\varphi(s))+\eta$ (6) $\displaystyle q(s,a,g)$ $\displaystyle\leftarrow
q(s,a,g)+\eta\left(\gamma\max_{a^{\prime}}q(s^{\prime},a^{\prime},g)-q(s,a,g)\right).$
(7)

Here two values are updated: in addition to $(s,a,g)$, the trajectory visiting
$s$ is also used to update the value for the goal $\varphi(s)$. The first part
always increases $q$ at the goal $\varphi(s)$ achieved by $s$; the second part
at $(s,a,g)$ has no reward contribution, and decreases $q$ at $(s,a,g)$ by a
factor $(1-\eta)$ while propagating the value from $s^{\prime}$. In
expectation, the decrease at $(s,a,g)$ compensates the increase at
$(s,a,\varphi(s))$: this compensation is exact when $q$ is the exact solution.

As a comparison, the tabular HER update works as follows: when observing a
trajectory $(g,s_{0},a_{0},s_{1},...)$, a transition
$(s,a,s^{\prime},g)=(s_{K},a_{K},s_{K+1},g)$ for some $K\geqslant 0$ is
selected; then HER samples $L\geqslant K$, defines
$g^{\prime}\mathrel{\mathop{:}}=\varphi(s_{L})$ as the re-sampled goal, then
applies the UVFA update (5) but with $(s,a,s^{\prime},g^{\prime})$ instead of
$(s,a,s^{\prime},g)$. When $L=K$, the goal sampled by HER is
$g^{\prime}=\varphi(s)$: this is somewhat similar to
$\delta\text{-}\mathrm{DQN}$, except $\delta\text{-}\mathrm{DQN}$ resamples an
independant goal instead of $g^{\prime}$ for the second term instead. Despite
this similarity, HER is biased in stochastic environments and can converge to
a low-return policy, while $\delta\text{-}\mathrm{DQN}$ is unbiased.

Algorithm 1 $\delta$-DQN

Input: Randomly initialized model $q_{\theta}(s,a,g)$; $\varphi$; exploration
policy $\pi_{\mathrm{expl}}(a|s,g)$; goal function $\varphi$; memory buffer
$\mathtt{TransitionMemory}$, $T$ the maximum trajectory length

repeat

for $K$ trajectories do

Get a goal $g$ and an initial state $s_{0}$

for $0\leqslant t\leqslant T$ steps do do

Sample $a_{t}\sim\pi_{\text{expl}}(.|s_{t},g)$, execute $a_{t}$ and observe
$s_{t+1}$

Store in the transition memory the transition
$\mathtt{TransitionMemory}\leftarrow(s_{t},a_{t},s_{t+1})$

end for

for $L$ gradient steps do

Sample $(s,a,s^{\prime})\sim\mathtt{TransitionMemory}$ and
$g\sim\rho_{\mathcal{G}}$

$\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}\mathrel{\mathop{:}}=\partial_{\theta}q_{\theta}(s,a,\varphi(s))+\partial_{\theta}q_{\theta}(s,a,g)\left(\gamma\max_{a^{\prime}}q_{\theta}(s^{\prime},a^{\prime},g)-q_{\theta}(s,a,g)\right)$.

Stochastic gradient step:
$\theta\leftarrow\theta+\eta\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}$.

end for

end for

until end of learning

###  3.3 Unbiased Policy Evaluation with Infinitely Sparse Rewards

Similarly to $\delta\text{-}\mathrm{DQN}$, there exists an actor-critic
algorithm for multi-goal environments with infinitely sparse rewards. We start
with policy evaluation, then derive the policy gradient algorithm.

Learning the value function $V^{\pi}(s,\operatorname{d}\\!{}g)$ directly
without bias poses technical issues due to the double dependency of
$V^{\pi}(s,\operatorname{d}\\!{}g)$ on $g$ (first via the location of the
reward, second, via the goal-dependent policy $\pi(.|.,g)$). This is discussed
in Appendix D.2.

Instead, we learn a richer object,
$M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$, the value function of $s$ if
the reward is a Dirac at $g^{\prime}$ but the agent follows the policy
$\pi(a|s,g)$ for goal $g$. This is defined as the measure over goals

$M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})\mathrel{\mathop{:}}=\mathbb{E}_{a_{t}\sim\pi(.|s_{t},g),s_{t+1}\sim
P(.|s_{t},a_{t})}\left[\sum_{t\geqslant
0}\gamma^{t}\delta_{\varphi(s_{t})}(\operatorname{d}\\!{}g^{\prime})|s_{0}=s\right]$
(8)

$M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$ represents the _successor goal
measure_ , and is related to the successor state measure (Blier et al., 2021).
Compared to $V^{\pi}(s,\operatorname{d}\\!{}g)$,
$M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$ splits the two effects of the
goal $g$ in two variables $g$ and $g^{\prime}$.
$V^{\pi}(s,\operatorname{d}\\!{}g)$ can be derived from
$M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$ as
$V^{\pi}(s,\operatorname{d}\\!{}g)=M^{\pi}(s,g,\operatorname{d}\\!{}g)$ (see
Appendix E.2). $M^{\pi}$ is a fixed point of the Bellman operator $T^{\pi}$
defined as:

$(T^{\pi}\cdot
M)(s,g,\operatorname{d}\\!{}g^{\prime})\mathrel{\mathop{:}}=\delta_{\varphi(s)}(\operatorname{d}\\!{}g^{\prime})+\gamma\mathbb{E}_{a\sim\pi(a|s,g),s^{\prime}\sim
P(\operatorname{d}\\!{}s^{\prime}|s,a)}\left[M(s^{\prime},g,\operatorname{d}\\!{}g^{\prime})\right]$
(9)

A rigorous proof of the existence of $M^{\pi}$ as well as its fixed point
Bellman equation is given in Theorem 13 in the supplementary. Similarly to the
$\delta\text{-}\mathrm{DQN}$ update obtained in Theorem 4, we can now derive
an unbiased $\delta\text{-}\mathrm{TD}$ update for $M^{\pi}$, leveraging the
structure of the Dirac reward and removing the issue of vanishing rewards. As
for $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$, because
$M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$ is a measure, we learn a model
$m_{\theta}(s,g,g^{\prime})$ of its density with respect to
$\rho_{\mathcal{G}}$, namely,
$M_{\theta}(s,g,\operatorname{d}\\!{}g^{\prime})=m_{\theta}(s,g,g^{\prime})\rho_{\mathcal{G}}(\operatorname{d}\\!{}g^{\prime})$.

###### Theorem 5.

Let
$M_{\theta}(s,g,\operatorname{d}\\!{}g^{\prime})=m_{\theta}(s,g,g^{\prime})\rho_{\mathcal{G}}(\operatorname{d}\\!{}g^{\prime})$
be a current estimate of $M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$. Let
likewise
$M_{\mathrm{tar}}(s,g,\operatorname{d}\\!{}g^{\prime})=m_{\mathrm{tar}}(s,g,g^{\prime})\rho(\operatorname{d}\\!{}g^{\prime})$
be a target $M$, and consider the following update to bring $Q_{\theta}$
closer to $T^{\pi}Q_{\mathrm{tar}}$ with $T^{\pi}$ the Bellman operator.

Let $(s,a,s^{\prime},g,g^{\prime})$ be samples of the environment such that
$a\sim\pi(a|s,g)$, $s^{\prime}\sim P(s^{\prime}|s,a)$ and
$g^{\prime}\sim\rho_{\mathcal{G}}$ is a goal sampled independently. Let
$\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}}$ be

$\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}}(s,a,s^{\prime},g,g^{\prime})\mathrel{\mathop{:}}=\partial_{\theta}m_{\theta}(s,g,\varphi(s))+\partial_{\theta}m_{\theta}(s,g,g^{\prime})\left(\gamma
m_{\mathrm{tar}}(s^{\prime},g,g^{\prime})-m_{\theta}(s,g,g^{\prime})\right)$
(10)

Then $\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}}$ is an unbiased
estimate of the Bellman error:
$\mathbb{E}_{s,a,s^{\prime},g,g^{\prime}}\left[\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}}(s,a,s^{\prime},g,g^{\prime})\right]=\frac{1}{2}\partial_{\theta}\|M_{\theta}-T^{\pi}M_{\mathrm{tar}}\|^{2}$,
where the norm $\left\lVert\cdot\right\rVert$ on measures is defined in
Theorem 13 (Appendix D.2).

In particular, the true successor goal measure
$M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$ is a fixed point of this
udpate: if $M_{\theta}=M_{\mathrm{tar}}=M^{\pi}$, then
$\mathbb{E}\left[\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}}\right]=0$.

Similarly to update $\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}$, the
update $\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}}$ has two parts: the
first part $\partial_{\theta}m_{\theta}(s,g,\varphi(s))$ represents the reward
update for the goal achieved in the current state $s$, and removes the
vanishing reward issue. The second part propagates the rewards along
transitions.

We can also define a horizon-$n$ $\delta\text{-}\mathrm{TD}(n)$ update if we
have access to longer sub-trajectories $\tau=(g,s_{0},a_{0},s_{1},...)$. The
update at a state $s_{k}$ in the trajectory is (Appendix, Theorem 13)

$\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}(n)}(\tau,k,g^{\prime})\mathrel{\mathop{:}}=\sum_{l=0}^{n-1}\gamma^{l}\partial_{\theta}m_{\theta}(s_{k},g,\varphi(s_{k+l}))+\partial_{\theta}m_{\theta}(s_{k},g,g^{\prime})\left(\gamma^{n}m_{\theta}(s_{k+n},g,g^{\prime})-m_{\theta}(s_{k},g,g^{\prime})\right)$
(11)

where $g^{\prime}\sim\rho_{\mathcal{G}}$ is sampled independently. The first
part increases the value estimate at state $s_{k}$ for every of the $n$ goals
$\varphi(s_{k}),...,\varphi(s_{k+n-1})$ achieved in the next $n$ steps: this
corresponds to the $n$-step return with Dirac rewards. The second part
propagates the value along transitions. This is similar to HER in that future
goals achieved along the trajectory are explicitly used, and could thus
improve sample efficiency. However, computational complexity is an issue. In
non-multi-goal environments, algorithms such as PPO (Schulman et al., 2017)
compute the TD($n$) update at every step of the trajectory. This is computable
with $O(n)$ forward passes through the value model $v_{\theta}$, because it
only requires to compute $v_{\theta}(s_{0}),\ldots,v_{\theta}(s_{n})$. Here we
have to compute $m_{\theta}(s_{k},g,\varphi(s_{k+l}))$ for every $k$ and $l$,
leading to an $O(n^{2})$ complexity (though this could potentially be sub-
sampled as in HER). This makes it slow in practice, and
$\delta\text{-}\mathrm{TD}(n)$ was not tested experimentally here.

###  3.4 Multi-Goal Policy Gradient

We now derive the actor-critic algorithm. The classical approach with reward
$R_{\varepsilon}$ for $\varepsilon>0$ considers the expected return
$J_{\varepsilon}(\pi)=\mathbb{E}_{g\sim p_{\mathcal{G}},s_{0}\sim
p_{0}(.|g)}\left[\sum_{t\geqslant
0}\gamma^{t}R_{\varepsilon}(s_{t},g)|s_{0}=s\right]=\int_{s_{0},g}V^{\pi}_{\varepsilon}(s,g)\,\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)\rho_{0}(\operatorname{d}\\!{}s_{0}|g)$
with a sampled goal $g\sim\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$ and
sampled initial state $s_{0}\sim\rho_{0}(\operatorname{d}\\!{}s_{0}|g)$, and
subsequent actions sampled from the policy for $g$. As in
$\delta\text{-}\mathrm{DQN}$, we want to derive an algorithm solving the
vanishing reward issue directly for $\varepsilon=0$. We first show that the
limit makes sense, then derive the corresponding update in (13) below.

###### Theorem 6.

Under _continuity assumptions_ (Assumption 1 in the Appendix), there is a
function $J(\pi)$ such that, for every parametric policy
$\pi_{\theta}(a|s,g)$:

$\displaystyle\frac{1}{\lambda(\varepsilon)}J_{\varepsilon}(\pi_{\theta})\rightarrow_{\varepsilon\rightarrow
0}J(\pi_{\theta})\quad\leavevmode\nobreak\ \quad\text{ and
}\quad\leavevmode\nobreak\
\quad\frac{1}{\lambda(\varepsilon)}\partial_{\theta}J_{\varepsilon}(\pi_{\theta})\rightarrow_{\varepsilon\rightarrow
0}\partial_{\theta}J(\pi_{\theta})$ (12)

where $\lambda(\varepsilon)$ is the volume of a ball of size $\varepsilon$ in
goal space. We call $J(\pi)$ the expected return with infinitely sparse
rewards. Moreover,
$J(\pi)\mathrel{\mathop{:}}=\int_{s_{0},g}V^{\pi}(s_{0},\operatorname{d}\\!{}g)\,p_{\mathcal{G}}(g)\,\rho_{0}(\operatorname{d}\\!{}s_{0}|g)$
where $p_{\mathcal{G}}(g)$ is the density of
$\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$ with respect to Lebesgue measure
on goals.

We now derive an estimate of $\partial_{\theta}J(\pi_{\theta})$ for a
parametric policy $\pi_{\theta}(a|s,g)$. We assume access to transition
samples $(s,a,s^{\prime},g)$ such that $a\sim\pi(.|s,g)$, $s^{\prime}\sim
P(\operatorname{d}\\!{}s^{\prime}|s,a)$ and $s$ is sampled from the goal-
dependant _discounted visitation frequencies_
$\nu^{\pi}(\operatorname{d}\\!{}s|g)=(1-\gamma)\sum_{t\geqslant
0}\gamma^{t}\rho_{0}(\operatorname{d}\\!{}s_{0}|g)(P^{\pi})^{t}(\operatorname{d}\\!{}s|s_{0},g)$:
namely, states $s$ on a trajectory sampled from $\pi$ with goal $g$.

We can define the actor critic update with infinitely sparse rewards by using
the model $m(s,g,g)$ as an estimate of the values, and applying the ordinary
policy gradient theorem (Sutton & Barto, 2018) on the extended space
$\mathcal{S}\times\mathcal{G}$ to include the goals (see Appendix E.4). This
leads to

$\widehat{\delta\theta}_{\delta\text{-}\mathrm{AC}}(s,a,s^{\prime},g)\mathrel{\mathop{:}}=\partial_{\theta}\log\pi_{\theta}(a|s,g)\left(\gamma
m_{\theta_{M}}(s^{\prime},g,g)-m_{\theta_{M}}(s,g,g)\right)$ (13)

where $m_{\theta_{M}}(s,g,g^{\prime})$ is the model of the value density
learned in Section 3.3. This is justified by the following statement, which is
an informal version of Theorem 20 in Appendix E.4: namely, if the value
function model $m_{\theta_{M}}$ is correct, then this actor-critic update is
an unbiased estimate of $\partial_{\theta}J(\pi_{\theta})$.

###### Informal Theorem 7.

If $m_{\theta_{M}}(s,g,g)\lambda(\operatorname{d}\\!{}g)$ approximates
$V^{\pi}(s,\operatorname{d}\\!{}g)$ as a measure, then
$\mathbb{E}_{s,a,s^{\prime},g}\left[\widehat{\delta\theta}_{\delta\text{-}\mathrm{AC}}(s,a,s^{\prime},g)\right]$
approximates $\partial_{\theta}J(\pi_{\theta})$.

This update, together with the one for $m$ in Theorem 5, make up the
$\delta$-Actor-Critic algorithm (Algorithm 2). We can similarly define a PPO
algorithm (Appendix A), used in the experiments.

Algorithm 2 One-step $\delta$-Actor-Critic

Input: Model $m_{\theta_{M}}(s,g)$; policy $\pi_{\theta}$; goal function
$\varphi$; $T$ the maximum trajectory length

Get a goal $g$ and an initial state $s_{0}$ from the environment

for $0\leqslant t\leqslant T$ steps do

Sample $a_{t}\sim\pi(a|s_{t},g)$

Execute action $a_{t}$ and observe the next state $s_{t+1}$

Sample an independent goal
$g^{\prime}\sim\rho_{\mathcal{G}}(\operatorname{d}\\!{}g^{\prime})$

$\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}}\mathrel{\mathop{:}}=\partial_{\theta}m_{\theta_{M}}(s_{t},g,\varphi(s_{t}))+\partial_{\theta}m_{\theta_{M}}(s_{t},g,g^{\prime})\left(\gamma
m_{\theta_{M}}(s_{t+1},g,g^{\prime})-m_{\theta_{M}}(s_{t},g,g^{\prime})\right)$

$\widehat{\delta\theta}_{\delta\text{-}\mathrm{AC}}=\gamma^{t}\times\partial_{\theta}\log\pi_{\theta_{\pi}}(a_{t}|s_{t},g)\left(\gamma
m(s_{t+1},g,g)-m(s_{t},g,g)\right)$

$\theta_{M}\leftarrow\theta_{M}+\eta_{M}\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}}$

$\theta_{\pi}\leftarrow\theta_{\pi}+\eta_{\pi}\widehat{\delta\theta}_{\delta\text{-}\mathrm{AC}}$

end for

##  4 Experiments

#### The Torus environment.

We first define the Torus$(n)$ environment, which is a continuous version of
the _flipping coin_ environment introduced in (Andrychowicz et al., 2017). The
state space is the $n$-th dimensional torus, represented as
$\mathcal{S}=[0,1)^{n}$, and can be obtained from the $n$-dimensional
hypercube by gluing the opposite faces together. The action space is
$\mathcal{A}=\\{1,\ldots,n\\}\times\\{-\alpha,\alpha\\}$ and action $a=(i,u)$
in state $s$ moves the position on the axis $i$ of a quantity $u$, then the
environment adds a Gaussian noise. Formally
$s^{\prime}\sim\left((s+u.e_{i}+\mathcal{N}(0,\sigma^{2}))\mod 1\right)$,
where $(e_{j})_{1\leqslant j\leqslant n}$ is the canonical basis
$(e_{i})_{k}=\mathbbm{1}_{i=k}$. We consider the environment in dimensions
$n=4$ and $n=6$. We also consider the modified environment with the _freeze_
action described in Section 2. For every environment, we observe trajectories
of length 200, and the reported metric is the rescaled negative L$1$ distance
to the goal at the end of trajectory $-\frac{1}{n}\|s-g\|_{1}$. The
experimental details are in Appendix A.

We compare UVFA, HER, $\delta\text{-}\mathrm{DQN}$, and $\delta$-PPO (defined
in Appendix A based on $\delta\text{-}\mathrm{AC}$). Each algorithm fails in
some environment: additional experiments in the Appendix show that
$\delta$-DQN and $\delta$-PPO are both failing to learn when the dimension of
the torus increases, while HER is still able to learn. This is discussed in
Section 5. While UVFA, HER and $\delta\text{-}\mathrm{DQN}$ are similar
algorithms and can be compared as actor-critic methods handle the trajectory
samples in a different way from $Q$-learning methods. Still, we observe that
$\delta$-PPO learns successfully in the same environments as $\delta$-DQN, and
also failing when $\delta$-DQN does.

#### The FetchReach environment.

The FetchReach environment (Plappert et al., 2018) is a robotic arm
environment in which the objective is for the extremity of the arm to reach a
given 3D position. The environment is deterministic, so HER is expected to
perform well. Here, all methods learn successfully. We also experimented
$\delta\text{-}\mathrm{DQN}$ and $\delta$-PPO on more complex environments of
the same robotic suite, such as FetchPush, but both methods fail in this
setting, while HER was successful.

Figure 1: We compare UVFA, HER, $\delta$-DQN in toy environments. We observe
different regimes: with a highly stochastic environment (Torus with freeze
action), HER is unable to learn because of its bias, whereas UVFA and
$\delta\text{-}\mathrm{DQN}$ are. When the state dimension becomes too large
(Torus$(6)$), UVFA is unable to learn because of the vanishing reward issue.
In environments in which HER is able to learn, it is the most efficient
method, and $\delta\text{-}\mathrm{DQN}$ is always performing better than
UVFA.

##  5 Limitations and Future Work

The algorithms using infinitely sparse rewards always perform better than
UVFA, and perform better than HER in environments designed to exhibit the HER
bias issue. But they do not perform as well as HER in some standard
environments, and are unable to learn at all in more complex environments such
as FetchPush. We discuss two technical limitations of $\delta$-DQN and
$\delta$-Actor-Critic.

The first issue is the function approximation. Learning the models
$Q_{\theta}(s,a,\operatorname{d}\\!{}g)=q_{\theta}(s,a,g)\rho(\operatorname{d}\\!{}g)$
of $Q^{\ast}$ and
$M_{\theta}^{\pi}(s,g_{1},\operatorname{d}\\!{}g_{2})=m_{\theta}(s,g_{1},g_{2})\rho(\operatorname{d}\\!{}g_{2})$
of $M^{\pi}$ requires approximating a Dirac distribution (when
$g_{2}=\varphi(s)$) with a continuous density. The theorems justify this, but
in practice the functions $m_{\theta}$ and $q_{\theta}$ have to reach multiple
orders of magnitude (high values close to the goal, low everywhere else), and
the values need to be accurate in these two regimes. Representing multiple
orders of magnitude in neural networks may require a well-suited family of
parametric functions.

A second issue is variance. The Dirac rewards remove the _infinite_ variance
of vanishing rewards in UVFA when $\varepsilon\rightarrow 0$. But the variance
of the remaining term can be high. Consider the tabular case (6)–(7):
$\delta$-DQN learns significantly faster than UVFA on the _diagonal_
$Q(s,a,g)$ when $g=s$, thanks to the Diracs. But this does not change the way
the reward is propagated to other states, due to the independent sampling of
$g$ in (7). Selecting goals $g$ more correlated to the state $s$ as in HER
could also be helpful, but this is not obvious to do without re-introducing
HER-style bias.

##  6 Conclusion

We have proved that there exist unbiased goal-oriented RL algorithms which do
not vanish when rewards become sparse: it is possible to deal with sparse
rewards in RL directly via the infinitely sparse reward limit, although this
does not solve all variance issues. We have also proved that another multi-
goal method, HER, is unbiased and has the correct fixed point in all
deterministic environments.

## Acknowledgments

We would like to thank Ahmed Touati for his technical help, and Corentin
Tallec, Alessandro Lazaric, Nicolas Usunier and Jonathan Laurent for their
helpful comments and advice.

## References

  * Andrychowicz et al. (2017) Andrychowicz, M., Wolski, F., Ray, A., Schneider, J., Fong, R., Welinder, P., McGrew, B., Tobin, J., Abbeel, O. P., and Zaremba, W.  Hindsight experience replay.  In _Advances in neural information processing systems_ , pp. 5048–5058, 2017.
  * Blier et al. (2021) Blier, L., Tallec, C., and Ollivier, Y.  Learning successor states and goal-dependent values: A mathematical viewpoint.  _ArXiv_ , abs/2101.07123, 2021.
  * Bogachev (2007) Bogachev, V. I.  _Measure theory_ , volume 1.  Springer Science & Business Media, 2007.
  * Fischhoff (1975) Fischhoff, B.  Hindsight is not equal to foresight: The effect of outcome knowledge on judgment under uncertainty.  _Journal of Experimental Psychology: Human perception and performance_ , 1(3):288, 1975.
  * Hausman et al. (2018) Hausman, K., Springenberg, J. T., Wang, Z., Heess, N., and Riedmiller, M.  Learning an embedding space for transferable robot skills.  In _International Conference on Learning Representations_ , 2018.
  * Jaderberg et al. (2016) Jaderberg, M., Mnih, V., Czarnecki, W. M., Schaul, T., Leibo, J. Z., Silver, D., and Kavukcuoglu, K.  Reinforcement learning with unsupervised auxiliary tasks.  _arXiv preprint arXiv:1611.05397_ , 2016.
  * Lanka & Wu (2018) Lanka, S. and Wu, T.  Archer: Aggressive rewards to counter bias in hindsight experience replay.  _ArXiv_ , abs/1809.02070, 2018.
  * Lillicrap et al. (2016) Lillicrap, T., Hunt, J. J., Pritzel, A., Heess, N., Erez, T., Tassa, Y., Silver, D., and Wierstra, D.  Continuous control with deep reinforcement learning.  _CoRR_ , abs/1509.02971, 2016.
  * Manela & Biess (2021) Manela, B. and Biess, A.  Bias-reduced hindsight experience replay with virtual goal prioritization.  _Neurocomputing_ , 451:305–315, 2021.
  * Nagabandi et al. (2019) Nagabandi, A., Clavera, I., Liu, S., Fearing, R., Abbeel, P., Levine, S., and Finn, C.  Learning to adapt in dynamic, real-world environments through meta-reinforcement learning.  _arXiv: Learning_ , 2019.
  * Plappert et al. (2018) Plappert, M., Andrychowicz, M., Ray, A., McGrew, B., Baker, B., Powell, G., Schneider, J., Tobin, J., Chociej, M., Welinder, P., et al.  Multi-goal reinforcement learning: Challenging robotics environments and request for research.  _arXiv preprint arXiv:1802.09464_ , 2018.
  * Rauber et al. (2019) Rauber, P., Mutz, F. W., and Schmidhuber, J.  Hindsight policy gradients.  _ArXiv_ , abs/1711.06006, 2019.
  * Schaul et al. (2015) Schaul, T., Horgan, D., Gregor, K., and Silver, D.  Universal value function approximators.  In Bach, F. and Blei, D. (eds.), _Proceedings of the 32nd International Conference on Machine Learning_ , volume 37 of _Proceedings of Machine Learning Research_ , pp. 1312–1320, Lille, France, 07–09 Jul 2015\. PMLR.  URL http://proceedings.mlr.press/v37/schaul15.html.
  * Schulman et al. (2017) Schulman, J., Wolski, F., Dhariwal, P., Radford, A., and Klimov, O.  Proximal policy optimization algorithms.  _ArXiv_ , abs/1707.06347, 2017.
  * Sutton & Barto (2018) Sutton, R. S. and Barto, A. G.  _Reinforcement learning: An introduction_.  MIT press, 2018.  2nd edition.
  * Wang et al. (2016) Wang, Z., Schaul, T., Hessel, M., Hasselt, H. V., Lanctot, M., and Freitas, N. D.  Dueling network architectures for deep reinforcement learning.  _ArXiv_ , abs/1511.06581, 2016.

  1. 1.

For all authors…

    1. (a)

Do the main claims made in the abstract and introduction accurately reflect
the paper’s contributions and scope? [Yes]

    2. (b)

Did you describe the limitations of your work? [Yes]

    3. (c)

Did you discuss any potential negative societal impacts of your work? [N/A]

    4. (d)

Have you read the ethics review guidelines and ensured that your paper
conforms to them? [Yes]

  2. 2.

If you are including theoretical results…

    1. (a)

Did you state the full set of assumptions of all theoretical results? [Yes]

    2. (b)

Did you include complete proofs of all theoretical results? [Yes]

  3. 3.

If you ran experiments…

    1. (a)

Did you include the code, data, and instructions needed to reproduce the main
experimental results (either in the supplemental material or as a URL)? [Yes]

    2. (b)

Did you specify all the training details (e.g., data splits, hyperparameters,
how they were chosen)? [Yes]

    3. (c)

Did you report error bars (e.g., with respect to the random seed after running
experiments multiple times)? [Yes]

    4. (d)

Did you include the total amount of compute and the type of resources used
(e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]

  4. 4.

If you are using existing assets (e.g., code, data, models) or
curating/releasing new assets…

    1. (a)

If your work uses existing assets, did you cite the creators? [Yes]

    2. (b)

Did you mention the license of the assets? [Yes]

    3. (c)

Did you include any new assets either in the supplemental material or as a
URL? [Yes]

    4. (d)

Did you discuss whether and how consent was obtained from people whose data
you’re using/curating? [N/A]

    5. (e)

Did you discuss whether the data you are using/curating contains personally
identifiable information or offensive content? [N/A]

  5. 5.

If you used crowdsourcing or conducted research with human subjects…

    1. (a)

Did you include the full text of instructions given to participants and
screenshots, if applicable? [N/A]

    2. (b)

Did you describe any potential participant risks, with links to Institutional
Review Board (IRB) approvals, if applicable? [N/A]

    3. (c)

Did you include the estimated hourly wage paid to participants and the total
amount spent on participant compensation? [N/A]

Table 1: Notation in the main text Notation |  Definition
---|---
$\mathcal{S}$ |  State space
$\mathcal{A}$ |  Action space
$\gamma$ |  Discount factor, $0\leqslant\gamma<1$
$P(\operatorname{d}\\!{}s^{\prime}|s,a)$ |  Transition probability measure, over $\mathcal{S}$, for every $s,a\in\mathcal{S}\times\mathcal{A}$.
$\mathcal{G}$ |  Goal space
$n$ |  Dimension of the goal space
$\varphi$ |  Goal function $\varphi:\mathcal{S}\rightarrow\mathcal{G}$. The goal $\varphi(s)$ is the goal _achieved_ in $s$.
$\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$ |  Goal sampling distribution.
$p_{\mathcal{G}}(g)$ |  If it exists, the density of $\rho_{\mathcal{G}}$ with respect to $\lambda$.
$\rho_{0}(\operatorname{d}\\!{}s_{0}|g)$ |  Initial state sampling distribution
$p_{0}(s_{0}|g)$ |  If it exists, the density of $\rho_{0}$ with respect to $\lambda$.
$\lambda(\operatorname{d}\\!{}.)$ |  Lebesgue measure
$\varepsilon$ |  Threshold for the sparse reward. $\varepsilon>0$
$\mathbbm{1}_{A}(x)$ |  Function equal to $1$ if $x\in A$, and $0$ is $x\notin A$.
$R_{\varepsilon}(s,g)$ |  Sparse reward around goal $g$: $R_{\varepsilon}(s,g)=\mathbbm{1}_{\|\varphi(s)-g\|\leqslant\varepsilon}(s))$
$\lambda(\varepsilon)$ |  Volume of a sphere of radius $\varepsilon$: $\lambda(\varepsilon)=\lambda(\\{x\quad\text{s.t.}\quad\|x\|\leqslant\varepsilon\\})$
$\pi$ |  Goal dependent policy. If $\mathcal{A}$ is discrete, $\pi(a|s,g)$ is the probability of selecting action $a$. If $\mathcal{A}$ is continuous, it is the density of selecting $a$ with respect to Lebesgue measure.
$P^{\pi}(\operatorname{d}\\!{}s^{\prime}|s,g)$ |  Transition probability measure for policy $\pi$:
|
$P^{\pi}(\operatorname{d}\\!{}s^{\prime}|s,g)=\int_{a}\pi(a|s,g)P(\operatorname{d}\\!{}s^{\prime}|s,a)$.
$\tau$ |  Trajectory: $\tau=(g,s_{0},a_{0},s_{1},...)$, with $g\sim\rho_{\mathcal{G}}$, $s_{0}\sim\rho_{0}(.|g)$,
|  $a_{t}\sim\pi(.|s_{t},g)$, $s_{t+1}\sim P(.|s_{t},a_{t})$.
$V^{\pi}_{\varepsilon}(s,g)$ |  Value function for reward $\varepsilon$:
|  $V^{\pi}_{\varepsilon}(s,g)=\mathbb{E}_{s_{t+1}\sim
P^{\pi}(.|s_{t},g)}\left[\sum_{t\geqslant
0}\gamma^{t}R_{\varepsilon}(s_{t},g)|s_{0}=s\right]$
$Q^{\pi}_{\varepsilon}(s,a,g)$ |  Action-value function for reward $\varepsilon$:
|
$Q^{\pi}_{\varepsilon}(s,a,g)=\mathbb{E}_{a_{t}\sim\pi(.|s_{t},g),s_{t+1}\sim
P(.|s_{t},a_{t})}\left[\sum_{t\geqslant
0}\gamma^{t}R_{\varepsilon}(s_{t},g)|s_{0}=s,a_{0}=a\right]$
$\pi^{\ast}$ |  Optimal policy
$Q^{\ast}_{\varepsilon}(s,a,g)$ |  Optimal action-value function for reward $R_{\varepsilon}$: $Q^{\ast}=Q^{\pi^{\ast}}$.
$\tilde{\mathcal{S}},\tilde{P}$ |  Augmented MDP: $\tilde{\mathcal{S}}=\mathcal{S}\times\mathcal{G}$ and for every $\tilde{s}=(s,g)$, action $a$, next state $\tilde{s}$ is sampled as $\tilde{s}=(s^{\prime},g)$ where $s^{\prime}\sim P(\operatorname{d}\\!{}s^{\prime}|s,a)$.
$Q_{\theta}$, $V_{\theta}$ |  Models of $Q^{\ast}$, $V^{\pi}$ parametrized by $\theta$.
$Q_{\mathrm{tar}}$, $V_{\mathrm{tar}}$ |  Target values
$Q_{\infty}$ |  Fixed point of an algorithm
$\pi_{\mathrm{expl}}$ |  Exploration policy
$T$ |  Optimal Bellman operator, defined for function $Q(s,a,g)$ or measures $Q(s,a,\operatorname{d}\\!{}g)$
|  $\bullet$ Functions: $(T\cdot
Q)(s,a,g)=R_{\varepsilon}(s,g)+\gamma\mathbb{E}_{s^{\prime}\sim
P(.|s,a)}\left[\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},g)\right]$.
|  $\bullet$ Measures: $(T\cdot
Q)(s,a,\operatorname{d}\\!{}g)=\delta_{\varphi(s)}(\operatorname{d}\\!{}g)+\gamma\mathbb{E}_{s^{\prime}\sim
P(.|s,a)}\left[\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},\operatorname{d}\\!{}g)\right]$.
$\widehat{\delta\theta}_{\mathrm{UVFA}}(s,a,s^{\prime},g)$ |  Stochastic _Universal Value Function Approximators_ update for $Q$-learning
Hindsight Experience Replay
$K$ |  Step $s_{K}$ of the update for a trajectory $\tau=(g,s_{0},a_{0},s_{1},...)$
$g^{\prime}$ |  Re-sampled goal by HER
$L$ |  Step of the resampling goal: $g^{\prime}=\varphi(s_{L})$.
$\widehat{\delta\theta}_{\mathrm{HER}}(\tau,K,L)$ |  HER stochastic update
$\|.\|_{\mathrm{HER}}$ |  Norm such that $\widehat{\delta\theta}_{\mathrm{HER}}(\tau,K,L)$ is an unbiased estimate of Bellman error
$a^{\ast}$ |  freeze-after-random-jump additional action
Infinitely Sparse Rewards
$\delta_{x}(\operatorname{d}\\!{}x^{\prime})$ |  Dirac measure located in $g$
$R(s,\operatorname{d}\\!{}g)$ |  Infinitely spare Dirac reward: $R(s,\operatorname{d}\\!{}g)=\delta_{\varphi(s)}(\operatorname{d}\\!{}g)$.
$Q^{\ast}(s,a,\operatorname{d}\\!{}g)$ |  Optimal action-value _measure_
$M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$ |  Successor goal _measure_ :
|
$M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})=\mathbb{E}_{a_{t}\sim\pi(.|s_{t},g),s_{t+1}\sim
P(.|s_{t},a_{t})}\left[\sum_{t\geqslant
0}\gamma^{t}\delta_{\varphi(s_{t})}(\operatorname{d}\\!{}g^{\prime})|s_{0}=s\right]$
$V^{\pi}(s,\operatorname{d}\\!{}g)$ |  Value _measure_ : $V^{\pi}(s,\operatorname{d}\\!{}g)=M^{\pi}(s,g,\operatorname{d}\\!{}g)$
$q_{\theta}(s,a,g)$ |  Model of the density of $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$ with respect to $\rho_{\mathcal{G}}$ parametrized by $\theta$
$Q_{\theta}(s,a,\operatorname{d}\\!{}g)$ |  Model of $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$ defined via its density: $Q_{\theta}(s,a,\operatorname{d}\\!{}g)=q_{\theta}(s,a,g)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
$q_{\mathrm{tar}}$ |  Target values
$\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}(s,a,s^{\prime},g)$ |  Stochastic update of $q_{\theta}(s,a,g)$ for $\delta\text{-}\mathrm{DQN}$
$\eta$ |  Learning rate
$T^{\pi}$ |  Bellman operator:
|  $(T^{\pi}\cdot
M)(s,g,\operatorname{d}\\!{}g^{\prime})=\delta_{\varphi(s)}(\operatorname{d}\\!{}g^{\prime})+\gamma\mathbb{E}_{s^{\prime}\sim
P^{\pi}(.|s,g)}\left[M^{\pi}(s^{\prime},g,\operatorname{d}\\!{}g^{\prime})\right]$.
$m_{\theta}(s,g,g^{\prime})$ |  Model of the density of $M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$ with respect to $\rho_{\mathcal{G}}(\operatorname{d}\\!{}g^{\prime})$ parametrized by $\theta$
$M_{\theta}(s,g,\operatorname{d}\\!{}g^{\prime})$ |  Model of $M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$ defined via its density:
|
$M_{\theta}(s,g,\operatorname{d}\\!{}g^{\prime})=m_{\theta}(s,g,g^{\prime})\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
$\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}}(s,a,s^{\prime},g,g^{\prime})$ |  Stochastic update of $m_{\theta}(s,g,g^{\prime})$ for $\delta\text{-}\mathrm{TD}$
$\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}(n)}(\tau,k,g^{\prime})$ |  Stochastic update of $m_{\theta}(s,g,g^{\prime})$ for $\delta\text{-}\mathrm{TD}(n)$
$J_{\varepsilon}(\pi)$ |  Expected return $J_{\varepsilon}(\pi)=\mathbb{E}_{g\sim\rho_{\mathcal{G}},s_{0}\sim\rho_{0}(.|g)}\left[\sum_{t\geqslant 0}\gamma^{t}R_{\varepsilon}(s_{t},g)|s_{0}=s\right]$
$J(\pi)$ |  Expected return with infinitely sparse rewards
$\nu^{\pi}(\operatorname{d}\\!{}s|g,s_{0})$ |  Discounted visitation frequencies:
|  $\nu^{\pi}(\operatorname{d}\\!{}s|s_{0},g)=(1-\gamma)\sum_{t\geqslant
0}\gamma^{t}(P^{\pi})^{t}(\operatorname{d}\\!{}s|s_{0},g)$
$\theta_{M}$ |  In policy gradient, parameter of the critic $m_{\theta_{M}}(s,g,g^{\prime})$
$\widehat{\delta\theta}_{\delta\text{-}\mathrm{AC}}(s,a,s^{\prime},g)$ |  Stochastic update for $\delta\text{-}\mathrm{AC}$
|

##  Appendix A Experiments Details

In this section, we present the experiment details of Section 4. Every
experiment was performed on a single GPU.

#### The Torus(n) environment

The state space of the Torus$(n)$ environment is the $n$-th dimensional torus,
$\mathcal{S}=[0,1)^{n}$, and can be obtained from the $n$-dimensional
hypercube by gluing the opposite faces together. If the current state is
$s=(s_{1},...,s_{n})$, we define the observation of the agent as $(\cos(2\pi
s_{1}),...,\cos(2\pi s_{n}),\sin(2\pi s_{1}),...,\sin(2\pi
s_{n}))\in[-1,1]^{2n}$. We use this representation in order to remove the
discontinuity of the representation $[0,1)^{n}$. This representation contains
all the information of the state $s$ and the environment is still fully
observable (and not partially observable). The action space is
$\mathcal{A}=\\{1,\ldots,n\\}\times\\{-\alpha,\alpha\\}$ and action $a=(i,u)$
in state $s$ moves the position on the axis $i$ of a quantity $u$, then the
environment adds a Gaussian noise. Formally
$s^{\prime}\sim\left((s+u.e_{i}+\mathcal{N}(0,\sigma^{2}))\mod 1\right)$,
where $(e_{j})_{1\leqslant j\leqslant n}$ is the canonical basis
$(e_{i})_{k}=\mathbbm{1}_{i=k}$. In practice, we take $\alpha=0.1$, and
$\sigma=\frac{0.1}{n}$. The reward is
$R_{\varepsilon}(s,g)=\mathbbm{1}_{\|s-g\|\leqslant\varepsilon}$ where $\|.\|$
is the rescaled L$1$ distance in the Torus:
$\|s-g\|=\frac{1}{n}\sum_{i=1}^{n}\min((s_{i}-g_{i})\mod 1,|((s_{i}-g_{i})\mod
1)-1|)$. In practice, we use $\varepsilon=0.05$. At the beginning of an
episode, we sample a goal uniformly in the environment, then we observe
trajectories of length $200$. We set $\gamma=.995$.

#### FetchReach

FetchReach is a standard environment from Plappert et al. (2018). The
objective is to reach a _goal_ position in 3 dimension with the end of the
robotic arm. The observation space $\mathcal{S}$ is of dimension $10$ and
contains positions and velocities, such that the environment is Markov, fully
observable, and deterministic. The action space $\mathcal{A}$ is continuous
and of dimension $4$. The goal space $\mathcal{G}$ is of dimension $3$, and
the goal represent the position of the end of the robotic arm. Trajectories
are of length $50$.

#### Q-learning experiments

Here we describe experiments with UVFA, HER and $\delta\text{-}\mathrm{DQN}$,
which have similar structure. For every algorithm, we use the same neural
network to learn $Q_{\theta}(s,a,g)$ or $q_{\theta}(s,a,g)$. Simlarly to DDPG
(Lillicrap et al., 2016), if the action space $\mathcal{A}$ is continuous, we
additionally learn a deterministic policy
$\pi_{\theta}:\mathcal{S}\times\mathcal{G}\rightarrow\mathcal{A}$. We use a
dueling architecture (Wang et al., 2016): we learn a _value_ network
$v_{\theta}(s,g)$ and an _advantage_ network $\mathrm{adv}_{\theta}(s,a,g)$.
We then define
$q_{\theta}(s,a,g)=v_{\theta}(s,g)+\widetilde{\mathrm{adv}}_{\theta}(s,a,g)$,
where $\widetilde{\mathrm{adv}}_{\theta}(s,a,g)$ is the _rescaled_ advantage,
and is defined as
$\widetilde{\mathrm{adv}}_{\theta}(s,a,g)=\mathrm{adv}_{\theta}(s,a,g)-\frac{1}{|\mathcal{A}|}\sum_{a^{\prime}\in\mathcal{A}}\mathrm{adv}_{\theta}(s,a^{\prime},g)$
if $\mathcal{A}$ is finite, and
$\widetilde{\mathrm{adv}}_{\theta}(s,a,g)=\mathrm{adv}_{\theta}(s,a,g)-\mathrm{adv}_{\theta}(s,\pi(s,g),g)$
if $\mathcal{A}$ is continuous. The networks for $v_{\theta}$, $a_{\theta}$
and $\pi_{\theta}$ are 3-hidden layers MLP of width 256 and ReLU activations.
The inputs of $v_{\theta}$ and $\pi_{\theta}$ are the concatenation of $s$ and
$g$. If $\mathcal{A}$ is continuous, the input of $\mathrm{adv}_{\theta}$ is
the concatenation of $s,a,g$. If $\mathcal{A}$ is discrete, the input of
$\mathrm{adv}_{\theta}$ is the concatenation of $s$ and $g$, and its output is
of dimension $|\mathcal{A}|$, every dimension corresponding to an action.

Most hypereparameters are shared among the three methods: we observe batchs of
trajectories of size $16$ for the Torus experiments, and of size $2$ for the
FetchReach environment. At every epoch, we observe a batch of trajectories and
store it in a memory buffer of size $10^{6}$ transitions. We use an
$\varepsilon$-greedy exploration strategy, with $\varepsilon=0.2$. At every
epoch, we sample $100$ batches from the replay buffer for the Torus
experiments, and $50$ for the FetchReach environment. For HER, we use the
future sampling strategy for goals: when sampling a transition
$(s,a,s^{\prime},g)$, with probability $0.2$ we define $g^{\prime}=g$, and
with probabiliyt $0.8$ we sample $g^{\prime}$ uniformly in the future of $s$.
For $\delta\text{-}\mathrm{DQN}$ in the Torus environment, we sample
independant goals with $\rho_{\mathcal{G}}$ uniform distribution in the Torus.
In FetchReach, we do not assume we have access to the goal sampling
distribution. Therefore, we re-sample independant goals from the memory
buffer. For every method, observations and goals are normalized. We use a
target network with parameter $\theta_{\mathrm{tar}}$ and update the target as
$\theta_{\mathrm{tar}}\leftarrow(1-\alpha)\theta_{\mathrm{tar}}+\alpha\theta$
with $\alpha=0.05$ after every epoch. Every model is trained with the Adam
optimizer with $\beta_{1}=0.9$ and $\beta_{2}=0.999$.

For every method and environment, the most sensitive hyperparameters were
selected with a grid-search. For HER, UVFA and $\delta\text{-}\mathrm{DQN}$,
we selected the learning rate of the optimizer from a range
$\\{1e-6,3e-6,1e-5,3e-5,1e-4,3e-4,1e-3\\}$. For HER and UVFA, we additionally
selected $R$ a reward scaling factor, in $\\{1e-2,1e-1,1,10,100,1000,1e4\\}$.
For $\delta\text{-}\mathrm{DQN}$, we also selected a parameter $c_{\delta}$
corresponding to the scaling of the reward: the scaled infinitely sparse
reward is
$R(s,\operatorname{d}\\!{}g)=c_{\delta}\delta_{\varphi(s)}(\operatorname{d}\\!{}g)$.
We experimented all the possible hyperparameters of this grid separately on
every environment on a single run and selected the best hyperparameters. The
values in Figure 1 are the mean performance evaluated with $5$ different
random seeds, and the confidence intervals represent the standard deviation of
the reported metric accross the $5$ independent runs. In practice, the reward
scaling factor for UVFA is $10$ for all the Torus environments and $100$ for
FetchReach. The reward factor is $1$ for HER for all the Torus environments
and $10$ for FetchReach. The learning rate for UVFA is $1e-4$ for all the
Torus environments and $1e-3$ for FetchReach. The learning rate for HER is
$3e-4$ for all the Torus environments and $1e-3$ for HER. For
$\delta\text{-}\mathrm{DQN}$, the learning rate is $1e-5$ for all the Torus
environments, and $1e-4$ for the FetchReach environment. The reward scaling
coefficient $c_{\delta}$ is $1e-2$ for every environments.

####  $\delta$-PPO experiments

The $\delta\text{-}\mathrm{PPO}$ is defined from $\delta\text{-}\mathrm{AC}$
similarly to PPO (Schulman et al., 2017) from actor critic methods. We learn
the model $m_{\theta}(s,g,g^{\prime})$ of the density of
$M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$ with respect to
$\rho_{\mathcal{G}}$, and $\pi_{\theta}(a|s,g)$ a parametric policy. We used a
shared architecture: we define $h_{\theta}(s,g,g^{\prime})$ a network
computing a hidden representation of dimension $H$. Then, we define two linear
layers $L^{m}_{\theta}$ and $L^{\pi}{\theta}$, and define
$m_{\theta}(s,g,g^{\prime})=L^{m}_{\theta}(h_{\theta}(s,g,g^{\prime}))$ and
$\pi_{\theta}(a|s,g)=L^{\pi}_{\theta}(h_{\theta}(s,g,g^{\prime}))$. In
practice, $h_{\theta}$ is a 2-hidden layers MLP with ReLU activations (except
at the last layer), with width $H=256$ for the internal and output layers.

A step of $\delta\text{-}\mathrm{PPO}$ is defined as follow. We first gather a
buffer of trajectories with the current policy $\pi_{\theta}$. Then, we define
$\theta^{\prime}\mathrel{\mathop{:}}=\theta$. For every transition
$(s,a,s^{\prime},g)$ in the buffer and every epoch $e\leqslant E$, we sample
an independant goal $g^{\prime}$ and compute:

$\displaystyle\widehat{\delta\theta}_{M}$
$\displaystyle\leftarrow\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}}(s,a,s^{\prime},g,g^{\prime})$
(14) $\displaystyle\mathrm{adv}$ $\displaystyle\leftarrow\gamma
m_{\theta_{M}}(s^{\prime},g,g)-m_{\theta_{M}}(s,g,g)$ (15) $\displaystyle
r(\theta^{\prime})$
$\displaystyle\leftarrow\frac{\pi_{\theta^{\prime}}(a|s,g)}{\pi_{\theta}(a|s,g)}$
(16) $\displaystyle\tilde{r}(\theta^{\prime})$
$\displaystyle\leftarrow\mathrm{clip}(r,1-u,1+u)$ (17)
$\displaystyle\widehat{\delta\theta}_{\pi}$
$\displaystyle\leftarrow\partial_{\theta^{\prime}}\left(\min\left(\mathrm{adv}\times
r(\theta^{\prime}),\mathrm{adv}\times\tilde{r}(\theta^{\prime})\right)\right)$
(18) $\displaystyle\widehat{\delta\theta}$
$\displaystyle\leftarrow\widehat{\delta\theta}_{\pi}+c_{M}\times\widehat{\delta\theta}_{M}$
(19)

where $c_{M}$ allow to scale the two updates. Then we use
$\widehat{\delta\theta}$ and with Adam optimizer to obtain a new value for
$\theta^{\prime}$. We did not use an entropy regularizer aw we observed that
the diversity of actions was not an issue in practice.

For the Torus environment, the independent goals $g^{\prime}$ are sampled fron
$\rho_{\mathcal{G}}$ the uniform distribution of goals in the environment. For
FetchReach, we do not assume we know $\rho_{\mathcal{G}}$ and sample goals
from the buffer.

In practice, at every step of the $\delta\text{-}\mathrm{PPO}$ algorithm we
observe a batch of $2$ trajectories for Torus$(4)$ and Torus$(6)$, $100$ for
the Torus$(4)$ with the freeze action $a^{\ast}$, and $200$ for FetchReach.
Three hyperparameters were selected independently for every environment via a
grid search: $E$ the number of epochs per $\delta\text{-}\mathrm{PPO}$ step,
the learning rate of Adam optimizer, and the coefficient $c_{M}$. We performed
a grid search with a single run per tuple of parameters. Then, the reported
results in Figure 1 are averaged over $5$ different random seeds with the
selected hyperparameters. The number of epoch $E$ per step was selected as
lowest number which achieved close-to-optimal performance accross the range
$\\{1,2,5,10,20,50,100\\}$. In practice, $E=20$ in the Torus$(4)$ and
Torus$(6)$ environments, $E=10$ in the Torus$(4)$ with the freeze action
$a^{\ast}$, and $E=50$ for FetchReach. The learning rate was selected in the
set $\\{1e-6,3e-6,1e-5,3e-5,1e-4,3e-4,1e-3\\}$, and in practice is $1e-4$ for
every environment. The coefficient $c_{M}$ was selected in
$\\{1e-4,1e-3,1e-2,1e-1,1e0,1e1,1e2,1e3\\}$ and in practice is $1e-3$ for
every Torus environment and $1e-1$ for the FetchReach environment.

#### Additional experiments

We experimented $\delta\text{-}\mathrm{DQN}$ and $\delta\text{-}\mathrm{PPO}$
in more complex environments such Torus of higher dimension, or other
environments of OpenAI Robotic suite (Plappert et al., 2018). In the Torus
environment, both methods fail when the dimension increases above $15$ while
HER is still able to learn. More importantly, $\delta\text{-}\mathrm{PPO}$ and
$\delta\text{-}\mathrm{DQN}$ did not learn at all in environments such as
FetchPush (which is easy to solve with HER) or HandReach, which has similar
structure but higher dimension than FetchReach. In the FetchPush environment,
the objective is to push a cube with a robotic arm to a given goal. We
observed that the issue of our methods was not an exploration issue, since the
robotic arm oftens reaches and pushes the cube randomly. We tried to increase
the generalization accross goals with the $\delta\text{-}\mathrm{TD}(n)$
update, but it was to computationally expensive, as explained in Section 3.3.
Limitations of $\delta\text{-}\mathrm{DQN}$ and $\delta\text{-}\mathrm{PPO}$
which could explain these results are discussed in Section 5.

##  Appendix B Proofs of Theorems on HER

###  B.1 HER is Unbiased in Deterministic Environments

We prove that HER is an unbiased method in deterministic environments. In
order to define HER, we assume access to samples of trajectories
$(g,s_{0},a_{0},s_{1},a_{1},...)\sim\rho(g,s_{0},a_{0},s_{1},a_{1},...)$ with
$g\sim\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$,
$s_{0}\sim\rho_{0}(\operatorname{d}\\!{}s_{0}|g)$, and for every $k\geqslant
0$, $a_{k}\sim\pi_{\mathrm{expl}}(a|s_{k},g)$ where $\pi_{\mathrm{expl}}$ is
an exploration policy, $s_{k+1}\sim P(\operatorname{d}\\!{}s|s_{k},a_{k})$.
For simplicity, we will assume the trajectories are infinite.

Here we consider HER with the future strategy descibed in the original paper:
goals are re-sampled from a trajectory as goal reached later in the
trajectory. We formalize HER as follows: we sample a trajectory
$\tau=(g,s_{0},a_{0},s_{1},a_{1},...)\sim\rho(g,s_{0},a_{0},s_{1},a_{1},...)$,
a Bernoulli variable $U\sim\mathcal{B}(\alpha)$, and two independent integer
random variables $K,L$, from distributions $p_{K}$ and $p_{L}$, such that for
every $k,l$, $p_{K}(k)>0$ and $p_{L}(l)>0$. The bernoulli variable $U$
represents the random choice of using the standard Q-learning update, or the
HER update with a resampled goal. The random variable $K$ represents the
timestep of the transition we will use for the Q-learning update, and $L$
represents the timestep used to sample a new goal $g^{\prime}$ for the future
sampling strategy. Then, the update
$\widehat{\delta\theta_{\mathrm{HER}}}(\tau,U,K,L)$ is defined as:

  * •

If $U=0$:

$\widehat{\delta\theta_{\mathrm{HER}}}(\tau,U=0,K,L)\mathrel{\mathop{:}}=\partial_{\theta}\frac{1}{2}(Q_{\theta}(s_{K},a_{K},g)-R(s_{K},g)-\gamma\sup_{a^{\prime}}Q(s_{K+1},a^{\prime},g))^{2},$

which corresponds to the usual Q-learning update as defined in UVFA (Schaul et
al., 2015).

  * •

If $U=1$ we set $g^{\prime}=\varphi(s_{K+L+1})$ and:

$\widehat{\delta\theta_{\mathrm{HER}}}(\tau,U=1,K,L)\mathrel{\mathop{:}}=\partial_{\theta}\frac{1}{2}(Q_{\theta}(s_{K},a_{K},g^{\prime})-R(s_{K},g^{\prime})-\gamma\sup_{a^{\prime}}Q(s_{K},a^{\prime},g^{\prime}))^{2},$

which corresponds to a Q-learning update for a re-sampled goal
$g^{\prime}=\varphi(s_{K+L})$, a goal achieved later in the trajectory.

We say that environment is a _continuous deterministic environment_ if there
is a continuous function
$\psi:\mathcal{S}\times\mathcal{A}\rightarrow\mathcal{S}$ such that for every
$(s,a)\in\mathcal{S}\times\mathcal{A}$,
$P(\operatorname{d}\\!{}s^{\prime}|s,a)=\delta_{\psi(s,a)}(\operatorname{d}\\!{}s^{\prime})$.
In particular, any discrete deterministic environment is a continuous
deterministic environment for the discrete topology. Therefore, the following
theorem can be applied to discrete environments.

###### Theorem 8 (Formal statement of Theorem 2).

We assume the environment is a continuous deterministic environment. We also
assume that for every pair of states $(s,s^{\prime})$, $s^{\prime}$ is
reachable from $s$, which means there is a sequence of actions
$(a_{1},...,a_{k})$ such that applying these actions from $s$ leads to
$s^{\prime}$. Finally, we assume that the support of the exploration policy
$\pi_{\mathrm{expl}}(a|s,g)$ is the entire action space $\mathcal{A}$ for
every $s,g$.

Then, there is an euclidean norm $\|.\|$ such that, for every $\theta$, the
HER update with the future sampling strategy at $\theta$,
$\widehat{\delta\theta_{\text{HER}}}$ is an unbiased estimate of the gradient
step between $Q_{\theta}$ and the target function
$Q_{\text{target}}\mathrel{\mathop{:}}=T_{\max}Q_{\theta}$:

$\mathbb{E}\left[\widehat{\delta\theta_{\text{HER}}}\right]=\partial_{\theta}\frac{1}{2}\|Q_{\theta}-Q^{\mathrm{tar}}\|^{2}$
(20)

If the state space $\mathcal{S}$ is finite, HER has a single fixed point
$Q_{\infty}$, which is equal to $Q^{\ast}$.

The euclidean norm $\|.\|$ in the theorem will depend on the exploration
policy $\pi_{\mathrm{expl}}(a|s,g)$. Therefore, if the exploration policy is
changing during learning, the norm will will be changing as well.

###### Proof.

The principle of the proof is the following. We study the sampling
distribution of transitions $\mu_{\mathrm{HER}}(s,a,s^{\prime},g)$ with HER.
The bias of HER comes from the fact that the sampling of goals $g$ with
$\mu_{\mathrm{HER}}(s,a,s^{\prime},g)$ is not independant of $s^{\prime}$
knowing $(s,a)$. On the contrary, in deterministic environments, the
disribution of $g$ knowing $(s,a)$ is independant of $s^{\prime}$ because
$s^{\prime}$ is uniquely determined by $(s,a)$.

We study the sampling distribution of transitions $(s,a,s^{\prime},g)$ used in
HER. Formally, we sample a transition $(s,a,s^{\prime},g)$ by sampling
$\tau,U,K,L$ and defining
$(s,a,s^{\prime},g^{\prime})\mathrel{\mathop{:}}=\Phi(\tau,U,K,L)$ as:

  * •

If $U=0$, $\Phi(\tau,U=1,K,L)=(s_{k},a_{k},s_{k+1},g)$

  * •

If $U=1$, $\Phi(\tau,U=1,K,L)=(s_{k},a_{k},s_{k+1},\varphi(s_{K+L}))$

Then, $\mathrm{HER}$ update can be equivalently defined as: sample
$(\tau,U,K,L)$ as described above, define
$(s,a,s^{\prime},g)=\Phi(\tau,U,K,L)$, and:

$\widehat{\delta\theta_{\mathrm{HER}}}(s,a,s^{\prime},g)\mathrel{\mathop{:}}=\partial_{\theta}\frac{1}{2}(Q_{\theta}(s,a,s^{\prime},g)-R(s,g)-\gamma\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},g))^{2}$
(21)

Therefore:

$\mathbb{E}\left[\widehat{\delta\theta_{\text{HER}}}\right]=\partial_{\theta}\mathbb{E}_{(s,a,s^{\prime},g)\sim\mu_{\mathrm{HER}}}\frac{1}{2}(Q_{\theta}(s,a,g)-R(s,g)-\gamma\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},g))^{2}$
(22)

where we define $\mu_{\mathrm{HER}}$ to be the distribution of
$(s,a,s^{\prime},g)$ given by the distribution of $\Phi_{\ast}(\rho\otimes
p_{U}\otimes p_{L}\otimes p_{K})$, where $\Phi_{\ast}$ is the _push-forward_
operator on measures. We now compute $\mu_{\mathrm{HER}}$. Let
$f:\mathcal{S}\times\mathcal{A}\times\mathcal{S}\times\mathcal{G}\rightarrow{\mathbb{R}}$
be a test function, we have:

$\displaystyle\mathbb{E}_{s,a,s^{\prime},g\sim\mu_{\mathrm{HER}}}\left[f(s,a,s^{\prime},g)\right]$
$\displaystyle=\mathbb{E}_{\tau,U,K,L}\left[f(\Phi(\tau,U,K,L))\right]$ (23)
$\displaystyle\begin{split}=\quad&(1-\alpha)\mathbb{E}_{\tau,U,K,L}\left[f(\Phi(\tau,U,K,L))|U=0\right]\\\
&+\alpha\mathbb{E}_{\tau,U,K,L}\left[f(\Phi(\tau,U,K,L))|U=1\right]\end{split}$
(24)

Moreover:

$\displaystyle\mathbb{E}_{\tau,U,K,L}$
$\displaystyle\left[f(\Phi(\tau,U,K,L))|U=0\right]=\sum_{K}p_{K}(k)\int_{g,s_{0},a_{0},...}\rho(g,s_{0},a_{0},...)f(s_{k},a_{k},s_{k+1},g)$
(25)
$\displaystyle=\sum_{k}p_{K}(k)\int_{g,s_{0},a_{0},...}\rho_{\mathcal{G}}(g)\rho_{0}(s_{0}|g)(P^{\pi_{\exp}})^{k}(s|s_{0},g)\pi_{\mathrm{expl}}(a|s,g)P(s^{\prime}|s,a)f(s,a,s^{\prime},g)$
(26)
$\displaystyle=\int_{s,a,s^{\prime},g}f(s,a,s^{\prime},g)\left(\rho_{\mathcal{G}}(g)\int_{s_{0}}\sum_{k}p_{K}(k)\rho_{0}(s_{0}|g)(P^{\pi_{\exp}})^{k}(s|s_{0},g)\pi_{\mathrm{expl}}(a|s,g)P(s^{\prime}|s,a)\right)$
(27)
$\displaystyle=\int_{s,a,s^{\prime},g}f(s,a,s^{\prime},g)\rho_{\mathcal{G}}(g)\nu(s|g)\pi_{\mathrm{expl}}(a|s,g)P(s^{\prime}|s,a)$
(28)

with

$\nu(s|g)\mathrel{\mathop{:}}=\rho_{\mathcal{G}}(g)\int_{s_{0}}\rho_{0}(s_{0}|g)\sum_{k}p_{K}(k)(P^{\pi_{\exp}})^{k}(s|s_{0},g)$
(29)

which is the future distribution of states $s$ when sampling a goal $g$ and
following the exploration policy $\pi_{\mathrm{expl}}(.|.,g)$, with $p_{K}$ as
the distribution of future timesteps. If $p_{K}(k)=(1-\gamma)\gamma^{k}$, this
definition of $\nu$ coincides with the definition of $\nu^{\pi}$ in the
following sections. This is the reason why we use the same notation, even
though $\nu$ is here slightly more general.

We now compute:

$\displaystyle\mathbb{E}_{\tau,U,K,L}$
$\displaystyle\left[f(\Phi(\tau,U,K,L))|U=1\right]=\sum_{k,l}p_{K}(k)p_{L}(l)\int_{g,s_{0},a_{0},...}\rho(g,s_{0},a_{0},...)f(s_{k},a_{k},s_{k+1},\varphi(s_{k+l}))$
(30)

If $l=0$, the re-sampled goal is $g^{\prime}=\varphi(s)$. Else, the law of
$g^{\prime}$ knowing $s_{k},a_{k},s_{k+1}$ is the law of $\varphi(s_{k+l})$,
which by using the Markov property is the law of $\varphi(\tilde{s})$ if
$\tilde{s}$ is sampled as $(P^{\pi_{\mathrm{expl}}})^{l-1}(.|s_{k+1},g)$.
Therefore:

$\displaystyle\mathbb{E}_{\tau,U,K,L}\left[f(\Phi(\tau,U,K,L))|U=1\right]=\sum_{k,l\geqslant
0}p_{K}(k)p_{L}(l)\int_{g,s_{0},a_{0},...}\rho(g,s_{0},a_{0},...)f(s_{k},a_{k},s_{k+1},\varphi(s_{k+l}))$
(31)
$\displaystyle\begin{split}=&\sum_{k}p_{K}(k)\int_{g,s_{0},...,s_{k+1}}\rho(g,s_{0},...,s_{k+1})\left(p_{L}(0)f(s_{k},a_{k},s_{k+1},\varphi(s_{k}))\right)+\\\
&+\sum_{k}p_{K}(k)\int_{g,s_{0},...,s_{k+1}}\rho(g,s_{0},...,s_{k+1})\left(\sum_{l\geqslant
1}p_{L}(l)\int_{\tilde{s}}(P^{\pi_{\mathrm{expl}}})^{l-1}(\tilde{s}|s_{k+1},g)f(s_{k},a_{k},s_{k+1},\varphi(\tilde{s}))\right)\end{split}$
(32)

We define
$\mu_{\mathtt{future}}(\operatorname{d}\\!{}g^{\prime}|s,s^{\prime},g)\mathrel{\mathop{:}}=p_{L}(0)\delta_{\varphi(s)}(\operatorname{d}\\!{}g^{\prime})+\sum_{l\geqslant
1}p_{L}(l)\varphi_{\ast}(\pi_{\exp}\ast P)^{l-1}(g^{\prime}|s^{\prime},g)$,
where $\varphi_{\ast}$ is the _push-forward_ on measures, and we have:

$\displaystyle\mathbb{E}_{\tau,U,K,L}$
$\displaystyle\left[f(\Phi(\tau,U,K,L))|U=1\right]=$ (33)
$\displaystyle=\sum_{k}p_{K}(k)\int_{g,s_{0},a_{0},...,s_{K+1},\tilde{s}}\rho(g,s_{0},a_{0},...,s_{k+1})\mu_{\mathtt{future}}(g^{\prime}|s_{k},s_{k+1},g)f(s_{k},a_{k},s_{k+1},g^{\prime})$
(34)
$\displaystyle=\int_{s,a,s^{\prime},g^{\prime}}\left(\int_{g}\rho_{\mathcal{G}}(g)\nu(s|g)\pi_{\mathrm{expl}}(a|s,g)\mu_{\mathtt{future}}(g^{\prime}|s,s^{\prime},g)\right)P(s^{\prime}|s,a)f(s,a,s^{\prime},g^{\prime}).$
(35)

Therefore,

$\mu_{\mathrm{HER}}(s,a,s^{\prime},g)=(1-\alpha)\rho_{\mathcal{G}}(g)\nu(s|g)\pi_{\mathrm{expl}}(a|s,g)P(s^{\prime}|s,a)+\alpha\left(\int_{\tilde{g}}\rho_{\mathcal{G}}(\tilde{g})\nu(s|\tilde{g})\pi_{\mathrm{expl}}(a|s,\tilde{g})\mu_{\mathtt{future}}(g|s,s^{\prime},\tilde{g})\right)P(s^{\prime}|s,a)$
(36)

We now use the deterministic hypothesis. We know that for every $s,a$,
$P(\operatorname{d}\\!{}s^{\prime}|s,a)=\delta_{\psi(s,a)}(\operatorname{d}\\!{}s^{\prime})$.
We have, for any $s,a$:

$\displaystyle
P(\operatorname{d}\\!{}s^{\prime}|s,a)\mu_{\mathtt{future}}(g|s,s^{\prime},\tilde{g})$
$\displaystyle=\delta_{\psi(s,a)}(\operatorname{d}\\!{}s^{\prime})\mu_{\mathtt{future}}(g|s,s^{\prime},\tilde{g})$
(37)
$\displaystyle=\delta_{\psi(s,a)}(\operatorname{d}\\!{}s^{\prime})\mu_{\mathtt{future}}(g|s,\psi(s,a),\tilde{g})$
(38)

Therefore:

$\displaystyle\mu_{\mathrm{HER}}(s,a,s^{\prime},g)=$ (39)
$\displaystyle=(1-\alpha)\rho_{\mathcal{G}}(g)\nu(s|g)\pi_{\mathrm{expl}}(a|s,g)P(s^{\prime}|s,a)+\alpha\left(\int_{\tilde{g}}\rho_{\mathcal{G}}(\tilde{g})\nu(s|\tilde{g})\pi_{\mathrm{expl}}(a|s,\tilde{g})\mu_{\mathtt{future}}(g|s,\psi(s,a),\tilde{g})\right)P(s^{\prime}|s,a)$
(40) $\displaystyle=\tilde{\mu}(s,a,g)P(s^{\prime}|s,a)$ (41)

where

$\tilde{\mu}(s,a,g)\mathrel{\mathop{:}}=(1-\alpha)\rho_{\mathcal{G}}(g)\nu(s,g)\pi_{\mathrm{expl}}(a|s,g)+\alpha\left(\int_{\tilde{g}}\rho_{\mathcal{G}}(g)\nu(s|\tilde{g})\pi_{\mathrm{expl}}(a|s,\tilde{g})\mu_{\mathtt{future}}(g|s,\psi(s,a),\tilde{g})\right)$

Therefore:

$\displaystyle\mathbb{E}\left[\widehat{\delta\theta_{\mathrm{HER}}}\right]$
$\displaystyle=\partial_{\theta}\int_{s,a,s^{\prime},g}\tilde{\mu}(s,a,g)P(s^{\prime}|s,a)(Q(s,a,g)-R(s,g^{\prime})-\gamma\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},g))^{2}$
(42)
$\displaystyle=\partial_{\theta}\int_{s,a,s^{\prime},g}\tilde{\mu}(s,a,g)\delta_{\psi(s,a)}(s^{\prime})(Q(s,a,g)-R(s,g^{\prime})-\gamma\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},g))^{2}$
(43)
$\displaystyle=\partial_{\theta}\int_{s,a,s^{\prime},g}\tilde{\mu}(s,a,g)(Q(s,a,g)-R(s,g)-\gamma\sup_{a^{\prime}}Q(\psi(s,a),a^{\prime},g))^{2}$
(44)
$\displaystyle=\partial_{\theta}\int_{s,a,g}\tilde{\mu}(s,a,g)(Q(s,a,g)-R(s,g)-\gamma\mathbb{E}_{s^{\prime}\sim
P(\operatorname{d}\\!{}s^{\prime}|s,a)}\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},g))^{2}$
(45)
$\displaystyle=\partial_{\theta}\int_{s,a,g}\tilde{\mu}(s,a,g)(Q(s,a,g)-T\cdot
Q(s,a,g))^{2}$ (46)

We define $\|Q\|_{\tilde{\mu}}$ as:

$\displaystyle\|Q\|_{\tilde{\mu}}^{2}\mathrel{\mathop{:}}=\int_{s,a,g}\tilde{\mu}(s,a,g)Q(s,a,g)^{2}.$
(47)

We now prove that $\|.\|_{\tilde{\mu}}$ is a norm for the space of continuous
functions on $\mathcal{S}\times\mathcal{A}\times\mathcal{G}$. This is
equivalent to showing that the support of the probability measure
$\tilde{\mu}$, $\mathrm{supp}(\tilde{\mu})$ is equal to
$\mathcal{S}\times\mathcal{A}\times\mathcal{G}$. Because
$\tilde{\mu}(s,a,g)\geqslant(1-\alpha)\rho_{\mathcal{G}}(g)\nu(s|g)\pi_{\mathrm{expl}}(a|s,g)$,
we know that
$\mathrm{supp}(\rho_{\mathcal{G}}(g)\nu(s|g)\pi_{\mathrm{expl}}(a|s,g))\subset\mathrm{supp}(\tilde{\mu})$.
Since for every $s,g$,
$\mathrm{supp}(\pi_{\mathrm{expl}}(a|s,g))=\mathcal{A}$,
$\mathrm{supp}(\rho_{\mathcal{G}}(g)\nu(s|g)\pi_{\mathrm{expl}}(a|s,g))=\mathrm{supp}(\rho_{\mathcal{G}}(g)\nu(s|g))\times\mathcal{A}$.
Moreover, $\mathrm{supp}\rho_{\mathcal{G}}=\mathcal{G}$. Therefore, we only
need to prove that for every $g$, $\mathrm{supp}(\nu(.|g))=\mathcal{S}$.

Let $g\in\mathcal{G}$. Because of the definition of $\nu$ and because
$p_{K}(k)>0$ for every $k$, we have
$\mathrm{supp}(\nu(s|g))=\bigcup_{k\geqslant
0,s_{0}\in\mathcal{S}}\mathrm{supp}\left((P^{\pi_{\mathrm{expl}}})^{k}(s|s_{0},g)\right)$.

We define the function $\Psi:\mathcal{S}\times\left(\cup_{k\geqslant
1}\mathcal{A}^{k}\right)\rightarrow\mathcal{S}$, corresponding to the action
of sequences of action , as follows: for every $a$, $\Psi(s,a)=\psi(s,a)$, and
for every $k$, $(a_{1},...,a_{k})\in\mathcal{A}^{k}$,
$\Psi(s,(a_{1},...,a_{k+1}))\mathrel{\mathop{:}}=\psi(\Psi(s,(a_{1},...,a_{k})),a_{k+1})$.
$\Psi$ is continuous. Moreover, we assumed that for any pair of states
$(s,s^{\prime})$, there is $k\geqslant 0$ and a sequence of actions
$(a_{0},...,a_{k})$ such that applying this sequence of actions from $s$ leads
to $s^{\prime}$. This means that for every $s$, $\Psi(s,.)$ is a surjective
continuous function.

Moreover, with

$\displaystyle\mathrm{supp}(P^{\pi_{\mathrm{expl}}})^{k+1}(s|s_{0},g)$
$\displaystyle=\cup_{s\in\mathrm{supp}(P^{\pi_{\mathrm{expl}}})^{k}(s|s_{0},g)}\mathrm{supp}\left(\psi(s,\cdot)_{\ast}\pi_{\mathrm{expl}}(.|s,g)\right)$
(48)
$\displaystyle\supseteq\cup_{s\in\mathrm{supp}(P^{\pi_{\mathrm{expl}}})^{k}(s|s_{0},g)}\left(\psi(s,\mathrm{supp}(\pi_{\mathrm{expl}}(.|s,g)))\right)$
(49)

by using the continuity of $\psi(s,.)$. Then:

$\displaystyle\mathrm{supp}(P^{\pi_{\mathrm{expl}}})^{k+1}(s|s_{0},g)$
$\displaystyle\supseteq\cup_{s\in\mathrm{supp}(P^{\pi_{\mathrm{expl}}})^{k}(s|s_{0},g)}\left(\psi(s,\mathcal{A})\right)$
(50)
$\displaystyle=\psi(\mathrm{supp}(P^{\pi_{\mathrm{expl}}})^{k}(s|s_{0},g)\times\mathcal{A})$
(51)

By induction, we have:
$\mathrm{supp}(P^{\pi_{\mathrm{expl}}})^{k}(s|s_{0},g)\supseteq\Psi(s,\mathcal{A}^{k})$.
Therefore:

$\displaystyle\mathrm{supp}(\nu(s|g))$ $\displaystyle=\bigcup_{k\geqslant
0,s_{0}\in\mathcal{S}}\mathrm{supp}(P^{\pi_{\mathrm{expl}}})^{k}(s|s_{0},g)$
(52) $\displaystyle\supseteq\bigcup_{k\geqslant
0,s_{0}\in\mathcal{S}}\Psi(s_{0},\mathcal{A}^{k})$ (53)
$\displaystyle=\bigcup_{s_{0}\in\mathcal{S}}\Psi(s_{0},\bigcup_{k\geqslant
0}\mathcal{A}^{k})$ (54) $\displaystyle=\mathcal{S}$ (55)

This concludes the proof. The main property we use in the theorem is that
$\mu_{\mathtt{future}}(g^{\prime}|s,s^{\prime},g)$ is independant of
$s^{\prime}$. Therefore, a simple way to remove HER bias is to define
$p_{L}(l)=\mathbbm{1}_{l=0}$. Still, this would not remove the issue of
vanishing rewards, since the fixed point of HER are the same than those of
UVFA.

∎

In the following, we will use again the results derived above. In particular,
we know that:

$\mathbb{E}\left[\widehat{\delta\theta}_{\text{HER}}\right]=\mathbb{E}_{(s,a,s^{\prime},g)\sim\mu_{\mathrm{HER}}}\left[\partial_{\theta}\frac{1}{2}(Q_{\theta}(s,a,g)-R(s,g)-\gamma\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},g))^{2}\right]$
(56)

with

$\displaystyle\mu_{\mathrm{HER}}(s,a,s^{\prime},g)$
$\displaystyle=(1-\alpha)\rho_{\mathcal{G}}(g)\nu(s|g)\pi_{\mathrm{expl}}(a|s,g)P(s^{\prime}|s,a)+\alpha\left(\int_{\tilde{g}}\rho_{\mathcal{G}}(\tilde{g})\nu(s|\tilde{g})\pi_{\mathrm{expl}}(a|s,\tilde{g})\mu_{\mathtt{future}}(g|s^{\prime},\tilde{g})\right)P(s^{\prime}|s,a)$
(57) $\displaystyle\mu_{\mathtt{future}}(g^{\prime}|s^{\prime},g)$
$\displaystyle=\sum_{l}p_{L}(l)\varphi_{\ast}(\pi_{\exp}\ast
P)^{l}(g^{\prime}|s^{\prime},g)$ (58) $\displaystyle\nu(s|g)$
$\displaystyle=\rho_{\mathcal{G}}(g)\int_{s_{0}}\rho_{0}(s_{0}|g)\sum_{k}p_{K}(k)(\pi_{\exp}\ast
P)^{k}(s|s_{0},g)$ (59)

###  B.2 Proof of HER bias

Let $\mathcal{M}=\langle\mathcal{S},\mathcal{G},\mathcal{A},P,R,\gamma\rangle$
be a multi-goal finite Markov Decision Process, with $\mathcal{G}=\mathcal{S}$
and $R(s,g)=\mathbbm{1}_{s=g}$. We define $S=|\mathcal{S}|$ the number of
states.

Let $\tilde{\mathcal{M}}$ be the augmented MDP with a _freeze_ action
$a^{\ast}$, defined as:

  * •

The augmented state space $\tilde{\mathcal{S}}=\mathcal{S}\times\\{0,1\\}$,
where $\tilde{s}=(s,x)$ is said to be frozen if $x=1$.

  * •

The augmented action space
$\tilde{\mathcal{A}}=\mathcal{A}\cup\\{a^{\ast}\\}$, where $a^{\ast}$ is the
_freeze_ action.

  * •

The goal space does not change
($\tilde{\mathcal{G}}=\mathcal{G}=\mathcal{S}$). For an augmented state
$\tilde{s}=(s,x)$, the reward is
$\tilde{R}(\tilde{s},g)=\tilde{R}((s,x),g)=R(s,g)$

  * •

If $\tilde{s}=(s,x)$ and $\tilde{s}^{\prime}=(s^{\prime},x^{\prime})$ are two
augmented states, the transition operator
$\tilde{P}(\tilde{s}^{\prime}|\tilde{s},a)$:

    * –

If the state is frozen ($x=1$), the agent can’t move:
$\tilde{P}((s^{\prime},y)|(s,x),a)=\mathbbm{1}_{s^{\prime}=s}\mathbbm{1}_{y=1}$

    * –

If the state is not frozen ($x=0$) and $a=a^{\ast}$, the agent is sent to a
uniformly random frozen state:
$\tilde{P}((s^{\prime},y)|(s,0),a)=\mathbbm{1}_{y=1}\frac{1}{\mathcal{S}}$

    * –

Else, the dynamic is the same than for $\mathcal{M}$: if $x=0$ and $a\neq
a^{\ast}$, then
$P((s^{\prime},y)|(s,0),a)=\mathbbm{1}_{y=0}P(s^{\prime}|s,a)$.

We can now prove the existence of MDPs such that HER will be biased in these
environments.

###### Theorem 9 (Formal statement of Theorem 1).

Let $\mathcal{M}$ be a finite MDP, and $\tilde{\mathcal{M}}$ the augmented MDP
with the freeze action $a^{\ast}$ defined above. We assume that for every
$s,a,g$ the exploration policy satisfies $\pi_{\mathrm{expl}}(a|s,g)>0$, and
that for every every $s,g$, $\nu(s|g)>0$, where $\nu$ is defined in equation
(29). This means that from the given distribution, every state $s$ has a non-
zero probability of being reached when following the exploration policy
conditioned by $g$: $\pi_{\mathrm{expl}}(a|s,g)$.

Let $Q_{\infty}$ be a fixed point of tabular HER, and $Q^{\ast}$ the true
optimal Q-function. Then, for every unfrozen state $(s,0)$ and goal $g$, HER
overstimates the value of action $a^{\ast}$:

$Q_{\infty}((s,0),a^{\ast},g)>Q^{\ast}((s,0),a^{\ast},g)$ (60)

###### Proof.

The principle of the proof is the following. First, we prove that for _frozen_
states $\tilde{s}=(s,1)$, HER converge converge to the true value
$Q_{\infty}(\tilde{s},a,g)=Q^{\ast}(\tilde{s},a,g)$. Then, we compute the
action-value of action $a^{\ast}$ for every _unfrozen_ state for the true
$Q^{\ast}$ and for the fixed point $Q_{\infty}$. HER samples transitions
$((s,0),a^{\ast},(s^{\prime},1),g)$. Let us consider the law of $s^{\prime}$
knowing $s,a^{\ast},g$: with probability $(1-\alpha)$ the goal $g$ was re-
sampled from the future sampling strategy, therefore, because after $a^{\ast}$
the position will be frozen, we know that $s^{\prime}=g$, the goal is reached
and the final return is $O(\frac{1}{1-\gamma})$. With probability $\alpha$,
the goal $g$ the original goal, the law of $s^{\prime}$ is uniform, and the
return is of order $O(\frac{1}{S(1-\gamma)})$. Therefore, when estimating the
return after action $a^{\ast}$ with HER, the computed value will be of order
$O(\frac{(1-\alpha)}{1-\gamma})$, while the true value is of order
$O(\frac{1}{S(1-\gamma)})$.

We now prove the theorem. We consider $Q_{\infty}$, a fixed point of the
algorithm, which means that starting from $Q_{\infty}$, the stochastic update
defined by HER has mean $0$: $\mathbb{E}\left[\widehat{\delta
Q}_{\text{HER}}\right]=0$. We know that

$\displaystyle\mathbb{E}\left[\widehat{\delta Q}_{\text{HER}}\right]$
$\displaystyle=\mathbb{E}_{(s,a,s^{\prime},g)\sim\mu_{\mathrm{HER}}}\left[\partial_{\theta}\frac{1}{2}(Q_{\theta}(s,a,g)-R(s,g)-\gamma\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},g))^{2}\right]$
(61)
$\displaystyle=\mathbb{E}_{(s,a,s^{\prime},g)\sim\mu_{\mathrm{HER}}}\left[E_{s,a,g}(Q_{\theta}(s,a,g)-R(s,g)-\gamma\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},g))\right],$
(62)

where $(E_{s,a,g})$ is the canonical basis of the tabular model. Therefore,
for every $(s,a,g)$ (because $\mu_{\mathrm{HER}}(s,a,g)>0$ for every
$(s,a,g)$), we have:

$\displaystyle
Q_{\infty}(s,a,g)=R(s,g)+\gamma\mathbb{E}_{s^{\prime}\sim\mu_{\mathrm{HER}}(s^{\prime}|s,a,g)}\left[\sup_{a^{\prime}}Q_{\infty}(s^{\prime},a^{\prime},g)\right]$
(63)

First, we prove that the values of frozen states $Q_{\infty}((s,1),a,g)$ is
equal to the true optimal Q-values. In that case,
$\tilde{P}(\tilde{s}^{\prime}|(s,1),a)=\delta_{(s,1)}(\tilde{s}^{\prime})$ we
can check that
$\mu_{\mathrm{HER}}(\tilde{s}^{\prime}|(s,1),a,g)=\delta_{(s,1)}(\tilde{s}^{\prime})$.
Therefore:

$\displaystyle
Q_{\infty}((s,1),a,g)=R(s,g)+\gamma\sup_{a^{\prime}}Q_{\infty}((s,1),a^{\prime},g)$
(64)

Therefore for every $s,a,g$, $Q_{\infty}((s,1),a,g)=\frac{1}{1-\gamma}R(s,g)$.

Then, we compute the values of $Q_{\infty}((s,0),a^{\ast},g)$, with the
_freeze_ action for an unfrozen state. We have:

$\displaystyle Q_{\infty}((s,0),a^{\ast},g)$
$\displaystyle=R(s,g)+\gamma\mathbb{E}_{(s^{\prime},y)\sim\mu_{\mathrm{HER}}((s^{\prime},y)|(s,0),a^{\ast},g)}\sup_{a^{\prime}}Q_{\infty}((s^{\prime},y),a^{\prime},g)$
(65)
$\displaystyle=R(s,g)+\frac{\gamma}{1-\gamma}\mathbb{E}_{(s^{\prime},y)\sim\mu_{\mathrm{HER}}((s^{\prime},1)|s,a^{\ast},g)}\left[\mathbbm{1}_{s^{\prime}=g}\right]$
(66)
$\displaystyle=R(s,g)+\frac{\gamma}{1-\gamma}\mu_{\mathrm{HER}}((s^{\prime},y)=(g,1)|s,a,g)$
(67)

because $\mu_{\mathrm{HER}}((s^{\prime},y)|(s,0),a^{\ast},g)$ is non zero only
if $y=1$, and
$Q_{\infty}((s^{\prime},1),a^{\prime},g)=\frac{1}{1-\gamma}R(s^{\prime},g)=\frac{1}{1-\gamma}\mathbbm{1}_{s^{\prime}=g}$.
We now compute $\mu_{\mathrm{HER}}((s^{\prime},y)=(g,1)|s,a,g)$. We use that
$P((s^{\prime},y)|(s,0),a^{\ast})=\mathbbm{1}_{y=1}/S$, and
$\mu_{\mathtt{future}}(g|(s^{\prime},y))=\mathbbm{1}_{s^{\prime}}$ if $y=1$.

$\displaystyle\mu_{\mathrm{HER}}((s,0),a^{\ast},(s^{\prime},1),g)$
$\displaystyle=(1-\alpha)\mu_{0}((s,0),g)\pi_{\mathrm{expl}}(a^{\ast}|(s,0),g)\frac{1}{S}+\alpha\left(\int_{\tilde{g}}\mu_{0}((s,0),\tilde{g})\pi_{\mathrm{expl}}(a^{\ast}|(s,0),\tilde{g})\right)\frac{1}{S}\mathbbm{1}_{g=s^{\prime}}$
(68)

Therefore, for every $s^{\prime}\neq g$:
$\mu_{\mathrm{HER}}((s,0),a^{\ast},(s^{\prime},1),g)<\mu_{\mathrm{HER}}((s,0),a^{\ast},(g,1),g)$.
So:

$\displaystyle\sum_{s^{\prime}}\mu_{\mathrm{HER}}((s,0),a^{\ast},(s^{\prime},1),g)<S\mu_{\mathrm{HER}}((s,0),a^{\ast},(g,1),g)$
(69)

and finally
$\mu_{\mathrm{HER}}((s^{\prime},y)=(g,1)|(s,0),a^{\ast},g)>\frac{1}{S}$. Then
we have:

$\displaystyle Q_{\infty}((s,0),a^{\ast},g)>R(s,g)+\frac{\gamma}{S(1-\gamma)}$
(70)

On the contrary, we can easily check that for any policy $\pi$,
$Q^{\pi}((s,0),a^{\ast},g)=R(s,g)+\frac{\gamma}{S(1-\gamma)}$. In particular,
by taking $\pi=\pi^{\ast}$, we have:

$\displaystyle Q_{\infty}((s,0),a^{\ast},g)>Q^{\ast}((s,0),a^{\ast},g)$ (71)

∎

##  Appendix C Goal-dependent $Q$-functions in continuous spaces

###  C.1 Optimal Bellman Operator for action-value measures

With continuous states and goals, in a stochastic environment, the goal-
dependent optimal $Q$-function $Q^{\ast}_{\varepsilon}$ with reward
$R_{\varepsilon}(s,g)=\mathbbm{1}_{\|\varphi(s)-g\|\leqslant\varepsilon}$
vanishes when $\varepsilon\rightarrow 0$: the probability of exactly reaching
a goal state is usually $0$. Likewise, a direct application of TD would never
learn anything because rewards would likely never be observed.

Instead, the goal-dependent $Q$-function is a _measure_ over goals.
Intuitively, for every infinitesimally small set of goals
$\operatorname{d}\\!{}g$, the quantity $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$
is the expected amount of time spent in $\operatorname{d}\\!{}g$ by the policy
that tries to maximize time spent in $\operatorname{d}\\!{}g$, starting at
$(s,a)$.

Formally, for every state-action $(s,a)$, $Q^{\ast}(s,a,\cdot)$ is a measure
over goals, solution to the Bellman equation

$Q^{\ast}(s,a,\operatorname{d}\\!{}g)=\delta_{\varphi(s)}(\operatorname{d}\\!{}g)+\gamma\,\mathbb{E}_{s^{\prime}\sim
P(\operatorname{d}\\!{}s^{\prime}|s,a)}\max_{a^{\prime}}Q^{\ast}(s^{\prime},a^{\prime},\operatorname{d}\\!{}g)$
(72)

where, as above, $\varphi\colon S\to G$ is the function defining the target
features, and where $\delta_{\varphi(s)}$ is the Dirac measure at $\varphi(s)$
in goal space. This is an equality between measures, and the supremum is a
supremum of measures (Bogachev, 2007, Section 4.7).

Existence and uniqueness of solutions, and a formal derivation of a TD
algorithm, are nontrivial in this setting. Uniqueness never holds without
restrictions: the infinite measure always solves (72). But it is not possible
to restrict ourselves to finite-mass measures, because sometimes the solution
we want has infinite mass. The need to deal with possibly infinite measures
restricts the use of uniqueness proofs by $\gamma$-contractivity arguments in
some norm.

Intuitively, the total mass $Q^{\ast}(s,a,\mathcal{G})$ of the goal state
$\mathcal{G}$ describes how much different action sequences result in non-
overlapping distributions of states. If the state space $\mathcal{A}$ is
finite and $|\mathcal{A}|=A$, the total mass of the horizon-$t$ part of the
$Q^{\ast}$-function can be as much as $\gamma^{t}A^{t}$: this is realized when
every possible sequence of $t$ actions leads to a disjoint part of the state
of goals. In Appendix C.3 we provide a simple continuous MDP in which every
action sequence leads to a distinct state: as there are an infinite number of
action sequences when $t\to\infty$, the total mass $Q^{\ast}(s,a,\mathcal{G})$
is infinite.

We still prove the existence of a canonical solution, equal both to the
_smallest_ solution and to the limit of the horizon-$t$ solution when
$t\to\infty$.

###### Theorem 10 (Formal statement of Theorem 3).

Let $\mathcal{Q}$ be the set of functions from $\mathcal{S}\times\mathcal{A}$
into positive measures over $\mathcal{G}$. Assume the set of actions
$\mathcal{A}$ is countable. Let $T$ be the Bellman operator mapping
$Q\in\mathcal{Q}$ to $T\cdot Q$ with

$T\cdot
Q(s,a,\cdot)\mathrel{\mathop{:}}=\delta_{\varphi(s)}(\cdot)+\gamma\,\mathbb{E}_{s^{\prime}\sim
P(\operatorname{d}\\!{}s^{\prime}|s,a)}\sup_{a^{\prime}}Q(s^{\prime},a^{\prime},\cdot)$
(73)

where the supremum is a supremum of measures and $\delta_{\varphi(s)}$ is the
Dirac measure at $\varphi(s)\in\mathcal{G}$.

Let $\mathbf{0}\in\mathcal{Q}$ be the measure $0$.

Let $Q_{t}\mathrel{\mathop{:}}=T^{t}\mathbf{0}$. (By expanding the definition
of $T$, this is the solution of the expectimax problem at time horizon $t$.)
Then when $t\to\infty$, for every state-action $(s,a)$ and for every
measurable set $G\subset\mathcal{G}$, $Q_{t}(s,a,G)$ converges to a finite or
infinite limit $Q^{\ast}(s,a,G)$. This limit $Q^{\ast}$ is an element of
$\mathcal{Q}$ and solves the Bellman equation $TQ^{\ast}=Q^{\ast}$. It is the
smallest such solution. In finite state spaces, it is the only solution with
finite mass. Moreover, for any goal-dependent policy $\pi$, its Bellman
operator $T^{\pi}$ and $Q$-value
$Q^{\pi}\mathrel{\mathop{:}}=\lim_{t\to\infty}(T^{\pi})^{t}\mathbf{0}$ can be
defined similarly (see equation (78)) and satisfy $Q^{\pi}\leqslant Q^{\ast}$
as measures.

###### Proof.

Assume the action space $\mathcal{A}$ is countable. Let $\mathcal{Q}$ be the
set of measurable functions from $\mathcal{S}\times\mathcal{A}$ to the set of
measures on $\mathcal{G}$.

For $Q_{1}$ and $Q_{2}$ in $\mathcal{Q}$, we write $Q_{1}\leqslant Q_{2}$ if
$Q_{1}(s,a,X)\leqslant Q_{2}(s,a,X)$ for any state-action $(s,a)$ and
measurable set $X\subset\mathcal{G}$. The Bellman operator of Definition 73
acts on $\mathcal{Q}$ and is obviously monotonous: if $Q_{1}\leqslant Q_{2}$
then $TQ_{1}\leqslant TQ_{2}$.

Since the zero measure $\mathbf{0}\in\mathcal{Q}$ is the smallest measure, we
have $T\mathbf{0}\geqslant\mathbf{0}$. Since $T$ is monotonous, by induction
we have $T^{t+1}\mathbf{0}\geqslant T^{t}\mathbf{0}$ for any $t\geqslant 0$.
Thus, the $(T^{t}\mathbf{0})_{t\geqslant 0}$ form an increasing sequence of
measures. Therefore, for every state-action $(s,a)$ and measurable set $X$,
the sequence $(T^{t}\mathbf{0})(s,a,X)$ is increasing, and thus converges to a
limit. We denote this limit by $Q^{\ast}(s,a,X)$. We have to prove that
$Q^{\ast}\in\mathcal{Q}$, namely, that for each $(s,a)$, $Q^{\ast}(s,a,\cdot)$
is a measure. The only non-trivial point is $\sigma$-additivity.

Denote $Q_{t}\mathrel{\mathop{:}}=T^{t}\mathbf{0}$. If $(X_{i})$ is a
countable collection of disjoint measurable sets, we have

$Q^{\ast}(s,a,\cup_{i}X_{i})=\lim_{t\to\infty}Q_{t}(s,a,\cup_{i}X_{i})=\lim_{t\to\infty}\sum_{i}Q_{t}(s,a,X_{i})\\\
=\sum_{i}\lim_{t\to\infty}Q_{t}(s,a,X_{i})=\sum_{i}Q^{\ast}(s,a,X_{i})$ (74)

where the limit commutes with the sum thanks to the monotone convergence
theorem, using that $Q_{t}$ is non-decreasing. Therefore, $Q^{\ast}$ is a
measure.

Let us prove that $TQ^{\ast}=Q^{\ast}$. We have

$TQ^{\ast}(s,a,\cdot)=\delta_{\varphi(s)}+\gamma\mathbb{E}_{s^{\prime}\sim
P(s^{\prime}|s,a)}\sup_{a^{\prime}}Q^{\ast}(s^{\prime},a^{\prime},\cdot)$ (75)

by definition. For any $s^{\prime}$, denote
$\tilde{Q}_{t}(s^{\prime},\cdot)\mathrel{\mathop{:}}=\sup_{a^{\prime}}Q_{t}(s^{\prime},a^{\prime},\cdot)$
where the supremum is as measures over $\mathcal{G}$. Since $Q_{t}$ is non-
decreasing, so is $\tilde{Q}_{t}$.

For any state $s^{\prime}$, we have

$\sup_{a^{\prime}}Q^{\ast}(s^{\prime},a^{\prime},\cdot)=\sup_{a^{\prime}}\sup_{t}Q_{t}(s^{\prime},a^{\prime},\cdot)=\sup_{t}\sup_{a^{\prime}}Q_{t}(s^{\prime},a^{\prime},\cdot)=\sup_{t}\tilde{Q}_{t}(s^{\prime},\cdot)$
(76)

since supremums commute. Now, since $\tilde{Q}_{t}$ is non-decreasing, thanks
to the monotone convergence theorem, the supremum commutes with integration
over $s^{\prime}\sim P(s^{\prime}|s,a)$ (which does not depend on $t$),
namely,

$\mathbb{E}_{s^{\prime}\sim
P(s^{\prime}|s,a)}\sup_{a^{\prime}}Q^{\ast}(s^{\prime},a^{\prime},\cdot)=\mathbb{E}_{s^{\prime}\sim
P(s^{\prime}|s,a)}\sup_{t}\tilde{Q}_{t}(s^{\prime},\cdot)\\\
=\sup_{t}\mathbb{E}_{s^{\prime}\sim
P(s^{\prime}|s,a)}\tilde{Q}_{t}(s^{\prime},\cdot)=\sup_{t}\mathbb{E}_{s^{\prime}\sim
P(s^{\prime}|s,a)}\sup_{a^{\prime}}Q_{t}(s^{\prime},a^{\prime},\cdot)$ (77)

and so $TQ^{\ast}=\sup_{t}TQ_{t}$. Now, since $Q^{t}=T^{t}\mathbf{0}$, we have
$TQ^{t}=T^{t+1}\mathbf{0}$, so that $\sup_{t\geqslant
0}TQ^{t}=\sup_{t\geqslant 1}T^{t}\mathbf{0}=Q^{\ast}$. So $Q^{\ast}$ is a
fixed point of $T$.

Let us prove that $Q^{\ast}$ is the smallest such fixed point. Let
$Q^{\prime}$ such that $TQ^{\prime}=Q^{\prime}$. Since $\mathbf{0}\leqslant
Q^{\prime}$ and $T$ is monotonous, we have $T\mathbf{0}\leqslant
TQ^{\prime}=Q^{\prime}$. By induction, $T^{t}\mathbf{0}\leqslant Q^{\prime}$
for any $t\geqslant 0$. Therefore, $\sup_{t}T^{t}\mathbf{0}\leqslant
Q^{\prime}$, i.e., $Q^{\ast}\leqslant Q^{\prime}$.

The statement for finite state spaces reduces to the classical uniqueness
property of the usual $Q$ function, separately for each goal state.

Optimality of the policy is proved by following classical arguments. Let
$\pi(a|s,g)$ be any goal-dependent policy and let $Q\in\mathcal{Q}$. Define
the Bellman operator associated to $\pi$ by

$(T^{\pi}Q)(s,a,\cdot)\mathrel{\mathop{:}}=\delta_{s}+\gamma\mathbb{E}_{s^{\prime}\sim
P(s^{\prime}|s,a)}\sum_{a^{\prime}}(\pi\ast Q)(s^{\prime},a^{\prime},\cdot)$
(78)

where for each action $a$, the measure $(\pi\ast Q)\in\mathcal{Q}$ is defined
via $(\pi\ast Q)(s^{\prime},a^{\prime},X)\mathrel{\mathop{:}}=\int_{g\in
X}\pi(a^{\prime}|s^{\prime},g)Q(s^{\prime},a^{\prime},\operatorname{d}\\!{}g)$,
so that the sum of $(\pi\ast Q)$ over all actions $a^{\prime}$ represents the
expected value of $Q(s^{\prime},a^{\prime},\cdot)$ under the goal-dependent
policy $\pi$; this formulation allows the policy to depend on the goal.

Since $\pi$ is a probability distribution, we have

$\sum_{a^{\prime}}(\pi\ast
Q)(s^{\prime},a^{\prime},X)\leqslant\max_{a^{\prime}}Q(s^{\prime},a^{\prime},X)$
(79)

where the right-hand-side is a maximum of measures (thus selecting the best
$a^{\prime}$ for each goal): this is clear from decomposing $X$ into the
components where each action $a^{\prime}$ is optimal.

Therefore, for any $Q\in\mathcal{Q}$, we have the inequality of measures

$T^{\pi}Q\leqslant TQ$ (80)

where $T$ is the optimal Bellman operator from above. Since the latter is
monotonous over $Q\in\mathcal{Q}$, for any $Q,Q^{\prime}\in\mathcal{Q}$ with
$Q\leqslant Q^{\prime}$, we have $T^{\pi}Q\leqslant TQ^{\prime}$.

Consequently, by induction, $(T^{\pi})^{t}\mathbf{0}\leqslant T^{t}\mathbf{0}$
for any horizon $t\geqslant 0$. The monotonous limit
$Q^{\pi}\mathrel{\mathop{:}}=\lim_{t\to\infty}(T^{\pi})^{t}\mathbf{0}$ exists
for the same reasons as $T^{t}\mathbf{0}$, representing the $Q$-function
(measure) of policy $\pi$. Therefore,
$Q^{\pi}=\lim_{t\to\infty}(T^{\pi})^{t}\mathbf{0}\leqslant\lim_{t\to\infty}T^{t}\mathbf{0}=Q^{\ast}$.
This proves that the policy $\pi$ has returns no greater than $Q^{\ast}$.

∎

###  C.2 Parametric goal-dependent $Q$-learning.

In this section, we formally derive the $\delta\text{-}\mathrm{DQN}$ update
introduced in Section 3.2. Let us consider parametric models for $Q$:

$Q_{\theta}(s,a,\operatorname{d}\\!{}g)\mathrel{\mathop{:}}=q_{\theta}(s,a,g)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
(81)

and we will learn $q_{\theta}$. 111The factor $\rho_{\mathcal{G}}$, or some
other measure, is needed to get a well-defined object in continuous state
spaces. In discrete spaces, it results in an $g$-dependent scaling of the $Q$
function, which still has the same optimal policy for each $g$.

The resulting parametric update is off-policy: we assume access to a sampling
distribution
$(s,a,s^{\prime})\sim\rho_{\mathrm{SA}}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)P(\operatorname{d}\\!{}s^{\prime}|s,a)$
in a Markov decision. Typically, this can correspond to transitions
$(s_{k},a_{k},s_{k+1})$ from exploration trajectory with
$g\sim\rho_{\mathcal{G}}$, $s_{0}\sim\rho_{0}(.|g)$, then
$a_{t}\sim\pi_{\mathrm{expl}}(.|s_{t},g)$ and $s_{t+1}\sim P(.|s_{t},a_{t})$.
Here, our statement with a distribution $\rho_{\mathrm{SA}}$ is more general.
Given a measure-valued function of $(s,a)$, such as
$Q(s,a,\operatorname{d}\\!{}g)$, we define its norm as

$\left\lVert
Q\right\rVert^{2}_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}\mathrel{\mathop{:}}=\mathbb{E}_{(s,a)\sim\rho_{\mathrm{SA}},\,g\sim\rho_{\mathcal{G}}}[q(s,a,g)^{2}]$
(82)

where
$q(s,a,g)\mathrel{\mathop{:}}=Q(s,a,\operatorname{d}\\!{}g)/\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
is the density of $Q$ with respect to $\rho_{\mathcal{G}}$, if it exists
(otherwise the norm is infinite).

Let $Q_{\theta}=q_{\theta}(s,a,g)\rho(\operatorname{d}\\!{}g)$ be our current
estimate of $Q$, and
$Q_{\mathrm{tar}}(s,a,\operatorname{d}\\!{}g)=q_{\mathrm{tar}}(s,a,g)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
a target measure, we define the loss:

$J_{Q}(\theta)\mathrel{\mathop{:}}=\left\lVert Q_{\theta}-T\cdot
Q_{\mathrm{tar}}\right\rVert^{2}_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}$ (83)

where $T$ is the optimal Bellman operator, and our goal is to obtain an
unbiased estimate of $\partial J_{Q}(\theta)$. In the statement of Theorem 4,
there is a hidden mathematical subtlety with continuous states regarding the
norm $\left\lVert Q_{\theta}-T\cdot
Q_{\mathrm{tar}}\right\rVert^{2}_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}$.
Indeed,
$Q_{\theta}(s,a,\operatorname{d}\\!{}g)=q_{\theta}(s,a,g)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
is absolutely continuous with respect to $\rho_{\mathcal{G}}$, while $T\cdot
Q_{\mathrm{tar}}$ is not, due to the Dirac term
$\delta_{\varphi(s)}(\operatorname{d}\\!{}g)$. This makes the norm
$\left\lVert Q_{\theta}-T\cdot
Q_{\mathrm{tar}}\right\rVert^{2}_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}$
infinite (see its definition in (82)). However, the _gradient_ of this norm is
actually still well-defined. There are at least two ways to handle this
rigorously, which lead to the same result. It is possible to do the
computation in the finite state space case and observe that the resulting
gradient still makes sense in the continuous case (which can be obtained by a
limiting argument). The other way we will use here, is to observe that the
loss $J_{Q}(\theta)$ is equal to

$J_{Q}(\theta)=\frac{1}{2}\left\lVert
Q_{\theta}\right\rVert^{2}_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}-\langle
Q_{\theta},TQ_{\mathrm{tar}}\rangle_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}+\frac{1}{2}\left\lVert
T\cdot
Q_{\mathrm{tar}}\right\rVert^{2}_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}$ (84)

where

$\langle
Q_{1},Q_{2}\rangle_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}\mathrel{\mathop{:}}=\int_{s,a}Q_{1}(s,a,\operatorname{d}\\!{}g)Q_{2}(s,a,\operatorname{d}\\!{}g)\frac{1}{\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)}.$
(85)

Even though $\|Q_{1}-Q_{2}\|_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}$ is
finite only if $Q_{1}$ and $Q_{2}$ are both absolutely continuous with respect
to $\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$, the dot product $\langle
Q_{1},Q_{2}\rangle_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}$ is still defined
if only one of $Q_{1}$ or $Q_{2}$ is absolutely continuous. Therefore, we can
define:

$J^{\prime}_{Q}(\theta)=\frac{1}{2}\left\lVert
Q_{\theta}\right\rVert^{2}_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}-\langle
Q_{\theta},T\cdot
Q_{\mathrm{tar}}\rangle_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}$ (86)

For a given $Q_{\mathrm{tar}}$, $J^{\prime}_{Q}(\theta)$ and $J_{Q}(\theta)$
have the same minima and gradients, but $J^{\prime}_{Q}(\theta^{\prime})$ is
always well defined and finite. Namely, $J_{Q}$ and $J^{\prime}_{Q}$ differ by
a constant in the finite case, and by an “infinite constant” in the continuous
case. We will work with the loss $J^{\prime}_{Q}$, which is finite even in the
continuous case.

###### Theorem 11 (Formal statement of Theorem 4).

Let
$Q_{\theta}(s,a,\operatorname{d}\\!{}g)=q_{\theta}(s,a,g)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
be a current estimate of $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$. Let likewise
$Q_{\mathrm{tar}}(s,a,\operatorname{d}\\!{}g)=q_{\mathrm{tar}}(s,a,g)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
be a target $Q$-function. We consider the loss function
$J^{\prime}_{Q}(\theta)$ defined in equation (86).

We consider the following update to bring $Q_{\theta}$ closer to
$TQ_{\mathrm{tar}}$ with $T$ the optimal Bellman operator: Let
$(s,a,s^{\prime})\sim\rho_{SA}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)P(s^{\prime}|s,a)$
be samples of the environment and $g\sim\rho_{\mathcal{G}}$ sampled
independently. Let
$\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}(s,a,s^{\prime},g)$ be

$\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}(s,a,s^{\prime},g)\mathrel{\mathop{:}}=\partial_{\theta}q_{\theta}(s,a,\varphi(s))+\partial_{\theta}q_{\theta}(s,a,g)\left(\gamma\max_{a^{\prime}}q_{\mathrm{tar}}(s^{\prime},a^{\prime},g)-q_{\theta}(s,a,g)\right)$
(87)

Then $\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}$ is an unbiased
estimate of $\partial_{\theta}J^{\prime}_{Q}(\theta)$:
$\mathbb{E}\left[\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}\right]=-\partial_{\theta}J^{\prime}_{Q}(\theta)$.

In particular, the true optimal state-action measure $Q^{\ast}$ is a fixed
point of this update: if $Q_{\theta}=Q_{\mathrm{tar}}=Q^{\ast}$ then
$\mathbb{E}\left[\widehat{\delta\theta}_{\delta\text{-}\mathrm{DQN}}\right]=0$.

Here we have presented the update using a fixed “target network” with
parameter $\theta_{0}$ (typically a previous value of $\theta$), a common
practice for parametric $Q$-learning.

For this theorem, we sample goals $g$ independently of $(s,a,s^{\prime})$. In
practice, this could be a source of variance, as sampling goals far from the
current state should produce close-to-$0$ Q-values. If we instead sample goals
from a distribution $\mu(g|s,a)$, this introduces an implicit _scaling_ factor
$\alpha(s,g)$ to the reward. This is discussed in details and the end of
Appendix E.2 in the case of the $V$-function.

###### Proof.

By definition of the optimal Bellman operator $T$ and the target
$Q_{\mathrm{tar}}$, we have:

$\displaystyle TQ_{\mathrm{tar}}(s,a,\operatorname{d}\\!{}g)$
$\displaystyle=\delta_{\varphi(s)}(\operatorname{d}\\!{}g)+\gamma\,\mathbb{E}_{s^{\prime}\sim
P(s^{\prime}|s,a)}\left[\sup_{a^{\prime}}q_{\mathrm{tar}}(s^{\prime},a^{\prime},g)\right]\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
(88)

By definition of $J^{\prime}_{Q}(\theta)$ and of the norm
$\left\lVert\cdot\right\rVert_{\rho_{\mathrm{SA}},\rho_{\mathcal{G}}}$, we
have

$\displaystyle J^{\prime}_{Q}(\theta)$ $\displaystyle=\frac{1}{2}\left\lVert
Q_{\theta}\right\rVert^{2}_{\rho_{\mathrm{SA}},\rho}-\langle
Q_{\theta},TQ_{\mathrm{tar}}\rangle_{\rho_{\mathrm{SA}},\rho}$ (89)
$\displaystyle=\frac{1}{2}\int_{s,a,g}q_{\theta}^{2}(s,a,g)\rho_{\mathrm{SA}}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)\rho(\operatorname{d}\\!{}g)-\int_{s,a,g}q_{\theta}(s,a,g)(T\cdot
Q_{\mathrm{tar}})(s,a,\operatorname{d}\\!{}g)\rho_{\mathrm{SA}}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)$
(90)

Consequently,

$\displaystyle\partial_{\theta}J^{\prime}(\theta)$
$\displaystyle=\int_{s,a,g}\partial_{\theta}q_{\theta}(s,a,g)q_{\theta}(s,a,g)\rho_{\mathrm{SA}}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)-\int_{s,a,g}\partial_{\theta}q_{\theta}(s,a,g)TQ_{\mathrm{tar}}(s,a,\operatorname{d}\\!{}g)\rho_{\mathrm{SA}}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)$
(91)
$\displaystyle=\int_{s,a,g}\rho_{\mathrm{SA}}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)\partial_{\theta}q_{\theta}(s,a,g)\left(Q_{\theta}(s,a,\operatorname{d}\\!{}g)-TQ_{\mathrm{tar}}(s,a,\operatorname{d}\\!{}g)\right)$
(92)

assuming $q_{\theta}$ is smooth enough so that the derivative makes sense and
commutes with the integral.

Moreover, we have:

$TQ_{\mathrm{tar}}(s,a,\operatorname{d}\\!{}g)-Q_{\theta}(s,a,\operatorname{d}\\!{}g)=\delta_{\varphi(s)}(\operatorname{d}\\!{}g)+\gamma\,\mathbb{E}_{s^{\prime}\sim
P(s^{\prime}|s,a)}[\sup_{a^{\prime}}q_{\mathrm{tar}}(s^{\prime},a^{\prime},g)-q_{\theta}(s,a,g)]\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)$
(93)

Therefore,

$\displaystyle\begin{split}-\partial_{\theta}J^{\prime}(\theta)=&\int_{s,a}\rho_{\mathrm{SA}}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)\partial_{\theta}q_{\theta}(s,a,g)\delta_{\varphi(s)}(\operatorname{d}\\!{}g)\\\
&+\int_{s,a,g}\rho_{\mathrm{SA}}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)\left(\gamma\,\mathbb{E}_{s^{\prime}\sim
P(s^{\prime}|s,a)}[\sup_{a^{\prime}}q_{\theta_{0}}(s^{\prime},a^{\prime},g)-q_{\theta}(s,a,g)]\right)\end{split}$
(94)
$\displaystyle\begin{split}=&\int_{s,a}\rho_{\mathrm{SA}}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)\partial_{\theta}q_{\theta}(s,a,\varphi(s))\\\
&+\int_{s,a,g}\rho_{\mathrm{SA}}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)\left(\gamma\,\mathbb{E}_{s^{\prime}\sim
P(s^{\prime}|s,a)}[\sup_{a^{\prime}}q_{\theta_{0}}(s^{\prime},a^{\prime},g)-q_{\theta}(s,a,g)]\right)\end{split}$
(95)

By definition of $\widehat{\delta\theta_{Q}}$, we have:

$\displaystyle\begin{split}\mathbb{E}_{s,a\sim\rho_{\mathrm{SA}}}\left[\widehat{\delta\theta_{Q}}\right]=&\mathbb{E}_{s,a\sim\rho_{\mathrm{SA}},g\sim\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)}\left[\partial_{\theta}q_{\theta}(s,a,\varphi(s))\right]\\\
&+\mathbb{E}_{s,a\sim\rho_{\mathrm{SA}},g\sim\rho_{\mathcal{G}}(\operatorname{d}\\!{}g)}\left[\partial_{\theta}q_{\theta}(s,a,g)\left(\gamma\sup_{a^{\prime}}q_{\theta_{0}}(s^{\prime},a^{\prime},g)-q_{\theta}(s,a,g)\right)\right]\end{split}$
(96) $\displaystyle=-\partial_{\theta}J^{\prime}(\theta)$ (97)

Finally, if $Q_{\mathrm{tar}}=Q_{\theta}=Q^{\ast}$, then
$TQ_{\mathrm{tar}}=Q^{\ast}$ and:

$\displaystyle\partial
J^{\prime}_{Q}(\theta)=\int_{s,a,g}\rho_{\mathrm{SA}}(\operatorname{d}\\!{}s,\operatorname{d}\\!{}a)\partial_{\theta}q_{\theta}(s,a,g)\left(Q_{\theta}(s,a,\operatorname{d}\\!{}g)-TQ_{\mathrm{tar}}(s,a,\operatorname{d}\\!{}g)\right)$
(98) $\displaystyle=0$ (99)

∎

###  C.3 Examples of MDPs with Infinite Mass for $Q^{\ast}$

Here are two simple examples of MDPs with finite action space, for which the
mass of the goal-dependent $Q$-measure $Q^{\ast}(s,a,\operatorname{d}\\!{}g)$
is infinite. The first has discrete states, the second, continuous ones.

Take for $\mathcal{S}$ an infinite rooted dyadic tree, namely,
$\mathcal{S}=\\{\varnothing,0,1,00,01,\ldots\\}$ the set of binary strings of
finite length $k\geqslant 0$, and $\mathcal{G}=\mathcal{S}$. Consider the two
actions “add a $0$ at the end” and “add a $1$ at the end”. Then, for every
state $s$, $Q^{\ast}(s,a,\cdot)$ is a measure that gives mass $\gamma^{k}$ to
all states $g$ that are extensions of $s$ by a length-$k$ string that starts
with $a$. Thus, its mass is $1+\sum_{k\geqslant 1}\gamma^{k}2^{k-1}$. This is
infinite as soon as $\gamma\geqslant 1/2$. This extends to any number of
actions by considering higher-degree trees.

A similar example with continuous states is obtained as follows. Let
$\mathcal{S}=[0;1)\times[0;1)$. Let $C=\\{\varnothing,0,1,00,01,\ldots\\}$ the
dyadic tree above. For each string $w\in X$, consider the set
$B_{w}\subset\mathcal{S}$ defined as follows: $B_{w}$ is made of those points
$(x,y)\in\mathcal{S}$ such that the binary expansion of $x$ starts with $w$,
and $y\in[1-1/2^{k};1-1/2^{k+1})$ where $k$ is the length of $w$. Graphically,
this creates a tree-like partition of the square $\mathcal{S}$, where the
empty string corresponds to the bottom half, the strings $w=0$ and $w=1$
correspond to two sets on the left and right above the bottom hald, etc.
Define the following MDP with two actions $0$ and $1$: with action $0$, every
state $s\in B_{w}$ goes to a uniform random state in $B_{w0}$, and with action
$1$, every state $s\in B_{w}$ goes to a uniform random state in $B_{w1}$. The
goal-dependent $Q$-function $Q^{\ast}$ is similar to the dyadic tree above,
but is continuous. Its mass is infinite for the same reasons.

##  Appendix D The successor goal measure
$M(s,g,\operatorname{d}\\!{}g^{\prime})$

###  D.1 Definition and existence of the successor goal measure

###### Theorem 12.

The _successor_ measure

$\displaystyle\nu^{\pi}(\operatorname{d}\\!{}s|s_{0},g)=(1-\gamma)\sum_{k\geqslant
0}\gamma^{k}(P^{\pi})^{k}(\operatorname{d}\\!{}s|s_{0},g)$ (100)

is a well defined probability measure over $\mathcal{S}$ for every $s_{0},g$.
It satisfies the fixed-point equation:

$\displaystyle\nu^{\pi}(\operatorname{d}\\!{}s|s_{0},g)=(1-\gamma)\delta_{s_{0}}(\operatorname{d}\\!{}s)+\mathbb{E}_{a\sim\pi(\operatorname{d}\\!{}a|s_{0},g),s_{1}\sim
P(\operatorname{d}\\!{}s_{1}|s_{0},a)}\left[\nu^{\pi}(\operatorname{d}\\!{}s|s_{0},g)\right]$
(101)

The _successor-goal measure_ is defined as:

$\displaystyle
M^{\pi}(s,g,.)\mathrel{\mathop{:}}=\frac{1}{1-\gamma}\varphi_{\ast}\nu^{\pi}(.|s,g)$
(102)

where $\varphi_{\ast}$ is the _push-forward_ operator on measures. We define
the Bellman operator mapping $M(s,g_{1},\operatorname{d}\\!{}g2)$ to
$T_{\pi}M$ with

$(T_{\pi}\cdot
M)(s,g_{1},\operatorname{d}\\!{}g_{2})=\delta_{\varphi}(s)(\operatorname{d}\\!{}g_{2})+\gamma\mathbb{E}_{a\sim\pi(a|s,g_{1}),s^{\prime}\sim
P(\operatorname{d}\\!{}s^{\prime}|s,a)}\left[M(s^{\prime},g_{1},\operatorname{d}\\!{}g_{2})\right],$
(103)

Then, $M^{\pi}$ is a fixed point of $T^{\pi}$.

###### Proof.

For every $k$, $(P^{\pi})^{k}(\operatorname{d}\\!{}s|s_{0},g)$ is a
probability measure over $\mathcal{S}$. Therefore, for any measurable set
$S\subset\mathcal{S}$, the sum $(1-\gamma)\sum_{k\geqslant
0}\gamma^{k}(P^{\pi})^{k}(S|s_{0},g)\leqslant 1$, and the sum converges.
$\nu^{\pi}(\operatorname{d}\\!{}s|s_{0},g)$ is a positive measure as a
convergent sum of positive measure. Its total mass is
$(1-\gamma)\sum_{k\geqslant
0}\gamma^{k}(P^{\pi})^{k}(\mathcal{S}|s_{0},g)=(1-\gamma)\sum_{k\geqslant
0}\gamma^{k}=1$. Therefore, $\nu^{\pi}(\operatorname{d}\\!{}s|s_{0},g)$ is a
well-defined probability measure.

We now prove the fixed point equation. We have:

$\displaystyle\nu^{\pi}(\operatorname{d}\\!{}s|s_{0},g)$
$\displaystyle=(1-\gamma)(P^{\pi})^{0}(\operatorname{d}\\!{}s|s_{0},g)+(1-\gamma)\sum_{k\geqslant
1}\gamma^{k}(P^{\pi})^{k}(\operatorname{d}\\!{}s|s_{0},g)$ (104)
$\displaystyle=(1-\gamma)\delta_{\varphi(s_{0})}(\operatorname{d}\\!{}s)+\left(P^{\pi}\left((1-\gamma)\sum_{k\geqslant
1}\gamma^{k}(P^{\pi})^{k-1}\right)\right)(\operatorname{d}\\!{}s|s_{0},g)$
(105)
$\displaystyle=(1-\gamma)\delta_{\varphi(s_{0})}(\operatorname{d}\\!{}s)+\gamma\left(P^{\pi}\ast\nu^{\pi}\right)(\operatorname{d}\\!{}s|s_{0},g)$
(106)
$\displaystyle=(1-\gamma)\delta_{s_{0}}(\operatorname{d}\\!{}s)+\mathbb{E}_{a\sim\pi(\operatorname{d}\\!{}a|s_{0},g),s_{1}\sim
P(\operatorname{d}\\!{}s_{1}|s_{0},a)}\left[\nu^{\pi}(\operatorname{d}\\!{}s|s_{0},g)\right]$
(107)

where
$(P^{\pi}\ast\nu^{\pi})(\operatorname{d}\\!{}s|s_{0},g)\mathrel{\mathop{:}}=\int_{s_{1}}P^{\pi}(\operatorname{d}\\!{}s_{1}|s_{0},g)\nu^{\pi}(\operatorname{d}\\!{}s|s_{1},g)$.
We now show the Bellman fixed point equation of $M^{\pi}$. We now that

$\displaystyle\nu^{\pi}(\operatorname{d}\\!{}s|s_{0},g)=(1-\gamma)\delta_{s_{0}}(\operatorname{d}\\!{}s)+\mathbb{E}_{a\sim\pi(\operatorname{d}\\!{}a|s_{0},g),s_{1}\sim
P(\operatorname{d}\\!{}s_{1}|s_{0},a)}\left[\nu^{\pi}(\operatorname{d}\\!{}s|s_{0},g)\right]$
(108)

By applying the push-forward operator $\varphi_{\ast}$ we have:

$\displaystyle(1-\gamma)M^{\pi}(s_{0},g,\operatorname{d}\\!{}g^{\prime})$
$\displaystyle=(1-\gamma)\delta_{s_{0}}(\operatorname{d}\\!{}s)+\varphi_{\ast}\left(\int_{a,s_{1}}\pi(a|s_{0},g)P(\operatorname{d}\\!{}s_{1}|s_{0},a)\nu^{\pi}(\operatorname{d}\\!{}s|s_{1},g)\right)$
(109)
$\displaystyle=(1-\gamma)\delta_{s_{0}}(\operatorname{d}\\!{}s)+\left(\int_{a,s_{1}}\pi(a|s_{0},g)P(\operatorname{d}\\!{}s_{1}|s_{0},a)\varphi_{\ast}\nu^{\pi}(\operatorname{d}\\!{}s|s_{1},g)\right)$
(110)
$\displaystyle=(1-\gamma)\delta_{s_{0}}(\operatorname{d}\\!{}s)+\int_{a,s_{1}}\pi(a|s_{0},g)P(\operatorname{d}\\!{}s_{1}|s_{0},a)M^{\pi}(s_{1},g,\operatorname{d}\\!{}g^{\prime})$
(111)

∎

###  D.2 The Policy Evaluation Update

In this section, we prove Theorem 5 for learning $M^{\pi}$ via temporal
differences algorithm, TD and $TD^{(n)}$. This theorem very similar to Theorem
11. We directly prove the result for $\mathrm{TD}^{(n)}$, as the standard
$\mathrm{TD}$ update stated in Theorem 5 corresponds to the
$\mathrm{TD}^{(n)}$ update for $n=1$.

The resulting parametric update is on-policy: Let $\pi$ be a policy, we assume
access to a sampling distribution
$(g,s_{0},...,,s_{n})\sim\rho_{\mathrm{SG}}(\operatorname{d}\\!{}g,\operatorname{d}\\!{}s_{0})P^{\pi}(\operatorname{d}\\!{}s_{1}|s_{0},g)...P^{\pi}(\operatorname{d}\\!{}s_{n}|s_{n-1},g)$,
where $\rho_{\mathrm{SG}}$ is any distribution on
$\mathcal{S}\times\mathcal{G}$. Typically, this can correpond to couples
$(g,s_{k})$ from trajectory with $g\sim\rho_{\mathcal{G}}$,
$s_{0}\sim\rho_{0}(.|g)$, $s_{t+1}\sim P^{\pi}(.|s_{t},g)$. Here, our
statement with a distribution $\rho_{\mathrm{SG}}$ is more general.

Given a measure-valued function of $(s,s)$, such as
$M(s,g,\operatorname{d}\\!{}g^{\prime})$, we define its norm as

$\left\lVert
M\right\rVert^{2}_{\rho_{\mathrm{SG}},\rho_{\mathcal{G}}}\mathrel{\mathop{:}}=\mathbb{E}_{(s,g)\sim\rho_{\mathrm{SG}},\,g^{\prime}\sim\rho_{\mathcal{G}}}[m(s,g,g^{\prime})^{2}]$
(112)

where
$m(s,g,g^{\prime})\mathrel{\mathop{:}}=M(s,g,\operatorname{d}\\!{}g^{\prime})/\rho_{\mathcal{G}}(\operatorname{d}\\!{}g^{\prime})$
is the density of $M^{\pi}(s,g,.)$ with respect to $\rho_{\mathcal{G}}$, if it
exists (otherwise the norm is infinite).

###### Theorem 13 (Formal statement of Theorem 5).

Let
$M_{\theta}(s,g,\operatorname{d}\\!{}g^{\prime})=m_{\theta}(s,g,g^{\prime})\rho_{\mathcal{G}}(\operatorname{d}\\!{}g^{\prime})$
be a current estimate of $M^{\pi}(s,g,\operatorname{d}\\!{}g^{\prime})$. Let
likewise
$M_{\mathrm{tar}}(s,g,\operatorname{d}\\!{}g^{\prime})=m_{\mathrm{tar}}(s,g,g^{\prime})\rho_{\mathcal{G}}(\operatorname{d}\\!{}g^{\prime})$
be a target $M$, and consider the following update to bring $M_{\theta}$
closer to $(T^{\pi})^{n}M_{\mathrm{tar}}$ with $T^{\pi}$ the Bellman operator.

Let
$\tau=(g,s_{0},...,s_{n})\sim\rho_{\mathrm{SG}}(\operatorname{d}\\!{}g,\operatorname{d}\\!{}s_{0})P^{\pi}(\operatorname{d}\\!{}s_{1}|s_{0},g)...P^{\pi}(\operatorname{d}\\!{}s_{n}|s_{n-1},g)$
be a sample of the environment and $g^{\prime}\sim\rho_{\mathcal{G}}$ is a
goal sampled independently. Let
$\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}(n)}$ be

$\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}(n)}(\tau,g^{\prime})\mathrel{\mathop{:}}=\sum_{l=0}^{n-1}\gamma^{l}\partial_{\theta}m_{\theta}(s_{0},g,\varphi(s_{l}))+\partial_{\theta}m_{\theta}(s_{0},g,g^{\prime})\left(\gamma^{n}m_{\theta}(s_{n},g,g^{\prime})-m_{\theta}(s_{n},g,g^{\prime})\right)$
(113)

Then $\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}(n)}$ is an unbiased
estimate of the Bellman error:
$\mathbb{E}_{\tau,g^{\prime}}\left[\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}}(\tau,g^{\prime})\right]=\frac{1}{2}\partial_{\theta}\|M_{\theta}-(T^{\pi})^{n}M_{\mathrm{tar}}\|_{\rho_{\mathrm{SG}},\rho_{\mathcal{G}}}^{2}$.

In particular, the true $M^{\pi}$ is a fixed point of this udpate: if
$M_{\theta}=M_{\mathrm{tar}}=M^{\pi}$, then

$\mathbb{E}\left[\widehat{\delta\theta}_{\delta\text{-}\mathrm{TD}(n)}\right]=0$
(114)

For this theorem, we sample goals $g^{\prime}$ independently of $\tau$. In
practice, this could be a source of variance, as sampling goals far from the
current state should produce close-to-$0$ V-values. If we instead sample goals
from a distribution $\mu(g|s,a)$, this introduces an implicit _scaling_ factor
$\alpha(s,g)$ to the reward. This is discussed in details and the end of
Appendix E.2 in the case of the $V$-function.

As in Appendix C.2, there is a hidden mathematical subtlety with continuous
states regarding the norm $\|M_{\theta}-(T^{\pi})^{n}M_{\mathrm{tar}}\|$,
which is infinite because $(T^{\pi})^{n}M_{\mathrm{tar}}$ is not absolutely
continuous with respect to $\rho_{\mathcal{G}}$. However, as in Appendix C.2,
the _gradient_ of $\|M_{\theta}-(T^{\pi})^{n}M_{\mathrm{tar}}\|$ is finite.
Because the rigorous way to handle it is exactly the same technique as in
Appendix C.2, we will not derive it in this section.

###### Proof.

The proof is very similar to the proof of Theorem 11. Similarly to the
derivation of (92), we have:

$-\partial_{\theta}\frac{1}{2}\partial_{\theta}\|M_{\theta}-(T^{\pi})^{n}M_{\mathrm{tar}}\|_{\rho_{\mathrm{SG}},\rho_{\mathcal{G}}}^{2}=\int_{s_{0},g,g^{\prime}}\rho_{\mathrm{SG}}(\operatorname{d}\\!{}s_{0},\operatorname{d}\\!{}g)\partial_{\theta}m(s_{0},g,g^{\prime})((T^{\pi})^{n}M_{\mathrm{tar}}(s,g,\operatorname{d}\\!{}g^{\prime})-M_{\theta}(s,g,\operatorname{d}\\!{}g^{\prime}))$
(115)

Moreover:

$\displaystyle\begin{split}(T^{\pi})^{n}M^{\mathrm{tar}}(s,g,\operatorname{d}\\!{}g^{\prime})-M_{\theta}(s,g,\operatorname{d}\\!{}g^{\prime})=&\sum_{k=0}^{n-1}\gamma^{k}\mathbb{E}_{s_{1},...,s_{k}|s_{0},g}\left[\delta_{\varphi(s_{k})}(\operatorname{d}\\!{}g)\right]\\\
&+\left(\gamma^{n}\mathbb{E}_{s_{n}|s_{0},g}\left[m_{\mathrm{tar}}(s_{n},g,g^{\prime})\right]-m_{\theta}(s_{0},g,g^{\prime})\right)\rho_{\mathcal{G}}(\operatorname{d}\\!{}g^{\prime})\end{split}$
(116)

Therefore: