2025/03/06 by Arsenii Mustafin, Mustafin, Arsenii, Aleksei Pakharev +5
Computer Science · Decision Sciences · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Formal Methods in Verification #Machine Learning (cs.LG) #Reinforcement Learning in Robotics
paper · pdf · doi:10.48550/arxiv.2503.04203
openalex publication_date 2025/03/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 γ.