Online Policy Optimization for Robust MDP
Authors: Jing Dong
Jingwei Li
Baoxiang Wang
Jingzhao Zhang
Venue: Submitted to ICLR 2023 (2023)

Abstract: Reinforcement learning (RL) has exceeded human performance in many synthetic settings such as video games and Go. However, real-world deployment of end-to-end RL models is rare, as RL models can be very sensitive to slight perturbation of the environment. The robust Markov decision process (MDP) framework---in which the transition probabilities belong to an uncertainty set around a nominal model---provides one way to develop robust models. While previous analysis shows RL algorithms are effective assuming access to a generative model, it remains unclear whether RL can be efficient under a more realistic online setting, which requires carefully balancing exploration and exploitation. In this work, we consider online robust MDP by interacting with an unknown nominal system. We propose a robust optimistic policy optimization algorithm that is provably efficient. To address the additional uncertainty caused by an adversarial environment, our model features a new optimistic update rule derived via Fenchel conjugates. Our analysis establishes the first regret upper bound for online robust MDPs. 

Under review as a conference paper at ICLR 2023
ONLINE POLICY OPTIMIZATION FOR ROBUST MDP
Anonymous authors
Paper under double-blind review
ABSTRACT
Reinforcement learning (RL) has exceeded human performance in many syn- thetic settings such as video games and Go. However, real-world deployment of end-to-end RL models is less common, as RL models can be very sensitive to slight perturbation of the environment. The robust Markov decision process (MDP) framework in which the transition probabilities belong an uncertainty set around a nominal model-provides one way to develop robust models. While previous analysis shows RL algorithms are effective assuming access gen- erative model, it remains unclear whether RI. can be efficient under a more re- alistic online setting, which requires careful balance between exploration and exploitation. In this work, we consider online robust MDP by interacting with an unknown nominal system. We propose robust optimistic policy optimization algorithm that is provably efficient. To address the additional uncertainty caused by an adversarial environment, our model features a new optimistic update rule derived via Fenchel conjugates. Our analysis establishes the first regret bound for online robust MDPs.
INTRODUCTION
The rapid progress of reinforcement learning (RL) algorithms enables trained agents to navigate around complicated environments and solve complex tasks. The standard reinforcement learning methods, however, may fail catastrophically in another environment, even the two environments only differ slightly in dynamics (Farebrother et al.] 2018 Packer et al.) 2018 Cobbe et al.) [2019] Song et al., 2019) Raileanu & Fergus, 2021). In practical applications, such mismatch of environ- ment dynamics are common and can be caused by a number of reasons, e.g., model deviation due to incomplete data, unexpected perturbation and possible adversarial attacks. Part of the sensitivity of standard RL algorithms stems from the formulation of the underlying Markov decision process (MDP). In sequence of interactions, MDP assumes the dynamic to be unchanged, and the trained agent be tested on the same dynamic thereafter.
To model the potential mismatch between system dynamics, the framework of robust MDP is intro- duced to account for the uncertainty of the parameters of the MDP (Satia & Lave Jr 1973 White III & Eldeib 1994 Nilim & El Ghaoui 20055 [yengar 2005). Under this framework, the dynamic of MDP no longer fixed but can come from some uncertainty set, such the rectangular uncer- tainty set, centered around a nominal transition kernel. The agent sequentially interacts with the nominal transition kernel to learn policy, which is then evaluated on the worst possible transition from the uncertainty set. Therefore, instead of searching for policy that may only perform well on the nominal transition kernel, the objective find the worst-case best-performing policy. This can be viewed dynamical zero-sum game, where the RL agent tries to choose the best policy while nature imposes the worst possible dynamics. Intrinsically, solving the robust MDPs involves solving max-min problem, which is known to be challenging for efficient algorithm designs.
More specifically, if generative model (also known as simulator) of the environment or a suitable offline dataset is available, one could obtain a e-optimal robust policy with Ō(E -2) samples under a rectangular uncertainty set (Qi & Liao, 2020 Panaganti & Kalathil 2022 Wang & Zou 2022 Ma
et al. 2022b. Yet the presence of a generative model is stringent to fulfill for real applications. In a
more practical online setting, the agent sequentially interacts with the environment and tackles the challenge as balances between exploring the state space and exploiting
the high-reward actions. In the robust MDP setting, previous sample complexity results cannot

---

Under review as a conference paper at ICLR 2023
directly imply sublinear regret in general Dann al. (2017) and so far no asymptotic result is available. A natural question then arises:
Can we design a robust RI. algorithm that attains sublinear regret under robust MDP with rectangular uncertainty set?
In this paper, we answer the above question affirmatively and propose the first policy optimization algorithm for robust MDP under a rectangular uncertainty set. One of the challenges for deriving regret guarantee for robust MDP stems from its adversarial nature. As the transition dynamic can be picked adversarially from predefined set, the optimal policy may be randomized (Wiesemann) al. 2013). This is in contrast with conventional MDPs, where there always exists a deterministic optimal policy, which can be found with value-based methods and a greedy policy (e.g. UCB-VI algorithms). Bearing this observation, resort policy optimization (PO)-based methods, which directly optimize a stochastic policy in an incremental way.
With stochastic policy, algorithm explores robust MDPs in optimistic manner. To achieve this robustly, we propose a carefully designed bonus function via the dual conjugate of the robust bellman equation. This quantifies both the uncertainty stemming from the limited historical data and the uncertainty of the MDP dynamic. In the episodic setting robust MDPs, we show that our algorithm attains sublinear regret O(v K) for both (s, a) and s-rectangular uncertainty set, where K the number of episodes. In the case where the uncertainty set contains only the nominal transition model, our results recover the previous regret upper bound of non-robust policy optimization (Shani al. 2020). Our result achieves the first provably efficient regret bound in the online robust MDP problem, as shown in Table We further validated our algorithm with experiments.
Table 1: Comparisons of previous results and our results, where S, A are the size of the state space and action space, H is the length of the horizon, K is the number of episodes, p is the radius of the uncertainty set and is the level of suboptimality. We shorthand e = [Sg(SAH² (3 + p)). The regret upper bound by Panaganti & Kalathil 2022) are obtained through converting their sample complexity results and the sample complexity result for work converted through our regret bound. We use "GM" denote the requirement of generative model. The superscript stands for results obtained batch-to-onling conversion. The reference
to the previous works are [A]; Panaganti & Kalathil (2022). [B]: Waag & Zou 20211, [C]: Badrinath & Kalathil
20211.
[D]: Yang et al. (2021).
Algorithm
Requires
Rectangular
Regret
Sample Complexity
[A]
Value based
GM
(s, a)
o 3
H S A
Value based
[B]
(s, a)
NA
Asymptotic
Policy
[C]
based
(s, a)
NA
Asymptotic
H* A(2+t))
Value
(s, a)
NA
[D]
GM
based
H 12 p322
s
NA
Policy
(s)
0
SH2VAKi
H S A 2²
Ours
based
SAPH2
H H* A
s
RELATED WORK
RL with robust MDP Different from conventional MDPs, robust MDPs allow the transition ker- nel to take values from uncertainty set. The objective in robust MDPs is to learn an optimal robust policy that maximizes the worst-case value function. When the exact uncertainty set known, this can be solved through dynamic programming methods (Iyengar 2005 Nilim & El Ghaoui 2005 Mannor et al. 2012). Yet knowing the exact uncertainty set is a rather stringent requirement for most real applications. If one has access to generative model, several model-based reinforcement learning methods are proven to be statistically efficient. With the different characterization of the uncertainty set, these methods can enjoy sample complexity of ((1/c2) for e-optimal robust
2

---

Under review as a conference paper at ICLR 2023
value function Panaganti & Kalathil 2022 Yang al. 2021 Similar results can also be achieved
an offline dataset is present, for which previous works Qi & Liao (2020) Zhou et al. (2021); Kallus et al. (2022) Ma et al. 2022) show the ((1/e²) sample complexity for e-optimal policy.
In addition, Liu et al. (2022) proposed distributionally robust policy Q-learning, which solves for
the asymptotically optimal ffunccioo..
In the case of online RL. the only results available are asymptotic. In the case discounted MDPs, Wang & Zoul (2021); [addinathh & Kalathil (2021) study the policy gradient method and show an O convergence rate for an alternative learning objective (a smoothed variant), which could be equivalent the original policy gradient objective in an asymptotic regime. These results in sample complexity and asymptotic regimes in general cannot imply sublinear regret in robust MDPs (Dann
et al. 2017)
RL with adversarial MDP Another line of works characterizes the uncertainty of the environment through the adversarial MDP formulation, where the environmental parameters can be adversarially chosen without restrictions. This problem is proved to be NP-hard to obtain low regret (Even- ct al. 2004). Several works study the variant where the adversarial could only modify the reward function, while the transition dynamics of the MDP remain unchanged. In this case, it is possible to obtain policy-based algorithms that efficient with sublinear regret (Rosenberg & Mansour 2019 Jin & Luo 2020 Jin et al., 2020 Shani et al.] 22200] Cai et al. 2020). On a separate vein, investigates the setting where the transition only allowed be adversarially chosen for C' out of the K total episodes. A regret of O + /K) established thereafter (Lykouris al. 2021
Chen et al. 2021b Zhang et al. 2022).
Non-robust policy optimization The problem of policy optimization has been extensively inves- tigated under non-robust MDPs (Neu al. 2010 Cai al. 2020; (hani et al.) 20.0 Wu al., [022] Chen et al., 2021a). The proposed methods are proved to achieve sublinear regret. The methods are
also closely related to empirically successful policy optimization algorithms in RL, such as PPO
Schulman et al. (011)) and TRPPOSShulman et al. (2015).
ROBUST MDP AND UNCERTAINTY SETS
In this section, we describe the formal setup of robust MDP. We start with defining some notations.
Robust Markov decision process We consider an episodic finite horizon robust MDP, which can denoted by tuple M = AS, H, (Pa) ( Here S is the state space, A is the action space, {r) h=1 is the time-dependent reward function, and H is the length of each episode. Instead of a fixed time-dependent uncertainty kernels, the transitions of the robust MDP is governed by kernels that are within time-dependent uncertainty set ) i.e., time-dependent transition Pa E PA C As at time h.
The uncertainty set P is constructed around nominal transition kernel (PR), and all transition dynamics within the set are close to the nominal kernel with a distance metric of one's choice. Different from an episodic finite-horizon non-robust MDP, the transition kernel P may not only be time-depended uncertainty set P. We consider the case where the rewards are stochastic. This is, on state-action (s, a) at time h, the immediate reward is Rd (s, a) E [0. 1]. which is drawn i.idd from a distribution with expectation ra (s, a). With the described setup of robust MDPs, we now define the policy and its associated value.
but may also be chosen (even adversarially) from a specified time-dependent
{TA [m where each TA is a function from to the probability simplex over actions, (AA). If the transition kernel is fixed to be P. the performance of policy π starting from state at time can be measured by its value function, which is defined as
Policy and robust value function A time-dependent policy π is defined
V. (s) ET,
Σ The (sw,,a)) 18h
3

---

Under review as a conference paper at ICLR 2023
In robust MDP, the robust value function instead measures the performance of under the worst possible choice of transition P within the uncertainty set. Specifically, the value and the Q-value function of policy given the state action pair (s, a) step / are defined as
(s) = min (P.)E(P))
V. (s),
Qī
min (PN)
(P)(P)
Σ ra(sw,, (Sh: an) (s,
The optimal value function is defined be the best possible value attained by a policy
Ve = max (s) max min (Pr)E(PN)
Vo (P)(())ss) (s).
The optimal policy is then defined to be the policy that attains the optimal value.
Robust Bellman equation Similar to non-robust MDP, robust MDP has the following robust bell-
man equation, which characterizes a relation to the robust value function (Ho et al. 2021: Yang
et al. 202T
(16,,a)-((s,)) = + opA (Vi+1)()))) (i(() (,
where
Pr, (v,+))
min Pa(- 8, V 8,)- 1 1,,))((')) PREPI.
e'ES
Without additional assumptions on the uncertainty set, the optimal policy and value of the robust
MDP are in general NP-hard to solve (Wiesemann et al. 2013). One of the most commonly as-
sumptions that make solving optimal value feasible is the rectangular assumption (Iyengar [0055] Wiesemann et al. 2013: Badrinath & Kalathil 2021 Yang et al. 2021 Panaganti & Kalathil 2022).
Rectangular uncertainty sets To limit the level of perturbations, we assume that the transition kernels close to the nominal transition measured via distance. We consider two cases.
The (s, a) reetanngul assumption assumes that the uncertain transition kernel within the set takes value independently for each (s, a). We further use Ei distance characterize the (s, reectanggal set around a nominal kernel with a specified level of uncertainty.
Definition 3.1 ((s, a)- rectangular uncertainty set [yengar 22005;; Wiesemann et al. 2013 ), For all time step h and with given state-action pair (s, a.). the reetannuull uncertainty set Pa(s, a)
is defined as
a) (l s, - P.C s, a)ll S p, P,( 8, E
where PR is the nominal transition kernel h, Pp s, 0, v(s E S A, p is the level of uncertainty and (SS) denotes the probability simplex over the state space S.
With the (s, a) aereennana set, it shown that there always exists an optimal policy that is deter- ministic Wiesemann al. (2013).
One way to relax the (s, a -eetttaanar assumption is to instead let the uncertain transition kernels within the set take value independent for each only. This characterization is then more general and its solution gives stronger robustness guarantee.
Definition 3.2 (s-rectangular uncertainty set Wiesemann et al. 2013)). ). For all time step and with given state 8, the s-rectangular uncertainty set (s) defined
Σ (P - PRC s, s, S Ap, Ph Ph(--s,)) =
Ps(s)
where PR is the nominal transition kernel at h, P | s, > 0, ((s E S x A, p is the level of uncertainty, and (SS) denotes the probability simplex over the state space S.
4

---

Under review as a conference paper at ICLR 2023
Different from the reectanulll assumption, which guarantees the existence of a deterministic optimal policy, the optimal policy under s-rectangular set may need to be randomized (Wiesemann
et al., 2013). We also remark that the requirement of ( s, s. 0 is mostly for technical convenience.
Equipped with the characterization of the uncertainty set, we now describe the learning protocols and the definition of regret under the robust MDP.
Learning protocols and regret We consider a learning agent repeatedly interacts with the envi- ronment in an episodic manner, over K episodes. At the start of each episode, the learning agent picks policy πy and interacts with the environment while executing Ty. Without loss of generality, we assume the agents always start from fixed initial state s. The performance of the learning agent measured by the cumulative regret incurred the K episodes. Under the robust MDP, the cumulative regret is defined to be the cumulative difference between the robust value of TT and the robust value of the optimal policy,
Regret(K)
- k=1
where of is the initial state.
We highlight that the transition of the states in the learning process is specified by the nominal transition kernel /= though the agent only has access to the nominal kernel in online manner. We remark that if the agent is asked to interact with a potentially adversarially chosen transition from an arbitrary uncertainty set, the learning problem is Even- Even- et al. (2004).
One practical motivation for this formulation could be as follows. The policy provider only sees feedback from the nominal system, yet she aims to minimize the regret for clients who refuse to share additional deployment details for privacy purposes.
4 ALGORITHM
Before we introduce algorithm, first illustrate the importance of taking uncertainty into sideration. With the robust MDP, one of the most naive methods to directly train a policy with the nominal transition model. However, the following proposition shows optimal policy under the nominal policy can be arbitrarily bad in the worst-case transition (even worse than random policy).
Claim 4.1 (Suboptimality of non-robust optimal policy). There exists a robust MDP M (S, A, P.r, r, H) with uncertainty sei P of uncertainty radius such that the non-robust optimal policy is ((1))suubpl to the uniformly random policy.
The proof of Proposition 4.1 is deferred to Appendix D With the above-stated result, it implics the policy obtained with non-robust RL algorithms, can have arbitrarily bad performance when the dynamic mismatch from the nominal transition. Therefore, we present the following robust optimistic policy optimization to avoid this undesired result.
4.1 ROBUST OPTIMISTIC POLICY OPTIMIZATION
With the presence of the uncertainty set, the optimal policies may be all randomized Wiesemann al. 2013). In such cases, value-based methods may be insufficient as they usually rely on deterministic policy. We thus resort to optimistic policy optimization methods Shani et al. 2020 which directly learn a stochastic policy.
Our algorithm performs policy optimization with empirical estimates and encourages exploration by adding a bonus to less explored states. However, we need to propose a new efficiently computable bonus that is robust to adversarial transitions. We achieve this via solving sub-optimization prob- lem derived from Fenchel conjugate. We present Robust Optimistic Policy Optimization (ROPO) in Al Algorithm and elaborate its design components.
5

---

Under review as a conference paper at ICLR 2023
To start, algorithm has access to the actual reward and transition function, following empirical estimator of the transition and reward:
the
Ei Hi (s, a)
5 = = =a}
(s)
No (s,
=k' I 8, at a, s =
poak (s, a,
(2)
N (s)
where (s, max ->
s, a 1 counts the number of visits to (s, a).
Optimistic Robust Policy Evaluation In each episode, the algorithm estimates Q-values with an optimistic variant of the bellman equation. Specifically, to encourage exploration in the robust MDP, we add a bonus term by (8, a), which compensates for the lack of knowledge of the actual reward and transition model as well as the uncertainly set, with order by, (s, a) = O (s) 1)/12).
(h a) min ((s,,)) o,, (V,+)) a) (s, H).
(s) (0. a. 18))
Intuitively, the bonus term by desires characterize the optimism required for efficient exploration for both the estimation errors of P and the robustmess of P. It is hard to control the two quantities in their primal form because of the coupling between them. We propose the following procedure to address the problem.
Note that the key difference between our algorithm and standard policy optimization is that p,, (s)) requires solving an inner minimization d1. Through relaxing the constraints with Lagrangian multiplier and Fenchel conjugates, under (s, -rectangull set, the inner minimization problem can be reduced to a one-dimensional unconstrained convex optimization problem on IR (Lemma
(11 min h+ (+))+ p PR(s s, (
VTT (
sup
The optimum of Equation (3) is then computed efficiently with bisection or sub- 10--grrdieett methods. We note that while the dual form has been similarly used before under the presence of generative model or with an offline dataset (Badrinath Kalathil, 2021] Panaganti Kalathil, 2022 Yang
al. 2021), it remains unclear whether is effective for the online setting.
Similarly, the case of s-rectangular set, the inner minimization problem is equivalent to a dimensional convex optimization problem.
sup Σ Th Σ P 8,a') (Tl 1laa' = U/ff
8'.a'
ApiNe I(a' = a V 84 h+1 (8'))
min a'
(4)
where a (x))))
In addition to reducing computational complexity, the dual form (Equation 3 and Equation 44 decouples the uncertainty in estimation error and in robustness, as p and Po are in different terms. The exact form of 0Y is presented in the Equation and
Using the optimistic Q-value obtained from policy evaluation, the al- gorithm improves the policy with a KL regularized online mirror descent step.
Policy Improvement Step
k+1 E arg max B(VV,"" .) , DKz(mllm))
where 3 is the learning rate. Equivalently, the updated policy is given by the closed-form solution Th I+1 (a s) = z exp(8Q
E. (3Q An important property of policy improvement is to use fun- damental inequality 7 of online mirror descent presented (Shani et al., 2020). We suspect that other online algorithms with sublinear regret could also be used in policy improvement.

---

Under review as a conference paper at ICLR 2023
In the non-robust case, this improvement step is also shown to be theoretically efficient (Shani et al. 2020; Wu et al.] 2022). Many empirically successful policy optimization algorithms. such PPO (Schulman al. 2017) and TRPO (Schulman et al. (2015), also take similar approach to KI regularization for non-robust policy improvement. Putting everything together, the proposed algorithm is summarized in Algorithm
Algorithm Robust Optimistic Policy Optimization (ROPO)
Input: learning rate B. bonus function b for k ...... K do
Collect a trajectory of samples by executing Tk.
# Robust Policy Evaluation
for = H H...., do
for as,
A do
Solve p. (1++1) (s, a) according to Equation (3) for (s, reettangga set Equation 4 for s-rectangular
(s, min ((8,a) or (V (s, (1, H}.
end for for Vs E do (s) (s, (
end for end for # Policy Improvement
for Vh, 8, a [M] x S x do á expl BQ (s,a)) E.' expl (Q,,()
" (a
end for
Update empirical estimate i, P with Equation 2 end for
THEORETICAL RESULTS
We are now ready analyze the theoretical results of our algorithm under the uncertainly set.
5.1 RESULTS UNDER (s, a)) RRECANNGUL UNCERTAINTY SET
Equipped with Algorithm and the bonus function described in Equation We obtain the regret upper bound under (s, a) -eettannga uncertainty set described in the following Theorem.
Theorem (Regret under (s, a) rectangular uncertainty set). With learning rate B bonus term b), as ( with probability at least d, the regret incurred by Algorithm over K episodes bounded by Regret(K)) 0 H² s Aolog K3/H2 p)/8)
log and H
Remark 5.1. When p O, the problem reduces to non-robust reinforcement learning. In such case our regret upper bound Ö (H2S/AK) which is the same order of policy optimization algorithms for the non-robust case Shani al. (2020).
While we defer the detailed proof to the appendix proof below.
Ae we sketch and highlight the challenges in the
First, unlike policy optimization for non-robust MDP, classic lemmas such as the value difference lemma (Shani et al. 2020) be longer applied, because the adversarial transition kerell are policy dependent. Naively employing a recursive relation with respect to a fixed transition kernel in similar way the value difference lemma may lead to linear regret. To address this issue,

---

Under review as a conference paper at ICLR 2023
propose the following decomposition,
(s) (s) S Ex. (ra(s,a) - (), a)) + (o (V a) - A.is,a) (V (s a)) ())))
+ Er. (Palaa) (Vi+ 1)),) Ppllaaa (1
(Q7 (s, T. --- s))
In particular, we perform recursion conditioned on varying transition kernel pa(: s,a) arg max Pal- | aV Vi41)) P.EPk
However, this introduces another problem. Maintaining optimism is hard the expectation of each time step h is taken with respect to a different transition kernel. To establish an optimism bonus for the uncertainty of the transition caused by limited interaction and the uncertainty set, we derive the dual formulation of inner optimization problem P(...)) (V) (3) This allows us to decouple the
uncertainty and bound each source of uncertainty separately.
Notice that now the difference of (P....)) (V) PPr,,, (V) is only incurred by the difference in Σ. (s 8, 8, (1- (x')((")) We then show that must be bounded at its optimum by inspecting certain pivot points and by the convexity of the dual. When we have the desired bounds of 17, applying Hoeffding's 's inequality with an e-net argument will yield the claimed regret bound.
Our algorithm and analysis techniques can also extend to other uncertainty sets, such as KL diver- gence constrained uncertainly set. We include the KL divergence result in Appendix C
5.2 RESULTS UNDER S- RERCAANGULAR UNCERTAINTY SET
Beyond the (s, a -rectanguua uncertainty set, we also extends to s-rectangular uncertainty set (Def- inition 3.2 Recall that value-based methods do not extend to s-rectangular uncertainty set as there might not exist a deterministic optimal policy.
Theorem 2 (Regret under s-rectangular uncertainty set). With learning rate 3 bonus term by as 16) with probability least 5, the regret of Algorithm bounded by Regret( K) O (SA2 1 p)/6).
2 A
H²K and
Remark 5.2. When p = 0, the problem reduces to non-robust reinforcement learning. In such case regret upper bound is Ô (SA' VK). Our result the first theoretical result for learning robust policy under s-rectangular uncertainty set, as previous results only learn the robust value function (Yang et al. 202I).
The analysis and techniques used for Theorem great similarity to those ones used for Theorem
The main difference is on bounding (Px()) (VTT1) - (V as, We defer the detailed proof the appendix B
EMPIRICAL RESULTS
To validate our theoretical findings, we conduct a preliminary empirical analysis of our purposed robust policy optimization algorithm.
Environment We conduct the experiments with the Gridworld environment, which is early ample reinforcement learning from [Suttnn Barto (2018)) The environment is two-dimensional and is in cell-like environment. Specifically, the environment a 5 grid, where the agent starts from the upper left cell. The cells consist of three types, road (labeled with o), wall (labeled with æ), or reward state (labeled with +). The agent can safely walk through the road cell but the wall cell. Once the agent steps on the reward cell, it will receive a reward of 1, and it will receive no rewards otherwise. The goal the agents collect as many rewards as possible within the allowed time.
8

---

Under review as a conference paper at ICLR 2023
The agent has four types of actions each step, up. down, left, and right. After taking the action, the agent has a success probability of p to move ac- cording to the desired direction, and with the remaining probability of moving to other directions.
San
X
x
Experiment configurations To simulate the robust MDP, we create a nom- inal transition dynamic with success probability p = 0.9. The learning agent will interact with this nominal transition during training time and interact with a perturbed transition dynamic during evaluation. the transitions are perturbed against the direction is agent is directing with a constraint of p. Under s-rectangular set, the transitions are perturbed against the direction of the goal state. Figure [ shows an example of our environment, where the perturba- tion caused some of the optimal policies under nominal transition to be sub-optimal under robust transitions. We denote the perturbed transition robust transitions in our results. We implement our proposed robust policy optimization algorithm along with the non-robust variant of it |Shan et al. (2020). The inner minimization of our Algorithm is computed through its dual formulation for efficiency. Our algorithm is implemented with the rLberry framework (Domingues et al. 2021).
Figure Example of the Gridworld envi- ronment.
(s, a -eretttngguaar set,
Results We present results with p= 0.1, 0.2, 0.3 under (s, a) rectanggull set here in Figure The results with s-rectangular sets are included in the appendix. We present the averaged cumulaaive rewards during evaluation. Regardless of the level of uncertainty, we observe that the robust variant of the policy optimization algorithm is more robust to dynamic changes as it is able to obtain higher level of rewards than its non-robust variant.
with rohual cranttion Ruau-r P0 i IISUO moniiio
rSQudl RoNurs 3O ART movr TmecII
Aust Rueripod Epioade Rowards
Intrgged Ephodde Rowards
Roburt PO WUTh miur
Iucrgge Eatoade Rowards
Number of Eploodes
Number Epleodes
Number Epirodes
(a) = 0.1
(b) = 0.2
(c) p = 0.3
Figure Cumulative rewards obtained by robust and non-robust policy optimization robust transition with different level uncertainty p = 0.1,0.2, 0.3 under & distance, (s, a) -eeetanaan set.
7 CONCLUSION AND FUTURE DIRECTIONS
In this paper, we studied the problem of regret minimization in robust MDP with a rectangular uncertainty set. We proposed robust variant of optimistic policy optimization, which achieves sub- linear regret in all uncertainty sets considered. Our algorithm delicately balances the exploration- exploitation trade-off through a carefully designed bonus term, which quantifies not only the uncer- lainty due to the limited observations but also the uncertainty of robust MDPs. Our results are the first regret upper bounds in robust MDPs as well as the first non -on-asymptotic results in robust MDPs without access to a generative model.
For future works, while our analysis achieves the same bound as the policy optimization algorithm in Shani et al. (2020) when the robustness level O. we suspect some technical details could be improved. For example, we required P% to be positive for any 8, a so that we could do change of variable to form an efficiently solvable Fenchel dual. However, the actual positive value gets canceled out later and does not show up in the bound, suggesting that the strictly positive assumption might be an artifact of analysis.
Furthermore, our work could also be extended in several directions. One is to consider other charac- terization of uncertainty sets, such the Wasserstein distance metric. Another direction is to extend robust MDPs to a wider family of MDPs, such as the MDP with infinitely many states and with function approximation.

---

Under review as a conference paper at ICLR 2023
REFERENCES
Alekh Agarwal, Nan Jiang, Sham M Kakade, and Wen Sun. Reinforcement learning: Theory and algorithms. CS Dept., UW Seattle, Seattle, WA, USA, Tech. Rep, pp. 10-4, 2019.
Kishan Panaganti Badrinath and Dilcep Kalathil. Robust reinforcement learning using least squares policy iteration with provable performance guarantees. In International Conference Machine Learning, 2021.
Peter Bartlett. Theoretical statistics. lecture 12, 2013.
Qi Cai, Zhuoran Yang. Chi Jin, and Zhaoran Wang. Provably efficient exploration in policy opti- mization. In International Conference on Machine Learning, 2020.
Liyu Chen, Haipeng Luo, and Chen- Wei. Minimax regret for stochastic shortest path with adversarial costs and known transition. In Conference on Learning Theory, 2021a.
Yifang Chen, Simon Du, and Kevin Jamieson. Improved corruption robust algorithms for episodic reinforcement learning. International Conference on Muchine Leurning, 2021b.
Karl Cobbe, Oleg Klimov, Chris Hesse, Taehoon Kim, and John Schulman. Quantifying generaliza- tion in reinforcement learning. International Conference on Machine Learning, 2019.
Christoph Dann, Tor Lattimore, and Emma Brunskill. Unifying PAC and regret: Uniform PAC
bounds for episodic reinforcement learning. Advances in Neural Information Processing Systems, 2017.
Omar Darwiche Domingues, Yannis Flet-Berliac, Edouard Leurent, Pierre Ménard, Xuedong Shang, and Michal Valko. rlberry A Reinforcement Learning Library for Research and Education, 10 2021. URL/attps: htt.tbttbbbu...///. com www.rrleeerrryrrr ryberbr
Eyal Even-Dar, Sham M Kakade, and Yishay Mansour. Experts Markov decision process. Advances in Neural Information Processing Systems, 2004.
Jesse Farebrother, Marlos C Machado, and Michael Bowling. Generalization and regularization in DQN. arXiv preprint arXiv:1810.00122 2018.
Chin Pang Ho, Marek Petrik, and Wolfram Wiesemann. Partial policy iteration for 11-robust markov decision processes. Journal of Machine Learning Research, 22:275, 2021.
Garud N Iyengar. Robust dynamic programming. Mathematics of Operations Research, 30(2): 257-280, 2005.
Chi Jin. Tiancheng Jin, Haipeng Luo, Suvrit Sra, and Tiancheng Yu. Learning adversarial Markov decision processes with bandit feedback and unknown transition. In International Conference on Machine Learning. 2020.
Tiancheng Jin and Haipeng Luo. Simultaneously learning stochastic and adversarial episodic MDPs with known transition. Advances in Neural Information Processing Systems, 2020.
Nathan Kallus, Xiaojie Mao, Kaiwen Wang, and Zhengyuan Zhou. Doubly robust distributionally robust pollco evaluation and learning. International Conference on Machine Learning. 2022.
Zijian Liu, Qinxun Bai, Jose Blanchet, Perry Dong, Wei Xu, Zhengqing Zhou, and Zhengyuan Zhou. Distributionally robust q-learning. In International Conference on Machine Learning, pp- 13623-13643. PMLR, 2022.
Thodoris Lykouris, Max Simchowitz, Alex Slivkins, and Wen Sun. Commuttion-robust exploration in episodic reinforcement learning. In Conference on Learning Theory, 2021.
Xiaoteng Ma, Zhipeng Liang, Li Xia, Jiheng Zhang, Jose Blanchet. Mingwen Liu, Qianchuan Zhao, and Zhengyuan Zhou. Distributionally robust offline reinforcement learning with linear function approximation. arXiv preprint 2xXix:20090066200 2022.
10

---

Under review as a conference paper at ICLR 2023
Shie Mannor, Ofir Mebel, and Huan Xu. Lightning does not strike twice: robust MDPs with coupled uncertainty. In International Conference on Machine Learning, 2012.
Gergely Neu, Andras Antos, András György, and Csaba Szepesvári. Online Markov decision pro-
cesses under bandit feedback. Advances in Neural Information Processing Systems, 2010.
Arnab Nilim and Laurent El Ghaoui. Robust control of Markov decision processes with uncertain transition matrices. Operations Research, 5315)770--798, 2005.
Charles Packer, Katelyn Gao, Jemej Kos, Philipp Krähenbühl, Vladlen Koltun, and Dawn Song. Assessing generalization deep reinforcement learning. arXiv preprint arXiv::810. 12282, 2018.
Kishan Panaganti and Dileep Kalathil. Sample complexity of robust reinforcement learning with a generative model. In International Conference on Artificial Intelligence and Statistics, 2022.
Zhengling Qi and Peng Liao. Robust batch policy learning in Markov decision processes. arXiv preprint arXiv:201 1.04185, 2020.
Roberta Raileanu and Rob Fergus. Decoupling value and policy for generalization in reinforcement learning. International Conference on Machine Learning. 2021.
Aviv Rosenberg and Yishay Mansour. Online convex optimization in adversarial Markov decision processes. In International Conference on Machine Learning, 2019.
Jay K Satia and Roy E Lave Jr. Markovian decision processes with uncertain transition probabilities. Operations Research, 2133):228-740, 1973.
John Schulman, Sergey Levine, Pieter Abbeel, Michael Jordan, and Philipp Moritz. Trust region
policy optimization. In International conference on machine learning, 2015.
John Schulman, Filip Wolski, Prafulla Dhariwal, Alec Radford, and Oleg Klimov. Proximal policy optimization algorithms. arXiv preprint arXiv: 2017.
Lior Shani, Yonathan Efroni, Aviv Rosenberg, and Shie Mannor. Optimistic policy optimization with bandit feedback. In International Conference on Machine Learning, 2020.
Xingyou Song, Yiding Jiang, Stephen Tu, Yilun Du, and Behnam Neyshabur. Observational overfit- ting in reinforcement learning. International Conference on Learning Representations, 2019.
Richard S Sutton and Andrew G Barto. Reinforcement learning: An introduction. MIT press, 2018.
Yue Wang and Shaofeng Zou. Online robust reinforcement learning with model uncertainty. Ad- vances Neural Information Processing Systems, 2021.
Yue Wang and Shaofeng Zou. Policy gradient method for robust reinforcement learning. Interna- tional Conference on Machine Learning, 2022.
Chelsea C White III and Hany K Eldeib. Markov decision processes with imprecise transition probabilities. Operations Research, 42(4):739-749, 1994.
Wolfram Wiesemann, Daniel Kuhn, and Berç Rustem. Robust Markov decision processes. Mathe- matics of Operations Research, 38(1):153-183, 2013.
Tianhao Wu, Yunchang Yang, Han Zhong, Liwei Wang, Simon Du, and Jiantao Jiao. Nearly optimal policy optimization with stable at any time guarantee. In International Conference on Machine Learming, 2022.
Wenhao Yang, Liangyu Zhang, and Zhihua Zhang. Towards theoretical understandings of robust Markov decision processes: Sample complexity and asymptotics. arXiv preprint arXiv:2105.03863, 2021.
Xuezhou Zhang, Yiding Chen, Xiaojin Zhu, and Wen Sun. Corruption-robus offline reinforcement learning. International Conference on Artificial Intelligence and Statistics, 2022.
Zhengqing Zhou, Zhengyuan Zhou, Qinxun Bai, Linhai Qiu, Jose Blanchet, and Peter Glynn. Finite- sample regret bound for distributionally robust offline tabular reinforcement learning. In Interna- fional Conference on Artificial Intelligence and Statistics, 2021.
11


Reviews:
[{"review_id": "RZptspLdVKu", "reviewer": "Reviewer_ZEUJ", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "The paper considers robust MDPs and proposes an online optimization policy where the agent interacts with the nominal environment.", "summary_of_the_review": "1. Most importantly, the contribution of this paper is confusing. While this paper considers an “online” setting without assuming knowledge of the environment, the proposed algorithm requires the size of the ambiguity set as an input. In this spirit, it is not clear to me how the proposed algorithm differs from existing algorithms, such as [i] and [ii].\n\n2. The definition of \"regret\" is less common.", "strength_and_weaknesses": "1. Most importantly, the contribution of this paper is confusing. While this paper considers an “online” setting without assuming knowledge of the environment, the proposed algorithm requires the size of the ambiguity set as an input. In this spirit, it is not clear to me how the proposed algorithm differs from existing algorithms, such as [i] and [ii].\n\n2. Moreover, the paper assumes that the agent interacts with an unknown nominal environment, but the regret is defined to be the difference between policy pi_k and the optimal robust value function, instead of the optimal value function under the nominal environment.\n\n3. The writing of the technical content is confusing. For example, it seems that the authors attempt the compute the support function sigma(V) for the s-rectangular case; however, for s-rectangular robust MDPs, the corresponding Bellman equation is not the same as the (s,a)-rectangular case, and it does not use the support function.\n\nMore comments/questions:\n\nSection 1, 4th paragraph, for (s,a)-rectangular robust MDPs, they have optimal deterministic policies; thus, the argument is not clear.\n\nSection 3, should {P}_{h=1}^H be {P_h}_{h=1}^H?\n\nSection 3, what is P_h = { P_h^o }? Or should it be P_h = P_h^o?\n\nSection 3, before definition 3.2. I don’t think s-rectangularity provides a “stronger robustness guarantee”\n\nSection 3, assuming P_h^o(.|s,a) > 0 appears to be a strong assumption. For example, this assumption does not hold for the classical machine replacement example. Could it be relaxed by perturbing P_h^o? What is the error bound?\n\nSection 3, Learning protocols and regret. What is V_1? Should it be V?\n\nClaim 4.1. This is confusing as this paper assumes that the agent interacts with the nominal environment.\n\nEquation (3). What are the upper and lower bounds when using the bisection method?\n\nEquation (3). Efficiently computing the support function with the L1 ambiguity set is not new. See [i].\n\nEquation (4). To the best of my knowledge, for the s-rectangular case, the support function is not used in the Bellman equation.\n\nEquation (4). Why it could be solved in O(A)?\n\n[i] Marek Petrik, and Dharmashankar Subramanian, RAAM: The Benefits of Robustness in Approximating Aggregated MDPs in Reinforcement Learning, 2014.\n[ii] Yue Wang, and Shaofeng Zou, Policy Gradient Method For Robust Reinforcement Learning, 2022.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "N3xhXLwBcnS", "reviewer": "Reviewer_JsyR", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "In Strength And Weaknesses", "summary_of_the_review": "In Strength And Weaknesses", "strength_and_weaknesses": "This paper extends robust MDP with a generative model/ offline dataset to the online setting by optimizing policies. This is the first online algorithm in robust MDPs. Though the extension is mainly based on prior works for non-robust MDPs, which means this paper's novelty is limited, I think this work is fundamental. I didn't go through all the details and appendix in this paper due to my heavy review load. Though I want to give the score 4, it is not in the choice. The authors should know I can't be more positive at the current stage by giving score 5. I will leave the decision to AC.\n\nBelow I list some questions and comments that I hope the authors could answer.\n\n1. As we know, in $L_1$ uncertainty set, the size $\\rho$ has an upper bound $2$. Thus, the result in Theorem 1 has nothing to do with $\\rho$. Then, what's the role of robustness? By [1], we know that when $\\rho$ is not small, the sample complexity could be reduced. But I can't see such similar results from this paper.\n2. About Eqn (4), why it is different from the expression in [1] (Lemma B.6), which means Eqn (4) is independent with policy $\\pi$?\n3. I would encourage the authors to pay more attention to their proof sketch. For example, they could illustrate how they do error decomposition and how to control each error term. The current description in Sec 5 is more like a redundancy.\n4. A missing related work. I believe the authors should discuss with it.[2]\n\n\n[1] Yang W, Zhang L, Zhang Z. Towards theoretical understandings of robust markov decision processes: Sample complexity and asymptotics[J]. arXiv preprint arXiv:2105.03863, 2021.\n\n[2] Liu Z, Bai Q, Blanchet J, et al. Distributionally Robust $ Q $-Learning[C]//International Conference on Machine Learning. PMLR, 2022: 13623-13643.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "Not applicable"}, "extra_text": {}}, {"review_id": "MJLVR3XGKae", "reviewer": "Reviewer_QpYY", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper is the first provable policy optimization algorithm for robust MDP in online RL with a $\\ell_1$ uncertainty set, along with a finite-sample complexity bound. The main contribution is that compared to the previous sample complexity of robust MDP, under an online RL setting, it gives the first provable optimization algorithm with a non-asymptotic regret bound and sub-linear sample complexity. The sample complexity also recovers a non-robust policy optimization result of a prior work when the uncertainty set $\\rho \\rightarrow 0$. Experiments are conducted to show the results.", "summary_of_the_review": "I recommend borderline acceptance since this is the first provable policy-based robust algorithm with finite-sample complexity. However, as the technical tools are not well-introduced, it is hard to see whether this is a combination of the tools in non-robust online RL and robust RL or far beyond. The results are somewhat significant and the technical tools may be novel but it is hard to see owing to no discussions.", "strength_and_weaknesses": "Strength:\n1. This is a very interesting topic whether some algorithms can achieve $O(\\sqrt{K}$ regret in an online robust RL case with an uncertainty set. The results are of a somewhat significant novelty since this work gives the first provable policy optimization algorithm with a non-asymptotic regret bound and sub-linear sample complexity.  \n2. I didn't check the proof in the appendix, but the writing and presentation are almost clear and easy to follow.\n\nWeaknesses:\n1. This work claim that the algorithm is designed by adaptation to the robust case from the non-robust algorithm in [2]. However, [2] seems not the best non-robust policy-based algorithm for online RL in the literature with regret bound $O(\\sqrt{S^2AH^4K})$. Since the optimal policy-based algorithm is [1] with bound $O( \\sqrt{SAH^3K}+ \\sqrt{AH^4K} )$ is better than [2], it seems to apply a robust version of the algorithm in [1] will lead to a better policy and better results. It is not clear why this is not considered.\n2. The sample complexity of prior works in Table 1 seems wrong if I didn't miss something. In $(s,a)$-rectangular case, if the claimed sample complexity means the required number of episodes, the results of [D] is $O(\\frac{H^4S^2A(2+\\rho)^2}{\\rho^2 \\epsilon^2})$, and also the $s$-rectangular case.\n2. The difficulty of addressing additional challenges due to the combination of robustness requirements and the online setting is not introduced in detail. Even if there is a section describing Challenges in Optimistic Robust Policy Evaluation, it will be better to have more discussions. Or it will seem like a combination of the techniques in non-robust online RL and robust RL.\n3. In the experiments, the parameters of the perturbed transition dynamic are not given in detail. So it is a little bit hard to rerun the experiments or check the results.\n\nSome extra questions or minors:\n1. Why the sample complexity does not depends on the uncertainty level with uncertainty level $\\ell_1$? That means the sample complexity does not depend on it? If so, how to compare the results with [Yang et al. 2021] with the $\\rho$ in the denominator of the sample complexity.\n2. The first equation on Page 5 may have typos if I didn't miss something. should $s_0$ be $s_0^k$?\n\n[1] Wu, Tianhao, et al. \"Nearly optimal policy optimization with stable at any time guarantee.\" International Conference on Machine Learning. PMLR, 2022.\n[2] Shani, Lior, et al. \"Optimistic policy optimization with bandit feedback.\" International Conference on Machine Learning. PMLR, 2020.\n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "8k6RfwKb_6", "reviewer": "Reviewer_yGXw", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "This paper studies the online robust MDP and proposes a policy optimization algorithm called Robust Optimistic Policy Optimization (ROPO) for achieving sublinear regrets. This paper starts by showing a sub-optimality result of non-robust optimal policies, which motivates the study of ROPO. The authors then provide two kinds of regret bounds of ROPO under different assumptions of the underlying uncertainty set of transition kernels. The result appears to be the first regret bound for policy-based methods in the online robust RL setting. Finally, this paper presents experimental results in simple RL environments to corroborate the performance.", "summary_of_the_review": "This paper takes the first step towards establishing the theoretical regret bounds for the online robust MDP. The contribution is significant as the technique introduced in this paper is valuable for sparking further results on online robust RL. My current rating is 6 mainly due to the concerns mentioned above. The score would be reconsidered if these issues can be addressed during the rebuttal.", "strength_and_weaknesses": "**Strength**\n\n- A solid paper supported by theoretical regret analysis. \n- This is the first work that provides an algorithm with theoretical regret bounds under robust MDP in the online setting.\n- Proposition 4.1 that shows the sub-optimality of the policy learned from the nominal transition model is interesting and provides a good motivation for ROPO.\n- The paper is well-written and easy to follow.\n\n**Weaknesses**\n- There are some issues regarding the main technical analysis: \n    - The statement “previous sample complexity results cannot directly imply a sublinear regret” does not make much sense to me as it seems feasible to convert the sample complexity results in Table 1 to regret bounds. Why cannot the regret bound of [A] in Table 1 be converted from the sample complexity result?\n    - In the proof of Lemma 4, “L(\\tilde{\\eta}, \\lambda)(s, a) is inversely proportional to \\lambda” is not true since \\tilde{\\eta} also depends on \\lambda. As a result, the optimal \\lambda derived in P.16 appears incorrect, and this could affect the subsequent analysis.\nShould Eq.3 be a “constrained” optimization problem? Specifically, in the proof of Lemma 4, it is required that $\\tilde{\\eta} - min_s \\hat{V}(s) \\leq \\lambda$. And the issue also arises in Eq.4. It is not immediately clear whether this would affect the analysis.\n    - In the second paragraph of P.3, the description about Badrinath & Kalathil (2021) is incorrect. It appears that the theoretical result of this work only provides asymptotic guarantees instead of a convergence rate.\n- The experiment results only show the performance of ROPO under the (s, a)-rectangular sets, lacking the result under the s-rectangular uncertainty sets.\n\nAdditional comments:\n\n1. Does the policy improvement step in Algorithm 1 require $-$?\n2. In the proof of Theorem 1, “ By Lemma 2 and Lemma 4,” => “ By Lemma 2 and Lemma 3,”\n3. The simplex set of the uncertainty set shall be $\\Delta_{S*A*H}$?\n4. What does it mean to have \"a fixed step of time-dependent uncertainty kernels\" mentioned at the beginning of Section 3?\n5. The definition of $\\Delta_S$ in Section 3 is not provided. \n6. The statement “This characterization is then more general, and its solution gives a stronger robustness guarantee.” on top of Definition 3.2 does not make much sense.\n7. Is it still NP-hard to solve the robust MDP under the two assumptions of the transition kernel?\n8. There seems to be a typo that the estimator of the transition is conditioned on $s’$.\n9. $\\hat{V}$ is not defined.\n10. The value function used in Eq.4 should be the estimator of value function \\hat{V}?\n11. The statement above the “Policy Improvement Step\" is weird. \\rho and $\\hat{P}$ seem to be in different terms.\n12. For the step of policy improvement, should “argmin” be “argmax”?\n13. How to define the gradient of \\hat{V}^{\\pi_k}? \n\n", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject