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

Question

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):

Answer 1

... 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!