LSE - Department of Mathematics

I presented my latest work on Partially Observable Markov Decision Processes, on the complexity of reachability objectives under constant memory policies.

Title

Computational complexity and strategy characterization for small memory policies in Partially Observable Sequential Decision Making

Abstract

Partially Observable Markov Decision Processes (POMDPs) model a controller interacting with an uncertain environment. A fundamental objective is to reach a target state. The general problem is algorithmically impossible: (1) Approximating the maximum probability the controller can guarantee to reach the target is undecidable. (2) even deciding if the maximum guarantee is probability 1 or not is undecidable. Therefore, we study the problem for constant memory policies. Under this restriction, the problem was known to be in between NP and a fundamental problem in geometry. Beyond explaining the computational complexity achieved, I will explain fundamental tools in logic and parameterized Markov Chains.

Here is the presentation: