[ 강화학습 ] 4. Dynamic Programming

본 교재에서는 Dynamic Programming 을 다음과 같이 정의한다.

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).

Dynamic Programming, DP는 Markov Decision Process (MDP) 같은 환경의 완벽한 모델이 주어졌을 때 Optimal Policy를 계산하는 데 사용되는 알고리즘이다. 따라서 이번 챕터에서는 environment 가 finite MDP 라는 가정을 하고 진행한다. 이전처럼 수식 전체를 한번에 계산하지 않기에 계산량이 적다는 장점이 있으나 environment에 대한 명확한 정의가 있어야 한다는 단점은 치명적이다. 

DP의 핵심 아이디어는 가치함수를 이용해 좋은 정책을 찾는 것이고, 이전과 다른 점은 한번에 구하는 것이 아닌 여러 차례의 업데이트를 통해 구한다는 것이다. 

4.1. Policy Evaluation

DP에서 Policy Evaluation, 정책 평가란 policy π에 대한 state-value function을 의미한다. 

π(a|s)는 policy π를 따랐을 때 state s에서 action a를 선택할 확률이다. 

만약 environment의 dynamic을 정확하게 안다면 마지막 식은 연립방정식으로 해결이 가능하지만

우리가 이번 챕터에서 다룰 문제는 반복적인 계산으로 해결하는 것이 더 적합하다.

연속적인 approximate value function v0, v1, v2... 에서 vπ 에 대한 Bellman Equation을 활용하여

순차적으로 값을 계산할 수 있다. 그 수식적인 표현은 아래와 같다.

여기서 중요한 것은 수식의 가장 뒤에 붙을 for all s E delta 이다.

즉, vk에서 모든 delta에 속하는 s에 대해서 계산하고 다음 v(k+1) 로 넘어간다는 것이다.

sequence {vk}는 k가 무한으로 갈 때 v(π)로 수렴하며, 이렇게 반복적으로 업데이트 하는 알고리즘을

Iterative Policy Evaluation이라 정의한다.

모든 state s에 대해 다음과 같은 과정을 반복한다.

1. v 변수에 이전값 v(s)를 저장한다.

2. v(s)를 Bellman Equation에 따라 업데이트 한다.

3. 모든 s 중에서 가장 많이 업데이트된 v값의 변화량을 저장한다.

4.2. Policy Improvement

4.1에 의해 Policy Evaluation을 진행했다면 어떻게 더 나은 Policy로 나아갈 수 있을까 그 개선을 목표로 한 알고리즘이다.

특정 state s에서 policy를 변경해야 할 지 그대로 유지해야 할 지 어떻게 결정할 수 있을까

이미 우리는 v_π(s)를 통해 현재의 policy를 따르는 것이 얼마나 좋은지 알고 있다. 이에 새로운 policy를 선택할 지, 말 지를

결정할 기준이 필요하고 그 방법 중 하나가 s에서 a를 선택하는 것이다. 그리고 기존의 policy π를 따라본다.

임의의 정책 π에서 수렴된 vπ에 대한 greedy policy가 있을 것이고, greedy policy 이외의 다른 행동 a를 선택하여 기존 정책 π를 따른 후에 기존 정책에 따른 vπ(s) 보다 크다면 새로 선택된 행동 a가 더 나은 policy가 된다.

즉, 기존 Policy의 value function에 대해 greedy한 방법을 사용해서 기존의 policy를 개선하여 새로운 policy를 만드는 프로세스를 policy improvement라 한다. 

4.3. Policy Iteration

앞서 policy improvement의 과정을 확인하였다. 이를 iterative하게 진행하면 그 과정중에 개선되는 policy와 value function의 sequence를 얻을수 있다. 

E는 policy evaluation을, I는 policy improvement를 의미한다.

이 단원에 들어서며 가장 먼저 이야기했던 전제를 떠올려보면 Finite MDP는 유한한 policy가 존재하기에 

