[강화학습 Key Paper] Double DQN

본 포스트는 OpenAI에서 공개한 강화학습 교육자료인 Spinning Up의 도움을 받아, 강화학습(Reinforcement Learning, RL)에 대한 기초개념을 정리해보고자 제작한 시리즈의 일환입니다.

1)기초 지식 2)주요 논문, 3)최신 논문 의 순서로 시리즈를 정리하고자 합니다.

Spinning Up에서 정리해놓은 주요 RL 논문 중, 핵심 논문을 추려 리뷰를 진행합니다. 본 포스트를 읽기 전, 해당 논문을 가볍게 읽어보는 것을 추천합니다. Key idea에 대해 가볍게 파악할 시간을 가져보고자 합니다. 아래 링크에서 더욱 다양한 추천 논문을 찾아볼 수 있습니다.

Key Papers in Deep RL - Spinning Up documentation

What follows is a list of papers in deep RL that are worth reading. This is far from comprehensive, but should provide a useful starting point for someone looking to do research in the field.

https://spinningup.openai.com/en/latest/spinningup/keypapers.html

Double DQN

분류: Model-Free RL/Deep Q-Learning/Double DQN

이번 포스트에선 강화학습의 붐을 일으킨 DQN을 개선하고, 획기적인 성능향상을 일으킨 Double DQN에 대해 살펴보겠습니다. 역시 Google DeepMind에서 쓰인 논문입니다.

Abstract

Abstract을 함께 볼까요? 통상적인 DQN 사용시, large-scale function approximation에서 Q값이 overestimate되어 성능의 하락을 야기하기에, double Q-learning에 쓰였던 아이디어를 활용해 double DQN 알고리즘을 제안한다는 내용입니다. 이번 리뷰에서 등장할 가장 중요한 keyword는 overestimation이 되겠네요.

Overestimation

우리는 traditional DQN에서 아래와 같은 target을 사용하였습니다. 이는 과연 괜찮은 선택이었을까요?

$Y_t^{DQN} \equiv R_{t+1} + \gamma \max_aQ(S_{t+1},a;\theta_t^-)$

식에 등장한 $\max$ function은 우리의 function approximator가 쫓아가야할 target을 optimal값보다 크게 추정, 즉 overestimate해버립니다. 이는 neural net을 사용하지 않는 기본적인 Q-learning에서도 등장했던 문제로, 본 논문에선 아래와 같은 theorem을 제시합니다. Double Q-learning이 제안되는 계기가 되었죠.

$\max$ 를 사용할 시, 우리의 function approximator는 optimal value에 대해 항상 최소 $\sqrt{C\over{m-1}}$만큼의 bias를 가진다는 내용으로, environment에 의한 noise때문에 생기는 현상입니다. Optimal value 대비 아래의 Fig. 1처럼 상당한 값의 error를 갖게 됩니다.

이에 본 논문에선, 아래와 같이 target을 수정합니다.

$Y_t^{DDQN} \equiv R_{t+1} + \gamma Q(S_{t+1}, \argmax_aQ(S_{t+1},a;\theta_t) ;\theta_t')$

외부에 위치한 Q는 target network가 되겠고, 안쪽에 위치한 Q는 $\epsilon$-greedy policy로 environment와 상호작용하는 main network입니다. 백문이 불여일견! 아래의 diagram처럼 요약할 수 있습니다.

이전 DQN의 diagram에서 달라진 점을 노란 화살표로 나타내었습니다. 해당 부분 외에는 바뀐 사항이 없네요. 실험결과를 볼까요?

Fig. 2를 봅시다. 맨 왼쪽 column의 세 plot을 보면, optimal value $Q*$과 DDQN을 이용한 function estimate $Q_t$가 유사하게 나옴을 알 수 있습니다. 가운데 column의 세 plot을 보면 $\max$ function을 사용하였을 때 $Q*$에 비해 훨씬 큰 값을 가짐을 알 수 있고, 이를 overestimate되었다고 표현할 수 있겠습니다. 맨 오른쪽 column의 경우, $Q*$의 $\max$ 값과의 차이가 기존 DQN의 경우 0으로 수렴하지 않으며, 개선된 DDQN에서는 0으로 수렴함을 알 수 있습니다.

Fig. 3은 Atari game에서의 실험결과를 보여주고 있습니다. DQN의 경우 value estimate이 훨씬 크게 나오며, Asterix게임의 경우 overestimate가 일어나자마자 value가 급감하며 diverge함을 볼 수 있습니다. 하지만 DDQN은 상대적으로 stable하네요.

여타 case들에도 DDQN이 개선된 performance를 보여준다는 figure를 마지막으로 포스트를 끝내고자 합니다. Dueling DQN, rainbow DQN 등 여러 개선버전에 대해서는 천천히 알아보도록 하겠습니다.

Reference

[1] R. S. Sutton, A. G. Barto, et al., Introduction to reinforcement learning, vol. 135. MIT press Cambridge, 1998.

[2] OpenAI. Spinning Up, [Online]. Available: https://spinningup.openai.com/

[3] Deep Reinforcement Learning with Double Q-learning, Hasselt et al 2015.