벨만 방정식(Bellman equation)

 1. 벨만 방정식이란?

앞서 State Value Function과 Action Value Function은 Return의 기댓값의 형태라 정의하였다.

하지만 이 수식 그대로를 적용한다면 모든 경우의 수를 시도해 본 후에야 Value Function을 구할 수 있을 것이다.

이는 복잡한 문제에서는 현실적으로 불가능하므로 이를 보완하고자 하는 시도중의 하나가 벨만 방정식을 이용하는 것이다.

벨만 방정식은 각 step 간의 재귀적 관계를 이용하여 정리한 식으로 이를 활용하면 현실적인 구현이 가능하다.

2. 벨만 기대 방정식(Bellman Expectation Equation)

2.1 상태 가치 함수

기본 정의에 따라 식을 순차적으로 전개해보자.

$$\begin{matrix}v_{\pi}(s) &=& E \left[ G_t \mid S_t = s, \pi \right] \\ &=& E \left[ R_{t+1} + \gamma R_{t+2} + \gamma^2 R_{t+3} + \dots \mid S_t = s, \pi \right] \\ &=& E \left[ R_{t+1} + \gamma G_{t+1} \mid S_t = s, \pi \right] \end{matrix}$$

이때 시간 $t+1$에서 return의 기댓값은 다음 그림을 보면

$t+1$에 해당하는 모든 상태의 return에 대한 기댓값을 취하면 상태 가치 함수와 같게 된다.

따라서 위 식은 다음과 같이 표현 가능하다.

$$E \left[ R_{t+1} + \gamma v_{\pi}(s_{t+1}) \mid S_t = s, \pi \right]$$

이를 전개하여 수열의 합 형태로 나타낼 수도 있다.

$$\begin{matrix} v_{\pi}(s) &=& \underset{a \in A} \sum \pi (a \mid s) \underset{s' \in S} \sum P_{ss'}^a \left( R_{s'} + \gamma v_{\pi}(s') \right) \\ &=& \underset{a \in A} \sum \pi (a \mid s)  \left( R_{s}^a + \gamma \underset{s' \in S} \sum P_{ss'}^a v_{\pi}(s') \right) \cdots (1) \end{matrix}$$

2.2 행동 가치 함수

행동 가치 함수도 마찬가지로 전개해보자.

$$\begin{matrix} q_{\pi}(s, a) &=& E \left[ R_{t+1} + \gamma G_{t+1} \mid S_t = s, A_t = a, \pi \right] \\ &=& E \left[ R_{t+1} + \gamma v_{\pi}(s_{t+1}) \mid S_t = s, A_t = a, \pi \right] \\ &=& \underset{s' \in S} \sum P_{ss'}^a \left( R_{s'} + \gamma v_{\pi}(s') \right) \\ &=& R_{s}^a + \gamma \underset{s' \in S} \sum P_{ss'}^a v_{\pi}(s') \cdots (2) \end{matrix}$$

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

$(1)$번 식과 $(2)$번 식의 관계를 살펴보면 다음 식이 성립한다.

$$v_{\pi}(s) = \underset{a \in A} \sum \pi(a \mid s) q_{\pi}(s, a)$$

이 식을 $(2)$번 식에 대입하면 다음과 같은 표현도 가능하다.

$$q_{\pi}(s, a) = R_{s}^a + \gamma \underset{s' \in S} \sum P_{ss'}^a \underset{a' \in A} \sum \pi(a' \mid s') q_{\pi}(s', a')$$

3. 벨만 최적 방정식

3.1 최적 벨류와 최적 정책

강화 학습은 Return을 극대화 하는 방향으로 정책을 설정하는것이 목표이기 때문에

가치함수를 최대화 하는 정책을 찾을 수 있다면 그 최대 가치를 최적 벨류(optimal value), 그때의 정책을 최적 정책(optimal policy)이라고 한다.

아래는 최적 벨류의 정의이다.

$$v_* (s) = \underset{\pi} \max v_{\pi}(s) \\ q_* (s, a) = \underset{\pi} \max q_{\pi} (s, a)$$

모든 상태 각각에서 가치함수를 최대화하는 정책이 최적 정책$\pi_*$이다.

3.2 벨만 최적 방정식

벨만 최적 방정식은 정책 요소들이 사라지는데

이는 최적 벨류를 따르는 행동을 취하기 때문이다.

벨만 기대 방정식을 벨만 최적 방정식으로  나타내보면 다음과 같다.

$$\begin{matrix} v_* (s) &=& \underset{a} \max E \left[ R_{t+1} + \gamma v_* (s_{t+1}) \right] \\ &=& \underset{a} \max \left[ R_s^a + \gamma \underset{s' \in S} \sum P_{ss'}^a v_* (s') \right]\end{matrix}$$

행동 가치 함수의 경우 현재상태의 행동은 최적 행동이 아니더라도 그 이후 정책을 모두 최적 정책이라 가정하고 식을 유도하면 된다.

$$\begin{matrix} q_* (s, a) &=& E \left[ R_{t+1} + \gamma \underset{a'} \max q_* (s_{t+1}, a') \right] \\ &=& R_s^a + \gamma \underset{s' \in S} \sum P_{ss'}^a \underset{a'} \max q_* (s', a') \end{matrix}$$