8
$\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$
1
  • $\begingroup$ Does LR decay actually solve your problem? From your result it seems the situation is mitigated but it is hard to see whether the policy can converge to the optimal one in a long term. $\endgroup$
    – hyyyyy
    Commented Jan 30 at 2:48

1 Answer 1

8
$\begingroup$

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

  1. You have been training your policy for too long on the same data distribution.
  2. Overfitting Q functions will then lead to data distribution mismatches more often in action selection and compounding errors will happen earlier than before.

You should probably train until 400 up to 600 episodes and then stop training the policy. Consider the following slide on compounding errors:

Data distribution mismatch and compounding errors

Whenever a wrong action is selected, because of overfitted Q value function, the agent can not generalize well on how to recover from that mistake. Eventually, compounding errors increase quadratically in time.

Compound errors are quadratic in time

It will only get worse for your agent once the wrong action is picked.

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 $

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

In the limit of exploration, they guarantee convergence to the optimal policy, for any Temporal Difference learning based algorithm. I would suggest you use a time-based decaying learning rate, which is the default choice in Keras when you set the decay parameter.

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

One iteration here means one epoch. You probably train your neural network every step taken by the agent, so one iteration means one epoch, one step taken by the agent.

In Keras you can set the decay like: model.compile(loss='mse', optimizer=Adam(lr=self.learning_rate, decay=decay_rate)) I would suggest a value of $0.001$, that should be a good starting point.

$\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
    Commented Jun 4, 2021 at 12:29
  • 1
    $\begingroup$ @Virus i edited the answer to elaborate a little longer in order to answer these questions $\endgroup$
    – devidduma
    Commented Jun 4, 2021 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
    Commented Jun 8, 2021 at 17:54
  • 2
    $\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
    Commented Jun 14, 2021 at 8:09

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .