Robust Reinforcement Learning with General Utility

Authors: ziyi  chen
yan  wen
zhengmian  hu
heng  huang
Venue: NeurIPS_cc_2024_Conference
Published: 2024-05-15 04:08:13

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.

Main paper: 
 introduction: 
 Reinforcement learning (RL) is an important decision-making framework [41] 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 a variety of practical needs, including risk-sensitive applications [22, 8, 52] , exploration maximization [18, 54, 51, 13, 6] , and safety constraints [54, 51, 13] . There are provably convergent algorithms to solve RL with general utility [54, 55, 6] . However, these works study RL with general utility in a fixed environment, which may fail in many applications where the policy is trained in a simulation environment but implemented in a different real-world environment [37, 56] .To make the policy robust to such environmental change, robust RL has been proposed to find the 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: Q: Can we train a robust policy for RL with general utility and obtain convergence results?We affirmatively answer this question by proposing robust RL with general utility, the first learning framework that obtains a robust policy for general utility in the worst possible environment. It is formulated as a minimax optimization problem min θ∈Θ max ξ∈Ξ f (λ θ,ξ ) where f is the utility function and λ θ,ξ is the occupancy measure under the policy parameter θ ∈ Θ and the environmental transition kernel parameter ξ ∈ Ξ. Our robust RL with general utility is a combination of its two important special cases, namely, RL with general utility [54] (formulated as min θ∈Θ f (λ θ,ξ ) where the environmental parameter ξ is fixed) and robust RL [36] where f is restricted to linear utility function. This new learning framework also covers many other existing RL frameworks including constrained RL [2] and robust constrained RL [43] with safety critical applications such as healthcare and unmanned drones, entropy regularized RL [10] 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 algorithms for our new proposed learning framework with the widely used convex utility function f . In this case, our objective min θ max ξ f (λ θ,ξ ) is still a highly challenging nonconvex-nonconcave minimax optimization problem. Hence, we have to utilize the structure and properties of λ θ,ξ 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 a stationary point of a different envelope function. Hence, we add a second phase targeted at a corrected objective f to converge to a near-stationary solution of the original objective f . The convergence analysis is non-trivial with two novel techniques. First, we have proved a projected gradient dominance property (Proposition 4) 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 a global Nash equilibrium (thus a stationary point) of f by Proposition 4, which is close to a stationary point of f by proving that ∇ ξ f (λ θ,ξ ) ≈ ∇ ξ f (λ θ,ξ ).Furthermore, with convex utility function f and the widely used s-rectangular polyhedral ambiguity set Ξ (including the popular L 1 and L ∞ ambiguity sets), we design an alternative algorithm which converges to a global optimal solution of this nonconvex-nonconcave optimization problem at a sublinear rate O(1/K) (Theorem 3). 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, 15, 25] , so we need novel algorithm design and novel techniques. First, we prove that arg max ξ f (λ θ,ξ ) can be obtained in the finite set of vertices V (Ξ) (Proposition 6). This is intuitive if f (λ θ,• ) is a convex function but in many applications, only f (λ) is convex. To solve this challenge, we prove a novel local invertibility property of λ θ,• (Proposition 5) by checking Bellman equation of λ θ,ξ state by state in two cases. Then we prove Proposition 6 using a novel state-by-state extension from an optimal non-vertex ξ to an optimal vertex ξ. Second, the major difficulty to design our algorithm is to find a descent direction of Γ(θ) := max ξ f (λ θ,ξ ). We select the near-optimal vertices ξ ∈ Ξ k ⊂ V (Ξ) that may affect the optimization progress Γ(θ k+1 ) -Γ(θ k ), and find the descent direction with provably large descent for all the corresponding functions {f (λ θ k ,ξ )} ξ∈Ξ k (Proposition 7) via convex optimization. Third, by Proposition 6, the global convergence measure ∆ k := Γ(θ k ) -min θ Γ(θ) at each iteration k either is O(1/k)-close to optimal (Γ(θ k ) ≤ O(1/k)) or enjoys large descent (Eq. ( 26)), so we prove the convergence in 3 cases: O(1/K)-optimal final θ K , iterate Eq. ( 26) from θ 0 or from a O(1/k)-optimal intermediate θ k .RL with General Utility. Standard RL aims to optimize over the accumulated reward/cost [21, 41] . Some early operation research works focus on other non-linear objectives such as variance-penalized MDPs [12] , risk-sensitive objectives [22, 8, 52] , entropy exploration [18] , constrained RL [2, 1, 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 O(ϵ -3 ) samples to achieve an ϵ-stationary policy for general utility and O(ϵ -2 ) samples to achieve an ϵ-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 method-solving 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 O(ϵ -3 ) samples to achieve ϵ-stationary policy in general and O(ϵ -2 ) samples to achieve ϵ-global optimal policy for convex utility. For large finite state action spaces, it requires O(ϵ -4 ) samples to achieve ϵ-stationary policy via linear function approximation of the occupancy measure. [53] proposes decentralized multi-agent RL with general utilities. [13] shows that convex RL is a subclass of multi-agent mean-field games.Robust RL. Robust RL is designed to learn a 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, 44, 29, 56] or s-rectangular [45, 42, 23, 26] . Methods to solve robust RL include value iteration [36, 20, 45, 15, 25] , policy iteration [20, 4, 24] and policy gradient [29, 44, 56, 42, 26, 17, 28] . 
robust reinforcement learning with general utility: 
 Notations. The space of probability distribution on a space X is denoted as ∆ X . If X is finite, we denote its cardinality as |X |. ∥ • ∥ p denotes p-norm of vectors and ∥ • ∥ = ∥ • ∥ 2 by default.Reinforcement Learning with General Utility. Reinforcement Learning (RL) with general utility is an emerging learning framework [54, 55, 6] , specified by a tuple ⟨S, A, p ξ , f, ρ, γ⟩, with finite state space S, finite action space A, transition kernel p ξ ∈ (∆ S ) S×A parameterized by ξ ∈ Ξ (Ξ ⊂ R dΞ is convex and compact), discount factor γ ∈ (0, 1), general utility function f : ∆ S×A → R and the distribution ρ ∈ ∆ S of the initial state s 0 . At time t, given the environmental state s t , the agent takes action a t ∼ π θ (•|s t ) based on a policy π θ ∈ (∆ A ) S parameterized by θ ∈ Θ (Θ ⊂ R dΘ is convex). Then the environment transitions to state s t+1 ∼ p ξ (•|s t , a t ). The occupancy measure λ θ,ξ ∈ ∆ S×A at (s, a) ∈ S ×A is defined below.EQUATIONwhere P π θ ,p ξ denotes the probability measure of the Markov chain {s t , a t } t≥0 induced by policy π θ , transition kernel p ξ and the initial distribution ρ. The aim of the agent is to find the optimal policy π θ that solves min θ∈Θ f (λ θ,ξ ) given fixed transition kernel p ξ . Here, f (λ θ,ξ ) can be seen as the overall cost of selecting policy π θ in the environment p ξ , and there are many examples of the utility function f covering a variety of applications (See Section 2.1). However, existing works on RL with general utility assume a fixed environmental transition kernel p ξ , which may fail in many applications where the policy is deployed in a 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 RL 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 Ξ, as formulated by the following minimax optimization problem with general utility function f .EQUATIONIn practice, the distance between the real-world environment (for deployment) and simulation environment (for training) is assumed to be bounded. Therefore, Ξ is usually set as a neighborhood around the nominal kernel ξ estimated from the simulation environment, i.e. Ξ = {ξ ∈ R dΘ : d(ξ, ξ) ≤ d 0 } with distance measure d and the distance upper bound d 0 ≥ 0.Example 1: RL with General Utility. When Ξ = { ξ} for a fixed environmental parameter ξ, our proposed robust RL with general utility (2) reduces to (non-robust) RL with general utility min θ∈Θ f (λ θ, ξ ), as introduced above.Example 2: Robust Constrained RL and Its Special Cases.Robust constrained RL [38, 43, 40] is 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 [43] . For math formulation, denote c (0) , c (1) , . . . , c (K) as cost functions S × A → R. At time t, the agent receives performance-related cost c (0) (s t , a t ) and safety-related costs {c (k) (s t , a t )} K k=1 . Define value functionsV (k)θ,ξ and robust value functionsV (k) θ as follows. V (k) θ,ξ def = ⟨c (k) , λ θ,ξ ⟩ = s,a c (k) (s, a)λ θ,ξ (s, a), V (k) θ def = max ξ∈Ξ V (k) θ,ξ , k = 0, 1, . . . , K. (3)Then robust constrained RL is formulated as the following constrained policy optimization problem.EQUATIONwhere τ k ∈ R is the safety threshold, andV (k) θ ≤ τ k means that the safety constraints V (k)θ,ξ ≤ τ k holds for any environmental parameter ξ ∈ Ξ. 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 .EQUATIONAfter removing the safety constraints, robust constrained RL reduces to an important special case called robust RL (formulated as min θ∈Θ max ξ∈Ξ ⟨c (0) , λ θ,ξ ⟩ with linear utility function f (λ) = ⟨c (0) , λ⟩) [36] . Furthermore, when Ξ = { ξ} for fixed ξ, robust constrained RL and robust RL reduce to constrained RL [2] and RL [41] respectively. All these examples are important special cases of our proposed robust RL with general utility based on Proposition 1.Example 3: Robust Entropy Regularized RL and Its Special Cases.Robust entropy regularized RL is also an important RL framework with application to imitation learning and inverse reinforcement learning which help agents learn from human experts' demonstration [32, 33] , and is formulated as the following minimax optimization problem.EQUATIONwhere c is a cost function, λ θ,ξ (s) = a λ θ,ξ (s, a) is the state occupancy measure, and H[π θ (•|s)] = a π θ (a|s) log π θ (a|s) is the entropy regularizer (with coefficient µ ≥ 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 a special case of our proposed robust RL with general utility (2) using the following convex utility function f .EQUATIONWhen µ = 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 Ξ = { ξ}, robust entropy regularized RL, robust RL and robust pure exploration reduce to entropy regularized RL [10] , RL [41] and pure exploration [18] respectively. All these examples are important special cases of our proposed robust RL with general utility based on Proposition 2.Theorem 1. The gradients of the objective function (2) for our proposed robust RL with general utility can be computed as follows.EQUATIONEQUATIONWe make the following standard assumptions which are also used in RL with general utility [55, 6] . Assumption 1. There exist constants l π θ , L π θ , l p ξ , L p ξ > 0 such that for all s, s ′ ∈ S, a ∈ A, θ, θ ′ ∈ Θ and ξ, ξ ′ ∈ Ξ, we have∥∇ θ log π θ (a|s)∥ ≤ ℓ π θ , ∥∇ θ log π θ ′ (a|s) -∇ θ log π θ (a|s)∥ ≤ L π θ ∥θ ′ -θ∥, ∥∇ ξ log p ξ (s ′ |s, a)∥ ≤ ℓ p ξ , ∥∇ ξ log p ξ ′ (s ′ |s, a) -∇ ξ log p ξ (s ′ |s, a)∥ ≤ L p ξ ∥ξ ′ -ξ∥.Assumption 2. There exist constants l λ , L λ > 0 such that for all λ, λ′ ∈ ∆ S×A , ∥∇ λ f (λ)∥ ≤ l λ and ∥∇ λ f (λ ′ ) -∇ λ f (λ)∥ ≤ L λ ∥λ ′ -λ∥. Proposition 3.Under Assumptions 1 and 2, the gradients (8) and (9) satisfy the following bounds for any θ, θ ′ ∈ Θ and ξ, ξ ′ ∈ Ξ.EQUATION)EQUATIONEQUATIONwhere L θ,θ :=ℓ 2 π θ √ |A|(L λ +ℓ λ √ |S||A|) (1-γ) 3 + Lπ θ ℓ λ (1-γ) 2 , L θ,ξ := γℓπ θ ℓp ξ √ |S| (1-γ) 3 (L λ + 2ℓ λ |S||A|), L ξ,θ := ℓπ θ ℓp ξ √ |A|(L λ +ℓ λ √ |S||A|) (1-γ) 3 , L ξ,ξ := γℓ 2 p ξ √ |S|(L λ +2ℓ λ √ |S||A|) (1-γ) 3 + ℓ λ (Lp ξ +ℓ 2 p ξ |S|) (1-γ) 2 .In practice, the exact gradients ( 8) 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, a > 0, which have been used to measure convergence of algorithms to stationary points of optimization [30, 5, 47] and RL problems [49, 46, 34] .G (θ) b (θ, ξ) := 1 b θ-proj Θ θ-b∇ θ f (λ θ,ξ ) , G (ξ) a (θ, ξ) := 1 a proj Ξ ξ +a∇ ξ f (λ θ,ξ ) -ξ (13)3 Gradient Convergence for Convex Utility Assumption 3. The utility function f (λ) is convex.Robust RL with convex utility functions f subsumes many important special cases, including robust constrained RL, robust entropy regularized RL, constrained RL, robust RL, RL, pure exploration, etc., as shown in Examples 2 and 3 in Section 2.1.Partially inspired by the gradient descent ascent (GDA) algorithm [31] for nonconvex-concave minimax optimization, we design the projected stochastic GDA algorithm (Algorithm 1) 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 f . Specifically, in the k-th the outer loop with fixed ξ k , the inner loop applies T projected stochastic gradient descent steps (14) to obtain θ k which converges to the global solution of Φ(ξ k ) := min θ∈Θ f (λ θ,ξ k ) as f is convex. Then, we update ξ k 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 Φ1 .EQUATION)To converge to a stationary point of f , we add the second phase (called corrected phase) which applies projected stochastic GDA to the following corrected objective.EQUATION)Algorithm 1 Projected Stochastic Gradient Descent Ascent Algorithm For Convex Utility1: Hyperparameters: K, T , K ′ , T ′ , α, β, a, b, L ξ,ξ , {m (k) λ , H (k) λ , m (k) θ , H (k) θ } 4 k=1 . 2: Initialize: ξ 0 ∈ Ξ, θ 0 , θ K ∈ Θ.# Begin original phase to solve the original optimization problem (2) 3: for Iterations k = 0, 1, . . . , K -1 doInitialize θ k,0 ← θ 0 .for Inner steps t = 0, 1, . . . , T -1 doEQUATIONθ , Hθ .Apply the following projected stochastic policy gradient descent step.EQUATIONend for 9:Assign θ k ← θ k,T .10:Obtain gEQUATIONλ , mξ , Hξ .11:Apply the following projected stochastic gradient descent step.EQUATION)12: end for 13: Obtain ξ from {ξ k } K-1 k=0 uniformly at random. # Begin corrected phase to solve the corrected optimization problem (19) 14: forIterations k = K, K + 1, . . . , K + K ′ -1 do 15:Initialize ξ k,0 ← ξ.for Inner steps t = 0, 1, . . . , T ′ -1 doEQUATIONξ , Hξ .Apply the following projected stochastic gradient ascent step.EQUATIONend for 20:Assign ξ k ← ξ k,T ′ .Obtain gEQUATIONλ , Hλ , mθ , Hθ .Apply the following projected stochastic gradient descent step.EQUATION)23: end for 24: Output:(θ k , ξ k )where k is obtained from {K, K + 1, . . . , K + K ′ -1} uniformly at random.The convergence analysis of Algorithm 1 is challenging largely because f (λ θ,ξ ) is only a convex function of λ θ,ξ not of θ. To tackle this challenge for non-robust convex RL with fixed ξ, [54] assumed that a global Lipschitz continuous inverse mapping from λ θ,ξ to θ exists. [55, 6] relaxed this assumption to the following assumption of local inverse mapping, which covers the popular direct policy parameterization π θ (a|s) = θ s,a [6] and softmax policy parameterization π θ (a|s) = exp(θs,a)a ′ exp(θ s,a ′ ) (see Proposition 8 for the proof). Assumption 4 (Local Invertibility of λ •,ξ ). There exists constants ℓ λ -1 > 0 and δ ∈ (0, 1) such that for any fixed θ ∈ Θ and ξ ∈ Ξ, the occupancy measure (1) satisfies: 1. There exists sets U θ,ξ ⊂ Θ and V λ θ,ξ ⊂ ∆ S×A that contain θ and λ θ,ξ respectively, such that λ θ,ξ : U θ,ξ → V λ θ,ξ is a bijection. Its inverse denoted as λ -1 θ,ξ is ℓ λ -1 -Lipscthiz. 2. There exists at least one optimal policy θ * (ξ) ∈ arg min θ ′ ∈Θ f (λ θ ′ ,ξ ) such that for any δ ∈ [0, δ],(1 -δ)λ θ,ξ + δλ θ * (ξ),ξ ∈ V λ θ,ξ .Proposition 4 (Projected Gradient Dominance for Convex Utility). Under Assumptions 1-4, the utility function f satisfies the following gradient dominance property for any θ ∈ Θ and ξ ∈ Ξ.EQUATIONRemark: Proposition 4 indicates that the function f (λ •,ξ ) is projected gradient dominant for convex utility function f , which is important in the convergence analysis of Algorithm 1. Our Proposition 4 is stronger than Lemma F.7 of [6] , a similar gradient dominance property for convex RL which requires assumption of positive definite Fisher information matrix, involves bias in the error term and focuses on unconstrained optimization with softmax parameterized policy (a special of our general parameterized policy with constrained variable θ ∈ Θ).Technical Novelty. In our proof, to tackle the constraint θ ∈ Θ which is more challenging than the unconstrained case Θ = R |S||A| in [55, 6] , we apply Assumption 4 to θ ′ := θ -βG(θ)β (θ, ξ) not to the obvious choice θ, which yieldsθ δ ∈ Θ for any δ ∈ [0, δ] such that λ θ δ ,ξ = (1 -δ)λ θ ′ ,ξ + δλ θ * (ξ),ξ ∈ V λ θ,ξ . Then ∇ θ f (λ θ ′ ,ξ ) ⊤ (θ δ -θ ′ ) (i) ≥ ∇ θ f (λ θ ′ ,ξ )-∇ θ f (λ θ,ξ )+G (θ) β (θ, ξ) ⊤ (θ δ -θ ′ ) (ii) ≥ -O[δ∥G (θ) β (θ, ξ)∥], where (i) uses the projection property(θ δ -θ ′ ) ⊤ [G (θ) β (θ, ξ)-∇ θ f (λ θ,ξ )] ≤ 0 and (ii) uses ∥θ δ -θ ′ ∥ ≤ O(δ).The above bound implies Eq. ( 20) since f is convex and ℓ θ -Lipscthiz. Assumption 5. Ξ is convex and compact with diameter D Ξ := max ξ,ξ ′ ∈Ξ ∥ξ ′ -ξ∥ > 0.Assumption 5 holds for the commonly used direct kernel parameterization p ξ (s ′ |s, a) = ξ(s, a, s ′ ) (for all s, s ′ ∈ S and a ∈ A) [42, 28, 26, 17] and Ξ defined a compact neighborhood around a nominal transition kernel parameter ξ.We show the gradient convergence result of Algorithm 1 by the following theorem and demonstrate the gradient convergence by the experiments in Appendix A. Theorem 2 (Gradient Convergence for Convex Utility). Suppose Assumptions 1-5 hold. For any precision 0 < ϵ ≤ 48L ξ,ξ L √ 2ℓ λ -1 L θ,θ + 4 L + ℓ θ ,(θ k , ξ k ) is an ϵ-close to a stationary point, that is, E[∥G (θ) b (θ k , ξ k )∥ 2 ] ≤ ϵ 2 and E[∥G (ξ) a (θ k , ξ k )∥ 2 ] ≤ ϵ 2 with projected gradients G (θ) b and G (ξ)a defined in Eq. (13) . The number of required stochastic samples isO log 2 [(1-γ) -1 ϵ -1 ] (1-γ) 25 ϵ 10 .Proof Sketch of Theorem 2 and Technical Novelty. Inspired by Appendix D of [31] , ξ from the first phase satisfies E∥∇ Φ( ξ)∥ 2 → 0 (see Appendix N.2). Then, ξ k := ξ k,T ′ from the inner update (16) of the second phase converges to the unique maximizer (denoted as ξ * k ) of the L ξ,ξconcave function f (θ k , •) as T ′ → +∞ (see Appendix N.3). This means the update step ( 17) is approximately projected gradient descent for min θ∈Θ Ψ(θ), which yields the convergence rate ofE ∥G (θ) b (θ k , ξ k )∥ 2 (see Appendix N.4).However, the biggest challenge is to obtain the convergence rate of E ∥G (ξ) a (θ k , ξ k )∥ 2 (see Appendix N.5), which corresponds to ∇ ξ f while the second corrected phase aims at the corrected objective f . To show that∇ ξ f (θ k , ξ k ) ≈ ∇ ξ f (θ k , ξ k ), note that ∇ ξ f (θ k , ξ k ) -∇ ξ f (θ k , ξ k ) = -2L ξ,ξ (ξ k -ξ) and that ∇ Φ( ξ) = 2L ξ,ξ [ξ * ( ξ) -ξ] ≈ 0 (already proved) where ξ * ( ξ) is the unique maximizer of Φ(ξ ′ ) -L ξ,ξ ∥ξ ′ -ξ∥ 2 ,a strongly concave function of ξ ′ in Eq. (18) . Hence, it suffices to showξ k ≈ ξ * ( ξ). Note that (θ k , ξ k ) is an approximate Nash equilibrium of f , i.e., ξ k ≈ ξ * k := arg max ξ∈Ξ f (θ k , ξ) (proved above) and θ k ≈ arg min θ∈Θ f (θ, ξ k ) (derived below). E[ f (θ k , ξ k ) -min θ ′ ∈Θ f (θ ′ , ξ k )] = E[f (λ θ k ,ξ k ) -min θ ′ ∈Θ f (λ θ ′ ,ξ k )] (i) ≤ O(E∥G (θ) β (θ, ξ)∥) ≤ O(ϵ),where (i) uses Proposition 4. Hence, based on the property of Nash equilibrium, we haveξ k ≈ arg max ξ ψ(ξ) = ξ * ( ξ) where ψ(ξ) := min θ∈Θ f (θ, ξ) = Φ(ξ) -L ξ,ξ ∥ξ -ξ∥ 2 . 
