Just Fighting
[강화학습] 벨만 방정식 본문
행동가치 함수를 시간구간 $[t, t+n-1]$에서 전개한다.
\begin{align*}
Q^{\pi}(X_t, u_t) &= E_{\tau_{u_{t+1}:u_T} \sim p(\tau_{u_{t+1}:u_T})} \left [ \sum_{k=t}^{T}\gamma^{k-t}r(X_k, u_k)|X_t, u_t \right ] \\
&= \int_{\tau_{u_{t+1}:u_T}} (r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1} + \sum_{k=t+n}^{T}\gamma^{k-t}r(X_k, u_k))p(\tau_{u_{t+1}:u_T}|X_t, u_t)d \tau_{u_{t+1}:u_T}
\end{align*}
* $ t+n \leq T $이고, $r_i = r(x_i, u_i)$
위식을 두 개의 적분식으로 분리한다.
\begin{align*} Q^{\pi}(X_t, u_t) &= Q_1 + Q_2 \\ &= \int_{\tau_{x_{t+1}:u_T}} (r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1}) p(\tau_{x_{t+1}:u_T}|X_t, u_t) d \tau_{x_{t+1}:u_T} \\ &\qquad + \int_{\tau_{x_{t+1}:u_T}} (\sum_{k=t+n}^{T} \gamma^{k-t}r(X_k, u_k)) p(\tau_{x_{t+1}:u_T}|X_t, u_t) d \tau_{x_{t+1}:u_T} \end{align*}
$Q_1$을 정리해보자.
확률의 연쇄 법칙에 의해
2023.05.21 - [분류 전체보기] - [강화학습] 가치함수 - 확률의 연쇄법칙 참고
\begin{align*}
p(\tau_{x_{t+1}:u_T}) &= p(\tau_{x_{t+1}:x_{t+n}},\tau_{u_{t+n}:u_T}|X_t, u_t) \\
&= p(\tau_{u_{t+n}:u_T}|X_t, u_t, \tau_{x_{t+1}:x_{t+n}}) p(\tau_{x_{t+1}:x_{t+n}}|X_t, u_t)
\end{align*}
위 식을 $Q_1$식에 대입하면,
\begin{align*} Q_1 &= \int_{\tau_{x_{t+1}:u_T}} (r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1}) p(\tau_{x_{t+1}:u_T}|X_t, u_t) d \tau_{x_{t+1}:u_T} \\ &= \int_{\tau_{x_{t+1}:x_{t+n}}} \int_{\tau_{u_{t+n}:u_T}} (r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1}) p(\tau_{u_{t+n}:u_T}|X_t, u_t, \tau_{x_{t+1}:x_{t+n}}) d \tau_{u_{t+n}:u_T} \\ &\qquad \qquad p(\tau_{x_{t+1}:x_{t+n}}|X_t, u_t) d \tau_{x_{t+1}:x_{t+n}} \\ &= \int_{\tau_{x_{t+1}:x_{t+n}}} [ \int_{\tau_{u_{t+n}:u_T}} p(\tau_{x_{t+n}:u_T}|X_t, u_t, \tau_{x_{t+1}:x_{t+n}}) d \tau_{u_{t+n}:u_T}] \\ &\qquad \qquad (r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1}) p(\tau_{x_{t+1}:x_{t+n}}|X_t, u_t) d \tau_{x_{t+1}:x_{t+n}} \\ &= \int_{\tau_{x_{t+1}:x_{t+n}}} (r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1}) p(\tau_{x_{t+1}:x_{t+n}}|X_t, u_t) d \tau_{x_{t+1}:x_{t+n}} \end{align*}
* 3번째 줄의 대괄호 안의 식의 값은 1이니까 !
$Q_2$를 정리해보자.
\begin{align*} Q_2 &= \int_{\tau_{x_{t+1}:u_T}} (\sum_{k=t+n}^{T} \gamma^{k-t}r(X_k, u_k)) p(\tau_{x_{t+1}:u_T}|X_t, u_t) d \tau_{x_{t+1}:u_T} \\ &= \int_{\tau_{x_{t+1}:x_{t+n}}} \gamma^n [ \int_{\tau_{u_{t+n}:u_T}} (\sum_{k=t+n}^{T} \gamma^{k-t}r(X_k, u_k)) p(\tau_{u_{t+n}:u_T}|X_t, u_t, \tau_{x_{t+1}:x_{t+n}}) d \tau_{u_{t+n}:u_T} ] \\ &\qquad \qquad p(\tau_{x_{t+1}:x_{t+n}}|X_t, u_t) d \tau_{x_{t+1}:x_{t+n}} \\ &= \int_{\tau_{x_{t+1}:x_{t+n}}} \gamma^n [ \int_{\tau_{u_{t+n}:u_T}} (\sum_{k=t+n}^{T} \gamma^{k-t}r(X_k, u_k)) p(\tau_{u_{t+n}:u_T}|X_{t+n}) d \tau_{u_{t+n}:u_T} ] \\ &\qquad \qquad p(\tau_{x_{t+1}:x_{t+n}}|X_t, u_t) d \tau_{x_{t+1}:x_{t+n}} \end{align*}
*$p(\tau_{u_{t+n}:u_T}|X_t, u_t, \tau_{x_{t+1}:x_{t+n}})$가 $p(\tau_{u_{t+n}:u_T}|X_{t+n})$이 된 이유는 마르코프 시퀀스 가정을 사용한 것.
상태가치 함수 식은 다음과 같으며, $Q_2$는 다음과 같이 표현할 수 있다.
$$V^{\pi}(X_t) = \int_{\tau_{u_t:u_T}} (\sum_{k=t}^{T}\gamma^{k-t}r(X_k, u_k))p(\tau_{u_t:u_T}|X_t)d \tau_{u_t:u_T}$$
$$ Q_2 = \int_{\tau_{x_{t+1}:x_{t+n}}} \gamma^n V^{\pi}(X_{t+n}) p(\tau_{x_{t+1}:x_{t+n}}|X_t, u_t) d \tau_{x_{t+1}:x_{t+n}} $$
따라서, 행동가치 식은 다음과 같다.
\begin{align*}Q^{\pi}(X_t, u_t)&=\int_{\tau_{x_{t+1}:x_{t+n}}}[(r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1})+\gamma^nV^{\pi}(X_{t+n})] \\ &\qquad \qquad p(\tau_{x_{t+1}:x_{t+n}}|X_t, u_t)d \tau_{x_{t+1}:x_{t+n}}\\ &=E_{\tau_{x_{t+1}:x_{t+n}} \sim p(\tau_{x_{t+1}:x_{t+n}}|x_t,u_t)}[r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1}+\gamma^nV^{\pi}(X_{t+n})] \end{align*}
* 여기서 $\tau_{u_t:x_{t+n}} = (u_t, x_{t+1}, u_{t+1}, \cdots, x_{t+n})$는 어떤 상태변수 $x_t$에서 시작해 그로부터 정책 $\pi$로 생성되는 궤적
위의 행동가치 식을 아래 상태가지 함수 $V^\pi(x_t)$에 대입해보자
\begin{align*}V^{\pi} (X_t) &= \int_{u_t} Q^{\pi} (X_t, u_t) \pi (u_t|X_t) d u_t \\ &= E_{u_t \sim \pi (u_t|x_t)} [Q^{\pi} (X_t, u_t)] \end{align*}
\begin{align*}V^{\pi} (X_t) &= \int_{u_t} Q^{\pi} (X_t, u_t) \pi (u_t|X_t) d u_t \\ &= \int_{u_t} [\int_{\tau_{u_{t+1}:x_{t+n}}}[(r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1})+\gamma^nV^{\pi}(X_{t+n})]p(\tau_{u_{t+1}:x_{t+n}}|X_t, u_t)d \tau_{x_{t+1}:x_{t+n}}]\pi (u_t|X_t) d u_t \\ &= \int_{\tau_{u_{t+1}:x_{t+n}}} [(r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1})+\gamma^nV^{\pi}(X_{t+n})]p(\tau_{u_t:X_{t+n}|X_t})d\tau_{u_t:X_{t+n}} \\ &= E_{\tau_{u_t:X_{t+n}}\sim p(\tau_{u_t:X_{t+n}}|X_t))}[r_t + \gamma r_{t+1} + \cdots + \gamma^{n-1} r_{t+n-1})+\gamma^nV^{\pi}(X_{t+n})]\end{align*}
* 여기서 $\tau_{u_t:x_{t+n}} = (u_t, x_{t+1}, u_{t+1}, \cdots, x_{t+n})$는 어떤 상태변수 $x_t$에서 시작해 그로부터 정책 $\pi$로 생성되는 궤적
여기서 시간구간 $n=1$로 하면, 상태 가치 함수는 다음과 같다.
\begin{align*}V^{\pi}(X_t)&=\int_{u_t}\pi(u_t|X_t)[\int_{X_{t+1}}[r(X_t,u_t)+ \gamma V^{\pi}(X_{t+1})]p(X_{t+1}|X_t, u_t)dx_{t+1}]du_t\\ &=E_{u_t\sim \pi(u_t|X_t)}[E_{x_{t+1}\sim p(x_{t+1}|x_t,u_t)}[r(X_t,u_t)+\gamma V^\pi(X_{t+1})]] \end{align*}
위 식에서 $r(X_t, u_t)$는 $X_{t+1}$의 함수가 아니기 때문에 아래와 같이 표현할 수 있다.
\begin{align*}V^{\pi}(X_t)&=E_{u_t\sim \pi(u_t|X_t)}[r(X_t,u_t)+E_{x_{t+1}\sim p(x_{t+1}|x_t,u_t)}[\gamma V^\pi(X_{t+1})]] \end{align*}
이 식을 벨만 방정식(Bellma equation)이라고 한다.
벨만 방정식은 현재 상태변수의 가치와 다음 시간스텝의 상태변수의 가치와의 관계를 나타내는 식이다.
위 식에서 T가 무한 구간이라면 상태가치 함수는 시불변 함수가 되므로 좌변과 우변에 있는 상태가치 함수는 동일하게 된다.
이번에는 시간구간 $n=1$일 때의 행동가치 함수를 다뤄보자.
\begin{align*} Q^\pi(X_t, u_t) &= \int_{x_{t+1}}[r(x_t, u_t)+\gamma V^\pi(X_{t+1})]p(X_{t+1}|x_t, u_t)dX_{t+1}\\ &= E_{X_{t+1}\sim P(X_{t+1}|X_t, u_t)}[r(X_t, u_t)+\gamma V^\pi (X_{t+1})] \\ &= r(X_t, u_t) + E_{X_{t+1}\sim P(X_{t+1}|X_t, u_t)}[\gamma V^\pi (X_{t+1})] \end{align*}
위 식에 상태 가치 함수를 대입하면, 다음과 같이 표현할 수 있다.
$$V^{\pi} (X_t) = \int_{u_t} Q^{\pi} (X_t, u_t) \pi (u_t|X_t) d u_t$$
\begin{align*} Q^\pi(X_t, u_t) &= \int_{x_{t+1}}[r(x_t, u_t)+\gamma \int_{u_t} Q^{\pi} (X_{t+1}, u_{t+1}) \pi (u_{t+1}|X_{t+1}) d u_{t+1}]p(X_{t+1}|x_t, u_t)dX_{t+1}\\ &= E_{x_{t+1}\sim p(X_{t+1}|x_t, u_t)}[E_{u_{t+1}\sim \pi (u_{t+1}|X_{t+1})}[r(X_t,u_t)+\gamma Q^\pi (X_{t+1}, u_{t+1})]] \\ &= r(X_t, u_t) + E_{x_{t+1}\sim p(X_{t+1}|x_t, u_t)}[E_{u_{t+1}\sim \pi (u_{t+1}|X_{t+1})}[\gamma Q^\pi (X_{t+1}, u_{t+1})]] \end{align*}
위 식도 벨만 방정식이라고 부른다.
상태가치함수로 전개한 벨만 방정식과 동일하게, 무한 구간이라면 행동가치 함수는 시불변함수가 되어 좌변과 우변에 있는 행동가치 함수는 동일하다.
[출처]
박성수, 「수학으로 풀어보는 강화학습 원리와 알고리즘」, 위키북스(2020)