Asynchronous Methods for Deep Reinforcement Learning Review

0. Introduction

Paper link

PDF link

한 줄 요약: 이 논문은 여러 actor-learner가 서로 다른 environment instance를 비동기적으로 탐색하고 하나의 shared network를 갱신하게 함으로써 replay memory 없이도 data correlation을 줄이며, 그중 A3C가 Atari, continuous control, 3D navigation에서 빠르고 안정적인 deep reinforcement learning을 가능하게 함을 보여준다.

이 논문을 지금 볼 가치가 있는 이유는 다음과 같음.

• A3C는 2016년 논문이지만, rollout worker와 learner를 분리하고 asynchronous experience를 소비하는 현대 RL system의 기본 설계 언어를 정립했다.
• Experience replay가 거의 필수처럼 여겨지던 시점에 parallel actor 자체가 decorrelation mechanism이 될 수 있음을 보여줬다.
• Policy gradient, value function, n-step return, entropy regularization을 하나의 간결한 actor-critic recipe로 묶었다.
• 최근 agentic RL에서는 environment interaction이 training보다 느리거나 불균일한 경우가 많아, actor-learner decoupling과 stale policy 문제가 다시 중요해지고 있다.
• 논문이 보고한 성능뿐 아니라 shared optimizer, lock-free update, wall-clock scaling을 함께 보면 algorithm과 system을 분리하지 않는 RL 연구의 출발점을 이해할 수 있다.

A3C는 종종 하나의 policy-gradient algorithm으로만 소개된다. 하지만 논문의 더 큰 기여는 deep RL의 data pipeline을 바꾼 데 있다. 하나의 agent가 trajectory를 모으고 replay buffer에서 minibatch를 뽑는 대신, 여러 actor가 서로 다른 state distribution을 동시에 만들고 global parameter에 update를 보낸다. 이 구조에서 parallelism은 단순한 속도 최적화가 아니라 learning stability를 만드는 일부다.

1. Problem Setting

1-1. Problem definition

Deep reinforcement learning은 supervised learning과 다른 두 가지 data 문제를 가진다.

1. Temporal correlation
   • 한 trajectory에서 연속된 state는 강하게 상관되어 있다.
   • 인접 transition으로 반복 update하면 gradient sample이 i.i.d.라는 일반적인 optimizer 가정에서 멀어진다.
   • Policy가 한 지역에 머무르면 training data도 좁은 state distribution에 갇힌다.
2. Non-stationary target
   • Agent가 학습되면서 policy와 value estimate가 계속 바뀐다.
   • Q-learning에서는 bootstrap target도 같은 network에 의존하므로 target distribution이 고정되어 있지 않다.
   • 최근 data가 빠르게 policy bias를 반영하면 update가 불안정해질 수 있다.

DQN은 이 문제를 experience replay와 target network로 완화했다. Replay buffer는 과거 transition을 섞어 temporal correlation을 줄이고, 같은 data를 여러 번 재사용한다. 하지만 replay에는 비용이 있다.

• 많은 transition을 memory에 저장해야 한다.
• On-policy method에는 그대로 적용하기 어렵다.
• Replay data는 current policy와 다른 behavior policy에서 왔기 때문에 off-policy correction이 필요할 수 있다.
• Buffer sampling과 learner update가 중심이 되는 architecture는 environment interaction parallelism과 별개로 설계된다.

이 논문은 다른 질문을 던진다.

하나의 replay buffer로 trajectory를 섞지 않고, 여러 environment에서 동시에 생성되는 서로 다른 trajectory 자체로 correlation을 줄일 수 있는가?

1-2. Why previous approaches are insufficient

논문이 나오기 전에도 distributed RL은 존재했다. 하지만 당시 대표적인 접근은 parameter server, 다수 machine, replay memory, 별도 learner를 결합하는 경우가 많았다. Gorila DQN처럼 큰 distributed system은 높은 throughput을 얻을 수 있지만, algorithm과 infrastructure가 함께 복잡해졌다.

저자들이 원하는 조건은 더 단순하다.

