Deep Q Network

Deep Q Network

---

DQN은 구글 딥마인드에서 발표한 논문 Playing Atari with Deep Reinforcement Learning과 Human-level control through deep reinforcement learning에서 제시된 강화학습 알고리즘으로, 기존 Q-learning 알고리즘의 Q(action-value) 함수를 딥러닝으로 근사하는 알고리즘이다.

이 알고리즘이 중요한 이유는 딥러닝을 강화학습에 적용하는 것을 어렵게 하는 여러 문제를 (필자가 아는 한 최초로) 해결했기 때문이다. 어려운 점의 대표적인 예시로는

• 성공적인 딥러닝을 위해선 예쁘게 가공된 대규모의 데이터 셋이 필요한데, 강화학습은 input에 대응되는 정답을 명확히 알 수 없을 뿐더러 delay가 있고 noise가 섞인 scalar reward 만으로 네트워크를 학습해야 한다.
• 대부분의 딥러닝 알고리즘은 학습 데이터가 서로 독립적임을 가정하는데, 강화학습에 쓰이는 환경에서 제공하는 데이터는 연속된 행동에 대한 결과이기 때문에 서로 연관되어 있다. 심지어 Agent가 학습함에 따라 policy 또한 달라지면서, 학습 데이터의 distribution 자체도 시간에 따라 변화한다. 딥러닝은 데이터에 대해 fixed underlying distribution을 가정하기 때문에 학습이 제대로 진행되지 않을 수 있다.

가 있다.

DQN은 첫번째 문제에 대해선 특별한 해법을 제시하지 않았고, 두번째 문제는 experience replay라는 개념을 통해 어느정도 해결했다. 어려운 내용은 아니고, 들어오는 입력을 순서대로 사용하면 데이터 간 연관성이 너무 크니까 최근 X개의 데이터(관측 상황, 취한 행동, 행동에 대한 보상, 행동 후 관측한 상황)를 계속해서 저장하고, 네트워크를 학습할 땐 저장한 데이터 중 몇개를 무작위로 샘플해 사용한다는 방법이다. X가 충분히 크면 학습 데이터의 분포가 smooth 해짐을 기대할 수 있다.

이제 DQN의 기본이 되는 오리지널 Q-learning, 2013년 NIPS 버전 DQN 알고리즘, 2015년 NATURE 버전 알고리즘, 실제로 DQN을 구현할 때 쓰이는 트릭 순서로 살펴보도록 하자.

---

 

Q-learning

먼저 강화학습에서 쓰이는 배경 지식에 대해 알아보자. 이미 알고 있다면 건너 뛰어도 된다.

거의 대부분의 강화학습 알고리즘은 환경이 Markov Decision Process(이하 MDP)임을 가정한다. MDP는 다음과 같은 구성 요소로 이루어져 있다.

• $S$ : 가능한 상태의 집합, 유한하다.
• $A$: 가능한 행동의 집합, 유한하다.

• $P$: 상태 간 전이 확률. $P_{ss'}^a =P[S_{t+1}=s'|S_t=s, A_t=a]$ 이다. $S_t$ 는 t번째 시각에서의 관찰된 상태, $A_t$는 $S_t$를 관찰한 후 취한 행동이다.
• $R$ : 보상 함수. $R_s^a = E[R_{t+1}|S_t=s, A_t=a]$ 이다. 보상은 스칼라 값으로 주어진다.
• $\gamma$ : discount factor. 가치 함수를 정의할 때 사용되는 상수값이며, 0 초과 1 미만의 값이다. 다른 구성 요소와 다르게 이 값은 알고리즘을 만드는 사람이 선택할 수 있다.

그러면 다음과 같이 가치 평가 함수를 정의할 수 있다.

• state value function $v(s)$ 는 다음과 같다.

  $$v(s) = E[R_{t+1}+\gamma R_{t+2}+... | S_t=s] = E[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1}|S_t=s]$$

  즉 현재 상태 $s$에서 출발했을 때 앞으로얻을 수 있는 총 보상의 기댓값과 같다.

• action value function $Q(s, a)$ 는 다음과 같다.

  $$Q(s, a) = E[R_{t+1}+\gamma R_{t+2}+... | S_t=s, A_t=a] = E[\sum_{k=0}^{\infty} \gamma^k R_{t+k+1}|S_t=s, A_t=a]$$

  즉 현재 상태 $s$에서 행동 $a$를 취했을 때 앞으로 얻을 수 있는 총 보상의 기댓값과 같다.

