벨만 방정식(Bellman Equation)

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

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

 

 

 

1. 벨만 기대 방정식

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

$$ \begin{flalign}
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{flalign} $$

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

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

 

1-1. $q_{\pi}$를 이용해 $v_{\pi}$계산하기

$$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{flalign}
v_{\pi}(s) &= \pi(a_{1}|s) * q_{\pi}(s, a_{1}) + \pi(a_{2}|s) * q_{\pi}(s, a_{2}) \\
&= 0.6 * 1 + 0.4 * 2 \\
&= 1.4 
\end{flalign} $$

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

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

 

 

 

1-2. $v_{\pi}$를 이용해 $q_{\pi}$계산하기

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

$$ q_{\pi}(s,a) = r^{a}_{s} + \gamma \sum_{s' \in S} P_{ss'}^{a} v_{\pi}(s') $$

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

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

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

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

$$ \begin{flalign}
q_{\pi}(s, a_{1}) &= r^{a_{1}}_{s} + p^{a_{1}}_{ss_{1}} * v_{\pi} (s_{1}) + p^{a_{1}}_{ss_{2}} * v_{\pi}(s_{2}) \\
&= 0.5 + 0.7 * 1.5 + 0.3 * (-1) \\
&= 1.25
\end{flalign} $$

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

$$ q_{\pi}(s,a) = r^{a}_{s} + \gamma \sum_{s' \in S} P_{ss'}^{a} v_{\pi}(s')$$

 

 

 

1-3. 식을 정리해 보자

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

$v_{\pi} → q_{\pi} $
$$ q_{\pi}(s,a) = r^{a}_{s} + \gamma \sum_{s' \in S} P_{ss'}^{a} v_{\pi}(s')$$

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

$$ v_{\pi} = \sum_{a \in A} \pi(a|s) \Big( r^{a}_{s} + \gamma \sum_{s' \in S} P_{ss'}^{a} v_{\pi}(s') \Big) $$

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

$$q_{\pi}(s,a) = r^{a}_{s} + \gamma \sum_{s' \in S} P_{ss'}^{a} \sum_{a \in A} \pi(a'|s')q_{\pi}(s',a')$$

 

---

2. 벨만 최대 방정식

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

$$ \begin{flalign}
v_{*} &= ^{max}_{\,\,\,a}\mathbb{E}[r_ + \gamma v_{*}(s')| s_{t} = s, a_{t} = a] \\
q_{*}(s,a) &= \mathbb{E}[r + \gamma ^{max}_{\,\,\,a'}\, q_{*}(s', a') | s_{t} = s, a_{t} = a] \\
\end{flalign} $$

 

2-1. 최적 벨류

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

$$ \begin{flalign}
v_{\pi} &= ^{max}_{\,\,\,\pi} v_{\pi}(s) \\
q_{*}(s,a) &= ^{max}_{\,\,\,\pi} q_{\pi}(s, a)
\end{flalign} $$

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

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

 

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

 

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

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

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

 

2-2. $q_{*}$를 이용해 $v_{*}$계산하기

$$ \Large v_{*} = ^{max}_{\,\,\,a}q_{*}(s, a) $$

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

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

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

$$ \begin{flalign}
v_{*} &= ^{max}_{\,\,\,a} q_{*}(s, a) \\
&= max (q_{*}(s, a_{1}), q_{*}(s, a_{2})) \\
&= max(1,2) = 2
\end{flalign} $$

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

 

2-3. $v_{*}$를 이용해 $q_{*}$계산하기

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

$$q_{*}(s, a) = r_{s}^{a} + \gamma \sum_{s' \in S} P_{ss'}^a v_{*}(s') $$

 

2-4. 식을 정리해 보자

$q_{*} → v_{*}$
$$ v_{*} = ^{max}_{\,\,\,a}q_{*}(s, a) $$

$v_{*} → q_{*} $
$$q_{*}(s, a) = r_{s}^{a} + \gamma \sum_{s' \in S} P_{ss'}^a v_{*}(s') $$

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

$$ v_{*} = ^{max}_{\,\,\,a} \Biggl[ r^{a}_{s} + \gamma \sum_{s' \in S} P^{a}_{ss'} v_{*}(s') \Biggl] $$

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

$$ q_{*}(s,a) = r_{s}^{a} + \gamma \sum_{s' \in S} P^{a}_{ss'}\, ^{max}_{\,\,\,a'}  q_{*} (s', a')  $$