# Hindsight Experience Replay: what the reward w.r.t. to sample goal means

Referring to the paper on Hindsight Experience Replay

Is it right that sampled goals which are visited states should be followed by a positive (or non-negative) rewards in order to allow an agent learn?

On page 5 of the paper, a "Algorithm 1 Hindsight Experience Replay (HER)" scheme reads in particular:

for t = 0, T-1 do
r_t := r(s_t, a_t, g)
Store the transition (s_t || g, a_t, r_t, s_(t+1) || g) in R

Sample a set of additional goals for replay G := S(current episode)
for g' ∈ G do
r' := r(s_t, a_t, g')
Store the transition (St||g', a_t, r', s_(t+1)||g') in R
end for
end for


where:

g : current goal
R : replay buffer

All other symbols with a dash indicate that they were sampled in addition to the actual current goal within the current episode.

It means (as long as I understand) that for the sampled goals (g') the reward is now a function of action taken in state given the sampled goal. It is not very clear whether the agent will learn the task in case the reward is still the old function (which is non-positive for all states that are different from the final goal).

As an example, in a grid-world an agent gets -1 reward while not in the final cell of its destination, but with the new goals introduced, the agent's reward with respect to its current state is not r, but r' (reward after reaching goal).

Illustrating example (grid-world): • Where is the relevant section in the paper? Aug 13 '18 at 13:07
• @n1k31t4, I clarified my question and added the citation from the paper. Aug 13 '18 at 14:41
• What are the green blocks in your diagram? Aug 15 '18 at 17:02
• @n1k31t4, the green boxes are future states visited after the current state in the same episode. Aug 15 '18 at 17:22
• Arrows indicate which goals can potentially be stored in the replay buffer: original goal, final state, or some other visited states. Aug 15 '18 at 17:38

... the reward is now a function of action taken in state given the sampled goal.

I believe the action taken is that from the original goal, not from the newly sampled goal (as you say you understand). Otherwise I think you have everything more or less correct.

We see in the first block of the algorithm, that each action $a_t$, given the current goal, g, results in the reward, $r_t$ (as usual). This is stored, along with the new state $s_{t+1}$ concatenated with the current goal (shown by the || symbol). This is highlighted as being standard experience replay.

In the second block, using the sampled (virtual) goals $g'$, we receive a virtual reward for our performance using the same action as previously $a_t$. This is repeated for some number of simulated goals, selected by a sampling strategy, of which several are discussed in Section 4.5.

I myself was wondering how many replays are sampled, as it seems that the key there is to sample enough, so that the buffer itself sees the right balance of additional goals (to reduce the reward density), but not so much that the virtual HER recordings from the second for-loop do not outnumber the real performed goal-action pairs from the first loop. In the paper (Section 4.5), this seems to be around the $k=8$ mark, where $k$ is the ratio of sampled/virtual goals to the original goals.

So I believe the sampled goals that are indeed visited states from the original goal, would indeed receive a non-negative reward.

I think the following is a key statement to help explain the intuition:

Notice that the goal being pursued influences the agent's actions but not the environment dynamics and therefore we can replay each trajectory with an arbitrary goal assuming we have an off-policy RL algorithm like DQN ...

This is very true in life. Imagine you try to throw a frisbee straight across a field to a friend. It doesn't make it, instead flying off to the right. Although you failed, you could learn that the wind is perhaps blowing left to right. If that had just so happened to be the task at hand, you would've received some positive reward for it! The authors sample many additional goals, which in my analogy, may be the flight dynamics of that particular frisbee, the air density/humidity etc.

The main contribution of this paper, is a method to increase the density of the reward function i.e. to reduce how sparse the reward is for the model while training. Sampling these additional goals after each attempt (failed or otherwise) gives the framework the opportunity to teach the model something in each episode.

In the grid-based example, if for example the agent doesn't reach the final goal (as its original goal), it records -1 to the replay buffer. Then other goals are sampled from the possible next steps according to a sampling strategy, $\mathbb{S}$. For If you were close to the goal, it would make sense that sampling from future states selected at random from the same episode - after the transition - that you would likely end up at the goal. It is important here to realise that the goal has changed, which allows reward to be received. I point this out because the goal usually doesn't change in grid-based games; however, the experiments in the paper were performed on a robotic arm with 7-DOF in continuous space (only the reward was discrete).

EDIT

Below is a sketch of an example path, where we reach the final goal after 10 transitions (blue arrows). I set $k = 4$, so in each of the states $s_t$, we also have 4 randomly selected goals. We then take the corresponding action $a_t$ for the current state, which is the blue arrow. If the randomly sampled goal, $g'$, happens to be the same as $s_{t+1}$, we get a non-negative reward - these are the orange arrows. Otherwise, a negative reward is returned: the green arrows. This is an example of the random sampling strategy, as my sampled goals $G$, are states that have been encountered in the whole training procesdure (not just the current episode), even though you cannot see it in my sketch.

So here we see there are 4 sampled goals, whch do indeed return non-negative reward. That was chance. The authors do say that:

In the simplest version of our algorithm we repla each trakectory with the goal $m(s_T)$, i.e. the goal which is achieved in the final state of the episode.

In that case, it would mean $k=1$ and is always simply where the episode ended. This would mean negative rewards in the HER portion of the algorithm for all time steps exluding the final, $t=T$, where we would reach the sampled goal.

That would indeed equate to the model having learned from an otherwise failed episode. In every single episode!

• Thank you for an answer. w.r.t. I believe the action taken is that from the original goal, not from the newly sampled goal (as you say you understand). it is a misunderstanding! "the reward is now a function of action taken in state given the sampled goal". Here the emphasis is on the reward, not on action, so the reward is in accordance with the sampled goal in presence of state and taken action. Aug 14 '18 at 10:24
• In the paper (Section 4.5), this seems to be around the k=8 mark, where k is the ratio of real goals to virtual goals. I think there is inaccuracy here. Citing section 4.5: "All of these strategies have a hyperparameter k which controls the ratio of HER data to data coming from normal experience replay in the replay buffer." So it seems that 8 is how many additional replays should be added to 1 natural trajectory. Aug 14 '18 at 10:59
• however, the experiments in the paper were performed on a robotic arm with 7-DOF in continuous space (only the reward was discrete). Without loss of generality their example can be extended to discrete cases, I believe. In either robotic arm or grid world agent must make huge number of actions to get a non-negative reward (I added illustrative picture to my question). However it is not intuitive why future visited states as sampled goals would generate a non-negative reward for the current state, since they can be very far away. Looks it just works without explanation, huh? Aug 14 '18 at 12:58
• @AlexeyBurnakov - (1) I don't understand your point exactly, and cannot find that quote in the paper. (2) I agree with you - I misread the paper and have corrected my answer. (3) Assume that future visited states are more likely than random states from the episode's starting point. Now if we make a future state a sampled goal, the probability of a reward increases. Furthermore, the simplest case is that we make the final state the sampled target, meaning a reward is guaranteed. All of this leads to a faster mapping of the reward space. Aug 15 '18 at 17:06
• @AlexeyBurnakov - I know what you mean. I am not 100% sure I understand the authors. I have added a sketch to my answer for $k = 4$, where the sampled goals do, in some cases, coincide with $s_{t+1}$, meaning we would expect a non-negative reward. Aug 15 '18 at 20:22