close_btn
로그인, 회원가입후 더 많은 혜택을 누리세요 로그인 회원가입 닫기

2016.07.12 Leewoongwon


Reinforcement Learning 그리고 OpenAI

 

<Contents>

 

1. Introduction to OpenAI

 

2-1. Intro to Reinforcement Learning (1) MDP & Value Function

2-2. Intro to Reinforcement Learning (2) Q Learning

 

3-1. CartPole with Deep Q Learning (1) CartPole example  

3-2. CartPole with Deep Q Learning (2) DQN(Deep Q-Networks)

3-3. CartPole with Deep Q Learning (3) TensorFlow

3-4. CartPole with Deep Q Learning (4) Code review

 

4-1. CartPole with Policy Gadient (1) Policy Gradient

4-2. CartPole with Policy Gadient (2) Code review

 

5-1. about Atari games

5-2. Atari "Pong"

5-3. Atari "Breakout"

 

6. MuJoCo


 


2-1. Intro to Reinforcement Learning (1) Q Learning

 

David Silver교수님의 RL course의 강의내용과 자료를 참고하여 작성하였습니다.

http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching.html

 

1. Bellman equation

지난 강의에서 MDP(Markov Decision Process)와 Value function에 대해서 살펴보았습니다. Agent는 이 value function을 가지고 자신의 행동을 선택하게 됩니다. value function에는 두 가지가 있는데 다음과 같이 정의됩니다. 둘 중에서 action-value function이 environment의 model을 몰라도 되므로 실재로 강화학습에서 많이 사용된다고 언급했었습니다.

Screenshot from 2016-07-12 17:23:24.png

 

과연 agent가 이 value function을 가지고 어떻게 학습할 지에 대해서 알려면 Bellman equation을 알아야 합니다.  어떠한 state에서의 value function은 다음 state의 value function과 다음과 같은 상관관계가 있습니다. 즉, 현재 state의 value function은 다음 state의 discounted value function에 지금 어떠한 행동을 해서 받는 reward를 합한 것입니다. 앞에 expectation이 붙은 것은 reward도 어떠한 action을 취하는 지에 따라 다르고 도착하는 state 또한 달라질 것이기 때문입니다. 이러한 식을 Bellman Expectation equation이라고 합니다.

 

강화학습하는 agent의 입장에서 봤을 때는 처음에는 각 state의 value function을 알 수가 없습니다. agent가 경험을 하면서 각 state의 value function을 배워가게 되는데 만약에 각 state의 value function이 true값이라면 다음 식이 만족하게 될 것입니다.

Screenshot from 2016-07-12 17:35:18.png

 

 

 

 

위 식에서 state-value function만 도식적으로 표현하자면 밑의 그림과 같습니다. 흰 점은 state를 나타내고 검은 점은 state에서 action을 선택한 상황을 의미합니다. r은 reward입니다. reward의 정의에 state와 action이 모두 조건으로 들어가기 때문에 그림에서 검은 점 밑에 표시된 것을 볼 수 있습니다. 간단히 표현하고자 그림에서는 가지를 2개씩만 쳤는데  이보다 더 많을 수도 적을 수도 있습니다. state에서 뻗어나가는 가지는 각 각의 action의 개수만큼입니다. 또한 action에서 퍼져나가는 가지는 만약 deterministic한 환경이라면 하나의 가지일 것이나 앞에서도 말했듯이 외부적인 요인에 의해서(바람이 분다던지) 같은 state에서 같은 action을 해줘도 다른  tate로 갈 수도 있습니다.

Screenshot from 2016-07-12 17:42:04.png

