My data lab

PDE 를 풀기위한 여러 방법중 위의 방법들에 대해서 공부를 하였다.

FDM : 1차 2치미분을 태일러 전개를 통해 discrete 한 Q 값의 차이로 근사를 이용한다.

1차미분= discrete 한 두 관찰된 포인트를 이용하여 미분방정식을 대체 함

특징

1. 직관적이고 쉽다.

2. 양함수적 성질로 인하여, Stepping방법을 자유롭게 변형 가능

3. 고차로 변형이 쉽다.

4. 복잡한 공간에서의 적용이 어려움

5. 불연속점에 대한 불완전성

FVM : volume 을 미리 만들어 놓고 conversation law 를 이용하여

i 번째 grid volume 의 Q_i(t+1) 값을 주변 Flux 의 변화량 으로 나타낼 수 있다.

이 때, Flux 는 다시 Q_i-1, , Q_i , Q_i+1 등으로 나타낼 수 있으므로

이때 Flux의 정의에 따라서 차수와 안정성(stability) 등이 결정 된다.

특징:

1. FDM 과는 다르게 복잡한공간 (complex Geometry) 에서도 flux 를 정의 하여 사용가능하다.

2. 이때 만들어진 원래의 방정식은 높은 차수(high order accuracy)를 갖을수 없는 단점을 가지고있다.(~2차 정도?)

FEM : weak Sense 로접근한다.

Test function 을 가지고 접근하여 그것을 적분했을 때 원래 식에 일치하는 것인지 확인하는 매커니즘을 갖는다.

u 자체를 미리정해놓은 basis(pi1, pi2 .) 들의 Weighted 합이라고 간주하고

pi1, pi2 는 한편 근처의 pi 들 외에는 내적할경우 0 이되도록 설정 해 버린다.

그러면 원래 풀려던 식에 pi 를 내적하면 Tridiagonal 한 Matrix A, Ax=b를 푸는 문제 가 된다.

1. FVM 과는 달리, FEM 는 basis function 자체를 고차로 잡아 버릴 수 있기 떄문에 높은 차수를 갖을 수 있다.

2. Matrix 자체를 연산하기 때문에 Implict 한 Method 이기 때문에 stability 등에 불완전성을 갖는다.

두번째 실험으로 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 로 구현 할 수 밖에 없을 것이다. 

6장 TD 에서 매인 컨셉으로 나온 알고리즘 2개를 돌려보는 시간을 가졌다.

2개의 의사코드를 보고 아무것도 참고안해보고 직접 구현을 해보았다.

느낀점은 같은 Reinforce Learning 도 컨셉이나 구현 방식에 따라 성능이 많이 달라질것 같다. 

왜냐면 예를들면 경로 탐색의 경우 visit 체크를 하느냐 마느냐, Backward 로 갱신하느냐

Episode 를 직접 만드냐, 아니면 Episode 를 사용자로부터 입력을 받느냐, Random 한 출발을 하느냐,

