Hindsight experience replay: strategy for sampling goals

The authors of Hindsight Experience Replay list out several strategies for sampling a set of additional goals $G$ in Section 4.5:

• final – corresponds with final state of environment,
• future — replay with k random states which come from the same episode as the transition being replayed and were observed after it,
• episode — replay with k random states coming from the same episode as the transition
  being replayed,
• random — replay with k random states encountered so far in the whole training procedure.

My interpretation of the future method is then that we can only select k random states if the current transition being replayed has already happened in the episode, so this is at minimum the second time we’ve seen the current transition. This seems very unlikely if working in an environment with a large state space (especially with continuous features). Am I missing something obvious in the interpretation of how to implement this strategy?