• 하나의 multi-core CPU machine에서 동작한다.
• Replay memory를 사용하지 않는다.
• 여러 actor가 global parameters를 공유한다.
• 각 actor가 독립적인 exploration policy를 가진다.
• Update는 lock-free하게 비동기적으로 적용한다.
• Value-based와 policy-based method 모두에 같은 framework를 적용한다.

핵심은 actor별 data distribution의 차이다. 각 actor는 다른 environment seed와 exploration randomness를 가진다. Q-learning thread라면 서로 다른 epsilon 값을 사용할 수 있고, actor-critic thread라면 stochastic policy 자체가 탐색을 만든다. 따라서 같은 시간 구간에 수집된 transition이라도 서로 다른 state-action region에서 온다.

이 구조는 replay가 제공하던 decorrelation을 완전히 동일하게 대체하지는 않는다. Replay는 오래된 data를 재사용해 sample efficiency를 높이지만, asynchronous actor는 fresh data diversity와 wall-clock throughput을 높인다. A3C의 장점은 replay의 모든 장점을 가져오는 것이 아니라, memory-heavy replay 없이도 안정적인 online update가 가능하다는 점이다.

2. Core Idea

2-1. Main contribution

논문의 contribution은 크게 세 층으로 나뉜다.

1. Asynchronous training framework
   • 여러 actor-learner thread가 각자 environment copy를 가진다.
   • Global network parameter는 모든 thread가 공유한다.
   • Thread는 local copy에서 gradient를 계산하고 global parameter에 비동기적으로 적용한다.
   • Explicit lock 없이 Hogwild-style update를 사용한다.
2. Four asynchronous RL variants
   • Asynchronous one-step Q-learning
   • Asynchronous one-step Sarsa
   • Asynchronous n-step Q-learning
   • Asynchronous advantage actor-critic, A3C
3. Broad empirical validation
   • Atari 2600에서 value-based와 actor-critic variants를 비교한다.
   • MuJoCo continuous control에서 recurrent actor-critic을 검증한다.
   • 3D visual navigation task에서 partial observability와 memory를 다룬다.
   • CPU thread 수에 따른 wall-clock speedup과 optimization stability를 분석한다.

이 중 A3C가 가장 널리 남았다. A3C는 policy와 value function을 하나의 network에서 동시에 학습하고, 짧은 n-step trajectory를 사용해 bias와 variance를 절충한다.

2-2. Design intuition

A3C의 설계 직관은 세 가지다.

첫째, parallel actor는 exploration과 decorrelation을 동시에 만든다. 한 actor가 특정 state region에서 반복 행동해도 다른 actor는 다른 trajectory를 생성한다. Global learner가 보는 gradient stream은 단일 trajectory보다 다양하다.

둘째, n-step return은 one-step temporal-difference와 full Monte Carlo return 사이의 중간점이다. State $s_t$에서 최대 $k$ step을 rollout한 return은 다음과 같다.

\[R_t = \sum_{i=0}^{k-1}\gamma^i r_{t+i} + \gamma^k V(s_{t+k};\theta_v)\]

Episode가 그 전에 끝나면 bootstrap term은 사라진다. 이 return으로 advantage를 만들면 다음과 같다.

\[A(s_t,a_t) = R_t - V(s_t;\theta_v)\]

또는 식을 펼치면 다음과 같다.

\[A(s_t,a_t) = \sum_{i=0}^{k-1}\gamma^i r_{t+i} + \gamma^k V(s_{t+k};\theta_v) - V(s_t;\theta_v)\]

One-step update보다 delayed reward를 빠르게 전달하고, full-episode Monte Carlo보다 variance를 줄인다.

셋째, entropy regularization은 early policy collapse를 막는다. Policy objective의 한 step contribution은 다음처럼 쓸 수 있다.

\[\nabla_\theta \log \pi(a_t|s_t;\theta) \left(R_t-V(s_t;\theta_v)\right) + \beta \nabla_\theta H(\pi(s_t;\theta))\]

첫 항은 positive advantage action의 probability를 높이고 negative advantage action의 probability를 낮춘다. 두 번째 entropy 항은 policy distribution이 너무 빨리 sharp해지는 것을 막아 exploration을 유지한다.

3. Architecture / Method

3-1. Overview

