Submodular Learning and Covering with Response-Dependent Costs

Abstract

We consider interactive learning and covering problems, in a setting where actions may incur different costs, depending on the outcomes of the action. For instance, in a clinical trial, selecting a patient for treatment might result in improved health or adverse effects for this patients, and these two outcomes have different costs. We consider a setting where these costs can be inferred from observable responses to the actions. We generalize previous analyses of interactive learning and covering to \emph{consistency aware} submodular objectives, and propose a natural greedy algorithm for the setting of response-dependent costs. We bound the approximation factor of this greedy algorithm, for general submodular functions, as well as specifically for \emph{learning objectives}, and show that a different property of the cost function controls the approximation factor in each of these scenarios. We further show that in both settings, the approximation factor of this greedy algorithm is near-optimal in the class of greedy algorithms. Experiments demonstrate the advantages of the proposed algorithm in the response-dependent cost setting.