💻 computer science

Distributional Bellman Operators with Power-Law Horizon Weights: Contraction and Fixed-Point Analysis

This paper establishes that distributional Bellman operators with arbitrary multi-horizon power-law weights are contractions in the supremal p-Wasserstein metric and preserve the true return distribution as a unique fixed point, thereby providing a theoretical foundation for incorporating long-memory mechanisms into distributional reinforcement learning.

Original authors: Yashar Mousavi, Rashin Mousavi, Arash Mousavi, Mahsa Tavasoli, Ibrahim Beklan Kucukdemiral, Afef Fekih, Umit Cali

Published 2026-10-14

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Yashar Mousavi, Rashin Mousavi, Arash Mousavi, Mahsa Tavasoli, Ibrahim Beklan Kucukdemiral, Afef Fekih, Umit Cali

Original paper licensed under CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of artificial intelligence, there is a persistent challenge known as the credit assignment problem. Imagine an agent, like a robot or a software program, learning to navigate a complex environment. It takes a series of actions, and only much later does it receive a reward or a penalty for its behavior. The difficulty lies in figuring out which specific actions in the past were responsible for that final outcome. If the reward comes hundreds of steps after the initial decision, the connection becomes faint, and the agent struggles to learn effectively. To solve this, researchers use mathematical tools called Bellman operators. These tools act as a kind of memory, helping the agent trace the value of its actions back through time. For decades, the standard approach has been to look at the immediate next step and then discount the future, fading the memory of distant events very quickly, like a sound dying out in a large room. This method is reliable and mathematically safe, but it often forgets important long-term patterns too soon.

A newer approach, known as distributional reinforcement learning, goes a step further. Instead of just predicting a single average value for a future reward, it models the entire range of possible outcomes, capturing the full shape of uncertainty. This provides a richer picture of the world, but it relies on the same mathematical safety net: the operator must shrink errors over time to ensure the agent eventually learns the correct answer. Recently, a framework called FracTrace introduced a way to give agents a much longer memory using power-law weighting, a method that keeps the influence of past actions alive for much longer than the standard approach. However, this framework was built with a strict rule: the long memory could only be used to evaluate the agent's policy, not to update its core value estimates. The reason was a fear that mixing these long-term memories into the core update rule would break the mathematical safety net, causing the learning process to become unstable.

This paper sets out to test whether that fear is justified. The researchers asked a fundamental question: if we replace the standard, short-sighted update rule with a new rule that mixes together many different time horizons, weighted by a power-law distribution, does the system still remain stable? They constructed a new mathematical operator that blends updates from one step, two steps, ten steps, and even hundreds of steps into a single, unified calculation. By rigorously analyzing this operator, they proved that it does not break the system. In fact, the new operator is just as stable as the old one, and under specific conditions—namely when the power-law distribution has a sufficiently heavy tail—it can be even more efficient at reducing errors. The study demonstrates that the long-memory approach can be safely applied to the core learning mechanism, not just the policy side, without sacrificing the mathematical guarantees that keep the agent from going off course.

The core of the discovery lies in how the new operator handles the passage of time. In the standard method, the influence of a future reward drops off exponentially, becoming negligible after a few dozen steps. The new method uses a power-law distribution, which means the influence of past actions fades much more slowly, allowing the agent to maintain a clear connection to events that happened long ago. The researchers showed that when you mix these different time horizons together, the mathematical property that ensures stability—known as contraction—can actually improve, but this depends on the specific shape of the weighting. They proved that placing more weight on longer horizons (using a "heavier" tail) leads to a faster shrinking of errors. However, this is not a universal rule for all power-law settings; if the tail is too light, the contraction can actually be slower than the standard geometric approach. The analysis reveals that the long memory acts as a stabilizer and accelerates learning only when the weighting is tuned to emphasize sufficiently long horizons.

To ensure this was not just a theoretical possibility, the team derived exact formulas for how fast this new method converges compared to the old one. They found that for the specific range of parameters that previous studies had identified as useful for long-term memory, the new operator reduces the number of steps needed to learn by a significant margin. In some scenarios, the new method requires only a fraction of the iterations that the standard method needs to reach the same level of accuracy. For instance, while the standard one-step method might need nearly seven hundred updates to clear up a small error, the power-law mixture with the right settings might need only six. This dramatic reduction suggests that agents could learn much faster if they are allowed to use this long-memory mechanism directly in their core learning loop, provided the tail of the distribution is heavy enough.

