On the Computational Complexity of Stochastic Controller Optimization in POMDPs

DOI10.1145/2382559.2382563zbMath1322.68111arXiv1107.3090OpenAlexW2962946825MaRDI QIDQ2947572

David Barber, Michael L. Littman, Nikos Vlassis

Publication date: 24 September 2015

Published in: ACM Transactions on Computation Theory (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1107.3090

zbMATH Keywords

computational complexitynonlinear optimizationpartially observable Markov decision processcomputations on polynomialsbilinear programsum-of-square-roots problemstochastic controllerMotzkin-Straus theoremmatrix fractional program

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Markov and semi-Markov decision processes (90C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items (5)

The complexity of reachability in parametric Markov decision processes ⋮ Algebraic optimization of sequential decision problems ⋮ Parameter synthesis in Markov models: a gentle survey ⋮ On the Complexity of Reachability in Parametric Markov Decision Processes ⋮ Optimizing active surveillance for prostate cancer using partially observable Markov decision processes

This page was built for publication: On the Computational Complexity of Stochastic Controller Optimization in POMDPs