Asynchronous Methods for Deep Reinforcement Learning

Run many copies of an agent at once, and deep reinforcement learning trains on a CPU.

Sixteen agents explore in parallel, so their experience is varied instead of one correlated stream. That variety stabilizes training and replaces the replay memory earlier deep RL needed, and it works for the on-policy methods a replay memory cannot support.

Before this paper, deep reinforcement learning meant a GPU and a large memory of replayed experience. A3C used neither, beat the state of the art on Atari, and did it in half the wall-clock time on a sixteen-core CPU.

For a while it was taken as fact that you could not train a deep network with plain online reinforcement learning. Feed a neural network the states an agent visits, one after another, and update on each one, and the training tended to diverge. The fix that made deep RL work, the one inside DQN, was a memory of past experience called a replay buffer: store every transition the agent sees, then train on random batches pulled back out of it. That one component is most of why DQN learned to play Atari from pixels, and it came with a price. The buffer needs memory and extra computation, it restricts you to a particular family of learning rules, and the setup ran on a GPU.

A3C, short for asynchronous advantage actor-critic, throws the buffer out and replaces it with something cheaper: many copies of the agent, running at the same time. The claim of the paper is that this one substitution recovers everything the buffer was doing, opens the door to learning rules the buffer had ruled out, and runs on an ordinary multi-core CPU. A handful of ideas carry it: why a single agent's data breaks learning and how parallel actors fix it, how those actors share one model without locking, why longer returns propagate reward faster, how an actor-critic turns returns into a low-variance policy update, and a small entropy bonus that keeps the agent exploring.

Why online deep RL kept breaking

Start with the failure the paper is reacting to. An agent walks through its environment and sees a stream of states: frame after frame of the same game, each almost identical to the one before. If you train a network on that stream in order, two things go wrong at once, and it helps to name both.

The first is correlation. Consecutive samples are nearly the same, so a run of gradient steps all point the same way and drag the network toward whatever is on screen right now, undoing what it learned about earlier situations. Stochastic gradient descent assumes its samples are roughly independent; a tightly correlated stream violates that and the updates thrash. The second is non-stationarity: in RL the data the agent collects depends on its current policy, and the policy keeps changing as you train, so the distribution of states shifts under you.

The replay buffer answers both. Keep a large pool of past transitions and sample random minibatches from it, and any single batch mixes moments from all over the agent's history: the correlations between neighbors are broken, and averaging over a slice of history smooths out the shifting distribution. Reuse of old data is a bonus, but in DQN the buffer's job was decorrelation and smoothing.

It buys stability and charges for it. A buffer of a million frames is memory and bookkeeping on every step. And it forces a specific choice: because the transitions in the buffer were generated by older versions of the policy, only a learning rule that can update correctly from another policy's data may drink from it. That rules out an entire family, the on-policy methods, which assume their data came from the policy being updated right now. Q-learning survives replay because it is off-policy; actor-critic does not. So the very thing that stabilized deep RL also boxed it into off-policy, value-based algorithms and a GPU. To get the stability another way, and get the on-policy methods back, you need a different way to break the correlation.

Return, value, advantage

Three quantities recur below: the return, the value, and the advantage. At each step the agent is in a state $s$, picks an action $a$ from its policy $\pi(a\mid s)$ (its strategy, a distribution over actions), and receives a reward $r$ and the next state. What it is trying to maximize is the entire discounted stream of future reward from now on, the return:

The discount $\gamma$ (set to $0.99$ in the experiments) weights a reward $k$ steps away by $\gamma^k$, so a value near one makes the agent far-sighted. Two bookkeeping quantities score how good a situation is. The state value $V^\pi(s)$ is the expected return if you start in $s$ and follow $\pi$, a rating of the situation itself. The action value $Q^\pi(s,a)$ is the expected return if you start in $s$, take the specific action $a$, then follow $\pi$, a rating of one move. The best action value any policy can achieve is $Q^*(s,a) = \max_\pi Q^\pi(s,a)$, the max over all strategies, not the greedy pick of the current estimate.

The difference between the two is the advantage:

It answers the sharper question a learner actually cares about: is this action better or worse than what I would normally do from here? Subtracting the state's own value centers the answer on zero, so a good action reads as positive and a bad one as negative regardless of whether the state itself is lucky or dire. Because it is centered on zero, you scale a policy update by the advantage, not the raw return, and the value functions here anchor all four algorithms the paper builds, the value-based ones (which learn $Q$) and the actor-critic (which uses both $V$ and $Q$, combined in the advantage). We come back to the advantage when the actor-critic assembles its update.

Parallel actors instead of replay

The paper turns on a single substitution: instead of one agent feeding a buffer, run many actors at once, each in its own copy of the environment, each carrying its own exploration. At any single instant the parallel actors are scattered across different parts of the game: one is in an early room, another mid-level, another near a death. Pool their current transitions into a training batch and that batch is already varied, drawn from all over the state space rather than from one contiguous stretch of a single walk. The parallelism does the decorrelation the buffer used to do, and it does it on fresh data. Because the pooled batch spans many actors at many stages of the game, it also averages over the broad, slowly-shifting distribution the buffer used to smooth, so parallelism covers the non-stationarity too, not only the correlation.

The figure makes the effect concrete. With one actor, the batch is a short segment of a single trajectory, a tight clump of near-identical samples: the spread meter reads low, the correlated stream that broke online learning. Add actors and the amber batch scatters across the space. Drag it to one and hold it, then to sixteen, and watch the clump become a scatter.

Diversity between the actors sharpens the effect, so the paper gives each thread its own exploration schedule (for the value-based methods, an $\varepsilon$-greedy rate drawn per thread), which pushes them into different regions and makes their pooled updates even less correlated in time.

What the fresh data unlocks matters more than the decorrelation. Because the actors' data is fresh, generated by the policy as it stands now rather than dredged from a buffer of stale transitions, the on-policy methods come back into play. The cleanest way to see what "on-policy" means is Sarsa versus Q-learning, which differ in a single symbol. Both update an action value toward a bootstrapped target. Q-learning uses $r + \gamma \max_{a'} Q(s',a')$, the value of the best next action, so it can learn the optimal policy from anyone's data, even an old policy's. Sarsa uses $r + \gamma\, Q(s',a')$ with $a'$ the action the current policy actually took, so it evaluates the policy that generated the data. That is on-policy, and it only makes sense on fresh data. A replay buffer holds stale data, so it forces the off-policy choice; parallel fresh actors remove that constraint, and actor-critic, which is on-policy, becomes trainable at scale without a buffer.

One shared model, many threads

