2. Bellman equation and MDP

1. Bellman equation for MRP

$V(s) = E[G_{t}|s_{t}=s]$

             $= E[r_{t}+\gamma r_{t+1}+\gamma^{2}r_{t+2}+...|s_{t}=s]$

             $= E[r_{t}+\gamma G_{t+1}|s_{t}=s]$

             $= E[r_{t}|s_{t}=s] + \gamma E[E[G_{t+1}|s_{t+1}]|s_{t}=s]$

             $= R(s) + \gamma E[V(s_{t+1})|s_{t}=s]$

 

$V(s) = R(s) + \gamma E[V(s_{t+1})|s_{t}=s]$

 

$V = R + \gamma T V$

$(1-\gamma T)V = R$

$V = (1-\gamma T)^{-1}R$

 

위 식을 통해 state-value funtion을 구할 수 있다. 그러나 $o(n^{3})$의 시간 복잡도가 소요된다. 이를 해결하기 위해 Dynamic programming을 사용한다.

 

 

2. DP for solving Bellman equation for MRP

• $V_{0}(s)$=0 으로 초기화
• $V_{k}(s) = R(s) + \gamma \sum_{s_{2} c S} T_{ss_{2}} V_{k-1}(s_{2})$
• 수렴할 때까지 반복

$o(n^{2})$의 시간 복잡도가 소요된다.

*참고 - 수렴하는 이유

---

$V_{k} = R + \gamma TV_{k-1}$

          $= R + \gamma T(R + \gamma TV_{k-2})$

          $= R(1+\gamma T+...+(\gamma T)^{k-1}) + (\gamma T)^{k}V_{0}$

{$0<\gamma<1, 0<T<1$}

$V_{k}$ = $R(1+\gamma T+...+(\gamma T)^{k-1})$ + $(\gamma T)^{k}V_{0}$

$V_{k-1}$ = $R(1+\gamma T+...+(\gamma T)^{k-2})$ + $(\gamma T)^{k-1}V_{0}$

$V_{k} - V_{k-1}$ = $(\gamma T)^{k-1}R$ + $(\gamma T)^{k-1}(\gamma T-1)V_{0}$

 

코시수열 $V_{k}$ $-V_{k-1}$이 0임을 보이면 V는 수렴하게 된다.

$0<\gamma<1, 0<T<1$이면 수렴함이 자명하다.

만약 $\gamma=1$이라면 $0<T<1$이면 수렴하고, T=1이면 코시수열의 차이가 좁혀지지 않아 수렴하지 않는다.

---

 

 

3. Value function for MDP (with policy $\pi$)

 - State-value function

First action이 정해져 있다. 그 뒤로는 policy의 action을 따라간다.

$Q^{\pi}(s,a) = R(s,a) + \gamma E_{\pi}[V^{\pi}(s_{t+1})|s_{t}=s, a_{t}=a]$

                     $= R(s,a) + \gamma E_{\pi}[Q^{\pi}(s_{t+1}, \pi(a|s_{t+1}))|s_{t}=s, a_{t}=a]$

 

 - Action-value function

처음부터 policy의 action을 따라간다.

$V^{\pi}(s) = R(s, \pi(a,s)) + \gamma E_{\pi}[V^{\pi}(s_{t+1})|s_{t}=s]$

 

 - For discrete MDP

$Q^{\pi}(s,a) = R(s,a) + \gamma \sum_{s'}p(s'|s,a)V^{\pi}(s')$

$V^{\pi}(s) = R^{\pi}(s) + \gamma \sum_{s'}p(s'|s,a)V^{\pi}(s')$

$V^{\pi}(s) = \sum_{a} \pi(a|s)Q^{\pi}(s,a)$

 

 

4. Policy Evaluation for MDP

Bellman equation으로 다음을 사용한다.

$Q^{\pi}(s,a) = R(s,a) + \gamma \sum_{s'}p(s'|s,a)Q^{\pi}(s',a')$

$Q^{\pi}(s,a) = R(s,a) + \gamma \sum_{s'}p(s'|s,a)V^{\pi}(s')$

$V^{\pi}(s) = R^{\pi}(s) + \gamma \sum_{s'}p(s'|s,a)V^{\pi}(s')$

 

MRP와 마찬가지로 DP를 이용해 state-value function을 구한다.

• $V^{\pi}_{0} = 0$ for all V
• $V^{\pi}_{k}(s) = R^{\pi}(s) + \gamma \sum_{s'}p(s'|s,\pi(a|s))V^{\pi}_{k-1}(s')$

 

 

5. Finding Optimal Policy

모든 value function을 maximize하는 policy를 구한다.

$V^{*}(s) = max_{\pi}V^{\pi}(s)$

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

 

$\pi^{*}(s) = argmax_{\pi}V^{\pi}(s)$

 

Optimal policy는 unique하지 않다. 값이 같지만, policy가 다를 수 있다.

Deterministic, stochastic policy 모두 optimal이 될 수 있다.

만약 유한한 action과 state를 가진다면, 계산량은 $|A|^{|S|}$이다.

 

 

6. Relation of Two Optimality Value Functions

$V^{*}(s) = max_{\pi}V^{\pi}(s) = max_{a}Q^{\pi}(s,a)$

$Q^{*}(s,a) = R(s,a) + \gamma E_{\pi}^{*}[V^{*}(s_{t+1})|s_{t}=s, a_{t}=a]$

$V^{*}(s) = max_{a}R(s,a) + \gamma E_{\pi^{*}}[V^{*}(s_{t+1})|s_{t}=s, a_{t}=a^{*}]$

where $a^{*} = argmax_{a}R(s,a)$

 

 

 

7. 기억할 것들

*Bellman Expectation Equation

State-Value function

$V^{\pi}(s) = E^{\pi}[G_{t} | S_{t} = s]$ $V^{\pi}(s) = E^{\pi}[R(s) + \gamma V^{\pi}(s_{t+1}) | S_{t} = s]$ $V^{\pi}(s) = \sum_{a} \pi(s, a) Q^{\pi}(s, a)$ $Q^{\pi}(s, a) = R(s, a) + \gamma \sum_{s'} P(s'|s, a)V^{\pi}(s')$ $V^{\pi}(s) = \sum_{a} \pi(s, a)(R(s, a) + \gamma \sum_{s'} P(s'|s, a)V^{\pi}(s'))$

Action-Value function

$Q^{\pi}(s, a) = R(s, a) + \gamma \sum_{s'} P(s'|s, a)V^{\pi}(s')$

 

 

*Bellman Optimality Equation

$V^{*}(s) = max_{\pi}V^{\pi}(s)$, $Q^{*}(s,a) = max_{\pi}Q^{\pi}(s,a)$

State-Value function

$V^{*}(s) = max_{\pi}V^{\pi}(s) = max_{a}Q^{\pi}(s,a)$ $V^{*}(s) = max_{a}(R(s,a) + \gamma \sum_{s'} P(s'|s, a)V^{\pi}(s'))$ $V^{*}(s) = max_{a}R(s,a) + \gamma \sum_{s'} P(s'|s, a)V^{*}(s')$

Action-Value function

$Q^{*}(s,a) = max_{\pi}Q^{\pi}(s,a) = max_{\pi}(R(s,a) + \gamma \sum_{s'} P(s'|s, a)V^{\pi}(s'))$ $Q^{*}(s,a) = R(s,a) + \gamma \sum_{s'} P(s'|s, a)V^{\pi}(s'))$