DQN 알고리즘 - 1

Q-러닝 알고리즘은 이산공간 상태변수와 행동을 기본으로 하며, 유한 개의 상태변수와 행동에 대한 행동가치의 값을 테이블(Q-테이블이라고 한다) 형식으로 저장하고 관리한다.

 

 

적은 수의 상태변수와 행동의 경우에는 문제가 되지 않지만 많은 수의 상태변수와 행동의 경우에는 이와 같은 테이블 형식의 관리는 불가능할 수 있다.

 

 

예를 들어서 비디오 게임에 Q-러닝을 적용한다고 할 때, $200\times 200$ 픽셀 이미지, $255$ 컬러, $3$ 채널로 가정한다면 상태변수의 개수는 $({255}^3{)}^{200\times 200}$ 개가 된다. 이 숫자는 전 우주에 있는 원자의 개수보다도 더 큰 숫자라고 한다. 이처럼 방대한 상태변수의 개수를 테이블 형태로 저장하고 관리한다는 것은 불가능한 일이다.

그러면 어떻게 해야 할까.

신경망을 도입하여 Q-테이블 또는 행동가치 함수를 근사화하는 것이다. 이제부터 상태변수를 연속공간 변수로 가정한다. 하지만 행동은 여전히 이산공간 값으로 가정하겠다. 일반적으로 행동은 그 개수가 상태변수보다 현저히 적으므로 큰 문제가 되지는 않는다. 행동까지 연속공간인 경우에는 다른 해결책이 있다. 이에 대해서는 추후 논의해보자.

상태변수는 연속공간 값이므로 ${\mathbf{x}}_t$ 로 표기하고 행동은 이산공간 값이므로 ${\mathbf{a}}_t$ 로 표기한다. Q-러닝 식을 다시 써보자.

 

$$Q({\mathbf{x}}_t,{\mathbf{a}}_t)\leftarrow r_t+{\mathbb{E}}_{{\mathbf{x}}_{t+1}\sim p({\mathbf{x}}_{t+1}|{\mathbf{x}}_t,{\mathbf{a}}_t)}[\gamma \underset{{\mathbf{a}}_{t+1}}{max}Q({\mathbf{x}}_{t+1},{\mathbf{a}}_{t+1})]$$

 

행동가치 함수를 추정하기 위해서 신경망을 이용하기로 하고, 그 신경망의 파라미터를 $\varphi$ 로 표기하자. 그리고 추정된 행동가치를 $Q_{\varphi }({\mathbf{x}}_t,{\mathbf{a}}_t)$ 라고 하자. 이 신경망을 심층 Q신경망(deep Q network) 또는 DQN이라고 한다. DQN은 상태와 행동을 입력으로 받으며 그에 대한 행동가치인 Q값을 출력한다. 따라서 신경망은 입력 레이어에서 상태와 행동을 입력으로 받고, 출력 레이어에서 Q값을 출력하는 구조로 만들면 된다.

 

개념적으로 위와 같은 구조가 맞지만, 행동이 이산화되어 있기 때문에 다음과 같은 구조로 신경망을 설계하는 것이 일반적이다.

 

 

즉 신경망은 상태변수만을 입력으로 받고, 출력으로는 각각의 행동에 대한 Q값인 $Q_{\varphi }({\mathbf{x}}_t,{\mathbf{a}}_1)$, $Q_{\varphi }({\mathbf{x}}_t,{\mathbf{a}}_2)$, $...$ , $Q_{\varphi }({\mathbf{x}}_t,{\mathbf{a}}_m)$ 을 계산하도록 입출력 레이어를 구성한다.

이 신경망의 손실함수는 최적 행동가치 함수를 정확히 추정할 수 있는 파라미터 $\varphi$ 를 갖도록 정해져야 한다. 따라서 손실함수는 행동가치 추정값 $Q_{\varphi }({\mathbf{x}}_t,{\mathbf{a}}_t)$ 와 최적 행동가치의 참값 $Q^{\star }({\mathbf{x}}_t,{\mathbf{a}}_t)$ 의 차이가 최소가 되도록 정하면 될 것 같다.

 

 

일반적인 지도학습(supervised learning) 문제이므로 신경망의 입력과 그 입력에 대한 정답으로 학습 데이터셋 $\{({\mathbf{x}}_i,{\mathbf{a}}_i),Q^{\star }({\mathbf{x}}_i,{\mathbf{a}}_i)\}$ 를 모으고 손실함수를 다음과 같이 평균제곱오차(MSE, mean squared error)로 정한다.

 

