인공지능의 기초: MDP에서의 동적프로그래밍 기법

 MDP에서의 동적 프로그래밍 기법

동적 프로그래밍(Dynamic Programming)

문제해결을 위해 문제를 여러개의 부분 문제로 분해하여 해결하는 접근법.

1. 최적 부분 구조 (Optimal Substructure)

전체 문제의 최적해를 부분 문제의 최적해들로 구할 수 있는 경우.

2. 겹치는 부분 문제 (Overlapping Subproblems)

동일한 부분 문제들이 반복해서 나타나는 경우(Recursive)

= 부분 문제의 최적해를 캐쉬하고 재사용할 수 있는 경우

MDP에서의 문제 : Prediction & Control.

• Prediction

주어진 policy로 value function값을 구하는 것.

$$V^{\pi }={(I-\gamma P^{\pi })}^{-1}{R}^{\pi }$$

이렇게 Bellman expectation equation matrix를 이용한 방법은 역함수를 구하는데만 $O(n³)$의 시간이 걸려서. 시간복잡도가 $O(n^3)$이다.

이를 단축시키기 위해 동적 프로그래밍을 사용한다.

동적 프로그래밍 적용 가능성

위의 bellman expectation equation matrix는 역행렬이 존재하는 경우, bellman expectation equation으로 $V_{\pi }(s)$를 구할수 있음을 알려준다. 그렇다면 bellman expectation equation으로 나타낸 $V_{\pi }(s)$를 알아내는 수식을 어떻게 구할 수 있을까?

bellman expectation equation은 어떤 state, s의 value function이 그 successor state, s'들의 value function으로 구해진다는 것을 나타낸다.

$$V_{\pi }(s)=\sum _{a\in A}\pi (a|s)R_s^a+\gamma \sum _{a\in A}\pi (a|s)\sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{V}_{\pi }(s^{\prime })$$

여기서, $s^{\prime }$는 S의 모든 원소가 되기 때문에, $s,\mathrm{\forall }s\in S,S=\{s_1,s_2,\cdots ,s_n\}$에 대해, 어떤 time step $t$에서의 value function $V_{\pi }^t(s)$는 그 다음 time step 에서 n개의 각 state가 가지는 value function $V_{\pi }^{t+1}(s_1),V_{\pi }^{t+1}(s_2),\cdots ,V_{\pi }^{t+1}(s_n)$의 선형결합으로 구해진다. 즉, $V_{\pi }^t(s)$를 구하는 문제는 $V_{\pi }^{t+1}(s_1),V_{\pi }^{t+1}(s_2),\cdots ,V_{\pi }^{t+1}(s_n)$를 구하는 n개의 부분 문제들로 분해될 수 있고 그 부분 문제들도 같은 방법으로 계속 분해가 가능하다. 다음은 m번 분해한 $n^m$개의 부분문제의 최적해 $V_{\pi }^m(s)$과 전체 문제의 최적해 $V_{\pi }^0(s)$의 관계를 나타낸다.

$$V_{\pi }^0(s_0)=\sum _{a_0\in A}\pi (a_0|s_0)R_{s_0}^{a_0}$$

$$+\sum _{i=0}^{m-2}({\gamma }^{i+1}\sum _{a_0\in A}\pi (a_0|s_0)\sum _{s_1\in S}{P}_{s_0{s}_1}^{a_0}\cdots \sum _{a_i\in A}\pi (a_i|s_i)\sum _{s_{i+1}\in S}{P}_{s_i{s}_{i+1}}^{a_i}\sum _{a_i\in A}\pi (a_{i+1}|s_{i+1})R_{s_{i+1}}^{a_{i+1}})$$

$$+{\gamma }^m\sum _{a_0\in A}\pi (a_0|s_0)\sum _{s_1\in S}{P}_{s_0{s}_1}^{a_0}\cdots \sum _{a_i\in A}\pi (a_{m-1}|s_{m-1})\sum _{s_m\in S}{P}_{s_{m-1}{s}_m}^{a_{m-1}}{V}_{\pi }^m(s)$$

이때, $n^m$개의 부분문제들의 최적해 $V_{\pi }(s_m)$들의 선형결합은 그 전체 문제의 최적해 $V_{\pi }(s_0)$가 된다. 결국 최하위 부분문제가 가진 최적해의 선형결합이 최상위 문제의 최적해가 되므로 "최적 부분 구조"를 만족한다.

그리고 위 수식 마지막 항에서 보이듯, $m$번 분해된 $n^m$개의 부분문제들은 사실 $n^{m-1}$번의 중복성을 지닌 n가지의 겹치는 부분문제들이다. $V_{\pi }^t(s)$의 부분문제들 $V_{\pi }^{t+1}(s_1),V_{\pi }^{t+1}(s_2),\cdots ,V_{\pi }^{t+1}(s_n)$은 $V_{\pi }^t(s_1),V_{\pi }^t(s_2),\cdots ,V_{\pi }^t(s_n)$를 계산하는데 모두 n번 중복되서 사용되기 때문이다. 따라서, "겹치는 부분문제"를 만족한다.

그런데 결국 모든 state의 $V_{\pi }^m(s)$를 모르면 $V_{\pi }^0(s)$ 을 못구하는것 아닌가? 하는 생각이 들 수도 있지만, 수식을 잘 살펴보면 $m$이 커질수록 상수항이 늘어나고 $V_{\pi }^m(s)$항의 값이 점점 줄어드는 것을 알수가 있다. $\sum _{a_0\in A}\pi (a_0|s_0)\sum _{s_1\in S}{P}_{s_0{s}_1}^{a_0}\cdots \sum _{a_i\in A}\pi (a_{m-1}|s_{m-1})\sum _{s_m\in S}{P}_{s_{m-1}{s}_m}^{a_{m-1}}{V}_{\pi }^m(s_m)$는 $s_0$ state에서 $m$번째 successor의 value function 기대값과 같다. 따라서 m이 커질수록 value function이 0인 terminal state에 도달할 확률이 높아지기 때문에(MDP의 정리), 그 값은 0에 수렴하게 되어있다. 더욱이 그 앞에 곱해지는 ${\gamma }^m$의 $\gamma$가 0과 가까운 값일 수록 그 과정은 더 빠르게 진행된다. 따라서, m이 커질수록 $V_{\pi }^0(s)$는 앞의 상수항에 수렴하게 되어있고 그 값이 문제의 최적해 $V_{\pi }(s)$가 된다. 그럼 상수항 부분은 무엇을 의미할까? 상수항을 전개하면 $s_0$부터 $m-1$번째 successor$s_{m-1}$까지 각 state의 immediate reward의 기대값이다. 즉, value function 의 정의와 부합하다.

따라서, Prediction은 동적 프로그래밍의 적용이 가능하고 그 알고리즘을 Iterative Policy Estimation 이라 한다.

Iterative Policy Estimation

우선 위에서 분해한 무한개의 부분문제들을 어떻게 효율적으로 연산할지를 생각해 보자, 우선 부분문제들의 중복성을 이용하기 위해 연산을 행렬로 확장하자.

$$V^{k+1}=R^{\pi }+\gamma P^{\pi }{V}^k$$

$V^k$는 $V^0$을 기준으로 $k$번 합성된 부분문제들의 해를 나타낸다. 여기선 $V^0$은 initial value function 행렬이고 우리가 가장 먼저 정의할 말단 부분문제들의 해다. $V^0$에서 연산을 m번 수행한 $V^m$은 $V^0$이 $V_{\pi }^m(s)$을 원소로 지닐때, $V_{\pi }^0(s)$를 원소로 가지는 행렬이다. 위에서 설명한 것처럼 m이 늘어날수록 $V^0$이 지닌 원소들 $V_{\pi }^m(s)$항의 값이 점점 줄어들게 되고 상수항이 늘어나면서 점점 어떠한 값에 수렴하게 되어있다. 하지만, 여기서 한가지 주의해야할 것은 우리가 처음 $V^0$을 가정했다는 것이다. $V_{\pi }^m(s)$항의 값이 m이 커질수록 작아지는 이유는 value function이 0인 terminal state에 도달할 가능성이 커져서 0에 수렴하게 되는 첫번째 이유와, ${\gamma }^m$이 앞에 곱해져있는 두번째 이유가 있었다. 그런데 만약 $V^0$의 원소중 terminal state의 value function값을 0이 아닌 숫자로 했다면. 그 자체로써 0으로 수렴하는것을 보장 못한다. 그 값은 아마 s에서 임의의 terminal state로 도달할때의 value function 기대값으로 수렴할 것이다. 그나마 이경우 $\gamma <1$ 라면 0으로 수렴시킬 수 있다.'

그래서, 항상 terminal state는 initial value function을 0으로 구성하는 것이 좋고 $\gamma$는 낮을수록 좋다. 하지만 $\gamma$는 문제에서 주어지는 값이므로 어쩔수가 없다.

Iterative Policy Estimation에서는 각 iteration마다 $n$개의 state에서 $a$개의 action을 통해 $n$개의 successor state로 가는 경우의 value function의 기대값을 계산하고 더한다. 따라서, 한번의 iteration은 $O(m{n}^2)$의 시간복잡도를 가진다. 여기서 iteration은 대부분 상수시간안에 종료 가능해서 m에 비해 n이 큰 문제일 수록 $O(n^3)$보다 훨신 적은 복잡도를 가진다.

• Control

다음을 만족하는 Optimal policy $\pi \ast$를 구하는 문제다.

$$\mathrm{\forall }s\in S,\mathrm{\forall }\pi \in \mathrm{\Pi },V_{\pi \ast }\ge V_{\pi }$$

위 수식에서 보듯control에는 prediction이 필요하다.

동적 프로그래밍 적용 가능성

Control은 기본적으로 $pi$에 따른 $V^{p}i$를 구하고 그에 맞추어 더 나은 ${\pi }^{\prime }$로 입력을 변경해가는 문제다. 다음 input으로 주어질 ${\pi }^{\prime }$는 어떤 state에 대한 정책으로 가장 높은 value function을 지니는 successor state들로 갈 확률이 가장 높은 action을 선택하게한다. 당장 최고의 결과를 기대할 수 있는 greedy한 선택이다.

$${\pi }^{\prime }=greedy(V_{\pi }))$$

그러나 이러한 각 iteration의 greedy한 선택은 전체 선택에 있어서 최선의 결과를 가져온다.

즉, 부분문제들의 최적해로 전체문제의 최적해를 구할수 있는 "최적 부분 문제"를 만족한다.

그리고 각 iteration의 개선된 policy로 구한 $V^{\pi }$는 다음 iteration에서 중복해서 사용되므로 "겹치는 부분 문제"를 만족한다. 게다가 각각의 iteration의 prediction에는 동적 프로그래밍인 iterative policy estimation을 사용 가능하다. 이렇듯 각 iteration별로 greedy한 선택을해서 policy를 개선해나가는 동적 프로그래밍 기법을 Policy Improvement라고 한다.

Policy Improvement

policy improvement에서 중요한 포인트는 iterative policy estimation의 iteration한번에 policy improve를 한번씩 수행한다는 것이다. 초기 $V^0$을 셋팅할때 각 $V_{\pi }(s)$의 대소관계에 맞게 주거나 적어도 균일하게 준다면, iteration을 한번 수행할때마다 $V_{\pi }(s)$의 대소관계는 점점 명확해지게 되어있다. policy의 개선은 올바른 $V_{\pi }(s)$의 대소관계만 알면 되기 때문에 한번 수행에 따른 결과로 충분히 최선의 policy를 결정할 수 있다. 그리고 그러한 개선된 policy로 iteration을 수행하면 이전 policy로 iteration을 수행할때보다 $V_{\pi }(s)$의 대소관계가 더욱 명확해져서 $V_{\pi }^{\ast }(s)$로 더욱 빠르게 나아가게 된다. 그리고 알다시피 $V_{\pi }^{\ast }(s)$가 주어지면 optimal policy를 알수가 있다. 따라서 Iterative Policy Estimation와 같이 한번의 iteration에 $O(m{n}^2)$의 시간 복잡도를 가진다.