Adaptivity in Adaptive Submodularity

Adaptive sequential decision making is one of the central challenges in machine learning and artificial intelligence. In such problems, the goal is to design an interactive policy that plans for an action to take, from a finite set of n actions, given some partial observations. It has been shown that in many applications such as active learning, robotics, sequential experimental design, and active detection, the utility function satisfies adaptive submodularity, a notion that generalizes the notion of diminishing returns to policies. In this paper, we revisit the power of adaptivity in maximizing an adaptive monotone submodular function. We propose an efficient batch policy that with O(log n log k) adaptive rounds of observations can achieve an almost tight (1-1/e-ϵ) approximation guarantee with respect to an optimal policy that carries out k actions in a fully sequential setting.