Adaptive Regularized Submodular Maximization

In this paper, we study the problem of maximizing the difference between an adaptive submodular (revenue) function and a non-negative modular (cost) function. The input of our problem is a set of n items, where each item has a particular state drawn from some known prior distribution The revenue function g is defined over items and states, and the cost function c is defined over items, i.e., each item has a fixed cost. The state of each item is unknown initially and one must select an item in order to observe its realized state. A policy π specifies which item to pick next based on the observations made so far. Denote by gavg(π) the expected revenue of π and let cavg(π) denote the expected cost of π. Our objective is to identify the best policy π^o ∈ arg maxπ gavg(π) - cavg(π) under a k-cardinality constraint. Since our objective function can take on both negative and positive values, the existing results of submodular maximization may not be applicable. To overcome this challenge, we develop a series of effective solutions with performance guarantees. Let π^o denote the optimal policy. For the case when g is adaptive monotone and adaptive submodular, we develop an effective policy π^l such that gavg(π^l) - cavg(π^l) ≥ (1 - ¹_e - ϵ)gavg(π^o) - cavg(π^o), using only O(nϵ^-2 log ϵ^-1) value oracle queries. For the case when g is adaptive submodular, we present a randomized policy π^r such that gavg(π^r) - cavg(π^r) ≥ ¹_e gavg(π^o) - cavg(π^o).