Divide and Conquer: Provably Unveiling the Pareto Front with Multi-Objective Reinforcement Learning

We appreciate the feedback from the reviewer and have addressed the raised questions and suggestions.

Baselines and presentation

With respect to the baselines, as mentioned in our general comment, GPI-LS is currently the state-of-the-art method for learning a convex hull. As the Minecart and MO-Reacher have (mostly) convex Pareto fronts, GPI-LS (which explicitly relies on this knowledge) presents a suitable “upper bound” on IPRO which does not make the simplifying assumption that the scalarisation function is linear.

To better convey why one would prefer IPRO over related work, we have introduced Table 1 in the introduction which summarises our contributions. In a nutshell, IPRO addresses a more general setting, discarding the assumption of linearity of the scalarisation function. This allows IPRO to also discover a richer front of Pareto optimal policies as well as tackle different policy classes. We have further attempted to improve the presentation of the paper by removing section 3.2.1 and adding the pseudocode for IPRO to the main text.

Responses to Raised Questions:

1. Utilising Another Multi-Objective Algorithm as a Subroutine: IPRO serves as a problem-agnostic algorithm, identifying target regions for undiscovered Pareto optimal points and delegating the task to a problem-specific subroutine. This approach allows for flexibility in handling various optimization tasks, extending beyond multi-objective reinforcement learning. The extension of the GGF-DQN algorithm allows for IPRO to be applied to the MORL setting, which we are particularly interested in, but it could indeed be applied more broadly to different domains.
2. Theorem 4.1 and Assumptions on Pareto Oracle: While additional assumptions are not explicitly placed on the Pareto oracle, we define the concept of a Pareto oracle ourselves, thus embedding certain desiderata into its definition. One example is that, we ensure that a Pareto oracle always returns an optimal point in its target region, but future work may be able to relax this definition.
3. Impact of Single-Objective RL Solution Accuracy on IPRO: While this may indeed happen with certain single-objective methods, this need not be a problem for IPRO. For example, if it is known that the single-objective RL solver has some bounded error, we may simply adjust the nadir and ideal to account for this. On the other hand, we could also “assume” that the method used to generate the nadir and ideal always does so optimally. Then, IPRO will still obtain all points in the resulting bounding box but may fail to retrieve the points outside the bounding box.
4. The definition of Achievement scalarising functions: We have updated the definition of $s_\mathbf{r}$ to better explain this. Intuitively, the ASF is instantiated with a referent $\\mathbf{r}$. We have also added a definition of the target region. Formally, the target region given a reference point $\\mathbf{r}$ contains all points $\\mathbf{v}$ such that $\\mathbf{v} \\succeq \\mathbf{r}$. We have added this to the preliminaries.
5. Definition \\mathbf{v}^\\pi: We have added a rigorous definition of the expected return value \\mathbf{v}^\\pi in the Problem Setup (Section 2) for clarity.

Thank you again for the constructive feedback. Please let us know if you have any additional questions or comments.

We appreciate the insightful questions raised by the reviewer and would like to provide clarifications on the points raised.

Reference point selection

The question about selecting the reference point from the set of lower points is addressed in the appendix due to space constraints. In practice, we use a heuristic that chooses the point with the most "open space" (i.e. space not allocated to an excluded subset) dominating it. The intuition is that a reference point with more open space above it is more likely to lead to the discovery of a Pareto optimal point. It is essential to note that IPRO is not reliant on any specific selection method, and this heuristic is employed for practical efficiency.

Convergence and Utility Function

We note that while convergence to the true Pareto front is asymptotic, we can guarantee convergence in a finite number of iterations to an arbitrary $\\tau$-Pareto front with $\\tau > 0$. The main benefit of IPRO is that we do not assume that utility is a weighted sum of the objectives, as opposed to Envelope, PGMORL, GPI-LS, and the vast majority of work in MORL. Rather, we allow for any nonlinear utility function. It has been proven that in the case of deterministic policies, the resulting Pareto front may be non-convex and hence methods which rely on linear scalarisation are inherently incapable of retrieving the full front. IPRO in contrast can find all points. We highlight this now in the introduction by adding a table which summarises the contributions of our work compared to relevant related work.

Convergence rate

While this is an interesting question, it is not straightforward as the convergence of IPRO is also dependent on the distribution of points on the Pareto front. It may be possible to characterise the behaviour of IPRO in the worst-case distribution of points along a Pareto front. We do not have any concrete results along this line but consider it an interesting topic for future work.

Pareto oracle definitions

The distinction between a weak Pareto oracle and an approximate Pareto oracle is primarily for theoretical rigour. However, both types of Pareto oracles may lead to different practical implementations. In the appendix, we describe the implementation of an approximate Pareto oracle using constrained MDPs, which would not be feasible with weak Pareto oracles.

Thank you again for the detailed feedback. If you have any further questions, we would be happy to answer them.

We appreciate the detailed feedback from the reviewer and would like to address the raised points.

Sample Complexity and Learning From Interactions

We believe the reviewer strikes an important point. Indeed, given our current training setup, we train a new policy in each oracle call. However, it is likely that a single-network approach is also possible with IPRO. As our primary focus was on novel theoretical results in this challenging setting, we did not yet opt for this approach but consider it a promising direction for future work.

As suggested, IPRO is indeed problem-agnostic and can thus be applied for general multi-objective problems. We are primarily interested in learning a Pareto front in MOMDPs where no explicit model is given, hence necessitating the use of RL as a subroutine. We plan to evaluate IPRO in related domains, such as optimisation and pathfinding, in the future.

$\lambda$ and $\rho$ parameters

