Revisiting the Softmax Bellman Operator: Theoretical Properties and Practical Benefits

Zhao Song, Ronald E. Parr, Lawrence CarinarXiv 2018 · OpenReview

Abstract

The impact of softmax on the value function itself in reinforcement learning (RL) is often viewed as problematic because it leads to sub-optimal value (or Q) functions and interferes with the contraction properties of the Bellman operator. Surprisingly, despite these concerns, and independent of its effect on exploration, the softmax Bellman operator when combined with Deep Q-learning, leads to Q-functions with superior policies in practice, even outperforming its double Q-learning counterpart. To better understand how and why this occurs, we revisit theoretical properties of the softmax Bellman operator, and prove that (i) it converges to the standard Bellman operator exponentially fast in the inverse temperature parameter, and (ii) the distance of its Q function from the optimal one can be bounded. These alone do not explain its superior performance, so we also show that the softmax operator can reduce the overestimation error, which may give some insight into why a sub-optimal operator leads to better performance in the presence of value function approximation. A comparison among different Bellman operators is then presented, showing the trade-offs when selecting them.

Introduction

In Reinforcement Learning (RL), the Bellman optimality equation serves as the foundation for finding optimal policies, typically employing the max operator to select the best future actions. However, in the context of Deep Q-Networks (DQN), the max operator often introduces a significant overestimation bias. Because neural networks are imperfect function approximators, they produce noisy Q-value estimates. The greedy nature of the max operator consistently selects the most positive errors, leading to inflated value estimates and unstable training gradients.

While the softmax operator is frequently used for exploration, it has traditionally been avoided for value function updates due to its theoretical sub-optimality and potential failure to satisfy contraction properties. This work challenges that convention, demonstrating that the Softmax Bellman Operator provides substantial practical benefits by mitigating overestimation and stabilizing training.

Methods

The authors propose integrating the softmax operator into the target networks of standard DQN and Double DQN (DDQN), resulting in S-DQN and S-DDQN. Instead of selecting the maximum Q-value for the next state, these algorithms use a softmax-weighted average of all possible Q-values, controlled by an inverse temperature parameter $\tau$.

Theoretical Contributions

  • Exponential Convergence: The authors prove that the softmax operator converges to the standard Bellman operator at an exponential rate relative to $\tau$, outperforming alternatives like Mellowmax which only converge linearly.
  • Bounded Sub-optimality: They establish that the distance between the softmax-derived value function and the true optimal value function is strictly bounded.
  • Bias Reduction: Formal analysis shows that the softmax operator reduces overestimation error across any temperature parameter $\tau$.

Experimental Results

The proposed methods were evaluated on the Arcade Learning Environment (ALE) using six Atari 2600 games: Q*Bert, Ms. Pacman, Crazy Climber, Breakout, Asterix, and Seaquest.

Learning curves for S-DQN and S-DDQN compared to standard DQN and DDQN across six Atari games.

As shown in the learning curves, S-DQN and S-DDQN consistently achieve higher maximum scores and faster convergence than their vanilla counterparts. Notably, in Asterix—a game where standard DQN often fails due to exploding gradients and severe overestimation—the softmax variants maintain stability and achieve significantly higher performance.

Analysis of Overestimation Bias

The primary driver of the improved performance is the reduction of overestimation bias. By averaging over actions rather than greedily selecting the maximum, the softmax operator dampens the impact of outlier Q-values caused by approximation noise.

Value estimates for DQN, DDQN, S-DQN, and S-DDQN, highlighting the reduction in overestimation bias.

In the value estimate plots, the estimates for vanilla DQN in Asterix grow uncontrollably, indicating severe overestimation. In contrast, S-DQN and S-DDQN maintain stable, lower value estimates that more accurately reflect the true underlying values. This stabilization leads to lower-norm gradients and more robust training throughout the learning process.

Discussion and Conclusion

The success of the softmax Bellman operator is counter-intuitive: a theoretically "sub-optimal" operator yields superior real-world policies. This suggests that in the presence of function approximation noise, being "softly" greedy is more effective than being perfectly greedy. The softmax operator acts as a natural regularizer, providing a more fundamental solution to overestimation than architectural changes like Double DQN.

Future work includes developing adaptive methods for tuning the inverse temperature $\tau$, as performance remains sensitive to this hyperparameter. While constant mid-range values for $\tau$ performed well, automated cooling schedules could further optimize results across diverse tasks.

Summary updated

Abstract

The impact of softmax on the value function itself in reinforcement learning (RL) is often viewed as problematic because it leads to sub-optimal value (or Q) functions and interferes with the contraction properties of the Bellman operator. Surprisingly, despite these concerns, and independent of its effect on exploration, the softmax Bellman operator when combined with Deep Q-learning, leads to Q-functions with superior policies in practice, even outperforming its double Q-learning counterpart. To better understand how and why this occurs, we revisit theoretical properties of the softmax Bellman operator, and prove that $(i)$ it converges to the standard Bellman operator exponentially fast in the inverse temperature parameter, and $(ii)$ the distance of its Q function from the optimal one can be bounded. These alone do not explain its superior performance, so we also show that the softmax operator can reduce the overestimation error, which may give some insight into why a sub-optimal operator leads to better performance in the presence of value function approximation. A comparison among different Bellman operators is then presented, showing the trade-offs when selecting them.
BibTeX
@misc{song2018revisiting,
  author = {Zhao Song and Ronald E. Parr and Lawrence Carin},
  title = {{Revisiting the Softmax Bellman Operator: Theoretical Properties and Practical Benefits}},
  year = {2018},
  eprint = {1812.00456},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1812.00456},
}
Figure