Robust $\phi$-Divergence MDPs
Authors: Chin Pang Ho
Marek Petrik
Wolfram Wiesemann
Venue: NeurIPS 2022 Accept (2022)
Keywords: Markov decision processes
robust optimization
phi-divergences

Abstract: In recent years, robust Markov decision processes (MDPs) have emerged as a prominent modeling framework for dynamic decision problems affected by uncertainty. In contrast to classical MDPs, which only account for stochasticity by modeling the dynamics through a stochastic process with a known transition kernel, robust MDPs additionally account for ambiguity by optimizing in view of the most adverse transition kernel from a prescribed ambiguity set. In this paper, we develop a novel solution framework for robust MDPs with $s$-rectangular ambiguity sets that decomposes the problem into a sequence of robust Bellman updates and simplex projections. Exploiting the rich structure present in the simplex projections corresponding to $\phi$-divergence ambiguity sets, we show that the associated $s$-rectangular robust MDPs can be solved substantially faster than with state-of-the-art commercial solvers as well as a recent first-order solution scheme, thus rendering them attractive alternatives to classical MDPs in practical applications. 

Robust O e-Divergence MDPs
Chin Pang Ho City University of Hong Kong clint. ho@cityu edu hk
Marek Petrik University of New Hampshire mpetrikecs. unh. edu
Wolfram Wiesemann Imperial College London
wn@imperial.com ac..ccc...... uk
Abstract
In recent years, robust Markoy decision processes (MDPs) have emerged as a prominent modeling framework for dynamic decision problems affected by un- certainty. In contrast to classical MDPs, which only account for stochasticity by modeling the dynamics through stochastic process with known transition kernel, robust MDPs additionally account for ambiguity by optimizing in view of the most adverse transition kernel from prescribed ambiguity set. In this paper, we develop a novel solution framework for robust MDPs with s-rectangular ambiguity sets that decomposes the problem into a sequence robust Bellman updates and simplex projections. Exploiting the rich structure present in the simplex projections corre- sponding ø-divergence ambiguity sets, we show that the associated s-rectangular robust MDPs can be solved substantially faster than with satte-of-the-aad commer- cial solvers as well recent first-order solution scheme, thus rendering them attractive alternatives to classical MDPs in practical applications.
Introduction
Markov decision processes (MDPs) are a flexible and popular framework for dynamic decision- making problems and reinforcement learning [39, 48]. practical limitation of the standard MDP model is that it assumes the model parameters, such as transition probabilities and rewards, to be known exactly. In reinforcement learning and other applications, these parameters must be estimated from sampled data, which introduces estimation errors. Optimal MDP solutions, referred to as policies, well known be sensitive errors and may fail catastrophically when deployed [25, 56).
Robust MDPs (RMDPs) mitigate the sensitivity of MDPs to estimation errors by computing a policy that is optimal for the worst plausible realization of the transition probabilities. This set of plausible transition probabilities is known as the ambiguity set. Most prior work considers ambiguity sets that are rectangular. In this work, focus s-reciangular ambiguity sets, which assume that the worst transition probabilities are chosen independently in each state [25, 56). While several other models of rectangularity have been studied [9, 13, 21, 28), s-rectangular ambiguity sets are popular due to their generality and their performance both in in-sample and out-of-sample [56]. However, even though polynomial-time algorithms based on dynamic programming concepts have been developed for s-rectangular sets, those algorithms may be too slow in practice. Solving RMDPs requires the solution of convex optimization problem in every step of value or policy iteration, which can become prohibitively slow even in moderatly sized problems with 100s of states [5, 9, 14, 19].
Motivated by the difficulty of solving RMDPs, several fast algorithms have been proposed for rectangular RMDPs [5. 9, 14, 19]. The preponderance of the earlier work has focused on ambiguity sets defined in terms of L and Too -norms. These ambiguity sets polyhedral, and they can be analyzed using linear programming techniques which offer fruitful avenues to exploit the structure inherent to those sets. However, recent statistical studies point to the superior solution quality offered by nonlinear ambiguity sets defined in terms of the Kullback-Leibler (KL) divergence, the L2-norm and other metrics [17]. Linear optimization solvers are not applicable RMDPs with s-rectangular ambiguity sets defined in terms of non- non-polyhedral ambiguity sets, as the corresponding optimization
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

problems are in general convex conic programs (e.g., exponential cone program in the case of KL divergence); thus, they are currently solved using first-order methods [14] or general convex conic solvers such as MOSEK [3], which tend to be complex, closed-source and slow.
As our main contribution, we propose new suite of fast algorithms for solving RMDPs with ø- divergence constrained s-rectangular ambiguity sets, ø-divergences, also known as f-divergences, constitute a generalization of the KL divergence that encompasses the Burg entropy as well as the L1- and weighted L2-norms as special cases [4, 6]. Moreover, d-divergence ambiguity sets benefit from rigorous statistical performance guarantees, and they are optimal among all (known and unknown) data-driven optimization paradigms for certain types of worst-case out-of- performance guarantees [35]. The radii of o-divergence ambiguity sets can be selected either via cross- validation or via statistical bounds [26, 32, 55J. Robust MDPs with d-divergence sets are challenging and unexplored for both (s, a) reeetanngala and s-rectangular ambiguity sets. Solving d-divergence RMDPs using value iteration requires the solution of seemingly unstructured min-max problems. Our main insight that these min- max problems can be reduced to a small number of highly structured projection problems onto probability simplex. We use this insight to develop tailored solution schemes for the projection problems corresponding to several popular ø-divergence ambiguity sets, which in turn give rise to efficient solution methods for the respective RMDPs. Ignoring tolerances, our algorithms achieve an overall O(S A log A) or O(S log S A) time complexity to compute the robust Bellman operator, where S and A denote the numbers of states and actions, respectively. Since the evaluation of a non-robust Bellman operator requires a runtime of O log A), our algorithms only incur additional logarithmic overhead to account for robustmess in the transition probabilities. This computational complexity compares favorably with the larger time complexity of recent first-order solution scheme for KL wwwerrencc-constraieee will elaborate on later in the paper) as well as a minimum complexity of O(S A) for the naive solution with state-of-the-at interior-point algorithms. Our framework is general enough readily accommodate for ø-divergences that have not been studied previously in the context of s-rectangular ambiguity sets, such as the Burg entropy and the ddiditaacce. For other o--divergeness, such as the L1 -norm, our framework results in the same complexity at substantially simplified proofs.
s-rectangular RMDPs (which
The algorithms developed in this paper speed up the computation of robust Bellman updates, and so they can be used in combination with a variety of RMDP solution schemes. In particular, they can be used to accelerate the standard robust value iteration, policy iteration, modified policy iteration [22] and partial policy iteration [19]. They can also be combined with a first order gradient method [14] that has been introduced recently. In addition, fast algorithms for computing the Bellman operator also play crucial role when scaling robust algorithms to value function approximation [50], model-free reinforcement learning [33, 42], and robust policy gradients [49]. In this paper, we focus on the model-based setting, which is currently under active study [24, 29, 31] and has many important real- life applications [12, 20, 58]; moreover, it also serves as an important building block constructing model- free algorithms. While this paper focuses on the s-rectangular ambiguity sets, the proposed algorithms in this paper can also be applied the special case of (s, a) rectanguull ambiguity sets.
The remainder of the paper proceeds as follows. Section 2 reviews relevant prior work and Section describes our basic RMDP setting. Then, Section 4 shows how the robust Bellman operator for large class of ambiguity sets can be reduced to a sequence of structured projections onto a simplex. We describe novel algorithms for efficiently computing the simplex projections for several d-divergences in Section 5. Finally, Section 6 presents experimental results that compare the runtime of our algorithms with general conic solvers as well recent first-order optimization algorithm [14].
Notation. We denote by e the vector of all ones, whose context determines its dimension. We refer to the probability simplex in I" by An = {p R. min(æ} = min(x; :i= 1,..., n) (similar for the maximum operator), and we define |x]+ E PT component-wise ([x)+ max (2;, 0}, i = 1....,n.
p 1}. For x R", we let
n. We refer to the conjugate of function f: IR + R by (*) sup x f(x) E J"). Random variables are indicated by tilde.
2 Related Work
While RMDPs have been studied since the seventies [45], they have witnessed significant recent interest due to their widespread adoption in applications ranging from assortment optimization [43], medical decision-making [12, 62] and hospital operations management [16], production planning [58]
2

