Answers.Body: <p>This is a case of <em><a href="https://en.wikipedia.org/wiki/Overfitting" rel="nofollow noreferrer">overfitting</a></em> the Q function leading to <em>compounding errors</em> when selecting actions.</p>
  <ol>
  <li>You have been training your policy for too long on the same data distribution.</li>
  <li>Overfitting Q functions will then lead to <em>data distribution mismatches</em> more often in action selection and <em>compounding errors</em> will happen earlier than before.</li>
  </ol>
  <p>You should probably train until 400 up to 600 episodes and then stop training the policy. Consider the following slide on compounding errors:</p>
  <p><a href="https://i.sstatic.net/2BFRA.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/2BFRA.png" alt="Data distribution mismatch and compounding errors" /></a></p>
  <p>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 <em>quadratically</em> in time.</p>
  <p><a href="https://i.sstatic.net/8BJG6.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/8BJG6.png" alt="Compound errors are quadratic in time" /></a></p>
  <p>It will only get worse for your agent once the wrong action is picked.</p>
  <p>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:</p>
  <ol>
  <li>The sequence of policies <span class="math-container">$\pi$</span> is Greedy in the Limit of Exploration (GLIE)</li>
  <li>The learning rates <span class="math-container">$\alpha_t$</span> satisfy the Robbins-Munro sequence such that:</li>
  </ol>
  <ul>
  <li><span class="math-container">$ \sum^{\infty}_{t=1} \alpha_t = \infty $</span></li>
  <li><span class="math-container">$ \sum^{\infty}_{t=1} \alpha^2_t &lt; \infty $</span></li>
  </ul>
  <p>You can infer that by any means we should use a <em>decaying</em> learning rate in order to satisfy the Robbins-Munro sequence. There are three types of decaying learning rates:</p>
  <ul>
  <li>time-based decay</li>
  <li>step-decay</li>
  <li>exponential decay</li>
  </ul>
  <p>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 <em>time-based decaying</em> learning rate, which is the default choice in Keras when you set the <code>decay</code> parameter.</p>
  <p><span class="math-container">$ lr = 1 / (1 + decay\_factor * iteration) $</span></p>
  <p>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.</p>
  <p>In Keras you can set the decay like:
  <code>model.compile(loss='mse', optimizer=Adam(lr=self.learning_rate, decay=decay_rate))</code>
  I would suggest a value of <span class="math-container">$0.001$</span>, that should be a good starting point.</p>
  
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T12:29:15.650Z
Answers.Text: 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?
Answers.UserDisplayName: Virus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-04T14:48:48.757Z
Answers.Text: @Virus i edited the answer to elaborate a little longer in order to answer these questions
Answers.UserDisplayName: devidduma
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-08T17:54:06.130Z
Answers.Text: @Virus I just gave a new idea you could try that could fix the problem you were facing. Let me know.
Answers.UserDisplayName: devidduma
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-14T08:09:24.703Z
Answers.Text: 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.
Answers.UserDisplayName: Virus
Answers.ContentLicense: CC BY-SA 4.0
Answers.CreationDate: 2021-06-03T23:00:39.463Z
Answers.LastActivityDate: 2023-01-17T09:49:48.950Z
Answers.LastEditDate: 2023-01-17T09:49:48.950Z
Answers.UserDisplayName: devidduma
Body: <p>I am implementing some &quot;classical&quot; papers in Model Free RL like DQN, Double DQN, and Double DQN with Prioritized Replay.</p>
  <p>Through the various models im running on <code>CartPole-v1</code> 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.</p>
  <p>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:</p>
  <ul>
  <li>adapt model architecture</li>
  <li>tune hyperparams like LR, batch_size, loss function (MSE, Huber)</li>
  </ul>
  <p>This problem persists, and I cannot seem to achieve any sustained peak performance.</p>
  <p><strong>Useful links I found</strong>:</p>
  <ul>
  <li><a href="https://ai.stackexchange.com/questions/12627/what-could-be-causing-the-drastic-performance-drop-of-the-dqn-model-on-the-pong">What could be causing the drastic performance drop of the DQN model on the Pong environment?</a></li>
  </ul>
  <p><strong>Example:</strong></p>
  <ul>
  <li>till ~250 episodes in Double DQN with PR (with annealing beta), performance steady goes up in both increase in reward and decrease in loss</li>
  <li>after that stage, the performance dips suddenly in both decreased average reward and increased loss as seen in output below</li>
  </ul>
  <pre><code>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
  </code></pre>
  <p><strong>Questions:</strong></p>
  <ul>
  <li>what is the theoretical reasoning behind this? Does this <code>fragile</code> nature mean we cannot use the above mentioned 3 algorithms to solve <code>CartPole-v1</code>?</li>
  <li>if not, what steps can help mitigate this? Could this be overfitting and what does this brittle nature indicate?</li>
  <li>any references to follow up with regarding this &quot;catastrophic drop&quot;?</li>
  <li>I observe similar behavior in other environments as well, does this mean that the above mentioned 3 algorithms are insufficient?</li>
  </ul>
  <p><strong>Edit:</strong>
  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.</p>
  <pre><code>   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 &lt;- 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
  </code></pre>
  <p><strong>Edit:</strong></p>
  <ul>
  <li>after further testing, pytorch's <code>ReduceLROnPlateau</code> seems to be working best with <code>patience=0</code> param.</li>
  </ul>
  
Comments.ContentLicense: CC BY-SA 4.0
Comments.CreationDate: 2024-01-30T02:48:35.987Z
Comments.Text: 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.
Comments.UserDisplayName: hyyyyy
Tags: <q-learning><deep-rl><gym><double-q-learning>
Title: Deep Q-Learning "catastrophic drop" reasons?
UserDisplayName: Virus
ThreadText: # Deep Q-Learning "catastrophic drop" reasons?
  
  (Asked by: username_0 on 2021-06-03)
  
  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**:
  
  * [What could be causing the drastic performance drop of the DQN model on the Pong environment?](https://ai.stackexchange.com/questions/12627/what-could-be-causing-the-drastic-performance-drop-of-the-dqn-model-on-the-pong)
  
  **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 @username_2'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.
  
  **Tags:** q-learning, deep-rl, gym, double-q-learning
  
  > **Comments:**
  > **username_1**: 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.  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_2 on 2021-06-03. Score: 8
  
  This is a case of *[overfitting](https://en.wikipedia.org/wiki/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](https://i.sstatic.net/2BFRA.png)](https://i.sstatic.net/2BFRA.png)
  
  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](https://i.sstatic.net/8BJG6.png)](https://i.sstatic.net/8BJG6.png)
  
  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.
  
  > **Comments:**
  > **username_0**: 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?  
  > **username_2**: @username_0 i edited the answer to elaborate a little longer in order to answer these questions  
  > **username_2**: @username_0 I just gave a new idea you could try that could fix the problem you were facing. Let me know.  
  > **username_0**: 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.  
  
  ---
  
  