{"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","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-08-11","reactions":{}}