3
$\begingroup$

Assume we have a deterministic game and we want to train an agent using Deep Q-Learning (a.k.a. DQN) to play this game. We record the score of the agent at each episode and plot the scores versus the episode numbers. Assume the maximum score of the game is 1 and the minimum is -1.

Now, my question is this: if we trained an agent for 300k episodes and observed after a while the agent learns to get the score of 1 and it keeps doing that for the first 100k. However, after that, the score drops to around -1 and stays there until 300k-th episode. What can be the reason for this phenomena? Although the agent learns to play the game perfectly for a long time, why it suddenly forgets it?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

This is called "catastrophic forgetting", and seems to occur quite frequently in DQN.

The problem you are seeing might go something like this internally (note this is a hand-wavy/conjecture argument, I have not measured thi happening numerically):

  • The agent learns a near-optimal strategy.

  • It follows that strategy, and only explores close to it.

  • The transition history becomes saturated with states and actions seen close to optimal behaviour, and that more often than not gain long-term rewards of optimal behaviour.

  • The model parameters, in order to obtain the best loss for those states, change so that they predict action values as accurately as possible for the current distribution of states and actions.

  • The accuracy of predictions for less-frequently seen states/actions gets worse due to over-fitting. Initially this is not noticed, because those state/action pairs are not being visited.

  • Eventually, a prediction for a bad action choice somewhere in the environment becomes high enough to get that action selected, perhaps whilst exploring. This makes the agent explore a "bad neighbourhood" of states and actions with low rewards.

  • The neural network tries to correct the predictions whilst taking these bad actions, but now the internal representations that were focused on the optimal path only work against it - any correction to this erroneously high prediction for a bad action will at least initially change parameters so that the values of all optimal state/actions are also reduced.

  • Depending on how far the over-fitting went before the agent made a poor enough prediction that made it misstep, it could either recover relatively quickly, or take a long time. The high error signals comparing predicted value against actual value could even cause it to diverge.

Some fixes to this are the same as for over-fitting - add regularisation to the neural network, test your progress (use monte-carlo estimates of the agent following the Q values perfectly over some number of episodes).

You might also be tempted to adjust what is stored in replay memory. It may help if you find a simple heuristic for this, or perhaps you are able to start the agent in a variety of random starting states. However, in general this is a really hard unsolved problem - the statistical dataset/population base assumed for supervised ML is not a perfect match for learning Q-functions, which don't have quite the same relationship to populations of observed transitions - at least not while exploring and learning optimal/better control.

There is ongoing research into this problem, with various proposed fixes, such as Overcoming Catastrophic Forgetting by Incremental Moment Matching.

$\endgroup$
8
  • $\begingroup$ Thanks for your comprehensive answer. For my case, the drop in the scores happens long after end of exploration phase (when epsilon became 0.01). Considering the fact that the environment of my problem is deterministic, can I set the minimum epsilon to 0 (instead of 0.01) to avoid the agent exploring those states with bad predictions? $\endgroup$
    – user491626
    Jul 2, 2018 at 21:13
  • 1
    $\begingroup$ @user491626: You can reduce epsilon, and that may help keep the estimates stable, but that is essentially the same as stopping learning. Minh et al.'s suggestion is similar to "early stopping" regularisation. $\endgroup$ Jul 2, 2018 at 21:40
  • 1
    $\begingroup$ @user491626 If you think you have finished learning, then the value of epsilon is irrelevant in Q learning. Set it to zero in order to just use the best policy found. If you want to continue learning, then epsilon needs to be non-zero (best value depending on problem at hand). It is not always clear what the maximum score is, you will instead have measures of best score so far. Most of the Atari games played by DQN were not "solved" with a theoretical max score. In a deterministic game, you may still worry about distribution of start states. In a 2-player game, worry about opponent's policy. $\endgroup$ Jul 2, 2018 at 21:55
  • 1
    $\begingroup$ @user491626: I'm not sure. Part of the problem is that generalisation (against one population) can actually work against you (derived feature representations in hidden layers get specialised to single population, and don't re-set fast enough in another population). Having less params won't necessarily save you from this "generalisation error leads to population shift" problem. As with supervised learning there is likely to be an optimal combination of hyperparameters, but that is not the entire answer. $\endgroup$ Jul 3, 2018 at 6:58
  • 1
    $\begingroup$ Your question was specifically about Q Learning in DQN. However if you are facing lots of problems like this in environments you want to solve, it may be worth looking at policy gradient methods, such as Actor-Critic (A3C or A2C implementations) - policy gradients modify policy less radically on finding errors (no max function that will just switch action when an action reaches top of a sorted list), and can be more robust to the effect as a result. $\endgroup$ Jul 3, 2018 at 7:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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