Twice regularized MDPs and the equivalence between robustness and regularization
Year: 2021

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

heading: 1 Introduction
text: MDPs provide a practical framework for solving sequential decision problems under uncertainty [30]. However, the chosen strategy can be very sensitive to sampling errors or inaccurate model estimates. This can lead to 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 a given uncertainty set U [17, 27]. In this setting, an optimal solution maximizes a 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.
In recent years, several methods have been developed to alleviate the computational concerns raised by robust reinforcement learning (RL). Apart from [23, 24] that consider specific types of coupled uncertainty sets, all rely on a rectangularity assumption without which the problem can be NP-hard [2, 40]. This assumption is key to deriving tractable solvers of robust MDPs such as robust value iteration [2, 11] or more general robust modified policy iteration (MPI) [18]. Yet, reducing time complexity in robust Bellman updates remains challenging and is still researched today [15, 11].
At the same time, the empirical success of regularization in policy search methods has motivated a wide range of algorithms with diverse motivations such as improved exploration [12, 20] or stability [34, 13]. 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 ∗Contact author: estherderman@campus.technion.ac.il
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
in approximate MPI [33] and leads to the same bounds as for standard MDPs. Nevertheless, as we further show in Sec. 3, policy regularization accounts for reward uncertainty only: it does not encompass uncertainty in the model dynamics. Despite a vast literature on how regularized policy search works and convergence rates analysis [36, 5], little attention has been given to understanding why it can generate strategies that are robust to external perturbations [13].
To our knowledge, the only works that relate robustness to regularization in RL are [6, 16, 9]. 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-critic [13]. 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. 7.
The robustness-regularization duality is well established in statistical learning theory [41, 35, 19], 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 robustness-regularization duality to RL would yield cheaper learning methods with robustness guarantees. As such, we introduce a regularization function ΩU that depends on the uncertainty set U and is 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 vπ,U = vπ,ΩU , where vπ,U is the robust value function for policy π and vπ,ΩU the regularized one. This equivalence is derived through the objective function each value optimizes. More concretely, we formulate the robust value function vπ,U as an optimal solution of the robust optimization problem:
max v∈RS 〈v, µ0〉 s. t. v ≤ inf (P,r)∈U Tπ(P,r)v, (RO)
where Tπ(P,r) is the evaluation Bellman operator [30]. Then, we show that vπ,U is also an optimal solution of the convex (non-robust) optimization problem:
max v∈RS 〈v, µ0〉 s. t. v ≤ Tπ(P0,r0)v − ΩU (π, v), (CO)
where (P0, r0) is the nominal model. This establishes equivalence between the two optimization problems. Moreover, the inequality constraint of (CO) enables to derive a twice regularized (R2) Bellman operator defined according to ΩU , a policy and value regularizer. For ball-constrained uncertainty sets, ΩU has an explicit form and under mild conditions, the corresponding R2 Bellman operators are contracting. The equivalence between the two problems (RO) and (CO) together with the contraction properties of R2 Bellman operators enable to circumvent robust optimization problems at each Bellman update. As such, it alleviates robust planning and learning algorithms by reducing them to regularized ones, which are known to be as complex as 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 R2 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 := {−∞,∞}. Given a finite set Z , the class of real-valued functions (resp. probability distributions) over Z is denoted by RZ (resp. ∆Z ), while the constant function equal to 1 over Z is denoted by 1Z . Similarly, for any set X , ∆XZ denotes the class of functions defined over X and valued in ∆Z . The inner product of two functions a,b ∈ RZ is defined as 〈a,b〉 := ∑ z∈Z a(z)b(z), which induces the `2-norm ‖a‖ := √ 〈a,a〉. The `2-norm coincides with its dual norm, i.e., ‖a‖ = max‖b‖≤1〈a,b〉 =: ‖a‖∗. Let a function f : RZ → R. The Legendre-Fenchel transform (or convex conjugate) of f is f∗(y) := maxa∈RZ{〈a,y〉 − f(a)}. Given a set Z ⊆ RZ , the characteristic function δZ : RZ → R is δZ(a) = 0 if a ∈ Z; +∞ otherwise. The Legendre-Fenchel transform of δZ is the support function σZ(y) = maxa∈Z〈a,y〉 [3, Ex. 1.6.1].

