Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning

We greatly appreciate the reviewer’s time and effort in evaluating our work. We hope that the following response can address some of your concerns:

Question 1 (a): Dependence on the various parameters

Regarding the dependence on $p_\wedge$, several prior works [1, 2, 3]-show that even for DMDP under the KL-divergence, the sample complexity lower bound necessarily depends on $1/p_\wedge$. Therefore, we believe this dependence may be inherent and possibly unavoidable for the KL setting. Moreover, [4] has also shown that in the $f_k$ divergence setting, the statistical risk of DR functional estimation converges like $n^{(1-k)/k}$ when $k > 1$ is close to 1, without the minimum support probability assumption, suggesting the impossibility of obtaining a parametric rate without this $p_\wedge$ constraint. In fact, a careful observation would reveal an estimation error convergence rate for k = 1 in the setting of [4] behaving like $\widetilde \Theta(1/(p_\wedge n^{1/2}))$. This suggests that the $1/p_\wedge$ could be necessary in a lower bound. However, due to the highly intertwined relationship between the minorization time $t_{\mathrm{minorize}}$ and $p_\wedge$ in our setting, it is unclear what a lower bound would look like.

Question 1 (b): Lower bounds

We mention that robustness presents additional statistical challenges to optimal policy learning. For instance, in the standard MDP setting, the minimax sample complexity of policy learning in AMDP setting is $t_{\mathrm{mix}}/\epsilon^2$, which can be obtained by a reduction method from AMDP setting where the sample complexity scales like $t_{\mathrm{mix}}(1-\gamma)^{-2}\epsilon^{-2}$. However, as noted in prior work (e.g. [2], which studies the chi-square case as a special instance of our framework), the sample complexity lower bound for DR-RL under this setting includes a factor of $(1-\gamma)^{-4}\epsilon^{-2}$. Viewing $(1-\gamma)\epsilon$ as the relative error, the extra powers $(1-\gamma)^{-2}$ could be suggesting a $t_{\mathrm{mix}}^2$ dependence in the worst case, potentially matching our upper bound in this regard, reflecting a non-trivial deviation of the robust MDP setting from the non-robust counterpart.

Question 2 (a): Technical challenges

In summary, our work makes a novel contribution by providing the first non-asymptotic, prior knowledge free algorithms for DR-AMDP under weak assumptions and provable sample complexity guarantees, while addressing technical obstacles that prior works have not resolved.

1. Weaker Assumption: We only make the ergodicity assumption on the nominal transition kernel $P$, and demonstrate the first sample complexity bounds for DR-AMDP. In contrast, previous work under DR setting relies on the assumptions that the mixing time is uniformly bounded over the uncertainty set $\mathcal P$. However, in reality, this assumption is unrealistic and too strong because it is very difficult for the system to discriminate the properties of all kernels in an uncertainty set. Whereas our DR work does not rely on this stringent assumption, we simply assume the ergodicity of the nominal transition kernel $P$; which has never been considered in previous work.
2. Non-trivial Extension to DR setting with optimal rate: Recent studies [5] have attempted to employ the reduction to DMDP method to the DR-AMDP context. However, this reduction framework only obtains a suboptimal sample complexity bound $\widetilde O(\varepsilon^{-4})$. The fact that prior efforts were unable to achieve the optimal quadratic rate $\widetilde O(\varepsilon^{-2})$ Using these methods highlights the substantial technical barriers involved. This demonstrates that even extending existing techniques to the DR setting is itself a non-trivial and challenging task. The optimal rate achieved in the non-DR setting critically relies on the fact that the error term $(1-\gamma)V_P^\pi - g_P^\pi$ converges to zero at a rate proportional to $O((1-\gamma)t_{\mathrm{minorize}})$ as $\gamma \to 1$. This enables the reduction and anchoring to be feasible. However, the same theoretical vehicles implemented in the non-DR MDP setting cannot directly lead to a similar sample complexity reduction in the DR setting, due to the presence of the uncertainty set. In DR-RL, the adversary has the capacity to perturb the transition kernel, inducing a sharp increase in mixing time. This effect can be seen in the provided hard MDP instance [2], minorization time tends to infinity when the minimal support $p_\wedge$ tends to $0$ by perturbation, which prevents the reduction to DMDP in the non-DR setting from having a finite sample guarantee. In order to achieve the presented sample complexity result in our work, a substantial effort is required to connect the radius of the uncertainty set, the minorization time, the discount factor, and the minimum support probability. These considerations lead to an optimal $\widetilde O(1/(1-\gamma)^2)$ scaling, matching the optimal dependence on $1/(1-\gamma)$ in the sample complexity lower bound for classical MDPs.
3. The first prior knowledge-free DR algorithms: Prior work on reductions to DMDP and anchored AMDP often relies on prior knowledge of certain problem-specific parameters to achieve optimal sample complexity in the non-DR setting. For example, Wang [6] requires setting the discount factor $\gamma=1-\Theta (\varepsilon/t_{\mathrm{minorize}})$ that depends on the minorization time parameter. Such information-sensitive algorithms are impractical in real-world scenarios. In contrast, our approach does not rely on such information, further demonstrating the generality and feasibility of our results. Specifically, we provide a novel theoretical analysis, allowing us to use the DMDP and Anchored AMDP with a much more flexible choice of $\gamma$ and $\eta$ without prior knowledge.

