2015

Tang et al.

Partial-Adaptive Submodular Maximization

Partial-Adaptive Submodular Maximization

Shaojie Tang Naveen Jindal School of Management, The University of Texas at
Dallas Jing Yuan Department of Computer Science, The University of Texas at
Dallas

The goal of a typical adaptive sequential decision making problem is to design
an interactive policy that selects a group of items sequentially, based on
some partial observations, to maximize the expected utility. It has been shown
that the utility functions of many real-world applications, including pooled-
based active learning and adaptive influence maximization, satisfy the
property of adaptive submodularity. However, most of existing studies on
adaptive submodular maximization focus on the fully adaptive setting, i.e.,
one must wait for the feedback from _all_ past selections before making the
next selection. Although this approach can take full advantage of feedback
from the past to make informed decisions, it may take a longer time to
complete the selection process as compared with the non-adaptive solution
where all selections are made in advance before any observations take place.
In this paper, we explore the problem of partial-adaptive submodular
maximization where one is allowed to make multiple selections in a batch
simultaneously and observe their realizations together. Our approach enjoys
the benefits of adaptivity while reducing the time spent on waiting for the
observations from past selections. To the best of our knowledge, no results
are known for partial-adaptive policies for the non-monotone adaptive
submodular maximization problem. We study this problem under both cardinality
constraint and knapsack constraints, and develop effective and efficient
solutions for both cases. We also analyze the batch query complexity, i.e.,
the number of batches a policy takes to complete the selection process, of our
policy under some additional assumptions.

##  1 Introduction

Adaptive sequential decision making, where one adaptively makes a sequence of
selections based on the stochastic observations collected from the past
selections, is at the heart of many machine learning and artificial
intelligence tasks. For example, in experimental design, a practitioner aims
to perform a series of tests in order maximize the amount of “information”
that can be obtained to yield valid and objective conclusions. It has been
shown that in many real-world applications, including pool-based active
learning Golovin and Krause (2011), sensor selection Asadpour and Nazerzadeh
(2016), and adaptive viral marketing Tang and Yuan (2020), the utility
function is adaptive submodular. Adaptive submodularity a notion that
generalizes the notion of submodularity from sets to policies. The goal of
adaptive submodular maximization is to design an interactive policy that
adaptively selects a group of items, where each selection is based on the
feedback from the past selections, to maximize an adaptive submodular function
subject to some practical constraints. Although this problem has been
extensively studied in the literature, most of existing studies focus on the
fully adaptive setting where every selection must be made after observing the
feedback from _all_ past selections. This fully adaptive approach can take
full advantage of feedback from the past to make informed decisions, however,
as a tradeoff, it may take a longer time to complete the selection process as
compared with the non-adaptive solution where all selections are made in
advance before any observations take place. This is especially true when the
process of collecting the observations from past selections is time consuming.
In this paper, we study the problem of partial-adaptive submodular
maximization where one is allowed to make multiple selections simultaneously
and observe their realizations together. Our setting generalizes both non-
adaptive setting and fully adaptive setting. As compared with the fully
adaptive strategy, our approach enjoys the benefits of adaptivity while using
fewer number of batches. To the best of our knowledge, no results are known
for partial-adaptive policies for the non-monotone adaptive submodular
maximization problem. We next summarize the main contributions made in this
paper.

  * •

We first study the partial-adaptive submodular maximization problem subject to
a cardinality constraint. We develop a partial-adaptive greedy policy that
achieves a $\alpha/e$ approximation ratio against the optimal fully adaptive
policy where $\alpha$ is the _degree of adaptivity_ of our policy. One can
balance the the performance/adaptivity tradeoff through adjusting the value of
$\alpha$. In particular, if we set $\alpha=1$, our policy reduces to a non-
adaptive policy, and if we set $\alpha=1$, our policy reduces to a fully
adaptive policy.

  * •

For the partial-adaptive submodular maximization problem subject to a knapsack
constraint, we develop a sampling based partial-adaptive policy that achieves
an approximation ratio of $\frac{\min\\{1/2,\alpha\\}}{6+\min\\{1,2\alpha\\}}$
with respect to the optimal fully adaptive policy.

  * •

We theoretically analyze the batch query complexity of our policy and show
that if the utility function is policywise submodular, a stronger assumption
than adaptive submodularity, then the above sampling based partial-adaptive
policy takes at most $O(\log n\log\frac{B}{c_{\min}})$ number of batches to
achieve a constant approximation ratio where $B$ is the budget constraint and
$c_{\min}$ is the cost of the cheapest item. It was worth noting that if we
consider a cardinality constraint $k$, then $O(\log n\log\frac{B}{c_{\min}})$
is upper bounded by $O(\log n\log k)$ which is polylogarithmic.

##  2 Related Work

Maximizing a submodular function subject to various practical constraints has
been extensively studied in the literature Nemhauser et al. (1978),
Badanidiyuru and Vondrák (2014), Buchbinder et al. (2014). However, the
classic notation of submodularity is not capable of capturing the interactive
nature of many adaptive sequential decision making problems. Recently, Golovin
and Krause (2011) extends this notation from sets to policies by proposing the
concept of adaptive submodularity. Intuitively, it states that if a function
is adaptive submodular, then the expected marginal benefit of an item never
increases as we collect more observations from past selections. They show that
if a function is adaptive monotone and adaptive submodular, then a simple
adaptive greedy policy achieves a $(1-1/e)$ approximation ratio. For
maximizing a non-monotone adaptive submodular function, Tang (2021a) show that
a randomized greedy policy achieves a $1/e$ approximation ratio. Unlike most
of existing studies on adaptive submodular maximization which is conducted
under the fully adaptive setting, our focus is on partial-adaptive (a.k.a
batch-mode) setting.

Recently, there are a few results that are related to partial-adaptive
submodular maximization. Chen and Krause (2013) propose a policy that selects
batches of fixed size $r$, and they show that their policy achieves a bounded
approximation ratio compare to the optimal policy which is restricted to
selecting batches of fixed size $r$. However, their approximation ratio
becomes arbitrarily bad with respect to the optimal fully adaptive policy. In
the context of adaptive viral marketing, Yuan and Tang (2017) develop a
partial-adaptive seeding policy that achieves a bounded approximation ratio
against the optimal fully adaptive seeding policy. Our study is similar to
theirs in that both studies introduce a controlling parameter to balance the
performance/adaptivility tradeoff. However, their results can not be extended
to solve a general adaptive submodular maximization problem. Moreover, unlike
the batch-mode setting, their model allows for observing a partial realization
of an item during the selection process. Tang and Yuan (2020) extends the
above study by developing a new partial-adaptive seeding policy subject to a
general knapsack constraint. Their design is general enough to be applied to
other adaptive submodular maximization problems. Very recently, Esfandiari et
al. (2021) study the batch-mode monotone adaptive submodular optimization
problem and they develop an efficient semi adaptive policy that achieves an
almost tight $1-1/e-\epsilon$ approximation ratio. To the best of our
knowledge, all existing studies are focusing on maximizing a monotone adaptive
submodular function. We are the first to study the non-monotone partial-
adaptive submodular maximization problem subject to both cardinality and
knapsack constraints. We also provide a rigorous analysis of the batch query
complexity of our policy.

##  3 Preliminaries and Problem Formulation

###  3.1 Items and States

The input of our problem is a set $E$ of $n$ items (e.g., tests in
experimental design). Each items $e\in E$ has a random state $\Phi(e)\in O$
where $O$ is a set of all possible states. Let $\phi(e)\in O$ denote a
realization of $\Phi(e)$. Thus, a _realization_ $\phi$ is a mapping function
that maps items to states: $\phi:E\rightarrow O$. In the example of
experimental design, the item $e$ may represent a test, such as the
temperature, and $\Phi(e)$ is the result of the test, such as,
$38\text{\,}\mathrm{\SIUnitSymbolCelsius}$. There is a known prior probability
distribution $p(\phi)=\Pr(\Phi=\phi)$ over realizations $\phi$. When
realizations are independent, the distribution $p$ completely factorizes.
However, in many real-world applications such as active learning, the
realizations of items may depend on each other. For any subset of items
$S\subseteq E$, let $\psi:S\rightarrow O$ denote a _partial realization_ and
$\mathrm{dom}(\psi)=S$ is called the _domain_ of $\psi$. Consider a partial
realization $\psi$ and a realization $\phi$, we say $\phi$ is consistent with
$\psi$, denoted $\phi\sim\psi$, if they are equal everywhere in
$\mathrm{dom}(\psi)$. Moreover, consider two partial realizations $\psi$ and
$\psi^{\prime}$, we say that $\psi$ is a _subrealization_ of $\psi^{\prime}$,
and denoted by $\psi\subseteq\psi^{\prime}$, if
$\mathrm{dom}(\psi)\subseteq\mathrm{dom}(\psi^{\prime})$ and they agree
everywhere in $\mathrm{dom}(\psi)$. Let $p(\phi\mid\psi)$ represent the
conditional distribution over realizations conditional on a partial
realization $\psi$: $p(\phi\mid\psi)=\Pr[\Phi=\phi\mid\Phi\sim\psi]$. In
addition, there is an additive cost function $c(S)=\sum_{e\in S}c(e)$ for any
$S\subseteq E$.

###  3.2 Policies and Problem Formulation

A policy is a function $\pi$ that maps a set of partial realizations to some
distribution of $E$: $\pi:2^{E\times O}\rightarrow\mathcal{P}(E)$, specifying
which item to select next. By following a given policy, we can select items
adaptively based on our observations made so far. We next introduce two
additional notions related to policies Golovin and Krause (2011).

######  Definition 3.1 (Policy Concatenation)

Given two policies $\pi$ and $\pi^{\prime}$, let $\pi@\pi^{\prime}$ denote a
policy that runs $\pi$ first, and then runs $\pi^{\prime}$, ignoring the
observation obtained from running $\pi$.

######  Definition 3.2 (Level-$t$-Truncation of a Policy)

Given a policy $\pi$, we define its level-$t$-truncation $\pi_{t}$ as a policy
that runs $\pi$ until it selects $t$ items.

There is a utility function $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$
which is defined over items and states. Let $E(\pi,\phi)$ denote the subset of
items selected by $\pi$ under realization $\phi$. The expected utility
$f_{avg}(\pi)$ of a policy $\pi$ can be written as

$\displaystyle f_{avg}(\pi)=\mathbb{E}_{\Phi\sim
p,\Pi}[f(E(\pi,\Phi),\Phi)]~{}$

where the expectation is taken over possible realizations and the internal
randomness of the policy.

In this paper, we first study the problem of partial-adaptive submodular
maximization subject to a cardinality constraint $k$.

$\max_{\pi}\\{f_{avg}(\pi)\mid|E(\pi,\phi)|\leq k\mbox{ for all realizations
}\phi\\}$

