Provable Policy Gradient for Robust Average-Reward MDPs  Beyond Rectangularity
Authors: Qiuhao Wang
Yuqi Zha
Chin Pang Ho
Marek Petrik
Venue: ICML 2025 poster (2025)
Keywords: Markov Decision Processes
Average-Reward Markov Decision Processes
Policy Gradient
Robust Optimization
Primary area: reinforcement_learning->planning
TL;DR: We propose a generic policy gradient algorithm for solving robust average-reward MDPs.

Abstract: Robust Markov Decision Processes (MDPs) offer a promising framework for computing reliable policies under model uncertainty. While policy gradient methods have gained increasing popularity in robust discounted MDPs, their application to the average-reward criterion remains largely unexplored. This paper proposes a Robust Projected Policy Gradient (RP2G), the first generic policy gradient method for robust average-reward MDPs (RAMDPs) that is applicable beyond the typical rectangularity assumption on transition ambiguity. In contrast to existing robust policy gradient algorithms, RP2G incorporates an adaptive decreasing tolerance mechanism for efficient policy updates at each iteration. We also present a comprehensive convergence analysis of RP2G for solving ergodic tabular RAMDPs. Furthermore, we establish the first study of the inner worst-case transition evaluation problem in RAMDPs, proposing two gradient-based algorithms tailored for rectangular and general ambiguity sets, each with provable convergence guarantees. Numerical experiments confirm the global convergence of our new algorithm and demonstrate its superior performance.

Provable Policy Gradient for Robust Average-Reward MDPs Beyond Rectangularity
Qiuhao Wang"s 1
Yuqi Zha 2 Chin Pang Ho Marek Petrik
Abstract
2011). However, applying MDPs to real-world problems often faces the challenge of model uncertainty, particularly in transition dynamics, which are rarely known precisely. To mitigate the impact of model errors, robust MDPs (Iyen- gar, 2005; Nilim & El Ghaoui, 2005) offer a compelling solution by assuming that uncertain parameters lie within a predefined ambiguity set. These robust MDPs aim to iden- tify policies that optimize performance under the worst-case scenario within the ambiguity set.
Robust Markov Decision Processes (MDPs) of- fer a promising framework for computing reliable policies under model uncertainty. While policy gradient methods have gained increasing popular- ity in robust discounted MDPs, their application to the average-reward criterion remains largely unexplored. This paper proposes Robust Pro- jected Policy Gradient (RP2G), the first generic policy gradient method for robust average-reward MDPs (RAMDPs) that is applicable beyond the typical rectangularity assumption on transition ambiguity. In contrast to existing robust policy gradient algorithms, RP2G incorporates an adap- tive decreasing tolerance mechanism for efficient policy updates at each iteration. We also present a comprehensive convergence analysis of RP2G for solving ergodic tabular RAMDPs. Furthermore, we establish the first study of the inner worst- case transition evaluation problem in RAMDPs, proposing two gradient-based algorithms tailored for rectangular and general ambiguity sets, each with provable convergence guarantees. Numerical experiments confirm the global convergence of our new algorithm and demonstrate its superior performance.
The majority of existing research on robust MDPs focuses on the discounted setting, where future costs are discounted by factor 7 E (0, 1). Under this setting, robust MDPs be- come computationally tractable by imposing certain rectan- gularity assumptions, such as (s, a)-rectangularity (Iyengar, 2005; Nilim & El Ghaoui, 2005), s-rectangularity (Le Tal- lec, 2007: Wiesemann et al., 2013), k-rectangular (Mannor et al., 2016), and r-rectangular (Goyal & Grand-Clement 2023). Significant progress has been made in both value- based methods that rely on the Bellman equation (lyengar, 2005; Nilim & El Ghaoui, 2005; Kaufman & Schaefer, 2013; Ho et al., 2021; Panaganti & Kalathil, 2021) and gradient- based methods that directly optimize the policy (Wang & Zou, 2022; Li et al., 2022: Wang et al., 2023a; Kumar et al., 2024a; Lin et al., 2024; Wang et al., 2024a). De- spite these advances, research on robust discounted MDPs beyond structured rectangular ambiguity sets is still scarce, with only few notable exceptions (Li al., 2023), as solv- ing robust discounted MDPs with general ambiguity sets Na-hard (Wiesemann et al., 2013).
1. Introduction
Markov Decision Processes (MDPs) (Puterman, 2014) pro- vide powerful framework for sequential decision-making, with applications such as game solving (Mnih, 2013), health- care (Shechter et al., 2008), and finance (Bäuerle & Rieder,
While much of the existing work focuses on robust dis- counted MDPs, many real-world systems that primarily focus on the steady-state behavior, such as queueing con- trol and scheduling automatic guided vehicles (Kober et al., 3),3), may still yield policies that perform poorly over the long term (Wang et al., 2024b). Meanwhile, as discounted factor y approaches one, solution methods tend to con- verge more slowly. increasing computational costs (Grand- Clement et al., 2023). We refer interested reader to Ap- pendix E.5 for more detailed numerical illustration. As such, optimizing the long-term average cost preferable to the total discounted cost for these applications.
"qqual contribution 'Fintech Innovation Center, Research In- stitute for Digital Economy and Interdisciplinary Sciences, South- western University of Finance and Economics 'Department of Data Science, City University of Hong Kong 'Department of Computer Science. University of New Hampshire. Correspon- dence to: Chin Pang Ho <clint.hode @ cdtyu.cdu.hk>, Marck Petrik <mpetrik @ es unh.edus.
Proceedings of the 42nd International Conference Machine Learning, Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).
To overcome the limitations of the discounted setting, recent

---

Policy Gradient for Robust Average-Reward MDPs
research has focused on robust MDPs with the average- reward criterion (Tewari & Bartlett, 2007; Lim al., 2013;
1.1. Related Work
Average-reward MDPs. Early research on average-reward MDPs focused on fundamental characterizations of the model and its properties (Bertsekas, 2012; Puterman, 2014). Many existing methods consider model-free approaches in tabular settings (Abounadi et al., 2001; Yang et al., 2016; Wan et al., 2021; Avrachenkov & Borkar, 2022; Wan & Sutton, 2022: Chae et al., 2024; Yang et al., 2024). Func- tion approximation techniques have also been studied for AMDPasMarbach & Tsitsiklis, 2001; 2019; Wei et al., 2021; Zhang et al., 2021: Chen et al., 2023; Wu et al., 2022; Zhang & Xie, 2023). Parametrization methods are another popular approach (Liao et al., 2022; Wang et al., 2022; 2023b; Bai et al., 2024), along with gradient-based methods (Murthy & Srikant, 2023; Grosof et al., 2024; Kumar al., 2024b). Despite these advance- ments, addressing the robust setting introduces additional challenges, which we focus in this work.
Grand-Clement et al., 2023; Wang et al., 2023d;c; 2024b; Sun et al., 2024). While policy gradient methods have been widely employed in standard reinforcement learning due to their empirical success and flexibility for problems in com- plex environments, and have been effectively extended to robust discounted MDPs, the development of robust policy gradient for average-reward settings with optimality guaran- tees remains largely unexplored in the literature. To this end, we aim to develop a computationally tractable algorithm for solving robust average-reward MDPs (RAMDPs) with theoretical convergence guarantees. The challenges and our major contributions are summarized as follows.
Yadkori et al.,
Our first contribution is Robust Projected Policy Gradient (RP2G), a novel generic policy gradient scheme for solv- ing RAMDPs. While RP2G retains the policy gradient updates used in nominal average-reward MDPs (AMDPs), it incorporates an additional inner subroutine for evaluating worst-case transitions. To reduce the computational cost of optimally solving the inner subroutine, RP2G incorporates a decreasing tolerance sequence for the inner subroutine, ensuring convergence even in the general ambiguity setting.
Robust average-reward MDPs. Research on robust average-cost MDPs is limited (Tewari & Bartlett, 2007; Lim et al., 2013; HeandCClement et al., 2023; Wang et al., 2023d;c; 2024b; Sun et al., 2024), with no prior work on gradient- based algorithms. While a concurrent work by (Sun et al., 2024) extends mirror descent for RAMDPs, their approach is restricted to (s, rectangular ambiguity sets and requires exact worst-case transition evaluations, leading to high computational costs. In contrast, RP2G en- sures global convergence for general compact, convex ambi- guity sets and reduces computational cost via a decreasing adaptive tolerance for the worst-case transition evaluation.
Our second contribution establishes the global convergence of RP2G to the optimal policy, assuming an oracle for solv- ing the inner subroutine. While this result aligns with findings for nominal AMDPs (Kumar et al., 2024b), the robust setting introduces unique challenges, including the non-differemiaabliiyy and non-convexity of the robust re- turn (Razaviyayn al., 2020). We address these challenges by leveraging the Moreau envelope as differentiable surro- gate for our convergence analysis.
2. Preliminaries
Our third contribution is the two proposed specialized gradient-based algorithms to solve the inner problem: one for rectangular ambiguity sets based on projected gradient ascent, and another for general ambiguity sets leveraging novel projected Langevin dynamics update. Both algorithms are supported by convergence and optimality guarantees. To our knowledge, this is the first study addressing the inner worst-case evaluation problem for RAMDPs.
2.1. Average-Reward Markov Decision Processes
A nominal infinite-horizon average-reward MDP is defined by the tuple M = (S, A. p, e, p), where S = {1, 2,...,... S} and A = (1.2...., actions, respectively. The initial state is chosen randomly according to the distribution p E A The probability distribution of transiting from current state s next state s' after taking an action is denoted as a vector Psa := (Peas' ) E 5 ,which is part of the transition kernel p = (Psa)sES,aEd E (AS)S*A, The instantaneous cost of this transition is denoted by Csas' (or equivalently, a reward Teas' = ). We assume Coas' E [0. 1] for all s, s E S and A, as translating or scaling costs does not affect the set of optimal policies (Puterman, 2014).
represent the finite sets of states and
Notation. Boldface lowercase letters and uppercase letters are used denote vectors and matrices, respectively. The symbol denotes a vector of all ones of the size appropriate to the context and the symbol denotes the Euler's 's number. The set R. represents the set of real numbers, and the set R+ represents the set of non-negative real numbers. The probability simplex in Ş is denoted as 8 For vectors, we use || |l to denote the norm.
We focus on stationary randomized policies due to their practical simplicity (Sutton & Barto, 2018; Zhang et al., 2022). A stationary randomized policy π := (T.) where π, E AA, specifies the probabilities over actions a E A for each state s E S. Under this policy, the action a
2

---

