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 setting (MMDP) 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 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 branch-and-bound policy search algorithm building on CRGs. CoRe typically requires less runtime than the available alternatives and finds solutions to problems previously unsolvable.

文章提出了一种新的用于转移独立多智能体决策问题的最优解算法CoRe，该算法利用了条件返回图的紧凑表示方法来计算联合策略的价值和局部策略的下限，并能够有效地解决一些此前无法解决的问题。

使用稀疏交互解决转移独立的多智体MDPs（扩展版本）