Then we generalize this study to consider a knapsack constraint $B$.

$\max_{\pi}\\{f_{avg}(\pi)\mid c(E(\pi,\phi))\leq B\mbox{ for all realizations
}\phi\\}$

###  3.3 Adaptive Submodularity and Adaptive Monotonicity

We next introduce some additional notations that are used in our proofs.

######  Definition 3.3 (Conditional Expected Marginal Utility of an Item)

Given a utility function $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$, the
conditional expected marginal utility $\Delta(e\mid S,\psi)$ of an item $e$ on
top of a group of items $S\subseteq E$ conditional on a partial realization
$\psi$ is defined as follows

$\displaystyle\Delta(e\mid
S,\psi)=\mathbb{E}_{\Phi}[f(S\cup\\{e\\},\Phi)-f(S,\Phi)\mid\Phi\sim\psi]$ (1)

where the expectation is taken over $\Phi$ with respect to
$p(\phi\mid\psi)=\Pr(\Phi=\phi\mid\Phi\sim\psi)$.

######  Definition 3.4 (Conditional Expected Marginal Utility of a Policy)

Given a utility function $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$, the
conditional expected marginal utility $\Delta(\pi\mid S,\psi)$ of a policy
$\pi$ on top of a group of items $S\subseteq E$ conditional on a partial
realization $\psi$ is

$\Delta(\pi\mid S,\psi)=\mathbb{E}_{\Phi,\Pi}[f(S\cup
E(\pi,\Phi),\Phi)-f(S,\Phi)\mid\Phi\sim\psi]$

where the expectation is taken over $\Phi$ with respect to
$p(\phi\mid\psi)=\Pr(\Phi=\phi\mid\Phi\sim\psi)$ and the random output of
$\pi$.

Now we are ready to introduce the notations of adaptive submodularity and
adaptive monotone Golovin and Krause (2011). Intuitively, adaptive
submodularity is a generalization of the classic notation of submodularity
from sets to policies. This condition states that the expected marginal
benefit of an item never increases as we collect more observations from past
selections.

######  Definition 3.5 (Adaptive Submodularity and Adaptive Monotonicity)

A function $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$ is submodular
adaptive if for any two partial realizations $\psi$ and $\psi^{\prime}$ such
that $\psi\subseteq\psi^{\prime}$, the following holds for each $e\in
E\setminus\mathrm{dom}(\psi^{\prime})$:

$\displaystyle\Delta(e\mid\mathrm{dom}(\psi),\psi)\geq\Delta(e\mid\mathrm{dom}(\psi^{\prime}),\psi^{\prime})$
(2)

Moreover, we say a utility function $f:2^{E\times
O}\rightarrow\mathbb{R}_{\geq 0}$ is _adaptive monotone_ (Golovin and Krause
2011) if for any partial realization $\psi$ and any $e\in
E\setminus\mathrm{dom}(\psi)$: $\Delta(e\mid\mathrm{dom}(\psi),\psi)\geq 0$.

##  4 Cardinality Constraint

We first study the problem of partial-adaptive submodular maximization subject
to a cardinality constraint $k$. It has been shown that if the utility
function is adaptive submodular, then a fully adaptive greedy policy can
achieve a $1/e$ approximation ratio against the optimal fully adaptive policy
(Tang 2021a). However, one weakness about a fully adaptive policy is that one
must wait for the observations from all past selections before making a new
selection. To this end, we develop a _Partial-Adaptive Greedy Policy_
$\pi^{p}$ that allows to make multiple selections simultaneously within a
single batch. We show that $\pi^{p}$ achieves a $\alpha/e$ approximation ratio
with respect to the optimal fully adaptive policy where $\alpha\in[0,1]$ is
called _degree of adaptivity_. One can adjust the value of $\alpha$ to balance
the performance/adaptivity tradeoff.

###  4.1 Algorithm Design

We next explain the design of $\pi^{p}$ (a detailed implementation of
$\pi^{p}$ is listed in Algorithm 2). We first add a set $V$ of $2k-1$ dummy
items to the ground set, such that $\Delta(e\mid\mathrm{dom}(\psi),\psi)=0$
for any $e\in V$ and any partial realization $\psi$. Let $E^{\prime}=E\cup V$
denote the expanded ground set. These dummy items are added to avoid selecting
any item with negative marginal utility. Note that we can safely remove all
these dummy items from the solution without affecting its utility. For any
partial realization $\psi$ and any subset of items
$S\subseteq\mathrm{dom}(\psi)$, define $M(S,\psi)$ as a set of $k$ items that
have the largest marginal utility on top of $S$ conditional on $\psi$, i.e.,

$\displaystyle M(S,\psi)\in\argmax_{V\subseteq E^{\prime};|V|=k}\sum_{e\in
E^{\prime}}\Delta(e\mid S,\psi)$ (3)

For any iteration $t\in[k]$ of $\pi^{p}$, let $S_{t}$ denote the first $t$
items selected by $\pi^{p}$, let $b[t]$ denote the batch index of the $t$-th
item selected by $\pi^{p}$, i.e., the $t$-th item is selected in batch $b[t]$,
and let $S_{[q]}$ denote the set of selected items from batch $q$. Let
$\psi_{q}$ denote the partial realization of the first $q$ batches of items
selected by $\pi^{p}$, i.e.,
$\mathrm{dom}(\psi_{q})=\cup_{i\in[1,q]}{S_{[i]}}$. Set the initial solution
$S_{0}=\emptyset$ and the initial partial realization $\psi_{0}=\emptyset$.

  * •

Starting with the first iteration $t=1$.

  * •

In each iteration $t$, we compare $\sum_{e\in
M(S_{t-1},\psi_{b[t-1]-1})}\Delta(e\mid S_{t-1},\psi_{b[t-1]-1})$ with
$\alpha\cdot\sum_{e\in
M(\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})$,
then decide whether to start a new batch or not based on the result of the
comparison as follows.

    * –

If

$\displaystyle\sum_{e\in M(S_{t-1},\psi_{b[t-1]-1})}\Delta(e\mid
S_{t-1},\psi_{b[t-1]-1})\geq\alpha\cdot\sum_{e\in
M(\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1}),$
(4)

then $\pi^{p}$ chooses to stay with the current batch, i.e., $b[t]=b[t-1]$. It
samples an item $e_{t}$ uniformly at random from $M(S_{t-1},\psi_{b[t]-1})$,
which is identical to $M(S_{t-1},\psi_{b[t-1]-1})$ due to $b[t]=b[t-1]$, and
updates the solution $S_{t}$ using $S_{t-1}\cup\\{e_{t}\\}$. Move to the next
iteration $t=t+1$.

    * –

Otherwise, $\pi^{p}$ starts a new batch, i.e., $b[t]=b[t-1]+1$, and observe
the partial realization $\Phi(e)$ of all items $e$ from the previous batch
$S_{[b[t-1]]}$. Then it updates the observation $\psi_{b[t]-1}$ using
$\psi_{b[t-1]-1}\cup\\{(e,\Phi(e))\mid e\in S_{[b[t-1]]}\\}$. Note that
$S_{t-1}=\mathrm{dom}(\psi_{b[t]-1})$ in this case. At last, it samples an
item $e_{t}$ uniformly at random from $M(S_{t-1},\psi_{b[t]-1})$ and updates
the solution $S_{t}$ using $S_{t-1}\cup\\{e_{t}\\}$. Move to the next
iteration $t=t+1$.

  * •

The above process iterates until $\pi^{p}$ selects $k$ items (which may
include some dummy items).

_Remark:_ Note that $\sum_{e\in
M(\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})$
in (4) is an upper bound of $\sum_{e\in
M(S_{t-1},\psi_{b[t-1]-1})}\Delta(e\mid S_{t-1},\psi_{b[t-1]-1})$ due to
$\mathrm{dom}(\psi_{b[t-1]-1})\subseteq S_{t-1}$ and $f:2^{E\times
O}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular. Intuitively,
satisfying (4) ensures that the expected gain of each iteration is
sufficiently large to achieve a constant approximation ratio. Unlike some
other criteria proposed in previous studies (Tang and Yuan 2020, Esfandiari et
al. 2021), evaluating (4) is relatively easy since it does not involve the
calculation of the expectation of the maximum of $n$ random variables. Under
our framework, one can adjust the degree of adaptivity $\alpha\in[0,1]$ to
balance the performance/adaptivity tradeoff. In particular, choosing a smaller
$\alpha$ makes it easier to satisfy (4) and hence leads to fewer number of
batches but poorer performance. Consider an extreme case when $\alpha=0$,
$\pi^{p}$ takes only one batch to complete the selection process, i.e.,
$\pi^{p}$ reduces to a non-adaptive policy in this case. At the other extreme,
if we set $\alpha=1$, then our policy becomes fully adaptive.

Algorithm 1 Partial-Adaptive Greedy Policy $\pi^{p}$

1: $t=1;b[0]=1;\psi_{0}=\emptyset;S_{0}=\emptyset;\forall
i\in[n],S_{[i]}=\emptyset$.

2: while $t\leq k$ do

3: let $M(S_{t-1},\psi_{b[t-1]-1})\leftarrow\argmax_{V\subseteq
E^{\prime};|V|=k}\sum_{e\in E^{\prime}}\Delta(e\mid S_{t-1},\psi_{b[t-1]-1})$;

4: if $\sum_{e\in M(S_{t-1},\psi_{b[t-1]-1})}\Delta(e\mid
S_{t-1},\psi_{b[t-1]-1})\geq\alpha\cdot\sum_{e\in
M(\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})$
then

5: {stay in the current batch}

6: $b[t]=b[t-1]$;

7: sample $e_{t}$ uniformly at random from $M(S_{t-1},\psi_{b[t]-1})$;

8: $S_{t}=S_{t-1}\cup\\{e_{t}\\}$; $S_{[b[t]]}=S_{[b[t]]}\cup\\{e_{t}\\}$;

9: else

10: {start a new batch}

11: $b[t]=b[t-1]+1$;

12: observe $\\{(e,\Phi(e))\mid e\in S_{[b[t-1]]}\\}$;
$\psi_{b[t]-1}=\psi_{b[t-1]-1}\cup\\{(e,\Phi(e))\mid e\in S_{[b[t-1]]}\\}$;

13: let $M(S_{t-1},\psi_{b[t]-1})\leftarrow\argmax_{V\subseteq
E^{\prime};|V|=k}\sum_{e\in E^{\prime}}\Delta(e\mid S_{t-1},\psi_{b[t]-1})$;

14: sample $e_{t}$ uniformly at random from $M(S_{t-1},\psi_{b[t]-1})$;
$S_{t}=S_{t-1}\cup\\{e_{t}\\}$; $S_{[b[t]]}=S_{[b[t]]}\cup\\{e_{t}\\}$;

