  Federated reinforcement learning (FRL) has emerged as a promising paradigm
for reducing the sample complexity of reinforcement learning tasks by
exploiting information from different agents. However, when each agent
interacts with a potentially different environment, little to nothing is known
theoretically about the non-asymptotic performance of FRL algorithms. The lack
of such results can be attributed to various technical challenges and their
intricate interplay: Markovian sampling, linear function approximation,
multiple local updates to save communication, heterogeneity in the reward
functions and transition kernels of the agents' MDPs, and continuous
state-action spaces. Moreover, in the on-policy setting, the behavior policies
vary with time, further complicating the analysis. In response, we introduce
FedSARSA, a novel federated on-policy reinforcement learning scheme, equipped
with linear function approximation, to address these challenges and provide a
comprehensive finite-time error analysis. Notably, we establish that FedSARSA
converges to a policy that is near-optimal for all agents, with the extent of
near-optimality proportional to the level of heterogeneity. Furthermore, we
prove that FedSARSA leverages agent collaboration to enable linear speedups as
the number of agents increases, which holds for both fixed and adaptive
step-size configurations.