Question 2 (b): Weakly communicating

We appreciate your suggestion to include more discussion of sharper parameters, such as bias span, which is used in a weakly communicating setting of classical MDPs. Actually, our theory can be directly applied to the setting of weakly communicating robust MDPs under the bias span parameter, provided that the average robust Bellman equation has a constant gain solution. However, the existence of a solution is, in general, invalid, a fact that is known in the stochastic game literature under a multichain setup (note that, in contrast, multichain MDPs always have a solution to the non-robust multichain Bellman equation). It is currently unclear if we can show the existence of a solution to the constant gain robust Bellman equation under a weakly communicating assumption. Hence, we decide not to state our results using bias span, which arises naturally in the weakly communicating setting, for which we do not know if the Bellman equation has a solution.

Supplementary: Experiment for the dependence of minorization time

Minimum support probability and minorization time are entangled. Since for hard MDP instances, $t_{\mathrm{minorize}} = 1/(2p_\wedge)$. For this reason, we cannot disentangle the dependence of $t_{\mathrm{minorize}}$ and $p_\wedge$ in hard MDP settings. We present the results for the different $t_{\mathrm{minorize}}$ below. Note that it is hard for us to disentangle the minorization time and the minimum support $p_\wedge$; we cannot clearly show the dependence of the minimization time solely. Nonetheless, we have experimented with different minorization times for reference

Thank you for your insightful comments.

[1] Shi, L., et al. The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model.

[2] Shi, L., & Chi, Y. (2024). Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity.

[3] Wang, S., Si, N., Blanchet, J., & Zhou, Z. (2024). Sample complexity of variance-reduced distributionally robust Q-learning.

[4] Duchi, J. C., & Namkoong, H. (2021). Learning models with uniform performance via distributionally robust optimization.

[5] Roch, Zachary, et al. "A finite-sample analysis of distributionally robust average-reward reinforcement learning."

[6] Wang, S., Blanchet, J., & Glynn, P. (2023). Optimal sample complexity for average reward markov decision processes.

I appreciate the responses 1a and 1b, and believe they may strengthen the paper. I am not completely convinced by the responses 2a and 2b:

2a: The authors cite the (non-peer-reviewed) paper [5] to justify their claim that there are substantial technical obstacles involved in using the discounted reduction approach. However, the paper [5] does not make use of recent developments in the analysis of discounted reductions for (non-robust) average-reward problems (ex. [38, 58] in the numbering of the main paper). Hence this is not sufficient justification. Also, the authors highlight that they develop algorithms for the robust setting which are prior-knowledge free, but as mentioned in their paper this problem of prior knowledge has already been solved in the non-robust setting (see line 95). Therefore it is not clear whether there are any significant new difficulties in the robust setting specifically related to removing prior knowledge. Overall, I still wonder about the difficulty in deriving the results of the present paper for researchers who are well-versed in prior work. As stated in my review, I do not necessarily view this as a fatal issue, but the authors should make clear whether the key techniques behind their results come primarily from prior developments or are new.

2b: Is this issue still present when using the minimum support lower bound assumption?

Thank you for the questions and engaging the discussion!

2a Response

