[Part 4] Deep Q-Networks and Beyond

포스팅에 앞서 Reference의 contents를 review하는 글임을 밝힙니다.

이번 포스팅에서는 강화학습의 Q-networks에 Deep Learning을 적용한 Deep Q-networks를 다루겠습니다. Part 0의 FrozenLake 예제에서는 Q-net이 table을 이용한 방법보다 좋은 성능을 내지 못했습니다. 하지만 Google DeepMind의 Playing Atari with Deep Reinforcement Learning(2013) 논문에서 적용한 아래의 세 가지 사항을 반영한 DQN을 구성하여 FrozenLake와 비슷한 환경에서 agent를 구성해보겠습니다. 우리가 Q-net에 반영할 사항은 아래 세 가지 입니다.

1) CNN(Convolution Neural Network)을 적용해서 화면의 pixel을 input data로 입력받는다.

2) Replay memory에 경험한 Transition pair들을 저장하고 재사용 한다(Experience Replay).

3) Q-value를 계산하는데 있어서, Target Network를 따로 구성하여 학습한다.

기존 Q-network에 위 항목별로 어떻게 적용하여 DQN을 구성했는지, 그리고 이에 더 진보딘 모델 Double DQN, Dualing DQN까지 살펴보고 grid world 환경에서 이를 적용한 agent를 다루겠습니다.

---

Q-Network to Deep Q-Netwrok 

 CNN network

 Atari game의 raw pixel을 directly input으로 사용하기위해 CNN network를 사용했습니다. 이는 pixels를 독립적인 input으로 삼기보다는 주변 pixel과 함께 하나의 region으로써 인식하기 위함입니다. CNN이 인간이 시각세포를 이용하여 시각을 얻는 방법과 유사하다는 연구결과도 존재합니다.  

 Experience Replay

 Experience replay는 본 블로그 Ch.9 DQN에서 다루었습니다. 핵심은, agent의 experience를 FIFO로 data set에 저장해두고, update시에 radomly draw하여 mini-batch로 구성한 뒤에 parameter를 update합니다. 이 example에서는 pre-processing과정을 거치지 않습니다.

 Target Network

 하나의 Network를 사용하지 않고 분리된 target network를 둔다는 것은 update를 하는 동안 target을 계산하는 다음의 식에서, 

계산에 사용되는 parameter를 고정한다는 것입니다. 즉, network에 사용되는 parameter들을 θi 라고 할 때(network 상에서의 w나 b등의 model parameter), parameter θ 를 아래 loss function,

에 의해 update하는 동안 θi-1 은 고정합니다. 이렇게 target network을 따로 두는(이전 parameter를 고정하는) 이유는, target의 값을 구할 때, 이 parameter의 영향을 크게 받기때문에 보다 안정적으로 계산하기 위해서입니다. 만약 이렇게 하지 않는다면, target Q value를 구할 때, parameter에 영향을 크게 받아 무한한 feedback loop에 빠지게 되고, estimated Q-value가 target으로 안정적으로 update되지 않을 수 있습니다. 따라서, 우리가 update할 target network의 parameter는 fix하고 update합니다. 

Beyond DQN

2013년 "Playing atari ~" 논문에서 DQN이 소개되고나서 보다 빠르고 안정성이 향상된 DQN architecture가 연구되었습니다. 이 중 Double DQN과 Dualing DQN에 대해 알아보고, 또 grid world에서 구현한 agent에도 적용해 보고자 합니다.

 Double DQN

 Double DQN이 normal DQN에 대해 제기한 문제의식은, data sampling시 frequent state에서의 action에 따라 결정되는 Q-value가 overestimate되지 않겠냐는 것입니다. 이렇게 된다면 optimal action이 아닌 다른(sub optimal) action을 취하도록 학습이 될 우려가 있고, 이는 곧 ideal policy를 학습하는데 방해요소가 됩니다. 이를 다음의 간단한 아이디어로 해결하자고 한 것이 Double DQN입니다. 

target Q value(yi)를 계산할 때, 기존의 DQN network에서는 단순히 target network에서 given parameter로 maximum Q를 취했지만, Double DQN에서는 maximum을 고르기 위한 Q들을 구할 때, 다음 state에 대해 Q value를 maximize하는 action을 target network가 아닌, DQN network에서 구하고나서 maximum Q를 target network에서 계산하는 방식을 따릅니다.

 Dualing DQN

 Dualing DQN의 idea는 Q-value를 2개로 쪼개는 것으로부터 출발합니다. 기존의 Q-value는 주어진 state에서 action을 취했을 때의 value를 의미하는데 이 Q-value를 다음과 같은 2개의 term으로 나누어서 바라보는 겁니다.

여기서 V(s)는 우리가 알고 있는 (state) value function입니다. 여기에 A(a,s)라는 함수를 추가로 정의하는데, 다른 action을 취했을 때보다 얼마나 더 좋은지를 나타내는 함수(advantage function)입니다. Dueling DQN은 Q-value를 이렇게 2가지로 나누어서 각각 계산하고, 마지막에 이를 다시 결합합니다. 