heading: 2 Preliminaries
text: 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 Ω : ∆Z → R be a strongly convex function. Throughout this study, the function Ω plays the role of a policy and/or value regularization function. Its Legendre-Fenchel transform Ω∗ satisfies several smoothness properties, hence its alternative name "smoothed max operator" [25]. Our work makes use of the following result [14, 25]. Proposition 2.1. Given Ω : ∆Z → R strongly convex, the following properties hold: (i) ∇Ω∗ is Lipschitz and satisfies∇Ω∗(y) = arg maxa∈∆Z 〈a,y〉 − Ω(a),∀y ∈ R
Z . (ii) For any c ∈ R,y ∈ RZ , Ω∗(y+c1Z) = Ω∗(y) + c. (iii) The Legendre-Fenchel transform Ω∗ is non-decreasing.
Discounted MDPs and LP formulation. Consider an infinite horizon MDP (S,A, µ0, γ, P, r) with S and A finite state and action spaces respectively, 0 < µ0 ∈ ∆S an initial state distribution and γ ∈ (0, 1) a discount factor. Denoting X := S ×A, P ∈ ∆XS is a transition kernel mapping each state-action pair to a probability distribution over S and r ∈ RX is a reward function. A policy π ∈ ∆SA maps any state s ∈ S to an action distribution πs ∈ ∆A, and we evaluate its performance through the following measure:
ρ(π) := E [ ∞∑ t=0 γtr(st, at) ∣∣∣∣ µ0, π, P ] = 〈vπ(P,r), µ0〉. (1)
Here, the expectation is conditioned on the process distribution determined by µ0, π and P , and for all s ∈ S, vπ(P,r)(s) = E[ ∑∞ t=0 γ
tr(st, at)|s0 = s, π, P ] is the value function at state s. Maximizing (1) defines the standard RL objective, which can be solved thanks to the Bellman operators:
Tπ(P,r)v := r π + γPπv ∀v ∈ RS , π ∈ ∆SA,
T(P,r)v := max π∈∆SA
Tπ(P,r)v ∀v ∈ R S ,
G(P,r)(v) := {π ∈ ∆SA : Tπ(P,r)v = T(P,r)v} ∀v ∈ R S ,
where rπ := [〈πs, r(s, ·)〉]s∈S and Pπ = [Pπ(s′|s)]s′,s∈S with Pπ(s′|s) := 〈πs, P (s′|s, ·)〉. Both Tπ(P,r) and T(P,r) are γ-contractions with respect to (w.r.t.) the supremum norm, so each admits a unique fixed point vπ(P,r) and v ∗ (P,r), respectively. The set of greedy policies w.r.t. value v defines G(P,r)(v), and any policy π ∈ G(P,r)(v∗(P,r)) is optimal [30]. For all v ∈ R S , the associated function q ∈ RX is given by q(s, a) = r(s, a) + γ〈P (·|s, a), v〉 ∀(s, a) ∈ X . In particular, the fixed point vπ(P,r) satisfies v π (P,r) = 〈πs, q π (P,r)(s, ·)〉 where q π (P,r) is its associated q-function.
The problem in (1) can also be formulated as an LP [30]. Given a policy π ∈ ∆SA, we characterize its performance ρ(π) by the following v-LP [30, 26]:
min v∈RS 〈v, µ0〉 subject to (s.t.) v ≥ rπ + γPπv. (Pπ)
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 µ∈RS
〈rπ, µ〉 s. t. µ ≥ 0 and (IdRS − γPπ∗ )µ = µ0, (Dπ)
where Pπ∗ is the adjoint policy transition operator 2: [Pπ∗ µ](s) := ∑ s̄∈S P
π(s|s̄)µ(s̄) ∀µ ∈ RS , and IdS is the identity function in RS . Let I(s′|s, a) := δs′=s ∀(s, a, s′) ∈ X ×S the trivial transition matrix and define its adjoint transition operator as I∗µ(s) := ∑ (s̄,ā)∈X I(s|s̄, ā)µ(s̄, ā) ∀s ∈
2It is the adjoint operator of Pπ in the sense that 〈Pπv, v′〉 = 〈v, Pπ∗ v′〉 ∀v, v′ ∈ RS .
S. The correspondence between occupancy measures and policies lies in the one-to-one mapping µ 7→ µ(·,·)I∗µ(·) =: πµ and its inverse π 7→ µπ given by
µπ(s, a) := ∞∑ t=0 γtP ( st = s, at = a ∣∣∣∣µ0, π, P) ∀(s, a) ∈ X . As such, one can interchangeably work with the primal LP (Pπ) or the dual (Dπ).
Regularized MDPs. A regularized MDP is a tuple (S,A, µ0, γ, P, r,Ω) with (S,A, µ0, γ, P, r) an infinite horizon MDP as above, and Ω := (Ωs)s∈S a finite set of functions such that for all s ∈ S, Ωs : ∆A → R is strongly convex. Each function Ωs plays the role of a policy regularizer Ωs(πs). With a slight abuse of notation, we shall denote by Ω(π) := (Ωs(πs))s∈S the family of state-dependent regularizers.3 The regularized Bellman evaluation operator is given by
[Tπ,Ω(P,r)v](s) := T π (P,r)v(s)− Ωs(πs) ∀v ∈ R S , s ∈ S,
and the regularized Bellman optimality operator by T ∗,Ω(P,r)v := maxπ∈∆SA T π,Ω (P,r)v ∀v ∈ R S [10]. The unique fixed point of Tπ,Ω(P,r) (respectively T ∗,Ω (P,r)) is denoted by v π,Ω (P,r) (resp. v ∗,Ω (P,r)) and defines the regularized value function (resp. regularized optimal value function). Although the regularized MDP formalism stems from the aforementioned Bellman operators in [10], it turns out that regularized MDPs are MDPs with modified reward. Indeed, for any policy π ∈ ∆SA, the regularized value function is vπ,Ω(P,r) = (IS − γP
π)−1(rπ − Ω(π)), which corresponds to a non-regularized value with expected reward r̃π := rπ − Ω(π). Note that the modified reward r̃π(s) is no longer linear in πs because of the strong convexity of Ωs. Also, this modification does not apply to the reward function r but only to its expectation rπ , as we cannot regularize the original reward without making it policy-independent.
Robust MDPs. 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, a robust MDP (S,A, µ0, γ,U) is an MDP with uncertain model belonging to U := P ×R, i.e., uncertain transition P ∈ P ⊆ ∆XS and reward r ∈ R ⊆ R
X [17, 40]. The uncertainty set U typically controls the confidence level of a model estimate, which in turn determines the agent’s level of robustness. It is given to the agent, who seeks to maximize performance under the worst-case model (P, r) ∈ U . Although untractable in general, this problem can be solved in polynomial time for rectangular uncertainty sets, i.e., when U = ×s∈SUs = ×s∈S(Ps × Rs) [40, 23]. For any policy π ∈ ∆SA and state s ∈ S, the robust value function at s is vπ,U (s) := min(P,r)∈U v π (P,r)(s) and the robust optimal value function v ∗,U (s) := maxπ∈∆AS v π,U (s). Each of them is the unique fixed point of the respective robust Bellman operators:
[Tπ,Uv](s) := min (P,r)∈U Tπ(P,r)v(s) ∀v ∈ R S , s ∈ S, π ∈ ∆AS ,
[T ∗,Uv](s) := max π∈∆SA [Tπ,Uv](s) ∀v ∈ RS , s ∈ S,
which are γ-contractions. For all v ∈ RS , the associated robust q-function is given by q(s, a) = min(P,r)∈U{r(s, a) + γ〈P (·|s, a), v〉} ∀(s, a) ∈ X , so that vπ,U = 〈πs, qπ,U (s, ·)〉 where qπ,U is the robust q-function associated to vπ,U .