이제 주어진 MDP 환경에서 정책(policy)을 학습할 수 있다. 알고리즘은 MDP의 구성 요소 중 상태간 전이 확률과 보상 함수를 알아야 하느냐에 따라 model-based/model-free로, 학습 중인 정책과 상태 샘플링에 쓰이는 정책이 같은지에 따라 on-policy/off-policy로 분류할 수 있다.

Q-learning은 기본적으로 action value function $Q$를 학습하는 알고리즘이다. 계속해서 행동과 관측을 하며 $Q$ 함수를 다음과 같이 업데이트한다.

$$Q(s_t , a_t) \leftarrow R_{t+1}+ \gamma Q(s_{t+1}, a')$$

이 때 주의할 점은 학습에 사용되는 policy가 두가지라는 것이다. 대부분의 경우 특정 상태 $s_t$에서 취할 행동 $a_t$는 $Q$ 함수에 대해 $\epsilon-greedy$ 알고리즘으로 선택하는 반면 업데이트 목표값으로 쓰이는 행동 $a'$는 그냥 $greedy$ 알고리즘을 사용한다. 즉 Q-learning은 off-policy 알고리즘이다. 이러한 방법을 취하는 이유는 $\epsilon-greedy$를 통해 exploration-exploitation에서 exploration의 지분도 확보하면서 업데이트 값 자체는 그냥 $greedy$를 통해 정확하게 업데이트 하기 위함이다.

정리하면 상태 $s_t$에서, $\epsilon-greedy$ 를 통해 이번에 취할 행동 $a_t$를 고른 뒤, 실제로 시행해 바뀐 상태 $s_{t+1}$과 보상 $R_{t+1}$를 관측하고 새로운 상태에서 최적의 행동을 찾아 $Q$ 값을 업데이트 하는 것이다. $a'$를 선택하는 정책을 반영해 식을 다시 쓰면

$$Q(s_t , a_t) \leftarrow R_{t+1}+ \max_a \gamma Q(s_{t+1}, a)$$

가 된다.

이제 임의의 상태에서 시작해 계속해서 위의 업데이트 식을 반복해주면 $Q$ 함수가 optimal하게 수렴함이 보장된다. 구현의 경우 $Q$를 $|S| * |A|$ 크기의 배열이나 python의 dictionary, c++의 map 등의 자료 구조를 사용하면 된다.

---

 

DQN Algorithm (2013 NIPS)

Playing Atari with Deep Reinforcement Learning 버전의 알고리즘을 살펴보자.

기존의 Q-learning 알고리즘과 다른 부분은 크게 두 가지이다.

1. Q 함수를 array나 dictionary가 아닌 neural net으로 구현했다.

   이는 'Q 함수를 딥러닝을 통해 근사했다' 정도로만 생각할 수도 있지만, 그것보단 더 의미 있는 일이다. 먼저 Q 함수를 뉴럴넷으로 근사한 덕분에 Hand-crafted feature가 아닌 이미지 픽셀 정보를 상태로 사용할 수 있게 되었다. 만약 Q 함수를 array로 구현했다면 비슷한 상태, 예를 들어 공의 위치가 1픽셀 정도 다른 두 상태에 대해서 서로 연관성 있는 결과를 얻어내기 힘들 것이다. 하지만 CNN을 통해 게임에서 중요한 정보를 자동으로 뽑아낸 다음 그 feature들을 기반으로 다시 각각의 Q 값을 계산하기 때문에 feature도 자동으로 뽑아내며 작은 상태 변화에 대해 robust한 계산을 기대할 수 있다.

2. Experience replay의 도입.

   기존 Q-learning에서는 target value를 정확하게 학습할 수 있었는데, 그냥 array나 다른 자료구조에 그 값을 대입해버리면 되기 때문이다. 하지만 Q 함수를 neural net으로 구현하면 target value를 정확하게 나타내려면 여러 번의 gradient descent를 시행해야 하고, 무엇보다 기존에 학습한 결과가 바뀔 수 있다. 또한 서론에서 적은 것과 같이 학습 데이터의 분포가 바뀌기 때문에 안정적인 학습이 이루어지기 힘들다. 이 문제점들을 해결해주는게 experience replay의 도입이다.

실제 구현에 관련된 사항은 다음과 같다. 7개의 Atari 게임에 대해 실험을 진행했으며, 모두 똑같은 구현을 사용했다고 한다.

• 상태를 원래의 210 * 160 크기의 RGB image 1 frame이 아니라 연속한 gray-scale image 4 frame을 110 * 84로 다운 샘플링 한 뒤 센터 부분의 84 * 84 부분만 크롭한 것을 스택해서 사용했다. 다운 샘플링은 input의 크기를 줄이기 위해서이고, RGB를 gray-scale로 바꾼 것은 보통 게임에서 플레이어는 다른 색으로 표현되는 경우가 많은데 RGB를 입력으로 받으면 플레이어의 위치를 hand-crafted feature로 받는 것과 다름 없기 때문에 이를 방지하기 위해 시행한 것이다. 스택해서 사용하는 이유는 움직임에 대한 정보를 얻기 위함이다. 벽돌깨기를 예로 들면 한 프레임의 이미지만 가지고는 공이 올라가는 중인지 떨어지는 중인지 알 수 없지만, 네 장의 연속한 프레임이 주어지면 공의 이동 방향을 알 수 있는 것이다.

• Q 함수를 상태와 행동을 입력받으면 가치를 나타내는 스칼라 값을 돌려주는 함수가 아닌, 상태를 입력 받으면 각각 행동에 대응되는 스칼라 값 여러개(=가능한 행동의 개수만큼) 돌려주는 함수로 설정했다. 이렇게 설정하면 한번의 forward pass 계산만으로 모든 행동에 대한 가치 측정이 가능하고, target value $y_j$ 를 계산하는데 드는 비용이 적어진다.

• 네트워크 구조는 다음과 같다.

  1. $84 * 84 * 4$ 크기의 입력 레이어
  2. stride 4, $8 * 8$ 크기의 필터 16개를 적용한 뒤 ReLU 적용
  3. stride 2, $4 * 4$ 크기의 필터 32개를 적용한 뒤 ReLU 적용
  4. 256개의 노드를 가지는 fully-connected 레이어와 연결 후 ReLU 적용
  5. ''가능한 행동의 개수'' 크기의 출력 레이어와 연결

• reward 값은 환경에서 제공하는 값을 그대로 쓰는 것이 아니라 양수면 1, 음수면 -1, 0은 0으로 정규화해서 사용했다. 이를 통해 기울기 값이 너무 커지는 것을 방지하고, 게임마다 보상의 스케일이 달라도 같은 알고리즘을 사용할 수 있게 했다.

• 매 프레임을 정직하게 반영하지 않고 매 4번째 프레임만 사용했다. 논문에선 frame-skipping이라고 되어 있는데 이를 통해 시뮬레이션 속도에 더불어 학습 속도를 빠르게 했다. 반영되지 않은 프레임에선 직전에 선택한 행동을 반복했다.

 

DQN Algorithm (2015 NATURE)

Human-level control through deep reinforcement learning 에서 어떤 개선이 이루어졌는지 살펴보자.

가장 눈에 띄는 변화는 target value의 계산 방식에서 일어났다. 2013년 버전의 경우 target value $y_j$를 계산할 때 $Q$ 함수를 그대로 사용한 반면 2015 버전의 경우 일정 스텝 동안 weight를 고정한 네트워크인 $\hat{Q}$ 을 사용한다. 이를 통해 학습의 불안정성을 개선했다고 한다. off-policy에 이어 off-value(?)를 적용한 셈.

그 외 변경 사항은 다음과 같다.

• 이미지를 전처리 할 때 110 * 84로 줄인 뒤 중앙을 잘라내는 방식이 아니라 처음부터 84 * 84로 rescale했다.

• 네트워크의 구조가 더 깊어졌다.

  1. $84 * 84 * 4$ 크기의 입력 레이어
  2. stride 4, $8 * 8$ 크기의 필터 32개를 적용한 뒤 ReLU 적용
  3. stride 2, $4 * 4$ 크기의 필터 64개를 적용한 뒤 ReLU 적용
  4. stride 1, $3 * 3$ 크기의 필터 64개를 적용한 뒤 ReLU 적용
  5. 512개의 노드를 가지는 fully-connected 레이어와 연결 후 ReLU 적용
  6. ''가능한 행동의 개수'' 크기의 출력 레이어와 연결

• 각 프레임을 그대로 쓰지 않고, 바로 이전 프레임과 픽셀 단위로 max 연산을 취한 프레임을 사용했다. 이는 아타리 게임에서 사용되는 물체 중 홀수번째 프레임에만 등장하거나 짝수번째 프레임에만 등장하는 경우가 있기 때문이다. frame-skipping까지도 고려하면 원래 게임의 $4i+1, 4i+2, 4i+3, 4i+4$ 번째 프레임 중 사용되는 프레임은 $4i+3, 4i+4$ 번째 프레임을 max 연산으로 합친 프레임 하나이고, 이러한 프레임 4개를 쌓아서 하나의 상태로 쓰는 것이다. 즉 하나의 상태는

  $$(max(4i+3, 4i+4), max(4i+7, 4i+8), max(4i+11, 4i+12), max(4i+15, 4i+16))$$

   

  이 되는 것이다.

그 외 사용된 하이퍼 파라미터는 논문에 기록되어 있으니 참고하면 된다.

---

실제 구현에서 쓰이는 트릭 (OpenAI baseline 기준)

논문에 나온 내용만 가지고 DQN을 구현해봤더니 모호한 부분도 많고 잘 동작하지 않았다. 고맙게도 OpenAI에서 여러 강화학습 알고리즘에 대한 baseline 구현을 제공해주므로 이를 추가적으로 살펴보자.

• 각 에피소드의 끝을 에뮬레이터 상의 게임 오버가 아닌 라이프 하나를 사용했을 때로 사용했다.
• 이미지의 값을 0~255 사이의 정수가 아닌 0.0~1.0 사이의 실수값으로 정규화 시켰다. 즉 이미지 값에 255를 나눠서 상태를 제공했다. 만약 이 옵션을 적용시키지 않고 정수값으로 이미지를 사용한다면, 이미지를 스택해서 사용할 때 한 이미지가 여러 번 사용되므로 객체는 하나만 만들고 그것을 가리키는 방식으로 상태를 구현해 메모리를 절약하는 옵션도 있다.
• error 함수 계산에 huber_loss를 적용시키는 것 이외에도 gradient clipping을 따로 진행했다. threshold 값은 10.0으로 설정했다.

---

 

구현

2013, 2015년 버전 각각에 대한 tensorflow 구현을 https://github.com/wwiiiii/DQN 에서 볼 수 있다.

2013 버전의 경우 학습이 안정화 되지 않았다.

2015 버전의 경우 학습이 잘 진행됨을 확인하였다.

각 파일은 다음과 같다.

• agent.py

  Agent 클래스가 구현된 파일이다. Agent 클래스 내에 Q 함수의 상태가 저장되어 있으며, 생성자에서 멤버 함수인 build_qnet을 통해 네트워크를 구축한 뒤 train 함수를 통해 학습을 진행하고, 학습이 끝난 뒤에는 play 함수를 호출해 실행해 볼 수 있다.

• environment.py

  Environment 클래스가 구현된 파일이다. 기본적으로 OpenAI gym의 BreakoutNoFrameSkip-v4(벽돌깨기)의 wrapper 클래스이며, frame-skipping과 두 프레임의 maximum 연산, 이미지를 실수로 정규화하는 전처리를 적용한 뒤 agent에게 관측한 상태를 넘겨준다.

• force_save.txt

  개인 컴퓨터로 학습을 진행할 경우 도중에 일시 정지가 필요한 경우가 있는데, 그 때를 위한 파일이다. 내용을 YES로 바꾸면 현재까지의 학습 내용을 즉시 저장한다.

• main.py

  전체 프로그램 실행을 위한 파일이다. python main.py 를 통해 학습을 시작시킬 수 있다. logger, 학습 환경, 에이전트 순으로 세팅한 뒤 학습을 진행한다.

• option.json

  각종 하이퍼 파라미터와 환경 세팅을 json 파일로 저장한 것이다.

• play.py

  main.py와 같지만 저장된 모델을 불러 시연하고 싶을 때 사용하는 파일이다.

• util.py

  코딩에 쓰이는 여러가지 helper function을 정의한 파일이다. one_hot, random argmax, 이미지 처리 함수, queue, replay memory 등을 구현했다.