{"id":"arxiv/2609.01099","url":"https://arxiv.org/abs/2609.01099","tags":["math.OC"],"score":0,"title":"The Complexity of Approximating the Value in Revealing POMDPs with Long-Run Average Objectives","domain":"math.OC","source":"arxiv","authors":["Ali Asadi","Krishnendu Chatterjee","David Lurie"],"reviews":0,"subject":"math.OC","summary":"We study partially observable Markov decision processes (POMDPs) with long-run average objectives, where the payoff is defined as the limit inferior of the expected average rewards. We consider the computational problem of approximating the long-run average value of a POMDP. In general, the long-run average value of a POMDP is neither computable nor approximable. We therefore consider the subclass of revealing POMDPs. Informally, a POMDP is revealing when the controller observes the underlying state with positive probability at each stage of the process. Our main contributions are threefold.…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-01","reactions":{}}