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

Technical Summary: The Value Function Semi-Algebraic Set in POMDPs

Problem Statement
This work investigates the geometric structure of the set of feasible value functions in infinite-horizon partially observable Markov decision processes (POMDPs) under memoryless stochastic policies. While the geometry of value functions in fully observable Markov decision processes (MDPs) is well-understood—characterized as a union of convex polytopes (Dadashi et al., 2019)—the corresponding structure for POMDPs has remained largely unexplored. The authors address the gap in understanding how partial observability, which introduces non-Markovian dynamics from the agent's perspective and couples decision variables, fundamentally alters the landscape of policy optimization.

Methodology
The authors approach the problem by interpreting the set of feasible value functions as the solution set to a parametric linear system derived from the Bellman equation, where the parameters are the policy variables.

1. Parametric Linear Systems: The Bellman equation $(I - \gamma P^\pi)V^\pi = r^\pi$ is reformulated as a parametric system $A(p)x - b(p) = 0$, where the coefficients depend linearly on the policy parameters $p$.
2. Interval and Parametric Characterization: The authors leverage results from interval linear systems (Oettli & Prager, 1964) and parametric systems (Hladík, 2012). They first establish a characterization using infinitely many piecewise linear inequalities (Theorem 3.9) by decomposing the policy polytope into rectangular parametrizations.
3. Semi-Algebraic Reduction: To obtain a finite description, the authors apply a zonotope-based condition. They demonstrate that a vector $x$ is a feasible value function if and only if the midpoint residual vector lies within the zonotope generated by the deviation vectors of the parametrization. This condition is translated into a system of polynomial equations and inequalities.
4. Explicit Construction: The paper constructs an explicit semi-algebraic description by analyzing the rank of a matrix $C(x)$ formed by the policy parameters and value function constraints. This allows for a stratification of the solution space based on the rank of the underlying linear system.

Key Contributions
The paper provides four primary theoretical contributions:

• Parametric Interpretation: It frames the feasible value functions of (PO)MDPs as the solution set to a Bellman equation parametrized by the policy, enabling explicit descriptions (Section 3).
• Infinite Piecewise Linear Characterization: It provides a necessary and sufficient condition for a value function to be feasible in terms of infinitely many piecewise linear inequalities (Theorem 3.9).
• Finite Semi-Algebraic Description: It derives a description of the feasible set using only finitely many polynomial equations and inequalities, establishing that the set is a semi-algebraic set (Theorem 4.2 and Corollary 4.3).
• Explicit Boundary Construction: It offers an explicit construction of the feasible set boundaries via determinantal conditions on the POMDP parameters, stratified by the rank of the constraint matrix (Theorem 4.4).

Results and Findings

• Geometric Complexity: Unlike fully observable MDPs, where the feasible set is a union of polytopes (linear constraints), the feasible set in POMDPs is a semi-algebraic set defined by nonlinear constraints. This results in curved boundaries and a more intricate geometric structure.
• Dependence on Initial State: The authors demonstrate that, in contrast to MDPs where the optimal policy is independent of the initial state distribution, optimal policies in POMDPs may not be unique and can depend sensitively on the initial state distribution. This is a direct consequence of the non-convex, curved geometry of the feasible set.
• Local Optima: The geometric characterization reveals the emergence of isolated local maximizers of the long-term reward. Experimental simulations on randomly generated POMDPs show that partial observability induces a substantial spread in both value and policy space, with multiple distinct local optima being the norm rather than the exception.
• Memoryless vs. Finite Memory: While extending to finite-memory policies (via observation enhancement) reduces the spread of values, the fundamental geometric complexity induced by partial observability persists, distinguishing it from the fully observable case.

Significance and Claims
The paper claims that this geometric characterization provides new insight into the landscape of policy optimization in both MDPs and POMDPs. Specifically, it:

• Extends the known polyhedral results of MDPs to the substantially more intricate partially observable setting.
• Reveals qualitative phenomena unique to partial observability, such as the dependence of optimal policies on initial state distributions and the existence of isolated local maximizers.
• Suggests that the semi-algebraic structure plays a central role in understanding optimization and learning in partially observable environments.

The authors note that while their results are primarily structural and do not immediately yield efficient algorithms for policy optimization, they lay the mathematical groundwork for future work in algorithm design, convergence guarantees, and robustness analysis. The work is restricted to memoryless stochastic policies and discounted infinite-horizon settings, with extensions to policies with memory or belief-states identified as important open directions.