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.

 A: This is a reasonable question, as the details in the paper are somewhat terse. My understanding is as follows. 
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)$. 
This toy example is a little frustrating because in this case, you're very conveniently replacing the desired goal by a morally equivalent goal of getting to a different state (i.e. by "resampling" your training data). Whereas the goal of the paper is to apply this technique to problems where the auxiliary goals are less clear. Thats why I think the overall message here is how to quickly learn the possible action state space transitions, so that you can more intelligently explore your state space, as opposed to just randomly trying things in the beginning as you never actually observe the reward. 
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})$.
