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

This paper addresses the challenge of approximating unknown subadditive set functions by developing active querying methods to minimize additive error through the strategic disclosure of subset values, thereby reducing the distance between minimal and maximal completions in both offline and online settings.

The Gist

Imagine you are a chef trying to recreate a famous, complex recipe, but you only have a few ingredients listed on a torn piece of paper. You know the names of the ingredients (the "subsets"), but you don't know exactly how much each one contributes to the final flavor, nor do you know how they taste when mixed together.

In the world of computer science and economics, this "recipe" is called a Set Function. It tells us the value of any possible combination of items. For example, in a business, it might tell you the profit of a specific team of employees. In AI, it might tell you how much a specific group of features improves a machine learning model.

The problem? If you have 10 ingredients, there are over 1,000 possible combinations. If you have 20, there are over a million. Checking every single combination is impossible; it would take too much time and money (like retraining a massive AI model for every single team arrangement).

This paper is about a smart strategy to figure out the recipe with the fewest possible taste tests.

The Core Problem: The "Guessing Game"

Usually, when we don't know the full recipe, we have to guess.

• The "Best Guess" (Upper Bound): We assume the ingredients are super powerful when mixed. Maybe Team A + Team B is worth more than the sum of their parts.
• The "Worst Guess" (Lower Bound): We assume the ingredients are weak together. Maybe Team A + Team B is worth less than the sum of their parts.

The difference between your "Best Guess" and your "Worst Guess" is called Divergence.

• High Divergence: You are very confused. Your guesses range from "This team is a goldmine" to "This team is a disaster."
• Low Divergence: You are confident. Your guesses are close together.

The goal of this paper is to minimize this confusion by asking the right questions (queries) to get the most information for the least cost.

The "Subadditive" Rule

The paper focuses on a specific type of recipe called Subadditive.
Think of it like this: In a subadditive world, 1 + 1 is never greater than 2.

• If you have a team of 5 people, adding a 6th person might help, but it won't magically make the whole team worth more than the sum of the two separate groups.
• This is common in real life: Buying two items together usually doesn't cost more than buying them separately (no "complementarity" magic).

The Three Big Ideas

1. Tightening the Box (The "Fence" Analogy)

Imagine the true value of a team is hidden inside a box.

• The Lower Fence: The minimum value the team could possibly have.
• The Upper Fence: The maximum value the team could possibly have.
• The Gap: The space between the fences (the Divergence).

The authors figured out that if you know the team follows specific rules (like being "Subadditive" or "Monotone" where adding people never hurts), you can build tighter fences.

• Analogy: If you know a cake recipe must use flour, you don't need to guess if it uses sand. You can immediately lower the "Upper Fence" for the sand ingredient to zero.
• The paper provides mathematical formulas to build these tighter fences for different types of "recipes" (classes of functions), making the gap between your best and worst guesses much smaller without asking any new questions.

2. The Smart Detective (Offline vs. Online)

Now that we have better fences, how do we choose which ingredients to taste-test next?

• The Offline Detective (The Planner):
  Imagine you have a map of all possible recipes (a "prior distribution"). You can plan your entire investigation before you start.

  • Strategy: "I will test ingredients A, B, and C in that specific order because, statistically, that will close the gap the fastest."
  • Result: The paper shows a "Greedy" planner (who picks the best next step one by one) works almost as well as the perfect planner, but is much faster to compute.

• The Online Detective (The Learner):
  Imagine you don't have a map. You have to learn as you go. You taste one ingredient, see how it changes your guess, and then decide what to taste next.

  • Strategy: The authors used Reinforcement Learning (like training a video game AI). The AI plays the game of "guessing the recipe" thousands of times. It learns that asking about "Team A" first usually gives it a huge clue, while asking about "Team Z" is a waste of time.
  • Result: For smaller problems, this AI learns to be incredibly efficient, often beating the random guessers by a huge margin.

3. The "Random" Trap

The paper tested a simple strategy: Just pick random teams to test.

