# Distributionally Robust Online Markov Game with Linear Function Approximation

arXiv: https://arxiv.org/abs/2511.07831 · HTML: https://mlsanity.com/paper/2511.07831/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Placed in Multi-agent reinforcement learning, 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.

## Placed in

- Deep reinforcement learning methods / [Multi-agent reinforcement learning](https://mlsanity.com/deeprl/multi-agent-reinforcement-learning/)

## Builds on (most cited first, 23 of 23)

- [Training language models to follow instructions with human feedback](https://mlsanity.com/paper/2203.02155/) (2022)
- [Dota 2 with Large Scale Deep Reinforcement Learning](https://mlsanity.com/paper/1912.06680/) (2019)
- [Reinforcement Learning in Feature Space: Matrix Bandit, Kernels, and Regret Bound](https://mlsanity.com/paper/1905.10389/) (2019)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Mixture Markov Decision Processes](https://mlsanity.com/paper/2012.08507/) (2020)
- [Frequentist Regret Bounds for Randomized Least-Squares Value Iteration](https://mlsanity.com/paper/1911.00567/) (2019)
- [Learning Zero-Sum Simultaneous-Move Markov Games Using Function Approximation and Correlated Equilibrium](https://mlsanity.com/paper/2002.07066/) (2020)
- [Robust Reinforcement Learning using Offline Data](https://mlsanity.com/paper/2208.05129/) (2022)
- [Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity](https://mlsanity.com/paper/2208.05767/) (2022)
- [Logarithmic Regret for Reinforcement Learning with Linear Function Approximation](https://mlsanity.com/paper/2011.11566/) (2020)
- [The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2305.16589/) (2023)
- [Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage](https://mlsanity.com/paper/2305.09659/) (2023)
- [The Power of Exploiter: Provable Multi-Agent RL in Large State Spaces](https://mlsanity.com/paper/2106.03352/) (2021)
- [A Finite Sample Complexity Bound for Distributionally Robust Q-learning](https://mlsanity.com/paper/2302.13203/) (2023)
- [Breaking the Curse of Multiagency: Provably Efficient Decentralized Multi-Agent RL with Function Approximation](https://mlsanity.com/paper/2302.06606/) (2023)
- [Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms](https://mlsanity.com/paper/2404.03578/) (2024)
- [Almost Optimal Algorithms for Two-player Zero-Sum Linear Mixture Markov Games](https://mlsanity.com/paper/2102.07404/) (2021)
- [Distributionally Robust Off-Dynamics Reinforcement Learning: Provable Efficiency with Linear Function Approximation](https://mlsanity.com/paper/2402.15399/) (2024)
- [Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty](https://mlsanity.com/paper/2404.18909/) (2024)
- [Towards Minimax Optimality of Model-based Robust Reinforcement Learning](https://mlsanity.com/paper/2302.05372/) (2023)
- [Sample-Efficient Reinforcement Learning for Linearly-Parameterized MDPs with a Generative Model](https://mlsanity.com/paper/2105.14016/) (2021)
- [Upper and Lower Bounds for Distributionally Robust Off-Dynamics Reinforcement Learning](https://mlsanity.com/paper/2409.20521/) (2024)
- [Near-Optimal Dynamic Regret for Adversarial Linear Mixture MDPs](https://mlsanity.com/paper/2411.03107/) (2024)
- [Minimax-Optimal Multi-Agent Robust Reinforcement Learning](https://mlsanity.com/paper/2412.19873/) (2024)

## Built on by (most cited first, 1 of 1)

- [Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation](https://mlsanity.com/paper/2605.03125/) (2026)

## 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.