CS234 6강 Summary

CS234 강의 중 Lecture 6(Deep Q Learning)을 듣고 정리해보자

본 포스팅은 Stanford Univ의 CS234:Reinforcement Learning 강의를 듣고 정리한 글입니다.

원래 6강에서는 Deep Q Learning 뿐 아니라 CNN 내용도 다루나, 교수님께서 강의에서 언급하신 부분이 제가 정리한 포스팅 이나 CNN 정리 사이트에 대부분 기술되어 있어 CNN 파트는 넘어가도록 하겠습니다.

DQN (Deep Q-Network)

DQN(Deep Q-Network)은 Google의 Deepmind가 발표한 알고리즘으로 Deep Neural Network와 RL을 결합하여 인간 수준의 높은 성능을 달성한 알고리즘이다.

Q-Learning의 경우 Q-value인 $Q(s,a)$를 저장하여 학습하는데 이러한 방식은 많은 memory와 긴 exploation time이 필요하게 된다.

이러한 문제를 딥러닝을 이용하여 해결할 수 있다. 즉, 매개변수 $\theta$를 가진 신경망과 같은 함수 근사기를 훈련시켜 Q-value를 추정하여 해결이 가능하다. $(Q(s,a;\theta) \approx Q^* (s,a))$

기존 Deep Q-Learning의 문제점

DQN 이전에도 딥러닝과 강화학습을 결합하고자 하는 시도는 존재했다. 하지만 딥러닝을 통해 Q-function을 근사하고자 하는 기존의 시도들은 학습의 불안정성을 보이거나 알고리즘이 수렴하지 않는 문제가 있었다.

이러한 학습 불안정성의 원인으로는 다음과 같은 것들이 존재한다.

• Sample Correlation : 딥러닝에서는 학습 샘플들이 독립적(independent)하게 추출되었다고 가정하고 모델을 학습한다. 하지만 강화학습에서는 연속된 샘플 사이에 dependency가 존재한다. Atary와 같은 게임의 경우 게임의 연속된 프레임은 서로 굉장히 연관 되어 있듯이 말이다. 즉, 이전 샘플이 다음 샘플이 생성되는 것에 영향을 미치는데, 이를 MDP 모델로 해석하면 현재 샘플에서의 Policy와 state transition probability에 의해 다음 샘플이 생성되기 때문이라고 볼 수 있다. 이런 Correlation이 강한 연속된 샘플들로 모델을 학습하면 아래 그림과 같이 제대로 된 Q-function의 모양을 찾을 수 없다.

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

• 움직이는 target : 기존의 Deep Q-Learning은 Neural Net의 모델 파라미터를 update 할 때 지도학습의 gradient descent 기반의 update 방식을 이용하는데 여기서 문제가 발생한다. 기존의 Q-network는 업데이트 할 시 기준점이 되는 target value $y_{t}$ 역시 $\theta$로 파라미터화 되어 있었는데 이로 인해 $\theta$가 업데이트 되면 결과값인 action-value $Q(s,a;\theta)$ 와 기준값인 target value $y_{t}$ 가 동시에 움직이게 된다. 따라서 Q가 update 될 때마다 target value가 같이 update 되므로 원하는 방향으로 $\theta$가 update되지 않아 학습의 불안정성을 유발한다.

해결방법

DQN은 위 세 가지 문제를 해결하기 위해 CNN 아키텍처, Experience replay와 Target network을 도입했다.

우선 기존 Deep Q-Learning의 알고리즘은 다음과 같다.

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 \underset{a^{\prime}}{\operatorname{max}} Q(s_{t+1},a^{\prime};\theta ) $를 계산한다.

5) Loss function $(y_{t} - Q(s_{t},a_{t}; \theta))^{2}$ 를 최소화 하는 방향으로 $\theta$를 업데이트 한다.