Item	Description
Goal	Replay memory 없이 asynchronous actor로 deep RL을 안정적으로 학습
Runtime	One machine, multiple CPU actor-learner threads
Shared state	Global model parameters and optimizer statistics
Local state	Environment copy, local parameter copy, trajectory buffer
Data decorrelation	Independent environments and exploration policies
Main algorithm	Asynchronous Advantage Actor-Critic, A3C
Return	Forward-view n-step return with bootstrap
Exploration	Stochastic policy plus entropy regularization
Update style	Lock-free asynchronous gradient application

3-2. Module breakdown

1) Global network and local worker

각 thread는 같은 model architecture를 사용하지만 두 parameter view를 가진다.

• Global parameters: 모든 thread가 update하는 shared parameters
• Thread-specific parameters: rollout과 gradient 계산에 사용하는 local copy

Worker는 update cycle을 시작할 때 global parameters를 local network로 복사한다. 그다음 자신의 environment에서 최대 $t_{max}$ step을 실행하거나 terminal state에 도달할 때까지 trajectory를 모은다. Rollout이 끝나면 backward direction으로 return과 gradient를 계산하고 global parameters에 적용한다.

이 구조에서 local network는 gradient 계산 중 다른 thread의 update로부터 직접 흔들리지 않는다. 반면 global network는 여러 worker의 update를 순차 lock 없이 받는다. 따라서 gradient가 계산된 parameter와 실제 적용 시점의 parameter가 정확히 같지는 않을 수 있다.

오늘날 용어로 보면 이것은 policy staleness의 초기 형태다. 논문은 작은 multi-core setting에서 이 비동기성이 오히려 exploration diversity와 wall-clock efficiency를 높인다고 본다.

2) Asynchronous one-step Q-learning

각 Q-learning worker는 자신의 epsilon-greedy policy로 action을 선택한다. Thread마다 epsilon을 다르게 두어 exploration diversity를 만든다. One-step target은 다음과 같다.

\[y_t = r_t + \gamma \max_a Q(s_{t+1},a;\theta^-)\]

원 논문의 asynchronous setting에서는 replay 없이 online transition을 사용한다. Target network 사용 여부와 synchronization 방식은 variant에 따라 다르지만, 핵심은 여러 thread가 서로 다른 exploration stream에서 Q update를 만든다는 점이다.

3) Asynchronous one-step Sarsa

Sarsa는 next action $a_{t+1}$을 실제 behavior policy에서 선택하고 다음 target을 사용한다.

\[y_t = r_t + \gamma Q(s_{t+1},a_{t+1};\theta)\]

Q-learning이 greedy target을 쓰는 off-policy method라면 Sarsa는 current behavior를 반영하는 on-policy update다. 두 method를 같은 asynchronous framework에서 비교함으로써 성능 개선이 특정 objective보다 parallel data generation에서 오는지 볼 수 있다.

4) Asynchronous n-step Q-learning

N-step Q-learning worker는 짧은 trajectory를 모은 뒤 accumulated reward와 bootstrap value로 update한다.

\[R_t = \sum_{i=0}^{k-1}\gamma^i r_{t+i} + \gamma^k \max_a Q(s_{t+k},a;\theta)\]

Delayed reward가 여러 preceding state로 한 번에 전파되므로 one-step method보다 빠른 credit assignment이 가능하다. 논문 실험에서도 n-step method는 one-step variants보다 강한 결과를 보이는 경우가 많다.

5) A3C network

A3C network는 shared representation 위에 두 output head를 둔다.

• Policy head: action probability distribution $\pi(a

  s;\theta)$

• Value head: scalar state value $V(s;\theta_v)$

Atari feed-forward variant는 convolutional encoder 뒤에 policy와 value head를 둔다. Recurrent variant는 encoder 뒤에 256-cell LSTM을 추가해 partial observability와 temporal memory를 처리한다.

Policy loss는 advantage-weighted log probability와 entropy bonus로 구성된다. Value loss는 n-step return에 대한 squared error다.

\[L_V = \frac{1}{2} \left(R_t-V(s_t;\theta_v)\right)^2\]

Combined loss는 구현 관점에서 다음처럼 볼 수 있다.

\[L = - \log \pi(a_t|s_t;\theta)A_t + c_v L_V - \beta H(\pi(s_t;\theta))\]

