2 분 소요

이전 포스트에 이어 Sutton의 책을 읽어가보자. 늘 그렇듯 책에 생략된 내용에 대해서는 자료를 찾거나 직접 계산 또는 증명해서 채워나갈 것이다. dynamic programming은, 이 책에서는 가장 기본적인 강화학습 알고리즘으로 소개된다. 환경모델이 완전히 주어진 상태에서 쓸 수 있는 가장 기본적인 알고리즘이라고 할만하다.

공부를 하면 할수록 강화학습의 fundamental이 되는 이 계산들이나 정리들이 꽤 만만치 않음을 느낀다. 이런 어려움은 나만 겪는 것이 아니라고도 생각해본다. 사람들이 때로, 아주 간단한 식에도 나처럼 심각하게 고민한 것을 몇 번 봤다.

Sutton의 3장은 꽤 책의 내용과 비슷하게 썼다. 하지만 내가 관심있는 수학적인 부분은 책에 자세하게 설명되지 않고 있기 때문에 책 외의 내용이 많이 적힐 예정이다. 식번호는 책의 것을 그대로 따랐으나, 절은 다르게 썼다.

이 포스트에서 꼭 다루고자 하는 것은 Bellman operator와 contraction principle로 policy evaluation이 유효한 것임을 증명하는 것이다. 이에 관해서는 이미 Ishwin Rao나 Carl Fredricksson이 잘 써놨는데 아마 조금씩 참고할 것 같다.

4. Dynamic Programming

4.1 Bellman optimal equation revisited

Bellman optimal equation도 다시 적어보자. optimal value $v_\ast$, $q_\ast$에 대한 optimal equation들은 다음과 같다.

\[\begin{align*} v_\ast(s) &=\max_a\mathbb E\left[R_{t+1}+\gamma v_\ast(S_{t+1})|S_t=s, A_t=a\right]\\ &=\max_a\sum_{s',r}p(s',r|s,a)\left[r+\gamma v_\ast(s')\right]\tag{4.1}\\ q_\ast(s,a) &=\mathbb E\left[R_{t+1}+\gamma\max_{a'}q_\ast(S_{t+1},a')|S_t=s, A_t=a\right]\\ &=\sum_{s',r}p(s',r|s,a)\left[r+\gamma\max_{a'}q_\ast(s',a')\right]\tag{4.2} \end{align*}\]

4.2 Bellman equation revisited

책의 4.1절에 가장 먼저 보이는 식은 $v$에 대한 Bellman equation

