Exploiting Anonymity in Approximate Linear Programming: Scaling to Large Multiagent MDPs
Exploiting Anonymity in Approximate Linear Programming: Scaling to Large Multiagent MDPs
复制标题
DOI：
10.1609/aaai.v30i1.10133
复制
发表时间：
2015-11
期刊：
影响因子：
--
通讯作者：
P. Robbel;F. Oliehoek;Mykel J. Kochenderfer
中科院分区：
文献类型：
--
作者：
P. Robbel;F. Oliehoek;Mykel J. Kochenderfer
马尔可夫决策过程（mdp）的许多求解方法利用了问题中的结构，并基于值函数分解。然而，特别是多代理设置，随着交互变得更加密集，值组件的大小会呈指数级增长，从而限制了问题的大小和可处理的类型。我们提出了一种方法来缓解某些类型的多智能体系统的这种限制，利用了因子MDP中可以被认为是“匿名影响”的属性。我们展示了匿名的代表性优势如何转化为计算效率，无论是因子图中的变量消除还是因子mdp的近似线性规划解决方案。我们的方法适用于以前无法解决的因素mdp，例如对具有50个节点和25个代理的密集连接图上的随机疾病过程的控制。
Many solution methods for Markov Decision Processes (MDPs) exploit structure in the problem and are based on value function factorization. Especially multiagent settings, however, are known to suffer from an exponential increase in value component sizes as interactions become denser, restricting problem sizes and types that can be handled. We present an approach to mitigate this limitation for certain types of multiagent systems, exploiting a property that can be thought of as "anonymous influence" in the factored MDP. We show how representational benefits from anonymity translate into computational efficiencies, both for variable elimination in a factor graph and for the approximate linear programming solution to factored MDPs. Our methods scale to factored MDPs that were previously unsolvable, such as the control of a stochastic disease process over densely connected graphs with 50 nodes and 25 agents.