One-Shot Averaging for Distributed TD($λ$) Under Markov Sampling
Haoxing Tian Ioannis Ch. Paschalidis Alex Olshevsky
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($\lambda$), 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($\lambda$) 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.