My data lab

두번째 실험으로 Blackjack game 에 대해서 Reinforcement Learning 을 이용하여 최적의 답(hit or stand) 을 구해보는 인공지능을 만들어보도록 하겠다. 

5장의 MonteCarlo method 와 4장의 Dynamic Programming 에 대해서

아래와 같은 의사코드를 바탕으로 모두 혼자서 구현하였고

github.com/Sangil55/ReinforceLearning_ex 여기에 코드를 첨부하였다.

몬테카를로부터 요약을 먼저해보자면

1.Episode 제작과정

MC 는 게임을 시뮬레이션한 것을 바탕으로 S A > R S A > R S A 이런 Episode 를 얻을 수 있었다.

그렇기 때문에 구현이 직관적으로 이루어질 수 있었다.

일단 episode 를 Generate 하는 것인데, 우리가 정책 pi 를 들고있다고 가정하면

Random 한 card 를 뽑는 과정을 통하여 쉽게 generate 할 수 있다.

2. Episode 진행 과정중 bust 가 나지 않는 상태과정에 대해서는 Reward를 조금 씩 주었다.

그이유는 21에 가까워졌다는 것으로 좋은 쪽으로 상태 이전이 일어났기에 일종에 Reward 를 부여한 것이다.

물론 Q(s,a) 가 그 값을 고려하여 update 하겠 지만, Q로인한 정책이 너무 소극적으로 바뀌게 되어 조금 더 직접적인 rewad도 필요했다.

3.간단한 게임이였지만 Ace 의 존재 (1 or 10) 떄문에 상태전이가 복잡한 경우가 생기더라,

다만 MC 의 장점이기도했지만, Episode 를 만들때만 주의하게 되면 , 그러한 상태 전이를 뒤에서 고려할 필요가 없었다.

4.구현에 유리함이 있었지만 상대적으로 많은 Episode (3만번)를 generate 하고, 그 것으로 Q값을 Q*값으로 수렴 시키고 최적 정책 pi 를 구했지만, 그마저도 data 불균형이 생기게 되더라, 그말인 즉슨, 자주오게 되는 state 에 대해서 update 가 자주일어나지고, 반대인 적은 case 도 생기게 되어, 적은 case 에 대해서 값이 들죽날죽해진다.

MC 결과를 지켜보자

ace 가 없는 경우 Q(S,0=stand) 의값, ace 가 없는 경우 Q(S,1=hit) 의값,

x 축은 내 카드합(0~20) y 축은 딜러 카드의 숫자이다.

ace 가 있는 경우 Q(S,0=stand) 의값, ace 가 있는 경우 Q(S,1=hit) 의값,

x 축은 내 카드합(0~20) y 축은 딜러 카드의 숫자이다.

Q값이 날카롭고 울퉁불퉁 하다 = 충분히 수렴시키지 못하였다. 

사실 노트북으로 에피소드를 30000번 돌린 회수이긴한데,

ACE 를포함 한경우라면 3000번도 안돌아갔을거다. 

그와중에 합이 13~20, 으로 분산이 된다치면 .. state 개수에 비해서 시행회수가 아직 너무 작다.

어찌됫건 ace 가있는경우 Q(S,1) 값이 ace 없는 경우 Q(S,1) 보다 대체적으로 높게나온것을 볼수 있다.

최적 정책은(Ace 없는경우)

ace 가 있는경우

ace 가 있는경우 최적정책이 더 1로(hit) 으로 덮여야 하는데, 듬성듬성 덮여있다.

전체적으로 dealer 패가 높을수록 더 공격적으로 하라고 지시한듯 하다.

역시 충분히 더돌려보고싶으나 수렴이 제대로 되고있는지 모니터링 하기가 꽤 까다롭다.

이번강화학습을 구현하면서 느꼈지만, 비교적 적은 state 의 예제를 구현해보는 데도, 구현하기에 꽤 까다롭고,

debuging과 Q 값, 정책값등을  같이 모니터링 하면서 코드를 지속적으로 수정 해주어야 한다.

하지만 예제코드를 구현하면서 어떻게 돌아가는지 체험해본 것 같다.

