소프트 정책 이터레이션

어떤 정책 \(\pi_{old}\) 에 대해서 행동가치 함수가 주어지면 기존의 정책 보다 더 큰 행동가치 값을 갖는 새로운 정책 \(\pi_{new}\) 를 계산할 수 있다. 이 과정을 정책 개선(policy improvement)이라고 한다.

 

 

그렇다면 최대 엔트로피 목적함수 문제에서 도입한 식 (1)의 탐욕적 정책으로

 

\[ \pi (\mathbf{u}_t | \mathbf{x}_t ) = \frac{ \exp⁡ \left( \frac{1}{\alpha} Q_{soft}^\pi (\mathbf{x}_t, \mathbf{u}_t ) \right) }{ \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_{soft}^\pi (\mathbf{x}_t, \mathbf{u}^\prime ) \right) d \mathbf{u}^\prime } \tag{1} \]

 

정책을 \(\pi_{old} \) 에서 \(\pi_{new}\) 로 업데이트하면 소프트 행동가치의 값이 증가, \(Q_{soft}^{\pi_{new}} (\mathbf{x}_t, \mathbf{u}_t ) \ge Q_{soft}^{\pi_{old}} (\mathbf{x}_t, \mathbf{u}_t ) \), 하는지 증명해 보자.

증명은 식 (2)의 소프트 벨만 방정식에서 출발한다.

 

\[ \begin{align} Q_{soft}^{\pi_{old}} (\mathbf{x}_t, \mathbf{u}_t ) &= r_t + \gamma \ \mathbb{E}_{\mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t | \mathbf{u}_t ), \ \mathbf{u}_{t+1} \sim \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \tag{2} \\ & \ \ \ \ \ \ \ \ \ \ \left[ Q_{soft}^{\pi_{old}} (\mathbf{x}_t, \mathbf{u}_t ) - \alpha \log \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) \right] \end{align} \]

 

식 (1)을 식 (2)의 기댓값 연산자 안에 있는 항에 대입하면,

 

\[ \begin{align} & \mathbb{E}_{\mathbf{u}_{t+1} \sim \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \begin{bmatrix} \alpha \log \pi_{new} (\mathbf{x}_{t+1} | \mathbf{u}_{t+1} ) \\ + \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_{soft}^\pi (\mathbf{x}_t, \mathbf{u}^\prime ) \right) d \mathbf{u}^\prime \\ - \alpha \log \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) \end{bmatrix} \tag{2} \\ \\ & \ \ \ = \mathbb{E}_{\mathbf{u}_{t+1} \sim \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \begin{bmatrix} \alpha \log \frac{ \pi_{new} (\mathbf{x}_{t+1} | \mathbf{u}_{t+1} ) }{ \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \\ + \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_{soft}^\pi (\mathbf{x}_t, \mathbf{u}^\prime ) \right) d \mathbf{u}^\prime \end{bmatrix} \\ \\ & \ \ \ = -\alpha D_{KL} \left( \pi_{old} (\mathbf{x}_{t+1} | \mathbf{u}_{t+1} ) \parallel \pi_{new} (\mathbf{x}_{t+1} | \mathbf{u}_{t+1} ) \right) \\ \\ & \ \ \ \ \ \ \ \ \ \ + \alpha \mathbb{E}_{\mathbf{u}_{t+1} \sim \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \left[ \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_{soft}^\pi (\mathbf{x}_t, \mathbf{u}^\prime ) \right) d \mathbf{u}^\prime \right] \\ \\ & \ \ \ \le \mathbb{E}_{\mathbf{u}_{t+1} \sim \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \left[ \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_{soft}^\pi (\mathbf{x}_t, \mathbf{u}^\prime ) \right) d \mathbf{u}^\prime \right] \end{align} \]

 

이 된다. 위 식의 마지막 줄은 \(\mathbf{x}_{t+1}\) 의 함수이므로 기대값을 \(\pi_{new } \) 기준으로 계산해도 결과는 동일하다.

 

\[ \begin{align} & \ \ \ = \mathbb{E}_{\mathbf{u}_{t+1} \sim \pi_{new} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \left[ \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_{soft}^\pi (\mathbf{x}_t, \mathbf{u}^\prime ) \right) d \mathbf{u}^\prime \right] \\ \\ & \ \ \ = \mathbb{E}_{\mathbf{u}_{t+1} \sim \pi_{new} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \left[ Q_{soft}^{\pi_{old}} (\mathbf{x}_t, \mathbf{u}_t ) - \alpha \log \pi_{new} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) \right] \end{align} \]

 

