본문으로 바로가기

팡요랩 TRPO 논문 리뷰 정리 노트

category Lectures/팡요랩 2019.03.15 10:38

늘 감사히 여기고 있습니다.

서론적인 부분은 제외하고, 논문의 내용에 집중해서 정리해야지! 다음은 PPO해준다니 기대가 된다. 그 때까지 TRPO 구현해봐야지.

Preliminaries

Kakade & Langford (2002)

모든 것의 출발점. 어떤 정책 $\pi$에서 $\tilde \pi$의 성능(보상의 합)과 얼마나 차이나는 지를 표현한다. $\pi$ 성능에다가 $\tilde \pi$에 의해 지나간 경로(trajectory)로 $\pi$의 advantage를 구해서 더하면 $\tilde \pi$의 성능이 된다.

예시

상태 $s_1$, $s_2$, $s_3$가 있고, 위로가는 행동을 $U$, 아래로 가는 행동을 $D$라고 하자. 그리고 $\gamma=1$이라고 가정한다.

상태 $s_1$에 대한 가치는 벨만 방정식에 의해서 다음과 같이 결정된다.

  • $s_1$에서 $U$ 행동 확률 $50% \ (0.5)$, 얻는 보상 $+2$
  • $s_1$에서 $D$ 행동 확률 $50% \ (0.5)$, 얻는 보상 $+4$
  • $V(s_1) = (0.5 \times 2) + (0.5 \times 4) = 3$

이를 이용해 advantage를 구한다면 다음과 같이 구할 수 있다.

  • $s_1$에서 $U$ 행동에 대한 가치는 $r_{s_3} + V(s_3)$
  • $s_1$에서 $D$ 행동에 대한 가치는 $r_{s_4} + V(s_4)$
  • $A_{s_3} = Q_{s_1->s_3} - V_{s_3} = 2 - 3 = -1$
  • $A_{s_4} = Q_{s_1->s_4} - V_{s_4} = 4 - 3 = +1$

그렇게해서 $s_0$, $s_1$, $s_2$, $s_3$, $s_4$ 이 있다고 할 때 정책 $\pi$에 대한 예를 들어서, Value와 Advantage를 구하면 다음과 같이 된다.

이제 어떤 정책 $\tilde \pi$의 성능(보상의 합)을 구하고 싶다. 그 방법은 위에서 나온 식처럼 구할 수 있는데 정말 그런지 알아볼 것이다.

그래서 임의의 $\tilde \pi$에 대한 정책이 있다고 하자

가치가 곧 성능을 말하므로 $\eta(\tilde \pi) = V_{\tilde \pi}(s_0) = 2.75$이고 $\eta(\pi) = V_{\pi}(s_0) = 4$이다. 이제 나머지 Advantage 부분이 어떤지 살펴보자

$$ \mathbb{E}{s_0, a_0, \cdots \sim \tilde \pi} \left [ \sum^\infty_{t=0} A_\pi(s_t, a_t) \right] = \tilde \pi(s_0,U) A_\pi(s_0, U) + \tilde \pi(s_0, D) A_\pi(s_0, D)$$

$$ = \tilde \pi(s_0,U) \left[ \tilde \pi(s_1,U)A_\pi(s_1, U) + \tilde \pi(s_1,D)A_\pi(s_1, D) \right] + \tilde \pi(s_0, D) A_\pi(s_0, D) $$

$$ = 0.5 \left[ 0.25 \times -1 + 0.75 \times 1\right] + 0.5 \times -3 = -1.25$$

정리하자면

$$ \eta(\tilde \pi) = \eta( \pi) + \mathbb{E}{s_0, a_0, \cdots \sim \tilde \pi} \left [ \sum^\infty_{t=0} A_\pi(s_t, a_t) \right] $$

$$ 2.75 = 4 - 1.25 $$

이 되어 식이 성립하는 것을 볼 수 있다. 논문에서는 이러한 식을 증명하는 것도 있다. $A = Q - V = r + \gamma V -V$이므로

오른쪽 두 V들은 풀어보면 $-V(s_0) + \gamma V(s_1) - \gamma V(s_1) + \gamma^2 V(s_2) - \gamma^2 V(s_2) + \cdots = -V(s_0)$이 된다.

