벨만방정식 유도하기

Seulgi Kim·2023년 5월 16일

reinforce learning

목록 보기

9/14

가치함수

상태가치함수

상태가치함수는 다음과 같다.

\begin{aligned} V^\pi(x_t)&={\mathbb E}_{\tau_{u_t:u_T}\sim p(\tau_{u_t:u_T}|x_t)}\left[ \sum\limits_{k=t}^T \gamma^{k-t} r(x_k, u_k) | x_t \right] \\ &=\int\limits_{\tau_{u_t:u_T}} \left( \sum\limits_{k=t}^T \gamma^{k-t} r(x_k, u_k) \right) p(\tau_{u_t:u_T}|x_t) d\tau_{u_t:u_T} \end{aligned}

$\tau$ 는 궤적을 의미하며, $\tau_{u_t:u_T}$ 는 $u_t$ 부터 $u_T$ 까지의 궤적을 뜻한다.
${\mathbb E}_{\tau_{u_t:u_T}\sim p(\tau_{u_t:u_T}|x_t)}$ 는 $\tau$ 가 확률 밀도 함수 $p(\tau|x_t)$ 를 따를 때의 평균을 의미한다.

행동가치함수

마찬가지로 행동가치함수는 다음과 같다.

\begin{aligned} Q^\pi(x_t, u_t) &= {\mathbb E}_{\tau_{x+1:u_T}\sim p(\tau_{x_{t+1}:u_T}|x_t, u_t)} \left[ \sum\limits_{k=t}^T \gamma^{k-t} r(x_k, u_k) | x_t, u_t \right] \\ &= \int\limits_{\tau_{x_{t+1}:u_T}} \left( \sum\limits_{k=t}^T \gamma^{k-t} r(x_k, u_k) \right) p(\tau_{x_{t+1}:u_T}|x_t, u_t) d\tau_{x_{t+1}:u_T} \end{aligned}

상태가치함수과 행동가치함수의 관계

앞서 살펴본 바와 같이, 상태가치함수와 행동가치함수는 다음과 같은 관계가 있다.

\begin{aligned} V^\pi(x_t) &= \int\limits_{u_t} Q^\pi(x_t, u_t) \pi(u_t|x_t) du_t \\ &= {\mathbb E}_{u_t\sim \pi(u_t|x_t)} \left[ Q^\pi(x_t, u_t) \right] \end{aligned}

즉, 상태가치함수란 특정 상태 $x_t$ 에서 정책 $\pi$ 에 따라 행동 $u_t$ 를 선택했을 때, 그때의 행동가치함수의 기댓값이다.

벨만방정식

행동가치함수를 시간구간 $[t, t+n-1]$ 과 $[t+n, T]$ 두 부분으로 나눠보자.

\begin{aligned} Q^\pi(x_t, u_t) &= Q_1 + Q_2 \\ &= \int\limits_{\tau_{x_{t+1}:u_T}} \left( \sum\limits_{k=t}^{t+n-1} \gamma^{k-t} r(x_k, u_k) \right) p(\tau_{x_{t+1}:u_T}|x_t, u_t) d\tau_{x_{t+1}:u_T} \\ &+ \int\limits_{\tau_{x_{t+1}:u_T}} \left( \sum\limits_{k=t+n}^T \gamma^{k-t} r(x_k, u_k) \right) p(\tau_{x_{t+1}:u_T}|x_t, u_t) d\tau_{x_{t+1}:u_T} \end{aligned}

이때 궤적 $\tau_{x_{t+1}:u_T}$ 를 $[x_{t+1}, x_{t+n}]$ 과 $[u_{t+n}, u_T]$ 두 영역으로 분할하면 확률의 연쇄법칙에 의해

$p(\tau_{x_{t+1}:u_T}|x_t, u_t) = p(\tau_{x_{t+1}:x+n}|x_t, u_t) \cdot p(\tau_{u_{t+n}:u_T}|x_t, u_t, \tau_{x_{t+1}:x_{t+n}})$

이 된다. 이때, 확률밀도함수는 마르코프 시퀀스임을 가정하므로,

$p(\tau_{x_{t+1}:u_T}|x_t, u_t) = p(\tau_{x_{t+1}:x+n}|x_t, u_t) \cdot p(\tau_{u_{t+n}:u_T}|x_{t+n})$

이다.
이를 각각 $Q_1$ 과 $Q_2$ 에 대입해보자.

\begin{aligned} Q_1 &= \int\limits_{\tau_{x_{t+1}:u_T}} \left( \sum\limits_{k=t}^{t+n-1} \gamma^{k-t} r(x_k, u_k) \right) p(\tau_{x_{t+1}:u_T}|x_t, u_t) d\tau_{x_{t+1}:u_T} \\ &=\int\limits_{\tau_{u_{t+n}:u_T}}~\int\limits_{\tau_{x_{t+1}:x_{t+n}}} \left( \sum\limits_{k=t}^{t+n-1} \gamma^{k-t} r(x_k, u_k) \right) p(\tau_{x_{t+1}:{x_{t+n}}}|x_t, u_t) p(\tau_{u_{t+n}:u_T}|x_{t+n}) d\tau_{x_{t+1}:x_{t+n}}d\tau_{u_{t+n}:u_T} \end{aligned}

