IMPALA - Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures

Published: 2019-07-01
Last modified:
Category • Tech

IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures https://arxiv.org/abs/1802.01561

저번달에 ‘최금강’님과 함께 IMPALA에 대해서 얘기를 나누고 Implementation을 했는데
이제서야 정리한다.

소개

IMPALA는 A3C알고리즘을 개선하여 기존 A3C의 On-Policy 부분과 함께,

Off-Policy의 특성을 추가하여 데이터의 효율을 높인 방법이라고 할 수 있다.

선행 연구와 비교한 장점

A2C: 각 Agent가 Trajectory를 끝낼때까지 기다려야 함.

A3C: multi-agent가 가능하나 GPU를 활용하지 못함.

GA3C: A3C를 개선하여 GPU를 활용할 수 있도록 Dynamic Batch를 도입했으나, Policy-lag의 개선이 필요함.

그리고 LSTM을 이용하여 Partial Observation뿐만 아니라 Training의 효율을 높이도록 구성하였다.

  • Policy-lag
    1. Agent가 Environment에서 Trajectory를 출력하기위해 사용하는 Policy(Behaviour policy)
    2. 만들어진 Trajectory를 이용하여 Learner가 학습하는 Policy(Target Policy) 1.과2.에 시간차가 있어 엄밀히는 On-policy라 할 수 없음.

제시 기술/방법

IMPALA에서는 Inportance Sampling과 Temporal Difference를 이용한 V-trace Target을 설정하여, Off-Policy특성에서도 학습이 잘 진행되도록 하였다.

  • V-trace Target
    Behavior Policy $\mu$ 를 이용하여, Actor로부터 생성된 $(n+1)$-step Trajectory를 $(x_t,a_t,r_t)_{t=s}^{t=s+n}$라고 하면, state value(V_trace target)는

    \[\begin{align} v_s := &V(x_s)+\sum\limits_{t=s}^{s+n-1}\gamma^{t-s}\left(\prod\limits_{i=s}^{t-1}\right)\delta_tV, \\ &(\text{where,}\quad \delta_tV := \rho_t(r_t+\gamma V(x_{t+1})-V(x_t)))\\ \quad\\ \rho_t :=& \min\left(\bar{\rho},\frac{\pi(a_t|x_t)}{\mu(a_t|x_t)}\right), \\ c_i :=& \min\left(\bar{c},\frac{\pi(a_i|x_i)}{\mu(a_i|x_i)}\right),\\ =& \min\left(\bar{c},\rho_i \right) \end{align}\]

  • Actor-Critic Update
    value parameter($\theta$)의 업데이트(Minimize)

    \[(v_s-V_\theta(x_s))\nabla_\theta V_\theta(x_s)\]

    policy parameter($\omega$)의 업데이트(Maxmize)

    \[\rho_s\nabla_\omega\log\pi_\omega(a_s|x_s)(r_s+\gamma v_{s+1}-V_\theta(x_s)\]

    그리고 entropy bonus(Minimize)

    \[-\nabla_\omega\sum\limits_a\pi_\omega(a|x_s)\log\pi_\omega(a|x_s)\]

  • Implementation 관련하여 몇가지

    • Unroll=20 으로 하였을때에 필요한 environment state의 갯수는 (Unroll+1)개가 필요하다. 또한 각 Trajectory에 대해 20스텝의 v-trace target을 구할때에

      timestep $s$ $a$ $r$ $V(s)$ $v$   $v_{\text{next}}$  
      0 $s_t$ $a_t$ $r_t$ $V(s_t)$ $v_t$   $v_{t+1}$ 20-step
      1 $s_{t+1}$ $a_{t+1}$ $r_{t+1}$ $V(s_{t+1})$ $v_{t+1}$ $\nearrow$ $v_{t+2}$ 19-step
      2 $s_{t+2}$ $a_{t+2}$ $r_{t+2}$ $V(s_{t+2})$ $v_{t+2}$ $\nearrow$ $v_{t+3}$  
      $\vdots$                
      19 $s_{t+19}$ $a_{t+19}$ $r_{t+19}$ $V(s_{t+19})$ $v_{t+19}$ $\nearrow$ $v_{t+20}$ 1-step
      20 $s_{t+20}$ $a_{t+20}$ $r_{t+20}$ $V(s_{t+20})$ $\leftarrow$bootstrap value $\nearrow$    

      $v_\theta(s_{t+19})$를 구하기 위해서는 $s_{t+20}, V(s_{t+20})$이 필요함에 주의해야 한다. 그리고 paper에 나와있듯 \(v_s = V(x_s)+\delta_sV+\gamma c_s(v_{s+1}-V(x_{s+1})).\) 를 이용하여 reverse로 v-trace target을 구할 수 있다.

    • Original 논문처럼 LSTM을 이용할경우 Tensorflow의 경우엔 Dynamic RNN을 이용하여 LSTM state를 보존해 주어야 한다. 그러나 Actor->Learner로 넘어갈때에 필요한 것은 Trajectory의 가장 처음에 있는 lstm state만이 필요하다. v_trace target을 구할시에 recursive하게 lstm의 h,c를 다시 구해주어야 한다.

    • weight 갱신 타이밍
      Tensorflow의 가변 사이즈 array인 nest를 사용하면 문제 없지만, 나 같은 경우에는 numpy array로 feed_dict를 사용해서 tensor에 넘겼다. 그렇기 때문에 array shape는 고정적이고, 중간에 terminal state가 포함되더라도, weight 갱신을 하지 않고, unroll push를 할때에만 갱신하도록 하였다.

    • Policy Update에 관해서
      $\rho_s$를 $c_s$로 truncate하지 않았을때,

      \[\begin{align} \rho_s(r_s+\gamma v_{s+1}-V_\theta(x_s)) = (v_{s}-V_\theta(x_s)) \end{align}\]

      이다. 그러므로, Policy Update식은,

      \[\nabla_\omega\log\pi_\omega(a_s|x_s)(v_{s}-V_\theta(x_s))\]

      로 고쳐쓸수있다. 내가 잘못봤나해서 뒤에 Appendix도 보고 확인해봐도 헷갈려서 저자에게 메일했더니, Appendix확인하라는 답장을 받았다.(…)

      혹시, 지나가다 뭐가 잘못되었는지 아는분 계시면 코멘트 부탁드립니다.

      내가 쓴 코드에선 \(\nabla_\omega\log\pi_\omega(a_s|x_s)(v_{s}-V_\theta(x_s))\) 로 고쳐도 학습은 잘 진행되는걸 확인하였다.

Related Posts