Double DQN 알고리즘

DQN에서 시간차 타깃 \(y_i\) 는 다음과 같이 계산된다.

 

\[ y_i=r(\mathbf{x}_i, \mathbf{a}_i )+ \gamma \max_{\mathbf{a}^\prime} Q_{\phi^\prime} (\mathbf{x}_{i+1}, \mathbf{a}^\prime ) \]

 

여기서 \(Q_{\phi^\prime} (\mathbf{x}_{i+1}, \mathbf{a}^\prime )\) 는 최적 행동가치 함수 \(Q^\star (\mathbf{x}_{i+1}, \mathbf{a}^\prime )\) 의 값을 신경망으로 추정한 값이다.

 

 

연구에 의하면 Q-러닝과 DQN에서는 행동가치 함수를 참값보다 항상 큰 값으로 추정하는 현상이 발생한다. 이를 과대추정 바이어스(overestimation bias)라고 한다.

아래 그림에서 빨강색 직선이 가치함수의 참값, 잡음이 있는 빨강색 곡선이 추정값으로서 과대추정 바이어스 현상을 확인할 수 있다.

 

H. van Hasselt, A Guez, and D. Silver, Deep Reinforcement Learning with Double Q-learning

 

가치함수를 과대추정하는 것이 무슨 문제가 있을까. 가치함수 값이 모든 상태변수와 행동에서 균일하게 과대추정된다면 문제될 것이 없을 것이다. 왜냐하면 최적 행동은 해당 상태변수에서 제일 큰 행동가치를 갖는 값으로 선택되기 때문에, 행동가치의 추정값에 상대적인 차이가 없다면 동일한 선택이 보장되기 때문이다. 하지만 만약 그렇지 않다면 최적이 아닌 정책이 선택될 수 있다.

과대추정 바이어스는 시간차 타깃 수식에 있는 max 연산자에 기인한다. 시간차 타깃에 있는 \(Q_{\phi^\prime} (\mathbf{x}_{i+1}, \mathbf{a}^\prime ) \)는 행동가치 함수의 참값이 아니라 추정값이다. 따라서 시간차 타깃의 수식은 추정값 중에서 최대값을 계산하는 'max of estimate' 구조이다. 본래는 max 연산자까지 포함하는 \(\max_{\mathbf{a}^\prime}⁡Q_{\phi^\prime} (\mathbf{x}_{i+1}, \mathbf{a}^\prime) \) 전체를 추정하는 'estimate of max' 구조이어야 한다.

다음 수식을 보자. 행동가치 함수 \(Q\)의 추정값 \(\hat{Q}\) 에 내재되어 있는 노이즈를 고려하여 행동가치 함수의 추정값을 랜덤변수로 볼 수 있다. 그러면 다음 식과 같이 행동가치 함수의 추정값에 바이어스가 없다고 하더라도 행동가치 함수의 추정 최대값(max of estimate)에는 바이어스가 있을 수 있다.

 

\[ \begin{align} \mathbb{E} \left[ \max_{\mathbf{a}^\prime} \hat{Q}(\mathbf{x}, \mathbf{a}^\prime ) \right] & = \mathbb{E} \left[ \max \{ \hat{Q}(\mathbf{x}, \mathbf{a}_1 ), \hat{Q}(\mathbf{x}, \mathbf{a}_2 ), ... , \hat{Q}(\mathbf{x}, \mathbf{a}_m ) \} \right] \\ \\ & \ge \max \{ \mathbb{E} [\hat{Q}(\mathbf{x}, \mathbf{a}_1 )], \mathbb{E} [\hat{Q}(\mathbf{x}, \mathbf{a}_2 )], ... ,\mathbb{E} [\hat{Q}(\mathbf{x}, \mathbf{a}_m )] \} \\ \\ & = ⁡\max \{ Q(\mathbf{x}, \mathbf{a}_1 ), Q(\mathbf{x}, \mathbf{a}_2 ), ... , Q (\mathbf{x}, \mathbf{a}_m ) \} \\ \\ & = \max_{\mathbf{a}^\prime} Q(\mathbf{x}, \mathbf{a}^\prime) \end{align} \]

 

위 식에서 두번째 줄은 젠센 부등식(Jensen’s inequality)에 의한 것이며 세번째 줄은 행동가치 함수의 추정값에 바이어스가 없다는 가정, \(\mathbb{E} [ \hat{Q} (\mathbf{x}, \mathbf{a})]=Q(\mathbf{x},\mathbf{a})\), 에 의한 것이다.

행동가치 함수의 추정값이 후속 상태의 추정을 사용하여 업데이트 되는 시간차 함수의 특성에 의해서, 행동가치 함수 추정값의 오류는 업데이트가 진행되면서 더욱 과장되어 누적된다. 이 누적된 오류로 인해 임의의 잘못된 상태가 높은 값으로 추정되어 최적이 아닌 정책 업데이트가 발생할 수 있는 것이다.

그렇다면 어떻게 해야 과대추정 바이어스의 원인이 되는 'max of estimate' 구조에서도 바이어스가 발생하지 않을까.

다시 시간차 타깃 수식에 있는 max 연산자를 살펴보자.

 

