Partially observable Markov decision processes (POMDPs) are flexible enough to represent many types of probabilistic uncertainty making them suitable for real-world decision and control problems. However, POMDPs are notoriously difficult to solve. Even for discrete state and observation spaces, decision problems related to finite horizon POMDPs are PSPACE-complete. Worse, real-world problems often have continuous (i.e. uncountably infinite) state, action, and observation spaces. In this talk, I will demonstrate that, surprisingly, there are online algorithms that can find arbitrarily close-to-optimal policies with no direct theoretical complexity dependence on the size of the state or observation spaces. Specifically, these algorithms use particle filtering and the sparse sampling approach which previously provided similar guarantees for MDPs. Although the theoretical results are much too loose to be used directly for safety guarantees, I will demonstrate how the approach can be used to construct algorithms that are very scalable in practice, for example planning with learned models and high-dimensional image observations and constructing safe and efficient plans in POMDPs with hundreds of dimensions using shielding. I will also discuss challenges in extending this approach further to multi-agent settings.

Bio

Zachary Sunberg is an Assistant Professor in the Ann and H.J. Smead Aerospace Engineering Sciences Department and director of the Autonomous Decision and Control Lab. He earned Bachelors and Masters degrees in Aerospace Engineering from Texas A&M University and a PhD in Aeronautics and Astronautics at Stanford University in the Stanford Intelligent Systems Lab. Before joining the University of Colorado faculty, he served as a postdoctoral scholar at the University of California, Berkeley in the Hybrid Systems Lab. His research is focused on safe and efficient operation of autonomous vehicles and systems on the ground, in the air, and in space. A particular emphasis is on handling uncertainty using the partially observable Markov decision process and game formalisms.