[논문 리뷰]Trust Region Policy Optimization

pyross·2024년 12월 1일

paper

목록 보기

45/63

요약

PPO의 이전에 나온 논문이고 매우 유명하고 매우 어려운 논문이다.
주제는 monotonic improvement를 보장하는 방법이 없을까?이다.
이를 위해서
$\eta(\tilde{\pi}) = \eta(\pi) + \mathbb{E}_{s_0, a_0, \dots \sim \tilde{\pi}} \left[ \sum_{t=0}^\infty \gamma^t A_\pi(s_t, a_t) \right] \quad(1)$ 에서 시작해서
$L_\pi(\tilde{\pi}) = \eta(\pi) + \sum_s \rho_\pi(s) \sum_a \tilde{\pi}(a \mid s) A_\pi(s, a). \quad (3)$ 로 1차미분을 통한 근사를 진행하고
이때 근사를 얼마나 해야할지 lower bound를 구해서
$\eta(\tilde{\pi}) \geq L_\pi(\tilde{\pi}) - C D_{\text{KL}}^{\text{max}}(\pi, \tilde{\pi}), \\\quad \text{where } C = \frac{4 \epsilon \gamma}{(1 - \gamma)^2} \quad (9)$ 이렇게 식을 구성한다.
이 lower bound를 상승시키면 monotonic improvement가 보장이 된다.

그러나 실제로 적용하기 어렵기에 이를 타협해서 constraint로 penalty를 보내고 advantage를 Q로 변경하고 importance sampling등의 기법으로 sum을 expectation으로 수정한 다음
$\begin{aligned} \text{maximize}_\theta \quad & \mathbb{E}_{s \sim \rho_{\theta_{\text{old}}}, a \sim q} \left[ \frac{\pi_\theta(a \mid s)}{q(a \mid s)} Q_{\theta_{\text{old}}}(s, a) \right] \quad (14) \\ \text{subject to} \quad & \mathbb{E}_{s \sim \rho_{\theta_{\text{old}}}} \left[ D_{\text{KL}}(\pi_{\theta_{\text{old}}}(\cdot \mid s) \,\|\, \pi_\theta(\cdot \mid s)) \right] \leq \delta. \end{aligned}$
이렇게 수식을 구성해서 실제 학습을 진행한다.

TRPO는 성능이 잘 나온다기 보다는 이렇게 하였을 때도 학습이 된다는 내용이고 추후 나온 PPO의 배경이기에 중요하다.

Abstract

이 논문은 policy를 optimize하는 과정에서 monotonic improvement를 보장하는 방법을 설명한다.
이는 TRPO(Trust Region Policy Optimization)으로 이론적 정의된 내용을 근사하는 방법으로 학습이 이루어진다.
다양한 task에서 robust한 성능을 얻었다고 한다.

1 Introduction

이 논문은 대체 목표 함수(surogate objective function)을 최적화하는 것이 policy 개선을 보장한다는 것을 증명하고 시작한다.
이후 이론적으로 정의된 알고리즘을 approximation하는 것으로 실제 적용을 한다.
이게 TRPO이다.

이 TRPO는 2개의 variant가 존재하는데

single-path method: model-free 환경에서 사용 가능
vine method: 시스템을 특정 상태로 복구가 가능한 시뮬레이션 같은 상황에서 사용이 가능하다.

이러한 TRPO를 통해 복잡한 문제를 풀 수있었다고 한다.

2 Preliminaries

명명법으로 시작한다. MDP 환경이 $(\mathcal{S,A,}P,r,p_0,\gamma)$ 로 구성이 될때

$\mathcal{S}$ :finite set of states
$\mathcal A$ : finite set of actions
$P: \mathcal{S \times A\times S}\rarr \mathbb R$ 으로 구성이 된 transition 확률
$r: \mathcal S \rarr \mathbb R$ 인 reward 함수
$p_0: \mathcal S \rarr \mathbb R$ 인 initial state $s_0$ 의 확률
$\gamma \in (0,1)$ discount factor이다.
$\pi: \mathcal{S \times A}\rarr[0,1]$ 로 stochastic policy이고

