One-Shot Averaging for Distributed TD(λ) Under Markov Sampling

We consider a distributed setup for reinforcement learning, where each agent has a copy of the same Markov Decision Process but transitions are sampled from the corresponding Markov chain independently by each agent. We show that in this setting, we can achieve a linear speedup for TD(λ), a family of popular methods for policy evaluation, in the sense that N agents can evaluate a policy N times faster provided the target accuracy is small enough. Notably, this speedup is achieved by "one shot averaging," a procedure where the agents run TD(λ) with Markov sampling independently and only average their results after the final step. This significantly reduces the amount of communication required to achieve a linear speedup relative to previous work.