Twice regularized MDPs and the equivalence between robustness and regularization
Authors: Esther Derman
Matthieu Geist
Shie Mannor
Venue: NeurIPS 2021 Poster (2021)
Keywords: reinforcement learning
robust MDPs

Abstract: Robust Markov decision processes (MDPs) aim to handle changing or partially known system dynamics. To solve them, one typically resorts to robust optimization methods. However, this significantly increases computational complexity and limits scalability in both learning and planning. On the other hand, regularized MDPs show more stability in policy learning without impairing time complexity. Yet, they generally do not encompass uncertainty in the model dynamics. In this work, we aim to learn robust MDPs using regularization. We first show that regularized MDPs are a particular instance of robust MDPs with uncertain reward. We thus establish that policy iteration on reward-robust MDPs can have the same time complexity as on regularized MDPs. We further extend this relationship to MDPs with uncertain transitions: this leads to a regularization term with an additional dependence on the value function. We finally generalize regularized MDPs to twice regularized MDPs  (R${}^2$ MDPs), i.e., MDPs with $\textit{both}$ value and policy regularization. The corresponding Bellman operators enable developing policy iteration schemes with convergence and robustness guarantees. It also reduces planning and learning in robust MDPs to regularized MDPs.

Twice regularized MDPs and the equivalence between robustness and regularization
Esther Derman' Technion
Matthieu Geist Google Research, Brain Team
Shie Mannor Technion, NVIDIA Research
Abstract
Robust Markov decision processes (MDPs) aim to handle changing or partially known system dynamics. To solve them, one typically resorts robust optimization methods. However, this significantly increases computational complexity and limits scalability both learning and planning. On the other hand, regularized MDPs show more stability in policy learning without impairing time complexity. Yet, they generally
not encompass uncertainty in the model dynamics. In this work, we aim to learn robust MDPs using regularization. We first show that regularized MDPs are a particular instance of robust MDPs with uncertain reward. We thus establish that policy iteration reward-robust MDPs have the same time complexity as on regularized MDPs. We further extend this relationship to MDPs with uncertain transitions: this leads to regularization term with an additional dependence on the value function. We finally generalize regularized MDPs to twice regularized MDPs (R2 MDPs), i.e., MDPs with both value and policy regularization.
The corresponding Bellman operators enable developing policy iteration schemes with convergence and robustness guarantees. It also reduces planning and learning in robust MDPs to regularized MDPs.
Introduction
MDPs provide practical framework for solving sequential decision problems under uncertainty However, the chosen strategy can be very sensitive to sampling errors or inaccurate model estimates. This lead complete failure in common situations where the model parameters vary adversarially or are simply unknown [22]. Robust MDPs aim to mitigate such sensitivity by assuming that the transition and/or reward function (P,r) varies arbitrarily inside given uncertainty set U [17 (27). In this setting, an optimal solution maximizes performance measure under the worst-case parameters. It can be thought of as a dynamic zero-sum game with an agent choosing the best action while Nature imposes it the most adversarial model. As such, solving robust MDPs involves max-min problems, which can be computationally challenging and limits scalability.
30
In recent years, several methods have been developed to alleviate the computational concerns raised that consider specific types of coupled uncertainty sets, all rely on a rectangularity assumption without which the problem can be NP-hard This assumption is key deriving tractable solvers of robust MDPs such as robust value iteration 2 [1] or more general robust modified policy iteration (MPI) [18] Yet, reducing time
by robust reinforcement learning (RL). Apart from 23 24
2 40)
complexity in robust Bellman updates remains challenging and still researched today [15
At the same time, the empirical success of regularization policy search methods has motivated wide range of algorithms with diverse motivations such improved exploration [12 20 or
stability [34] [3]. Geist et al. [10] proposed a unified view from which many existing algorithms can be derived. Their regularized MDP formalism opens the path to error propagation analysis
CCntact author: estherddrrmanécappus technion.ac.11
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

in approximate MPI 33 and leads to the same bounds as for standard MDPs. Nevertheless, as we further show in Sec. policy regularization accounts for reward uncertainty only: does not encompass uncertainty in the model dynamics. Despite vast literature on how regularized policy search works and convergence rates analysis [3 [., little attention has been given to understanding why it can generate strategies that are robust to external perturbations [[3].
To our knowledge, the only works that relate robustness to regularization in RL are 66 [6
Derman & Mannor [6] employ a distributionally robust optimization approach to regularize an empirical value function. Unfortunately, computing this empirical value necessitates several policy evaluation procedures, which is quickly unpractical. Husain et al. [16] provide a dual relationship with robust MDPs under uncertain reward. Their duality result applies to general regularization methods and gives a robust interpretation of soft-actor-crite [T.. Although these two works justify the use of regularization for ensuring robustness, they do not enclose any algorithmic novelty. Similarly,
Eysenbach & Levine [9] specifically focus on maximum entropy methods and relate them to either reward or transition robustness. We shall further detail on these most related studies in Sec.
The robustness-rggularzzatio duality is well established in statistical learning theory [41 35 [9] as opposed to RL theory. In fact, standard setups such as classification or regression may be considered as single-stage decision-making problems, i.e., one-step MDPs, a particular case of RL setting. Extending this ceguustess--rgulaiiiaee robustness guarantees. As such, we introduce a regularization function Su that depends on the uncertainty set Ul and defined over both policy and value spaces, thus inducing a twice regularized Bellman operator (see Sec. (5. We show that this regularizer yields an equivalence of the form Ur = Un, where U7 is the robust value function for policy æ and Ur, the regularized one. This equivalence is derived through the objective function each value optimizes. More concretely, we formulate the robust value function Un 2 as an optimal solution of the robust optimization problem:
duality to RL would yield cheaper learning methods with
max (U, Po) s. t. v S inf T(,,)) (P.r)
(RO)
where ((,,)) is the evaluation Bellman operator [30. Then, we show that Un is also an optimal solution of the convex (non-robust) optimization problem:
max (u, po) s. t. v S " vER
v),
(CO)
where (Po,ro) is the nominal model. This establishes equivalence between the two optimization problems. Moreover, the inequality constraint of (CO) enables to derive twice regularized (R²) Bellman operator defined according to Sly a policy and value regularizer. For ball-constrained uncertainty sets, Der has an explicit form and under mild conditions, the corresponding R² Bellman operators are contracting. The equivalence between the two problems (RO) and (CO) together with the contraction properties of R Bellman operators enable to circumvent robust optimization problems at each Bellman update. As such, alleviates robust planning and learning algorithms by reducing them to regularized ones, which are known to be as complex classical methods.
To summarize, we make the following contributions: (i) We show that regularized MDPs are a specific instance of robust MDPs with uncertain reward. Besides formalizing a general connection between the two settings, our result enables to explicit the uncertainty sets induced by standard regularizers. (ii) We extend this duality to MDPs with uncertain transition and provide the first regularizer that recovers robust MDPs with s-rectangular balls and arbitrary norm. (iii) We introduce twice regularized MDPs (R2 MDPs) that apply both policy and value regularization to retrieve robust MDPs. We establish contraction of the corresponding Bellman operators. This leads us to proposing an R² MPI algorithm with similar time complexity as vanilla MPI, thus opening new perspectives towards practical and scalable robust RL.
Notations. We designate the extended reals by R: (-00, oo). Given a finite set 2, the class of
real-valued functions (resp. probability distributions) over Z is denoted by R (resp. Az), while the constant function equal to 1 over Z is denoted by 1z. Similarly, for any set X, A denotes the class of functions defined over X' and valued in Ag. The inner product of two functions a, b E R2 is defined as (a, b) := Exe a(=) b(=), which induces the 22-norm ||a|| := / /a, a). The no-m coincides with its dual norm, i.e., ||a||| = max 5 1 (a, b) =: ||a||.- -.l Let a function f TR 2 -, lr The Eegendre-Fencher transform (or convex conjugate) of f is f" (y) =- max {(a - ((a)}. Given set 3 C R² the characteristic function 03 : R² - R2 is (3(a) = 0 if E 3: +o0 otherwise.
The Legendre- Fenchel transform of 03 is the support function 03 (y) max.a3 (a. y) [ Ex. 1.6.1].
2

---

2
Preliminaries
This section describes the background material that we use throughout our work. Firstly, we recall useful properties in convex analysis. Secondly, we address classical discounted MDPs and their linear program (LP) formulation. Thirdly, we briefly detail on regularized MDPs and the associated operators and lastly, we focus on the robust MDP setting.
Convex Analysis. Let Az + R be strongly convex function. Throughout this study, the function plays the role of a policy and/or value regularization function. Its Legendre- Fenchel transform l2 satisfies several smoothness properties, hence its alternative name "smoothed max
operator" 25.. Our work makes use of the following result 25).
Proposition 2.1. Given Ω Az - R strongly convex, the following properties hold: (i) VΩ" is Lipschitz and satisfies (y) = arg m -((a), (l v E (ū) For any E y E IR2, (y +cl 2) = (y) + (iii) The Sogendre-Fencher transform Ω non-decreasing.
Discounted MDPs and LP formulation. Consider an infinite horizon MDP (S, A. Ho. r, with S and A finite state and action spaces respectively, < Mo As an initial state distribution and 7 E 10, a discount factor. Denoting X' == S x A, P E Ag is a transition kernel mapping each state-action pair to probability distribution over S and r Ex is reward function. A policy и E A maps any state 8 E S to an action distribution T E A, and we evaluate its performance through the following measure:
((T))
E
Σ (r((st; ur) No: n, P (uTP.r):
Here, the expectation is conditioned the process distribution determined by μo: ग and P, and for all s E S, "/ "Pp,,) (8) = E 7'r(s, as)]s0 = 8, π, P| is the value function at state 8. Maximizing IT defines the standard RL objective, which can be solved thanks to the Bellman operators:
T(p,ju:= r" + tpP Ve E T A
T(p:))== max (:p,o YUERS TEAS
((p,)(u) = E A U Ve E R.S.
where r5 := [T., (s, MoEs and p== (s'ls))))ss with PT P**(s(s)) == (T.. ((s'|s,) +)). Both Tip.. and T(P..) are 7-contractions with respect to (w.r..)) the supremum norm, so each admits unique fixed point "(r,)) and U(r,y) respectively. The set of greedy policies w.r.t. value v defines =
R.S. the associated function q E E. given by q(s, a) = -r(s + (P((ss, v) (ss E X. In particular, the fixed point ((r,)) satisfies ((rr)) = (Te. Tr.yy (s, )) where (r.r) is its associated q-function.
(v),)))), and any policy क E (G(P.))(((Pm)) is optimal 30 For all
The problem in (T) can also be formulated as LP 30). Given policy A we characterize its performance p(T) by the following L-LP 30 26
min (v, po) subject to (s.t.) 2 r" 7 V
(PT)
This primal objective provides a policy view on the problem. Alternatively, one may take a state visitation perspective by studying the dual objective instead:
max (T .1) S. t. 2 0 and (Idgs - - )p p4: PERS
(D*)
where pT is the adjoint policy transition operator [PT)](s) == Eses (s(33) Vu E RS, and Ids is the identity function in S Let ((s' dwms V(s, 5') E X x S the trivial transi- tion matrix and define its adjoint transition operator as I.J(s)) = E(R.)ex [[s|8, ()) E
It is the adjoint operator of pd in the sense that (P v²) (v. PTV) Ve,v E
3

---

S. The correspondence between occupancy measures and policies lies in the one-to-on mapping p(-)) f [x() TH and its inverse + Mr given by
26 (=(s,a) = En'P -8 8, = P0, P)
((s,a)&
As such, can interchangeably work with the primal LP P the dual D*).
Regularized MDPs. A regularized MDP is tuple (S, A. (4o 7, P. 12) with (8, A, no: 7, P, an infinite horizon MDP as above, and Ω : (St)ses finite set of functions such that for all 8 S, Q2 Aa - R strongly convex. Each function S2 plays the role of policy regularizer Ω (T.). With slight abuse of notation, shall denote by Q((T) (R, (T,))) lees the family of state-dependent regularizers The regularized Bellman evaluation operator is given by
[T (Pr) []({) = ((s)) - (T. Vo ER ,8ES,
and the regularized Bellman optimality operator by (P.r) mEX (P:y)) Vo E R 10 m. The unique fixed point of TTP., (respectively T(p..) ) is denoted by (P,r) (resp. u(Pr)) and defines the regularized value function (resp. regularized optimal value function). Although the regularized MDP formalism stems from the aforementioned Bellman operators in [0], turns out that regularized MDPs are MDPs with modified reward. Indeed, for any policy E A the regularized value [(x)), which corresponds to a non-regularized value with expected reward fa := r* - ?(T). Note that the modified reward F (s) is no longer linear in T. because of the strong convexity of S2g. Also, this modification does not apply to the reward function but only to its expectation r", as we cannot regularize the original reward without making policy-independent.
function 7. = (Is - -P*) '(Prr)
In general, the MDP model is not explicitly known but rather estimated from sampled trajectories. As this may result in over-sensitive outcome 22, robust MDPs reduce such performance variation. Formally, robust MDP (S, AA, Mo, 7,24) is an MDP with uncertain model
Robust MDPs.
belonging 4 := P x R. i.e., uncertain transition P E P C Ag and reward E R C R [7 40) The uncertainty set 24 typically controls the confidence level of model estimate, which in turn determines the agent's s level of robustness. It is given to the agent, who seeks to maximize performance under the worst-case model r) E U. Although untractable in general, this problem can be solved in polynomial time for rectangular uncertainty sets, i.e. when U Xsesú, XsES(P, x R.) For any policy क E A and state E S, the robust value function at F (s) == min(Pr))u (s) and the robust optimal value function oi (s) == max NEA a ( them is the unique fixed point of the respective robust Bellman operators:
40 23
Each of
(rFMo](3) == min T (s)) (Pr)ee
VU , AS
v])s) = max [T (s) YOERS, SE TEAS
which are 7-contractions. For all v E R the associated robust q-function is given by g(s, a) = (iniieeeeeuussss ()le((sss)+(()))) (PP()))))))))))))))))))))))))))) } V(s, a) E X, so that x (T,, 9thh 2l (() ())))) where x is
the robust fufncttion associated Td
3 Reward-robust MDPs
This section focuses reward-robust MDPs, iee, robust MDPs with uncertain reward but known transition model. We first show that regularized MDPs represent a particular instance of reward-robust MDPs, both solve the same optimization problem. This equivalence provides theoretical motivation for the heuristic success of policy regularization. Then, we explicit the uncertainty set
In the formalism of Geist et al. 10] St is initially constant over S. However, later in the paper 10 Sec. 5], it changes according to policy iterates. Here, we alternatively define family 1t of state-dependent regularizers. which accounts for dependee uncertainty sets (see Sec. 5 beloww.

---

underlying some standard regularization functions, thus suggesting an interpretable explanation of their empirical robustness.
We first show the following proposition 3.1 which applies to general robust MDPs and random policies. It slightly extends [17], Lemma 3.2 there focuses uncertain-transitto MDPs and deterministic policies. For completeness, we provide a proof of Prop. 3.1 in Appx.[A.
Proposition 3.1. For any policy x E A the robust value function o M is the optimal solution of the robust optimization problem:
max (e, po) s. U uor all (P.r) Eu. eck
(Pu)
In the robust optimization problem Pu the inequality constraint must hold over the whole uncertainty set U. As such, a function E R is said to be robust feasible for (uu) if S ((P,)) for all for all s E S. Therefore, checking
(P.r) E Ul or equivalently, if max(rs))eu - o(s) robust feasibility requires to solve maximization problem. For properly structured uncertainty sets, a closed form solution can be derived, as we shall see in the sequel. As standard in the robust RL the remaining of this work focuses uncertainty nominal model. Formallyy given Po (resp. TO) nominal transition kernel (resp. reward function), we consider uncertainty sets of the form (Po + P) x (ro + R). The size of P R quantifies our level of uncertainty or alternatively, the desired degree of robustness.
literature 32 15 I.
centered around known
Reward-robust and regularized MDPs: an equivalence. We now focus reward-robust MDPs, ie.. robust MDPs with 2 = [Po] (ro + R). Thm. 3.1 establishes that reward-robust MDPs are in fact regularized MDPs whose regularizer given by support function. Its proof can be found in Appx. A.2 This result brings two take-home messages: (i) policy regularization is equivalent to reward uncertainty; (ii) policy iteration reward-robust MDPs has the same convergence rate as regularized MDPs, which in turn is the same as standard MDPs [10.
Theorem 3.1 (Reward-robust MDP). Assume that U = (Po} x (ro + R). Then, for any policy A the robust value function n is the optimal solution of the convex optimization problem:
max (u, pu) S. t. v(s) S T(Po VERS
u(s) - OR. (- all s E S.
Thm. 3.1 clearly highlights a convex regularizer (2(TT)) = OR, (-Tx) vs E S. We thus recover regularized MDP by setting [T): TT u(s) (0,))-OR((-5)) (- Ws E S. In particular, when R, is ball of radius a', the support function (or regularizer) can be written in closed form as Ps (T.) of TT which is strongly convex. We formalize this below (see proof in Appx. A.3)
Corollary 3.1. Let A and U (Po) (ro + R). Further assume that for all E S, the reward uncertainty set at is R2 == fra R ||rall S a. Then, the robust value function = is the optimal solution of the convex optimization problem:
max (v. no) u(s) S ((....) of all E S. HERS
While regularization induces reward-robustnes, Thm. 3.1 and Cor. 3.1 suggest that, on the other hand, specific reward-robust MDPs recover well-known policy regularization methods. In the following section, we explicit the reward-uncertainty sets underlying some these regularizers.
Related Algorithms. Consider a reward uncertainty set of the form R == X x detines an (s, a) reettangula R (a particular type of s-rectangular R) whose rectangles R,, are independently defined for each state-action pair. For the regularizers below, we derive appropriate R2,a-S that recover the same regularized value function. Detailed proofs are in Appx.Ap. A.4 There, we also include a summary table that reviews the properties of some RL regularizers, as well as our R2 function which we shall introduce later Sec. 5 Note that the reward uncertainty sets here depend on the policy. This is due to the fact that standard regularizers are defined over the policy space and not each state-action pair. similarly explains why the reward modification induced by regularization does not apply to the original reward function, as already mentioned in Sec. 2
R..a- This
5

---

Negative Shannon entropy. Let R. (T) == [In (4/x(a)), t00) port function enables write:
v(s,a) E R. The associated sup-
max (x) (-Ta) r(s,))r(s,a" ER ", (x), EA4 aEA
-r(sa))To(a) = Σ (a)a) (n())(a)),
aEA
where the last equality comes from maximizing -7(s, a) over [In (o),(a)) +o0) for each A. We thus recover the negative Shannon entropy (T(TT)) = EaEA (a) In(TT, (a)) B
Kullback-Leibler divergence. Given an action distribution 0 < A let R (T) == In (d(a))
R.. (T) V(s,a) X. It amounts to translating the interval R by the given constant. Similarly writing the support function yields ((T.)) -EEE (a In (-. (a)aa((()) which is exactly the KL divergence [3]..
V(s X, we recover the Negative Tsallis entropy. Letting R. (T) == (0))2,00)/22-00
negative Tsallis entropy ((x,)) - +1, 1) 20
The equivalence between reward-robust and regular- ized MDPs leads us to wonder whether we can employ policy-gradies (37) on reward-robust MDPs using regularization. The following result establishes that a policy-gradient theorem can indeed be established for reward-robust MDPs (see proof in Appx. A.5).
Policy-gradient for reward-rohust MDPs.
Proposition 3.2. Assume that U = {Po} x (ro + R.) with R. = fr& E RAA, ||rl|l S o.)) Then, the gradient of the reward-robue objective (x) == (w M (a)) is given by
(1 a Te [2((a)
(u( = E(s,a)=p..
V Vinza(a))
|
where ja the occupancy measure under the nominal model Po and policy n.
Although Prop. 3.2 an application of [0 Appx. D.3] for a specific regularized MDP, its reward- robust formulation is novel and suggests another simplification of robust methods. Indeed, previous works that exploit policy-gradient on robust MDPs involve the occupancy measure of the worst- case model (21). whereas our result sticks to the nominal. In practice, Prop. 3.2 enables to learn a robust policy by sampling transitions from the nominal model instead of all uncertain models. This has twofold advantage: (i) it avoids an additional computation of the minimum done in 229 71. 77 where the authors sample next-state transitions and rewards based on all parameters from the uncertainty set, then update a policy based on the worst outcome; (ii) it releases from restricting to finite uncertainty sets. In fact, our regularizer accounts for robustness regardless of the sampling procedure, whereas the parallel simulations of [29 21 7 require the uncertainty set to be finite.
Technical difficulties are yet to be addressed for generalizing our result to transition-uncertall MDPs, because of the interdependence between the regularizer and the value function (see Secs, 5). We detail more on this issue in Appx. A.5
General robust MDPs
Now that we have established policy regularization as a reward-robust problem, we would like to study the opposite question: can any robust MDP with both uncertain reward and transition be solved using regularization instead of robust optimization? If so, is the regularization function easy to determine? In this section, we answer positively to both questions for properly defined robust MDPs. This greatly facilitates robust RL, as it avoids the increased complexity of robust planning algorithms while still reaching robust performance.
The following theorem establishes that similarly to reward-robust MDPs, robust MDPs can be formulated through regularization (see proof Appx. B. Although the regularizer is also support function in that case, it depends on both the policy and the value objective, which may further explain the difficulty of dealing with robust MDPs.
Theorem 4.1 (General robust MDP). Assume that U = (Po P) x (ro + R). Then, for any policy T A the robust value function i 1 the optimal solution of the convex optimization problem:
max (V,Po) (o) v(8) I The (()) OR. (- ) op, op, (- m,) for all 8 E E,S,
(2)
VERS
where (v- TT](s' a) (())) ((s E

---

The upper-bound in the inequality constraint 2 is of the same spirit as the regularized Bellman operator: the first term is a standard, non-regularized Bellman operator on the nominal model (Po. ro) to which we subtract policy and value-dependent function playing the role of regularization. This function reminds that of [6] Thm. 3.1] also coming from conjugacy. This is the only similarity between both regularizers: in [6], the Legendre- Fegechee-Fenchel transform is applied on a different type of function and results in a regularization term that has no closed form but can only be bounded from above. Moreover, the setup considered there is different since it studies distributionally robust MDPs. As such, it involves general convex optimization, whereas we focus on the robust formulation of an LP.
The support function further simplifies when the uncertainty set is a ball, as shown below. Yet, the dependence of the regularizer on the value function prevents us from readily applying the tool-set of regularized MDPs. We shall study the properties of this new regularization function in Sec. [
Corollary 4.1. Assume that U = (Po + P) x (ro + R) with Ps == {P, E R ||Pall S a.) and
R₂ == frxs E RA ||rs||| S og) for all E S. Then, the robust value function yat 14 is the optimal
solution of the convex optimization problem:
max (0,, v(s) S (()) VERS
01 - a. >//>>//||||==|0100 all 8 E.S. E.
(3)
One can actually take two different norms for the reward and the transition uncertainty sets. Similarly, Cor. 4.1 can be rewritten with an arbitrary norm, which would reveal a dual norm ||-I|- instead of
||-Il in Eq. 3 (see proof in Appx. B.2 Here, we restrict our statement to the f2-norm for notation convenience only, the dual norm of Eg being le itself. Thus, our regularization function recovers a robust value function independently of the chosen norm, which extends previous results from [ Indeed, Ho et al. [15] lighten complexity of robust planning for the -nnorm only, while Grand- Clément & Kroer [II focus on KL and & ball-constrained uncertainty sets. Both works rely on the specific structure induced by the divergence they consider to derive more efficient robust Bellman updates. Differently, our method circumvents these updates using generic, -ineee-nndeeendent regularization function while still encompassing s s-rectangular uncertainty sets as in [1
R MDPs
we showed that for general robust MDPs, the optimization constraint involves a regular- ization term that depends on the value function itself. This adds a difficulty to the reward-robust case where the regularization only depends on the policy. Yet, we provided an explicit regularizer for general robust MDPs that are coll-constrained. In this section, we introduce R MDPs, an extension of regularized MDPs that combines policy and value regularization. The core idea is to further regularize the Bellman operators with a value-dependent term that recovers the support functions we derived from the robust optimization problems of Secs. 34
In Sec. 4
Definition 5.1 (R² Bellman operators). For all v E R.S, define Qu AA + R as ( ==
|| [a + aaf (lll)))))). The R² Bellman evaluation and optimality operators are defined as
TT. x² v)(s) T T(P.))))))) ((s) - Q ( Ys E,
& ()( == max FEAR
[T u)(s) = 2 (a.) E.
For any function E RS, the associated unique greedy policy is defined as
Toe arg max TR v(s) VI" U. T,EDA
(qx),
Vs E S
that is, in vector form, π VΩ u. (4) = Go (v) = To.ik x
The R² Bellman evaluation operator is not linear because of the functional norm appearing in the regularization function. Yet. under the following assumption, it is contracting and we can apply Banach's 's fixed point theorem to define the R² value function.
Assumption 5.1 (Bounded radius). For all S, there exists c, > 0 such that
1-7-6- Eo
0 S min
min
PTPo--ls
7/88/
E ||ux||=1
V |
7

---

requires to upper bound the ball radius of transition uncertainty sets. The first term in the minimum is needed for establishing contraction of R Bellman operators (item (iii) in Prop. (..)). while the second one is used for ensuring monotonicity (item (i) in Prop. 5.1). We remark that the former depends on the original discount factor y: radius of must be smaller as y tends to but can arbitrarily grow decreases to O, without altering contraction. Indeed, larger implies longer time horizon and higher stochasticity, which explains why we need tighter level of uncertainty then. Otherwise, value and policy regularization seem unable to handle the mixed effects of parameter and stochastic uncertainties. The additional dependence on the state-space size comes from the
Asm. 5.1
22-norm chosen for the ball constraints. In fact, for any f--norm of dual fg. |S| replaces
/
in the denominator, so it becomes independent of |S] as (p. g) tends to (1, c0) (see Appx. C.1 Although we recognize a generalized Rayleigh quotient-type problem in the second minimum 28
its interpretation in our context remains unclear. Asm. Jenblles the R² Bellman operators to admit
a unique fixed point, among other nice properties. We formalize this below (see proof in Appx. C.I
Proposition 5.1. Suppose that Asm.
5.1 holds. Then, we have the following properties:
(i) Monotonicity: For all v1,02 E R- such that U1 I U2. we have T U1 S T
02 and
T 01 S TT* U2.
(ii) Sub-distributivityy For all U1 E C R, we have T (01 + cls) S T in + yells and T (v) + +clls) S T U1 + sclls, Vc E R.
(iii) Contraction: Let 6. == minges > 0. Then, for all U1,02 E R
x² | 11 7 v2 vo S - c.)ll - oo and || U1 T 12ll S (1 - E.)ll11 - U2 bloo.
We should note that the contracting coefficient in Prop. 5.1 is different from the original discount factor 7, since here we have 1 c² Yet, as Asm. 5.1 suggests it, an intrinsic dependence between ? and e* makes the R² Bellman updates similar the standard ones: when y tends to 0, the value of e" required for Asm. A.m] to hold increases, which makes the contracting coefficient 1 - E tend to 0 as well, i.e., the two contracting coefficients behave similarly. The contraction of both R² Bellman operators finally leads us to introduce the R² value functions.
Definition 5.2 (R2 value functions). (i) The R² value function v. is defined as the unique fixed point of the R² Bellman evaluation operator: u=. TT. g The associated q-function is 9T (s,a) = ro(s, a)= + + a), R.."). (ii) The R² optimal value function " is defined as the unique fixed point of the R² Bellman optimal operator: v* T y² x= The associated q-function is xx as.a)= = ro(s, a) + (Pa(-l a), oxxk))
The monotonicity of the R² Bellman operators plays a key role in reaching an optimal R² policy, as we show in the following. A proof can be found in Appx. C.2
Theorem 5.1 (R² optimal policy). The greedy policy π R² Ga, (v+ is the unique optimal
R policy, i.e., for all π E A5,,0T' = 2 u....
Remark 5.1. An optimal R² policy may be stochastic. This is due to the fact that our R² MDP framework builds upon the general s-rectangularity assumption. Robust MDPs with s-rectangular un- certainty sets similarly yield an optimal robust policy that is stochastic [40) Table 1]. Nonetheless, the
R² MDP formulation recovers deterministic optimal policy in the more specific (s a.a) rectangulla case, which is in accordance with the robust MDP setting (see proof in Appx. C.3
All of the results above ensure convergence of MPI in R² MDPs We call that method R² MPI and provide its pseudo-code in Alg. [ The convergence proof follows the same lines in [30]. More- over, the contracting property of the R² Bellman operator ensures the same convergence rate in standard and robust MDPs, ie.. a geometric convergence rate. On the other hand, R² MPI reduces the computational complexity of robust MPI by avoiding solve a max-min problem at each iteration, as this can take polynomial time for general convex programs. Advantageously, the only optimization involved in R² MPI lies in the greedy step: it amounts to projecting onto the simplex,
Algorithm 1: R² MPI
Result: Tk-1, Uk41
Initialize 2y R
while not converged do
Th+1 < 9R,- (vk); uk+1 < (T 1. ym
end
A 'The stochasticity of an optimal regulariid policy as in the examples of Sec. 3 is not contradicting. Indeed, even though the corresponding uncertainty set is (s, a) rectaangula there, it is policy-depender
8

---

which can efficiently be performed in linear time | Still, such projection is not even necessary in the (s, reeetanuul case: as mentioned in Rmk. 5.1 it then suffices to choose a greedy action in order to eventually achieve an optimal R² value function.
6 Numerical Experiments
We aim to compare the computing time of R² MPI with that of MPI 300 and robust MPI [8] The code is available at https: tttt:::/ggithb..... com/ / Esstteerrrrrmm///mag on an Intel(R) Core (MM) 17-1068NG7 CPU @ 2.30GHz machine, which we test on a x 5 grid-world domain. In that environment, the agent starts from random position and seeks to reach goal state in order to maximize reward. Thus, the reward function is zero in all states but two: one provides a reward of I while the other gives 10. An episode ends when either one of those two states is attained.
To do so, we run experiments
The partial evaluation of each policy iterate is a building block of MPI. As a sanity check, we evaluate the uniform policy through both R² and robust policy evaluation (PE) sub-processes, to ensure that the two value outputs coincide. For simplicity, we focus on an (s, r--tttnagall uncertainty set and take the same ball radius (resp. (3) at each state-action pair for the reward function (resp. transition function). Parameter values and other implementation details are deferred to Appx. D We obtain the same value for R² PE and robust PE, which numerically confirms Thm. 4.1 On the other hand, both are strictly smaller than their non-robust, non-regularized counterpart, but as expected, they converge to the standard value function when all ball radii tend to 0 (see Appx. D More importantly, R PE converges in 0.02 seconds, whereas robust PE takes 54.8 seconds to converge, i.e., 2740 times longer. This complexity gap comes from the minimization problems being solved at each iteration of robust PE, something that R² PE avoids thanks to regularization. R² PE still takes 2.5 times longer than its standard, non-regularized counterpart, because of the additional computation of regularization terms. Table shows the time spent by each algorithm until convergence.
Table I: Computing time (in sec.) of planning algorithms using vanilla, R and robust approaches. Each cell displays the mean + standard deviation obtained from running seeds.
Vanilla
R
Robust
PE
0.008 + O.
0.02 + O.
54.8 + 1.2
MPI (m = 1)
0,01 + O.
0.03 + O.
118.6 + 1.3
MPI (m = 4)
0.01 + O.
0.03 + O. 98.1 + 4.1
We then study the overall MPI process for each approach. We know that in vanilla MPI, the greedy step is achieved by simply searching over deterministic policies (30]. Since we focus our experiments on an (s, recttnnagl uncertainty set, the same applies to robust MPI 44) and to R² MPI, as already mentioned in Rmk. [.T] We can see in Table that the increased complexity of robust MPI even more prominent than its PE thread, as robust MPI takes 3953 (resp. 3270) times longer than R² MPI when m = 1 (resp. m = 4). Robust MPI with m 4 is bit more advantageous than m 1, as it needs less iterations (31 versus 67). i.e.. less optimization solvers to converge. Interestingly, for both m E (1, 43, progressing from PE to MPI did not cost much more computing time to either the vanilla or the R² version: both take less than one second run.
7 Related Work
Connections between regularization and robustness have been established in standard statistical learning settings such as support vector machines [41], logistic regression (35) or maximum likelihood estimation [19]. As stated in Sec. [ these represent particular RL problemss as they concern a single-stage decision-makee maainn process. In that regard, the generalization of robustness-regularizttoo duality to sequential decision makingg has seldom been studied in the RL literature.
Two works that view policy regularization from a robustness perspective are [66 and 9 In [6]
regularization is applied on the dual objective instead of the primal. This has two shortcomings: (i)
prevents from deriving regularized Bellman operators and dynamic programming methods; (ii)
The feasible set is that of occupancy measures, so the connection with standard policy regularization remains unclear. Furthermore, their work focuses on reward robustness. Differently, Eysenbach &
Levine [9] address both reward and transition uncertainty by showing that policies with maximum

---

entropy regularization solve particular type of robust MDP. Yet, their amalysis separately treats the uncertainty on P and r, which questions the robustness of the resulting policy when the whole model (P,r) is adversarial. Moreover, the dual relation they establish between entropy regularization and transition-robus MDPs is weak and applies to specific uncertainty sets. Both of these works treat robustness as a side-effect of regularization more than an objective on its own, whereas we aim to do the opposite, namely, use regularization to solve robust RL problems.
Derman & Mannor 6 similarly use regularization as a tool for achieving robust policies. Through distributionally robust MDPs, they show upper and lower bounds between transition-robustnsss robustness and regularization. There again, duality is weak and reward uncertainty is not addressed. Moreover, since the exact regularization term has no explicit form, is usable through its upper bound only. Finally, regularization is applied on the mean of several value functions "[ "(,,r)' where each P; is a transition model estimated from an episode run. Computing this quantity requires as many policy evaluations as the number of model estimates available, which results in a linear complexity blowup at least.
Previous studies analyze robust planning algorithms to provide convergence guarantees, The works 27 propose robust value iteration, while 17 40 introduce robust policy iteration. Kaufman & Schaefer [8]] generalize both schemes by proposing a robust MPI and determine the conditions under which it converges. The polynomial time within which all these works guarantee a robust solution is often insufficient, as the complexity of Bellman update grows cubically in the number of states [15].
In order reduce the time complexity of robust planning algorithms, Ho al. [5] propose two algo- rithms that compute robust Bellman updates in [| [og([S)|AA) operations for & -onotsatadde uncertainty sets. Advantageously, our regularization approach reduces each such update to its stan- dard, non-robust complexity of (((S)IA) Moreover, although Ho et al. [IS] address both (s, a) and s-rectangular uncertainty sets, they focus on transition uncertainty, whereas we tackle both reward and transition uncertainties in the general s-rectangular case. Finally, their contribution relies on LP formulations that necessitate restricting to the f f1-orrm while our method applies to any norm. This duality 31 a generalization of LP duality (see Appx. A.2 and I. More recently, Ceemm-teément & Kroer [1I propose first-order method to accelerate robust value iteration under s- s-rectangular uncertainty sets that are either ellipsoidal or Kl.-constrained. To our knowledge, our study is the first one reducing the time complexity of robust planning when the uncertainty set is s-rectangular and constrained with an arbitrary norm.
may come from the fact that our main Theorems (Thms, 3.1 and 4.1 use
8 Conclusion and future work
In this work, we established strong duality between robust MDPs and twice regularized MDPs. This revealed that the regularized MDPs of [10] are in fact robust MDPs with uncertain reward, which enabled us derive a policy-gradient theorem for reward-robust MDPs. When extending this crausttees-regllaiizatit
duality to general robust MDPs, we found that the regularizer depends on the value function besides the policy. We thus introduced R² MDPs, a generalization of regularized MDPs with both policy and value regularization. The related R Bellman operators lead us to propose a converging R² MPI algorithm that achieves the optimal robust value function within similar computing time as standard MPI.
This study settles the theoretical foundations for scalable robust RL. We should note that our results naturally extend to continuous but compact action spaces in the same manner as standard MDPs do 30 Extension to infinite state-space would be more involved because of the state-dependent regular- izer in R² MDPs. In fact, it would be interesting to study the R² MDP setting under function approx- imation, as such approximation would have a direct effect on the regularizer. Similarly. one could an- alyze approximate dynamic programming for R² MDPs in light of its robust analog [38] [ Although our theory focused on planning, the R Bellman operators and their contracting properties open the path to learning algorithms that can (i) use existing RL algorithms and robustify them by simply chang- ing the regularizer; (ii) scale to deep learning settings. Apart from its practical effect, we believe our work opens the path to more theoretical contributions in robust RL. For example, extending R MPI to the approximate case 33 would be an interesting problem to solve because of the R² evaluation operator being non-linear. So would be a sample complexity analysis for R² MDPs with comparison to robust MDPs 42). Another line of research to extend policy-gradicn to R² MDPs, as this would avoid parallel learning of adversarial models ? 39 and be very useful for continuous control.
10

---

Acknowledgements
We would like thank Raphael Derman for his useful suggestions that improved the clarity of the text. Thanks also to Stav Belogolovsky for reviewing a previous version of this paper. Funding in direct support of this work: ISF grant.
References
[1] Badrinath, K. and Kalathil, D. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference on Machine Learning, pp. 511-520. PMLR, 2021.
[2] Bagnell, J. A., Ng, A. and Schneider, J. G. Solving uncertain Markov decision processes. 2001.
[3] Bertsekas, D. P. Comvex optimization theory. Athena Scientific Belmont, 2009.
[4] Borwein, J. and Lewis, A. S. Convex analysis and nonlinear optimization: theory and examples. Springer Science Business Media, 2010.
[5] Cen, S., Cheng, C., Chen, Y., Wei, Y., and Chi, Fast global convergence of natural policy gradient methods with entropy regularization. arXiv preprint arXiv:2007.065558 2020.
[6] Derman, E. and Mannor, S. Distributional robustness and regularization in reinforcement learning. ICML Workshop, 2020.
[7] Derman, E., Mankowitz, D., Mann, T., and Mannor, S. Soft-robust actor-critic
AUAI press for Association for Uncertainty in Artificial Intelligence, pp. 208 208,218, 2018.
[8] Duchi, J., Shalev-Shwarte S., Singer, Y., and Chandra, T. Efficient projections onto the I 1-ball for learning in high dimensions. In Proceedings of the 25th international conference on Machine learning, pp. 272-279, 2008.
[9] Eysenbach, B. and Levine. Maximum entropy RL (provably) solves some robust RL problems. arXiv preprint 1rXiv:2103.06::: 2021.
[10] Geist, M., Scherrer, B., and Pietquin, O. A theory of regularized Markov decision processes, In International Conference on Machine Learning, pp. 2160-2169. PMLR, 2019.
[11] Grand-Clément J. and Kroer, Scalable first-order methods for robust mdps. Proceedings of the AAAI Conference Artificial Intelligence, volume 35, pp. 12086-12094, 2021.
[12] Haarnoja, T., Tang, H., Abbeel, P., and Levine, S. Reinforcement learning with deep energy- based policies. In International Conference on Machine Learning, pp. 1352-1361. PMLR, 2017.
[13] Haarnoja, T., Zhou, A., Abbeel, P., and Levine, S. Soft actor-critic: Off-policy maximum entropy deep reinforcement learning with a stochastic actor. In International Conference on Machine Learning, pp. 1861-1870. PMLR, 2018
[14] Hiriant-Urutty J.-B. and Lemaréchal, C. Fundamentals of convex analysis. Springer Science & Business Media, 2004.
[15] Ho, C. P., Petrik, M., and Wiesemann, W. Fast Bellman updates for robust MDPs. In Interna- tional Conference on Machine Learning, pp. 1979-1988. PMLR, 2018.
[16] Husain, H., Ciosek, K., and Tomioka, Regularized policies are reward robust. In International Conference on Artificial Intelligence and Statistics, pp. 64-72. PMLR, 2021.
[17] Iyengar, G. N. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280. 2005.
[18] Kaufman, L.. and Schaefer, A. Robust modified policy iteration. INFORMS Journal on Computing, 25(3):396-444 -409,64----66 2013.

---

[19] Kuhn, D., Esfahani, P. M., Nguyen, V. A., and Shaficezadeh-Abadee S. Wasserstein distri- butionally robust optimization: Theory and applications in machine learning. In Operations Research & Management Science in the Age of Analytics, pp. 130-166. INFORMS, 2019.
[20] Lee, K., Choi, S., and Oh, S. Sparse Markov decision processes with causal sparse Tsallis entropy regularization for reinforcement learning. IEEE Robotics and Automation Letters, 3(3): 1466--173, 1473, 2018.
[21] Mankowitz, D., Mann, T., Bacon, P.-L., Precup, D., and Mannor, S. Learning robust options. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[22] Mannor, S., Simester, D., Sun, P., and Tsitsiklis, J. N. Bias and variance approximation in value function estimates. Management Science, 53(2):308-322, 2007.
[23] Mannor, S., Mebel, O., and Xu, H. Lightning does not strike twice: Robust MDPs with coupled uncertainty. ICML, 2012.
[24] Mannor, S., Mebel, O., and Xu, H. Robust MDPs with k-rectangular uncertainty. Mathematics of Operations Research, 1144):448-1150, 2016.
[25] Mensch, and Blondel, Differentiable dynamic programming for structured prediction and attention. In International Conference on Machine Learning, pp. 3462-3471, PMLR, 2018.
[26] Nachum, O. and Dai, B. Reinforcement learning via Cenchel-RRocafellle duality. arXiv preprint arXiv:2001.00 000000...166,.... 2020.
[27] Nilim, A. and El Ghaoui, L. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
[28] Parlett, B. N. The Rayleigh quotient iteration and some generalizations for nonnormal matrices. Mathematics of Compulation, 28( 28(117):679-693) 1974.
[29] Pinto, L., Davidson, J., Sukthankar, R., and Gupta, A. Robust adversarial reinforcement learning. In International Conference on Machine Learning, pp. 2817-2826. PMLR, 2017.
[30] Puterman, M. L. Markov decision processes: discrete stochastic dynamic programming. John Wiley & Sons, 2014.
[31] Rockafellar, R. T. Convex analysis, volume 36. Princeton university press, 1970.
[32] Roy, A., Xu, H., and Pokutta, S. Reinforcement learning under model mismatch. NIPS, 2017.
[33] Scherrer, B., Ghavamzadeh, M., Gabillon, V., Lesner, B., and Geist, M. Approximate modified policy iteration and its application the game of Tetris. J. Mach. Learn. Res., 16:1629-1676. 2015.
[34] Schulman, J., Levine, S., Abbeel, P., Jordan, M., and Moritz, P. Trust region policy optimization. In International conference on machine learning, pp. 1889-1897. PMLR, 2015.
[35] Shafieezadeh-Abaddhh. S., Esfahani, P. M., and Kuhn, D. Distributionally robust logistic regression. NIPS, 2015.
[36] Shani, L., Efroni, Y., and Mannor, S. Adaptive trust region policy optimization: Global convergence and faster rates for regularized MDPs. In Proceedings of the AAAI Conference Artificial Intelligence, volume 34, pp. 5668-5675, 2020.
[37] Sutton, R. S., McAllester, D. A., Singh, S. P., Mansour, Y., et al. Policy gradient methods for reinforcement learning with function approximation. In NIPs, volume 99, pp. 1067-1063. Citeseer, 1999.
[38] Tamar, A., Mannor, S., and Xu, H. Scaling up robust MDPs using function approximation. In International Conference Machine Learning, pp. 181-189, PMLR, 2014.
[39] Tessler, C., Efroni, Y., and Mannor, S. Action robust reinforcement learning and applications in continuous control. International Conference on Machine Learning, pp. 6215-6224, PMLR, 2019.
12

---

[40] Wiesemann, W., Kuhn, D., and Rustem, B. Robust Markov decision processes. Mathematics of Operations Research, 38(1):153-183, 2013.
[41] Xu, H., Caramanis, C., and Mannor, S. Robustness and regularization of support vector machines. Journal of machine learning research, 10(7), 2009.
[42] Yang, W. and Zhang, Z. asn-asymptotic performances of Robust Markov Decision Processes. arXiv preprint arvi 105. 038633 2021.
13

---

Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] The main contributions are consistently listed in the abstract and introduction. These are: Showing that regularized MDPs are particular instance of robust MDPs with uncertain reward (Sec. B): Extending this relationship to MDPs with uncertain transitions (Sec. 4 Generalizing regularized MDPs to R MDPs (Sec.
(b) Did you describe the limitations of your work? [Yes] These are described when discussing Prop. 3.2 and Asm. 5.1 near the corresponding statements.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] Assumptions are introduced by "Assume that..." " or "If..." in each theoretical result.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs can be found in the Appendix. At each theoretical statement in the text body, we precisely refer to the corresponding proof.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed reproduce the main perimental results (either the supplemental material or as a URL)? [Yes] The code available at /nttps://githui:
www com//sstherDeerma//rnittt all instructions needed to reproduce the results.
which includes
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] These are included in the experiments section (Sec. (6) and detailed in Appx.
(c) Did you report error bars (e.g., with respect to the random seed after running exper- iments multiple times)? [Yes] [ mean + standard deviation for each type of experiment, The figure plots in Appx. D also include error bars.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] See Sec.
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(c) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you deseribe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
14


Reviews:
[{"review_id": "uZC2TpeS_u1", "reviewer": "Reviewer_NyMe", "summary": "The paper highlights two limitations of current approaches for Robust RL: \n\n1. Robust optimization methods are computationally demanding.\n2. They do not account for uncertainty in the model dynamics.\n\nThe paper proposes to work around these limitations by learning robust MDPs using regularization. Their contributions are the following:\n\n1. Showing that regularized MDPs are an instance of Robust MDPs with uncertain rewards; thus, policy iteration on reward-robust MDPs has the same time complexity as on regularized MDPs \n2. Extend point 1 to MDPs with the uncertain transition.\n3. Generalize regularized MDPs to twin regularized MDPs to retrieve robust MDPs.", "questions": "", "limitations": "", "rating": 7, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Strengths:\n\n1. The paper is well-contained. I am not familiar with Robust RL and even less familiar with work in theoretical RL. Still, I had no difficulty reading the paper and understanding its central claims/contributions.  Kudos to the authors.\n2. I think the theoretical contributions are substantial and useful - connecting regularized MDPs to robust MDPs, extending the approach for uncertain dynamics function, etc. Though I should highlight that robustness/theory is not my area of expertise, so I might be over-estimating this contribution.\n\nQuestions / suggestions for improvement\n\n1. Line 170 mentions a nominal model. How do we get access to this model? Is it part of the problem formulation, or is it learned using the sampled trajectories? If it is learned, how do we ensure that the nominal model is correct?\n\n2. The paper mentioned that one of the limitations of existing approaches is that they are computationally demanding. I may have missed it, but it seems that the paper did not include any evidence for the twin regularized MDPs to be computationally more efficient.  Line 177 mentions that \"policy iteration on reward-robust MDPs has the same convergence rate as regularized MDPs, which in turn is the same as standard MDPs.\" Still, it would be helpful to include both the convergence rates and error bounds in the main paper (for both the proposed approach and the standard robustness-based approaches) to provide a complete comparison. For example, regularized MDPs are a particular case of robust MDPs. So other robustness methods may have a slower convergence rate but achieve better performance. The paper can be improved by including these tradeoffs explicitly.\n\n3. Missing empirical evidence - I understand that this paper is focusing on theoretical contributions. It may strengthen the paper to include some experimental results as well (even if it is on simplistic grid worlds). ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations And Societal Impact are addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "syz8GOUDlJz", "reviewer": "Reviewer_sP9P", "summary": "This paper formalized robust MDPs as general MDP with regularization. They first show that regularized MDPs are equivalent to MDPs with uncertain rewards. They also derive a regularized MDP formulation for robust MDPs with uncertain transitions. And they finally generalize a regularized MDP that can handle both reward and transition uncertainty. They argue that their regularized MDP framework provides better computational complexity and scalability compared to traditional robust optimization techniques.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "In lines 58-64, many quantities like v, \\mathcal{U}, \\mu etc. start appearing from no where. They were not defined before. This section needs reorganization making sure that everything is defined before referred or used.\n\nIt is possible to solve the reward robust MDP as a linear programming problem. The paper presents a policy gradient algorithm for the same purpose. How do they compare?\n\nThe theories presented in the paper look good from a high level. Though a rigorous verification of the correctness was not possible due to time constraint.\n\nIt is understandable that the paper is mostly theoretical, but one big weak point is not having any empirical analysis of the methods. How about having an empirical evaluation for robust and proposed regularized methods, possibly with different RL regularizers?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Limitations and impacts are addressed.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "YbmNk0Kssj", "reviewer": "Reviewer_FBfb", "summary": "The paper studies the connection between robust and regularized MDPs. The authors first show that solving robust MDPs with uncertain rewards is equivalent to solving regularized MDPs with a suitable policy-dependent regularization. Then, they extend this result to MDPs with uncertain transitions, obtaining the equivalence with both policy and value regularization. Finally, they propose R^2 MDPs, i.e., MDPs with both value and policy regularization for which, under certain assumptions, they guarantee good properties (eg contraction) for the corresponding Bellman operators and thus convergence of a modified policy iteration scheme. This allows solving robust MDP problems with the same computational cost as regularized ones.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "Significance, novelty, and relevance\n---\n\nThe paper considers a relevant problem, that of robust RL and, in particular, planning in robust MDPs, where reducing the computational complexity of Bellman updates is an important open area of research. While there have been many works that addressed this topic and the related one of regularized MDPs, to my knowledge, the contributions of this paper are novel. Overall I found this contribution interesting and significant. \n \n\nRelation with prior work\n---\n\nTo my knowledge, relevant prior works are discussed.\n\n\nClarity of writing\n---\n\nI found the paper well-written and easy to read. I think the authors did a good job in discussing and providing intuition for all results.\n\n\nDetailed comments/questions\n---\n\n1. One limitation of this work is that no numerical result is provided. I know this is mostly theoretical work, but, since the final impact is on algorithms for solving robust MDPs (and a new algorithm is even provided), it would be good to see at least some experiments. For instance, it would be good to compare the MPI scheme for learning robust policies of Section 5 with existing robust DP methods (both in terms of convergence speed and computational cost), or to test the policy gradient derived in Section 3, possibly comparing with the existing related techniques mentioned in that section.\n\n2. Theorem 5.1 proves that the optimal policy for R^2 MDPs is unique and, I assume, such a policy could be stochastic due to the regularization term. On the other hand, if I am not mistaken, for robust MDPs an optimal deterministic policy exists under certain conditions. So are there problems where there exists an optimal deterministic robust policy but solving the corresponding R^2 MDP we find only a stochastic one? If this is the case, it could be a potential limitation of using regularized methods, as in practice deterministic policies are desirable and we might not be able to find them using this alternative technique.\n\n3. I appreciated that the authors showed (in Section 3) what are the uncertainty sets corresponding to common regularizers adopted in the literature. However, do the uncertainty sets presented in Section 3.2 make any sense in the robust RL literature? They only depend on the policy for which we are evaluating the regularizer and not on other MDP-related quantities (such as how uncertain we are about the rewards etc.). Some policy-dependent uncertainty sets were studied in [1], but still I do not see any connection with those reported here.\n\n4. This paper considers finite states and actions, while most of the adopted \"functional/operator-based\" notation can be used also for more general state-action spaces. Do the results presented here easily extend to, say, countably infinite or continuous state-action spaces?\n\n5. Line 132 mentions that regularized MDPs are standard MDPs with a modified reward function. Still, it should be mentioned that, while it is true that we can modify the expected reward r^\\pi(s) of any policy \\pi by including the regularizer, we cannot do the same for the original reward r(s,a) without making it policy-dependent (e.g., I am thinking about the standard entropy regularizer).\n\n6. R^2 MDPs are introduced only for ball-constrained uncertainty sets, which yields the convenient norm-based regularization terms of Corollary 4.1. What about more general regularizers/uncertainty sets (e.g., KL-based)? Is it possible to obtain similar results?\n\n7. The contraction property in Prop. 5.1 is wrt to 1-\\epsilon_\\star and not \\gamma. So, while there is a computational gain wrt solving a robust MDP using classical techniques, could there be that the convergence rate of Bellman backups in the R^2 regularized MDP is much slower than in a standard regularized/unregularized MDP?\n\n\nMinor:\n- Line 99: is q a typo?\n- Line 105: the notation for \\Delta with both superscript and subscript was not introduced\n- Prop. 3.2: is the subscript R^2 of J a typo? Also, in the main result there it is not clear under what MDP \\mu_\\pi is computed (though later the text mentions it is wrt the nominal model)\n\n[1] Tirinzoni, Andrea, and Xiangli Chen. \"Policy-conditioned uncertainty sets for robust Markov decision processes.\" Advances in neural information processing systems (2018).", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors discuss some of the limitations of their work, while there might be others that could be mentioned (see above). I do not see any societal impact.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "KKtcVKvvG1K", "reviewer": "Reviewer_qvyT", "summary": "The paper establishes an equivalence between regularized MDPs and robust MDPs. The first main result shows that policy-regularized MDPs are equivalent to reward-robust MDPs, gives examples of equivalences between common regularizers and uncertainty sets, and gives a policy gradient algorithm for reward-robust MDPs. The second main result extends the equivalence to robust MDPs with both reward and transition uncertainty. The third main result introduces R^2 MDPs, which extend regularized MDPs with a value regularizer. It is shown that under certain assumptions on the uncertainty sets, the equivalent R^2 MDP can be solved with MPI.", "questions": "", "limitations": "", "rating": 8, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "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": "", "main_review": "## Originality\n\nI am not familiar with the literature in this area, but the paper claims all 3 main results as original. Related work is covered thoroughly.\n\n## Quality\n\nI don't have the mathematical background to verify the analysis. The statements of the results are precise and seem to include all required assumptions. The work addresses both the narrower case of reward-robust MDPs as well as the case of general robust MDPs, and provides both a construction of the equivalent regularized problems and a solution algorithm.\n\n## Clarity\n\nThe paper is clearly-written but is fairly dense. Mathematical notation is precise.\n\n## Significance\n\nEach of the main results seems to be significant on its own. The connection between regularization and robustness seems like it will be fertile for further analyses. The MPI algorithm for R^2 MDPs is significant in that it establishes that R^2 MDPs with appropriate assumptions have the same complexity as ordinary MDPs, making them a tractable subset of robust MDPs.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The paper clearly states the assumptions needed for its analysis, which seem to be the only significant limitations. I see no potential for negative societal impact.", "review_text": "", "extra_scores": {"ethical_concerns": "None", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}]

Author rebuttal:

Meta-review: All but one reviewer recommend publication.  The one who does not is concerned about the lack of empirical results, but I think this is a topic of interest to the community and its reasonable to have a purely theoretical paper on this.
Decision: Accept (Poster)