Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 8: Top 50% of accepted NeurIPS papers, clear accept
review_content: summary: The paper establishes an equivalence between regularized MDPs and robust MDPs. The first main result shows that policy-regularized MDPs are equivalent to reward-robust MDPs, gives examples of equivalences between common regularizers and uncertainty sets, and gives a policy gradient algorithm for reward-robust MDPs. The second main result extends the equivalence to robust MDPs with both reward and transition uncertainty. The third main result introduces R^2 MDPs, which extend regularized MDPs with a value regularizer. It is shown that under certain assumptions on the uncertainty sets, the equivalent R^2 MDP can be solved with MPI.
main_review: ## Originality

I am not familiar with the literature in this area, but the paper claims all 3 main results as original. Related work is covered thoroughly.

## Quality

I don't have the mathematical background to verify the analysis. The statements of the results are precise and seem to include all required assumptions. The work addresses both the narrower case of reward-robust MDPs as well as the case of general robust MDPs, and provides both a construction of the equivalent regularized problems and a solution algorithm.

## Clarity

The paper is clearly-written but is fairly dense. Mathematical notation is precise.

## Significance

Each of the main results seems to be significant on its own. The connection between regularization and robustness seems like it will be fertile for further analyses. The MPI algorithm for R^2 MDPs is significant in that it establishes that R^2 MDPs with appropriate assumptions have the same complexity as ordinary MDPs, making them a tractable subset of robust MDPs.
limitations_and_societal_impact: The paper clearly states the assumptions needed for its analysis, which seem to be the only significant limitations. I see no potential for negative societal impact.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper highlights two limitations of current approaches for Robust RL: 

1. Robust optimization methods are computationally demanding.
2. They do not account for uncertainty in the model dynamics.

The paper proposes to work around these limitations by learning robust MDPs using regularization. Their contributions are the following:

1. Showing that regularized MDPs are an instance of Robust MDPs with uncertain rewards; thus, policy iteration on reward-robust MDPs has the same time complexity as on regularized MDPs 
2. Extend point 1 to MDPs with the uncertain transition.
3. Generalize regularized MDPs to twin regularized MDPs to retrieve robust MDPs.
main_review: Strengths:

1. The paper is well-contained. I am not familiar with Robust RL and even less familiar with work in theoretical RL. Still, I had no difficulty reading the paper and understanding its central claims/contributions.  Kudos to the authors.
2. I think the theoretical contributions are substantial and useful - connecting regularized MDPs to robust MDPs, extending the approach for uncertain dynamics function, etc. Though I should highlight that robustness/theory is not my area of expertise, so I might be over-estimating this contribution.

Questions / suggestions for improvement

1. Line 170 mentions a nominal model. How do we get access to this model? Is it part of the problem formulation, or is it learned using the sampled trajectories? If it is learned, how do we ensure that the nominal model is correct?

2. The paper mentioned that one of the limitations of existing approaches is that they are computationally demanding. I may have missed it, but it seems that the paper did not include any evidence for the twin regularized MDPs to be computationally more efficient.  Line 177 mentions that "policy iteration on reward-robust MDPs has the same convergence rate as regularized MDPs, which in turn is the same as standard MDPs." Still, it would be helpful to include both the convergence rates and error bounds in the main paper (for both the proposed approach and the standard robustness-based approaches) to provide a complete comparison. For example, regularized MDPs are a particular case of robust MDPs. So other robustness methods may have a slower convergence rate but achieve better performance. The paper can be improved by including these tradeoffs explicitly.

3. Missing empirical evidence - I understand that this paper is focusing on theoretical contributions. It may strengthen the paper to include some experimental results as well (even if it is on simplistic grid worlds). 
limitations_and_societal_impact: Limitations And Societal Impact are addressed.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper studies the connection between robust and regularized MDPs. The authors first show that solving robust MDPs with uncertain rewards is equivalent to solving regularized MDPs with a suitable policy-dependent regularization. Then, they extend this result to MDPs with uncertain transitions, obtaining the equivalence with both policy and value regularization. Finally, they propose R^2 MDPs, i.e., MDPs with both value and policy regularization for which, under certain assumptions, they guarantee good properties (eg contraction) for the corresponding Bellman operators and thus convergence of a modified policy iteration scheme. This allows solving robust MDP problems with the same computational cost as regularized ones.
main_review: Significance, novelty, and relevance
---

The paper considers a relevant problem, that of robust RL and, in particular, planning in robust MDPs, where reducing the computational complexity of Bellman updates is an important open area of research. While there have been many works that addressed this topic and the related one of regularized MDPs, to my knowledge, the contributions of this paper are novel. Overall I found this contribution interesting and significant. 
 