global convergence on polyhedral ambiguity set: 
 This section aims to obtain a global optimal policy θ * that minimizes the robust utility Γ(θ) def = max ξ∈Ξ f (λ θ,ξ ). This maximization is challenging for convex utility f . In contrast, global conver-gence results have been obtained without such challenge in some important special cases, including convex RL with fixed ξ [54, 51, 6] and robust RL where linear utility f is amenable to both min θ∈Θ and max ξ∈Ξ [36, 45, 42, 23, 26] . Fortunately, we will show that by using the popular s-rectangular polyhedral ambiguity set Ξ, arg max ξ∈Ξ f (λ θ,ξ ) always exists among the finitely many vertices of Ξ.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 utility, [45] . A common practice to make the problem tractable is to use direct kernel parameterization p ξ (s ′ |s, a) = ξ(s, a, s ′ ) [42, 28, 26, 17] and assume the ambiguity set Ξ to satisfy some certain rectangularity conditions, such as s-rectangularity defined below [45, 42, 23, 26] . Assumption 6. We use direct kernel parameterization and assume that Ξ is s-rectangular, i.e., Ξ = × s∈S Ξ s := {ξ ∈ (∆ S ) S×A : ξ(s, •, •) ∈ Ξ s , ∀s ∈ S}, a Cartesian product of Ξ s ⊂ (∆ S ) A . Proposition 5 (Local Invertibility of λ θ,• ). Suppose Assumption 6 holds and Ξ is a convex set. For any θ ∈ Θ, ξ 0 , ξ 1 ∈ Ξ and δ ∈ [0, 1], define the following kernel parameters ξ δ ∈ (∆ S ) S×A .EQUATIONwhere λ θ,ξ (s) := a∈A λ θ,ξ (s, a) for any s ∈ S, θ ∈ Θ and ξ ∈ Ξ. Then ξ δ ∈ Ξ and its corresponding occupancy measure is λ θ,ξ δ = δλ θ,ξ1 + (1 -δ)λ θ,ξ0 .Remark: Proposition 5 indicates that the mapping from ξ to λ θ,ξ is locally invertible for srectangular set Ξ, which is important to solve the aforementioned challenge that convex utility is not amenable for max ξ∈Ξ f (λ θ,ξ ). This role is similar to that played by the local invertibility assumption (Assumption 4) for policy θ. To our knowledge, Proposition 5 has never been obtained in the existing literature. Assumption 7. Under Assumption 6, for every s ∈ S, Ξ s is a polyhedron spanned by a finite set of vertices V (Ξ s ) := {ξ Polyhedral ambiguity set defined by Assumption 7 includes the widely used s-rectangular L 1 and L ∞ ambiguity sets, defined as Ξ = {ξ ∈ (∆ S ) S×A : ∥ξ(s, :, :) -ξ(s, :, :)∥ p ≤ α s , ∀s ∈ S} for p ∈ {1, ∞} respectively [7, 19, 16] , where ξ ∈ Ξ is the nominal transition kernel usually obtained via empirical estimation. On polyhedral ambiguity set, the optimal kernels arg max ξ∈Ξ f (λ θ,ξ ) can always be obtained at the vertices of Ξ, as shown below. Proposition 6. Under Assumptions 3, 6 and 7, for any θ ∈ Θ, we have ϵ) respectively in the proof in Appendix I), then ξ 1 , ξ 0 are also optimal. Ideally, if ξ 1 ∈ V (Ξ) or ξ 0 ∈ V (Ξ), the proof is done. However, this is not guaranteed since in Proposition 5 and Assumption 6, the convex combination coefficients differ among the states s ∈ S. To solve this challenge, it suffices to find such optimal ξ 1 that differs from ξ * at only one state s such that the non-vertex ξ * (s) / ∈ V (Ξ s ) is replaced with vertex ξ 1 (s) ∈ V (Ξ s ). Then we can conduct such 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 ξ 1 (s), note that on polyhedral set Ξ s , there always exist ξ 1 (s) ∈ V (Ξ s ) and ξ 0 (s) ∈ Ξ s such that the non-vertex point ξ * (s) is a convex combination of ξ 1 (s) and ξ 0 (s), while ξ * (s ′ ) = ξ 1 (s ′ ) = ξ 0 (s ′ ) for any s ′ ̸ = s. Hence, there exists δ ∈ [0, 1] such that ξ * = ξ δ defined by Proposition 5, which implies that λ θ,ξ * is a convex combination of λ θ,ξ * 1 and λ θ,ξ (ϵ) .EQUATIONAlgorithm 2 Globally Converged Algorithm for Convex Utility on Polyhedral Ambiguity Set (23) . One way to solve min d∈B1 A k (d) is to apply projected subgradient method (28) and obtain1: Hyperparameters: K, {σ k , ϵ k , β k } K-1 k=0 . 2: Initialize: θ 0 ∈ Θ. 3: for Iterations k = 0, 1, . . . , K -1 do 4: Calculate λ θ k ,ξ , f (λ θ k ,ξ ) and ∇ θ f (λ θ k ,ξ ) for all ξ ∈ V (Ξ). 5: Select near-optimal vertices Ξ k := {ξ ∈ V (Ξ) : f (λ θ k ,ξ ) ≥ max ξ ′ ∈V (Ξ) f (λ θ k ,ξ ′ ) -σ k }. 6: Find d ′ k ∈ B 1 := {d ∈ R dΘ : ∥d∥ ≤ 1} such that A k (d ′ k ) ≤ min d∈B1 A k (d) + ϵ k . (A k is defined in Eq.d ′ k ∈ arg max d∈{d k,t :0≤t≤T } A k (d).) 7:Letd k := d ′ k /∥d ′ k ∥and obtain θ k+1 by Eq. ( 22). 8: end for 9: Output:(θ K , ξ K ) where ξ K ∈ arg max ξ∈V (Ξ) f (λ θ K ,ξ ).The original objective (2) is equivalent to the minimization problem min θ∈Θ Γ(θ), where Γ(θ) := max ξ∈V (Ξ) f (λ θ,ξ ) with finite vertex set V (Ξ) based on Proposition 6. A natural choice to solve this minimization problem is the following policy update rule (for simplicity we consider the unconstrained policy space Θ = R dΘ as in [55, 6] ).EQUATION)where β k > 0 is the stepsize and d k is a unit descent direction of Γ(θ k ). Subgradient descent method seems an obvious choice for d k which aligns with the direction of a subgradient∇ θ f (λ θ k ,ξ k ) where ξ k ∈ arg max ξ∈V (Ξ) f (λ θ k ,ξ). However, the convergence analysis of subgradient descent method [11] requires the convexity of f (λ •,ξ k ) which does not hold in our setting, and the function value is not monotonically decreasing. To solve these challenges, we design Algorithm 2 which selects near-optimal verticesEQUATIONHere we only care about the near-optimal vertices in Ξ k ⊂ V (Ξ) because for any worse verticesξ ∈ V (Ξ)/Ξ k , f (θ k , ξ) < max ξ ′ ∈V (Ξ) f (λ θ k ,ξ ′ )-σ k implies f (θ k+1 , ξ) < max ξ ′ ∈V (Ξ) f (λ θ k+1 ,ξ ′ ) for appropriate σ k > 0.This means such worse ξ can not affect the optimization progress Γ(θ k ) -Γ(θ k+1 ). Hence, by solving min d∈B1 A k (d), we can obtain a direction d k in which all the potentially effective function values {f (λ θ k ,ξ )} ξ∈Ξ k have uniformly large amount of descent -∇f(λ θ k ,ξ ) ⊤ d k .To analyze the global convergence of Algorithm 2, we want to guarantee sufficient descent Γ(θ k ) -Γ(θ k+1 ) whenever θ k 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 θ * (ξ) with a robust optimal policy θ * ∈ arg min θ∈Θ Γ(θ) and shrinks the range from ξ ∈ Ξ to ξ ∈ V (Ξ).Remark: Assumption 8 is no stronger than Assumption 4 and also covers the popular direct policy parameterization. Also, Assumption 8 guarantees that from any policy θ ∈ Θ, there exists a partial curve {θ δ : δ ∈ [0, δ]} towards a robust optimal policy θ * such that λ θ δ ,ξ = (1 -δ)λ θ,ξ + δλ θ * ,ξ , so we can utilize convexity of f and obtain the following important sufficient descent property. Proposition 7 (Sufficient Descent on Polyhedral Ambiguity Set). Under Assumptions 1-3 and 8, at any θ ∈ Θ := R dΘ , there exists a unit descent direction d (∥d∥ = 1) such thatEQUATION)where θ * ∈ arg min θ ′ ∈Θ Γ(θ) is given by Assumption 8 and x + := max(x, 0) for any x ∈ R.Remark: d in Proposition 7 is a good descent direction since whenever the function value gapf (λ θ,ξ ) -f (λ θ * ,ξ ) > 0, it is dominated by the gradient descent amount -∇ θ f (λ θ,ξ ) ⊤ d > 0.Unlike existing gradient dominance properties for robust RL [42, 26, 17] , f (λ θ,ξ ) -f (λ θ * ,ξ ) ≤ 0 is possible so we use [•] + to cover all cases. This brings challenge and thus novel techniques to 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 2 withβ k = 2 √ 2ℓ λ k+2 , σ k = 4 √ 2ℓ θ ℓ λ k+2and any ϵ k > 0. Then under Assumptions 1-3, 6-8, the algorithm output θ K has the following global convergence rate.EQUATIONRemark: The convergence rate O(1/K) matches the state-of-the-art of policy gradient type methods for robust RL [26] , while the error term ϵ k results from solving the convex optimization problemmin d∈B1 A k (d) in line 6 of Algorithm 2.Technical Novelty. Applying Proposition 7 to Algorithm 2 with σ k = 2β k ℓ θ , we haveEQUATIONTo overcome the main difficulty caused byEQUATIONEQUATION)Then we obtain the rate (25) in 3 cases:If A k (d ′ k ) < 0 for all k = 0, 1, . . . , K -1, iterate Eq. (27) from ∆ 0 ; If A K-1 (d K-1 ) ≥ 0, ∆ K ≤ √ 2ℓ λ -1 ϵ K + σ k ; If A K ′ -1 (d K ′ -1 ) ≥ 0 while A k (d k ) < 0 for all k = K ′ , . . . , K -1, iterate Eq. (27) from ∆ K ′ ≤ √ 2ℓ λ -1 ϵ K ′ -1 + 3β K ′ -1 ℓ θ .Algorithm 2 involves convex optimization problems min d∈B1 A k (d), which can be solved via the following projected subgradient method for t = 0, 1, . . . , T -1.EQUATIONThe best direction d ′ k ∈ arg max d∈{d k,t :0≤t≤T } A k (d) from the above subgradient method achieves ϵ k accuracy within T = O(ϵ -2 k ) steps [11] , which yields the following complexity result. Corollary 1. Under the conditions of Theorem 3, for any ϵ > 0, implement Algorithm 2 withK = 8ℓ λ -1 ϵ -1 (ℓ λ -1 L θ,θ + 2 √ 2ℓ θ ) iterations and T = 36ℓ 2 λ -1 ℓ 2 θ ϵ -2 subgradient descent updates (28) with stepsize α = ϵ 3ℓ λ -1 ℓ 2 θ to obtain d ′ k . Then the output θ K achieves Γ(θ K ) -min θ ′ ∈Θ Γ(θ ′ ) ≤ ϵ.Finally, we can prove that all these Assumptions 1-8 required by our convergence results (Theorems 2 and 3) can be satisfied by the following examples. Proposition 8. Assumptions 1-8 are all satisfied if we use the following choices:• Softmax policy parameterization π θ (a|s) = exp(θs,a)a ′ exp(θ s,a ′ ) , where θ ∈ Θ = [-R, R] |S|×|A| for some constant R > 0 to prevent π θ (a|s) from approaching 0.• Direct kernel parameterization p ξ (s ′ |s, a) = ξ s,a,s ′ with s-rectangular L 1 or L ∞ ambiguity sets defined as Ξ = {ξ ∈ (∆ S ) S×A : ∥ξ(s, :, :) -ξ(s, :, :)∥ p ≤ α s , ∀s ∈ S} for p ∈ {1, ∞} respectively, where the fixed nominal kernel ξ satisfies ξ(s, a, s ′ ) > α s , ∀s, a, s ′ to prevent p ξ (s ′ |s, a) from approaching 0.• The utility function f (λ) defined in Eq. ( 7) for robust entropy regularized RL and its special cases, within the range λ ∈ Λ = {λ θ,ξ : θ ∈ Θ, ξ ∈ Ξ} for the domains Θ and Ξ selected above. 
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. In addition, to extend the results to large or continuous state-action space is also an interesting direction. initial state distribution ρ. To optimize the objective function ( 2), we apply direct parameterization to policy parameter θ s,a = π(a|s) ∈ Θ = (∆ A ) S and transition kernel parameter ξ s,a,s ′ = p(s ′ |s, a) ∈ (∆ S ) S×A . In order to preserve ξ(:, :, 
safeguards: 
 Question: Does the paper describe safeguards that have been put in place for responsible release of data or models that have a high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?Answer: [NA] Justification: This paper does not 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 no 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 is challenging, and many papers do not require this, but we encourage authors to take this into account and make a best faith effort.12. Licenses for existing assets Question: 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?Answer: [NA]Justification: The paper does not use existing assets.Guidelines:• The answer NA means that the paper does not 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 a 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. 
 
 Appendix: G ( ) b ( k , k ) 2 + G ( ) a ( k , k ) 2s ′ ) ∈ ∆ S , We select nominal kernel ξ(•, •, s ′ ) as |10+ε s ′ | s ′ |10+ε s ′ | , where ε s ′ i.i.d∼ N (0, 1) for each s ′ ∈ S. Then we select sufficiently small radius r = 0.01 < min s,a,s ′ ξ s,a,s ′ and use the L 2 ambiguity set Ξ := {ξ : ∥ξ(s, :, :) -ξ(s, :, :)∥ ≤ r} (for transition kernel) such that all ξ ∈ Ξ have all positive entries. As for the general utility function f , we use the following convex entropy function with application to exploration (Example 2.2 of [54] ).EQUATIONwhere λ θ,ξ (s) := a∈A λ θ,ξ (s, a) denotes the state visitation measure for any s ∈ S, θ ∈ Θ and ξ ∈ Ξ.Hyperparameters. For Algorithm 1, we use the following hyperparameters obtained from finetuning but not from Theorem 2:EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONξ = 10, H (3) ξ = 100, m (4) λ = 10, H (4) λ = 100, m (4) θ = 10, H (4) θ = 100.Environment. The experiment is 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 1 is shown in Figure 1 . Here the y-axis is the norm of the true projected gradient ∥G(θ) b (θ k , ξ k )∥ 2 + ∥G (ξ) a (θ k , ξ k )∥ 2 ateach outer iteration k of both phases of Algorithm 1 (separated by the green vertical dashed line), and the x-axis is the sample complexity (i.e., the total number of generated samples up to iteration k). Figure 1 shows that the projected gradient decays and converges to a small value, which matches Theorem 2.Lemma 1. Under Assumption 1, for any s, s ′ ∈ S, a ∈ A, θ, θ ′ ∈ Θ, ξ, ξ ′ ∈ Ξ, we haveEQUATIONEQUATIONProof. Based on Assumption 1, the following inequalities holds for all s, s ′ ∈ S, a ∈ A, θ ∈ Θ, ξ ∈ Ξ, which by Lagrange mean value theorem directly proves Eq. ( 30)∥∇ θ π θ (a|s)∥ ≤ ∥∇ θ log π θ (a|s)∥ ≤ ℓ π θ , ∥∇ ξ p ξ (s ′ |s, a)∥ ≤ ∥∇ ξ log p ξ (s ′ |s, a)∥ ≤ ℓ p ξ .Then we prove Eq. ( 31) as follows.∇ ξ p ξ ′ (s ′ |s, a) -∇ ξ p ξ (s ′ |s, a) = p ξ ′ (s ′ |s, a)∇ ξ log p ξ ′ (s ′ |s, a) -p ξ (s ′ |s, a)∇ ξ log p ξ (s ′ |s, a) ≤p ξ ′ (s ′ |s, a) ∇ ξ log p ξ ′ (s ′ |s, a) -∇ ξ log p ξ (s ′ |s, a) + |p ξ ′ (s ′ |s, a) -p ξ (s ′ |s, a)| ∇ ξ log p ξ (s ′ |s, a) (i) ≤p ξ ′ (s ′ |s, a)L p ξ ∥ξ ′ -ξ∥ + ℓ p ξ • ℓ p ξ ∥ξ ′ -ξ∥ ≤ L p ξ p ξ ′ (s ′ |s, a) + ℓ 2 p ξ ∥ξ ′ -ξ∥, where (i) uses Eq. ( 30) and Assumption 1.Lemma 2. For any θ ∈ Θ and ξ ∈ Ξ, the occupancy measure λ θ,ξ defined by Eq. ( 1) is the unique solution to the following Bellman equation of λ ∈ R |S|×|A| .EQUATION)Therefore, the state occupancy measure λ θ,ξ (s) := a∈A λ θ,ξ (s, a) satisfiesEQUATIONProof. First, we can prove that λ θ,ξ satisfies Eq. ( 32) as follows.λ θ,ξ (s ′ , a ′ ) = (1 -γ) +∞ t=0 γ t P π θ ,p ξ (s t = s ′ , a t = a ′ |s 0 ∼ ρ) = π θ (a ′ |s ′ )(1 -γ) +∞ t=0 γ t P π θ ,p ξ (s t = s ′ |s 0 ∼ ρ) = π θ (a ′ |s ′ )(1 -γ) P π θ ,p ξ (s 0 = s ′ |s 0 ∼ ρ) + γ +∞ t=0 γ t P π θ ,p ξ (s t+1 = s ′ |s 0 ∼ ρ) = π θ (a ′ |s ′ )(1 -γ) ρ(s ′ ) + γ +∞ t=0 γ t s,a P π θ ,p ξ (s t = s, a t = a|s 0 ∼ ρ)p ξ (s ′ |s, a) = π θ (a ′ |s ′ ) (1 -γ)ρ(s ′ ) + γ s,a p ξ (s ′ |s, a) (1 -γ) +∞ t=0 γ t P π θ ,p ξ (s t = s, a t = a|s 0 ∼ ρ) = (1 -γ)ρ(s ′ ) + γ s,a λ θ,ξ (s, a)p ξ (s ′ |s, a) π θ (a ′ |s ′ ).Next, we prove the uniqueness. Suppose λ 1 , λ 2 ∈ R |S|×|A| satisfies Eq. ( 32). Then we haves ′ ,a ′ |λ 2 (s ′ , a ′ ) -λ 1 (s ′ , a ′ )| = s ′ ,a ′ γπ θ (a ′ |s ′ ) s,a [λ 2 (s, a) -λ 1 (s, a)]p ξ (s ′ |s, a) ≤γ s ′ s,a |λ 2 (s, a) -λ 1 (s, a)|p ξ (s ′ |s, a) ≤γ s,a |λ 2 (s, a) -λ 1 (s, a)|,which implies that (1 -γ) s,a |λ 2 (s, a) -λ 1 (s, a)| ≤ 0 and thus λ 2 = λ 1 , i.e., the solution to Eq. ( 32) is unique.Finally, we will prove Eq. (33) . Note thatλ θ,ξ (s) = a∈A λ θ,ξ (s, a) (i) = (1 -γ)ρ(s ′ ) + γ s,a λ(s, a)p ξ (s ′ |s, a),where (i) uses Eq. ( 32). Then Eq. ( 33) can be proved by substituting the above equality into Eq. ( 32).Lemma 3. Under Assumption 1, the occupancy measure (1) satisfies the following Lipschitz properties for any θ, θ ′ ∈ Θ and ξ, ξ ′ ∈ Ξ.EQUATION)Proof. For any θ, θ ′ ∈ Θ and ξ, ξ ′ ∈ Ξ, we have∥λ θ ′ ,ξ ′ -λ θ,ξ ∥ = s ′ ,a ′ |λ θ ′ ,ξ ′ (s ′ , a ′ ) -λ θ,ξ (s ′ , a ′ )| 2 (i) = s ′ ,a ′ γπ θ ′ (a ′ |s ′ ) s,a λ θ ′ ,ξ ′ (s, a)p ξ ′ (s ′ |s, a) -λ θ,ξ (s, a)p ξ (s ′ |s, a) + (1 -γ)ρ(s ′ ) + γ s,a λ θ,ξ (s, a)p ξ (s ′ |s, a) [π θ ′ (a ′ |s ′ ) -π θ (a ′ |s ′ )] 2 1/2 (ii) ≤ s ′ ,a ′ γπ θ ′ (a ′ |s ′ ) s,a λ θ ′ ,ξ ′ (s, a)[p ξ ′ (s ′ |s, a) -p ξ (s ′ |s, a)] 2 + s ′ ,a ′ γπ θ ′ (a ′ |s ′ ) s,a p ξ (s ′ |s, a)[λ θ ′ ,ξ ′ (s, a) -λ θ,ξ (s, a)] 2 s ′ ,a ′ (1 -γ)ρ(s ′ ) + γ s,a λ θ,ξ (s, a)p ξ (s ′ |s, a) [π θ ′ (a ′ |s ′ ) -π θ (a ′ |s ′ )] 2 (iii) ≤ γ s ′ (ℓ p ξ ∥ξ ′ -ξ∥) 2 + γ s ′ s,a p ξ (s ′ |s, a)[λ θ ′ ,ξ ′ (s, a) -λ θ,ξ (s, a)] 2 + a ′ (ℓ π θ ∥θ ′ -θ∥) 2 (iv) ≤ γℓ p ξ |S|∥ξ ′ -ξ∥ + γ s ′ s,a p ξ (s ′ |s, a)|λ θ ′ ,ξ ′ (s, a) -λ θ,ξ (s, a)| 2 + ℓ π θ |A|∥θ ′ -θ∥ ≤γℓ p ξ |S|∥ξ ′ -ξ∥ + γ∥λ θ ′ ,ξ ′ -λ θ,ξ ∥ + ℓ π θ |A|∥θ ′ -θ∥,where (i) uses Eq. ( 32), (ii) uses triangular inequality, (iiiEQUATIONs, a)p ξ (s ′ |s, a)] = 1 and (iv) uses Jensen'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 ∈ ∆ X on finite space X has the upper bound that ∥x -y∥ ≤ √ 2.Proof. Denote d = |X | and x j , y j as the j-th entry of x, y respectively. Then∥x -y∥ 2 ≤ d j=1 x 2 j + y 2 j -2x j y j ≤ d j=1x j + y j = 2.Lemma 5. Under Assumptions 1-2, the projected gradients in (13) have the following properties.EQUATIONEQUATIONEQUATION)Proof. The proof for ∥G (θ)β (θ, ξ)∥ in Eq. ( 35) simply follows from the contraction property of projection as follows.∥G (θ) β (θ, ξ)∥ := 1 β θ -proj Θ θ-β∇ θ f (λ θ,ξ ) ≤ 1 β θ -θ-β∇ θ f (λ θ,ξ ) = ∥∇ θ f (λ θ,ξ )∥.Then, ∥∇ θ f (λ θ,ξ )∥ ≤ ℓ θ by Proposition 3. The proof logic for ∥G (ξ)β (θ, ξ)∥ is the same. Next, we prove Eq. ( 36) as follows and the proof of Eq. ( 37) follows the same logic.EQUATIONwhere (i) uses Proposition 3.EQUATIONProof. For any δ ∈ (0, 1], x δ := δx ′ + (1 -δ)proj X (x) belongs to the convex set X since x ′ , proj X (x) ∈ X . Then based on the definition of projection we have0 ≤∥x δ -x∥ 2 -∥proj X (x) -x∥ 2 ≤∥x δ -proj X (x)∥ 2 -2[x δ -proj X (x)] ⊤ [x -proj X (x)] =δ 2 ∥x ′ -proj X (x)∥ 2 -2δ[x ′ -proj X (x)] ⊤ [x -proj X (x)].The above inequality can be rearranged as follows[x ′ -proj X (x)] ⊤ [x -proj X (x)] ≤ δ 2 ∥x ′ -proj X (x)∥ 2 ,which proves Eq. ( 39) as δ → +0.To get the stochastic estimation of the gradients ( 8) and ( 9), we first estimate the occupancy measure (1) as follows.EQUATIONwhere 1{•} is an indicator function and τ (λ) := {τ (λ) i } m λ i=1 contains m λ independent trajectories τ (λ) i := {s (λ) i,h , a (λ) i,h } H λ -1h=0 (i = 1, . . . , m λ ) of length H λ generated from the policy π θ and transition kernel p ξ . Then the estimated cost function isc := ∇ λ f [ λ(τ (λ) )].Algorithm 3 Obtain Stochastic Gradients at (θ, ξ)1: Input: z := (θ, ξ) ∈ Z := Θ × Z. 2: Hyperparameters: m λ , H λ , m θ , H θ , m ξ , H ξ . 3: Generate independent trajectories τ (λ) i := {s (λ) i,h , a (λ) i,h } H λ -1h=0 (i = 1, . . . , m λ ) from π θ , p ξ . 4: Obtain λ(τ (λ) ; s, a) for every s, a ∈ S × A by Eq. ( 40) with τ (λ) := {τ(λ) i } m λ i=1 . 5: Obtain c := ∇ λ f [ λ(τ (λ) )]. 6: Generate independent trajectories τ (θ) i := {s (θ) i,h , a (θ) i,h } H θ -1h=0 (i = 1, . . . , m θ ) from π θ , p ξ . 7: Obtain g (θ) (τ (θ) , θ, ξ, c) by Eq. ( 41) with τ (θ) := {τ(θ) i } m θ i=1 . 8: Generate independent trajectories τ (ξ) i := {s (ξ) i,h , a (ξ) i,h } H ξ -1 h=0 (i = 1, . . . , m ξ ) from π θ , p ξ . 9: Obtain g (ξ) (τ (ξ) , θ, ξ, c) by Eq. (42) with τ (ξ) := {τ (ξ) i } m ξ i=1 . 10: Output: g (θ) (τ (θ) , θ, ξ, c) ≈ ∇ θ f (λ θ,ξ ), g (ξ) (τ (ξ) , θ, ξ, c) ≈ ∇ ξ f (λ θ,ξ ).The stochastic gradients ( 8) and ( 9) can be approximated respectively by the following stochastic sample averaged values known as GPOMDP [50] .EQUATIONEQUATION)whereτ (θ) := {τ (θ) i } m θ i=1 and τ (ξ) := {τ (ξ) i } m ξ i=1 contain m θ independent trajectories τ (θ) i := {s (θ) i,h , a (θ) i,h } H θ -1 h=0 (i = 1, . . . , m θ ) and m ξ independent trajectories τ (ξ) i := {s (ξ) i,h , a (ξ) i,h } H ξ -1 h=0 ∪ {s (ξ)i,H ξ } (i = 1, . . . , m ξ ) respectively, both generated from the policy π θ 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 1 and 2, the stochastic gradients (41) and (42) have the following error bounds.EQUATIONEQUATIONAs follows, we slightly rewrite the utility function f defined in Eq. ( 5), by replacing λ with λ θ,ξ .EQUATIONTherefore, for any θ ∈ Θ, we havemax ξ∈Ξ f (λ θ,ξ ) = max ξ∈Ξ ⟨c (0) , λ θ,ξ ⟩, if ⟨c (k) , λ θ,ξ ⟩ ≤ τ k for all ξ ∈ Ξ and k = 1, . . . , K + ∞, otherwise .Recalling the definition of the robust value function (3), i.e., V (k) θ def = max ξ∈Ξ ⟨c (k) , λ θ,ξ ⟩, the equation above can be rewritten as follows.EQUATIONTherefore, θ ∈ Θ minimizes max ξ∈Ξ f (λ θ,ξ ) if and only if θ solves the constrained robust RL problem (4), as repeated below.min θ∈Θ V (0) θ , s.t. V (k) θ ≤ τ k for all k = 1, . . . , K.Finally, we will prove that f (λ) defined in Eq. ( 5) is a convex function. Note thatA k = {λ ∈ ∆ S×A : ⟨c (k) , λ⟩ ≤ τ k } is a convex set, so A = ∩ K k=1A k is also a convex set. Then for any λ 1 , λ 0 ∈ ∆ S×A and α ∈ [0, 1], we aim to prove thatEQUATION) If either λ 1 /∈ A or λ 0 / ∈ A, then Eq. ( 45) obviously holds as the right side equals +∞. Otherwise, if λ 1 , λ 0 ∈ A, then δλ 1 + (1 -δ)λ 0 ∈ A as A is a convex set, and thus Eq. ( 45) holds with equality as proved below.f [δλ 1 + (1 -δ)λ 0 ] =⟨c (0) , δλ 1 + (1 -δ)λ 0 ⟩ =δ⟨c (0) , λ 1 ⟩ + (1 -δ)⟨c (0) , λ 0 ⟩ =δf (λ 1 ) + (1 -δ)f (λ 0 ).The utility function f in Eq. ( 7) satisfiesf (λ θ,ξ ) = s,a λ θ,ξ (s, a) c(s, a) + µ log λ θ,ξ (s, a) a ′ λ θ,ξ (s, a ′ ) (i) = s,a λ θ,ξ (s, a)c(s, a) + µ s,a λ θ,ξ (s)π θ (a|s) log π θ (a|s) (ii) = s,a λ θ,ξ (s, a)c(s, a) -µ s λ θ,ξ (s)H[π θ (•|s)] .where (i) uses λ θ,ξ (s) = a λ θ,ξ (s, a) and Eq. ( 33) that λ θ,ξ (s, a) = λ θ,ξ (s)π θ (a|s), and (ii) denotes the entropy function that H[π θ (•|s)] =a π θ (a|s) log π θ (a|s). The above function is exactly the minimax objective function (6) of the robust entropy regularized RL.Finally, we will prove that f (λ) defined in Eq. ( 7) is a convex function. For any λ 0 , λ 1 ∈ ∆ S×A and δ ∈ [0, 1], denote λ δ = δλ 1 + (1 -δ)λ 0 , λ δ (s) = a λ δ (s, a) and policy π δ (a|s) = λ δ (s,a) λ δ (s) . Then, the convexity of f can be proved as follows.δf(λ 1 ) + (1 -δ)f (λ 0 ) -f (λ δ ) =µ s,a δλ 1 (s, a) log λ 1 (s, a) λ 1 (s) + (1 -δ)λ 0 (s, a) log λ 0 (s, a) λ 0 (s) -λ δ (s, a) log λ δ (s, a) λ δ (s) =µ s,a δλ 1 (s, a) log π 1 (a|s) + (1 -δ)λ 0 (s, a) log π 0 (a|s) -[δλ 1 (s, a) + (1 -δ)λ 0 (s, a)] log π δ (a|s) =µ s,a δλ 1 (s)π 1 (a|s) log π 1 (a|s) π δ (a|s) + (1 -δ)λ 0 (s)π 0 (a|s) log π 0 (a|s) π δ (a|s) =µ s δλ 1 (s)KL[π 1 (•|s)∥π δ (•|s)] + (1 -δ)λ 0 (s)KL[π 0 (•|s)∥π δ (•|s)] ≥ 0.The first formula of Eq. ( 10) can be proved as follows and the second formula can be proved in the same way.∥∇ θ f (λ θ,ξ )∥ (i) ≤ E π θ ,p ξ +∞ t=0 γ t |c(s t , a t )| t h=0 ∥∇ θ log π θ (a h |s h )∥ (ii) ≤ E π θ ,p ξ +∞ t=0 γ t t h=0 ℓ π θ = ℓ π θ +∞ t=0 γ t (t + 1) = ℓ π θ (1 -γ) 2 ,where (i) uses Eq. ( 41) and (ii) uses c(s t , a t ) ∈ [0, 1] and Assumption 1.Define the following V function.EQUATION)For any fixed cost function c : S × A → R, the gradient ∇ θ V θ,ξ (c) can be rewritten as follows.EQUATIONwhere (i) uses Eq. ( 5) of [6] and (ii) uses the occupancy measure (1) and defines the following Q function.EQUATIONThe above Q function has the following upper boundEQUATIONwhere c max := max s,a |c(s, a)| and also satisfies the following Bellman equation.EQUATIONTherefore, for any θ, θ ′ ∈ Θ, ξ, ξ ′ ∈ Ξ and fixed cost function c, we havemax s,a |Q θ ′ ,ξ ′ (s, a; c) -Q θ,ξ (s, a; c)| ≤γ max s,a s ′ ,a ′ |p ξ ′ (s ′ |s, a) -p ξ (s ′ |s, a)|π θ ′ (a ′ |s ′ )|Q θ ′ ,ξ ′ (s ′ , a ′ ; c)| + γ max s,a s ′ ,a ′ p ξ (s ′ |s, a)|π θ ′ (a ′ |s ′ ) -π θ (a ′ |s ′ )||Q θ ′ ,ξ ′ (s ′ , a ′ ; c)| + γ max s,a s ′ ,a ′ p ξ (s ′ |s, a)π θ (a ′ |s ′ )|Q θ ′ ,ξ ′ (s ′ , a ′ ; c) -Q θ,ξ (s ′ , a ′ ; c)| (i) ≤ γc max 1 -γ max s,a ∥p ξ ′ (•|s, a) -p ξ (•|s, a)∥ 1 + max s ∥π θ ′ (•|s) -π θ (•|s)∥ 1 + γ max s,a |Q θ ′ ,ξ ′ (s, a; c) -Q θ,ξ (s, a; c)|,where (i) uses Eq. ( 49). Rearranging the above inequality yields that max s,aEQUATION)where (i) uses Lemma 1. For any θ ∈ Θ, ξ ∈ Ξ and fixed cost functions c, c ′ , we haveEQUATION)where (i) uses Eq. ( 48).Therefore, Eq. ( 11) can be proved as follows.∥∇ θ f (λ θ ′ ,ξ ′ ) -∇ θ f (λ θ,ξ )∥ =∥∇ θ V θ ′ ,ξ ′ [∇ λ f (λ θ ′ ,ξ ′ )] -∇ θ V θ,ξ [∇ λ f (λ θ,ξ )]∥ (i) ≤ 1 1 -γ s,a λ θ ′ ,ξ ′ (s, a) -λ θ,ξ (s, a) ∇ θ log π θ ′ (a|s) Q θ ′ ,ξ ′ [s, a; ∇ λ f (λ θ ′ ,ξ ′ )] + 1 1 -γ s,a λ θ,ξ (s, a) ∇ θ log π θ ′ (a|s) -∇ θ log π θ (a|s) Q θ ′ ,ξ ′ [s, a; ∇ λ f (λ θ ′ ,ξ ′ )] + 1 1 -γ s,a λ θ,ξ (s, a) ∇ θ log π θ (a|s) Q θ ′ ,ξ ′ [s, a; ∇ λ f (λ θ ′ ,ξ ′ )] -Q θ,ξ [s, a; ∇ λ f (λ θ ′ ,ξ ′ )] + 1 1-γ s,a λ θ,ξ (s, a) ∇ θ log π θ (a|s) Q θ,ξ [s, a; ∇ λ f (λ θ ′ ,ξ ′ )]-Q θ,ξ [s, a; ∇ λ f (λ θ,ξ )] (ii) ≤ ℓ π θ ℓ λ (1 -γ) 2 s,a λ θ ′ ,ξ ′ (s, a) -λ θ,ξ (s, a) + L π θ ℓ λ (1 -γ) 2 s,a λ θ,ξ (s, a)∥θ ′ -θ∥ + ℓ π θ 1 -γ s,a λ θ,ξ (s, a) • γℓ λ (1 -γ) 2 ℓ p ξ |S|∥ξ ′ -ξ∥ + ℓ π θ |A|∥θ ′ -θ∥ + ℓ π θ (1 -γ) 2 s,a λ θ,ξ (s, a) ∇ λ f (λ θ ′ ,ξ ′ ) -∇ λ f (λ θ,ξ ) ∞ (iii) ≤ ℓ π θ ℓ λ |S||A| (1 -γ) 2 λ θ ′ ,ξ ′ -λ θ,ξ + L π θ ℓ λ (1 -γ) 2 ∥θ ′ -θ∥ + γℓ λ ℓ π θ (1 -γ) 3 ℓ p ξ |S|∥ξ ′ -ξ∥ + ℓ π θ |A|∥θ ′ -θ∥ + ℓ π θ L λ (1 -γ) 2 λ θ ′ ,ξ ′ -λ θ,ξ (iv) ≤ ℓ π θ (L λ + ℓ λ |S||A|) (1 -γ) 2 • γℓ p ξ |S|∥ξ ′ -ξ∥+ℓ π θ |A|∥θ ′ -θ∥ 1 -γ + L π θ ℓ λ (1 -γ) 2 ∥θ ′ -θ∥ + γℓ λ ℓ π θ (1 -γ) 3 ℓ p ξ |S|∥ξ ′ -ξ∥ + ℓ π θ |A|∥θ ′ -θ∥ (v) ≤ γℓ π θ ℓ p ξ |S| (1 -γ) 3 (L λ +2ℓ λ |S||A|)∥ξ ′ -ξ∥+ ℓ 2 π θ |A|(L λ +ℓ λ |S||A|) (1 -γ) 3 + L π θ ℓ λ (1 -γ) 2 ∥θ ′ -θ∥,where (i) uses the gradient (47), (ii) uses Assumptions 1-2 and Eqs. ( 49), ( 51) and ( 52) with c max = ∥∇ λ f (λ θ ′ ,ξ ′ )∥ ∞ replaced by its upper bound ℓ λ , (iii) uses Assumption 2, (iv) uses Lemma 3 and (v) uses Assumption 1.The proof of Eq. ( 12) follows the same logic. To elaborate, ∇ ξ V θ,ξ (c) can be derived as follows in a similar way to the derivation of Eq. ( 47)EQUATIONwhere (i) uses the occupancy measure (1) and defines the following V function.EQUATION)The above V function has the following upper boundEQUATIONwhere c max := max s,a |c(s, a)| and also satisfies the following Bellman equation.EQUATIONAs a result,max s |V θ ′ ,ξ ′ (s; c) -V θ,ξ (s; c)| ≤ max s a π θ ′ (a|s) -π θ (a|s) c(s, a) + γ s ′ p ξ ′ (s ′ |s, a) V θ ′ ,ξ ′ (s ′ ; c) + γ max s a π θ (a|s) s ′ p ξ ′ (s ′ |s, a) -p ξ (s ′ |s, a) V θ ′ ,ξ ′ (s ′ ; c) + γ max s a π θ (a|s) s ′ p ξ (s ′ |s, a) V θ ′ ,ξ ′ (s ′ ; c) -V θ,ξ (s ′ ; c) (i) ≤ c max 1 -γ ℓ π θ |A|∥θ ′ -θ∥ + γℓ p ξ |S|∥ξ ′ -ξ∥ + γ max s |V θ ′ ,ξ ′ (s; c) -V θ,ξ (s; c)|,where (i) uses Eq. ( 55) and Lemma 1. Rearranging the above inequality yields thatEQUATIONSimilar to Eq. ( 52), we haveEQUATION)Therefore, we can prove Eq. ( 12) as follows.∥∇ ξ f (λ θ ′ ,ξ ′ ) -∇ ξ f (λ θ,ξ )∥ =∥∇ ξ V θ ′ ,ξ ′ [∇ λ f (λ θ ′ ,ξ ′ )] -∇ ξ V θ,ξ [∇ λ f (λ θ,ξ )]∥ (i) ≤ 1 1 -γ s,a,s ′ λ θ ′ ,ξ ′ (s, a) -λ θ,ξ (s, a) ∇ ξ p ξ ′ (s ′ |s, a) ∇ λ f (λ θ ′ ,ξ ′ )(s, a) + γV θ ′ ,ξ ′ [s ′ ; ∇ λ f (λ θ ′ ,ξ ′ )] + 1 1 -γ s,a,s ′ λ θ,ξ (s, a) ∇ ξ p ξ ′ (s ′ |s, a) -∇ ξ p ξ (s ′ |s, a) ∇ λ f (λ θ ′ ,ξ ′ )(s, a) + γV θ ′ ,ξ ′ [s ′ ; ∇ λ f (λ θ ′ ,ξ ′ )] + γ 1 -γ s,a,s ′ λ θ,ξ (s, a) ∇ ξ p ξ (s ′ |s, a) V θ ′ ,ξ ′ [s; ∇ λ f (λ θ ′ ,ξ ′ )] -V θ,ξ [s; ∇ λ f (λ θ ′ ,ξ ′ )] + 1 1 -γ s,a,s ′ λ θ,ξ (s, a) ∇ ξ p ξ (s ′ |s, a) γ V θ,ξ [s; ∇ λ f (λ θ ′ ,ξ ′ )]-V θ,ξ [s; ∇ λ f (λ θ,ξ )] + ∇ λ f (λ θ ′ ,ξ ′ )(s, a) -∇ λ f (λ θ,ξ )(s, a) (ii) ≤ ℓ p ξ 1 -γ ℓ λ + γℓ λ 1 -γ s,a,s ′ p ξ ′ (s ′ |s, a) λ θ ′ ,ξ ′ (s, a) -λ θ,ξ (s, a) + 1 1 -γ ℓ λ + γℓ λ 1 -γ s,a,s ′ λ θ,ξ (s, a) L p ξ p ξ ′ (s ′ |s, a) + ℓ 2 p ξ ∥ξ ′ -ξ∥ + γℓ p ξ 1 -γ s,a,s ′ λ θ,ξ (s, a)p ξ (s ′ |s, a) • ℓ λ (1 -γ) 2 ℓ π θ |A|∥θ ′ -θ∥ + γℓ p ξ |S|∥ξ ′ -ξ∥ + ℓ p ξ 1 -γ s,a,s ′ λ θ,ξ (s, a)p ξ ′ (s ′ |s, a) γ ∇ λ f (λ θ ′ ,ξ ′ ) -∇ λ f (λ θ,ξ ) ∞ 1 -γ + ∇ λ f (λ θ ′ ,ξ ′ ) -∇ λ f (λ θ,ξ ) ∞ (iii) ≤ ℓ p ξ ℓ λ |S||A| (1 -γ) 2 λ θ ′ ,ξ ′ -λ θ,ξ + ℓ λ L p ξ + ℓ 2 p ξ |S| (1 -γ) 2 ∥ξ ′ -ξ∥ + γℓ λ ℓ p ξ (1 -γ) 3 ℓ π θ |A|∥θ ′ -θ∥ + γℓ p ξ |S|∥ξ ′ -ξ∥ + ℓ p ξ L λ (1 -γ) 2 λ θ ′ ,ξ ′ -λ θ,ξ (iv) ≤ ℓ p ξ L λ + ℓ λ |S||A| (1 -γ) 2 γℓ p ξ |S|∥ξ ′ -ξ∥+ℓ π θ |A|∥θ ′ -θ∥ 1 -γ + ℓ λ L p ξ + ℓ 2 p ξ |S| (1 -γ) 2 ∥ξ ′ -ξ∥ + γℓ λ ℓ p ξ (1 -γ) 3 ℓ π θ |A|∥θ ′ -θ∥ + γℓ p ξ |S|∥ξ ′ -ξ∥ ≤ ℓ π θ ℓ p ξ |A| L λ + ℓ λ |S||A| (1 -γ) 3 ∥θ ′ -θ∥ + γℓ 2 p ξ |S| L λ + 2ℓ λ |S||A| (1 -γ) 3 + ℓ λ L p ξ + ℓ 2 p ξ |S| (1 -γ) 2 ∥ξ ′ -ξ∥,where (i) uses the gradient (53) and denotes∇ λ f (λ θ ′ ,ξ ′ )(s, a) = ∂f (λ θ ′ ,ξ ′ )∂λ(s,a) as the (s, a)-th element of ∇ λ f (λ θ ′ ,ξ ′ ), (ii) uses ∇ ξ p ξ ′ (s ′ |s, a) = p ξ ′ (s ′ |s, a)∇ ξ log p ξ ′ (s ′ |s, a), Assumptions 1-2 and Eqs. ( 31), ( 55), ( 57) and (58) with c max = ∥∇ λ f (λ θ ′ ,ξ ′ )∥ ∞ replaced by its upper bound ℓ λ , (iii) uses Assumptions 2 and (iv) uses Eq. (34) .Implement one projected gradient step from θ and obtain θ ′ = proj Θ θ -β∇ θ f (λ θ,ξ ) = θ -βG (θ) β (θ, ξ) where the projected gradient G (θ) β (θ, ξ) is defined by Eq. ( 13). Based on Assumption 4, for any δ ∈ [0, δ], there exists θ δ ∈ Θ such that λ θ δ ,ξ = (1 -δ)λ θ ′ ,ξ + δλ θ * (ξ),ξ ∈ V λ θ,ξ . Based on Assumption 4, for any δ ∈ [0, δ], there exists θ δ ∈ Θ such that λ θ δ ,ξ = (1 -δ)λ θ ′ ,ξ + δλ θ * (ξ),ξ ∈ V λ θ ′ ,ξ . Then we have,EQUATIONwhere (i) uses the L θ,θ -smoothness of f (λ •,ξ ) based on Proposition 3, (ii) uses Lemma 4.By applying Lemma 6 toX = Θ, x = θ -β∇ θ f (λ θ,ξ ), x ′ = θ δ ∈ Θ (so proj X (x) = θ ′ = θ -βG (θ)β (θ, ξ)), we obtain thatEQUATIONThen on one hand, f (λ θ δ ,ξ ) has the following lower bound.EQUATIONwhere (i) and (iii) use L θ,θ -smoothness of f (λ •,ξ ) based on Proposition 3, (ii) uses Eq. (60), and (iv) uses Lemma 5, ∥θ δ -θ ′ ∥ ≤ √ 2δℓ λ -1 (obtained in the same way as Eq. ( 59)) and θ ′ -θ = -βG (θ) β (θ, ξ). On the other hand, f (λ θ δ ,ξ ) has the following upper bound since f is convex.EQUATION)The above two inequalities (61) and (62) imply thatEQUATIONFinally, we prove Eq. ( 20) as follows.f (λ θ,ξ ) (i) ≤f (λ θ ′ ,ξ ) + ℓ θ ∥θ ′ -θ∥ (ii) ≤ min θ ′′ ∈Θ f (λ θ ′′ ,ξ ) + √ 2ℓ λ -1 βL θ,θ + 1 + βℓ θ ∥G (θ) β (θ, ξ)∥.where (i) uses Eq. ( 10) which implies thatf λ •,ξ is ℓ θ -Lipschitz, (ii) uses θ ′ -θ = -βG (θ)β (θ, ξ) and Eq. ( 63).We will first prove that ξ δ ∈ Ξ. Note that the s-rectangular ambiguity set Ξ can be expressed as a Cartesian product of Ξ s for all s ∈ S. Hence, as Ξ is convex, Ξ s is convex for all s ∈ S. Therefore, for any s ∈ S, ξ δ (s, •, •) ∈ Ξ s since it is a convex combination of ξ 0 (s, •, •) ∈ Ξ s and ξ 1 (s, •, •) ∈ Ξ s defined by Eq. ( 21), so ξ δ ∈ Ξ.Next, we will prove λ θ,ξ δ = δλ θ,ξ1 + (1 -δ)λ θ,ξ0 . Denote λ δ := δλ θ,ξ1 + (1 -δ)λ θ,ξ0 , so the aim becomes to prove λ θ,ξ δ = λ δ . Based on Lemma 2, it suffices to prove the following equation.EQUATIONFor each s ∈ S, consider the following two cases.(Case 1): λ θ,ξ1 (s) > 0 or λ θ,ξ0 (s) > 0.Note that λ δ (s, a)ξ δ (s, a, s ′ )EQUATIONEQUATIONEQUATIONwhere (i) uses Eq. ( 21) and λ δ := δλ θ,ξ1 + (1 -δ)λ θ,ξ0 , (ii) and (iii) use Eq. ( 33).(Case 2): λ θ,ξ0 (s) = λ θ,ξ1 (s) = 0.In this case, λ δ (s) = δλ θ,ξ1 (s)+(1-δ)λ θ,ξ0 (s) = 0 and thus λ δ (s, a) = λ θ,ξ1 (s, a) = λ θ,ξ0 (s, a) = 0 for any a ∈ A, so Eq. ( 65) also holds for any choice of ξ δ (s, •, •).Therefore, we can prove Eq. (64) as follows.(EQUATIONwhere (i) uses Eq. ( 65) and λ δ := δλ θ,ξ1 + (1 -δ)λ θ,ξ0 and (ii) applies Lemma 2 to λ θ,ξ1 and λ θ,ξ0 .Fix any θ ∈ Θ, and there exists at least oneξ * ∈ arg max ξ ′ ∈Ξ f (λ θ,ξ ′ ). If ξ * ∈ V (Ξ) := × s∈S V (Ξ s ), then this proposition directly holds. Hence, we focus on the case where ξ * / ∈ V (Ξ), which means ξ * (s 0 ) / ∈ V (Ξ s0 ) for at least one s 0 ∈ S.Based on Assumption 6-7, there exists a probability vector ν:= [ν 1 , . . . , ν Ms 0 ] such that ξ * (s 0 ) = Ms 0 m=1 ν m ξ (s0)m , where we denote ξ ′ (s) := ξ ′ (s, •, •) ∈ Ξ s for all ξ ′ ∈ Ξ. Without loss of generality, we assume ν 1 = max 1≤m≤Ms ν m (Otherwise we can make this assumption hold by permutating the elements in each Ξ s .).For any ϵ > 0, define ξ * 1 , ξ (ϵ) ∈ (∆ S ) S×A such that ξ * 1 (s) = ξ (ϵ) (s) = ξ * (s) for any s ̸ = s 0 , while at s = s 0 we define ξ* 1 (s 0 ) = ξ (s0) 1 ∈ V (Ξ s0 ) and ξ (ϵ) (s 0 ) =ξ * (s 0 ) + ϵ[ξ * (s 0 ) -ξ * 1 (s 0 )] = [(1 + ϵ)ν 1 -ϵ]ξ (s0) 1 + Ms 0 m=2 (1 + ϵ)ν m ξ (s0) m ,which implies thatEQUATION)It is easily seen that ξ * 1 ∈ Ξ by its definition. Since lim ϵ→+0 [(1 + ϵ)ν 1 (s) -ϵ] = ν 1 (s) = max 1≤m≤Ms ν m (s) > 0, there exists a sufficiently small ϵ > 0 such that [(1 + ϵ)ν 1 (s) -ϵ, (1 + ϵ)ν 2 (s), . . . , (1 + ϵ)ν Ms (s)] ∈ [0, 1] |Ξs| is a probability vector and thus ξ (ϵ) ∈ Ξ. Furthermore, select arbitrary δ ∈ [0, 1] if λ θ,ξ (ϵ) (s 0 ) = λ θ,ξ * 1 (s 0 ) = 0 and the following δ otherwise.EQUATIONwhere λ θ,ξ (s) := a∈A λ θ,ξ (s, a) is defined as the state occupancy measure for any s ∈ S, θ ∈ Θ and ξ ∈ Ξ. Then it can be directly verified that ξ * satisfies the following equality.ξ * (s, a, s ′ ) =      arbitrary as long as ξ * (s, a, •) ∈ ∆ S , if λ θ,ξ (ϵ) (s) = λ θ,ξ * 1 (s) = 0 δλ θ,ξ * 1 (s)ξ * 1 (s, a, s ′ )+(1-δ)λ θ,ξ (ϵ) (s)ξ (ϵ) (s, a, s ′ ) δλ θ,ξ * 1 (s)+(1-δ)λ θ,ξ (ϵ) (s), otherwise .Hence, based on Proposition 5, ξ * satisfiesEQUATIONOn one hand,f (λ θ,ξ * 1 ) ≤ f (λ θ,ξ * ) and f (λ θ,ξ (ϵ) ) ≤ f (λ θ,ξ * ) since ξ * ξ * ∈ arg max ξ ′ ∈Ξ f (λ θ,ξ ′ ).On the other hand, the above Eq. ( 68) along with convexity of f implies thatf (λ θ,ξ * ) ≤ δf (λ θ,ξ * 1 ) + (1 -δ)f (λ θ,ξ (ϵ) ). Therefore, f (λ θ,ξ * 1 ) = f (λ θ,ξ (ϵ) ) = f (λ θ,ξ * ) = max ξ ′ ∈Ξ f (λ θ,ξ ′ ). If ξ * 1 ∈ V (Ξ), then the proof is done. Otherwise, note that ξ * 0 (s 0 ) / ∈ V (Ξ s0 ) while ξ * 1 (s 0 ) ∈ V (Ξ s0), and ξ * 1 (s) = ξ * 0 (s) for any s ̸ = s 0 . Hence, in the same way, we can obtain the sequence ξ * 2 , ξ * 3 , . . . , ξ * N 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):1. For 1 ≤ k ≤ N -1, ξ * k (s k ) / ∈ V (Ξ s k ) while ξ * k+1 (s k ) ∈ V (Ξ s k ), and ξ * k (s) = ξ * k+1 (s) for any s ̸ = s k . 2. ξ * N ∈ V (Ξ). 3. For 1 ≤ k ≤ N , f (λ θ,ξ * k ) = max ξ ′ ∈Ξ f (λ θ,ξ ′ ).As a result, we find the optimal vertex ξ * N ∈ V (Ξ) ∩ arg max ξ ′ ∈Ξ f (λ θ,ξ ′ ), which concludes the proof.Based on Assumption 8, for any θ ∈ Θ and δ ∈ [0, δ], there existsEQUATIONwhere (i) uses the L θ,θ -smoothness of f (λ •,ξ ) based on Proposition 3, (ii) uses Lemma 4. Hence, on one hand, using L θ,θ -smoothness of f (λ •,ξ ) based on Proposition 3, f (λ θ δ ,ξ ) has the following lower bound.EQUATIONOn the other hand, f (λ θ δ ,ξ ) has the following upper bound since f is convex.EQUATIONCombining the above two inequalities, we obtain thatEQUATIONwhere (i) uses Eq. (71), and (ii) uses Eq. ( 69) and assumes f (λ θ,ξ ) ≥ min θ ′ ∈Θ max ξ ′ ∈Ξ f (λ θ ′ ,ξ ′ ) without loss of generality (otherwise, Eq. ( 24) trivially holds).Based on the Bolzano-Weierstrass theorem, there exists a sequence δ n → +0 such that θ δn -θ ∥θ δn -θ∥ → d ∈ R dΘ as n → +∞. Hence, ∥d∥ = 1 and we can conclude the proof by letting δ = δ n and n → +∞ in the above inequality.Proposition 2 indicates that the utility function f defined by Eq. ( 7) is convex, which proves Assumption 3.To prove Assumptions 1 and 2, it suffices to prove that the following functions have bounded first-order and second-order derivatives for any (s, a, s ′ ) ∈ S × A × S. s, :, : ) -ξ(s, :, :)∥ p ≤ α s , ∀s ∈ S} where p ∈ {1, ∞} and ξ(s, a, s ′ ) > α s , ∀s, a, s ′ .1. log π θ (a|s) = θ s,a -log a ′ exp(θ s,a ′ ) as a function of θ ∈ Θ = [-R, R] |S|×|A| . 2. log p ξ (s ′ |s, a) = log ξ(s, a, s ′ ) as a function of ξ ∈ Ξ = {ξ ′ ∈ (∆ S ) S×A : ∥ξ ′ (3. f (λ) = s,a λ(s, a) c(s, a) + µ log λ(s,a) a ′ λ(s,a ′ ) (repeat Eq. ( 7)) as a function of λ ∈ Λ = {λ θ,ξ : θ ∈ Θ, ξ ∈ Ξ}.EQUATION)When p = 1 or p = ∞, any ξ ∈ Ξ satisfies p ξ (s ′ |s, a) = ξ(s, a, s ′ ) ≥ ξ(s, a, s ′ ) -∥ξ(s, :, :) -ξ(s, :, :EQUATIONwhere ξ min > 0 since it is minimum over finitely many positive numbers ξ(s, a, s ′ ) -α s . Then for any θ ∈ Θ and ξ ∈ Ξ, we haveEQUATION)Finally, for any (s, a, s ′ ), (s 1 , a 1 , s ′ 1 ), (s 2 , a 2 , s ′ 2 ) ∈ S × A × S, we obtain all the derivative bounds as follows, where 1{•} is an indicator function.∂ log π θ (a|s) ∂θ(s 1 , a 1 ) = 1{s 1 = s} 1{a 1 = a} -π θ (a 1 |s) ∈ [-1, 1]. ∂ 2 log π θ (a|s) ∂θ(s 1 , a 1 )∂θ(s 2 , a 2 ) = -1{s 1 = s}π θ (a 1 |s) ∂ log π θ (a|s) ∂θ(s 2 , a 2 ) ∈ [-1, 1]. ∂ log p ξ (s ′ |s, a) ∂ξ(s 1 , a 1 , s ′ 1 ) = 1 ξ(s, a, s ′ ) 1{(s 1 , a 1 , s ′ 1 ) = (s, a, s ′ )} ∈ [0, ξ -1 min ]. ∂ 2 log p ξ (s ′ |s, a) ∂ξ(s 1 , a 1 , s ′ 1 )∂ξ(s 2 , a 2 , s ′ 2 ) = -ξ -2 (s, a, s ′ )1{(s 1 , a 1 , s ′ 1 ) = (s 2 , a 2 , s ′ 2 ) = (s, a, s ′ )} ∈ [-ξ -2 min , 0]. ∂f (λ) ∂λ(s 1 , a 1 ) = c(s 1 , a 1 )+log λ(s 1 , a 1 ) a ′ λ(s 1 , a ′ ) +1- λ(s 1 , a 1 ) a ′ λ(s 1 , a ′ ) ∈ c min -log(|A|λ min ), c max +1 ,where c min = min s,a c(s, a) and c max = max s,a c(s, a).∂ 2 f (λ) ∂λ(s 1 , a 1 )∂λ(s 2 , a 2 ) =1{s 1 = s 2 } 1{a 1 = a 2 } λ(s 1 , a 1 ) - 1 a ′ λ(s 1 , a ′ ) - 1{a 1 = a 2 }-λ(s 1 , a 1 ) [ a ′ λ(s 1 , a ′ )] 2 ∈ - 1 |A|λ min - 1 |A| 2 λ 2 min , 1 λ min + 1 |A|λ min .K.2 Proof of Assumptions 5, 6 and 7 about ambiguity set ΞIt is straightforward to verify that the ambiguity set Ξ = {ξ ∈ (∆ S ) S×A : ∥ξ(s, :, :) -ξ(s, :, :)∥ p ≤ α s , ∀s ∈ S} (p ∈ {1, ∞}) is convex and compact, which proves Assumption 5.Assumption 6 can be proved easily by letting Ξ s = {ξ s ∈ (∆ S ) A : ∥ξ s -ξ(s, :, :)∥ p ≤ α s } (p ∈ {1, ∞}).Then we will prove Assumption 7, that is,Ξ s = {ξ s ∈ (∆ S ) A : ∥ξ s -ξ(s, :, :)∥ p ≤ α s } (p ∈ {1, ∞})is a polyhedron. Based on Definition 1.1 and Theorem 1.26 of [9] , it is equivalent to prove that Ξ s is bounded (already proved above) and is an intersection of finitely many closed half-planes (obvious based on the definitions of ∥ • ∥ 1 and ∥ • ∥ ∞ ).We will only prove Assumption 8, since Assumption 4 can be proved in the same way.Fix any ξ ∈ Ξ and θ ∈ Θ = [-R, R] |S|×|A| . Then we select any θ * = θ * (θ) ∈ arg min θ ′ ∈Θmin ∥θ ′ -θ∥ ∞ where Θ min := arg min θ ′ ∈Θ Γ(θ ′ ) is a compact set since Γ is a continuous function.Define the following notations.• λ(δ) θ,ξ = (1 -δ)λ θ,ξ + δλ θ * ,ξ for δ ∈ [0, 1] (we select δ = 1). • Policy π (δ) θ,ξ defined as π (δ) θ,ξ (a|s) = λ (δ) θ,ξ (s,a) λ (δ) θ,ξ (s)where λ(δ) θ,ξ (s) = a ′ λ (δ) θ,ξ (s, a ′ ) (Note that λ (δ) θ,ξ (s) ≥ λ (δ) θ,ξ (s, a) ≥ λ min > 0, so λ (δ)θ,ξ (s) can be the denominator and π(δ) θ,ξ (a|s) > 0). • θ (δ)θ,ξ ∈ R |S|×A with each entry defined as follows.(θEQUATION)which is valid since π (δ) θ,ξ (a|s) > 0 and π θ (a|s) ≥ π min > 0. • U θ,ξ = {θ (δ) θ,ξ : δ ∈ [0, 1]} ⊂ R |S|×|A| . • V θ,ξ = {λ (δ) θ,ξ : δ ∈ [0, 1]} ⊂ ∆ S×A . Now, itθ,ξ = θ * . (P2): U θ,ξ ⊂ Θ = [-R, R] |S|×|A| . (P3): λ (δ) θ,ξ = λ θ (δ) θ,ξ ,ξ . (P4): The mapping θ (δ) θ,ξ → λ (δ)θ,ξ from U θ,ξ to V θ,ξ is a bijection and is Lipschitz continuous in both directions.(P1) obviously follows from Eq. (76).Note that (θ (δ) θ,ξ ) s,a defined by Eq. ( 76) is a monotone function of δ ∈ [0, 1], and (P1) implies that (θ(0) θ,ξ ) s,a = θ s,a ∈ [-R, R] and θ (1) θ,ξ = θ * s,a ∈ [-R, R]. Therefore, (θ (δ) θ,ξ ) s,a ∈ [-R, R] which proves (P2).To prove (P3), rewrite Eq. (76) as follows.(θEQUATIONwhere we denote c δ (s) := log λEQUATION.Note that for any θ ′ ∈ R |S|×|A| , we haveEQUATIONwhere (i) uses Lemma 2. Then we have(1 -γ)ρ(s ′ ) + γ s,a λ (δ) θ,ξ (s, a)p ξ (s ′ |s, a) π θ (δ) θ,ξ (a ′ |s ′ ) -λ (δ) θ,ξ (s ′ , a ′ ) (i) =π θ (δ) θ,ξ (a ′ |s ′ ) (1 -γ)ρ(s ′ ) + γ s,a λ (δ) θ,ξ (s, a)p ξ (s ′ |s, a) -λ (δ) θ,ξ (s ′ ) (ii) = δπ θ (δ) θ,ξ (a ′ |s ′ ) (1 -γ)ρ(s ′ ) + γ s,a λ θ,ξ (s, a)p ξ (s ′ |s, a) -λ θ,ξ (s ′ ) + (1 -δ)π θ (δ) θ,ξ (a ′ |s ′ ) (1 -γ)ρ(s ′ ) + γ s,a λ θ * ,ξ (s, a)p ξ (s ′ |s, a) -λ θ * ,ξ (s ′ ) (iii) = 0,where (i) uses Eq. ( 78), (ii) uses λ (δ)θ,ξ = (1 -δ)λ θ,ξ + δλ θ * ,ξ and (iii) uses the Eq. ( 79) for θ ′ ∈ {θ * , θ}. Based on Lemma 2, the equality above implies (P3).Next, we prove (P4). Note that the mapping from θ to λ(δ) θ,ξ = λ θ (δ)θ,ξ ,ξ is Lipschitz continuous based on Lemma 3. Hence, we only need to consider its reverse mapping.If λ θ * ,ξ = λ θ,ξ , then π θ * = π θ . Hence, θ ∈ Θ min := arg min θ ′ ∈Θ Γ(θ ′ ) because Γ(θ ′ ) = max ξ ′ ∈Ξ f (λ θ ′ ,ξ ′ )can be seen as a function of π θ ′ . Therefore, θ * = θ which means U θ,ξ = {θ} and V θ,ξ = {λ θ,ξ } are singletons. In this case, (P4) trivially holds.Therefore, we focus on the case where λ θ * ,ξ ̸ = λ θ,ξ . Before proving (P4), we will prove the following statement.(P5) There exists a constantL ′ > 0 such that ∥θ * -θ∥ ∞ ≤ L ′ ∥λ θ * ,ξ -λ θ,ξ ∥ ∞ for any θ ∈ Θ = [-R, R] |S|×|A| . Define θ ′ * ∈ θ ∈ R |S|×|A| such that θ ′ * s,a = θ * s,a + 1 |A| a ′ (θ s,a ′ -θ * s,a ′ ).Then it can be easily verified thatEQUATIONEQUATION)Note that π θ (a|s) = exp(θs,a)a ′ exp(θ s,a ′ ) and π θ ′ (a|s) = exp(θ ′ s,a ) a ′ exp(θ ′ s,a ′ ) , so θ ′ s,a -θ s,a = log π θ ′ (a|s) - log π θ (a|s) + u(s) where u(s) := log a ′ exp(θ ′ s,a ′ ) -log a ′ exp(θ s,a ′ ) .Then combining with Eq. ( 81), we obtain that u(s)EQUATIONwhere (i) uses Eqs. ( 73) and (80) which imply that π θ (a|s),EQUATIONs) ≥ |A|λ min for θ, θ * ∈ Θ as a result of Eq. ( 75).Based on the definition of θ ′ * , we have maxa ′ θ ′ * s,a ′ -min a ′ θ ′ * s,a ′ = max a ′ θ s,a ′ -min a ′ θ s,a ′ ≤ 2R.Therefore, for each s ∈ S, there are three cases:-R ≤ min a ′ θ ′ * s,a ′ ≤ max a ′ θ ′ * s,a ′ ≤ R, max a ′ θ ′ * s,a ′ > R and min a ′ θ ′ * s,a ′ < -R, and we can define θ ′′ ∈ R |S|×|A| as follows θ ′′ s,a =          θ ′ * s,a , -R ≤ min a ′ θ ′ * s,a ′ ≤ max a ′ θ ′ * s,a ′ ≤ R θ ′ * s,a -max a ′ θ ′ * s,a ′ + R, max a ′ θ ′ * s,a ′ > R θ ′ * s,a -min a ′ θ ′ * s,a ′ -R, min a ′ θ ′ * s,a ′ < -R .It can be easily verified that the θ ′′ defined above satisfiesθ ′′ ∈ Θ = [-R, R] |S|×|A| (since max a ′ θ ′ * s,a ′ -min a ′ θ ′ * s,a ′ ≤ 2R) and π θ ′′ = π θ ′ * = π θ * (the second = comes from Eq. ( 80)). Therefore, θ ′′ ∈ Θ min and thusEQUATIONwhere (i) uses θ ′′ ∈ Θ min and θ * ∈ arg min θ ′ ∈Θmin ∥θ ′ -θ∥ ∞ . To further obtain the upper bound of ∥θ ′′ -θ ′ * ∥ ∞ in the above inequality, we discuss the three aforementioned cases.(Case I): When -R ≤ min a ′ θ ′ * s,a ′ ≤ max a ′ θ ′ * s,a ′ ≤ R, we have θ ′′ s,a -θ ′ * s,a = 0. (Case II): When max a ′ θ ′ * s,a ′ > R, we have 0 < θ ′ * s,a -θ ′′ s,a = max a ′ θ ′ * s,a ′ -R (i) ≤ max a ′ θ ′ * s,a ′ -max a ′ θ s,a ′ ≤ ∥θ ′ * -θ∥ ∞ , where (i) uses θ ∈ Θ = [-R, R] |S|×|A| . (Case III): When min a ′ θ ′ * s,a ′ < -R, we have 0 < θ ′′ s,a -θ ′ * s,a = -min a ′ θ ′ * s,a ′ -R (i) ≤ min a ′ θ s,a ′ -min a ′ θ ′ * s,a ′ ≤ ∥θ ′ * -θ∥ ∞ , where (i) uses θ ∈ Θ = [-R, R] |S|×|A| .Summarizing the above three cases, we obtain that ∥θ ′′ -θ ′ * ∥ ∞ ≤ ∥θ ′ * -θ∥ ∞ and therefore Eq. ( 83) implies thatEQUATIONwhere (i) uses Eq. ( 82). This proves (P5).We consider Eq. ( 76) as a function of δ and take its derivative as follows.∂(θEQUATIONwhere (i) uses θ, θ * ∈ Θ = [-R, R] |S|×|A| and Eq. ( 75), (ii) uses θ, θ * ∈ Θ = [-R, R] |S|×|A| , (iii) uses Eq. (84).Therefore, for any δ, δ ′ ∈ [0, 1], we have ∥θ(δ ′ ) θ,ξ -θ (δ) θ,ξ ∥ ∞ ≤ 2(L ′ + 1) exp(2R) λ min ∥λ θ * ,ξ -λ θ,ξ ∥ ∞ |δ ′ -δ| = 2(L ′ + 1) exp(2R) λ min ∥λ (δ ′ ) θ,ξ -λ (δ)θ,ξ ∥ ∞ , which proves the statement (P4) and thus proves Assumption 8. Assumption 4 can be proved in the same way simply by replacing θ * with any θ * (ξ) ∈ arg min θ ′ ∈Θ f (λ θ ′ ,ξ ).The estimated occupancy measure ( 40) is an unbiased estimator of the following truncated occupancy measure with truncation level H λ .EQUATION) Denote λ(τ (λ) ) := λ(τ (λ) ; s, a) s,a∈S×A ∈ R |S||A| , λ (H λ ) θ,ξ := λ (H λ )θ,ξ (s, a) s,a∈S×A ∈ R |S||A| , λ θ,ξ := λ θ,ξ (s, a) s,a∈S×A ∈ R |S||A| , Then the estimation error of occupancy measure has the following upper bound.EQUATIONwhere (i) uses E∥X∥ 2 = VarX + ∥EX∥ 2 for random vector X := λ(τ (λ) ) -λ θ,ξ , (ii) uses Eqs.(1) and ( 86) and uses the fact that λ defined by Eq. ( 40) is average among the m λ i.i.d. individual estimators λ i (τEQUATIONi,h = a} for i = 1, . . . , m λ , (iii) uses VarX ≤ E∥X∥ 2 for random vector X := λ 1 (τ (λ) ) and P π θ ,p ξ (s t = s, a t = a|s 0 ∼ ρ) ∈ [0, 1], and (iv) uses 0 ≤ ∥ λ 1 (τ(λ) i ∥ 2 ≤ s,a λ 1 (τ (λ) i ; s, a) = 1 and s,a P π θ ,p ξ (s t = s, a t = a|s 0 ∼ ρ) = 1.Define the cost function as c := ∇ λ f (λ θ,ξ ). The error of estimating c by c := ∇ λ f [ λ(τ (λ) )] has the following upper bounds.EQUATIONwhere (i) uses Assumption 2 and (ii) uses Eq. (87). Also, c and c have the following norm bound based on Assumption 2.EQUATIONNote that g (θ) (τ (θ) , θ, ξ, c) defined by Eq. ( 41) (replace c with c) is the average of the following m θ i.i.d. individual stochastic gradients.EQUATION∇ θ log π θ (aEQUATIONThen it can be easily seen that gi , θ, ξ, c) defined above is an unbiased estimator of the following truncated policy gradient.EQUATIONi , θ, ξ, c) can be bounded as follows by using Eq. ( 90) and Assumption 1.EQUATIONi,t )| t h=0 ∥∇ θ log π θ (a (θ) i,h | s (θ) i,h )∥ ≤ H θ -1 t=0 (t + 1)γ t ℓ λ ℓ π θ ≤ ℓ λ ℓ π θ (1 -γ) 2 .(93) Therefore, we can prove Eq. ( 43) as follows, and Eq. ( 44) can be proved using the same logic.EQUATION∇ θ log π θ (aEQUATION] + 3 +∞ t=H θ γ t ℓ λ ℓ π θ (t + 1) 2 (iii) ≤ 3L 2 λ |S||A| 1 m λ + γ 2H λ ℓ π θ (1 -γ) 2 2 + 3 m θ ℓ λ ℓ π θ (1 -γ) 2 2 + 3 ℓ λ ℓ π θ γ H θ [1 + H θ (1 -γ)] (1 -γ) 2 2 ≤ 3ℓ 2 π θ (1 -γ) 4 L 2 λ |S||A| 1 m λ + γ 2H λ + ℓ 2 λ m θ + ℓ 2 λ [1 + H θ (1 -γ)] 2 γ 2H θ ,where (i) uses Eqs. ( 8),( 41),(92) andEQUATIONuses Eq. ( 90), Assumption 1 andEQUATIONi , θ, ξ, c)} m θ i=1 are independent, (iii) uses Eqs. (89) and (93).The policy gradient (8) is proved by Eqs. ( 5) and ( 6) of [6] . We will next prove the transition gradient (9) .Under the transition kernel p ξ and policy π θ , the probability of obtaining a certain trajectory τ t = {s h , a h } t h=0 ∪ {s t+1 } with initial state distribution ρ can be expressed as follows.P π θ ,p ξ (τ t ) = ρ(s 0 ) t h=0 π θ (a h |s h )p ξ (s h+1 |s h , a h ) .Hence, the gradient of the log of the above probability can be computed as follows.EQUATIONDenote c := ∇ λ f (λ θ,ξ ). Then the transition gradient (9) can be obtained as follows.∇ ξ f (λ θ,ξ ) = ∇ λ f (λ θ,ξ ) ⊤ ∇ ξ λ θ,ξ = s,a c(s, a)∇ ξ ∞ t=0 γ t P π θ ,p ξ (s t = s, a t = a) = ∇ ξ ∞ t=0 γ t c(s t , a t )P π θ ,p ξ (τ t )dτ t = ∞ t=0 γ t c(s t , a t )∇ ξ P π θ ,p ξ (τ t )dτ t = ∞ t=0 γ t c(s t , a t ) ∇ ξ P π θ ,p ξ (τ t ) P π θ ,p ξ (τ t ) • P π θ ,p ξ (τ t )dτ t = ∞ t=0 E τt∼Pπ θ ,p ξ γ t c(s t , a t )∇ ξ log P π θ ,p ξ (τ t ) s 0 ∼ ρ (i) = E π θ ,p ξ ∞ t=0 γ t c(s t , a t ) t h=0 ∇ ξ log p ξ (s h+1 |s h , a h ) s 0 ∼ ρwhere (i) uses Eq. ( 94).Based on Proposition 9, we define the following error terms E (ξ) j and E (θ) j (i, j ∈ {1, 2, 3, 4}) to bound the estimation errors of the stochastic gradients in lines 6, 10, 17 and 21 of Algorithm 1 respectively.EQUATIONEQUATIONThen we prove Theorem 2 in the following procedures.Step (14) of the First Original Phase Lemma 7. Suppose Assumptions 1-4 hold. Apply the projected stochastic gradient descent step (14) in Algorithm 1 to the policy optimization problem min θ∈Θ f (λ θ,ξ k ) with fixed ξ k ∈ Ξ. Select stepsize α = 1 2L θ,θ and initialization θ k,0 = θ 0 . Then the output θ k := θ k,T globally converges at the following rate for any δ ∈ [0, δ].EQUATION1 is defined in Eq. (95).Proof. For any θ k,t ∈ Θ in the update rule (14) , there exists at least one optimal policy θ * k,t ∈ arg min θ ′ ∈Θ f (λ θ ′ ,ξ k ) such that for any δ ∈ [0, δ], there exists θEQUATIONThen, we analyze the optimization progress of the stochastic gradient descent step (14) as follows.EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONwhere (i) and (iii) use L θ,θ -smoothness of f (λ •,ξ k ) based on Proposition 3, (ii) uses the update rule (14) with stepsize α = 1 2L θ,θ which implies that θ k,t+1 ∈ arg min θ∈Θ (gk,t ) ⊤ (θ -θ k,t ) + L θ,θ ∥θθ k,t ∥ 2 , (iv) uses Eq. (98) and the following inequality.∥θ (δ) k,t -θ k,t ∥ (i) ≤ℓ λ -1 λ θ (δ) k,t ,ξ k -λ θ k,t ,ξ k = ℓ λ -1 δ λ θ * k,t ,ξ k -λ θ k,t ,ξ k (ii) ≤ √ 2ℓ λ -1 δ,where (i) uses Assumption 4 and (ii) uses Lemma 4. Rearranging Eq. (99) and taking conditional expectation, we obtain thatEQUATIONwhere (i) uses Eq. ( 43) in Proposition 9 and E (θ) 1 defined in Eq. ( 95) with j = 1. Then the convergence rate (97) can be proved by iterating the above inequality as follows. EQUATIONThen, the output ξ of the first original phase has the following convergence rate.EQUATIONwhereE (ξ)2 is defined in Eq. (96) with j = 2.Proof. For any fixed ξ ∈ Ξ, define the optimal policy parameter θ * (ξ) and the optimal utility value Φ(ξ) as follows.θ * (ξ) :∈ arg minEQUATIONEQUATIONSince f (λ θ,• ) is L ξ,ξ -smooth for any θ ∈ Θ based on Proposition 3, for any (θ, ξ)∈ Θ × Ξ, f (λ θ,ξ ′ ) - L ξ,ξ2 ∥ξ ′ -ξ∥ 2 is a concave function of ξ ′ . As a result, Φ(ξ ′ ) -L ξ,ξ ∥ξ ′ -ξ∥ 2 is a L ξ,ξ -strongly concave function of ξ ′ and thus it has the following unique maximizer.EQUATIONAccordingly, we define the following Moreau envelope function (repeat Eq. ( 18)).Φ(ξ) := maxEQUATION)Based on Lemma 3.6 of [31] , Φ is L ξ,ξ -smooth withEQUATIONSimilar to Lemma D.3 of [31] , we obtain the following ascent property of the above envelope function Φ for any k = 0, 1, . . . , K -1.EQUATIONwhere (i) uses Eqs. ( 15) and ( 105), (ii) holds for any τ k > 0 whose value is to be determined later, (iii) uses contraction property of projection and ξ * (ξ k ) ∈ Ξ, (iv) uses Propositions 3-9 and the error termE (ξ)2 defined in Eq. ( 96), (v) uses Eqs. ( 100) and ( 103), (vi) uses Eqs. (104)-(105) which imply that Φ(ξ k ) = Φ[ξ * (ξ k )] -L ξ,ξ ∥ξ * (ξ k ) -ξ k ∥ 2 ≥ Φ(ξ k ), (vii) uses Eq. (106). Taking unconditional expectation of Eq. ( 107) and telescoping it over k = 0, 1, . . . , K -EQUATION≤ 1 4 , we obtain thatβ 8 K-1 k=0 E ∇ Φ(ξ k ) 2 ≤E Φ(ξ K ) -Φ(ξ 0 ) + 5K 4 L ξ,ξ β 2 ℓ 2 ξ + 5K 2 L ξ,ξ βϵ 0 + KL ξ,ξ β 2 1 + 2 βL ξ,ξ E (ξ) 2 (i) ≤f * -E Φ(ξ 0 ) + 5K 4 L ξ,ξ β 2 ℓ 2 ξ + 5K 2 L ξ,ξ βϵ 0 + 5KβE (ξ) 2 2 ,where (i) uses the following range of Φ(ξ) (defined in Eq. ( 105)) that holds for any ξ ∈ Ξ.EQUATIONAs a result,EQUATIONNext we focus on the second corrected phase which aims to solve the following minimax optimization problem (repeat Eq. ( 19)).EQUATION)where ξ is obtained from {ξ k } K-1 k=0 uniformly at random in the first original phase. Based on Proposition 3, it can be easily verified that f has the following smoothness properties and f (θ, •) is L ξ,ξ -strongly concave.EQUATIONEQUATIONNext, we 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 (θ k , •).EQUATION)The optimization progress of each step of Eq. ( 16) for k = K, K + 1, . . . , K + K ′ -1 can be bounded as follows.EQUATIONwhere (i) uses Eq. ( 16), ξ * k ∈ Ξ and contraction property of projection, (ii) holds for any c k > 0 whose value will be assigned later, (iii) uses ∇ ξ f (θ k , ξ * k ) = 0 and the definition of f in Eq. ( 110), (iv) uses Proposition 9, the error term E (ξ) 3 defined in Eq. (96) as well as the 3L ξ,ξ -smoothness and L ξ,ξ -strongly concavity of f (θ k , •) (see Eq. ( 112)), and (v) uses a = 1 9L ξ,ξ and c k = 1 17 . Iterating the unconditional expectation of Eq. ( 114) over t = 0, 1, . . . , T ′ -1, we obtain thatEQUATIONEQUATIONEQUATION)where the second ≤ denotes D Ξ := sup ξ,ξ ′ ∈Ξ ∥ξ ′ -ξ∥ as the diameter of the compact set Ξ.N.4 Convergence Rate of E[∥G (θ) b (θ k , ξ k )∥ 2 ]Since f (θ, •) is strongly concave, it has unique maximizer ξ * (θ) and the corresponding function value Ψ(θ) defined as follows.EQUATIONEQUATIONFurthermore, since f (θ, •) is L ξ,ξ -strongly concave and f has the smoothness properties (111) and (112), we can easily obtain that ξ * (θ) is (L ξ,θ /L ξ,ξ )-Lipschitz and Ψ is L := L θ,θ + L θ,ξ L ξ,θ /L ξ,ξsmooth with the following gradient, following the proof of Lemma 4.EQUATIONNote that for any k = K, . . . , K + K ′ -1, the projected stochastic gradient ascent step (17) satisfies∥g (θ) k ∥ = 1 b θ k -θ k -bg (θ) k (i) ≥ 1 b proj Θ θ k -bg (θ) k -θ k -bg (θ) k (ii) = 1 b ∥θ k+1 -θ k + bg (θ) k ∥,where (i) uses θ k ∈ Θ and the definition of projection and (ii) uses the stochastic gradient descent step (17) . The above inequality implies that (gEQUATION)Then, we analyze the optimization progress of the potential function (117) along the projected stochastic gradient descent step (17) as follows.E Ψ(θ k+1 )EQUATIONEQUATIONwhere (i) uses the L := L θ,θ + L θ,ξ L ξ,θ /L ξ,ξ -smoothness of Ψ, (ii) uses Eq. ( 118), (iii) uses Cauchy-Schwartz inequality and Eq. ( 119), (iv) uses b = 1 4 L , Propositions 3-9 and the error termE (θ)4 defined by Eq. ( 95), (v) uses Eq. ( 115). Denote G(θ) b (θ k , ξ k ) = 1 b θ k -proj Θ [θ k -b∇ θ f (λ θ k ,ξ k )] for k = K, . . . , K + K ′ -1.Its norm can be bounded as follows.EQUATIONEQUATIONwhere (i) uses Eqs. ( 17) and (120) as well as EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONwhere (i) uses Eqs. ( 116)-( 117) and selects the stepsize b = 1 4 L , (ii) uses Eq. (110), and (iii) uses f * := min θ∈Θ max ξ∈Ξ f (λ θ,ξ ) and Γ(θ) := max ξ∈Ξ f (λ θ,ξ ).EQUATIONwhere (i) uses Eq. ( 104), (ii) uses Eq. ( 113), (iii) uses ∇ ξ f (θ k , ξ * k ) = 0 at the optimal variable ξ * k defined by Eq. ( 113) and 3L ξ,ξ -smoothness of f (θ, •) implied by Eq. (112). On the other hand, since f (θ, •) is L ξ,ξ -strongly concave, ψ is L ξ,ξ -strongly concave. Hence,EQUATIONwhere (i) uses ∇ψ ξ * ( ξ) = 0 at the unique optimizer ξ * ( ξ) = arg max ξ∈Ξ ψ(ξ) (see Eq. ( 104)). Then, we haveEQUATIONwhere (i) uses proj Ξ ξ * k + a∇ ξ f (θ k , ξ * k ) -ξ * k = 0 based on Eq. ( 113), (ii) uses the definition of f given by Eq. ( 110), (iii) uses 3L ξ,ξ -smoothness of f (θ k , •) based on Eq. ( 112), (iv) uses Eqs. ( 106), ( 123) and ( 124), (v) uses Eq. (110). Taking expectation of the above Eq. ( 125) and averaging it over k = K, . . . , K + K ′ -1, we obtain the convergence rate of E[∥GEQUATION16 17EQUATIONEQUATIONwhere (i) uses Eqs. ( 20), ( 101) and ( 115), (ii) uses Eq. ( 122), (iii) uses ℓ θ , ℓ ξ = O[(1 -γ) -2 ], L θ,ξ , L ξ,ξ , L = O[(1 -γ) -3 ] based on Proposition 3 and selects stepsizes a = 1 9L ξ,ξ = O[(1 -γ) 3 ], b = 1 4 L = O[(1 -γ) 3 ], β = 1 2L ξ,ξ √ K = O[K -1/2 (1 -γ) 3 ].Denote δ = min δ,ϵ 2 5760L ξ,ξ L θ,θ ℓ 2 λ -1 , 1 2 = O[(1 -γ) 6 ϵ 2 ].Then we select the following hyperparameter values.EQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONEQUATIONSubstituting the above hyperparameter choices into Eqs. ( 95) and (96), we haveEQUATIONEQUATIONEQUATIONEQUATION. Lemma 7 implies that for any fixed ξ ∈ Ξ, θ T ′ obtained from the update rule ( 14) satisfiesEQUATIONEQUATIONwhere (i) uses Lemma 7, (ii) uses Eqs. ( 128), (151) and δ ≤ϵ 2 5760L ξ,ξ L θ,θ ℓ 2 λ -1 , (iii) uses log(1 -δ) ≤ -δ for δ ∈ [0, 1/2]. Hence, the above inequality implies that ϵ 0 defined by Lemma 8 satisfiesϵ 0 ≤ ϵ 2 480L ξ,ξ .As a result, we can prove that E ∥G (ξ) a (θ k , ξ k )∥ 2 ≤ ϵ 2 and E ∥G (θ) b (θ k , ξ k )∥ 2 ≤ ϵ 2 by substituting ϵ 0 ≤ ϵ 2KT (m (1) λ H (1) λ + m (1) θ H (1) θ ) + K(m (2) λ H (2) λ + m (2) ξ H (2) ξ ) + K ′ T ′ (mNote that σ k = 2β k ℓ θ , so by the definition ofEQUATIONHence,EQUATIONwhere (i) uses Eq. ( 10) in Proposition 3 which implies that f (λ •,ξ ) is ℓ θ -Lipschitz continuous, (ii) uses Eq. ( 155) and the update rule (22) with ∥d k ∥ = 1. Eqs. ( 155) and ( 156) respectively imply the following two equations.EQUATIONΓ(θ k+1 ) = maxEQUATIONwhere ξ * k+1 ∈ arg max ξ ′ ∈Ξ k f (λ θ k+1 ,ξ ′ ).Based on Proposition 7, there exists a unit descent direction d k (∥ d k ∥ = 1) such that 0 < f (λ θ k ,ξ )-minθ ′ ∈Θ Γ(θ ′ ) ≤ f (λ θ k ,ξ )-f (λ θ * ,ξ ) ≤ - √ 2ℓ λ -1 ∇ θ f (λ θ k ,ξ ) ⊤ d k + , ∀ξ ∈ Ξ k (159)Then we have EQUATIONEQUATIONwhere (i) uses Eq. ( 161) and the update rule (155) with ∥d k ∥ = 1.(Case 2):If A k (d ′ k ) < 0, then since ∥d ′ k ∥ ≤ 1, d k = d ′ k /∥d ′ k ∥ satisfies A k (d k ) ≤ A k (d ′ k ) < 0.Hence, Eq. (160) implies thatEQUATION)As a result, we bound the one-step optimization progress of Γ(θ k ) as follows.Γ(θ k+1 ) -Γ(θ k )(i) ≤f (λ θ k+1 ,ξ * k+1 ) -f (λ θ k ,ξ * k+1 ) (ii) ≤ ∇ θ f (λ θ k ,ξ * k+1 ) ⊤ (θ k+1 -θ k ) + L θ,θ 2 ∥θ k+1 -θ k ∥ 2 (iii) = β k ∇ θ f (λ θ k ,ξ * k+1 ) ⊤ d k + L θ,θ 2 β 2 k (iv) ≤ β k A k (d k ) + L θ,θ 2 β 2 k (v) ≤ β k ϵ k + L θ,θ β k 2 + √ 2β k ℓ θ ℓ λ -1 - β k √ 2ℓ λ -1 Γ(θ k ) -min θ ′ ∈Θ Γ(θ ′ ) ,where (i) uses Eqs. (157) and ( 158), (ii) uses L θ,θ -smoothness of f (λ •,ξ ) based on Proposition 3, (iii) uses the update rule (22) with ∥d k ∥ = 1, (iv) uses ξ * k+1 ∈ Ξ k and the definition of A k in Eq. ( 23), (v) uses Eq. (163). Rearranging the above inequality yields that Γ(θ k+1 ) -minEQUATIONwhere (i) usesβ k = 2 √ 2ℓ λ -1 k+2 .O.2 Obtain the Convergence Rate (25)(Case 1): If A k (d ′ k ) < 0 for all k = 0, 1, . . . , K -1, then we iterate Eq. ( 164) over k = 0, 1, . . . , K -1 as follows.EQUATION(Case 2): If A K-1 (d K-1 ) ≥ 0, then Eq. ( 162) holds for k = K -1, i.e., Γ(θ K ) -minEQUATION)(Case 3): If A K ′ -1 (d K ′ -1 ) ≥ 0 for some K ′ ∈ {1, . . . , K -1} while A k (d k ) < 0 for all k = K ′ , . . . , K -1, then we iterate Eq. ( 164) over k = K ′ , . . . , K -1 as follows.Γ(θ K ) -minEQUATIONwhere (i) applies Eq. (162) to k = K ′ and (ii) usesβ k = 2 √ 2ℓ λ -1k+2 . In sum, the convergence rate (25) holds in all the above three cases.Note that A k (d) := max ξ∈Ξ k ∇ θ f (λ θ k ,ξ ) ⊤ d defined by Eq. ( 23) is convex and ℓ θ -Lipschitz continuous. Hence, the best direction d k ∈ arg max d∈{d k,t :0≤t≤T k } A k (d) obtained from the subgradient method (28) converge at the following rate [11] .A k (d k ) -min d∈B1 A k (d) (i) ≤ ∥d k,0 -d * k ∥ 2 + ℓ 2 θ T α 2 2T α (ii) ≤ 4 + 4 24ℓ λ -1 ϵ -1 = ϵ 3ℓ λ -1, where (i) denotes d * k ∈ arg max d∈B1 A k (d), (ii) uses T =36ℓ 2 λ -1 ℓ 2 θ ϵ 2 = O[(1 -γ) -4 ϵ -2 ], α = ϵ 3ℓ λ -1 ℓ 2 θand ∥d k,0 ∥, ∥d * k ∥ ≤ 1. Hence, the accuracyϵ k = ϵ 3ℓ λ -1 is achieved in Algorithm 2. Substituting ϵ k = ϵ 3ℓ λ -1 , K = 8ℓ λ -1 ϵ (ℓ λ -1 L θ,θ + 2 √ 2ℓ θ ) = O[(1 -γ) -3 ϵ -1] into the convergence rate (25), we obtain that ] gradient descent updates to the policy gradient descent updates (22) .Γ(θ K ) -min θ ′ ∈Θ Γ(θ ′ ) ≤ √ 2ℓ λ -1 max 1≤k≤K ϵ k + 4ℓ λ -1 K + 1 (ℓ λ -1 L θ,θ + 2 √ 2ℓ θ ) ≤ ϵ.• Examples of negative societal impacts include potential malicious or unintended uses (e.g., disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations. • The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point 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 or 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 a system learns from feedback over time, improving the efficiency and accessibility of ML).38th Conference on Neural Information Processing Systems (NeurIPS 2024).The convergence rate of ∥∇ Φ( ξ)∥ is proved in[31] when f (λ θ,ξ ) is a convex function of θ, and will be proved in Appendix N.2 for our Theoremwhen f (λ) is convex.∇1 f [θ, ξ * (θ)] and ∇1f (λ θ, ξ * (θ) ) denote gradients with respect to only the first input argument θ. 