한 가지 상당히 헷갈릴수가 있는 것이 같은 Bellman Expectation equation이 expectation을 사용해서 표현될 수도 있고 위의 식처럼 summation을 사용해서 표현할 수도 있습니다. 앞선 글에서 강화학습은 environment의 model을 몰라도 학습할 수 있다고 했는데 강화학습에서 model은 위의 식에서 reward와 state transition probability입니다. 따라서 그 두 가지의  정보를 모르고 학습하는 강화학습에서는 Bellman equation으로는 구할 수가 없습니다. 하지만 model을 다 알고 학습하는 Planning에서는 다음 식을 가지고 학습할 수가 있습니다. 결국은 강화학습이 model을 다 알고 학습하는 Dynamic Programming이라는 알고리즘에 기반을 두고 발전했기 때문에 아래에서 DP(dynamic programming)을 설명할 것입니다.

 

다음 그림은 같은 내용을 action-value function의 입장에서 나타낸 것입니다.

Screenshot from 2016-07-12 17:51:33.png
 

 

 

강화학습의 목표를 다시 정의하자면, action-value function을 최대로 만들어주는 optimal policy를 찾는 것입니다. action-value function의 optimal한 값을 안다면 단순히 q값이 높은 action을 선택해주면 되므로 MDP가 풀렸다고 말할 수 있습니다. 그러면 어떻게 optimal한 action-value function의 값을 알 수 있을까요?

Screenshot from 2016-07-12 17:58:59.png

 

 

 


 

2. Dynamic Programming

 

  •  Policy Iteration

 

dynamic progamming은 environment의 model을 다 알고 문제를 푸는 planning입니다. 이후에 강화학습은 model을 다 모르기 때문에 sampling을 통해서 학습합니다.

 

위의 Bellman equation의 그림과 다른 점은 value function에 k라는 iteration숫자가 붙은 것입니다.

Screenshot from 2016-07-12 18:09:21.png

 

전체 MDP의 모든 state에 대해서 동시에 한 번씩 계산해서 update함으로서 k가 하나씩 올라가게 됩니다.

처음에는 agent는 아무 정보가 없기 때문에 random policy로 시작합니다. 그러한 policy에 대해서 위 같이 한 step씩 계산을 진행하면 무한한 시간이 흘렀을 경우 해당 policy에 대한 true value function을 얻을 수 있습니다. 이러한 과정을 Policy Evaluation이라고 합니다.

 

해당 policy에 대한 참 값을 얻었으면 이제 policy를 더 나은 policy로 update해줘야 합니다. 그래야 점점

optimal policy에 가까워질 것입니다. 그러한 과정을 Policy improvement라고 합니다. improve하는 방법

으로는 greedy improvement가 있습니다. 다음 식에서 보듯이 간단히 다음 state중에서 가장 높은 value function을 가진 state로 가는 것입니다. 즉, max를 취하는 것입니다.

 

Screenshot from 2016-07-12 18:19:44.png

 

 

 

이러한 두 과정을 합쳐서 Policy Itertion이라고 합니다. 다음과 같이 그림으로 나타낼 수 있습니다.

Screenshot from 2016-07-12 18:24:12.png

 

 

 

  •  Value Iteration

 

Value Iteration이 Policy Iteration과 다른 점은 Bellman Expectation Equation이 아니고 Bellman Optimality Equation을 사용한다는 것입니다. Bellman Optimality Equation은 할 수 있는 행동들의 action-value function의 최대값을 사용하여서 value-funciton을 update합니다.

Screenshot from 2016-07-12 23:39:10.png

 

이 equation을 사용하여 다음과 같이 update를 하는데 policy iteration처럼 중간 중간에 policy를 update하지않고 마지막에 구해진 optimal q-function의 값을 보고 greedy하게 policy를 정해버립니다. Policy Iteration때와 마찬가지로 Bellman optimality equation과 다른 점은 k라는 iteration숫자가 달리면서 한 스텝 한 스텝 업데이트를 한다는 것입니다.

Screenshot from 2016-07-12 23:44:00.png

 

 

 

