가치 이터레이션 (Value Iteration)

정책 이터레이션에서는 정책 평가 단계 시에 가치함수를 수렴할 때까지 수차례 반복 계산하였다. 그리고 수렴된 가치함수를 이용하여 정책 개선을 수행하였다.

 

 

만약 정책 평가 단계 시에 가치함수를 한 번만 계산하고 수렴되지 않은 상태로 바로 정책 개선 단계로 넘어가면 어떨까. 즉, 식 (1)과 같이 정책 \(\pi_i\) 에 대한 정책 평가를 한 단계만 수행한 후,

 

\[ \begin{align} & V_{i+1}^{\pi_i} (\mathbf{x}_t )= r_t+ \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma V_i^{\pi_i } (\mathbf{x}_{t+1} ) \right] \tag{1} \\ \\ & Q_{i+1}^{\pi_i} (\mathbf{x}_t, \mathbf{u}_t )= r_t+ \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma Q_i^{\pi_i } (\mathbf{x}_{t+1}, \mathbf{u}_{t+1} ) \right] \end{align} \]

 

식 (2)와 같이 바로 정책 개선을 수행하는 것이다.

 

\[ \begin{align} \pi_{i+1} &= \arg \max_{\mathbf{u}_t} Q_{i+1}^{\pi_i} (\mathbf{x}_t, \mathbf{u}_t ) \tag{2} \\ \\ & = \arg \max_{\mathbf{u}_t} \left[ r_t+ \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma V_{i+1}^{\pi_i } (\mathbf{x}_{t+1} ) \right] \right] \end{align} \]

 

그리고 다시 업데이트된 정책 \(\pi_{i+1}\) 의 평가를 수행하는 것이다. 그래도 괜찮을까.

 

 

괜찮은지 알아보기 위해서 식 (1)과 (2)를 한 개의 식으로 합쳐보자.

식 (2)를 (1)에 대입하면 정책 평가 단계는 다음과 같이 된다.

 

\[ \begin{align} & V_{i+1} (\mathbf{x}_t )= \max_{\mathbf{u}_t} \left[ r_t+ \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma V_i (\mathbf{x}_{t+1} ) \right] \right] \tag{3} \\ \\ & Q_{i+1} (\mathbf{x}_t, \mathbf{u}_t )= r_t+ \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma \max_{\mathbf{u}_{t+1}} Q_i (\mathbf{x}_{t+1}, \mathbf{u}_{t+1} ) \right] \end{align} \]

 

식 (3)을 이용하여 가치함수가 수렴할 때까지 반복하여 계산하는 방법을 가치 이터레이션(value iteration)이라고 한다.

 

 

가치 이테레이션은 정책 이터레이션과는 다르게 수식에 명시적인 정책이 보이지 않는다. 따라서 반복 계산 중에 있는 가치함수는 어떤 특정 정책에 속한 가치함수라고 보기 힘들다.

식 (3)의 계산이 수렴한다면 그 때의 가치함수를 최적 가치함수라고 한다. 최적 정책은 최적 가치 함수로부터 다음과 같이 계산하면 된다.

 

\[ \begin{align} \pi^\star (\mathbf{x}_t ) &= \arg \max_{\mathbf{u}_t} Q^\star ( \mathbf{x}_t, \mathbf{u}_t) \tag{4} \\ \\ &= \arg \max_{\mathbf{u}_t} \left[ r_t+ \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t ) } \left[ \gamma V^\star (\mathbf{x}_{t+1}) \right] \right] \end{align} \]

 

한편 식 (3)을 살펴보면 구조가 식 (5)로 주어지는 상태가치 함수와 행동가치 함수에 대한 벨만 최적 방정식을 이터레이션 방법으로 계산하는 것과 동일하다는 것을 알 수 있다.

 

\[ \begin{align} & V^\star (\mathbf{x}_t )= \max_{\mathbf{u}_t} \left[ r_t+ \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma V^\star (\mathbf{x}_{t+1} ) \right] \right] \tag{5} \\ \\ & Q^\star (\mathbf{x}_t, \mathbf{u}_t )= r_t+ \mathbb{E}_{ \mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t) } \left[ \gamma \max_{\mathbf{u}_{t+1}} Q^\star (\mathbf{x}_{t+1}, \mathbf{u}_{t+1} ) \right] \end{align} \]

 

