  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 for agents to share their 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 near-optimal dependencies on
other salient problem parameters.
  In the asynchronous setting, existing analyses of federated Q-learning, which
adopt an equally weighted averaging of local Q-estimates, require that every
agent covers the entire state-action space. In contrast, our 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 to collectively cover the entire state-action space,
unveiling the blessing of heterogeneity in enabling collaborative learning by
relaxing the coverage requirement of the single-agent case. However, its sample
complexity still suffers when the local trajectories are highly heterogeneous.
In response, we propose a novel federated Q-learning algorithm with importance
averaging, giving larger weights to more frequently visited state-action pairs,
which achieves a robust linear speedup as if all trajectories are centrally
processed, regardless of the heterogeneity of local behavior policies.

Machine Learning;Machine Learning