Local Policies for Graph-Structured Markov Decision Processes

We study a cooperative form of multi-agent reinforcement learning with state space dynamics and agent interaction controlled by an underlying graph. Each agent has a local state and action, the evolution of the local state depends only on the states and actions in the $1$-hop neighborhood defined by the graph. Structured dynamics of this type arise in various applications, including network resource allocation, co-operative games, epidemic control, and wireless scheduling. The global state-action space scales exponentially in the number of agents, so that computing global optimal policies is intractable in the worst-case. We study conditions under which it is possible to approximate the optimal policies by a local policy for each agent that depends only on states associated with nodes within its $m$-hop neighborhood. By controlling the propagation of influences via a Dobrushin-type stability matrix, we establish that globally optimal policies can approximated by local policies with sub-optimality gap decaying exponentially in $m$.

We study a cooperative multi-agent problem where agents are distributed on a graph where agents directly affect only their neighbors. The agents aim to collaboratively solve a global task together. Solving this global problem exactly requires resources that scale exponentially in the number of agents, which can quickly blow up. We show the existence of an approximately optimal strategy by which agents only need to collaborate with their m-hop neighbors to solve the global problem.