들어가며...

Q-Learning의 Update를 다시 적어보면,

$$Q(S_t,A_t) \leftarrow Q(S_t,A_t) + \alpha \left[ R_{t+1}+\gamma\max_{a'}Q(S_{t+1},a')-Q(S_t,A_t) \right]$$

이다.

State와 Action이 적을 때는 $Q(s,a)$를 Table에 저장하면 된다. 하지만 State가 게임 화면이라면 가능한 이미지를 전부 Table의 행으로 만들 수 없다.

DQN, Deep Q-Network의 핵심 아이디어는 간단하다.

Q-table 대신 Neural Network가 State를 보고 모든 Action의 Q값을 한 번에 출력하게 만든다.

아이디어는 간단하지만 Neural Network와 Q-Learning을 그대로 합치면 학습이 쉽게 흔들린다. 연속된 경험이 서로 너무 닮아 있고, Network가 예측과 Target을 동시에 바꾸기 때문이다.

이번 글에서는 DQN의 세 구성 요소인 Q-network, Experience replay, Target network를 각각 왜 필요한지 중심으로 정리한다.

화면에서 Q값까지

Atari 같은 환경에서는 한 장의 화면만 보고 물체가 어느 방향으로 움직이는지 알기 어렵다. 그래서 DQN은 연속된 여러 Frame을 State로 묶는다.

$$S_t = \left[ X_{t-3},X_{t-2},X_{t-1},X_t \right]$$

Network에 $S_t$를 넣으면 가능한 Action마다 Q값이 나온다.

$$Q(S_t,\cdot;\mathbf w) = \begin{bmatrix} Q(S_t,\text{LEFT};\mathbf w) \\ Q(S_t,\text{RIGHT};\mathbf w) \\ Q(S_t,\text{JUMP};\mathbf w) \\ Q(S_t,\text{WAIT};\mathbf w) \end{bmatrix}$$

Action을 고를 때는 $\epsilon$-greedy를 사용할 수 있다. 대부분 가장 큰 Q값의 Action을 고르고, 가끔 Random action을 선택해 탐색한다.

DQN의 Loss

한 Transition을,

$$(S_t,A_t,R_{t+1},S_{t+1})$$

이라고 하자.

Q-Learning Target은 다음과 같다.

$$Y_t = R_{t+1} + \gamma\max_{a'}Q(S_{t+1},a';\mathbf w^-)$$

$\mathbf w^-$는 잠시 뒤 설명할 Target network의 Parameter다. 현재 Network의 예측은,

$$Q(S_t,A_t;\mathbf w)$$

이고 둘의 Squared error를 줄인다.

$$L(\mathbf w) = \mathbb E \left[ \left( Y_t-Q(S_t,A_t;\mathbf w) \right)^2 \right]$$

Supervised learning처럼 보이지만 Target $Y_t$가 고정된 Label은 아니다. 학습 중인 Q값으로 만든 움직이는 Target이다. 이 차이가 DQN의 안정화 장치를 필요하게 만든다.

문제 1: 시간 순서의 경험은 서로 너무 닮았다

Agent가 오른쪽으로 걷고 있다면 시간 $t$, $t+1$, $t+2$의 화면은 거의 같다. 이 Transition을 순서대로 Network에 넣으면 Mini-batch 안의 Sample들이 강하게 Correlated된다.

일반적인 Supervised learning에서는 Data를 Shuffle한다. DQN도 경험을 바로 한 번 쓰고 버리지 않고 Replay buffer $\mathcal D$에 저장한다.

