A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Authors: Zachary Andrew Roch
George K. Atia
Yue Wang
Venue: ICML 2025 poster (2025)
Keywords: Robust Reinforcement Learning
Average Reward
Primary area: reinforcement_learning

Abstract: Robust reinforcement learning (RL) under the average reward criterion, which seeks to optimize long-term system performance in uncertain environments, remains a largely unexplored area. To address this challenge, we propose a reduction-based framework that transforms robust average reward optimization into the more extensively studied robust discounted reward optimization by employing a specific discount factor. Our framework provides two key advantages. 
**Data Efficiency**: We design a  model-based reduction algorithm that achieves near-optimal sample complexity, enabling efficient identification of optimal robust policies; **Scalability**: By bypassing the inherent challenges of scaling up average reward optimization, our framework facilitates the design of scalable, convergent algorithms for robust average reward optimization leveraging function approximation. Our algorithmic design, supported by theoretical and empirical analyses, provides a concrete solution to robust average reward RL with the first data efficiency and scalability guarantees, highlighting the framework’s potential to optimize long-term performance under model uncertainty in practical problems.

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Zachary Roch
George Atia 12
Yue Wang"
1
Abstract
(Silver et al., 2016; Zha et al., 2021), and video games (Wei et al., 2022; Liu et al., 2022a), RL often experiences significant performance degradation in practical settings. This phenomenon, known as the Sim-to-Real gap, arises from discrepancies between the training environment and the deployment environment. In simulation- based applica- tions like games, the training and deployment environments are typically identical and vanilla RL performs well. How- ever, in real-world scenarios, differences such as modeling errors, perturbations, partial observability, and potential ad- versarial attacks introduce model mismatches between the training and deployment environments, resulting subopti- mal policies and poor performance outcomes, undermining the reliability of RL in practical applications.
Robust reinforeement learning (RL) under the av- erage reward criterion, which seeks to optimize long-term system performance in uncertain envi- ronments, remains largely unexplored area. To address this challenge, we propose a reduction- based framework that transforms robust average reward optimization into the more extensively studied robust discounted reward optimization by employing specific discount factor. Our frame- work provides two key advantages. Data Effi ciency: We design model-basee reduction al- gorithm that achieves near-optimal sample com- plexity, enabling efficient identification of optimal robust policies; Scalability: By bypassing the in- herent challenges scaling up average reward optimization, our framework facilitates the design of scalable, convergent algorithms for robust av- erage reward optimization leveraging function ap- proximation. Our algorithmic design, supported by theoretical and empirical analyses, provides a concrete solution to robust average reward RL with the first data efficiency and scalability guar- antees, highlighting the framework's potential to optimize long-term performance under model un- certainty in practical problems.
To address this issue, framework of robust RL was in- troduced (Bagnell et al., 2001; Nilim & El Ghaoui, 2004; Iyengar, 2005). It deviates from vanilla RL by consider- ing a set of environment transition dynamics instead of a fixed one, and its goal to optimize performance under the worst-case scenario across these models, which provides performance guarantees across all uncertain environments within the defined uncertainty set, making the policy more robust to model mismatches and more generalizable.
On the other hand, different reward criteria in (robust) RL can result in substantially distinct problem settings. Among these, the discounted reward criterion the most extensively studied. While offers elegant mathematical properties, its focus short-term rewards can lead to suboptimal long- term performance due the exponential decay of rewards. In practical applications such as queuing control, supply chain inventory management, and communication networks (Kober et al., 2013), however, evaluating policies based on their long-term average performance becomes crucial. This highlights the importance of optimizing the long- average reward in environments with uncertainty, motivating our focus robust RL under average reward in this paper.
1. Introduction
Reinforcement Learning (RL) aims to optimize agent's performance by identifying policy that maximizes cumula- tive rewards based on specified criterion while interacting with an environment. Despite its remarkable success in ap- plications such as synthetic control problems, board games
'Department of Electrical and Computer Engineering DDeparmment of Computer Science, University of Central Florida. Orlando, Florida. Correspondence to: Zachary Roch <zachary.roch @ edf.. George Atia <george. ateeratttau...du... Yue Wang <-ue. wang @ucf.edu>.
Despite its practical importance, robust RL under average reward generally more complex than its discounted coun- terpart due to its dependence on the limiting behavior of the underlying stochastie processes, and hence understudied. Recent work (Wang et al., 2023e; Grand-Clemm 2023) further emphasizes its inherent challenges, including
Proceedings of the ndnd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
al.,

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
the non-contracted nature of the Bellman operator, the high dimensionality of the solution space, and the difficulties in relaxing underlying assumptions.
plexity characterization of robust RL with average reward.
Design of scalable reduction algorithms: To further vali- date the practical applicability of our framework, we adapt it to design scalable algorithms for robust average reward RL. After identifying key challenges in scaling up robust average reward RL, we show that our reduction framework circumvents these difficulties, enabling the design of effi- cient algorithms for large-scale problems. We evaluate our algorithms in large-scale MuJoCo environments, showeas- ing the capability of our framework to optimize long-term rewards under model uncertainty in complex systems. These results underscore the potential of our framework to effi- ciently solve large-scale, real-world problems.
To address these challenges, a natural approach is to draw on insights from the extensive studies of robust RL. for dis- counted rewards as an intermediate step. This idea has been validated in (Wang et al., 2023d; Grand-Clemen et al., 2023), which show that, under certain assumptions, the per- formance of discounted robust RL asymptotically converges to that of average reward as the discount factor approaches 1. While this convergence highlights the potential of using discounted robust RL to study the average reward setting, there remains a lack of results demonstrating its practical applicability. Key questions regarding its efficiency, effec- tiveness, and scalability remain unanswered, leaving gaps in understanding its implementation and real-world impact.
2. Preliminaries and Problem Formulation
Discounted reward MDPs. A discounted reward Marko- vian decision process (DMDP) (S, A, r,, 7) is specified by: a state space S, an action space A, a transition kernel P = (Po E A(S), a E A, s E S)', where P is the distri- bution of the next state over S upon taking action a in state (with P denoting the probability of transitioning to s'), reward function r S A + [0, 1]. and a discount factor Y E [0, 1). At each time step t, the agent at state s, takes an action a,, the environment then transitions to the next state St+1 according to P and produces a reward signal r: = ((tt,a)) to the agent.
In this paper, we explore this approach in greater depth and propose a reduction-based framework for concrete al- gorithm implementation. This framework facilitates the use of various robust discounted RL algorithms to address robust average reward RL problems. To assess the practical- ity of our framework, we evaluate its performance across two key dimensions: data efficiency and scalability. Our contributions are summarized as follows.
Reduction of robust average reward RL to discounted one: Under a standard assumption (Assumption 3.1), we propose a reduction- based framework that shows how ro- bust average reward optimization under model uncertainty can be equivalently addressed through robust discounted RL with a specific discount factor. While prior work has explored asymptotic convergence, no practical guidance has been offered on selecting reduction discount factor to guar- antee the optimality of the resulting policy. Our framework provides a concrete choice of the reduction discount factor, ensuring that the robust policy learned for the discounted reward also optimal under the average reward criterion. This universal framework deepens the understanding of the fundamental connections between average and discounted rewards while enabling robust average reward optimization.
A stationary policy т. S - A(A) is a distribution over A for any given state s. The agent follows the policy by taking action subject to the distribution (s)) The accumu- lative reward of a stationary policy starting from E S for DMDPs is measured by the discounted value function: VT,(() 2 E,, IEro S'r,/So = s].
Average reward MDPs. Unlike DMDPs, average reward MDPs (AMDPs) do not discount the rewards over time and instead measure the accumulative reward by considering the behavior of the underlying Markov process under the steady-state distribution. Specifically, the average reward (or the gain) of policy ι starting from 8 E ES is²
Design of data-efficient reduction algorithms: Building on our reduction framework, we present the first model- based algorithm for robust RL under average reward, ap- plicable to various uncertainty set models, with a thorough sample complexity analysis. We study the total number of samples required to learn an e-optimal robust policy for the average reward criterion under different uncertainty set structures. Specifically, we provide detailed analyses for total variation, x² divergence, and Dellbacck-eibble diver- gence uncertainty sets, demonstrating that our reduction algorithms achieve near-optimal sample complexity. These results highlight the practical potential of our framework in data-intensive settings, offering the first sample com-
R-1
gp (s)
2 lim E.. 11 10
Σ 1=0
rr = s]
(I)
It is also useful to define the following relative value func- tion or bias for an AMDP:
hp((s) A E E.
(re (oo-55]150 =
(2)
which is the cumulative difference over time between the immediate reward and the average reward.
(S)): the (IS) -)-dimensional probability simplex on S. "The limit may not exist, but under the assumption we made, such limit exists (Puterman, 1994).
2

---