• Surprise: Random guessing actually works okay! This is because real-world recipes usually have structure.
• However: The smart strategies (Planner and AI Learner) consistently beat random guessing. They reduce the confusion (Divergence) much faster. It's the difference between wandering aimlessly in a maze versus using a compass.

Why Does This Matter?

This isn't just about math puzzles. It solves real-world headaches:

1. AI Explainability: If you want to know why an AI rejected a loan application, you need to know the value of specific features (e.g., "Income" + "Credit Score"). Calculating this usually requires retraining the AI model, which is expensive. This paper helps you pick the fewest features to retrain to get a clear answer.
2. Fair Pay: If you want to know how much a specific group of employees contributes to a company, you can't fire everyone and rehire them to test. You have to estimate. This method helps managers get a fair estimate of contribution with minimal disruption.
3. Auctions: In complex auctions, bidders need to know the value of bundles of items. This helps them bid efficiently without calculating every single possibility.

The Takeaway

The paper teaches us that not all questions are created equal.
When you are trying to understand a complex system (like a team, a machine learning model, or a market), you don't need to know everything to get a good answer. By understanding the rules of the system (like "adding people doesn't magically multiply value") and using smart strategies to pick your next question, you can shrink your uncertainty rapidly.

It's the difference between trying to learn a language by reading every book in the library, versus asking a native speaker the 10 most important questions to get by. The paper gives you the list of those 10 questions.

Technical Summary

1. Problem Formulation

The paper addresses the challenge of learning an unknown subadditive set function $f: 2^N \to \mathbb{R}$ when only a limited number of subset values can be queried.

• Context: In applications like combinatorial auctions, explainable AI (e.g., SHAP values), and cooperative game theory, determining the value of every subset is computationally prohibitive ($2^n$ values). Often, values are derived from expensive processes (e.g., retraining ML models).
• The Gap: When values are missing, there is ambiguity regarding the true function. This ambiguity is quantified as the divergence between the lower completion (the tightest possible lower bound) and the upper completion (the tightest possible upper bound) of the function, given the known values and the assumption that the function belongs to a specific class $\mathcal{C}_n$ (e.g., subadditive, XOS, etc.).
• Objective: Given a fixed budget of $k$ queries, select a subset of queries $K^*$ to minimize the expected additive error (divergence) across all subsets, rather than the multiplicative error used in many prior works.
• Setting: The problem is modeled as an active learning task where a "principal" (e.g., a manager or engineer) selects queries based on a prior distribution $\mathcal{F}$ over possible functions. The authors study both offline (selecting all $k$ queries at once) and online (sequentially selecting queries based on previous results) scenarios.

2. Methodology

A. Theoretical Framework: Tight Completions

The core theoretical contribution is the derivation of tight upper and lower completion functions for various subclasses of subadditive functions. These completions define the bounds within which the true function value must lie.

• Hierarchy of Classes: The authors establish a hierarchy of increasingly restrictive classes, yielding tighter bounds:
  $$\text{Submodular (SSn)} \subset \text{Concave Additive (CAn)} \subset \text{SCMM} \subset \text{XOS} \subset \text{Subadditive Monotone (SAMn)} \subset \text{Subadditive (Sn)}$$
• Key Derivations:
  • Subadditive ($S_n$): Uses Masuya and Inuiguchi's results. The upper bound is the minimum sum of known disjoint subsets covering $S$; the lower bound is derived from the complement.
  • Subadditive Monotone ($SAM_n$): Introduces a new characterization where the union of subsets need not be disjoint but must cover $S$. They propose an iterative algorithm to compute these bounds efficiently, trading slight tightness for tractability.
  • Fractionally Subadditive / XOS: Utilizes the property that XOS functions are the maximum of additive functions. The upper bound is derived via linear programming duality (fractional covering).
  • SCMM & Symmetric Submodular ($SS_n$): For functions depending only on set cardinality or concave transformations of additive functions, the bounds are derived via linear interpolation of the underlying concave function $g(|S|)$.
