10
$\begingroup$

I'm reading Barto and Sutton's Reinforcement Learning and in it (chapter 11) they present the "deadly triad":

  1. Function approximation
  2. Bootstrapping
  3. Off-policy training

And they state that an algorithm which uses all 3 of these is unstable and liable to diverge in training. My thought is, doesn't deep Q-learning hit all 3 of these? It certainly uses function approximation in the form of a deep neural network, it uses bootstrapping since it's a form of Temporal Difference learning so its updates are based on future Q-values, and it uses off-policy training because its value updates utilizes the maximum of the future time-step Q-values whereas the policy being trained (the behavior policy) might not be a greedy algorithm.

It seems to me then that deep-Q learning should be inherently unstable. Is this true, or is my understanding wrong somewhere? If it is in fact inherently unstable, a follow up question would be, is it unstable in practice? I.e. is there a wide class of problems for which deep-Q learning would be unstable, or is it generally still fine to use deep-Q learning for the vast majority of problems but there are some small set of problems for which deep-Q learning might be unstable?

Improve this question
$\endgroup$

1 Answer 1

Reset to default
2
$\begingroup$

Given that tricks such as replay memory, gradient clipping, reward clipping, carefully selected rollout strategies, and the use of a target network are often necessary for achieving reasonable performance, and even then training can be unstable, yes, it seems to be true in practice.

That doesn't mean it doesn't work in practice -- DeepMind's Atari paper showed it is indeed possible, with the help of aforementioned tricks. However, it is fairly challenging and requires tens of millions of steps to train properly.

Improve this answer
$\endgroup$
3
  • $\begingroup$ I've seen some sources talking about training instability, but they seem to focus on overfitting. By unstable, I mean that the value estimates can diverge as training occurs instead of converging to some value. Is Deep-Q Learning theoretically unstable in this sense? $\endgroup$
    – enumaris
    Commented Jun 13, 2018 at 3:35
  • $\begingroup$ @enumaris yes, it can be unstable in that sense, but I also meant unstable as in the performance of the policy wildly varies from epoch to epoch, the loss is all over the place, etc. Unstable in this sense does not prevent the network from eventually performing well. I believe diverging value estimates is usually solved using those tricks mentioned in my answer. $\endgroup$
    – shimao
    Commented Jun 13, 2018 at 3:41
  • $\begingroup$ I have seen more than one question regarding emulating DQN's success on Atari games, where the results have been unstable, and fixes include adding a target network (delayed copy of learning network) plus usually adjusting hyper-parameters for batch size and size of delay between learning network and target network. The behaviour when these are wrong can be similar to when learning rate is set too high. I would say this backs up this answer that DQN is inherently unstable, but still usable with a little patience thanks to the additions. $\endgroup$
    – Neil Slater
    Commented Jun 13, 2018 at 9:11

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.