Solving Transition-Independent Multi-agent MDPs with Sparse Interactions

Conference paper (2016)

Authors

J.C.D. Scharpff Algorithmics - EEMCS
Diederik M. Roijers Universiteit van Amsterdam
F.A. Oliehoek Universiteit van Amsterdam, University of Liverpool
M.T.J. Spaan Algorithmics - EEMCS
M.M. de Weerdt Algorithmics - EEMCS
Research Group
Algorithmics (EEMCS) (TU Delft)
Copyright: © 2016 J.C.D. Scharpff, Diederik M. Roijers, F.A. Oliehoek, M.T.J. Spaan, M.M. de Weerdt
Markov Decision Process Transition-independent Multi-agent MDPs Reward interactions Conditional Return Graphs
More Info
expand_more

Published Date

2016

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Department

Software Technology

Research Group

Algorithmics

Abstract

In cooperative multi-agent sequential decision making under uncertainty, agents must coordinate to find an optimal joint policy that maximises joint value. Typical algorithms exploit additive structure in the value function, but in the fully-observable multi-agent MDP (MMDP) setting such structure is not present. We propose a new optimal solver for transition-independent MMDPs, in which agents can only affect their own state but their reward depends on joint transitions. We represent these de- pendencies compactly in conditional return graphs (CRGs). Using CRGs the value of a joint policy and the bounds on partially specified joint policies can be efficiently computed. We propose CoRe, a novel branch-and-bound policy search algorithm building on CRGs. CoRe typically requires less runtime than the available alternatives and finds solutions to previously unsolvable problems.