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

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.

Reinforcement learning (RL) is a powerful model for statistical learning, where agents learn to interact with their environment by balancing exploration and exploitation. The mathematical framework we use to describe RL problems is known as a Markov decision process (MDP), where the behavior of the agent in the future only depends on the present state, and not on its past behavior or trajectory. Solving a RL problem means finding the optimal policy, or set of decision making rules for each state in the environment, which lead to the maximum reward over time. The ability of an agent to find the optimal policy depends heavily on the information the agent receives from the environment. In partially observable settings, where the agent's read of the current state is obscured in some way, finding an optimal policy is known to be extremely complex in general, and perhaps impossible. In our work, we take a geometric lens towards understanding why partially observable Markov decision processes are so difficult to solve. By leveraging tools from algebraic geometry, we prove that the set over which traditional optimization methods search for the solution is formed by non-linear curves, which are known to hinder optimization. In this way, we extend earlier work which showed that in fully observable settings, the same geometry is formed by linear hyperplanes, and is thus amendable to traditional optimization methods.