acceptodds
Under review as a conference paper at ICLR 2027

Controlling the Overestimation Bias of Q-learning From an Action-Selection and Action-Evaluation Overlap Perspective

Abstract

The well-known estimation bias causes Q-value estimates to be overestimated or underestimated, potentially impairing learning and policy performance. This bias is closely related to the sharing of Q-functions between action selection and value evaluation. However, existing methods lack a systematic analysis of how the sharing degree affects estimation bias, providing limited theoretical guidance for bias minimization across different settings. We formalize the sharing degree as the overlap between the Q-functions used for action selection and value evaluation, and analyze how this overlap affects estimation bias and should be chosen to minimize bias. Under the stated assumptions, we prove that the signed estimation bias is a monotonic function of this overlap, and that the bias-minimizing overlap is governed by the signal-to-noise ratio (SNR). Motivated by this finding, we propose Selective-Overlap Q-learning (SOQ). SOQ uses all Q-functions for value estimation and selects a Q-function subset for action selection according to a state-dependent proxy for SNR, aiming to approximate the bias-minimizing overlap and reduce estimation bias. By adapting the overlap between action selection and value evaluation, SOQ improves the reliability of Q-value estimation across different settings.

Primary area:
reinforcement learning
Keywords:
Reinforcement learning, Q-learning, Estimation bias

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_xHqbOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper tackles the topic of overestimation bias in Q-learning, a topic that is of interest for RL research and a wide range of methods and approaches exist on how to tackle and reduce the bias. In Q-learning two tasks are carried out by the Q-function, that is, it is used to evaluate actions in states and it is used to select new actions during the update step. Sharing the Q-function between these two steps (Watkins' Q-learning and its DQN variants, etc.) tends to result in overestimation bias whereas separating both tasks into separate Q-functions (Hasselt's Double Q-Learning, etc.) tends to cause an underestimation bias. From this observation the authors conclude that both, over- and underestimation biases relate to a shared underlying mechanism based on how much sharing of Q-function(s) is done by action evaluation and action selection. Intuitively speaking, many of the existing methods treat the symptoms of this effect, that is, they tackle over- and/or underestimation biases.

This work's goal is to identify the root cause of both biases, provide an analysis, and then provide an approach that tackles the estimation bias problem at the root. To that end they connect the bias to the level of overlap present between the set of Q-functions that select actions and the set of Q-functions that evaluate actions. This analysis of the bias is initially conducted in the setting of an independent, equal-variance Gaussian error model with two actions and then extended into a setting with more actions of equally spaced expected rewards. The limitation of using this constructed environment is stated as such in their discussion of limitations, Section 5.

In the first step, using the two-action setting and assuming a set of MM estimators for each action, the authors quantify the estimation bias in terms of N∈[1,M]N\in[1,M], which is the number of estimators used for action selection, when the full set of MM estimators is used for action evaluation. Therefore, NN quantifies their notion of the overlap, as explained above, and establishes the relation to the resulting bias. This is followed by an evaluation of the bias levels of N∈[0,M]N\in[0,M], while treating NN as continuous for which their bias(N)\text{bias}(N) mapping is monotonically increasing. In Proposition 1, they show that over this range the bias goes from underestimation at the left endpoint to overestimation at the right endpoint, which implies a value of NN at which the bias is zero. They define a Signal-to-Noise Ratio (SNR), established in the two action setting, given by ε=(μ1−μ2)/σ\varepsilon=(\mu_{1}-\mu_{2})/\sigma, that is the difference between the means of the two actions for which μ1>μ2\mu_{1}>\mu_{2} and the shared standard deviation. They then connect the SNR to the bias in Proposition 2 that suggests using smaller overlap for low values of SNR and larger overlap for high values. This is an important step because it paves the way to how the algorithm the paper introduces in Section 3.3 controls the level of overlap that minimizes the bias.

The second step is motivated by the fact that the just-established SNR is not observable during training and therefore not usable to control the level of overlap. This is why the authors introduce the Signal Coverage Ratio (SCR) in the second setting with multiple actions of evenly spaced expected rewards. The SCR is the sum over the probabilities that any action has a higher Q-value than that of the optimal action. SCR can be connected to the SNR and is strictly decreasing in the SNR. This connection between SCR and SNR justifies the usage of the SCR instead of the unobservable SNR for use in the proposed Q-learning method. Since the optimal action is also not available during training, they introduce an estimator for the SCR that can be obtained during training as the average across all actions of the mean count of Q-values that are larger than the Q-value of the reference action. The reference action is the action that maximizes the Q-values of the current ensemble average.

