Near-Optimal Sample Complexities of Divergence-based S-rectangular Distributionally Robust Reinforcement Learning

We thank the reviewer for their comments and valuable suggestions. We address their questions below.

Q1. What's the theoretical complexity lower bound?

The theoretical complexity lower bound under the $\chi^2$-divergence uncertainty set is given in [1], which is

We currently have not included a direct table comparing our results with this lower bound, but will mention and compare it in the discussion section of the revised version.

[1] Yang, W., Zhang, L., & Zhang, Z. (2022). Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50(6), 3223-3248.

Q2.Could you cite the following works of value iteration on robust MDP? Also, [1] seems to have better dependence on $\epsilon$. How to explain?

Thank you for your question and literature suggestion. We will cite the related works [1,2] on solving robust MDPs. Regarding the $\epsilon$-dependence, [1] and [2] focus on an optimization setting where the underlying robust MDP instance is known to the optimizer. In contrast, our setting assumes an unknown robust MDP instance where we need to learn an optimal robust policy from data. Therefore, [1,2] report the iteration complexity, whereas our paper analyzes the statistical complexity. Since these two types of complexity measure different aspects of the problem, their dependence on $\epsilon$ is not directly comparable.

[1] Grand-Clément, J. and Kroer, C. (2021). Scalable first-order methods for robust mdps. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12086–12094.

[2] Kumar, N., Levy, K., Wang, K., and Mannor, S. (2023b). An efficient solution to s-rectangular robust markov decision processes. ArXiv:2301.13642.

Q3.Are Lemmas 1 and 2 proposed by you or existing literature? If latter, please cite.

A similar result was presented in previous work [1] where $R$ is only a function of $S_t,A_t$. However, since we consider the case where $R(S_t, A_t, S_{t+1})$ can depend on the next state (which is important to many application settings, e.g., inventory problems), the results in [1] cannot be applied directly. So, we prove these lemmas in this paper.

[1] Yang, W., Zhang, L., & Zhang, Z. (2022). Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50(6), 3223-3248.

Q4. To reproduce Section 5.2 (the second experiment), what does "estimation error" mean? (might be defined by equations) What is the discount factor $\gamma$?

Thank you for pointing out this clarity issue. The “estimation error” is defined as

where $V_{\mathcal{P}}^{\pi}$ and $V_{\hat{\mathcal{P}}}^{\pi}$ denote the value functions under the true and estimated transition probability, respectively. We thank the reviewer for pointing out the omission of the discount factor. In our experiments, we set $\gamma = 0.9$. We have added these clarifications in the revision.

Q6. $\Vert R+\gamma v\Vert_{\infty}$ in Proposition 2 could be defined, especially considering that $R(s,a)$ and $v(s)$ take different input variables.

Thanks for pointing this out. Here, $\Vert R+\gamma v\Vert_{\infty}$ is defined as

where $R(s, a, s')$ is the reward function and $v(s')$ is the value function at state $s'$. We will make it clear in the revised version.

Q7. In Section 5, does $n_0=n$ ?

No, $n_0$ and $n$ are not the same. Here, $n$ denotes the total number of samples, while $n_0$ is the number of samples collected for each $(s,a)$ pair. They are related by

We have clarified this in the revision.

Q5.Q8. $A_t$ insead of $a_t$ in Example 1. Figure 4 caption: "number of actions".

We thank the reviewer for carefully pointing out these typos. We will correct them in the revision.

Thank the authors for your response. My questions are well solved. Since the theoretical result is obtained using empirical transition evaluation without significant challenge, I plan to keep my rating for now.

Dear reviewer bgCq,

Thank you for your feedback and thoughtful review.

Best regards,
The authors

We thank the reviewer for their comments and valuable suggestions. We address their questions below.

Q1. The approach builds empirical kernel using samples which is not feasible for large states space MDPs.

