Policy Optimization for Robust Average Reward MDPs
Authors: Zhongchang Sun
Sihong He
Fei Miao
Shaofeng Zou
Venue: NeurIPS 2024 poster (2024)
Keywords: Reinforcement learning
average reward
model mismatch
Primary area: reinforcement_learning

Abstract: This paper studies first-order policy optimization for robust average cost Markov decision processes (MDPs). Specifically, we focus on ergodic Markov chains. For robust average cost MDPs, the goal is to optimize the worst-case average cost over an uncertainty set of transition kernels. We first develop a sub-gradient of the robust average cost. Based on the sub-gradient, a robust policy mirror descent approach is further proposed. To characterize its iteration complexity, we develop a lower bound on the difference of robust average cost between two policies and further show that the robust average cost satisfies the PL-condition. We then show that with increasing step size, our robust policy mirror descent achieves a linear convergence rate in the optimality gap, and with constant step size, our algorithm converges to an $\epsilon$-optimal policy with an iteration complexity of $\mathcal{O}(1/\epsilon)$. The convergence rate of our algorithm matches with the best convergence rate of policy-based algorithms for robust MDPs. Moreover, our algorithm is the first algorithm that converges to the global optimum with general uncertainty sets for robust average cost MDPs. We provide simulation results to demonstrate the performance of our algorithm.

Policy Optimization for Robust Average Cost MDPs
Zhongchang Sun University at Buffalo zhongcha@buffalo. edu
Sihong He University Texas at Arlington sihong hww.ta.uuhcccc..ee edu
Fei Miao University of Connecticut fei www.oucoon edu
Shaofeng Zou Arizona State University zou@asu. edu
Abstract
This paper studies first-order policy optimization for robust average cost Markov decision processes (MDPs). Specifically, we focus on ergodic Markov chains. For robust average cost MDPs, the goal is to optimize the worst-case average cost over an uncertainty set of transition kernels. We first develop a sub-gradient the robust average cost. Based the sub-gradient, robust policy mirror descent approach is further proposed. To characterize its iteration complexity, we develop a lower bound on the difference of robust average cost between two policies and further show that the robust average cost satisfies the Lojjs---jjsiiiiizz (PL)-condition. We then show that with increasing step size, our robust policy mirror descent achieves a linear convergence rate in the optimality gap. and with constant step size, our algorithm converges to an e-optimal policy with an iteration complexity of (11cc.. The convergence rate of our algorithm matches with the best convergence rate of policy-based algorithms for robust MDPs. Moreover, our algorithm is the first algorithm that converges to the global optimum with general uncertainty sets for robust average cost MDPs. We provide simulation results to demonstrate the performance of our algorithm.
Introduction
Markov decision process (MDPs) 34 has been widely used model agent-environment interactions in sequential decision-making problems. An MDP consists of set of states, set of actions, transition kernel describing the dynamics of the enviromment, and cost function of state-action pairs. The agents aim to minimize the cumulative cost obtained over time under given transition kernel. However, real-world environments often exhibit uncertainties and non-stationarity that challenge the assumptions of traditional RL approaches. When there is a mismatch between the training environment and the real environment, minimizing the cumulative cost under the training environment may lead to poor performance under the real environment.
To address the challenges raised by the model mismatch, the robust MDP was proposed 3 where the transition kernel of the MDP is not fixed but lies in an uncertainty set. The goal of the robust MDP is to optimize the worst-case performance over the uncertainty set of transition kernels. The obtained policy under the robust setting is thus robust to the model mismatch.
Existing works robust MDPs mainly focus the discounted cost setting, where the goal is to minimize the worst-case cumulative discounted cost. However, in many real-world applications with long time horizons, such inventory management in supply chains and applications in communi- cation networks [16]. the optimal policies obtained from the discounted cost setting may have poor long-term performance [[5].
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

To address these challenges, recent research has shifted focus towards robust average cost MDPs, where the objective to optimize the worst-case average cost obtained per time step. The average cost MDPs offer several advantages over discounted cost MDPs, including better stability and applicability to
tasks. However, achieving robust and efficient learning in average cost settings remains significant challenge. Since the cost is discounted exponentially with time in discounted cost MDPs, establishing a contraction only requires a discount factor strictly less than one. Compared with discounted cost MDPs, average cost MDPs depend on the long-term performance of the underlying MDPs as it assigns equal weight to both immediate and future costs. Research on robust average cost MDPs is relatively scarce in the existing literature, with only few notable works focuses on the
studies, such as those by 36 22 fundamental characterization of gradient- based algorithms. Therefore, in our paper, we present the first theoretical analysis of the global convergence of policy optimization algorithms in the context of robust average cost MDPs with general uncertainty sets.
39
40 [2]. None of the
1.1 Main Contributions
In this paper, for ergodic Markov chains, we propose a policy-based optimization algorithm called robust policy mirror descent to solve the robust average cost MDPs. We further show that with increasing step size, our robust policy mirror descent achieves linear convergence in the optimality gap, and with constant step size, our algorithm converges to an e-optimal policy with iteration complexity of (1/e). Our algorithm is the first policy-based algorithm with global convergence and finite iteration complexity analysis for robust average cost MDPs with general uncertainty sets. In particular, our main contributions are summarized as follows.
We derive a policy (sub)-gradient for the robust average cost MDPs. In robust average cost MDPs, the goal is optimize the worst-case performance, known the robust average cost, which considers the worst-case over the uncertainty set of transition kernels. However, the robust average cost function typically involves "max" operator over transition kernels, making it non-differentiable with respect to the policy. Therefore, in this paper, we first develop the Fréchet sub-gradient of the robust average cost with general uncertainty sets, which serves as a foundation of the policy-basee based algorithm. The robust policy gradient under the discounted setting was derived in [42] [2]. The work 42] considers the specific R-contamination uncertainty set, and the derivative of the robust policy gradient in [2]] relies on the fact that the discount factor is strictly less than 1, which can not be extended to the average cost setting.
We propose a robust policy mirror descent algorithm. Based on the derivative of the Fréchet sub-gradient, we propose the robust policy mirror descent algorithm. We apply the dynamically weighted divergence to the policy mirror descent so that the policy can be updated for each state separately, which further ensures global convergence.
We show that our algorithm converges to the global optimum, and we further characterize the iteration complexity. To show the global convergence, we first prove that the robust average cost satisfics the algorithm and characterize its iteration complexity. We show that with increasing step size, our robust policy mirror descent achieves linear convergence in the optimality gap, and with constant step size, our algorithm converges to an c-optimal policy with iteration complexity O(1/c). For increasing step size, the linear convergence of our algorithm matches with the robust discounted cost setting [21]. In (1], the robust policy mirror descent was shown converge the global optimum with iteration complexity (1/e) for discounted cost MDPs when the step size is sufficiently large. Conversely, for non-robust discounted cost MDPs, the policy mirror descent was demonstrated achieve a O(1/e) iteration complexity in 45 representing the state-of-ther the-hat art convergence rate for policy mirror descent with a constant step size. Therefore, the convergence rate of our algorithm matches with the performance of the best non-robust counterpart. The convergence analysis of policy- baased algorithms for non-robust MDPs relies on the fact that the value function is smooth, which not the case for the robust average cost function. In this paper, we combine the first-order optimality condition of the policy update and the PL condition develop a novel proof for the convergence rate of our algorithm.
(PL) condition 22 23], We then prove the global optimality of our
1.2 Related Works
In this section, we discuss works on policy-based approaches for non-robust MDPs, robust discounted cost MDPs and robust average cost MDPs
2

---

