강화학습 학습하기 - [4]MC

[4] Monte Carlo method

"강화학습 학습하기"시리즈는 KAIST 신하용 교수님의 수업 IE540 "DP and RL"수업 내용을 제가 제 방식대로 요약 및 정리한 것입니다. 퍼가실때는 미리 물어봐주시고, 내용은 제가 변형하고 추가하되 렉쳐노트에 쓰인 그림은 사용해도 된다고 교수님께 허락 받았습니다. 

0. Previously on..

저번 편에서 드디어 동적계획법과 강화학습의 연결고리를 찾았다. 모델이 알려져있을 때는 동적계획법으로 풀면 되지만(Value iteration, policy iteration), 모델을 알지 못 할때는 강화학습으로 풀면 된다. 이땐 모델을 추정하기 보단, 상호작용할 수 있는 샘플을 이용해서 최대의 보상을 얻을 수 있는 정책을 결정하면 된다. 강화학습에는 두 가지 방향이 있다. 값을 기반으로 하는 value based RL, 그리고 구하고자하는 정책 그자체를 이용한 강화학습 이렇게 두 가지이고, 두 가지 모두의 장단점과 종류를 "강화학습 학습하기"에서 알려주고한다. 

강화학습의 종류 : Value based, policy based

1. Monte Carlo Simulation(Method)

강화학습 중 가장 간단하고 이해하기 쉬운 MC, 몬테카를로 방법에 대해서 이번 편에 알아보자. 일단 몬테카를로는 모나코의 행정구 중에 하나로 카지노가 유명한 곳이다. 카지노 처럼 무작위성을 고려해야한다고 카지노로 유명한 도시 이름을 따온 것이다. 우리나라로 치면 강원 method였을지도 모르겠다. 어쨌든 몬테카를로 방법은 강화학습 뿐만 아니라, 어떤 모델을 알기 어려울때, 특성을 알아볼때도 유명하다. 엔리코 페르미가 중성자의 특성을 연구하기 위해 MC 방법을 사용한 것으로도 유명하다. 예를 들어, 사분원의 넓이를 이용해 pi값을 알고 싶다면, 1*1 정사각형에 계속 다트를 던진다. 이때 맞는 곳은 무작위라고 가정한다면, 전체 다트 수에서 사분원의 안에 들어간 다트수가 1과 사분의 PI의 관계가 된다.  MC 방법은 MC simulation이라고도 하는데, 계속 시뮬레이션을 통해서 값을 추정해가는 과정이다. 

Monte Carlo simulation.

이렇게 몬테카를로 시뮬레이션을 하다보면, 바로 문제가 생길 것이다. 만약에 샘플이 2차원에 퍼져있지 않고 높은 차원에 퍼져있다면 문제가 생긴다. 그리고 만약 다트를 표적에 던지는데, 바람이 불어서 엉뚱한 곳들에 박힌다고 생각해보자. 단순히 결과만 가지고 바로 분석하기에는 문제가 있을 것이다. 그리고 만약 샘플 숫자가 적다면 결과를 통해서 적절한 결론을 만들어낼 수 있을까? 몬테 카를로 방법은 샘플이 아주 많고, 낮은 차원에서 그리고 우리가 샘플링의 확률 분포를 알고 있어야지 적용가능하다. 

2. Incremental average. 

Incremental average

Incremental average가 있다. 이는 주어진 데이터에서 평균을 뽑아낼 때, 점화식처럼 n-1의 평균과 n의 평균의 관계를 나타낼 수 있는 값이다. 일반적으로 1/n이 붙으면 산술평균, 알파 n이 붙으면 일반화된 식인데, 알파 n의 값에 따라서 평균값이 수렴할 수도 있고 안될 수도 있다. 

Generalized incremental average. 알파 n은 step size라고도 한다. 

Data n개의 평균은 data n-1개의 평균에다가 알파 n 곱하기 새로운 샘플에서 이전 n-1개의 평균을 뺀 값이 된다. 이는 새로운 평균을 계산할때 새로운 데이터의 영향을 얼마나 고려하냐는 것으로 바꿔 말할 수 있다. 영어로는 "surprise of new data"라고 한다. 아마 온고지신이란 사자성어처럼 이전 것은 잘 받아들이면서 새로운 것도 적용하는 것이다. 

3. Robbins-Monro condition on step size

