[Markov Decision Process - 4] Bellman Equation

State value and Q-value

State value($v_\pi(s)$)

: State value function는 해당 State에서 end of episode(종료 조건 만족) 까지 가는데 얻어지는 Expected return이다.

 

$$ v_\pi(s) = \mathbb{E}[G_t|S_t = s] $$

$$ v_\pi(s) = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+2} + ... + \gamma^{T-t-1}R_\gamma|S_t = s] $$

 

Q-value(=Action value)($q_\pi(s, a)$)

: Q-value(=Action value)는 해당 특정 state에서 특정 action을 행했을 때 end of epsiode까지 가는데 얻어지는 Expected return이다.

 

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

$$ q_\pi(s, a) = \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+2} + ... + \gamma^{T-t-1}R_\gamma|S_t = s, A_t = a] $$

 

State value는 해당 State에서 가능한 action들에 대한 Q-value 기대값이다.

Bellman equations

: Bellman equation은 control tasks를 풀기위한 optimal policy를 찾는데 아주 중요한 개념이다.

• Bellman equation의 의미 : Bellman equation 은 현재의 v 혹은 q를 다음 시점의 v혹은 q로 표현하는 방정식이다. (재귀적)

Bellman equation for State value

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

유도과정

 

$v_\pi(s) = \mathbb{E}[G_t|S_t = s]$

 

$= \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+2} + ... + \gamma^{T-t-1}R_t|S_t = s]$

 

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

 

State value는 해당 State에서 가능한 action들에 대한 Q-value 기대값

 

$= \sum_a{\pi(a|s)\mathbb{E}[R_{t+1}+\gamma G_{t+1} | S_t = s, A_t = a}]$

 

$= \sum_a{\pi(a|s)\sum_{s', r}{p(s',r|s,a)[r + \gamma \mathbb{E}[G_{t+1} | S_{t+1} = s']]}}$

 

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

 

이는 $v_\pi(s)$에 대한 재귀적인 식이며, 이는 알고리즘을 개발하는데 아주 유용하다.

Bellman equation for Q-value

$q_\pi(s,a) = \sum_{s',r}p(s',r|s,a)[r+\gamma\sum_{a'}\pi(a'|s')q_\pi(s',a')]$

유도과정

 

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

 

$= \mathbb{E}[R_{t+1} + \gamma R_{t+2} + \gamma^2R_{t+2} + ... + \gamma^{T-t-1}R_t|S_t = s, A_t = a]$

 

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

 

$= \sum_{s',r}p(s',r|s,a)[r+\gamma\sum_{a'}\pi(a'|s')q_\pi(s',a')]$

 

이는 $q_\pi(s,a)$에 대한 재귀적인 식이며, 이는 알고리즘을 개발하는데 아주 유용하다.

Solving a Markov decision process

State의 optimal value는 optimal policy에서의 expected return이다. 이를 식으로 표현하면 아래와 같다.

 

$$ v_*(s) = E_{\pi_*}[G_t|S_t=s] $$

 

$$ q_*(s,a) = E_{\pi_*}[G_t|S_t = s, A_t = a] $$

 

Optimal policy($\pi_*$)는 $v(s)$ or $q(s,a)$를 maximize하는 policy이다.

• 아래 식은 각각 state value/q-value를 maximize 하는 식이며, $\arg\max_a$는 $\pi_*(s)$가 뒤의 식을 maximise하는 $a$를 결정하는 정책이라는 뜻이다.

$$ \pi_*(s) = \arg\max_a\sum_{s',r}p(s',r|s,a)[r+\gamma v_*(s)] $$

$$ \pi_*(s) = \arg\max_a q_*(s,a) $$

 

여기서 문제가 생긴다. optimal value를 알려면 optimal policy가 필요하고 optimal policy를 알려면 optimal value를 알야아한다. (닭이 먼저냐, 계란이 먼저냐) 따라서 우리는 optimal value / optimal policy를 하나가 다른 하나에 의존하는 식으로 만들고 싶다.

 

이 문제를 해결하기 위해 사용하는 것이 Bellman equation이다.

Bellman optimality equations

위의 문제상황을 해결하기 위해 Bellman equation으로 돌아가보자. 아래의 식은 Optimal Policy 상황에서의 Bellman equations인, Bellman optimality equations이다. 이후 포스팅할 DP에서 이 2가지 공식을 통해 Optimal Policy와 Optimal value를 반복적으로 찾는 방법을 알아볼 것이다.

 

$$ v_*(s) = \max_a \sum_{s',r}p(s',r|s,a)[r+\gamma v_*(s')] $$

$$ q_*(s,a) = \sum_{s',r} p(s',r|s,a)[r+\gamma \max_{a'} q_*(s',a')] $$