---

and energy systems [20] to model predictive control [10], aireraft collision avoidance [23], wireless communications [57] and the robustification against approximation errors in aggregated MDPs [37].
Efficient implementations of the robust value iteration have been first proposed by [11, 21, 32] for RMDPs with (s, ---recanng ambiguity sets, where the worst transition probabilities are considered separately for each state and action. The authors study ambiguity sets that bound the distance of the transition probabilities some nominal distribution in terms of finite scenarios, interval matrix bounds, ellipsoids, the relative entropy. the KL divergence and maximum a posteriori models. Subsequently, similar methods have been developed by [57] for interval matrix bounds as well as likelihood uncertainty models. by [37] for 1-norm ambiguity sets as well as by [62] for interval matrix bounds intersected with a budget constraint. All of these contributions have in common that they focus on (s, a) rectanguul ambiguity sets where the existence of optimal deterministic policies guaranteed, and it not clear how they could be extended to the more general class of s-rectangular ambiguity sets where all optimal policies may be randomized.
In contrast to (s, a) rectanngull ambiguity sets, s-rectangular ambiguity sets restrict the conservatism among transition probabilities corresponding to different actions in the same state, which tends to lead to a superior performance in data-driven settings. [56] solve the subproblems arising in the robust value iteration of an s-rectangular RMDP as linear or conic optimization problems using complexity, general-purpose solvers cannot exploit the structure present in these subproblems, which renders them suitable primarily for small problem instances. More efficient tailored solution methods for s-rectangular RMDPs have subsequently been developed by [5, 18, 19]. [18] develop homotopy continuation method for RMDPs with (s, a rectangula and s-rectangular weighted 1-norm ambiguity sets, while [5] adapt the algorithm of [18] to unweighted co-norm ambiguity sets. [19] embed the algorithms of [18] in a partial policy iteration, which generalizes the robust modified policy iteration proposed by [22] for (s, a c)-rectangular RMDPs to s-rectangular RMDPs.
commercial off- fff-he--heeff solvers. Despite their polynomial
While the present paper focuses on the robust value iteration for ease of exposition, we note that our algorithms can also be combined with the partial policy iteration of [19] to obtain further speedups. [9] establish a relationship between s-rectangular RMDPs and twice regularized MDPs, which they subsequently use to propose efficient Bellman updates for a modified policy iteration. While their approach can solve RMDPs in almost the same time as a classical non-robust MDPs, the obtained policies can be conservative as the worst-case transition probabilities are not restricted to reside in a probability simplex and, therefore, may be negative and/or add up to more or less than Finally, [14] propose a first-order framework for RMDPs with s-rectangular KL and spherical ambiguity sets that interleaves primal-dual first-order updates with approximate value iteration steps. The authors show that their algorithms outperform robust value iteration that solves the emerging subproblems using state-of-the- commercial solvers. We compare our solution method for KL ambiguity sets with the approach proposed by [14] in terms of its theoretical complexity and numerical runtimes.
While this paper exclusively studies s-rectangular uncertainty sets, alternative generalizations of (s, a) -)-rectangular ambiguity sets have been proposed in the literature as well. For example, [28] consider k-rectangular ambiguity sets where the transition probabilities of different states can be coupled, [13] study factor ambiguity model ambiguity sets where the transition probabilities depend on small number of underlying factors, and [51] construct ambiguity sets that bound marginal moments of state-action features defined over entire MDP trajectories. Moving beyond the model- based setting, there is also an active line of research on robust reinforcement learning, such as least squares policy iteration [33], analysis sample complexity [34), robust Q-learning and robust TDC algorithms [42, 53], and robust policy gradient [54]. We also note the papers [7, 15, 60] which study the related problem of distributionally robust MDPs whose transition probabilities are themselves regarded as random objects that are drawn from distributions which are only partially known. The connections between RMDPs and multi-stage stochastic programs as well as distributionally robust problems are explored further by [44, 46, 47].
3 Preliminaries
We study RMDPs with finite state space S = (1,.... .S).....)... and a finite action space A = (I,..., A). We assume an infinite planning horizon, but all of our results immediately extend to finite time horizon. Without loss of generality, we assume that every action is admissible
Robust MDPs
3

---

