벨만 방정식(Bellman Equation)

해당 포스팅을 보기 전에 MDP 포스팅을 보길 권장한다.

벨만 방정식은 주어진 정책 $\pi$ 의 벨류를 구하기 위해서 사용되며 현재 시점($t$)와 다음 시점($t+1$) 사이의 재귀적 관계를 이용해 정의된다. 이 방정식에는 '기대' 방정식과, '최적' 방정식 두 가지가 존재하므로 둘 모두를 설명한다.

 

1. 벨만 기대 방정식

벨만 기대 방정식은 아래와 같이 나타낼 수 있다.

$$\begin{array}{rl}{v}_{\pi }& ={\mathbb{E}}_{\pi }[r_{t+1}+\gamma v_{\pi }(s_{t+1})\\ \\ & ={\mathbb{E}}_{\pi }[G_t]\\ & ={\mathbb{E}}_{\pi }[r_{t+1}+\gamma r_{t+2}+{\gamma }^2{r}_{t+3}+\cdots ]\\ & ={\mathbb{E}}_{\pi }[r_{t+1}+\gamma (r_{t+2}+\gamma r_{t+3}+\cdots )]\\ & ={\mathbb{E}}_{\pi }[r_{t+1}+\gamma G_{t+1}]\\ & ={\mathbb{E}}_{\pi }[r_{t+1}+\gamma v_{\pi }(s_{t+1})]\end{array}$$

${\mathbb{E}}_{\pi }=$ 정책함수 $\pi$를 따라가는 경로에 대해서 기댓값을 취하라는 의미

현재상태 $s_t$의 밸류(리턴 기댓값)를 쪼개서 생각해 보자는 의미이며
리턴이 먼저 한 스텝만큼 진행하여 보상을 받은 뒤($r_{t+1}$), 그 다음 상태인 $s_{t+1}$부터 미래에 받을 보상을 더해줘도 똑같다는 의미($\gamma v_{\pi }(s_{t+1})$)이다.

 

1-1. qπ를 이용해 vπ계산하기

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

$v_{\pi }$ 는 상태가치 함수이다. ($s$부터 끝까지 $\pi$ 를 통해 움직였을 때 얻는 리턴의 기댓값.)
$q_{\pi }$ 는 액션가치 함수이다. ($s$에서 $a$를 선택하고 그 후에는 $\pi$ 를 따라 움직였을 때 얻는 리턴의 기댓값.)

위 식을 이해하기 위해 아래 그림을 참조하면 좋다.

바닥부터 배우는 강화학습 [그림 3-3]

$\pi$는 정책함수로서 특정 상태($s$) 에서 특정 액션($a$) 를 선택할 확률을 의미한다.
$q_{\pi }$는 액션 가치 함수로서, 특성 상태($s$) 에서 특정 액션($a$)를 선택한 뒤 그 이후 $\pi$를 따라 움직일 때 얻는 기대 리턴값을 의미한다.

여기서 액션벨류 $q_{\pi }(s,a_1)$과 $q_{\pi }(s,a_2)$ 의 값이 각각 1, 2 라는것을 알고 있는 상황이라면 이를 이용해 s의 총 벨류를 계산할 수 있다.

$$\begin{array}{rl}{v}_{\pi }(s)& =\pi (a_1|s)\ast q_{\pi }(s,a_1)+\pi (a_2|s)\ast q_{\pi }(s,a_2)\\ & =0.6\ast 1+0.4\ast 2\\ & =1.4\end{array}$$

어렵게 볼 필요 없이 각 정책함수값(확률) 과, 기대되는 액션벨류를 곱해주면 더해주면 $s$에 대한 최종적인 벨류를 구할 수 있다. 위의 풀이 과정을 수식으로 치환하면 위에서 언급했던 식이 도출된다.

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

 

 

 

1-2. vπ를 이용해 qπ계산하기

위에서 우리는 $q_{\pi }$를 통해 $v_{\pi }$를 계산해 봤다. 그렇다면 그 반대 역시 가능하지 않을까?

$$q_{\pi }(s,a)=r_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime })$$

$v_{\pi }$ 는 상태가치 함수이다. ($s$부터 끝까지 $\pi$ 를 통해 움직였을 때 얻는 리턴의 기댓값.)
$q_{\pi }$ 는 액션가치 함수이다. ($s$에서 $a$를 선택하고 그 후에는 $\pi$ 를 따라 움직였을 때 얻는 리턴의 기댓값.)

