Enabling Pareto-Stationarity Exploration in Multi-Objective Reinforcement Learning: A Weighted-Chebyshev Multi-Objective Actor-Critic Approach

Your Comment 1 (Also Weakness 1): The major weakness might lie in the novelty of the proposed method. To the knowledge of the reviewer, Although the theoretical analysis partially answers the challenges mentioned in the introduction, the proposed method seems to largely based on (Désidéri, 2012) and (Momma et al., 2022), with the multi-objective optimization gradients replaced with policy gradients.

Our Response: Thanks for your comments. We agree with the reviewer that the actor component of the proposed MOAC approach is indeed based on the MGDA approach in (Désidéri, 2012) and (Momma et al. (2022)). However, we do want to emphsize that the adaptation of these techniques to the MORL setting is by no means straightforward due to the unique challenges in MORL, which requires additional new algorithmic techniques (e.g., the momentum-based approach to eliminate systematic biases). Moreover, the theoretical finite-time convergence proof and analysis are new, which cannot be found in (Désidéri, 2012) and (Momma et al. (2022)). In particular, the Pareto stationary convergence rate's dependency on the weight vector $\mathbf{p}$ is a new result in the literature. In addition, the empirical studies in Figure 1 does indicate that our proposed WC-MOAC approach in Algorithm 1 is able to explore a much larger Pareto stationarity front footprint than that of the conventional approach based on linear scalarization.

Your Comment 2 (Also Question 1): In Theorem 4, what is the different between |w*-w| and zeta? Intuitively, both these two terms are related to the error of value functions. The reviewer is confused because the definition of w* also needs clarification. The optimality of the critic network depends on both $\phi(s)$ and w. Different state representation phi might correspond to different optimal w. Is $\phi$ function fixed?

Our Response: Thank you for your comment. $\mathbf{w}^{i,*} - \mathbf{w}_t^i$ and $\zeta_{\text{approx}}$ have different physical meansings, which are stated as follows:

1) The meaning of $\zeta_{\text{approx}}$: The quantity $\zeta_{\text{approx}}$ represents the fundamental inability of the linear function approximation apporach for accurately quantifying the $i$-th value function (i.e., $V^{i}(s)\approx\phi(s)^{\top} \mathbf{w}^{i}$). Mathematically, $\zeta_{\text{approx}}=\max_{i\in[M]}V^{i}(\cdot) - \mathbf{w}^{i,\*}\Phi$ characterizes the maximum gap between the ground truth value function $V^{i}$ and best linear approximation given the feature matrix $\Phi$ and the optimal linear approximation solution $\mathbf{w}^{i,*}$ among all $M$ objectives.

2) The meaning of $\mathbf{w}^{i,\*} - \mathbf{w}_t^i$: The quantity $\mathbf{w}^{i,\*} - \mathbf{w}^i_t$ represents the finite-time convergence gap compared to the optimal linear function approximation solution $\mathbf{w}^{i,*}$, which itself has a gap $\zeta_{\text{approx}}$ to the ground truth value function $V^i(\cdot)$ of the $i$-th objective.

For ease of explaination, let's use the discounted reward setting in here as a concrete example. The value function $V^{i}(s)$ for the $i$-th objective at $s\in \mathcal{S}$ follows the canonical definition of the discounted reward setting. However, in some MDPs, due to large state space $\mathcal{S}$, approximation is used to cope with the high dimensionality challenge. In this paper, we applied linear approximation assuming the feature vector mapping $\phi(s)$ is given. How to choose a suitable feature mapping $\phi(\cdot)$ is an interesting problem by itself, but beyond the scope of this paper. This suggests for each objective $i$, the critic will maintain a $\mathbf{w}^{i}$ parameter to evaluate the $i$-th objective. $\mathbf{w}^{i,\*}$ is used to denote the optimal approximation under such linear approximation. Please see Line 854 in the supplementary material for the precise defition of $\mathbf{w}^{i,\*}$ under the discounted reward setting. In Theorem 4, the term $\mathbf{w}^{i}-\mathbf{w}^{i,*}$ refers to the error in convergence from critic component of Algorithm 1 and the optimal linear approximation parameter for $i$-th objective.

