  In this paper, we consider federated reinforcement learning for tabular
episodic Markov Decision Processes (MDP) where, under the coordination of a
central server, multiple agents collaboratively explore the environment and
learn an optimal policy without sharing their raw data. While linear speedup in
the number of agents has been achieved for some metrics, such as convergence
rate and sample complexity, in similar settings, it is unclear whether it is
possible to design a model-free algorithm to achieve linear regret speedup with
low communication cost. We propose two federated Q-Learning algorithms termed
as FedQ-Hoeffding and FedQ-Bernstein, respectively, and show that the
corresponding total regrets achieve a linear speedup compared with their
single-agent counterparts when the time horizon is sufficiently large, while
the communication cost scales logarithmically in the total number of time steps
$T$. Those results rely on an event-triggered synchronization mechanism between
the agents and the server, a novel step size selection when the server
aggregates the local estimates of the state-action values to form the global
estimates, and a set of new concentration inequalities to bound the sum of
non-martingale differences. This is the first work showing that linear regret
speedup and logarithmic communication cost can be achieved by model-free
algorithms in federated reinforcement learning.