15: $t\leftarrow t+1$;

###  4.2 Performance Analysis

We next analyze the performance of $\pi^{p}$ against the optimal fully
adaptive strategy. The following main theorem shows that $\pi^{p}$ with degree
of adaptivity $\alpha$ achieves an approximation ratio of $\alpha/e$.

###### Theorem 4.1

If $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular,
then the Partial-Adaptive Greedy Policy $\pi^{p}$ with degree of adaptivity
$\alpha$ achieves a $\alpha/e$ approximation ratio in expectation.

The rest of this section is devoted to proving Theorem 4.1. We first present
two technical lemmas. Recall that for any iteration $t\in[k]$, $S_{t-1}$
represents the first $t-1$ selected items, $\psi_{b[t]-1}$ represents the
partial realization of all items selected from the first $b[t]-1$ batches, and
$M(S,\psi)\in\argmax_{V\subseteq E^{\prime};|V|=k}\sum_{e\in
E^{\prime}}\Delta(e\mid S,\psi)$.

###### Lemma 4.2

For each iteration $t\in[k]$, $\sum_{e\in
M(S_{t-1},\psi_{b[t]-1})}\Delta(e\mid
S_{t-1},\psi_{b[t]-1})\geq\alpha\cdot\sum_{e\in
M(\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})$.

_Proof:_ We prove this lemma in two cases.

  * •

If $b[t]=b[t-1]$, i.e., the $t-1$-th item and the $t$-th item are selected
within the same batch, then according to the design of $\pi^{p}$, it must be
the case that $\sum_{e\in M(S_{t-1},\psi_{b[t-1]-1})}\Delta(e\mid
S_{t-1},\psi_{b[t-1]-1})\geq\alpha\cdot\sum_{e\in
M(\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})$.
This together with $b[t]=b[t-1]$ implies that $\sum_{e\in
M(S_{t-1},\psi_{b[t-1]-1})}\Delta(e\mid
S_{t-1},\psi_{b[t-1]-1})\geq\alpha\cdot\sum_{e\in
M(\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})$.

  * •

Otherwise, if $b[t]=b[t-1]+1$, i.e., the $t-1$-th item and the $t$-th item are
selected within different batches, then we have
$\mathrm{dom}(\psi_{b[t]-1})=S_{t-1}$. Thus, $\sum_{e\in
M(S_{t-1},\psi_{b[t]-1})}\Delta(e\mid S_{t-1},\psi_{b[t]-1})=\sum_{e\in
M(\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})\geq\alpha\cdot\sum_{e\in
M(\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})$
where the inequality is due to $\alpha\leq 1$.

This finishes the proof of this lemma. $\Box$

The next lemma shows that for any iteration $t\in[k]$, the sum of expected
marginal benefits of all items from
$M(\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})$ is sufficiently high. This will
be used later to lower bound the expected gain of each iteration of our
policy.

###### Lemma 4.3

Let $\pi^{*}$ denote an optimal fully adaptive policy. In each iteration
$t\in[k]$, $\sum_{e\in
M(\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})\geq\Delta(\pi^{*}\mid
S_{t-1},\psi_{b[t]-1})$.

_Proof:_ Observe that for any $S_{t-1}$ and $\psi_{b[t]-1}$, the marginal
utility of the optimal policy $\pi^{*}$ on top of $S_{t-1}$ conditional on
$\psi_{b[t]-1}$ can be represented as

$\Delta(\pi^{*}\mid
S_{t-1},\psi_{b[t]-1})=\mathbb{E}_{\Phi\sim\psi_{b[t]-1}}[\Delta(\pi^{*}\mid
S_{t-1},\psi_{b[t]-1}\cup_{e\in
S_{t-1}\setminus\mathrm{dom}(\psi_{b[t]-1})}(e,\Phi(e)))]$

In the above equation, $\psi_{b[t]-1}\cup_{e\in
S_{t-1}\setminus\mathrm{dom}(\psi_{b[t]-1})}(e,\Phi(e))$ represents a random
realization of $S_{t-1}$ conditional on $\psi_{b[t]-1}$. For convenience, let
$\Phi(S_{t-1})$ denote $\psi_{b[t]-1}\cup_{e\in
S_{t-1}\setminus\mathrm{dom}(\psi_{b[t]-1})}(e,\Phi(e))$ for short. Then we
have

$\displaystyle\Delta(\pi^{*}\mid S_{t-1},\psi_{b[t]-1})$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\Phi\sim\psi_{b[t]-1}}[\Delta(\pi^{*}\mid
S_{t-1},\Phi(S_{t-1}))]$ (5) $\displaystyle\leq$
$\displaystyle\mathbb{E}_{\Phi\sim\psi_{b[t]-1}}[\sum_{e\in
M(S_{t-1},\Phi(S_{t-1}))}\Delta(e\mid S_{t-1},\Phi(S_{t-1}))]$ (6)
$\displaystyle\leq$
$\displaystyle\mathbb{E}_{\Phi\sim\psi_{b[t]-1}}[\sum_{e\in
M(S_{t-1},\Phi(S_{t-1}))}\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})]$
(7) $\displaystyle\leq$
$\displaystyle\mathbb{E}_{\Phi\sim\psi_{b[t]-1}}[\sum_{e\in
M(\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})]$
(8) $\displaystyle=$ $\displaystyle\sum_{e\in
M(\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})$
(9)

The first inequality is due to $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$
is adaptive submodular and Lemma 1 in (Gotovos et al. 2015). The second
inequality is due to $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$ is
adaptive submodular and $\psi_{b[t]-1}\subseteq\Phi(S_{t-1})$. $\Box$

Now we are ready to prove the main theorem. Let the random variable
$\mathcal{S}_{t-1}$ denote the first $t-1$ items selected by $\pi^{p}$ and let
the random variable $\Psi_{b[t]-1}$ denote the partial realization of the
first $b[t]-1$ batches of items selected by $\pi^{p}$. For any $t\in[k]$, we
next bound the expected marginal gain of the $t$-th iteration of $\pi^{p}$,

$\displaystyle f_{avg}(\pi^{p}_{t})-f_{avg}(\pi^{p}_{t-1})$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\mathcal{S}_{t-1},\Psi_{b[t]-1}}[\mathbb{E}_{e_{t}}[\Delta(e_{t}\mid\mathcal{S}_{t-1},\Psi_{b[t]-1})]]$
(10) $\displaystyle=$
$\displaystyle\frac{1}{k}\mathbb{E}_{\mathcal{S}_{t-1},\Psi_{b[t]-1}}[\sum_{e\in
M(\mathcal{S}_{t-1},\Psi_{b[t]-1})}\Delta(e\mid\mathcal{S}_{t-1},\Psi_{b[t]-1})]$
$\displaystyle\geq$
$\displaystyle\frac{1}{k}\mathbb{E}_{\mathcal{S}_{t-1},\Psi_{b[t]-1}}[\alpha\cdot\sum_{e\in
M(\mathrm{dom}(\Psi_{b[t]-1}),\Psi_{b[t]-1})}\Delta(e\mid\mathrm{dom}(\Psi_{b[t]-1}),\Psi_{b[t]-1})]$
$\displaystyle=$
$\displaystyle\frac{\alpha}{k}\mathbb{E}_{\mathcal{S}_{t-1},\Psi_{b[t]-1}}[\sum_{e\in
M(\mathrm{dom}(\Psi_{b[t]-1}),\Psi_{b[t]-1})}\Delta(e\mid\mathrm{dom}(\Psi_{b[t]-1}),\Psi_{b[t]-1})]$
$\displaystyle\geq$
$\displaystyle\frac{\alpha}{k}\mathbb{E}_{\mathcal{S}_{t-1},\Psi_{b[t]-1}}[\Delta(\pi^{*}\mid\mathcal{S}_{t-1},\Psi_{b[t]-1})]$
$\displaystyle=$
$\displaystyle\frac{\alpha}{k}(f_{avg}(\pi^{*}@\pi^{p}_{t-1})-f_{avg}(\pi^{p}_{t-1}))$
$\displaystyle\geq$
$\displaystyle\frac{\alpha}{k}((1-\frac{1}{k})^{t-1}f_{avg}(\pi^{*})-f_{avg}(\pi^{p}_{t-1}))$
(11)

The second equality is due to the fact that at each round $t\in[k]$, $\pi^{p}$
adds an item uniformly at random from $M(S_{t-1},\psi_{b[t]-1})$ to the
solution. The first inequality is due to Lemma 4.2. The second inequality is
due to Lemma 4.3. The last inequality is due to Lemma 1 in (Tang 2021a) where
they show that
$f_{avg}(\pi^{*}@\pi^{p}_{t-1})\geq(1-\frac{1}{k})^{t-1}f_{avg}(\pi^{*})$.

We next prove

$f_{avg}(\pi^{p}_{t})\geq\frac{\alpha
t}{k}(1-\frac{1}{k})^{t-1}f_{avg}(\pi^{*})$ (12)

by induction on $t$. For $t=0$, $f_{avg}(\pi^{p}_{0})\geq
0\geq\frac{\alpha\cdot 0}{k}(1-\frac{1}{k})^{0-1}f_{avg}(\pi^{*})$. Assume Eq.
(12) is true for $t^{\prime}<t$, let us prove it for $t$.

$\displaystyle f_{avg}(\pi^{p}_{t})$ $\displaystyle\geq$ $\displaystyle
f_{avg}(\pi^{p}_{t-1})+\frac{\alpha}{k}((1-\frac{1}{k})^{t-1}f_{avg}(\pi^{*})-f_{avg}(\pi^{p}_{t-1}))$
$\displaystyle=$
$\displaystyle(1-\alpha/k)f_{avg}(\pi^{p}_{t-1})+\frac{\alpha(1-\frac{1}{k})^{t-1}f_{avg}(\pi^{*})}{k}$
$\displaystyle\geq$
$\displaystyle(1-\alpha/k)\cdot(\alpha(t-1)/k)\cdot(1-1/k)^{t-2}\cdot
f_{avg}(\pi^{*})+\frac{\alpha(1-\frac{1}{k})^{t-1}f_{avg}(\pi^{*})}{k}$
$\displaystyle\geq$
$\displaystyle(1-1/k)\cdot(\alpha(t-1)/k)\cdot(1-1/k)^{t-2}\cdot
f_{avg}(\pi^{*})+\frac{\alpha(1-\frac{1}{k})^{t-1}f_{avg}(\pi^{*})}{k}$
$\displaystyle=$ $\displaystyle\frac{\alpha
t}{k}(1-\frac{1}{k})^{t-1}f_{avg}(\pi^{*})$

The first inequality is due to (11), the second inequality is due to the
inductive assumption. When $t=k$, we have
$f_{avg}(\pi^{p}_{t})\geq\alpha(1-1/k)^{k-1}\cdot
f_{avg}(\pi^{*})\geq(\alpha/e)f_{avg}(\pi^{*})$. This finishes the proof of
the main theorem.