Thanks a lot for your detailed replies! We can now focus on my previous Comments 1, 2, 7 and 8.

The main issue with the paper's organization is that others can strongly overestimate the contributions.

As stated in Reviewer P2zK's summary, "The WC-MOAC algorithm is designed to combine multi-temporal-difference (TD) learning in the critic phase with ... multi-gradient descent in the actor phase, effectively managing the complexities of non-convexity and scalability in multi-objective problems. The primary theoretical result of this work is a finite-time sample complexity bound, which is independent of the number of objectives ... This independence ... is a notable theoretical advance."

Reviewer qYKr02 stated:" Central to the discussion is the concept of (local) (weak) Pareto optimality, which serves as the foundational solution criterion for balancing multiple objectives. The proposed training architecture employs a single actor coupled with multiple critics, where each critic is specifically trained to approximate the value function corresponding to a distinct objective."

None of these are your novel contributions, which Zhou and colleagues have introduced. The paper writing is strongly misleading.

As your reply to the first comment stated, this work "focuses on systematically exploring the Pareto Stationary front using a weighted-Chebyshev formulation." The introduction of the preference weighting is the main contribution.

However, your experiment design does not show the advantage of including such weighting. For the experiment in Table 1, the effect of emphasizing "Comment" or "Dislike" objectives can be more persuasive. As replied to Comments 7 and 8, the preference vector is not trained. What is the systematic way of deciding the weighting in your approach? As TSCAC, does your method also require domain knowledge? Meanwhile, for the experiment shown in Figure 1, concentrating on click, dislike, and watch do not differ much.

Your Comment 1 (Also Weakness 1): The contribution can be stated more directly. For example, the abstract mentions that the algorithm fills the gap "to systematically explore the Pareto-stationary solutions". It would be more apparent if the paper explained why it is needed to explore these solutions and how the exploration is achieved.

Our Response: When decision-maker aims for optimizing in a multi-objective setting, at the beginning there's not always a clear priori on what the preference for a particular Pareto Optimal solution among the set of Pareto Front(PF). Considering such potential uncertainty in priori, exploring the PF has been an on-going effort on multi-objective problem settings [1]. On the other hand, once PF is entirely characterizes, it allows a Posteriori selection of a preferable Pareto solution, giving better insight to a decision-maker [2]. Towards this effort, we are proposing a WC-MOAC algorithm that enables systematically exploration of Pareto solution in MORL context, which is under-investigated.

[1] Kristof Van Moffaert and Ann Nowé. Multi-objective reinforcement learning using sets of pareto dominating policies. The Journal of Machine Learning Research, 15(1):3483–3512, 2014.

[2] Simone Parisi, Matteo Pirotta, and Marcello Restelli. Multi-objective reinforcement learning through continuous pareto manifold approximation. Journal of Artificial Intelligence Research, 57:187–227, 2016.

Your comment (Also Weakness 2): The paper overstates the contribution without a clear acknowledgement of previous work. The paper should introduce the work by Zhou et al. (2024) with more details, and it is also necessary to make a comparison to clarify the novelty of the work.

Our Response: To highlight the contribution of this work, we provide following comparisons with (Zhou et al. (2024)).

Objective Differences: Our work focuses on systematically exploring the Pareto Stationary front using a weighted-Chebyshev formulation. This objective is distinctly different from that of (Zhou et al., 2024), which aims to find a Pareto stationary point rather than exploring the full Pareto stationary front.

Methodological Innovation: We have incorporated a weighted-Chebyshev formulation, a technique which is entirely absent in (Zhou et al., 2024). Our paper devotes Section 4.2 to describing this approach in detail, illustrating how we use the weighted-Chebyshev method to achieve systematic exploration. This technique leverages an exploration/weight vector $\mathbf{p}$, extensively explained in our derivations.

Unique Theoretical Contributions: Our Theorem 4 and Corollary 5 highlight the effects of the weight vector $\mathbf{p}$, particularly through its minimum entry, $p_{\min}$, on convergence rate to Pareto stationarity and corresponding sample complexities for each exploration. While some order-wise results appear similar, the coefficients in Theorem 4 are different from those in (Zhou et al., 2024).

