Distributionally Robust Online Markov Game with Linear Function Approximation

Zewu Zheng, Yuanyuan Lin · 2025

Read Distributionally Robust Online Markov Game with Linear Function Approximation by Zewu Zheng, Yuanyuan Lin (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07831.txt.

Introduction

Zewu Zheng and Yuanyuan Lin train game agents that survive the gap between simulator and reality. Policies polished in simulation often collapse under shifted dynamics. Robust learning answers by optimizing against worst-case environment changes, but online multi-agent versions with large state spaces resist fast algorithms.

A hardness result shows where the difficulty truly sits under shift assumptions. Using a minimum value assumption restores tractability, and a least-squares algorithm follows with linear function fitting. Sample efficiency with live data is the prize. Robust games matter for fleets, markets, and infrastructure where opponents and physics both drift.

Catalog record

CREATORZewu Zheng, Yuanyuan Lin
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE100 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2511-07831

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Distributionally Robust Online Markov Game with Linear Function Approximation Zewu Zheng, Yuanyuan Lin Abstract The sim-to-real gap, where agents trained in a simulator face significant performance degradation during testing, is a fundamental challenge in reinforcement learning. Extensive 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 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 ε − \varepsilon- 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 ϵ − \epsilon- approximate CCE with a regret bound of 𝒪 ​ { d ​ H ​ min ⁡ { H , 1 min ⁡ { σ i } } ​ K } \mathcal{O}\{dH\min\{H,\frac{1}{\min\{\sigma_{i}\}}\}\sqrt{K}\} , where K K is the number of interacting episodes, H H is the horizon length, d d is the feature dimension, and σ i \sigma_{i} represents the uncertainty level of player i 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 optimal sample complexity in terms of the feature dimension d d . Meanwhile, we also conduct simulation study to validate the efficacy of our algorithm in learning a robust equilibrium. 1 Introduction Reinforcement learning (RL) has experienced significant advancements across various industrial applications, including video games, autonomous driving, and large language models, owing to its capacity to learn complex decision-making policies directly from data ( 39 ; 28 ; 38 ; 31 ) . The complexity of RL tasks increases substantially when multiple agents operate in the same environment, a scenario commonly referred to as multi-agent reinforcement learning (MARL) ( 40 ; 3 ) . In MARL, the Markov Game framework ( 21 ; 33 ) is widely adopted, where each agent optimizes its individual reward function by learning a Markov policy that serves as the best response to the policies of other agents. The solution to these joint policies is typically framed as a stable equilibrium, such as Nash equilibrium ( 29 ) or coarse correlated equilibrium ( 2 ) . Extensive research has investigated learning equilibria in Markov Games across various settings, proposing algorithms with theoretical guarantees on sample efficiency. Robustness is essential A critical challenge in reinforcement learning (RL) is the sim-to-real gap, characterized by discrepancies between simulated training environments and real-world deployment settings, which often result in degraded performance ( 19 ; 14 ) . This issue has motivated extensive research into distributionally robust reinforcement learning, where the objective is to develop policies that maintain robustness against variations in environmental dynamics ( 13 ; 30 ; 36 ; 24 ) . The challenge is particularly pronounced in MARL, as highlighted by ( 37 ) , where the sensitivity of equilibrium solutions to minor environmental perturbations exacerbates the problem. Large state space with linear function approximation When state and action space are large, function approximation are applied to mitigate the curse of dimensionality. The linear MDP framework, where the transition kernel and reward function are represented as linear functions of low-dimensional feature vectors, is analytically tractable and extensively studied by ( 17 ; 47 ; 6 ; 41 ; 11 ; 20 ) in single agent RL. However, research on linear Markov Games remains limited ( 5 ; 45 ) , particularly for multi-player general-sum Markov Games ( 6 ) . To date, the study of online robust general-sum Markov Games with linear function approximation remains an open area, representing a critical gap in the existing literature. As a result, it is natural to ask: Can we design a provably sample efficient algorithms for online robust general sum Markov Game with linear function approximation? Our main contributions • We investigate the inherent hardness of online learning in robust Markov games by constructing a specific two-player general-sum Markov game and establishing a lower bound that demonstrates the impossibility of learning without additional assumptions in this context. Subsequently, we adopt the minimum value assumption introduced by ( 25 ) , providing analysis of its applicability. • We address the additional challenges posed by distributionally robust Markov games compared to the single-agent setting ( 23 ; 22 ) . From an algorithmic perspective, we introduce agent-specific bonus terms to ensure adequate exploration and maintain each agent’s own risk preference. From a technical standpoint, when applying concentration arguments to establish uniform upper bounds for the CCE, we use the Find-CCE subroutine. This approach handles the issue that the CCEs of general-sum games are unstable (i.e., not Lipschitz continuous) with respect to changes in the payoff matrices, while remaining computationally feasible. • We develop an algorithm for interactive data collection, utilizing ridge regression and deriving an instance-dependent upper bound via refined analysis. By exploiting the shrinkage properties of the robust value function and proposing a general assumption on feature mapping and transition kernel properties, our algorithm achieves a regret of order \mathcal{O}\{dH\min\{H,\frac{1}{\min\{\sigma_{i}\}}\}\sqrt{K}\} . This bound exhibits polynomial dependence on all key problem parameters and is minimax optimal with respect to the feature dimension d . The algorithm’s efficacy is corroborated through further simulation studies. 2 Related work Robust online linear MDPs The setting of online linear Markov Decision Processes (MDPs) ( 46 ; 47 ; 48 ; 17 ; 12 ; 11 ; 50 ) has been extensively studied. The work of ( 11 ) achieved minimax optimality in this setting by incorporating variance-weighted ridge regression into their algorithm. In contrast, the study of online robust linear MDPs has only recently been explored in two works ( 23 ; 22 ) . Specifically, ( 22 ) introduced a robust variant of variance-weighted ridge regression, achieving a regret bound of order \mathcal{O}(dH\min\{1/\sigma,H\}\sqrt{K}) under full data coverage assumption. However, this result still falls short of the constructed lower bound, which is of order \Omega(dH^{\frac{1}{2}}\min\{1/\sigma,H\}\sqrt{K}) , highlighting that the single-agent counterpart of this setting remains insufficiently explored. Robust Markov game While there has been extensive research on distributionally robust MDPs ( 24 ; 7 ; 34 ; 36 ; 43 ; 25 ) , the study of robust Markov games remains relatively underexplored. Existing works, such as ( 18 ; 49 ) , primarily focus on proving the existence of equilibria and analyzing convergence properties. In offline setting, a unified framework P^{2}M^{2}PO has been proposed by ( 4 ) , with sample complexity of \mathcal{O}(\frac{H^{5}|S|^{2}|A|^{2}}{\epsilon}) . ( 35 ; 37 ; 15 ) extended this framework to generative model setting, where samples can be obtained from any state-action pair. In particular, ( 15 ) proposed a Q-FTRL type algorithm, demonstrating that it is minimax optimal and breaking the curse of multi-agency with a sample complexity of \mathcal{O}(\frac{H^{3}|S|\sum_{i=1}^{m}|A_{i}|}{\varepsilon^{2}}\min\left\{H,\frac{1}{\sigma}\right\}) . In the more realistic online setting, the work most relevant to ours is (

Read the complete text