# Active Value Querying to Minimize Additive Error in Subadditive Set Function Learning

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 42 references that are in the map.
- First posted on arXiv 26 Feb 2026.

## Builds on (most cited first, 9 of 9)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [A Unified Approach to Interpreting Model Predictions](https://mlsanity.com/paper/1705.07874/) (2017)
- [Deep Submodular Functions](https://mlsanity.com/paper/1701.08939/) (2017)
- [Representation, Approximation and Learning of Submodular Functions Using Low-rank Decision Trees](https://mlsanity.com/paper/1304.0730/) (2013)
- [Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas](https://mlsanity.com/paper/1307.3301/) (2013)
- [Learning Coverage Functions and Private Release of Marginals](https://mlsanity.com/paper/1304.2079/) (2013)
- [Faster and Simpler Sketches of Valuation Functions](https://mlsanity.com/paper/1407.7269/) (2014)
- [Approximate Modularity Revisited](https://mlsanity.com/paper/1612.02034/) (2016)
- [Reducing Optimism Bias in Incomplete Cooperative Games](https://mlsanity.com/paper/2402.01930/) (2024)

## Abstract (arXiv)

Subadditive set functions play a pivotal role in computational economics (especially in combinatorial auctions), combinatorial optimization or artificial intelligence applications such as interpretable machine learning. However, specifying a set function requires assigning values to an exponentially large number of subsets in general, a task that is often resource-intensive in practice, particularly when the values derive from external sources such as retraining of machine learning models. A~simple omission of certain values introduces ambiguity that becomes even more significant when the incomplete set function has to be further optimized over. Motivated by the well-known result about inapproximability of subadditive functions using deterministic value queries with respect to a multiplicative error, we study a problem of approximating an unknown subadditive (or a subclass of thereof) set function with respect to an additive error -- i. e., we aim to efficiently close the distance between minimal and maximal completions. Our contributions are threefold: (i) a thorough exploration of minimal and maximal completions of different classes of set functions with missing values and an analysis of their resulting distance; (ii) the development of methods to minimize this distance over classes of set functions with a known prior, achieved by disclosing values of additional subsets in both offline and online manner; and (iii) empirical demonstrations of the algorithms' performance in practical scenarios.