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 semi adaptive
policy that with $O(\log n \times\log k)$ adaptive rounds of observations can
achieve an almost tight $1-1/e-\epsilon$ approximation guarantee with respect
to an optimal policy that carries out $k$ actions in a fully sequential manner.
To complement our results, we also show that it is impossible to achieve a
constant factor approximation with $o(\log n)$ adaptive rounds. We also extend
our result to the case of adaptive stochastic minimum cost coverage where the
goal is to reach a desired utility $Q$ with the cheapest policy. We first prove
the conjecture of the celebrated work of Golovin and Krause by showing that the
greedy policy achieves the asymptotically tight logarithmic approximation
guarantee without resorting to stronger notions of adaptivity. We then propose
a semi adaptive policy that provides the same guarantee in polylogarithmic
adaptive rounds through a similar information-parallelism scheme. Our results
shrink the adaptivity gap in adaptive submodular maximization by an exponential
factor.

本文提出了半自适应策略，用于最大化自适应单调次模函数，能够实现几乎完美的近似保证，并将自适应次模最大化策略的适应性差距缩小了指数级别。