Research map / Multi-agent systems and games / Games and equilibria

Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation

NeurIPS 2026 · Multi-agent systems and games › Games and equilibria · approach: Learning in Markov games · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Develops provably sample-efficient algorithms for distributionally robust linear Markov games (TV fictitious uncertainty) in generative-model and online settings, breaking the curse of multiagency with large/infinite state spaces.

Problem

Sample-efficient learning of robust equilibria (CCE) in distributionally robust Markov games with large or infinite state spaces, where prior provable results are tabular or restricted to vanishing-minimal-value linear RMGs and suffer exponential dependence on the number of agents.

Approach

Extends independent per-agent linear function approximation to robust Markov games with TV fictitious uncertainty sets; uses a finite support set from a G-optimal design for generative sampling, and in the online setting a hybrid sampling scheme with pessimistic robust value estimates to sample from the approximate adversarial environment.

Key results

• Generative-model algorithm L-Robust-Q-FTRL finds an epsilon-robust CCE with sample complexity O(H^9 d^3/epsilon^4) for R-LMGs under TV uncertainty sets.
• Online Algorithm achieves regret Õ(H^2 d max_i A_i sqrt(T)) and breaks the curse of multiagency, versus exponential prod A_i dependence of prior DR-CCE-LSI.
• Tabular specialization gives regret Õ(H^2 S max_i A_i^2 sqrt(T)), polynomial in all parameters.

Limitations

• Results are theoretical; no empirical experiments reported in the provided text.
• Only total variation fictitious uncertainty sets analyzed; other divergences not covered by guarantees.
• Online setting requires sampling from an approximate adversarial environment, which is an assumed interaction protocol.

Experimental setup

Metrics: sample complexity regret epsilon-approximate CCE

Baselines: Robust-Q-FTRL P2MPO DR-NVI DRMG DR-CCE-LSI

Builds on: Robust-Q-FTRL linear Markov games with per-agent independent LFA fictitious uncertainty sets Glicksberg fixed point theorem

Closest papers by meaning

• Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning (ICML 2025 · similarity 0.95)
• Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty (ICML 2024 · similarity 0.92)
• Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms (NeurIPS 2024 · similarity 0.90)
• Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms (NeurIPS 2024 · similarity 0.90)
• Sample-Efficient Tabular Self-Play for Offline Robust Reinforcement Learning (NeurIPS 2025 · similarity 0.90)
• Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.89)