Geometric Re-Analysis of Classical MDP Solving Algorithms
Arsenii Mustafin, · 2025
Read Geometric Re-Analysis of Classical MDP Solving Algorithms by Arsenii Mustafin, (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-04203.txt.
Introduction
Arsenii Mustafin and co-authors published this theory paper in 2025. Markov decision processes are the standard model for sequential choices under uncertainty, from robotics to operations research. Two classical algorithms solve them: value iteration, which improves value estimates step by step, and policy iteration, which improves whole strategies. A recent geometric reading of these processes views their solutions as shapes in a high-dimensional space.
The authors re-analyze both algorithms through that geometric lens. Looking at the algorithms as movements and projections in this space can expose why they converge at the rates they do. It can also reveal structure that algebraic proofs tend to hide. The paper belongs to a broader effort to unify the theory of these workhorse methods. A shared geometric picture may suggest sharper bounds, cleaner proofs, and ideas for new algorithms.
Catalog record
| CREATOR | Arsenii Mustafin, |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2503-04203
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Geometric Re-Analysis of Classical MDP Solving Algorithms Arsenii Mustafin, Abstract 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 γ \gamma , 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 γ \gamma . 1 Introduction 1.1 History of the Subject and Previous works A Markov Decision Process (MDP) is a widely used mathematical framework for sequential decision-making. It was first introduced in the late 1950s, along with foundational algorithms such as Value Iteration (VI) ( Bellman 1957 ) and Policy Iteration (PI) ( Howard 1960 ) . These algorithms have become the foundation for various theoretical and practical methods for solving MDPs, which today form the backbone of applied Reinforcement Learning (RL). Over the following decades, significant advancements were made, culminating in a comprehensive summary of key results by Puterman in 1990 ( Puterman 1990 ) . In recent years, the growing popularity of practical RL algorithms has renewed interest in MDP analysis, leading to several notable developments. For Value Iteration, Howard 1960 showed that the algorithm’s convergence rate is upper bounded by the discount factor \gamma and that this upper bound is achievable. However, in most practical cases, VI exhibits faster convergence. Subsequent works focused on analyzing this convergence and providing guarantees for MDP instances under additional assumptions ( Puterman 1990 ; Feinberg & Huang 2014 ) . For Policy Iteration, a significant gap in understanding its convergence properties remains. Important progress was made by Ye 2011 ; Hansen et al. 2013 ; Scherrer 2013 , where the authors significantly improved the upper bound on the number of iterations required for convergence in terms of 1-\gamma , where \gamma is the MDP discount factor. At the same time, a separate line of work ( Fearnley 2010 ; Hollanders et al. 2012 ; Hollanders et al. 2016 ) showed that the complexity of PI can be exponential when the discount factor \gamma is not fixed. In this paper, we extend the analysis of VI and PI by leveraging the recently introduced geometric interpretation of MDPs ( Mustafin et al. 2024 ) . In their work, the authors proposed viewing MDPs from a geometric perspective, drawing analogies between common MDP problems and geometric problems. We build on this approach to develop new analytical methods for studying Value Iteration and Policy Iteration. These tools allow us to simplify the analysis and improve convergence results in several cases. 1.2 Motivation and Contribution The primary motivation for this paper is to address existing gaps in the understanding and analysis of fundamental MDP algorithms. In the case of Value Iteration, the gap lies between the convergence rate observed in most settings and the theoretically guaranteed convergence rate. For Policy Iteration, the gap exists between its upper and lower convergence bounds. The geometry-based analysis proposed in this work enhances our understanding of algorithm dynamics and has the potential to guide the design of new algorithms. Our main contributions are as follows: • We develop a new geometry-based framework for analyzing the convergence of Value Iteration and Policy Iteration. In particular, we identify a rotation component in the Value Iteration algorithm and introduce an MDP transformation that modifies the discount factor \gamma . • Using the discount factor transformation, we show that the theoretical convergence of both VI and PI can be improved when the transformation can be applied in a way that preserves the regularity of the MDP. • We show that in the case of a 2-state MDP, the number of iterations required by PI to reach the optimal policy is upper bounded by the number of actions 1 1 1 For us, actions are unique to a state, so using earlier terminology (which we do not use in this paper), the claim is that the number of iterations is upper bounded by the number of state-action pairs. . • For Value Iteration, we show that it benefits from information exchange between states, leading to a convergence rate faster than \gamma when the Markov reward process (MRP) induced by the optimal policy is strongly connected. In this case we improve the total number of iterations from: \mathcal{O}\left(\frac{\log{1/\epsilon}+\log(1/(1-\gamma))}{\log{(1/\gamma)}}\right)\quad\text{to}\quad\mathcal{O}\left(\frac{\log(1/\epsilon)+\log(1/(1-\gamma))}{\log(1/\gamma)+{\color[rgb]{0,0,1}\log(1/\tau^{1/N})}}\right), where \tau^{1/N} is a measure of the mixing rate associated with an optimal policy. While the former convergence rate on the left blows up polynomially as \gamma\rightarrow 1 (due to the \log(1/\gamma) in the denominator which approaches zero as (\gamma-1)/\gamma ), the new convergence on the right rate blows up logarithmically as \gamma\rightarrow 1 . Additionally, we give simplified geometry-based proofs for a several established facts. 2 Mathematical setting 2.1 Basic MDP setting We employ an MDP framework from Mustafin et al. 2024 . An MDP is defined by the tuple \mathcal{M}=\langle\mathcal{S},\mathcal{A},\mathrm{st},\mathcal{P},\mathcal{R},\gamma\rangle , where \mathcal{S}=\{s_{1},\ldots,s_{n}\} represents a finite set of n states, and \mathcal{A} is a finite set containing m possible actions, where each action is defined in a unique state. Therefore, actions in the framework correspond to state-action pairs in earlier literature. This relation is defined by a mapping \mathrm{st} , which maps actions a to the state where it can be chosen. Each action a is characterized by the probability distribution \mathcal{P}(a)=(p^{a}_{1},\dots,p^{a}_{n}) and deterministic rewards r^{a} which are described by \mathcal{R}:\mathcal{A}\to\mathbb{R} . An agent interacting with the MDP follows a policy, which is a map \pi:\mathcal{S}\rightarrow\mathcal{A} that satisfies \mathrm{st}(\pi(s))=s for all s\in\mathcal{S} . We consider deterministic stationary policies, where a single action is chosen for each state throughout the trajectory. If a policy \pi chooses action a in state s , we write a\in\pi . Therefore, a policy \pi can be described as the set of its actions, \pi=\{a_{1},\dots,a_{n}\} . The value of a policy \pi at state s , denoted V^{\pi}(s) , is the expected discounted reward over infinite trajectories starting from s under policy \pi : V^{\pi}(s)=\E\left[\sum_{t=1}^{\infty}\gamma^{t}r_{t}\right], where r_{t} is the reward at time t . The value vector V^{\pi} uniquely satisfies the Bellman equation T^{\pi}V^{\pi}=V^{\pi} , where T^{\pi} is the Bellman operator: (T^{\pi}V)(s)=r_{\pi}+\sum_{s^{\prime}}P\left(s^{\prime}\,|\,\pi(s)\right)\gamma V(s^{\prime}). Evaluating the values of a given policy \pi is known as the Policy Evaluation problem. The main challenge, however, is to identify the optimal policy \pi^{*} that satisfies: V^{\pi^{*}}(s)\geq V^{\pi}(s),\quad\forall\pi,s. This policy can be found by the Policy Iteration algorithm, but each iteration of it requires inverting an n\times n matrix. Alternatively, we may aim to find an approximate solution, \epsilon -optimal policy \pi^{\epsilon} , which satisfies: V^{\pi^{*}}(s)-V^{\pi^{\epsilon}}(s)<\epsilon,\quad\forall s. An \epsilon -optimal policy can be found using the Value Iteration (VI) algorithm. The required number of iterations depends on \epsilon , with each iteration having a computational complexity of \mathcal{O}(nm) . MDP setting presented above was reinterpreted in geometric terms in Mustafin et al. 2024 , and our analyzis relies on this geometric interpretation. In this work the authors suggest to view MDP actions as vectors in a linear space