Fast Multi-Agent Temporal-Difference Learning via Homotopy Stochastic
  Primal-Dual Optimization
  We study the policy evaluation problem in multi-agent reinforcement learning
where a group of agents, with jointly observed states and private local actions
and rewards, collaborate to learn the value function of a given policy via
local computation and communication over a connected undirected network. This
problem arises in various large-scale multi-agent systems, including power
grids, intelligent transportation systems, wireless sensor networks, and
multi-agent robotics. When the dimension of state-action space is large, the
temporal-difference learning with linear function approximation is widely used.
In this paper, we develop a new distributed temporal-difference learning
algorithm and quantify its finite-time performance. Our algorithm combines a
distributed stochastic primal-dual method with a homotopy-based approach to
adaptively adjust the learning rate in order to minimize the mean-square
projected Bellman error by taking fresh online samples from a causal on-policy
trajectory. We explicitly take into account the Markovian nature of sampling
and improve the best-known finite-time error bound from $O(1/\sqrt{T})$
to~$O(1/T)$, where $T$ is the total number of iterations.
