Trust-Region-Policy-Optimization

0. Abstract

Monotonic improvement가 보장된 policy gradient 알고리즘을 설명하겠다.

비록 이론적 결과에 대한 approximation을 하게 되지만 여전히 monotonic improvement를 주는 경향이 있다.

1. Introduction

이론적 결과로 특정한 surrogate objective function을 최적화한다면 policy improvement가 보장됨을 보이겠다. (Algorithm 1)

그 다음, 실용성을 위해 이에 대한 근사인 TRPO를 소개하도록 하겠다.

TRPO에 2가지 버전 single-path와 vine이 있는데 후자는 simulation에서만 가능하다.

실험적으로, TRPO가 Atari, swimming, walking 등에서 complex policy를 학습할 수 있음을 보이겠다.

2. Preliminaries

Infinite-horizon discounted Markov decision process (MDP) $(\mathcal{S},\mathcal{A},P,r,{\rho }_0,\gamma )$

• $\mathcal{S}$ is a finite set of states
• $\mathcal{A}$ is a finite set of actions
• $P:\mathcal{S}\times \mathcal{A}\times \mathcal{S}\to \mathbb{R}$ is the transition probability distribution
• $r:\mathcal{S}\to \mathbb{R}$ is the reward function
• ${\rho }_0:\mathcal{S}\to \mathbb{R}$ is the distribution of the initial state $s_0$
• $\gamma \in (0,1)$ is the discount factor

Let

• $\pi :\mathcal{S}\times \mathcal{A}\to [0,1]$ is a stochastic policy
• $\eta (\pi )={\mathbb{E}}_{s_0,a_0,\dots }\left[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^{t}r\left(s_t\right)\right]$ is the expected discounted reward
  • $s_0\sim {\rho }_0\left(s_0\right)$
  • $a_t\sim \pi (a_t\mid s_t)$
  • $s_{t+1}\sim P(s_{t+1}\mid s_t,a_t)$
• $Q_{\pi }(s_t,a_t)={\mathbb{E}}_{s_{t+1},a_{t+1},\dots }\left[\sum _{l=0}^{\mathrm{\infty }}{\gamma }^{l}r\left(s_{t+l}\right)\right]$ is the state-action value function
• $V_{\pi }\left(s_t\right)={\mathbb{E}}_{a_t,s_{t+1},\dots }\left[\sum _{l=0}^{\mathrm{\infty }}{\gamma }^{l}r\left(s_{t+l}\right)\right]$ is the state value function
• $A_{\pi }(s,a)=Q_{\pi }(s,a)-V_{\pi }(s)$ is the advantage function

---

Kakede & Langford (2002)에 대한 요약

$$\begin{array}{rl}\eta (\tilde{\pi })& =\eta (\pi )+{\mathbb{E}}_{s_0,a_0,\cdots \sim \tilde{\pi }}\left[\sum _{t=0}^{\mathrm{\infty }}{\gamma }^t{A}_{\pi }(s_t,a_t)\right]\\ & =\eta (\pi )+\sum _s{\rho }_{\tilde{\pi }}(s)\sum _a\tilde{\pi }(a\mid s)A_{\pi }(s,a)\end{array}$$

where ${\rho }_{\pi }(s)=P(s_0=s)+\gamma P(s_1=s)+{\gamma }^{2}P(s_2=s)+\dots$

• 직감적으로, $\tilde{\pi }$에 대한 evaluation을 $\pi$를 가지고 할 수 있다는 것이다.
• 만약 모든 state $s$에 대해서, $\sum _a\tilde{\pi }(a\mid s)A_{\pi }(s,a)\ge 0$ 일 경우 policy improvement가 보장된다.

하지만, 실제로는 $A_{\pi }(s,a)$는 샘플링 기반으로 approximation하게 될 것이다.

그 때, trajectory sample은 old policy $\pi$에서 뽑은 것을 사용할 것이다.

그 경우엔 ${\rho }_{\tilde{\pi }}(s)$는 장애물이 될 것이다.

이를 대처하기 위해 local approximation을 도입한다.

$$L_{\pi }(\tilde{\pi })=\eta (\pi )+\sum _s{\rho }_{\pi }(s)\sum _a\tilde{\pi }(a\mid s)A_{\pi }(s,a)$$

이는 굉장히 좋은 근사이다.

1. $L_{{\pi }_{{\theta }_0}}\left({\pi }_{{\theta }_0}\right)=\eta \left({\pi }_{{\theta }_0}\right)$
2. ${{\mathrm{\nabla }}_{\theta }{L}_{{\pi }_{{\theta }_0}}\left({\pi }_{\theta }\right)|}_{\theta ={\theta }_0}={{\mathrm{\nabla }}_{\theta }\eta \left({\pi }_{\theta }\right)|}_{\theta ={\theta }_0}\because$ Sutton, 1999

결론은, 작은 step만큼 policy update할 경우 $L$의 증가가 곧 $\eta$의 증가를 의미한다.

하지만 충분히 작은 step에 대한 애매모호함이 있기에 이들은 conservative policy iteration을 도입하였다.

