In reinforcement learning and adaptive dynamic programming, solving a Markov Decision Process (MDP) or a stochastic game fundamentally relies on finding the fixed point of a Bellman operator. Whether an agent uses model-based Value Iteration (VI) or model-free Q-learning, the standard update rule is governed by the contraction mapping theorem. This theorem guarantees convergence, but it also imposes a strict speed limit: the operator contracts at a rate dictated entirely by the environment's discount factor $\gamma \in (0, 1)$.
When $\gamma$ is close to 1—which is typical for long-horizon or continuous control tasks—convergence becomes agonizingly slow. Each iteration only shrinks the distance to the optimal solution by a factor of $\gamma$, requiring a massive number of iterations or samples to reach an acceptable error threshold. As noted in a comprehensive review by Derong Liu et al., balancing this convergence speed with stability remains a core theoretical and practical challenge in deploying learning algorithms to real-world physical systems.
To break this speed limit, a recent line of research adapts a classic technique from numerical linear algebra: Successive Over-Relaxation (SOR). By modifying the Bellman operator with an explicitly tunable relaxation parameter, this approach mathematically alters the contraction factor itself, allowing algorithms to converge faster than the standard discount factor would normally permit.
The Intuition: Extrapolating the Trajectory
To understand why successive relaxation works, imagine trying to reach a target destination where each step you take covers a fixed percentage of the remaining distance. If your step size is small, you will approach the target asymptotically, taking a long time to get close.
Successive over-relaxation alters this process by looking at where a standard step would land you, and then intentionally overshooting or extrapolating further along that exact trajectory.
Mathematically, if $T$ is the standard Bellman operator and $V_k$ is the current value estimate, a relaxed value iteration update takes the following form:
$$V_{k+1} = (1-\omega)V_k + \omega T V_k$$
Here, $\omega$ is the relaxation parameter.
- When $\omega = 1$, the update reverts to the standard first-order Bellman update.
- When $\omega > 1$ (over-relaxation), the algorithm aggressively pushes the value estimate further in the direction of the correction, anticipating the asymptotic path.
As explained by Chandramouli Kamanchi et al., incorporating this weighting parameter transforms the standard first-order update into a generalized second-order method. This geometric adjustment alters the contraction properties of the iterative process. Instead of contracting at the standard rate of $\gamma$, the newly constructed operator contracts at a rate strictly smaller than $\gamma$. Because the contraction factor is smaller, the distance between the current estimate and the optimal fixed point shrinks much faster at every single iteration.
Standard Update: [V_k] --------(gamma)--------> [T V_k]
Relaxed Update: [V_k] ----------------------------(omega > 1)----------------------------> [V_k+1]
(Closer to V*)
From Dynamic Programming to Model-Free Q-Learning
While the benefits of relaxation are straightforward to compute when the environment's transition dynamics are known, the real challenge lies in extending this mechanism to sample-based, model-free reinforcement learning.
In Successive Over-Relaxation ${Q}$ -Learning, Chandramouli Kamanchi et al. successfully embedded this numerical technique into the Q-learning framework. By modifying the temporal difference update rule with an over-relaxation parameter $\omega > 1$, the authors derived a modified Q-Bellman operator. They proved that this operator maintains a contraction factor below the discount factor, leading to lower average error and faster policy generation within fewer environment interactions.
To further optimize sample efficiency, Indu John et al. developed Generalized Speedy Q-learning (GSQL). Standard Speedy Q-learning accelerates convergence by utilizing both the current and the previous step's Q-estimates to mitigate sample variance. GSQL integrates successive relaxation directly into this architecture.
The authors demonstrated that the relaxation parameter $w$ fundamentally lowers the algorithm's sample complexity. It provides tighter finite-time performance bounds, particularly in environments where states have a high probability of "self-looping" (remaining in the same state), which typically stalls standard Q-learning. Crucially, the authors designed a simplified empirical operator for GSQL that avoids complex transition sampling, allowing practitioners to reap the acceleration benefits of a relaxed Bellman operator without needing to explicitly modify or know the environment's transition probabilities.
Bypassing Limits in Multi-Agent Games
The acceleration power of successive over-relaxation is not limited to single-agent MDPs. In competitive multi-agent environments, finding the optimal value function is notoriously slow because the Bellman equation must resolve a minimax optimization at every state to find the Nash equilibrium.
Addressing this bottleneck, Raghuram Bharadwaj Diddigi et al. applied successive over-relaxation to two-player zero-sum stochastic games. By introducing a relaxation parameter greater than one into the minimax Bellman equation, the authors showed that the inherent speed limit of competitive Q-learning can be bypassed.
Just as in the single-agent case, the over-relaxed minimax operator reduces the effective contraction factor below the standard discount factor. This mathematical guarantee ensures that the value function converges to the game's equilibrium significantly faster, proving that relaxation techniques are robust enough to stabilize and accelerate even highly non-linear, adversarial optimization landscapes.
Key Foundational Work
Successive Over-Relaxation ${Q}$ -Learning (2020) — contributed 6 concept elements to this direction.
Generalized Speedy Q-learning (2019) — contributed 4 concept elements to this direction.