4. 4장 DP (Policy Evaluation and improvement)

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