Empirical Evidence: In Figure 1 of Experiment Section, we present the Pareto footprint, i.e., the Pareto fronts explored by our method via varying exploration/weight vector $\mathbf{p}$ and a popular linear scalarization approach. In contrast, (Zhou et al., 2024) includes no such comparative analysis.

Your Comment 3(Also Weakness 3): Line 100 states, "Collectively, our results provide the first building block toward a theoretical foundation for MORL." Zhou et al. (2024) gave a sample complexity bound of the same order.

Our Response: We are happy to remove this statement and acknowledge the contribution from the previous literature including (Zhou et al. (2024)). For the second point, we want to emphasize that proving the same sample complexity doesn't mean it's not a new result in the context of leveraging the weight-Chebyshev. In particular, reiterating the point in our response to your comment 2, while some order-wise results appear similar, the coefficients in Theorem 4 are different from those in (Zhou et al., 2024).

Your Comment 1 (Also Weakness 1): While the paper provides a comprehensive theoretical foundation, certain methodological aspects could be clarified further. For example, the integration of the multi-gradient descent update, which computes a dynamic weighting vector $\lambda_t$ that balances exploration with convergence, could benefit from a more detailed discussion on its rationale and practical implementation steps.

Our Response: Thanks for your comments. In terms of computing weight vector $\lambda_t$, it is obtained from solving Eq. (10), whose solution $\hat{\lambda}^{*}_t$ is then used in the momentum computation in Eq.(11). In Eq.(10), the $\lambda_t$-solution balances two aspects:

1. the first term corresponds to multiple-gradient descent approach, which is an approach to ensure achieving Pareto stationarity upon convergence.

2. The second term $\lambda^{\top}(\mathbf{P}\odot(\mathbf{J}^{*}_{ub}-\mathbf{J}(\theta)))$ corresponds to the weighted-Chebyshev scarlization formulation, which induces Pareto stationarity front exploration as explained in the paper.

3. The hypber-parameter $u>0$ is used to balance the trade-off between i) achieving a Pareto stationary solution and ii) systematically exploring the Pareto stationarity front.

Your Comment 2 (Also Weakness 2): Additionally, the empirical evaluation is limited to a single dataset, the KuaiRand offline dataset, which raises questions about the algorithm's generalizability. Expanding the experimental analysis to include diverse datasets or multi-objective environments would provide deeper insights into the algorithm's robustness across varied applications.

Our Response: Thank you for your suggestions. In this rebuttal period, we will provide more experimental settings. We are still working hard on conducting further experiments and will provide you an upate as soon as we are finished. Unfortunately, adding more datasets during this rebuttal period is quite challenging due to i) the limited amount of time and ii) the KuaiRand is the only suitable large-scale dataset for MORL that we can find at the current stage. We hope these resource limitations will not negatively affect the reviewer's evaluation toward our work.

Your Comment 3 (Also Question 1): The paper would benefit from further clarification on several key points. First, could the authors discuss the impact of the preference vector $\mathbf{p}$ on the algorithm's performance, especially in environments with highly non-convex reward landscapes?

Our Response: We thank the reviewer for this insightful question. For settings with non-convex accumulated reward landscapes (i.e., $J^{i}(\theta)$ is nonconvex in variable $\theta$ for some reward function $i\in [M]$), our algorithm converges to a Pareto stationary point for any given weight vector $\mathbf{p}$ suggested by Theorem 4. Note that Pareto stationarity is a necessary condition for Pareto optimality. Similar to single-objective non-convex optimization for machine learning problems, it is often acceptable to find a Pareto stationary solution in the non-convex multi-objective settings.

Your Comment 4 (Also Question 2): As the convergence rate depends on $p_{\min}$, understanding the selection of $p$ would be useful for real-world applications.

Our Response: Thanks for your comments and questions. Our Theorem 4 suggests that the smaller miminum enntry in vector $\mathbf{p}$ (i.e. smaller $p_{\min}$-value), the slower the convergence is. This implies that it might take more iterations to explore the Pareto stationarity front with a smaller $p_{\min}$-value. On the other hand, in order to systematically explore the Pareto stationary solutions, the user can vary and enumerate the vector $\mathbf{p}$ in the $M$-dimensional standard simplex, which is then taken by Algorithm 1 as input. For example, one possible approach will be using a grid search for trying different $\mathbf{p}$ vectors.

