Answer to reviewer QVRk

We appreciate the reviewer for careful review and insightful feedback. It is rewarding to know that the reviewer recognizes the significance of our contributions. In what follows, we provide our response to the reviewer's comments.

Overall, I found the main paper to be well-written, though it does contain some minor typos, formatting inconsistencies, and punctuation errors within the main text.

We will try to correct as much as possible all minor typos in the next version of the manuscript.

• 1- At the technical level, beyond considering a new dual formulation, what is the main difference compared to the proof scheme in Shi et al., 2023?

The challenge in comparing to the work of Shi et al., 2023 is the following. Is it possible to generalize the work of Shi et al., 2023 to general $L_p$ norms and to $s$-rectangular case ? One of the key of their proof was to bound the range of the value function by $1/\sigma$ for large radius $\sigma\geq 1-\gamma$. Is it possible to adapt it to $L_p$ RMDPs and to $s$-rectangular assumptions. Moreover is there a chance to concentrate more complex dual for $L_p$ RMDPs compare to TV case in Shi et al., 2023 ?

From upper bound perspective:

• Adaptation and generalisation of key lemma from Shi et al., 2023 to reduce sample complexity in the $L_p$ context.
  Two new key lemmas 5 and 6 which are different from $TV$ case are derived, introducing $C_g$ coefficient which is not present in Shi et al., 2023.

• Concentration of more complex dual for $L_p$ RMDPs compare to TV case Concentration lemma (lemma 8) is very different from Shi et al. 2023 with additional term to control. Indeed as the dual form for $TV$ and $L_P$ , $p>1$ involve respectively a scalar optimization and a vector in the case of $L_p$, uniform concentration in lemma 8 is more challenging in the $L_p$ case with factor depending on the geometry of the norm called $C_s$.

• Adaptation and generalisation of the proof to $s$-rectangular case Contrary to Shi et al., 2023 , our proof tackles the problem of $s$-rectangular. We introduce quantities related to the stochasticity of the policy in the upper bound which is not present in Shi et al., 2023 to derive bound in the $s$-rectangular case.

• Finally from a lower bound perspective : new lower bound using counter example with stocastic optimal policy for $s$-rectangular case are derived and result from $sa$ rectangular is extended to $L_p$ norms.

2- What challenges are involved in establishing lower bounds that hold for any $L_p$ norm in the s-rectangularity case? and Establishing the lower bounds in the s-rectangularity setting for any L_p norm, not just the L_{linfty} norm, would strengthen the paper, enabling it to discuss minimax optimality also in that setting.

The lower bounds are for the case of $s$-rectangularity, which poses entirely new challenges compared to the case of $sa$-rectangularity: the optimal policies may be stochastic and difficult to characterise as closed forms, compared to the deterministic ones in $sa$ cases. When using different norms, the corresponding optimal policies might even not have closed forms, which is also the bottleneck to extend the $L_\infty$ case (Theorem 4) to more general $L_p$ arbitrary norms (as in Theorem 2).

Q3 Is there a fundamental limitation to extending the results to the entire range of the uncertainty level?

