mlsanityData to 14 Oct 2026

Settling the Communication Complexity for Distributed Offline Reinforcement Learning

arXiv 2202.04862 ↗First posted 10 Feb 2022stat.ML cs.AI cs.LGcited by 1

On the map: Offline RL and imitation learning from data → Offline RL algorithms

Abstract (arXiv)

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 Omega(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.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in Offline RL algorithms, one of 13 directions in Offline RL and imitation learning from data. Builds on 7 of its 13 references that are in the map. First posted on arXiv 10 Feb 2022.

Builds on

7 of 13 references.

References · 7

  1. 2018A Finite Time Analysis of Temporal Difference Learning With Linear Function Approximationcited by 229
  2. 2015Federated Optimization:Distributed Optimization Beyond the Datacentercited by 195
  3. 2019Personalized HeartSteps: A Reinforcement Learning Algorithm for Optimizing Physical Activitycited by 70
  4. 2021Federated Linear Contextual Banditscited by 61
  5. 2013Distributed Exploration in Multi-Armed Banditscited by 46
  6. 2017Estimation Considerations in Contextual Banditscited by 23
  7. 2018Online Human Activity Recognition using Low-Power Wearable Devicescited by 10

Built on by

Cited by year

Citing papers per year: 2022: 1.

1 paper.

  1. 2022COptiDICE: Offline Constrained Reinforcement Learning via Stationary Distribution Correction Estimationcited by 71

Similar, not cited

Close in wording, no citation either way

  1. 2025Optimal Single-Policy Sample Complexity and Transient Coverage for Average-Reward Offline RL
  2. 2025On the Statistical Complexity for Offline and Low-Adaptive Reinforcement Learning with Structures
  3. 2022Nearly Minimax Optimal Offline Reinforcement Learning with Linear Function Approximation: Single-Agent MDP and Markov Game
  4. 2025A Tutorial: An Intuitive Explanation of Offline Reinforcement Learning Theory
  5. 2023Selective Uncertainty Propagation in Offline RL
  6. 2021Towards Instance-Optimal Offline Reinforcement Learning with Pessimism
  7. 2021Nearly Horizon-Free Offline Reinforcement Learning
  8. 2021Offline Neural Contextual Bandits: Pessimism, Optimization and Generalization