in every state S. The RMDP starts in random initial state šo that follows the known probability distribution pd from the probability simplex As in R action a AA is taken in state E S, then the RMDP transitions randomly to the next state according to the conditional probability distribution
Psa E Ag. We condense the transition probabilities Psa to the tensor p E (Ag) S The transition probabilities are only known to reside in a non-empty, compact ambiguity set P S (Ag)Sx4 For a transition from state s E to state s' E S under action a E A, the decision maker receives an expected reward of ses E R4. As with the transition probabilities, we condense these rewards to the tensor E R $x Without loss of generality, we assume that all rewards are non-negative.
We denote by IT = (A the set of all stationary (i.e., time-independent) randomized policies. A policy π E II takes action
A in state & E S with probability Taa The transition probabilities P and the policy E II induce stochastic process {(5,, ] on the space (S x A) of sample paths. We refer by BP to expectations with respect to this process. The decision maker risk-neutral but anbiguity-averse and wishes to maximize the worst-case expected total reward under a discount factor (0, 1),
max min RP. Hell pEp
Σ X T8,
80 p"
(1)
Note that the maximum and minimum in (1) are both attained by the Weierstrass theorem since II and P are non-empty and compact, while the objective function is finite since À < 1.
Rectangular Ambiguity Sets For general ambiguity sets P. evaluating the inner minimization in (1) is NP-hard even if the policy æ E Il is fixed [56]. For these reasons, much of the research on RMDPs and their applications has focused on rectangular ambiguity sets. Among the most general rectangular ambiguity sets are the s-rectangular ambiguity sets P satisfying
p == (p (As)5xA P. Ps vs ES] where P. S (As) 8 E,
see [25, 56, 59, 61]. In contrast to the simpler class of (s, rectanguul ambiguity sets, s-rectangular ambiguity sets restrict the choice of transition probabilities P.1..... Pa.A corresponding to different actions applied in the same state This limits the conservatism of the resulting RMDP (1) and typically leads to better performance of the optimal policy [56]. Although Bellman's 's optimality principle extends to s- s-rectangular RMDPs and there is always an optimal stationary policy, all optimal policies of an s-rectangular RMDP may be randomized.
We study a new general class of s-rectangular ambiguity sets that can be expressed as
P.
Ps E (As) dd P.a) S Ban
aEA
where E R4 is the uncertainty budget and the distance functions de (Psa, Psa). E A, are d-divergences (also known as f-divergences) satisfying
da (Psa: Pea)
Σ EPaas E'ES
Psas'
Pras'
Here, Φ: R+ + R. is a convex function satisfying ((1) = 0. Intuitively, a a é-divergencee measures the distance between two probability distributions. With an appropriate choice of Φ, it generalizes other metrics including the KL divergence, the Burg entropy, Li- and L2-norms and others [4, 6]. Table reports some popular didivergences that we study in this paper. The variation distance coincides with the -bssed s-rectangular ambiguity sets studied in earlier work [18, 19]. Note that although we assume that Φ is the same for different state-action pairs, the proposed approach also works for the more general case where d, (P P.a) Eses Psas Peas' (Peas' /Paas).
Robust Value Iteration A standard approach for computing the optimal value and the optimal policy of an RMDP (1) is the robust value iteration [21, 32, 25, 56]: Starting with an initial estimate v" E S of the state-wise optimal value to-go, we conduct robust Bellman iterations of the form ot+1 f 3(v",, 1- 0, I,... where the robust Bellman operator J is defined component-wise
[(]]]s
max min
Σ aEAA
Tea Pso T T(r.a Xe)
Vs E S.
(3)
n. T.AA P.EPA

---

Divergence
da Caaa Poa)
6(()
Complexity of
Prior Art
Kullback-Leibler
E.' Pense log
1 Blog +++1
O Alg A)
(E A)
Pous' Pence
Burg Entropy
Ev Psast log
logt
O(S* A)
no poly-time O O log 5A) O(S A)
Pousr
Variation Distance
E, |Paas' Prast
||-1| (L (1- O log SA)
O log SA)
x --Distance
E.'
(Peast - Peart
Pans!
Table I: Summary of the d-divergences studied in this paper, together with the complexity of our robust Bellman operator 3 (applied across all states s E S) as well as the best known results from the literature. The complexity estimates omit constants and tolerances that are reported in Section 5 of the paper. 'E", where present, refers to the number of Bellman iterations conducted so far.
This yields the optimal value pT where the limit lime of is approached component-wise at geometric rate. The optimal policy πt* E II, finally, is recovered state-wise via
T E arg max min T.EAA P.EP.
Σ aEA
Tsa Psa T (rsa + Xv") As E.
Robust Bellman Updates via Simplex Projections
In this section, we show that the robust Bellman operator reduces to a generalized projection problem. This reduction is important because it underlies our fast algorithms for computing J.
At the core of the robust value iteration the solution of the max-min problem (3). By applying the minimax theorem, the right-hand side of (3) equals to
minimize
{Psa T T(rsa {u)}
subject to
da (Psa Psa) S
(4)
P. E (As)a.
The above optimization problem can be solved via bisection on its objective value: that seek the lowest possible 3 such that P.a (rsa + Xv) < 3, for each a E A where p, satisfies the constraints in (4). For any given |8 in the bisection method, we check whether such pa exists by solving the following generalized du -rojjecciion problem of the nominal transition probabilities ...:
minimize subject to
da Pso)
Peo P.a As
(5)
Here, Psa E As are the decision variables and P.a. E As, b E R and 3 E R. are parameters. For any fixed B, we compute E.EA P(P.. sn + Xv, 9) and construct ps E (As) where psa the optimal solution of the associated projection problem P(... b, 3). We can then distinguish between the following two cases:
If E.EA BiP..: Te + Xu, S K, then the constructed p. a feasible solution to (5). Therefore, 3 upper bounds the optimal objective value.
2. If EaEa Pi M Tea + Yu, 3) > K, then there is feasible p. E AA such that the objective value attains 3 or less. Therefore, 3 lower bounds the optimal objective value.
As consequence of the cases above, one can compute the robust Bellman update (3) efficiently by bisection if the projection problem (5) can be solved efficiently. The proof of Theorem describes further details needed to implement this algorithm, including the initial upper and lower bounds on and bounds on the precision needed when solving the projection problems.
Note that problem (5) is infeasible if and only if min(b) B. Moreover, problem (5) is trivially solved by P.a with optimal objective value of 0 whenever b P... 3. To avoid these trivial cases,
5

---

(6)
(b)
(c)
Figure 1: The generalized da projecctin problem (5) in S = 3 dimensions (a) and two-dimensional projections for the variation distance (b), the distttaec (c) and the KL divergence (d). The gray shaded areas represent the probability simplex As, , the red dashed lines show the boundary of the intersection of the halfspace b Pea I 3 with the probability simplex, and the white shapes illustrate contour lines centered at the nominal transition probabilities Psa
we assume throughout the paper that min(b) S 3 and b P.o > 8. We illustrate the feasible region and optimal solution to problem (5) for different <i-divergences in Figure 1.
Our generalized projeecct (5) relates the rich literature on projections onto simplices, which we review in the next section. In fact, our algorithms in the next section solve variant of the simplex projection problem that restricted by an additional inequality constraint. We therefore believe that our algorithms may find additional applications outside the RMDP literature.
In the following, say that for given estimate of R$ of the optimal value function, the robust Bellman iteration (3) is solved to e-accuracy by any vl+1 E R satisfying | [l S e. We seek e-optimal solutions because
ambiguity sets nonlinear and hence the exact Bellman iterate ((x") may be irrational even if v' is rational. To simplify the exposition, we define R [1-A] -|-A1_1 max(Tsas' 8, E S, a E A} as an upper bound on all [3(v]]., S o² and s E S.
For divergence- bassed ambiguity sets, the projection problem (5) is generically nonlinear and can hence not be expected to be solved exact optimality. To account for this additional complication, we say that for a given sa E As. b E RE and B RR+, the generalized -rojjecet B 3) solved to 5-accuracy by any pair (d. d) E R2 satisfying P(P..: b, B) [d. d and d d 5.
Theorem 1. Assume that the generalized da -rojjecctiinn (5) can be computed to any accuracy 5 > in time O (k())). Then the robust Bellman iteration (3) can be computed to any accuracy >> 0 in time O h(<x/|2AR + Ael) log[Rte]]..
Theorem reduces the evaluation of the robust Bellman iterator J. which involves the solution of max-min optimization problem over an s-rectangular ambiguity set that couples all actions a E A,, to sequence of much simpler and highly structured projection problems that are no longer coupled across different actions a E .A. The next section describes efficient solution schemes for the projection problem (5) in the context of several ø-divergence ambiguity sets. The runtimes of these solution schemes are summarized in Table 1. Note that the evaluation of non-robust Bellman operator requires runtime of O log A), which implies that our algorithms only incur additional logarithmic overhead to account for robustness in the transition probabilities.
5 Fast Projections on é-Divergence Simplices
We next describe fast algorithms for computing generalized projections onto the probability simplex. Combined with the results from Section these algorithms
be used efficiently compute the robust Bellman operator. Note that some d-divergences, such as the KL divergence and the -diistance, imply that if P. Paas'
for some s' E S and E A, then Psas' = 0 for all P.. E As with d, (P... ) < oc, and thus we can remove indices s' with Pras' = 0. For other d-divergences, can readily verify that results remain
such the Burg entropy and the variation distance, valid no matter whether P.. > O or not, but the formulations and proofs require additional case distinctions and/or limit arguments. To simplify the exposition, therefore assume that P.o 0.

---

Proposition 1. For the distance function de Paa) Peas' (Psov' ). the optimal value of the projection problem (3) equals the optimal value of the bivariate convex problem
(
maximize
- S
R'ES osa +()
(6)
subject to
a a S R.
Proposition I reduces the S-dimensional projection problem (5) to a two-dimensional optimization problem over the dual variables a and Ç. In the following, we show that for the d-divergences from Table I, problem (6) can be further simplified to univariate convex optimization problems that can be solved efficiently via bisection, binary search or sorting.
5.1
Kullback-Leibler Divergence
We first show that for the KL divergence o(t) logt - + 1, the reduced projection problem (6) be further simplified to univariate convex optimization problem.
Proposition 2. For the KL divergence @(t) tlogt t + the optimal value of the projection problem (5) equals the optimal value of the univariate convex problem
maximize a
-a - loo
Σ s'ES
Paas'
eab,
ab,
We next show that the univariate optimization problem (2) admits an efficient solution via bisection.
Theorem 2. If 8 2 min + w for some w O. then the projection problem (5) can be solved to any 8-accuracy in time OSS log mmx log(mmn (mmmm
Note that the projection problem (5) is infeasible whenever 3 < min(b). The condition in the statement of Theorem 2 can thus be interpreted as a strict feasibility requirement. It worth contrasting the result of Theorem 2 with the solution of the projection problem (5) as an exponential cone program. The latter would result in a practical complexity of O(S)), assuming that-which is often observed in practice-thy number of iterations of the employed interior-point solver does not grow with the problem dimensions. A theoretically guaranteed complexity, on the other hand, does not seem to be available at present as the commercial state-of of-the-art solvers for exponential conic programs are not proven to terminate in polynomial time.
Corollary The robust Bellman iteration (3) over a KL. divergence ambiguity set can computed to any accuracy > 0 in time ( A log A log R² -log(min / (c)rn) Rog[R/c).
[14] propose first-order framework for RMDPs over s-rectangular KL divergence ambiguity sets whose robust Bellman update enjoys a complexity of O 52. A A...Alll((e -og((-))) where E the iteration number. A careful analysis results in an overall convergence rate for the optimal MDP policy of O(S3 - e logle "J). In contrast, the convergence rate of our robust value iteration amounts to O(52.A Aog A A-log(R? 2 R. and x as constants, our convergence rate simplifies to O A log A [og(c-2]. log2(c-1] which compares favourably against the convergence rate of the first-order scheme. Our numerical results in Section show that this theoretical difference appears to carry over a favourable empirical performance on test instances as well.
-lllllmii///n (/) ko)] (ot///))lo(((-1] Treating the problem parameters
We finally note the related work [1], which optimizes a linear function over the intersection of probability simplex with constraint on the KL divergence to a nominal distribution. While one could in principle modify that algorithm to solve our projection problem (5), the resulting algorithm would require additional bisection and would thus be significantly slower than ours.
5.2 Burg Entropy
Similar the KI. divergence, the reduced projection problem (6) can further simplified univariate convex optimization problem for the Burg entropy é(t) log + t 1.
7

---

Proposition 3. For the Burg entropy o(t) = logt to 1. if > min(b), then the optimal value of the projection problem (5) equals the optimal value of the univariate convex problem
byt 1
maximize a
Σ Peae' log 1 min
(8)
S'ES
Similar to the KL divergence, the univariate optimization problem (8) can be solved efficiently.
Theorem 3. B Z min{b) + w for some w O, then the projection problem (5) can be solved to any 6-accuracy in time O(S log (max())/ (ów))]
As with the KL divergence, the projection problem (5) corresponding to the Burg entropy can be solved in a practical complexity of ((S)) as an exponential cone program, whereas we are not aware of any fate-of-the-an solvers equipped with theoretical guarantees. To our best knowledge, RMDPs with s- s-rectangular Burg entropy ambiguity sets have not been studied previously in the literature. Corollary 2. The robust Bellman teration (3) over a Burg entropy ambiguity set can be computed to any accuracy e > in time O A log A log /(e2x)) Rog(R/e]]
Similar to the previous subsection, we note that the related paper [1] optimizes a linear function over the intersection of a probability simplex with bound on the Burg entropy to nominal distribution. While that algorithm could in principle be employed to solve our projection problem (5), the resulting solution scheme would not be competitive due to the inclusion of an additional bisection.
5.3 Variation Distance
We first provide an equivalent univariate optimization problem for the reduced projection problem (6) corresponding to the variation distance @(t) = - 1/.
Proposition 4. For the variation distance ((t) = It 11, the optimal value of the projection problem (5) equals the optimal value of the univariate convex problem
maximize 2 + (b B) Σ Pons' [2 a a (min(b) by by aERt
s'ES
Once more, the univariate optimization problem (9) admits an efficient solution. Theorem 4. The projection problem (5) can be solved exactly time OSS log S).
Note that contrast to the previous results, Theorem employs binary search and thus offers an exact solution to the projection problem (5). Our result of Theorem 4 matches the complexity of the homotopy continuation method proposed by [19]. The correctness and runtime of their algorithm, however, relies lengthy ad hoc arguments, whereas Theorem 4 relies the groundwork laid by Theorem I and Proposition 1. Problem (5) can also be solved as a linear program with practical complexity of ( and a theoretical complexity of O($3.5).
Corollary The robust Bellman iteration (3) over a variation distance ambiguity set can be computed to any accuracy 0 in time O log S A Alog((/e)).
[40] study the related problem of optimizing linear function over the intersection of probability simplex with an unweighted 1-norm constraint, and they identify structural properties of the optimal solutions. Since the linear function and the norm constraint are in different places of the optimization problem, however, their findings are not directly applicable to our setting.
5.4 x² -Distancce
In contrast to the previous subsections, we directly solve the bivariate problem (6) for the ddiitancce ((t) = (t 1)2 without first formulating an associated univariate optimization problem.
Theorem 5. For the dddittance @(1) (L - 1)2, the optimal value of the projection problem (5) can be computed exactly in time O(S log S).
Theorem 5 splits the bivariate piecewise quadratic optimization problem (6) corresponding to the 2 disttance into S + 1 bivariate quadratic problems by sorting the components of b. Each of these problems can be reduced to the solution of univariate quadratic problems that themselves admit analytical solutions.
8

---

MOSEK
fast
MOSEK/fast
S A
MOSEK
fast
MOSEK/fast
1,000
47.56
0.20
243.23
100
3,383.35
22.32
151.56
1,500
71.00
0.29
241.92
150
15,353.40
51.67
297.17
2,000
89.57
0.39
231.46
200
46,049.30
83.86
549.10
2,500
114.82
0.48
239.11
250
104,709.00
130.34
803.35
3,000
139.13
0.58
241.86
300
215,871.00
176.35
1,224.05
Table 2: Comparison of our algorithms ('fast') MOSEK for the projection problem (left) and the Bellman update (right) on KL-divergence constrained ambiguity sets. Runtimes are reported ms.
S f-o its)
f-o its)
fast
f-o/fast its)
f-o/fast (5 its)
100
175.80
489.66
22.32
7.88
21.94
150
397.84
1,103.53
51.67
7.70
21.36
200
704.93
1,955.05
83.86
8,41
23.31
250
1,051.25
2,921.71
130.34
8.07
22.42
300
1,542.03
4,283.27
176.36
8.74
24.29
Table 3: Comparison of our algorithms ('fast') ) vs. the first-order method of [14] (after E = 3, its.)
for the Bellman update on KL-divergence constrained ambiguity sets. Runtimes are reported in ms.
Corollary 4. The robust Bellman iteration (3) over a x22 -diitancce ambiguity set can be computed to any accuracy 0 in time O log S A log R/e)).
The projection problem (5) for the 22 -isttance ambiguity set can be solved as a quadratic program with practical complexity of ( as well theoretical complexity of (($3.5).
The first-order framework of [14] also applies to RMDPs sets. In that case, the robust Bellman update enjoys complexity of O (
s-rectangular spherical uncertainty
522 A (c-"), where is the iteration number. careful analysis results in an overall convergence rate for the optimal MDP policy of O log S A iteration amounts (S log S A log R logl "I) Treating the parameter R as constant, convergence rate simplifies to O log S A log (og""c-')) ')), which compares favourably against the convergence rate of [14]. We remark, however, that the spherical ambiguity sets of [14] differ from the >-ddittance ambiguity
logle 'I). In contrast, the convergence rate of our robust value
studied here, and such the two methods
directly comparable.
We also note that our "ddistance ambiguity sets enjoy strong statistical justification [4, 6).
Computing unweighted 2-norm projections of points onto S-dimensional probability simplices has manifold applications in image processing, finance, optimization and machine learning [1, 8]. [30] proposes of the earliest algorithms that computes this projection in time ((S²) by iteratively reducing the dimension of the problem using Lagrange multipliers. The minimum complexity of O(S) is achieved, among others, by [27] through linear-time median-finde findinn algorithm and by [36] through a filtered nucket-clusterigg method. Note, however, that these algorithms do not account for the weights and the additional inequality constraint present in our generalized projection (5). The unweighted 2-norm projection of point onto the intersection of the S-dimensional probability simplex with axis-parallel hypereube is computed by [52] through a sorting-based method and by [2] through Newton's method, respectively. [38] optimize a linear function over the intersection of a probability simplex with an unweighted 2-norm constraint through an iterative dimension reduction scheme. [1], finally, study algorithms that optimize linear functions over the intersection of probability simplex and a bound on the unweighted 2-norm distance nominal distribution.
6 Numerical Results
We compare our fast suite of algorithms with the state-of-the-art solver MOSEK 9.3 [3] (commercial) and the first-order method of [14]. All experiments are implemented in C++, and they are run 3.6 GHz 8-Core Intel Core CPU with 32 GB 2667 MHz DDR4 main memory. The source code available at https: t//sites http://sieseeeeslleeeeeeeessseee google. com wwwccio//iieeeeeeeeeeeeieeeeeeee http/viee/////eeeeeee www.eti/ctttteeeee//ee/eeeeeeeee chin mann-pang-ii ho.

---

S
MOSEK
fast
MOSEK/fast
S = A
MOSEK
fast
MOSEK/fast
1,000
49.94
0.05
981.91
100
148.63
2.59
57.40
1,500
76.61
0.08
945.99
150
353.58
6.01
58.85
2,000
93.13
0.11
854.39
200
687.14
11.78
58.34
2,500
123.16
0.14
879.72
250
1,212.30
19.38
62.54
3,000
153.06
0.17
917.18
300
1,908.92
25.84
73.87
Table 4: Comparison of our algorithms ('fast') MOSEK for the projection problem (left) and the Bellman update (right) on x2 -ddistance constrained ambiguity sets. Runtimes are reported in ms.
For experiments, we synthetically generate random RMDP instances as follows. For the projection problem, we sample each component of b uniformly at random between O and 1. Similarly, we sample each component of Pso. uniformly at random between 0 and and subsequently scale Pso that its elements sum up to 1. The parameter 3, finally, is uniformly distributed between min b} + 10 and b 10-8 to adhere to the assumptions of our paper. For the robust Bellman update, all vectors b.a and all transition probabilities Psa. 8 S and A, generated according the above procedure. The parameter is also sampled from uniform distribution supported on [0, 1].
Tables 2-4 report average computation times over 50 randomly generated test instances for the KL-divergence and the x²-distance based ambiguity sets and show that the proposed algorithms outperform other methods. The tables reveal that algorithms are about two orders of magnitude faster than MOSEK in solving the projection problem (5). For computing the robust Bellman update also orders of magnitude faster than MOSEK, and this ratio increases with the problem size. The results also show that our algorithm outperforms the first-order method of [14]. The difference becomes more significant with an increasing number of robust Bellman updates. While our algorithms outperform the first-order scheme by a factor of 8 in the third Bellman iteration, they outperform by a factor of about 20 in the fifth Bellman iteration. Since first-order methods are known to require many iterations for convergence, we conclude that our algorithm compares favorably in this experiment as well.
J. algorithms
Conclusion
We study s-rectangular robust MDPs with o-divergence ambiguity sets. We develop efficient algo- rithms for computing robust Bellman updates for several important special cases of this ambiguity set. Our experimental results indicate that the proposed algorithms outperform MOSEK. Future work should address extensions to scalable model-free algorithms.
Acknowledgments
This work was supported, in part, by the Engincering and Physical Sciences Research Council (EPSRC) grant EP/W003317/1, by the CityU Start-Up Grant (Project No. 9610481), by the National Natural Science Foundation of China (Project No. 72032005). by the Chow Sang Sang Group Research Fund sponsored by Chow Sang Sang Holdings International Limited (Project No. 9229076), and by the NSF grant No. 1815275 Any opinion, finding, conclusion, or recommendation expressed in this material are those of the authors and do not necessarily reflect the views of the Engineering and Physical Sciences Research Council and the National Natural Science Foundation of China.
References
[1] L. Adam and V. Mácha. Projections onto the canonical simplex with additional linear inequalities. Optimization Methods & Software, Available online first, 2020.
[2] M. S. Ang, J. Ma, N. Liu, K. Huang, and Y. Wang. Fast projection onto the capped simplex with applications to sparse regression in bioinformatics. In Advances in Neural Information Processing Systems, volume 34, 2021.
[3] MOSEK ApS. MOSEK Fusion API for C++ 9.3.20, 2019. URL hww.hhttpt:t/tttt hww.ddccs.ossskk...o....oo...... com/ latest/cxxfusi /inooni//n/ee//iioeoeeeeeeeeieee html.
10

---

[4] G. Bayraksan and D. K. Love. Data-driven stochastic programming using phi- thieeivergences. In
D. M. Aleman and A. C. Thiele, editors, INFORMS TutORials in Operations Research, pages
1-19. 2015.
[5] B. Behzadian, M. Petrik, and C. P. Ho. Fast algorithms for connstraan s-rectangular robust MDPs. In Advances Neural Information Processing Systems, volume 34, 2021.
[6] A. Ben-Tal, D. den Hertog, A. de Waegenaere, B. Melenberg, and G. Rennen. Robust solutions of optimization problems affected by uncertain probabilities. Management Science, 59(2): 341-357, 2013.
[7] Z. Chen, P. Yu, and W. B. Haskell. Distributionally robust optimization for sequential decision- making. Optimization, 68(12):2397-22) 24222246,, 2019.
[8] L. Condat. Fast projection onto the simplex and the I ball. Mathematical Programming, 158 (1-2):575-585, 2016.
[9] E. Derman, M. Geist, and S. Mannor. Twice regularized MDPs and the equivalence between ro- bustness and regularization. In Advances in Neural Information Processing Systems, volume 35, pages (Pre- Preceecccedi))) 2021.
[10] M. Diehl and J. Bjornberg. Robust dynamic programming for min- max model predictive control of constrained uncertain systems. IEEE Transactions on Automatic Control, 49(12):2253-2257, 2004.
[11] R. Givan, S. Leach, and T. Dean. Intelligence, 122(1 12:11111,-, 2000.
Markov decision processes. Artificial
[12] J. Goh, M. Bayati, S. A. Zenios, S. Singh, and D. Moore. Data uncertainty in Markov chains: Application cost-effect analyses of medical innovations. Operations Research, 66(3): 697-715, 2018.
[13] V. Goyal and J. Grand- Cland-Céément. Robust Markov decision process: Beyond rectangularity. Available on arXiv, 2018.
[14] J.
and C. Kroer. Scalable first-order methods for robust MDPs. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 35, pages 12086-1204, 2021.
[15] J. Grand-Clément and C. Kroer. First-order methods for Wasserstein distributionally robust MDPs. In Proceedings of Machine Learning Research, volume 139, pages 2010-2019 2021.
[16] Grand-Clément, C. W. Chan, Goyal, and G. Escobar. Robust policies for proactive ICU transfers. Working Paper, 2019.
[17] Vishal Gupta. Near-optimal Bayesian ambiguity sets for distributionally robust optimization. Management Science, 65(9):4242-4266 2019.
[18] C. P. Ho, M. Petrik, and W. Wiesemann. Fast Bellman updates for robust MDPs. In Proceedings of the 35th International Conference on Machine Learning, pages 979-1988, 2018.
[19] C. P. Ho, M. Petrik, and W. Wiesemann. Partial policy iteration for ro-butttt Markov decision processes. Journal of Machine Learning Research, 22: 22:1-46, 2021.
[20] Q Huang, Q.- Jia, and X. Guan. Robust scheduling of EV charging load with uncertain wind power integration. IEEE Transactions on Smart Grid, 902):1043 2018
[21] G. N. Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
[22] D. L.. Kaufman and A. J. Schaefer. Robust modified policy iteration. INFORMS Journal on Computing, 25(3):396-411 2013.
[23] M. Kochenderfer and J. P. Chryssanthacopollos. Robust airborne collision avoidance through dynamic programming. Project Report ATC-371 for the Federal Aviation Administration, 2011.

