Soft Robust MDPs and Risk-Sensitive MDPs: Equivalence, Policy Gradient, and Sample Complexity
Authors: Runyu Zhang
Yang Hu
Na Li
Venue: ICLR 2024 poster (2024)
Keywords: risk-sensitive reinforcement learning
robust Markov Decision Processes
Primary area: reinforcement learning
TL;DR: We propose a new formulation of risk-sensitive MDP and establish its equivalence with the (soft) robust MDP. Building upon the equivalence, we analyzed the policy gradient and offline sample complexity of the two problems.

Abstract: Robust Markov Decision Processes (MDPs) and risk-sensitive MDPs are both powerful tools for making decisions in the presence of uncertainties. Previous efforts have aimed to establish their connections, revealing equivalences in specific formulations. This paper introduces a new formulation for risk-sensitive MDPs, which assesses risk in a slightly different manner compared to the classical Markov risk measure [Ruszczy ́nski 2010], and establishes its equivalence with a class of soft robust MDP (RMDP) problems, including the standard RMDP as a special case. Leveraging this equivalence, we further derive the policy gradient theorem for both problems, proving gradient domination and global convergence of the exact policy gradient method under the tabular setting with direct parameterization. This forms a sharp contrast to the Markov risk measure, known to be potentially non-gradient-dominant [Huang et al. 2021]. We also propose a sample-based offline learning algorithm, namely the robust fitted-Z iteration (RFZI), for a specific soft RMDP problem with a KL-divergence regularization term (or equivalently the risk-sensitive MDP with an entropy risk measure). We showcase its streamlined
design and less stringent assumptions due to the equivalence and analyze its sample complexity.

