5. Monte Carlo method (MC method)

컴공에서 MC 라고하면 그냥 모든경우수 다따져서 탐색하는 방법으로 알려져있다.

역시 Reinforcement learning 에서는 다른 용어로 쓰인다.

왜 애매한 용어를 가져다 써서 혼선을 주는 지는 모르겠지만. 역시 내가모르는 이유가 있겠지..

 

아무튼 내가 읽어본 MC method 는 상당히 강력한것 같다.

그 뜻은 일단 일반적인 문제에 적용할 수 있을 만큼 구현이 쉬운 부분에 있어서다

수렴은 앞에 MDP 와 유사할 것 같다.

 

기존 알고리즘 중 DFS 와 유사하다고 생각이 들었다. 

 

본질적으로 MC method 역시 v* 또는 q* 를 찾기 위해서 평가와 향상이 이루어지는건 마찬가지인데,

MC method는 한개의 정책에 대해서 끝까지 수행 한 후 그 보상을 가지고 value function 을 update 치면 된다.

일반적으로 4장의 DP 의 경우 v_pi 값을 모두 가지고있어야 update 되는 반면에, 

MC method 는 1개의 시나리오에 대해서 해당 state 들만 update 되면 된다.

 

이렇게 하면 굳이 state 간의 관계전이 확률인 p 도 필요없어지고, Value 를 갱신 할 수 있게 된다.

다만 이렇게 하면 에피소드에 소외된 state들이 생기게 될 수 밖에 없는데, 이런 state 들을 위해서 

  시작탐험을 가정하는데, e = epsilon 을 주어서 낮은확률로 일종의 탐험하지 않은  state 를 pi-Episode 에 없는 강제로 탐험하도록 만드는것이다.

 

두번째 문재점으로서는 수렴성의 문제인데, 무한히 에피소드에 대해서 수행해야 수렴을 가정할 수 있다,

 

이말 인 즉슨, 무한히 많은 에피소드를 가정하라 수만 있다면 이 부분은 매단계 마다 qpi 를 충분하 평가과정을 거치면 각각 qpi 로 수렴하다고 볼수 있다.

다만 이 방법은 시간이 너무 많이 소요된다. 그래서 

첫번째로는 qpi 를 근사하는 방식(벨만 - DP 방식 ) 을 사용하는 것이고

두번째로는 정확한 qpi 를 구하지 않고 향상과 평가를 반복하는 것이다.

1평가-1향상으로서는 가치반복이 유명한데, 더 극단적으로 상태 마다 반복시킬 수도 있다.

 

몬테카를로 의 경우 1평가 -1 향상이 에피소드마다 이루어지는게 자연스럽다.

그래서 완성된것이 아래의 의사코드

 

그리고 epsilon 을 통한 의사코드는 아래와 같다.

이와 같은데, e-mc method도 어느정도 수렴성을 보장 할 수 있다.

 

 

 

 

그리고 우리가 구하고자 하는 정책에 대한 data 가 많지 않다고 가정해보자

data 다른 정책 b 에 있어서 데이타가 많을경우 

정책 b의 data 를 반복적으로 학습(?) 시켜서 pi 에 대한 정책의 vpi 값도 구할 수 있다.

이 기법을 Importance Sampling 이라고 하며, off-policy Prediction 이라고 하기도 한다.

 

 

그때의 의사코드는 아래와 같다.

여기서 Repeat 에서 만들어진 뮤는, 우리가 구하고자 하는 정책이아닌 표본 정책 b 라고 보면된다.

여기서 구하고자하는 pi 애 대한 가치함수는 Q 이며 C는 계산을 돕기위한 값이라고 생각 할 수 있다.

또한 W 는 Weighted importance Sampling 을 하기위한 값 인데 , 매번 계산을 해준다는 것이 특징적이다.

 

이때 이 의사코드가 성립하기 위해서는 b 가 소프트 정책이고, coverage 하여야하는데, 

소프트정책이란 모든 정책/Action을 0이 아닌 확률로 탐험 할 수 있는 정책 이여야 하고,

Coverage 하다는 뜻은 파이의 주요 정책에 실행될 action 이 b 의 정책에 실행될 action 에 포함되는 상태

즉, pi(a|s) >0 incurs b(a|s) > 0 이여야 한다.

소프트정책이면 Coverage 하다.

 

어쨋든 e-mc method 는 임의로 탐험하도록 강제적으로 만드는 것이라면

off-policy method 의 경우 더 좋은 표본 에피소드를 찾아 우리가 알고자 하는 v_pi 값을 알아내려 하는 것이다.

 

후자는 유용할듯 싶다. 특히 학습용 정책을 잘만들어 놓으면, 우리가 원하는 정책을 동시적으로 확장 할 수 있는 구조로도 발전가능 하겠다.