Skip to content

Sample-Efficient Tabular Self-Play for Offline Robust Reinforcement Learning

🕒 Published (v1): 2025-01-01 · Source: NeurIPS · Venue: NeurIPS 2025 · link

Ask a follow-up

Open an assistant pre-loaded with this paper's context.

💬 Ask ChatGPT✦ Ask Claude

TL;DR

This paper proposes RTZ-VI-LCB, a model-based algorithm for offline robust two-player zero-sum Markov games (RTZMGs) that achieves near-optimal sample complexity under partial state-action coverage and environmental uncertainty. It introduces a novel concentrability coefficient and a Bernstein-style penalty to handle distribution shift and model mismatches. A matching information-theoretic lower bound confirms the algorithm is optimal w.r.t. state and action space dimensions.

Problem

Existing offline MARL algorithms for robust TZMGs suffer from high sample complexity and fail to account for uncertainty levels when bounding convergence. The prior state-of-the-art (P²M²PO) achieves Õ(C_r H⁵ S² AB / ε²) and ignores uncertainty level (σ⁺, σ⁻), facing the curse of multiagency. No algorithm had provably optimal dependence on S and {A, B} simultaneously for offline RTZMGs under partial coverage.

Method

RTZ-VI-LCB is a pessimistic model-based algorithm running backward value iteration on an empirical nominal MDP:

  1. Two-stage subsampling (Algorithm 1): Splits the dataset into two halves D^m and D^a; uses D^a to construct trimmed visitation counts that remove statistical dependencies between transitions, yielding an effectively i.i.d. dataset D⁰.
  2. Optimistic robust Q-value estimation (Algorithm 2): At each step h, computes robust Q-functions via distributionally robust Bellman backups over TV-ball uncertainty sets. Strong duality converts the inner infimum/supremum over the S-dimensional simplex into a tractable scalar dual problem.
  3. Bernstein-style penalty β_h(s,a,b,V̂): Data-driven uncertainty bonus capturing variance of the next-step value under the empirical kernel, scaled by 1/N_h(s,a,b). Tighter than standard LCB penalties because it exploits the variance structure specific to robust Bellman operators.
  4. Nash policy computation: At each state, solves a minimax matrix game on the estimated Q-matrices to produce per-step Nash policies for both players.
  5. Robust unilateral clipped concentrability (C_r⋆): A new coverage criterion that measures distribution mismatch between the behavior policy and each player's individual best-response policy, clipped at 1/S(A+B) to avoid requiring full coverage.

Key Contributions

  • RTZ-VI-LCB algorithm: First offline RTZMG algorithm with sample complexity Õ(C_r⋆ H⁴ S(A+B) · f(σ⁺,σ⁻,H) / ε²), improving over P²M²PO by factors of H, S, and A·B→A+B.
  • Novel concentrability measure C_r⋆: Unilateral clipped concentrability that accounts for environmental uncertainty and yields tighter coverage requirements than the bilateral coefficient C_r used in prior work.
  • Information-theoretic lower bound: Proves Ω(C_r⋆ SH⁴(A+B)/ε²) for low uncertainty (min{σ⁺,σ⁻} ≲ 1/H) and Ω(C_r⋆ SH³(A+B)/(ε² min{σ⁺,σ⁻})) for high uncertainty, matching the upper bound on S and {A,B}.
  • Multi-agent extension (Multi-RTZ-VI-LCB): Generalizes to m-player general-sum robust Markov games, breaking the curse of multiagency with sample complexity scaling as Σ_i A_i rather than Π_i A_i.

Results

  • On randomly generated tabular TZMGs (S=50, A=B=2, H=100, averaged over 100 seeds): RTZ-VI-LCB consistently achieves lower value gap than baseline robust value iteration (RTZ-VI, without LCB penalty) across all states and all sample sizes K.
  • Log-log regression of value gap vs. K yields slope −0.4877, closely matching the theoretical O(K^{-1/2}) prediction from the upper bound.
  • Sample complexity comparison (Table 1):
  • P²M²PO: Õ(C_r H⁵ S² AB / ε²), no uncertainty-level dependence
  • RTZ-VI-LCB: Õ(C_r⋆ H⁴ S(A+B) · f(σ⁺,σ⁻,H) / ε²)
  • Lower bound (low uncertainty): Ω(C_r⋆ SH⁴(A+B) / ε²)
  • Lower bound (high uncertainty): Ω(C_r⋆ SH³(A+B) / (ε² min{σ⁺,σ⁻}))

Limitations

  • Analysis is restricted to tabular (finite state-action) RTZMGs; no function approximation for large/continuous spaces.
  • Requires the two-player-wise (s,a,b)-rectangularity assumption on uncertainty sets, which may not hold in all real-world models.
  • Computing Nash equilibria per state at each backward step (ComputNash) is PPAD-hard in general; the algorithm relies on external NE solvers.
  • The concentrability coefficient C_r⋆ is information-theoretically unestimable from offline data, so the sample complexity bound cannot be computed a priori.
  • Experiments are on randomly generated transition kernels; no evaluation on structured or real-world multi-agent tasks.

Relevance to Agentic AI / LLM Agents

This work addresses a foundational theoretical challenge in multi-agent decision-making under distributional shift and environmental uncertainty — conditions ubiquitous in real agentic deployments where agents must act on pre-collected data and face sim-to-real gaps. The pessimistic offline RL framework (learn robust policies without online environment interaction) directly parallels the challenge of training LLM-based agents from logged interaction data without costly live rollouts. The multi-agent extension breaking the curse of multiagency is especially relevant for cooperative or competitive LLM agent systems where joint action spaces grow exponentially. While this paper is purely theoretical/tabular, its sample complexity results and coverage-based analysis provide principled foundations for offline MARL algorithms that could underpin more sample-efficient offline training of agentic systems.