Reinforcement Learning

논문 최종본 수정도 마치고, 공부하기도 싫고해서 미뤄왔던 강화 학습 (Reinforcement Learning)에 대한 포스팅을 해보겠다. 먼저 RL에 대한 대략적인 개념을 집고 넘어가는 것이 중요하겠다. 단순하게 생각하자면 인간이나 동물의 학습을 모방했다고 볼 수 있다. 즉 어떤 행동을 했을 때 좋은 Feedback을 받을 경우 그 행동을 더 강화하고, 나쁜 Feedback을 받을 경우 해당 행동을 하지 않는 것이다. 쉽게 예를 들자면 자전거를 타는 동작을 생각할 수 있겠다. 이 경우 Feedback은 넘어지지 않고 앞으로 가는 여부가 되겠다. 

하지만 우리는 이러한 개념을 "구현"해야 한다. "구현"의 다른 의미는 수학적 모델로 표현함과 같다. 존 폰 노인만의 다음 quote가 이를 설명하는데 적합할 것 같다. 

"If you tell me precisely what it is a machine cannot do, then I can always make a machine which will do just that." 

 - John von Veumann

바꿔 말하면, 무엇을 정확하게 구현하기 위해서는 이를 명확하게 표현할 수 있어야 한다는 의미를 갖는다. 그리고 수학적 모델을 무엇을 정확하게 표현할 수 있는 몇 안되는 모델 중 하나이다. (수학은 Lemma로부터 시작되어서 쌓여올려진 거대한 성과 같다.)

모 여튼 다시 우리의 강화 학습으로 돌아오면, 강화 학습은 고전 제어 방법론 중 하나인 Markov Decision Process (MDP)라는 수학적 모델 위에 세워져 있다. 이 MDP는 연속적인 상황에서 특정 행동을 결정할 수 있게 해주는 수학적 모델이다. 조금 더 구체적으로 들어가보자면, 다음 5개의 묶음으로 현재 상태를 표현한다. (경우에 따라 더 많기도 한 것 같다.)

1. State : 현재 상태 

2. Action : 현재 상태에서 하고 있는 행동 

3. Reward : 현재 행동을 통해 얻은 Feedback 

4. Policy : 어떤 상태에서 어떤 행동을 할지를 정해주는 함수 

5. Transition Probability (or Dynamic model) : 어떤 상태에서 어떤 행동을 했을 때 다른 상태들로 넘어갈 확률

갑자기 어려워졌다. 왜 이런 것들이 강화 학습과 관련있는지 이해가 안되는 것이 당연하다. 그럼 일단 예를 들어서 생각해보자. 앞에서 우리가 봤던 자전거를 타는 경우를 살펴보자. 음.. 사실 이는 적합하지 않을지도 모르겠다. 기본적으로 MDP는 Discrete한 문제에 적용이 되기 때문이다. 무슨 말이냐면 상태나 행동이 한정된 경우의 수 안에서 표현되야 한다는 의미이다. 다음의 간단한 예를 살펴보자. 

