Robust Reinforcement Learning with General Utility
Authors: Ziyi Chen
Yan Wen
Zhengmian Hu
Heng Huang
Venue: NeurIPS 2024 poster (2024)
Keywords: robust reinforcement Learning
general utility
minimax optimization
Primary area: reinforcement_learning
TL;DR: We propose a new robust reinforcement learning framework with general utility, and design algorithms with provable convergence rates to stationary point or global optimum.

Abstract: Reinforcement Learning (RL) problem with general utility is a powerful decision making framework that covers standard RL with cumulative cost, exploration problems, and demonstration learning. Existing works on RL with general utility do not consider the robustness under environmental perturbation, which is important to adapt RL system in the real-world environment that differs from the training environment. To train a robust policy, we propose a robust RL framework with general utility,  which subsumes many existing RL frameworks including RL, robust RL, RL with general utility, constrained RL, robust constrained RL, pure exploration, robust entropy regularized RL, etc. Then we focus on popular convex utility functions, with which our proposed learning framework is a challenging nonconvex-nonconcave minimax optimization problem, and design a two-phase stochastic policy gradient type algorithm and obtain its sample complexity result for gradient convergence. Furthermore, for convex utility on a widely used polyhedral ambiguity set, we design an algorithm and obtain its convergence rate to a global optimal solution.

Robust Reinforcement Learning with General Utility
Ziyi Chen, Yan Wen, Zhengmian Hu, Heng Huang
Department of Computer Science, Institute of Health Computing.
University of Maryland College Park College Park, MA 20742, USA c2c286, ywenl, zhu123, heng ) @umd. edu
Abstract
Reinforcement Learning (RL) problem with general utility is powerful decision making framework that covers standard RL with cumulative cost, exploration problems, and demonstration learning. Existing works on RL with general utility not consider the robustness under environmental perturbation, which is important environment that differs from the training
adapt RL system in the environment. To train a robust policy, we propose a robust RL framework with general utility, which subsumes many existing RL frameworks including RL, robust RL, RL with general utility, constrained RL, robust constrained RI., pure exploration, robust entropy regularized RL,, etc. Then we focus popular convex utility functions, with which our proposed learning framework is a challenging nonconvex now.ooecceeeeeceeeeeeeee minimax optimization problem, and design two wwo-phase stochastic policy gradient type algorithm and obtain its sample complexity result for gradient convergence. Furthermore, for convex utility widely used polyhedral ambiguity set, we design an algorithm and obtain its convergence rate to a global optimal solution.
1 Introduction
aiming to find the optimal policy that minimizes accumulative cost, which is also a linear utility function of occupancy measure. Recent works have extended standard RL to more general utility functions to account for variety of practical needs, including risk-sensitive applications 22 & (2), exploration maximization
Reinforcement learning (RL) is an important decision-making framework 41
18 54 51 13 6), and safety constraints [54] [3]. There are provably convergent algorithms to solve RL with general utility [54 555 6). However, these works study RL with general utility in fixed environment, which may fail in many applications where the policy is trained in a simulation
environment but implemented in different real-world environment [37 56].
To make the policy robust such environmental change, robust RL has been proposed to find
optimal robust policy under the worst possible environment [36 20 48 45 14] However, all the existing robust RL works restrict to linear utility function to our knowledge. Therefore, we aim to answer the following research question:
O: Can we train a robust policy for RL with general utility and obtain convergence results?
1.1 Our Contributions
We affirmatively answer this question by proposing robust RL with general utility, the first learning framework that obtains robust policy for general utility in the worst possible environment. It formulated as minimax optimization problem minsee maxçe= o (Ao.g) where f the utility function and λ is the occupancy measure under the policy parameter 6 E θ and the environmental
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