이때 $t$ 와 $t+1$ 일때의 상태와 행동은 독립성을 가정하므로,

\begin{aligned} Q_1 &=\int\limits_{\tau_{x_{t+1}:x_{t+n}}}\left[ ~\int\limits_{\tau_{u_{t+n}:u_T}} p(\tau_{u_{t+n}:u_T}|x_{t+n}) d\tau_{u_{t+n}:u_T} \right] \\ & \cdot \left( \sum\limits_{k=t}^{t+n-1} \gamma^{k-t} r(x_k, u_k) \right) p(\tau_{x_{t+1}:{x_{t+n}}}|x_t, u_t) d\tau_{x_{t+1}:x_{t+n}} \\ &=\int\limits_{\tau_{x_{t+1}:x_{t+n}}} \left( \sum\limits_{k=t}^{t+n-1} \gamma^{k-t} r(x_k, u_k) \right) p(\tau_{x_{t+1}:{x_{t+n}}}|x_t, u_t) d\tau_{x_{t+1}:x_{t+n}} \end{aligned}

이다. 다음으로 $Q_2$ 를 정리해보자. 마찬가지로, 독립임을 가정하므로,

\begin{aligned} Q_2 &= \int\limits_{\tau_{x_{t+1}:u_T}} \left( \sum\limits_{k=t+n}^T \gamma^{k-t} r(x_k, u_k) \right) p(\tau_{x_{t+1}:u_T}|x_t, u_t) d\tau_{x_{t+1}:u_T} \\ &=\int \gamma^n \left[ \int \left( \sum\limits_{k=t+n}^T \gamma^{k-(t+n)} r(x_k, u_k) \right) p(\tau_{u_{t+n}:u_T}|x_{t+n}) d\tau_{u_{t+n}:u_T} \right] p(\tau_{x_{t+1}:x_{t+n}}|x_t, u_t) d\tau_{x_{t+1}:x_{t+n}} \end{aligned}

이다. 대괄호 안을 면밀히 살펴보면, $t+n$ 시간대의 상태가치함수와 같다는 것을 알 수 있을 것이다. 즉,

\begin{aligned} Q_2 = \int\limits_{\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}} \end{aligned}

이다. 이제 행동가치함수 $Q$ 를 구해보면,

\begin{aligned} Q^\pi(x_t, u_t) &= \int\limits_{\tau_{x_{t+1}:x_{t+n}}} \left[ \sum\limits_{k=t}^{t+n-1} \gamma^{k-t} r(x_k, u_k) + \gamma^n V^\pi(x_{t+n}) \right] p(\tau_{x_{t+1}:x_{t+n}}|x_t, u_t) d\tau_{x_{t+1}:x_{t+n}} \\ &= {\mathbb E}_{\tau_{x_{t+1}:x_{t+n}}\sim p(\tau_{x_{t+1}:x_{t+n}}|x_t, u_t)} \left[ \sum\limits_{k=t}^{t+n-1} \gamma^{k-t} r(x_k, u_k) + \gamma^n V^\pi(x_{t+n}) \right] \end{aligned}

가 된다. 특별한 경우로서, $n=1$ 로 하면 행동가치함수는 다음과 같다.

\begin{aligned} Q^\pi(x_t, u_t) &= {\mathbb E}_{\tau_{x_{t+1}:x_{t+n}}\sim p(\tau_{x_{t+1}:x_{t+n}}|x_t, u_t)} \left[ r(x_t, u_t) + \gamma V^\pi(x_{t+n}) \right] \end{aligned}

위 식에서 $r(x_t, u_t)$ 는 $x_{t+1}$ 에 관한 함수가 아니므로,

\begin{aligned} Q^\pi(x_t, u_t) &= r(x_t, u_t) + {\mathbb E}_{\tau_{x_{t+1}}\sim p(\tau_{x_{t+1}}|x_t, u_t)} \left[ \gamma V^\pi(x_{t+1}) \right] \end{aligned}

이다. 이를 상태가치함수로 나타내면 다음과 같다.

\begin{aligned} V^\pi(x_t) = {\mathbb E}_{u_{t} \sim \pi(u_t|x_t)} \left[ r(x_t, u_t) + {\mathbb E}_{\tau_{x_{t+1}}\sim p(\tau_{x_{t+1}}|x_t, u_t)} \left[ \gamma V^\pi(x_{t+1}) \right] \right] \end{aligned}

이 두 식을 바로 벨만방정식(Bellman equation)이라고 부르며, 현재 상태의 가치와 다음 시간 스템의 상태의 가치와의 관계를 나타내는 식이다.

벨만 최적 방정식

모든 정책 중 상태가치 값을 최대로 만드는 정책을 적용했을 때의 상태가치함수와 행동가치함수를 각각 최적 상태가치함수, 최적 행동가치함수라고 한다.

