Solving transition-independent multi-agent mdps with sparse interactions

Scharpff, J, Roijers, DM, Oliehoek, FA, Spaan, MTJ and Deweerdt, MM
(2016) Solving transition-independent multi-agent mdps with sparse interactions. .

[img] Text
Scharpff16AAAI.pdf - Accepted Version

Download (607kB)


© Copyright 2016, Association for the Advancement of Artificial Intelligence ( All rights reserved. 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 fullyobservable multi-agent MDP (MMDP) setting such structure is not present.We propose a new optimal solver for transitionindependent MMDPs, in which agents can only affect their own state but their reward depends on joint transitions. We represent these dependencies 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 branchand- bound policy search algorithm building on CRGs. CoRe typically requires less runtime than available alternatives and finds solutions to previously unsolvable problems.

Item Type: Conference or Workshop Item (UNSPECIFIED)
Depositing User: Symplectic Admin
Date Deposited: 21 Jun 2016 09:11
Last Modified: 13 Dec 2018 13:13
Repository Staff Access