Name
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 $\pi$ specifies which item to pick next based on the observations made so far. Denote by $g_{avg}(\pi)$ the expected revenue of $\pi$ and let $c_{avg}(\pi)$ denote the expected cost of $\pi$. Our objective is to identify the best policy $\pi^o\in \arg\max_{\pi}g_{avg}(\pi)-c_{avg}(\pi)$ 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 $\pi^o$ denote the optimal policy. For the case when $g$ is adaptive monotone and adaptive submodular, we develop an effective policy $\pi^l$ such that $g_{avg}(\pi^l) - c_{avg}(\pi^l) \geq (1-\frac{1}{e}-\epsilon)g_{avg}(\pi^o) - c_{avg}(\pi^o)$, using only $O(n\epsilon^{-2}\log \epsilon^{-1})$ value oracle queries. For the case when $g$ is adaptive submodular, we present a randomized policy $\pi^r$ such that $g_{avg}(\pi^r) - c_{avg}(\pi^r) \geq \frac{1}{e}g_{avg}(\pi^o) - c_{avg}(\pi^o)$. |
Year | DOI | Venue |
|---|---|---|
2021 | 10.4230/LIPIcs.ISAAC.2021.69 | ISAAC |
DocType | Citations | PageRank |
Conference | 0 | 0.34 |
References | Authors | |
0 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Shaojie Tang | 1 | 1 | 3.39 |
| Jing Yuan | 2 | 237 | 11.92 |