2025/04/22 by Jian Li, Yinchen Liu, Li, Jian +3
Computer Science · Decision Sciences · #Auction Theory and Applications #Data Stream Mining Techniques #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.2504.15547
openalex publication_date 2025/04/22 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study the stochastic probing problem under a general monotone norm objective. Given a ground set U = [n], each element i ∈ U has an independent nonnegative random variable Xi with known distribution. Probing an element reveals its value, and the sequence of probed elements must satisfy a prefix-closed feasibility constraint F. A monotone norm f: ℝ≥ 0n → ℝ≥ 0 determines the reward f(XP), where P is the set of probed elements and XP is the vector with Xi for i ∈ P and 0 otherwise. The goal is to design a probing strategy maximizing the expected reward 𝔼[f(XP)]. 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(log2 n). A refined analysis yields an improved bound of O(log r log n / loglog n), where r is the maximum size of a feasible probing sequence. As a by-product, we derive an asymptotically tight adaptivity gap Θ( log n/loglog n) for Bernoulli probing with binary-XOS objectives, matching the known lower bound. Additionally, we show an O(log3 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].