Your Comment 5 (Also Question 3): Additionally, what limitations, if any, might arise in adapting the proposed algorithm to online settings, given that the study's empirical evaluation is restricted to offline data?

Our Response: In fact, the proposed Algorithm 1 is an online algorithm. Since KuaiShou dataset used in the empirical studies is an offline dataset, we have adapted our algorithm to the offline MORL setting. In principle, Algorithm 1 should perform better in online settings due to the fact that, in online setting, the algrotihm can sample more diverse data to evaluate and improve upon the current policy. In contrast, in offline MORL, the algorithm needs to work on the online dataset collected by a behavior policy, which may only have a limtied coverage.

Your Comment 1: Page 5 eq (2). On the left of “:=” is a function of x, while on the right you have a scalar. Please make the definition consistent.

Our Response: Thank you for pointing out this typo. We will revise the definition as follows in the revision: $WC_{\mathbf{p}}(\mathbf{F}(\cdot)) := \min_{\mathbf{x}}\max_{i\in[M]}\{ p_i f_i(\mathbf{x})\}= \min_{\mathbf{x}} \\| \mathbf{p} \odot \mathbf{F}(\mathbf{x}) \\|_{\infty}.$

Your Comment 2: Page 5 Lemma 1. You do not provide a proof for Lemma 1. Please reference the exact theorem or proposition from the cited work that supports Lemma 1.

Our Response: Thanks for your comments. Lemma 1 is cited from Proposition 4.7 and its proof on Page 42 in (Qiu et al. (2024)). Specifically, on Page 42 of the proof of Proposition 4.7, Part 1) and Part 2) collectively provide an "if-and-only-if" statement in Lemma 1 of this paper. We will provide more clarification on this in our revision.

Qiu, S., Zhang, D., Yang, R., Lyu, B., & Zhang, T. (2024). Traversing pareto optimal policies: Provably efficient multi-objective reinforcement learning. arXiv preprint arXiv:2407.17466.

Your Comment 3: Lemma 1 states existence of the vector $\mathbf{p}$, which is directly related to a weak Pareto-optimal. However, it is not clear how $\mathbf{p}$ is determined in practice within the algorithm. Does Theorem 4 hold for arbitrary p or for the specific p provided in Lemma 1? It would be helpful to include a more detailed explanation of p’s role in the algorithm and whether it influences the theoretical guarantees.

Our Response: Thanks for your question. Again, we would like to emphasize that Lemma 1 is an "if-and-only-if" statement, which implies that there is a one-to-one mapping between a WC-solution and a Pareto-optimal solution and further suggest a systematical way to explore the Pareto-front (assuming the WC-scalaization problem can be solved to optimality). As a result, when applying Algorithm 1, one does not need to carefully pick the vector $\mathbf{p}$. Rather, the decision-maker is supposed to vary and enumerate the vector $\mathbf{p}$ in the $M$-dimensional standard simplex, which is then taken by Algorithm 1 as input to systematically explore the Pareto front. Also, Theorem 4 holds for arbitrary $\mathbf{p}$ whose entries are strictly positive (but one would typically use $\mathbf{p}$ in the $M$-dimensional standard simplex to avoid arbitrariness in scaling). For those $\mathbf{p}$-vectors with some entries being 0, one can simply discard those zero entries and reformulate the problem in a multi-objective RL problem with lower dimension, which only retains those non-zero entries in the original $\mathbf{p}$.

Your Comment 4: Page 7. It will be clearer if you specify what arguments you are optimizing. In eq (7), could you clarify whether the optimization is over $\mathbf{\lambda}$, or both $\lambda$ and $\mathbf{\theta}$? It appears from my understanding that eq (9) optimizes over both $\lambda$ and $\theta$, whereas eq (10) involves only $\lambda$.

Our Response: Thanks for your question. In Eq.(7), we are optimizing over $\lambda$ for any given $\theta$, where $\pi_{\theta}$ denotes the current policy. Similarly, in Eq.(9), we are also optimizing over $\lambda$ for any given $\theta$. The rationale is that, given the current policy evaluation from the critic component, we want to leverage and integrate multi-policy-gradient descent (first term in Eq.(10)) and the weighted-Chebyshev scalarization (second term in Eq.(10)) to guide the policy update direction to achieve a balance between i) converging to a Pareto stationary solution and 2) systematically exploring the Pareto stationarity front.