DQN에서는 trainsition sample을 획득하는 3번 과정에서 experience replay를, 가중치를 업데이트하는 4-5번 과정에서 target network를 적용했다.

첫번째로 DQN은 CNN의 도입을 통해 인간과 비슷한 형식으로 Atari 게임(벽돌깨기)의 input을 처리하였다. Vision 분야에서 좋은 성능을 보이는 CNN은 높은 차원의 이미지 input을 효과적으로 처리할 수 있기에 기존 Deep Q-Learning의 Linear function approximator 보다 높은 성능을 가진다.

CNN의 입력으로 action을 제외한 state만을 받고 출력으로 action들에 해당하는 복수개의 Q-value들을 뽑아낸다. 이렇게 되면 Q-value를 update하기 위해 $ r_{t} + \gamma \underset{a^{\prime}}{\operatorname{max}} Q(s_{t+1},a^{\prime};\theta) $를 계산할 때 $\operatorname{max} Q(s,a)$값을 찾기 위해 CNN을 action마다 여러 번 통과시키지 않고 state input 한 번만 CNN에 통과시켜주면 되는 장점이 있다.

두번째로 아까 말했듯이 3번 과정에서 도입한 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 $D$라는 버퍼를 하나 만들어주어 현재 생성된 샘플 $e_{t}$를 저장한다. 다음으로 현재 선택된 action을 수행해 결과 값과 샘플을 얻지만 바로 평가에 이용하지 않고, 의도적으로 지연시켜준다. 이를 통해 기존 Deep Q-Learning에서 학습 불안정성을 유발하는 Sample Correlation과 Data distribution의 급작스러운 변화 문제를 해결할 수 있다.

상세히 말하자면, Replay memory를 이용해서 랜덤하게 추출된 샘플들은 각각 다른 time step에서 수행된 샘플들이므로 서로 독립적일 확률이 높아 Sample Correlation이 작으며, 랜덤 추출에 의해 Q-function이 다양한 action을 동시에 고려하여 update하므로, behavior policy와 training data의 분포가 편향되지 않고, smmoothing 되는 효과를 가질 수 있다.

이러한 experience replay의 장점을 정리하면 아래와 같다.

• Data efficiency 증가 : 하나의 샘플을 여러 번의 모델 업데이트에 이용 가능하므로 데이터 효율 증가.

• Sample Correlation 감소 : 랜덤 추출로 샘플들이 서로 독립적이기에 update variance를 낮춤.

• 학습 안정성 증가 : Behavior policy가 평균화 되어 학습 시 파라미터의 oscillation과 발산을 억제.

마지막으로 4-5번 과정에서 도입한 target network의 기본적인 컨셉은 다음과 같다.

