Revisiting Overestimation Bias Problem of Q-learning: Settling Large Discrete Action Space via Action Intersection

arXiv 2608.12912 ↗First posted 13 Aug 2026cs.LGcited by 0

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

This paper considers the overestimation bias problem of Q-learning in the setting of a large action space, for the purpose of relieving the bottleneck of existing methods. We find that the large action space increases the randomness in Q-value estimation. The randomness makes two paradigms that drive the major literature on the overestimation problem have their own bottlenecks: the coupling paradigm, i.e., the optimal action and its Q-value are estimated with the same Q-function, always has a positive bias. This is because randomness leads to some actions having abnormally high estimated values than their true values, and the coupling methods prefer these actions. The decoupling paradigm, i.e., the optimal action and its Q-value are estimated with two independent Q-functions, always has a negative bias. This is because randomness increases the estimation gap between the two independent Q-tables for the same action. This paper shows that action intersection can be a simple yet powerful strategy to relieve these bottlenecks. The action intersection strategy enables semi-decoupling via two designs: (1) it allows two Q-functions to share a certain fraction of trajectory data; (2) if a data sample is shared, each Q-function is updated using the coupling paradigm; otherwise, using the decoupling paradigm. Two properties make the action intersection strategy powerful: (1) attaining a large bias range, i.e., varying the data sharing fraction, the estimation bias varies from underestimating to overestimating; (2) fine granularity: the action intersection size can be made arbitrarily finer to enable finer control. We consider two experiment settings, i.e., tabular and deep RL, deep RL experiments show that our method outperforms several SOTA baselines drastically; tabular experiments reveal why our method can achieve superior performance.

Key facts. No citing papers in the map yet (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 14 of its 29 references that are in the map. First posted on arXiv 13 Aug 2026.

Builds on

14 of 29 references.

References · 14

2013Playing Atari with Deep Reinforcement Learningcited by 3,274
2021Randomized Ensembled Double Q-Learning: Learning Fast Without a Modelcited by 288
2024From r to Q^*: Your Language Model is Secretly a Q-Functioncited by 242
2016Sample Efficient Actor-Critic with Experience Replaycited by 188
2015Deep Reinforcement Learning in Large Discrete Action Spacescited by 161
2020Maxmin Q-learning: Controlling the Estimation Bias of Q-learningcited by 117
2016Averaged-DQN: Variance Reduction and Stabilization for Deep Reinforcement Learningcited by 106
2021Ensemble Bootstrapping for Q-Learningcited by 31
2018Sample Efficient Deep Reinforcement Learning for Dialogue Systems with Large Action Spacescited by 15
2020Exact Reduction of Huge Action Spaces in General Reinforcement Learningcited by 10
2023Adaptive Ensemble Q-learning: Minimizing Estimation Bias via Error Feedbackcited by 9
2021Action Candidate Based Clipped Double Q-learning for Discrete and Continuous Action Taskscited by 7

2 more

2021On the Estimation Bias in Double Q-Learningcited by 4
2022M2DQN: A Robust Method for Accelerating Deep Q-learning Networkcited by 1

Built on by

Not cited yet.

Similar, not cited

Close in wording, no citation either way