소프트 정책 이터레이션

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

 

 

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

 

$$\begin{array}{}\text{(1)}& \pi ({\mathbf{u}}_t|{\mathbf{x}}_t)=\frac{\exp (\frac{1}{\alpha }{Q}_{soft}^{\pi }({\mathbf{x}}_t,{\mathbf{u}}_t))}{{\int }_{{\mathbf{u}}^{\prime }}\exp (\frac{1}{\alpha }{Q}_{soft}^{\pi }({\mathbf{x}}_t,{\mathbf{u}}^{\prime }))d{\mathbf{u}}^{\prime }}\end{array}$$

 

정책을 ${\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{array}{rl}\text{(2)}& 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})}& [Q_{soft}^{{\pi }_{old}}({\mathbf{x}}_t,{\mathbf{u}}_t)-\alpha \log {\pi }_{old}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})]\end{array}$$

 

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

 

$$\begin{array}{r}\text{(2)}& & {\mathbb{E}}_{{\mathbf{u}}_{t+1}\sim {\pi }_{old}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})}\left[\begin{array}{c}\alpha \log {\pi }_{new}({\mathbf{x}}_{t+1}|{\mathbf{u}}_{t+1})\\ +\alpha \log {\int }_{{\mathbf{u}}^{\prime }}\exp (\frac{1}{\alpha }{Q}_{soft}^{\pi }({\mathbf{x}}_t,{\mathbf{u}}^{\prime }))d{\mathbf{u}}^{\prime }\\ -\alpha \log {\pi }_{old}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})\end{array}\right]\\ & ={\mathbb{E}}_{{\mathbf{u}}_{t+1}\sim {\pi }_{old}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})}\left[\begin{array}{c}\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 (\frac{1}{\alpha }{Q}_{soft}^{\pi }({\mathbf{x}}_t,{\mathbf{u}}^{\prime }))d{\mathbf{u}}^{\prime }\end{array}\right]\\ \\ & =-\alpha D_{KL}({\pi }_{old}({\mathbf{x}}_{t+1}|{\mathbf{u}}_{t+1})\parallel {\pi }_{new}({\mathbf{x}}_{t+1}|{\mathbf{u}}_{t+1}))\\ \\ & +\alpha {\mathbb{E}}_{{\mathbf{u}}_{t+1}\sim {\pi }_{old}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})}[\log {\int }_{{\mathbf{u}}^{\prime }}\exp (\frac{1}{\alpha }{Q}_{soft}^{\pi }({\mathbf{x}}_t,{\mathbf{u}}^{\prime }))d{\mathbf{u}}^{\prime }]\\ \\ & \le {\mathbb{E}}_{{\mathbf{u}}_{t+1}\sim {\pi }_{old}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})}[\alpha \log {\int }_{{\mathbf{u}}^{\prime }}\exp (\frac{1}{\alpha }{Q}_{soft}^{\pi }({\mathbf{x}}_t,{\mathbf{u}}^{\prime }))d{\mathbf{u}}^{\prime }]\end{array}$$

 

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

 

$$\begin{array}{rl}& ={\mathbb{E}}_{{\mathbf{u}}_{t+1}\sim {\pi }_{new}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})}[\alpha \log {\int }_{{\mathbf{u}}^{\prime }}\exp (\frac{1}{\alpha }{Q}_{soft}^{\pi }({\mathbf{x}}_t,{\mathbf{u}}^{\prime }))d{\mathbf{u}}^{\prime }]\\ \\ & ={\mathbb{E}}_{{\mathbf{u}}_{t+1}\sim {\pi }_{new}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})}[Q_{soft}^{{\pi }_{old}}({\mathbf{x}}_t,{\mathbf{u}}_t)-\alpha \log {\pi }_{new}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})]\end{array}$$

 

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

 

$$\begin{array}{r}\text{(4)}& & {\mathbb{E}}_{{\mathbf{u}}_{t+1}\sim {\pi }_{old}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})}[Q_{soft}^{{\pi }_{old}}({\mathbf{x}}_t,{\mathbf{u}}_t)-\alpha \log {\pi }_{old}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})]\\ & \le {\mathbb{E}}_{{\mathbf{u}}_{t+1}\sim {\pi }_{new}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})}[Q_{soft}^{{\pi }_{old}}({\mathbf{x}}_t,{\mathbf{u}}_t)-\alpha \log {\pi }_{new}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})]\end{array}$$

 

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

 

$$\begin{array}{rl}\text{(5)}& 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})}& [Q_{soft}^{{\pi }_{old}}({\mathbf{x}}_t,{\mathbf{u}}_t)-\alpha \log {\pi }_{old}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})]\\ \\ & \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})}\\ & [Q_{soft}^{{\pi }_{old}}({\mathbf{x}}_t,{\mathbf{u}}_t)-\alpha \log {\pi }_{new}({\mathbf{u}}_{t+1}|{\mathbf{x}}_{t+1})]\end{array}$$

 

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

 

