Partial-Adaptive Submodular Maximization
  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 \emph{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.
