mlsanityData to 14 Oct 2026

Distributionally Robust Online Markov Game with Linear Function Approximation

arXiv 2511.07831 ↗First posted 11 Nov 2025stat.ML cs.LGcited by 1

On the map: Deep reinforcement learning methods → RL theory and sample complexity

Abstract (arXiv)

The sim-to-real gap, where agents trained in a simulator face significant performance degradation during testing, is a fundamental challenge in reinforcement learning. Extansive works adopt the framework of distributionally robust RL, to learn a policy that acts robustly under worst case environment shift. Within this framework, our objective is to devise algorithms that are sample efficient with interactive data collection and large state spaces. By assuming d-rectangularity of environment dynamic shift, we identify a fundamental hardness result for learning in online Markov game, and address it by adopting minimum value assumption. Then, a novel least square value iteration type algorithm, DR-CCE-LSI, with exploration bonus devised specifically for multiple agents, is proposed to find an episilon-approximate robust Coarse Correlated Equilibrium(CCE). To obtain sample efficient learning, we find that: when the feature mapping function satisfies certain properties, our algorithm, DR-CCE-LSI, is able to achieve ε-approximate CCE with a regret bound of OdHminH,1/minσi√K, where K is the number of interacting episodes, H is the horizon length, d is the feature dimension, and simgai represents the uncertainty level of player i. Our work introduces the first sample-efficient algorithm for this setting, matches the best result so far in single agent setting, and achieves minimax optimalsample complexity in terms of the feature dimension d. Meanwhile, we also conduct simulation study to validate the efficacy of our algorithm in learning a robust equilibrium.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL theory and sample complexity, one of 15 directions in Deep reinforcement learning methods. Builds on 23 of its 40 references that are in the map. First posted on arXiv 11 Nov 2025.

Builds on

23 of 40 references.

Closest ancestors · 3

Same direction, newest first

  1. 2024Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning30 Sep
  2. 2024Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms4 Apr
  3. 2024Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximation23 Feb

Other references · 20

  1. 2022Training language models to follow instructions with human feedbackcited by 15,971
  2. 2019Dota 2 with Large Scale Deep Reinforcement Learningcited by 1,103
  3. 2019Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Boundcited by 201
  4. 2020Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processescited by 200
  5. 2019Frequentist Regret Bounds for Randomized Least-Squares Value Iterationcited by 101
  6. 2020Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibriumcited by 100
  7. 2022Robust Reinforcement Learning using Offline Datacited by 96
  8. 2022Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexitycited by 87
  9. 2020Logarithmic Regret for Reinforcement Learning with Linear Function Approximationcited by 79
  10. 2023The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Modelcited by 52
  11. 2023Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coveragecited by 51
  12. 2021The Power of Exploiter: Provable Multi-Agent RL in Large State Spacescited by 48
8 more
  1. 2023A Finite Sample Complexity Bound for Distributionally Robust Q-learningcited by 36
  2. 2023Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximationcited by 30
  3. 2021Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Gamescited by 25
  4. 2024Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertaintycited by 25
  5. 2023Towards Minimax Optimality of Model-based Robust Reinforcement Learningcited by 22
  6. 2021Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Modelcited by 18
  7. 2024Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPscited by 5
  8. 2024Minimax-Optimal Multi-Agent Robust Reinforcement Learningcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximationcited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2025Sample-Efficient Distributionally Robust Multi-Agent Reinforcement Learning via Online Interaction
  2. 2025Online Robust Reinforcement Learning with General Function Approximation
  3. 2026Interactive Distributionally Robust Multi-Agent Learning with General Function Approximation
  4. 2024Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning
  5. 2025Policy Regularized Distributionally Robust Markov Decision Processes with Linear Function Approximation
  6. 2024Model-Free Robust Reinforcement Learning with Sample Complexity Analysis
  7. 2024Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes
  8. 2025Sample-Efficient Tabular Self-Play for Offline Robust Reinforcement Learning