Decision: 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.

Reviews: review: paper_summary: paper_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.
strength_weakness: strength_weakness: My main concern is about the motivation, interpretation of the results, along with potential tightness results. Please see question section.
questions: 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? 

2. 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).

3. 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: limitations: N/A
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- 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.

- 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.

- 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.
questions: 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.
- $\ell_{\lambda^{-1}}$: please provide an explicit example of this constant and its dependence on |S| and |A|
- Line 230: Inversible -> Invertible
limitations: limitations: The authors touched upon the limitations of theoretical complexity
paper_summary: paper_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.
strength_weakness: strength_weakness: - 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.

- The numerical experiments should be part of the main article as they add a lot to the theoretical results.

- The results are very technical and some explanations (for example for the main theorems) could be beneficial to the readers.
questions: 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?


Typos and misc:
- 134: $\quad$ before $,$
- 309: $\epsilon_k$ only defined in Algorithm
limitations: 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.
paper_summary: paper_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).
strength_weakness: strength_weakness: 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.

Here are some further points:
- 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.
- 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.
- 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, ...).
- 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).
questions: 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. 
- 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?
- 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.
- 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: 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. 

Nonetheless, 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.

Comments: title: Thank Reviewer nGSn for your appreciation
Thanks
Thank Reviewer joNT very much
A better answer to Reviewer iNNQ's Q3
Complexity Result Comparison for Reviewer joNT
Thank Reviewer 7fYr very much
Thanks, I will raise my score.
The 1 example for Reviewer 7fYr's Q5
Authors' response to Q3 (2)
Answer 2
Thanks & further comments
Author Response to Reviewer 7fYr (3)
Author Response to Reviewer 7fYr (2)
About Reviewer joNT's summary
Author Response to Reviewer iNNQ (2)
comment: Thank Reviewer nGSn for your appreciation.

