Venue: NeurIPS 2022 Conference

Reviews:

final_score: 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.
review_content: summary: This paper studies three instances of the multi-objective RL problem, namely smooth concave scalarization, CMDPs, and max-min trade-off. The authors proposed a new class of algorithms for these problems which updates a regularized objective which constrains the KL between the update policy and some anchor policy and uses natural gradients for policy update. The resulting algorithm achieves $\tilde{O}(1/T)$ global convergence with exact gradients.
strengths_and_weaknesses: I think this is a solid paper which extends the recent series of work on the global convergence of policy gradient methods to several important classes of multi-objective problems. One disclaimer I wish to make is that even though I am familiar with some of the related work, this paper is a little outside my own research area, but despite this I found the paper to be quite clearly written and fairly easy for me to follow. I did not go through all the details of the proofs but the overall structure and logic is quite clear. Multi-objective RL and constrained RL are gaining increasing interest within the community both from a theoretical and practical perspective, I think this paper makes an important contribution to our understanding of the problem and I therefore recommend this paper for acceptance.  Some additional comments and questions below in the section below.

questions: - Mathematically it seems that using natural gradients is key to achieving $\tilde{O}(1/T)$ global convergence but I wonder if you could give a little more intuition on the update rule in Equation (5), specifically if we change the gradient term to be w.r.t. the unregularized objective $V$ instead of the regularized $\tilde{V}$, this would be first-order equivalent to optimizing the KL-regularized objective in Equation (4) (first-order equivalence of TRPO and NPG) so I'm curious what is the intuition with taking the gradient of the regularized objective here?
- Following up on the previous question, what would happen if we were to remove the Fisher information term altogether and do the InnerLoop as a standard policy gradient update w.r.t. the regularized objective.
- Another question I have is related to the sample efficiency of the algorithm from a practical perspective, since both the expected KL and Fisher information matrix are w.r.t. $\pi_{\theta}$ and not the anchor policy $\pi_{\theta_k}$, this means that if we were to use a sample-based version of your proposed algorithm, we would need to collect new samples from $\pi_{\theta}$ every time we perform a policy update in the InnerLoop, wouldn't this be extremely sample inefficient even for relatively small $t_k$?
- (Minor) On line 147, is the tilde on top of the $V$ on the RHS of the equality a typo?
- (Minor) "Lagrange" is mis-spelt as "Langrange" in several places.
limitations: Yes, the authors discussed future extensions to the function approximation case
review_title: null

final_score: 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.
review_content: summary: In this paper, the authors studied policy optimization in multi-objective Markov decision processes. Three specific optimization scenarios are considered: smooth concave scalarization, objective constraints, and max-min tradeoffs. The main technical contribution is an anchor-changing regularized natural policy gradient (ARNPG) framework. Theoretical analyses for the three scenarios are provided under the ARNPG framework. Some empirical experiments corroborate theoretical results.
strengths_and_weaknesses: Originality: This work is quite original. The authors make this connection between mirror ascent and multi-objective policy optimization. Proposition 1, which establishes an analogous inequality to classical first-order methods, is technically novel. 

The theoretical applications of Proposition 1 (Section 4) are natural and instructive. The three optimization scenarios encompass a wide range of decision-making in multi-objective MDPs. In summary, this paper clearly passes the bar for originality. 

Quality: I have only checked the proof of Proposition 1 (Section D in the Appendix) as it is the foundation for the subsequent analyses. The proof is technically sound and contains several interesting techniques. 

Being a mainly theoretical paper, the empirical evaluation part (Section 5) provides some corroborations to the theoretical results but it is weak in terms of baselines. In Section B.1.1 Sommth concave scalarization, there are no baseline methods. Granted the specific scalarization formula (equation 16) limits baseline choices. I wonder if it is possible to apply the more common linear scalarization, which is also smooth concave, and compare with works such as the one by Yang et al. NeurIPS 2019.

Clarity: The paper is overall clear. I have some minor questions in the next section.

Significance: Theoretical analyses of policy optimization in multi-objective MDPs are highly relevant to the NeurIPS community. The novel proof techniques in this paper are likely to be significant for the future development of this topic.

questions: 1. Line 122: equation (3), I believe it should be $v$ instead of $v_k$ in the inner product?

2. Line 639: It would improve the readability of the proof to include some more details on how equation (20) comes about, rather than simply pointing to a reference.

