Submodular Learning and Covering with Response-Dependent Costs
This work addresses cost-sensitive decision-making in interactive scenarios, offering incremental improvements to existing methods.
The paper tackles interactive learning and covering problems where action costs depend on responses, proposing a greedy algorithm with bounded approximation factors for both active learning and general settings, and shows it is near-optimal among greedy algorithms.
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.