[논문] Deep Reinforcement Learning with Double Q-learning
카테고리: Papers
0. Abstract
DQN같은 Q-learning 알고리즘은 특정 조건에서 action-value를 overestimate하는 것으로 알려졌다.
하지만 이 문제점에 대해서 이전까지는 다음과 같은 질문의 답을 알 수 없었다
- overestimate가 왜 일어나는지?
- overestimate가 일반적으로 일어나는 현상인지?
- overestimate가 Q-learning 성능에 안좋은 영향을 주는지?
- overestimate를 막을 수는 있는지?
이 논문에서는 이러한 질문에 대한 답을 제공한다.
1. Introduction
overestimate는 왜 발생할까?
Q-learning은 강화학습에서 가장 유명한 알고리즘 중 하나이지만, 때때로 비현실적으로 높은 action-value를 학습하는 것으로 알려져있다. 왜냐하면 그것은 underestimated value보다 overestimated를 선호하는 경향이 있는 action value를 maximization하는 단계를 포함하기 때문이다.
즉, DQN에서의 Q값(action value)은 추정치이기 때문에 오차가 존재할 수 있다. 그 추정치가 실제 값보다 overestimated되었다면 max연산에 의해 그것을 선택할 확률이 높다.
overestimate는 무조건 성능에 부정적인 영향을 끼칠까?
overestimations가 발생했을 때 이게 무조건 성능에 부정적인 영향을끼치는 것만도 아니다.
- 모든 values가 균일하게 높다면, 그것이 정책을 더 나쁘게 할것이라고 예상하지는 않는다.
- optiministic한 것의 장점인 optimisim in the face of uncertainty같은 exploration technique도 있다.
하지만 overestimations는 균일하지 않고, state에 집중되어 있지도 않다. 그래서 정책의 퀄리티에 부정적인 영향을 끼칠수 있다.
실제로 overestimate가 발생을 하는가?
그렇다면 실제로 overestimations가 발생을 하는지 알아보기 위해서 DQN의 최상의 시나리오로 세팅을 하고 테스트를 해도 가끔씩 action-value overestimate가 일어나는 것을 확인했다.
overestimate를 막기위한 해결책 : DDQN
tabular setting에서 처음 제안된 Double Q-learning 알고리즘은 function approximation와 deep neural network를 통해 일반화될 수 있다 이것을 활용해 만든 Double DQN을 보여준다.
DDQN은 더 정확한 value estimate를 계산하고, 몇 개의 게임에서 더 좋은 점수를 얻게했다.
이것은 DQN의 overestimate는 더 안좋은 정책을 만들고 그것을 줄이는 것이 유익하다는 것을 입증했다.
2. Background
2.1 Q-Learning
action-value를 구하는 수식은 다음과 같다.
Optimal Value는 action-value중 가장 큰 값이 Optimal한 value이고
Optimal Policy는 각 state에서 optimal value를 선택하는 action을 하는 것이다.
Q-learning은 모든 State에서 모든 Action에 대한 value를 학습하기 때문에 연산량이 많다는 문제가 존재한다. 그래서 Q-value function을 파라미터화해 그 파라미터화를 학습한다.
이제 Target인 \(Y_t^Q\)방향으로 현재 Value \(Q(S_t, A_t; \theta _t)\)를 업데이트 하는것으로 생각할 수 있다.
2.2 Deep Q Networks
주어진 State s에 대해 action-value \(Q(s,a;\theta)\)의 vector를 출력하는 multi-layered NN이다.
n-dimensional state space와 m개의 action을 포함하는 action space의 경우 NN은 \(R^n\)부터 \(R^m\)까지의 함수이다.
DQN 알고리즘의 2가지 중요한 idea는 target network와 experience replay이다. 그리고 이 방식이 DQN 알고리즘의 성능을 급격하게 향상시켰다.
Target network
파라미터 \(\theta^-\)로 구성된 target network는 online network와 모두 동일하지만, 파라미터 \(\theta^-\)는 매 \(\tau\)-step마다 online network의 파라미터인 \(\theta\)로 복사된다. 즉 \(\tau\)-step마다 \(\theta_t^- = \theta_t\)가 되고 다음 주기가 올때까지 유지된다.
Experience replay
관찰된 transition(state, action, next_state, reward)가 replay buffer(Memory)에 저장되며, batch_size 보다 커지면 이 Memory에서 랜덤하게 sampling해 학습을 진행한다.
링크 DQN
2.3 Double Q-learning
Standard Q-learning과 DQN에서 사용하는 max 연산자에서 action을 선택하고 평가하는데 같은 Value를 사용한다.
기존의 DQN의 Target Y는 action을 선택과 평가할 때, 동일한 파라미터 \(\theta_t\)를 사용한다.
이것은 action을 평가할 때도 greedy policy가 적용되기 때문에 overestimated value를 선택할 확률이 높아져 overestimated value를 과도하게 추정한다.
이것을 방지하기 위해, 평가와 선택을 분리하자는 idea가 Double Q-learning이다.
Double Q-learning 알고리즘은 두 개의 value function를 학습한다. 즉 weights \(\theta\) 과 \(\theta'\)가 있다.
각 experience를 무작위로 선택하여 두 개의 value function중 하나를 업데이트하도록 할당한다.
각 업데이트마다 한 세트의 weight는 greedy policy를 결정하고 다른 것은 value를 결정한다.
action의 선택은 여전히 argmax 연산을 통해 online weight \(\theta_t\)에 의해 결정된다.
이는 기존 Q-learning과 마찬가지로, \(\theta_t\)에 의해 결정된 현재 values를 통해 greedy policy의 value를 평가한다.
하지만 이 정책의 value 평가를 공평하게 하기 위해 두번째 weight 세트인 \(\theta'\)를 사용한다. 그리고 이 것은 \(\theta\)와 \(\theta'\)의 역할을 바꿔서 대칭적으로 업데이트 될수도 있다.
3. Overoptimism due to estimation errors
Q-learning의 overestimation 발생
- action value에 random errors가 포함되어 있고, 이 error가 \([-\epsilon, \epsilon]\) 사이에서 균등하게 분포한다고 가정했을 때 Q-learning의 Target은 최대 \(\gamma\epsilon\frac{m-1}{m+1}\) 까지 overestimated 할 수 있다. (m : actions의 수)
- environment에서 발생하는 noise가 overestimation으로 이어질 수 있다.
기존의 연구는 overestimate가 위의 경우에 발생할 수 있다고 주장했다.
하지만 이 논문에서는 원인의 종류에 상관없이 초기에 true values를 알 수 없기 때문에 생기는 부정확한 action value가 overestimation을 일으킨다고 주장한다.
3.1 Theorem 1
어떤 state s에서 모든 true optimal action values가 동일하다고 가정한다. 즉 아래와 같은 수식이 성립하는 state s를 고려해보자
\(Q_t(s,a)\)가 true value라면 아래의 수식이 성립한다.
하지만 \(Q_t(s,a)\)의 error가 발생하는 경우(True value가 아닌 경우)
max연산자 사용하면
다음과 같이 하한을 구할 수 있다. 즉, Q-learning은 최소 \(\sqrt\frac{C}{m-1}\) 만큼 overestimate 한다는 것이다.
같은 조건에서 Double Q-learning estimation의 absolute error 하한은 0이다. (Appendix 1)
Orange Bar : Single Q-learning bias
Blue Bar : Double Q-learning bias
⇒ Single Q-learning의 bias가 Double Q-learning의 bias보다 크고, 그것은 action 수가 많아질 수록 극대화 되는 것을 볼 수 있다.
True value and an estimate
보라색 선 : true values \(V_*(s)\)
초록색 선 : estimated values
초록색 점 : sampled states
중간 그래프를 보면 6차 다항식 \(Q_t(s,a)\)가 모든 true value의 sample를 포함하지 못한다.(the function approximation is insufficiently flexible) 즉, esimated value가 부정확 하다.
하단 그래프를 보면 9차 다항식 \(Q_t(s,a)\)가 모든 true value의 sample를 포함하기는 하지만(function is flexible) unsampled state에 대해서 정확도가 떨어진다.
flexible 해질수록 unseen state에 대해서 높은 estimation error를 유발한다는 것을 알 수 있다. (갑자기 튀어 오르는 부분) 이것이 중요한게 flexible parametric function approximators는 종종 RL에서 사용된다는 것이다.
이를 통해 overestimations가 꽤 일반적으로 일어난다는 것도 알 수 있다.
All estimates and max
녹색 선 : estimate aciton value for all action
점 선 : max estimate action value
여러 개의 녹색선이 있는 이유는 서로 다른 sample state로 학습을 진행했기 때문이다. 이때 max estimate action value(점선)은 대부분의 optimal action value(보라색 선)보다 값이 크다.
Bias as function of state
주황색 선 : Bias at Single Q-learning
파란색 선 : Bias at Double Q-learning
Single Q-learning은 upward bias를 포함하기 때문에 거의 항상 양의 bias를 갖는다. 반면 Double Q-learning은 거의 0에 가깝거나 Single Q-learning에 비해 작은 bias 값을 갖는다.
즉, Double Q-learning이 overestimate를 성공적으로 줄인 것을 알 수 있다.
4. Double DQN
Double Q-learning의 idea는 overestimations를 줄이기 위해 target의 max 연산을 action selection과 action evaluation을 나누는 것이다.
완전히 분리되지는 않았지만, DQN의 target network는 추가 networks없이 두번째 value function에 대한 후보를 제공한다.
따라서 online network를 통해 greedy policy를 평가하고, target network를 사용해 그것의 value를 평가한다.
Double Q-learning과 DQN 모두 참고하여 만든 알고리즘이 Double DQN이다.
이 알고리즘의 업데이트 방식은 기존 DQN과 동일하지만, DQN에서 사용하는 Target \(Y_T^{DQN}\)을 \(Y_t^{DoubleDQN}\)으로 대체한다.
Double Q-learning과 비교했을 때, 기존의 Second network의 weight \(\theta'_t\) 대신, Target network의 weight \(\theta^-_t\)를 사용하여 현재 Greedy policy의 Value를 평가한다.
또한, Target Network의 업데이트 방식은 기존 DQN과 동일하게, 주기적으로 Online network의 weight를 복사하여 업데이트하는 방식을 유지한다.
이러한 Double DQN 방식은 DQN을 Double Q-learning으로 변경하는 최소한의 수정으로 볼 수 있다.
즉, Double Q-learning의 장점을 최대한 활용하면서도, 기존 DQN 알고리즘의 나머지 부분을 그대로 유지하여 공정한 비교를 가능하게 하고, 추가적인 연산 비용을 최소화하는 것이 목표이다.
4.1 Empirical results
상단 그래프의 주황색 : DQN의 value estimation, true value
상단 그래프의 파란색 : Double DQN의 value estimation, true value
DDQN이 DQN보다 더 낮은 estimate를 만들고, true와 estimate의 차이도 작다.
즉, DDQN이 더 정확한 estimation을 하고, 더 나은 정책을 만들어 낸다.
하단 그래프를 보면 Training steps간의 Score를 알 수 있다.
DQN의 overestimate가 발생하면(급격히 value estimate 증가 부분) DQN의 Score가 감소를 한다.
즉, DDQN을 통해 overetimate를 방지하면 학습을 더 안정적으로 할 수 있다.
4.2 Quality of the learned policies
Overoptimisim이 항상 정책 학습에 안좋은 영향을 끼치는 것은 아니다. 예를 들어 Pong 같은 경우 약간의 Overestimate가 있긴 했지만 DQN을 통해 좋은 성과를 냈다.
하지만 overestimate를 줄이는 것이 학습을 안정적으로 할 수 있다는 것을 위 그래프를 통해 확인했다.
DDQN이 DQN에 비해 일반적으로 얼마나 좋은지 알아본다.
정확한 비교를 위해 DDQN과 DQN은 Target Y를 제외하고 모든 파라미터를 같게 하고 각 게임의 Score를 다음과 같이 normalize 했다.
위 표를 통해 DDQN이 DQN보다 좋다는 것을 확인할 수 있다.
4.3 Robustness to Human starts
determinisitc 게임에서 한가지 걱정되는 것은 같은 시작 지점에서 시작하면 일반화하는 것이 아니라그 자리에서의 action을 암기해 동작할 수 있다는 것이다.
이를 해결하기 위해 전문가를 통해 100개의 시작 지점을 정하고 학습한다. 앞서 파라미터를 모두 같게 한다고 했기 때문에, 이것은 다른 알고리즘으로 tuned된 Double DQN이라고 한다.
이를 통해 DQN < Double DQN < Double DQN (tuned)로 성능이 좋아지는 것을 확인할 수 있다.
5. Discussion
- deterministic하더라도 학습의 내재된 estimation error로 인해 Q-learning이 large-scale problems에서 overoptimistic함을 보여준다.
- Atari games에서의 value esimate를 분석해 overestimations가 전에 알던 것 보다 더 일반적이고더 심하다는 것을 확인한다.
- Double Q-learning이 overoptimism을 성공적으로 줄일 수 있고, 학습에서 더 안정적이고 믿을만한 결과를 낸다.
- 추가적인 networks나 파라미터 없이 DQN의 아키텍쳐와 deep neural network를 사용해 만든 Double DQN을 제안한다.
- Double DQN이 더 나은 정책을 찾고, Atrai 2600에서 좋은 성과를 냈다.
댓글남기기