Bellman Equation

State와 action, 그리고 그에 대한 보상이 있기 때문에 그 state의 가치는 무엇인가, 즉 그 state에 있는 것이 앞으로 얼마만큼의 total reward를 제공하는가에 대한 의문이 들 수 있다. 단순히 state의 가치뿐만 아니라, 그 state에서 어떤 action을 취하는 것이 장기적으로 얼마나 가치있는지에 대해서도 자연스럽게 궁금함이 생긴다.

 

여기서 핵심은 reward는 즉각적(local) 신호이지만, 우리가 궁금한 가치는 long-term outcome이라는 점이다. 이러한 질문에 답하기 위해 정의된 것이 state value function과 state-action value function이다.

---

State-Value Function & State-Action Value Funtion

State-value function $v_{\pi}(s)$는 다음과 같이 정의된다:

$$ v_{\pi}(s)=E_{\pi}[G_t | S_t = s]=E_{\pi}\left[\sum_{k=0}^{\infty}\gamma^k R_{t+k+1} | S_t = s\right] $$

즉, 특정 policy $\pi$를 따랐을 때 state s에서 시작해 앞으로 얻을 수 있는 long-term return의 기대값을 의미한다. 이 함수는 “그 state 자체가 얼마나 좋은가”를 정량적으로 평가하는 기준으로 사용된다.

 

그런데 state 자체 말고, state에서 어떤 action을 선택하는 가치까지 알고 싶을 수도 있다. 이를 정량적으로 정의한 것이 state-action value function $Q_\pi(s,a)$ 이다. 수식으로 확인해보자:

$$ Q_\pi(s,a)=E_{\pi}[G_t | S_t=s, A_t=a]=E_{\pi}\left[\sum_{k=0}^{\infty}\gamma^k R_{t+k+1}\mid S_t=s, A_t=a\right] $$

Bellman Expectation Equation

State value function과 State-action value function을 decompose해보자.

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

여기서 Markov property에 의해서

$$ E_\pi[G_{t+1}\mid S_{t+1}=s’, S_t=s, A_t=a] = E_\pi[G_{t+1}\mid S_{t+1}=s’] = v_\pi(s’) $$

를 만족하므로, 결국

$$ v_{\pi}(s)=\sum_a \pi(a\mid s) \sum_{s',r}p(s',r\mid s,a)(r+\gamma v_{\pi}(s')) $$

로 recursive하게 정의된다.

 

State action value function 또한 비슷한 과정으로

$$ Q_\pi(s,a) = \sum_{s',r}p(s',r\mid s,a) \left(r + \gamma\sum_a' \pi(a'\mid s')Q_\pi(s',a')\right)=\sum_{s',r}p(s',r\mid s,a) \left(r + \gamma v(s')\right)$$

와 같이 정의된다.

 

이렇게 state-value function과 state-action value function은 현재의 보상과 이후의 상태 가치 함수의 결합으로 recursive하게 표현됨을 알 수 있고, 이를 Bellman expectation equation이라 한다. 이 recursive form은 이후에 우리가 TD learning, dynamic programming, Monte-Carlo prediction 등을 구현할 때 update rule의 핵심 기반이 되는 매우 중요한 구조이다.

 

여기서 중요한 점은 value function이 단순히 수학적인 정의에서 끝나는 것이 아니라, “policy의 품질을 비교하는 기준” 역할을 한다는 점이다. 두 policy가 있을 때, 특정 policy가 다른 policy보다 더 나은지 비교하는 가장 직접적인 방법은 value function을 비교하는 것이다.

즉, 어떤 policy가 모든 state에서 더 큰 value를 제공한다면 그 policy가 더 좋은 policy라고 말할 수 있다. 다음과 같은 definition을 확인하자:

$$ \pi \geq \pi' \text{ if only if } v_{\pi}(s) \geq v_{\pi'}(s), \forall s\in \mathcal{S} $$

Value function은 policy의 quality를 비교할 수 있다. 그렇다면 다음 질문은, "모든 policy 중에서 가장 좋은 policy는 존재하는가?"에 관한 것이다.

 

Finite MDP에서는 항상 하나 이상의 optimal policy가 존재하며(이후에 확인해보자), 이러한 optimal policy들이 공유하는 value function이 바로 optimal state-value function $v_*(s)$ 이다. 정의는 다음과 같다:

$$ v_*(s) = \max_{\pi} v_{\pi}(s), \quad \forall s \in \mathcal{S} $$

즉, optimal policy는 모든 state에서 long-term return이 최대가 되는 policy를 의미하며, 그 때의 value function이 $v_*$ 이다. 마찬가지로 state-action value function도 동일하게 optimal version을 정의할 수 있다:

$$ Q_*(s,a) = \max_{\pi} Q_{\pi}(s,a) $$

 

지금까지는 특정 policy를 fixed 했을 때의 value function을 정의하고 이를 recursive하게 표현할 수 있음을 확인했다. 하지만 궁극적으로 우리가 하고 싶은 것은 “policy를 optimize” 하는 것이다. 우선 그러한 optimal policy가 존재할 수 있는지, 그리고 어떤 policy가 가장 높은 long-term return을 주는지, 그리고 그러한 optimal policy를 어떻게 찾을 수 있는지에 대해 다음 포스트에서 알아보도록 하자.