The Blessing of Heterogeneity in Federated Q-Learning: Linear Speedup and Beyond
This work addresses collaborative reinforcement learning without data sharing for distributed agents, offering improved sample complexity and robustness to heterogeneity, though it is incremental in refining federated Q-learning methods.
The paper tackles the problem of federated Q-learning in reinforcement learning by analyzing sample complexity for synchronous and asynchronous variants, achieving linear speedup with the number of agents and near-optimal dependencies on problem parameters. It also proposes a novel algorithm with importance averaging to handle heterogeneous local trajectories, achieving robust linear speedup regardless of heterogeneity.
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.