# Data-Driven Solution Portfolios

arXiv: https://arxiv.org/abs/2412.00717 · HTML: https://mlsanity.com/paper/2412.00717/

## Key facts

- Cited by 4 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 1 Dec 2024.

## Built on by (most cited first, 4 of 4)

- [Navigating the Social Welfare Frontier: Portfolios for Multi-objective Reinforcement Learning](https://mlsanity.com/paper/2502.09724/) (2025)
- [TCS-BENCH: Benchmarking State-of-the-Art Generative AI Theoretical Computer Science Research Ability](https://mlsanity.com/paper/2608.09538/) (2026)
- [Retriever Portfolios: A Principled Approach to Adaptive RAG](https://mlsanity.com/paper/2605.31176/) (2026)
- [Many Preferences, Few Policies: Towards Scalable Language Model Personalization](https://mlsanity.com/paper/2604.04144/) (2026)

## Abstract (arXiv)

In this paper, we consider a new problem of portfolio optimization using stochastic information. In a setting where there is some uncertainty, we ask how to best select k potential solutions, with the goal of optimizing the value of the best solution. More formally, given a combinatorial problem Pi, a set of value functions V over the solutions of Pi, and a distribution D over V, our goal is to select k solutions of Pi that maximize or minimize the expected value of the em best of those solutions. For a simple example, consider the classic knapsack problem: given a universe of elements each with unit weight and a positive value, the task is to select r elements maximizing the total value. Now suppose that each element's weight comes from a (known) distribution. How should we select k different solutions so that one of them is likely to yield a high value? In this work, we tackle this basic problem, and generalize it to the setting where the underlying set system forms a matroid. On the technical side, it is clear that the candidate solutions we select must be diverse and anti-correlated; however, it is not clear how to do so efficiently. Our main result is a polynomial-time algorithm that constructs a portfolio within a constant factor of the optimal.