# The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 82 references that are in the map.
- First posted on arXiv 14 Oct 2021.

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

- [On the Global Convergence Rates of Softmax Policy Gradient Methods](https://mlsanity.com/paper/2005.06392/) (2020)
- [Global Optimality Guarantees For Policy Gradient Methods](https://mlsanity.com/paper/1906.01786/) (2019)
- [Reward is enough for convex MDPs](https://mlsanity.com/paper/2106.00661/) (2021)
- [Pure and Spurious Critical Points: a Geometric Study of Linear Networks](https://mlsanity.com/paper/1910.01671/) (2019)
- [The Value Function Polytope in Reinforcement Learning](https://mlsanity.com/paper/1901.11524/) (2019)
- [The Euclidean distance degree of an algebraic variety](https://mlsanity.com/paper/1309.0049/) (2013)
- [What is Decidable about Partially Observable Markov Decision Processes with ω-Regular Objectives](https://mlsanity.com/paper/1309.2802/) (2013)
- [The act of remembering: a study in partially observable reinforcement learning](https://mlsanity.com/paper/2010.01753/) (2020)
- [Algorithms in Real Algebraic Geometry: A Survey](https://mlsanity.com/paper/1409.1534/) (2014)
- [Open Problem: Approximate Planning of POMDPs in the class of Memoryless Policies](https://mlsanity.com/paper/1608.04996/) (2016)
- [Wasserstein Distance to Independence Models](https://mlsanity.com/paper/2003.06725/) (2020)
- [Geometry and Determinism of Optimal Stationary Control in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/1503.07206/) (2015)
- [Geometry of Policy Improvement](https://mlsanity.com/paper/1704.01785/) (2017)
- [Linear Programming for Decision Processes with Partial Information](https://mlsanity.com/paper/1811.08880/) (2018)

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

- [Geometry and convergence of natural policy gradient methods](https://mlsanity.com/paper/2211.02105/) (2022)
- [Fisher-Rao Gradient Flows of Linear Programs and State-Action Natural Policy Gradients](https://mlsanity.com/paper/2403.19448/) (2024)
- [Geometric Policy Iteration for Markov Decision Processes](https://mlsanity.com/paper/2206.05809/) (2022)
- [Solving infinite-horizon POMDPs with memoryless stochastic policies in state-action space](https://mlsanity.com/paper/2205.14098/) (2022)
- [On Minimizing Adversarial Counterfactual Error in Adversarial RL](https://mlsanity.com/paper/2406.04724/) (2024)
- [Optimal Rates of Convergence for Entropy Regularization in Discounted Markov Decision Processes](https://mlsanity.com/paper/2406.04163/) (2024)
- [On shallow planning under partial observability](https://mlsanity.com/paper/2407.15820/) (2024)
- [Memoryless Policy Iteration for Episodic POMDPs](https://mlsanity.com/paper/2512.11082/) (2025)
- [The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processes](https://mlsanity.com/paper/2606.03048/) (2026)

## Abstract (arXiv)

We consider the problem of finding the best memoryless stochastic policy for an infinite-horizon partially observable Markov decision process (POMDP) with finite state and action spaces with respect to either the discounted or mean reward criterion. We show that the (discounted) state-action frequencies and the expected cumulative reward are rational functions of the policy, whereby the degree is determined by the degree of partial observability. We then describe the optimization problem as a linear optimization problem in the space of feasible state-action frequencies subject to polynomial constraints that we characterize explicitly. This allows us to address the combinatorial and geometric complexity of the optimization problem using recent tools from polynomial optimization. In particular, we estimate the number of critical points and use the polynomial programming description of reward maximization to solve a navigation problem in a grid world.