acceptodds
Under review as a conference paper at ICLR 2027

Distributionally Robust Average-Reward Reinforcement Learning: Finite-Sample Guarantees under Weakly Communicating

Abstract

We study distributionally robust reinforcement learning (DR-RL) in the average-reward setting under weak communication. Our main result provides finite-sample guarantees for estimating the robust optimal average reward and learning a near-optimal policy, covering both SA-rectangular and S-rectangular structures with divergence-based and distance-based uncertainty sets. Specifically, for Kullback–Leibler and -divergence balls, we establish explicit radius conditions under which the robust average-reward Bellman equation admits a constant-gain solution, while for total variation and Wasserstein balls, any positive radius suffices without requiring the nominal MDP is weakly communicating. Our algorithm is prior-knowledge-free and achieves sample complexities of for estimating the robust optimal average reward and for learning an -optimal policy. Here, is the smallest positive nominal transition probability and is a robust optimal bias function. We further provide an almost-tight explicit upper bound on . Finally, we validate the predicted convergence rate through numerical experiments.

Primary area:
learning theory
Keywords:
Reinforcement Learning, Distributional Robustness, Average-Reward, Sample Complexity, Weakly Communicating MDPs, S-Rectangular Uncertainty, SA-Rectangular Uncertainty

Reviews

Among:
Shape:
1234this paper, Top 30%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.67 over 3 reviews, above 70% of the others.
Reviewer_hUx8OpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies distributionally robust average-reward reinforcement learning with a generative model. It covers two rectangular sets and four uncertainty metrics for robustness considerations. The authors establish sufficient conditions under difference metrics to guarantee the existence of an optimal Bellman equation and a constant optimal robust gain. By estimating the nominal transition kernel with samples from a generator, this paper provides a finite sample complexity bound for obtaining a robust ϵ\epsilon-optimal policy under average reward criteria. The bound depends on the the span of the optimal bias function, which is further upper bounded under different settings.

Critical strengths
  1. This paper gives a finite sample complexity analysis under a weak communication assumption, which is weaker than previous work that assumes irreducibility, ergodicity, or unichain, enabling more MDPs to be consider under this setting.

  2. This paper targets a broader scope of settings in robust RL, by handling both SS- and SASA-rectangular sets under KL, fkf_k divergence, and TV, and Wasserstein distance.

Critical weaknesses
  1. In section 4.1, the main theoretical findings for the TV and Wasserstein distance are a natural extension of prior work. While for KL and fkf_k divergence, assumption 1 seems restrictive. For example, by the definition of p∧p_{\land}, it satisfies p∧≤1∣S∣p_{\land} \leq \frac{1}{\left|S\right|}, which may have negligible value when the state space is large. In this case, δ\delta can be close to 0 and the uncertainty set considered may be too restrictive in a robust RL problem.

  2. The experimental results are limited. They validate the rate of decrease in gain estimation error under a constructed MDP instance. However, since this paper focuses on the robust RL setting, an experiment comparing with the corresponding non-robust algorithm would better fit the purpose of this paper.

Questions for authors
  1. Is the extra p∧p_{\land} factor and assumption 1 necessary for policy learning, particularly for TV/Wasserstein uncertainty?

  2. In algorithm 1, how to solve for the empirical optimal discounted Bellman equation for both SS- and SASA-rectangular sets? What is the compuational complexity?

Reviewer_LQLTOpenReview ↗
Rating
2
Confidence
3
Informativeness
1
Presentation
3
Soundness
3
Read review
Paper summary

The paper derives finite sample guarantees for average reward MDPs under weak communication assumptions for SA- and S-rectangular uncertainty. Conditions for the existence of constant gain solutions to the robust average reward Bellman eq. are established. An algorithm based on discounted reduction is also developed.

Critical strengths
  • Existing literature on finite sample guarantees for robust RL has largely focused on the discounted setting. Results for average reward robust MDPs typically rely on strong assumptions (ergodicity, irreducibility, unichain, ...). This paper establishes guarantees under weak communication, which is a relaxation of these assumptions.
  • The paper provides conditions for the existence of constant gain solutions to the robust Bellman equation and bounds on the robust bias span for different uncertainty sets.