원 논문의 algorithm description은 policy와 value gradient를 별도로 적지만, 현대 implementation에서는 shared backbone에 대한 combined loss 형태로 자주 구현한다.

6) Shared RMSProp

논문은 RMSProp의 running statistics를 thread별로 따로 유지하는 방식과 global하게 공유하는 방식을 비교한다. Shared statistics variant가 더 robust한 결과를 보였고, 이후 A3C recipe의 대표 설정으로 남았다.

RMSProp의 running squared-gradient estimate를 단순화하면 다음과 같다.

\[g_t = \alpha g_{t-1} + (1-\alpha) \Delta\theta_t^2\] \[\theta \leftarrow \theta - \eta \frac{\Delta\theta_t} {\sqrt{g_t+\epsilon}}\]

여러 thread가 $g_t$를 공유하면 step scale에 대한 global statistics가 형성된다. 다만 이 state 역시 lock-free하게 update되므로 엄밀한 deterministic optimizer는 아니다.

4. Training / Data / Recipe

4-1. Data

이 논문은 고정 dataset을 학습하는 방식이 아니다. 각 environment interaction이 online training data를 만든다.

Atari

• Arcade Learning Environment의 57개 Atari game을 사용한다.
• Raw pixel observation에서 policy와 value를 학습한다.
• Feed-forward와 LSTM A3C를 모두 평가한다.
• Human-normalized score의 mean과 median을 보고한다.

Continuous control

• MuJoCo physics simulator의 continuous action task를 사용한다.
• Policy는 Gaussian distribution의 mean과 variance를 출력한다.
• Recurrent network가 observation history를 처리한다.

3D navigation

• Randomly generated 3D maze에서 visual navigation을 수행한다.
• Agent는 first-person RGB observation만 받고 reward location을 찾아야 한다.
• LSTM이 partial observability를 보완한다.

4-2. Training strategy

대표적인 training loop는 다음과 같다.

1. Global parameter를 local worker로 복사한다.
2. Worker가 자신의 environment에서 action을 sampling한다.
3. 최대 $t_{max}$ step 또는 terminal까지 state, action, reward를 저장한다.
4. 마지막 state가 terminal이 아니면 value estimate로 bootstrap한다.
5. Trajectory를 역순으로 순회하며 n-step return을 계산한다.
6. Policy gradient, value gradient, entropy gradient를 누적한다.
7. Gradient를 global parameter에 비동기적으로 적용한다.
8. 다음 update cycle을 시작한다.

Atari 실험은 16개 CPU core를 사용하는 설정을 중심으로 보고된다. Exploration parameter와 learning rate는 전체 training progress에 따라 annealing된다. Feed-forward와 LSTM model 모두 같은 asynchronous framework를 사용한다.

4-3. Engineering notes

1) Parallelism은 batch size가 아니다

A3C의 16 worker는 하나의 synchronized minibatch를 만드는 data-parallel training과 다르다. Worker마다 rollout length와 terminal timing이 다르고, gradient가 준비되는 즉시 global model에 적용된다.

2) Reproducibility는 어렵다

Thread scheduling, environment timing, unsynchronized update 순서에 따라 exact trajectory와 parameter sequence가 달라진다. Seed를 고정해도 bitwise reproducibility를 기대하기 어렵다.

3) Staleness는 무시할 수 없는 system variable이다

Worker가 local parameter를 복사한 뒤 rollout과 backward를 수행하는 동안 global model은 다른 worker에 의해 바뀔 수 있다. 작은 CPU setting에서는 허용되지만, rollout이 길거나 distributed latency가 큰 system에서는 behavior policy와 learner policy의 gap이 커진다.

4) Optimizer state sharing이 중요하다

Parameter만 공유하고 adaptive optimizer statistics를 worker별로 분리하면 thread마다 effective learning rate가 달라진다. 논문은 shared RMSProp statistics가 hyperparameter robustness에 기여한다고 본다.

5) Environment throughput이 실제 bottleneck일 수 있다

A3C는 GPU utilization을 높이는 논문이 아니라, CPU environment와 network inference를 병렬화해 wall-clock을 줄이는 논문이다. Modern agentic RL에서는 browser, code sandbox, simulator, external API가 느리기 때문에 같은 원리가 다시 중요하다.