(아래 문제에 대한 solution: http://enginius.tistory.com/361)

위와 같은 미로가 있다고 하자. 목표는 S (Start position)에서 G (Goal position)까지 "최대한 빨리" 가는 것이다. 그렇다면 이 문제를 어떻게 풀면 될까? 위의 문제를 RL로 풀기 위해선 일단 위의 환경을 MDP로 표현해야 한다. 

1. State :  미로의 각 위치 (네모)

2. Action : 행동 (상하좌우)

3. Reward : Goal에 도착하면 +10 / 한번 이동시마다 -1

4. Policy : 어떤 행동에서 각 행동을 할 확률들 

5. Transition : 어떤 행동을 했을 때 다음 특정 state로 갈 확률 

위와 같이 미로 찾기 문제를 MDP로 나타내게 된다면, 우리가 얻고 싶은 policy는 각 위치에서 어느 방향으로 움직일지에 해당한다. 그리고 어느 방향으로 움직일지를 정하는 기준은 해당 방향으로 움직였을 때 기대할 수 있는 Reward의 합이 최대로 되게 하는 것이다. 그렇다면 Reward는 어떻게 주어지는가? 이 부분이 중요하다. 

강화 학습에서 가장 중요한 것을 Reward function을 적절하게 설정하는 것이다.

위의 문제에서 Reward는 Goal에 도착했을 때 +10, 그 외 이동할 때 마다 -1을 설정한다. 이게 무슨 의미냐 하면, Goal에 도착하면 큰 값을 줘서 해당 Goal로 이동하는 행동을 하게 하는 것이고, 그외 이동에 대해서 -1씩 주기 때문에 최소한의 경로로 Goal까지 가길 원한다는 것이다. 

 그렇다면, 뛰어난 독자들은 의구심이 생길 것이다. Goal에 도착하는 행동은 시작점 S에서 상당히 많은 이동을 한 후 일텐데, 어떻게 모든 위치에 대해서 적절한 행동을 설정할 수 있을까? 바로 이 점이 Reinforcement Learning의 큰 강점 중 하나이다. 위해서 언급 했듯이 RL으 policy는 expected reward를 최대로 하기 때문에 이론상 모든 점에서 원하는 행동을 할 수 있게 한다. 

 답을 먼저 보자. 다음의 동영상은 RL을 통해서 MDP를 푸는 것을 동영상으로 나타낸 것이다. 

다음 팟에 올려서 광고가 많이 뜨는 것을 이해해주세요.. 

위의 그림에서 색은 해당 위치에서 Value를 의미한다. 간단히 생각해서 Reward의 sum이라고 생각하면된다. 해당 위치에서 예상되는 Reward의 sum으로 Value가 높은 쪽으로 이동하면 된다. 

직관적으로 색의 변화만을 보면 처음에는 Goal 주변에서만 색의 변화가 생긴다. 이는 사실 당연한 것이 Goal에 도착할 때만 +10의 Reward를 주기로 했기 때문이다. 하지만 한번 Goal 주변의 변화가 생기면 그 변화가 점점 뒤로 전파된다. (Back propagation과는 비슷다름하다..) 그래서 결국엔 우리의 시작 지점인 S까지 색의 변화가 전파되고, 변화되는 정도가 일정 수준 이하로 떨어지면 학습을 멈춘다. 

위의 그림에서 화살표가 해당 state에서 policy 즉 이동 방향을 의미하고, 대충 잘 따라가보면 모든 방향에서 Goal까지 가는 것을 알 수 있다. 다시 말하면 위의 문제를 RL을 통해서 푼 것이다. 

여기까지가 가장 기본적인 RL에 대한 설명이다. 물론 여기까지 알아선 문제를 풀기엔 부족하다. 이제부턴 복잡한 수학적 얘기를 해보겠다. 직관이 많이 들어갈 것이고, 틀리 수 있다는 것을 미리 말하고 넘어가겠다. 

1) Discounted Return 

Return은 reward와 비슷한 개념이다. Reward의 정확한 개념은 어떤 state에서 어떤 행동을 했을 때 어떤 state로 넘어간다고 했을 때, 해당 경우에 주어지는 값이다. 이가 명확히 정의 되기 위해선 R(s, a, a')으로 정의된다. s와 s'은 이전과 다음 state, a는 action을 의미한다. 즉 이 함수가 정의되는 공간은 state space^2*action space로 매우 크다. 이를 다 정의하는 것은 어려우므로 간단히 특정 state에 도달했을 때 reward와 비슷한 개념으로 return을 준다. 

 이 경우에 Discounted Return은 다음과 같이 정의된다.  

$$ R_t = r_{t+1} + \gamma r_{t+2}+ \gamma^2 r_{t+3} $$

 즉 현재 들어오는 return이 나중에 들어오는 return에 비해서 '$\gamma$' 라는 factor 만큼 더 중요한 것을 의미한다. 

2) Markov Property

확률에서 Markov propertiy는 현재가 주어졌을 때 과거와 미래에 대한 conditional independency를 의미한다. 이를 수학적으로 풀어보면 다음과 같다. 

$$ P(s_{t+1} = s', r_{t+1} = r | s_t, a_t, r_t, s_{t+1}, a_{t+1}, r_{t+1}) = P(s_{t+1} = s', r_{t+1} = r | s_t, a_t, r_t) $$

쉽게 생각하면 내일의 확률은 오늘에만 dependent하다는 것이다. 

대학원 확률 수업 때 교수님이 하셨던 말이 생각난다. 

"세상이 Markovian이라면 얼마나 좋을까요. 시험 성적이 전날 공부에만 Dependent할테니까요."

앞에서 언급한 MDP에서 M이 Markov를 의미한다. 결국 MDP에서 우리가 어떤 행동을 했을 때 다음 상태는 이전 상태와 현재 행동에만 상관있다는 의미이다. 

3) Bellman Equation

이 Bellman Equation이 RL혹은 MDP의 근간이 되는 수식이다. 이 수식은 Bellman optimality condition을 이용한다. 

Principle of Optimality: An optimal policy has the property that whatever the initial state and initial decision are, the remaining decisions must constitute an optimal policy with regard to the state resulting from the first decision.

사실 위의 문장은 선문답 같은 느낌이 있다. 쉽게 설명하면 다음과 같다. 최적의 행동을 위해 행동을 결정할 때 그 종료 시점까지의 모든 결정이 반영되야 한다. 음.. 내가 봐도 무슨 말인지 모르겠다. Vague한 예를 들자면 행복을 cost function이라고 할 때, 행복한 삶을 위해선 평생 열심히 선택해야 한다는 것이다. 좋은 부모를 만나고, 좋은 대학을 들어가고, 좋은 배우자를 만나고, 좋은 회사에 들어가고, 아이를 잘 키우고, 이 모든 선택들이 우리의 최적의 행복한 삶에 영향을 미친다는 의미이다. 

