Source-linked AI summary
Maxmin Q-learning: Controlling the Estimation Bias of Q-learning
Qingfeng Lan, Yangchen Pan, Alona Fyshe, Martha White
TL;DR
Q-learning can overestimate values because it takes maxima over noisy estimates, while the performance impact of bias depends on the environment. The paper introduces Maxmin Q-learning to control bias through multiple estimators and reports theoretical, convergence, and empirical support for the approach.
Problem
Q-learning suffers from overestimation bias, and the relationship between estimation bias, learning performance, and existing mitigation methods is not fully understood.
Method
Maxmin Q-learning maintains multiple action-value estimators and uses their minimum in the Q-learning target, with N controlling the bias.
Results
Maxmin Q-learning controls bias across environments and achieves comparable or better performance, becoming more stable than competing methods as Mountain Car reward variance increases.
Takeaways & Limitations
Choosing the number of estimators allows Maxmin Q-learning to trade off learning speed, exploration, estimation bias, and final performance across environments.
Takeaways & Limitations
The theoretical analysis assumes estimator errors follow a uniform distribution, with the error scale depending on samples shared among estimators.
Abstract
from arXiv · showhide
Q-learning suffers from overestimation bias, because it approximates the maximum action value using the maximum estimated action value. Algorithms have been proposed to reduce overestimation bias, but we lack an understanding of how bias interacts with performance, and the extent to which existing algorithms mitigate bias. In this paper, we 1) highlight that the effect of overestimation bias on learning efficiency is environment-dependent; 2) propose a generalization of Q-learning, called \emph{Maxmin Q-learning}, which provides a parameter to flexibly control bias; 3) show theoretically that there exists a parameter choice for Maxmin Q-learning that leads to unbiased estimation with a lower approximation variance than Q-learning; and 4) prove the convergence of our algorithm in the tabular case, as well as convergence of several previous Q-learning variants, using a novel Generalized Q-learning framework. We empirically verify that our algorithm better controls estimation bias in toy environments, and that it achieves superior performance on several benchmark problems.
1 INTRODUCTION
Q-learning’s simple maximum-based update is vulnerable to overestimation bias, especially with many actions and function approximation. Existing variants reduce or redirect this bias, motivating Maxmin Q-learning as a flexible control mechanism.
- Q-learning: Q-learning updates action-value estimates toward the observed reward plus the estimated maximal next-state action value.The update target represents the highest value the agent estimates it could obtain.
- Overestimation bias: Maximum selection can overestimate value because stochasticity or estimator errors make at least one action estimate misleadingly large.The problem becomes more likely as the number of actions increases.
- Overestimation bias: Overestimation bias can substantially impair learned policies under function approximation and can even cause Q-learning failure.
- Existing methods: Double Q-learning uses two independent estimators to avoid overestimation, but its expected selected value is biased toward underestimation.Double DQN has nevertheless been shown to improve performance over Q-learning.
- Existing methods: Weighted, bias-corrected, ensemble, averaged, and actor-critic methods offer additional ways to reduce overestimation, while theoretical guidance remains incomplete.In particular, applying a minimum operator and choosing the number of estimators lack rigorous theoretical guidance in the cited actor-critic example.
- Maxmin Q-learning: Maxmin Q-learning controls estimation bias from positive to negative, with theoretical, convergence, and empirical analyses spanning tabular, neural-network, and benchmark settings.The method uses minimization over multiple action-value estimates and extends to Maxmin DQN.
2 PROBLEM SETTING
The paper formulates reinforcement learning as an MDP and describes Q-learning as an off-policy method for learning optimal state-action values. Its greedy policy selects actions with maximal learned value, and the tabular algorithm is known to converge under stated coverage conditions.
- MDP formulation: An MDP consists of states, actions, transition probabilities, rewards, and a discount factor, with policies maximizing expected return from an initial state.
- Q-learning: Q-learning is an off-policy algorithm that learns state-action values for the optimal policy.
- Optimal policy: The optimal policy acts greedily by selecting an action from arg max_a∈A Q*(s, a).
- Convergence: Q-learning updates can use transitions generated by any behavior sufficiently covering the state space, and the tabular algorithm is known to converge.The passage notes only limited convergence results for function approximation.
3 UNDERSTANDING WHEN OVERESTIMATION BIAS HELPS AND HURTS
Overestimation and underestimation can help or hurt depending on how stochasticity aligns with value in the environment. Experiments in a simple MDP support this environment-dependent effect and motivate flexible bias control.
- Motivation: The paper reports that either overestimation or underestimation bias may improve learning performance depending on the environment.
- Motivation: Maxmin Q-learning is motivated as a way to flexibly control estimation bias while reducing estimation variance.
- Mechanism: The maximum target is overestimated because noisy action-value estimates can include positive errors, making their maximum exceed the maximum expected value.Formally, E[max_a′ Q(s′,a′)] ≥ max_a′ E[Q(s′,a′)].
- Environment dependence: Overestimation can encourage exploration of stochastic high-value regions, but it can also cause over-exploration of stochastic low-value regions.Underestimation may discourage exploration or prevent discovery of high-value regions.
- Toy MDP: In the toy MDP, positive µ makes the stochastic region high-value, whereas negative µ makes it low-value, reversing which bias is expected to help.
- Toy MDP results: For µ = +1, Q-learning learns the optimal policy fastest while Double Q-learning underestimates too much; for µ = −1, Double Q-learning is fastest and larger-N Maxmin Q-learning follows.All methods reach the optimal policy for µ = −1, while Maxmin Q-learning progresses toward it for N = 2, 4, 6, 8 when µ = +1.
4 MAXMIN Q-LEARNING
Maxmin Q-learning generalizes Q-learning by maintaining multiple action-value estimates and taking their minimum before the next-state maximum, allowing the number of estimators to control estimation bias and variance.
- Algorithm: Maxmin Q-learning maintains N action-value functions and uses max_a′ min_i Q_i(s′, a′) in the Q-learning target.For N = 1, it reduces to Q-learning; increasing N moves the estimator from overestimation toward underestimation.
- Algorithm: The method uses experience replay and random subsamples or mini-batches so multiple estimators receive approximately independent data.A random estimator can be updated per step, and target networks can be added to obtain Maxmin DQN.
- Bias analysis: Theorem 1 expresses the expected estimation bias as E[Z_MN] = γτ[1 − 2t_MN], where t_MN depends on the number of actions M and estimators N.The theorem assumes all actions share the same true action-value and uses the approximation-error model specified in the analysis.
- Bias analysis: Under uniform random approximation errors, the expected bias decreases as N increases and can switch from positive to negative.An appropriate choice satisfying t_MN ≈ 1/2 can reduce the bias to near zero.
- Variance analysis: The variance of the minimum estimator decreases as N increases, and a suitable N can yield lower variance than a single estimator using all samples.The comparison accounts for samples being divided among estimators; under the stated analysis, the maxmin estimator can still have lower variance.
- Experiments: On Mountain Car, the four algorithms were compared across reward variances, with results averaged across 100 runs and standard errors reported.The figure reports last-episode steps and, at σ2 = 10, training steps to reach the goal; additional higher-variance experiments appear in Appendix C.2.
5 EXPERIMENTS
Experiments evaluate robustness to reward variance in Mountain Car and performance across seven benchmark games. Maxmin methods become more stable under high reward variance and can trade slower early learning for better final performance.
- Mountain Car: At σ = 50, Q-learning and Averaged Q-learning failed to reach the goal within 5,000 steps, while Double Q-learning produced runs exceeding 400 steps.At low reward variance, the four methods had comparable performance; instability increased for the other methods as variance rose.
- Mountain Car: Maxmin Q-learning remained more stable than Q-learning, Double Q-learning, and Averaged Q-learning as Mountain Car reward variance increased.The experiment averaged results over 100 runs and measured steps to reach the goal in the final training episode.
- Benchmark environments: Maxmin DQN performed as well as or better than other algorithms across seven benchmark environments.The evaluation covered Lunarlander, Catcher, Pixelcopter, Asterix, Seaquest, Breakout, and Space Invaders, averaging results over 20 runs.
- Benchmark environments: In Pixelcopter, Lunarlander, and Asterix, better final performance coincided with slower initial learning, possibly because Maxmin DQN explored more extensively early on.For Pixelcopter and Asterix, smaller N learned faster but reached suboptimal performance, whereas larger N learned more slowly and reached better final performance.
6 CONVERGENCE ANALYSIS OF MAXMIN Q-LEARNING
The paper introduces Generalized Q-learning, whose bootstrap target applies a function G to multiple action-value estimates while preserving relative maximum values. This framework establishes tabular convergence for Maxmin Q-learning and several existing variants under stated assumptions.
- Generalized Q-learning: Generalized Q-learning defines a common framework in which the bootstrap target uses a function G of N action-value estimates.The framework is designed to encompass Q-learning variants that differ in their one-step bootstrap target.
- Generalized Q-learning: The main condition on G is that it maintains relative maximum values across the action-value estimates.This condition is formalized as Assumption 1.
- Special cases: Different choices of G, N, and K recover Q-learning, Double Q-learning, Ensemble Q-learning, Averaged Q-learning, and Historical Best Q-learning as special cases.Historical Best Q-learning uses the largest action value among estimates from up to K previous updates, with convergence guaranteed under the framework.
- Convergence theorem: Under Assumptions 1 and 2, tabular Generalized Q-learning converges to the optimal action-value function with probability 1 for finite MDPs.The theorem covers γ < 1, or γ = 1 under additional absorbing-state and proper-policy conditions.
- Convergence theorem: Because Maxmin Q-learning satisfies Assumption 1, Theorem 2 proves its convergence in the tabular setting.The same theorem is then applied to Q-learning and its variants.
7 CONCLUSION
The paper concludes that Maxmin Q-learning flexibly controls estimation bias through the number of action-value functions, while reducing bias and variance for appropriate choices. It also establishes convergence through a Generalized Q-learning framework and reports empirical advantages in noisy toy problems and benchmark environments.
- Conclusion: Maxmin Q-learning controls overestimation or underestimation bias by choosing the number N of action-value functions according to the environment.The paper links this flexibility to improved learning efficiency and reports reduced estimation bias and variance for an appropriate N.
- Conclusion: The Generalized Q-learning framework proves convergence for Maxmin Q-learning and several other variants that use multiple action-value estimates.The conclusion identifies this framework as the basis for the tabular convergence results.
- Conclusion: Experiments report advantages for Maxmin Q-learning on reward-noise toy problems and several benchmark environments.The conclusion summarizes the empirical evidence as supporting better bias control and performance.
A THE PROOF OF THEOREM 1
The proof uses order-statistics properties to characterize how Maxmin Q-learning’s estimator changes with the number of estimators. It establishes decreasing bias and variance, and shows that suitable choices can approach zero bias while reducing variance.
- Order-statistics tools: Order-statistics lemmas characterize the distributions and moments of minima and maxima formed from independent action-value estimates.The proof derives CDFs, PDFs, expectations, and variances for these order statistics.
- Bias analysis: The expected Maxmin estimate decreases with N, moving from the single-estimator case toward a more negative bias under the uniform-noise model.The proof states E[Z_M,N=1] = γτ(M−1)/ (M+1) and that the expectation decreases as N increases.
- Bias-variance trade-off: For each action count M, an estimator count N can make the absolute expected estimation bias close to 0 while also reducing estimation variance.This is the stated bias-variance trade-off supported by the empirical results in Figure 5.
- Variance comparison: Under uniform random noise, Maxmin Q-learning has lower variance than the single-estimator Q-learning baseline when N ≥8.The comparison assumes evenly allocated samples among estimators and uses the variance relation derived in the corollary.
B.2 KEY LEMMAS AND THE PROOFS
The key lemmas establish contraction and bounded-noise properties for the Generalized Q-learning operator. These properties support almost-sure convergence under discounted or suitable undiscounted MDP conditions.
- Contraction lemmas: The Generalized Q-learning operator is a contraction under the stated assumptions, including in the maximum norm for the discounted case.For undiscounted problems, contraction can instead be established in a weighted norm when all policies are proper.
- Undiscounted case: For undiscounted problems, the analysis uses an absorbing reward-free state and assumes all policies are proper to obtain the required contraction.The absorbing-state initialization sets the corresponding action values to zero.
- Generalized iteration: The convergence framework models updates as noisy asynchronous fixed-point iterations with step sizes, potentially outdated components, and history-dependent update decisions.The update equation includes a step-size coefficient, a noise term, and possibly stale coordinates of the iterate.
- Stochastic assumptions: The assumptions require zero conditional-mean noise, appropriate measurability, bounded noise conditions, and update decisions that do not anticipate future noise.These conditions formalize the stochastic approximation setting used by the convergence theorems.
B.4 PROOF OF THEOREM 2
Theorem 2 applies the Generalized Q-learning convergence framework to finite MDPs. Under the stated assumptions, the tabular action-value estimates converge almost surely to the optimal action-value function.
- Theorem 2: In a finite MDP, Generalized Q-learning with tabular updates converges to the optimal action-value function with probability 1.The theorem covers the cases listed in the subsequent conditions.
- Discounted case: The convergence result applies directly when the discount factor satisfies γ < 1.This is the discounted case in the theorem’s conditions.
- Undiscounted case: For γ = 1, the result applies when the initialized absorbing state is reward-free and all policies are proper.These conditions provide the undiscounted setting required by the framework.
- Proof strategy: The proof verifies the generalized stochastic-approximation assumptions and then invokes Theorem 5 to conclude convergence.The step-size requirement includes infinitely many simulations of every state-action pair, and outdated information is permitted under the assumptions.
C.1 MDP RESULTS
The MDP experiments compare algorithms on a simple MDP and Mountain Car under varied reward settings. The reported results use repeated-run averages, with some algorithms failing to reach the Mountain Car goal under high reward variance.
- Simple MDP: The simple-MDP comparison evaluates three algorithms for µ = +0.1 and µ = −0.1 using learning curves for Q(A, Left).The true action value is respectively +0.1 and −0.1, and results are averaged over 5,000 runs.
- Mountain Car: Mountain Car experiments compare four algorithms under different reward settings, with all results averaged over 100 runs.The passage reports the experimental design but does not provide the complete learning-curve outcomes.
- Mountain Car: For reward variance σ^2 = 50, Q-learning and Averaged Q-learning fail to reach the goal position within 5,000 steps.Consequently, their learning curves are omitted for that reward setting.
C.3 BENCHMARK ENVIRONMENT RESULTS
Sensitivity analysis evaluates the four algorithms DQN, DDQN, Averaged DQN, and Maxmin DQN across seven benchmark environments. The supplied passages identify the analysis and compared methods but do not report its outcome.
- Seven benchmark environments are included in the sensitivity analysis.
- The compared methods are DQN, DDQN, Averaged DQN, and Maxmin DQN.
- Figure 8 presents the sensitivity analysis results for the benchmark environments.