Your Comment 5: Page 7 line 340, “gradient” should be “Jacobian”.

Our Response: Thanks for your question. Here, matrix $\mathbf{G}$ we are referring to is $\mathbf{G}=-[\nabla_{\theta} J^{1}(\theta), \cdots, \nabla_{\theta} J^{i}(\theta), \cdots, \nabla_{\theta} J^{M}(\theta)].$ In other words, each column $i\in [M]$ is the gradient of $J_{\text{ub}}^{i,\*}-J^{i}(\theta)$ with respect to $\mathbf{\theta}$, where $J_{\text{ub}}^{i,\*}$ is an upper bound constant. Hence, $\mathbf{G}$ is related to but not exactly the Jacobian (more precisely, it is negative Jacobian matrix). We will further clarify this in our revision.

Your Comment 6: Page 8 Def 3 line 419. $\lambda$ is already given. Why do you have $\min_{\lambda}$?

Our Response: Thank you for pointing out this typo out. We will revise it in revision and change it to $\\| \nabla_{\theta} \mathbf{J}_{\theta}(\theta) \lambda \\|_2^2 \leq \epsilon$.

We appreciate the reviewer's constructive comments and valuable insights. The detailed point-by-point responses are as follows:

Your Comment 1: The pseudo code of WC-MOAC are almost the same (almost verbatim) as those of the MOAC algorithm (cf. Algorithms 1 and 2 in (Zhou et al., 2024)).

Our Response: In this paper and (Zhou et al., 2024), the algorithms both utilized actor-critic framework, which is a widely used and standard RL framework. If merely following the actor-critic framework violates academic integridty, then we are not sure how the reviwer would view the thousands of papers published in the RL literatrue that adopted the actor-critic framework. Further, in terms of the algorithms, the following are the major differences between our work and (Zhou et al., 2024):

1. Algorithm 1 in this paper is presented as a single-oracle, which includes both Critic and Actor components; whereas in (Zhou et al., 2024), the critic component is presented as a subroutine, which is called in its main Algorithm 2. In this paper, we have leveraged a weight/exploration vector $\mathbf{p}$ to explore the Pareto stationarirty front (a necessary condition for Pareto Front). This is reflected by two major aspects (see next two points), which are not present in (Zhou et al., 2024).

2. In the second column of Line 395, $\hat{\mathbf{\lambda}}^{*}_t$ is the solution of Eq. (10), which is an objective function that carefully balances the Weighted-Chebyshev exploration controlled by the $\mathbf{p}$-weight vector and the mutpile-gradient descent term. If one were to check Eq. (10) in this paper and Eq. (9) in (Zhou et al. (2014)), it is apparent that they are completely different.

3. Leveraging a weight vector $\mathbf{p}$, the update for $\mathbf{g_t}=\mathbf{G_t}(\mathbf{p}\odot \mathbf{\lambda_t})$ in this paper, which enables the exploration of the Pareto front (also see Figure 1 for the exploration effect). In contrast, there is no such Hadamard multiplied $\mathbf{p}$ term for the policy update in (Zhou et al., 2024), which is in the form of $\mathbf{g}_{t}=\mathbf{G}_t(\mathbf{p}\odot \mathbf{\lambda}_t)$. We also note that the solution of Eq. (10) yields a completely different quantity from that of Eq. (9) in (Zhou et al. (2014)). As a reuslt of such a difference, the algorithm in (Zhou et al. (2024)) can only guarantee convergence to a Pareto stationary point, but lacks the capability of systematic Pareto stationarity exploration.

4. In the actor component of this paper, we require the computation of score function $\mathbf{\psi}_{t,l}$ by Eq.(12) (see approximately in Line 388 in the second column). This is clearly not in the Pseudo code of (Zhou et al., 2024).

5. In Algorithm 1, it is required that $w^{i}_k=w^{i}_t$ for synchronization of the critic parameters (see the first column in Line 398-399). Note that this is absent in (Zhou et al. 2024).

