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.
Introduction
Standard Q-learning relies on the max operator to estimate future rewards. However, this operator is non-differentiable and prone to the overestimation phenomenon, where noise in value estimates leads to a positive bias that can cause training to diverge or settle on suboptimal policies.
While previous "softmax" operators like Mellowmax were designed to be differentiable and non-expansive (ensuring convergence), they suffer from two main drawbacks: oversmoothing, where action values are aggregated without considering the actual policy probability, and hyperparameter sensitivity, requiring painstaking per-environment tuning. Additionally, this overestimation problem is amplified in Multi-Agent Reinforcement Learning (MARL), where the joint action space grows exponentially with the number of agents.
The Soft Mellowmax (SM2) Operator
The proposed Soft Mellowmax (SM2) operator is a weighted quasi-arithmetic mean defined as:
$$sm_\omega Q(s, \cdot) = \frac{1}{\omega} \log \left[ \sum_{i=1}^n soft_\alpha(Q(s', a_i)) \exp(\omega Q(s', a_i)) \right]$$
Key features of SM2 include:
- Policy Weighting: Unlike standard Mellowmax, SM2 uses a softmax term ($soft_\alpha$) to weight action values based on their relative importance (policy probability), preventing oversmoothing.
- Theoretical Soundness: The SM2 Bellman operator is a contraction mapping, ensuring convergence to a unique fixed point with explicit performance bounds relative to the true optimal $Q^*$.
- Robustness to Tuning: SM2 is significantly less sensitive to its hyperparameters ($\alpha$ and $\omega$) than Mellowmax. In many tests, a single set of parameters worked well across all scenarios.
Experimental Evaluation
The researchers evaluated SM2 across diverse benchmarks:
- Single-Agent RL: Games from the PyGame Learning Environment (PLE) (Catcher, Pixelcopter, Pong) and MinAtar (Asterix).
- Multi-Agent RL: The StarCraft Multi-agent Challenge (SMAC), using scenarios like
3m,8m,3s5z, and2s_vs_1sc.
Key Results
Bias Reduction
Empirical tests confirmed that SM2 effectively reduces the overestimation of Q-values compared to standard DQN, leading to more accurate target estimates during training. As shown in the comparison of estimated Q-values, SM2 (red) maintains significantly lower and more stable estimates than the standard DQN and DDQN baselines.
Performance and Stability
In single-agent tasks, SM2 consistently achieved higher average returns and lower variance than DQN, Double-DQN (DDQN), and Mellowmax-DQN. When applied to SMAC, SM2 outperformed state-of-the-art algorithms like QMIX, VDN, and COMA, showing particularly strong results in difficult maps where standard QMIX often falls into suboptimal local minima.
Conclusion
SM2 provides a robust, theoretically grounded alternative to the max operator in Q-learning. By bridging the gap between mean and max through controlled smoothing, it mitigates overestimation bias and stabilizes training in both single-agent and complex multi-agent environments. Future work includes exploring automatic dynamic tuning of the $\alpha$ and $\omega$ parameters to further enhance performance.
Summary updated