4
$\begingroup$

I am implementing some "classical" papers in Model Free RL like DQN, Double DQN, and Double DQN with Prioritized Replay.

Through the various models im running on CartPole-v1 using the same underlying NN, I am noticing all of the above 3 exhibit a sudden and severe drop in average reward (with a sudden and significant increase in loss) after achieving peak scores.

After reading online, I can see that this is a recognized problem but I cant find a suitable explanation. Things I have tried to mitigate:

  • adapt model architecture
  • tune hyperparams like LR, batch_size, loss function (MSE, Huber)

This problem persists, and I cannot seem to achieve any sustained peak performance.

Useful links I found:

Example:

  • till ~250 episodes in Double DQN with PR (with annealing beta), performance steady goes up in both increase in reward and decrease in loss
  • after that stage, the performance dips suddenly in both decreased average reward and increased loss as seen in output below
Episode: Mean Reward: Mean Loss: Mean Step
  200 : 173.075 : 0.030: 173.075
  400 : 193.690 : 0.011: 193.690
  600 : 168.735 : 0.015: 168.735
  800 : 135.110 : 0.015: 135.110
 1000 : 157.700 : 0.013: 157.700
 1200 :  99.335 : 0.013: 99.335
 1400 :  97.450 : 0.015: 97.450
 1600 : 102.030 : 0.012: 102.030
 1800 : 130.815 : 0.010: 130.815
 1999 :   89.76 : 0.013: 89.76

Questions:

  • what is the theoretical reasoning behind this? Does this fragile nature mean we cannot use the above mentioned 3 algorithms to solve CartPole-v1?
  • if not, what steps can help mitigate this? Could this be overfitting and what does this brittle nature indicate?
  • any references to follow up with regarding this "catastrophic drop"?
  • I observe similar behavior in other environments as well, does this mean that the above mentioned 3 algorithms are insufficient?

Edit: Taking from @devidduma's answer, I added time based LR decay to the DDQN+PRB model and kept everything else same. Here are the numbers, they look better than before in terms of the magnitude of the performance drop.

   10 : 037.27 : 0.5029 : 037.27
   20 : 121.40 : 0.0532 : 121.40
   30 : 139.80 : 0.0181 : 139.80
   40 : 157.40 : 0.0119 : 157.40
   50 : 225.10 : 0.0107 : 225.10 <- decay starts here, factor = 0.001
   60 : 227.90 : 0.0101 : 227.90
   70 : 227.00 : 0.0087 : 227.00
   80 : 154.30 : 0.0064 : 154.30
   90 : 126.90 : 0.0054 : 126.90
   99 : 154.78 : 0.0057 : 154.78

Edit:

  • after further testing, pytorch's ReduceLROnPlateau seems to be working best with patience=0 param.
$\endgroup$
3
$\begingroup$

This is a case of overfitting the Q function leading to compounding errors when selecting actions.

  1. You have been training your neural network as function approximator for too long on the same data distribution, so the neural network loses it's ability to generalize and slowly starts overfitting, i.e. learns the data exactly as it is or at least very closely.
  2. Overfitting Q functions will then lead to data distribution mismatches more often in action selection and compounding errors will happen earlier than before.

Judging from the table you have posted, you should probably train until 400 up to 600 episodes and then stop training the neural network.

Compounding errors are a well known issue in autonomous driving. Consider the following slide from Stanford lectures on reinforcement learning:

Data distribution mismatch and compounding errors

The slide is actually treating this problem in the specific case of imitation learning, but the concept of data distribution mismatch and compounding errors can be applied in your case too. Basically, whenever a wrong action is selected because of overfitted, biased Q value function, the agent does not have any more data on how to recover from that mistake, even more so when the Q function is overfitted.

Moreover, compounding errors were at first considered to increase linearly in time, but this is not true. They increase rather quadratically in time, as you can see from the following slide.

Compound errors are quadratic in time

It will only get worse for your agent once the wrong action is picked. I am not sure if the following advice is going to work in order for you to continue training without stopping, but you could give it a try.

In Temporal Difference learning methods like TD-0, SARSA or Q learning, finite-state and finite-action MDP's converge to the optimal action-value if the following two conditions hold:

  1. The sequence of policies $\pi$ is Greedy in the Limit of Exploration (GLIE)
  2. The learning rates $\alpha_t$ satisfy the Robbins-Munro sequence such that:
  • $ \sum^{\infty}_{t=1} \alpha_t = \infty $
  • $ \sum^{\infty}_{t=1} \alpha^2_t < \infty $

Than being said, you can infer that by any means we should use a decaying learning rate in order to satisfy the Robbins-Munro sequence. There are three types of decaying learning rates:

  • time-based decay
  • step-decay
  • exponential decay

Each one of these does guarantee convergence to the optimal policy, of course in the limit of exploration for any Temporal Difference learning based algorithm. Without going into much details, I would suggest you use a time-based decaying learning rate with the following formula:

$ lr = 1 / (1 + decay\_factor * iteration) $

Time-based decay is what is provided by default in Keras when you set the decay parameter when building the neural network. One iteration here means one epoch. In your case, you probably train your neural network every step taken by the agent, so one iteration = one epoch = one step taken by the agent.

In Keras setting the decay should look like the following: model.compile(loss='mse', optimizer=Adam(lr=self.learning_rate, decay=decay_rate)) Provide there any value that you see fit for the decay rate. I would suggest a value of $0.001$. Try and tune this hyperparameter if it does not work with $0.001$, although that value should be a good starting point.

Give it a try and tell me if it fixes your problem.

$\endgroup$
4
  • $\begingroup$ that makes sense! What alternatives do we have other than early stopping? Does this problem of compounding errors exist in other algorithm classes which use temporal difference learning like SARSA and so one? $\endgroup$ – Virus Jun 4 at 12:29
  • 1
    $\begingroup$ @Virus i edited the answer to elaborate a little longer in order to answer these questions $\endgroup$ – devidduma Jun 4 at 14:48
  • 1
    $\begingroup$ @Virus I just gave a new idea you could try that could fix the problem you were facing. Let me know. $\endgroup$ – devidduma Jun 8 at 17:54
  • $\begingroup$ thanks for adding the theory background to your answer! Its exactly what I was looking for, I have added the new performance numbers after a bit of tinkering with the ideas you mentioned. The results are promisingly better, with the drops being smaller but still there. I start the time - based decay after epoch 50, and kept it at 0.001 which works well. $\endgroup$ – Virus Jun 14 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.