_Remark:_ When the utility function $f:2^{E\times
O}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular and adaptive
monotone, Golovin and Krause (2011) show that
$f_{avg}(\pi^{*}@\pi^{p}_{t-1})\geq f_{avg}(\pi^{*})$ for all $t\in[k]$. Thus,
for all $t\in[k]$,

$\displaystyle f_{avg}(\pi^{p}_{t})-f_{avg}(\pi^{p}_{t-1})$
$\displaystyle\geq$
$\displaystyle\frac{\alpha}{k}(f_{avg}(\pi^{*}@\pi^{p}_{t-1})-f_{avg}(\pi^{p}_{t-1}))$
(13) $\displaystyle\geq$
$\displaystyle\frac{\alpha}{k}(f_{avg}(\pi^{*})-f_{avg}(\pi^{p}_{t-1}))$

The first inequality is due to (10). Through induction on $t$, we have
$f_{avg}(\pi^{p})\geq(1-e^{-\alpha})f_{avg}(\pi^{*})$.

###### Theorem 4.4

If $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular and
adaptive monotone, then the Partial-Adaptive Greedy Policy $\pi^{p}$ achieves
a $1-e^{-\alpha}$ approximation ratio in expectation.

##  5 Knapsack Constraint

In this section, we study our problem subject to a knapsack constraint $B$. In
(Tang 2021b, Amanatidis et al. 2020), they develop a fully adaptive policy
that achieves a bounded approximation ratio against the optimal fully adaptive
policy. We extend their design by developing a partial-adaptive policy which
allows to select multiple items in a single batch. Our policy with degree of
adaptivity $\alpha$ achieves an approximation ratio of $\frac{1}{6+4/\alpha}$
with respect to the optimal fully adaptive policy. Again, one can balance the
peformance/adaptivity tradeoff by adjusting the degree of adaptivity $\alpha$.
In addition, we provide a rigorous analysis of the batch query complexity of
our policy under some additional assumptions.

Algorithm 2 Partial-Adaptive Density-Greedy Policy $\pi^{k}$

1: $t=1;b[0]=1;\psi_{0}=\emptyset;S_{0}=\emptyset;\forall
i\in[n],S_{[i]}=\emptyset$.

2: for $i\in E$ do

3: let $r\sim\mathrm{Bernoulli}(\frac{1}{2})$

4: if $r=1$ then

5: add $i$ to $R$

6: while $R\setminus S_{t-1}\neq\emptyset$ do

7: let $e^{\prime}\leftarrow\arg\max_{e\in R\setminus
S_{t-1}}\frac{\Delta(e\mid S_{t-1},\psi_{b[t-1]-1})}{c(e)}$

8: if $t=1$ then

9: $e^{\prime\prime}\leftarrow e^{\prime}$