$\eta(\pi)=\mathbb E_{s_0,a_0,...}[\sum^\infin_{t=0}\gamma^t r(s_t)]$ 로 expected discounted reward 이다.
이때 $s_0 \sim p_0(s_0), a_t\sim \pi(a_t|s_t),s_{t+1}\sim P(s_{t+1}|s_t,a_t)$ 이다.

또한
$Q_\pi(s_t, a_t) = \mathbb{E}_{s_{t+1}, a_{t+1}, \dots}[ \sum_{l=0}^\infin \gamma^l r(s_{t+l})]$
$V_\pi(s_t) = \mathbb{E}_{a_t, s_{t+1}, \dots} \left[ \sum_{l=0}^\infty \gamma^l r(s_{t+l}) \right]$
$A_\pi(s, a) = Q_\pi(s, a) - V_\pi(s), \text{where} \\a_t \sim \pi(a_t \mid s_t), s_{t+1} \sim P(s_{t+1} \mid s_t, a_t) \quad \text{for } t \geq 0$
을 만족한다.

그냥 전체 notation은 간단하게 MDP 환경이고 Q는 action value, V는 value, A는 advantage이다.

여기에서 재밌는 부분이 나온다.
우리가 다른 policy $\tilde \pi$ 의 expected return을 구하기 위해서 현재 알고있는 policy $\pi$ 를 이용할 수 있는데
$\eta(\tilde{\pi}) = \eta(\pi) + \mathbb{E}_{s_0, a_0, \dots \sim \tilde{\pi}} \left[ \sum_{t=0}^\infty \gamma^t A_\pi(s_t, a_t) \right] \quad(1)$
위와 같은 식으로 구할 수 있다.
식의 의미는 $\tilde \pi$ 의 expected return은 policy $\pi$ 의 expected return에 $\tilde \pi$ 의 trajectory에서 policy $\pi$ 의 advantage를 더해준 것이다.

이 부분이 사실 와닿지 않았는데
정책 $\pi$ 의 advantage $\mathbb E_{a_t\sim \pi(a_t|s_t)}[A_\pi(s_t,a_t)]=0$ 인 것을 생각하면 이해가 조금 쉽고
advantage는 그 행동 자체의 value라고 생각하면 더 와닿는 것 같다.
예를 들어서
만약 state가 $s_0,s_1$ , action은 $a_0,a_1$ 만 있는 상황에서 초기 state는 $s_0$ 이고 무슨 짓을 하든 $s_1$ 으로 가고
$R(s_0,a_0)=1$ 이고 $R(s_0,a_1)=0$ 이라고 하자.
이때 policy가 $\pi$ 는 $\pi(a_0|s_0)=0.5, \pi(a_1|s_0)=0.5$ 일때
policy $\pi$ 의 기대보상은 0.5이다. state 0에서 $1\times0.5+0 \times0.5$ 이기 때문.
이때 advantage는 $A_\pi(s_0,a_0)=1-0.5=0.5$ , $A_\pi(s_0,a_1)=0-0.5=-0.5$ 이다.

이제 $\tilde \pi$ 를 생각해보자 $\tilde \pi(a_0|s_0)=0.7,\tilde \pi(a_1|s_0)=0.3$ 일때
$\tilde \pi$ 의 expected return은 0.7이다.
이를 위 수식을 통해 구하면
$\eta(\tilde \pi)=\eta(\pi)+0.7\times0.5+0.3\times-0.5=0.5+0.35-0.15=0.7$ 로 정확한 값이 구해진다.
$\tilde \pi$ 의 확률 분포와 $\pi$ 의 advantage 즉 행동을 하였을 때 얻는 return의 기댓값과 곱해져서 차이를 만들어내고 이 차이를 원래 policy $\pi$ 의 기댓값과 더해져서 $\tilde \pi$ 의 기댓값으로 만들어지는 것이다.

추가로 위 식의 증명은 다음과 같다.출처

이제 위 1번식을 수정할건데 한가지 term을 정의해야한다.
아래는 $P(s_t=s)$ 를 가중해서 더한 값 즉 visitation frequency인데 normalized가 되어있지 않아 정확히는 (unnormalized) discounted visitation frequencies이다.
뜻은 $\pi$ 가 특정 state에 있을 확률들의 가중합을 의미한다.

$\rho_\pi(s)=P(s_0=s)+\gamma P(s_1=s)+\gamma ^2P(s_2=s)+...$

