Abstract
Q-Learning algorithm의 경우 특정 조건에서 action value를 과대평가하는 것으로 알려져 있다.
https://arxiv.org/abs/1312.5602
Playing Atari with Deep Reinforcement Learning
We present the first deep learning model to successfully learn control policies directly from high-dimensional sensory input using reinforcement learning. The model is a convolutional neural network, trained with a variant of Q-learning, whose input is raw
arxiv.org
Q-Learning을 Deep Learning과 접목시킨 DQN Algorithm은 "Playing Atari with Deep Reinforcement Learning"이라는 논문에서 처음으로 등장했다. 이 경우 Atari 2600 doamin의 몇몇 게임들에서 상당한 Overestimation이 존재한다는 것을 확인할 수 있었고, 이를 해결하기 위해 본 논문에서는 Double Q-Learning algorithm을 만들어서 large-scale function approximation으로 일반화를 하려고 시도했다. 결과적으로 이전에 관측되던 Overestimation이 줄어들었고, 성능도 몇몇 게임에서는 DQN보다 향상되었다고 한다.
흔히 말하는 Reinforcement Learning의 목표는 순차적인 decision problem의 최적의 해결책을 future reward를 최적화하는 과정을 통해 찾는 것이다. DQN이 등장하기 이전, Q-Learning은 강화학습에서 가장 최적의 솔류션으로 알려져 있었지만, estimated action value에 대해 maximization step이 들어가 있기 때문에 overestimated 되는 경향이 존재한다는 점이 단점이었다. Overestimation은 성능에도 좋지 않은 영향을 미치기 때문에 이를 해결할 방법이 필요했다.
하지만, Overestimation은 획일적이지 않고, 우리가 학습하고자 하는 것에만 분포하고 있는 것도 아니기 때문에 결과로 도출되는 policy의 quality에 부정적인 영향을 미칠 가능성이 존재한다.
이에 대한 해결책으로 DQN이 나오게 되었고, Deep Learning이 강화학습에서도 효과적인 방법이 될 수 있다는 가능성을 보였다. 하지만, DQN 마저도 Overestimate를 하는 경향은 여전히 존재했기 때문에 Double DQN이라는 알고리즘이 등장하게 된다.
Background
Sequential decision problem을 해결하기 위해 각각의 action에 대해 최적의 estimation을 학습해야 하는데, 이 과정을 위의 식과 같이 future reward의 기댓값으로 구할 수 있다. 이를 통해 optimal policy는 각각의 state에서 가장 높은 값을 갖는 action을 선택함으로써 유도될 수 있다.
Optimal action value는 Q-learning으로 학습될 수 있는데, 가장 흥미로운 문제는 모든 state들에서 모든 action value들을 별개로 학습하기에는 너무 크다는 점이다. 그래서 이 방법 대신에 SGD와 유사한 parameterized value function을 사용해서 구했다고 한다.
Deep Q Networks
DQN은 Multi-layered Neural Network로 주어진 state에 대해 action value의 vector를 output으로 전달한다.
DQN의 2가지 중요한 요소는 target network와 experience replay를 사용한다는 점이다.
그 다음으로 Experience replay의 경우는 특정 시간에 저장을 해놓고 저장해 놓은 memory bank에서 uniform sampling을 통해 network를 update한다.
결과적으로 Target network와 Experience replay는 알고리즘의 성능 향상에 크게 기여했다고 한다.
Double Q-learning
Q-learning과 DQN의 공통점은 max operator를 쓴다는 점인데, 이 max operator에서는 action을 select하고 evaluate할 때 같은 값들을 쓴다. 이로 인해 overestimated value를 선택할 가능성이 높아지고, overoptimistic value estimate를 야기하게 된다.
그럼 같은 값을 쓰는 것을 막으면 되는게 아닌가?
그래서 연구자들은 selection과 evaluation 과정을 분리했고, 이것이 Double Q-learning의 background idea이다.
Overoptimisim due to estimation errors
Q-learning의 overestimation은 action value가 uniform distribution에서 random error를 갖고 있다면 [m-1]/[m+1]로 target이 overestimated된다는 것을 발견한 Thrun과 Schwartz에 의해 처음 연구되었다고 한다.
여기 이 사람들이 제시한 Theorem이 있다. 논문 뒷편에 Appendix에 이 Theorem에 대한 증명이 있어서 따라서 증명을 해보았다.
https://en.wikipedia.org/wiki/H%C3%B6lder%27s_inequality
Hölder's inequality - Wikipedia
From Wikipedia, the free encyclopedia Inequality between integrals in Lp spaces In mathematical analysis, Hölder's inequality, named after Otto Hölder, is a fundamental inequality between integrals and an indispensable tool for the study of Lp spaces. H
en.wikipedia.org
이 Theorem을 통해 주목해야할 점은 다른 action에 대한 estimation error는 independent하기 때문에 가정할 필요가 없다는 점이다.
Figure1을 봐도 알 수 있듯이 Q-learning의 overestimation [빨간색]은 action의 개수에 비례하게 증가하는 반면, Double Q-learning [파란색]의 경우 action의 개수와 상관없이 unbiased 분포를 보여주고 있다. 이를 통해 Theorem1에서 나온 결론인 overoptimism이 [m-1]/[m+1]이 된다는 것이 입증이 되게 된다.
그 다음으로 Figure2를 보면, 주로 함수 근사와 overestimation에 대한 결과를 그래프로 표현하고 있다.
- 제일 위의 행과 중간 행을 비교하면, 상단과 중간 행에서의 차이는 True Value Function인데 이는 과대평가가 특정한 참 값 함수에 의존하지 않음을 나타낸다. 즉, 과대평가는 어떤 True Value Function이라도 발생할 수 있다는 것을 보이고 있다.
- 중간과 하단 행에서의 차이는 함수 근사의 flexibility에 있다. 중간 행의 왼쪽 그래프에서는 함수가 충분히 flexible하지 않아서 일부 샘플 상태에서 잘못된 추정값을 보인다. 반면에 하단 행의 왼쪽 그래프에서는 보다 flexible한 함수 근사를 사용했으나, 이는 미탐색 상태에서 높은 estimation error를 발생시키며 결과적으로 overestimation을 유도하게 된다. 이 부분은 강화 학습에서 자주 사용되는 flexible한 함수 근사기가 이와 같은 문제를 일으킬 수 있음을 시사한다.
- 이 실험에서는 이미 true value에 대한 샘플이 있다고 가정했음에도 overestimation이 발생하며, 이는 잘못된 추정치가 부트스트랩[bootstrapping]을 통해 전파되기 때문인데 이는 강화 학습 과정에서 overestimation이 policy learning의 quality에 안좋은 영향을 미칠 수 있음을 보여준다. 특히, 상태 및 행동 간의 상대적 가치가 왜곡되어 optimal policy learning을 방해할 수 있습니다.
Double DQN
Double Q-learning에 대한 idea는 위에서 설명했듯이 target에서의 max operation을 action selection과 action evaluation 과정으로 분해해서 overestimation을 줄이는 것이다. Double DQN에 대한 식을 수식으로 표현하면 다음과 같다.
여기서의 Double DQN은 DQN에서 Double Q-learning으로의 최소한의 변화를 의미하는데 이를 통해 얻고자 하는 건 Double Q-learning에서 챙길 수 있는건 최대한 많이 챙기면서 computational overhead를 줄이는 것이라고 한다.
Empirical results
Results on overoptimism
Figure3은 DQN의 Atari에서 6개의 게임을 실행했을 때의 Overestimation을 보여주고 있다. 주황색으로 보이는 DQN의 경우, 현재의 greedy policy에 대해 consistent하고 때때로는 광범위하게 overoptimistic한 모습을 보인다. 이 값은 다음 수식으로 계산된다고 한다.
반면에 파란색으로 보이는 Double DQN의 경우 final policy의 true value인 파란색 굵은 직선에 거의 근사한 모양을 보인다. 이 말은 Double DQN이 단순히 더 정확한 value를 estimate하는 것 뿐만 아니라 더 나은 policy를 만들어낸다는 것을 알 수 있다.
더 극단적인 overestimation은 "Asterix"와 "Wizard of Wor"라는 게임에서 매우 불안정한 모습을 보이는 가운데 2개의 plot에서 확인할 수 있다. 아래 2개의 plot은 이 2게임에 대한 score를 보여주는데, 주목할 점은 가운데 plot에서 DQN의 estimaed value의 증가폭과 아래쪽 plot의 score의 감소폭이 우연히 일치한다는 점이다.
이 말인 즉슨, overestimation이 policy의 quality를 떨어뜨리는데 영향을 준다는 말과 일치한다.
Quality of the learned policies
지금까지 overoptimism이 무조건 안좋은 녀석이라고만 했는데, 이 녀석이 그렇다고 항상 학습된 policy에 안좋은 영향을 미치는 것은 아니다.
예를 들어, DQN의 경우 policy value를 약간 overestimate했음에도 Pong에서 최적의 behavior를 달성했다. 하지만 확실한건 overestimation을 줄이면 learning의 안정성에는 매우 큰 장점이 된다는 점이다. 그래서 저자들은 DQN에서 test 했던 방식 그대로 49개의 게임에 대해 Double DQN이 얼마나 도움이 되었는지 policy quality 관점에서 평가했다고 한다.
Table 1,2를 보면, DQN과 Double DQN의 중간값과 평균이 5분동안 했을 때는 20% 정도의 향상이 있었지만, 30분 동안 했을 경우 2배 이상의 차이를 보일 정도로 큰 차이를 보인다는 것을 확인할 수 있다.
Robustness to Human starts
이전의 evaluation에서의 한가지 걱정거리는 시작점이 정해져 있는 게임의 경우 learner가 action의 순서를 기억할 수 있기 때문에 generalize에 많은 노력을 들이지 않아도 된다는 점이다. 이렇게 되면 성공을 하더라고 robust하지 않게 된다는 점이 문제가 된다.
따라서 agent들을 여러 starting point에서 testing 함으로써 이 걱정거리를 해결할 방법을 찾았다고 한다.
연구원들은 각각의 game에서 100개의 starting point들을 얻어서 108,000 frame까지 emulator를 동작시켰다고 한다.
참고로 이 평가 과정에서는 hyperparameter를 tuning한 tuning 버전 Double DQN도 추가했다고 한다.
그랬을 때의 결과는 위와 같이 된다고 한다.
여러 게임들에서 DQN과 Double DQN의 차이는 엄청난 차이를 보이고 몇몇 케이스들에서는 score가 인간과 비슷하거나 심지어 넘어서기도 했다고 한다.
이를 통해 Double DQN이 더 어려운 evaluation에 대해 robust하다는 것을 확인할 수 있었다고 한다.
Discussion
이 논문이 기여한 점은 다음 5가지로 정리할 수 있다.
- Q-learning이 inherent estimation errors of learning 때문에 deterministic한데도 불구하고 왜 large-scale problem에서 overoptimistic한지를 보였다
- Atari game을 통해 value를 분석함으로써 이러한 overestimation은 실제로 이전에 알고 있던 것 보다 더 흔하고 심하다는 것을 알 수 있다.
- Double Q-learning이 성공적으로 overestimation을 줄이고, 더 stable하고 reliable한 learning을 한다는 것을 보였다
- Double DQN이라는 방식을 제시해서 추가적인 network parameter 없이 기존의 architecture와 DQN algorithm의 Deep Neural Network를 사용했다
- Double DQN이 더 나은 policy들을 찾고, Atari 2600 domain에서 SOTA 성능을 보인다는 것을 확인했다.
아까 증명했던 Theorem1의 증명 내용이다.
그리고 이건 estimation error가 어떻게 [m-1]/[m+1]에 근사하게 되는지를 증명한 내용이다.
강화학습 자체가 수식이 복잡하고 난잡?하기 때문에 수식에 대한 이해가 필요할 것 같다.
여기까지가 Double DQN에 대한 논문 분석이였습니다. 내용자체가 어렵다보니 제가 이해한 내용이 전부 맞지는 않다는 점 참고부탁드립니다.
-강화학습 시리즈는 계속 됩니다-