(A3C) Asynchronous Methods for Deep Reinforcement Learning

google
reinforcement
deepmind
icml
icml2016

#1

구글 #google#deepmind 에서 나온 페이퍼입니다. 개념적으로 복잡성이 증가하지 않으면서, 매우 가벼운 RL 프레임워크입니다.

여러 Agent를 동시에 각각 다른 Environment에서 행동하여 경험을 쌓되, 결과를 학습시키는 네트워크는 공유하는 형태입니다. 기존에는 1개의 Agent가 시간 순서대로 경험한 결과를 메모리에 쌓아서 과거 데이터로 학습을 시켰고, 이를 replay memory 라고 불렀습니다. 이 논문에서 제안한 agent는 동일한 policy, value network를 공유하되 여러 환경에서 학습하며, replay memory 개념을 사용하지 않습니다.

이 논문은 결과적으로 A3C : Asynchronous Advantage Actor-Critic RL을 제안합니다.

이 논문에서 제안한 A3C 알고리즘은 여러 환경에서 학습시켰을 때,

  • 더 적은 Computation Resource 만으로 : 16cpu without gpu
  • 더 우수한 결과를 : Atari 2600 등에서 outperform
  • 빠른 시간 내에 : 수십배까지 빠른 속도로

얻었습니다.

Background

기존의 RL Agent가 학습 환경에서 시간 순으로 데이터를 얻으면, 얻어진 action-state-reward 데이터는 non-stationary, strong correlated 하다고 볼 수 있습니다. 쉽게 1초전의 경험이나 지금의 경험이나 비슷비슷하고, 둘이 서로 관계가 있다는 뜻으로 해석하면 됩니다. 이 부분을 해소하기 위해 DQN 등에서 replay memory를 이용해 좋은 성과를 report 했고요.

image
DQN(Deepmind) : https://www.cs.toronto.edu/~vmnih/docs/dqn.pdf

그 이후에는 General Reinforcement Learning Architecture (Gorila) 로 알려진 논문에서 distributed 환경에서의 학습을 보여주기도 했습니다. 여러 agent로 replay memory를 쌓아 학습에 사용했다는 것이 DQN에서의 차별성입니다.

Li & Schuurmans, 2011 에서는 Map Reduce 프레임워크로 batch reinforcement learning을 시도한 경우도 있습니다. 혹은, Grounds & Kudenko, 2008 의 경우 여러 agent가 학습하다가 주요한 변화가 있을 때마다 전달하는 시도도 있었고요.

이 논문에서는 replay memory의 역할을 multiple agent의 다양한 경험으로 해소하려고 합니다. 즉 1개의 agent 만으로 얻은 데이터는 timely correlated 하지만, 그런 여러 agent는 서로 correlated 되어 있지 않으므로 replay memory를 대체하였다는 것입니다.

Asynchronous RL Frameowork

4가지의 RL Framework를 제안합니다. 물론 최종적으로는 A3C 가 최고지만…

  • Asynchronous 1-step Sarsa
  • Asynchronous 1-step Q-Learning
  • Asynchronous n-step Q-Learning
  • Asynchronous Advantage Actor-Critic(A3C) RL

여기에서는 A3C 만을 주로 다루겠습니다. 이름에서 이미 프레임워크의 특징을 많이 내포하고 있습니다.

Asynchronous

Asynchronous한 Action Learner(Agent)를 사용해서 붙은 이름입니다. 여러개의 Agent가 각각 다른 Environment에 Action을 취하며 경험을 얻습니다. 이 과정이 Async하다고해서 붙었습니다.

특이점은 아래와 같습니다.

  • 1 Machine 에 Multi Thread로 구현했다는 점입니다. 즉 Agent의 최대 개수는 Thread 수 만큼으로 한정되었음에도 좋은 성능을 냈습니다.
  • 각 action learner가 서로 다른 exploration policy를 갖도록 했고, 이 부분이 더 좋은 성능과 Robustness에 영향을 주었다고 합니다.

Advantage

Q-Learning과 같이 Discounted Return을 직접 Estimate하기도 하지만 여기에서는 예상치(Expected)보다 실제로 얼마나 더 나았는지를 Advatage로 정의하고

Advantage A = Q(s,a) - V(s)
Advantage Estimate A'=R-V(s)

이를 Loss 에서 사용합니다.

Actor-Critic

Actor-Critic은

  • Actor : Policy \pi(s) (Action probabilities) 를 통해 Action을 취하는 Agent
  • Critic : Value Function V(s) 를 통해 현재 상태를 Evaluation

로 구성되어 있습니다.

A3C Algorithm

모든 Worker들이 공유하는 네트워크는 2개의 Output을 갖습니다.

  1. Policy \pi(a_t | s_t;\theta)
  2. Value Function V(s_t ; \theta_v)