따라서 식 (3)에 의하면 다음 부등식이 성립한다.

 

\[ \begin{align} & \mathbb{E}_{\mathbf{u}_{t+1} \sim \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \left[ Q_{soft}^{\pi_{old}} (\mathbf{x}_t, \mathbf{u}_t ) - \alpha \log \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) \right] \tag{4} \\ \\ & \ \ \ \le \mathbb{E}_{\mathbf{u}_{t+1} \sim \pi_{new} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \left[ Q_{soft}^{\pi_{old}} (\mathbf{x}_t, \mathbf{u}_t ) - \alpha \log \pi_{new} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) \right] \end{align} \]

 

이제 식 (4)를 식 (2)에 대입하면 다음과 같이 된다.

 

\[ \begin{align} Q_{soft}^{\pi_{old}} (\mathbf{x}_t, \mathbf{u}_t ) &= r_t + \gamma \ \mathbb{E}_{\mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t | \mathbf{u}_t ), \ \mathbf{u}_{t+1} \sim \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \tag{5} \\ & \ \ \ \ \ \ \ \ \ \ \left[ Q_{soft}^{\pi_{old}} (\mathbf{x}_t, \mathbf{u}_t ) - \alpha \log \pi_{old} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) \right] \\ \\ & \le r_t + \gamma \ \mathbb{E}_{\mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t | \mathbf{u}_t ), \ \mathbf{u}_{t+1} \sim \pi_{new} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) } \\ & \ \ \ \ \ \ \ \ \ \ \left[ Q_{soft}^{\pi_{old}} (\mathbf{x}_t, \mathbf{u}_t ) - \alpha \log \pi_{new} (\mathbf{u}_{t+1} | \mathbf{x}_{t+1}) \right] \end{align} \]

 

식 (5)의 오른쪽 항에 있는 \(Q_{soft}^{\pi_{old}} (\mathbf{x}_{t+1}, \mathbf{u}_{t+1} )\) 에 다시 식 (2)의 소프트 벨만 방정식을 대입하고 계속 전개하면, 결국 다음 부등식을 얻을 수 있다.

 

\[ Q_{soft}^{\pi_{old}} (\mathbf{x}_t, \mathbf{u}_t ) \le Q_{soft}^{\pi_{new}} (\mathbf{x}_t, \mathbf{u}_t ) \tag{6} \]

 

식 (6)에 의하면 식 (1)의 정책으로 소프트 행동가치를 개선할 수 있다는 것이 증명되었다.

 

 

한편 정책 \(\pi\) 가 주어지면, 소프트 벨만 방정식을 풀어서 소프트 행동가치를 계산할 수 있다. 이 과정을 정책 평가(policy evaluation)라고 한다. 소프트 벨만 방정식은 보통 해석적인 해를 구할 수 없으므로 반복적 계산 방법, 즉 이터레이션(iteration) 방법으로 해를 구할 수 있다. 이 때 이 계산이 수렴하는지 알아보자.

 

 

우선 소프트 행동가치 함수와 소프트 가치함수의 관계식이 다음과 같으므로

 

\[ Q_{soft}^\pi (\mathbf{x}_t, \mathbf{u}_t )= r_t + \gamma \ \mathbb{E}_{\mathbf{x}_{t+1} \sim p(\mathbf{x}_{t+1} | \mathbf{x}_t, \mathbf{u}_t ) } \left[ V_{soft}^\pi (\mathbf{x}_{t+1} ) \right] \tag{7} \]

 

소프트 벨만 백업 연산자 \( \mathcal{T}^\pi\) 를 다음과 같이 도입한다.

 

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

 

탐욕적 정책 (1)에 대한 소프트 상태가치 함수가 다음과 같으므로,

 

\[ V^\pi_{soft} (\mathbf{x}_t ) = \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_{soft}^\pi (\mathbf{x}_t, \mathbf{u}^\prime ) \right) d \mathbf{u}^\prime \tag{9} \]

 

식 (9)를 식 (8)에 대입하면 다음과 같이 된다.

 

