  In this paper, we study the stochastic submodular maximization problem with
dependent items subject to packing constraints such as matroid and knapsack
constraints. The input of our problem is a finite set of items, and each item
is in a particular state from a set of possible states. After picking an item,
we are able to observe its state. We assume a monotone and submodular utility
function over items and states, and our objective is to select a group of items
adaptively so as to maximize the expected utility. Previous studies on
stochastic submodular maximization often assume that items' states are
independent, however, this assumption may not hold in general. This motivates
us to study the stochastic submodular maximization problem with dependent
items. We first introduce the concept of \emph{degree of independence} to
capture the degree to which one item's state is dependent on others'. Then we
propose a non-adaptive policy that approximates the optimal adaptive policy
within a factor of
$\alpha(1-e^{-\frac{\kappa}{2}+\frac{\kappa}{18m^2}}-\frac{\kappa+2}{3m\kappa})$
where the value of $\alpha$ is depending on the type of constraints, e.g.,
$\alpha=1$ for matroid constraint, $\kappa$ is the degree of independence,
e.g., $\kappa=1$ for independent items, and $m$ is the number of items. We also
analyze the adaptivity gap, i.e., the ratio of the values of best adaptive
policy and best non-adaptive policy, of our problem with prefix-closed
constraints.