(꼭 그럴 필요는 없지만) 논문에서는 네트워크의 base는 갖고 위 2가지 output만 출력되도록 설계했습니다.

또 네트워크의 마지막 output 부근에 lstm 을 추가해 memory 로 사용될 수 있게 만들었습니다. DQN 등에서 여러 frame을 넣는 것 대비 훨씬 나은 형태의 네트워크 모델링이겠죠.

Policy Loss

일반적인 actor-critic에서는, Policy에 관계된 Loss는 아래처럼 정의됩니다.

Policy Loss: L_p = log(\pi(s)) \times A(s)
  • 이해를 위해 정성적으로 해석하자면, Advantage A(s) 가 양수인 경우(기대보다 더 좋은 경우) Policy에서 해당하는 action은 1의 방향으로, A(s) 가 음수인 경우(기대 보다 나쁜 경우) 0의 방향으로 트레이닝 되고 실제 값과 예측 값의 차이인 Advantage는 줄어드는 방향으로 트레이닝 됩니다.
  • 이해하기 좋은 블로그 아티클을 소개합니다 : https://medium.com/@awjuliani/super-simple-reinforcement-learning-tutorial-part-1-fd544fab149
  • 이렇게 action들에 대해 얼마나 좋아져야하는지를 평가하기 때문에 'action-critic’이라고 부릅니다.
  • 논문에서는 위의 일반적인 loss에 \pi 에 대한 entropy loss를 아래와 같이 추가해서, 보수적인 모델로의 early converge를 막는다고 합니다.
Policy Loss: L_p' = log(\pi(s)) \times A(s) + \beta \times H(\pi)

Value Loss

Policy Loss에 Advantage에 대한 Loss도 포함되어 있지만, Value Loss 역시 추가합니다.

Value Loss: L_v = \sum(R-V(s))^2

따라서 최종적인 Loss L = L_p' + 0.5 \times L_v 로 linear combination하여 정의했습니다. 참고로 entropy에 사용된 파라미터 \beta 는 0.01 정도를 사용했구요.

이렇게 정의된 네트워크는 아래와 같은 Flow를 따라 사용됩니다.

(1) Thread 별로 생성된 Worker는 Shared Parameter 로부터 동일한 Network을 카피.
(2) 각 Worker는 서로 다른 Environment에서 서로 다른 Exploration Policy를 가지며 탐색
(3~5) 각 Worker가 Value / Policy Loss로부터 Gradient를 구하고 각 Worker가 Asyncronous하게 Shared Parameter를 업데이트

마치 Multi-GPU Training에서 Asynchronous SGD 가 학습하듯이 여러 Worker가 Shared Parameter를 업데이트하는 구조입니다. 논문에서는 약간 modified된 RMSProp이 가장 성능이 좋았다고 설명하고 있습니다.

수도코드로 하나의 워커가 하는 일을 적어보면 아래와 같습니다.

Experiments

Atari 2600에서 대표적인 5가지 게임을 선정했고, DQN에 비해 더 짧은 시간에 더 높은 퍼포먼스를 보이는 agent를 안정적으로 학습했음을 보여주고 있습니다. 이 5가지 게임에 대해 hyper-parameter를 최적으로 선별한 후 나머지 아타리 게임에 대해서도 동일하게 적용해 outperform하는 결과를 얻었습니다.

image


기타 실험 결과를 요약하면

Evaluations

  1. Thread 수에 따라 매우 효과적으로 scale-up 된다.

image

Data Exploration Ability의 향상으로 parallel한 worker 수가 증가함에 따라 트레이닝 시간이 단축됨을 볼 수 있습니다. 놀랍게도 선형 이상으로 증가하기도 하는데, 이는 적은 수일때에 대비해서 bias를 제거해주는 effect로 해석했습니다.

  1. Robust 하며 Stable 하다.

RL에서 트레이닝 되던 Agent가 Collapse하거나 Diverge 하는 경우가 있어 트레이닝이 상대적으로 어려운데, 이 논문에서는 hyper parameter 등에 따라 robust함을 보였습니다. 특히 여러 실험에도 트레이닝이 잘되는 Learning Rate 구간 값 내에서는 Collapse되는 결과는 없었다는 점을 근거로 보였습니다.

Implementations

(1) https://github.com/openai/universe-starter-agent
(2) https://github.com/dennybritz/reinforcement-learning

Reference

[1] Asynchronous Methods for Deep Reinforcement Learning

[2] Medium Blog : https://medium.com/emergent-future/simple-reinforcement-learning-with-tensorflow-part-8-asynchronous-actor-critic-agents-a3c-c88f72a5e9f2

[3] https://github.com/awjuliani/DeepRL-Agents/blob/master/A3C-Doom.ipynb


StarCraft II: A New Challenge for Reinforcement Learning