---

[24] M.A.S. Kolarijani, G.F. Max, and P. Mohajerin Esfahani. Fast approximate dynamic pro- gramming for infinite-horizon markov decision processes. Advances in Neural Information Processing Systems, volume 34, pages 23652-23666, 2021.
[25] Y. Le Tallec. Robust, Risk-Sensitive, and Data-driven Control of Markov Decision Processes. PhD thesis, Massachusetts Institute of Technology, 2007.
[26] D. Love and G. Bayraksan. Phi-divergence constrained ambiguous stochastic programs for data-driven optimization. Technical report, 2015.
[27] N. Maculan and G. G. de Paula Jr. A linear-time median-finding algorithm for projecting vector on the simplex of IR.. Operations Research Letters, 8(4):219-2) 222,, 1989.
[28] S. Mannor, O. Mebel, and H. Xu. Robust MDPs with k-rectangular uncertainty. Mathematics of Operations Reseurch, 4 41(4): 1484-1999,, 2016.
[29] A. Al Marjani, A. Garivier, and A. Proutiere. Navigating to the best policy in markov decision processes. In Advances in Neural Information Processing Systems, volume 34, pages 25852- 25864, 2021.
[30] C. Michelot. A finite algorithm for finding the projection of point onto the canonical simplex of R". Journal of Optimization Theory and Applications, 50(1):195-200, 1986.
[31] A. Nie, E. Brunskill, and C. Piech. Play to grade: Testing coding games classifying markov decision process. In Advances in Neural Information Processing Systems, volume 34, pages 1506-1518, 2021.
[32] A. Nilim and L. El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 53(5):780-798, 2005.
[33] K. Panaganti and D. Kalathil, Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In Proceedings of the 38th International Conference on Machine Learning, pages 511-520, 2021.
[34] K. Panaganti and D. Kalathil. Sample complexity of robust reinforcement learning with generative model. In International Conference on Artificial Intelligence and Statistics, pages 9582-9602. PMLR, 2022.
[35] B. P.G. Van Parys, P. Mohajerin Esfahani, and D. Kuhn. From data to decisions: Distributionally robust optimization is optimal. Management Science, 67(6):3387-3402, 2021.
[36] G. Perez, M. Barlaud, L. Fillatre, and J.-C. Régin. A filtered bucket-clustering method for projection onto the simplex and the l ball. Mathematical Programming, 182(1-2):445 464, 2020.
[37] M. Petrik and D. Subramanian. RAAM: The benefits of robustness in approximating aggregated MDPs in reinforcement learning. In Advances in Neural Information Processing Systems, volume 27, pages 1987, 2014.
[38] A. Philpott, V. de Matos, and L. Kapelevich. Distributionally robust SDDP. Computational Management Science, 15(3-4):431-444 2018
[39] M. L. Puterman. Markov Decision Processes: Discrete Stochastic Dynamic Programming. John Wiley & Sons, 1994.
[40] H. Rahimian, G. Bayraksan, and T. Homem-de-Mello. Identifying effective scenarios in distri- butionally robust stochastic programs with total variation distance. Mathematical Programming, 173(1-2):393-420, 2019.
[41] R. T. Rockafellar. Convex Analysis. Princeton University Press, 1997.
[42] A. Roy, Xu, and S. Pokutta. Reinforcement learning under model mismatch. In Advances in Neural Information Processing Systems, volume 30, 2017.
12

