Accelerating Reinforcement Learning with Successive Over Relaxation

You are reading version 1 of this direction, frozen 2026-10-04. The latest version is version 2.

Version 1 of 29 papers22 conceptsfrozen 2026-10-04

In reinforcement learning (RL), the speed of discovery is often dictated by a mathematical "speed limit." Whether an agent is learning to play a game or control a robot, it typically relies on the Bellman operator to update its estimates of future rewards. This operator is a contraction mapping, meaning that with each update, the estimate gets closer to the truth. However, the rate of this approach is strictly bounded by the environment's discount factor ($\gamma$). When $\gamma$ is close to 1—as it often is in long-horizon tasks—convergence can become agonizingly slow.

A growing body of research suggests we can break this speed limit by borrowing a classic tool from numerical linear algebra: Successive Over-Relaxation (SOR). By modifying the standard Bellman update with a relaxation parameter, researchers have shown it is possible to reach optimal policies significantly faster than traditional methods.

The Intuition of Over-Relaxation

Standard Value Iteration and Q-learning move the current value estimate directly toward a target. If the target is $T(V)$ and the current estimate is $V$, the update essentially says: "Move to exactly $T(V)$."

Successive Over-Relaxation, as explored by Chandramouli Kamanchi and Raghuram Bharadwaj Diddigi in Successive Over Relaxation Q-Learning, changes this logic. Instead of stopping at the target, the algorithm "overshoots" it slightly. By introducing a relaxation parameter $w$ (typically between 1 and 2), the update becomes a weighted combination of the old value and the new target.

Mathematically, this modification transforms the effective contraction factor of the Bellman operator. While the standard operator contracts at a rate of $\gamma$, the relaxed version contracts at a rate strictly lower than $\gamma$. This means the "distance" to the optimal solution shrinks faster in every iteration, allowing the algorithm to close the gap in fewer steps.

Scaling to Complex Scenarios

The power of this idea lies in its versatility across different RL architectures:

  • Competitive Games: In A Generalized Minimax Q-learning Algorithm for Two-Player Zero-Sum Stochastic Games, Diddigi and Kamanchi apply SOR to minimax operators. In adversarial settings where two players are at odds, reaching equilibrium is computationally expensive; over-relaxation provides a shortcut to that equilibrium without losing theoretical convergence guarantees.
  • Deep Learning: The concept isn't limited to tabular look-up tables. S. Zubin Gautam and colleagues introduced D-SOR-MQL in Deep SOR Minimax Q-learning for Two-player Zero-sum Game, demonstrating that over-relaxed updates can stabilize and accelerate training even when using deep neural networks as function approximators.
  • Second-Order Methods: For even faster convergence, Kamanchi and Diddigi combined SOR with Newton-Raphson optimization in Second Order Value Iteration in Reinforcement Learning. Here, relaxation helps smooth out the non-differentiable parts of the Bellman equation, allowing second-order methods to find the optimal policy with extreme precision.

Why It Works: Self-Loops and Eigenvalues

Why does overshooting actually help? One perspective, offered by Indu John and Kamanchi in Generalized Speedy Q-learning, links the benefit of SOR to the structure of the environment. In Markov Decision Processes where an agent might "self-loop" (stay in the same state after an action), standard updates are particularly inefficient. SOR effectively compensates for these loops, pushing the value function through the "stuck" states more aggressively.

From a control theory perspective, as discussed by Derong Liu and co-authors in State of the Art of Adaptive Dynamic Programming and Reinforcement Learning, the relaxation factor acts as a tunable knob for the convergence rate. By optimizing this parameter, practitioners can balance the speed of learning against the stability of the policy. This is mathematically related to the spectral properties of the transition matrix; as Xingguo Chen notes in A Variance Minimization Approach to Temporal-Difference Learning, accelerating convergence often involves increasing the magnitude of the key eigenvalues that govern the system's dynamics.

By treating the Bellman equation not just as a learning rule, but as a numerical system to be solved, Successive Over-Relaxation provides a robust framework for making reinforcement learning faster and more efficient across a wide array of domains.

Papers in this version

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 5 papers
  2. Version 1 · 2026-10-04 · 9 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_relaxation_based_convergence_acceleratio_75352e70,
  title = {relaxation-based convergence acceleration},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/relaxation-based-convergence-acceleration/rdr_75352e7011b748b5b1de40d0c71d2328},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-20},
}

This exact version (version 1, frozen text):

@misc{lacuna_accelerating_reinforcement_learning_with_75352e70_v1,
  title = {Accelerating Reinforcement Learning with Successive Over Relaxation},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/accelerating-reinforcement-learning-with-successive-over-relaxation/rdr_75352e7011b748b5b1de40d0c71d2328/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-20},
}