The complexity of planning with partially-observable Markov decision processes
Martin Mundhenk · 2000
Contents 1 Introduction 1 2 Partially-Observable Markov Decision Processes 13 2.1 Policies and Performances . . . . . . . . . . . . . . . . . . . . 14 2.2 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 2.3 Representations of POMDPs . . . . . . . . . . . . . . . . . . 24 2.4 Representations of Policies . . . . . . . . . . . . . . . . . . . . 30 2.5 Computational Questions . . . . . . . . . . . . . . . . . . . . 31 3 Complexity Classes 35 4 Short-Term Policy Evaluation 39 4.1 Flat Representations . . . . . . . . . . . . . . . . . . . . . . . 40 Stationary and time-dependent policies . . . . . . . . . . . . 40 Concise and history-dependent policies . . . . . . . . . . . . 44 4.2 Compressed Representations . . . . . . . . . . . . . . . . . . . 48 5 Short-Term Policy Existence for Flat POMDPs 51 5.2 Fully-Observable POMDPs . . . . . . . . . . . . . . . . . . . 54 5.3 POMDPs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 5.4 Non-Approximability for Short