• Divergence Properties: The paper proves that the divergence measure is monotonically non-increasing, subadditive, and normalizable. Crucially, they show that for $n \le 4$, the divergence is supermodular for certain classes, allowing for approximation guarantees in greedy selection.

B. Algorithms for Query Selection

To minimize divergence, the authors propose three algorithms:

1. OFFLINE OPTIMAL: An exhaustive search that evaluates every possible combination of $t$ queries. It estimates the expected divergence by sampling $\kappa$ functions from the prior $\mathcal{F}$.
   • Complexity: Exponential in the number of subsets. Feasible only for small $n$ (e.g., $n \le 5$).
2. OFFLINE GREEDY: A greedy heuristic that iteratively selects the subset that minimizes the expected divergence given the previously selected subsets.
   • Complexity: Significantly faster than optimal; performs near-optimally for small $n$.
3. PPO (Proximal Policy Optimization): An online reinforcement learning approach. The agent learns a policy to select the next subset based on the history of observed values to maximize the cumulative reward (negative divergence).
   • Mechanism: Uses a neural network actor-critic architecture trained over millions of steps.

3. Key Contributions

1. Additive Error Focus: Shifts the paradigm from multiplicative approximation (which has known inapproximability results for subadditive functions) to additive error minimization, which is more relevant for applications like fair valuation and risk modeling.
2. Tight Completion Characterization: Provides explicit formulas and algorithms for computing tight upper and lower bounds for a hierarchy of subadditive function classes ($S_n, SAM_n, XOS_n, SCMM_n, SS_n$).
3. Divergence Analysis: Proves that knowing the function belongs to a stricter subclass (e.g., XOS vs. general Subadditive) can reduce divergence from exponential to zero in specific cases.
4. Algorithmic Solutions: Develops and evaluates both offline (greedy/optimal) and online (RL-based) strategies for active querying.

4. Experimental Results

The authors evaluated their methods on three distributions:

• submod-neg: Monotonically decreasing submodular functions.
• xos-6: XOS functions formed by the max of 6 random additive functions.
• sam-covg: Functions derived from set cover problems.

Findings:

• Performance: Both OFFLINE GREEDY and PPO significantly outperform a random baseline.
• Small $n$ ($n=5$): OFFLINE GREEDY performs nearly as well as the computationally expensive OFFLINE OPTIMAL. PPO slightly outperforms GREEDY by leveraging sequential information.
• Large $n$ ($n=10$): OFFLINE OPTIMAL is infeasible. PPO struggles to generalize due to the high-dimensional action space and continuous observations, performing worse than OFFLINE GREEDY.
• Structure Matters: The "RANDOM" baseline performed surprisingly well, suggesting that the distributions have strong internal structure that is easily captured even by chance, but informed selection (Greedy/PPO) consistently reduces divergence faster.
• Comparison to Sketching: When compared to the Cohavi–Dobzinski Sketching Algorithm (CDSA) for multiplicative error, the proposed OFFLINE GREEDY approach achieved tighter approximation ratios under the same query budget.

5. Significance

• Practical Applicability: The work is highly relevant for scenarios where data acquisition is costly (e.g., retraining deep learning models for SHAP values or rearranging corporate teams for performance evaluation). It provides a principled way to decide which data points are most valuable to acquire.
• Theoretical Insight: It bridges the gap between cooperative game theory (divergence/uncertainty) and machine learning (active learning), offering a rigorous framework for handling incomplete set functions.
• Scalability: While the problem is inherently exponential, the decomposition of the divergence calculation and the effectiveness of greedy heuristics make the approach viable for practical problem sizes where $n$ is moderate (e.g., 10-20 items).

In summary, the paper establishes that by leveraging structural assumptions (subclasses of subadditivity) and active querying strategies, one can significantly reduce the uncertainty (divergence) of incomplete set functions, offering a robust alternative to passive learning or random sampling.