On the Computational Complexity of Stochastic Controller Optimization in\n POMDPs

2011/07/15 by Nikos Vlassis, Michael L. Littman, Vlassis, Nikos +3 · 3 citations
Computer Science · #Formal Methods in Verification #Machine Learning and Algorithms #Bayesian Modeling and Causal Inference

paper · pdf · doi:10.48550/arxiv.1107.3090

Abstract

We show that the problem of finding an optimal stochastic 'blind' controller\nin a Markov decision process is an NP-hard problem. The corresponding decision\nproblem is NP-hard, in PSPACE, and SQRT-SUM-hard, hence placing it in NP would\nimply breakthroughs in long-standing open problems in computer science. Our\nresult establishes that the more general problem of stochastic controller\noptimization in POMDPs is also NP-hard. Nonetheless, we outline a special case\nthat is convex and admits efficient global solutions.\n

Cited by

• Memoryless Policy Iteration for Episodic POMDPs
• Scalable Policy-Based RL Algorithms for POMDPs
• Commit to the Bit: Reactive Reinforcement Learning Done Right

Related

• Solving POMDPs by Searching the Space of Finite Policies
• Complexity of finite-horizon Markov decision process problems
• The Complexity of Markov Decision Processes
• Geometry and Determinism of Optimal Stationary Control in Partially Observable Markov Decision Processes
• Planning with Partially Observable Markov Decision Processes: Advances in Exact Solution Method