\begin{aligned} V^*(x_t) &= \max\limits_\pi V^\pi(x_t) \\ Q^*(x_t, u_t) &= \max\limits_\pi Q^\pi(x_t, u_t) \end{aligned}

먼저 최적 상태가치함수부터 살펴보자. $t$ 시간과 $t+1$ 시간의 행동은 독립적이므로, 다음과 같이 쓸 수 있다.

\begin{aligned} V^*(x_t) &= \max\limits_\pi {\mathbb E}_{u_{t} \sim \pi(u_t|x_t)} \left[ r(x_t, u_t) + {\mathbb E}_{\tau_{x_{t+1}}\sim p(\tau_{x_{t+1}}|x_t, u_t)} \left[ \gamma V^\pi(x_{t+1}) \right] \right] \\ &=\max\limits_{u_t, u_{t+1}, ..., u_T} \left[ r(x_t, u_t) + {\mathbb E}_{\tau_{x_{t+1}}\sim p(\tau_{x_{t+1}}|x_t, u_t)} \left[ \gamma V^\pi(x_{t+1}) \right] \right] \end{aligned}

이때 보상함수 $r(x_t, u_t)$ 는 $u_{t+1}, ..., u_T$ 에 대한 함수가 아니고, 궤적 $\tau_{x_{t+1}}$ 도 $u_{t+1}, ..., u_T$ 에 독립이므로,

\begin{aligned} V^*(x_t) &= \max\limits_{u_t} \left[ r(x_t, u_t) + \max\limits_{u_{t+1}, ..., u_T} {\mathbb E}_{\tau_{x_{t+1}}\sim p(\tau_{x_{t+1}}|x_t, u_t)} \left[ \gamma V^\pi(x_{t+1}) \right] \right] \\ &=\max\limits_{u_t} \left[ r(x_t, u_t) + {\mathbb E}_{\tau_{x_{t+1}}\sim p(\tau_{x_{t+1}}|x_t, u_t)} \left[ \max\limits_\pi\gamma V^\pi(x_{t+1}) \right] \right] \\ &=\max\limits_{u_t} \left[ r(x_t, u_t) + {\mathbb E}_{\tau_{x_{t+1}}\sim p(\tau_{x_{t+1}}|x_t, u_t)} \left[ \gamma V^*(x_{t+1}) \right] \right] \end{aligned}

이다. 또한 행동가치함수로부터,

\begin{aligned} Q^*(x_t, u_t) &= r(x_t, u_t) + \max\limits_{u_{t+1}, ..., u_T} \left[ {\mathbb E}_{x_{t+1}\sim p(x_{t+1}|x_t, u_t)} \left[ \gamma V^\pi(x_{t+1}) \right] \right] \\ &= r(x_t, u_t) + {\mathbb E}_{x_{t+1}\sim p(x_{t+1}|x_t, u_t)} \left[ \max\limits_\pi\gamma V^\pi(x_{t+1}) \right] \\ &= r(x_t, u_t) + {\mathbb E}_{x_{t+1}\sim p(x_{t+1}|x_t, u_t)} \left[ \gamma V^*(x_{t+1}) \right] \end{aligned}

최적 상태가치함수와 최적 행동가치함수의 관계

최적 상태가치함수와 최적 행동가치함수로부터 다음과 같은 관계를 얻을 수 있다.

\begin{aligned} V^*(x_t) = \max\limits_{u_t}Q^*(x_t, u_t) \end{aligned}

이로부터 다음과 같은 식을 유도 가능하다.

\begin{aligned} Q^*(x_t, u_t) = r(x_t, u_t) + {\mathbb E}_{x_{t+1}\sim p(x_{t+1}|x_t, u_t)} \left[ \gamma \max\limits_{u_{t+1}}Q^*(x_{t+1}, u_{t+1}) \right] \end{aligned}

이를 벨만 최적 방정식(Bellman optimality equation)이라고 부르며, 현재의 최적 가치와 다음 시간스텝의 최적 가치와의 관계를 나타낸다.

최적 정책

상태가치값을 최대로 만드는 정책을 최적 정책(optimal policy)라고 부른다.

\begin{aligned} \pi^*(x_t) &= \argmax\limits_{u_t} \left[ r(x_t, u_t) + {\mathbb E}_{x_{t+1}\sim p(x_{t+1}|x_t, u_t)} \left[ \gamma V^*(x_{t+1}) \right] \right] \\ &= \argmax\limits_{u_t} Q^*(x_t, u_t) \end{aligned}

강화학습 방법

최적의 정책을 얻기 위하여 여러 방법을 사용한다.
1. 가치기반 강화학습 : 가치함수를 추정해 최대의 보상을 계산
2. 정책 그래디언트 : 직접 정책을 유도하는 방법
3. 모델 기반 강화학습 : 환경 모델을 추정해 사용하는 방법

Seulgi Kim

이전 포스트

강화학습 개념

다음 포스트