Dynamic Programming In RL (1)

이전 포스팅에서 강화학습이 무엇인지 살펴 보았고, 이를 MDP로 정의할 수 있음을 살펴 보았습니다. MDP로 정의하는 이유는 가치 함수를 이용하여 순차적 의사결정을 하는 강화학습 문제를 풀기위함이었습니다. 즉 우리가 강화학습문제를 해결하기 위해선 가치함수의 값을 알고 있어야 합니다.

가치함수를 추정하는 방법은 상태공간($\mathcal{S}$)의 크기에 따라서 tabular method와 approximation method 두 가지 방법이 존재합니다. Tabular method는 기본적으로 각 상태에 대한 가치함수 값을 모두 저장하고 있습니다. 이에 따라 상태 공간 크기가 너무 크면 각 상태에 대한 가치함수의 값을 저장하는데 한계가 있어 tabular method를 적용하기 어렵고, 해당 경우에는 approximation method를 적용합니다. 앞으로 3~4개의 포스팅에 거쳐서 tabular method를 소개하고, 이후에 이어질 포스팅들에서 approximation method를 다루려고 합니다. 이번 포스팅에서는 가치함수를 추정하는 방법 중 역사적으로 가장 유의미한 dynamic programming (DP)에 대해서 살펴보겠습니다.

Dynamic Programming (DP)

DP?

DP (동적 계획법)는 복잡한 문제를 여러 개의 작은 문제로 나누어 푸는 방법을 말합니다. 간단한 예제 하나면 어느정도 DP에 대해 감을 잡을 수 있습니다. 피보나치 수열을 예를 들겠습니다. 먼저 피보나치수열은 $$1,1,2,3,5,\cdots$$와 같은 수열로 $$f(n)=f(n-1)+f(n-2)\text{, }n\ge 3\text{, }f(1)=f(2)=1$$로 정의할 수 있습니다. 피보나치 수열을 컴퓨터로 계산하고자 합니다.

Figure 1: Fibonacci Numbers

좌측 그림은 단순하게 위에서 피보나치 수열을 정의한대로 계산한 것으로 $f(5)$를 계산할 때, $f(1)$, $f(2)$, $f(3)$가 중복호출되는 것을 확인할 수 있습니다. 우측 그림은 동적 계획법을 이용하여 피보나치 수열을 계산한 것입니다. 먼저 메모리를 할당한 후 결과를 저장하는 방식을 취합니다. 그래서 우측 마디의 $f(3)$을 계산할 때는 좌측 마디 작은 문제를 해결해가며 메모리에 저장한 결과를 호출함으로써 효율적으로 결과를 계산하는 것을 확인 할 수 있습니다.

강화학습에서의 DP

