[Ch.9] DQN(Deep Q-Networks)

우리는 지금까지 MDP로 정의된 문제를 푸는 강화학습의 여러 방법들을 살펴보았습니다. 하지만, 이는 table형태로 값을 저장하기때문에 현실의 문제를 다루기에는 한계가 있어서 value func.을 parameter w를 이용한 func.으로 approximation하여 이 w을 update시킨다고 했습니다. 이번 포스팅에서는 이러한 강화학습의 func. approximator로써 Deep Learning을 사용하는 DQN에 대해서 다루겠습니다. 이 포스팅에서는 기본적인 neural network에 대해 알고 있다고 가정하고 DQN을 중점적으로 다루겠습니다. 혹시 neural network에 대해 더 알고 싶으신 분은 제가 review하고 있는 reference [1]이나 거기에 참조되어있는 아래 두 링크를 참조하시면 좋겠습니다. 

 

- http://sanghyukchun.github.io/74/ 

상혁님 블로그는 제가 공부할 때 자주 도움을 얻는 블로그입니다. 다루고자하는 주제를 이해하기 쉽게 하위 항목을 체계적으로 가지를 쳐서 설명하고 있습니다. 이 블로그에 올라오는 글들은 블로거분이 모든 개념을 이해한 상태에서 스스로의 말로써 설명하고 있기때문에 많은 insight들이 설명에 담겨있습니다. 제가 읽고 이해한 부분과 비교하면서 읽기에 너무 좋은 컨텐츠들이 많습니다.

  

- http://arxiv.org/pdf/cs/0308031.pdf

ANN에 대해 beginner의 입장에서 차근차근 논문형식으로 설명한 pdf입니다. 기본적인 원리를 수식과 함께 쉽게 설명하고 있습니다. 정말 처음 접하시는 분들이라면 이 pdf에 나와있는 기본 개념들, 용어들을 숙지하신 상태로 위 블로그를 참조하시는게 도움이 되리라 생각합니다.

 

 

---

DQN

 DQN이라는 개념은 AlphaGo를 개발한 DeepMind의 "Playing Atari with Deep Reinforcement Learning"이라는 논문에서 처음 소개되었습니다. 이번 chapter에서는 이 논문을 리뷰하면서 DQN이 무엇인지, 그리고 무얼 받아서 어떤 network을 통과해서 어떤 결과를 내는지에 대해 살펴보겠습니다. 

 What is DQN?

DQN이 무엇인지부터 살펴보겠습니다. 본 논문의 4.1 Preprocessing and Model Architecture의 마지막 단락에서 DQN을 아래와 같이 정의했습니다.

 

We refer to convolutional networks trained with our approach as Deep Q-Networks (DQN). 

 DQN은 Deep Q-Networks을 줄인 말인데 convolutional networks를 이용하여 learning하는 방법을 말한다고 합니다. 이 단 한줄로 설명하기에 생략된 것이 너무 많습니다. 여기에 논문 abstract를 보면 이 network의 input과 output과 함께 위 문장에서 DQN이 무얼 말하고 있는지 대해 아실 수 있습니다. 

 

We present the first deep learning model to successfully learn control policies directly from high-dimensional sensory input using reinforcement learning. The model is a convolutional neural network, trained with a variant of Q-learning, whose input is raw pixels and whose output is a value function estimating future rewards. We apply our method to seven Atari 2600 games from the Arcade Learning Environment, with no adjustment of the architecture or learning algorithm. We find that it outperforms all previous approaches on six of the games and surpasses a human expert on three of them.

 DQN은 Atari Game의 raw pixel들을 input으로해서 CNN을 function approximator로 이용하여 value function을 output으로 내고 있습니다. 결국 그 value function은 future reward를 추정하는데 이용되는 재료가 되겠네요.

 Issues between Deep Learning and Reinforcement Learning

Recent breakthroughs in computer vision and speech recognition have relied on efficiently training deep neural networks on very large training sets. The most successful approaches are trained directly from the raw inputs, using lightweight updates based on stochastic gradient descent. By feeding sufficient data into deep neural networks, it is often possible to learn better representations than handcrafted features [11]. These successes motivate our approach to reinforcement learning. Our goal is to connect a reinforcement learning algorithm to a deep neural network which operates directly on RGB images and efficiently process training data by using stochastic gradient updates.

 이 논문이 발표되기 전까지 RL분야에서 agent가 high-dimensional한 vision 및 language data들을 직접 다루는 것이 불가능에 가까웠습니다. 그나마 agent가 다룰 수 있게 hand-crafted features를 이용하는 것이 전부였다고 합니다. 현실 세계의 문제를 풀기 위해서는 반드시 high dimensional data를 다루는 것이 반드시 해결해야할 과제였습니다. 그리고 DL분야에서 RNN, CNN, RBM 등 high dimensional data를 다루는 방법들이 등장하고 RL에 이 방법론을 적용하고자하는 시도를 하게 됩니다. 하지만, 두 분야에는 data input이나 분포 등에서 차이가 존재하기 RL에 DL 방법론을 적용할 때 issue가 발생합니다.

 

However, reinforcement learning presents several challenges from a deep learning perspective. Firstly, most successful deep learning applications to date have required large amounts of handlabelled 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. The delay between actions and resulting rewards, which can be thousands of timesteps long, seems particularly daunting when compared to the direct association between inputs and targets found in supervised learning. 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. 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.

 

 

