Search papers, labs, and topics across Lattice.
This paper investigates the structure of optimal policies in Restart POMDPs by employing a sufficient-statistic representation that simplifies the problem to a fully observed MDP. The authors establish that under certain conditions, optimal policies exhibit a threshold structure based on the elapsed time since the last restart, applicable to both discounted and undiscounted cost criteria. Additionally, they demonstrate that in partially ordered state spaces with stochastically monotone kernels, the optimal threshold is nonincreasing in the state, providing insights into average cost criteria under specific assumptions.
Optimal policies in Restart POMDPs reveal a surprising threshold structure that depends on elapsed time, challenging conventional approaches to policy optimization.
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.
