babylonpolice.com

When the data used for reinforcement learning (RL) are collected by multiple
agents in a distributed manner, federated versions of RL algorithms allow
collaborative learning without the need of sharing local data. In this paper,
we consider federated Q-learning, which aims to learn an optimal Q-function by
periodically aggregating local Q-estimates trained on local data alone.
Focusing on infinite-horizon tabular Markov decision processes, we provide
sample complexity guarantees for both the synchronous and asynchronous variants
of federated Q-learning. In both cases, our bounds exhibit a linear speedup
with respect to the number of agents and sharper dependencies on other salient
problem parameters. Moreover, existing approaches to federated Q-learning adopt
an equally-weighted averaging of local Q-estimates, which can be highly
sub-optimal in the asynchronous setting since the local trajectories can be
highly heterogeneous due to different local behavior policies. Existing sample
complexity scales inverse proportionally to the minimum entry of the stationary
state-action occupancy distributions over all agents, requiring that every
agent covers the entire state-action space. Instead, we propose a novel
importance averaging algorithm, giving larger weights to more frequently
visited state-action pairs. The improved sample complexity scales inverse
proportionally to the minimum entry of the average stationary state-action
occupancy distribution of all agents, thus only requiring the agents
collectively cover the entire state-action space, unveiling the blessing of
heterogeneity.