Distributionally Robust Online Markov Game with Linear Function Approximation

AI summary

Overview

Research area: Reinforcement learning theory — specifically multi-agent reinforcement learning (MARL), distributionally robust reinforcement learning, and online Markov games with linear function approximation.

Technical level: Advanced. The paper is a theory paper built on robust Bellman equations, total-variation uncertainty sets, coarse correlated equilibrium (CCE), ridge regression with bonus terms, covering-number arguments, and minimax regret lower bounds.

Scope: This paper establishes a hardness result for online robust general-sum Markov games, proposes the DR-CCE-LSI algorithm that achieves a regret bound of 𝒪{dH min{H, 1/min{σ_i}}√K} and a sample complexity that is minimax optimal in the feature dimension d, and supports the analysis with a simulation study.

What This Paper Is About

Agents trained in a simulator often lose performance when deployed in the real world — the "sim-to-real gap." One response is distributionally robust reinforcement learning, which learns policies that hold up under the worst-case shift in environment dynamics, but doing this with several agents, large state spaces, and data collected interactively has remained open. This paper asks whether provably sample-efficient algorithms exist for online robust general-sum Markov games under linear function approximation, and answers yes with an algorithm called DR-CCE-LSI.

Key Contributions

1. A hardness result plus a workaround assumption. The authors construct a two-player general-sum robust Markov game and prove an online regret lower bound of Ω(σ · HK), showing learning is impossible without extra assumptions. They then adopt the minimum value assumption from Lu et al. (2024) (their Assumption 4.2) and analyze why it is applicable, including a proposition (4.3) characterizing the robust Bellman operator under it.

2. An algorithm designed for multiple agents' differing risk preferences. DR-CCE-LSI introduces agent-specific bonus terms so that each agent explores adequately while preserving its own uncertainty level σ_i, in contrast to single-agent robust linear MDP methods (Liu and Xu 2024; Liu et al. 2024).

3. A technical fix for CCE instability. Because coarse correlated equilibria of general-sum games are not Lipschitz continuous with respect to changes in payoffs (Lemma 4.4, adapted from Xie et al. 2020), the authors use a Find-CCE subroutine to build a covering set for the value function class while keeping the procedure computationally feasible.

4. An instance-dependent regret bound. Using ridge regression and a refined analysis exploiting shrinkage properties of the robust value function, the algorithm attains a regret of order 𝒪{dH min{H, 1/min{σ_i}}√K}, a first for this setting, matching the best single-agent result and achieving minimax optimal sample complexity in the feature dimension d.

Main Findings

• Hardness without assumptions: Theorem 4.1 gives inf over algorithms, sup over two game instances of the expected regret = Ω(σ · HK), where σ is the shared uncertainty level of both players and K is the number of episodes. The authors attribute this to the support shift problem: collected samples may not cover trajectories relevant to the worst-case environment.

• The minimum value assumption removes the obstruction: Under Assumption 4.2 (min over states of the robust value is zero for all i, h, π, and the initial state is not a minimizer), Proposition 4.3 shows that the worst-case transition evaluation reduces to σ_i times an expectation under a tilted kernel, and that the ratio P̃_h(s'|s,a) / P_h^0(s'|s,a) is bounded by 1/σ_i. This keeps worst-case transitions inside the support of the nominal kernel.

• The assumption is satisfiable without loss of generality: It can be met by augmenting the game with an isolated absorbing fail state s_f at each time step, with P_h^0(s_f|s_f,a) = 1 and r_{i,h}(s_f,a) = 0.

• Formal regret guarantee: Theorem 5.1 states that with λ = 1, β_i = min{H, 1/σ_i} · √(c_β n d log(ndHK/δ)), and ε = 1/(KH), the suboptimality of DR-CCE-LSI is bounded with probability at least 1 − δ by 8 min{H, 1/min{σ_i}} √(2HK log(3n/δ)) plus 4 max_i{β_i} Σ_k Σ_h Σ_j √(φ_{h,j}^k 1_j^T (Λ_h^k)^{-1} 1_j φ_{h,j}^k).

• Minimax optimality in d: The bound has polynomial dependence on all key problem parameters and is minimax optimal with respect to the feature dimension d.

• Risk preference must be shared to learn efficiently: Because the bound depends on max_i{β_i}, a single risk-seeking player can inflate it. The authors interpret this as implying that, given finite interacting episodes, players should share a common sense of risk preference to achieve the best sample efficiency.