이를 이용해서 (1)번식을 수정할 수 있는데
$\eta(\tilde{\pi}) = \eta(\pi) + \mathbb{E}_{s_0, a_0, \dots \sim \tilde{\pi}} \left[ \sum_{t=0}^\infty \gamma^t A_\pi(s_t, a_t) \right] \quad(1)$
이 식을 전개하면 아래와 같이 구성이 가능하다.

$\eta(\tilde{\pi}) = \eta(\pi) + \sum_{t=0}^\infty \sum_s P(s_t = s \mid \tilde{\pi}) \sum_a \tilde{\pi}(a \mid s) \gamma^t A_\pi(s, a) \\ \quad = \eta(\pi) + \sum_s \sum_{t=0}^\infty \gamma^t P(s_t = s \mid \tilde{\pi}) \sum_a \tilde{\pi}(a \mid s) A_\pi(s, a) \\ \quad = \eta(\pi) + \sum_s \rho_{\tilde{\pi}}(s) \sum_a \tilde{\pi}(a \mid s) A_\pi(s, a). \quad (2)$
첫번째 줄은 expectation을 제거한 것이고 두번째 줄은 sigma의 위치를 변경하고 $\gamma ^t$ 가 t에대한 값이기 때문에 밖으로 뺀 것이다.
3번째 줄인 위 정의한 term을 이용해서 식을 간략하게 줄인 것이다.

여기에서 중요한 것은 $\tilde \pi$ 로 $\pi$ 를 업데이트 할때 모든 state $s$ 에 대해서 advantage가 nonnegative면
즉, $\sum_a \tilde{\pi}(a \mid s) A_\pi(s, a) \geq 0$ 이면 항상 $\eta(\tilde \pi)$ 가 증가하거나 유지되는 것을 보장한다.
이는 기존의 exact policy iteration에서 $\tilde \pi(s)=\arg\max_aA_\pi(s,a)$ 로 업데이트할 때 advantage가 양수이고 state visit probability가 0이 아닌 상황이 1개라도 존재하면 policy가 개선이 됨을 보여준다.
하지만 실제로는 neural network로 근사해서 표현을 하기 때문에 exact policy가 될 수 없고 그렇기에 실제로는 $\sum_a \tilde{\pi}(a \mid s) A_\pi(s, a) < 0$ 인 상황인데 0보다 크거나 같다고 생각해서 update가 일어날 수 있다.

여기에서 중요한 것은 위 수식에서 $\rho_{\tilde{\pi}}(s)$ 가 사용이 되었기 때문에 $\tilde \pi$ 의 trajectory를 구하고 state에 위치할 확률을 구해야 한다. 이는 update를 매우 어렵게 만든다. update를 하기 위해서 trajectory를 미리 구해봐야 하기 때문
그렇기에 위 수식의 $\rho_{\tilde{\pi}}(s)$ 를 $\rho_{{\pi}}(s)$ 수정해서 표현을 한다.
$L_\pi(\tilde{\pi}) = \eta(\pi) + \sum_s \rho_\pi(s) \sum_a \tilde{\pi}(a \mid s) A_\pi(s, a). \quad (3)$

이렇게 수정하면 policy의 변경에 따른 visitation density의 변경을 무시하게 된다.

이렇게표현을 해도 괜찮을까?
당연히 괜찮지 않다.
그러나 policy를 조금만 변경하면 동일한 근사가 가능하다.
$L_{\pi_{\theta_0}}(\pi_{\theta_0}) = \eta(\pi_{\theta_0}),\\ \nabla_\theta L_{\pi_{\theta_0}}(\pi_\theta) \big|_{\theta = \theta_0} = \nabla_\theta \eta(\pi_\theta) \big|_{\theta = \theta_0}. \quad (4)$
위 내용을 보면 $L_{\pi_{\theta_0}}(\pi_{\theta_0})$ 인 상황은 당연하 advantage가 0이기 때문에 $\eta(\pi_{\theta_0})$ 와 동일하게 된다.
이때 양변을 미분한 것은 작은 step에 한해서 동일한 미분 값이 나오게 되고 그 미분 영역의 주변에서 근사 표현이 가능하다.

