[강화학습] 벨만 방정식, 벨만 최적 방정식

[강화학습] 벨만 방정식, 벨만 최적 방정식

이전 포스팅에서 정책, 가치함수, 벨만 기대 방정식, 행동 가치함수, 큐함수의 벨만 기대 방정식에 대해 알아보았습니다.

[강화학습] 정책, 가치함수, 벨만 기대 방정식

[강화학습] 정책, 가치함수, 벨만 기대 방정식

[강화학습] 큐함수 - 행동 가치함수

[강화학습] 큐함수 - 행동 가치함수

이번 포스팅에서는 벨만 방정식과 벨만 최적 방정식에 대해 알아보겠습니다.

---

• 벨만 방정식

정책을 반영한 벨만 기대 방정식은 다음과 같습니다.

$$\mathbf{v}_\pi(s) = E_\pi[R_{t+1}+\gamma\mathbf{v}_\pi(\mathbf{S}_{t+1})|\mathbf{S}_{t} = s]  \cdots (1)$$

 

벨만 방정식은 강화학습에서 상당히 중요합니다. 

벨만 방정식을 반환값으로 표현한 방정식은

$$\mathbf{v}_\pi(s) = E_\pi[R_{t+1}+\gamma R_{t+2}+ \gamma R_{t+3} + \cdots + \gamma^{k-1}R_{t+k}]\cdots (1)$$

입니다.

 

위의 반환값으로 표현한 벨만 방정식은 컴퓨터에서 계산하기에 상당히 비효율적입니다.

 

컴퓨터에서는 식(1)과 같이 재귀적으로 표현되는 식을 계산하는 것이 계산에 있어서 식(2) 보다 훨씬 효율적입니다.

이는 다이내믹 프로그래밍과 연관이 있습니다.

 

벨만 기대 방정식을 계산하기 위해서는 기댓값을 계산해야 합니다.

