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

2016.07.15 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

 

 

 


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

 

 

http://karpathy.github.io/2016/05/31/rl/

 

 

 현재 강화학습에서 가장 "hot"하다고 볼 수 있는 방법이 Policy Gradient입니다. 강화학습의 기본 교재인 Sutton 교수님의 책에는 Policy Gradient가 몇 장 안나와 있어서 Silver교수님 RLcourse 7번째 Policy Gradient강의를 통해 그 개념을 접하고 이해하시는 것을 추천드립니다.

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

 

ammar14.png

 

http://icml.cc/2014/icml2014keywords/image/ammar14.png

 

 

알파고의 알고리즘도 "Policy Gradient with Monte-Carlo Tree Search"라고 합니다. 또한 실재 로봇이나 헬리콥터, 드론같은 적용에 적합한 방법이라고 합니다. 처음에 제가 강화학습에 관심을 가지게 된 계기도 드론의 자율주행이었기 때문에 Policy Gradient는 상당히 흥미롭게 다가왔습니다. 밑의 그림과 같이 적용되기도 합니다. Policy Gradient에도 여러가지 방법들이 있는데 나중에 다루도록 하겠습니다.

 

researchMultiTaskPolicyGradientControl.jpg

 

 

 

Policy Gradient에 대한 설명은 David Silver교수님의 강의를 바탕으로 작성하였으며 다음과 같은 순서로 진행됩니다.

Screenshot from 2016-07-15 11:48:15.png

 


 

1. Value-based Reinforcement Learning VS Policy-based Reinforcement Learning

지금까지 저희가 다루었던 방법들은 모두 "Value-based" 강화학습입니다. 즉, Q라는 action-value function에 초점을 맞추어서 Q function을 구하고 그것을 토대로 policy를 구하는 방식입니다. 이전에 했던 DQN또한 Value-based RL으로서 DNN을 이용해 Q-function을 approximate하고 policy는 그것을 통해 만들어졌습니다.

 

Screenshot from 2016-07-15 12:41:12.png

 

 

그와 달리 Policy-based RL은 Policy자체를 approximate해서 DNN에서 나오는 것이 value function이 아니고 policy자체가 나옵니다. Policy자체를 parametrise하는 것입니다.

 

Screenshot from 2016-07-15 12:43:29.png

 

왜 이렇게 할까요?? Policy Gradient의 장점과 단점은 다음과 같습니다. 기존의 방법의 비해서 수렴이 더 잘되며 가능한 action이 여러개이거나(high-dimension) action자체가 연속적인 경우에 효과적입니다. 즉, 실재의 로봇 control에 적합합니다. 또한 기존의 방법은 반드시 하나의 optimal한 action으로 수렴하는데 policy gradient에서는 stochastic한 policy를 배울 수 있습니다.(예를 들면 가위바위보)

 

하지만 local optimum에 빠질 수 있으며 policy의 evaluate하는 과정이 비효율적이고 variance가 높습니다.

Screenshot from 2016-07-15 12:51:45.png

 

 

 

 

기존 방법의 문제를 살펴보도록 하겠습니다. Value-based RL 방식에는 두가지 문제가 있습니다.

 

1. Unstable

Screenshot from 2016-07-15 12:43:43.png

 

Value-based RL에서는 Value function을 바탕으로 policy계산하므로 Value function이 약간만 달라져도 Policy자체는 왼쪽으로 가다가 오른쪽으로 간다던지하는 크게 변화합니다. 그러한 현상들이 전체적인 알고리즘의 수렴에 불안정성을 더해줍니다. 하지만 Policy자체가 함수화되버리면 학습을 하면서 조금씩 변하는 value function으로 인해서 policy또한 조금씩 변하게 되어서 안정적이고 부드럽게 수렴하게 됩니다.

 

 

2. Stochastic Policy

앞에서 언급했듯이 때로는 Stochastic Policy가 Optimal Policy일 수 있습니다. 가위바위보 게임은 동등하게 가위와 바위와 보를 1/3씩 내는 것이 Optimal한 Policy입니다. 또한 Partially Observed MDP의 경우에도(feature로만 관측이 가능할 경우) Stochastic Policy가 Optimal Policy가 될 수 있습니다.

Screenshot from 2016-07-15 12:57:41.png

 

 

 

 

 

2. Policy Objective Function

