Navigating the Social Welfare Frontier: Portfolios for Multi-objective Reinforcement Learning

We thank you for your incredibly detailed and insightful comments! Additional results are available in the anonymous link here

1. On the overstimation of oracle complexity in Theorem 4.1, and how this impacts our current results.

• We thank you for pointing out such a detailed point! Indeed, both expressions are valid upper bounds. The version stated in the paper,($O\left(\frac{\ln(\kappa)^2 \ln\ln(N)}{\ln(1/\alpha)\ln\ln(1/\alpha)}\right)$ is intentionally presented in a slightly simplified, cleaner form. The more precise, but somewhat more complicated expression, would be $O\left(\frac{(\ln \kappa)(\ln \kappa + \ln\ln(N))}{\ln(1/\alpha)\ln\ln(1/\alpha)}\right)$); we will include this bound in the revised version. Both formulations correctly bound the oracle complexity, with our stated version slightly overestimating it for simplicity.

2. Discussions on selected $p$ values in the experiments.

• We thank you for the great suggestion. Yes, your understanding is correct: our approach outputs pairs of $p-$value and the corresponding optimal policies. We have included the entire $p$ values chosen by our main algorithm $p$-MeanPortfolio in the anonymous link, Table 2. Furthermore, we have provided illustrative results demonstrating how the outcomes of the optimal policies for different $p$ values in the portfolio lead to varying impacts for the stakeholders (see Figures 4,5). We observe that the $p$ values are quite diverse, which corroborates the algorithm's objective to cover the entire $p$ range only with these selected values.

  For the random $p$ baseline, however, it is more challenging to present the entire $p$ values with meaningful explanations. Due to the inherent randomness of this baseline, we generate 10 independent random $p$ portfolios and report the average performance across these runs (see Section 5.1 for details). Since the $p$ values are sampled uniformly at random from an interval, listing them would result in too many random values without providing additional useful insight.

3. Why the heuristic can sometimes outperform the p-meansPortfolio

• $p$-MeanPortfolio selects policies solely to meet the input approximation factor $\alpha$. However, the algorithm has no incentive or mechanism to surpass this approximation quality.

  In contrast, the heuristic fully utilizes the input budget $K$, and strategically selects boundary points first (a small initial $p$ followed by $p=1$). When $K$ is very small (1 or 2), this initial heuristic strategy can provide more effective coverage across $p \in [-\infty, 1]$, explaining its occasional superior performance.

4. Code Reproducibility in the Supplementary materials.

• We have included the code to replicate our results in the anonymous link, and have verified that everything runs seamlessly. Thank you for pointing this out.

5. It seems that this method is applicable for reduced-size (small-sized portfolios) problems.

• In our experiments, the algorithms indeed resulted in small-sized portfolios while maintaining high approximation guarantees. However, we respectfully argue that our method is not inherently limited to small-sized portfolios. The theoretical results we provided explicitly characterize how portfolio size depends on the underlying problem parameters, allowing the method to scale accordingly. Our experiments involve a significantly larger number of reward functions (stakeholders) compared to prior MORL research, demonstrating the effectiveness of our method beyond simpler settings.

6. Typo in Lemma A.4.

• We thank the reviewer for noting this detail! We will promptly correct the typo.

We thank you for the insightful comments! Additional results are available in the anonymous link here

1. The selection of baselines seems somewhat unfair ... much more Oracle calls.

• Thank you for your comment. However,if we match the number of oracle calls for the random $p$ baseline, the resulting portfolio becomes impractically large. For instance, in the taxi environment, our portfolio achieves an approximation factor of 0.99 with 10 policies (using 144 oracle calls), while the random baseline under the same oracle calls will produce 144 policies. Thus, although both approaches may yield similar approximation quality under the same oracle budget, our method does so with significantly fewer policies.

2. It is unclear how p-means were tuned ... given number of policies.

• We do not manually tune the $p$ values to explicitly control the number of policies in the portfolio. Instead, the portfolio size is implicitly controlled through the desired approximation factor $\alpha$. Given a specific $\alpha$ as the input, our algorithm systematically searches through the entire range of $p \in [-\infty, 1]$, automatically selecting a minimal set of representative $p$-values to build a $\alpha-$approximate portfolio.

3. The general task of the paper is hard to grasp ... of broader impact to the machine learning community.

• We thank you for this important comment. Generalized $p$-means represent a widely used and theoretically justified class of social welfare functions in MORL. However, an important practical challenge that was previously overlooked is that the right fairness criterion (the choice of $p$) can be unclear in advance. Selecting a policy optimized for an arbitrary $p$ can lead to poor outcomes under a different $p$ value (see the approximation qualities of random $p$ baselines in our experiments).

  We propose computing a small yet representative set of policies that covers the entire spectrum of fairness criteria represented by $p \in [-\infty, 1]$. The decision-maker can confidently select from this portfolio, without worrying about suboptimality under other potential choices of $p$.

  Finally, we respectfully argue that the assumption on reward ranges is not overly restrictive. If each reward function $i \in [N]$ has a different range $L_i \leq R_i(\cdot) \leq U_i$, we can simply define a universal reward range as $L := \min_{i \in [N]} L_i$ and $U := \max_{i \in [N]} U_i$ without loss of generality.

