USHER: Unbiased Sampling for Hindsight Experience Replay
Authors: Liam Schramm
Yunfu Deng
Edgar Granados
Abdeslam Boularias
Venue: CoRL 2022 Poster (2022)
Keywords: Reinforcement Learning
Multi-goal reinforcement learning
Reinforcement learning theory

Abstract:  Dealing with sparse rewards is a long-standing challenge in reinforcement learning (RL). Hindsight Experience Replay (HER) addresses this problem by reusing failed trajectories for one goal as successful trajectories for another. This allows for both a minimum density of reward and for generalization across multiple goals. However, this strategy is known to result in a biased value function, as the update rule underestimates the likelihood of bad outcomes in a stochastic environment. We propose an asymptotically unbiased importance-sampling-based algorithm to address this problem without sacrificing performance on deterministic environments. We show its effectiveness on a range of robotic systems, including challenging high dimensional stochastic environments.

USHER: Unbiased Sampling for Hindsight Experience Replay
Liam Schramm
Yunfu Deng
Department of Computer Science Rutgers University
Department of Computer Science
Rutgers University
New Brunswick, NJ 08904 1bs105Grutgers.c edu
New Brunswick, NJ 08904
yd275@scarleemaill rutgers edu
Edgar Granados
Abdeslam Boularias
Department of Computer Science
Department of Computer Science
Rutgers University
Rutgers University
New Brunswick, NJ 08904
New Brunswick, NJ 08904
gary. waaryggranados@gail.ccmmm
ab1544@rutgers. edu
Dealing with sparse rewards is long-standing challenge in reinforce- ment learning (RL). Hindsight Experience Replay (HER) addresses this problem by reusing failed trajectories for one goal successful trajectories for another. This allows for both a minimum density of reward and for generalization across multiple goals. However, this strategy is known to result in a biased value function, as the update rule underestimates the likelihood of bad outcomes stochastic environment. We propose an asymptotically unbiased importance-sampling based algorithm address this problem without sacrificing performance on deterministic environments. We show its effectiveness range of robotic systems, including challenging high dimensional stochastic environments.
Abstract:
Keywords: Reinforcement Learning, Multi-goal reinforcement learning
Introduction
In recent years, model-free reinforcement learning (RL) has become popular approach in robotics. In particular, these methods stand out in their ability to learn near-optimal policies in high-dimensional spaces [1, 2, 3]. One popular extension of RL, multi-god RL, allows trained robots to generalize to new tasks by conditioning on goal parameter that determines the reward function. However, RL algorithms often struggle with tasks that involve sparse rewards, as these environments can require a very large amount of exploration to discover good solutions. Hindsight Experience Replay (HER) offers solution the sparse reward problem for multi-goal reinforcement learning [4]. HER treats failed attempts reach one goal as successful at- tempts reach another goal. This significantly reduces the difficulty of the exploration problem, because it guarantees minimum density of reward and ensures that every trajectory receives useful feedback on how to reach some goal, even when the reward signal is sparse. However, these benefits come with a trade-off. While HER is unbiased in deterministic environ- ments, it is known be asymptotically biased in stochastic environments [5, 6]. This is because HER suffers from vivorship bias. Since failed trajectories to one goal are treated as successful trajectories to another, it follows that HER only ever sees successful trajectories. a random event can prevent the robot from reaching a desired goal g, then HER will only
Figure 1: Q-values learned with HER (left), and Q-leaming (right). A robot must navigate from the white cirele black circle while avoiding obsta- cles (black squares) and risky areas (yel- low triangle. 75% chance of stopping the robot). The value function ranges from (bright green) to (bright red).
6th Conference Robot Learning (CoRL. 2022), Auckland, New Zealand.

---

