Streaming Adaptive Submodular Maximization
This addresses a gap in sequential decision-making for applications requiring real-time item selection, though it appears incremental as it extends existing pool-based methods to streaming.
The paper tackles the problem of adaptive submodular maximization in a stream-based setting, where items arrive arbitrarily and decisions must be made immediately, by introducing semi-policywise submodular functions and developing effective algorithms to maximize them.
Many sequential decision making problems can be formulated as an adaptive submodular maximization problem. However, most of existing studies in this field focus on pool-based setting, where one can 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.