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

Answer to W1

We thank the reviewer for this valuable feedback. To strengthen the empirical validation, we have added a new comparison against $\mathrm{P}^2\mathrm{M}^2\mathrm{PO}$, a recent baseline designed for RTZMGs. Specifically, we report the performance gap $\mathrm{Gap}({\mu}, {\nu})$ with respect to dataset size across both methods. To demonstrate our optimal sample complexity scaling in the action space, we use a setting with $S = 50$, $A = B = 3$, and $H = 100$, which differs from the configuration in Appendix A (where $AB = A + B$). The new results are presented in the following table, which will be included in the revised manuscript:

These results highlight the superiority of our method across varying dataset sizes and validate the theoretical claims under controlled experimental conditions. While we focus on tabular settings in this work, our algorithm can serve as a theoretical foundation for scalable extensions based on linear or kernel-based function approximation.

Answer to W2

Thank you for this helpful suggestion. Our current study focuses on tabular settings, which provide a clean foundation for precise theoretical analysis and algorithmic development. To scale to larger and more practical domains, straightforward approaches are function approximation methods, particularly linear or kernel-based methods, as explored in prior works, e.g., Refs. [1,2]. These approaches enable generalization over large or continuous state-action spaces while preserving a degree of theoretical tractability. We will include a brief discussion of this extension path in Section 5 of the revised version, stating that: "While RTZ-VI-LCB is developed in the tabular setting, it offers a solid theoretical foundation for robust offline multi-agent learning. Generalizing its core principles, such as data-driven penalization, to high-dimensional settings via function approximation (e.g., linear or kernel-based methods [1,2]) represents a promising direction toward practical deployment."

Answer to Q1

Thank you for this insightful question. In general, estimating $C_{\mathrm{r}}^\star$ from purely offline data is information-theoretically impossible. Consider, for example, the degenerate robust two-player Markov game with $\sigma^+=\sigma^- = 0$ and $B=1$, which reduces to the standard single-agent RL setting. For an MDP with horizon $H=2$, whose first step has a singleton state space $\mathcal{S}_ 1=\\{0\\}$ and action space $\mathcal{A}_ 1=\\{0,1\\}$, and whose second step has state space $\mathcal{S}_ 2=\\{0,1\\}$ and singleton action space $\mathcal{A}_ 2=\\{0\\}$, [24] has shown it is impossible to determine the sample size required or provide a valid certificate. Therefore, estimating $C_ {\mathrm{r}}^\star$ is also generally infeasible in RTZMGs.

Fortunately, our algorithm does not rely on prior knowledge of $C_{\mathrm{r}}^\star$. It can be executed with any offline dataset and will succeed once the underlying task becomes statistically feasible. Although we cannot determine in advance whether a given dataset is sufficient, RTZ-VI-LCB remains practically useful by avoiding reliance on unverifiable assumptions.

We will incorporate this discussion near Definition 4.1 in the revised manuscript, adding: "Estimating the concentrability coefficient $C_{\mathrm{r}}^\star$ from offline data is generally information-theoretically impossible, as demonstrated even in the single-agent case by the example construction in Section 3.4 of [24]. Fortunately, this does not affect the execution of our algorithm."

Answer to Q2

Thank you for this thoughtful question. In this work, we do not explicitly address the computational complexity of solving the robust Nash equilibrium (NE). That is, our algorithm assumes access to arbitrary robust NE solver and focuses on the sample complexity of the overall procedure. In addition, our framework is compatible with any computational relaxations or approximation methods for solving RTZMGs, such as Monte-Carlo sampling (Ref. [3]). In our experiments, we use the Python package nashpy for NE computation.

We will add the following remark to the manuscript to clarify this implementation detail: "In our experiments, the robust NE at each state and timestep is computed using standard NE solvers, i.e., the Python package nashpy. Our algorithm is compatible with any exact or approximate NE solver, including computational relaxations or sampling-based methods. If an approximate solver is used, the corresponding approximation error will be introduced into our theoretical analysis as an additional term."

Answer to Q3

Thank you for highlighting this important point. Our current work focuses on multi-agent tabular settings (see Theorem 4.4 and Appendix F) to facilitate precise theoretical analysis. To extend RTZ-VI-LCB to high-dimensional cases, a natural direction is to incorporate function approximation, particularly using linear function classes or kernel-based representations. Key challenges in this setting include ensuring concentration and coverage conditions in high-dimensional spaces. As responded to Weakness 2, we will include a discussion of this extension path in Section 5 of the revised version.

