mlsanityData to 7 Oct 2026

Corruption-Robust Offline Two-Player Zero-Sum Markov Games

arXiv 2403.07933 ↗First posted 4 Mar 2024cs.GT cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

We study data corruption robustness in offline two-player zero-sum Markov games. Given a dataset of realized trajectories of two players, an adversary is allowed to modify an ε-fraction of it. The learner's goal is to identify an approximate Nash Equilibrium policy pair from the corrupted data. We consider this problem in linear Markov games under different degrees of data coverage and corruption. We start by providing an information-theoretic lower bound on the suboptimality gap of any learner. Next, we propose robust versions of the Pessimistic Minimax Value Iteration algorithm, both under coverage on the corrupted data and under coverage only on the clean data, and show that they achieve (near)-optimal suboptimality gap bounds with respect to ε. We note that we are the first to provide such a characterization of the problem of learning approximate Nash Equilibrium policies in offline two-player zero-sum Markov games under data corruption.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 52 of its 83 references that are in the map. First posted on arXiv 4 Mar 2024.

Builds on

52 of 83 references.

References · 52

  1. 2013Intriguing properties of neural networkscited by 5,114
  2. 2020Offline Reinforcement Learning: Tutorial, Review, and Perspectives on Open Problemscited by 1,873
  3. 2020Conservative Q-Learning for Offline Reinforcement Learningcited by 1,777
  4. 2019Certified Adversarial Robustness via Randomized Smoothingcited by 1,324
  5. 2018Off-Policy Deep Reinforcement Learning without Explorationcited by 1,227
  6. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,084
  7. 2016Practical Black-Box Attacks against Machine Learningcited by 893
  8. 2014Deep Neural Networks are Easily Fooled: High Confidence Predictions for Unrecognizable Imagescited by 774
  9. 2017Evasion Attacks against Machine Learning at Test Timecited by 686
  10. 2020MOReL : Model-Based Offline Reinforcement Learningcited by 582
  11. 2020Is Pessimism Provably Efficient for Offline RL?cited by 362
  12. 2017Adversarial Attacks on Neural Network Policiescited by 314
38 more
  1. 2019Way Off-Policy Batch Deep Reinforcement Learning of Implicit Human Preferences in Dialogcited by 283
  2. 2021Bridging Offline Reinforcement Learning and Imitation Learning: A Tale of Pessimismcited by 275
  3. 2021Bellman-consistent Pessimism for Offline Reinforcement Learningcited by 267
  4. 2019Adversarial Policies: Attacking Deep Reinforcement Learningcited by 209
  5. 2019Provably Efficient Exploration in Policy Optimizationcited by 203
  6. 2017Tactics of Adversarial Attack on Deep Reinforcement Learning Agentscited by 163
  7. 2021Pessimistic Model-based Offline Reinforcement Learning under Partial Coveragecited by 160
  8. 2017Safe Policy Improvement with Baseline Bootstrappingcited by 141
  9. 2018Sever: A Robust Meta-Algorithm for Stochastic Optimizationcited by 123
  10. 2022Offline Reinforcement Learning with Realizability and Single-policy Concentrabilitycited by 122
  11. 2021Provable Benefits of Actor-Critic Methods for Offline Reinforcement Learningcited by 109
  12. 2018Supervised Reinforcement Learning with Recurrent Neural Network for Dynamic Treatment Recommendationcited by 101
  13. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  14. 2018Is feature selection secure against training data poisoning?cited by 88
  15. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  16. 2022RORL: Robust Offline Reinforcement Learning via Conservative Smoothingcited by 83
  17. 2020Policy Teaching via Environment Poisoning: Training-time Adversarial Attacks against Reinforcement Learningcited by 81
  18. 2016Data Poisoning Attacks on Factorization-Based Collaborative Filteringcited by 78
  19. 2019Policy Poisoning in Batch Reinforcement Learning and Controlcited by 70
  20. 2020Stealthy and Efficient Adversarial Attacks against Deep Reinforcement Learningcited by 62
  21. 2021Cautiously Optimistic Policy Optimization and Exploration with Linear Function Approximationcited by 53
  22. 2021Decentralized Q-Learning in Zero-sum Markov Gamescited by 53
  23. 2021Fault-Tolerant Federated Reinforcement Learning with Theoretical Guaranteecited by 52
  24. 2021Corruption-Robust Offline Reinforcement Learningcited by 51
  25. 2022Nearly Optimal Algorithms for Linear Contextual Bandits with Adversarial Corruptionscited by 51
  26. 2019Deceptive Reinforcement Learning Under Adversarial Manipulations on Cost Signalscited by 50
  27. 2020Robust regression with covariate filtering: Heavy tails and adversarial contaminationcited by 49
  28. 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
  29. 2022Pessimistic Minimax Value Iteration: Provably Efficient Equilibrium Learning from Offline Datasetscited by 42
  30. 2021CROP: Certifying Robust Policies for Reinforcement Learning through Functional Smoothingcited by 41
  31. 2020Vulnerability-Aware Poisoning Mechanism for Online RL with Unknown Dynamicscited by 38
  32. 2022Corruption-Robust Algorithms with Uncertainty Weighting for Nonlinear Contextual Bandits and Markov Decision Processescited by 33
  33. 2022When is Offline Two-Player Zero-Sum Markov Game Solvable?cited by 27
  34. 2020Online and Distribution-Free Robustness: Regression and Contextual Bandits with Huber Contaminationcited by 26
  35. 2020Policy Teaching in Reinforcement Learning via Environment Poisoning Attackscited by 24
  36. 2021Defense Against Reward Poisoning Attacks in Reinforcement Learningcited by 20
  37. 2022Reward Poisoning Attacks on Offline Multi-Agent Reinforcement Learningcited by 19
  38. 2023Implicit Poisoning Attacks in Two-Agent Reinforcement Learning: Adversarial Policies for Training-Time Attackscited by 14

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2025: 3; 2026: 1.

4 papers.

  1. 2025On Corruption-Robustness in Performative Reinforcement Learningcited by 6
  2. 2025Policy Teaching via Data Poisoning in Learning from Human Preferencescited by 2
  3. 2025Sparse Offline Reinforcement Learning with Corruption Robustnesscited by 0
  4. 2026Corruption-robust Offline Multi-agent Reinforcement Learning From Human Feedbackcited by 0