다음으로 DP 로 구현 과정을 요약하자면

1. 상태전이 확률 설정은 카드값이 나올 확률로 대체 한다.

2. Dealer 의 첫 숫자 - (17~21) 의 최종 기대값도 미리 계산된 페이지를 참고한다. 

www.blackjackinfo.com/dealer-outcome-probabilities/

3. Dealer 의 숫자 = 기댓값로 생각하여 승패를 예측한다.

4. Ace 가 있을 경우 17>7 로 가는 등의 상태전이 확률이 필요하다.

5. Q 대신 V 를 사용하며 수행 후 계산된 가치함수인 V의 결과는 아래와 같다.

 결과를 요약해보자면, 상대적으로 MC method 에 비해 완만하다. 확률적으로 승률을 계산했기 떄문에 

당연한 결과이고, 사실 수렴을 마쳤다고 봐도된다.

또한 적은 회수의 반복만으로도, V, pi 가 수렴을 한 것을 볼 수 있었는데

정책은 아래와 같다.

ace 가 있을 경우 18 까지 hit 을 하라는 결론~ 과 그렇지 안흘경우 13까지 hit을 하고, 14부터는 stand 를 하되,

Dealer 의 카드가 6~8인 경우 좀더 공격적으로 하라는 결론이였다.

결과적으로 MC method 는 아직 수렴중인 듯하며, 사실 정확한 Q와 pi 를 얻자면 더많은 시행 착오를 겪어야 될 듯하다.

원래 이예제를 풀게 된의도는 

MC vs DP 였다.

결론적으로 DP 를 구현할 수 만 있다면 DP 를 구현하는게 몇배는 더좋은 알고리즘을 만들어낸다.

즉, 상태전이확률과 승률의 기대값을 높은 신뢰도로 이미 알고 있다면,

굳이 많은 에피소드의 학습 없이도 답과 유사하게 만들어 낼수 있다. 일종의 Generative model 과도 일맥 상통한다고 보면된다.

하지만 실제 우리환경에서 이 것을 정확히 알지 못하는 대부분의 경우 에 있어서는 MC 로 구현 할 수 밖에 없을 것이다. 

컴공에서 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 값을 알아내려 하는 것이다.

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

Dynamic Programming

알고리즘 공부를 오래 한사람들은 흔히 Dynamic Programming 하면 점화식을 떠올릴 것이다.

일반적으로 점화식이 성립한다는 것은, 어떠한 탐색적 방법 보다도 시간복잡도측면에서 우위에 있다. 

n 번째항의 답을 n-1 번째 항 또는 그전에 구할 수 있는 모든값으로부터 구할 수 있다는 것 자체가 성립하기가 어려울 수 있지만, 성립만 한다면 거의 최적의 해라고 생각할 수 있다.

Reinforcement Learning 의 경우에 DP 라는 용어를  좀더 일반적으로 쓰는 느낌이다.

MDP 에서 p를 정의하고 우리는 알고 있다고 가정 했기 때문에, 우리는 Bellman Equation 을 구할 수 있었고,

가치 함수 또는 최적 가치 함수에 대해 점화식을 만들 수 있었다.

이 점화식 자체가 DP 를 의미한다.

사실 3장에서 DP 개념을 다설명한것같은데. 이장의 제목이 왜 DP 인지 모르겠다..

정책의 평가와 향상이 더 주가되는 챕터 같은데..  DP 가제목이라니. 일반적인 DP 의 해법이라고 봐야하려나

아무튼 리뷰를 시작하겠다.

1. v_pi 를 어떻게 구할 건지에 대해서 부터 시작한다. 우리는 정책 pi 를 알고 있고, p 를 미리 알고 있다고 가정하면

v_pi 를 구할 수 있는데 그과정을 Policy Evaluation 이라 한다.

일단 이런 Bellman Equation 을 따르는 것은 당연하고,

이 Equation 은 N개의 식 N 개의 변수를 갖으니 원래는 풀면 된다. 그런데

이 책에서는 아래와 같이 v 를 반복적으로 iterate 시키면, 위의 V_pi 로 수렴한다고한다. (왜죠??)