Indeed, we consider the full range of the uncertainty level in our theorems. In Theorem 1 and 3, the entire possible range of uncertainty level $\sigma$ is considered (see Theorem 1 and 3 where we defined $\sigma_{max}$ and $\tilde{\sigma}_{max}$ in the $sa$- and $s$-rectangular case.

Q4- On the motivation side, the authors write (page 2) that "in practice, numerous applications are based on optimizations or learning approaches that involve general norms beyond those that have already been studied". Could the authors provide relevant citations?

In the context of RMDPs the work of [1] proposed to use weighted norm to define a RDMPs. Moreover, in other application without the scope of RDMPS, general norm are used in robust optmization such as in [2,3].

give examples from other areas, such as supervised learning, adversarial learning.

[1] Reazul Hasan Russel, Bahram Behzadian, and Marek Petrik. "Optimizing norm-bounded weighted ambiguity sets for robust mdps" arXiv preprint arXiv:1912.02696, 2019

[2] Dimitris Bertsimas, Dessislava Pachamanova, Melvyn Sim "Robust linear optimization under general norms

[3] J Rony, L Gustavo, R Sabourin, E Granger : Decoupling direction and norm for efficient gradient-based l2 adversarial attacks

Q5 Regarding Theorem 4. For the $\mathcal{S}$-rectangular robust set case, the lower bound is only for the standard $L_{\infty}$-norm case. Could the authors elaborate more on the difficulty in proving a lower bound for the general $L_p$-norm case?

The lower bounds are for the case of $s$-rectangularity, which poses entirely new challenges compared to the case of $sa$-rectangularity: the optimal policies can be stochastic and difficult to characterize as closed forms, compared to the deterministic ones in $sa$ cases. When using different norms, the corresponding optimal policies might even not have closed forms, which is also the bottleneck to extend the $L_\infty$ case (Theorem 4) to more general $L_p$/arbitrary norms (as in Theorem 2).

Q6. Some typos and grammatical mistake that I found:

Many thanks for pointing out the typos. We have revised them and check throughout the entire paper again.

Aswer to revierwer Tr2g

We appreciate the reviewer's comprehensive feedback and recognition of the significance of our contributions.

Q1. One of the key message is that learning general $L_p$-norm robust MDPs is easier than learning standard MDPs. So I think it is less discussed how the exact choice of the generalized $L_p$-norm would further affect the difficulty of learning this type of robust MDPs.

Thank you for the clarification question. How different $L_p$ norm metric compared to TV affects the sample complexity or difficulty of learning RMDPs is present in two coefficients $C_g$ and $C_s$. For instance, in $sa$-rectangular cases, we recall that our sample complexity results is in the order of $O(\frac{ S A}{(1-\gamma)^2 \max \{ 1-\gamma, C_g \sigma\} \varepsilon^2} + \frac{ SA C_S \left\|1_S\right\| }{(1-\gamma)^2 \epsilon})$.

• The coefficient $C_g>0$ is related to the geometry of the norm. For classical non-weighted $L_p$ norms, this coefficient is bigger than $1$, leading to sample complexity smaller than in classical TV case. However, for arbitrary weighed norms, this coefficient can be smaller than 1, which imply a bigger sample complexity compared to TV cases.
• The coefficient $C_s>0$ represent how smooth is the gradient of the norm. This coefficient does not affect the sample complexity for small error $\epsilon \leq \left(\max \{1-\gamma, C_g \sigma\}\right) /\left(C_S\left\|1_S\right\|\right)$, with $\sigma$ the radius of the uncertainty ball, and $\left\| . \right\|$ the considered norm, as it is a second order term in terms of $\epsilon$ or burn in term. The smoother the gradient of the norm is, the smaller is $C_s$ which lead to smaller burn-in term.

Q2. Although theoretically sound, it is not well discussed when and why people need to consider modeling the inherent uncertainty of the MDP parameters using the generalized $L_p$-norm.

Thank you for the insightful suggestion. We consider general $L_p$ norm since its soundness in both theory and practice. [4] use TV for RL learning of Online 3D Bin or [6] for Offline policy optimization and [5] use $L_\infty$ for learning S-rectangular Robust MDPs. Moreover, the general $L_p$ problem formulation has unique interesting optimization properties, namely, relaxing slightly the problems will lead to a closed-form dual problems ([1,2] developed respectively Value Iteration and policy-based methods to solve RMDPs with $L_p$ norms).

[1] Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Levy, Shie Mannor "Policy Gradient for Rectangular Robust Markov Decision Processes"

[2] Navdeep Kumar, Kfir Levy, Kaixin Wang, Shie Mannor "Efficient Policy Iteration for Robust Markov Decision Processes via Regularization"

[4] Adjustable Robust Reinforcement Learning for Online 3D Bin Packing Yuxin Pan, Yize Chen, Fangzhen Lin

[5] B Behzadian, M Petrik, CP Ho Fast Algorithms for $L_\infty$-constrained S-rectangular Robust MDPs, Advances in Neural Information Processing Systems, 2021

[6] Lee, J., Jeon, W., Lee, B., Pineau, J., and Kim, K.-E. (2021). Optidice: Offline policy optimization via Stationary distribution correction estimation.

Q3 (Line 687-689) It is claimed that the dual form is derived for arbitrary norms, which seems like an overclaim since the proofs still depend on the assumptions in Definition 1 (e.g., Line 718). I think this is a misleading claim and needs revision.

Yes it is true, we will replace it, this is a typo.

Q4 It seems that the proof of duality in Section 8.3 resembles that in [1] without mentioning that work. Could the authors highlight a bit more the difference between the proofs here the and the proofs for duality in the previous work [1]?

There are many differences between our work and Clavier et al. [2023], such as our key lemma 5 and 6 to improve the sample complexity, the Variance decomposition (equation 64 of our work) which is central in our paper and differ from Clavier et al. [2023]. Please refer to the General Response for all technical contributions and new challenge addressed in our paper upon Clavier et al. [2023].

Q4. Regarding Theorems 3 and 4 for the $\mathcal{S}$-rectangular case. The upper bound in Theorem 3 (Equation (21)) involves a minimization over two terms (this is different from the $\mathcal{S} \times \mathcal{A}$-case where only the first term appears, which I think comes from a different upper bound on the span of the value function), but the lower bound in Theorem (Equation (23)) for a special case only involves the first term in the minimization in the upper bound, which seems like a contradiction. Could the authors explain more on that?

Thank you for the insightful question. In equation (20) of Theorem 3, using the result for the $L_\infty$ gives that the upper bound is exatly proportional to $\frac{SA}{\epsilon^2(1-\gamma)^2\max\{1-\gamma,\sigma \} }$. The other cases of the upper bound in equation (20) involve the quantity

$\min_{s \in \mathcal{S}} ( \lVert \pi_s^*\ \rVert_* \lVert 1_A \rVert , \lVert \hat{\pi_s} \rVert_* \lVert 1_A \rVert )=1$ in the case of $L_\infty$ RMDPs because.

$\min_{s \in \mathcal{S}} ( \lVert \pi_s^*\ \rVert_* \lVert 1_A \rVert , \lVert \hat{\pi_s} \rVert_* \lVert 1_A \rVert )=\min_{s \in \mathcal{S}} ( \lVert \pi_s^*\ \rVert_1 \lVert 1_A \rVert_\infty , \lVert \hat{\pi_s} \rVert_1 \lVert 1_A \rVert_\infty )=1$ So there is no contradiction with our lower bound which exactly match the upper bound.

Answer to reviewer 5t5a

We appreciate the reviewer's careful review and insightful feedback. It is rewarding to know that the reviewer recognizes the significance of our contributions. In what follows, we provide our response to the reviewer's comments.

Q1) The primary issue is that this paper closely aligns with Clavier et al. [2023]. To clarify the unique contributions, the authors should include more in-depth discussions comparing their work to Clavier et al. [2023]. For instance, the proof in Section 8.3 appears to follow Clavier et al. [2023] without proper citation.