• Let ${\pi }^{\prime }=\arg \underset{{\pi }^{\prime }}{max}{L}_{{\pi }_{\mathrm{old}}}\left({\pi }^{\prime }\right)$
• Let ${\pi }_{\text{new }}(a\mid s)=(1-\alpha ){\pi }_{\text{old }}(a\mid s)+\alpha {\pi }^{\prime }(a\mid s)$
• Then, $\eta \left({\pi }_{\text{new }}\right)\ge L_{{\pi }_{\text{old }}}\left({\pi }_{\text{new }}\right)-\frac{2ϵ\gamma }{(1-\gamma {)}^2}{\alpha }^2$ where $ϵ=\underset{s}{max}\left|{\mathbb{E}}_{a\sim {\pi }^{\prime }(a\mid s)}[A_{\pi }(s,a)]\right|$

---

하지만 이 lower bound는 mixture policy에서 적용되기 때문에 일반적이지 못하다.

3. Monotonic Improvement Guarantee for General Stochastic Policies

Let

• $D_{TV}(p|q)=\frac{1}{2}\sum _i|p_i-q_i|$
• $D_{\mathrm{TV}}^{max}(\pi ,\tilde{\pi })=\underset{s}{max}{D}_{TV}(\pi (\cdot \mid s)|\tilde{\pi }(\cdot \mid s))$

Theorem 1

​ Let $\alpha =D_{\mathrm{TV}}^{max}({\pi }_{\mathrm{old}},{\pi }_{\mathrm{new}})$. Then,

$$\begin{array}{rl}\eta \left({\pi }_{\text{new}}\right)& \ge L_{{\pi }_{\text{old}}}\left({\pi }_{\text{new }}\right)-\frac{4ϵ\gamma }{(1-\gamma {)}^2}{\alpha }^2\text{where }ϵ=\underset{s,a}{max}|A_{\pi }(s,a)|\\ & \ge L_{{\pi }_{\text{old }}}({\pi }_{\text{new }})-\frac{4ϵ\gamma }{(1-\gamma {)}^2}{D}_{\mathrm{KL}}^{max}({\pi }_{\text{old }},{\pi }_{\text{new }})\because D_{TV}(p\Vert q{)}^2\le D_{\mathrm{KL}}(p\Vert q)\end{array}$$

---

위의 정리에 기반하여 monotonic increasing policy iteration algorithm을 제안한다.

이 알고리즘은 $A_{\pi }$에 대한 evaluation이 가능하다고 암묵적으로 가정한다.

그 상황에서 monotonically improving sequence of policies가 생성된다.

Let $M_i(\pi )=L_{{\pi }_i}({\pi }_{i+1})-C{D}_{\mathrm{KL}}^{max}({\pi }_i,\pi )$.

Since $\eta \left({\pi }_{i+1}\right)\ge M_i\left({\pi }_{i+1}\right)$ and $\eta \left({\pi }_i\right)=M_i\left({\pi }_i\right)$,

$$\eta \left({\pi }_{i+1}\right)-\eta \left({\pi }_i\right)\ge M_i\left({\pi }_{i+1}\right)-M\left({\pi }_i\right)\ge 0$$

---

TRPO는 알고리즘 1에 대한 근사이다.

Large update를 robust하게 허용하기 위해 페널티 텀 $C{D}_{\mathrm{KL}}^{max}({\pi }_i,\pi )$을 없애고 constraint를 건다.

4. Optimization of Parameterized Policies

이론적인 알고리즘 1은 $A_{\pi }$에 대한 evaluation이 가능함을 가정하였고 policy search ${\pi }_{i+1}=\underset{\pi }{\arg max}[\dots ]$의 computational complexity를 고려하지 않았다.

이번 장과 다음 장에서 finite sample과 parameter로 구현되는 practical algorithm을 도출하겠다.

Let

• $\eta (\theta ):=\eta \left({\pi }_{\theta }\right)$
• $L_{\theta }(\tilde{\theta }):=L_{{\pi }_{\theta }}\left({\pi }_{\tilde{\theta }}\right)$
• $D_{\mathrm{KL}}(\theta |\tilde{\theta }):=D_{\mathrm{KL}}\left({\pi }_{\theta }|{\pi }_{\tilde{\theta }}\right)$

Then, ${\pi }_{i+1}=\underset{\pi }{\arg max}[L_{{\pi }_i}(\pi )-C{D}_{\mathrm{KL}}^{max}({\pi }_i,\pi )]$ is expressed as

$$\underset{\theta }{\mathrm{maximize}}[L_{{\theta }_{\text{old }}}(\theta )-C{D}_{\mathrm{KL}}^{max}({\theta }_{\text{old }},\theta )]$$

페널티 텀을 집어 넣는 방식의 경우 step size가 정말 작을 수도 있다.

Robust한 방식으로 large step을 취하기 위해서, trust region constraint를 채택하자.

$$\underset{\theta }{\mathrm{maximize}}{L}_{{\theta }_{\text{old }}}(\theta )\text{ subject to }{D}_{\mathrm{KL}}^{max}({\theta }_{\mathrm{old}},\theta )\le \delta$$

