Can I read Geometric Re-Analysis of Classical MDP Solving Algorithms on EtoBox?

Geometric Re-Analysis of Classical MDP Solving Algorithms by Mustafin, Arsenii; Pakharev, Aleksei; Olshevsky, Alex; Paschalidis, Ioannis Ch. is a scholarly article available to read on EtoBox.

What is Geometric Re-Analysis of Classical MDP Solving Algorithms about?

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$.

Author

Mustafin, Arsenii; Pakharev, Aleksei; Olshevsky, Alex; Paschalidis, Ioannis Ch.

Published

2025

Language

EN