• $q_{\pi }(s,a)$ : $s$에서 $a$를 실행하는 벨류
• $r_s^a$ : 즉시 얻는 보상
• $P_{s{s}^{\prime }}^a$ : $s$에서 $a$를 실행하면 $s^{\prime }$에 도착할 확률
• $v_{\pi }(s^{\prime })$ : $s^{\prime }$의 벨류

바닥부터 배우는 강화학습 [그림 3-4]

우리는 $a_1$을 선택하자마자 얻는 보상의 값(0.5)을 알고있다. 그리고 액션 $a_1$을 선택한 뒤 다음 상태가 어떤 상태가 될 것인지에 대한 전이확률($70\mathrm{\%},30\mathrm{\%}$) 역시 알고 있으며, 각 상태의 벨류(1.5, -1) 또한 알고 있다. 때문에 앞서 계산한 바와 같이 계산할 수 있다.

$$\begin{array}{rl}{q}_{\pi }(s,a_1)& =r_s^{a_1}+p_{s{s}_1}^{a_1}\ast v_{\pi }(s_1)+p_{s{s}_2}^{a_1}\ast v_{\pi }(s_2)\\ & =0.5+0.7\ast 1.5+0.3\ast (-1)\\ & =1.25\end{array}$$

위 풀이를 좀더 일반적으로 변환하면 처음 언급했던 식이 도출된다.

$$q_{\pi }(s,a)=r_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime })$$

 

 

 

1-3. 식을 정리해 보자

$q_{\pi }\to v_{\pi }$
$$v_{\pi }=\sum _{a\in A}\pi (a|s)q_{\pi }(s,a)$$

$v_{\pi }\to q_{\pi }$
$$q_{\pi }(s,a)=r_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime })$$

$v_{\pi }=\cdots$ 내부 $q_{\pi }$식에 $q_{\pi }(s,a)$ 식을 대입해 준다.

$$v_{\pi }=\sum _{a\in A}\pi (a|s)(r_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\pi }(s^{\prime }))$$

$q_{\pi }(s,a)=\cdots$ 내부 $v_{\pi }(s^{\prime })$ 식에 $v_{\pi }$ 식을 대입 해 준다. (참고로 $s^{\prime }$ 등과 같은 ${}^{\prime }$ 표시는 $s_{t+1}$ 을 뜻함.)

$$q_{\pi }(s,a)=r_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a\sum _{a\in A}\pi (a^{\prime }|s^{\prime })q_{\pi }(s^{\prime },a^{\prime })$$

 

---

2. 벨만 최대 방정식

벨만 최대 방정식은 아래와 같다.

$$\begin{array}{rl}{v}_{\ast }& {=}_a^{max}\mathbb{E}[r_{+}\gamma v_{\ast }(s^{\prime })|s_t=s,a_t=a]\\ q_{\ast }(s,a)& =\mathbb{E}[r+{\gamma }_{a^{\prime }}^{max}{q}_{\ast }(s^{\prime },a^{\prime })|s_t=s,a_t=a]\end{array}$$

 

2-1. 최적 벨류

벨만 기대 방정식은 $v_{\pi }$와 $q_{\pi }(s,a)$에 대한 수식이라면 벨만 방정식은 $v_{\ast }(s)$와 $q_{\ast }(s,a)$에 대한 수식이다. $v_{\pi }$와 $q_{\pi }(s,a)$는 모두 정책이 $\pi$로 고정되었을 때 밸류에 관한 함수였다. 반면$v_{\ast }(s)$, $q_{\ast }(s,a)$는 최적벨류 에 대한 함수이다. 최적 벨류에 관한 정의는 아래와 같다.

$$\begin{array}{rl}{v}_{\pi }& {=}_{\pi }^{max}{v}_{\pi }(s)\\ q_{\ast }(s,a)& {=}_{\pi }^{max}{q}_{\pi }(s,a)\end{array}$$

MDP 안에 존재하는 모든 $\pi$중에서 가장 좋은 $\pi$를 (즉 $v_{\pi }(s)$ 의 값을 가장 높게 하는) 선택하여 계산한 밸류가 곧 최적벨류($v_{\ast }(s)$) 라는 의미이다.