5. Evaluation

5-1. Main results

1) Atari 57 games

논문 Table 1의 human-normalized score는 다음과 같다.

Method	Training time / resource	Mean	Median
DQN	8 days, GPU	121.9	47.5
Gorila	4 days, 100 machines	215.2	71.3
Dueling DDQN	8 days, GPU	343.8	117.1
Prioritized DQN	8 days, GPU	463.6	127.6
A3C FF	1 day, CPU	344.1	68.2
A3C FF	4 days, CPU	496.8	116.6
A3C LSTM	4 days, CPU	623.0	112.6

A3C LSTM은 mean score가 가장 높지만 median은 Prioritized DQN과 Dueling DDQN보다 낮다. 이는 일부 game에서 매우 큰 improvement가 mean을 끌어올렸을 가능성을 의미한다. 따라서 A3C가 모든 game에서 일관되게 우월하다고 읽으면 안 된다.

또한 resource comparison은 완전히 동일하지 않다. GPU method의 hardware, implementation maturity, frame preprocessing, evaluation protocol이 다르다. 논문이 보여주는 핵심은 16-core CPU 한 대에서도 당시 강한 Atari 성능에 도달했다는 점이다.

2) Wall-clock scaling

Worker thread 수를 늘리면 모든 asynchronous method의 training speed가 개선된다. 16 thread는 one-thread baseline 대비 적어도 order-of-magnitude 수준의 wall-clock speedup을 보인다.

일부 one-step method에서는 단순한 compute scaling보다 큰 improvement가 나타난다. 이는 더 많은 thread가 같은 시간에 더 다양한 experience를 만들기 때문에 optimization 자체가 쉬워지는 data-diversity effect로 해석된다.

3) Continuous control

A3C는 continuous action space에서도 별도 replay buffer 없이 안정적으로 학습된다. MuJoCo task에서 좋은 solution을 24시간 이내에 얻었고, 많은 task는 몇 시간 안에 의미 있는 policy에 도달한다.

이 결과는 A3C가 Atari-specific trick이 아니라는 점을 보여준다. Discrete action에서는 softmax policy, continuous action에서는 Gaussian policy를 쓰되 asynchronous actor-critic 구조는 유지된다.

4) 3D navigation

LSTM A3C는 first-person visual input만으로 3D maze를 탐색한다. Reward location과 maze structure가 바뀌는 partial-observable setting에서 recurrent state가 history를 요약한다.

이 실험의 의미는 raw pixel control을 넘어 memory-dependent navigation에도 같은 framework가 적용된다는 점이다. 다만 오늘날의 large-scale embodied benchmark와 직접 비교할 정도의 환경 복잡도는 아니다.

5-2. What really matters in the experiments

이 논문에서 중요한 것은 최고 score 하나보다 다음 네 가지다.

1. Replay-free stability
   • Multiple actor stream만으로 deep network를 안정적으로 학습할 수 있었다.
2. Wall-clock efficiency
   • CPU parallelism이 algorithmic exploration과 system throughput을 동시에 개선했다.
3. Cross-domain portability
   • Discrete game, continuous control, partial-observable navigation에 같은 abstraction을 적용했다.
4. Robustness of shared optimizer
   • Asynchronous system에서는 model architecture뿐 아니라 optimizer state topology가 성능을 바꾼다.

A3C의 가장 오래 남은 contribution은 score가 아니라 topology다. Environment actor와 learner를 분리하고, 여러 policy version이 만든 data를 하나의 training stream으로 합치는 문제는 오늘날 online RL, simulator training, web agent RL에서도 그대로 반복된다.

6. Limitations

1. Sample efficiency가 주요 목표는 아니다.
   • Replay memory를 쓰지 않으므로 transition 재사용은 제한적이다.
   • Wall-clock은 빠를 수 있지만 동일 environment step 수에서 replay-based method보다 효율적이라는 보장은 없다.
2. Update staleness를 명시적으로 correction하지 않는다.
   • Worker가 사용한 policy와 global update 시점의 policy가 다를 수 있다.
   • Large distributed system에서는 importance sampling이나 policy-version filtering이 필요할 수 있다.
