W2CB: Online Data Acquisition Optimization With Wasserstein Contextual Combinatorial Bandits

The success of modern machine learning (ML) heavily depends on high-quality data. With the emergence of data-sharing platforms (DSPs), users can submit ML queries to acquire suitable training data, while data contributors can monetize their datasets. However, developing an efficient and scalable DSP faces two-fold challenges. <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">First</i>, both data blocks and ML queries are continuously generated in practice, requiring the efficient evaluation of data blocks on the fly. <italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Second</i>, redundancy or complementary effects among data blocks make selecting multiple data blocks an NP-hard combinatorial optimization problem. To address these challenges, we propose the <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">W</u>asserstein-based <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</u>ontextual <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">C</u>ombinatorial <underline xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">B</u>andits (W2CB) algorithm for online data acquisition on DSPs. Specifically, W2CB employs Wasserstein embedding to evaluate subsets of data blocks for queries, considering both individual values and overall diversity. Meanwhile, the contextual combinatorial multi-armed bandit (C<sup xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">2</sup>MAB) framework is deployed to select the optimal data block subsets for queries based on historical and contextual information. The notable advantage of W2CB lies in its adaptability to diverse and dynamic data distributions, along with its innovative evaluation and selection mechanism that enhances the performance and efficiency of data acquisition. Theoretical analysis proves a sublinear cumulative regret upper bound for W2CB. Experimental results demonstrate the superiority of W2CB, which outperforms SOTA baselines with up to a 7.7% improvement in ML training utility.