[Ch.4] Dynamic Programming

 

 이번 포스팅에서 다룰내용은 Dynamic Programming(이하 DP)입니다. 강화학습은 시간에 따라 step별로 action을 취하는 문제를 MDP로 정의하여 푸는 방법 중에 하나인데, DP도 마찬가지 입니다. 차이점은 DP는 model(environment)의 reward, state transition probability)을 알아야하는(Model-based) 방법인데 반해, 강화학습은 model을 몰라도(Model-free) 풀 수 있는 방법입니다. 전자를 Planning이라고 부르며, 후자를 Learning이라고 말합니다. 즉, DP는 Planning의 방법으로써 env.의 model을 안다는 전제 하에 Bellman Eqn.을 푸는 것을 말합니다. 이 DP를 보완한 것이 강화학습입니다.

 

---

Dynamic Programming

 Sutton 교수님의 교재에서는 DP를 다음과 같이 정의합니다.

The term dynamic programming (DP) refers to a collection of algorithms that can be used to compute optimal policies given a perfect model of the environment as a Markov decision process (MDP)

 

 

앞서 말씀드다시피 environment의 model을 완벽히 알고 푸는 algorithm이라고 하네요. DP는 강화학습보다 먼저 Bellman Eqn.을 푸는 algorithm으로 소개가 되었습니다. "Dynamic Programming"이라는 표현이 DP의 특성을 매우 잘 나타내주고 있습니다.

 

< Fig 1. The meaning of DP >

 

즉, Dynamic은 동적이라는 뜻으로, 시간에 따라는 변하는 대상을 다루고 있음을 나타내고 Programming은 여러 process로 나누어 Planning한다는 뜻입니다. 단어로부터 알수 있듯이 DP의 개념은 큰 순차적인 행동 결정 문제를 작은 process들로 나누어 푸는데, 푸는 대상이 시간에 따라 변하는 대상인 것입니다. 예를 들자면, 우리는 1부터 100까지 더하는 문제를 한꺼번에 세로로 쓰고 일의 자리, 십의 자리, 백의 자리를 따져가며 계산하는 것이 아니라 다음과 같이 순차적으로 작게 풀어나갈 수 있습니다.

 

< Fig 2. Concept of DP >

 Prediction & Control

DP는 Prediction과 Control, 두 step으로 나누어집니다. 그리고 현재 진행하는 policy에 따라 value func.을 구하고(prediction) 이를 토대로 policy를 optimal하게 발전시키(control)는 흐름으로 진행됩니다. 이때, Prediction의 과정이 Policy Evaluation이고, Control의 과정이 Policy Improvement입니다. DP는 각 과정에서 사용하는 Bellman Eqn.에 따라 2가지 종류로 나뉘게 되는데 Bellman expectation Eqn.을 사용하는 Policy Iteration과, Bellman optimality Eqn.을 사용하는 Value Iteration입니다.

< Fig 3. DP의 종류 >

 

Policy Iteration

 Policy Evaluation

자, 그러면 조금 더 DP스러운 예제를 하나 생각해보겠습니다. 다음과 같이 State 1, 2, 3이 주어져 있습니다. 이 state들은 MDP로 정의되어 있습니다. 그리고 각 state를 통해서 value func.들이 존재합니다.

 

           

 

< Fig 4. DP state, value func. Example >

 

 우리가 찾고자 하는 것은 각 state들의 true value func., Vπ(s)입니다. True value func.이라 함은, 현재 따르는 policy가 옳냐 틀리냐를 판단하기 위해서(처음의 policy는 random policy이기 때문에 반드시 이를 판단하고 발전시켜야합니다) value func.을 사용하는데, 처음 구한 state의 value func.은 진짜 value func.이 아닙니다. 현재의 policy대로 각 state별로 중요도의 경중이 존재하게되는데 이를 agent는 알 길이 없습니다. 그래서 몇번이고 이 state 저 state를 왔다갔다하면서 value func.을 계속해서 update를 시켜 최종적으로 중요한지 안한지를 판단할 수 있는 "진짜" value func.을 찾는 것입니다. 하지만 이 true value를 처음부터 구하기가 매우 어려우니 아래와 같이 iteration을 반복하며 점점 true value에 다가가자는 게 DP의 아이디어입니다. 

 

< Fig 5. Iterations for get the true value func. >

 

 

이 때, 하나의 Iteration에서는 우리가 알고 있는 model을 이용해서 전체 state의 value func.을 모두 구합니다. 이렇게 되면 무한히 반복되면 전체 state의 "진짜" 정보를 알게 되고 확실히 가야할 state도 알 수 있게 됩니다. 이렇게 true value func.을 구하기 위해 Iteration을 반복하는 것을 Policy Evaluation이라고 합니다. 이때, policy iteration사용하는 value func.을 구하는 식은 계산가능한 형태의 Bellman Expectation Eqn.입니다.

 

 