Answer to Q4

Thank you for the insightful question. The Bernstein-style penalty acts as an adaptive, variance-aware term. In particular, it significantly improves the algorithm’s performance when the actual variance is much smaller than the trivial bound of $H^2$. By leveraging a tighter, data-dependent penalty, the algorithm can achieve improved performance.

In contrast, the two-stage subsampling is primarily introduced for theoretical analysis, specifically to handle within-episode temporal dependence. In practice, we have observed that this subsampling step is not strictly required for the empirical performance. However, how to rigorously remove this step while maintaining theoretical guarantees remains an open problem for future research.

We will clarify these insights in Section 1.1 and discuss the practical and theoretical roles of each component in more detail.

Reference

[1] Nika, Andi, et al. "Corruption-robust offline two-player zero-sum Markov games." International Conference on Artificial Intelligence and Statistics. PMLR, 2024.

[2] Lim, Shiau Hong, and Arnaud Autef. "Kernel-based reinforcement learning in robust Markov decision processes." International conference on machine learning. PMLR, 2019.

[3] Ponsen, Marc, Steven De Jong, and Marc Lanctot. "Computing approximate Nash equilibria and robust best-responses using sampling." Journal of Artificial Intelligence Research 42, 575-605, 2011.

Answer to W1 and Q1

We sincerely appreciate the reviewer’s insightful comment regarding the novelty of our work. The study by Yan et al. [a] investigates offline Markov games (MGs) using the LCB approach. Our work builds upon this line by explicitly incorporating environmental uncertainty, resulting in a substantially stronger and more challenging formulation. In the presence of uncertainty, we can no longer solve the value function in its primal form and need to operate instead in the dual space. To address this, we introduce a novel Bernstein-style penalty that ensures the empirical variance estimate (i.e., the plug-in estimate) closely matches the true variance. Through these innovations, we establish a minimax optimal sample complexity that significantly improves over prior results in its dependence on the state and action spaces under uncertainty. While the best existing bounds scale as $O\left( \frac{C_ \mathrm{r} H^5 S^2 A B}{\varepsilon^2} \right),$ our result achieves $O\left( \frac{C^\star_\mathrm{r} H^4 S(A+B)}{\varepsilon^2} \cdot f(\sigma^+, \sigma^{-}, H) \right)$ with $C^\star_\mathrm{r}\le C_\mathrm{r}$ and $f(\sigma^+, \sigma^{-}, H)\le H$, which notably reduces the dependence on both the state and action dimensions. We will revise the manuscript to include a discussion clarifying the novelty, stating: "RTZ-VI-LCB extends the offline MGs algorithm proposed in [a] by explicitly incorporating environmental uncertainty and solving the dual problem."

Answer to W2

Thank you for pointing this out. We apologize for the omission and will revise Section 1.2 (Related Work) to incorporate the missing references more comprehensively. Specifically, in the paragraph on Single-agent robust offline RL, we will include the following sentence as "Several works [b, c] study offline robust RL with linear function approximation, while others consider various uncertainty metrics such as total variation, $\chi^2$-divergence, and KL-divergence [d], or operate under more general settings without requiring strong coverage assumptions [e]." In the paragraph on Robustness in MARL, we will add "Optimal dependence on the action space size $\{A, B\}$ has been achieved in recent work from an online learning perspective [f], but the offline robust formulation in multi-agent settings remains largely underexplored."

Answer to Q2

Thank you for this insightful and inspirational question. Under a generative model with uniform sampling, the visitation distribution becomes explicit; that is, $d_h^{\mathsf{n}, P^0}(s, a, b) = \frac{1}{SAB}$. In this case, it is sufficient to choose $C_{\mathrm{r}}^\star = \min\\{A, B\\}$, which can be readily verified to satisfy Eq. (20). This choice leads to the sample complexity

which matches the bound established in [34] and confirms the efficiency of our approach in the generative model setting. We will add a corresponding remark after Theorem 4.2 to clarify this point.

I appreciate authors' detailed and quick response. I have no more questions and have raised my score.

Answer to Question about time complexity and the tradeoff between time complexity and sample complexity

We thank the reviewer for this important question. As the reviewer mentioned, computing Nash Equilibria (NE) for two-player general-sum games is PPAD-hard. Since our algorithm solves an NE at each horizon and state, its overall time complexity is also PPAD-hard.