---

[43] P. Rusmevichientong and H. Topaloglu. Robust assortment optimization under the multinomial logit choice model. Operations Research, 60(4):865 882, 2012.
[44] A. Ruszczyúski, Risk-averse dynamic programming for Markov decision processes. Mathemat- ical Programming, 125(2):235-261, 2010.
[45] J. K. Satia and R. E. Lave Jr. Markovian decision processes with uncertain transition probabilities. Operations Research, 21(3):728774) 1973.
[46] A. Shapiro. Rectangular sets of probability measures. Operations Research, 64(2):528-541, 2016.
[47] A. Shapiro. Distributionally robust optimal control and MDP modeling. Operations Research Letters, (9(3):809-814 2021.
[48] R. S. Sutton and A. G. Barto. Reinforcement Learning: An Introduction. The MIT Press, second edition, 2018.
[49] A. Tamar, Y. Glassner, and S. Mannor. Policy gradients beyond expectations: Conditional value-at-riskk. Available on arXiv, 2014.
[50] A. Tamar, S. Mannor, and H. Xu. Scaling up robust MDPs using function approximation. In Proceedings of the 31st International Conference of Machine Learning, 2014.
[51] A. Tirinzoni, X. Chen, M. Petrik, and B. D. Ziebart, Policy-conditioned uncertainty sets for robust Markov decision processes. In Advances in Neural Information Processing Systems, volume 31, pages 8953-8963, 2018.
[52] W. Wang and C. Lu. Projection onto the capped simplex. Available arXiv, 2015.
[53] Y. Wang and S. Zou. Online robust reinforcement learning with model uncertainty. In Advances in Neural Information Processing Systems, volume 34, pages 7193-7206, 2021.
[54] Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. In Proceedings of the 39th International Conference on Machine Learning, pages 23484-23526. 2022.
[55] T. Weissman, E. Ordentlich, G. Seroussi, S. Verdu, and M. J. Weinberger. In- equalities for the I deviation of the empirical distribution. Technical Report, attps://www hpw. hp. www.reseeaccciiiff theory/pappee Stte:e////PLL22--9911101 ..df.... 2003.
[56] W. Wiesemann, D. Kuhn, and B. Rustem. Robust Markov decision processes. Mathematics of Operations Research, 3811):153-18, 2013.
[57] H. Xiao, K. Yang, and X. Wang. Robust power control under channel uncertainty for cognitive radios with sensing delays. IEEE Transactions on Wireless Communications, 12(2):646-655, 2013.
[58] L. Xin and D. A. Goldberg. Distributionally robust inventory control when demand martingale. Available on arXiv, 2018.
[59] H. Xu and S. Mannor. Distributionally robust Markov decision processes. In Advances in Neural Information Processing Systems, volume 23, pages 2505-2513, 2010.
[60] H. Xu and Mannor. Distributionally robust Markov decision processes. Mathmmttcs of Operations Research, 37(2):288-300 2012.
[61] Yu and H. Xu. Distributionally robust counterpart in Markov decision processes. IEEE Transactions on Automatic Control, 6109):538-22533 2016.
[62] Y. Zhang, L. N. Steimle, and B. T. Denton. Robust Markov decision processes for medical treatment decisions. Available on Optimization Online, 2017.
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 abstract well explains the main contributions the paper.
(b) Did you describe the limitations your work? [Yes] We took great care ensure that our numerical results provide an objective and unbiased assessment of our solution approach.
(c) Did you discuss any potential negative societal impacts your work? [N/A] There are no new negative societal impacts that we can identify.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes] We have carefully read those guidelines, and to our best understanding our paper fully complies with them.
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All of our results state the full set of assumptions, with exception of the blanket assumptions that are assumed to hold throughout the paper and that are clearly marked as such.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs contained in the appendix.
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as a URL)? [Yes] All code and instructions for our experimental results are published online.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] All details are mentioned either in the numerical results section or the appendix.
(c) Did you report error bars (e.g.. with respect to the random seed after running experi- ments multiple times)? [Yes] Included in the appendix.
(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] Included in the numerical results section.
4. If you using existing assets (e.g., code, data, models) curating/releasing assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We use C++ and MOSEK, all of which are cited the text.
(b) Did you mention the license of the assets? [Yes] All licenses are mentioned.
(c) Did you include any new assets either in the supplemental material or as URL? [Yes] All code and instructions for our experimental results are published online.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A] We use synthetic data in our experiments.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A] We use synthetic data in our experiments.
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] We use synthetic data in our experiments.
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A] We use synthetic data our experiments.
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A] We use synthetic data in our experiments.
14


