Double Pessimism is Provably Efficient for Distributionally Robust Offline Reinforcement Learning: Generic Algorithm and Robust Partial Coverage

Summary

This paper proposed a unified framework of Robust Markov Decision Process, which includes many newly proposed models as special cases. Under their generic framework, they proposed Doubly Pessimistic Model-based Policy Optimization (P^2MPO) that adopts a double pessimism principle for policy optimization. They showed that the suboptimality gap of the proposed algorithm can be upper bounded by the model estimation error and the robust partial coverage coefficient. They further provided concrete implementations of their algorithm on some specific models and showed that their algorithm enjoys a $n^{-1/2}$ convergence rate with $n$ being the number of trajectories in the offline dataset.

Strengths

- They proposed a generic framework that covers many models such as $\mathcal{S}\times\mathcal{A}$-rectangular tabular RMDPs, $\mathcal{S}\times\mathcal{A}$-rectangular kernel RMDPs, $\mathcal{S}\times\mathcal{A}$-rectangular neural RMDPs, $\mathcal{S}\times\mathcal{A}$-rectangular factored RMDPs. - Instead of covering the visitation distribution of any policy, they only require a partial coverage style assumption, i.e., the dataset covers the visitation distribution of the optimal policy in a robust fashion.

Weaknesses

- Computationally inefficient, i.e., not sure how to solve (4.1), (4.2) and (3.2) efficiently. - Though the authors showed how the model estimation step is implemented on some specific models, it is not clear how to implement the model estimation step that satisfies Condition 3.1 and Condition 3.2 in general.

Questions

- Why the robust partial coverage assumption (which considers all the possible transition kernels in a robust set) is much weaker than assuming the dataset covers the visitation distribution of any possible policy (under only the true transition kernel)? In other words, does the full-coverage-style assumption implies the partial-coverage-style assumption? - How does the rates obtained in Section 4 Corollary 4.1, 4.3 compare with the previous works?

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

3: You are fairly confident in your assessment. It is possible that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work. Math/other details were not carefully checked.

Soundness

3 good

Presentation

3 good

Contribution

3 good

Limitations

See weaknesses

Summary

This study focuses on distributionally robust offline reinforcement learning to discover an optimal robust policy using an offline dataset for effective performance in perturbed environments. A novel algorithm framework called Doubly Pessimistic Model-based Policy Optimization (P2MPO) is proposed. P2MPO combines a flexible model estimation subroutine with a doubly pessimistic policy optimization step, leveraging the double pessimism principle to address challenges arising from behavior-policy mismatch and model perturbations. The study demonstrates the sample efficiency of P2MPO with robust partial coverage data and highlights its convergence rate. It introduces the concept of double pessimism as a general learning principle for robust offline RL, showcasing its efficiency in kernel and neural function approximators.

Strengths

I think this work really pushes the robust RL community research efforts further by answering: > can we design a generic algorithm for robust offline RL in the context of function approximation? The main contribution of double pessimism: one for robustness of dynamics uncertainty and one for model-estimation using offline data is a really nice idea worthy for publication at NeurIPS.

Weaknesses

I have only minor weaknesses for this work as follows: 1. The robust Bellman equation for d-rectangular sets are not formally proven. The proof isn't there even in [Ma et al. 22] to the extent of my search. The current Appendix C just rewrites [Iyengar 05] proof. Maybe replace it by the proof for d-rectangular robust Bellman equation? 2. The robust partial concentrability dependence on the robust set $\Phi$: Is it tight? Is there a lower bound for this setting? The reason for this question is coming from the fact that the robust solution is looking for $\min$ over the robust set $\Phi$. 3. Honestly, Section B.2 can be expanded further. I found the following statement vague in its current form: > our algorithm framework is unable to deal with this kind of rectangular robust sets in the context of partial coverage data due to some technical problems in applying the partial coverage coefficient (Assumption 3.3) under this kind of robust sets.

Questions

please see weaknesses

Rating

7: Accept: Technically solid paper, with high impact on at least one sub-area, or moderate-to-high impact on more than one areas, with good-to-excellent evaluation, resources, reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

3 good

Limitations

Regarding S-rectangular sets, please see weaknesses

Summary

This paper studies distributionally robust offline reinforcement learning. They propose a general learning principle, double pessimism, as well as a generic algorithm framework P$^2$MPO for robust offline RL, and show that it is provably efficient in the context of general function approximation.

Strengths

The paper is well-written and theoretically solid. It provides several novel contributions to the field of distributionally robust MDP. First, it proposes a general learning principle, double pessimism, together with a generic algorithm framework P$^2$MPO and a unified theoretical analysis. Second, it proposes several novel structures of uncertainty set and discusses their qualities under three commonly used rectangularity assumptions. Under these structures, they solve the open problem of learning robust offline RL in the context of general function approximation.

Weaknesses

Some minor issue of typos.

Questions

1. On line 100, is the policy a function from $\mathcal{S}$ to $\Delta(A)$? 2. How strong are assumption D.1 and E.1, are they reasonable? 3. Check inequality (E.23) '$0\leq \lambda_iH$'.

Rating

8: Strong Accept: Technically strong paper, with novel ideas, excellent impact on at least one area, or high-to-excellent impact on multiple areas, with excellent evaluation, resources, and reproducibility, and no unaddressed ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

4 excellent

Presentation

4 excellent

Contribution

3 good

Limitations

Yes.

Summary

This paper proposed a generic framework to study distributionally robust offline reinforcement learning problems, which included a model estimation step and a robust policy optimization step. Previous works in the literature usually assume finite state action spaces; this framework can incorporate function approximations and ultimately paved the way of tackling large state action spaces. Additionally, two specific model estimation approaches are introduced and studied in details; corresponding sample complexity results are provided.

Strengths

This paper explicitly considered the two sources of uncertainties in distirbutionally robust RL problems. The first one is the difference between the estimated training model using finite samples and the true training model; the second one is the difference between the true training model and the testing model. Current literature usually assume that the testing model is within a radius of the estimated training model. The double pessimistic idea is new. Additionally, only partial coverage offline dataset is required, while many previous works require observing all state action pairs in the dataset. This paper also provided an interesting sub-optimality theorem that decomposes the sub-optimality gap into a model estimation error part and a data coverage part, which could be used for future developments. The problem setting, definitions and notations are clear and easy to understand.

Weaknesses

The paper is somewhat hard to follow. A lot of examples that can be studied under the proposed framework are presented in the main paper. I think it is better to present one example in details in the main paper, move the others to the appendix and put relevant literature review in the main paper. Similarly, in the model estimation parts, one example should be enough. The motivation of considering the double pessimism is not clear to me. Two uncertainty sets are introduced, the model uncertainty set, for example, is controlled by $\epsilon$ when using MLE estimator and the distribution shift robust uncertainty set is controlled by $\rho$. It is not clear to me whether the two phase uncertainty sets are necessary as in general we don't know $\rho$. In practice, people may use similar datasets that include both training and testing sets to estimate (guess) the uncertainty set radius, which is a single phase approach and directly captures the difference between the finite training set and the testing set. More rationales or examples should be provided to motivate the two-step approach. For example, 1) the authors could provide applications that singles-step uncertainty set cannot be easily estimated while the two-step approach is more applicable in practice, 2) the author could theoretically show that this two-step approach can avoid conservativeness under certain conditions.

Questions

1. The underscore $\lambda$ and $C_1$ in the Corollary 4.1 is not defined in the main paper. They are well-defined in the appendix; I think it is better to at least provided the meaning of underscore $\lambda$ here. In addition, is it possible to avoid the assumption of the lower bound on the dual variable $\lambda$? As you consider the two-step uncertainty set, I think you could provide sub-optimality gap in terms of $\epsilon$ and $\rho$ in Section 4 and discuss the choices of them as well. 2. Some distributionally robust RL papers that adopt KL-divengence as the uncertainty set measure have radius square in the SubOpt term, e.g., [37] [64] in the papers you cited, while your SubOpt does not suffer from the radius square term. Can you comment on this? I think this could be a big benefit when selecting small $\rho$s.

Rating

6: Weak Accept: Technically solid, moderate-to-high impact paper, with no major concerns with respect to evaluation, resources, reproducibility, ethical considerations.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

2 fair

Contribution

2 fair

Limitations

This is a theoretical work at this stage and thus no potential negative societal impact of their work.

Summary

This paper studies the offline robust RL problem. A double pessimism approach is proposed and studied.

Strengths

1. The approach is novel and new compared to previous offline robust RL ones. 2. The approach can be used for large-scale problems. 3. The theoretical analysis is comprehensive.

Weaknesses

1. The model the authors proposed, seems hard to solve. With no robustness consider, the model reduces to the one in [Masatoshi Uehara and Wen Sun, 2022]. The model in the non-robust is hard to solve and becomes hard together with robustness. 2. Compared to [Masatoshi Uehara and Wen Sun, 2022], the contribution seems a little bit incremental to me. The results and approaches are not surprising, in aspects of approach designing and error bound analysis.

Questions

1. Do you have some efficient approach to solve the model you proposed? 2. The analysis seems similar to the ones in [Masatoshi Uehara and Wen Sun, 2022], can you highlight the novelty and contribution?

Rating

4: Borderline reject: Technically solid paper where reasons to reject, e.g., limited evaluation, outweigh reasons to accept, e.g., good evaluation. Please use sparingly.

Confidence

4: You are confident in your assessment, but not absolutely certain. It is unlikely, but not impossible, that you did not understand some parts of the submission or that you are unfamiliar with some pieces of related work.

Soundness

3 good

Presentation

3 good

Contribution

2 fair

Limitations

See parts above.

Thanks for the rebuttal

I have read the rebuttal and all the other reviews. I think the paper has novel contributions (i.e., double pessimism, P^2MPO) but my concern is still the computational issue. Thus I will keep my score.