Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning
Authors: Zijun Chen
Shengbo Wang
Nian Si
Venue: NeurIPS 2025 poster ()
Keywords: Reinforcement Learning
Distributional Robustness
Markov Decision Process
Ergodicity
Long-run Average Reward
Primary area: reinforcement_learning
TL;DR: We propose priori knowledge-free algorithms for distributionally robust average-reward estimation, with both finite-sample theoretical guarantees and numerical validation.

Abstract: Motivated by practical applications where stable long-term performance is critical—such as robotics, operations research, and healthcare—we study the problem of distributionally robust (DR) average-reward reinforcement learning. We propose two algorithms that achieve near-optimal sample complexity. The first reduces the problem to a DR discounted Markov decision process (MDP), while the second, Anchored DR Average-Reward MDP, introduces an anchoring state to stabilize the controlled transition kernels within the uncertainty set. Assuming the nominal MDP is uniformly ergodic, we prove that both algorithms attain a sample complexity of $\widetilde{O}\left(|\mathbf{S}||\mathbf{A}| t_{\mathrm{mix}}^2\varepsilon^{-2}\right)$ for estimating the optimal policy as well as the robust average reward under KL and $f_k$-divergence-based uncertainty sets, provided the uncertainty radius is sufficiently small. Here, $\varepsilon$ is the target accuracy, $|\mathbf{S}|$ and $|\mathbf{A}|$ denote the sizes of the state and action spaces, and $t_{\mathrm{mix}}$ is the mixing time of the nominal MDP. This represents the first finite-sample convergence guarantee for DR average-reward reinforcement learning. We further validate the convergence rates of our algorithms through numerical experiments.

Sample Complexity of Distributionally Robust Average-Reward Reinforcement Learning
Zijun Chen
Department of Computer Science and Engineering Hong Kong University of Science and Technology zchendg@connect. ust.hk hk
Shengbo Wang Daniel J. Epstein Department of Industrial and Systems Engineering University of Southern California shengbow@usc.
Nian Si
Department of Industrial Engincering and Decision Analytics Hong Kong University of Science and Technology niansi @ust. hk
Abstract
Motivated by practical applications where stable long-term performance is criti- cal-such roboties, operations research, and healthcare-we study the problem of distributionally robust (DR) average-reward reinforcement learning. We propose algorithms that achieve near-optimal sample complexity. The first reduces the problem to a DR discounted Markov decision process (MDP), while the second, Anchored DR Average-Reward Reward MDP, introduces an anchoring state stabilize the controlled transition kernels within the uncertainty set. Assuming the nominal MDP is uniformly ergodic, we prove that both algorithms attain sample complex- ity of Ô ([S) 2 for estimating the optimal policy as well the robust average reward under KI. and fx-divergence-basee uncertainty sets, provided the uncertainty radius is sufficiently small. Here, e the target accuracy, [S] and |A| denote the sizes of the state and action spaces, and mii is the mixing time of the nominal MDP. This represents the first finite-sample convergence guarantee for DR average- reward reinforcement learning. We further validate the convergence rates of our algorithms through numerical experiments.
Introduction
is core machine learning framework in which agents learn to make decisions by interacting with their environments to maximize long-term rewards. RL has been successfully applied across wide range of domains-free classic applications in robotics and control systems [3] to more recent advances in game playing 21 and large language model (LLM))driven reasoning tasks [47 14].
Reinforcement learning (RL) 351
central assumption in that the training environment (e.g. simulator) faithfully represents the real-world deployment setting. In practice, however, this assumption rarely holds, leading to fragile policies underperform when exposed to mismatches between training and deployment environments. This remains major obstacle to translating RL's successes in simulated settings to reliable performance in real-world applications.
To address this challenge, Zhou et al. 56
built upon the distributionally robust Markov decision to propose a distributionally robust reinforcement learning
process (DR-MDP) framework [16]
27
48
"Corresponding author
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

