![[논문 리뷰] Asynchronous Methods for Deep Reinforcement Learning (A3C)](https://img1.daumcdn.net/thumb/R750x0/?scode=mtistory2&fname=https%3A%2F%2Fblog.kakaocdn.net%2Fdn%2FbQRgkD%2FbtssQatbwNl%2Fw8fiX6kJq79GEdN3KnceX1%2Fimg.webp)
이번 논문에서는 강화학습을 비동기적이게 학습을 하게 만든 논문을 들고 왔다. 이 논문의 특이점이라고 한다면 보통의 학습에서 쓰이는 GPU를 사용하지 않고 CPU 코어들을 통한 병렬학습을 한다는 것이다. 이를 통해 Atari 벤치마크에서 새로운 기록을 세웠고 다른 도메인에서도 좋은 결과를 보여주는 모습이다.
[1602.01783] Asynchronous Methods for Deep Reinforcement Learning (arxiv.org)
Asynchronous Methods for Deep Reinforcement Learning
We propose a conceptually simple and lightweight framework for deep reinforcement learning that uses asynchronous gradient descent for optimization of deep neural network controllers. We present asynchronous variants of four standard reinforcement learning
arxiv.org
Introduction
보통의 online RL알고리즘은 DNN(Deep Neural Network)과 합쳐지면 안정적이지 않았다. 이는 온라인으로 들어오는 데이터들 간의 상관관계가 높았기 때문인데, 이를 DQN에서는 Experience Replay라는 방식을 사용해 데이터를 먼저 저장을 하고 랜덤 하게 학습을 하는 방식을 취했다. 이 방법의 단점은 off-policy RL만 가능하고 메모리와 computation power을 많이 쓴다는 단점이 있다. 또한 옛날 데이터를 학습한다는 문제도 있다.
이 논문에서는 이 문제를 agent들을 parallel로 학습시키는 방법을 사용하여 해결했다. 여러 개의 agent를 사용하면 한 state와 연관된 데이터가 아니라 각각의 agent마다 다른 데이터를 만들어내기 때문에 더 안정적이게 학습을 할 수 있다. 이 아이디어는 다양한 RL 알고리즘에 적용할 수 있는데, 심지어 off-policy 알고리즘에도 적용할 수 있다.
Related Work
General Reinforcement Learning Architecture(Gorilla)에서는 비동기적인 학습을 환경, Replay Memory, learner을 각각의 agent마다 복제해서 학습하였다. Gradient 값을 asynchronous 하게 중앙 서버로 보내어서 모델을 업데이틀 하고 이를 주기적으로 하위 learner에 보내주는 방식을 사용하였다.
Parallelism을 사용하여 matrix operation의 속도를 늘리거나 SARSA를 가속하는 연구도 있었다. 또한, evolutionary 메서드를 병렬화 하여 여러 개의 thread와 node에 나누어서 시뮬레이션을 돌려 학습을 가속화하는 방법도 있다
Reinforcement Learning Background
Value-based RL
앞부분에서는 RL의 원리를 전반적으로 설명하고 있기 때문에 넘어가겠다 (앞에 있는 다른 블로그 글을 참조하자). n-step return에 대해서 잠깐 설명하고 있는데, 이는 일반의 DRL의 one-step return인 $$r + \gamma \max_{a'} Q(s', a'; \theta)$$ 대신에 n개의 step에 걸친 $$r_{t} + \gamma r_{t+1} +... + \gamma^{n-1} r_{t+n-1} + \max_{a} \gamma^n Q(s_{t+n}, a)$$을 사용하는 것이다. 나중에 이 논문도 리뷰를 할 예정이다. 이 방식의 장점은 하나의 reward가 n개의 state-action에 영향을 준다는 것이다. 즉, 더 효율적인 학습이 가능하다.
Policy-based RL
Value-based와 다르게 policy 자체를 평가하는 방식이다. 이 방식도 많이 사용되어서 곧 policy-based RL에 관한 리뷰를 할 예정이다. Policy $\pi (a|s;\theta)$가 있을 때 $\mathbb {E}[R_t]$에 대한 경사상승을 진행한다. 간단한 policy-based RL인 REINFORCE는 $\theta$를 $\nabla_\theta \log \pi(a_t|s_t;\theta) R_t$으로 업데이트를 한다. 이는 $\nabla_\theta \mathbb {E}[R_t]$의 추정값이다.
여기서 이제 variance를 줄이기 위해 baseline인 $b_t(s_t)$를 빼주면 결과 gradient는 $$\nabla_\theta \log \pi(a_t|s_t;\theta)(R_t-b_t(s_t))$$ 이 된다. 이 baseline을 value function으로 사용하면 $$b_t(s_t) \approx V^\pi(s_t)$$가 된다. 이 $R_t-b_t(s_t)$를 advantage의 estimation라고 볼 수 있는데 이는 $$A(a_t, s_t) = Q(a_t, s_t) - V(s_t)$$이다. $R_t$가 $Q(a_t, s_t)$의 estimate이고 $b_t$가 $V(s_t)$의 estimate인데 이 방법론을 actor-critic architecture로 볼 수 있다 ($\pi$가 actor, $b_t$가 critic).
Asynchronous RL Framework
이제 multi-thread로 학습하는 asynchronous RL에 대해 이야기를 해보겠다. 이 논문에서는 one-step Sarsa, one-step Q-learning, n-step Q-learning, 그리고 A2C(Advantage actor-crtic)의 asynchronous version에 대해서 다룬다. 두 가지 방법을 사용하여 이 알고리즘들을 asynchronous 하게 바꾼다.
1. Asynchronous actor-learner 사용
각각의 서버에 agent를 할당하고 파라미터 서버를 두지 않고, 하나의 서버에서 여러 개의 cpu 코어를 사용한다. 이를 사용하면 gradient를 보낼 때 서버 간에 필연적으로 발생할 수밖에 없는 communication delay를 획기적으로 감소시킨다.
2. 여러 개의 actor이 병렬적으로 돌면 각각 환경의 다른 부분을 explore 한다
즉, replay memory처럼 state 간의 correlation을 해결할 수 있는 메커니즘을 도입을 하지 않아도 된다. 각각 online으로 여러 가지의 경험이 한 번에 학습되기 때문에 diversity의 증가와 데이터 간의 correlation의 저하가 이루어진다. 또한 agent마다 다른 exploration scheme을 사용시켜 학습의 폭을 넓힐 수 있다. 즉, 학습을 상당히 안정적으로 진행할 수 있다.
다른 장점은 agent의 수에 따라 비례하여 학습시간이 줄어든다. 또한, replay memory를 사용하지 않기 때문에 on-policy RL을 사용할 수 있다 (Sarsa, actor-critic). 저장할 필요가 없기 때문에 메모리가 줄어드는 것은 덤이다.
이제는 각각에 알고리즘에 어떻게 asynchronous를 적용했는지 보겠다.
Asynchronous one-step Q-learning
thread 하나당 각각의 environment과 interact 한다. 각 step마다 gradient를 계산하나 target network에는 gradient들이 accumulate 되어서 update 된다(supervised learning에서 minibatch 방식과 비슷). 또한 각각의 thread마다 다른 exploration strategy를 주면 더 robust 하다. 여기서는 $\epsilon$-greedy에서 $\epsilon$을 어떤 distribution에서 sampling 하는 방식으로 차이를 주었다.
Asynchronous one-step Sarsa
이 방식은 위에 있는 one-step Q-learning과 비슷하나 차이점은 target value를 $$Q(s, a)=r+\gamma Q(s', a';\theta^-)$$를 사용한다($\max_a$를 사용하는 Q-learning과 다름).
Asynchronous n-step Q-learning
Forward view를 사용하여 eligibility traces 방식과 다르게 explicit 하게 n-step return을 계산한다. 이 방식이 momentum 기반의 학습 방식과 backprogration through time 방식에 적합하다고 한다. action을 $t_max$ step 또는 terminal state가 나올 때까지 고르고 n-step update를 진행한다. n-step update를 할 때는 제일 긴 step update를 사용하는데, 즉, 마지막 state는 one-step update를 진행하고, 두 번째 마지막 state는 two-step update... 이 방식으로 n-step까지 계산한 후 모아서 한 번에 gradient update를 진행한다.
Asynchronous advantage actor-critic (A3C)
A3C는 policy $\pi(a_t|s_t;\theta)$와 value function의 estimation인 $V(s_t;\theta_v)$를 사용하여 학습한다. n-step Q-learning과 비슷하게 forward view를 사용한다. $\theta$와 $\theta_v$의 parameter은 어느 정도 공유되는데, CNN의 output을 softmax를 통햇 policy $\pi$에 넣어주고 linear output을 value function $V$에 넣어준다. 또한, 정책 $pi$에 entropy를 도입하면 초반에 optimal 하지 않은 정책으로의 수렴을 막아준다.
Experiments
이 논문에서는 Arcade Learning Environment, TORSC 3D car racing simulator, Mujoco, Labyrinth를 사용하여 실험을 진행했다(마지막 두 개는 A3C에서만 사용).
Atari 2600
K40 CPU를 사용한 DQN보다 16개의 CPU 코어를 사용해서 Asynchronous 하게 학습한 알고리즘은 더 빨랐다. 또한, A3C 같은 경우에는 위에 나온 3가지의 value-based 방식보다 더 좋은 성능을 내었다. 실험에 사용한 hyperparameter은 6개의 game에서 search를 통해 찾은 후에 다른 57개의 게임에 같은 것을 적용하였다. 또한, feed-forward 방식과 LSTM을 사용한 recurrent agent 방식도 실험하였다. A3C 같은 경우에는 SOTA를 뛰어넘는 성능을 가지면서 학습 시간은 반으로 줄이는 모습을 보여줬다.
TORCS Car Racing Simulator
TORCS의 장점은 Atari보다 더 나은 그래픽을 가지고 있어서 조금 더 realistic 한 테스팅이 가능하다. 이 게임에서 reward는 트랙 중간에서의 속도와 비례한다. 위의 그래프를 보면 알겠지만 A3C가 제일 좋은 성능을 내었고 대충 인간 실험자의 75%~90%의 성능을 내었다.
Continuous Action Control Using the MuJoCo Physics Simulator
Continuous 한 환경인 MuJoCo에서는 policy 기반인 A3C가 적합해서 실험을 하였는데, visual input이나 physical state를 input으로 주었을 때 24시간 안에 좋은 설루션을 찾아내었다.
Labyrinth
이 미로 환경에서는 계속 랜덤 하게 생성되는 미로에서 길을 찾는 게 목표이다. 각 episode마다 랜덤 한 미로가 생성되기에 general 한 전략이 필요하다. 도착점에 들어가면 10점을 주고 episode당 60초가 소모되는데, 50 정도의 점수를 agent가 달성하였기 때문에 3D maze를 visual input만으로 풀 수 있다는 것을 알 수 있다.
CPU의 스레드 수가 늘어날수록 학습 속도가 비례해서 빨라지는 것을 알 수 있는데, 특이하게 Q-learning과 SARSA는 super-linear 한 상승을 보여준다. 이는 아마 multi-thead덕분에 bias가 줄어서 그런 것이다. Asychronous 하게 적용한 알고리즘들은 lr이나 랜덤 한 시작에 강한 모습을 보여준다.
Conclusions and Discussion
Asynchronous 하게 학습하는 것은 다양한 종류의 도메인에서 좋은 성능을 보여준다. 이 방식은 value-based, policy-based, off-policy, on-policy처럼 다양한 곳에 적용될 수 있다. A3C는 절반의 시간으로 SOTA를 달성하였고 이는 CPU만으로만 학습한 결과이다. Paralle actor을 사용하면 one-step 방법인 다양한 value-based 알고리즘들에 stabilizing 하는 효과를 가져다준다.
Experience replay를 적용해서 예전의 데이터를 다시 학습할 수 있겠으나, 이런 활용은 학습하는 것보다 환경에서 action을 취하는 시간이 더 긴 TORCS 같은 곳에 적용을 할 수 있겠다. 또한 알고리즘의 변형인 Dueling DQN 같은 것도 이 아키텍처를 적용해 볼 수 있다. 이 논문은 GPU로만 학습했던 기존의 알고리즘을 병렬처리라는 개념을 사용하여 성공적으로 학습속도를 올렸다.