기댓값에는 어떤 행동을 할 확률($\pi(a|s)$), 그 행동을 했을 때 어떤 상태로 가게되는 확률($P_{ss'}^a$)이 포함되어 있습니다.

(정책 $\pi(a|s)$, 상태 변환 확률 $P_{ss'}^a$ https://deep-learning-challenge.tistory.com/46 참고)

[강화학습] 강화학습 기본 개념 정리

따라서 정책과 상태 변환 확률을 포함해서 식을 세우면 됩니다.

벨만 기대 방정식의 계산 가능한 형태는 다음과 같습니다.

$$\mathbf{v}_\pi(s) = \sum\limits_{a \in A} \pi(a|s)(r_{(s,a)}+\gamma \sum\limits_{s'\in \mathbf{S}} P_{ss'}^a \mathbf{v}_\pi(s'))$$

 

위 식에서 상태 변환 확률$P_{ss'}^a = 1$로 설정을 하면 

$$\mathbf{v}_\pi(s) = \sum\limits_{a \in A} \pi(a|s)(r_{(s,a)}+\gamma \mathbf{v}_\pi(s'))$$

입니다.

위 식을 해석해보면

1) 각 행동에 대해 그 행동을 할 확률을 고려하고 - $ \sum\limits_{a \in A} \pi(a|s)$

2) 각 행동을 했을 때 받을 보상과 - $r_{(s,a)}$

3) 다음 상태의 가치함수를 고려합니다. - $\gamma \mathbf{v}_\pi(s'))$

 

에이전트가 벨만 기대 방정식을 이용해 가치함수 $\mathbf{v}_\pi(s)$를 업데이트 할 때 상태 변환 확률$P_{ss'}^a = 1$로 설정한 위의 식을 사용합니다.

 

• 벨만 최적 방정식

벨만 기대 방정식을 계속해서 계산하다 보면 언젠가 좌변과 우변이 같아집니다.

 

벨만 기대 방정식 $$\mathbf{v}_\pi(s) = E_\pi[R_{t+1}+\gamma\mathbf{v}_\pi(\mathbf{S}_{t+1})|\mathbf{S}_{t} = s] $$

위의 벨만 기대 방정식을 반복적으로 계산하다보면, 무한히 반복하여 계산하면 방정식의 왼쪽 식과 오른쪽 식이 같아집니다. 즉, $\mathbf{v}_\pi(s)$의 값이 수렴하는 것입니다.

이는 정책$\pi$에 대한 참 가치함수를 구하는 것입니다.

 

위의 벨만 기대 방정식을 기댓값을 계산하기 위한 식으로 써보면

$$\mathbf{v}_{k+1}(s) \gets \sum\limits_{a\in A}\pi(a|s)(r_{(s,a)}+\gamma \mathbf{v}_k(s'))$$

입니다.

 

$\mathbf{v}_{k+1}(s)$의 아래첨자$k+1$은 현재 정책에 따라 $k+1$번째 계산한 가치함수를 뜻하고 $(s)$는 상태 $s$의 가치함수를 의미한다는 뜻입니다.

$k+1$번째 가치함수는 $k$번째 가치함수 중에서 주변 상태들 $s'$을 이용해 구합니다.

 

위의 식

$$\mathbf{v}_{k+1}(s) \gets \sum\limits_{a\in A}\pi(a|s)(r_{(s,a)}+\gamma \mathbf{v}_k(s'))$$ 

을 통해 현재 정책에 대한 참 가치함수를 구할 수 있습니다. 하지만 강화학습의 목적은 참 가치함수를 찾는 것이 아닌 최적 정책을 찾는 것입니다.

 

최적 정책은 정책을 따라갔을 때 받을 보상의 합인 가치함수를 통해 판단할 수 있습니다. 따라서 가치함수가 최대가 될 때의 정책을 최적 정책으로 정하고 수식으로는 다음과 같습니다.

$$\mathbf{v}*(s) = \max_{\pi}[\mathbf{v_\pi(s)}]$$

 

위의 식을 말로 해보면 "여러 정책 중 가치함수를 최대로 만드는 정책에서의 가치함수를 $\mathbf{v}*(s)$라고 하겠다" 정도가 되겠습니다. 

여기에서 $\mathbf{v}*(s)$를 최적 가치함수라고 합니다. 

 

최적 큐함수(행동 가치함수)또한 같은 방식으로 다음과 같습니다.

$$\mathbf{q}*(s,a) = \max_{\pi}[\mathbf{q_\pi(s,a)}]$$

 

최적 정책은 최적 큐함수에서 가장 큰 큐함수를 갖는 행동을 하는 것입니다.

즉, 선택 상황에서 판단 기준은 큐함수이며 최적 정책은 언제나 이 큐함수 중에 가장 높은 행동을 하는 것입니다.

따라서 최적 정책 $\pi *(s,a)$는 다음과 같이 구합니다.

 

$$\pi*(s,a)= \begin{cases} 1, & \mbox{if  } a = \arg \max_{a \in A} q*(s,a) \\  0, & \mbox{ otherwise} \end{cases}$$

 

벨만 방정식은 현재 상태의 가치함수와 다음 타임스텝 상태의 가치함수 사이의 관계식입니다.

에이전트는 큐함수를 통해 가치함수가 최적인지를 판단합니다.

이때 선택의 기준인 큐함수가 최적 큐함수가 아니라면 아무리 에이전트가 큐함수 중 최대를 선택해도 가치함수는 최적이 되지 않습니다. 따라서 다음 식과 같이 최적의 큐함수에서 최적 가치함수를 선택합니다.

$$\mathbf{v}*(s) = \max_{a}[q*(s,a)|\mathbf{S}_t = s, \mathbf{A}_t = a]$$

 

위의 식은 최적의 큐함수 중 최대를 선택하여 최적 가치함수를 나타내는 식입니다.

이 식에서 큐함수를 가치함수로 표현하면 다음과 같습니다.

$$\mathbf{v}*(s) = \max_{a}E[R_{t+1}+\gamma\mathbf{v}*(\mathbf{S}_{t+1}|\mathbf{S}_t = s, \mathbf{A}_t = a]$$

 

이를 벨만 최적 방정식(Bellman Optimality Equation)이라고 하며, 이 식은 최적의 가치함수에 대한 식입니다.

 

같은 방식으로 큐함수에 대한 벨만 최적방정식도 표현할 수 있으며 다음과 같습니다.

$$q*(s,a) = E[R_{t+1}+\gamma\max_{a'}q*(\mathbf{S}_{t+1},a')|\mathbf{S}_t = s, \mathbf{A}_t = a]$$

 

다음 포스팅에서는 다이내믹 프로그래밍에 대해 다루겠습니다. 

다이내믹 프로그래밍을 이용해 벨만 기대 방정식과 벨만 최적 방정식을 이용해 MDP로 정의되는 문제를 계산으로 풉니다.