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

• URL: http://arxiv.org/abs/2512.00352v1
• Date: Sat, 29 Nov 2025 06:45:00 GMT
• Title: Sample-Efficient Tabular Self-Play for Offline Robust Reinforcement Learning
• Abstract summary: We focus on robust two-player zero-sum Markov games (TZMGs) in offline settings.<n>We propose a model-based algorithm (textitRTZ-VI-LCB) for offline RTZMGs, which is optimistic robust value iteration combined with a data-driven Bernstein-style penalty term for robust value estimation.<n>An information-theoretic lower bound is developed to confirm the tightness of our algorithm's sample complexity, which is optimal regarding both state and action spaces.
• Score: 29.063170235480317
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Multi-agent reinforcement learning (MARL), as a thriving field, explores how multiple agents independently make decisions in a shared dynamic environment. Due to environmental uncertainties, policies in MARL must remain robust to tackle the sim-to-real gap. We focus on robust two-player zero-sum Markov games (TZMGs) in offline settings, specifically on tabular robust TZMGs (RTZMGs). We propose a model-based algorithm (\textit{RTZ-VI-LCB}) for offline RTZMGs, which is optimistic robust value iteration combined with a data-driven Bernstein-style penalty term for robust value estimation. By accounting for distribution shifts in the historical dataset, the proposed algorithm establishes near-optimal sample complexity guarantees under partial coverage and environmental uncertainty. An information-theoretic lower bound is developed to confirm the tightness of our algorithm's sample complexity, which is optimal regarding both state and action spaces. To the best of our knowledge, RTZ-VI-LCB is the first to attain this optimality, sets a new benchmark for offline RTZMGs, and is validated experimentally.

Related papers

• A Unified Algorithmic Framework for Hybrid Reinforcement Learning in Tabular MDPs with Shifted Transition Dynamics [36.92549343895364]
  We propose a unified algorithmic framework featuring two algorithms: MIN-UCB-VI for regret minimization and MAX-LCB-VI for best policy identification.<n>We provide theoretical guarantees for our framework, including both instance-dependent and independent upper bounds on regret and sub-optimality gap.
  arXiv  Detail & Related papers  (2026-07-28T02:27:27Z)
• Evolving Robustness--Exploration Trade-off in Online Reinforcement Learning via Quantile Bayesian Risk MDPs [8.44570722529746]
  In online reinforcement learning, data scarcity creates uncertainty that makes robustness important early in learning, whereas sufficient exploration is needed to learn the true-environment optimal policy.<n>We study this time-varying robustness--a trade-off through a quantile Bayesian risk-aware Markov decision process (BR-MDP)<n>We propose an online Bayesian risk-aware algorithm with an adaptive quantile schedule that emphasizes early and gradually encourages exploration of less-visited state-action pairs.
  arXiv  Detail & Related papers  (2026-05-23T02:12:00Z)
• ProAct: Agentic Lookahead in Interactive Environments [56.50613398808361]
  ProAct is a framework that enables agents to internalize accurate lookahead reasoning through a two-stage training paradigm.<n>We introduce Grounded LookAhead Distillation (GLAD), where the agent undergoes supervised fine-tuning on trajectories derived from environment-based search.<n>We also propose the Monte-Carlo Critic (MC-Critic), a plug-and-play auxiliary value estimator designed to enhance policy-gradient algorithms.
  arXiv  Detail & Related papers  (2026-02-05T05:45:16Z)
• Distributionally Robust Online Markov Game with Linear Function Approximation [2.4636535146231613]
  Sim-to-real gap, where agents trained in a simulator face significant performance degradation during testing, is a fundamental challenge in reinforcement learning.<n>We devise algorithms that are sample efficient with interactive data collection and large state spaces.<n>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.
  arXiv  Detail & Related papers  (2025-11-11T04:56:39Z)
• Offline Learning for Combinatorial Multi-armed Bandits [56.96242764723241]
  Off-CMAB is the first offline learning framework for CMAB.<n>Off-CMAB combines pessimistic reward estimations with solvers.<n>Experiments on synthetic and real-world datasets highlight the superior performance of CLCB.
  arXiv  Detail & Related papers  (2025-01-31T16:56:18Z)