We note that $\lambda$ is a weight vector that is supplied by IPRO and is computed as $(\mathbf{v}^\text{i} - \mathbf{r})^{-1}$ where $\mathbf{v}^\text{i}$ is the ideal and $\mathbf{r}$ the referent. This normalises the improvement of a vector $\mathbf{v}$ relative to the referent $\mathbf{r}$ by the theoretical maximum improvement at the ideal $\mathbf{v}^\text{i}$. The purpose of this normalisation is to maintain a balanced scale across all objectives, preventing the dominance of one objective over another. $\rho$, on the other hand, is a hyperparameter which we tune.

$L$ and $U$ sets

The construction of the sets $L$ and $U$ is now detailed more explicitly in Appendix B1. Intuitively, this is a sequential process that starts from the initial $L$ and $U$ sets. Then, every time a new point is added to the Pareto front, we can compute the added “corners” of the boundaries of the dominated and dominating sets. These new corners are then added to $L$ and $U$. For a visualisation, we refer to Figure 2. Pseudocode is also presented in Algorithm 2.

Brief answers to the remaining questions:

1. The use of pruning: Pruning does not uncover additional points, but rather rejects points which are not Pareto optimal but were added during IPRO’s execution. This step may be safely omitted without changing anything except possibly returning an unnecessarily large set.
2. Memory-based policy implementation: We concatenate the memory (which is the accrued reward until the given timestep) to the observation and feed this into the neural network. This induces what is known in the MORL literature as an “augmented state space” and is a common approach.
3. Definitions of “nadir” and “ideal” vector: The nadir $\mathbf{v}^\text{n}$ is defined as the “greatest lower bound” while the ideal $\mathbf{v}^\text{i}$ is defined as the “least upper bound”. To give an example, let $PF = \\{(1, 2), (2, 0)\\}$ then the nadir is $(1, 0)$ while the ideal is $(2, 2)$. These quantities are defined in the preliminaries.
4. The design of $a^\ast$ in eq (3): Intuitively, this definition “mimics” the optimisation objective of the agent where it aims to optimise its scalarisation function applied to the expected returns of the policy. While this update does not exactly represent this objective, it is common in the MORL literature and works well in practice.
5. The discrepancy between coverage and hypervolume: The DQN agent fails to find a Pareto optimal point in some target region and then incorrectly excludes the search space in the region from consideration. As such, it has a higher coverage while still resulting in a lower hypervolume. For future work, we plan to extend IPRO to incorporate uncertainty over which sections of the search space may still contain optimal points rather than the current approach of including/excluding search space.
6. Usage of Section 3.2.1: We intended to inform the reader that the concept of a Pareto oracle is feasible to implement and comes with theoretical grounding for specific policy classes. We did not use it in the remainder of the text. However, most reviewers agreed that this section was unnecessary and complicated the understanding of our paper. We have therefore moved this section to the appendix and added the pseudocode of IPRO to the main text instead.

Thank you again for the detailed feedback. If you have any further questions, we would be happy to answer them.

Thank the authors for the detailed response. The algorithmic details have been made more transparent in several places. That said, regarding the sample efficiency and the comparison with the MORL benchmark methods, my concerns still nevertheless remain, as also pointed out by other reviewers. Therefore, I tend to maintain my original rating.

We appreciate the positive feedback from the reviewer regarding the contributions of our paper. Below, we address the main remarks and also go over the detailed questions.

Advantages of IPRO

In the vast majority of MORL, exemplified by references [1] (envelope) and [2] (PG-MORL), a simplifying assumption is made that decision-makers have linear preferences, resulting in a convex Pareto front and the sufficiency of deterministic policies. By forgoing such assumptions, IPRO gains a unique advantage in addressing more general settings. To support this claim, we focus on deterministic memory-based policies, a class where the Pareto front may exhibit non-convexity. Indeed, the assumption of linear preferences in the Deep Sea Treasure environment leads to only two of the ten Pareto optimal policies being retrievable. Critically, IPRO does not assume linear preferences and is thus able to find all Pareto optimal solutions. We present a summarising table in the introduction, highlighting IPRO's advantages compared to related work.

Experimental Results

Addressing the concern about experimental results, we conducted an extended hyperparameter search, resulting in significant improvements across all experiments. In addition, it is worth noting that the Reacher benchmark is a MuJoCo environment and that the remaining multi-objective MuJoCo environments in MO-Gymnasium have continuous actions. While IPRO is agnostic to the underlying problem and thus could handle continuous actions, this would require significant additional contributions as there has been limited work tackling such complex continuous control settings with nonlinear scalarisations. Finally, we did not compare against Envelope, PG-MORL and Q-Pensieve as GPI-LS has been reported to reach state-of-the-art results on the chosen benchmarks.

Presentation

As stated in our general comment, we have moved Section 3.2.1 to the appendix and added pseudocode for IPRO to the main text. We believe that this improves the presentation.

Occupancy measure in section 3.2.1

We moved this section to the appendix to avoid confusion. To briefly clarify, an occupancy measure intuitively denotes how frequently a specific state is visited when employing a particular policy. This metric is commonly used in concave utility RL and for deriving theoretical results in classical RL settings.

Training details and pruning

Each iteration of the Pareto oracle runs for a fixed number of steps, which is reported in the appendix. After the entire execution of IPRO has concluded, we perform one pruning step to remove weakly Pareto dominant solutions. While not strictly necessary, this step avoids presenting unnecessary solutions to decision-makers. To enhance clarity, we have removed the mention of pruning from the main text, addressing this aspect instead in the appendix. Additionally, we've expanded the appendix to provide additional details regarding the algorithm (Appendix B1) and training procedure (Appendix D).

Thank you again for the constructive feedback. Please let us know if you have any additional questions or comments.