# Submodular Learning and Covering with Response-Dependent Costs

arXiv: https://arxiv.org/abs/1602.07120 · HTML: https://mlsanity.com/paper/1602.07120/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2016.

## Built on by (most cited first, 1 of 1)

- [Adaptive Combinatorial Maximization: Beyond Approximate Greedy Policies](https://mlsanity.com/paper/2404.01930/) (2024)

## Abstract (arXiv)

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.