Best regards,

Authors
Thanks for the authors' response. It addressed most of my concerns, and I believe the paper meets the acceptance threshold.
Thank you for your response. I’ll keep my score.
Hello, Reviewer joNT,

Thank you very much.
Best regards,

Authors
Thank you for your response, I have increased my score accordingly.
Dear Reviewer iNNQ, 

Our above answer to your Q3 gives examples for each assumption. The combination of the following policy, transition kernel, ambiguity set and utility function satisfy all the assumptions (Assumptions 1-8).

$\bullet$ Softmax policy: $\pi _ {\theta}(a|s)=\frac{\exp(\theta _ {s,a})}{\sum _ {a'}\exp(\theta _ {s,a'})}, \theta\in\Theta$, where the range $\Theta\subseteq[-R,R]^{|\mathcal{S}|\times|\mathcal{A}|}$ for some constant $R>0$ to prevent $\pi _ {\theta}(a|s)$ from approaching 0. 

$\bullet$ Directly parameterized transition kernel: $p _ {\xi}(s'|s,a)=\xi _ {s,a,s'}$. 

$\bullet$ s-rectangular $L^1$ ambiguity set: $\Xi\overset{\rm def}{=}${$\xi:||\xi(s,:,:)-\xi^0(s,:,:)||_1\le \alpha_s, \forall s$}, where the fixed nominal kernel $\xi^0$ satisfies $\xi^0(s,a,s')>\alpha_s, \forall s,a,s'$ to prevent $\xi(s,a,s')$ from approaching 0. 

$\bullet$ Convex utility function for pure exploration [1]: $f(\lambda)=\sum_s \lambda(s)\log\lambda(s)$ where $\lambda(s)\overset{\rm def}{=}\sum_a\lambda(s,a)$. The inital state distribution $\rho$ satisfies $\rho(s)>0, \forall s$ to prevent $\lambda(s)$ from approaching 0. 

[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.
We compare our complexity results for robust RL with general utility vs. the state-of-the-art complexity results for *robust constrained RL (RC-RL)* and *entropy regularized robust RL (ER-RL)* as follows. For fair comparison, we focus on policy gradient methods and leave aside the value iteration [1-2] and policy iteration [2] methods of ER-RL, since they directly leverage the Bellman equation for linear utility function $f$ that does not hold for general utility function $f$. 

(1) To achieve an $\epsilon$-global optimal point for non-stochastic setting, our Algorithm 2 takes $KT=\mathcal{O}(\epsilon^{-3})$ iterations based on our Corollary 1, while ER-RL takes $\mathcal{O}(\epsilon^{-3}\log\epsilon^{-1})$ iterations [3], and there is no global convergence result yet for RC-RL to our knowledge. 

(2) To achieve an $\epsilon$-stationary point for stochastic setting, our Algorithm 1 uses $\mathcal{O}(\epsilon^{-10})$ samples, while to our knowledge, ER-RL has no gradient convergence results, and the only available complexity result for RC-RL is $\mathcal{O}(\epsilon^{-14})$ in Remark 1 at the end of page 27 of [4]. 

**As a result, our complexity results either outperform those of ER-RL and RC-RL, or even fill in their blanks in complexity results.** 

[1] 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).

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

[3] Chen, Z. and Huang, H. (2024). Accelerated Policy Gradient for s-rectangular Robust MDPs with Large State Spaces. In Proceedings of the International Conference on Machine Learning (ICML).

[4] Wang, Y., Miao F., and Zou, S. (2022). Robust constrained reinforcement learning. ArXiv:2209.06866.
Thank you for your response. 

I understand that robust and non-robust approaches have different objective functions in the optimization formulation. Still, one driving motivation for using robust approaches is to achieve better performance in the face of the sim-to-real gap because the robust approach avoids overfitting (see e.g. introduction and fig. 5 of [1] for static stochastic programming setting, and fig. 1 of [2] for offline RL setting). 

I also agree that robust constrained RL and robust entropy-regularized RL can be viewed as a special case of robust RL with general utility. What remains unclear to me is e.g. the performance of existing robust constrained RL approaches against your robust RL with general utility algorithms on the same test problems. Eventually, we want to solve specific cases and I would argue that it is worthwhile to show that your more general algorithm provides superior results than more tailored algorithms.

[1] Mohajerin Esfahani, Peyman, and Daniel Kuhn. "Data-driven distributionally robust optimization using the Wasserstein metric: Performance guarantees and tractable reformulations." Mathematical Programming 171.1 (2018): 115-166.

[2] Shi, Laixi, and Yuejie Chi. "Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity." Journal of Machine Learning Research 25.200 (2024): 1-91.
Thank you very much, Reviewer 7fYr.

Yes, It is possible to explicitly keep track of all constants that appear in the algorithmic choices needed for Theorem 2, i.e., $c_1,\cdots, c_6$ in our initial response. We are conducting the change. 

Best regards,
Authors
Thank you very much for the clarification, my major concerns (flaws in the proofs, statement of theorem, possible empty result) have been resolved I will raise my score to 7.

One last comment. When you rewrite the proof for the constants, it is perhaps possible to explicitly keep track of all constants that appear in the algorithmic choices needed for Theorem 2? I had the impression when checking if your modification looks right. If so you should do it (as it is the theorem could not be used even if I ignore the huge powers) but I leave it to you.
The combination of the following policy, transition kernel, ambiguity set and utility function satisfy all the assumptions (Assumptions 1-8) of Theorems 2, 3 and Proposition 3, 4, 5.

$\bullet$ Softmax policy: $\pi _ {\theta}(a|s)=\frac{\exp(\theta _ {s,a})}{\sum _ {a'}\exp(\theta _ {s,a'})}, \theta\in\Theta$, where the range $\Theta\subseteq[-R,R]^{|\mathcal{S}|\times|\mathcal{A}|}$ for some constant $R>0$ to prevent $\pi _ {\theta}(a|s)$ from approaching 0. 

$\bullet$ Directly parameterized transition kernel: $p _ {\xi}(s'|s,a)=\xi _ {s,a,s'}$. 

$\bullet$ s-rectangular $L^1$ ambiguity set: $\Xi\overset{\rm def}{=}${$\xi:||\xi(s,:,:)-\xi^0(s,:,:)||_1\le \alpha_s, \forall s$}, where the fixed nominal kernel $\xi^0$ satisfies $\xi^0(s,a,s')>\alpha_s, \forall s,a,s'$ to prevent $\xi(s,a,s')$ from approaching 0. 

$\bullet$ Convex utility function for pure exploration [1]: $f(\lambda)=\sum_s \lambda(s)\log\lambda(s)$ where $\lambda(s)\overset{\rm def}{=}\sum_a\lambda(s,a)$. The inital state distribution $\rho$ satisfies $\rho(s)>0, \forall s$ to prevent $\lambda(s)$ from approaching 0. 

[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.
Q3: We replaced the named citations in these paragraphs with numbered citations as follows. 

Intro to robust RL at line 97:

Robust RL is designed to learn a policy that is robust to perturbation of environmental factors. Usually robust RL is NP-hard [43], but becomes tractable for ambiguity sets that is (s, a)-rectangular [33, 18, 43, 41, 28, 54] or s-rectangular [43, 40, 22, 25]. Methods to solve robust RL include value iteration [33, 18, 43, 14, 24], policy iteration [18, 4, 23] and policy gradient [28, 41, 54, 40, 25, 16, 27]. 

Under Assumption 3:

Robust RL with convex utility subsumes three important special cases, the commonly used convex RL problem [52 , 49 , 6] with fixed $\xi$, the standard robust RL [33, 18, 43, 40] with linear utility function $f$, and the standard RL [39] with linear utility function f and fixed $\xi$. Convex RL can be applied to maximum-entropy exploration [17, 52, 49, 12, 6], constrained RL [52, 49, 12] and demonstration learning [52, 49].
Q5: I fear you must be more specific. Which policies/MDPs do satisfy ALL assumptions of your Thm 2, 3, Prop 3, 4, 5. Not only for the review process, that must be integral part of the paper to justify the statements are not empty. I am satisfied if I get one precise example as an answer.

Q7: Not for this revision but for future work you might want to have a loot (for instance at)

Kaiqing Zhang, Alec Koppel, Hao Zhu, and Tamer Ba¸sar. “Global convergence of policy gradient methods to (almost) locally optimal policies”. SIAM Journal on Control and Optimization, 2020.

It is so obvious how to obtain unbiased gradient estimators that it is amazing how many people just do truncation.
Thanks for going through your proof again! 
I strongly disagree on the opinion that sloppy work of others justifies sloppy work of oneself. Good ML papers have clean statements, clean proofs, and only use the O-notation in text or tables for easy comparison. I am happy the way you used the O-notation is much stronger than what the O-notation really is. Please work properly to keep the ML community sound. It might be useful to familiarise yourself with standard notation, https://en.wikipedia.org/wiki/Big_O_notation. Otherwise sooner or later this will result in trouble once good and bad use of standard notation is mixed.

The way you formulate in the rebuttal the constants would likely depend on $\epsilon$ as you suggest to chose the constants in the last step where you aim to achieve $\epsilon^2$ upper bound. I checked your proof and it seems ok, you can already choose the constants in step 3 without dependence on the target $\epsilon^2$. I think there are more constants to chose carefully as you say so a careful modification touches more than 1 page, but that's not the point. I am fine with your improvement and will improve the score. There were enough reviewers that hopefully checked these details as well.

Q3: As an example, have a look at the text below Assumption 3. Nobody is going to read that, the overview is extremely wide. Similarly the intro to robust RL at line 97. I would suggest to replace this paragraph by text and collect some citations without names to safe a lot of space. I certainly do not decrease/increase my score for these matters of taste.
**Q10:** 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? 

**A:** Good question and suggestion. Our simulation does not exactly follow the theoretical hyperparameter choices and assumptions. We will explain this in our revision. 

**About Summary:** Our work not only provides Algorithm 1 with gradient convergence results, but also Algorithm 2 with **global** convergence results.
**Q5:** 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, ...). 

**A:** Thank you for your suggestion. In the revised paper, we will add the following practical examples for the assumptions. 

Assumption 1 covers popular policy parameterizations including softmax policy $\pi_{\theta}(a|s)=\frac{\exp(\theta_{s,a})}{\sum_{a'}\exp(\theta_{s,a'})}$ [1] and log-linear policy $\pi_{\theta}(a|s)=\frac{\exp(\theta\cdot\phi_{s,a})}{\sum_{a'}\exp(\theta\cdot\phi_{s,a'})}$ [1], as well as popular transition kernels including direct parameterization $p_{\xi}(s'|s,a)=\xi _ {s,a,s'}$ [2,3] and linear parameterization $p_{\xi}(s'|s,a)=\xi\cdot\phi_{s,a,s'}$ [4,5] when $\Xi$ is located away from 0, i.e., $\inf_{s,a,s',\xi\in\Xi}p_{\xi}(s'|s,a)\ge p_{\min}$ for a constant $p_{\min}>0$. Assumptions 2-3 cover the three convex utility examples in Section 2 of [6], including MDP with Constraints, pure exploration, and learning to mimic a demonstration. Assumptions 4 and 8 are similar and cover direct policy parameterization $\pi_{\theta}(a|s)=\theta _ {s,a}$, since it has been proved that direct policy parameterization satisfies Assumption 4.1 of [6] which implies Assumptions 4 and 8. Assumptions 5-7 cover $s$-rectangular $L_1$ and $L_{\infty}$ ambiguity sets (defined as $\Xi=\{\xi:\|\xi(s,:,:)-\xi^0(s,:,:)\| _ p\le \alpha_s\}$ for $p\in\{1,\infty\}$ respectively using direct kernel parameterization $p_{\xi}(s'|s,a)=\xi_{s,a,s'}$), which are very popular in robust RL [7,8]. 

[1] Agarwal, Alekh, et al. "On the theory of policy gradient methods: Optimality, approximation, and distribution shift." Journal of Machine Learning Research 22.98 (2021): 1-76. 

[2] Kumar, Navdeep, et al. "Policy gradient for rectangular robust markov decision processes." Advances in Neural Information Processing Systems (2023).

[3] Behzadian, Bahram, Marek Petrik, and Chin Pang Ho. "Fast Algorithms for $L_\infty$-constrained S-rectangular Robust MDPs." Advances in Neural Information Processing Systems (2021).

[4] Ayoub, Alex, et al. "Model-based reinforcement learning with value-targeted regression." International Conference on Machine Learning. PMLR, 2020.

[5] Zhang, Junkai, Weitong Zhang, and Quanquan Gu. "Optimal horizon-free reward-free exploration for linear mixture mdps." International Conference on Machine Learning. PMLR, 2023.

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

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

[8] 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. 

**Q6:** 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). 

