DQN: Deep Q-Network

DQN Architecture

2013 NIPS 버전: Playing Atari with Deep Reinforcement Learning

2015 Nature 버전: Human-Level Control through Directly-Trained Deep Spiking Q-Networks

배경

DQN은 Deep Q-Network의 약자로  Q-Learning에 신경망(Neural Network)이 결합된 형태이다.

당시에 강화학습은 Vision이나 Speech 같은 고차원 데이터가 환경으로 주어졌을때 이를 해결할 수 없었다. 논문에 나온 Atari Game을 예시로 들자면 아래 사진에 있는 Breakout이란 게임은 210 x 168 픽셀을 가졌고 128가지의 색상을 지원한다.

 

 

이제 생각을 해보자 210 x 168의 프레임을 그리드 월드라고 생각하고 길 찾기 에이전트를 만든다고 가정하면 210 x 168 = 35,280개이다. 이정도면 사실 문제도 안된다 근데 문제는 이게 색상을 가진 이미지라는 것이다. 원래는 그리드 월드 1칸당 상태나 행동에 대한 가치를 측정할 수 있었는데 이제는 똑같은 칸에 있더라도 색상에 따라 내 상태는 달라진다. 그러면 몇개의 상태가 나올 수 있는가 \(128^{(210 \times 168)}\) 개의 상태가 나올수 있다. 근데 Q-Learning은 아래와 같은 표 형태로 값을 저장해놓고 업데이트하는 방식으로 학습이 진행된다.

state	action1	action2	action3
\(s_1\)	-1.0	12	10
\(s_2\)	1	5	6
\(s_3\)	0	-9	9
\(s_4\)	−20	−19	−17
\(s_5\)	15	14	60
\(s_6\)	10	65	23
\(s_7\)	17	27	28

 

저 Table이 \(128^{(210 \times 168)}\) 개의 Row Data가 있다고 했을 때 컴퓨터가 감당을 못한다. 그래서 DQN은 Table안쓰고 훈련 과정에서 Experience Replay라는것을 사용해서 경험을 replay 메모리에 저장하고 여기서 몇개만 샘플링해서 신경망을 통해 Q값을 근사한다.

신경망 + 강화학습의 챌린지

논문에서는 아래와 같은 이유로 "강화학습은 딥러닝 관점에서 여러 가지 과제를 제시한다"라고 말합니다.

 

1. 지도학습과 강화학습의 데이터 차이

"most successful deep learning applications to date have required large amounts of hand-labelled training data RL algorithms, on the other hand, must be able to learn from a scalar reward signal that is frequently sparse, noisy and delayed"

 

여기서 sparse(희소)한 보상은 예시로 경로 탐색을 하는데 100번이든 1000번이든 행동을 수행한 후에 목적지에 도착해야만 보상을 받으면 보상이 희소하다고 할 수 있다.

noisy가 많다는 것은 에이전트가 동일한 상태에서 동일한 행동을 취한다고 항상 동일한 보상이 돌아오지 않아서 이를 노이즈가 많다고 표현한다. 지도학습은 개 사진을 보고 고양이라고 하면 1000번을 해도 1000번 다 틀렸다고 한다.

마지막 delayed(지연된) 보상은 아래 이미지와 같이 천국과 지옥의 갈림길에 서있을때 내가 오른쪽으로 이동하는 즉시 보상이 들어오지 않고 한참 걸어가다가 수천 step 뒤에 아 여기가 천국이네 하며 보상이 늦게 들어오는 것을 말하는데 지도학습은 개를 고양이라고 하면 즉각적으로 틀린것을 바로 알 수 있고 이러한 방식들이 강화학습과 지도학습의 큰 차이를 보인다

2. 데이터 독립성

"Another issue is that most deep learning algorithms assume the data samples to be independent, while in reinforcement learning one typically encounters sequences of highly correlated states"

 

대부분의 데이터들은 데이터들간의 상관관계가 없지만 강화학습은 MDP만 봐도 알고있듯이 순차적 의사 결정 문제인데 당연히 서로 관계가 강함.

 

3. 데이터 분포

"Furthermore, in RL the data distribution changes as the algorithm learns new behaviours, which can be problematic for deep learning methods that assume a fixed underlying distribution"

 

