Navigating the Social Welfare Frontier: Portfolios for Multi-objective Reinforcement Learning
Authors: Cheol Woo Kim
Jai Moondra
Shresth Verma
Madeleine Pollack
Lingkai Kong
Milind Tambe
Swati Gupta
Venue: ICML 2025 poster (2025)
Keywords: Reinforcement learning
multi-objective optimization
p-means aggregation
Primary area: reinforcement_learning->planning

Abstract: In many real-world applications of Reinforcement Learning (RL), deployed policies have varied impacts on different stakeholders, creating challenges in reaching consensus on how to effectively aggregate their preferences. Generalized $p$-means form a widely used class of social welfare functions for this purpose, with broad applications in fair resource allocation, AI alignment, and decision-making. This class includes well-known welfare functions such as Egalitarian, Nash, and Utilitarian welfare. However, selecting the appropriate social welfare function is challenging for decision-makers, as the structure and outcomes of optimal policies can be highly sensitive to the choice of $p$. To address this challenge, we study the concept of an $\alpha$-approximate portfolio in RL, a set of policies that are approximately optimal across the family of generalized $p$-means for all $p \in [-\infty, 1]$. We propose algorithms to compute such portfolios and provide theoretical guarantees on the trade-offs among approximation factor, portfolio size, and computational efficiency. Experimental results on synthetic and real-world datasets demonstrate the effectiveness of our approach in summarizing the policy space induced by varying $p$ values, empowering decision-makers to navigate this landscape more effectively.

