Other Research
Multi-environment POMDPs
Multi-environment partially observable Markov decision processes (POMDPs) are systems in which one agent interacts with a stochastic environment. She has only partial information about the current state of the system, but tries to maximise the sum of the rewards she gets. Contrary to classical POMDPs, she does not know the initial state of the system, and doesn't even have a probability distribution: she must assume the worst case. We show that computing the optimal payoff the agent can obtain, within a finite horizon, is PSPACE-complete, and provide an efficient practical algorithm.
- L. Brice, F. Cano, K. Chatterjee, T. Henzinger, S. Muroya, "Multi-Environment POMDPs with Finite-Horizon Objectives", unpublished (ArXiv)
Robbins' problem
Robbins' problem is a famous open problem, one of the variants of the secretary problem. We used a Markov decision process approach to compute numerically better values than those formerly known (in Principles of Verification: Cycling the Probabilistic Landscape).
- L. Brice, F. T. Bruss, A. Majumdar, J.-F. Raskin, "Algorithms for Robbins' Problem Using Markov Decision Processes", in Principles of Verification: Cycling the Probabilistic Landscape, LNCS 13844, 2023