Stabilizing Q Learning Via Soft Mellowmax Operator

Yaozhong Gan, Zhe Zhang, Xiaoyang Tan

Presented at AAAI 2021, this research introduces a novel mathematical operator designed to stabilize Reinforcement Learning (RL) by addressing one of its most persistent challenges: overestimation bias.

The Overestimation Problem in Q-Learning

In standard Q-learning, the max operator is used to estimate future rewards. However, because max is non-differentiable and highly sensitive to noise, it frequently leads to overestimation bias. This occurs when an agent perceives certain actions as significantly more valuable than they truly are, resulting in unstable training and suboptimal policies.

While previous smoothing techniques like Mellowmax were developed to mitigate this, they often suffer from "oversmoothing"—treating all actions as equally likely and producing overly pessimistic estimates—and extreme hyperparameter sensitivity.

Figure 4: Q-value estimates in Catcher-PLE. Standard DQN and DDQN show significantly higher (overestimated) values compared to SM2 and other smoothed variants.

This overestimation problem is further compounded in Multi-Agent Reinforcement Learning (MARL), where the presence of multiple agents causes estimation errors to scale proportionally with the team size.

The Soft Mellowmax (SM2) Operator

The authors propose the Soft Mellowmax (SM2) operator, a differentiable alternative to the standard max operator. It is defined as:

$$sm_\omega Q(s, \cdot) = \frac{1}{\omega} \log \sum_{i=1}^n soft_\alpha(Q(s', a_i)) \exp(\omega Q(s', a_i))$$

Key Innovations

  • Weighted Aggregation: Unlike the original Mellowmax, which uses a simple average, SM2 incorporates a "soft" policy term ($soft_\alpha$). This term acts as a weight, prioritizing actions that the current policy deems important, thereby preventing the oversmoothing issue.
  • Convergence Guarantees: The authors provide theoretical proof that SM2 is a contraction mapping, ensuring it converges to a unique fixed point. They also derive performance bounds relative to the true optimal value.
  • MARL Scalability: The operator was integrated into the QMIX framework for multi-agent settings, replacing the standard max-operator in target value calculations to improve stability in complex environments like StarCraft.

Experimental Results

The SM2 operator was evaluated across single-agent environments (PyGame Learning Environment and MinAtar) and multi-agent scenarios (StarCraft Multi-Agent Challenge).

Figure 2: Average return across various single-agent environments. SM2 (red) consistently achieves higher or more stable returns compared to DQN, DDQN, and other variants.

Key Findings

  • Superior Performance: In single-agent tasks, SM2 consistently outperformed DQN and Double DQN (DDQN). For instance, in Pixelcopter, SM2 achieved a mean return of 40.11, significantly higher than DQN's 25.95.
  • Overcoming Suboptimal Plateaus: In the StarCraft 2s_vs_1sc map, standard QMIX often plateaus at a ~20% win rate. SM2-QMIX successfully escaped this local optimum, reaching a win rate near 95%.
  • Robustness: SM2 proved much less sensitive to hyperparameters than its predecessors. A single set of parameters ($\alpha=10, \omega=5$) was effective across nearly all tested StarCraft maps.
  • Reduced TD Error: Quantitative analysis confirmed that SM2 leads to lower and more stable Temporal Difference (TD) errors, indicating more accurate target value estimation during training.

Conclusion

By weighting the Mellowmax operator with action probabilities, SM2 retains the smoothness necessary for stability while maintaining the "ambition" of the max operator. While future work may explore adaptive temperature tuning to further reduce manual parameterization, SM2 currently offers a robust and theoretically grounded method for improving the reliability of both single and multi-agent reinforcement learning.

Summary updated

Abstract

Learning complicated value functions in high dimensional state space by function approximation is a challenging task, partially due to that the max-operator used in temporal difference updates can theoretically cause instability for most linear or non-linear approximation schemes. Mellowmax is a recently proposed differentiable and non-expansion softmax operator that allows a convergent behavior in learning and planning. Unfortunately, the performance bound for the fixed point it converges to remains unclear, and in practice, its parameter is sensitive to various domains and has to be tuned case by case. Finally, the Mellowmax operator may suffer from oversmoothing as it ignores the probability being taken for each action when aggregating them. In this paper, we address all the above issues with an enhanced Mellowmax operator, named SM2 (Soft Mellowmax). Particularly, the proposed operator is reliable, easy to implement, and has provable performance guarantee, while preserving all the advantages of Mellowmax. Furthermore, we show that our SM2 operator can be applied to the challenging multi-agent reinforcement learning scenarios, leading to stable value function approximation and state of the art performance.
BibTeX
@inproceedings{gan2021stabilizing,
  author = {Yaozhong Gan and Zhe Zhang and Xiaoyang Tan},
  title = {{Stabilizing Q Learning Via Soft Mellowmax Operator}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2021},
  url = {https://openreview.net/forum?id=ARKrl8spjC},
}
Figure