Step size 알파 n은 두 가지 조건을 만족해야한다. 알파 n의 무한급수가 발산해야하고, 알파 n의 제곱의 무한급수는 수렴해야한다. 이는 첫번째 조건의 의미하는 바는 알파 n의 무한급수가 발산해야 너무 빨리 decrease하는 것을 막고, 알파 n의 제곱의 무한급수가 수렴해야 충분히 탐색(반영)한 후에 수렴한다는 것이다. 이를 로빈슨 몬로 컨디션이라고 하고 사실 강화학습 뿐만 아니라 여러가지 분야에 적용된다. 만약 step size가 상수라면 알파 n의 제곱의 무한급수가 발산하여 RM 조건을 어기게 되고, 만약 step size가 e^(-n)인 exponential form이라면 알파 n의 무한급수가 수렴하여 너무 빨리 수렴하게 된다. 앞으로 강화학습에서 나오는 내용이 여기서 반복된다. 처음에 exploitation과 exploration의 딜레마가 있었다. 너무 빨리 수렴해서도 너무 많이 탐색하여 발산해서도 안되는데 이러한 trade-off가 강화학습이라는 분야에 전반적으로 깔려있다. 

로빈슨 먼로 컨디션 (RM 컨디션)

step size가 n^(-p)일 때의 RM 조건. p가 1보다 작거나 같고 1/2보다는 커야한다. 

4. Monte Carlo policy evaluation(Prediction)

이제 알아야할 것들은 다 알았으니 Value based RL의 첫 번째 방법인 몬테카를로 방법을 알아보자. 강화학습을 해야하는 상황부터는 일반적으로 state transition probability와 reward model을 모른다. 그래서 우린 DP를 사용할 수 없다. sample trajectory를 통해서 state에 대한 value를 알아보고, 이를 이용해서 policy를 결정하고 다시 sample traejectory를 구할 것이다. 

MC method.

종결 state의 reward 값은 0으로 하고(기준을 잡기 위해서), state를 건너갈 때마다 받는 reward를 discounted하여 total discounted reward인 return을 계산한다. 이 return값은 sample trajectory마다 바뀐다. State value라는 것은 state가 s일 때의 return의 기댓값이 된다. 

MC method의 return.

밑에 있는 알고리즘은 더 직관적으로 MC method가 어떻게 작동하는지 보여준다. 이때 every visit, first visit이라는 용어가 나오지만 나중에 설명할 것이다. 첫 번째로 모든 상태 값은 0으로 초기화하고, sample trajectory를 만든다. 이를 에피소드라고 한다. 에피소드를 구하고 이에 따른 return값을 계산하고 이 return값으로 기존에 구해진 stae value값을 incremental average( "surprise of new data"를 고려)한다. 

MC policy evaluation의 알고리즘

미리 언급했던 first visit, every visit은 간단하다. 한 episode에서 같은 state를 여러 번 지날 수도 있다. 이때 그 상태를 지나갈 때마다 값을 업데이트하냐 아니면 한번 지나갔으면 다음 번에 지나갈때는 업데이트를 안 하는 것이냐 하는 차이다. every visit이 더 직관적으로 정확해보이지만 둘 다 괜찮다. 문제 상황에 따라서 다른게 적용할 수 있고, 만약 같은 문제를 누군가는 every visit, 다른 이는 first visit으로 적용한다면 값을 당연히 다를 것이다. 

 그리고 추가적인 언급으로는 MC는 episode를 생성하고 이에 속한 state만 update를 하기 때문에 모든 state에 대해서 update가 일어난다고는 할 수 없다. 그리고 MC에 대한 가장 중요한 성질을 설명하려고 한다. 바로 편향성(bias), variance이다. 편향성은 평균치가 치우쳐져있는 것이고, variance는 평균치로부터 얼마나 값이 떨어져있냐이다. 

MC method의 Bias와 variance.

MC method의 value 값은 return 값을 사용해서 update하기 때문에 bias가 없다. 그리고 하나의 episode로 return을 정하는 MC은 episode에 highly dependent하기 때문에 variance가 크다. 

5. Monte Carlo Control

Control을 위해서는 정책(policy) pi가 필요하다. 

DP에서는 Q값을 V값에서 model을 사용해서 계산할 수 있지만, model이 없을 경우에는 Q값은 episode를 이용해서 구해야한다. 

MC control의 장점은 쉽고, 병렬화 적용하기 쉽다. 그리고 full models(model을 모르고 environment에 대한 interaction으로 배운다), full states(episode로 거쳐가는 states만 필요하다)를 알 필요가 없기 때문에 강력하다. 그리고 Bellman equation을 사용하지 않기 때문에 MDP의 성질인 memoryless property를 어겨도 적용가능하다. 

참고1. GLIE policy

GLIE policy. Greedy in the limit, infinitely exploration.

무한히 탐사하면서 최대한 best인 것을 취하는 policy를 통해서 MC control을 진행한다. 

참고2. MC method의 단점

MC method의 단점은 high variance이다. High variance때문에 장점들에도 불구하고 사실상 impractical하다. 이 impractical한 면이 다음편인 TD methods에 대한 motivation이다.