While our previous explanation may have caused some misunderstanding, we wish to clarify that the DR (distributionally robust) setting is technically distinct from the non-DR case. There are challenges unique to the DR framework that must be addressed before techniques such as Reduction to DMDP and Anchored methods can be effectively applied.

We highlight the differences between the non-DR and DR settings through a proof sketch

First, we need to ensure that all transition kernels within the uncertainty set are mixing, given that only the nominal transition kernel is mixing. We note that if there are kernels within the uncertainty set that induce multichain or even weakly communicating MDPs, the existing literature does not provide a positive answer regarding the existence of a solution to the robust Bellman equation and a stationary optimal policy. In contrast, the Bellman equation always has solutions in the non-DR setting. We will elaborate on this matter in our response 2b.

Our Proposition 4.2 directly addresses this concern:

$\sup_{Q, \pi}t_\mathrm{minorize}(Q_\pi)\leq 2t_\mathrm{minorize}$, when $\delta$ satisfies Assumption 2

In Propositions B.2 and E.2 (which restate Proposition 4.2 under KL and $f_k$ divergences, respectively), we show that, under our assumption on $\delta$, any transition kernel $Q \in \mathcal{P}$ has its conditional distribution $q_{s,a}$ (given an $(s,a)$-pair) absolutely continuous with respect to the nominal distribution $p_{s,a}$, with a minimal support of $1-\frac{1}{2m_\vee}$. This ensures that any such $Q$ satisfies the $(m, \frac{p}{2})$-Doeblin condition and is thus uniformly ergodic; that is, $t_\mathrm{minorize}(Q_\pi)$ is uniformly bounded across all $Q \in \mathcal{P}$ and all policies.

Second, to tackle the nonlinearity introduced by the DR operation in Lemma C.6,

Lemma C.6: $|\sup_{\alpha\geq 0}f(\hat p_{s,a}, V, \alpha) - \sup_{\alpha\geq 0}f(p_{s,a}, V, \alpha)| = O(\mathrm{Span}(V)||\frac{\hat p - p}{p}||_{L^\infty(p)} )$ w.p.1.

Here, we use duality, the mean value theorem, and Lemma C.4

Lemma C.4: $\sup_{\alpha \geq 0}\alpha\frac{(\hat p - p)[e^{-V/\alpha}]}{p[e^{-V/\alpha}]} = O(\mathrm{Span}(V)||\frac{\hat p - p}{p}||_ {L^\infty(p)})$ w.p.1.

to show that the difference between the empirical and nominal transition kernels under KL-divergence can be bounded by $\mathrm{Span}(V)$ and the relative empirical measure estimation error $\sup_{s,a}||\frac{\hat p_{s,a} - p_{s,a}}{p_{s,a}}||_ {L^\infty(p_{s,a})}$. This bound will reduce to a simple application of Hoeffding's inequality and union bound in the non-DR setting.

Next, to connect these statistical analyses of DR Bellman operator to the sample complexity, we show in Theorem D.1 and Lemma C.3 that:

W.p.1. $V_{\mathcal P}^* - V_{\mathcal P}^{\hat\pi^*} \leq 2\max_{\pi\in \Pi} ||V_{\widehat {\mathcal P}}^\pi - V_{\mathcal P}^\pi|| \leq 2\sup_{\pi, Q}\frac{1}{1-\gamma}|| \widehat{\mathcal T}_ \gamma^\pi (V_Q^\pi) - \mathcal T_ \gamma^\pi(V_Q^\pi)||$

where $Q\in\mathcal{P}$ and $\pi\in\Pi$. This is an important step that reduces the analysis of policy error to the estimation error of DR Bellman operator evaluated at $V_Q^{\pi}$.

Using equation C.27 and Lemma C.6 $||\widehat{\mathcal T}_ \gamma^\pi (V_Q^\pi) - \mathcal T_\gamma^\pi (V_Q^\pi)||$ can be bounded by $O(\mathrm{Span}(V_Q^\pi)||\frac{\hat p - p}{p}||_ {L^\infty(p)})$. Then, leveraging Proposition 4.2 (each $Q\in\mathcal{P}$ is uniformly ergodic) and the that $||\frac{\hat p - p}{p}||_ {L^\infty(p)} = \widetilde O(n^{-1/2})$, we obtain