따라서 가치 이터레이션은 벨만 최적 방정식을 이용하여 최적 가치함수를 반복적인 방법으로 계산하는 것이라고 할 수 있다. 이와 같이 가치 이터레이션을 최적 가치함수를 계산하는 과정이라고 해석한다면, 반복 계산 중에 있는 가치함수를 최적 가치함수의 중간단계 추정값으로 해석할 수 있을 것이다.

 

 

그렇다면 가치 이터레이션은 과연 특정한 정책과 가치함수로 수렴할까. 식 (3)의 수렴 여부를 따져보는 것이 필요하므로, 우선 다음과 같이 연산자 \(\mathcal{B}\) 를 도입한다.

 

\[ \mathcal{B} V = \max_{\mathbf{u}} \left[ r(\mathbf{x}, \mathbf{u}) + \mathbb{E}_{ \mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u} ) } \left[ \gamma V (\mathbf{x}^\prime ) \right] \right] \tag{6} \]

 

연산자 \(\mathcal{B}\) 를 벨만 백업(Bellman backup)이라고 한다. 만약 벨만 백업을 두 개의 서로 다른 상태가치 함수에 적용했을 때 두 상태가치 함수의 거리(distance)가 더 줄어든다면, 식 (3)은 이터레이션이 진행되면서 수렴할 것이다. 두 상태가치 함수의 거리는 \(\infty\)-놈(norm)을 사용한다.

 

\[ \lVert V- V^\prime \rVert_\infty = \max_{\mathbf{x}} \left\vert V (\mathbf{x})- V^\prime (\mathbf{x} ) \right\vert \tag{7} \]

 

그러면 두 개의 서로 다른 상태가치 함수의 벨만 백업의 거리는 다음과 같다.

 

\[ \begin{align} \lVert \mathcal{B} V - \mathcal{B} V^\prime \rVert_\infty &= \lVert \max_{\mathbf{u}} \left[ r(\mathbf{x}, \mathbf{u}) + \mathbb{E}_{ \mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u} ) } \left[ \gamma V (\mathbf{x}^\prime ) \right] \right] \\ & \ \ \ \ \ \ \ \ \ \ - \max_{\mathbf{u}} \left[ r(\mathbf{x}, \mathbf{u}) + \mathbb{E}_{ \mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u} ) } \left[ \gamma V^\prime (\mathbf{x}^\prime ) \right] \right] \rVert_\infty \tag{8} \\ \\ & \le \max_{\mathbf{u}} \lVert r(\mathbf{x}, \mathbf{u}) + \mathbb{E}_{ \mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u} ) } \left[ \gamma V (\mathbf{x}^\prime ) \right] \\ & \ \ \ \ \ \ \ \ \ \ - r(\mathbf{x}, \mathbf{u}) - \mathbb{E}_{ \mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u} ) } \left[ \gamma V^\prime (\mathbf{x}^\prime ) \right] \rVert_\infty \\ \\ &= \max_{\mathbf{u}} \lVert \gamma \mathbb{E}_{ \mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u} ) } \left[ V (\mathbf{x}^\prime ) - V^\prime (\mathbf{x}^\prime ) \right] \rVert_\infty \\ \\ & \le \max_{\mathbf{u}} \lVert \gamma \mathbb{E}_{ \mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u} ) } \lVert V - V^\prime \rVert_\infty \rVert_\infty \\ \\ &= \max_{\mathbf{u}} \lVert \gamma \lVert V - V^\prime \rVert_\infty \mathbb{E}_{ \mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u} ) } [1] \rVert_\infty \\ \\ &= \gamma \lVert V - V^\prime \rVert_\infty \end{align} \]

 

\(\gamma \lt 1\)이라면 \( \lVert \mathcal{B} V- \mathcal{B} V^\prime \rVert_\infty \lt \lVert V-V^\prime \rVert_\infty\) 이 성립한다. 이와 같이 어떤 연산자를 적용했을 때 두 함수의 거리가 본래 보다 더 가까워진다면 그 연산자를 축약(contraction) 연산자라고 한다. 여기서는 축약 성질이 \(\gamma\)값에 의존하기 때문에 벨만 백업 연산자를 \(\gamma -\)축약 연산자라고 한다.

벨만 백업 연산자를 이용하면 식 (3)을 다음과 같이 표현할 수 있으므로

 

\[ V_{i+1}=\mathcal{B} V_i \tag{9} \]

 

식 (3)을 통해 가치함수를 업데이트할 수록 점점 어떤 포인트로 수렴하게 된다는 것을 알 수 있다.