# Threshold Structure of Optimal Policies in Restart POMDPs

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 10 of its 27 references that are in the map.
- First posted on arXiv 11 Aug 2026.

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

- [Collapsing Bandits and Their Application to Public Health Interventions](https://mlsanity.com/paper/2007.04432/) (2020)
- [Near Optimality of Finite Memory Feedback Policies in Partially Observed Markov Decision Processes](https://mlsanity.com/paper/2010.07452/) (2020)
- [Age of Information: Whittle Index for Scheduling Stochastic Arrivals](https://mlsanity.com/paper/1801.03422/) (2018)
- [A Whittle Index Approach to Minimizing Functions of Age of Information](https://mlsanity.com/paper/1908.10438/) (2019)
- [Hitting Times in Markov Chains with Restart and their Application to Network Centrality](https://mlsanity.com/paper/1503.08548/) (2015)
- [Whittle Index Policy for Crawling Ephemeral Content](https://mlsanity.com/paper/1503.08558/) (2015)
- [MDPs with Setwise Continuous Transition Probabilities](https://mlsanity.com/paper/2011.01325/) (2020)
- [Intermittently Observable Markov Decision Processes](https://mlsanity.com/paper/2302.11761/) (2023)
- [Two families of indexable partially observable restless bandits and Whittle index computation](https://mlsanity.com/paper/2104.05151/) (2021)
- [Constrained Average-Reward Intermittently Observable MDPs](https://mlsanity.com/paper/2504.13823/) (2025)

## Abstract (arXiv)

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.