Venue: ICLR 2023 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: **Strength**

- A solid paper supported by theoretical regret analysis. 
- This is the first work that provides an algorithm with theoretical regret bounds under robust MDP in the online setting.
- 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.
- The paper is well-written and easy to follow.

**Weaknesses**
- There are some issues regarding the main technical analysis: 
    - 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?
    - 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.
Should 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.
    - 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.
- The experiment results only show the performance of ROPO under the (s, a)-rectangular sets, lacking the result under the s-rectangular uncertainty sets.

Additional comments:

1. Does the policy improvement step in Algorithm 1 require $-$?
2. In the proof of Theorem 1, “ By Lemma 2 and Lemma 4,” => “ By Lemma 2 and Lemma 3,”
3. The simplex set of the uncertainty set shall be $\Delta_{S*A*H}$?
4. What does it mean to have "a fixed step of time-dependent uncertainty kernels" mentioned at the beginning of Section 3?
5. The definition of $\Delta_S$ in Section 3 is not provided. 
6. 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.
7. Is it still NP-hard to solve the robust MDP under the two assumptions of the transition kernel?
8. There seems to be a typo that the estimator of the transition is conditioned on $s’$.
9. $\hat{V}$ is not defined.
10. The value function used in Eq.4 should be the estimator of value function \hat{V}?
11. The statement above the “Policy Improvement Step" is weird. \rho and $\hat{P}$ seem to be in different terms.
12. For the step of policy improvement, should “argmin” be “argmax”?
13. How to define the gradient of \hat{V}^{\pi_k}? 


clarity,_quality,_novelty_and_reproducibility: This paper is well-written and easy to follow in most places. For reproducibility, the details of the environment are provided. The solid theoretical result is novel and is expected to have good impacts to the RL community.
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.
review_title: null

final_score: rating: 5: marginally below the acceptance threshold
review_content: summary_of_the_paper: 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.

Below I list some questions and comments that I hope the authors could answer.

1. 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.
2. About Eqn (4), why it is different from the expression in [1] (Lemma B.6), which means Eqn (4) is independent with policy $\pi$?
3. 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.
4. A missing related work. I believe the authors should discuss with it.[2]


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

[2] Liu Z, Bai Q, Blanchet J, et al. Distributionally Robust $ Q $-Learning[C]//International Conference on Machine Learning. PMLR, 2022: 13623-13643.
clarity,_quality,_novelty_and_reproducibility: In Strength And Weaknesses
summary_of_the_review: In Strength And Weaknesses
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: 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.
strength_and_weaknesses: Strength:
1. 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.  
2. I didn't check the proof in the appendix, but the writing and presentation are almost clear and easy to follow.

Weaknesses:
1. 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.
2. 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.
2. 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.
3. 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.

Some extra questions or minors:
1. 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.
2. The first equation on Page 5 may have typos if I didn't miss something. should $s_0$ be $s_0^k$?

[1] Wu, Tianhao, et al. "Nearly optimal policy optimization with stable at any time guarantee." International Conference on Machine Learning. PMLR, 2022.
[2] Shani, Lior, et al. "Optimistic policy optimization with bandit feedback." International Conference on Machine Learning. PMLR, 2020.


clarity,_quality,_novelty_and_reproducibility: The clarity and quality is very good.
The reproducibility of the experiments may need some more details such as the parameters of the perturbed transition dynamics.

The novelty of the results is great. The novelty of the technical details is a little bit hard to see. It may be better to give more discussions about the main technical tools used to deal with the challengs.

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.
review_title: null

final_score: rating: 3: reject, not good enough
review_content: summary_of_the_paper: The paper considers robust MDPs and proposes an online optimization policy where the agent interacts with the nominal environment.
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].

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

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

More comments/questions:

Section 1, 4th paragraph, for (s,a)-rectangular robust MDPs, they have optimal deterministic policies; thus, the argument is not clear.

Section 3, should {P}_{h=1}^H be {P_h}_{h=1}^H?

Section 3, what is P_h = { P_h^o }? Or should it be P_h = P_h^o?

Section 3, before definition 3.2. I don’t think s-rectangularity provides a “stronger robustness guarantee”

Section 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?

Section 3, Learning protocols and regret. What is V_1? Should it be V?

Claim 4.1. This is confusing as this paper assumes that the agent interacts with the nominal environment.

Equation (3). What are the upper and lower bounds when using the bisection method?

Equation (3). Efficiently computing the support function with the L1 ambiguity set is not new. See [i].

Equation (4). To the best of my knowledge, for the s-rectangular case, the support function is not used in the Bellman equation.

Equation (4). Why it could be solved in O(A)?

[i] Marek Petrik, and Dharmashankar Subramanian, RAAM: The Benefits of Robustness in Approximating Aggregated MDPs in Reinforcement Learning, 2014.
[ii] Yue Wang, and Shaofeng Zou, Policy Gradient Method For Robust Reinforcement Learning, 2022.
clarity,_quality,_novelty_and_reproducibility: Please see my major and minor comments above.
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].

2. The definition of "regret" is less common.
review_title: null

Meta-review: metareview:_summary,_strengths_and_weaknesses: The submitted paper considers the problem of learning a robust policy for MDPs with uncertainty about the decision dynamics. More specifically, they consider an online setting and are interested in deriving regret bounds for this setting. They derive theoretical results in that regard and relate it to results from the literature. Furthermore, they provide proof-of-concept type experiments illustrating that their proposed algorithm can indeed effectively learn a robust policy in 5x5 grid world environment. The paper clearly addresses an important problem, derives theoretical results that could be promising, and illustrate that their algorithm can perform beneficial to a sensible baseline. Unfortunately, there are several concerns about basic definitions (e.g., uncertainty sets and the corresponding Bellman equations) and the relation into to existing results (whether their results are correctly represented as there were several inconsistencies in the discussion between reviewers and authors).
Overall, the idea of the paper is good, the taken approach probably as well, but the paper needs to be carefully revised to clarify/correct the concerns raised in the reviews. Therefore, at this stage, the paper is not ready for publication but the authors are encouraged to improve their paper based on the reviews and submit a revised and improved version to a future venue.
justification_for_why_not_higher_score: The paper does not yet meet the bar for publication. In particular, the paper must be revised to clarify the concerns about the theory and relation to existing work.
justification_for_why_not_lower_score: n/a
Decision: Reject