목차
- Preliminaries
- Monotonic Improvement Guarantee for General Stochastic Policies
- Optimization of Parameterized Policies
- Sample-Based Estimation of the Objective and Constraint
- Training
- Conjugate Gradient
- Reference
Preliminaries
Trust Region Policy Optimization(TRPO) 논문은 Kakade & Langford 논문을 기반으로 발전한 논문이다.
TRPO에서는 \(\eta(\pi)\)를 expected discounted reward라고 정의하였다.
\[\eta(\pi) = E_{s_0,a_0 \dots} [\underset{t=0}{\overset{\infty}{\sum}} \gamma^t r(s_t)]\]where \(s_0 \sim \rho_0(s_0)\), \(a_t \sim \pi(a_t \vert s_t)\), \(s_{t+1} \sim P(s_{t+1} \vert s_t, a_t)\)
Kakade & langford 논문에서 아래 식을 주장하였다.
\[\eta(\tilde{\pi}) = \eta(\pi) + E_{s_0,a_0 \dots \sim \tilde{\pi}} [\underset{t=0}{\overset{\infty}{\sum}} \gamma^t A_\pi(s_t,a_t)]\]이때 \(\rho_\pi\)는 discounted visitation frequencies다.
\[\rho_\pi(s) = P(s_0=s) + \gamma P(s_1=s) +\gamma^2(P(s_2=s) + \cdots\]Lemma 1
Lemma
\[\eta(\tilde{\pi}) = \eta(\pi) + E_{s_0,a_0 \dots \sim \tilde{\pi}} [\underset{t=0}{\overset{\infty}{\sum}} \gamma^t A_\pi(s_t,a_t)]\]Proof.
\[A_\pi(s,a) = E_{s' \sim P(s' \vert, s,a)}[r(s) + \gamma V_\pi(s') - V_\pi(s)]\] \[E_{\tau \vert \tilde{\pi}}[\underset{t=0}{\overset{\infty}{\sum}} \gamma^t A_\pi(s_t, a_t)]\] \[= E_{\tau \vert \tilde{\pi}} [\underset{t=0}{\overset{\infty}{\sum}} \gamma^t (r(s_t) + \gamma V_\pi(s_{t+1}) - V_\pi(s_t))]\]\(\sum \gamma^{t+1}V_\pi(s_{t+1}) - \gamma^t V_\pi(s_t)\)를 연산하면 \(-V_\pi(s_0)\)만 남음
\[= E_{\tau \vert \tilde{\pi}} [-V_\pi(s_0) + \underset{t=0}{\overset{\infty}{\sum}} \gamma^t r(s_t)]\] \[= -E_{s_0}[V_\pi(s_0)] + E_{\tau \vert \tilde{\pi}}[\underset{t=0}{\overset{\infty}{\sum}} \gamma^t r(s_t)]\] \[= - \eta(\pi) + \eta(\tilde{\pi})\]정리하면
\[\eta(\tilde{\pi}) = \eta(\pi) + E_{s_0,a_0 \dots \sim \tilde{\pi}} [\underset{t=0}{\overset{\infty}{\sum}} \gamma^t A_\pi(s_t,a_t)]\]이 된다.
\(\bar{A}(s) = E_{a \sim \tilde{\pi(\dot \vert s)}} [A_\pi (s,a)]\) 일 시 Lemma 1은 아래와 같이 변형이 가능하다.
\[\eta(\tilde{\pi}) = \eta(\pi) + E_{\tau \sim \tilde{\pi}} [\underset{t=0}{\overset{\infty}{\sum}} \gamma^t \bar{A} (s_t)]\] \[L_\pi(\tilde{\pi}) = \eta(\pi) + E_{\tau \sim \pi} [\underset{t=0}{\overset{\infty}{\sum}} \gamma^t \bar{A}(s_t)]\]\(\eta\)의 식을 timestep이 아닌 sum over state로 변환하면 아래 식이 된다.
\[\eta(\tilde{\pi}) = \eta(\pi) + \underset{t=0}{\overset{\infty}{\sum}} \sum_s P(s_t =s \vert \tilde{\pi}) \sum_a \tilde{\pi} (a \vert s) \gamma^t A_\pi(s,a)\] \[= \eta(\pi) + \sum_s \sum^\infty_{t=0} \gamma^t P(s_t = s \vert \tilde{\pi}) \sum_a \tilde{\pi} (a \vert s) A_\pi(s,a)\] \[=\eta(\pi) + \sum_s \rho_{\tilde{\pi}}(s) \sum_a \tilde{\pi} (a \vert s) A_\pi (s,a)\]이 식은 어떤 policy가 \(\pi \to \tilde{\pi}\)로 update된다면 non negative expected advantage를 보장한다. 즉 \(\eta\)의 policy performance가 감소하지 않는다는 것을 보장한다는 뜻이다.
하지만 위 식을 사용하기 위해서 estimation과 approximation으로 인하여 error가 발생할 것이다. 그러므로 최소한 보장되는 Trust region을 제한할려고 한다.
하지만 \(\rho_{\tilde{\pi}}(s)\)는 식을 최적화하기 어렵게 만들기 때문에 아래 식으로 대체한다.
\[L_\pi(\tilde{\pi})=\eta(\pi) + \sum_s \rho_{\pi}(s) \sum_a \tilde{\pi} (a \vert s) A_\pi (s,a)\]\(L_\pi(\tilde{\pi})\)는 visitation frequency \(\rho_{\tilde{\pi}}\) 대신 \(\rho_\pi\)를 사용한다.그러므로 policy가 바뀜에 따른 state visitation density를 무시할 수 있다.
\(\tilde{\pi}\)에 \(\pi_{\theta_0}\)를 대입하면 L과 \(\eta\)가 같아지고 1차 미분 또한 같아진다.
\[L_{pi_{\theta_0}}(\pi_{\theta_0})=\eta(\pi_{\theta_0})\] \[\nabla_\theta L_{\pi_{\theta_0}}(\pi_\theta) \vert_{\theta = \theta_0} = \nabla_\theta \eta(\pi_\theta) \vert_{\theta=\theta_0}\]이 뜻은 small step에 대해서 \(\pi_{\theta_0} \to \tilde{\pi}\)에 대해서 L이 \(\eta\)의 성능 향상을 보장한다는 뜻이다.
\[\pi_{\text{new}}(a \vert s) = (1 - \alpha)\pi_{\text{old}}(a \vert s) + \alpha \pi'(a \vert s)\]Kakade and Langford에서 아래의 lower bound를 정의하였다.
\[\eta(\pi_{\text{new}}) \ge L_{\pi_{\text{old}}}(\pi_{\text{new}}) - \frac{2 \epsilon \gamma}{(1-\gamma)^2} \alpha^2\]where \(\epsilon = \text{max}_s \vert E_{a \sim \pi'(a \vert s)}[A_\pi(s,a)] \vert\)
Monotonic Improvement Guarantee for General Stochastic Policies
이전 식을 general stochastic policy로 확장하기 위해서 \(\alpha\) 대신 \(\pi\)와 \(\tilde{\pi}\)의 거리를 이용하고 \(\epsilon\) 식을 변형할 수 있다. Total variation divergence를 이용하여 두 policy의 거리를 측정할 수 있다.
\[D_{\text{TV}}( p \vert\vert q) = \frac{1}{2} \sum_i \vert p_i - q_i \vert\] \[D^{\text{max}}_{\text{TV}} (\pi, \tilde{\pi}) = \text{max}_s D_{\text{TV}} ( \pi(\cdot \vert s) \vert\vert \tilde{\pi} (\cdot \vert s))\]위 Divergence를 이용하여 \(\eta\) 식을 변형할 수 있다.
\[\alpha = D^{\text{max}}_{\text{TV}} (\pi_{\text{old}}, \pi_{\text{new}})\] \[\eta(\pi_{\text{new}}) \ge L_{\pi_{\text{old}}}(\pi_{\text{new}}) - \frac{4 \epsilon \gamma}{(1-\gamma)^2} \alpha^2\]where \(\epsilon = \text{max}_{s,a} \vert A_\pi (s,a) \vert\)
Theorem 1
그리고 total variation divergence가 아닌 KL divergence를 사용할 것이다.
\[D_{\text{TV}}(p \vert\vert q)^2 \le D_{\text{KL}} (p \vert\vert q)\]그러므로 식이 아래와 같이 바뀐다.
\[\eta(\tilde{\pi}) \ge L_\pi(\tilde{\pi}) - \text{C} \text{D}^{\text{max}}_{\text{KL}} (\pi, \tilde{\pi})\]where \(\text{C} = \frac{4 \epsilon \gamma}{(1 - \gamma)^2}\)
위 식이 monotonically policy improve를 보장하기 위해서 아래와 같이 증명한다.
부등식의 오른쪽을 \(M_i(\pi)\)라고 정의하면
\[\eta(\pi_{i+1}) \ge M_i (\pi_{i+1})\] \[\eta(\pi_i) = M_i(\pi_i)\]이다.
그러므로
\[\eta(\pi_{i+1}) - \eta(\pi_i) \ge M_i (\pi_{i+1}) - M_i(\pi_i)\]이다.
그래서 \(M_i\)를 최대화하는 것은 \(\eta\)의 non-decreasing을 증명한다고 할 수 있다.
Optimization of Parameterized Policies
이 section에서는 위 이론 수식을 실제로 적용하기 위한 방법을 설명하고자 한다. 위 수식을 그대로 사용하기에는 small step을 사용해야한다. larger step을 사용하기 위한 한 가지 방법은 KL divergence를 constraint로 사용하는 것이다.
\[\text{maximize}_\theta \text{L}_{\theta_\text{old}} (\theta)\]subject to \(\text{D}^{\text{max}}_{\text{KL}} (\theta_\text{old}, \theta) \le \delta\)
KL divergence의 constraint는 state space에서 매 point마다 bound된다는 문제가 있다. 그러므로 aerage KL divergence를 사용하여 heuristic approximation을 사용한다.
\[\bar{\text{D}}^\rho_{\text{KL}}(\theta_1, \theta_2) := E_{s \sim \rho} [\text{D}_{\text{KL}}(\pi_{\theta_1}(\cdot \vert s) \vert\vert \pi_{\theta_2}(\cdot \vert s))]\] \[\text{maximize}_\theta \text{L}_{\theta_\text{old}} (\theta)\]subject to \(\bar{\text{D}}^{\rho_{\theta_{\text{old}}}}_{\text{KL}} (\theta_\text{old}, \theta) \le \delta\)
Sample-Based Estimation of the Objective and Constraint
이 section에서는 objective와 constraint function이 Monte Carlo simulation을 이용하여 approximation할 것이다.
\[\text{maximize}_\theta \sum_s \rho_{\theta_{\text{old}}} \sum_a \pi_\theta (a \vert s) A_{\theta_{\text{old}}} (s,a)\]subject to \(\bar{\text{D}}^{\rho_{\theta_{\text{old}}}}_{\text{KL}} (\theta_\text{old}, \theta) \le \delta\)
위 식을 변환을 하여 approximation한다.
\[\sum_s \rho_{\theta_{\text{old}}} (s) [\dots] \to \frac{1}{1-\gamma} E_{s \sim \rho_{\theta_{\text{old}}}}[\dots]\] \[A_{\theta_{\text{old}}} \to Q_{\theta_{\text{old}}}\]Sum over the actions를 importance sampling을 이용하여 대체
\[\text{maximize}_{\theta} E_{s \sim \rho_{\theta_{\text{old}}}, a \sim q} [\frac{\pi_{\theta}(a \vert s)}{q(a \vert s)} Q_{\theta_{\text{old}}}(s,a)]\]subject to \(E_{s \sim \rho_{\theta_{\text{old}}}} [\text{D}_{\text{KL}}(\pi_{\theta_{\text{old}}} ( \cdot \vert s) \vert\vert \pi_\theta (\cdot \vert s)] \le \delta\)
Training
위의 식을 taylor series를 적용하면 아래 식이 된다.
\[L_{\theta_k}(\theta) = L_{\pi_k}(\pi) \sim L_{\theta_k}(\theta) + g^T(\theta-\theta_k)\] \[D_{KL}(\pi_{\theta_k}, \pi_\theta) = D_{KL}(\pi_{\theta_k},\pi_\theta) + \nabla_\theta D_{KL}(\pi_{\theta_k}, \pi_\theta) (\theta - \theta_k) + \frac{1}{2} (\theta - \theta_k)^T H (\theta-\theta_k)\]첫번째식의 첫번째 term은 \(\theta_k = \theta\)가 된다면 0이 되고 두번째식 또한 마지막 term을 제외하고 0이된다.
그러므로
\[\theta_{k+1} = \text{argmax}_\theta g^T(\theta-\theta_k)\]subject to \(\frac{1}{2}(\theta - \theta_k)^T H (\theta- \theta_k) \le \delta\)
위 식을 Largrangian G로 표현하면
\[G = g^T s - \lambda \frac{1}{2} s^T H s\]where \(s = \theta-\theta_k\)
가 된다.
maximize하는 것이 목표니 1차 미분이 0이되어야한다.
\[\frac{\partial G}{\partial s} = g -\lambda Hs =0\]즉 Hs = g를 풀면 된다.
\(s = H^{-1}g\)로 풀기 위해서 hessian matrix를 직접 구하는 것은 높은 computation core, time을 요구한다. 그래서 TRPO 논문에서는 conjugate gradient 방법을 이용한다.
conjugate gradient 방법을 이용하여 \(H^{-1}g\)가 아닌 \(Hg\)를 이용하고 2차 미분인 H를 직접 구하는 것이 아닌 1차 미분 후 g를 곱하고 다시 한번 미분하는 방식을 사용한다.
\[Hx = \nabla_\theta ((\nabla_\theta D_{KL} (\theta || \theta_k)^T x)\]conjugate는 gradient를 점차적으로 구하여 최적 해에 도달하는 방법으로 gradient descent방식과 다르게 conjugate gradient를 고려하여 구하는 방법이다.
Conjugate Gradient
\(\phi = \frac{1}{2} x^T A x - x^T b\) 일 때
\(min_x \phi\)를 구하는 것이 목적이다.
\(\frac{\partial \phi}{\partial x} = AX^k - b\) 이다.
classical method 방법으로는 negative direction으로 update하는 방법이다.
\[g^k = -(Ax^k - b)\]방향은 결정되었으므로 얼마나 이동할 지를 결정해야한다.
\[x^{k+1} = x^k + \lambda_k g^k\] \[\lambda_k = \frac{b^Tg^k}{(g^k)^T A g^k}\]Conjugate graident 방법은 negative direction이 아닌 conjugate direction으로 이동한다.
conjugate란 직각을 의미하며
일반적인 두 벡터 사이각이 90라면 내적이 0이다.
\[v \cdot u = \vert v \vert \vert u \vert cos \theta\] \[cos \pi/2 = 0\]두 벡터가 있을 시 A에 대해서 conjugate한 식을 이용하여 conjugate gradient를 진행한다.
\[v^TSu = 0\]\({s^0, s^1, s^2 \cdots }\)를 direction이라하자.
\((s^k)^T A s^{k-1} = 0\) 이 식을 이용하여 conjugate 방향으로 이동하게 한다.
\[s^k = \beta_k s^{k-1} + g^k\] \[(s^k)^T A s^{k-1} = (\beta_k s^{k-1} + g^k)^T A s^{k-1}\] \[= (\beta_k s^{k-1})^TAs^{k-1} + (g^k)^TAs^{k-1}\]\(\beta\)에 대해서 정리하면 아래 식이 된다.
\[\beta_k = -\frac{(g^k)^TAs^{k-1}}{(s^{k-1})^TAs^{k-1}}\]\(\beta\)를 원래 s의 식에 대입한다.
\[s^k = - \frac{(g^k)^T A s^{k-1}}{(s^{k-1})^T A s^{k-1}}s^{k-1} + g^k\]그렇다면 gradient descent 방법과 다르게 g가 아닌 s를 사용하면 아래 식이된다.
\[x^{k+1} = x^k + \lambda s^k\] \[\lambda = \frac{b^Ts^{k-1}}{(s^{k-1})^TAs^{k-1}}\]더 자세하게 공부하여 정리가 필요한 부분인 것 같다.