4. The example in section 1.2 did not help me ... varying the p-value actually means.

• We thank you for this suggestion. To clarify the meaning behind $p$-means, we constructed an illustrative example in Figures 1, 2, and 3. In this example, three vectors $A$, $B$, and $C$ represent different policies, where each vector's $i$-th entry is the reward for the $i$-th stakeholder. Here, $A$ is a balanced policy, $B$ is unbalanced with a high sum, and $C$ lies in between. Figure 3 plots the $p$-mean values of these vectors, showing that varying $p$ leads to different optimal policy.

5. The section on warm-starting the oracle ... convergence of the method used to solve the MDP.

• We thank you for this comment. Indeed, the provided bound does not directly translate into an explicit convergence rate, as this rate depends heavily on the specific algorithm used to solve a given MDP. What we aimed for is a theoretical foundation that quantifies the benefits of warm-starting regardless of the algorithm, using the distance between an initial value function (obtained by warm-starting) and the optimal value function, which is standard metric in the literature.

6. How did you select the $\alpha$ values?

• For a given portfolio size $K$, we chose the smallest $\alpha \in \{0.10, 0.15, \ldots, 0.90, 0.95\} \cup \{0.99\}$ among which the resulting portfolio has size $K$. We will make sure to clarify this point in the revision.

7. Why the approximate algorithm can outperform the p-meansPortfolio

• $p$-MeanPortfolio selects policies solely to meet the input approximation factor $\alpha$. However, the algorithm has no incentive or mechanism to surpass this approximation quality.

  In contrast, the heuristic fully utilizes the input budget $K$, and strategically selects boundary points first (a small initial $p$ followed by $p=1$). When $K$ is very small (1 or 2), this initial heuristic strategy can provide more effective coverage across $p \in [-\infty, 1]$.

8. What is the set of feasible set of policies ... using the Oracle?

• The set of feasible policies $\Pi$ is assumed to be given as an input. Note that $\Pi$ may include all possible policies within an MDP and need not be a small, restricted set. The Oracle we refer to computes the welfare-maximizing policy within $\Pi$, given a fixed value of $p$ (i.e., a fixed social welfare function).

We thank you for the insightful comments! Additional results are available in the anonymous link here

1. Including one or more realistic environment with higher number of objectives.

• We respectfully note that our experiments already consider a significantly higher number of objectives compared to most previous MORL studies. For example, while the referenced papers explore up to 16 objectives (Yu et al., 2024), 6 in [1], 2 in [2], and 9 in [3], our setups include a natural disaster scenario with 16 objectives and a healthcare intervention scenario with 59 objectives. We will make sure to emphasize this point in our manuscript.

2. The relation to the paper (Yu et al., 2024) and the benefits of our work over existing methods

• Yu et al. (2024) optimize a generalized Gini welfare assuming a fixed weight vector. We address a fundamentally different scenario, where decision-makers are uncertain about the appropriate fairness criterion (e.g., the choice of $p$ in $p$-means or the selection of weights in Gini welfare) in advance. Optimizing a single policy for one fairness parameter can lead to poor outcomes under different criteria (see the approximation qualities of random $p$ baselines in our experiments). Our method computes a small, representative set of policies covering the entire spectrum of fairness criteria. This allows decision-makers to select confidently from this set, without worrying about suboptimality under other potential choices of $p$

3. While theoretically sound ... limit the scalability to large MDPs.

• The referenced scenario ($\alpha = 1.0$) means that the computed portfolio achieves perfect optimality across the entire range of $p$. Our algorithm provides a flexible trade-off: selecting smaller $\alpha$ will reduce the oracle calls, thereby enhancing scalability to large MDPs while still maintaining approximation guarantees. For example, in the same experiment, the portfolio constructed with 7 oracle calls achieves 0.982 optimality.

  Furthermore, we'd like to respectfully highlight that to the best of our knowledge, our work is the first to explicitly consider the number of oracle calls required for constructing portfolios in MORL. Hence, we believe explicitly counting and reporting oracle complexity (along with a theoretical bound) represents a strength of our work rather than a weakness.

4. The RL algorithm used, hyperparameters, and the experimental settings (ESR vs SER).

• We thank you for this comment. We respectfully note that the experimental details pointed out can be found in Section 5.2. For example, we used Welfare Q-Learning (Fan et al., 2022) for the taxi environment. For the other two environments, the feasible policy set $\Pi$ consists of finite pre-computed policies, which are selected according to the procedure detailed in Appendix B.1. Consequently, for these environments, Problem (3) is solved by simply enumerating the policies in $\Pi$ without needing additional RL algorithms. The finite $\Pi$ setting is discussed in the beginning of Section 4. We have also made the code to replicate our results available in the anonymous link (including hyperparameters) .

5. Comparisons to other MORL methods. How does this work differ from methods like Envelope [1], GPI [2], or PCN [3]

