07. Value Iteration

policy iteration

• Policy Iteration 이란, Policy Evaluation 과 Policy Improvement 가 계속해서 반복되는 과정.

• Policy Evaluation 은 아래의 Value function 이 수렴하도록 특정 policy $\pi$ 에 대해 Value function 으로 수렴하도록 여러 스텝을 진행.
  

• 그 후 Policy Evaluation 을 1-step 혹은 짧게 $k$-step 만 진행한다고 이야기 했다.

value iteration

• Value Iteration 이란, Policy iteration 의 한 가지 방법.
• Value Iteration 이 바로 Policy Evaluation 을 1 step 만 진행한다.
  $V_{k+1}(s) = \sum_a \sum_{s'} p(s' | s,a)\pi (a|s) \left[R(s,a,s') + \gamma V_k(s')\right] \text{for all } s \in S$
  이와 같이 Policy Evaluation 식을 1-step 만 진행한다.
  
• Policy Improvement 는 아래와 같이

  • policy improvement theorem 조건 만족.

    $\pi_{k+1}(a|s) \left \{ \begin{aligned} 1 &\quad \text{if } a = \argmax\limits_a Q^{\pi_{k}}(s, a) \\ 0 &\quad {\rm else} \end{aligned} \right.$

    Action-Value function 의 값이 제일 높은 행동을 100% 로 고르도록 Policy 를 업데이트한다.

위 두 가지 식을 결합해서 하나의 식으로 쓸 수 있다.

• 1-step policy evaluation + argmax policy improvement
  $\rightarrow V_{k+1}(s) = \max\limits_a\sum_{s'}p(s'|s,a)\left[r + \gamma V_k(s'))\right]$
  • $V_k$ 에 대해서 Action-Value function 을 최대화 하는 action 에 대한 값으로 설정.
  • 1-step policy evaluation 과 argumax policy improvement 가 합쳐져서 나온 식.
• Value Iteration 의 업데이트 식이라고 할 수 있다.

deep dive on value iteration

• Value Iteration 은 초기 Policy 가 존재하지 않는다. 초기 Value function $(\exist V_0)$ 만 존재한다.

  • $V_0 \xrightarrow{PI} \pi_0 \xrightarrow{PE} V_1 \xrightarrow{PI} \pi_1 \cdots$ $V_0$ 가 Policy Improvement 를 거쳐 $\pi_0$ 를 만들고, Policy Evaluation 을 거쳐 $V_1$ .. 반복 구조.

• $\pi_{0}(a|s) \left \{ \begin{aligned} 1 &\quad \text{if } a = \argmax\limits_a Q^{\pi_{k}}(s, a) \\ 0 &\quad {\rm else} \end{aligned} \right.$

  Action-Value function 값. $Q^{\pi_k}(s,a) = \sum\limits_{s'}p(s'|s,a)[ r + \gamma V_0(s')]$

  이 값을 최대화 하도록, $\pi_0(a|s)$ 를 모든 state 에 대해서 만들 것이다.

  $\pi_{0}(a|s) \left \{ \begin{aligned} 1 &\quad \text{if } a = \argmax\limits_a\sum\limits_{s'}p(s'|s,a)[ r + \gamma V_0(s')]\\ 0 &\quad {\rm else} \end{aligned} \right.$

• $V_1(s) = \sum\limits_a \sum\limits_{s'} p(s'|s,a)\pi_0(a|s)\left[R(s, a, s') + \gamma V_0(s')\right] \text{for all } s \in S$

  $V_1(s)$ 가 위의 식에 대해서 계산되는데, $\pi_0(a|s)$ 를 뜯어보면
  $V_1(s) = \sum\limits_a$ $\sum\limits_{s'} p(s'|s,a)$ $\pi_0(a|s)$ $\left[R(s, a, s') + \gamma V_0(s')\right]$

  이 추출된 식을 최대화 하는 행동만, 확률이 $1$ 이 된다.
  따라서 $\sum\limits_a$ 가 모든 $a$ 에 대해서 따질 필요가 없고, 이 값을 최대화 하는 행동 하나만 따지면 된다.

  $V_1(s) = \sum\limits_{a} \sum\limits_{s'}p(s'|s,a)\left[r + \gamma V_0(s') \right]$

Value Iteration 식과 동일하다. $V_1(s)$ 를 가지고 $\pi_1(s)$ 를 만들 수 있고, $V_2(s)$ 를 만들 수 있다.
이와 같이 반복적으로 하다보면, $\sum\limits_a\pi_i(a|s)$ 의 값이 똑같이 max operator 로 바뀐다.

어떤 $k$ 에 대해서도 결과적으로 Value Iteration 식이 표현된다.

• 1-step policy evaluation + argmax policy improvement 가 결합된 식이다..
  $\rightarrow V_{k+1}(s) = \max\limits_a\sum_{s'}p(s'|s,a)\left[r + \gamma V_k(s'))\right]$

pseudo code

한 번에 업데이트 하는 것처럼 식이 보인다. Value Iteration 을 표현하면 아래와 같이 표현된다.

---

Initialize $V_0(s)$ for all $s \in \mathcal{S}$
Set $\delta > 0, \Delta = \delta$ and $k = 0$
While $\Delta \geq \delta$
  Set $\Delta = 0$
  For $s \in \mathcal{S}$
   $V_{k+1}(s) = \max\limits_a\sum\limits_{a'}p(s'|s,a)[r + \gamma V_k(s')]$
   $\Delta = \max(\Delta | V_{k+1}(s) - V_{k}(s)|)$
  $k = k + 1$

Output a deterministic policy $\pi$
  For $s \in \mathcal{S}$
    $a_{\max} = \argmax\limits_a \sum\limits_{s'}p(s'|s, a)[r + \gamma V_k(s')]$
    $\pi(a_{\max}|s) = 1$

---

1. 모든 State 에서 정의 되는 Value Function 을 초기화 한다.
   Initialize $V_0(s)$ for all $s \in \mathcal{S}$

2. Value Iteration 이 충분히 수렴했는지 판별하기 위한 값인 $\delta$ 를 설정 ( threshold ).
   $k$ 는 얼마나 value iteration step 이 돌았는지 저장하는 변수.
   Set $\delta > 0, \Delta = \delta$ and $k = 0$

3. Value Iteration 이 수렴하지 않았다고 하고, value iteration 을 반복.
   While $\Delta \geq \delta$

4. $\Delta = 0$ 은 Value Function 의 변화량을 계속해서 저장할 변수.
   Set $\Delta = 0$

5. 모든 State 에 대해서 Iteration 식을 적용한다.
   For $s \in \mathcal{S}$

• 이 변화량 중에, 모든 State 에 대해서, 가장 큰 값이 $\Delta$ 에 저장.

• 이 식은 policy improvement 와 one-step policy evaluation 이 동시에 합해진 식.
    $V_{k+1}(s) = \max\limits_a\sum\limits_{a'}p(s'|s,a)[r + \gamma V_k(s')]$

• $\Delta$ 의 Value Function 의 변화량 중 가장 큰 값을 저장하기 위해 $\max$ 를 취해 $\Delta$ 를 업데이트.
    $\Delta = \max(\Delta | V_{k+1}(s) - V_{k}(s)|)$

6. 모든 State 에 대해서 이 과정이 끝나면, $k$ 를 $1$ 증가 시켜준다.
    $k = k + 1$

Value Function 의 변화량이 크지 않을 때, threshold 미만으로 떨어졌을 때.
Output a deterministic policy $\pi$ : deterministic policy $\pi$ ( optimal policy ) 를 출력.

 For $s \in \mathcal{S}$
이때 얻게되는 value function 이 Optimal Value function 이라고 생각할 수 있다.
   $a_{\max} = \argmax\limits_a \sum\limits_{s'}p(s'|s, a)[r + \gamma V_k(s')]$
   $\pi(a_{\max}|s) = 1$

---

• 모든 State 에 대해서, 마지막으로 얻은 Value Function 을 최대화하는 행동을 얻고,
• 그 행동에 대해서만 그 State 에서 확률을 $1$ 로 설정해준다.

이러면 나머지 모든 행동에 대한 확률은 자동으로 $0$ 이 된다. 확률은 모든 행동에 대해서 합하면 $1$ 이 되어야 하기 때문이다. 이렇게 해서 최종적으로 Optimal Policy 와 Optimal Value function 을 출력해준다.

Policy Evaluation 을 한 스텝만 진행하면서 Policy Improvement 를 진행하는 이 과정을 계속해서 반복하면, Optimal Value Function 을 얻을 수 있을까?

possible in just 1-step?

Value Iteration 은 Policy Evaluation 을 1-step 만 진행함.

• 그럼에도 불구하고, optimal policy 와 optimal value function 으로 수렴.

Value Iteration 업데이트 식은 아래와 같다.

$V_k$ 을 가지고 $V_{k+1}$ 을 만들었다. $V_k$ 가지고 얻을 수 있는 action value 중에 가장 큰 값을 $V_{k+1}$ 에 Value 로 설정해주었다. 이것을 모든 state 에 대해서 반복했다.

• 모든 state 에 대한 value function $V_k$ 로부터 $V_{k+1}$ 을 얻는 함수 (mapping) 을 $T^{*}$ 라 표현 하면 아래와 같이 표현 가능하다.
  $V_{k+1} = T^{*}(V_k), \quad V_k \in \mathbb{R}^{n}$
  한 state 에 대한 value function 이 아니라, 모든 state 에 대한 value function 을 나타내는 이 vector $V_k$ 가 $T^{*}$ 를 거쳐서 $V_{k+1}$ 이 된다.

  이 과정을 모든 state 에서 반복한 것을 $T^{*}$ 라고 표현한 것.

• 이때 (complete) metric space $(\mathbb{R}^n, d_\infin)$ 에 대해 $T^{*}$ 는 contraction mapping 이다. → Contraction mapping theorem 적용 가능!
  $\begin{aligned} d_{\infin}(x,y) &= \parallel x-y \parallel_\infin \\ &= \lim\limits_{p \rightarrow \infin} \left( |x_1 - y_1|^p + \cdots + |x_n - y_n|^{p}\right)^{\frac{1}{p}} \\ &= \max \left(|x_1 - y_1|, \cdots, |x_n - y_n|\right) \end{aligned}$
  어느 두 점 사이의 거리에 대한 metric 으로 사용될 수 있다.

contraction mapping

• Contraction mapping theorem 이란?
  Let $(X, d)$ be a complete metric space with a contraction mapping $T:X \rightarrow X$.
  Then ( 이 2 개가 Contraction mapping theorem 의 명제 )

  1. there exists a unique vector $x^{*}$ satisfying $x^{*} = T(x^{*})$

     • 유일한 fixed point $x^{*}$ 를 갖는다. transformation 을 적용해도, 값이 같다.

  2. $x^{*}$ can be obtained from an arbitrary point $x_0 = T(x^*)$
     Define $x_{n+1} = T(x_n)$
     then $\lim\limits_{n \rightarrow \infin} x_n = x^{*}$.

     • transformation 을 임의의 점에서 시작하여, 무한히 계속 적용하면 결국에는 $x^{*}$, fixed point 로 수렴한다.

• Contraction mapping theorem 에 의해 아래의 결과가 성립.

  1. $T^{*}$ 의 유일한 fixed point 는 optimal value function $V^{*}$ 이다.

  2. $\lim\limits_{k \rightarrow \infin}V_k = V^*$

  • 시작점은 어느 지점이든 간에 상관 없다. 어떻게 초기화된 Value Function 에서 시작해도,
  • 계속해서 $T^{*}$ 를 적용하면, 결과적으로 Optimal Value Function 을 얻을 수 있다.

그래서 Value Iteration 을 계속 반복하면 Optimal Value Function 으로 수렴한다.

$T^{*}$ 가 $(\mathbb{R}^{n}, d_\infin)$ 에서 contraction mapping 인가?

$V_{k+1}(s) = \max\limits_{a}\sum\limits_{s'}p(s'|s,a)[r + \gamma V_k(s')] \text{ for all } s \in \mathcal{S}$

$\longrightarrow T^{*}(V_k)(s) = \max\limits_{a}\sum\limits_{s'}p(s'|s,a)[r + \gamma V_k(s')]$

contraction mapping 이 되는지 확인해보자.

• 임의로 초기화 된 두 Value Vector 가 있다고 가정하자.

$V^{1}, V^{2}$ 여기서 $\left| T^{*}\left(V^{1}(s)\right) - T^{*}\left(V^{2}(s)\right) \right|$ 차이의 절대 값을 살펴보자.

mathematical proof

---

$\left| \; T^{*}(V^{1}(s)) - T^{*}(V^{2}(s)) \; \right|$

$\; = \; \left| \; \max\limits_a \sum\limits_{s'}p(s'|s,a)[r + \gamma V^{1}(s')] - \max\limits_{a}\sum\limits_{s'} p\left( s'|s,a \right)[r + \gamma V^{2}(s')] \; \right|$

---

1. $T^{*} \left(V^{1}(s)\right) \geq T^{*}(V^{2}(s)) \geq C_2$

• $\left| \; T^{*}\left(V^{1}(s)\right) - C_2 \; \right| \geq \left| \; T^{*}\left(V^{1}(s)) - T^{*}(V^2(s)\right) \; \right|$

• $a_{\max}^{1} = \argmax\limits_{a} \sum\limits_{s'} p(s'|s,a) [r + \gamma V^{1}(s')]$

• 뒤의 항 $\max\limits_{a}\sum\limits_{s'} p\left( s'|s,a \right)[r + \gamma V^{2}(s')]$ 을 최대화로 만드는 행동은 따로 있는데, 대신 $a^{1}_{\max}$ 로 최대화 하는 행동을 넣으면 원래 값보다 작아지게 된다.

• 앞의 항에 대해서는 최대화 하는 행동은 당연히 $a_{\max}^{1}$ 이 된다.

$T^{*}(V^{1}(s)) \geq T^{*}(V^{2}(s)) \geq$ $\sum\limits_{s'}p(s'|s,a^{1}_{\max})[r + \gamma V^{2}(s')]$

$A \geq B \geq C$ 일 때, $|A-B| \leq |A-C|$ 가 되는데, 사이가 더 벌어졌기 때문이다.

$\left| \; T^{*} (V^{1}(s)) - T^{*}(V^{2}(s)) \; \right| \leq \left| \; T^{*} (V^{1}(s)) - C_{2} \; \right|\\ = \left| \; T^{*}(V^{1}(s)) - \sum\limits_{s'}p(s'|s,a^{1}_{\max})[r + \gamma V^{2}(s')] \; \right| \\ = \left| \; \sum\limits_{s'}p\left(s'|s, a^{1}_{\max}\right) [r + \gamma V^{1}(s')] - \sum\limits_{s'}p(s'|s,a^{1}_{\max})[r + \gamma V^{2}(s')\; \right| \\ = \gamma \left| \sum\limits_{s'} p(s'|s,a_{\max}^{1}) \left[ V^{1}(s') - V^{2}(s')\right] \right|$

• 원래 $V^{1}(s') - V^{2}(s')$ 은 양수 혹은 음수가, $\sum\limits_{s'}p(s'|s,a_{\max}^{1})$ 이런 식으로 평균 내어진 것.
• 이 값을 전부 양수로 바꾸어 버리면, 평균 값도 크거나 같아지게 된다.

$\leq \gamma \sum\limits_{s'} p(s'|s,a_{\max}^{1}) \left| V^{1}(s') - V^{2}(s') \right|$ : [ 차이 값의 평균 ]
$\leq \gamma \max\limits_{s'} \left| V^{1}(s') - V^{2}(s') \right|$ : [ 차이 값 중에 가장 큰 것 ]
$= \gamma\parallel V^{1} - V^{2} \parallel_{\infin}$ : [ vector 의 표현이므로 $s'$ 이 빠지게 된다. ]

---

2. $C_1 \leq T^{*}(V^{1}(s)) \leq T^{*}(V^2(s))$

$C \leq A \leq B$ 일 때, $| A - B | \leq | C - B |$ 가 되는데, 위와 마찬가지로 사이가 더 벌어졌기 때문.

$| \; T^{*}(V^{1}(s)) - T^{*}(V^{2}(s)) \;| \leq | \; C_1 - T^{*}(V^{2}(s)) \; |$

$| \; T^{*}(V^{1}(s)) - T^{*}(V^{2}(s)) \;| \\ = \left| \max\limits_{a}\sum\limits_{s'} p(s'|s,a)\left[r + \gamma V^{1}(s')\right] - \max\limits_a \sum\limits_{s'} p(s'|s,a)\left[r + \gamma V^{2}(s')\right]\right|$

• $a_{\rm max}^{2} = \argmax\limits_{a} \sum\limits_{s'}p(s'|s,a)\left[ r + \gamma V^{2}(s') \right]$

• $\sum\limits_{s'} p(s'|s,a_{\rm max}^{2})[r + \gamma V^{1}(s')] \leq T^{*}(V^{1}(s))$
  $T^{*}(V^{1}(s)) = \max\limits_{a}\sum\limits_{s'} p(s'|s,a)\left[r + \gamma V^{1}(s')\right]$ 를 보면, 최대화 하도록 행동을 고른다.
  

• 앞의 항 $\max\limits_a \sum\limits_{s'} p(s'|s,a)\left[r + \gamma V^{1}(s')\right]$ 를 최대화로 만드는 행동은 따로 있는데, 대신 $a^{2}_{\rm max}$ 로 최대화 하는 행동을 넣으면, 원래 값보다 작아지게 된다.

• 뒤의 항에 대해서는 최대화 하는 행동은 당연히 $a_{\max}^{2}$ 가 된다.

$\left| \; T^{*} (V^{1}(s)) - T^{*}(V^{2}(s))\; \right| \leq \left| C_1 - T^{*}(V^{2}(s)) \right| \\ = \left| \sum\limits_{s'}p\left(s'| s,a_{\max}^{2} \right)[r + \gamma V^{1}(s')] - T^{*}\left(V^{2}(s)\right)\right| \\ = \left| \; \sum\limits_{s'}p\left(s'| s,a_{\max}^{2} \right)[r + \gamma V^{1}(s')] - \sum\limits_{s'}p\left(s'|s,a_{\max}^{2}\right)[r + \gamma V^{2}(s')]\; \right| \\ \leq \gamma \left| \; \sum\limits_{s'} p(s' | s, a_{\max}^{2})[V^{1}(s') - V^{2}(s')] \right|$

• $V^{1}(s') - V^{2}(s')$ 양수 혹은 음수가, $\gamma \sum\limits_{s'}p(s'|s, a_{\max}^{2})$ 이런 식으로 평균 내어진 것.
• 이 값을 전부 양수로 바꾸어 버리면, 평균 값도 거 크거나 같아지게 된다.

$\leq \gamma \sum\limits_{s'}p(s'|s, a_{\max}^{2}) \left| V^{1}(s') - V^{2}(s') \right|$ : [ 차이 값의 평균 ]
$\leq \gamma \max\limits_{s'} \left| V^{1}(s') - V^{2}(s') \right|$ : [ 차이 값 중에 가장 큰 것 ]
$= \gamma\parallel V^{1} - V^{2} \parallel_{\infin}$ : [ vector 의 표현이므로 $s'$ 이 빠지게 된다. ]

conclusion

따라서 결론적으로

이건 특정 state $s$ 가 정해진 것이 아니라, 임의의 state $s$ 에 대해서 항상 성립 하는 것.

• $\parallel T^{*}(V^{1}) - T^{*}(V^2) \parallel_{\infin}$ 중 제일 큰 것,

즉, $\left| \; T^{*}(V^{1}(s)) - T^{*}(V^{2}(s)) \; \right|$ 여기서 $s$ 가 될 수 있는 값 중에 제일 큰 것을 가져와도,

• $\parallel T^{*}(V^{1}) - T^{*}(V^2) \parallel_{\infin} \; \leq \; \gamma \parallel V^{1} - V^{2} \parallel_{\infin}$ 이 성립한다.

여기서 $T^{*}$ 가 의미하는 것은 $( \mathbb{R}^n, d_{\infin})$ 에 대해서, Contraction Mapping 이 된다.

Transformation 을 거친 두 점 사이의 거리,

여기서 $0 \leq \gamma < 1$ 로 설정되면, Contraction Mapping 이 될 수 있다. 그래서, $T^{*}$ 즉, Value Iteration 에 쓰이는 Mapping 이 Contraction Mapping 이라는 것을 확인했다.