Lemma C.7: $||\widehat{\mathcal T}_ \gamma^\pi (V_Q^\pi) - \mathcal T_ \gamma^\pi (V_Q^\pi)|| = \widetilde O(t_\mathrm{minorize}(Q_\pi)/\sqrt{n})$ with high probability.

So, the estimation error is bounded in $1/(1-\gamma)$. This leads to the conclusions in Theorems 4.4 and 4.5.

For the $f_k$-divergence case, the overall proof structure is similar, but requires different techniques. In Lemma F.7, we show that the statistical error of estimating the robust Bellman operator can also be controlled by $t_\mathrm{minorize}$, while Lemma F.6 employs the envelope theorem to achieve a refined analysis that works for all $k > 1$. This is a challenging task: according to our best knowledge, no prior literature achieves an analysis that works for all $k>1$. In particular, it is known that for $k$ close to 1, the minimax statistical behavior of estimating the DR functional under $f_k$-divergence can diverge. This issue is addressed by a careful analysis with the introduction of the minimum support probability.

We thank the reviewer for this constructive feedback. We hope the following response can address some of your concerns:

Weakness 1: Baseline comparisons

Our experiments primarily validate the theoretical $O(n^{-1/2})$ statistical error rate of our algorithm, empirically demonstrating the first provable parametric non-asymptotic convergence in DR-AMDP. In response, we also include new comparisons with DR RVI Q-learning [5], further strengthening the empirical evaluation and demonstrating the efficiency of our approach.

The error in Alg 1 & Alg 2 is the maximum over both algorithms.

Since DRVI-LCB is an offline RL method, it does not apply to our setting.

Weakness 2: Clarify novelty; methods similar to prior works.

In summary, our work makes a novel contribution by providing the first non-asymptotic, prior knowledge-free algorithms for DR-AMDP under weak assumptions and provable sample complexity guarantees, while addressing technical obstacles that prior works have not resolved.

1. Weaker Assumption: We only assume ergodicity for the nominal transition kernel $P$, and provide the first sample complexity bound for DR-AMDP. In contrast, previous DR work requires the mixing time to be uniformly bounded over the uncertainty set, which is unrealistic and too strong in reality. Our approach avoids this stringent assumption by assuming only the ergodicity of $P$, which has never been addressed in previous work.
2. Non-trivial Extension to DR setting with optimal rate: Recent work [3] attempted to reduce DR-AMDP to DMDP, but only achieved a suboptimal sample complexity of $\widetilde O(\varepsilon^{-4})$, highlighting significant technical barriers to reaching the optimal $\widetilde O(\varepsilon^{-2})$ rate. In standard MDPs, optimal rates rely on fast convergence of the error term $\\|(1-\gamma)V_P^\pi - g_P^\pi\\| \\leq O((1-\gamma)t_{\mathrm{mix}})$ as $\gamma\to 1$, but this approach does not extend to the DR setting due to the added complexity of the uncertainty set. In DR-RL, adversarial perturbations can sharply increase mixing times, making finite-sample guarantees impossible. Achieving our sample complexity results thus requires new analysis to relate the uncertainty set, minorization time, discount factor, and minimum support. Our work overcomes these challenges and achieves the optimal $\widetilde O(1/(1-\gamma)^2)$ scaling, matching the best-known dependence for classical MDPs first, and then extends the reduction framework to DR-AMDP.
3. The first prior knowledge-free DR algorithms: Prior work on reductions to DMDP and anchored AMDP often relies on knowledge of problem-specific parameters (e.g., [2] needs $\gamma$ set based on $t_{\mathrm{minorize}}$) to achieve optimal sample complexity in the non-DR setting. Such information-sensitive algorithms are impractical in real-world. Our approach removes this requirement, allowing flexible choices of $\gamma$ and $\eta$ without prior knowledge, and offers a more general and practical solution with new theoretical analysis.

Our contribution is mainly on the algorithmic design and theoretical guarantee for the DR-AMDP, which differs from Robust Q-Iteration [1]: designed for DR-DMDP and Plug-in Approach [2]: not robust and doesn't address DR setting, robust extension faces many technical difficulties and complications. Therefore, the results in [1,2] are not applicable to our setting; we need to devise many theoretical innovations to achieve our efficient prior-knowledge free algorithms and analyses.