이제 기존의 방법처럼 Q function이 output으로 나오는 DNN을 만드는 것이 아니로 Policy가 output으로 나오는 DNN을 만들 것입니다. DNN을 update하려면 기준이 필요한 데 DQN에서는 그것이 loss function으로 target과 현재 Q function 값의 error의 제곱의 평균이었습니다. 하지만 Policy Gradient에서는 Objective Function이라는 것을 정의합니다. 그에는 세 가지 방법이 있습니다. state value, average value, average reward per time-step입니다. 게임에서는 보통 똑같은 state에서 시작하기 때문에 처음 시작 state의 value function이 강화학습이 최대로 하고자 하는 목표가 됩니다. 두 번째는 잘 사용하지 않고 세 번째는 각 time step마다 받는 reward들을 각 state에서 머무르는 비율(stationary distribution)을 곱한 expectation값을 사용합니다.

 

Screenshot from 2016-07-15 13:03:04.png

 

Stationary distribution은 처음 접하는 개념일겁니다. sutton교수님의 policy gradient논문에서는 stationary distribution을 다음과 같이 정의하고 있습니다.

https://webdocs.cs.ualberta.ca/~sutton/papers/SMSM-NIPS99.pdf

Screenshot from 2016-07-15 13:09:06.png

 

 

개인적으로는 위에서 언급했다시피 각 state에 머무르는 비율로 이해하고 있습니다. 어떻게 구현하는 지가 중요할 텐데 다음 Code Review 글에서 Karpathy가 어떻게 구현했는지를 살펴보면서 이해를 하면 좋을 것 같습니다.

 

Policy Gradient에서 목표는 이 Objective Function을 최대화시키는 Theta라는 Policy의 Parameter Vector을 찾아내는 것입니다. 그렇다면 어떻게 찾아낼까요? 바로 Gradient Descent입니다. 그래서 Policy Gradient라고 불리는 것입니다. 다음에서는 Objective Function의 Gradient를 어떻게 구하는 지에 대해서 보겠습니다.

Screenshot from 2016-07-15 13:16:07.png

 


Objective Function의 Gradient를 구하는 방법이 핵심인데 세 가지 방법이 있습니다.

Finite Difference Policy Gradient / Monte-Carlo Policy Gradient / Actor-Critic Policy Gradient

 

4. Finite Difference Policy Gradient

 

이 방법은 수치적인 방법으로서 Parameter vector가 5개의 dimention로 이루어져 있으면 하나 하나 흔들어보면서 그 Gradient를 구하는 것입니다. 간단하지만 비효율적이고 노이지한 방법입니다. policy가 미분가능하지 않더라도 작동한다는 장점이 있습니다.

Screenshot from 2016-07-15 13:18:51.png

 

5. Monte-Carlo Policy Gradient

 

analytic하게 gradient를 계산하는 방법으로서 위에서 objective function에 직접 gradient를 취해줍니다. 이때, Policy는 미분가능하다고 가정합니다. 밑에서 보면 score function이라는 것이 나옵니다. score function이란 무엇일까요?

Screenshot from 2016-07-15 13:27:53.png

 

(1) Score Function

Objective function에 직접 gradient를 취하면 다음과 같습니다.

Screenshot from 2016-07-15 13:31:58.png

log가 갑자기 나오는 이유는 다음과 같습니다. 로그의 미분과 관련이 있는 것입니다.

Screenshot from 2016-07-15 13:33:58.png

따라서 이 policy에 log를 취한 형태가 score function이 됩니다. 결국 objective function의 gradient는 다음과 같습니다.

Screenshot from 2016-07-15 13:31:58.png

 

(2) Policy Gradient Theorem

r이란 immediate reward를 의미합니다. 하지만 즉각적인 reward말고 Q function을 사용할 수 있다는 것이 Policy Gradient Theorem입니다. 마지막 식을 보면 r대신에 Q function이 들어간 것을 볼 수 있습니다. 한 순간 순간의 reward를 보는 것이 아니라 지금까지 강화학습이 그래왔듯이 long-term value를 보겠다는 것입니다. 이 Theorem은 위에서 소개한 sutton교수님의 논문에 증명되어있습니다.

Screenshot from 2016-07-15 13:38:26.png

 

위의 gradient를 통해서 policy의 DNN을 업데이트할 것입니다. 하지만 DNN을 설계함에 있어서 output인 policy의 형태를 지정해줘야합니다. 정확히 말하자면 지금 하는 강화학습은 Stochastic Policy Gradient로서 policy자체가 stochastic합니다. 그러한 policy를 표현하는 방법으로서 다음 두 가지가 있습니다. 어떤 것을 사용할 지는 설계자의 몫입니다.

 

