[RL] 강화학습 알고리즘: (1) DQN (Deep Q-Network)

---

Google DeepMind는 2013년 NIPS, 2015년 Nature 두 번의 논문을 통해 DQN (Deep Q-Network) 알고리즘을 발표했습니다. DQN은 딥러닝과 강화학습을 결합하여 인간 수준의 높은 성능을 달성한 첫번째 알고리즘입니다. 심층강화학습에서 가장 기본이 되는 알고리즘을 논문을 통해 리뷰해보도록 하겠습니다.

 

Why Deep Reinforcement Learning?

딥러닝을 강화학습과 결합하게 되면 어떠한 이점이 있을까요? 기존의 Q-learning은 state-action $(s,a)$에 해당하는 Q-value인 $Q(s,a)$를 테이블 형식으로 저장하여 학습합니다. 이러한 방식은 state space와 action space가 커지게 되면 모든 Q-value를 저장하기에 많은 memory와 긴 exploration time이 필요하게 되는데, 이를 딥러닝이 해결할 수 있습니다.

 

딥러닝을 이용하여 Q-table에 해당하는 Q-function을 비선형 함수로 근사시켜 이 함수만 제대로 알고 있으면, 모든 state-action에 대한 Q-value값을 찾거나 저장할 필요가 없어집니다. 이때 딥러닝으로 근사한 Q-function의 weight parameter들은 일반적으로 $\theta$ 로 표현합니다.

 

Figure 1. Q-learning과 deep Q-learning 비교

 

기존 Deep Q-learning의 문제점

기존에도 딥러닝과 강화학습을 결합하고자 하는 시도는 존재했습니다. 하지만 딥러닝을 통해 Q-function을 근사하고자 하는 기존의 시도들은 학습의 불안정성을 보이거나 알고리즘이 수렴하지 않는 문제를 가지고 있었습니다. 2015 Nature 논문에서는 이러한 학습 불안정성의 원인으로 ① sample correlation, ② data distribution 변화 ③ 움직이는 target value를 지목하였습니다.

This instability has several causes: the correlations present in the sequence of observations, the fact that small updates to $Q$ may significantly change the policy and therefore change the data distribution, and the correlations between the action-values ($Q$) and the target values $r+\gamma \max_{a'}Q(s',a')$

 

DQN은 experience replay와 target network의 도입을 통해 위의 세 가지 문제를 해결하였는데, 각각의 문제에 대해서는 DQN을 소개하면서 함께 정리해보도록 하겠습니다.

 

Deep Q-Network (DQN) 이란?

논문에서 DQN은 ① CNN (convolutional neural network), ② experience replay, ③ target network의 세 가지 핵심 요소로 구성되어 있다고 말하고 있습니다. 먼저 DQN이 적용되지 않은 기존의 deep Q-learning 알고리즘을 요약해서 나타내면 아래와 같습니다.

[기존의 Deep Q-learning algorithm]
1) 파라미터를 초기화하고, 매 스텝마다 2~5를 반복한다.
     2) Action $a_t$ 를 $\epsilon$-greedy 방식에 따라 선택한다.
     3) Action $a_t$ 를 수행하여 transition $e_t=(s_t,a_t,r_t,s_{t+1})$ 를 얻는다.
     4) Target value $y_t=r_t+\gamma \max_{a'}Q(s_{t+1},a';\theta)$ 를 계산한다.
     5) Loss function $(y_t-Q(s_t,a_t;\theta))^2$ 를 최소화하는 방향으로 $\theta$ 를 업데이트한다.

 

DQN에서는 transition sample을 획득하는 3번 과정에서 experience replay가, $\theta$ 를 업데이트하는 4~5번 과정에서 target network가 새롭게 적용됩니다.

 

① CNN Architecture

첫번째로 DQN은 CNN의 도입을 통해 인간과 유사한 형식으로 Atari 게임의 인풋을 처리하여 높은 성능을 얻고자 하였습니다. Computer vision 분야에서 좋은 성능을 보이는 CNN은 높은 차원의 이미지 인풋을 효과적으로 처리할 수 있기 때문에 DQN은 기존 linear function approximator 보다 높은 성능을 나타냅니다.

 

특징적인 점은 CNN의 입력으로 action을 제외한 state만을 받고 출력으로 action들에 해당하는 복수개의 Q-value들을 뽑아내는 구조입니다. 이렇게 되면 Q-value update를 하기 위해 $r_t+\gamma \max_{a'}Q(s_{t+1},a';\theta)$를 계산할 시, $\max Q(s,a)$ 값을 찾기 위해 CNN을 action마다 여러 번 통과시키지 않고 state 인풋 한 번만 CNN에 통과시켜주면 되는 이점이 있습니다.

 

② Experience Replay

[Experience Replay]
1) 매 스텝마다 추출된 샘플 $e_t=(s_t,a_t,r_t,s_{t+1})$ 을 replay memory $D$ 에 저장한다.
2) Replay memory $D$ 에 저장된 샘플들을 uniform하게 랜덤 추출하여 Q-update 학습에 이용한다.

 

Experience replay의 기본적인 컨셉은 위와 같이 간단합니다. Replay memory라는 버퍼를 하나 만들어줘서 현재 생성된 샘플 $e_t$를 저장해줍니다. 현재 선택된 action을 수행해 결과 값과 샘플을 얻지만 이를 바로 평가에 이용하지 않고, 의도적으로 지연시켜줍니다. 이를 통해 기존 deep Q-learning에서 학습 불안정성을 유발하는 아래의 요인들을 해결할 수 있습니다.

 