Reviews:
[{"review_id": "LWA8OaRvK4j", "reviewer": "Reviewer_KgfB", "summary": "This paper proposed equivalence between the robust Bellman operator and a projected optimization problem. Also, several solutions to the projected optimization problems are developed for different distance measures. ", "questions": "See the above part.", "limitations": "This paper mainly focuses on the model-based setting, which limits the contributions. Also, some external methods like binary search or other optimization methods are introduced and hence will complexify the method. ", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: (1). The $\\phi$-divergence is general hence several distance measures are included; (2). The proposed method works for many different uncertainty sets. (3). The complexity matches the one for non-robust problems. \n\nWeakness: (1). Although this is a model-based method, many model-free methods aren't discussed, e.g., [1,2,3]. More related works should be discussed. \n(2). Theoretically, the authors didn't explain clearly why the method in this paper is better than the value iteration or dynamic programming method for robust RL problems.\n\n\n\n[1 ]Wang, Yue, and Shaofeng Zou. \"Online robust reinforcement learning with model uncertainty.\" Advances in Neural Information Processing Systems 34 (2021): 7193-7206.\n[2] Panaganti, Kishan, and Dileep Kalathil. \"Sample Complexity of Robust Reinforcement Learning with a Generative Model.\" International Conference on Artificial Intelligence and Statistics. PMLR, 2022.\n[3] Badrinath, Kishan Panaganti, and Dileep Kalathil. \"Robust reinforcement learning using least-squares policy iteration with provable performance guarantees.\" International Conference on Machine Learning. PMLR, 2021.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "EwaxyILs8LX", "reviewer": "Reviewer_gVaR", "summary": "The paper studies robust MDPs with s-rectangular ambiguity sets defined by $\\phi$-divergence. The authors then propose a number of fast algorithms with complexity analyses for different popular $\\phi$-divergences. Numerical results were then provided to support the methodologies.  The paper is well-written. The problem studied is highly relevant and of importance. ", "questions": "- Why are $\\phi$-divergence (s)-rectangular ambiguity sets useful? \n- Can we handle ambiguity sets defined by several $\\phi$-divergences?\n- Can the algorithms developed apply to policy improvement?", "limitations": "I don't see any limitations and potential negative societal impact of their work.", "rating": 5, "confidence": 4, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths:\n\nRobust MDP is an important topic in ML/AI and the question of how to quickly solve a robust MDP problem is highly relevant. It is known in the literature that to maintain tractability, one needs to stick with (s)- or (sa)-rectangular ambiguity sets. The paper focuses on several types of (sa)-rectangular sets and provides rigorous investigations, which is good and would be a good contribution to the research topic. \n\n### Weaknesses:\n\nMy main concern goes to the novelty and the significance of the work. Robust MDP is already widely studied and well understood. The paper does not provide new robust MDP models, but only focuses on how to quickly solve the robust MDO problem under some well-known uncertainty settings (the use $\\phi$-divergence ambiguity sets in robust MDP is not new). Note that $\\phi$-divergence (sa)-rectangular ambiguity sets were already studied in the literature, thus the work here is just an extension to (s)-rectangularity settings.\n\n**Other comments**\n\nThe paper only discusses value iteration; how's about policy evaluation and policy improvement?\n\nThe experiments are quite limited since the authors only compare their algorithms with MOSEK solvers. I can see that the Bellman equation has a standard max-min form with a linear objective function, for which several efficient algorithms exist. \n\nDiscussions on why $\\phi$-divergence (s)-rectangular ambiguity sets are useful and how to construct them seem missing. \n\n ", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "1yJhGudJXj", "reviewer": "Reviewer_19se", "summary": "This paper investigates the problem of computing the robust Bellman operator efficiently when the uncertainty set is defined using $\\phi$-divergence. The basic idea is to calculate the robust Bellman update via simplex projections, which can be solved efficiently. Multiple examples of $\\phi$-divergence defined uncertainty sets are given, including Kullback-Leibler Divergence, Burg Entropy, Variation Distance, $\\chi^2$-divergence. Numerical experiments are provided to demonstrate the efficiency of the proposed method.", "questions": "Please see Strengths And Weaknesses.", "limitations": "NA.", "rating": 6, "confidence": 5, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\nThis paper investigates a more general notation of uncertainty set, s-rectangular, which is less conservative than the (s,a)-rectangular uncertainty set model. A large class of distance metrics, i.e., $\\phi$-divergence defined uncertainty sets are studied. The proposed method is claimed to be more computationally efficient. Theoretical results and numerical experiements validates these claims. Overall, the contribution is useful in practice.\n\n\nWeaknesses:\nThe major weakness of this paper lies in the presentation. In section 4, the author claim that the robust Bellman operator can be solved efficiently if the projection problem in (4) can be solved efficently. However, it is not discussed at all how the projection problem in (4) is related to the robust Bellman operator. It is thus not clear to this reviewer that once the projection in (4) is solved, how it is going to be used in the evaluation of the robust Bellman operator. As in section 5, the discussion is focused on solving the projection in (4) for various types of $\\phi$-divergences. The overall presentation of the paper needs to be carefully revised.\n\nSecond, the setting focused in this paper is the s-rectangular uncertainty set. One question is that if the problem is reduced to the (s,a)-rectangular uncertainty set, is the challenging in evaluating the robust Bellman operator still exist? As for the (s,a)-rectangular uncertainty set, the problem is reduced to a distributionally robust optimization problem for each (s,a) pair. Therefore, the motivation of considering the s-rectangular uncertainty set shall be carefully discussed in order to motivate the research in this paper. \n\nThird, this paper mainly focus on the model-based planning setting, where the uncertainty set is assumed to be known. Therefore, the approach in this paper might be difficult to be generalized to the practical reinforcement learning setting with large or even continuous state and action spaces. \n\nFourth, there is another line of research focus on model-free robust reinforcement learning, where the uncertainty set is not known, and samples from the center of the uncertainty set can be obtained. Different uncertainty set models are considered, e.g., ellipsoid type uncertainty set models and $\\epsilon$-contamination uncertainty set model. Those algorithms are computationally efficient (the complexity at each iteration is independent of S and A), and can be easily extended to the case with function approximation for large state-action sapces. \nReinforcement learning under model mismatch. NIPS 2017.\nOnline Robust Reinforcement Learning with Model Uncertainty. NeurIPS 2021.\nRobust reinforcement learning using least squares policy iteration with provable performance guarantees. ICML 2021.\nPolicy Gradient Method For Robust Reinforcement Learning, ICML 2022.\n\n\n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept