MDP에서의 동적 프로그래밍 기법
동적 프로그래밍(Dynamic Programming)
문제해결을 위해 문제를 여러개의 부분 문제로 분해하여 해결하는 접근법.
1. 최적 부분 구조 (Optimal Substructure)
전체 문제의 최적해를 부분 문제의 최적해들로 구할 수 있는 경우.
2. 겹치는 부분 문제 (Overlapping Subproblems)
동일한 부분 문제들이 반복해서 나타나는 경우(Recursive)
= 부분 문제의 최적해를 캐쉬하고 재사용할 수 있는 경우
MDP에서의 문제 : Prediction & Control.
• Prediction
주어진 policy로 value function값을 구하는 것.
$$V^{\pi}=\left(I-\gamma P^{\pi} \right)^{-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'\in S}P_{ss'}^{a}V_{\pi}(s')$$
여기서, $s'$는 S의 모든 원소가 되기 때문에, $s, \forall s \in S, S=\left\{s_1, s_2, \cdots, s_n \right\}$에 대해, 어떤 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}\left(\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}}\right)$$
$$+\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(mn^2)$의 시간복잡도를 가진다. 여기서 iteration은 대부분 상수시간안에 종료 가능해서 m에 비해 n이 큰 문제일 수록 $O(n^3)$보다 훨신 적은 복잡도를 가진다.
• Control
다음을 만족하는 Optimal policy $\pi\ast$를 구하는 문제다.
$$\forall s \in S, \forall \pi \in \Pi,V_{\pi\ast}\ge V_{\pi}$$
위 수식에서 보듯control에는 prediction이 필요하다.
동적 프로그래밍 적용 가능성
Control은 기본적으로 $pi$에 따른 $V^pi$를 구하고 그에 맞추어 더 나은 $\pi'$로 입력을 변경해가는 문제다. 다음 input으로 주어질 $\pi'$는 어떤 state에 대한 정책으로 가장 높은 value function을 지니는 successor state들로 갈 확률이 가장 높은 action을 선택하게한다. 당장 최고의 결과를 기대할 수 있는 greedy한 선택이다.
$$\pi'=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(mn^2)$의 시간 복잡도를 가진다.
댓글
댓글 쓰기