Using this SCR proxy the authors introduce their Q-learning method named "Selective-Overlap Q-learning". It is based on an ensemble of MM Q-tables that are selected uniformly at random to be updated to be updates. For the update step, their method computes the estimated SCR value based on which an overlap value N∈[1,M]N\in[1,M] is chosen by a controller that maps the range of the SCR into the range of possible overlaps. Based on the overlap decision of the controller, NN indices are randomly chosen to be the "action selection ensemble" based on which the greedy action for the Bellman update step is chosen. This action is then evaluated with the full ensemble of MM tables to construct the Bellman target for the Q-value update. The paper then establishes almost sure convergence of this method to the optimal Q-function in the discounted infinite horizon setting.

The work provides a range of experiments, across tabular environments, function approximation environments, and continuous-action environments to show that their method does reduce estimation bias and promises to increase aggregate reward learning performance.

Critical strengths
  1. Directly targeting the root cause of the biases instead of treating the symptoms is a desirable approach to dealing with undesired effects. Further, their method and findings are intuitive in their goals and effects. Interpolation between the two end-points of single-Q-function Q-learning and Double Q-learning through overlap connects their idea with other existing methods.

  2. The paper contains a wide range of experiments. The experiments range from the tabular setting, in which the theory and method were developed, to the function approximation setting of the Atari-10 environments, and also include an adaptation to the continuous-action setting of MuJoCo environments. The results are in line with what one would expect from bias reduction, that is, in general improved performance with some outliers where environments might benefit from the over- or underestimation bias of other methods [1].

[1] Lan et al. (2020) - "Maxmin Q-learning: Controlling the Estimation Bias of Q-learning"

Critical weaknesses

The notation should be improved. Objects are assigned to symbols and used before they are properly introduced and some parts of the notation, e.g., the Δ\Delta, are overloaded. While it is clear from the context what symbols are intended to be in the current scope, it would improve clarity, accessibility, and rigor to properly introduce notation and objects.

Questions for authors

Q1. Based on the different regimes of overlap, as presented in Figure 2, have you looked at partial overlaps that split the ensemble into three sets: Only action-selection, Overlap, and only action evaluation? That would be Figure 2(b) with the QAQ_{A} and QBQ_{B} subsets overlapping at the "middle NN Q-functions" and allow full interpolation between Figure 2(a) ME and Figure 2(b) CE.

Q2. In Proposition 1, the bias expression from Lemma 1 is viewed as continuous function of N∈[0,M]N\in[0,M]. Should the interval not only be considered in the range [1,M][1,M], since 11 is the smallest value NN can take? Therefore, why was 00 chosen for the lower endpoint of the interval of NN?

Q3. Something you also mention in lines 315-317 made me curious. With the reference action aˉN\bar{a}_{N} being selected from the full ensemble and then being used as the comparison across the ensemble, c^\hat{c} can suffer from an underestimation bias, which results in an overestimated UU which in turn makes the controller choose larger overlaps that increase overestimation tendencies. This would then be a weakened version of the initially introduced estimation bias coupling. Have you considered whether or not nesting your method could be useful, for example to eliminate the small, leftover overestimation bias in Figure 3(a), or is the effect likely to be absorbed by the rounding and clipping operation of the controller?

Details, Typos, and Nitpicks

  1. Is there a possible better name for the current use of "overlap"? Because in line with Figure 2 that goes from "Complete Overlap" (Q-learning) to "No Overlap" (Double Q-learning), the expected "Partial Overlap" to also include Q-functions that are only used for action selection. Maybe something like "Nesting Factor", but that would make the intuitive connection to the other methods and the general concept of the "overlap" less obvious. Maybe, depending on your response to my Q1, a short sentence on why the overlap is restricted to the QA⊆QQ_{A}\subseteq Q case could resolve that.
  2. In Lemma 1: since estimation bias is a function of NN the dependency should be given in the Equation of BiasOE(N)\text{Bias}^{OE}(N) and the z(N)z(N) to make the dependency explicit.
  3. In Proposition 3: η\eta is used without being introduced.
  4. In Theorem 1: γ\gamma currently has no floor on possible values that can be chosen.
  5. Line 134-135: "...where satisfied..." is missing in XaX_{a}
  6. In Lemma 2: Here KK is used as the cardinality of the number of actions, in Lemma 1 mm is the number of actions.
  7. Line 292: ρ\rho is introduced to be 12\frac{1}{2} and never carries a different value. Instead 12\frac{1}{2} could be used directly.
  8. Figure 4: The subplots (a) and (b) have no space between the label and the "index"; all the other figures always have one space between "index" and label.
2 comments