Navigating the Social Welfare Frontier: Portfolios for Multi-objective Reinforcement Learning
Cheol Woo Kim
Jai Moondra"
2
Shresth Verma
Madeleine Pollack3 3 Lingkai Kong" Milind Tambe 14
Swati Gupta
Abstract
This setting, which is often modeled using multi-objective reinforcement learning (MORL), arises in many RL applica- tions, such as fair resource allocation in healthcare (Verma et al., 2024a), cloud computing (Perez et al., 2009; Hao et al., 2023) and communication networks (Wu et al., 2018; Chen et al., 2021). Recently, with the rise of large language mod- els (LLMss, reinforcement learning from human feedback (RLHF) techniques that reflect the preferences of hetero- geneous individuals have also been explored (Chakraborty et al., 2024; Zhong et al., 2024; Park et al., 2024).
In many real-world applications of reinforcement learning (RL), deployed policies have varied im- pacts on different stakeholders, creating chal- lenges in reaching consensus on how to effec- tively aggregate their preferences. Generalized p-means form a widely used class of social wel- fare functions for this purpose, with broad applica- tions in fair resource allocation, Al alignment, and decision-making. This class includes well-known welfare functions such as Egalitarian, Nash, and Utilitarian welfare. However, selecting the appro- priate social welfare function is challenging for eeciision-makers as the structure and outcomes of optimal policies can be highly sensitive the choice of p. To address this challenge, we study the concept of an a-approximate portfolio in RL, set of policies that are approximately optimal across the family of generalized p-means for all I 1. We propose algorithms to compute such portfolios and provide theoretical guarantees on the trade-offs among approximation factor, portfo- lio size, and computational efficiency. Experimen- tal results synthetic and real-world datasets demonstrate the effectiveness of our approach in summarizing the policy space induced by varying values, empowering mecision-makers to navi- gate this landscape more effectively.
Preference aggregation in such scenarios is often achieved by choosing social welfare function, which takes the utilities of multiple stakeholders as input and outputs a scalar value representing the overall welfare (Yu et al., 2024; Cousins al., 2024; Verma et al., 2024a; Fan et al., 2022; Zhong et al., 2024; Park et al., 2024: Chakraborty et al., 2024). However, selecting the appropriate social welfare function is a nontrivial task. Different functions encode distinct fairness criteria, and the resulting policies can lead to vastly different outcomes for stakeholders depending on the choice of the social welfare function.
In this work, we focus on class of social welfare func- tions known as generalized p-means, widely used class of social welfare functions in algorithmic fairness and social choice theory. Each choice of represents a distinct notion of fairness, and the y-means unify commonly used welfare functions such as Egalitarian welfare (p -co), Nash wel- fare (p = 0) and Utilitarian welfare (p 1), providing smooth transition between these principles. Notably, this is known to be the only class of social welfare functions that satisfy several key axioms of social welfare, such as mono- tonicity, symmetry, and independence of scale (Roberts, 1980; Moulin, 2003; Cousins, 2023; Pardeshi et al., 2024).
1. Introduction
In this paper, we study a reinforcement learning (RL) set- ting where deployed policy impacts multiple stakeholders in different ways. Each stakeholder is associated with unique reward function, and the goal is to train a policy that adequately aggregates their preferences.
In practice, the right choice of p is often unclear in advance, and the decision-make must understand how policies vary with p in order to make informed choices about which p (and thus which policy) to adopt. Small changes in p can some- times lead to dramatically different policies, and selecting a policy optimized for an arbitrary p can lead to poor out- comes under a different value. Despite these challenges, much of the existing work assumes a fixed social welfare
'Equal contribution 'Harvard University, Cambridge, USA "Georgia Institute of Technology, Atlanta, USA 'Massachusetus Institute of Technology, Cambridge, USA *Google Deepmind. Correspondence to: Cheol Woo Kim <ewkim @ seas, harvard.edu>.
Proceedings of the 42nd International Conference Machine Learning. Vancouver, Canada. PMLR 267, 2025. Copyright 2025 by the author(s).

---

Navigating the Social Welfare Frontier
Policy
our contributions as follows:
Policy
Policy
1. We propose Algorithm P-MEANPORTFOLIO (Algo- rithm 1) to compute a finite portfolio of policies that is a-approximate for the generalized p-means objectives for any value of 1. We provide theoretical guaran- tees, including an upper bound on the portfolio size and the number of MDPs solved to optimality, both expressed in terms of the approximation factor o.
(Nomallzed)) Score
0.-
0.0
Stonde
12t Gomplird
Drobhate
Ael
2. We introduce lightweight heuristic BUDGET- CONSTRAINEDPORTFOLLO (Algorithm 3) that reduces computational costs compared to Algorithm p-MEANPORTFOLIO while maintaining high-quality portfolio generation.
(anaaaaiddd Score
0.99
3. We theoretically show that the search for an optimal policy for given p-mean can be efficiently warm-started using the optimal policy for a different p-mean.
0.90
Ages
21-30
32-40
43-50
Ages
4. We evaluate our approach on three different domains, spanning synthetic to real-world problems. Our results show that a small portfolio can achieve near-optimal performance across all p S 1. Moreover, the heuristic BODDETT-ONSTTRINEDDDPO
Figure 1. Portfolio of three policies for the healtheare intervention setting (see Section 5 for details), obtained using Algorithm with 0.60. The har plots show total rewards induced by each policy across different education (top) and age (hottom) brackets. "score" of 1.0 corresponds to baseline policy (not shown in the figure) used for comparison. The three policies impact various education and age brackets differently, offering a theoretically sound and diverse set of options for decision-makers.
constructs portfo- lios that closely match those produced by Algorithm p-MEANPORTFOLIO, while significantly reducing the computational cost.
The literature in RL with multiple stakeholders has primarily focused on optimizing policies for given choice of com- posite objective. However, this work shifts the focus toward constructing a small set of policies with theoretical guar- antees. This approach better captures the trade-offs within the actionable policy space, rather than relying on modeling choices on how these objectives should be formulated.
function and hence fixed value of p is given (Hayes et al., 2022).
To address this challenge, we propose a method to compute a small yet representative set of policies that covers the entire spectrum of faimesss criteria represented by p S 1. Our main algorithm, D-MEAAPORTTOLLOO, sequentially selects finite p values starting from -o to 1. These values are chosen so that the optimal policies at these points sufficiently cover the entire range of p < 1 for a given approximation factor a. We also propose a computationally efficient heuristic algorithm, which adaptively selects the next p value from the intervals formed by previously chosen p values.
1.2. Example
An illustrative example we consider in this work is a public health application, where the staff of a healthcare orga- nization aims to train an intervention policy for multiple beneficiaries under limited budget (Verma al., 2024a). This setting can be captured by restless multi-armed bandits (RMABs) (Whittle, 1988), which model sequential resource allocation problems under budget constraints. In this con- text, each beneficiary is associated with a state variable representing their level of engagement with the healthcare program, and the overall state the problem is the con- catenation of the states of all beneficiaries. At each time step, policy determines which beneficiary to intervene on, subject to the budget constraint. Depending the reward function used to train policy, different -ocoo-eemoga groups among the beneficiaries can be prioritized. For ex- ample, one reward function might encode the preference to prioritize older populations, while another reward func- tion might encode the preference to prioritize low-income
The portfolios provide structured summary of approxi- mately optimal policies, allowing decision-makers to navi- gate the implications of different p values efficiently. The decision-make can review the impact of the choice of p on the structure of policies, on relevant dimensions of interest, and make an informed choice about which policy to deploy.
1.1. Summary of Contributions
In this paper, we explore the concept of a-approximate port- folios for preference aggregation in MORL. We summarize
2

---

Navigating the Social Welfare Frontier
populations. The decision-maker (e.g., healthcare organiza- tion staff) must train a policy that balances these conflicting objectives.
A more refined notion of portfolio similar the one we study is the concept of convex coverage sets. However, this concept is limited to weighted linear combinations of re- ward functions (Roijers et al., 2013) and does not account for p- pe-ms As a result, existing MORL methods, whether based on the Pareto frontier or weighted linear combinations, do not provide guarantees with respect to y-mean welfare functions. We include additional discussion comparing our method with several well-known MORL algorithms pro- posed in (Yang et al., 2019; Reymond et al., 2022; Alegre et al., 2023; Yu et al., 2024) in Appendix C.
See Figure for demonstration of portfolio generated using the proposed method. The portfolio consists of three policies, each affecting stakcholders differently based on age and education levels. This perspective helps staff understand the trade-offs between operational choices. For details on the experiment, refer to Section 5.
2. Related Work
Portfolios in Optimization. In the optimization literature, (Drygala et al., 2025) studied portfolios with stochastic guar- antees for fixed objectives, Recent work in approximation algorithms also explores the notions of small-sized portfo- lios that approximately optimize class of social welfare functions (Gupta et al., 2023; 2025; Goel and Meyerson, 2006; Golovin et al., 2008; Chakrabarty and Swamy, 2019), by exploiting the combinatorial properties of facility lo- cation, scheduling and set cover problems. While these works operate in well-structured combinatorial settings, our work addresses significantly more complex landscape of RL where the policy space is vast and computing optimal policies is inherently challenging. This necessitates novel algorithmic and theoretical advancements to efficiently con- struct portfolios with strong guarantees.
Social Welfare Function and RL. In RL with multiple stakeholders, various social welfare functions have been plored, including generalized Gini-Welfare (Yu et al., 2024; Cousins et al., 2024), p-means (Verma et al., 2024a; Fan et al., 2022; Cousins et al., 2024), proportional- et al., 2024), Nash welfare (Mandal and Gan, 2023), among others. (Alamdari et al., 2024) investigated ordinal social welfare functions rather than cardinal ones.
(Ju
related line of work has emerged in RLHF for LLMs, where social choice theory has been used to aggregate mul- tiple reward models. For example, approaches leveraging Nash welfare (Zhong et al., 2024), a-fairness (Park et al., 2024), and Egalitarian welfare (Chakraborty et al., 2024) have been proposed. However, in both RLHF and broader multi-stakeholder RL, existing works typically assume that a fixed social welfare function is given and focus on comput- ing the corresponding optimal policy (Hayes et al., 2022). As result, these methods do not offer guidance for settings where the appropriate choice of social welfare function is unclear in advance.
3. Preliminaries
In this section, we provide preliminaries on MORL, p-mean social welfare functions, and portfolios.
3.1. Multi-Objective Reinforcement Learning
We consider multi-objective Markov decision process (MDP), defined by the tuple M = (S. P.R R (Ro)E where S denotes finite state space, A de- notes finite action space, and P S x A - As is the transition probability. Additionally, we assume that we start in fixed initial state $1 E S and H is the time horizon. In the specific MORL context we consider, there are N distinct stakeholders, each associated with a reward function R₁ : S x A + Ryo for i E [N]. A policy π S x [H] + A(A) defines a distribution over actions at given time h E [A]]. We use r (s1, 01;--.; 8H) to de- note trajectory, which is the sequence of states and actions from time to H. Throughout, we assume that all reward functions are bounded:
Portfolios in MORL. In the broader MORL literature, the concept of portfolios of policies is well-established. A com- mon approach is to compute solutions that approximate the Pareto front (Parisi et al., 2014; Van Moffaert and Nowé, 2014; Radulescu et al., 2019; Hayes et al., 2022). While the Pareto front provides a characterization of trade-offs between conflicting objectives, it does not assume a specific set of social welfare functions. This generality, while pow- erful, presents challenges in practical multt--ttakeholdr set- tings. That is, the Pareto front does not directly correspond to any specific notion of welfare or utility, making it diffi- cult to interpret the societal implications of these policies. Furthermore, without an explicit scalarization function to aggregate preferences, decision-maker must choose among Pareto-efficient policies without clear guidance on how to weigh the trade-offs, which is often critical in real-world applications where diverse preferences must be aggregated into a single deployable policy. Additionally, the Pareto front is typically large, making it prohibitively expensive to compute practice (Hayes et al., 2022).
Assumption 3.1 (Bounded Reward). There exist strictly positive scalars U, L such that L S R₂(-) S U for all E [N]. We call k == U/L the condition number of rewards.
The N stakeholders could represent different entities de- pending on the application; for example, different con-
3

---

Navigating the Social Welfare Frontier
stituent demographies of democracy, stakeholders in company, simply just abstract differences in values or
et al. (2022), Roijers al. (2013), Radulescu al. (2019), Agarwal et al. (2022), and Fan et al. (2022). While these aggregation rules are often studied independently in MORL, our work provides unified framework applicable to both methods. We show that the proposed algorithms apply to both settings leveraging similar theoretical foundations.
preferences.
3.2. Social Welfare Function
We consider the following family of social welfare functions p) 18 - R~o called the generalized p-mean. It is defined for each E [-o0, 1] and strictly each positive vector x = (I1..... 2N) E R as follows:
3.3. Portfolio of Policies for All p-means
In this section, we introduce the key definitions for portfo- lios. For brevity, we denote the maximum value function
minje[N] Zz
if p -0;
c. [-00,, 1] + IR defined as v._ v := max w(9) (T.)).
1/p
well When é and II are clear from context, denote the optimal policy for v (9) (..) as TT.
1
pf $ 03,
f(x,p)-
N
M
) Given a S 1, ag- gregation rule l E (1, and an approximation factor a E (0, 1). a policy π 11 is an a-approximation to the ag- gregation function (:p)) p) if the value o(()) (IT, p) achieved by iT is within factor of the maximum achievable value of (0 (..p) p) by policies in II, that is,
Definition 3.3 (a-approximation))
I/N
pf O.
(E[N)
We also provide an illustrative example in Appendix B to provide the intuitive impact of various p-mean objectives. We will use the following monotonicity property:
(1() (T. 2 a x max (00 (' = x v. 2 (p)-
x'Ell
Lemma 3.2 (Theorem 1, Chapter 3.3.1 (Bullen, 2003)). For all strictly posilive vectors x E B and for all p,q S 1 with < q, we have f(x. p) S fxx,4).
When and II are clear from context, we say for brevity that is an a-approximate policy for p. Definition 3.4 (Portfolio). Given aggregation rule & E {1,2} and approximation factor a E (0, set of policies IT' C IT is called an a-approximate portfolio for aggrega- tion functions v(9) if for each p S 1, there exists a policy in II' that is an a-approximation 2i()) (..p).
The generalized p-means provides a method to aggregate heterogeneous preferences by assigning a scalar value to any policy π. We focus on two aggregation rules, denoted by E (1, that have been previously proposed in the literature. Each combination of an aggregation rule & E {1,2] and parameter p defines specific aggregation function, denoted as (.Pp) Given a trajectory T = ($), .I,...,......................... SH, aH), => [sh,, an), i E [M. represent the total
4. Portfolio Algorithms
In this section, we present our main algorithmic and theoret- ical results. Before presenting the details of our proposed method, we first define the notion of an oracle, which serves as a key component in our algorithm and analysis. Recall that for fixed p. aggregation function o.9) (.,p), E (1, (1) and given set of policies II, the associated welfare max- imizing policy can be obtained by solving the following problem:
let G.(T) = R= reward over the trajectory, and G(r) E R the vector with GT( as its ith entry. The aggregation functions are defined as follows:
( (T.p)) E,wxx [f(G(T),
(T, = -[ (G()),
(2)
(e)
(p)
max (8) p).
(3)
In the MORL literature, (:)()) p) is referred to as pected scalarized returns (ESR), while (.)) p) is known as scalarized expected returns (SER). In general, ESR is preferred when the expected total reward from a single exe- cution the primary focus, whereas SER more suitable when policies are executed multiple times and rewards ac- cumulate over iterations. Computing the optimal policy for (f9) (c,p) requires specialized algorithms different from standard RL methods, which are not directly applicable. For example, (Fan et al., 2022) and (Agarwal et al., 2022) de- veloped algorithms for z (.)().))) p) and u(() (., P). respectively. More detailed comparisons between these scalarization tech- niques and their solution algorithms are available in Agarwal
The algorithms we develop assume that (3) can be solved, and we refer to each instance of solving (3) as an "ora- cle". This terminology is used to facilitate the discussion of oracle complexity, which quantifies the number of times Problem (3) must be solved to construct portfolio.
If IT is defined as the set of all possible policies in the MDP, as in the standard RL setting, each oracle call can be compu- tationally expensive. Moreover, achieving exact optimality
'The a-approximation we refer to is distinct from the a- fairness mentioned in Section 2. To avoid confusion, from this point onward, all instances of a will exclusively refer to the ap- proximation factor.
4

---

Navigating the Social Welfare Frontier
Algorithm J-MEANPORTFOLOOMMM.LC.
the portfolio size [TT and the number of oracle calls solve (3). The full proof is provided in Appendix A.
input (i) MDP M A,, (Ri) with N reward functions, (ii) feasible set of policies II for M, (iii) aggregation rule é E {1, 2}. and (iv) desired ap- proximation factor a E (0,1)
Theorem 4.1. Given an MDP M with N reward functioon with condition number K, set II of feasible policies, an aggregation rule E {1,2], and a desired approximation factor a E 10, Algorithm p-MEANPORTFOLAN returns an a-approximate portfolio of policies I1' for the set of aggregation functions (vl()..)) p 1). Further,
output a-approximate portfolio IT' for the set of aggrega- tion functions (-) ().p). p - assuming oracle access to solve problem (3)
lm[1/a] and t 0 2: initialize portfolio 11' + 0
1: initialize Po
Iu N
1. The portfolio size
3: while Pt < 1 do
( In [m(l/a))
[IT' =0
4: add pp arg max en (1, to IT
5: Pr-1 LINESEARCI(( .P,
6: f 1
2. The number of oracle calls by the algorithm is upper bounded by
7: return II'
δ ( ( [Inn)]
In(1/a) m
Algorithm 2 LINESEARCH(" II)
input (i) aggregation function ((() (ii) some E (-o0, 1) (ii) feasible set II of policies, and (iv) desired approxi- mation a E (0, 1)
where Ô hides all lower order terms.
Here, explain the high-level ideas behind the algorithm. The algorithm iteratively chooses increasing sequence of p values Po < PI < ... < PK using a line search sub- routine (Algorithm 2). It ensures that Tp. is a-approximate for all E [pt, 1t and that Tpo is a-approximate for all p E po].
output 8" > such that `p == arg max.maxrre en ( (T',p) is an a-approximation for (l(()))) for all & E [p, b+]
a + 4-p and b
2: initialize π = arg max max m (T',
3: while ( a) < a Ux (b) do
(1)
4: qt atb
Line search. The line search subroutine works as follows: given a p 1, it seeks to find some b" p such that Tp is an a-approximation for all g b"]. To achieve this, it maintains lower and upper bounds a, b on d' with S < b S 1 and iteratively refines these bounds.
5: if (0 2 va v. (q) then
6: atq
7: else
8: b-q q
9:
return b
At each iteration, the algorithm checks whether (T a) 2 au! (P) (line 3). If this condition holds, then by the monotonicity property of p-means (Lemma 3.2), we must have:
for Problem (3) may not always be feasible due to limita- tions in RL algorithms. This means that when measuring the approximation factor of a policy π with respect to an aggre- gation function o') (-, p). the maximum value (4) (p) might not be attainable or computable. In this case, approx- imate o as the value achieved by applying the given RL algorithm. This approach measures the approximation factor relative what is achievable using the algorithm at hand.
(Tp: (99 (Tpp a) 2 v. (b).
Then, this holds for any E [a, b), implying that T. is a- approximate across this interval. Therefore, this procedure can safely output 5* = b. This establishes the correctness of the algorithm, as the line search successfully identifies the next p value if it terminates.
In practice, II may be small set of pre-trained policies, particularly in scenarios where training new policies is in- feasible. In such cases, Problem (3) can be solved efficiently by enumerating over the policies π II and using Monte Carlo simulations to estimate the value ((() (x,
Bounds a, b are updated in each iteration follows (lines 4-8): we query the value (()) (q) for ط+h As before, if (Tpp a) exceeds a times ( (q). then we know that Tp must be a-approximation for any value in (a, g). and the lower bound a can be tightened as + q. Otherwise, the upper bound can be tightened as b <- g.
4.1. Algorithm >-MEANPORTFOLLO
In this section, we introduce p>MEANPORTFOLIO (Algo- rithm 1), which constructs an a-approximate portfolio II' for all p E 1. In Theorem 4.1, we establish formal bounds
However, as we show in the formal proof in Appendix A, we can in fact ensure faster convergence by slightly modi- fying this step. Instead of checking whether (Tpp a) 2
5

---

Navigating the Social Welfare Frontier
a v/ (4). we check the stronger condition vl (Tp, a) 2 vā x uh (q). Since vā 2 a, this stricter condition does not affect correctness but accelerates convergence.
putationally infeasible, particularly since evaluating the ob- jective for any new p would require additional oracle call. Instead, SENDDGETCCOOSTRRIIEDDRRRREE imates this worst-case p using only the information gathered from previous iterations, inspired by the theoretical princi- ples of p- p-MMENPORTFOLLOO
approx-
Oracle complexity. We briefly sketch how we bound the oracle complexity (i.e., number of oracle calls to solve Prob- lem (3)) by bounding the number of oracle calls in each run of LIRESEARCH. As discussed, in each iteration of the line search algorithm, the distance b - is cut by half since either b or a are updated to a+t 2 As we show in Lemma A.8, this implies that after j iterations of LINESEARCH, the v10 (b) is upper bounded by (K, NN, a) x x2-5, where "y (a)
After iteration t, the previously selected p values partition the interval [oc, 1] into at most + 1 disjoint intervals:
-00 < Pm(1) < Pm(2)) < ... < Pm(()) S 1.
ratio
Rather than solving Problem (4) exactly to pinpoint the worst-case p. we instead aim to identify the interval where the approximation quality is the weakest.
& is some function of condition number KG dimension NN, and approximation factor a. By deriving lower bound on this ratio, we derive an upper bound on the total number of iterations j.
First, we rewrite Equation (4) by decomposing the mini- mization over the intervals:
4.2. Heuristic under a Budget Constraint
max a0 (TT
In p-MEANPORTFOLIO, we provide guarantees on the ap- proximation factor a. However, achieving these guarantees may require a large number of oracle calls to solve Prob- lem (3) across different values of p, which can be impractical when computational resources are severely limited.
Q(I)) ~ min iE(t-1] pelpmes)Pmeet)
min
(
(p)
The only approximation introduced in this decomposi- tion arises from neglecting the intervals [-o0, Pmt()) and [Pm(t), 1]. To cover the first interval, we can initialize the algorithm with a sufficiently small pl. guarantceing that the approximation factor remains well-controlled in this region (Theorem 4.1). The second interval is covered by explicitly setting p2 1.
One way to reduce oracle calls is to select a smaller a. However, while Theorem 4.1 provides an upper bound on the number of calls required, the exact number is difficult to determine in advance, making it challenging to balance computational cost with portfolio quality. Alternatively, budget on the total number of oracle calls can be imposed along a, but this introduces its own trade-offs: if a is too large, the algorithm may exhaust calls prematurely, leaving parts of the p range unexplored; a is too small, it may progress to p- = too quickly, missing opportunities to refine the portfolio.
For each interval Pm)(++))) we compute its interval approximation factor, denoted as u(l), using the following sequence of approximations:
max e(() (T,P)
min PE (e((mm))-Pp((t)))
(p)
(2) (TTmay
To address this limitation, we propose the heuristic BUDGET- CONSTRAINED (Algorithm 3), designed for scenarios with strict budget K on oracle calls. Unlike P-MMEANPRTFOLLOO, which selects p values in a mono- tonically increasing order from -x to 1, this algorithm dynamically refines the search space based on observed ap- proximation performance. It greedily targets regions where the approximation factor is likely to be weakest, ensuring efficient use of the limited oracle budget.
min pe pElpmct Poittn)
26 ('((p)
m(() pTomtt Pmm(++1)) = u(I).
Vy ( (Pm(141))
The first approximation follows from the assumption that each interval is well-covered by the policy trained at its left endpoint, similar to the approach used in p- p-MMENPORTTFOLOO The second approximation is justified
First, we describe the ideal version of this greedy approach. After oracle calls, let II; denote our current portfolio. The objective at each step to identify the worst-case p value where the approximation quality of II, is the lowest by solving the following problem:
under the assumption that (F(((F)))))))))) is monotonically
v!'(p)
decreasing function of p in the interval [Pm(()) Pm)(+
Note that this assumption holds exactly when the inter- val is sufficiently small, as this function is continuous in (Lemma A.8) and attains its maximum value (= 1) at p = Pmn()-
max (00) (00
)(I)) = min
(4)
To select the next p value, we identify the interval with the worst (smallest) approximation factor and choose its
However, solving this optimization problem exactly is com-
6

---

Navigating the Social Welfare Frontier
Algorithm 3 BUDGETTCONSTRANDDOORTOOS
two baseline approaches. Suppose p-MEANPORTFOLIO generates portfolio of size K. The first baseline se- lects K values of uniformly random from [po. 1] and computes their optimal policies, where Po matches that of p-MEANPORTFOL.O.. The second baseline randomly sam- plcs K policies from I1. Since both baselines involve ran- domness, we generate 10 independent baseline portfolios for each setting and report the average performance across these runs. Finally, we with budget K.
input (i) MDP M = (S, = (Ra),e()) with N
reward functions, (ii) aggregation rule E 2]. (iii)
feasible set of policies IT for M. (iv) budget K, and (v)
initial po
output A portfolio IT' 1: Initialize IT' <-g 0
2: for t = 1 to K do
3: i = 1 then
4: Pt + Po
5: else if t. = 2 then
To evaluate each portfolio 11', compute its approximation factor Q(II') as defined in Equation (4). Since computing this value exactly is infeasible, we approximate it using a grid search over p. referring to it as the actual approxima- tion. We also compare the number of oracle calls made by p- M-MAANPRRTFOLLO and BUDGETCCNSTRAINEDPOOTT L.O. This procedure is repeated for varying values.
6: Pt 1
7: else
8: compute u(() for (m)()))) AE [t 2-22 2]
9: Pt f- P 11), 1" = arg mi u(!)
2 10: Add policy Tpp ;- arg max (T. to II'
11:
return IT'
5.2. Environments
midpoint:
We conduct experiments across three domains, ranging from synthetic real-worle settings, as described below.
Pmlll + Pm((++)) +1)
P++1
1" == arg mi min
2
Taxi Environment. We consider synthetic setting based the works of Dietterich (2000); Fan et al. (2022). The taxi environment consists of grid world where taxi driver serves passengers across N = 4 different source-destination pairs. When the agent drops off passenger at their destina- tion, it earns a reward corresponding to that route. However, since the taxi can only carry one passenger at a time, it must decide which route to prioritize. A fair agent should serve all source-destination pairs equitably, avoiding the neglect of more challenging routes. We train p-mean maximizing policy using Welfare Q-Learning (Fan et al., 2022). Finally, we experiment on e()) and define II as the set of all possible policies in the MDP.
4.3. Warm-Start for Computational Efficiency
Both p-MEANPORTFOLIO and BUDGET- CONSTRAINEDPORTFOLI. involve repeatedly solving Problem (3) for different p values. To accelerate this process, warm-starting is natural choice. Specifically, once the optimal policy Tp for max u(() (T, p) is found, it can be used as a warm-starting point for solving max (TT, 4). q > p, if q and are close. Proposition 4.2 below offers a theoretical justification for this approach by showing that e(()) (Tp. 9) is close to the optimal value 2i (0) (q) whenever p and q are close. The proof is deferred to Appendix A.
Proposition 4.2. Let q > p. For E (1,2), the following inequality holds:
Resource Allocation after Natural Disaster. In this syn- thetic setting, we have a set of N 12 clusters of neigh- borhoods impacted by a natural disaster. Each cluster is characterized by average household income (high, middle, low), proximity to critical infrastructure (near, far), and pop- ulation density (high, low), along with distinct post-disaster resource needs. Over a time horizon, a decision-make must decide how to allocate a limited number of resources to these 12 clusters. The reward function for each cluster is the aver- age of the fraction of unmet need and the fraction of total aid allocated to that cluster. We conduct experiments using (2(2) with IT defined as finite set of pre-trained policies.
1 (q)- - (i (Tp, 2) S (qg-))HHkhi
where up denotes the policy arg max maxxen (0 (0.
5. Numerical Experiments
In this section, we present the results of our nu- merical experiments. Additional details of the ex- perimental setups and the environments are provided in Appendix E. The code for our experiments can be found at https:://gitii hww.:hhb.ccccceecoooooeeeeee cttp/uuwcccoo/////oo.....aaaaa ppppooxmttttoo---oottoooo-----s jaimoondra/
Healthcare Intervention. We consider real-world health- care intervention problem, modeled as an RMAB problem described in Section 1.2 (Verma et al., 2024b). ARMMAN (ARMMAN, 2024), an NGO based in India, runs large-scale maternal and child mobile health programs. One of their initiatives delivers critical health information via weekly
5.1. Experimental Setups
For a given a and MDP environment, we first compute a portfolio using p and compare against
7

---

Navigating the Social Welfare Frontier
automated voice messages. To enhance engagement, lim- ited number of beneficiaries receive direct calls from health workers each week, with call assignments determined by policy, The problem involves N = 59 reward functions, each prioritizing different socio-demographic groups among the beneficiaries. We conduct experiments using v(2), where consists of a finite set of pre-trained policies, All experi- ments are strictly secondary analyses and adhere to ethics board approvals; for further discussion, refer to impact statement.
Table 1. comparison of actual approximation ratios across vari- ous portfolio sizes for w-MEANPORIFOLIO, random policy sam- pling, and random p sampling. p-MEANPORTFOLIO consistently outperforms the other two methods across all portfolio sizes and experiments.
Random
Random
Portfolio Size
P-MEAN- PORTFOLIO
Policy
Sampling
Sampling
Resource Allocation after Natural Disaster
0.706
0.534
0.832
0.904
0.568
0.890
0.999
0,591
0.892
5.3. Results
4
1.000
0.609
0.888
Table 1 presents comparisons of the approximation quality of p--EENPPRTTOLLL with random p sampling and ran- dom policy sampling baselines, while Table reports the number of oracle calls made by P-MEANPORTFOLI and the number of calls for
Healthcare Intervention
0.924
0.479
0.913
2
0.982
0.545
0.941
0.982
0.589
0.929
0.982
0.625
0.947
Note that by design, LIO is always the same as the portfolio size.
5
0.993
0.635
0.957
0.999
0.647
0,962
7
1.000
0.667
0.953
Size. The portfolios computed using Algorithm p-MFANPORTROL.OO remain small while achieving a very high approximation factor. Across all three environments, the portfolio size never exceeds 10, yet still attains an ap- proximation factor close to 1. This suggests that a small portfolio is sufficient to effectively cover the entire spectrum of p values 1.
Taxi Environment
0.66
0.24
0.66
2
0.61
0.31
0.61
3
0.97
0.54
0.65
0.87
0.71
0.67
10
0.99
0.60
0.65
BUDGETTCONSTRAANEEPPRROOOO serves as a strong alternative with good empirical performance.
Approximation Quality. The proposed algorithms achieve significantly better approximation quality than both bench- mark methods. In particular, p-MEANPORIFOLL generally attains the highest approximation quality, followed closely by BUDDGETCONSTRAANNDPPPTTOO.. in most cases.
Diversity. As we have shown in Figure in Section 1.2, portfolios can simplify policy deployment decisions by pre- senting small yet diverse set of policies. We also provide the entire p values chosen by (~MEANPORTFOLIO in Ap- pendix D, Table 4. We observe that the values are quite diverse, which corroborates the algorithm's 's objective to cover the entire p range only with these selected values. Figures and further illustrate how the outcomes of the optimal policies for different p values in the portfolio lead to varying impacts for the stakeholders. Importantly, these are not arbitrary policies but optimal policies for specific p values, with approximation guarantees extending to other ps as well.
and random p sampling occasionally outperform p-MEANPORTFOLIO. This is because p-MFANPORTFOLLIO selects policies solely to meet the input approximation factor a, but has no incen- tive or mechanism to surpass this approximation quality.
However,
In contrast, BUDGETCCONSTAANEEDPPRTTTO lizes the imput budget K, and strategically selects boundary points first (a small initial p followed by 1). When K is very small (I or 2), this initial heuristic strategy can provide more effective coverage across p < 1, explain- ing its occasional superior performance. Likewise, in rare cases where K 1, a randomly chosen p may happen to yield better coverage than the single policy selected by D-MEEAPORTHOLLO.
fully uti-
6. Conclusion
In this paper, we studied the concept of an a-approximate portfolio in MORL for generalized p-means. We proposed algorithm compute a-approximate portfolios and es-
Computational Efficiency. As noted earlier, p-MEANPORTFOL.O requires large number of ora- ele calls to produce high-quality portfolio. In contrast, BUDDETCCONTRRANNDPOORRER
'Here, we observe drop in the actual approximation factor of p- M--ANPPRRFOOLOO when the portfolio size 8. Although this portfolio is computed using = 0.9, its achieved approximation is slightly lower. This discrepancy is likely due to the inherent randomness the RL algorithm and the challenges of computing exact optimal policies in RI. settings, as discussed in Section 4.
achieves comparable quality while using significantly fewer oracle calls. This suggests that when computational resources are limited,
8

---

Navigating the Social Welfare Frontier
Acknowledgments
Table comparison of the numher of oracle calls and actual approximation ratios for p- M-MAAPPRRFOLLOO and BUDEETOON- STRAINEDPORTFOLIO across different portfolio sizes. While p-MEANPORTFOLIO often achieves slightly better approximation, requires significantly more oracle calls."
We thank NSF AI Institute for Societal Decision Making (AI-SDM) Award No. 2229881, ONR MURI N00014-24-1- 2742, and NSF CAREER 2239824 for their support.
BUDGETCONSTRAINER
Portfolio
P-MEANPORTFOLIO
Impact Statement
PORTFOLIO
Size
Oracle
Actual Approximation
Oracle
Actual
Our work studies the setting where a deployed RL policy impacts multiple stakeholders differently, a scenario that arises in various societal applications, including healthcare and LLMs. By summarizing the space of policies induced under different p-values, our proposed approach aims to assist decision makers in making informed and equitable choices, Furthermore, this work has the potential to stim- ulate discussions within the machine learning community about the complexities and pluralities of social welfare no- tions, and the importance of addressing them. However, our focus is limited p-means social welfare functions, which may not fully capture all dimensions of fairness in real- world scenarios.
Calls
Calls
Approximation
Resource Allocation after Natural Disaster
0.706
0.885
0.904
0.921
3
18
0.999
3
0.921
4
50
1.000
4
0.921
Healthcare Intervention
2
0.924
1
0.938
2
0.982
2
0.938
0,982
0,938
4
19
0,982
4
0.938
5
23
0.993
5
0.986
46
0.999
0.986
7
61
1.000
7
0.993
Taxi Environment
Our experiments use real-world healthcare data provided by the NGO ARMMAN. These experiments strictly secondary analyses, with no real-world deployment of the proposed algorithm or baseline methods. All data usage complied with ARMMANs ethics board approvals, and data exchange and analysis followed their ethics review commit- tee's guidelines, including privacy, informed consent, and anonymization. All of the analyses is conducted close collaboration with ARMMAN.
0.66
0.66
2
30
0.61
2
0.61
44
0.97
0.92
118
0.87
0.90
10 144
0.99
10
0.92
tablished theoretical guarantees on the trade-offs among a, portfolio size, and the number of oracle calls. Addi- tionally, we presented theoretical analysis of warm-start techniques and developed an efficient heuristic algorithm. Our numerical experiments demonstrated that the proposed methods successfully compute compact portfolios that effec- tively capture the entire spectrum of values, empowering to make informed decisions.
This work belongs to the broader area of algorithmic decision-making, where deployment decisions can have real- world implications. We emphasize the importance of not relying on this study isolation. Responsible deployment requires comprehensive field testing and human oversight. Moreover, we acknowledge broader challenges inherent in algorithmic pacision-making including potential biases in data, inaccuracies in the underlying mathematical models, accountability issues, and concerns related to consent and privacy. Addressing these challenges is essential ensuring that algorithmic decisions are ethically sound.
References
Mridul Agarwal, Vaneet Aggarwal, and Tian Lan. Multi- objective reinforcement learning with non-linear scalar- ization. Proceedings of the 21st International Conference Autonomous Agents and Multiagent Systems, (AAMAS), page 917. International Foundation for Autonomous Agents and Multiagent Systems, 2022.
Parand A. Alamdari, Soroush Ebadian, and Ariel D. Pro- caccia. Policy aggregation. In The Thirty-eighth Annual Conference on Neural Information Processing Systems,

---

Navigating the Social Welfare Frontier
2024. URL httphhts//ppeereeeeee...too id=ybiUVIxJth.
in Theoretical Computer Science Conference (ITCS 2025), volume 325 of Leibniz International Proceedings in Informatics (LIPIcs), pages 46:1-46:15. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2025, URL https: / /drops dwgstuhlsll.oooo
Lucas N. Alegre, Diederik M. Roijers, Ann Nowé, Ana L. C. Bazzan, and Bruno C. da Silva. Sample-efficient multi- objective learning via generalized policy improvement prioritization. In Proceedings of the 22nd International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2023.
document /10. 4230 LIPICS. ITCS 2025.42255
Zimeng Fan, Nianli Peng, Muhang Tian, and Brandon Fain. Welfare and fairness in multi-objective reinforcement learning. arXiv preprint arXiv:2212.01382, 2022.
ARMMAN. Armman:
Advancing reduction in mortality and morbidity of mothers, children, and neonates, 2024. URL https::/aammaa..ee
Ashish Goel and Adam Meyerson. Simultaneous optimiza- tion via approximate majorization for concave profits convex costs. Algorithmica, 44:301-323, 2006.
P.S. Bullen. Handbook of Means and Their Inequalities. Mathematics and Its Applications. Springer Netherlands, 2nd edition, 2003.
Daniel Golovin, Anupam Gupta, Amit Kumar, and Kanat Tangwongsan. All-norms and all-I fiil-_p-norms approxi- mation algorithms. In IARCS Annual Conference on Foundations of Software Technology and Thcoretical Computer Science (2008). Schloss- Dagilss-DDgttuuhLLLbbiiii Zentrum für Informatik, 2008
Deeparnab Chakrabarty and Chaitanya Swamy. Approxima- tion algorithms for minimum norm and ordered optimiza- tion problems. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pages 126-137, 2019.
Swati Gupta, Jai Moondra, and Mohit Singh. Which Ip norm is the fairest? Approximations for fair facility location across all "p". In Proceedings of the 24th ACM Conference on Economics and Computation, page 817. Association for Computing Ma- chinery, 2023. URL https: /tt.///oiiio//// http://oooo.og/////////o 10g/10..00 1145/ 3597664.
Souradip Chakraborty, Jiahao Qiu, Hui Yuan, Alec Koppel, Dinesh Manocha, Furong Huang, Amrit Bedi, and Mengdi Wang. MaxMin-RLHF: Align- ment with diverse human preferences. In Proceedings of the 41st International Conference on Machine Learning, volume 235, pages 6116-6135 PMLR, 2024. URL ptttttss//proceee http///prceeee......ce//// .aa.gssmrr.pp..... .mlr.press/ 2235/chakrabort.g 4b. html.
Swati Gupta, Jai Moondra, and Mohit Singh. Balanc- ing notions of equity: Trade-off's between fair portfo- lio sizes and achievable guarantees. In Proceedings of the 2025 Annual ACM-SIAM Symposium on Discrete Algorithmss (SODA), 2025. URL sttps://arxiv. org/ abs 2112231133333
Jingdi Chen, Yimeng Wang, and Tian Lan. Bringing fair- actor-critic reinforcement learning for network utility optimization. In IEEE Conference on Computer Communications, pages 1-10, 2021.
Hao Hao, Changqiao Xu, Wei Zhang, Shujie Yang, and Gabriel-Miro Muntean. Computing offloading with fair- ness guarantee: deep reinforcement learning method, IEEE Transactions Circuits and Systems for Video Technology, 33(10):6117-6133) 2023.
Cyrus Cousins. Revisiting fair-pac learning and the ioms of cardinal welfare. In Francisco Ruiz, Jen- nifer Dy, and Jan-Willem van de Meent, editors, Proceedings of The 26th International Conference on Artificial Intelligence and Statistics, volume 206 of Proceedings of Machine Learning Research, pages 6422 6442, 2023. URL https: https:://rocceeeeee /ptp///doccce.....//// mlr.presss v206/ cousins23a html.
Conor F. Hayes, Roxana Rädulescu, Eugenio Bargiacchi, Jo- han Källström, Matthew Macfarlane, Mathieu Reymond, Timothy Verstraeten, Luisa M. Zintgraf, Richard Daze- ley, Fredrik Heintz, Enda Howley, Athirai A. Irissappane, Patrick Mannion, Ann Nowé, Gabriel Ramos, Marcello Restelli, Peter Vamplew, and Diederik M. Roijers. practical guide multi-objective reinforcement learn- ing and planning. Autonomous Agents and Multi-Agent Systems, 36(1):26, April 2022.
Cyrus Cousins, Kavosh Asadi, Elita Lobo, and Michael Littman. On welfare-centric fair reinforcement learning. Reinforcement Learning Journal, 1:1124-1137, 2024.
Thomas G Dietterich. Hierarchical reinforcement learning with the maxq value function decomposition. Journal of artificial intelligence research, 13:227-303 2000.
Peizhong Ju, Amob Ghosh, and Ness Shroff. Achieving fair- ness in multi-agent MDP using reinforcement learning. The Twelfth International Conference on Learning Representations, 2024. URL https: atttps://openrevie. net htte/foormmiidyyyooee
Marina Drygala, Silvio Lattanzi, Andreas Maggiori, Miltiadis Stouras, Ola Svensson, and Sergei Vassilvitskii. Data- Driv-D Solution Portfolios. In 16th Innovations
10

---

Navigating the Social Welfare Frontier
Debmalya Mandal and Jiarui Gan. Socially fair reinforce- ment learning, 2023. URL httpp:://axxii...oo. org/ abs/2208 12584.
Kristof Van Moffaert and Ann Nowé. Multi-objective re- inforcement learning using sets of pareto dominating policies. J. Mach. Learn. Res., 15(1):3483351, January 2014. ISSN 1532-4435.
Hervé Moulin. Fair Division and Collective Welfare. The MIT Press, January 2003.
Shresth Verma, Gargi Singh, Aditya Mate, Paritosh Verma, Sruthi Gorantla, Neha Madhiwalla, Aparna Hegde, Divy Thakkar, Manish Jain, Milind Tambe, and Apara Taneja. Expanding impact of mobile health programs: Saheli for maternal and child care. Al Magazine, 44(4):363-376, 2023.
Christos H Papadimitriou and John N Tsitsiklis. The com- plexity of optimal queuing network control. Mathematics of Operations Research, 24(2):293-305, 1999.
Kanad Shrikar Pardeshi, Itai Shapira, Ariel D. Procaccia, and Aarti Singh. Learning social welfare functions. In The Thirty-cighth Annual Conference on Neural Information Processing Systems, 2024. URL https: //openreviens net/ forum?? d=70d=tttr8nn
Shresth Verma, Niclas Bochmer, Lingkai Kong, and Milind Tambe. Balancing act: Prioritization strategies for LLM- designed restless bandit rewards, 2024a. URL https:
//arxiv.orgg/aaaa.e.aeaa 2408. 12112.
Simone Parisi, Matteo Pirotta, Nicola Smacchia, Luca Bascetta, and Marcello Restelli. Policy gradient ap- proaches for multi-objective sequential decision mak- ing. In 2014 International Joint Conference on Neural Networks (IJCNN), pages 2323-2330. 2014.
Shresth Verma, Gargi Singh, Aditya Mate, Paritosh Verma, Sruthi Gorantla, Neha Madhiwalla, Aparna Hegde, Divy Thakkar, Manish Jain, Milind Tambe, and Aparna Taneja. Increasing impact of mobile health programs: Saheli for maternal and child care. Proceedings of the AAAI Conference on Artificial Intelligence, 37(13): 15594-15602, Jul. 2024b.
Chanwoo Park, Mingyang Liu, Dingwen Kong, Kaiqing Zhang, and Asuman Ozdaglar. RLHF from heteroge- neous feedback via personalization and preference ag- gregation, 2024. URL https: pestps://araee /ttp///avvvvv///////////e org.orrg/ssss......o. / 2405. 00254.
P. Whittle. Restless bandits: Activity allocation in a chang- ing world. Journal of Applied Probability, 25:287-299 298, 1988. ISSN 00219002. URL. htttp://www /www. http://wwww.........oo jstor. htg/stable//224111
Julien Perez, Cécile Cermain-Renaud Balázs Kégl, and Charles Loomis. Responsive elastic computing. In Proceedings of the 6th International Conference Industry Session on Grids Meets Autonomic Computing, GMAC '09, page 5564. Association for Computing Machin- ery, 2009. URL https: //ooi. org 1145/ 1555301 1555311.
Qingqing Wu, Yong Zeng, and Rui Zhang. Joint tra- jectory and communication design for multi-uav en- abled wireless networks. IEEE Transactions on Wireless Communications, 173):2109-2121, 2018.
Runzhe Yang, Xingyuan Sun, and Karthik Narasimhan. A generalized algorithm for multi-objective reinforce- ment learning and policy adaptation. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, 2019.
Roxana Rädulescu, Patrick Mannion, Diederik M. Roijers, and Ann Nowé. Multi-objective multi-agent decision making: utility-based analysis and survey, Autonomous Agents and Multi-Agen Systems. 34(1):10, December 2019.
Guanbao Yu, Umer Siddique, and Paul Weng. Fair deep reinforcement learning with generalized gini welfare func- tions. In Autonomous Agents and Multiagent Systems. Best and Visionary Papers, pages 3-29, Cham, 2024. Springer Nature Switzerland.
Mathieu Reymond, Eugenio Bargiacchi, and Ann Nowé.
Pareto conditioned networks. In Proceedings of the 21st International Conference on Autonomous Agents and Multiagent Systems, (AAMAS), pages 1110-1118. International Foundation for Autonomous Agents and Multiagent Systems, 2022.
Huiying Zhong, Zhun Deng, Weijie J. Su, Zhiwei Steven Wu, and Linjun Zhang. Provable multi- callt--prtty reinforce- ment learning with diverse human feedback, 2024. URL https: ppps://arxivv
Kevin W. S. Roberts.
Interpersonal Comparability and So- cial Choice Theory. The Review of Economic Studies, 47(2):421-439, January 1980.
Diederik M. Roijers, Peter Vamplew, Shimon Whiteson, and Richard Dazeley. A survey of mulli--bjecciion sequential decision-making. J. Artif. lnt. Res., 48(1):67113, October 2013. ISSN 1076-9757.

---

Navigating the Social Welfare Frontier
A. Omitted Proofs
We include omitted proofs and various lemmas here.
A.1. Proof of Theorem 4.1
Our first lemma shows establishes the monotonicity of aggregation functions y(6) in Lemma A.1. For any fixed policy x E II, (1, p) is monotone increasing in for i E (1,2).
Proof. & 1: For any T n, Lemma 3.2 implies that f(G(T). is monotone increasing in p. Therefore,
0 a. p) E (
monotone increasing in p-
= 2: Denote Er [G()). Then the monotonicity of v.2) f(x,p) follows directly from Lemma 3.2.
The following corollary follows immediately: Corollary A.2. u (p) (p) max e09 (T, is monotone increasing in p for l {1.2).
The following two lemmas show that the p-mean for p -c is a-approximated by the po-mean where Po can effectively restrict [-Po, 1] when finding portfolios:
In N In(1/a]+ 80
Lemma A.3. Given vector R.y and E (0,1), 1), define po In(1/o]
In
Then,
f(x.-o0) -00) 2 a f(x,p( Ap Po-
Proof. Suppose 0 < x1 S ... S In, so that f(x, -00) minjelM] 2ÿ = T1. Given p S po, denote q = -p 2 Then, since
In In(1/a]
1/D
f(x.p)
iE[N]
1/2 Eje[N]
zy
1
1/9
N
JEENN]
99
1/4
we get
1/4
N/P
N1/po
I
a
2
x
[(x,P) P)
21
N
21
f(x,- -C)
or that f(x, -00 a. f(x. p).
Lemma A.4. Given MDP M with N reward functions, II of feasible policies. and approximation factor
1), denote Po Im[1aa. Then, for given aggregation rule l E (1,2), policy = arg max (Tt, Po) is an a-approximation for all S Po- That is,
in N
( (TO.P) 2 (8) (p)
max (0) (R,P) Vp S po xel
Proof. 8 1: From Lemma A.3, for all p S po. we get
v (1) (TO. p) 2 (()) -00
(Lemmaa A.1)
E [f(G] -c]]
(eqn.(1)
2 a E (G)()))
(Lemma A.3)
(1)) ( Po)
(eqn.(1))
a max (1) (T. Po) fell
a max (1) (T,
(Lemma A.1).
sell
The result for = 2 follows similarly and is omitted.
The following three lemmas establish guarantees on LINESEARCH:
12

---

Navigating the Social Welfare Frontier
Lemma A.S. Suppose LINESEARCH (Algorithm 2) on input vl0, p, II, returns b' (p, 11. Then, either bz or the policy π arg max satisfies
v1 (T.
S (b)
Va
a
Proof. If LLLNESEARCI( P, 11, ar) does not return b* = 1, then we must have that p-MEANPORTFOLIO enters the while loop (step 2) at least once. In particular,
<a <a (b)) va (b*).
This proves the first inequality. For the second inequality, notice that the algorithm terminates only when ( a) 2 u. (b*). As can be easily checked, the algorithm maintains the invariant 2 Therefore, by Lemma A.I,
e (T, by) y (T. 2 a (o
Lemma A.6. Algorithm LINESEARCH maintains the following invariant at all times: (1, 2 v vo (a).
Proof. Initially, p = a, and therefore ग := arg max o (T' satisfies v10 p) = uu u 2 Va us (p) since E 10.
Further, the algorithm only updates <- in step 2 when ( 2 va v. (g). Since 2 we get from Lemma A.1 that (.() (x, q) 2 ( a), thus finishing the proof.
Lemma A.7. Algorithm LINESEARCH input v( 1l, returns b* > p such that arg max o (T, is an a-approximation for all q E [p, b*), i.e., vl0 q) 2 a Us ( (4) for all such q.
Proof. LINEŠEARCH starts with a +- p and keeps increasing < q whenever (m,, a) 2 va (1) for q 2g In particular, whenever is increased, we get that for all o' [a, (a b)/ from Lemma A.1,
( (T, d') 2 (1. 2 Va v. 1 (a + 2)/2) Va u. (n, d') a a
(9))) (g').
That is, all times, the algorithm maintains the invariant that is an a-approximation for o' E [p.a]. Further, the algorithm terminates at 6 = 6* when ((() (TT, a) 2 (c) (b*), i.e. for all q' E [a, 6*). we get
( (T, 2 (T, 2 av 20 (b 2 a m (g))
The next lemma bounds the slope of the logarithm of the p-mean function and consequently the slope of In In (p):
Lemma A.8. 1. For any x E By such that HL < x; I HU for all i E [N], define g(x,p) = In f(x =
1 In 1 2 -1E(N==)) Then, if L I S U with condition number == U we have
p
dg(x. p) dp < k k.
2. For any given policy E II and aggregation rule é E {1,2), we have d(Ino"((T.))) < k In K, where k is the condition number defined in Assumption 3.1.
3. For given aggregation rule e e (1, define w(p) In u. (p). Then, for all distinct p, q S 1. w(
w(p)
< k klnx.
9-1 p
13

---

Navigating the Social Welfare Frontier
Proof. Part 1. Note that g(x,,)) In + +g(x,p) for all x E R p S and 3 > 0. Therefore, can assume without loss of generality that LH 1 and UH-
CH LH k.
That is, assume without of generality that S .... I IN I Since g(x. -In N.
1 In (EIE(M) x.). we get
p
that pg (x. p) In N + In (EE(N))*) 2 Therefore.
g(x,p) + dx(x,p) p)
x,) 22
(5)
dp
Since In t is concave in t, we get that
pg(x. In
1
Σ
In x..
P N
Σ
In
N
N
Therefore, we get
2 N E h pfp20, 0,
g(x,p) p)
(6)
5 Σ In t pf O.
Denote Up - 1 N Eie(M) z.
Case A: E [0, Plugging this back into eqn. (5), we get
dg(x.p) E,(nx)) xf 1 N
Inn=
In
1 N
Σ In
-1-1)
dp
Nup
Hp
Since 1 S 2; for all i, we have 0 I In I In for all i. Further, since XN
2z. we get that
dg(x,p) p)
-1-
-1) 1).
Ny
In
In
Σ ix
1 S Nink
dp
Up
1p
2Pp
Now, since Pe is the mean of x, E [N], we must have that μ4p 0t for some 1 5 0 S k. Substituting this, we get Np dg(x.p) dp S ((nn) ((xN/ /0P 1). Since o S and the derivative of a with respect pa. we get
(<NN/0 - 1) s (ND 1)
1,¹ p p-a=1 da
< J, p. 1-1111 da
(since p 1 < 0 and a=1 is nonincrcasing in p)
S p(k -1) 1) S pr..
(since 2 0)
Plugging this back into eqn. (7), we get
dg(x,
< In dp
or that dg(x.p) dp < k ln for all p E [0. 1].
Case B: p < O. As before, plugging bound (6) into eqn. (5), we get
dg(x,p) p) dp
x()x)) x
In
Σ In I
-1)
x
1
Σ Inx;
(1-
Nup
N
N
Up
N
That is, since p < 0,
dg(x.p) <
dp
N
Σ In
1-_11
1
_
Mp
x
In R
N)N
1
Hp
P
<
N
In R
XN
1-
Up
=
(-p)
In
1 Jx
Hp
di Sup
14

---

Navigating the Social Welfare Frontier
Denote -p -p q; then q > As before, Mp 0 for some 5 N, and so have
dg(x.p)
n.
1
1
dp S
1
q
q
K2
For q 2 (i.e., for p S -1), this is most In K. For q E [0, 1], we will bound this in manner similar Case A:
dg(x,p) p)
In
J1/a qa
da
dp
["
In
11/1 x9-1 da
$ (l)
x k2 1 S klnk.
Part 8 Given any trajectory т, for the vector G(T) [LH,UH] we get from Part that d (In (T)())
S k sll k.
dp
Consequently, for any policy n, we get for ui (TT,) E,sr [f(G(T).p) using linearity of expectation that
d (In (' p)) E
d (In (IG((G()))))
EYsa [1s In k] = k. In kn..
dp
é = 2. Follows by taking x = Brno [G(T] in Part 1.
Part 3. Note that w(p) In ln (p) (p) In max u10) (T. max In vl (T, Given distinct p,g S denote
Tp arg max (T, Then, by Part 1,
w(g)= w(p) (max In (0) (T. 9)) - In 100 (Tp. In ol)) (1)(((((p))))))) 9) In I (1p:(((TTp)))) S knx.
P-P
P-P
We are ready to prove Theorem 4.1 that gives guarantees for p-MEANPORTFOLIO (Algorithm 1).
Proof of Theorem 4.1. We prove that (comrectnes) the set IT' of policies output by the algorithm is indeed an a-approximate portfolio, (size bound) [ = O In bounded by
[m[1/a]] and (oracle complexity) the number of oracle calls to Problem (3) is upper
o (
(In(L/a) ( In In
(8)
We note that this size bound can be tightened slightly to O (In (Ine)(lxx we present the the above cleaner bound for simplicity.
In
Correctness.
Suppose the algorithm returns II' {no, T..... ng} such that me arg max mmaxx.em" (0 In[1/a] Po < P1 ... PK-
(0) (IT, Pc) with
N
Lemma A.4 shows that To is an a-approximation for all p S Po- Is therefore sufficient to prove that for all t E [o, K K-11 1], policy ny is an a-approximation for all p E [p., Pt+1]. Since P++1 LINESEARCH(V(O) Pt, II, a), Lemma A.7 implies this.
Size bound. Note that by definition, Pr+1 LINESEARCH((())) Pt, II, a). Therefore, from Lemma A.5, have that m v! for all except possibly = --1. Therefore,
satisfies v. (p++1) 2
va
(K (K-1)/2
10 (po) ( (K-1)/2 Ux
Ux
(0) 2 v2 1 (pk-1)>
(pk)
(0) (-00).
However, ! (px) S HU and ( (po) 2 HL. so that
(px)
U 1 k. and therefore,
2 (po)
K -
In
< log
2
In(1/a)
15

---

In that LINESBARCI on input finished in j iterations. Navigating the Social Welfare Frontier
Oracle complexity. To bound the oracle complexity, will show that each of LINESEARCH calls the oracle solve Problem (3) at most O (In (slpa))) times, where po
W is the first iterate in p-MEANPORTFOLL. and U/L is
In[l/o]
the condition number of the rewards. Since LINESEARCH is called at most O(K) = O [n(1//) times, this implies the bound (8).
To bound the number of oracle calls in LINESEARCH, we will Lemma A.8.3 that upper bounds the slope of w(p)
In 2 (p) by m ;= k In K. Suppose, for given 2 Po Im[1aa Then, we have the following for LINESEARCH:
Po S p a < b S all times, and
2. except in the last iteration, have U(π, a) vb(b) (otherwise LINESEARCH terminates step 2).
Denote by a.t-1), B0--1) the value of b in iteration j - 1. Then, since b - a is halved in each iteration, we must have
4ln 2-3
0 < ((51) - (1-1)) = (1--)) (5-1) v (1 - -p002- (i-1)
In(1/a))
However, since the algorithm does not terminate in step as discussed, we must also have that
( u (b(i-1))
(9)
From Lemma A.8, we get that
19 (bb--)) In
-()-)) { <k(In=)((n N) 2-3
-
(10)
(2) (ali-1))
In(1/a)
However, from Lemma A.6, we get (10) (T,, ((ا-))) 2 va vāu! (a(i-1)) Putting these together with eqns. (9) and (10), we get that
1
2 In In(1/a)
2-1
In(1/a)
Therefore,
85(In (In N)
2 v (In(1/a))²
Equivalently, the number of iterations j in LINESEARCH bounded by
o (In mm/l//)) =0 =1"mni((aaa)
A.2. Proof of Proposition 4.2
We prove the proposition assuming the aggregation function (T, p). The same proof applics for (2 (T,)) (T, p).
Proof.
max
E E,a, [f(G(T). ETTT, [f(G(T).
mell
max E, [f(G(r).)) - E,WTY [f(((T) well
max wa [f(G(r),g) - max Ex [f(G()),
#Ell
Tell
max En [f(G(T).g) -F(G(T), p)] HEll
df(G(T),r)
maxEE,55 #Ell
(g (q-p) max rE(p.9)
dr
< max Eyaa
- p) In KHU
#ell
(q p)UHklun
16

---

Navigating the Social Welfare Frontier
Entrfes Vector
of stlected
different
1.0
10
1.5
125
66
039
000
12.00
(a) Entries of A, B,C
(h) p-means at selected p values.
(c) p-means across different p values.
Figure 2. Side-by-side comparison of entries and y-means for vectors A, B.C.
The first inequality follows from Lemma 3.2, which ensures monotonicity in the parameter. The equality comes directly from the definition of Tp, as maximizes (F, p). The second inequality uses the properties of the maximum function. The next line applies the mean-value theorem to the function S(G(T).)) with respect to the variable p. The subsequent bound follows from the boundedness of the reward function and Lemma A.8. Finally, the terms involving k are replaced with L and U for conciseness.
B. Generalized p-Means: Illustrative Example
To clarify the meaning behind p-means, constructed an illustrative example in Figure 2. In this example, three vectors A, B and C' represent different policies, where each vector's s ith entry is the total reward for the ith stakeholder. Here, A is balanced policy, B is unbalanced with the largest sum, and C lies in between. Figure 2 (c) plots the p-mean values of these vectors, showing that varying p leads to different optimal policy.
C. Comparison with other MORL Algorithms
(Yu et al., 2024) optimize 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 random baselines our experiments). Our method computes a small, representative set of policies covering the entire spectrum of fairness criteria. This allows decision-maken to select confidently from this set, without worrying about suboptimality under other potential choices of p.
(Yang et al., 2019) focuses weighted linear objectives and learns single policy, whereas we focus on p-means and compute portfolio (multiple policies). (Alegre et al., 2023) builds portfolios focusing on weighted linear objectives (as opposed to p- p-means) and does not offer guarantees on portfolio size or oracle complexity. (Reymond et al., 2022) trains a single policy to approximate the Pareto frontier, which does not directly correspond to any social welfare function. To the best of our knowledge, our work 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.
In Table 3, we also present comparisons between p- >-MAAPPORTFOLIO and the Generalized Policy Improvement (GPI) algorithm of (Alegre et al., 2023), which maintains a set of policies II' C II and iteratively chooses the weight vector w with the highest difference between the optimal policy value for w in IT vs in IT'. Our implementation of GPI uses the differential evolution solver from scipy for this global optimization step. The results in the table indicate that our approach achieves significantly better approximation quality. We omit other details of GPI here and refer the interested reader (Alegre et al., 2023).
D. Additional Experimental Results
Figures 3 and 4 illustrate how the optimal policies for different values the portfolio lead to varying impacts for the stakeholders. These portfolios are all obtained using p- p-MEANPORTFOLIO. We also include the values of p chosen by p- D-MFANPORTFOLIO to construct the portfolio Table
17

---

Navigating the Social Welfare Frontier
Table comparison of actual approximation ratios various portfolio sizes for p-MEAPPORTFOL.O and implementation of
GPL.
Portfolio Size
D-MEAN-
GPI
PORTFOLIO
Resource Allocation after Natural Disaster
0.706
0,514
2
0.904
0.520
3
0.999
0.520
4
0.100
0.520
Healthcare Intervention
1
0.924
0.347
2
0.982
0.641
3
0.982
0.641
4
0.982
0.641
5
0.993
0.641
6
0.999
0.641
7
1.000
0.641
Portfolio Main
Total loomalizzed Reward
Route
Route
0.2
13.158
10.061
66165
4.818
0.657
077
0.73
(39)
p-value
Figure 3. Normalized total reward for each route under differrnt policies in the portfolio generated by POMEANPORTFOLIO in the taxi environment.
E. Experimental Details
We include the details of various experiments here.
E.1. Taxi Environment
Problem Setting
This environment consists of taxi agent whose task is to deliver passengers from source to destination. The world consists of a 6x6 grid and based on the environment setup of (Fan et al., 2022), we consider 4 source-destination pairs. Whenever a moves to a source point, it can pick a passenger, move to destination and drop the passenger, thus receiving reward. Since some routes could be easier to serve, the agent has decide which route to serve more often. Rewards multi-dimensional, each dimension corresponding to each route. We consider the following source-destination pairs: source coorde_ [[o, 0), [0, 5]. [3, 0), [1, OJ], destination_coortee [[1, 5), [5, 0), [3. 3], [0. 3]]
MDP Structure
STATE SPACE (S)
The state space consists of information on the location of the taxi, location of passengers and whether passengers have been picked up by the taxi the moment.
18

---

Navigating the Social Welfare Frontier
Fraction need met by each policy for each cluster Natural disaster experiment
Cluster
Cluster
Cluster 10
Cluster
Cluster
Cluster 7
Cluster
Cluster
Cluster
Cluster
Cluster
Cluster
.23.58
.5.15
-0.54
0.71
Figure Fraction of need for various clusters by various policies in the portfolio obtained by D-MEANPORTFFOLIO after intervention steps for the natural disaster experiment. Note that different solutions in the portfolio emphasize different clusters.
19

---

Navigating the Social Welfare Frontier
Table 4. The set of values of p chosen PoMEANORTFOOO ohtain the corresponding portfolios.
Portfolio size
p Values
Resource Allocation After Natural Disaster
-0.829
2
-4,864, -0.466
3
-11.136, -2.034, 0.621
4
-23.58, -5.15, -0.537, 0.712
Healthcare Intervention -1.325
2
-2.864, 0.034
3
-4.333, -0,333, 0.333
4
-6,641, -0.433, -0.075, 0.463
5
-9.216, -4.108, -0.437, -0.078, 0.461
6
-13,801, -6.4, -0,594, -0.22, 0.085, 0.542
7
-17.793, -3.698, -0.549,-0.186, -0.038, 0.222, 0.611
Taxi Environment
-2.0
2
-3.89, 0.87
3
-6.21, 0.72, 0.86
8
133.66.10.066 -6.17, -4,82, 0.66, 0.7, 0.77, 0.89
10
-27.03, -13.02, -6.25, 0.66, 0.71, 0.78, 0.81, 0.86, 0.89, 0.95
ACTION SPACE (S)
The agent can take one of 6 actions: move north, south, east, west and pick or drop passenger in the current grid cell.
REWARD (R)
The reward function gives reward 0 for moving, 100 reward for taking invalid action of picking or dropping a passenger at wrong coordinating, and 30 reward for dropping a passenger at the right destination.
LEARNING POLICY
Given a scalarization function (or welfare function ), the task is to find policy x² that maximizined the expected value of scalarized return. Specifically:
π arg max max [F(G(T),)]]
(11)
We learn this policy using the Welfare Q-Learnng algorithm proposed in (Fan et al., 2022). For every problem setting, we train the policy for 200 episodes. Every episode is finite horizon problem with 1000 timesteps. We consider discount factor gamma 0.99.
E.2. Natural Disaster Problem Setting
In this synthetically generated example, suppose that in the wake of a natural disaster, a centralized aid agency must determine how to allocate resources to a set of 12 clusters (N = 12). Each cluster is characterized by their population density (high or low), proximity to critical infrastructure (near or far), and the predominant income level of its residents (low, middle, high).
MDP Formulation and Experimental Protocol
We model postdisaster resource allocation to N-12 clusters as a finite-horizon MDP. Let H denote the time horizon. Throughout, we use for the allocation increment and K for the per-period budget (these correspond to and B in the informal description above). All needs and allocations lie on the k-grid.
20

---

Navigating the Social Welfare Frontier
Cluster ID
Density
Proximity
Income Level
Total Population
Initial Need
High
Far
148
150
2
High
Far
Low-Income
307
500
3
High
Far
Middle-Income
616
650
High
Near High-Income
816
5
High
Near
Low-Income
1405
1000
6
High
Near
Middle-Income
2782
950
7
Low
Far
High-Income
74
1000
Low-Income
350
Low
Far
Middle-Income
396
300
10
Low
Near
36
50
11
Low
Near
Low- Low-Income
113
100
12
Low
Near
Middle-Income
230
100
Table 5. Clustered population data including density, proximity, income level, total population, and initial need.
State space (S). At time f, the state is 9; = (st, St.N) E E where St,i is the unmet need of cluster i (in units of k). We initialize 8y from Table 5. Feasible states are those reachable by repeatedly (i) subtracting allocated units and (ii) possibly increasing one unattended cluster by k (see transitions below).
Action space (A). An action an allocation vector a; (0t,1..... ... with ar E (0, 2k...., .......K K} and per-period
budget constraint Σ dz S K. We impose a validity constraint:
st,i = 0t 0,
i.e., we never allocate to cluster whose need is already zero. In implementation, enumerate the full feasible action space A = fa Σ, s } and then state-filter to A(st) {a E A $1, = 0 = 0}.
Transitions (P). Given 9 and ar, define the interim post-allocation state
Ft.i max (0, 81,5 a
24 (Ft,1..... Tt,N):
Let U, {i: 2 > 0 and dr = 0) be the set of unattended clusters that still have unmet need. With probability spillover occurs and 8141 24. With probability 1 - p. exactly one unattended cluster Ue is chosen uniformly and its need increases by l:
Iz,i k,
i= J.
8t411
Te,50
i i j.
The rationale behind this model behavior is that if need remains unmet, there can possibly be increase in need over time. For example, lack resources might lead to an increase need for medical care, which will compound the total resources needed in the next time period. Ug = 0, then 8141 x, deterministically.
Policy menu. We evaluate reasonable structured policies that map state s to valid action Ass) using the following priorities:
1. bred-based: allocate all K to arg max; St-
2. Per-capita need: allocate all K to arg max; s:/pop,-
3. Population: allocate all K to arg max; pop,-
4. Income-priority: prioritize Low Middle > High income (breaking ties by higher s;) and allocate all K to the first in this order.
5. Proxinity-priority: prioritize Near Far (ties by higher s;) and allocate all K accordingly.
6. Randomized weighted hybrid (implemented). Sample weights Wheed; Wpes Wine; Uprox Unif(O, 1) and normalize to sum to one; score each cluster
score;
Wneed
+ U/p
S4 pop;
+ Wine
(income; Low) + Uprox 1(prox, -Near..
21

---

Navigating the Social Welfare Frontier
Let arg max; score;, If 8g. 2 K, allocate at- K. Otherwise allocate a,- it and allocate the remaining k (if available) to uniformly random other cluster with 8; 0; all other coordinates are 0. (Allocations are always in increments of k.)
In simulation, when state is first encountered we sample one policy from this menu and fix it for that state for the remainder of the rollout. This produces stateaction map that varies across reachable states without solving global control problem.
Reward and optional equity bonus.
Let need, be cluster is initial need. For a transition 8 + s the per-cluster reward
(k/10/ a- A1s,, (1 B.),
r=(s, =
1 2
HK
+
2
need?
where (, a, s') (s - s;) 1[a; 0} penalizes unattended clusters whose need inflates, and the small floor k/10 avoids zero signal in edge cases. The optional global equity multiplier B, enables global constraints/bonuse::
B. s wiif E c} + (income, = Low].
B f min Smax),
cluster set bonus
category honus
where w is user-set weight, a designated set clusters (c.g., (2}), and Binx an optional cap. Setting w = recovers the unmodified reward.
Expected returns, allocations, and what report. Given (s, a), we enumerate all feasible s' and their probabilities, and compute per-cluster expected rewards
E Err = P(())),)))((s.....)
Over the horizon accumulate (i) the expected cumulative reward R; = E(=o
H1-1 Pr(reach sx) (sr, ae, Se+1)] and (ii) the expected total allocation A; = = 0 Pr(reach s;) E] We report both R2 and A₁ for each cluster.*
Rollout and tractability. We avoid Monte Carlo sampling by enumerating next states but retain only those with probability (default 10- Newly reached states are added to frontier with their path probability; we prevent revisiting states to keep the graph acyclic in practice. This yields a sparse, tree-like expansion that preserves essentially all probability mass while remaining tractable even with a large discrete action space A (whose size scales as O((K/k+1)*) For diagnostics on small instances we also provide a CSR- based transition matrix constructor.
Parameterization. Unless otherwise noted, we use the k-grid and budget specified in the problem setting (e.g., k=50, K=150), spillover parameter p e 10, controlling unattended-ned -eed inflation, and finite horizon H. We conduct sensitivity checks in p and H in the appendix.
E.3. Healthcare Intervention
The Healthcare Intervention problem is based on the large-scale mobile-health program run by the NGO ARMMAN (ARMMAN, 2024). The goal of the program is to maximize engagement of beneficiaries with the program using limited service call interventions. Based on previous works, arms beneficiaries, a budget the number of service calls to give every week. For every beneficiary, on their listenership with the voice call. This is considered as an engaging or non-engaging state if the listenership is above or below 30-seconds threshold respectively. One week of time is considered as one timestep. Finally, every week, the action can be to place (active) or not to place live service call (passive). Additionally, for every beneficiary, we have information on their socio-denne deriioddmmgraphiic characteristics such as age, income, education. We use real world data from service quality improvement conducted by ARMMAN in January 2022 (Verma et al., 2023). Further, for our experiments, we sample data for 2100 beneficiaries, and run the experiment for /l 12 timesteps.
model this problem as RMAB problem where we have multiple
have information
II code, both are computed by weighting each steps contrihutions by the path probability mass.
22

---

Navigating the Social Welfare Frontier
Generation of Policies & Reward Functions
The default reward incentivizes agents to be in engaging state. Thus, agents receive reward if they are in engaging state, and otherwise. However, due varying policy needs over time or over different geographies, health workers often have prioritize some beneficiaries more than others. To capture these varying priorities, leverage the Social Choice Language Model framework (Verma et al., 2024a) to derive reward functions from natural-language commands. Given a command specifying N preferences (each indicating subgroup to prioritize) this method generates two sets of reward functions:
1. Individual preferences: one reward function per preference (total of N reward functions) which we treat as cach stakeholder's s reward function.
2. Balancing functions:
a collection of reward functions that trade off among the N preferences, whose corresponding policies form our feasible IT.
In our experiments, we set N = 59 and construct [[]] = 200 balancing policies as feasible set.
Learning Policy
It is computationally intractable to optimally solve the RMAB problem (Papadimitriou and Tsitsiklis, 1999). Thus, the popular Whittle Index Heuristic (Whittle, 1988) to solve RMAB problem for given single reward function. Specifically, Whittle Index quantifies the reward gain achieved for every arm in every state if we took the active action as compared to if we took the passive action. The policy then chooses the arms with highest whittle indices within the budget limit.
Baseline Policy
The baseline policy mentioned in Figure 1 is trained on the default reward.
E.4. Other Details
Initial for CONGEETTOO For NUDGE--COSSTTANNEPPRRTOOLLO we fix Pn 1000
Computing actual approximation factor
The approximation factor Q(IT') for any portfolio TT' is computed via a grid search over 1000 points in (oo, 1] for the natural disaster environment and the healthcare intervention problem. For the taxi environment, used 50 points due the computational burden of solving each problem.
Choice of
For given portfolio size K, we chose the smallest a (0.05, 0.10, 0.15,.... ... 0.900 0.95, 0.99) among which the resulting portfolio has size K.
23


Reviews:
[{"review_id": "lELbqjiOyl", "reviewer": "Reviewer_YvM6", "summary": "In this paper, the authors proposed a novel setting in optimizing social welfare while considering different preferences. The authors proposed an algorithm which can trade off among approximation factor, portfolio size, and computation efficiency. The proposed p-MEANPORTFOLIO algorithm chooses several p-value, and train corresponding policies.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the insightful comments! Additional results are available in the anonymous link [here](https://anonymous.4open.science/r/approximation-portfolios-for-rl-ICML)\n\n**1.** *Why there is a need to find $\\alpha$-approximation for p-value. Why not use previous MORL algorithms?*\n\n- We thank you for this important comment. Our work addresses the following limitations of previous MORL methods. \n\n1. 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. \n\n2. 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. \n\n3. 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. \n\nOur work addresses each of these limitations as follows: \n\n1. We provide theoretical guarantees that polynomially bound both portfolio size and the number of oracle calls, and we empirically demonstrate this. \n2. We ensure strong fairness guarantees with respect to $p$-means, a widely used class of social welfare functions. \n3. 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$. \n\n\n**2.** *Comparison to other optimization or MORL algorithms.*\n\n- 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.\n\n\n**3.** *If the model is perfectly known ... is there still a need to use MORL?*\n\n- 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. \n\n**4.** *The authors mentioned ``Small changes in p can sometimes ... Can we directly model or optimize the policies given different p?*\n\n- 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.  \n\n    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.\n\n**5.** Extension to a multi-agent setting.\n\n- 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. \n\n\n**6.** *Other social welfare functions are not discussed.*\n\n- 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).\n\n**7.** *To select the policies, the authors assumed the utility can ... under different p-value.*\n\n- 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).", "claims_and_evidence": "In real-world applications, decision-makers should understand how policies change as the value p varies, and make informed decisions about which policy to deploy. The authors reflected this observation in their algorithm design.", "methods_and_evaluation_criteria": "Yes, the methods are properly evaluated in the simulation section with several environments.", "theoretical_claims": "Yes, I checked the major proofs of Proposition and Theorems.", "experimental_designs_or_analyses": "Yes, I checked the simulation results.", "relation_to_broader_scientific_literature": "The proposed method in this paper is an interesting addition to multi-objective Reinforcement Learning and practical settings of social welfare setups.", "essential_references_not_discussed": "NA", "other_strengths_and_weaknesses": "Strengths:\n\n-The paper comes up with a novel setting for connecting MORL with social welfare maximization problem. \n\n-Simulation on several interesting social domains validate the effectiveness of the proposed algorithm.\n\n-Theoretical results support the usage and effectiveness of line search and warm start.\n\nWeaknesses\n\nIt is unclear why there is a need to find \\alpha-approximation for p-value. Why not directly applying some previous MORL algorithms?\n\nOther social welfare functions are not discussed, and it is also unclear how the algorithm performs for other social welfare functions.\n\nTo select the policies, the authors assumed the utility can always be evaluated. However, in many practical settings, it is not possible to query the environment and get all the possible return under different p-value. \n\nThere lacks comparisons to neither model-based optimization approaches nor other MORL algorithms.", "other_comments_or_suggestions": "Please see above.", "questions_for_authors": "In the Introduction section, authors mentioned that the major challenge is p-value can change. But in previous literature, if the model is perfectly known, and the social welfare maximization problem is totally tractable, is there still a need to use MORL?\n\nIn the Introduction, the authors mentioned \"Small changes in p can sometimes lead to dramatically different policies, further complicating the selection process\". What does selection process refer to? Can we directly model or optimize the policies given different p?\n\nA related but also practical setting to this work is that each user may have its own utility or welfare definition, and they are making decisions independently. In this way, a multi-agent setting shall be considered with different objectives. Can the authors comment on this setting?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "qDkg1hsIep", "reviewer": "Reviewer_XsQh", "summary": "The paper investigates an interesting problem of learning fair policies in multi-objective reinforcement learning (MORL) by proposing an $\\alpha$-approximate portfolio which is a finite set of policies that are approximately optimal across the family of generalized p-means social welfare functions (e.g., Nash, utilitarian, egalitarian). Instead of optimizing a single welfare function, the authors develop algorithms (p-MeanPortfolio and Budget-ConstrainedPortfolio) to construct portfolios for generalized p-means with theoretical guarantees on approximation quality and computational efficiency. Experiments on synthetic and real-world domains (e.g., healthcare interventions) demonstrate the approach’s ability to balance fairness and efficiency while reducing oracle calls.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the insightful comments! Additional results are available in the anonymous link [here](https://anonymous.4open.science/r/approximation-portfolios-for-rl-ICML)\n\n**1.** *Including one or more realistic environment with higher number of objectives.*\n\n- 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.\n\n  \n**2.** *The relation to the paper (Yu et al., 2024) and the benefits of our work over existing methods*\n\n- 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$\n\n**3.** *While theoretically sound ... limit the scalability to large MDPs.*\n\n-  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.\n\n    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.\n\n\n**4.** *The RL algorithm used, hyperparameters, and the experimental settings (ESR vs SER).*\n\n-  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) .\n\n**5.** *Comparisons to other MORL methods. How does this work differ from methods like Envelope [1], GPI [2], or PCN [3]*\n\n- [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.\n\n\n    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.\n\n**6.** *Bound on the heuristic algorithm's approximation factor*\n\n- 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.\n\n**7.** *Do the approximation guarantees differ between SER and ESR?*\n\n- Our theoretical guarantees hold uniformly for both ESR ($v^{(1)}$) and SER ($v^{(2)}$).", "claims_and_evidence": "Most of the paper claims are supported by theoretical and experimental results. However, the paper lacks baseline comparisons and more realistic environments to show if the proposed method can scale with environments with large number of objectives.", "methods_and_evaluation_criteria": "The benchmark environments are appropriate. However, including one or more realistic environment with higher number of objectives would further strengthen the paper's claim.", "theoretical_claims": "The theoretical results in the main paper seem to be correct. However, I did not verify the detailed proofs in the appendix.", "experimental_designs_or_analyses": "Relevant baselines and more realistic empirical validations are missing.", "relation_to_broader_scientific_literature": "The contributions of this paper to fair RL are somewhat unclear. Previous methods, such as the one cited in the paper (Yu et al., 2024), already optimize the generalized Gini welfare function for preferential user treatment. This approach is quite similar to the one proposed here. The Gini welfare function is also highly general where setting $w_1=1$ and all others to 0 results in an egalitarian outcome, while equal weights lead to a utilitarian welfare function. Additionally, preferential weights can be used to sample a policy for specific user weights. A key advantage of the cited work is that it learns a single policy which eliminates the need for multiple oracle calls. This raises the question of what specific benefits this paper offers over existing methods?", "essential_references_not_discussed": "The paper adequately discusses related work.", "other_strengths_and_weaknesses": "Strengths: \n* The paper investigates an interesting problem of fairness in MORL where the goal is to achieve policy outcomes to the choice of social welfare functions. This problem in its setting is not only interesting but also novel the way it is being solved. \n\n* The idea of an $\\alpha$-approximate portfolio is promising, seems original and provides a structured way to learn a set of Pareto optimal policies that trade-offs across p-values. Moreover, the unification of scalarized expected returns (SER) and expected scalarized returns (ESR) under one framework is a notable contribution.\n\n* The analysis of portfolio size (logarithmic in the reward condition number κ) and oracle complexity (Theorem 4.1) is thorough, and make sense.\n\n* The Budget-ConstrainedPortfolio heuristic achieves near-optimal $\\alpha$ with significantly fewer oracle calls than p-MeanPortfolio* (Table 2), making it viable option for real-world applications.\n\n* The paper is well-written, and the related work section comprehensively covers MORL and fairness literature.\n\nWeaknesses: Despite it strengths, the paper has several weaknesses. Below I enlist the weaknesses, my concerns, questions and suggestions for improving the paper.\n\n* While theoretically sound, p-MeanPortfolio* requires many oracle calls (e.g., 69 calls for α=1.0 in healthcare experiments) which is very computationally expensive and also limit the scalability to large MDPs.\n\n* The paper does not specify the underlying RL method used to solve Problem (3) (e.g., policy gradient, Q-learning). It's important to explain how (3) is solved both for practical and reproducibility reasons. \n\n* The paper also lacks comparisons to MORL methods that approximate Pareto front such as Envelope[1], GPI[2] or PCN[3]. Although random policy and $p$ baselines are included, comparisons to multi-policy MORL methods is essential to see if they can outperformed by the proposed methods both in terms of fairness and policy diversity. \n\n* The experiments do not clarify whether results correspond to SER, ESR, or both. It's important to clarify as results holding for SER may not be hold true for ESR.", "other_comments_or_suggestions": "See above.", "questions_for_authors": "See above weaknesses and my concerns in the Relation To Broader Scientific Literature. \n\nA few more questions:\n* How does the heuristic algorithm perform in worst-case scenarios? Can you bound its approximation factor $\\alpha$ as a function of the budget K?\n* Which RL algorithms (e.g., policy gradient, value iteration) were used to compute optimal policies for fixed p-means? How were hyperparameters tuned?\n\n* Do the approximation guarantees differ between SER and ESR scalarizations? Is it possible to include separate results for each criterion?\n\n* How does the portfolio size/quality trade-off compare to Pareto front approximations in terms of interpretability and computational cost?\n\n* How does this work differ from methods like Envelope [1], GPI [2], or PCN [3], which also learn multiple policies for diverse objectives? \n\n[1] Yang, Runzhe, Xingyuan Sun, and Karthik Narasimhan. \"A generalized algorithm for multi-objective reinforcement learning and policy adaptation.\" Advances in neural information processing systems 32 (2019).\n\n[2] Alegre, Lucas N., et al. \"Sample-efficient multi-objective learning via generalized policy improvement prioritization.\" arXiv preprint arXiv:2301.07784 (2023).\n\n[3] Reymond, Mathieu, Eugenio Bargiacchi, and Ann Nowé. \"Pareto conditioned networks.\" arXiv preprint arXiv:2204.05036 (2022).", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "yXaobp1Hih", "reviewer": "Reviewer_yxwr", "summary": "The paper proposes algorithms for computing a portfolio of policies for multi-objective MDPs. The individual reward functions are scalarized by an aggregation function called p-means, which is dependent on a parameter $p  \\in [-\\infty,1]$. The authors propose an algorithm, which generates an $\\alpha$-approximate cover of all $p$ values, i.e., for an p-value there is an alpha approximation in the portfolio. The algorithm starts with a lower bound and then, exploits the monotonicity of the p-means functions to find the next p-value for a policy that should be included in the portfolio. Finding this upper bound is done by a binary search algorithm which requires logarithmic calls of the oracle function. The authors also provide an upper bound for the portfolio size and the number of MDPs that have to be solved.\nAs an alternative, they propose a second algorithm, which has a bounded number of oracle calls, but cannot guarantee to hold a specific $\\alpha$-value. In the experiments, the algorithms are compared to baselines generating policies for a randomly chosen number of values for $p$.", "questions": "", "limitations": "", "rating": 3, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for the insightful comments! Additional results are available in the anonymous link [here](https://anonymous.4open.science/r/approximation-portfolios-for-rl-ICML)\n\n**1.** *The selection of baselines seems somewhat unfair ... much more Oracle calls.*\n\n-  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.\n\n  \n**2.** *It is unclear how p-means were tuned ... given number of policies.*\n\n- 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. \n\n**3.** *The general task of the paper is hard to grasp ... of broader impact to the machine learning community.*\n\n- 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). \n\n    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$. \n\n    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. \n\n\n**4.** *The example in section 1.2 did not help me ... varying the p-value actually means.*\n\n- 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. \n\n**5.** *The section on warm-starting the oracle ... convergence of the method used to solve the MDP.*\n\n- 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.\n\n\n**6.** *How did you select the $\\alpha$ values?*\n\n- 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.\n\n\n**7.** *Why the approximate algorithm can outperform the p-meansPortfolio*\n\n- $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.\n\n    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]$.\n\n\n**8.** *What is the set of feasible set of policies ... using the Oracle?*\n\n- 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).", "claims_and_evidence": "I would generally say that the claims are supported well enough.", "methods_and_evaluation_criteria": "The empirical evaluation uses three environments looking appropriate for this setting.", "theoretical_claims": "As far as I could follow the proofs in the appendix, I could not find any flaw.", "experimental_designs_or_analyses": "The selection of baselines seems somewhat unfair as the baselines have exactly $K$ MDPs to solve whereas the proposed p-mean portfolio might have much more Oracle calls. Also, it is unclear how p-means were tuned to exactly generate a given number of policies.\nThe approximate method sometimes beat the non-approximate ones and there was no comment on how this happened.", "relation_to_broader_scientific_literature": "The related work section of the paper was insightful though I lack the familiarity with the area to claim that I could check for completeness here.", "essential_references_not_discussed": "I am not aware of any major work that should have been mentioned.", "other_strengths_and_weaknesses": "The general task of the paper is hard to grasp as the use of varying the parameters of p-means is not motivated very well. Also, the assumption that all reward functions have the same range is somewhat unmotivated. Thus, the problem setting seems to be rather specific and have to ask myself if the paper is of broader impact to the machine learning community.", "other_comments_or_suggestions": "The example in section 1.2 did not help me much to understand the paper. Instead, a paragraph to better explain the idea of p-means would be insightful. Maybe a figure on which reward vectors are optimal under varying values of p, would help to grasp what varying the p-value actually means.\n\nAs your work does not rely on reinforcement learning, assuming MDPs where the optimal solution can be computed by dynamic programming or linear programming, might allow you exactly determine optimal policies for a particular value of p.\n\nThe section on warm-starting the oracle is also not very insightful. The general idea is known from methods for computing the pareto front and the proposition gives a cryptic bound for the difference in the value. But this is not very insightful on the rate this accelerates the convergence of the method used to solve the MDP.", "questions_for_authors": "How did you select the $\\alpha$ values for the experiments?\n\nCan you explain why the approximate algorithm can outperform the p-meansPortfolio? \n\nWhat is the set of feasible set of policies  $\\Pi$ for in the input of  your algorithms? You seem to compute the policies on the fly using the Oracle?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "MFLh3csZT1", "reviewer": "Reviewer_vi7q", "summary": "This paper proposes a method to create a portfolio of multi-objective reinforcement learning policies that aim to preserve the social welfare among agents; in other words, a portfolio that ensures that different stakeholders fulfill their individual preferences. The presented method (*p-MeanPortfolio*) revolves around Generalized p-means, a family of social welfare functions that balance fairness given a parameter $p \\in [-\\infty, 1]$. This work proposes an algorithm that generates a portfolio of policies that approximates the generalized p-means objectives up to a level defined by $\\alpha \\in (0,1)$. The paper provides theoretical bounds to the portfolio size and the number of Markov Decision Processes (MDPs) optimally solved. Additionally, this paper proposes a heuristic algorithm (*BudgetConstrainedPortfolio*) that reduces the computational cost of the *p-MeanPortfolio* algorithm while preserving the quality of the portfolio. The paper presents experiments in synthetical data and real-world problems.", "questions": "", "limitations": "", "rating": 4, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your incredibly detailed and insightful comments! Additional results are available in the anonymous link [here](https://anonymous.4open.science/r/approximation-portfolios-for-rl-ICML)\n\n**1.** *On the overstimation of oracle complexity in Theorem 4.1, and how this impacts our current results.*\n\n-  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.\n\n  \n**2.** *Discussions on selected $p$ values in the experiments.*\n\n- 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.\n\n    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.\n\n\n**3.** *Why the heuristic can sometimes outperform the p-meansPortfolio*\n\n- $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.\n\n   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.\n\n\n**4.** *Code Reproducibility in the Supplementary materials.*\n\n-  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.\n\n\n**5.** *It seems that this method is applicable for reduced-size (small-sized portfolios) problems.*\n\n- 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.\n\n\n\n**6.** *Typo in Lemma A.4.*\n\n- We thank the reviewer for noting this detail! We will promptly correct the typo.", "claims_and_evidence": "Theoretical analysis and experiments on synthetic data and real-world scenarios support the paper's claims.", "methods_and_evaluation_criteria": "The proposed methods fulfill the objective of the paper: selecting a subset of policies from a larger set to constitute a portfolio that preserves generalized p-means welfare along the spectrum of possible values of p, tackling the limitations of picking a specific value that could be suboptimal. The paper introduces two algorithms that manage to do this: *p-MeanPortfolio* and *BudgetConstrainedPortfolio* and shows their validity empirically in cases of limited size.\n\nThe characteristics of the testing scenario match the theoretical guarantees the paper provides, as it assumes bounded rewards for the Markov Decision Processes (MDPs), and they respect the bound for the portfolio size detailed in the theory part.", "theoretical_claims": "I checked all the theoretical claims:\n\n- Assumption 3.1 to bound the reward\n- Lemma 3.2 that talks about the monotonicity of the generalized p-mean\n- Theorem 4.1 about the bounds to portfolio size and Oracle calls:\n\nI think the final bound has a miscalculation (Line 858), leading to an overestimation of the oracle calls upper-bound:\n\n$$\nO\\left(ln\\left(\\frac{\\kappa ln N}{ln(1/\\alpha)}\\right)\\right) = O\\left(\\frac{ln\\kappa + ln ln N}{ln ln(1/\\alpha)}\\right)\n$$\n\n- Proposition 4.2 talks about the closeness of optimal values for two different p (enabling the proposition of warming up the search and increasing computational efficiency.", "experimental_designs_or_analyses": "The presented experiments ran over three scenarios: resource allocation after a natural disaster (synthetic), taxi (synthetic), and healthcare intervention (real-world). There was a set of pre-trained policies to choose from in all cases. The test consisted of evaluating the quality of the portfolios based on how close they were on average with respect to the best possible performance (known beforehand).\n\nOne experiment compared the *p-MeanPortfolio* with picking the policies randomly and picking the value of p randomly to create the portfolio regarding the approximation quality. I couldn't see any mention of the selected value of p for each policy in the final portfolio, and it's relevant to better understand the experiments.\n\nThe other experiment compared both methods (*p-MeanPortfolio* and *BudgetConstrainedPortfolio*) regarding approximation quality., portfolio size, and oracle calls.\n\nI couldn't find an explanation in the paper for the cases in which *BudgetConstrainedPortfolio* beat the *p-MeanPortfolio* in terms of quality, considering that the former uses heuristics versus the latter using as many calls to the oracle as possible.", "relation_to_broader_scientific_literature": "The work in this paper could be comparable to optimizing portfolios using combinatorial methods (which the paper referenced), with the approach of searching over the space of possible values of $p$ in the context of generalized p-mean welfare instead of solving a mathematical problem, as long as the assumptions hold.", "essential_references_not_discussed": "I couldn't find any essential reference that was not discussed.", "other_strengths_and_weaknesses": "*Strengths*\n\n- The paper is well-organized and easy to follow.\n- The theoretical claims are clearly developed and verifiable\n- The theoretical bounds seem reasonable in providing optimality guarantees (given an original set of policies).\n\n*Weaknesses*\n\n- Supplementary materials don't add to the submission\n- The results don't discuss the selection of values for $p$ when picking a policy to be part of the portfolio; considering that the most important contribution of this work is the search over the range of possible values for $p$, I believe the pairs policy-value of p should be discussed.\n- It seems that this method is applicable for reduced-size (small-sized portfolios) problems.", "other_comments_or_suggestions": "- Check the suggestion over the final expression of the bound in Theorem 4.1 for oracle calls and discuss if the overestimations change in any sense your results\n- I think there's a typo in Lemma A.4 (Line 653): You switched to $v^{\\mathcal{(l)}}$, but you were developing all for $v^{\\mathcal{(1)}}$.\n- Why do you think the *BudgetConstrinedPortfolio* performs better for portfolio sizes 1 and 2?", "questions_for_authors": "- How does your overestimation of Theorem 4.1 impact your current results?\n- How diverse are the final p values selected in your experiments? I understand that the final portfolio finds the $\\alpha$-approximate portfolio that ultimately contains pairs policy-value of p. Is my understanding correct?", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: This paper addresses the problem of constructing policy portfolios for multi-objective reinforcement learning to approximate generalized p-means social welfare objectives. The reviewers generally agreed that the problem is clearly motivated and relevant, especially in scenarios where decision-makers face uncertainty in stakeholder preferences.

 Reviewers appreciated the clear theoretical framework, rigorous proofs, and practical algorithms (p-MeanPortfolio and BudgetConstrainedPortfolio) proposed. The experiments effectively demonstrate the trade-offs in portfolio size, computational cost, and approximation quality in synthetic and realistic scenarios. The clarity of writing and presentation were also positively noted.
 The primary concerns revolved around somewhat limited baseline comparisons, especially with respect to Pareto front approximation methods. Reviewers suggested additional discussion on how the method would scale to larger or more complex scenarios. Initially, there was also some confusion regarding algorithmic details. But these concerns were clarified in the authors' rebuttal.

 Overall, while the paper could benefit from expanded comparisons and clearer discussions of scalability, the contributions are solid, and the results convincing. It represents a sound contribution to the multi-objective reinforcement learning literature. I recommend acceptance, provided the authors incorporate the reviewers' feedback in their final revision.
Decision: Accept (poster)