[강화학습] 4. Bellman Equation

Value Functions (가치 함수)

가치 함수는 각 상태 $s$(또는 상태-행동 쌍$(s; a)$)의 퀄리티를 측정합니다. 이때, 정책 $\pi$에 대한 기대 보상은 $G_t$를 따른다.

1. State-Value Function (상태-가치 함수) $v_{\pi}(s)$
   • 정책 $\pi$를 따랐을 때 특정 상태 $s에서 시작하는 기대 반환을 나타냄 
   • $v_{\pi}(s) = \mathbb{E}_{\pi} \left[ G_t | S_t = s \right]$
2. Action-Value Function (행동-가치 함수) $q_{\pi}(s,a)$
   • 상태 $s$에서 행동 $a$를 취하고 이후 $\pi$를 따라갔을 때의 기대 반환을 나타냄
   • $q_{\pi}(s, a) = \mathbb{E}_{\pi} \left[ G_t | S_t = s, A_t = a \right]$
3. Advantage Function (어드밴티지 함수) 
   • $A_{\pi}(s,a) = q_{\pi}(s,a) - v_{\pi}(s)$
   • 여기서, $v_{\pi}(s) = \sum_{a} \pi(a | s) q_{\pi}(s, a)$

 

Bellman Equation

Bellman Equation은 벨맨 방정식은 재귀 방정식으로, 상태값 함수 $v_{\pi}(s)$ 를 즉각적인 보상 $R_{t+1}$과 할인된 다음 상태 값 $\gamma v_{\pi}(S_{t+1})$로 분해한다.

 

\begin{align} v_{\pi}(s) &= \mathbb{E}_{\pi} \left[ G_t | S_t = s \right] \\ &= \sum_{a} \mathbb{E}_{\pi} \left[ G_t | S_t = s, A_t = a \right] \pi(a | s) \\ &= \sum_{a} \pi(a | s) \mathbb{E}_{\pi} \left[ R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a \right] \\ &= \sum_{a} \pi(a | s) \sum_{s', r} \mathbb{E}_{\pi} \left[ R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a, S_{t+1} = s', R_{t+1} = r \right] p(s', r | s, a) \\ &= \sum_{a} \pi(a | s) \sum_{s', r} p(s', r | s, a) \left( r + \gamma v_{\pi}(s') \right) \\ &= \sum_{a} \pi(a | s) \left( \mathbb{E}[R_{a}s] + \gamma \sum_{s'} p(s' | s, a) v_{\pi}(s') \right) \\ &= \mathbb{E}_{\pi} \left[ R_{t+1} + \gamma v_{\pi}(S_{t+1}) | S_t = s \right]\end{align}

 

 

\begin{align} q_{\pi}(s, a) &= \mathbb{E}_{\pi} \left[ G_t | S_t = s, A_t = a \right] \\ &= \sum_{s', r} p(s', r | s, a) \left( r + \gamma \sum_{a'} \pi(a' | s') q_{\pi}(s', a') \right) \\ &= \mathbb{E}_{\pi} \left[ R_{t+1} + \gamma q_{\pi}(S_{t+1}, A_{t+1}) | S_t = s, A_t = a \right]\end{align}

 

 

 

Optimal Value Functions and Policy

최적값 함수는 다른 모든 값 함수와 비교했을 때 최대값을 산출한다.

최적의 값 함수를 찾으면 MDP가 'solved '된다

• Optimal State-Value Function: $v_*(s) = \max_{\pi} v_{\pi}(s)$
• Optimal Action-Value Function: $q_*(s,a) = \max_{\pi} q_{\pi}(s,a)$

[Theorem] 그 어떤 MDP도 다음을 만족한다
1. 모든 $\pi$에 대해 optimal policy $\pi_{*} \geq \pi$가 존재한다.
2. 모든 optimal policy는 $v_{{\pi}_{*}}(s) = v_{*}(s)$를 achieve 한다.
3. 모든 optimal policy는 $q_{{\pi}_{*}}(s,a) = q_{*}(s,a)$를 achieve 한다

 

Optimal Policy는 $q_{*}(s,a)$를 maximize함으로써 도출될 수 있다.

$$\pi_*(a|s) = \begin{cases}
 1&  \text{ if } \;\;\;a = argmax_a q_*(s,a) \\
 0& \text{ if\;\;\; otherwise}  
\end{cases}$$

 

 

Bellman Optimality Equation

\begin{equation} v^*(s) = \max_{a \in A(s)} q^*(s, a) = \max_{a} \mathbb{E}_{\pi^*} \left[ G_t | S_t = s, A_t = a \right] \end{equation} \begin{equation} = \max_{a} \mathbb{E}_{\pi^*} \left[ R_{t+1} + \gamma G_{t+1} | S_t = s, A_t = a \right] \end{equation} \begin{equation} = \max_{a} \mathbb{E} \left[ R_{t+1} + \gamma v^*(S_{t+1}) | S_t = s, A_t = a \right] \end{equation} \begin{equation} = \max_{a} \sum_{s', r} p(s', r | s, a) \left( r + \gamma v^*(s') \right) \end{equation}

 

\begin{equation} q^*(s, a) = \mathbb{E} \left[ R_{t+1} + \gamma \max_{a'} q^*(S_{t+1}, a') | S_t = s, A_t = a \right] \end{equation} \begin{equation} = \sum_{s', r} p(s', r | s, a) \left( r + \gamma \max_{a'} q^*(s', a') \right) \end{equation}

 

 

 

참고 문헌

오승상 강화학습" target="_blank" rel="noopener" data-mce-href="http://오승상 강화학습">http://오승상 강화학습

오승상 강화학습 Deep Reinforcement Learning