• Comparison to prior work: The bound matches the best single-agent result so far; in the single-agent robust linear MDP setting, Liu et al. (2024) achieved 𝒪(dH min{1/σ, H}√K) under full data coverage while the constructed lower bound is Ω(dH^{1/2} min{1/σ, H}√K), which the authors note leaves that setting not fully resolved.

• Simulation validation: The authors report that they conduct a simulation study confirming the algorithm's efficacy in learning a robust equilibrium; the truncated content does not report the simulation setup, metrics, or numerical results.

Methodology in Plain English

The authors model the problem as a distributionally robust general-sum Markov game in which each player's uncertainty set is d-rectangular around a nominal transition kernel, measured by total variation distance. Assuming linear structure for rewards and transitions (Assumption 3.1), they define the robust action-value function as the worst-case value over each player's uncertainty set, which yields a robust Bellman equation.

They first show, via an explicit two-player construction, that online learning is hopeless in general, then import the minimum value assumption, which converts the inner worst-case optimization into a tractable supremum over a scalar parameter α of a term involving a shrunk value function. To learn, they run repeated episodes: in each episode, for each player and each step, they fit a ridge regression of the (clipped) next-step value onto the feature map, take the worst-case over α, add an optimistic exploration bonus, and clip the result. The joint policies at each state come from solving an n-player matrix game for a coarse correlated equilibrium using the Find-CCE subroutine, which searches a discretized cover of the action-value function class; this sidesteps the fact that CCEs can jump discontinuously when payoffs change only slightly. Regret is measured against the best unilateral deviation under the worst-case transition.

Why This Matters

Impact on research: This is described as the first sample-efficient algorithm for online robust general-sum Markov games with linear function approximation, filling a gap the authors identify explicitly: robustness in online linear Markov games had not previously been studied, and prior robust Markov game work was either offline (Blanchet et al. 2023, with sample complexity 𝒪(H⁵|S|²|A|²/ε)), in the generative-model setting (Shi et al. 2024a; Shi et al. 2024b; Jiao and Li 2024, whose Q-FTRL achieves 𝒪(H³|S|Σᵢ|Aᵢ|/ε² · min{H, 1/σ})), or online with restrictive constraints on σ_i (Ma et al. 2023).

Real-world applications (examples the authors themselves give for why the minimum value assumption is reasonable):

• Warfare, where soldiers face daily risk to their lives.
• Hospitals, where patients undergoing treatment may not survive each day.
• Round-based computer games, where players can fail in each round.
• More broadly, any setting with a sim-to-real gap — autonomous driving and large language models are cited among the industrial applications of RL that motivate this line of work.

Industry relevance: Practitioners deploying multi-agent systems trained in simulators need policies that do not collapse under environment shift. This paper provides a theoretically grounded route to such policies when state and action spaces are large, with an explicit statement of when the problem is unsolvable and what extra structural assumption restores solvability.

Future Directions

• Closing the single-agent gap. The authors note that for robust online linear MDPs, the best known upper bound (Liu et al. 2024) is 𝒪(dH min{1/σ, H}√K) while the constructed lower bound is Ω(dH^{1/2} min{1/σ, H}√K), so that setting "remains insufficiently explored."
• Robustness in decentralized learning. The paper states that addressing robustness under decentralized (independent) linear function approximation "remains an open and challenging problem," since decentralized methods avoid the curse of multi-agency in tabular games but require assumptions that deviate from the standard linear MDP setting.
• Relaxing the minimum value assumption and d-rectangularity. Both are structural assumptions needed to make worst-case optimization tractable; determining what can be learned without them, or under alternative uncertainty sets, is left open.
• Reconciling heterogeneous risk preferences. The bound's dependence on max_i{β_i} suggests a tension between players choosing different uncertainty levels σ_i and sample efficiency, which the authors flag rather than resolve.

Target Audience

Theoretical reinforcement learning researchers working on sample complexity, regret bounds, and robust or multi-agent RL will find the main results most useful, particularly those interested in the intersection of linear function approximation, distributionally robust optimization, and equilibrium computation. It is also relevant to graduate students and practitioners with a strong optimization and probability background who need to understand the precise conditions under which robust multi-agent learning is and is not possible. Readers without familiarity with Markov games, robust Bellman equations, and regret analysis will find the paper difficult, as the provided content is almost entirely theorem statements and algorithm pseudocode.

Authors’ 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. 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 O{dHmin{H,1/min{σ_i}}\sqrt{K}}, where K is the number of interacting episodes, H is the horizon length, d is the feature dimension, and \simga_i 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.