0%

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) (S,A,P,r,ρ0,γ)

  • S is a finite set of states
  • A is a finite set of actions
  • P:S×A×SR is the transition probability distribution
  • r:SR is the reward function
  • ρ0:SR is the distribution of the initial state s0
  • γ(0,1) is the discount factor

Let

  • π:S×A[0,1] is a stochastic policy
  • η(π)=Es0,a0,[t=0γtr(st)] is the expected discounted reward
    • s0ρ0(s0)
    • atπ(atst)
    • st+1P(st+1st,at)
  • Qπ(st,at)=Est+1,at+1,[l=0γlr(st+l)] is the state-action value function
  • Vπ(st)=Eat,st+1,[l=0γlr(st+l)] is the state value function
  • Aπ(s,a)=Qπ(s,a)Vπ(s) is the advantage function

Kakede & Langford (2002)에 대한 요약

η(π~)=η(π)+Es0,a0,π~[t=0γtAπ(st,at)]=η(π)+sρπ~(s)aπ~(as)Aπ(s,a)

where ρπ(s)=P(s0=s)+γP(s1=s)+γ2P(s2=s)+

  • 직감적으로, π~에 대한 evaluation을 π를 가지고 할 수 있다는 것이다.
  • 만약 모든 state s에 대해서, aπ~(as)Aπ(s,a)0 일 경우 policy improvement가 보장된다.

하지만, 실제로는 Aπ(s,a)는 샘플링 기반으로 approximation하게 될 것이다.

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

그 경우엔 ρπ~(s)는 장애물이 될 것이다.

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

Lπ(π~)=η(π)+sρπ(s)aπ~(as)Aπ(s,a)

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

  1. Lπθ0(πθ0)=η(πθ0)
  2. θLπθ0(πθ)|θ=θ0=θη(πθ)|θ=θ0 Sutton, 1999

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

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

  • Let π=argmaxπLπold(π)
  • Let πnew (as)=(1α)πold (as)+απ(as)
  • Then, η(πnew )Lπold (πnew )2ϵγ(1γ)2α2 where ϵ=maxs|Eaπ(as)[Aπ(s,a)]|

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

3. Monotonic Improvement Guarantee for General Stochastic Policies

Let

  • DTV(p|q)=12i|piqi|
  • DTVmax(π,π~)=maxsDTV(π(s)|π~(s))

Theorem 1

​ Let α=DTVmax(πold,πnew). Then,

η(πnew)Lπold(πnew )4ϵγ(1γ)2α2where ϵ=maxs,a|Aπ(s,a)|Lπold (πnew )4ϵγ(1γ)2DKLmax(πold ,πnew )DTV(pq)2DKL(pq)

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

이 알고리즘은 Aπ에 대한 evaluation이 가능하다고 암묵적으로 가정한다.

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

Let Mi(π)=Lπi(πi+1)CDKLmax(πi,π).

Since η(πi+1)Mi(πi+1) and η(πi)=Mi(πi),

η(πi+1)η(πi)Mi(πi+1)M(πi)0

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

Large update를 robust하게 허용하기 위해 페널티 텀 CDKLmax(πi,π)을 없애고 constraint를 건다.

4. Optimization of Parameterized Policies

이론적인 알고리즘 1은 Aπ에 대한 evaluation이 가능함을 가정하였고 policy search πi+1=argmaxπ[]의 computational complexity를 고려하지 않았다.

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

Let

  • η(θ):=η(πθ)
  • Lθ(θ~):=Lπθ(πθ~)
  • DKL(θ|θ~):=DKL(πθ|πθ~)

Then, πi+1=argmaxπ[Lπi(π)CDKLmax(πi,π)] is expressed as

maximizeθ[Lθold (θ)CDKLmax(θold ,θ)]

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

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

maximizeθLθold (θ) subject to DKLmax(θold,θ)δ

δ를 허용된 step size라고 해석하면 된다.

DKLmax(θold,θ)δ를 확인하기 위해서 모든 state에 대해 KL-divergence를 구하는 것은 비실용적이다.

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

maximizeθLθold (θ) subject to DKLρθold(θold,θ)δ

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

5. Sample-Based Estimation of the Objective and Constraint

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

maximizeθsρθold (s)aπθ(as)Aθold (s,a) subject to DKLρθold(θold,θ)δ

approximation하는 방법을 소개한다.

  1. sρθold (s)[]11γEsρθold [] ;
  2. AθoldQθold  ;
  3. aπθ(asn)Aθold (sn,a)=Eaq[πθ(asn)q(asn)Aθold (sn,a)]

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

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

maximizeθEsρθold ,aq[πθ(as)q(as)Qθold (s,a)] subject to Esρθold [DKL(πθold (s)πθ(s))]δ

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

5.1 Single path

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

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

  1. Sample s0ρ0
  2. Simulate one trajectory a0,s1,a1,,sT1,aT1,sTπθold×P
  3. MC approximation

5.2 Vine

  1. Sample s0ρ0
  2. Simulate multiple trajectories a0,s1,a1,,sT1,aT1,sTπθold×P
  3. Choose N states along these trajectories; {s1,s2,,sN}, called rollout set
  4. For each state sn in the rollout set, sample K actions; an,kq(sn) s.t.
    • supp(πold(sn))supp(q(sn))
    • continuous action을 다룰 땐, q(sn)=πθold(sn)이 좋고
    • discrete action을 다룰 땐, q(sn)=Uni가 좋다. (exploration 측면에서)

모르겠다.

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

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

6. Practical Algorithm

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