Value Function and Bellan Equation

Value Function(가치 함수)

먼저 value function(가치 함수)를 설명하기 위해 간단하게 MDP에 대해 설명해 보려 합니다. MDP에서 에이전트는 각 상태에서 보상을 극대화하기 위한 정책. 즉. 앞으로 받을 것으로 예상되는 보상의 기댓값을 고려하여 행동을 선택하게 됩니다. 여기서 앞으로 받을 것으로 예상되는 보상의 기댓값을 value function이라고 표현한다.

 

가치함수는 크게 State-value function과 Action-value function 두 가지로 구분이 됩니다.

State-value function

에이전트가 $t$시점에 $s$에서 행동 $a$ 선택하고 reward $r$을 받는 것을 매 시점마다 반복해 나가 그때 받았던 일련의 보상의 합을 구하면 다음과 같습니다.

 

$R_{t+1} + R_{t+2} + R_{t+3} + R_{t+4} + ...$

 

이때 감가율($\gamma$)이란 개념을 통해 미래의 보상보다 현재의 보상이 더 중요하다는 것을 알고 있을 것입니다. 따라서 여기서도 미래의 시점에 감가율($\gamma$)을 곱해 주어 다음과 같이 나타냅니다.

 

$G_t = R_{t+1} + {\gamma}R_{t+2} + {\gamma}^{2} R_{t+3} + ... = \sum_{k=0}^{\infty}\gamma^kR_{t+k+1}$

 

위 식의 기댓값이 state-value function으로 어떤 상태 S의 가치로 해석합니다. 이렇게 구해진 state-value function을 통해 에이전트가 다음으로 갈 수 있는 state들의 가치를 보고서 높은 가치의 state로 이동하게 됩니다.

 

$v(s) = E[G_t | S_t = s]$

 

 

Action-value function(Q-Function)

value function은 어떤 state가 좋은 state인지는 알려주지만 그 state로 가는 action에 대해서는 평가하지 않습니다. 따라서 value function을 구하고 높은 value를 가지는 state로 가기 위한 action은 따로 고려해야 하는데, 이를 동시에 하기 위해 state와 action을 동시에 고려한 Action-value function을 사용합니다. Action-value function은 다른 말로 Q-Function이라고도 부릅니다.

 

Action-value function은 State-value function에 action을 추가한 형태로, State-value function과 마찬가지로 현재 state를 시작으로 policy $\pi$를 따라갔을 때의 총기댓값의 합을 구하는 것입니다.

 

$q_{\pi}(s, a) = E[G_t | S_t = s, A_t = a]$

 

Bellman equation(벨만 방정식)

Bellman expectation equation(벨만 기대 방정식)

Bellman expectation equation은 policy $\pi$를 따라갔을 때 reward의 총합을 구하는 것을 말합니다. 

 

$v_\pi(s) = E_\pi[R_{t+1} + \gamma{v}(S_{t+1}) | S_t=s]$

 

여기서 $t+2$시점부터의 reward은 감가율($\gamma$)을 통해 묶어주면 묶인 텀은 $t+1$시점부터 받을 보상의 reward로 이는 곧 $t+1$시점에서의 value function으로 표현할 수 있습니다. 아래와 같이 다음 state와 현재 state의 value function 사이의 관계를 식으로 나타낸 것을 Bellman expection eqation이라고 합니다.

 

$v(s) = E[G_t | S_t = s]$

$= E[R_{t+1} + {\gamma}R_{t+2} + {\gamma}^2R_{t+3} + ... | S_t = s]$

$= E[R_{t+1} + {\gamma}(R_{t+2} + {\gamma}R_{t+3} + ...)| S_t = s]$

$= E[R_{t+1} + {\gamma}G_{t+1} | S_t = s]$

$= E[R_{t+1} + {\gamma}v(S_{t+1}) | S_t = s]$

 

벨만 최적 방정식(Bellman Optimality equation)

Optimal value function

Bellman optimality equation을 보기 전에 optimal value function에 대해서 살펴보도록 하겠습니다. 강화 학습의 목적이 accumulative future reward를 최대로 하는 policy를 찾는 것이라 했었습니다. optimal state-value function이란 현재 state에서 policy에 따라서 앞으로 받을 reward들이 달라지는데 그중에서 앞으로 가장 많은 reward를 받을 policy를 따랐을 때의 value function입니다. optimal action-value function도 마찬가지로 현재 $(s,a)$에서 얻을 수 있는 최대의 value function입니다.

 

- optimal state-value function

 

$v*(s) = \underset{\pi} max$ $v_{\pi}(s)$

 

- optimal action-value function

 

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

 

현재 environment에서 취할 수 있는 가장 높은 reward의 총합입니다. optimal value function의 값을 안다면 단순히 q 값이 높은 action을 선택해주면 되므로 이 최적화 문제는 풀렸다고 볼 수 있습니다. 강화 학습뿐만 아니라 Dynamic programming에서도 목표가 되는 optimal policy는 다음과 같습니다. optimal policy는 (s, a)에서 action-value function이 가장 높은 action만을 고르기 때문에 deterministic 합니다.

 

Bellman Optimality Equation

Bellman Optimality Equation은 Optimal value function을 찾기 위해서는 단순히 현재 에이전트의 policy에 대한 value function을 구하는 것이 아니라 현재의 policy을 optimal policy로 업데이트해 나가는 것을 말합니다.

 

optiaml policy를 업데이트 하기 위해서 우리는 value function을 통해 어떤 policy가 더 좋은 policy인지 평가합니다. 따라서 모든 policy에 대해 가장 큰 보상을 기대할 수 있는 optimal value function을 찾습니다.

 

$v^*(s) = max[v_\pi(s)]$

 

Q-function 역시 같은 방식으로 표현 할 수 있습니다.

 

$q^*(s, a) = max [q_\pi(s, a)]$

 

optimal value function을 찾았다면, 이때 optimal policy는 optimal Q-function을 통해 가장 보상 기댓값이 높은 행동을 하는 것으로 다음과 같이 표현합니다.

 

$\pi^*(s,a) = {1, if a = argmax_a{q}_\pi(s,a) \brace 0, otherwise}$

 

마지막으로 앞서 소개한 optimal value function 두 식을 각각 value function로 고쳐 표현하면 다음과 같습니다.

 

$v^*(s) = maxE[R_{t+1} + \gamma {v}^*(S_{t+1}) | S_t = s, A_t = a]$

 

$q^*(s,a) = E[R_{t+1} + \gamma{max}q^*(S_{t+1},a') | S_t=s, A_t]$

 

이때, 첫 번째 수식을 Bellman Optimality Equation. 두 번째 수식을 큐 함수에 대한 Bellma Optimality Equation이라 합니다.

 

이러한 Bellman equation을 통해 iterative하게 MDP 문제를 푸는 것을 Dynamic Programming(DP)라고 합니다. 

 

---

출처 

https://www.youtube.com/watch?v=NMesGSXr8H4&list=PLpRS2w0xWHTcTZyyX8LMmtbcMXpd3s4TU&index=2

http://www0.cs.ucl.ac.uk/staff/d.silver/web/Teaching_files/MDP.pdf

https://dhznsdl.tistory.com/14

https://dnddnjs.gitbooks.io/rl/content/bellman_equation.html