Weakness 3: Simulator and offline RL

This is a great point. We focus on the generative model since it is important in its own right and plays a central role in many landmark achievements of RL (e.g., AlphaGo’s use of simulation-based planning). Moreover, the generative model serves as a crucial foundation for both sequential offline and online DR-RL tasks. Since there are no prior non-asymptotic sample complexity results for DR-AMDP, establishing results in the generative model is a necessary foundation for future, more applied studies. Our work aims to serve as a cornerstone for the field and to facilitate subsequent advances in both offline and online DR-RL.

We agree that this offline RL setup would significantly broaden the scope and practical impact of our work. In the revised manuscript, we will explicitly discuss future work on offline settings.

Weakness 4: Experiment

Thank you for the question. We chose a simple MDP with 2 states and 2 actions mainly for theoretical reasons:

1. Theoretical Focus: As this is a theory-oriented paper, our primary goal is to empirically validate the theoretical relationship between sample size and accuracy. So simple and controlled MDPs enable clear comparison with theory.
2. Choice “Hard” MDPs: As shown in [4], this "Hard" MDP achieves the maximal lower bound $\widetilde\Omega(t_{\mathrm{minorize}}/\varepsilon^2)$ for the non-DR AMDP, making it highly representative for validating theoretical properties. For theory-focused investigations, we prioritized such “hardest” instances in our empirical analysis. This further justifies our experimental setup.
3. Algorithmic Challenge: Solving Algorithms 2 and 3 using value iteration in these hard MDPs represents one of the most challenging scenarios in RL, as the agent cannot trivially distinguish the optimal action, further confirming the robustness of our experimental validation.

Additionally, we have conducted further experiments on Large MDP (20 states, 30 actions) as in [5] to support our theoretical result

In large instances, the results are consistent with our theoretical guarantee, with the fitted slope in log-scale being close to $-1/2$.

Question 1: Knowledge on uncertainty set radius

We would like to clarify that $\delta$ is not a system characteristic parameter, but rather a decision parameter specified by the user to represent how robust the user wants the learned policy to be. This parameter governs the tradeoff between the policy's resilience to environmental distributional shifts and its optimality under the nominal kernel $P$. Importantly, our theoretical guarantee holds for any user-specified $\delta$ within the range specified in assumption 2, which is the regime most relevant for practical applications of DR-AMDP.

Question 2: Differences: discounted vs. discounted mixing

The main difference between DR-RL under the discounted and discounted mixing settings lies in the additional mixing time assumption. In the general discounted setting, no assumptions are made about the mixing properties of the MDP, the mixing time may be unbounded under any policy.

In contrast, discounted mixing MDP assumes an explicit mixing or stability property; e.g. the mixing time of the Markov chain induced by any policy is bounded. This additional assumption results in a sharper and more refined complexity bound.

Specifically, in [6], under the mixing time assumption $t_{\mathrm{mix}} \leq (1-\gamma)^{-1}$, the sample complexity upper bound for standard MDP can be improved to $\widetilde O(t_\mathrm{mix}(1-\gamma)^{-2} \epsilon^{-2})$, which is less conservative than the worst case bound of $\widetilde O((1-\gamma)^{-3} \epsilon^{-2} )$ for discounted MDP.

Question 3: Update rule for $g^*$

No, the $g^*$ is obtained by solving for the unique solution of the robust Bellman equation. There are many ways to solve (or approximately solve) these equations, including robust relative value iteration (RVI), robust policy iteration (RPI), or approximate dynamic programming (ADP) methods.

Question 4: Proof sketch and Novelty

This is a great suggestion. Our proof relies on two key insights:

1. Bounded Minorization Times: Under the assumption of bounded uncertainty size, the minorization time on the full set of uncertainties can be effectively controlled.
2. Improved Bellman Operator Error Bound: The Bellman operator error between the empirical and nominal transition kernel can be improved from the usual $1/(1-\gamma)$ dependence to a dependence on $t_{\mathrm{minorize}}$

These two ingredients are central to our analysis and distinguish our work from prior results. We will add a proof sketch and explicitly highlight the novelty of our analysis in the reviewed manuscript to improve its readability and clarity.

Limitation

