Quasipolynomial-Time Breakthrough for ℓ∞ Contractions: New Algorithm for Stochastic Games

In theoretical computer science, finding fixed points of non-expansive mappings in high-dimensional spaces has long been a core problem. A recent paper titled "A Quasipolynomial Algorithm for ℓ∞ Contractions" proposes a breakthrough algorithm that can compute ε-approximate fixed points of non-expansive mappings under any d-dimensional ℓ∞ norm in quasipolynomial time. This result not only deepens our understanding of the computational complexity of fixed points but also directly implies that simple stochastic games can be solved in quasipolynomial time, bringing new tools to algorithmic game theory and complexity theory.

Algorithm Core: Boosting Argument and Geometric Shrinking

The core of the proposed algorithm lies in a "boosting argument" that gradually shrinks the search region in a geometric progression. Specifically, in each iteration, the algorithm reduces the candidate region by a fixed ratio, thereby achieving ε-approximate accuracy in time (\log(1/\epsilon)^{O(\log^2 d)}). This time complexity is called quasipolynomial because the exponent depends on (\log^2 d), rather than being polynomial or exponential.

Unlike traditional polynomial-time algorithms, this algorithm does not directly construct a fixed point but instead approaches the target by repeatedly shrinking the search space. This approach is particularly effective for high-dimensional problems, as the volume of the search region grows exponentially with dimension, and geometric shrinking can significantly reduce the computational burden. The authors point out that the key to this boosting argument is designing an adaptive region update rule that ensures the approximate fixed point remains within the region after each shrink.

Quasipolynomial time refers to algorithmic complexity of the form (2^{O(\log^k n)}), where (n) is the input size and (k) is a constant. It lies between polynomial time (which reduces to polynomial when (k=1)) and exponential time, and is commonly found in approximation algorithms or parameterized algorithms for (\mathrm{NP})-hard problems. In this context, the time complexity (\log(1/\epsilon)^{O(\log^2 d)}) is quasipolynomial in the dimension (d), because (\log^2 d) appears in the exponent. Quasipolynomial algorithms are often regarded as an intermediate ground—"better than exponential, worse than polynomial"—whose existence often reveals the fine structure of a problem and provides a stepping stone for subsequent improvements to polynomial time.

From Fixed Points to Stochastic Games: New Boundaries of Complexity Classes

The most striking corollary of this algorithm is that simple stochastic games can be solved in quasipolynomial time. Simple stochastic games are a classic model in algorithmic game theory, involving two players and a random node, with the goal of computing winning probabilities. Previously, the exact complexity of solving such games was unknown, and approximate solving was known to be in NP∩coNP, but efficient algorithms were lacking.

The new algorithm reduces the fixed point problem of stochastic games to the fixed point computation of ℓ∞ contraction mappings, directly applying the aforementioned quasipolynomial-time algorithm to obtain a quasipolynomial-time algorithm for solving simple stochastic games. This result lowers the complexity upper bound for simple stochastic games from exponential to quasipolynomial; although it has not yet reached polynomial time, it is an important advance. You might not have noticed that this reduction does not depend on the specific structure of the game, and thus applies to a large class of stochastic game problems.

Simple Stochastic Games (SSG) were introduced by Condon in 1992 and are a two-player zero-sum game model with three types of vertices: choice nodes controlled by Player 1, choice nodes controlled by Player 2, and random nodes (transitioning according to a fixed probability distribution). The goal is to compute the winning probability of reaching a target vertex from a start vertex. The decision version of SSG (whether the winning probability exceeds a given threshold) is known to be in (\mathrm{NP} \cap \mathrm{coNP}), but it is not known whether it is in (\mathrm{P}). It is closely related to algorithms such as strategy iteration and value iteration, and is one of the typical problems in (\mathrm{NP} \cap \mathrm{coNP}) for which no polynomial-time algorithm has been proven. This paper provides the first quasipolynomial-time upper bound by reducing to the fixed point problem of (\ell_\infty) contraction mappings.

Technical Details and Potential Impact

On the technical side, the algorithm's time complexity is (\log(1/\epsilon)^{O(\log^2 d)}), where d is the dimension and ε is the approximation accuracy. This complexity is close to polynomial when d is small but grows rapidly in high dimensions. The paper introduces a recursive dimension reduction strategy that decomposes high-dimensional problems into low-dimensional subproblems to control exponential growth. In the specific implementation, the algorithm uses geometric tools such as sphere intersections and norm equivalence to ensure the effectiveness of the shrinking process.

