A3C: Asynchronous Methods for Deep Reinforcement Learning

Many copies of an agent, playing at once on one CPU, give deep reinforcement learning stable training data without a replay memory.

DeepMind's 2016 paper runs 16 actor-learner threads that share one neural network. Their mixed, fresh experience stabilizes training the way DQN's replay buffer did, and because it comes from the current policy, on-policy methods such as actor-critic can train on it.

The best of its four algorithms, A3C, trained for four days on 16 CPU cores and no GPU. The DQN variants it was compared with trained for eight days on a GPU, and A3C beat all of them on the mean score over 57 Atari games.

In 2015 the best-known recipe for deep reinforcement learning from pixels was DQN: a convolutional network that maps game frames to action values, trained on random batches drawn from a replay buffer that stores the last million frames of play. Without the buffer, training on the agent's experience as it arrives tended to diverge, and the paper describes the belief of the time as "the combination of simple online RL algorithms with deep neural networks was fundamentally unstable."

This paper replaces the buffer with parallelism. Sixteen threads on one machine each play their own copy of the game and write gradient updates into one shared network. The authors apply that framework to four standard algorithms: one-step Q-learning, one-step Sarsa, n-step Q-learning, and advantage actor-critic. The last one, asynchronous advantage actor-critic or A3C, is the one that stuck. To follow it you need five ideas, in this order: why a single agent's stream of experience breaks training and how parallel actors fix it; how the threads share weights without locks; n-step returns, which move reward back through time faster; the actor-critic update and its baseline; and an entropy bonus that keeps the policy exploring. After those come the full update with real numbers and then the results.

Why online deep RL kept breaking

An agent playing a game produces a stream of transitions: state, action, reward, next state. Consecutive states are nearly identical, because one Atari frame differs from the next by a few pixels. Training a network on that stream in order causes two problems.

The first is correlation. Stochastic gradient descent assumes each minibatch is a fair sample of the data it should fit. A batch of 16 consecutive transitions all come from the same few seconds of play, so every gradient in the batch points the same way: toward fitting the current screen. A neural network's weights are shared across all inputs, so moving them to fit this screen also changes the outputs for screens the agent saw a minute ago. The network keeps refitting whatever part of the game it is in and losing what it learned elsewhere. The second is non-stationarity. The data depends on the policy, the policy changes with every update, and so the distribution of states the network trains on keeps shifting.

The figure below reproduces the correlation problem with a model small enough to watch. A cubic curve (four weights, every one of which affects the output at every $x$) is fit by SGD to a fixed target, using a batch of exactly 16 samples per update. The slider changes only where those 16 samples come from: one actor walking slowly along $x$ supplies its last 16 positions, two actors supply 8 each, and so on up to 16 actors that supply one each.

DQN's replay buffer fixes both problems by sampling. A random batch from a million stored frames mixes moments from all over the agent's recent history, so the batch is close to independent samples, and the mix averages over many past policies, which smooths the shifting distribution. In the figure, the replay button gives one actor the same low error that sixteen actors reach.

The paper lists what the buffer costs. It "uses more memory and computation per real interaction", and it "requires off-policy learning algorithms that can update from data generated by an older policy." A transition in the buffer may be hundreds of thousands of updates old, generated by a policy that no longer exists. Q-learning can learn from such data; the on-policy methods, which assume their data came from the policy being trained right now, cannot. Actor-critic is on-policy, so as long as stability came from a replay buffer, actor-critic could not use it.

Return, value, advantage

At each time step $t$ the agent sees a state $s_t$, picks an action $a_t$ from its policy $\pi(a\mid s)$ (a probability distribution over actions given the state), and receives a reward $r_t$ and the next state. It tries to maximize the return, the discounted sum of all future reward:

The paper indexes the reward for the action at step $t$ as $r_t$ and allows $\gamma = 1$; both are its conventions. Every experiment uses $\gamma = 0.99$. A reward 100 steps ahead is weighted by $0.99^{100} \approx 0.37$, so the agent effectively plans about 100 steps out. The Atari setup repeats each action for 4 frames, so 100 steps is 400 frames, under 7 seconds of play at 60 frames per second. As a small example, rewards of 0, 0, 1 starting at step $t$ and nothing after give $R_t = 0.99^2 \times 1 = 0.9801$.