A Reduction Framework for Distributionally Robust Reinforeement Learning under Average Reward
Robust MDPs. In robust MDPs, the transition kernel is not fixed but, instead, belongs to a designated uncertainty set denoted as P. Following an action, the environment undergoes a transition to the next state based on an arbitrary transition kernel P E P. We specifically concentrate on the (s, a) ---rettangular uncertainty set (Nilim & El Ghaoui, 2004; Iyengar, 2005), where p X s.a Pg. with Pa C A(S) defined independently over all state-action pairs.
3. Reduction Framework for Robust AMDPs
Our framework aims to reduce the robust average reward problem a robust discounted reward one, leveraging well- developed algorithms in this space. The convergence (6) and the existence of a robust Blackwell optimal policy (Wang et al., 2023d; Grand-Clément & Petrik, 2024) (a policy that optimizes the robust discounted reward for any 7 > Tow) further inspires us to reduce robust AMDP to robust DMDP with a sufficiently large discount factor. However, existing results foeus on asymptotic convergence, leaving the choice of discount factor for desired level of accu- racy unresolved. In this section, we study the relationship between the two robust MDPs and determine specific reduction discount factor.
Robust MDPs aim to optimize the worst-case performance over the uncertainty set. The robust discounted value func- tion of a policy ı is defined as the worst-case discounted value function over all possible transition kernels:
7, (s)
min
So =
(3)
P
We first adopt the following compactness and unichain as- sumption, which is commonly used in robust AMDPs.
where K (Po, PI...) E 0120 P. The discounted robust value functions are shown to be the unique solution to the robust discounted Bellman equation (lyengar, 2005):
Assumption 3.1. For any E S, a E A. the uncertainty set Pa is a compact subset of ASS). Moreover, any deter- ministic policy ı and any kernel P E P induce a unichain Markovian process?.
V(s)= Σ ((cls)(r(s.a) + (ops(()))
(4)
where pp: (V) A minper: PV is the support function of V the uncertainty set P
Due the Heine-Borel theorem (Dugac, 1989), the first part of Assumption 3.1 is satisfied if the uncertainty set is closed as it is always bounded. We remark that many standard uncertainty sets satisfy this assumption, e.g., those defined by e-contamination (Huber, 1965), finite interval (Tewari & Bartlett, 2007), total-variation (Rahimian et al., 2022) and KL-divergence (Hu & Hong, 2013).
In scenarios where the long-term performance under model uncertainty is concerned, we focus on the following worst- case average reward:
(p)))
min $20 P 70000
lim
ET
-
Σ 10 t=
(5)
The second part of Assumption 3.1 imposes additional struc- ture on the underlying MDP, an assumption commonly used in non-robust AMDP studies due to their inherent complex- ity (e.g., (Puterman, 1994; Wan et al., 2021: Zhang & Ross, 2021; Lan, 2020; Zhang et al., 2021 For robust AMDPs, the unichain assumption ensures the solvability of the aver- age reward robust Bellman equation (Wang et al., 2023d;e), which plays an essential role in our analysis. Under this assumption, the stationary distribution np always exists and does not depend on the initial state, and the average re- ward is identical for all starting states (Bertsckas, 2011), i.c., gb (51) = gb (s2), Vs1, 82 E S.
to which we refer as the robust average reward. The robust AMDP aims to find an optimal policy w.r.t. it, that is, x² & arg max 9 (s), for any s S.
In (Wang et al., 2023d), it is shown that the robust dis- counted value functions converge to the robust average re- ward w.r.t. the same MDP as the discount factor approaches 1:
lim (1 - V. 97.
Hence, the robust AMDP can be approximately solved through the corresponding robust DMDP with a sufficiently large discount factor, known as the reduction method. How- ever, selecting a discount factor to ensure near-optimality under the average reward remains unclear, leaving the adap- tation of the reduction method uncertain.
Inspired by non-robust AMDP studies (Wang et al., 2022: Zurek & Chen, 2023), we further extend the concept of the optimal bias span (Bartlett & Tewari, 2012) therein the robust setting.
Definition 3.2. For robust AMDP (S,A, its robust
In this paper, our goal is to develop a concrete reduction framework and design algorithms for optimizing the robust average reward, and to demonstrate the practical applicabil- ity of our framework.
A Markovian process is unichain if it contains exactly one recurrent class and possibly some transient states (Puterman, 1994; Bertsekas, 2011).
3

---

A Reduction Framework for Distributionally Robust Reinforeement Learning under Average Reward
optimal bias span is defined as*
ability to optimize long-term performance in data-intensive and large-scale practical scenarios.
H. - max Sp(pp)
PEP
4. Sample Complexity for Robust RL under Average Reward
where hg is the relative value function as in (2), and Sp(V) _ max, V(i) - min; V(i) is the Span semi-non semi-norm. Remark 3.3. We assume H is known, which can be viewed as a robust extension from the common assumption of knowl- edge of non-robust span in non-robust AMDPs studies (Wang et al., 2022: Zurek & Chen, 2023; Zhang & Xie, 2023; Wang et al., 2023a). Our framework and results re- main valid if H is replaced with any upper bound on H. such as the corresponding robust extensions of the mixing time or the diameter of a non-robust MDP (Wang et al., 2022). Additional discussion on estimating H is provided in Section 10. Specifically, we can derive an upper bound on H. for robust MDPs with some additional structures.
In this section, we study the data efficiency of our reduction framework for robust RL under average reward, to charac- terize the total number of samples required to identify an <-optimal policy и through our reduction framework.
We first present a general result on the sample complexity of robust AMDP reduction. Specifically, leveraging Theo- rem 3.4, the sample complexity of robust. AMDP algorithms aligns with that of robust DMDP algorithms with specific discount factor. This result is formally stated as follows:
Theorem 4.1. Consider any algorithm y optimizing the robust discounted reward. Denote the sample complexity y to identify an Ey e--ooiimal policy (wart. the discounted reward) by A, (x))) Then, we can identify an e-optimal policy for the robust average reward through re- duction and algorithm V, with a sample complexity of
Next, we present our reduction framework.
Theorem 3.4. (Reduction Frumework) For any set", Ty ==
1- 6. then any opttmmal policy ft,, for the robust DMDP
3. A.,,P,rr, r) )) is also an (cppoiil policy for the corre- sponding robust AMDP (S,A,P,r):
N (S,A.,,11- C H. n1).
(8)
96 - -9 Rr S
5e,
8 + H
E.
This result holds universally, regardless of the uncertainty set models or algorithms used for robust DMDPs. More im- portantly, it provides a basis for studying sample complexity and data requirements for optimizing the average reward under model uncertainty. In the following, we analyze the sample complexity of robust AMDPs under different uncer- tainty sets, offering a concrete understanding of their data efficiency and our framework.
While we defer the full proof to the appendix, the intu- ition behind the proof of our reduction framework relies on showing a bound on the convergence error of the robust discounted value function to the average reward. As shown in Lemma 11.1, under Assumption 3.1 with 7 E (0,1) and for any stationary π E 11, l0p - (1 V) S Sp((1 Vi,,) We then show that we can bound the <.-optiiall robust discounted value function induced by ,, as (1) (.P) S c. Similarly, we show we can bound Sp((1 - V..p) S e, before we combine these two re- sults with that of Lemma 11.1 to derive our bound in the Theorem 3.4.
Remark 4.2. Although Theorem 4. I holds for general un- certainty sets, existing sample complexity studies of robust focus the "ball-structured" uncertainty sets:
Dh = = D(allP?) S R),
(9)
The result in Theorem 3.4 shows that we provide a concrete choice for the reduction discount factor, ensuring that the ro- bust DMDP and robust AMDP share the same near-optimal policy. Our framework allows any algorithm designed for ro- bust DMDPs to be directly applied to solve robust AMDPs, with theoretical performance guarantees, effectively bypass- ing the challenges of robust AMDPs by transforming them into the well-studied DMDP domain.
where P. is the nominal kernel, R is the uncertainty radius indicating the uncertainty level, and D is some distribu- tion distance measure or divergence function. Hence, we similarly focus on uncertainty sets with this structure.
In our subsequent analysis, we focus on the generative model setting, where the agent can arbitrarily generate sam- ples following the nominal kernel P. This setting has been widely adopted for sample complexity analysis under both non-robust RL (Agarwal et al., 2020; Li et al., 2020; Zurek & Chen, 2023) and robust RL (Shi et al., 2023; Panaganti & Kalathil, 2022; Wang et al., 2023e). While robust RL has also been explored in other settings, such as offline (Shi & Chi, 2022; Blanchet et al., 2024; Wang et al., 2024b; Pana- ganti et al., 2022; Liu & Xu, 2024; Wang et al., 2024a) and
In the following sections, we investigate the applicability of our reduction framework from two key perspectives: data ef- ficiency and scalability. These demonstrate the framework's 's
"We prove in the Appendix that the value H exists and is finite.
'For robust DMDP, -optimall policy is some policy Iy such that max, V. Viax (s) S Ey, Vs E S.
4

---

A Reduction Framework for Distributionally Robust Reinforeement Learning under Average Reward
online (Lu al., 2024) scenarios, and sample complexity results for robust average reward under these settings can be directly derived from Theorem 4.1, we concentrate on the generative setting, allowing us to focus on the challenges of the robust average reward framework itself rather than the complexities of data collection under restricted settings.
robust AMDPs. We note that the minimax lower bound on the sample complexity for non-robust AMDPs is f2 (SA"), with H being the non-robust optimal span (Zurek & Chen, 2023; Wang et al., 2022; Jin & Sidford, 2021). Thus, our results are near-optimal under these uncertainty sets, align- ing with the lower bound in terms of S, A, E, with an addi- tional dependence on H. Notably, this is the first sample complexity analysis for robust RL under average reward, of- fering insights into data requirements for long-term reward optimization under model uncertainty. Furthermore, our framework demonstrates strong data efficiency, requiring nearly minimal samples to optimize the long-term reward, underscoring its potential in inta-intensive scenarios.
We develop a model-based reduction meta-algorithm for robust AMDPs. Specifically, after generating the data, we construct an estimate of the nominal kernel, and build empirical uncertainty set centered around it with the same D and R in (9). We then solve a DMDP with a specific dis- count factor to identify a near-optimal policy. Our algorithm is presented in Algorithm 1.
Remark 4.5. Theorem 4.4 is not a direct combination of Theorem 4.1 with existing sample complexity of robust DMDPs (Panaganti & Kalathil, 2022; Shi et al., 2023). Specifically, the existing sample complexity of a robust DMDP with TV set is Ô
Algorithm 1 Model-based algorithm for robust AMDPs
1: Input: N nominal samples {(s, a, s s ~ P.. under each (s, a) pair, uncertainty level R. robust bias span H. and accuracy level e
SA (1-))) aannd Ô
SA
((--))
2: Initialization: Q
for CS set. By setting E, = H. and 7 = t the result- ing average reward complexity is Ô (SA) and Ô (SAH2 respectively. Such higher complexity results due to the higher dependence on (1 (1-7) in the DMDP complex- ity, which becomes coorder in the average reward setting through our framework. To achieve lighter results, we need to further tighten the complexity result for robust DMDPs. Specifically, we showed that with reward perturbation technique (Li al., 2020; Wang al., 2022: Zurek & Chen, 2023) and more careful analysis involving the connection between robust DMDPs and AMDPs, we can reduce both sample complexities to Ô in the near-optimal complexity in Theorem 4.4.
3: Estimate transition model Po. 3,5'
Σ, 16..a
4: Construct empirical uncertainty set P centered at P:
P: = {g E (SS) D(alIPg) I R]
5: Set - 1- R. Ey + H
6: Obtain an optimal policy Ωं for the robust DMDP
(8, AS, r, ,,,7) with value iteration
7: Output: f..
Remark 4.3. In Line 6 of Algorithm 1, we need identify an o--oiimall policy for robust DMDPs, which can be done through robust value/policy iteration (Panaganti & Kalathil, 2022; Yang et al., 2021; Shi et al., 2023). For commonly used unceriainty sets, e.g., when D is lotal variation or x2 divergence, the algorithms can be implemented with polynomial computational complexity (Iyengar, 2005) and exponentially fast convergence rate.
SAR² (1-))²
which further result
We can further obtain sample complexity for optimizing robust AMDPs for other types of uncertainty sets, by com- bining Theorem 4. 1 with existing results for DMDPs. For instance, combining with (Panaganti & Kalathil, 2022), Al-
[ A log
SAN
Next, we present the sample complexity of Algorithm 1 for the robust AMDP in the following theorem.
gorithm I requires O
exp
samples
to identify an c-optimal policy under the Kullback-Leible (KL) divergence. The results in (Clavier et al., 2023) im-
Theorem 4.4. Consider an uncertainty set defined by to- tal variation (TV) or x2 divergence (CS). Let C be some universal constant. If the total number of sumples satisfies
ply a sample complexity of O SAR log( S4M for the
lp -noommed uncertainty set. Our framework thus provides the first concrete sample complexity characterization for ro- bust AMDPs, establishing a foundation for studying robust long-term performance optimization.
NSA> CSAmin( R
H 1+ R= t/ log
(SAN
(TV)
2
NSAZ CSAH Ro log
SAN
(CS)
Remark 4.6. As demonstrated in prior studies on non- robust AMDPs (Zurek & Chen, 2023; Wang et al., 2022; 2023b), tightening the complexity bounds for non-robust DMDPs leads to optimal AMDP complexity in the corre- sponding reduction framework. We therefore attribute our sub-optimal sample complexity to the loose bounds of robust DMDPs rather than limitations in our reduction framework.
22
then, with probability at least 46, Rny is c-optimal under the robust average reward.
The result shows that Algorithm 1 requires most Ö SAH² samples to identify an e-optimal policy for both
5

---

A Reduction Framework for Distributionally Robust Reinforeement Learning under Average Reward
Refining the complexity analysis of robust DMDPs align with the optimal bounds for robust AMDPs is an important direction for future research.
i.e., E A $0, vO. Under this assumption, there exists unique 0 that minimizes the approximation loss. We note that the robust average reward also encounters this issue, but the higher dimensionality of its solution space (compared to the one-dimensional solution space in the non-robust setting) (Wang et al., 2024c) may result in more restrictive assumptions, making even more challenging to directly apply linear FA to the robust average reward setting.
5. Scalable Robust RL for Average Reward
In this section, we explore scalable approaches for optimiz- ing the average reward under model uncertainty, aiming to facilitate long-term performance optimization in practical, large-scale problems. Specifically, we show that our frame- work overcomes the major challenges in solving large scale robust AMDPs, and further enables us to design scalable algorithms for the robust average reward, greatly enhancing the scalability and applicability of our methods.
Another challenge arises from unstable convergence under the average reward. Even in the tabular setting, algorithm design and convergence analysis remain limited due to the instability caused by the Span semi-norm multi-step contrac- tion of the Bellman operator (Puterman, 1994), compared to the norm contraction in the discounted setting. Existing studies address this issue either by introducing additional offset functions to stabilize convergence (Wan et al., 2021; Wan & Sutton, 2022; Puterman, 1994; Bertsekas, 2011) or by only ensuring convergence to solution set (Zhang et al., 2021b). As demonstrated in (Wang et al., 2023d;e), simi- lar challenges persist in the robust average reward setting, and addressing them is expected to involve even greater complexity.
When the problem scales are large, function approxima- tion (FA) techniques have been extensively studied. FA methods aim to approximate the value functions by some low-dimensional function class, F = {fo(s) 0 E θ S RR, ,, < 5}. to find some 0* E θ such that Vss) R fo- (s), Vs. Two commonly studied function classes for FA are the linear function class and neural networks (Cai et al., 2019; Bhatnagar et al., 2009; Wai et al., 2019). We focus on linear FA illustrate the scalability of our framework, but our method can be directly extended to neural networks or other function classes.
Noting these two issues, it can be much more challenging to directly apply FA techniques to the robust average re- ward. However, our reduction framework simplifies this by transforming the complex robust average reward prob- lem into the more manageable discounted reward setting. This bypasses the aforementioned difficulties and facilitates the design of scalable algorithms. As an immediate appli- cation, we extend our reduction framework to the robust natural actor-critic (NAC) algorithm with linear FA (Zhou et al., 2024), resulting in robust NAC algorithm for robust AMDPs, detailed in Algorithm 2. Algorithm 2 consists of two key steps: (i) a robust TD step to update the weight vector for value approximation, and (ii) an actor step to update the policy", neither of which suffers from the issues mentioned above.
Linear FA is based on a set of feature functions {Ø: S + J. In robust DMDPs, the robust value function is approximated using linear function: (s)) A V (s), where 0 E d is some weight vector. Despite extensive studies on linear FA in robust DMDPs (Tamar et al., 2014; Xu & Mannor, 2010; Wang & Zou, 2021; Zhou et al., 2024; Roy et al., 2017: Badrinath & Kalathil, 2021), remains largely understudied for (robust) AMDPs. In the non-robust average reward policy evaluation problem, we aim to approximate the bias hü to estimate 9p. by approxi- mating the solution to the non-robust Bellman equation
(ss)T x
h(*)= = Σ (alls)(((s,a) - g P.)).
(10)
Note that the feature vectors in Algorithm 2 are predefined, e.g., by tile coding (Sutton, 1995), Fourier Basis (Konidaris et al., 201 1), or randomly generated (Ghavamzadeh et al., 2010), by the learner prior to training.
However, two major challenges hinder the study of linear FA for average reward MDPs. The first is that (10) admits non- unique solutions (Puterman, 1994; Wan et al., 2021: Wan & Sutton, 2022). Specifically, besides the average reward and relative value function pair (g8, hT),, ), any pair" (95, hi ce) with any E IR is also solution to (10). This implies that the weight vector may not be unique, leading to a divergent algorithm. A common approach to address this issue is to impose additional assumptions on the feature functions (Zhang et al., 2021a; la; Tsitsiklis & Van Roy, 1999; Konda & Tsitsiklis. 1999 Yu & Bertsekas, 2009), ensuring that the all-one vector does not lie within the span of {((s))
We further characterize the convergence of Algorithm 2 (see Theorem 14.2 for the formal theorem statement).
Theorem 5.1. (Informal) Under some additional standard assumptions, set T = 5 2 x in Algorithm 2, then ner an O + -cppomalall policy, where eg is the critic error due to the representation power of the linear function class. The total sample complexity is O(H²
Our results demonstrate that, without requiring any addi-
cc = (1, 1, 1,.., 1) is the all-one vector.
The detailed algorithms are provided Section 14.
6

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Algorithm 2 Reduction Robust Natural Actor-Critic
00333
Input: T, H. base functions {ø}
2: Initialization: On for value function approximation and
Fost0
We for policy parametrization
0.5
3: y 1-11 H
tou Full boe Ricui mare
mall rellisigg labuc (eo?
4: for fort=a 0,
Raducton ledzar for 0-0
034
Raductor 0000
5: Robust critic updates 6g with Algorithm 3
04
36
Co
02
06 06
6: Robust natural actor updates 1241 with Algorithm
Figure 1. Effectiveness under the Garnet problem.
7: end for
8: Output: WT
Next, we evaluate the data efficiency of our model- -based framework under the same settings by optimizing empiri- cal robust DMDPs with a reduction factor corresponding to 0.01 across different dataset sizes. The results, presented in Figure 2, show that our model-based algo- rithm converges to the optimal policy as dataset size N increases and achieves near-optimal performance with a limited amount of data. These findings highlight the data efficiency of our framework, demonstrating its ability to optimize long-term rewards with fewer samples. Since the computational cost for finding the worst performance (i.e., robust policy evaluation) in TV and CS uncertainty sets are O ((Slog(S) log(S)) (Iyengar, 2005) under the tabular setting, their estimation can be tractable.
tional assumptions on the base functions, our framework enables the optimization of robust average reward with func- tion approximation with stable convergent algorithm, un- derscoring its scalability, This represents the first solution for large-scale robust long-term reward optimization, offer- ing both convergence and performance guarantees.
Remark 5.2. In addition to function approximation, design- ing model-free algorithms for robust AMDPs can also im- prove scalability. Our framework also facilitates model-free algorithm design, which we discuss in detail in Section 15.
6. Numerical Experiments
3.500
We first assess the effectiveness and efficiency of our frame- work in tabular settings, aiming to verify that with the reduc- tion discount factor in Theorem 3.4, optimizing the robust DMDP approximately optimizes the robust AMDP.
0.40
8,530
5.400
0.17
Opta sil Sukal Ayerage Nomen
Ganin Rould Average Ronard
Our experiments are conducted on the Garnet problem (Archibald et al., 1995), where the nominal transition kemnel and reward functions sian distributions. We consider Garnet problem with 20 states and 8 actions, constructing uncertainty sets using To- tal Variation (TV) and Chi-Square (CS) divergences, both with radius R = 0.2. Additional results for other problems are provided in Section 9.
304
451
1rea
19t rare
280
2009 1209 3401
Figure 2. Efficiency under the Garnet problem.
randomly generated from Gaus-
We then demonstrate the scalability of our framework in large-scale problems by showing that robust average reward optimization can be equivalently formulated as a robust DMDP with a sufficiently large reduction factor. Specifi- cally, we implement Algorithm 2 in the MuJoCo simulation environments (Todorov et al., 2012) for robust DMDPs with varying discount factors and evaluate the average reward per- formance under model uncertainty. Implementation details are provided in Section 14.
To verify the effectiveness of our framework, we optimize robust DMDPs with different discount factors and plot the robust average reward 97" of the learned policy nry using Algorithm from (Wang et al., 2023d). As a baseline, we plot the optimal robust average reward gi., obtained via Algorithm 2 from (Wang et al., 2023d). Additionally, we estimate H using Algorithm 2 from (Wang et al., 2023e) and compute the corresponding reduction factor for different accuracy levels e, as described in Theorem 3.4. The results, shown in Figure 1, indicate that the robust average reward can be approximately optimized through a robust DMDP with a sufficiently large discount factor. Furthermore, the robust average reward corresponding to each c falls within the prescribed accuracy level, confirming the effectiveness of our framework and the validity of the reduction factor.
Our experiments are conducted in two continuous large- scale environments: Walker2d-v3 and Hopper-v3. We first train our algorithms the nominal environments to learn the optimal policy for the given robust discounted reward. To estimate the robust average reward, we deploy the learned policies in perturbed environments, where at each evaluation epoch, we randomly sample parameters within the pertur- bation interval and apply them to each joint. The average reward is then computed over 30 independently perturbed environments.

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Figure 3. Scalability under Walker2d-v3.
Figure 5. Neural network approximation under Walker2d-v3.
No. Sarhbbuc Polictton Malhed
100
Figure 4. Scalability under Hopper-v3.
Figure 6. Neural network approximation under Hopper-v3.
As noted in Remark 3.3, we assume have the knowledge of H. however, we would like to note that in practice this is rarely the case. In lieu of a pre-obtained H. we can equiva- lently use any upper-bound on H and see that our results still hold. In our experimentation on Walker2d-v3 and Hopper- v3, we opted to estimate the diameter as it could be easily obtained. For each of the independently perturbed environ- ments, we sampled 1,000 randomly obtained trajectories and recorded how many steps it took the given trajectory to terminate. Based on this, we recorded the highest value for the number of steps across each of the 30 environments before averaging these values together to obtain an estimate for the diameter. The results, presented in Figures 3 and 4, show that as the discount factor increases, robust DMDP optimization aligns more closely with robust average ward optimization. In both environments, performance sta- bilizes when is large, further validating the effectiveness of our framework. Moreover, our results demonstrate that, when combined with function approximation techniques, our framework effectively scales to large-scale problems.
on bounding the Blackwell discount factor. The Blackwell discount factor, denoted as Tow is defined such that the optimal robust policy for the DMDP with discount factor "ow is also optimal to any robust DMDP with discount factor 7 2 Tbu- This implies that any optimal policy for the robust Now -MDDP also optimizes the robust AMDP.
With this notation, a robust AMDP can similarly be re- duced to a robust DMDP with "bur- To enable this reduction, & Petrik, 2024) derives an upper bound on Thw While this reduction-based framework shares some similarity with our approach, our method offers several ad- vantages compared to their approach.
First, the results in (Grand-Clément & Petrik, 2024) are only applied to robust MDPs that meet two conditions: (1) the uncertainty sets are defined using 2 or 1 norms:; and (2) the nominal kernels are rational numbers, i.e., P na...
m,,a"
for some Ta,a. My,a E N. In contrast, we only require the uncertainty set to be compact and the Markov chain induced by each kernel in it to be a unichaín. The restrictions in their work due the reliance on the separation bounds of algebraic numbers for rational polynomial in their proofs. In contrast, we developed more detailed structural char- acterization of robust AMDPs, allowing us to obtain more general results. More importantly, the resulting sample complexity from (Grand-Clément & Petrik, 2024) less favorable than ours. The robust Blackwell discount factor is bounded by The I 1 53m ST, where m is the minimal denominator of the nominal kemne. Using this result in reduction framework leads to an exponentially large sample complexity, making the results impractical. We note that the Blackwell optimality can be overly stringent for merely solving a robust AMDP, and hence it results in significantly worse sample complexity compared to ours.
We emphasize that our reduction framework independent of any specific discounted algorithm used, thus it is not limited to only linear approximation. To verify this claim, we present additional experimentation using neural network approximation in Figures and 6. As the results show, our reduction framework remains valid even with neural network approximation, and it more robust than the non- robust reduction method. We present additional results for this in Section 14.
7. Related Work
7.1. Comparison with Prior Art
In this section, we compare our results with the most related work (Grand-Clémen & Petrik, 2024), which also explores
reduction of robust AMDPs to DMDPs, However, it focuses
8

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
7.2. Other Related Work
is equivalent achieving a near-optimal policy under the discounted reward with specific reduction discount factor, based on which we constructed reduction- baaoo frame- work that solves robust RL with average reward effectively. Our framework is adaptable to any method or oracle and versatile across uncertainty sets. It offers two key benefits: data efficiency and scalability, as illustrated by our design of both tabular and function approximation algorithms, along with their sample complexity analysis and experimental per- formance. Our results represent the first concrete solutions for robust RL in the average reward setting under the mild assumption (unichain), advancing the understanding of opti- mizing long-term RL performance under model uncertainty.
Robust AMDPs. Robust AMDPs studies are quite limited. Model-based robust AMDPs were first studied in (Tewari & Bartlett, 2007) for specific finite-interva uncertainty set, which is further extended to more general models in recent works including (Wang et al., 2023d; Grand-Clement et al., 2023). A game-based method is also proposed in (Chat- terjee et al., 2023). These works reveal the fundamental structure of robust AMDPs, illustrating their connections to robust DMDPs. However, all of them model-based with asymptotic convergence, whereas we developed sample complexity analysis.
Robust DMDPs. Robust DMDPs were studied in (Iyen- gar, 2005; Nilim & EI Ghaoui, 2004; Bagnell et al., 2001; Wiesemann et al., 2013; Lim et al., 2013), where the un- certainty set assumed to be fully known. This inspired model-based methods for robust MDPs, where the learner first estimates a model, then solves the estimated model using robust dynamic programming (Zhang et al., 202 Ic; Panaganti & Kalathil, 2022: Yang et al., 2021; Shi et al., 2023). The studies were also extended to the model-free setting for more practical settings (Roy et al., 2017; Badri- nath & Kalathil, 2021: Wang Zou, 2021; 2022; Liu al., 2022b; Zhou al., 2021: Goyal & Grand- Clemment 2018; Kaufman & Schaefer, 2013; Ho et al., 2018; 2021; Wang et al., 2024c). Our work shows that the sample complex- ity of solving robust AMDPs can be transformed to that of solving DMDPs, enabling us to leverage the extensive prior work on the discounted setting.
A Acknowledgments
This work was supported by DARPA under Agreement No. HR0011 1 1-24-9-0427 and NSF under Award CCF-2106339, We would also like to show our appreciation to the reviewers of this work for their impactful insight during the revision of this paper.
Impact Statement
The work contained in this paper is to advance the field of robust reinforcement learning. As there are many different potential impacts to different fields and that we provide a theory-based general framework, we do not feel that there is a need to delve into specific potential impacts here.
Early contributions non-robust AMDPs involve fundamental characterizations of the prob- lem and the development of model-based methods (Puter- man, 1994; Bertsekas, 2011). Recently, model-free methods in the tabular setting, e.g.. (Abounadi et al., 2001; Wan et al., 2021; Wan & Sutton, 2022), have been developed and demonstrated convergence to the optimal average re- ward. The sample complexity of non-robust AMDPs has been a recent focus (Wang et al., 2022; Zhang & Xie, 2023). Among them, similar reduction based methods are consid- ered in, e.g. (Wang et al., 2022; 2023b; Zurek & Chen, 2023), achieving the optimal complexity. Extending such frameworks to robust settings is notably challenging, due to the inherent complexity of the robust average reward setting, stemming from the non- -ineeiieyy of the Bellman operator and a more complicated high-dimensional solution space for the robust Bellman equation (Wang et al., 2023e).
Non-robust AMDPs.
References
Abounadi, J., Bertsekas, D., and Borkar, V. S. Learning algorithms for Markov decision processes with average cost. SIAM Journal on Control and Optimization, 40(3): 681-698,1 2001.
Agarwal, A., Kakade, S., and Yang. L. F. Model-based rein- forcement learning with a generative model is minimax optimal. In Conference on Learning Theory, pp. 67-83, PMLR, 2020.
Archibald, T., McKinnon, K., and Thomas, L. On the generation of Markov decision processes. Journal of the Operational Research Society, 46(3):354-3611 1995.
Badrinath, K. P. and Kalathil, D. Robust reinforeement learning using least squares policy iteration with provable performance guarantees. In Proc. International Confer- ence on Machine Learning (ICML), pp. 511-520. PMLR, 2021.
8. Conclusion
In this work, we studied the fundamental connection be- tween robust AMDPs and DMDPs. We reveal that ob- taining an optimal policy for the robust average reward
Bagnell, J. A., Ng, A. Y., and Schneider, J. G. Solving uncertain Markov decision processes. Carnegie Mellon University, Technical Report, 2001.
9

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Bartlett, P. L.. and Tewari, A. Regal: regularization based algorithm for reinforcement learning in weakly commu- nicating mdps. arXiv preprint
Grand-Clément, and Petrik, M. Reducing blackwell and average optimality to discounted MDPs via the black- well discount factor. Advances in Neural Information Processing Systems, 36, 2024.
2012.
Bertsekas, D. P. Dynamic Programming and Optimal Con- trol 3rd edition, volume II. Belmont, MA: Athena Scien- rific, 2011.
Grand-Clement J., Petrik, M., and Vieille, N. Beyond discounted returns: Robust markov decision processes with average and blackwell optimality. arXiv preprint arXi::2312.03614 2023.
Bhatnagar, S., Precup, D., Silver, D., Sutton, R. S., Maei, H., and Szepesvári, C. Convergent lemporal-differnnce difference learning with arbitrary smooth function approximation. In Proc. Advances in Neural Information Processing Sys- tems (NIPS), volume 22, pp. 1204-1212, 2009.
Ho, C. P., Petrik, M., and Wiesemann, W. Fast Bellman updates for robust MDPs. In Proc. International Con- ference on Machine Learning (ICML), pp- 1979-1988. PMLR, 2018.
Blanchet, J., Lu, M., Zhang, T., and Zhong, H. Double pessimism is provably efficient for distributionally robust offline reinforcement learning: Generic algorithm and robust partial coverage. Advances in Neural Information Processing Systems, 36, 2024.
Ho, C. P., Petrik, M., and Wiesemann, W. Partial policy iter- ation for L1-robust Markov decision processes. Journal of Machine Learning Research, 22(275):1-46, 2021.
Hu, Z. and Hong, L. J. Kullback-Leibler divergence con- strained distributionally robust optimization. Available at Optimization Online, pp. 1695-1724, 2013.
Blanchet, J. H. and Glynn, P. W. Unbiased Monte Carlo for optimization and functions of expectations via multi-level randomization. In 2015 Winter Simulation Conference (WSC), pp.
IEEE, 2015.
Huber, P. J. A robust version of the probability ratio test. Ann. Math. Statist., 36:1753-1758, 1965.
Blanchet, J. H., Glynn, P. W., and Pei, Y. Unbiased mul- tilevel Monte Carlo: Stochastic optmizaaiin, steady- state simulation, quantiles, and other applications. arXiv preprint (9t1::9994099922. 2019.
Iyengar, G. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-280, 2005.
Jin, Y. and Sidford, A. Towards tight bounds on the sam- ple complexity of average-reward mdps. In Interna- tional Conference on Machine Learning, pp. 5055-5064. PMLR, 2021.
Cai, Q. Yang, 7., Lee, J. D., and Wang, Z. Neural temporal-difference learning converges to global optima. In Proc. Advances in Neural Information Processing Sys- tems (NeurIPS), pp. 11312-11322, 2019.
Kaufman, D. L.. and Schaefer, A. Robust modified policy iteration. INFORMS Journal on Computing, 25(3):396- 410, 2013.
Chatterjee, K., Goharshady, K., Karrabi, M., Novotný, P., and Žikelić, u. Solving long-run average reward robust mdps via stochastic games. arXiv preprint 2XXi:23312.13912 2023.
Kober, J., Bagnell, A., and Peters, J. Reinforcement learning in robotics: A survey. The International Journal of Roboties Research, 32((1):1238 111112221274 2013.
Clavier, P., Pennec, E. L., and Geist, M. Towards minimax optimality of model-based robust reinforcement learning. arXiv preprint
2023.
Konda, V. and Tsitsiklis, J. Actor-critic algorithms. Ad- vances in neural information processing systems, 12, 1999.
Dugac, P. Sur la correspondance de borel et le théorème de dirichlet-heine-vee wererrie-wweeestrsss--oooee hhreeessttssssooresssceeeeeeeeee Archives internationales d' d'histoire des sciences, 39(122); 69-110, 1989.
Konidaris, G., Osentoski, S., and Thomas, P. Value function approximation in reinforcement learning using the fourier basis. Proceedings of the AAAI conference on artificial intelligence, volume 25, pp. 380-385, 2011.
Ghavamzadeh, M., Lazaric, A., Maillard, O., and Munos, R. LSTD with random projections. In Proc. Advances in Neural Information Processing Systems (NIPS), 2010.
Lan, G. First-order and Stochastic Optimization Methods for Machine Learning. Springer Nature, 2020.
Goyal, V. and Grand-Clement, J. Robust Markov deci- sion process: Beyond rectangularity. arXiv preprint arXiv: 2018.
Levin, D. A. and Peres, Markov chains and mixing times, volume 107. American Mathematical Soc., 2017.
10

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Li, G., Wei, Y., Chi, Y., Gu, Y., and Chen, Y. Breaking the sample size barrier in model-based reinforcement learning with a generative model. Advances in neural information processing systems, 15:12861-12877 2020.
Roy, A., Xu, H., and Pokutta, S. Reinforcement learning under model mismatch. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 3046-3055, 2017.
Lim, S. H., Xu, H., and Mannor, S. Reinforcement learning in robust Markov decision processes. In Proc. Advances in Neural Information Processing Systems (NIPS), pp. 701-709,2011
Shi, L. and Chi, Y. Distributiinnally robust model- badel-basedd offline reinforcement learning with near-optimal sample complexity. arXiv preprint 220X::220..05772 2022.
Shi, L., Li, G.. Wei, Y., Chen, Y., Geist, M., and Chi, Y. The curious price of distributional robustness in reinforce- ment learning with a generative model. arXiv preprint arXiv:2305. 16589, 2023.
Liu, R.-Z., Pang, Z.-J,, Meng, Z.-Y., Wang, W., Yu, Y., and Lu, T. On efficient reinforcement learning for full-length game of starcraft ii. Journal of Artificial Intelligence Research, 75:213-260, 2022a.
Liu, Z. and Xu, P. Minimax optimal and computationally efficient algorithms for distributionally robust offline re- inforcement learning, arXiv preprint (rXiv:2403.09621 2024.
Silver, D., Huang, A., Maddison, J. Guez, A., Sifre, L., Van Den Driessche, G., Schrittwieser, J., Antonoglou, I., Panneershelvame V., Lanctot, M., et al. Mastering the game of go with deep neural networks and tree search. nature, 529(7587):444448, 2016.
Liu, Z., Bai, Q. Blanchet, J., Dong, P., Xu, W., Zhou, Z., and Zhou, Distributionally robust Q-learning. In Proc. International Conference on Machine Learning (ICML). pp. 13623-13643, PMLR, 2022b.
Sobel, M. The variance of discounted markov decision processes. Journal of Applied Probability, (9(4):794-802 1982.
Lu, M., Zhong, H., Zhang, T., and Blanchet, J. Distribu- tionally robust reinforcement learning with interactive data collection: Fundamental hardness and optimall algorithm. arXiv prepriní arXiv:2404.03578, 2024.
Sutton, R. S. Generalization in reinforcement learning: Sue- cessful examples using sparse coarse coding. Advances in neural information processing systems, 8, 1995.
Tamar, A., Mannor, S., and Xu, H. Scaling up robust MDPs using function approximation. In Proc. International Conference on Machine Learning (ICML), pp. 181-189. PMLR, 2014.
Müller, A. Integral probability metrics and their generating classes of functions. Advances in applied probability, 29 (2):429 443, 1997.
Nilim, A. and El Ghaoui, L. Robustness in Markov decision problems with uncertain transition matrices. In Proc. Ad- vances in Neural Information Processing Systems (NIPS), pp. 839-844-- 846,2262 2004.
Tewari, A. and Bartlett, P. L. Bounded parameter Markov decision processes with average reward criterion. In Inter- national Conference on Computational Learning Theory, pp. 263-277, Springer, 2007.
Panaganti, K. and Kalathil, D. Sample complexity of robust reinforcement learning with a generative model. arXiv preprint ar 12.00 2021.
Todorov, E., Erez, T., and Tassa, Y. Mujoco: physics engine for model-based control. In 2012 IEEE/RSJ inter- national conference intelligent robots and systems, pp. 5026-5033. IEEE, 2012.
Panaganti, K. and Kalathil, D) Sample complexity of ro- bust reinforcement learning with generative model. In International Conference on Artificial Intelligence and Statistics, pp. 9582-9602. PMLR, 2022.
Tsitsiklis, J. N. and Van Roy, B. Average cost temporal- difference learning. Automatica, 35(11):199-1180 1999.
Panaganti, K., Xu, Z., Kalathil, D., and Ghavamzadeh, M. Robust reinforcement learning using offline data. arXiv preprint arXiv:2208.05122 2022.
Vershynin, R. digh--dimesiooal probability: An introduc- tion with applications in data science, volume 47. Cam- bridge university press, 2018
Puterman, M. L. Markov decision processes: Discrete
stochastic dynamic programming, 1994.
Wai, H.-T., Hong, M., Yang, Z., Wang, Z., and Tang, K. Variance reduced policy evaluation with smooth func- tion approximation. In Proc. Advances in Neural Infor- mation Processing Systems (NeurIPS), volume 32, pp. 5784-5795, 2019.
Rahimian, H., Bayraksan, G., and De-Mello, T. H. Effective scenarios in multistage distributionally robust optimiza- tion with a focus on total variation distance. SIAM Journal on Optimization, 32(3):1695 119811779-7 2022.

---

A Reduction Framework for Distributionally Robust Reinforeement Learning under Average Reward
Wan, Y. and Sutton, R. S. On convergence of average-reward off-policy control algorithms in weakly-communicating MDPs. arXiv preprint 2rXiv:2209.15222 2022.
Wang, Y., Zou, S., and Wang, Y. Model-free robust rein- forcement learning with sample complexity analysis. In The 40th Conference Uncertainty in Artificial Intelli- gence, 2024c.
Wan, Y., Naik, A., and Sutton, R. S. Learning and planning in average-reward Markov decision processes. In Proc. International Conference on Machine Learning (ICML),
Wei, H., Chen, J., Ji, X., Qin, H., Deng, M., Li, S., Wang. L.., Zhang, W., Yu, Y., Line, I.., et al. Honor of kings arena: environment for generalization in competitive reinforcement learning. Advances in Neural Information Processing Systems, 35:1 1881-18811999 2022.
pp. 10653-10662. PMLR, 2021.
Wang, G. and Wang. T. Unbiased multilevel Monte Carlo methods for intractable distributions: Mlme meets memc. arXiv preprint 2080000 2022.
Wiesemann, W., Kuhn, D., and Rustem, B. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153- 1833,8, 2013.
Wang. H., Shi, L., and Chi, Y. Sample complexity of offline distributionally robust linear markov decision processes. arXiv preprint arXiv:2403. /2946, 2024a.
Xu, H. and Mannor, S. Distributionally robust Markov deci- sion processes. In Proc. Advances in Neural Information Processing Systems (NIPS), pp.
Wang, J., Wang, M., and Yang, L. F. Near sample-optimal ialuucioonbbsedd policy learning for average reward mdp. arXiv preprint arXiv:22/2.0000
2010.
2022.
Yang, W., Zhang, L., and Zhang. Z. Towards theoreti- cal understandings of robust Markov decision processes: Sample complexity and asymptotics. arXiv preprint 205.::2005.03863 2021.
Wang, S., Blanchet, J., and Glynn, P. Optimal sample com- plexity for average reward Markov decision processes. arXiv preprint arXiv:2310.088 088833,, 2023a.
Yu, H. and Bertsekas, D. P. Convergence results for some temporal difference methods based on least squares. IEEE Transactions on Automatic Control, 54(7):1515-1531, 2009.
Wang, S., Blanchet, J., and Glynn, P. Optimal sample complexity of reinforcement learning for mixing dis- counted Markov decision processes. arXiv preprint Sttv:2302.07477, 2023b.
Zha, D., Xie, J., Ma, W., Zhang, S., Lian, X., Hu, X., and Liu, J. Douzero: Mastering doudizhu with self-play deep reinforcement learning. In international conference on machine learning, pp. 1 12333- 12344. PMLR, 2021.
Wang, S., Si, N., Blanchet, J., and Zhou, Z. A finite sample complexity bound for distributionally robust q-learning. In International Conference on Artificial Intelligence and Statistics, pp. 3370-3398. PMLR, 2023c.
Zhang, H., Chen, H., Xiao, C., Li, B., Liu, M., Boning, D.,, and Hsich, C.-J. Robust deep reinforcement learning against adversarial perturbations on state observations. Advances in Neural Information Processing Systems, 33: 2020.
Wang. Y. and Zou, S. Online robust reinforcement learning with model uncertainty. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2021.
Wang, Y. and Zou, S. Policy gradient method for robust re- inforcement learning. In Proc. International Conference Machine Learning (ICML), volume 162, pp. 23484- 23526. PMLR, 2022.
Zhang, S., Wan, Y., Sutton, R. S., and Whiteson, S. Average- reward off-policy policy evaluation with function approx- imation. In Proc. International Conference on Machine Learning (ICMI.), pp. 12578-12588. PMLR, 2021a.
Wang, Y., Velasquez, A., Atia, G., Trater-Bennette A., and Zou. S. Robust average-reward Markov decision pro- cesses. In Proc. Conference on Artificial Intelligence (AAAI), 2023d.
Zhang, S., Zhang, Z., and Maguluri, S. T. Finite sample analysis of average-reward TD learning and Q-learning. In Proc. Advances in Neural Information Processing Sys- lems (NeurIPS), volume 34, pp. 1230-1242, 2021b.
Wang, Y., Velasquez, A., Atia, G. K., Prater-Bennette A., and Zou, S. Model-free robust average-reward reinforce- ment learning. In International Conference on Machine Learning, pp. 36431-36461 PMLR, 2023e.
Zhang, X., Chen, Y., Zhu, X., and Sun, W. Robust policy gradient against strong data corruption. arXiv preprint a0X0v.2102.05800, 2021c
Wang, Y., Sun, Z., and Zou, S. A unified principle of pessimism for offline reinforcement learning under model mismatch. In The eighty- Annual Conference on Neural Information Processing Systems, 2024b.
Zhang, Y. and Ross, K. W. On-policy deep reinforcement learning for the average- criterion. In Proc. Inter- national Conference on Machine Learning (ICML), pp. 12535-12545. PMLR, 2021.
12

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Zhang, Z. and Xie, Q. Sharper model-free reinforcement learning for average-reward Markov decision processes. In The Thirty Sixth Annual Conference on Learning The- ory, Pp. 5476-5477, PMLR, 2023.
Zhou, R., Liu, T., Cheng, M., Kalathil, D., Kumar, P., and Tian, C. Natural actor-critic for robust reinforcement learning with function approximation. Advances in neural information processing systems, 36, 2024.
Zhou, Z., Bai, Q. Zhou, Z. Qiu, L., Blanchet, J., and Glynn, Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pp. 3331-3339. PMLR, 2021.
Zurek, M. and Chen, Y. Span-based optimal sample complexity for average reward mdps. arXiv preprint arXiv:2311.13469 2023.
13

---

Appendix
9. Additional Experiments for Tabular Settings
Building upon the results in 6, we aim to verify our theoretical findings by presenting concrete experimental validation using the true transition kernel as well as the empirical kernel in figures and respectively. In each setting, both the nominal generated via normal distribution for 20 states and 8 actions. Given this,
transition kernel and the reward function then construct the uncertainty set with either TV or CS divergence, both with a radius I 0.2. For each fixed value of we estimate nT for the associated robust DMDP using robust value iteration (lyengar, 2005). We then use Algorithm in (Wang et al., 2023d) on this policy to obtain its robust average reward 9p" Additionally, we plot the optimal robust average reward using Algorithm from (Wang et al., 2023d). By iterating through discount factors and obtaining the robust average reward, our results show that as 7 - 1, the estimated policies obtained from the corresponding robust DMDPs yield an increasingly higher robust average reward, thus we converge to the optimal policy for the robust AMDP. To further solidify this point, given arbitrarily chosen values for e, we can estimate the robust optimal bias span H using the work of (Wang et al., 2023e). With these values, know the optimal discount factor necessary to obtain the optimal policy of the robust AMDP.
1.0000
c-000001
20000
0,9995
0.9995
Robost Average Reward
Roaust Average Roword
0.9990
k=0.001
0.9990
6-0 6-0.001
00000
0.9985
Optimal Average Roward
Estlmmted Average Reward
0.9985
0,9980
0,9 0,9980
0.9975
0.9675
0.9970
c=0.003
0.9970
0=0.003
Extimated Average Reward
Optimal Ave ago Ruward
0.800
0,9050
299900
0.5
0,9000
9,99996
Discount Factor
Figure 7. Convergence of true kernel for TV (left) and x²
2 divergeee (right).
1.0025
1.0000
Avtrogia Roward
Avreaage Reward
0.000
c-0.001
0.9975
0:083
0.9950
0-00003
0.996
0.9925
0.9900
Estimated Average Reward
0.394
Estimated Average Reward
Optimal Average Reward
0.9875
Optim Average Reward
0.25
0.30
0.35
0.50
0.85
0.80
0.35
0,000
0.9000
9oond
0.95
0.99
8998
0. 99pos
Discount Facter Figure 8. Convergence of empirical kemel for TV (left) and -d-veerreence (right).
Discount Factor
We also wish to compare other methods to our reduction framework. Due to the novelty of our work, opted to compare our method to two baselines for robust AMDPSs robust value iteration (RVT) (Wang et al., 2023d), and robust relative value iteration (RRVI) (Wang et al., 2023e), under the tabular Garnet problem due to the baseline method's asymptotic convergence guarantees. We set the reduction factor to be 0.99 in our framework (corresponds to c = 0.001. As we show in Figure 9, our method obtains a better policy within the same number of steps, thus achieving sfate-of-the-an performance in robust average reward optimization.
14

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Reduction
Robusz Average Rleeardd
200
80
70-
60
20
40
62
80
100
Stop
Figure Comparison with AMDP baselines
10. Discussion on H For general uncertainty sets, we can obtain an upper bound of H with an additional assumption.
Lemma 10.1. Assume there exists some positive integer >> 0 and some positive value p. such that
(P*),,z 2 p. vP P, (s, E
(11)
Then,
1 1 Sp(hp) <
(12)
P 101
Proof. Without loss of generality, we prove the case 1. The results in other cases can be derived in similar way. First, it holds that
P pmp(y),
(13)
where PTT the reduced transition kernel by m. and rip is the stationary distribution. Define a stochastic matrix Q through the equation
P P= pP + (1 P)Q.
(14)
We claim that
(P) (1-(1-1)))) (1- (1- + +1 (11- Q)*
(15)
To show this, we use induction. Clearly (15) holds when l: = 1. Assume that (15) holds when = n.
(P) = (1-(11))))P + Qp
(16)
Then,
(P) (1 (1 p)') (1 Q)*P)
(1 (1 p)* + (1-p)" (1-))Q)
(1 (1 - p) n ) + (1 0) n 1
(17)
which proves the claim (15). Thus, rearranging terms implies
||p* P'| < (1 - 1) - P s 1- p
(1 k)*
(18)
15

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Then, holds that
|
lim
Σ t=0
p
rl S
lim 7-0000
Σ t=0
Prr - 7P*r|| S 5 p) 1 -
1
(19)
p(1
p)
t=0
which further implies that
2 p(1 - p)
Sp(hp) S 2|11 S
(20)
Remark 10.2. As sufficient condition for the assumption in Lemma 10.1, it is commonly assumed that the Markov chains induced by any deterministic policy und transition kernels in the uncertainty set are uperiodic and irreducible (Levin & Peres, 2017). Since the aperiodicity can be ensured by applying the aperiodicity transformation (Puterman, 1994), the only additional assumption required is the irreducibility of the induced Markov chains.
Remark 10.3. Another well adopted assumption that can imply an upper bound on H. is to assume uniformly Geometric ergodic chains. Namely, there exists constants m, Ps such that for all deterministic policy and kernel,
[I(P")" -n S mm
(21)
In this case, it holds that
T-1
2m
S. max Sp PEP
lim
Σ
((P*)* - -nnnm )r $
I-
(22)
70000 1=1
11. Proof of Theorem 3.4
We first prove some important lemmas.
Lemma 11.1. Under Assumption 3.1, for any 7 (0, 1) and any stationary policy n, it holds that
11g (1 plobo s Spp(11 (V,,.)
Proof. Recalling the definition of oe in (1), we have that for any kernel P and policy x,
gF Tm:
where r, is the induced immediate reward function: r (s) Eir(s, a)la (T))], and P the Cesàro limit (Puterman, 1994) of the transition kernel P that follows the policy æ.
On the other hand, we have that
7PP (I-?Pm) Tx.
(23)
Note that:
P (,(T->P=) = -Pp (1 7)
(24)
where the above equation is from the fact that for every policy æ, Ps P" PpPx P"P = Thus.
P = -1= -1-
(25)
Hence,
g Prr (1 (1-7)P= -1- 7Px)
P -1-11))) V.
(26)
Here, the last equation is from (23).
16

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Since each of P is transition kernel of unichain, 9p (s) is constant Vs and can be bounded
min - 7) - gp I max(1 - (.))s(
(27)
Taking min on both sides of inequality (27) implics that PEP
min min - ") 1 min gp 9p. PEP
(28)
PEP
By interchanging the order of two min operators, have that
min(1 - 7) min V (.((ss) min(1 (s, S sgp.
(29)
PEP
On the other hand, we have
9p-
min gp = min
P -) V.7.p
(30)
PEP
We denote by Q2 E P the worst case transition kernel Vgpp. Then,
g Q1 V)
(31)
= Q1 >)V S max(1 (s),
(32)
(33)
where (31) is from (30), (32) is from the definition of Q,, and (33) is because for every distribution of Q, we have
Eq, [11-)) 7.0.1 I max(1 - - 7,0 (s).
Combining (29) and (33), we get
min 7) () S o5 1 max(1 - >,)
(34)
This implies that
11 (1 (1,-)V,,,ple <Sp((1 (/)
(35)
which completes the proof.
Lemma 11.2. Under assumption for any [0, H)) we setwesryyy y where 7- max
Sp(hp') then
PEP
Sp VV Sc..
Proof. Since the MDP is assumed to be unichain, both gp and gpp are constant. Moreover, g and h satisfy the robust
Bellman optimality equation (Wang al., 2023e):
C0p + (s)
(s) max {r(s,a) opg
(36)
where apy (V) - min p V.
pEPs
It is also known that for any 7 E [0, 1), the optimal robust discounted value function VSTY satisfies the discounted Bellman equation:
Voa (s) max (r(s.a) + t00py (V
(37)
17

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Next, aim to rewrite the robust discounted Bellman equation to obtain a form similar to the Bellman equation for the average reward setting. First, we define
h
1 gp.
(38)
7.P
Note the fact that " and Vi have the same span because 9p is constant:
Sp(h "
Sp(V
(39)
Now, we substitute (38) into (37) to obtain an equation similar to (36);
(s) =
h
7
x
+
|ー
1-7
(8) = max
r(s, a) + +00p
77
xyix"
+
1
= max r(s) + +00ps
+
Jp
(40)
where (40) is because 93 is a constant and can be taken from the support function. The above equation can be written
as
(8) = max (r(s,a) a) + +00p; (M"T7"" )
gp
g6
(41)
1
a
1
This implies that
"0 + g0 (8) max { ((() t0pp= (1)xp²)} }
(42)
Combine (36) and (42) and Vs E S we have
1h:p h p
[s) = max (().a) + 1p:0ppp) }
-max (((s,0) + -opp (hypp"
(43)
< max jop; (1%²) - -rop= (17Tp H
(44)
= max (op; (1 ) - -7op: (17")
+ 770pp 11 - -7ops Fxrii
(45)
< max (nopp (1p') -70py
T. ) ) mmx (11 p) (h }}|.
(46)
And since jopy (V) Opy (W) S V| - W| and opy (V)l - ||
1h ho (s) S >11/5" - hT oo + (1 - 711 ll
(47)
Thus, it follows that,
11 xx 11 S 11/ 11.0.
(48)
Now, we combine (39) and (48):
Sp (?,),)> Sp(h xx.i"
S 2|,,,
"- 1100 S 41//5' loo.
(49)
From Theorem 3.1 of (Wang et al., 2023c), for any policy there exists a transition kernel Pv E Pw such that h& = hp, + ce for e. E R, where e denotes the vector (1, 1, 1) E |S| Hence, we have that
Sp(V I 4|/15' 1o 41, 1bo0
(50)
and
Sp(V p.) S 4/ /lxe S 4Sp(hpg)) S 471.
(51)
which completes the proof.
18

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Combine the above results, then we direcly have the following result. Corollary 11.3. Under Assumption 3.1. for any 7 E (0, 1) and the policy ny it holds that
9p
Vo,pllo S H.
Lemma 11.4. Under assumption 3.1, any [0, H). we set y ". then Sp((1 - (/pp) Sc.
Proof. First, we utilize the definitions of the finite time-horizon reward function V7,((s) 2 ET. _ r2 - and
the other definition of bias (s)
A limr-+50
VT.p - gg
Note that:
V 7.P
min V
(52)
7.P
PEP
T-1
min
lim
? 'p' 7- TT T
(53)
PEP
7-+00
T-1
min PEP
lim T-+20
VT.. - (1 - 7)
Σ
7 b-
pt
Vi-IP)
(54)
n.
1=1
Recall the worst case transition kernel Q, where Qj E P:
T-1
7,P = V7,0 lim Vi., - (1-
Σ
7
Q V=-10
(55)
T-000
t=l
We have:
T-1
Sp(V = Sp(VV S lim sup Sp( + (1-7)
Σ
(56)
T-200
Now the objective is to find upper bound for Sp(VF.e,) ). From the definition of h2, have
hā, liim (Vila, tg²,)
(57)
N
= lim N
1
Σ
(Vi.e, - -1922)
(58)
N
1=1
lim N
1
Σ
(Vr.e- - -tgg.).
(59)
N
1=T-1
Thus, have
h6 lim
Σ [VV.2, -TgO,) +
VT Vi-TQ. (1- +T (L-))
N+ N
1=1+1
N-T
-VF.e, - -Tg ) + Qt lim
Σ (V (ViTT, (t (t- ()-
(60)
No000 N
I=T+1
-T.e, - TTe Q 15
It follows that
V7,0, = =Tge, + hhe 2T
(61)
19

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Thus, have
Sp(VF.. S 2Sp(h )-
(62)
Note that Sp(hş) is continuous and P a compact set, thus Sp(hp) S H. VP E P. Now we can combine the result from (56) and (62):
T-1 Σ
Sp(V Sp(V S lim sup Sup 717) T-200
1 Sp( Sp(V.-
(63)
x
S 2Sp(h1
1+ (1 -1) Σ xt-1
(64)
t=1
=Sp(hhp
(65)
Thus,
Sp(V.,)) 47H.
(66)
As direct corollary, it holds that Corollary 11.5. Under Assumption 3.1, for any 7y E (0, 1), it holds that
gr
Vo 47H
Proof. From Lemma 11.1 and Equation (66),it holds that
19g (1
V D.pplll S SSp((1 ()((1-))V7,5)) S 4(1 -7)H,
which completes the proof.
We are now ready to prove the main theorem.
Theorem 11.6. (Restatement of Theorem 3.4) Under Assumption 3.1, for any if we set y= H. then any e, optimall policy n for the robust 7-DMDPS is also an O(c)-optimal policy for the robust AMDP, iee.
5e
gp
9p
<
8
(67)
H
Specifically, an O(H)) robust policy for the robust DMDP is an O(c)-optimal robust policy under the average reward.
Proof. Under Assumption 3.1, for any (0, H. and any 8 (0, 1], consider policy of the robust DMDP and At, is an -pottiall policy in the robust DMDP. Then,
z. Suppose n. is an optimal
[[ - >> 7. (1 >) S (1 7)6y-
(68)
Considering (35), (51), and (66), we have that:
Sp((1 - -. S Sp((1 - -)) 21((1 - -) - (1--)V >> 11x
< 4e + 2(1 7)
(69)
Foor a robust DMDP, an e-optimal policy is some policy a such that V, (.) S V
20

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Moreover, because of the optimality of myy.
V V
(70)
recalling that n" is an optimal policy of the robust AMDP.
By merging Lemma 11.1, (68), (69), and (70) we have:
9 < (1 V + de 2(1 ?),
(71)
$ (1 - [1)- 7, + 4e + 2(1 7)
V
(72)
$ (1 V)x + 4E + 3(1 E)
(73)
S 9p Se + 5(1 - 7)yy
4
(74)
which completes the proof.
12. Proof of Theorem 4.4 Part
We first note that the result under the case R 2 π can be directly obtained from the existing result in (Shi al., 2023).
1
Specifically, it is shown in (Shi et al., 2023) that learning optimal policy for d-discuunted robust MDP requires samples of size
CSA log A(S.....).)) (1-7)² m R, Je
(75)
Thus, by setting 7 = 1 1 77 and 6, = H as Theorem 4.1, we have that the complexity to learn e-optimal policy for the robust average reward MDP is
CSAlog eSA
CSA log aSA 2²R
CSAH log eSA
(76)
(1 ) max RR 1 - 73e
We hence mainly focus on the case of R
1 In the following proof, we denote Ey as H.
We first introduce some notation. Let P and P be the estimated nominal kernel and estimated uncertainty set. For any policy n, let T 7 7.76 Vr, be the robust value function w.r.t. perturbed reward and estimated uncertainty set, unperturbed reward and estimated uncertainty set, unperturbed reward and the true uncertainty set. The optimal robust policy w.r.t. V is denoted by " and the corresponding optimal robust value functions are denoted by V 7 and Q* "
We consider a general policy and we denote the worst-case kernel of any vector V under Po and P by P..VV and P.Y.V. Then, holds that
4 3.
VTP = Tx rx
+
pp.. Vx 7E - (rr +ypm.
VTP))
-7 V
> /イ (>pm.
V
7. -7pt - v
7:
(1)
I 7 V=
V=
- p p + (xpm) v*
7 - -yp=, V
7
7iP) )
where (i) holds by observing that
p w
P
V 7 S
V 4
w
7.8
due to the worst-case kernel. Rearranging terms leads
V 7
V.P.p S 7
-1 (p=.
V 7/8
(77)
7.
21

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Similarly, we can also deduce
V
Vi =1 + .pT.
V 2. - (rz + 7
VT
y.P
7,p)
V (1p%:
V
->pr. V=
(>pt.
V
->pT - V 7i 7.
10
v.P
3.P/
7 P 12
7.8
-p
viTp)
+
(7
10
V --p V
7.1
7.P)
2 7 [ - -p.p))
(pm
v
p
V
(78)
7,7
Combining (77) and (78), we arrive at
V 7 voplll 00 Symax {|l (1 pp=))) -1 (px.P va (px
- -pr.pv
V
ve'
7.8
7,
10
|| (1 (I- (pw
va 3.8
- P V
(79)
m
7:
By decomposing the error in a symmetric way, we can similarly obtain
V. - Vy Vl bo S 5ymax
{||( (1((1~>0m)) -bm)))
(PnVVV - s
7,P
k7pp)
|| [I- (1-- -1
( - w
VT.
V..
y,p/
}
(80)
m
12.1. Part A: 11 |T.
Consider 1/=' (s) - V=
7 (s)l for some state s. If 5x (5) V= (s) > 0, then
1 (s)(s)) - (T, (5) = 1/ (s) V/ (s)
= (1 >P"' - -(1 -71- ) -1pp
5 (1 - 7P w -1
(1 7ppp" ) -
IN
(81)
where p=* and px are the corresponding worst-case transition kernel. w
A similar result can also be obtained for the other case, hence it holds that
| (s) - 7, ll S
(82)
6
We thus have that
| 3.P
S
V= 7.P
|| 7.P
V.r S
+ 7.
V.T ll,
(83)
7.
and it suffices to study the second term
V.r Applying (80) further implies that -| 7.
-| 7.P
Voril
S 7 max {l| - -p=:)pp -1
(pm V
V -=t. V
t0
-1 || (1 1px. ;r) -rr)))((
(pxt V3*t.Vvss Vor pss iv v.Spp) } w
(84)
We first consider the case that max {1( - - -1 (pxi. " VV 7.P
- ....p.V
VV 7.
: (I 1-
-1 (ps. VV
p* .V 7.P
>p () ( (p=..V VV p V VVn"
7.P
7.P
We first apply the following lemma.
22

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Lemma 12.1. (Lemma 11 of (Shi et al., 2023)) Consider any E (0, 1). Setling N 2 log( (199A)) with probability least
1 6, has
log I8SAN
Varpr (v7pp) + log( 18SAN
p V. V...P.
VV..Va Pw
V
2
1.
(85)
N
N(1 - 7)
Thus, it holds that
|| (1
p. -1 (p=
- - V==
m
7.P
7.P
log( 18SAN) 6 N
log( 18S
(I->P=7.))
2\
Varpar (V7.p)
N - 7)
log( 18SAN
2
5 N
(I-ンPTr
Varrgg o (VT.P)
log( 18SAN
(I- (1- pT::D) :)== -1
+
N
v Varpa & (V775
7.80
A2
log( 189AN
(1- -p ....i.)) p) V Varpgr (VTTp) - Varp.. (V
8
N
A3
log(
18SAN 5
(1- pp::p) u
Varp (VTTT) /Varp. (VT3))
log( 188AN
+ 21
(86)
N
N(1 - -1
A4
PV* Term A1. We note that Q A pe arg millper 7,2
thus we have that
V 7
= = + + (VTT) = r +7 V=
7:33
(87)
On the other hand, we have that
7.0 = - + 7.Q.
(88)
hence both 7.P 7.Q are fixed points of the Bellman operator w.r.t. Q which implies they are identical V**
and
3.5
Vn
7.0
-1 Thus, the term (T (T->PE 1)
Var Varpe. pr 7,6
(V
can be rewritten
w
(I (1-
Var pa- (V = (1-70-")" / /Var (V,7)),
(89)
and the term A1 can be rewritten as
log( 18SAN
(T-10=²) -1
A1 = 2/
Varque (V
(90)
N
We then apply the following lemma to bound A1, which is the main result for the complexity improvement.
Lemma 12.2. For any policy n. if N 2 0
log
SA
). holds with probability least 8 that
|| (1- (1-
cIHl (1
V VVrra. (V,70)
S
991)
7)
23

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
The proof of this lemma can be derived similarly the ones in (Zurek & Chen, 2023). For completeness, we provide its proof in Section 12.4.
Thus, it holds that
201 log( 18SAN H
A1 <
(92)
2
Term A2. holds that
log( 18SAN
A2 = 2/
(1-
Var pa. (V7.5 - 7,
N
log( 18SAN
$ 21
V
V= 7.8
(93)
N(1 - 7)2
Term A3. It holds that
(1 - p
Varpy (VT5)
x² Varpr- (V755)
= =(1 -1-17p0
pr. ppx))=
([aar pr. (VT2)) (arp(V?,))))
(1- px. (1-
Varpy. (VT,)) - ((rp(V)))))
(94)
Note that both V p belong to the uncertainty set P, hence 1Â - -Pl11 S 2R, which further implies that
|Var (V7T5)
Varp V. (K?.)))))s ))
= -VVarpa (VT.P
1 1- 9p - Varp (Vr (Vr-p) 1- yp 1a,
< <Ip - P|[1 1
97 1|
< 2RH?,
(95)
where the last inequality is from Lemma 11.1 and Lemma 11.2.
Since R S 1 holds that
A3 S 2
log(
I8SAN
(I-)p=))
V2Hi S $2
log( 18SAN 1
(96)
N(1 - 712
Term A4. We directly apply Lemma 6 of (Panaganti Kalathil, 2022) and Lemma 11 of (Shi et al., 2023), and it implies that
logg( 18SAN
A4 <
(97)
N(1 7)²
We then plug (92), (93), (96) and (97) in (86), and we have that
7
1
f VT 7.p - P Vo.Vera
T.P
log(
18SAN
20 log( 188AN 171 8
log( 18SAN
log(
18SAN IH
log( 188AN
N(1 72
(1 2NN
+ 2
N(1 - )2
Vxa
7.P
V5
7.8
+2
N(1 7)2
N(1
7)2
8
(98)
24

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
32 log 18SAN)
We note that if we set N 2
it holds that
C1 log( 18SAN
20 log( 18SAN )
V. S
(99)
(1 7)
(1 2)2NN
which completes the first term in (80).
To bound the second term in (80), following eq (69) in (Shi et al., 2023), we have that -1 (P=
|| (1 - ")
VV p 7.P 11
log( 1
log( (88AAN)
(I-)P=""))
- VV
Varpe. 7.P)
(100)
N
N - 7)²
Now applying Lemma 12.10,
(1-
-1
va
7.P
- P..V VV. -P
7.P) w
C3 log( 8
N(1 - 7]
2C4 log( 18SAN 1712
(1 7
(101)
We hence obtain the bound on ||
V. as follows:
7.7
a1 log( 18SAN
a2 log( 18SAN H 8
11x0 2.
Vor S
(102)
N(1 7)
(1 - 7
C' log( 188AN) ) (1-7)²
when N
12.2. Part B: 1V=
V
7.7
Similarly, we have that
V
v.ll
S !3 -
7.Pl +
7.
V
S + |İ
xP Vrpppl.
(103)
hence it suffices to bound the term
1 7.8
V By setting क ã in (79), we have that
{|l ( (I-)pent)
| 7.0 - V 11p S 5ymax
- -
pa 7.8
w
7.8
(1- -1
(p
- p
(104)
w
7i
w
We first bound the first term Pt.V and p by w
|| (I->Ptt))
-1 (paiiv 7.
- pa v
|
To simplify notation, we rewrite P as
7.2)
We first introduce the following separation events:
2 A {V. (V;;
max Φ (0,0)) 2 w Vs ES) (*)
(105)
Ω2w A (Vxp(s))
max (**
(s,0)
2 Vs
(106)
These events indicate that there exists some threshold between the value functions of the optimal action and other actions, and there is no tie between the optimal robust value functions. It further implics that the optimal policy 4" and T are unique. As we shall show in Lemma 12.3, with a carefully chosen threshold, such events will occur with high probability.
25

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Lemma 12.3. Set
(6(1-7) 35A2 then both (105) and (106) occur with probability least 1. 6.
We then combine Lemma 14 from (Shi al., 2023) and Lemma 9 in (Li et al., 2020) together show the following result. Such result allows to decouple the dependence between f and other terms.
log
G4SAN2 (1-118
Lemma 12.4. Consider any 8 E (0. Taking N 0 (106) occur, and it holds that
with probability at least 26, events (105) and
1-7
log( 548AN2 (1-3)8
8 logg( 54SAN2 (1-7)6
p
V 7.5
P
V 7,10
S 21
V Vaar.... (V& 7,,))++
1.
(107)
N 7)
With Lemma 12.4 in hand, we have
[
V
-P..V
V 7.P)
7.
(
- P,,,
17)
-1
F
V
P P
w
7.35
7.5
log( G4SAN2
8 8log( 54SAN2
21
(I-7)8
- >-
Varya (V+ (2,0) +
(1-7)5
N
N(1 7)2
8 log(
54SAN2 [1-7]8
log( S4SAN2 (1-7)8
1+21
(I-2pH;)) mi
pa. i (V* Var
[11 - 7)2
N
3.75
=:B;
log( G1SAN2 [1- (1-2)8
/ -1
+ 2V
Varps (V+ (Vx.p))
Var
p
(V* p
(108)
N
7:P
=:Ba
where (i) and (ii) hold by the fact that each row of (1 - 7) (I (I- 7.. is probability vector that falls into A(S).
Term B1. Similar term A1, term B1 equivalent to 2V log( AN
(P)- Varp(VV,p)) with P pa.
Specifically, & can be viewed as the optimal policy for and the empirical uncertainty set. Thus, applying Corollary 11.3 implies that
I|V 7.8
9p 7
|| S H.
(109)
and hence
2d, log( 18SAN H
B1 S
(110)
(1 (1-7)2N
Term B2. Similar to term A3, term B2 can be bounded by noting that R < H
log( 18SAN }H2
B2 < V
(111)
N(1 7)
Clog SAN (I-3)²
Combine both bounds together, and we have that when N >
(1 (p -1
P
p D p
Dj log( 18SAN 8
2D log( 18SAN 1112 8
+
(112)
7:76
N(1 7)2
2
26

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
with probability at least
-. Similarly, we can get the bound the second term of (104), which finally implies that
D1 log( 18SAN
2Dz log( 18SAN yH2
| 7.P
(113)
N(1 - 7)2
2
12.3. Summing Up the Results
Combine the bounds obtained from both Part A and Part B, it holds that with probability at least 46,
log( 18SAN
log( 18SAN 1712
V* 7.P
mIE + 12 V...D
mg
3 (1 2)
(114)
N(1 -(1-)) 7)2
when N C log( 188AN)
(1-1)²
Thus, achieve an e-optimal policy, requires a total number of samples of
log( 18SAN HH2
CSA 18SAN
NSA (1 222
(115)
(1 - 2}-
for some constant C. Then setting c = H and 7 и implies that
CSAH log SAN
NSA2
(116)
22
samples required to find c-optimal policy for robust average reward.
12.4. Proofs of Lemmas Lemma 12.5. (Lemma 6 of (Zurek Chen, 2023)) For any deterministic stationary policy n, we have
2
7 (1 >p=)11
Varp
7.P
Varp
7 Ru
(117)
1=
Proof. The following variance Bellman equation holds from (Sobel, 1982):
oc
Varp-
Σ
7' Ri
2 Varp=
[V..p]
Σ 7 Rr
(118)
On the other hand, it holds that
(1 - 7)e (1 -P---"-
Varp=
Va 7
$
r)e (ee -p=) Varp V.
-
Denote that v Varp.
V 7.pp we then have that
||(T - -1p-)-p---0
Volloo =7 1-
||11 - -7)(1 (I -1 Volll
(119)
1
S 7
[1(1 -r)(1 - - -
(120)
1
7 -- VIICT -pp) )
(121)
27

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Moreover,
-1--)" = - - ||<=-99'0007P9)11--9--111-
(122)
(1 -1-))p1)--1p
(123)
= 7)( +1
(124)
$ [[(1 - --- + +>|1(1 - 10
(125)
$ -> 000000
|| pp*) " 7 (1 22
(126)
$ ((++)][(->?p7) w11
(127)
(128)
Combining them with the variance Bellman equation (118), it holds that
Sn VI- 2 21111 (?)p) -1lllo S
1
/ 2
V -
Varp
7 R4
(129)
1==
Lemma 12.6. (Lemma 7 of (Zurek & Chen, 2023)) For any integer T 2 for any deterministic stationary policy have
Varp=
Et=
y' + V ( VV
Varpa
ET.Re
2T
Lemma 12.7. (Lemma 8 of (Zurek & Chen, 2023)) If 2 1
H. for some integer H 2 L, then
1
1-72H 2 1 (
1
4 H.
H
1 1-7
Lemma 12.8. Letting x² be the optimal policy for the robust DMDP (S,A, P), we have
H
Varp
< 1 -7
1=0
Proof. By using Lemma 12.6, it suffices to bound
Varp..
H-1 E R: + HH HVpx:((H))
Fixing state 8u S,
H-1 Σ
H-1
Varpa 2g
72t R4 + H (Sx)
Varp.
Σ 7 Re +
(vip(SH)
gp
30
1
1=
カ-1
2
Epr-
Σ
7' +
(kip(SH)
1
9p
t=0
#-1
2
2
< 2Epr.
Σ
+ 22Epr
H
(TT((SH))
2
1
272 2sup
(5))())
gp
1
472
28

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
where the last inequality can be similarly derived Lemma 11.1. We thus have that
4742
Varp.
7 R
1 72
Together with Lemma 12.7, this completes the proof.
log (I-7)56
Lemma 12.9. (Lemma 12.2) For any policy if O
it holds with probability least 1 that
1-7
[11-)00))
H
V Varr= (V770)
(130)
V (1 71-
Proof. We prove a more general result: for any kernel P, holds that
(1
-1 /Vaprr (KT
c1Hl
(131)
1(1- 71-
By Lemma 12.5, we have that
(1- >px)) -1
11
Varpa (V..p)
2
Varp.
Σ Pe
V 1
1=0
2
H
5
1
1074
(132)
V (1-7)2²
where (a) is due Lemma 12.8.
Lemma 12.10. For any transition kernels qi and q2, it holds that
|| [1 nor (I-
H2
Var (Vg.;)
(133)
V (1 (1-7)²
Proof. Note that (V), Var, - ke) for any l and e = (l, 1). Moreover, from Corollary 11.5, it holds that
1
up S 47.
(134)
1
Thus
1
Var o3 (V..p) Var 95"
(V
gp
V
gp
112 S 1672
(135)
1
The proof is then completed.
Lemma 12.11. (Lemma 12.3) Set w
EB( 1-)) then both (105) and (106) occur with probability at least 1 8. 39.4"
Proof. The proof is similar for both events, hence we only present the proof for (106). We show more general result, namely, with probability at least - 8, for any s and # az
{ō(1 - 7))
10) 01) (s,
(136)
35
29

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
We further introduce the following notation:
ry (5 01) = T, (s d') (.s V(',
(137)
+ (s,a1).
(138)
We denote the optimal robust value functionn and the optimal policy w.r. T, as Qi, V and x.
We first prove the following claim: there exists some r', such that
N. (s) # Ø1 for r <T', (s) Ø1 for all T T/,
(139)
(140)
Define
7' = sup(u (T( + a1, VT < u))
(141)
then it suffices to show (140) for our choice, which exactly follows as the proofs of eq (95) in (Li et al., 2020). We then prove the lemma as follows.
First, define the following sets:
1w, {r: Q1 <w}.
(142)
1 [ < ( ((( <w),
(143)
12, (00=)2 a2) <w).
(144)
Clearly, Jo..- = m, U 12 and we will show that the probability of these events is small.
Step 1. For E Iass note that V does not depend on т, since (s) * a1, and r is never active when calculating V.". Thus, the robust Bellman equation becomes
(1)) = - 10 (V²), (*() = f(s,02) + y0 (V7).
(145)
Thus, it holds that
p0 (V?) Q' (s))2)) 0z) < w). wi (T: 70
(146)
Since both terms po (V7") and Q" (s, a2) are independent from r, the Lebesgue measure of I most 2ns.
Step We consider 12 First, note that
5s Or - -Q, S TT - Tn + (a(((( - (V,)))
STa Tn + -
(147)
for any 72 > tI > 7', which is from the 1-L-iscchizz of the support functions. Moreover, for any (x.b) # (8, a1), since Tre (x. b) = rr (x: b), holds that
0 5 - s V
(148)
On the other hand, note that
0 S V V. max Q max 0; S 110; - 11,
(149)
and thus
V VAll < 10 - Q2 ||.
(150)
30

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Note that (148) implies that
S 71V - V < IV - Villb b) + (s,
(151)
thus
10 - Q (Q On (8, a1) 2 V V ||
(152)
(s. a1), and we further have that Since TI, T', Q'' (1) and = 7
(z) -V = 0 (s,a1) - Qn (8, 2 VI - VA
(153)
and hence
IVV V = (8, Q7, (8,
(154)
Now from the robust Bellman equation, it holds that
2 (1) 0 (s,
- V
||r In + -
2 Pr Ir:
(155)
due the monotonicity properties of the support functions.
We note that (148) and (155) exactly match eqs. (99) and (102) in (Li et al., 2020), and hence the rest of the proof follows similarly.
S19AN2 log
Lemma 12.12. (Lemma 12.4) Consider any å (0, 1). Taking N 2 O
[I 730 1-7
with probability least 28,
events (105) and (106) occur and it holds that
log(
5ASAN2, (1-7)8
8 log(( SASAN2 (1-7)8
pa. v
Da.V
Y.P S 21
Varp
(V+
7.
+
(156)
7.P
N(1 - 7)
Proof. The proof is obtained similarly as Lemma 14 from (Shi et al., 2023), by only replace r(s, a) therein by B(f(s,
For any (s,a), a), by the duality we have that
(p*t)) w
)a. )
V 7.P - (pa. )a.
V 7.P S
max (m(inn, F+ 7.8 max, a+ (x)) (Pan - -Pa.) 11 pppplal.
(157)
Construction of auxiliary RMDPs with deterministic empirical nominal transitions. Recall that we target the empirical infinite-horizon robust MDP with the nominal transition kernel P. We define the nominal transition kernel and reward function as ps.a and y.M, which are expressed as follows
(s'u('' (s = 1(s =)) pan (),) ())15,))
for all (s', a) E x A, for all (5, E S and 3
(158)
and
(s, = u ye (3,a) E[F(5, a))
for all a E A, for all (3, a) S x A and s
(159)
Correspondingly, the associated robust Bellman operator is then
Sxx.) (Q) aM (3
inf PV, PEP(P
with V(²) max ((
(160)
31

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Fixed-point equivalence. Recall that 2r the unique fixed point of the Bellman operator with the corresponding robust
value f* 7.P'
We assert that the corresponding robust value function (V,, 7,p)), obtained from the fixed point of s.,
aligns with the robust value function V y,P as long as we choose u in the following manner:
u (8)
V 7.P (s) - inf PV*
(161)
PEP(e.) y.P
where eg is the s-th standard basis vector in R Towards verifying this, we shall break arguments in two different cases.
For state s: One has for any E A:
pa pa. (s, + inf PEP(P)""")
PV* = +y inf Pī** PEP(ex)
7.8
7.75
V (5)((s) - inf PEP(e.)
PV* 7.
+
inf PEP(e.)
P 7
V (s))
(162)
where the first equality follows from the definition of pa."" in (158), and the second equality follows from plugging in the definition of ut in (161).
For state s' * 8: It is easily verified that for all A,
s as +
inf PEP
PVR P r(( +7 inf PEPIPR 7.P = =T(Ô* (,) ()))))sss (sssss
PVR
7.P
(163)
where the first equality follows from the definitions in (159) and (158), and the last line arises from the definition of the is the fixed point of T(-).
robust Bellman operator, and that Q+ 7
of the operator T. (.) Combining the facts in the above two cases, we establish that there exists a fixed point by taking
1 plo (8,a) VA (8) Q
for all E A, for all s' o and E A.
(164)
@ D.s. (
Consequently, we confirm the existence of a fixed point the operator T Te (-). addition, its corresponding value function (V* ", also coincides with 7
7.8
This equivalence exactly matches with Step and Step 2 in Lemma 14 of (Shi et al., 2023), and hence the remaining part directly follows.
13. Proof of Theorem 4.4 Part 2
The proof of Theorem 4.4 mainly follows similar structure. We note that it equivalent show that
2(1 - R)H2 log( 36SAN
V
V.pllls
16
(165)
(1 (1-7)2N
In order to control the performance gap
V== V.A.p Il.. note that
7.P
7.P
V"" 7.P
Va 7
+
Va-
7
+
V
7.8
VA
7.
V0
7.
7.5
+
F4
758
- V4
7.D.
(166)
hence sufficient bound the two terms on the RHS.
32

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Part A: V 7.P blo
Towards this, recall the bound in (80):
7.P
1 7.P
Vppll Iloo S my {|(( - pp P)) (p (p.'.V''"
7:P - -Pii
-V 1 7:D)
|| (I-> (p Vor''Ver' Vx 7.P
- - V 7.P
(167)
To control the main term PW pa VV.
T.P PT V VV, in (167), we first introduce the following lemma.
Lemma 13.1. For any E (0, 1) and any fixed policy 9,, one has with probability at least - 6,
2(1 + R)H2 log( 218AN
| V7.
P...
V 7.P
541
(168)
80
N
Applying Lemma 13.1 by taking π = x* gives
2(1 + R)H log( 24SAN
p V...p PV..V=" V
54
8
(169)
which directly leads to
(1 y pp). ppt.V
-1
VV. - -p v
V
V
i
10
7iP
7,p)
< pm VV.. 7.P -
-
- VV vv
(1(11 -1
511
2(1 + R)H log( 24SAN
(170)
7.P
(1 (1-7)2N
Similarly, have
2(1 + R)H2 log( 24SAN
[1 (I (pp
.V Vx-
7.P
-....VV Vx*
7.P
$ 4v
(1-7)2N
(171)
Inserting (170) and (171) back to (167) yields
2(1 + R)H. log( 21SAN
V 7.P
Vi
(172)
(1 2
Part B: controlling
|
V* 7.P
Similarly, we have that
7,
| 7.
VØA Il.0 I 7 max {ll(1 - 7
(p
V*
-Pt.P
V
7.8
-
7.8
10
[1 (T-
pp.
V
-p..
VA
(173)
3.
7.
We introduce the following lemma which controls pa.0 V#
pa,
V
(173);
7.8
w
JB
Lemma 13.2. With probability at least - 5, one has
2(1 12
log(
369 AN
p v 7.
D pa
< 512s
(174)
7.6
N
Repeating the arguments from (169) to (172) yields
2(1 + R)7(2 log A6S
||v
v++
5 12
(175)
7.6
33

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Finally, combining all bounds together implies that
VT
7.P ll
2(1 + RYH log( 2ASAN
2(1 + RYH² log
368 ANO
S </
12
8
(1 (1-7)2N
(1 2)
2(1 + RiHH log( 36SAN2
- 161
(176)
(1-7)2N
13.1. Proofs of Lemmas
Lemma 13.3. (Lemma 13.1) For any 5 E (0,1) and any fixed policy n, one has with probability least 1 6,
2(1 + R)H2 log(
24SAN
p
V V
541
(177)
N
Proof. Step 1: controlling the point-wise concentration. Consider any fixed policy x and the corresponding robust value I-7 (independent from P). We note that |V]] s H. showed before. By the duality of CS sets (Shi
vector V A V.P go
al., 2023) it holds that
(P Da, VTP -P )a,a V...D
max at Emin, max, V(s)] (a RVarp ... ([Va))
[Pan[V/a= - /RVarp,,. A. ([V)a)
max @e(min, m()),mxx, V(s)]
(Ps.0 - -P,.a) [Vl + RVarp.... a.. ((Va) RVarp... ((Va)
ac [min, max, V(+)]
(Pan -Pan) [W]|+
max (min, max, V(s]]
max aE/min, max, V(+)
Varp... ([Va)) Varp... ([Vaa)
(178)
where the first inequality follows by the maximum operator being 1-Lipschitz, and the second inequality follows from the triangle inequality.
The first term in (178) can be directly bounded through an e-net technique and Hoeffding's inequality, which implies that with probability at least ô,
log( 28AN )
max ( max,, V(si] (P&.. - Posa) [Va I 21
(179)
N
holds for all (s, a).
Step controlling the second term in (178), Consider fixed a E [0, 1 applying Lemma 6 of (Panaganti & Kalathil, 2021) with [|[V]allo I H. we get that
2 log ( 1
| Vare... (Ma) Vare... (V)) S
(180)
N
5. We then introduce the following lemma, whose proof can be similarly derived as Lemma 18 of (Shi et al., 2023).
holds with probability at least
Lemma 13.4. For any V obeying ||V S H. the function (a, V) = Varp ((Va) v Varp... ([[a) w.I.f. a obeys
J [J,,(01, V) J..a V)I S 4v 12
34

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
We then construct an e-net N over [0, H] with size N, S 3eH (Vershynin, 2018), so that with probability at least 1 holds that for any (s, a).
it
53'
max max, V(o)] V /arr s,0 ([Va) Vare... ((Va)
aE/min, max,
IV Varp... (1Va) /Var.... ((Vaa)
max ae(0.1/(1-1))
+ sup aEN
Varp... ((aa) V Varp... (Vaa)
1-
2712 log( 2SA[N
(08)
2712 log( 2SA
21
N
27(2 log( 24SAN
- 2/
(181)
N
log 25 ASSIIN)
where (i) holds by the property of the e-net, (ii) follows from (180), (iii) follows from taking
8.V
Inserting (179) and (181) back to (178) and taking the union bound over (s, a), with probability at least 1 - 5,
(P )s,a V (p, (PiT.) )a,a )a,a),,n V
a jmin, V V(s) v(s)] (Pa.. - Ps,a) [Ma
S
max
max aE [min, m(x), V(+)
AVarp... ((Va)) - RVarp.... (Via)
2(1 + R)H² log( 24SAN
<
N
Finally, we complete the proof by recalling the matrix form as below:
2(1 + R)H23 log( 248
V V V. VV..V
S max
pa.V V (P )s.a V
$4/
(s,a)
N
Lemma 13.5. (Lemma 13.2) With probubility least
8, one has
2(1 + R)H2 log(
368 AN?
p V
v$
p..
V
I 12
(182)
7.8
7,6
N
Proof. For any (8,a), a), following the same arguments of (178) yields
(ptt
)an
V 7:
-PPt.
V )am
7.
= =| w
)aal (V*
7.8 s (Pr.V)
)na (V+
7.8 /
(Pa,a - -P..a Pa.)) [V= - +
<
max 0 min, v (s) (5) -93 max, v x. (5) [
VR.
Vara... (IV+, - -)pa) Varp... (Ivz, sblaa) (183)
max a6 min, de (6) max, 2, (8) -8)
35

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
The first term in (183) can be bounded through Hoeffding's inequality
(Ps.a - -Pa.a) [v [v..plaa
max
aE min, V 3.5 (t) max, V 7:
(+)-
(Ps.a Pa.a)
[V 7:5b
max
aél - H
log( 3SANS/2
(1-736
S <4/
H2
(184)
We then consider the second term of (183). Towards this, we can construct an auxiliary robust MDP (S, A, ,r,,, 7) as in Section D.2.2. in (Shi et al., 2023), so that 7. To Va,u* 9s.u* for some u" E H-, H.. We then construct an e-net N over [-H, H], so that |u' u| S e for some N.. Following (Shi al., 2023), it holds that
V Varp... (IV35 (8la)
Varpzn (IVA, 7.5 - -821.)
max aE min, 7. (5) max, 7.20 (8) 28
2R722 log( W
(185)
N
with probability at least - 8.
Inserting (185) and (184) back to (183), we have that with probability at least 6,
2(1 + RYH2 log( 36S
f P V
-
p..
V
S 121
(186)
7.
7.8
N
14. Function Approximation for Robust AMDPs
The algorithm design part almost identical to (Zhou et al., 2024). For completeness we provide a brief discussion.
Following (Zhou et al., 2024), we consider class of Integral Probability Metrie (IPM) Uncertainty Set. Given some function class F C R$ including the zero function, the integral probability metric (IPM) is defined by d>(p, == sup f q q f} 2 0 (Müller, 1997). Many metrics such as Kantorovich metric, total variation, etc., are special cases of IPM under different function classes (Müller, 1997). The IPM uncertainty set is defined as Pa = {q dz P.) < RJ.
We also consider the linear function class as (Zhou et al., 2024). Denote E Rd the feature matrix with rows ((x), we set
F F (s (s)) E: E IR |Il|| < 1).
(187)
Without loss of generality, assume & has full column rank, and let the first coordinate of d(s) be 1 for any We then detail the algorithm designs of the two updates steps in Algorithm 2.
Algorithm Robust Linear Temporal Difference (RLTD)
Input: T.
2: Initialization: 0o. 50
3: for k = 0, 1...... K - do
4: Sample a사 ~ T (-18s)), M according to P Pa and 88411 from 1/+++
5: Update Wh+1 0₂ + and(su) (T (SE, ag, 31+1) )(sx) To
6: end for
7: Output: 0x
We adopt the following standard assumption from robust RI, studies.
36

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Algorithm 4 Robust Q-Natural Policy Gradient (RQNPG)
1: Input: 8,77 W
2: Initialization: 80,80
3: for n - =0 0, I....... N do
4: Sample On ~ (-18-)))) U1++1 according to Paxins and determine Sn+1 from yo+1
5: Update un++ = un + Sno(sn an) (T Vo) Ons yn+1) p(Sn, an) Un
6: end for
7: Output: + MUN
Assumption 14.1. There exists 3 < 1 such that
79ss S BPa s,y, Vgg Pa.
(188)
This assumption is widely adopted in function approximation studies in robust RL, e.g., (Tamar et al., 2014; Xu & Mannor, 2010; Zhou et al., 2024), to ensure the solvability of function approximation.
We then provide the formal statement of Theorem 5.1.
Theorem 14.2. Set geometrically increasing step sizes 17 2 in Algorithm and Algorithm 4, and 2 Hooog H. then
8²H² -H-2211 for each t = 1,2..... T. Ser N,K K O(Hc-
......T.
gT Eig S <
T-1
MH?
+
c
HS
2²
where C' is some constant, and ce Cstat + Cbias measures the approximation error.
Proof. To apply Theorem 1 of (Zhou et al., 2024), is assumed that for initial state distribution p. there exists M such that supkep - 1o S MM < oc. We note that since 9.p is a constant and does not depend on the initial distribution, we can simply set uniform initial distribution p ...,, 5 ), in which case M
By applying Theorem of (Zhou al., 2024) with 7 1 3. it holds that
E(V S (1
T-1
SH2 C+
V7
H.S
Ee.
(189)
+ 1 Note that 6. = = VR VN
when omitting the critic error, thus setting N,K = O implies that
T-1
V
V S
SH.
(190)
H.S
Note that if we set T large enough so that (1
T-1 S H. which can be satisfied > Hog H then Ty is an H--optimal policy for the robust DMDP. Combining the above with Theorem 3.4 completes the proof.
14.1. Details for Experiments
To expand on our results Section 6, we provide additional detail here. In our experiments, for different discount factors " we run the corresponding RNAC algorithm (Zhou et al., 2024) to learn robust policy, and then we estimate the robust average reward of the learned policy by calculating the average reward under environment perturbations. Experiments were performed two custom perturbed MuJoCo environments, Walker2d-v3 and Hopper-v3, using the integral probability metric (IPM) uncertainty set (Zhou al., 2024). We evaluate the performance of algorithm with different perturbation levels, and the results, including one standard deviation from the mean, are shown below in Figure 10 for varying perturbation levels. These experimental results align with our theoretical results, and thus verify the scalability of combining our framework with function approximation.
To show that our framework does not result in high computational costs regarding varying reduction factors, we show the execution time of our method using these factors. As can be seen in Tables and 2, even with very large value for 7, the
37

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
7Ot01
Autroan Racond
15
Extimtted Updinal Aeerage swword
15
meted Taweed Uptinal svtrage Heward
63
Dreoumii Pactor
Figure 10. Scalability under Walker2d-v3.
execution time is similar, thus showing that our method is also computationally efficient. Similar how we showed in Section 6, we show additional results comparing our robust reduction method that of the non-robust reduction method in Figures 11 and 12 for neural network approximation in the Walker2d-và and Hopper-v3 environments, respectively. Additionally, while the focus of this work is on distributional robustness, we hypothesize that our reduction framework should work under the adversarial robustness formulation. Due to this idea and inspired by (Zhang et al., 2020), we conducted a preliminary experiment on (discounted) adversarial robust RL in the Humanoid-ve environment using increasing factors of y. As our result in Figure 13 shows, the reward under attack increases as y increases, indicating the potential to develop a similar reduction framework for this setting.
Table 1. Computational efficiency under the Walker2d-v3 environment.
PHASE
[=[0.9, 0.99, 0.999, 0.9999, 0.99998, 0. 0.9999904483887333
TRAINING
603.92, 630.72, 63, 706.32, 71 711.70 1070, 676.36 5.93, 25.60, 10.03, 9.16, 10.44, 6.05
EVALUATION
Table 2. Computational efficiency under the Hopper-v3 environment.
PHASE
[0.9, 0.99, 0.999, 0.9999, 0. 0.99998, 0999999533192601666
TRAINING
579.41, 634.98, 678.29, 29, 682.53, 686.92, 683.56 6.42, 37.80, 7.15, 5.80, 7.10, 6.84
EVALUATION
2000
2000
Non-Robust Reduction Method
1750
Non-Robust Reduction Mothod
Average Reware
-.50
1500
1250
Average
250
0.90
0.92
0.62
0.3
0.94
0.98
0.99
0.880
8.92
0.63
0.97
0.99
0.88
Disccunt Factor
Discount Tacto-
Figure 11. Neural network approximation Walker2d-v3.
38

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Redurtion Method Non-tobust
Reductton Method
900
Robust Reduction
700
000
Fvverage
000
500
000
0.90
0.92
0.3
038
0.99
0.90
0.1
0.92
093
0.66
0.7
0.8
0.99
Discount factor
Discount factor
Figure 12. Neural network approximation under Hopper-v3.
1200
Reduction Methoa Under Adversary
Average Reward
800
600
400
200
0.7
Discount Factor
Figure 13. Preliminary discounted adversarial robust under Humanoid-v4.
15. Model-Free RL for Robust AMDPs
15.1. Multi-Level Monte Carlo Robust Q-Learning
One potential way to improve scalability to design model-free algorithms. In contrast to the model-based method in the last section, model-free methods do not store the transition kernels and aim to learn the optimal policy directly. To illustrate the applicability of our framework and ensure it's scalability, we develop two model-free algorithms that can be applied efficiently for large-scale problems. First, introduce algorithm that combines reduction framework with the multi-level Monte Carlo (MLMC) technique (Liu et al., 2022b; Wang al., 2023e; Blanchet & Glynn, 2015; Blanchet et al., 2019; Wang & Wang, 2022), and provide theoretical analysis of its sample complexity. We further design another mini-batch model-free robust Q-learning algorithm for robust AMDP in Section 15.2. Both algorithms do not require model estimation and storage, making them scalable for robust RL. with average reward.
The MLMC approach is widely used to construct an unbiased estimator of the robust Bellman operator, which is challenging due its non-linear dependence on the nominal kernel (Wang et al., 2023e). It relies on a geometric distribution with parameter (0, 1), and requires N+1 samples each step, with Geom (V), construct unbiased estimator of Ope (V).
By adapting the MLMC estimator with our reduction-based framework, we propose the MLMC robust Q-learning algorithm for robust AMDPs, given in Algorithm 5.
Our algorithm is hence the first model-free one for robust RL under average reward, along with finite sample analysis. These results demonstrate the broad applicability of our reduction-basee framework, enabling the direct integration of any model-free algorithm designed for robust DMDPs yield algorithms for robust AMDPs with sample complexity guarantees.
"Specifically, support function ope (V) is not linear P
39

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
Algorithm 5 MLMC robust Q-learning for robust AMDPs
Input: A generative model of (S,A,,,r) uncertainty radius 0, robust bias span H. accuracy c. y 0.5, threshold
Nm
2: Initialization:() f 0, Su
3: 7 N. + 11-
4: < do
5: for all s E S. E do
6: V(s) t max, Q(s. a)
7:
Sample N ~ (e)
8:
N 4- fnin(NNm N
9:
Sample 2 samples following P
Obtain the multi-level estimator according to (191)
11: (s,.a)= r(s, a) v0p: (V)
12: end for
13: end for
14: (s) + arg max, Q(s, a), Vs
15: Output: K.
As result, our framework is scalable to large-scale problems while maintaining high data efficiency.
The MLMC operator based on a geometric distribution with parameter V E (0, 1). For any 8, a, we first generate number N from geometric distribution with parameter V (0, 1). Then, we take action state s for 2 times, and observe r(s, a)) and the subsequent state { 1, .....; 2N We divide these N+1 samples into two groups: samples with odd indices, and samples with even indices. We then individually calculate the empirical distribution of s' using the even-index samples,
the odd-index samples, all the samples, and the first sample: Pa.E S,N+1 전े Σi= 1o4.
pa.0 s,N+1
2i=1 - Pa 2,N+1 2 Ei= 2 1x;
P e,N+1 1 Then, use these estimated transition kernels as nominal
kernels to construct four estimated uncertainty sets (with the same uncertainty radius): Pa. s,N+ N,N+1 The multi-level estimator is then defined as
Pa.0 Pm Pa.1
N+N+ N,N+1
Aw(V)
Qpy (V) p 1.
(V) +
(191)
PN
where pN = 11 W and
Ppa.. ,,N11
(V)
pa. (V) ..811
Av(V) & p N.N41
(V)
Our threshold-MLMCC estimator is constructed as follows
A A N.. (V)
ōgg (V) A
ppa.1
(V) +
m.min
N11)
Pmin(N,Ne
The formal statements on the sample complexity are as follows. The proofs are straightforward by combining our framework with the results in (Wang al., 2024c).
Theorem 15.1. (I), For the TV-defined uncertainty set, set Nm of Algorithm is c-optimal policy for the robust AMDP if
2 and the step size B, (1-7 log
TlogT
Then, the oulput
N N2O δ SAH
(192)
3
(2). For the Chi-Square sieeurr-dvvveeeceeedeeeee uncertainty set, set Nm. of Algorithm is an e-optimal policy for the robust AMDP if
21og and step size as 3r
21og T
Then the output
log
(1-7)7
SAH
N > θ
(193)
40

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
(3). For the KL-divergence-deffned uncertainty set,
1og T log(1 (1 + Py log(25) log T)
Nm max where Ps. the minimal positive entry of the nominal kernel P. Then, the output of Algorithm 5 is an e-optimal policy for the robust AMDP if
log 2
log
SAHH C
N 2 Ō
(194)
15.2. Mini-Batch Robust Q-Learning with Variance Reduction
In this section, we present model-free mini-batch Q-learning algorithm. The algorithm is derived from the robust DMDP algorithm (Wang et al., 2023c), which employs variance reduction technique to improve the sample complexity. When combined with our framework, we can also achieve improved sample complexity for robust AMDPs. The details can be found in Algorithm
Algorithm Mini-batch robust Q-learning for robust AMDPs
1: Input: generative model of (S,A,, uncertainty radius o, robust bias span H. accuracy e, batch size n, and behavior policy
2: Initialization: Q1 0, 8g
H 4: for < do
3: Set
5: Vi(s) t max, a)
6: Sample a, ~ (--)8t)
7: Sample samples from Pa, and obtain empirical uncertainty set Pa:
8: A I+11-3
9: Q4t1 0z) e (1 Xs)Qu(se, ar) + (r(ss,, at) + pa: (V))
Sample the next 8141 Per from the generative model
11: end for
12: (s) f- arg max, Qr(s.a),Vs
13: Output: R.
We then derive the sample complexity of the mini-batch robust Q-learning algorithm, as stated in the following theorem.
Theorem 15.2. Consider the uncertainty set defined by the KL divergence. we ser
T == ( (SAA2) n Ô
(AAH
(
H
(195)
Algorithm 6, then the output policy h, of Algorithm 6 an c-optimal policy for robust AMDP.
The result shows that the mini-batch robust Q-learning requires Ô (SAH" 23
samples to obtain an e-optimal policy for the robust AMDP. This improves the sample complexity for MLMC robust Q-learning algorithm and represents the state-of-the-art in robust AMDP model-free sample complexity.
15.3. Numerical Experiments
To exemplify the scalability of our framework for robust AMDPs, we present concrete proof of convergence of our model- free MLMC robust Q-learning algorithm in figure 14. We first created the uncertainty set using total variation. Then for each value we wanted to test, we generate number N from geometric distribution with V E (0. 1) and take action a at state
We omit the complex dependencies of T and other parameters, including the uncertainty radius, highlight the potential of our framework.

---

A Reduction Framework for Distributionally Robust Reinforcement Learning under Average Reward
for 2-++1 times in order learn the optimal policy under the robust discounted DMDP. Once have the ey optimal policy, Hy, then applied algorithm from (Wang et al., 2023d) evaluate the robust average reward for each policy. This experiment was independently conducted 5 times, where plot the mean of the estimated robust average reward for every y factor along with 1 standard deviation above and below the mean in figure 14. Following this, we then implemented algorithm from (Wang et al., 2023d) order to find the optimal robust average reward. By combining our reduction-basse framework with the multi-level Monte Carlo (MLMC) technique (Liu et al., 2022b; Wang et al., 2023e; Blanchet & Glynn, 2015; Blanchet al., 2019 Wang & Wang, 2022), we are able to prove our theoretical results in showing that our model-free algorithm converges the optimal robust average reward.
MLMC Robust Q-Learning for Robust AMDPs
Average Reward
Optimal Reward
6
Estimated Average Reward
0.95
0.96
0.97
0.98
0.99
1.00
Discount Factor
Figure 14. Model-Free Experimental Results Under Total Variation
42


Reviews:
[{"review_id": "s7fVhXNvrS", "reviewer": "Reviewer_4tjq", "summary": "The paper introduces a reduction-based framework for solving robust average Markov Decision Processes (AMDPs) by transforming them into robust discounted MDPs (DMDPs). This framework allows existing methods for discounted reinforcement learning to be applied effectively to the average reward setting, ensuring data efficiency and scalability. The authors validate their approach through theoretical analysis and numerical experiments, demonstrating its robustness across uncertainty sets.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for your time and thoughtful feedback, and we are glad to hear that our work is appreciated. \n\nWe conducted additional experiments, at the link: https://anonymous.4open.science/r/ICML-2662-4C1E/README.md\n\n**W1: The estimation of $\\mathcal{H}$.**\nSince we mainly focus on developing the theoretical foundation of our reduction framework, we assume the knowledge of $\\mathcal{H}$, which is extensively adopted in previous theoretical studies, (see line 167, and additionally in [1,2]). Also we discussed several estimation methods in Appendix when problems have additional structures.  \n\nOn the other hand, while we acknowledge that in practice estimation of $\\mathcal{H}$ can be challenging, we emphasize that our framework and subsequent results are still effective if $\\mathcal{H}$ is replaced by its upper bound (see Remark 3.3). For example, the worst-case diameter is an upper bound and is easier to estimate [Wang et al., 2022]. We conduct additional experiments to verify our framework's effectiveness. We estimate the worst-case diameter for the Walker ($\\approx 511$) and the the Hopper environment ($\\approx 1339$), and plot the robust average reward of the policies learned from corresponding discount factors. We also specify the reduction factor and the optimal value. As the results in E1 in the link show, with our reduction factor, the reduction framework obtains a policy with the suboptimality gap within the error range, which verifies our theoretical results and illustrate the effectiveness of our framework with alternative upper bounds of $\\mathcal{H}$. \n\n[1] Zhang, Z. et al. Sharper model-free reinforcement learning for average-reward markov decision processes. 2023.\n[2] Wang, S et al. Optimal Sample Complexity for Average Reward Markov Decision Processes. 2023.\n\n**W2: Algorithm 2 only deals with linear approximation and needs to know the feature vectors in advance.**\nFirstly, we want to clarify that the feature vectors in linear function approximation are pre-set by the learner before learning, instead of some unknown parameters. Hence, these features are known by the learner and can be set through different ways, e.g., tile coding [1], Fourier basis [2], or randomly generated [3]. \n\nWe also want to highlight that, our reduction framework is independent of any specific algorithm used, thus it is not restricted to the linear approximation. After setting the reduction discount factor, any discounted algorithm can be applied to optimize the average reward. We present Algorithm 2 with linear function mainly to develop a theoretical guarantee, but it can combined with any algorithm. To verify this, we provide an additional experiment with neural network approximation in E2 in the link. As the results showed, our reduction framework remains valid even with neural network approximation, and is more robust than the non-robust reduction method. \n\n[1]Sutton, Richard  Generalization in reinforcement learning: Successful examples using sparse coarse coding. 1995.\n[2] Konidaris, G. et al. Value function approximation in reinforcement learning using the Fourier basis. 2011.\n[3] Ghavamzadeh, M. et al.  LSTD with random projections. 2010.\n\n**Q1: Are there any existing empirical methods for robust AMDPs? If so, the authors should compare their performance with the proposed methods in the experiments.**\nWe first acknowledge that there exist other methods for robust AMDPs (Wang et al., 2023c, Wang et al., 2023d). However, these methods only have asymptotic convergence guarantees, and can only be applied for tabular settings, whereas our method has finite sample complexity analysis and can be applied with function approximation. \n\nSince there is no straightforward implementations of these methods for large-scale problems, we compare our method to the two baselines, robust Value iteration (RVI) (Wang et al., 2023c) and robust relative value iteration (RRVI) (Wang et al., 2023d), under the tabular Garnet problem. We set the reduction factor to be $0.99$ in our framework (corresponds to $\\epsilon=0.001$).   Results in E3 in the link show that our method finds a better policy with the same number of steps. Thus, our method achieves state-of-the-art performance in robust average reward optimization. \n\n**Q2: Algorithm 2 is indeed a DMDP algorithm without the discount factor selection part?**\nWe clarify that we select the discount factor in Line 3. Based on our framework, robust average reward can be optimized through any algorithm for discounted MDP with the reduction factor. Thus, the remaining steps in algorithm 2 after selecting the factor is for the discounted reward. We also want to highlight that the developing of the reduction framework (instead of concrete algorithm design) is our major contribution.\n \n**Q3: What are the used $\\phi$s in the experiments when you implement algorithm 2?**\nFor each state-action pair, we generate a random vector and then normalize it to $(0,1)$ as the feature vector.", "claims_and_evidence": "Yes.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes, the theorems and the proofs are correct.", "experimental_designs_or_analyses": "Yes, the experiments are reasonable.", "relation_to_broader_scientific_literature": "This paper is theoretically sounded and empirical meaningful. \n1. Theoretically, the authors propose a provable framework to convert robust AMDPs to DMDPs by selecting an appropriate discount factor. The proof of Theorem 4.4 also has technical novelty to achieve tightness in the sample complexity under TV/CS constrained set.\n2. Empirically, the authors validate the theoretical findings by observing the average reward attained from different discount factors. \n\nLimitation:\n1. The estimation of $\\mathcal{H}$ seems hard when the environment is complicated, and thus empirically the selection of the discount factor might need hyperparameter fine-tuning.\n2. Algorithm 2 only deals with linear approximation and needs to know the feature vectors in advance.", "essential_references_not_discussed": "N/A.", "other_strengths_and_weaknesses": "N/A.", "other_comments_or_suggestions": "N/A.", "questions_for_authors": "1. Are there any existing empirical methods for robust AMDPs? If so, the authors should compare their performance with the proposed methods in the experiments.\n2. Algorithm 2 is indeed a DMDP algorithm without the discount factor selection part?\n3. What are the used $\\phi$s in the experiments when you implement Algorithm 2?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "gGOkZgXcUm", "reviewer": "Reviewer_JZQS", "summary": "This work proposes a reduction-based framework that converts robust average reward optimization into robust discounted reward optimization by selecting an appropriate discount factor. The framework focuses on total variation (TV) and $\\chi^2$ divergence and introduces a model-based algorithm with near-optimal sample complexity. It also applies function approximation techniques to robust average reward and proposes a robust natural actor-critic (NAC) algorithm with linear function approximation. The experimental results demonstrate the effectiveness of the proposed approach.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for your time and thoughtful feedback, and we are glad to hear that our work is appreciated. \n\nWe conducted additional experiments, at the link: https://anonymous.4open.science/r/ICML-2662-4C1E/README.md\n\n**W1: Results for other uncertainty sets**\nWe first want to highlight that the TV and $\\chi^2$ are the most commonly studied in robust RL, e.g., (Shi et al., 2023; Panaganti \\& Kalathil, 2022; Yang et al., 2021), and we develop our studies for them to compare with existing results and illustrate the advantages of ours. \n\nHowever, our framework is independent of the uncertainty set used, hence results under other uncertainty sets can be directly obtained. For example, the results under KL divergence are discussed in Line 237 and Theorem 15.1 and 15.2 in Appendix. Results for Wasserstein distance can be similarly obtained based on [1]. However, as we discussed in Section 4, results directly obtained are generally suboptimal due to the loose bound associated with the discounted reward  setting. Tightening this bound and improving the sample complexity, however, can be challenging and may require tailored efforts for each individual set. We therefore leave these investigations for future work.\n\n[1] Xu, Z., et al. Improved sample complexity bounds for distributionally robust reinforcement learning. 2023.\n\n**W2: Results in Fig 1**\nIn Fig 1 we plot the robust average (not discounted) reward $g_{\\mathcal{P}}$ of the policies learned under different discount factors. We want to clarify that increasing $\\gamma$ does not imply the increase of the average reward. It holds that $(1-\\gamma)V_{\\gamma,\\mathcal{P}} \\to g_{\\gamma,\\mathcal{P}}$ (eq 6), however, there may not exist a monotonic dependence of the average reward on the discount factor, and hence a larger discount factor can still result in a smaller average reward. This instability is one of the motivations of our work: rather than selecting a large factor that may still lead to suboptimal performance, we aim to identify a specific factor with a performance guarantee.\n    \n**W3: Out-of-sample testing**\nWe first want to clarify that the experiments are performed with out-of-sample testing. We trained our algorithms under the nominal kernel and tested them under the worst-case kernel, which is generally different from the raining environment. Thus, the testing environments are never seen during training, and hence they are out-of-sample testing. \n\nAs for the advantages of our method v.s. the discounted one, as our results showed, with a small discount factor (less than the reduction factor we choose for our method), the robust average reward (reflects the total reward by tracking the total time steps) is higher, thereby demonstrating the benefit of our approach. Additional experiments are showed in \nE1 in the link, where we plot the optimal value and our reduction factor. As the results show, our method (with the reduction factor) results in a near-optimal policy, whereas the DMDP are worse.\n\n**Q1: Figure 4 is fuzzy** Thank you for letting us know. We will fix this issue in the final version.\n\n**Q2: Computational time**\nSince the algorithms are implemented with fixed time steps, the computational cost is then determined by the cost for each step. In our Algorithm 1, we use robust value iteration in each step, whose computational cost is $\\mathcal{O}(S^2A\\log (S))$ for both TV and $\\chi^2$ sets (Iyengar, 2005). This cost is typical for any model-based robust RL method. \n\n**Q3: Algorithm 2 v.s. original Robust Natural Actor-Critic**\nWe would like to clarify that our major contribution is the development of a reduction framework to reduce the challenging robust average reward problem to the easier discounted one, and the framework also enables methods for large scale optimization with function approximation.  We thus adopt the NAC algorithm in Algorithm 2 to illustrate that our framework can also be applied with function approximation techniques. Hence, the major part of the algorithm will be similar to RNAC, but the major contribution is the choice of the reduction factor in Line 3, which provides the performance guarantee under the average reward. As we showed numerically in E1 in the link, the choice of the reduction factor is necessary, otherwise RNAC with an randomly chosen factor can result in suboptimal performance. We also provide the first theoretical convergence guarantee for robust average reward with function approximation in Thm 5.1. \n\nAs for the computational time, it will be identical to the NAC if the discount factors are the same. To illustrate that our framework will not result in high computation cost (with the reduction factor), we show the execution time for different factors in E4 in the link. Clearly, even with a large gamma, the execution time is similar, and hence our method is also computational efficient. More importantly, we provide solution to the average reward optimization, and RNAC is for discounted.", "claims_and_evidence": "Yes. Claims made in the submission supported by clear and convincing evidence.", "methods_and_evaluation_criteria": "Yes.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "The author presents two sets of experiments. In the first part, Garnet MDP is used to evaluate the data efficiency of the algorithm. In the second part, two classic examples from GYM are used to demonstrate scalability.", "relation_to_broader_scientific_literature": "Compared to previous work, this approach applies to a more general setting and achieves better sample complexity.", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "Strengths:\nThe paper is well-structured and clearly presents its ideas. The authors provide a near-optimal complexity supported by strong proofs. In addition to proposing a model-based algorithm for robust AMDPs, they also introduce the Reduction Robust Natural Actor-Critic approach to address problems with function approximation. The experimental results are convincing and demonstrate the efficiency and scalability of the proposed method.  \n\nWeaknesses:\n1. This work primarily focuses on total variation (TV) and $\\chi^2$ divergence. Citing relevant references would help justify that these divergences are commonly used. Incorporating KL-divergence [1,2] or Wasserstein distance [1,2] could further improve the generality and applicability of the approach.  \n\n2. In the experiment, Figure 1 shows the robust average reward with different discount factors. According to the definition  \n\n\\begin{equation}  \nV_{\\gamma, \\mathcal{P}}^\\pi(s) \\triangleq \\min _{\\kappa \\in \\bigotimes_{t \\geq 0} \\mathcal{P}} \\mathbb{E}_{\\pi, \\kappa}\\left[\\sum_{t=0}^{\\infty} \\gamma^t r_t \\mid S_0=s\\right],  \n\\end{equation}  \n\na larger $\\gamma$ should imply a larger reward. However, in Figure $1$, there are cases where a smaller $\\gamma$ performs better. This observation is also different from Figure $5$ in Appendix $9$.  \n\n3. In the experimental section, it would be beneficial to perform out-of-sample testing and use the total reward to compare AMDP and DMDP(different $\\gamma$). This would better demonstrate the advantage of the proposed method.  \n\nReference:\n\n[1] J. Grand-Clément and M. Petrik. Reducing Blackwell and average optimality to discounted MDPs via the Blackwell discount factor. Advances in Neural Information Processing Systems, 36, 2024.\n\n[2] Y. Wang, A. Velasquez, G. K. Atia, A. Prater-Bennette, and S. Zou. Model-free robust average-reward reinforcement learning. In Proceedings of the International Conference on Machine Learning (ICML), pp. 36431–36469. PMLR, 2023d.", "other_comments_or_suggestions": "1. Figure $4$ is fuzzy.\n\n2. What is the computational time of the algorithm as the state size $S$ and action size $A$ increase?  \n\n3. In Algorithm $2$, the main part of the algorithm is similar to the structure of Robust Natural Actor-Critic. The author should provide more explanation about the contributions of the proposed algorithm, or compare the computational time of the tailored algorithm $2$ with the original Robust Natural Actor-Critic.", "questions_for_authors": "No.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "F5Hf1rJSXl", "reviewer": "Reviewer_PFDp", "summary": "This work builds a framework to aid in the reduction of average reward MDPs to robust discounted reward MDPs. Previous work has shown that as discount factor approaches 1, a policies value function in a robust discount reward MDP approaches the return found in an average reward MDP. This work builds a framework that helps choose the correct discount factor in a robust DMDP that achieves the desired approximation to a robust AMDP.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for your time and thoughtful feedback, and we are glad to hear that our work is appreciated.\n\nWe conducted additional experiments, at the link: https://anonymous.4open.science/r/ICML-2662-4C1E/README.md\n\n**W1: More extensive empirical evaluation.**\nSince we focus mainly on theoretical studies, we only use experiments as illustrations of our claims. We first want to mention that have some additional experiments in the appendix. We additionally develop the following experiments.\n\n1. To verify the effectiveness of our reduction framework, we conduct experiments with reduction factor estimation and the optimal robust average reward in E1 in the link above. As in Remark 3.3, our framework and subsequent results are still effective if $\\mathcal{H}$ is replaced by its upper bound. We adopt the worst-case diameter, which is an upper bound and is easier to estimate [Wang et al., 2022], as an alternative of $\\mathcal{H}$. We estimate the worst-case diameter for the Walker ($\\approx 511$) and the the Hopper environment ($\\approx 1339$), and plot the robust average reward of the policies learned from corresponding discount factors. We also calculate the reduction discount factor for different optimality level $\\epsilon$. As the results show, our reduction framework (with the reduction factor) obtains a policy with a suboptimality gap within the error range, which verifies our theoretical results and illustrate the effectiveness of our framework, even in large scale setting.\n\n2. To verify the scalability, we conduct experiments with neural network approximation in E2 in the link above. As the results showed, our method is more robust to the non-robust baseline, while also maintain scalable. \n\n3. To enhance our empirical evaluation, we develop a primarily experiment under more practical adversarial robustness, under the humanoid environment. Although adversarial robustness has a different formulation from the distributional robustness we study, we believe that the reduction framework should also work. We conduct a preliminarily experiment inspired by [1] in the Humanoid-v4 environment. We implement (discounted) adversarial robust RL under increasing factors, and plot the average reward under attack. As the results (E5 of the link above) show, the performance improves as $\\gamma$ increases, hence the reduction framework should also remain effective, i.e., there exists a reduction factor to reduce the average reward to discounted reward. It is also promising to develop a similar reduction framework for adversarial robustness. We leave the development of theoretical analysis and the identification of the reduction factor for future work.\n\n4. We compare our method to other baselines in (Wang et al., 2023c, Wang et al., 2023d). These methods only have asymptotic convergence guarantees, and can only be applied for tabular settings, whereas our method has finite sample complexity analysis and can be applied with function approximation. We compare our method to the two baselines, robust Value iteration (RVI) (Wang et al., 2023c) and robust relative value iteration (RRVI) (Wang et al., 2023d), under the tabular Garnet problem. Results in E3 in the link show that our method finds a better policy with the same number of steps. Thus, our method achieves state-of-the-art performance in robust average reward optimization\n\nWe will also include more experiments in the final version. \n\n[1] Zhang, H. et al,  Robust deep reinforcement learning against adversarial perturbations on state observations, 2020.\n\n**W2: The intuition for Theorem 3.4 should be in the main paper instead of leaving everything to the proof.**\nWe would like to thank you for your suggestion. We provide a brief sketch of the proof for our reduction framework.\n\nThe key step is the study of the convergence error of the robust discounted value function to average reward. The result (Lemma 11.1) shows that the error is upper bounded by the Span semi-norm of the robust discounted vector $\\|(1-\\gamma)V^\\pi_\\gamma-g^\\pi \\|\\leq Sp ((1-\\gamma)V^\\pi_\\gamma)$, for any policy $\\pi$. We can thus control the choice of $\\gamma$ so that the RHS is smaller than $\\epsilon$. We can then decompose the error between the optimal robust average reward and the one under the learned $\\epsilon_\\gamma$-optimal policy $\\pi$ (we omit $\\gamma$ from $V^\\pi_\\gamma$): $g^{\\pi^*}-g^\\pi= g^{\\pi^*}-(1-\\gamma) V^{\\pi^*}+(1-\\gamma) V^{\\pi^*}-(1-\\gamma) V^\\pi+(1-\\gamma) V^\\pi-g^\\pi\\leq \\epsilon+\\epsilon_\\gamma+\\epsilon$, which completes the proof of the reduction. \n\nThe improvement of sample complexity for model-based methods is also based on this key result. Using the fact that $\\|(1-\\gamma)V^\\pi_\\gamma-g^\\pi \\|\\leq Sp ((1-\\gamma)V^\\pi_\\gamma)$, we can bound the variance terms (the main challenging term in the complexity analysis) in terms of $\\mathcal{H}$ instead of $(1-\\gamma)$, thereby improving the results. \n\nWe will provide a more detailed sketch in the final version.", "claims_and_evidence": "The main claim in this work is that solving a DMDP with a discount factor of $1- \\frac{\\epsilon}{\\mathcal{H}}$ within $\\epsilon$ of the optimal policy will correspondingly produce a policy in the ADMP where the suboptimality is bounded by $8 + \\frac{5\\epsilon_\\gamma}{\\mathcal{H}}$.  This claim is proven in the appendix.\n\nFurther, the work introduces a model-based algorithm for solving robust AMDPs, under strict assumptions that the transition kernel can be arbitrarily queried. The work also claims that this method can scale to the function approximation setting, specifically with linear and neural network function approximaters.", "methods_and_evaluation_criteria": "To verify empirically the choice of discount factor necessary for reduction, the authors solve the Garnet problem tabularly under different discount factors. They demonstrate (in Figure 1) that the predicted discount factor produces the $\\epsilon$-optimal policy in the DMDP setting and the equivalent in the AMDP setting.\n\nFurther, Figure 2 demonstrates that the performance of the proposed methods scales with the size of the dataset, eventually reaching optimal performance. Lastly, the Figures 3 and 4 demosntrate the ability to find the optimal robust AMDP policy on common RL benchmark tasks in Mujoco.", "theoretical_claims": "Not verified.", "experimental_designs_or_analyses": "The experiments in this work are minimal and discussed in the Methods and Evaluations Criteria section. This work presents a mostly theoretical framework.", "relation_to_broader_scientific_literature": "The main result is the reduction of the robust AMDP to a robust DMDP. This provides practitioners a tractable way to solve both types of MDPs interchangeably.", "essential_references_not_discussed": "N/a", "other_strengths_and_weaknesses": "Beyond more extensive empirical evaluation, this paper would benefit greatly from including some intuition for Theorem 3.4 in the main paper, instead of relinquishing the proof to the appendix.", "other_comments_or_suggestions": "n/a", "questions_for_authors": "n/a", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "22tT4zPVyH", "reviewer": "Reviewer_chdA", "summary": "The paper \"Efficient and Scalable Reinforcement Learning for Average Reward under Model Uncertainty\" focuses on solving robust reinforcement learning (RL) with the average reward criterion, which is crucial for optimizing long-term performance in uncertain environments. The key challenge is that most robust RL methods focus on discounted rewards, while average reward RL is more suitable for real-world applications like queuing systems, supply chain management, and communication networks. However, robust average reward RL is difficult due to non-contractive Bellman operators, high-dimensional solution spaces, and model mismatches between training and deployment environments.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We sincerely thank the reviewer for your time and thoughtful feedback, and we are glad to hear that our work is appreciated.\n\nWe conducted additional experiments, at the link: https://anonymous.4open.science/r/ICML-2662-4C1E/README.md\n\n**W1: Scalability is demonstrated using linear function. No theoretical guarantees for non-linear function approximation.**\n\nWe use the commonly adapted linear function approximation to illustrate scalability, as it has better mathematic properties and enables rigorous theoretical studies. Under it, we develop both empirical and theoretical studies. \n\nHowever, our major contribution is the reduction of the challenging robust average reward, which is independent from algorithms used. Thus we can adopt any algorithms for the discounted reward, no matter what function approximation is used. As an empirical evidence, we develop additional experiments with neural network approximation, shown in E2 in the link above. As the results show, our robust reduction method enjoys enhanced robustness against non-robust baselines, and the increasing robust average reward as $\\gamma$ increasing further verifies the effectiveness of our reduction approach, even with neural network approximation. However, even standard non-robust RL with neural network approximation generally lacks theoretical guarantees, thus it can be challenging to derive theoretical results. We leave this as a future direction. \n \n \n\n\n**W2 \\& W3: The uncertainty estimation is not practical, and thus extending the framework to a non-parametric uncertainty set would be beneficial. Robust policy evaluation requires solving a min-max problem over an uncertainty set, which may not be tractable for large-scale problems.**\n \n\nWe first emphasize that the computational cost for finding the worst performance (i.e., robust policy evaluation) in TV and $\\chi^2$ sets are $\\mathcal{O}(S\\log S)$ (Iyengar, 2005) under the tabular setting, thus their estimation can be tractable. \n\nOn the other hand, developing efficient methods for distributionally robust RL with large scale is still an open question. One potential way is to relax the uncertainty set constraints, which can result in an efficient solution to the support function, even for large or continuous spaces [1,2] (Zhou et al., 2024). Adversarial training techniques can also be applied to approximate the robust value functions [3-5]. \n \n\nWe agree that the framework for robust RL with a non-parametric uncertainty set is important, but it generally lacks a concrete theoretical formulation. However, we expect that our intuition of reducing the average reward to the discounted reward still remains valid under different uncertainty sets. We conduct a preliminary experiment under adversarial attacks (please see below) to illustrate this.\n\n\n[1] Kumar, N. et al. Policy gradient for rectangular robust Markov decision processes. 2023.\n[2] Zhang, Y. et al. Robust reinforcement learning in continuous control tasks with uncertainty set regularization. 2023.\n[3] Huang, S., et al.  Adversarial attacks on neural network policies. 2017.\n[4] Pinto, L., et al.  Robust adversarial reinforcement learning. 2017.\n[5] Yu, T., et al. Combo: Conservative offline model-based policy optimization. 2021.\n \n\n\n**W4: The experiments do not test adversarial robustness in real-world deployment settings.**\nWe emphasize that we consider the distributionally robust RL formulation, which aims to enhance robustness under dynamic uncertainty, and is more tractable for theoretical studies than other formulations of robustness. Since we focus more on the theoretical aspect, we only use synthetic experiments to verify our results. In our experiments, we applied perturbations to the joints and other parameters to simulate dynamic uncertainties, which provides evidence for our theoretical claims.  \n\nWe acknowledge that adversarial robustness is also important, and we believe that our reduction framework can also be extended to the adversarial robustness setting. We conduct a preliminarily experiment inspired by [1] in the Humanoid-v4 environment, shown in E5 in the link above. We implement (discounted) adversarial robust RL under increasing factors, and plot the average reward under attack. As the results show, the performance improves as $\\gamma$ increases, indicating the potential of developing a similar reduction framework. We will conduct more comprehensive experiments and include them in the final version.\n\n\n[1] Zhang, H. et al,  Robust deep reinforcement learning against adversarial perturbations on state observations, 2020.", "claims_and_evidence": "The paper claims that their framework scales well with large problems through function approximation, but it only demonstrates scalability using linear function approximation. They do not provide theoretical guarantees for non-linear function approximation, making the robustness of their approach questionable in high-dimensional problems.", "methods_and_evaluation_criteria": "1. The uncertainty estimation seems not practical, since it is computed primarily under total variation, chi-squared, and KL divergence. Although those methods are commonly used in theory, but may not computationally efficient. Extending the framework to more realistic non-parametric uncertainty sets would be better.\n\n2. Robust policy evaluation requires solving a min-max problem over an uncertainty set, which may not be tractable for large-scale problems.", "theoretical_claims": "Yes.", "experimental_designs_or_analyses": "1. The experiments focus only on synthetic perturbations in MuJoCo but do not test adversarial robustness in real-world deployment settings (e.g., changes in environment dynamics, sensor noise).", "relation_to_broader_scientific_literature": "This paper formalizes a reduction framework with a concrete discount factor selection, making the connection practical for real-world use. It also extends sample complexity analysis for robust RL, building on Agarwal et al. (2020) for model-based RL and Panaganti & Kalathil (2022) for robust RL under uncertainty sets (e.g., TV, Chi-squared, KL divergence).", "essential_references_not_discussed": "No.", "other_strengths_and_weaknesses": "See comments above.", "other_comments_or_suggestions": "No.", "questions_for_authors": "Please answer the questions mentioned above.", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper studies robust RL with average reward by building a reduction to robust discounted MDP. With the reduction framework, any robust discounted MDP algorithm can be used to solve the original problem in the average reward setting. 

While the reviewers in general are positive on the paper, there are still a few concerns about the paper. First the proposed approach needs to estimate the worst case diameter. The authors mentioned that they can estimate the diameter in practice but more details should be provided in terms of how and when one can ensure the estimated diameter is accurate. Another conern is on the computation side. Beyond very special settings such as tabular, it is in general computationally intractable to solve the robust MDP problem. Authors probably should fully discuss these points in their final version of the work.
Decision: Accept (poster)