The researchers also addressed a critical concern: does this new method still lead the agent to the correct answer? In mathematics, an operator can be stable and shrink errors, but if it shrinks them toward the wrong target, the agent will learn a false reality. The paper proves that the new operator has a unique fixed point, and that point is exactly the true distribution of future rewards. This means the agent is not just learning faster; it is learning the right thing. The study further showed that this holds true even when the weighting of the time horizons changes depending on the specific situation the agent is in. This flexibility is crucial for real-world applications where different states might require different memory depths. The mathematical proof confirms that the system remains stable and correct regardless of how the memory weights are adjusted across different states.

One of the most important findings is that the new method does not simply offer a trade-off where you gain speed but lose safety. The analysis confirms that the new operator is guaranteed to be at least as stable as the standard one-step method, and it offers a strictly faster error correction rate only when the power-law tail is sufficiently heavy. The researchers constructed specific, simple examples to show that the theoretical limits they calculated are not just loose estimates but are the exact worst-case scenarios. This means the speed-up is real and guaranteed for the heavy-tailed cases, not just a lucky occurrence in a few test cases. They also demonstrated that the method works for different ways of measuring error, ensuring that the stability holds up under various definitions of what it means for the agent to be "close" to the truth.

The paper also clarifies a misunderstanding about how this new method relates to previous work. It explains that the power-law memory used in the new operator is fundamentally different from the non-summable kernels used in the policy side of the FracTrace framework. The new operator uses a normalized distribution, meaning the weights add up to one, which is a requirement for the mathematical proof to hold. This distinction is vital because it allows the long-memory mechanism to be used safely in the Bellman backup, a place where it was previously thought to be too risky. The study effectively removes the barrier that had kept long-memory mechanisms confined to the policy side, opening the door for a new generation of agents that can learn from long-term patterns directly in their value estimation.

While the theoretical results are robust, the authors are careful to note the practical implications. They point out that calculating these long-memory updates is more computationally expensive than the standard one-step update because it requires looking further into the future. The speed-up in learning iterations does not automatically translate to a faster wall-clock time unless the computational cost is managed. The paper leaves the question of how to balance this computational cost with the learning speed as an open area for future research. However, the theoretical foundation is now solid: the long-memory approach is mathematically safe, leads to the correct answer, and offers a significantly faster path to convergence when the tail of the distribution is heavy enough. This provides a strong basis for engineers and researchers to experiment with incorporating these powerful long-memory mechanisms directly into the core of their reinforcement learning systems, potentially unlocking new capabilities for agents that need to understand complex, long-term cause-and-effect relationships.

Technical Summary: Distributional Bellman Operators with Power-Law Horizon Weights

Problem Statement
Distributional Reinforcement Learning (RL) models the full distribution of returns rather than just their expected values, relying on the contraction property of the distributional Bellman operator to ensure stable policy evaluation. While the standard one-step distributional Bellman operator is known to be a contraction in the supremal $p$ -Wasserstein metric, it remains unclear whether this property is preserved when the operator is extended to a multi-horizon backup with power-law memory. Previous work, such as the FracTrace framework, utilized power-law (Mittag–Leffler) kernels for credit assignment but restricted their application to the policy side (advantage estimation) rather than the critic. This restriction was adopted because the technical coupling arguments used to prove contraction for the standard operator do not directly transfer to operators that mix returns over many horizons under arbitrary weight distributions. The central question addressed is whether a multi-horizon distributional Bellman operator, defined by an arbitrary normalized distribution of bootstrap horizons (specifically including power-law weights), preserves contraction and converges to the correct return distribution.

Methodology
The paper introduces a general multi-horizon mixing operator, $T_w$ , which combines $n$ -step distributional Bellman backups weighted by a normalized probability distribution $w$ over horizons $n \ge 1$ . The analysis is conducted within the space of return-distribution functions with uniformly bounded support, equipped with the supremal $p$ -Wasserstein metric.

The methodology relies on three primary technical components:

Coupling Arguments: The proof extends the standard coupling technique used for the one-step operator. By coupling identical trajectory prefixes and rewards, the analysis isolates the difference in bootstrap distributions.
Convexity of Wasserstein Distance: The proof utilizes the convexity of the $p$ -th power of the Wasserstein distance under mixtures (Lemma 1) to bound the distance between mixed operators.
Stochastic Dominance: To compare contraction rates across different weight families, the paper employs first-order stochastic dominance. It analyzes how shifting weight toward longer horizons affects the contraction modulus, explicitly distinguishing this from mean-preserving spreads which might suggest the opposite via Jensen's inequality.

