Adaptivity Gaps for Stochastic Probing with Subadditive Functions

In this paper, we study the stochastic probing problem under a general monotone norm objective. We are given a ground set $U=[n]=\{1,2, \ldots, n\}$, where each element i is associated with an independent nonnegative random variable $X_{i}$ (with a known distribution). We may probe these elements adaptively, and upon probing an element i, its value $X_{i}$ is realized. The sequence of probed elements must satisfy a prefix-closed feasibility constraint $\mathcal{F}$, such as a matroid, an orienteering constraint, or any other downward-closed constraint. We also have a monotone norm function $f: \mathbb{R}_{\geq 0}^{n} \rightarrow \mathbb{R}_{\geq 0}$. Let $P \subseteq U$ be the set of probed elements. Then the reward is $f\left(X_{P}\right)$, where $X_{P}$ is an n-dimensional vector whose i-th coordinate equals the realized value of $X_{i}$ if $i \in P$ (i.e., element i is probed), and 0 otherwise. Our objective is to design a probing strategy that maximizes the expected reward $\mathbb{E}\left[f\left(X_{P}\right)\right]$. We study the adaptivity gap of the problem, defined as the ratio between the expected reward of an optimal adaptive strategy and that of an optimal non-adaptive strategy. A small adaptivity gap allows us to focus on designing nonadaptive strategies, which are typically simpler to represent and analyze. Establishing tight adaptivity gaps is a central challenge in stochastic combinatorial optimization and has been studied extensively for stochastic probing problems with various objective functions. In this paper, we resolve a central open problem in this line of research, posed in [1], [2], by proving that the adaptivity gap for stochastic probing with general monotone norms is bounded by $O\left(\log ^{2} n\right)$. With a refined analysis, we can further strengthen the bound to $O(\log r \log n / \log \log n)$ where r is the maximum length of a sequence in the feasibility constraint ($2 \leq r \leq n$). As a by-product, we obtain an asymptotically tight adaptivity gap $\Theta(\log n / \log \log n)$ for Bernoulli stochastic probing with binary-XOS objectives, matching the lower bound in [1]. We also obtain an $O\left(\log ^{3} n\right)$ upper bound for Bernoulli stochastic probing with general subadditive objectives. Furthermore, for monotone symmetric norms, we prove that the adaptivity gap can be bounded by $O(1)$, answering an open question posed in [3] and improving upon their $O(\log n)$ upper bound. Index Terms-stochastic probing, adaptivity gap, subadditive objective