Inﬂuence-Based Policy Abstraction for Weakly-Coupled Dec-POMDPs - Witwicki, Stefan; Durfee, Edmund (Proceedings of the International Conference on Automated Planning and Scheduling, 2010)
Decentralized POMDPs are powerful theoretical models for coordinating agents’ decisions in uncertain environments, but the generally-intractable complexity of optimal joint policy construction presents a signiﬁcant obstacle in applying Dec-POMDPs to problems where many agents face many policy choices. Here, we argue that when most agent choices are independent of other agents’ choices, much of this complexity can be avoided: instead of coordinating full policies, agents need only coordinate policy abstractions that explicitly convey the essential interaction inﬂuences. To this end, we develop a novel framework for inﬂuence-based policy abstraction for weakly-coupled transition-dependent Dec-POMDP problems that subsumes several existing approaches. In addition to formally characterizing the space of transition-dependent inﬂuences, we provide a method for computing optimal and approximately-optimal joint policies. We present an initial empirical analysis, over problems with commonly-studied ﬂavors of transition-dependent inﬂuences, that demonstrates the potential computational beneﬁts of inﬂuence-based abstraction over state-of-the-art optimal policy search methods.