• SAM as the Guide: Mastering Pseudo-Label Refinement in Semi-Supervised Referring Expression Segmentation [66.92696817276288]
  SemiRES is a semi-supervised framework that effectively leverages a combination of labeled and unlabeled data to perform RES. SemiRES incorporates the Segment Anything Model (SAM), renowned for its precise boundary demarcation. In instances where a precise mask cannot be matched from the available candidates, we develop the Pixel-Wise Adjustment (PWA) strategy.
  arXiv  Detail & Related papers  (2024-06-03T15:42:30Z)
• Provably Efficient Information-Directed Sampling Algorithms for Multi-Agent Reinforcement Learning [50.92957910121088]
  This work designs and analyzes a novel set of algorithms for multi-agent reinforcement learning (MARL) based on the principle of information-directed sampling (IDS) For episodic two-player zero-sum MGs, we present three sample-efficient algorithms for learning Nash equilibrium. We extend Reg-MAIDS to multi-player general-sum MGs and prove that it can learn either the Nash equilibrium or coarse correlated equilibrium in a sample efficient manner.
  arXiv  Detail & Related papers  (2024-04-30T06:48:56Z)
• Distributionally Robust Reinforcement Learning with Interactive Data Collection: Fundamental Hardness and Near-Optimal Algorithm [14.517103323409307]
  Sim-to-real gap represents disparity between training and testing environments. A promising approach to addressing this challenge is distributionally robust RL. We tackle robust RL via interactive data collection and present an algorithm with a provable sample complexity guarantee.
  arXiv  Detail & Related papers  (2024-04-04T16:40:22Z)
• Sample Complexity of Offline Distributionally Robust Linear Markov Decision Processes [37.15580574143281]
  offline reinforcement learning (RL) This paper considers the sample complexity of distributionally robust linear Markov decision processes (MDPs) with an uncertainty set characterized by the total variation distance using offline data. We develop a pessimistic model-based algorithm and establish its sample complexity bound under minimal data coverage assumptions.
  arXiv  Detail & Related papers  (2024-03-19T17:48:42Z)
• Maximize to Explore: One Objective Function Fusing Estimation, Planning, and Exploration [87.53543137162488]
  We propose an easy-to-implement online reinforcement learning (online RL) framework called textttMEX. textttMEX integrates estimation and planning components while balancing exploration exploitation automatically. It can outperform baselines by a stable margin in various MuJoCo environments with sparse rewards.
  arXiv  Detail & Related papers  (2023-05-29T17:25:26Z)
• Sample Efficient Deep Reinforcement Learning via Local Planning [21.420851589712626]
  This work focuses on sample-efficient deep reinforcement learning (RL) with a simulator. We propose an algorithmic framework, named uncertainty-first local planning (UFLP), that takes advantage of this property. We demonstrate that this simple procedure can dramatically improve the sample cost of several baseline RL algorithms on difficult exploration tasks.
  arXiv  Detail & Related papers  (2023-01-29T23:17:26Z)
• Distributionally Robust Model-Based Offline Reinforcement Learning with Near-Optimal Sample Complexity [39.886149789339335]
  offline reinforcement learning aims to learn to perform decision making from history data without active exploration. Due to uncertainties and variabilities of the environment, it is critical to learn a robust policy that performs well even when the deployed environment deviates from the nominal one used to collect the history dataset. We consider a distributionally robust formulation of offline RL, focusing on robust Markov decision processes with an uncertainty set specified by the Kullback-Leibler divergence in both finite-horizon and infinite-horizon settings.
  arXiv  Detail & Related papers  (2022-08-11T11:55:31Z)
• Model-Based Multi-Agent RL in Zero-Sum Markov Games with Near-Optimal Sample Complexity [67.02490430380415]
  We show that model-based MARL achieves a sample complexity of $tilde O(|S||B|(gamma)-3epsilon-2)$ for finding the Nash equilibrium (NE) value up to some $epsilon$ error. We also show that such a sample bound is minimax-optimal (up to logarithmic factors) if the algorithm is reward-agnostic, where the algorithm queries state transition samples without reward knowledge.
  arXiv  Detail & Related papers  (2020-07-15T03:25:24Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.