Concurrent MDPs with Finite Markovian Policies

摘要

The recently defined class of Concurrent Markov Decision Processes (CMDPs) allows one to describe scenario based uncertainty in sequential decision problems like scheduling or admission problems. The resulting optimization problem of computing an optimal policy is NP-hard. This paper introduces a new class of policies for CMDPs on infinite horizons. A mixed integer linear program and an efficient approximation algorithm based on policy iteration are defined for the computation of optimal polices. The proposed approximation algorithm also improves the available approximate value iteration algorithm for the finite horizon . case.