Two functions rate situations under a policy $\pi$. The state value $V^\pi(s)$ is the expected return when starting in $s$ and following $\pi$. The action value $Q^\pi(s,a)$ is the expected return when starting in $s$, taking action $a$ first, and following $\pi$ after that. The optimal action value is $Q^*(s,a) = \max_\pi Q^\pi(s,a)$: the best expected return any policy can get after taking $a$ in $s$, a maximum over all policies. Q-learning tries to learn $Q^*$.

The difference between the two is the advantage:

It measures how much better action $a$ is than the policy's average behavior in the same state. Suppose a state is worth $V = 5$ and two actions have $Q$ values 6 and 4. Their advantages are $+1$ and $-1$. In a worse state with $V = -20$ and $Q$ values $-19$ and $-21$, the advantages are again $+1$ and $-1$. The advantage removes how good the state is and keeps only the comparison between actions, which is what a policy update needs. The actor-critic section uses it as the weight on each policy update.

How parallel actors replace experience replay

Figure 1 already showed the mechanism: a batch made of many actors' current samples is as varied as a batch drawn from a buffer. In the paper, each of the 16 threads runs its own copy of the environment. At any instant one thread may be in the first room of a game, another near the end of a level, another just losing a life. The paper says the parallel actor-learners "are likely to be exploring different parts of the environment", so the updates they apply together are "less correlated in time than a single agent applying online updates." The same mix also spans many stages of play at once, which the paper describes as decorrelating the data "into a more stationary process."

Figure 2 shows this in an abstract state space. With one actor, the update batch is a short segment of one trajectory and the spread meter reads low. Drag the slider to 16 and the batch covers the space.

The paper adds diversity on purpose. For the three value-based methods, which explore with $\varepsilon$-greedy actions (a random action with probability $\varepsilon$, the greedy one otherwise), each thread samples its own final $\varepsilon$: 0.1 with probability 0.4, 0.01 with probability 0.3, or 0.5 with probability 0.3, each annealed down from 1 over the first four million frames. Some threads end up nearly greedy and others keep acting randomly half the time, so they visit different states.

The data from parallel actors is also fresh: each thread acts with the current shared weights, synced at the start of every short rollout. That brings on-policy methods back. Sarsa and Q-learning show the difference in a single term. Both move $Q(s,a)$ toward a target built from the reward and the next state. Q-learning uses $r + \gamma \max_{a'} Q(s',a')$, the value of the best next action, which is correct for the optimal policy whichever policy produced the transition, so old data works. Sarsa uses $r + \gamma\, Q(s',a')$ with $a'$ the action the agent took next, which evaluates the policy that generated the data, so the data has to come from the current policy. Asynchronous one-step Q and n-step Q are off-policy and could have used a buffer; one-step Sarsa and A3C are on-policy and could not.

Dropping replay does not mean replay is useless. The paper's conclusion says that stable training without it "does not mean that experience replay is not useful", and that adding replay to the framework "could substantially improve the data efficiency of these methods by reusing old data."

Sixteen threads, one set of weights

The 16 actors are threads in one process sharing one set of network weights in memory. Each thread repeats four steps: copy the shared weights into a private copy, act in its own environment for up to 5 steps, compute a gradient from those steps, and add that gradient into the shared weights. There is no central server and no lock around the parameters. Two threads may write to the same weights at the same moment, and one write can partly overwrite the other. This lock-free scheme comes from Hogwild! (Recht et al., 2011). Hogwild!'s convergence guarantee assumes sparse updates, where each gradient touches only a few parameters. A deep network's gradients are dense, so A3C does not inherit the guarantee and relies on its experiments.

Because the threads start their rollouts at different times, they are always at different points in the loop. No thread waits for another; the word asynchronous in the title refers to this. Click a thread in Figure 3 to read its current step.

The predecessor was Gorila (Nair et al., 2015), a distributed DQN with 100 actor-learner processes and 30 parameter servers, 130 machines in total, each actor still keeping its own replay memory. A3C moves the whole system onto one multi-core CPU and drops replay. Keeping the threads on one machine removes the cost of sending gradients and parameters over a network, and it makes the lock-free shared-memory updates possible.

Each thread accumulates its gradient over the steps of a rollout and applies it once, like a minibatch. The paper gives two reasons: fewer writes mean fewer chances for threads to overwrite each other's updates, and the rollout length trades computation against data efficiency. All experiments update after every 5 actions ($t_{\max} = 5$).

n-step returns: moving reward back faster

One-step Q-learning, as DQN uses it, regresses $Q(s,a;\theta)$ toward a target $y$ built from one reward and the estimated value of the next state:

Here $\theta^{-}$ is a target network, a copy of the weights that is refreshed only occasionally, so the target does not move with every gradient step. (The paper's background section writes the previous iterate $\theta_{i-1}$ in this slot; its algorithms use $\theta^{-}$.) A reward $r$ changes only $Q(s,a)$ for the one state-action pair that earned it. The state before that one learns about the reward only on a later update, after $Q(s,a)$ has moved and shows up in its own target, and the state before that one update later still. A reward 20 steps after the decision that caused it needs at least 20 rounds of updates to reach that decision.

An $n$-step return uses $n$ real rewards before falling back on the estimate:

Now one reward directly changes the targets of the $n$ state-action pairs before it. In Figure 4, set $n=1$ and only the last state before the reward is reached; at $n=7$ one update reaches seven states back.

The longer return has a cost. The bootstrap term $\gamma^n \max_a Q$ is an estimate that may be wrong; a longer return leans on it less (less bias) but sums more random rewards (more variance).

The paper computes these returns in the forward view: roll out up to $t_{\max}$ steps, then compute each state's return directly from the rewards that followed it. The classical alternative is the backward view of TD($\lambda$), which keeps an eligibility trace (a decaying record of recently visited states) and spreads each new error back along it. The authors chose the forward view because it is "easier when training neural networks with momentum-based methods and backpropagation through time." Within one rollout, the states get returns of different lengths: the last state gets a one-step return, the second-to-last a two-step return, and the first a $t_{\max}$-step return. Each state uses one return length; the mix is across states, not a weighted blend of lengths per state.

How A3C works: the actor and the critic

Value-based methods learn $Q$ and act greedily on it. Policy-based methods instead give the network a softmax output $\pi(a\mid s;\theta)$ and change $\theta$ to raise the expected return. The basic estimator is REINFORCE (Williams, 1992): for each action taken, step in the direction

which makes the action more likely in proportion to the return that followed it. Averaged over many samples, this is an unbiased estimate of $\nabla_\theta \mathbb{E}[R_t]$. A single sample is very noisy. In a state where every action leads to a return near 100, every sampled action gets pushed up by about 100, and the part of the signal that says which action was better (a difference of a few points) is small compared with that common push.

Subtracting a baseline $b(s)$, any function of the state alone, and using $R_t - b(s_t)$ as the multiplier removes the common push without changing the expected gradient:

Read (5) left to right. $b(s)$ does not depend on the action, so it moves outside the expectation. The expectation weights each $\nabla_\theta \log \pi(a\mid s)$ by $\pi(a\mid s)$, and $\pi \nabla \log \pi = \nabla \pi$. The sum of $\nabla_\theta \pi(a\mid s)$ over actions is the gradient of $\sum_a \pi(a\mid s) = 1$, a constant, so it is zero. The baseline changes the variance of the estimate and leaves its mean alone.

The usual choice is $b(s) \approx V^\pi(s)$, learned by the same network. The return $R_t$ after taking $a_t$ is a sample of $Q^\pi(s_t,a_t)$, so $R_t - V(s_t)$ estimates $Q - V$, the advantage from (2). Why not subtract $Q(s,a)$, which would center each action exactly? Because it depends on the action, it cannot move outside the sum in (5), and the update would become biased. This setup is called actor-critic: the policy $\pi$ is the actor, the value estimate $V$ is the critic that supplies the baseline, and the "advantage" in A3C's name is $R_t - V(s_t)$.

Figure 5 runs this update on a one-dimensional action. Sampled actions with return above the dashed baseline get an up arrow, those below get a down arrow, and the policy moves toward the peak of the return curve.

A3C does not wait for the end of the episode to compute $R_t$. It uses the $k$-step return from the previous section, with the critic supplying both the bootstrap value at the end of the rollout and the baseline:

Here $k$ varies from state to state and is at most $t_{\max}$. With $k=1$, (6) is the one-step temporal-difference error $r_t + \gamma V(s_{t+1}) - V(s_t)$. Subtracting the baseline adds no bias, by (5). The bias in (6) comes from the bootstrap term $\gamma^k V(s_{t+k})$: while $V$ is still inaccurate, the estimated return is off by $\gamma^k$ times its error. Larger $k$ shrinks that factor and adds more reward noise. A3C uses one $k$ per state, set by its position in the rollout; generalized advantage estimation (Schulman et al., 2015), which averages over all $k$ with geometric weights, is listed in the paper as a possible improvement.

The actor and critic are trained in opposite directions. The actor takes gradient ascent steps on $\log \pi(a_t\mid s_t) \cdot A$, raising the probability of actions with positive advantage. The critic takes gradient descent steps on $(R_t - V(s_t))^2$, treating $R_t$ as a fixed target even though it contains $V(s_{t+k})$ (a semi-gradient). In Atari the two are one network: the policy $\theta$ and value $\theta_v$ are written separately for generality, but they share every layer except the two output heads. A3C is on-policy, so it could not have been trained from a replay buffer. The same family of policy-gradient methods includes TRPO, published a year earlier, and PPO, published a year later; Soft Actor-Critic later rebuilt actor-critic as an off-policy method with a replay buffer and an entropy term in the objective itself.

The entropy bonus

A policy-gradient learner can raise the probability of the first action that pays off until it is close to 1. After that it rarely samples anything else, so it never finds out whether another action is better. The paper counters this by adding the entropy of the policy, $H(\pi(\cdot\mid s))$, to the objective. Entropy is highest for a uniform distribution and zero for a deterministic one. The full actor gradient is

The entropy term is added and the actor ascends, so the update rewards a spread-out policy and pushes back against collapse onto one action. The weight is $\beta = 0.01$ in all Atari and TORCS experiments. For a policy over 6 actions, entropy ranges from 0 (deterministic) to $\ln 6 \approx 1.79$ (uniform). The bonus dates to Williams and Peng (1991) and applies only to the actor; the value-based variants have no policy distribution and explore with $\varepsilon$-greedy actions instead.

In Figure 6, slide $\beta$ toward zero and the policy puts nearly all its probability on the best action. Raise it and probability spreads back to the other actions. At the top of the range the policy is close to uniform and barely prefers the best action.

For continuous actions (the MuJoCo experiments) the policy is a Gaussian with mean $\mu$ and variance $\sigma^2$, and its entropy is

The paper writes the term as a cost, $-\tfrac{1}{2}(\log(2\pi\sigma^2)+1)$, with weight $10^{-4}$. Since $1 = \log e$, that cost is exactly $-H$. Adding $-H$ to a loss that is minimized is the same as adding $+H$ to an objective that is maximized, so it also rewards entropy and keeps $\sigma$ from shrinking to zero. A Gaussian's entropy can be negative (below $\sigma \approx 0.24$), unlike the entropy of a discrete distribution.

One A3C update, step by step

One thread's loop, following the paper's Algorithm S3 with the entropy term from (7) added (Algorithm S3 leaves it out; Section 4 specifies it):

# one actor-learner thread (Algorithm S3); shared: theta, theta_v, counter T
repeat:
    d_theta, d_v = 0, 0
    theta_p, v_p = theta, theta_v        # sync a private copy of the weights
    t_start = t
    while not terminal(s) and t - t_start < t_max:      # t_max = 5
        a = sample(pi(s; theta_p))       # act on-policy in this thread's game
        s_next, r = env.step(a); store(s, a, r)
        s = s_next; t += 1; T += 1
    R = 0 if terminal(s) else V(s; v_p)  # bootstrap from the value head
    for i in reversed(range(t_start, t)):           # walk the rollout backward
        R = r[i] + gamma * R             # (k = t - i)-step return for state i
        adv = R - V(s[i]; v_p)           # advantage, eq (6)
        d_theta += grad log pi(a[i] | s[i]; theta_p) * adv
        d_theta += beta * grad H(pi(s[i]; theta_p))  # entropy, eq (7)
        d_v     += grad (R - V(s[i]; v_p))**2       # R is a fixed target
    apply(theta, d_theta); apply(theta_v, d_v)      # shared RMSProp, no lock
until T > T_max

Figure 7 runs the inner backward loop on numbers. The thread has played 5 steps, collected rewards 0, 0, 1, 0, 0, and now stands in $s_5$, which its critic values at 0.40. The critic's current predictions for $s_0$ through $s_4$ are fixed numbers in the table. Starting from $R = 0.40$, the loop computes $R_4 = 0 + 0.99 \times 0.40 = 0.396$, then $R_3 = 0.392$, $R_2 = 1 + 0.99 \times 0.392 = 1.388$, $R_1 = 1.374$, and $R_0 = 1.360$. Subtracting each $V(s_i)$ gives advantages 0.740, 0.674, 0.538, 0.092 and 0.046 for $s_0$ to $s_4$.

The table shows two things. First, the bottom row: $s_4$ uses a 1-step return and $s_0$ a 5-step return, the mix across states described in the n-step section. Second, the reward of 1 raised the advantage of every action before it, including the actions at $s_1$ and $s_0$, one and two steps before the rewarded action at $s_2$, in one update. Mark $s_5$ as terminal and the bootstrap becomes 0: $R_4$ and $R_3$ drop to 0, their advantages become $-0.35$ and $-0.30$, and the actor lowers the probability of those two actions.

The network in the paper's speed experiments (and TORCS) is the one from the 2013 DQN paper. Its input is the last 4 frames, downsampled to $84 \times 84$. A convolution with 16 filters of $8\times 8$ at stride 4 gives a $20 \times 20 \times 16$ map; a second with 32 filters of $4 \times 4$ at stride 2 gives $9 \times 9 \times 32$, which is 2,592 numbers; a fully connected layer maps those to 256 units. All three use ReLU. On top sit the two heads: a softmax with one output per action (the actor) and one linear output (the critic). For a 6-action game that is about 678,000 weights, 98% of them in the fully connected layer. A recurrent variant adds 256 LSTM cells after the last hidden layer. For the 57-game comparison the paper says its feedforward agent used the architecture of the 2015 Nature DQN and its successors instead.

The optimizer is shared as well. The paper compares momentum SGD, RMSProp with per-thread statistics, and RMSProp whose running average of squared gradients $g$ lives in shared memory and is updated by every thread without locks:

All operations are elementwise, $\Delta\theta$ is the accumulated gradient, and $\epsilon$ sits inside the square root. Each parameter's step is divided by a running estimate of its gradient's size, the same idea Adam combines with momentum. Shared RMSProp was the most robust of the three across learning rates, per-thread RMSProp second, momentum SGD last. The decay is $\alpha = 0.99$; the learning rate is drawn per run from $\mathrm{LogUniform}(10^{-4}, 10^{-2})$ and annealed to 0 over training.

The three value-based variants run the same loop with a different loss and one extra component, a shared target network $\theta^{-}$ refreshed every 40,000 frames. A3C has no target network. Each thread syncs its private copy of the weights at the start of every 5-step rollout and bootstraps from $V(s_t;\theta_v')$ (0 if the episode ended). A target network addresses the moving target in (3); it does nothing about the upward bias that the $\max$ in (3) introduces when the $Q$ estimates are noisy. Double DQN fixes that bias, and the paper lists reducing it as future work for its value-based methods.

Continuous control changes the actor head and little else. The policy outputs a mean $\mu$ from a linear layer and a variance $\sigma^2$ through a SoftPlus, $\log(1+e^x)$, which keeps it positive, and actions are sampled from that Gaussian. In those MuJoCo runs the policy and value networks share no parameters, and because episodes were at most a few hundred steps, each episode became one update with no bootstrapping.

Speedup with more threads

The authors measured, for each method and thread count, the wall-clock time to reach a fixed reference score, and defined the speedup as the one-thread time divided by the $n$-thread time, averaged over seven Atari games. More threads process more frames per second, so the expected best case is about linear: $n$ threads, $n$ times faster. All four methods reach at least a 12-fold speedup at 16 threads. The two one-step methods go past linear: 24.1× for one-step Q-learning and 22.1× for one-step Sarsa. Drag the slider in Figure 8 to read each method at each thread count.

Extra threads give at most a linear gain in frames processed per second. A speedup above $n$ means the method also needed fewer total frames to reach the score. If throughput scaled perfectly, one-step Q at 16 threads would have needed about $16 / 24.1 \approx 0.66$ as many frames as with one thread. The paper observes this directly (its Figure 3 plots score against frames) and offers an explanation it labels as a belief: more threads reduce the bias of one-step methods, whose targets lean entirely on their own bootstrapped estimates. n-step Q reaches 17.2×, just above 16, and the paper does not call it superlinear. A3C reaches 12.5×, below linear.

The paper also checks stability. For each of the four methods on five games it trains 50 agents with different learning rates and random initializations. Each method and game has a wide band of learning rates in which nearly every run scores well, and in those bands there are almost no runs with a score of 0, which would have signaled training that collapsed or diverged.

Atari scores: mean and median

The 57-game comparison uses human-normalized scores (100% means human level, 0% means random play) with the "human starts" evaluation (each test episode begins from a point taken from a human player's game), and reports both the mean and the median across games. Hyperparameters were tuned on six games and then fixed for all 57. On the mean, A3C with an LSTM scores 623.0%, ahead of the best DQN variant, Prioritized DQN, at 463.6%, after four days on 16 CPU cores against eight days on a K40 GPU. After one day, A3C's feedforward agent already matches Dueling Double DQN's mean (344.1% against 343.8%). Switch Figure 9 to the median and the order changes.

On the median, A3C feedforward (116.6%) and A3C LSTM (112.6%) roughly tie Dueling Double DQN (117.1%) and trail Prioritized DQN (127.6%). A mean over 57 games is dominated by the few games where an agent scores many times a human's score; the median describes the typical game. The paper's claim, that A3C "significantly improves on state-of-the-art the average score" in half the training time, holds for the mean.

A3C also trained outside Atari, in settings where the value-based variants were weaker or not applicable:

• TORCS, a 3D car racing simulator with a reward proportional to speed along the track. A3C was the best of the four methods, reaching roughly 75% to 90% of a human tester's score on all four settings (a slow or fast car, with or without opponent bots) in about 12 hours of training.
• MuJoCo continuous control, close to the tasks in DDPG. Only A3C was tested, because it extends easily to continuous actions. It found good solutions in under 24 hours, usually in a few hours, from joint states and, on three tasks, from pixels.
• Labyrinth, randomly generated 3D mazes seen through $84 \times 84$ RGB frames. Apples are worth 1 and a portal is worth 10 (it respawns the agent elsewhere and restores the apples), with 60-second episodes and a new maze every episode. An A3C LSTM agent reached an average score of about 50, which the paper reads as a reasonable exploration strategy.

Synchronous A2C: what carried over

Later work separated the two ideas in the title. In 2017 OpenAI released A2C, a synchronous version: all actors step their environments together, their gradients are averaged, and one batched update is applied, which suits a GPU better than many small asynchronous updates. OpenAI reported that A2C gives equal performance and that their synchronous implementation performed better than their asynchronous ones, with no evidence that the noise from asynchrony helped. Clemente et al.'s PAAC (2017) is a similar synchronous design. Christiano et al. used A2C for the Atari experiments in deep RL from human preferences.