- 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 estimators for each action, the authors quantify the estimation bias in terms of , which is the number of estimators used for action selection, when the full set of estimators is used for action evaluation. Therefore, 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 , while treating as continuous for which their 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 at which the bias is zero. They define a Signal-to-Noise Ratio (SNR), established in the two action setting, given by , that is the difference between the means of the two actions for which 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 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 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, 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 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
-
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.
-
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 , 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 and subsets overlapping at the "middle 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 . Should the interval not only be considered in the range , since is the smallest value can take? Therefore, why was chosen for the lower endpoint of the interval of ?
Q3. Something you also mention in lines 315-317 made me curious. With the reference action being selected from the full ensemble and then being used as the comparison across the ensemble, can suffer from an underestimation bias, which results in an overestimated 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
- 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 case could resolve that.
- In Lemma 1: since estimation bias is a function of the dependency should be given in the Equation of and the to make the dependency explicit.
- In Proposition 3: is used without being introduced.
- In Theorem 1: currently has no floor on possible values that can be chosen.
- Line 134-135: "...where satisfied..." is missing in
- In Lemma 2: Here is used as the cardinality of the number of actions, in Lemma 1 is the number of actions.
- Line 292: is introduced to be and never carries a different value. Instead could be used directly.
- 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 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?
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 M predictors. For a fixed action under our independent, equal-variance model, averaging m predictors gives variance σ2/m. Assigning heads exclusively to selection leaves fewer estimates for evaluating that action. SOQ therefore keeps all M 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=1. Proposition 1 takes the limit N→0+ only for the continuous extension of the bias formula. The bias is negative in this limit and positive at N=M, which establishes a zero crossing in (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).
We also clarified that Δ denotes the total action-value gap. For two actions this is μ1−μ2. For K equally spaced action values, the adjacent gap is Δ/(K−1).