Critical weaknesses

My main concern is the limited technical novelty of the work. Extending finite sample guarantees to weakly communicating robust average reward MDPs has merit, but many of the main ingredients appear very closely related to existing results and techniques. At this point, I am not convinced that the paper introduces sufficiently new theoretical insights or analytical machinery for ICLR beyond combining and extending established arguments. Here are some specific points to be more concrete:

  • The structural results appear closely related to existing work, particularly [Wang and Si 2025]. Also, the proof of Theorem 2 seems to rely largely on standard arguments. For KL and divergence-based uncertainty, the span bound is obtained by combining existing support preservation results with classical hitting time arguments. Although making these bounds explicit is useful, it is unclear to me whether their derivation represents a significant theoretical advancement.

  • Per the remark following Theorem 1, Roch et al. (2026) had already identified that their finite sample guarantees could be extended to weakly communicating MDPs provided that the spans of all robust Bellman solutions are uniformly bounded. The present paper establishes such uniform bounds, which effectively verifies a sufficient condition for the extension identified in that work. This could still be useful but even the bounds appear to be derived using established arguments as discussed above. It is therefore unclear how significant the additional theoretical contribution is, particularly given that the finite sample analysis also relies on a standard discounted reduction. I would appreciate clarification on which aspects of the analysis require genuinely new techniques or provide insights beyond existing results.

  • The exponential dependence on the inverse of the smallest positive transition probability is established through a standard construction. The same exponential phenomenon can arise in nominal MDPs so there is nothing there that seems specific to robust RL or to rectangular uncertainty. The novelty of the lower bound and the additional insight it provides are thus unclear.

  • The proposed algorithm follows a very well established approach of reducing average reward learning to a discounted problem. The resulting sample complexity guarantees also retain dependence on the bias span and the smallest positive nominal transition probability, similar to previous analyses. It is not clear what fundamentally new analytical tools are needed for the proposed reduction and corresponding guarantees.

  • Although weak communication is a relaxation of the unichain assumption, the conditions imposed on the uncertainty sets can still be restrictive. In particular, the support preserving radius restrictions for divergence-based uncertainty can become restrictive when the smallest positive nominal transition probability is small. The practical significance of the resulting guarantees requires further discussion.

Questions for authors
  1. Given that extension to weakly communicating MDPs under bounded span assumptions is already identified in [Roch et al. 2026] and that Theorem 2 establishes uniform bound on the spans of all robust Bellman solutions, doesn't this allow their analysis to extend to the weakly communication setting? If so, what is the additional technical contribution beyond establishing these span bounds?

  2. To what extent do the Bellman existence results and explicit span bounds improve upon the existing structural results (hitting time arguments)?

  3. Is there a new insight that Theorem 3 provides beyond establishing a matching exponential dependence through a standard construction?

  4. Does the analysis of S-rectangular uncertainty require new techniques that are substantially different from those available for SA-rectangular uncertainty? If so, please highlight these differences more explicitly.

I would be happy to reconsider my assessment if the authors can clarify the genuinely new technical contributions, particularly any non-trivial aspects of the analysis and guarantees.

4 comments

Thank you again for your detailed review. We hope our clarifications are helpful and look forward to hearing your comments. We would be happy to address any remaining concerns.

Reviewer_LQLTOpenReview ↗

Re: Official Comment by Authors

Thank you for the detailed response and clarifications regarding (i) the distinction between requiring a uniform span bound over all Bellman solutions and using the span of a single solution, (ii) the additional challenges under S-rectangular uncertainty, and (iii) the differences from previous discounted reduction analyses. These clarifications address several of my concerns. Some reservations remain regarding their significance. In particular, the structural span bounds rely substantially on established support preservation and hitting-time arguments (I understand that handling S-rectangular uncertainty introduces some additional challenges). Also, while Theorem 3 establishes a matching exponential dependence, the underlying construction and phenomenon are already familiar from nominal MDPs, so its additional theoretical insight appears limited.

Thank you for your thoughtful feedback. For distance-based uncertainty sets (TV and Wasserstein), admissible perturbations may destroy the support of nominal transitions, so the minimum positive transition probability is not preserved. Consequently, traditional hitting-time arguments cannot be directly applied, requiring a new proof technique.

