My data lab

RL 에 대해서 여러가지 리뷰를 진행 하였고, 정리하였다.

일단 RL 쪽에 계속 발전하고있고, 기존방식의 문제점들을 보완하려는 노력을 하고있다.

RL 같은경우 아래와 같은 한계점들이 존재한다고한다.

1. State 가 무수히 많을 경우

2. 수렴성의 보장

3. 높은 분산값 

이런것들을 보완하기위해서 새로운방법들이 나오고있고, 현재 진행형 인 듯 하다.

강화학습을 나중에 더 깊게 파고들 수도있지만. 정확히말해서 그렇게 까지 잘 될것 인지에 대한 확신 이 없다.

적절한 보상을 주고 알아서 판단하게 만들려고하는게 강화학습인데 어디까지 더 생각을 해야될까? 라는 의문점을..

아무튼 키워드위주로 정리하겠다.

DQN - state 가 무수히 많을 경우 Q-Value 를 state마다 정의하지않고,  네트워크를 만들어서해결

Policy gradient -  DQN 과 이어서 생각해보았을때 seta 가 일종의 DQN 의 parameter이라 생각해보자, 기존에는 policy 가 Q_seta 에 의해 결정되었다면,  policy 자체를 seta 에 대한 직접적인 output 이라 생각한다.

그 다음 Q_pi 의 값이 늘어나는쪽으로 (gradient) 가게되면 전체적으로 value function 이 높아지는 쪽으로 수렴한다.

cost function 은 대체로 보상 들의 합의 기대값으로 놓고 그것을 최대로 하는 seta 를 찾는게 목표이다.

이 식으로 인해 grad(log_pi_seta(타우=경로) ) 의 기대값을 계산하면 costfunction 의 그라디언트를 구할 수 있는데,

