Exploiting Fast Decaying and Locality in Multi-Agent MDP with Tree Dependence Structure

Abstract

This paper considers a multi-agent Markov Decision Process (MDP), where there are $n$ agents and each agent $i$ is associated with a state $s_i$ and action $a_i$ taking values from a finite set. Though the global state space size and action space size are exponential in $n$, we impose local dependence structures and focus on local policies that only depend on local states, and we propose a method that finds nearly optimal local policies in polynomial time (in $n$) when the dependence structure is a one directional tree. The algorithm builds on approximated reward functions which are evaluated using locally truncated Markov process. Further, under some special conditions, we prove that the gap between the approximated reward function and the true reward function is decaying exponentially fast as the length of the truncated Markov process gets longer. The intuition behind this is that under some assumptions, the effect of agent interactions decays exponentially in the distance between agents, which we term "fast decaying property".

arXiv comment10 pages, 3 figures. Accepted to CDC 2019

References in corpus (6)

• Fully Decentralized Multi-Agent Reinforcement Learning with Networked Agents
• Learning to Cooperate via Policy Search
• $QD$-Learning: A Collaborative Distributed Strategy for Multi-Agent Reinforcement Learning Through Consensus + Innovations
• Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimization
• Nonequilibrium phase transition in a model for the propagation of innovations among economic agents
• Dynamic mean-field and cavity methods for diluted Ising systems

Cited by in corpus (2)

• Scalable Multi-Agent Reinforcement Learning for Networked Systems with Average Reward
• A Microscopic Pandemic Simulator for Pandemic Prediction Using Scalable Million-Agent Reinforcement Learning