transition kernel parameter Ç E. Our robust RL with general utility is a combination of its two important special cases, namely, RL with general utility [54] (formulated as m f f( where the environmental parameter { is fixed) and robust RI.
36 where / is restricted to linear utilityy function. This new learning framework also covers many other existing RI. frameworks including constrained RI. [2 and robust constrained RI.
43 with safety critical applications such as healthcare and unmanned drones, entropy regularized RL 110 and its robust extension [32] which help agents learn from human demonstration, pure exploration 18 with application to explore an environment with sparse reward signals and its robust extension, etc. These examples use convex utility functions f. which is the focus of this paper. See Section 2.1 for details of these examples.
Then, we focus on designing provably convergent algorithmss for our new proposed learning frame- work with the widely used convex utility function f. In this case, our objective ming max; f( is still a highly challenging nonconvex-nomne nonconcceee minimax optimization problem. Hence, we have to utilize the structure and properties of λo,g to design algorithms and obtain convergence results. To elaborate, we design a projected stochastic gradient descent ascent algorithm with two phases. Interestingly, the first phase targeted at the objective function f obtains stationary point of a different envelope function. Hence, we add a second phase targeted at corrected objective to converge to a near-stationary solution of the original objective f- 'The convergence analysis is non-trivial with two novel techniques. First, have proved projected gradient dominance property (Proposition that is much stronger than the existing one on convex utility, with less assumptions, no bias term and applicability to more general parameterized policy. Second, in the convergence analysis of the second phase, we obtain convergence to global Nash equilibrium (thus stationary point) of by Proposition 4 which is close to a stationary point of f by proving that Vef((No.e) (>e.))
Furthermore, with convex utility function f and the widely used s-rectangular polyhedral ambiguity set E (including the popular L and L ambiguity sets), we design an alternative algorithm which converges to global optimal solution of this
optimization problem at a sublinear rate (11 () (Theorem 33. This is much more challenging than global convergence for convex RL (that is, RL with convex utility function and fixed {) [54] 51 6 and for robust RL
with linear utility satisfying Bellman equation [36] 20 45 [5] (25.. so we need novel algorithm design and novel techniques. First, prove that arg maxe (Aa,g) can be obtained in the finite set of vertices V(E) (Proposition 6). This is intuitive if f()o,)) is a convex function but in many applications, only f(A) is convex. To solve this challenge, we prove a novel local invertibility property of λe (Proposition 5) by checking Bellman equation of λø.ç state by state in two cases. Then we prove Proposition 6 using a novel state- by-tte extension from an optimal non-vertex g to optimal vertex g. Second, the major difficulty to design our algorithm is find descent direction of r(0)= == max; / (Daag). We select the near-optimal vertices & E E C V(E) that may affect the optimization progress ((0k+1) T(0x), and find the descent direction with provably large (Proposition
7 via convex optimization. Third, by Proposition 6 the global convergence measure As == r(00)) ming I'(0) at each iteration k either is (11/k))close to optimal (I'(0)) < (l(/k)) or enjoys large descent (Eq. (26)). so we prove the convergence in cases: ((1/K)-optima final 0g, iterate Eq. (26) from Og or from O(1/k) intermediate 0z.
descent for all the corresponding functions
1.2 Related Works
RL with General Utility. Standard RL aims to optimize over the accumulated reward/cost [1] 41]. Some carly operation research works focus on other non-lineat objectives such as variance- -eaaaczeee
MDPs [2), risk-sensitive objectives 22 g [22], entropy exploration [18] constrained RL [2] 35
and learning from demonstration (39 3
54 proposes RL with general utilities to cover the above applications and applies variational policy gradient method that provably converges to the global optimal solution for convex utility. [55]
proposes a variance reduced policy gradient algorithm which requires ((c-3) samples to achieve an e-stationary policy for general utility and Ö(c samples to achieve an e-global optimal policy for convex utility and overparameterized policy. (51) provides a meta-algorithm to solve the convex MDP problem as a min-max game between a policy player and a cost player who produces rewards that the policy player must maximize. They further show that any wothiod-ollving problems under the standard RL settings can be used to solve the more general convex MDP problem. [27] obtains policy

---

gradient theorem for RL with general utilities. 6 proposes a simpler single-loop parameter-free normalized policy gradient algorithm with recursive momentum variance reduction. This algorithm requires OE samples to achieve e-stationary policy in general and OE -2 samples to achieve e-global optimal policy for convex utility. For large finite state action spaces, it requires Ō( samples to achieve e-stationary policy via linear function approximation of the occupancy measure. [53] proposes decentralized multi-agent RL with general utilities. [3] shows that convex RL is subclass of multi-agent mean-field games.
Robust RL. Robust RL is designed to learn policy that is robust to perturbation of environmental factors. Usually robust RL is NP-hard [45), but becomes tractable for ambiguity sets that is (s, a)-
rectangular [36] 20 45
56 or s-rectangular [45 42 23
26].
Methods to solve robust and policy gradient
RL include value iteration
36
20
45
15
25]. policy iteration
20
4
29
56
26 17 28
2 Robust Reinforcement Learning with General Utility
Notations. The space of probability distribution on a space X' is denoted A If X' is finite, we denote its cardinality as (t denotes p-norm of vectors and || || = || ll2 by default.
Learning with General Utility. Reinforcement Learning (RL) with general utility is an emerging learning framework [54]|55]
Reinforcement
[55 6 specified by tuple (S. Py. f. f.. p. 7), with finite state space S, finite action space A, transition kernel pę E (AS)SXA parameterized by & E (E C Rs convex and compact), discount factor y E (0, 1), general utility function f A + I and the distribution p A of the initial state Su- At time t, given the environmental state st, the agent takes action a, ~ (-(-(st) based on a policy Ty E (Ad)5 parameterized by E θ (O C Rd is convex). Then the environment transitions to state 81+1 Pe Pp(-1s),ai) az). The occupancy measure λ A Sx. at (s, a) E x A is defined below.
(0, def (1-7)
Σ
MP To (0: 8, also ~ p),
where F.o.pe denotes the probability measure of the Markov chain {st, at Fcz induced by policy me. transition kernel Pş and the initial distribution p. The aim of the agent find the optimal policy ma that solves minøge f (>o.ç) given fixed transition kernel Pę- Here, f(Ao.g) can be seen as the overall cost of selecting policy Ty in the environment pç. and there are many examples of the utility function ff covering a variety of applications (See Section 2. However, existing works on RL with general utility assume a fixed environmental transition kernel Ps. which may fail many applications where the policy is deployed in real-world environment different from the simulation environment for training. To obtain a policy that is robust to such environmental change, we propose a new learning framework called robust RI. with General Utility as follows.
Our Proposed Robust RL with General Utility. The goal of our proposed robust RL with general utility is to find an optimal robust policy under the worst possible environmental parameter & from an ambiguity set E, as formulated by the following minimax optimization problem with general utility function f.
min max f()o.c), #E0 EEE
In practice, the distance between the real-world environment (for deployment) and simulation environment (for training) is assumed to be bounded. Therefore, E is usually set as a neighborhood around the nominal kernel { estimated from the simulation environment, i.e. E = (g Rde d(E. E) < do} with distance measure d and the distance upper bound do 0.
2.1 Examples of Our Robust RL with General Utility
Example 1: RL with General Utility.
When = ) for a fixed environmental parameter 3, our proposed robust RI. with general utility reduces to (non-robust) RL with general utility minsge f f(oog), as introduced above.
3

---

Example 2: Robust Constrained RL and Its Special Cases.
an emerging learning framework where an agent should obey safety conditions in all possible real-world environments, which is important in safety critical applications such as healthcare and unmanned aerial vehicle 4 For math formulation, denote c(")) c(1), ...... ((K) (Kk), as cost functions S A - IR. At time t, the agent receives performance-related cost (st, az) and safety-related costs (86, at) Define value functions vi(k) and robust 0.g
Robust constrained RL [88
43 40
value functions (*( as follows.
Vik) def (e()) Aa.E) = =E (s, 0.E
v(k) def max SEB
(-(k) 0.
h = -,,,,,,... K.
Then robust constrained RI. is formulated as the following constrained policy optimization problem.
min ((() s.t. ve()) S Th for all k: K,
dgG
where 7h I. is the safety threshold, and (/( S Th means that the safety constraints V S Tk holds for any environmental parameter ş E E.
Proposition 1. The robust constrained RL problem (4) is a special case of our proposed robust RL with general utility 2 using the following convex utility function f.
(clo),) ,)
if (c(c)), S Th for all k = I,...,K K
f(A)
(5)
00,
otherwise
After removing the safety constraints, robust constrained RL reduces to important special case called robust RL (formulated as minage maxçez (c!o), >a.e) with linear utility function s()) (c(0), [36. Furthermore, when E = { for fixed Ć, robust constrained RL. and robust RL reduce to constrained RL [2 and RL [1] respectively. All these examples are important special cases of our proposed robust RL with general utility based on Proposition []]
Example 3: Robust Entropy Regularized RL and Its Special Cases.
Robust entropy regularized RL is also important RL framework with application imitation learn- ing and inverse reinforcement learning which help agents learn from human experts' demonstration and is formulated as the following minimax optimization problem.
32 33
min max
Σ (s) 1 Σ [>v.e(s)
(6)
PE EEE
where is cost function, (s) = E. \0 a) is the state occupancy measure, and H[[e(-|ss]] = - -Ea (als) log up (a|s) ) is the entropy regularizer (with coefficient μ 2 0) which encourages the agent to explore more states and actions and helps to prevent early convergence to sub-optimal policies.
Proposition 2. The robust entropy regularized RL problem (6) is special case of our proposed robust RL with general utility ( using the following convex utility function f.
a(s,a)
f(A== = EXss + + log En Mssaa))
8,a
When μ = 0, robust entropy regularized RL (6) reduces to robust RL (36] When c = 0 but μ > 0, robust entropy regularized RL reduces to robust pure exploration. Furthermore, when E = (τ).
robust entropy regularized RL, robust RL and robus! pure explorution reduce to entropy regularized RI [10,, RL [4] and pure exploration [18 respectively. All these examples are important special cases of our proposed robust RL. with general utility based on Proposition
2.2 Gradients for Our Robust RL with General Utility
Theorem 1. The gradients of the objective function utility can be computed as follows.
2 for our proposed robust RL with general
too
0f()..)) Ds,.e(5r, 01)
vof(No.e)
E.OO.E
Vo log (o(an())) Su ~ppppp
(8)
4=0

---

af(Ao.s) i70,c(5t, at) h=0
Vef(No,e)= ETTOPEE
ve Pe and so
0
(9)
We make the following standard assumptions which are also used in RL with general utility [55 Assumption 1. There exist constants 1 La lp Lps > 0 such that for all s, E S. A.
0, 0' E θ and 5. E B, we have
I log (T(a)))] < tuo
V log Te (als) - V log Te (a)) S 1 - -01,
VV log (s (s, 1 pp:
IV le (5'18, a) - Ve log Pe (5') 1s, a)ll S Iipell 1ll - Ell-
Assumption 2. There exist constants 1, L, such that for all X, X E A [[ s L and (X') V>J(A)Il S LallX' A|I-
Proposition Under Assumptions a the gradients and 99) satisfy the following bounds for any 0, 0' E θ a.d E
Ps 7)2
IVoo(Deg))) :6 :=
(1- [eef(Ao <.g (1
(10)
[Voo(Arr Vol(Ao,))l S Ta,0l10' 0 + Lo,e 11 Ell
(11)
V (ef(Nrrg)) - Vef(Ne,))) S Lg..ol00 011 + Lg. - -Ell.
(12)
where L0.0 = P2, v AAlLa VISIIAA
+ Liohy
(1-7)21 Logg = r0a (1s
(L1 + 22x2 |||, Lg.0
(1-7)a
(1-9)3
Eng feve VIAlLAt (SIIA) (
Lgg:= = T Vii VSSIAA) &a Ex (0(15)) (S)
(1-7)3
(1-7)3
(1 (1->)²
In practice, the exact gradients and (9) are unavailable and can only be estimated via stochastic samples. We refer the details to Appendix C as those largely follow [6].
Define the following projected gradients with stepsizes b, 0, which have been used measure
convergence of algorithms to stationary points of optimization 30
5 47
and RI. problems 49 46
34
G 1 (0,E) = p0- (
(0,) = [roj (=taVe((+))))()ee -c] (13)
3 Gradient Convergence for Convex Utility
Assumption 3. The utility function f(A) is convex.
Robust RL with convex utility functions subsumes many important special cases, including robust constrained RI,, robust entropy regularized RI, constrained RI, robust RL, RL., pure exploration, etc., as shown in Examples 2 and in Section 2.1
Partially inspired by the gradient descent ascent (GDA) algorithm 31 for manconvex-concant minimax optimization, we design the projected stochastic GDA algorithm (Algorithm) I with two phases to solve robust RL with convex utility. The first phase (called original phase) can be seen as projected stochastic GDA algorithm on the original objective function ʃ. Specifically, in the k-th the outer loop with fixed εk. the inner loop applies projected stochastic gradient descent steps (14) to obtain 0g which converges to the global solution of (EEx) == minsee f(Ne.5) as f is convex. Then, we update Ea using the projected stochastic gradient ascent step (15). However, the output & of the first phase only converges to a stationary point of the following the envelope function कb
(E)
max E'EE
[b(g))
E11
(18)
To converge a stationary point of we add the second phase (called corrected phase) which applies projected stochastic GDA to the following corrected objective.
min max f(0.5) = f()o.)) T.g.ells - E||2.
(19)
REB EEE
'The convergence rate of [ is proved in 31 when f(Aa.) is convex function of 6, and will be proved in Appendix N.2 for Theorem 2 when f(X) is convex.
5

---

Algorithm Projected Stochastic Gradient Descent Ascent Algorithm For Convex Utility
1: Hyperparameters: K, T, K", T', o, 8, a, b, Lgg, {m X m , ( 14
(k)
Ik=1
2: Initialize: Ço E E, 8g: 0x E ④
# Begin original phase to solve the original optimization problem 2
3: for Iterations = 0, ...... K do
4: Initialize 0k.0 <- 0g-
5: for Inner steps
0, 1, ..... T do (0) ~ V (No, (.Eu by Algorithm 3 with hyperparameters m " mg H!
6: Obtain Ok.
(1)
7: Apply the following projected stochastic policy gradient descent step.
0 =proje (Ox.r agk.))
(14)
8:
end for
9:
Assign 0g e 8R.T.
Obtain Ok (E) = Vf by Algorithm with hyperparameters m (2) H m H!!).
(2)
10:
11:
Apply the following projected stochastic gradient descent step.
Ek+1 proj= + ))
(15)
12:
end for
Obtain & from (EA k=0 k=0
K-1 uniformly random.
# Begin corrected phase to solve the corrected optimization problem 19
14:
for Iterations = K, + 1,..., K K' do
15:
Initialize εk. & E.
16:
for Inner steps = 0, I,..., T" do
Obtain ( (h....e.d sn..) by Algorithm 3 with hyperparameters m (1) m H!")
(3)
17:
Apply the following projected stochastic gradient ascent step.
Sh.+11 = proj=[Ex,t ag 2T,ge(ER, {))]
(16)
19:
end for
20:
Assign En 5- En,T"- (0)
Obtain 9k ~ VoJ ) by Algorithm with hyperparameters m H1()) (4) H
21:
22:
Apply the following projected stochastic gradient descent step.
a proje (0x bg (
(17)
23:
end for
24:
Output: (0g, (x) where Te is obtained from {K, K + 1...., K K' -1] uniformly at random.
The convergence analysis of Algorithm|] iis challenging largely because f(Ao.g) is only convex function of λσ,ş not of 0. To tackle this challenge for non-robust convex RL with fixed e. [54] assumed that a global Lipschitz continuous inverse mapping from λσς to 0 exists. (55] 6 relaxed
this assumption to the following assumption of local inverse mapping, which covers the popular
direct policy parameterization To (a s) = 0s,a [6] and softmax policy parameterization no (a(s)) =
(see Proposition E. exp(e
exp(e..a)
8 for the proof).
Assumption 4 (Local Invertibility of X. There exists constants fx-1 O and 5 E (0, 1) such that for any fixed 0 E θ and 5 E, the occupancy measure ① satisfies: 1. There exists sets Ua, C O and Vra.s C ASA that contain 0 and λo. respectively, such that bijection. Its inverse denoted as Xn is lx --Lisscthiz.
X U9 Vxo.e
2. There exists at least one optimal policy (E) arg aargming mingee (()r.g) such that for any ô E [0,3].
(1 - 5))o.c + (78-(E).E VAs.E-
Proposition (Projected Gradient Dominance for Convex Utility). Under Assumptions 7 4 the
utility function f satisfies the following gradient dominance property for any O O and
f f(>o.s)
min f()o.s) ( +1 + +Bbo]]l (0,
(20)

---

Proposition 4 indicates that the function f().g) is projected gradient dominant for convex utility function f. which is important in the convergence analysis of Algorithm Our Proposition f is stronger than Lemma F.7 of [6]. a similar gradient dominance property for convex RI. which requires assumption of positive definite Fisher information matrix, involves bias the error term and focuses on unconstrained optimization with softmax parameterized policy (a special of our general parameterized policy with constrained variable E +).
Remark:
Technical Novelty. In our proof, to tackle the constraint 0 E θ which is more challenging than the unconstrained case θ TR $i in [55 6), we apply Assumption 4 to 0 0 10000-000 3G (0, not the obvious choice 8, which yields 0g E θ for any å E [0, 8] such that A0, = (1- (1-8)Aer + d E
Vxo.e. Then
(8))
Vaf(Arr ( (0,-0') Vof(Arr -vo (0, (0s-0) 110 - (0,E)) (l..
where (i) uses the projection property (0g 105-0% 0') | (0.g) Vos(>o=)) S 0 (ii) uses 10s 1 0'| s
(6). The above bound implies Eq. 20 since is convex and ls LipLishct
Assumption 5. is convex and compact with diameter D== == maxx, lks'
=1
Assumption hoold for the commonly used direct kernel parameterization pr(5'ss,)) E(,, a, 8') (for all s, s' E S and a E A) 42 28 26 17 and E defined compact neighborhood around nominal transition kernel parameter g.
We show the gradient convergence result of Algorithm bb the following theorem and demonstrate the gradient convergence by the experiments in Appendix
Theorem 2 (Gradient Convergence for Convex Utility). Suppose Assumptions 7 hold. For any precision O < E S 48T.3. 122x-1(Lan) + 4ī) + Lo]. we can always find proper hyperparameter values of Algorithm ((see Eqs. (150)-115) in Appendix ( these hyperparanter values) such S e The number
that the algorithm output (0 Ex) is an c-close stationary point, that is, E|||c (00 and E[I|G! of required stochastic samples is O (1-7)
< e² with projected gradients G. and Gif) defined in Eq. 13
Proof Sketch of Theorem 2 and Technical Novelty. Inspired by Appendix D of 31,, E from
the first phase satisfies B| V (E) + 0 (see Appendix N.2).. Then, & := EN.T" from the inner update (16) of the second phase converges the unique maximizer (denoted as { of the Lg.e- concave function :((0,,)) as T" + +oo (see Appendix N.3 This means the update step 11 is approximately projected gradient descent for minøge (0), which yields the convergence rate of E B[IG, (Ox [3]] (see Appendix N.4).
However, the biggest challenge is to obtain the convergence rate of E [[]G]] (0g, E2)11 (see Appendix N. which corresponds to & while the second corrected phase aims at the corrected objective f. To show that (eF(O,, x V f Ek), note that vgF(0x.
(0 Ex) = -2,g, ) {] Rs O (already proved) where (5) is the unique maximizer Lg.glls' - EP. strongly concave function of g in Eq. (88). Hence, it suffices to show Ex (E). Note that (0x, Ex) is an approximate Nash equilibrium of F. i.c. En R E :=
and that ($( = 2
of ((5')
arg max:ee](O0n E) (proved above) and 02 ~ arg mrngge Ex) (derived below).
Blf(0r. - min F(0', ((0',x))= (Af min f(Ae ...... - O (0, OII) S O(e), l'ee
d'ee
where (i) uses Proposition 4 Hence, based on the property of Nash equilibrium, we have En RJ
arg max. (b)) (E) where +{{) ;= minsge (() (E)) Le.elE - E1)..
4 Global Convergence on Polyhedral Ambiguity Set
This section aims to obtain a global optimal policy 0* that minimizes the robust utility T(0) def maxçez f(e..). This maximization is challenging for convex utility f. In contrast, global conver-
7

---

gence results have been obtained without such challenge in some important special cases, including convex RL with fixed
6 and robust RL where linear utility is amenable both minge 26 Fortunately, we will show that by using the popular s-rectangular polyhedral ambiguity set E. arg (Axge=/(Aoo)) always exists among the finitely many vertices of E.
[54
5T
and maxgez 36 45
42
23
4.1 S-rectangular Polyhedral Ambiguity Set
In this subsection, we will introduce the popular s-rectangular polyhedral ambiguity set, and derive its important propositions for designing globally converged algorithm.
Fhe global convergence is generally NP-hard, even for the important special case called robust RL with linear uttliity [45]. A common practice to make the problem tractable is to use direct kernel parameterization pe (s (s, a) = E(s, a, 42 28 26 [7] and assume the ambiguity set E to satisfy
some certain rectangularity conditions, such s-rectangularity defined below [45 42 23 26
Assumption 6. We use direct kernel parameterization and assume that E is s-rectangular i.e. X=esE, := {E E (AS)SXA; -Ess,--) E E,, Vs E S}. a Cartesian product of E. c. (A$)A.
Proposition 5 (Local Invertibility of )o,)). Suppose Assumption 2 holdd and Enr is conver set. For any 0 E O, E E E and 5 E [0, 1], define the following kernel parameters {s E (AS)SKA.
arbitrary as long as a, E S
if Ao A (8) =0
Eo(s, als,a,s')
d' (1) +1)+(18)MM)))) (s))a(s, 8'))
(21)
otherwise
8d0.5, (1) (s)
where (s) = EnEA )o.c(s,a) for any E S, 0 E Q and E E. Then Ex E E and its corresponding occupancy measure is λe,es = dd0.s. + -8)
Proposition 5 indicates that the mapping from to λ is locally invertible for rectangular set E, which is important to solve the aforementioned challenge that convex utility is not amenable for maX ()a.s). This role is similar that played by the local invertibility assumption (Assumption 4 for policy 0. To our knowledge, Proposition 5 has never been obtained in the existing literature.
Remark:
Assumption 7. Under Assumption 0 for every 8 E S, E, is polyhedron spanned by finite set of (c(e)) M, Jm=1 CE,, E.s.i.e i.e., E, { Mr gin
vertices VEE):
1/mm 2 0, EM- V'm = 1}.
Polyhedral ambiguity set defined by Assumption 7 inncluess the widely used s-rectangular L, and Lo ambiguity sets, defined as E { E (AS)SXA, IIE(s,;,)) E(s,;,))l, S a,,, Vs E S} for p E oo} respectively 7 19 16 where & E is the nominal transition kernel usually obtained via empirical estimation. On polyhedral ambiguity set, the optimal kernels arg max (Ne.e) can always be obtained at the vertices of E, as shown below.
3 and 7 for any 0 E O, we have maxeez s(oo.) max f(>a.g). where V(E) = X (E.) is the vertex set.
Proposition 6. Under Assumptions
Technical Novelty. Suppose vertex kernel &" arg magxaaee((eee) ff is convex, if λa.g- is convex combination of λe.e; and Aa.g()) for some Eo E E (corresponding g(t) respectively in the proof in Appendix [. then Eo are also optimal. Ideally, i (E) or ED E V(E), the proof is done. However, this is not guaranteed since in Proposition 5 and Assumption 6, the convex combination coefficients differ among the states
is optimal. Since
S. To solve this challenge, it suffices to find such optimal & that differs from g* at only one state 8 such that the non-vertex (s) & V(E)) is replaced with vertex (s) change from non-vertex to vertex for only one state s at a time until the kernel becomes vertex at every state, while keeping the optimality all the way. To find such (s). note that on polyhedral set E., there always exist (s) V(,)) and (o(s) E E, such that the non-vertex point (*((s is convex combination of (s) and (s)s). while (*')) = (s'')=((s'))
V(E.). Then we can conduct such
Eu(s') for any s' * s. Hence, there exists 5 E [0. 1] such that 5* = Es defined by Proposition 5 which implies that do.g- is convex combination of λo,ę; and Ag.goo.
8

---

4.2 Globally Converged Algorithm
The original objective is equivalent to the minimization problem mingee [(0), where
Algorithm Globally Converged Algorithm for Convex Utility on Polyhedral Ambiguity Set
T(0) == (E) [(A.g)
1: Hyperparameters:: K, (or, Ck. Bx K-1
with finite vertex set (()
2: Initialize: On O.
based on Proposition 6 A nat- ural choice to solve this min- imization problem the fol- lowing policy update rule (for simplicity we consider the un- constrained policy space θ = Rdde as in [55 6)).
3: for Iterations k = 0, 1..... K - do
4: Calculate A0, (( and VoJ(>o,.s) for all & V(E).
5:
Select near-optimal vertices = (5 V()) M(News)) 2
maxg'eV(E) f()eL.))) -x..
6:
Find d'g EB,- {dl E RR ||d] S 1 such that (x(d)) I mindeR Ax(d) + + E2-
(Ax is defined in Eq. (2). One way to solve mingeB: A&
is to apply projected subgradient method (28) and obtain
Ok+1 02 - Badd:
(22)
d² E arg (ed, (o.serrAAad))) Ax(d).)
where 3e 0 is the stepsize
7:
Let da == bhd:=<//lll ///ll and obtain 0x41 by Eq. 22
and dg is a unit descent direc-
8: end for
tion of ((2)). Subgradient de- scent method seems obvi-
9: Output: (0k, where εK E arg ma (Nox
ous choice for dy which aligns with the direction of a subgradient (of()ex..e) where EN E arg (Ao..)) ). However, the convergence analysis of subgradient descent method [I1] requires the convexity of f()..s) which does not hold in our setting, and the function value is not monotonically decreasing. To solve these challenges, we design Algorithm P which selects near-optimal vertices == E V(=) [(>o,.s) 2 maxerev(E) J (AAo,.s') a with certain threshold Ø > O and obtains de by solving the convex optimization problem B, A& (d) up to precision 6 > 0, where A& below denotes effective descent of T(fs) along the direction d.
(d) = max (Vo((A,.)) []. de T. B = = E Rdda ||d'l| < 13. EEEt
(23)
Here we only care about the near-optimal vertices in Ex C ((E) because for any worse vertices & E V(E)/Ex, f(0,, <) < max f(Ne,.:)) implies f(0x+1, < maxervv()) I ()0841.5)) for appropriate σ > 0. This means such worse & can not affect the optimization progress T(0x)
T(0x+1). Hence, by solving min (d). can obtain direction de in which all the potentially effective function values (f(e,.=)) have uniformly large amount of descent -Vf()e..2) de.
To analyze the global convergence of Algorithm 2 we want to guarantee sufficient descent [(0x) I(fx+1) whenever 0% is not close to optimal. It suffices to slightly alter Assumption 4 as follows.
Assumption 8. A variant of Assumption 4 holds which replaces the non-robust optimal policy 8* (E) with robust optimal policy 6* arg mingge I(f) and shrinks the range from & E to E VE).
Remark: Assumption g is no stronger than Assumption 4 and also covers the popular direct policy parameterization. Also, Assumption X guarantees that from any policy 0 O there exists partial curve (0s : 8 E [0, }]} towards a robust optimal policy 0" such that Ao = (1 d) + dd e. so we can utilize convexity of f and obtain the following important sufficient descent property.
Proposition 7 (Sufficient Descent Polyhedral Ambiguity Set). Under Assumptions any 0 E θ == Rdd, there exists unit descent direction d ([|d] = such that
at
f()o.) f(Aor S[ V2l Vol c0 VV E
(24)
where 0 E arg mingree 1((0) is given by Assumption 8 and x+ = max(x, 0) for any x I.
Remark: d in Proposition 7 is good descent direction since whenever the function value gap f(x,,)) f()e- .) > it is dominated by the gradient descent amount ( "d >> Unlike
existing gradient dominance properties for robust RL 42 26 17I. f(Ae.e) (Apr < 0 is possible so we use [:]- to cover all cases. This brings challenge and thus novel techniques obtain the first global convergence result of our robust RL with general convex utility as follows.
Theorem 3 (Global Convergence for Convex Utility on Polyhedral Ambiguity Set). Implement
Algorithm with By
2/2(1
k+2
Ok
4r3tals and any E > 0. Then under Assumptions 3 8 the
k+2

---

algorithm output 0g has the following global convergence rate.
4 max EK + K+1 x (Ex L0. + 2v2()).
r(Ox)= - min r(0') S 22 d'Eb
(25)
ISkSk
Remark: The convergence rate (1) matches the state-of-the-art of policy gradient type methods for robust RL (26). while the error term 6A results from solving the convex optimization problem mingeB, Ag(d) in line 6 of Algorithm
Technical Novelty. Applying Proposition 7 to Algorithm with 28xLa, we have
4 [(2)) min ((6') [V26, alck Ax(d4)]] + 2,3
(26)
g'
To overcome the main difficulty caused by [+++ above, we analyze each k-th iteration in cases A& Ax()) 2 0 and (d() < O. If (d,)) ( 2 0, then As S v2fx-1ex + 23r6a and thus A S V2 + 35gl, If (d())) < O, then in Eq. (26) we replace A& (x()), with Ag - A& (x < 0
and remove H++. This along with 1(0k+1) r(0x)=
S BxAA (d+) + L B (by smoothness) implies
DK+1 S
k
D + 0
Ek
(27)
k+2 2
2
(k+ 22
Then we obtain the rate (25) in cases: If Ax(d)) < for all h: = 0, 1,.., K 1, iterate Eq. 27
from Du; If 1
0, A S 62 + σы: If A (dk- 2 0 while (x(ds) <
for all k = K" K",..., K - 1, iterate Eq. (27 from Ax 3 V262 - + -14
Algorithm| involves convex optimization problems minse As(d), which can be solved via the following projected subgradient method for t = 0, T,
dR < proj [dr,e a v (Ao,,en.)) }}, where Ex.t E arg max VoJ dd.,
de,t-
(28)
The best direction d'. E arg max (d,,, (0S1ST) (d) from the above subgradient method achieves EN accuracy within = O(Ex²) steps [ЛI. which yields the following complexity result.
Corollary 1. Under the conditions of Theorem 3 for any e O, implement Algorithm with K
10x-11-1(2x1100 + +2/2la) iterations and T 366 3613_112- f.e- subgradient descent updates (28)
with stepsize 3 to obtain d'. Then the outpui 0x achieves [(0x) - mingre r(00' Se.
Finally, we can prove that all these Assumptions I requiree by our convergence results (Theorems
2 and can be satisfied by the following examples.
Proposition 8. Assumptions
78 are all satisfied if we use the following choices:
Softmax policy puramelerizatinn Ta(a(s)
E. explo.,..)' where 0 E O = R] SIXLA for
exp(O...)
some constant R > 0 to prevent To To(als (ulss)fron from approaching 0.
Direct kernel parameterization pe (s' (s,a) Es with s-rectangular Li Loo ambiguity
sets defined as E = { E (AS)SXA, : [E((s,..:) E(s,;.:))lp I a,,, E S} for p E {1, o0) respectively, where the fixed nominal kernel & satiisies ( a,s') > ass Vs, a, s' to prevent pe (s from approaching O.
The utility function f()) defined in Eq. for robust entropy regularized RL and its special cases, within the range E A= = (No.e : 0 E O, c E EE for the domains & and E selected above.
5 Conclusion
In this work, we propose robust RL with general utility, the first learning framework that obtains a robust policy for RL with general utility. We propose a stochastic policy gradient type algorithm for convex utilities and obtains its sample complexity result for gradient convergence. Furthermore, for convex utility on polyhedral ambiguity set, we propose an alternative policy gradient type algorithm and obtain its global convergence rate. Note that this globally converged algorithm requires enumeration among many vertices, and thus it is an important future direction to reduce enumeration by utilizing structural properties. addition, to extend the results to large or continuous state-action space is also an interesting direction.
10

---

Acknowledgments
This work was partially supported by NSF IIS 2347592, 2347604, 2348159, 2348169, DBI 2405416, CCF 2348306, CNS 2347617.
References
[1] Joshua Achiam, David Held, Aviv Tamar, and Pieter Abbeel. Constrained policy optimization. In International conference on machine learning, pages 22-31, 2017.
[2] Eitan Altman. Constrained Markov decision processes. Routledge, 2021.
[3] Brenna D Argall, Sonia Chernova, Manuela Veloso, and Brett Browning. A survey of robot learning from demonstration. Robotics and autonomous systems, 57(5):469-483, 2009.
[4] Kishan Panaganti Badrinath and Dileep Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference on Machine Learning, pages 51 511-520, 2021.
[5] Maxim Viktorovich Balashov. The gradient projection algorithm for a proximally smooth set and function with lipschitz continuous gradient. Sbornik: Mathematics, 21 211(4);481, 2020.
[6] Anas Barakat, Ilyas Fatkhullin, and Niao He. Reinforcement learning with general utilities: Simpler variance reduction and large state-action space. In International Conference on Machine Learning, 2023.
[7] Bahram Behzadian, Marek Petrik, and Chin Pang Ho. Fast algorithms for Loc -.-conttrained s- rectangular robust mdps. In Proceedings of the International Conference on Neural Information Processing Systems (Neurips), 2021.
[8] Vivek Borkar and Sean P Meyn. Risk-sensitive optimal control for markov decision processes with monotone cost. Mathematics of Operations Research, 27(1):192-209 2002.
[9] Winfried Bruns and Joseph Gubeladze. Polytopes, rings, and K-theory. Springer Science & Business Media, 2009.
[10] Shicong Cen, Chen Cheng, Yuxin Chen, Yuting Wei, and Yuejie Chi. Fast global convergence of natural policy gradient methods with entropy regularization. Operations Research, 70(4):2563- 2578, 2022.
[11] Yuxin Chen. Subgradient methods. htt.ps://yuxxnnchennn// wwtp::200....iiitioo. wit.ub.thu...... icliueb2. optimi zat. http://eccuuees/uuurrddireeteeee
2020. 202..
[12] Jerzy Filar, Lodewijk CM Kallenberg, and Huey-Miin Lee. Variance- penaaizee markov decision processes. Mathematics of Operations Research, 14(1):147-161, 1989.
[13] Matthieu Geist, Julien Pérolat, Mathieu Laurière, Romuald Elie, Sarah Perrin, Oliver Bachem, Rémi Munos, and Olivier Pietquin. Concave utility reinforcement learning: The mean-field game viewpoint. In Proceedings of the s International Conference on Autonomous Agents and Multiagent Systems, pages 489-497, 2022.
[14] Mohammad Ghavamzadeh. Marek Petrik, and Yinlam Chow. Safe policy improvement by minimizing robust baseline regret. In Proceedings of the International Conference on Neural Information Processing Systems (Neurips), volume 29, 2016.
[15] Julien Grand-Clémen and Christian Kroer. Scalable first-order methods for robust mdps. In Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pages 12086-1209) 2021.
[16] Julien Grand-Clément and Marek Petrik. Reducing blackwell and average optimality to dis- counted mdps via the blackwell discount factor. In Proceedings of the International Conference on Neural Information Processing Systems (Neurips), 2023.
11

---

[17] Etash Kumar Guha and Jason D Lee. Solving robust mdps through no-regret dynamics. ArXiv:2305.19035, 2023.
[18] Elad Hazan, Sham Kakade, Karan Singh, and Abby Van Soest. Provably efficient maximum entropy exploration. In International Conference Machine Learning, pages 2681-2691, 2019.
[19] Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Partial policy iteration for 11-robust markov decision processes. Journal of Machine Learning Research, 22(275):1-46, 2021.
[20] Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2):257-280, 2005.
[21] Leslie Pack Kaelbling, Michael L. Littman, and Andrew W Moore. Reinforcement learning: A survey. Journal of artificial intelligence research, 4:237-285, 1996.
[22] Lodewijk CM Kallenberg. Survey of linear programming for standard and nonstandard marko- vian control problems. part i: Theory. Zeitschrift für Operations Research, 40:1-42, 1994.
[23] Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Levy, and Shie Mannor. Policy gra- dient for rectangular robust markov decision processes. In Proceedings of the International Conference on Neural Information Processing Systems (Neurips), 2023.
[24] Navdeep Kumar, Kfir Levy, Kaixin Wang, and Shie Mannor: Efficient policy iteration for robust markov decision processes via regularization. ArXiv:2205.14327 2022.
[25] Navdeep Kumar, Kfrr Levy, Kaixin Wang, and Shie Mannor. An efficient solution to s- rectangular robust markov decision processes. ArXiv:2301. 2023.
[26] Navdeep Kumar, Ilnura Usmanova, Kfir Yehuda Levy, and Shie Mannor. Towards faster global convergence of robust policy gradient methods. In Sixteenth European Workshop on Reinforcement Learning 2023.
[27] Navdeep Kumar, Kaixin Wang, Kfir Levy, and Shie Mannor. Policy gradient for reinforcement learning with general utilities. ArXiv:2210.0099) 2023.
[28] Mengmeng Li, Tobias Sutter, and Daniel Kuhn. Policy gradient algorithms for robust mdps with non-rectangular uncertainty sets. ArXiv:2305.19004, 2023.
[29] Yan Li, Guanghui Lan, and Tuo Zhao. First-order policy optimization for robust markov decision process. ArXiv:2209.10577 2023.
[30] Zhize Li and Jian Li. simple proximal stochastic gradient method for nonsmooth nonconvex optimization. In Proceedings of the International Conference on Neural Information Processing Systems (Neurips), pages 5569-5579, 2018
[31] Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for Nonconvex-concaa minimax problems. In International Conference Machine Learning, pages 5083-6092 2020.
[32] Tien Mai and Patrick Jaillet. Robust entropy-regulatized markov decision processes. ArXiv:2112.15364 2021.
[33] Daniel J Mankowitz, Nir Levine, Rae Jeong, Abbas Abdolmaleki, Jost Tobias Springenberg, Yuanyuan Shi. Jackie Kay, Todd Hester, Timothy Mann, and Martin Riedmiller. Robust reinforcement learning for continuous control with model misspecification. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
[34] Weichao Mao, Lin Yang, Kaiqing Zhang, and Tamer Basar. On improving model-free algorithms for decentralized multi-agent reinforcement learning. In International Conference on Machine Learning, pages 15007-15049, 2022.
[35] Sobhan Miryoosefi, Kianté Brantley, Hal Daumé, Miroslav Dudík, and Robert E Schapire Reinforcement learning with convex constraints. Proceedings of the International Conference on Neural Information Processing Systems (Neurips), pages 14093-14105 2019.
12

---

[36] Arnab Nilim and Laurent EI Ghaoui. Robust control of markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
[37] Xue Bin Peng. Marcin Andrychowiez, Wojciech Zaremba, and Pieter Abbeel. Sim-to-real transfer of robotic control with dynamies randomization, In 2018 JEEE international conference on robotics and automation (ICRA), pages 3803-3810. IEEE, 2018.
[38] Reazul Hasan Russel, Mouhacine Benosman, and Jeroen Van Baar. Robust constrained-mdds: Soft-constrained robust policy optimization under model uncertainty. ArXhv:2010.0487,.22 2020.
[39] Stefan Schaal. Learning from demonstration. In Proceedings of the International Conference on Neural Information Processing Systems (Neurips), volume 9, 1996.
[40] Zhongchang Sun, Sihong He, Fei Miao, and Shaofeng Zou. Constrained reinforcement learning under model mismatch. ArXiv:2405.01327, 2024.
[41] Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
[42] Qiuhao Wang, Chin Pang Ho, and Marek Petrik. Policy gradient in robust mdps with global convergence guarantee. In Proceedings of the International Conference on Machine Learning (ICML), volume 202, pages 35763-35797, 23-29 Jul 2023.
[43] Yue Wang, Fei Miao, and Shaofeng Zou, ArXi::2209.06866 2022.
Robust constrained reinforcement learning.
[44] Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In Proceedings of the International Conference on Machine Learning (ICML), pages 23484-23524 2022.
[45] Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust markov decision processes. Mathematics of Operations Research, 38(1):153-18) 183, 2013.
[46] Lin Xiao. On the convergence rates of policy gradient methods. Journal of Machine Learning Research, 23(282):1-36 2022.
[47] Tesi Xiao, Krishna Balasubramanian, and Saeed Ghadimi. constrained stochastic multi-level composition optimization. In Proceedings of the International Conference Neural Information Processing Systems (Neurips), 2022.
A projection-free free algorithm for
[48] Huan Xu and Shie Mannor. Parametric regret in uncertain markov decision processes. In Proceedings of the 48h IEEE Conference Decision and Control (CDC) held held jointly with 2009 IEEE, 2009.
28th Chinese Control Conference, pages
[49] Pan Xu, Felicia Gao, and Quanquan Gu. Sample efficient policy gradient methods with recursive variance reduction. In Proceedings of the International Conference on Learning Representations (ICLR), 2020.
[50] Rui Yuan, Robert M Gower, and Alessandro Lazaric. A general sample complexity analysis of vanilla policy gradient. In International Conference on Artificial Intelligence and Statistics, pages
2022.
[51] Tom Zahavy, Brendan O'Donoghue, Guillaume Desjardins, and Satinder Singh. Reward is enough for convex mdps. In Proceedings of the International Conference on Neural Information Processing Systems (Neurips), volume 34, pages 257559, 2021.
[52] Junyu Zhang, Amrit Singh Bedi, Mengdi Wang, and Alec Koppel. Cautious reinforcement learning via distributional risk in the dual domain. ArXiv:2002. 2475, 2020.
[53] Junyu Zhang, Amrit Singh Bedi, Mengdi Wang, and Alec Koppel. Multi-agent reinforcement learning with general utilities via decentralized shadow reward actor-critic. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 36, pages 9031-9039, 2022.
13

---

[54] Junyu Zhang, Alec Koppel, Amrit Singh Bedi, Csaba Szepesvári, and Mengdi Wang. Variational policy gradient method for reinforcement learning with general utilities. In Proceedings of the International Conference on Neural Information Processing Systems (Neurips), pages 4572-4583, 2020.
[55] Junyu Zhang, Chengzhuo Ni, Zheng Yu, Csaba Szepesvari, and Mengdi Wang. On the conver- gence and sample efficiency of reduccd policy gradient method. In Proceedings of the International Conference on Neural Information Processing Systems (Neurips), 2021.
[56] Ruida Zhou, Tao Liu, Min Cheng, Dileep Kalathil, Panganamala Kumar, and Chao Tian. Natural actor-critic for robust reinforcement learning with function approximation. In Proceedings of the International Conference on Neural Information Processing Systems (Neurips), 2023.
14

---

Appendix
Table of Contents
A Experiments
15
B Supporting Lemmas
16
Stochastic Gradients
19
Proof of Proposition
20
E Proof Proposition
21
F Proof Proposition
3
21
G Proof of Proposition 4
26
H Proof Proposition 5
26
Proof of Proposition 6
27
Proof of Proposition
28
Proof of Proposition X
29
K. Proof of Assumptions
and
29
Proof Assumptions
5 6 and
about ambiguity set
................................
30
Proof Assumptions
and
30
L Proof Proposition
33
M Proof of Theorem 1
35
Proof of Theorem 2
36
N.1
Convergence Rate of Inner Update Step (14) of the First Original Phase
36
N.2
Convergence Rate of V ( from the First Original Phase
37
Convergence of the Inner Update Step (16) of the Second Corrected Phase
39
N.4
Convergence Rate of E B|||G] (0:, [2)1
40
N.5
Convergence Rate of I [| (0;. [;)1
42
N.6
Substituting Hyperparameters
43
Proof of Theorem
3
46
0.1
Analyze the k-th Iteration
47
0.2 Obtain the Convergence Rate (25)
47
Proof Corollary
A
Experiments
In this section, we present simulation results of Algorithm convex utility.
Simulation Setting. We choose (1,2, 2, ,S} with 10 states and = (1, A}
with A 5 actions. The discount factor 0.95 and we select uniform distribution as the
15

---

E + [[ EwI12
0.0054
0.0052
0.0050
(0x.
0.0048
||Gb (
0.0046
0.0
0.5
1.0
1.5
2.0
2.5
3.0
3.5
Sample Complexity
1e7
Figure I: Numerical Experimental Result (the green vertical line denotes the transition from Phase I to Phase II of Algorithm T).
initial state distribution p. optimize the objective function 2 we apply direct parameterization to policy parameter 02 (als) E θ (As and transition kernel parameter &a,a.e' ((ss(ss,)) E (A5)SXA, In order to preserve E(:,;,s') E A We select nominal kernel E(),,,'))
|10+..l as Σ. [10+e,11 where Exr A/(0, 1) for each s' E S. Then we select sufficiently small radius r= 0.01 < mill,,,s' Ex...s' and use the L ambiguity set =\t {E [|E((,,;,)) i. ((,,;, Sr) (for transition kernel) such that all & E have all positive entries. As for the general utility function /. we use the following convex entropy function with application to exploration (Example 2.2 of [54]
min max (()a.)) BE EEE
Σ (s) log (s.
(29)
where \s. = EnEe (s. a) denotes the state visitation measure for any E S, 0 E + and E
Hyperparameters. For Algorithm
[ we use the following hyperparameters obtained from fine-
uning but not from Theorem 2 K 200, T 25, K' 300, T" 25, 0.002, 9 0.001,
a = 0.002, = 0.002, Lggg = 20, m) (1) = 15, ( 100, mg = 15, H (1) = 100, m (2) 15,
( 100, m
(2)
15, H 100, m
(3) 10, H(3) 100, m
(3)
(3) 10, H (3) 100, m.
(4) 10.
H 4) 100, ma 4) 10, H. 4) 100.
Environment. The experiment implemented on Python 3.8 on AMD EPYC-7313 CPU with 3.00GHz, which costs about 1.5 hours in total.
Results. The numerical result of Algorithm is shown in Figure 1 Here the y-axis is the norm the
true projected gradient / /IIa (0x, E²) ||G| (0x, (x) at each outer iteration k of both phases of Algorithm| I (separated by the green vertical dashed line), and the x-axis is the sample complexity (i.e.. the total number of generated samples up iteration k). Figure| shows that the projected gradient decays and converges to small value, which matches Theorem
B Supporting Lemmas
Lemma 1. Under Assumption 7 for any 8, of S, a E A. e O, E.5' E we have
bo (als) (e(aas)) < ex. 1101 - 011 (pe(s'(s, pe(s'ls, a)) s lpo Ell.
(30)
V (s'ess) (epe(s'ls, a)ll < (s + e || Elll
(31)
16

---

Proof. Based on Assumption | the following inequalities holds for all s, E S, a A,0 Ç E E. which by Lagrange mean value theorem directly proves Eq. (30)
[[
Ve { < Laoi
[|Vepe
|s,a)] IV lolgoes"'sssa)) S Epp
Then we prove Eq.
31 as follows.
V -
P5 |s, a) log
Sper(s'|s, a) [V lo
(8 (s a) Ve Pe (5') (s. a)ll
+ Ipee [s, a) - (s a)ll Ve logpe(s'|s,a))
per (5' 1,, a) pe 115 - El1 + fp -b 11 - Ell
Pe a)) [%,11le - Ell
where (i) uses Eq. (30) and Assumption [
Lemma 2. For any 0 E Q and & E =, the occupancy measure d defined by Eq. is the unique solution to the following Bellman equation of X E [A5)
Ms'.a') = (1 - ()((s)) + Σ M(s, (sssa) 1s, ()) no(d'ls), s' EES,'EE E.
(32)
3,a
Therefore, the state occupancy measure )o,s(s)= = EaEs (es(s,a) satisfies
)0,e(s,a)= >0 (0
(33)
Proof. First, we can prove that Aa,5 satisfies Eq.
32 as follows.
\ aa) (1 71)
P Toppe (st = s'.a-= = a'sso ~ p)
t=0
= - 7)
P.o.pp = (5t== 8'1800 ~p) p)
==a(a's'))1 - 7) P Pr (50 s'150 ~ p) + 7
' mo (P = 5'180 p]]
(=0
t00
-o(d)1s)(117)(16)) +
pp('))
Σ
Σ
P
To (0t s,a, = also p))p((((s,,0)
t=0
= (1- (1-
+ Σ (s()
toc
(1- 7) 1=0
Σ
AIP Ko (st s,a; also -))l
(1 (1-))p(s)) Σ
() no(a'ls')
Next, we prove the uniqueness. Suppose \1, d2 R|S|x|A satisfies Eq.
32
Then we have
- -11(s' -
= Σ (Te(d'ls') Σ P2ss, - a)ssa))pe(6
s'a
3,a
(e((s (109
8,a
5 (e) )1(s,a)),
17

---

which implies that - (1-7)Eea (2((, (r(),)) -((s,a) & 0 and thus 22 = λ1, i.c., the solution to Eq.
32 is unique.
Finally, we will prove Eq.
33 Note that
a)) (8) (1- ()(s)) + ((s,a))(((1sss))))
{0,g(s)= =
aEA
8,0
where (i) uses Eq.
Then Eq.
33
can be proved by substituting the above equality into Eq.
32
Lemma 3. Under Assumption 7 the occupancy measure ① satisfies the following Lipschitz proper- ties for any 0,0' E A and E =.
Aw 20.el allps- Pe ||+
To
Toll
7pp V
S
1s' - -11+ no
A 0 - 011
(34)
1
1 7
Proof. For any 0, 0' E and E E E, we have
1o Ao.ell
Por (o'. a')) (o
Σ y (d'1s')
Σ ( (lls.a)pp ()) [1
+ (1 - >)pss))s)>>- + Σ N (s, (s) (a'ls)) Ta(a'|s') -m(l 2/22
(8)
Yoee (a'ls')
Σ
No e (s, (s. (s)1))))))))) - pe(5"|s,
8,a
yoo (a'ls") Σ (e
(0.c(s.
s,a
(11 7)p(s') + Σ ds (p)(s)ss)) a)) (d'ls) no(a'|s\)]
(20))
(lpelle 11E' - -1l)>2
Σ Σ (e(551s,,))00:xss0.0 ) 2 +
E(en 110 110 01)2
7
(10)
I plpe v /SSIIEE - Ell + -.
ΣΣ 8,a
- (s, + v V|All100 - 01
Stxpe SSIIIS - Ell + 7ll de + Er V AAll10 OII,
where (i) uses Eq. (3).. (ii) uses triangular inequality, (iii) uses Lemma I
En गe (a'ls')² < 1 and
E.1(( 7) p)s's + Ea,a Ao. (s, a)pç (ells,,o) a)] = 1 and (iv) uses Jensen's 's inequality. Then Eq.
34 can be proved by rearranging the above inequality.
Lemma 4. The distance between any pair of probability vectors x, y E X on finite space X has the upper bound that || yil I /2.
Proof. Denote d = | and xyz yy as the j-th entry of x, y respectively. Then
|| - 2112 < 2
+
20
<
x + y 2
j=1
18

---

Lemma S. Under Assumptions 2 the projected gradients in 13 have the following properties.
| (0, < [Voo(Ao S to.
|G (0, = (ee((Ao,))) S t
(35)
" (0', ( - (g Lo.0) 116' A|| + Lo,glle' - E11
(36)
| (0', (') G (0, E) & L..010'' - 01l + { a
+ Le.s) IIE Ell-
(37)
simply follows from the contraction property of Proof. The proof for | (0, [) in Eq. projection as follows.
35
| (0, = 3
1 21100 proje (0-3 - -1100 (0- Ve [
Then, (oo()ee) s Eo by Proposition
3 The proof logie for ||G/ (0, <) is the same.
Next, we prove Eq. 366) as follows and the proof of Eq. 37 follows the same logic.
|G (0, (0', { G 000 (0,
|projs 10' - (o projjl (Vo((oo)))
$ 3 18' l|l + Vof((Ao,)) - Vof(Arr.e))
(0)
+ L.,) 110' 01 + Le Ell,
(38)
3
where uses Proposition
Lemma 6. Suppose X' c. Fd is a closed convex set. For any æ E Fd and x' e X, we have
[x' -prooox (x)) projx (x)) 0
(39)
Proof. For any 8 1]. 25 8x + (1 5) (r)jx belongs to the convex X' since x', ".rroxx()) (z) E X. Then based on the definition projection we have
0 S| x1 - [lproxx x|12
<| (x)ox(())] 2(xs- (r) [x pr)
=8 8 111|= p 28'n' proix(x)] -x-poxxx()]]
The above inequality be rearranged follows
8
l (z) - projx(=)] s '122' projx(x)]1
2
which proves Eq.
39 as 6 +0.
C
Stochastic Gradients
To get the stochastic estimation of the gradients follows.
8 and 9).
we first estimate the occupancy measure
①
7 my Hy
S(T(A)
(1 s, s a),
(40)
mA
where 1{-} is an indicator function and (1) = {T." jm contains mx independent trajectories
(A) (A) (2) -1
Li Jk=0 (i= L.=,...,,m my) of length HA generated from the policy and transition
kernel pe. Then the estimated cost function is 2 = V
19

---

Algorithm 3 Obtain Stochastic Gradients at (0,5)
1: Input: = (0.5) 2 O Z.
2: Hyperparameters: m., Hx, ma, Hg. mg, Hgg
3: Generate independent trajectories T, 7|(1 = { ai 1h-
(A) 1 (i = m.) from To. p
4: Obtain X(=(2); 8, a) for every 8, a E by Eq. (40) with 7()) = (T((2) )==
5: Obtain ē = Vxf[A(T()))
6: Generate independent trajectories 7; = (. 1=h
(0) (0) He-
(i ...,, ma) from No. Pe-
7: Obtain ( (0) (, by Eq. (4) with (()) = {r: (-(0)mm
8: Generate independent trajectories T [ hh0
(5) (5) H--1
(i = 1, .....,,, mz) from ne. Ps-
9: Obtain (7((), 0, by Eq. with 7( = (7,() (5)
Ti=l
10: Output: (T(0), 0.E. = Vof(da,)), ( ( 0,5,0) vel()os)
The stochastic gradients 8 and 9 can be approximated respectively by the following stochastic sample averaged values known as GPOMDP [50]
1 Ho-1 1
me
= me
V 9 log To (a s4,h))
(41)
My
(7(6), 0,,,7 1
( log Pe 1
(5) 2,
(42)
ma
1=0
h=
(5) mg where -(0) = {T. } and (5) = {
(0)mm h
J==l contain my independent trajectories T.
(0 (8) Ho-1
1, ..... ma) and mg independent trajectories Ti = (0 ai h=o
(E) Hg
(g(9 HH (i= mg) respectively, both generated from the policy me and transition kernel pç-
We summarize the procedure of obtaining the stochastic gradients (8) and (9) in Algorithm 3 These stochastic gradients approximate the true gradients with the following error bounds. Proposition 9. Under Assumptions error bounds.
7 and the stochastic gradients and (42) have the following
E E. (0,,,)
(AI(E))))
362
1 1 +
[R/S]| AA
+ + + Ho(1 - 2012
(43)
(1 74
m1
mo
B Br (T(5),,
0, - -Ve(Aoos)l
362 pt
7) |3 - ++ +22t1)
B
+ + + He(1 - 211
(44)
m1
mg
D Proof of Proposition 1
As follows, we slightly rewrite the utility function ʃ defined in Eq. 5), by replacing with Ae.5.
f(Ao.)) ( (c >e.e)
(c()), de.e) S Tx for all == 1,...,A K
+ 00,
otherwise
Therefore, for any E O, we have
(0)
Ao.s)
if (c(*), do S To for all & E E and k = 1,..., K
max f(No.)) EEE
EEE
+00,
otherwise
3 i.e. ((()) def maxçez(c(k) do,e). the
Recalling the definition of the robust value function equation above can be rewritten as follows.
())
if (R) I Th for all l: = 1,...,K K otherwise
max f()o.)) = EE
oC,
20

---

Therefore. 0 E Q minimizes maxçez f ((e,g) if and only if solves the constrained robust RL problem as repeated below.
min (0) lg@ 8 s.t. Vg( Th for all l = = I, K.
Finally, we will prove that (A) defined in Eq.
( is a convex function. Note that A = (A A 0 k==1 Ag also convex set. Then for any X1, Au E ASXA
(c(4), X) Tie is convex set, so A
and a E [0, we aim to prove that
faa + (1 - ao) S (1-
(45)
If either A $ A d A, then Eq. (45) obviously holds as the right side equals +00. Otherwise, if Ao A, then δΛ + +1 - 8) E as A is a convex set, and thus Eq. (45) holds with equality as proved below.
fςdA1 + (1- (1-6)Aol = δΛ1 + (1 (1-8))o)
=5(c(0) A1) + (1-6)(c , =5((A1) (1 -o))
E Proof of Proposition 2
The utility function f in Eq. satisfies
[(ha,z) = Σ A0, a) [c(s. + wog
En Ao,e(s,aa)
( a)((s,) + 1 Σ Aa (o.g())m(((as))00m000)
s.a
8,a
[N 5,a
Da.e (H
where (i) uses (0.g(5) = E. denotes the entropy function that ([Ta(-ss) exactly the minimax objective function 66) of the robust entropy regularized RL.
E.. (s, a) and Eq. (33) that dg.5 (s, a) = )g.e (s) and (ii) Ln (alas) log (a)ss)) The above function is
Finally, will prove that f(A) defined in Eq. 7 is convex function. For any λo A1 A and 8 E [0, 1), denote As- σλ1 + (1 8)A0. As(s) E. \o(s, a) and policy =s(aas) As(s) the convexity of f can be proved as follows. 5f(Ai) ) (1 6){(2n) - [(ss)
Aa(s,a)
Then,
[4 Σ as) log (s) (1
An(s,a) As(s, a) log Ao(s)
As(s, a)
+ (1 8))o0s,
As(s)
=4
Σ
[An (lo(s, + (1 5)Ao(s, a) log (a(ss)
8.0
())1(s, (1 (1- (0)
log (slls)
(als))
+ - 6))o())To(((l))) log To(a|s)
Σ (s) log na(als)
Ts(als)
# Σ (I) + () 2
F Proof of Proposition 3
The first formula of Eq. (I0) can be proved follows and the second formula can be proved in the same way.
+oc
[of
< E
ETO.PE
Σ
Ac(ss, ar)
Vo log (a)a(s))))
21

---

(11)
+00
c
TTO
to0
(t + 1)
(1 (1-
1=
where uses Eq. (11 and (ii) uses c(se, a+) E [0, 1] and Assumption !
Define the following V function.
y'csse, a0) m].
Vo,e(c) = Er Pe
(46)
For any fixed cost function c: ::S S x A- + R, the gradient Vo VoVo,(()) can be rewritten as follows.
+00
VoVo,e(c)
ERO.PE
> c/(s,, at)
V log Ta(anlss)
1=0
h=
+00
= Exe.Pe
Vo To
c( at)
1=h
h
P mo (5h =8 a|30 V log to(as)
h=0
8,a
4000
Ego
Σ
+ c(80, ar) 8h = =
+oc
Torpp (8h = =,,00 = =0/50 ~ p) Ve log To (als)
8.0 h=0
E
(c((8) 80 8,00 =a)
(i)
Vo To (oll::/mm
(47)
s,a
where (i) uses Eq. (5) of [6] and (ii) uses the occupancy measure ① and defines the following Q function.
(s. = E.ooPe
Σ
r at) so s, 00 =
(48)
The above Q function has the following upper bound
QQ.e(s, a;)))
Cmax 1-7¹
(49)
where Cmax max.,a lo(s, a)l and also satisfies the following Bellman equation.
Q a; c) = c(s, a) + Pe(''ss, a)ma \) Qo. d':e).
(50)
s'.0'
Therefore, for any 0 E O, E = = and fixed cost function c, we have
max max QQr a; c) (s.c(s,acc)) 8,a
< max
Ie (6 18, a) pe (s' 1s, a) TT (wlls)))
8.0
(s' (ssssssss)))) (s =o(d1s")llQuee
max
22

---

max
[s s (5 d':c) Qag((s d')c)l
st,0'
(1) YCmax
mmax Ie (1),))) Pe(-1s,))ll + max (-1s) no(-1s)]la)
+ y max
1Q8 1 (s, a; c) - Qs,e a; e)),
5
where (i) uses Eq. 49). Rearranging the above inequality yields that
max Qu Sorgg(s, c) (s,((s,acc)
Mmma
(max IIpe (-1s, a) - pc a)ll + max || (-1s) - no(-|s]]11)
(1 7)2
a,
Cmax
7)2 (fog (Slls - E1+ 4 |Alloo 01).
(51)
where (i) uses Lemma
I For any O. E and fixed cost functionn e, e', we have
(1)
max QQ, a; Q0,c(o a;))) S.roppe
Σ (st ax) - c(sc,at)) 80 3,00 a
8,0
x '|c'' cllo0 1|l lid-c0 -clo00
(52)
1 --9
where (i) uses Eq.
(8).
Therefore, Eq.
be proved as follows.
(of s() vol()a
VoVe & V (
V VAf
(1)
1
(x - Ao.e(1; a) (ab Vas(oe
s,0
Σ Aa.e (8, Voloo Vas - a; V
s,0
do.s (s. (al /og a; VV/(( Q0 Vx VAl(Noot) (Noz))
5,a
(10
E l
l E ( 01
- tes(s,
(1 7)2
7e2
As, (1- []- (frz SS1I''
- Ell + e Alll0' -
lx
Σ An.E(s, [xl(>or))) - VaS(Maee)loo
+ (1 7)
8,a
(111 F. la / |
Liol> 110'-011
|>0:e'- - -ooell + (1 7)2 - 011
(1 7)2
Eng I.x poog do.ell
(1 - 7)3 181118 Ell Exo AAll -01) + (1 7)2
(10) 40 (L> + la (AVIS|(AA) Thee VTSIE' - El1 lxo /All000 - -011
+ Loggs Ex
(1 7)2 110' 01
7)2
1 1-7
+ (1 7]
(e 1S - Ell + 6no |All0' 01)
23

---

(1) uo Lpe (LA+2ex ISIAAIIE EII -EEI
( (|I(Lttta//1/SII L la
100'
-11,
(1-7)3
1-7))
where (i) uses the gradient (47 (ii) uses Assumptions 12 and Eqs. (49
and 52 with
Cmax = V .. loc replaced by its upper bound εx. (ii) uses Assumption
(iV) uses Lemma
and (v) uses Assumption
The proof of Eq. (12 follows the same logic. To elaborate, V& VeVo,e(c) can be derived follows in similar way to the derivation of Eq. (47
Ve Vo.g(()) = ET
ye(ss at)
Vg log (sgpe(9n an)
h=0
toc
P To (3h = 0, = a, 8h+1 = s ~ p] (s'
h=0
9,0,8'
4000
E
c(s,, (t) 8h 8, an a, 8h+1 =s' 8')
toc
Σ
h
Σ
To.PE (8h = 8, 0h = al30 ~ p)pe (8'1 a) Ve logre(s')s,))
h=0
8,0,0'
to0
Exo.P
E
((s.a)=
+ Σ re((s) az) so 0.00 =0,8==/
1 Σ
da Vepe (s' ()) + (V),(si;c)
(53)
s,a.8'
where uses the occupancy measure I and defines the following V function.
(o.e(5';c) == Em Pe
Σ
No(ss = of.
(54)
The above V function has the following upper bound
Cmax (V.g(s. I-
(55)
where Crax max,,a (c(s, a)l and also satisfies the following Bellman equation.
(o.g(s: Σ To(a|s) ((s,)) + 2c(("1s,,)Voosss53
(56)
As result,
max (s;c) - Vo,e(s;))
max Σ Tor (als))
(a(a))) [((8,a)| +
+ y max
Σ To Ta(ss))
Σ (s pe(s'ls, - Ve)
+ 7 max
Σ ne (als)
Σ (s
Vo.c(':cc))
Cmax (lzol All
A|| + 7 SIll'' - Ell) + ? max Vor g (s;c) (o)(
where (i) uses Eq. (55 and Lemma
T
Rearranging the above inequality yields that
max - Vole(s;))] (1 7)3
Cmax
(Alo 0ll + 7 EI) (57)
24

---

Similar to Eq. 52 we have
max (o.g(s;)) Volg(s;)) s cclo clloc
(58)
1 1-7
Therefore, we can prove Eq.
follows.
vef(Nn.e) vef(Ao WgVor.lVas((o000
VeVo,e Vale
1
Σ
- - - -es((s_a)|1Veerr(((ss..))
7 8,0,8'
(af(Ar + VV VAfeAel
1
)a Vepe - Vepe(s)ss.))
+ 1-7
S,0,s'
Vaf( Vo V
+
Σ
/ Va Volls:: Vxf(Arrs))
3,0,8!
+
A0 Vepe(6'(s,a)))
8,0,s'
(7) Volels;
(1
7ex
Ps
(x + 1-7) 8,0,8'
Σ (s (s (x,
7
+ 1-7
1
(ex+ + yex
Σ
(0, PppPe + & -1ll''Ef] -Ell
Sin,a!
+ 78
lx
Σ
)0,5(s, (pp((s))
(1- (1- (ozo
(4 All6 01 + 1SllEE -El)
S,a,5!
+ Epp
7>V ) - vaf(Mee))l + VAA(Ao))) Vaf(Ne)))
)a,(5s (s'))s)))
1-7
(61)) De ex [S] A
ex P2 + f2 (81)
- +
1|5"= -El
7)2
(1 (1- 7)2
Texppe
(Al1 - 811 + + 1511s' El] + Eye Li
+ (1 7)3
(1 - - || - -do.el
(in) 1p (LA + la lavIs |IS yla VISIIE - +11+ ero v /A|l100 -011
Ea(Tep + (2)15))
11" Ell
(1 7)2
1 --
(1 71-
Tlilps
+ (1 7)3
(enolAAl10' 011 + + EIl
LT Eee |Al(L> + La VISILAI
110 - 011
(1 7)
122 Pc
V [ + 2Cx 1 (81A4
+ la (x + (gg
115' Ell-
(1-7)3
(1 (1-7)²
where (i) uses the gradient (53) and denotes Vxf(Agr (x = os(Avr
ax(s.a) as the (s, a) element of Vx(()rr)r)) (ii) uses VePe (s'|s, a) = pe (s'ls, a Ve (s" a). Assumptions 12 and Eqs.
(TD. (55). (57) and (58) with GInxx
Vx (Ao .² )l ooo replaced by its upper bound ex (iii) uses
Assumptions and (iv) uses Eq. 34
25

---

G Proof of Proposition
Implement one projected gradient step from 0 and obtain 0' = -proje (0 - (Vol()o,e) = 0 (0, (0, {) is defined by Eq. (13). Based on Assumption for any 5 E [0. 8). there exists 0g E ④ such that A0 (1 5) + (E)) E VAL.s Based on
3 (0,E) where the projected gradient G3
Assumption 4 for any E [0, 6). there exists Og E θ such that A0s (1 o) + d')o-().s Vigr,e Then we have,
(3)
|0, 0'11 S fx-1
- Ao,ell 5l (oo do.El S V2822-1, 1 1111se1-1
(59)
where (i) uses the Lgg -smoothness of f()..)) based on Proposition
(ii) uses Lemma
By applying Lemma 6 to X = θ x = 0 -Vof()oe)) = 0s E (so projx(4) = 0'
0 g (0, obtain that
(0s - 0') T ( Vof SO.
(60)
Then on one hand, f(Nos,e) has the following lower bound.
f(Nos.)) 2 2(()r + (of(Nor T(0s (0s -0)- 2
110 _200100 0'11
La.0
(10 2(Drr)) + [Vo[(Aorss) -ool(d,s) + (0, [0] T
Lg.0
(0s- -0)
100 -
0'122
2
(40)
L0.0
2 =((ra)))= (Lo - | (0, 10, 0'11
110s
0
2
( 2 - 2226 + 1) || 0 (0, - 20
(61)
where (i) and (iii) use smmoosmos of / s(A.g) based on Proposition 3 (ii) uses Eq. (60). and
(iv) uses Lemma 5 |10g 0'l 22 (obtained in the same way as Eq. (59) and 0' 0
( - (0,E). On the other hand, J (No..e) has the following upper bound since ʃ is convex.
f(Xer.s) (1-)))(1))()) 6)f(>e 5) + 8f (1 6)f()rr + min f(or,s).
(62)
8"E8
The above two inequalities 661 and 62
imply that
1 ([((Ar)) f(Wo,))]
f(Ao,e)
min f (Aarre) 8"
S lim sup limsup 6--00 I
< 5v + 1) (0.E)
(63)
Finally, we prove Eq. (0) follows.
(
(()a.) (((rr()) + 6o110' -
(40)
min f()ar.)) 1 + +1) + Alo] ||G (0, E)Il.
where (i) uses Eq.
10 which implics that fx.e is Ep-Lipschitz, (ii) uses 0' - = -BG (0, E) and
Eq. (63)
H Proof of Proposition
We will first prove that &a E E. Note that the s-rectangular ambiguity set E can be expressed as Cartesian product of E, for all E S. Hence, as E is convex, E. is convex for all E S. Therefore, for any 8 E S, (s ..)) E E, since is a convex combination of (x. E E, and (1(8, E E, defined by Eq. (1 E E.
26

---

Next, we will prove Ao.e= = 8λ0.E, + (1 aeA0 so.
Denote Às == δ + + 8) so the aim it suffices to prove the following equation.
becomes to prove Ao,E, Ag. Based on Lemma
As d') = [1 (1-7))((s) + +2 Σ An(s, 8, s. mo(a"ss", ( s'E E E.. (64)
8,0
For each 8 E S, consider the following two cases.
(Case 1): Ao.g, (s) or A8,5o (s) 0.
Note that
(s,
@ [8An, (s,a) + (1 8)Aa.c (s, a)] dda.,, (") (1- o) (s) (s)
Sd0,2, (5) + (1 - 6)A0,5 (0) (s)
(60 To(als)[8Aoss (s) (1 8))0.c( (s) 070.E, (1) a, 8¹) + - -6)A0.60 (o),
670,5 (s) + (1 - -o)
(10) 8A0.E (s) 5') + (1- - 80 (s.
(65)
where (i) uses Eq. 21 and As == 8A0.2. + (1 -)) (ii) and (iii) use Eq. 33
(Case 2): Ao,o (s) A0.5i (s) = 0.
In this case, (s) = dd (1-11)1100000 (s) = 0 and thus As a) = A0,5, (8, = (0,50
0 for any A, so Eq. (65) also holds for any choice of :s,
Therefore, we can prove Eq.
66 as follows.
- (0--))(s))- + Σ Xo(8, A0(0 =o(('lss)
a.a
@ (1 11-))((s)) +7 Σ Io (s. (1- (1-8))a0ca (.. To(d'ss)
8.a
=6 (1 7)p(s') + Σ (s, (s, solaaasssssssssss
- (1((1-))00) ()')
(s, (z) a) (,) Tal'a ma(a'ls")
828.5 (s) +1 5) (s) = \s(ssa),
where (i) uses Eq. 665 and As dda.E, + (1 8) 8)>a.so and (ii) applies Lemma 2 to Aa.E and Ao.so
I Proof of Proposition 6
Fix any 0 O and there exists at least one 8" E arg ( If E V(3) X (E.), then this proposition directly holds. Hence, we focus the case where E* $ VE)). which means (*p) & v(E..) for at least one s0 E S.
Based on Assumption 6 there exists a probability vector = [M [ PM,,) such that (*(o)
EM 5m (100)
(80). where denote ('(s) := ..) E, for all g' E. Without loss of generality,
we assume 11 = max M.M. Vm (Otherwise we can make this assumption hold by permutating the elements in each E,.).
For any c 0, define ET. g(+ E (AS)5xA such that (s) = (() = (s) for any + so, while at 80 we define Eì (so) = c(00) V(E,,) and
Mao
( =5" + (so) - E (so) = [11 E)u - =fe(00) + Σ
(1 + (
m=2
which implies that
cg(e) + 13 g"
(66)
1 1+c
27

---

It is easily seen that či E E by its definition. Since lim,-++ol(1 + e)²2 (s) cl = (1 = gax M, Vm (3) > there exists sufficiently small 0 such that [(1 + c) -
c) (1+e)uM, (s)] E [0, 1| is probability vector and thus g(r) E E. Furthermore, select arbitrary å E [0, if A (50) A0.e; (50) 0 and the following 8 otherwise.
(5)
8
(67)
c (5o) + (5))
where === ==E= (0,c(s,a) a) is defined as the state occupancy measure for any S, E θ :
and { E E. Then can be directly verified that 5* satisfies the following equality.
arbitrary as long as (=, A
if (s)= (8)=0 =0
((
8d0.c 8 (s) (11 (s)
otherwise
dA (5) + (1-8) (1-
Hence, based on Proposition 5 5 satisfies
A = 5A0.E1 + (1 8)An.eo
(68)
On one hand, f(Ao.s)) S f(Ao.e-) and ((o,,ec)) S s(Dos=) since 8* 5* arg ( On the other hand, the above Eq. 68) along with convexity of f implies that
[()a.x- S 55()ee)) + (1 (Agg()))())).
Therefore, s(Aa,s;) - ((nns)))) = maxe ((o,e") Ei V()), then the proof
done. Otherwise, note that (50) & V(E..) while Ei (sn) E V(( and (s) Eo (s) for any 8 * 8o. Hence, in the same way, can obtain the sequence E- S3. ...S....,, ..4 that satisfies the following conditions by changing non-vertex into vertex at one state each time until no non-vertex remains (i.e., until the condition 2 below holds):
For k S (zk) & V(E..) while (sk) E ((Es)), and (s) = EE+1 (8)
for any + 5k-
2. SV E VE)).
3. For 1 S k N. f(N..;;) = maxpes ()
As result, we find the optimal vertex EN E V(E) O arg f which concludes the proof.
Proof of Proposition
Based on Assumption for any 0 E and E [0,5], there exists O5 E O such that λosig =
(1 - 8) + 8A
(i) |0, - 01 S la 11 Ao,ell = 562-1 -or - No.el S 28
(
(69)
where (i) uses the La smoothness of f()..e) based on Proposition 3 (ii) uses Lemma Hence, on one hand, using L smoothness of f f().g) based on Proposition bound.
(Nos.e) has the following lower
Lg.0 110s 01
s(Ma,,)) 2 20(0.e)) + (os(No.e) (0s - 0)
(70)
2
On the other hand, f()o..)) has the following upper bound since is convex.
[(>e..)) S (1 8) + 6f(60= :) (1 8)5(Ae.)) + 8 min max s(ho e' gree
(71)
Combining the above two inequalities, we obtain that
-Vol(No.e) 0s f(Xo.)) s()o..))
T..00 110g 01l
10; Oll 00g 01l
28

---

(1 ( ming'e maxere g()
La.0
110g - 011
|0: - 01
(1) f(Ao.s) - ming co ma (()rse))
v2ôlz LL0,0
(72)
226x11
2
where (i) uses Eq. (1). and (ii) uses Eq.
669
and assumes / ((A,,) 2 mingree maxera g(
without loss of generality (otherwise, Eq. 24
trivially holds).
Based on the Bolzano- theorem, there exists a sequence 8n +0 such that
0s. -0
[[0
d E Rde as n + +oc, Hence, ||d] 1 and we can conclude the proof by letting = 6n and
n + to0 in the above inequality.
K Proof of Proposition
8
K.1 Proof of Assumptions 1 2 and
Proposition indicates that the utility function f defined by Eq. is convex, which proves
Assumption
To prove Assumptions 1 and it suffices to prove that the following functions have bounded first-order and second-order derivatives for any (s, a, S x A.S.
function of θ = 1- Al, 2. log log(s(s')s, logE(s, a, s') as a function of & E {E' E (AS)SXA (s.
1. log (u(a)s) 0s,a - log En exp(Os.a')
- E(s,i,))lo S as Vs E S} where p E {1, and E(s,a, > as a.
A(s.a) 3. S(A) En, M(s a) [c(s, a) + poo E. X(e.0)) (repeat Eq. as a function of A E
(Ao. 0 E 0,E E}.
For any 0 E θ = - R, R S|x|A|, we have
Ta(a Exeexp(0 exp(02.a.) Tmin def
exp(Oaa)
exp(-It)
exp(-RR + (IA) 1) exp(It) 0.
(73)
When p = or p- = xc, any E satisfies
P a) a(s,a, E(s, (,s, ||{(s,;,)) - E(s,;,,))lp
2 {(s, a s¹) a
2 Emin
def
min 3,a,
fin, a, s') a.l > 0,
(74)
where Smin > 0 since it is minimum over finitely many positive numbers E(s, a, 8') - as Then for any 0 O and & E, we have
400
a)) def (1-7) Σ
P no pe (st s, also ~ p)
71 7) pe (s) s,a, also p)
711 7) Σ p(s')=Toa'' Ro ('ppsssssssssss//_ (als))
8',a'
71 7) Σ ( Amin
e'.a'
Amin def Emin mmin (1 - -7) > 0.
(75)
Finally, for any (s, a, s'), ($1, 01 s (52, a2, s2) E S x A x S. we obtain all the derivative bounds as follows, where 1 1-} an indicator function.
log (als)) (001810))
((s1 = [1 = a} - m E 1-11,
29

---

(100 1/81 - s)to(ailo) 2 log To (als)
8 loggoiin (a(ass)
[-11 1].
(0(82, a2)
@logpe(d'(s,d)
1 1151,,1,, 51) (5,a, [0, Eminl
(E(s),
a(),a,
PP =- (s,,, 81)= (82, Uz x62) a, (0, El 0J.
06($1, o4 )0 dg 02, 822
0f(A)
=c(s1, 01) (1) +log (1)
+1 a1),
E (Smmialog((AAA)) log((AA)2min): Grax +
0A($1.01)
En a()
Ev ((s1
where Cmin = mins, c(s, a) and Gmax = maxs,a a(s,a).
S(A()
=1ss1 =2] [ fai = =02)
1(a1 = =a2) -1(1,
0A(s1. (1)
M(11,a)
Ev A(s1.
EE ((81.00))
E [4pAmin
1
+
|A|2
min
Ammu
|Al
K.2 Proof of Assumptions
5
and aabout ambiguity set E
It is straightforward to verify that the ambiguity set E = {E E (A5)SxA, :.:) - E(s,;;;))
ag, Vs 8} (p E {1, (o)) is convex and compact, which proves Assumption 5
Assumption 6 can be proved easily by letting E. (5. (AS)A (p E (o.))
lls. E(s,;, S as)
Then will prove Assumption] 7 that is, E, tE. E (A$)A || [(s 1p
a,) (p (1)
a polyhedron. Based on Definition 1.1 and Theorem 1.26 of [9]. is equivalent to prove that E, is bounded (already proved above) and is an intersection of finitely many closed half-planes (obvious based on the definitions of || |/1 and || lls)).
K.3 Proof of Assumptions and
We will only prove Assumption 8 since Assumption 4 can be proved in the same way.
Fix any & E E and 0 E θ = [- R| |||||| Then we select any 8" 0" (0) E arg gemi. 110'
Olooc where O mmn == arg mingre r(0') is compact set since a continuous function.
Define the following notations.
(8) (1 8)da,s dAo-.g for 8 [0, 1] (we select 7= == 1).
(8) Policy #8.8 defined as (a 2.. (e,o) where
=ar (
(s.
(s)
(Note that (s) 2 (s. 2 Amin > 0, so 0.g
(s)
X (0) can be the denominator and T8.
(6) > 0).
(a|s)
0/1 E IS with each entry defined as follows.
(1 (1- d) a) + ((
a.g llo
log (1 d) (s, () exp( Om.a) + SAo= (8, a) expp-000 -02
(76)
which is valid since =0. (als)
(5)
and ro(als) 2 Amin
Uoos (0(0) 8 E [0, 1]} (|
Vo.5 (1 5 [0. 1]} SXA
Now, it remains to prove the following two statements.
(P1): 0 0 and f(1) l*
(P2): Uo θ |-R. R. R| |
30

---

(P3): (6)
(P4): The mapping 0(8) directions.
A from Lo. to Vo.g is a bijection and is Lipschitz continuous in both
(P1) obviously follows from Eq. (6).
Note that ( defined by Eq. 76) is a monotone function of 8 [0, 1), and (P1) implies that
(0 = 0s.a E I-R, R and 0 proves (P2).
9. 02 E I-R, RJ. Therefore, ( E [-R, R which
To prove (P3), rewrite Eq. (76) as follows.
(0gg)) 8.0
= logg 0 8, a)] - log [1 8) ())0.(5)) exp(- + 8dg. (0s),,,))TT (als) exp((-0% [a,a]]
(1 ())
(do-,E(t)
llog 0.g 8, a)) - log
exp(Ba,aa) + Egr exp(e) 2,0!
6))
O76-
Log (1 (5) (als) log
(8)
Σne exp(0s,ar) llog | (a|s [c]s] + co(s),
En exp 2,00
(8)
(77)
where we denote cs(s) == log [1 [s)] log
(1-8)do,e())
)dgr,els) Σ. expl0"
Therefore,
En exp((222)
exp [(0 )
(al() = 1,g (8,() a)
Tn (a|s)
(78)
En. exp )
/ (8)
Note that for any l' E (| we have
Ao )0,
Σ (s'
n Σ (1 (1)())(s)) + Σ el () To (a'ls')
5,a
=(1 (11-20) 7)p(s') + (5)
(79)
where (i) uses Lemma] Then we have
(1 (1- + Σ ()p((1 (d))))))) - (
8.0
2 (a'ls') (1 - (1-2)(()) + Σ ( {62
8,a
(a'ls') (1 7))((')) + Σ Na.e(s, -
+ (1 5) 5)m
000 (a'ls) (1-7))())) + Σ
- Xo (('))
3,a
(152)
0,
where (i) uses Eq.
78).
(ii) uses 2/ = (1 5)^o.5 + dd and (iii) uses the Eq. 779 for
0' E {00, O). Based on Lemma 2
the equality above implies (P3).
Next, prove (P4). Note that the mapping from 0 to X A is Lipschitz continuous based on Lemma Hence, only need to consider its reverse mapping.
31

---

If Ag & Ao.g. then Tg- = no. Hence, 8 E mmi := arg ming ce [(6) because r(0') m f f() can be seen as function of wy. Therefore, 6* 0 which means Up = {0} and
Vo,g = (do.e) are singletons. In this case, (P4) trivially holds.
Therefore, we focus the case where Xo- # Ao.g. Before proving (P4), we will prove the following statement.
(P5) There exists constant L' > such that I10 -11o0 I L'IlAor A0,glloo for any 0 E O [- [-R R||S)x|A|
Define 6* E A E RISIXIA such that 0%,a 0% + 1 verified that
I Ear (. Then it can be easily
(80)
Σ 02.00' = Σ 0s.a'.
(81)
o'
exp(O..a) Note that To(aas) E. exp(o...)) and To (als)
En exp(o' ". so 8' -0,,0 log To (als) log To (a|s) 8) + u(s) where u(s) = log EEa' exp(O",a - log La exp(Os.e) }] Then combining
exp(11'
with Eq. (1.. we obtain that u(s) = TAT La llog To(a'ss) log no (a (a'[s)). Therefore,
V 0s,al
S log To. (als) log logTo(als)| +
log (o(a'ls) - log TTa (d||s)
A
(1) min To- (a|s) To(a|s)) +
Tuin
(TO(aals) - To- Ta-(a'1s)) (a'1s))
|Al
<2m min max TT- (a-((a))) Thg (a(aals)) [a'1s)]
Ao- g c(s,a') )0.{(s,a))
<2 min max
( s
(sx)(s)
Ao (o- a') A =2m min max
(s) ( Der(()))))))))))))))))))))))))) - Ao- [s)]]
(80)
2
max (0=,,(s,aa) d0,c(s,a')
A
Ami Tinn
2
Eor (0,e(0,a))
+ A min min
2
4/| 11- A0-_g- Aa.el
(82)
| Tmin
where (i) uses Eqs.
73 and 80 which imply that (a)a))), no. (als) = T (als) E [Tmin 1] for
0, 0r E O (ii) uses Xo (o. [Apmii for 0, O" E θ as result of Eq. (75)
Based on the definition of 6' we have max.' &/t ming' 6hr = maxa' Pz,a' min Or.a' S 2R. Therefore, for each & S, there are three cases: R S min, 0%t S maxa 0% S R.
max,' 8ha > R and min, 8 < R, and we can define 8" E R S|x|A as follows
0'+ 0%
RS min 0- S max O'. S R
0"
0'+ + R, max a'
max O'r >
8.0
a'
8,0 min 0+ R, a'
min 0r < R
can be easily verified that the 0" defined above satisfies 0" E θ [-R, R S|X|A| (since
max, 0'* mina 0'+ < 2R) and Tgr Ter- Th. (the second = comes from Eq. (80). Therefore, 8" E Omin and thus
110 01100 - 110" 011 S 110" 1 + 110 - 01
(83)
32

---

where (i) uses H" E min and 0" E arg e | - -llcc To further obtain the upper bound of |00" 0*1 oo in the above inequality, we discuss the three aforementioned cases.
(Case D): When - R I mina' 0g,a- maxe 0² R, we have 6",a - -0" O.
(Case II): When maxo 0%.0a > R, we have
( R S max - max 0n. S 110 - -0lloos
<
0 a,
5,a = max 6,0'
a'
a
where (i) uses 0 θ = [-R,, R [|
(Case III:: When ming' 0t.a'
R. we have
R (1) S min 0,,a' min 6% S 110 - 01loo
0 8 0 min Or
where (i) uses 0 E θ = [-R, R (ix|a|
Summarizing the above three cases, obtain that 110" - 100 110 - 01 and therefore Eq. (83) implies that
(0) 811 da.eloo del I', (84)
00" - Ol I 110" 1101~ + 110" - - 22100 - 01 S 2| Tmin
where uses Eq. (2). This proves (P5).
consider Eq.
76 as a function of å and take its derivative as follows.
8(06.)) s.a
06
Ao ((, 0) - )0,e(8,a) +
A e a) exp(-)xx)p) ()
(1 (), _ho,, (s) (1- d) (8, exp(- 0s,a) el0 exp( 02,0)
( Ap d0.ello + | a) (exp(( (a)a)) exp(- (xp(-0xaa) exp(-0s,a) (0, a) (8,
Amin
Amin exp( - RR)
(10 A & -00,elo00 + exp(It)(5,a - 0s + (el))ll..ssss0. A0 (s,
Amin
Amin exp( (P( R)
(112) Do & d0.Ello + +exp(2
1'11a0- A0. + 11 Aa.elox
Amin
Amin
2(T.' + exxx((2
|A0- - d0,elloc
(85)
Amin
where (i) uses 0, 0t E I-R, ||lsi and Eq. (5). (ii) uses 0,0º N = 1-1, (iii)
uses Eq. 84
Therefore, for any 8, E [0, 1]. we have
1000 0 2(L' exp(2
|>00 2
Amin
2(L' + ex2(X2R
||1/02
A9, loc:
(6)
Amin
which proves the statement (P4) and thus proves Assumption R Assumption can be proved in the same way simply by replacing 0* with any (E)
arg millgree .))
L Proof of Proposition 9
The estimated occupancy measure (40) measure with truncation level HĄ-
unbiased estimator of the following truncated occupancy
HA-1
A
(Hx)
(s,a) def
(1 - 7)
Σ
7 Proopee (sx 5, a. also ~ p).
(86)
33

---

Denote X(r(Al): = ( 88,0)) a)] AOESKA
RRIIIAI, (HA))
[ (x,
E RISIIAI,
λ == [Nn,e(s, a)) s,ess E RISILAI, following upper bound.
Then the estimation error of occupancy measure has the
E ETO.PS [|((+(A)) Ao,ell"
Vargome [][T(A1)] + Bag. (1(Hta) AB,EEl
(88
Var (T2
Σ
(1 7)
"TProo To.ps (8: 8, a|so p)
ma
8,a
t= H
(116)
1T12((110)) )1 + (1 (1-1)
+000
(1-7) 7)
Σ
400
2 To (8: 8, also ~ p))
ma
H
8,a
H=HA
1
2H1
(87)
mx
where (i) uses E| x = Var + | |XX| 11 for random vector X == A(((A)) A0.c. (ii) uses Eqs. ① and (86) and uses the fact that À defined by Eq. 40) is average among the mn i.idd. individual
estimators A,(T(() ;s, a) == (1 - 7) Σm= 7 ( 1,6 = 8, a = a} for i = I...., my, (ii) uses Var S x for random vector X = (T(1)) and P PT (st = 8, at = also p) E [o. 1). and (iv) uses 0 (T E.. (1 ;
ss,a) a) and E., I Po (st s, a2 a p) 1.
Define the cost function as c= (. The error of estimating by 7= (x)(A(7(A1) has the following upper bounds.
ERo.PE ||c cll =Bmo.p V>f vaf(Ho.))12
1 E Bor.o [²(T(2)) - A0.el12
1 +22t1s)
(88)
m71
Exo.pe |10 - c|l < | To. Po. 11 - cll S L (-- ms
+ +HH
(89)
where (i) uses Assumption and (ii) uses Eq. 87
Also, c and have the following norm bound
based on Assumption 2
max (1c//0, |1]),0) S lx
(90)
Note that (7(()) 0,C,e) e) defined by Eq. 41 (replace ? with e) is the average of the following me i..d. individual stochastic gradients.
Ho
di (T: 0.E.c) =
Σ
(0)
ai
(0) o log n (a (
(91)
1=0
Then it can be easily seen that 9 following truncated policy gradient.
(T 0, C)
(0)
defined above is an unbiased estimator of the
Ho Σ
(Hal (Ao.s) = E.r.pe
N a.)
Vo log no (an (sn)s))))))))))()))))
(92)
h=0
Also, 9, (T)))) 0, s. c) can be bounded as follows by using Eq.
90 and Assumption
Ho-1
l1g; (7(
(0) 0, <
Σ
(0)
Vo log no (a
(1))
34

---

He
Σ (t 11+1 - Exlro 1=0
(93)
(1 7)-
Therefore, we can prove Eq. 43 as follows, and Eq. (44) can be proved using the same logic.
11a.eell9" 0.
Vof(Ao,e)l1
<31E Pe 10
0,
(7 0)(.
+ 3E PE 119 10 (7 0 c))) Vof (XH, + V (HH) (HH,)) (o
(4)
mg H
(0) ? [ (00)) cfsaae a
(0)
Vo log To (a (1,,) ||²
+ 3 Var
[g (T 0, c)l + 3 BrO.Ps
Σ
ree(s;, at)
V log (s(an(ss)
t=
h=0
(10)
me H -1
2
S 3I Po
1/1 - c1lo0 + 1)exo]
mm
t=
t00
+ m0
Var
191
(0) (Ti 0,,,,, c)] +
Σ (1+)))
H=
(110)
+ +222 (
Eno
2
Mg (1 - 11) )² + 2 + H2(1 - 7)] 2
3
Exlxo
|1
(1-7)3
+
(1-7)²
322 (1 7)
R + lll + Ho(l - 2
To
131STLA1
+ 7 2H
where (i) uses Eqs. Assumption 1 and g (8) (0) 0.
992 and V Vo (Ho) (8..g) =R (0) (,, c)
(r)),, 0, E,
(ii) uses Eq. (90).
E.c)
i== gi (T("), (,("),0,E
(0)
0,0,E, E, c) where (9. (0) (T (0)
0, E, m) are
m
independent, (iii) uses Eqs. (89) and
M Proof of Theorem
The policy gradient (8 is proved by Eqs, (5) and (6) of (6. We will next prove the transition gradient
Under the transition kernel pę and policy ne the probability of obtaining certain trajectory Te {sh, an V U [s(+1} with initial state distribution P can be expressed as follows.
P Pro.pe (Tt) = p(su)
II A=0
(o)(a/ls))p(99)1111 an)].
Hence, the gradient of the log of the above probability can be computed as follows.
Ve log P. Pe (5)
Ve p9 an).
(94)
hm
Denote c: Vxf(>o,c). Then the transition gradient 9 can be obtained follows.
Vef(Ne.e) = vaf(Ne.e) Teden
Σ V Σ p " ProOEE (st 0, = a)
5.a
7'c(se, at (P) (T))d
35

---

7/0(81, a1) VePPooo (Tx)d7:
V (T)) P PRO.Ee (T))
y'((se ar)
Po (Te)dr,
B BranPrying
((c((e az) Ve log F. xo (Te) ~ pl
E ETO.PE
Σ
fo(se, at) Σ
Ve log (s 8n, an) 50 ~
h=0
where uses Eq. (94).
N Proof of Theorem 2
Based on Proposition we define the following error terms E and (0) (i,j E (1,2,3.4) 4)) to bound the estimation errors of the stochastic gradients lines 6 I7 and 21 of Algorithm respectively.
302
L
1 (-1)
2220
+ + + H²)) (1 -1-1111110 21-7))222
(95)
(1 - 7
(])
m
m
36 Pe
E
=
T
()) +2205)
+
20
+ 1 + H (1)))222222
(96)
m
m
Then prove Theorem 2 in the following procedures.
N.1 Convergence Rate of Inner Update Step (14) of the First Original Phase
Lemma Suppose Assumptions 7 hold. Apply the projected stochastic gradient descent step
(14) in Algorithm to the policy optimization problem minege f f(>e.eu) with fixed &N E. Select stepsize 2Lo and initialization 0R,o 0o- Then the outpui On == Og.T globally converges at the following rate for any 8 E (0
E E(S(NoLee)) min (Ao.Eu) [Ex
E
min ((Ao.s)))E + +4 4T.,,ol--10
(97)
8EB
8Lo.0*
where 1 is defined in Eq. 95).
Proof. For any 0n + in the update rule (4 there exists at least one optimal policy 0% arg minge (hor such that for any å [0, there exists 0 θ that satisfies Ag(0) (1 8))or, d'oo, Since f is convex, have
f( (
(1-0))))) + 8f(Not, = (1- (N)....))
min f(Ao.s)). 0EB
(98)
Then, analyze the optimization progress of the stochastie gradient descent step 11 follows.
[(N0..12:5u)
<((Nou..s) + (of(eeneesa)) (( 0k.e) + Lo.9
100,141 - 02.e
2
=f(Nous.sa++ + (of()ou. gk.ll
(0)] (0x,141 0k.))
Lg.0 10x,441 1n.ell 2
+ (o( ( (6K,441 0k.)) +
36

---

1 Vol (oo,A), -
1/ 112 L0.0 1k,,041 Ok,z1l'
<f(Neunike) +
2L
+ (9k.e) (0)) ((9h.))(BB.444 (0N,041- -b,,e) +
L0.0
||0,,141 - 0k,ell
2
<((Aon. + (9ke,) (
( (0p,1+1
- -0p,s) + Lo,oll0u.441 - 0x,el1
Vof (o0,)..1))))) - 111112
+ 2L0.0
(ABc.
+ (0)) T(0 -O..) + L0,0110..1 02,=11
1 VoI 9k,t!
96,211? 112
+ 2T.000
< <((o.. Vef ) (00 - 0k,1)
L0.0
10
- 0x,el
2
+ [g Vof(Noe. ) (0
h,t 8x,z) +
3L0.8
|0(0)
0x.el
2
k,t
+
1
Vof
9k.1 11
(0)
2Lg.0
(146)
ff(Ag())
f(A
Vof - 1/.2112 1
L8.9
(10(0]
On.ell
2L0,8
2
+ 2
31..0
|0[0]]
k,t
12,112+
2La.0
[of(Aee.
gi.t
(10)
1 IVo 12.0112 + 4L (99)
I (1-8) (>o à min [(Noes) + L0.0
where (i) and (iii) Lo, so.othmoo of f()..s)) based Proposition
(ii) the update rule
(44 with stepsize 2La which implies that 0s.411 E arg mingge (( (0 Ox,c) + Le 0
8 [3]. (iv) uses Eq. (98) and the following inequality.
(ii) [10/.]] fxlll Sex P Aeu,,ge = lx (22-881120 A00 So Ao
S
V2e, 15,
where (i) uses Assumption expectation, obtain that
4 Handd (ii) uses Lemma Rearranging Eq.
(99) and taking conditional
{(J(No.1t1&))) min f(No.sw) BEO
1 - [[ (e) +L .02
<(1 [f min [Ex Lø,0
(0) <(1 - 6)
E(1)
min 0eB
((e Ex] + &L 182
Le
where (i) Eq. (43
in Proposition and F,(") defined in Eq. (55) with j 1. Then the
convergence rate 997
can be proved by iterating the above inequality as follows.
N.2 Convergence Rate of (E) from the First Original Phase
Lemma 8. Implement the first original phase of Algoritim 7 with stepsizes a 2 and B 2Le.VK VK' The inner projected stochastic gradient descent step (4) implemented up to precision
Eo 0 as follows.
E (Aos...))))
min f(No.ca))E)) < cg.
(100)
BEO
Then, the output & of the first original phase has the following convergence rate.
8f
8E (Eo))
E ||[|1
+ 10L + 20L + +00
(101)
KB
37

---

where E is defined in Eq. (96) with j 2.
Proof. For any fixed & E, define the optimal policy parameter 0 (5) and the optimal utility value (E) as follows.
(5) :E arg min f()..g)
(102)
8E0
(<) min f(a..)) f(No-(s).s) e
(103)
Since f()o,) is Tggg--mooot for any 0 Q based Proposition for any (0,g) E O E. f(Aogg)) L ||!' Ell is a concave function of g'. As result, ((g') L - E|l is Tig.e-strongl concave function of g and thus has the following unique maximizer.
( =- arg e'E=
[#(E') Le,elle' - E|]²]
(104)
Accordingly, we define the following Moreau envelope function (repeat Eq.
(8))
(5)
max E [E()) Lg.elle' - =1²] = (() Lg (5) - El1
(105)
Based on Lemma 3.6 of 31,, ④ is Lg.e-smoott with
Vक((E) 2Ig,e(E -
(106)
Similar to Lemma D.3 of 31, obtain the following ascent property of the above envelope function for any 0, I....,K K
E [[((Ex+)]EE)]
(
_E( - L...|lss(( proj= + (96( (5) (1({Es)
2 =E(O(E - Le,s + Tl]l (Ex) projs ( + V f (Ao, .xx) 11
- Le,(1 + Txx ">>'|lprooof )||projj [Ex + vV (Doc. - proja (5x + /gh (E) [x()a))
000
E ((((" - TT)l Eall? L3. + Tx) V (Mex.sa)
2I + +x) - Ex. (AI(Ans.s))
1e,00 Tx )116 - 1l)
(00)
(EE" - L + (I +
- Exll 2 Lg.g (1+ Tz)
+ +2Lg, + Tu )E ( f(No).) {(NoLee)) - LEg 11E (Ex) - Ex Ex
2
2 (1 Tx 1) E
(9)
2 (Ex)) - Le,E( + (E)) - Exl12 -1 Tx)
+
L5,5 (Ex()) - -cal1?] - LL +
+ +2 (1+TTb) (Ex)) - (Exx) - c
Tr T
2
(0t) ((Ex) L5. ((((((((s) (Ex)
Eall (5 Th)e
21 + Tx)) [ [15((E) - -xel1 - -co] - -2 + + F1(5) (
Le,e
(w4))
2 (Ex) + (8(1 +
Lg,g | T2c.g.82 (1 (1 + Tx)
Tk
31 + TR)en 0g (1 T D
(107)
where (i) uses Eqs. 15) and (T0)), (ii) holds for any Tı > whose value to be determined later,
(iii) uses contraction property of projection and 5x (Ex) E. (iv) uses Propositions 3 9 and the error
38

---

term E defined in Eq.
(66.. (v) uses Eqs. (100) and 103 (vi) uses Eqs. 104
105
which imply
that क6 (Ex) "55" (Cx) sl.sells Ex ((Ex), (vii) uses Eq. (106). Taking unconditional
expectation of Eq. 117 and telescoping it over k 0, 1. ..... K 1 with 3 2 [0, 2
Th $ 1 t. we obtain that
K-1
Σ E
(Ex))
k=
<E
(E(KK
(Eo)] + Le
5K
5K
2 Lg,g + KLg (1+
E
4
BLgg
① - + 5K
5K
5K3E
Le
L
Le0
2
where (i) uses the following range of (() (defined in Eq. 105 that holds for any & E E.
(E)) S max 4(5')
max maxmin f(Aa,))
S
min max f(v..') = f
(108)
E'EE
Ee 6E8
0E8 E'E
(E) 2 (E)
(109)
As result,
E3 V (Ex)
8f
83 (Eo)]
+ 10L + 20Lg,500 + 2
KB
N.3
Convergence of the Inner Update Step (6)) of the Second Corrected Phase
Next we focus on the second corrected phase which aims to solve the following minimax optimization problem (repeat Eq. (T)).
min max [(0.5) = f()o.) Lg,ell - E.,
(110)
BED EEE
where { obtained from { uniformly at random in the first original phase. Based on
Proposition 3 it can be easily verified that ff has the following smoothness properties and f(0,-) -) is T.g.e- -stronly concave.
|VoJ(o', voJ(0, < To,00 - 01| + Too. - -1l- |Ve ,5') F0, e)Il - Lg - 0ll + 3Lg ElI+
(111)
(112)
Next, will see the convergence rate of the projected stochastic gradient ascent steps (16 to the following optimal variable, which is unique due to strong concavity of f(8
t == arg max f(Ok. E).
(113)
EEE
The optimization progress of each step of Eq. bounded as follows.
16 for l K,K 1, K K' can be
E [1EE,1141 - |0p
S [llER + a(g - 2Lg,e(En.t - E)) - [0
(4)
$ + cu) OE [[lER + a aVzF(0k. En,e) 11
+ (1 + o |E (a (gh5) 2 (Ex, E) (e(((
(68)
(1 + cb) [1[EH. 12 + 2a V &f f(e,, En.1) vef(On. ( Et)
39

---

+ + Ek,) (e
+ + " B |19 VeJ(Aon. 0k]
(1v)
S (1+ c+) g_ ga= + +9L
- + + (1++)) c ))
( 16
2
17 [|E. [ [.]
E
(114)
where (i) uses Eq. (16), S E and contraction property of projection, (ii) holds for any C2 >
whose value will be assigned later, (iii) uses (fJ( {2) = O and the definition of f in Eq. (10)..
(iv) uses Proposition the error term E.g defined in Eq. (96) as well as the 3l.g.-smoottin
and
1 Iterating Lg.ę -t..only concavity of f(Ok,)) -) (see Eq. (122). ). and (v) uses 9 and C 17' the unconditional expectation of Eq. (14) over t. 0, U......, T 0 = E [| 1 0%
1, we obtain that
E
I|
11
T
1x + 17(2F)))
16 T
34
E [kk,
-
D2
(115)
17
1
17
9
where the second < denotes D= sup&eeell 11s' - Ell the diameter of the compact set E.
N.4
Convergence Rate E[llG!" (0g 12]1
Since f(0,-) is strongly concave, it has unique maximizer (0) and the corresponding function value (0) defined follows.
(0) arg max F(B.g)
(116)
EEE
(0) max f(0,E),
(117)
EEE
Furthermore, since F(O,)) is Le.g-strongl concave and f has the smoothness properties [II and
(12). we can easily obtain that (*) is (Lg.o/ L...LLLgg.p-Lhhhii and V is := Lgg + Leg Lg,0/ Lg.5
smooth with the following gradient, following the proof of Lemma 4.3 in 31
(ū v. (0)) Vif(Ao,=(o))
(118)
Note that for any K. K K' 1, the projected stochastic gradient ascent step (17) satisfies
19
1/ (0x- - -bgi
6 proje (0x- -b9(") (0,- bg (0)
1
(0) 1 |0u+1 02 + b9 (0)
where uses 02 θ and the definition of projection and (ii) uses the stochastic gradient descent step 17 The above inequality implies that
(g (0) (0x+1 - 0x) <
1
11 0x112.
(119)
26
Then, we analyze the optimization progress of the potential function 117 along the projected stochastic gradient descent step as follows.
(0+0++1)
( E (()) (B (0t+1 0x) + 110tt1 0x11
v 110. (0)) and V Vif(Ao.E.()) denote gradients with respect only the first input argument 6.
40

---

(3) E (0k)) + 11 - 9k 0x+1 - 0x) + (obk (
(8)
T(0++1 - -Ok)
I
+ 2 10++1 0s|l2]
(186)
E (0+) - 11
(0,))1+++ 2= 11 0
I
3/1 10t01 0x
1
2L
2h
T.
+ 2 10s+11 0x]13]
(0x) + "110""" (9)
VoI(Annn >1(++/++/ Vol ( VIs(App.
2b T.) 10(00+1 - 0x11
E
La LllEx - (0w))
(0)(O)) +
B110++1 - 02xl1
L
4b
(0) < <O)( +
D
16 T
341
F
18 02101+11 0x11?,
(120)
L
L
17
9LL2
4b
where (i) uses the i = Lg, + L L L -mmoothnsss of V (ii) uses Eq. [188 (iii) uses Cauchy- Schwartz inequality and Eq. (19). (iv) uses = 4 Propositions 3 and the error term E²(") defined
by Eq. k = K
955 (v) uses Eq. 115 Denote G (02, {.)) = 0 proiel0x bV DV )}] for
K + K"
-1 1. Its norm can be bounded as follows.
E G (0k=EE))
B110+11 - 02 + 66 (0x, Ex) - -Okx+1 1x)l
2
3/2 El (0a-1 - 0
2
B1100+1 02 + bG, (0x, 1
1,2
(9)
E
Ellprojee (0z - bug( - proje (0. -V (\o
122
8
(0+) (( +
E
D2
16
T"
34L
8.6
+ T
L
L
17
9LL2 E.E
(00)
5 2E 9h
(0)
Vos(Mo
8
E
D&L2
16 T
3412
Fr(()
+ b
(Ba) - ((k+1)) +
E
+
U.5
L
17
9L.12
(188)
8E(0)
8D8 1.
16
T"
272 8.g F.(e)
< 2E
((T(O))
(0+++))] +
(121)
b
7l
17
9bLL E.E
where (i) uses Eqs.
17
and 1200 as well (0k,
{x) 1; [Ox proje 10+- - bVo (Ne I]].
(ii) uses Eq. (110 and (iii) uses Proposition 9 and the error term E defined by Eq. 995
By rearranging the above inequality and averaging it over l K, K 1, K K" 1, we obtain the convergence rate of E[]| [[ (0g+ [P as follows.
K'
BIIG (0g
E G (0x, Ez)
K
k=
8L(0) (0)
SDLL2 16 T" 2721 2 E((
<2E( +
8
E
(
((KK4k))
bī.
kk
bī.
17
9bT.122 E.
41

---

(1)
<34E4 +
32T.
-
32D (17)
16 r'
+
1088 E(()
B3
K'
17
9L
@ 34
(
32Σ
B
Ox0 +3222
(17)
166 T'
1088 E3 F(
K
9
(1))
32T.
16 T"
108812 E
S 34E4
(0)
[((k) 1*] + 32D
(122)
K'
17
9
where (i) uses Eqs. 116 117 and selects the stepsize b +t (ii) uses Eq. (10). and (iii) uses
f == mingge mäx f (Ao.e) and r(0) == maxee= (()
N.5
Convergence Rate of E|I|G! ( (0
Denote (E) == mingge f(0,E) = +({) Lg,ells El1
Then, on one hand,
vb (() - (Ex.)
@
max EEE
(5) (Ex))
= max min f(0, ()
min f(0, (x)
EEE BEB
$ max f(Ox: {) SEE
min f(),Ex)
( F(0x.
min f(0, Ex)
(00) S Ee) + 31g
||Ex Ex 8EB
min f(0, Ex),
(123)
2
where (i) uses Eq. (104). (ii) uses Eq. 113). (iii) uses V&J (t) 0 at the optimal variable Eg
defined by Eq. (113) and -.g.ee-mmottnnee -mooohhness of F(0,-) -) implied by Eq. (112 On the other hand, since
F(0,-) is Lt.o-ntyy concave, vi is Lg. concave. Hence,
LEg
(Ex)) s (3) V (3) (5) - -Ex]
1-t( (E)
|x|
2
2 (0)
Les || (5) -a.
(124)
where (i) uses [e (ε) = 0 at the unique optimizer (x) = arg max (E) (see Eq. (104).
Then, have
( (0x, Ex)ll
|roj + aV (Aoa.s))) - 1
a
① 2 [proj=(E< aV (Ok, {x)) Ex] - [proj= aVgF(0,. =]]l
a
2
+
(S: + VV (Vo. projz (EL + (0)
d²
4
projz(EE + fV.. (1) - projo (Et + a (0,. {i) || +
|15t 1a
a
a
2
+
proj + a VVf (E + aV F55( [1
a²
4 (Ex (VgF((k. (5t + aV (2)
4
a |15 1
+ 2 Vef(No. ve](0x, 12
8
V F( (x) F(b( |1 2 +
8
11
Ex
12
22
l1EE Exll + 2/12L (Ex 11
42

---

(188)
12
-
72L G.C
+
11Ex-EEN1 -Eil + 1 - E (E))11 + (ls5s(t) - -]
a²
(1m)
(22L2 5.c +
12
11Ex - - -326e. [(()x,E))+
3.E
||Ex - -in f(0, (x) +-4 ( BeB
a²
2
(
1200,
12
min [Ao + 4| (E)) ||Ex- - E2ll + -222e (ABr..)
(125)
nz)
OEB
where (i) uses (4t + V. vo5((0,, {t) - E 0 based on Eq. 113
(ii) uses the definition of
given by Eq. 110), (iii) uses 3Lg g -smoohhness of f(0x.-) based on Eq. (122) (iv) uses Eqs. (106).
123 and (24). (v) uses Eq. (10). Taking expectation the above Eq. 125 and averaging it over
K
K + K' I, we obtain the convergence rate of B|||G (0. k 5g ||]] as follows.
B B (0 (:)11)
K+K'-1
12
1201
+
Σ
ElcA EX1l + V
K'
a²
k=k
K+K'-1 Σ
32Lg,
+
E [A 0E0
min f(No.sx)]
K'
k=K
(4)
12
16 T"
34E(5)
120L2
+
D2 +
a²
17
9L
85
[ [((o)]
SE
+ 4
+ 10Lg BB + 20Lg + 20
KB
+ +32Lg,4 1 [V20=- (bL8,
+ +1) + blg E " [0.
(8)
12002 +
2-)
12
[(
16
T +
34E(5) (5)
32f" -32E (Eo)] +
40Lg,3302
17
9L
KB
+ 80Lg +80E 32L /22 (bLg, + 1) + b6e]
1088 (() 1/2
34 (0)
32L
K' [T(K))
14] +320
16 T'
8,5 33 8.5
(126)
17
9L665
where (i) uses Eqs.
20 101 and 115 (ii) uses Eq. 122
(iii) uses Lo Eg
O - 7)-
Lo.g, Lg.g, L = O[(1 7) 31 based on Proposition and selects stepsizes a = gT.e. O [))].
b AL = [ (1[1->))))
2LLAVK =OK 1/2 %1
N.6 Substituting Hyperparameters
2 Denote = min 6. h,, =
Then we select the following hyperpa-
rameter values.
K -36 [6 + 2002)² O[(1 - -7)-8
(127)
T log 14400L.5E
1
-B (B(()()))) - min 0EB,SE=
[(aeee] } = =0 -olog[[ -
10g -
(128)
30
(1 - 662
K' 294912T.I22
[[0k) - [+2 (La.8 + 1L) + Eo = O1(1 - 7) -
(129)
Ize4
T' -33 loog//54400 54ALE. DzLo, -2V2ex (L., + 010)((117))) -1)
(130)
1
a 2L0.0
(131)
3 2L
(132)
43

---

(133)
9
1
(134)
4I.
17280L no l3
m1
20,08c211 (1 -7)4
= =0[(1 - -10
(135)
17280L 5. 22 1.
m
(1)
100
0[(1 100-101111
(136)
L0,08E²( (1 -1- 7)
17280L 5 [ = log (1 - 7) E
(1
log
(137)
2 loog(
L0,00e2(1 - 7)a
1 1
4
1- ) + log(>-1)
2
51840LE, f2 no
L10,0c²(11 7) =0 flgg( (1 - -7)- -2
log
log
(138)
1 .
1 1-9 7
14851222
O[11 - 7) -6-6,
(139)
(1 77)
14851213
82 |S||A| O[(1 -7)
m
(2)
A
(140)
e0 7)
H (2)
1
0
log[(1 - -
(141)
2 log((~1))
c²(1 7)
1-7 7
4
2
2970026 pp
= = log[(1 - --)---=-
H
log
+
log(7-1 log
(142)
1-7
7-7
c²(1 -7)-
1 1-7
133693141
12 & PC
(2122x= (Lo.0 + +44) + tol
m
(3)
= O((1 7)0 1000 -
(143)
(126111 - -7)1
1336934413
6.2 1 |||[ 122x-1 [ (1..0 + 4T.) + [0]
5 P2
= 0 - 100
(144)
[2e4(1-1)
1336934412 e 13,1811A1 [V26,- -1 (Lo,0 4I) Eo] ]
H (3)
2 log()-1)
T2 -7)1
-0 log( (1 -
(145)
1 1- ?
267386881 12 P2 (212222 (Lo.0 4ï) + fol?
H (3)
4
log 1 1-71
2
+
log
p.
1
log(7-1)
[2e4 7)
=0 logi (1 7) -1--
(146)
1- 7
3760128L2 (1V2l==:(Lo. + +4L) Lo]
mg
(4)
c.5 ao (
0111-))-10--1
(147)
(1c4(1-9))
3760128L2 e 13 A1llLAAl/eee--1 (L0.0 Aï) tol? =01(1 - -20 -
mx
(4)
E.6
(148)
T. -7)²
((1))
1
37601281.2 c. E
12 1318][A1[ + +TT) + fo]
2 1og(>~1)
-0 logi(1 -E
(149)
1-7 ?
752025612 12 12(2222-1 (L + 4ī) + fo)2
H1(4)
4 log
1 (1- 2 )
+
log
5.5
1 1-2
log(>-1)
T.2 -7)²
44

---

-0 logi(1 ( - --
(150)
-
Substituting the above hyperparameter choices into Eqs.
(95)
and (96) we have
3 E
To
LAIS|1A1
1 + +)208))
&
+ Ell + H (0-(111100 2
(1 7)
m
m
Lg,0dE²
(151)
1440Lg,
363
LA1S|AA1
+ y 2
+ +11 + H (1 (1-))
+
7)
(2)
m
m
E2
(152)
12376'
362
2
E3
PE
|
+ +
+ + (1-)))
(1 7)
(3)
(3)
m.
mg
i.2d
(153)
111411213 [220> (Lo,0 4I) Co]
9,6
362 (1 7)a [L3SS1AA1 (4)
(0
+ +,201%
+ 21 + (1-2))]
m
mag
T.21
(154)
31334412 (V2_[[2222__222 (To,0 + 4T. + 66)2
E.3
where we used [1 + HTaa) (1 7)] (1 2 for 1²xh) - log (1--) (k = 1,2,3,4) 4).
Lemma 7 Dimplies that for any fixed & E E, 0r obtained from the update rule (4 satisfies
E [(S()o
min [(vo,)] 6E0
(1) 5(1 T)TEE.FFFF [[
min f(No,s.) + 4Lo.ol3-18 F.(0) BE8
6Lg.0
(1)
< E
(((b))
f()..)) exp loggl 8) log 1440Lg,5 ( DEA,EE=
min
min oE0,se=
f(eee) }
+
+ 1440
1440Le.e
(117
2
480LE.
where (i) uses Lemma 7 (ii) uses Eqs. 128 151 and 8 La, (iii) uses log(1 - 8) <
-8 for E [0, 1/2]. Hence, the above inequality implies that en defined by Lemma g satisfies
S 480Le.5
As result, we can prove that E [[[
(0g. [3] è² and " (0p. [p]l < c by substituting
< 4801...5 and Eqs. 127 154)
into the convergence rates 122 and 126 The number of
samples required by Algorithm iis
KT(m (1) (t) + mg (1) () + K (mm) (2) (1(2) + m m2 (2 (2
+ 'K'T (m) (3) H (3) + m 33) H ( + K' K'(m) (4) (((1) m
(4) (4) H1())
log - -16
log (1 -
=0 - 8 100
O マ) 10 10 - 110
(1 (1-1) 61-2)662
1 1 7
45

---

+0 - -0 log - -7) -
1-7
log - -
+0[(1- "0000)))0000000000-~~~7"""7 -0001--)--0-
1-7
- + +0[(1-7) -1 logl(1 - -
1 -
log" [1 7)
(1 - 7) 26
O Proof of Theorem? 3
Note that oF 23xl0, by the definition of E == {e V(E) f(Xer.) 2 max 1((onn))) - (0) we have
1(No..) < max [(Now.))) 28kEa, Ag ((E)/E ('EV(E)
(155)
Hence,
max ((66x.))) 100---(peep ((0e1111)) max f()er.e)) - -(Nov.)) - 260 -26e|10z41 OKl E'E
E'
(1)) > 23 2loBx =0, AA E V(E)/Ex
(156)
where uses Eq. 10 Proposition which implies that s(A.s) ln-Lisschitz continuous, (ii) uses Eq. (155) and the update rule (22 with [|dx 1. Eqs. 155) and (156) respectively imply the
following two equations.
r(0x) max f()oL.))) 2 f ((oo. E'E=
(157)
r(0x+1) = max ((NNNI))) (Noniieee E'ESL
(158)
where fi+1 E arg max ()
Based on Proposition
7 there exists a unit descent direction de (1|ōa] || = 1) such that
0 f<f())o.s)) min T(0') ((or))))))))))) s(20- x) V2l Vo vos()o.s)) ddke) VG Ex (159)
l'Ee
Then we have
I(0x) min r(0')
(8)
max f()or.)) - min I(0")
8' 6'
(EEVEE)
#'6
min f()BL.)
min T(0') + 23 Fee
geEk
(82)
< min
[ V22 Vef T [z) 23
EE
=[ - 22 A (dx)) + 2,3g0
(1v)
$ [V22x-1 -1 |ex - A& (dk))] + 2,3x
(160)
where (i) uses Proposition 6 (ii) uses 3₁ == {E E v( =(NoLe) 2 maxeev(s) f()e..
2, (iii) uses Eq. 159 (iv) uses A (dx) > minden, Ax(d) 2 As(d') - ea based on line of
Algorithm 2
46

---

0.1 Analyze the k-th Iteration
(Case 1): If Ag(d)) 2 0, then Eq. 166 implies that
T(0x)
min r(0') S v2 lep + 28r60. 0'EB
(161)
Hence, by Li-Lipsshitz continuity of (()) max (A.gg) (based Proposition 3), we have
r(0x+1) min r(0)= - [(t)) min r(0') + Eg 0k+1 0xll V2l 3 (162) ('Ee
d'
where (i) uses Eq. 161 and the update rule (155) with |dxl| = 1.
(Case 2): If Ag (d') < 0, then since ||d%,| I d2 /1/111//1l satisfies Ax(dk) S Ax(d)) <
Hence, Eq. (660) implies that
[(Ox)
min r(0') S 12l Ax(da)] + 28x60- Pe
(163)
As a result, we bound the one-step optimization progress of I(0x) as follows.
r(0x+1) - -((x)) 2 ((oomii (10e
Tg,00
Vof(Aou.si (6x++1 - 0xx) +
110-11 - 0xll
2
(01)
Be Vo Eh.11 Td + L0.0
32
(10) 3 (dx) +
L0.0 o
(0)
Lo,0Bk
v2,3,00
BE
S Bk ck +
+
[T(+))
min I(8'), l'
2
Ex-1
V2lx-1
where (i) uses Eqs. 117 and 1588 ). (ii) uses Lg -smoothessssss of f(x..s) based on Proposition
uses the update rule (22)
with | = (iv) uses Ex+1 E and the definition of Ag in Eq. 23
(v) uses Eq. (13).. Rearranging the above inequality yields that
I(0x+1)
min r(0') #'e
3k
Lo,03x
V23al0
[(0x)
min 1((0'] + B/
Ek
28
d'EB
2
ex-1
(
k
r(0)] + 2 2v
86
Lo.
V20
T(0s)
min B'
+
(164)
k + 2
k 2
(k + 2)²
2
Ex
2V26 k+2
where uses Ba
O.2 Obtain the Convergence Rate 25
(Case 1): If A& (dz)
< 0 for all k = 0, O.1.... K
1, then we iterate Eq.
164 over k
0,1, K- 1 as follows.
r(Ox)
min I(0') 6'ee
K
k(k + 1)
12V20
822
La.
V2lg
K(K 1)
k+1
(k 1)2
2
lx-1
k=0
2/22,
48x
Σ (KEx) +
Lo,0 2/22o)
K(K + 1)
K +
42x-1
< 2V22x-1
Ck ISkSK
(Ex-1 Lo.0 2vol))
(165)
K K+1
47

---

(Case 2): If Ak-1(dx-1) 2 0, then Eq. (62 holds for k = K - 1, i,,
r(0k) min r(0) - 12 cK + 33k-140- S -2e 6v 0'
(166)
+
(Case 3): If (dx 2 0 for some K" E {l, K 1} while (x(d)) < 0 for all
K" ...., K 1, then we iterate Eq. (I64) over k K' ...., K follows.
T(0k)
min I(0') 0'E0
K
kik + 1)
-2/20x ICk
862 (k+1) 1)2
L8.9
V200
Σ
+
K(K +1)
k+1
2
x--1
k= K
+ K'KK' + 1) [[(xx))
min I(00)] O'EB
K(K + 1]
2 2/26x-1
E (KEA) + 1 -K")
(Bs 2L0,0 + 2V/(o)
K(K 1)
K(K +1)
k=K++1
+ K'KK' + +1)
(V2l2-1Ck + +28k:E0)
K(K +1)
18) 2/
K
(kOr) + 48x 462-1(K - -K') K(K +1)
Σ
(ex 2L.00 + 2V
K(K + 1)
k=K'+1
K'(K' +1)
(V2ex-IER +
4V22glx-1)
+
K(K+ +1)
K' +2
48x-1 (ex-1 1.0.0 2V/20))
S SV
max K+IskkKK
6k +
(167)
K ++1
where (i) applies Eq. (662) to k K' and (ii) uses B, 2v21 -1
k+2
In sum, the convergence rate (25 holds in all the above three cases.
P Proof of Corollary 1
Note that Ae(d)= == maNgez, VoJ T defined by Eq. 23 is convex and Lg-Lisschitz con-
tinuous. Hence, the best direction da E arg max da, o0S A&(d)
obtained from the subgradient
method (28) converge at the following rate 11
(0) d 2
dil 1| + PTT (2)
4+4
(d(d)) min (xd) dEBi
2Ta
246x-16-1
36x-1*
361² - O111 - - a
where (i) denotes di E arg max (d). (ii) uses T
3--11f and ||da.ol|, l|dill I 1. Hence, the accuracy c
is achieved in Algorithm
31, 1
Substituting E 32 K 86 (lx Lg.0 + 2/2(o) = 01(1 7) -a--') - into the convergence
rate 25 we obtain that
46x-1
r(Ok) min r(0') <V max cK + IgkS
K + (1x-1 Lo.0 + 2V22)) Se.
d'Ee
The above e accuracy above requires K[V -1 s(Ao..) and ()o,s),,)) KT O - - subgradient updates (28) and K = O(1
evaluations to A0
- -)-8E- gradient descent updates to the policy gradient descent updates (22
48

---

NeurIPS Paper Checklist
1. Claims
Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Question:
Answer: [Yes]
Justification: In the abstract and introduction, we have accurately reflect our contributions, namely, proposed new learning framework (robust RL with general utility), and proposed algorithms as well as their convergence results for convex utilities, concave utilities and other utilities that satisfy weak Minty variational inequality.
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 the paper and important assumptions and limitations. A No or NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize to other settings.
It is fine to include aspirational goals as motivation as long as is clear that these goals attained by the paper.
2. Limitations
Question:
Does the paper discuss the limitations the work performed by the authors?
Answer: [Yes]
Justification:
We mention the limitations in the conclusion section.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend 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 or images are taken in low lighting. Or speech-to-text system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't 't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full of assumptions and complete (and correct) proof?
49

---

Answer: [Yes]
Justification: All our lemmas, propositions and theorems contain assumptions (if there are) and the corresponding proofs shown in the appendix.
Guidelines:
The answer NA means that the paper does not include theoretical results. All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated or referenced in the statement of any theorems.
The proof' can either appear in the main paper or the supplemental material, but if they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversell, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix or supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental Result Reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: In the experiment section, have provided all details needed reproduce our experiments, including the problem setup (c.g. utilization function, transition kernel parameterization, policy parameterization, ambiguity set, discount factor), the algorithms we implemented (as shown in our algorithm boxes) and the hyperparameter choices.
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 to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g.. in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS 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 to reproduce that algorithm.
(b) the contribution is primarily new model architecture, the paper should describe the architecture clearly and fully.
(c) the contribution is a new model (e.g., a large language model), then there should either be way access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. In the case of closed-source models, it may be that access to the model is limited in some way (c.g., to registered users), but it should be possible for other researchers to have some path to reproducing verifying the results.
50

---

5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
We have uploaded code which generates the simulation data for experiments.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please the NeurlPS code and data submission guidelines (https: cc/
public/ Codeddddee/ddddSuuittt ss ssoooooiiry for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurlPS code and data submission guidelines (https
/ httppps.cccppllcpppppppppppp idg...ee...... CodeS Summi ss i onPoliccy for more details.
The authors should provide instructions on data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones 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
Does the paper specify all the training and test details (c.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Question:
Answer: [Yes]
Justification:
We have shown the experimental settings Appendix
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 a level of detail that is necessary 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: [No]
Justification:
We report one time implementation of each algorithm.
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, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall with given experimental conditions).
51

---

The method for calculating the error bars should be explained (closed form formula, call a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
It is OK to report 1-sigma error bars, but one should state it. The authors should 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 figures symmetric error bars that would yield results that are out of range (e.g. negative rates).
show in tables or
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 puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We have shown the hardware and computing resource in Appendix A
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary failed experiments that didn't It 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 http://ppreeeeeie..////////ttaat
Answer: [Yes]
Justification:
We do not see any ethics violation of our theoretical study.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g., if there is special consid- cration due to laws or regulations their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [NA]
Justification: We not see any societal impact of our foundational theoretical study since is not tied to particular applications, let alone deployments.
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 societal impact why the paper does not address societal impact.
52

---

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

---

If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, [paperswi has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
datasets
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 encouraged to reach out the asset's s creators.
13. New Assets
Question: Are assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [Yes]
Justification: We have uploaded anonymized zip file containing code and readme file on how to use the code.
Guidelines:
The answer NA means that the paper does not release assets.
Researchers should communicate the details of the dataset/code/mooel part of 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 is used.
At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsoureing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
This work does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then much detail as possible should be included the main paper.
According to the NeurlPS Code of Ethics, workers involved in data collection, curation, 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 an equivalent approval/review based on the requirements of your country or institution) were obtained?
Answer: [NA]
Justification:
This work 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.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
54

---

We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
55


Reviews:
[{"review_id": "9qg4mTxpLr", "reviewer": "Reviewer_iNNQ", "summary": "The paper studies the problem of robust RL with general utility function, which is looking at maximizing a general (possibly non-convex) utility function with the worst-case possible transition kernels in an ambiguity set. The paper provides convergence analysis for a wide range of utility functions and ambiguity set.", "questions": "1. I think the authors might do a better job motivating and introducing the problem at the introduciton section. I'm confused about the exact definition of robust RL with general utility until the end of section 2. Is it possible to provide intuitive explanations at the beginning? \n\n2. it might be easier to understand the 4 different settings if the authors can motivate with good examples in practice (convex utility, concave utility, polyhedral ambiguity set and weak Minty variational inequality).\n\n3. There have been a lot of assumptions in the paper before the convergence results. Can authors comment on how practical those assumptions are? And under such assumptions, can the authors comment on the tightness of the results in terms of sample complexity / iteration complexity?", "limitations": "N/A", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "The technical contribution mainly comes from the following convergence analysis:\n\n1. With convex utility, a two-phase projected stochastic gradient descent ascent algorithm is shown to converge to stationary point.\n2. WIth convex utility and an s-rectangular polyhedral ambiguity set, global convergence is proven.\n3. The gradient convergence is also proven for concave utility and utility that satisfies weak Minty variational inequality.", "weaknesses": "My main concern is about the motivation, interpretation of the results, along with potential tightness results. Please see question section.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We will revise the manuscript accordingly after the review discussion period. Please let us know if further clarifications are needed.\n\n**Q1:** I think the authors might do a better job motivating and introducing the problem at the introduction section. I'm confused about the exact definition of robust RL with general utility until the end of section 2. Is it possible to provide intuitive explanations at the beginning? \n\n**A:** Thank you for your suggestion. In the **revised introduction**, we will briefly compare the definitions of the existing *RL with general utility problem* and our proposed *robust RL with general utility problem*. Specifically, the existing *RL with general utility problem* is formulated as $\\min_{\\theta} f(\\lambda_{\\theta,\\xi_0})$ where the agent aims to select its policy parameter $\\theta$ to minimize the cost-related utility function $f$, under a **fixed transition kernel parameter** $\\xi_0$. In contrast, *our robust RL with general utility problem* is formulated as $\\min_{\\theta} \\max_{\\xi\\in\\Xi}f(\\lambda_{\\theta,\\xi})$ where the agent aims to select a robust optimal policy $\\theta$ that minimizes the utility **under the worst possible transition kernel parameters** $\\xi\\in\\Xi$. We will refer the readers to Section 2 for more details. To motivate our research, we will also briefly summarize the useful special cases and application examples of our proposed problem listed in our global response. \n\n**Q2:** It might be easier to understand the 4 different settings if the authors can motivate with good examples in practice (convex utility, concave utility, polyhedral ambiguity set and weak Minty variational inequality). \n\n**A:** Thank you for your suggestion.  \n\nBased on all the reviewers' feedback, we will remove concave utility and other utilities that satisfy weak Minty variational inequality, since they lack application examples. \n\nWe have listed two popular examples of polyhedral ambiguity set, $L_1$ and $L_{\\infty}$ ambiguity sets in lines 48-49 in the introduction, and defined these sets right after Assumption 7. To have stronger motivation, we will also add the explanation that these ambiguity sets are popular in robust reinforcement learning, an important special case of our proposed robust RL with general utility. \n\nWe will add the following examples of convex utilities [1] to our revised paper. \n\n(1) MDP with Constraints or Barriers, which has safety-critical applications including healthcare [2], autonomous driving [3] and unmanned aerial vehicle [4]. \n\n(2) Pure exploration, which can be applied to explore an environment that lacks reward signals [5]. \n\n(3) Learning to mimic a demonstration, which is used to help the agent mimic the expert demonstration [1].", "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": "Ah3NUhjyUl", "reviewer": "Reviewer_joNT", "summary": "This paper aims to incorporate robustness in reinforcement learning environments by allowing the transition kernel to be within a polyhedral s-rectangular uncertainty set to handle general utility functions. It applies a stochastic gradient descent with (gradient sampling subroutines) algorithm designed for global convergence and presents numerical experiments to showcase its convergence properties.", "questions": "- Comparison with Barakat et al. 2023: It would be helpful if the authors could provide a more detailed comparative analysis of their approach with the work by Barakat et al., especially in terms of algorithmic differences and performance in continuous state-action spaces.\n- $\\ell_{\\lambda^{-1}}$: please provide an explicit example of this constant and its dependence on |S| and |A|\n- Line 230: Inversible -> Invertible", "limitations": "The authors touched upon the limitations of theoretical complexity", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The methodology behind robustifying the transition kernel is well thought out. The theory is supported by proofs that are generally clear to follow. The convergence behavior is validated by numerical simulations.", "weaknesses": "- Modeling motivation: The paper lacks a comparative analysis to demonstrate superiority over existing non-robust methods in handling scenarios like constrained and risk-averse RL. To solidify its contributions, it should include empirical or theoretical evidence comparing its performance against established methods, especially in real-world scenarios that involve distributional shifts.\n\n- Computational costs. Detailed evaluations of the computational overhead comparing to non-robust approaches needs to be presented to demonstrate the price of robustness and usefulness of the modeling.\n\n- Scalability. The robustness in transition kernels is modeled through s-rectangular uncertainty with direct parametrization of the transition kernels, which appears to be less advantageous for scalability and generalization in complex or continuous environments. The paper should discuss potential adaptations or extensions of the method that can handle larger state spaces without compromising theoretical integrity.\n\n- Hyperparameters. The algorithm requires managing an extensive set of hyperparameters, complicating its practical implementation. The paper should propose methods to reduce hyperparameter complexity, such as adaptive tuning or simplified parameter settings, to enhance usability and accessibility.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We will revise the manuscript accordingly after the review discussion period. Please let us know if further clarifications are needed.\n\n**Q1:** Modeling motivation: The paper lacks a comparative analysis to demonstrate superiority over existing non-robust methods in handling scenarios like constrained and risk-averse RL. To solidify its contributions, it should include empirical or theoretical evidence comparing its performance against established methods, especially in real-world scenarios that involve distributional shifts. \n\n**A:** Thank you for your suggestion. Our work is fundamentally different from the works on *non-robust* RL with general utility, not only in methodology, but also in the objective function and convergence measures. Specifically, *non-robust* RL with general utility aims to solve $\\min_{\\theta\\in\\Theta}f(\\lambda_{\\theta,\\xi_0})$ under a fixed environment $\\xi_0\\in\\Xi$, while our proposed *robust* RL with general utility aims to solve $\\min_{\\theta\\in\\Theta}\\max_{\\xi\\in\\Xi}f(\\lambda_{\\theta,\\xi})$ under the worst possible test environment $\\xi\\in\\Xi$. As a result, our convergence measures are also very different, so the performance is not directly comparable. We will stress these fundamental differences in our revised paper. \n\n**Q2:** Computational costs. Detailed evaluations of the computational overhead comparing to non-robust approaches needs to be presented to demonstrate the price of robustness and usefulness of the modeling.\n\n**A:** Thank you for your suggestion. As mentioned in our answer to Q1, the computational overhead is not directly comparable, since the non-robust approaches and our robust approaches have different objectives and different convergence measures. \n\n**Q3:** Scalability. The robustness in transition kernels is modeled through s-rectangular uncertainty with direct parameterization of the transition kernels, which appears to be less advantageous for scalability and generalization in complex or continuous environments. The paper should discuss potential adaptations or extensions of the method that can handle larger state spaces without compromising theoretical integrity.\n\n**A:** Thank you for your suggestion. To extend to large state spaces, we can adopt linear occupancy measure $\\lambda_H^{\\pi_{\\theta}}(s,a)\\approx \\omega_{\\theta}\\cdot\\phi(s,a)$ (Barakat et al. 2023) and linear transition kernel parameterization $p_{\\xi}(s'|s,a)=\\xi\\cdot\\phi_{s,a,s'}$ [1,2], with parameters $\\omega_{\\theta}$ and $\\xi$ of scalable dimensionality. To extend to Robust RL with continuous state space, we can adopt Gaussian policy (Barakat et al. 2023) and transition kernel $s_{t+1}=f(s_t,a_t)+\\omega_t$ with Gaussian noise $\\omega_t\\in\\mathbb{R}^d$ [3]. We will add these potential extensions to our conclusion section. \n\n[1] Ayoub, Alex, et al. \"Model-based reinforcement learning with value-targeted regression.\" International Conference on Machine Learning. PMLR, 2020.\n\n[2] Zhang, Junkai, Weitong Zhang, and Quanquan Gu. \"Optimal horizon-free reward-free exploration for linear mixture mdps.\" International Conference on Machine Learning. PMLR, 2023.\n\n[3] Ramesh, Shyam Sundhar, et al. \"Distributionally robust model-based reinforcement learning with large state spaces.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2024. \n\n**Q4:** Hyperparameters. The algorithm requires managing an extensive set of hyperparameters, complicating its practical implementation. The paper should propose methods to reduce the complexity of hyperparameters, such as adaptive tuning or simplified parameter settings, to improve usability and accessibility.\n\n**A:** Thank you for your suggestion. Based on Theorem 2, we can reduce the hyperparameters in Algorithm 1 by replacing $m_{\\lambda}^{(1)}, m_{\\theta}^{(1)}, m_{\\lambda}^{(3)}, m_{\\theta}^{(3)}, m_{\\lambda}^{(4)}, m_{\\theta}^{(4)}$ with $m^{(1)}$, replacing $m_{\\lambda}^{(2)}, m_{\\theta}^{(2)}$ with $m^{(2)}$, and replacing $\\{H_{\\lambda}^{(k)},H_{\\theta}^{(k)}\\}_{k=1}^4$ with $H$. Based on Theorem 3 and Corollary 1, we can reduce the hyperparameters in Algorithm 2 by replacing $\\sigma_k$, $\\epsilon_k$ and $\\beta_k$ with $\\frac{\\sigma}{k+2}$, $\\epsilon$ and $\\frac{\\beta}{k+2}$ respectively. \n\n**Q5:** Comparison with Barakat et al. 2023: It would be helpful if the authors could provide a more detailed comparative analysis of their approach with the work by Barakat et al., especially in terms of algorithmic differences and performance in continuous state-action spaces.\n\n**A:** Thank you for your suggestion. As mentioned in our answer to Q1, the most fundamental difference between our work and (Barakat et al. 2023) is that we aim at different objectives and convergence measures. As a result, the biggest difference in algorithms is that (Barakat et al. 2023) only updates policy parameter $\\theta$ under fixed transition kernel parameter $\\xi_0\\in\\Xi$ while we update both $\\theta$ and $\\xi\\in\\Xi$. The performance is not directly comparable also due to the differences in objectives and convergence measures. \n\n**Q6:** $\\ell_{\\lambda^{-1}}$: please provide an explicit example of this constant and its dependence on |S| and |A|. \n\n**A:** Thank you for your suggestion. It has been proved in [4] that for direct policy parameterization $\\pi_{\\theta}(a|s)=\\theta_{s,a}$, $\\ell_{\\lambda^{-1}}=\\frac{2}{\\min_s\\rho(s)}\\ge \\frac{2}{|S|}$ where $\\rho$ is the initial state distribution. \n\n[4] Zhang, Junyu, et al. \"Variational policy gradient method for reinforcement learning with general utilities.\" Advances in Neural Information Processing Systems 33 (2020): 4572-4583. \n\n**Q7:** Line 230: Inversible -> Invertible. \n\n**A:** Thank you for pointing out this typo. We will correct that.", "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": "jjJZr87Ud6", "reviewer": "Reviewer_nGSn", "summary": "In this submission, the authors tackle a new problem: how to train a policy with a general utility when one needs to be robust to some uncertainty in the environment. More precisely, they are looking for the solution of min-max problem: the minimization over a set of parametric policies of the worst case over a set of possible transition probabilities of a (convex) functional of the occupancy measure. They propose a policy gradient type algorithm for which they prove that the gradient goes to 0. They also introduce a more complex algorithm for a specific classical uncertainty set (s-regular polyhedral ambiguity set) that is provably convergent toward the global optimal solution.", "questions": "Can the author explain if the control on the size of the gradient with respect to \\xi corresponds to a convergence for the functional itself or just that the algorithm is going to slow down?\n\n\nTypos and misc:\n- 134: $\\quad$ before $,$\n- 309: $\\epsilon_k$ only defined in Algorithm", "limitations": "The complexity of their algorithms is quite high, as it is mentioned, and the convergences are local or in a specific setting, but this makes sense for a first paper in a topic.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 4, "strengths": "- The authors attack a novel problem (the combination of general utility and robustness) for which they construct algorithms with theoretical guarantees.\n\n- The content is very technical, but the writing makes it understandable. I really liked the way the authors stress their specific contribution.\n\n- The proof seem correct, although I did not check all of them extensively.\n\n- The results are supported by some numerical experiments).", "weaknesses": "- The nonconvex case is only handled in the Appendix. I liked the fact that they have much more in their pocket than the content of the main article. The nonconvex case could nevertheless have been mentioned only in the conclusion as it is not really part of the main article.\n\n- The numerical experiments should be part of the main article as they add a lot to the theoretical results.\n\n- The results are very technical and some explanations (for example for the main theorems) could be beneficial to the readers.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We will revise the manuscript accordingly after the review discussion period. Please let us know if further clarifications are needed.\n\n**Q1:** The nonconvex case is only handled in the Appendix. I liked the fact that they have much more in their pocket than the content of the main article. The nonconvex case could nevertheless have been mentioned only in the conclusion as it is not really part of the main article. \n\n**A:** Thank you for your suggestion and appreciation. Based on all the reviewers' feedback, we will remove concave utility and other utilities that satisfy weak Minty variational inequality, since they lack application examples. \n\n**Q2:** The numerical experiments should be part of the main article as they add a lot to the theoretical results. \n\n**A:** Thank you for your suggestion and appreciation. We originally planned to put numerical experiments in the main article. Later, we found that after fitting some other necessary parts into the main article, including problem formulation, algorithms and theoretical results for both gradient and global convergence, the 9-page limit did not allow experiments. Therefore, in line 194 in the main article, we refer the experiments to Appendix A. \n\n**Q3:** The results are very technical and some explanations (for example for the main theorems) could be beneficial to the readers. \n\n**A:** Thank you for your suggestion. \n\nTheorem 2 provides the first sample complexity result to achieve $\\epsilon$-stationtary point of the objective function $f(\\lambda_{\\theta,\\xi})$ for robust RL with general utility. Specifically, we select sufficiently large batchsizes and truncation numbers to ensure that the stochastic gradients are close to the true gradients, and select sufficiently many iterations to ensure optimization progress. These theoretical and conservatively large hyperparameter choices are not necessarily needed in practical implementation. \n\nTheorem 3 provides the first global convergence rate for robust RL with general utility. The global convergence error consists of sublinear convergence rate $\\mathcal{O}(1/K)$ with $K$ iterations, and $\\max_{1\\le k\\le K}\\epsilon_k$ which denotes the convergence error of the subroutine for maximizing the concave function $A_k$. \n\n**Q4:** Can the author explain if the control on the size of the gradient with respect to $\\xi$ corresponds to a convergence for the functional itself or just that the algorithm is going to slow down? \n\n**A:** Good question. We select sufficiently large batchsizes and truncation numbers to ensure that the estimated stochastic gradients are close to the true gradients $\\nabla_{\\theta} f(\\lambda_{\\theta,\\xi})$ and $\\nabla_{\\xi} f(\\lambda_{\\theta,\\xi})$.   \n\n**Q5:** \"134: \\quad before ,\"\n\n**A:** Thank you for pointing this out. We will add spaces before the commas. \n\n**Q6:** 309: $\\epsilon_k$ only defined in Algorithm. \n\n**A:** Thank you for pointing this out. We will modify line 309 to \"with $\\beta_k=\\frac{2\\sqrt{2}\\ell_{\\lambda}}{k+2}$, $\\sigma_k=\\frac{4\\sqrt{2}\\ell_{\\theta}\\ell_{\\lambda}}{k+2}$ and any $\\epsilon_k>0$\", since the convergence rate (20) holds for any $\\epsilon_k>0$.", "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": "TPVMRystJN", "reviewer": "Reviewer_7fYr", "summary": "The authors combine the topics of robust RL with general non-linear utility. They use policy gradient formulae from general utility RL and combine those with gradient algorithms for minimax problems due to Lin et al. The authors claim to have a convergence theory for the sample based algorithm that ensures convergence to a stationary point (convergence of gradient).", "questions": "- It might be interesting to think about unbiased gradient estimators for general utility RL. Such have been found in the past years for linear RL, I guess something similar works in the non-linear case. \n- Assumption 1, assumption for p. That assumption is somewhat crucial. I do not have a feeling, there is no discussion, if (or not) that assumption is strong. In what situation is the assumption satisfied? Is there any interesting situation in which the assumption is satisfied?\n- Assumption 4 looks brutal to me. Is there any way to verify that assumption? Is there any example for which it can be verified? Perhaps that was addressed in past work, but some discussion is needed.\n- The example: If I am not wrong the choices of parameters do not fit to the theory. Do they? If not, that should at least be discussed. How about the assumptions, can they be checked in that example? If not, I fear the article might prove something on the empty set.", "limitations": "As mentioned above I cannot confirm that I agree with the theoretical results. The statement of Theorem 2 seems incorrect and the proofs continue in the same fashion. Since the article is of only theoretical nature I do not think it can be published in the current form at the top conference. \n\nNonetheless, I believe the research direction is very reasonable and the authors have made very important and very non-trivial research progress! In my view the article needs a full major revision which is not in the scope of a conference revision.", "rating": 7, "confidence": 2, "soundness": 1, "presentation": 1, "contribution": 2, "strengths": "The topic is interesting and it is very reasonable to combine the different setups in the way the authors propose. The algorithm is clever, the results look (mostly) reasonable, a very extensive theoretical study is carried out.", "weaknesses": "It seems to me the authors did not understand the Landau O notation, at least the way it is used does not make much sense. The O notation is only reasonable (and only defined for) in a limiting sense where typically one limiting variable is chosen. For a fixed number there is no sense in the O notation, it could allow to multiply that number by any real which of course is non-sense! Looking at Theorem 2 the problem becomes visible. The statement as is does not make sense: The accuracy $\\epsilon$ is fixed. Then a number of parameters of the algorithm are fixed as K=O(...), T=O(...), K'=O(...). What does that mean, O in what variable? Please compare with your Corollary 1, that statement makes sense. I went into the proofs to see if this is only imprecisely formulated, but it got even worse. The proof is full of estimates of the type $A\\leq O(...)$ for a number $A$ and, even worse, $O(...)\\leq A$. What is that supposed to be? The proofs are way too long (and this is not the referee's job) to check if the proofs can be saved or if there are O-constants that build up and spoil the proof. I am not too skeptical, the theorems looks somewhat reasonable. On the other hand a lot can happen if all constants are swept under the carpet, I cannot confirm correctness of the results. The analysis should be completely reworked and might make the article interesting for the next top tier conference.\n\nHere are some further points:\n- There is no clear motivation given for the article. As a Mathematician I agree the question is interesting, for a leading ML conference there should be some clearer motivation. The example is extremely artificial and not convincing at all.\n- It is not particularly pleasant to read the article. I believe there are way too many repetitive (and imprecise) citations. One clear citation for the general utility policy gradient theorem should be enough, most citations given do not include such a variant. To me the article is too technical, a little bit of story telling would be very much appreciated. Perhaps the authors might want to think of splitting the article in two.\n- There should be examples for the assumptions. For instance, what standard class of policies satisfy the policy assumptions? This is certainly standard for PG methods but almost all articles discuss some examples (softmax, linear softmax, ...).\n- The complexity \"result\" of Theorem 2 is pretty extreme. For the usual $\\gamma=0.99$ and $\\epsilon=0.01$ the powers make it essentially infinite. I do not criticise the result, that's what the Maths gives. Still, the authors should point out that this is a theoretical estimate with no practical implication. Similarly, the theoretical iteration numbers and batch sizes are ridiculously large. This is a theoretical worst case estimate (perfectly fine with me) but it should be mentioned that in practice those numbers would not be used. If I am not wrong those numbers are not used in their own simulation example (which should also be mentioned).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for reviewing our manuscript and providing valuable feedback. Below is a response to the review questions/comments. We will revise the manuscript accordingly after the review discussion period. Please let us know if further clarifications are needed.\n\n**Q1:** The weakness in the O notation requires reworking the long proof. \n\n**A:** Thank you for your suggestion. Similar to theoretical results in [1,2], our Theorem 2 uses the $\\mathcal{O}$ notation to stress the dependence on the large positive constants like $(1-\\gamma)^{-1}$ and $\\epsilon^{-1}$. For example, $\\mathcal{O}[(1-\\gamma)^{-8}\\epsilon^{-4}]$ is defined as $C(1-\\gamma)^{-8}\\epsilon^{-4}$ where the constant $C$ **does not depend on** $\\gamma$ and $\\epsilon$. This definition fits the following limiting sense.\n$$\n    \\frac{\\mathcal{O}[(1-\\gamma)^{-8}\\epsilon^{-4}]}{(1-\\gamma)^{-8}\\epsilon^{-4}}=\\frac{C(1-\\gamma)^{-8}\\epsilon^{-4}}{(1-\\gamma)^{-8}\\epsilon^{-4}}\n   \\to C {\\rm ~ as ~} \\gamma\\to 1^-, \\epsilon\\to 0^+.\n$$\n\nThe proof of Theorem 2 only uses the $\\mathcal{O}$ notations to simplify the convergence rates at the end of Appendices N.4-N.5 and to derive the sample complexity in Appendix N.6. **These $\\mathcal{O}$ notations take about only 1 page in total, and will be changed to explicit expressions in the revision within 3 hours, following the procedure below:** \n\nStep 1: At the end of Appendices N.4-N.5, by substituting Eqs. (93-94) into Eqs. (120) and (125), we can obtain **O-free convergence rates** of $\\mathbb{E}\\big[\\|G_{b}^{(\\theta)}(\\theta_{\\widetilde{k}},\\xi_{\\widetilde{k}})\\|^2\\big]$ and $\\mathbb{E}\\big[\\|G_{a}^{(\\xi)}(\\theta_{\\widetilde{k}},\\xi_{\\widetilde{k}})\\|^2\\big]$ respectively. \n\nStep 2: In Appendix N.6, the hyperparameters with $\\mathcal{O}$-notations will be changed to **O-free hyperparameters** as follows.\n$$m_{\\lambda}^{(1)}=m_{\\theta}^{(1)}=m_{\\lambda}^{(3)}=m_{\\xi}^{(3)}=m_{\\lambda}^{(4)}=m_{\\theta}^{(4)}=c_1(1-\\gamma)^{-10}\\epsilon^{-4}, \nm_{\\lambda}^{(2)}=m_{\\xi}^{(2)}=c_2(1-\\gamma)^{-4}\\epsilon^{-2},$$ $$H_{\\lambda}^{(1)}=H_{\\theta}^{(1)}=H_{\\lambda}^{(2)}=H_{\\xi}^{(2)}=H_{\\lambda}^{(3)}=H_{\\xi}^{(3)}=H_{\\lambda}^{(4)}= H_{\\theta}^{(4)}=\\frac{c_3\\log[(1-\\gamma)^{-1}\\epsilon^{-1}]}{1-\\gamma},$$ $$K=c_4(1-\\gamma)^{-8}\\epsilon^{-4}, K'=c_5(1-\\gamma)^{-9}\\epsilon^{-4}], T'=c_6\\log[(1-\\gamma)^{-1}\\epsilon^{-1}],$$ \nwhere the constants $c_1,c_2,c_3,c_4,c_5,c_6>0$ **do not depend on** $\\gamma$, $\\epsilon$ and will be selected in Step 3. \n\nStep 3: In Appendix A.6, substitute the **O-free hyperparameters** (from Step 2) into the **O-free convergence rates** (from step 1). Then all the inequalities like $A\\le \\mathcal{O}(...)$ and $\\mathcal{O}(...)\\le A$ will no longer contain $\\mathcal{O}$ notations and can be proved with sufficiently small constants $c_1,c_2,c_3,c_4,c_5,c_6>0$. \n\nStep 4: In Appendix A.6, substitute the **O-free hyperparameters** (from Step 2) into the sample complexity. \n\n**About other $\\mathcal{O}$ notations:** All $\\mathcal{O}$ notations in the main text follow the above definition and are used to present either results or intuitive proof sketch, which is typical in ML optimization works. Appendices D, E, P and Q containing $\\mathcal{O}$ notations will be removed since these sections focus on concave utilities and other utilities that satisfy weak Minty variational inequality that lack application examples. \n\n[1] Barakat, Anas, Ilyas Fatkhullin, and Niao He. \"Reinforcement learning with general utilities: Simpler variance reduction and large state-action space.\" International Conference on Machine Learning. PMLR, 2023.\n\n[2] Zhang, Junyu, et al. \"On the convergence and sample efficiency of variance-reduced policy gradient method.\" Advances in Neural Information Processing Systems 34 (2021): 2228-2240. \n\n**Q2:** There is no clear motivation given for the article.\n\n**A:** Thank you for pointing out the motivation issue. We have elaborated our motivation with application examples in our global response. We will add these examples to our revised paper. \n\n**Q3:** There are way too many repetitive (and imprecise) citations. One clear citation for the general utility policy gradient theorem should be enough, most citations given do not include such a variant. \n\n**A:**  Thank you for your suggestion. Existing policy gradient theorems only give $\\nabla_{\\theta}f(\\lambda_{\\theta,\\xi})$ while we also need transition kernel gradient $\\nabla_{\\xi}f(\\lambda_{\\theta,\\xi})$, so we present both in Theorem 1 instead of citing policy gradient theorems. We guess you may misunderstand that the 5 citations right before Theorem 1 are used to support Theorem 1. However, we have clearly stated that they are used as examples of linear utility functions, not policy gradient theorem. \n\nWhat other citations do you think are repetitive and imprecise? \n\n**Q4:** To me the article is too technical, a little bit of story telling would be very much appreciated. Perhaps the authors might want to think of splitting the article in two. \n\n**A:** Thank you for your suggestions. In the revised main text, we will add stories including our motivation with application examples (elaborated in our global response) and examples for our assumptions (elaborated in our answer to your Q5), and move the propositions to the appendices to make more main-text space for story telling. To shorten the article, we will remove the parts of concave utilities and other utilities that satisfy weak Minty variational inequality since they lack application examples, so that our theory mainly consists of the two convergence theorems, for gradient and global convergence respectively.", "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:
**About Motivation**

Thank the reviewers for bringing the motivation issue to our attention. **Our revision will include the following special cases and application examples of our proposed problem. First, our proposed *robust RL with general utility* can be applied to improve the policy robustness for the following useful special cases of the existing *RL with general utility* as well as their application examples [1].**

(1) MDP with Constraints or Barriers, which has **safety-critical applications including healthcare [2], autonomous driving [3] and unmanned aerial vehicle [4].**

(2) Pure exploration, which can be **applied to explore environment that is lack of reward signals [5].** 

(3) Learning to mimic a demonstration, which is **used to help the agent mimic the expert demonstration [1].**

**Second, our proposed problem also covers the following useful *robust* special cases and their application examples.**

**(4) Robust Constrained RL [6-8]:**
In **safety critical applications such as healthcare and unmanned aerial vehicle**, it is important for an intelligent agent to constrain its behavior to a safe range while optimizing the performance. However, in practice, the test environment often differs from the training environment which may degrade performance, and may even violate the safety constraints. For example, a safe and effective treatment for a patient may be fatal for another patient. A drone may run out of battery, leading to a crash in the test environment [8].

Robust constrained RL has been proposed to guarantee safety in all possible test environments while  optimizing the robust performance. In robust constrained RL, there are two cost functions $c^{(0)}, c^{(1)}$ relating to performance and safety respectively. Denote $\lambda_{\theta,\xi}$ as the occupancy measure under the policy parameter $\theta\in\Theta$ and the environment parameter $\xi\in\Xi$. Define value functions $V_{\theta,\xi}^{(0)}, V_{\theta,\xi}^{(1)}$ and robust value functions $V_{\theta}^{(0)}, V_{\theta}^{(1)}$ as follows. 

$$
    V_{\theta,\xi}^{(k)}\stackrel{\text { def }}{=}\langle c^{(k)},\lambda_{\theta,\xi}\rangle=\sum_{s,a}c^{(k)}(s,a)\lambda_{\theta,\xi}(s,a),  \quad\quad
    V_{\theta}^{(k)}\stackrel{\text { def }}{=}\max_{\xi\in\Xi} V_{\theta,\xi}^{(k)}, ~ k=0,1.
$$
Robust constrained RL is formulated as the following constrained policy optimization problem.
$$
    \min _ {\theta\in\Theta} V _ {\theta}^{(0)}, ~ {\rm s.t.} ~ V _ {\theta}^{(1)}\le \tau.
$$
where $\tau\in\mathbb{R}$ is the safety threshold.  It can be easily verified that the above robust constrained RL problem is a special case of our proposed  problem $\min_{\theta\in\Theta}\max_{\xi\in\Xi}f(\lambda_{\theta,\xi})$ with the following utility function $f$.
$$
    f(\lambda)=
        \langle c^{(0)},\lambda\rangle {\rm ~ if ~ }\langle c^{(1)},\lambda\rangle\le \tau {\rm ~ and ~ }
        f(\lambda)=+\infty{\rm ~ if ~ }\langle c^{(1)},\lambda\rangle>\tau.
$$

**(5) Entropy Regularized Robust RL [9-10]:** Entropy regularized robust RL has been applied to **imitation learning and inverse reinforcement learning which help agents learn from human demonstration [10]**. Entropy regularized robust RL is formulated as the following minimax optimization problem. 
\begin{align}
    \min_{\theta\in\Theta}\max_{\xi\in\Xi} \sum_{s,a}\big[\lambda_{\theta,\xi}(s,a)c(s,a)\big]-\mu\sum_s\big[\lambda_{\theta,\xi}(s)\mathcal{H}[\pi_{\theta}(\cdot|s)]\big],
\end{align}
where $c$ is the cost function, $\lambda_{\theta,\xi}(s)=\sum_a\lambda_{\theta,\xi}(s,a)$ is the state occupancy measure, and $\mathcal{H}[\pi_{\theta}(\cdot|s)]=-\sum_{a}\pi_{\theta}(a|s)\log\pi_{\theta}(a|s)$ is the entropy regularizer (with coefficient $\mu>0$) which encourages the agent to explore more states and actions and helps to prevent early convergence to sub-optimal policies. 

It can be easily verified that the above entropy regularized robust RL problem is a special case of our proposed problem $\min_{\theta\in\Theta}\max_{\xi\in\Xi}f(\lambda_{\theta,\xi})$ with the following utility function $f$.
\begin{align}
    f(\lambda)=\sum_{s,a}\lambda(s,a)\Big[c(s,a)+\mu\log\frac{\lambda(s,a)}{\sum_{a'}\lambda(s,a')}\Big]
\end{align}

[1] Zhang, Junyu, et al. "Variational policy gradient method for reinforcement learning with general utilities." Advances in Neural Information Processing Systems 33 (2020): 4572-4583.

[2] Corsi, Davide, et al. "Constrained reinforcement learning and formal verification for safe colonoscopy navigation." 2023 IEEE/RSJ International Conference on Intelligent Robots and Systems (IROS). IEEE, 2023.

[3] Hu, Xuemin, et al. "Long and Short-Term Constraints Driven Safe Reinforcement Learning for Autonomous Driving." ArXiv:2403.18209 (2024).

[4] Khairy, Sami, et al. "Constrained deep reinforcement learning for energy sustainable multi-UAV based random access IoT networks with NOMA." IEEE Journal on Selected Areas in Communications 39.4 (2020): 1101-1115.

[5] Hazan, Elad, et al. "Provably efficient maximum entropy exploration." International Conference on Machine Learning. PMLR, 2019.

[6] Russel, Reazul Hasan, Mouhacine Benosman, and Jeroen Van Baar. "Robust Constrained-MDPs: Soft-constrained Robust Policy Optimization Under Model Uncertainty." ArXiv:2010.04870 (2020).

[7] Sun, Zhongchang, et al. "Constrained Reinforcement Learning Under Model Mismatch." ArXiv:2405.01327 (2024).

[8] Wang, Yue, Fei Miao, and Shaofeng Zou. "Robust Constrained Reinforcement Learning." ArXiv:2209.06866 (2022).

[9] Mankowitz, D. J., Levine, N., Jeong, R., Abdolmaleki, A., Springenberg, J. T., Shi, Y., Kay, J., Hester, T., Mann, T., and Riedmiller, M. (2019). Robust reinforcement learning for continuous control with model misspecification. In Proceedings of the International Conference on Learning Representations (ICLR).

[10] Mai, T. and Jaillet, P. (2021). Robust entropy-regularized markov decision processes. ArXiv:2112.15364.

Meta-review: This paper studies concave utility reinforcement learning where the policy belongs to a parameterized uncertainty set. A novel stochastic gradient descent-ascent algorithm for policy optimization is proposed, theoretically analyzed, and experimentally validated. The reviewers are nearly unanimous of its technical merit and innovations. I concur with these assessments and thus recommend this paper be accepted.
Decision: Accept (poster)