\[\begin{align*} v_\pi(s) &=\mathbb E_\pi\left[G_t|S_t=s\right]\\ &=\mathbb E_\pi\left[R_{t+1}+\gamma G_{t+1}|S_t=s\right]\\ &=\mathbb E_\pi\left[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s\right]\tag{4.3}\\ &=\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)\left[r+\gamma v_\pi(s')\right]\tag{4.4} \end{align*}\]

이다. 첫번째 줄과 두번째줄이 같다는 것, 그리고 그것이 네번째 줄과 같다는 것은 이전 포스트에서 증명했고, 그것을 Bellman equation이라고 했었다. 그러나 세번째 줄은 조금 뜬금없어보인다. 그래, 의미상으로는 당연히 그럴 것 같은데 왜 그런 지는 그렇게까지 쉽게 설명되지 않는다. 그러니, 세번째 줄로부터 시작하여 네번째 줄로 도출되는 계산을 해보려 한다.

다음과 같다.

\[\begin{align*} &\mathbb E\left[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s\right]\\ =&\sum_a\pi(a|s)\mathbb E\left[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s,A_t=a\right]\\ =&\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)\mathbb E\left[R_{t+1}+\gamma v_\pi(S_{t+1})|S_t=s,A_t=a,R_{t+1}=r,S_{t+1}=s'\right]\\ =&\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)\mathbb E\left[r+\gamma v_\pi(S_{t+1})|S_{t+1}=s'\right]\\ =&\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)\mathbb E\left[r+\gamma v_\pi(s')\right]\\ \end{align*}\]

4.3 policy evaluation

책의 4.1절에서 다루는 것은, 주어진 정책 $\pi$에 대하여 이에 대한 가치함수 $v_\pi$를 얻어내는 것이다. 즉 정책을 평가하는(policy evaluation, prediction problem) 것으로서 DP를 포함한 모든 강화학습에서의 주요한 두 과정 중 하나이다.

가치함수를 얻어내는 방식은 식 (4.4)을

\[v_{k+1}(s)=\sum_a\sum_{s',r}p(s',r|s,a)\left[r+\gamma v_k(s')\right]\tag{4.5}\]

와 같이 변형해 가치함수들의 수열 $v_0, v_1, v_2, \cdots$을 만들어나가는 것이다. $v_0$가 임의의 함수(e.g. $v_0\equiv0$)이고 $v_\pi$가 존재한다는 조건 하에 수열 $\{v_i\}$가 $v_\pi$로 수렴하는 것이 알려져 있고, 이를 증명하려 한다.

4.4 Bellman operation

먼저 할 것은 식 (4.4) 버전의 Bellman equation을 Bellman operation으로 표현하는 것이다. 기본적으로 Carl Fredricksson의 자료를 따라갔다.

많은 계산들, 특히 marginalization이 포함되어 있으므로 천천히 계산하기 위해 일단 두 값 $A$, $B$로 분리하면

\[\begin{align*} v_\pi(s) &=\sum_a\pi(a|s)\sum_{s',r}p(s',r|s,a)\left[r+\gamma v_\pi(s')\right]\\ &=\sum_{a,s',r}r\pi(a|s)p(s',r|s,a)+\gamma\sum_{a,s',r}v_\pi(s')\pi(a|s)p(s',r|s,a)\\ &=A+\gamma B \end{align*}\]

이다. 먼저 $A$를 계산하면

\[\begin{align*} A&=\sum_{a,s',r}r\pi(a|s)p(s',r|s,a)\\ &=\sum_{a,s',r}r\frac{P\left(S_t=s,A_t=a\right)}{P\left(S_t=s\right)}\times \frac{P\left(S_t=s,A_t=a,S_{t+1}=s',R_{t+1}=r\right)}{P\left(S_t=s,A_t=a\right)}\\ &=\sum_r r\sum_{a,s'}\frac{P\left(S_t=s,A_t=a,S_{t+1}=s',R_{t+1}=r\right)}{P\left(S_t=s\right)}\\ &=\sum_r r\frac{P\left(S_t=s,R_{t+1}=r\right)}{P\left(S_t=s\right)}\\ &=\sum_r r{P\left(R_{t+1}=r|S_t=s\right)}\\ &=\mathbb E\left[R_{t+1}|S_t=s\right]\\ &=r_\pi(s) \end{align*}\]

이다. 두번째 줄은 두 표현 $\pi(\cdot|\cdot)$, $p(\cdot,\cdot|\cdot,\cdot)$ 정의, 세번째 줄은 통분, 네번째 줄은 두 변수에 $a$, $s’$에 대한 marginalization, 다섯번째 줄과 여섯번째 줄은 각각 조건부확률과 조건부기댓값의 정의에 의해 계산되었다. 마지막 줄은 새롭게 $r_\pi$라는 함수를 정의한 것이다.

다음으로 $B$를 계산하는데 통분과 같은 과정은 빠르게 넘어가면서 계산해보려 한다. 계산해보면

\[\begin{align*} B &=\sum_{a,s',r}v_\pi(s')\pi(a|s)p(s',r|s,a)\\ &=\sum_{s'}v_\pi(s')\sum_{a,r}P\left(S_t=s,A_t=a,S_{t+1}=s',R_{t+1}=r|S_t=s\right)\\ &=\sum_{s'}v_\pi(s')P\left(S_{t+1}=s'|S_t=s\right) \end{align*}\]

와 같다. 두번째 줄은 기호의 정의와 통분, 세번째 줄은 marginalization에 의해 계산되었다. 마지막 식은 $\mathbb E\left[S_{t+1}|S_t=s\right]$로도 쓸 수 있지만 위의 계산결과까지만 사용할 것이다. 즉 Bellman equation을 다시 쓰면

\[v_\pi(s)=r_\pi(s)+\gamma\sum_{s'}v_\pi(s')P\left(S_{t+1}=s'|S_t=s\right)\]

이 된다. 이전 포스트에도 언급했고, 책의 4장에도 다시 강조되지만 Bellman equation의 본질은 연립방정식, 그것도 선형(affine)연립방정식이다. state space $\mathcal S$를 $\mathcal S=\{s_1,\cdots,s_n\}$으로 두고 위 식을 다시 쓰면 모든 $i$에 대하여 ($1\le i\le n)$

\[v_\pi(s_j)=r_\pi(s_i)+\gamma\sum_{i=1}^nv_\pi(s_i)P\left(S_{t+1}=s_i|S_t=s_j\right)\]

이 성립하는 것이다. 선형(affine)방정식이니, 벡터와 행렬로 표현하면 가장 적절하다. 행렬 $P$를

\[P= \begin{bmatrix} P\left(S_{t+1}=s_1|S_t=s_1\right)&\cdots&P\left(S_{t+1}=s_1|S_t=s_n\right)\\ \vdots&\ddots&\vdots\\ P\left(S_{t+1}=s_n|S_t=s_1\right)&\cdots&P\left(S_{t+1}=s_n|S_t=s_n\right) \end{bmatrix}\]

로 정의하고 벡터 $v_\pi$, $r_\pi$을

\[v_\pi= \begin{bmatrix} v_\pi(s_1)\\ \vdots\\ v_\pi(s_n) \end{bmatrix} ,\quad r_\pi= \begin{bmatrix} r_\pi(s_1)\\ \vdots\\ r_\pi(s_n) \end{bmatrix}\]

으로 두면 Bellman equation은

\[v_\pi=r_\pi+Pv_\pi\]

가 된다. 이런 관점에서 Bellman operation $\mathcal T^\pi$를

\[\mathcal T^\pi(v)=r_\pi+Pv\]

로 정의할 수 있고 Bellman equation도 간단히 $v_\pi=\mathcal T^\pi(v_\pi)$로 쓰일 수 있다. 그리고 policy evaluation 식 (4.5)도

\[v_{k+1}=\mathcal T^\pi(v_k)\tag{4.5*}\]

로 표현될 수 있다.

댓글남기기