3. Lock-free update는 nondeterminism과 race condition을 만든다.
   • 작은 dense network에서는 잘 동작하지만, optimizer state와 sparse update가 복잡해지면 debugging이 어려워진다.
4. Atari comparison은 현대 benchmark standard와 다르다.
   • Evaluation protocol과 hardware가 현재 관행과 다르며, 2016년 score를 최신 agent 성능과 직접 비교할 수 없다.
5. Shared RMSProp의 이론적 설명은 제한적이다.
   • Empirical robustness는 보이지만, nonlinear network의 asynchronous convergence를 완전히 설명하지는 않는다.
6. Multi-core CPU 중심 architecture다.
   • Modern accelerator cluster에서는 inference batching, network communication, parameter sharding, weight synchronization이 새로운 bottleneck이 된다.
7. Agentic long-horizon setting의 delayed and sparse reward는 더 어렵다.
   • A3C의 짧은 n-step return만으로 긴 tool-use trajectory의 credit assignment를 해결할 수는 없다.

7. My Take

7-1. Why this matters for my work

최근 agentic RL framework를 보면 rollout engine, environment worker, trainer, reward service, weight sync가 각각 별도 component로 나뉜다. 이 구조의 조상 격이 A3C다. 차이는 modern system이 CPU thread가 아니라 GPU cluster와 remote environment를 사용한다는 점이다.

A3C를 다시 읽으면 다음 질문이 선명해진다.

• Parallel actor는 단순히 sample을 더 많이 만드는가, 아니면 exploration distribution을 바꾸는가?
• Learner가 소비하는 data는 어느 policy version에서 왔는가?
• Rollout latency가 긴 worker의 gradient를 그대로 받아도 되는가?
• Shared optimizer state와 global normalization은 어디에 있어야 하는가?
• Wall-clock throughput과 sample efficiency를 어떻게 분리해 보고할 것인가?

A3C는 이 질문들에 완전한 답을 주지는 않는다. 대신 asynchronous RL system을 algorithm의 외부 구현 detail이 아니라 learning behavior의 일부로 보게 만든다.

7-2. Reuse potential

1) Independent actor environments

• 서로 다른 seed, task subset, tool configuration을 actor에 배정한다.
• 단순 duplicate rollout보다 state distribution diversity를 높인다.

2) Short trajectory update

• Full episode 종료를 기다리지 않고 bounded rollout chunk로 update한다.
• 긴 agent trajectory에서는 chunk boundary와 bootstrap estimator를 명확히 설계한다.

3) Entropy-aware exploration

• Reward가 sparse한 초기 stage에서 policy entropy를 모니터링한다.
• Entropy coefficient를 고정값으로 두기보다 task progress와 함께 조정할 수 있다.

4) Staleness dashboard

• Rollout policy version, learner policy version, queue delay를 기록한다.
• Old trajectory의 비율과 importance ratio distribution을 함께 본다.

5) Wall-clock and sample metrics separation

• Environment steps, generated tokens, learner updates, elapsed time을 따로 보고한다.
• Faster system이 더 많은 data를 소비해서 좋아진 것인지, 같은 data에서 더 효율적인지 구분한다.

7-3. Follow-up papers

• IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architectures
• Ape-X: Distributed Prioritized Experience Replay
• ACER: Sample Efficient Actor-Critic with Experience Replay
• Distributed Prioritized Experience Replay
• Proximal Policy Optimization Algorithms
• SEED RL: Scalable and Efficient Deep-RL with Accelerated Central Inference

8. Summary

• A3C는 여러 actor-learner가 independent environment를 탐색하고 shared network를 비동기적으로 갱신하는 replay-free deep RL framework다.
• Parallel actor는 throughput뿐 아니라 temporal correlation을 줄이고 exploration diversity를 높이는 algorithmic 역할을 한다.
• A3C는 n-step return, advantage actor-critic, entropy regularization, shared value-policy representation을 간결하게 결합한다.
• Atari, continuous control, 3D navigation에서 당시 강한 결과와 큰 wall-clock speedup을 보였지만 sample efficiency와 stale-policy correction은 핵심 한계로 남는다.
• 현대 agentic RL에서 rollout worker, learner, asynchronous queue, policy version을 설계할 때 여전히 유효한 출발점이다.