Submodular Learning and Covering with Response-Dependent Costs
  We consider interactive learning and covering problems, in a setting where
actions may incur different costs, depending on the response to the action. We
propose a natural greedy algorithm for response-dependent costs. We bound the
approximation factor of this greedy algorithm in active learning settings as
well as in the general setting. We 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 among all greedy algorithms. Experiments demonstrate
the advantages of the proposed algorithm in the response-dependent cost
setting.