Published as a conference paper at ICLR 2024
SOFT ROBUST MDPs AND RISK-SENSITIVE MDPs: EQUIVALENCE, POLICY GRADIENT, AND SAMPLE COM- PLEXITY
Runyu (Cathy) Zhang Harvard University
Yang Hu
Na Li
Harvard University yanghuêg. ha harvard.edd
Harvard University na 1i @seas. harvard.
runyuzhang@ fas ha harvarddedd
ABSTRACT
Robust Markov Decision Processes (MDPs) and risk-sensitive MDPs are both powerful tools for making decisions in the presence of uncertainties. Previous efforts have aimed to establish their connections, revealing equivalences in specific formulations. This paper introduces new formulation for risk-sensitive MDPs, which assesses risk in a slightly different manner compared to the classical Markov risk measure (71], and establishes its equivalence with class of soft robust MDP (RMDP) problems, including the standard RMDP as a special case. Leveraging this equivalence, further derive the policy gradient theorem for both problems, prov- ing gradient domination and global convergence of the exact policy gradient method under the tabular setting with direct parameterization. This forms sharp contrast to the Markov risk measure, known to be potentially non-gradient-dominant (39] We also propose a sample-based offline learning algorithm, namely the robust fitted-Z iteration (RFZI), for specific soft RMDP problem with a Kl--divergence regularization term (or equivalently the iiskssensitive MDP with an entropy risk measure). We showcase its streamlined design and less stringent assumptions due to the equivalence and analyze its sample complexity.
INTRODUCTION
Making decisions amidst uncertainty presents fundamental challenge cutting across diverse domains, including finance 32 80), engineering [45] 744, and robotics [88] etc. Within these realms, decisions carry consequences that depend only on expected rewards but also the level of uncertainty and associated risks. Addressing this challenge necessitates approaches such as robust, and risk-sensitive These approaches explicitly incorporate uncertainty and aim find policies that perform well across a spectrum of scenarios and adeptly strike a balance between expected gains and potential risks.
For robust decision mmaking in a dynamic environment, the robust Markov Decision Process (RMDP) popular framework. RMDPss model the environment Markov decision process, seeking policies that excel across various potential models. This involves solving a max-min problem, optimizing an objective function that considers the policy's worst-case performance across all models within a defined uncertainty set. The RMDP framework was introduced by [1 57], spurring research into efficient planning algorithms when the model is given 34
96
93 100, 56].There are also
21 which leverage convex formulation and regularization techniques to tackle robustness. In cases of unknown models recent efforts have designed reinforcement learning (RL) algorithms with guarantees, but most model-based for tabular cases, i.e., requiring an empirical estimation of the probability transition model [51 63 105 99 98 77). thereby impeding their applicability large state spaces. Some works focus on the model-free setting and employ linear function approximation for handling large state spaces [85] 70 4. However, these approaches provide only asymptotic guarantees and rely on approximated robust dynamic programming, which inherently is computationally more expensive than standard dynamic programming. recent contribution by (4 offers non-asymptotic sample
works focusing on the computational facets for these problems 37 6 35|
By 'unknown model' we refer to the setting where the nominal probability transition model is unknown. Both model-based and model-free methods belong to this setting, where model-hased methods keep empirical estimate of the nominal model whereas model-free algorithms don't require this empirical estimation step.

---

Published as a conference paper at ICLR 2024
complexity guarantees in the context of model-free robust RL. This achievement, however, introduces additional dual variables, thus adding additional computational complexity and imposing more stringent assumptions.
An alternative approach for handling uncertainty is risk-sensitive decision-making, which intriguingly shares elegant equivalence with robust decision-making. The concept of coherent risk measures was initially introduced and explored in 2 18 69]. where the uncertainty is represented by a static random variable. The connection robustness was established by characterizing risk measures as the infimum of expected shortfall across a set of probability measures, known as the risk envelope. The risk notion further extended to convex risk measures which capture a broader class of risk evaluation functions 30, 773 B1. Subsequently, conditional and dynamic risk measures were introduced to generalize
risk assessment from static random variables to stochastic processes A 14 29 22
72 65| In
particular, [71] introduces the Markov risk measure in the context of Markov Decision Processes (MDPs). However, the equivalence between the Markov risk measure and robust MDPs not as straightforward as in static settings. Notably, [71 75 5
62 established the equivalence between optimizing the Markov risk measure and solving a modified RMDP problem, where the uncertainty set dynamically changes with the implemented policy. This differs from the standard RMDPs, where the uncertainty sets are typically unrelated to the policy. Though [62] attains stronger equivalence results with RMDPs, it is only applicable specific risk measures, such as Conditional Value at Risk (CVaR). Similar to RMDPs, optimizing Markov risk measures also faces many challenges. Firstly. building upon the equivalence with the modified RMDP with policy-dependent uncertainty set, Huang et al. (39) highlights that, even in tabular setting with direct parameterization, Markov risk measures may lack gradient-dominance a stark contrast to the gradient domination observed in standard MDPs [.. This implies that policy gradient algorithms may not ensure global optima, even in straightforward, full-informttion environment. Further, the sample complexity is also harder to obtain. While there is series of efforts dedicated to optimizing the Markov risk measure within the realm of RL 12 76 46), these works primarily provide asymptotic convergence results.
The challenges outlined above motivate us to investigate the potential of introducing an alternative risk formulation. This new formulation seeks to capture risk in a way similar to Markov risk measures while achieving a stronger and broader equivalence with RMDPs. Moreover, convergence properties, including the crucial aspect of gradient domination. These improvements are poised to support the development of learning algorithms for both RMDPs and risk-sensitive MDPs while maintaining provable guarantees.
aim to enhance
Our Contributions: In this paper, we propose new formulation for risk-sensitive MDP, whose definition incorporates the general concepts of convex risk measures. We first establish the equivalence of risk-sensitive MDP with class of soft RMDP problems, which includes the standard RMDP as special case. Leveraging this equivalence, we proceed to derive the policy gradient theorem for both the aforementioned class of soft RMDPs and risk-sensitive MDPs (Theorem 3 and prove the global convergence of the exact policy gradient method under the tabular setting with direct parameterization. Our result, to the best of our knowledge, presents the first global convergence analysis with iteration complexity for a general class of risk-sensitive MDPs.
Based on the policy gradient theorem, we also highlight the difficulty of gradient estimation using samples compared with the standard MDP setting, motivating us to seek other types of sample-based learning methods. In the last part of this paper, we mainly focus on the setting of offline learning with nonlinear function approximation which is relatively less-studied scenario, and propose sample-based offline learning algorithm, namely the robust fitted-Z iteration (RFZ), that resembles policy iteration rather than policy gradient.Seccifccally
focus on setting where the regularization term for the RMDP is a KL-divergence term, which is equivalent to the resk-sensitive MDP with the entropy risk measure. The algorithm utilizes the equivalence between the two problems, which enables simpler algorithm design. Notably, our algorithm is model-free and does not rely on an empirically estimated probability transition model. The sample complexity for RFZI is also provided. Compared with (64) which considers offline robust RL with sample-comple guarantees, our work considers a different uncertainty set, requires less computational and implementation complexity, and less stringent assumptions.
Due to space limit, we defer a detailed literature review and numerical simulations to the appendix.
2

---

Published as a conference paper at ICLR 2024
2 PROBLEM SETTINGS AND PRELIMINARIES
Markov Decision Processes (MDPs). A finite Markov decision process (MDP) is defined by tuple M - (S, A, P. 7: P),, where S a finite set of states, AA is a finite set of actions available to the agent, and P is the transition probability function such that P(s'|s |s, a) describes the probability of transitioning from one state s to another s' given a particular action a. For the sake of notation simplicity, we
Ps.a to denote the probability distribution P(11s, a) over the state space S. r x A - [0. 1] is a reward function, Y E [0, 1) is a discounting factor, and / specifies the initial probability distribution over the state space S.
A stochastic policy S I specifies strategy where the agent chooses its action based on the current state in a stochastic fashion; more specifically, the probability of choosing action a at state s is given by Pr(aas) every state s there is an action a, such that π (a,]))) = 1. For notation simplicity, we slightly overload the notation and use (s)) to denote the action a, for deterministic policies. For a given stationary policy т and set of transition probability distributions {Ps,a we denote the discounted state visitation distribution by
π (aass) A deterministic policy is special case of the stochastic policy where for
d (s) == (1 -1--1 7) Ei= y PPPr.PPss = =s =s| $150 ~ p).
Robust MDPs (RMDPs) and Soft Robust MDPs. Unlike the standard MDP which considers a fixed transition model ), the robust MDP considers a set P transition probability distributions and aims to solve the sup-inf problem [1
sup= inf (PrEP)ezo B B Poopp Et 4000 7 (r(s), at)
(I)
where the objective is to find the best action sequence that maximizes a worst-case objective over all
63 4 consider the uncertainty set under the (s, a) -rectangularit condition P @.ES.aEAA.. Ps.as where Ps,a {Ps.a : E( Ps.a) S
possible models in the uncertainty set P. Many papers 41 57 99
c), and é is a penalty function that captures the deviation of P..a from a nominal model Ps.a. Some popular penalty functions are KL divergence, total variation distance, etc.
In this paper, we generalize the above robust MDP problem to a wider range of problems which we call the soft robust MDF The objective of the soft robust MDP solves the following sup-inf problem:
su inf (Pr) E aa P P.s Σto 7' (r(ss, as) DD( Po...))
(2)
Note that here inf [P: (22 is with respect to all the possible state-transition probability distributions. When the penalty function D is chosen as the indicator function
{(P..:: Psa) S otherwise
D(P..,. Ps.a)
+00
it recovers the robust MDP problem TT. When D is set non-indicator functions, for example,
D(P.aa, Ps,a) = (L((P... (P...alll 2.al|P2 p..)), Problem (2) is a robust MDP with a soft penalty term D on the deviation of P..a from P..a rather than a hard constraint on P Ps.a-
Similar to the robust MDP problem, we can define the optimal value function as
= iup (Pr) E BenN -t 7t (r(s,,, a.) + + P.. Pa..e)) |so = s (3)
Additionally, given a stationary policy æ, the value function V uunder policy л is defined as follows:
(s( == inf inf (Po) E E P Ete 7e (r(st, at) + +DD(PPrsees P.n.a))
(s00000000 =
(4)
We also define the corresponding Q f-functions
Q' (s, a) =u inf (8)
E Ean Etoo 75 (T(s), (Psss au Pol.a))
So - s, 0u a==a
Q" (s.a):=inf (P))oo E E Etoo (r Ps P.c.a))
So 8, 0. =a
FFor the sake of generality, allow the transition probability to be non-stationary and the policy be non-Markovian and stochastic. However, in later sections will show that the sup-inf solution be obtained by a stationary deterministic Markov policy and stationary transition probability (Theorem 2].
We adopt the term from robust optimization literature, the concept of regularizing the adversaries actions is referred soft-robustness
D (or comprehensive robustness X and globalized robustness (00).
3

---

Published as a conference paper at ICLR 2024
Remark (Soft Robust MDP.). The soft robust MDP problem is useful, especially when the uncer- tainty set is not explicitly given. In this case, it is more desirable to consider all possible probability transition models (P))20 while treating the deviation from the nominal model as soft penalty term D rather than constraining to be within a specified uncertainty set.
In this paper, we establish connection between the soft robust MDP and another class of MDPs. namely risk-sensitive MDPs. To define the risk-sensitive MDP, we will first introduce the notation of convex risk measures.
Convex Risk Measures 30). Consider finite set S, let gl denote the set of real-valued functions over A convex risk measure a RISl + R is a function that satisfies the following properties:
1. Monotonicity: for any V", V E RI if V S V. then (VV S <o()).
2. Translation invariance: for any V E RI E R. aVV m) oVV m.
3. Convexity: for any V", E R E [0, 1]. aAV + -)V"' S \o (1-))()())))))
Using standard duality theory, it is shown in classical results 30 that convex risk measures satisfy the following dual representation theorem:
Theorem 1 (Dual Representation Theorem (30). The function a : I + R convex risk measure if and only if there exists a "penalty function" " D(-): A R. such that
o suPpEaIsI (- D(T))
(5)
Further, the penalty function D can be chosen satisfy the condition D 2 -0(()) for any | and it can be taken to be convex and lower-semmicontinuous In specific, it can be written in the following form:
D(P) = supv (-o(V) - EEsn)V(s))
(6)
Note that and D serve the Fenchel conjugate of each other. In most cases, the convex risk measure o (V)) can be interpreted as the risk associated with random variable that takes on values (s) where s is drawn from some distribution measures are typically associated with underlying probability distribution μ A (e.g., Examples D. This paper focuses on this type of risk measures and thus we use (H,, -) to denote the risk measure, where the additional variable μ indicates the associated probability distribution. Correspondingly, we denote the penalty term (fa) of (j,,) ) in the dual representation theorem as D( n1)
μ. Consequently, most commonly used risk
Here we provide an example of convex risk measure and its dual form.
Example 1 (Entropy risk measure 30).. For given 0, the entropy risk measure takes the form:
(p, V) = 3-1 log Eg-ue -BV(s)
Its corresponding penalty function D in the dual representation theorem is the KL divergence D(P. p) = 6- (KL((())))) = 3- Exes (is) log (f(s)/u(s)).
Risk-Sensitive MDPs. Convex risk measures capture the risk associated with random variables. It would be desirable if the notion could adapted to the MDP to capture the risk of a given policy under the Markov process. Given an MDP M, a class of convex risk measures {a(PP (Ps,a. JeS and policy π (-|s),, the risk-sensitive value function 1a8 for the infinite discounted MDP is given as
(s) = E. (aasss)) (((s,a)-700) (Ps v*)) Vs E.
With the definition of risk-sensitive V=, the risk-sensitive MDP problem is to find the policy that maximizes max, र.. We denote the optimal value by V which is the fix-point solution of the following equation.
'Please note that the symbol D serves dual purpose, representing both the regularization term in 2 and the penalty function for risk measure in (5) and (6) This intentional notation overlap will become clear in the following sections, which reveal the connection between these terms.
4

---

Published as a conference paper at ICLR 2024
(s) == max, (r(s,a) -oo(Ps. VT)) Vs E.S.
(8)
It is worth noting that the fixed point operators for 7 are contractive (proof deferred to Appendix D which immediately implies the following lemma which verifies that the fixed point equations for V and V* ( are well-defined.
Lemma 1. The solution to 7 exists and is unique. Same argument holds for
Remark 2. We would like emphasize that when the policy is stochastic, definition of the
value functions V are different from the Markov risk measures defined in [7 86 87 However, the two quantities are equivalent when π. is deterministic. Additionally, when further assuming that mixture quasiconcave (c.f. (77), the optimal policy for the Markov risk measure is also deterministic and thus the sesk-sensitive MDP and the Markov risk measure obtain the same optimal value V* (see Appendix Cor more details).
the risk measure
We also define the Q-function of the risk sensitive MDP as:
Q" (" = r(s, a) (P V*,,
(=( a) -(o(L)) V*).
Other notations: For any function f : S x + R, state-action distribution μ E A(S x A) the j--wiigttd 2-norm of f defined as 1| (fs,e=af(s.a)))
EQUIVALENCE OF SOFT RMDPS AND RISK-SENSITIVE MDPS
Theorem 2 (Equivalence of Soft RMDPs and Risk- disk-Sensitive MDPs), For given MDP M, penalty function D, class of convex risk measures (a(Ps..:))) and stationary policy if the penalty function D satisfies
D(Ps.a Ps.a) = supv (-o(Pa.s V) P.
V(6').
then the value functions and Q-functions of the soft RMDP and the risk-sensitiv MDP are always the same. That is, =V= V
=V==== Q²=Q===Q"" Q = Q"
Further, for every initial state so, the sup-inf solution of the policy and transition probabilities for V* V80)) defined in 33 is given by:
x (s) argmax, (r(s, a) - -o V*)),
(10)
E:s,a P.. = argmin p D(P, Ps.a) + BV)
where 10) means that the optimal action sequence {ath22 can be achieved by implementing the deterministic policy a₂ = (st).
Similarly, for any initial state so, the minimum solution of the transition probabilities for V* defined in (4 is given by
P P PT D Ps.a) EBL-PV
(11)
Since Theorem has established the equivalence of risk-sensitive MDPs and soft RMDPs, from now V VV. Q²,Q" denote the value functions and Q-functions for both settings and assume by default that the penalty function D and the risk measure satisfy relationship
Remark 3. a comparison to the equivalence result for the Markov risk measures [72 861. their uncertainty set for the robust problem generally depends on the policy π (see e.g. Assumption 2.2 in (86)), while in our setting, the penalization function is independent of the policy and matches with the most slandard formulation of RMDPs.
'Due to this difference, the value function V* can no longer be written as p( 7'r(s,, a.)) where p is a time-consistent dynamic risk measure. This makes our definition different from the usual interpretation of the dynamic risk measures.
WWe would like to note that the equivalence of optimal value might fail if a is not mixture semiconcave (e.g. mean (semi)- deviation, mean (semi)-momen measures (17) or if policy regularization is added into the value function because the optimal policy might longer be deterministie.
'The equivalence V = V=_ Q" = Q" easily extends to the setting with policy regularization, since adding regularization only requires changing the reward function r(s, a) to be r (s, a) r(s, a) + R(=(--s)), where R. the policy regularizer, which the proof of Theorem 2 still carry through naturally.
5

---

Published as a conference paper at ICLR 2024
4 POLICY GRADIENT FOR SOFT RMDPS
In this section, present the policy gradient theorem for differentiable policy To parameterized by 8, which provides an analytical method for computing the gradient soft RMDPs. Additionally, we prove the global convergence of the exact policy gradient ascent algorithm for the direct parameteri- zation case. For simplicity, in this section we use the abbreviations V Q" Po, v(t), Q(9, p()) to denote V** QTa Pro, V=a(o, QFo(e), Proce respectively.
Theorem (Policy gradient theorem). Suppose that Hι is differentiable with respect to 0 and that (Ps,as)) :) RRS) + R is differentiable function, then V is also differentiable function with respect to and the gradient is given by
VoV = a Po
Et 20 (sc ar) V log No so(arls) =
where To0 is defined in (11)
We leave the discussion of this result the end of this section in Remark 4 Theorem 3 immeddately implies the following corollary on the policy gradient under direct parameterization (c.f. M 94), where the parameter 0z.a directly represents the probability of choosing action a at state i.e.
0, = ne (a)s).
Corollary (Policy gradient for direct parameterization). Under direct parameterization,
Bp (sn)
d d
P" (s)
(12)
00...
Note that the policy gradient theorem only holds for the case where (PP..: is differentiable; nevertheless, we can generalize (12 the non -indeifeeret case by defining the variable G(0) [RSS||AA| as follows:
G())) = 1-7 d (s))*
For both differentiable and non-differentiable cases, we could perform the following ('quasi (qquasi-)gradden ascent algorithm:
((++1) Proj (010 +))((())),
(13)
where X' &SES A denotes the feasible region of For the standard MDP case, it is known that the value function satisfies the gradient domination property under direct parameterization [I], which enables global convergence of the policy gradient algorithm. Similar properties also hold for the soft RMDP/risk-senniee sensitive MDP setting which is shown the following lemma:
Lemma 2 (Gradient domination under direct parameterization).
E Eggri (so) (0) I
max क -T88 G()))
a=t 150
d= (6) PV
where
max,
The gradient domination property suggests that as long as the term
is not infinite, all the first order stationary points global optimal solutions. Based on this observation, we further derive the convergence rate for the policy gradient algorithm. Before that, we introduce the following sufficient exploration assumption:
Assumption 1 (Sufficient Exploration). For any policy ग. it holds that d= ir (s) > O, where pm defined as in (IT). We define the distributional shift factor M to be constant that satisfies M 2 d=.F"(a) (s) for all state and policy
Note that when we start with initial distribution where p(x) > 0 for every state the term M can be upper bounded by (1-7) p(a) If Assumption I is satisfied, it can be concluded that
< .. Thus we could use gradient domination to derive the global convergence rate.
pe

---

Published as a conference paper at ICLR 2024
Theorem 4 (Convergence rate for exact policy gradient under direct parameterization). Under (1->)²
Assumption / by setting 2|A|ar rumning
13 guarantees that
Ek=1 (Bxo~pV*(s)) - v(b) 16AA|M"
(1-7)"
Therefore, by setting K 2
10 (1-7)-23 it is guaranteed that minisksK (
Se.
If we apply the same proof technique to standard MDPs, the convergence rate is O LAIMe
(1-7)* The
dependency on the distributional shift factor M is worse for soft RMDPs, which caused by the choice of a smaller stepsize v) (see Remark 7 the Appendix for more details). It is an interesting open question whether this worse dependency fundamental or just a proof artifact.
Remark 4 (Difficulties of Sample-based Gradient Estimation). Though Theorem Theoremmestablisst establishes the global convergence of exact policy gradient. it is hard to generalize the result to cample-based settings. Note that the policy gradient in Theoremaaake
similar form compared to standard MDPs 83 however, there's 's a primary distinction that the expectation is taken over trajectories sampled from the probability transition model o instead of the nominal model P. Consequently when confined to samples exclusively from the nominal model, estimating this expectation becomes exceptionally challenging, particularty in the context of non-gen non-generative models.
OFFLINE REINFORCEMENT LEARNING OF THE KL-SOFT RMDP
Since the previous section considers learning with full information and studies iteration complexity, the major motivation for this section is examine sample-based learning for risk sensitivity MDPs and soft robust MDPs. As discussed in Remark 4 developing sample-based policy gradient learning methods might be difficult, therefore, we seek an alternative cample-based method that resembles policy iteration rather than policy gradient. Specifically, we mainly focus on the setting of offline learning with nonlinear function approximation which is relatively less-studied scenario. Moreover, due to the challenge in developing method for soft MDPs with general D functions (or equivalently for risk sensitive MDPs with general risk functions o), in this section, we look into a particular and important case of soft RMDP where the regularization term is the KL-divergence, i.c.,
max, minp, E Pr Etoo 7 (r(st, a:) + x 1yy--kK- "OL--KL(PPP) PLLee....o
(14)
The hyperparameter, 33 represents the penalty strength of the deviation of P from P. the smaller / is, the larger the penalty strength. From Example [nd Theorem 2 the KL-soft RMDP is equivalent to the risk-sensitive MDP problem with the risk measures o (PPa,s chosen as the entropy risk measure
(PP... V) 8 log E.r~P..e e- (V((')
In this case, the Bellman equations for the value functions V*, V=,V* "*, Q", Q* are given by:
-" a),
a) log E, BP -VV(6')
(*)s) max, (ss,a),
(s) = r(s, ~ log E, P,. (V)
For notational simplicity, we define the Bellman operator the Q-functions To -RR R|S)
(s) = r(s, - 7 1 log Egy- Pyy max, Q(e',a)) a')
(15)
It is not hard to verify from the above arguments that the optimal Q function Q* satisfies
Q' = TQQ.
Offline robust reinforcement learning. The remainder of the paper focuses on finding the optimal robust policy x² for the soft robust MDP problem (14). Specifically, we explore offline robust reinforcement learning algorithms which use pre-collected dataset D to learn x². The dataset typically generated under the nominal model {Px.a P.s.ases.ae.. such that = {s; a; Ti, N where the state-action pairs az) ~ y are drawn from a specific data-generating distribution p..
7

---

Published as a conference paper at ICLR 2024
Definition (Robustly Admissible Distributions). A distribution E / ||8) is robustly admissible there exists h 2 0 and policy a and transition probability PPP (ls.al 33 (both can be non-stationary) such that v(8, a) = Pr(sh,
p, P).
Assumption 2 (Concentrabilityy, The Kata-ggnerattnn distribution μ satisfies concentrability if there exists a constant C' such that for any v that is robustly admissible, maX,,0 p(s.a) - C.
p(s.s)
Remark 5. The notion of robustly admissible distribution and concentrability are adapted from the the corresponding notions defined for the standard MDP setting [13), where they also demonstrate the necessity of this assumption for standard RL with function approximation.
would be an interesting open question whether Assumption 2 is also necessary for robust RL seltings. Recent works for standard offline RI. also show that by considering variations of the RL algorithms (e-g. exploring pessimism (95] or the primal dhall formulation (I02]), the concentrability assumption can be weakened to single-policy concentrabiliry. Another interesting future direction is to study whether applying similar approaches for the soft RMDP would result the same improvement.
5.1 ROBUST FITTED-7. ITERATION (RFZI)
The offline robust MDP learning method we propose is Robust fitted-Z iteration (RFZI). The main idea is to utilize the fix point equation Q' ToQ" with the Bellman operator (15) from the corresponding equivalent risk-sensitive MDP. However, To involves term log Ev' which is hard to approximate with empirical estimation. Thus, instead of directly solving Q* using Q" = ToQ". we introduce auxiliary variable, Z-function and solve fix point equation for Z, which play an important role in our algorithm design and theoretical analysis.
The Z-functions. For a given Q-function Q S A + R, we define its corresponding Z-function as below:
Z(s, a) = Eg,',,, e max, Q(/ ,a))
One can establish the relationship between the Z-function and the Q-function by [TqQ](s,a) r(s,a) --8-1 log as.
Further, we also define the Z-Bellman operator on Z-functions as:
[Tz a) = Ep'P, e max, ( (r(o' a')- 1 log 2()',d'))
Then TolToQ][ss, a) = r(s,a) - 1 log Tz T2 a). Thus, instead of solving Q = =TQQ" an alternative approach is to solve Z* Tz 7* and recover Q" by Q r- 'log Z This is the key intuition of our RFZI algorithm. Note that compare with To. Tz eliminates the log dependency on the expectation term Egee,,,. which makes it easier for empirical estimation.
Function approximation and projected Z-Bellman operator. Given that Tz is a contraction
mapping, the solution Z can be obtained by running Zk+1 = T Zx. limg-- Zk = Z* However, when the problem considered is of large state space, is computationally very expensive compute the Bellman operator Tz exactly. Thus function approximation might needed to solve the problem approximately. Given a function class F, we define the projected Z. B-Bellman operator as:
[Tz, a) == argminzrer I 2
One can verify that T Z is also the minimizer of the following loss function L.
C(Z', 2)) == E. R By Pa.a (Z'(s, a) - cxp (-8 max, maa..aa((66 (r(s',a') - --3-1 1-p--loop log Z(s', ( ie., T = argming ( Z).
We make the following assumptions the expressive power of the function class F Assumption 3 (Approximate Completeness). supzer infzee Z -TzZlla 11,,, Ec.
Assumption (Positivity). e -ー < Z 11 YZER
8

---

Published as a conference paper at ICLR 2024
Approximate the projected Z-Bellman operator with empirical loss minimization. The compu- tation of the loss function & requires knowledge of the empirical model Ps.a which the algorithm doesn't have access to. Thus, introduce the following empirical loss to further approximate the loss function L.. Given an offline data set {(*;, di, {())= generated from the distribution (8i, ~M, 6/ Peç,, we can define the empirical loss E as:
Z) = Ei (Z'(s;, a.) - exp (- max. 7B-1 log ((s), a()))
Given the empirical loss E the empirical projected Bellman operator is defined Tz er C(Z', Z). Our robust fitted iteration (RFZI) essentially updating the Z-functions iteratively by Zk+1 Tz.5 Zg. The detailed algorithm is displayed in Algorithm
Algorithm 1 Robust Fitted Z. Iteration (RFZI)
1: Input: Offline dataset = (8i, Oz Fú, 8 function class F.
2: Initialize: Zo 1 E F
3: for k == 0, O...., K 1 do
4: Update Z = argminzer Zk),
5: end for
6: Output: π argmax, r(s, a) 78 log Z (s,
5.2 SAMPLE COMPLEXITY
This section provides the theoretical guarantee for the convergence of the RFZI algorithm. Due to space limit, we defer the proof sketches as well as detailed proofs to Appendix H
Theorem 5 (Sample complexity for RFZI). Suppose Assumption 2 and 4 hold, then for any
dE E (0, 1), with probability at least 1 - 6, the policy т obtained from RFQI algorithm (Algorithm 7 satisfies:
2
2C
(AV)
log([F))
2 1og(888) +GG
E. Exg~p V (80)s V (50)
7)2 1
AV
+5V
(1 (1-7)2
N
N
24 The performance gap in Theorem consists of three parts. The first part (1-g)² captures the effect of y-contraction of the Bellman operators. The second term, which is the term with y 20 is related to the approximation error caused by using function approximation. The third term
(1-7)=
7
2C [1->}²
4V
(o))
+5
(88()8 is caused by the error of replacing the projected N
Z-Bellman operator with its empirical version.
Remark 6 (Comparison and Discussions). Under similar Bellman completeness and concentrability
assumptions, the sample complexity for risk-neutral offline RL 13 is 0 log [
while our result
(1-1)
gives O
log [F] (1->)+e²
(assuming c 00. As consequence of robustness, our bound
has worse dependency the concentrability factor C and an additional factor (s-le==)) Note
that the term - first decreases and then increases with 3 as it goes from 0 +00, suggesting that the hyperparameter 3 also affects the learning difficulty of the problem. The choice of 3 should not be either too large too small, ideally the same scale with 1 1-7, It is still unclear to us whether the exponential dependency e -ー is a proof artifact or intrinsic in our setting, however, there are results under similar settings that suggest this exponential dependency on parameter 3 and the effective length T-
1_ is fundamental (e.g. Theorem 3 in (261).
We also compare our performance bound with the RFQI algorithm 164 which considers similar offline learning setting and obtains sample complexity O (og(FFllg))
(1 where 3 in their setting is and the
the radius of the uncertainty set. Note that both results share the same dependency concentrability constant C. However, the bound in (64) includes an additional term on the size of the 20
dual variable space log [G], whereas we have the exponential dependence term e

---

Published as a conference paper at ICLR 2024
6 CONCLUSIONS AND DISCUSSIONS
This paper proposes formulation of risk-sensitive MDP and establishes its equivalence with the soft robust MDP. This equivalence enables us to develop the policy gradient theorem and prove the global convergence of the exact policy gradient method under direct parameterization. Additionally, for the KL-soft robust MDP (or equivalently the risk-sensitive MDP with entropy risk measure) scenario, we propose a sample- canple-bseed offline learning algorithm, namely the robust fitted-Z iteration (RFZI), and analyze its sample complexity.
Our work admittedly has its limitations. Currently, our policy gradient result limited to the exact gradient case, and further research is needed to extend it to approximate gradients. The RFZI algorithm is specifically designed for KL.-soft problems and may be more suitable for small action spaces. Our future work will focus developing practical algorithms that can handle large even continuous state and action spaces, as well as generalizing the approach to accommodate different penalty functions.
ACKNOWLEDGEMENT
This work was funded by NSF AI institute: 2112085, NSF ECCS: 2328241.
REFERENCES
[1] Alekh Agarwal, Sham M. Kakade, Jason D. Lee, and Gaurav Mahajan. On the theory of policy gradient methods: Optimality, approximation, and distribution shift, 2020.
Philippe Artzner, Freddy Delbaen, Jean-Mare Eber, and David Heath. Coherent measures of risk. Mathematical finance, 93)::203-228, 1999.
[3] Philippe Artzner, Freddy Delbaen, Jean-Mare Eber. David Heath, and Hyejin Ku. Coherent multiperiod risk adjusted values and Bellman's 's principle. Annals of Operations Research, 152: 5-22, 2007.
[4] Kishan Panaganti Badrinath and Dileep Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference on Machine Learning, pages 511-520. PMLR, 2021.
[5] Nicole Bäuerle and Alexander Glauner. Distributionally robust Markov decision processes and their connection to risk measures. Mathematics of Operations Research, 175771777- 2022.
[6] Bahram Behzadian, Marek Petrik, and Chin Pang Ho. Fast algorithms for L constrriiedd s-rectangular robust MDPs. Advances in Neural Information Processing Systems, 34:25982- 25992, 2021.
[7] Mare G Bellemare, Will Dabney, and Rémi Munos. A distributional perspective on reinforce- ment learning. In International conference machine learning, pages 458. PMLR, 2017.
[8] Aharon Ben-Tal Stephen Boyd, and Arkadi Nemirovski. Extending scope of robust optimiza- tion: Comprehensive robust counterparts of uncertain problems. Mathematical Programming, 107(1-2):63-88) 2006.
[9] Aharon Ben-Tal, Dimitris Bertsimas, and David B Brown. soft robust model for optimization under ambiguity. Operations research, 58(4-part-2): 2010.
[10] Aharon Ben-Tal, Ruud Brekelmans, Dick Den Hertog, and Jean-Philippe Vial. Globalized robust optimization for nonlinear uncertain incqualities. INFORMS Journal on Computing, 29 (2):550-36,, 2017.
[11] Nicole Bäuerle and Alexander Glauner. Markov decision processes with recursive risk mea- sures. European Journal of Operational Research, 296(3):953-966 2022. ISSN 0377-2217.
10

---

Published as a conference paper at ICLR 2024
[12] Özlem Çavus and Andrzej Ruszczyíiski. Computational methods for risk-e undiscounted transient Markov models. Operations Research, 62(2):401-477, 2014.
[13] Jinglin Chen and Nan Jiang. Information-theorrtic considerations in batch reinforcement learning. In International Conference on Machine Learning, pages 1042-1051. PMLR, 2019.
[14] Patrick Cheridito, Freddy Delbaen, and Michael Kupper. Dynamic monetary risk measures for bounded discrete-time processes. Electronic Journal of Probability. 2006.
[15] Yinlam Chow, Mohammad Ghavamzadeh, Lucas Janson, and Marco Pavone. Risk-constrained reinforcement learning with percentile risk criteria. The Journal of Machine Learning Research, (10))66070- 2017.
[16] Anthony Coache and Sebastian Jaimungal. Reinforcement learning with dynamic convex risk measures. Mathematical Finance, 2023.
[17] Erick Delage, Daniel Kuhn, and Wolfram Wiesemann. "dice"-sion-makinn under uncertainty: When can random decision reduce risk? Manag. Sci., 65:3282- 3301, 2016. URL https:
7/ //ppi. www.sseesannnscoseeemeee
org/ :o:
[18] Freddy Delbaen. Coherent risk measures on general probability spaces. Advances in finance and stochastics: essays in honour of Dieter Sondermann, pages 1-37, 2002.
[19] Esther Derman and Shie Mannor. Distributional robustness and regularization in reinforcement learning. ICML Workshop on Theoretical Foundations of Reinforcement Learning, 2020.
[20] Esther Derman, Daniel Jaymin Mankowitz, Timothy A. Mann, and Shie Mannor. Soft-robust actor-critic gradee.gr.dient In Conference on Uncertainty in Artificial Intelligence, 2018
[21] Esther Derman, Matthieu Geist, and Shie Mannor. Twice regularized MDPs and the equivalence between robustness and regularization. Advances in Neural Information Processing Systems, 34:22274-22287, 2021.
[22] Kai Detlefsen and Giacomo Scandolo. Conditional and dynamic convex risk measures. Finance and stochastics, 9:539-561 2005.
[23] Wenhao Ding, Laixi Shi, Yuejie Chi, and Ding Zhao. Seeing is not believing: Robust rein- forcement learning against spurious correlation. Advances in Neural Information Processing Systems, 2023.
[24] Simon S. Du. Sham M. Kakade, Ruosong Wang. and Lin F. Yang. Is a good representation sufficient for sample efficient reinforcement learning? In International Conference Learning Representations, 2020.
[25] Benjamin Eysenbach and Sergey Levine. Maximum entropy RL (provably) solves some robust RL problems. In International Conference on Learning Representations, 2022.
[26] Yingjie Fei, Zhuoran Yang, Yudong Chen, Zhaoran Wang, and Qiaomin Xie. Risk-sensitive reinforcement learning: Near-optimal risk-sample tradeoff in regret. Advances in Neural Information Processing Systems, 33:22384 223955, 2020.
[27] Yingjie Fei, Zhuoran Yang, Yudong Chen, and Zhaoran Wang. Exponential Bellman equation and improved regret bounds for risk-sensitive reinforcement learning. Advances in Neural Information Processing Systems, 14:20436-20446, 2021.
[28] Yingjie Fei, Zhuoran Yang, and Zhaoran Wang. Risk-sensitive reinforcement learning with function approximation: A debiasing approach. In International Conference on Machine Learning, pages 3198-3207. PMLR, 2021.
[29] Hans Föllmer and Irina Penner. Convex risk measures and the dynamics of their penalty functions. Statistics & Risk Modeling, 24(1):61-96, 2006.
[30] Hans Föllmer and Alexander Schied. Convex measures risk and trading constraints. Finance and stochastics, 6:429-447, 2002.
11

---

Published as a conference paper at ICLR 2024
[31] Hans Föllmer and Alexander Schied. Robust preferences and convex measures of risk. Advances in Finance and Stochastics: Essays in Honour of Dieter Sondermann, pages 39-56, 2002.
[32] Hans Föllmer and Alexander Schied. Stochastic finance. Stochastic Finance. Gruyter, 2016.
[33] Peter Geibel and Fritz Wysotzki. Risk-sensitive reinforcement learning applied to control under constraints. Journal of Artificial Intelligence Research, 24:81-108, 2005.
[34] JI González-Trejo, Onésimo Hernández-Lerma, and Luis F Hoyos-Reyes. Minimax control of discrete-time stochastic systems. SIAM Journal on Control and Optimization, 41(5): (626-1659, 2002.
[35] Julien Grand-Clément and Marek Petrik. On the convex formulations of robust Markoy decision processes. arXiv preprint arXiv:2209. 2022.
[36] Aria HasanzadeZonuzz, Archana Bura, Dileep Kalathil, and Srinivas Shakkottai. Learning with safety constraints: Sample complexity of reinforcement learning for constrained MDPs. Proceedings of the AAAI Conference on Artificial Intelligence, 2021.
[37] Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Robust ø-divergence MDPs. Advances in Neural Information Prucessing Systems, 35:32680-32693, 2022.
[38] Ronald A Howard and James E Matheson. Risk-sensitive Markov decision processes. Man- agement science, 18(7):356-385 369, 1972.
[39] Audrey Huang, Liu Leqi, Zachary C Lipton, and Kamyar Arizzadenesheli. On the convergence and optimality of policy gradient for Markov coherent risk. arXiv preprint arXiv:2103.02877 2021.
[40] Vasile Istratescu. Fixed point theory: an introduction. Springer, 1981.
[41] Garud N lyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
[42] Sebastian Jaimungal, Silvana M Pesenti, Ye Sheng Wang. and Hariom Tatsat. Robust risk- aware reinforcement learning. SIAM Journal on Financial Mathematics, 13(1):213-226, 2022.
[43] Sham M. Kakade and John Langford. Approximately optimal approximate reinforcement learning. In Claude Sammut and Achim G. Hoffmann, editors, Machine Learning, Proceedings of the Nineteenth International Conference, pages 267-274, 2002.
[44] IS Khalil, JC Doyle, and K Glover. Robust and optimal control. Prentice hall, 1996.
[45] Faisal Khan, Seyed Javad Hashemi, Nicola Paltrinieri, Paul Amyotte, Valerio Cozzani, and Genserik Reniers. Dynamic risk management: contemporary approach to process safety management. Current opinion in chemical engineering. 14:9-17, 2016.
[46] Ümit Köse and Andrzej Ruszczyúski. Risk-averse learning by temporal difference methods with Markov risk measures. The Journal of Machine Learning Research, 22(1):1800-188) 1021.
[47] Navdeep Kumar, Esther Derman, Matthieu Geist, Kfir Yehuda Levy, and Shie Mannor. Policy gradient for rectangular robust markov decision processes. In Thirty-seventh Conference on Neural Information Processing Systems, 2023.
[48] Prashanth La and Mohammad Ghavamzadeh. Actor-critic algorithms for risk-sensitive MDPs Advances in neural information processing systems, 26, 2013.
[49] Gen Li, Laixi Shi, Yuxin Chen, Yuejie Chi, and Yuting Wei. Settling the sample complexity of model-basee offline reinforcement learning, arXiv preprint arXiv:2204.0522 2022.
12

---

Published as a conference paper at ICLR 2024
[50] Mengmeng Li, Tobias Sutter, and Daniel Kuhn. Policy gradient algorithms for robust MDPs with non-rectangular uncertainty sets. arXiv preprint (XXXv:2335,190000 2023.
[51] Shiau Hong Lim, Huan Xu, and Shie Mannor. Reinforcement learning in robust Markov decision processes. Advances in Neural Information Processing Systems, 26, 2013.
[52] Lynn Harold Loomis and Shlomo Sterbberg. Advanced calculus. World Scientific, 1968.
[53] Xiaoteng Ma, Li Xia, Zhengyuan Zhou, Jun Yang, and Qianchuan Zhao. Dsac: Distributional soft actor critic for risk-sensitive reinforcement learning. arXiv preprint arX1v:2004.14547, 2020.
[54] Xiaoteng Ma. Zhipeng Liang, Li Xia, Jiheng Zhang, Jose Blanchet, Mingwen Liu, Qianchuan Zhao, and Zhengyuan Zhou. Distributionally robust offline reinforcement learning with linear function approximation. arXiv preprint wxXiv2209.066200 2022.
[55] Daniel J. Mankowitz, Nir Levine, Rae Jeong. Abbas Abdolmaleki, Jost Tobias Springenberg, Yuanyuan Shi, Jackie Kay, Todd Hester, Timothy Mann, and Martin Riedmiller. Robust reinforcement learning for continuous control with model misspecification. In International Conference on Learning Representations, 2020.
[56] Shie Mannor, Ofir Mebel, and Huan Xu. Robust MDPs with k-rectangular uncertainty. Mathematics of Operations Research, 4144)11484-150, 2016.
[57] Arnab Nilim and Laurent El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
[58] Erfaun Noorani and John S Baras. Risk-sensitive reinforce: A monte carlo policy gradient algorithm for exponential performance criteria. In 202 60th IEEE Conference on Decision and Control (CDC), pages 1522-1527. IEEE, 2021.
[59] Erfaun Noorani and John S Baras. Risk-sensitive reinforcement learning and robust learning for control. In 2021 60th IEEE Conference on Decision and Control (CDC), pages 2976-26 1981. IEEE, 2021.
[60] Erfaun Noorani and John Baras. From regularization to risk-scnsitivity--nd back again. IFAC-PupprSOnLLine, 55(15)333-38, 2022.
[61] Erfaun Noorani, Christos Mavridis, and John Baras. Risk-sensitive reinforcement learning with exponential criteria. arXiv preprint arXiv:2212.09010. 2022.
[62] Takayuki Osogami. Robustness and risk- in Markov decision processes. Advances in Neural Information Processing Systems, 25, 2012.
[63] Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with generative model. In International Conference on Artificial Intelligence and Statistics, pages 9582-9602. PMLR, 2022.
[64] Kishan Panaganti, Zaiyan Xu, Dileep Kalathil, and Mohammad Ghavamzadeh. Robust reinforcement learning using offline data. Alice H. Oh, Alekh Agarwal, Danielle Belgrave, and Kyunghyun Cho, editors, Advances in Neural Information Processing Systems, 2022.
[65] Alois Pichler, Rui Peng Liu, and Alexander Shapiro. Risk-averse stochastic programming: Time consistency and optimal stopping. Operations Research, 70(4):2439-244 2022.
[66] Lerrel Pinto, James Davidson, Rahul Sukthankar, and Abhinav Gupta. Robust adversarial reinforcement learning. In International Conference on Machine Learning, pages 2817-2826.
PMLR, 2017.
[67] Tongzheng Ren, Zhaolin Ren, Na Li, and Bo Dai. Stochastic nonlinear control via finite- dimensional spectral dynamic embedding. arXiv preprint arXiv:2304.03907, 2023.
[68] Frank Riedel. Dynamic coherent risk measures. Stochastic processes and their applications, 112(2):185-200 2004.
13

---

Published as a conference paper at ICLR 2024
[69] R Tyrrell Rockafellar, Stanislav Uryasev, et al. Optimization of conditional value-at-risk Journal of risk, 2:21-42, 42, 2000.
[70] Aurko Roy, Huan Xu, and Sebastian Pokutta. Reinforcement learning under model mismatch. Advances in neural information processing systems, 30, 2017.
[71] Andrzej Ruszezyúski. Risk-averse dynamic programming for Markov decision processes. Muthematical proghicammrrrrgmmmmman programming, 125:235-261, 2010.
[72] Andrzej Ruszczyíski and Alexander Shapiro. Conditional risk mappings. Mathematics of operations research, 31(3):544 -614, 2006.
[73] Andrzej Ruszczyúski and Alexander Shapiro. Optimization of convex risk functions. Mathe- matics of operations research, 31(3):433-45,, 2006.
[74] Mohammad Shahidehpour, Hatim Yamin, and Zuyi Li. Market operations in electric power systems: forecasting. scheduling, and risk management. John Wiley & Sons, 2003.
[75] Yun Shen, Wilhelm Stannat, and Klaus Obermayer. Risk-sensitive Markov control processes. SIAM Journal Control and Optimization, 51(5):3652-361) 2013.
[76] Yun Shen, Michael J Tobia, Tobias Sommer, and Klaus Obermayer. Risk-sensitive reinforce- ment learning. Neural computation, 26(7): 1298-1328, 2014.
[77] Laixi Shi and Yuejie Chi. Distributionally robust model-based offline reinforcement learning with near-optimal sample complexity. arXiv preprint arXiv:2208.05766 2022.
[78] Laixi Shi, Gen Li, Yuting Wei, Yuxin Chen, Matthieu Geist, and Yuejie Chi. The curious price of distributional robustness in reinforcement learning with generative model. Advances in Neural Information Processing Systems, 2023.
[79] Rahul Singh, Qinsheng Zhang, and Yongxin Chen. Improving robustness via risk averse distributional reinforcement learning. In Learning for Dynamics and Control, pages 958-968. PMLR, 2020.
[80] Songsak Sriboonchita, Wing-Keung Wong, Sompong Dhompongsa, and Hung T Nguyen. Stochastic dominance and applications to finance, risk and economics. CRC Press, 2009.
[81] Silvestr Stanko and Karel Macek. Risk-averse distributional reinforcement learning: A evar optimization approach. In IJCCI, pages 412-423, 2019.
[82] Ke Sun, Yi Liu, Yingnan Zhao, Hengshuai Yao, Shangling Jui, and Linglong Kong. Exploring the training robustness distributional reinforcement learning against noisy state observations. In ECML/PKDD, 2021.
[83] Richard S Sutton, Andrew Barto, et al. Introduction to reinforcement learning, volume 135. MIT press Cambridge, 1998.
[84] Aviv Tamar, Dotan Di Castro, and Shie Mannor. Policy gradients with variance related risk criteria. In Proceedings of the twenty-ninth international conference on machine learning, pages 387-396, 2012.
[85] Aviv Tamar, Shie Mannor, and Huan Xu. Scaling up robust MDPs using function approxima- tion. In International conference on machine learning, pages 181-189. PMIR, 2014.
[86] Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Policy gradient for coherent risk measures. Advances in neural information processing systems, 28, 2015.
[87] Aviv Tamar, Yinlam Chow, Mohammad Ghavamzadeh, and Shie Mannor. Sequential decision making with coherent risk. IEEE Transactions on Automatic Control, 62(7):332-33338, 2017. doi: 10.1 10.1109/AC..22122244888
[88] Sebastian Thrun. Probabilistic algorithms in robotics. Ai Magazine, 21(4):93-93 2000.
14

---

Published as a conference paper at ICLR 2024
[89] Qiuhao Wang, Chin Pang Ho, and Marek Petrik. Policy gradient in robust mdps with global convergence guarantee. In International Conference on Machine Learning. 2022.
[90] Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty, Advances in Neural Information Processing Systems, 34:7193-7206, 2021.
[91] Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In International Conference on Machine Learning, pages 23484223526. PMLR, 2022.
[92] Yue Wang. Fei Miao, and Shaofeng Zou. Robust constrained reinforcement learning. arXiv preprint arXiv:2209.66800 2022.
[93] Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov decision processes. Mathematics of Operations Research,
2013.
[94] Lin Xiao. On the convergence rates of policy gradient methods. The Journal of Machine 2022.
Learning Research,
[95] Tengyang Xie, Ch Cheng, Nan Jiang, Paul Mineiro, and Alekh Agarwal. Bellman- consistent pessimism for offline reinforcement learning. Advances in neural information processing systems, 34:6683-666 6694, 2021.
[96] Huan Xu and Shie Mannor. Distributionally robust Markov decision processes. Advances in Neural Information Processing Systems, 23, 2010.
[97] Mengdi Xu, Zuxin Liu, Peide Huang, Wenhao Ding, Zhepeng Cen, Bo Li, and Ding Zhao. Trustworthy reinforcement learning against intrinsic vulnerabilities: Robustness, safety, and generalizability. arXiv preprint arXiv:2209.08023 2022.
[98] Zaiyan Xu, Kishan Panaganti, and Dileep Kalathil. Improved sample complexity bounds for distributionally robust reinforcement learning. In Francisco Ruiz, Jennifer Dy, and Jan- Willem de Meent, editors, Proceedings of The 26th International Conference Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 9728-9754 PMLR, 25 25-27 Apr 2023.
[99] Wenhao Yang. Liangyu Zhang, and Zhihua Zhang. Toward theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics. The Annals of Statistics, 50 (6):3223-33) -224, 2022.
[100] Pengqian Yu and Huan Xu. Distributionally robust counterpart Markov decision processes.
IEEE Transactions Automatic Control, (1(9):253-25444 2015.
[101] Xian Yu and Lei Ying. On the global convergence of risk-averse policy gradient methods with expected conditional risk measures. In Proceedings of the 40th International Conference on Machine Learning, pages 40425-40451, 2023.
[102] Wenhao Zhan, Baihe Huang, Audrey Huang, Nan Jiang, and Jason Lee. Offline reinforcement learning with realizability and single-policy concentrability. In Conference on Learning Theory, pages 2730-2775. PMLR, 2022.
[103] Huan Zhang, Hongge Chen, Chaowei Xiao, Bo Li, Mingyan Liu, Duane Boning, and Cho- Jui Hsieh. Robust deep reinforcement learning against adversarial perturbations state observations. Advances in Neural Information Processing Systems, 33:21024-21033 2020.
[104] Kaiqing Zhang, Bin Hu, and Tamer Basar. Policy optimization for H2 linear control with Hox robustness guarantee: Implicit regularization and global convergence. In Learning for Dynamics and Control, pages 199-190. PMLR, 2020.
[105] Zhengqing Zhou, Zhengyuan Zhou, Qinxun Bai, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite-sample regret bound for distributionally robust offline tabular reinforcement learning. In International Conference on Artificial Intelligence and Statistics, pages 3331-3339, PMLR,
2021.
15


Reviews:
[{"review_id": "sD1OiTYcGe", "reviewer": "Reviewer_SuJM", "summary": "This work introduces an alternative formulation of risk-sensitive MDP (RS-MDP in the sequel) that enables to show equivalence with regularized-RMDPs. Leveraging this equivalence, the authors derive a converging risk-sensitive policy-gradient method that asymptotically recovers the optimal value and policy of Markov RS-MDPs. Thus, they tackle the potential non-gradient domination of the Markov RS-MDP setting. Focusing on KL-regularized RMDP, an offline algorithm called RFZI is then introduced, that presumably improves upon the RFQI algorithm of [61] in terms of computational complexity and required assumptions.", "questions": "Questions:\n- I found the second paragraph of Sec. 1 quite confusing: \"when the model is given\", \"in cases of unknown models... most are model-based for tabular cases\", \"model-free setting\". How are the shortcomings mentioned in this paragraph addressed in the present work? How do the authors distinguish between \"unknown model\" and \"model-free\"? Does it refer to the uncertainty set or the nominal model? For example, in my understanding, [48] is model-free in the sense that it does not take the uncertainty set as given but estimates it from data. Accordingly, most robust learning approaches are model-based in the sense that they consider the uncertainty set to be known and solve robust planning from there. \n- Rmk 1 was also confusing to me. What do the authors mean by \"the boundary of the uncertainty set\"? What is a \"hard boundary\"? Referring here to the fact that $(\\hat{P}_t)_t$ are in the whole simplex for regularized RMDPs, as opposed to a specified uncertainty set $\\mathcal{P}$ in RMDPs would greatly help understanding the authors' motivation for that setting. Also, is this remark related to the discussion on \"model-free\" vs \"model-based\" in the intro? \n- Thm 1 seems to simply relate the double Fenchel conjugate with the original function. Is it what it does? If so, it would be useful to mention it in the text and if not, how is this result different? \n- Could you please provide an intuitive explanation as to why the value function is different from Markov risk measures of previous works when the policy is stochastic, but the same when it is deterministic?\n \n \nSuggested corrections: \n- Last line of Sec. 1: \"appendix\" without capital letter\n- Typo \"valule\" right before Eq. (7)\n- Eqs. (12), (14), (18) are numbered without being referred to in the text.\n- Missing capital letters in references: Markov in [6, 10, 32, 35, 36, 43, 48, 54, 59, 71, 94] and others, Bellman in [4]\n- Published/workshop papers should be referred as such: [16, 17, 20, 21, 22, 40, 44, 52, 61, 78, 85, 96]\n- I do not see the utility of the paragraph on finite-horizon (referred to as (*) in the following item), to explain the fixed point equation (7). This is standard in MDPs and would save some valuable space that seems to be missing in this work. Instead, it would be useful to briefly mention the properties of the operator (7) -- monotonicity, sub-distributivity, contraction -- and how they follow from those of the convex risk measure $\\sigma$. \n- Sec. 3 is very short. I would rather incorporate the \"risk-sensitive MDPs\"-paragraph of Sec. 2 into that one. \n- In general, I think that the authors could and should shrink some parts of the text to better motivate their approach, and defer some explanation details of their method to the appendix. For example, Ex. 2 could be removed/put into appendix, as it is not further used in the paper (as opposed to Ex. 1); the paragraph (*) could be removed completely. As such, instead of declaring \"Due to space limit, we defer a detailed literature review and numerical simulations to the appendix\", the authors could provide more synthetic exposition of their method, but detail more on its positioning w.r.t. previous works. Please see my questions in that respect. \n- In the same spirit of saving space, the \"other notations\" paragraph at the end of Sec. 2 could be written inline and deferred to the \"MDPs\" paragraph at the beginning of Sec. 2; Remarks may be written as regular text. \n- Typo in Assmp 1", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is well-written and the mathematical setting rigorously specified.\n\nThe reformulation via regularized-robustness to provide a converging policy-gradient is crafty.", "weaknesses": "- It would be preferable to give more space to motivate this work rather than explaining the method (see suggestions below)\n\n- To me it is a bit frustrating to see so many references in the bibliography with no discussion of them in the text body. Specifically, how does the regularization term of this work compare to [18]? Also, the regularized+robust objective considered in this work reminds that of [32] who also combine the two to derive a convex formulation of RMDPs. This leads me to the following question: does the same convex formulation applies to the authors' regularized RMDPs? Is it the aforementioned convex property that ensures gradient domination in this setting as well?  \n\n- As mentioned in Rmk 4, sampling from $\\hat{P}^{\\theta}$ rather than the nominal represents the main challenge in estimating the policy-gradient. In this respect, we refer to the work [101] that explicitly formulate the policy gradient in RMDPs: by focusing on $\\ell_p$-ball constrained uncertainty sets, the authors are able to explicitly derive the worst transition model and as a result, a robust policy-gradient that is more amenable to be estimated from nominal samples. In fact, I assume that specific assumptions on the convex risk measure $\\sigma$ can similarly be leveraged to explicit a risk-sensitive gradient. For example, departing from the equivalence between coherent risk measures and RMDPs with risk envelope, one may write a robust policy-gradient as in [101] and broaden the class of measures to be considered while preserving tractability of the gradient. \n\n- The offline learning part is a bit of an outlier in this paper. In particular, I do not understand the motivation to section 5. Simulation experiments on the other hand, would study the risk-sensitive behavior of regularized-robust optimal policies and compare them to robust optimal policies.  \n\n- It is not clear to me how the performance gap of Thm 5 compares to that of RFQI [61]. The authors briefly mention the computational cost incurred by introducing dual variables in [61], but the performance gap obtained from each approach should further be discussed. More generally, Sec. 5 raises several open questions without further discussing them, which is a bit frustrating: can Assm 2 be avoided? How to empirically select the penalty factor $\\beta$ and shrink the performance gap? Is the exponential dependence a proof artifact or is it intrinsic to the problem? \n\n[101] N. Kumar, E. Derman, M. Geist, K.Y. Levy, S. Mannor. Policy Gradient for Rectangular Robust Markov Decision Processes. *Advances in Neural Information Processing Systems*, 2023. https://arxiv.org/pdf/2301.13589.pdf", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "lbGmc3G8YT", "reviewer": "Reviewer_RSEz", "summary": "The paper presents an extension of robust MDP that replaces the uncertainty set for the uncertain transition matrix with a penalty for the adversary. Connections are made between this approach and risk sensitive MDPs when the policy is deterministic. For the case of a penalty of the form of KL divergence, the regularized robust MDP reduces to a risk averse MDP with a nested entropic risk measure. A value iteration approach à la Fei et al. (2021) is proposed to solve the problem. When a stochastic policy is used, the property of gradient domination under direct parametrization is established.", "questions": "The authors are invited to comment on the three main concern described above.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 2, "strengths": "The paper is very well written. The notation is clear and proofs appear all accurate based on the amount of time I could invest in checking them. The paper makes connection with many different streams of the literature: robust MPD, risk measures, gradient dominance, etc.", "weaknesses": "My main concerns are three-fold:\n\n1) Theorem 2 holds only for risk measures \\sigma that satisfy quasi-concave and does not hold if the policy is regularized. ﻿ ﻿ ﻿Indeed,  first I enocurage the authors to have a look at Delage et al. (2019) for an investigation of what risk measures have the mixture quasi-concave property and the implications in terms of optimality of randomized policies. Even in the case of mixture quasi-concave risk measures (such as CVaR and entropic risk measure), I find this result to be problematic. First, it implies that the regularized robust MDP will underestimate the risk of stochastic policies (as it is taking the average). Second, the equivalence fails if one include policy regularization which could force the optimal policy to become stochastic, thus misestimated by regularized RMDP. I would therefore limit the connection to a dynamic risk preference relation (see Pichlet et al. 2021) setting of the form:  RPR( [r_1,…, r_infty] ) = rho_0( r_1 + gamma E[ rho_1( r_2 + gamma E[ rho_2(… ) |a_2 ]|s_2)|a_1]).    where I would emphasize that the policies effect is treated as risk neutral and the transitions as risk averse.\n\n2) Many of the results appear to follow closely from existing work. ﻿     \nTheorem 1 comes from [27]. The equivalence between soft robust optimization and convex risk measure is already established in Ben-Tal et al. (2010). It is therefore no surprise that the result in theorem 2 would hold. Theorem 3, Lemma 2, and Theorem 4 extend the result of [85] from robust MPD to the slighlty more general regularized/soft robust MDP. Section 5 proposes an algorithm that resembles the approach presented in [24] although I am not aware of a sample complexity result for that class of algorithm.\n\n3) The concept of regularized robust is misleading. In problem (2) it is the adversarial transition probability matrix that is being regularized. This is completely different from regularizing the policy as is usually understood as \"regularized MDP”. I would suggesting calling it differently to avoid this confusion. Namely, in the robust optimization literature, the concept of regularizing the adversaries actions is referred as soft-robust, comprehensive robust, or globalized robust optimization (see references below).\n\n\nBen-Tal, S. Boyd, and A. Nemirovski. Extending scope of robust optimization: Comprehensive robust counterparts of uncertain problems. Mathematical Programming, 107(1-2):63–89, 2006.\n\nA. Ben-Tal, D. Bertsimas, and D. B. Brown. A soft robust model for optimization under ambiguity. Operations Research, 58(4-part-2):1220–1234, 2010\n\nA. Ben-Tal, R. Brekelmans, D. den Hertog, and J.-P. Vial. Globalized robust optimization for nonlinear uncertain inequalities. INFORMS Journal on Computing, 29(2):350–366, 2017.\n\nE. Delage, D. Kuhn, and W. Wiesemann, “Dice”-sion–Making Under Uncertainty: When Can a Random Decision Reduce Risk? Management Science, 65(7):3282-3301, 2019.\n\nA. Pichler, R. P. Liu, and A. Shapiro. Risk-averse stochastic programming: Time consistency and optimal stopping. Operations Research, 70:4, 2439-2455, 2021\n\n\nProof to verify:\nPage 34, in equation (25), it should be illustrated how the second inequality holds, which seems not obvious.\n\n\nTypos/clarifications:\n\nPage 5, in the middle \"Risk-Sensitive MDPs\" misspell \"Senstive\"\nPage 5, the line above equation (7), misspell \"valule\"\nPage 8, Assumption 1, \"For any policy pi and \" missing P\nPage 25, paragraph under section C, last part, repeat expression \"is defined as is defined as”\nPage 26, the notation would be clearer if the two “T^\\pi” and “T^*” operators were denoted as “bar T^\\pi” and “bar T^*” since they are defined in terms of the robust MDP\nPage 26, last part of Proof of Lemma1, \"Lemma 1 is an immediate corollary of Lemma 8\", it should be Lemma 3. \"\\tilde V and \\tilde V^\\star in (4) and (3)\", it should be (7) and (9).\nPage 27, in Lemma 4, the definition of \\mathcal{T}^* should be clarified.\nPage 28, In the proof of Lemma 4, \\mathbb{E}{s_1\\sim \\hat{P}{0}  should have a uniform expression as the passages above and below, i.e., \\mathbb{E}{s_1\\sim \\hat{P}{0;s_0,a_0}.\nIn line 4, there is a missing bracket in the last equation.\nPage 32, in Part G, the performance Difference Lemma [40] should be stated separately, as it has been applied a lot of times in the proofs. It is better to illustrate how this lemma is applied to this specific case.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "LQAWDKeupf", "reviewer": "Reviewer_BzBp", "summary": "The authors provide a sufficient condition for establishing the equivalence between the regularized robust MDPs and risk-sensitive MDPs, and provide the optimal policy for them when the condition is satisfied. Under some assumptions, the authors provide a quasi-policy gradient algorithm with a global convergence rate. They also provide KL-regularized RMDPs as an instantiation of their framework.", "questions": "- In section 2, the authors introduce convex risk measures, where there is only one input in the measure $\\sigma$ in (5) and (6), while there are two in examples 1 and 2. Could the authors explain what is the difference between these two $\\sigma$'s?\n\n- What is \"direct parameterization\"?\n\n- Is the right-hand side of (15) independent of the initial distribution $\\rho$?\n\n- About the feasible region $\\mathcal{X}$ of $\\theta$: why it is of dimension $SA$? And why each subvector $\\theta_s$ should be in the probability simplex?\n\n- Assumption 1, typo in the first sentence.\n\n- Assumption 3, what is the norm with subscript \"$2,\\mu$\"?", "limitations": "", "rating": 8, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "The theoretical contribution is inspiring. I like theorem 2 where the authors provide an elegant sufficient condition for the equivalence of regularized RMDPs and risk-sensitve MDPs.", "weaknesses": "Could the authors provide some examples where theorem 2 is applied to establish the equivalence between some popular regularized RMDPs and risk-sensitve MDPs?", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "2s7HK1BdKm", "reviewer": "Reviewer_KqgB", "summary": "The paper establishes an equivalence between a specific class of regularised robust Markov Decision Processes (MDP) and the risk-sensitive MDP. The authors derive the exact policy gradient method and demonstrate its global convergence in tabular-setting MDP. Specifically, the authors study the regularised MDP with KL divergence regularisation term, and design the sample-based offline learning algorithm, robust fitted-Z iteration.", "questions": "1. Within the framework of risk-sensitive MDP, the value function for a given policy $\\pi$, denoted as $\\tilde{V}^{\\pi}(s)$, is defined by equation (7). The optimal value function, $\\tilde{V}^\\star$, is defined as $\\max_{\\pi} \\tilde{V}^{\\pi}$. Could the authors elucidate how $\\tilde{V}^\\star$ satisfies the equation (9)?\n\n2. As noted in remark 7, the sample complexity of the proposed algorithm appears less favorable than that detailed in reference [11], assuming that there is no function approximation error in authors' approach, $\\epsilon_c = 0$. What then are the advantages of the corresponding RFZI algorithm?\nFurthermore, given the resemblance between Equations (7) and (9) and the traditional Bellman equation, and considering that the operators are proven contractions, is it feasible for the authors to employ value iteration or policy iteration to resolve the MDP? Such methods should theoretically exhibit rapid (geometric) convergence and remain unaffected by unknown exact gradients present in policy gradient methods.\n\n3. At the end of remark 7, the authors claim that the choice of $\\beta$ should not be too large or too small, and would be better if it is on the same scale with $1-\\gamma$. $\\beta$ is the radius of the ambiguity set related to transition kernel and $\\gamma$ is the discounted factor. It seems unconventional to determine the ambiguity set's radius based solely on the discount factor. Could this choice be elaborated upon?\n\n4. In 'E.2 Proof of theorem 2 (infinite horizon case)' on page 23, the authors claim that it is not hard to show $\\lim_{h\\to +\\infty} \\bar{V}^\\star_{0:h} = \\bar{V}^\\star, \\lim_{h\\to +\\infty} \\bar{V}^{\\pi}_{0:h} = \\bar{V}^{\\pi}$. This assertion doesn't immediately resonate with me. Would it be possible to furnish a detailed proof for this claim? Subsequent statements, $\\bar{V}^\\star = \\mathcal{T}^\\star \\bar{V}^\\star $ and $\\bar{V}^\\pi = \\mathcal{T}^\\pi \\bar{V}^\\star $ also require clarification.", "limitations": "", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "The paper bridges two distinct types of MDP, and introduces a policy gradient method to compute their solutions. The theoretical equivalences between these MDP types are intriguing. Moreover, the proposed algorithm demonstrates global convergence. The writing of the paper is good.", "weaknesses": "The framework of the robust MDP and risk-sensitive MDP is not clear enough: The authors fail to explicitly differentiate between stationary and non-stationary policies, as well as between stochastic and deterministic policies. While Equations (1) and (2) suggest that the authors are considering a robust MDP with a non-stationary and deterministic policy, Equations (7) and (8) indicate a stationary and stochastic policy for the risk-sensitive MDP. A similar inconsistency is observed in the transition kernel: while the robust MDP seems to consider the worst-case transition kernel for each time horizon (as evidenced by the decision variables in the infimum problem of Equations (1) and (2)), the risk-sensitive MDP presumes the existence of a transition kernel that is independent of time $t$.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (poster)