[논문 리뷰] Deep Reinforcement Learning with Double Q-learning (DDQN)

[1509.06461] Deep Reinforcement Learning with Double Q-learning (arxiv.org)

Deep Reinforcement Learning with Double Q-learning

이번 논문은 DQN에서의 target을 변형시켜서 overestimation을 해결한 Double DQN에 대해 리뷰할 것이다. DQN에 대한 리뷰는 아래 블로그 글을 참조하면 된다.

 

[논문 리뷰] Playing Atari with Deep Reinforcement Learning (DQN) — LimePencil's Log (tistory.com)

[논문 리뷰] Playing Atari with Deep Reinforcement Learning (DQN)

 

Abstract

The popular Q-learning algorithm is known to overestimate action values under certain conditions. It was not previously known whether, in practice, such overestimations are common, whether they harm performance, and whether they can generally be prevented.

이 논문에서는 Q-learning의 하나의 단점을 언급한다. Q-learning에서 action value를 overestimate 하는 경향이 있는데 이것을 해결할 수 있는지 탐색해 본다고 한다. 또한 제한된 환경에서만 쓸 수 있는 Double Q-learning을 generalize 하게 바꾸어서 DQN의 변형으로 사용하는 연구를 이 논문에 담았다. 이를 통해 기존 벤치마크보다 성능 향상을 보여준다고 한다.

 

Overestimation이 생기는 이유는 target을 계산할 때 max를 사용하기 때문에 그런데, uniformly overestimating 하다면 이 자체는 문제가 아니지만, 균일하지 않고 학습하고 싶은 state에 집중되어 있지 않다면 이는 성능에 영향을 줄 수 있다.

 

실제로 DQN에서 overestimation이 관찰되었고 이를 해결할 방안은 이 논문에서 제시한다.

 

Background

The max operator in standard Q-learning and DQN, in (2) and (3), uses the same values both to select and to evaluate an action. This makes it more likely to select overestimated values, resulting in overoptimistic value estimates. To prevent this, we can decouple the selection from the evaluation. This is the idea behind Double Q-learning.

Double DQN을 위해서는 두 가지의 사전 지식이 필요한데 이는 DQN과 Double Q-learning이다. DQN은 위에 있는 논문 리뷰에 잘 정리되어 있기 때문에 Double Q-learning에 조금 더 집중할 것이다.

 

Q-learning에서는 $Y_t^Q \equiv R_{t+1} + \gamma \underset{a}{\max}Q(S_{t+1},a;\theta_t)$이라는 타깃을 사용한다.

 

여기에서 DQN은 target network를 사용하여 $\theta$대신에 $\theta^-$을 사용하여 업데이트한다.

 

기존의 Q-learning은 같은 max operator이 action을 고르고 평가하는 데에 쓰이기 때문에 이것이 overestimation을 일으킬 수 있다. Double Q-learning은 이 두 개를 나누어서 계산한다. Double Q-learning에는 두 개의 weight $\theta$와 $\theta'$이 사용되는데 이 두 개 중에 하나를 랜덤 하게 골라서 업데이트한다. 하나는 greedy policy를 결정하는 데에 사용하고 나머지 하나는 그의 가치를 계산하는 데 사용한다.

 

식은 $Y_t^{DoubleQ} \equiv R_{t+1} + \gamma  Q(S_{t+1},\underset{a}{\mathrm{argmax}}Q(S_{t+1},a;\theta_t);\theta_t')$ 과 같고 online weight인 $\theta_t$만 업데이트된다. 두 개의 가중치를 바꾸어서 사용하면서 symmetrical 하게 업데이트할 수 있다.

 

Overoptimism due to estimation errors

In this section we demonstrate more generally that estimation errors of any kind can induce an upward bias, regardless of whether these errors are due to environmental noise, function approximation, non-stationarity, or any other source.

https://arxiv.org/pdf/1509.06461.pdf

이 파트에서는 estimation error이 environmental noise, function approximation, non-stationarity 등 때문에 생길 수 있다고 하고 upward bound와 lower bound를 구한다. 논문에서는 action의 개수가 올라갈수록 그냥 Q-learning은 error이 늘어나는 것을 볼 수 있다. 하지만 Double Q-learning을 사용하면 error이 action의 개수에 비례하지 않는다. 또한 특정한 value function에만 국한되는 현상이 아니기 때문에 이를 해결하는 게 accurate 하게 value function을 근사하는 방법이다.

 

Double DQN

We therefore propose to evaluate the greedy policy according to the online network, but using the target ne  twork to estimate its value. In reference to both Double Q-learning and DQN, we refer to the resulting algorithm as Double DQN.

Double DQN은 Double Q-learning + DQN이라고 보면 된다. target이 $Y_t^{DoubleDQN} \equiv R_{t+1} + \gamma  Q(S_{t+1},\underset {a}{\mathrm {argmax}}Q(S_{t+1}, a;\theta_t);\theta_t^-)$로 바뀌는 것 빼고 다른 것이 없다. 여기서 주목할 점은 target 네트워크로 evaluation을 하고 online network는 action selection을 한다는 것이다. 이 방식은 DQN의 장점을 가져가면서도 computationally expensive 하지 않게 성능을 올릴 수 있는 방법이다.

 

Empirical results

If seen in isolation, one might perhaps be tempted to think the observed instability is related to inherent instability problems of off-policy learning with function approximation. However, we see that learning is much more stable with Double DQN, suggesting that the cause for these instabilities is in fact Q-learning’s overoptimism.

Double DQN은 DQN보다 확실한 성능 향상을 보여준다. 같은 hyperparameter로 학습을 시켜도 더 좋은 결과를 보여주고, fine-tuning을 진행했을 때에는 더욱더 좋은 성능을 보여주었다. 이는 저자들이 말한 overoptimism이 성능을 저하시키는 원인이라는 것을 보여준다.

 

Discussion & Conclusion

Q-learning은 큰 환경의 문제에서 overoptimistic 하는 경향이 있고 이를 저자들은 Double Q-learning을 DQN에 접목한 DDQN이라는 새로운 아키텍처를 제안한다. DDQN은 overestimation을 줄이고, Atari 2600 벤치마크에서 SOTA를 기록하는 결과를 보여주었다. 또한 DDQN은 DQN을 크게 바꾸지 않기 때문에 periority experience replay나 dueling DQN 같은 다른 향상 방법을 적용할 수 있다.