# Elastic Step DQN: A novel multi-step algorithm to alleviate overestimation in Deep QNetworks

arXiv: https://arxiv.org/abs/2210.03325 · HTML: https://mlsanity.com/paper/2210.03325/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 51 references that are in the map.
- First posted on arXiv 7 Oct 2022.

## Builds on (most cited first, 25 of 25)

- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Addressing Function Approximation Error in Actor-Critic Methods](https://mlsanity.com/paper/1802.09477/) (2018)
- [Deep Reinforcement Learning with Double Q-learning](https://mlsanity.com/paper/1509.06461/) (2015)
- [OpenAI Gym](https://mlsanity.com/paper/1606.01540/) (2016)
- [Curiosity-driven Exploration by Self-supervised Prediction](https://mlsanity.com/paper/1705.05363/) (2017)
- [Rainbow: Combining Improvements in Deep Reinforcement Learning](https://mlsanity.com/paper/1710.02298/) (2017)
- [Dueling Network Architectures for Deep Reinforcement Learning](https://mlsanity.com/paper/1511.06581/) (2015)
- [CURL: Contrastive Unsupervised Representations for Reinforcement Learning](https://mlsanity.com/paper/2004.04136/) (2020)
- [Distributional Reinforcement Learning with Quantile Regression](https://mlsanity.com/paper/1710.10044/) (2017)
- [Distributed Prioritized Experience Replay](https://mlsanity.com/paper/1803.00933/) (2018)
- [Safe and Efficient Off-Policy Reinforcement Learning](https://mlsanity.com/paper/1606.02647/) (2016)
- [Revisiting Fundamentals of Experience Replay](https://mlsanity.com/paper/2007.06700/) (2020)
- [Deep Reinforcement Learning and the Deadly Triad](https://mlsanity.com/paper/1812.02648/) (2018)
- [Maxmin Q-learning: Controlling the Estimation Bias of Q-learning](https://mlsanity.com/paper/2002.06487/) (2020)
- [Kinematic State Abstraction and Provably Efficient Rich-Observation Reinforcement Learning](https://mlsanity.com/paper/1911.05815/) (2019)
- [Averaged-DQN: Variance Reduction and Stabilization for Deep Reinforcement Learning](https://mlsanity.com/paper/1611.01929/) (2016)
- [Accelerated Hierarchical Density Clustering](https://mlsanity.com/paper/1705.07321/) (2017)
- [Revisiting Rainbow: Promoting more Insightful and Inclusive Deep Reinforcement Learning Research](https://mlsanity.com/paper/2011.14826/) (2020)
- [MushroomRL: Simplifying Reinforcement Learning Research](https://mlsanity.com/paper/2001.01102/) (2020)
- [GEP-PG: Decoupling Exploration and Exploitation in Deep Reinforcement Learning Algorithms](https://mlsanity.com/paper/1802.05054/) (2018)
- [Provable RL with Exogenous Distractors via Multistep Inverse Dynamics](https://mlsanity.com/paper/2110.08847/) (2021)
- [WD3: Taming the Estimation Bias in Deep Reinforcement Learning](https://mlsanity.com/paper/2006.12622/) (2020)
- [The Effect of Multi-step Methods on Overestimation in Deep Reinforcement Learning](https://mlsanity.com/paper/2006.12692/) (2020)
- [On the Reduction of Variance and Overestimation of Deep Q-Learning](https://mlsanity.com/paper/1910.05983/) (2019)
- [Mixture of Step Returns in Bootstrapped DQN](https://mlsanity.com/paper/2007.08229/) (2020)

## Built on by (most cited first, 5 of 5)

- [Delphos: A reinforcement learning framework for assisting discrete choice model specification](https://mlsanity.com/paper/2506.06410/) (2025)
- [Issues with Value-Based Multi-objective Reinforcement Learning: Value Function Interference and Overestimation Sensitivity](https://mlsanity.com/paper/2402.06266/) (2024)
- [PER-DPP Sampling Framework and Its Application in Path Planning](https://mlsanity.com/paper/2503.07411/) (2025)
- [Ensemble Elastic DQN: A Step Dependent Ensemble Approach for Reducing Overestimation in Deep Value-Based Reinforcement Learning](https://mlsanity.com/paper/2506.05716/) (2025)
- [Trajectory Planning for UAV-Based Smart Farming Using Imitation-Based Triple Deep Q-Learning](https://mlsanity.com/paper/2512.18604/) (2025)

## Abstract (arXiv)

Deep Q-Networks algorithm (DQN) was the first reinforcement learning algorithm using deep neural network to successfully surpass human level performance in a number of Atari learning environments. However, divergent and unstable behaviour have been long standing issues in DQNs. The unstable behaviour is often characterised by overestimation in the Q-values, commonly referred to as the overestimation bias. To address the overestimation bias and the divergent behaviour, a number of heuristic extensions have been proposed. Notably, multi-step updates have been shown to drastically reduce unstable behaviour while improving agent's training performance. However, agents are often highly sensitive to the selection of the multi-step update horizon (n), and our empirical experiments show that a poorly chosen static value for n can in many cases lead to worse performance than single-step DQN. Inspired by the success of n-step DQN and the effects that multi-step updates have on overestimation bias, this paper proposes a new algorithm that we call `Elastic Step DQN' (ES-DQN). It dynamically varies the step size horizon in multi-step updates based on the similarity of states visited. Our empirical evaluation shows that ES-DQN out-performs n-step with fixed n updates, Double DQN and Average DQN in several OpenAI Gym environments while at the same time alleviating the overestimation bias.