There are many differences between our work and Clavier et al. [2023], e.g., our key lemma 5 and 6 to improve the sample complexity and the Variance decomposition (equation 64 of our work) which is central in our paper and differ from Clavier et al. [2023]. Please refer to the General Response for all technical contributions and new challenge addressed in our paper upon Clavier et al. [2023].

Section 8.3 of this work about optimization duality is similar to Clavier et al. [2023], while our proof is slightly more general as it works for weighted $L_p$ norms. We will refer to it in our last version of the proof of this manuscript. Moreover, the difference in optimization part is that we are not relaxing the dual of RMDPs problem like in Lemma C2 of Clavier et al. [2023].

Q2) A potential limitation of the paper is its focus on the tabular setting. It would be valuable to explore whether these insights can be applied to the function approximation setting as well. Nevertheless, this does not diminish the importance of the contributions presented in this work.

Thanks for proposing this interesting direction, investigating robust RL with linear function approximation or other settings such as online settings, or model-free algorithms are definitely interesting directions in the future work. Robust RL with linear function has inspired some recent works such as [1,2,3]. We believe the findings of current results in tabular cases about norms lays a solid foundation to carry out to cases with linear function approximation, e.g., the finding of using any $L_p$ norm may lead to less sample size requirement. While the entire pipeline in this work will need to adapt or change a lot since this setting involves additional challenges from problem definition (how to define a reasonable uncertainty set is still relatively open) towards algorithm design.

[1] Blanchet, J., Lu, M., Zhang, T., and Zhong, H. (2024). Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36.

[2] H Wang, L Shi, Y Chi Sample complexity of offline distributionally robust linear markov decision processes arXiv preprint arXiv:2403.12946, 2024