**A:** Thank you for your suggestion. Yes, you are right. These theoretical and conservatively large hyperparameter choices are not necessarily needed in practical implementation, so the hyperparameters in our simulation are obtained by fine-tuning not theory. We will add this explanation in the revision. 

**Q7:** 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.

**A:** Thank you for your suggestion. All the robust RL with general utility works we found either only provide true gradients or provide gradient estimators with bias which goes to 0 as the truncation level $H\to+\infty$. We select such a gradient estimator with sufficiently large $H$ to bound the bias. 

**Q8:** About Assumption 1 for p, 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? 

**A:** Thank you for your suggestion. See our answer to your Q5. 

**Q9:** 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.

**A:** Good question and suggestion. See our answer to your Q5.
The properties mentioned in Reviewer joNT's summary belong to two algorithms respectively. 

Algorithm 1: stochastic gradient descent with gradient sampling subroutines, general uncertainty set, gradient convergence. 

Algorithm 2: polyhedral s-rectangular uncertainty set, global convergence.
**Q3:** 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? 

**A:** Thank you for your suggestion. In the revised paper, we will add the following practical examples for the assumptions. 

Assumption 1 covers popular policy parameterizations including softmax policy $\pi_{\theta}(a|s)=\frac{\exp(\theta_{s,a})}{\sum_{a'}\exp(\theta_{s,a'})}$ [6] and log-linear policy $\pi_{\theta}(a|s)=\frac{\exp(\theta\cdot\phi_{s,a})}{\sum_{a'}\exp(\theta\cdot\phi_{s,a'})}$ [6], as well as popular transition kernels including direct parameterization $p_{\xi}(s'|s,a)=\xi_{s,a,s'}$ [7,8] and linear parameterization $p_{\xi}(s'|s,a)=\xi\cdot\phi_{s,a,s'}$ [9,10] when $\Xi$ is located away from 0, i.e., $\inf_{s,a,s',\xi\in\Xi}p_{\xi}(s'|s,a)\ge p_{\min}$ for a constant $p_{\min}>0$. Assumptions 2-3 cover all the three convex utilities listed in our answer to your Q2. Assumptions 4 and 8 are similar and cover direct policy parameterization $\pi_{\theta}(a|s)=\theta_{s,a}$ (Actually, it has also been proved to satisfy Assumption 4.1 of [1] which implies Assumptions 4 and 8). Assumptions 5-7 cover $s$-rectangular $L_1$ and $L_{\infty}$ ambiguity sets (defined as $\Xi=\{\xi:\|\xi(s,:,:)-\xi^0(s,:,:)\| _ p\le \alpha_s\}$ for $p\in\{1,\infty\}$ respectively using direct kernel parameterization $p_{\xi}(s'|s,a)=\xi_{s,a,s'}$), which are very popular in robust RL [3,4]. 

We are not sure about the tightness of our results because the complexity lower bounds are unknown for our proposed robust RL with general utility. However, as mentioned in our conclusion, our gradient complexities may still be improved in the future, compared with the state-of-the-art gradient complexities (Lin et al., 2020; Pethick et al., 2023) for minimax optimization. 

[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] Agarwal, Alekh, et al. "On the theory of policy gradient methods: Optimality, approximation, and distribution shift." Journal of Machine Learning Research 22.98 (2021): 1-76. 

[7] Kumar, Navdeep, et al. "Policy gradient for rectangular robust markov decision processes." Advances in Neural Information Processing Systems (2023).

[8] Behzadian, Bahram, Marek Petrik, and Chin Pang Ho. "Fast Algorithms for $L_\infty$-constrained S-rectangular Robust MDPs." Advances in Neural Information Processing Systems (2021).

[9] Ayoub, Alex, et al. "Model-based reinforcement learning with value-targeted regression." International Conference on Machine Learning. PMLR, 2020.

[10] Zhang, Junkai, Weitong Zhang, and Quanquan Gu. "Optimal horizon-free reward-free exploration for linear mixture mdps." International Conference on Machine Learning. PMLR, 2023.