6. Among the input of Algorithm 1 (Lines 380-381), our algorithm requires a weighted/exploration vector $\mathbf{p}$ in addition to standard input parameters for actor-critic with linear approximations.

Again, we want to emphasize that the actor-critic algorithmic framework in the RL literature will share a lot of structural similarities, including (Zhou et al. (2014)). This also indicates the popularity of the actor-critic framework for solving RL problems. The similar notations are due to the convention in the literature for the ease of understanding.

I sincerely thank the authors for the detailed response and for answering my technical questions. Below let us focus more on the Comments 1-8.

• Comment 1 (regarding the pseudo code of WC-MOAC and MOAC), Comment 2 (regarding the theoretical results), and Comments 3-4 (regarding the introduction): I can understand that both algorithms share the actor-critic architecture, and the two papers are both focused on the convergence to the stationarity. However, from a reviewer’s viewpoint, given the high similarity (in terms of design, paper structure, and even wording), it appears almost impossible to argue that this paper is completed independently from [Zhou et al., 2024] or the two are just concurrent works. Moreover, as far as I understand, such similarity in both structure and wording shall be viewed as paraphrasing, which is not allowed if there is no due credit or acknowledgement given to the prior works (i.e., [Zhou et al., 2024]). Furthermore, as mentioned by Reviewer JPv7, without a proper comparison with or mention of [Zhou et al., 2024], the readers can be easily misguided by the overclaimed contributions.

• Comment 5 (regarding the Key Contributions): Just like the comment above, my concern about paraphrasing in this part still remains unsolved. Moreover, apart from the structure and wording, the novelty and contributions can be overestimated without properly mentioning [Zhou et al., 2024]. Specifically:

In the first bullet of our "Key Contributions,"" we mentioned the impacts of the weight/exploration vector on the sample complexity. More importantly, we proposed a completely different WC-MOAC algorithm, which systematically explores Pareto stionarity front assisted by the $\mathbf{p}$-vectors. These are clearly not in (Zhou et al.(2024)).

Based on the current writing of the paper, the readers can get easily misled that WC-MOAC is a totally new algorithm in the MORL literature. However, under a comparison with MOAC, WC-MOAC can indeed appear somewhat incremental.

The second bullet in our "Key Contributions" addresses, even with such weight vector $\mathbf{p}$, it achieves sample complexity that is independent of $M$, where $M$ is the number of objectives.

This is also one key feature that has been shown by MOAC. Then, this would not be a convincingly new feature for people to choose WC-MOAC over MOAC.

Similarly, the third bullet in our "Key Contributions" showed the benefit of the momentum approach in the weighted-Chebyshev Pareto stationarity exploration.

As far as I know, the momentum-based design has already been proposed by MOAC (cf. Equation (10) in [Zhou et al., 2024]), and its benefit has been shown by the MOAC paper.

Lastly, our empirical results strongly suggest the nature of exploration Pareto stationarity points by looking at Figure 1, which does not have any counterpart in (Zhou et al. (2024)). The key takeaways from this paper is very different from that of (Zhou et al. (2024)).

I can understand that the empirical results are shown to corroborate the nature of exploration of Pareto stationary points. That being said, if one directly compares the results of MC-MOAC and those of the MOAC in [Zhou et al., 2024] in terms of Like, Comment, Dislike, and WatchTime, the differences appear rather not significant. It is not immediately clear to me why the empirical results (cf. Table 1 and Figure 1) clearly supports the claim. While I understand in general that the works published within 3 months of submission are not necessarily needed in the comparison, a comparison with MOAC can serve as a really helpful ablation study and hence nicely support the claim of the paper. Please correct me if I missed anything.

• Comments 6-8 (regarding the writing of the problem formulation and preliminaries): I understand that MDP and MOMDP are standard problem formulations in RL. However, there are various ways to describe the same setting. As far as I know, it is a standard practice to describe the problem formulation that tailors to the need of each specific paper and hence shall be written in the authors’ own words. Again, as mentioned above, this similarity in both structure and wording shall be viewed as paraphrasing and is not allowed if there is no due credit or acknowledgement given to the prior works. Therefore, I would like to emphasize that “using the similar formulations” is not the issue, and the high similarity in terms of structure and wording is where the concerns arise. I hope that the authors can understand my concerns.