🤖 machine learning

Computing Fixpoints of Learned Functions: Chaotic Iteration and Simple Stochastic Games

This paper generalizes the dampened Mann iteration scheme to compute fixpoints of approximated functions by relaxing constraints on learning rates, thereby enabling chaotic iterations for high-dimensional problems and extending applicability to probabilistic models like simple stochastic games.

Original authors: Paolo Baldan, Sebastian Gurke, Barbara König, Florian Wittbold

Published 2026-01-23

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Paolo Baldan, Sebastian Gurke, Barbara König, Florian Wittbold

Original paper licensed under CC BY 4.0 (http://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

The Big Picture: Guessing the Answer to a Moving Target

Imagine you are trying to find the exact center of a foggy room. You can't see the center directly, but you have a flashlight that gives you a slightly blurry, imperfect view of where the center might be. Every time you take a step, you get a new, slightly better (or sometimes slightly worse) glimpse of the room.

In computer science, this "center" is called a fixpoint. It's the stable answer to a complex calculation. Often, we don't know the exact rules of the room (the function); we only have a series of approximations (the blurry flashlights).

The paper asks: How do we keep walking toward the center without getting lost, even if our map keeps changing and we can't look at every corner of the room at once?

The Old Way: The "Mann" Walk

Previously, researchers used a method called Dampened Mann Iteration. Think of this as a specific way of walking:

The Step: You look at your current guess and your new blurry map. You take a step that is a mix of staying put and moving toward the new map.
The Dampener: Sometimes, your new map might be too optimistic (it says the center is closer than it really is). To prevent you from overshooting and running into a wall, you apply a "dampener" (a brake) to slow you down.
The Rules: The old rules said you had to look at every corner of the room at every single step, and your "learning rate" (how big your step is) had to follow a very strict, predictable pattern.

The New Breakthroughs

This paper improves that walking method in three major ways:

1. Walking with a Flexible Pace (Non-Converging Learning Rates)

The Problem: In the old method, you had to take steps that got smaller and smaller in a very specific way, eventually settling into a tiny, precise shuffle.
The New Idea: The authors say, "You don't have to slow down that strictly."

Analogy: Imagine you are hiking. The old rule said you must slow down your pace exactly by 10% every hour. The new rule says you can speed up, slow down, or even stop randomly, as long as you eventually make progress.
Why it helps: This allows the computer to handle situations where the "map" (the approximation) is very noisy or changes unpredictably. It makes the method much more robust, similar to how real-world learning algorithms (like those in self-driving cars) work when data is messy.

2. The "Chaotic" Room Sweep (Updating Only Some Parts)

The Problem: Imagine a room with 10,000 corners. The old method forced you to check every single corner before you could take one step. If the room is huge, this takes forever and is impossible for real-time systems.
The New Idea: Chaotic Iteration.

Analogy: Instead of checking every corner, you just pick one random corner, check it, update your guess for that spot, and move on. You don't need to check the whole room at once.
The Twist: The paper proves that even if you update the corners in a random, "chaotic" order, you will still eventually find the center.
Why it helps: This is a game-changer for large systems (like complex video game AI or massive networks). You don't need to wait for a full system update; you can update parts as they become available, making the process much faster and scalable.

3. Applying to "Game Theory" (Simple Stochastic Games)

The Problem: The old method worked well for single-player scenarios (like a Markov Decision Process, where you just try to maximize your own reward). But what if there are two players? One trying to maximize the score, and one trying to minimize it (like a zero-sum game)?
The New Idea: The authors proved that their flexible, chaotic walking method works for these Simple Stochastic Games (SSGs) too.

Analogy: Imagine two people trying to find a hidden treasure. One wants to get there fast; the other wants to delay you. The old method struggled to prove that your "walking strategy" would still work when the other person is actively trying to mess up your map. The new math proves that even with an opponent, if you keep updating your position using these flexible rules, you will still find the optimal path.

The "Why" Behind the Math

The paper introduces a concept called a "Progressing Scheme."

Think of the "Dampener" (the brake) and the "Learning Rate" (the step size) as two forces pulling on a rope.
The old rules required the step size to stay strong.
The new rules say: As long as the "brake" eventually gets weaker than the "step size" (even if both are fluctuating wildly), you will eventually stop oscillating and settle on the correct answer.

Summary of Results

The paper doesn't just say "this might work." It provides mathematical proofs that:

You can use randomized step sizes (even ones that go to zero or bounce around) and still find the answer.
You can update only a few parts of the system at a time (chaotic iteration) and still find the answer.
This works for Simple Stochastic Games, a type of problem involving two opposing players, which previous methods couldn't handle directly without expensive "speed-ups."

The Takeaway

This paper is like upgrading a GPS navigation system.

Old GPS: Required you to recalculate the entire route every second, using a very rigid formula for how fast you could turn.
New GPS: Allows you to recalculate just the next few turns, handles messy traffic data (noisy approximations) better, and works even if another driver is trying to block your path (stochastic games).

The authors show that by loosening the strict rules on how we update our guesses, we can solve much larger, messier, and more complex problems efficiently.

Technical Summary: Computing Fixpoints of Learned Functions via Chaotic Iteration and Simple Stochastic Games

1. Problem Statement

The paper addresses the problem of computing the least fixpoint ( $\mu f$ ) of a $d$ -dimensional function $f: X \to X$ over the non-negative reals ( $\mathbb{R}^d_+$ ), where $f$ is not known precisely but is only accessible through a sequence of approximations $(f_n)$ . This scenario arises frequently in quantitative systems, such as Markov Decision Processes (MDPs) and Simple Stochastic Games (SSGs), where transition probabilities and rewards must be estimated via sampling.

A primary challenge is that the least fixpoint operator is not necessarily continuous; thus, the sequence of least fixpoints of the approximations $(\mu f_n)$ does not always converge to $\mu f$ . Furthermore, previous work (specifically [4]) relied on Mann-Kleene schemes, which assume:

All components of the vector are updated at every iteration step.
The learning rate sequence $(\alpha_n)$ converges to a value strictly greater than 0 (typically 1).
The approximation sequence $(f_n)$ converges "normally" (i.e., $\sum \|f - f_n\| < \infty$ ), a condition that often requires artificially accelerating the sampling process.

These constraints render the method impractical for high-dimensional systems (where full updates are computationally infeasible) and limit its applicability to model-free reinforcement learning algorithms (like Q-learning) where learning rates must converge to 0 to handle stochastic noise.

2. Methodology

The authors generalize the dampened Mann iteration scheme to overcome these limitations. The standard iteration is defined as:
$x_{n+1} = (1 - \beta_n) \cdot (x_n + \alpha_n \cdot (f_n(x_n) - x_n))$
where $\alpha_n$ is the learning rate and $\beta_n$ is a dampening factor.

The paper introduces three key generalizations:

A. Non-Converging and Vanishing Learning Rates

The authors relax the requirement that $\alpha_n \to 1$ (or $\alpha > 0$ ). They define a progressing scheme where the condition $\lim_{n \to \infty} \beta_n / \alpha_n = 0$ holds. This allows:

$\alpha_n$ to converge to 0 (essential for model-free RL convergence).
$\alpha_n$ to not converge at all (e.g., random selection).
The dampening factor $\beta_n$ to still satisfy $\sum \beta_n = \infty$ and $\lim \beta_n = 0$ .

This relaxation permits the convergence condition on approximations to be weakened from $\sum \|f - f_n\| < \infty$ to $\sum \alpha_n \|f - f_n\| < \infty$ . When $\alpha_n \to 0$ , this condition is significantly easier to satisfy.

B. Generalized (Vector) Parameters and Chaotic Iteration

The parameters $\alpha_n$ and $\beta_n$ are generalized from scalars to vectors in $[0, 1]^d$ . This enables chaotic iteration, where only a subset of components $I_n \subseteq \{1, \dots, d\}$ is updated at step $n$ :
$x_{n+1}(i) = \begin{cases} (1 - \beta_n(i)) \cdot (x_n(i) + \alpha_n(i) \cdot (f_n(x_n) - x_n)(i)) & \text{if } i \in I_n \\ x_n(i) & \text{if } i \notin I_n \end{cases}$
To ensure convergence in this asynchronous setting, the authors introduce a generalized progressing scheme. This requires that dampening factors decrease "fairly" across all dimensions: there must exist a sequence of time steps such that between any two steps, every component is updated at least once, and the sum of the minimum dampening factors over these intervals diverges to infinity.

C. Convergence Proofs for Approximated Functions

The paper establishes convergence for sequences $(f_n)$ that are monotone and non-expansive (1-Lipschitz).

Exact Case: If $f$ is known, progressing generalized schemes converge to $\mu f$ .
Approximated Case: Convergence is guaranteed if $\lim_{n \to \infty} \mu(\sup_{k \ge n} f_k) = \mu f$ . This condition holds if $(f_n)$ converges monotonically to $f$ or if the limit function $f$ is a Picard operator (has a unique fixpoint and iterates converge to it).

3. Key Contributions and Results

Generalization of Dampened Mann Iteration: The authors prove that dampened Mann iteration works with learning rates that converge to 0 or do not converge, and with vector-valued parameters enabling chaotic updates.
Application to Simple Stochastic Games (SSGs): The paper demonstrates that dampened Mann iteration applies directly to SSGs. Unlike previous work which required "speeding up" sampling to enforce normal convergence (which is costly), this method works with standard sampling sequences. This is achieved by proving that the least fixpoint operator is continuous for SSGs under sampling.
Extension to Behavioral Metrics: The results imply that dampened Mann iteration can be used to compute behavioral metrics (e.g., probabilistic bisimilarity distances) in approximated settings, offering a robust alternative to methods sensitive to small perturbations in transition probabilities.
Numerical Experiments: The authors conducted experiments on 50 randomly generated SSGs.
- Learning Rates: They compared schemes with vanishing ( $\alpha_n = 1/n^\epsilon$ ) and random ( $\alpha_n \sim U[0,1]$ ) learning rates against standard relaxed Mann-Kleene schemes. Results showed similar convergence speeds, suggesting that vanishing rates do not hinder convergence in faultless sampling scenarios.
- Chaotic Iteration: They tested chaotic variants where only one randomly chosen state is updated per step. The results indicated that chaotic iteration yields convergence speeds comparable to full updates (when normalized for computational effort) while allowing for intermediate results and potentially lower memory footprints.

4. Significance and Claims

The paper claims that its generalizations are essential for bridging the gap between theoretical fixpoint iteration and practical reinforcement learning algorithms:

Model-Free RL: By allowing $\alpha_n \to 0$ , the theory now aligns with algorithms like Q-learning, where updates depend on current samples rather than estimated probabilities.
Scalability: By enabling chaotic iteration, the method becomes applicable to high-dimensional systems where full vector updates are infeasible.
Robustness: The relaxation of convergence conditions on $(f_n)$ allows for the use of standard sampling strategies without the need for computationally expensive "speed-up" mechanisms to enforce normal convergence.
SSG Solvability: The work resolves an open question regarding whether dampened Mann iteration works "out of the box" for SSGs, proving it does so without requiring the specific structural assumptions (like power contractions) that limited previous approaches.

The authors maintain a modest tone, noting that while chaotic iteration with random component selection incurs no additional cost in convergence speed, informed heuristics for component selection (e.g., based on visitation frequency) could further improve efficiency, a direction they plan to explore. Similarly, they suggest future work on applying these results to limit-average convergence scenarios typical in stochastic approximation theory.