\[ \begin{align} & \mathcal{T}^\pi Q (\mathbf{x}, \mathbf{u} ) = r(\mathbf{x}, \mathbf{u}) \tag{10} \\ \\ & \ \ \ \ \ + \gamma \ \mathbb{E}_{\mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u} ) } \left[ \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_{soft}^\pi (\mathbf{x}^\prime, \mathbf{u}^\prime ) \right) d \mathbf{u}^\prime \right] \end{align} \]

 

소프트 벨만 백업을 두 개의 서로 다른 소프트 행동가치 함수에 적용했을 때 두 행동가치 함수의 거리(distance)가 더 줄어든다면, 소프트 행동가치는 이터레이션이 진행되면서 수렴할 것이다. 두 소프트 행동가치 함수의 거리는 \(\infty-\)놈(norm)을 사용한다.

 

\[ \lVert Q_1-Q_2 \rVert_\infty = \max_{(\mathbf{x}, \mathbf{u})}⁡ \left\vert Q_1 (\mathbf{x}, \mathbf{u}) -Q_2 (\mathbf{x}, \mathbf{u}) \right\vert \tag{11} \]

 

그러면 다음 식이 성립한다.

 

\[ \begin{align} & \lVert \mathcal{T}^\pi Q_1- \mathcal{T}^\pi Q_2 \rVert_\infty \tag{12} \\ \\ & \ \ \ = \gamma \begin{Vmatrix} \mathbb{E}_{\mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u}) } \begin{bmatrix} \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_1 \right) d \mathbf{u}^\prime \\ - \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_2 \right) d \mathbf{u}^\prime \end{bmatrix} \end{Vmatrix}_\infty \\ \\ & \ \ \ = \gamma \begin{Vmatrix} \mathbb{E}_{\mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u}) } \begin{bmatrix} \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} ( Q_1+Q_2-Q_2 ) \right) d \mathbf{u}^\prime \\ - \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_2 \right) d \mathbf{u}^\prime \end{bmatrix} \end{Vmatrix}_\infty \\ \\ & \ \ \ \le \gamma \begin{Vmatrix} \mathbb{E}_{\mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u}) } \begin{bmatrix} \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} (Q_2+ \lVert Q_1-Q_2 \rVert_\infty) \right) d \mathbf{u}^\prime \\ - \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_2 \right) d \mathbf{u}^\prime \end{bmatrix} \end{Vmatrix}_\infty \\ \\ & \ \ \ = \gamma \begin{Vmatrix} \mathbb{E}_{\mathbf{x}^\prime \sim p(\mathbf{x}^\prime | \mathbf{x}, \mathbf{u}) } \begin{bmatrix} \lVert Q_1-Q_2 \rVert_\infty + \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_2 \right) d \mathbf{u}^\prime \\ - \alpha \log \int_{\mathbf{u}^\prime} \exp⁡ \left( \frac{1}{\alpha} Q_2 \right) d \mathbf{u}^\prime \end{bmatrix} \end{Vmatrix}_\infty \\ \\ & \ \ \ = \gamma \lVert Q_1-Q_2 \rVert_\infty \end{align} \]

 

식 (12)에 의해서 \(\gamma \lt 1\) 이라면 \( \lVert \mathcal{T}^\pi Q_1- \mathcal{T}^\pi Q_2 \rVert_\infty \lt \lVert Q_1-Q_2 \rVert_\infty \) 가 성립한다. 따라서 소프트 벨만 백업 연산자는 \(\gamma-\)축약(contraction) 연산자다.

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

 

\[ Q_{i+1} = \mathcal{T}^\pi Q_i \tag{13} \]

 

소프트 행동가치 함수가 유한하다면 행동가치 함수를 업데이트할 수록 점점 어떤 포인트로 수렴하게 된다는 것을 알 수 있다.

 

 

식 (2)로 \(Q_{soft}^\pi (\mathbf{x}_t, \mathbf{u}_t )\) 가 수렴할 때까지 반복 계산하고 수렴한 후에 식 (1)로 정책을 업데이트 하는 과정을 소프트 행동가치와 정책이 각각 최적인 값으로 수렴할 때까지 계속 반복하는 것을 소프트 정책 이터레이션(soft policy iteration)이라고 한다.