# Why does Hindsight experience replay help addressing the problem of sparse rewards?

My question is about Hindsight experience replay which has been proposed for problem with sparse rewards. While the idea of this paper seems intuitive, I don't know why it can help in addressing the above issue. The following paragraph is from this paper. Any idea why it helps?

For example, in a game where at each time, the reward is -1 if state st is not equal to a goal g and +1 otherwise (st =g). Then, consider a state sequence s1, . . . , sT and a goal g which is not equal to any of s1, . . . , sT which implies that the agent received a reward of −1 at every timestep. The pivotal idea behind our approach is to re-examine this trajectory with a different goal — while this trajectory may not help us learn how to achieve the state g, it definitely tells us something about how to achieve the state sT . This information can be harvested by using an off-policy RL algorithm and experience replay where we replace g in the replay buffer by sT . In addition we can still replay with the original goal g left intact in the replay buffer. With this modification at least half of the replayed trajectories contain rewards different from −1 and learning becomes much simpler.

In the bit-flipping problem, for a bit sequence of length $n$, the algorithm has up to $n$ states (tries/steps) to achieve the target state. Since the number of possible states is $2^n$, this becomes ridiculously large for growing $n$. Already at $n=30$ there are a billion possible configurations to choose from. This issue of large state space is compounded by the problem that the reward is always -1, even if the current state differs from the target state by a single bit, i.e. there's no relative measure of closeness (i.e. a shaped reward function, such as the difference in bits between current and target state). So, despite learning transitions (i.e. how to get from one state to the next), there's essentially zero learning achieved unless the algorithm gets lucky and hits the target state, which happens with exceedingly rare probability as $n$ gets large. Moreover, even for small $n$, it still needs to wait sufficiently long enough to hit the target state.
The purported solution is as follows. Define secondary goals $g_i$ to be reaching previously visited states. So in the above example, you run the algorithm and get a sequence $(s_1,\cdots,s_T)$ along with the actions you took, which did not achieve your goal of $g$. You instead define a new goal $g_1=s_T$, and then sample from a set of goals $(g,g_1)$ via plugging these goals along with the last observed actions into the RL network. Since your sequence did achieve $g_1$, there is something learned here, in particular about the transitions $(s_1,\cdots,s_T)$.
The paper gives a good example of robotic arm training, where a shaped reward function might be detrimental to the algorithm: penalizing moving away from a cube might be bad in situations where the arm needs (would benefit) to make a maneuver that temporarily increases the distance from the cube. In the example of picking up a cube, since everything is done in simulation, you can check if the algorithm could have picked up a cube at state $s_T$ (and I think also $s_1,\cdots,S_{T-1})$.