10: if $\frac{\Delta(e^{\prime}\mid
S_{t-1},\psi_{b[t-1]-1})}{c(e^{\prime})}\geq\alpha\cdot\frac{\Delta(e^{\prime\prime}\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}{c(e^{\prime\prime})}$
then

11: {stay in the current batch}

12: if $c(e^{\prime})+c(S_{t-1})\leq B$ then

13: $b[t]=b[t-1];e_{t}\leftarrow e^{\prime}$;
$S_{t}=S_{t-1}\cup\\{e_{t}\\};S_{[b[t]]}=S_{[b[t]]}\cup\\{e_{t}\\};t=t+1$

14: else

15: break

16: else

17: {start a new batch}

18: $b[t]=b[t-1]+1$

19: observe $\\{(e,\Phi(e))\mid e\in S_{[b[t-1]]}\\}$;
$\psi_{b[t]-1}=\psi_{b[t-1]-1}\cup\\{(e,\Phi(e))\mid e\in S_{[b[t-1]]}\\}$;

20: let $e^{\prime\prime}\leftarrow\arg\max_{e\in
R\setminus\mathrm{dom}(\psi_{b[t]-1})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}{c(e)}$

21: if
$\frac{\Delta(e^{\prime\prime}\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}{c(e^{\prime\prime})}>0$
then

22: if $c(e^{\prime\prime})+c(S_{t-1})\leq B$ then

23: $e_{t}\leftarrow e^{\prime\prime}$; $S_{t}=S_{t-1}\cup\\{e_{t}\\}$;
$S_{[b[t]]}=S_{[b[t]]}\cup\\{e_{t}\\}$; $F=F\setminus\\{e_{t}\\};t=t+1$

24: else

25: break

26: else

27: break

###  5.1 Algorithm Design

We first construct two candidate policies: the first policy always picks the
best singleton $o$ that maximizes the expected utility, i.e.,
$o\in\arg\max_{e\in E}\mathbb{E}_{\Phi\sim p}[f(\\{e\\},\Phi)]$ and the second
candidate is a sampling based “density-greedy” policy $\pi^{k}$. Our final
policy picks one from the above two candidates to execute such that $\\{o\\}$
is picked with probability $\frac{1/\alpha}{3+2/\alpha}$ and $\pi^{k}$ is
picked with probability $\frac{3+1/\alpha}{3+2/\alpha}$. In the rest of this
paper, let $f(o)$ denote $\mathbb{E}_{\Phi\sim p}[f(\\{o\\},\Phi)]$ for short.

We next explain the idea of _Partial-Adaptive Density-Greedy Policy_ $\pi^{k}$
(the second candidate policy). $\pi^{k}$ first selects a random subset $R$
which is obtained by including each item $e\in E$ independently with
probability $1/2$. Then we run a “density-greedy” algorithm only on $R$. We
first introduce some notations. For each iteration $t\in[n]$, let $b[t]$
denote the batch index of $t$, i.e., the $t$-th item selected in batch $b[t]$,
for convenience, we define $b[0]=1$. Let $S_{t-1}$ denote the first $t-1$
items selected by $\pi^{k}$, and $\psi_{b[t-1]-1}$ represent the partial
realization of the first $b[t-1]-1$ batches of selected items. Set the initial
solution $S_{0}=\emptyset$ and the initial partial realization
$\psi_{0}=\emptyset$.

  * •

Starting from iteration $t=1$ and batch $b[t]=1$.

  * •

In each iteration $t$, let $e^{\prime}$ be the item that has the largest
benefit-cost ratio on top of $S_{t-1}$ conditional on $\psi_{b[t-1]-1}$ from
$R\setminus S_{t-1}$, i.e.,

$\displaystyle e^{\prime}\leftarrow\arg\max_{e\in R\setminus
S_{t-1}}\frac{\Delta(e\mid S_{t-1},\psi_{b[t-1]-1})}{c(e)}$ (14)

Let $e^{\prime\prime}$ be the item that has the largest benefit-cost ratio on
top of $\mathrm{dom}(\psi_{b[t-1]-1})$ conditional on $\psi_{b[t-1]-1}$ from
$R\setminus\mathrm{dom}(\psi_{b[t-1]-1})$, i.e.,

$\displaystyle e^{\prime\prime}\leftarrow\arg\max_{e\in
R\setminus\mathrm{dom}(\psi_{b[t-1]-1})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}{c(e)}$
(15)

It will become clear later that $e^{\prime\prime}$ stores the first selected
item, if any, from the $b[t-1]$-th batch. Note that
$\mathrm{dom}(\psi_{b[t-1]-1})\subseteq S_{t-1}$.

Compare $\frac{\Delta(e^{\prime}\mid S_{t-1},\psi_{b[t-1]-1})}{c(e^{\prime})}$
with
$\alpha\cdot\frac{\Delta(e^{\prime\prime}\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}{c(e^{\prime\prime})}$,

    * –

if $\frac{\Delta(e^{\prime}\mid
S_{t-1},\psi_{b[t-1]-1})}{c(e^{\prime})}\geq\alpha\cdot\frac{\Delta(e^{\prime\prime}\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}{c(e^{\prime\prime})}$
and adding $e^{\prime}$ to the solution does not violate the budget
constraint, then stay in the current batch, i.e., $b[t]=b[t-1]$, add
$e^{\prime}$ to the solution, i.e, $S_{t}=S_{t-1}\cup\\{e^{\prime}\\}$. Move
to the next iteration, i.e., $t=t+1$;

    * –

if $\frac{\Delta(e^{\prime}\mid
S_{t-1},\psi_{b[t-1]-1})}{c(e^{\prime})}\geq\alpha\cdot\frac{\Delta(e^{\prime\prime}\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}{c(e^{\prime\prime})}$
and adding $e^{\prime}$ to the solution violates the budget constraint, then
terminate;

    * –

if $\frac{\Delta(e^{\prime}\mid
S_{t-1},\psi_{b[t-1]-1})}{c(e^{\prime})}<\alpha\cdot\frac{\Delta(e^{\prime\prime}\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}{c(e^{\prime\prime})}$,
then start a new batch, i.e., $b[t]=b[t-1]+1$, observe the partial realization
of all items selected so far, i.e.,
$\psi_{b[t]-1}=\psi_{b[t-1]-1}\cup\\{(e,\Phi(e))\mid e\in S_{[b[t-1]]}\\}$. If
$\max_{e\in
R\setminus\mathrm{dom}(\psi_{b[t]-1})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}{c(e)}>0$
and adding $\arg\max_{e\in
R\setminus\mathrm{dom}(\psi_{b[t]-1})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}{c(e)}$
to the solution does not violate the budget constraint, then add
$\arg\max_{e\in
R\setminus\mathrm{dom}(\psi_{b[t]-1})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}{c(e)}$
to the solution, and move to the next iteration, i.e., $t=t+1$; otherwise,
terminate.

A detailed description of $\pi^{k}$ is presented in Algorithm 2.

Algorithm 3 Equivalent $\pi^{k}$

1: $t=1;b[0]=1;\psi_{0}=\emptyset;F=E;S_{0}=\emptyset;\forall
i\in[n],S_{[i]}=\emptyset$.

2: while $F\neq\emptyset$ do

3: let $e^{\prime}\leftarrow\arg\max_{e\in F}\frac{\Delta(e\mid
S_{t-1},\psi_{b[t-1]-1})}{c(e)}$

4: if $t=1$ then

5: $e^{\prime\prime}\leftarrow e^{\prime}$

6: if $\frac{\Delta(e^{\prime}\mid
S_{t-1},\psi_{b[t-1]-1})}{c(e^{\prime})}\geq\alpha\cdot\frac{\Delta(e^{\prime\prime}\mid\mathrm{dom}(\psi_{b[t-1]-1}),\psi_{b[t-1]-1})}{c(e^{\prime\prime})}$
then

7: {stay in the current batch}

8: if $c(e^{\prime})+c(S_{t-1})\leq B$ then

9: consider $e^{\prime}$

10: let $r\sim\mathrm{Bernoulli}(\frac{1}{2})$

11: if $r=1$ then

12: $b[t]=b[t-1];e_{t}\leftarrow e^{\prime}$; $S_{t}=S_{t-1}\cup\\{e_{t}\\}$;
$S_{[b[t]]}=S_{[b[t]]}\cup\\{e_{t}\\}$; $F=F\setminus\\{e_{t}\\};t=t+1$

13: else

14: $F=F\setminus\\{e^{\prime}\\}$

15: else

16: break

17: else

18: {start a new batch}

19: $b[t]=b[t-1]+1$

20: observe $\\{(e,\Phi(e))\mid e\in S_{[b[t-1]]}\\}$; update
$\psi_{b[t]-1}=\psi_{b[t-1]-1}\cup\\{(e,\Phi(e))\mid e\in S_{[b[t-1]]}\\}$;

21: let $z\leftarrow\arg\max_{e\in
F}\frac{\Delta(e\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}{c(e)}$

22: if
$\frac{\Delta(z\mid\mathrm{dom}(\psi_{b[t]-1}),\psi_{b[t]-1})}{c(e^{\prime\prime})}>0$
then

23: if $c(z)+c(S_{t-1})\leq B$ then

24: consider $z$

25: let $r\sim\mathrm{Bernoulli}(\frac{1}{2})$

26: if $r=1$ then

27: $e_{t}\leftarrow z$; $S_{t}=S_{t-1}\cup\\{e_{t}\\}$;
$S_{[b[t]]}=S_{[b[t]]}\cup\\{e_{t}\\}$; $F=F\setminus\\{e_{t}\\}$;
$e^{\prime\prime}\leftarrow z$; {$z$ is selected as the first item in batch
$b[t]$}

28: $t=t+1$

29: else

30: $F=F\setminus\\{z\\}$

31: else

32: break

33: else

34: break

###  5.2 Performance Analysis

For ease of analysis, we present an auxiliary policy in Algorithm 3. Unlike
Algorithm 2 where $R$ is sampled at the beginning of the algorithm, we defer
this decision in Algorithm 3, that is, we toss a coin of success $1/2$ to
decide whether or not to add an item to the solution each time after an item
is being considered. It is easy to verify that both versions of the algorithm
have identical output distributions.

We first provide some useful observations that will be used in the proof of
the main theorem. Consider an arbitrary partial realization $\psi$, let
$W(\psi)=\\{e\in E\mid\Delta(e\mid\mathrm{dom}(\psi),\psi)>0\\}$ denote the
set of all items whose marginal utility with respect to $\mathrm{dom}(\psi)$
conditional on $\psi$ is positive. We number all items $e\in W(\psi)$ by
decreasing ratio $\frac{\Delta(e\mid\mathrm{dom}(\psi),\psi)}{c(e)}$, i.e.,
$e(1)\in\arg\max_{e\in
W(\psi)}\frac{\Delta(e\mid\mathrm{dom}(\psi),\psi)}{c(e)}$. If $\sum_{e\in
W(\psi)}c(e)\geq B$, let $l=\min\\{i\in\mathbb{N}\mid\sum_{j=1}^{i}c(e(i))\geq
B\\}$; otherwise, if $\sum_{e\in W(\psi)}c(e)<B$, let $l=|W(\psi)|$. Define
$D(\psi)=\\{e(i)\in W(\psi)\mid i\in[l]\\}$ as the set containing the first
$l$ items from $W(\psi)$. Intuitively, $D(\psi)$ represents a set of _best-
looking_ items conditional on $\psi$.

Consider any $e\in D(\psi)$, assuming $e$ is the $i$-th item in $D(\psi)$, let

$x(e,\psi)=\min\\{1,\frac{B-\sum_{s\in\cup_{j\in[i-1]}\\{e(j)\\}}c(s)}{c(e)}\\}~{}$

where $\cup_{j\in[i-1]}\\{e(j)\\}$ represents the first $i-1$ items in
$D(\psi)$.

Define

$\displaystyle d(\psi)=\sum_{e\in
D(\psi)}x(e,\psi)\Delta(e\mid\mathrm{dom}(\psi),\psi)~{}$

In analogy to Lemma 1 of (Gotovos et al. 2015),

$\displaystyle d(\psi)\geq\Delta(\pi^{*}\mid\mathrm{dom}(\psi),\psi)$ (16)

We use $\lambda=(\\{S^{\lambda}_{t},\psi^{\lambda}_{b[t]-1}\mid
t\in[z^{\lambda}]\\},\psi^{\lambda}_{b[z^{\lambda}]})$ to represent a fixed
run of $\pi^{k}$ where $S^{\lambda}_{t}$ denotes the first $t$ items selected
by $\pi^{k}$ under $\lambda$, $\psi^{\lambda}_{b[t]-1}$ denotes the partial
realization of first $b[t]-1$ batches of selected items under $\lambda$, and
$\psi^{\lambda}_{b[z^{\lambda}]}$ denotes the partial realization of all
selected items under $\lambda$, i.e., $\pi^{k}$ selects $z^{\lambda}$ items
under $\lambda$. Hence,
$\mathrm{dom}(\psi^{\lambda}_{b[z^{\lambda}]})=S^{\lambda}_{z^{\lambda}}$.
Define $C(\lambda)$ as those items in $D(\psi^{\lambda}_{b[z^{\lambda}]})$
that have been considered by $\pi^{k}$ but not added to the solution because
of the coin flips. Let $U(\lambda)$ denote those items in
$D(\psi^{\lambda}_{b[z^{\lambda}]})$ that have not been considered by
$\pi^{k}$. (16) implies that

$\displaystyle d(\psi^{\lambda}_{b[z^{\lambda}]})$ $\displaystyle=$
$\displaystyle\sum_{e\in
D(\psi^{\lambda}_{b[z^{\lambda}]})}x(e,\psi^{\lambda}_{b[z^{\lambda}]})\Delta(e\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})$ $\displaystyle=$
$\displaystyle\sum_{e\in U(\lambda)\cup
C(\lambda)}x(e,\psi^{\lambda}_{b[z^{\lambda}]})\Delta(e\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})~{}$
$\displaystyle\geq$ $\displaystyle\Delta(\pi^{*}\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})$ (18)

Before presenting the main theorem, we provide two technical lemmas.

###### Lemma 5.1

Let the random variable $\Lambda$ denote a random run of $\pi^{k}$,

$\displaystyle f_{avg}(\pi^{k})\geq\frac{1}{2}\mathbb{E}[\sum_{e\in
C(\Lambda)}\Delta(e\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})]$ (19)

_Proof:_ For each $e\in E$, let $H(e)=\\{\lambda\mid e\in C(\lambda)\\}$
denote the set of all possible runs of $\pi^{k}$ under which $e$ is being
considered and it is among _best-looking_ items. Let $\mathcal{D}(H(e))$
denote the prior probability distribution over $H(e)$. In addition, let
$H^{+}(e)$ denote the set of all possible runs of $\pi^{k}$ under which $e$ is
being considered and let $\mathcal{D}(H^{+}(e))$ represent the prior
probability distribution over $H^{+}(e)$. Thus, $H(e)\subseteq H^{+}(e)$.
Consider any fixed run $\lambda\in H^{+}(e)$, assume $S^{\lambda}_{e}$
contains all items that are selected before $e$ is being considered and let
$\psi^{\lambda}_{e}$ denote the partial realization of $S^{\lambda}_{e}$,
i.e., $\mathrm{dom}(\psi^{\lambda}_{e})=S^{\lambda}_{e}$. Note that
$\psi^{\lambda}_{e}$ is a subrealization of $\psi^{\lambda}_{b[z^{\lambda}]}$,
i.e., $\psi^{\lambda}_{e}\subseteq\psi^{\lambda}_{b[z^{\lambda}]}$. Then we
have

$\displaystyle f_{avg}(\pi^{k})$ $\displaystyle=$ $\displaystyle\sum_{e\in
E}\mathbb{E}_{\Lambda\sim\mathcal{D}(H^{+}(e))}[\Pr[e\mbox{ is selected given
it was considered}]\Delta(e\mid S^{\Lambda}_{e},\psi^{\Lambda}_{e})]$ (20)
$\displaystyle\geq$ $\displaystyle\sum_{e\in
E}\mathbb{E}_{\Lambda\sim\mathcal{D}(H(e))}[\Pr[e\mbox{ is selected given it
was considered}]\Delta(e\mid S^{\Lambda}_{e},\psi^{\Lambda}_{e})]$ (21)
$\displaystyle=$ $\displaystyle\sum_{e\in
E}\mathbb{E}_{\Lambda\sim\mathcal{D}(H(e))}[\frac{1}{2}\times\Delta(e\mid
S^{\Lambda}_{e},\psi^{\Lambda}_{e})]$ (22) $\displaystyle=$
$\displaystyle\frac{1}{2}\sum_{e\in
E}\mathbb{E}_{\Lambda\sim\mathcal{D}(H(e))}[\Delta(e\mid
S^{\Lambda}_{e},\psi^{\Lambda}_{e})]$ (23) $\displaystyle\geq$
$\displaystyle\frac{1}{2}\sum_{e\in
E}\mathbb{E}_{\Lambda\sim\mathcal{D}(H(e))}[\Delta(e\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})]$ (24)
$\displaystyle=$ $\displaystyle\frac{1}{2}\mathbb{E}[\sum_{e\in
C(\Lambda)}\Delta(e\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})]$ (25)

The first inequality is due to $H(e)\subseteq H^{+}(e)$. The second equality
is due to the probability of $e$ being selected conditional on $e$ has been
considered is $1/2$. The second inequality is due to
$\psi^{\lambda}_{e}\subseteq\psi^{\lambda}_{b[z^{\lambda}]}$ for all $e\in E$
and $\lambda\in H(e)$ and $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$ is
adaptive submodular. $\Box$

###### Lemma 5.2

Let the random variable $\Lambda$ denote a random run of $\pi^{k}$,

$\displaystyle
f_{avg}(\pi^{k})+f(o)\geq\alpha\cdot\mathbb{E}_{\Lambda}[\sum_{e\in
U(\Lambda)}x(e,\psi^{\Lambda}_{b[z^{\Lambda}]})\Delta(e\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})]$ (26)

_Proof:_ We first show that for any fixed run $\lambda$ of $\pi^{k}$, the
following inequality holds:

$\displaystyle\sum_{t\in[z^{\lambda}]}\Delta(e\mid
S^{\lambda}_{t-1},\psi^{\lambda}_{b[t]-1})+f(o)\geq\alpha\cdot\sum_{e\in
U(\lambda)}x(e,\psi^{\lambda}_{b[z^{\lambda}]})\Delta(e\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})$ (27)