$$\begin{array}{}\text{(6)}& Q_{soft}^{{\pi }_{old}}({\mathbf{x}}_t,{\mathbf{u}}_t)\le Q_{soft}^{{\pi }_{new}}({\mathbf{x}}_t,{\mathbf{u}}_t)\end{array}$$

 

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

 

 

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

 

 

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

 

$$\begin{array}{}\text{(7)}& 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)}[V_{soft}^{\pi }({\mathbf{x}}_{t+1})]\end{array}$$

 

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

 

$$\begin{array}{}\text{(8)}& {\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})}[V({\mathbf{x}}^{\prime })]\end{array}$$

 

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

 

$$\begin{array}{}\text{(9)}& V_{soft}^{\pi }({\mathbf{x}}_t)=\alpha \log {\int }_{{\mathbf{u}}^{\prime }}\exp (\frac{1}{\alpha }{Q}_{soft}^{\pi }({\mathbf{x}}_t,{\mathbf{u}}^{\prime }))d{\mathbf{u}}^{\prime }\end{array}$$

 

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

 

$$\begin{array}{r}\text{(10)}& & {\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})}[\alpha \log {\int }_{{\mathbf{u}}^{\prime }}\exp (\frac{1}{\alpha }{Q}_{soft}^{\pi }({\mathbf{x}}^{\prime },{\mathbf{u}}^{\prime }))d{\mathbf{u}}^{\prime }]\end{array}$$

 

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

 

$$\begin{array}{}\text{(11)}& \Vert Q_1-Q_2{\Vert }_{\mathrm{\infty }}=\underset{(\mathbf{x},\mathbf{u})}{max}|Q_1(\mathbf{x},\mathbf{u})-Q_2(\mathbf{x},\mathbf{u})|\end{array}$$

 

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

 

$$\begin{array}{r}\text{(12)}& & \Vert {\mathcal{T}}^{\pi }{Q}_1-{\mathcal{T}}^{\pi }{Q}_2{\Vert }_{\mathrm{\infty }}\\ & =\gamma {\Vert \begin{array}{c}{\mathbb{E}}_{{\mathbf{x}}^{\prime }\sim p({\mathbf{x}}^{\prime }|\mathbf{x},\mathbf{u})}\left[\begin{array}{c}\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{array}\right]\end{array}\Vert }_{\mathrm{\infty }}\\ \\ & =\gamma {\Vert \begin{array}{c}{\mathbb{E}}_{{\mathbf{x}}^{\prime }\sim p({\mathbf{x}}^{\prime }|\mathbf{x},\mathbf{u})}\left[\begin{array}{c}\alpha \log {\int }_{{\mathbf{u}}^{\prime }}\exp (\frac{1}{\alpha }(Q_1+Q_2-Q_2))d{\mathbf{u}}^{\prime }\\ -\alpha \log {\int }_{{\mathbf{u}}^{\prime }}\exp \left(\frac{1}{\alpha }{Q}_2\right)d{\mathbf{u}}^{\prime }\end{array}\right]\end{array}\Vert }_{\mathrm{\infty }}\\ \\ & \le \gamma {\Vert \begin{array}{c}{\mathbb{E}}_{{\mathbf{x}}^{\prime }\sim p({\mathbf{x}}^{\prime }|\mathbf{x},\mathbf{u})}\left[\begin{array}{c}\alpha \log {\int }_{{\mathbf{u}}^{\prime }}\exp (\frac{1}{\alpha }(Q_2+\Vert Q_1-Q_2{\Vert }_{\mathrm{\infty }}))d{\mathbf{u}}^{\prime }\\ -\alpha \log {\int }_{{\mathbf{u}}^{\prime }}\exp \left(\frac{1}{\alpha }{Q}_2\right)d{\mathbf{u}}^{\prime }\end{array}\right]\end{array}\Vert }_{\mathrm{\infty }}\\ \\ & =\gamma {\Vert \begin{array}{c}{\mathbb{E}}_{{\mathbf{x}}^{\prime }\sim p({\mathbf{x}}^{\prime }|\mathbf{x},\mathbf{u})}\left[\begin{array}{c}\Vert Q_1-Q_2{\Vert }_{\mathrm{\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{array}\right]\end{array}\Vert }_{\mathrm{\infty }}\\ \\ & =\gamma \Vert Q_1-Q_2{\Vert }_{\mathrm{\infty }}\end{array}$$

 

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

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

 

$$\begin{array}{}\text{(13)}& Q_{i+1}={\mathcal{T}}^{\pi }{Q}_i\end{array}$$

 

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

 

 

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