<p>You are right. There is no direct association between memory (experience replay) and the performance of the model in episode reward. The Q-value in DQN is used to predict each action's expected reward in each step. The performance measure of how good your model was is the difference between the real reward and the expected reward (TD-error). </p>

<p>The deployment of -1 for non-goal steps is a trick to help RL models to choose the actions that can finish the episode quicker. Because of the Q-value is an action-value. At each step, the model predicts rewards for every possible move and the policy (usually greedy or epsilon-greedy) choose the action with the most significant value. You can imagine that going back at one moment will result in 200 steps to finish the episode but going forward takes only 100 steps. The Q-value will be -200 (without discount) and -100 respectively. You might wonder how the model knows the value of each action, that is because in the repeated episodes and successive trial-and-error. The model was trained to minimise the difference between real reward and expected reward, aka TD-error.       </p>

<p>In a randomly sampled experience replay, all experiences are sampled and deleted uniformly. However, in priority experience replay, you can reuse those experience with high estimated error. Usually, the priorities are proportional to the TD error (real_reward - expected_reward) of expected Q-value and the current model's predicted Q-value. The larger the priority means how surprising the experience, and it helps accelerate the training.</p>

<p>You can check the idea in <a href="https://arxiv.org/pdf/1511.05952.pdf" rel="nofollow noreferrer">Priority Experience Replay, Schaul et al., 2016</a> </p>
How does DQN work in an environment where reward is always -1
<p>Given that the OpenAI Gym environment <a href="https://github.com/openai/gym/blob/master/gym/envs/classic_control/mountain_car.py" rel="noreferrer">MountainCar-v0</a> ALWAYS returns -1.0 as a reward (even when goal is achieved), I don't understand how DQN with experience-replay converges, yet I know it does, because I have <a href="https://gist.github.com/keithmgould/f99296260b4a739ac6b523ad71e1ec90" rel="noreferrer">working code</a> that proves it. By working, I mean that when I train the agent, the agent quickly (within 300-500 episodes) learns how to solve the mountaincar problem. Below is an example from my trained agent. 
<a href="https://i.stack.imgur.com/odrPU.gif" rel="noreferrer"><img src="https://i.stack.imgur.com/odrPU.gif" alt="enter image description here"></a></p>

<p>It is my understanding that ultimately there needs to be a "sparse reward" that is found. Yet as far as I can see from the openAI Gym <a href="https://github.com/openai/gym/blob/master/gym/envs/classic_control/mountain_car.py" rel="noreferrer">code</a>, there is never any reward other than -1. It feels more like a "no reward" environment.</p>

<p>What almost answers my question, but in fact does not: when the task is completed quickly, the <strong>return</strong> (sum of rewards) of the episode is larger. So if the car never finds the flag, the return is -1000. If the car finds the flag quickly the return might be -200.  The reason this does not answer my question is because with DQN and experience replay, those returns (-1000, -200) are never present in the experience replay memory. All the memory has are tuples of the form (state, action, reward, next_state), and of course remember that tuples are pulled from memory at random, not episode-by-episode.</p>

<p>Another element of this particular OpenAI Gym environment is that the Done state is returned on either of two occasions: hitting the flag (yay) or timing out after some number of steps (boo). However, the agent treats both the same, accepting the reward of -1. Thus as far as the tuples in memory are concerned, both events look identical from a reward standpoint.</p>

<p>So, I don't see anything in the memory that indicates that the episode was performed well.</p>

<p>And thus, I have no idea why this DQN code is working for MountainCar.</p>