Research map / Multi-agent systems and games / Games and equilibria
Sample-Efficient Tabular Self-Play for Offline Robust Reinforcement Learning
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.
Proposes RTZ-VI-LCB, a model-based offline robust value iteration with Bernstein-style LCB penalty and two-stage subsampling for robust two-player zero-sum Markov games, proving near-optimal sample complexity in S and actions and a matching lower bound.
Problem
Sample-efficient offline learning of robust Nash equilibria in tabular two-player zero-sum Markov games with transition uncertainty sets and partial data coverage.
Approach
Optimistic (pessimistic-LCB) robust value iteration with a data-driven Bernstein-style penalty and a two-stage subsampling procedure that removes intra-episode dependence, plus a new robust unilateral clipped concentrability coefficient C*_r that replaces the prior C_r.
Key results
- RTZ-VI-LCB sample complexity upper bound of Õ(C*_r H^4 S(A+B) f/ε^2), matched by a lower bound Ω(C*_r S H^4(A+B)/ε^2) for small uncertainty levels.
- Empirically, log-log regression of the gap vs sample size gives slope -0.4877, matching the theoretical 1/sqrt(K) rate.
- In a table over log(KH) from 6 to 9, RTZ-VI-LCB gap is lower than P2M2PO (e.g., 3.1699 vs 3.5970 at log(KH)=6; 0.0819 vs 0.0890 at log(KH)=9).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use RTZ-VI-LCB instead of P²M²PO | Offline robust two-player zero-sum Markov games · Randomly generated RTZMGs, log(KH)=6 | sub-optimality performance gap: 3.5970 -> 3.1699 | Helped |
| Use RTZ-VI-LCB instead of P²M²PO | Offline robust two-player zero-sum Markov games · Randomly generated RTZMGs, log(KH)=7 | sub-optimality performance gap: 2.2503 -> 2.1498 | Helped |
| Use RTZ-VI-LCB instead of P²M²PO | Offline robust two-player zero-sum Markov games · Randomly generated RTZMGs, log(KH)=8 | sub-optimality performance gap: 0.2404 -> 0.2324 | Helped |
| Use RTZ-VI-LCB instead of P²M²PO | Offline robust two-player zero-sum Markov games · Randomly generated RTZMGs, log(KH)=9 | sub-optimality performance gap: 0.0890 -> 0.0819 | Helped |
| Increase the sample size | RTZ-VI-LCB · Randomly generated RTZMGs | sub-optimality performance gap: 3.1699 -> 2.1498 -> 0.2324 -> 0.0819 | Helped |
Limitations
- Tabular setting only; experiments limited to small synthetic MDPs.
- Estimating C*_r from data is information-theoretically impossible in general, so the coefficient is not directly checkable.
- Robust NE computation per state is PPAD-hard in general, relying on approximate solvers.
Experimental setup
Datasets: randomly generated tabular transition kernels (synthetic)
Benchmarks: synthetic randomly generated robust two-player zero-sum MGs
Metrics: sub-optimality gap log-log slope of gap vs sample size
Baselines: P2M2PO RTZ-VI
Builds on: P2M2PO single-agent clipped concentrability (pessimistic offline RL) robust MDP dual formulation (TV distance) VI-ULCB
Closest papers by meaning
- Sample-Efficient Robust Multi-Agent Reinforcement Learning in the Face of Environmental Uncertainty (ICML 2024 · similarity 0.91)
- Taming the Curses of Multiagency in Robust Markov Games with Large State Space through Linear Function Approximation (NeurIPS 2026 · similarity 0.90)
- Breaking the Curse of Multiagency in Robust Multi-Agent Reinforcement Learning (ICML 2025 · similarity 0.89)
- Incentivize without Bonus: Provably Efficient Model-based Online Multi-agent RL for Markov Games (ICML 2025 · similarity 0.89)
- Minimax Optimal and Computationally Efficient Algorithms for Distributionally Robust Offline Reinforcement Learning (NeurIPS 2024 · similarity 0.88)
- Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithms (NeurIPS 2024 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.