Thank you for the close reading of the estimator and its notation. Your questions helped us clarify why the evaluation ensemble stays fixed and how the continuous analysis relates to the algorithm's integer choices.

Q1. Why restrict selection to a subset of evaluation? What about selection-only, shared, and evaluation-only heads?

Your three-set construction would allow the selection and evaluation ensembles to become fully disjoint. We chose the nested construction for variance control under a fixed budget of MM predictors. For a fixed action under our independent, equal-variance model, averaging mm predictors gives variance σ2/m\sigma^2/m. Assigning heads exclusively to selection leaves fewer estimates for evaluating that action. SOQ therefore keeps all MM estimates in the evaluation average and varies the size of the selection subset. We added this rationale in Section 3.1.

Q2. Why use zero as the lower endpoint in Proposition 1 when the smallest subset has size one?

Yes, the smallest feasible subset size is N=1N=1. Proposition 1 takes the limit N→0+N\to0^+ only for the continuous extension of the bias formula. The bias is negative in this limit and positive at N=MN=M, which establishes a zero crossing in (0,M)(0,M). Section 3.1 now specifies the integer domain in the estimator definition and the continuous extension in the proposition.

Q3. Can reference-action coupling survive rounding and clipping, and could it explain the residual overestimation in Figure 3(a)?

It can survive both operations. In the near-tie experiment in Appendix G.4, we held the original ensemble fixed and selected the SCR reference action either from that ensemble or from an independent one. Across 100,000 paired draws, changing the reference changed the final integer subset size in 24.7% of cases with independent heads.

This supports the mechanism you describe and shows that a separate reference can reduce overestimation in a controlled setting. In practice, maintaining an independent reference ensemble would require additional computation and memory.

Notation and presentation (in the order raised).

  1. We retained overlap because it counts the predictors shared between selection and evaluation. Section 3.1 now explains why our estimator keeps the full evaluation set.
  2. Lemma 1 now writes the bias as a function of NN and uses zNz_N in the formula.
  3. Proposition 3 now introduces η≥0\eta\geq0 as a uniform bound on the one-step discrepancy.
  4. Theorem 1 now states 0≤γ<10\leq\gamma < 1.
  5. We corrected the sentence introducing the action outcome XaX_a in Section 3.1 and made the independence assumption explicit in Lemma 1.
  6. Lemma 1 now says “two actions” directly. Lemma 2 introduces KK for the general action count.
  7. The controller now uses the theoretical endpoint 1/21/2 directly. We removed the redundant parameter ρ\rho from the pseudocode and aligned the appendix notation.
  8. We corrected the spacing after (a) and (b) in Figure 4.

We also clarified that Δ\Delta denotes the total action-value gap. For two actions this is μ1−μ2\mu_1-\mu_2. For KK equally spaced action values, the adjacent gap is Δ/(K−1)\Delta/(K-1).

Thank you for the detailed response and for clarifying my questions.

However, one question regarding Q3 remains. I agree that a fully separate reference ensemble requires additional memory. A fully independent reference may also overcorrect, similar to Double Q-learning. This is why I was wondering whether nesting your own method onto the reference action selection would be useful, since it requires no additional memory or forward passes. Have you considered or tried such a variant?

Reviewer_UhcvOpenReview ↗
Rating
2
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper studies Q-value estimation bias through the overlap between estimators used for action selection and evaluation. Under a two-action, independent, equal-variance Gaussian model, it derives a bias expression, shows that signed bias increases with overlap, and relates the continuous zero-bias overlap to the signal-to-noise ratio. Selective-Overlap Q-learning (SOQ) uses the full ensemble for evaluation and adapts the selection subset using an empirical signal coverage ratio (SCR). The paper also establishes tabular convergence under the stated conditions. Validation includes tabular bias and control experiments, fixed-overlap and ensemble-size studies, an eight-head DQN implementation on Atari-10, and a TD3-based continuous-control extension. The reported Atari aggregate AUC improves over the compared baselines, while continuous-control results vary across tasks.

Critical strengths
  1. The overlap perspective is useful. The fixed-overlap analysis explains how bias changes. It also gives a clear reason to consider adaptation.
  2. The tabular convergence result adds theoretical support. The paper is clear that convergence does not guarantee good controller choices during learning.
  3. The experiments examine both bias and decision quality. They include ensemble baselines and signal/noise variations. The continuous-control results also show where the method struggles.
Critical weaknesses
  1. The empirical adaptation signal needs more validation. It uses the same ensemble to select the reference action and assess uncertainty. This may affect calibration.
  2. The deep experiments do not clearly isolate adaptation. Simpler subset rules, extra capacity, and target changes remain possible explanations for some gains.
  3. Task-to-task variation and computational cost need more discussion. I lean slightly negative for now. If convincing responses and comparisons resolve these concerns, I would consider raising my score.