The potential impact of this work is not limited to stochastic games. Fixed point computation for ℓ∞ contraction mappings has applications in various fields, such as equilibrium computation in economics, adversarial training in machine learning, and stability analysis in control theory. The quasipolynomial-time algorithm provides new theoretical guarantees for these fields, especially in high-dimensional scenarios. However, the algorithm is currently a theoretical result, and practical implementation may require further optimization of constant factors and numerical stability.

Non-expansive mapping refers to a mapping (f) satisfying (|f(x)-f(y)| \le |x-y|), i.e., it does not amplify the distance between any two points. Under the (\ell_\infty) norm, the unit ball is a cube (a polyhedron), whose geometric properties are fundamentally different from the Euclidean ball under the (\ell_2) norm: the (\ell_\infty) ball is not strictly convex, causing many gradient-based algorithms to fail. The existence of fixed points (points satisfying (f(x)=x)) for non-expansive mappings is guaranteed by Brouwer's fixed point theorem, but constructive algorithms (such as Banach fixed point iteration) usually only work for contraction mappings (with contraction factor (<1)). For non-expansive mappings, more complex iterations or geometric methods are generally required, and the relationship between approximation accuracy (\epsilon) and running time is one of the core questions in computational complexity research.

Comparison with Existing Methods

Previously, for the fixed point problem of ℓ∞ contraction mappings, the best known algorithms were exponential-time algorithms based on the simplex method, or polynomial-time algorithms for special structures. The new algorithm achieves quasipolynomial time in the general case for the first time, filling the gap between exponential and polynomial. Compared with contraction mapping problems under the (\ell_2) norm, the (\ell_\infty) norm is more challenging because its unit ball is a polyhedron rather than a smooth sphere, causing traditional gradient methods to fail. The paper bypasses this difficulty by combining geometry and boosting arguments.

Another noteworthy comparison is with algorithms for solving stochastic games. Previously, algorithms for solving simple stochastic games included strategy iteration and value iteration, but their worst-case time complexity was exponential. The new algorithm achieves quasipolynomial time by reducing to the ℓ∞ contraction problem, which is a significant theoretical improvement. Although practical performance may not match heuristic algorithms, this result is quite important for understanding the intrinsic complexity of the problem.

Future Directions and Open Problems

The paper leaves several open problems. First, can the quasipolynomial time be improved to polynomial time? This requires more refined dimension reduction or stronger boosting arguments. Second, is the algorithm applicable to contraction mappings under other norms, such as the ℓp norm (p≠∞)? The current method relies heavily on the special properties of the ℓ∞ norm. Additionally, practical implementation and experimental evaluation of the algorithm are part of future work, especially performance in moderate dimensions.

For stochastic games, a natural question is whether the results can be extended to more general stochastic game models, such as discounted stochastic games or partially observable games. These models are common in reinforcement learning and multi-agent systems but have higher complexity. The authors believe that the ℓ∞ contraction framework may provide a foundation for these extensions, but additional technical obstacles need to be overcome.

Overall, this work is an important advance in theoretical computer science, connecting fixed point computation, game theory, and geometric algorithms, and demonstrating the potential of quasipolynomial-time algorithms in design. Although there is still a gap to practical application, its theoretical value cannot be ignored.

One-line Summary

A new algorithm solves the fixed point problem of ℓ∞ non-expansive mappings in quasipolynomial time and yields a quasipolynomial-time algorithm for simple stochastic games.

Paragraph Summary

The paper presents the first quasipolynomial-time algorithm for non-expansive mappings under the ℓ∞ norm, capable of computing ε-approximate fixed points in time (\log(1/\epsilon)^{O(\log^2 d)}). The core of the algorithm is a boosting argument that gradually shrinks the search region through geometric contraction and uses recursive dimension reduction to control high-dimensional growth. This result directly implies that simple stochastic games can be solved in quasipolynomial time, improving the previous exponential upper bound to quasipolynomial. The paper also discusses potential applications of the algorithm in fields such as economic equilibrium computation and adversarial training, and points out open problems such as improving to polynomial time and extending to other norms.