Relation with prior work
---

To my knowledge, relevant prior works are discussed.


Clarity of writing
---

I found the paper well-written and easy to read. I think the authors did a good job in discussing and providing intuition for all results.


Detailed comments/questions
---

1. One limitation of this work is that no numerical result is provided. I know this is mostly theoretical work, but, since the final impact is on algorithms for solving robust MDPs (and a new algorithm is even provided), it would be good to see at least some experiments. For instance, it would be good to compare the MPI scheme for learning robust policies of Section 5 with existing robust DP methods (both in terms of convergence speed and computational cost), or to test the policy gradient derived in Section 3, possibly comparing with the existing related techniques mentioned in that section.

2. Theorem 5.1 proves that the optimal policy for R^2 MDPs is unique and, I assume, such a policy could be stochastic due to the regularization term. On the other hand, if I am not mistaken, for robust MDPs an optimal deterministic policy exists under certain conditions. So are there problems where there exists an optimal deterministic robust policy but solving the corresponding R^2 MDP we find only a stochastic one? If this is the case, it could be a potential limitation of using regularized methods, as in practice deterministic policies are desirable and we might not be able to find them using this alternative technique.

3. I appreciated that the authors showed (in Section 3) what are the uncertainty sets corresponding to common regularizers adopted in the literature. However, do the uncertainty sets presented in Section 3.2 make any sense in the robust RL literature? They only depend on the policy for which we are evaluating the regularizer and not on other MDP-related quantities (such as how uncertain we are about the rewards etc.). Some policy-dependent uncertainty sets were studied in [1], but still I do not see any connection with those reported here.

4. This paper considers finite states and actions, while most of the adopted "functional/operator-based" notation can be used also for more general state-action spaces. Do the results presented here easily extend to, say, countably infinite or continuous state-action spaces?

5. Line 132 mentions that regularized MDPs are standard MDPs with a modified reward function. Still, it should be mentioned that, while it is true that we can modify the expected reward r^\pi(s) of any policy \pi by including the regularizer, we cannot do the same for the original reward r(s,a) without making it policy-dependent (e.g., I am thinking about the standard entropy regularizer).

6. R^2 MDPs are introduced only for ball-constrained uncertainty sets, which yields the convenient norm-based regularization terms of Corollary 4.1. What about more general regularizers/uncertainty sets (e.g., KL-based)? Is it possible to obtain similar results?

7. The contraction property in Prop. 5.1 is wrt to 1-\epsilon_\star and not \gamma. So, while there is a computational gain wrt solving a robust MDP using classical techniques, could there be that the convergence rate of Bellman backups in the R^2 regularized MDP is much slower than in a standard regularized/unregularized MDP?


Minor:
- Line 99: is q a typo?
- Line 105: the notation for \Delta with both superscript and subscript was not introduced
- Prop. 3.2: is the subscript R^2 of J a typo? Also, in the main result there it is not clear under what MDP \mu_\pi is computed (though later the text mentions it is wrt the nominal model)

[1] Tirinzoni, Andrea, and Xiangli Chen. "Policy-conditioned uncertainty sets for robust Markov decision processes." Advances in neural information processing systems (2018).
limitations_and_societal_impact: The authors discuss some of the limitations of their work, while there might be others that could be mentioned (see above). I do not see any societal impact.
review_title: null

final_score: rating: 5: Marginally below the acceptance threshold
review_content: summary: This paper formalized robust MDPs as general MDP with regularization. They first show that regularized MDPs are equivalent to MDPs with uncertain rewards. They also derive a regularized MDP formulation for robust MDPs with uncertain transitions. And they finally generalize a regularized MDP that can handle both reward and transition uncertainty. They argue that their regularized MDP framework provides better computational complexity and scalability compared to traditional robust optimization techniques.
main_review: In lines 58-64, many quantities like v, \mathcal{U}, \mu etc. start appearing from no where. They were not defined before. This section needs reorganization making sure that everything is defined before referred or used.

It is possible to solve the reward robust MDP as a linear programming problem. The paper presents a policy gradient algorithm for the same purpose. How do they compare?

The theories presented in the paper look good from a high level. Though a rigorous verification of the correctness was not possible due to time constraint.

It is understandable that the paper is mostly theoretical, but one big weak point is not having any empirical analysis of the methods. How about having an empirical evaluation for robust and proposed regularized methods, possibly with different RL regularizers?

limitations_and_societal_impact: Limitations and impacts are addressed.
review_title: null

Meta-review: All but one reviewer recommend publication.  The one who does not is concerned about the lack of empirical results, but I think this is a topic of interest to the community and its reasonable to have a purely theoretical paper on this.
Decision: Accept (Poster)