Lower Bound on the Greedy Approximation Ratio for Adaptive Submodular Cover

Adaptive-submodularity is a widely used framework in stochastic optimization and machine learning [GK11, GK17, EKM21, ACN22]. Here, an algorithm makes sequential decisions while (partially) observing uncertainty. We study a basic problem in this context: covering an adaptive-submodular function at the minimum expected cost. We show that the natural greedy algorithm for this problem has approximation ratio at least 1.3 (1 + ln Q), where Q is the maximal function value. This is in contrast to special cases such as deterministic submodular cover or (independent) stochastic submodular cover, where the greedy algorithm achieves a tight (1 + ln Q) approximation ratio.