Revisiting the Softmax Bellman Operator: New Benefits and New Perspective

Zhao Song, Ronald Parr, Lawrence CarinICML 2019 · OpenReview

TL;DR While the softmax function is a staple for exploration in reinforcement learning (RL), this paper reveals its hidden power as a structural component of the learning process itself. By replacing the standard "max" in the Bellman operator with a "softmax" variant, the authors demonstrate that agents can significantly reduce overestimation bias and gradient noise, leading to state-of-the-art performance on complex Atari benchmarks.

The Problem: Overestimation and Instability

In Deep Q-Learning (DQN), agents learn to make decisions by estimating the "value" (Q-value) of taking a specific action in a specific state. Traditionally, this relies on the Bellman equation, which uses a max operator to determine the best possible future value.

However, the max operator has two major Achilles' heels in deep learning:

  1. Overestimation Bias: Because neural network estimates are noisy, the max operator tends to pick the "luckiest" (most overestimated) value rather than the truly best one. This leads to a spiral of over-optimism that can ruin training.
  2. Gradient Instability: Overestimation often leads to massive, erratic updates to the neural network (high gradient noise), which can cause the model to diverge or "explode" during training.

While researchers have tried to fix this with architectural changes like Double DQN (DDQN), the authors of this paper argue that the root of the problem—the max operator itself—deserves a fundamental rethink.

The Solution: The Softmax Bellman Operator

The authors propose the Softmax Bellman Operator. Instead of calculating the target value using the strict maximum Q-value of the next state, they use a softmax-weighted average of all possible future Q-values.

Key technical details include:

  • S-DQN and S-DDQN: The authors integrated this operator into the standard DQN and Double DQN architectures, creating two new variants.
  • Inverse Temperature ($\tau$): They use a parameter $\tau$ to control how "peaky" the softmax is. As $\tau$ increases, the operator behaves more like a standard max.
  • Theoretical Proofs: They provide new proofs showing that while the softmax operator isn't always a strict "contraction" (a mathematical property usually required for convergence), it converges to the optimal Bellman operator exponentially fast as $\tau$ increases.
  • Comparison: Unlike other softened operators (like Mellowmax) that converge linearly, the Softmax Bellman operator's exponential convergence explains why it works so well even with high $\tau$ values.

Experimental Setup

The researchers evaluated their methods using the Arcade Learning Environment (ALE), testing on six diverse Atari 2600 games: QBert, Ms. Pacman, Crazy Climber, Breakout, Asterix, and Seaquest.*

A crucial insight in their setup is the separation of target calculation and behavior. They use softmax for the target calculation (how the agent learns) but keep standard $\epsilon$-greedy for exploration (how the agent acts). This proves the benefits are structural to the value updates, not just a result of better exploration.

Key Results and Insights

The softmax operator acts as a smoother version of the max. By considering all actions (weighted by their value), it naturally dampens the impact of a single noisy, overestimated Q-value. This smoothing significantly lowers the variance and norm of the gradients, making the neural network much easier to train.

Performance across Atari games

As shown in the performance curves across the Atari suite, S-DQN and S-DDQN consistently outperformed their standard counterparts. In many cases, S-DQN (the "softer" version of the original DQN) even beat the more advanced Double DQN.

Asterix served as a particularly important test case. It is well-known in the RL community for causing massive overestimation issues in standard DQN.

Value estimates on Asterix

On Asterix, standard DQN failed miserably due to exploding value estimates. In contrast, S-DQN and S-DDQN maintained stable, realistic value estimates and achieved scores orders of magnitude higher (e.g., ~8,800-11,000 vs. ~200 for standard DQN).

Limitations and Future Work

While highly effective, the approach has a few limitations:

  • Hyperparameter Sensitivity: Performance depends heavily on choosing the right inverse temperature $\tau$. If $\tau$ is too low, the agent underestimates values; if it's too high, the benefits of smoothing disappear.
  • Manual Tuning: In this study, $\tau$ was selected via grid search. The authors suggest that future work should investigate "cooling schemes"—automated ways to adjust $\tau$ dynamically during training, similar to simulated annealing.
  • Theoretical Gap: While they proved the operator is "well-behaved," the fact that it isn't a strict contraction in all cases remains a theoretical curiosity that warrants further investigation in more complex environments.

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 contr...
BibTeX
@inproceedings{song2019revisiting,
  author = {Zhao Song and Ronald Parr and Lawrence Carin},
  title = {{Revisiting the Softmax Bellman Operator: New Benefits and New Perspective}},
  booktitle = {International Conference on Machine Learning},
  year = {2019},
  url = {https://openreview.net/forum?id=BkZBVn-uZr},
}
Figure