To illustrate our motivation, consider a two-state robust MDP with S=0,1\mathcal S=\\{0,1\\}, a single action, rewards r(0)=0r(0)=0, r(1)=1r(1)=1, and nominal transitions p0=(1,0)p_0=(1,0), p1=(0,1)p_1=(0,1). Under TV uncertainty with radius δ∈(0,1)\delta\in(0,1), the worst-case transitions are q0=(1,0)q_0=(1,0) and q1=(δ,1−δ)q_1=(\delta,1-\delta). The robust Bellman equations yield

gδ∗=0,uδ∗(0)=0,uδ∗(1)=1+(1−δ)uδ∗(1)=1/δ.g_\delta^{\ast}=0,\qquad u_\delta^{\ast}(0)=0,\qquad u_\delta^{\ast}(1)=1+(1-\delta)u_\delta^{\ast}(1)=1/\delta.

Thus, Span⁡(uδ∗)=1/δ\operatorname{Span}(u_\delta^{\ast})=1/\delta. This observation led us to conjecture that 1/δ1/\delta is a tight upper bound for TV, and subsequently motivated the analogous bound (c/δ)ℓ(c/\delta)^\ell for Wasserstein.

To establish these bounds, we develop a different proof technique by directly constructing a feasible kernel

qs,a=(1−α)ps,a+α1s−,q_{s,a}=(1-\alpha)p_{s,a}+\alpha\mathbf1_{\\{s^-\\}},

with α=δ\alpha=\delta for TV and α=(δ/c)ℓ\alpha=(\delta/c)^\ell for Wasserstein, where s−∈arg⁡min⁡svγ∗(s)s^-\in\arg\min_s v_\gamma^{\ast}(s). Under both SA- and S-rectangularity, the feasibility of this construction and the robust Bellman equations give the following two key inequalities:

max⁡svγ∗(s)≤1+γ[(1−α)max⁡svγ∗(s)+αmin⁡svγ∗(s)],\max_s v_\gamma^{\ast}(s)\le 1+\gamma\left[(1-\alpha)\max_s v_\gamma^{\ast}(s)+\alpha\min_s v_\gamma^{\ast}(s)\right],

min⁡svγ∗(s)≥γmin⁡svγ∗(s)≥0.\min_s v_\gamma^{\ast}(s)\ge\gamma\min_s v_\gamma^{\ast}(s)\ge0.

Subtracting these inequalities yields

Span⁡(vγ∗)≤1+γ(1−α)Span⁡(vγ∗)−(1−γ)min⁡svγ∗(s)≤1+γ(1−α)Span⁡(vγ∗).\operatorname{Span}(v_\gamma^{\ast})\le 1+\gamma(1-\alpha)\operatorname{Span}(v_\gamma^{\ast})-(1-\gamma)\min_s v_\gamma^{\ast}(s)\le 1+\gamma(1-\alpha)\operatorname{Span}(v_\gamma^{\ast}).

Consequently, Span⁡(vγ∗)≤1/[1−γ(1−α)]≤1/α\operatorname{Span}(v_\gamma^{\ast})\le 1/[1-\gamma(1-\alpha)]\le1/\alpha. Taking γ→1\gamma\to1 along a convergent subsequence yields the bounds Span⁡(uδ∗)≤1/δ\operatorname{Span}(u_\delta^{\ast})\le1/\delta for TV and Span⁡(uδ∗)≤(c/δ)ℓ\operatorname{Span}(u_\delta^{\ast})\le(c/\delta)^\ell for Wasserstein. Importantly, these bounds are independent of γ\gamma, allowing us to focus our analysis on a single robust optimal Bellman solution uδ∗u_\delta^{\ast} satisfying these bounds, without requiring uniform assumptions over all policies, such as unichain or uniform ergodicity.

