Adaptivity Gaps for Stochastic Probing with Subadditive Functions

Abstract

In this paper, we study the stochastic probing problem under a general monotone norm objective. Given a ground set $U=[n]$, each element $i\in U$ has an independent nonnegative random variable $X_i$ with known distribution. Probing an element reveals its value, and the sequence of probed elements must satisfy a prefix-closed feasibility constraint $\mathcal{F}$. A monotone norm $f:{\mathbb{R}}_{\ge 0}^n\to {\mathbb{R}}_{\ge 0}$ determines the reward $f(X_P)$, where $P$ is the set of probed elements and $X_P$ is the vector with $X_i$ for $i\in P$ and 0 otherwise. The goal is to design a probing strategy maximizing the expected reward $\mathbb{E}[f(X_P)]$. We focus on the adaptivity gap: the ratio between the expected rewards of optimal adaptive and optimal non-adaptive strategies. We resolve an open question posed in [GNS17, KMS24], showing that for general monotone norms, the adaptivity gap is $O({\log }^{2}n)$. A refined analysis yields an improved bound of $O(\log r\log n/\log \log n)$, where $r$ is the maximum size of a feasible probing sequence. As a by-product, we derive an asymptotically tight adaptivity gap $\hat{I}˜(\log n/\log \log n)$ for Bernoulli probing with binary-XOS objectives, matching the known lower bound. Additionally, we show an $O({\log }^{3}n)$ upper bound for Bernoulli probing with general subadditive objectives. For monotone symmetric norms, we prove the adaptivity gap is $O(1)$, improving the previous $O(\log n)$ bound from [PRS23].

51 pages, 7 figures, To appear in FOCS 2025