We thank the reviewer for their feedback. However, we want to remark that model-based methods that uses an empirical kernel or empirical measures are important cases for not only understanding the statistical complexity but also practical implementation. This is because, in many high-risk real-world settings such as aerospace engineering, finance, or health care, we usually cannot rely on function approximation. Moreover, from a sample-efficiency perspective, empirical kernel-based methods usually enjoys better efficiency, hence are suitable for applications where the data is scarce [1]. On the other hand, we are considering a generative model setting, and it is usually a first step to study model-based methods, as they are typically more efficient. Moreover, the analysis of these model-based methods is an important building blocks for other application-specific designs in future research.

[1] Chua, Kurtland, et al. "Deep reinforcement learning in a handful of trials using probabilistic dynamics models." Advances in neural information processing systems 31 (2018).

Q2.Para (Line 40-44) do not mention the optimal policies for S-rect can be stochastic and has a threshold power policy nature.

We have mentioned that the optimal policies for S-rectangular models can be stochastic in lines 60-66. We will add this fact around Example 1.

Q3. Literature review missing mention large bodies of relevant works such as s-rectangular works [2,4,8] , non -rectangular works [3,5] that are even less convervative than s-rect, KL-based SA-rect work [6], and [7] that has sample complexity for R-contamination uncertainty sets

We thank the reviewer for pointing out these important and relevant works [2, 3, 4, 5, 6, 7, 8]. These works primarily focus on optimization, while we mainly focus on the statistical aspects. We will make sure to cite and properly acknowledge them in the revised version.

[9,10] focus on average-reward SA-rectangular robust RL, while we focus on discounted-reward S-rectangular robust RL. Furthermore, [10] is uploaded after Neurips submission deadline and the first version of [9] has some mistakes. Therefore, there are not relevant to this paper.