강화 학습에서는 알고리즘이 새로운 행동을 학습함에 따라 데이터 분포가 변화하는데 이는 고정된 분포를 가정하는 딥러닝에서는 문제가 될 수 있다. 보통 딥러닝에서는 개 사진 1000장 고양이 사진 1000장 이런식으로 고정된 데이터셋을 준비해두기 때문에 데이터 분포가 변하지 않는다. 근데 강화학습은 에이전트가 초기에 멍청할 때, 똑똑할 때 각 에피소드마다 데이터 분포가 다 다르다.

Core Methodology

이 논문은 위의 Q-Learning과 기존 심층 강화학습의 문제를 CNN을 통해 해소하여 성공시킨다. DQN에서 알아야할 핵심 키워드는 다음과 같다.

• Target Network
• Experience Replay

Target Network

원래 우리가 알던 Q-Learning에서는 아래 식으로 \(Q(s, a)\)를 업데이트했었다.

\[ Q(s, a) \leftarrow Q(s, a) + \alpha \big[ r + \gamma \max_{a'} Q(s', a') - Q(s, a) \big] \]

근데 DQN에서는 \(Q\)값을 표에 저장하는게 아니라 신경망으로 근사하기로 했으니까, \(Q(s, a)\)가 \(Q(s, a; \theta)\)로 바뀐다. 그리고 타겟 부분에 들어있던 \(\max_{a'} Q(s', a')\)도 마찬가지로 신경망 버전인 \(\max_{a'} Q(s', a'; \theta)\)로 바뀐다. 그러면 이제 우리가 업데이트하려는 대상은 표 안의 숫자가 아니라 신경망 가중치 \(\theta\) 자체가 된다.

업데이트 방향은 gradient descent로 잡는다.

\[ \theta \leftarrow \theta - \alpha \nabla_\theta L(\theta) \]

여기서 Loss는 결국 "정답이랑 예측이랑 얼마나 다른가"인데, 위에서 변환한 식을 그대로 넣으면 이렇게 된다.

\[ L(\theta) = \big( \,\underbrace{r + \gamma \max_{a'} Q(s', a'; \theta)}_{\text{target (정답)}} \;-\; \underbrace{Q(s, a; \theta)}_{\text{prediction (예측)}}\, \big)^2 \]

즉 우리가 하려는건 \(Q(s, a; \theta)\)가 \(r + \gamma \max_{a'} Q(s', a'; \theta)\)에 가까워지도록 만드는 \(\theta\)를 찾는 거고, 그 차이(Loss)가 줄어드는 방향으로 \(\theta\)를 업데이트하면 된다.

근데 여기서 뭔가 이상하지 않은가? 위 Loss 식을 한 번 더 자세히 보자. target에도 \(\theta\), prediction에도 \(\theta\). 둘이 같은 \(\theta\)다. 내가 prediction을 target에 맞추려고 \(\theta\)를 움직이는 순간 target도 그 \(\theta\)로 계산되니까 같이 움직여버린다. 활을 쏘려고 조준하는데 내가 손을 움직이면 과녁이 같이 휙휙 움직이는 셈. 학습이 안정적으로 될리가 없다. 이걸 moving target problem이라고 부른다.

 

Target Network는 2013년 NIPS Workshop 버전에는 등장하지 않고, 2년 뒤 2015년 Nature 논문에서 추가된 개념이다. 

 

해결책은 의외로 단순하다. 같은 \(\theta\) 하나로 양쪽을 다 계산하니까 문제였으니, 신경망을 두 개로 쪼개버린다.

• \(\theta\) : 매 스텝마다 학습되는 메인 네트워크 (Online Network)
• \(\theta'\) : 타겟 계산할 때만 쓰는 네트워크 (Target Network)

그리고 핵심은 둘 중 하나(\(\theta'\))는 가만히 고정시켜둔다는 것. 매 스텝마다 같이 움직이게 두지 않고, 무작위로 특정 스텝마다 한 번씩 Online Network의 \(\theta\)를 그대로 복사해서 가져온다.

\[ \theta' \leftarrow \theta \quad (\text{특정 스텝마다}) \]

그러면 Loss 식이 이렇게 바뀐다.

\[ L(\theta) = \big( \,r + \gamma \max_{a'} Q(s', a'; \theta') \;-\; Q(s, a; \theta)\, \big)^2 \]

이제 target 쪽은 \(\theta'\)로 계산되니까 한참동안 고정되어있고, 그동안 prediction 쪽 \(\theta\)만 그 고정된 정답을 따라잡으려고 움직인다. 활 쏘는 동안 과녁이 가만히 있어주는 상황이 된 것이다. 그러다 특정 스텝이 지나면 과녁을 한 번 옮기고(\(\theta' \leftarrow \theta\)), 또 한참동안 고정. 이걸 반복해서 moving target problem을 해결한다.

Experience Replay

데이터 독립성과 데이터 분포 변화 문제를 다시 떠올려보자.

매 스텝 경험이 들어올 때마다 그 경험을 바로 학습(online learning)에 써버리면 두 가지가 한꺼번에 터진다.

첫번째로 연속된 프레임끼리 너무 닮아있어서, 거의 똑같은 데이터로 신경망이 계속 업데이트된다. 그러면 한쪽으로 쏠려서 분산이 커지고 비효율적이다.

두번째로 지금 신경망 파라미터가 다음에 볼 데이터를 결정해버린다. 예를 들어 신경망이 "왼쪽으로 가는게 좋다"고 잠깐 판단해서 \(\theta\)가 그쪽으로 움직이면, 그 다음에 쌓이는 경험도 왼쪽 위주가 된다. 그러다 갑자기 오른쪽이 더 좋다고 바뀌면 또 데이터가 통째로 오른쪽으로 넘어간다. 신경망이 자기 자신의 학습 데이터를 직접 정하는 셈인데, 이러다 발산할수도 있다.

그래서 DQN이 들고온게 Experience Replay다. 매 스텝 경험을 바로 학습에 쓰지말고 일단 메모리에 쌓아두자는 것.

매 스텝 에이전트가 환경과 상호작용해서 만들어낸 transition \(e_t = (s_t, a_t, r_t, s_{t+1})\) 을 replay memory \(D\)에 저장한다. 보통 최근 \(N\)개만 유지하는 queue 형태다.

\[ D = \{e_{t-N+1}, e_{t-N+2}, \dots, e_t\} \]

그리고 학습할 때는 방금 들어온 경험으로 업데이트하는게 아니라 \(D\)에서 무작위로 mini-batch를 뽑아서 업데이트한다.

위에서 Target Network를 설명할 때의 Loss는 사실 한 transition만으로 적은 단순화 버전이었고, 논문이 정식으로 정의한 Loss는 기댓값 형태다.

\[ L_i(\theta_i) = \mathbb{E}_{s, a \sim \rho(\cdot)}\Big[\big(y_i - Q(s, a; \theta_i)\big)^2\Big] \]

여기서 \(y_i = \mathbb{E}_{s' \sim \mathcal{E}}\big[r + \gamma \max_{a'} Q(s', a'; \theta') \mid s, a\big]\) 이고, behavior distribution \(\rho\)랑 환경 \(\mathcal{E}\)로부터 나오는 가능한 모든 transition에 대해 기댓값을 취한 거다. 이 Loss의 gradient도 똑같이 기댓값 형태가 나온다.

\[ \nabla_{\theta_i} L_i(\theta_i) = \mathbb{E}_{s,a \sim \rho;\, s' \sim \mathcal{E}}\Big[\big(r + \gamma \max_{a'} Q(s', a'; \theta') - Q(s, a; \theta_i)\big) \nabla_{\theta_i} Q(s, a; \theta_i)\Big] \]

근데 이 기댓값을 그대로 계산하려면 가능한 모든 transition을 다 봐야 한다는건데 그건 불가능하다. 논문은 이걸 어떻게 처리할지 콕 짚는다.

"Rather than computing the full expectations in the above gradient, it is often computationally expedient to optimise the loss function by stochastic gradient descent. If the weights are updated after every time-step, and the expectations are replaced by single samples from the behaviour distribution \(\rho\) and the emulator \(\mathcal{E}\) respectively, then we arrive at the familiar Q-learning algorithm."

 

기댓값 안의 표현을 샘플 한 개로 대체해서 매 스텝 가중치를 업데이트하면 그게 바로 SGD(Stochastic Gradient Descent)이고, 결국 우리가 알던 Q-Learning 업데이트 식이 그대로 나온다는 얘기다.

\[ \theta \leftarrow \theta - \alpha \big(r + \gamma \max_{a'} Q(s', a'; \theta') - Q(s, a; \theta)\big) \nabla_{\theta} Q(s, a; \theta) \]

근데 여기서 문제가 다시 등장한다. 매 스텝 환경에서 방금 받은 샘플 하나로 가중치를 업데이트한다는건 결국 위에서 짚었던 online learning 그 자체다. 연속 프레임끼리 너무 닮아서 gradient에 상관성이 묻고, 그 한 샘플의 noise가 그대로 분산이 되어 학습이 출렁거리고, 신경망이 자기가 학습할 데이터 분포를 직접 결정해버리는 문제가 생긴다. (SGD를 쓰긴 써야 하는데 환경에서 들어오는 대로 그냥 쓰면 망한다는 뜻)

여기서 SGD랑 Experience Replay가 만난다. SGD는 그대로 쓰되, 샘플을 환경에서 방금 받은 transition에서 뽑는게 아니라 replay memory \(D\)에서 무작위로 그것도 mini-batch 단위(\(B\)개)로 뽑아서 그 평균 gradient로 업데이트하는 방식. 식으로 적으면 DQN의 한 업데이트는 이렇게 된다.

\[ \theta \leftarrow \theta - \alpha \cdot \frac{1}{B}\sum_{j=1}^{B} \big(r_j + \gamma \max_{a'} Q(s_j', a'; \theta') - Q(s_j, a_j; \theta)\big) \nabla_{\theta} Q(s_j, a_j; \theta) \] \[ (s_j, a_j, r_j, s_j') \sim \text{Uniform}(D), \quad B=32 \]

이렇게 SGD랑 Experience Replay를 합치면 다음과 같은 효과를 얻을 수 있다.

1. gradient 분산 감소: 무작위로 시점이 한참 떨어진 transition들을 한 mini-batch에 모아서 평균을 내면, 연속 프레임끼리 묻어있던 상관성이 끊긴다. 한 개 샘플로 계산하던 SGD보다 분산이 \(1/B\) 수준으로 줄어들면서 학습이 안정된다.
2. 하나의 경험을 여러 번 재사용: online SGD는 경험 하나 쓰고 그대로 버린다. 근데 메모리에 넣어두면 그 transition이 다음 학습 step에서도, 그 다음 step에서도 또 뽑힐 수 있다. 같은 경험으로 가중치 업데이트를 여러 번 할 수 있으니 데이터 효율이 훨씬 좋아진다.
3. 데이터 분포 평탄화: 매번 메모리 전체에서 골고루 뽑으니까 신경망 파라미터가 잠깐 한쪽으로 흔들려도 학습 데이터가 통째로 쏠려가지 않는다.

위에서 짚었던 두 문제(상관성, 분포 변화)가 그대로 이 세 가지 시너지로 풀린다. SGD와 Experience Replay 중 하나만 따로 떼어놓으면 안 되고, 둘이 묶여야 비로소 DQN의 학습이 성립한다는걸 알 수 있다.

정리

서사

1. Q-Learning은 상태가 너무 많아지면 Table로 다 기록할 수 없음
2. 이것을 해결하기 위해! Table대신 신경망을 도입해서 값을 추정하려 함
3. 그러나 But, 딥러닝과 강화학습을 합치기에 데이터 분산 문제나 상관관계 등의 문제가 있음
4. 그래서 DQN이 Target Network와 Experience Replay, SGD를 사용해서 요것을 해결

이 흐름으로 나는 공부함

전체 DQN 과정

1. 현재 상태 \(s\)에서 \(\epsilon\)-greedy로 행동 \(a\) 선택
2. 환경에서 보상 \(r\)이랑 다음 상태 \(s'\) 받음
3. transition \((s, a, r, s')\)를 메모리 \(D\)에 저장
4. \(D\)에서 무작위로 mini-batch 추출
5. 그 mini-batch로 Loss 계산하고 gradient descent로 \(\theta\) 업데이트
6. 특정 스텝마다 \(\theta' \leftarrow \theta\)

행동을 수집하는 부분(1~3)이랑 신경망을 학습시키는 부분(4~5)이 메모리를 통해 분리되어 있다는게 핵심이다.

2013 DQN의 Experience Replay는 메모리에서 균등 확률로 뽑는다. 중요한 경험이든 시시한 경험이든 똑같이 취급되는데, TD error가 큰(즉 신경망이 아직 잘 모르는) 경험에 우선순위를 두는게 더 효율적일거다. 이 아이디어가 후속 연구인 Prioritized Experience Replay로 이어진다.