[RL] 강화학습 알고리즘: (2) Double DQN

---

DDQN (Double DQN)은 DQN의 후속 알고리즘으로 Google DeepMind에서 2015년도에 공개된 논문입니다. DQN에 관련된 내용은 이전 포스팅을 참고하시길 바랍니다.

 

Motivation

우리는 일반적으로 AI를 학습할 때 목표값인 target value와 결과값인 prediction value의 차이를 줄이는 방법을 이용합니다. 하지만 target value가 처음부터 잘못된 값이라면 네트워크는 제대로 된 결과를 학습할 수 없겠죠. 논문은 기존 DQN의 target value가 특정 조건에서 overestimate 된다고 주장하고 이를 해결하기 위한 Double DQN을 제안합니다.

 

Double DQN

기존 DQN과 Double DQN의 차이는 알고리즘상 한 줄입니다. Target value $y_t$를 설정하는 부분이 다른데 아래 수식과 같습니다.

 

$$ \begin{align} y_t^{\text{DQN}} &=r_t+\gamma~\max_a{Q(s_{t+1},a;\theta^-)} \\\\ y_t^{\text{DoubleDQN}} &=r_t+\gamma~ Q(s_{t+1},\arg\max_a{Q(s_{t+1},a;\theta)};\theta^-) \end{align} $$

 

Q-learning 기반 알고리즘은 TD target을 이용하기 때문에 target value를 Q-function을 이용해 추론하는 과정이 포함되어 있습니다. 이 과정에서 DQN의 max operation이 target value의 overestimation을 일으킨다고 합니다. 따라서 Double DQN에서는 action의 selection과 evaluation를 분리하여 직접적인 $\max Q$ 를 통해 현재 state의 가치를 추정하는 것을 방지합니다.

 

Overestimation이란?

Target value $y_t$의 overestimation은 action-value $Q(s,a)$의 에러 때문에 발생합니다. Action-value의 에러는 ① environmental noise, ② function approximation, ③ non-stationarity 등으로 발생합니다. 특이한 점은 이러한 에러는 양의 방향 에러와 음의 방향 에러 모두 존재하지만 target value는 항상 증가시키는 방향으로 overestimation이 일어난다는 점입니다.

 

Figure 1. DQN target의 overestimation 증명

이를 Theorem 1을 통해 증명하였는데 사용된 세 가지 가정은,

1) 특정 state에서 true optimal action-value는 action과 무관하게 동일함 $\rightarrow Q_*(s,a)=V_*(s)$

2) 임의로 추정된 action-value는 unbiased 되어있음 $\rightarrow \sum_a(Q_t(s,a)-V_*(s))=0$

3) 추정된 action-value의 적어도 일부는 정확하지 않음 $\rightarrow \frac{1}{m}\sum_a(Q_t(s,a)-V_*(s))^2=C$ 

 

1번은 action과 무관하게 action-value의 에러가 target value에 미치는 영향을 보기 위해 설정한 가정으로 보입니다. 2번은 양의 방향 에러만 존재하면 target value를 증가시키는 방향으로 추정되는 것이 당연하기 때문에, 에러가 unbiased 되도록 설정한 것으로 보입니다. 3번은 action-value에 에러가 존재하는 상황을 가정합니다.

 

이러한 상황에서 target value는 적어도 $\sqrt{\frac{C}{m-1}}$ 만큼의 overestimation되는 것을 증명하였는데, 수식 증명은 건너뛰고 예시를 보면 아래와 같습니다.

 

Figure 2. Theorem 1의 예시

1번 가정에 따라 action과 무관하게 10이라는 true optimal action-value를 설정하고, 2~3번 가정에 맞게 에러를 추가하였습니다. 두가지 예시 모두 주어진 바운드보다 같거나 큰 overestimation error가 발생하게 됩니다. 

 

Figure 3. DQN과 Double DQN의 overestimation error

Theorem 1의 특수한 조건하에서는 action의 개수 $m$에 따라 에러의 lower bound가 감소하지만, 일반적인 경우에는 [그림 3]과 같이 action이 증가할수록 overestimation이 증가한다고 합니다. 반면 Double DQN은 action 개수와 상관 없이 낮은 에러를 보여줍니다.

 

Results

Figure 4. DQN과 Double DQN 성능 비교

6개의 Atari 게임을 통해 DQN과 비교한 결과입니다. DQN은 true value에 비해 상당한 overestimation을 보여주는데 반해서 Double DQN은 비교적 잘 overestimation을 억제합니다. 이를 바탕으로 전체 score 측면에서도 Double DQN은 기존 DQN에 비해 높은 성능을 보여줍니다.

 

References

[1] H. van Hasselt et al., "Deep Reinforcement Learning with Double Q-learning," arXiv, 2015.

---

강화학습 스터디의 다른 글 목록

• 강화학습 이론: On-policy & Off-policy
• 강화학습 알고리즘: (1) DQN (Deep Q-Network)
• 강화학습 알고리즘: (2) Double DQN
• 강화학습 알고리즘: (3) Dueling DQN
• 강화학습 알고리즘: (4) DDPG
• 강화학습 알고리즘: (5) PPO

 

---

오타나 잘못된 부분 있으면 댓글 부탁드립니다. 도움이 되셨다면 공감 눌러 주시면 감사하겠습니다 :)