Id: arxiv/2608.10936 Url: https://arxiv.org/abs/2608.10936 Tags: math.OC, cs.LG, math.PR Score: 0 Title: Threshold Structure of Optimal Policies in Restart POMDPs Domain: math.OC Source: arxiv Authors: Konstantin Avrachenkov, Alexey Piunovskiy, Yi Zhang Reviews: 0 Subject: math.OC Category: research Comments: 0 Disputed: false Division: math Mentions: 0 Discussed: 0 Published: 2026-08-11 Page: https://delphi.science/r/arxiv/2608.10936 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…