Multi-Environment POMDPs with Finite-Horizon Objectives
Léonard Brice, Filip Cano, Krishnendu Chatterjee, Thomas A. Henzinger, Stefanie Muroya
原文摘要
Partially Observable Markov Decision Processes (POMDPs) are systems in which one agent interacts with a stochastic environment, and receives only partial information about the current state. In a multi-environment POMDP (MEPOMDP), the initial state is unknown, and assumed to be adversarially chosen. In this work we focus on computing the optimal value and policy in MEPOMDPs with finite-horizon objectives. That problem is known to be PSPACE-complete in POMDPs. The extension is nontrivial: MEPOMDPs require reasoning about beliefs and payoffs across environments, and deterministic policies are no longer enough for optimal payoff. While the lower bound transfers immediately, the upper bound requires new techniques: we prove that mixtures of at most $n$ deterministic policies suffice for $n$ environments and show how to explore them without storing exponential-size policy descriptions. Our main results are as follows: (1) we establish that it is also PSPACE-complete in the more general setting of MEPOMDPs; (2) we present a practical algorithm and evaluate it on classical benchmarks, significantly outperforming the only previously known algorithm.
cs.AI