Clavier et al. (2024) establish span bounds for all policies, achieving rates of O(1/σ)O(1/\sigma) under SA-rectangularity and O(1/(σmin⁡s∣πs∣∗))O(1/(\sigma\min_s\\|\pi_s\\|_{\ast})) under S-rectangularity as γ→1\gamma\to1. In comparison, our Theorem 2 provides explicit and tight upper bounds for the robust optimal bias function under both rectangularity structures. To the best of our knowledge, this direct feasible-kernel construction and the resulting span argument have not been used in prior work. Thus, except for the SA-rectangular divergence-based case, our proofs of Theorem 2 employ techniques different from prior work. Theorems 2 and 3 are primarily intended to provide theoretical completeness across all eight uncertainty configurations. We will further clarify their motivation and scope.

Among our contributions, Theorem 1 remains the main result. It establishes finite-sample guarantees for both robust optimal gain estimation and policy learning under weak communication, achieving ε−2\varepsilon^{-2} dependence in sample complexity. These guarantees depend only on the span of a single Bellman solution, without requiring uniform span bounds over all policies or Bellman solutions. The result applies to both SA- and S-rectangular uncertainty across all four uncertainty families. We believe these guarantees are of significant interest to the average-reward RL community.

Thank you again for your thoughtful feedback. We would like to kindly follow up on our previous response. As the deadline (Nov 18 AOE) is approaching, we would be happy to provide any further clarification if needed. We appreciate your time and consideration.

Reviewer_f8eROpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
3
Soundness
3
Read review
Paper summary

The paper considers average-reward robust MDPs under weak communication and proposes a model-based approach with sample complexity bounds. The setting covers various uncertainty sets, covering both SA and S rectangular sets and divergence and distance based uncertainty sets (KL, f_k, TV, Wasserstein). The results are in terms of span of a robust optimal bias, which they also provide bounds for. Finally, the authors verify their results on some numerical simulations.

Critical strengths
  1. Extending the analysis to weakly communicating robust MDPs is significant since ergodicity/unichain assumptions are very restrictive and also very difficult to verify.
  2. The results are quite comprehensive, it also covers s-rectangular sets and contains several uncertainty sets. Bounding the span of a robust optimal bias and making the algorithm prior knowledge-free algorithm are also nice additions, which makes the paper more complete.
Critical weaknesses
  1. Novelty: The analysis does not seem to be very novel and the results do not seem very surprising. At a high level, the paper seems to be putting together existing methods rather than creating a new analysis technique for their proofs. (Wang & Si, 2025) in particular already provides much of the structural results for the robust weakly communicating case.

Shengbo Wang and Nian Si. Bellman optimality of average-reward robust Markov decision processes with a constant gain. arXiv preprint arXiv:2509.14203, 2025.

Questions for authors

Can you please clarify the novelty in the analysis? What was the main challenge in going from the structural results in Wang & Si 2025 to finite-sample guarantees in this paper?

5 comments

Thank you again for your detailed review. We hope our clarifications are helpful and look forward to hearing your comments. We would be happy to address any remaining concerns.

I thank the authors for their detailed response. The response clarifies the additional statistical steps beyond Wang and Si, particularly controlling empirical Bellman perturbations and obtaining a guarantee for the returned policy without uniform policywise mixing bounds.

My remaining concern concerns the originality of those steps. Wang and Si already provide the optimal discounted-span comparison, while Li et al. (AISTATS 2026, Appendix D.2) already analyze the coupled fkf_k dual through interpolation, the envelope theorem, and optimizer conditions. Could you pinpoint the essential additional developments relative to these arguments, particularly in Lemmas 14-18 and the returned-policy analysis?

I acknowledge the value of the resulting finite-sample extension, my only remaining concern now is about the extent of additional analytical innovation.

Thank you for your thoughtful feedback. Li et al. (2026, Appendix D.2) restrict the dual optimization to the open set X2=η:daessinf⁡μau<ηa<M,∀a∈AX_2=\\{\eta:d_a\operatorname{essinf}_{\mu_a}u<\eta_a<M,\\ \forall a\in\mathcal A\\}. They then apply the envelope theorem to obtain

V(1)−V(0)=∫01∂tg(η∗(t),t),dt,η∗(t)∈arg⁡max⁡η∈X2g(η,t).V(1)-V(0)=\int_0^1\partial_tg(\eta^{\ast}(t),t)\\,dt,\qquad \eta^{\ast}(t)\in\arg\max_{\eta\in X_2}g(\eta,t).

