Technical Summary: Ensemble Elastic DQN (EEDQN)

Problem Statement

Deep Q-Networks (DQN) and other value-based reinforcement learning algorithms frequently suffer from overestimation bias. This occurs because bootstrapped targets utilize a maximization operation over noisy value estimates, allowing positive errors to be selected and propagated through subsequent updates. This inflation of Q-values can mislead action selection, encourage agents to revisit overestimated state-action regions, and contribute to convergence toward sub-optimal policies.

While ensemble-based methods (e.g., Averaged DQN, MaxMin DQN) and multi-step methods (e.g., Rainbow, Elastic Step DQN) have independently shown promise in improving stability and sample efficiency, their interaction remains under-explored. Combining these approaches is non-trivial; while ensemble aggregation can reduce overestimation, applying conservative aggregation uniformly across all targets risks introducing underestimation bias. Furthermore, existing adaptive multi-step methods like Elastic Step DQN rely on computationally expensive clustering-based similarity tests, limiting their scalability.

Methodology

The paper proposes Ensemble Elastic DQN (EEDQN), a value-based algorithm that integrates adaptive elastic multi-step returns with horizon-dependent ensemble aggregation.

1. Scalable Elastic Step Mechanism

EEDQN modifies the original Elastic Step DQN to eliminate the computational overhead of clustering. Instead of using representation clustering to determine state similarity, EEDQN employs a lightweight Q-value difference rule:

• It maintains an ensemble of $N$ target networks $\{\hat{Q}_i\}$.
• It computes the ensemble mean target vector $\bar{Q}^-(s, \cdot)$.
• It calculates the $L_1$ difference ($z$) between the mean target vectors of the start state ($s_0$) and the current next state ($s'$).
• An adaptive threshold ($h$) is derived from a historical buffer of recent $z$ values ($h = \text{mean}(B) + \text{std}(B)/\sqrt{|B|}$).
• If $z > h$, the trajectory is deemed to have entered a new value region, triggering the storage of the accumulated return and resetting the accumulation. Otherwise, rewards continue to accumulate.

2. Horizon-Dependent Ensemble Aggregation

A core innovation of EEDQN is the use of different aggregation rules based on the length of the accumulated return (horizon $k$):

• One-step targets ($k=1$): The bootstrap value is calculated using the ensemble mean. This prevents the targets from becoming overly conservative, which could hinder learning in regions where bootstrapping is necessary.
• Multi-step elastic returns ($k > 1$): The bootstrap value is calculated using the ensemble minimum. Since longer returns already accumulate significant reward information before the bootstrap term, using the minimum reduces extreme optimistic extrapolation without dominating the full target value.

The target value $y$ is defined as:
$$y = \begin{cases} R(k) & \text{if terminal} \\ R(1) + \gamma G_{\text{mean}}(s', a^*) & \text{if } k=1 \\ R(k) + \gamma^k G_{\text{min}}(s', a^*) & \text{if } k>1 \end{cases}$$
where $a^*$ is the greedy action selected based on the ensemble mean.

Key Contributions

1. Algorithm Proposal: Introduction of EEDQN, which combines adaptive elastic multi-step returns with ensemble-based target aggregation.
2. Scalability Improvement: Replacement of the clustering-based similarity test in Elastic Step DQN with a lightweight Q-value difference rule, making adaptive return construction more applicable to discrete control settings.
3. Horizon-Dependent Aggregation: Proposal of a rule where one-step targets use the ensemble mean while longer elastic returns use the ensemble minimum, aiming to balance the reduction of optimistic bias with the preservation of sample efficiency.
4. Empirical Evaluation: Comprehensive evaluation against DQN, Double DQN, Averaged DQN, MaxMin DQN, and Elastic Step DQN across five MinAtar environments.
5. Ablation Analysis: Investigation of various aggregation rules (mean, minimum, swapped, and convex combinations) to analyze the interaction between ensemble conservatism and adaptive return length.

Experimental Results

EEDQN was evaluated on five MinAtar environments (Seaquest, SpaceInvaders, Asterix, Breakout, Freeway) using 10 matched random seeds.

• Performance: EEDQN achieved the highest final return in four of the five environments (SpaceInvaders, Asterix, Breakout, Freeway). In Seaquest, MaxMin DQN performed best, with EEDQN ranking second.
• Value Inflation Control: A diagnostic metric comparing maximum observed Q-values against the theoretical discounted return upper bound showed that EEDQN and MaxMin DQN remained below the inflation threshold in all environments. In contrast, DQN, DDQN, Averaged DQN, and Elastic Step DQN exceeded this bound in at least one environment.
• Ablation Findings: No single aggregation rule dominated across all environments.
  • EEDQN (Mean for $k=1$, Min for $k>1$) performed best in Asterix, Breakout, and Freeway.
  • MinEEDQN (Min for all) performed best in Seaquest, an environment with severe overestimation issues.
  • ConvexEEDQN2 (50/50 mix) performed best in SpaceInvaders.
  • This suggests the optimal degree of conservatism is environment-dependent.

Significance and Claims

The paper claims that EEDQN successfully demonstrates that adaptive multi-step returns and ensemble aggregation are complementary mechanisms for reducing overestimation bias. However, the results also indicate that a "one-size-fits-all" aggregation strategy is suboptimal; the best degree of conservatism depends on the specific environment's characteristics.

The authors position EEDQN as a lightweight value-based approach that studies how aggregation rules should adapt to the backup horizon. They explicitly state that the contribution lies not merely in using ensembles or multi-step returns in isolation, but in the study of a horizon-dependent rule that changes the aggregation operator based on the adaptive return length. The paper concludes that while EEDQN improves upon standard baselines, future work is needed to investigate adaptive aggregation rules that adjust the mean-minimum trade-off online and to evaluate the method on larger benchmarks like the full Atari Learning Environment.