Threshold Structure of Optimal Policies in Restart POMDPs

• URL: http://arxiv.org/abs/2608.10936v1
• Date: Tue, 11 Aug 2026 14:03:29 GMT
• Title: Threshold Structure of Optimal Policies in Restart POMDPs
• Abstract summary: We study a Restart POMDP (Partially Observable Markov Decision Process) on a general Borel state space.<n>Exploiting a sufficient-statistic representation consisting of the last observed state and the elapsed time since restart, we reduce the problem to a fully observed MDP.
• Score: 2.8686127872933724
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study a Restart POMDP (Partially Observable Markov Decision Process) on a general Borel state space, where the controller either lets the hidden state evolve unobserved or restarts the system and observes the new state. Exploiting a sufficient-statistic representation consisting of the last observed state and the elapsed time since restart, we reduce the problem to a fully observed MDP. Under a natural one-step cost deterioration condition, we prove that optimal policies have a threshold structure in the elapsed time for both the discounted and total undiscounted cost criteria. When the state space is partially ordered and the kernel is stochastically monotone, we further show that the optimal threshold is nonincreasing in the state. For the average cost criterion, under additional assumptions of geometric ergodicity and domination of the transient gain, we establish analogous threshold results via the vanishing discount approach, after showing the uniform boundedness of the optimal thresholds and relative value functions.

Related papers

• Ratio-Variance Regularized Policy Optimization [64.95520246570446]
  We show that explicitly constraining the policy ratio variance provides a principled local approximation to trust-region constraints.<n>We introduce $bf R2bf VPO$ (Ratio-Variance Regularized Policy Optimization), which implements this constraint via a primal-dual optimization framework.
  arXiv  Detail & Related papers  (2026-05-26T09:53:42Z)
• Understanding Quantization of Optimizer States in LLM Pre-training: Dynamics of State Staleness and Effectiveness of State Resets [10.325245543844245]
  We study low-precision exponential moving average (EMA) states and show how quantization can cause many nominal updates to round back to the same stored value.<n>We develop a simple predictive model of stalling that estimates one-step stalling probabilities and characterizes how stalling builds up over time.<n>This perspective provides a mechanistic explanation for why-state resets help in low precision.
  arXiv  Detail & Related papers  (2026-03-17T16:14:36Z)
• Optimal Sample Complexity for Single Time-Scale Actor-Critic with Momentum [62.691095807959215]
  We establish an optimal sample complexity of $O(-2)$ for obtaining an $$-optimal global policy using a single-timescale actor-critic (AC) algorithm.<n>These mechanisms are compatible with existing deep learning architectures and require only minor modifications, without compromising practical applicability.
  arXiv  Detail & Related papers  (2026-02-02T00:35:42Z)
• Monitoring State Transitions in Markovian Systems with Sampling Cost [65.4151496405543]
  A natural approach is a greedy policy that predicts when the expected prediction loss is below the query cost and queries otherwise.<n>We analyze this policy in a Markovian setting, where the optimal (OPT) strategy is a state-dependent threshold policy.<n>For the case of unknown transition probabilities, we propose a projected gradient descent (PSGD)-based learning variant of the greedy policy.
  arXiv  Detail & Related papers  (2025-10-25T15:07:37Z)
• Sampling Complexity of TD and PPO in RKHS [32.00317289826905]
  We revisit Proximal Policy Optimization (PPO) from a function-space perspective.<n>Our results place PPO on a firmer theoretical footing beyond finite-dimensional assumptions.
  arXiv  Detail & Related papers  (2025-09-29T16:19:19Z)
• MDPs with a State Sensing Cost [3.673994921516517]
  We formulate an expected discounted cost Markov Decision Process (MDP)<n>We derive lower bounds on the optimal value function, which allow us to bound the suboptimality gap of any policy.<n>We also propose a computationally efficient algorithm SPI, based on policy improvement, which in practice performs close to the optimal policy.
  arXiv  Detail & Related papers  (2025-05-06T08:06:45Z)
• On the Global Convergence of Policy Gradient in Average Reward Markov Decision Processes [50.68789924454235]
  We present the first finite time global convergence analysis of policy gradient in the context of average reward Markov decision processes (MDPs) Our analysis shows that the policy gradient iterates converge to the optimal policy at a sublinear rate of $Oleft(frac1Tright),$ which translates to $Oleft(log(T)right)$ regret, where $T$ represents the number of iterations.
  arXiv  Detail & Related papers  (2024-03-11T15:25:03Z)
• Hallucinated Adversarial Control for Conservative Offline Policy Evaluation [64.94009515033984]
  We study the problem of conservative off-policy evaluation (COPE) where given an offline dataset of environment interactions, we seek to obtain a (tight) lower bound on a policy's performance. We introduce HAMBO, which builds on an uncertainty-aware learned model of the transition dynamics. We prove that the resulting COPE estimates are valid lower bounds, and, under regularity conditions, show their convergence to the true expected return.
  arXiv  Detail & Related papers  (2023-03-02T08:57:35Z)
• Structural Estimation of Markov Decision Processes in High-Dimensional State Space with Finite-Time Guarantees [39.287388288477096]
  We consider the task of estimating a structural model of dynamic decisions by a human agent based upon the observable history of implemented actions and visited states. This problem has an inherent nested structure: in the inner problem, an optimal policy for a given reward function is identified while in the outer problem, a measure of fit is maximized. We propose a single-loop estimation algorithm with finite time guarantees that is equipped to deal with high-dimensional state spaces.
  arXiv  Detail & Related papers  (2022-10-04T00:11:38Z)
• Robust and Adaptive Temporal-Difference Learning Using An Ensemble of Gaussian Processes [70.80716221080118]
  The paper takes a generative perspective on policy evaluation via temporal-difference (TD) learning. The OS-GPTD approach is developed to estimate the value function for a given policy by observing a sequence of state-reward pairs. To alleviate the limited expressiveness associated with a single fixed kernel, a weighted ensemble (E) of GP priors is employed to yield an alternative scheme.
  arXiv  Detail & Related papers  (2021-12-01T23:15:09Z)
• Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes [0.0]
  We study a planning problem for POMDPs where the system dynamics and measurement channel model is assumed to be known. We find optimal policies for the approximate belief model under mild non-linear filter stability conditions. We also establish a rate of convergence result which relates the finite window memory size and the approximation error bound.
  arXiv  Detail & Related papers  (2020-10-15T00:37:51Z)

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.