[TRPO] Trust Region Policy Optimization

Machine Learning/Reinforcement Learning

[TRPO] Trust Region Policy Optimization

@tai_haku 2022. 7. 7. 14:44

Abstract

TRPO는 샘플기반 제약수반 반복적 정책최적화 알고리즘
TRPO는 단조적 개선을 보장하는 알고리즘
Policy Gradient(정책 경사) 알고리즘과 유사하며 규모가 큰 비선형 정책최적화 문제에 효과적
엔지니어링적 측면에서 이론 전제와는 다소 오차가 있는 상황에서도 우수성 입증

Introduction

정책최적화 알고리즘 대분류
1. Policy Iteration(정책반복)
2. Policy Gradient(정책경사)
3. Derivative-free(비 미분최적화) → 구현, 이해 용이 → 선호
Policy Gradient 방법은 샘플복잡도가 낮은데도 불구하고 Derivative-free 방법보다 성능이 낮음
반면, 최근 Continuous gradient-based 방법은 지도학습과 강화학습에서 두각을 나타내고 있는 최적화 방법
이에 본 논문에서는 첫번째로 다양한 Step size 기반의 ‘Minimizing of surrogate objective function(보조목적함수 최소화)’이 정책의 단조개선을 보장함을 증명
이러한 개념을 기반으로 하는 알고리즘을 ‘Trust Region Policy Optimization(TRPO)’라고 하며, 2가지 버전이 존재함
- Single Path
- Vine
TRPO는 수만개의 파라미터를 가진 규모가 큰 비선형적 정책에 대한 최적화가 가능한 방법

Preliminaries

어떤 정책 $\pi$에 대한 기대보상식

$$ \begin{align*}&\eta(\pi)=\mathbb{E}{s_0,a_0,\dots}[\overset{\infin}{\underset{t=0}{\sum}}\gamma^tr(s_t)],\ where\\&s_0\sim\rho_0(s_0),a_t\sim\pi(a_t|s_t),s{t+1}\sim P(s_{t+1}|s_t,a_t)\end{align*} $$

행동가치함수(Q함수), 상태가치함수(V함수), Advantage함수

$$ \begin{align*}&Q_\pi(s_t,a_t)=\mathbb{E}{s{t+1},a_{t+1},\dots}[\overset{\infin}{\underset{l=0}{\sum}}\gamma^lr(s_{t+l})]\\&V_{\pi}(s_t,a_t)=\mathbb{E}{a_t,s{t+1},\dots}[\overset{\infin}{\underset{l=0}{\sum}}\gamma^lr(s_{t+l})]\\&A_{\pi}(s,a)=Q_\pi(s,a)-V_\pi(s),\ where\\&a_t\sim\pi(a_t|s_t),s_{t+1}\sim P(s_{t+1}|s_t,a_t)\ for\ t\ge0.\end{align*} $$

또다른 어떤 정책 $\tilde{\pi}$에 대한 기대보상식을 어떤 정책 $\pi$의 기대보상식을 갖고 누적 Advantage함수로 기술한 식

$$ \begin{align}\eta(\tilde{\pi})=\eta(\pi)+\mathbb{E}{s_0,a_0,\cdots\sim\tilde{\pi}}[\overset{\infin}{\underset{t=0}{\sum}}\gamma^tA\pi(s_t,a_t)]\end{align} $$

할인방문빈도식

$$ \begin{align}&\rho_\pi(s)=P(s_0=s)+\gamma P(s_1=s)+\gamma^2P(s_2=s)+...,\\&where\ s_0\sim\rho_0,\quad actions\ are\ chosen\ according\ to\ \pi\end{align} $$

$(1)$번 식에 대해 $(2)$번 식을 적용하여 변환한 식

$$ \begin{align}&\eta(\tilde{\pi})=\eta(\pi)+\overset{\infin}{\underset{t=0}{\sum}}\underset{s}{\sum}P(s_t=s|\tilde{\pi})\underset{a}{\sum}\tilde{\pi}(a|s)\gamma^tA_\pi(s,a)\\&=\eta(\pi)+\underset{s}{\sum}\overset{\infin}{\underset{t=0}{\sum}}\gamma^t P(s_t=s|\tilde{\pi})\underset{a}{\sum}\tilde{\pi}(a|s)A_\pi(s,a)\\&=\eta(\pi)+\underset{s}{\sum}\rho_{\tilde{\pi}}(s)\underset{a}{\sum}\tilde{\pi}(a|s)A_\pi(s,a)\end{align} $$