두 항 다 성능을 의미하지만 왼쪽 항은 $\pi$에 대한 성능이고 오른쪽은 $\tilde \pi$에 대한 성능이므로 결과적으로 다음과 같이 된다.

식을 정리하면 성립한다는 것이 증명된다. 전체적인 증명은 다음과 같다.

관점의 변화

timestep에 따른 Advantage의 합이 아니라 state에 따른 Advantage 합으로 볼 수 있다. 그 전에 알아야할 것은 Discounted (unnormalized) visitation frequency이다.

첫 번째에서 상태가 $s$일 확률 두 번째에서 $s$일 확률, ... 이런식으로 전부 더하는 데, 이 때 $\gamma$로 discount 시켜서 표현한다. 그러다보니 확률이 1을 넘을 수 있다.(unnormalized)

이를 이용해서, 이전의 식을 state에 따른 Advantage 관점으로 볼 수 있다.

이 때, 모든 상태에 대해서 $\sum_a\tilde \pi (a|s) A_\pi(s, a) \ge 0$ 이라면 $\eta(\tilde \pi) \ge \eta(\pi)$이 되어 성능이 증가함을 보장이 된다. 하지만 실제로는 function approximation으로 근사하기 때문에 approximator error 때문에 음수가 나오는 경우가 있을 수 있다.

그런데 새로운 정책에 대한 $\rho_{\tilde \pi}(s)$를 구하는 것은 쉽지가 않다.(현재 trajectory만을 구하기 때문에) 그래서 구할 수 있는 $\rho_\pi(s)$로 대체하는데 이를 $L_\pi(\tilde \pi)$라 표현한다.

이렇게 막 바꾸어도 되나? 싶지만 된다고 한다. 왜냐하면, 정책을 $\theta$로 파라미터화하고 $\pi_\theta(a|s)$가 미분가능하다고하면, $\theta_0$인 지점에서는 다음 두 식이 성립하기 때문이다.

위 식은 직접 대입해보면 알 수 있다.

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

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

결국 같은 지점이 존재한다는 의미이며, $\eta$대신 $L$을 사용해도 된다. 하지만 완전히 똑같은 게 아니라 $\theta_0$ 지점에서만 같고 멀어질 수록 많이 차이나기에 step이 어느 정도 충분히 작아야 한다. 하지만 어느 정도 작아야 할지 식에서는 알 수가 없다. 그래서 Kakade & Langford는 Conservative policy iteration라는 정책 업데이트 방법론을 제시한다.

Conservative policy iteration

Conservative(보수적인) 업데이트 하겠다는 얘기인데, 현재 정책과 새로운 정책의 업데이트 비율을 두고 업데이트 한다. (momentum 같다)

근데 업데이트가 되는지 확실해야 하기 때문에, 최소로 어느 정도 개선되는지 lower bound를 유도해낸다.

이전 정책과 현재 정책로 업데이트하는 섞은 정책(mixture policy) 실질적으로 별 도움이 되지 않는다. 그래서 general하게 통용되는 방법이 필요하다.

General improvement guarantee

Total variance divergence

general하게 사용하기 위해 두 분포 사이의 차이를 표현하는 total variance divergence를 사용한다. 다를수록 값이 커질 것이다.

이제 여기에 모든 상태에 대해서 정책의 차이가 최대인 값을 다음과 같이 정의한다.

Theorem 1.

$\alpha$를 정책을 업데이트할 비율이 아니라 이전 정책과 새로운 정책의 total variance divergence가 최대인 값이라 정의한다.

그렇게 해서 기존 mixture policy에 대한 lower bound를 변형해 Theorem 1을 제시한다.

여기에다가 한번 더 변형한다. (아이고) KL Divergence가 Total variance divergence보다 항상 크거나 같다고 증명이 되어있다.

그래서 이를 적용해도 부등식은 변하지 않으므로 KL divergence를 대신 적용한다.

결국 Theorem을 나타내고 KL divergence로 변환한 다음 간단하게 C로 치환을 해서 policy improvement guarantee를 나타낸다.

알고리즘

그렇다면 과연 $\pi_{i+1} = \arg\max\left[ L_{\pi_i}(\pi) - CD^\max_{KL}(\pi_i, \pi)\right]$일 때, $\eta(\pi_0) \le \eta(\pi_1) \le \eta(\pi_2) \le \cdots $가 성립할까? 즉 성능이 개선되는게 맞는 걸까?