종단조건을 어디서 줄거냐.( 일종의 Reward 가 Threshold 값(-100?) 이 넘게되면 종단 하는것도 방법이다.

이러한 세세한 사항 하나하나에 의해 수렴도 결정되고 수행 속도도 결정될듯 하다.

또한 이러한 간단한 예제를 구현하는대로 부가적인 프로그래밍요소가 많이 필요하였다. 

고로 RL 은 일반적인 솔루션을 만들기가 어려울것이다. 그 이유는 문제가 복잡할 수록 예외상황이나 Agent 세부적인 것들을 다 손을 봐줘야 하기 때문이다. 

아래의사코드를 바탕으로 구현하였다.

1. SARSA

2.Q-Learning

구현 후기는 일단 2가지 차이를 생각히보자면,

QLearning 이 조금더 Greedy 하고 미리 다음 step 을 보고 움직인다고할까? 

ODE 미분방정식을 풀때 다음 항의 미분값을 가져와서 평균내는 것처럼 (Runge kutta)

QLearning 은 다음 state 에서 Action 중에 일종의 max_a (Q(S',a)) 값을 가져와서 그 값으로 갱신 하기 때문에,

좀더 implict 한 method 이고 Convergence order (수렴속도) 가 빨라질 수 밖에 없을 것 같다고 생각 이 들었다.

한편 그 값은 가장 dominant 한 Q(S,A) 값이 기 때문에  

Q 가 수렴해야 할 방향중 가장 큰 Gradient 값을 가져와서 갱신 시켰다고 보는것과 유사 할 듯하다.

Sarsa 는 주어진 epidode 에 대해 오로지 그대로 움직이면서 주어진 State , Action 값 만 새롭게 갱신한다.

QLearning 은 주어진 Episode 의 1step 뒤의 주변 환경을 고려하여 갱신하다.

이러한 차이 때문에 , 절벽문제 같은 경우에 있어서는, 

Sarsa 에서는 Episode 중 절벽을 가는 Episode (다음 Action)가 존재하다면

Q(S,A) = Q(S', A) + 절벽으로 가는 Action 의 (-100) 업데이이트 가 이루어지기 떄문에

절벽 근처에 State 에 대해서도 낮은 Q 값을 갱신하는 반면 

한편 Q_Learning 에서는 Episode 다음 step에서 절벽쪽으로 가는 Action 이 있어도

Q(S,A) = Q(S', A) 절벽으로 가는 Action 의 (-100) 의 업데이트가 이루어지지 않기 떄문이다.

최적의 길 측면에서는 Q_Learning 은 주변을 흝는 대신, 미리 최적이 어디 일 것이다라는 assumption 을 포함한 더 공격적인 update 가 이루어질 것이며,

Q_Sarsa 는 정해진 Episode 의  State, Action 의 값 대로 epside 그대로 방어적이지만 정해진 길을 확실히 가는 update 가 이루어진다.  이 문제의 최적의 길 측면에서는 Q_Learning 이 유리 할 수 밖에없다.

다만 Episode 가 모든 State 를 골고루 스쳐간다고 가정하면

Q 값의 갱신은 Q_learning 은 좀더 정해진 (max) 값을 불러 오기 때문에 Q_sarsa 가 좀 더 episodic 에 의존하여 잘 이루어 질 수 있다.

하지만 종단 최적(?)의 경로 측면에서는 Q_Learning 이 좋을 수도 있다.

다만 Q_Sarsa 는 우리가 겪은 episode 의 경험으로부터 학습 하기 떄문에 , 좀더 Determinestic 하게 움직일 것이며,

'경험' 에 의존 한 다는 것이 '상태 전이 확률' 을 고려한 움직임이 될 수 밖에없다. 만약 Q_Learning 이 다음 상태의 max 값을 잘가져왔다 쳐도, 그 상태로 갈 확률이 거의 0 에 가깝다면, 사실 잘못된 Q 갱신이 이러날 수도있다.

그렇기 때문에 , 내가 환경을 잘모른다고 가정하면, 나는 Q_Sarsa 를 선호 할 것이다.

그리고 부족한 SARSA 를 위해 random 하게 탐색하는 episode 를 최대한 generate 할 것이다.

Risk 를 회피하는 측면에서도 SARSA 가 유리할 듯싶은데,

그렇다면 Q_Learning 을 왜쓰는 것일 까?

아래 결과를 보면 Q_Learning 이 최적 경로를 찾는 부분에 있어서 더욱 빠른 길을 찾아낸다. Q를 더 빠르게 수렴시킨다.

맨 아래 최종 그래프의 값을 보면 Q 값도 더욱 안전히 빠르게 수렴한 듯 싶다.

그래프는 Episode 별로 평균 Reward 를 구한 것인데,  Sarsa 는 Eps 에 의해서 절벽으로 가는 현상도 일어난다.

반면에 Q는 다음 step 에서의 Q 값은 절대 절벽으로 가는것으로 일어나지 않기 떄 문에 Episode 별 평균 Reward 에는 큰 영향이 없다.

우리가 Random 한 Episode 에서 보상을 최대로 알아내는 알아내는 길을 찾는 것이 목표라 할 때 

무엇이 목표일까?

1.(Risk 회피의 안전 제일)  vs 최적 보상의 경로를 Clear하게 얻고 싶은가

2.경험으로 부터 최적의 값을 알고싶느냐 vs 경험을 따르되 좀더 generate 하게 최적을 알고 싶으냐 

2.상태/환경 를 잘아느냐 vs 상태/환경를 잘모르느냐

뭐이런 측면에서 두가지 method 는 계속 비교당하지 않을 까싶다.

아래 구현/소스 과정에 있어서 부연 설명을 하자면

* 0,0>10,0 으로 가기위한 Random한 Episode 의 정의~

구현 방법에 있어서 Epsidode 를 대입 한 방식이 사람들과 다른점이 있을 수도 있다.

사실 나는 Episode 의 정의가 무엇이냐 부터 구현과정에 있어서 혼돈이 있다.

나는 Episode 를 시작에서 종단까지 의 한 Route 라고 생각하고 

0 0 > 10.0 으로 가는 random 한 경로에 대해서 모두 임의로 Generate 하였고, 

그것을 기반으로 RL  을 돌렸다. 

인터넷에보면 그렇지 않은 경우가 많다. 그냥 0, 0 으로 시작해서 절벽에 떨어지는 경우

종단 하는 경우의 코드가 있었고, -100을먹고 다시 처음 state 로 강제로 오게 하는 부분도 있다.

시작점은 항상 0,0 이였고, 10,0 까지 가는것이 계속 Episode 로 보더라..

물론 나는 그렇게 해도 좋을 것 같았으나, Episode 가 이렇게 깔끔하게 정의 되지 않는 경우도  있고, 

최초에 10,0 까지 가는 것도 시간이 너무 오래걸릴 것 같다는 생각도 분명히 있어서

일반적으로 한개의 시작상태 > 종단 상태로 가는 상태 변이의 집합을 한개의 Episode 라고 가정하고

그 path 자체를 Sarsa,Qlearning 의 input으로 대입 하였다.

* 나는 절벽에 떨어진다고 해도, 계속 -100 보상을 얻고 지속 한다고 가정하였다.

* 0,0>10,0 으로 가기위한 Random한 Episode 의 정의를 아래와 같이 정의한다.

EPisode 란 0 > 10,0 까지 의 임의에 경로를 온 사용자의 '경험' 이라는 측면에서 구현을 하였고,

그렇기 때문에 완성된 Path 를 역순으로 대입 시켜가면서 시작하여 종단 까지 탐색하였다. 

그리고 path 를 뒤에서 부터 돌면서 Q 탐색을 시작하면서 업데이트 시켰다.

Q 를 거꾸로 업데이트 시킨 이유는 1번의 갱신이후 바로 다음 갱신이 바로 전값을 가져올 수 있어서 이다.

출발점이 0,0 1개가 아니라면? 

State 를 정의하기 힘든경우라면?

그럼으로 Episode 를 명확히 할 필요가있다.

2. 완성된 Q 값 그래프

위는 SARSA 밑에는 Q 뭐가 맞는 것 같은가?

1000번이나 돌리긴 했지만 Q_Learning 의 경우 저렇게 어느정도 규칙적으로 수렴한(?)모습으로서 최적을 보장한다.

SARSA 의 경우 에는 좀더 Episode 의존적 이며 아직 더 수렴 할것(?) 같은 모습을 보인다. 

github.com/Sangil55/ReinforceLearning_ex/