상기 식이 시사하는 바는 어떤 정책이 모든 상태에 대해 기대되는 Advantage가 음이 아닌 다음 정책으로 갱신된다면, 이것이 정책의 성능을 보장하고 더 나아가 일정하게 유지된다는 것
이는 Deterministic(결정적인) 정책을 사용하는 Policy Iteration(정책반복 알고리즘)에 의해 수행되는 갱신이 적어도 하나의 상태-행동 쌍이 양의 Advantage를 갖고 방문빈도가 0이 아닌 정책을 개선해옴을 나타냄
하지만 Approximation setting(근사 설정)에서 추정 및 근사에 의한 오차 발생을 피할 수 없음
할인방문빈도의 정책에 대한 종속성은 $(6)$번식을 최적화하는데 어려움을 줌
이 문제를 해결하고자, 본 논문은 $\eta$로 지역 근사화 항 도입

$$ L_\pi(\tilde{\pi})=\eta(\pi)+\underset{s}{\sum}\rho_\pi(s)\underset{a}{\sum}\tilde{\pi}(a|s)A_\pi(s,a) $$

상기 식에서 $L_\pi$항은 빈도식으로 $\rho_{\tilde{\pi}}$대신 $\rho_\pi$ 사용 → 정책 종속성 해결
하지만, 만약 미분가능한 파라미터로 구성된 함수식(신경망)을 갖게 되면 $L_\pi$와 $\eta$는 일치

$$ \begin{align*}&L_{\pi_{\theta_0}}(\pi_{\theta_0})=\eta(\pi_{\theta_0}),\\&\nabla_\theta L_{\pi_{\theta_0}}(\pi_{\theta_0})=\nabla_\theta\eta(\pi_{\theta_0})|_{\theta=\theta_0}\end{align*} $$

상기 식은 $L_\pi$를 개선하는 step은 $\eta$ 또한 개선함을 암시 → 하지만, 개선 정도는 미지수
‘개선의 하한선’을 제공하고자 고안된 ‘Conservative Policy Iteration(보수적 정책반복)’ 정책갱신계획법
새 정책이 다음과 같이 혼합정책으로 정의되었을 때,

$$ \pi_{new}(a|s)=(1-\alpha)\pi_{old}(a|s)+\alpha\pi'(a|s) $$

Lower bound는 다음과 같음

