In reinforcement learning (RL), we often focus on the precision of value estimates—trying to predict exactly how much reward an agent will receive. However, a growing body of research suggests that the absolute accuracy of these values is less important than the action gap: the difference in value between the optimal action and the next best alternative.
When this gap is large, the agent’s policy becomes robust to noise and approximation errors. When it is narrow, even tiny errors can cause the agent to "flip" to a suboptimal action. Understanding and manipulating this gap is central to improving both the sample efficiency and the robustness of modern RL agents.
The Margin Between Decision and Error
Standard RL theory often treats value estimation as a regression problem. However, as Amir-massoud Farahmand argues in Action-Gap Phenomenon in Reinforcement Learning, the ultimate goal is actually a classification task: selecting the best discrete action.
The "action-gap regularity" implies that an agent can achieve an optimal policy long before its value function estimates converge. If the estimation error is smaller than half the action gap, the agent will still rank the actions correctly. This perspective shifts the focus from global function accuracy to the decision boundary. As noted by Farahmand et al. in Classification-based Approximate Policy Iteration, mistakes in states with a large action gap are far more detrimental than mistakes where actions are nearly identical in value, suggesting that algorithms should prioritize precision where the gap is most decisive.
Why Small Gaps Lead to Instability
In deep reinforcement learning, function approximation is inherently noisy. Vieillard et al. observe in Munchausen Reinforcement Learning that the value difference between optimal and suboptimal moves is often very small in practice. This narrow margin makes agents highly susceptible to choosing incorrect actions due to minor estimation errors.
This instability is particularly visible in complex tasks. Clark et al. point out in Beyond The Rainbow that a narrow action gap causes agents to frequently switch between suboptimal actions, hindering steady progress. Similarly, Tan and Patel highlight that when converting models (such as from DQNs to Spiking Neural Networks), small approximation errors can lead to catastrophic performance drops if the original action values were too close together.
Artificially Expanding the Gap
To combat this sensitivity, several researchers propose operators that intentionally widen the action gap.
- Munchausen RL: Vieillard et al. introduce a simple modification that adds the agent's scaled log-policy to the reward. This systematically expands the action gap, making the policy more robust to the noise inherent in neural networks.
- Stochastic Operators: Lu et al. propose Robust Stochastic Operators, which use randomness to penalize the difference between the state value and specific action values, effectively filtering out sampling noise by increasing the separation between actions.
- Smoothing Advantage Learning: Gan and Zhang develop the SAL operator to prevent the "exploding action gap" problem while still maintaining a sufficient margin to ensure the correct policy is preserved despite estimation errors.
Gap-Dependent Sample Complexity
The action gap isn't just a tool for robustness; it is a fundamental driver of how fast an agent can learn. Traditional "worst-case" bounds suggest that sample complexity scales cubically with the planning horizon. However, Zanette et al. demonstrate in Almost Horizon-Free Structure-Aware Best Policy Identification that if an algorithm can identify clearly inferior actions, it can decouple sample complexity from the horizon.
This "gap-dependent" complexity means that in environments where the best choice is obvious, agents can find the optimal policy much faster. Jonsson et al. apply this to Monte-Carlo Tree Search in MDP-GapE, showing that focusing exploration on the most competitive candidates—rather than all actions—leads to significantly higher efficiency.
Certified Robustness and Adversarial Defense
Finally, the action gap serves as a buffer against adversarial attacks. If an agent is trained to maintain a large margin between the best and second-best action, a small perturbation to the input (like noise in a sensor) will be insufficient to "flip" the agent's decision.
Oikarinen et al. formalize this in RADIAL-RL by incorporating robustness verification bounds into training to ensure a consistent margin. Building on this, Wang et al. introduce CAMP, which explicitly maximizes the "Q-gap." By treating the action gap as an optimization objective, these methods produce agents that are provably resilient to worst-case perturbations.
Key Foundational Work
Variable Resolution Discretization in Optimal Control (2002) — contributed 2 concept elements to this direction.
Algorithms and Bounds for Rollout Sampling Approximate Policy Iteration (2008) — contributed 1 concept elements to this direction.