heading: 3 Reward-robust MDPs
text: This section focuses on reward-robust MDPs, i.e., robust MDPs with uncertain reward but known transition model. We first show that regularized MDPs represent a particular instance of reward-robust MDPs, as both solve the same optimization problem. This equivalence provides a theoretical motivation for the heuristic success of policy regularization. Then, we explicit the uncertainty set
3In the formalism of Geist et al. [10], Ωs is initially constant over S . However, later in the paper [10, Sec. 5], it changes according to policy iterates. Here, we alternatively define a family Ω of state-dependent regularizers, which accounts for state-dependent uncertainty sets (see Sec. 5 below).
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], as Lemma 3.2 there focuses on uncertain-transition MDPs and deterministic policies. For completeness, we provide a proof of Prop. 3.1 in Appx. A.1.
Proposition 3.1. For any policy π ∈ ∆SA, the robust value function vπ,U is the optimal solution of the robust optimization problem:
max v∈RS 〈v, µ0〉 s. t. v ≤ Tπ(P,r)v for all (P, r) ∈ U . (PU )
In the robust optimization problem (PU ), the inequality constraint must hold over the whole uncertainty set U . As such, a function v ∈ RS is said to be robust feasible for (PU ) if v ≤ Tπ(P,r)v for all (P, r) ∈ U or equivalently, if max(P,r)∈U{v(s)−Tπ(P,r)v(s)} ≤ 0 for all s ∈ S . Therefore, checking robust feasibility requires to solve a 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 literature [32, 15, 1], the remaining of this work focuses on uncertainty sets centered around a known nominal model. Formally, given P0 (resp. r0) a nominal transition kernel (resp. reward function), we consider uncertainty sets of the form (P0 + P)× (r0 +R). The size of P ×R quantifies our level of uncertainty or alternatively, the desired degree of robustness.
Reward-robust and regularized MDPs: an equivalence. We now focus on reward-robust MDPs, i.e., robust MDPs with U = {P0} × (r0 +R). Thm. 3.1 establishes that reward-robust MDPs are in fact regularized MDPs whose regularizer is given by a 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 on 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 = {P0} × (r0 + R). Then, for any policy π ∈ ∆SA, the robust value function vπ,U is the optimal solution of the convex optimization problem:
max v∈RS 〈v, µ0〉 s. t. v(s) ≤ Tπ(P0,r0)v(s)− σRs(−πs) for all s ∈ S .
Thm. 3.1 clearly highlights a convex regularizer Ωs(πs) := σRs(−πs) ∀s ∈ S . We thus recover a regularized MDP by setting [Tπ,Ωv](s) = Tπ(P0,r0)v(s)− σRs(−πs) ∀s ∈ S. In particular, when Rs is a ball of radius αrs, the support function (or regularizer) can be written in closed form as Ωs(πs) := α r s‖πs‖, which is strongly convex. We formalize this below (see proof in Appx. A.3). Corollary 3.1. Let π ∈ ∆SA and U = {P0} × (r0 + R). Further assume that for all s ∈ S, the reward uncertainty set at s isRs := {rs ∈ RA : ‖rs‖ ≤ αrs}. Then, the robust value function vπ,U is the optimal solution of the convex optimization problem:
max v∈RS 〈v, µ0〉 s. t. v(s) ≤ Tπ(P0,r0)v(s)− α r s‖πs‖ for all s ∈ S .
While regularization induces reward-robustness, 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 of these regularizers.
Related Algorithms. Consider a reward uncertainty set of the form R := ×(s,a)∈XRs,a. This defines an (s, a)-rectangular R (a particular type of s-rectangular R) whose rectangles Rs,a are independently defined for each state-action pair. For the regularizers below, we derive appropriate Rs,a-s that recover the same regularized value function. Detailed proofs are in Appx. 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 in 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 at each state-action pair. It similarly explains why the reward modification induced by regularization does not apply to the original reward function, as already mentioned in Sec. 2.
Negative Shannon entropy. Let RNSs,a(π) := [ln (1/πs(a)) ,+∞) ∀(s, a) ∈ X . The associated support function enables to write:
σRNSs (π)(−πs) = max r(s,·):r(s,a′)∈RNS
s,a′ (π),a ′∈A ∑ a∈A −r(s, a)πs(a) = ∑ a∈A πs(a) ln(πs(a)),
where the last equality comes from maximizing −r(s, a) over [ln (1/πs(a)) ,+∞) for each a ∈ A. We thus recover the negative Shannon entropy Ω(πs) = ∑ a∈A πs(a) ln(πs(a)) [13].
Kullback-Leibler divergence. Given an action distribution 0 < d ∈ ∆A, let RKLs,a(π) := ln (d(a)) + RNSs,a(π) ∀(s, a) ∈ X . It amounts to translating the intervalRNSs,a by the given constant. Similarly writing the support function yields Ω(πs) = ∑ a∈A πs(a) ln (
πs(a)/d(a)), which is exactly the KL divergence [34].
Negative Tsallis entropy. Letting RTs,a(π) := [(1−πs(a))/2,+∞) ∀(s, a) ∈ X , we recover the negative Tsallis entropy Ω(πs) = 12 (‖πs‖ 2 − 1) [20].
Policy-gradient for reward-robust MDPs. The equivalence between reward-robust and regularized MDPs leads us to wonder whether we can employ policy-gradient [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).
Proposition 3.2. Assume that U = {P0}× (r0 +R) withRs = {rs ∈ RA : ‖rs‖ ≤ αrs}. Then, the gradient of the reward-robust objective JU (π) := 〈vπ,U , µ0〉 is given by
∇JU (π) = E(s,a)∼µπ [ ∇ lnπs(a) ( qπ,U (s, a)− αrs πs(a)
‖πs‖
)] ,
where µπ is the occupancy measure under the nominal model P0 and policy π.
Although Prop. 3.2 is an application of [10, Appx. D.3] for a specific regularized MDP, its rewardrobust 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 worstcase 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 a twofold advantage: (i) it avoids an additional computation of the minimum as done in [29, 21, 7], 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-uncertain MDPs, because of the interdependence between the regularizer and the value function (see Secs. 4-5). We detail more on this issue in Appx. A.5.