However, since X2X_2 is not compact, the supremum over X2X_2 is not guaranteed to be attained. In particular, they do not establish that arg⁡max⁡η∈X2g(η,t)≠∅\arg\max_{\eta\in X_2}g(\eta,t)\neq\varnothing for almost every t∈[0,1]t\in[0,1]. Thus, η∗(t)\eta^{\ast}(t) may not exist, and the above integral representation is not justified as written.

In our Lemma 14, we instead define the compact set

X=∏a∈A[La,Ma+∑b∈A(Mb−Lb)c−∣A∣1/k],X=\prod_{a\in\mathcal A}\left[L_a,\\ M_a+\frac{\sum_{b\in\mathcal A}(M_b-L_b)}{c-|\mathcal A|^{1/k}}\right],

where La=min⁡x∈Xs,aϕ(a)zs,a(x)L_a=\min_{x\in\mathcal X_{s,a}}\phi(a)z_{s,a}(x) and Ma=max⁡x∈Xs,aϕ(a)zs,a(x)M_a=\max_{x\in\mathcal X_{s,a}}\phi(a)z_{s,a}(x). We prove that G(t)=sup⁡θ∈Xf(θ,t)G(t)=\sup_{\theta\in X}f(\theta,t) for every t∈[0,1]t\in[0,1]. Since XX is compact, Lemma 15 guarantees X∗(t)≠∅X^{\ast}(t)\neq\varnothing. We also explicitly handle the boundary case Bθ(t)=0B_\theta(t)=0, proving that ft(θ,t)=0f_t(\theta,t)=0 in this case. Consequently, Lemma 16 rigorously establishes G(1)−G(0)=∫01ft(θ∗(t),t),dtG(1)-G(0)=\int_0^1 f_t(\theta^{\ast}(t),t)\\,dt.

Even if we assume that the envelope theorem argument in Li et al. is valid, their perturbation bound cannot be directly used in our average-reward analysis. Their final estimate depends on ∣u∣∞\\|u\\|_\infty, and they subsequently use ∣R+γv∣∞≤(1−γ)−1\\|R+\gamma v\\|_\infty\le(1-\gamma)^{-1}, which diverges as γ→1\gamma\to1. Specifically, their proof uses ∣u(x)−∣u∣L∞(μa)∣≤2∣u∣L∞(μa)|u(x)-\\|u\\|_{L^\infty(\mu_a)}|\le2\\|u\\|_{L^\infty(\mu_a)}, yielding

|\partial_tg(\eta^{\ast}(t),t)|\le2\\|u\\|_{\infty,\mu}\left\\|\frac{dm_n}{d\mu_n(t)}\right\\|_{\infty,\mu}.

In our Lemma 18, we use Ma=max⁡x∈Xs,aϕ(a)zs,a(x)M_a=\max_{x\in\mathcal X_{s,a}}\phi(a)z_{s,a}(x) and the sharper inequality 0≤Ma−ϕ(a)zs,a(x)≤ϕ(a)Span⁡(zs,a)0\le M_a-\phi(a)z_{s,a}(x)\le\phi(a)\operatorname{Span}(z_{s,a}). Together with the optimizer condition in Lemma 17, this gives

∣ft(θ∗(t),t)∣≤2η∑a∈Aϕ(a)Span⁡(zs,a)≤2η(1+Span⁡(v)).|f_t(\theta^{\ast}(t),t)|\le2\eta\sum_{a\in\mathcal A}\phi(a)\operatorname{Span}(z_{s,a})\le2\eta(1+\operatorname{Span}(v)).

Our Lemma 21 further establishes Span⁡(vγ∗)≤2Span⁡(uδ∗)\operatorname{Span}(v_\gamma^{\ast})\le2\operatorname{Span}(u_\delta^{\ast}). Therefore, we can control the perturbation using the robust optimal bias span without introducing an additional (1−γ)−1(1-\gamma)^{-1} factor, which is essential for our finite-sample analysis under weak communication.

