# The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processes

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 13 of its 48 references that are in the map.
- First posted on arXiv 2 Jun 2026.

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

- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Partially Observable Markov Decision Processes in Robotics: A Survey](https://mlsanity.com/paper/2209.10342/) (2022)
- [Approximate information state for approximate planning and reinforcement learning in partially observed systems](https://mlsanity.com/paper/2010.08843/) (2020)
- [The Value Function Polytope in Reinforcement Learning](https://mlsanity.com/paper/1901.11524/) (2019)
- [Sample-Efficient Reinforcement Learning of Partially Observable Markov Games](https://mlsanity.com/paper/2206.01315/) (2022)
- [Partially Observable RL with B-Stability: Unified Structural Condition and Sharp Sample-Efficient Algorithms](https://mlsanity.com/paper/2209.14990/) (2022)
- [Learning Reward Machines: A Study in Partially Observable Reinforcement Learning](https://mlsanity.com/paper/2112.09477/) (2021)
- [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)
- [Geometric Policy Iteration for Markov Decision Processes](https://mlsanity.com/paper/2206.05809/) (2022)
- [Future memories are not needed for large classes of POMDPs](https://mlsanity.com/paper/2205.02580/) (2022)
- [Solving infinite-horizon POMDPs with memoryless stochastic policies in state-action space](https://mlsanity.com/paper/2205.14098/) (2022)
- [Algebraic optimization of sequential decision problems](https://mlsanity.com/paper/2211.09439/) (2022)

## Abstract (arXiv)

We study the geometry of feasible value functions in infinite-horizon partially observable Markov decision processes (POMDPs) under memoryless stochastic policies. Our main contribution is a characterization of the feasible set of value functions as a semi-algebraic set, defined by explicit polynomial inequalities determined by the transition dynamics, observation kernel, and reward structure of the POMDP. This result extends prior work for fully observable Markov decision processes, where the feasible set is known to be a polytope, to the substantially more intricate partially observable setting. In contrast to the polyhedral structure arising in MDPs, partial observability induces fundamentally nonlinear constraints, leading to a richer and more complex geometric structure. Our geometric characterization provides new insight into the landscape of policy optimization in both MDPs and POMDPs, and reveals qualitative phenomena unique to partial observability, including the emergence of isolated local maximizers of the long-term reward and their dependence on the initial state distribution.