Streaming adaptive submodular maximization

Adaptive submodular maximization has been extensively studied in the literature. However, most of existing studies in this field focus on pool-based setting, where one is allowed to pick items in any order, and there have been few studies for the stream-based setting where items arrive in an arbitrary order and one must immediately decide whether to select an item or not upon its arrival. In this paper, we introduce a new class of utility functions, semi-policywise submodular functions. We develop a series of effective algorithms to maximize a semi-policywise submodular function under the stream-based setting.