Decentralized Planning in Stochastic Environments with Submodular Rewards

Authors

  • Rajiv Kumar Singapore Management University
  • Pradeep Varakantham Singapore Management University
  • Akshat Kumar Singapore Management University

DOI:

https://doi.org/10.1609/aaai.v31i1.10709

Keywords:

Multiagent Systems, Planning under uncertainty

Abstract

Decentralized Markov Decision Process (Dec-MDP) provides a rich framework to represent cooperative decentralized and stochastic planning problems under transition uncertainty. However, solving a Dec-MDP to generate coordinated yet decentralized policies is NEXP-Hard. Researchers have made significant progress in providing approximate approaches to improve scalability with respect to number of agents. However, there has been little or no research devoted to finding guarantees on solution quality for approximate approaches considering multiple (more than 2 agents) agents. We have a similar situation with respect to the competitive decentralized planning problem and the Stochastic Game (SG) model. To address this, we identify models in the cooperative and competitive case that rely on submodular rewards, where we show that existing approximate approaches can provide strong quality guarantees ( a priori, and for cooperative case also posteriori guarantees). We then provide solution approaches and demonstrate improved online guarantees on benchmark problems from the literature for the cooperative case.

Downloads

Published

2017-02-12

How to Cite

Kumar, R., Varakantham, P., & Kumar, A. (2017). Decentralized Planning in Stochastic Environments with Submodular Rewards. Proceedings of the AAAI Conference on Artificial Intelligence, 31(1). https://doi.org/10.1609/aaai.v31i1.10709

Issue

Section

AAAI Technical Track: Multiagent Systems