$$L(\varphi )=\frac{1}{2}\sum _i\Vert Q^{\star }({\mathbf{x}}_i,{\mathbf{a}}_i)-Q_{\varphi }({\mathbf{x}}_i,{\mathbf{a}}_i){\Vert }^2$$

 

그런데 여기서 최적 행동가치의 참값 $Q^{\star }({\mathbf{x}}_i,{\mathbf{a}}_i)$ 를 알지 못하므로, 부트스트래핑(bootstrapping) 방법을 사용한다.

 

$$Q^{\star }({\mathbf{x}}_i,{\mathbf{a}}_i)\approx y_i=r({\mathbf{x}}_i,{\mathbf{a}}_i)+\gamma \underset{{\mathbf{a}}^{\prime }}{max}{Q}_{\varphi }({\mathbf{x}}_{i+1},{\mathbf{a}}^{\prime })$$

 

그러면 손실함수는 다음과 같이 된다.

 

$$L(\varphi )=\frac{1}{2}\sum _i\Vert y_i-Q_{\varphi }({\mathbf{x}}_i,{\mathbf{a}}_i){\Vert }^2$$

 

여기서 $y_i$ 를 시간차 타깃이라고 한다.

 

 

손실함수를 최소화하는 파라미터 $\varphi$ 는 다음과 같이 경사하강법으로 구할 수 있다.

 

$$\varphi \leftarrow \varphi -{\alpha }_{\varphi }{\mathrm{\nabla }}_{\varphi }L(\varphi )$$

 

손실함수의 그래디언트는 다음과 같이 계산한다.

 

$${\mathrm{\nabla }}_{\varphi }L(\varphi )=-\sum _i(y_i-Q_{\varphi }({\mathbf{x}}_i,{\mathbf{a}}_i)){\mathrm{\nabla }}_{\varphi }{Q}_{\varphi }({\mathbf{x}}_i,{\mathbf{a}}_i)$$

 

이제 다음과 같이 학습 알고리즘을 만들면 될 것 같다.

[1] DQN의 파라미터를 초기화한다. 그리고 [2]-[4]를 반복한다.
[2] 행동 ${\mathbf{a}}_i$ 를 실행하여 천이샘플(transition sample) $\{{\mathbf{x}}_i,{\mathbf{a}}_i,r_i,{\mathbf{x}}_{i+1}\}$ 를 모은다.
[3] $y_i=r({\mathbf{x}}_i,{\mathbf{a}}_i)+\gamma \underset{{\mathbf{a}}^{\prime }}{max}{Q}_{\varphi }({\mathbf{x}}_{i+1},{\mathbf{a}}^{\prime })$ 를 계산한다.
[4] $\varphi \leftarrow \varphi +{\alpha }_{\varphi }\sum _i(y_i-Q_{\varphi }({\mathbf{x}}_i,{\mathbf{a}}_i)){\mathrm{\nabla }}_{\varphi }{Q}_{\varphi }({\mathbf{x}}_i,{\mathbf{a}}_i)$ 로 신경망을 업데이트 한다.

그런데 의도와는 달리 위 알고리즘은 제대로 작동하지 않을 것이다. 사실 위 알고리즘에는 생각해야 할 문제가 많이 있다.

먼저 Q-러닝은 오프-폴리시 방법이다. 오프-폴리시의 장점을 알고리즘에 반영해야 한다.

두번째는 탐색(exploration)의 문제다. Q-러닝은 확정적 정책이므로 불확실한 환경을 적극적으로 탐색할 수 있는 무작위성(randomness)이 없다. 행동에 무작위성을 도입할 방안을 마련해야 한다.

세번째는 학습의 수렴성 문제다. 테이블 형태의 Q-러닝은 수렴성이 보장됐었는데 DQN도 그럴 것인지는 따져봐야 한다.

네번째는 학습의 안정성 문제다. DQN에서도 A2C 알고리즘과 마찬가지로 부트스트래핑 방법을 사용했다. 시간차 타깃이 신경망을 업데이트 할 때 마다 계속 달라지므로 학습이 불안정해질 수 있다.

다섯번째는 신경망 학습에 사용된 경사하강법(gradient descent) 문제다. 알고리즘의 [4]번이 경사하강법이 맞긴 한 것인가?

이 문제들에 대한 대처 방안을 알아보도록 하자.