sample goal when the event did not occur, leading it to significantly overestimate the likelihood of success and underestimate the likelihood of dangerous events. Practically, this manifests as a tendency for HER to want to "run red lights" and take risks.
We present a concrete toy example of this problem in Figure 1, using tabular Q-learning- As can sec, HER values the direct path to the goal and the square en route to the dangerous square much higher than that path's 's correct Q-value because it undersestimates the risk. HER learns to take the shorter, more dangerous path and achieves lower success rate with lower reward than Q-learning.
As suggested in both [5] and [6], we derive an approach that allows us to use HER for sampling goals without suffering from these bias problems. We do this by separating the goal used for the reward function (g,) from the goal that is passed to the policy (gx). The value function is conditioned on both goals, but only the reward goal is sampled using HER. This allows us efficiently learn successor representation over future achieved goals that we can use for importance sampling. We show that reweighting HER's s mean squared Bellman error using this successor representation yields an unbiased estimate of the error. We call this method Unbiased Sampling for Hindsight Experience Replay (USHER). We demonstrate this approach on an array of stochastic environments, and find that it counteracts the bias shown by HER without compromising HER's sample efficiency or stability.
2 Definitions
We define multi-goal Markov Decision Process (MDP) as a seven-tuple: state space S S IR" action space A RRm,, discount factor y E [0. 1]. transition probability distribution P(s' s, a) (with density function f(s' a)) for (s, a, s') E S x A x S. goal space G s R², goal function 6 : S - G, and reward function R S x G - R. A goal g = o(s) E G is vector of goal-relevant features of state 8 E S. Goal function Φ is defined a priori, depending on the task. A typical example of db(s) is a low-dimensional vector that preserves only the entries of state-vector s that are relevant to the goal. For instance, a mobile robot is tasked with moving to a particular location and arriving there at zero velocity. The state space of the robot would include velocities and orientations of each wheel, along with several other attributes that are needed to control the robot. The goal function would take the full high-dimensional state of the robot and return only its location and velocity. Therefore, each goal point corresponds to a subspace of the state space in this example. A special case is when G = S and g = Φ(s), Vs E S. Note that the immediate reward function R(s,g) g) depends on a selected goal g e G. Every selection of g E G produces a valid single-goal MDP. We denote by π a deterministic goal-conditioned policy, with T ((, g) E A for 8 E S, g E G, and define Q*(s (s, a, g) to be the unique optimal Q-value of action E A in state 8 E S. given selected goal g E G.
In the proposed algorithm and analysis, policy can be evaluated according to goal that is not necessarily the same goal used by the policy for selecting actions. Therefore, we use Ix to refer to goals that are passed to policies, and Ir to denote goals that are used to evaluate policies. Using these notations, the Bellman equation is re-written as
Qt (s, a, (r.)))>) = [R<( gr) + (Q" ((66,'=)) (r). 9r)9*) s..a].
Intuitively, this means "The expected cumulative discounted sum of rewards R()', when using policy T(s', )x. The reason for this separation is that it allows us to more casily separate the problem of predicting future rewards from the problem of directing the policy. This makes much easier to find an analytic expression for HER's bias. In particular, it lets us learn an expression for future goal occupancy that is conditioned only on g= and not gr, which will allow us to correct for the bias induced by hindsight sampling. Observe that when g. 9a. this definition reduces to the Bellman equation for standard multi-goal RL. For standard Q-learning, T(s', 9r) would be arg max, Q(s', a', Sr 9x), where both the policy and reward goals are set to Jx-
HER. HER is a modification of the experience replay method employed by many deep RL algo- rithms [1, 4, 7, 8, 9]. Policy goal gx is sampled before each trajectory begins, and is not changed while generating the trajectory. After generating trajectory, HER stores the entire trajectory in the replay buffer. When sampling transitions (s, In, a, s') from the buffer, HER retains the original goal
2

---

Inr used in the policy that generated the trajectory, i.e., 9r < 9x. with probability k+1: where ls is a natural number (usually or 8). The rest of the time, it replaces the original goal with d(*)), i.e., Ir < ((s)), where &t is a randomly sampled state from the future trajectory that starts at 8. Goals that are selected from the future trajectory are referred to as "hindsight goals". HER then updates the Q-value and policy networks with (s, 9n. a, s', Ri'sR((ss)) gr)).
1_
3 Related Work
Over the last few years, several methods have attempted to address the hindsight bias induced by HER. ARCHER attempts to decrease HER's hindsight bias by multiplying the loss on hindsight goals and non hindsighd goals by different weights, effectively upweighting the importance of hindsight goals [10]. MHER extends HER to a multi-step RI. and proposes a bias/variance tradeoff for that setting [11]. A rigorous mathematical approach to HER's hindsight bias is taken in [5], by showing that HER unbiased in deterministic environments, and that one of HER's key benefits is ensuring minimum density of feedback from the reward function, even in high-dimensional spaces where the reward density would normally be extremely low. This reward-density problem is addressed by deriving family of algorithms (called the 8-family, e.g. 6-DQN, 8-PPO), which guarantees minimum reward density while still being unbiased. These methods do not use HER and have higher variance. The authors of [S] also state that the problem of formulating an unbiased form of HER is still open, and call for additional research into the problem.
CarreCore HER (BHER) attempts account for hindsight bias by analytically calculating importance-sampling hindsight goals [12]. Unfortunately, we believe that this derivation is incorrect. The proof in BHER relies on the assumption that the probability of transition is independent of the goal (J's' 8, 0, g) = f(s' s; a)). This assumption does not hold for HER, because it samples the goal from the future trajectory of s, which depends on 8'. Both our work and [5] give concrete counterexamples to this assumption. The following derivation provides an unbiased solution that does not rely on this flawed assumption.
4 Derivation
Bias in HER. We derive the formula of the bias introduced by HER in estimating the Q-value function in the following. Let 8, a, and s' be random variables representing a state, action, and subsequent state in given trajectory generated by policy with goal 9.- Let T be the number of time- remaining in the sub-trajectory that starts at s. Let QHERR( a, fr. be the solution to the Bellman equation obtained using HER's s sampling process of reward goal gr (Sec. 2). This sampling process takes into account both 9-. and T. Furthermore, 9r is selected from the sub-trajectory that starts at with probability + R+T. Therefore, the probability f(s' 8, 9r. 9r, T") of the next state s' after knowing Ir,9r and T is generally not the same as f(&' a), which is what HER uses empirically to estimate QHER((S a, gr, 9x). The following proposition quantifies this bias ratio.
Proposition 1. Suppose 9- is fixed at the start of the trajectory, and gr is sampled using HER. Then for any s', s, a. gr. Ix T.f (s' s.a. Gr. 9n T) [[gela' .x(' . be).g..T-- (g.TT-1 [ (g9-99,0.9..1 .T)
f(s' s,
Proof: Appendix (A.5). This identity presents an interesting corollary.
Corollary. Suppose QHER(S, s, a, 9n 9n) satisfies the Bellman equation and the distribution of future achieved goals is absolutely continuous with respect the goal space for all s, a, 9x. and n ((s, (x) arg max. QuER a', In, Ix). Then QiERls, a, In 9x) Q* (s, a, Jx), where Q* is the optimal goal-conditioned Q-function.
Proof: Appendix (A.6). While this establishes that the target value for QHER is unbiased when Ir 9r. the function approximator for Q ERE may still be biased, because values other than 9r Ir may influence it through the training of the network. Thus, it is possible that the learned Q value may remain biased until unacceptably large amounts of data gathered. Additionally, since the density of data is discontinuous, Q may be discontinuous and difficult to approximate with
3

---

neural network. The rest of this section is devoted to developing an importance sampling method that is guaranteed to be asymptotically unbiased over the entire domain of Q.
Unbiased HER. To estimate Q" (s. a, 9r. 9r), the solution to the unbiased Bellman equation, we use in this work the following expression,
as, = E., [.,[M((s', s,a, 9r. T) (R((')
(QT(S (x)) (r)))) O. Pr. I T].
where M(s', 8, 0, Dr. 9r, 7) is a weight that cancels the bias ratio given in Proposition 1. Conditioning the expected value over 5' on 9r.9a, 9a. and I frees us from the constraint that s' needs to be independent
of 9r. and T. This would allow us to select 9, from the future trajectory of s, as HER does. Note that conditioning on T. the number of steps left in the trajectory, is necessary because the distribution of goals selected by HER is not time-independent.
Proposition is useful for understanding what situations may cause HER to be biased, but un- fortunately we cannot directly use it for importance sampling. Weighting samples by setting fls.ls.a.ge.7))
would require f(g s', iT's, (r), 9r. T 1) to always be greater than 0. which is not necessarily true. To solve this, we sample mixture of hindsight goals and goals drawn uniformly from the goal space G. Of the goals where 9r 1 Jr. fraction of our goals will be drawn uniformly from the goal space, and the remaining 1 - will be drawn from the trajectory that follows s. This results in the following identity,
M(s', S, gr. 9v. T) as f(g=le'.m(ed ((1 -..1))
Let W(s', 8, O. Gr 9x. T) of of T) (0 1n). 00 Let a real value in the range (0, 1]. Then for any s', s, 9r, Ix.
Proposition 2.
f(s s, a) = W (s', gr. In. (af((s (1- a) (sll'|ss,,,,0.. (r. T)) Furthermore, for any function F state s',
Eg s,a] aB [W (s', a, ar In. Fss') s,a] +(1- - al-,)),, a, Ir Ix. F(') a, 9m gr, Tr.
(I)
Appendix (A.7). We can now derive an unbiased variant of HER by applying Proposition 2 to Bellman equation.
Proof:
Suppose is a deterministic policy, gr is sampled from the previously mentioned mix of hindsight and uniform random goals, and 9n. Then for any s' 8, a, gr Ix, T,
Corollary.
(s,, a, 9w) o..'(W(s', 8, a, Gr, 9r: () 9r) (Q(s' gr), Dr, (x)) |s, a] Ex s, a, 9r, In. 9n. T) (R(s g-) + 7Q(ss, T(s', . gx), Tr. gr)gg)) In 9r, (2)
This corollary provides with a simple method of estimating Q(s, a, 9r) using HER. A similar unbiased expression can be derived for estimating the gradient of the Bellman error with respect to the weights of a Q-function network, instead of estimating ((s, Gr, 9n) directly from samples.
Learning the future goal distribution. In order to use the proposed unbiased estimator of the Q-function with policy and reward goals, we need to compute weight W defined Propo- sition 2. This can be achieved by learning future goal distributions f(gr s, a, 9-: T) and [g. | 86, (18',9n) 3n), 9r. T 1). which both correspond to the conditional probability that given goal 9. will be selected as a hindsight goal by HER. A technique for learning such long-term distributions, introduced in [5], consists in training a network fe. with parameters 0, to approximate the density of future goals f(r |s a). The following estimator for the gradient is used in [5], sampling (s, a, s')
from transitions, and fixing 9r at the start of each trajectory,
folall-fosss fo a, ((s))] + E,,a,'' gr [fo(s, a, gr) (ff(ss a, g.) ymax,' furerr (s', a', (g)))))..
wherein funget copy of fo that is updated separately. This method has however a significantly higher variance than HER [5]. We examine here the source of this variance, and explain how
separating the policy and reward goals allows us avoid this variance problem. One issue with this method that can contribute to variance is that the gradient is separated into two parts: one in which

---

the goal comes from the state (o(s)), and one in which the goal is sampled at the start of the trajectory (g+). This is problem, because the gradient at the state-derived goals strictly negative, while the gradient at the sampled goals is usually positive. In our experiments, this led to a pattern where the value the state-derived goals would diverge unboundedly, until a goal was sampled sufficiently close to make the value function crash back down to zero, and then the process would repeat again. In other words, it is not guaranteed that fo converges a fixed point for every finite set of trajectories.
One way to avoid this problem would be to have fixed, non-zero chance that ((s) Ir, so that So always converges to a fixed point given any set of training trajectories. We use HER to achieve this outcome. This is possible, unlike in [5], because we can use the importance sampling method derived above to sample mixture of HER goals and goals independent of the state. Since HER draws from the future states of observe that [gr 8; a, Iw: 7' is in fact successor representation [13], using average-rewan reward formulation (because the probability of selecting any of the next T states is uniform). Observe that we can define this probability as
In). T 1) 8, s,a], [gr 8, 0, 9w, T) Eg E. 1 ((')) + (1 } M (
wherein is Dirac delta function. This results in the loss gradient:
Vo (E 2 fols, a, ((s), 9n T) Ex|L(ss, Ir. In. T) 8, alll).
(3)
Ls8, 0, 8' 1r.9rr Ir. T) fo(s, a, Dr. Ir. (fo(s, a, 9r. Ir, T) - 1 Jurgels (s', (()'9r)), Ir: In. 7 1)). While fo may not be a true probability density (because it may not integrate to 1), this does not matter for our purposes, as this factor will divide out when we calculate W. Finally, we inject the formula in Equation into Equation 1, while replacing F with fe. to derive the following unbiased loss gradient,
VoL VolEl -o folos, o(s), 9n. 1) a [W (s, a, s' gr, In T L) a, s' I', 9n. T) a]
2
+ (1 - a))-a) a, 9r 9x. (s, a, s gr, Ir. T) s, a. 9r In. 9n. TT].
Note that the values of a we use for learning Q9 (Equation 2) and goal distribution densities fa (Equation 4) can be different. For discrete environments, we can learn the future distribution of the goal state using simple tabular methods, such as tabular successor representations.
Algorithm and Implementation
USHER may be implemented atop DDPG [7], SAC [8], TD3 [9], or any other continuous RL algorithm, as it only changes the loss function for training the goal-conditione Q-value network. In our experiments, we use SAC as a base. USHER calculates the loss follows: It samples batch of transitions (s, a, yr, 8', T) from the replay buffer, along with sets of goals: gr. which is drawn from the future distribution of s, and g'.,, which is drawn uniformly from the goal space G. For each set of goals, we calculate two values of W. W. and Way. We omit the full training loop here, it is identical to standard HER except for the loss computation. To minimize the variance induced by importance sampling, we clip Way and W og to the range [Tte + c], where e is a hyperparameter: This allows us to make a bias/variance trade-off between hindsight bias and the variance induced by importance sampling. We find that performance is best for e s 0.3, and that the bias induced by clipping negligible for e > 1.0 for most environments. We approximate W using fo for all experiments. In order to reduce the total number of neural network evaluations, we made Qo and fo two heads of two-headed neural network. Although this choice conditions the value function on T. the expected gradient for the policy remains the same.
6 Experiments
6.1 Discrete environment
We first demonstrate our method in the discrete case described in the introduc- tion in Figure because it is analytically tractable and allows to verify that
5

---

Algorithm 1 Update Rule for USHER
Input:
Replay Busfer B, Two-headed Critic Network with weights 0, Actor Network with weights w. Weighting Factor aq q for Q, Weighting Factor agfor f. Goal Space G, Goal Function Ø: Sample batch of tuples (s, a, 9',9r, from B;
critic loss 0; actor _loss-ossss--- =0
Define ((s, a, 9.. 9r. (.)) a (7)l))ll.....7)++11111 (. (an (1 9.).
for each sampled tuple (s, a, 8., 99:: TT: B do
With probability k k+1; 9r =Sample from future trajectory of 8: Else: 9r = 9
largel_q R(b(s' ).9r) ) + Qurrer (s', π T (r), Dr, Iw: T 1); // Q targe is copy of Qo
target_ R( (6 (.)..r)) + Quares (8) (88 - 9r. T 1);
Wa, (1 aj (s,a,, s', gr, T, ag)); Wa, a a, Ix. g aa,) (s,
Wao = (1 aq) (Q) (s, a, 5', :' T, (xQ); W aeW (s, a,
IN Fr. T, oq)
critic_oss 2 (=)))
s, 9n: T)
crilic_loss += Wo, (Jo( 8, 0, Iz: T) - Starges
8 π , [=)= gr, T - 1))² s',, π ( 19x) 9x. T 1))
critic_loss += Way (fo(g s, Ix: T) ftarges (g's
crilic_loss WaO (Qa(s, a Gr. gr: T) largel_g)
critic_lose += W (Qo(s, a, Ir gu, T) target_q")
actor_loss - Qo(8, Tae (8, 9n, Dr gr. 9x,9x, T) end for
Backprop critic_los loss and update Backprop actor loss and update
USHER learns the correct value function. path that has a high chance of disabling the robot, and a longer risk-free path. tao
The environment used has a short, risky
The longer path has a higher expected reward, but we find that HER mistakenly prefers the riskier path. The value functions for USHER and Q-learning both quickly converge to the ex- pected value, while HER overestimates the ex- pected reward.
Figure 2: Average reward and bias for HER, USHER, and Q-learning on the long/short path environment.
6.2 4- Torus with Freeze
N-Torus with Freeze (Fig 3) is a benchmark envi- ronment introduced by Unbiased Methods that demonstrates HER's bias. Robots navigate torus with an N-dimensional surface to reach a goal. There is also "Freeze" action, which causes the agent to jump to a random location and then permanently freeze in place and not move again. Further details can be found in [5] or in the Appendix (A.1.2). HER learns to always take the freeze action and fails as a result, while USHER learns a successful policy. DDPG and 6-DDPG are unbiased in this environment, but DDPG struggles due to the difficulty of exploring in high dimensions, and 6-DDPG struggles with its variance.
Figure 3: Success Rates (left) and Average Rewards (right) for the Torus with Freeze environment
6.3 Car Environment with Random Noise
This environment (Fig 4) uses the "Simple Car" dynamics described [14). The robot must navigate around walls while subject to Gaussian action noise [15]. HER performs well for low noise values, but tends to overestimate values more the noise level rises. USHER suffers significantly less from high noise levels than HER.

---

Longustar Inueoement heformaace
Langhroat fowiveer Nertemmnne
020 A1d G.M Eay
616
020
Figure 4: Success Rates (middle) and (right) the Stochastic Car environment
6.4 Red Light Environment
Here, expand the example given in the introduction, where HER learns to run red lights because it underesti- mates the likelihood of a crash. This environment (Fig 5) uses the same car dynamics the short/long path en- vironment, but change the map to be two sections separated by intersec-
20-14
20
1000
2000
1050
1000
Figure 5: Success rates (left) and average reward (right) for the Red Light Environment
tion and traffic light. If the car is in the intersection while the traffic light is red, than there is 75% chance per unit time that the car will be an accident and break. The green and yellow lights are both safe, and the initial color of the light random. We find that HER learns to run the red light and immediately attempt to reach the goal, while USHER learns to wait for the red light to end. This results in USHER achieving both higher success rates and higher rewards.
6.5 Fetch Robot Environments
While the 6-Actor Critic succeeded being unbiased, this came the expense of performance in deterministic environments, due to the method's 's increased variance [5]. Our goal in this section is to show that USHER does not suffer from this trade-off, and delivers performance competitive with standard HER. To do this, we compare the performance of HER and USHER on several Fetch Robot object manipulation tasks (Fig 6), as these were the tasks HER was originally designed for. These three environments task a robot manipulating a robot arm to reach point, push an object, and slide an object point outside of the robot's reach, respectively. USHER able to match HER's performance all of the tested environments (Fig This suggests that the importance sampling method does not significantly affect USHER's 's variance sample efficiency in deterministic environments, where HER is known to be unbiased. It also significantly outperforms two other unbiased methods, DDPG and 5-DDPG on FetchReach. Note that although BHER performs slightly better than HER, it takes approximately 10x as long to train as HER, due to needing to evaluate the policy for the entire trajectory for every sampled goal at training time.
Figure 6: FetchReach (left), FetchPush (middle), and FetchSlide (right) Environments
Figure 7: Success Rates for the FetchReach, FetchPush, and FetchSlide Environments
7

---

6.6 Mobile Throwing Robot
We design a simulated robot arm on a mobile base, and task it with throwing a ball to a randomly selected location (Fig 8). There is also a 50% chance of wind that can blow the ball off course. USHER matches HER's 's sample efficiency until the point where HER's 's bias causes its performance to suffer. USHER's performance, by contrast, continues to grow steadily significantly better than HER's 55%. Interestingly, reward here. This is likely because this environment is slightly non-Markovian, because the wind is sampled at the beginning of each trajectory, and then remains fixed. USHER's ' proof of unbiasedness, however, assumes that the environment is Markovian. It is interesting to note that USHER still performs well even when this property does not completely hold.
75% success rate, find that USHER actually underestimates its
Figure 8: (Left to right) Visualization of the experiment, Success Rates, Rewards, and Bias for the Mobile Robot Throwing experiment
6.7 Navigation on a physical mechanum robot
Lastly, we train mechanum robot to navigate around obstacles to reach goal and deploy it on a physical robot (Fig 9). The terrain contains high friction zone that leads to the goal faster, but unreliably. Transfer was done by rolling out trajectories in simulation, and then deploying the same sequence of actions on the physical robot as an open-loop control. We find that USHER outperforms HER. Both robots take the short goal when it is open. When the path is blocked, HER repeatedly slams into the obstacle. By contrast, USHER runs into the block once, and then turns to go around it if it is blocked. This leads USHER to have a higher success rate. In simulation, HER's s success rate is approximately 50%, while USHER's is near 100%. Due to the difficulty of transfer, USHER's performance drops on the physical robot, but it still outperforms HER. HER succeeded on 4/10 goals, while USHER succeeds on 6/10. Both methods succeed I 100% of the time on the unblocked path environment.
IED
Figure 9: Simulated Mechanum Robot(left) and Physi- cal Mechanum Robot(right)
7 Limitations
One limitation of this work is that we rely on the Markov assumption to derive our importance sampling weights. This means that while we can correctly estimate the value function for stochastic transitions, we cannot guarantee that the learned value is correct in environments with hidden information. It unclear whether this is actually an issue in practice, as USHER still outperforms HER on the non-Marke Man-Markovian environments we tested (such the Throwing Bot). Additionally, USHER requires approximately 2.5 times as many neural net evaluations HER does per batch update. This was not an issue in our experiments, as the cost of simulation and policy evaluations usually dominated the training time.
8 Conclusion
We derive an unbiased importance sampling method for HER, and show that it able to effectively counteract HER's hindsight bias. We find that addressing this bias leads to higher success rates and rewards in a range of stochastic environments. Furthermore, we introduce a mathematical framework to justify our method which can be used to examine the situations where HER is likely to experience significant bias. In future work, we hope to examine the finite-sample case, in order to better understand whether HER introduces a bias there, and if so, how it could be corrected.
8

---

References
[1] V. Mnih, K. Kavukcuoglu, D. Silver, A. Graves, I. Antonoglou, D. Wierstra, and M. Riedmiller. Playing Atari with Deep Reinforcement Learning. arXiv:1312.5602 [cs], Dec. 2013. URL ssttp//arxiv..o /t////aaww...gaa/////////// 5602. arv: 1312.5602.
[2] D. Silver, J. Schrittwieser, K. Simonyan, Antonoglou, A. Huang. A. Guez, T. Hubert, Baker, M. Lai, A. Bolton, Y. Chen, Lillicrap, Hui, L. Sifre, van den Driessche, T. Graepel, and D. Hassabis. Mastering the game of Go without human knowledge. Nature, 550(7676;:354-3333 Oct. 2017. ISSN 1476-4687. doi: 10..1000//a/aue22220000 URL https: http::::/wwww.ttttt nature com/
articles/nature245
[3] M. Laskin, A. Srinivas, and P. Abbeel. CURL: Contrastive Unsupervised Representations for Reinforcement Learning. Proceedings of the 37th International Conference on Machine Learning, pages 5639-5650. PMLR, Nov. 2020. URL htt.hht://prroceeinngggg mlr.press.
v119/laskin20a.htm.
[4] M. Andrychowicz, F. Wolski, A. Ray, J. Schneider, R. Fong, P. Welinder, B. McGrew, J. Tobin, P. Abbeel, and W. Zaremba. Hindsight Experience Replay.
[cs], Feb. 2018.
URL http: http///axvvvvvva////v//eae//aaaa .rgg harg/abb/17/0 01495. arXiv: 1707.01495.
[5] L. Blier and Y. Ollivier. Unbiased Methods for Multi-Goal Reinforcement Learning. arXiv:2 106.086633 [cs], June 2021. URL http://arxiv http:///aaxivv..r/abbbbbeee org/abs/21066 08863, arXiv: 2 2106.08863.
[6] M. Plappert, M. Andrychowicz, A. Ray, B. McGrew, B. Baker, G. Powell, J. Schneider, J. Tobin, M. Chociej, P. Welinder, V. Kumar, and W. Zaremba. Multi-Goal Reinforcement Learning: Challenging Robotics Environments and Request for Research. 10.2::1882.09444 [cs], Mar.
2018. URL http: /ttp:://arxxvv org/ abs/aa02 09464. arXiv: 1802.09464.
[7] T. P. Lillicrap. J. J. Hunt, A. Pritzel, N. Heess, T. Erez, Tassa, D. Silver, and Wierstra. Continuous control with deep reinforcement learning. arXiv: 0ol::/509.02977 [cs, stat), July 2019. URL http://arxii org/ abs//509 Tww.1.999........ 02971. arXiv: 1509.02971.
[8] T. Haarnoja, A. Zhou, P. Abbeel, and S. Levine. Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with Stochastic Actor. arXiv:1801 1000.100.00001 200.002900 [cs, stat), Aug. 2018. http: /awxiv..ivvvvv//////////////aia/ www.eoorgooo... aa////bs//1111 01290. arXiv: 1801.01290.
[9] Fujimoto, H. van Hoof, and D. Meger. Addressing Function Approximation Error Actor- Critic Methods. arXiv:1802.09477 [cs, stat], Oct. 2018. URL hwR.tttpp/aarii.orrg////// 09477. arXiv: 1802.09477.
[10] S. Lanka and T. Wu. ARCHER: Aggressive Rewards to Counter bias in Hindsight Experience Replay, arXiv:1809.02000 [cs, stat], Sept. 2018. URL http://arxins wtt.aaawww.....///./rrraaaaaaaae org/abs/1809 02070. arXiv: 1809.02070.
[11] R. Yang, J. Lyu, Y. Yang. J. Ya, F. Luo, D. Luo, Li, and X. Li. Bias-reduced Multi-step Hind- sight Experience Replay for Efficient Multi-goal Reinforcement Learning. 1rXiv:2102.12962 [cs), June 2021. URL http: /arxiviv... org/ htt//bb//200/ 12962. arXiv: 1292.
[12] C. Bai, I.. Wang, Y. Wang. 7. Wang, R. Zhao, C. Bai, and P. Liu. Addressing Hindsight Bias in Multigoal Reinforcement Learning. IEEE Transactions on Cybernetics, pages 1-14, 2021. ISSN 2275. 1. 100.1110//.BB.21....3.
[13] Dayan. Improving generalization for temporal difference learning: The successor representa- tion. Neural Computation, 5:613, 1993.
[14] S. M. Lavalle. Planning Algorithms. Cambridge University Press, 2006. ISBN 0521862000 1862051.

---

[15] S. Valalle Planning Algorithms. Cambridge University Press, University of Illinois, Urbana- Champaign, 2006.
[16] T. Dai. Hindsight Experience Replay implementation in Pytorch. URL https:h/tttthhi
10


Reviews:
[{"review_id": "hW_bNQTCOSs", "reviewer": "Reviewer_mpQg", "summary": "The paper proposed an algorithm that leverages importance sampling to unbias hindsight experience replay in stochastic environments. This is achieved by involving separate goals for rewards function and for the policy correspondingly. By conditioning both goals to the value function, a successor representation can be learned for importance sampling, where Bellman error using the representation provides unbiased error estimation. Concrete mathematical proof is provided to support the claim the HER is biased and how the algorithm could reach unbiased HER. Sufficient experiments were conducted in simulation to support the algorithm.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The developed algorithm is novel, challenging and interesting. It involves importance sampling to unbias - HER with concrete mathematical proof to verify the efficacy of the algorithm. \n- The paper is well written and easy to follow.\n- The design choices are reasonable and has been reflected in the ablation study.\n- Comprehensive simulation experiments were conducted to support the paper.\n\nWeaknesses:\nAlthough the simulation experiments are convincing. The Real robot experiment is a bit weak. Only 10 episodes were executed for each of the methods. Given the complexity, noise, uncertainty and domain gap posed by the real environment, 6/10 USHER vs 4/10 HER is far from enough to claim USHER outperforms HER. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "It is a solid paper that addresses bias in HER. The algorithm is backed by math and the simulation experiments are convinving. The only concern is the real world experiments. The sample size is inadequate to make any conclusions.", "technical_quality": "Very Good:  Convincing.", "clarity_of_presentation": "Very Good:  Well organized and clear.", "potential_impact": "", "robotics_focus": "Sufficient demonstration on hardware", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "4: The work contains interesting new ideas that will potentially have major impact in robotics or machine learning.", "issues": "See above", "reviewer_expertise": "3: The reviewer is fairly confident that the evaluation is correct"}, "extra_text": {}}, {"review_id": "O5GIAUsZm7", "reviewer": "Reviewer_d9ww", "summary": "This paper presents an algorithm to correct for the bias that’s introduced by the Hindsight Experience Replay (HER) algorithm for multi-goal / goal-conditioned RL. The proposed strategy is to separate out the goal used for the reward function from the goal passed to the policy. This allows the derivation of an unbiased variant of HER, using importance sampling. Practical application requires learning the future goal distribution, which is predicted as a separate head off of the existing Q network. Experiments show that this method performs significantly better than HER, as well as other previous unbiased variants of HER, specifically in stochastic environments crafted with HER’s weaknesses in mind. The experiments also show that the importance sampling doesn’t affect HER’s performance in deterministic environments, where bias isn’t a problem.\n", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- Paper is clear and the language is easy to read, although it looks like a few passages of text and equations may have compressed a bit due to space limitations. \n- The theory is original and novel, and experimental results back up the claims well.\n\nWeaknesses:\n- The “transfer” method used for real-robot application is to roll out trajectories in simulation, and then use the same sequence of actions on the real robot applied open-loop. Since the scenario being tested is fairly straightforward (i.e. it’s about picking one risky lane vs another safe one), it’s probably fine, but it doesn’t reflect how a policy might be used in practice.\n- How often does one encounter truly stochastic environments in robot applications? (I don’t claim to know the answer to this). Do you think this method will be equally helpful in cases of partial observability?\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "The paper proposes a novel method for unbiased HER in stochastic environments using importance sampling, and experimental evaluations attest to its effectiveness. It’s unclear how often this method will show a benefit in situations encountered in real-world policy learning, but the theory and algorithm are nonetheless a useful contribution to robot learning. I would accept this paper.\n", "technical_quality": "Excellent: Very convincing and thorough.", "clarity_of_presentation": "Very Good:  Well organized and clear.", "potential_impact": "", "robotics_focus": "Highly relevant to robotics but no hardware experiments", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "reviewer_expertise": "4: The reviewer is confident but not absolutely certain that the evaluation is correct"}, "extra_text": {"issues": "It would be nice if you used a consistent color for HER across all graphs (I think it’s different just for Fig 3a and 3b).\nIn some of the graphs where two of the curves are coincident, it just looks like one of the curves is completely missing. Some correction for this would be useful.\n"}}, {"review_id": "H40YQJanRiI", "reviewer": "Reviewer_KeLa", "summary": "This work addresses the “survivorship” bias present in Hindsight Experience Replay when in stochastic environments. In particular, the proposed method USHER estimates an importance weight to de-bias HER. USHER is then evaluated on various simulated robot environments, and the policy learned in one simulated environment is deployed on a physical robot.", "questions": "", "limitations": "", "rating": 2, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This work tackles an issue of HER in stochastic environments, and fixes it with importance sampling. To minimize the variance often associated with importance sampling, they simply clip the weights. The proposed method USHER is evaluated on a diverse set of experimental tasks, including discrete/continuous action spaces, deterministic/stochastic environments, and deployment on a physical robot.\n\nWeaknesses: My main concerns are on the experimental validation. Some of the comparisons are missing in some of the performance plots. For example, delta-DDPG and DDPG are missing from the Fetch Push/Slide and Throwing tasks. Also, in these plots, the x-axis is “Epochs,” but it’s not clear how this translates to the number of environment steps. From the experiments performed by Blier and Ollivier, it appears that delta-DQN and delta-PPO are able to achieve a near perfect success rate on FetchReach after about 250 and 1500 trajectories respectively. How do these translate into epochs?\n\nThere also appears to be multiple relevant algorithms that attempt to address bias in HER mentioned in the related work, which should be compared to, such as ARCHER, Bias-reduced Multi-step HER, and Bias-corrected HER. Even if these are tackling other forms of bias or incorrectly address bias, I believe they are relevant to compare to.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "This work addresses the bias of HER in stochastic environments through importance sampling. This method in theory should address the bias, but from the experimental evaluation, it’s difficult to gauge the advantages of USHER over existing methods. In particular, I believe the work can be improved in the following areas: clarifying the x-axis in the plots, inclusion of all comparisons in all of the experimental tasks, comparisons to additional methods, and sensitivity analysis for hyperparameters.", "technical_quality": "Good: Generally convincing, but some additional experiments or analyses needed.", "clarity_of_presentation": "Good: Minor revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Sufficient demonstration on hardware", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "3: The work is incremental and unlikely to have much impact, even though it may be technically correct and well executed.", "reviewer_expertise": "3: The reviewer is fairly confident that the evaluation is correct"}, "extra_text": {"issues": "There are a few hyperparameters for USHER like $\\alpha_Q$, $\\alpha_f$, and the clipping parameter. How are these chosen? How sensitive is USHER to these parameters? Does a clipping parameter of 0.3 work for all environments presented? These details appear to be missing from the main text and appendix, except for the Mechanum robot experiment which appears to use a clipping parameter of 100. "}}, {"review_id": "0N4JcS8vIZ0", "reviewer": "Reviewer_Z2DH", "summary": "The paper proposes a novel method to alleviate bias in hindsight experience replay (HER) using importance sampling. The authors present experiments on a range of environments which suggest that this method boosts performance beyond the original HER algorithm.", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n * The method seems interesting, and has potential to be impactful in the research community upon further experimental evaluation.\n * I don't have the theoretical expertise necessary to verify the authors' proofs, but the method seems to be grounded well in theoretical analysis.\n * The authors present results on robot hardware.\n * The abstract and introduction do a good job motivating the problem and introducing the authors' solution.\n\n# Weaknesses\n * A key weakness of the paper is presentation\n     * Algorithm 1 is far too crowded to be useful. The authors should replace some of the math with references to the rest of the text.\n     * For some reason when the authors show the environments in Figure 2, they only show a subset of them. For example, what is 4-Torus with Freeze? All environments included in the paper should be either explained in the main text or supplement.\n     * The results summary section is very disorganized. The authors present all of their results in a gigantic Figure 3 without any helpful captions or references to them in the text. The authors should reorganize this section to be more clear.\n * The authors' core claim is that their proposed method does a better job alleviating HER bias than other work (ARCHER, BHER) that has attempted to do the same in the past, but they never compare to any of this work in experiments. In order to contextualize this work with respect to other literature, these comparisons are critical.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "Overall, I think the method has promise and encourage the authors to address reviewer concerns during the rebuttal period. I feel that my main concerns about presentation issues and lacking comparisons make the paper unpublishable in its current state, but will happily increase my score if the authors can fully address these issues during the rebuttal period.\n\nThe theoretical results seem interesting but I don't have the expertise to evaluate them so I have not considered them while writing my review.", "technical_quality": "Fair: Significant additional evidence required to support the claims.", "clarity_of_presentation": "Fair: Major revision needed to improve organization or clarity.", "potential_impact": "", "robotics_focus": "Sufficient demonstration on hardware", "quality_of_limitations": "Limitations are addressed clearly", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"impact": "2: Unsure, difficult to assess.", "reviewer_expertise": "4: The reviewer is confident but not absolutely certain that the evaluation is correct"}, "extra_text": {"issues": "### Larger issues\n * The authors should spend some time reorganizing Section 6 to be easier to follow and give more details about the environments they use for evaluation.\n * The authors should modify Algorithm 1 to be more concise and useful.\n * The authors should add the comparisons to other algorithms they mention in the related works section.\n\n### Small Issues\n * Missing space on line 184\n * Should line 195 say $C < 1.0$?\n"}}]

Author rebuttal:

Decision: Accept (poster)