3. I am not entirely clear on what the “exact gradients” mean in Section 5.1. Can the authors provide some clarifications?

limitations: The authors had an adequate discussion on the limitation of the current work.
review_title: null

final_score: 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.
review_content: summary: The authors propose Anchor-changing Regularized Natural Policy Gradient (ARNPG), a novel framework for designing policy-gradient based methods for multi-objective MDPs which builds on first-order methods for convex optimization problems. In contrast to prior work, it allows $\mathcal O(1/T)$ convergence without artificial or impractical assumptions. The authors theoretically analyze their approach and provide empirical evaluations in exact-gradient as well as sampling-based CMDP as well as on Acrobot.
strengths_and_weaknesses: **Originality:** The authors develop a novel framework for the design of policy-gradient methods in multi-objective MDPs and demonstrate its application in several scenarios (proportional fairness, constrained MDP, max-min trade-off). Building on first-order convex optimization methods, they claim that their method achieves $\mathcal O(1/T)$ global convergence w.r.t. optimality gap and constraint violation, which related work does not achieve without further assumptions. They clearly work out their contributions in their Introduction and Related Work section. 

**Quality:** The problem setting as well as the proposed ARNPG approach and its theoretical foundations are presented clearly and in a technically sound manner. The authors thoroughly analyze ARNPG in various different scenarios and make sure to clearly state relevant assumptions for their proofs. Further, they provide experimental evidence for the effectiveness of their approach. However, I am not familiar enough with the topic to judge the soundness of the proofs and experiments themselves.

**Clarity:** The paper is written very clearly. The authors structure their work well and do a good job in guiding the reader through their paper. I cannot judge the presentation and clarity of the derivations and proofs. 

**Significance:** I believe that powerful policy-gradient methods for multi-objective MDPs and, in particular, a thorough and sound theoretical and experimental analysis as presented in the paper is important and therefore I am convinced the submission is interesting for the community. However, I am not familiar enough with the state of the art to fully judge the significance of this work.

In summary, I think this work is an interesting contribution and presented in a clear and well-written manner. Therefore, I recommend acceptance. However, this recommendation is with low confidence, as I am not very familiar with the topic. Therefore, I might adjust my rating after the discussion period.
questions: ---------
limitations: -----------
review_title: null

final_score: rating: 5: Borderline accept: Technically solid paper where reasons to accept outweigh reasons to reject, e.g., limited evaluation. Please use sparingly.
review_content: summary: This paper proposed an Anchor-changing Regularized Natural Policy Gradient (ARNPG) framework, which can systematically incorporate ideas from well-performing first-order methods into the design of policy optimization algorithms for multi-objective MDP problems. Theoretically, the designed algorithms based on the ARNPG framework achieve $O(\frac{1}{T})$ global convergence with exact gradients.  A few experiments demonstrate the effectiveness of the algorithm.
strengths_and_weaknesses: ## Strengths
1. Adequate theoretical proof.
2. Well-established experimental evidence (though simple).
3. The motivation is clear.

## Weaknesses
1. Except for the tabular-based experiment, the effectiveness of ARNPG is verified in only one task (i.e., Acrobot-v1). We still need more practical examples to verify the value of the algorithm in more scenarios. I am concerned that one example alone is not enough to demonstrate the effectiveness of the algorithm.
questions:  There are no obvious problems. I am only concerned about whether it can be applied to more complex tasks, such as robotics control or video game, etc.
limitations: The limitations of the algorithm are rarely discussed in this paper. As far as I'm concerned, the algorithm presented in this paper is only proved to be effective in a very simple human-designed environment, and there are no relevant experiments for more practical standard tasks, such as video games.
review_title: null

Meta-review: metareview: This paper studies multi-objective RL, and in particular the settings of smooth concave scalarization, constraints, and max-min trade-off. The authors propose a framework for these problems called “anchor changing regularized natural policy gradient” (ARNPG) and show $O(1/T)$ convergence with exact gradients. The results do not require some of the assumptions used in related works such as ergodicity. The authors evaluate their approach on tabular environments, Acrobot, and (post-rebuttal) Hopper.
The paper is well-written, the results seem correct, and the work provides a nice extension of the recent results on PG convergence to the multi-objective case. This contribution warrants acceptance despite the somewhat limited empirical evaluation. 

confidence: Certain
Decision: Accept