이렇게 Dynamic Programming에 대해서 살펴보았습니다. 처음에 언급했다시피 DP는 MDP에 대한 정보를 다 가지고 있어야 optimal policy를 구할 수 있습니다. 하지만 MDP가 상당히 크거나 MDP에 대해서 다 알지 못할 때는 DP를 적용시킬 수 없고 대부분의 경우에는 이 경우에 해당합니다. 그렇다면 그러한 상황에 Learning을 하기 위해서는 어떻게 해야할까요?

 

이때 등장하는 개념이 sample back-up입니다. 즉, Sampling을 통해서 value function을 업데이트한다는 것입니다. 여러분이 바둑을 두고 있다고 가정해봅시다. 만약에 DP로 바둑이라는 문제를 풀려면 모든 수에 대해서 머리속에서 전부 계산한 다음에 다음 수를 두어야할 것입니다. 여러분도 이것이 불가능하다는 것을 알고 있습니다. 우리는 이럴 때 "한 번 가보자"라고 생각하고 한 번 해보고 그 결과를 바탕으로 학습하게 됩니다. Sampling 또한 마찬가지이고 이때부터 "강화학습"이 되는 것입니다.

 

Screenshot from 2016-07-12 23:50:20.png

 

 


 

3. Model-free Control

 

Modep-free라는 말 그대로 MDP의 model에 관계없이 optimal policy를 구하는 방법입니다. Control이라는 단어를 처음 접하셨을텐데 Policy Iteration에서  Policy Evaluation까지만 진행하면 Prediction이지만 Policy Improvement(예를 들면 Greedy improvement)까지 진행하면 Control이 됩니다. 발전이 있으면 Control이라고 생각하시면 됩니다. "맨날 혼나면서도 발전이 없는 아이는 Control하고 있지 않다"라고 이해하면 될까요?

 

Sampling을 통해서 Value function을 update하는 방법에는 다음 두 가지가 있습니다.

 

(1) Monte-Carlo Control

(2) Temporal Difference Control

 

 

 

  •  Monte-Carlo Control

 Monte-Carlo Control을 그림으로 나타내면 다음과 같습니다. DP를 알아야하는 이유가 다음과 같이 그 구조를 기반으로 강화학습이 발전했기 때문입니다.

 

Screenshot from 2016-07-13 00:06:43.png

 

여기서 두 가지를 알아야하는 포인트가 있습니다.

 

(1) Policy Iteration처럼 evaluation을 끝까지하지 않고 한 번의 episode로 인해 얻은 정보를 토대로 현재의 policy를 평가해줍니다.

 

(2) evaluation하고 대상이 state-value function이 아니고 action-value function입니다. model free control이 되려면 MDP의 model을 몰라도 할 수 있어야하는데 state-value function을 사용하면 greedy improvement할 때 model이 필요하기 때문입니다.

 

(2) Greedy policy improvement가 아니고 epsilon이 그 앞에 들어가는데 이유는 exploration문제에 있습니다. 진정한 답을 얻기위해서는 충분하게 경험해보는 것이 필요한데 그냥 greedy improvement할 경우에는 얻은 답이 optimal한 해답이라고 장담할 수 없기 때문에 일정한 모험의 요소를 추가한 것입니다. 정의는 다음과 같습니다.

Screenshot from 2016-07-13 00:13:01.png

하지만 MC는 episode가 꼭 끝이 있어야하고 online으로 학습하지 못한다는 단점이 있습니다. 따라서 그 대안이 될 수 있는 것이 online으로 한 스텝마다 update하는 Temporal Difference Learning이 있습니다.

 

 

 

  •  Temporal-Difference Control = SARSA

SARSA라고 표현하는 이유는 아래 그림과 같이 현재 state와 action, 그로인한 reward 그리고 다음 state와 action까지만 보고서 update가 이뤄지기 때문입니다.

Screenshot from 2016-07-13 00:19:37.png

위의 식은 강화학습을 할 때 가장 기억해야 할 식 중에 하나입니다. 현재 Q function의 값을 update하는 데 one step sample을 통해서 estimate된 값과의 error를 통해서 update합니다. 그 error를 TD error라고 부릅니다. alpha는 어떠한 비율로 update할 것인지에 대한 parameter입니다.

 