Indeed, assuming uniform ergodicity on the nominal kernel $P$ could be a strong assumption in practice. However, previous work on DR-AMDP makes an even stronger assumption: all kernels in the uncertainty set are uniformly ergodic. Our work is the first to show that a parametric convergence rate is achievable under a weaker assumption that only the nominal kernel $P$ is uniformly ergodic.

[3] Roch, Zachary, et al. A finite-sample analysis of distributionally robust average-reward reinforcement learning.

[4] Wang, Shengbo, et al. Optimal sample complexity for average reward Markov decision processes.

[5] Wang, Yue, et al. Model-free robust average-reward reinforcement learning.

[6] Wang, Shengbo., et al. Optimal sample complexity of reinforcement learning for mixing discounted Markov decision processes.

Dear Reviewer huvR,

Thank you for reviewing our manuscript and providing feedback.

As the discussion phase ends soon (by 8.6), we hope our responses have addressed your concerns. Please let us know if you need further clarification.

Best regards,

The Authors

We thank the reviewer for the insightful comments. We hope that the following response will help to address some of the concerns.

Weakness: Limited technical novelty in robust domain extension & Question 1: Obstacles in adapting techniques to robust average-reward RL

We think your concern regarding the technical novelty of our methods (“Both core ideas, the reduction to DMDPs and the anchoring technique, are adapted from earlier work...”) and the question about the obstacles encountered when adapting these techniques to the distributionally robust (DR) average-reward RL setting are closely related. Therefore, we provide a reorganized response on the novelty and challenges as follows:

1. Weaker Assumption: We only make the ergodicity assumption on the nominal transition kernel $P$, and demonstrate the first sample complexity bounds for DR-AMDP. In contrast, previous work under the DR setting relies on the assumptions that the mixing time is uniformly bounded over the uncertainty set $\mathcal P$, or assumes an upper bound on the span seminorm of the optimal bias value function. However, this assumption is unrealistic in application and unsatisfactory from a theoretical point of view. In practice, it is difficult to require properties of all kernels within the uncertainty set, while in theory, there is no obvious way to check these properties. Our DR work does not rely on this type of uniform assumption; we simply assume the ergodicity of the nominal transition kernel $P$, which has never been studied or successfully analyzed in previous work.
2. Non-trivial Extension to DR setting: Although both ideas exist under non-DR, their extension to the DR context is far from straightforward. Recent studies [1] have attempted to employ the reduction to DMDP method to the DR-AMDP context. However, this reduction framework only obtains a suboptimal sample complexity bound $\widetilde O(\varepsilon^{-4})$. The fact that prior efforts were unable to achieve the optimal quadratic rate $\widetilde O(\varepsilon^{-2})$ highlights the technical barriers involved. The optimal rate achieved in non-DR setting critically relies on the fact that the error term $(1-\gamma)V_P^\pi - g_P^\pi$ converges to zero at a rate proportional to $O((1-\gamma)t_{\mathrm{minorize}})$ as $\gamma \to 1$. This enables the reduction and anchoring methods. However, the same theoretical vehicles implemented in the standard non-DR MDP setting cannot directly lead to a similar sample complexity reduction in the DR setting, due to the presence of the uncertainty set. In DR-RL, the adversary has the capacity to perturb the transition kernel, inducing a sharp increase in mixing time. This effect can be seen in the provided hard MDP instance [2], minorization time tends to infinity when the minimal support probability $p_\wedge$ tends to $0$ by perturbation, preventing the reduction to the DMDP framework in the non-DR setting from having a similar sample guarantee. In order to achieve the presented sample complexity result in our work, a substantial effort is required to connect the radius of the uncertainty set, the minorization time, the discount factor, and the minimum support probability. These considerations lead to an optimal $\widetilde O(1/(1-\gamma)^2)$ scaling, matching the optimal dependence on $1/(1-\gamma)$ in the sample complexity lower bound for classical MDPs.
3. The first priori knowledge free DR algorithms: Prior work on reductions to DMDP and anchored AMDP often relies on priori knowledge of certain problem-specific parameters to achieve optimal sample complexity in the non-DR setting. For example, Wang [2] requires setting the discount factor $\gamma=1-\Theta (\varepsilon/t_{\mathrm{minorize}})$ that depends on the minorization time parameter. Such information-sensitive algorithms are impractical in real-world scenarios. In contrast, our approach does not rely on such information, further demonstrating the generality and feasibility of our results. Specifically, we provide a novel theoretical analysis, allowing us to use the DMDP and Anchored AMDP with a much more flexible choice of $\gamma$ and $\eta$ without prior knowledge.

