# A Stochastic Probing Problem with Applications

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

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 24 Feb 2013.

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

- [Bandit Algorithms for Prophet Inequality and Pandora's Box](https://mlsanity.com/paper/2211.08586/) (2022)
- [Online Learning for Min Sum Set Cover and Pandora's Box](https://mlsanity.com/paper/2202.04870/) (2022)
- [Batched Dueling Bandits](https://mlsanity.com/paper/2202.10660/) (2022)
- [Semi-Bandit Learning for Monotone Stochastic Optimization](https://mlsanity.com/paper/2312.15427/) (2023)
- [Contextual Pandora's Box](https://mlsanity.com/paper/2205.13114/) (2022)
- [Approximating Pandora's Box with Correlations](https://mlsanity.com/paper/2108.12976/) (2021)
- [An Asymptotically Optimal Batched Algorithm for the Dueling Bandit Problem](https://mlsanity.com/paper/2209.12108/) (2022)
- [Fully Dynamic Online Selection through Online Contention Resolution Schemes](https://mlsanity.com/paper/2301.03099/) (2023)
- [Stochastic Multi-round Submodular Optimization with Budget](https://mlsanity.com/paper/2404.13737/) (2024)
- [T-TAMER: Provably Taming Trade-offs in ML Serving](https://mlsanity.com/paper/2509.22992/) (2025)
- [Online Convex Optimization with Sublinear Noisy Probes](https://mlsanity.com/paper/2606.14640/) (2026)

## Abstract (arXiv)

We study a general stochastic probing problem defined on a universe V, where each element e in V is "active" independently with probability pe. Elements have weights we and the goal is to maximize the weight of a chosen subset S of active elements. However, we are given only the pe values-- to determine whether or not an element e is active, our algorithm must probe e. If element e is probed and happens to be active, then e must irrevocably be added to the chosen set S; if e is not active then it is not included in S. Moreover, the following conditions must hold in every random instantiation: (1) the set Q of probed elements satisfy an "outer" packing constraint, and (2) the set S of chosen elements satisfy an "inner" packing constraint. The kinds of packing constraints we consider are intersections of matroids and knapsacks. Our results provide a simple and unified view of results in stochastic matching and Bayesian mechanism design, and can also handle more general constraints. As an application, we obtain the first polynomial-time Omega(1/k)-approximate "Sequential Posted Price Mechanism" under k-matroid intersection feasibility constraints.