Settling the Communication Complexity for Distributed Offline Reinforcement Learning
This work addresses communication efficiency in distributed RL for researchers and practitioners, providing foundational lower bounds and algorithms, but it is incremental as it builds on existing offline RL frameworks.
The paper tackles the problem of distributed offline reinforcement learning with communication constraints, establishing information-theoretic lower bounds on minimax risk and showing that the required bits scale as Ω(AC) for contextual bandits to match centralized optimal rates, while also developing algorithms that achieve optimal risk up to logarithmic factors.
We study a novel setting in offline reinforcement learning (RL) where a number of distributed machines jointly cooperate to solve the problem but only one single round of communication is allowed and there is a budget constraint on the total number of information (in terms of bits) that each machine can send out. For value function prediction in contextual bandits, and both episodic and non-episodic MDPs, we establish information-theoretic lower bounds on the minimax risk for distributed statistical estimators; this reveals the minimum amount of communication required by any offline RL algorithms. Specifically, for contextual bandits, we show that the number of bits must scale at least as $Ω(AC)$ to match the centralised minimax optimal rate, where $A$ is the number of actions and $C$ is the context dimension; meanwhile, we reach similar results in the MDP settings. Furthermore, we develop learning algorithms based on least-squares estimates and Monte-Carlo return estimates and provide a sharp analysis showing that they can achieve optimal risk up to logarithmic factors. Additionally, we also show that temporal difference is unable to efficiently utilise information from all available devices under the single-round communication setting due to the initial bias of this method. To our best knowledge, this paper presents the first minimax lower bounds for distributed offline RL problems.