Policy Gradient for Robust Average-Reward MDPs
is selected with probability Tea whenever the AMDP is in state S. The set of all stationary randomized policies is
2.2. Differential Value Functions
denoted by 11 = (AA)S.
In the average-reward setting, we introduce the following differential functions, analogous to the value and action- value functions in standard MDPs. These functions quantify the accumulated deviations from steady-state performance and serve as key elements in our subsequent analysis. Specif- ically, the differential action- value function is defined as a solution to the following Bellman equation:
The long-term average cost (p( p)) for a given policy π and transition kernel p is defined as
1
_p(T. = lim T-000 T p.sorrp
Ca. Carar
(1)
Here, p.erpp denotes the expectation with respect stochastic process where the action a, is selected according to the policy T.. the next state 8(+1 evolves according to the transition kernel as and the initial state So is drawn from the initial distribution E AS, For time-homogeneous MDPs with finite state space and bounded costs, the limit (1) guaranteed exist (Puterman, 2014).
TP Epeas (Coos) -J (
Σ Te' qdld
and the differential state-value function (also referred to as the bias function in (Puterman, 2014)) is defined as:
n..
Σ Usa Dpsas (Ceas' - J p) + U/
In this work, restrict our attention to the ergodic setting, which is formally stated through the following assumption: Assumption 2.1. The MDP M is ergodic, i.e., for any pol- icy æ and kernel p. the Markov chain {#t Je20 irreducible and aperiodic.
where it is known that = Barto, 2018). Note that dT and qTT are unique only up to an additive constant, i.e., the above equations are satisfied by q - ccce and Tm oge for any arbitrary constants ei and c2. To uniquely determine these functions, the additional constraint Σ. d P.T.P = 0 throughout the paper (Puterman, 2014; Wei et al., 2020; Bai et al., 2024; Cheng et al., 2024). Under this constraint, the differential state-value function be uniquely written as,
=EEA Teu -
(Sutton &
impose
The assumption of ergodicity is standard in average-teward
MDPs (Gong & Wang, 2020; Wei et al., 2020; Pesquerel & Maillard, 2022; Bai et al., 2024; Cheng et al., 2024; Ganesh et al., 2024; Wu et al., 2024). Under ergodicity, the average cost objective is independent of the initial distribution p for any feasible π and p (see, for example, (Puterman, 2014, Section 8)). Hence, cost by overloading the notation J as:
(Ca,0 - J p))
0 .TP := ET p.
redefine the long-term average
and the differential action-value function is
Jp( p) = ((T, == Eg os s' [Ceast] (2)
8
P. = Exs.p.s
(en - ((T
where P E S is the stationary state distribution induced by and p. formally defined as:
2.3. Robust Rverage-Reward Markov Decision Processes
d lim
E n
1 (st Σ 1=
$}
(3)
In most applications, the exact transition kernel is not known precisely and must be estimated from data. These estima- tion errors often lead to policies that perform poorly when deployed. To address this challenge and ensure reliable policies under model uncertainty, RAMDPs, specified by (S, A, P, c, p), aim to optimize the worst-case performance over set of plausible errors (Goyal & Grand- Grand-Clement, 2023; Wang al., 2023e; 2024b).
is well-established that the stationary distribution is unique under ergodicity (Norris, 1998; Meyn & Tweedie, 2012: Gagniuc, 2017) and independent of p as well (Puter- man, 2014). The goal of AMDP is to find policy "² minimizing the long-run average cost:
arg min #ETl
min max J(T,P)) well PEP
(4)
The above stationary and Markovian policy π" is guarantee to be optimal, even when considering the broader class of all possible policies, including stationary ones (Puterman, 2014).
where P is referred to as the ambiguity set. By appropri- ately calibrating P, the optimal policy derived from (4) can guarantee reliable performance in the face of model errors GGrand-Clement et al., 2023; Wang al., 2024b).
and non-
3

---

Policy Gradient for Robust Average-Rewart MDPs
The concept of rectangular ambiguity set has been widely adopted in the context of robust MDPs due to their fa- vorable computational properties (lyengar, 2005; Nilim & EI Ghaoui, 2005; Wiesemann et al., 2013; Ho et al., 2021). Two broad classes of rectangular ambiguity sets are mainly considered in this paper:
Algorithm 1 Robust Projected Policy Gradient (RP2G)
Input: initial policy πo. iteration number T, step sizes {arteso tolerances {6 with dt+1 I Tô, for some T E (0.1) for 10..1,....,T--
// Worst Transition Evaluation Compute Pe such that J Pt) 2 max
Definition 2.2 ((s, a)- and s-Rectangular Ambiguity Sets). An ambiguity set P S (AS)SxA of transition kernel is called
max J(T,, p) d;; pEP
// Policy Improvement
Update Tet1 f Proin - at (
end for
1. (s, a) -rectangular (lyengar, 2005; Nilim & El Ghaoui, 2005) if it is a Cartesian product of sets Pa.a S A for each state $ E S, i.e., P = II (x..s)))Sx..P...
Output: :
; such that [(Tr,pe)
min J J(T., Pc)) VE(U,...TT))
2. s-rectangular (Wiesemann et al., 2013) it Carte- sian product of sets P, - (A for each state s e E and action a E i... P P...sP.
3.1. Robust Projected Policy Gradient (RP2G)
From an optimization perspective, the optimal policy x for the RAMDP is the solution (T²', .p') of the minimax prob- lem (4), where πt minimizes the function maXpep J (TT, p), and p" represents the worst-case transition kernel that max- imizes ((T",)) (Jin et al., 2020; Luo et al., 2020; Raza- viyayn et al., 2020; Zhang et al., 2020). Thus, solving the RAMDP can be equivalently formulated as
Otherwise. we refer to an ambiguity set P as a general ambiguity set in this paper if is neither (s, --rreannga nor s-rectangular, allowing for various dependencies across states and actions, including k-rectangular and r-rectangular ambiguity sets. While general ambiguity sets tend to be less conservative, they introduce significant analytical chal- lenges, even in the discounted setting (Nilim & El Ghaoui, 2005; Wiesemann al., 2013). We refer interested readers to Appendix E.6 for a detailed numerical illustration.
min #ENl
(TT)
= max J (TT. PEP
p)).
(5)
Note that, in contrast to most prior work that assumes rect- angularity in RAMDPs (Goyal & Grand-Clement, 2023; Wang et al., 2023c;d; 2024b; Sun et al., 2024), our analy- sis of the proposed robust policy gradient method does not rely on this assumption. Instead, we only require that P be compact and convex. However, rectangularity assumptions can be helpful when developing algorithms for the inner maximization problem.
It may seem natural to attempt solving (5) by performing gradient descent on the function V. However, this approach is not applicable since V is not differentiable due to the inherent "max" operation (Razaviyayn et al., 2020). Further- more, as V is neither convex nor concave, its subgradient does not exist either (Nouiehed et al., 2019; Lin al., 2020). To overcome these challenges, we propose a specialized ro- bust policy gradient algorithm summarized in Algorithm 1, termed Robust Projected Policy Gradien (RP2G).
3. Robust Policy Gradient for RAMDPs
RP2G adopts the well-known gradient-descent-assee (GDA) scheme, drawing inspiration from the two-timescale rule to form a nested-loop structure with a max-oracle. In this section, we assume the existence of an oracle capable of solving the inner maximization problem. Further details regarding the evaluation of the inner worst-case transition kernel will be provided in Section 4.
In this section, we introduce a policy gradient approach for solving RAMDPs. The key contribution of this section is to demonstrate that our algorithm computes globally optimal solution of problem (4) with guarantees despite the non- convexity of the objective J(,, This result builds upon recent advancements in policy gradient methods for both ordinary MDPs (Agarwal et al., 2021; Bhandari & Russo, 2024) and AMDPs (Kumar et al., 2024b).
Specifically, RP2G iteratively searches for an optimal policy in (5) by taking steps along the policy gradient. At each iteration I, Algorithm first performs an inner update to approximate the worst-case transition kernel p; for some given precision 8, Once p: is obtained, RP2G performs the projected gradient descent on with fixed pi:
The rest of the section is organized as follows. In Sec- tion 3.1, we describe the motivation and details of our new policy gradient scheme. Then, in Section 3.2, provide standard convergence analysis, showing that our algorithm is guaranteed to converge to the global solution. To the best of our knowledge, this is the first generic robust policy gradient algorithm for a general ambiguity set that comes with global convergence gaarocegguaaannn guarantees.
π T++11 Projm ( a V (
where Projm is the projection operator onto II and o₁ > 0 is the step size.
4

---

Policy Gradient for Robust Average-Reward MDPs
When chosen appropriately, the sequence {6:)20 effec- tively reduces the computational burden while maintaining global convergence. This adaptive tolerance sequence, in- spired by previous work on robust discounted MDP algo- rithms (Ho et al., 2021; Wang et al., 2024a), accelerates policy updates during the initial stages. As a result, it leads to significantly improved performance, as demonstrated by our experimental results in Section 5.2.
tighter Lipschitz constants L4 O A) and bn = O(S), compared to I: O( D(vAS² and fx (AAS3) in the prior work. This significantly reduces the dependence on the sizes of state and action spaces.
Lemma 3.2 establishes the continuity properties of L ((T)), which provides a crucial foundation for proving the global convergence of RP2G. However, weak convexity alone can not provide guarantees for convergence to a global optimum. Following classic results from stochastic approximation and optimization (Beck, 2017: Ostrovskii et al., 2021), Algo- rithm is expected to converge to stationary points only.
It is worth emphasizing that RP2G relies only on first-order information V (TT, P) to solve (5). Since Pt is fixed, this gradient is identical to the one used in ordinary AMDPs (Sut- ton & Barto, 201 8); that is,
Recent work (Agarwal et al., 2021; Bhandari & Russo, 2024) shows that policy gradient methods achieve global conver- gence in discounted MDPs under the gradient dominance condition, which ensures the gradient does not vanish pre- maturely. Informally, a function h(x) satisfies this condition if h(x) - h(x*)) = ((G())) where G(.) is a measure of the gradient of and x is the global optimum of h.
(TT d Ts0 0T
As a result, the non-difierentiabiliyy of V (T)) does not hinder the implementation of RP2G.
3.2. Global Convergence Analysis
Although Ti is non-smooth, weakly convex problems nat- urally admit an inherent smooth approximation through the Moreau envelope (Davis & Drusvyatskiy, 2019; Mai & Johansson, 2020). Extending the concept of gradient dominance, we introduce the gradient of the Moreau enve- lope and establish a tailored gradient dominance condition satisfied by V, as presented in the following theorem.
In this subsection, we provide a convergence analysis of RP2G. In particular, we first leverage the sensitive anal- ysis technique from (Cheng et al., 2024) to establish the weak convexity of non-convex, non-differentiable objective function V. We then derive a tailored gradient dominance property for V in Theorem 3.4, which quantifies the gap between the function value and its optimum. Finally, we present the global convergence result in Theorem 3.5.
Theorem 3.4. Let nt" be the globally optimal policy for RAMDPs. For any policy the following holds:
The following lemma establishes analytical bounds on the differential sensitivity of differential value functions, which are essential for proving continuity and convexity properties.
(TT)) ((TT) S (MVSA+
I.m
|| 1/2e (Tr)
26
Lemma 3.1. (Policy Sensitivity Bounds for Average- Reward MDPs) For any policies π, n' E II, transition kernel p E A BYSSA and state S, the following bounds hold:
where ( is the Moreau envelope of (TT).
To derive this result, we introduce the distribution mis- match coefficient between two stationary distributions |d" which is often assumed to be bounded in prior works average reward problems (Wang et al.,
PT d=' pl < Cā
π π²' 112,00
[((T.)) p) J(TT', p) S CJ
π π 1110001
2023c; Kumar et al., 2024b; Sun et al., 2024), denoting as M := SUPT,m .ppp' 1/d"
-T - J² .Pl x < C_]
π π |1,,001
|lx0 < co.
11 मं pl < C π - π 111000
Theorem 3.4 shows that any first-order stationary point of the Moreau envelope corresponds to an approximately glob- ally optimal policy. Building on this foundation, we now present a theorem that guarantees global convergence.
Due to page limit, the proof of this lemma, along with all remaining results, is provided in the appendix. Appendix A also includes table that define all parameters. Using these sensitivity bounds, the weak convexity of the objective func- tion (T)) can be established.
Theorem 3.5. Let To be the policy produced by Algo- rithm 1. With constant step size := 1/VT and an initial tolerance do S VT, we have
Lemma 3.2. The objective function (TT.P) P) in (2) is L Lipschitz and -m-sooot in π, implying that the robust ob- jective (TT) ) is ---weakly convex and -ipLiscchi.. Remark 3.3. Similar continuity results for AMDPs with re- spect to π were recently established in (Kumar et al., 2024b). Our analysis improves upon these results by providing
(TT))) min (TT)) S c,
Hell
where T is chosen such that
Lx (MVSA
26 ( 46
2l 12
4 1
2
1-7
T
=0(E
e
5

---

Policy Gradient for Robust Average-Reward MDPs
At high level, our proof of Theorem 3.5 first invokes standard analysis of nonconvex stochastic subgradient de- scent (Davis& & Drusvyatskiy, 2019) to analyze the number of iterations that is needed for computing solution with suf- ficiently small Moreau envelope gradient. Building on this, the gradient dominance property established in Theorem 3.4 allows us to complete the proof. Note that the guarantee we provide for the e-global optimum found within ( +) iterations, consistent with other GDA convergence results that apply the two-timescale rule in non-convex minimax optimization (Daskalakis et al., 2020; Jin et al., 2020).
Algorithm 2 Projected gradient ascent for solving the worst-
case transition kernel
Input: current policy æ, initial kemel Pu, iteration num- ber K, step size sequences (Bx)x20 for k = 0, 0,l,..... K do
Update Pa-1 t (Po + BR V
end for
Output: Pk- E (po....,PPk' PK-1) such that J(T, pk=) =
max (0((0...K11)) (
The global convergence of RP2G hinges on an inner loop that identifies one worst-case transition kernel for a given policy π. However, this computation is not trivial, as methods for evaluating the worst-case transition remain of RAMDPs largely unexplored. To address this challenge, we propose several tailored gradient-based algorithms for the inner maximization under different ambiguity assumptions.
Note that with the policy is being fixed, the transition kernel evaluation could be regarded as constrained non- concave maximization problem. From standard optimiza- tion analysis, a smooth function ensures that small gradi- ent ascent updates improve the objective value (see Ap- pendix B.2). To establish the required smoothness con- ditions, we first derive relevant sensitivity bounds for the transition kernel, as stated in the following lemma.
4. Worst-Case Transition Evaluation
Lemma 4.2. (Adversary Sensitivity Bounds for Average- Reward MDPs) For any transition kernels P1-P2 E (A (ASYSxA, policy π E 11, and state-action pair (s,a) E S x A, the following sensilivity bounds are established:
As yet, we have outlined RP2G and established its global convergence, assuming the worst-case transition kernel is computable. In this section, we focus solving the inner maximization problem,
1d d d.
P2
< Cj c1 P2 P2|11,00
(T)
= max ((TPP), PEP
[J - - P2)
S CJ] PP P2 1,
- y 1000
S CP [P] P2 p2|11,000
referred to as the worst-case transition evaluation problem, by developing two gradient-based solution methods. No- tably, the convergence results in Section 3 are independent of the inner evaluation method. We begin by deriving key properties of the inner evaluation problem in Section 4.1. Subsequently, Section 4.2 and Section 4.3 introduce and analyze tailored gradient- braddeen-bbsedd algorithms designed for rect- angular and general ambiguity sets, respectively.
g - gh P2
1l S CP PP P2 121|1,00
Using the result of sensitivity bounds, we can obtain the continuity of the transition evaluation problem, showing the Lipschitz continuity and smoothness.
Lemma 4.3. The objective function J(T.)) p)) in (2) is Li- Lipschitz continuous and ep-smooth with respect to p.
4.1. General Properties
4.2. Rectangular Ambiguity Sets
In general, the worst-case transition evaluation can be inter- preted as an adversarial nature maximizing decision maker's average cost by selecting proper transition kernel from the ambiguity set P (Lim et al., 2013; Goyal & 2023). To apply the gradient-basee based update on the transi- tion kernel, we introduce the following lemma to derive the gradient of the evaluation problem.
Under the common rectangularity assumption on the ambi- guity set (lyengar, 2005; Nilim & Ghaoui, 2005; Wiese- mann et al., 2013), Algorithm 2 is proposed as first maddeent-based method solve the worst-case transition evaluation problem with guarantee of global convergence. To maximize J(T,P) p) over p. Algorithm 2 iteratively per- forms the projected gradient update on p:
Lemma 4.1. (Adversary's 's Policy Gradient) For any policy E II and transition kernel p E (AS),xA, the gradient of J (TT over p has the analytical form as follows:
pk+1 PPojo Ba V J (T.
which depends on the explicit form of P. Given the specific structure of rectangularity, this projected gradient update can be further decoupled to multiple projection updates across (s, a)- s-tuple: for (s, --reetangula RAMDPs, we have for any S,
aJ(Tp))
Opeas' JT..P. Taa" (Ceus' J(TT, + P),
where gaor == Ceas' - -(TT p) + uT is referred to as the differential action-next-stun state value function (Li et al., 2023; Wang et al., 2024b).
Pk+1.sa = Projp... (P + B& p... J(T Pk));
6

---

Policy Gradient for Robust Reward MDPs
whereas for s-rectangular RAMDPs,
Algorithm 3 Projected Langevin dynamics for solving the
worst-case transition kernel
Ph+1, = Proje, (Pa.. + 8x J..
Input: current policy æ, initial kernel pu, Gibbs parame-
Since s-rectangularity is more general compared to (s, a)- rectangularity, our analysis is primarily based on the s- rectangular ambiguity set. However, our results readily extend to the (s, rectanguul case.
ter À > 1, step size v > O, iteration number K for k = 0, o,.,..... K do
Sample wh+11 ~ NN (A55)x(ASP))
2n X
Set Ps: - Pk + V ( Pr. +
WK+1
Due to the non-convex nature of J, the smoothness prop- crty established in Lemma 4.3 alone is insufficient to ensure global convergence. To address this, we derive the following specialized gradient dominance condition for the evaluation problem, which provides the foundation of our global con- vergence guarantee.
Update Pa-1 arg min ||p pkll;
pEP
end for
where À >>> is the temperature parameter. Sampling from is of interest because it converges weakly to the uniform distribution over the global maxima of J(T,, P) as X + oo (Hwang, 1980). Notably, the compactness of P and the continuity of [TT p) ensure the denominator remains finite.
Theorem 4.4. (Adversary's 's Gradient Dominance) When the ambiguity set P is s-reciangular, for any π E II, we have,
PEP p(H - J(T,P) S max (p- P. D p)),
Building on the insights for the above Gibbs distribution Vx+ employ the discrete-time Langevin diffusion to generate samples from the Gibbs distribution, as outlined in Algo- rithm 3. At each iteration k, Algorithm 3 iteratively applies the projected gradient ascent step perturbed by Gaussian noise to update the transition kernel:
where p" be one of worst-case transition kernel over n, i.e., p' E arg maxpep J (TT,p).
The above lemma ensures that any stationary point of J(H,p) p) is globally optimal. By leveraging the above re- sult, estabilish the convergence rate of Algorithm 2.
2n PE++ = Projp Pk: + V (T. +
wk Wk+1 )
Theorem 4.5. Let Pk- be the output of Algorithm 2 and
X
5n > O be the precision. Then, for s-rectangular RAMDPs, Algorithm 2 with constant step size B = 1/tp satisfies
After K iterations, the output px follows distribution VK that approaches P/ within the 1-Wasserstein distance (Lam- perski, 2021).
max Jp(TT.P) p) JJ(TT.PPP S 8 PEP
Theorem 4.6. Assume n 1/2. 8n 0 and E (0. 1). Then, there exist positive constants a > 4, b > 1, and c1, C1,02, C3 > O such that X 2 ci (2AS (ct (1 - x)) and K 2 max(4, C2 exp{ A S | }. the distribution Vk of the output Pk of Algorithm satisfies Epwex [J(T.P) p)] Z maxpep J(T. p) 8n.
whenever
321 M 2
K
82
4.3. General Ambiguity Sets
While (s, a)- and s- rectangularity assumptions simplify the inner maximization problem due to the independence among state-action pairs (and states), many practical sce- narios involve general ambiguity where such independence no longer holds (Wiesemann al., 2013; Li et al., 2023), resulting in more challenging optimization landscape.
Theorem 4.6 establishes that the number of iterations re- quired to achieve a 5n -ptomti inner solution grows expo- nentially with the dimension A of the transition kemel and with the number of desired accuracy digits, log(1/s)). While the complexity may appear high, this algorithm is the first general approach capable of addressing the worst-case transition evaluation problem for general RAMDPs.
To tackle this challenge, we draw insprition from (Lamper- ski, 2021; Li et al., 2023) and extend our discussion to pro- pose a new tailored Markov Chain Monte Carlo algorithm designed for the general evaluation problem with probabilis- tic global optimality guarantees. Specifically, for the worst- case evaluation problem, we consider J (TT, p): P + R and the following relevant Gibbs distribution:
5. Numerical Experiments
We now demonstrate the convergence and robustness of RP2G, along with the two proposed inner solution methods, on the standard benchmark, GARNET MDPs (Archibald et al., 1995). All results were generated on an Apple M2 Max with 32 GB LPDDRS memory. The algorithms are implemented in Python 3.1 1.5,, and we use Gurobi 1 11.0.3
(Txp())(TT)))dd
(B) = Jo (x (T)
7

---

Policy Gradient for Robust Average- MDPs
3,4)
Robust
3
5,44
Non-robust
C115, 6)
2-
Relative
Wlm)
1
0
50
100
150
200
250
50
100
150
200
250
300
Number of iterations
Number of iterations
Figure The relative difference of objective values computed by RP2G and RVI for Garnet problems with different sizes.
Figure 2. Performance comparison RP2G and non-robust PG on Garnet problems with ellipsoid general ambiguity sets.
to solve any linear optimization problems involved. To support reproducibility, the full source code used to gener- com/
solutions. For this comparison, the worst-case transition evaluation problem in RPMD to fixed value å = 10-5, whereas RP2G uses decreasing sequence initialized at 6o = with a decay rate of r 0.95. For each problem size, we run 30 instances and report the average runtimes and standard deviations in Table 1, with termination based on minimal changes in the objective (i.e.. J (rtc)--p++)-J( P:)ll S 10-A). The results indicate that RP2G, leveraging the decreasing tolerance sequence, significantly outperforms RPMD in runtime efficiency.
the tolerance of
ate the results is available at AMDP. Additional information on the benchmark and experimental setup is given in Ap- pendix E.
5.1. Rectangular RAMDPs
We validate the convergence of RP2G random GARNET MDPs across varying problem sizes with (s, a rectangular ambiguity. For each size, we generate 50 instances and com- pare the objective values of RP2G at different iterations with the optimal values J computed using the robust value iter- ation method from (Wang et al., 2023c). Figure illustrates how the relative error (i.e., ( Pt) J') decreases consistently the number of iterations increases, demon- strating the convergence and optimality of our algorithm. The upper and lower envelopes of the curves correspond to the 95 and percentiles of the 50 samples, respectively.
5.3. General RAMDPs
In this experiment, implement RP2G using the general inner solution method (Algorithm 3). We consider an ellip- soidal ambiguity set P (Li et al., 2023). which is not neither (s, a) rectanguua nor s-rectangular:
p = (p: (p (p-pp-)) D) E (p- sr.
with size parameter r > 0, Hessian matrix Σ, and nom- inal transition kernel p. To evaluate RP2G's robustness, we compare against the non-robust policy gradient (PG) method, which optimizes under the nominal model. We apply both methods to 20 sample problems, recording v (TT) maXpep J (TT, p) for policies generated by RP2G and PG, respectively, at each iteration t. As shown in Fig- ure 2, RP2G achieves robust performance and converges under general ambiguity. The shaded regions indicate the range between the and 95 percentiles over the 20 samples.
5.2. Runtime Comparison
We now conduct experiment GARNET MDPs with (s, c)-rectangular ambiguity to assess the impact of the de- creasing tolerance sequence h22 on the computational efficiency. Specifically, we compare RP2G with the only existing gradient-bast based method, robust policy mirror de- scent (RPMD) (Sun al., 2024), which assumes exact inner
Table Average runtimes and standard deviations (in seconds) comparison of algorithms.
6. Conclusion
Problem Size
RPMD
RP2G
In this paper, we proposed RP2G, a novel policy optimiza- tion algorithm for solving RAMDPs with general ambiguity sets. RP2G ensures global convergence under mild condi- tions by incorporating suitable step size and an adaptive
3,3 G(10,5,5
13.99(13.05)
0.63(0.35)
532.64(356.8A4 2711.79(849.00)
2.48(0.90)
G(15, 10, 6)
12.54(3.85)
8

---

Policy Gradient for Robust Average-Reward MDPs
tolerance sequence. Additionally, we conducted the first study the inner worst-case transition evaluation problem, developing gradient-based solution methods in both rectan- gular and more general settings. Experiments validate the global convergence of RP2G, its efficiency, and robustness compared to non-robust approaches. Future work could explore extensions to scalable, model-free algorithms.
Beck, A. First-order methods in optimization. SIAM, 2017.
Bertsekas, D. Dynamic progrumming and optimal control:
Volume I, volume 4. Athena scientific, 2012.
Bertsekas, D. P. Nonlinear Programming. Athena scientific, 3rd edition, 2016.
Bhandari, J. and Russo, D. Global optimality guarantees for policy gradient methods. Operations Research, 2024.
Acknowledgements
We thank our friend Min Cheng for her helpful insights on deriving the sensitivity bounds. This work was supported, in part, by UHK Start-Up Grant (Project No. 9610481) and the Research Grants Council of Hong Kong (General Research Fund, Project No. 11508623). This work was also supported, in part, by NSF grants 2144601 and 2218063.
Chae, W. Hong, K., Zhang, Y., Tewari, A., and Lee, D. Learning infinite-horizon average-reward linear mixture mdps of bounded span. arXiv preprint arXiv:2410. 14992, 2024.
Chen, Z. C.,, Li, J., Yuan, A., Gu, Q., and Jordan, M. I. A general framework for sample-efficient function ap- proximation in reinforcement learning. In International Conference on Learning Representations (ICLR), 2023.
Impact Statement
This paper focuses on theoretical aspects of Machine Learn ing. There are no new socictal impacts that we can identify.
Cheng, M., Zhou, R., Kumar. P., and Tian, C. Provable policy gradient methods for average-reward markov po- tential games. In International Conference Artificial Intelligence and Statistics, pp. 4699-4707, PMLR, 2024.
References
Abbasi- Yadkori Y.. Bartlett, P., Bhatia, K., Lazic, N., Szepesvari, C., and Weisz, G. Politex: Regret bounds for policy iteration using expert prediction. Interna- tional Conference on Machine Learning, pp. 3692-3702. PMLR, 2019.
Cover, T. M. and Thomas. J. A. Elements of Information Theory. John Wiley & Sons, 2012.
Daskalakis, C., Foster, J., and Golowich, N. Independent policy gradient methods for competitive reinforcement learning. Advances in neural information processing systems, 33:5527-5540, 2020.
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, 2001.
Davis, D. and Drusvyatskiy, D. Stochastic model-based minimization of weakly convex functions. SIAM Journal on Optimization, 29(1):007-239, 2019.
Agarwal, A., Kakade, S. M., Lee, J. D., and Mahajan, G. On the theory of policy gradient methods: Optimality. approximation, and distribution shift. Journal of Machine Learning Research, 22(98)) 2021.
Drusvyatskiy, D. and Paquette, C. Efficiency of minimiz- ing compositions of convex functions and smooth maps. Mathematical Programming, 178:503-558, 2019.
Archibald, T., McKinnon, K., and Thomas, L. On the generation of Markov decision processes. Journal of the Operational Research Society, 46(3):354-361, 1995.
Gagniue, A. Markov chains: from theory to implementa- tion and experimentation. John Wiley & Sons, 2017.
Avrachenkov, K. E. and Borkar, V. Whittle index based q-learning for restless bandits with average reward. Auto- matica, 139:1 10186. 2022.
Ganesh, S., Mondal, W. U., and Aggarwal, V. Variance- reduced policy gradient approaches for infinite horizon average reward markov decision processes. arXiv preprint arXiv:2404.02/08. 2024.
Bai, Q. Mondal, W. U.. and Aggarwal, V. Regret analysis of policy gradient algorithm for infinite horizon average reward markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 38, pp. 10988- 2024.
Ghadimi, S. and Lan, G. Accelerated gradient methods for nonconvex nonlinear and stochastic programming. Mathematical Programming, 156(1):59-99, 2016.
Gong, H. and Wang, M. A duality approach for regret minimization in average-award ergodic markov decision processes. In Learning for Dynamics and Control, pp. 862-883. PMLR, 2020
Bäuerle, N. and Rieder, U. Markov decision processes with applications to finance. Springer Science & Business Media, 2011.

---

Policy Gradient for Robust Average-Reward MDPs
Goyal, V. and Grand-Clement, J. Robust markov decision processes: Beyond rectangularity. Mathematics of Oper- ations Research, 48(1):203-226, 2023.
Levin, D. A. and Peres, Y. Markov chains and mixing limes, volume 107. American Mathematical Soc., 2017.
Li, M., Sutter, T., and Kuhn, D. Policy gradient algorithms for robust mdps with non-rectangular uncertainty sets. arXiv preprint arXiv:2305. 19004, 2023.
Grand-Clement, J., Petrik, M.. and Vieille, N. Beyond discounted returns: Robust markov decision processes with average and blackwell optimality. arXiv preprint arXiv:23 2023.
Li, Y., Zhao, T., and Lan, G. First-order policy optimiza- tion for robust Markov decision process. arXiv preprint urXiv:2209. 10579, 2022.
Grosof, I., Maguluri. S. T., and Srikant, R. Conver- gence for natural policy gradient on infinite-state average- reward markov decision processes. arXiv preprint arXiv:2402.05274, 2024.
Liao, P., Qi. Z.,, Wan, R., Klasnja, P., and Murphy, A. Batch policy learning average reward markov decision processes. Annals of statistics, 50(6):3364, 2022.
Ho, C. P., Petrik, M., and Wiesemann, W. Partial policy iteration for 11 11-robust Markov decision processes. Journal of Machine Learning Research, 22(275):1 2021.
Lim, S. H., Xu, H.,, and Mannor, S. Reinforcement learning in robust markov decision processes. Advances in Neural Information Processing Systems, 26, 2013.
Hwang, C.-R. Laplace's method revisited: weak conver- gence of probability measures. The Annals of Probability, pp. 1177-1182, 1980.
Lin, T., Jin, C., and Jordan, M. On gradient descent ascent for canconveex-concaye minimax problems. In Interna- tional Conference on Machine Learning, pp. 6083-6093. PMLR, 2020.
Iyengar, G. N. Robust dynamic programming Mathematics of Operations Research, 30(2)257-220, 2005.
Jin, C., Netrapalli, P., and Jordan, M. What is local opti- minimax optimization?
Lin, Z., Xue, C., Deng, Q., and Ye, Y. A single-loop ro- bust policy gradient method for robust markov decision processes. arXiv preprint arXiv:2406.0022
mality in In International Conference on Machine Learning, pp. 4880 4889. PMLR, 2020.
2024.
Luo, L.,, Ye, H., Huang. Z., and Zhang, T. Stochastic re- cursive gradient descent ascent for stochastic nonconvex- strongly-concave minimax problems. Advances in Neural Information Processing Systems, 33:20566-20577, 2020.
Kaufman, D. L. and Schaefer, A. J. Robust modified policy iteration. INFORMS Journal on Computing. 25(3):396 410, 2013.
Kober, J., Bagnell, J. A., and Peters, J. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research, 32(11):1238-1211 2013.
Mai, and Johansson, M. Convergence of a stochastic gradient method with momentum for non-smooth non- convex optimization. In International conference chine learning, pp. 6630-6639, PMLR, 2020.
Kruger, A. Y. On fréchet subdifferenttiass. Journal of Math- ematical Sciences, 116(3):335--358, 2003.
Mannor, S., Mebel, O., and Xu, H. Robust mdps with k-rectangular uncertainty. Mathematics of Operations Research, 41(4):1484-1509 2016.
Kumar, N., Derman, E., Geist, M., Levy, K. Y., and Mannor, S. Policy gradient for rectangular robust markov decision processes. Advances in Neural Information Processing Systems, 36, 2024a.
Marbach, P. and Tsissiklis, J. N. Simulation-based optimiza- tion of markov reward processes. IEEE Transactions on Automatic Control, 46(2):191-209 2001.
Kumar, N., Murthy, Y., Shufaro, I., Levy, K. Y., Srikant, R., and Mannor, S. On the global convergence of policy gradient in average reward markov decision processes. arXiv preprint arXiv:2403. 066006, 2024b.
Meyn, S. P. and Tweedie, R. L. Markov chains and stochas- tic stability. Springer Science & Business Media, 2012.
Lamperski, A. Projected stochastic gradient langevin algo- rithms for constrained sampling and non-convex learn- ing. In Conference on Learning Theory, pp. 2891-2937. PMLR, 2021.
Mnih, V. Playing atari with deep reinforcement learning. arXiv preprint arXiv: 2013.
Murthy, Y. and Srikant, R. On the convergence of natural policy gradient and mirror descent-like policy methods for average-reward mdps. In 2023 62nd IEEE Conference on Decision and Control (CDC), pp. 1979-1984, IEEE, 2023.
Le Tallec, Y. Robust, risk-sensitive, and data-driven control of Markov decision processes. PhD thesis, Massachusetts Institute Technology, 2007.
10

---

Policy Gradient for Robust Average-Reward MDPs
Nilim, A. and El Ghaoui, L. Robust control of Markov decision processes with uncertain transition matrices. Op- erations Research, 53(5):780-798, 2005.
Thekumparampil, K. K., Jain, P., Netrapalli, P., and Oh, S. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 32, 2019.
Norris, J. R. Markov chains. Number Cambridge univer- sity press, 1998.
Wan, Y. and Sutton, S. On convergence of average-reward off aff-policy control algorithms in weakly communicating mdps. arXiv preprint arXiv:2209. 15141, 2022.
Nouiched, M., Sanjabi, M., Huang, T., Lee, J. D., and Raza- viyayn, M. Solving class of non-convex min-mat max games using iterative first order methods. Advances in Neural Information Processing Systems, 32, 2019.
Wan, Y., Naik, A., and Sutton, R. S. Learning and planning in average-reward markov decision processes. In Inter- national Conference on Machine Learning, pp. 10653-
Ostrovskii, D. M., Lowy, A., and Razaviyayn, M. Efficient search of first-order nash equilibria in monconvex-concan smooth min-max problems. SIAM Journal on Optimiza- tion, 31(4):2508-25 2538, 2021.
10662. PMLR, 2021.
Wang, J., Wang, M., and Yang, L. F. Near sample-optimal reduction- policy learning for average reward mdp. arXiv preprint arXiv:2212.0000 2.0000000..00 2022.
Panaganti, K. and Kalathil, D. Sample complexity of ro- bust reinforcement learning with generative model. 12X00:2122.015000 [cs, stat], 2021.
Wang. Q. Ho, C. P., and Petrik, M. Policy gradient in
robust mdps with global convergence guarantee. In In- ternational Conference on Machine Learning, pp. 35763- 65797.PMLR, 2023a.
Pesquerel, F. and Maillard, O.-A. Imed-rl: Regret optimal learning of ergodic markov decision processes. Advances in Neural Information Processing Systems, 35:26363- 26374, 2022.
Wang, Q. Xu, S., Ho, C. and Petrick, M. Policy gradient for robust markov decision processes. arXiv preprint arXiv:2410.221 14, 2024a.
Puterman, M. I.. Markov decision processes: discrete
stochastic dynamic programming. John Wiley & Sons, 2014.
Wang. S., Blanchet, J., and Glynn, P. Optimal sample complexity for average reward markov decision processes. arXiv preprint arXiv:2310.0885 2023b.
Razaviyayn, M., Huang, T., Lu, S., Nouiched, M., Sanjabi, M., and Hong. M. Nonconvex min-max optimization: Applications, challenges, and recent theoretical advances. IEEE Signal Processing Magazine, 37(5):55-66) 66, 2020.
Wang. Y. and Zou, S. Policy gradient method for robust reinforcement learning. In International conference on machine learning, pp. 23484-23526 PMLR, 2022.
Rockafellar, R. T. Monotone operators and the proximal point algorithm. SIAM journal on control and optimiza- fion, 14(5):877-898, 1976.
Wang. Y., Velasquez, A., Atia, G., Prater-Bennette A., and Zou, S. Robust average-reward markov decision pro- cesses. In Proceedings of the AAAI Conference on Artifi- cial Intelligence volume 37, pp. 15215-15223, 2023c.
Rockafellar, R. T. and Wets, R. J.-B. Variational analysis, volume 317. Springer Science & Business Media, 2009.
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-36466 PMLR, 2023d.
Shechter, S. M., Bailey, M. D., Schaefer, A. J., and Roberts, M. S. The optimal time to initiate hiv therapy under ordered health states. Operations Research, 56(1):20-33, 2008.
Wang, Y., Velasquez, A., Atia, G., Prater-Bennette. A., and Zou, S. Robust average-reward reinforcement learning. Journal of Artificial Intelligence Research, 80:719-803 2024b.
Sun, Z., He, S., Miao, F., and Zou, S. Policy optimization for robust average reward mdps. In The Thirty-eighuh Annual Conference on Neural Information Processing Systems, 2024.
Wei, C.-Y., Jahromi, M. J., Luo, H., Sharma, H., and Jain, Model-free reinforcement learning infinite-horizon average-reward markov decision processes. In Interna- tional conference machine learning, pp. 10170-10180. PMLR, 2020.
Sutton, R. S. and Barto, A. G. Reinforcement learning: An introduction. MIT press, 2018
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.
Wei, C.-Y. Jahromi, M. J., Luo, H., and Jain, R. Learning infiiit-horizon average-rewant mdps with linear function

---

Policy Gradient for Robust Seerage--Rewake MDPs
approximation. In International Conference on Artificial Intelligence and Statistics, pp- 3007-3015. PMLR, 2021.
Wiesemann, W., Kuhn, D., and Rustem, B. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153-183,22 2013.
Wu, F., Ke, J., and Wu, A. Inverse reinforcement learning with the average reward criterion. Advances in Neural Information Processing Systems, 36, 2024.
Wu, Y., Zhou, D., and Gu, Q. Nearly minimax optimal regret for learning mufnite-horizon average-reward mdps with linear function approximation. In International Con- Serence on Artificial Intelligence and Statistics, pp. 3883- 3913. PMLR, 2022.
Yang. S., Gao, Y., An, B., Wang, H., and Chen, X. Efficient average reward reinforcement learning using constant shifting values. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 30, 2016.
Yang, X., Hu, J., and Hu, J.-Q. Relative q-learning for average-reward markov decision processes with contin- uous states. IEEE Transactions on Automatic Control, 2024.
Zhang, J., Xiao, P., Sun, R., and Luo, Z. A single- loop smoothed gradient descent-ascent algorithm for nonconvex-concant min-max problems. Advances in Neural Information Processing Systems, 33:7377-7389, 2020.
Zhang, S., Wan, Y., Sutton, R. S., and Whiteson, S. Average- reward off- oif-policy policy evaluation with function approxi- mation. In international conference on machine learning, pp. 12578-12588. PMLR, 2021.
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.
Zhang, Z., Ji, X., and Du, S. Horizon-free reinforcement learning in polynomial time: the power of stationary policies. Conference on Learning Theory, pp. 3858- 3904. PMLR. 2022.
Zipkin. P. Foundations of Inventory Management. McGraw-Hill sumpanies,Incorporatee 2000. ISBN
9780256113792 URL https: /books..... google. com. hom.hh/bbootss.err220000....
12

---

Policy Gradient for Robust Average-Reward MDPs
A. Table of constants needed in analysis
restate table of constants and their description in this appendix for the sake convenience.
Definition
Remark
fiix
Uniform bound on the mix time (See Definition B.2)
mix
C
=ax | pa + 1
See Definition A.1
CT
mix
Sensitive bound d w.r.t.
CT
mim
Sensitive bound on [TT, P) w.r.t.
C
2C' + + C7C
Sensitive bound on = w.r.t. π
CT
CJ + C
Sensitive bound on qT w.r.t. π
L
Timi VA
Restricted Lipschitz constant w.r.t. π
t
ACT + 28 CJ
Restricted gradient Lipschitz constant w.r.. (Smoothness)
CR
2 + 5fmix
Sensitive bound on d w.r.t. p
C
2 + 5mmix
Sensitive bound on J p) w.r.t. P
CF
20' + CSCC + C² C2SC
Sensitive bound on TTP w.r.t. p
C
C CP
Sensitive bound on qT w.r.t. p
Lx
(2 5lmixx V5
Restricted Lipschitz constant w.r.t. p
4CP + 4(2 + 5tmix) S
Restricted gradient Lipschitz constant w.r.t. (Smoothness)
Table 2. Constants
Definition A.1. [(Wang et al., 2023c; Cheng et al., 2024)] For any policy ग Il and transition kernel p E P, the matrix (I-Pa + pT,00) is invertible (Puterman, 2014). We define
:= max PEP
|| p + p
B. Auxiliary Lemmas
B.1. Definitions and Properties of Ergodic Average-Reward Markov Decision Process
At the beginning, consider the differential vate- function and provide useful results. As add the constraint
Σ. d PuT.P 0, the differential value function takes the following form:
J. : ET
Σ
(co.aseun - J(TT
(p)(())
C
where c Ea-m,,s' s' [Cans]] is defined the state cost, and ( C (ASYS is denoted the 1-step transition matrix induced by and p. where for t 1.
Σ pa (t-1) pn s'gn,
p Σ ssaPaas
Then, we can obtain the analytical form of the differential state-value function.
13

---

Policy Gradient for Robust Average-Reward MDPS
Lemma B.1 (Analytical Form of Value Function (Puterman, 2014)). Let pa -im + Et= pm,t; be the limit
matrix, where each corresponds the stationary distribution d Then, we obtain closed-form expression, for the differential value function:
TT = -I- + p=.,00--((I - -r
Then, we introduce crucial definition that benefits our further analysis. Under the assumption of ergodicity, a finite mixing time is guaranteed and defined as follows (Levin & Peres, 2017; Wei et al., 2020):
Definition B.2 (Mixing time). The mixing time of ergodic MDP with respect to policy and transition kernel is defined as
== min t2 1
Vs E =
R.P
pmm(0
-m
$ 4
(8)
mix
where P.T((0) the s-th row of the t-step transition matrix.
For analytical convenience, we define the upper bound on the overall mixing time mmix ma 1. This represents the maximum time, across all policies and transition kernels, required for the state distribution to be within 1/4 of the stationary distribution.
Lemma B.3. (Policy performance difference lemma) For any π, x
II and p (AS)SXA, have
(.t.))-[(T'p))) J(T''p) = Σ
-
d Σ
(Tsa
Tea)
Isa
x'
(9)
aES
aEA
Proof of Lemma B.3. Using Bellman equation the differential action value function, we have
Σ d
Σ d
Σ Peas'
(Cons- J(T'' .p) + T &
T.
2
-( J (T' p) + Σ
Σ P
TaaPaae
J(T,p) J( p) + Σ
n
5¹
J(Z, p) + Σ
TT
o sa x
Eo Tea Eg Coas and d where the second equality is obtained by using the fact that J(T.P) E, d
Σ. dT.P La ssaPsast
Lemma B.4. (Bounds for differential value functions) For ergodic MDP satisfying Assumption 2.1 with any π Il and E (A A)SAA we have for any 8 E S, a E A.
10 T. <
5lmies
and
T.P S
Tm
14

---

Policy Gradient for Robust Average-Rewand Reward MDPs
Proof of Lemma B.4. By the identity u.P satisfies, have
1
P
p 2o'
d..))
p.p
t=0
s'
p
d 1TT 100
1=
Mmm
20
(++1)am
| d
P.
dm.Pll
00
$ mimix
+
2
2. 2- mii
5b
where the penultimate equality is obtained by applying Corollary 13.1 of (Wei et al., 2020). Therefore, also obtain
Doas' (Ceas! - -(TT + up
Psast Csas' +
Σ
Panss J (T.
+
Σ Psas o.
8¹
8¹
< + 1 + 5tmix
< 7fmix:
where we bound the average reward objective as
[T p)l
[E of [cearr]
S
It is worth noting that, the original upper bound result of the differential action value function in (Wei al., 2020) missed the bound of the objective. It is worth noting that, the original upper bound result of the differential action value function in (Wei et al., 2020) missed the bound of the objective. Here, we revise the original result to the current new one.
Here we include the result showing the form of gradient over π for the sake of completeness.
Lemma B.5. For any policy π E II and transition kernel E (AS)SXA, the gradient of J (TT over a has the analytical form as follows:
0J(T, P) d= TTP
iTsa
Proof of Lemma B.5. We now derive the form of partial derivative sa obtain (6). Note that for any 8 E S, the gradient of the differential value function can be written as
SUZ.P
Σ
wan 4
T-P
OTaA
TTa
0g..P
Σ
+ Taa
OTaA
Oris Usa + waa
i
Σ
Poas' (Csas' [ p)) + T.P)
Urssa
Jnsa
Owe Asa
@J(T.P)
Ov
Σ
Oreaa
+ Raa
Oraa
Σ
Pans' Iisa sa
15

---

Policy Gradient for Robust Average-Reward MDPs
Multiplying each side with dr.P, taking the summation over E S, and rearranging terms, obtaín
@J(
Oug
dus
Σ
d=
Isa
+
Tea
Σ
Psad'
UTa
no
du T
OuT. Oea
Σ
d
Isa
Σ d.
Σ
Nsa
Psas'
Σ dg
Σ
d
d= 45h
R.P
pt sà
By introducing the distribution mismatch coefficient between two stationary distributions
d 1
and
M
d
supa, p...
d11
d22:P2
oC, we can reach the gradient dominance condition that AMDPs satisfy.
Lemma B.6. (Policy Gradient Dominance (Kumar et al., 2024b)) For any P E (AS)SXA, we let x be one of optimal policies over p. ie., n² E arg min [ p). then we have,
J(H J(TT, p) S M max n,, V ( p)). REll
(10)
Proof of Lemma B.6. By the policy difference performance lemma (Lemma B.3), we have for any π E 11 and E P, we have
J( p) - J(x.P)
Σ
de p
Σ (
Tsa)
Isa
T.P.
aEA
Then, obtain that
$ J p) - J( = Σ
(T
T
$ES
aEA
P
T.. P
Taa T quo
d p
aEA
n" P
T..
max
Too
de P.
#. Ell,
8ES
aEA
d
max Ell
Toe0 T.P
d..p ip
#ES
aEA
M max
{
V (TT,
#ell
where the inequality (a) obtained due to
J(H,P) - J(xx" pp)2.
and Σ
(Tea - TTa). - 2 0, Vs E.
ae.A
B.2. Standard definitions and results optimization
In this subsection, we present some standard optimization definitions (Ghadimi & Lan, 2016; Beck, 2017), which are used in our work. Consider the following optimization problem
min h(x))
(11)
with X' being a nonempty closed and convex set and h: Rd + R being proper, closed and f-smooth. We first introduce the crucial definitions of smoothness and Lipschitz continuity.
16

---

Policy Gradient for Robust Average-Reward MDPs
Definition B.7. A function h: X > IR is L-Lipschitz if for any #1, 22 X, have that [[(())) h(x2)))l S L||a; x2/l and E-smooth if for any æ1, 22 X, we have [[Vh(=1) Vh(==)] I ||| 21 Ø2
Another common definition need clarify is the indicator function. Definition B.8 (Indicator functions). For any subset X' Rd the indicator function of X' is defined to be the extended real-valued function given by
Ix(x)= = 0, x E X, 00, & X.
Definition B.9. The Fréchet sub-differential of function h X + R point X' is defined as the set dh(x) {u] lim inf h(x') h(x) (u, x' <))l|=' æi| 0).
Then, common lemma is provided to illustrate a basic property that smooth function satisfies. Lemma B.10. Let h: X > IR be E-smooth, then it is l-weakly convex function.
Proof of Lemma B.10. Let ((t) h(x + t(x' - z)), for any x, x' X. The following holds true
h(x) = r(0), and h(x') r(1).
Then, we observe that
h(x') - h(x) -((1) -1))-(()) S. vr(t)dt,
where
Vr(() Vh(x + 1(x' - x\) T2)) x))
We complete the proof as
[1(x²) h(z) Vh(z) - -z)l $ 1 Vr(t)dt (h())) - -0)
2 / |[V(() Vh(x) - x)] dt
Vh(r + 1(x' - x)) (0f - x)) - Vh(x) (ef - x)] de
<
- x)]ldt 11V/(x ((x' -x)) - vh(x)]l 1<''
< L nellEr =1 2
L E1ا1 =1
We present the standard optimization results from (Ghadimi & Lan, 2016; Beck, 2017) used our proofs. We then denote the optimal h value by h((=)). Definition B.11 (Gradient Mapping). The gradient mapping G (z) is defined as
G (x) (x - Projx 8Vh(z)))
(12)
where the operator Projx is the projection onto X. Theorem B.12. (Beck, 2017, Theorem 10.15) Let {wxh<20 be the sequence generated by the projected gradient descent algorithm for solving the problem (11) either with constant step size defined by B 1/2. Then
1. The sequence (h(#*) is non-increasing.
2. G (2x) - 0 as t
17

---

Policy Gradient for Robust Neeaad MDPs
3. (in. |G (2xe)l
20(h( (((h(()))h())))) T
Lemma B.13. (Ghadimi & Lan, 2016, Lemma 3) Let feerx==00 =I =G (x) S c. then
-Vh(x*) E (x 21)(
(13)
where Nx is the norm cone of the set X and B(r) fx E R | r
B.3. Moreau Envelope and its property
For smooth function h(z). a point æ E X' is defined as the first-order stationary point (FOSP) when 0 E ah(z). However, this notion of stationarity can be very restrictive when optimizing nonsmooth functions (Lin et al., 2020). In respond this issue, alternative measure of the first-order stationarity is proposed based on the construction of the Moreau envelope (Thekumparampil et al., 2019).
Definition B.14. For function h X -> and À > 0, the Moreau envelope function of h is given by
1 || - x''1"" h(x') + 2X
hx(x) = min z'EX
(14)
Definition B.15. Given an (-weakly convex function h, we say that x² an 6-first order stationary point (e-FOSP) if, [VVhyne<*"]] S C, where h 1 (a)) is the Moreau envelope function of h with parameter X 1/24.
The following lemma connects w-wekkly convex function and its Moreau envelope function and will be useful in our proofs. Lemma B.16. Suppose the function h: X C I + IR is f-weakly convex and may be not differentiable at any point. Then for each X < l:
1. The Moreau envelope function hx is C* -smooohhh with the gradient given by,
Vhi(w) x-1
x
arg min well
h((w) || w/l )
Meanwhile, by introducing 2 (x) == arg min h(w) + 1/2x || w|1 we have (|xx(x) x:1 = (x)]]
2. The inequality [[V)(=))]| < implies (xxx x=l de and Eg (z)) such that
1 (mx()))) x) S (x)(
1 ; | - -z0l B(1),
- E (x)() +
where (x((x(x)) defined as the normal cone of X at (x))) and B(r) fa E R" ||>||| S r). In particular, when X RR, we have that
|E||| _ 1 -11xx(00) - 211 = [V>x(>)]|
min (=))
Proof of Lemma 16 First, the analytical form of the Moreau envelope function's gradient is well-established by Proposi- tion 13.37 in (Rockafellar & Wets, 2009). Then, let us consider the optimality appearing in the definition of the Moreau envelope function. Define dx)y)) h(y) + (x - zx x - y1l². and then we notice that for any E IR", xx(x) is the
optimal solution of dz (y), which leads to
(x = min (x())
0 E 2 h(v) + -x(v) +
1
a - (x=l)l)) -
yERm
2
1
- &
+ (x(xa
(#)(x)) - x))
1
- E Nx
(+x(x) =)
(15)
18

---

Policy Gradient for Robust Average-Reward MDPs
The last inequality of 15 implies that, for any R"
(E + (0x(x) x), = +1(x)) 2
1 " (+x - -x), , - =x(x)), Vz R"
(-6,z - 2x(x))
(-,,2 - xx(x))) 1 x ((x(x)) - x|| 11|1 - -x)x))1 22 E R
(-,,= - - xx(x)) & > -|(x(())= - x||, Vz E R" || - 2x(2)) = 1,
which is our desired result. Specifically, while consider the case X' = R we have
1
(15) + π (ar xx(())) E ah(#),
which implies that
min (=))(xx(2))
|| 5 > [10x(0)) 2x = [[)]I
Based on the above properties of the Moreau envelope of weakly convex function, a small gradient [x)]] implies that æ is near some point (x)) that is nearly stationary for h. In the broader non-smooth setting, the norm of the gradient, [V)x())] has an intuitive interpretation in terms of year-stationarit for the target problem ((x) (Beck, 2017; Davis & Drusvyatskiy, 2019; Drusvyatskiy & Paquette, 2019).
B.4. Danskin's Theorem
We also need to introduce the following Danskin's ' Theorem, which helps prove our global convergence theorem.
Proposition B.17. (Bertsekas, 2016, Proposition B.25) Let Z C Rm be a compact set, and let h RR Z + RR be continuous function and such that h(,,z) z): I2n R. is convex for each Z. If hf, z) is differentiable for all Z and Vh(æ,,) -) is continuous on Z for each æ. then J (xx == maxxez h(æ, 2) and any E RR.
2 E arg max maggmax(2,2) 2) }. #EZ
0f(x) = conv Vah(z, x)
C. Omitted Proofs in Section 3
The first key step in the analysis of RP2G is to determine the continuity property of this non-convex, non-differentiable (i.c., non-smooth) objective function (TT). To do so, we derive the following sensitivity bounds for differential value functions, which play an important role establishing the continuity conditions.
Proof of Lemma 3.1. First, we provide the sensitivity analysis on the policy-induced cost and the state transition probability as follows:
1C TT
c5' Pl
Σ (Tea
Thaa
Σ Peus Ceas!
TT, T'll1. Vs S,
P
pT
Σ (Taa Than Poas'
Peas'
I ||,T, T''l,, Vs, E S.
Next, we turn to derive our desired results. Notice that, the stationary distribution d could be viewed as a particular average-reward objective with taking 1 {- = 3) as the cost function, which is also bounded in [0, 1). Therefore, by applying
19

---

Policy Gradient for Robust Average- Reward MDPs
the policy performance difference lemma (Lemma B.3),
[J p) - J(T', (p)
d
(Tea
naaa) Usa
d
(TTa - Toaa) - v Pl
14000"
I mis
Pl Σ (TT - T'all
(Due to 1I S mmx)))
S mm
max
(T x
Σ NES
ld
< 7m
|| - T 100,,,000
which also leads to
d
dg PP S mmx
T - T ||1000
Recall the analytical form of the differential value function as x = (I p + p1 - ).. (See
Lemma B. and for simplicity of our analysis, we introduce HTP == (1 pm + -
(1 - pm) We note that
T ax pl/00 = | - -H" PC -p|/20
1 (TT (CtP- c HTP -HTP-HH
HSP-HO' HJ () ploo
where
HTD - H P = - + pm ( -
(1- - (I - pm + - (I- 10)
(T pz -- - II p + p 0011) (I- p
+ (I - pd + p p 100-- ad 00 - p
(I (I-
p- ad
pp - -p - p +pt'o0)) (I p + + (I- pm) (I-
(I- p + p x-
pp - -
Then, we obtain that
10
x 11 1005
H CTD - cT
10 + ||(I - -pw' + pr' (prixo- - -px,a) c 1lo
+
[I-P p + p
p p + pm p00 (I px + pprrog11) (I p ) ct'
1H71P1000 ||TTPP cI + ||(I p + p 10-
p 00 - p 110
+ +1[[- - --- + pm. -1 1100 |p - p - p + p 00 1100 ||(1 - pr + p 2011
(8)
_ TP -c ct P 1| Cl d d='Ppl 1 + C2 p pa
11 + C²IldTP -d dr''pli
< <(22 + CTS + CS CTCS) - n I'11,,00
where the inequality (a) is attained from the fact that |[ p
c ppl Pl10o S 1, and the inequality (b) is obtained due to
1 pm 10x0
Σ
Id
ds' P
_ d d='p1li.
p pm
1x max
px
35'
By applying the Bellman equation that q satisfies, we have for any (8, ESXA
[J(T.p) J(T'' + Σ (170 - uz 1))
20

---

Policy Gradient for Robust Average-Reward MDPs
which leads the following result:
11 Pl - [J(T,P) - J(T',))) + ||Paall - -
1 S (CT + + | 11100
Proof of Lemma 3.2. While the form partial derivative over π has already been derived (Lemma B.5), we demonstrate that [T, p) is -ipscchtt æ by showing the boundedness of V (TT, p). which has been shown below
@J(T,P) p))
2
Σ
= ΣΣ
d P
2 S 7m VA, Qoa
where the last inequality is obtained from the facts 1 S Tfmix and (d)) < 1. We then turn to prove the smoothness condition of J with the help of perturbation theory of stochastic matrices. Let オ, π E II be any policies
within the policy class. We introduce (a) as a convex combination of policies π and I that is, vT(a) = (1-a) π aT' == + au where
æ. Notice that the partial derivative of ((T((a).))) p) over is
aJ(TTO)).p) do
Σ Pu 3,0
Usalee T()).
then, we are going to show that [J(mm())p))
a.(pp)) Da
S alx, which is obtained as follows:
8a
0J (J(TT(a).P) p)
OJ(T.P)
Σ
deh (a) Pe Uea
T.)..p
Σ
d Uea Isa
da
da
8;a
8,a
p (al Usa Nea
(())
+
Σ
(dTT(a)pp
P)sa)a T.
5,a
8,a
d (a)
(1s 9s
(()).p
9 p.
(T((a).p
d...p/
((us q TPP)
Σ (.))))/((==()))
P.
|uul1 11
|| 11 Σ dT((a).p d
20 a + mmxx C7 S11 < (40) + 28 CTS)o, S)a,
where the inequality (a) is obtained from the sensitivity of q. and d (Lemma 3.1), well as the facts | < 7f
and ||ul|| < 2. Therefore, the smoothness is proved.
We next show the continuity of (T). We first show (TT) is L -iisschhi J(m, p) is LipLishchitz in w. Without loss of generality, we assume that for any Ti, T2 II, (TT) s (TT2) and pr = arg maxpep J (TI,P) and p2 = arg maxper J J p), then we have
0 < V ( (T2) JA(TI,P1) (2(,2.22) S JT(TI,P)) - (1), s T T22
Then, we notice that Lemma in (Thekumparampil et al., 2019) verifies that ((T)) is Eneally convex if J(T, , p) is l- -mooth,, which can intuitively determine the weakly convexity of (TT).
Note that, similar smoothness conditions are derived in (Cheng et al., 2024; Kumar et al., 2024b), however, there are mistakes in the smoothness conditions derivation in (Cheng et al., 2024). Compared to the results in (Kumar et al., 2024b) we mentioned, we efficiently reduce the dependency on the state and action numbers.
Now, we turn to derive our main theorems. First of all, we prove the gradient dominance condition that our robust objective T satisfies.
21

---

Policy Gradient for Robust Average-Reward MDPs
Proof of Theorem 3.4. We denote xt' is the optimal policy for the robust AMDPs. We note that while J (I,, p)) is non-concave with respect to p and the ambiguity set P is assumed to be a compact set, it is possible to have multiple N inner maximum points. For simplicity of analysis, we consider the case N 1, and refer interested reader to Theorem 3.2 in (Wang et al., 2023c) for more detailed discussion about the similar general case. Specifically, we denote p* := arg maxpep J p) as the worst-case transition kernel for fixed policy ग E II. By utilizing the gradient domination condition established for nonrobust AMDPs (Lemma B.6), we can derive the following inequality:
(T) (TT" S J(T,P")
min p(H, S M . max ( म. V #Ell
(16)
#Ell
Notice that, by applying Lemma B. Jp(TT.P) is 4 -wekkky convex in n, which leads to the fact that J(TT.)) p) == ((T, + - || is convex in (Kruger, 2003). Let (T)) == maxpep J(T p). By leveraging the convexity of J (TT,))
and the compactness of P, we can apply Danskin's Theorem (Proposition B.17) to attain
(²( VnJJ(T.P"
( ZT VnJ( + 7T
(V)) V=J(TT.P))
which also implies that _ ( = V J p"1 ). By introducing मे arg minyen (gy + l ||T y|l² Lemma 1.16 implies that there exists E = ( such that
- C Nx + 26
न| π -B().. Then, we have
(++) - Vi(TT' S M max #ell
( न. V J [ S M max { - ((,,((""))
(17)
#Ell
Notice that for any ,I, 22 E II, we have e < क πे S e where is all-one vector. Then, we introduce a adaptive all-one vector é, whose i-th element é = 1 while the corresponding element of - ( p²) is 1 and è, -1 while the corresponding element of - J p*) is -1. Therefore, we have
(17) < M (e, - J = M (e.-E) S MVSA
/ (T)
(18)
The final inequality can be derived from the result in Lemma B. It is worth noting that Lemma 3.2 implies the L Lipschitz continuity of T (TT). By leveraging this Lipschitz property in conjunction with the aforementioned equation (18), we derive the desired result
L (T) - -(T' = ((T) - - + ((+)+ - v (TT(')
S MVSA V 1/2ea (TT)
+ V((T ((()
S MVSA V V1le2e2 (T)
+ Lo || #|
L
MVSA +
V 1/2r (T)
(19)
2l
where (19) holds by using arguments of Lemma 1.16 and (T() 2 (+))
Proof of Theorem 3.5. We begin by defining policy म. = arg min V (Tt) + lx T| 112 then, we have
Vayaen (Te+1) min ( (TT + ln || +|
V ( Lz || * 11
The proposed RP2G updates the policy by using the projected gradient descent step:
T++1 Projn (π, - as Vm
Therefore, the Moreau envelope function 1i/eer (T++1) satisties
V Viface (TT+1) < V ( fur [|Poojn ( - a a ( p:)) Proju
(a)
< (T+.)) + fn ग. V. J ( p:) - -
-(++)) lr | 12 - 2 a ( nJ ( Pt), गe. - -i)) + 26 V/ (
S Mayee (TT, + 22 (((TTt))) v (TT.) + 8, + lx
T 711l?) + a²t 2
(20)
22

---

Policy Gradient for Robust Average-Reward MDPs
Here, (T,, Pt) is produced by the RP2G scheme iteration step L. The inequality (a) follows the basic projection property (Rockafellar, 1976), Le., for any æ1; 22 E R
P (m)) ( - ||00| - æ221;
and the last inequality holds due to the fact that ( p)) is -mooth in æ,, in the sense that, for o..
le | TT|| -Tell
((+)) 2 P.) 2 J(T,, Pt) + (V Te.. Pt); के o.))
fr || Tell?.
2 max J(T.,P) p) 5c + [ Pt). t T④) pEp
v(T)))
By summing (20) up over i, we deduce that,
52 + Ex || -T:1l
V 1/22r (TT-1) V1/2en (Tr) + 2t a
(Tt:)) - (TT,))
Ta
2
1=
Rearranging the above inequality yields
Σ
- (+t.)
La |i Tell?
5
Vafeew (TTO) - M/seew া
Tal
T
d..
(21)
2
20
2
1=0
is worth noting that,
lx - =1 -Tell2 (TT:)) + + IT, TTll= (tt:) lx || -T.
lx
(TT,)) (++.)
TTe
lx | TT, 11
(TTe) + fr I|T Tell?
min (VI(TT)
lx || -
- TT(
well
1 - 1 4
V s/or, [T.))|?
(22)
where the inequality (a) in (22) is obtained due to the strong convexity of (T) + lx || - π 112 for example see Lemma E.3 in (Wang et al., 2023c). The last equality in (22) is obtained by directly utilizing the gradient of Moreau envelope function proposed in Lemma B.16, i.e.,
W/2 (T)) = 2P Te arg max (V((T) + lx || - -1²)) #ell
28 (TT; - -T)).
Let us introduce कं arg min (((T) [ 2 and then we have
and कि == arg min ( ex |T2 - क 1|2 for any TT, I22 E II,
L 1//2 (T) - 11//2 (Tz)
min
(V + 4
|| || - 11 min (M + fm Im2 11)
#Ell
HEll
(#:) + 4 |
1||2 V( - | - 12l1
S (+12) + lx ||| Ā2|2 ( - l न22
ln (I|m) #2 ||T2 - 12
s 2
(23)
Therefore, obtain upper bound such that
U 11/2e (TO)
v Viieen (πT-1) S S.
Plug (23) and (22) into (21) and then we obtain that
V v 1/2cn (T=) 5
2T .fl
a 12 + 4l
Σ dz.
23

---

Policy Gradient for Robust Average-Reward MDPs
We next show that for some tolerance > 0, there exists some i such that
(Te)
min (T) r
S
We define the globally optimal policy for the RMDP as n². By applying the result stated in Theorem 3.4, we have
(T..)) - ((T))) = (MVSA
LT Ln 2F
+
(24)
By summing up (24) over t and lower-bounding it, we can observe that
min (V(T+)) ((())) (e(0,-TT11)
1 - π Σ
- -
s
7
1
Lu (MVSA+
V syzee (T+:
2P
By Cauchy-Seai Schhay--ccwazziii inequality, can obtain
T (T))
T-1
V
1/2n
L 1/arr (T:)
a ==
1 v 60 $ VT, 6.t1 I Thg and nτ. as the output of Algorithm 1, and then we obtain
(TTT))) (V(TT) s
1
[VVSA+
+
L
A V.V (T+i)l
VT
26
T-1 S + 2T 44,
1
M SM
SA + L
Σ di
VT
28
1=0
(0)
1
[M SM + Li
v
(AL +
VT
2l
1-7)
Lm
(1eSSVT+ ( + +
4P 4
M MV
SA +
26
1-T
where the inequality (a) holds due to the adaptive tolerance sequence, the sense that,
8 < 50 (1 (1+T+ +...) S 50 --
Σ
t=
==
Now we can attain our final result that, when T' satisfies the following condition,
[MVSA+
b=)
(4emS + 26 + 46. 2
T2
= =0(c-))
then, we have
(( - min min (T S
#Ell
24

---

Policy Gradient for Robust Average-Reward MDPs
D. Omitted Proofs in Section 4 and Relative Supporting Results
Proof of Lemma 4.1. For any & S, we can formulate gradient of the differential value function as
Oug.P
Tsa Ops1e192 Σ
Opsra1s2
dporo1o2 Tsa Σ
i
E Poas' (Ceas' - J(T. + ug:0)
Öpsas
(-
aJ 0vy m
(T. P)
Σ Tsa
(Ceas' - J( + V/g x) + Σ Rea Epsae
Ppe1019
ppsraee
Multiplying each side with d= taking the summation over E S, and rearranging terms, we then obtain
(J(
Opsas
Oup.
Oog p
Σ d
(Ceas' J(T + U/ TT.P)
Σ Taa Σ Psas'
T
Öp Öps1a182
Opscai82
pperass
Opsaase
Öpeas'
Σ P
(Coad' [ p) + -0u? ))
aa
Öps1a182
d Esjay
(Csja1s2
J ( + T.P
Then, we show the corresponding performance difference lemma that the adversary satisfies.
Lemma D.I. (Adversary's Performance Difference Lemma) For any policy I1 and p. p' (AS)SXA, we have
J( p) - J(T,p') = Σ
d T.P
Σ (peas' Peast) Isas
Tea
SES
acA
Proof of Lemma D.1. By the definition of the differential action-next-ste value function, we have
Σ p. Σ sa
Σ
Σdn P
Σ Tsa Σ Psas'
(Ceas'
J(T, p') + u0 T.
Pras Isas'
J(T, J[ p') + Σ
d
pT Σ Ta Σ Pras U
J(T, J [ p') +
T
U
n.
-((T.)) - J (T, p') + Σ
d p Σ
To Psar gass!
which leads to the desired result.
Proof of Lemma 4.2. We first follow the similar strategy of Lemma 3.1 propose the sensitivity analysis on the transition- induced cost and the state transition probability as follows, that is, for any s E S
cg
R.P2
Σ Tsa Σ
(Pi,sas' P2,sas' Csas'
Σ Usa max
Σ
|Pi.aas'
P2..ass|
||pi
P22l1,00
8,0
P
PT.
Σ
Pi.,ass'
D2. 5 lpp: -22l11,00.
25

---

Policy Gradient for Robust Average-Reward MDPs
Then, by utilizing the adversial policy performance difference lemma (Lemma D.I), we can reach our first desire results. For the average-reward objective, we have
[ J(T, p)21
Σ IES
d
Tea
D(PL.000
P2.cas/ g
acA
(2 + mlmix)
Σ Σ
Tsa
Pl.sas
P2,sas'
REA
S (2 + mlmix)l P2|11.00
where the inequality (a) obtained due to the faet that for any π E II, p E (A5)SxA, and (8, (8 E
9
P.P. sas
S
Csas' ( p)
S Csass + ||d ||c + |0 I 2 + mix
As for the stationary distribution, we can straightforward obtain that
d d < (2 + 5tmxx) llp P2ll1,00, Vs E S.
Then, consider the sensitive bound for the differential value function, that is
T. 0TT.Pello0 H c CT C
H (c - c..) (HT-.) HTTP2)) c cT 1oo0
where HDD (I - p + p px)0) is defined in the proof of Lemma 3.1. We notice that
HT MT
(I - PT + PTT > - P (I PT )
(I P
((I PT + PM P [I PT ) 11 (I- (I-PPt
+I- PT + + P (PT )!T
(II- + - (PT P P + P (I - P + PT. (I - )
+ (I- Ps + P
PP )
Thus, we have
10" TP: Pt
T. 1l,0 HT (c p.) 30 || p PT ) (PTT.00 - c T.22 00
+ +1[ Ps + p (PT
T, - P ,77 (I pMT + PTT PTT
(I PM T.p
TT 1000 ||c C2
T.P
+ ||(1 - P + P p0.00
1000 || 00 -P 1100
+ || - P + P PTT 100 P. - -P p
+ + 000 I1 || P -
(
2 2T c 1100 + c' P || + + PT - P 1oc
C²2
P
s (2C + CSC + C² C2 P2211,000
where the inequality (a) obtained due to II(I pT ( cm ~0 S 1. By applying the definition of T. we have
1g T.P:
-... || = max Ceass - JTT, P1) + u
T.Pl
(Ceus' - J(TT, + u.
< [T(, ((T,P2)) + =. - u 12 S (CP + CP) P2l1
Proof of Lemma 4.3. Lemma 4.1 provides the analytical form of the partial derivative, that is,
0J(T.P)
d saa Tap.
Opsas'
26

---

Policy Gradient for Robust Average-Rewand Reward MDPs
Then, have
(T,)
Σ 8,0,a'
2n (d, TTa Ianlsas') S (2 5ixx)
Σ 8,0,a'
(d TT Tsa) )² S (2 5l VS,
which verifies that JTT,, p) is Lp Lipschitz in p by showing the boundedness of (TT We then turn to derive the smoothness condition (T,, p) utilizing the similar perturbation theory of stochastic matrices applied in Lemma 3.1. Let p. p' E (A5) be any transition kernels. We introduce p(a) as convex combination of transition kernels p and p', that is. p(a) app + op' p + at where p' p. Notice that the partial derivative of J J p(a)) over a is
p((T)
d T
d..p(a)
U Iaas'
da
8,0.6'
then, going derive the smoothness by showing
3J(m(a).p)
as(p.)) 80
S al
da
(T, p(a))
(J.
=
Σ
d plap(a)
Taa U Vond' Isas'
p(aa)
Σ
d TI sn U Vans' 9 Daas
da
da
9,0.8'
$,a,8'
Σ
dee p(()
Tea Veus (g
a.
+
(dit
P D) Usar T.
5,a,"'
5,a,"''
Σ
pT d
Tea
(uaa: Iza
ppp(a)
9
d
(pT)p(a)
d
Σ Tea (w0as Isa x.P)
8,0
<
Σ
d
plp))
Tan
1 || Waall1
Σ dTT.p(o) d=
Tsa ||
(a)
0 1,00 + + + 5l C < 2(20g 2(2 + 5l S),,
PCP
where the inequality (a) obtained from the sensitivity of qThh -P and d (Lemma 4.2), well as the facts | 2+ 5tmix and ||,|1,,00 S 2. Therefore, the smoothness is proved.
Proof of Theorem 4.4. By the adversary' difference performance lemma (Lemma D.1), we have for any IT and (A SSS we have
J(T,p') J(T,p)
Σ sES
d Σ Tsa Σ (Peas' Poad Isae
Then, we can obtain that
0 s J(T -(TTp) = Σ
d
Tsa
(Pras' Poaer) F.
SES
acA
8¹
PT.
Σ To
Σ (Deae' - Doas') ) Doas!
d
dg
P.
BES
REA
dTTPP'
max
PEP
J..P
d
(Weae' Dsas') T.P
8
d
max
T sa
T.P (pinss Dras') Isas'
d
P.EP.
#ES
BEA
20,
=0 while p.=pi
< M max PEP
(p p, V ,,, p)),
where the inequality (a) holds only under the rectangularity condition.
27

---

Policy Gradient for Robust Average-Reward MDPs
Now, we proceed show main convergence result the inner worst-case kernel evaluation. Here define the gradient mapping
G Gp(p) = 3 (Projp(p pV.((T.))) - -p).
(25)
Notice that P is convex and [TT, p) is l p-smooth in p, then we turn to derive our main result.
Proof of Theorem 4.5. Lemma B.13 implies that if | S e, then
(PJ(TTPp)) E N (p*) + 2cB(1),
(26)
where p' == p (p). No the norm cone of the set P. and B(r) = fxr E R" ||||| S r). By the gradient
dominance condition established in Lemma 4.4,
min kE K-1,)
(J(T, p(). M min (E( K--, PEP
max (p- Ps, (PJ(
S M max (p P V (T, PEP
(27)
where := + arg Bagminns---o [G Note that, Lemma B.12 implies that
26p (J, pr) (TT,
26
|| (P s
K
K
where the last inequality holds due to JJ p)1 S
While we set that
28
on 4MVSA
32 32p, ()
KZ
K
82
then
| (P 5
4M SM
Hence, by applying the equation (26), we have
P Pall 22 6n
(27) S M max
PEP
4MVSA
where for any Pi. E P.
P2ll S |Pil| + ||22|| S 2/SA.
(28)
Theorem D.2. (Lamperski, 2021, Theorem 1) Assume that 1) S 2. integers the following bound holds:
There are positive constants h, Ca, C5 such that for all
Wi(C(ph), s cce + cs (n log k)
In particular, if 46K
log K. and K 2 4, then:
W((C()K) (cs
C5 (4h)
K k- (log K)²
Proposition D.3. (Lamperski, 2021, Proposition 2) The constant e1 and C2 grows linearly with n. If D2 < 8, then we can set h = D 2 { 2, while C4 and cs, grows polynominally with respect to -1-10 D²12 and x In general, we have
a positive constant es and a monotonically increasing polynomial p (independent of n and X) such that for all X > the following bounds hold:
h 2 c6t expe ( [DeE ) max max cs) S p(A e
(3D
4
4
28

---

Policy Gradient for Robust Average-Reward MDPs
We note that only the notation has been adapted to our setting; the results and their proof remain unchanged from (Lamperski, 2021).
Lemma D.4. For any function J : P + R. let be the probability measure defined by v2( = exexp((( (( 2)) ddp Particularly, vo represents uniform measure. If J is LypLipschit,, then the KL divergence of v. from the uniform measure vo bounded by:
Jo exp( (or.
2 (r+ +
1) + log(2D").
0 s KL(Ps, & Eug (T p)] max (TT, + nlog pEP
max
r log(2)
Proof of D.4. The KL divergence is bounded below by 0 as a standard result in (Cover & Thomas, 2012). Then we only need to prove the upper bound.
Denote pd as the optimal solution of maxpep [ p) for given policy π. It exists as is Lipschitz continuos and P compact. Then multiply both numerator and denominator of v. by exp(- p²) )), we have
(B) = Js (m p1 Sp
Noted that by definition of uniform distribution, v/(pp) vol(P) So the definition of KL divergence implies
dp
KL(vJ, vo) =
- log(vol(P))
log (J(m dp
Note that the set P is contained in a ball of radius D (for example, for an ellipsoidal ambiguity set of size 0, we have D /0/Xo Amin where Amin is the smallest eigenvalue of the shape matrix Q). Hence, the volume satisfies vol(P) I n/2 1(n/2+1) S 2D", where denotes the circular constant. The second inequality holds for n 10.
D"
Therefore, upper bound the denominator, it suffices to obtain lower bound fp -(mmp)) dp. Since the function J is Lipsschciitz continuous, it follows that
02 J(T, P) (TT,P') - -pplpp - p'll 1-
Besides, L 1-p'1l 2 1/2 if and only if | p'1l S
log 2 L
Set c and let Bp (c) be the ball of radius centred at p". Then for any C Pn PNB (c), we have
log2 Lp
[ (( dp> 2 Po (c)) vol(C).
As proved in (Lamperski, 2021, Lemma 15), the contains ball with radius min r ++ ). where denotes the radius of a ball contained in P. Then lemma follows by using the fact that a ball of radius 7 has volume given by 2 T(*+1)
Proof of 4.6. Recall that J p) is Tpp-Lipschitz, that AJ(m p) is -ipsshitc, Assume that p follows distribution PxJ, then applying Lemma D.4 can obtain
(r + V + D22 1 (1m11))) })
n log 2D max
Epnes [[TT 2 max J(
(29)
pEp
X
r loog 2
Let Ty be the k-th iterate of the algorithm 3, then
Kanturovich Duality
E E[J(m pk)
E,, [ [)] LppW:(
(29)
log(e1 max(1, W. (C(ps)
max J(T,
pep
29

---

Policy Gradient for Robust Average-Reward MDPs
(r+vr2+ AA)A
where = 2D max
(2)
Then we will show how to tune the parameters achieve an average suboptimality of o
First, we choose so that logle max(1.)))
f Without loss of generality, we assume 1. Set æ = log(e2A): so that
ci ex and the required bound becomes
2n
For any x E (0, 1), the maximum value of se (1-n)) occurs at x = (1 - k)- so that for all x E R:
xe ze (1 (1-m)z <
(30)
(1 k)e
So it is sufficient to set na (16((1-0) to achieve the bound. Then plugging back, it shows that sufficient condition
for log(esA) < Az is given by 2
2n
2 cT
(31)
c1
Now for a fixed 1, the bounds from Theorem D.2 and Proposition D.3 to give that
W1 W1(C(p)),
C5 c1+
K (log K)*
K
(4h)
D²ex 16
S p(1)e 20
1+
K $ (log K)$
4
sp(1) (1+
13D 16
K (log K)
48cg
Similar to (30), can derive the following inequality for all p (0, and all K > 0:
K K-2te
--t (log K) (
(K-tto S
ep
Thus, to achieve (C(p)))))),))) S bx. 2, it is sufficient to have
K S ep
6x
(P(L) 1+
1902
-2
2
4 43c3
e
=
which is equivalent have
1
2
2
C1-2p
To separate the parameters, define constant Cj that is independent to 17, X, 8x, and p. such that the bound above holds whenever
13D2RA
exp
14(1-2p)
Combining the results above with (31), we obtain the desired conclusion by introducing a= 1-20 by substituting the dimension of the transition kernel
4 > 4 and b b= a > 1, and
222
E. Experiment Details
In this section, we provide the implementation details and experimental setup. All results were generated on an Apple M2 Max with 32 GB LPDDR5 memory. The algorithms are implemented in Python 3.11.5, and we use Gurobi 11.0.3 to solve any linear optimization problems involved.
30

---

Policy Gradient for Robust Average-Reward MDPs
E.1. Environment Setting
GARNET MDP G((S), 6) defined by three parameters: S the size of the state space; |A], the size of the action space; and b, the branching factor, which specifies the number of accessible next states for each state. The cost is generated randomly following uniform distribution within [0, 10).
E.2. Rectangular Ambiguous Case
We validate the convergence of RP2G three different sizes of GARNET MDPs with (s,d)-rectangular ambiguity sets. Specifically, we use the l norm to measure the size of the ambiguity set.
Pea = {Pea A
Pea - Psa 11 S Ksal:
where Psa is the nominal transition kernel and Ksa. randomly generated from uniform distribution over the interval [0, 0.3].
We run 50 sample instances with 250 iterations of RP2G for each GARNET problem. At each iteration, we record the relative error between the objective values of RP2G and the optimal value J", calculated as (IJ(T,,,.)) 1/J//" For the optimal value J", we use the robust value iteration method from (Wang et al., 2023c) as our benchmark, with the stopping criterion l|l, - 0 112 I 5 x 10-4.
The relative error values are plotted in Figure 1. each problem at each iteration. The upper and lower envelopes of the lines correspond to the 95 and 5 percentiles of the 50 samples, respectively. These results demonstrate the convergence and optimality of our algorithm.
The line represents the average relative error across the 50 instances for
E.3. Runtime
This subsection compares the computational efficiency of RP2G with the only existing gradient-basee method to highlight the advantage of adopting decreasing tolerance sequence {6, )20- Specifically, we consider the robust policy mirror descent algorithm (Sun et al., 2024) as a benchmark, which assumes the inner worst-case evaluation problem is solved exactly. For computational considerations, we set the inner worst-case evaluation problem in the benchmark method with a fixed tolerance of d = 10 at each iteration, while RP2G adopts a decreasing tolerance sequence initialized with do = 1 and reduced at a rate of 0.95.
We the same environment and ambiguity settings described in the Section F.2. Table reports the runtime for the two methods, with termination determined by minimal changes in the objective value, i.e., [ Pt) - (TT Pt-1)] 1, 10-4, The results demonstrate the effectiveness of adopting decreasing tolerance sequence in improving runtime efficiency.
E.4. Non- Ron-Rectangular Ambiguous Case
We adopt the ellipsoid form (Wiesemann et al., 2013; Li et al., 2023) for constructing the non-rectangular ambiguity set, defined as
p = (p (p-p) T
5 rr)
p)
We set size parameter r == 1. The Hessian matrix Σ is generated as Σ - ooo T with o E R AxAA being a column vector whose elements are independently sampled from a uniform distribution over [0, 0.1. The nominal transition kernel denoted as p.
We validate the robustness of RP2G on the non-rectangular ambiguity set by comparing it against the non-robust policy gradient method in (5, 3, 4). At each iteration, we evaluate and compare the values of V (TT) maxpep J(T,, P) for both methods. The results are plotted in Figure 2. The line represents the mean values across 20 instances, while the shaded area indicates the range between the 5 and 95 percentiles over the 20 samples. This figure demonstrates the robustness of RP2G compared to the non-robust policy gradient and also shows the convergence of the RP2G algorithm when using Algorithm for inner worst-case evaluation.
E.5. Discount Factor Discussion
In this section, we perform experiments with different choices of the discount factor y. For robust discounted MDPs, we use the Double-Loop Robust Policy Gradient (DRPG) algorithm proposed in (Wang et al., 2023a). The experiment also
31

---

Policy Gradient for Robust Average-Rewed Reward MDPs
200
AMDP
Iterations to Convergence
150
50
0.70
0.75
0.80
0.85
0.90
0.95
1.00
Y
Figure 3. Iterations to convergence under different discount factors and AMDP.
conducted on GARNET MDPs G(5, 3,5)
We set the step size (1 ? for each robust discounted MDP, consistent with the theoretical convergence analysis in the reference. For RP2G, we use a step size of 3 = 0.05. Figure illustrates the number of iterations required for convergence under different values of the discount factor, compared to the iteration count for convergence in robust average-reward MDPs. Convergence determined when [(++1 - Jz) < 10-4, It is evident that as increases, the number of iterations for convergence grows significantly, showing a clear upward trend.
E.6. Rectangular and Non-rectangular Ambiguity Comparison
In this section, we conduct experiment with two ambiguity sets under same size to show the superiority of ton-rectangularity in application. In particular, we compare the put-of-sample performance of (s, a) -rectangular ambiguity set and ellipsoid ambiguity in classical inventory control problem (Zipkin, 2000).
In the inventory control environment, the agent decides how many items to order (a) based the current inventory level (s). Each ordered item incurs cost of 1, and we assume that there is no delay in the ordering process.
After the customer demand d E [0, m] is realized, the agent observes the updated inventory level. If the resulting inventory level s + a falls below the allowed backlog limit (set to m our experiments), the agent can only fulfill s + units of demand. this case, the effective demand truncated exceeds the maximum inventory capacity m. is reset m. the end of each period, the agent incurs holding of 1 for each item in inventory and backlog cost of for each unit back-ordered.
+ a. the other hand, the updated inventory level
To estimate transition probabilities for policy training, we simulate 1000 trajectories using uniformly random actions and demands. Each trajectory consists of 100m time steps. Table reports the average long-term cost under two ambiguity sets. The results show that the policy derived from the non-rectangular RAMDP is less conservative, as indicated by its lower average cost.
Table Average performance under different inventory levels over 2,000 out- sample trajectories, comparing the (s, a) roctanuugl and non-rectangular (ellipsoidal) ambiguity sets with set size equal to 0.I.
Inventory Level(m)
5
6
7
8
(s, rectanguul
2.906
3.980
4.360
5.246
6.014
6.620
Non-rectangular
2.850
3.659
4,289
5.187
5.931
6.582
32


Reviews:
[{"review_id": "Pimce8cRoO", "reviewer": "Reviewer_sWdH", "summary": "This paper extends the work of Li et al. 2023 from solving robust MDPs in discounted setting to average reward setting. Numerical results are also provided.\n\n## update after rebuttal\nI thank the authors for their efforts in writing the rebuttal. I agree with that letting the discount factor to 1 would of course be a too simple adaptation, but still the essential difference seems to be an alternative dynamic equation -- the same technique from discount factor setting still applies. I will keep my score.", "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": "Thank you for your insightful questions and constructive suggestions! \n\n**_Comment 1: Additional comparison between rectangular and non-rectangular RAMDPs would be helpful._**\n\nThanks for the suggestion! As the (non-)rectangularity only affects the ambiguity structure and appears to be independent of the chosen reward criterion [1], we adopt the non-rectangularity to the average-reward case without further justification; thus we did not design an experiment specifically to show the advantages of non-rectangularity over rectangularity under this criterion. We do agree that it would be helpful if the superiority of the non-rectangularity could be better demonstrated in this setting. To address this, we compare the performance of $(s,a)$-rectangular and non-rectangular RAMDPs in an inventory control setting with the same set size (see https://drive.google.com/file/d/1VKnmT5_Wzpj6PwH_UbHImimhrhKBpVgq/view?usp=sharing). The results, presented in the table, show that the policy obtained from the non-rectangular RAMDP is less conservative, as evidenced by its lower average cost. We will provide a more detailed discussion in the next version of our paper and highlight the advantage and superiority of non-rectangularity.\n\n**_Comment 2: Further clarification of the technical novelty could be useful._**\n\nWe appreciate the reviewer's concerns regarding our technical novelty and would like to emphasize that the extension from the discounted setting to the average-reward setting is non-trivial (see the example in **Reviewer iYjz, Comment 2**)\n\nAs our proposed algorithm follows a double-loop structure, widely used in various fields, including game theory [2], min-max optimization [3,4], and robust MDPs [5], our analysis builds on standard non-convex optimization techniques, which were also adopted by [5]. Compared to [5], our novel contributions are twofold: (1) for the outer loop, we establish Lipschitz continuity via a novel sensitivity analysis and introduce a gradient dominance condition with an convergence guarantee tailored to the average-reward setting; (2) for the inner loop, we provide an effective algorithm for worst-case transition evaluation under rectangularity, along with which is structurally different from Algorithm 3.2 in [5]. While achieving a similar convergence rate, our analysis differs from [5], relying on standard non-convex optimization techniques [6].\n\n\n**_Comment 3. Essentiality of using average-reward instead of discounted reward should be highlighted._**\n\nThanks for your suggestion. As our work is theoretically oriented, our contribution focus on developing efficient algorithms with theoretical convergence guarantees for RAMDPs. We do understand average-reward setting is well-suited for agents concerned with long-term or steady-state policy behaviour, such as resource allocation, portfolio management, and healthcare [7,8]. In this sense, exploring the practical advantages of RAMDPs in these applications represents a promising direction for our future research.\n\nMoreover, as shown in Appendix E.5, when $\\gamma$ approaches $1$, the computational cost increases significantly when using discounted-reward MDPs to approximate average-reward solutions. This underscores the necessity of methods specifically designed for the average-reward setting.\n\n**_Comment 4. Adaptation to stochastic policy gradients could be considered._**\n\nThank you for this valuable question. Our analysis assumes a model-based setting in which the MDP structure is known except for the transition kernel, so the policy gradient can be computed exactly. When only stochastic policy gradients are available, additional challenges arise in modeling and in ensuring robustness under broader uncertainty. Extending our results to this case is a promising direction for future work, for example by incorporating robust temporal-difference methods such as [9].\n\n[1] Wiesemann W., Kuhn D., & Rustem B. 2013. Robust Markov decision processes. \n\n[2] Ding D., Wei C. Y., Zhang K., & Jovanovic M. 2022. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. \n\n[3] Jin C., Netrapalli P., & Jordan M. 2020. What is local optimality in nonconvex-nonconcave minimax optimization?\n\n[4] Davis D., & Drusvyatskiy D. 2019. Stochastic model-based minimization of weakly convex functions.\n\n[5] Li M., Kuhn, D., & Sutter T. 2023. Policy gradient algorithms for robust mdps with non-rectangular uncertainty sets.\n\n[6] Beck A. 2017. First-order methods in optimization. \n\n[7] Ghalme G., Nair V., Patil V., & Zhou Y. 2021. Long-term resource allocation fairness in average markov decision process (amdp) environment.\n\n[8] Patrick J., & Begen M. A. 2011. Markov decision processes and its applications in healthcare.\n\n[9] Wang Y., & Zou S. 2022. Policy gradient method for robust reinforcement learning.", "claims_and_evidence": "The claims are well-evidenced.", "methods_and_evaluation_criteria": "Methods (PG) and evaluation criteria (average reward robust MDP) all make sense.", "theoretical_claims": "No, but I believe the plausibleness of the theoretical claims because of correctness in the discounted setting.", "experimental_designs_or_analyses": "The methods are evaluated in random synthetic MDPs instance GARNET, which is a standard benchmark in robust MDPs. The methods are evaluated from runtime and compared to non-robust method. However, the paper only compares the worst-case policy value of the one output by a non-robust PG method and the proposed method, which seemed incomplete because the power of non-rectangularity is really statistical efficiency compared to rectangular uncertainty sets, and the key contribution is extension to average reward criteria. Please refer to my comment for possible improvements.", "relation_to_broader_scientific_literature": "The paper is solving an important instance of robust MDPs -- the one with average reward criteria. In this sense, the paper complements the work of Li et al. 2023 well.", "essential_references_not_discussed": "The paper is well-positioned and relevant literature is discussed.", "other_strengths_and_weaknesses": "Weakness: On a technical level, the essential thing that changes from solving discounted to average reward setting is the gradient formula and the magnitude of Lipschitz constant. Thus, I am unsure about the novelty on the technical side.", "other_comments_or_suggestions": "Please consider comparing to a data-driven MDP instance and compare the out-of-sample performance of robust MDP with non-rectangular uncertainty sets vs. the one with a rectangular uncertainty set. In addition, it would be enhancing the paper's significance if the authors can show the essentialty of using average-reward criteria (e.g., comparing against work of Li et al. 2023) where we can see the practical advantage of using average reward robust MDP with non-rectangular uncertainty set.", "questions_for_authors": "How does the proof work when only access to stochastic policy gradients is available? What are the major changes required then?", "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": "Su0OZ0tnVX", "reviewer": "Reviewer_iYjz", "summary": "The paper investigates methods for solving robust Markov Decision Processes (MDPs) under the average-reward criterion. Building on existing approaches developed for the discounted-reward setting, the authors extend these ideas to the average-reward framework. The study presents multiple algorithms tailored to different structures of the ambiguity set, with a particular focus on whether the set exhibits a rectangular structure. Convergence results for these algorithms are provided, demonstrating their theoretical validity and practical implications.", "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 are sincerely grateful to the reviewer for the insightful comments and valuable questions. \n\n**_Comment 1. Additional clarification on the difference between our work and Li et al. (2023) is needed._**\n\nWe apologize for the insufficient explanation of the contributions of this work. It is important to clarify that the extension from the discounted-reward setting to the average-reward setting is non-trivial (see our reply to **Comment 2** for a detailed discussion). \nWhile both our work and that of Li et al. (2023) rely on a double-loop structure, along with similar properties such as the smoothness of the objective function $J$ and the gradient-dominance condition, the technical foundations used to establish these properties are quite different. Compared to their work, our contributions span both loops. For the outer loop, we establish Lipschitz continuity via a novel sensitivity analysis and introduce a gradient dominance condition specifically tailored to the average-reward setting, leading to the convergence guarantee. For the inner loop, We propose a tailored projected gradient ascent algorithm for worst-case transition evaluation under rectangularity, with a convergence guarantee. This approach is structurally different from Algorithm 3.2 in Li et al. (2023). Although our inner convergence results may appear similar, the underlying analytical tools are fundamentally different.\n\nWe hope this clarifies the key differences between our work and that of Li et al. (2023), both in theoretical foundations and algorithmic contributions.\n\n**_Comment 2: Recovering average-reward results from the discounted setting could be discussed._**\n\nWe thank the reviewer for raising this point. While it is theoretically possible to recover average-reward results by taking the limit as $\\gamma \\to 1$ in the discounted-reward setting, this approach is often infeasible in practice. As shown in Li et al. (2023), the number of iterations is $\\mathcal{O}(\\frac{1}{(1 - \\gamma)^4})$ (hidden within their constants), which increases rapidly as $\\gamma\\to 1$. This makes the computational cost prohibitively high for large $\\gamma$. We also provide empirical evidence in Appendix E.5, where we observe a significant increase in iteration count as $\\gamma$ increases. These results highlight the practical limitations of using discounted-reward methods for solving robust average-reward MDPs, and motivate the need for a tailored algorithm, as proposed in our work.\n\n**_Comment 3: Additional explanation for Figure 2 could be helpful._**\n\nThank you for pointing this out. Regarding the experimental setup, we obtain and record the policies from both robust and non-robust AMDPs at each iteration. To assess policy robustness, we evaluate their performance under the worst-case transition scenario, i.e., computing $\\max_{\\boldsymbol{ p} \\in \\mathcal{P}} J(\\boldsymbol{\\pi}, \\boldsymbol{ p})$ with given $\\boldsymbol{\\pi}$, and then record these values for plotting. This comparison is wildly adopted in robust MDPs literature [8,9] as a standard approach to demonstrate robustness.\n\nIn terms of result interpretation, the RAMDP policies consistently achieve lower costs under worst-case transitions, highlighting their effectiveness against adversarial kernels. Moreover, as the number of iterations increases, the worst-case evaluation cost stabilizes, indicating convergence. These findings are in line with our theoretical results in Section 4.3. \n\nWe hope these additional explanations could help clarify our numerical experiment.\n\n[1] Lamperski, A. 2021. Projected stochastic gradient langevin algorithms for constrained sampling and non-convex learning.\n\n[2] Wang, Y., Velasquez, A., Atia, G., Prater-Bennette, A., \\& Zou, S. 2024. Robust Average-Reward Reinforcement Learning.\n\n[3] Riemer, M., Khetarpal, K., Rajendran, J., \\& Chandar, S. 2024. Balancing context length and mixing times for reinforcement learning at scale. \n\n[4] Kearns, M., Mansour, Y., \\& Ng, A. 1999. Approximate planning in large POMDPs via reusable trajectories. \n\n[5] Jin, Y., \\& Sidford, A. 2020. Efficiently solving MDPs with stochastic mirror descent.\n\n[6] Puterman, M. L. 2014. Markov decision processes: discrete stochastic dynamic programming.\n\n[7] Xiao, L. 2022. On the convergence rates of policy gradient methods.\n\n[8] Sun, Z., He, S., Miao, F., \\& Zou, S. 2024. Policy optimization for robust average reward mdps. \n\n[9] Tamar, A., Mannor, S., \\& Xu, H. 2014. Scaling up robust MDPs using function approximation.", "claims_and_evidence": "The paper explores methods for solving robust Markov Decision Processes (MDPs) under the average-reward criterion, extending ideas originally developed for the discounted-reward setting. The authors introduce a robust projected policy gradient algorithm (RP2G) and establish its global convergence, despite the challenges posed by non-rectangular ambiguity sets. This convergence analysis relies on an oracle that efficiently solves the so-called inner problem. To address this, the paper presents two specialized algorithms for solving the inner problem: one based on projected Langevin dynamics and another using projected gradient ascent, specifically for rectangular ambiguity sets.\n\nThe presented results are interesting, meaningful, and convincingly supported. However, one key question arises: Based on my understanding, Li et al. (2023) have already obtained similar results in the discounted-cost setting. Could the authors clarify what distinguishes their work from Li et al. (2023), beyond the shift from the discounted-reward to the average-reward criterion?", "methods_and_evaluation_criteria": "The examples and evaluation criteria considered are meaningful and interesting, however, again almost identical to Li et al. (2023), with the only noticeable difference being the averge-reward criterion.", "theoretical_claims": "The theoretical results look surprisingly similar to those achieved for the discounted-reward setting in Li et al. (2023).\n\nCould you state clearer where the differences are?\n\nWhat happens if in the discounted cost setting you choose the discount factor $\\gamma\\to 1$? Can you recover the average-reward results?", "experimental_designs_or_analyses": "I don't fully understand Figure 2. It would be helpful to explain better why this plot is interesting.", "relation_to_broader_scientific_literature": "The literature is well cited and discussed.", "essential_references_not_discussed": "none", "other_strengths_and_weaknesses": "The paper is well written and easy to follow. The only concern I have is the novelty compared to Li et al. (2023), see points raised above.", "other_comments_or_suggestions": "-", "questions_for_authors": "-", "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": "C3iqqUKVNR", "reviewer": "Reviewer_WW4Y", "summary": "This paper studies robust *average-reward* MDPs (RAMDPs) with general ambiguity sets. It proposes a policy-gradient-based algorithm, RP2G, that leverages an exponentially decaying adaptive tolerance mechanism $\\{ \\delta_t \\}$ to enable provably efficient policy updates, assuming an oracle that solves the inner problem $\\Psi(\\pi)$, and coming with global convergence guarantees. Further, it also proposes an optimization algorithm (also leveraging projected gradient update) to solve $\\Psi(\\pi)$ for the worst-case kernel that also provably converges (in some sense). The performance of the proposed algorithms are supported by simulation results.", "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": "Thank you very much for taking the time to review our paper and your insightful comments as well as suggestions.\n\n**_Comment 1: Technical details in Section 4.3 should be added._**\n\nThank you so much for pointing out the missing details in this section! That would be definitely helpful if full technical details are provided. We will include a detailed discussion of the proof and analysis in the next version of our paper.\n\n**_Comment 2: Statement with \"... is the first...\" could be misleading._**\n\nThank you for your suggestion. We would like to emphasize that while the technical tools for solving generic non-convex problems are well established [1], no existing literature has applied such analysis to robust average-reward MDPs. To the best of our knowledge, the most recent policy gradient method for robust average-reward MDPs [2] is limited to the more conservative $(s,a)$-rectangular case. We will clarify the wording in the manuscript in our revision to improve readability.\n\n**_Comment 3: Considering additional benchmarks in the experiment could be helpful._**\n\nThank you for this insightful suggestion. We do totally agree that incorporating additional benchmarks would strengthen our experimental evaluation. As suggested by **Reviewer sWdH**, we conducted an experiment in an inventory control setting to demonstrate RP2G's superior performance (see https://drive.google.com/file/d/1VKnmT5_Wzpj6PwH_UbHImimhrhKBpVgq/view?usp=sharing). Our results show that the policy obtained by solving the non-rectangular RAMDP is less conservative (see our reply to **Reviewer sWdH, Comment 1** for a detailed explanation). We will evaluate our algorithms on other benchmarks in the next version of this paper.\n\n**_Comment 4: Typos._**\n\nThank you for pointing out the typos. We will update our paper according to these suggestions!\n\n**_Question 5: Could you incorporate the estimation error of Algorithm 3 into the overall convergence bound in Theorem 3.5?_**\n\nThank you for raising this important question. We would like to emphasize that the theoretical guarantee for RP2G (Theorem 3.5) accounts for the inner output error ($\\delta_{t}$ at $t$-th iteration). However, unlike Algorithm 2 for the inner problem, which features a simple and effective structure for updating the inner transition kernel, Algorithm 3 employs Monte Carlo sampling to achieve a probabilistic convergence guarantee, which introduces additional estimation error. Therefore, incorporating this estimation error from Algorithm 3 (as detailed in Theorem 4.6) into a deterministic convergence guarantee (shown in Theorem 3.5) remains challenging. We believe that investigating the overall convergence bound while accounting for the inner worst-case evaluation error is an interesting direction for future work that could further enhance the significance of our results.\n\n**_Question 6: What makes average-reward MDPs so different from discounted MDPs?_**\n\nThis difference arises in both theory and practice. While the RAMDP be seen as a special case of the RMDP ($\\gamma=1$), extending the theoretical framework from the discounted setting to the average-reward setting is non-trivial (see our reply to **Reviewer iYjz, Comment 2** and [3] for a detailed explanation). In practice, many real-world systems prioritize steady-state or long-term behaviour, where policies derived from discounted MDPs may perform poorly (see Introduction line 37-48).\n\n**_Question 7: Is the mixing time important to the theoretical analysis?_**\n\nAt this stage, the mixing time is crucial for bounding the differential (action) value function, which plays a key role in establishing Lipschitz continuity and the gradient dominance condition.\n\n**_Question 8: Is this approach potentially adaptable to discounted MDPs or episodic MDPs?_**\n\nThank you for this insightful question. Regarding the discounted MDPs, [4] already proposed methods with a double-loop structure for solving RMDPs. However, extending our approach to episodic MDPs seems challenging, as the ergodicity assumption does not hold in this setting, preventing a direct application of our theoretical framework. Developing a suitable policy gradient framework for episodic MDPs remains an important direction for future research.\n\n[1] Lamperski, A. 2021. Projected stochastic gradient langevin algorithms for constrained sampling and non-convex learning.\n\n[2] Sun, Z., He, S., Miao, F., \\& Zou, S. 2024. Policy optimization for robust average reward mdps.\n\n[3] Kumar N, Murthy Y, Shufaro I, et al. 2024. On the global convergence of policy gradient in average reward markov decision processes.\n\n[4] Li M., Kuhn, D., \\& Sutter T. 2023. Policy gradient algorithms for robust mdps with non-rectangular uncertainty sets.", "claims_and_evidence": "All claims are supported by concrete results.", "methods_and_evaluation_criteria": "The algorithm makes intuitive sense, and the evaluation method is reasonable.", "theoretical_claims": "The theoretical results are supported by proofs that are checked to be correct.", "experimental_designs_or_analyses": "Since this is mostly a theory-oriented paper, the numerical simulations only act as a supporting evidence. For this purpose, the experimental design and results look good to me.", "relation_to_broader_scientific_literature": "N/A", "essential_references_not_discussed": "N/A", "other_strengths_and_weaknesses": "Strengths:\n1. The paper is overall well-written. Algorithms are sufficiently motivated and introduced with intuitive ideas.\n2. Theoretical results presented in the main text, though lacking quite a few technical details, are largely self-explanatory and convincing.\n    * It's delightful to see the nice symmetry between the sensitivity in $\\boldsymbol{\\pi}$ and that in $\\boldsymbol{p}$.\n\nWeaknesses:\n1. The discussion regarding the projected Langevin dynamics that solves $\\Psi(\\pi)$ for general ambiguity sets is a little too hand-wavy. Basically no technical details are provided in the paper (including the appendix). The current Section 4.3 also does not fit into the flow very well.\n    * After a quick look, (Lamperski, 2021) is a very technical paper that deals with generic non-convex learning. Hence technical details are definitely needed here to show how it fits into the average-reward MDP setting.\n    * It is a little weird to see \"... is the first ...\" after results cited from other papers, without further explanations.\n2. The numerical experiments can preferably be extended to include more common benchmarks.", "other_comments_or_suggestions": "1. There are a few typos observed during reading.\n    * On line 715: does \"DFunctions\" mean \"diffusion value functions\"?\n    * In Lemma 4.2: \"is\" should be \"are\".", "questions_for_authors": "1. Currently the theoretical guarantee for RP2G (Theorem 3.5) is isolated from that for the adversary gradient ascent (Theorem 4.6), in the sense that the former does not take the estimation error of the inner problem into consideration. Is it possible to incorporate this estimation error into the overall bound, probably using some quick fixes?\n2. Honestly I'm not very familiar with average-reward MDPs. What makes average-reward MDPs so different from discounted MDPs? Is it the mixing property and the upper bounds involving mixing time that is key to the theoretical analysis? Is this approach potentially adaptable to discounted MDPs or episodic MDPs?", "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": {"ethical_review_concerns": "N/A"}}, {"review_id": "ijYhvgnfnA", "reviewer": "Reviewer_zvi6", "summary": "The studies very sparsely studied topic of average reward robust MDPs. Specifically, the paper establishes global convergence of robust policy gradient (RPG) for average reward MDPs with an iteration complexity of $O(\\epsilon^{-4})$ given oracle access to the robust gradient. This paper combines the techniques of RPG in discounted reward MDP [1] and convergence policy gradient for average reward MDPs [2].\n\nIn addition, this paper improves the smoothness coefficient for average reward MDPs over existing result in [2].  The paper is well written.\n\n\n\n\n[1] Wang, Q., Xu, S., Ho, C. P., and Petrick, M. Policy gradient for robust markov decision processes. arXiv preprint\narXiv:2410.22114, 2024a.\n\n[2] Kumar, N., Murthy, Y., Shufaro, I., Levy, K. Y., Srikant, R., and Mannor, S. On the global convergence of policy gradient in average reward markov decision processes.arXiv preprint arXiv:2403.06806, 2024b.", "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": "Thank you for your insightful questions and taking the time to assess our manuscript.\n\n1. **_Comment 1: Additional clarification in proofs could be helpful ._**\n\nThank you very much for providing helpful suggestions on writing style and missing clarification! We will clarify the wording in the next version of our manuscript, including more detailed explanations, to improve readability.\n\t\n2. **_Comment 2: Technical novelty need to be further elaborated._**\n\nWe'd like to emphasis that the extension from the discounted setting to the average-reward setting\nis non-trivial, even the average-reward MDP can be seen as a special case of discounted MDPs ($\\gamma=1$). Please see our reply to **Reviewer iYjz, Comment 2** and the introduction of [2] for a detailed explanation.\n\nFor the outer loop, we establish Lipschitz continuity via a novel sensitivity analysis and introduce a gradient dominance condition specifically tailored to the average-reward setting, leading to an outer-loop convergence guarantee. Compared to [2], we provide improved smoothness coefficients. While our approach adopts a double-loop structure, which is widely used in various fields such as game theory [3], min-max optimization [4,5], and robust MDPs [1], our analysis relies on standard non-convex minimax optimization techniques, which are significantly different from the mirror descent analysis used in [1].\n\nFor the inner loop, we propose two tailored algorithms for worst-case transition evaluation under both rectangular and non-rectangular settings, whereas [1] only addresses the rectangular case. To establish the inner-loop convergence guarantee, we derive the first form of the adversarial transition gradient (Lemma 4.1), establish first adversarial smoothness conditions using sensitivity analysis techniques (Lemma 4.3), and prove the first adversarial gradient dominance condition (Theorem 4.4), along with corresponding inner convergence guarantee.\n\nTherefore, our work differs substantially from both references [1,2]. Building on these theoretical advancements, our approach offers a comprehensive framework for addressing robust average-reward MDPs beyond existing methods. We will further clarify these contributions in the next version of our paper.\n\n[1] Wang, Q., Xu, S., Ho, C. P., and Petrick, M. Policy gradient for robust markov decision processes. \n\n[2] Kumar, N., Murthy, Y., Shufaro, I., Levy, K. Y., Srikant, R., and Mannor, S. On the global convergence of policy gradient in average reward markov decision processes.\n\n[3] Ding D., Wei C. Y., Zhang K., \\& Jovanovic M. 2022. Independent policy gradient for large-scale markov potential games: Sharper rates, function approximation, and game-agnostic convergence. \n\n[4] Jin C., Netrapalli P., \\& Jordan M. 2020. What is local optimality in nonconvex-nonconcave minimax optimization?\n\n[5] Davis D., \\& Drusvyatskiy D. 2019. Stochastic model-based minimization of weakly convex functions.", "claims_and_evidence": "Yes, seems good.", "methods_and_evaluation_criteria": "Yes, seems good.", "theoretical_claims": "I went over all the proofs but not in great details. All seems good.", "experimental_designs_or_analyses": "No.", "relation_to_broader_scientific_literature": "In RL, average reward MDPs has its own independent significance yet the most of the results are of discounted reward MDPs, due to the complexity of the setting. This work makes this gap little narrower.", "essential_references_not_discussed": "All seems good.", "other_strengths_and_weaknesses": "Strengths: Good theoretical results of significance.\n\nWeakness: The proofs are well presented (above average), however a little more clarification on the maths proofs would be beneficial to the readers.", "other_comments_or_suggestions": "Suggestion: A more readable proofs would be beneficial to the readers.", "questions_for_authors": "Question: This paper is direct combination of [1] and [2]. Please elaborate on the technical novelty.", "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 studied robust MDP in the average reward setting. The  paper proposes a policy gradient based algorithm for robust average-reward MDPs (RAMDPs) that is applicable beyond the typical rectangularity assumption on transition ambiguity. Convergence analysis of the proposed algorithm is presented, and numerical experiments are conducted to support some of the claims of the paper. 

After rebuttal, the reviewers are leaning to the positive side. But there are still several concerns. One concern is on the novelty side of the work when comparing to prior works. Particularly, multiple reviewerrs think the technical novelty possessed in the proof seems marginal based on existing tools in average-reward MDPs and the generic method proposed for robust MDPs with non-rectangular ambiguity sets. During the rebuttal, one reviewer also mentioned a few related work. The authors probably should include the detailed discussion to these prior works into the revised version.
Decision: Accept (poster)