We prove the above inequality in two cases, depending on whether Line 16 or
Line 32 has been triggered or not under $\lambda$. For the case when neither
Line 16 nor Line 32 has been triggered, there are two possible reasons: either
all items from $E$ have been considered or the _best-looking_ item with
respect to $S^{\lambda}_{z^{\lambda}}$ conditional on
$\psi^{\lambda}_{b[z^{\lambda}]}$ has negative marginal utility, i.e., Line 34
is triggered. In the former case, (27) follows from the fact that
$U(\lambda)=\emptyset$. In the latter case, due to the definition of
$U(\lambda)$, it must hold that for all $e\in U(\lambda)$, $\Delta(e\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})<0$, i.e., the
marginal utility of every item in $U(\lambda)$ is negative. This implies that
the RHS of (27) is non-positive, moreover, because
$\sum_{t\in[z^{\lambda}]}\Delta(e\mid
S^{\lambda}_{t-1},\psi^{\lambda}_{b[t]-1})>0$ which implies that the LHS of
(27) is non-negative, we have (27).

We next focus on proving (27) for the case when either Line 16 or Line 32 has
been triggered. Let $e^{\lambda}_{z^{\lambda}+1}$ denote the item who triggers
Line 16 or Line 32, i.e., adding $e^{\lambda}_{z^{\lambda}+1}$ to
$S^{\lambda}_{z^{\lambda}}$ violates the budget constraint. Let
$b[\lambda_{z^{\lambda}+1}]=b[z^{\lambda}]$ if Line 16 has been triggered and
let $b[\lambda_{z^{\lambda}+1}]=b[z^{\lambda}]+1$ if Line 32 has been
triggered. We first show that for any $t\in[z^{\lambda}+1]$,

$\displaystyle\frac{\Delta(e^{\lambda}_{t}\mid
S^{\lambda}_{t-1},\psi^{\lambda}_{b[t]-1})}{c(e^{\lambda}_{t})}$
$\displaystyle\geq$ $\displaystyle\alpha\cdot\max_{e\in
U(\lambda)}\frac{\Delta(e\mid\mathrm{dom}(\psi^{\lambda}_{b[t]-1}),\psi^{\lambda}_{b[t]-1})}{c(e)}$
(28) $\displaystyle\geq$ $\displaystyle\alpha\cdot\max_{e\in
U(\lambda)}\frac{\Delta(e\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})}{c(e)}$ (29)

The first inequality is due to the selection rule of $\pi^{k}$ and the
definition of $U(\lambda)$. The second inequality is due to $f:2^{E\times
O}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular and
$\psi^{\lambda}_{b[t]-1}\subseteq\psi^{\lambda}_{b[z^{\lambda}]}$ for any
$t\in[z^{\lambda}+1]$.

Now we are ready to prove (27). Let $y\in\arg\max_{e\in
U(\lambda)}\frac{\Delta(e\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})}{c(e)}$, (29)
implies that

$\sum_{t\in[z^{\lambda}+1]}\Delta(e^{\lambda}_{t}\mid
S^{\lambda}_{t-1},\psi^{\lambda}_{b[t]-1})\geq\alpha\cdot\sum_{t\in[z^{\lambda}+1]}\frac{c(e^{\lambda}_{t})\Delta(y\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})}{c(y)}$

It follows that

$\displaystyle\sum_{t\in[z^{\lambda}+1]}\Delta(e^{\lambda}_{t}\mid
S^{\lambda}_{t-1},\psi^{\lambda}_{b[t]-1})$ $\displaystyle\geq$
$\displaystyle\alpha\cdot\sum_{t\in[z^{\lambda}+1]}\frac{c(e^{\lambda}_{t})\Delta(y\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})}{c(y)}$ (30)
$\displaystyle=$
$\displaystyle\alpha\cdot(\sum_{t\in[z^{\lambda}+1]}c(e^{\lambda}_{t}))\frac{\Delta(y\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})}{c(y)}$ (31)
$\displaystyle\geq$
$\displaystyle\alpha\cdot(\sum_{t\in[z^{\lambda}+1]}c(e^{\lambda}_{t}))\frac{\sum_{e\in
U(\lambda)}x(e,\psi^{\lambda}_{b[z^{\lambda}]})\Delta(e\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})}{\sum_{e\in
U(\lambda)}x(e,\psi^{\lambda}_{b[z^{\lambda}]})c(e)}$ (32) $\displaystyle\geq$
$\displaystyle\alpha\cdot\sum_{e\in
U(\lambda)}x(e,\psi^{\lambda}_{b[z^{\lambda}]})\Delta(e\mid
S^{\lambda}_{z^{\lambda}},\psi^{\lambda}_{b[z^{\lambda}]})$ (33)

The last inequality is due to
$\sum_{t\in[z^{\lambda}+1]}c(e^{\lambda}_{t})=\sum_{e\in
S^{\lambda}_{z^{\lambda}}}c(e)\geq B$ and $\sum_{e\in
U(\lambda)}x(e,\psi^{\lambda}_{b[z^{\lambda}]})c(e)\leq B$. Recall that $o$ is
the best singleton, we have $\sum_{t\in[z^{\lambda}]}\Delta(e\mid
S^{\lambda}_{t-1},\psi^{\lambda}_{b[t]-1})+f(o)\geq\sum_{t\in[z^{\lambda}+1]}\Delta(e^{\lambda}_{t}\mid
S^{\lambda}_{t-1},\psi^{\lambda}_{b[t]-1})$ due to $f:2^{E\times
O}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive submodular. This together with
(33) implies (27).

Given (27) in hand, now we are ready to prove the lemma.

$\displaystyle f_{avg}(\pi^{k})+f(o)$ $\displaystyle=$
$\displaystyle\mathbb{E}_{\Lambda}[\sum_{t\in[z^{\Lambda}]}\Delta(e\mid
S^{\Lambda}_{t-1},\psi^{\Lambda}_{b[t]-1})+f(o)]$ (34) $\displaystyle\geq$
$\displaystyle\mathbb{E}_{\Lambda}[\alpha\cdot\sum_{e\in
U(\Lambda)}x(e,\psi^{\Lambda}_{b[z^{\Lambda}]})\Delta(e\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})]$ (35)
$\displaystyle=$ $\displaystyle\alpha\cdot\mathbb{E}_{\Lambda}[\sum_{e\in
U(\Lambda)}x(e,\psi^{\Lambda}_{b[z^{\Lambda}]})\Delta(e\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})]$ (36)

The inequality is due to (27). $\Box$

Now we are ready to present the main theorem.

###### Theorem 5.3

If we randomly pick a policy from $\\{o\\}$ and $\pi^{k}$ with degree of
adaptivity $\alpha$ to execute such that $\\{o\\}$ is picked with probability
$\frac{1/\alpha}{3+2/\alpha}$ and $\pi^{k}$ with degree of adaptivity $\alpha$
is picked with probability $\frac{3+1/\alpha}{3+2/\alpha}$, then we can
achieve the expected utility of at least
$\frac{1}{6+4/\alpha}f_{avg}(\pi^{*})$.

_Proof:_ Lemma 5.1 and Lemma 5.2 imply that

$\displaystyle 2\times
f_{avg}(\pi^{k})+\frac{1}{\alpha}\times(f_{avg}(\pi^{k})+f(o))$ (37)
$\displaystyle\geq$ $\displaystyle\mathbb{E}_{\Lambda}[\sum_{e\in
C(\Lambda)}\Delta(e\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})]+\mathbb{E}_{\Lambda}[\sum_{e\in
U(\Lambda)}x(e,\psi^{\Lambda}_{b[z^{\Lambda}]})\Delta(e\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})]$ (38)
$\displaystyle=$ $\displaystyle\mathbb{E}_{\Lambda}[\sum_{e\in
C(\Lambda)}\Delta(e\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})+\sum_{e\in
U(\Lambda)}x(e,\psi^{\Lambda}_{b[z^{\Lambda}]})\Delta(e\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})]$ (39)
$\displaystyle\geq$ $\displaystyle\mathbb{E}_{\Lambda}[\sum_{e\in
U(\Lambda)\cup C(\Lambda)}x(e,\psi^{\Lambda}_{b[z^{\Lambda}]})\Delta(e\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})]$ (40)
$\displaystyle\geq$ $\displaystyle\mathbb{E}_{\Lambda}[\Delta(\pi^{*}\mid
S^{\Lambda}_{z^{\Lambda}},\psi^{\Lambda}_{b[z^{\Lambda}]})]$ (41)
$\displaystyle=$ $\displaystyle f_{avg}(\pi^{*}@\pi^{k})-f_{avg}(\pi^{k})$
(42)

The second inequality is due to $x(e,\psi^{\lambda}_{b[z^{\lambda}]})\leq 1$
for all $\lambda$. The third inequality is due to (18).

Recall that we toss a coin of success $1/2$ to decide whether or not to add an
item to the solution each time after an item is being considered, this design,
together with Lemma 1 in (Tang 2021b), implies that
$f_{avg}(\pi^{*}@\pi^{k})\geq f_{avg}(\pi^{*})/2$. Combining this with (42),

$\displaystyle 2\times
f_{avg}(\pi^{k})+\frac{1}{\alpha}\times(f_{avg}(\pi^{k})+f(o))\geq\frac{f_{avg}(\pi^{*})}{2}-f_{avg}(\pi^{k})$
(43)

It follows that

$\displaystyle(3+\frac{1}{\alpha})f_{avg}(\pi^{k})+\frac{1}{\alpha}f(o)\geq\frac{f_{avg}(\pi^{*})}{2}$
(44)

Recall that our final policy randomly picks a policy from $\\{o\\}$ and
$\pi^{k}$ to execute such that $\\{o\\}$ is picked with probability
$\frac{1/\alpha}{3+2/\alpha}$ and $\pi^{k}$ is picked with probability
$\frac{3+1/\alpha}{3+2/\alpha}$, then the expected utility of our final policy
is

$\displaystyle
f_{avg}(\pi^{k})\times\frac{3+1/\alpha}{3+2/\alpha}+f(o)\times\frac{1/\alpha}{3+2/\alpha}$
(45)

(44) and (45) imply that the expected utility of our final policy is at least

$\displaystyle\frac{(3+1/\alpha)f_{avg}(\pi^{k})+(1/\alpha)f(o)}{3+2/\alpha}\geq\frac{1}{6+4/\alpha}f_{avg}(\pi^{*})$
(46)

$\Box$

###  5.3 Bounding the Batch Query Complexity

We next analyze the the batch query complexity, i.e., the number of batches a
policy takes to complete the selection process, of our partial-adaptive
policy. We show that if we choose an appropriate $\alpha$, then it takes at
most $\min\\{O(n),O(\log n\log\frac{B}{c_{\min}})\\}$, where
$c_{\min}=\min_{e\in E}c(e)$ is the cost of the cheapest item, batches to
achieve a constant approximation ratio. Notably, if we consider a cardinality
constraint $k$, then the above complexity is upper bounded by $O(\log n\log
k)$ which is polylogarithmic. This is in sharp contrast to the case of fully
adaptive policy whose batch query complexity is $O(n)$. To establish this
result, we first introduce two classes of stochastic functions.