Figure 2. Experience replay

1) Sample correlation

딥러닝에서는 학습 샘플들이 independent하게 추출되었다고 가정하고 모델을 학습합니다. 하지만 강화학습에서는 연속된 샘플 사이에 dependency가 존재합니다. 즉, 이전 샘플이 다음 샘플이 생성되는 것에 영향을 미치는데, 이를 MDP 모델로 해석하면 현재 샘플에서의 policy와 state transition probability에 의해 다음 샘플이 생성되기 때문이라고 볼 수 있습니다. Correlation이 강한 연속된 샘플들로 모델을 학습하게 되면 아래 그림과 같이 제대로 된 Q-function의 모양을 찾을 수 없습니다.

 

Figure 3. Sample correlation 예시

2) Data distribution 변화

모델을 on-policy로 학습할 경우, Q-update로 인해 behavior policy가 바뀌면 그로 인해 생성되는 training data의 분포도 갑자기 변화할 수 있습니다. 이러한 data distribution의 갑작스러운 변화는 학습 파라미터의 oscillation을 유발하고 이러한 불안정성으로 인해 local minimum에 수렴하거나 심지어 알고리즘이 발산하게 만들 수 있습니다.

 

따라서 replay memory를 이용해서 랜덤하게 추출된 샘플들은 각각 다른 시간에서 수행된 샘플들이므로 sample correlation이 작습니다. 또한 랜덤 추출에 의해 Q-function이 다양한 action을 동시에 고려하여 업데이트되므로, behavior policy와 training data 분포가 편향되지 않고 smoothing 되는 효과를 가질 수 있습니다. Experience replay의 장점을 정리하면 아래와 같습니다.

 

• Data efficiency 증가: 하나의 샘플을 여러 번의 모델 업데이트에 이용할 수 있으므로 데이터 효율 증가
• Sample correlation 감소: 랜덤 추출로 sample correlation을 없애 update variance를 낮춤
• 학습 안정성 증가: Behavior policy가 평균화되어 학습 시 파라미터의 oscillation과 발산을 억제

 

③ Target Network

[Target network]
1) Target network $\theta^-$ 를 이용하여 target value $y_j=r_j+\gamma \max_{a'}\hat{Q}(s_{j+1},a';\theta^-)$ 를 계산한다.
2) Main Q-network $\theta$ 를 이용하여 action-value $Q(s_j,a_j;\theta)$ 를 계산한다.
3) Loss function $(y_j-Q(s_j,a_j;\theta))^2$ 이 최소화되도록 main Q-network $\theta$ 를 업데이트한다.
4) 매 $C$ 스텝마다 target network $\theta^-$ 를 main Q-network $\theta$ 로 업데이트한다. 

 

Target network의 기본적인 컨셉은 위와 같습니다. 기존의 Q-network를 동일하게 복제하여 main Q-network와 target network의 이중화된 구조로 만듭니다. Target network를 통해 이중화된 네트워크 구조를 가짐으로써 움직이는 target value로 인한 학습 불안정성을 개선할 수 있습니다.

 

Figure 4. DQN의 target network 구조

• Main Q-network: State, action을 이용해 결과값이 되는 action-value $Q$를 얻는데 이용됩니다. 매 스텝마다 파라미터가 업데이트됩니다.
• Target network: 업데이트의 기준값이 되는 target value $y=r+\gamma\max\hat{Q}$를 얻는데 이용됩니다. 매번 업데이트되지 않고 $C$ 스텝마다 파라미터가 main network와 동기화됩니다.

 

3) 움직이는 target value

기존 deep Q-learning은 뉴럴넷의 모델 파라미터를 업데이트할 시 지도학습의 gradient descent 기반의 업데이트 방식을 이용하는데 여기서 문제가 발생합니다. 기존의 Q-network는 업데이트할 시 기준점이 되는 target value $y_t$ 역시 $\theta$로 파라미터화 되어있습니다. 이로 인해 $\theta$가 업데이트되면 결과값인 action-value와 기준값인 target value가 동시에 움직이게 됩니다. 따라서 일반적인 지도 학습과는 달리, target value가 같이 움직이기 때문에 원하는 방향으로 $\theta$가 업데이트되지 않고 이는 학습의 불안정성을 유발합니다.

 

따라서 $C$ 스텝동안 target network를 이용해서 target value를 고정시켜두면 해당 구간 동안은 원하는 방향으로 모델을 업데이트할 수 있고, $C$ 스텝 이후 target network와 main network를 동일화시켜 bias를 줄여주는 과정을 수행합니다. 

 

Figure 5. DQN 알고리즘 (2015 Nature)

앞의 내용을 종합한 2015 Nature 논문의 DQN 알고리즘은 [그림 5]와 같습니다. 일부 preprocessing 과정이 포함되어있지만 핵심적인 알고리즘은 위 설명과 동일합니다.

 

Results

Table 1. Experience replay와 target network의 효과

Experience replay와 target network으로 인한 성능개선 결과는 [표 1]과 같으며, 게임에 따라 차이가 있습니다. 일반적으로는 experience replay로 인한 성능개선 효과가 더 크며, Seaquest 게임에서는 target network로 인한 성능개선 효과가 더 크다는 것을 알 수 있습니다.

 

References

[1] V. Mnih et al., "Human-level Control Through Deep Reinforcement Learning", Nature, 2015.

[2] V. Mnih et al., "Playing Atari with Deep Reinforcement Learning," arXiv, 2013.

---

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

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

---

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