Reinforcement learning is slow when the discount factor is close to one. Each Bellman update, the step that refreshes a value estimate from its successors, shrinks the error only by a factor of $\gamma$. That makes the effective horizon $1/(1-\gamma)$ both the iteration count and the dominant term in sample-complexity bounds. Successive over-relaxation (SOR), borrowed from numerical linear algebra, deliberately overshoots each update by a factor $\omega>1$. It can contract faster than $\gamma$, but only when states have self-loops, meaning some probability of staying in the same state. It also needs those self-loop probabilities known in advance to choose $\omega$.
This note makes a simple observation and follows it through. For the optimal self-loop-aware choice of $\omega$, SOR is exactly the Bellman equation of the jump chain: the process observed only when the state actually changes. Over-relaxation therefore replaces the step horizon with a shorter event horizon. The consequence is that $\omega$ should be set per state from a conservative, confidence-bounded estimate of that state's self-loop probability, obtained from counts or from a learned model. The learned-model setting is where overshoot becomes dangerous: a model that overestimates how often the system stays put produces an $\omega$ that breaks contraction. We propose to build this estimator, prove that it contracts with high probability, analyze its sample complexity in terms of the event horizon, and test it in both tabular and model-based deep reinforcement learning.
Core Claim
Write $p(s,a)=P(s\mid s,a)$ for the self-loop probability. Consider the relaxed Q-update of Successive Over-Relaxation Q-Learning:
$$(T_\omega Q)(s,a)=\omega\big(r(s,a)+\gamma\,\mathbb{E}_{s'}\max_b Q(s',b)\big)+(1-\omega)\max_b Q(s,b).$$
In this update the weight on the current state's own value is $1-\omega+\omega\gamma p$ and the total absolute weight is $1-\omega(1-\gamma)$. Allowing $\omega$ to vary by state-action pair, the largest safe choice is $\omega^*(s,a)=1/(1-\gamma p(s,a))$. That choice gives a local contraction factor of
$$\gamma'(s,a)=\frac{\gamma\,(1-p(s,a))}{1-\gamma\,p(s,a)},\qquad \frac{1}{1-\gamma'}=\frac{1-\gamma p}{1-\gamma}.$$
Here $\gamma'$ is the discount of the chain that skips self-transitions. When $p$ is near one, as in lazy systems, sticky dynamics, or finely discretized control, the effective horizon behaves like $(1-p)/(1-\gamma)$: the number of steps on which the state actually moves.
Two facts follow from the same algebra, and neither is stated in the existing SOR papers. First, SOR does not change the fixed point, so it cannot reduce the bias of a wrong model. It changes only how fast, and with how much noise, the estimate gets there. Second, overestimating $p$ is not immediately fatal. Contraction survives as long as $\omega<2/(1+\gamma-2\gamma p)$, which gives an explicit tolerance for model error. Beyond that bound the iteration diverges.
The claim to test is this: with $\omega(s,a)$ set from a lower confidence bound on $p(s,a)$, relaxed Q-learning contracts with high probability, needs no prior model knowledge, and has a sample complexity governed by the event horizon rather than $1/(1-\gamma)$.
Relation to Prior Work
The SOR line supplies the operator but leaves the gaps we target. Successive Over-Relaxation Q-Learning proves faster contraction under self-loops using a single global $\omega$ fixed by the minimum self-loop probability, which it assumes is known. Generalized Speedy Q-learning adds relaxation to Speedy Q-learning with a probably-approximately-correct bound based on the Azuma-Hoeffding inequality, a concentration bound that ignores variance; that bound is proven only for one variant. Generalized Second-Order Value Iteration gets Newton-type convergence but needs the exact model and a cubic-cost matrix inversion. Our proposal differs from all three in making $\omega$ state-dependent, data-driven and confidence-bounded, and in replacing the Azuma analysis with variance-aware tools.
The horizon-complexity line supplies the analysis technique and also constrains the claim. Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning shows that vanilla Q-learning needs $\tilde O(|S||A|/((1-\gamma)^4\varepsilon^2))$ samples, using Freedman's martingale inequality and high-order error recursions. It also shows that Speedy Q-learning's extra machinery buys nothing in horizon order. That warns us that acceleration claims can dissolve under a tight analysis. We reuse its recursion with $\gamma'(s,a)$ in place of $\gamma$, plus an extra term for the error in estimating $p$. Settling the Horizon-Dependence of Sample Complexity and the variance argument of Azar et al. show that horizon factors are often artifacts of loose analysis. Our claim is structural rather than analytic: laziness genuinely shortens the horizon, and relaxation is one way to exploit it.
The compounding-error line defines the application regime. When to Trust Your Model bounds model-rollout error as quadratic in rollout length and therefore keeps rollouts short. Masked Model-based Actor-Critic masks uncertain model transitions and penalizes them. Double Horizon Model-Based Policy Optimization separates long rollouts used to gather states from short rollouts used to compute value targets. None of these changes how fast values propagate through the Bellman backup. Our fixed-point observation also says plainly what relaxation cannot do for them: it cannot repair model bias.
Research Program
The theoretical stage has three parts.
The first is to prove that per-state relaxation, with $\omega(s,a)$ built from a Bernstein lower confidence bound on $p(s,a)$, gives a $\gamma'$-contraction under the true dynamics with high probability.
The second is to adapt the Freedman-based recursion of Li et al. to relaxed synchronous Q-learning. The target is a bound in which $(1-\gamma)^{-4}$ becomes $\big((1-\gamma)/(1-\gamma \bar p)\big)^{-4}$, where $\bar p$ is a suitably averaged laziness, plus a separate term for estimating $p$. One subtlety must be handled head-on. Sup-norm contraction is set by the least lazy state, so the gain must come from a local, state-weighted argument. The other risk is noise: relaxation multiplies the target noise by $\omega$. The analysis must show that this amplification is offset because $\max Q(s')$ equals $\max Q(s)$ whenever the state self-transitions. If it is not offset, the result is a negative theorem, and that is worth publishing too.
The third part is a perturbation result. If the self-loop estimate $\hat p$ comes from a learned model with error $\epsilon_p$, we bound the slowdown when $\hat p$ underestimates $p$. When $\hat p$ overestimates $p$, we bound the loss of contraction using the $2/(1+\gamma-2\gamma p)$ threshold.
The algorithmic stage builds "certified-relaxation Q-learning" in tabular form. In this version $p$ is estimated from visit counts, and the update needs only $O(|S||A|)$ extra memory.
We then extend it to a Dyna-style deep agent. For continuous states the self-loop becomes a soft quantity: the learned model's predicted probability that the next state falls within a small value-indistinguishable neighborhood of the current one. Its lower confidence bound is taken across the model ensemble. The resulting relaxed critic target is plugged into the model-based policy optimization agent of When to Trust Your Model, using the target-normalization fixes of A Forensic Analysis of Synthetic Data in RL so that we avoid the scale failures that paper documents.
The deep extension is explicitly the riskier stage. Where true self-loops do not exist, it may collapse into a tuned step size, and the ablations below are designed to detect exactly that.
Baselines
The naive reference is standard Q-learning ($\omega=1$) with the same step-size schedule. In the deep setting it is the standard agent with its unmodified critic target. Every method receives the same samples, the same number of updates, and the same hyperparameter-search budget, with all learning rates tuned on held-out random MDPs.
The strongest relaxation competitor is global SOR Q-learning from Successive Over-Relaxation Q-Learning, given the true minimum self-loop probability, which is an oracle advantage we do not have. On 100 random MDPs with 10 states and 5 actions, after $10^5$ iterations, that paper reports an average error of 0.3032 versus 0.3962 for Q-learning. We replicate this exact setting first. Beating it means lower error at matched iterations without oracle knowledge, with a margin that grows as self-loop probabilities become heterogeneous across states.
Generalized Speedy Q-learning is also run, but no reported result for it on Lacuna was found in numerical form, so we compare against our own reimplementation.
For the statistical question, the strongest competitor is certainty-equivalent planning. That means fitting the empirical transition model from the same samples and solving it exactly, the approach analyzed by Azar et al.. It is statistically strong but uses $O(|S|^2|A|)$ memory.
In the deep setting, the strongest baselines are the normalized agent from A Forensic Analysis of Synthetic Data in RL, which reports beating soft actor-critic on 5 of 7 DeepMind Control tasks, and Double Horizon Model-Based Policy Optimization. No per-task return numbers for either were found on Lacuna, so both are rerun under our budget.
Two ablations isolate the key ingredient. The first uses a global $\omega$ equal to the mean of our per-state values. The second uses an oracle per-state $\omega^*(s,a)$ computed from the true $p$. The gap between our method and the global variant measures the value of state dependence. The gap to the oracle measures the cost of confidence bounds.
Why not just…?
Why not just tune the learning rate or the target-network update rate? A uniform $\omega$ applied to a frozen target network is, in function space, just an extrapolated target step. A reviewer is right that it could be absorbed by tuning. What cannot be absorbed is the state dependence and the self-loop structure: over-relaxing a state with no self-loop breaks contraction, while under-relaxing a lazy state wastes speed. We settle this with an ablation that uses a learning rate tuned to its best value. If the tuned rate matches us on MDPs with heterogeneous self-loops, the claim is false.
Why not just estimate the model and plan exactly? This is the real threat on sample count. Certainty-equivalent planning may already exploit laziness implicitly. We expect it to match or beat us in samples, and we will report whether it also scales with the event horizon, which would itself be a finding. Our method's case rests on keeping a memory-light online update and on the deep setting, where exact planning is not available.
Why not use n-step returns, action repeat, or a smaller $\gamma$? Reducing $\gamma$ changes the problem being solved. Action repeat restricts the set of policies the agent can represent. N-step returns trade bias against variance without using self-loop structure. The Li et al. result also shows that such variance machinery alone does not change the horizon order. We include n-step Q-learning and action repeat as baselines on the sticky-dynamics MDPs, where these distinctions should show up.
Why not simply mask uncertain model transitions or keep rollouts short? Masking and short rollouts address bias from the model. Relaxation addresses propagation speed, which they do not touch. The two are complementary, so the deep experiment tests relaxation on top of masking rather than instead of it.
Proposed Experiments
The decisive tabular test uses random MDPs in the style of the SOR papers, scaled to 1,000 states as in Generalized Speedy Q-learning. We sweep $\gamma$ from 0.9 to 0.999 and control the distribution of self-loop probabilities, from none to near one and from uniform across states to highly heterogeneous. We measure the number of samples needed to reach sup-norm error $\varepsilon$, and fit how that number scales with the nominal horizon and with the event horizon.
The prediction is falsifiable. Samples-to-$\varepsilon$ should track $(1-\gamma\bar p)/(1-\gamma)$ rather than $1/(1-\gamma)$. With no self-loops, the method should revert exactly to Q-learning.
The model-error test builds a tabular Dyna agent whose self-loop estimate is deliberately biased upward by $\epsilon_p$. We then check whether divergence begins where the $2/(1+\gamma-2\gamma p)$ threshold predicts, and whether lower-confidence-bound estimation prevents it.
The deep test runs on DeepMind Control Suite and MuJoCo. We halve and quarter the control timestep to create lazy dynamics and report returns at fixed numbers of environment steps. A positive result means that the relaxed-target agent's advantage grows as the timestep shrinks and survives the matched-learning-rate ablation. If the advantage vanishes under that ablation, we will report that relaxation in deep reinforcement learning without true self-loops reduces to step-size tuning.
References
- Successive Over-Relaxation ${Q}$ -Learning
- Generalized Speedy Q-Learning
- Generalized Second-Order Value Iteration in Markov Decision Processes
- Tightening the Dependence on Horizon in the Sample Complexity of Q-Learning
- Settling the Horizon-Dependence of Sample Complexity in Reinforcement Learning
- On the Sample Complexity of Reinforcement Learning with a Generative Model
- When to Trust Your Model: Model-Based Policy Optimization
- Trust the Model When It Is Confident: Masked Model-based Actor-Critic
- Double Horizon Model-Based Policy Optimization
- Fixing That Free Lunch: When, Where, and Why Synthetic Data Fails in Model-Based Policy Optimization