An Iterative Algorithm for Solving Constrained Decentralized Markov Decision Processes
Aurélie Beynier, Abdel‐Illah Mouaddib · 2006
Despite the significant progress to extend Markov Decision Processes (MDP) to cooperative multi-agent systems, developing approaches that can deal with realistic problems remains a serious challenge. Existing approaches that solve Decentralized Markov Decision Processes (DEC-MDPs) suffer from the fact that they can only solve relatively small problems without complex constraints on task execution. OC-DEC-MDP has been introduced to deal with large DEC-MDPs under resource and temporal constraints. However, the algorithm developed to solve this class of DEC-MDPs has some limits: it suffers from overestimation of opportunity cost and restricts policy improvement. In this paper, we propose to overcome these limits by first introducing the notion of Expected Opportunity Cost to better assess the influence of a decision on the others. We then describe an iterative version of the algorithm that can be used to iterate the improvement process leading to higher quality solutions in some settings. 1