Policy Gradient for Rectangular Robust Markov Decision Processes

Summary

The paper investigates policy gradient methods in the context of unknown transition kernels in Markov Decision Processes (MDPs). The authors focus on a robust approach, where the uncertain transition kernel is assumed to lie within a specific uncertainty set, known as a rectangular uncertainty set. The authors address the computation of robust policy gradients in this setting, aiming to achieve the same time complexity as in the non-robust case.

Strengths

The combination of policy gradients with robust MDPs is an interesting and practical approach with promising initial results. The paper is well-written and accessible, making it relatively easy to understand.

Weaknesses

There are a couple of issues regarding the modelling of the uncertainty set: 1) In Section 3.2.1 it is written that the radius $\beta$ of the uncertainty set should be “small enough” such that transition kernels of the form $P_0 + \mathcal{P}$ are well defined. This, however, requires the nominal transitions kernel $P_0$ to be strictly positive everywhere. Moreover, small positive values of $P_0$ are also not enough. Therefore, this modelling seems highly restrictive - particularly for high-dimensional settings. 2) The motivation for using rectangular ambiguity sets is not clear. In practice, ambiguity sets are often non-rectangular and derived from principles like maximum likelihood estimation. Could the method handle more general uncertainty sets?

Questions

1) See the two questions raised as weaknesses? 2) Uncertainty sets are often chosen with the goal to achieve some statistical properties of the learned solution (here policy gradient). Is there a statistical motivation for choosing the specific uncertainty set you choose? Or in other words, why not choosing another uncertainty set than the one you chose? 3) In Section 3.1, what is the relation between $k$ and $\mu$? 4) How do you choose the radius $\beta$? 5) What is the motivation/justification for $\mathcal{U}$ being convex? 6) Line 106 has a typo. Should be $(P,R)$

Rating

5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited 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

4 excellent

Contribution

3 good

Limitations

1) Uncertainty set modelling is a) not well motivated and b) it seems rather restrictive. Please see the questions and points raised above.

Summary

This paper proposes the robust policy gradient (RPG) algorithm as an efficient approach to solve rectangular RMDPs. The results are based on an explicit characterization of $\ell_p$-ball-constrained RMDPs, where the worst-case kernel can be viewed as a rank-one perturbation of the nominal kernel and the worst-case occupation frequency can also be written in closed form, so that the well-known policy gradient theorem can still be applied to calculate the sub-gradient for the RMDP. It is further pointed out in the appendix that these results are all closely related to a fundamental characterization of a constrained inner product minimization problem. The paper also redefines the robust value functions using the worst-case kernel, and shows its equivalence with the common definition in literature, so that it comes up with a more efficient way to calculate the value function of RMDPs, which constitutes as the last piece for evaluating the sub-gradient. Numerical simulations are presented to show the efficiency of the proposed algorithm.

Strengths