[2]@inproceedings{ kumar2024efficient, title={Efficient Value Iteration for s-rectangular Robust Markov Decision Processes}, author={Navdeep Kumar and Kaixin Wang and Kfir Yehuda Levy and Shie Mannor}, booktitle={Forty-first International Conference on Machine Learning}, year={2024}, url={https://openreview.net/forum?id=J4LTDgwAZq} }

[3] Gadot, U., Derman, E., Kumar, N., Elfatihi, M. M., Levy, K., & Mannor, S. (2024). Solving Non-rectangular Reward-Robust MDPs via Frequency Regularization. Proceedings of the AAAI Conference on Artificial Intelligence, 38(19), 21090-21098. https://doi.org/10.1609/aaai.v38i19.30101

[4]@inproceedings{10.5555/3666122.3668721, author = {Kumar, Navdeep and Derman, Esther and Geist, Matthieu and Levy, Kfir and Mannor, Shie}, title = {Policy gradient for rectangular robust Markov decision processes}, year = {2023}, publisher = {Curran Associates Inc.}, address = {Red Hook, NY, USA}, booktitle = {Proceedings of the 37th International Conference on Neural Information Processing Systems}, articleno = {2599}, numpages = {25}, location = {New Orleans, LA, USA}, series = {NIPS '23} }

[5]@misc{kumar2025dualformulationnonrectangularlp, title={Dual Formulation for Non-Rectangular Lp Robust Markov Decision Processes}, author={Navdeep Kumar and Adarsh Gupta and Maxence Mohamed Elfatihi and Giorgia Ramponi and Kfir Yehuda Levy and Shie Mannor}, year={2025}, eprint={2502.09432}, archivePrefix={arXiv}, primaryClass={cs.AI}, url={https://arxiv.org/abs/2502.09432}, }

[6] @inproceedings{ gadot2024bring, title={Bring Your Own (Non-Robust) Algorithm to Solve Robust {MDP}s by Estimating The Worst Kernel}, author={Uri Gadot and Kaixin Wang and Navdeep Kumar and Kfir Yehuda Levy and Shie Mannor}, booktitle={Forty-first International Conference on Machine Learning}, year={2024}, url={https://openreview.net/forum?id=UqoG0YRfQx} }

[7] @inproceedings{ wang2021online, title={Online Robust Reinforcement Learning with Model Uncertainty}, author={Yue Wang and Shaofeng Zou}, booktitle={Advances in Neural Information Processing Systems}, editor={A. Beygelzimer and Y. Dauphin and P. Liang and J. Wortman Vaughan}, year={2021}, url={https://openreview.net/forum?id=IhiU6AJYpDs} }

[8]@misc{derman2021twiceregularizedmdpsequivalence, title={Twice regularized MDPs and the equivalence between robustness and regularization}, author={Esther Derman and Matthieu Geist and Shie Mannor}, year={2021}, eprint={2110.06267}, archivePrefix={arXiv}, primaryClass={cs.LG}, url={https://arxiv.org/abs/2110.06267}, }

[9]@misc{xu2025finitesampleanalysispolicyevaluation, title={Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning}, author={Yang Xu and Washim Uddin Mondal and Vaneet Aggarwal}, year={2025}, eprint={2502.16816}, archivePrefix={arXiv}, primaryClass={stat.ML}, url={https://arxiv.org/abs/2502.16816}, }

[10]@misc{xu2025efficientqlearningactorcriticmethods, title={Efficient -Learning and Actor-Critic Methods for Robust Average Reward Reinforcement Learning}, author={Yang Xu and Swetha Ganesh and Vaneet Aggarwal}, year={2025}, eprint={2506.07040}, archivePrefix={arXiv}, primaryClass={cs.LG}, url={https://arxiv.org/abs/2506.07040}, }

Dear Reviewer Qk39,

We hope that we have addressed all of your concerns. As the author-reviewer discussion period concludes, please do not hesitate to reach out if further clarifications are needed. We would be delighted to provide additional explanations or adjustments.

Thank you again for your invaluable feedback and contributions to this work.

Best wishes,
The authors

We thank the reviewer for their comments and valuable suggestions.

Q1. Theorems 1 and 2 are not the sample complexity discussed in [1, 2].

We thank the reviewer for their input. We want to remark that the sample complexity of learning the optimal value function within an absolute error of $\epsilon$ is an important question by itself [4]. In particular, they are useful for the analysis of value-based procedures, as well as for certifying the performance of the robust optimal policy. With this said, we recognize that the sample complexity of obtaining an $\epsilon$ optimal policy is also important and is not hard to obtain from our analysis. So, we enrich our paper by proving the following theorem that aligns with the sample complexity discussion in [1,2]. In particular, we show the following theorem 3 in the revision. Recall that

Theorem 3 Under the KL-divergence uncertainty set, with probability $1-\eta$ $\sup_{\pi\in\Pi}V_{\mathcal{P}}^{\pi}-V_{\mathcal{P}}^{\hat{\pi}^\*}\leq\frac{18}{\sqrt{n\mathfrak{p}}(1-\gamma)^2}\sqrt{\log{(4|\mathcal{S}|^2|\mathcal{A}|/\eta)}}.$ Under $f_k$-divergence uncertainty set, with probability $1-\eta$

$$$$

\sup_{\pi\in\Pi}V_{\mathcal{P}}^{\pi}-V_{\mathcal{P}}^{\hat{\pi}^*}\leq\frac{6\cdot2^{k^*}k^*}{\sqrt{n\mathfrak{p}}(1-\gamma)^2}\sqrt{\log\left(4|S|^2|\mathcal{A}|/\eta\right)}.

\sup_{\pi\in\Pi}\left\Vert\hat{\mathbf{T}}^{\pi}(v)-\mathcal{T}^{\pi}(v)\right\Vert_{\infty}\leq \frac{9\Vert R+\gamma v\Vert_\infty}{\sqrt{n\mathfrak{p}}}\sqrt{\log{(4|\mathcal{S}|^2|\mathcal{A}|/\eta)}},

\sup_{\pi\in\Pi}\left\Vert\hat{\mathbf{T}}^{\pi}(v)-\mathcal{T}^{\pi}(v)\right\Vert_{\infty}\leq \frac{3\cdot2^{k^*}k^*\Vert R+\gamma v\Vert_{\infty}}{\sqrt{n\mathfrak{p}}}\sqrt{\log\left(4|S|^2|\mathcal{A}|/\eta\right)}.

Lemma 12: Let $\hat{\pi}^\*:=\arg\max_{\pi}V_{\hat{\mathcal{P}}}^{\pi}$, we have $0\leq \sup_{\pi\in\Pi}V_{\mathcal{P}}^{\pi}-V_{\mathcal{P}}^{\hat{\pi}^\*}\leq 2\sup_{\pi\in\Pi}\left\Vert V_{\hat{\mathcal{P}}}^{\pi}-V_{\mathcal{P}}^{\pi}\right\Vert_{\infty}$

With Lemma 11 and 12, we have that under KL-divergence uncertainty set, with probability $1-\eta$

under $f_k$-divergence uncertainty set, with probability $1-\eta$

This completes the proof of Theorem 3.

We then prove the claimed lemmas as follows.

Proof of Lemma 11

Similarly to Proposition 1, we first prove that $\mathcal{T}^{\pi}$ and $\hat{\mathbf{T}}^{\pi}$ are $\gamma$-contraction operators.

where $\Vert P_s\Vert_\infty=\sup_{\Vert v\Vert_\infty=1}\Vert P_sv\Vert_\infty$ is the induced operator norm. By replacing $P_s$ with $P_{s,n}$, we obtain

Following the proof of Proposition 1, which only requires that $V_{\mathcal{P}}^{\pi}$ and $V_{\hat{\mathcal{P}}}^{\pi}$ are fixed points of $v = \mathcal{T}^{\pi}(v)$ and $v = \hat{\mathbf{T}}^{\pi}(v)$, respectively, and that $\mathcal{T}^{\pi}$ and $\hat{\mathbf{T}}^{\pi}$ are $\gamma$-contraction operators, we then obtain

Proof of Lemma 12

Note that

Q2. The involvement of the minimum support probability for $f_k$-divergence uncertainty set is sub-optimal when compared to [Theorem 3.2(b), 1].

In our analysis, we focus on a $\rho$-free bound that holds uniformly for all $k$. We believe that the minimum support probability should be present in the bound as $k \to 1$. This is reflected in [3], as without such a minimum support probability assumption, it is not possible to achieve the $n^{-1/2}$ rate in a minimax sense. In contrast, [Theorem 3.2(b), 1] considers only the $\chi^2$-divergence case, and yields a looser bound in terms of its dependence on $\rho$ as $\rho \to 0$. Moreover, their dependence on $\mathfrak{p}$ is worse than ours in the KL-divergence setting. We believe that a $\mathfrak{p}$-free bound for the $\chi^2$-divergence may be attainable through another specialized analysis.

Q3. Can you explain why the bounds in Theorems 1 and 2 do not involve the uncertainty radius $\rho$?

We thank the reviewer for the insightful comments. Intuitively, as $\rho = 0$ represents the non-robust MDP setting, the sample complexity of robust policy learning should not be unbounded as $\rho\rightarrow 0$. This behaviour of the sample complexity’s independence of $\rho$ as $\rho\rightarrow 0$ is first observed in [4] in the SA rectangular setting with KL divergence, and we generalize to the more challenging S-rectangular setting with both KL and $f_k$ divergences, where the SOTA bounds all have a $1/\rho$ dependence [1].

Technically, for the KL‑divergence, the uncertainty radius $\rho$ is canceled out in the following calculation since $f$ contains $-\lambda|\mathcal{A}|\rho$:

For the $f_k$‑divergence, according to Lemma 9 (D.3), $c(k,\rho,|\mathcal{A}|)$ can be expressed in terms of $\mu$ and $w$:

Therefore, $\rho$ no longer appears in the subsequent analysis or the final bounds.

[1] Yang, W., Zhang, L., & Zhang, Z. (2022). Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50(6), 3223-3248.

[2] Clavier, P., Shi, L., Le Pennec, E., Mazumdar, E., Wierman, A., & Geist, M. (2024). Near-Optimal Distributionally Robust Reinforcement Learning with General $L_p$ Norms. Advances in Neural Information Processing Systems, 37, 1750-1810.

[3] Duchi, J. C., & Namkoong, H. (2021). Learning models with uniform performance via distributionally robust optimization. The Annals of Statistics, 49(3), 1378-1406.

[4] Wang, S., Si, N., Blanchet, J., & Zhou, Z. (2024). Sample complexity of variance-reduced distributionally robust Q-learning. Journal of Machine Learning Research, 25(341), 1-77.

Dear Reviewer 5h1f,

We hope that we have addressed all of your concerns. As the author-reviewer discussion period concludes, please do not hesitate to reach out if further clarifications are needed. We would be delighted to provide additional explanations or adjustments.

Thank you again for your invaluable feedback and contributions to this work.

Best wishes, The authors

We thank the reviewer for their comments and valuable suggestions. We address their questions below.

W&Q1.Numerical experiments

We thank the reviewer for the valuable suggestion for additional numerical validation. In response to the reviewer’s concerns about the comprehensiveness and robustness of the experiments, we would like to clarify two key points:

First, our algorithm does not contain hyper‑parameters that require tuning; the inputs to the algorithm are all known quantities that do not require prior knowledge of the MDP instance.

Second, regarding the original submission, we performed only one run on a benchmark instance. There was no repetition and hence error bars could not be produced. Our figure demonstrates remarkably low variability in the performance of our algorithm: the log-log plot reveals an error convergence rate with a slope of −0.5 even without averaging. However, your suggestion to include an error bar diagram could improve the clarity. We implemented this in our revision and produced the tables below.

In the revised manuscript, to further verify the performance of our method, we have introduced additional empirical validation on multiple instances with different environment parameters (e.g., price, purchase cost, etc.). For each instance, we conduct 200 independent runs with different random seeds, where the only source of randomness is the sample set drawn from the demand distribution. The aggregated results for these instances are reported below.

instance 1 (original instance in the paper) $I=10,B=5,O=5,p=3,c=2,h=0.2,b=3,\gamma =0.9, P_D=[0.1,0.2,0.3,0.3,0.1]$ with KL divergence unceratinty sets.

Instance 2: New instance (low back order cost setting) $I=10,B=5,O=5,p=3,c=2,h=0.2,b=1,\gamma =0.9, P_D=[0.1,0.2,0.3,0.3,0.1]$ with KL divergence unceratinty sets.

Instance 3: New instance (high holding cost setting)

$I=10,B=5,O=5,p=3,c=2,h=1,b=3, \gamma =0.9, P_D=[0.1,0.2,0.3,0.3,0.1]$ with KL divergence unceratinty sets.

W&Q2. Guidance to the practice

We would also like to clarify that both the statistical analysis and optimization procedure are important factors in achieving a practical algorithm. While there are many existing studies on how to efficiently compute the optimal policy given an S-rectangular robust MDP model under $f_k$ and KL divergence from an optimization point of view [1,2], the statistical complexity upper bounds in the literature have been overly pessimistic, presenting a suboptimal $|\mathcal{S}|^2$ dependence. In contrast, our work marks the first contribution that exhibits a linear sample complexity dependence on the number of states $|\mathcal{S}|$ in the $f_k$ and KL divergence settings. This improved dependence elicits the fact that achieving robust policy learning is not statistically more challenging than in the classical MDP setting. Therefore, coupled with the fact that $f_k$ and KL divergence are the most commonly used models in practice, our sample complexity results can guide the design of practical robust algorithms that are as sample-efficient as non-robust algorithms.

[1] Ho, C. P., Petrik, M., & Wiesemann, W. (2018, July). Fast Bellman updates for robust MDPs. In International Conference on Machine Learning (pp. 1979-1988). PMLR.

[2] Ho, C. P., Petrik, M., & Wiesemann, W. (2022). Robust $\phi$-Divergence MDPs. Advances in Neural Information Processing Systems, 35, 32680-32693.

Dear Reviewer G8HC,

We sincerely appreciate the time and effort you have dedicated to reviewing our manuscript and providing valuable feedback.

As the discussion phase ends soon (by 8.6), we hope our responses have addressed your concerns. If you need further clarification or have any additional concerns, we are willing to continue the communication with you.

Best regards,
The Authors