My data lab

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 라고도 한다.