반복하여 말하면 강화학습의 핵심은 가치함수를 이용하여 의사결정을 하는 것입니다. 주어진 상태공간 및 행동공간에 대하여 가치함수를 계산하고 나면 최적의 정책을 결정하고, 최적의 의사결정을 할 수 있게 됩니다. 강화학습에서는 가치함수, 즉, 벨만의 방정식을 효율적으로 계산하기위하여 사용됩니다. 단, DP는 model-based 방법에만 적용가능합니다. Model을 안다는 것은 상태전이확률인 $\mathbb{P}(s',r|s,a)$를 안다는 것과 같은 말입니다. 이어서 순서대로 살펴보겠습니다. 

Policy Evaluation (Prediction)

처음으로 DP를 이용하여 계산할 것은 상태가치함수입니다. 상태가치함수를 계산할 때 어떤 주어진 정책 $\pi$에 대하여 계산하기 때문에 가치평가 (policy evaluation)이라고 하며 이를 prediction이라고 부르기도 합니다. 가치평가를 하기 앞서 벨만 방정식을 리뷰해보면 아래와 같습니다. $$\begin{align*}v_{\pi}(s)=&\mathbb{E}_{\pi}\left[\left.R_{t+1}+\gamma v_{\pi}(S_{t+1})\right|S_{t}=s\right]\\=&\sum_{a}\pi(a|s)\sum_{s',r}\mathbb{P}(s',r|s,a)\left[r+\gamma v_{\pi}(s')\right]\end{align*}$$ 결국 위 식은 $v_{\pi}$를 정확하게 알 수 없기 때문에 계산할 수 없습니다. DP를 이용하여 다음과 같이 업데이트 하는 방식으로 계산할 수 있습니다. $$v_{k+1}(s)=\sum_{a}\pi(a|s)\sum_{s',r}\mathbb{P}(s',r|s,a)\left[r+\gamma v_{k}(s')\right]\text{, }\forall s\in\mathcal{S}$$ 최초 $k=0$ 일 때 $v_{0}$은 임의의 값으로 초기화 한뒤 위 업데이트를 여러번 반복하면, 즉, $k\rightarrow\infty$이면 $v_{\pi}$로 수렴합니다. 이때  1회 업데이트 되는 단위를 sweep이라고 부릅니다. DP는 $s$에 대한 가치함수를 업데이트 하기 위해서 다음 상태 $s'$ 가치 함수 결과를 이용합니다. 이렇게 현재 상태를 업데이트 할 때 다음 상태의 가치 함수 결과를 이용하는 방식을 bootstrap 업데이트라고 부릅니다.

실제로 DP를 적용하여 계산하기 위해선 2개의 array가 필요합니다. 각각에는 현재 상태 가치함수와 직전 상태 가치함수를 저장하는 것입니다. 2개의 array를 이용하여 상태가치함수를 업데이트를 할 때, 두 가지 방법을 선택할 수 있습니다.

1. (일반적인 방법) $v_{k+1}(s)$가 모든 $s$에 대하여 업데이트 될 때까지 $v_{k}(s)$를 이용한다.
2. (In-place 방법) $v_{k+1}(s)$가 업데이트 될 때, 업데이트가 이뤄진 상태 $s$는 $v_{k+1}(s)$를 적용하고, 아닌경우 $v_{k}(s)$를 적용한다.

위 두 가지 방법 모두 알고리즘을 충분히 반복하면 수렴하는 것으로 알려져 있고, 보통은 in-place 방법이 수렴속도가 빠르다고 합니다. 이어서 Policy Evaluation의 pseudocode를 살펴보겠습니다.

Figure 2: Pseudocode, Policy Evaluation

Policy Improvement

우리가 앞선 Policy Evaluation에서는 주어진 정책 $\pi$를 평가했습니다. 즉 정책 $\pi$를 이용했을 때 상태의 가치 함수를 계산한 것 입니다. 당연하게도 앞선 정책 $\pi$가 최적임을 보장할 수 없기 때문에 개선할 필요가 있습니다. 정책 평가 결과 기반 정책을 개선하는 것을 정책 개선 (Policy Improvement)이라고 부릅니다. 정책을 개선할 때 가장 좋은 방법은 평가된 정책과는 다르게 행동해보는 것 입니다. 즉 다른 정책 $\pi'$ 아래의 행동가치함수가 $\pi$ 아래 상태가치함수보다 크다면 정책 $\pi$는 개선의 여지가 있다고 할 수 있습니다. 또한 policy improvement theorem에 의하여 $\pi'\ge\pi$라고 말할 수 있습니다.

Policy Improvement Theorem

주어진 $\pi$와 $\pi'$와 모든 $s\in\mathcal{S}$에 대하여 $$q_{\pi}(s,\pi'(s))\ge v_{\pi}(s)$$가 성립하면 $\pi'$은 $\pi$ 만큼 좋은 정책이거나 나은 정책이다. 즉, 모든 상태 $s\in\mathcal{S}$에 대하여 $$v_{\pi'}(s)\ge v_{\pi}(s)$$가 성립한다.