Ch.3와 다른 점은 iteration k가 더해진 것뿐입니다. 현재 state s의 (k+1)번째 value func.은 s에서 이동 가능한 s'에 대해서 k번째에서 구해놓은 state s'의 value func.을 이용한다는 것입니다. 이렇게 next-state-value func.으로 present-state-value func.을 구하는 것을 Back-up이라고 합니다. backup을 진행하는 step에 따라 one-step backup과 multi-step backup이 있고, 구하는 state의 종류에 따라 Full-width backup과 sample backup이 있습니다. DP는 value func.을 구할 때 바로 다음 step의 state value func.을 이용하기에 one-step backup이고, 현재 s에서 가능한 모든 s'들의 value func.을 구하기 때문에 Full-width backup입니다. 그러면 실제 grid-world에서 예제를 살펴보겠습니다.

 

Example(grid-world)

 살펴볼 예제의 환경과 조건은 다음과 같습니다.

< Fig 6. Policy evaluation example in grid-world  >

4x4의 회색 표시된 state가 terminal state인 grid-world입니다. action은 상하좌우 4가지이고, 제일 바깥쪽 state에서 gird-world를 초월하는 action을 취할경우 제자리로 다시 돌아옵니다. deterministic한 환경으로 가정하여 state transition probability는 1이라고 생각하겠습니다. reward는 time-step에 따라 -1을 받고 따라서 reward를 최대로 받아야하는 agent는 최단거리로 terminal state로 가는 것을 학습할 것입니다. 처음 agent가 택하는 policy는 상하좌우를 모두 같은 확률로 가는 uniform random policy입니다. 그럼 agent가 이 policy를 택했을 경우에 value func.을 구해보겠습니다.

 

< Fig 7. Policy evaluation iter.0 >

 

iteration 0입니다. 왼쪽 표와 같이 초기 value func.들은 모두 0입니다. 그럼 (1,2) state에서 현재의 V0 을(현재는 0) 위와 같이 one-step씩 이동 가능한 모든 next state s'의 value func.으로 다음 interation의 value func.(V1) 을 구하여 update할 수 있습니다. 계산 식에 어떤 value func.을 사용하는지 아시기 편하게 색을 칠해두었습니다.

 

 

< Fig 8. Policy evaluation iter.1 >

 

위와 같이 모두 계산하면 첫 번째 iteration 결과 update된 value func.들이 왼쪽과 같이 도출됩니다. 이제 마찬가지의 방법으로 (1,2) state 그리고 이번에는 (1,3) state까지 계산한 결과입니다. 그렇게 반복하다보면 우리는 최종적으로 다음의 evaluation 결과를 얻습니다.

 

< Fig 9. Policy evaluation in P.I. >

 

 이렇게 iteration을 반복해서 해당 policy에 대한 true value func.을 구하는 과정이 policy evaluation입니다. 하지만, 우리는 어떨 때 true value라고 판단을 해야할까요? 그리고 만약 간단한 env.이 아니라면, 모든 value-func.을 구하는 것이 과연 빠르고 정확하게 계산할 수 있을까요? 전자의 질문에서는 심히 고민해봐야할 문제지만, 제가 직접 작성한 code를 보면 일정 iteration이 지나고부터는 값이 어느 정도 수렴한 다는 것을 알 수 있기 때문에 적당한 시점에서 true value라고 판단할 수 있을 것 같습니다. 후자의 질문에 대해서 생각해보면 1) 복잡한 실제 환경 속에서 DP의 계산량은 엄청 많다는 것과 2) model을 알고 있어야만이 풀 수 있다는 생각이 듭니다. 따라서, 이 부분이 DP의 한계점이고 이를 보완한 것이 강화학습입니다. 

 Policy Improvement

 Iteration을 반복하며 true value func.을 찾았으면 이 policy를 따르는 것이 좋은지 안 좋은지를 판단하고 Policy를 update해아합니다. 이를 통해서 우리는 현재의 policy보다 더 나은 policy를 따르게 되고 점점 optimal policy에 가까워 질 것입니다. 이 과정을 Policy Improvement라고 합니다. policy를 improve하는 방법이 정해져 있는 것은 아니지만, 여기서는 가장 널리 알려진 방법인 Greedy policy improvement을 다루겠습니다. Greedy policy improvement는 말 그대로 가치가 가장 높은 state를 가겠다, 즉 max값만을 선택하겠다는 겁니다. policy evaluation에서 state-value func.을 이용하여 모든 state들에 대해 value값을 구해놓았다면, 이제는 policy에 따른 action을 취해야합니다. 현재의 action은 random policy에 따라 random한 action을 취하는데, 우리는 Greedy policy improvement의 방법에 따라 현재 state에서 갈 수 있는 state 중 가장 높은 곳으로 이동하는 action을 취해야합니다. 이러한 action을 정량화하여 선택하는 기준을 만드는 것이 아래의 q-func.(action-value func.)입니다.

 

policy evaluation에서는 state의 value func.을 iterative하게 계산하여 모든 state들에 대한 true value를 도출하는 과정이라면, policy improvement에서는 도출된 state value들을 토대로 현재의 policy를 action-value func.을 이용하여 더 좋은 action을 선택하는 policy로 만드는 과정입니다. 그리고 이 q-func.의 max값만을 취하는 것이 바로 greedy policy improvement입니다. 그러면 앞선 결과를 바탕으로 greedy policy improvement을 적용해보겠습니다.

 

 