• Issue 1. 성공적인 Deep Learning applications는 hand-labelled training data set을 요하는데, Reinforcement Learning에서는 오로지reward를 통해 학습이 이루어지고, 그 reward도 sparse하고 noisy 심지어는 delay되어 주어진다.
  
  
• Issue 2. Deep Learning에서는 data sample이 i.i.d. 분포를 가정하지만, Reinforcement Learning에서는 현재 state가 어디인지에 따라 갈 수 있는 다음 state가 결정되기때문에 state간의 correlation이 크다. 즉, data간의 correlation이 크다.

본 논문은 experience replay라는 방법으로 위 issue들을 해결하여 RL에 DL 방법론을 성공적으로 접목시킵니다.  

 

1. raw pixel을 받아와 directly input data로 다룬 것

2. CNN을 function approximator로 이용한 것

3. 하나의 agent가 여러 종류의 Atari game을 학습할 수 있는 능력을 갖춘 것

4. Experience replay를 사용하여 data efficiency를 향상한 것

 

이 논문에는 위와 같이 4가지 주목할만한 contribution이 있습니다. 이를 잘 보면 서로 관련이 있는 것이 있습니다. raw pixel을 받아와서 directly input data를 다룸으로써 하나의 agent가 여러 종류의 game을 learning할 수 있었고, DL의 방법론인 CNN을 RL에 적용하기 위해 experience replay라는 방법을 도입했습니다. 관련이 있는 2가지를 각각 그룹핑해서 다루어 보겠습니다.

 

2, 4 - Experience replay

1, 3 - Input data

 Experience replay

이전에 살펴본 algorithm들과 같이 본 논문이 나오기 전에는 environment와 상호작용하며 얻어진 on-policy sample들, 

을 통해 parameter를 update하였습니다. 하지만, 이와 같은 방법은 on-policy sample을 통해 update하기때문에 sample에 대한 의존성이 커서 policy가 converge하지 못하고 oscillate할 수 있습니다. 이러한 문제를 해결하고자, 착안한 아이디어가 Experience replay입니다. 각 time-step별로 얻은 sample(experience)들을 아래와 같은 tuple형태로 data set에 저장해두고, randomly draw하여 mini-batch를 구성하고 update하는 방법입니다. 

 

 

이때, data set은 무한히 저장할 수 없기 때문에 N으로 고정하고, FIFO방식으로 저장합니다. 또한 input으로써 arbitrary length를 받는데에 어려움이 있기 때문에 function Φ를 정의하여 pre-processing하여 state의 length를 fixed시킵니다. Experience replay를 이용하면 아래와 같은 이점을 얻을 수 있습니다.

• data sample을 한번 update하고 버리는 기존의 방법과 달리 random sampling을 함으로써 data usage efficiency를 도모할 수 있습니다.
• RL에서 발생할 수 있는 state간의 high correlation 문제(위에서 언급한 Issue 2. correlation문제)를 해결 할 수 있습니다현재 update된 parameter를 통해 다음 training의 대상이 되는 sample을 어느정도 determine할 수 있습니다. 
• 현재의 policy에 따라 argmax action을 고르고 난 뒤, 그 다음 training sample은 이 action에 따라 결정됩니다. 이를 current sample에 의해 다음 training sample이 dominate되었다고 말합니다. 본 논문에 따르면, 이렇게 되면 불필요한 feedback loops를 돌거나, parameter들이 local minimum에 빠지거나 diverge하는 경우를 찾아낼 수 있어서, 이를 방지할 수 있다고 합니다. 주의할 점은, experience replay를 사용할 땐, 반드시 off-policy로 learning해야하는데, 이는 current parameter가 update하는 sample들과 다르기때문입니다. 

 

 

 

 Input data of DQN

아래는 DQN의 Algorithm입니다.

 

<Fig 1. Algorithm>

 

finite capacity N을 가진 replay memory D를 정의하고 Q-learning을 위해 Q-value를 initialize시킵니다. 1 episode동안 sequence를 initialize시키고 pre-process시킵니다. 

 

<Fig 2. Pre-processing>

 

pre-processing의 과정은 다음과 같습니다. 주어진 history 중에서 down-sizing과 gray scale을 하고, GPU환경에 맞게 square로 crop한 뒤, last 4 frame을 stack으로 쌓습니다. 그 다음 time-step마다 e-greedy방식으로 action을 취하고, 이를 통해 reward와 다음 state(St+1)를 pre-processing하여 experience을 구성하고 D에 저장합니다. 그리고 D에 저장된 sample을 mini-batch로 취하여 사전에 정의된 loss를 minimize하도록 GD update시킵니다. DQN network는 CNN을 이용하며, 아래와 같은 구조를 이용합니다.

 

 

<Fig 3. DQN model architecture>

 

마치며

DQN을 Doubling하거나 Dual로 update하는 구조도 있습니다. 이는 실습 Part 4에서 다루어 보도록 하고 다음 포스팅은 Policy gradient에 대해 다루겠습니다. 

 

오탈자나 잘못 언급된 부분이 있으면 댓글로 지적해 주세요 :)

Reference

[1] https://legacy.gitbook.com/book/dnddnjs/rl/details, 9. DQN p.124-137

[2] http://sanghyukchun.github.io/90/

[3] https://mc.ai/rl-dqn-deep-q-network/