<Fig1. Dualing DQN network> top : single stream Q-network, bottom : dualing Q-network

나중에 합칠 것을 왜 미리 나누어서 다시 합치는 과정을 해야할 지 의문이 듭니다. 해당 논문을 참조하시면, 예제를 통해서 이를 설명하고 있습니다. 사용된 예제는 Atari의 Enduro라는 게임으로, 다른 차를 피해 racing하는 game입니다. 예제를 살펴보기전에 간단히 어떻게 하는 게임인지 영상을 찾아보았습니다. 차를 좌우로 움직일 수 있고 길은 계속해서 변화하고 장애물이 될만한 차들이 도로 상에 있습니다. 그리고 길을 따라 계속 가기만 한다면 score는 계속해서 쌓이고 길 가드레일에 부딪히면 score가 쌓이는 속도가 일시적으로 줄어듭니다.

<Video1. Enduro game(Atari)>

<Fig2. Enduro game agent> : attend and drive>

Value stream과 Advantage stream 관점에서 나누어봤을때 agent가 앞으로의 reward를 얻기 위해 어디에 관심을 두는지를 red-tint로 화면 상에 표시한 것입니다. 위 그림을 먼저 보시면 지평선 끝에 차 한대가 작게 있는 것을 볼 수 있습니다. 먼저, value stream 관점에서는 앞으로의 reward를 최대화 하기 위해서 agent는 1) score와 2) 멀리 있는 차(장애물) 그리고 3) 차를 피하기위해 가야할 길에 attend합니다. 이에 비해, advantage stream 관점에서는 attend하는 것이 없습니다. 당장에 action을 취하지 않아도 어차피 차는 나아가고 score는 쌓이고 있기 때문입니다. 이제 아래 그림을 보면 차와 다른 차들이 매우 가깝습니다. 그렇기 때문에 value stream 입장에서는 1) score 2) 당장 앞에 있는 차들(장애물) 3) 우리가 계속 score를 쌓기 위해 장애물들을 피해 나아가야할 곳에 attend합니다. advantage stream을 보면 당장에 action을 취하지 않으면 reward를 얻는데 영향을 주기 때문에 이때는 앞에 있는 차에 신경을 써서 action을 취해야합니다.

이렇게 Q-learning을 두 가지 stream으로 dualing하면, agent가 state마다 action을 해보면서 그 결과를 학습하지 않아도 어떤 state가 valuable한지 알 수 있습니다. normal DQN에서는 agent가 state에서 각 action에 대한 Q-value를 계산해야합니다. 하지만, value function이 좋지 않을 때, 즉, state가 dangerous하거나 reward를 얻기에 좋지 않은 state에서도 Q-value를 계산해봐야하고, state에서 할 수 있는 모든 action들이 나쁜결과를 초래하더라도 계산해봐야합니다. 제가 논문을 읽으면서 생각하기에, dualing의 본질은 normal DQN에서는 state와 action pair로 Q-learning을 계산하는데, 이 둘 중 어느 하나라도 나쁘면, 그걸로 Q-value를 계산해봤자 optimal policy를 learning하는데 방해만 되니, 조금이라도 아닌애들은 재껴두고 알짜배기들만 learning하겠다는 것입니다. 이렇게 하면, 불필요한 연산시간도 줄일 뿐더러 조금 더 quality 높은 sample들로 learning할 수 있겠다고 생각이 드네요.

아래는 본 reference [1]의 저자가 제작한 grid world 환경에서 이를 구현한 code입니다. grid world는 아래와 같이 파란 블록을 움직여 빨간 블록을 피하며 초록색 블록으로 가는 단순한 환경입니다. 이 환경은 매 episode마다 사각형의 개수와 위치가 바뀝니다. Frozen Lake처럼 고정된 환경이 아니므로 agent learning하는데 조금 더 어렵고, 시간이 걸립니다.

<Fig3. Simple Grid world>

gridworld 모듈은 https://github.com/awjuliani/DeepRL-Agents/blob/master/gridworld.py 에서 받을 수 있습니다.

마치며

다음 포스팅은 Part.5  Visualizing an Agent’s Thoughts and Actions입니다. 위에서 구현한 agent가 실제로 어떻게 학습하는지, 그리고 action을 취했을 때의 reward는 무엇인지를 시각화하여 보여주는 방법론을 다룬 글입니다. 

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

Reference

[1] https://medium.com/@awjuliani/simple-reinforcement-learning-with-tensorflow-part-4-deep-q-networks-and-beyond-8438a3e2b8df

[2] http://ishuca.tistory.com/391

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

[4] https://medium.freecodecamp.org/improvements-in-deep-q-learning-dueling-double-dqn-prioritized-experience-replay-and-fixed-58b130cc5682

[5] http://papers.nips.cc/paper/3964-double-q-learning.pdf

[6] https://arxiv.org/pdf/1511.06581.pdf