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

• URL: http://arxiv.org/abs/2606.03048v1
• Date: Tue, 02 Jun 2026 02:30:49 GMT
• Title: The Value Function Semi-Algebraic Set in Partially Observable Markov Decision Processes
• Abstract summary: We study the geometry of feasible value functions in infinite-horizon partially observable Markov decision processes (POMDPs) under memoryless policies.<n>Our main contribution is a characterization of the feasible set of value functions as a semi-algebraic set.<n>Our geometric characterization provides new insight into the landscape of policy optimization in both MDPs and POMDPs.
• Score: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Uniform matrix product states with a boundary [0.09999629695552194]
  We introduce a generalized canonical form for uniform MPS with a boundary matrix.<n>This canonical form reveals that any such MPS can be represented as a block-invertible matrix product operator.<n>Our results establish a unified theoretical foundation for uniform MPS with boundaries.
  arXiv  Detail & Related papers  (2025-12-12T19:00:06Z)
• Horizon-Free Regret for Linear Markov Decision Processes [92.02082223856479]
  A recent line of works showed regret bounds in reinforcement learning can be (nearly) independent of planning horizon. We give the first horizon-free bound for the popular linear Markov Decision Process (MDP) setting. In contrast to prior works which explicitly estimate the transition model and compute the inhomogeneous value functions, we directly estimate the value functions and confidence sets.
  arXiv  Detail & Related papers  (2024-03-15T23:50:58Z)
• Abstraction-based Probabilistic Stability Analysis of Polyhedral Probabilistic Hybrid Systems [6.574517227976925]
  We consider the problem of probabilistic stability analysis of a subclass of Hybrid Systems, namely, Polyhedral Probabilistic Hybrid Systems (PPHS) We present an abstraction-based analysis framework that consists of constructing a finite Markov Decision Processes (MDP) Our experimental analysis demonstrates the feasibility of the approach in successfully verifying probabilistic stability on PPHS of various dimensions and sizes.
  arXiv  Detail & Related papers  (2023-03-29T15:29:30Z)
• PAC Reinforcement Learning for Predictive State Representations [60.00237613646686]
  We study online Reinforcement Learning (RL) in partially observable dynamical systems. We focus on the Predictive State Representations (PSRs) model, which is an expressive model that captures other well-known models. We develop a novel model-based algorithm for PSRs that can learn a near optimal policy in sample complexity scalingly.
  arXiv  Detail & Related papers  (2022-07-12T17:57:17Z)
• Provably Efficient Reinforcement Learning in Partially Observable Dynamical Systems [97.12538243736705]
  We study Reinforcement Learning for partially observable dynamical systems using function approximation. We propose a new textitPartially Observable Bilinear Actor-Critic framework, that is general enough to include models such as POMDPs, observable Linear-Quadratic-Gaussian (LQG), Predictive State Representations (PSRs), as well as a newly introduced model Hilbert Space Embeddings of POMDPs and observable POMDPs with latent low-rank transition.
  arXiv  Detail & Related papers  (2022-06-24T00:27:42Z)
• Reinforcement Learning from Partial Observation: Linear Function Approximation with Provable Sample Efficiency [111.83670279016599]
  We study reinforcement learning for partially observed decision processes (POMDPs) with infinite observation and state spaces. We make the first attempt at partial observability and function approximation for a class of POMDPs with a linear structure.
  arXiv  Detail & Related papers  (2022-04-20T21:15:38Z)
• The Geometry of Memoryless Stochastic Policy Optimization in Infinite-Horizon POMDPs [0.0]
  We consider the problem of finding the best memoryless policy for an infinite-horizon partially observable decision process. We show that the discounted state-action frequencies and the expected cumulative reward are the functions of the policy, whereby the degree is determined by the degree of partial observability.
  arXiv  Detail & Related papers  (2021-10-14T14:42:09Z)
• Permutation Invariant Policy Optimization for Mean-Field Multi-Agent Reinforcement Learning: A Principled Approach [128.62787284435007]
  We propose the mean-field proximal policy optimization (MF-PPO) algorithm, at the core of which is a permutation-invariant actor-critic neural architecture. We prove that MF-PPO attains the globally optimal policy at a sublinear rate of convergence. In particular, we show that the inductive bias introduced by the permutation-invariant neural architecture enables MF-PPO to outperform existing competitors.
  arXiv  Detail & Related papers  (2021-05-18T04:35:41Z)
• A maximum-entropy approach to off-policy evaluation in average-reward MDPs [54.967872716145656]
  This work focuses on off-policy evaluation (OPE) with function approximation in infinite-horizon undiscounted Markov decision processes (MDPs) We provide the first finite-sample OPE error bound, extending existing results beyond the episodic and discounted cases. We show that this results in an exponential-family distribution whose sufficient statistics are the features, paralleling maximum-entropy approaches in supervised learning.
  arXiv  Detail & Related papers  (2020-06-17T18:13:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.