Abstract
Sequential decision-making under uncertainty is a fundamental problem studied in artificial intelligence (AI) and formal methods, with applications in areas as robotics, healthcare, and finance. Partially observable Markov decision processes (POMDPs) are a standard mathematical model for solving such problems in partially observable environments. POMDPs are very expressive, but computationally intractable. When modeling problems as POMDPs, much of the structure present in the original problem is hidden in the model and remains unexploited, limiting the efficiency of solution algorithms. In this project, we address this challenge by identifying, exploiting, and abstracting the available structure in POMDPs to achieve efficient planning and reinforcement learning (RL) in partially observable environments. We study subclasses of POMDPs and how to exploit the additional structure present there. In particular, we (1) investigate the computational complexity and construct efficient algorithms to solve such subclasses; (2) develop methods to measure the distance of a given POMDP to a subclass instance; and (3) build abstraction schemes for planning and RL in POMDPs, exploiting the subclass structures and distance measures investigated in (1) and (2) with end-to-end performance guarantees. Advancing these three research directions together will lead to more efficient planning and RL methods in partially observable environments with direct applications to many real-world problems.
Researcher(s)
Research team(s)
Funding
Project type(s)