Value-based reinforcement learning agents learn a critic, a network that predicts how much future reward an action will earn. They then pick actions the critic scores highest. Because the critic is noisy, "pick the highest" systematically selects actions whose scores are inflated by error. This overestimation bias compounds as the agent bootstraps each prediction from the next one. The most sample-efficient fixes train large ensembles of critics many times per environment step and take a minimum over a few of them. They are expensive, and they run every critic in lock-step. Spreading those critics across devices without waiting for one another would remove the synchronization barrier. The usual expectation is that it would also make things worse, because each critic would be working from out-of-date ("stale") information.
This note argues the opposite may hold over a useful range. Overestimation in actor-critic methods arises mainly because the actor, the network that proposes actions, climbs the errors of the very critics it is trained against. A critic the actor has not recently consulted, for example one lagging on another device, has errors that are less aligned with the actor's choices. It behaves like the independent evaluator that double Q-learning wanted but could not get in continuous control. If that holds, asynchrony stops being a cost we tolerate for throughput. It becomes a source of evaluator independence, as long as the lag is bounded and corrected.
Core Claim
The claim is this: in an ensemble actor-critic, bias in the learning target depends on two quantities that synchronous designs merge. The first is how far a critic's parameters lag behind the present, which we call lag. The second is whether the actor has been optimized against that critic, which we call exploitation. Exploited critics carry positively correlated error at the actor's chosen actions. Unexploited critics carry a lag bias that grows with staleness but has no such correlation.
We propose a target built only from critics the actor has not recently ascended. Concretely, write $Q_i$ for critic $i$, $\tau_i$ for its staleness in learner steps, $\mathcal{U}_t$ for the critics not consulted by the actor in the last window, and $\mathcal{M}\subset\mathcal{U}_t$ for a random subset of size $M$. The target is
$$y = r + \gamma \Big( \min_{i \in \mathcal{M}} Q_i(s', \pi_t(s')) + \hat{b}(\tau_{\mathcal{M}}) \Big),$$
where $\pi_t$ is the current actor and $\hat{b}(\tau)$ is a staleness correction fitted online. That correction is estimated the way Automating Control of Overestimation Bias for Continuous Reinforcement Learning estimates bias: by comparing predictions to returns from fresh rollouts. The difference is that we index the correction by staleness rather than fitting a single global scalar.
The resulting system runs critics as non-blocking workers. It should match REDQ-style sample efficiency at lower wall-clock cost, with lower measured bias than a synchronized ensemble of the same size.
Relation to Prior Work
Three lines of work motivate the proposal.
Deep Reinforcement Learning with Double Q-Learning separates choosing an action from scoring it. Addressing Function Approximation Error in Actor-Critic Methods, the TD3 paper, shows this separation fails in actor-critic because the target network drifts too slowly to stay independent. TD3 falls back on a pessimistic minimum of two critics. We take the diagnosis seriously and seek independence through the actor's training graph rather than through time alone.
Randomized Ensembled Double Q-Learning (REDQ) uses ten critics, a minimum over random pairs, and twenty updates per environment step. Aggressive Q-Learning with Ensembles (AQE) averages the lowest few critics over a shared multi-head backbone. Both name compute as their main cost. Both also update all critics in lock-step and let the actor consult the whole ensemble, so every critic is exploited.
Use the Online Network If You Can (MINTO) takes the minimum of online and target networks. It is the closest serial cousin, but it mixes a fresh exploited network with a stale exploited copy of the same network. It reports being comparable or slightly worse on DMC-Hard, which is consistent with over-conservatism.
The systems side supplies method and constraints. PASSCoDe and Asynchronous Parallel Greedy Coordinate Descent show that lock-free updates keep convergence under bounded staleness. Those proofs are for convex problems, and PASSCoDe degrades on dense data. We borrow the bounded-staleness discipline, a hard cap on $\tau_i$, but not the convex guarantees. Evaluation of publicly available Barrier-Algorithms shows that application speedup is limited by load imbalance at barriers more than by barrier latency itself. A per-gradient-step ensemble barrier is exactly this kind of imbalance point. Acceleration for Deep Reinforcement Learning using Parallel and Distributed Computing: A Survey names policy lag as the price of asynchrony but does not measure its effect on overestimation. That measurement is our first deliverable.
Research Program
The first stage is purely diagnostic and runs in serial code with simulated delay. Each critic's parameters are read from a buffer of past snapshots with a controlled lag $\tau$. Separately, we control whether the actor's loss includes that critic. This produces a two-by-two design: lag versus no lag, crossed with exploited versus unexploited. Within it we measure true bias by the protocol of TD3 and REDQ: Monte Carlo returns from the current policy compared against critic predictions at sampled states, reporting both mean and standard deviation of normalized bias.
The prediction is specific. Unexploited critics should show lower overestimation at small $\tau$, with an underestimation-like lag bias growing in $\tau$. Exploited stale critics, the target-network case, should show little benefit. If unexploited fresh critics already deliver the whole effect, the asynchronous story collapses into a serial algorithm. We would report that outcome as such.
The second stage builds the system. Critics live on separate GPUs or processes and pull replay batches and actor snapshots without barriers. The actor reads a rotating subset of critics. Targets are assembled from whichever unexploited replicas are fresh within the cap. The staleness correction $\hat{b}(\tau)$ is a small regression from observed lag to the rollout-measured bias gap. It is refit every few thousand steps.
The third stage stresses the system with stragglers: heterogeneous device speeds and injected jitter. The aim is to find where the cap binds and where the bounded-delay assumptions behind PASSCoDe-style reasoning break.
Baselines
The naive reference point is SAC with two critics at the same high update-to-data ratio. This is the configuration REDQ and AQE show to overestimate badly. It tells us how much of any gain comes from the ensemble at all.
The strongest existing competitor is REDQ, with AQE as a second strong competitor. REDQ reports being roughly 3x to 8x more sample efficient than SAC on Hopper, Walker2d, Ant, and Humanoid. Combined with OFENet, it reached 5000 on Humanoid in 150K interactions. AQE reports reaching target performance about 3x faster than SAC and 2x faster than TQC, with final MuJoCo scores 26% above SAC. On DMC, AQE reports up to 13.7x early efficiency over SAC.
The stronger synchronized competitor is a REDQ implementation with all ten critics vectorized on a single GPU. That isolates the barrier question honestly. No reported wall-clock or synchronization-cost figures for REDQ or AQE were found on Lacuna beyond REDQ's note that MBPO took about 75% longer to run, so we will measure wall-clock ourselves.
All methods get the same ensemble size and update ratio, the same replay data pipeline, the same hardware, and the same hyperparameter search budget per method, over ten seeds. Beating the competitor means matching REDQ's return curves within seed noise at equal environment steps. It also means reaching REDQ's final return in less wall-clock time on the multi-device setup, with measured bias closer to zero.
MINTO and TD3 serve as cheap pessimistic baselines.
Two ablations isolate the key ingredient. In one, the target uses all critics including exploited ones, giving asynchrony without independence. In the other, everything stays synchronous but the actor-critic split is kept, giving independence without asynchrony. A third ablation removes $\hat{b}$ to test whether the correction is needed.
Why not just…?
Why not just vectorize the ensemble on one GPU and keep it synchronous? This is the real threat for MuJoCo-sized networks. The multi-head design in AQE and GPU batching of the kind the survey credits to Isaac Gym may make the barrier nearly free. The independence-without-asynchrony ablation addresses it directly. If that ablation captures the bias benefit and single-GPU synchronous code is fastest, the contribution narrows to an algorithmic result: hold critics out of the actor's loss. We would claim no systems win and say so. The asynchronous design earns its place only on multi-device runs, with larger critics, or when replicas straggle, and we report the crossover point.
Why not just use TD3's clipped two-critic minimum or MINTO? Both are cheap. However, REDQ and AQE document that two-critic pessimism stalls or overestimates at high update ratios. MINTO's own DMC-Hard results suggest over-conservatism. Both are run as baselines at the same update ratio, and the bias measurements will show whether their gap is in mean bias or in its variance.
Why not just treat the target network as the "stale critic" you need? A target network is a lagged copy of a critic the actor already exploited. TD3 found that such copies stay too correlated to act as independent judges. The exploited-and-stale cell of the stage-one design measures exactly this case. If it performs as well as the unexploited cell, our central mechanism is wrong.
Why not just tune the pessimism adaptively, as in automated overestimation control? That approach removes grid search but adjusts one global penalty. It does not change which errors enter the target. We include it as a baseline with its rollout-based tuning. We also test whether our staleness-indexed correction adds anything once evaluator independence is in place.
Proposed Experiments
Stage one runs on MuJoCo Hopper, Walker2d, Ant, and Humanoid at update ratio 20 with ten critics. It sweeps simulated lag $\tau \in \{0, 1, 5, 20, 100\}$ steps across the exploited and unexploited conditions, and reports normalized bias mean and standard deviation alongside returns.
The decisive check has two parts. The unexploited condition must show significantly lower mean overestimation than the exploited one at small $\tau$. Lag bias must rise monotonically with $\tau$. Without both, the approach is abandoned.
Stage two compares the asynchronous system against the baselines on MuJoCo and DMC on one-, two-, four-, and eight-GPU nodes. It reports return against environment steps, return against wall-clock time, and device idle fraction.
Stage three injects stragglers by slowing one replica by factors of two to ten. It checks whether the staleness cap and correction keep bias bounded where an uncapped lock-free variant diverges, which probes whether convex-style bounded-delay intuitions transfer to temporal-difference learning at all.
Success requires all of the following: equal sample efficiency to REDQ, lower measured bias, and a wall-clock advantage that grows with device count. The program also succeeds, as a narrower serial result, if the evaluator-independence effect turns out to be real but synchronous.
References
- Automating Control of Overestimation Bias for Continuous Reinforcement Learning
- Deep Reinforcement Learning with Double Q-Learning
- Addressing Function Approximation Error in Actor-Critic Methods
- Randomized Ensembled Double Q-Learning: Learning Fast Without a Model
- Aggressive Q-Learning with Ensembles: Achieving Both High Sample Efficiency and High Asymptotic Performance
- Use the Online Network If You Can: Towards Fast and Stable Reinforcement Learning
- PASSCoDe: Parallel ASynchronous Stochastic dual Co-ordinate Descent
- Asynchronous Parallel Greedy Coordinate Descent
- Evaluation of publicly available Barrier-Algorithms and Improvement of the Barrier-Operation for large-scale Cluster-Systems with special Attention on InfiniBand Networks
- Acceleration for Deep Reinforcement Learning using Parallel and Distributed Computing: A Survey