👨‍🏫학습목표

오늘은 TRPO의 Minorization-Maximization algorithm과 KL Divergence constraint 식에 대해 배워볼 예정이다.

👨‍🎓강의영상: https://www.youtube.com/watch?v=ojgn1xBWfGo

TRPO 논문: https://arxiv.org/pdf/1502.05477

1️⃣ Trust Region Policy Optimization

📕 지난 시간에 배운 내용

🔻 DDPG의 한계

• Policy의 monotonic improvement가 보장되지 않는다.

🔻 TRPO의 극복 방법

• Minorization-Maximization algorithm
• Trust region

이번 시간에는 Minorization-Maximization algorithm을 통해 policy의 monotonic improvement가 어떻게 보장되는지 살펴볼 예정이다.

---

2️⃣ TRPO의 object function

📕 지난 시간에 배운 내용

🔻 TRPO의 object function

$\eta(\pi) = \mathbb{E}_{s_0, a_0, \dots}\left[\sum_{t=0}^{\infty} \gamma^t r(s_t)\right]$

• Expected return을 object function으로 사용한다.

🔻 Object function 계산 방법

$\eta(\pi) = \eta(\pi_\text{old}) + \sum_{s} \rho_\pi(s) \sum_a \pi(a|s) A_{\pi_\text{old}}(s,a)$

• New policy의 $\eta(\pi)$를 구하기 위해서 old policy $\eta(\pi_{old})$에 추가적인 부분을 더한다.
• 다만 $\rho_\pi(s)$를 구하기 위해서 new policy $\pi$의 sample state를 수집해야 하는데, 아직까지 new policy를 구하는 과정이기 때문에 실제로 sample state를 수집할 수 없다.

---

3️⃣ Object function의 approximation

📕 지난 시간에 배운 내용

🔻 Local approximation

$L_{\pi_\text{old}}(\pi) = \eta(\pi_\text{old}) + \sum_s \rho_{\pi_\text{old}}(s) \sum_a \pi(a|s) A_{\pi_\text{old}}(s, a)$

• $L_{\pi_\text{old}}(\pi):$ 근사한 Object function
• 기존 식의 $\rho_{\pi}(s)$를 $\rho_{\pi_\text{old}}(s)$으로 변환한 것을 확인할 수 있다.

🔻 Approximation의 특징

$L_{\pi_{\theta_0}}(\pi_{\theta_0}) = \eta(\pi_{\theta_0}) \text{ for any parameter value } \theta_0.$

$\nabla_\theta L_{\pi_{\theta_0}}(\pi_{\theta_0})|_{\theta=\theta_0} = \nabla_\theta \eta(\pi_\theta)|_{\theta=\theta_0} \text{ for any parameter value } \theta_0.$

• 위 두 식을 만족한다.
• Local한 영역에서 두 식에 유사하기 때문에 근사식이 improve되는 방향에서 기존의 식 역시 improve될 수 있음을 알 수 있다.
• 다만 근사한 영역의 크기를 알 수는 없기에 step size에 대한 정보는 알 수 없다.

🔻 Conservative policy iteration update

$\pi(a|s) = (1-\alpha)\pi_\text{old}(a|s) + \alpha\pi'(a|s) \text{ where } \pi' = \arg\max_\pi L_{\pi_\text{old}}(\pi)$

• Conservative policy iteration update는 근사식 $L_{\pi_\text{old}}(\pi)$을 최적화시킨 후 그 값을 Old policy $\pi_{old}$에 일부만 반영하는 방법이다.
• Step size의 크기를 알 수 없기에 조금만 업데이트하는 방식이다.
• 해당 방식의 장점은 업데이트를 진행할 때 근사식이 lower bound를 가진다는 것이다.

$\eta(\pi) \geq L_{\pi_\text{old}}(\pi) - \frac{2\epsilon\gamma}{(1-\gamma)^2}\alpha^2 \text{ where } \epsilon = \max_s |\mathbb{E}_{a \sim \pi'(a|s)}[A_{\pi_\text{old}}(s,a)]|$

• 물론 성능이 개선된다는 보장은 없지만 lower bound를 통해 다양한 접근을 시도해볼 수 있다.
• 하지만 $\epsilon$ 값을 구하는 것은 쉽지 않다.
• 또한 mixture policy라는 개념 역시 아직까지 practical하게 적용하기는 쉽지 않다.

따라서 다음 단계에서는 approximation을 한번 더 진행할 예정이다.

---

4️⃣ Total Varinace Distance & KL Divergence

🔷 확률분포 사이의 거리

🔻 Total Variance distance

• 확률 분포 차이의 면적을 의미한다.
• 2로 나눠주기 때문에 $P > Q$ 인 영역만 고려해도 된다.
• 양쪽의 면접은 정확히 같다.

🔻 Kullback-Leibler divergence

$D_{\text{KL}}(P || Q) = \int_x p(x) \log \frac{p(x)}{q(x)} dx$

• $p(x)$와 $q(x)$가 유사해지면 $\frac{p(x)}{q(x)} \simeq 1$ 가 된다.

• 그 결과 $\log \frac{p(x)}{q(x)} \simeq 0$ 이 된다.

• 또한 $D_{\text{KL}}(P || Q) \neq D_{\text{KL}}(Q || P)$ 방향성을 가진다.

🔻 Approximation

🔸 기존의 식

$\eta(\pi) \geq L_{\pi_\text{old}}(\pi) - \frac{2\epsilon\gamma}{(1-\gamma)^2}\alpha^2 \text{ where } \epsilon = \max_s |\mathbb{E}_{a \sim \pi'(a|s)}[A_{\pi_\text{old}}(s,a)]|$

• $\alpha:$ Mixture policy를 생성할 때, 새로운 policy를 얼마나 반영할지 결정하는 파라미터
• $\pi' = \arg\max_\pi L_{\pi_\text{old}}(\pi)$

🔸 $\alpha$ 변환

$\alpha = \max_s D_{\text{TV}}(\pi_\text{old}(\cdot | s) || \pi(\cdot | s))$

• $\alpha$값을 Total Variation Distance로 대체한다.
• $D_{\text{TV}}:$ Total Variation distance

🔸 $\epsilon$ 변환

$\eta(\pi) \geq L_{\pi_\text{old}}(\pi) - \frac{4\epsilon\gamma}{(1-\gamma)^2}\alpha^2 \text{ where } \epsilon = \max_{s,a}|A_{\pi_\text{old}}(s,a)|$

• $\epsilon$ 값 역시 바꾼다.
• 위 수식으로 변한다.
• $\pi'$을 사용하지 않는 것이 포인트이다.

🔸 KL-발산으로 변환

$D_{\text{KL}}^{\max}(\pi_\text{old}, \pi) = \max_s D_{\text{KL}}(\pi_\text{old}(\cdot | s) || \pi(\cdot | s))$

$\eta(\pi) \geq L_{\pi_\text{old}}(\pi) - C D_{\text{KL}}^{\max}(\pi_\text{old}, \pi) \quad \text{where } C = \frac{4\epsilon\gamma}{(1-\gamma)^2}.$

• 기존에 Total variance distance로 표현한 $\alpha$를 KL-발산으로 바꾼다.
• $D_{\text{TV}}(p || q)^2 \leq D_{\text{KL}}(p || q)$ 부등호가 성립하기 때문이다.

🔷 Minorization-Maximization algorithm

$\eta(\pi) \geq L_{\pi_\text{old}}(\pi) - C D_{\text{KL}}^{\max}(\pi_\text{old}, \pi) \quad \text{where } C = \frac{4\epsilon\gamma}{(1-\gamma)^2}.$

• Lower bound를 surrogate objective로 사용하면 policy가 monotonic하게 성능이 개선되는 것을 보장한다.

다음 페이지를 살펴본 후 다시 돌아와서 이야기해보도록 하겠다. MM algorithm을 TRPO에 적용하여 monotonic하게 improve되는 것을 확인한 후 다시 돌아오자.

🔷 Practical algorithm

• 앞서 살펴본 MM-algorithm의 이론적 내용을 기반으로 pratical한 algorithm을 만들어보자.
• $\pi_{\theta}(a|s):$ Policy를 의미한다.
• $\theta:$ Policy를 구현하는 파라미터를 의미한다.
• $\theta_{old}:$ Old policy를 구현하는 파라미터를 의미한다.

$\eta(\theta) \geq L_{\theta_\text{old}}(\theta) - C D_{\text{KL}}^{\max}(\theta_\text{old}, \theta)$

• $\eta$ 를 업데이트하는 식을 위처럼 표현할 수 있다.

$\max_\theta \left[ L_{\theta_\text{old}}(\theta) - C D_{\text{KL}}^{\max}(\theta_\text{old}, \theta) \right]$

• Next policy $\theta$를 구하기 위해서는 위 연산을 수행해야 한다.
• 하지만 해당 연산은 너무 많은 계산량이 필요한다.
• 따라서 TRPO는 많은 계산량을 필요로 한다.

---

5️⃣ Minorization-Maximization algorithm

🔷 MM algorithm

• Iterative method
• 3 step이 반복되는 구조이다.

🔻 1. Find a surrogate objective function $M_i$

• $M_i:$ Surrogative objective function

• $\pi_i:$ Current policy

• $M_i$는 Object function $\eta(\pi)$를 $\pi_i$에서 approximate하는 함수이다.

• Surrogative objetive function $M_i$는 Object function $\eta(\pi)$의 lower bound이다.

• $\eta(\pi) \geq M_i$

• Surrogative objetive function $M_i$는 Optimize하기 쉬워야 한다.

• TRPO에서는 $M_i$로 이차함수를 사용한다.

🔻 2. Find the optimal point $\pi_{i+1}$

• $M_i$를 Maximize하는 optimal policy $\pi_{i+1}$를 구한다.
• $M_i(\pi_i) \leq M_i(\pi_{i+1}) \leq \eta(\pi_{i+1})$ 를 만족한다.
• 이러한 방식을 통해 monotomic improvement를 보장할 수 있다.

🔻 3. Find new surrogate objective function $M_{i+1}$

• 업데이트된 $\pi_{i+1}$를 사용하여 $M_{i+1}$를 구한다.

🔻 Iteration

• Step 1~3을 반복하면 policy가 monotonic하게 improve된다.
• 궁극적으로 local 혹은 global optimal값에 도달한다.

---

6️⃣ MM algorithm 적용

🔷 Surrogate objective function $M_i(\pi)$

$\eta(\pi) \geq L_{\pi_\text{old}}(\pi) - C D_{\text{KL}}^{\max}(\pi_\text{old}, \pi)$

$M_i(\pi) = L_{\pi_i}(\pi) - C D_{\text{KL}}^{\max}(\pi_i, \pi)$

• 앞서 찾은 lower bound이다.
• $\pi_i$를 통해 $\pi$를 찾는 과정이다.

🔻 $M_i(\pi)$를 surrogate objective function으로 사용할 수 있는 조건

• $\eta(\pi_i) = M_i(\pi_i)$
• $\eta(\pi) \geq M_i(\pi)$

🔷 Monotonic improvement

$\eta(\pi_i) = M_i(\pi_i) \text{ and } \eta(\pi) \geq M_i(\pi)$

$\Rightarrow \eta(\pi_i) = M_i(\pi_i) \leq M_i(\pi_{i+1}) \leq \eta(\pi_{i+1}) \quad \text{for } \pi_{i+1} = \arg \max_\pi M_i(\pi)$

• True objective function $\eta$ 가 monotonic하게 improve한다.

이제 앞서 살펴본 Minorization-Maximization algorithm으로 돌아가자.

---

7️⃣ Trust region

🔷 KL penalized objective

$\max_\theta \left[ L_{\theta_\text{old}}(\theta) - C D_{\text{KL}}^{\max}(\theta_\text{old}, \theta) \right]$

• Minorization-Maximization algorithm의 핵심은 surrogate object function을 maximize하는 policy를 찾는 것이었다.
• 위 식에서 $C D_{\text{KL}}^{\max}(\theta_\text{old}, \theta)$를 빼는 것은 penalty를 적용하는 것으로 해석할 수 있다.
• 이때 위 식을 KL penalized objective라고 한다.

🔷 KL penalized objective 변형

$\max_\theta L_{\theta_\text{old}}(\theta) \quad \text{subject to} \quad D_{\text{KL}}^{\max}(\theta_\text{old}, \theta) \le \delta$

• $D_{\text{KL}}^{\max}(\theta_\text{old}, \theta) \le \delta$ 를 KL constrained objective라고 한다.
• KL-발산 항으로 제약조건을 걸었다는 의미이다.
• MM-algorithm의 surogate object function을 위의 식으로 변형할 수 있다.
• 따라서 위 제약조건 하에서 $L_{\theta_\text{old}}(\theta)$의 maximize해주는 $\theta$가 new policy이다.

🔻 변형 시 이점

• 기존의 식에서는 $\gamma$가 1에 가까워지면 상수 $C$의 값이 커져 step size의 크기를 줄여야 했다.
• KL penalized objective를 제약조건 식으로 변형할 경우 상수 $C$를 사용하는 대신, 제약조건의 범위를 $\delta$로 조정할 수 있다.
• 이러한 방법을 Hard constraint라고 한다.

🔷 Constraint를 사용하는 것의 어려움

$D_{\text{KL}}^{\max}(\theta_\text{old}, \theta)= \max_s D_{\text{KL}}(\pi_\text{old}(\cdot | s) || \pi(\cdot | s)) \le \delta$

• 모든 state에 대해서 KL-발산 값이 $\delta$보다 작아야 한다.
• State 값이 많기 때문에 많은 constraint가 있다.
• 따라서 이 조건을 만족하는 $\pi$를 찾는 것은 쉽지 않다.
• 특히 sample data만 사용하기 때문에 더 그렇다.
• 이러한 문제를 해결하기 위해 Heuristic approximation을 사용한다.

🔷 Heuristic approximation

🔸 기존 식

$\max_\theta L_{\theta_\text{old}}(\theta) \quad \text{subject to} \quad D_{\text{KL}}^{\max}(\theta_\text{old}, \theta) \le \delta$

🔸 Approximation 적용

$\max_\theta L_{\theta_\text{old}}(\theta) \quad \text{subject to} \quad \mathbb{E}_{s \sim \rho_{\theta_\text{old}}}\left[D_{\text{KL}}(\pi_{\theta_\text{old}}(\cdot | s) || \pi_\theta(\cdot | s))\right] \le \delta$

• Max 함수 대신 Expectation 함수를 사용한다.
• 따라서 Expected KL divergence 를 사용한다.
• Expectation은 Monte carlo simulation에 따라 sample data를 통해 대체할 수 있다.

---

8️⃣ Monte Carlo simulation

🔷 $L_{\theta_\text{old}}(\theta)$ 변형

🔸 변형 전

$\max_\theta L_{\theta_\text{old}}(\theta) \quad \text{subject to} \quad \mathbb{E}_{s \sim \rho_{\theta_\text{old}}}\left[D_{\text{KL}}(\pi_{\theta_\text{old}}(\cdot | s) || \pi_\theta(\cdot | s))\right] \le \delta$

• $L_{\pi_\text{old}}(\pi) = \eta(\pi_\text{old}) + \sum_s \rho_{\pi_\text{old}}(s) \sum_a \pi(a|s) A_{\pi_\text{old}}(s, a)$
• $L_{\pi_\text{old}}(\pi)$ 식을 변형할 수 있다.

🔸 변형 후

$\max_\theta \sum_s \rho_{\theta_\text{old}}(s) \sum_a \pi_\theta(a|s) A_{\theta_\text{old}}(s, a) \quad \text{subject to} \quad \mathbb{E}_{s \sim \rho_{\theta_\text{old}}}\left[D_{\text{KL}}(\pi_{\theta_\text{old}}(\cdot | s) || \pi_\theta(\cdot | s))\right] \le \delta$

• 좌변의 식을 maximize하는 $\theta$를 찾는 것이기 때문에 $\eta(\pi_\text{old})$ 는 상수이다.
• 따라서 $\eta(\pi_\text{old})$는 제외한다.
• Constraint 식은 old policy에 대하여 expectation을 하는 것을 확인할 수 있다.
• Expectation은 sample data를 통해 구할 수 있다.
• Obeject function 부분은 변형이 조금 더 필요하다.

🔷 Object function 변형

$\max_\theta \sum_s \rho_{\theta_\text{old}}(s) \sum_a \pi_\theta(a|s) A_{\theta_\text{old}}(s, a) \quad \text{subject to} \quad \mathbb{E}_{s \sim \rho_{\theta_\text{old}}}\left[D_{\text{KL}}(\pi_{\theta_\text{old}}(\cdot | s) || \pi_\theta(\cdot | s))\right] \le \delta$

🔻 1. Expectation 만들기

$\sum_s \rho_{\theta_\text{old}}(s)[\dots] \quad \text{by} \quad \frac{1}{1-\gamma}\mathbb{E}_{s \sim \rho_{\theta_\text{old}}}[\dots]$

$\sum_{s \in \mathcal{S}} \rho_\pi(s) = \sum_{t=0}^\infty \gamma^t \sum_{s \in \mathcal{S}} P(S_t = s | \pi) = \sum_{t=0}^\infty \gamma^t = \frac{1}{1-\gamma}$

• State visit frequency는 확률이 아니기 때문에 확률로 만들기 위해 ${1-\gamma}$ 를 곱한다.
• 확률이 되었기 때문에 expectation으로 바꿀 수 있다.

🔻 2. Advantage function 변형

$\max_\theta \sum_s \rho_{\theta_\text{old}}(s) \sum_a \pi_\theta(a|s) A_{\theta_\text{old}}(s, a) \quad \text{subject to} \quad \mathbb{E}_{s \sim \rho_{\theta_\text{old}}}\left[D_{\text{KL}}(\pi_{\theta_\text{old}}(\cdot | s) || \pi_\theta(\cdot | s))\right] \le \delta$

• 좌변의 Advantage function $A_{\theta_\text{old}}(s, a)$ 을 Q-value function $Q_{\theta_{old}}$로 바꿀 수 있다.
• State value function $V(s)$는 policy와 관계없기 때문에 상수 역할을 하기 때문이다.
• 물론 상수 차이에 따라 Maximun값은 바뀌지만, Maximize하는 $\theta$는 바뀌지 않는다.
• Advantage function $A_{\theta_\text{old}}(s, a)$ 을 Q-value function $Q_{\theta_{old}}$로 바꾸는 것은 선택사항이다.
• TRPO에서는 Q-value function으로 바꾸지만, PPO에서는 바꾸지 않는다.

🔻 3. Expectation 만들기

$\sum_a \pi_\theta(a|s) A_{\theta_\text{old}}(s, a) = \mathbb{E}_{a \sim \pi_{\theta_\text{old}}}\left[ \frac{\pi_\theta(a|s)}{\pi_{\theta_\text{old}}(a|s)} A_{\theta_\text{old}}(s, a) \right]$

• New policy에 대한 expectation을 취하면 sample data를 구할 수 없기 때문에 old policy로 expectation을 만들어야 한다.
• $\frac{\pi_\theta(a|s)}{\pi_{\theta_\text{old}}(a|s)} :$ Importance sampling weight라고 한다.

🔸 Importance sampling weight

$\mathbb{E}_{x \sim p}[f(x)] = \mathbb{E}_{x \sim q}\left[\frac{p(x)}{q(x)}f(x)\right] \approx \frac{1}{N}\sum_{n=1}^N w(x_n) f(x_n) \\ \text{ from } x_n \sim q(x) \text{ where } w(x) = \frac{p(x)}{q(x)}$

• Expectation을 구하고 싶지만 해당 확률분포가 다루기 어려울 경우 사용한다.
• 조금 더 다루기 쉬운 확률분포로 바꾼 후 Importance sampling weight를 곱한다.
• 다른 확률분포를 사용한 후 그 차이를 Importance sampling weight를 통해 보정한다.

🔷 Final optimization

$\max_\theta \mathbb{E}_{s \sim \rho_{\theta_\text{old}}, a \sim \pi_{\theta_\text{old}}}\left[ \frac{\pi_\theta(a|s)}{\pi_{\theta_\text{old}}(a|s)} Q_{\theta_\text{old}}(s, a) \right] \ \ \text{subject to } \mathbb{E}_{s \sim \rho_{\theta_\text{old}}}\left[ D_{\text{KL}}(\pi_{\theta_\text{old}}(\cdot|s) || \pi_\theta(\cdot|s)) \right] \leq \delta$

• 앞에서 살펴봤던 3가지 변형을 적용한다.

• Maximize하는 $\theta$를 찾는 것이 목표이기 때문에 $\frac{1}{1-\gamma}$ 는 제거한다.

• KL-Constraint 항은 동일한다.

• 최종적으로 Surrogate object function을 Constraint가 있는 object function으로 변형하였다.

• Object function과 Constraint 식 모두 old policy에 대한 expectation이기 때문에 sample data를 수집하여 그 값을 구할 수 있다.

• Q-value function $Q_{\theta_{old}}$은 Q-Network를 설계하여 구할 수 있다.

---

9️⃣ TRPO

🔷 Practical algorithm

$\max_\theta \mathbb{E}_{s \sim \rho_{\theta_\text{old}}, a \sim \pi_{\theta_\text{old}}}\left[ \frac{\pi_\theta(a|s)}{\pi_{\theta_\text{old}}(a|s)} Q_{\theta_\text{old}}(s, a) \right] \ \ \text{subject to } \mathbb{E}_{s \sim \rho_{\theta_\text{old}}}\left[ D_{\text{KL}}(\pi_{\theta_\text{old}}(\cdot|s) || \pi_\theta(\cdot|s)) \right] \leq \delta$

🔻 Step 1 Sample data 수집하기

• Current policy를 사용하여 episode trajectory를 구한다.
• 해당 Sample data를 사용하여 Q-Network를 업데이트 할 수 있다.
• 그 후 업데이트한 Q-Network로 Q-value를 구할 수 있다.

🔻 Step 2 Expectation 값 구하기

• Sample data를 통해 Object function와 Constraint 식의 값을 구한다.
• 즉 Monte Carlo simulation을 통해 각각의 값을 구한다.

🔻 Step 3 Natural Policy Gradient

• Natural Policy Gradient를 사용하여 parameter $\theta$를 업데이트 한다.
• Natural Policy Gradient는 Second order optimization이다.
• 이후 Conjugate gradient와 backtracking Line search 방식을 사용한다.
• 이에 대한 내용은 다음 수업 때 자세히 설명하도록 하겠다.

---

🔟 정리

🔷 28강에서 배운 내용은 아래와 같다.

1. TRPO는 Conservative policy iteration update를 통해 lower bound를 만들었다.
2. 다양한 approximation을 통해 KL Divergence constraint 식을 만들었다.
3. Monte Carlo simulation을 적용하기 위해 old policy에 대한 expectation을 만들었다.
4. Constraint 식을 만족하면 monotonic한 improve가 가능하다.
5. Natural gradient policy를 통해 파라미터를 업데이트한다.