$$ \begin{align}&\eta(\pi_{new})\ge L_{\pi_{old}}(\pi_{new})-\frac{2\epsilon\gamma}{(1-\gamma)^2}\alpha^2\\&where\ \epsilon=\underset{s}{max}|\mathbb{E}{a\sim\pi'(a|s)}[A\pi(s,a)]|&\end{align} $$

허나, 해당 하한은 혼합정책에만 사용 가능(제한적, 고난도) → 일반적(범용, 쉬운) 방법 필요

Monotonic Gradient Improvement Guarantee for General Stochastic Policies

Conservative Policy Iteration이 적용된 $(7)$번 방정식은 우변 항의 방향으로 정책갱신이 이루어지면, 성능 $\eta$가 개선됨을 보장한다는 내용을 나타냄
하지만, 해당 하한은 혼합정책에 대해서만 사용가능하다는 문제점이 있었고 이를 해결하기 위해 본 논문에서는 학습률 $\alpha$를 $\pi$와 $\tilde{\pi}$간 거리메트릭 수치로, 상수 $\epsilon$를 다른 특정 수치로 적절히 바꿔 일반화 하고자 함
$\alpha$ 변환 과정에서 ‘Total variation divergence(총분산 거리)’ 메트릭을 사용하는데 이에 따라 아래의 하한식을 충족(증명 → 부록 A)

$$ \begin{align*}&\eta(\pi_{new})\ge L_{\pi_{old}}(\pi_{new})-\frac{4\epsilon\gamma}{(1-\gamma)^2}\alpha^2\\&where\ \epsilon=\underset{s,a}{max}|A_\pi(s,a)|\end{align*} $$

총분산 거리와 KL 발산 간 관계 식에 따라 아래와 같은 하한식을 충족

$$ \begin{align*}&\eta(\tilde{\pi})\ge L_\pi(\tilde{\pi})-CD_{KL}^{max}(\pi,\tilde{\pi}),\\&where\ C=\frac{4\epsilon\gamma}{(1-\gamma)^2}\end{align*} $$

하기 알고리즘은 이 방정식에 따라 정책에 대한 단조증가개선을 보장하는 정책반복알고리즘

$M_i(\pi)=L_{\pi_i}(\pi)-CD_{KL}^{max}(\pi_i,\pi)$라는 가정 하에 아래와 같은 수식이 만족하기 때문에 $M_i$를 반복 최대화하는 것은 성능 $\eta$가 최소한 현상유지나 단조증가개선함을 보장

$$ \begin{align*}&\eta(\pi_{i+1})\ge M_i(\pi_{i+1})\\&\eta(\pi_i)=M_i(\pi_i),\ therefore,\\&\eta(\pi_{i+1})-\eta(\pi_i)\ge M_i(\pi_{i+1})-M_{\pi_i}(\pi_i)\end{align*} $$

상기 알고리즘은 Minorization-Maximazation 알고리즘의 종류로, $M_i$는 Surrogate function(보조함수)으로서 Proximal gradient와 Mirror descent 최적화를 연상시킴
TRPO는 이 알고리즘을 안정적 갱신을 위해 Penelty기반 제약이 아닌 KL 발산기반의 제약을 통해 근사화한 알고리즘

Optimization of Parameterized Policies

이전 장의 내용들은 정책의 파라미터를 고려하지않고 모든 상태에 대해 평가가능하다는 가정 하에 정책 최적화 문제를 고려
본 장에서는 유한개의 샘플과 임의의 파라미터를 기반으로한 실질적 알고리즘 도출

$$ \begin{align*}&\underset{\theta}{maximize}[L_{\theta_{old}}(\theta)-CD_{KL}^{max}(\theta_{old},\theta)]\ then,\\&\ improcement\ of\ \eta\ can\ be\ guaranteed\end{align*} $$

실전 적용 시, 패널티계수 $C$를 적용하는 것은 장기적 학습의 경우에 대해 step size(학습률)이 작다는 문제가 있음
이 때문에 안정적 장기학습을 위한 제약으로서 신, 구 Policy 간 KL 발산을 제약으로 사용

$$ \begin{align*}&maximize\ L_{\theta_{old}}(\theta)\\&subject\ to\ D_{KL}^{max}(\theta_{old},\theta)\le\delta\end{align*} $$

이를 적용함에 있어서 문제점은 이론의 관점에서 KL 발산이 모든 상태에 제약을 가해야 한다는 것 → 하지만, 실질적으로 이는 너무 많은 수의 제약을 필요로 함
이에 따라서 하기 식과 같이 평균 KL 발산 사용

$$ \bar{D}{KL}^\rho(\theta_1,\theta_2):=\mathbb{E}{s\sim \rho}[D_{KL}(\pi_{\theta_1}(\cdot|s)|\pi_{\theta_2}(\cdot|s))] $$

이에 따라 최적화 문제를 해결하는 솔루션 제안

$$ \begin{align*}&\underset{\theta}{maximize}\ L_{\theta_{old}}(\theta)\\&subject\ to\ \bar{D}{KL}^{\rho{\theta_{old}}}(\theta_{old},\theta)\le\delta\end{align*} $$

Sample-Based Estimation of the Objective and Constraint

앞서 총기대보상추정을 매 갱신마다 정책의 변화에 제약을 가하며 정책을 최적화하는 방법 소개
본 장에서는 MonteCarlo(샘플 기반 시뮬레이션) 방법을 통해 어떻게 목표함수와 제약함수를 근사하는지 보임
우선, 다음과 같이 상기 방정식을 확장하여 최적화 문제를 해결하고자 함

$$ \begin{align*}&\underset{\theta}{maximize}\ L_{\theta_{old}}(\theta)\rightarrow \underset{\theta}{maximize}\ \underset{s}{\sum}\rho_{\theta_{old}}(s)\underset{a}{\pi_\theta}(a|s)A_{\theta_{old}}(s,a)\\&subject\ to\ \bar{D}{KL}^{\rho{\theta_{old}}}(\theta_{old},\theta)\le\delta\end{align*} $$

상기 식에서 각각의 요소를 아래와 같이 대체

상태천이확률 → 상태천이기반 기댓값 $\times$ $\frac{1}{1-\gamma}$
Advantage → Q
행동 총 합 → 중요도 샘플링(Off-policy)

$$ \begin{align*}&\underset{s}{\sum}\rho_{\theta_{old}}(s)[\cdots]\rightarrow \frac{1}{1-\gamma}\mathbb{E}{s\sim\rho{\theta_{old}}}[\cdots]\\&A_{\theta_{old}}\rightarrow Q_{\theta_{old}}\\&\underset{a}{\sum}\pi(a|s)\rightarrow \frac{\pi_{\theta}(a|s_n)}{q(a|s_n)}\quad q\ is\ distribution\ of\ sample\end{align*} $$

변환버전의 방정식

$$ \begin{align*}&\underset{\theta}{maximize}\ \mathbb{E}{s\sim{\theta_{old}},a\sim q}[\frac{\pi_{\theta}(a|s)}{q(a|s)}Q_{\theta_{old}}(s,a)]\\&subject\ to\ \mathbb{E}{s\sim\rho{\theta_{old}}}[D_{KL}(\pi_{\theta_{old}}(\cdot|s)|\pi_{\theta}(\cdot|s))]\le\delta\end{align*} $$

이제 샘플평균기반의 추정치로 Q를 대체하는 작업 남음

Single Path

개별적으로 샘플링 된 Trajectory 기반 방법
특정정책을 기반으로 일정 시간 동안 Trajectory 생성 → $q(a|s) = \pi_{\theta_{old}}$
$q(a|s)$는 모든 상태에 대해 할일된 기대 보상합으로 계산

Vine

Rollout 세트 구성 및 각 세트 내 상태 별 다수 행동 수행법
특정 정책 기반 Trajectory 생성
N개의 상태 각각에 대한 집합 선택 → S
상태 별 선택가능행동 샘플링 → K개
$\pi_{\theta_i}(\cdot|s)$의 Support를 포함하는 Support와 함께인 $q(\cdot|s_n)$은 일관된 추정기 생산
실전에서 $q(\cdot|s)=\pi_{\theta_{i}}(\cdot|s_n)$이 연속문제에서 잘 작동함을 확인
반면, Uniform distribution(균등분포) 상에서 이산 문제에 잘 작동함을 확인
각 상태에서 추출된 각 행동들에 대해 Rollout 수행 → $\hat{Q}{\theta_i}(s_n,a{n,k})$ 또한, 우리는 rollout간 각 Rollout에 대한 노이즈의 측면에서 같은 개수의 시퀀스를 사용함 → Q 간 분산 축소
정리하면, 이산 행동공간 내 주어진 상태에 대한 가능한 행동들의 Rollout 생성 가능

$$ L_n(\theta)=\overset{K}{\underset{k=1}{\sum}}\pi_{\theta}(a_k|s_n)\hat{Q}(s_n,a_k) $$

연속 행동공간에 대해서는 중요도 샘플링을 통해 보조목적의 함수 추정기를 생성 가능

$$ L_n(\theta)=\overset{K}{\underset{k=1}{\sum}}\frac{\overset{K}{\underset{k=1}{\sum}}\frac{\pi_{\theta}(a_{n,k}|s_n)}{\pi_{\theta_{old}}(a_{n,k}|s_n)}\hat{Q}(s_n,a_{n,k})}{\overset{K}{\underset{k=1}{\sum}}\frac{\pi_{\theta}(a_{n,k}|s_n)}{\pi_{\theta_{old}}(a_{n,k}|s_n)}} $$

상기 추정기는 Q를 Basis(기저)로 사용할 필요성 제거 및 $S_n$을 평균화 함에 따라, $L_{\theta_{old}}$의 추정과 경사를 얻음
본 논문에서 샘플링에 사용되는 Trajectory가 다양한 지점에서 몇개의 짧은 오프샷으로 분기되는 덩굴줄기에 비유될 수 있기 때문에 Vine(덩굴)이라는 용어 사용
Single path 대비 Vine의 장$\cdot$단점
- Vine 장점
  - 보조목적함수에서 동일한 개수의 Q가 주어질 때, 목적함수에 대한 우리의 추정치가 갖는 분산이 낮아짐 → 이는 더 나은 Adv 추정 제공
- Vine 단점
  - 추정치 계산을 위해 더 많은 연산 필요
  - Rollout 세트 속 각 상태에 대해 다수의 Trajectory 생성을 요구 → 임의 상태로 될 수 있는 시스템에 적용 제한

Practical Algorithm

2가지 실질 정책최적화 소개
Q 추정 샘플링 → Single path or Vine 기반 MonteCarlo 샘플링
샘플 평균을 기반으로 평가 Objective function(목적함수) 구성 및 방정식 상의 Contraint(제약 = Surrogate function) 구성
$\theta$로 구성된 정책을 갱신하는 제약있는 최적화 문제를 Approximation(근사)적으로 풀기 → Gradient(경사) 기반의 방법보다 연산량 많음
Fisher information matrix(피셔정보행렬)을 KL 발산의 Hessian을 계산 함에 따라 계산 → Covariance(공분산) 사용 X → Hessian은 Dense(밀도)이기 때문에 모든 경사를 계산할 필요가 없어 연산량 축소 가능
정책 개선 비율은 경험적인 FIM과 유사
정리
1. 보조목적함수 기반 최적화 간 KL 발산 기반의 패널티 부과방식으로 정의
2. 모든 상태 기반 제약은 수가 많아 계산량 극대화 → 추출된 샘플 기반으로 한정
3. 본 이론은 Advantage에 대한 Prediction error(추정 에러) 무시

Connections with Prior Work

유관 이전 연구들
- Natural GD = 방정식(12)의 특수해
- 선형근사 to $L$
- 2차근사 to $D_{KL}$ = KL 발산
$$ \begin{align*}&\underset{\theta}{maximize}[\nabla_\theta L_{\theta_{old}}(\theta)|{\theta={\theta}{old}}\cdot(\theta-\theta_{old})]\\&subject\ to\ \frac{1}{2}(\theta_{old}-\theta)^TA(\theta_{old})(\theta_{old}-\theta)\le\delta,\\&where\ A(\theta_{old}){ij}=\frac{\partial}{\partial\theta_i}\frac{\partial}{\partial\theta_j}\mathbb{E}{s\sim\rho_\pi}[D_{KL}(\pi(\cdot|s,\theta_{old})||\pi(\cdot|s,\theta))]|{\theta=\theta{old}}.\end{align*} $$
- 갱신 식 → 미묘한 계산식 차이 = 큰 결과 차이
$$ \theta_{new}=\theta_{old}+\frac{1}{\lambda}A(\theta_{old})^{-1}\nabla_{\theta}L(\theta)|{\theta=\theta{old}} $$
- 정책반복 갱신 문제
$$ \begin{align*}&\underset{\theta}{maximize}[\nabla_{\theta}L_{\theta_{old}}(\theta)|{\theta=\theta{old}}\cdot(\theta-\theta_{old})]\\&subject\ to\ \frac{1}{2}||\theta-\theta_{old}||^2\le\delta.\end{align*} $$
- REPS → $(s,a)$의 한계밀도함수 사용, 비선형 최적화 기법 필요
- KL 발산을 사용하는 다른 방법도 존재 → 동역학 모델의 유효 구간 내 결속 제약으로 사용

Experiments

신경망 구조

Locomotion from MuJoCo
- 실험 주안점
  1. 샘플링 방식 간 비교 → Single-path vs Vine
  2. 이전 연구대비 성능 유효성
  3. 스케일이 큰 문제 적용 가능성
- 하이퍼파라미터
  - $\delta=0.01$
  - 나머지 = 부록 D
- 성능 비교 알고리즘
  - Single-path TRPO
  - Vine TRPO
  - CEM
  - CMA
  - Natural gradient
  - Empirical FIM
  - Max KL
- 알고리즘 당 5회 평균 보상 곡선

Single-path TRPO, Vine TRPO 모두 해결
NGD는 Hopper Walker 학습 실패 → KL divergence Rubust하다는 사실
CEM, CMA → High sample complexity → 성능 나쁨
Max KL → Slow convergence → 결과는 Average KL constraint와 근사한 결과 도출
결론 = TRPO는 최소한의 도메인 지식, 단순한 보상체계, 범용정책구조를 갖고 다양한 학습 보폭에 따라 학습 가능

Game from Atari
- 실험 주안점
  - 관측복잡과제에 대한 평가 수행
- 하이퍼파라미터
  - 2개층
  - 16채널, 2-stride
  - 전결합층 20개 노드
- 결론
  - TRPO 압도적 성능

저작자표시