Faster Fixed-Point Methods for Multichain MDPs

arXiv stat.ML / 4/23/2026

💬 OpinionIdeas & Deep AnalysisModels & Research

共有:

Key Points

The paper studies value-iteration (VI) methods for multichain Markov decision processes (MDPs) under the average-reward criterion, a setting that is hard due to non-contractivity and non-unique Bellman solutions.
It argues that, in multichain MDPs, an optimal policy must both optimize long-run performance within each strongly connected component and solve a “navigation” problem of steering toward the best connected component.
The authors develop new algorithms that improve how VI handles this navigation subproblem, leading to faster convergence for multichain MDPs.
The work also contributes broadly reusable theory, including connections between average-reward and discounted problems, optimal fixed-point methods for discounted VI in general Banach spaces, and refined convergence/error and suboptimality analyses.
Overall, the results strengthen the theoretical foundations of VI approaches by delivering sharper complexity and convergence-rate guarantees for both discounted and average-reward formulations.

Abstract

We study value-iteration (VI) algorithms for solving general (a.k.a. multichain) Markov decision processes (MDPs) under the average-reward criterion, a fundamental but theoretically challenging setting. Beyond the difficulties inherent to all average-reward problems posed by the lack of contractivity and non-uniqueness of solutions to the Bellman operator, in the multichain setting an optimal policy must solve the navigation subproblem of steering towards the best connected component, in addition to optimizing long-run performance within each component. We develop algorithms which better solve this navigational subproblem in order to achieve faster convergence for multichain MDPs, obtaining improved rates of convergence and sharper measures of complexity relative to prior work. Many key components of our results are of potential independent interest, including novel connections between average-reward and discounted problems, optimal fixed-point methods for discounted VI which extend to general Banach spaces, new sublinear convergence rates for the discounted value error, and refined suboptimality decompositions for multichain MDPs. Overall our results yield faster convergence rates for discounted and average-reward problems and expand the theoretical foundations of VI approaches.