# Geometric Re-Analysis of Classical MDP Solving Algorithms

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 3 of its 13 references that are in the map.
- First posted on arXiv 6 Mar 2025.

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

- [Improved and Generalized Upper Bounds on the Complexity of Policy Iteration](https://mlsanity.com/paper/1306.0386/) (2013)
- [The Value Iteration Algorithm is Not Strongly Polynomial for Discounted Dynamic Programming](https://mlsanity.com/paper/1312.6832/) (2013)
- [MDP Geometry, Normalization and Reward Balancing Solvers](https://mlsanity.com/paper/2407.06712/) (2024)

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

- [Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration](https://mlsanity.com/paper/2604.17457/) (2026)

## Abstract (arXiv)

We build on a recently introduced geometric interpretation of Markov Decision Processes (MDPs) to analyze classical MDP-solving algorithms: Value Iteration (VI) and Policy Iteration (PI). First, we develop a geometry-based analytical apparatus, including a transformation that modifies the discount factor γ, to improve convergence guarantees for these algorithms in several settings. In particular, one of our results identifies a rotation component in the VI method, and as a consequence shows that when a Markov Reward Process (MRP) induced by the optimal policy is irreducible and aperiodic, the asymptotic convergence rate of value iteration is strictly smaller than γ.