Compact Mathematical Programs For DEC-MDPs With Structured Agent Interactions

Hala Mostafa, Victor Lesser
Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, PMLR R9:589-596, 2011.

Abstract

To deal with the prohibitive complexity of calculating policies in Decentralized MDPs, researchers have proposed models that exploit structured agent interactions. Settings where most agent actions are independent except for few actions that affect the transitions and/or rewards of other agents can be modeled using Event-Driven Interactions with Complex Rewards (EDI-CR). Finding the optimal joint policy can be formulated as an optimization problem. However, existing formulations are too verbose and/or lack optimality guarantees. We propose a compact Mixed Integer Linear Program formulation of EDI-CR instances. The key insight is that most action sequences of a group of agents have the same effect on a given agent. This allows us to treat these sequences similarly and use fewer variables. Experiments show that our formulation is more compact and leads to faster solution times and better solutions than existing formulations.

Cite this Paper

BibTeX
@InProceedings{pmlr-vR9-mostafa11a, title = {Compact Mathematical Programs For {DEC}-MDPs With Structured Agent Interactions}, author = {Mostafa, Hala and Lesser, Victor}, booktitle = {Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence}, pages = {589--596}, year = {2011}, editor = {Cozman, Fabio and Pfeffer, Avi}, volume = {R9}, series = {Proceedings of Machine Learning Research}, month = {14--17 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/r9/main/assets/mostafa11a/mostafa11a.pdf}, url = {https://proceedings.mlr.press/r9/mostafa11a.html}, abstract = {To deal with the prohibitive complexity of calculating policies in Decentralized MDPs, researchers have proposed models that exploit structured agent interactions. Settings where most agent actions are independent except for few actions that affect the transitions and/or rewards of other agents can be modeled using Event-Driven Interactions with Complex Rewards (EDI-CR). Finding the optimal joint policy can be formulated as an optimization problem. However, existing formulations are too verbose and/or lack optimality guarantees. We propose a compact Mixed Integer Linear Program formulation of EDI-CR instances. The key insight is that most action sequences of a group of agents have the same effect on a given agent. This allows us to treat these sequences similarly and use fewer variables. Experiments show that our formulation is more compact and leads to faster solution times and better solutions than existing formulations.}, note = {Reissued by PMLR on 04 October 2026.} }
Endnote
%0 Conference Paper %T Compact Mathematical Programs For DEC-MDPs With Structured Agent Interactions %A Hala Mostafa %A Victor Lesser %B Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence %C Proceedings of Machine Learning Research %D 2011 %E Fabio Cozman %E Avi Pfeffer %F pmlr-vR9-mostafa11a %I PMLR %P 589--596 %U https://proceedings.mlr.press/r9/mostafa11a.html %V R9 %X To deal with the prohibitive complexity of calculating policies in Decentralized MDPs, researchers have proposed models that exploit structured agent interactions. Settings where most agent actions are independent except for few actions that affect the transitions and/or rewards of other agents can be modeled using Event-Driven Interactions with Complex Rewards (EDI-CR). Finding the optimal joint policy can be formulated as an optimization problem. However, existing formulations are too verbose and/or lack optimality guarantees. We propose a compact Mixed Integer Linear Program formulation of EDI-CR instances. The key insight is that most action sequences of a group of agents have the same effect on a given agent. This allows us to treat these sequences similarly and use fewer variables. Experiments show that our formulation is more compact and leads to faster solution times and better solutions than existing formulations. %Z Reissued by PMLR on 04 October 2026.
APA
Mostafa, H. & Lesser, V.. (2011). Compact Mathematical Programs For DEC-MDPs With Structured Agent Interactions. Proceedings of the 27th Conference on Uncertainty in Artificial Intelligence, in Proceedings of Machine Learning Research R9:589-596 Available from https://proceedings.mlr.press/r9/mostafa11a.html. Reissued by PMLR on 04 October 2026.

Related Material