이유를 명확히 설명해주지는 않는다. '그렇다고 한다' 

다만 rootfinder 에서 아이디어를 얻자면, 0 = f(x) 의 근을 찾기 위해서

우리는 x = f(x) + x = g(x) = x 의 근을 찾기위해 , x_n+1 = g(x_n) 으로 update 해나간다.

v(t) = p*(r+v(t+1))  를 푸는 것이라 생각하면 v(t) 를 계속 g(v(t+1)) 로 update 해나가면된다.

다만 fixed point 에 대해서는 범위 안에서 Lipscitz 였던가  |g'| < 1 이 만족 해야하는데, 이 책엔 그런 설명 따윈없다.ㅎ

아무튼 이게 항상 수렴한다고 혹은 수렴하게 만들어 줄 수 있다고 가정 하고 이작업을 Policy evaluation 또는 Expcted update 라고 한다.

+>>일단 정책이 결정되었을 때 N개의 시스템에대해 직접 푸는 정해를 구하지 않고 Iterative 하게 하는 이유는 우리가 p 를 정확하게 알지 못하거나 환경에 대해 정확히 알지 못하는 경우도 있을것이고 (>>몬테카를로,TD 등으로 이어짐),,  pi=정책 조차도 결정되지 않은 변수로 optimal policy 를 위해 가변적으로 변해야 되는 부분 때문에 , 계속 설명할 '근사'적인 방법에 의존 할 수 밖에 없기 때문인 듯 하다. 어쨌건 정책이 결정되면 v_pi 를 구할 수있고, v_pi 로 부터 더좋은 정책을 구할 수 있고... 계속해서 v* 를 구해낼 수 있다는 것이다. 그렇다면 처음부터 pi 에 대해서 v_pi 를 정확하게 알 필요가 있을까?  지엽적으로는 v_pi 로 수렴하고, 전체적으로는 v* 로 수렴하기 위해 반복하는 일련의 큰 근사적인 반복이다.

2. 1의 과정은 보통 1번의 평가에서 한번 씩 갱신되는데, 가치가 결합되는 방식에 따라서 다양한 종류에 기대값 갱신이 존재한다고 한다.

3. 정책향상, 다른것 보다 정책향상에 대한 아이디어는 1에 비해서 너무 좋고 깔끔하다.  정책향상정리 (policy improvement Theorem) 에 의해서 진행 된다.

q_pi 는 state, action 을 하고난뒤 기대값이고,

v_pi 는 state 전후로 계속 p를 따를 때의 기대값이다.

q_pi(s,pi'(s)) 를 생각해보면

    a'=pi'(s)     pi

s------>s' --------->

    pi       pi

s------>s' --------->

에서 정책 s' 기준으로 앞부분이 바뀌어버리는 것을 의미한다. 

그외에 pi ' 는 p 랑 동일하다고 생각하면, 정책 pi 는 s> s' 가는구간에 대해서 4.7 을 만족하면 새로운 정책으로 변하게 된다.

이때 pi' 는 고룰 수 있는 액션중에 q 값을 가장 커지개 해주는 탐욕적인 방법으로 결정 하면되고. 이과정으로 

Policy improvement 라고 한다.

4. 최적정책이 아니라면 항상 정책향상이 이루어 질수 밖에 없다.

5. 보통 정책은 pi 는 결정적이아니라 확률로서 나타내진다. 그렇기 때문에 '정책 향상'이란것도 확률의 개선으로 이루어져야 될 것이다. 

6. 보통은 정책반복을 1과 3을 반복하는데 정책평가에서 vpi 로 수렴하기위해서 여러번 수행한다(like fixed point)

다만 자기들입으로도 수렴성이 보장이안되고, 오래걸린다고 한다. 아무튼 이 과정을 간소화 한게 Value iteration 또는 Truncated policy evaluation 을 포함한다고한다.

7. 정책 향상과 평가를 Async 하게 할 수 있다. 이로써 효율이 오르기도 한다고 한다.

8. 일반적으로 GPI 라고도 한다.