[Part 0] Q-Learning with Tables and Neural Networks

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

이번 포스팅에서는 강화학습의 Q-Learning 알고리즘을 알아보겠습니다. 강화학습의 방법론에서 policy gradient은 agent가 인식한(observe) state에 action을 직접적으로 연결하는 함수를 이용하는 반면, Q-Learning은 주어진 state에 대한 value를 학습해서 특정한 action을 선택하는 것으로 학습합니다. 먼저 Deep learning으로 학습하는 것에 앞서서 간단히 Table로 알고리즘을 구현하여 기초적인 원리를 이해하고, 이 후에 Neural Network를 이용하여 구현해보겠습니다. 

---

Tabular Approaches for Tabular Environments(Q-Table)

사용하는 예제는 OpenAI gym에서 제공하는 FrozenLake입니다. FrozenLake는 한번 쯤은 접해보실 기회가 있을 것 같은데, pokemon게임 시리즈에 자주 등장합니다. 

  

<Fig1. FrozenLake example in pokemon game>

보시는 것과 같이 pokemon에 있는 FrozenLakes는 미끄러지는 얼음판 위에 장애물이 있고, 얼음판 위에서 이동할 시에는 장애물에 부딪히기 전까지는 움직임을 컨트롤할 수 없습니다. 

하지만, 여기서 다룰 OpenAI gym의 FrozenLake는 다음과 같은 규칙을 갖는 환경입니다.

ㆍStructure : 4 X 4 grid 모양

ㆍState : Start / Goal / Safe-Frozen / Dangerous hole (4가지)

ㆍAction : Up / Left / Down / Right (4가지)

ㆍReward : Goal state를 지날 때 1, 그 외의 step은 0 

ㆍObjective : agent가 시작 블록에서 목표 블록으로 구멍을 피해서 이동하는 것을 학습

ㆍCatch : 해당 grid world에는 바람이 불고 있어 agent가 수행하는 행동에 방해가 되는 상황

먼저, FrozenLake-v0의 주어진 state를 보면 아래와 같습니다.

<Fig.2 FrozenLake-v0 Env.>

Start state에서 시작으로 짙은 회색으로 칠한 hole을 피해 goal state로 도달하는 것이 Agent의 강화학습 목표입니다.

그럼 Q-Table을 이용한 코드를 보겠습니다. 해당 코드는 원문 코드에 제가 약간의 이해를 돕기 위해 부연 설명을 달아 놓고, 추가적으로 커스터마이징 했습니다.

In [5] 부분을 보시면, action 값이 0, 1, 2, 3일 때 각각 Left, Down, Right, UP의 실제 행동으로 mapping되는 것을 보실 수 있습니다. 

ln [7] for문에서 a을 선택하는 부분을 보시면, Q-Table의 state 행을 가져와서 standard normal distribution을 따르는 4개의 숫자를 발생시켜 더합니다. 이렇게 생성된 Q-value의 최댓값이 있는 열의 action을 수행하여 env.로부터 s1(next state), r(reward), d(간접적으로는 state가 어떠한 종류인지 직접적으로는 loop를 끝내는 state인지 아닌지), info(확률)을 받습니다.

Q-Table을 update하는 부분은 다음과 같은 수식을 기반으로 합니다.

현재 state s에서 위에서 선택한 action a을 했을 때, 현재 Q-value를 받은 reward와 next Q value의 정보를 반영하여 수정하는 것입니다.

In [7] while loop는 하나의 episode마다 진행하는 여러 step을 구현한 것인데, 종료조건이 d = True입니다. d가 True가 되는 경우는 아래와 같이 goal 혹은 hole에 도달했을 때 입니다. (첨부파일이 길어질 것 같아 for문에 print 함수는 모두 주석처리 했습니다.) 이렇게 while 문이 종료되면 해당 episode를 마치고 다음 episode로 진행합니다

  

<Fig 3. env.render() 결과 예시>

In [7] for문은 이렇게 while loop가 종료되고 다음 episode로 넘어가기 전에 rList라는 변수의 reward list에 해당 episode에서 받은 reward를 저장하게되는데, goal에 도달하고 끝난 경우는 1, hole에 도달하는 경우는 0이 저장됩니다. 그래서 최종적으로 정확도를 계산할 때, rList의 값을 모두 더하면 2000번의 episode중에서 goal에 도달하고 끝난 경우를 count하는 것과 같습니다. 제 경우에는 0.585가 나왔으니 0.585 * 2000 = 1170번 goal state에 도달했네요.(In [8])

In [9] 의 Q-table로 알 수 있는 것은 각 state에서 취할 수 있는 action들의 Q-value입니다. 해당 table에 저장된 Q-value들을 보고 agent가 해당 state에 도달했을 때, 그래도 Q-value가 높은 action을 취할 가능성이 높게됩니다. In[10]의 print는 각각 state 0, state 1, .... state 15에서 취할 action들을 나열한 것입니다.(start부터 0, 1, 2, ... , goal이 15입니다.) 보시면 hole과 goal state에서는 종료되므로 Q-value값이 0이 됩니다. 

Q-Learning with Neural Networks

앞서서 Q-Table로 문제를 풀어보았는데, agent가 실제로 받아들이고 즉각적인 반응을 이끌어내기도 어렵고, 조금 더 복잡한 실제 문제에 경우 Table을 생성하는 것 자체만으로도 큰 연산이 필요합니다. 따라서 Table이 아닌 action에 대한 Q-value를 얻을 수 있는 방법이 필요합니다. 이때 이 방법이 neural networks를 이용하는 방법입니다. 실제의 값을 모두 observe하여 수치화하는 것이 아닌 function approximator로써 data를 얻을 수 있습니다(이는 실제 data를 빠짐없이 observe하여 저장하는 것보다 효율적입니다). 

이 예제에서는 1X16의 one-hot vector의 형태 인코딩하여 각 action에 대한 Q-value를 도출합니다. 그리고 이 vector는 neural network의 알고리즘에 따라 loss function과 back-propagation으로 weight을 학습하여 update됩니다. 사용되는 loss는 현재 추정한 Q-value와 다음 state에서의 Q-value(Q-target)과의 차의 제곱을 사용합니다. 코드를 보겠습니다.

Q-Table과 비교해서 성능이 그렇게 좋지는 못한 듯 합니다. layer도 더 추가하거나 조금 더 다양한 variation을 줄 수 있는 반면 아직은 robust하지 않은 결과를 내고 있습니다. 하지만 neural network를 이용하는 것은 분명 많은 이점들이 있습니다. 

마치며

다음 포스팅은 Part 1 Two-Armed bandit에 대해 포스팅하겠습니다.

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

Reference

[1] https://medium.com/emergent-future/simple-reinforcement-learning-with-tensorflow-part-0-q-learning-with-tables-and-neural-networks-d195264329d0

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