여기서 이런 의문이 들 수 있다. $s_1\sim s_5$에서는 ${\pi }_1$의 벨류가 더 높고, 나머지 $s_6\sim s_{10}$ 에서는 ${\pi }_2$의 벨류가 더 높은 경우이다. 이런 상황에서는 ${\pi }_1,{\pi }_2$ 의 벨류중 어떤것이 더 높은지 파악하기가 힘들다. 이런 상황에 대해서 의문을 느껴 올바른 최적 $\pi$를 찾는데에 어려움을 느낄 수 있지만 걱정하지 않아도 된다. 아래와 같은 정리가 증명되어 있기 때문이다.

 

MDP 내에 모든 $\pi$에 대해 ${\pi }_{\ast }>\pi$를 만족하는 ${\pi }_{\ast }$가 반드시 존재한다.

 

위와같이 최적의 정책($\pi$)가 정의되고 나면 최적 벨류, 최적의 액션 벨류는 다음과 같은 등식이 성립한다.

• 최적의 정책 : ${\pi }_{\ast }$
• 최적의 벨류 : $v_{\ast }(s)=v_{{\pi }_{\ast }}(s)$(${\pi }_{\ast }$를 따랐을 때의 벨류)
• 최적의 액션 벨류 : $q_{\ast }(s,a)=q_{{\pi }_{\ast }}(s,a)$(${\pi }_{\ast }$를 따랐을 때의 액션 벨류)

현재까지 최적의 벨류란 무엇인지, 최적 정책이 무엇인지에 대해 설명했다. 이제 벨만 최적 방정식을 설명 해 보겠다.

 

2-2. q∗를 이용해 v∗계산하기

$$v_{\ast }{=}_a^{max}{q}_{\ast }(s,a)$$

상태 $s$의 최적 벨류는 $s$에서 선택할 수 있는 액션들 중에서 벨류가 가장 높은 벨류와 같다는 의미이다.

바닥부터 배우는 강화학습 [그림 3-5]

위 그림과 같이 상태 $s$에서 선택할 수 있는 액션이 $a_1,a_2$ 2개가 존재한다고 하자. 우리는 이미 각 액션을 선택했을 때 얻을 수 있는 최적 벨류를 이미 알고 있는 상황(1, 2)이다.이럴경우 상태 $s$의 최적 벨류는 당연히 $a_2$가 될 것이다. 이 때 최적벨류인 $v_{\ast }(s)$ 는 아래와 같이 나타낼 수 있다.

$$\begin{array}{rl}{v}_{\ast }& {=}_a^{max}{q}_{\ast }(s,a)\\ & =max(q_{\ast }(s,a_1),q_{\ast }(s,a_2))\\ & =max(1,2)=2\end{array}$$

전에 벨만 기대 방정식에서는 $q_{\ast }(s,a)$ 앞에 각 액션을 선택할 확률이 곱해졌었는데, 여기서는 당연히 100% 확률로 $a_2$ 를 선택하는것이 최적임을 알기에 따로 액션 선택 확률을 곱해주지 않는다.

 

2-3. v∗를 이용해 q∗계산하기

벨만 기대 방정식과 마찬가지로 이 역시 역순으로 도출해 내는것이 가능하다.

$$q_{\ast }(s,a)=r_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\ast }(s^{\prime })$$

 

2-4. 식을 정리해 보자

$q_{\ast }\to v_{\ast }$
$$v_{\ast }{=}_a^{max}{q}_{\ast }(s,a)$$

$v_{\ast }\to q_{\ast }$
$$q_{\ast }(s,a)=r_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\ast }(s^{\prime })$$

$v_{\ast }(s)=\cdots$ 식 내부에 $q_{\ast }(s,a)$에 식을 대입해 준다.

$$v_{\ast }{=}_a^{max}[r_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{v}_{\ast }(s^{\prime })]$$

$q_{\ast }(s,a)=\cdots$ 식 내부에 $v_{\ast }(s^{\prime })$에 식을 대입해 준다.

$$q_{\ast }(s,a)=r_s^a+\gamma \sum _{s^{\prime }\in S}{P}_{s{s}^{\prime }}^a{}_{a^{\prime }}^{max}{q}_{\ast }(s^{\prime },a^{\prime })$$