1) Target netowrk $\theta^{-}$ 를 이용하여 target value $y_{j} = r_{j} + \gamma \underset{a^{\prime}}{\operatorname{max}} \hat{Q}(s_{t+1},a^{\prime};\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로 인한 학습 불안정성을 개선할 수 있다.

• Main Q-network : state,action을 이용해 결과값이 되는 action-value Q를 얻는데 이용된다. 매 step마다 파라미터가 업데이트 된다.

• Target network: 업데이트의 기준값이 되는 target value y 를 얻는데 이용된다. 매번 업데이트 되지 않고, n 스텝(n은 하이퍼파라미터임)마다 파리미터가 main network와 동기화된다.

따라서 target network를 이용해 target value를 고정시켜두면, 해당 구간 동안은 원하는 방향으로 모델을 업데이트할 수 있고, n 스텝 이후 target network와 main network를 동기화시켜 bais를 줄여 Q-learning에서 w가 발산하는 문제를 방지한다.

DQN 알고리즘

앞의 내용을 종합한 DQN의 의사코드는 위 그림과 같다. (전처리 과정도 일부 포함되어 있다.)

Deep RL Improvements

다음으로는 Deepmind의 논문 이후에 발표된, Deep RL의 주요 improvemets들을 설명해보겠다.

Double DQN

그 중 첫번째는, 바로 Double DQN이다. 이는 저번에 설명했던, maximization bias 문제를 해결하기 위해 나온 Double Q-learning의 Deep RL 적용판이다

Double Q-learning은 위 그림과 같이 Q를 하나만 쓰는 대신, 두 개를 사용하여 50% 확률로 $Q_{1}$, 나머지 50% 확률로 $Q_{2}$를 사용하여 Q-learning을 하는 방식이었다.

이 방식을 위 식과 같이 DQN에 적용시킨 것이 바로 Double DQN이다. 현재 사용하는 Q-network $w$를 action을 고르는 데 사용하고, $w^{-}$ 은 action을 evaluate 하는 데 사용하는 것이다.

Prioritized Replay

두번째 방식은, 바로 Prioritized Replay이다.

말 그대로, Experience Replay를 마음대로 설정하지 말고, 우선순위를 정해서 하자는 것이다.

아무런 영향을 주지 못한 replay는 결국 연산 횟수만 증가시키는 꼴이 되기 때문에 replay buffer를 선택하는 과정은 update 효율을 굉장히 증가시켜 준다.

그러면 어떻게 replay buffer의 우선순위를 정해야 할까 ?

이것은 DQN error를 사용하는 방법을 통해 정할 수 있다. 방법은 다음과 같다.

어떤 tuple (replay buffer)를 골랐을 경우의 TD error와 현재 error의 차이가 가장 큰 것의 우선순위를 크게 잡아두는 것이다.

만약 TD error가 현재의 error와 같다면 어떨까?

지금 선택한 replay buffer가 error에 아무런 영향을 끼치지 않는다는 이야기가 되므로, 정말 아무런 쓸데 없는 연산이 된다고 할 수 있다.

반면, TD error가 현재의 error와 크게 차이가 난다면?

그 버퍼가 바로 우리가 미처 제대로 습득하지 못한 데이터일 가능성이 커지게 되는 것이다. 이런 방식으로 replay buffer의 우선순위를 결정할 수 있다.

참고로 만약 $\alpha$ 가 0이라면 저번 step에서 일어난 일이 현재 step까지 어떤 영향을 끼치지 못하게 되는 꼴이므로, 모든 TD-error과 현재 error의 차이가 동일하게 정해지게 되어서 replay buffer는 그냥 랜덤하게 결정되게 된다.

Dueling DQN

다음으로, Dueling DQN 이라는 방식이 있다.

이는 기존의 신경망 구조 대신 강화학습에 더 특화된 신경망 구조를 이용해 학습하면 더 나은 결과가 나올 것이라는 생각으로 부터 나오게 되었다.

우선 Dueling Q-network의 구조는 위 그림과 같다.

기존의 Q-network에서는 마지막 fully-connected layer를 통과하면 action에 대한 Q-value들을 바로 추정한 반면, Dueling network에서는 fully-connected layer를 두 부분으로 분리하여, state-value와 advantage로 나누어 추정한 후 마지막에 합쳐 Q-value들을 출력하는 구조이다.

\[A(s,a) = Q(s,a) - V(s)\]

수식은 위와 같으며, 여기서 $V(s)$는 앞으로 선택될 action에 관계없이 현재 state의 가치가 얼마나 되는지를 나타내며 $A(s,a)$는 현재 state에서 해당 action이 다른 action들에 비해 가지는 상대적 가치를 나타낸다.

Dueling DQN 에 대해서 더 자세히 알아보고 싶다면 여기를 참고하자.

이외에도 Policy Optimization과 관련하여 DDPG, PPO 등의 알고리즘이 있는데, Reinforcement 알고리즘을 정리한 블로그를 참고하면 좋을 것 같다.

Reference

• 강화학습 강의 (CS234) 6강 - CNN + DQN (Deep Q Network)

• 강화학습 알고리즘 DQN