Policy-based approaches for non-robust MDPs. In the non-robust setting, policy-based algorithms
44 35
T7
31 32] have demonstrated remarkable success across various applications. Recendy.
the global convergence of the policy-based algorithms were established 4 S I
24
20
19
49
9
48
45]. For discounted cost MDPs, was shown in [1] that the projected gradient descent converges to a
global optimum with iteration complexity (1)c²). In both [4]] and 45, the authors show that the
projected gradient descent converges to a global optimum with a less iteration complexity (1/e).
For average cost MDPs, [18] presents sublinear convergence bound for projected gradient descent, where the bound involves the parameter that characterizes the complexity of the underlying MDP. In all the above works, the convergence analysis depends the smoothness of the value function. However, since the smoothness may not hold for the robust value function, the methodologies applied in D 48 45 [8] can not be extended to case. The policy mirror descent with increasing step size was shown to achieve linear convergence in [45]. The policy mirror descent with constant step size was also proved converge with iteration complexity (1)cc) for discounted cost MDPs in [45] Their proof relies on the performance difference lemma and the fact that the underlying transition kernel doesn't 't change with time. In this paper, we derive the policy sub-gr sub-gradient for robust average cost MDPs and design the robust policy mirror descent. We then develop a lower bound on the difference of robust average cost between two policies and further combine it with the first-order optimality condition of the policy update to characterize the iteration complexity of our algorithm.
Robust discounted cost MDPs. Robust discounted cost MDPs have been widely studied [3] 27 41
| 21 46 28 33), where the goal is to minimize the worse-case cumulative discounted cost over the uncertainty set of transition kernels. In this section, introduce works on volicy-based algorithms, which are closely related to our work. In [42], the robust MDPs are considered under the R-contamination uncertainty set and the robust policy gradient algorithm is designed. It is shown in (38] that the robust policy gradient algorithm converges to the global optimum with iteration complexity (11/e)). Later in (38), the double-loop robust policy gradient was proposed for general uncertainty sets and was further proved to converge to the global optimum with iteration complexity 0(1/4). The robust policy mirror descent was designed for discounted cost MDPs in (2T] With increasing step size, the robust policy mirror descent converges linearly to the global optimum, while with constant but sufficiently large step size, the algorithm converges the global optimum with iteration complexity (1/e). In this paper, we study the average cost setting and show that with increasing step size, the robust policy mirror descent achieves linear convergence, and with constant step size, our algorithm converges to the global optimum with iteration complexity ((1/c), which matches with the best achievable iteration complexity of policy- based algorithms for robust MDPs. For the case with constant step size, our analysis doesn't 't require the step size to be sufficiently large.
Robust average cost MDPs. Existing literature that focuses on robust average cost MDPs is relatively limited. The robust average cost MDPs were initially explored by R6] where a specific finite interval uncertainty set was considered and the (1/cc convergence rate was achieved. In [22]. the robust average cost MDPs were studied under the 4 uncertainty set. However, the approaches in [36] 22 are not applicable for general uncertainty sets. Later in [39 40 [2]. algorithms were proposed and the global convergence was proved. In [12], the connection are built between the discounted reward MDPs and average reward MDPs and the existence of Blackwell optimal policies are proved. In (39 40) the model- based and model-free robust average reward MDPs are studied and the robust relative value iteration algorithms are proposed. However, finding stopping criterion and characterizing the iteration complexity for robust value iteration based algorithms remain elusive. In this paper, we propose the first policy-based algorithm for robust average cost MDPs We show that our algorithm converges to the global optimum and we further characterize its iteration complexity. Therefore, our algorithm is the first algorithm with finite iteration complexity analysis for robust average cost MDPs with general uncertainty sets.
the robust value iteration based
Exponential cost robust MDPs. For the robust average cost MDPs, when the uncertainty set is defined by the KL-divergence metric, the problem admits a dual formulation, which is the exponential cost robust MDPs The exponential cost robust MDPs have also been studied in the literature. In [6], the Q-learning and the actor-critic method are described and the asymptotic performance are characterized for risk sensitive robust MDPs. In [7], the value iteration and policy iteration algorithms are also analyzed for risk sensitive MDPs. Recently, in (26). the modified policy iteration is proved to converge to the global optimum for exponential cost risk sensitive MDPs. The policy gradient algorithm for the risk sensitive exponential cost MDPs is studied and the asymptotic convergence
3

---

bounds to a stationary point are provided in 225 In our paper, we study the robust average cost MDPs with general uncertainty sets and characterize the global convergence of our algorithm.
2
Preliminaries and Problem Formulation
In this section, we introduce some preliminaries on discounted cost MDPs, average cost MDPs and present our problem formulation.
2.1 Discounted Cost MDPs
discounted cost MDP is defined by the tuple (S, A, P.r.)), where S denotes the finite state space, A denotes the finite action space, P (P: A(8), s E S,a A is the transition kernel, r: 8 x A + [0, 1] denotes the cost function, and E 1) is the discount factor. Denote by the number of states and A the number of actions, respectively.
We consider the set of all stationary and randomized policies II = :
A(A)) For each policy æ, it maps from state E 8 to distribution over action a A. At each state 8, the agent takes action a with probability π (als), and the environment transits from state to state s' according to P.. The discounted value function of policy л starting from initial state is defined as
P.y (8)
Ep
7'r(Sts az)]s0 =
where Ep denotes the expectation with respect to the distribution induced by the transition kernel P. To align with conventions in the optimization literature, in this paper, we adopt minimization formulation. For discounted cost MDPs, the goal is find a policy æ that minimizes the discounted value function VP, (s) for any initial state
2.2 Average Cost MDPs
Average cost is another fundamental criterion for MDPs. For discounted cost MDPs, the agent penalizes the future cost with discount factor demonstrate the preference for the current cost. The average cost MDPs focus on the long-term performance of the underlying MDPs under the steady-state distribution. The average cost MDP can be defined by the tuple (8, A, P,r). For policy π, define the average cost under transition kernel P starting from an initial state 8 as follows
go(s)
2 lim Ep T-000
Σ
r(se, ac) = =,
(2)
We also define the relative value function Vp and the relative state-action value function Q3 for average cost MDPs as follows
(s) A Ep
(r(s a.) - gā) |so
(s, a) A Ep
(r(st, (z) - g 1s0 8, 0g a,
The relative value function VPr and the average cost of satisfy the following Bellman equation 30
(s) Σ x(als)(F(s,a) (5) Σ P (F)(s)),
where P denotes the probability of transiting to state s' when choosing action state Let dg denote the stationary probability induced by the policy and transition kernel P. and it satisfies that dpp = dz. Similar as [18), we consider the projection of the value function onto the subspace orthogonal to the vector so that V and QF are unique. For average cost MDPs, the goal is find policy π that minimizes the average cost (s) for any initial state s.
(8) denotes the probability simplex detined 8.

---

2.3 Robust Average Cost MDPs
For robust MDPs, the transition kernel P is not fixed but lies in some uncertainty set P. Define the robust average cost MDP by the tuple Prr). In this work, we consider a) ( rectangular uncertainty set:
Po Pe {1 A(8): D(g (Po).) S R), 3,0
where Po is known nominal transition kernel, D measures the difference between two distributions, e.g., KL divergence, and R is the pre-specified radius of the uncertainty set.
For robust average cost MDPs, the agent aims to optimize the worst-case performance over the uncertainty set Define the worst-case average cost as follows
(g)
max lim Ep PEP
Σ T t=0
r(tt. 0c) 8,
(6)
T
Similarly, we denote by V and QT the robust relative value function and the robust relative state action value function, respectively. The robust relative value function V and the robust average cost 9ß satisfy the following Bellman equation (39].
(8)
Σ T(als)(r(ssa) - (5()) + max aEA
Σ V7 8'ES
PEP
For any policy т, denote by dip the stationary distribution of the state under the worst-case transition kernel и. The goal is to find a policy т such that the worst-case average cost g is minimized, i.c., min (s), for any s E S. FEll
(8)
Denote the optimal policy by Æ² and the robust average cost of by g In this paper, we state the following assumption to guarantee that the average cost is independent of the initial state, which is widely used in the studies of average cost MDPs 43 50 TO 37 39 40).
Assumption 2.1. For any π II and P E P, the induced Markov chain is ergodic.
3 Robust Policy Mirror Descent
In this section, we first derive the robust average cost policy gradient. We then propose the robust policy mirror descent algorithm.
3.1 Robust Average Cost Policy Gradient
Since the worst-case average cost o takes "max" over all P P, 9it might not be differentiable. To address this issue, we introduce the concept of Fréchet sub-gradient. Let || denote the L2 norm of vector.
Definition 3.1. For any function f : x C RRN. + IR the Fréchet sub- mub-gradient u E RRN is a vector that satisfies
f(x + 5) f()) (u. 20.
lim inf 8-0
(9)
||8||
When ff is differentiable at x, the Fréchet sub- uub-gradient u is the gradient of f. In this paper, we consider the direct policy parameterization. We derive the sub-gradies gradient for the robust average cost 9i in the following lemma.
Lemma 3.2. Let V (s) = (s)) a). Then V is the Fréchet sub- bub-gradient of 9T-
Note that the Fréchet sub-gradient has been derived for robust discounted cost MDPs 21,, of which the (s, a) entry takes the form - (s) (7,7,,, a). Here, with little abuse of notation, we use d. to denote the visitation distribution of policy π under the worst-case transition kernel and use Q to denote the worst-case action value function of policy x. The Fréchet sub aub-gradient for robust discounted cost MDPs in (1 can not extended to the average setting since in [21]. the discounted factor 7 is required to be strictly less than 1. In this paper, we derive the Fréchet bub-gradient of robust average cost MDPs by applying the performance difference lemma for average cost MDPs and the Lipschitz property of the relative action value function (18).
5

---

Algorithm Robust Policy Mirror Descent
Input: step size T/k, initial policy no
for 0, 1,,,,.., K do for s E 8 do
Update policy: T (-1s) = arg min pEa()) {Th (s, + D(p, (x(-)))
end for end for Output: πK
3.2 Robust Policy Mirror Descent
With Lemma 3.2 we are ready to present our robust policy mirror descent algorithm for average cost MDPs. We assume that for given policy there exists oracle that outputs the robust relative state action value function Q7- We denote by (+r(-1)), x x((+ss) the Bregman divergence between two policies r--ss) and T' (-1s). We further define the weighted Bregman divergence function Da(m, T') =
E.gs D(s) T (+1s)) for any E A(8). We define the following robust policy mirror descent with dynamically weighted divergence
T arg min (v . + D Dage (T, (T,
(10)
where is the step size. Note that 97 might not be differentiable, thus in our algorithm we replace the gradient of gip by its Fréchet sub- araggradient Vgp. By plugging in the sub-gra uub-gradient formula of g in Lemma 3.2] we have that
TJ Σ de (s, (-{s)) + Dage (T, mb)} SE8
Th++1 arg min WEll
arg min well
(nx (s.)). D((((l))) [x((ss))))(())))) T-(-1s))
(11)
#ES
which is equivalent to
Tk+1(1s)) arg min
( (nx (s.)).) + D(p, (())) Es
(12)
PEA(A)
We summarize our algorithm in Algorithm
Note that for the projected policy (sub)-gradient algorithm, the policy is updated as follows
mh+ (-1s) arg min
mm (V (8,)), + lp TA (-bs))) Vs E
(13)
PEA(A)
In paper, set the Bregman divergence D).,)) :) to be the squared Euclidean distance. In this case, the difference between our robust policy mirror descent and the projected policy gradient lies in that we replace the policy subb)-gradient Vg by 1
In the next section, we show that though the robust average cost g might not be differentiable, our robust policy mirror descent achieves linear convergence in the optimality gap with increasing step size, and converges to an e-optimal policy with iteration complexity (11/e) with constant step size.
4 Theoretical Results
Before we show the global optimality of the robust policy mirror descent, we first provide some important properties of the robust average cost MDPs.
We first provide a lower bound on the difference of robust average cost between two policies, which key step derive the global optimality.
Lemma 4.1. For any two policies n², we have that gip 93 2 E Baway ((QT(s.))

---

Lemma 4.1 is not straightforward extension of performance difference lemma 8 to the robust setting since the worst-case transition kernels are different for different policies. A similar bound was derived in [2]] for robust discounted value function by applying the Bellman equation of robust value function, which is not applicable in our case as the average cost itself does not satisfy the Bellman equation. Therefore, we apply the Bellman equation of the robust relative value function V and the robust average cost 93 in ( and the observation that g is independent the initial state s to obtain Lemma 4.1
We then show that the robust average cost gh satisfies the PL-condition in the following lemma.
Lemma 4.2. The suboptimality of any satisfies dj. 9 CpL max; Vgg. f),, where
Cpr. max,,e (+)
(8)
The PL-condition implies that when the subgradient V Vgjj is small, the policy л lies in the small neighborhood of the global optimum.
Our convergence analysis also leverages the following Lipschitz property of the non-robust relative value function VP [8]
Lemma 4.3. The relative value function Vp is Lipschitz in æ, i.e, there exists constant L,, such that [V
V < T1=||T - Tl|.
4.1 Increasing Step Size
In this section, we show that our algorithm achieves linear convergence rate with increasing step size. We first characterize some properties of our robust policy mirror descent algorithm. Lemma 4.4. For any p II and
we have that
mps (Q7" (s, T4+1 (-1s) - p(-1s)) + || (-1s) (-|s)]|2
< [|((|s) (+1s))) (1p(-ss) (141(11))13
(14)
In the following lemma, we establish the convergence property for each iteration of our algorithm. Lemma 4.5. At each iteration of our algorithm, we have that
97
93 1
M
(gg) Th
E, s--dp" 176
[-11 (-1s) m (11s))]
M
1
T (-1s) TT41 (-1))-1)))1
(15)
M
7/k
where M = SuP
We show that with increasing step size, our robust policy mirror descent converges linearly.
Theorem 4.6. Under Assumption 2.1 set the step size Tle 2 πk-1
1 N5
M. The robust policy
mirror descent satisfies
9
gip (1
Φ6) (1
R-1
E aa MTo
[1|s( (o] (16)
M
Our analysis in this section mainly leverages the performance difference lemma [ and the Bregman divergence three-point lemma. The convergence rate for our robust policy mirror descent with increasing step size matches with the best convergence rate of policy-based algorithm for robust MDPs 21 Our algorithm is the first algorithm that converges to the global optimum with finite iteration complexity for robust average cost MDPs with general uncertainty sets.
4.2 Constant Step Size
proceed to show that with constant step size, our algorithm achieves the global optimum with iteration complexity (1/e).
7

---

Theorem 4.7. Under Assumption 2.1 let step size 17 iteration of the robust policy mirror descent satisfies
Ln for all k 2 1. We have that the each
1
( ALx wk
/2
Th 98
9 - max
(9 - 9
(17)
2
where w (2/2SCrz)-²
For Algorithm to find an c-optimal policy, Theorem 4.7 shows that the iteration complexity is upper bounded by O(1/c). In [21], the robust policy mirror descent studied for discounted cost MDPs. The iteration complexity (1/c)) in [2]] can only be achieved with a sufficient large step size Th = 1/c. For the non-robust discounted cost MDPs, the policy mirror descent was shown to enjoy (1/e)) iteration complexity in [45], which is the state-of-the-ard convergence rate for policy mirror descent with constant step size. Our robust policy mirror descent with constant step size converges to the global optimum with iteration complexity ((1/e), which matches with the best non-robust counterpart 45).
Define the gradient mapping G (TT(- = 7 (Tx(+1)) - (-+1(-1s)). Note that Ty. is updated exactly by the -sabe-gradient descent, then G (mx((11)) Vgz (). The norm ||G (+x(+)))) measures the closeness of the current step to the first-order stationary point. Our proof relies on the following key ingredient.
96
9p 2 snd ro+1 [lG (Tx (+1)))1 2 wh(sp T - -gp)²
(18)
In [1 45. similar steps are adopted to derive the convergence rate of the policy gradient descent for non-robust discounted cost MDPs. In their analyses, obtain (18), the smoothness of the value function is required. However, since the worst-case transition kernel is a function of the policy æ, the robust average cost o might not be smooth. Therefore, the approaches applied in 1 451 can not be directly extended to robust average cost MDPs. Without the smoothness of the value function, we still prove that (18) holds by leveraging Lemma /. and the following first-order optimality, which is from the optimality condition of the robust policy mirror descent update in (12)
1
(s,-))
- (Tx+ mo(-1))), Th. (1+1(-1)) 2 0, Vp A(A).
(19)
TJk
Remark 4.8. Since for robust discounted cost MDPs, Lemma 4. Lemma 4.2 and Lemma 4.3 also hold, the result in Theorem[4.Jalso holds for robust discounted cost MDPs. Therefore, our robust policy mirror descent with constant step size finds an e-optimal policy with iteration complexity (1/e) for robust discounted cost MDPs. Compared with (21), our step size doesn't 't need to be sufficiently large.
Simulation Results
In this section, we provide some simulation results to demonstrate the performance of our algorithm. We verify our method on one classical problem: the Garnet problem, and robotic application problem: the recycling robot problem.
Garnet environments are synthetic benchmarks designed to be used for studying the performance of RL algorithms. The Garnet framework provides way to create randomly generated MDPs with specified properties, such as the number of states, actions, and transition probabilities. More details can be found in (2).
In the recycling robot problem, mobile robot powered by rechargeable battery is tasked with collecting empty soda cans. The robot operates with two battery levels: low and high. It has three possible actions: (I) search for empty cans; (2) remain stationary and wait for someone to bring it a can; or (3) return to its home base to recharge. When the robot's 's battery is low (high), it has a empty can and maintaining its current battery level. If the robot searches for cans but does not find any. will deplete its battery completely and must be carried back by humans. For more details, refer to (34 In this paper, we a 0.9, B 0.9.
probability of (3) of finding
We compare our robust policy mirror descent with the non-robust method 45 We consider Garnet(3, 2), Garnet(5, 2). Garnet(10, 5) and recycling robot problems. Both methods use uniform random

---

0.-
04-
35-
Acouse simor
RoDL PUPSI/y Niierr CINCRRT
bauther
Figure I: Garnet(3, 2)
Figure 2: Garnet(5, 2)
075
1.-
16-
0.99
1.2
045
00-
500
1hs
Figure Gamet(100 5)
Figure 4: Recycling Robot
policy as the initialized policy. We conducted 5 trials with different random seeds and reported mean and standard deviation of the robust average costs over training episodes. Each training episode contains 2000 training steps. The length of training episodes respectively 100 and 300 for Garnet and robot problems. We choose the uncertainty set to be the KL divergence uncertainty set. We consider the constant step size and set the step size 1) = 0.01, the pre-specified radius of the uncertainty set I = 0.1. The host machine used in our experiments is a server configured with AMD Ryzen Threadripper 2990WX 32-core processors and four Quadro RTX 6000 GPUs. All experiments are performed on Python 3.8.
Figure I showcases the mean values of the optimal robust average cost values and standard deviations for our robust method and the non-robust baseline over the training episode in Garnet(3, 2). Our robust method converges faster than the non-robust baseline, though these two methods converge the same value. We speculate that the reason why the two methods converge to similar numbers is further compare our robust method
because this MDP environment has small size. Therefore, with the non-robust baseline in two larger Garnet problems Garnet(5, 2) and Garnet(10) 10, 5), and the recycling robot problem. Figure 2 3 and 4 respectively show the mean optimal robust average cost and standard deviations in these three problems. From Figure 2 B and 4 we find that our robust method outperforms the non-robust baseline in terms of mean costs all three problems. The simulation results demonstrate the robustness of our algorithm.
Conclusion
In this paper, we investigated the policy-based algorithm for robust average cost MDPs. We first introduced the sub-gradient of the robust average cost. Based on the sub-gradient, we proposed the robust policy mirror descent. Our theoretical analysis demonstrates that the proposed algorithm with increasing step size achieves linear convergence rate, and with constant step size, the proposed algorithm finds an c-optimal policy with iteration complexity (1/c), matching the best convergence rate observed in policy mirror descent algorithms for robust MDPs. Moreover, our algorithm the first algorithm that converges to the global optimum with finite iteration complexity for robust average cost MDPs with general uncertainty sets. Our paper focuses on the model-based setting. In the future, it is of interest to design -bsed model-free free algorithms for robust average cost MDPs.

---

7 Acknowledgements
The work of Zhongchang Sun and Shaofeng Zou is supported by the National Science Foundation under Grants CCF-2438429 and ECCS CCCSS2233392 (CAREER). The work of Sihong He and Fei Miao supported by the National Science Foundation under Grants CNS-2047354 (CAREER), and the New England University Transportation Center (NEUTC). Funding for the UTC Program is provided by the Office of Assistant Secretary for Research and Innovation (OST-R) of the United States Department of Transportation. The recommendations of this study are those of the authors and do not represent the views of NEUTC.
10

---

References
[1] A. Agarwal, S. M. Kakade, D. Lee, and G. Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift. Journal of Machine Learning Research, 22(98))1-76, 2021.
[2] T. Archibald, K. McKinnon, and I.. Thomas. On the generation of Markov decision processes. Journal of the Operational Research Sociery, 46(3):354-361, 1995.
[3] K. P. Badrinath and D. Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In Proc. International Conference on Machine Learning (ICML), pages 51 1-520. PMLRR 2021.
[4] Bhandari and D. Russo. Global optimality guarantees for policy gradient methods, arXiv N00iv::900.0000 0eee//9060.7800 0178,, 2019.
preprint Xrvi
[5] J. Bhandari and D. Russo. On the linear convergence of policy gradient methods for finite MDPs. In Proc. International Conference on Artifical Intelligence and Statistics (AISTATS), pages 1388623994 PMLR, 2021.
[6] V. S. Borkar. Learning algorithms for risk-sensitive control. In Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems-MTNS, volume 5, 2010.
[7] V.S. S. Borkar and S. P. Meyn. Risk-sensitive optimal control for markov decision processes with monotone cost. Mathematics of Operations Research, 27(1):192-25) 2002.
[8] R. Cao. Single sample path-based optimization of markov chains. Journal of optimization theory and applications, 100:527-548, 1999.
[9] S. Cen, C. Cheng, Y. Chen, Y. Wei, and Y. Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 2021.
[10] L. Chen, R. Jain, and H. Luo. Learning infinite-horizon average-reward markov decision processes with constraints. arXiv preprint 2rXiv:2202.00155. 2022.
[11] Dong, Li, B. Wang, and J. Zhang. Online policy optimization for robust mdp. arXiv preprint arXiv:2209, 18441, 2022.
[12] J. Clemmnt,, M. Petrik, and N. Vieille. Beyond discounted returns: Robust markov decision processes with average and blackwell optimality, 2024.
[13] G. N. Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257- 280, 2005.
[14] S. M. Kakade. A natural policy gradient. In Proc. Advances in Neural Information Processing Systems (NIPS), volume 14, pages 1531-1538, 2001.
[15] M. Kazemi, M. Perez, F. Somenzi, S. Soudjani, A. Trivedi, and A. Velasquez. Translating omega- regular specifications average objectives for model-free reinforcement learning. AAMAS '22, page 732-741, Richland, SC, 2022. International Foundation for Autonomous Agents and Multiagent Systems.
[16] Kober, A. Bagnell, and J. Peters. Reinforcement learning in robotics: A survey. The International Journal of Robotics Research,
2013.
[17] V. R. Konda and J. N. Tsitsiklis. Actor-critic algorithms. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 1008-1014, 2000.
[18] N. Kumar, Y. Murthy, Shufaro, Y. Levy, Srikant, and S. Mannor. On the global convergence of policy gradient in average reward markov decision processes. arXiv preprint arXiv:2403. 06806, 2024.
[19] R. Laroche and R. T. des Combes. Dr jekyll & mr hyde: the strange case off-policy policy updates. In Proc. Advances in Neural Information Processing Systems (NeurIPS), 2021.

---

[20] G. Li. Y. Wei, Chi, Y. Gu, and Y. Chen, Softmax policy gradient methods can take exponential time to converge. arXiv preprint arXiv:2102.11270, 2021.
[21] Y. Li, G. Lan, and T. Zhao. First-order policy optimization for robust markov decision process. arXiv preprint urXiv:2209. 10579, 2022.
[22] S. H. Lim, H. Xu, and S. Mannor. Reinforcement learning in robust Markov decision processes.
In Proc. Advances in Neural Information Processing Systems (NIPS), pages 701-709, 2013.
[23] S. Lojusiewiez. A topological property of real analytic subsets. Coll. du CNRS, Les équations aux dérivées partielles, 117(87-89)2, 1963.
[24] J. Mei, C. Xiao, C. Szepesvari, and D. Schuurmans. On the global convergence rates of softmax policy gradient methods. In Proc. International Conference on Machine Learning (ICML), pages 6829. PMLR, 2020.
[25] M. Moharrami, Y. Murthy, A. Roy, and R. Srikant. A policy gradient algorithm for the risk- sensitive exponential cost mdp. Mathematics of Operations Research, 2024.
[26] Y. Murthy, M. Moharrami, and R. Srikant. Modified policy iteration for exponential cost risk sensitive mdps. In Learning for Dynamics and Control Conference, pages 395-406. PMLR, 2023.
[27] A. Nilim and L. El Ghaoui. Robustness in Markov decision problems with uncertain transition matrices. In Proc. Advances in Neural Information Processing Systems (NIPS), pages 939-846, 2004.
[28] K. Panaganti and D. Kalathil. Sample complexity of robust reinforcement learning with generative model. In International Conference on Artificial Intelligence and Statistics, pages 9582-9602. PMLR, 2022.
[29] B. T. Polyak. Gradient methods for minimizing functionals. Zhurnal vychislitel noi matematiki i matematicheskoi fiziki, 3(4):643-653, 1963.
[30] M. L. Puterman. Markov decision processes: Discrete stochastic dynamic programming, 1994.
[31] Schulman, Moritz, Levine, M. Jordan, and Abbeel. High-dimensional continuous control using generalized advantage estimation. arXiv preprint arXiv: w0X.:::500.02438,, 2015.
[32] Schulman, Wolski, Dhariwal, A. Radford, and O. Klimov. Proximal policy optimization algorithms. arXiv preprint TXXXvv1777.063444 2017.
[33] L. Shi, G. Li, Y. Wei, Chen, M. Geist, and Y. Chi. The curious price of distributional robustness in reinforcement learning with generative model. arXiv preprint arXiv:2305. 2023.
[34] R. S. Sutton and A. G. Barto. Reinforcement learning: An introduction. MIT press, 2018.
[35] R. S. Sutton, D. A. McAllester, S. P. Singh, Y. Mansour, et al. Policy gradient methods for reinforcement learning with function approximation. In Proc. Advances in Neural Information Processing Systems (NIPS), volume 99, pages 1057-1063. Citeseer, 1999.
[36] A. Tewari and P. L. Bartlett. Bounded parameter markov decision processes with average reward criterion. In International Conference on Computational Learning Theory, pages 263-277. Springer, 2007.
[37] Y. Wan, A. Naik, and R. S. Sutton. Learning and planning in average-reward markov decision processes. In International Conference on Machine Learning, pages 10653-10662, PMLR, 2021.
[38] Q. Wang, C. P. Ho, and M. Petrik. Policy gradient in robust mdps with global convergence guarantee, 2023.
12

---

[39] Y. Wang, A. Velasquez, G. Atia, A. Prater-Beet Bennette, and S. Zou. Robust average reward markov decision processes. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 37, pages 15215-15223, 2023.
[40] Y. Wang, A. Velasquez, G. K. Atia, A. Prater-Bennette, and S. Zou. Model-free robust average- reward reinforcement learning. Interaational Conference on Machine Learning, pages 36431-36469. PMLR, 2023.
[41] Y. Wang and S. Zou. Online robust reinforcement learning with model uncertainty. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 34, pages 7193-7206, 2021.
[42] Y. Wang and S. Zou. Policy gradient method for robust reinforcement learning. In Proc. International Conference on Machine Learning (ICML), volume 162, pages 23484-23526 PMLR, 2022.
[43] C.-Y. Wei, J. Jahromi, H. Luo, Sharma, and R. Jain. Model-free reinforcement learning in infinite-horizon average-reward markov decision processes. In International conference machine learming, pages 10170-10180, PMLR, 2020.
[44] R. J. Williams, Simple statistical gradient-follie following algorithms for connectionist reinforcement learning. Machine learning, 8(3):229-2555 1992.
[45] L. Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282): 1-36, 2022.
[46] Z. Xu, K. Panaganti, and D. Kalathil, Improved sample complexity bounds for distributionally robust reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 9728-9754, PMLR, 2023.
[47] W. Yang, L. Zhang, and Z. Zhang. Towards theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics. arXiv preprint arXiv:2105.0360 2021.
[48] J. Zhang, A. Koppel, A. Bedi, C. Szepesvari, and M. Wang. Variational policy gradient method for reinforcement learning with general utilities. In Proc. Advances in Neural Information Processing Systems (NeurIPS), volume 33, pages 4572-4583, 2020.
[49] Zhang, R. Tachet, and Laroche. Global optimality and finite sample analysis of softmax off-policy actor critic under state distribution mismatch. arXiv preprint arXi::2111.0299 2021.
[50] Zhang, Y. Wan, R. Sutton, and Whiteson. Average-reward off- off-policy policy evaluation with function approximation. In International Conference on Machine Learning, pages 12578- 12588. PMLR, 2021.
13