###### Definition 5.4

(Tang and Yuan 2021)[Policywise Submodularity] A function $f:2^{E\times
O}\rightarrow\mathbb{R}_{\geq 0}$ is policywise submodular with respect to a
prior $p(\phi)$ and a knapsack constraint $(c,B)$ if for any two partial
realizations $\psi$ and $\psi^{\prime}$ such that $\psi^{\prime}\subseteq\psi$
and $c(\mathrm{dom}(\psi))\leq B$, and any $S\subseteq E$ such that
$S\cap\mathrm{dom}(\psi)=\emptyset$, we have

$\displaystyle\max_{\pi\in\Omega}\Delta(\pi|\mathrm{dom}(\psi^{\prime}),\psi^{\prime})\geq\max_{\pi\in\Omega}\Delta(\pi|\mathrm{dom}(\psi),\psi)$
(47)

where $\Omega=\\{\pi\mid\forall\phi:c(E(\pi,\phi))\leq
B-c(\mathrm{dom}(\psi)),E(\pi,\phi)\subseteq S\\}$ denotes the set of feasible
policies which are restricted to selecting items only from $S$.

######  Definition 5.5 (Weak Policywise Submodularity)

A function $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$ is weak policywise
submodular with respect to a prior $p(\phi)$ and a knapsack constraint $(c,B)$
if for any partial realization $\psi$ such that $c(\mathrm{dom}(\psi))\leq B$,

$\displaystyle
f_{avg}(\pi^{*})\geq\max_{\pi\in\Omega}\Delta(\pi|\mathrm{dom}(\psi),\psi)$
(48)

where $\pi^{*}$ represents an optimal policy and
$\Omega=\\{\pi\mid\forall\phi:c(E(\pi,\phi))\leq B-c(\mathrm{dom}(\psi))\\}$
denotes the set of feasible policies subject to a budget constraint
$B-c(\mathrm{dom}(\psi))$.

Observe that policywise submodularity implies weak policywise submodularity.
In Tang and Yuan (2021), it has been shown that policywise submodularity (and
hence weak policywise submodularity) can be found in a wide range of real-
world applications, including generalized binary search (Golovin and Krause
2011), any applications where items are independent (Asadpour and Nazerzadeh
2016), and adaptive viral marketing (Golovin and Krause 2011). We next show
that if a utility function is both adaptive submodular and weak policywise
submodular, then our partial-adaptive policy achieves a constant approximation
ratio using only $O(\log n\log k)$ number of batches.

To analyze the batch query complexity of $\pi^{k}$, we focus on the original
description of $\pi^{k}$ (Algorithm 2). That is, instead of tossing a coin
each time after an item is being considered to be added to the solution, we
first select a random subset $R$ which is obtained by including each item
$e\in E$ independently with probability $1/2$. Then we run the “density-
greedy” algorithm only on $R$. We first present a technical lemma that extends
Lemma 7 in (Esfandiari et al. 2021) to a general knapsack constraint.

###### Lemma 5.6

Consider an arbitrary batch index $l$ and a partial realization $\psi_{l}$
observed after the first $l$ batches conditional on $R\subseteq E$ is being
sampled at the beginning of $\pi^{k}$. Let
$l^{+}=l+\log_{\frac{1}{1-(1-\alpha)/2}}(\frac{n}{\delta})$. Assuming we run
$\pi^{k}$ without budget constraint and $f:2^{E\times
O}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive monotone and adaptive
submodular, then

$\displaystyle\max_{e\in
R\setminus\mathrm{dom}(\psi_{l^{+}})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{l^{+}}),\psi_{l^{+}})}{c(e)}\leq(1-\frac{1-\alpha}{2})\max_{e\in
R\setminus\mathrm{dom}(\psi_{l})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{l}),\psi_{l})}{c(e)}$
(49)

with probability at least $1-\delta$. Note that it could be the case that
there may not be $l^{+}$ batches after selecting all items. If that is the
case, just add some empty batches to make it $l^{+}$ batches.

_Proof:_ We closely follow the proof of Lemma 7 in (Esfandiari et al. 2021).
For any $l^{\prime}\geq l$, let the random variable $R_{l^{\prime}}$ denote
the set of items from $R\setminus\mathrm{dom}(\psi_{l^{\prime}})$ such that
$\frac{\Delta(e\mid\mathrm{dom}(\psi_{l^{\prime}}),\psi_{l^{\prime}})}{c(e)}\geq(1-\frac{1-\alpha}{2})\max_{e\in
R\setminus\mathrm{dom}(\psi_{l})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{l}),\psi_{l})}{c(e)}$.
To prove this lemma, it suffices to show that

$\displaystyle\mathbb{E}[|R_{l^{\prime}+1}|]\leq(1-\frac{1-\alpha}{2})\mathbb{E}[|R_{l^{\prime}}|]$
(50)

This is because (50), together with the facts that $|R_{l}|\leq n$ and
$l^{+}=l+\log_{\frac{1}{1-(1-\alpha)/2}}(\frac{n}{\delta})$, implies that
$\mathbb{E}[|R_{l^{+}}|]\leq\delta$. Note that $|R_{l^{+}}|$ is non-negative,
thus we have $|R_{l^{+}}|=0$ with probability at least $1-\delta$, as desired.

We next focus on proving (50). First, because of adaptive submodularity, we
have $e\in R_{l^{\prime}+1}$ implies that $e\in R_{l^{\prime}}$. Thus,
$R_{l^{\prime}+1}\subseteq R_{l^{\prime}}$. We next show that for any item
$e\in R_{l^{\prime}}$, we have $e\notin R_{l^{\prime}+1}$ with probability at
least $\frac{1-\alpha}{2}$.

Because we run $\pi^{k}$ without budget constraint, if $e\in R_{l^{\prime}}$
and $e$ is not selected within the $(l^{\prime}+1)$-th batch of $\pi^{k}$,
then

$\displaystyle\mathbb{E}_{\Psi_{l^{\prime}+1}}[\frac{\Delta(e\mid\mathrm{dom}(\Psi_{l^{\prime}+1}),\psi_{l^{\prime}})}{c(e)}]\leq\alpha\max_{e\in
R\setminus\mathrm{dom}(\psi_{l^{\prime}})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{l^{\prime}}),\psi_{l^{\prime}})}{c(e)}$
(51)

Because $\max_{e\in
R\setminus\mathrm{dom}(\psi_{l^{\prime}})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{l^{\prime}}),\psi_{l^{\prime}})}{c(e)}\leq\max_{e\in
R\setminus\mathrm{dom}(\psi_{l})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{l}),\psi_{l})}{c(e)}$
due to adaptive submodularity, we have
$\mathbb{E}_{\Psi_{l^{\prime}+1}}[\frac{\Delta(e\mid\mathrm{dom}(\Psi_{l^{\prime}+1}),\psi_{l^{\prime}})}{c(e)}]\leq\alpha\max_{e\in
R\setminus\mathrm{dom}(\psi_{l})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{l}),\psi_{l})}{c(e)}$.
This, together with the assumption that $f:2^{E\times
O}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive monotone, implies that the
probability that
$\frac{\Delta(e\mid\mathrm{dom}(\Psi_{l^{\prime}+1}),\psi_{l^{\prime}})}{c(e)}<(1-\frac{1-\alpha}{2})\max_{e\in
R\setminus\mathrm{dom}(\psi_{l})}\frac{\Delta(e\mid\mathrm{dom}(\psi_{l}),\psi_{l})}{c(e)}$
is at least $\frac{1-\alpha}{2}$. It follows that $e\notin R_{l^{\prime}+1}$
with probability at least $\frac{1-\alpha}{2}$. This indicates that
$\mathbb{E}[|R_{l^{\prime}+1}|]\leq(1-\frac{1-\alpha}{2})\mathbb{E}[|R_{l^{\prime}}|]$,
as desired. $\Box$

The following lemma shows that if $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq
0}$ is adaptive monotone and adaptive policywise submodular with respect to a
prior $p(\phi)$ and any knapsack constraints, then it takes at most $O(\log
n\log\frac{B}{c_{\min}})$ batches of $\pi^{k}$ to achieve a near optimal
solution. Let $\pi^{k}(T)$ denote a policy that runs $\pi^{k}$ and stops if it
makes $T$ batch queries. In the rest of this section, let
$T=\log_{\frac{1}{1-(1-\alpha)/2}}(\frac{n}{\delta})\times\log_{\frac{1}{1-(1-\alpha)/2}}(\frac{B}{c_{\min}(1-\alpha)})$
where
$\delta=\frac{1-\alpha}{\log_{\frac{1}{1-(1-\alpha)/2}}(\frac{B}{c_{\min}(1-\alpha)})}$.

###### Lemma 5.7

If $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive monotone,
adaptive submodular, and weak policywise submodular with respect to a prior
$p(\phi)$ and any knapsack constraints, then
$f_{avg}(\pi^{k}(T))\geq(1-\alpha+\alpha^{2})f_{avg}(\pi^{k})-(1-\alpha)f_{avg}(\pi^{*})$.

_Proof:_ We first analyze the expected utility of $\pi^{k}(T)$ conditional on
$R\subseteq E$ is sampled at the beginning of $\pi^{k}$. Let $a$ be the first
selected item, i.e., $a\in\arg\max_{e\in
R}\frac{\Delta(e\mid\emptyset,\emptyset)}{c(e)}$. Assuming we run $\pi^{k}$
without budget constraint, by applying Lemma 5.6 iteratively
$\log_{\frac{1}{1-(1-\alpha)/2}}(\frac{B}{c_{\min}(1-\alpha)})$ times we have

$\displaystyle\max_{e\notin\mathrm{dom}(\Psi_{T})}\frac{\Delta(e\mid\mathrm{dom}(\Psi_{T}),\Psi_{T})}{c(e)}$
$\displaystyle\leq$
$\displaystyle(1-\frac{1-\alpha}{2})^{\log_{\frac{1}{1-(1-\alpha)/2}}(\frac{B}{c_{\min}(1-\alpha)})}\frac{\Delta(a\mid\emptyset,\emptyset)}{c(a)}$
(52) $\displaystyle=$
$\displaystyle\frac{c_{\min}(1-\alpha)}{B}\times\frac{\Delta(a\mid\emptyset,\emptyset)}{c(a)}\leq\frac{(1-\alpha)\Delta(a\mid\emptyset,\emptyset)}{B}$
(53)