Questions for authors
  1. Does empirical SCR track the best overlap choice when true values are known? Please consider near ties and correlated errors. Would an independently estimated reference action change the result?
  2. Could you compare adaptive, fixed, and random overlap under the same deep-RL setup? Matching critics and actors in continuous control would help. Please also clarify the runtime trade-off.
  3. Are the Atari gains consistent across games? Per-game improvements and a robust aggregate would help. Could the uncertainty estimates also include uncertainty in the DQN reference?
1 comment

Thank you for identifying three comparisons that would clarify the empirical case for SOQ. We added a known-value experiment, a controlled deep overlap ablation, and an Atari analysis that propagates uncertainty in the DQN reference.

Q1. Does empirical SCR track the best overlap near ties or with correlated heads? Would an independent reference help?

Appendix G.4 tests this directly with eight heads and two actions whose true values differ by 0.25σ0.25\sigma, where σ\sigma is the noise standard deviation of one head. We evaluate every fixed integer size from 1 to 8 against the known maximum and identify the size with the smallest absolute bias. On fresh draws, we change only the ensemble used to choose the SCR reference action. The original ensemble still computes SCR, selects the bootstrap action, and evaluates it.

\text{Head correlation} & 0 & 0.5 \\\\ \hline \text{Best fixed }N & 2 & 1 \\\\ \text{Mean }N\text{, SOQ} & 2.26 & 4.48 \\\\ \text{Mean }N\text{, independent reference} & 1.78 & 2.84 \\\\ \text{Signed bias, SOQ} & +0.0142 & +0.2783 \\\\ \text{Signed bias, independent reference} & -0.0055 & +0.2427 \\\\ \text{Signed bias, best fixed overlap} & -0.0049 & +0.2039 \\\\ \text{Signed bias, full overlap} & +0.0976 & +0.3092 \end{array}$$ Bias is reported in units of $\sigma$. With independent heads, the two mean overlap choices fall on either side of the best fixed size. With correlated heads, both rules miss the shift toward $N=1$. The independent reference reduces overestimation, but fixing $N=1$ gives the smallest bias in this condition. The controller does not explicitly estimate head correlation. **Q2. How do adaptive, fixed, and random overlap compare under a common deep setup, and what is the runtime trade-off?** Figure 6 compares five subset rules in the same eight-head MinAtar setup over six seeds and 3M decisions per run. $$\begin{array}{lrr} \text{Overlap rule} & \text{Seaquest} & \text{Space Invaders} \\\\ \hline \text{Adaptive} & 52.01 & 92.51 \\\\ \text{Fixed 1} & 36.17 & 64.94 \\\\ \text{Fixed 4} & 49.69 & 89.28 \\\\ \text{Fixed 8} & 33.74 & 79.90 \\\\ \text{Uniform random} & 42.59 & 83.87 \end{array}$$ The adaptive variant had the highest mean time-normalized AUC on both games, with fixed $N=4$ closest. For runtime, Table 1 reports end-to-end training throughput on Amidar. DQN, EBQL, and MINTO processed 565.2, 447.1, and 426.4 decision steps/s. SOQ processed 424.9 steps/s, 24.8% below DQN, 5.0% below EBQL, and 0.4% below MINTO. **Q3. Are gains consistent across games, and does the aggregate include DQN uncertainty?** SOQ had a higher mean AUC than DQN on seven of the ten games. The largest gains were on BattleZone (+374.4%) and Bowling (+136.7%), followed by Riverraid (+62.8%), Qbert (+45.2%), DoubleDunk (+8.3%), Phoenix (+4.1%), and NameThisGame (+2.1%). Mean AUC was lower on Amidar (−1.2%), KungFuMaster (−28.5%), and Frostbite (−30.1%). Figure 8 suggests that the unusually large AUC gain on BattleZone largely reflects how late DQN’s returns began to rise, with a much smaller relative gap by the end of training. Figure 5 now reports an equal-game-weight IQM. On a scale with the observed DQN IQM at 100, the indices are 122.0 for SOQ, 105.0 for MINTO, and 103.9 for EBQL. We resample seeds within each method and game and recompute every DQN reference in each of 50,000 bootstrap replicates. The SOQ-to-DQN IQM gain is **22.0% (95% interval 13.2% to 30.5%)**.
Reviewer_qNp2OpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
2
Soundness
1
Read review
Paper summary

