Non-monotone Adaptive Submodular Maximization (extended version with supplementary material)

A wide range of AI problems, such as sensor place-ment, active learning, and network influence max-imization, require sequentially selecting elements from a large set with the goal of optimizing the util-ity of the selected subset. Moreover, each element that is picked may provide stochastic feedback, which can be used to make smarter decisions about future selections. Finding efficient policies for this general class of adaptive optimization problems can be extremely hard. However, when the objective function is adaptive monotone and adaptive sub-modular, a simple greedy policy attains a 1 − 1/e approximation ratio in terms of expected utility. Unfortunately, many practical objective functions are naturally non-monotone; to our knowledge, no existing policy has provable performance guaran-tees when the assumption of adaptive monotonicity is lifted. We propose the adaptive random greedy policy for maximizing adaptive submodular func-tions, and prove that it retains the aforementioned 1 − 1/e approximation ratio for functions that are also adaptive monotone, while it additionally pro-vides a 1/e approximation ratio for non-monotone adaptive submodular functions. We showcase the benefits of adaptivity on three real-world network data sets using two non-monotone functions, repre-sentative of two classes of commonly encountered non-monotone objectives