Finally, our Lemmas 14–18 apply to both S- and SA-rectangular uncertainty. Under S-rectangularity, we directly analyze the coupled dual problem, while under SA-rectangularity, we apply the same argument separately to each action. These results provide the span-dependent Bellman perturbation bounds needed for Theorem 1 under both rectangularity structures.

Chen et al. (2025) [2] rely on uniform ergodicity to obtain uniform minorization-time bounds (Proposition B.2), which underlie their discounted value span bound (Proposition A.5) and discounted-to-average approximation (Lemma A.6). Under weak communication, some policies may be multichain with infinite mixing times, making these bounds unavailable. Instead, Lemmas 21 and 25 control the optimal discounted value span and approximation error through Span⁡(uδ∗)\operatorname{Span}(u_\delta^{\ast}).

Chen et al. [2] and Li et al. [3] bound policy error via uniform policy-value estimation:

Vγ∗(s)−Vγπ^∗(s)≤2sup⁡π∈Π∣V^γπ−Vγπ∣∞.V_\gamma^{\ast}(s)-V_\gamma^{\widehat\pi^{\ast}}(s)\le2\sup_{\pi\in\Pi}\\|\widehat V_\gamma^\pi-V_\gamma^\pi\\|_\infty.

Chen et al. require uniform minorization times; Li et al. use Span⁡(Vγπ)≤1/(1−γ)\operatorname{Span}(V_\gamma^\pi)\le1/(1-\gamma), which is too loose. Instead, Lemma 19 bounds Bellman-operator perturbations for any stationary randomized policy. Bellman inequalities and telescoping directly give

gδπ^∗(s)≥(1−γn)min⁡xv^γn∗(x)−3η(1+Span⁡(v^γn∗)).g_\delta^{\widehat\pi^{\ast}}(s)\ge(1-\gamma_n)\min_x\widehat v_{\gamma_n}^{\ast}(x)-3\eta(1+\operatorname{Span}(\widehat v_{\gamma_n}^{\ast})).

This yields Theorem 1's policy-error guarantee without uniform span or mixing-time bounds over all policies.

Comments on the paper

1 comment

We thank all reviewers for their thoughtful feedback and constructive comments. We summarize the main concerns and our revisions below.

  1. Novelty of the main results (LQLT, f8eR). Theorem 1 establishes finite-sample guarantees for robust optimal gain estimation and policy learning under weak communication, depending only on the span of a single Bellman solution, rather than uniform bounds over all solutions as required by Roch et al. (2026). Our result achieves ε⁻² sample complexity across all eight uncertainty configurations.

  2. Novelty of the technical analysis (LQLT, f8eR). Unlike Chen et al. (2025), our Lemmas 19, 21, and 25 allow us to analyze the returned policy directly without uniform mixing-time bounds. Lemmas 14–18 establish a compact optimization domain, handle boundary differentiability, and obtain perturbation bounds depending on the value span. We also derive dual formulations for S-rectangular TV and Wasserstein uncertainty and handle transition-dependent rewards.

  3. Span bounds and theoretical insights (LQLT, hUx8). For TV and Wasserstein, uncertainty may destroy nominal transition support, so traditional hitting-time arguments cannot be directly applied. Our feasible kernel construction yields explicit and tight bounds of 1/δ and (c/δ)^ℓ, respectively. Theorem 3 highlights the different dependencies of divergence-based and distance-based uncertainty. We have added a remark after Theorem 2 and clarified the motivation and scope of Theorems 2 and 3.

  4. Assumptions, sample complexity, and computational complexity (LQLT, hUx8). We clarified that the radius restrictions apply only to KL and f_k-divergence. In many practical applications, transitions are local even when the state space is large, so the minimum positive nominal transition probability need not decrease with the state-space size. We also explained the additional factor in policy sample complexity arising from our fixed discount factor and provided the empirical Bellman solver and computational complexity for both rectangularity structures.

  5. Experimental validation (hUx8). We have added a non-robust baseline using the same samples. Our method achieves substantially lower estimation error across all eight uncertainty configurations, with results presented in Appendix G.

Overall, we believe our results fill an important gap between existing structural results and finite-sample robust gain estimation and policy learning, and make a valuable contribution to the average-reward RL community.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.