  The goal of a sequential decision making problem is to design an interactive
policy that adaptively selects a group of items, each selection is based on the
feedback from the past, in order to maximize the expected utility of selected
items. It has been shown that the utility functions of many real-world
applications are adaptive submodular. However, most of existing studies on
adaptive submodular optimization focus on the average-case. Unfortunately, a
policy that has a good average-case performance may have very poor performance
under the worst-case realization. In this study, we propose to study two
variants of adaptive submodular optimization problems, namely, worst-case
adaptive submodular maximization and robust submodular maximization. The first
problem aims to find a policy that maximizes the worst-case utility and the
latter one aims to find a policy, if any, that achieves both near optimal
average-case utility and worst-case utility simultaneously. We introduce a new
class of stochastic functions, called \emph{worst-case submodular function}.
For the worst-case adaptive submodular maximization problem subject to a
$p$-system constraint, we develop an adaptive worst-case greedy policy that
achieves a $\frac{1}{p+1}$ approximation ratio against the optimal worst-case
utility if the utility function is worst-case submodular. For the robust
adaptive submodular maximization problem subject to cardinality constraints
(resp. partition matroid constraints), if the utility function is both
worst-case submodular and adaptive submodular, we develop a hybrid adaptive
policy that achieves an approximation close to $1-e^{-\frac{1}{2}}$ (resp.
$1/3$) under both worst- and average-case settings simultaneously. We also
describe several applications of our theoretical results, including pool-base
active learning, stochastic submodular set cover and adaptive viral marketing.
