# Geometric Policy Iteration for Markov Decision Processes

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

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 33 references that are in the map.
- First posted on arXiv 12 Jun 2022.

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

- [The Value-Improvement Path: Towards Better Representations for Reinforcement Learning](https://mlsanity.com/paper/2006.02243/) (2020)
- [A Geometric Perspective on Optimal Representations for Reinforcement Learning](https://mlsanity.com/paper/1901.11530/) (2019)
- [The Information Geometry of Unsupervised Reinforcement Learning](https://mlsanity.com/paper/2110.02719/) (2021)
- [On the Complexity of Solving Markov Decision Problems](https://mlsanity.com/paper/1302.4971/) (2013)
- [The Value Function Polytope in Reinforcement Learning](https://mlsanity.com/paper/1901.11524/) (2019)
- [Improved and Generalized Upper Bounds on the Complexity of Policy Iteration](https://mlsanity.com/paper/1306.0386/) (2013)
- [The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs](https://mlsanity.com/paper/2110.07409/) (2021)
- [The Geometry of Robust Value Functions](https://mlsanity.com/paper/2201.12929/) (2022)
- [On the Complexity of Policy Iteration](https://mlsanity.com/paper/1301.6718/) (2013)
- [Policy iteration for perfect information stochastic mean payoff games with bounded first return times is strongly polynomial](https://mlsanity.com/paper/1310.4953/) (2013)

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

- [Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation](https://mlsanity.com/paper/2410.23434/) (2024)
- [Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration](https://mlsanity.com/paper/2604.17457/) (2026)
- [The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2606.03048/) (2026)

## Abstract (arXiv)

Recently discovered polyhedral structures of the value function for finite state-action discounted Markov decision processes (MDP) shed light on understanding the success of reinforcement learning. We investigate the value function polytope in greater detail and characterize the polytope boundary using a hyperplane arrangement. We further show that the value space is a union of finitely many cells of the same hyperplane arrangement and relate it to the polytope of the classical linear programming formulation for MDPs. Inspired by these geometric properties, we propose a new algorithm, Geometric Policy Iteration (GPI), to solve discounted MDPs. GPI updates the policy of a single state by switching to an action that is mapped to the boundary of the value function polytope, followed by an immediate update of the value function. This new update rule aims at a faster value improvement without compromising computational efficiency. Moreover, our algorithm allows asynchronous updates of state values which is more flexible and advantageous compared to traditional policy iteration when the state set is large. We prove that the complexity of GPI achieves the best known bound Oleft(frac|A|1 - γlog frac11-γright) of policy iteration and empirically demonstrate the strength of GPI on MDPs of various sizes.