< Fig 10. True value func. and State numbers >

 

 

 왼쪽은 policy evaluation 결과 얻은 true value func.들이고, 오른쪽은 non-terminal state를 numbering한 것입니다. 이제 state 1과 state 5에 대해 q-func.을 구하겠습니다.

 

 

< Fig 11. Greedy policy improvement >

 

state별로 취할 수 있는 action에 대해 각각 q-func.값이 구해지고 greedy policy improvement를 통해 선택된 action들입니다. 그리고 모든 state에 대해 이를 적용하면 아래와 같아집니다.

 

 

< Fig 12. The result of Greedy policy improvement >

 

이 예제는 grid world가 매우 단순하고 계산이 간단한 조건이기 때문에 policy evaluation과 policy improvement를 한 번씩만해도 optimal policy를 찾게 됩니다. 하지만 보통의 경우에는 이를 반복적으로 계산해야 optimal로 다가갑니다. 그래서 Policy "Iteration"이라고 부르는 이유가 그것입니다.

 

그럼 이 모든 걸 코드로 구현해보겠습니다. 

 

 

 

맨 마지막에 Policy Iteration 결과에 대해 부연설명을 드리자면, Fig12와 결과가 같아야하지만, np.argmax를 취했기 때문에 max값 index가 선행하는 것 하나만 나오게 됩니다. 예를 들자면, state 3의 경우 {Down, Left}를 도출해야하지만, np.argmax에 따라 index가 선행하는 down하나만 나오게 됩니다. T는 terminal state를 의미합니다.

 

Value Iteration

 Policy Iteration과 구분되는 Value Iteration은 Bellman Optimality Eqn.을 이용하는 것인데, 이를 이용하면 evaluation을 한번만 진행하게 됩니다(전체 Iteration중에 한번이라는 뜻입니다. evaluation은 수많은 부분 iteration으로 이루어져있습니다). 우리는 evaluation과정에서 이동가능한 state s'들에 대해 모든 value func.들을 더하여 도출했지만, 이중에 max값을 취해서 greedy하게 value func.을 구해서 improve해버리자는게 Value Iteration의 아이디어입니다. 그래서 우리는 action을 취할 확률을 곱해서 summation하는 대신에 max값을 취하는 아래의 optimal value func.식을 사용합니다.

 

 

 

 앞서 소개했던 grid world 예제에 Value Iteration을 적용해보겠습니다.

 

< Fig 13. Policy Evaluation iter.0,1 in V.I.>

 

그리고 이를 수렴할 때까지 반복하면 아래와 같습니다.

 

< Fig 14. Policy Evaluation in V.I. >

 

Policy Iteration과 다르게 세 번째 iteration(k=3)에서 이미 converge하는 것을 알 수 있습니다. Value Iteration을 구현한 코드를 보겠습니다.

 

 

 

 

 여기서 Policy Iteration과 Value Iteration의 눈에 띄는 차이점은 policy improvement가 없다는 것입니다. Policy Iteration의 경우에는 policy에 따라 value func.이 확률적으로 주어지게됩니다. 따라서, 기댓값으로 value func.을 구해야만하고 Bellman expectation eqn.을 이용하게됩니다. 하지만 이와달리 Value Iteration의 경우에는 현재 policy가 optimal하다는 것을 전제해서 value func.의 max를 취하기때문에 deterministic한 action이 됩니다. 우리가 Ch.2에서 다루었듯, optimal policy에서는 a = argmax q∗(s, a)일때 π∗(a|s) =1 이기때문입니다. 따라서, Value Iteration에서는 이미 value func.의 ture value를 찾는 policy evaluation에 optimal한 policy로의 improvement가 내재되어있습니다. 따라서 policy evaluation과정만으로도 optimal policy로 다가갈 수 있습니다. policy evaluation도 결국 여러 iteration을 진행하기에 policy도 그 만큼 update됩니다. 작성한 코드에서도 policy evaluation 함수 내 # update policy부분(policy improvement)이 있는 것도 같은 이유입니다. 

마치며

 이렇게 Dynamic Programming의 두 가지 iteration방법을 알아보았습니다. 하지만, 방대한 계산을 요하며 model을 알아야하는 점이 실제 문제를 푸는데 있어서 많은 제약이 따릅니다. 따라서 이를 보완하여 full-width backup을 하는 것 대신, trial and error를 겪으며 sample backup을 하자는 것이 강화학습이고 다음 장에서는 이에 근간이 되는 Monte Carlo Method에 대해 다루겠습니다.

 

오탈자나 잘못 언급된 부분이 있으면 댓글로 지적해 주세요 :)

 

Reference

[1] https://dnddnjs.gitbooks.io/rl/content/dynamic_programming_1.html

[2] 이웅원, 양혁렬, 김건우, 이영무, 이의령. "파이썬과 케라스로 배우는 강화학습". 위키북스. p.60-109