  We provide a new non-asymptotic analysis of distributed TD(0) with linear
function approximation. Our approach relies on "one-shot averaging," where $N$
agents run local copies of TD(0) and average the outcomes only once at the very
end. We consider two models: one in which the agents interact with an
environment they can observe and whose transitions depends on all of their
actions (which we call the global state model), and one in which each agent can
run a local copy of an identical Markov Decision Process, which we call the
local state model.
  In the global state model, we show that the convergence rate of our
distributed one-shot averaging method matches the known convergence rate of
TD(0). By contrast, the best convergence rate in the previous literature showed
a rate which, in the worst case, underperformed the non-distributed version by
$O(N^3)$ in terms of the number of agents $N$. In the local state model, we
demonstrate a version of the linear time speedup phenomenon, where the
convergence time of the distributed process is a factor of $N$ faster than the
convergence time of TD(0). As far as we are aware, this is the first result
rigorously showing benefits from parallelism for temporal difference methods.