간단하게 $M_i(\pi) = L_{\pi_i}(\pi) - CD^\max_{KL}(\pi_i, \pi)$라고 하자. 이전에 나온 것처럼 $\eta(\pi_{i}) \ge L_{\pi_i}(\pi) - CD^\max_{KL}(\pi_i, \pi)$이기 때문에,

$$\eta(\pi_{i+1}) \ge M_i(\pi_{i+1})$$

$M_i(\pi_{i})$라면 $CD^\max_{KL}(\pi_i, \pi_i) = 0$이 되기 때문에,

$$\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$을 값을 크게한다는 것은 곧 $\eta$를 크게한다는 것이 되어서 감소하지 않고 개선된다는 것을 보장해준다. 여기서 $M_i$는 $\eta(\pi)$의 surrogate function이라고 한다.

Practical 하게

실제 문제에 적용하기 위해 $\pi$를 $\theta$로 파라미터화 시킬 것이다.

Penalty가 무서워

위와 같이 파라미터 $\theta$간의 분포의 차이만큼 업데이트 하는데 이 KL-divergence 계수인 C가 너무나 큰 수가 된다.(예를 들어 $\gamma=0.99$인 경우 분모가 0.0001, 즉, 10000을 곱하게 된다) 위와 같은 형태를 Penalty라고 하는데, 이 Penalty 때문에 step size를 많이 줄일 수 밖에 없다. 그래서 이를 해결하기 위해 constraint optimization 문제로 바꾼다.

Max 문제

Max를 알려면 모든 상태를 다 보고 최대인 값을 구해야한다. 하지만 상태가 많은 실세계 문제에서는 적용할 수가 없다. 그래서 대신 heuristicc approximation으로 기댓값(average)을 사용한다.

샘플 기반의 objective and constraint estimation

expectation은 샘플을 통해 구할 수 있다. 그래서 objective($L$)도 distribution 자체를 쓰는 것 대신 기댓값 형태로 바꾼다. 우선 $L$은 다음과 같았다.

여기서 $\sum_s \rho_{\theta_{old}}(s)[...]$를 $\frac{1}{1-\gamma}\mathbb{E}{s \sim \rho{\theta_{old}}}\left[... \right]$로 대체한다. 여기서 $\frac{1}{1-\gamma}$는 무한급수가 되어가면서 값이 바뀌는 것을 막기 위한 항이지만 결국 둘 다 최대화하도록 할 것이기 때문에 없어도 된다.

또 $A_{\theta_{old}}$를 $Q_{\theta_{old}}$로 대체한다. 원래 Advantage를 사용하는 이유가 Variance를 줄이기 위해서 였고 이를 위해 $Q-V$를 했었다. 하지만 $Q$를 최대화하는 거나 $Q-V$를 최대화하는 것(V를 상수 취급)이나 똑같기 때문에 대체해도 상관없다.

기댓값으로 바꾸긴 했는데, 이전 정책에 의한 분포와 다음 정책에 의한 분포가 다르기 때문에 importance sampling을 사용해야 한다.

따라서 위 3 가지를 모두 적용하게 되면 다음과 같이 된다. 결과적으로 동일한 목표로 objective를 maximize하게 된다.

이제 샘플링만 하면 되는데 single path, vine 두 가지가 있다. 슬라이드가 잘 정리되어 있어서 이건 그대로 사용

학습하는 순서를 정리하자면

  1. single path나 vine으로 Q값을 구한다.
  2. 샘플들의 평균을 내서 objective와 constraint를 estimate한다.
  3. 최적화 문제를 풀기 위해 파라미터 $\theta$에 대하여 업데이트 한다. 이 때 line search를 따르는 conjugate gradient 알고리즘을 사용한다.(그냥 gradient를 사용하는 것보다 더 expensive하다)

요약

후반갈수록 지쳤다...

Atari 실험 결과

고생하셨습니다

진짜 논문은 이보다 더 한 내용들이 많다는 것을 알기에 이렇게 정리해주신 팡요랩에 감사함을 느낍니다.ㅠㅠ


댓글을 달아 주세요