Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning
Authors: Yang Xu
Washim Uddin Mondal
Vaneet Aggarwal
Venue: NeurIPS 2025 poster ()
Keywords: Robust Reinforcement Learning
Policy Evaluation
Finite-Sample Analysis
Average Reward MDPs
Stochastic Approximation
Primary area: theory
TL;DR: We present the first finite-sample analysis for policy evaluation in robust average-reward reinforcement learning using semi-norm contractions.

Abstract: We present the first finite-sample analysis of policy evaluation in robust average-reward Markov Decision Processes (MDPs). Prior work in this setting have established only asymptotic convergence guarantees, leaving open the question of sample complexity. In this work, we address this gap by showing that the robust Bellman operator is a contraction under a carefully constructed semi-norm, and developing a stochastic approximation framework with controlled bias. Our approach builds upon Multi-Level Monte Carlo (MLMC) techniques to estimate the robust Bellman operator efficiently. To overcome the infinite expected sample complexity inherent in standard MLMC, we introduce a truncation mechanism based on a geometric distribution, ensuring a finite expected sample complexity while maintaining a small bias that decays exponentially with the truncation level. Our method achieves the order-optimal sample complexity of $\tilde{\mathcal{O}}(\epsilon^{-2})$ for robust policy evaluation and robust average reward estimation, marking a significant advancement in robust reinforcement learning theory.

Finite-Sample Analysis of Policy Evaluation for Robust Average Reward Reinforcement Learning
Yang Xu
Washim Uddin Mondal
Purdue University West Lafayette, IN 47907, USA xu xu1720@purdue.cm edu
Indian Institute of Technology Kanpur Kanpur, UP, India 208016 wmondal @ieleiiiikk..e ac in
Vaneet Aggarwal
Purdue University
West Lafayette, IN 47907, USA
vaneet@purdue edu
Abstract
We present the first finite-sample analysis of policy evaluation in robust average- reward Markov Decision Processes (MDPs). Prior work in this setting have es- tablished only asymptotic convergence guarantees, leaving open the question of sample complexity. In this work, we address this gap by showing that the ro- bust Bellman operator is a contraction under carefully constructed semi-norm, and developing stochastic approximation framework with controlled bias. Our approach builds upon Multi-Level Monte Carlo (MLMC) techniques to estimate the robust Bellman operator efficiently. To overcome the infinite expected sample complexity inherent standard MLMC, we introduce a truncation mechanism based on geometric distribution, ensuring finite expected sample complexity while maintaining a small bias that decays exponentially with the truncation level. Our method achieves the order-optimal sample complexity of (c=2) for robust policy evaluation and robust average reward estimation, marking significant ad- vancement in robust reinforcement learning theory.
Introduction
Reinforcement learning (RL) has achieved notable success in domains such robotics 33 fi-
nance [17], healthcare (44), transportation (0) and large language models (30] by enabling agents to learn optimal decision-making strategies through interaction with environment. However, in many real-world applications, direct interaction is impractical due to safety concerns, high costs, or limited data collection budgets (32. 19]. This challenge particularly evident in scenarios where agents are trained in simulated environments before being deployed in the real world, such as in robotic control and autonomous driving. The mismatch between simulated and real environments, known as the simulation colllatioontorrallty to-reality gap, often leads to performance degradation when the learned policy encounters unmodeled uncertainties. Robust reinforcement learning (robust RL) addresses this challenge by formulating the learning problem as an optimization over an uncertainty set of transition probabilities, ensuring reliable performance under worst-case conditions. In this work, we focus on the problem of evaluating the robust value function and robust average reward for given policy using only data sampled from simulator (nominal model), aiming to enhance generalization and mitigate the impact of transition uncertainty in real-world deployment.
Reinforcement learning problems under infinite time horizons typically studied under two pri- mary reward formulations: the discounted-reward setting, where future rewards are exponentially
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

