Lifting in Multi-Agent Systems Under Uncertainty
Abstract
A decentralised partially observable Markov decision problem (DecPOMDP) formalises collaborative multi-agent decision making. A solution to a DecPOMDP is a joint policy for the agents, fulfilling an optimality criterion such as maximum expected utility. A crux is that the problem is intractable regarding the number of agents. Inspired by lifted inference, this paper examines symmetries within the agent set for a potential tractability. Specifically, this paper contributes (i) specifications of counting and isomorphic symmetries, (ii) a compact encoding of symmetric DecPOMDPs as partitioned DecPOMDPs, and (iii) a formal analysis of complexity and tractability. This works allows tractability in terms of agent numbers and a new query type for isomorphic DecPOMDPs.
Cite
Text
Braun et al. "Lifting in Multi-Agent Systems Under Uncertainty." Uncertainty in Artificial Intelligence, 2022.Markdown
[Braun et al. "Lifting in Multi-Agent Systems Under Uncertainty." Uncertainty in Artificial Intelligence, 2022.](https://mlanthology.org/uai/2022/braun2022uai-lifting/)BibTeX
@inproceedings{braun2022uai-lifting,
title = {{Lifting in Multi-Agent Systems Under Uncertainty}},
author = {Braun, Tanya and Gehrke, Marcel and Lau, Florian and Möller, Ralf},
booktitle = {Uncertainty in Artificial Intelligence},
year = {2022},
pages = {233-243},
volume = {180},
url = {https://mlanthology.org/uai/2022/braun2022uai-lifting/}
}