지금까지는 on-policy learning에 대해서 살펴보았습니다. 두 가지 on-policy control(MC and TD)에서 epsilon greedy하게 improve를 하는데 optimal한 값으로 가기 위해서는 epsilon이 0으로 수렴하는 구조여야합니다. 그렇게 되면 충분한 exploration을 보장할 수 없으므로 여기에서 off-policy learning이 등장합니다.

 

 


4. Q-Learning

off-policy learning이란 두 가지  policy를 동시에 사용할 경우를 말합니다. 즉, learning에 사용되는 policy는 greedy하기 improve를 하고 움직일 때는 현재의 Q function을 토대로 epsilon greedy하게 움직입니다. 식으로 표현하자면 다음과 같습니다.

Screenshot from 2016-07-13 00:38:14.png

식과 같이 다음 가능한 Q function중에서 최대를 뽑아서 현재 Q function을 update하고 움직일 때는 max값을 알면서도 가끔 다른 행동을 하게 됩니다. 알고리즘으로 표현하자면 다음과 같습니다.

 

Screenshot from 2016-07-13 00:42:39.png

 

 

이렇게 강화학습의 전반적인 개념에 대해서 살펴보았습니다. 앞으로의 과정은 위의 Q-Learning을 사용할 예정이고 다음 글에서부터는 본격적으로 OpenAI에 강화학습을 적용시켜보도록 하겠습니다.

 

번호 제목 글쓴이 날짜 조회 수
공지 강화학습 (Reinforcement Learning) 연구실 OpenRL 모임 안내 모두의연구소 2016.06.12 1300
22 softmax action result에 대한 reward 김상범 2017.10.31 255
21 강화학습 논문 웹사이트 모음 xelgana 2016.10.28 1548
20 Monte-Carlo Tree Search 코드 [3] file 이영무 2016.10.06 1866
19 2016. 9. 1. Asynchronous 발표 자료 [1] file 최한철 2016.09.10 412
18 2016. 9. 1. 발표자료 [3] 최한철 2016.08.29 532
17 Fundamental of Reinforcement Learning 링크 이웅원 2016.08.24 1093
16 2016.08.18 OpenRL 발표자료 file 이웅원 2016.08.17 758
15 강화학습 그리고 OpenAI - 4: CartPole with Policy Gradient (2) Code Review [5] file 이웅원 2016.07.20 5398
14 강화학습 그리고 OpenAI - 4: CartPole with Policy Gradient (1) Policy Gradient [9] file 이웅원 2016.07.15 10656
13 강화학습 그리고 OpenAI - 3: CartPole with Deep Q Learning (4) Code Review file 이웅원 2016.07.14 8419
12 강화학습 그리고 OpenAI - 3: CartPole with Deep Q Learning (3) TensorFlow 이웅원 2016.07.13 3886
11 강화학습 그리고 OpenAI - 3: CartPole with Deep Q Learning (2) DQN file 이웅원 2016.07.13 5946
10 강화학습 그리고 OpenAI - 3: CartPole with Deep Q Learning (1) CartPole example file 이웅원 2016.07.12 6602
9 DQN 발표자료 file 플룻 2016.07.11 966
» 강화학습 그리고 OpenAI - 2: Intro to Reinforcement Learning (2) Q Learning [4] file 이웅원 2016.07.08 16137
7 강화학습 그리고 OpenAI - 2: Intro to Reinforcement Learning (1) MDP &Value Function [2] file 이웅원 2016.07.04 17403
6 강화학습 그리고 OpenAI - 1: Introduction to OpenAI [3] file 이웅원 2016.07.01 20208
5 Reinforcement Learning by Sutton Chapter 5~16 file 마르코프김 2016.07.01 579
4 Reinforcement Learning by Sutton Chapter 1~4 [1] file 마르코프김 2016.06.30 2212