In normal Q-learning, the update rule is an implementation of the exponential moving average, which then converges to the optimal true Q values. However, looking at DQN, how exactly is the exponential moving average implemented in deep networks?


However, looking at DQN, how exactly is the exponential moving average implemented in deep networks?

It is not implemented directly as exponential moving average.

Instead, the ability of neural networks to learn online and incrementally forget older input/output associations is used to achieve the same goal.

If you use the simplest mini-batch stochastic gradient descent methods - i.e. just a simple gradient step $\mathbf{w} \leftarrow \mathbf{w} - \alpha \nabla_{\mathbf{w}}\sum_i(g_i - \hat{q}_i)^2$ where $g_i$ is measured (or bootstrap estimated) discounted return for a single state/action pair and $\hat{q}_i$ is the current estimate, then the learning rate $\alpha$ is analagous to the same factor in exponential moving average approach, and in fact would be the same thing mathematically if you one-hot-encoded the states and only had a single layer in the neural network.

Typical implementations of DQN will have deeper networks, will not one-hot-encode the entire state space, and will typically use some gradient modifier such as momentum or Adam to improve performance. So the match to exponential moving average is not exact. But the behaviour is similar in the most important aspect for RL - the ability to learn online and forget older values as the target distribution of expected returns changes due to changes in policy.

  • $\begingroup$ I don’t quite understand this fully, but what you’re tying to say is, the exponential moving average and the update of the weights are essentially the same mathematically ? $\endgroup$ – Chukwudi Ogbonna Aug 23 '20 at 11:47
  • $\begingroup$ Can you refer me to the mathematical proof of the SGD being the same as the exponential moving average $\endgroup$ – Chukwudi Ogbonna Aug 23 '20 at 11:50
  • $\begingroup$ @ChukwudiOgbonna: I don't have a reference, but it is trivial because fully enumerated linear "approximation" is exactly the same as tabular, and the weights become the Q table. You won't find many references because it is not a very interesting result. No-one uses DQN in a way that the updates are directly equivalent. Just similar behaviour of online learning, as described in the last paragraph in this answer. $\endgroup$ – Neil Slater Aug 23 '20 at 13:49
  • $\begingroup$ Thank you for your time, I appreciate , I don’t know if I should really bother my self with the maths aspect, what do you think $\endgroup$ – Chukwudi Ogbonna Aug 23 '20 at 14:13
  • $\begingroup$ @ChukwudiOgbonna: If you want to understand RL well enough to alter or implement algorithms yourself, it is worth working on the maths. In this particular case you are looking at a minor issue though, so you could skip it with the broad understanding that all that matters is the online learning behaviour which exponential moving average and neural network training by gradient descent both produce. The numerical equivalence in a special case (which never happens in real problems) is not too important, and other forms of forgetting old inputs might be equally good. $\endgroup$ – Neil Slater Aug 23 '20 at 14:39

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.