The analysis covers both state-independent weights and state-dependent weight families (where the horizon distribution varies per state), ensuring the results apply to architectures similar to FracTrace where kernels are state-modulated.

Key Contributions
The paper establishes the following theoretical results:

Unconditional Contraction: For any normalized horizon-weight distribution $w$ and any $p \ge 1$ , the operator $T_w$ is a contraction in the supremal $p$ -Wasserstein metric. The contraction modulus is given explicitly as $\kappa_p(w) = (\sum_{n \ge 1} w(n)\gamma^{np})^{1/p}$ . This modulus satisfies $\kappa_p(w) \le \gamma$ , with equality holding if and only if $w$ is the point mass at $n=1$ (the standard one-step operator).
Fixed-Point Preservation: The unique fixed point of $T_w$ is identified as the true return-distribution function $Z^\pi$ . This confirms that mixing returns across horizons does not alter the target distribution, ensuring the safety of the fractionalized critic.
Comparative Contraction Law: The paper proves that horizon distributions placing more weight on longer horizons (in the sense of first-order stochastic dominance) yield a strictly smaller (tighter) contraction modulus within the power-law family. This contradicts the intuition that "spreading" weights might weaken contraction via convexity arguments.
Closed-Form Moduli: Explicit formulas for the contraction modulus are derived for geometric weights (recovering compound updates) and power-law weights $w_\alpha(n) \propto n^{-(1+\alpha)}$ . For power-law weights, the modulus is expressed using the polylogarithm function: $\kappa_p(w_\alpha)^p = \text{Li}_{1+\alpha}(\gamma^p) / \zeta(1+\alpha)$ .
Sharpness and State-Dependence: The derived modulus is shown to be the exact worst-case Lipschitz constant over the class of admissible Markov Decision Processes (MDPs). Furthermore, the theory extends to state-dependent weights without incurring renormalization-inflation constants, provided the weights are normalized per state.
Iteration Complexity: The contraction modulus is converted into an explicit iteration count required to reach a target accuracy, demonstrating that heavier-tailed weights can significantly reduce the number of operator applications needed for convergence.

Results
Numerical evaluations on a tabular MDP and analytical calculations confirm the theoretical findings:

Contraction Rates: For a discount factor $\gamma=0.99$ , power-law weights with small $\alpha$ (heavy tails, e.g., $\alpha \in [0.08, 0.16]$ ) achieve significantly lower contraction moduli than both the standard one-step operator ( $\kappa = 0.99$ ) and the geometric reference ( $\lambda=0.95$ ). For instance, at $\alpha=0.08$ and $p=1$ , the modulus drops to approximately $0.3041$, representing a substantial improvement over the geometric baseline.
Crossover Behavior: The analysis identifies a crossover point ( $\alpha^* \approx 0.43$ for $p=1$ ) where power-law weights begin to out-contract geometric weights. Below this threshold, power-law mixing is superior; above it, geometric mixing is superior.
Iteration Reduction: The reduction in the contraction modulus translates to a dramatic reduction in the number of operator applications required to reduce error by three orders of magnitude. For heavy-tailed power-law weights, the required iterations drop from ~688 (one-step) to ~6, a reduction of two orders of magnitude.
Verification: Experiments on a random tabular MDP verify that the realized contraction ratios respect the theoretical bounds, though the bounds are conservative for non-degenerate problems. The sharpness of the bound is confirmed on a degenerate MDP constructed specifically to attain the worst-case Lipschitz constant.

Significance and Claims
The paper claims to provide a theoretical basis for incorporating long-memory mechanisms directly into distributional critics. By proving that normalized power-law mixtures preserve contraction and converge to the correct fixed point, the work removes the technical obstruction that previously confined fractional calculus methods to the policy side of RL architectures.

The authors emphasize that their results clarify the architecture of frameworks like FracTrace rather than overturning them. They note that while the advantage kernels in FracTrace are non-summable and require truncation, the Bellman mixture operator studied here relies on summable, normalized weights. Consequently, the contraction guarantees hold for the critic if it adopts a summable power-law horizon mixture.

The paper remains modest regarding practical implications, noting that while the theoretical iteration count improves, the computational cost per operator application increases (scaling with the truncation horizon). Therefore, the net wall-clock benefit is an open empirical question. The results are strictly limited to the population-level Bellman operator and do not directly address off-policy settings or stochastic approximation algorithms, which are identified as directions for future work.

Technical Summary: Distributional Bellman Operators with Power-Law Horizon Weights

More like this