Bounding the probability of resource constraint violations in multi-agent MDPs

Frits De Nijs, Erwin Walraven, Mathijs M. De Weerdt, Matthijs T.J. Spaan

Research output: Chapter in Book/Report/Conference proceedingConference PaperResearchpeer-review

6 Citations (Scopus)


Multi-agent planning problems with constraints on global resource consumption occur in several domains. Existing algorithms for solving Multi-agent Markov Decision Processes can compute policies that meet a resource constraint in expectation, but these policies provide no guarantees on the probability that a resource constraint violation will occur. We derive a method to bound constraint violation probabilities using Hoeffding's inequality. This method is applied to two existing approaches for computing policies satisfying constraints: the Constrained MDP framework and a Column Generation approach. We also introduce an algorithm to adaptively relax the bound up to a given maximum violation tolerance. Experiments on a hard toy problem show that the resulting policies outperform static optimal resource allocations to an arbitrary level. By testing the algorithms on more realistic planning domains from the literature, we demonstrate that the adaptive bound is able to efficiently trade off violation probability with expected value, outperforming state-of-the-art planners.

Original languageEnglish
Title of host publicationProceedings of the Thirty-First AAAI Conference on Artificial Intelligence (AAAI-17)
EditorsSatinder Singh, Shaul Markovitch
Place of PublicationPalto Alto CA USA
PublisherAssociation for the Advancement of Artificial Intelligence (AAAI)
Number of pages7
Publication statusPublished - 1 Jan 2017
Externally publishedYes
EventAAAI Conference on Artificial Intelligence 2017 - Hilton San Francisco Union Square, San Francisco, United States of America
Duration: 4 Feb 201710 Feb 2017
Conference number: 31st


ConferenceAAAI Conference on Artificial Intelligence 2017
Abbreviated titleAAAI 2017
Country/TerritoryUnited States of America
CitySan Francisco
Internet address

Cite this