[3] Liu, Z. and Xu, P. (2024a). Distributionally robust off-dynamics reinforcement learning: Provable efficiency with linear function approximation. arXiv preprint arXiv:2402.15399.

Answer to Reviewer 6HyR

We appreciate the reviewer for recognizing our contributions, and for providing constructive suggestions. Here some comments on the different questions raised :

Q1: NSA been not use in Eq. 17, 18,19,20,21. Although the intention of the authors is clear, but that would improved readability.

Thanks for the suggestions. We add a new notation $N_{\mathsf{all}} = NSA$ to represent the total number of samples and use $N_{\mathsf{all}}$ in Eq. 17, 18,19,20,21 or other equations to make it clearer for the readers.

Q2: In Table 1, the bounds are used in order sense, it would improve readability to have written in $\mathcal{O}(.)$, especially since the lower and upper bounds are of same order.

Thank you for the clarification question. Throughout the paper (including Table 1), we use the same metric to measure the sample complexity --- the order that defined as:

• "Let $\mathcal{X} := \big( S, A, \frac{1}{1-\gamma}, \sigma, \frac{1}{\varepsilon}, \frac{1}{\delta} \big)$. The notation $f(\mathcal{X}) = O(g(\mathcal{X}))$ or $f(\mathcal{X}) \lesssim g(\mathcal{X})$ indicates that there exists a universal constant $C_1>0$ such that $f\leq C_1 g$, the notation $f(\mathcal{X}) \gtrsim g(\mathcal{X})$ indicates that $g(\mathcal{X})=O(f(\mathcal{X}))$, and the notation $f(\mathcal{X})\asymp g(\mathcal{X})$ indicates that $f(\mathcal{X}) \lesssim g(\mathcal{X})$ and $f(\mathcal{X}) \gtrsim g(\mathcal{X})$ hold simultaneously. Additionally, the notation $\widetilde{O}(\cdot)$ is defined in the same way as ${O}(\cdot)$ except that it hides logarithmic factors."

We added the footnote inside Table 1 to introduce the definition of order as above and clarify that we omit $\widetilde{O}(\cdot)$ in the caption, as the reviewer suggested.

Q3: It would great improve the draft with some empirical evaluation to back the theoretical bounds, even a toy example.

Thank you for the constructive suggestion. We will conduct an experiment with simple RMDPs defined with $L_p$ balls on a toy example to show the dependency in the radius of the ball $\sigma$ on the sample complexity.

Q4: Does our sample complexity improvement significant improve prior art?

For RL problems, especially in theory, the sample complexity dependency on the salient parameter $\frac{1}{1-\gamma}$ is one of the significant terms that dominate the sample efficiency. A line of work has committed to the endeavor of gradually improve this dependency towards optimal in various RL problems including but not limited to standard RL [1,2], and robust RL [3,4,5] that this work focus on.

In $sa$-rectangular cases. We focus on improving the sample complexity when $\sigma >1-\gamma$, where the prior art is still far from optimal. In $sa$-rectangular cases, we improve upon the prior art [5] sample complexity $\widetilde{O}(\frac{S A}{(1-\gamma)^4 \varepsilon^2}$) to $\widetilde{O}(\frac{S A}{(1-\gamma)^2 \sigma \varepsilon^2})$ by at least a factor of $\frac{1}{1-\gamma}$ and goes to $\frac{1}{(1-\gamma)^2}$ when $\sigma \geq O(1)$. Notably, this results is minimax-optimal in all salients parameters that match our lower bound for general $L_p$ norms, as long as the accuracy level $\epsilon$ is in a reasonable range. This is a significant improvement and near-optimal result. The same improvement is done for the $s$-rectangular case, by at least a factor of $1/(1-\gamma)$ compared to [5].

[1] Azar, Mohammad and Munos, Rémi and Kappen Hilbert , Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model

[2] Gheshlaghi Azar, R Munos, HJ Kappen - Minimax PAC bounds on the sample complexity of reinforcement learning with a generative model

[3] Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Toward theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics

[4] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, Yuejie Chi The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model

[5] Pierre Clavier, Erwan Le Pennec, Matthieu Geist Towards minimax optimality of model-based robust reinforcement learning