\[ \max_{\mathbf{a}^\prime} Q_{\phi^\prime} (\mathbf{x}_{i+1}, \mathbf{a}^\prime) = Q_{\phi^\prime} \left( \mathbf{x}_{i+1}, \arg\max_{\mathbf{a}^\prime} ⁡Q_{\phi^\prime} (\mathbf{x}_{i+1}, \mathbf{a}^\prime ) \right) \]

 

표준 DQN의 max 연산자는 \(Q_{\phi^\prime}\) 에 의해서 행동 \(\mathbf{a}^\prime\) 을 선택하고 \(Q_{\phi^\prime}\) 에 의해서 행동가치를 계산한다. 즉 노이즈가 포함된 동일한 함수를 사용하여 행동을 선택하고 평가한다. 이로 인해 과대 평가된 값을 선택할 가능성이 높아져 과도하게 큰 행동가치 값이 추정되는 것으로 보인다.

이를 방지하기 위해서는 행동을 선택할 때와 평가할 때 사용하는 행동가치 함수에 내재되어 있는 노이즈의 상관관계를 깨는 것(decorrelation)이 필요하다. 그러기 위해서 행동을 선택할 때와 평가할 때 사용하는 신경망을 분리하자는 것이 Double DQN의 아이디어다.

 

 

샘플을 분리하여 각각 독립적인 두개의 행동가치 추정 함수 \(Q_1 (\mathbf{x}, \mathbf{a})\) 과 \(Q_2 (\mathbf{x}, \mathbf{a})\) 를 만들었다고 하자. 행동가치 함수의 추정값에는 바이어스가 없다고 가정한다. 그러면 행동을 선택할 때 \(Q_1\) 을 사용하고,

 

\[ \mathbf{a}^\star = \arg\max_{\mathbf{a}}⁡ Q_1 (\mathbf{x}, \mathbf{a}) \]

 

그 행동을 평가할 때는 \(Q_2\) 를 사용한다면 'max of estimate'의 구조에서의 추정값에도 바이어스가 없게 된다.

 

\[ \mathbb{E} [ Q_2 (\mathbf{x}, \mathbf{a}^\star )] = Q ( \mathbf{x}, \mathbf{a}^\star) \]

 

Double DQN에서는 두 개의 독립적인 Q 신경망을 만드는 대신에 표준 DQN에 이미 사용하고 있는 Q 신경망과 타깃 신경망을 이용한다. 즉 Q 신경망으로 행동 \(\mathbf{a}^\prime\) 을 선택하고 타깃 신경망으로 행동가치를 계산한다.

 

\[ y_i=r(\mathbf{x}_i, \mathbf{a}_i )+ \gamma Q_{\phi^\prime} \left( \mathbf{x}_{i+1}, \arg\max_{\mathbf{a}^\prime}⁡Q_\phi (\mathbf{x}_{i+1}, \mathbf{a}^\prime ) \right) \]

 

타깃 신경망의 파라미터가 일정한 주기 마다 Q 신경망의 파라미터로 업데이트되거나 또는 Q 신경망의 파라미터를 느린 속도로 따라가도록 했기 때문에, 엄밀한 의미에서는 Q 신경망과 타깃 신경망이 서로 독립적인 신경망이라고 할 수 없다. 하지만 연구 결과에 의하면 표준 DQN보다는 훨씬 과대추정 바이어스를 줄일 수 있다고 한다.

Double DQN 알고리즘을 정리하면 다음과 같다. 표준 DQN과의 차이는 [6]번에 있다.

[1] Q 신경망의 파라미터를 초기화한다.
[2] Q 신경망의 파라미터를 타깃 신경망에 복사한다.
[3] 리플레이 버퍼를 초기화 한다. 그리고 [4]-[8]을 반복한다.

   [4] \(\epsilon-\)탐욕 정책을 실행하여 발생된 천이샘플(transition sample) \(\{\mathbf{x}_i, \mathbf{a}_i, r_i, \mathbf{x}_{i+1}\}\) 를 리플레이 버퍼에 저장한다.
   [5] 리플레이 버퍼에서 \(N\)개의 천이샘플 \(\{\mathbf{x}_i, \mathbf{a}_i, r_i, \mathbf{x}_{i+1}\}\) 를 무작위로 추출한다.
   [6] \( y_i=r(\mathbf{x}_i, \mathbf{a}_i )+ \gamma Q_{\phi^\prime} \left( \mathbf{x}_{i+1}, \arg\max_{\mathbf{a}^\prime}⁡Q_\phi (\mathbf{x}_{i+1}, \mathbf{a}^\prime ) \right) \) 를 계산한다.
   [7] \(\phi \gets \phi + \alpha_\phi \sum_i \left( y_i-Q_\phi (\mathbf{x}_i, \mathbf{a}_i ) \right) \nabla_\phi Q_\phi (\mathbf{x}_i, \mathbf{a}_i )\) 로 Q 신경망을 업데이트 한다.
   [8] \(\phi^\prime \gets \tau \phi + (1-\tau) \phi^\prime\) 로 타깃 신경망을 업데이트 한다.