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

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. We believe that our work opens a new door for mitigating the overestimation bias of Q-learning.

Improvements to AI systems:

1. Bias-controllable Q-learning for large action spaces – Implement a new Q-learning variant where the data-sharing fraction between two Q-functions is a tunable hyperparameter. This allows the system to continuously adjust its estimation bias from negative (underestimation) to positive (overestimation), enabling task-specific calibration (e.g., conservative bias for safety-critical tasks, optimistic bias for exploration-heavy tasks).

2. Semi-decoupled action selection with intersection – Replace fully coupled or fully decoupled Q-functions with an action-intersection mechanism. The system maintains two Q-functions, but for shared trajectory samples, it updates them jointly (coupling); for non-shared samples, it updates them independently (decoupling). This reduces both the positive bias of coupling and the negative bias of decoupling, yielding more stable value estimates in high-dimensional action spaces (e.g., robotics, combinatorial optimization).

3. Fine-grained bias control via action-set intersection size – Add a new control knob: the size of the action intersection set. By shrinking or expanding this set, the system can achieve arbitrarily fine adjustments to the bias range, allowing precise trade-offs between overestimation and underestimation without retraining the core architecture.

4. Randomness-aware value estimation – Incorporate a mechanism that detects high randomness in Q-value estimates (e.g., variance across actions) and automatically adjusts the intersection fraction. This makes the system adaptive to action-space complexity, improving robustness in non-stationary or partially observable environments.

What the improved AI system can do:

• Achieve superior performance in large-action-space tasks (e.g., recommendation systems, autonomous navigation, game playing with many discrete actions) by reducing the harmful overestimation bias that leads to suboptimal policies.

• Tune its own exploration–exploitation balance by setting the bias direction (positive or negative) via a single parameter, without changing the learning algorithm.

• Maintain stable learning even when the action space grows dynamically (e.g., adding new items in a catalog) by adjusting the intersection size on the fly.

• Outperform state-of-the-art deep RL baselines (e.g., Double DQN, TD3, SAC) in terms of final returns and sample efficiency, as demonstrated in the paper’s experiments.

• Provide interpretable bias control for practitioners: they can explicitly choose to underestimate values (safer for real-world deployment) or overestimate (for faster initial exploration) based on domain requirements.