1. The flow of this paper is very good. It provides the reader with enough background information to understand the framework, and the final algorithm naturally builds upon the building blocks established in the first few sections so that the readers can easily acquire the intuition. 2. The paper consists of a thorough literature review that justifies the place of this result in the spectrum of related works. The reviewer particularly appreciates the table presented in Section 2 that compares the contributions a full range of related works. 3. The contribution of this work is significant as viewed by the reviewer, in that it is among the first to apply policy gradient methods to solve RMDPs. The algorithm is presented with theoretical complexity guarantees, and the paper also discusses more efficient LP-based algorithms in the $\ell_1$-constrained special case, which adds to the applicability of the algorithm. 4. The mathematical proofs seem correct to the reviewer in the form they are presented in the paper. (Note: since the proof cites quite a few theorems from e.g. [12], the reviewer took those published results for granted and didn't bother to check them.)

Weaknesses

1. The numerical experiments seem relatively crude and incomplete, and the results are not convincing as viewed by the reviewer. The authors do not release the code for the simulations, and nor do they describe the settings in detail so that the results can be replicated. The presentation of results only focuses on running time but says nothing about the policy found by the algorithm, nor are they compared to any SOTA baselines. Experiments seem to be repeated with different random seeds, yet the deviation is only roughly reported in the appendix. Finally, figures cannot be found anywhere! The reviewer will be more positive if the results are more concrete, visualized, and reproducible. 2. This paper cites a lot of results from previous work like [12]. Readers unfamiliar with it (like me) may sometimes find it very uneasy to handle these cited results which basically scatter across the whole paper. It is advisable to have an independent preliminaries section that explains what is done in [12] and why we need them here.

Questions

1. The reviewer urges the authors to design better experiments to show both the running time and the performance of the proposed RPG algorithm against a few other baseline algorithms. Results should ideally be presented in the form of figures. 2. In the introduction, [14] seems to be closely relevant to this paper, yet it is not discussed in details in the related works section, and nor does it appear in the table. How does this work compare with [14]? And how about the efficiency of the algorithm proposed in [14]?

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

3 good

Contribution

3 good

Limitations

The paper discusses about its limitations and future work in a satisfactory way.

Summary

The paper presents a policy gradient method for solving rectangular-robust MDPs. They propose closed forms for the worst-case reward and transition models. They also present robust Q-value forms that can be efficiently updated by a proper Bellman operator. Furthermore, they show an expression for the robust policy gradient that matches the non-robust PG complexity, and is therefore very fast.

Strengths

The paper targets a specific problem, and is very well-written. I applaud the authors for their valuable work, and enjoyed reading through the paper without any significant issues. The notation used for the theory is standard and appropriately compact, and the theory itself is clear and insightful. The computational efficiency obtained by the proposed method is both supported by theory, and also shown to be significant-enough in practice. This proves, once again, that a well-tailored algorithm can produce significant speed-ups over generic solvers (e.g., linear programming or convex optimizers).

Weaknesses

While this is a minor point, I think the authors could slightly increase external references and elaborate more to help (an otherwise unfamiliar) reader follow through the content. For instance, (1) in Line 100, it would only take the authors a few words to reference this inequality as the Holder inequality, (2) provide a second common name for terms (such as the credal set for the probability simplex, or the visitation frequency for the occupation measure), (3) briefly derive simple results with the proposed notation (e.g., the gamma-contraction property in Line 118). These are only a few examples, and will mostly help the reader warm-up and get comfortable with the derivations before jumping into the core part of the paper. Also, while I understand that this is out of the scope of the paper, but due to its importance I should mention it. The authors could possibly comment deeper about the resiliency of their proposed approach to stochastic approximation. While there is some limited discussion in the paper (e.g., Lines 218) about this point, I would like this point to be discussed in more length. If in future, this method is adapted to a more realistic or model-free setting, it would be valuable to have the authors comment on the statistical aspects of this approach.

Questions

I would like the authors to address the points I raised in the Weaknesses section, even though they don't point to any fundamental short-comings in the paper.

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

4 excellent

Presentation

4 excellent

Contribution

4 excellent

Limitations

The paper portrays a fair description of its limitations. This includes, but isn't limited to, (1) the second paragraph of discussion (Lines 304-311), (2) Lines 262-267, and (3) Lines 218-222.

Summary

This paper develops policy gradients for robust MDPs, and proves several interesting properties of the worst-case kernel and occupancy measure along the way. The paper also shows that the robust Bellman operator is just the vanilla Bellman operator, with regularization of the vector's generalized variance function. The key result is a robust gradient expression that only depends on nominal samples.

Strengths

1. Except the large amount of newly introduced notation, this paper seems polished and well written. 2. Good discussion on time complexity, which is often absent from many prior works but crucially important for robust MDPs. 3. The proposed method only requires samples from the nominal data distribution, and appears more computationally efficient than prior convex optimization approaches.

Weaknesses

1. Notation is a bit hard to follow and is defined all over the place throughout section 3. It would be helpful to have a centralized place where all notation is defined. 2. There is no "convergence to local/global optima" result. 3. The experimental results only show running time, but does not evaluate the robust MDP performance of the learned policies. Do all methods end up learning the same robust optimal policies?

Questions

1. Why is there a p-norm on a scalar in def. of R_{(s,a)}? 2. In Sec 3.2.1., what if the perturbation has a negative entry, which could possibly make P_0 + P have negative entries as well? This is not so unrealistic if P_0 has small entries somewhere. 3. Can this result generalize to convex uncertainty sets, or does it crucially rely on the uncertainty set being a lp ball? 4. Looking at Table 1, is the main benefit of this work a better time complexity, rather than the ability to learn better policies? Convex optimization approaches that guarantee global optimum seem to only be worse in terms of time complexity.

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

Please see questions/weaknesses.

Summary

This present studied robust policy gradient to solve rectangular robust Markov decision process, where the authors provide a closed-form expression for the worst case of reward model and transition kernel. The provided explicit form of the robust policy gradient can be estimated from data with the same time complexity as its non-robust equivalent.

Strengths

- Instead of previously performing max-min optimization approaches, this paper presents a closed-form expression for the worst case kernel and reward estimation; thus we can achieve similar time complexity. - Empirical experiments demonstrate that the new proposed method can achieve similar complexity as non-robust settings, make the algorithm more practical than previous ones. - The main part of the paper is easy to follow and understand the main idea.

Weaknesses

- The techniques mainly replies on the properties of the normed-ball structure of the uncertainty set, I am not sure how practical it is in realistic settings such as continuous policy optimization? - it is still unclear for real-world scenarios, how the method or the idea can be leveraged to derive a computational efficient and practical algorithm. To me, it seems that to get the optimal reward and kernel, it is quite difficult to estimate from empirical samples (continuous case).

Questions

- Can authors give me a concrete example or explanation of the difference of the risk-averse approach and robust RL? the uncertainty set you mentioned?

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

4 excellent

Contribution

3 good

Limitations

NA

Thanks for the responses!

I appreciate the efforts made by the authors to settle my concerns. The experiment part definitely looks better now, and the supplementary materials are also useful. Based on these improvements, I will raise my score to 7.

After reading the rebuttal

I would like to thank the authors to answer my questions. Regarding the first question raised, I don't understand why you would want to consider uncertainty sets that contain "absurd" MDP models - this should lead to unnecessary conservatism. Related is the discussion about the choice of the radius - which also remains open (at least from the theoretical side). I do understand, however, that this questions may be beyond the scope of this work.

Thank you for your response

I thank the authors for their response, and will maintain my initial score as the authors addressed all my concerns.

Response

I would like to thank the authors for answering my questions. I will keep my score and vote for acceptance.