Controlling Probabilistic Systems Under Partial Observation
summary
Uses Rabin probabilistic automata and partially observable Markov decision processes to pin down what is decidable: emptiness/threshold problems are broadly undecidable (even robust to parameter noise), the exact-one acceptance is PSPACE-complete and quantitative equivalence is polynomial-time, and many reachability/safety questions become EXPTIME-decidable via belief-set constructions. Gives concrete examples (holiday planning, robot maze) where optimal strategies do not exist, finite-memory restrictions or population discretization restore decidability in practice, and flags the positive-frequency Büchi problem for POMDPs as open.
AI-written summary · about
chapters (13)
- 0:00Start
- 1:37Partially observable probabilistic systems
- 9:30Outline
- 9:40Motivating example for probabilistic automata (PA)
- 12:27Control strategies in PA
- 14:24Existence of good enough strategies
- 17:56Anything decidable?
- 20:07Recap on Probabilistic Automata
- 21:28Example of partially observable MDP (POMDP)
- 24:56Infinite horizon objectives
- 26:14Decidability results
- 31:04Life is hard.
- 31:50but there is still hope
related talks
56mOn the Curses of Future and History in Off-policy Evaluation in non-Markov Environments
01h 00mLogic and Probabilistic Circuits 3
11mProbabilistic Programming Meets Automata Theory: Exact Inference using Weighted Automata
24mHigher order programming with probabilistic effects: A model of stochastic memo...
19mPositive Almost-Sure Termination – Complexity and Proof Rules
33mFormal Verification of Probabilistic Deep Reinforcement Learning Policies with(…)
31mLearning to Control Unknown Systems
01h 03mLogic and Probabilistic Circuits 2