$\delta$를 허용된 step size라고 해석하면 된다.

$D_{\mathrm{KL}}^{max}({\theta }_{\mathrm{old}},\theta )\le \delta$를 확인하기 위해서 모든 state에 대해 KL-divergence를 구하는 것은 비실용적이다.

Approximation (sampling 기반)으로 constraint를 확인하기 위해 average KLD로 바꾸자.

$$\underset{\theta }{\mathrm{maximize}}{L}_{{\theta }_{\text{old }}}(\theta )\text{ subject to }{\bar{D}}_{\mathrm{KL}}^{{\rho }_{{\theta }_{\mathrm{old}}}}({\theta }_{\mathrm{old}},\theta )\le \delta$$

실험적으로 이러한 constraint의 변경은 큰 성능차이를 불러일으키지 않음을 확인하였다.

5. Sample-Based Estimation of the Objective and Constraint

4장에서 정의한 objective function과 constraint function을

$$\underset{\theta }{\mathrm{maximize}}\sum _s{\rho }_{{\theta }_{\text{old }}}(s)\sum _a{\pi }_{\theta }(a\mid s)A_{{\theta }_{\text{old }}}(s,a)\text{ subject to }{\bar{D}}_{\mathrm{KL}}^{{\rho }_{{\theta }_{\mathrm{old}}}}({\theta }_{\mathrm{old}},\theta )\le \delta$$

approximation하는 방법을 소개한다.

1. $\sum _s{\rho }_{{\theta }_{\text{old }}}(s)[\dots ]⟹\frac{1}{1-\gamma }{\mathbb{E}}_{s\sim {\rho }_{{\theta }_{\text{old }}}}[\dots ]$ ;
2. $A_{{\theta }_{\mathrm{old}}}⟹Q_{{\theta }_{\text{old }}}$ ;
3. $\sum _a{\pi }_{\theta }(a\mid s_n)A_{{\theta }_{\text{old }}}(s_n,a)={\mathbb{E}}_{a\sim q}\left[\frac{{\pi }_{\theta }(a\mid s_n)}{q(a\mid s_n)}{A}_{{\theta }_{\text{old }}}(s_n,a)\right]$

위의 세가지 사실들은 1. normalize; 2. $V$텀은 $\theta$에 독립적임; 3. policy ${\pi }_{old}$에서 뽑은 샘플로 MC approximation을 하기 위해 importance samling 도입한 것이다.

위의 세가지 사실을 활용하면 optimization 식을 다르게 표현할 수 있다.

$$\underset{\theta }{\mathrm{maximize}}{\mathbb{E}}_{s\sim {\rho }_{{\theta }_{\text{old }}},a\sim q}[\frac{{\pi }_{\theta }(a\mid s)}{q(a\mid s)}{Q}_{{\theta }_{\text{old }}}(s,a)]\text{ subject to }{\mathbb{E}}_{s\sim {\rho }_{{\theta }_{\text{old }}}}\left[D_{\mathrm{KL}}({\pi }_{{\theta }_{\text{old }}}(\cdot \mid s)\Vert {\pi }_{\theta }(\cdot \mid s))\right]\le \delta$$

이제 objective function과 constraint function을 estimate하는 두가지 방법을 소개하겠다.

5.1 Single path

Individualized trajectories sampling에 기반한 방식이다.

이는 policy gradient estimation에서 일반적으로 사용된다.

1. Sample $s_0\sim {\rho }_0$
2. Simulate one trajectory $a_0,s_1,a_1,\dots ,s_{T-1},a_{T-1},s_T\sim {\pi }_{{\theta }_{\text{old}}}\times P$
3. MC approximation

5.2 Vine

1. Sample $s_0\sim {\rho }_0$
2. Simulate multiple trajectories $a_0,s_1,a_1,\dots ,s_{T-1},a_{T-1},s_T\sim {\pi }_{{\theta }_{\text{old}}}\times P$
3. Choose $N$ states along these trajectories; $\{s_1,s_2,\dots ,s_N\}$, called rollout set
4. For each state $s_n$ in the rollout set, sample $K$ actions; $a_{n,k}\sim q(\cdot \mid s_n)$ s.t.
   • $\text{supp}({\pi }_{\text{old}}(\cdot \mid s_n))\subseteq \text{supp}(q(\cdot \mid s_n))$
   • continuous action을 다룰 땐, $q(\cdot \mid s_n)={\pi }_{{\theta }_{\text{old}}}(\cdot \mid s_n)$이 좋고
   • discrete action을 다룰 땐, $q(\cdot \mid s_n)=\text{Uni}$가 좋다. (exploration 측면에서)
5. …

모르겠다.

Vine은 single path method보다 분산이 낮아서 좋다.

하지만 simulation 밖에서는 안되는 방법이다.

6. Practical Algorithm

이해하려면 appendix 정리에 대한 증명을 봐야하는데 할 게 많아서 엄두가 안나서 여기까지 하고 PPO 논문을 읽겠다 ㅎㅎ;;