What makes some POMDPs easy to approximate?
David Hsu, Wee Sun Lee, and Nan Rong · POMDPs are notoriously difficult to solve exactly ( P S P A C E - c o m p le te , undecidable, ...). In practice, point-based algorithms have made dramatic progress in computing approximate s o lu tio n s .
performance on a benchmark problem

T3

Sparsity, smoothness, fully observable state variables, ... drastically reduce computational complexity.
characterized by

·

covering number of belief space · · Small covering number of reachable space  poly. time Small covering number of space reachable under an optimal policy A small cover given The analyses suggest the practical strategy of finding an approximate cover heuristically.

· ·

 NP-hard  poly. time

·

W hy?