Policy Improvement Theorem은 가볍게 증명해 볼 수 있습니다. $$\begin{align*}v_{\pi}(s)\le&q_{\pi}(s,\pi'(s))\\ &=\mathbb{E}\left[\left.R_{t+1}+\gamma v_{\pi}(S_{t+1})\right|S_{t}=s,A_{t}=\pi'(s)\right]\\ &=\mathbb{E}_{\pi'}\left[\left.R_{t+1}+\gamma v_{\pi}(S_{t+1})\right|S_{t}=s\right]\text{ }\left(\because\pi'(s)\text{ is deterministic}\right)\\ &\le\mathbb{E}_{\pi'}\left[\left.R_{t+1}+\gamma q_{\pi}(S_{t+1},\pi'(S_{t+1}))\right|S_{t}=s\right]\\ &=\mathbb{E}_{\pi'}\left[\left.R_{t+1}+\gamma \mathbb{E}_{\pi'}\left[\left.R_{t+1}+\gamma v_{\pi}(S_{t+2})\right|S_{t+1},A_{t+1}=\pi'(S_{t+1})\right]\right|S_{t}=s\right]\\ &=\mathbb{E}_{\pi'}\left[\left.R_{t+1}+\gamma R_{t+2}+\gamma^{2} v_{\pi}(S_{t+2})\right|S_{t}=s\right]\\ &\le\mathbb{E}_{\pi'}\left[\left.R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\gamma^{3}v_{\pi}(S_{t+3})\right|S_{t}=s\right]\\ &\vdots\\ &\le\mathbb{E}_{\pi'}\left[\left.R_{t+1}+\gamma R_{t+2}+\gamma^{2} R_{t+3}+\gamma^{3}R_{t+4}+\cdots\right|S_{t}=s\right]\\ &=v_{\pi'}(s)\end{align*}$$

이제 문제는 한가지입니다. 바로 어떻게 현정책 $\pi$보다 조금더 나은 정책 $\pi'$을 고려하는가 입니다. 아주 간단하게 $\pi(s)$, $\forall s\in\mathcal{S}$에 대하여 greedy하게 행동을 취하면 됩니다. 앞선 포스팅에서 행동가치함수를 상태가치함수를 이용하여 나타낼 수 있었습니다. 이를 이용하면 행동가치함수 기반 greedy한 행동을 얻을 수 있습니다. $$\begin{align*}\pi'(s)&=\underset{a}{\operatorname{argmax}}q_{\pi}(s,a)\\&=\underset{a}{\operatorname{argmax}}\mathbb{E}\left[\left.R_{t+1}+\gamma v_{\pi}(S_{t+1})\right|S_{t}=s,A_{t}=a\right]\\&=\underset{a}{\operatorname{argmax}}\sum_{s,'r}\mathbb{P}(s',r|s,a)\left[r+\gamma v_{\pi}(s')\right]\end{align*}$$ 위 방법을 통하여 행동가치함수기반 더 나은 정책을 찾을 수 있고, 이런 과정을 정책 개선 (Policy Improvement)이라고 부릅니다.

결국 정책 평가와 정책 개선을 반복적으로 하다보면 언젠가 $\pi=\pi'$에 도달할 것 입니다. (자세한 내용은 다음 포스팅에서 다루겠습니다.) $\pi=\pi'$ 상황아래 상태가치함수를 다시 정의해보면 아래를 얻을 수 있습니다. $$\begin{align*}v_{\pi'}(s)&=\underset{a}{\operatorname{max}}q_{\pi'}(s,a)\\&=\underset{a}{\operatorname{max}}\mathbb{E}\left[\left.R_{t+1}+\gamma v_{\pi'}(S_{t+1})\right|S_{t}=s,A_{t}=a\right]\\&=\underset{a}{\operatorname{max}}\sum_{s',r}\mathbb{P}(s',r|s,a)\left[r+\gamma v_{\pi'}(s')\right]\end{align*}$$ 마지막 식을 보면 벨만의 최적 방정식임을 알 수 있습니다. 이에 따라 $\pi$와 $\pi'$ 모두 최적 정책임이 보장됩니다.

위 결론은 정책 평가와 정책 개선이 반복적으로 이루어져 $\pi=\pi'$가 된다는 대전제로 시작했습니다. 따라서 정책 평가와 개선을 반복 시키는 알고리즘이 어떤게 있는지 살펴보는 일만 남았습니다.

쓰다 보니 양이 너무 많아져서 DP 2부로 내용을 나누려고합니다. 조만간 2부로 찾아뵙겠습니다 :)

References

• Sutton, Richard S., and Andrew G. Barto. Introduction to reinforcement learning. Vol. 2. No. 4. Cambridge: MIT press, 1998.