On the Near-Optimality of Local Policies in Large Cooperative Multi-Agent Reinforcement Learning
share
We show that in a cooperative N-agent network, one can design locally executable policies for the agents such that the resulting discounted sum of average rewards (value) well approximates the optimal value computed over all (including non-local) policies. Specifically, we prove that, if |š³|, |š°| denote the size of state, and action spaces of individual agents, then for sufficiently small discount factor, the approximation error is given by šŖ(e) where eā1/ā(N)[ā(|š³|)+ā(|š°|)]. Moreover, in a special case where the reward and state transition functions are independent of the action distribution of the population, the error improves to šŖ(e) where eā1/ā(N)ā(|š³|). Finally, we also devise an algorithm to explicitly construct a local policy. With the help of our approximation results, we further establish that the constructed local policy is within šŖ(max{e,Ļµ}) distance of the optimal policy, and the sample complexity to achieve such a local policy is šŖ(Ļµ^-3), for any Ļµ>0.
READ FULL TEXT