mlsanityData to 7 Oct 2026

Byzantine-Robust Online and Offline Distributed Reinforcement Learning

arXiv 2206.00165 ↗First posted 1 Jun 2022cs.LG cs.DC stat.MLcited by 13

Not on the map. Why?

Abstract (arXiv)

We consider a distributed reinforcement learning setting where multiple agents separately explore the environment and communicate their experiences through a central server. However, α-fraction of agents are adversarial and can report arbitrary fake information. Critically, these adversarial agents can collude and their fake data can be of any sizes. We desire to robustly identify a near-optimal policy for the underlying Markov decision process in the presence of these adversarial agents. Our main technical contribution is Weighted-Clique, a novel algorithm for the robust mean estimation from batches problem, that can handle arbitrary batch sizes. Building upon this new estimator, in the offline setting, we design a Byzantine-robust distributed pessimistic value iteration algorithm; in the online setting, we design a Byzantine-robust distributed optimistic value iteration algorithm. Both algorithms obtain near-optimal sample complexities and achieve superior robustness guarantee than prior works.

Key facts. Cited by 13 papers in the map (data through 7 Oct 2026). Builds on 39 of its 58 references that are in the map. First posted on arXiv 1 Jun 2022.

Builds on

39 of 58 references.

References · 39

  1. 2020Language Models are Few-Shot Learnerscited by 32,199
  2. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,479
  3. 2018IMPALA: Scalable Distributed Deep-RL with Importance Weighted Actor-Learner Architecturescited by 866
  4. 2018Byzantine-Robust Distributed Learning: Towards Optimal Statistical Ratescited by 698
  5. 2016TensorFlow: Large-Scale Machine Learning on Heterogeneous Distributed Systemscited by 660
  6. 2017Minimax Regret Bounds for Reinforcement Learningcited by 500
  7. 2018Is Q-learning Provably Efficient?cited by 485
  8. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  9. 2017Adversarial Attacks on Neural Network Policiescited by 314
  10. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  11. 2018Distributed Prioritized Experience Replaycited by 260
  12. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
27 more
  1. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 199
  2. 2019A Survey on Distributed Machine Learningcited by 187
  3. 2017Unifying PAC and Regret: Uniform PAC Bounds for Episodic Reinforcement Learningcited by 175
  4. 2020What are the Statistical Limits of Offline RL with Linear Function Approximation?cited by 135
  5. 2016Agnostic Estimation of Mean and Covariancecited by 131
  6. 2020Almost Optimal Model-Free Reinforcement Learning via Reference-Advantage Decompositioncited by 127
  7. 2021Provably Efficient Reinforcement Learning with Linear Function Approximation Under Adaptivity Constraintscited by 124
  8. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  9. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  10. 2020Adaptive Reward-Poisoning Attacks against Reinforcement Learningcited by 86
  11. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  12. 2019Provably Efficient Q-Learning with Low Switching Costcited by 77
  13. 2018Robust Estimation via Robust Gradient Estimationcited by 76
  14. 2019Corruption-robust exploration in episodic reinforcement learningcited by 72
  15. 2019Policy Poisoning in Batch Reinforcement Learning and Controlcited by 70
  16. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 52
  17. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  18. 2021A Provably Efficient Algorithm for Linear Markov Decision Process with Low Switching Costcited by 38
  19. 2013Optimal Algorithms for Testing Closeness of Discrete Distributionscited by 37
  20. 2021Robust Policy Gradient against Strong Data Corruptioncited by 30
  21. 2021Provably Efficient Cooperative Multi-Agent Reinforcement Learning with Function Approximationcited by 23
  22. 2017Learning Discrete Distributions from Untrusted Batchescited by 14
  23. 2021Communication Efficient Parallel Reinforcement Learningcited by 10
  24. 2022Private and Byzantine-Proof Cooperative Decision-Makingcited by 9
  25. 2019Efficiently Learning Structured Distributions from Untrusted Batchescited by 8
  26. 2020Distributed Reinforcement Learning for Cooperative Multi-Robot Object Manipulationcited by 7
  27. 2022Byzantine-Robust Federated Linear Banditscited by 7

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 5; 2024: 4; 2025: 2; 2026: 1.

13 papers.

Sort:

By area:

  1. 2023Survival Instinct in Offline Reinforcement Learningcited by 20
  2. 2022Federated Offline Reinforcement Learningcited by 13
  3. 2023Efficient Adversarial Attacks on Online Multi-agent Reinforcement Learningcited by 9
  4. 2023FedHQL: Federated Heterogeneous Q-Learningcited by 6
  5. 2024Global Convergence Guarantees for Federated Policy Gradient Methods with Adversariescited by 6
  6. 2024Federated UCBVI: Communication-Efficient Federated Regret Minimization with Heterogeneous Agentscited by 5
  7. 2024Corruption-Robust Offline Two-Player Zero-Sum Markov Gamescited by 4
  8. 2025Gap-Dependent Bounds for Federated Q-learningcited by 4
  9. 2023Byzantine-Resilient Decentralized Multi-Armed Banditscited by 3
  10. 2024On the Hardness of Decentralized Multi-Agent Policy Evaluation under Byzantine Attackscited by 3
  11. 2025Regret-Optimal Q-Learning with Low Cost for Single-Agent and Federated Reinforcement Learningcited by 2
  12. 2023A Robust Classification Framework for Byzantine-Resilient Stochastic Gradient Descentcited by 0
1 more
  1. 2026Online Security Learning in Cooperative Multi-Agent Systems under Hidden Byzantine Attackscited by 0