The paper concerns a classic, well-known problem (i.e., bias reduction) in value-based RL methods, specifically Q-learning. It notes that when the same set of predictions are used for both choosing action and evaluation, it could introduce estimation bias. The paper provides some theoretical support to quantify this claim. The paper proposes to use a subset of predictors to decide which action to take for the bootstrap target, and asks the whole group to evaluate it. The selected subset's size is determined by balancing optimism and pessimism. Empirically evidence shows that it reduces bias in small controlled settings and improves performance on some Atari games.

Critical strengths

To my knowledge, though the bias issue is well-known in Q learning, the paper provides a somewhat new angle to study it. They also provide certain level of theoretical and empirical support for their proposed method.

Critical weaknesses
  1. The theoretical analysis considers a simplified model, which I think is fine. However, there are some critical gaps. The theoretical model uses independent Gaussian errors with equal variance and a fixed-size of subset predictors, but the implemented method changes the subset size and the predictors are correlated. The convergence theory proof's novelty is unclear, and is established in a tabular setting. Though I think a simplified setting itself is not a critical drawback, it does not show that the proposed adaptation reduces bias or improve convergence rate.

  2. Proposition 2 establishes a bias-minimization subset size for predictors, however, this does not justify the linear rule before rounding and clipping. The empirical uncertainty can be resulting from differences in predictors' value levels when they agree on action rankings.

  3. Ablation study is restricted to tabular problems. I think this is not enough, because there are some sensibly important changes in continuous-control variant. For example, it introduces another actor, different target averaging and replay updates, and additional critics. Without in-depth ablations on such domain, it is hard to claim that the proposed adaptation rule is the real source of benefit.

  4. I have doubts on the Atari games improvement. The improvements are normalized by each game's estimated DQN performance, and this might amplify those with small baseline scores, while the bootstrap holds those reference values fixed. The uncertainty in the reference scores are needed to be accounted for to support the reported gain.

Questions for authors

see above.

1 comment

Thank you for distinguishing the fixed-overlap analysis from the guarantees one might want for the adaptive algorithm. We address your four concerns in order.

Q1. What does the theory establish for the implemented method?

Theorem 1 establishes that adaptive overlap preserves convergence to the optimal Q-function in the tabular setting under the stated visitation, step-size, and update-index assumptions. It allows the controller to choose the subset size from the current ensemble and transition. The SOQ-specific step in the proof is to show that the tables reach consensus, so the discrepancy introduced by subset-based action selection vanishes. The theorem gives an asymptotic guarantee.

Our main theoretical contribution concerns the estimator itself. With independent, equal-variance Gaussian errors and a fixed subset size, Lemma 1 gives the signed bias explicitly, and Proposition 1 shows that it increases with overlap. Appendix G.4 now tests what carries over when the controller chooses the overlap and the heads are correlated. Near a tie, the controller tracks the best fixed size closely under independent errors but selects more heads under positive correlation.

Q2. Why use a linear rule, and what happens if predictors agree on rankings but differ in value level?

Proposition 2 characterizes the continuous zero-bias overlap at low signal-to-noise ratio. Together with the endpoint analysis, it motivates using a small overlap when actions are difficult to distinguish and allowing a larger one when their rankings are reliable. We use linear interpolation as the simplest mapping between those endpoints. Optimality of the interpolation at intermediate values is a separate question, which we investigate empirically in Appendix G.4.

Value-level differences can affect empirical SCR even when the heads agree on the best action. Fix the current predictions and suppose every head strictly prefers the same action. Averaging over any nonempty subset preserves that preference, whatever subset size SCR produces. The full ensemble then evaluates the same action in every case. Thus, in the case you describe, even an error in SCR that changes the subset size introduces no additional error in the resulting value estimate.

Q3. Do the deep experiments isolate the contribution of adaptation?

We added a controlled comparison on MinAtar (Figure 6). With eight heads, six seeds per method, and 3M decisions per run, we compared adaptive overlap with fixed subset sizes of 1, 4, and 8 and with uniformly sampled subset sizes. The adaptive variant had the highest mean AUC on both games. On Seaquest its AUC was 52.01, versus 49.69 for the best fixed size (N=4N=4) and 42.59 for random sizes. On Space Invaders the corresponding values were 92.51, 89.28, and 83.87.

Q4. Could unusually low DQN reference scores drive the Atari improvement?

BattleZone and Bowling had a substantial influence on the original arithmetic mean. We therefore revised Figure 5 to report the more robust interquartile mean (IQM).

All ten games receive equal weight. In each of 50,000 bootstrap replicates, we resample seeds within each method and game, recompute each game's DQN reference, and recompute both methods' IQMs. The resulting SOQ gain over DQN is 22.0% (95% bootstrap interval 13.2% to 30.5%).

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.