One challenge in sparse reward tasks with high-dimensional state space is deriving a policy for long horizon. On one hand, while planning algorithms work well for task that determining a distance between states and designing local policy is easy, it is problematic when it comes to high-dimensional observations. On the other hand, even though RL algorithms work well with high-dimensional observations, they fail to solve some tasks in long horizons. To achieve the benefit of planning and RL algorithms, a combined algorithm is presented in [1]}. In this approach, the task is decomposed into a series of easier goal-reaching tasks and the problem of finding these sub-goals is reduced to a shortest path problem using a distance metric. By defining the reward value as -1 for every move until reaching a goal, the Q function and the shortest path would be closely connected. Using the distance between nodes, a directed graph is built on top of the states in a replay buffer in which each node corresponds to an observation. This graphs finds a set of nodes showing the shortest path from the start state to the goal state and the goal-based policy starts to find the goal by reaching intermediate goals one after each other.
