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

🕒 Published (v1): 2025-11-29 06:45 UTC · Source: Arxiv · Venue: NEURIPS 2025 · link

Ask a follow-up

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

💬 Ask ChatGPT✦ Ask Claude

TL;DR

RTZ-VI-LCB is a model-based offline algorithm for robust two-player zero-sum Markov games (RTZMGs) that achieves the first provably optimal sample complexity w.r.t. state space S and action spaces {A, B}. It combines pessimistic robust value iteration with a Bernstein-style penalty and a novel two-stage subsampling scheme under partial data coverage and TV-distance uncertainty sets.

Problem

Existing offline MARL algorithms for robust two-player zero-sum Markov games suffer from suboptimal sample complexity—specifically the curse of multiagency—and fail to account for the influence of uncertainty levels {σ⁺, σ⁻} on sample efficiency. The best prior result (P²M²PO) achieves O(CᵣH⁵S²AB/ε²) but uses a looser concentrability measure and ignores uncertainty-level dependence.

Method

RTZ-VI-LCB proceeds in three steps: 1. Two-stage subsampling (Algorithm 1): Splits the offline dataset D into two halves; uses one half to compute trimmed state-visitation counts, the other to draw near-independent transition samples, eliminating within-episode statistical dependencies. 2. Empirical model construction: Builds empirical transition kernel P̂⁰ and reward r̂ from visit frequencies. 3. Backward robust value iteration with LCB (Algorithm 2): At each step h, computes optimistic robust Q-values via dual TV-distance formulations (strong duality to convert to scalar optimization), applies a Bernstein-style penalty term βₕ(s,a,b,V̂) = min(max(variance-based term, H·log-term/N), H) to account for estimation uncertainty, then calls a standard Nash solver (nashpy) on the resulting matrix game. The key new concentrability measure, robust unilateral clipped concentrability Cᵣ⋆, clips the density ratio at 1/(S(A+B)) rather than requiring full coverage, tightening the data-quality measure over prior Cᵣ.

Key Contributions

• RTZ-VI-LCB algorithm: First offline RTZMG algorithm optimal in S and {A,B}, achieving Õ(Cᵣ⋆H⁴S(A+B)·f(σ⁺,σ⁻,H)/ε²) sample complexity under partial coverage.
• Robust unilateral clipped concentrability (Cᵣ⋆): New criterion that accounts for distribution shift under environmental uncertainty; strictly tighter than prior Cᵣ.
• Matching information-theoretic lower bound: Ω(Cᵣ⋆SH⁴(A+B)/ε²) when min{σ⁺,σ⁻} ≲ 1/H; Ω(Cᵣ⋆SH³(A+B)/(ε²·min{σ⁺,σ⁻})) when min{σ⁺,σ⁻} ≳ 1/H—confirming near-tightness.
• Multi-RTZ-VI-LCB: Extension to m-player general-sum robust MGs, breaking the curse of multiagency.

Results

• RTZ-VI-LCB outperforms baseline RTZ-VI (no LCB penalty) across all 50 states at K=148 and all tested sample sizes.
• Log-log regression of value gap vs. sample size yields slope −0.4877, consistent with the theoretical O(K^{-1/2}) guarantee.
• Sample complexity comparison (omitting log factors):

Algorithm	Sample complexity	Notes
P²M²PO	Cᵣ·H⁵·S²·AB/ε²	Ignores uncertainty levels
RTZ-VI-LCB (ours)	Cᵣ⋆·H⁴·S(A+B)·f(σ⁺,σ⁻,H)/ε²	Optimal in S, A, B
Lower bound (low σ)	Cᵣ⋆·S·H⁴·(A+B)/ε²	Matches upper bound

Limitations

• Theory is restricted to tabular (finite S, A, B) settings; no function approximation.
• Computational bottleneck: Nash computation per state/step is PPAD-hard for robust zero-sum games; the paper delegates this to off-the-shelf solvers without addressing computational complexity.
• Two-stage subsampling halves the effective dataset size, incurring a constant-factor sample cost.
• Experiments use only randomly generated transition kernels (S=50, A=B=2, H=100); no real-world or structured domain evaluation.
• Extension to general-sum multi-player games (Multi-RTZ-VI-LCB) is presented but receives no empirical validation.

Relevance to Agentic AI / LLM Agents

This paper is primarily a theoretical RL contribution rather than directly addressing LLM-based agents; its relevance is indirect but real. Robust offline MARL is foundational for deploying autonomous agents in environments where the training distribution diverges from deployment (the sim-to-real gap), a central challenge for any agentic system trained offline and deployed in the open world. The pessimism-under-uncertainty principle (LCB) and partial-coverage analysis developed here apply broadly to multi-agent settings where agents must act reliably without exhaustive environment interaction—conditions that will become increasingly relevant as LLM-based agentic systems move toward offline or low-interaction training paradigms. The curse-of-multiagency result is particularly pertinent for multi-agent LLM systems where joint state-action spaces grow exponentially with agent count.