with probability
$1-\delta\times\log_{\frac{1}{1-(1-\alpha)/2}}(\frac{B}{c_{\min}(1-\alpha)})=\alpha$.
Recall that
$T=\log_{\frac{1}{1-(1-\alpha)/2}}(\frac{n}{\delta})\times\log_{\frac{1}{1-(1-\alpha)/2}}(\frac{B}{c_{\min}(1-\alpha)})$,
this indicates that with probability $\alpha$ the total expected marginal
benefit of all item added after the $T$-th batch is at most

$\displaystyle\frac{(1-\alpha)\Delta(a\mid\emptyset,\emptyset)}{B}\times
B=(1-\alpha)\Delta(a\mid\emptyset,\emptyset)\leq(1-\alpha)\mathbb{E}[f_{avg}(\pi^{k})\mid
R]$ (54)

where $\mathbb{E}[f_{avg}(\pi^{k})\mid R]$ is the expected utility of
$\pi^{k}$ conditional on $R$ is being sampled.

Moreover, because $f:2^{E\times O}\rightarrow\mathbb{R}$ is weak policywise
submodular with respect to a prior $p(\phi)$ and any knapsack constraints, we
have

$\displaystyle\max_{\pi\in\Omega}\Delta(\pi|\mathrm{dom}(\psi_{T}),\psi_{T})\leq
f_{avg}(\pi^{*})$ (55)

where $\Omega=\\{\pi\mid\forall\phi:c(E(\pi,\phi))\leq
B-c(\mathrm{dom}(\psi_{T}))\\}$ denotes the set of all feasible policies
subject to a budget constraint $B-c(\mathrm{dom}(\psi_{T}))$. (55) indicates
that for any $\psi_{T}$, the total expected marginal benefit of all item added
after the $T$-th batch is at most $f_{avg}(\pi^{*})$. This, together with
(54), implies that the total expected marginal benefit of the items added
after the $T$-th batch is at most

$\displaystyle\alpha(1-\alpha)\mathbb{E}[f_{avg}(\pi^{k})\mid
R]+(1-\alpha)f_{avg}(\pi^{*})$ (56)

It follows that the expected utility of $\pi^{k}(T)$ conditional on $R$ is
being sampled is at least

$\displaystyle\mathbb{E}[f_{avg}(\pi^{k}(T))\mid R]\geq
f_{avg}(\pi^{k})-\alpha(1-\alpha)\mathbb{E}[f_{avg}(\pi^{k})\mid
R]-(1-\alpha)f_{avg}(\pi^{*})$ (57)

By taking the expectation of both sides of the above inequality over $R$, now
we are ready to bound the expected utility of $\pi^{k}(T)$ as follows:

$\displaystyle f_{avg}(\pi^{k}(T))$ $\displaystyle=$
$\displaystyle\sum_{R\subseteq E}\Pr[R\mbox{ is
sampled}]\mathbb{E}[f_{avg}(\pi^{k}(T))\mid R]$ (58) $\displaystyle\geq$
$\displaystyle\sum_{R\subseteq E}\Pr[R\mbox{ is
sampled}](f_{avg}(\pi^{k})-\alpha(1-\alpha)\mathbb{E}[f_{avg}(\pi^{k})\mid
R]-(1-\alpha)f_{avg}(\pi^{*}))$ (59) $\displaystyle=$ $\displaystyle
f_{avg}(\pi^{k})-(1-\alpha)f_{avg}(\pi^{*})-\sum_{R\subseteq E}\Pr[R\mbox{ is
sampled}]\alpha(1-\alpha)\mathbb{E}[f_{avg}(\pi^{k})\mid R]$ (60)
$\displaystyle=$ $\displaystyle
f_{avg}(\pi^{k})-(1-\alpha)f_{avg}(\pi^{*})-\alpha(1-\alpha)f_{avg}(\pi^{k})$
(61) $\displaystyle=$
$\displaystyle(1-\alpha+\alpha^{2})f_{avg}(\pi^{k})-(1-\alpha)f_{avg}(\pi^{*})$
(62)

The inequality is due to (57). $\Box$

_Remark:_ Note that adaptive submodularity does not necessarily imply (55). As
a result, one main result (Theorem 8) presented in (Esfandiari et al. 2021)
does not hold without resorting to weak policywise submodularity.

We next show that if we randomly pick a policy from $\pi^{k}(T)$ and $\\{o\\}$
to execute, then we can achieve a constant approximation ratio against the
optimal fully adaptive policy.

###### Lemma 5.8

Assuming $f:2^{E\times O}\rightarrow\mathbb{R}_{\geq 0}$ is adaptive monotone,
adaptive submodular, and adaptive policywise submodular with respect to a
prior $p(\phi)$ and any knapsack constraints. If we randomly pick a policy
from $\pi^{k}(T)$ and $\\{o\\}$ to execute such that $\pi^{k}(T)$ is picked
with probability $\frac{3+1/\alpha}{3+2/\alpha}$ and $\\{o\\}$ is picked with
probability $\frac{1/\alpha}{3+2/\alpha}$, then we can achieve the expected
utility of at least
$\frac{(1-\alpha+\alpha^{2})/2-(1-\alpha)(3+1/\alpha)}{3+2/\alpha}f_{avg}(\pi^{*})$.

_Proof:_ Observe that if $\pi^{k}(T)$ is picked with probability
$\frac{3+1/\alpha}{3+2/\alpha}$ and $\\{o\\}$ is picked with probability
$\frac{1/\alpha}{3+2/\alpha}$, then the expected utility can be represented as
$f_{avg}(\pi^{k}(T))\times\frac{3+1/\alpha}{3+2/\alpha}+f(o)\times\frac{1/\alpha}{3+2/\alpha}$.
Then we have

$\displaystyle
f_{avg}(\pi^{k}(T))\times\frac{3+1/\alpha}{3+2/\alpha}+f(o)\times\frac{1/\alpha}{3+2/\alpha}$
(63) $\displaystyle\geq$
$\displaystyle((1-\alpha+\alpha^{2})f_{avg}(\pi^{k})-(1-\alpha)f_{avg}(\pi^{*}))\times\frac{3+1/\alpha}{3+2/\alpha}+f(o)\times\frac{1/\alpha}{3+2/\alpha}$
(64) $\displaystyle\geq$
$\displaystyle\frac{(1-\alpha+\alpha^{2})(3+1/\alpha)f_{avg}(\pi^{k})+(1/\alpha)f(o)}{3+2/\alpha}-(1-\alpha)\frac{3+1/\alpha}{3+2/\alpha}f_{avg}(\pi^{*})$
(65) $\displaystyle\geq$
$\displaystyle\frac{(1-\alpha+\alpha^{2})((3+1/\alpha)f_{avg}(\pi^{k})+(1/\alpha)f(o))}{3+2/\alpha}-(1-\alpha)\frac{3+1/\alpha}{3+2/\alpha}f_{avg}(\pi^{*})$
(66) $\displaystyle\geq$
$\displaystyle\frac{(1-\alpha+\alpha^{2})f_{avg}(\pi^{*})/2}{3+2/\alpha}-(1-\alpha)\frac{3+1/\alpha}{3+2/\alpha}f_{avg}(\pi^{*})$
(67) $\displaystyle=$
$\displaystyle\frac{(1-\alpha+\alpha^{2})/2-(1-\alpha)(3+1/\alpha)}{3+2/\alpha}f_{avg}(\pi^{*})$
(68)

The first inequality is due to Lemma 5.7. The forth inequality is due to (44).
$\Box$

##  6 Conclusion

In this paper, we study the partial-adaptive submodular maximization problem.
Our setting allows to select multiple items in a batch simultaneously and
observe their realizations together. We develop effective solutions subject to
both cardinality constraint and knapsack constraint. We analyze the batch
query complexity of our policy under some additional assumptions about the
utility function.

## References

  * Amanatidis et al. (2020) Amanatidis, Georgios, Federico Fusco, Philip Lazos, Stefano Leonardi, Rebecca Reiffenhäuser. 2020.  Fast adaptive non-monotone submodular maximization subject to a knapsack constraint.  Advances in neural information processing systems.
  * Asadpour and Nazerzadeh (2016) Asadpour, Arash, Hamid Nazerzadeh. 2016.  Maximizing stochastic monotone submodular functions.  Management Science 62 2374–2391.
  * Badanidiyuru and Vondrák (2014) Badanidiyuru, Ashwinkumar, Jan Vondrák. 2014.  Fast algorithms for maximizing submodular functions.  Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 1497–1514.
  * Buchbinder et al. (2014) Buchbinder, Niv, Moran Feldman, Joseph Naor, Roy Schwartz. 2014.  Submodular maximization with cardinality constraints.  Proceedings of the twenty-fifth annual ACM-SIAM symposium on Discrete algorithms. SIAM, 1433–1452.
  * Chen and Krause (2013) Chen, Yuxin, Andreas Krause. 2013.  Near-optimal batch mode active learning and adaptive submodular optimization.  ICML (1) 28 8–1.
  * Esfandiari et al. (2021) Esfandiari, Hossein, Amin Karbasi, Vahab Mirrokni. 2021.  Adaptivity in adaptive submodularity.  COLT .
  * Golovin and Krause (2011) Golovin, Daniel, Andreas Krause. 2011.  Adaptive submodularity: Theory and applications in active learning and stochastic optimization.  Journal of Artificial Intelligence Research 42 427–486.
  * Gotovos et al. (2015) Gotovos, Alkis, Amin Karbasi, Andreas Krause. 2015.  Non-monotone adaptive submodular maximization.  Twenty-Fourth International Joint Conference on Artificial Intelligence.
  * Nemhauser et al. (1978) Nemhauser, George L, Laurence A Wolsey, Marshall L Fisher. 1978.  An analysis of approximations for maximizing submodular set functions-i.  Mathematical programming 14 265–294.
  * Tang (2021a) Tang, Shaojie. 2021a.  Beyond pointwise submodularity: Non-monotone adaptive submodular maximization in linear time.  Theoretical Computer Science 850 249–261.
  * Tang (2021b) Tang, Shaojie. 2021b.  Beyond pointwise submodularity: Non-monotone adaptive submodular maximization subject to knapsack and $k$-system constraints.  Modelling, Computation and Optimization in Information Systems and Management Sciences. Springer.
  * Tang and Yuan (2020) Tang, Shaojie, Jing Yuan. 2020.  Influence maximization with partial feedback.  Operations Research Letters 48 24–28.
  * Tang and Yuan (2021) Tang, Shaojie, Jing Yuan. 2021.  Optimal sampling gaps for adaptive submodular maximization.  arXiv preprint arXiv:2104.01750 .
  * Yuan and Tang (2017) Yuan, Jing, Shaojie Tang. 2017.  No time to observe: adaptive influence maximization with partial feedback.  Proceedings of the 26th International Joint Conference on Artificial Intelligence. 3908–3914.