Question 2: Lower bound for DR average-reward RL

The landscape of lower bounds in DR-RL setting is not yet fully understood, even for the discounted case. We think the average-reward setting could entail more intricate issues, such as the dependence of the mixing parameter, the radius of the uncertainty set, and the minimum support probability. This makes it challenging to establish tight or fine-grained lower bounds. Currently, the only known uniform lower bound for DR average-reward RL is the lower bound for non-DR $(\delta=0)$ average-reward RL: $\widetilde O(t_{\mathrm{mix}}/\varepsilon^{2})$. However, it is currently unclear if this is tight for all regimes, and we have some reasons to believe otherwise. Specifically, [3] established a lower for the statistical risks of $\widetilde \Omega(1/(1-\gamma)^{4}\varepsilon^{2})$ for DR-DMDPs with $\delta = O(1)$ under $\chi^2$-divergence uncertainty sets (which corresponds to the case $k=2$ in our $f_k$-divergence setting). In particular, this bound represents a deviation from the standard $\widetilde\Omega(1/(1-\gamma)^3\varepsilon^2)$ lower bound for non-robust MDPs. Therefore, using a reduction argument that views $\varepsilon(1-\gamma)$ as the relative error, from this result in [3], we anticipate a $\Omega(t_{\mathrm{minorize}}^2/{\varepsilon^{2}})$ dependence for the DR average-reward case. However, proving sharp lower bounds that encapsulate this intuition remains an open and intriguing direction for future research.

[1] Roch, Zachary, et al. "A finite-sample analysis of distributionally robust average-reward reinforcement learning."

[2] Wang, S., Blanchet, J., & Glynn, P. (2023). Optimal sample complexity for average reward markov decision processes.

[3] Shi, L., Li, G., Wei, Y., Chen, Y., Geist, M., & Chi, Y. (2023). The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model.

We sincerely thank the reviewer for the thoughtful and constructive feedback, as well as for recognizing the contributions of our work. Here we address the specific weaknesses and questions raised:

Weakness 1: Technical difficulty of extending non-DR result to DR-RL setting.

We would like to explicitly clarify several crucial points that distinguish our results from Wang [38], particularly regarding the challenges of extending their approach to the DR-RL setting:

1. Non-trivial Extension to DR-RL: While Wang [38] employs a reduction to DMDP for their analysis, this technique does not straightforwardly extend to the DR-RL setting. The primary reason is that their reduction critically relies on the fact that the error term $(1-\gamma)V_P^\pi - g_P^\pi$ converges to zero at a rate proportional to $O((1-\gamma)t_{\mathrm{minorize}})$ as $\gamma \to 1$. In the non-DR setting, this enables a sample complexity of order $t_{\mathrm{minorize}}/(1-\gamma)^2$, making the reduction feasible. However, the same theoretical techniques used by Wang [38] in the standard non-DR MDP setting cannot directly yield a similar sample complexity reduction in the robust setting, due to the presence of the uncertainty set. In DR-RL, the adversary has the capacity to perturb the transition kernel, inducing a sharp increase in mixing time. This effect can be seen in the provided hard MDP instance [38], minorization time tends to infinity when the minimal support $p_\wedge$ tends to $0$ by perturbation. In order to achieve the presented sample complexity result in this work, a substantial effort is required to connect the radius of the uncertainty set, the minorization time, the discount factor, and the minimum support probability. These considerations leads to not only a correct $\widetilde O(1/(1-\gamma)^2)$ scaling, but also matching the optimal dependence on $1/(1-\gamma)$ in the sample complexity lower bound for classical MDPs, but also an algorithm that need neither prior knowledge of $t_{\mathrm{minorize}}$ or $t_{\mathrm{mix}}$, nor the condition that all the kernels in the uncertainty set induces mixing. We will elaborate next.