이 프로세스 역시 유한번 iteration을 통해 optimal policy와 optimal value function으로 수렴해야 한다.

Optimal policy를 찾는 일련의 과정을 Policy Iteration이라 부르며 그 과정은 아래와 같다.

4.4. Value Iteration

Policy Iteration의 과정을 다시 떠올려보면 매 Iteration마다 Policy Evaluation이 포함되어 있다. 

Policy Evaluation 과정 자체가 State Set를 모두 돌아 체크하는 것을 필요로 하기에 시간이 많이 소요된다.

그렇다면 Policy Iteration의 수렴을 보장하는 동시에 그 과정을 간단히 할 수 있는 방법은 무엇이 있을까

단 한 번의 State 업데이트와 함께 Policy Evaluation을 종료하는 방법이 있고, 이를 Value Iteration이라 부른다.

즉, 한번 Value를 갱신할 때마다 Policy를 바꾸는 Policy Evaluation이 아니라 V값을 수렴할 때 까지 업데이트 한 후에

마지막에 Policy를 바꾼다. 조금 더 간단히 말하면

Policy Iteration : 주어진 Input Policy에 따른 행동 a에 대해서 V값을 배운다.

Value Iteration : 가능한 모든 정책 a들 중 최대값을 주는 V값을 배운다.

그렇다면 무조건적으로 Value Iteration이 Policy Iteration보다 나은가?

아니다. 일반적으로는 Value Iteration이 빠르지만 Environment에 따라 Policy Iteration이 나을 수 있다.

4.5.Asynchronous Dynamic Programming

간단히

4.6. Generalized Policy Iteration

Policy Iteration을 정리하면 현재 Policy에 맞게 Value Function을 만드는 Policy Evaluation과

현재 Value Function에 맞게 Greedy 한 Policy를 만드는 Policy Improvement로 이루어져 있다.

반면 Value Iteration은 Evaluation과 Improvement를 동시에 진행한다. 앞서 간단히 다룬 Asynchronous DP의 경우 역시

Evaluation과 Improvement가 미세한 차이로 진행된다. 

이처럼 Policy Evaluation과 Improvement가 서로 상호작용하는 이 개념을 Generalized Policy Iteration, GPI라고 부른다.

거의 모든 강화학습은 GPI로 설명되며, Policy는 항상 Value Function에 대해서 향상되고, Value Function은 항상 Policy를

따르는 방향으로 나아간다.

GPI에서 Evaluation과 Improvement는 경쟁하는 동시에 협력하는 것으로 보기도 한다. 

서로 반대 방향으로 당긴다는 관점에서 이 둘은 경쟁한다. 

일반적으로 Value Function에 대해 Greedy 하게 Policy를 만드는 것은 변경되는 Policy 에 대해서 Value Function을 부정확하게 만들고, Policy와 일치하는 방향으로 Value Function이 변경되는 것은 더이상 Policy가 Greedy하지 않음을 의미한다.

하지만 최종적으로 이 두 프로세스는 Optimal Value Function과 Optimal Policy를 찾는다는 관점에서 협력한다.

4.7. Efficiency of Dynamic Programming

간단히

4.8. Summary

이번 챕터에서는 Finite MDP 를 해결하는 것과 관련이 있는 DP의 기본 아이디어와 알고리즘을 다뤘다.

Policy Evaluation은 주어진 Policy의 Value Function을 반복적으로 계산하는 것을,

Policy Improvement는 주어진 Value Function을 고려해서 더 나은 Policy를 계산하는 것을 의미한다.

이 둘을 이용하여 DP에서 가장 유명한 Policy Iteration과 Value Iteration을 유도할 수 있다.

이번 챕터에서 다룬 DP는 이들 중 하나를 이용하여 MDP에 대한 완벽한 정보가 존재하는 finite MDP의

Optimal Policy와 Value Function을 계산하는 것이다.