discounted, and the average-reward setting, which focuses on optimizing long-term performance. While the discounted-rewan formulation is widely used, it may lead to myopic policies that un- derperform in applications requiring sustained long-term efficiency, such as queueing systems, in- ventory management, and network control. In contrast, the average-reward setting is more suitable for environments where decisions impact long-term operational efficiency. Despite its advantages, robust reinforcement learning under the average-reward criterion remains largely unexplored. Ex- isting works robust average-reward RL primarily provide asymptotic guarantees (37 39 38). lacking algorithms with finite-time performance bounds. This gap highlights the need for principled approaches that ensure robustness against model uncertainties while maintaining strong long- term performance guarantees.
Solving the robust werage-reward reinforcement learning problem is significantly more challenging than its non-robust counterpart, with the primary difficulty arising in policy evaluation. Specifically, the goal is to compute the worst-case value function and worst-case average reward over entire uncertainty set of transition models while having access only to samples from a nominal transition model. In this paper, we investigate three types of uncertainty sets: Contamination uncertainty sets, total variation (TV) distance uncertainty sets, and Wasserstein distance uncertainty sets. Unlike the standard average-reward setting, where value functions and average rewards can be estimated directly from observed trajectories [41. 2. 12. 13, [4), the robust setting introduces an additional layer of complexity due to the need to optimize against adversarial transitions. Consequently, con- ventional approaches based on direct estimation such as [41 12 13, [4] immediately fail, as they do not account for the worst-case nature of the problem. Overcoming this challenge requires new algorithmic techniques that can infer the worst-case dynamics using only limited samples from the nominal model.
1.1 Challenges and Contributions
A common approach to policy evaluation in robust RL is to solve the corresponding robust Bellman operator. However, robust average-reward RL presents additional difficulties compared to the ro- bust discoonted-rewaat setting. In the discounted case, the presence of a discount factor induces a contraction property in the robust Bellman operator [40, 46). facilitating stable iterative updates. In contrast, the average-reward Bellman operator lacks contraction property with respect to any norm even in the non-robust setting [45], making standard fixed-point analysis inapplicable. Due this fundamental limitation, existing works on robust average-reward RL such as (39) rely on asymp- totic techniques, primarily leveraging ordinary differential equation (ODE) analysis to examine the behavior of temporal difference (TD) learning. These methods exploit the asymptotic stability of the corresponding ODE [6] to establish almost sure convergence but fail to provide finite-sample performance guarantees. Addressing this limitation requires novel analytical tools and algorithmic techniques capable of providing explicit finite-sample bounds for robust policy evaluation and opti- mization.
In this work, we first establish and exploit a key structural property of the robust average-reward Bellman operator with uncertainty set P under the ergodicity of the nominal model: it is a con- traction under some semi-norm, denoted as || llp, where the detailed construction is specified in Theorem
4.2 and (5). Constructing || ||/p is not straightforward, because ergodicity alone only guarantees that the chain mixes over multiple steps and fails to produce a single-step contraction for familiar measures such as the span semi-norm. To overcome this, we group together all the worst-case transition dynamics under uncertainty into one compact family of linear mappings, and observe that their "worst-case gain" over any number of steps stays strictly below 1. From this we build an extremal norm, which by construction shrinks every non-constant component by the same fixed factor in single step. Finally, we add small "quotient" correction that exactly annihilates constant shifts, producing a semi-norm that vanishes only on constant functions but still inherits the one-step shrinkage. The above construction yields uniform, strict contraction for the robust Bellman operator.
This fundamental result above enables the use of stochastic approximation techniques similar to [45] to analyze and bound the error policy evaluation, overcoming the lack of standard contraction property that has hindered prior finite-sample analyses. Building on this insight, we develop a novel stochastic approximation framework tailored to the robust average-reward setting. Our approach simultaneously estimates both the robust value function and the robust average reward, leading to

---

an efficient iterative procedure for solving the robust Bellman equation. A critical challenge in this framework under TV and Wasserstein distance uncertainty sets is accurately estimating the worst- case transition effects, which requires computing the support function of the uncertainty set. While previous works 5 391 have leveraged Multi-Level Monte Carlo (MLMC) for this task, their MLMC-based estimators suffer from infinite expected sample complexity due to the unbounded nature of the required geometric sampling, leading to only asymptotic convergence. To address this, we introduce truncation mechanism based on truncated geometric distribution, ensuring that the sample complexity remains finite while maintaining an exponentially decaying bias. With these techniques, we derive the first finite-samin sample complexity guarantee for policy evaluation in robust average-reward RI,, achieving an optimal (( sample complexity bound. The main contributions of this paper are summarized as follows:
We prove that under the ergodicity assumption of the nominal model, the robust average-reward Bellman operator is contraction with respect to a suitably constructed semi-norm (Theorem 4.2). This key result enables the application of stochastic approximation techniques for policy evaluation.
We prove the convergence of stochastic approximation under the semi-norm contraction and under i..dd. with noise with non-zero bias (Theorem B. as an intermediate result.
We develop an efficient method for computing estimates for the robust Bellman operator under TV distance and Wasserstein distance uncertainty sets. By modifying MLMC with truncated geometric sampling scheme, we ensure finite expected sample complexity while keeping variance controlled and bias decaying exponentially with truncation level (Theorem 5.145.4).
We propose a novel temporal difference learning method that iteratively updates the robust value function and the robust average reward, facilitating efficient policy evaluation in robust average- reward RL. We establish the first non-asy asymptotic sample complexity result for policy evaluation in robust average-reward RL, proving an order-optimal (E complexity for policy evaluation (Theorem 6. along with a Ö(E complexity for robust average-reward estimation (Theorem
6.2
2
Related Work
The theoretical guarantees of robust average-reward reinforcement learning have been studied by the following works. (37] takes a model-based perspective, approximating robust average-reward MDPs with discounted MDPs and proving uniform convergence of the robust discounted value function as the discount factor approaches one, employing dynamic programming and Blackwell optimality ar- guments to characterize optimal policies. [39] proposes a model-free approach by developing robust relative value iteration (RVT) TD and Q-learning algorithms, proving their almost sure convergence using stochastic approximation, martingale theory, and Multi-Level Monte Carlo estimators to han- dle non-line non-linearity in the robust Bellman operator. While these studies provide fundamental insights into robust reward RL, they do not establish explicit convergence rate guarantees due to the lack of contraction properties in the robust Bellman operator. In addition, [3] 35) study the policy optimization of average-reward robust MDPs assuming direct queries of the sub-gradient informa- tion.
Policy evaluation in robust disscounted-rewarn reinforcement learning with finite sample guarantees has been extensively studied, with the key recent works [40, 46. 25, 24, 23 focusing on solving the robust Bellman equation by finding its fixed-point solution. This approach made feasible by the contraction property of the robust Bellman operator under the sup-norm, which arises due to the presence of a discount factor y < 1. However, this fundamental approach does not directly extend to the robust weward setting, where the absence of discount factor removes the contraction property under any norm. As a result, existing robust discounted methods cannot be applied in the robust average-reward RL setting.
Recently, growing body of concurrent work has established fnite-sample guarantees for robust average-reward reinforcement learning. Model-based approaches include (29. 10). and (28) devel- ops a model-free value-iteration method under contamination and E,--ball uncertainty sets. While these results significantly advance the area, the specific problem of policy evaluation in robust average-reward MDPs has not yet been addressed in terms of sample complexity. Our work tar- gets this gap.
3

---

3 Formulation
3.1 Robust average-reward MDPs.
For robust MDP with state space S and action space A while |S] = S and |AI = A, the transition kernel is assumed be in some uncertainty set P. At each time step, the environment transits the next state according to an arbitrary transition kernel P E P. In this paper, we focus on the (s, a)- rectangular compact uncertainty set (27 22 i.e., P X a.a Pa where P. S A(S), and A denotes the probability simplex. Popular uncertainty sets include those defined by the contamination model 21 40), total variation [26], and Wasserstein distance 11]].
We investigate the worst-case average-reward over the uncertainty set of MDPs. Specifically, define the robust average-reward of a policy π as
(b)
min
lim
ET
Σ
So
RE
P T
T
0
where K (Pu. PI..) E
n20 P. It was shown in [37] that the worst case under the time-varying model is equivalent the one under the stationary model:
T-1 Σ 1=
(
min lim E.. PEP T
T
r =
Therefore, we limit our focus to the stationary model. We refer the minimizers of as the worst-case transition kernels for the policy æ,, and denote the set of all possible worst-case transition kernels by 22 i.e., 22 & {P E P g5 = 9p where op denotes the average reward of policy π under the single transition P E P:P:
T-1 Σ n=0
9 (
($)
A
lim ET.
S. =
(3)
T-000
T
We focus on the model-free setting, where only samples from the nominal MDP denoted as (the centroid of the uncertainty set) are available. We investigate the problem of robust policy evaluation and robust average reward estimation, which means for given policy т, we aim to estimate the robust value function and the robust average reward. Throughout this paper, we make the following standard assumption regarding the structure of the induced Markov chain.
Assumption 3.1. The Markov chain induced by æ is irreducible and aperiodic for the nominal model P.
In contrast to many current works on robust average-reward RL 37. 39, 38, 31, 28), Assumption 3.]
requires only that the center of the uncertainty set be irreducible and aperiodic. We note that when the radius of uncertainty sets is small enough, Assumption (.100 can ensure that p is irreducible and aperiodic for all P E P. This ensures that, under any transition model within the uncertainty set, the policy induces single recurrent communicating class. A well-known result in average-reward MDPs states that under Assumption B.J the average reward is independent of the starting state, i.e., for any
and all s, s' S, we have (s) = (s'). Thus, we can drop the dependence on the initial state and simply write de as the robust average reward. We now formally define the robust value function V by connecting it with the following robust Bellman equation:
Theorem 3.2 (Robust Bellman Equation, Theorem 3.1 in 39). ). If (g, V) is solution to the robust Bellman equation
((s) = - (clls)(F(s. g (V)),, V
(4)
a
where d's (V) minpep: pT is denoted as the support function, then the scalar corresponds the robust average reward, i.e., g Sp. and the worst-case transition kernel Py belongs the
set of minimizing transition kernels, i.e., Pv E ST where D A E P: 96 g Furthermore,
the function V is unique up to an additive constant, where if is a solution to the Bellman equation,

---

then we have -= VV + ce. where E E and e is the all-ones vector in R and Vpv is defined as the relative value function of the policy under the single transition Pv as follows:
20
Vp (8) 2 Ex.PV
Σ (Tr
gP =
(5)
Theorem 3.2 implies that the robust Bellman equation identifies both the worst-case average reward y and corresponding value function V that is determined only up an additive constant. In partieular, Op (V) represents the worst-case transition effect over the uncertainty set Pa Unlike the robust discounted case, where the contraction property of the Bellman operator under the sup-norm enables straightforward fixed-point iteration, the robust average-reward Bellman equation does not induce contraction under any norm, making direct iterative methods inapplicable. Throughout the paper, we denote e as the all-ones vector in R.S. We now characterize the explicit forms of op: (V) for different compact uncertainty sets follows:
Contamination Uncertainty Set The contamination uncertainty models outliers or rare faults 77. Specifically, the ò-contamination uncertainty set P. {[1 : + ōg q E A(S)), where 0 < 6 < 1 is the radius. Under this uncertainty set, the support function can be computed as
Opy (V) (1 - 8)(P)) + m V(s).
(6)
and this is linear in the nominal transition kernel Pg.
Total Variation Uncertainty Set. The total variation (TV) distance uncertainty set models cate-
gorical misspecification or discretization error [18), and is characterized as P = {q E A(
llgg - P0] | S 6}, define |ss as the span semi-norm and the support function can be computed
using its dual function 22
Pp (V) max ((P?) (V- #20
- -4) 1)
- 0lV =llap).
Wasserstein Distance Uncertainty Sets. The Wasserstein distance uncertainty Models smooth
model drift when states have a geometry [1]]. Consider the metric space (S, d) by defining some distance metric d. For some parameter (o) and two distributions p.g E A(S), define the !-Wasserstein distance between them as Wi(g.p) = iinfuer(p-g)) [|d]|u. where I'(p, q) denotes the
distributions over S x S with marginal distributions and ||d]| (E [d(X,)) The Wasserstein distance uncertainty set then defined as
ped = {u E A(S) Wi(P,, 4) < 8].
(8)
The support function w.r.t. the Wasserstein distance set, can be calculated as follows 15
(210' + Epp inf (V(2) Ad(S.
p (V) sup X
(9)
3.2 Robust Bellman Operator
Motivated by Theorem 3.2 define the robust Bellman operator, which forms the basis for our policy evaluation procedure.
Definition 3.3 (Robust Bellman Operator, 39 ) The robust Bellman operator T, is defined as:
(V) Σ <(cls)(F(s..)) - (V)], Vs E S.
(10)
The operator T, transforms a value function V by incorporating the worst- transition effect. A key challenge solving the robust Bellman equation that T, does not satisfy contraction under standard norms, preventing the use of conventional fixed-point iteration. To cope with this problem, we establish that T, is contraction under some constructed semi-norm. This allows us further develop provably efficient stochastic approximation algorithms.
5

---

Semi-Norm Contraction of Robust Bellman Operators
Under Assumption 3.1 we are able to establish the semi-norm contraction property. For motivation, we first establish the semi-norm contraction property of the non-robust average-reward Bellman operator for a policy x under transition defined as follows:
(v))s) - Σ (alss)[r(s.a) + P(s'sss.a)viss E
π -
(11)
Lemma 4.1. Let S be a finite state space, and let π be a stationary policy. If the Markov chain induced by πI under the transition P irreducible and aperiodic, there exists semi-norm ||- with kernel {ce: c. E IR} and a constant 3 E (0, 1) such that for all V1, V22 E IR and any E I,
(VT (V))) S 8 - V21lp-
(12)
Proof ProofSketch Under ergodicity, the one-step transition matrix (denoted as PT) has unique station- ary distribution d", define the stationary projector = e d", then the fluctuation matrix (defined as Q p - Σ) has all eigenvalues strictly inside the unit circle. Standard finiteddimensional theory (via the discrete Lyapunov equation (20]) would produce a norm || llQ on IR such that there a constant a E (0, 1) such that for any x R$, =|@==ll I a | We then build the semi-norm
as follows:
| 110 + inf || cella. <<< <<<cl-a,
(13)
cElt
so that its kernel is exactly the constant vectors (the second term vanishes only on shifts of e) and the first term enforces one-step shrinkage by 8
1. A short calculation then shows ||PTz||p= S 3 @||=|||.. yielding the desired contraction, which leads to the overall result.
The concrete proof of Lemma 4. including the detailed construction of the semi-norm || |l is in Appendix [ where the properties of irreducible and aperiodic finite state Markov chain are utilized. Thus, show the (non-robust) sverage-rewarde Bellman operator T, is strict contraction under || llp. Based the above motivations, the robust average-reward Bellman operator by leveraging Lemma and the compactness of the uncertainty sets.
formally establish the contraction property of
Theorem 4.2. Under Assumption 3.1 if is compact, with certain restrictions the radius of the uncertainty sets, there exists a semi-norm || -|pp with kernel {ce : c E R} such that the robust Bellman operator Tg is contraction. Specifically, there exist y (0, 1) such that
(V1) (V2)ll I > >IVV - Valle, A V1, V/2 E R . E.R.
(14)
Proof Sketch For any P P. the one-step transition matrix p has a unique stationary projector Ep due to ergodicity. Since P is compact, the family fluctuation matrices {Qp = p - Ep : P e P) has joint spectral radius strictly less than 1. By Lemma FlIn B. one is able to construct an "extremal norm" (denoted as ||. (lexx under which every QF contracts by a uniform factor a E (0, 1). Mimicking the non-robust case in Lemma we similarly define
|||||p = sup PEP
||Qazllext + inf || - ce celext, cER
o<e<l-a.
(15)
The supremum zeros out if & E foe : E R) and it inherits the uniform one-step shrinkage by a. Adding the small quotient term fixes the kernel without spoiling 7 = a++e < 1, so one shows
(M)) - (V))ll S >>IlV - V2llp for all PEP
(16)
The above leads to the desired results.
The concrete proof of Theorem 4.2 along with the detailed construction of the semi-norm || || and the specific radius restrictions on various uncertainty sets are Appendix A.2 Since all the uncertainty sets listed in Section 3.1 closed and bounded in a real vector space, these uncertainty sets are all compact and satisfy the contraction property in Theorem 42 We also note that the
contraction factor y relates to the joint spectral gap of the family {Q} P PJ.

---

Efficient Estimators for Uncertainty Sets
To utilize the contraction property in Section obtain convergence rate results, idea is perform the following iterative stochastic approximation:
(s) - Vi(s + Th - -
E
(17)
where the learning rate would be specified Section 6 The detailed analysis and complexities of the general stochastic approximation in the form of 11 is provided in Appendix Theorem [B.]
implies that if T, (V), being an estimator of (V), could be constructed with bounded variance and small bias, V, converges to a solution of the Bellman equation in 4 However, the challenge of constructing our desired T (V) lies in the construction of the support function estimator Op (V).
In this section, we aim to construct an estimator 6 (V) for all s E S and a E A various uncertainty sets. Recall that the support function Tp- (V) represents the worst-case transition effect over the uncertainty set p as defined in the robust Bellman equation in Theorem (322 The explicit forms of op (V) for different uncertainty sets were characterized in (6)-()) Our goal in this section construct efficient estimators opy (V) that approximates opy (V) while maintaining controlled variance and finite sample complexity.
Linear Contamination Uncertainty Set Recall that the ó-contamination uncertainty set is Pa ((1-6) P) ōg 9 A(S)), where 0 < 6 < 1 is the radius. Since the support function can be computed by (6) and the expression is linear in the nominal transition kernel Pg. A direct approach is to use the transition to the subsequent state to construct our estimator:
ōp: (V) A (1 (s') + min (ix),
(18)
where s' is a subsequent state sample after (s,a). Hence, the sample complexity of 18 is just one. Lemma [3 from [39] states that opy (V) obtained by (18) is unbiased and has bounded variance as follows:
E Topp (V) = op: (V), and Var(op; (V)) S |V
(19)
Nonlinear Contamination Sets Regarding TV and Wasserstein distance uncertainty sets, they have a nonlinear relationship between the nominal distribution P. and the support function dpp (V). Previous works such [4. 5. 39 have proposed Multi-Level Monte-Carlo (MLMC) method for obtaining an unbiased estimator Op: (V) with bounded variance. However, their approaches require drawing 2 samples where N is sampled from a geometric distribution Geom (V) with parameter (0, 0.5). This operation would need infinite samples in expectation for obtaining each single estimator as E[2N+1] = "N= N (1(1 V)
N= 21 2 + co. To handle the above problem, we aim to provide an estimator d.p. (V) with finite sample complexity and small enough bias. We construct a Muncated-MLMM. estimator under geometric sampling with parameter = 0.5 as shown in Algorithm
In particular, if n < Ninxx then (N' = n) = (N =n) n) with probability (1) while (N' Nmax] has probability Σm= (1/2)m+1 = 2- --aa After obtaining N Algorithm [ then
collects a set N i.i.d. samples from the nominal transition model to construct empirical estimators for different transition distributions. The core of the approach lies in computing the support function estimates for TV and Wasserstein uncertainty sets using a correction term AN (V), which accounts for the bias introduced by truncation. This correction ensures that the final estimator maintains low bias while achieving a finite sample complexity. This truncation technique has been widely used in prior work across different settings such crucial properties of Algorithm[] [[
[36. 14
43). We now present several
Theorem 5.1 (Finite Sample Complexity). Under Algorithm 7 denote M = N24+1 as the random number of samples (where N' min (N, Nmax }). Then
E[M] = Nmax + 2 = O(Nmax)
(20)
The proof of Theorem 5.1
in Appendix C.I which demonstrates that setting the geometric sam-
pling parameter to V 0.5 ensures that the expected number of samples follows linear growth
7

---

Algorithm Truncated MLMC Estimator for TV and Wasserstein Uncertainty Sets
Input: S, a E A, Max level Nuax: Value function V
I: Sample N Geom((.55
2: N' + min,N, ( ]
3: Collect 2 Lid.. samples of {s with s/ ~ Pa for each i
4: Pa.E
s,N'+1
< 2 1i (62.))
5: Pa.0
f 2 Limi 1022111
4,N'41
6: Pa
,,N' f 2 Ei= (x()
7: $a.1
s,N'+1 <
{+1}
8: IV then Obtain Jp A.
(V), (V), Op..
(p),opu.o (V) from
0,8'
2,N+
9: else if Wasserstein then Obtain opu..
(V), Tp
(V),
(V), ppn.o
(V) from
9
10: end if
(V) - - ${[opue (V) + opp. (M)
11: Av. (V) pp 2.N'
(V)
12: ōpy (V) t ppn. 2.14+1
Av(V) (V) P(N=R))
where p'(n) PPN' = n) return ppy(V)
pattern rather than an exponential one. This choice precisely cancels out the effect of the exponential sampling inherent in the truncated MLMC estimator, preventing infinite expected sample complex- ity. This result shows that the expected number of queries grows only linearly with Nmax, ensuring that the sampling cost remains manageable even for large truncation levels. The key factor enabling this behavior is setting the geometric distribution parameter to 0.5, which balances the probability mass across different truncation levels, preventing an exponential increase in sample complexity.
Theorem 5.2 (Exponentially Decaying Bias). Let op: (V) be the estimator of a (V) obtained from Algorithm then under TV uncertainty set, we have:
[B (V) dpy (V)] S 6(1 $)322
Nmaz |V sp
(21)
where 5 denotes the radius of TV distance. Under Wasserstein uncertainty set, we have:
[[ (V) dpy (V)] S 6. Nmax |Vilsp
(22)
Theorem 5.2 estabbishhss that the bias of the truncated MLMC estimator decays exponentially with Nmax. ensuring that truncation does not significantly affect accuracy. This result follows from ob- serving that the deviation introduced by truncation can be expressed as sum of differences between support function estimates at different level, and each of which is controlled by the & -ddistance between transition distributions. Thus, exponentially decaying bias.
use binomial concentration property to ensure the
The proof of Theorem 5.2 is in Appendix
One important lemma used in the proof is the following Lemma where we show the Lipschitz property for both TV and Wasserstein distance uncertainty sets.
C
Lemma 5.3. For any p,q E A(S), let Pry and Qrv denote the TV distance uncertainty set with radius centering at p and respectively, and let Pw and Qw denote the Wasserstein distance uncertainty set with radius 8 centering at p and q respectively. Then for any value function V. we have:
|oprv (V) - oerv (V) (1+ 1 1 M1V 4ll and Jopw (V) 22 (V) [[ qlla
(23)
We refer the proof of Theorem 5.2 to Appendix C
Theorem 5.4 (Linear Variance). Let op= (V) be the estimator of ape (V) obtained from Algorithm
7 then under TV distance uncertainty set, we have:
Var(op: (V)) s 3 144(1 + 1
) 2 Nmax
(24)
8

---

and under Wasserstein distance uncertainty set, we have:
Var(ōrp (V)) = 3 + 1
(25)
Theorem 5 4 establishes that the variance of the truncated MLMC estimator grows linearly with Nmax. ensuring that the estimator remains stable even as the truncation level increases. The proof of Theorem is in Appendix C.4 which follows from bounding the second moment of the estimator by analyzing the variance decomposition across different MLMC levels. Specifically, by expressing the estimator in terms of successive refinements of the transition model, we show that the variance accumulates additively across levels due to the binomial concentration property.
6 Robust Average-Reward TD Learning
Equipped with the methods of constructing åp: (V) for all E S and E A. we now present the formal algorithm for robust policy evaluation and robust average reward for a given policy x in Algorithm 2 Algorithm 2 presents robust temporal difference (TD) learning method for policy evaluation in robust average- reward MDPs. This algorithm builds upon the truncated MLMC esti- mator (Algorithm and the biased stochastic approximation framework in Section ensuring both efficient sample complexity and finite-time convergence guarantees.
The algorithm is divided into main phases. The first phase (Lines 1-7) estimates the robust value function. The noisy Bellman operator is computed using the estimator op (V:) obtained depending on the uncertainty set type. Then the iterative update follows stochastic approximation scheme with stepsize The ensuring convergence while maintaining stability. Finally, the value function is centered an anchor state so remove the ambiguity due its additive invariance. The second phase (Lines 8-14) estimates the robust average reward by utilizing VT from the output of the first phase. The expected Bellman residual (s) is computed across all states and averaging òt. A separate stochastic approximation update with stepsize 3, then applied to refine gt, ensuring convergence to the robust worst-case average reward. By combining these two phases, Algorithm provides an efficient and provably convergent method for robust policy evaluation under average- reward criteria, marking significant advancement over prior methods that only provided asymptotic guarantees.
obtain
Algorithm 2 Robust Iverage-Reward TD
Input: Policy x, Initial values Vo. go = 0, Stepsizes nes Br, Max level Nmaxx Anehor state 80 E S
1: for = 0, 1,, T
do for each (s. S do
2:
3:
Contamination then Sample åp (V₂) according to 18
4:
else TV or Wasserstein then Sample o (V/) according to Algorithm [ 5: end if
6:
end for
7:
Too (V))(s) < E. (alls)(r(s,a) do tpp (V)),,
Vs
8: (s) VV((s + mh (v) vi(ss): VsE
9:
(s) (s) Vit1(s0), Vs E
10: end for
11: for tort- = 0. .,. 1
12:
for each (s, a) S do if Contamination then Sample 6p: (Vi) according 18 else if TV Wasserstein then Sample p (V,) according to Algorithm end end for
13:
14:
15:
16:
17:
(s() + E. (s)))) + +0p; (Vr) - Vi), As E
18:
5. - 1
19:
St-1 1 gt + Br g9) gr)
20: end for return VT. gr

---

To derive the sample complexity of robust policy evaluation, we utilize the semi-norm contraction property the Bellman operator in Theorem and fit Algorithm@iinto the general biased stochas- tic approximation result in Theorem B. while incorporating the bias analysis characterized in Sec-
tion [ Since each phase of Algorithm 2 contains a loop of length T with all the states and actions updated together, the total samples needed for the entire algorithm in expectation is ATATE N max where max] is one for contamination uncertainty sets and ((Nmax) from Theorem 5. for TV and Wasserstein distance uncertainty sets.
Theorem 6.1. V. is generated by Algorithm 2 and satisfying Assumption 3.1 then if the stepsize T ( we require a sample complexity of O SAr.
for contamination uncertainty set and
2(1--)²
a sample complexity of Ō S.A 2(1-))" for TV and Wasserstein distance uncertainty set to ensure an convergence of Vr. Moreover, these results are order-optimal in terms of
Theorem 6.2. If 9t is generated by Algorithm 2 and satisfying Assumption 3.1 then if the step-
size Br = O we require sample complexity of Ô Wasserstein distance uncertainty set to ensure convergence of 9r.
for all contamination, TV, and --(--)>
SAL mix
The formal version of Theorems 6.1 and 6.2 along with the proof's are Appendix Theorem [
provides the order-optimal sample complexity of ((e=?) for Algorithm[ājo achieve an e-accurate es- timate of Vr. Although Theorem [. I.lcaams order-optimal in terms of e, we do not claim tightness in S, and y. and treat sharpening these dependencies as open. The proof of Theorem 6.2 extends the analysis of Theorem 1. robust average reward estimation. The key difficulty lies in controlling the propagation of error from value function estimates reward estimation. By again leveraging the contraction property and appropriately tuning stepsizes, establish Õ complexity bound for robust average reward estimation.
7 Conclusion
This paper provides the first finite-sample analysis for policy evaluation in robust average-reward MDPs, bridging a gap where only asymptotic guarantees existed. By introducing biased stochas- tic approximation framework and leveraging the properties of various uncertainty sets, establish finite-time convergence under biased noise. Our algorithm achieves an order-optimal sample com- plexity of ((=22) for policy evaluation, despite the added complexity of robustness.
A crucial step in analysis is proving that the robust Bellman operator is contractive under constructed semi-norm || |lp, ensuring the validity of stochastic approximation updates. We further develop truncated Multi-Level Monte Carlo estimator that efficiently computes worst-case value functions under total variation and Wasserstein uncertainty, while keeping bias and variance con- trolled. One limitation of this work is that the results require ergodicity hold in the setting, as stated in Assumption 3.T Additionally, scaling the algorithm and results the paper via function approximations remains important open problem.
Acknowledgments
We would like to thank Zaiwei Chen of Purdue University for assistance with identifying relevant literature and for constructive feedback. We also thank Zijun Chen and Nian Si of The Hong Kong University of Science and Technology for helpful discussions regarding Appendix A Finally, we thank the anonymous reviewers for insightful comments that substantially improved the paper.
References
[1] Abubakr O Al-Abbasi, Arnob Ghosh, and Vaneet Aggarwal. Deeppool: Distributed model-free algorithm for ride-sharing using deep reinforcement learning. IEEE Transactions on Intelligent Transportation Systems, 20 20(12):47144472) 2019.
[2] Qinbo Bai, Washim Uddin Mondal, and Vaneet Aggarwal. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pages 10980-10988, 2024.
10

---

[3] Mare A Berger and Yang Wang. Bounded semigroups of matrices. Linear Algebra and its Applications. 166:21-27, 1992.
[4] Jose H Blanchet and Peter W Glynn. Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization. In 2015 Winter Simulation Conference (WSC), pages 3656-36666 3667. IEEE, 2015.
[5] Jose H Blanchet, Peter W Glynn, and Yanan Pei. Unbiased multilevel Monte Carlo: Stochas- tic optimization, steady-state simulation, quantiles, and other applications. arXiv preprint 2019.
[6] Vivek S Borkar and Vivek S Borkar. Stochastic approximation: dynamical systems viewpoint, volume 100. Springer, 2008.
[7] Mengjie Chen, Chao Gao, and Zhao Ren. A general decision theory for huber's 6- contamination model. Electronic Journal of Statistics, 10:3752-3774, 2016.
[8] Zaiwei Chen, Siva Theja Maguluri, Sanjay Shakkottai, and Karthikeyan Shanmugam. Finite- sample analysis of contractive stochastic approximation using smooth convex envelopes. Ad- vances Neural Information Processing Systems, 33:8223-8234 2020.
[9] Zaiwei Chen, Sheng Zhang, Zhe Zhang, Shaan UI Haque, and Siva Theja Maguluri. A non- asymptotic theory of seminorm Yyapumov stability: From deterministic to stochastic iterative algorithms. arXiv preprint arXiv:2502. 14208, 2025.
[10] Zijun Chen, Shengbo Wang, and Nian Si. Sample complexity of distributionally robust average- reward reinforcement learning. arXiv preprint arXiv:2505.10007, 2025.
[11] Julien Grand Clement and Christian Kroer. First-order methods for wasserstein distributionally robust mdp. In International Conference on Machine Learning, pages 2010-2019. PMLR, 2021.
[12] Swetha Ganesh and Vaneet Aggarwal. Regret analysis of average-reward unichain mdps via an actor-critic approach. Advances in Neural Information Processing Systems, 2025.
[13] Swetha Ganesh, Washim Uddin Mondal, and Vaneet Aggarwal. Order-optimal regret with novel policy gradient approaches in anfinitehhorizon average reward mdps. In International Conference on Artificial Intelligence and Statistics, pages 3421-34299 PMLR, 2025.
[14] Swetha Ganesh, Washim Uddin Mondal, and Vanect Aggarwal. A sharper global convergence analysis for average reward reinforcement learning via actor-critic approach. In Forty- second International Conference on Machine Learning, 2025.
[15] Rui Gao and Anton Kleywegt. Distributionally robust stochastic optimization with wasserstein distance. Mathematics of Operations Research, 48(2):603-655, 2023.
[16] Stéphane Gaubert and Zheng Qu. Dobrushin's is ergodicity coefficient for markov operators on cones. Integral Equations and Operator Theory, 81(1):127-150, 2015.
[17] Ben Hambly, Renyuan Xu, and Huining Yang. Recent advances in reinforcement learning in finance. Mathematical Finance, 33(3):4375503 2023.
[18] Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Partial policy iteration for 11 11-robust markov decision processes. Journal of Machine Learning Research, 22(275):1 2021.
[19] Sebastian Höfer, Kostas Bekris, Ankur Handa, Juan Camilo Gamboa, Melissa Mozifian, Flo- rian Golemo, Chris Atkeson, Dieter Fox, Ken Goldberg, John Leonard, et al. Sim2real in robotics and automation: Applications and challenges. IEEE transactions on automation sci- ence and engineering, 18(2):398 400, 2021.
[20] Roger A Horn and Charles R Johnson. Matrix analysis. Cambridge university press, 2012.
[21] Peter J Huber. robust version of the probability ratio test. The Annals of Mathematical Statistics, pages 1753-1758, 1965.

---

[22] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-280, 2005.
[23] Yufei Kuang, Miao Lu, Jie Wang, Qi Zhou, Bin Li, and Houqiang Li. Learning robust pol- icy against disturbance in transition dynamics via state-conservative policy optimization. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 7247-7254, 2022.
[24] Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Y Levy, and Shie Mannor. Policy gra- dient for rectangular robust markov decision processes. Advances in Neural Information Pro- cessing Systems, 36:59477-5900 -59001, 2023.
[25] Yan Li, Guanghui Lan, and Tuo Zhao. First-order policy optimization for robust markov deci- sion process. arXiv preprint 22x::2209.10779 2022.
[26] Shiau Hong Lim, Huan Xu, and Shie Mannor.
Reinforcement learning in robust markov deci- sion processes. Advances in Neural Information Processing Systems, 26, 2013.
[27] Arnab Nilim and Laurent El Ghaoui. Robustness in markov decision problems with uncertain transition matrices. Advances in neural information processing systems, 16, 2003.
[28] Zachary Roch, Chi Zhang, George Atia, and Yue Wang. A finite-sample analysis of distri- butionally robust average-reward reinforcement learning. arXiv preprint arXiv:2505. 12462, 2025.
[29] Zachary Andrew Roch, George K Atia, and Yue Wang. A reduction framework for distribu- tionally robust reinforcement learning under average reward. In Forty-second International Conference Machine Learning, 2025.
[30] Saksham Sahai Srivastava and Vaneet Aggarwal. A technical survey of reinforcement learning techniques for large language models. arXiv preprint arXiv:2507.04/ 26070 2025.
[31] Zhongehang Sun, Sihong He, Fei Miao, and Shaofeng Zou. Policy optimization for robust aver- age reward mdps. In The Thirth-eighth Annual Conference Neural Information Processing Systems, 2024.
[32] Niko Sünderhauf, Oliver Brock, Walter Scheirer, Raia Hadsell, Dieter Fox, Jürgen Leitner, Ben Upcroft, Pieter Abbeel, Wolfram Burgard, Michael Milford, al. The limits and potentials of deep learning for robotics. The International journal of robotics research, 37(4-5):405-420 2018.
[33] Chen Tang, Ben Abbatematteo, Jiaheng Hu, Rohan Chandra, Roberto Martin-Martin, and Peter Stone. Deep reinforcement learning for robotics: A survey of real-world successes. In Pro- ceedings of the AAAI Conference on Artificial Intelligence, volume 39, pages 28694-28698, 2025.
[34] Jinghan Wang, Mengdi Wang, and Lin F Yang. Near sample-optimal reduction- policy learning for average reward mdp. arXiv preprint arXiv:2212.00600 2022.
[35] Qiuhao Wang, Yuqi Zha, Chin Pang Ho, and Marek Petrik. Provable policy gradient for ro- bust average-reward mdps beyond rectangularity. In Forty-second International Conference Machine Learning, 2025.
[36] Yudan Wang, Shaofeng Zou, and Yue Wang. Model-free robust reinforcement learning with sample complexity analysis. In Uncertainty in Artificial Intelligence, pages 3470-3513, PMLR, 2024.
[37] Yue Wang, Alvaro Velasquez, George Atia. Ashley Trater-Bennette and Shaofeng Zou. Ro- bust average-reward markov decision processes. Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 15215-15223, 2023.
[38] Yue Wang, Alvaro Velasquez, George Atia, Ashley average-reward reinforcement learning. Journal of Artificial Intelligence Research, 80:719- 803, 2024.
and Shaofeng Zou, Robust
12

---

[39] Yue Wang, Alvaro Velasquez, George K Atia, Ashley Prater- and Shaofeng Zou. Model-free robust average-reward reinforeement learning. In International Conference on Machine Learning, pages 36431-36466 PMLR, 2023.
[40] Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In International conference on machine learning. pages 23484 23526.. PMLR, 2022.
[41] Chen-Ye Yu Wei, Mehdi Jafarnia Jahromi, Haipeng Luo, Hiteshi Sharma, and Rahul Jain. Model- free reinforcement learning in infinite-horizon average- reward markov decision processes. In International conference on machine learning, pages 10170-10180. PMLR, 2020.
[42] Fabian Wirth. The generalized spectral radius and extremal norms. Linear Algebra and its Applications, 342(1-3):17-40, 2002.
[43] Yang Xu and Vaneet Aggarwal. Accelerating quantum reinforcement learning with quantum natural policy gradient based approach. In Forty-second International Conference on Machine Learning, 2025.
[44] Chao Yu, Jiming Liu, Shamim Nemati, and Guosheng Yin. Reinforcement learning in health- A survey. ACM Computing Surveys (CSUR), 55(1):1-36. 2021.
[45] Sheng Zhang, Zhe Zhang, and Siva Theja Maguluri. Finite sample analysis of average-reward td learning and q-learning. Advances in Neural Information Processing Systems, 34: 1230-
1242, 2021.
[46] Ruida Zhou, Tao Liu, Min Cheng, Dileep Kalathil, PR Kumar, and Chao Tian. Natural actor- critic for robust reinforcement learning with function approximation. Advances in neural in- formation processing systems, 36, 2024.
13

---

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]
The claims made in the abstract and introduction accurately reflects the nov- elty and contributions of this paper. All details can be found either in the rest of the main text or in the appendix.
Justification:
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made 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
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.
is fine to include aspirational goals as motivation as long as it 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]
Justification:
The discussion of limitations can be found in the conclusion.
Guidelines:
The answer NA means that the paper has 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 separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (c.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The au- thors should reflect on how these assumptions might be violated practice and what the implications would be.
The authors should reflect 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 on the factors that influence the performance of the ap- proach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or a speech-to-tex system might not be used reliably provide closed captions for online lectures because 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 ad- dress problems of privacy and faimeess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, a worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
14

---

Answer: [Yes]
Justification: The assumptions are clearly stated in the main text, the theorem statements and some proof sketches also included in the main text. The formal theorem statements and their complete proofs are in the appendix.
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 theo- rems.
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 to provide intuition.
Inversely, any informal proof provided in the core of the paper should be comple- mented by formal proofs provided in appendix or supplemental material. Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main experimental results of the paper to the extent that it affects the main claims and/or conclu- sions of the paper (regardless of whether the code and data are provided or not)?
Answer: [NA]
Justification: This is theoretical paper and does not include experiments. The minor numerical examples added during the rebuttal will be released.
Guidelines:
The answer NA means that the paper does not include experiments. If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is 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 novel architecture, describing the architecture fully might suffice, or if the contribution is specific model and empirical evaluation, it may be necessary either make it possible for others replicate the model with the same dataset, or provide access to 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 a large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all sub- missions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new 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 to access this model for reproducing the results way to re- produce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case au- thors 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 (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
15

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions to faithfully reproduce the main experimental results, described in supplemental material?
Answer: [NA]
Justification: This is theoretical paper and does not include experiments. The minor numerical examples added during the rebuttal will be released.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please tails.
data submission guidelines ceceips.ccppubllee http:///ww////eiidddee/////s//aa
the NeurlPS code and
for more de-
While we encourage the release of code and data, we 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 a new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurIPS code and data submission guidelines (uttps://nips..
for more details. The authors should provide instructions 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 new 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 to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental setting/details
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?
Question:
Answer: [NA]
Justification: This is theoretical paper and does not include experiments. The minor numerical examples added during the rebuttal will be released.
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper 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, or as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropri- ate information about the statistical significance of the experiments?
Question:
Answer: [NA]
Justification: This is theoretical paper and does not include experiments. The minor numerical examples added during the rebuttal will be released.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by emoor bars, confi- dence intervals, or statistical significance tests, least for the experiments that support the main claims of the paper.
16

---

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.
It is OK to report 1-sigma error bars, but one should state it. The authors should prefer- ably 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 figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
If error bars are 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 reproduce the experiments?
Question:
Answer: [NA]
Justification: This a theoretical paper and does not include experiments. The minor nu- merical examples added during the rebuttal will be released. The minor numerical examples added during the rebuttal will be released.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or 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 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 or failed experiments that didn't 't make it into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics /
Answer: [Yes]
Justification: The research conducted in the paper theoretical and conform, in every respect, the NeurlPS Code of Ethics.
Guidelines:
The answer NA means that the authors have not reviewed the NeurlPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- cration 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: [NA]
Justification: This is theoretical work and the algorithm could be applied in different applications. There is nothing specific that can be highlighted.
17

---

Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal impact 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 spe- cific 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 a 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 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 as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitiga- tion strategies (e.g., gated release of models, providing defenses addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data or models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification: This is a theoretical work and the algorithm could be applied in different applications. There is nothing specific that can be highlighted.
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
allow for controlled use of the model, for example by re- quiring that users adhere to usage guidelines restrictions access the model or implementing safcty 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
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?
Question:
Answer: [NA]
Justification:
The paper does not use existing assets.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version of the asset used and, possible, include URL.
The name of the license (c.g., CC-BY 4.0) should be included for each asset.
18

---

For scraped data from a particular source (e.g., website), the copyright and terms of service of that souree should be provided.
assets are released, the license, copyright information, and terms use in the pack- age should be provided. For popular datasets, pwpppawi dataseta has curated licenses for some datasets. Their licensing guide can help determine the li- cense of dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if it has changed) should be provided.
If this information is 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 documenta- tion provided alongside the assets?
Answer: [NA]
Justification:
The paper does not release new assets.the paper does not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl 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 is 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. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the pa- per include the full text of instructions given to participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contri- bution 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. cura- tion, or other labor should paid at least the minimum wage the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification:
The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
19

---

Depending on the country in which research is conducted, IRB approval (or equiva- lent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do 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, or formatting purposes and does not impact the core methodology, scientific rigorousness, originality of the research, declaration is not required.
Question:
Answer: [NA]
Justification: The core method development in this research does not involve LLMS as any important, original, non-standard components.
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 policy (https://neurii) /ttp:p/////arrrreooooo/o/ooeerer / for what should or should not be described.
20

---

A Semi-Norm Contraction Property of the Bellman Operator
A.1 Proof of Lemma 4.1
For any Vi, V/ R and define A Vi V2. Denote p as the transition matrix under policy and the unique stationary distribution d=, and denote as the matrix with rows being identical to d² We further define Q" PD E. Thus, would have,
(V)))) - -T (v) ((() v2(5)) = =P*
(26)
SEES
which implies
(V1) -V) = - =
(27)
We now discuss the detailed construction of the semi-norm || |pp. Since P is ergodic, according to the Perron-Frobenius theorem, pr has an eigenvalue À of algebraic multiplicity exactly one, with corresponding right eigenvector Moreover, all other eigenvalues X2 2 2 Äs of pr satisfies [V < for all i SS..
Lemma A.1. All eigenvalues Q lies strictly inside the unil circle.
Proof. Since = ed E is a rank-one projector onto the span of e. Hence the spectrum of E is (1.0....,0) 0). In addition, show pa and E commute by
Pa = (o((d EP" e((d") = ) =
(o(dd))) =
(28)
(29)
Thus, by the Schur's theorem, and E are simultaneously upper triangularizable. In a common triangular basis, the diagonals of P and list their eigenvalues in descending orders, which are {21, ........ } and {1,0..... 0} respectively. Thus, in that same basis, Q = p E is also triangular, with diagonal entries being {}1 1, 12 O...., As 0}. Since \ we have the spectrum of QF is exactly (A2,..., As,0) 0). Since we already have [& < 1 for all i E f S}. we conclude the proof.
Define p(-) to be the spectral radius of a matrix, then Lemma A. implies that p(Q") < 1. Hence by equivalence of norms in I S it is possible to construct a vector norm || llq so that the induced operator norm of Q" is less than 1, specifically
s p(()) S 11 > S L.
(30)
A concrete construction example is to leverage the discrete-Lyapunoe equation 20 of solving M on the space symmetric matrices for any p(Q") < a < as follows:
Q* MQ - a²M = -I
(31)
Define B QF, then p(B) a-' 1. We can express M in the form of Neumann
series as
M 21 + " +a + ((QT)T) (Q))+.
2(++)) ((QT)T)((0 (QT)*
k=0
(BT)*1) B²
(32)
now show that M is bounded. Write = SJS-1, where diag (Jm, (A1).... Jm, (2r)) the Jordan normal form. By the Jordan block power formula 20).
Jm (A) AI Nm
(33)
21

---

with Ny the nilpotent matrix having ones on the first superdiagonal and N = 0. Then B SJ and j = diag( (Jm, (A For each block and each integer & 2 m, by the binomial theorem we have Nm and
m-1
1: A kー
Jm = (Aim + Nm
=
N
(34)
5=0
For m, (0)
and factor 1a|#:
S
|I|
|1 S km 121K
(35)
where Cm,A سド= | of B. Since J is block diagonal,
- | 12. Thus, let max; m, be the size of the largest Jordan block
| 12
| (A.) (A.)
E Cminie h max (A.1) CCkk~1p(BB**
(36)
for all & 2 8, where Cf Ex= Cm; and p(B) max; [dl.-
Since similarity does not change eigenvalues but may scale norms by the condition number, we can derive that
|| 1B*122 = (| 112 S ||2 S <(S) C,k) (k 2 s),
where x(8) = ||||||||~11| By choosing the appropriate constant, the same bound holds for all k
3 CB > 0 such that ||8||2 I OB p(B)* (A: 2 0).
In spectral norm, this implies
[I (B 12 = [1(BB) T B² m 3B=)== 11 < 2) p(B)2*.
max
(37)
Thus, the scalar series Σ 12 1) pl B) in the form of polynomial times geometric with ratio less than 1, which converges, and the partial sum expression in 32 converges absolutely as geometric-type series.
Also, since each term in B2 is positive semi-definite, and the first term a 2 being positive definite, we can conclude that M being the summation well-defined and is positive definite. Thus, using the positive definite M defined in (31. we can define our desired norm || l|Q as
| = T TMx
(38)
which implies
||@T=lle
v(Q=x) [(Q=x)TMQR MM (a)
||Q l|q = sup
sup #=0
S a <<
(39)
|
VaTMa Mr
Where (a) is because for any 0, from 31
have
(Qx)= MQ a²x Mx -T
(Qx)=T (0=)"TQQ==== a² Mx ||=11
(40)
Since ||< |/ is always non-negative dividing both sides of the second equation further taking the square root both sides yields the inequality of (a).
44 by x. Mx and
Based on the above construction the norm
lle. define the operator || as
| = l|@T - =11o + e inf
x celle
(41)
oER
where 0 < < 1
22

---

Lemma A.2. The operator || llp is valid semi-norm with kernel being exactly {ce R). Furthermore, for all x E R we have ||p*=e|p S (a + e)|
Proof. Regarding positive bomogeneity and nonnegativity. for any scalar À and RR
||x=|p = || (Az)lla + cinf Ar -ello = 1 x = + c
cella | |
and clearly ||>||p 2 0, with equality only when both ||@T 0 and inf, || cellq 0. Regarding triangle inequality, for any 2, R=
| + vllp 110 (z + مااا e in[ x+ + カリ y cell
110 vll + + ae + y bellQ
110 0| ul + cinf ac llll + cinffly bella
| ||y||p.
Regarding the kernel, if = ke for some k E I, then we have
| = ||Q + e inf like celle
|| - E)elle + <llke kelle
=
|lke kello <ll0lla 0
(42)
On the other hand, if & foe: RJ. we know that
| einf ||
cellq 0
(43)
Thus, the kernel of ||- |p exactly fce: :oe:ce c R}. We now show that, for any x E R
p x |p = =|(@"(P*>)
e inf einff] -celq
c
110=0"=+ ExIla
c + 1 -celc cella
S =
(a)elll
S <lllp.
(44)
Let 3 a + by 330 and 41..
we have E (0,1) and (0, a). Thus, 3 E (0,1) and
combining 3 with the semi-norm ||e confirms Lemma
A.2 Proof of Theorem
We override the terms a, À and from the previous section. For any V,, V2 and E S,
T
Σ T(als)lopp (Vi) org (V2)
aEA
Σ
[aass)
min Σ p(8)Vi(8'' - min Σ ((s')V((8')
pePo
pEP
aEd
e'ES
EEES
Σ ((ass) max
Σ (((s)Vi'8')) - Σ p(>')Vs(s')
pEps
FESS
SES
< Σ
(als))
(Vi('') -V2(s']
(45)
where p(n, (-ss,))()ssa))
arg maxpep: Eres p(s')Vi(s') E('Es((')VVll and each
P(v.))) P for all Vi, V2. We now discuss the construction of the desired semi-norm I|p.
23

---

A.2.1 Joint Spectral Radius of Qp
For any P E P, denote Pr as the transition matrix under policy and the unique stationary dis- tribution dp. and denote Ep as the matrix with all rows being identical to dp (we will provide the conditions for all p having a unique stationary distribution later). We further define the following:
OF = Ep and QF (QF P P)-
(46)
To obtain the desired one-step contraction result under Assumption B.T along with proper radius restrictions, we need to show the conditions of the radius under the different uncertainty sets such that the joint spectral radius p(O)) defined in Lemma I.I satisfies p(Q%) < 1, which is necessary
establish the desired one-step contraction. We first provide an upper bound of the joint spectral radius as follows:
Lemma A.3. Define the Dobrushin's 's coefficient of an n dimensional Markov matrix P as
TPP min min (Pss Pjs),
(47)
then the joint spectral radius of the family Qp is upper bounded by the following:
p(()) S inf m21 P.EP
sup (PT
P
(48)
Proof. We start by first connecting p(Q7) to the joint spectral radius of the family {PT P E P}. Define IHI == fx R$ e 2 0} to be the zero-sum subspace where the space spanned by is removed. Furthermore, choose an orthonormal basis U = [uo Un] E SxS with
1
UH = Is-1. U = II = Is
S c0
e
Ua=0
VS"
where 11 is the orthogonal projector onto HI. Since U is orthogonal, U = U-1 notations, for any QF E Qp. we can construct a similar matrix Qp as
With the above
h -- 0 ap
where Bp = UST P E (881)))())-) Bp
(49)
Equivalently, define Tp- IIP which operates entirely H. Then Bp is the matrix of Tp in the basis of Un. Since Ep el (dz)² and U O, we have U1 EpU = Hence, the lower-right block in Ug UF is just Bp. Consequently, for any sequence PT....,Py P
U-L ... UU = Po Bp. ... Be.
(50)
Hence, by block upper- taper-triangullrrty 20), the spectral radius of QF, ... Q5, on R equals the spec- tral radius of Bp, Bp, on IH:
p(OF. -F.F..F.) = p(Br. ... BP.))
PUU ...
P(U ..I..PP)
p(TP. ... TP.).
(51)
Thus, the spectral radius of the family QF, QF, on s equals the spectral radius of PT ...P..... on Hi:
p(FF. ... 2F, = p(Tp) Tp,) = pIIIP] ... PT Given 52 we now study the joint spectral radius of Pa {IIP= :P E P) on H.
(52)
From Lemma F. have that for arbitrary norm
||E- H,
(PE))
lim sup |TPE ... .
lim sup [Tp. ... Tp, T k-000 P,
(53)
k P,EP
24

---

Divide & into m partitions of blocks with length q and residue k = qm++r where 9, m.r E N. 0 q S k and 0 I r q. Furthermore, let Mm == supp, EP l[Tp ... Tp, Il- and <m = maxogrem suPp,eP 17p, Tp, llu-a. then by the submultiplicity of operator norm, we have that on HHI
sup [TPp Tp, 1la-x S My Kem- P.EP
(54)
taking power of & and let k + oo implies
lim sup
[Tp, Tp, llii-a I lim MA K
(55)
k P.EP
k000
1 Since q 1 we have limg-poc & m integer m we have,
and lima-roo 0, which suggests that for any positive
#
lim sup [Tp, ... Tp, Il S M
sup P.EP
[[TP,. ... Tp, IIB--a) ..ll.lllla)
(56)
1-000 P.EP
which implies for any norm
|| ||n- on HI, we have
lim sup [Tp, Tp....TTlllle ll inf m21
sup
1| ... Tp. ||
(57)
P.EP
From (16). the Dobrushin's 's coefficient is a valid norm (the induced matrix span norm) on the zero- sum subspace H., which yields (48).
Lemma A.3 provides quantitative method to relate the joint spectral radius of the family Q and the Dobrushin's 's coefficient of the family P. Under Assumption 3.1 we next discuss the radius restrictions of contamination, TV and Wasserstein distance uncertainty sets such that P(Q5) satisfied.
A.2.2 Discussions on Radius Restrictions
We provide the following Lemma A A.6 which quantifies the radius restrictions regarding all three uncertainty sets of interests for obtaining the desired results.
Contamination Uncertainty Regarding contamination uncertainty, where the uncertainty set characterized as
p= { ((s.
(1-8))(-|ss.) a) (s. A(8)). 05 <
For fixed policy n, the induced state-transition matrix pT expressed as
D sss
Σ ((als) s, (1 Σ T(als) Σ {alls))(s\(s.c) (58)
Define the induced uncertainty set p = {Pr E P] and define (s Σ. ((lss) a). Then (58) can be expressed as
pd (1-5))P + 8q q" row-stochastic }-
(59)
Lemma A.4. Under the contamination uncertainty set, if the centroid p is irreducible and aperi- odic, then the joint spectral radius of Q7 defined in (46) is strictly less than 1. Furthermore, pa irreducible and aperiodic for all P E P.
Proof. Since pr is irreducible and aperiodic. Then there exists an m E N such that all entries in (p")m are strictly positive. For any P E Pa we can write p = (1 - 5)P= + oq with q" being row-stochastic, by multinomial expansion,
(P*) ((1 8)PP" + 6g") > -1- (P (entrywise).
(60)
25

---

Hence (P*)" "h is strictly positive for all P E P. which implies every pa E p is primitive with the same exponent m, which further implies pa is irreducible and aperiodic for all P.
To bound the joint spectral radius, for the same integer m, define the m-step overlap constant of the centroid as
= min Σ min (P Dis, (P*)ja} E (0, 1].
SES
For any length-m product P "..PP with P P", the same entrywise bound (60) gives
PT PT (1 8)m (P=)n, whence for all i + J. we have
Σ min ((P ... ....P)ss: (P ... PT)a+] 2 ......T)jall
(1-8) 8)''aa
(61)
By the definition of the Dobrushin's 's coefficient in 47 the above yields
7(P ... PT) I 1- - (1 - 8) 0o < 1.
(62)
By Lemma A.3
sup r(P ..... p?)) $ (1-(1-5))m) -5)"ao) 1/m < 1.
(QF) & inf
121 P.EP
Therefore, if the center pD is primitive and 0 S 5 < 1, without having any additional restrictions on the radius, we have that all induced kernels Pa are irreducible and aperiodic. Furthermore, the joint spectral radius of QP satisfies ((Q7) < 1.
Total Variation (TV) Distance Uncertainty Regarding TV uncertainty, where the uncertainty set characterized
p = ( V(s,a), a), (() s 8).
82 0,
where TV expressed as
11p 9ll1. For fixed policy æ, the induced state tran--tranition matrix p is
(M = Σ [(s(s))(s||s,
(63)
Then for each state s.
(T. TV
Σ ((als) a), Σ ((((s))(((1s.))
(64)
by convexity of TV(..) in each argument. Hence
ps c M row-stochastic: Vs, (V, 5o].
(65)
Lemma A.S. Under the TV distance uncertainty set, if centroid Pa irreducible and aperiodic, then there exists E N. such that (PTym is strictly positive. Define bo ((P=, ).. > then if the radius satisfies 8 < m. the joint spectral radius of Q7 defined in (46) is strictly less than 1. Furthermore, pa is irreducible and aperiodic for all P P.
Proof. Define the m-step constant 0g as
an min Σ min (in)((")) ((Pa)m)))) E (0,
26

---

then 2 S by where S |S].
Regarding the joint spectral radius, for any length-m product P ... PT with P. Pa. By telescoping expansion and nonexpansiveness of TVV under right-muttiliiatioon by a Markov kernel,
TV((P ... (P S má for all rows i.
Then, for all i *
Σ min ... Pf)ia (Pm ... ....PP))e) TV(PP ... PT)(),), -.T)())))
a0 2md,
(66)
by the triangle inequality in TV. Hence
T(Pp ....... PT)) min
Σ
min ((P ......PP. ...PPT)ss (P ...PP) S 1 (av 2md). (67)
By setting 8 < we have EP ((.P..))T))) < 1, and by Lemma A.3
((F)
(uup
((P m ..P)))).)))
1/m
S (1 - (ao -2md)) 1/m 1.
(68)
P.EP
Similarly, the same perturbation bound yields
min(P") !m
min((P")))* md > bo md,
so by setting 8 < bo mn we have that (P*)" is strictly positive for every P E P; hence all induced kernels are irreducible and aperiodic. Since do 2 Sho, we have 2m 2 be for S 2 2. Therefore the
condition that 8 satisfies both requirements.
Wasserstein Distance Uncertainty Regarding Wasserstein uncertainty with 2 1, let (S, d) be the finite metric space. The uncertainty can be characterized
P p= {p : V(s, ()((s.s)))
s {o).
For a fixed policy n, the induced state transition matrix pa expressed as
(M 8') = Σ [(sls)P(s'\s,,)
(69)
For each state by joint convexity of Wp(, :d)
PP WT Σ ((lls)P((ss,) a), Σ ((lss)
Σ ((ass)
8",
hence W, (PT (s) < 8 for all i.e.
p C ( row-stochastic Vs, W, (M (s. < 6).
(70)
We now draw connection between 770) and the TV version in (65). Since the state space is finite, denote & = min d(Ir,)) >> 0. Then, for any distributions u, v, we have
Wi uz d) 2 8min TV(u,
and
Wp uz d) 2 (u,
which implies that
Wi (u,, v;d) Wo(u,edd)
TV(u, v) <
(71)
8uin
8min
Therefore reduce 770 into TV distance uncertainty set characterized follows:
5
nd C M row swwchasccattic Vs, (s.
PT( <
(72)
8mm
27

---

Lemma A.6. Under the Wasserstein distance uncertainty set, if the centroid P is irreducible and aperiodic, then there exists m & N such that (pa) is strictly positive. Define bo mins, ((P"))")) > O and òmin == minggy d(z y) > O, then if the radius satisfies å < Sminba the joint spectral radius of Qp defined in (46 strictly less than Furthermore, P is irreducible and aperiodic for all P E E.P
Proof. This a direct corollary Lemma A.5 under the condition of 72
Remarks. (i) If is normalized so min 1, the thresholds simplify accordingly. (ii) One can also argue via WP 2 8 TV,, which gives the alternative (more conservative when e is small) choice 82 38/8min the linear reduction r = 6/6min above is sharper and suffices for the bounds.
A.2.3 Extremal Norm Construction
Under the radius conditions of Lemma A.4 A.6
we have that
p((2) <
(73)
We follow similar process for constructing our desired semi-norm || -llp as in Appendix A.] by first constructing norm such that all Q$ are strictly less then one under that norm. We choose (r", 1) and we follow the approach in (42) by constructing an extremal norm
-lext as follows:
|,]||ext == sup sup R20 .......EEE.
Q10122 where
O {Q PEP)
(74)
Note that we follow the convention that [[ Q22112 = ||0||2 when
Lemma A.7. Under Assumption 3.7 and the radius conditions of Lemma A.4 the operator llxtt valid norm with |Qp ext for all P P
Proof. We first prove that ||- llexa is bounded. Following Lemma F. and choosing (r", a.), then there exist a positive constant < oo such that
1QuQx-1...0 ..lll S CA*
(75)
Hence for each and for all x R
-h | - as k - 0c
a ~ Q10112 S *1100-011111111122222.
Cx 1a*1 = =
(76)
Thus the double supremum To check that || Ilext is valid norm, note that if x = 0, ||æ]|exe is directly 0. On the other hand,
74 is over a bounded and vanishing sequence, so || llext bounded.
||æ]|eext have
sup 0= Q Q Qi EQU
11 = ||ж|| = == 0
(77)
Regarding homogeneity, observe that for any e E IR and x E R
|ca eext sup
sup k Q Q.EE
a
|c]|=||exxt
(78)
Regarding triangle inequality, using IQQ... c + 1) < |Q Q10112 + 11Qx Qivlla for any x, y E 12 obtain,
|| + vilext sup k20 R...QQ............... QLEQU
sup
a a=11Q= Q +v)12 S ||/||oox + IIyllext
(79)
28

---

For any P E P. we have
sup sup
a 0010000-1---99100
120 Qr.... EEE
sup S sup
k21 Quu.,
-asup
sup Q.ERp
11000A-1-..11111 11
R21 Q
S ossup
sup
k20 Q 4.E
= a x x
(80)
Since is arbitrary, 80
implies that for any P E P.
1 lext
| elettext
sup x#0
I a <
(81)
||||
A.2.4 Semi-Norm Contraction for Robust Bellman Operator
We now follow the same method as construct the semi-norm ||-|p, Define the operator ||-11p as
| [ == sup
@ + inf ce
(82)
PEP
cER
where 0 < 1-1
Lemma A.8. The operator ||. lle is a valid semi-norm with kernel being exactly fce : E R] under Assumption 3.7 and the radius conditions of LemmalAA.4AA. Furthermore, for all E R$, we have | x $ (a + =) all P e P.
Proof. Regarding positive homogeneity and nonnegativity, for any scalar À and E TR:S
||A Ip = sup @ +c inf A ext PEP
| sup Q$x ext
+c|A|
inf eER
| cc = |
eER
PEP
and || 2 0. Regarding triangle inequality, for any x, V R$ note that for any P E P.
1 lext I ||Q + ||QFyllext
(83)
Taking supremum over P on both sides yields
sup PEP
|1 + lex S sup ||Q + sup |/Pyllext
(84)
PEP
PEP
Thus, we have
||
vllp
sup PEP
( v) + cinffla + oolloxt
I sup ||@ + sup ||@Fvleext + +einf a.b
x ae + y - be bell ext
PEP
PEP
< sup | + sup PEP
|1@ + e
aell lext + e iinf - be |let
PEP
|||| + ||y|pp
Regarding the kernel, if ke for some ie E I, then similar (42 we have
|
sup
(F(e)) + inf like cellext 0 0= PEP
(85)
On the other hand, if x & foc c E R}, we know that
||/|| 2 inf | cellext
(86)
29

---

Thus, the kernel of || // is exactly (ce:cE R).
We now show that, for any E R$ and P E P.
| 2
=
sup QE 47
QPP laxe + c P" x cellext
sup |1Q + Qpx ext + inf + Epx - cellext
QE Q7
sup
|[Qpxxllxx + in einf cellext
QE Q3
S a sup |Qx]|eex + <II@*==/ee
Qe 47
(a + c) xleext
- (a + e)||=||p.
(87)
Since E (0, 1) and E (0, a). Thus, let + then y E (0, Substituting the above
result back to (45) we obtain
-y ( - S >
Velle
(88)
B Biased Stochastic Approximation Convergence Rate
In Section 4 we established that the robust Bellman operator is contraction under the semi-norm Iel ensuring that policy evaluation can be analyzed within a well-posed stochastic approximation framework. However, conventional stochastic approximation methods typically assume unbiased noise, where variance diminishes over time without introducing systematic drift. In contrast, the noise in robust policy evaluation under TV and Wasserstein distance uncertainty sets exhibits small but persistent bias, arising from the estimators of the support functions 0p (V) (discussed in Section lead uncontrolled error accumulation, affecting the
5). This bias, if not properly addressed, reliability of policy evaluation. To address this challenge, this section introduces a novel analysis of biased stochastic approximation, leveraging properties dual norms to ensure that the bias remains controlled and does not significantly impact the convergence rate. Our results extend prior work on unbiased settings and provide the first explicit finite-time guarantees, which further used to establish the sample complexity of policy evaluation in robust average-reward RL. Specifically, we analyze the iteration complexity for solving the fixed equivalence class equation H(x") - x² E E where == foe E R] with e being the all-ones vector. The stochastic approximation iteration being used is follows:
1 1+1
+ [+(("') =e', where =(x')= H('') + wt.
(89)
with 1): being the step-size sequence. We assume that there exist y (0, 1) such that
Il - (v) S 7 yllp, Vx,y
(90)
We also assume that the noise terms w i.i.d. and have bounded bias and variance
E || S + B || x 1 and [[(""((")) || S Ehins
(91)
Theorem B.1. If is generated by 89 with all assumptions in (90) and 91 satisfied, then if the stepsize (). = (
E 110
x² 13
O
1000
x² +
( )
(
+
A + O
Saup Shiae log T
(92)
T
1-
where Tsup sup, || do is the upper bound of the || ||p semi-norm for all xt.
Theorem B.1 adapts the analysis of (55 and extends it to biased i.i.d. noise setting. To manage the bias terms, we leverage properties of dual norms to bound the inner product between the error term and the gradient, ensuring that the bias influence remains logarithmic in T rather than growing
30

---

unbounded, while also carefully structuring the stepsize decay to mitigate long-term accumulation. This results in an extra Ebis term with logarithmic dependence of the total iteration T..
We perform analysis of the biased-noise extension to the semi-norm stochastic approximation (SA) problem by constructing smooth convex semi-I_yapunov function for forming the negative drift and using properties in dual norms for managing the bias.
45
B.1 Proof of Theorem B.1
B.1.1 Setup and Notation.
In this section, we override the notation of the semi-norm -| ||p by re-writing it as the norm IIv (defined in (96)) to the equivalence class of constant vectors. For any norm lle and equivalence class E, define the indicator function fg as
= 0
x E,
(93)
otherwise.
then by (5). the semi-norm induced by norm ||- and equivalence class E is the infimal convolution of || le and the indicator function og can be defined as follows
| == (ll |le +ine (x) inl alle + dg(v)) = inf || ellc
Vxr
(94)
eEE
where *inf denotes the infimal convolution operator. Throughout the remaining section, we let E == {oe e E R} with being the all-ones vector. Since || || constructed (82) semi-norm with kernel being E, we can construct norm || IIl such that
| = (ll Il #int 8g)(z) = ||=||p
(95)
construct || Il as follows:
|| = sup Q$2 lextt + inf l falir--eellln cellexs + E||x2|eext PEP
(96)
oER.
where OP and defined in
82
Lemma B.2. The operator || ||, defined in (96) is norm satisfying (95).
Proof. We first verify that || |l is a norm. Regarding positivity, since all terms in (96) are non- negative, ||a|a 2 for all RR and ||o||v 0. If * O, since || |lexe is valid norm and e > 0, we have
| 2 e||2/|lext > O.
Regarding homogeneity, For any I, we have
PEP (fx))) tcinf](AAr) - collaxe <||Ax|len ext || sup
= |A|sup supp| extt + +[[A/inff] cell c//l[|//|ee
PEP
|А||||||
Regarding triangle inequality, for any ær, RRS, we have
| + vllv- sup supllQF(1= + y)ll + +inf
(z + 8) collaxt + c||x + yllext
PEP
< sup [Qzz|lext + sup ||QFvllexs + iinf inf]læ= ae + y - bel extt + e([lollexse + l1Brllexs)
PEP
PEP
a.b
< sup || + sup
|1Q + ael lext + inf - bell + eller/lesee + |1 llv/lesee b
PEP
PEP
= ||ار + ||y/
31

---

We now show that since Oāe = 0 for all P E P, by the definition of infimal convolution, we have that for all E R
(ll Ia *inf (z(2) = inf o - kellw
RER
inf
sup
Up.
kQ nxt
+ inf CEE.
oc kkol + c|12:
kell exxt
RER
PEP
inf
sup PEP
@pxx ext + +e
ieinf
ce
ext + c||æ - kellext
RER
oERR
sup
1pz lext
+ +e inf
cel
+ inf (ellæ kellext)
PEP
cER
KER
= |
We thus restate our problem of analyzing the iteration complexity for solving the fixed equivalence class equation H (x*) - E. with the operator R= 1R" satisfying the contraction property as follows:
(x) ((v)ll S >11 - vll 7 (0,
Va,y
(97)
The stochastic approximation iteration being used as follows
x++1 = r² n (f(')) x²], where A'x') H(x") + wt.
(98)
We assume:
[[[[ 1
NE F A + Blix² x² 11 N.E
(In the robust average-reward TD case, 0).
N.
biass
mp 0 chosen stepsize sequence (decreasing constant).
Note that beside the bias in the noise, the above formulation and assumptions are identical to the unbiased setups in Section B of [45]. Thus, emphasize mostly on managing the bias.
B.1.2
Semi-Lyapunov (-) and Smoothness.
By [45, define
Proposition 1-2], using the Moreau envelope function M(x) Definition 2.2 of {8 we
Mg(x) = (M #inf (x),
so that there exist Ct, Cu 0 with
<M)(x) I |1allyy S Sc.((()
(99)
and My is L-smooth w.r.f. another semi-norm ||,,5 Concretely, L-smoothness means:
My(1) s Mz(x) (VMg(z) y x) 1/2 =1 Vx,y.
(100)
Moreover, the gradient of M satisfies (VMz(x), co) = 0 for all x, and the dual norm denoted as I is also L-smooth:
[ VM S - Vz,y.
(101)
Note that since || 11s. and Il are semi-norms finite-dimensional space with the same kernel, there exist (1, P2 0 such that
P1 |=ll,,E < ||=1|,E S Pa II Zz. Likewise, their dual norms (denoted || Il..... and || II satisfy the following:
(102)
| S [| - P
|| Vz.
(103)
32

---

B.1.3 Formal Statement of Theorem B.1
By L-smoothness w.r.t. || -1,.E in (T00) for each t,
M Mg(atti- x²) S M E (x' x²) (VM (x' x²),x(+1
1 x²) + 211x0t1
x² 2²1 S.E"
(104)
where x²+ x² = H - = n (H(")) + w² - x7). Taking expectation of the second term of the RHS of (104) conditioned the filtration Ft we obtain,
M - x² x²),x²t) - = - - x²), H(x') x' + [F)
= - - x²) H(x')(x))) x²) + The M x² x2)),")
= =n(V - x²) xx',, H(x')() x²) nu MZ x²), B(W (105)
To analyze the additional bias term V - x²), B[) we use the fact that for any (semi- Jnorm with dual (semi-)norm general inequality
|l. (defined by ||u/|+ = sup v) ||l|| S 1},, we have the
(u, v) - |/ |w||: Vu,
(106)
In the biased noise setting,
VM (x x²) and v B[w"FFt, with || 1-11= II So
V - x" x²),E(w"(F)) VM - x²") z²)"l Il,,,.. ||| II
(107)
Since ||B[w*] FF'll
| NE S Ebiss it remains to bound VV x0" II By setting
0 in
(OO), get
[V V ... S
1| Vx.
(108)
Thus,
VM I [ + LI1 Vr.
(109)
By 103). we know that there exists
S S ب such that
[VM w. VallVM
(110)
Thus, combining 109 and
110 would give:
|| II. S (IV L||=!l,,E). Vx.
(111)
By
102
we know that ||~||a,E S |I thus we have:
IVM S (IIVM [p Vo.
(112)
Hence, combining the above with (107). there exist some
G = 0
max (V.
(113)
P1
such that
E (VM - - w [F
B(w,, < G(1 + ||= x² x'Ilx.7) Biass
(114)
Combining with 105 we obtain
(xf x=) +11 2²)(["}] & m/. (V -x"), Hx*)) x²)
+ mp Genins (1 ||+0* Il
(115)
33

---

To bound the first term in the RHS of (15),, note that
(VMplæ' - xx", (.HH((')))))) x²) (VMg(a'
- -²)), H(0)) x² + -x²)
Mg(H(z²) -x²) MM(x' -x')
3 I
[1((2') )- - 1((0((0)) (xxx))lEE Ma(a' - xx")
201
22
1| xx xxIlE,E MM(e' - xx)
201
-1) Mela' -1)MMlat
x²)
C1
S - - (1-Y---C MVVCc//)MMML - xx),,
(116)
where (a) follows from the convexity of MR. (b) follows from x' belonging fixed equivalence class with respect to and (c) follows from the contraction property of H. Combining (166). (15)
and Lemma F2 with [04), arrive follows:
M ( - x Fe & (1 20:27h + ass7h)) ( x²) + an?
+ 1/1 Ghias (1 1| x'IINNE))
(117)
Where 02 == (1 CVCC/a/ Ca/ca) ). 0g = (8 + 2B) and 044 = Ap2 We now present the formal
version of Theorem B.1 as follows:
Theorem B.3 (Formal version of Theorem B let 02, 03 and 04 be defined in if xf is
generated by 98 with all assumptions B. satisfied, then the stepsize T) ag(t+K] while
K = max (a3//0,322000
E 1|1x" - x N.E I (T+ KYa
K²cu
1| - x² I +
8010
2c C2 C2E
(118)
(T K)az
where C1 G(1 ((1+22 C2 1 +og (T~K-K) G is defined in 113 and Teup = sup || N. the upper bound of the || ||p semi-norm for all x'.
Proof. This choice 7, satisfies agni I ar77 Thus, by 117 we have
E E[Mg(z - x |FF s (1 M x²) + amn + 11
(119)
we define D == (1 - (227)) and further obtain the T-sepp recursion relationship as follows:
T-1 1
M Mx - =0)] s M x²) + +r
Maah + [1
T1+1
1=
T-1 = - -2) + TTT
T-1
[a4n
+
T++1
D++1
1=0
1=0
-TrM5(00 x²)+ + T
Haam
+
Mn
(120)
02
P++1
T+41
==
where the term R₁ is identical to the unbiased case in Theorem 3 of (45 which leads to
K²
4a2
R
(T + KY² M Mz x²) + (T + K K)a
(121)
also, R2 can be bounded by logarithmic dependence of T''
T-1
T-1
C2C2ebis
R2 5 m ( = C1 Ebias
Σ
5
(122)
az(1 + K)
02
1=
34

---

Combining 121 and T22) with (20) would obtain the following:
K²
402
C2C2shias
I
M T
x²)
(T + K)) Ma(a" x²)
+
+
(123)
(T
+ K)a
a2
Combining 123
with 999
yields
(18).
C Uncertainty Set Support Function Estimators
C.1 Proof of Theorem 5.1
We have
Nmax Σ
E
E[M]
=
2n P(N' = n) + 22 = >Nmax)
==0
N max
2 P(N =n) + Namax +1 PPN 2 Nuaxx)
==0
Nmux""
2n+1
NNax Ip(N 2 Mmax)
2n+1
Nmax + 2muxx +1 PPN 2 Nmax)
Nmaxt1
Nmax + 2 man
Nixx + 2 = ((Nmax)
(124)
C.2 Proof of Theorem
denote o (V) the untruncated MLMC estimator obtained by running Algorithm when setting Nmax to infinity. From (39], under both TV uncertainty sets and Wasserstein uncertainty sets, have p. (V) as an unbiased estimator of dpp (V). Thus,
E ppp (V) Jay
Opy (V)] = E [o (V)]
- E Oip (V)
AN (V)
Av(V)
=
E
Op.i 41
(V)+
E
Ope. +iN+1
(V) +
P(N' n))
P(N=1)
AN
AN(V)
E
- E
P(N' n)
P(N n)
Nmax
Σ (V)
Σ Av)
(v)
(125)
12 Ninxx
For each (V)),, the expectation of absolute value can be bounded as
[[A.( E lop p (V) Opp: -p::(()) (
[
Ope.E -, (V) op: (V) + E Toop.o. (V) - op: op: (v>]]
(126)
By the binomial concentration and the Lipschitz property of the support function as in Lemma 5.3
we know for TV distance uncertainty, have
1
E [V)IlV)]] < 6(1 -
(127)
and for Wasserstein disance uncertainty, we have
E E (|A.(V) < 6.2 3 ||
(128)
35

---

Thus, for TV distance uncertainty, we have
[ - dpy -ry (V)]I < Σ
B[AA( < 6(1 = g)
Neax
Vllss
(129)
max
and for Wasserstein distance uncertainty, we have
E (V) (v: (v)]]
E
(VIl 2-2
Muua
(130)
Nanax
C.3 Proof of Lemma
For TV uncertainty sets, for fixed V, for any A(S), define fp(N) p(V 11) 8|l V Mllap and M = arg max fp()). Thus, we have
Pry (V) 2or (V) = Sp(1gg) - (1
(131)
since, M and by are maximizers of fp and fg respectively, we further have
Sp(()) (4(1 - (o(1)) Sq(1G) $ (b((5) 19(14))
(132)
Combing 131 and 132 thus have:
Pprrv (V) - der (V)I S max (1x(())))))) f9(45)). 15((1)) (1()))
max (V - 11)1,, -V pD)1
(133)
Note that dprv (V) also be expressed as Prr (V) px 811x* 1lap where x" arg maxxsv (px /lpp) Let M == max, x (s) and m == min, x*(). then ||x||ep M m.. Denote the all-ones vector, then min, V(8) is feasible solution. Thus,
px 8(M - m) 2 p(min ((s) e) - 811 min V(s) ellsp min ((s)
(134)
Since p is probability vector, px* M, using the fact that > 0, then obtain
M - M - m) min V(s) = M m S min, (s)) Since x" is feasible solution, we have
(135)
M max (s)) M min V(s) S max V(s) min V(s) VVllp
(136)
Combining
135 and 136) we obtain
VIlse
M V lpp
IVIlap
M m
min V(s)
(137)
5
Where the last inequality is from M 2 min, V(s). which is direct result of 135 and the term 5(M - m) being positive. We finally arrive with
| 8
x x²) E [m, M] c min V(s)
max V(s)
Vjes
(138)
Thus, ||x* Ilap I (1 + V which Ieads to
||V - -V=iblla ppll < (1 MI - -rllep S <11
31+
(139)
Combining (139) with 133 we obtain the first part of 23
For Wasserstein uncertainty sets, note that for any p E A(S) and value function V,
((Ap))
Pp (V) = sup AzU
X8 + Ep inf (V Ad(S.v)))
(140)
yES
((a,))
36

---

Note that
inf V(v) - 0(s A) - V8)) + Ad(S, = V(s)
(141)
yES
where the first inequality is because Ad(SS,) v) 2 0 for any d and I. We can then bound ø by the span of V as
[o(s, A) - ||V v
(142)
We then further have that for any p.g E (SS) and X > 0.
lg(A,p) g(>,9)) - Σ
[p(s) (())] A) s ll |lliIVVlls
(143)
sES
using 143 and the fact that If(A) - g(Ail $ E =
sup, f(A) supa g(A)] S e, we obtain the
second part of (23).
C.4 Proof of Theorem 5.4
For all p E A(S), we have oy(V) $ [Vllsp leading to
Var(ōpy (V)) = EE (V)) + IIV
(144)
To bound the second moment, note that
A AN. (V) P(N' =n)
E (op= (V)) E
Opn.1 - (V)
[IVIlap +
(v)
IE
P(N' =n)
AN-(V) P(N n)
S V| + 2F
Nmxx
[V]An( 2
$ 2 + 2
P(N' = n)
P(N' =n)
Nimax
(V))I
2
(145)
P(N
0=
Under TV distance uncertainty set, by
127 we further have
N Nuax
36(1 +
E (op: (v))
< 2 12p +2
2 (n+1)
==
2 12p + 144(1 + 2 S N
(146)
Under Wasserstein distance uncertainty set, by
128 we further have
Nmax 362 V
IE [v)) < V
25
2 (-(++1
2| V Nmax
(147)
D Convergence for Robust TD
D.1 Formal Statement of Theorem 6.1
The first half of Algorithm 1 line 7) can be treated as a special instance of the SA updates in 988 with the bias and variance of the i.i.d. noise term specified in Section 5 To facilitate deriving
37

---

the bounds of the noise terms, we first analyze the bounds in terms of the 1s norm, and then translate the bounds in terms of the || ||r semi-norm obtain the final results.
We start with analyzing the bias and variance of T go (V,) for each t. Recall the definition of T (V)) is as follows:
T (V) = Σ (rals) - 3u + Opy (Vi) Vs E
Thus, we have for all E.
E
T 90 (V))(s)
- To (Vo)(s)
$ Σ [(a|s) Blopy (V)) Opy (Vo) BBōp; (Vo] opy (Vi)
(148)
Which further implies the bias of T (Vi) is bounded by the bias of pp (Vi) follows:
E T 90 (v))
T go (Vi)
- B (Vi) d.p (Vi)
(149)
Regarding the variance, note that
E
(T g0 (V)(s)
To (Vi)()))²)
E T (Vo)(s) -T Too (V2)(s))
+ Var (T (V:)
s Blörp (Vi) op; op: (Vi))² + Var Σ T(aas) (V))
= B (Vi) - opp (vo) Σ T(als) Var (ōpz (Vi))
(150)
To create an upper bound of VVllap for all possible V, define the mixing time of any p E P be
1
L arg min max
('OP*)) - 1Ã0
(151)
2
where Px is the finite state Markov chain induced by π, Ho is any initial probability distribution on C.mmaFF4aam F.4land for any value function
S and is its invariant distribution. By Assumption 3.1 and Lemma V, we have
mix +oc and |V S 41 < 44
(152)
where we define miix == suppep 1 then mix is also finite due to the compactness P. We now derive the bounds biases and variances for the three types of uncertainty sets. Regarding contam- ination uncertainty sets, according to Lemma F.3 op (V) is unbiased and has variance bounded by
||V] Thu, define fmix according to Lemma F.4 and combining the above result with Lemma F4 obtain that T 90 (V)) is also unbiased and the variance satisfies
E T (V) - To (V)) (va) < [|V.11 < 166²
(153)
Regarding TV distance uncertainty sets, using the property of the bias and variance of opg (V) in Theorem 5. 2 and Theorem 5.4 while combining them with Lemma F4 we have
T (V2)
Too (Vo)
1 s 6(1 + 1 J)552 Nyus IVIlpp 24(1 { 1
Myya tmix (154)
and
E
r (V:) T (Vi)
24(1 + ) ".v52
Nugas tmix
+ +3| + 144(1 + ) N
2
24(1+ + " V/522
Neax
tmix
48 mix
+ 2230
3) 2 S Niax
(155)
38

---

Similarly, for Wasserstein distance uncertainty sets, we have
E T (Vi) - go (vi)
56V52 Maya [
24v
mix
(156)
and
E
T 90
(V))
- Too (V))
I 224
S2
N Maps
Emixx
3 sp
+ 144
N Mmax
I 24v
S2
Mayax
miix
48t mix + 2304St
mix -
(157)
In order to translate the above bounds from the Loc norm into the || el norm, recall that in line 7 of Algorithm 2 we chose an anchor state 8o set Vi(so) for all to avoid ambiguity. We thus can draw the following relationship:
Lemma D.1. Let x E I& satisfy 2; = for some fixed index Then
| S ||=|| = max Ij min
Iy S looe
15J5m 15j5n
Moreover, since all semi-norms with the same kernel spaces are equivalent, there are constants cp, Op > 0 so that
epl1æ|lap I |0|| S Cpllxllsp V
then
cp||æ||> S op||=||>p | S Cpl|rllsp 20p||z]1
(158)
Proof. Since F, = 0, for every we have ~| S æ3 S | Hence
max 2i S || min 2, 2 ||
and so
|| max (max r, 0, 0- 10mmnnz) x, S |4ll max max miii x, I |=]ls0 2 |=2|
Since ||- lepp and || p both have the same kernel of (ce R), by the equivalence of semi-norms, follows that there exists ep and Cp such that
cp||=||>o S cpll=|lep S ||>|| S Cpl|=/lep S 20p||z/la
as claimed.
With the relationship established above, line line 7 of Algorithm can be formally treated special instance of the SA updates in (98) with B = O. We now provide the bias and variance of the i..dd noise for the different uncertainty sets discussed using Lemma D.I and the estimation bounds in For contamination uncertainty sets, we have
Crntt O and A Cont 3
(159)
bias
for TV distance uncertainty sets, we have
TV bias
48Cpp1 + /
Nmax mix
O 0(V52
Nmax
(160) t mmix 2
and
1 TV 202 24(1 VS2
Nmax 2
6mix
+ 16C
4608C +
1 2 mixx St
Nmax
O SN max)
(161)
and for Wasserstein distance uncertainty sets, we have
Wass bias
48CpVS2
Muax tmix =0 -0V32
N Nmax
miix
(162)
and
A Wass
202 (24V52
Myya truix) + 16C22
4466802.5tt St2
St Nuax
O S.
(163)
39

---

Theorem D.2 (Formal version of Theorem 6.1). Let == =1
(1-10 - (1--//c/cc) 03 == 8caP2L and 04 == P2L, if Ve is generated by Algorithm 2 Define V* to be the anchored robust value function V = V
Vp + ce for some e such that V (so) 0, then under Assumption 3. and the radius
conditions of Lemma A.6 if the stepsize Tkc ux( while K max(0x//ar 33, then for contamination uncertainty sets,
C2 IVo - 1 + 8A 04Ca 0 ( (T + KY acpp
1
E |V - V 18 S
+ T(1 - 7)
mix
(T+ KK
(164)
for TV distance uncertainty sets,
c,
8ATV aucu
C. TV
E - - (T (T+ K)
11 1 + (T K)a3ep
(165)
(12
12 mix Nuax
12 2 _uau log T
=
+
(166)
T
T(1 - 7)2
(1-
for Wusserstein distance uncertainty sets,
E 2[1Vr- - 111 x
11 - VVo- + (T + K c
8A Wase
a4ca
Cu CaCre
Wass bins
(167)
(T KyGc
a22
1
22
N max
mix 2
Nmax
log T
mix
(168)
T2
T(1
7)
71-
where the E and A terms are defined in 159
163),
C2 t tlog (2 (2-1+K = G
ry is defined in (I4), Cu. Ct are defined in
(9). P2 is defined in (102), G is defined in 113). and Cp, Cp
are defined in Lemma D.
Proof. By Lemma D.I and 152 as follows:
we have that for any value function V its || 1|p norm is bounded
| S 4Cptmix
(169)
Substituting the terms of 159] contamination uncertainty sets,
163
169 and Theorem
4.2 Theorem
B.
we would have for
E |r- V [|:] <
K2cu
(+KK)a Voo v +
8A Cont agc
= O
(
1
mix
(170)
72
T(1 - 7)3
for TV distance uncertainty sets,
K2c, Cu
8A 44c
Cn C2
TV
E | - 11
< (T kPa
11 - 1V-1 +
hins
(171)
(T K)0z
0.2
S1 StenixNNim Nmax
S12 Stmiix 2 -ugua
log
+
(172)
T
T(1 -)
(1 - (1
for Wasserstein distance uncertainty sets,
K2cu co
Vivo 1- + 4A Wass Cucu
Cu C2C
Wass
E3
|| v1
<
bias
(173)
(T'+ KY²c
(T K K)az
022
o
1
+
St2
mix
N
St2 mix
2
Nmax
log T
(174)
T
T(1
7)2
(1 7)2
where the e and A terms are defined 159)-
163
C2 = 1 +log [ [T-14 (I G(18Cpmmmmm)))
y is defined in (14, Cu. are defined in 999) P2 is defined in (12). & is defined in 113. and Cp
defined Lemma D.I We now translate the result back to the standard Lo norm by applying Lemma [. lggain to the above, we obtain the desired results.
40

---

D.2 Proof of Theorem 6.1
We use the result from Theorem D.2 to set E
- S
= For contamination uncertainty set
we set T - O
(-(1-))
finix
resulting in O
(11-1)
SAL
sample complexity. For TV and Wasserstein
uncertainty set, set Niaxx O (log
Sfmmix c(1-2)
and == O
L log -(1-))) combining
with Theorem 5.1 this would result in O
2211-)² log² V5ttzz <(1-7)
SAt
sample complexity.
To show order-ottimality, we provide the standard mean estimation as hard example. Consider the TD learning of the MDP with only two states S {s1, ( and Pr(s + s1) p, Pr(s - $2)
1 p for each s E S with E (0, Thus, this MDP indifferent from the actions chosen and we further define r(81)
1, r(s2) = Thus, estimating the relative value functions is equivalent of estimating p. By the Cramér-Rao or direct variance argument for Bernoullipp) estimation, we have
that to achieve jp'v p|? v e² requires N 2 1/2c² =2(c 2).
D.3 Formal Statement of Theorem 6.2
To analyze the second part (line 8 line 14) of Algorithm(Zland provide the provide the complexity for gt. we first define the noiseless function 8(V) as
8(V) = S Σ
Σ r ((als) (alls)(((s,a) + (opy())) - V(s)
(175)
Thus, we have
82 o(V)) + 1t
(176)
where is the noise term with bias equal to the bias Opy (Vr)
1 ΣΣ (=(a)s)B[lop: (Vr) - -py (V+) |E. [ôpy (Vr) op; op:((]]]
R ||01 = S
(177)
By the Bellman equation in Theorem 3.2 we have g 5(V*), which implies
8(V7) 5 = ((V+) 8(V")]
s
Σ
Σ T(uls) (Vr) - (v+ (V7()))+VVVV -v)
S
Σ
Σ T(als) (Vr) - ( Vz(s) v*()
S 8
< 5 Σ 2| - V 1ssp
V7 V'
S V V*Ila
(178)
Where the last incquality is by Lemma
D.I Thus, the following recursion can be formed
19++1
gpp
99 3. 9.) g%
9t 9 + Br(B, - 97 g3 - gt)
9: gā + 3,(5(V")) - -g + v/ + - - 9t)
< (1 3,) 19: 9pو + 3,( 17 + 14.))
S (1 3.) 9t oo + (.(4 Vo + 1p])
(179)
Thus, taking expectation conditioned on the filtration F yields
[1 - g31] < (1 (3t) gt 9 + (E V| 1* E((n-))
< (1 - 3.) Igt - g5 + 3, (4E [ - V [l E ( - ops (V+)
(180)
41

---

By letting Si = 10 (1 Se), we obtain the T-step recursion as follows:
E 19T - -
S
Cr
1go gel
T-1
+ 5T
3r 4E || - V (VT) opp (Vr)
S1+1
1=0
(r 190
9pl
}3, (4E [||V 11 E 0ōp (VT) op: (V+)
C++1
ST 0g0 - gpوl
3: (4E [|[V Volloo] + |B [opy (VT) op- (V+)]l
T-1
C9 100 - gpو + (4 V - V= + E Topp - Ops (Vr)]
Σ
(181)
t=0
By setting Br =
I 1+I.
we have Cr = 7- S + and ET-1 Be 2log T, 181
implies
E 1 9pl - T
190 g + (SE
- + B Jōpy (VT) op, (Vr)]]) log (182)
Theorem D.3 (Formal version of Theorem 6
Following all notations and assumptions in Theo-
rem D.2 then for contamination uncertainty sets.
1 S T
16K 16KCpvEn log
E
gpl
190 g
V V*
(T' KKepeeeee
/ 2/22A ancC log
log T
tmix log II'
O
(183)
02CPV T
T
VT(1- (1)
For TV distance uncertainty sets,
16K Cp / Cu log T
pr gb S T
190 gol +
Vo
Vo
(T + K)ep .
16 16 TV Vac, T
8 8 CaCC bias
log T
48(1 } JVV2 r
mixx log
a2CpV T T
c2v02
=
logT 7 T
+
tmix v Maaxx log
VStmix2 2 Naax
log 3 T
+ V
Nauax
Lixx log T
VT(1-1)
V1-9
(184)
42

---

For Wasserstein distance uncertainty sets,
16KCp Co log T
oT B
03|
7 190
1Vo Vo
(T K)epva
16v2 2A
Wass 04c log T
8y 22
bins
Wass
log T
48 S2
Mmax
Lmix log T
C2CPVT
cpv02
0
1
l T
+
mix V SNN max
TogT
Stmmix
Mipax
log 2 T
+ VS2
Noxx
mix log T
T
VT(1 (1)
(185)
where all the above variables are defined the same as in Theorem D.2
Proof. By Theorem D.2 taking square root both side and utilizing the concavity of square root function, we have for contamination uncertainty sets,
2KCPvca 1ivo Vo (T K)cp
2/2A Cont
2. a4cu
E - V S
(186)
02 T
for TV distance uncertainty sets,
2KCPVCu 11oo 1o0 + 2V ascu (T (T+K)opvc
C.CCCeTTV
E
| |V--
(187)
0g V T
0:2
for Wasserstein distance uncertainty sets,
E 11- V'
2KCPvG 1 Vo + 2 2. Wass (T + (K+K)cpPV
C4Cu
Ca CaCe bias a22
Wass
(188)
02Cpv TTppyT+R
Regarding the bound for the absolute bias of opp, from Lemma H3 have for contamination uncertainty.
E Tōp (V) Pp. (v)]
(189)
In addition, combining 129
30
with Lemma
F4
we have for for TV distance uncertainty,
E @p: (V) op. (V) 24v5(1 1
Nmax 4
mix
(190)
and for Wasserstein distance uncertainty, we have
E T (V) op. (V) < 24v52
Nmax
tmix
(191)
Combining 86
191 with 182 gives the desired result.
D.4 Proof of Theorem 6.2
We use the result from Theorem D.3 to set E l9T g3 < For contamination uncer- tainty sets we T o
2 マ
log 8(1-y)) resulting in O "(1-7)>
SAr2 log x(1-))
/ ple complexity. For TV and Wasserstein uncertainty set, we set Nmax O log
e[1 ((I->)
and T -o
2 ( (ाा -0(zie log (1 <l->)
combining with Theorem this would result in
SAL2 (11-))²
log VStumi)) c(1-7)
sample complexity.
43

---

E Numerical Validations for Semi-Norm Contractions
In this section, we provide numerical examples that directly verify the one-step strict contraction across the settings studied. These results empirically support the key structural claims used by our analysis.
E.1 Evaluations of Lemma 4.1
Lemma A.2 is the technical backhone for Lemma 4.1 Lemma A.2 constructs the fixed- semi-norm and provides the one-step contraction for given P. Therefore, we perform numerical
evaluations
CemmalA.211 demonstrate the one-step contraction property for Lemmale 4.1
For kernel P with stationary distribution we follow the steps in Appendix A. and construct ||-1|p in (41 with
a = 1m.99.099, 1+p(2)) }, c= 0.2 - aa),
(192)
2
where P ed Then the one-step contraction factor is te<l.
To generate ergodic matrices with dimension n, In be the identity matrix and S, be the cyclic shift matrix defined by S,e, 6/+1 mod x- We provide the following four examples:
Pi = 0.5 I3 + 0.5 S3
. = 0.6 + 0.4.g
.P3 0.55 1 + 0.45 S7
Pi 0.6 0.3 0.1
We generate 1000 random unit vectors and compute each ratio summarized below.
The empirical results
|
matrix n
max span ratio
p((2)
ratiomin
ratiomedian
ratãopao
ratiomax
PI
0.8099
0.9045
0.0239
0.9284
0.3824
0.7950
0.8077
0.8090
P2
0.8718
0.9359
0.0160
0.9519
0.5197
0.8510
0.8687
0.8718
P3
0.9020
0.9510
0.0122
0.9633
0.5861
0,8799
0.8976
0.9014
P4
0,8700
0.9350
0.0162
0.9513
0.4855
0,8226
0.8604
0.8685
Table Empirical one-step contraction ratios for ergodic kernels using the fixed-kerned semi-norm
[|-[P..
E.2 Evaluations of Theorem 4.2
Lemma A.S is the key step for Theorem
2 as Lemma A.8 proves a uniform one-step contraction across all P in the uncertainty set. We therefore perform numerical evaluations on Lemma A.8 to demonstrate the one-step contraction property for Theorem 4.2 under contamination, total variation (TV), and Wasserstein- uncertainty. We select the same P1. Pz, Ps, and P; in Appendix(E.]]aa four examples of the nominal model.
To numerically approximate || defined in 82 certainty set and (ii) using a finite product to approximate the extremal norm. First, we sample family (P(() m C of size m and form
we approximate ||: by (i) discretizing the un-
Q2 = p()) -dd
f = max p(Q:).
We set min (0.99, /2 and choose (0, 1- a.). To approximate the extremal norm, build library of scaled products of the Q.'s up to maximum length K: for each k = 0, 1,..,, K we draw products MaJ Qu. Q the number of such draws each & the "products per length" (denoted samples _per____________ k in the tables). This defines the surrogate
|| [|)]
max
(193)
USkSK.j
44

---

We then set
|||||
(K)
max i=I...m
1Q
+ emmin eEc r - ce
cellext
(194)
We generate 50 random unit vectors r for each sampled uncertainty matrix in { Jm C P, and compute the ratios |
The empirical results of the uncertainty sets studied in our settings |
are summarized below.
nominal
m
coxplea_pen Bateea_per____ mux span ratio
rotio
rationediaa
ratioy.0
rationsx
Pl
5
0.15
30
25
0,8138
0.9069
0.0253
0.9302
0.2210
0.6396
0.8057
0.8134
0.15
30
25
0,8807
0.9403
0.0149
0.9553
0.2957
0.6581
0.8630
0.8785
0.0117
P4
8
0.15
30
25
0.8812
0.9406
0.0148 0.555
0.3739
0.5964
0,8207
0.8624
Table 2: Empirical one-step contraction ratios under contamination uncertainty.
nominaa
a
m
K
hamples_per.
max span ratio
rali0mm
ratiOgeddian
rili0g00
milions
P1
5
0.15
30
25
0.8280
0.9140
0.0215
0.9355
0.3239
0,7609
0.8239
0.8280
30
25
0.9507
0.0123
0,4021
0.7904
0.8862
0.9006
0.15
30
0,9175
0.9588
0.0103
0.6991
0.4457
0.7918
0.8962
0.9162
P4
8
0.15
30
25
0.8805
0.9403
0.0149
0.9552
0.4497
0.7503
0.8449
0.8739
Table 3: Empirical one-step contraction ratios under total variation (TV) uncertainty.
mominal
a
m
K
saxples_per._ _er___
max span ratio
rati0ma
ratiogedtion
ratiogos
ratiousx
P1
5
0.15
30
25
(18184
0.9022
0.0227
09319
0.3698
0,7569
0.8144
018188
0.9587
0.7889
0.8774
7 0.15
30
0,9110
0.9555
0.0111
0.9666
0.4262
0.7818
0.8827
0.9080
P4
8
0.15
30
25
(18758
0.9379
0.0155
0.9344
0.4413
0.7224
0,8518
(18689
Table 4: Empirical one-step contraction ratios under Wasserstein-1 uncertainty.
E.3
Interpretations
Note that for the above tables, span ratio denotes the largest one-step span contraction coeffi- cient over the sampled families. This value equals to for all the settings, meaning no strict one-step contraction in the span. In contrast, the quantities ratiomin: ratiomediann ratiop9o, and ratio summarize the empirical one-step ratios ||Pile (in the robust case) and [| (in the non-robust T[ case) computed under the constructed semi-norms over all sampled kernels P and random unit direc- tions v. They report, respectively, the minimum, median, 90th percentile, and maximum observed value across those tests. In every table we have ratio < 1 so we observe empirical one-step contraction under our semi-norms even when span does not contract. Moreover, ratiomax S 7 (ro- bust case) or ratiomax < 3 (non-robust case), which is consistent with the corresponding theoretical contraction factor guaranteed by our constructions.
T
F
Some Auxiliary Lemmas for the Proofs
Lemma F.1 (Theorem IV in ED, Let Q be bounded set of square matrix such that p(Q) oo for all Q E Q where pl-) denotes the spectral radius. Then the joint spectral radius of Q can be defined
as
(
lim sup p(Q +Q) k-000 k-000.E0
lim sup k-000 Q.EQ
IIQu..QQ111
(195)
where || an arbitrary norm.
Lemma F.2 (Lemma in (45)). Under the setup and notation Appendix B.I.I if assuming the noise has bounded variance of [E[ [| [ [F
< A + Bl
t x || we have
E ||aft|
2² 2²112 Frt
< (16 + 4B)
M M x²) + 2Ap21
(196)
45

---

Lemma F.3 (Theorem D.1 in (39.). The estimator op.(V) obtained by 18) for contamination uncertainty sets unbiased and has bounded variance as follows:
E (V)] op (V): and Var(ōp: (V)) |V
(197)
Lemma F.4 (Ergodic case of Lemma 9 in 34]). For any average-reward MDP with stationary policy πt and the mixing time defined
Tmix
arg min max (14 - 121
(198)
where Pa the finite state Markov chain induced by n, Po any initial probability distribution on S and is its invariant distribution, If Pa is irreducible and aperiodic, then Tmix < +000 and for the value function V, we have
||p S 4Tmix
(199)
46


Reviews:
[{"review_id": "BeuZ2fvAX2", "reviewer": "Reviewer_uoff", "summary": "This paper studies the finite-sample complexity bound for robust policy evaluation in average-reward settings. \nA key technical challenge in this context is that, as in the classic MDP setting, the Bellman operator is no longer a contraction. Moreover, the ambiguity set introduce nonlinearity, making simple the Monte Carlo method not applicable. The authors resolve the first issue by proving the existencce of a seminorm under which the evaluation operator is a contraction, provided that the underlying Markov chain induced by any policy and adversarial case kernel is recurrent and apperiodic. The second issue is addressed with a truncated multilevel Monte Carlo estimator. The combination of the two lead to a $\\widetilde O(n^{-1/2})$ convergent model-free algorithm.", "questions": "- Line 86: The MLMC based estimator in the two Blanchet papers do not need infinite expected samples. Also, the MLMC based Q-learning in [1] has a non asymptotic expected sample complexity of $\\widetilde O(\\epsilon^{-2})$. Could this be adapted in the context of this paper? \n- Line 184: The kernel of a seminorm is not defined. \n- Theorem 3.1 and 3.2 seems very interesting. The authors should consider providing a simple (not span contracting) example to illustrate this new seminorm. \n- Is there a relationship between $1/(1-\\gamma)$ and $t_{mix}$? I would guess that $1/(1-\\gamma) = \\Omega(t_{mix})$, but in general do we have $1/(1-\\gamma) = \\Theta(t_{mix})$? \n- What is the bias level given an optimal allocation of the samples? In MLMC, one would typically get O(1) variance. To converge with constant setpsize, if one step bias is $b$, then the total bias scales like $\\sum_k (1-\\eta)^k \\eta b = b$. So one would make $b = \\epsilon$ to converge. The bias under the truncation at level N is $2^{-N}$ due to the odd and even sampling (I think the analysis in this paper had $2^{-N/2}$ which could be improved). If one use bias to be $2^{-N/2}$, the levels has to be $\\log(\\epsilon^{-2})$. This will use $\\epsilon^{-2}$ samples within one iteration with constant order probability. So, this analysis seem to suggest the current bias bound is not sufficently tight to get $\\epsilon^{-2}$ rate, as it didn't account for the the odd and even sampling in [2]. I am a little concerned about the validity of the convergence analysis. \n- I am wondering why the authors doesn't consider policy optimization. It seems that most of the arguments still goes through. Is it because 3.1 or 3.2 fails? \n\n- Equation (41), would you need the mapping $P\\rightarrow \\rho(Q_P)$ be continuous? \n\n[1] Wang, S., Si, N., Blanchet, J. &amp; Zhou, Z.. (2023). A Finite Sample Complexity Bound for Distributionally Robust Q-learning. Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 206:3370-3398.\n\n[2] Blanchet, J. H., Glynn, P. W., & Pei, Y. (2019). Unbiased multilevel Monte Carlo: Stochastic optimization, steady-state simulation, quantiles, and other applications. arXiv preprint arXiv:1904.09929.", "limitations": "The limitation is not sufficiently discussed. Please see the weaknesses I have listed above.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "The paper analyzes a model-free algorithm (TD learning), which is not only theoretically more challenging than its model-based counterparts, but also potentially generalizable to continuous state space models. Moreover, the paper establishes the contraction property of the Bellman operator under recurrence and aperiodicity, which could be of theoretical value to future work.\n\nHowever, the contraction property does not have a concrete physical interpretation (such as mixing time or the span norm, both commonly used in classical MDP settings), and is not easily accessible due the relevant seminorm is obtained non-constructively. \n\nMoreover, based on some of the results in the paper and my personal expertise in this domain, I believe it should be straightforward to obtain a $\\widetilde O(\\epsilon^{-2})$ sample complexity using model-based methods.\n\nFurthermore, if we consider the minimax sample complexity in this setting, I do not believe it should depend on $(1 - \\gamma)$, which represents the **one-step** contraction factor. In classical MDP settings with mixing, the one-step Bellman operator is not a span contraction (for similar reasons as those discussed in this paper—it is a contraction under a certain semi-norm). Nevertheless, the sample complexity is still $\\widetilde{O}(t_{\\text{mix}} / \\epsilon^2)$, independent of the one-step contraction factor. With that said, I think this is understandable given the focus on model-free average-reward MDP algorithms, which represent a significantly more challenging setting.\n\nGiven these, I think the narrative of the paper should be oriented toward the model-free aspect, emphasizing their algorithm's versatility. \n\nOn the other hand, even though TD learning is interesting in the robust MDP setting due to the nonlinearity introduced by the adversarial dynamics, one could argue that the control (i.e., policy optimization) problem is of greater importance to practitioners.\n\nFinally, there is no numerical validation in the paper to support the theory. I would appreciate it if the authors could provide some numerical experimentation, especially given that I have some reservations about the analysis, as the current bias and variance bounds do not seem to suggest a $\\widetilde O(\\epsilon^{-2})$ sample complexity. See below. I am not certain about this last assessment, but I do believe that the analysis is not tight enough.", "was_revised": true, "final_justification": "The authors are able to address my main concerns about the validity of their approach.", "rebuttal": "We sincerely thank the reviewer for their feedback and valuable suggestions. We address each point carefully and explicitly below:\n\n## **Regarding MLMC (Q1, Q5 and Weaknesses)** ##\n\nThanks for bringing up comparisons between our work and the two Blanchet papers. We note that [1] obtains $\\tilde O(\\epsilon^{-2})$ using unbiased and untruncated MLMC under a smooth‑functional assumption (differentiable with Hölder‑continuous derivative, as mentioned in their Theorem 1), which enables second‑order multilevel cancellation. [2] studies discounted robust RL with KL divergence uncertainty sets, where these conditions hold, so their unbiased‑MLMC analysis in [1] carries through. In contrast, we focus on TV and Wasserstein distance uncertainty sets, and the support functions in our setting are Lipschitz with no uniform differentiability guarantees. Thus, the analysis of the unbiased MLMC in [1] and [2] is no longer applicable. We therefore adopt a different framework where we apply the truncated MLMC method and still yielding the $\\tilde O(\\epsilon^{-2})$ sample complexity.\n\nWe note that we characterize the sample complexity, bias and variance properties of our truncated MLMC approach (Algorithm. 1) in our Theorem 4.1-4.4. In particular, we note that due to truncation, the expected number of samples to perform Algorithm. 1 is $O(N_{\\rm max}) $ instead of $O(2^{N_{\\rm max}})$ with $N_{\\rm max}$ being the maximum truncation level. Thus, we agree with the reviewer that if one uses bias to be $2^{-N/2}$, the level is indeed $O(\\log(\\epsilon^{-2})) $, which is equivalent to $O(\\log(\\epsilon^{-1})) $ (what we wrote in the draft). However, this will use $O(\\log(\\epsilon^{-2}))$ samples instead of $O(\\epsilon^{-2})$ within one iteration with constant order probability, which still leads to our $\\tilde{O}(\\epsilon^{-2})$ sample complexity result. \n\n---\n\n## **Regarding Model-Based Methods (Weaknesses)** ##\nWe agree that our focus is model‑free since the problem of policy evaluation is essentially a model-free approach by its nature, and we will add emphasis on this in the revised draft. We note that the problem is not straightforward even for model-based settings, and indeed there is a new paper [3] in ICML 2025 (which came online after our work was submitted), that studies robust model-based average reward setting with TV, chi-square, and contamination uncertainty sets. We will add this to Related Work in the final version, while note that the approach of model-based that is used in this paper which is reduction from discounted to average does not work well in model-free settings due to higher dependence on $1/(1-\\gamma)$ in the model-free setups.\n\n---\n\n## **Regarding the Semi‑Norm Contraction and $\\gamma$ (Q2-Q4 and Weaknesses)** ##\nThanks a lot for the great suggestion on providing examples to demonstrate the contraction properties in Lemma 3.1 and Theorem 3.2. Due to space constraint, we refer to our additions in the response to Reviewer rBB6 (**Regarding Numerical Validations**), where we provide detailed numerical validations and demonstrate the semi-norm contraction properties.\n\nRegarding the interpretation of $\\gamma$. Note that in Lemma C.3, by setting $\\epsilon \\rightarrow 0$ and  $\\alpha \\rightarrow r^\\star$, our construction allows $\\gamma$ to be made arbitrarily close to $\nr^\\star = \\sup_{P\\in\\mathcal P}\\rho(Q_P)$ defined in Eq. (41). Since $r^\\star$ represents the second‑largest eigenvalue among all the $P\\in\\mathcal P$, this semi-norm is constructive and $\\gamma$ tracks the spectrum that matters for stability. We note that in the reversible (or lazy‑reversible) case, $r^\\star$ directly controls mixing: for each $P$, where we have so $t_{\\mathrm{mix}}=\\tilde O\\big(1/(1-r^\\star)\\big)$ (shown in Theorem 12.4 of [4]). For non‑reversible chains, the standard replacement is the pseudo‑spectral gap via multiplicative reversibilization; we will add a short remark connecting $r^\\star$ to that quantity for completeness.\n\nWe also would like to note that the kernel of a semi-norm is the set of all vectors in the vector space that map to zero under the semi-norm, we will add this explanation in the revised draft to improve clarity.\n\n---\n\n\n## **Regarding Future Work (Q6 and Weaknesses)** ##\n\nWe agree with the reviewer that the policy optimization and control problem is an important direction. However, policy optimization is based on policy evaluation, which is the focus of this paper. Thus, one cannot obtain policy optimization results without having a complete analysis of policy evaluation. Further, we note that the current policy optimization papers in robust average-reward setup [5] assume knowledge of exact sub-gradient, while our method provides actual sampling techniques with finite-time analysis for policy evaluation. Thus, our work can potentially be used in their analysis to replace the knowledge of exact sub-gradient. However, a detailed analysis is left as a future work, and will be mentioned in the paper. \n\n---\n\n## **Regarding the Mapping $P\\mapsto\\rho(Q_P)$ (Q7)** ##\n\nWe note that the continuity of the mapping holds under the assumptions in the paper. On finite ergodic chains, the stationary distribution $d_P$ depends continuously  on $P$; hence $Q_P=P-\\mathbf e d_P^\\top$ is continuous in $P$. The spectral radius is a continuous function of the matrix entries (Appendix D in [6]), so the composition $P\\mapsto\\rho(Q_P)$ is continuous on the ergodic region. We will add the detailed proof on this in the final version.\n\n---\n\n# References\n\n[1] Unbiased multilevel Monte Carlo: Stochastic optimization, steady-state simulation, quantiles, and other applications, 2019.\n\n[2] A Finite Sample Complexity Bound for Distributionally Robust Q-learning, 2023.\n\n[3] A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward, 2025.\n\n[4] Markov Chains and Mixing Times, 2017.\n\n[5] Policy Optimization for Robust Average Reward MDPs, 2024.\n\n[6] Matrix Analysis, 2012."}, {"review_id": "7Z30c8ZT0r", "reviewer": "Reviewer_rBB6", "summary": "The paper investigates the finite-sample performance of policy evaluation in robust average-reward Markov Decision Processes (MDPs), where the transition dynamics are only partially known. The authors first establish that the robust Bellman operator, central to the robust dynamic programming framework, is a contraction mapping---guaranteeing convergence of value iteration. Building on this property, the paper derives a near-optimal sample complexity bound of $\\tilde{O}(\\epsilon^{-2})$ for estimating the value of a fixed policy under worst-case transition dynamics. These results provide strong theoretical guarantees for robust policy evaluation in average-reward settings.", "questions": "1) I am confused by the sample requirements in Algorithm~1. It appears that exponentially many i.i.d.\\ samples are needed from the generative model. Is this interpretation correct? If so, this would be practically infeasible and significantly limit the applicability of the method. Please clarify.\n    \n2) The definition of the support function in Theorem 2.1 is unclear. I assume the intended definition is $\\sigma(V) = \\min_{p} \\langle p, V \\rangle$, but the inner product notation is missing. Similar notational issues also appear in Equation (7). Please revise for precision.\n    \n3) The vector \\(e\\) in Lemma~3.1 is used without being defined. Please introduce and explain it when it first appears.\n    \n4) The references section appears to contain duplicate entries, specifically [8] and [9]. Please clean up and consolidate the bibliography.", "limitations": "The paper has two significant limitations that are not easily addressed. First, the assumption of finite state and action spaces confines the results to relatively simple environments, limiting their applicability to the large-scale or continuous domains commonly encountered in modern reinforcement learning. Second, the dependence on a generative model—capable of providing i.i.d.\\ samples (exponentially many?) on demand—is often unrealistic, as many practical settings involve only a single trajectory or a fixed batch of data. While these assumptions are standard in theoretical work, it would be valuable for the authors to comment on possible strategies to relax them or to highlight the key obstacles in doing so.", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 3, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths:**\n\n1) The paper tackles a timely and important problem in reinforcement learning, namely robust policy evaluation in average-reward MDPs—a topic of both theoretical and practical significance.\n\n2) Establishing near-optimal sample complexity bounds is a strong theoretical contribution and highlights the algorithm’s statistical efficiency.\n\n3) The presentation is generally clear, and the technical results are well-structured and accessible.\n\n**Weaknesses:**\n\n1) The paper lacks numerical validation. While the sample complexity result is theoretically compelling, the absence of empirical experiments makes it difficult to assess the practical utility and robustness of the proposed approach.\n\n2) Assumption 2.3 appears to be quite restrictive and may not hold except for very small ambiguity sets $\\mathcal{P}$. It would be helpful to provide a practical discussion or example illustrating how this assumption can be verified or approximately satisfied in realistic settings.", "was_revised": true, "final_justification": "I would like to thank the authors for the careful revision and in particular for providing some numerical evidence for the theoretical results in this paper. Given that many of my points have been clarified, I am willing to raise my score.", "rebuttal": "We sincerely thank the reviewer for their feedback and valuable suggestions. We address each point carefully and explicitly below:\n\n## **Regarding Numerical Validations (Weakness 1)** ##\n\nWe like to note that this work is primarily theoretical, and the full empirical evaluation of robust TD learning is left as a future work for application papers. That said, because our guarantees hinge on the one‑step semi‑norm contraction properties (characterized in Lemma 3.1 and Theorem 3.2), we now include numerical evaluations that directly verify strict contraction across the settings studied. These results empirically support the key structural claim used by our analysis.\n\n## Evaluation of Lemma 3.1\n\nLemma C.2 is the technical backbone for Lemma 3.1, as Lemma C.2 constructs the fixed‑kernel seminorm and provides the one-step contraction for a given $P$. So we perform numerical evaluations on Lemma C.2 to demonstrate the one-step contraction property for Lemma 3.1.\n\nFor an ergodic Markov matrix $P$ with stationary $d$, we follow the steps in Appendix C.1 and construct $||\\cdot||_P$ in Eq. (36) with $\\alpha=\\min(0.99,(1+\\rho(Q))/2)$ and $\\epsilon=0.25(1-\\alpha)$ where $Q=P-\\mathbf ed^\\top$. Then the one‑step contraction factor would be $\\beta=\\alpha+\\epsilon<1$.\n\nTo generate ergodic matrices with dimension $n$, let $I_n$ be the identity matrix and $S_n$ be the cyclic shift matrix $(S_ne_i=e_{i+1 \\bmod n})$. We provide the following 4 examples:\n\n- $P_1 = 0.5I_5 + 0.5S_5$\n- $P_2 = 0.6I_6 + 0.4S_6$\n- $P_3 = 0.55I_7 + 0.45S_7$\n- $P_4 = 0.6I_8 + 0.3S_8 + 0.1S_8^2$\n\nWe generate 1000 random unit vectors $x$ and calculate each of the ratio $ \\frac{||P_i x||_P}{||x||_P}$. We present the empirical results as follows:\n\n\n|matrix|$n$|max span ratio|$\\rho(Q)$|$\\alpha$|$\\epsilon$|$\\beta$ |ratio_min|   ratio_median|ratio_p90|ratio_max|\n|:-|-:|-:|-:|-:|-:|-:|-:|-:|-:|:-|\n|P1|5|1|0.8090|0.9045|0.0239|0.9284|0.3824|0.7950|0.8077|0.8090|\n|P2|6|1|0.8718|0.9359|0.016|0.9519|0.5197|0.8510|0.8687|0.8718|\n|P3|7|1|0.9020|0.9510|0.0122|0.9633|0.5861|0.8799|0.8976|0.9014|\n|P4|8|1|0.8700|0.9350|0.0162|0.9513|0.4855|0.8226|0.8604|0.8685|\n\n## Evaluation of Theorem 3.2\n\nLemma C.4 is the key step for Theorem 3.2 as Lemma C.4 proves a uniform one‑step contraction across all $P$ in the uncertainty. So we perform numerical evaluations on Lemma C.4 to demonstrate the one-step contraction property for Theorem 3.2 under contamination, TV, and Wasserstein-1 distance uncertainty set. We select $P_1$, $P_2$, $P_3$, and $P_4$ as 4 examples of the nominal model.\n\n\nTo perform numerical approximation of $\\lVert\\cdot\\rVert_{\\mathcal P}$ defined in Eq. (50), we approximate $\\lVert\\cdot\\rVert_{\\mathcal P}$ by (i) discretizing the uncertainty set and (ii) using a finite‑product to approximate the extremal‑norm. First, we sample a family $\\{P^{(i)}\\}_{i=1}^m\\subset\\mathcal P$ \n\nof size $m$ and form $Q_i:=P^{(i)}-\\mathbf e d_{P^{(i)}}^\\top$ with $\\hat r=\\max_i \\rho(Q_i)$. We set $\\alpha=\\min(0.99,(1+\\hat r)/2)$ and $\\epsilon\\in(0,1-\\alpha)$. To approximate the extremal norm, we build a library of scaled products of the $Q_i$’s up to maximum length $K$ for each $k=0,1,\\dots,K$ we draw a set of products $M_{k,j}=Q_{i_k}\\cdots Q_{i_1}$; the count of such draws at each $k$ is the products per length (denoted as **samples_per_k** in the table). This defines the surrogate\n$||z||_{\\rm ext}^{(K)}$\n\n=$\\max_{0\\le k\\le K,j}\\ \\alpha^{-k}||M_{k,j}z||_2$.\nWe then set\n\n$||x||_{\\mathcal P}^{(K)}$\n\n$=\\max_{i=1,\\dots,m} ||Q_i x||_{\\rm ext}^{(K)}$\n\n$+\\epsilon\\min_{c}||x-c \\mathbf e||_{\\mathrm{ext}}^{(K)},$\n\nWe generate 50 random unit vectors $x$ for each of the sampled uncertainty matrix inside  \n\n\n$\\{P^{(i)}\\}_{i=1}^m\\subset\\mathcal P$\n\n\n, and calculate each of the ratio of\n\n\n$ ||P^{(i)} x||_{\\mathcal{P}} $ \n\n\nand  $||x||_{\\mathcal{P}}$\n\n\nWe present the empirical results as follows:\n\n**Contamination**\n\n|nominal distribution|$n$|$\\delta$|$m$|$K$|samples_per_k|max span ratio|$\\hat{r}$|$\\alpha$|$\\epsilon$|$\\gamma$ |ratio_min |ratio_median |ratio_p90 |ratio_max|\n|:-|:-|:-|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|\n|P1|5|0.15|30|3|25|1|0.8138|0.9069|0.0233|0.9302|0.2210|0.6396|0.8057|0.8134|\n|P2|6|0.15|30|3|25|1|0.8807|0.9403|0.0149|0.9553|0.2957|0.6581|0.8630|0.8785|\n|P3|7|0.15|30|3|25|1|0.9067|0.9534|0.0117|0.9650|0.3217|0.6683|0.8700|0.8901|\n|P4|8|0.15|30|3|25|1|0.8812|0.9406|0.0148|0.9555|0.3739|0.5964|0.8207|0.8624|\n\n\n**TV**\n\n|nominal distribution|$n$|$\\delta$|$m$|$K$|samples_per_k|max span ratio|$\\hat{r}$|$\\alpha$|$\\epsilon$|$\\gamma$ |ratio_min |ratio_median |ratio_p90 |ratio_max|\n|:-|:-|:-|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|\n|P1|5|0.15|30|3|25|1|0.8280|0.9140|0.0215|0.9355|0.3239|0.7609|0.8239|0.8280|\n|P2|6|0.15|30|3|25|1|0.9013|0.9507|0.0123|0.9630|0.4021|0.7904|0.8862|0.9006|\n|P3|7|0.15|30|3|25|1|0.9175|0.9588|0.0103|0.9691|0.4457|0.7918|0.8962|0.9162|\n|P4|8|0.15|30|3|25|1|0.8805|0.9403|0.0149|0.9552|0.4497|0.7503|0.8449|0.8739|\n\n\n**Wasserstein-1**\n\n|nominal distribution|$n$|$\\delta$|$m$|$K$|samples_per_k|max span ratio|$\\hat{r}$|$\\alpha$|$\\epsilon$|$\\gamma$ |ratio_min |ratio_median |ratio_p90 |ratio_max|\n|:-|:-|:-|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|-:|\n|P1|5|0.15|30|3|25|1|0.8184|0.9092|0.0227|0.9319|0.3698|0.7569|0.8141|0.8188|\n|P2|6|0.15|30|3|25|1|0.8900|0.9450|0.0138|0.9587|0.4257|0.7889|0.8774|0.8894|\n|P3|7|0.15|30|3|25|1|0.9110|0.9555|0.0111|0.9666|0.4262|0.7818|0.8827|0.9080|\n|P4|8|0.15|30|3|25|1|0.8758|0.9379|0.0155|0.9534|0.4413|0.7224|0.8518|0.8689|\n\n## Interpretations\n\nNote that for the above tables, **max span ratio** denotes the empirical largest one‑step span contraction coefficient over the sampled families. This value equals to $1$ for all the settings, meaning no strict one‑step contraction in the span.\n\nThe quantities **ratio\\_min / ratio\\_median / ratio\\_p90 / ratio\\_max** summarize the empirical one‑step ratios computed under the constructed semi-norms over all sampled $P$ and random unit directions $x$. They report, respectively, the minimum, median, 90th percentile, and maximum observed value across those tests. In every table we have **ratio\\_max < 1**, so we observe empirical one‑step contraction under our semi-norms even when span does not contract. Moreover, **ratio\\_max $\\le$ $\\gamma$** (robust case) or **$\\le$ $\\beta$** (non-robust case), which is consistent with the corresponding **theoretical contraction factor** guaranteed by our constructions.\n\nThe above numerical results and the code for the experiments would be released in the revised manuscript.\n\n---\n\n## **Regarding Assumption 2.3 (Weakness 2)** ##\n\nThanks for raising this question. We provide Remark 2.4 after this Assumption 2.3 showing how it relaxes to *ergodicity of the nominal model only* when the uncertainty radius is small. The assumption of ergodicity for nominal model aligns with common practice in the non‑robust average‑reward RL literature (such as [1]-[3]). Additionally, In our numerical validations, we also assume only the nominal model is ergodic and still observe strict contraction for reasonably large radii, in our case, $\\delta=0.15$.\n\n---\n\n## **Regarding Algorithm 1's Sample Complexity (Q1)** ##\n\nWe would like to clarify that in Algorithm. 1, the expected sample cost of a single call to the robust‑expectation oracle is $O(N_{\\max})$ by Theorem 4.1, and in Appendix F4 we set $N_{\\max}={O}(\\log(1/\\epsilon))$ to control bias/variance. Hence we note that Algorithm 1 does not require exponentially many i.i.d. samples; the overall policy‑evaluation complexity remains $\\tilde O(\\epsilon^{-2})$. Due to space constraint, we refer to our response to Reviewer uoff (**Regarding MLMC**) for a more detailed explanation of why we do not need exponentially many i.i.d. samples. We will mention the above in the revised draft to prevent this misunderstanding.\n\n---\n\n## **Regarding Typos and Definition of $\\mathbf e$ (Q2-Q4)** ##\nThanks for identifying the typos, we agree with the review on the definition of $\\sigma(V)$ and the duplicated reference, and they will be fixed in the revised draft. We note that $\\bf e$ is initially defined in line 144, we will also re-emphasize this definition in Lemma 3.1 in the revised draft.\n\n---\n\n## **Regarding Limitations** ##\n\nWe agree that our tabular analysis and the use of a generative model are simplifying assumptions. Our goal here is to establish the first finite‑sample guarantees for policy evaluation in robust average‑reward RL. To the best of our knowledge, the most closely related works cited in Appendix A also study tabular problems and adopt a generative‑model abstraction. This abstraction is particularly natural in the robust setting, where the motivation is assuming access to the simulated environment. We have noted these limitations in the conclusion. We view these as promising directions but outside the scope of this first finite‑sample study.\n\n\n---\n\n## **References** ##\n\n[1] Finite Sample Analysis of Average-Reward TD Learning and Q-Learning, 2021.\n\n[2] Learning Infinite-horizon Average-reward MDPs with Linear Function Approximation, 2021.\n\n[3] A sharper global convergence analysis for average reward reinforcement learning via an actor-critic approach, 2025."}, {"review_id": "V7pciDmaD9", "reviewer": "Reviewer_qbnD", "summary": "The paper studies policy evaluation for average-reward infinite-horizon reinforcement learning where the estimated value is robust to uncertainty in the data / observed transitions. They provide a finite-sample result that is order-optimal in the accuracy level $\\varepsilon$. This is achieved by considering the robust Bellman operator and showing that it is a contraction with respect to a semi-norm. However, this robust Bellman operator requires the estimation of a support function. They provide a procedure to estimate this support function (based on a truncated multi-level monte carlo algorithm), that can then be used to iteratively apply the robust Bellman operator, providing the finite-sample result.", "questions": "1. In the formulation section, the uncertainty set is introduced as the  $(s, a)$-rectangular compact uncertainty set, which is a bit confusing because it seems like this is the type of uncertainty set that will be considered instead of contamination, total variation and Wasserstein distance. In addition, because ultimately only samples from the centroid of this uncertainty set (the nominal MDP) are used, I wonder what the value is in introducing the rectangular set. Is it not equivalent and simpler to only define/introduce the nominal transitions and then consider the uncertainty set as defined by the contamination model, TV and Wasserstein distance ? Or am I missing something ?\n2. Following from the previous question, it would also be useful to provide some motivations for the different types of uncertainty sets. While the contamination model provides an algorithm and analysis that is much simpler, I assume the other two are considered because they provide more realistic in the way they model uncertainty ?\n3. Here is a list of a few typos: l.136: “definied”; Grammar l.144-145; l.187 typo in definition of E, should be $E = e {d^\\pi}^T$ I think;\n4. How easy/hard is it to solve the robust policy evaluation problem when you know the true nominal transitions ? If it is easy, since you “focus on the model-free setting”, could you comment on the difficulties of a model-based approach where potentially you use all the samples to estimate the nominal transitions and then use this estimate as the ground-truth ?\n5. I was initially a bit confused by the statement of Theorem 2.1 where it seemed to me that $g$ should depend on the state and not be a scalar. This was clarified later when it was mentioned that under the ergodicity assumption, the average-reward did not depend on the starting state. Is this what is being used in Theorem 2.1 or does Theorem 2.1 also hold without the assumption of ergodicity ? And if Theorem 2.1 does require the assumption of ergodicity, I would suggest re-orgnaising or at least mentioning or referring to the independence of $g$ from the starting-state before Theorem 2.1.\n6.  In the description of Algorithm 2, in line 18 the expected Bellman residual is averaged across all states. I am surprised that this work and that it should not be weighted by how often states are actually visited – could you comment ?", "limitations": "yes", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strengths\n1. The paper is very well-written/structured and easy to follow. The proof-sketches are clear and provide some good intuition for the general proof ideas.\n2. The work provides the first finite-sample results, while prior works only established asymptotic results.\n3. The algorithms extend known algorithm in novel non-trivial ways. The analysis also includes some key novel steps such as the contraction of the robust Bellman operator with respect to a semi-norm.\n\nWeaknesses\n1. While it is explicitly stated that the finite-time bound is order-optimal in $\\varepsilon$, optimality is not discussed for other quantities (e.g. S, A). Even if it is not optimal, it would be helpful to have a discussion on the dependence of these other quantities. The lower-bound justifying the claim that the dependence on $\\varepsilon$ was not discussed as far as I could tell.\n2. The one weakness of the structure would be that Section 5 feels a bit rushed, there is little discussion of the results Theorem 5.1 and 5.2 (which connects to the previous point). In addition, the difference in the results between the contamination model and the TV/Wasserstein distance could also be discussed more. In particular the difference only appears to be logarithmic in Theorem 5.1, and that difference comes from the value of $N_{\\max}$ (which it would also be useful to have the explicit setting of it in the main text). A brief discussion on how these policy evaluation methods could be fit in within a procedure to find the optimal policy would also be welcome.\n3. See questions below for some slightly confusing parts.", "was_revised": true, "final_justification": "I believe this paper is of good quality, clarity, significance and originality. The points raised during my review, which were mostly about clarifying details that I did not fully understand were addressed and should be corrected adequately in the final version. I recommend acceptance.", "rebuttal": "We sincerely thank the reviewer for their feedback and valuable suggestions. We address each point carefully and explicitly below:\n\n\n## **Regarding Optimality and Lower Bounds (Weakness 1)** ##\n\nWe agree our rates are order‑optimal only in $\\epsilon$ ($\\tilde O(\\epsilon^{-2})$). Regarding other factors (e.g., $|\\mathcal S|, |\\mathcal A|$ and structural constants), we will clarify that our bounds have a linear $|\\mathcal S||\\mathcal A|$ factor from per–state–action oracle calls, and also depend on the contraction gap $1-\\gamma$, the span bound on $V$, and an additional $\\log(1/\\epsilon)$ from truncation in the TV and Wasserstein cases.\n\nRegarding the lower bounds, we note that classical regret lower bound for finding an optimal policy in non-robust average reward reinforcement learning in [1] is $\\Omega(\\sqrt{|S| |A| T D})$ where $D$ denotes the diameter of the MDP. However, this does not directly translate into a policy‑evaluation sample‑complexity lower bound of $\\Omega(\\sqrt{S A D} \\epsilon^{-2})$. This is because the conversion from regret in control to estimation error in evaluation is non‑trivial and depends on additional structure (e.g., mixing time/diameter and whether a generative model is available). To the best of our knowledge, there have been no works specifically characterizing the exact lower bound for policy evaluation in (robust) average reward reinforcement learning with the focus on $|S|$ and $|A|$. We will therefore not claim tightness in $|\\mathcal S| |\\mathcal A|$ and treat sharpening these dependencies as open. Regarding the lower-bound justifying the claim that the dependence on $\\epsilon$, we note that we provide the standard mean estimation as a hard example and demonstrate the sample complexity of $\\Omega(\\epsilon^{-2})$ in Appendix F.2. We will mention the above in our revised draft.\n\n---\n\n## **Regarding Section 5 (Weakness 2)** ##\n\nWe note that Section 5 is a bit concise due to page constraints, and we will expand it in the final version due to availability of an additional page. We have provided the detailed analysis for this Section in Appendix F, some of the key details can be moved to Section 5 with additional space availability in the final version. We would add the discussion of the additional logarithmic terms in the sample complexity results for TV and Wasserstein distance uncertainty sets. These are due to the bias of the estimators for the support functions $\\hat{\\sigma}(V)$ in Algorithm 1. In contrast, the estimator of the support function in the contamination uncertainty set is unbiased (as shown in Eq. (19)), and thus the corresponding sample complexity for policy evaluation not have the logarithmic terms. \n\nWe also agree that a brief discussion on how these policy evaluation methods could be fit in within a procedure to find the optimal policy is important, specifically, our algorithm can be used to estimate the robust policy sub-gradients, which can be then utilized to perform policy optimizations accordingly, we will add the above in the revised draft.\n\n---\n\n## **Regarding Rectangularity (Q1)** ##\n\nThanks for raising up this point. We note that our algorithms do focus on **contamination, TV, and Wasserstein** ambiguity around a nominal model $P$. We will clarify the presentation by first fixing $P$, and then defining the $(s,a)$‑rectangular set as $\\mathcal U=\\prod_{s,a}\\mathcal U_{s,a}$ where $\\mathcal U_{s,a}$ is, respectively, a contamination/TV/Wasserstein neighborhood of $P(\\cdot\\mid s,a)$. In our algorithms, the nominal generative model first supplies samples from $P$, and then we compute the support function $\\min_{q\\in\\mathcal U_{s,a}}\\langle q, V\\rangle$ by **decoupling across $(s,a)$**, this procedure is achievable due to rectangularity assumption. Thus, our $(s,a)$‑rectangular assumption makes Algorithm 1 implementable (closed‑form for contamination; truncated‑MLMC for TV/W) and is standard in robust DP to preserve Bellman‑style decomposability. We will add the above to the revised draft.\n\n---\n\n## **Regarding Motivations for Different Uncertainty Sets (Q2)** ##\n\nWe provide the motivations for the different types of uncertainty sets studied in this work as follows:\n\n* **Contamination ($\\delta$).** Models outliers or rare faults [2]: with prob. $\\delta$, the next‑state law can be arbitrary (e.g., sensor glitch or unmodeled jump to a bad region). Leads to a simple worst‑case expectation combining $P$ with the worst state value.\n* **Total variation (TV radius).** Models categorical misspecification or discretization error [3]: bounded $\\ell_1$ mass shift per $(s,a)$; captures sparse but possibly large reallocation of probability mass.\n* **Wasserstein (metric radius).** Models smooth model drift when states have a geometry [4] (e.g., position/velocity): mass can move to nearby states with cost proportional to distance; realistic for learned simulators and dynamics linearization.\n\nWe will add a compact paragraph with these examples in the revised draft\n\n---\n\n## **Regarding Typos (Q3)** ##\n\nThanks for identifying the typos, we agree with the review on the definition of $E$. The typos will be fixed in the revised draft.\n\n---\n\n## **Regarding Model-Based Methods (Q4)** ##\n\nWe agree that our focus is model‑free setting. We note that the model-based counterpart is not straightforward, and there is a new paper [5] in ICML 2025 (which came online after our work was submitted), that studies robust model-based average reward setting with TV, chi-square, and contamination uncertainty sets. We will add this to Related Work in the final version, while note that the approach of model-based that is used in this paper which is reduction from discounted to average does not work well in model-free settings due to higher dependence on $1/(1-\\gamma)$ in the model-free setups.\n\n---\n\n## **Regarding $g$ and Theorem 2.1 (Q5)** ##\n\nWe agree $g^\\pi$ is a scalar independent of the starting state under a standard **unichain/ergodicity** assumption. Our Theorem 2.1 indeed assumes ergodicity later in the section. Thanks for pointing this out. we will move that assumption next to the theorem statement to avoid ambiguity in the revised draft.\n\n---\n\n## **Regarding Line 18 in Algorithm 2 (Q6)** ##\n\nThanks for pointing out this detail. In our algorithm, we use uniform averaging to control the span/semi‑norm uniformly over states. The analysis also goes through with stationary‑distribution weighting ($d_{P}$); we will add a remark noting this variant and that it can reduce variance in practice without changing the rate.\n\n---\n\n## **References** ##\n\n[1] Near-optimal regret bounds for reinforcement learning, 2008.\n\n[2] A General Decision Theory for Huber’s $\\epsilon$-Contamination Model, 2017.\n\n[3] Partial Policy Iteration for $L_1$-Robust Markov Decision Processes, 2021.\n\n[4] First-Order Methods for Wasserstein Distributionally Robust MDPs, 2021.\n\n[5] A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward, 2025."}, {"review_id": "GM2ClEjJEh", "reviewer": "Reviewer_EMhU", "summary": "This paper proposes an algorithm to solve the policy evaluation problem in the context of robust average reward RL. To achieve this, it analyzes the contractivity of the robust Bellman operator under a well-chosen semi-norm, then proposes an efficient estimation method for approximating a subproblem appearing when computing the Bellman operator, and then finally proposes an iterative sample-based algorithm to approach the fixed point of the robust Bellman equation. Sample complexities are provided for this algorithm.", "questions": "- How do existing work dedicated to the discounted setting (cited as [25, 29, 16, 15, 14] in the related work) relate to the developed method and sample complexities? Specifically, is the proposed algorithm of the present paper similar, or fundamentally different? Is there any kind of equivalence / correspondence between the average and discounted case, as could be suggested by Theorem 3.2?\n- Is it possible to illustrate the $\\tilde O(\\epsilon^{-2})$ convergence rate of the algorithm on a very simple toy example?\n- In Theorems 5.1 and 5.2, the robustness level (quantified by $\\delta$) does not appear explicitly in the convergence rates. If this dependence is simple, is it possible to make it explicit in the rates? In particular, what happens when $\\delta \\rightarrow 0$? Is it possible to relate the robust TD algorithm to its non-robust counterpart?\n- The  $O(\\epsilon^{-2})$ sample complexity is known to be optimal for the non-robust policy evaluation problem. Do you know of any lower-bounds in the robust setting?\n- In line 149, $P^a_s$ should be replaced by $\\tilde P^a_s$.\n- In line 114, the simplex $\\Delta$ is not defined.\n- From lines 146 to 158, it seems that $\\Delta(S)$ and $\\Delta(|S|)$ are used interchangeably.", "limitations": "Limitations are mentioned in the conclusion about the ergodicity assumption and the finite state space setting.", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 4, "clarity": 4, "significance": 3, "originality": 3, "strengths_and_weaknesses": "This paper proposes a very complete analysis of the robust average-reward policy evaluation problem. The presentation is very clear and progressive, making the paper easy to read and follow. The proofs of the main results look technically solid, although I could not check all the details of the appendix. The tackled setting looks interesting, yet it is somehow difficult to evaluate its practical reach, not so much discussed. One possible limitation of the paper in its present form is that there is no numerical illustration of the proposed algorithm. Other weaknesses of this very thorough work are, in my sense, minor, and are more related to open problems that could be subsequently studied (see questions below).", "was_revised": true, "final_justification": "This paper proposes a very complete analysis of the robust average-reward policy evaluation problem. The presentation is clear. The authors added some numerical illustration during the rebuttal. The few limitations of this paper by no means justify that it should be rejected. Therefore I will keep my score and recommend to accept.", "rebuttal": "We sincerely thank the reviewer for their feedback and valuable suggestions. We address each point carefully and explicitly below:\n\n## **Regarding Numerical Illustrations (Weaknesses and Q2)** ##\n\nWe would like to note that this work is primarily theoretical, and the full empirical evaluation of robust TD learning is left as a future work for application papers. That said, because our guarantees hinge on the one‑step semi‑norm contraction properties (characterized in Lemma 3.1 and Theorem 3.2), we now include numerical evaluations that directly verify strict contraction across the settings studied. These results empirically support the key structural claim used by our analysis. Due to space constraint, we refer to our additions in the response to Reviewer rBB6 (**Regarding Numerical Validations**).\n\n---\n\n## **Regarding Discounted Robust RL Methods (Q1)** ##\n\nWe make the following comparisons between our work and the prior robust discounted RL works. In discounted RL, contraction comes for free from the discount factor $\\beta<1$ in a (weighted) sup-norm [1], and standard stochastic fixed point iterations yields rates accordingly. In contrast, average-reward has no inherent contraction and our analysis builds a new semi-norm under which the **robust average-reward** operator is a contraction via ergodicity. The algorithmic analysis is therefore fundamentally different from discounted works, and we will add a short remark clarifying this correspondence and the different constants.\n\n---\n\n## **Regarding Robust Level $\\delta$ (Q3)** ##\n\nThanks for bringing up this important point. We note that the bound for contamination (Eq. 138) and Wasserstein (Eq. 141) do not have a dependance over $\\delta$, and thus the limit as $\\delta\\to 0$ is the same. Thus, the result do not degrade with increasing $\\delta$. However, we note that contraction factor depends on $\\delta$ since the maximum spectral radius in the uncertainty set will increase with $\\delta$. However, there is an additional factor of $(1+\\frac{1}{\\delta})$ for the TV uncertainty set (see Eq. 128, 139), which is a loose bound and is left as a future work to make this tighter. We will mention the discussion in the final version. \n\n\n---\n\n## **Regarding Lower Bounds (Q4)** ##\n\nWe note that since the non-robust serves as a special case for the robust policy evaluation, the lower bound of non-robust can serve as a hard example for the robust setting. Nevertheless, obtaining tight lower bounds that also track $\\delta$ for robust evaluation remains an interesting open problem. We will mention the above in the revised version.\n\n---\n\n## **Regarding Typos and the Missing Definition of $\\Delta$ (Q5-Q7 and Paper Formatting Concerns)** ##\n\nThanks for identifying the typos, and we will fix them in the revised draft. In particular, we will define the simplex $\\Delta(\\mathcal S)$ as the probability simplex over the state space and use this notation consistently.\n\n---\n\n## **References** ##\n\n[1] Weighted Sup-Norm Contractions in Dynamic Programming: A Review and Some New Applications, 2012."}]

Author rebuttal:

Meta-review: This paper develops an algorithm based on MLMC to solve the policy evaluation problem for robust average-reward reinforcement learning, and derives the finite sample analysis. The overall sample complexity is $O(\epsilon^{-2})$. In order to solve this problem, this paper develops some interesting results, including the contraction property of the Bellman operator. The reviewers requested numerical results during the discussion, and the authors have provided them. It would strengthen the paper if these results were incorporated into the future version of this paper. This is the first paper providing finite sample analysis for robust average-reward RL. Given the significance of the results, I therefore recommend acceptance of this paper.
Decision: Accept (poster)