Solving Concurrent Markov Decision Processes

Abstract

Typically, Markov decision problems (MDPs) assume a single action is executed per decision epoch, but in the real world one may frequently exe-cute certain actions in parallel. This paper explores concurrent MDPs, MDPs which allow multiple non-conflicting actions to be executed simultaneously, and presents two new algorithms. Our first approach exploits two prov-ably sound pruning rules, and thus guarantees solution optimality. Our sec-ond technique is a fast, sampling-based algorithm, which produces close-to-optimal solutions extremely quickly. Experiments show that our approaches outperform the existing algorithms producing up to two orders of magnitude speedup. 1