The actors are not separate agents learning separate models. They are threads on one machine sharing a single set of weights. Each thread runs the same short loop: copy the shared weights into a private working copy, act in its own environment for a few steps, accumulate a gradient from what happened, then apply that gradient back to the shared weights. No central server, no message passing, and no lock around the shared parameters. Threads read and write the same weights concurrently, in the lock-free style of Hogwild!, and the paper found the occasional clobbered write does no harm at this scale. (Hogwild!'s formal guarantee assumes sparse gradients, which deep-network gradients are not, so A3C borrows the lock-free style as a heuristic and rests on the empirical result, not the proof.)

Tap a thread in the figure to follow its four steps. Because the threads run out of phase, at any instant they sit in different steps of the loop, and no thread ever waits for another. The word asynchronous names exactly that.

This is a deliberate simplification of the paper's predecessor. Gorila (Nair et al., 2015) had already parallelized DQN, but across roughly 130 machines: a hundred actor-learners sending gradients to thirty parameter servers, and it still kept a replay buffer at each actor. A3C collapses that distributed system onto the cores of one CPU and drops the buffer. Keeping the threads on a single machine removes the cost of shipping gradients and parameters over a network, and it enables the lock-free shared-memory updates. Each thread also accumulates its gradient over several steps before applying it, like a minibatch, which cuts how often two threads overwrite each other and lets you trade a little computation for data efficiency.

Propagating reward faster

There is a slow leak in the simplest value-based update, and n-step returns plug it. In one-step Q-learning the loss regresses $Q(s,a)$ toward a target that folds in a single reward:

The reward $r$ only ever lands directly on the value of the one state-action pair that produced it. Every other state that led there feels it only later, once its own value has been updated toward that pair, and so on back down the chain. So a reward has to trickle backward one state per update, and learning a long-horizon payoff takes many passes. To fix it, look further ahead before you bootstrap. An $n$-step return uses the next $n$ real rewards and only then falls back on an estimate:

A single reward now lands directly on the values of the $n$ state-action pairs that preceded it, in one update instead of $n$. Drag $n$ in the figure and watch the reward's reach grow: at $n=1$ only the last state is touched, and it has to walk back one step at a time; crank $n$ up and a single update pulls a whole run of states toward the reward at once.

The reach is not free. After the $n$ real rewards you still fall back on a guess, the bootstrapped $\gamma^n \max_a Q$, so a longer return depends less on a possibly-wrong estimate but inherits more of the reward noise: larger $n$ trades bias for variance. A3C computes these returns in the forward view, rolling out up to $t_{\max}$ steps and reading the returns straight off the rollout, rather than the backward-view machinery of eligibility traces (a running, decaying tally of recently visited states) that classical $\text{TD}(\lambda)$ uses to spread credit. Within one $t_{\max}$-step rollout the states even get returns of different lengths, a one-step return for the last state up to a $t_{\max}$-step return for the first (a mix across states, not a per-state blend of horizons), so a single rollout already fans one batch of rewards back across a long run of states at once.

The actor and the critic

Value-based methods learn $Q$ and act greedily with respect to it. Policy-based methods skip the value table and adjust the policy directly, nudging $\pi(a\mid s;\theta)$ to raise expected return. The classic estimator, REINFORCE, is simple: sample a trajectory, and for each action push its log-probability up in proportion to the return that followed it,

which is an unbiased estimate of the gradient of expected return. It is also badly noisy, for a reason you can feel: in a good state every action is followed by a high return, so every action gets pushed up, and the useful signal, which action was better than which, is buried under the common offset. So subtract it. Pick any function of the state alone, a baseline $b(s)$, and scale the update by $R_t - b(s)$ instead. The subtraction is free in the sense that matters: it changes nothing in expectation, because

Follow the cancellation left to right. Because $b(s)$ does not depend on the action, it slides outside; the expectation weights each action's $\nabla_\theta \log \pi$ by its probability $\pi(a\mid s)$; and the identity $\pi\,\nabla\log\pi = \nabla\pi$ turns that probability-weighted sum of log-gradients into a plain sum of $\nabla_\theta \pi$, which is the gradient of $\sum_a \pi(a\mid s) = 1$, and the gradient of a constant is zero. Any state-only baseline leaves the gradient unbiased and only changes its variance. The natural choice is the state's own value, $b(s) \approx V^\pi(s)$. The return that follows the sampled action $a_t$ is a single sample of $Q^\pi(s_t,a_t)$, so the multiplier $R_t - V(s_t)$ estimates $Q - V$, the advantage from (2). (Why not subtract $Q$, which would center it perfectly? Because $Q$ depends on the action, and an action-dependent baseline breaks the cancellation in (5) and biases the update. The value $V$ is the most you can subtract without adding bias.) This structure has a name, the actor-critic: the policy $\pi$ is the actor, the value estimate $V$ is the critic that supplies the baseline, and the "A" in A3C is this advantage.

The figure runs the update on a one-dimensional action. Watch the sampled actions above the dashed baseline get an up arrow and those below it a down arrow, and the policy bell climb the return landscape as those nudges accumulate. That climb is $\nabla \log\pi \cdot A$ averaged over samples.

A3C does not use the full-episode return in that slot. It plugs in the $k$-step return from the last section, with the critic supplying both the bootstrap and the baseline, which gives the advantage the algorithm actually uses:

At $k=1$ this collapses to the one-step temporal-difference error $r_t + \gamma V(s_{t+1}) - V(s_t)$. Note where the bias lives: subtracting the baseline is exactly unbiased, so the imperfection is not there. It is the $\gamma^k V(s_{t+k})$ bootstrap, which leans on a value estimate that is not yet accurate, that makes the finite-$k$ advantage biased. Longer $k$ shrinks that bias and raises variance, the same knob as before. The actor and the critic then train in opposite senses on the same shared network: the actor ascends $\log\pi \cdot A$ to raise return, while the critic descends the squared error $(R_t - V)^2$ to sharpen its estimate, holding the return target fixed as it does so. A3C is on-policy, which is precisely why it needed the parallel actors: its gradient assumes the data came from the current policy, so it could never have learned from a replay buffer in the first place. This is the same maximum-return actor-critic that later off-policy methods like Soft Actor-Critic rebuild around an entropy objective, and the same policy-gradient family as TRPO and PPO.

A bonus for staying unsure

A policy-gradient learner can still lock onto the first action that looks good, drive its probability toward one, and stop trying anything else, before it has discovered a better action it now never samples. The paper heads this off with a small bonus for keeping the policy uncertain. Add the entropy of the policy, $H(\pi(\cdot\mid s))$, to the objective, so the full actor gradient is

The sign matters: the entropy term is added under gradient ascent, rewarding high entropy, so it pushes back against premature collapse to a near-deterministic policy. The weight $\beta$ (set to $0.01$ on Atari) sets how hard it pushes. This is not an A3C invention; it goes back to Williams and Peng (1991), and it applies only to the actor. The value-based variants have no policy to keep spread, so they explore the old-fashioned way, with $\varepsilon$-greedy actions.

Slide $\beta$ in the figure. Near zero, the policy piles onto the single best action and the others go dark: it commits before it has explored. Turn $\beta$ up and the distribution spreads back out and keeps sampling the runners-up. Too high and it flattens toward uniform and never commits at all. The useful setting is in between, spread enough to explore, peaked enough to still prefer the good actions.

Continuous actions get the same treatment with a twist. There the policy is a Gaussian over real-valued actions, and its spread is the standard deviation $\sigma$; the entropy of a Gaussian is

The paper writes the bonus as a cost $-\tfrac{1}{2}\big(\log(2\pi\sigma^2)+1\big)$ added to a minimized loss. The leading minus sign looks like it is punishing entropy, but it is the negation of the entropy above added to a loss that is being minimized, which is the same as rewarding entropy under ascent: it keeps $\sigma$ from collapsing to zero, so the continuous policy stays exploratory. (The $+1$ is $\log e$ in nats, and unlike the discrete case a Gaussian's differential entropy can go negative when $\sigma$ is small.)

A3C, one update at a time

The paper presents four algorithms that share the parallel-actor skeleton: asynchronous one-step Q-learning, one-step Sarsa, n-step Q-learning, and A3C. The three value-based ones differ from A3C in one component: they keep a target network. That is a second, slowly updated copy of the weights, $\theta^{-}$, used only to compute the bootstrap target, refreshed every 40000 frames. It exists to fix the non-stationarity of chasing a target that moves with every gradient step. A3C uses no target network. Its rollouts are short and on-policy, and each thread already syncs a private copy of the weights at the start of every rollout, so the moving-target problem never bites the same way and there is nothing to freeze. (A target network fixes that moving-target instability; it does nothing for the separate overestimation bias of the $\max$ operator, which is Double DQN's job.)

One A3C thread in full, the four steps from the architecture figure made literal:

# one actor-learner thread; shared theta, theta_v, counter T  (Algorithm S3)
repeat:
    d_theta, d_v = 0, 0
    theta', v'   = theta, theta_v         # sync a private copy of the weights
    t_start = t
    s = current_state
    while not terminal(s) and t - t_start < t_max:   # roll out up to t_max=5
        a = sample(pi(s; theta'))         # act on-policy in this thread's env
        s, r = env.step(a); store(s, a, r)
        t += 1; T += 1
    R = 0 if terminal(s) else V(s; v')    # bootstrap from the value head
    for i in reversed(range(t_start, t)): # walk the rollout backward
        R = r[i] + gamma * R              # the n-step return for state i
        adv = R - V(s[i]; v')             # the advantage A
        d_theta += grad log pi(a[i]|s[i]; theta') * adv + beta * grad H(pi)
        d_v     += grad (R - V(s[i]; v'))**2    # critic: squared TD error
    apply(theta, d_theta); apply(theta_v, d_v)  # push to SHARED weights, no lock
until T > T_max

Make it concrete with real numbers. The Atari network is the one from the original DQN: a convolutional layer of 16 filters ($8\times 8$, stride 4), then 32 filters ($4\times 4$, stride 2), then a fully connected layer of 256 units, all with rectifier nonlinearities. On top of that shared trunk sit two small heads: a softmax over the game's actions (the actor $\pi$) and a single linear unit (the critic $V$). A thread starts a rollout by copying the shared weights, then acts for up to $t_{\max}=5$ steps in its own game, collecting, say, rewards $0,0,1,0,0$. It bootstraps from its value head, $R \leftarrow V(s_5)$, then walks backward: $R \leftarrow r_i + 0.99\,R$ at each step gives the five states returns of length five down to one. For each state it adds $\nabla\log\pi(a_i\mid s_i)\cdot(R - V(s_i))$ to the policy gradient and $\nabla(R - V(s_i))^2$ to the value gradient, plus the entropy term. Then it applies both to the shared weights and starts again. Sixteen threads do this at once, out of phase, on one CPU.

The optimizer is shared too. The paper uses non-centered RMSProp with the running average of squared gradients $g$ held in shared memory across threads, which it found more robust than a per-thread copy or momentum SGD:

with decay $\alpha = 0.99$ and a learning rate drawn per run from $\text{LogUniform}(10^{-4}, 10^{-2})$ and annealed to zero. A recurrent variant adds 256 LSTM cells after the trunk. For continuous control the actor head instead emits a mean $\mu$ (a linear unit) and a variance $\sigma^2$ (through a SoftPlus), and actions are sampled from that Gaussian. Very little changes between all four: the same trunk, the same rollout-and-apply loop, the same shared optimizer. Only the target and the head differ.

What parallelism bought

The paper rests on two results: a speed result and the Atari scoreboard. Take speed first. The authors measured, for each method, how much faster it reaches a fixed reference score as you add actor-learner threads. The obvious expectation is a roughly linear win: $n$ threads, up to $n$ times faster. The one-step methods beat that. At 16 threads, one-step Q-learning reaches its score $24.1\times$ faster and one-step Sarsa $22.1\times$, both above the linear line. Drag the slider to 16 and read them off.

More threads is at most a linear compute win, so a speedup above the number of threads has to come from somewhere else, and it does: data efficiency. A one-step method relies heavily on its own bootstrap, and that bootstrap is biased when the updates are correlated. Decorrelating the updates with parallel actors reduces that bias, so each method needs fewer environment steps to reach the score, on top of running them faster. The effect is specific to the one-step methods, where the bias is worst. n-step Q-learning lands at $17.2\times$, only just above linear and not really superlinear, and A3C at $12.5\times$ is comfortably sublinear, because they had less bootstrap bias to shed. And "speedup" here is wall-clock time to a fixed score, not raw throughput.

The second result is the Atari scoreboard, and it rewards reading past the first number. On the mean human-normalized score over 57 games, A3C with an LSTM tops the table at $623\%$, ahead of the best DQN variant at $464\%$, and it got there in four days on 16 CPU cores against eight days on a K40 GPU, half the wall-clock time and no GPU. Switch the figure to the median and the story changes. There A3C sits mid-pack: its feedforward median of $116.6\%$ and LSTM median of $112.6\%$ roughly tie Dueling Double DQN at $117.1\%$ and trail Prioritized DQN at $127.6\%$.

The two numbers disagree for a reason that is easy to check. The mean is pulled up by a handful of games where A3C scores many times a human's, while the median, the typical game, has it level with the best value-based methods rather than beating them. The fair claim is that A3C matches the state of the art on the typical game and outruns it on the mean, on a CPU, in half the time. It also generalizes beyond Atari: the same algorithm learned continuous motor control in MuJoCo, reached most of a human tester's score on the TORCS driving simulator in about twelve hours, and learned to navigate randomly generated 3D mazes from raw pixels, none of which the value-based methods handle as readily.

There is a coda the paper could not have written, though its own follow-ups did. The title says asynchronous, and the asynchrony is not the load-bearing part. A synchronous version, which lets all the actors finish a step, averages their gradients, and applies one batched update, works as well or better; it became known as A2C. What actually did the work was the varied, decorrelated data from running many actors at once, not the lock-free timing. Read that way, the durable lesson of the paper is the one the first figure showed: parallel diverse experience is a replacement for a replay buffer, and once you have it, on-policy deep RL is stable, trains on a CPU, and needs no memory of the past.