2. Priori Knowledge Free: In [38], the work leverages a restrictive parameter selection $\gamma = 1-\Theta(\varepsilon/ t_{\mathrm{minorize}})$, which requires prior knowledge of minorization time even in the non-DR setting. In contrast, our approach does not rely on such information, leading to a feasible algorithm that can run without such knowledge. This is achieved by a novel theoretical analysis that generalizes the previous approach, allowing us to use the discounted MDP with a much more flexible choice of $\gamma$ (or $\eta$ in the anchored setting). In particular, this allows us to choose $\gamma = 1-\Theta(1/\sqrt{n})$ and $\eta=1/\sqrt{n}$, without prior knowledge, to achieve the claimed rates for DR-AMDP.

Weakness 2: Table 1 results interpretation is incomplete.

We thank the reviewer's feedback of our results as presented in Table 1. In the next revision, we will explicitly enhance the discussion of Table 1, both in the introduction and in a dedicated section, With respect to Table 1, our results represent a significant improvement over previous works in terms of both weaker assumptions that we only makes the ergodicity assumption on the nominal transition kernel $P$, and demonstrates the first sample complexity bounds for DR-AMDP. We will make these points more explicit in the revised manuscript and ensure that readers can readily interpret the advantages of our approach.

Weakness 3: Algorithm 2 vs. Algorithm 3: advantages, differences, scalability.

We thank the reviewers for their questions and suggestions for improving our experimentation. The primary motivation for including both algorithms is to systematically investigate whether well-established approaches from the non-DR setting—namely, reduction to DMDP and Anchored AMDP—can be effectively extended to the distributionally robust context. Both algorithms are widely recognized for their simplicity and sample efficiency under the non-DR setting, and it is valuable to understand their respective strengths and limitations when adapted to DR-RL.

The differences and potential advantages between two algorithms are:

1. Algorithm 2 (Reduction to DMDP) leverages the connection between average-reward and discounted-reward problems, which can simplify analysis and benefit from existing results in the discounted setting. It can be implemented flexibly using a variety of established techniques, such as Q-learning and value iteration.
2. Algorithm 3 (Anchored AMDP), on the other hand, leverages span contraction, which enables fast convergence under the span seminorm. It directly tackles the average-reward problem and may exhibit better empirical performance or stability, especially in environments where the reduction may introduce additional approximation errors. We will expand the discussion in the revised version to clearly articulate these differences, including their theoretical guarantees and practical trade-offs.

On large-scale experimental setups

To empirically compare the two algorithms under large-scale settings, we conducted example used in [1], which involves 20 states and 30 actions. Our results provide practical insight into their scalability and performance differences in more complex environments. We will include a detailed discussion of these experimental findings in the revised manuscript to further clarify the relative advantages of each algorithm. Actually, even in the large–scale experiments with large state-action space, the slope of the linear regression of our results on the logarithmic scale is very close to -1/2, further validating our theoretical guarantee:

Question 1: Definition of $(s,a)$ rectangular sets

The definition of $(s,a)$-rectangular sets is provided in line 194 of the paper. We will add a clear forward reference in line 114 to enhance the clarity and ensure readers can easily locate the definition.

Question 2: Typo “constant”

Thank you for catching this typo. We have corrected the issue in the revised manuscript.

Question 3: Definition 3.3

We have revised this definition as follows to improve mathematical rigor.

Definition 3.3: And MDP (or its controlled transition kernel $P$ ) is said to be uniformly ergodic if for all policies $\pi \in \Pi$, $t_{\mathrm{minorize}}(P_\pi) < \infty$, denote $t_{\mathrm{minorize}} := \max_{\pi\in\Pi}t_{\mathrm{minorize}}(P_\pi)$

Question 4: $Q$ and $Q_\pi$

In this context, $Q:=\set{q_{s,a}\in \Delta(\mathbf S): (s,a)\in \mathbf S\times \mathbf A}$ is an element from the uncertainty set $\mathcal{P}$ consisting of transition kernels. On the other hand, $Q_\pi(s, s’):= \sum_{a\in\mathbf A}\pi(a|s)q_{s,a}(s’)$ is the transition matrix induced by policy $\pi$ and kernel $Q$. We have updated our manuscript to improve clarity.

[1] Wang, Y., Velasquez, A., Atia, G. K., Prater-Bennette, A., & Zou, S. (2023, July). Model-free robust average-reward reinforcement learning.