Bellman equation은 다음과 같다. (http://en.wikipedia.org/wiki/Bellman_equation)

여기선 x가 state를 의미하는데 어떤 state마다 value라는 값이 지정된다. 그리고 모든 행동은 해당 state 에서 갈 수 있는 state 중에서 value가 높아지는 쪽으로 정하면 된다. 간단하다!

4) TD Learning과 Q Learning 

여기부터가 실제적인 Reinforcement Learning이다. (내 생각엔) 

위에서 언급한 Bellman Equation을 이용한 방법의 문제가 무엇일까? 

위까지 의도적으로 별로 언급하지 않은 문자가 있다. 바로 T이다. 이는 Transition probability라고 한다. 즉 Markov property에 대해서 현재 상태에서 어떤 행동을 했을 때 다음 가능한 행동들로 갈 수 있는 확률을 의미한다. 하지만 이 T를 구하기 위해선 앞에서 잠깐 언급한 Return과 같이 굉장히 넓은 공간 속에서 정의되어야만 한다. 더욱이 이 값이 아예 정의가 안될 수도 있다. 

예를 들어서 우리에게 다관절 뱀 모양 로봇이 주어졌다고 하자. 

우리의 목적이 다음 로봇을 앞으로 이동시키는 것이라고 하자. 그렇다면 이 경우에 state는 각 관절의 모터의 각도에 대한 Cartesian product space일 것이다. 쉽게 생각해서 각도가 180도 이동 가능하고, 우리가 10도 단위로 discretize했다면 한 관절당 18개의 값을 가질 수 있고, 10개의 모터가 있다면 가능한 경우의 수는 18^10으로 매우 크다. 즉 18^10이 우리가 가지고 있는 state space이고, T가 정의되기 위해선 최소 18^20의 공간에서 정의가 되야 한다. 말도 안된다. 

이를 해결하기 위해서 우리에게 필요한 것은 T를 수식에서 없에는 것이다. T의미가 무엇인가? 즉 어떤 state에서 어떤 행동을 했을 때 다른 state로 넘어가는 확률이다. 우리가 얻고 싶은 것은 무엇인가? 정해진 reward를 최대로 하는 policy를 찾는 것이다. 결국 T는 reward를 구하는 과정 중간에 필요한 변수이다. 그럼 이를 돌아갈 수 있을까? 그렇다!

Q learning을 보자. (http://en.wikipedia.org/wiki/Q-learning)

위 식이 가지는 의미를 알기 위해선 두 가지를 보면 된다. 하는 Q라는 함수의 input으로 state와 actino이 있다는 것이고, 다른 하나는 Transition probabiltiy가 식에 포함되지 않았다는 것이다. 직관적으로 설명하자면 Transition probabiltiy는 결국 어떤 상태에서 어떤 행동을 했을 때 어떤 상태로 갈 지를 의미하고 때문에 이를 경험을 통해 구하고, 그 식을 내부로 포함시킨 것이다. 결국 우리는 어떤 상태에서 특정 행동을 하고 다른 상태로 넘어가고, 이 반복만 하면 되는 것이다. 또한 이전에는 행동을 정할 때 각 state에 다한 value를 다 구하고, 행동을 구하고, 다시 바뀐 행동에 따른 value를 구하고를 반복했다면, 이번엔 Q라는 함수 내부에 state와 action을 모두 가지고 있기 때문에 이 과정이 한번에 이뤄진다. 

5) Exploration and Exploitation 

 우리가 풀고자 하는 문제가 커졌다고 치자. 이 경우엔 모든 가능한 state, 모든 가능한 행동을 할 수가 없다. 게다가 TD나 Q Learning을 할 때는 우리가 한 행동이 직접적으로 학습에 영향을 미치고, 우리가 하지 않은 행동은 학습될 수 없다. 이러한 경우엔 약간의 Heuristics를 섞어야 하고 이것이 바로 Exploration and Exploitation 이다. 

 

 말은 어렵지만 개념은 간단하다. 일정 확률로 우리가 현재까지 구한 최적의 행동을 하고, 1-확률로 완전 random한 행동을 하는 것을 의미한다 . 그리고 이 확률을 보통 '$\epsilon$'으로 표현하고, '$\epsilon$'-greedy learning이라고 쓴다. 즉 일정 확률로 우리가 지금 좋다고 생각하는 행동을 점점 좋게 만들고, 또 나머지 확률로는 새로운 좋은 행동이 없나 찾아보는 것을 의미한다. 

---

개인적으로 생각하는 최고의 강의