Screenshot from 2016-07-15 13:43:09.png

 


6. Actor-Critic Policy Gradient

이제 조금 더 생각해봅시다. 사실 위에서 Q function의 값을 어떻게 구하지?라고 생각하신 분들도 계실겁니다. 이름이 Monte-Carlo이듯이 episode가 끝나면 해당 Policy에 대해 Q function을 구할 수가 있습니다.

다음과 같은 알고리즘입니다.

Screenshot from 2016-07-15 13:48:13.png

 

Return을 사용하기 때문에 Monte-Carlo 고유의 문제인 high variance의 문제가 있습니다. 또한 episode자체가 길수도 있기 때문에 다음과 같은 아이디어를 낼 수 있을 것 입니다. "neural network를 두 개 만들어서 Q function도 approximate해서 gradient를 구하자!" 이것이 바로 Actor-Critic Policy Gradient입니다.

 

 

(1) Actor & Critic

다음과 같이 Critic은 Q function을 approximate하고 Actor는 policy를 approximate합니다. 따라서 w와 theta라는 두 개의 weight parameter를 사용해야합니다.

Screenshot from 2016-07-15 13:49:24.png

이 Critic은 Q function을 통해 현재의 Policy를 평가하는 역할을 합니다. 그래서 Critic이라는 이름이 붙었습니다. Policy evaluation은 앞의 DP에서 나온 개념으로서 세 가지 방법으로 가능합니다. 이 또한 사용하기 나름인데 코드에서 확인하는 것이 나을 것 같습니다.

 

Screenshot from 2016-07-15 13:52:26.png

 

 

(2) Baseline

여기까지 기본적인 Policy Gradient의 개념에 대해서 살펴보았는데 Actor Critic말고 다르게 Variance문제를 해결하는 것이 Baseline입니다. Q function이후로 사용하고 있지 않던 State value function을 일종의 평균으로 사용해서 현재의 행동이 평균적으로 얻을 수 있는 value보다 얼마나 더 좋나라는 것을 계산하도록 해서 variance를 줄이는 것입니다.

Screenshot from 2016-07-15 13:58:00.png

 

 

(3) Off-Policy Actor-Critic

Learning문제에서 Exploration의 이슈는 피해갈 수 없습니다. Policy Gradient도 마찬가지라서 Q learning처럼 Off-Policy를 사용함으로서 그 문제를 해결할 수 있습니다. David Silver교수님의 Deterministic Policy Gradient논문에 나와있습니다. 이해가 되지 않더라도 이런 것이 있다라고 알고 있으면 나중에 다시 볼 수 있을 겁니다.

http://jmlr.org/proceedings/papers/v32/silver14.pdf

Screenshot from 2016-07-15 14:11:59.png

 


여기까지 Policy Gradient의 개념에 대해서 살펴보았습니다. 현재 Policy Gradient가 추세인 만큼 이 개념에 대해서 이해하는 것이 중요할 것입니다. 여기서 이해가 잘 안되더라도 다음 글에서 Karpathy의 Code를 살펴보면서 이해하셔도 됩니다.

번호 제목 글쓴이 날짜 조회 수
공지 강화학습 (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 5399
» 강화학습 그리고 OpenAI - 4: CartPole with Policy Gradient (1) Policy Gradient [9] file 이웅원 2016.07.15 10661
13 강화학습 그리고 OpenAI - 3: CartPole with Deep Q Learning (4) Code Review file 이웅원 2016.07.14 8420
12 강화학습 그리고 OpenAI - 3: CartPole with Deep Q Learning (3) TensorFlow 이웅원 2016.07.13 3887
11 강화학습 그리고 OpenAI - 3: CartPole with Deep Q Learning (2) DQN file 이웅원 2016.07.13 5947
10 강화학습 그리고 OpenAI - 3: CartPole with Deep Q Learning (1) CartPole example file 이웅원 2016.07.12 6604
9 DQN 발표자료 file 플룻 2016.07.11 966
8 강화학습 그리고 OpenAI - 2: Intro to Reinforcement Learning (2) Q Learning [4] file 이웅원 2016.07.08 16143
7 강화학습 그리고 OpenAI - 2: Intro to Reinforcement Learning (1) MDP &Value Function [2] file 이웅원 2016.07.04 17414
6 강화학습 그리고 OpenAI - 1: Introduction to OpenAI [3] file 이웅원 2016.07.01 20211
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