이 값(grad(log_pi_seta(타우=경로) )은 기대값이기 때문에 MC - method 등으로 인해 경험적으로 구할 수 있다.

하는이유 : DQN 에 비해 좋은 수렴성

Baseline - 강화학습에서 미리 계산된 Value Function 을 사용 할 수도 있다.

A = Q - V 이렇게 놓고 A 를  수렴 시키기도한다. (분산이줄음)

Actor-Critic

위의 policy gradient 의 경우에는 MC 로 진행 햇을경우 높은 분산값을 갖는데 그값을 줄이기위해서

ACtor Q 를 수렴

Critic V 를 수렴 ( Q 의 action 선택을 비평)

Critic은 action value function을 approximate하는 w를 update하고

이때 Ciritic 도 network 를 사용하는 이유는 모든 경우를 trial 하지 않고 적은 sample 로도 기대값의 합을 알수 있게 되는 효과가 있다.

Actor는 policy를 approximate하는 seta를 update 따라서 w와 seta, 두 개의 weight parameter 를 갖는 강화학습 방법 

DDPG

NAtural Policy

TRPO PPO 등이 더있는데. 나중에 정리하겠다.

두번째 실험으로 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/

TD 란 Temporal-Diffrance , 시간의 차를 두어 학습한다의 용어이다.

일단 이 내용 리뷰를  쓸까 말까 고민을 하다가 작성을 하는데 

그이유는 구현하기전 까지는 정확히 컨셉이 이해가 안될 것 같아서이다.

MC method 와 DP 방법을 결합했다고 하는데, 두개 컨샙이 아예 달라 애매 한 말이다.

1.상태 전이 확률 p 를 준다는 뜻인가?  > 아니오 상태 전이확률이 필요없다.

2. v pi(s') 를 이용해 v_pi(s) 를 구한다는 뜻인가? > 예

3. 에피소트의 (S,A,S,A 시리즈) 로  value function 을 업데이트 하겠다는 뜻인가? >Yes

어쩃든 목적은 정책 pi 에 대해서 vpi 를 추정하는데 목적이 있다.   MC method를 개량 한 것이라 생각한다.

원래는 MC method 로 한 에피소드 종단까지 기달려야 하지만,

TD method 는 중간에 Value function 를  v(s) = v(s) + a( g(t) - v(st) )  이렇게 업데이트하는데, 여기서 g(t) 는 우리가 구한 value_function 이 아니라  t 시간이후의 이득(?) 이고 이 값을  (Rt+1 + rV(st+1) ) 값으로 대체 하여 

V(st) 를 업데이트한다. 이방법을 TD(0) 이라하며 one step TD 라고한다.

two step TD 이면 Rt+2 + rV(st+2) 가되려나? 아니면 2개의 합산이되려나 아무튼 뒤에 다시 나온다 한다.

 Gt − V (St) 를 Td Error 라 한다.

아무튼 이방법이 MC - method 에 비해서 이점이 있겠지 .. 

언뜻봐서는 MC 도 충분히 평가나 value function 의 갱신이 빠를것같은데..

TD 는 그것보다 더빠르다고,, 에피소드가 길어지거나 아예없는 경우에 이점이 더 커진다고한다.

정리하자면

1.MC 에 비해서 online 으로 가치 평가가 된다. (에피소트종단전에)

2. 수렴성이 MC 와 마찬가지이다. -t가 작아질수록 수렴에 도움이되는데 책에는 수식적인 이유는 없다 그렇다고 한다.

Td 에도마찬가지로 On-policy / Off policy 방법이 존재한다.

Td ,on-policy method 를 sarsa method라고하며

Td ,off-policy method 를 Q-learning 이라고한다. 의사코드로 비교해보자

이 의사코드를 한번 보면

일단 using policy dervied from Q 라는 뜻이 처음에 잘 이해가 안됬다. 

Q 러닝에서는 따로 pi 가 지정되어있지 않고, Q(s) 에서 갈 수 있는 다른 value function 들의 추정값 (Q(S,A1) , Q(S,A2) ...) 으로부터 

가장 큰 값으로 정책을 결정 하고 나머지는 epsilon 을 주는 방식 이기 때문 이다.

이 부분에 있어서 우리는 MC method 완 다르게 정책을 입력으로 받을 필요가 없는 부분이고, 

Q- value 자체가 정책을 결정한다.  그래서 Q 로 묶어버리기 때문에 정책 향상 과정도 따로 필요가 없을듯 하다.

또한 off/on policy 차이 도있지만

sarsa 와 Q - learning 차이 점충 가장  큰 부분은 sarsa 의 경우 Next Action 까지 확률적 정책으로 떙겨오지만,

Q-Learning 의 경우 next state 를 까지는 같지만 그다음 action 의 경우 가장 큰 가치의 value function 값으로 땡겨온다.

이것이 Action 이 현재 정책을 따라 가지 않는 부분이기 때문에 Q-Learning 을 off -policy 라고 한다. 

앞장하고 컨샙이너무달라서 이해가안될 수 밖에 없다.

아무튼 이제 구현을 해봐야겠다.

지인의 조언으로서는 Sarsa 가 메모리형식으로 저장이 불가능한 반면에 

Q-learning 은 메모리제어가 가능하다고.. 한다.

우리가 비교해볼 수 있는것들은

TD vs MC vs DP  일단 이렇게 3개를 비교해볼 수 있을 것 같고,

TD(Sarsa) vs TD(Q) 가 어떻게 다른지 비교를 하는 예제를 구현 해볼 수 있을 것이다.

다음 에는 진도대신 이 예제를 구현해보는 것으로 포스트(프로젝트)를 대신하겠다.

컴공에서 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 라고도 한다.  

Ref - ReinForcement 2nd Edition.pdf

Richard S. Sutton

일단 해석학과 대수로 고통받던 나날중에 프로젝트를 위해 강화학습을 따로 스터디를 진행하였다.

바이블이라고 하는 Richard Sutton 의 책을 보면서 배운내용을 정리하고자 한다.

다만 수학을 보다가 이쪽 내용을 봐서 그런지 모르겠는데

전체적으로 Markov 전재를 하고 다룬다는 점에서 일반적인 문제를 특수한 경우로 정의하여 다루는 것 같고

일종의 점화식들 : 이렇게 돌리면 최적의 가치함수로 수렴할것 이다 라는 내용이 중간중간에 자주 나오는데

바이블이란 책을 보는데도  이 것들이 이유가 없이 애매하다. 일단 내가 잘몰라서 그런것이라 생각하고 넘어가긴했지만 생각해 볼점이 많을것 같다.

실제로 강화학습이 문제에 잘안쓰이는 이유도 이쪽으로 투영시키기 위해서는 첫번째로 State 로 상태를 정의할수 있는 문제 여야하며 두번째는 수렴성이 명확히 보장되지 않아서가 아닐까 싶다. (아니면 내가 잘 이해못했거나.. 책을 보고도 명확히 이해가 안되는건 역시 문제가 있다. )

chapter 3 MDP 

강화학습 에이전트 란 행동(Action)을 하면서 보상(Reward)을 얻는다. 내부적인 값은 상태(State) 값을 갖는다.

MDP

1. 상태를 갖는다. 상태를 갖음으로써, 즉각적인 보상외에 전이된 상태의 보상, 즉 Delay Reward 를 고려해야한다.

2. 지연된 보상을 고려하기위해서 v* q* 등을 고려한다. 

3. p 는 State-Trainsition Property 로 볼 수 있는데 바로 전 상태에만 영향을 받는다(Markov) 및 MDP 의 Dynmaics 이라고 불리기도한다.

4. 위로 부터 보상의 기대값 r(s,a) = Ra * sigma_s'( p(s',r | s,a)를 구할 수 있다.

5. 장기적 보상을 최대로 갖는 목표(goal)를 갖는다.

6. Policy 정책(pi) 에 대한 가치 함수 ( value function) 를 정책 pi 를 따랏을 경우 예상되는 이득의 기대값으로 정의한다.

7.  6 에서 정의한 내용들은 Bellman Equation(3.12), 아래와 같이 가치 함수(s) = 시그마(가치함수(s')* 상태전이확률) 을 만족해야한다. 이때 이후 가치함수를 이용함으로써 현재 가치를 알아내기 때문에 Bootstrap 기법이라고 하기도한다.

8. 6,7의 에 정의한 value Function 에 대해서는 최적 정책함수 (Optimal Value Function) 이 Uniquae 하게 존재 하고, 아래의 최적 Bellman Equation 을 만족해야한다.

7과 비교했을 때, 기대값이 아닌 최대값으로 Update 를 해야 하는것이 중요하다.

v의 경우 action 을 수행한 다음의 얻게될 전이확률 * 보상의 합 (action 수행뒤 다음 State 가 꼭 1개는 아니다)이 최대가 되야한다.

q 의 경우 현재 상태와 액션을 결정 되 있고 (s,a) s' 도 전이확률로써 결정되어있다. 그렇기 때문에 각각의 다음 state s' 에 대해서 취할수 있는 action a' 들 중 최대의 값을 갖는 a' 를 택한다. 즉 다음 State s' 에서 할 수 있는 action 중에서 최대 q* 를 가져와서 업데이트한다.

9. 8에 대해서 풀게되면, v* 또는 q* 를 알 수 있고, 최적정책은 탐욕적으로 결정하면된다.

9. MDP 라는 것은 보통 p 를 알고있다라는 것을 뜻한다. 즉 상태 와 상태전이확률에 대한 이해가 확실하고, MDP 에서 M(markov) 은 p 자체 를 정의 할수 있다는 것을 뜻한다.