Distributed Randomized Multiagent Policy Iteration in Reinforcement Learning

We propose a distributed randomized policy iteration algorithm for infinite horizon dynamic programming problems for which the control at each stage is m-dimensional. The traditional policy iteration algorithm involves performing a minimization over an m-dimensional constraint set and has a computational complexity that increases exponentially in m, resulting in an intractable combinatorial search problem. In each iteration, our algorithm performs a series of sequential minimizations followed by policy evaluation and policy improvement using the policy that attains the minimum cost over the sequential minimizations. Our algorithm is well-suited for parallel computation, has a complexity that increases linearly in m, and converges to an agent-by-agent optimal policy. We characterize sufficient conditions for which our algorithm generates a globally optimal policy that coincides with that obtained from standard policy iteration