• [1] focuses on weighted linear objectives and learns a single policy, whereas we focus on $p$-means and compute a portfolio (multiple policies). [2] builds portfolios focusing on weighted linear objectives and does not offer guarantees on portfolio size or oracle complexity. [3] trains a single policy to approximate the Pareto front, which does not directly correspond to any social welfare function. To the best of our knowledge, our work is the first to (1) propose a multi-policy approach in $p$-means and (2) provide theoretical guarantees on portfolio size, approximation quality, and oracle complexity simultaneously.

  We conducted preliminary experiments comparing our method to a version of GPI[2]. The results indicate that our approach achieves significantly better approximation quality. For example, the approximation quality of the GPI portfolio can be as low as 35% of that achieved by our portfolio with the same size. Please refer to Table 1 in the anonymous link. We have also provided a theoretical explanation in Lemma 1, which shows why the weighted linear combinations that GPI focuses on lead to suboptimal results from the $p-$means perspective.

6. Bound on the heuristic algorithm's approximation factor

• The best bound we have on the heuristic algorithm's approximation factor is $\kappa$ (See Lemma 2 in the link). However, this is a generic bound that holds for all portfolios.

7. Do the approximation guarantees differ between SER and ESR?

• Our theoretical guarantees hold uniformly for both ESR ($v^{(1)}$) and SER ($v^{(2)}$).

We thank you for the insightful comments! Additional results are available in the anonymous link here

1. Why there is a need to find $\alpha$-approximation for p-value. Why not use previous MORL algorithms?

• We thank you for this important comment. Our work addresses the following limitations of previous MORL methods.

1. Current work on approximating the Pareto frontier scales exponentially with the number of reward functions. Furthermore, to the best of our knowledge, there are no known theoretical guarantees about the portfolio size, approximation factors or oracle complexity.

2. Approaches that explicitly incorporate a fairness perspective via social welfare functions (instead of Pareto front) assume that the right social welfare function is known and fixed. This overlooks the challenge that the ideal choice of the fairness parameter (e.g., $p$ value) is often unclear in advance. Selecting a policy optimized for an arbitrary $p$ can lead to poor outcomes under a different $p$ value.

3. Moreover, the connections between the Pareto frontier (as considered in the RL literature) and how this maps to social welfare functions is largely unclear. Please see (Hayes et al., 2022) cited in our paper for this discussion.

Our work addresses each of these limitations as follows:

1. We provide theoretical guarantees that polynomially bound both portfolio size and the number of oracle calls, and we empirically demonstrate this.
2. We ensure strong fairness guarantees with respect to $p$-means, a widely used class of social welfare functions.
3. Our approach computes a small yet representative set of policies that covers the entire spectrum of fairness criteria represented by $p \in [-\infty, 1]$. The decision-maker can confidently select from this concise portfolio, without worrying about suboptimality under other potential choices of $p$.

2. Comparison to other optimization or MORL algorithms.

• We conducted preliminary experiments comparing our method to a version of a well-known MORL algorithm, Generalized Policy Improvement (GPI), which builds portfolios by considering weighted linear combinations of objectives for multiple weights. The results indicate that our approach achieves significantly better approximation quality. For example, the approximation quality of the GPI portfolio can be as low as 35% of that achieved by our portfolio with the same size. Please refer to Table 1 in the anonymous link. We have also provided a theoretical explanation in Lemma 1 in the anonymous link, which shows why the weighted linear combinations that GPI focuses on lead to suboptimal results from the $p-$means perspective.

3. If the model is perfectly known ... is there still a need to use MORL?

• Indeed, if the exact choice of the social welfare function (i.e., the exact value of $p$) were already known and fixed, computing a single optimal policy would suffice, and there would be no need for constructing a portfolio. As noted above, we address a fundamentally different scenario, where decision-makers are uncertain about the appropriate $p$ in advance.

4. The authors mentioned ``Small changes in p can sometimes ... Can we directly model or optimize the policies given different p?

• The selection process refers to the challenge a decision-maker faces when trying to choose an appropriate social welfare function (parameterized by $p$) and its corresponding optimal policy in advance.

  As suggested, we could incorporate $p$ as an additional input to the policy. While this is an appealing direction, this policy again assumes that the decision-maker knows the desired $p$ at deployment, making it challenging to apply in our setting where the right choice of $p$ is unclear.

5. Extension to a multi-agent setting.

• We thank you for this interesting idea. Our work explicitly assumes a centralized decision-maker who selects a policy to balance the outcomes across multiple stakeholders. Thus, addressing multi-agent scenarios falls beyond our current scope. Nevertheless, we agree that extending our ideas to such settings is an exciting future direction.

6. Other social welfare functions are not discussed.

• We thank you for this comment. Although our approach addresses $p$-means only, we emphasize respectfully that this represents a rich and theoretically justified class of social welfare functions (see page 1, right column, lines 23–33 for our discussion).

7. To select the policies, the authors assumed the utility can ... under different p-value.

• In our setting, each stakeholder $i$'s utility is defined as the sum of rewards along a trajectory, $\sum_{h=1}^{H} R_i(s_h, a_h)$, which is a standard assumption in MORL. For a fixed $p$, Problem (3) can be solved using existing RL methods to find a welfare-maximizing policy (see also Section 3.2, lines 190–195).