Bounded MAB: Optimizing Expert Crowdsourcing Beyond the "Winner-Takes-All" Fallacy

TL;DR

While traditional crowdsourcing focuses on cheap "micro-tasks," hiring experts (web designers, software engineers) involves high costs and strict time limits. This paper introduces the Bounded MAB model and the Bounded ε-first algorithm. By merging bandit theory with knapsack optimization, it achieves up to 300% better utility than traditional methods by intelligently distributing tasks across a portfolio of experts rather than hunting for a single "unicorn" worker.

The Problem: The Capacity Limit of Experts

In platforms like Amazon Mechanical Turk, we assume workers are an infinite resource. However, in Expert Crowdsourcing (e.g., oDesk/Upwork), two harsh realities collide:

1. Heterogeneity: A developer charging $100/hrmightbe10xfasterthanonecharging$10/hr, but their true quality is unknown until they start working.
2. Boundedness: Every expert has a "task limit" ($L_i$). You cannot buy 1,000 hours from a specialist who only has 10 hours available.

Existing Budget-limited MAB algorithms often converge on the single best worker. In the expert world, that worker's "capacity" is exhausted almost instantly, leaving the employer with no strategy for the rest of the budget.

Methodology: From Bandit Exploration to Knapsack Exploitation

The authors propose a clean, two-phase architectural split:

1. Uniform Exploration Phase

The agent spends a fraction of the budget ($ϵB$) pulling all "arms" (hiring all applicant workers) equally. The goal isn't just to find the best worker, but to estimate the quality-cost density (${\mu }_i/c_i$) for the entire pool.

2. Bounded Knapsack Exploitation

Once estimates (${\hat{\mu }}_i$) are gathered, the problem shifts from "learning" to "planning." The algorithm solves the following optimization:

• Maximize: Total Utility $\sum {\hat{\mu }}_i{x}_i$
• Subject to: Total Cost $\sum c_i{x}_i\le (1-ϵ)B$
• Constraint: Task limits $x_i\le L_i-x_{explore}$

Since the Bounded Knapsack Problem is NP-hard, the authors use Bounded Greedy logic: they sort workers by ${\hat{\mu }}_i/c_i$ and fill the capacity of the highest-density workers first until the budget or their task limit is hit.

The workflow highlights the critical transition from sampling unknown performance to solving a constrained optimization problem.

Theoretical Achievement: The $O(B^{2/3})$ Regret

One of the paper's strongest contributions is proving that even with the approximation used in the exploitation phase, the regret (the gap between this algorithm and a perfect-information oracle) is bounded by $O(B^{2/3})$. As the budget $B$ grows, the average regret drops to zero.

The authors also compare this to Successive Rejects (SR) exploration. Surprisingly, uniform exploration proves superior here because the "Greedy" exploitation phase requires a accurate ranking of many top arms, not just identifying the single best one.

Results: 300% Gains in the Real World

Using 30,000+ Java experts' data from oDesk, the authors simulated project allocations.

• Small Budgets ($500): All algorithms perform similarly as there is little room for "strategy."
• Large Budgets ($30,000+): Bounded ε-first dominates. While "Trialsourcing" or standard MABs stall after the first worker hits their limit, Bounded ε-first transitions seamlessly to the next best experts.

In large-budget scenarios, the gap between Bounded ε-first and traditional MABs (which neglect task limits) widens significantly.

Critical Insight: Why "Simple" Works

The beauty of this work lies in its "ε-first" simplicity. While more complex algorithms like KUBE (which solves knapsacks at every single step) exist, they are computationally ruinous for large projects. This paper proves that in budget-limited settings, exploring first and then solving a fixed optimization is not just faster—it is theoretically sound and practically superior.

Conclusion

The Bounded MAB framework is a vital shift toward "Portfolio-based" AI decision-making. Whether you are hiring a dev team, procuring medical supplies, or allocating cloud computing instances, you cannot rely on a single source. You must learn the landscape and then fill your "knapsack" with the most efficient combination of limited resources.