(DR-RL) framework. Subsequent work advanced the field, including both model- free (22 40 43 and
model-based settings 129
50, B3), as well as approaches for offline learning 32 and generative
models 40
43
53
7
along with functional approximations 2 24
However, the aforementioned developments predominantly focus discounted-reward or finite- horizon settings, while the average-reward case remains largely overlooked. This gap is significant because average-reward reinforcement learning is crucial in many practical applications where long-term performance matters more than short-term gains. For example:
. Control systems (e.g., robotics, autonomous vehicles) often require optimizing steady-state performance rather than cumulative discounted rewards.
Operations research problems (e.g., inventory management, queueing systems) rely on long-run average metrics for stability and efficiency.
Healthcare or energy management applications may prioritize sustained optimal performance over finite-time rewards.
Average-reward RI. not only important but also more challenging in terms of algorithm design and theoretical analysis. In the standard (non-robust) RL setting, the minimax sample complexity for generative models in discounted-rewt reward cases was resolved as early as 2013 M. In contrast, analogous results for average-reward settings were only developed much later, with recent advances 60) under granular structural assumptions.
in Wang et al. 37 Zurek and Chen 57 58 59
This paper marks the first systematic analysis of the statistical properties of distributional robust average-reward MDPs AMDPs) in the tabular setting, addressing a critical gap in the literature.
Specifically, we propose two algorithms that achieve near-optimal (in a minmax sense) sample complexity for learning DR-AMDPs. The first is based reduction the DR discounted-reward MDP (DR-DMDP), where a discount factor y must be carefully chosen to balance the trade-off between finite sample statistical error and the algorithmic bias introduced by the reduction. The second algorithm, anchored DR-AM AR-AMDP, modifies the entire uncertainty set of transition kernels by introducing an anchoring state with certain calibration probability.
To demonstrate their statistical efficiency, we consider a tabular setting where the nominal MDP is uniformly ergodic (Definition 3.3) with uniform mixing time upper bound tmix for all stationary, Markovian, and deterministic policies. We show that, to learn the optimal robust average reward and policy within E accuracy, both algorithms achieve a sample complexity of Ô (|S]|A = under KL and fx-divergence uncertainty sets, assuming a sufficiently small uncertainty radius 8 (to be defined). Here, |S] and |A| denote the cardinality of the state and action spaces, respectively. Compared standard (non-robust) average-reward RL literature, this rate optimal in its dependence on |S| A| and E.
Our analysis establishes three key contributions to the theory of DR-RL under the average-reward criterion. First, we address a fundamental modeling challenge: conventional uncertainty sets can contain MDPs that are not unichain, thereby invalidating the standard Bellman equations. To resolve this issue, we derive structural conditions on the uncertainty set that ensure stability for all MDPs within it. Second, we develop and analyze the reduction yielding the first stability-sensitiv sample complexity bound for DRDDMDPs of [|S upper bound for DR-AMDPs. Building on this framework, we introduce the anchored algorithm and show that its output coincides with that of the reduction approach under a suitable choice of the anchoring parameter. Third, both algorithms knowledge of model-specific parameters, particularly the mixing time fmix- Collectively, our work offers unified treatment that connects robustness, stability, algorithm design, and finite-sample guarantees for DR-RL under the average-reward criterion.
?)= and hence the aforementioned
designed to function without requiring prior
The remainder of this paper is organized as follows:
Section 2 |surveys existing results for both standard and robust RLs. Section intrrouuess the mathematical preliminaries, including key notations and problem formulation. Our main theoretical contributions, including algorithmic development and sample complexity analysis, are presented Section 4 Finally, Section 5 provides empirical validation of our theoretical findings and Section [ concludes the paper and discusses future work.

---

Table 1: Summary of S.O.T.A. sample complexity results in the literature, where mii defined in
Type
Sample Complexity
Origin
Standard
Discounted
@([)) |A
E)-
Azar et al. [. Li et al. [20
Discounted Mixing
( A Lmmix (1
-7) -)-
Wang et al. 37
Average Mixing
- (|S) A f
Wang et al. 38
Zurek and Chen
557
DR-RL
Discounted
Ó(S |A (1 --)= 2)
Shi and Chi 32
Wang et al.
43
Discounted Mixing
0 |||||A|P 1 miix (1- ---)
Theorem 4.3
Average Mixing
Ó(S| A mix
Theorem 4.4 & 4.5
2 Literature Review
Sample Complexity of Discounted- Tabular RL: There is an extensive literature on the sample complexity of tabular reinforcement learning. standard (non-robust) settings, the minimax sample complexity for discounted-reward problems has been well studied. Early works by Azar et al. M1. Li al. [20] established the minimax rate of @(SS]AA(1 32- More recent research has shifted toward mnstance-dependee
bounds that leverage structural properties of the MDP. For example, Wang al. B8). Zurek and Chen (59] derive tighter instance- dependddn bounds of [[[S]||||tbee uniformly ergodic or weakly communicating, where H denotes the span of the relative value function.
7) 2 and Ö(S [H(L - ?) =3 under the assumptions that P is
Sample Complexity of Aewarde-Reaard Tabular RL: Recently, there has been growing interest in the sample complexity of average-rewars reinforcement learning in standard (non-robust) settings. Early work by Jin and Sidford [17 established a bound of Ö([ A using primal-dume
stochastic mirror descent. A rate of O(S)) Imise -3) was established later via reduction to the discounted MDP setting [18]. Subsequent analyses achieved tighter bounds: Wang et al. [38] obtained a rate of Ō [t|lA|tmix -). while Zurek and Chen [57 59 derived instance-dependent optimal rates
of Ö(S)) ||||||HHHHS ?) for weakly communicating MDPs. Further refinements [58] 60 achieved similar rates without requiring prior knowledge, using plug-in and span penalization approaches. Beyond the generative model setting, Zhang al. (55) and Chen [5] provided finite-sample analyses for synchronous and asynchronous Q-learning, respectively. Asymptotic properties were also studied in
Yu et al. (54). Wan al. (36] for asynchronous Q-learning.
DR-DMDP and DR-RL: Our work builds on the theoretical foundations of robust MDPs
27 48 49 42) which primarily develop dynamic programming principles under the discounted- reward setting. Recent advances in distributionally robust reinforcement learning (DR-RL) have investigated the sample complexity of DR-DMDPs under various divergence-basee uncertainty sets. For example, Wang et al. [43]. Shi and Chi [2) establish a model free upper bound of O(SS]|A|[ - 7) --- -2= under KL KL-divergence. Under x -iveergge, Shi et al. [33] obtain a similar upper bound, while Clavier et al. 7 show that 4y-norm constraints admit a tighter minimax rate of @([S] A| 7) -2) In this paper, by incorporating the mixing time parameter, we present a siitance--deendeence sample complexity bound of Ô || mix (1 11-7) -> -=),,, which improves the dependence on the effective horizon from (1 - -1 to (1 -2 Several other works contribute to the theoretical and algorithmic landscape of DR-RL in various settings, including Panaganti and
Kalathil (28). Yang al. [52). Xu et al. [50], Blanchet al. [3. Liu et al. [23] Wang et al. [41), Yang et al. [5I].
Distributionally Robust Average-Reward MDPs: While the sample complexity of learning DR- DMDP's has been extensively studied, the average-rewarrs setting remains relatively underexplored. Wang et al. 46 44 45 prove their convergence, but without providing sample complexity guarantees. Grand-Clément et al. [2] show that for (s, a) -eeetatang uncertainty sets, the optimal policy can be stationary and deterministic; however, this result may not extend s-rectangular uncertainty sets. More recently, Wang and Si [39] study average-reward robust MDPs under s-rectangular uncertainty and provide
propose robust relative value iteration and TD/Q-leaming algorithms and
3

---

one-sided weak communication conditions that ensure the existence of solutions to the Bellman optimality equation. Although existing work has investigated the existence and structure of optimal policies in average-reward DR-RI, non-asymptotic sample complexity bounds remain an open question.
We provide summary of state-of-the-ar sample complexity results in the literature in Table [ In particular, we establish the first sample complexity guarantees for the average-reward DR-RL formulation, which achieves optimal dependence for and |S||A|]
3 Preliminaries
3.1 Markoy Decision Processes
We briefly review and define some notations for classical tabular MDP models. Let A(S) denotes the
probability simplex over IR A finite discounted MDP (DMDP) is defined by the tuple (S, A, P. P. 7) Here, S, A denote the finite state and action spaces respectively; r S A + [0. 1] the reward
function; P = {pa.. E (S)) (s, a) E S x A) is the controlled transition kernel, and (0, 1) the discount factor. An average-reward MDP (AMDP) model, on the other hand, is specified by
(S, A,, r, P) without the discount factor.
Define the canonical space Ω = (S x A equipped with FF the a-field generated by cylinder sets. The state-action process {(S,, A,), 2 0} is defined by the point evaluation X, (,()) 8t, Ar(w) = 0e for all t 2 0 for any w = (80: ag, $1, a1....) E Q. A general history dependent policy π = (me)s20 E 1HD is sequence of the agent's decision rule. Here, the decision rule n. time f a mapping Te : (S x A) x S + A (A), signifying the conditional distribution of A, given the history. It is known in the literature 30 i2 that to achieve optimal decision making in the context of infinite horizon AMDPs, DMDPs, or their robust variants (to be introduced), it suffices to consider the policy class II of stationary, Markov, and deterministic policies; i.e. π II can be seen as function : S - A. Thus, in the subsequent development, we restrict our discussion to II.
As in Wang al. 388 policy E TI and an initial distribution μ E A(S) uniquely defines probability measure on (2, We will always assume that j is the uniform distribution over S. The expectation under this measure is denoted by Ep. To simplify notation, we define (=
EAEA (aass)p.,a (s') and rx (s) == Enca [(als)r(s, a).
pecounted-reward MDP (DMDP): Given DMDP instance (S. P.P) and π E II. the discounted value function Vp S + RR is defined as: Vp = Ep 1= (r A = s]. An
optimal policy " achieves the optimal value V5 == max
Average-reward MDP (AMDP): For AMDP model (S, A, r, P) and π E II, the long-run average- renctf 97. S + R is defined as (s) == lim sup T ET DD r(S,, A. s).
When uniformly ergodic (a.k.a.unice .ui.chinn, be defined later), the ghdh is constant across states 30]. In this context, an optimal policy π² E Il achieves the long-run average-reward ea 97.
3.2 Uniform Ergodicity
Motivated by engineering applications where policies induce systems that are stable in the long run, we consider a stability property of MDPs known as uniform ergodicity, a stronger version of the unichain property. In this setting, the controlled Markov chain induced by any reasonable policy converges in distribution to a unique steady state in total variation distance Il-IIrv defined by Ipp ry == supacs Ip(A) (AA) for probability vectors p. 9 E A(S).
We start with reviewing concepts relevant to uniformly ergodic Markov chains.
Definition 3.1. (Uniform Ergodicity) A transition kernel K E RRSS is uniformly ergodic one of the following holds
There exists a probability measure p for which (s,)) pl|TV -> 0 for all E S.
K satisfies the (m, p)Dooellin condition: For some m E N and p E (0, if there exists probability measure v and a stochastic kernel R s.t. (T (s'(s) + (1 R)s

---

It is well known [25] that p must be the unique stationary distribution of K and that two conditions are equivalent. The vp and R in the Doeblin condition are known as the minorization measure and the residual kernel respectively.
Next, we introduce the mixing and minorization times associated with uniformly ergodie kernel K.
Definition 3.2. (Mixing Time and Minorization Time) Define the mixing time of uniformly er- godic transition kernel P as miix (K) ;= inf m 2 1 max,es K (s, p(-)]l S } and the minorization time as Eminorize K) == inf mm/p minges K (s, 2 pip(-) (-) for some 3/ E A(S))
It shown in Theorem of Wang et al. 37 that for a uniformly ergodic transition kernel K, these met- rics of stability are equivalent up constants: Eminorize (K) < 22/ (K) S 22 (og616)mmmnoiit (K).
While the MDP sample complexity literature typically uses the mixing time complexity parameter, for our purposes, the Doeblin condition and the associated minorization time offer sharper theoretical insights into how adversarial robustness affects the statistical complexity of RL. Given the equivalence between mixx ( and Imimorize K), and the latter's advantage in revealing these insights, we will use mminorize K') time throughout this work.
Having reviewed the uniform ergodicity of a stochastic kernel K, we define uniformly ergodic MDPs.
Definition 3.3 (Uniformly Ergodic MDP). An MDP (or its controlled transition kernel P) is said to be uniformly ergodic if for all policies II, minoriiaa (P=) < oc. Then, define minorriee max mmnorrize ( (,)) < 0o.
To provide sharper sample complexity results, it is useful to define the following upper bound parameter m.
my max inf {m: Pa is (m, p) Doeblin and m/p tminorize (P,) for some p}. (3.1)
=enl
This is well defined: In Appendix A Lemma A.3
prove that for any transition kernel P,, the equality m/p = Eminorize (Px) is always attained by some m and s.t. min P (s, 2 pr(())
It is easy to see that my < Iminorine and we will demonstrate by the example in Section 5 that it is possible for my = while 'minorize can be arbitrarily large.
3.3 Distributionally Robust Biccounted-Rewarte and Average-Reward MDPs
This paper focuses on a robust MDP setting where the stochastic dynamics of the system is influenced by adversarial perturbations the transition structure. We assume the presence of an adversary that can transition probabilities within KL. or /s-divergence uncertainty sets. Specifically, for probability measures 4,P A(S) where q is absolutely continuous w.r.t. p, denoted by 9 < p, define Here, the
DKL (gllp) = E.es (s)p((()))))(())) and D (gllp) == E.es (()(((())p(())((()))))) function fu is defined for l E (1, 20) by fa(t) = (th kt + k - 1)/ - 1)). When k = 2, D is the x2 2 -ivieeegeec..
We assume that the underlying MDP has an unknown nominal controlled transition kernel
P {Pa.a E A(S) (s. e S A}.
(3.2)
For each as E S A we define the uncertainty set under divergence D = DKL, Dr. and parameter 5 > 0 centered at Ps.a by (D,)( possible adversarial perturbations of the transition out of (s, a). Note that the parameter controls the size of the (D, 5), quantifying the power of the adversary. The uncertainty set for the entire controlled transition kernel is P(D, 8) == X(I.))EXXA Pa.o (D,6). 6). An uncertainty set of this product
{p : (ppllp...) < 0}. This set contains all
from called SA-rectangular 42
We will suppress the dependence of D and when it is clear from the context. Also, for notation simplicity, define the mapping r P.... .RSS - R for Px.a C A(S) by
Tr. (V) = inf FSS-p [V(S)] PEP.,.
Optimal distributionally robust Bellman operators TV and T are central to algorithmic design.
5

---

T Definition 3.4. The optimal DR Bellman operators T,, T :R - R are defined by
(V) max {r(s, a) + P. (V)
a (8) == max
(3.3)
r(s,, a) + +p... (t)}
a
DR-DMDP: A DR-DMDP model is given by the tuple (S, A, P,r,, For fixed π E II, define the DR value function
V$(s)
EP PE(P)
inf
Y rr(S
A,) So So= So
(3.4)
See Iyengar [16] for a rigorous construction of the expectation Ep. Then, the optimal value function (s)(s) max V (s). is well known (c.f. Iyengar (T6) that V2 is the unique solution of the DR Bellnhman equation: Vi = (Vp))
Note that the expectation Ep is under the adversarial perturbation from Markovian policy class (P) It is possible to consider other information structures for the adversary while retaining the satisfaction of the Bellman equation (4).
DR-AMDP: A DR-AMDP model is given by the tuple (S, A, P,r). To simplify our presentation, we restrict our consideration to uniformly ergodic DR-AMDPs.
For each π E we define the DR long-run average-reward function by
g
= inf lim sup EP PE(P)N
Σ r rS,, A.)
So
(3.5)
T
T-000
Natually, the optimal average reward is gp(()) = max (s).
This paper focuses on a setting where the DR-AMDP is uniformly ergodic in the following sense. Definition 3.5. A DR-AMDP (or P) is said be uniformly ergodic if for all controlled kernels E Q is uniformly ergodic as in Definition 3.3
We note that p 5) is compact in the sense that Ps.a(D,)) is compact subset of A(S) for all 8, a. With uniform ergodicity and compactness, Wang et al. [44) shows that gp(() is constant for E S which uniquely solves the DR Bellman equations.
Proposition 3.6 (Theorems 7 an 8 of Wang et al. [44).. IfP is uniformly ergodic with a uniformly bounded minorization time, then gi (s) = 9p constant s E S. Moreover there exists solution (g, v) of v(s) (v)(s) 9" (8) for all 8 E S and any such solution satisfies g(s) = =gp for all E S. Moreover, the policy x²(6 (s) E arg max.eA {r(s,a) a) + PP... (w)} achieves the optimal average-reward Fp-
4 DR-AMDP: Algorithms and Sample Complexity Upper Bound
In this section, we introduce two algorithms for DR-AMDPss and establish their sample complexity upper bounds. Before presenting the algorithms and results, we first specify the assumptions on the data-generating process and MDP models, along with insights into their rationale and relevance.
We assume the availability of simulator, a.k.a. generative model, which allows us to sample independently from the nominal controlled transition kernel Ps.a. for any (s, a) E S A. Given
sample size n, we sample i.i.d. { (s!)) [..,,.... s...))) from Pa.o and construct the empirical transition probability
s(a)
(s.a = Σ
1
S 1
1
=
(4.1)
1=1
Unlike Wang et al. 44 which requires unichain assumption on every element of P. we only assume that the nominal controlled transition kernel P is uniformly ergodic. We will establish that this weaker condition, coupled with properly constrained adversarial uncertainty set in Assumption 2 will still guarantee the uniform ergodicity for all Q E P.

---

Assumption 1.
The nominal controlled transition kernel P in 3.2 is uniformly ergodic with
minorization time minorixe as Definition 3.3
To introduce limits the adversarial power and facilitate our sample complexity analysis, introduce the following complexity metric parameter:
Definition 4.1. Define the minimum support as:
PA
(s,0,s")E8xAA (Daaao') Pa > 0}
min
(4.2)
Assumption 2. Suppose the parameter satisfies S
PA when P(DKI. and 8 v 8mg
1
mmx PA when fw:
Here, the constant 1/8 can potentially be relaxed. As mentioned earlier, this restriction on the adversarial power parameter ensures the minorization times remain uniformly bounded across the uncertainty set by constant multiple of the nominal controlled kernel's minorization time.
Proposition 4.2. Suppose Assumptions 7 hold, and P P(DKL, or p())., satisfying As- sumption Then, for all Q P and π II, Iminorize (Qx) S 2iminorizes where mminorize is from
Assumption 7
The proof is deferred to Appendix B E We further note that without Assumption 2 the Hard MDP instance in Section 5 will have non-mixing worst-case adversarial kernel and state-dependent optimal average reward even when / This emphasizes the necessity of limiting the adversarial power obtain a stable worst-case system and state-independent average reward.
We propose two algorithms: Reduction to DR-DMDP and Anchored DR-AMDP. Notably, these are the first provide finite-sample guarantees for DR-AMDPss and achieve the canonical n 1/12 convergence rate in policy and estimation. Furthermore, both algorithms operate without requiring prior knowledge of minorizee Together, these contributions represent foundational advances in study of data-driven learning of DR-AMDPs.
4.1 Reduction to DR-DMDP
First, we present the algorithmic reduction from DR-AMDP to DR-DMDP. The algorithm design in this section inspired by prior works [46] [8. Specifically, we apply value iteration to an auxiliary empirical DR-DMDP model to obtain both the value function and optimal policy. Utilizing a calibrated discount 1 n 11/2 where n is the input sample size in Algorithm 1 we achieve an e-approximation of the target DR-AMDP value and policy with the auxiliary DR-DMDP using Ö(S] ||| minorize e- samples.
Algorithm 1 Distributional Robust DMDP: DR - DMDP(7,,,
Input: Discount factor y E (0, 1), sample size 1, D DKL Djc- For all (s,a) a) E S x A, compute the n- tamale empirical transition probability Pe.a as in (4. Construct the uncertainty set as P (s.a)exxA P..a where P... {p D(pl) S d)). Compute the solution V as the solution the empirical DR Bellman equation; i.c. Vs S:
(s())
max ((s, +I (V3) E
Then, extract any optimal policy #* E IT from 7 (s) E arg max.EA (r(3,a) +7T (Vz))
return 7* V
With the help of Proposition 4.2 the Algorithm I has the following optimal sample complexity guarantee.
Theorem 4.3. Suppose P = P(DKI, 5) or P(D,,, 8) and Assumptions D
in force. Then, for any > 32p log(2)$/3|A// the policy "* and value function Vž returned by Algorithm 1
7

---

satisfy
2 V Vp
C miinorize
/ogg(21(19/A//3) and
7) /np,
(4.3)
tminorize
VV Vo
/ log(2/S|/|A1/3)
with probability at least 3. where the constants c, c' S 2 for both the KL and fu cases.
The proof of Theorem is deferred to Appendix
We note that Theorem 4.3 implies that
to achieve an E-optimal policy as well as producing uniform E-error estimate of V2 with high
probability using Algorithm| we need (([S] A Amminoriz (1 - = samples. Compared
to state-of-the-arr sample complexity results for DR-DMDPs 32
4
33
Theorem 4.3 provides
significant refinement: when the nominal controlled kernel is uniformly ergodic, the effective horizon
dependence improves (1 --7 -)- Notably, this (1 - -) ) scaling also known be optimal in the non-robust setting [37] which corresponds to DR-DMDPs when = 0. As we will show, this
optimal dependence directly enables the canonical n 11/2 convergence rate for policy learning and value estimation in the DR-AMDP setting.
Algorithm 2 Reduction to DMDP
Input:
Samples size
Assign 7 = 1/vn and run Algorithm 1 with input DR DMDP(7, n) obtain H*, V return ** V/lVn
Theorem 4.4. Suppose P P(DKL, 8) p(D),,) 8) and Assumptions and 2 are in force. Then
for any 2 32p log( (2 the policy 7t and value function V Vn returned by Algorithm
2 satisfies
Ininorize
0 0. gpp
9p
log (2)(22)))
and
VIpA
(4.4)
V
tminorize
1og(2
Vn
VMpA
with probability B, where the constants c, 120 for both the KL and fü cases.
Again, we remark that Theorem 4.4 implies that to achieve an e-optimal policy as well as producing uniform E-error estimate of the optimal robust long-run average reward with high probability using Algorithm we need Ö(SS) A mmnoriineP samples.
4.2 Anchored DR-AMDP
In this section, we develop anchored DR-AMDP Algorithm 3 that avoids solving a DR-DMDP subproblem. Inspired by Fruit et al. [10], Zurek and Chen [58] s anchoring approach for classical MDPs, our anchored DR-AMDP approach modifies the entire uncertainty set of controlled transition kernels via uniform anchoring state so and calibrated strength parameter We show that Algorithm Jenjoys the same error and sample complexity upper bounds to Algorithm 2
Theorem 4.5. Suppose Assumption 1 [andd2 are in force. Then for any n 2 32p, log ( the policy R* and value function 9 returned by Algorithm 3 satisfies (.44 with V Vn replaced by
g with probability at least - 3.
This theorem implies the same Ö(S minorize PA -2-2) sample complexity achieve an e-optimal policy and value estimation.
Sketched Proof of Theorems 4.4 and 4.5
Our proof begin with establishing that, under Assump- tion each adversarial transition kernel Q E P consists conditional distributions qa that are absolutely continuous with respect to the nominal distributions Ps.a, with uniform lower bound
1 2m. its Radon-Nikodys derivative. This guarantees that tminorize (Q+) S Of for
all Q E P and II.

---

Algorithm 3 Anchored DR-AMDP
Input: Sample size 2 and divergence D = DKL. or Drx-
For all (s.a) E ES x A, compute the n-sample empirical transition probability Ps.a in Let ç = 1/vv and fixed any anchoring point E S. Construct the anchored empirical uncertainty
set P X (s.a)x8xA P. P...r where P, { (1 E)p + $le D(pl(Da.)) S 63.
Solve the empirical DR average reward Bellman equation
(s) aEA
max (r(s,)) + 2.. (cğ) 03(s)
for a solution pair (0 2
Extract an optimal policy X* II as (s) arg max {r(s,a)+ + + + Li (2)) return R" "'
1
1-p P
01
02:
1-p
1-p
Figure 1: Transition diagram of the hard MDP instance in Wang et al. 37
Next, combining Theorem D.I with Lemma
C.3
we establish that the policy error satisfies
2
Vi v <
max 7, (V (VP)
1 sell
This reduces the analysis of the policy error to bounding the estimation error of the DR Bellman operator evaluated at Vg. As the rewards cancel out, it remains to show that the DR functional applied to Vi satisfy appropriate concentration bound.
To this end, we apply the strong duality for the DR functional, the bound in Lemma C.6 and Bernstein-type inequality to show that for any function V, the deviation satisfies
|r'... (V) Pr.... (V) (V)
áō Span (V)
VripA
with high probability.
Finally, by selecting the parameters 7 7 1/Vn and 7 1/vn, and noting that Span (V Olminorize)) we complete the proof for the KL-divergence case of Theorems 4.4 and 4.5 The argument under the Ja-divergence formulation proceeds in analogous manner.
<
5 Numerical Experiments
In this section, we present numerical experiments to validate our theoretical results. We employ the Hard MDP family introduced in Wang et al. (37), which confirms minimax sample complexity lower bound of {1minorrzee 22) for estimating the average reward to within an è absolute error in the non-robust setting, matching the known upper bound. Our experiments show empirical convergence rate of n 1/22 for both algorithms, validating them as the first algorithms that achieve this rate in the DR-AMDP setting.
Definition 5.1 (Hard MDP Family in Wang al. (37). This family of MDP instances has S 21. A = 2), and reward function r(1,-) = and r(2..) = 0. The controlled transition kernel P is parameterized by with transition diagram given in Figure 1
Observe that under this controlled transition kemel, stationary policies induce the same transition matrix P, Moreover, restricting p (0, | we have pm (1 (1 2p)") ) (1-22))))" 1, where

---

J is the matrix of all 1 and I is the identity matrix. Therefore, Ps. is (m. (1 - (1 2p) -Doeblin
Thus, the minorization time of P is inf m/(1 -p) 2p'
This example clarifies our use of my in Definition 3.3 while my for all p E (0, 1/2]. the
minorization time Eminorize is unbounded, approaching infinity as p goes to O.
Next, evaluate the performance of Algorithm and by analyzing their value approximation errors under both KL and x2 uncertainty sets. x² is special case of fi--divergence with k = 2.
The sub-figures in Figure p samples for every state-action pair. Each data point in the plots corresponds to a single estimate generated by one independent of the corresponding algorithm. Then, we compute the -error between the estimator and the ground-truth average-reward, which is computed via value iteration.
presents the error achieved by the algorithms using total of transition
We then perform regression on data points on each MDP instance with the same parameter p. The plots demonstrate the error converging with rate 1/2 evidenced by the slope of -1/2 in Figure on a log-log scale. We observe a remarkably low variance around the regression line of both gorithms, given that each data point is single independent run of the corresponding algorithm.
2
10a
p-0.1 Islope= 0.06)
101
BJ (slope-
0.51))
0. (slope= 0.171
average error
0-09 (slope-0.500
average error
(olopen-O.50)
10-1
20-1
10-4
10-2
10
number of samples
number of samples
(a) KL-divergence case for Algorithm
(b) 2 -divergence case for Algorithm
10a
0 Islepe-- 3.561
1n
0.1 (slopem-0449)
0-0 (slope--0.48))
0.5 (slope-0.45)
average orxor
0:0 (slope-0..80 0.50)
average ervor
2 BP (8.
10
10
101
10a
10a
10a
10
number of samples
number of samples
(c) KL-divergence case for Algorithm
(d) x² diverregee case for Algorithm
Figure 2: Comparative numerical experiments on (a-b) Algorithm 2 and (c-d) Algorithm 3 for the hard MDP instance, demonstrating e-dependence under different divergence measures.
In addition to these experiment, also perform a larger scale experiment to stress test our algorithm. Due to space limitations, the report provided in Appendix H
6 Conclusion and Future Work
In this work, we study distributionally robust average-reward reinforcement learning under a genera- tive model. We first establish instance-dependen bound of Õ([S) A
1 Miinorize (1 -)) -2g-2 for DR-DMDP. Building on this result, we propose two a priori knowledge- frre algorithms with finite- sample complexity Ö(SS) A E 2). Our work provides novel insights into the relationship between uniform ergodicity and sample complexity under distributional robustness.
While our results rely on the assumptions of uniform ergodicity and constraints on the uncertainty size, we acknowledge these as potential limitations. For future work, we plan to generalize these results to weakly communicating settings and, potentially, multichain MDPs, and investigate broader uncertainty sets (c.g., balls and Wasserstein metrics).
10

---

Acknowledgement
N. Si gratefully acknowledges the support from the Hong Kong Research Grants Council [Theme- based Research Scheme T32-661524-R).
References
[1] Azar, M. G., Munos, R., and Kappen, J. (2013). Minimax pac bounds on the sample complexity of reinforcement learning with a generative model. Machine learning, 91(3):325-349,
[2] Blanchet, J., Lu, M., Zhang, T., and Zhong, (2023). Double pessimism provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36:66845-66859.
[3] Blanchet, J., Lu, M., Zhang, T., and Zhong, H. (2024). Double pessimism is provably efficient for distributionally robust offiin reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36.
[4] Boucheron, S.. Lugosi, G., and Bousquet, O. (2004), Concentration inequalities. In Bousquet, O., von Luxburg, U., and Rätsch, G., editors, Advanced Lectures on Machine Learning: ML Summer Schools 2003, Canberra, Australia, February 14, 2003, Tübingen, Germany, August 4 16, 2003, Revised Lectures, pages 208-240. Springer Berlin Heidelberg.
[5] Chen, Z. (2025). Non-asymptotic guarantees for average-reward q-learning with adaptive stepsizes. arXiv preprint arXiv:2504.18743,
[6] Choi, J., Laibson, D., Madrian, B. C.,, and Metrick, A. (2009). Reinforcement learning and savings behavior. The Journal of finance, (4(())2515-2554
[7] Clavier, P., Shi, L., Le Pennec, E., Mazumdar, E., Wierman, A., and Geist, M. (2024). Near- optimal distributionally robust reinforcement learning with general i_p norms. Advances in Neural Information Processing Systems, 37:1750-1810 1810.
[8] Deng, Y. Bao, F., Kong, Y., Ren, Z., and Dai. Q. (2017). Deep direct reinforcement learning for financial signal representation and trading. IEEE Transactions on Neural Networks and Learning Systems, 28(3):653-66 664.
[9] Duchi, and Namkoong, H. (2021). Learning models with uniform performance via distribu- tionally robust optimization. The Annals of Statistics, 49.
[10] Fruit, R., Pirotta, M., Lazaric, A., and Ortner, R. (2018). Efficient bias-span-constrained exploration-explootatio in reinforcement learning. In International Conference on Machine Learning, pages 1578-1586. PMLR.
[11] González-Trejj Trejo, J., Hernández- Lermandez-Lerma, O., and Hoyos-Reyes, F. (2002). Minimax control of discrete-ting stochastic systems. SIAM Journal on Control and Optimization, 41(5):1626-165,
[12] Grand-Clément, J., Petrik, M., and Vieille, N. (2025). Beyond discounted returns: Robust Markov decision processes with average and Blackwell optimality. crXiv:2312.0361s [math].
[13] Gu, S., Holly, E., Lillicrap, T., and Levine, S. (2017). Deep reinforcement learning for robotic manipulation with asynchronous off-policy updates. In 2017 IEEE international conference robotics and automation (ICRA), pages 3389-3396. IEEE.
[14] Guo, D., Yang, D., Zhang, H., Song, J., Zhang, R., Xu, R., Zhu, Q., Ma, S., Wang, P., Bi, X., al. (2025). Deepseek-rl: Incentivizing reasoning capability in llms via reinforcement learning. arXiv preprint 2rXiv:2501. 12948.
[15] Hu, Z. and Hong, L. J. (2013). Kullback-leible divergence constrained distributionally robust optimization. Available Optimization Online, 1(2):9.
[16] Iyengar, G. (2005). Robust dynamic programming. Mathematics of Operations Research, 30(2):257-280.

---

[17] Jin, Y. and Sidford, A. (2020). Efficiently solving mdps with stochastic mirror descent.
[18) Jin, Y. and Sidford, A. (2021). Towards tight bounds on the sample complexity of average-reward mdps. In International Conference on Machine Learning, pages 5055-5064 PMLR.
[19] Kober, J., Bagnell, A., and Peters, J. (2013). Reinforcement learning in robotics: survey. The International Journal of Robotics Research, 121113:128-11
[20] Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. (2020). Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in neural information processing systems, 13:12811-22872.
[21] Li, Y., Szepesvari, C., and Schuurmans, D. (2009). Learning exercise policies for american options. In Artificial Intelligence and Statistics, pages 352-359.
[22] Liu, Z., Bai, Q., Blanchet, J., Dong, P., Xu, W., Zhou, Z., and Zhou, Z. (2022a). Distributionally Robust SQS-Leaming. In Proceedings of the 39th International Conference Machine Learning. PMLR. ISSN: 2640-3498.
pages
[23] Liu, Z., Bai, Q Blanchet, J., Dong, P., Xu, W., Zhou, Z.., and Zhou, Z. (2022b). Distributionally robust Q-learning. In Chaudhuri, K., Jegelka, S., Song, L.., Szepesvari, C., Niu, G., and Sabato, S., editors, Proceedings of the 39th International Conference on Machine Learning, volume 162 of Proceedings of Machine Learning Research, pages 13623-13643. PMLR.
[24] Ma, X., Liang. Z.. Blanchet, J., Liu, M., Xia, L., Zhang, J., Zhao, Q., and Zhou, Z. (2022). Distributionally robust offline reinforcement learning with linear function approximation. arXiv preprint arXiv:2209. 200.2200006....
[25] Meyn, and Tweedie, R. L. (2012). Markov chains and stochastic stability. Springer Science & Business Media.
[26] Milgrom, P. and Segal, I. (2002). Envelope theorems for arbitrary choice sets. Econometrica, 70(2):583-601.
[27] Nilim, A. and EI Ghaoui, L. (2005). Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798.
[28] Panaganti, K. and Kalathil, D. (2021). Sample complexity of robust reinforcement learning with a generative model.
[29] Panaganti, K. and Kalathil, D. (2022). Sample Complexity of Robust Reinforcement Learning with Generative Model. In Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, pages 9582-9602. PMLR. ISSN: 2640-3498.
[30] Puterman, M. L. (2009). Markov Decision Processes: Discrete Stochastic Dynamic Program- ming. Number v.414 in Wiley Series in Probability and Statistics. John Wiley & Sons, Inc, Hoboken.
[31] Shapiro, A. (2022). Distributionally robust modeling of optimal control. Operations Research Letters, 5065)-611-567.
[32] Shi, L. and Chi. Y. (2024). Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. Journal of Machine Learning Research, 1-
[33] Shi, L., Li. G., Wei, Y., Chen, Y.. Geist, M., and Chi. Y. (2024). The curious price of distributional robustness in reinforcement learning with a generative model.
[34] Si, N., Zhang, F., Zhou, Z., and Blanchet, (2020). Distributionally Robust Policy Evaluation and Learning in Offline Contextual Bandits. In Proceedings of the 37th International Conference on Machine Learning, pages 8884-8894. PMLR. ISSN: 2640-3498.
[35] Sutton, R. and Barto, A. G. (2018). Reinforcement learning An introduction. MIT press.
[36] Wan, Y., Yu, H., and Sutton, S. (2024). On convergence of average-reward q-learning in weakly communicating markov decision processes.
12

---

[37] Wang, S., Blanchet. J., and Glynn, P. (2023a). Optimal Sample Complexity of Reinforcement Learning for Mixing Discounted Markov Decision Processes. arXiv:2302.07477 [es].
[38] Wang, S., Blanchet, J., and Glynn, P. (2024a). Optimal Sample Complexity for Average Reward Markov Decision Processes. arXiv:2310.08833 [cs].
[39] Wang, S. and Si, N. (2025). Bellman optimality of average-reward robust markov decision processes with constant gain.
[40] Wang, S., Si, N., Blanchet, J., and Zhou, Z. (2023b). Finite Sample Complexity Bound for Distributionally Robust Q-learning. In Proceedings of The 26th International Conference Artificial Intelligence and Statistics, pages 3370-3398, PMLR. ISSN: 2640-3498.
[41] Wang. S., Si, N., Blanchet, J., and Zhou, Z. (2023c). A finite sample complexity bound for distributionally robust Q-learning.
[42] Wang. S., Si, N., Blanchet, J., and Zhou, Z. (2024b). On the Foundation of Distributionally Robust Reinforcement Learning. arXiv:2311.0001 [cs].
[43] Wang, S., Si, N., Blanchet, J., and Zhou, Z. (2024c). Sample complexity of variance-reduced distributionally robust qeeaanning Journal of Machine Learning Research, 25(341):1-77.
[44] Wang. Y., Velasquez, A., Atia, G., Prater-Bennete A., and Zou, S. (2023d). Robust average- reward markov decision processes. Proceedings of the AAAI Conference Artificial Intelligence, 37(12):1515-115223
[45] Wang, Y., Velasquez, A., Atia, G., Prater- Bennette,, A., and Zou, S. (2024d). Robust average- reward reinforcement learning. Journal of Artificial Intelligence Research, 80:719-803.
[46] Wang, Y., Velasquez, A., Atia, G. K., Prater-Bennetee A., and Zou, S. (2023e). Model-free robust average-reward reinforcement learning. International Conference on Machine Learning. pages 36431-36469, PMLR.
[47] Wei, J., Wang, X., Schuurmans, D., Bosma, M., Xia, F., Chi, E., Le, V., Zhou, D., al. (2022). Chain-of-thought prompting elicits reasoning in large language models. Advances in neural information processing systems, 35:24824 248377.
[48] Wiesemann, W., Kuhn, D., and Rustem, B. (2013). Robust markov decision processes. Mathe- matics of Operations Research, 38(1):153-183.
[49] Xu, H. and Mannor, S. (2010). Distributionally robust markov decision processes. In NIPS, pages 2505-2513.
[50] Xu, 7.,, Panaganti, K., and Kalathil, D. (2023). Improved sample complexity bounds for distributionally robust reinforcement learning.
[51] Yang. W., Wang, H., Kozuno, T.. Jordan, S. M., and Zhang, Z. (2023). Avoiding model estimation in robust markov decision processes with a generative model.
[52] Yang, W., Zhang, I.,, and Zhang, Z. (2021). Towards theoretical understandings of robust markov decision processes: Sample complexity and asymptotics.
[53] Yang, W.. Zhang, L., and Zhang, Z. (2022). Toward theoretical understandings of robust markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50(6):3223- 3248.
[54] Yu, H., Wan, Y., and Sutton, R. S. (2025). Asynchronous stochastic approximation and average- reward reinforcement learning.
[55] Zhang, S., Zhang, Z., and Maguluri, S. (2021). Finite sample analysis of average-reward td learning and q-learning. In Ranzato, M., Beygelzimer, A., Dauphin, Y., Liang, P., and Vaughan, J. W., editors, Advances Neural Information Processing Systems, volume 34, pages 1230-1242. Curran Associates, Inc
13

---

[56] Zhou, Z., Bai, Q. Zhou, Z., Qiu, L., Blanchet, J., and Glynn, P. (2021). Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3331-3339. PMLR.
[57] Zurek, M. and Chen, Y. (2023). Span-based optimal sample complexity for average reward mdps. arXiv preprint arXiv:2311.1336:
[58] Zurek, M. and Chen, Y. (2024a). The Plug-in Approach for Average- Reward and Discounted MDPs: Optimal Sample Complexity Analysis. arXiv:2410.07616 [es].
[59] Zurek, M. and Chen, Y. (2024b). Span-Based Optimal Sample Complexity for Weakly Commu- nicating and General Average Reward MDPs. arXiv:2403, 1477 [cs].
[60] Zurek, M. and Chen, Y. (2025). Span-agnostic optimal sample complexity and oracle inequalities for average-reward rl. arXiv preprint arXiv:2502. / 1238.
14

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
All the main claims accurately reflect the paper's contribution.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made in the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No or
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
The limitations due to assumptions made for the theoretical guarantee are discussed in Section
Justification:
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
the paper. The authors should use their best
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
15

---

The full set of assumptions is formally stated in Section 4 with rigorous proofs provided in the appendix.
Justification:
Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide a short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification:
The complete algorithmic implementation under the generative model is
provided in Section including detailed pseudo-code. Section 5 specifies all experimental configurations and parameter settings, ensuring full reproducibility of our results.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer this question will not perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is a dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access the model. In general. releasing code and data often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
specific model and empirical evaluation, may
While NeurIPS does not require releasing code, the conference does require submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily a new algorithm, the paper should make it clear how reproduce that algorithm.
(b) If the contribution is primarily
model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reprodueibility may be tricky in some cases, in which authors are welcome to describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (e.g., to registered users), but it should be possible for other researchers have some path reproducing verifying the results.
5. Open access to data and code
16

---

Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
Justification: We have included the complete experimental code in the supplemental materi- als.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurlPS code and data submission guidelines (https://nnis.cc
cublicc/qudees/Codeeubbsss wtwpeeeesuumiisioooooooooooo for more details.
While encourage the release of code and data, understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ wwtps/cccppplgguuuiieeeeae
Stteee///ooSSSeeissSiSica www.ssssiiiggcoooo for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended the paper) is recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Section 5 documents all experimental parameters and implementation details necessary for understanding the results.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [Yes]
Justification: We present statistical significance by fitting the regression line, which is clearly outlined the figures in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
17

---

The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification: Our sample complexity analysis provides statistical guarantees that inde- pendent of computational power considerations, which represent distinct aspect from our theoretical focus.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't make into the paper).
9. Code ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics htt.ghtht...../.ooo....o/ooo///a
Answer: [Yes]
Justification: NeurIPS Code of Ethics has been scrutinised and followed carefully. Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make to preserve anonymity (e.g., if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: This paper establishes the first sample complexity upper bound for DR-AMDP, representing significant advance in distributionally robust reinforcement learning theory.
Guidelines:
18

---

The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning correctly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g.. gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how a system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: There is no such risk.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset used and, possible, include a URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
19

---

If assets are released, the license, copyright information, and terms of use in the thcode has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
package should be provided. For popular datasets, paperswi
latasets.paperssit
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should be provided.
If this information not available online, the authors are encouraged to reach out to the asset's s creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: No such assets are included.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moode as part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not include such kind of experiment.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According to the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals or equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country institution) were obtained?
Answer: [NA]
Justification:
We don't have human participants in the study.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
20

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
16. Declaration of LLM usage
Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: Our core methodology, including algorithm design and theoretical analysis, was developed independently without employing LLM.
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, non-standard components.
Please refer to our LLM for what should or should not be described.
21

---

Appendices
A Notations and Basic Properties
In this section, we present the technical proof for DR-MDPs. Before introducing the theoretical foundations and analyzing related statistical properties, we first define key notations and auxiliary quantities to facilitate subsequent analysis.
For ARMDPs, is useful to consider the span semi-norm Puterman 30 (1, .1" and define:
For vector u E RR, let
Span (u) max (u:) min (u,)
15i 15isd
(A.1)
22 inf ||u celloo
Note that the span semi-norm satisfies the triangle inequality
Span (v) + v2) s Span (ri) + Span(12)
Our analysis relies extensively on two fundamental operators: the DR discounted policy Bellman operator 7, and its optimal counterpart T These operators are defined as follows:
(V) = Σ (s|a) (r(s, a) (V'...()))
(A.2)
(+) aEA
== max {r(s. a) + +
(A.3)
Similarly, we define the empirical DR discounted policy operator ग,. and its optimal counterpart F
(v))s = Σ T(s|a) (r(s. R.. (v))
(A.4)
(v)) = (r(s a) + p (V)
(A.5)
aeA
has been shown that the DR value function Vi is the unique fixed-point of the DR discounted policy operator (A.2). a.k.a. V3 the solution the DR discounted Bellman equation: V
=V,
Iyengar [6], Puterman (30), Nilim and El Ghaoui [27].
We introduce some technical notations. For function S + IR, let
p plu = Σ p())o(s)
Notice that with the above notation, we simplify the expectation as Eplu] [lu]
For probability measure p. E A(S), we say that is absolutely continuous w.r.t. denoted by p & q. if qss) 0 implies that p(s) 0. If p g. define the likelihood ratio, a.k.a. Radon-Nikodym derivative,
((s)
p(s) if {() > else
g
((s)
We say that p and & are mutually absolutely continuous, denoted by p ~ qf << and < p.
For p E A(S). we also define the (o((p) norm of function
R
|| 1. (p) = ess sup |o| max [e[s)]
s:p(s)>0
In the DR sctting, given uncertainty set Pa.a and a function V S - R. we say pd is a worst-case measure if
p" [V] inf p [V] pEP.
22

---

Also, recall Definition 4.1 we define the minimal support probability in measuring the samples required.
S'ES min (s,a :P..a('') >0}
Px min (5.4)ESxA
The sample complexity's dependence on РA emerges from two theoretical requirements. First, accurate estimation of the worst-case transition kernel demands that samples capture the distribution's support, necessitating at least (2(1/>>) /px) samples to ensure all non-zero probability transitions are observed. Second, the perturbed transition kernel needs preserve certain mixing characteristics. This is crucial for to establish uniform high probability bound on the minorization times of the controlled kernels the uncertainty set.
Specifically, we consider the "good events" set Sn,d, as the collection of empirical measures that remain sufficiently close to the nominal transition kernel P. Recall from (4.1 that
1 Σ E =s/ (s.a := ni
For any d > 0 we define,
Pa.a Psça
anallpsa) w
d
(A.6)
Ps.a
(ps.a)
as the relative difference between Ps.a and Ps.a is close up to d. Then, define:
Dn
Ima(Ps,a).
(A.7)
(s,a)E8XA
Theorem A.1 (Bersstein' 's inequality, Theorem 3 in Boucheron et al. (4). Let X1, X2,... X be independent random variables with E[X,] = l and [X; p S M almost surely. Then we have:
M
Var (X)
X,
log
+
log
(A.8)
3n
B
n
B
t=1
with probability at least 1 8.
By Bernstein's inequality, could bound the probability measure of Dnndd
Lemma A.2. When the relative difference d satisfies:
2/S
2/S/2 2
2
2/S|2| A
d 3mp^ log
log
npp
then
P(O S
Proof. Let supp(ps,a) = fs' (s') > 0}. Given n i.idd samples ((1) Staa. , drawn from Ps.a. We define the indicator variables:
(s) 1
5(1) (((()) =s
Note that X X3 (s') ~ (.ennoulli(pp (p..a for all 1 sis n. Then:
1 n
(s')
(s))
n
By Union bound, we have:
P(D)) <
Σ
P
Ps.a Ps.
2d
(x
Ps.a
L (p(()
<
Σ
Σ
P P(Ppsa(s') Ps)) dp).
(A.9)
(s.0)ESxA A A Esuup(pp.a)
p
< Σ
P
X (x)) - -Peals') 2 dpealo))
(s.a)ESxA A' s'Esupp(po.a
23

---

Then, by Bernstein's 's inequality E supp(ps.a). since Epraa
A.8 for any action-state pairs (s, a) E S x A, and next state
[
Ps.a (s'). and [X (s') Ps.al I 1, we have:
||
Var (ar((ernoullippp log
2|S
(s') (s.aas')
log
3n
B
n
3
(A.10)
with probability at least
Thus, let
|
2/S 2|
2 Vpp
2|S| 2 A
d
log
log
3mp,
then, for all as ESA. x A, and s' suppp(psaa:
(s)
1|S|
(5)
2|S|2|A| A
(6))
log
log
3mpk
npp
2/S|2145 ||
(
2|S|2|A|
log
log
(A.11)
B
n1
B
(
2/S|21 A
Var (Bernoulli(p..d
(8)))
log 2|S|
log
+
3n
B
n
Where (i) relies on Var(Bernouli(p..d (8')) = (s.a('')(1 P=aa then we conclude, for all
(s, a) ES x and E supp(ps,a). with probability
T we have:
x (s') Polals))
S ddpe.(l').
(A.
1=1
Then we conclude that:
p
Σ
X (6') Do,a(6) 2 dpaa(s))
I A
And further:
P(
P(Ω 5
Σ
Σ
P
X (8) - pr,a(s)) 2 dppallt)
(x,a)ESxA A o' d'Emupp(p..))
i=1
(A.13)
A
<|S |||
SSPAA
B.
Proved.
Lemma A.3. Let the transition kernel K be uniformly ergodic. If tminorizo (K) co, then there
exists an (m, p) pair, such that:
m p
minorize (K)
Proof. By definition:
Iminorize (K) = inf m/p: min KT kT"(s,)) 2 pib(.) for some E AS))
SES
As Eminorine (K) < 0o, then, there exists a constant C > 0, such that
Eminorize < C.
As the feasible (m, p) p)pair such that:
(m,p)
(m, p) min Km 2 pv(() for some &s E A(S)
sEB
24

---

m < C, then m S Cp I C because p E (0, 1]. we conclude:
p
m E ECC:= 21.2.... |C]] and |C| oc.
Define Cm and Pinaxe (m)
Cm = [p: 3&4 A(S), (8, pb(()}
Pmax (m) sup P
(A.14)
PECm
With this definition, note that
minoriie (K)
inf meC,pECm p
m
We will show that the set Cm is closed, hence Prmax(m)) E Cm is achieved.
Since S finite, ASS) R/S| compact. Consider any sequence {pr} S C. such that pa. - p. Then, there exists 2),, (S), such that
<*"(,,,)) 2 p-)) 8 SES.
As (SS) is compact, sequence { J has subsequence (V }. such that:
Vna + A(S) pointwise.
and corresponding (Pr.) such that Prax - Then for any (8, ES S:
KT (""(,, 8) 2 Pmu Vnn (8'), Vk
We have Pus - p and V'a (8) (ss)):
Pue (nn(ss) p. (55).
Thus:
(m 2 pV((); Vs e
i.c. p E C.. Hence, Cm closed and Pmax (m) E Cm.
Therefore,
Iminorizel (K) inf mEC.pECm p
m min
m
meC Pmax (m*
Since C is finite, there exists m E .1, ,CJ} such that
m
minoriiz (K)
Prnax (Tr²)
Lemma A.4. Suppose the controlled transition kernel P is uniformly ergodic. for all Q P. Ps.a & qs.a holds for all (s,a) E x A, then P is uniformly ergodic.
Proof. Since P is uniformly ergodic, then for all 1I, Eminorize (Px), by Lemma (m,, Px) such that:
A.3 there exists
m
mminorize (Pa).
Pa
For any Q E P and state pair (so, Sma) can be expressed as:
S. the mtep transition probability of Pr. and Qu
p (so, 8m=)
Σ
Pon ) (s)))))))))))) Pam, 1. (5m.)
#1 182 Smig -1
(A.15)
Q (so. sm-)
Σ
(1)9 ... Jome 1,x (Sm.).
$1,82,"
Define:
U(so, mm.)== ((11, 82, ,8 -1) E ST ( 0,0 1
25

---

Since Ps,a < Is,a holds for all (s, a) pairs, we have for any tuple ($1, $2, 5m E U(su sma).
II t=1
(8:)11 > 0,
by absolute continuity, implies:
my
II
(e) 0
Then:
Que (S0: 8me)
E
(11)
qmme intomy- -1) (5me)
Σ
(so, (ss,
aome lallmm -1) (8me)
(8) (81 Smyx (50
Σ
(snnt(ool (81)
Ps ((o.
(or Ps ()))((1)(82))
Poo.=(oo)
(8) Amx (ame-1)) ())0((00
Isma - (Smm (8ma)
P P 11 -1) (8mm)
Pemy -1 (5mm -1)
20(80, Sma))
Σ
Pen (p Poome L.mem 2) (8mm)
(11,8211 Smn 9mm-1) -1)E2((00.mm))
=c(su, Sma))
pm (so, Smm)
(A.16)
where:
mh (es))())) (s++1) >
c(sa: Sme)
min (81, Hm,
II
JeEu
(s,)(ss))
Denote min c(s, O, we conclude:
n (so, Sme) 2 cPm (so. $m,) for all (su, Sm.) E SSXx S.
Since Px satisfies (m,, Pm) Doeblin condition, for some vs E A()). we have:
( 8m,) 2 cPam. (so. 8m.) ) 2 (550) for all (so 8me) E S x S
Q. satisfies (m,, 9x) -Deblin condition where fr cpr. Thus, we concludes for all Q E and E II, Qa satisfies (m², 4x) -Doeblin condition, and:
minorrie (Q=) S mr
< oc for π TE
max minorrize (Qx) < Hell
Finally, we concludes, for all Q E P:
max Iminorize (Qz) xell
P is uniformly ergodic.
Having established the uniformly ergodic property preservation under absolute continuity, we now introduce additional technical tools central to analysis. Our proof strategy fundamentally relies on the span semi-nome norm framework for value functions in DMDPs, the following proposition from Wang al. (37) formalizes this connection:
Proposition A.S (Proposition 6.1 in Wang et al. 33 Suppose Pr satisfies (m,p) -)-Dobllin condition, and VF the value function associate with kernel under policy n, then Span (Vş) S 3m/p
Our core approach involves approximating the DR-AMDP through its DR-DMDP counterpart. To establish this connection rigorously, we require the following fundamental lemma that bridges discounted and average-reward value functions:
26

---

Lemma A.6 (Lemma 1 in Wang et al. [3]). Suppose Px satisfies (Ma ( -Debbinn condition and Eminorize (P²) 00, then:
[1 (1-7)VV - g S 9(1 ((1-7) minorizo (P.)
Proposition A.7 (Restatement of Proposition 3.6). P uniformly ergodic with a uniformly bounded minorization time, then (p) gp constant in S. Moreover, there exists solution (g. v) of u(s) = (u)(s) g" (s) for all s E and any such solution satisfies g(s) = 9p for all s E S. Moreover, the policy x' (s) E arg maxacA {r(s,a) a) + Pp (v)} achieves the optimal average-reward 9p.
Proof. Since P is uniformly ergodic with uniformly bounded minorization time, for any stationary policy x the kernel Qx satisfies an pm PQ. >-Doeblin condition. Then, by Theorem UE in Wang et al. 37.
sup (s,-) PQ+ Ol s 2(1 -PQ+) In/mar
Vn 2
#E8
where PQ+ denotes the unique stationary distribution of QT. Let m = suPQEP, mQ, < 00 and p == infqeP, PQ- > 0. Choose s' S such that PQ² (s') 2 [5]
Let
In In(1/(8|S1)
In p)
Then, for any E S.
0'(s,5)) 2 (s) 4(1 PQ- ----) [J/mol
2
1
1
0.
[S]
2|8
2
Now, for fixed 80 E S, consider the iteration
1+t1 f (w))s
Wt+1 <- 2t+1 (50) e,
where e is the all-ones vector. Combine the fact there exists positive integer such that for all
Q E P and any stationary deterministic policy there exists state s' E S, such that Q (s, > O, applying Theorem Wang et 45), (wa, M)) converges to a solution (g, v) of
(ss) = T (v)(s) g(s).
vs S
which proves existence. Combining Theorem in Wang et al. we have that g(s) = g for all
E S and
x <'(s) E arg max ( r(s,a) a) - I'p.. (v)
aEA
achieves the optimal average reward gp-
B Uniform Ergodicity of the KL Uncertainty Set
In this section, we prove the uniform ergodic properties over P and P under Assumption and [ To achieve this, establish the uniform Doeblin condition through careful analysis of the Radon-Nikodym derivatives between perturbed and nominal transition kernels Is.a and Pa.a- we propose some concepts in facilitating bound the Radon-Nikodym derivative between derivative between perturbed kernel qa and nominal Pa.a-
Proposition B.1. Suppose 8 < 5m? Pr. then for all qs.a E Pasas the Radon-Nikodym derivative satisfies
Is.a Ps.a
2 1
L (p..a)
2mny
holds for all (s, S
27

---

Proof. Consider 9s,a E Pe.as then with KL-constraint, for any s' S, where ps > 0, we have:
5 > DKL (9s,allP..a)
log ?s,a
=9saa
Pe.o
(B.1)
(o,a(s")
1 (s,a(5))
29,a (s') log Ps,a(s')
+ (1 (s))((')) log
1
Ps.a (5')
While the last inequality is derived by log-sum inequality. Let:
x: y
- x
h(x, v) = x log
+ (1 2²) log
1
where y E [px,] - Px]. since:
8h(r, v)
1
Or.2
And hly, v) = 0. we know for any fixed y, h(,, y) convex with respect to on x E (0, y). Since
1(0. log ( log (
PA > 8. By mean value theorem there exists unique
x= ="(y) s.t. h(2" (y), v) 6. Hence, define x" (y) (0. fo h(2, v) 6}. and for any fixed
E (0, 1), if (1))) < ly. then:
8 82 h(2" (v), v) h(ty. v)
1 1 ty
ty logt + (1 - ty) log
1 y
(B.2)
(1)
2 (1 + t log t)y
② (1 t)2
2 y
Here (1) refers to the h(ty, y) expansion at = 0,
lim h(ty, y)/v =1 t + flogt
0 ph(t,. v)
20
0y²
then
h(ty, v) 2 (1 t + 1)g
And (2) refers to the fact that
(1 (1-
t + flgg
2 on t E (0,
The above functional dependence is optimal in polynomial. Hence, when t
2m, we have:
8 82 h(2 2 h (1-- 2my V.u
8my
8m7 PA
However, under the assumption that 8 < P As E [px, 1 - pal, let (s)a(''), we establish the uniform lower bound:
PA. the preceding inequality leads contradiction.
1
a (s') 2
Ps.a(s')
2mw
This inequality holds uniformly across all:
State-action pairs a) E A A
Next states s' supp(ps.o)
28

---

Consequently, the Radon-Nikodym derivative admits uniform lower bound over the uncertainty set Ps.a:
Is,a
inf 0,,0 Pa,o
Ps.a
L (pa.a)
2mv
for all (8,0)
Followed by the boundedness of the Radon-Nikodym derivative, we are able to show the uniform ergodic properties on the uncertainty P
Proposition B.2 (Restatement of the KL case Proposition 4.2). Suppose P is uniformly ergodic, and 8 S 5m Pr then P = PDDK,, 6) is uniformly ergodic and for all Q E P and π E IT:
Iminorize (Q+) S minnoriee
(B.3)
where minoriiee is from Assumption
7
Proof. By Lemma A.3 since P is uniformly ergodic, then there exists (m=, Px) pair, such that:
minorize
P
and
m,
my
Px
For all Q E P, by Proposition
B.1
we have for all (8, a) E S x A,
Is.a
1 2mz
Px.
L (peia)
Then, for all state pairs (so, 8m.)
S x S, consider T we have:
2 (S0, 8m,)
Σ
(so. (81 (11))))))))) ... Qamy ( 1) (sme)
81 1827 1m
Σ
(oo.7(s0)
2ml Ps (o)
2mw
1mm-1
1
Pmmy- 1:50--1, (1 (1 (8
21T
(B.4)
1 my
1
p (so+ Sme)
2m
(1)
Σ pm (su 8mm))
(2) x (5mm)) )
2
The inequality (1) follows from:
11 (1-2))
m 2
m,
2my
2m,
2
(1) holds. The result (2) is derived from the (mz, Px --Doblin condition satisfied by P.. This implies that for every policy II, the perturbed kernel Q, maintains (Mir, - -Doeblln condition. Crucially, this conclusion holds uniformly across all policies in II. Furthermore, the minorization time satisfies:
minorrie (Qx) S
mg Pr 2
< 2f (Px) < 21 minoorzee
where Eminorize max Eminorize (P*) by Assumption
Thus tminorize (Q-)) is uniformly
bounded over Q E P and π E II:
sup max mminorize (Qx) < 24 2iminorize < 00,
QEP sell
P is uniformly ergodic.
29

---

Building upon Proposition B.2 we establish that all perturbed transition kernels Q E P, Qr satifies the (m,, & )-Doeblin condition, and P preserves uniformly ergodic given P is uniformly ergodic with appropriate adversarial power constraint. We further extends the uniform ergodicity to empirical kernels Pa and empirical uncerainty sets P. Although these results not essential for proving main theorems, they provide valuable methodological insights for uniform ergodicity theory:
(i) Offering technical blueprint for extending classical ergodic theory to DR settings
(ii) Laying the theoretical foundation for analyzing uncertainty sets in Markov models
(iii) Opening new research directions for perturbation analysis of ergodic processes.
These findings may prove particularly useful for future studies in DR-MDP and related ares. Lemma B.3, Suppose P is uniformly ergodic. When the sample size:
32m 2 n Z
log
PA
the empirical nominal transition kernel P is also uniformly ergodic with:
minorize (Pa)= I minnorize =ell
max
on the event set D2, and 2mmy
On (nn smy
(0m))))) 2 1-9
Proof. When the sample size satisfies:
32m
||
n
log
PA
then:
2/$
(2 A
2
2/ 2 A
log
+
log
3mpx
8
1
(B.5)
48m2
4mm
<
2my
Then by Bernsteins' inequality and A.2
S
A
2|S|2 A
log
+
log
<
np.
B
1
2my
the probability of the event set 2,, bounded by:
P(0.n. Ω Jmy
) 21
For any fixed as E A. and E 1J the event of On,a(ps,)), we have, for all s' supp(pa.a):
Pa.a (s') 2 (1-
1
Pe.a 2 (s))
Ps.a
2mn
2ml
30

---

Then, by Lemma A.3 for any x E II, there exists a (mx, Px) pair such that
Uminorize PT).
Pri
Consider the transition matrix Ps, we have, for all (s, E S x S:
PmT (s, (s,
Σ
Pa.n(s) D m() (82) Pam- o (sm, (1
(8) (81, -5m-1 (mm-))
my
Σ
Paix(s) (51) Pome 1:m
2mw
($1,921" Pam ee
my
IV IV
pm
(8,
2my
Pm 2
(55))
(B.6)
which implies Pr. satisfies the (M=
Px 2
-Doeblin Condition, and:
minoriza
Pr)) <
minorize Px)) S 2f 2iinnrinee
P.
P is uniformly ergodic with probability 1
B.
Combining Proposition B.2 with Lemma B33 we establish that for all empirical transition kernels Q E P. the minorization time satisfies
minoriie (2)) S minorize
This bound yields the following immediate Corollary. Corollary B.4. Suppose the nominal transition kernel P uniformly ergodic, and 6 S 16mg PA then when the sample complexity
32m 2| Pa
log
the empirical uncertainty set P is uniformly ergodic and satisfies: following holds with probability
1 - B
sup max mmnoriie (xx) S 4fminorize
QEP sell
with probability 1 B.
Proof. First, by Lemma A.3
for any II, there exists (ma Pa) pair such that:
m
miinorize (Pa).
Pr
Then, consider
Pssa(s))
PA min (s.a)EXxA
min ('supp(pe.a)
by Lemma B.3 when
32m
2|S|2|A|
n
log
Px
8
PA
2r
PA
Px. and P satisfies (m Px) DDoeblin condition with probability 1-8 B.
Then, by Proposition
B.2
PA
8m PA
16m
implies for all 2 e P. Qr satisfies (mn,
Ps 4
Doeblin condition, and:
4m
Eminorize (2x)
4fminorize (Pa) S 4t minnorize
Px
P is uniformly ergodic with probability 1 - B.
31

---

Theorem B.5, Under Assumptions
and when 8 -
1
when sample size satisfies:
16m3,
32m 2
log
then.
P is uniformly ergodic, and for any Q E P and π E II, the minorization time of Q
Iminorize (Qx) S minoriae
with probability
P uniformly ergodic and for any 11, the minorization time of Pa:
Iminnriie P*) S 2/minorize-
with probability 1 3.
P uniformly ergodic, and for any Q E P, the minorization time of Qn:
minoriaa (Qx) S 4innorizee
with probability 1
Proof. The result follows by synthesizing three key components:
1. The uniform Doeblin condition for KL-constrained uncertainty set (Proposition B.2
2. The Doeblin condition for empirical transition kernel (Lemma B.3
3. The uniform Doeblin condition for empirical KL.-constrained uncertainty set (Corollary B.4
The combination of 1-3 yields the claimed uniform bounds through careful propagation of the minorization parameters across different uncertainty sets.
C Properties of the Bellman Operator: KL-Case
In this section, we aim to bound the error between DR discounted Bellman operator A.2 and the empirical DR discounted Bellman operator (A.4). In the DR setting, it is challenging to work with the primal formulation in the operators:
Pr. (V) inf P[V].
pEP...
To overcome this difficulty, we instead work with the dual formula by using the strong duality.
Lemma C.1 (Theorem of Hu and Hong [1).. For any as E S x A, let Ps.a be the uncertainty set centered at the nominal transition kernel Ps.a- Then, for any 8 0:
I Pr... (V) =sup { -ad a alogps a20
V/a
(C.I)
for any V S RR
Since the reward and value function are bounded, directly apply Lemma C.1 to the r.h.s of Equation Vg, and (gp, vip) satisfied the following dual form of the optimal DR Bellman equation:
r(s, a) 7 -ar a log {e V2/a 1}
V = max
a
a20
(C.2)
-ad log (=0p/0]]]
max asA
r(s, O3 + sup
a20
32

---

Our analyses are inspired by the approach in Wang et al. [43]. To carry out our analysis, we first introduce some notation. As in Wang al. [43] we denote the KL-dual functional under the nominal transition kernel Ps.a: f( v. == -ad aloggaP Pa.a le VVVa
(C.3)
then
Tp, (V) sup f (Ps,as V,a).
az0
At the same time, define the help measures as:
(t,a()) lis.0 + (1 - 1)p
Aps,a Pa.a Pa,a
(C.4)
Is.a (t, (Ps,att) (t), V.
By Definition A.7 it is clear when d < 1, Ps.a (t) Ps,a holds for all (s,a) E A and f E [0, on Qn
We first introduce the auxiliary lemma that will be used useful in facilitating the later proof:
Lemma C.2. For any (s) S A, and value function V1, V/2 E R have:
P.. (Vi) - P... (V2) < | - V/2l
Proof. For any E Pe... have:
1 [ii S a [V2] [V - V2]
Since q is probability measure, by Hölder's inequality with |ql for all g Pa,a
a ( - [3] S I1 V2llao
Thus:
[i] Σq [2
+ 1 V2ll.0
for all
E Ps.a
inf
[V]] Sq [V2]
1| V2ll
for all q s.a
pEP.
inf p [V[] < inf p [V2]] + V V2
(C.5)
pEP... A.o
PEP,..
Pp... (V1) ST P. (V/2 + +I[ - 122l
P.,, (V1) - Tp... a (V/2 $ + 1| - 1/2l20
Switch V1 and V22 we have:
Pr. (V2) - TP... (Vi) S 1 V/2la
Then conclude:
Tr, (Vi) - -Pp, (V2) $ 1 V
Proved
Then, we bound the error of empirical value function Vi and the true value function Vi with respect the the Bellman operators (A.3) and (D.77) by the following lemma:
Lemma C.3, Let n be any policy, and V and V are the fixed points to the DR Bellman Operators
A.2 and A.44, where V = T (VF) and V = 7. (VZ), then we have:
vg V3
-
33

---

Proof. DR Bellman operators T and ग.. are y-contractions, i.e., for any two value functions
Vi, V2 R we have:
(1)) - - (V2)
Σ
+ r(s,a) ((s,.)) -IP.. (V2))
max sES
max #ES
Σ
((ass) (T'... Tr (V2))
aEA
(
S [[ V2ll
(0) Y | - V2
-V)) (V2)
(C.6)
where the inequalities (z), (ii) are concluded by Lemma C.2
Thus, we have:
V
77 (V3)
T (V (VB) -V))
(C.7)
7. (VB) - (VØ)
+ (vイ) - T7
<> Vz V || + 75 - (T3)
and
V3
1 - (V3) -,
(C.8)
Proved.
Next, we aim to bound the approximation error (V3V))TT1
Previous approaches relies
on estimating via KL-dual functionals with optimal multipliers a E [0, 8 (1 - -) While this yields bound of Õ(8- 1 y)
y)- )) it ultimately leads to suboptimal O(1/=*) sample complexity.
Building on Wang et al. [43]'s s breakthrough in achieving õ-independent bounds through KL-dual analysis, make two key advances:
1. Targeted Value Function Analysis: Instead of considering the entire value function space 0. (1 (1.11-)--11 -11s we restrict analysis to V specifically. This allows us to replace the
(1 (- dependence with the span semi-norm of V/A.
2. Error Rate Improvement: Combining the Span (VF) dependent error bound with Propo-
sition A.5
we improve the bound from Ō (6- 10 -)) to:
(バ(²)) - (VB δ (Iminorize (P+)
As shown in Section
D these refinements ultimately yield the improved smaple complexity of
Ö([S]| A f Liiinnnieee Lemma C.4. Let Pi, P2,P A(S) s.I. P1,P2 < p. Define A == Pr P2- Then, for any V - I and (0,
V/a
3
A
sup a
Span (NV'
(C.9)
a20
p
V/a
2
p
(p)
Proof. First note that for any K E P. we have:
A E V/a
- (V-a)/a
V/a
e kk-a
34

---

Hence, if we shift the value function V' = V -inffes V(s) then, is equivalent show:
Sp)n(V) where | = Span (V),
A V/a
A
V'ja"
sup a a20 P
sup a+) a20
- 3
1
Pe-v
V/a
/o/
(p)
Thus, only need show
A V-Va
V/o
A P (p)
sup
S 3
|
p V/a
a20
i.e. the bound with respect to Lo of V and replace I1-1l by SSpan WLOG, we assume infses V(s) 0. Then for fixed e >> 0, decompose the domain of [o,c|IVlllo U
(c|IVllo 20) = K1 U K2, we have:
le V/a]
A V/a V/a
sup a² A ee [e-via] V/a
sup a
p pe V/a = max
sup a aEKi
a20
p e
ack;
p
e V/a
(C.10)
max (Ki(c), K2(c)}
For Ki(c), we have
A
A ccllVllz
(i(c)
< sup acK;
S
<c
p (,x
For K2(c), the condition is more complicated
K2(c)= = sup a II ack2
(V+
As A [1|=00 0:
a A (V+IVII A aod (e-M4HVVl2)aa1)
Then:
aa (e (-(V+IVVI
p 1 (++1 V 1/0
p p (ee((++lV (V+IVV
1
( (6-VHHVVWW/aa11)
dA
p (V [V+IVII))/a
P
dp
a
aa (e (V++IVIVV 1/a
(C.11)
(r--(V-IV )/a
(x
a (e (e-V+IVIL->--
A
(V+IVII))
p (M()))
(e- (1
Consider the first term
denote
(V+1V1
a D// 1)
<a² (211V1la/a
é -V++V
(C.12)
:=f(a)
Taking the derivative f(a), we have:
0f(a)
=ja²-1 (22VVll -1) + a
(221V (-
2 211V
da
a²
(C.13)
=jat-1 ((1 (1-211V) 2 (iVila/a-1)
ja
35

---

replace t 2||V and c= j V p-1
0f(a)
c
((1-)))--11
(C.14)
da
1-1
and when j E 20, 1]
d (1-9) c
-11))(11)))) (1- e 0
(C.15)
dt 1J11
combine the fact: a = 0. It implies Oaf(a) S O, and further f(a) is decreasing with respect a. Therefore, over K2:
f(a) s ((ellll s (c (V (2) for all a E K2(c)
Combine the previous result, we get the result where:
K2(c) = (c (cIIV (216-
p (m(())
Then:
sup a
A V/o
max [c
A p
(c (c (021-
A
p p V/a
(x)
p (x)
In select c = 2n the minimax optimality is achieved, we have:
A e
V/a V/a
A
sup &
S 3
IIVE
f[e-v/
P (x)
As the the above result is invariant under the constant shift of V, let V' = V -inf.ess V(s) Span(V) have:
A V'
A Ve-Vaal
V/al
3 2
sup d
sup a20
S
Span (V)'
p e
V/a
e e-V
az0
(p)
Proved
Lemma C.5. For any value function V with span semi-norm Span (V):
Span (V) 0, the optimal Lagrange multiplier a = 0, and for all as E Pa la is worst-case measure.
Span (V) 0, the optimal Lagrange multiplier a* 0, and:
(),(() Ps.a [e-V/a"
V/a" 1[:3]
(C.16)
Pa.a [e- V/a*)
is worst-case measure
Proof. From Si et al. 34], for optimal Lagrange multiplier a", it sufficient to consider a e [0, 8-1 I| (p..))))) When Span (V) = 0, it implies V is a constant over supp(ps.a) and:
f(r V, ad a log Ps.e
VVaa
V/a
(C.17)
ad + | (x(,a)))
Thus, a( V,a*) =up (p V, a" 0, and for all Ja.a Pa,ex qa,a is worst-case measure since V is constant function supp(ps.a).
When Span (V) * 0, a" satisfies:
f(pea V,a")=
sup V
f(Peas V,a)
36

---

As a" is the optimal Lagrange multiplier and is differentiable, consider the first-order partial derivative with respect a:
af(psa: V,a) = = Peo e V/a da
log Ps.a [e-V/a] Ps.a e V/a
and lima- O.f > As a" the optimal multiplier, 0,f ( V, V.a)a=-- = 0, and
a eVaa"
V
Ps,a
llog Ps,a [c (e-vja" =
[ VVV
Ps.a
Further:
8 sPs,a V,a)
Psá V2e-V/a
+ Pz.a [Ve VV-22
da
P'Pa, C V/o
a (e-Vaa]
(C.18)
Ps.a [ V/a] Ps.a [e-v/a]
Ps.a [Ve VVeV//
Psça [e V/al 2
Ps.a (e V/a]2
Define the measure:
Ps.a [e V/00 1{:
Pr (-)
Ps.a (e- C-V/a"]
Thus:
0² f(s V,a) da²
Varp: (V)
50 Thus f(e..a V, a) is concave for a > O. a is the unique optimal multiplier where a > 0 and P..e satisfies:
(C.19)
a
Pa.a
DKL. (a'.Vaaalaaaa =v',a
log
Ps.a
V
V/a*
22,a
log Ps.e
a
(C.20)
VV/a"
Ps.a
c VVVa
log Ps.a
V/aa
Pa.a
Therefore, we show Pr is worst-case measure.
Lemma C.6. Let Ps.a the nominal transition kernel, and Ps.a be the empirical transition kernel, then the below inequality holds:
sup a20
f( V,a) suu f(po.a. v,a) s 3d Span (V),
(C.21)
a20
on Dn,di when d <
Proof. Recall the general KL-dual functional under the probability measure Ps.a. value function V. and parameter a is:
f(P.,, V.a) aalogp Ps.a
[e -v/a/a -a8
V/a
Then:
sup fP V. - sup f(Pe.a v.a) a20
S Ssup If V,a) f(Da.. V,a)) a20
(C.22)
a20
Further, consider the difference of fs..aVia
fpra.Vall:
(f a.) f(p.aa V,a)]
19,,a (1, (0,a0,aa))
(t,
for some T E [0,1]
Øl
1=
(C.23)
(ssa Ps.a) (
[e-V/o
=a
(Ps,(TT) [e-V/a]
37

---

On 2ndd where d S 2, we have for all T E =0, 1], and s' E supp(ps.a):
(s,a(T(())) (s') + (1 (b))) 2 20sa(66)
(C.24)
Apply Lemma C.4 we have:
(Po. Pa.a [e V/a (De,a(T)) VVaaj
sup [f(Ps,a V,a) f(D V,a) = sup o20
a20
Ps.a Psãa
Span (V)
Ps.a
L (pr.))
(C.25)
(9)
3Span (V)
Pa.o
Pa.a
Ps.a
[
S 3d Span (V)
Where inequality (i) is by Lemma C.4 and the inequality (ii) is by Equation (C.24) The difference of KL-dual functional is bounded by:
sup az0
(f v.)) f(Ps,a V,a)) 3d Span (V)
on Ind when d < n
Lemma C.7. When 2 32p log (og(()//((A//B))) then for any E II, the boo- -rror the emprical DR Bellman operator T and the DR Bellman operator T.y can be bounded by:
8 ra
2|
(VB) - T (V7) S minoriza (Pa)
log
with probability 1 B, where Pa, the transition kernel induced by controlled transition kernel P and policy и.
Proof. First, by Bernstein's inequality, when:
32
||S|
log
P^
Then:
Po,a(s') (s))
1
2
A
2/8/
log
log
Ps.a
3
74p^
B
2|S|2|A)
(C.26)
log
3
2
with probability at least - 3 for all (s,a)
S x A and s' E supp(ps.a). thus, let
8
2|
d
log 3
np
then d 1. and:
P(In.)) > 1 - 3.
38

---

Then we consider the difference of the Bellman operators for particular value function Vp, on Indd
(VP) - T5
Σ T(als) (r(s,a) + p.. (VF)
Σ T(als) (r(s,a) + p..
max SEB
20
REAA
Sy max
T3 (VP) -Pp,, (V3)
(x
sup f(Ps,as up, - [(s,,a op)
max (s,0)E8XA
a20
a20
3d Span (VB)
(C.27)
on Qn.d. where (i) is derived by C.6 Combine Proposition A.5 and Lemma A.3
when Pr is
(m Pw DDoeblin with my /P= minorize (Px), and Span (VF) S /ma/Pa thus, we have:
(VB) (VB)
9m
8
log
A|
(C.28)
Px
npn
B
withe probability 1 - B. Let:
32
||
n 2
log
8
Then with probability at least 1 - B, for any π E II, the following bound holds:
8
2/S|21 ||
(v3)
9f minorize (Pa)
(Pa))
log
(C.29)
3
Proved.
D Sample Complexity Analysis: KL Uncertainty Set
In this section, we prove the sample complexity bound as shown in Theorem 4.4 and Theorem 4.5
D.I DR-DMDP under KL Uncertainty Set
Lemma D.1. Let म arg max V then the following inequality holds:
0 V V
max mEll
V
Proof. The left direction of the inequality is trivial. For the right inequality, we have:
Vp
V/
= max
V/2
V
wlll
max
V
max VT +
V7
V
Tell
well P
P
(D.1)
max V
MENl
max Tell
+
P
V
<2 max well
Proved.
Theorem D.2 (Restatement of Theorem 4.3 for any 2 32p log(2]s|²) the policy मt and value function returned by Algorithm satisfies:
Suppose Assumptions and 2 Dare in force. Then,
m2mmori
2
2 A
0 V V <
log
apn
B
(D.2)
|/ Vil
364
2
2/S/ A
log
apn
39

---

with probability 1 - B. Consequently, the sample complexity to achieve E-optimal policy and value function with probability 1 is:
n n c. | minorize log
2|S| (1-7) PE
where 2- 722 and 2 36 respectively.
Proof. For any π as V is the fixed point to the DR Bellman operator (.2 T, (VP), by Lemma C.7 when:
where VØ
32
||
n 2 log
8
then, with probability 1 - B, for all π E II:
V
V$
T7. (vz) - (V3
$
20
< sup QEP
(V - T7, (V2)
(
9t minoriaa (Qx)
8
2|S| A
(D.3)
$ sup
log
QEP
1-7
прд
3
(i) minoniii
2| B
log
1-7
where (1) derived by Lemma C.3
and (ii) relies on Proposition B.2 where minorriee (Qx) is
uniformly bounded for all Q E P and
E 1I. We conclude, when
32 log n
A|
8
have
S Vp
V
22
max
V VT
#ell
2
<
max #Ell
T (VB)
T (VP)
1
(D.4)
mimooriz
2
2/ A
log
?
8
with probability 1 3.
Since for value function evaluation:
V
- V
< max well
VT
V
00
(D.5)
minorizr
2
2 A
log
1-y
3
holds for the same sample complexity condition and high probability guarantee, we prove the Theorem.
Remark D.3. In the proof of Theorem D.2 we establish high probability guarantee for the uni-
form value function approximation enror: max V V
< [Otminorize - 1/2).
Crucially, this uniform bound simultancously controls both:
The policy gap: V
V
The value function approximation error:
V; Vi
40

---

via the relationship:
Both errors I
max Tell
V
VP
This simultaneous control ensures the final error guaranee in (D.2) holds without requiring additional division of the confidence parameter B. The key observation is that uniform concentration bound on value functions automatically propagates to both policy selection and value estimation errors.
D.2 Reduction DR-DMDP Approach under KL Uncertainty Set
Theorem D.4 (Restatement Theorem
Suppose Assumption ! and in force, then for any
32
||
log
PA
B
the policy ft and value function
returned by Algorithm
satisfies:
2
2/S|
A
0 97
9p
996t
minorize
log
npA
|8
(D.6)
V
2
1|
9p
248mminooiie
log
Vn
npx
3
with probability 3. Hence, the sample complexity of achieving E-error in either optimal policy or value estimation is
|
minorize
log
PAE2
8
where 2- 992,, and 2 482 repectively.
Proof. Initially, let
VP =T (Vp)
V =T v/ (V%)
(D.7)
VΦ = (VT)
V - (V
(D.8)
For the 7"' policy evaluation, we have:
0 S.p
gp
V
V
P
-0-
Vn
n
nn
vn
Vn
9p
(D.9)
V
V
9p
V
P
V
+
V
+
9p
Then, by definition:
V
V
V$
90p
max 9o
max
max mEll
#EIl
#ell
(D.10)
3 Vp
max V
max V rell
max Tell
#ell
Then, have:
0 S 90
g0
< 2 max
Jp
+ 2 max sell
V3
(D.11)
xell
n
For
value evaluation, we have:
V
V
gp
Vn
T
V
V
V
P
4p
(D.12)
Vn
Vn
Vn
8
Vx
V
+
90
P
Vn
41

---

Combine D.10
we have:
V
VØ Vn
g6
mAx
9p
max nell
V - 1/3 vn
Vn
xell
Therefore, we have:
V
1
0 S 9p
9p
4'
2
max
9p
+ 2 max xell
1/ Vp
#ell
Vn1
vn
20
(D.13)
V v2
VB
9p
max
max T
V
- Vp
Vn
We consider the error bound term by term, for simplicity, we denote Step 1: bounding 1 (1-2) llac
7,
When S (3(s) (1 (s). then, for any > 0, there exist an P. E P such that
>)) + & (1
and hence:
0 S ss( (1 - (3}
I inf 95(s) (1 - (s)
QEP
(D.14)
$ 9h. (s) (1 - V/, (s) +E
S sup 9 - (1 - // +
QEP
Taking limit as e + 0, we conclude when 0 5 (8) (1 (B):
0 S gs) - (1 V3 S sup
9 V/ll
QEP
Similarly, when 0 2 (8) (1 - V3 (s), let consider Pe such that:
g + (s)
then we have:
2 (5()) (1 (s)
2 9p (8) E inf (1 (z)
QEP
(D.15)
2 fp (8) (1 (s) -
2 sup (1 V) - gōll -
QEP
Taking limit as e + O, we conclude when 02 (s) - (1 ());
0 S (1 (1-) (5)
S sup 1g0 - - (1
QEP
And thus:
(s)(s)) - -1- (V))))B((s) sup QEP
9 (1 V/ vo for all SES
And further:
lg (1- S sup |g - (1 -1- 2
(D.16)
QEP
Then, by Lemma A.6 over the nominal uncertainty set
l (1- (1-
< sup QEP
_ - (1 V)
< 9(1 - 7) sup Imiuorize (Qr) QEP
(D.17)
By Proposition B.2 minorize
(Qx) is uniformly bounded on P x 11 by 2t mininrrzees we have:
11gp (1 1) 1l < sup 9(1 - miinorizee (Qx) S 18(1 tiinoizeee
QEP
As the above inequality holds for all π E II, further, plug back = we conclude that:
18 1/mmoiiize
max xell
S
(D.18)
7
vn
42

---

with probability 1.
Step 2: bounding
1/ 7
By the definition of 1 and Vp. we know V and V are the solutions to the DR Bellman equations / V = (V)). v =T,' TT, (V thus, by Lemma C.3
(v5)) T, 7,
(D.19)
Combine Lemma C.7 and Proposition
4.2
we have when:
32
2
n
log
PΛ
8
then, with probability at least
B, for all II.
V
V
(V T," (V
(D.20)
18t minorize
8 'pa
2|
log
Further, with the choice of y 1- 1 Vn
we conclude when
32 Px
log
2|8
then:
1
8
2
8 A
max Fell
V
184 186minoriee
log
V
8
with probability 1 - B. Step combining the previous results. For policy evaluation:
9r
9p
7 22 max nEll
9P
2 max
1 V/
sell
36t minorize
2|A
+ minoinee
log
Vn
8
(D.21)
36t minorize
2 2
1+
log
Vn
PA
2
96t minorize
log
B
wth probabilityy 1-3. Where the last inequality uses the trival bounds where PA S 3. and |S), 2 1.
2 mminoriz
Thus, when n Px6
the policy 2* satisfies:
2
2
0 gp
minooii
log
B
(D.22)
2/S|2|A
gp
minorizo
log пp 3
simultaneously with probability optimal policy value value estimation is:
B. The sample complexity of achieving an e-error in either
#2 n minorize log
2|S|2|A|
/
where 2- 962 and 2 2 repectively. Recall the minorization time is equivalent to mixing time, the total sample used is:
A|| minorisa log |
/ | A ( P
((5)
N A| O
Ō
c
PAE2
Proved.
Remark D.5. Notice the error guarantee relies on the relative error between Ps,a and Ps.a is less
equal thant 2, hence P(Le (0 < 3, thus, the lowerbound of n is ÿ (1/px).
43

---

D.3 Anchored DR-AMDP Approach under KL Uncertainty Set
This section analyzes the anchored algorithm and establishes a sample complexity upper bound for the anchored DR-AMDP Algorithmm3] Key to our analysis is the insight that the anchored DR-AMDP can where is the anchoring parameter.
be identified with DR- DR-DMDP with discount factor y
Fix 80 E S, recall that
Pa {(1-5)p+
+ Ele E Pa.a) and p=
X
P P.par
(8,0)xSxA
We consider the anchored DR average Bellman equation
(()) max { [((. a) + +I',,. (u)) 9(6) Vs E.S
(D.23)
Lemma D.6. Assume that P is uniformly ergodic. Ler Vi be the solution to the DR Bellman equation with discounted parameter y E
( = max (r(s,
(..
Ys E S.
aEA
Then, (g. v) = (so), Vi²) (.23). Moreover, for all solution pairs (g', v') to (D.23), g' (s)(
) is a solution pair to the anchored DR average Bellman equation
Proof. As P is uniformly ergodic, for all Q E P. Q is uniformly ergodic. Thus, for Q E P, by Lemma A.3 for any π E IT there exists an (mz, Pn) pair such that my minorize (Qx). As for all
Q E P. n E II, and (So: mm+) E S x S: 2 (so, 8m-) ((1 -)1-E)Q. + )1e my (50, 3ma)
(D.24)
-) Q.7 8m,,
Since Qx satisfies (m,, Pn --oeblin condition, it follows that Q satifies (m*,, - p=)-eeb condition. Consequently, Q is uniformly ergodic, which further implies that P is uniformly ergodic. Given the uniform ergodicity of P. by Proposition 3.6 (g.0) v) is a pair of the solutions to the
anchored DR average Bellman equation:
v(s) = max (((s,a) + Fg, (v) g(s) s
A
Then = 9 is unique. Next, we show (g. = (5V2(so), V2)) is the solution to the anchored DR average Bellman equation:
max {r(s, a) + +I'(()) g(())
max {r(s, a) +Tz(V))} - {V7(5 eEA
as,,a) + inf ((1 E)p +gle [V}]
-VV)(so)
aEA
PEP
(D.25)
((s,a) + -) inf p [Vp] + +VV((50) pEP..a
(s)
aEA
(r(s, +(1 P.. (V²))
max aEA
(s) Thus, show (sVp(su). Vi)) is pair of solution to Equation (D.23), combine Lemma 3.6 know g = (Vp is unique, where Vp is the optimal value function of DR discounted Bellman operator A.3 with parameter -
The above Lemma D.6/holds for any uncertainty set P, hence (g. v) = (5V) V3) and (g, v) = (se). Vi)) are the solutions to the anchored DR average Bellman equation (D.26) and empirical anchored DR average Bellman equation (D.27) respectively:
u(s) = max a
((s,a)) + T.. (v).(o) g(s) E
(D.26)
u(s) max A
((ss () + + E,. (v)
g(s) vs
(D.27)
Similarly, the equivalent also holds for the DR policy equations:
44

---

Lemma D.7. Pf is uniformly ergodic, let Vp be the solution to the DR discounted policy equation with y
V Σ
(r(s)) + (1- ()-E)Ip,, (VF)) As S
aEA
Then,
(g.0) v) = (CV7 V2)
(D.28)
is solution pair of the anchored DR average policy Bellman equation:
v(s) = Σ T(als) (r(ss + (T,.
(2))
g(s) vs E S.
(D.29)
oEA
Moreover, for all solution pairs (g', D.29). g' (sV)
Proof. The proof is similar with Lemma D.6. As g = 9p is unique, only need show solution pair:
D.28 is
Σ T(ass) ((s.a)+Tp..d (v)) g(s)
aEA
Σ t(als) ((() a) + +1p (VT) - -5V (50)
aEA
Σ T(als) (r(s,a) a) + +(1 -)][' P.., (Vz)) Σ -(aab)VV5(s))-51 - (VV
(D.30)
aEA
aEA
Σ
T(als) (r(s, a) + (1- - P)I' (V5))
aEA
=V-
Thus, by Theorem 6 in Wang et al.
44 we show (EV7(s0), VF) is pair of solution to Equation
D.29 where g = <VØ (so) is unique.
With these auxiliary result, present proof to the following main result.
Theorem D.8 (Restatement of Theorem 4.5).
Suppose Algorithm 3s in force. Then for any:
32
1|
log
P^
B
The oulput policy 7" and approximate average value function o satisfies:
2
2 A
0 9p
9p
996 minoriie
log
8
(D.31)
2
2/S|2 A
1/2 gp
< <88 <48mminories
log πpa
3. Hence, the sample complexity of achieving an E-error both optimal policy and value estimation is
with probability least
c. 12 12
2/S|2|
minorize log 2xE2
where 2- 262 and 2 482 repectively.
Proof. For policy evaluation, consider policy ** returned by Algorithm 3 by Lemma 3.6 we know #* is an optimal policy for the anchored empirical uncertainty set P.
q' = 0
45

---

further
9p
9p
5"
max 90
9p
T"
xEll
max n-
xell
9p
wlll P
9p
(D.32)
2 max tlll
9 9p
For average value function evaluation sz.
93 11a
0/2
= max FEll
02
- max 9p
tEll
(D.33)
- max xell
0
Then, we analysis 9 97
by Lemma
D.7 we know 03 = <V (Sq), then:
96 2
[V (80) (s) + EV (50) 9
(D.34)
(V CVZ (80) + 1IEVE - 96 1la
Since for all Q P, by Proposition B.1 we know Ps.a < qs.a for all (8, a) E SSX A. Then by
Lemma A.4 for all Q P. Q is also uniformly ergodic, and Span (zp) = 0. Thus:
| 06
<E
V
+ 1EVE
go (80)
(D.35)
<
V
V
gp oo
Vx by Lemma C.3 and Lemma C.7 1 8, for all क E Il:
With the choice 1
when
2
32 PA
log
IA
with probability
St minorize
8
2 2
A
9
g
minorize
log
vn
72p
B
18t minorize
8 log
2
2
A
1
Vn
PΛ
(D.36)
2 S 8
< 2fmminrrie
log
2
48 4immoiio
log
711^
8
Thus, combine the results:
2 log
2/ A
Jp g0 S max
03 - y3
966
(D.37)
rell
3
with probability 1 3. And when:
2- 2z
2/S | 2
minoriee log s
we get:
0 0 oソ
*' S
with probability Simultaneously.
3, R* is an a-optimal policy.
2/ A
max
48 481 481minorize
log
(D.38)
np^
B
46

---

with probability 1 - 3. And when:
2-48 48"8
4 minoriie
2|S/ B
log
PA
get:
-
E
with probability 1 - 8, op is an e-optimal value function.
E
Uniform Ergodicity of the f& Uncertainty Set
In this section, prove the technique results similar in fx fi-divergence constraints given the Assump- tion I and 2 Like what we have in KL-diverence, we first bound the Nidon-Nikodym derivative between perturbed kernel as,a and nominal Ps.a-
Lemma E.1. Suppose 8 S
max (8.4k88,kmo PA. then for all qs,a E Pa the Radon-Nikodyne derivative
of 4s,a satisfies:
Is.a
2 1
Ps.a
L (pr.a)
2mny
for all (8,a) ESXA
Proof. We prove the Lemma by contradiction. For any (s, E S A, consider qa,a E Pa.a suppose there exists s' E S, such that
Is.a (s') <1
r:=
Ps.a
2mv
Then for any qs.a E Pa.as we have:
1s.a
Día Sra,aallloo. = Psça fkx
Pssa
y (5') Po,a(o')
(E.1)
2 Jú
Ps.a
2 fk (r)
Define the helper function ga((1) = b 1)? when A: 2 2, we have:
1/ kt 1
[k(1) (1)
k(k - 1) 1 1)2
* kk + k -1 (k -t)(t2 + 1)
k(k + 1)
(E.2)
kt +
1 - (k - 1)(² + 2(k - 1)1 (k
k(k - 1)
2 (k: - 1)t² + (l: 2)t
k(k
The nominator is
(t* (k 1)t + (k 2)),
let
(t(t) = kk - (I: 1)t + (k- 2).
Then:
(t)
(I: k22 (h: 1) s 0 on te [0
(E.3)
dt
(t)
(t)
and
dt < 0
(E.4)
dt
1=1
47

---

We conclude that (t) 2 on t E [0, 1], and thus:
(x(1) mb(1) = (t)
2 0
k:Ak: 1)
Hence, when
<1
2may
1
8
fx(r)) 2 (r) >g 1 2ml
k
Am
4km
P^
(E.5)
Pp
However, the above incquality contradict to (E.1) where fi(())p 5. For the case when E (1, consider the function:
fx(t)
th kt + k
hx(1) (1 11- k(k 1)(t -1)2
(E.6)
is easy to see that lim hx(11) 2. and hsx(0) x. Hence (0) 2 lim lz((1). Then, the derivative:
(t)
(htth11 - 1) - 1)2 (1t kt + 1)2k ()(1-1) -1)
df
k2 2) - 1)
(E.7)
(k: - 2)th ktth + kt - 1 +
k(k 1)(t - 1)3
Denote the nominator as:
(x(t) = (k 2) kth kt +
then we have:
(t)(t)
=k(k - 2) x- -1 kck 1)th + k
dt
d² qu =k(k () 2)t -2 k(k - 1)(k - 2)²
(E.8)
dt²
=k(k 1)(k 2)(* -3 (1-11)
When 1 < k < 2, the second order derivative d (1) > 0 on l E (0, 1). dgx(1) is monotone increasing, and degx: (1),==1 0, have deqx (1) on / (0, 1], which sequentially implies 4% (t) is monotone decreasing,
(t) 2 (1) = 0 on e [0
And further (t) s 0, (t) monotone decreasing from 1/2 to Thus, for < 2:
(x(() 2 fx(()) 2 ( 1)2
1
(F.9)
- 1)2 2
2
Combine the previous results, have, when
<
2mv
fx(r) 2 (r 1)2 >
2 4m 2
2
which contradict to
82 Dsg (1e.allPsaa) Ps.a) fx(r)p
Consequently, we prove, for all E (1, oc) when S (onxx8_,u6m@) PA. the Radon-Nikodym
derivative of between any qs.a E Peo and Ps.a satisfies:
Js.a
1 2m
2 1
Ps.a L (ps.a)
Proved.
48

---

Further, similiar with Proposition B.2 we have when å I 4max(2,k)m$ PA. P is uniformly ergodic with:
sup max minorize (Qx) S minoriiee QEP sell
(E.10)
The idea is as same as the KL-divergence case, as under Assumption 2 the Radon-Nikode derivative uniform bounded by 2mm P, thus, have for any Q E P. Q (8, 8') pmn (s, 8') for all (s, 5') E S. Proposition F.2 (Restatement of Proposition 4.2 Suppose P is uniformly ergodic, and å s
max(88,4kmg PA then P fe, 8) is uniformly ergodic for all Q P, and π E 11:
Eminorize (Qn) - minorrize
(E.11)
where Iminorine is from Assumption 7
Proof. By Lemma A.3 since P is uniformly ergodic, then there exists an (Mir, Px) pair, such that: (Px) and
ma
minorize
My S my
Px
For all Q E P. by Lemma
E.1
we have for all (s, a) E SSSA A,
Ps.a
L (pr.a)
2mnyy
Then, for all state pairs (so, 8m.)
E S x S, consider Q we have:
Q (sg: 5mm)
Σ
(80.)
-mm-1
(E.12)
Px 2
(5mm))
The proof of the above inequality is the same in B.4). This implies that for every policy TT, Pa. 2 DDoeblin condition. Furthermore, the minorization
the perturbed kernel Q~ maintains (mz, time satisfies:
t minorrie (Qx) S
< 2f minurize (Px) S
2iminorize:
Cr 2
where iminorize EIT minoriiee (P*) by Assumption bounded over Q E P and क E II:
Thus lminorize (Qz)) is uniformly
sup max maxxmminoried (Qx) < 2t minorrie 00,
QEP rell
P is uniformly ergodic.
We furthr establish uniform ergodicity properties for both the empirical transition kernel P and its empirical uncertainty set P. serving a probabilistic counterpart to Theorem B.5 Whle not directly impacting our sample complexity results, this analysis reveals that when the robustness parameter satisfies:
8 max {16, 8k) m PA
both P and P. maintain uniform ergodicity with high probability.
Corollary E.3. Under Assumption 7 and 8 max(16.56 my PA when the smaple size satisfies:
n > 32m?
log 2/S/2AA
then:
P uniformly ergodic, for any Q P and II, the minorization time of Q=:
Eminorixe (Qx) & minooiie
with probability 1.
49

---

is uniformly ergodic and for any E II, the minorization time of Pa:
minorrie (Pa) S
minoriie
with probability 1 B.
P is uniformly ergodic, for any Q P and π E I1, the minorization time of Qa:
minorize ( I
minorize
with probability 1
Proof. Since P is uniformly ergodic, by Lemma A.3 for any E II, there exists (Mag Px) pair such that Ma Eminorize (Pa) (.)).
First, for P. by Lemma E.1 for all Q E P, we have:
1
Ps.a
L (pr.a)
2mm
and there exists an vb E A(S), for any (NO, 8m,,
IESXAL
1
mr
2 (s0, Smx
pm (so, 8mg)
2mv
(F.13)
(58))
2
which implies Qn satisifes (m,, Pz >-Dobll condition with probability 1. And further, have
m
Eminorize (erriizee(+: (Qx) S
2iminrriee
P=
2
And P is uniformly ergodic. Second, for empirical kernel P. by Lemma B.3 we have when
32m
2|A||AA|
log
P^
empiricla kernel P,, satisifes (mgs Ps. -ooeblin condition, and P uniformly ergodic with probability
1 B.
Third, since when n 2 pa
32mL
log 21S
P
Q 2mm
)
2 21-8 B.
On P2 1,, PA 2 (1
PA 1M. By Lemma E.I
2my
1
Pm mmax {2, k) my PA max (2, k} m
It implies fo all @ P, Q. satisifes (m,,) 2 ( ) -Doeblin condition, P is uniformly ergodic and
sup maxt minorrie (+) 4t 4fminorize
@ep sell
with probability 1 B.
F Properties of the Bellman Operator: fa-Case
In this section, we target to bound the error between DR discounted Bellman opertaor and empirical DR discounted Bellman operator under fa Jx-divergnee. Similar to the KL-case. We override the notations for the fa-case and introduce the fa duality
50

---

Lemma F.1 (Lemma of Duchi and Namkoong 1)). For any (s,a) E S x A. let Pe.a be the
Ji-uncertainty set centered at the nominal transition kernel Ps.a. Then, for any á > 0, let k k-1
k
T Po.. (V) sup { (6p)) (a-v(5))
(F.1)
OER
where (x) (1 + k(k 1)6)* (-) max {, 0} and V S + R is the value function.
we denote the du-dual functional under the nominal transition kernel Ps.a:
f(P.,as V,a) == -- cx (a v) d
(F2)
then
(V) sup (P V, a
At the same time, we follow the auxiliary measures and function used in KL-case:
Ps.a(() tps.a (1 t)p
Apa,a = Ps.a -Pa,a IN.0 (t, a) (ps,a(t), V.
(F33
When d < 1, P1) ~ Pa,a holds for all (s,a) E S x A and I E [0, 1] on 2n
Lemma F.2. For any ö, the supremum of (ps a, is achieved at a² 2 ess essinfp.. V. of" ess inf Px.a. V. then
Pe.o [(a* x V)4 2-
cx(5)
Ps.a (aa" V)
where Pa.a defined as below:
pa (-) Ps.0 (a VV) (.)
Ps.a (a- - V)
a worst-case measure. When a" ess inf
V, the worst-case measure is given as:
Ps.a [1 (U n-]]
Pa.a (.)
Ps. [U)
where U {s'
(s's:' V(s') ess inf v).
Proof. A directly consequence for (p vx is (Ps.a V, = when ess inf V Ps.a
Thus, f is monotone increasing as a < css inf pa... V. thus, the supremum of {Ps.as V, a.) achieved x** 2 ess infp... V. The first order derivative (p V,ax) with respect to a is given as:
Of V.a) 1 cx(
Po.o (a v)4
Pa.a - (a- -1)
(F.4)
da
By Proposition I of Duchi and Namkoong (91. the dual form of f(ee.a a, is concave with respect to a, and the supremum is achieved at a where fP V, a) lama Since:
0f (p V,
cx (0) |aaa (wuee -V)
# Vssa [ - v)
(F55)
dx
By the first order condition, we have:
0 Of(ps. V.a)
da
a=0"
(F6)
- (d)
Pane -o-e--V''"
Posa (a'e (a'e- -1)
51

---

Whiche implies:
(6) Ps.a (a- c 1) 1-
(F.7)
Ps.a [ - V)+
Then, to show Pa.a a worst-case measure, it sufficient to show Ps.a V = f(ps,a, V,a*) and
Di (Pa.a (ls,a) 6. We have:
(a' - 'v)
Psça
Pza VV-
[(at - V1
Ps.a
(a" - (v)4
a*)
Ps,a (a* - -1 a*
Psça
+
Ps.a (a* 1007-10 -V4
Psoa (a -1
(F.8)
Ps. 1(0" - -V)
a²
Psça (aa - -V)
(o)pss - -V)- +
f(Pa,ax V,a")
Where (i) is derived by Equation F.7..
Moreover, by the definition of fR diveeeeree we have:
(a" 10---o V- -V)
k(a" - V²
Djv (e-..aallaaaa = k:kk Pa,a
+ k:
Ps. (a" -V)
Ps.a (a VV 1
-1]
(a" -V3k
k(a" -V)
k:k 1) Poia
P8.0 [(00 V)4=-11 -17 + ke
Pe.a [(00 V)
kps,a (a" VV
Ps.a (a"- V)
+ -
k(k 1)
Ps.a (a*
Ps.a [a* V)
(cx(0) k k - 1)
k( 1)
=
(F.9)
Here we proved that when a² > ess inf px.a V:
p-)a()) Ps.a (a" -14--14-111 [1
Pe,a [(a* V) k-==-11
P5 is worst-case measure. Further we show when a* = ess inl Pa.. V, ph,a defined below is worst-case measure:
v.a()) Ps.a [1 (Un-
Ps.a [1
where U= = V(') ess ess inf p... VJ. As (V) = ess inf V, then we only need to show
Dra (Dp.allpa... S 8. To show this, we divide into two cases.
First, is constant function on supp(ps.a). then U = S, then for all qa.a E Pa.ar Ja.a [V] ess inf p... V. and ph_a Pe.a. Pe.o E Psaa is worst-case measure.
Second, if V is not constnat, then S\U of 0, observe that, by continuity, there exists eo > 0,
such that for all 0 < < Ev.
ess inl S a" +
ess ess V(s)
Paia
s
At the same time, as (pa.a V,a*) = sup, sup, f( V.a,, then
0 aS V.a)
50
da
la+e
52

---

which implies:
021-c46 Ps.a (aat + -) 10-
Pssa (aa + (()+
(F.10)
(6) 2 Ps.a [=1 (U])*
1
Ps.a [<1 (U])
Ps.a [ {U})
The above inequality holds for all O, thus, by k I-I we concludes:
(6) 2 Ps.a [1 {UH)-1
(F.11)
Then, we can compute the fi-divergence as:
(
1 1(U)
A1 (U}
Ds (Po.allaa)))
k(k - 1) Ps.a
Pasa (paal1(UH)
Pao [UU + + +h-1
1
k
k(k - 1) Ps.a [1 [U}]k-
(F.12)
k(k (cx(0) 1)
Where (i) follows by F.1I). Thus, we proved the Lemma.
Lemma F3. 8 S 26 Pr. then a [V
Proof. First, if V is essentially the constant, then Span (V) = 0, and
f(P.aa V.a)=a =a when a S || L (p)..a))
And hence a 2 I (pr.a))
When V is essentially the constant, let U ( ess inf v). and S\U + 0, hence:
Pa.a [U}) $ - P
Recall Lemma F2 the worst-case measure given as:
(.) = Pe.a (a - VV) -1 1 1.3
Pa.a [(a* - V)4
Hence:
8 2 Dy, (pi.a (ls.a) =
Po.al (U]jk-1 -1)
k(k: 1)
(1 (1-pa) I -1
(F.13)
k(k: - 1)
1
PA
k
Inequality (i) is derived by (1-zje
1
12 when > 0. However, the above result contradict to the
assumption where < PA. Thus, we conclude a > [ [ (p(.)))))
As a" (Vllzo((aa))
-a' = -V>0
holds. Then, show the following Lemma:
53

---

Lemma F4. Let P2.P E A(S) s.t. P1.P2 & p. Define A == P1 P2. Then, for any V S + R and h 1:
A ((a [(-
2A
sup a>
h-
pl(a- V)K-1
p
Span (V)
(F.14)
Proof. Notice that for all E E:
1 k-
A (\
1
A (((a - c) (V c))²
sup a
pl(a- v)
sup a (
k-
p pl((a= c) (V (V-c)) c))
(F.15)
let c = ess inf, V and V = V c, then V V' (p) Span (V), and we have:
A (aa
sup 1
A [((a c) Vykk
sup a a2IlV |
k
plaa - VVh--
a2IlV k
pl((a c) -V
(F.16)
A (aa
1a- - VyK
sup VVSpan(V)
h+
p [(a - -
First, consider the case where 21 Span (V), then, for any 8 E S, and V'(s) > 0, we have:
a
2 2k*
2
vi(s)
1 2
(F.17)
a k1
(a Viyk-11 z
2
And when ('(s) = 0, (a)) >
2 holds trivially.
Further, with tayler expansion, there exists a E where E(s) E (o, Span(V) such that:
(1-VLo) V'(s) ke
= =1 -1- + k *"kk=_ 1)
V'())
2 (1 E(s)) k- (s)
a²
Then, we can derive that:
A A((a- (1aa-vy Viyk"
sup a 222k Span V) he
Pa,a(r) Ha - -V'))
A aak
1 - k V2
(*(K-11
5)
-22
V
1
a
sup 22 2222-SppanVV SV)n(V)
p ah*
2
aak (-K+V²
("(K-11
5) -2 1
1
2
.
sup o 22 SVan(V) h-
p
A
2
k- V'V'
(M-1) (1 - E)K² 22
2
P
(p)
sup 2222
x
(p)
k VV
(1- Ki (1 -2 -21"
2
A
a
1:
p
sup (p) a 222k Span(V)
kl-
(m(P)
2A
sup 222k 222k
V' 1 (1(1
bt*
(1
) k2--2
4k
2k
(p)
(p)
(a0)
2A
Span (V)
(p)
(F.18)
54

---

The equality (i) follows from the property that A 0 for any constant function since the difference between two measurres Á annihilates constants. The inequality (ii) is obtained by applying the condition 2 2 Span (V"), which ensures sufficient regularization. Finally, (Mii) emerges from the fundamental constraint A in our parameter condition.
Second, we consider the case where Span (V) S S Span (V), actually, the the above result holds trivally:
1
A (a - V
sup Span(V) (2) Saaaa Span(V)
K
p pl(a V)
1
A - V
sup
k
laa 1'
p pl(a V1
(F.19)
Span(V) So SpannsVV
2A
Span (V)
p
(p)
Combine the previous two cases, derived the result:
A a - "
24
sup a> |I [
$
Span (V)
p (p)
Proved
To establish Lemma F.6 bounding the dual functional difference, we build on Lemma
F.4 While this
result is analogous to Lemma C.7 for the KL-divergence case, the analysis for fu-divergence requires first applying the Envelope Theorem to characterize the variational behavior of the dual optimization problem.
Lemma F5 (Envelope Theorem, Corollary of Milgrom and Segal (26)). Denote as:
(t) sup f(r =EX
Where X is convex set in a linear space and f: Xx [0, 1] - R is concave function. Also suppose that to, and that there some I² E X (to) such that de fx" (t*,to) to) exists. Then V is differentiable at to and
dV 0f(z*.t) t)
dt
Lemma F.6. Let Ps.a be the nominal transition kernel, and pa.a be the empirical transition kernel, when 5 S mmx(8,48)m Pa, then the below inequality holds
sup ff.... V,a) sup f(ps,a, V.a) 4d Span (V)
.ER
oER
on Dn,d. when d S
Proof. Since
1
5 max {8, 4k) m² PA 2
by Lemma
F.3 we have a' || 1. (p..a))))))) thus, only need to consider the case where >
||V]|
[| then recall
gn a) = -1 (1)
(t) (a - +
(F.20)
=a - c2
concave with respect to a, then denote G(t) and a (t) we have:
G(t)
sup
at,
(F21)
=g,,a (t, a" (t))
55

---

Combine previous results, we have:
sup f(Pe.a V,a) - sup f( V,a) = [G(1) G(O) = dG(()
(F.22)
dt
oE
aER
Then, by Lemma
F.5 have, as G(t) differentiable on [0, 1], then:
dG(t) dge,alt,a)
Öt
(a=a(())
Then have:
dG
sup a v, - sup ((s v. loER
dt
aeR
ter
(y Ot
(F.23)
a==a 11=
(x)
(Ds,a Po.a) (t) V)*
h+
Pa (1) [aa -V) *े
Since or (+) is the optimal multiplier for sup supa221VV| 90,a (T, Using Lemma F.2 we have, for all E [0, 1]:
(6) (T) (T) 1- Pa.a(T) (T) - []
Thus:
(Ds,a - -aaa) (T)
- V)4*
sup f( V,a) - sup fP V,a) = kz aelt
(T ((a - V)
ack
(F.24)
1
(Fs. Pa.a) [(a V)*
a2 [V (po.a)
sup
bet
(T. [[a VI
Using the fact a" 2 IV by the formula where k Lemma
we know & > 1, then, apply k-
*
F4
1
(Pe. Po.a) - (a-v)** Pa.a (T,a(T) (( 11
2 (Do.a Pr.a) Pa.a (T)
sup a (p)
Span (V)
(p..a)
Further, on the events set Qnnds we have, when d S
2'
Pe.a Pa.a
d d.Ps.a
S 2d.
(T)
1.00 (p.u)
TPs.a +1 Ps d) (
1 d
We derived the result:
sup (Pr,a V.a,a) - f(ra. V.a)) S 4d Span (V).
Proved.
Lemma E7. When n > 32p Log(2)S((AA//3) then for any π E 11, the los -eror of the empirical DR Bellmam operator 1r and the DR Bellman operator 7 can be bounded as:
- - (VF) < 12t (Pa)
8
log
S A
3
with probability least 3, where Pz is the transition kernel induced by controlled transition kernel P and policy m.
56

---

Proof. By Union bound and Bernstein's 's inequality, we have, when:
32
||
log
Px
the relative enror of (a could be bounded as:
(s.a(s') Ps.a(s')
2/S A
2
2 A
log
log
Ps
74p^
B
2| A
(F.25)
log
7
83
Thus, let d
8 V upx
log
2|
2 we have:
p(On.a) 2 1 - 3.
Then, on an by Lemma F.6 could bound the error
(VB)) (V()))
Σ r(als)
E m(als) (r(8,a)++Tpp. + p... (Vz))
max sES
max
?I P.. (VP) - -T.P... (VP)
(s,a)ESxA
Sy max
sup ff Vp, a) - -sup S(p,a VB,a) aEk
(x.
aE
Sy max
sup
[f vb f(p Vi,a)]
(s.a)ESxA acR
IAS
4d Span (VF)
3,0ESXA
(F:26)
The inequality (i) is derived by Lemma P.4 Since Lemma
A.3
there exists an (m,, P-) pair such that is
m2/P /Px minorrie (Pa), combine Proposition A.5
when
Span (VP) S
Sm,/Pr. we have: when
32
||
log
8
then
(7(3))-T,(0
<dd Span (VB)
(F.27)
2/ 8
2t 2tminorize (Pt)
log
with probability 1 3.
G Sample Complexity Analysis: fú Uncertainty Set
We proceed with the analysis of the Algorithm and 3 in the fx-divergence case.
G.1 DR-DMDP under fo Uncertainty Set
Building upon these analytical foundations, we derive the following sample complexity bound for DR-MDPs with fi-divergence uncertainty sets:
Theorem G.1 (Restatement of Theorem 4.4). Suppose Assumptions and are force. Then for any > 32p log(2)5|{AA|/3) the policy 7" and value function returned by Algorithml 1
57

---

satisfies:
minooiie
2
2/S|2 A
5 V Vp
log
apn
(G.1)
V - Vp
minooiizze
log
2/S|2| A
apx
B
with probability 1 - 3. Consequently. the sample complexity to achieve E-optimal policy and value function with probability 1 is:
C. 12 minorize log
7)-
8
where c 962, and = 2- 48 repectively.
Proof. For any æτ, V is the solution to VØ TT, (Vp), by Lemma F.7 when:
32
2 2 A|
n
log 8
with probability
3, we have:
(VB)
S sup QEP
(v T, (V2)
2 A
12 sup imiooriaa (Qx)) ) QEP
log
(G.2)
8
2/S/2 A
S 24
log
Since the above result holds for all æ E II, then:
max well
v
V
max y xEll
T: (V%) T (V7)
(G.3)
481 minoriie
2|S| A
log
1
8
By Lemma
D.I as 7* = arg max V
we have:
p.
V - V
2 max TE
V V
Thus, when:
32
2| A
n >
log
B
we have:
2
2/S ||A
VΦ V < 96l minorize
log
,3
with probability B. At the same time, when 2 32p
log (2//) we have:
48t minorize
2
2|S A
V
V 00
max n
VT
log
00
7
npA
with probability 1 1 3 concurrently.
58

---

G.2
Reduction to DR-DMDP Approach under fR. Uncertainty Set
Theorem G.2 (Restatement Theeree
Suppose Assumptions 2 are in force. Then, for any
32
||
log
Px
B
V8
The output policy 7" and vn
returned by Algorithm
satisifes:
|
S 9p 9p
minoriioo
log
/
(G.4)
V
2
2|S|
96
600tminozit
log
nn
B
with probability 1 B, and the sample complexity achieve E-optimal policy and value function with probability 3 is:
[/ Miioorize log
2|5|9|A||
n= 0
PAE2
3
Proof. Similar with The proof of Theorem D.4 we have:
V
0 S gp
9p
<2
max
+ 2 max xell
V
V
mEll
Vn
(G.5)
Vx
V
V
V3
Jp
max xell
9p
max Rell
Vn
Vn
As, with Proposition
B.2
we have P uniformly ergodic, and for all Q E P and E II:
Inninorize (Q+) S 2bminorine
Thus:
V P
1 St minorize
Since by Lemma F.7
we have, when >
32 log
AAA
8
2|S
max nell
Vp
< sup max 24t minorize (Qx) QEP gell
log
Vn
пр^
3
(G.6)
log 2|S|2| A|
4t minorize
B
with probability 8. Combine the intermediate results, we have:
36t 36tminorize
8
2/S 2
A
S g
48t minorizzee
log
Vn
3
36t minoiize v 'n
128
2/S 2|
A
+
log
9px
(G.7)
2 A
120t minorize
log
0
V
2
2|S
go
60 minorise
log
Vn
npa
59

---

with probability 1 - 5. where (i) and (it) are derived simply by the trival parameter bound PA S A 2 and 1. The sample complexity required for policy evaluation on म and value
V in achieving e-optimality evaluation on vn
C 12
2/ A
minorise log
P
B
where c 2- 1202 and c 2- 602 respectively.
G.3
Anchored DR-AMDP Approach under f& Uncertainty Set
Theorem G.3 (Restatement of Theorem any
4.5
are in force. Then for Suppose Assumption 7 and 2
32
||
||
n
log
8
The policy 7t and 0z returned by Algorithm satisifes:
2
2|S|
0 S g0
9p
S
log
|
(G.8)
2|
260mminoriee
<60
log Пpf
B
with probability 1 8, and the sample complexity to achieve E-optimal policy and value function with probability 1 - 3 is:
2 miinorrie log
2|S|?|A|
n =
PAE
8
Proof. Similarily with what we have in Theorem D.8 empirical uncertainty P:
is optimal policy for the anchored
9
gp
s0:
96
9p
max S
9
97
TEl
In addition:
97
max
g 97
(G.9)
mEn
Since 03 = (sV) for any π E 11
07 gf
3V (50) - (8) + {S7((s)) g3
[V gV
VVV 110
(G.10)
<<
V
V
+ lKVV g 1l
where (i) relies to P uniformly ergodic, thus, g
g for all E S. og
for some constant
Then, have:
0 gp
yp
max
REIl
V
P
V
2 max xell
L go 1
(G.1l)
J/
9p
max
VT
Va
+ max xell
V 9b 1lo
P
20
60

---

With the choice of == -/m by Lemma C.3 II:
and Lemma
F.7
when
2 Pn.
log
3|S| |||
then for all
minorize
8
2/S
gp
$18
+ 24t minoriie
log
0c
Vn
72p
B
18t 1inooiiiee
128
2|S|
+
log
(G.12)
vn
9p^
8
2
<
minorrize
log
7
8
with probability B. We concludes, when:
32
2 2 A
log
P^
8
then with probability 1 1 8
2 log прa
2/S| A
0 S gp
9p
1120minoriee
(G.13)
2
||
9p
minorizee
log ПрΛ
B
holds. And the sample complexity required to achieve E-optimality for both policy and average value function is:
12 Lmmnorize
|S||AA] = o
12
S
n
log
log
PA
3
13
where mix = maX mix (Pa) proved.
< 00, since mix is equivalent to &minorize up to a constant,
H
Additional Experiment
To further expand on our results in Section 4 we provide additional experiments on baseline com- parison and large-scale MDPs. First, we include comparisons with DR RVI Q-learning (46) on Hard MDP Instance [.1 as baseline. Table and Figure shows
shows the enror performance for DR RVI Q-learning and the two algorithms for PA = 0.9 and á = 0.1. They demonstrated that the error levels of our two algorithms are comparable and significantly outperform the previous baseline.
Table 2: Performance comparison with DR RVI Q-learning
Sample
10
32
100
316
1000
3162
10000
31622
100000
DR RVI Q-learning [46]
1.84e-1
7.36e-2
7.47e-2
6.20e-2
5.52e-2
4.46e-2
3.60e-2
3.08e-2
2.6le-2
Reduction to DMDP
1.21e-1
5.95e-2
5.35e-2
2.74--2
1.39--2
6.65e-3
3.49e-3
3.21e-3
1.17c-
Anchored DR-AMDP
1.67e-1
6.52e-2
6.26e-2
2.90e-2
1.16e-2
7.5le-3
3.27e-3
2.37e-3
1.23e-3
Further, to demonstrate the capability of our framework in solving large-scale MDPs, we consider large-scale MDP with 20 states and 30 actions, as in Wang et al. [46]. The nominal transition distri- bution is specified by Pe.a ~ (1,, a.,a). where Js.a ~ Uniform 00, 100], followed by normalization. We then choose the uncertainty size d = 0.4 to introduce stronger perturbations, following the setting in Wang et al. [46] under the KL-divergence. Note that although = 0.4 violates Assumption 2 the slope of the linear regression of our results the logarithmic scale remains very close - -1/2. further supporting our theoretical guarantees. This observation empirically validates the theoretical results established in our theorems.
Further, to demonstrate the capability of our framework solving large-scale MDP instances, we consider large-scale MDP with 20 states and 30 actions, as in Wang et al. [46. Specifically, Algorithm 2 and Algorithm are evaluated on two distinet large-scale instances, respectively, to verify their effectiveness. The nominal transition distribution is specified by Ps.a (V
61

---

0.175
DR RVI Q-leamiing
Reduction DMDP
0.150
Anchored DR
average error
0.125
0.100
0.050
0.025
0.000
10
10a
10a
10
10a
number of samples
Figure 3: KL-divergence case for Algorithm and
10
..... slage -0.4%
slope -0.54
average error
average error
10
10a
10
10
10
10a number samples
105
number samples
(a) Algorithm
large-scale MDP.
(h) Algorithm for large-scale MDP.
where Ja.a Uniform [0, 100). followed by normalization. We then choose the uncertainty size = 0.4 to introduce stronger perturbations, following the setting Wang et al. [46] under the KL-divereence. Note that although 5 0.4 violates Assumption 2 the slope of the linear regression of our results on the logarithmic scale remains very close to - -1/2. /2, further supporting our theoretical guarantees. This observation empirically validates the thcoretical results established in theorems.
Table 3: Performance on large-scale MDP across different sample sizes.
Sample
32
100
316
1000
3162
10000
31622
100000
Reduction to DMDP
1.04e-1
6.54e-2
3.07e-2
2.46e-2
8.28e-3
4.82e:3
4.66e-3
3.12e-3
1.12e-3
Anchored DR-AMDP
6.55e-2
3.72e-2
2.69e-2
4.79c-3
3.73e-3
1.15e-3
1.33e-3
9.42e-4
5.61e-4
62


Reviews:
[{"review_id": "ODm8ijLlMj", "reviewer": "Reviewer_Umdh", "summary": "This work proposes new algorithms with improved sample complexity for DRO RL problems for discounted and average reward settings. The improvements are possible due to recent advances in non-DRO settings, significantly tightening the dependence on the discount factor compared to prior work in the DRO setting and nearly matching the rates in the standard non-DRO setup. \n\nWhile there are some objective weaknesses concerning the technical novelty compared to a non-DR setting, and limited empirical evaluation, my overall evaluation is positive. The main positive points are the practical importance of the problem, excellent presentation, and the technical depth of the derived results.", "questions": "This is a standard thing in DRO, but I could not find the definition of $(s, a)$ rectangular sets mentioned in line 114 of the paper. \n\nTypo on line 145, should be \"constant\". \n\nSomething is wrong in Definition 3.3. It should be either for all policies or maximum over all policies. \n\nWhat are $Q_{\\pi}$ and $Q$ in Proposition 4.2. I assume this is another typo.", "limitations": "n/a", "rating": 4, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:** \n1. The sample complexity in the DR setting is improved for the discounted setting in terms of $1-\\gamma$ dependence from $O((1-\\gamma)^{-4})$ to $O((1-\\gamma)^{-2})$. This is a significant improvement and in addition this allowed them to extend the result to average reward settings via black box reduction. \n\n2. The sample complexity matches the lower bound in non-DR setting, making this extension essentially almost \"for free\". However, the dependence on the mixing time becomes quadratic instead of being linear; it is unclear to me if this is improvable. \n\n3. The presentation of preliminaries is very useful to understand the key theoretical components. \n\n4. Experimental results are well done, although limited to a toy (hard instance) task. Figure 2 verifies theoretical convergence rates. There are no error bars, but the variability among different numbers of samples is relatively small; this is likely because the task is very simple.  \n\n**Weaknesses:**\n\n1. It is difficult for me to judge the technical difficulty of extending the Standard (non-DR) convergence result to this DR-RL setting, but I have the impression that the improvements are largely dependent on the very recent improvement by Want et al [38]. \n\n2. Some results should be better discussed in the next revision. For example, how to interpret the results in Table 1. The prior work in this table is mostly discussed in the text, but the positioning of the derived result in the literature is not complete. \n\n3. Why do we need two algorithms in the average reward setting? Is there any advantage of Algorithm 3 over Algorithm 2? The differences should be discussed. What is the difference between them in a large-scale experimental setup?", "was_revised": true, "final_justification": "I thank the authors for addressing my concerns and answering questions. I appreciate the additional experiments provided and consequently maintain my score.", "rebuttal": "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:\n\n**Weakness 1: Technical difficulty of extending non-DR result to DR-RL setting.** \n\nWe 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:\n\n1. **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.\nHowever, 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.\nIn 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.\n\n2. **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. \n\n**Weakness 2: Table 1 results interpretation is incomplete.**\n\nWe 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.\n\n**Weakness 3: Algorithm 2 vs. Algorithm 3: advantages, differences, scalability.**\n\nWe 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. \n\n**The differences and potential advantages between two algorithms are:**\n1. **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.\n2. **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.\nWe will expand the discussion in the revised version to clearly articulate these differences, including their theoretical guarantees and practical trade-offs.\n\n**On large-scale experimental setups**\n\nTo 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:\n\n| Sample           | 10      | 32      | 100     | 316     | 1000    | 3162    | 10000   | 31622   | 100000  |\n|:----------------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|\n| Large Scale MDP  | 1.04e-1 | 6.54e-2 | 3.07e-2 | 2.46e-2 | 8.28e-3 | 4.82e-3 | 4.66e-3 | 1.32e-3 | 1.12e-3 |\n\n**Question 1: Definition of $(s,a)$ rectangular sets**\n\nThe 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.\n\n**Question 2: Typo “constant”**\n\nThank you for catching this typo. We have corrected the issue in the revised manuscript. \n\n**Question 3: Definition 3.3**\n\nWe have revised this definition as follows to improve mathematical rigor. \n> 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)$\n\n**Question 4: $Q$ and $Q_\\pi$**\n\nIn 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.\n\n[1] Wang, Y., Velasquez, A., Atia, G. K., Prater-Bennette, A., & Zou, S. (2023, July). Model-free robust average-reward reinforcement learning."}, {"review_id": "cHxWjoUFlG", "reviewer": "Reviewer_wDLr", "summary": "This paper investigates distributionally robust (DR) average-reward reinforcement learning and first establishes a sample-complexity $t_{\\text{mix}}^{2} \\epsilon^{-2}$ for a model-based algorithm in this setting. Building on techniques from the non-robust RL literature, this paper proposes DR-DMDP with Reduction to DMDP, and then propose Anchored DR-AMDP to avoid the costly subproblem required by earlier methods. Both algorithms achieve near-optimal sample complexity and are empirically validated on hard MDP instance.", "questions": "What obstacles had to be overcome to adapt the discounted reduction and anchoring techniques to the distributionally robust average-reward RL setting?\n\nIs there a known lower bound for distributionally robust average-reward RL?", "limitations": "yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 2, "significance": 2, "originality": 2, "strengths_and_weaknesses": "Strengths:\nThe paper introduces DR-DMDP with Reduction to DMDPs and Anchored DR-AMDP, establishing a sample-complexity $t_{\\text{mix}}^{2}\\,\\epsilon^{-2}$ for the first time in the distributionally robust average-reward RL setting. Numerical experiments on a toy hard MDP instance demonstrates theoretical results\n\n\nWeaknesses:\nBoth core ideas, the reduction to DMDPs and the anchoring technique, are adapted from earlier work. Consequently, the technical novelty appears to lie mainly in extending existing methods to the distributionally robust domain, and it is unclear how substantial that advance is.", "was_revised": true, "final_justification": "I am satisfied with the response and have no unresolved issues other than the novelty of the contribution, as noted in the rebuttal. Consistent with my original review, since the strengths slightly outweigh the weaknesses, I will maintain my score.", "rebuttal": "We thank the reviewer for the insightful comments. We hope that the following response will help to address some of the concerns.\n\n**Weakness: Limited technical novelty in robust domain extension & Question 1: Obstacles in adapting techniques to robust average-reward RL**\n\nWe 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: \n1. **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.\n2. **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. \nThe 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. \nIn 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.  \n3. **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.\n\n**Question 2: Lower bound for DR average-reward RL**\n\nThe landscape of lower bounds in DR-RL setting is not yet fully understood, even for the discounted case.\nWe 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.\nCurrently, 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.\n\n[1] Roch, Zachary, et al. \"A finite-sample analysis of distributionally robust average-reward reinforcement learning.\"\n\n[2] Wang, S., Blanchet, J., & Glynn, P. (2023). Optimal sample complexity for average reward markov decision processes.\n\n[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."}, {"review_id": "xV9nctmJF3", "reviewer": "Reviewer_huvR", "summary": "This paper studies offline RL under the assumption that the environment is modeled as a DR-AMDP. The transition dynamics are non-stationary and lie within a divergence-based uncertainty set, specified using either KL divergence or $f_k$​-divergences. The authors consider both average-reward and discounted-reward settings and propose two algorithms with theoretical sample complexity guarantees.\n\nThe first algorithm builds on Q-learning, using a modified distributionally robust Bellman update that incorporates pessimism by finding a transition in the uncertainty set to minimizing the value function. The second algorithm employs an anchoring technique, modifying the transition kernel with a fixed reference state to ensure robustness, and achieves the same sample complexity as the first.\n\nTheoretical analysis shows a near-optimal sample complexity under a uniform ergodicity assumption. Empirical results on a synthetic two-state, two-action MDP validate the theoretical findings by demonstrating that the average error scales with the number of samples at a rate consistent with the theoretical bounds.", "questions": "* Does the theoretical guarantee require knowledge of $\\delta$, the radius of the uncertainty set?\n\n* Could the authors clarify the difference between DR-RL under the discounted setting and DR-RL under the discounted mixing setting?\n\n* Is the update rule for g^* missing in Algorithm 3?\n\n* A proof sketch should be provided to improve readability, and the novelty of the analysis should be clearly highlighted.", "limitations": "The assumptions of uniform ergodicity and the availability of simulators make the proposed method less tractable for real-world applications.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 2, "originality": 2, "strengths_and_weaknesses": "**Strengths** \n* This paper improves the sample complexity bound for offline DR-MDP with the assumption of uniform ergodicity.\n*  Empirical results validate the theoretical result, where the average error scales with the number of samples at a rate consistent with the theoretical bounds.\n* The proposed algorithms are designed without requiring knowledge of the mixing time.\n\n**Weaknesses**\n* The empirical results lack comparisons with other baseline approaches. It would be helpful if the authors could provide results for other algorithms, such as DRVI-LCB and DR Q-learning.\n\n* The novelty of the paper should be clarified. In terms of the algorithm design, the two proposed methods are similar to previous works: Robust Q-Iteration [1] and the Plug-in approach [2].\n\n* The proposed algorithms and theoretical guarantees require access to simulators for generating i.i.d. samples. This setting differs from the traditional offline RL setup, where the transition model must be estimated solely from offline data, making the approach less tractable in real-world scenarios.\n\n* The environment used in the experiment is a simple MDP with only 2 states and 2 actions, which is not representative of most RL applications.\n\n[1] Robust Reinforcement Learning using Offline Data\n\n[2] The Plug-in Approach for Average-Reward and Discounted MDPs: Optimal Sample Complexity Analysis", "was_revised": true, "final_justification": "I accept the authors’ argument and will maintain my positive score for this paper.", "rebuttal": "We thank the reviewer for this constructive feedback. We hope the following response can address some of your concerns:\n\n**Weakness 1: Baseline comparisons**\n\nOur 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. \n\n| Sample           | 10      | 32      | 100     | 316     | 1000    | 3162    | 10000   | 31622   | 100000  |\n|:----------------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|\n|DR RVI Q-learning [5]   | 1.84e-1 | 7.36e-2 | 7.47e-2 | 6.20e-2 | 5.52e-2 | 4.46e-2 | 3.60e-2 | 3.08e-2 | 2.61e-2 |\n| Alg1 & Alg2      | 1.21e-1 | 5.95e-2 | 5.35e-2 | 2.74e-2 | 1.39e-2 | 6.65e-3 | 3.49e-3 | 3.21e-3 | 1.17e-3 |\n\nThe error in Alg 1 & Alg 2 is the maximum over both algorithms.\n\nSince DRVI-LCB is an offline RL method, it does not apply to our setting.\n\n**Weakness 2: Clarify novelty; methods similar to prior works.**\n\nIn 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.\n\n1. **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.\n2. **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.\n3. **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.\n\nOur 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. \n\n**Weakness 3: Simulator and offline RL**\n\nThis 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.\n\nWe 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.\n\n**Weakness 4: Experiment**\n\nThank you for the question. We chose a simple MDP with 2 states and 2 actions mainly for theoretical reasons:\n1. **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.\n2. **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.\n3. **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.\n\nAdditionally, we have conducted further experiments on Large MDP (20 states, 30 actions) as in [5] to support our theoretical result\n| Sample           | 10      | 32      | 100     | 316     | 1000    | 3162    | 10000   | 31622   | 100000  |\n|:----------------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|:-------:|\n| Large Scale MDP  | 1.04e-1 | 6.54e-2 | 3.07e-2 | 2.46e-2 | 8.28e-3 | 4.82e-3 | 4.66e-3 | 1.32e-3 | 1.12e-3 |\n\nIn large instances, the results are consistent with our theoretical guarantee, with the fitted slope in log-scale being close to $-1/2$.\n\n**Question 1: Knowledge on uncertainty set radius**\n\nWe 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.\n\n**Question 2: Differences: discounted vs. discounted mixing**\n\nThe 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.\n\nIn 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.\n\nSpecifically, 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.\n\n**Question 3: Update rule for $g^*$**\n\nNo, 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. \n\n**Question 4: Proof sketch and Novelty**\n\nThis is a great suggestion. Our proof relies on two key insights:\n1. **Bounded Minorization Times:** Under the assumption of bounded uncertainty size, the minorization time on the full set of uncertainties can be effectively controlled.\n2. **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}}$\n\nThese 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.\n\n**Limitation** \n\nIndeed, 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.\n\n[3] Roch, Zachary, et al. A finite-sample analysis of distributionally robust average-reward reinforcement learning.\n\n[4] Wang, Shengbo, et al. Optimal sample complexity for average reward Markov decision processes.\n\n[5] Wang, Yue, et al. Model-free robust average-reward reinforcement learning.\n\n[6] Wang, Shengbo., et al. Optimal sample complexity of reinforcement learning for mixing discounted Markov decision processes."}, {"review_id": "ZwBJhHGEEt", "reviewer": "Reviewer_6nKR", "summary": "The paper considers the nonasymptotic sample complexity of learning near-optimal policies for distributionally robust average-reward MDPs under $f_k$ and KL divergence uncertainty sets. The authors consider the uniformly ergodic setting. They provide two (closely related) algorithms based on discounted reduction, and based on an anchoring-based approximation of the average-reward MDP. They provide an intermediate result showing a refinement of the sample complexity of discounted distributionally robust MDPs of independent interest. The paper also provides some numerical experiments.", "questions": "1. What dependence on minimum support/minorization is exhibited by the hard MDP instances? Relatedly, what lower bounds exist in the literature for the sample complexity of robust MDPs, both for discounted and for average-reward settings?\n2. More description of the technical obstacles encountered and overcome by the authors would be beneficial in appreciating the level of contribution of this paper. In particular, how do the obstacles faced by the authors differ from those encountered in other papers on (non-robust) average-reward MDPs? Also, it would be appreciated if the authors could discuss why they did not present results which hold for weakly-communicating MDPs.", "limitations": "yes", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths:\nI think the paper is written clearly. The algorithms are natural and the main results seem to have good significance, and therefore I believe that this paper will lead to future work on this problem. While I have some doubt about the level of technical obstacles faced (below), I believe this is mitigated by the fact that this natural problem has not been previously addressed from a sample complexity perspective.\n\nWeaknesses:\nThe results depend on the minimum support parameter, and they also depend on the square of the minorization time (rather than linearly on the minorization time, which is the correct scaling for the non-robust case). It is unclear whether these are the correct dependencies, and they are not explored theoretically by the paper as no lower bounds are provided (except for the trivial application of the non-robust lower bound). This is mitigated somewhat by the experiments which vary the minorization time/minimum support parameter (which coincide for this instance), but the dependence is not explored clearly (there are no experiments where the minorization time is the x-axis). It would be nice to have more discussion of lower bounds within the related work section. The results are in terms of the uniform mixing time, while work on non-robust average-reward MDPs has worked on sharper parameters (such as the optimal bias span) which are finite for weakly communicating MDPs. Overall, I have some doubt of the level of technical obstacles faced in obtaining the results of the paper and how they differ from obstacles which have been already solved for non-robust average-reward MDPs.\n\nOther minor comments:\n1. It should be clarified in table 1 that only corollaries for the mixing time are presented, since (especially for standard MDPs) there are several other complexity parameters which are considered\n2. I don’t understand the point made on line 168 that the minoration time offers sharper theoretical insights, it seems to be undermined by the subsequent claim of equivalence up to constants between the mixing and minoration times.\n3. Maybe for clarity it should be emphasized in definition 3 that this is a maximum over all deterministic policies", "was_revised": true, "final_justification": "The proof sketch details provided by the authors in the discussion substantially clarify my questions about the novelty of the paper's techniques relative to the non-robust setting, and will improve the contribution of the paper.", "rebuttal": "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:\n\n**Question 1 (a): Dependence on the various parameters**\n\nRegarding 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. \n\n**Question 1 (b): Lower bounds**\n\nWe 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. \n\n**Question 2 (a): Technical challenges**\n\nIn 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.\n\n1. **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.\n2. **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.\nHowever, 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. \nIn 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.  \n3. **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. \n\n**Question 2 (b): Weakly communicating**\n\nWe 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.\n\n**Supplementary: Experiment for the dependence of minorization time**\n\nMinimum 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\n\n| $t_{\\mathrm{minorize}}$ | 1      | 5      | 10     | 20     | 40     | 60     | 80     | 100    | 120    | 140    | 160    | 180    | 200    |\n|:-----------------------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|:------:|\n| **Error**               | 9.08e-3| 6.31e-2| 1.04e-1| 2.04e-1| 3.29e-1| 4.05e-1| 4.65e-1| 5.55e-1| 5.65e-1| 6.16e-1| 6.14e-1| 6.78e-1| 6.85e-1|\n\nThank you for your insightful comments.\n\n[1] Shi, L., et al. The Curious Price of Distributional Robustness in Reinforcement Learning with a Generative Model.\n\n[2] Shi, L., & Chi, Y. (2024). Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity.\n\n[3] Wang, S., Si, N., Blanchet, J., & Zhou, Z. (2024). Sample complexity of variance-reduced distributionally robust Q-learning. \n\n[4] Duchi, J. C., & Namkoong, H. (2021). Learning models with uniform performance via distributionally robust optimization.\n\n[5] Roch, Zachary, et al. \"A finite-sample analysis of distributionally robust average-reward reinforcement learning.\"\n\n[6] Wang, S., Blanchet, J., & Glynn, P. (2023). Optimal sample complexity for average reward markov decision processes."}]

Author rebuttal:

Meta-review: Summary: This paper investigates the sample complexity of distributionally robust reinforcement learning (DR-RL) under both discounted and average-reward settings. The authors extend recent advances in non-robust MDPs to the robust domain, introducing reductions and anchoring techniques to design algorithms with improved sample complexity guarantees. In particular, they establish the first nontrivial sample complexity bound for distributionally robust average-reward MDPs, matching known lower bounds in the non-robust setting up to mixing-time dependencies. Theoretical results are supported by experiments on a simple hard-instance MDP, which validate the predicted convergence rates.

Comments: This paper has received 4 expert reviews with scores 4, 4, 4, 4, and the average score is 4.0 

The reviewers acknowledge that this makes meaningful technical progress by improving sample complexity guarantees in the discounted setting and extending them to the average-reward setting. Results are theoretically significant, with complexity bounds that closely match non-robust lower bounds. The proofs and preliminaries are presented clearly, and the experiments (though limited) confirm the theoretical convergence rates. The algorithms are natural and well-motivated, and the paper may stimulate further research in robust average-reward RL.

The reviewers, however, have raised many concerns. For example, the dependence of the results on parameters such as mixing time and minimum support is not fully clarified, and no lower bounds are provided to confirm optimality. The assumptions of uniform ergodicity and access to simulators reduce the practical relevance of the results.

Based on my reading of the paper, reviews, and the rebuttal discussion, I believe that this paper presents solid technical contributions to the theory of robust RL, particularly in establishing sample complexity guarantees for average-reward settings. While the novelty relative to prior work is not completely original, the results are natural and important, and the analysis is carefully executed. The main weakness lies in the lack of convincing empirical validation and the reliance on strong assumptions, which limit immediate practical impact. Nevertheless, the theoretical advances are substantial enough to warrant acceptance.
Decision: Accept (poster)