Algorithms and Data Analysis (ADA) Seminar at King's College London

I presented my latest work on Revealing Partially Observable Markov Decision Processes, which was accepted to AAAI 2026.

Title

Revelations in uncertain sequential decision making: from undecidable to EXPTIME

Abstract

Partially observable Markov decision processes (POMDPs) are a central model for uncertainty in sequential decision making.  The most basic objective is reachability: a target must be eventually visited. The computational problems are:  (a) almost-sure winning: reaching the target with probability 1; (b) limit-sure winning: reaching the target with probability arbitrarily close to 1; and (c) quantitative analysis: approximating the optimal probability of reaching the target. For general POMDPs, almost-sure analysis is EXPTIME-complete, but limit-sure and quantitative analysis are undecidable. A special class of POMDPs, called revealing POMDPs, has been studied recently in several works, where almost-sure analysis was shown to be EXPTIME-complete. In this work, we show that for revealing POMDPs the limit-sure analysis is EXPTIME-complete, and the quantitative analysis is EXPTIME.

The presentation was on a whiteboard.