---

A Proof of Lemma 3.2
In this section, we provide the proof for Lemma 3.2
Consider polices n, E II. For the non-robust average cost gp, we have that
9P
9p
(p(s)(p (s.)), ---1s))
Σ (s.) Qā(s, ) (1(s)) - -T-ls))
Σ (())) (+1ss) -(|s)) + (5) (s, QF(s,)) *(-ss), (20)
where (a) is from the performance difference lemma g
Since the relative value function Vp" (s) is L,,-Lisscitzz in (Lemma 4.3 we have that (s,,,) +)
Lipscctc in Therefore, have that QP (s,-) (x.
O( Il), which further
implies that Σ, (Qp (s, :) - (s, )) ('(s)) (-|s)) o(I I')..
Let Px denote the worst-case transition kernel for policy æ. For the robust average cost, we have that
gつ = - 9p_ 2 -5_ gp_
= Σ (F(s) ). (11s) - ग (-|s)) + o(l - +'1l).
(21)
We then have that
g5 E, dp(s) ), (-1s) x(-15)) 95
lim inf
20.
(22)
||t
T'
Therefore, the Fréchet sub-gradient of 93 is Vgz with each (s, enttry
B Proof of Lemma 4.1
For the robust relative value function ViJ (8), we have that
(8) (s)
Σ (als)) (s, Σ (5(5))
Σ (#'(als) - m(lss) + (s) - (5
Σ (F((ass) - -(als) (s. (1 QF(
Σ
x(lls)
x(ass) Σ ( 93 (5') V (s') (s))
m(lss) (p((s)s.0(((ss)) 95(6) +V(())
(rl(s - (5.s) (5(()) -5
(23)
where (a) is from the Bellman equation independent of 8, have that
By re-arranging terms and from the fact that gi is
(s) 93 (s)
14

---

Σ - ((.s)) a(sla) (s (5) [pa(o1e.0)13(6))
VF (5) + (8)
(0)
2 Σ (a|s) [(als)) (s) T((ass)
Σ
Pa (s( (5)) [P((5)s,
V (s) (s),
(24)
where (a) is due to the fact that P- is the worst-case transition kernel for т. Since the LHS of (24 is independent of the RHS of (24) doesn't 't depend on either. We then take the weighted sum of the RHS with respect to _
( 9 (s)
E dp_ (((()) + ΣΣ d. (T)((s))) Pds(sss,)) (6)
C5 (P _ dB (VV (s) + Σ dF (s) (25)
From the definition of the stationary distribution, we have that Σ, E. (x dp_ (s'). Therefore,
95 (8) 95 (8)
Es B (5.-), (((1))
+ +Σ (3)V (6)- - (4,566)
Σ dp. (5) (s) + Σ dø (s)
= BB [ (s, a (:18) 7( (-11s)]
(26)
This completes the proof.
C Proof of Lemma 4.2
From the performance difference lemma 8 we have that
g5 9
gp. , Pp
< gp. Pp.
= Σ dF (QF (s, (-1s) -
< max
ds. (s) (s-s).((-(s)) #(-ls))
8
max (s, )) (T|ss) - -(-1s)).
(27)
(s. Note that dF_ (s) maxa (QF (s, ), a( (-1s) #(11s) 2 since (QF (s. -), (-1ss) T-|ss) 0. We then have that
g3 gT
dp_ (8) [s)
< max
d3_ (s) d3. (s) max (-1s) - #(-ls))
= CpL max
Σ 12 क( (-1s) #-1ss)
15

---

Cpl max V9g. π 8),
(28)
d3 (e) and the last step is from Lemma 3.2 where CpL m 15(3)
D Proof of Lemma 4.4
For the update of our algorithm
(++s)+ls = arg min mm:125 .).)) + D(p, TA (11)))) Vs PEA(A)
(29)
the following first-order optimality condition holds for any E 17 and 8
Q (8, + (T (-18) =x(+1s)), - m (-18)) 2 O.
(30)
From the three-poine Lemma of the Bregman divergence, we have that (+s+1(-|s) n& (-1s), p(-1s) x++1(-1s))
= -Ipp(-86 (8) Th (-1s))) || Tee (-1s)]1 (Ip(1ss) x-1s(-
(31)
Combining (30 and 31 we have that Lemma 4.4 holds.
E
Proof of Lemma 4.5
Plug p = Thk in 14). we have that
Th (27 (s, ), T 1+(s) TT((Is)) S -1|| -1 - - || - m++1(-1s)) (32)
Moreover, plug p n in 14). we have that
10 (8, TT+ (-1s) - (+((+=)) na (QT (s, -), TA (-18) x (-1s))
$ < (+1s) TT (-|s)))]1 + |||T (-|s) Tx (-<(ss)]1 |-|s( J (-1s)]12.
(33)
For the term (Q (s. :), 1-1s) - N& (+{ss)) we have that
(a)
Th S B
[ (s, (=+1(ss))) nx (-1)))
9
(b)
s [(0 1+ (111))) (-(sss)) 20,
(34)
M
where (a) is from the performance difference lemma g and (b) is from the definition of M and
(3)
For the term (QT (s, T - TT (-|s)), we have that
0 5 g g S gpth gp.. E Banap;
x" (11s))
(35)
Therefore, we have that
M (g
+ 53 96
< E
|| (-|s) m <=<(1s)]]?)
E Bend
1
|| (1ss - (++)(+))))?]
(36)
aodd Pee
17
By re-arranging the terms the above equation, we have that
M
99
g5 x
(g
gt)) + E, Bondi" 1766
|| (+1s) (-(())))1
M
1
E
- T"" (-|s) Th. (-1s)||]
(37)
M
1/k
16

---

Proof of Theorem 4.6
By recursively applying Lemma 4.5 we have that
96
15 2
(1
k
(97
g5)
+
(1
k-1
-
-T (-|s) - no (-1)))
M
17/0
k k-1
1
1.
1
B
Bsndt Frz
|-((s ne(-1s)]12
M
M
177
[=1
(1
1 k-r
-=((1s)-m((ss)]]] ==((ls))]]]
E
Benddi
(38)
M
171-1
M7 (1
Since the step size satisfies f)
M)
M, we have that
1
1 k k-1-1
E
(+|s) (-(ss)]
M
M
Litt
(1
k-t
TT' (-Is) m((l)))*]) s
Ban
(39)
M
T
Therefore, we have that
k
((1++1111
1
R-1
D6 Th
9p S
To
-gp)
+
E sadd
[1]*((|8) - To([16)]]]] (40)
M
M
Mno
G Proof of Theorem 4.7
Set the step size Tik = and define the gradient mapping (TT(Tx (-1s Th+ (+13)).
Note that if Ty is updated exactly by the
descent, then (T())(-))) = (s, -.. The
norm | ( (-s)) measures the closeness of the current step to the first-order stationary point. To prove Theorem 4.7 first show the following lemma.
Lemma G.1. For the robust average cost, setting L = La we have the following inequalities.
9y
S L (g - 99
Ju+1
(41)
Cri2 2|S
Proof.
For the update of our algorithm
Tk+1 (-1s) = arg min
(n (s, (.p) + D(p, (x(11s)) Vs Es PEΔ(A)
(42)
the following first-order optimality condition holds for any p E 11 and (s (s. + L [(Tx+1(11)) - (+(sss)), p(-(s) * 2 0.
(43)
By letting p Tg, we have that
(QF (5 F4 - TT+1
2 (L(TA+1(11 T
nx (+(s))) TT - (+(ss))
= -|| =T(-ss)112
(44)
From Lemma 4.1 we further have that
g -g
ah+1
E
(0 (s))), (+11(11))
(45)
Therefore, we have that
+ (Tm))(1)))))
g6
R
and
Ek+1
(46)
17

---

On the other hand, from Lemma 4.2 we have that
99 S OpL max E 9y Tut1
andd [10 (8, (++1(-1s) [
(47)
For (Qp (s, (x+1(11)) ----))-((1ls))) f(-ls)) from the first-order optimality condition 443 we have that
(07 ( --(1))
$ (()) ( + ( - TN (+(+s)) p(-1)) - +++1(-1s) -
- (I(T++((-15) -(())
Tx (-(s)) T++2(11s) -(-1s))
=
3 (La
#(-1s)]
5 (Lx + +]][=++1( (-1s) Th m+(+ss)]l/2]))
Lx
L ([L)(
(48)
where (a) is due to the fact that the robust relative action value function Q is L-pLischhtzz (Lemma
4.3 and (b) is due to the fact that [|+s)((-|s) - #(-|s)]| S 2/S/.
Therefore, have that
(1 Lx ) ) [CL((T((1))))
Tu+1 99 S CPL max E
end
To+t
(49)
By setting L = Log, we have that
S (E [ [Bandtats
Jut1 [[ (Tx(-15))11])
(PL2V/[S)
E
Tht1
[||r,, (mo(11s)) L (177
19
(50)
where the second inequality is from Jensen's inequality.
We ready prove Theorem 4.7
Proof. Let
We have that
(Cp12/2181))
T 9g
Tkll
08)2
Th gv 1
(51)
Let 0% = Et Dz. We then have that
o S (9 )5t) (or
Fy
ruti) 8x 8k41
(52)
L
We then divide both side by 5p00+1 and have that
5x+1
(53)
5k+1
5k L
6%
We then take the sum of the above inequality over iterations 0, 1... k 1. It then follows that
8141
(54)
6%
50
L i=0
From 46 we have that 9
g
Th+1
E
J6tt
(Te(-sss)) 2 0. Therefore, we have
Pxtt1
that 9
Iy and thus 6.+1 < 6;.
For any two constant 1, m E (0, 1), let n(k 1) be the number of steps that A. is at least over the first & iterations. If (k, 2 mk. we then have that
> at least [mk]] times. Therefore.
a.
w
2
mik.
(55)
8k
8g
L
18

---

We then have that
Ln 6ū S
(56)
wmik
(K, 1) < mk, we have that
I at least [(1 mik1 times. Since 8,+1 S 64, we have that
5x v 601(1-m)k 80 m
(57)
Since (56) and 57) hold for any m E (0, 1), have that
6 S min max
{
(wilk do mm))-)))
L
(58)
0c1,m<1
By letting = m 2. we have that
4Lx wk
V2
9'b) }
9 g s max
(95
(59)
2
This completes the proof.
19

---

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

---

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

---

Answer:
[No]
Justification: The code will be released the paper is accepted. The experiments are straightforward and easy to reproduce.
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips... cc/
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" is an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to to reproduce the results. See the NeurlPS code and data submission guidelines (https
wttgggidddd//oeSuuunnnnn ssicnpolicy) for more details. hetpolliicggiddeeCoooooo
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification:
We clearly specify all the details for the experiments in Section
Guidelines:
The answer NA means that the paper does not include experiments.
The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, or as supplemental material.
7. Experiment Statistical Significance
Question: Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Answer: [Yes]
Justification: We plot the mean and the standard deviation for 10 independence experiments as the error bar.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, or statistical significance tests, at least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
22

---

It should be clear whether the error bar is the standard deviation or the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars are reported in tables or plots, The authors should explain the text how they were calculated and reference the corresponding figures tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [NA]
Justification:
No computing resources are required.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics /attps:/nneuris. http///wrr....cuuuuu../aaccccaaa
Answer: [Yes]
Justification:
We have reviewed the Code of Ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special circumstances that require a deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., there a special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: There is potential societal impact that needs to be specified.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no socictal impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
23

---

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

---

If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification:
We do not release new assets.
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details the dataset/code/mooell as part their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: The paper does not involve crowdsoureing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
25


Reviews:
[{"review_id": "sUNHvzA7qS", "reviewer": "Reviewer_Ehp7", "summary": "The authors consider the mirror descent algorithm in the context of robust average cost MDPs. The consider $(s,a)$-rectangular uncertainty sets across a general distance metric. The Bregman divergence chosen for the purpose of analysis is the Euclidean 2-norm distance. The authors leverage on a prior result proving the existence of a corresponding Bellman equation for the robust average cost and another prior result proving Lipschitzness of the risk neutral average cost value function to derive the results in the paper. Since the robust average cost is the maximum average cost across the uncertainty set it is not differentiable and hence the authors resort to using the sub-gradient as a substitute. This sub gradient is shown to be the robust $Q$ function. Subsequently, the performance difference inequality in conjunction with a PL result is proven and leveraged to obtain the final convergence bounds which are of $O(1/\\epsilon)$. They characterize these bounds for both a constant and increasing step size.", "questions": "1. Is there a closed form expression for the value function corresponding to the solution of Equation 7? In exponential cost MDPs, these value functions do indeed have a closed form expression and I was curious about their generalizations to other distance metrics.\n\n2. Since the Bregman divergence considered is the Euclidean 2 norm, it feels more accurate to refer to the algorithm as policy gradient rather than mirror descent. Mirror descent is more commonly employed when the KL divergence is used as the Bregman divergence. Is there any specific reason for not referring to this algorithm as policy gradient?\n\n3. Since the minimization problem is considered, it is more relevant to refer to the setting as average cost rather than average reward as is currently done. \n\n\nSome typos: \n\n1. Line 463.5 in the appendix: should be $+\\sum_a\\pi(a|s)$ instead of $-\\sum_a\\pi(a|s)$\n\n2. In equation 10: should be $\\nabla g^{\\pi_k}_\\mathcal{P}$ instead of $\\nabla g^{\\pi}_\\mathcal{P}$", "limitations": "Even though the limitations are not explicitly addressed, the paper has been presented clearly and hence the limitations are apparent.", "rating": 6, "confidence": 5, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The problem considered is of significance to the community. Average cost problems are harder to analyze than their discounted cost counterparts due to the absence of the contraction factor. Hence even though its a technical challenge, this objective is more representative of applications where long term performance is important. And the robust average cost objective is important to ensure optimality in the face of uncertainty associated with the underlying transition kernel. \n\n2. Even though the analysis techniques are inspired by prior literature such as Agarwal et al, Xiao, it is not a straight forward extension and hence this paper provides with valuable tools in this context such as the performance difference inequality, PL inequality, etc which may be of independent interest to the community. \n\n3. The paper yields $O(1/\\epsilon)$ convergence bounds which are optimal even when compared to the risk neutral average cost setting/discounted cost setting. \n\n4. The results are also experimentally validated.", "weaknesses": "1. The authors seem to have missed a line of work pertaining to the robust average cost. Although they consider general $(s,a)$-rectangular sets with any distance metric, much of the prior work has considered the KL (Kullback Leibler) distance metric whose dual formulation yields the exponential cost robust MDPs. Some of the earlier works on this include [Borkar 2010], [BS02] where they characterize asymptotic behavior of dynamic programming algorithms for this robust formulation. Some of the more recent work in this domain can be found in [MMS23] and [MMS24]. [MMS23] considers a policy gradient algorithm for this robust setting, but provides asymptotic convergence bounds to a stationary point. [MMS24] considers modified policy iteration, an algorithm that generalizes both policy and value iteration and provides with finite time global convergence guarantees. Hence the repeated claim in the paper to have characterized the first policy based global convergence bounds in the context of robust average cost MDPs has to be modified accordingly. \n\n2. The authors assume an oracle provides with $Q^\\pi_\\mathcal{P}$, that is the value function corresponding to the argmax kernel associated with policy $\\pi$. In the risk neutral case, one can solve for the state action value function provided corresponding to a policy $\\pi$ by solving for the average cost Bellman equation (which typically involves a matrix inversion). It is not clear as to how to evaluate this robust value function even when you have access to the model, that is the nominal transition matrix and the single step costs. \n\n3. The authors assume that the underlying Markov chain is unichain. However, unichain Markov chain implies the existence of some transient states whose associated stationary measure is zero. In that case, the concentrability coefficient $C_{PL}$ will be infinity. Hence it seems like ergodicity is a requirement. \n\n4. The increasing step size requires knowledge of $M$, which is not apparent even in the full information setting. For instance, reference [16] in the paper characterizes the Lipschitz constant in terms of the model considered and hence can be evaluated when given access to the complete model information such as the probability transition matrix, etc. However, it is not apparent as to how to determine M based on its definition in line 254. \n\n\n\n[Borkar 2010] Borkar, V. S. (2010, July). Learning algorithms for risk-sensitive control. In Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems–MTNS (Vol. 5, No. 9).\n\n[BS02] Borkar, V. S., & Meyn, S. P. (2002). Risk-sensitive optimal control for Markov decision processes with monotone cost. Mathematics of Operations Research, 27(1), 192-209.\n\n[MMS24] Moharrami, M., Murthy, Y., Roy, A., & Srikant, R. (2024). A policy gradient algorithm for the risk-sensitive exponential cost MDP. Mathematics of Operations Research.\n\n[MMS23] Murthy, Y., Moharrami, M., & Srikant, R. (2023, June). Modified Policy Iteration for Exponential Cost Risk Sensitive MDPs. In Learning for Dynamics and Control Conference (pp. 395-406). PMLR.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the helpful and insightful feedback. Below we provide point-to-point responses to the weaknesses and questions. \n\n**W1. Related works on robust average cost MDPs.**\nWe thank the reviewer for pointing this out. In the revision, we modify our statement as 'We characterized the first policy based global convergence bounds with general uncertainty sets for robust average cost MDPs.' We also compare our work with the related works [Borkar 2010], [BS02], [MMS24], [MMS23]. We add the following paragraph in Section 1.2 in the revision:\n\n**Exponential cost robust MDPs.** For the robust average cost MDPs, when the uncertainty set is defined by the KL-divergence metric, the problem admits a dual formulation, which is the exponential cost robust MDPs. The exponential cost robust MDPs have also been studied in the literature. In [Borkar 2010], the Q-learning and the actor-critic method are described and the asymptotic performance are characterized for risk sensitive robust MDPs. In [BS02], the value iteration and policy iteration algorithms are also analyzed for risk sensitive MDPs. Recently, in [MMS23], the modified policy iteration is proved to converge to the global optimum for exponential cost risk sensitive MDPs. The policy gradient algorithm for the risk sensitive exponential cost MDPs is studied and the asymptotic convergence bounds to a stationary point are provided in [MMS24]. In our paper, we study the robust average reward MDPs with general uncertainty sets and characterize the global convergence of our algorithm. \n\n**W2. Evaluate the robust relative value function.** \nThe robust relative value function can be evaluated by generalizing the relative value iteration to the robust setting. The algorithm is presented as follows:\n\n> Algorithm parameters: $V_0$, $\\epsilon$, and reference state $s^* \\in \\mathcal{S}$   \nInitialize  $w_0 \\leftarrow V_0 - V_0(s^*)\\textbf{1}$    \n>\n> Loop for each step: $sp(w_t - w_{t-1})\\geq \\epsilon$    \n$\\quad$Loop  for  each  $s \\in \\mathcal{S}$:    \n$\\qquad V\\_{t+1} \\leftarrow \\mathbb{E}\\_{a\\sim\\pi}[r(s, a) + \\sigma\\_{\\mathcal{P}\\_s\\^a}(w\\_t)]$   \n$\\qquad w\\_{t+1}(s) \\leftarrow V\\_{t+1}(s) - V\\_{t+1}(s^*)$         \nreturn $V_t$ \n\nIn the algorithm, $\\\\sigma\\_{\\\\mathcal{P}\\_s\\^a}(w\\_t) = \\\\max_{p\\\\in\\\\mathcal{P}\\_s\\^a}p\\\\top w\\_t$, and can be solved in the dual formulation for various uncertainty sets [Iyengar05]. The returned $V\\_t$ is the robust relative value function and $V\\_t(s\\^*)$ is the robust average reward. \n\nThe assumption that an oracle that outputs the robust value function exists is also presented in robust discounted reward MDPs, for example [Li22].\n\n**W3. Unichain assumption may lead to infinite $C_{PL}$.**\nWe agree with the reviewer that the unichain assumption may not guarantee that $C_{PL}$ is finite, and moreover, ergodicity is a sufficient condition to guarantee $C_{PL}$ is finite.\n\n**W4. Determine the increasing step size $M$.**\nSince the definition of $M$ involves taking the sup over all transition kernels in the uncertainty set, theoretically determining $M$ is challenging. In practice, we only require an upper bound for $M$ so that the convergence result holds in Theorem 4.6. Therefore, in practice, we can run simulation to find an upper bound of $M$ and fine tune it. For example, we can numerically solve $\\min_{\\pi, P\\in\\mathcal{P}}\\\\|d_P^\\pi\\\\|_\\infty$ when the ergodicity holds, which is an upper bound of $M$. \n\n**Q1. Closed from expression for the value function.**\nFor the widely used metrics like the total variation distance, $\\chi$ -square distance and the KL divergence, the closed-form expression exists for $\\max\\_{\\mathsf{P}\\in\\mathcal{P}}\\sum\\_{s\\^\\prime \\in \\mathcal{S}}\\mathsf{P}\\_{s, s\\^\\prime}\\^aV\\_{\\mathcal{P}}\\^\\pi(s\\^\\prime)$ [Iyengar05]. The dual formulation depends on the structure of the uncertainty set. However, if the value function has closed-form solution as the exponential cost MDPs is unclear. Moreover, our algorithm and theoretical results do not depend on the specific structure of the uncertainty set and the closed-form solution of the value function.\n\n\n**Q2. Policy gradient or mirror descent.**\nWe don't refer to our algorithm as policy gradient is due to the fact that in our algorithm, we replace the policy (sub)-gradient $\\nabla g_\\mathcal{P}^{\\pi_k}$ by $Q_\\mathcal{P}^{\\pi_k}$. Since our algorithm is the mirror descent with a specific Bregman divergence and $Q_\\mathcal{P}^{\\pi_k}$ is not the (sub)-gradient, we refer to our algorithm as policy mirror descent.\n\n**Q3. Average cost MDPs.**\nWe thank the reviewer for this comment. In our paper, we adopt a minimization formulation to align with conventions in the optimization literature. In the revision, we will replace rewards with costs.\n\n**Q4. Typos.** We thank the reviewer for pointing this out. Fixed.\n\n**Reference.**\n[Borkar 2010] Borkar, V. S. (2010, July). Learning algorithms for risk-sensitive control. In Proceedings of the 19th International Symposium on Mathematical Theory of Networks and Systems–MTNS (Vol. 5, No. 9).\n\n[BS02] Borkar, V. S., Meyn, S. P. (2002). Risk-sensitive optimal control for Markov decision processes with monotone cost. Mathematics of Operations Research, 27(1), 192-209.\n\n[MMS24] Moharrami, M., Murthy, Y., Roy, A., Srikant, R. (2024). A policy gradient algorithm for the risk-sensitive exponential cost MDP. Mathematics of Operations Research.\n\n[MMS23] Murthy, Y., Moharrami, M., Srikant, R. (2023, June). Modified Policy Iteration for Exponential Cost Risk Sensitive MDPs. In Learning for Dynamics and Control Conference (pp. 395-406). PMLR.\n\n[Iyengar05] Garud N. Iyengar (2005). Robust Dynamic Programming. Mathematics of Operations Research.\n\n[Li22] Yan Li, Guanghui Lan, Tuo Zhao. (2022). First-order Policy Optimization for Robust Markov Decision Process.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": "PHS4vXN30u", "reviewer": "Reviewer_7myA", "summary": "The authors present a gradient-based algorithm for average reward robust MDP (finite MDP). This setting has been studied in prior works, however, this paper proposes a policy optimization-based algorithm which is not yet done. They do a theoretical analysis of this setting and show linear convergence (by increasing step size), finite iteration complexity and quite nicely show satisfying PL condition and therefore perhaps trivially global convergence.", "questions": "Questions:\n\n43-44 -> What are these algorithms based upon in contrast to gradient-based? \n\nIs there an assumption on eqn 3 about boundedness? Why does V and Q are necessarily finite?\n\nWhat will be a sufficient condition for assumption 2.1? Also motivating beforehand on why you need this assumption will be good.\n\nIs there a bound/relation between C_{PL} and M? \n\nWhat does the non-robust method line 307 optimize for? what is it's objective and used transition?", "limitations": "None", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is easy to read.\n- Policy gradient-based approach for robust average rewards MDP\n- There are multiple theoretical contributions: Linear convergence, Global optimality, derived sub-gradient of robust average reward MDPs", "weaknesses": "- Presentation of theoretical results is not sharp or rather quite bad. They do not mention the assumptions for the lemma/theorem statement holds. I am uncertain if there are any further assumptions.\n-  Much of the used theory is already exists in the literature of robust MDP and infinite horizon case (which is not bad since authors make sure to explain that they not trivially using but extending it, e.g., 197-204 lines). This is currently described in pieces throughout the paper, I would appreciate it if authors could concretely explain at one place (perhaps in related works) the tools used from prior works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the helpful and insightful feedback. Below we provide point-to-point responses to the weaknesses and questions. \n\n**W1. Didn't mention the assumptions for the lemma/theorem statements.**\nWe thank the reviewer for this comment. In the revision, we will rephrase the statements of lemmas and theorems to include the assumptions we use. Specifically, \nTheorem 4.6: Under Assumption 2.1, set the step size $\\eta_k \\geq \\eta_{k-1}\\Big(1-\\frac{1}{M}\\Big)^{-1}M$, the robust policy mirror descent satisfies\n$g\\_\\mathcal{P}\\^{\\pi\\_k} - g\\_\\mathcal{P}\\^\\* \\leq (1-\\frac{1}{M})\\^k(g\\_\\mathcal{P}^{\\pi\\_0} - g\\_\\mathcal{P}\\^\\*) + (1-\\frac{1}{M})\\^{k-1}\\frac{1}{M\\eta\\_0}\\mathbb{E}\\_{s\\sim d\\_{\\mathsf{P}\\_{\\pi\\_0}}\\^{\\pi\\^\\*}}[\\|\\pi\\^\\*(\\cdot|s) - \\pi\\_0(\\cdot|s)\\|\\^2].$\n\nFor Theorem 4.7:  Under Assumption 2.1, let step size $\\eta = \\frac{1}{L_\\pi}$ for all $k\\geq 1$, we have that the each iteration of the robust policy mirror descent satisfies $g\\_\\mathcal{P}\\^{\\pi\\_k} - g\\_\\mathcal{P}\\^\\* \\leq \\max\\Big\\\\{\\frac{4L_\\pi}{\\omega k},(\\frac{\\sqrt{2}}{2})^k\\big(g_\\mathcal{P}^{\\pi_0} - g_\\mathcal{P}^*\\big)\\Big\\\\}$, \nwhere $\\omega = (2\\sqrt{2S}C_{PL})^{-2}$.\n\n**W2. Explain the tools used from prior works at one place.** \nWe thank the reviewer for this comment. We summarize the results that are used from prior works in Section 1.2. We will add the following paragraph in the revision:\n\nIn [1], the Fr\\'echet sub-gradient has been derived for robust discounted reward MDPs. However, the Fr\\'echet sub-gradient for robust discounted reward MDPs in [1] can not be extended to the average setting since in [1], the discounted factor $\\gamma$ is required to be strictly less than 1. In [2], the performance difference lemme was derived for average reward MDPs. In our paper, we provide a lower bound on the difference of robust average reward between two policies. Such a bound was also derived in [1] for robust discounted value function by applying the Bellman equation of robust value function, which is not applicable in our case as the average reward itself doesn’t satisfy the Bellman equation. We also extend the Lipschitz property of the non-robust relative value function in [3] to the unichain setting. In [4] and [5], the convergence rate of the policy gradient descent for non-robust discounted reward MDPs was derived. In their analyses, the smoothness of the value function is required. However, the robust average reward might not be smooth. Therefore, the approaches applied in [4] and [5] can not be directly extended to robust average reward MDPs.\n\n**Q1. Details on related works.**\n[6] and [10] build the connection between the discounted reward MDPs and average reward MDPs and prove the existence of Blackwell optimal policies. The algorithms based on value iteration are further proposed. [7] is an extension of [6] with parts of the state space having arbitrary transitions and other parts are purely stochastic. In [8] and [9], the model-based and model-free robust average reward MDPs are studied and the robust relative value iteration algorithms are proposed. We will add this discussion in the revision\n\n**Q2. Boundedness assumption on V and Q.**\nWe thank the reviewer for pointing this out. Since $V$ and $Q$ are unique up to an additive constant, similar as [3], we consider the projection of the value function onto the subspace orthogonal to the $\\textbf{1}$ vector. In this case, our theoretical results still hold. \n\n**Q3. Sufficient condition and motivation for assumption 2.1.**\nThe sufficient condition for Assumption 2.1 is that for any $\\pi\\in\\Pi$ and $\\mathsf{P}\\in \\mathcal{P}$, the Markov chain only contains a single recurrent class and some transient states.  The unichian assumption is important and widely used since under the unichain assumption, the robust average reward is identical for every starting state. To derive Lemma 4.1, we leverage the fact that the robust average reward is independent of the initial state. If the unichain assumption doesn't hold, the inequality may not hold, and this is a key step to derive the global optimality of our algorithm. \n\nIn practice, it is often the case that only unichains are of interest to the decision-making problem. For example, the nominal transition kernel is obtained from samples, and is a unichain. Then, the true transition kernel must be a unichain, and therefore to obtain a robust policy that works well on the true transition kernel, it is sufficient to only consider unichain. Even in standard MDP, extending results from unichain to e.g., multichain problems is very challenging. Extending our results under a relaxed assumption beyond unichain is even more challenging, and it is of future interest.\n\n**Q4. Relation between $C_{PL}$ and $M$.**\nThe relation between $C_{PL}$ and $M$ is unclear. We have that $M = \\sup\\_{\\pi, \\mathsf{P}\\in\\mathcal{P}}\\Big\\\\|\\frac{d\\_{\\mathsf{P}\\_\\pi}\\^{\\pi\\^\\*}}{d\\_\\mathsf{P}\\^\\pi}\\Big\\\\|\\_\\infty = \\sup\\_{\\pi, s, \\mathsf{P}\\in\\mathcal{P}} \\frac{d\\_{\\mathsf{P}\\_\\pi}\\^{\\pi^*}(s)}{d\\_\\mathsf{P}\\^\\pi(s)}$ and $C\\_{PL} = \\max\\_{\\pi, s} \\frac{d\\_{\\mathcal{P}}\\^{\\pi\\^\\*}(s)}{d\\_\\mathcal{P}\\^\\pi(s)} = \\max\\_{\\pi, s} \\frac{d\\_{\\mathsf{P}\\_{\\pi\\^\\*}}\\^{\\pi\\^\\*}(s)}{d\\_{\\mathsf{P}\\_{\\pi}}\\^\\pi(s)}$. The sup of $M$ and $C_{PL}$ can be achieved at different $\\pi$. In the numerator, it's unclear if $d\\_{\\mathsf{P}\\_\\pi}\\^{\\pi\\^\\*}(s)$ is larger than $d\\_{\\mathsf{P}\\_{\\pi\\^\\*}}\\^{\\pi\\^\\*}(s)$ or not.\n\n**Q5. Objective and transition kernel of baseline algorithm.**\nFor the baseline algorithm, it's trained under the known nominal transition kernel and the objective is to maximize the non-robust average reward.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": "CSQFKoaSbI", "reviewer": "Reviewer_H19Z", "summary": "The paper studies gradient-based methods for robust average reward MDPs. The paper first derives a sub-gradient for the robust average reward (which is nonsmooth), and then uses it to define a mirror descent algorithm. They prove a few structural properties of the setting and then use them to provide a convergence guarantee for their algorithm. They also provide some experimental results.", "questions": "Maybe the unichain assumption 2.1 should be placed earlier, since the stationary distributions $d^\\pi$ are not generally well-defined in the absence of this assumption.\n\nIn line 177, is the definition of $d_{\\mathcal{P}}^\\pi$ unique?\n\nLemma 3.2: similar question, I think the worst-case transition kernel for a policy $\\pi$ is not unique. In this case I wonder if $d_{\\mathcal{P}}^\\pi$ and $Q_{\\mathcal{P}}^\\pi$ are uniquely defined? And thus my main question is, for the sub-gradient, can we use different worst-case transition kernels in $d_{\\mathcal{P}}^\\pi$ and $Q_{\\mathcal{P}}^\\pi$, or do they need to use the same one? (The proof makes it seem like they are using the same one?) Thus maybe the lemma statement would need to be amended to discuss this.\n\nLemma 4.2: Is $C_{PL}$ guaranteed to be finite? The usual definition of unichain (e.g. in Puterman) is that the transition matrix has a single recurrent class plus a (possibly empty) set of transient states. The transient states would have stationary measure 0 which could cause $C_{PL}$ to blow up?\n\nI have a similar concern about the quantity $M$ in Lemma 4.5. I am also confused about the denominator (is there a missing subscript $\\pi$?)\n\nWhere is the proof of Lemma 4.3? It is claimed that a result from [16] can be easily extended to a more general (unichain) setting; however, because such details can be very thorny in the average reward setting, I think a proof should be provided.", "limitations": "No major limitations", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "Overall the paper and proofs are written with high clarity and quality, but I do have several technical concerns (in the questions section). I would raise my soundness score and overall evaluation if they were all adequately addressed.\n\nThere is good originality in the problem setting and the fact that they consider gradient-based methods. In particular it requires surmounting certain technical difficulties related to the robust average reward. If the technical concerns can be addressed, then I think these theoretical developments could prove to have good significance to future work.", "weaknesses": "The main weakness of the paper is what I perceive to be several technical concerns (listed in the questions section). I would raise my soundness score and overall evaluation if they were all adequately addressed.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "**W1. Listed in the question section.**\nPlease refer to the response of Q1-Q6.\n \n**Q1. Unichain assumption should be placed earlier.**\nWe thank the reviewer for this comment. In the revision, we will introduce the unichain assumption earlier in the paper and emphasize that our contributions are based on the unichain assumption.\n\n**Q2. Uniqueness of $d_\\mathcal{P}^\\pi$.**\nThe worst-case transition kernel may not be unique for general uncertainty sets, and thus $d_\\mathcal{P}^\\pi$ may not be unique. \n\n**Q3. Uniqueness of $d_\\mathcal{P}^\\pi$ and $Q_\\mathcal{P}^\\pi$.**\nThough the worst-case transition kernel may not be unique, $Q\\_\\mathcal{P}\\^\\pi$ is unique. From the definition of the worst-case transition kernel, for a worst-case transition kernel $\\mathsf{P}\\_\\pi$ of a policy $\\pi$, we have that $Q\\_{\\mathsf{P}\\_\\pi}\\^\\pi = \\max\\_{\\mathsf{P}\\in\\mathcal{P}} Q\\_{\\mathsf{P}}\\^\\pi$. Therefore, the robust action value function is unique. For the sub-gradient, the worst-case transition kernel of $d\\_\\mathcal{P}\\^\\pi$ and $Q\\_\\mathcal{P}\\^\\pi$ can be different, but this does not affect our results.\n\n**Q4. Boundedness of $C_{PL}$.**\nWe agree with the reviewer that in the unichain setting, $C_{PL}$ might not be finite if transient state exists.\nThe constant $C_{PL}$ depends on the structure of the underlying MDPs and also appears in prior works on discounted reward MDPs and non-robust average reward MDPs ([1], [2], [3], [4]). If the Markov chain is ergodic, i.e., there is only a single recurrent class, then $C_{PL}$ is guaranteed to be finite.\n\n**Q5. Boundedness of $M$.**\nSimilar as $C_{PL}$, the constant $C_{PL}$ depends on the structure of the underlying MDPs. If the Markov chain is ergodic, then $M$ is guaranteed to be finite. The definition of $M$ is our paper is accurate. For the denominator, the subscript $\\mathsf{P}$ denotes the transition kernel that we maximize. In the numerator, the subscript $\\mathsf{P}_\\pi$ denotes the worst-case transition kernel of $\\pi$.\n\n**Q6. Proof of Lemma 4.4.**\nIn Lemma 14 of [4], the $L_\\pi$-Lipschitz of the relative value function is proved. In their paper, $L_\\pi = 2C_m^2C_p\\kappa_r + 2C_mC_r$. For $C_p$ and $\\kappa_r$, the proof of Lemma 18 in [4] shows that the ergodicity of the Markov chain is not required and the results can be extended to the unichain setting. We only need to show that $C_m$ is finite for unchain. In [4], $C_m$ is defined as the maximum of the operator norm of the matrix $(I-\\Phi P_\\pi)^{-1}$ across all policies $\\pi\\in\\Pi$. For any $\\pi\\in\\Pi$, following the proofs in Section A.2 of [4], we have that the eigenvalues of $(I-\\Phi P_\\pi)$ is non-zero for unchain since unchain only has a single recurrent class and the stationary distribution exists. Therefore, for any $\\pi\\in\\Pi$, $\\|(I-\\Phi P_\\pi)^{-1}\\| < \\infty$. Moreover, since the collection of all policy $\\Pi$ is compact, we have that the maximum of the operator norm of the matrix $(I-\\Phi P_\\pi)^{-1}$ across all policies $\\pi\\in\\Pi$ is finite. Therefore, $L_\\pi$ exists for unchains. We will add the proof sketch of Lemma 4.4 in the revision.\n\n**Reference.**\n[1] Y. Wang and S. Zou. Policy gradient method for robust reinforcement learning. In Proc.\nInternational Conference on Machine Learning (ICML), volume 162, pages 23484–23526. PMLR, 2022.\n\n[2] Q. Wang, C. P. Ho, and M. Petrik. Policy gradient in robust mdps with global convergence415\nguarantee, 2023.\n\n[3] Y. Li, G. Lan, and T. Zhao. First-order policy optimization for robust markov decision process.\narXiv preprint arXiv:2209.10579, 2022.\n\n[4] N. Kumar, Y. Murthy, I. Shufaro, K. Y. Levy, R. Srikant, and S. Mannor. On the global convergence of policy gradient in average reward markov decision processes. arXiv preprint arXiv:2403.06806, 2024.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": "C0Crj0CEhG", "reviewer": "Reviewer_2EU7", "summary": "The authors introduce study a policy gradient algorithm for solving unichain average reward robust MDPs. They show a linear convergence rate for increasing step sizes and a $O(1/k)$ convergence rate for fixed step size, where $k$ is the number of iterations of the algorithms.", "questions": "* The authors in [1] mention a $O(1/\\epsilon)$ convergence rate for their algorithm in their conclusion. How does that compare to your $O(1/\\epsilon)$ result?\n\n* Under the unichain assumption, it is well-known that discounted MDP with a discount factor sufficiently large can solve average reward MDPs (typically with a discount factor larger than $1-\\epsilon/D$ where $D$ is the diameter of the MDP). There is a vast number of recent papers on policy gradient methods for nominal discounted MDPs and discounted robust MDPs. Can the authors compare the complexity of their algorithms with the complexity of the best policy gradient methods for discounted MDPs combined with the appropriate (large) discount factor for unichain MDPs?\n\n* I understand that the robust value function may be non-smooth for robust MDPs. But isn’t it also the case in the discounted setting? How do authors in the discounted setting bypass that for designing policy gradient algorithms? Is it the same `trick' in your paper? Also, for what geometry of the uncertainty set is the robust value function smooth? \n\n* l159-160, definition of the bias: in all generality the definition of the bias/relative value function should involve the Cesaro average, see p 338 in [2]. In my understanding the definition given by the authors only holds fors for *aperiodic* Markov chains. Please clarify.\n\n* A minor comment: Usually, rewards are maximized, and costs are minimized. In this paper, rewards are minimized, which is a bit weird, even though the maths don’t change.\n\n* Please introduce the equations for $d^{\\pi}$ in the main body.\n\nl287: typo, the first two sentences of rmk 4.8 should be one sentence.\n\n[1] A. Tewari and P. L. Bartlett. Bounded parameter markov decision processes with average reward criterion. In International Conference on Computational Learning Theory, pages 263–277. Springer, 2007.\n\n[2] M. L. Puterman. Markov decision processes: Discrete stochastic dynamic programming, 1994", "limitations": "No problem here.", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "This is a good paper. It is well-written and defines clearly its objectives. It extends to the case of unichain average reward robust MDPs the current state-of-the-art results for policy gradient methods in discounted robust MDPs and average reward nominal MDPs.", "weaknesses": "I only have three minor comments as regards the claims of the authors, which I find a bit too far from the exact results proved in their theorems. I think that the paper requires some clarifications. \n\n* The authors should mention the unichain assumption much earlier in the paper. The word *unichain* isn’t even present in the abstract, in the introduction, it is only mentioned in the very end of section 2. This assumption is crucial to establish several important properties of average value function (such as uniformity across states) and relative value function (such as continuity). This needs to be emphasized much earlier, and highlighted when the authors give their main contributions. Given the connection between mean-payoff perfect-information stochastic games and robust MDPs [0], the sentence from l13-14 of the abstract: *Moreover, our algorithm is the first algorithm that converges to the global optimum with polynomial time for robust average reward MDPs* would mean that the authors have solved a long-standing open problem, which is not the case since they solely focus on unichain instances (although I appreciate the results of the authors). Please clarify. \n\n* I am a bit confused with the claim about the polynomial time complexity of the algorithms. Usually, a (weakly) polynomial time complexity refers to a number of arithmetic iterations polynomial in $\\log(1/\\epsilon)$, in the dimension of the problems and in the logarithm of the entries of the problem (here, the number of bits necessary to represent the rewards and the transition probabilities). So why is $O(1/\\epsilon)$ a polynomial-time complexity? Similarly, the $O(.)$ notations seem to be hiding the $C_{PL}$ term from (15), and it’s not clear how this is bounded in terms of $S,A$ and the parameter of the problem. Same with the constant $L_{\\pi}$ from (16), can you provide a bound on this? The closed statement from polynomial-time complexity appears to be Th 4.6 but there again we have terms like $M$ appearing in the bound, and it’s not clear how to bound them. Please clarify or reformulate your claims about *polynomial-time* algorithms.\n\n* Some of the definitions appear incorrect. In all generality the definition of the bias should involve some Cesaro averages or the sum may diverge, the definition given by the authors is correct only for aperiodic Markov chains (see my other comments below).\n\n[0] Chatterjee, K., Goharshady, E. K., Karrabi, M., Novotný, P., & Žikelić, Đ. (2023). Solving long-run average reward robust mdps via stochastic games. arXiv preprint arXiv:2312.13912.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the Reviewer for the helpful and insightful feedback. Below we provide point-to-point responses to the weaknesses and questions. \n\n**W1. Present assumption 2.1 earlier.** In the revision, we will introduce the unichain assumption earlier in abstract and emphasize that our contributions are based on the unichain assumption.\n\n**W2. Polynomial time complexity of the algorithm.**\nSince the complexity of our algorithm is in the order of $\\mathcal{O}(1/\\epsilon)$ not $\\mathcal{O}(\\log(1/\\epsilon))$, the polynomial-time complexity claim is not accurate. We will reformulate our claims in the revision. Though our algorithm doesn't have polynomial-time complexity, our algorithm is still the first algorithm that has finite time complexity for robust average reward MDPs. \n\nSince $M$ and $C_{PL}$ depend on the structure of the underlying MDPs, characterizing the upper bound of $M$ and $C_{PL}$ is non-trivial. We would like to emphasize that similar constants also appear in prior works on robust discounted reward MDPs and average reward MDPs ([3], [4], [5], [6]). For the constant $L_\\pi$, when the underlying MDP is ergodic, the upper bound of $L_\\pi$ is characterized in [6], which is also depends on the structure of the MDP. From the Lemma 14 in [6], we have that $L_\\pi$ is in the order of $\\mathcal{O}\\Big(\\frac{C_e^2S^2}{(1-\\lambda)^2}\\sqrt{A}\\Big)$, where $C_e$ and $\\lambda$ are constants that characterize the geometric ergodicity of the MDPs.\n\n**W3. Clarify definitions of average reward.**\nIn [2], the Cesaro limit sense relative value function was defined for periodic chain. This is because the Markov chain is not assumed to be unichain in [2]. When the Markov chain is unichain, the Markov chain only contains a single recurrent class and some transient states, and the average reward is independent of the initial state. Since there is only one recurrent class, the relative value function does not need to involve the Cesaro average. \n\n**Q1. Compare with an existing work with $\\mathcal{O}(1/\\epsilon)$ convergence rate.**\nIn [1], the $\\mathcal{O}(1/\\epsilon)$ convergence rate was achieved for robust average reward MDPs when the uncertainty set is a bounded parameter MDP. Specifically, for each state action pair $(s, a)$, the transition probability $p_s^a(s^\\prime)$ is bounded between a lower bound $l_s^a(s^\\prime)$ and an upper bound $u_s^a(s^\\prime)$. In our paper, we consider more general uncertainty sets. Moreover, [1] studies the convergence rate by building the connection between discounted reward MDPs and average reward MDPs while our paper focuses on policy gradient-based method. We discussed [1] in the related works section in our paper. We will also compare the $\\mathcal{O}(1/\\epsilon)$ convergence rate in the revision. \n\n**Q2. Compare with policy gradient method for discounted MDPs with large discount factor.**\nThere are recently works on policy gradient methods for robust discounted MDPs. In [3], the robust MDPs are considered under the $R$-contamination uncertainty set. The robust policy gradient converges to the global optimum with iteration complexity $\\mathcal{O}(1/\\epsilon^3)$. In [4], the double-loop robust policy gradient was proposed and was further proved to converge to the global optimum with complexity $\\mathcal{O}(1/\\epsilon^4)$. In [6], with sufficiently large step size, the robust policy mirror descent converges to the global optimum with complexity  $\\mathcal{O}(1/\\epsilon)$. To the best of the author's knowledge, there is no works building the connection between the robust discounted reward and robust average reward. Therefore, it's non-trivial to compare the complexity of our algorithm with the policy gradient methods for discounted MDPs combined with the large discount factor.\n\nThe authors of [7] shows that there exists a discount factor\n$\\gamma_{bw}\\in(0, 1)$ such that any policy that is $\\gamma$-discount optimal for $\\gamma\\in(\\gamma_{bw}, 1)$ is also Blackwell optimal when the uncertainty set is definable. However, how to choose $\\gamma_{bw}$ is still an open problem. In [7], only value iteration based algorithms are proposed and no stopping criterion is introduced for their algorithms.\n\n**Q3. Bypass non-smoothness of robust value function in discounted MDPs.**\nFor discounted reward MDPs, different methods are proposed to bypass the non-smoothness of the robust value function. In [3], the total-variation uncertainty set is studied and the non-smoothed robust value function is smoothed by approximating the max operator using the LogSumExp (LSE) operator. In [4], the non-smoothness of the robust value function is bypassed by introducing the Moreau envelope function, which can also be viewed as a smoothed version of the robust value function. In [5], the authors develop a similar bound as the Lemma 4.1 in our paper by applying the Bellman equation of robust value function, and further apply it to show the convergence of the mirror descent algorithm. However, it is not applicable in our case as the average reward doesn't satisfy the Bellman equation. \n\n A sufficient condition for the robust value function to be smooth is that there exists a constant $C$ such that $\\|d\\_s\\^{\\pi, \\mathsf{P}\\_{\\pi}} - d\\_s\\^{\\pi\\^\\prime, \\mathsf{P}\\_{\\pi\\^\\prime}}\\|\\leq C\\\\|\\pi-\\pi\\^\\prime\\\\|$, which depends on the geometry of the uncertainty set. Since it involves the worst-case transition kernel and the closed-form expression doesn't exist, it unclear for what geometry of the uncertainty set is the robust value function smooth.\n\n**Q4. Clarify the definition of relative value function.**\nPlease refer to the response of W3\n\n**Q5. Average cost.**\nIn the revision, we will replace rewards with costs.\n\n**Q6. Introduce the equations for $d^\\pi$.**\nWe provide the equations for $d^\\pi_\\mathsf{P}$ in the revision: $d^\\pi_\\mathsf{P}$ is the stationary measure of $s$ under the transition kernel $\\mathsf{P}$ satisfies that $d^\\pi_\\mathsf{P} \\mathsf{P} = d^\\pi_\\mathsf{P}$. \n\n**Q7. Typo.**\nFixed.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "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": {}}]

Author rebuttal:

Meta-review: The paper analyzed policy gradient methods for average reward robust MDPs.
The contribution and challenge here are mainly technical, since the results for the discounted case already appear in previous work.
Nevertheless, all reviewers (some of them experts in the field) unanimously agree that the contribution is important and relevant to the neurips community and that the paper is well written.
I will therefore accept.
Decision: Accept (poster)