Experience Replay Not Always Giving Better Results

I have recently started working on a control problem using a Deep Q Network as proposed by DeepMind (https://arxiv.org/abs/1312.5602). Initially, I implemented it without Experience Replay. The results were very satisfying, although after implementing ER, the results I got were relatively bad. Thus I started experimenting with BATCH SIZE and MEMORY CAPACITY.

• (1) I noticed that if I set BATCH SIZE = 1 and MEMORY CAPACITY = 1 i.e. the same as doing normal online learning as previously, the results are then (almost) the same as initially.

• (2) If I increased CAPACITY and BATCH SIZE e.g. CAPACITY = 2000 and BATCH SIZE = 128, the Q Values for all actions tend to converge to very similar negative values.

A small negative reward -1 is received for every state transition except of the desired state which receives +10 reward. My gamma is 0.7. Every state is discrete and the environment can transition to a number of X states after action a, with every state in X having a significant probability.

Receiving a positive reward is very rare as getting to a desired state can take a long time. Thus, when sampling 128 experiences if 'lucky' only a small amount of experiences may have a positive reward.

Since, when doing mini-batch training we average the loss over all the samples and then update the DQN I was wondering whether generally the positive rewards can become meaningless as they are 'dominated' by the negative ones. Which means that this would result in a very slower convergence to actual values ? And also justifies the the convergence to similar negative values as in (2) ? Is this something expected? I am looking to implement. Prioritised ER as a potential solution to this, but is there something wrong inn the above logic?

I hope this does makes sense. Please forgive me if I make a wrong assumption above as I am new to the field.

Edit: The problem seemed to be that indeed finding rewards very rarely would result in sampling almost never, especially at the begging of training, which in turn resulted in very slow convergence to the actual Q values. The problem was successfully solved using Prioritised ER -but I believe any form of careful Stratified Sampling would result in good results

• Just curious, are you using a duplicate network to store the network weights after every $C$ updates, and using the duplicate network to calculate the expected value of state action pairs for the DQN update error term? (Ie “q-hat”) – Hanzy Apr 29 '19 at 15:48
• Thank you for your comment. If I understand correctly, yes I am using a target net (fixed Q values) which I update every. 10 episodes. – George Papagiannis Apr 29 '19 at 15:53
• sorry if I ask more questions, just trying to get a sense of your implementation. When you used batch size = 1 and capacity = 1, did you also use the same target network updated after 10 episodes? When doing the “online” version you are really training on policy rather than off policy, since every update is following a trajectory. So that’s why I’m curious to know what factors changed between the two. Off policy learning with function approximation and bootstrapping (what Sutton / Barto call the “deadly triad”) is known to face issues of stability. – Hanzy Apr 29 '19 at 16:26
• Yes, so when batch size = 1 and capacity = 1 I use the exact same configuration. I have the main policy net Q and target net Q_hat. I get the action to perform using Q. I calculate the error using Q_hat for the new state and I update Q_hat every 10 episodes. I sample from ER every time I perform an action on the environment and train – George Papagiannis Apr 29 '19 at 16:30
• this sounds like an off-policy problem to me. What you proposed seems reasonable... since you’re training off policy and sampling out of trajectory AND averaging over the updates, it seems reasonable it could effect your performance. This is a bit of a hack, but can you try making your reward for goal states >= batch size? I’ll expand more of this idea in an answer since I’m limited by characters here. – Hanzy Apr 29 '19 at 16:52

What you describe sounds to me like a problem inherent to off policy learning, and what you describe seems to me to be a reasonable interpretation of what may be happening.

When you implemented experience replay with capacity = 1 and batch_size = 1 you said you got “almost” the same results as before. There are probably two reasons for this being “almost” the same. One is simply the random initializations of the networks, so as you train, you will potentially converge around the same point but not exactly to it (also the stochastic nature of generating the training samples). The other reason might be to do with what has already occurred each time you update the target net weights, so your error terms may differ slightly at each point in time, but asymptotically converge.

This is essentially following an on policy training, so every training sample is following a trajectory (they are all sequential states). Eventually, given enough time, this trajectory will reach a goal state and be rewarded. The reward will be propagated through the network and effect the backed up values of other states will be updated as well. So essentially each episode ends with a reward (I presume), and the average reward given per episode is proportional to the average length of an episode.

When increasing capacity and batch size > 1, we move to true off policy training. When sampling, the updates are not following a trajectory. And as such, there is no guarantee that we EVER sample any positive reward (although, I’m sure you will at some point). So, if we are averaging over the rewards in the updates, the average reward given per “episode” is no longer proportional to the average episode length (and the idea of episode starts to lose some of its relevance - since we aren’t following a trajectory). This the effect of the reward on all other states is not in proportion to what it was when following an on-policy trajectory.

You could try some hacks to investigate, for example try making your positive reward > batch_size. Or, if you have some statistics on how often your goal state is being sampled, perhaps scale it up by that factor. (Or if you know the size of your state space, make your reward greater than that).

This blog post offers some more elegant refinements, like prioritized ER which you mentioned. But it would be interesting to see the effect of scaling up your reward will overcome the effect of averaging over many negative rewards.

• This makes perfect sense and I understand your idea behind changing the positive received reward. Just one note, a positive reward is not always received received as the goal is to reach a desired state in a specific number of steps. Although, the principle behind no longer sampling from a trajectory and reducing the chances of having a positive reward is true. I will go ahead and change the reward. I will update you with the results – George Papagiannis Apr 29 '19 at 17:36
• @GeorgePapagiannis I would be very interested to hear what you find. Again, other options may be more elegant and fruitful, but this would be the easiest to implement and may provide insight on if what you describe really is having the effect observed. Please do update! – Hanzy Apr 29 '19 at 17:37
• Something I also noted in your reply @Hanzy. Why is it that it's not really off-policy whenI train online during interaction with the environment, since I still use to different networks (Q_main, Q_target)? Many thanks :) – George Papagiannis May 3 '19 at 13:29
• @GeorgePapagiannis I guess it lives somewhere in between since you are training based on your policy (since every step is sequential) but bootstrapping from something slightly different from your policy (although, it’s really a time delayed copy of your policy and very correlated). I wouldn’t really consider it “off policy” in the same sense as when you are “taming actions” according to a different policy and then updating the value function based upon that series (which is basically what we are doing when we sample replay). – Hanzy May 3 '19 at 14:25
• thank you very much for your explanation. I’m still a 2nd year undergrad so I’m not very experienced and that’s why I keep asking, but I do understand your point. Also, I edited my initial question to include a response to this and following our previous conversations indeed Prioritised ER indeed fixed the problem and I also believe any time of stratified (or targeted) sampling would improve the solution as long as you can make sure a positive reward is actually sampled. Thanks again :))!! – George Papagiannis May 3 '19 at 19:57