Taming Decentralized POMDPs: Towards Efficient Policy Computation for Multiagent Settings

Nair, Ranjit; Tambe, Milind; Yokoo, Makoto; Pynadath, David V.; Marsella, Stacy

Taming Decentralized POMDPs: Towards Efficient Policy Computation for Multiagent Settings

Ranjit Nair, Milind Tambe, Makoto Yokoo, David V. Pynadath, Stacy Marsella

Download BibTeX Cite

Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence. Pages 705-710.

Abstract

The problem of deriving joint policies for a group of agents that maximize some joint reward function can be modeled as a decentralized partially observable Markov decision process (POMDP). Yet, despite the growing importance and applications of decentralized POMDP models in the multiagents arena, few algorithms have been developed for efficiently deriving joint policies for these models. This paper presents a new class of locally optimal algorithms called "Joint Equilibriumbased search for policies (JESP)". We first describe an exhaustive version of JESP and subsequently a novel dynamic programming approach to JESP. Our complexity analysis reveals the potential for exponential speedups due to the dynamic programming approach. These theoretical results are verified via empirical comparisons of the two JESP versions with each other and with a globally optimal brute-force search algorithm. Finally, we prove piece-wise linear and convexity (PWLC) properties, thus taking steps towards developing algorithms for continuous belief states.

Ranjit Nair, Milind Tambe, Makoto Yokoo, David V. Pynadath, and Stacy Marsella. 2003. Taming Decentralized POMDPs: Towards Efficient Policy Computation for Multiagent Settings. In Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03. IJCAI, 705–710. https://ijcai.org/proceedings/2003/103

@inproceedings{ijcai2003p103,
  title     = {Taming Decentralized POMDPs: Towards Efficient Policy Computation for Multiagent Settings},
  author    = {Nair, Ranjit and Tambe, Milind and Yokoo, Makoto and Pynadath, David V. and Marsella, Stacy},
  booktitle = {Proceedings of the Eighteenth International Joint Conference on
               Artificial Intelligence, {IJCAI-03}},
  publisher = {International Joint Conferences on Artificial Intelligence},
  editor    = {Georg Gottlob},
  pages     = {705--710},
  year      = {2003},
  url       = {https://ijcai.org/proceedings/2003/103},
}

TY  - CPAPER
TI  - Taming Decentralized POMDPs: Towards Efficient Policy Computation for Multiagent Settings
AU  - Nair, Ranjit
AU  - Tambe, Milind
AU  - Yokoo, Makoto
AU  - Pynadath, David V.
AU  - Marsella, Stacy
T2  - Proceedings of the Eighteenth International Joint Conference on Artificial Intelligence, IJCAI-03
PB  - International Joint Conferences on Artificial Intelligence
PY  - 2003
SP  - 705
EP  - 710
UR  - https://ijcai.org/proceedings/2003/103
ER  -