Adaptive Regularized Submodular Maximization

Abstract

In this paper, we study the problem of maximizing the difference between an adaptive submodular (revenue) function and an non-negative modular (cost) function under the adaptive setting. The input of our problem is a set of n items, where each item has a particular state drawn from some known prior distribution p. 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, 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 g_avg() the expected revenue of and let c_avg() denote the expected cost of . Our objective is to identify the best policy ^o _g_avg()-c_avg() 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 grantees. 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 g_avg(^l) - c_avg(^l) (1-1e-)g_avg(^o) - c_avg(^o), using only O(n^-2 ^-1) value oracle queries. For the case when g is adaptive submodular, we present a randomized policy ^r such that g_avg(^r) - c_avg(^r) 1eg_avg(^o) - c_avg(^o).

Tasks

Reproductions