My data lab

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 자체 를 정의 할수 있다는 것을 뜻한다.