heading: 4 General robust MDPs
text: 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 in Appx. B.1). Although the regularizer is also a 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 = (P0 + P)× (r0 +R). Then, for any policy π ∈ ∆SA, the robust value function vπ,U is the optimal solution of the convex optimization problem:
max v∈RS 〈v, µ0〉 s. t. v(s) ≤ Tπ(P0,r0)v(s)− σRs(−πs)− σPs(−γv · πs) for all s ∈ S, (2)
where [v · πs](s′, a) := v(s′)πs(a) ∀(s′, a) ∈ X .
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 (P0, r0) to which we subtract a 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-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. 5. Corollary 4.1. Assume that U = (P0 + P)× (r0 +R) with Ps := {Ps ∈ RX : ‖Ps‖ ≤ αPs } and Rs := {rs ∈ RA : ‖rs‖ ≤ αrs} for all s ∈ S. Then, the robust value function vπ,U is the optimal solution of the convex optimization problem:
max v∈RS 〈v, µ0〉 s. t. v(s) ≤ Tπ(P0,r0)v(s)− α r s‖πs‖ − αPs γ‖v‖‖πs‖ for all s ∈ S . (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 ‖·‖∗ instead of ‖·‖ in Eq. (3) (see proof in Appx. B.2). Here, we restrict our statement to the `2-norm for notation convenience only, the dual norm of `2 being `2 itself. Thus, our regularization function recovers a robust value function independently of the chosen norm, which extends previous results from [15, 11]. Indeed, Ho et al. [15] lighten complexity of robust planning for the `1-norm only, while GrandClément & Kroer [11] focus on KL and `2 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 a generic, problem-independent regularization function while still encompassing s-rectangular uncertainty sets as in [15, 11].

heading: 5 R2 MDPs
text: In Sec. 4, we showed that for general robust MDPs, the optimization constraint involves a regularization 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 ball-constrained. In this section, we introduce R2 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. 3-4. Definition 5.1 (R2 Bellman operators). For all v ∈ RS , define Ωv,R2 : ∆A → R as Ωv,R2 (πs) := ‖πs‖(αrs + αPs γ‖v‖). The R2 Bellman evaluation and optimality operators are defined as
[Tπ,R 2 v](s) := Tπ(P0,r0)v(s)− Ωv,R2 (πs) ∀s ∈ S, [T ∗,R 2 v](s) := max
π∈∆SA [Tπ,R
2 v](s) = Ω∗
v,R2 (qs) ∀s ∈ S .
For any function v ∈ RS , the associated unique greedy policy is defined as πs = arg max
πs∈∆A Tπ,R
2 v(s) = ∇Ω∗
v,R2 (qs), ∀s ∈ S,
that is, in vector form, π = ∇Ω∗ v,R2 (q) =: GΩ R2 (v) ⇐⇒ Tπ,R2v = T ∗,R2v.
The R2 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 fixed point theorem to define the R2 value function. Assumption 5.1 (Bounded radius). For all s ∈ S, there exists s > 0 such that
αPs ≤ min 1− γ − sγ√|S| ; minuA∈RA+ ,‖uA‖=1 vS∈RS+,‖vS‖=1 u>AP0(·|s, ·)vS  .
Asm. 5.1 requires to upper bound the ball radius of transition uncertainty sets. The first term in the minimum is needed for establishing contraction of R2 Bellman operators (item (iii) in Prop. 5.1), 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 γ: radius αPs must be smaller as γ tends to 1 but can arbitrarily grow as γ decreases to 0, 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 `2-norm chosen for the ball constraints. In fact, for any `p-norm of dual `q, |S| 1 q replaces √ |S| in the denominator, so it becomes independent of |S| as (p, q) tends to (1,∞) (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. 5.1 enables the R2 Bellman operators to admit a unique fixed point, among other nice properties. We formalize this below (see proof in Appx. C.1). Proposition 5.1. Suppose that Asm. 5.1 holds. Then, we have the following properties: (i) Monotonicity: For all v1, v2 ∈ RS such that v1 ≤ v2, we have Tπ,R 2 v1 ≤ Tπ,R 2 v2 and T ∗,R 2 v1 ≤ T ∗,R 2 v2. (ii) Sub-distributivity: For all v1 ∈ RS , c ∈ R, we have Tπ,R 2 (v1 + c1S) ≤ Tπ,R 2 v1 + γc1S and T ∗,R 2 (v1 + c1S) ≤ T ∗,R 2 v1 + γc1S , ∀c ∈ R. (iii) Contraction: Let ∗ := mins∈S s > 0. Then, for all v1, v2 ∈ RS , ‖Tπ,R2v1 − Tπ,R 2 v2‖∞ ≤ (1− ∗)‖v1 − v2‖∞ and ‖T ∗,R 2 v1 − T ∗,R 2 v2‖∞ ≤ (1− ∗)‖v1 − v2‖∞.
We should note that the contracting coefficient in Prop. 5.1 is different from the original discount factor γ, since here we have 1− ∗. Yet, as Asm. 5.1 suggests it, an intrinsic dependence between γ and ∗ makes the R2 Bellman updates similar to the standard ones: when γ tends to 0, the value of ∗ required for Asm. 5.1 to hold increases, which makes the contracting coefficient 1− ∗ tend to 0 as well, i.e., the two contracting coefficients behave similarly. The contraction of both R2 Bellman operators finally leads us to introduce the R2 value functions.
Definition 5.2 (R2 value functions). (i) The R2 value function vπ,R 2
is defined as the unique fixed point of the R2 Bellman evaluation operator: vπ,R 2 = Tπ,R 2 vπ,R 2 . The associated q-function is qπ,R 2 (s, a) = r0(s, a)+γ〈P0(·|s, a), vπ,R
2〉. (ii) The R2 optimal value function v∗,R2 is defined as the unique fixed point of the R2 Bellman optimal operator: v∗,R 2 = T ∗,R 2 v∗,R 2 . The associated q-function is q∗,R 2 (s, a) = r0(s, a) + γ〈P0(·|s, a), v∗,R 2〉.
The monotonicity of the R2 Bellman operators plays a key role in reaching an optimal R2 policy, as we show in the following. A proof can be found in Appx. C.2.
Theorem 5.1 (R2 optimal policy). The greedy policy π∗,R 2
= GΩ R2
(v∗,R 2 ) is the unique optimal
R2 policy, i.e., for all π ∈ ∆SA, vπ ∗,R2 = v∗,R 2 ≥ vπ,R2 . Remark 5.1. An optimal R2 policy may be stochastic. This is due to the fact that our R2 MDP framework builds upon the general s-rectangularity assumption. Robust MDPs with s-rectangular uncertainty sets similarly yield an optimal robust policy that is stochastic [40, Table 1]. Nonetheless, the R2 MDP formulation recovers a deterministic optimal policy in the more specific (s, a)-rectangular case, which is in accordance with the robust MDP setting (see proof in Appx. C.3). 4
Algorithm 1: R2 MPI Result: πk+1, vk+1 Initialize vk ∈ RS ; while not converged do
πk+1 ← GΩ R2 (vk); vk+1 ← (Tπk+1,R 2 )mvk;
end All of the results above ensure convergence of MPI in R2 MDPs. We call that method R2 MPI and provide its pseudo-code in Alg. 1. The convergence proof follows the same lines as in [30]. Moreover, the contracting property of the R2 Bellman operator ensures the same convergence rate as in standard and robust MDPs, i.e., a geometric convergence rate. On the other hand, R2 MPI reduces the computational complexity of robust MPI by avoiding to solve a max-min problem at each iteration, as this can take polynomial time for general convex programs. Advantageously, the only optimization involved in R2 MPI lies in the greedy step: it amounts to projecting onto the simplex,
4The stochasticity of an optimal entropy-regularized policy as in the examples of Sec. 3 is not contradicting. Indeed, even though the corresponding uncertainty set is (s, a)-rectangular there, it is policy-dependent.
which can efficiently be performed in linear time [8]. Still, such projection is not even necessary in the (s, a)-rectangular case: as mentioned in Rmk. 5.1, it then suffices to choose a greedy action in order to eventually achieve an optimal R2 value function.

heading: 6 Numerical Experiments
text: We aim to compare the computing time of R2 MPI with that of MPI [30] and robust MPI [18]. The code is available at https://github.com/EstherDerman/r2mdp. To do so, we run experiments on an Intel(R) Core(TM) i7-1068NG7 CPU @ 2.30GHz machine, which we test on a 5×5 grid-world domain. In that environment, the agent starts from a random position and seeks to reach a goal state in order to maximize reward. Thus, the reward function is zero in all states but two: one provides a reward of 1 while the other gives 10. An episode ends when either one of those two states is attained.
The partial evaluation of each policy iterate is a building block of MPI. As a sanity check, we evaluate the uniform policy through both R2 and robust policy evaluation (PE) sub-processes, to ensure that the two value outputs coincide. For simplicity, we focus on an (s, a)-rectangular uncertainty set and take the same ball radius α (resp. β) 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 R2 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, R2 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 R2 PE avoids thanks to regularization. R2 PE still takes 2.5 times longer than its standard, non-regularized counterpart, because of the additional computation of regularization terms. Table 1 shows the time spent by each algorithm until convergence.
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, a)-rectangular uncertainty set, the same applies to robust MPI [40] and to R2 MPI, as already mentioned in Rmk. 5.1. We can see in Table 1 that the increased complexity of robust MPI is even more prominent than its PE thread, as robust MPI takes 3953 (resp. 3270) times longer than R2 MPI when m = 1 (resp. m = 4). Robust MPI with m = 4 is a 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 ∈ {1, 4}, progressing from PE to MPI did not cost much more computing time to either the vanilla or the R2 version: both take less than one second to run.

heading: 7 Related Work
text: 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. 1, these represent particular RL problems as they concern a single-stage decision-making process. In that regard, the generalization of robustness-regularization duality to sequential decision-making has seldom been studied in the RL literature.
Two works that view policy regularization from a robustness perspective are [16] and [9]. In [16], regularization is applied on the dual objective instead of the primal. This has two shortcomings: (i) It 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 a particular type of robust MDP. Yet, their analysis 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-robust 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-robustness and regularization. There again, duality is weak and reward uncertainty is not addressed. Moreover, since the exact regularization term has no explicit form, it is usable through its upper bound only. Finally, regularization is applied on the mean of several value functions vπ
(P̂i,r) , where each P̂i 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 [2, 27] propose robust value iteration, while [17, 40] introduce robust policy iteration. Kaufman & Schaefer [18] 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 a Bellman update grows cubically in the number of states [15].
In order to reduce the time complexity of robust planning algorithms, Ho et al. [15] propose two algorithms that compute robust Bellman updates in O(|S||A| log(|S||A|)) operations for `1-constrained uncertainty sets. Advantageously, our regularization approach reduces each such update to its standard, non-robust complexity of O(|S||A|). Moreover, although Ho et al. [15] 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 `1-norm while our method applies to any norm. This may come from the fact that our main Theorems (Thms. 3.1 and 4.1) use Fenchel-Rockafellar duality [31, 4], a generalization of LP duality (see Appx. A.2 and B.1). More recently, Grand-Clément & Kroer [11] propose a first-order method to accelerate robust value iteration under 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.

heading: 8 Conclusion and future work
text: In this work, we established a 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 to derive a policy-gradient theorem for reward-robust MDPs. When extending this robustness-regularization duality to general robust MDPs, we found that the regularizer depends on the value function besides the policy. We thus introduced R2 MDPs, a generalization of regularized MDPs with both policy and value regularization. The related R2 Bellman operators lead us to propose a converging R2 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 regularizer in R2 MDPs. In fact, it would be interesting to study the R2 MDP setting under function approximation, as such approximation would have a direct effect on the regularizer. Similarly, one could analyze approximate dynamic programming for R2 MDPs in light of its robust analog [38, 1]. Although our theory focused on planning, the R2 Bellman operators and their contracting properties open the path to learning algorithms that can (i) use existing RL algorithms and robustify them by simply changing 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 R2 MPI to the approximate case [33] would be an interesting problem to solve because of the R2 evaluation operator being non-linear. So would be a sample complexity analysis for R2 MDPs with a comparison to robust MDPs [42]. Another line of research is to extend policy-gradient to R2 MDPs, as this would avoid parallel learning of adversarial models [7, 39] and be very useful for continuous control.

heading: Acknowledgements
text: We would like to 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.

Review summaries:
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.

The paper highlights two limitations of current approaches for Robust RL:   1. Robust optimization methods are computationally demanding. 2. They do not account for uncertainty in the model dynamics.  The paper proposes to work around these limitations by learning robust MDPs using regularization. Their contributions are the following:  1. 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  2. Extend point 1 to MDPs with the uncertain transition. 3. Generalize regularized MDPs to twin regularized MDPs to retrieve robust MDPs.

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.

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.