Mixed-integer linear programming for transition-independent decentralized MDPs
Jianhui Wu, Edmund H. Durfee · 2006
The class of problems solved in this paper is a subclass of decentralized Markov decision processes (Dec-MDPs) where multiple cooperative agents are tied together through the rewards of joint tasks and the actions taken by one agent do not impact other agents ’ transitions. Each agent can fully observe its own local state but can only have a partial view of the global environment. We present a novel formulation of this transition-independent Dec-MDP problem as a mixed integer linear program (MILP) that can efficiently build near-optimal joint policies for the cooperative agents. Our experiments demonstrate that our MILP-based algorithm can have better anytime performance than existing approaches, and thus represents a promising new strategy for multiagent policy coordination. 1