$$\mathcal D = \left\{ (s_i,a_i,r_i,s'_i) \right\}$$

학습할 때는 과거 Transition을 Random하게 뽑아 Mini-batch를 만든다.

$$(s,a,r,s') \sim \mathcal D$$

Experience replay는 두 가지 역할을 한다.

1. 연속 Sample의 상관을 줄여 Mini-batch를 더 다양하게 만든다.
2. 환경과 상호작용해 얻은 비싼 경험을 여러 번 재사용한다.

다만 아주 오래된 경험은 현재 Policy의 분포와 다를 수 있다. DQN이 Q-Learning 기반의 Off-policy Algorithm이기 때문에 재사용이 가능하지만, Buffer의 크기와 데이터 분포는 여전히 학습에 영향을 준다.

문제 2: 쫓아가는 Target도 같이 움직인다

만약 하나의 Network $\mathbf w$로 현재 예측과 다음 State Target을 모두 계산하면,

$$Y_t = R_{t+1} + \gamma\max_{a'}Q(S_{t+1},a';\mathbf w)$$

가 된다.

$\mathbf w$를 한 번 Update하면 왼쪽의 예측도 바뀌고 오른쪽의 Target도 바뀐다. 시험 답을 고치는 동시에 채점 기준도 계속 고치는 셈이다.

DQN은 같은 구조의 Network를 두 개 둔다.

• Online network $Q(s,a;\mathbf w)$: 매 Step Gradient로 Update한다.
• Target network $Q(s,a;\mathbf w^-)$: 일정 기간 고정해 Target만 계산한다.

일정한 $C$ Step마다,

$$\mathbf w^- \leftarrow \mathbf w$$

로 Online network의 Parameter를 복사한다. 또는 매 Step 조금씩 섞는 Soft update를 사용할 수도 있다.

$$\mathbf w^- \leftarrow \tau\mathbf w + (1-\tau)\mathbf w^-$$

Terminal에서는 미래 Value가 없다

$S_{t+1}$이 Terminal state라면 Episode가 끝났으므로 이후 Reward가 없다.

$$Y_t=R_{t+1}$$

구현에서는 Done mask를 사용해 한 식으로 쓸 수 있다.

$$Y_t = R_{t+1} + \gamma(1-D_t) \max_{a'}Q(S_{t+1},a';\mathbf w^-)$$

$D_t=1$이면 Bootstrap 항이 사라진다. 다만 시간 제한 때문에 잘린 Truncation과 실제 Terminal을 같은 것으로 처리하면 미래 Value를 잘못 없앨 수 있다. 마지막 글에서 이 구분을 다시 다룬다.

DQN 학습 과정을 순서대로 보면

1. 현재 State에서 $\epsilon$-greedy로 Action을 고른다.
2. 환경에서 Reward와 Next state를 받는다.
3. Transition을 Replay buffer에 저장한다.
4. Buffer에서 Random mini-batch를 뽑는다.
5. Target network로 $Y_t$를 계산한다.
6. Online network의 $Q(s,a;\mathbf w)$가 $Y_t$에 가까워지도록 Update한다.
7. 일정 Step마다 Online Parameter를 Target network로 복사한다.

한 줄의 핵심 Update는,

$$\mathbf w \leftarrow \mathbf w + \alpha \left[ Y_t-Q(S_t,A_t;\mathbf w) \right] \nabla_{\mathbf w}Q(S_t,A_t;\mathbf w)$$

이다.

Max가 만드는 과대 추정

Target의 $\max$는 추정 Noise가 있는 여러 Action 중 우연히 높게 나온 값을 선택하는 경향이 있다.

$$\max_{a'}Q(S_{t+1},a')$$

이 때문에 Q값이 실제보다 과대 추정될 수 있다. Double DQN은 Action 선택과 평가를 분리한다.

$$a^* = \arg\max_{a'}Q(S_{t+1},a';\mathbf w)$$ $$Y_t = R_{t+1} + \gamma Q(S_{t+1},a^*;\mathbf w^-)$$

Online network가 Action을 고르고 Target network가 그 Action의 값을 평가한다.

DQN이 잘 맞지 않는 경우

DQN은 각 Action의 Q값을 하나씩 출력하므로 Action이 유한한 Discrete space일 때 자연스럽다. Robot torque처럼 Action이 연속이면 모든 Action의 Q값을 나열할 수 없고 $\max_a Q(s,a)$도 쉽게 계산되지 않는다.

또한 DQN은 다음 한계가 있다.

• 많은 환경 상호작용이 필요할 수 있다.
• Replay buffer와 Target update 주기에 민감하다.
• Q값 과대 추정과 불안정성이 남아 있다.
• Policy 자체를 직접 표현하지 않는다.

연속 Action과 직접적인 Policy 학습은 다음 글의 Policy Gradient가 다룬다.

이번 글에서 기억할 것

DQN은 Q-table을 Neural Network로 바꾸고, Replay buffer와 Target network로 데이터 상관과 움직이는 Target 문제를 완화한다.

1. Network는 한 State에서 가능한 Action의 Q값을 출력한다.
2. Experience replay는 경험을 섞고 재사용한다.
3. Target network는 학습 목표가 너무 빠르게 움직이지 않도록 잠시 고정한다.
4. DQN의 Target은 $R+\gamma\max Q_{\text{target}}$이다.
5. 기본 DQN은 Discrete action에 적합하고, $\max$ 때문에 과대 추정될 수 있다.

참고 자료

• David Silver, Lecture 6: Value Function Approximation
• Mnih et al., Human-level control through deep reinforcement learning
• 서울대학교 DSBA 연구실, Introduction of Reinforcement Learning