# Faster Fixed-Point Methods for Multichain MDPs

arXiv: https://arxiv.org/abs/2506.20910 · HTML: https://mlsanity.com/paper/2506.20910/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 26 Jun 2025.

## Builds on (most cited first, 14 of 14)

- [A First Order Method for Solving Convex Bi-Level Optimization Problems](https://mlsanity.com/paper/1702.03999/) (2017)
- [Efficient Bias-Span-Constrained Exploration-Exploitation in Reinforcement Learning](https://mlsanity.com/paper/1802.04020/) (2018)
- [Towards Tight Bounds on the Sample Complexity of Average-reward MDPs](https://mlsanity.com/paper/2106.07046/) (2021)
- [Near Sample-Optimal Reduction-based Policy Learning for Average Reward MDP](https://mlsanity.com/paper/2212.00603/) (2022)
- [Exact Optimal Accelerated Complexity for Fixed-Point Iterations](https://mlsanity.com/paper/2201.11413/) (2022)
- [A First-Order Approach To Accelerated Value Iteration](https://mlsanity.com/paper/1905.09963/) (2019)
- [Span-Based Optimal Sample Complexity for Weakly Communicating and General Average Reward MDPs](https://mlsanity.com/paper/2403.11477/) (2024)
- [Optimal error bounds for nonexpansive fixed-point iterations in normed spaces](https://mlsanity.com/paper/2108.10969/) (2021)
- [Stochastic Halpern iteration in normed spaces and applications to reinforcement learning](https://mlsanity.com/paper/2403.12338/) (2024)
- [Accelerating Value Iteration with Anchoring](https://mlsanity.com/paper/2305.16569/) (2023)
- [The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis](https://mlsanity.com/paper/2410.07616/) (2024)
- [Optimal Non-Asymptotic Rates of Value Iteration for Average-Reward Markov Decision Processes](https://mlsanity.com/paper/2504.09913/) (2025)
- [Span-Agnostic Optimal Sample Complexity and Oracle Inequalities for Average-Reward RL](https://mlsanity.com/paper/2502.11238/) (2025)
- [Universal bounds for fixed point iterations via optimal transport metrics](https://mlsanity.com/paper/2108.00300/) (2021)

## Built on by (most cited first, 2 of 2)

- [Learning Policy from a Single Trajectory in Average-Reward Markov Decision Process](https://mlsanity.com/paper/2606.16729/) (2026)
- [Persistent-Transient Policy Evaluation for Markov Chains via Minimal Peripheral Quotients](https://mlsanity.com/paper/2602.00474/) (2026)

## Abstract (arXiv)

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.