Regarding the tradeoff, there does not exist a direct tradeoff between time complexity and sample complexity, as the main computational bottleneck is NE computation. A potential aspect of tradeoff could lie in the number of NE computations required by the algorithm. In this regard, the number of NE computations in our algorithm is $HS$ (with $H$ as the horizon and $S$ as the number of states), which is optimal. Therefore, our work primarily focuses on improving sample efficiency, as the time complexity per NE computation is dictated by the underlying hardness of NE-solving itself.

Answer to uncertainty sets beyond $(s,a,b)$-rectangularity

We thank the reviewer for this valuable suggestion. Extending our framework to uncertainty sets beyond $(s,a,b)$-rectangularity is indeed an important direction. In particular, KL-divergence-based uncertainty sets offer a principled connection between hard robustness and soft entropy regularization. To extend our algorithm to handle KL divergence, two key aspects must be addressed.

Algorithmically, RTZ-VI-LCB can be generalized by replacing its robust Bellman operator with an entropy-regularized (soft) Bellman operator and solving for a regularized Nash equilibrium. Additionally, the data-driven penalty term would need to be modified. Instead of relying on the empirical variance $\mathsf{Var}_ {\widehat{P}^0_ {h,s,a,b}}(\widehat{V})$, the penalty should incorporate the minimal nonzero transition probability $\hat{P}_ {\min, h}(s, a, b) = \min_ {s'} \\{ \hat{P}_ h^0(s' \mid s, a, b) : \hat{P}_ h^0(s' \mid s, a, b) > 0 \\}$.

As for theoretical analysis, this generalization would require a different complexity characterization. In particular, the sample complexity would depend on the smallest positive transition probability $P_ {\min}^\star = \min_ {h, s, a, b, s'} \\{ P_ h^0(s' \mid s, \mu_h^\star(s), \nu_h^\star(s)) > 0 \\}$ under the optimal robust policy, as well as a burn-in cost condition on the smallest positive state transition probability $P_ {\min}^{\sf{n}} = \min_ {h, s, a, b, s'} \\{ P_ h^0(s' \mid s, a, b) > 0 : d_h^{\mathsf{n}, P^0}(s, a, b) > 0 \\}$ of the behavior policy.

We will include this discussion in Section 5 to clarify how our algorithm can be extended to more general uncertainty structures, including KL-divergence-based sets.

We would like to thank you for the time and effort you dedicated to the review.

Answer to Q1

Thank you for this intriguing question. In our setting, the number of NE computations required under the robust NE policy is $HS$. All algorithms in the same setting need to calculate at least $HS$ number of NE computations since there are $HS$ different states. Hence, as the reviewer pointed out, our approach achieves optimality in both sample complexity and computational complexity to find an $\varepsilon$-optimal robust NE policy.

Answer to Q2

We thank the reviewer for this valuable suggestion. In this work, we do not explicitly address the computational complexity of solving the robust NE. In our implementation, we employ the Python package nashpy for NE computation.

Generally, our framework is compatible with a wide range of computational relaxations and approximation schemes. For instance, NE computation can be approximated using Monte Carlo sampling–based methods (Ref. [1]). In addition, another way to address such a computation issue is to consider CE (Ref. [2]) or CCE (Ref. [3]) instead of NE, both of which admit polynomial-time solutions even in the robust setting. In this case, our algorithm can be directly adapted by substituting $\mathsf{ComputNash}(\cdot)$ in Algorithm 2 with the corresponding CE or CCE computation.

We will incorporate a discussion on NE approximations and relaxations into the revised manuscript to clarify the computational aspects.

Reference

[1] Ponsen, Marc, Steven De Jong, and Marc Lanctot. "Computing approximate Nash equilibria and robust best-responses using sampling." Journal of Artificial Intelligence Research, 42, 575-605, 2011.

[2] Chen, Ziyi, Shaocong Ma, and Yi Zhou. "Finding correlated equilibrium of constrained markov game: A primal-dual approach." Advances in Neural Information Processing Systems, 35, 25560-25572, 2022.

[3] Chen, Zixiang, Dongruo Zhou, and Quanquan Gu. "Almost optimal algorithms for two-player zero-sum linear mixture markov games." International Conference on Algorithmic Learning Theory, PMLR, 2022.