# The Value Function Polytope in Reinforcement Learning

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 31 Jan 2019.

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

- [Who Is the Strongest Enemy? Towards Optimal and Efficient Evasion Attacks in Deep RL](https://mlsanity.com/paper/2106.05087/) (2021)
- [Efficient Adversarial Training without Attacking: Worst-Case-Aware Robust Reinforcement Learning](https://mlsanity.com/paper/2210.05927/) (2022)
- [Greedification Operators for Policy Optimization: Investigating Forward and Reverse KL Divergences](https://mlsanity.com/paper/2107.08285/) (2021)
- [The Information Geometry of Unsupervised Reinforcement Learning](https://mlsanity.com/paper/2110.02719/) (2021)
- [Control-Oriented Model-Based Reinforcement Learning with Implicit Differentiation](https://mlsanity.com/paper/2106.03273/) (2021)
- [Metrics and continuity in reinforcement learning](https://mlsanity.com/paper/2102.01514/) (2021)
- [Proto Successor Measure: Representing the Behavior Space of an RL Agent](https://mlsanity.com/paper/2411.19418/) (2024)
- [Generalized Data Distribution Iteration](https://mlsanity.com/paper/2206.03192/) (2022)
- [Non-Adversarial Inverse Reinforcement Learning via Successor Feature Matching](https://mlsanity.com/paper/2411.07007/) (2024)
- [The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs](https://mlsanity.com/paper/2110.07409/) (2021)
- [Frustratingly Easy Regularization on Representation Can Boost Deep Reinforcement Learning](https://mlsanity.com/paper/2205.14557/) (2022)
- [An Entropy Regularization Free Mechanism for Policy-based Reinforcement Learning](https://mlsanity.com/paper/2106.00707/) (2021)
- [GDI: Rethinking What Makes Reinforcement Learning Different From Supervised Learning](https://mlsanity.com/paper/2106.06232/) (2021)
- [The Geometry of Robust Value Functions](https://mlsanity.com/paper/2201.12929/) (2022)
- [Geometric Policy Iteration for Markov Decision Processes](https://mlsanity.com/paper/2206.05809/) (2022)
- [MDP Geometry, Normalization and Reward Balancing Solvers](https://mlsanity.com/paper/2407.06712/) (2024)
- [Functional Acceleration for Policy Mirror Descent](https://mlsanity.com/paper/2407.16602/) (2024)
- [Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes](https://mlsanity.com/paper/2502.09432/) (2025)
- [Convergence Theorems for Entropy-Regularized and Distributional Reinforcement Learning](https://mlsanity.com/paper/2510.08526/) (2025)
- [Topological Foundations of Reinforcement Learning](https://mlsanity.com/paper/2410.03706/) (2024)
- [Model-free Low-Rank Reinforcement Learning via Leveraged Entry-wise Matrix Estimation](https://mlsanity.com/paper/2410.23434/) (2024)
- [Bellman operator convergence enhancements in reinforcement learning algorithms](https://mlsanity.com/paper/2505.14564/) (2025)
- [Policy Gradient with Tree Search: Avoiding Local Optimas through Lookahead](https://mlsanity.com/paper/2506.07054/) (2025)
- [Beyond the Bellman Fixed Point: Geometry and Fast Policy Identification in Value Iteration](https://mlsanity.com/paper/2604.17457/) (2026)
- [Evaluation-Aware Reinforcement Learning](https://mlsanity.com/paper/2509.19464/) (2025)
- [On the Tension Between Optimality and Adversarial Robustness in Policy Optimization](https://mlsanity.com/paper/2512.01228/) (2025)
- [Thermodynamics of Reinforcement Learning Curricula](https://mlsanity.com/paper/2603.12324/) (2026)
- [The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2606.03048/) (2026)
- [Priced Motion Through Optimal Faces: A Normal-Fan Geometry for Non-Stationary Adversarial MDPs](https://mlsanity.com/paper/2606.29092/) (2026)

## Abstract (arXiv)

We establish geometric and topological properties of the space of value functions in finite state-action Markov decision processes. Our main contribution is the characterization of the nature of its shape: a general polytope (Aigner et al., 2010). To demonstrate this result, we exhibit several properties of the structural relationship between policies and value functions including the line theorem, which shows that the value functions of policies constrained on all but one state describe a line segment. Finally, we use this novel perspective to introduce visualizations to enhance the understanding of the dynamics of reinforcement learning algorithms.