이 부분이 이해가 어려울 수 있는데
간단하게 2차 함수를 미분해서 표현하는 것을 생각하면 좋다.
위 그림을 보면 2차함수를 미분해서 직선으로 구하였을 때 그 오차(빨간선)가 미분한 점에 가까울수록 줄어들게 된다. 이를 통해 작은 영역에서는 동일한 표현이 가능하고
$\pi_{\theta_0}$ 를 $\tilde \pi$ 로 작은 step만큼 업데이트 하는 상황에서 $L_{\pi_{\text{old}}}$ 를 증가시키면 $\eta$ 도 증가시킬 수 있다. 이를 통해서
'작은 step의 update가 이루어질 때' performance의 증가를 보장할 수 있다.

그런데 이 작은 step의 기준을 어떻게 정할 수 있을까?

kakade & langford의 논문에서 lower bound가 증명이 되었는데
$\pi_{\text{old}}$ 가 현재의 policy이고 $\pi'=\arg\max_{\pi'}L_{\pi_\text{old}}(\pi')$ 가 update될 policy인 상황에서

$\pi_{\text{new}}(a \mid s) = (1 - \alpha) \pi_{\text{old}}(a \mid s) + \alpha \pi'(a \mid s). \quad (5)$

위 상황 즉 $\pi'$ 과 $\pi_{\text{old}}$ 의 비율을 통하여 mixture policy를 구성할 때
$\eta(\pi_{\text{new}}) \geq L_{\pi_{\text{old}}}(\pi_{\text{new}}) - \frac{2 \epsilon \gamma}{(1 - \gamma)^2} \alpha^2, \\\quad \text{where } \epsilon = \max_s \left| \mathbb{E}_{a \sim \pi'(a \mid s)} \left[ A_\pi(s, a) \right] \right|. \quad (6)$
위와 같이 lower bound가 구성이 됨을 증명하였다.

위 수식에서 $\gamma$ 와 $\alpha$ 는 고정된 constatnt 값이고 $\epsilon$ 이 중요한데 $\epsilon$ 은 advantage의 기댓값이 0이기 때문에 $\pi_{\text{old}}$ 와 $\pi_{\text{new}}$ 의 차이가 작으면 0에 가까워지고 크면 커진다.

이를 이용해서 lower bound를 커지는 방향으로 update를 진행하면 $\eta$ 도 커지는 방향으로 update가 되기 때문에 monotonic imporvement를 보장할 수 있다.

하지만 이러한 lower bound는 policy가 섞이는 mixture policy에만 적용할 수 있기 때문에 실제 상황에서 적용하기에는 힘들다.

3 Monotonic Improvement Guarantee for General Stochastic Policies

이제부터 이 논문의 contribution이 시작된다.
우선 위 (6) 식을 practical하게 개선하는 것으로부터 시작한다.

우선 (5) mixture policy는 실제로 잘 사용되지 않기에 다른 방법으로 표현한다.

$D_{TV}(p||q)=\frac{1}{2}\sum_i|p_i-q_i|$ 라고 하자 즉 $(\frac{1}{3},0,0),(0,\frac{2}{3},0)$ 이면 $\frac{1}{2}$ 이다.

이를 이용해서 아래와 같이 $D_{\text{TV}}^{\text{max}}(\pi, \tilde{\pi})$ 를 정의한다.
$D_{\text{TV}}^{\text{max}}(\pi, \tilde{\pi}) = \max_s D_{\text{TV}}(\pi(\cdot \mid s) \,\|\, \tilde{\pi}(\cdot \mid s)). \quad (7)$

Theorem1 $\alpha=D_{\text{TV}}^{\text{max}}(\pi, \tilde{\pi})$ 인 상황에서 lower bound는
$\eta(\pi_{\text{new}}) \geq L_{\pi_{\text{old}}}(\pi_{\text{new}}) - \frac{4 \epsilon \gamma}{(1 - \gamma)^2} \alpha^2, \\\quad \text{where } \epsilon = \max_{s, a} \left| A_\pi(s, a) \right|. \quad (8)$
위처럼 정의가 된다.

여기에서 한번 더 정리가 들어가는데 pollard의 정리에 따르면
$D_{TV}(p||q)^2 \leq D_{\text{KL}}(p||q)$ 를 만족시킨다.
그리고 위에서 $D_{\text{TV}}^{\max}$ 를 정의한 것처럼
$D_{\text{KL}}^{\text{max}}(\pi, \tilde{\pi}) = \max_s D_{\text{KL}}(\pi(\cdot \mid s) \,\|\, \tilde{\pi}(\cdot \mid s))$ 라고 하자.

그러면 아래와 같이 정리가 가능하다.
$\eta(\tilde{\pi}) \geq L_\pi(\tilde{\pi}) - C D_{\text{KL}}^{\text{max}}(\pi, \tilde{\pi}), \\\quad \text{where } C = \frac{4 \epsilon \gamma}{(1 - \gamma)^2} \quad (9)$

이제 이렇게 만든 식을 이용해서 이론적인 학습이 가능하다.
위 알고리즘인데 간단하다.
위 수식을 이용해서 학습을 하는데
새로운 $\pi_{i+1}$ 을 (9)식의 우변을 최대화 하는 $\pi$ 로 만든다.
이때 가능한 모든 advantage $A_{\pi_i}(s,a)$ 를 전부다 구하는데 사실 이는 말이 안된다. state와 action이 무수히 많기 때문. 이론적으로 구성이 되기에 이렇게 작성이 되었다.

위 알고리즘 1 사용하면 monotonically improvement가 보장이 된다.
정확히는
$\eta(\pi_0)\leq \eta(\pi_1) \leq \eta(\pi_2) \leq...$ 이 됨을 보이기 위해서
$M_i(\pi)=L_{\pi_i}(\pi)-CD_{\text{KL}}^{\max}(\pi_i,\pi)$ 라고 할때

$\eta(\pi_{i+1}) \geq M_i(\pi_{i+1}) \text{ by Equation (9)} \\ \eta(\pi_i) = M_i(\pi_i), \text{ therefore,} \\ \eta(\pi_{i+1}) - \eta(\pi_i) \geq M_i(\pi_{i+1}) - M(\pi_i). \quad (10)$
위와 같인 구조로 유도가 되고 만약 $M_i$ 가 각 iteration에서 non-decreasing을 만족하게 된다면 $\eta$ 도 non-decreasing을 만족한다.

이때 $M_i$ 를 surrogate function 즉 대리의 함수로 본다.( $M_i$ 를 증가하는 것이 곧 $\eta$ 의 증가이기 때문에 surrogate objective임)

4 Optimization of Parameterized Policies

지금까지는 parameter이 안된 $\pi$ 인 상황이었고 policy가 모든 state에서 평가가 될 수 있다고 가정을 하였다.
이제는 실질적인 parameterized policy 상황을 가져온다.
간단하게 이전 수식들을 parameterized 상황에서 어떻게 표현할지를 다룬다.

parameretized policy $\pi_\theta(a|s)$ 와 parameter vector $\theta$ 라고 하자.
이때 $\pi$ 대신 $\theta$ 를 사용할 것이다.
예를 들어서 $\eta(\theta):=\eta(\pi_\theta)$ , $L_\theta(\tilde \theta):=L_{\pi_\theta}(\pi_{\tilde \theta})$ 등등

이전에
$\text{maximize}_\theta \left[ L_{\text{old}}(\theta) - C D_{\text{KL}}^{\text{max}}(\theta_{\text{old}}, \theta) \right].$ 를 통해 $\eta$ 를 증가시킬 수 있음을 보였는데
이때 중요한 부분이 coefficient $C = \frac{4 \epsilon \gamma}{(1 - \gamma)^2}$ 가 너무 크다는 것이다. 만약 $\gamma =0.99$ 면 분모가 $0.01^2$ 이 되고 분자에 10000이 곱해진다...
이 때문에 penalty가 너무 세서 step이 작아질 수밖에 없다.

그렇기 때문에 penalty term의 coefficient를 빼고 constraint에 넣어서 최적화 진행을 해준다.
사실 이 부분은 이론적인 최적에서 실질적으로 적용을 하기 위해서 타협을 한 것이다.
$\text{maximize} \quad L_{\text{old}}(\theta) \\ \quad \text{subject to} \quad D_{\text{KL}}^{\text{max}}(\theta_{\text{old}}, \theta) \leq \delta. \quad(11)$

여기에서 다시한번 더 조절을 하는데
$D_{\text{KL}}^{\text{max}}(\pi, \tilde{\pi}) = \max_s D_{\text{KL}}(\pi(\cdot \mid s) \,\|\, \tilde{\pi}(\cdot \mid s))$ 로 앞서 정의가 되었는데 이때의 문제점은 max s를 찾기 위해서 모든 state를 전부 다 알아야 한다.
이는 말이 안되기에 한번 더 타협을 해서 휴리스틱을 이용해서 다음과 같이 평균으로 변경한다. 평균으로 된다면 Montecarlo로 비편향추정량을 구할 수 있기 때문
$\overline{D}_{\text{KL}}^\rho(\theta_1, \theta_2) := \mathbb{E}_{s \sim \rho} \left[ D_{\text{KL}}(\pi_{\theta_1}(\cdot \mid s) \,\|\, \pi_{\theta_2}(\cdot \mid s)) \right].$

결국 이를 반영해서
$\text{maximize} \quad L_{\text{old}}(\theta) \\ \quad \text{subject to} \quad D_{\text{KL}}^{\rho_{\theta_\text{old}}}(\theta_{\text{old}}, \theta) \leq \delta.\quad(12)$
으로 최종적으로 변경한다.

실험에서 이렇게 구성한 (12)식은 (11)식과 실질적으로 비슷한 성능을 보였다고 한다.

5 Sample-Based Estimation of the Objective and Constraint

이 부분은 앞서 설명한 (12)식을 monte carlo로 어떻게 approximate가 되는지 설명하는 부분이다.

위 식을 풀면 다음과 같다.
$\begin{aligned} \text{maximize}_\theta \quad & \sum_s \rho_{\theta_{\text{old}}}(s) \sum_a \pi_\theta(a \mid s) A_{\theta_{\text{old}}}(s, a) \\ \text{subject to} \quad & \overline{D}_{\text{KL}}^{\rho_{\theta_{\text{old}}}}(\theta_{\text{old}}, \theta) \leq \delta. \end{aligned} \quad (13)$

우선 첫번째로 $\sum_s \rho_{\theta_\text{old}}(s)[...]$ 의 내용을 expectatoin으로 변경한다.
$\frac{1}{1-\gamma} \mathbb E_{s\sim\rho_{\theta_{\text{old}}}}[...]$ 와 같이 변경한다.

이렇게 만들기 위해서는 확률로 표현이 되어야하고 이를 위해서 정규화를 해주어야 한다.
원래 $\rho_\pi(s)=P(s_0=s)+\gamma P(s_1=s)+\gamma ^2P(s_2=s)+...$ 의 구성이었다.
그렇기에 $\sum_s\rho_\pi(s)=\sum_s\sum_{i=0}^\infin\gamma^iP(s_t=s|\pi)$ 이다.
이를 순서를 바꾸면 $\sum^\infin_{i=0}\gamma^i\sum_sP(s_t=s|\pi)$ 로 표현할 수 있고
여기에서 각 시간 t에서 모든 state에 있을 확률의 합은 1이다.
$\sum_sP(s_t=s|\pi)=1$
그렇기에 $\sum^\infin_{i=0}\gamma^i\sum_sP(s_t=s|\pi)=\sum^\infin_{i=0}\gamma^i$
$\sum^\infin_{i=0} \gamma^i=\frac{1}{1-\gamma}$ 이기 때문에 $\sum_s\rho_\pi(s)=\frac{1}{1-\gamma}$ 이다. 이전의 $\rho_\pi(s)$ 는 unnormalized 였기에 정규화가 되지 않았는데 이를 총합으로 나누면 즉 $(1-\gamma)\rho_\pi(s)$ 의 형태로 [0,1]의 분포로 정규화를 시켜줄 수 있다.
이를 통해 확률과 같이 표현이 가능하고
$\frac{1}{1-\gamma} \mathbb E_{s\sim\rho_{\theta_{\text{old}}}}[...]$ 로 결국 표현이 가능해진다.

이후 $A_{\theta_\text{old}}$ 를 $Q_{\theta_\text{old}}$ 로 바꾼다. 이 부분은 원래 REINFORCE에서도 사용하는 방법이기에 사용하는 것 같다.
그리고 importance sampling을 통해서 sum을 기댓값으로 바꾸는데
$\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].$ 이렇게 된다.
그냥 앞부분에 $\frac{q(a|s_n)}{q(a|s_n)}$ 을 곱해서 expectation으로 변경한 것이다.
q는 sampling distribution이다.

이 내용을 종합하면
$\begin{aligned} \text{maximize}_\theta \quad & \mathbb{E}_{s \sim \rho_{\theta_{\text{old}}}, a \sim q} \left[ \frac{\pi_\theta(a \mid s)}{q(a \mid s)} Q_{\theta_{\text{old}}}(s, a) \right] \quad (14) \\ \text{subject to} \quad & \mathbb{E}_{s \sim \rho_{\theta_{\text{old}}}} \left[ D_{\text{KL}}(\pi_{\theta_{\text{old}}}(\cdot \mid s) \,\|\, \pi_\theta(\cdot \mid s)) \right] \leq \delta. \end{aligned}$
이렇게 표현이 된다.
$D_{\text{KL}}$ 의 평균화 부분은 원래 평균이었기에 쉽게 바로 표현이 가능하다.

이를 활용한 학습 방법이 2가지가 있다

single path: sampling individual rajectories에서 policy gradient로 학습
vine: rollout set을 구성하고 각 rollout set의 state에서 multiple action을 진행

위 그림에서 왼쪽이 single path, 오른쪽이 vine이다.
single path는 trajectory에서 state, action pair를 이용해서 학습
vine은 여러개의 trajectory를 만들고 도달한 state에서 branch rollout을 진행해서 여러경로를 동시에 학습 진행

5.1 Single Path

매우 간단하다.
$s_0\sim \rho_0$ 에서 policy $\pi_{\theta_\text{old}}$ 를 따라서 trajectory $s_0,a_0,s_1,a_1,...,s_{T-1},a_{T-1},s_T$ 를 생성하고 $q(a|s)=\pi_{\theta_\text{old}}(a|s)$ 의 상황에서
$Q_{\theta_\text{old}}(s,a)$ 를 계산하고 (14)의 최적화 문제를 푸는 방향으로 학습을 진행

5.2 Vine

이 부분이 조금 어려운데
$s_0\sim \rho_0$ 에서 policy $\pi_{\theta_i}$ 를 따라서 trajecyory를 여러개 생성하는데 이때 subset $N$ 개만큼의 state를 고른다. $s_1,s_2,...,s_N$ 이를 rollout set이라고 부른다.
각 state에서 action $K$ 개를 sampling하는데 $a_{n,k}\sim q(\cdot|s_n)$ 으로 생성한다.
이때 $q(\cdot|s_n)=\pi_{\theta_i}(\cdot|s_n)$ 는 continuous problem에서 잘 작동했고 uniform distribution은 exploration에 도움을 줘서 아타리 등의 discrete task에서 잘 작동했다고 한다.

sampling한 state와 action을 시작으로 rollout을 진행해서
$\hat Q_{\theta_i}(s_n,a_{n,k})$ 를 추정한다. 이를 동일한 난수 시퀀스로 여러번 뽑음으로써 rollout의 variance를 줄일 수 있다.

이때 작고 유한한 공간에서는 state에서 모든 action에 대한 rollout을 만들 수 있다. 특정한 상태 $s_n$ 에서 기여하는 부분은 다음과 같다.
$L_n(\theta) = \sum_{k=1}^K \pi_\theta(a_k \mid s_n) \hat{Q}(s_n, a_k),$
이는 state $s_n$ 에서의 L 추정치인데 이를 모든 rollout state에서 평균내서 바꿔서 기존의 목표함수 $L_{\theta_\text{old}}$ 로 바꿔줘야한다.

이를 importance sampling을 이용해서 self-normalized estimator로 만들 수 있는데
single state $s_n$ 에서 얻어지는 $L_{\theta_\text{old}}$ 는 다음과 같다.
$L_n(\theta) = \frac{\sum_{k=1}^K \frac{\pi_\theta(a_{n,k} \mid s_n)}{\pi_{\theta_{\text{old}}}(a_{n,k} \mid s_n)} \hat{Q}(s_n, a_{n,k})} {\sum_{k=1}^K \frac{\pi_\theta(a_{n,k} \mid s_n)}{\pi_{\theta_{\text{old}}}(a_{n,k} \mid s_n)}},$