  Constrained submodular maximization has been extensively studied in the
recent years. In this paper, we study adaptive robust optimization with nearly
submodular structure (ARONSS). Our objective is to randomly select a subset of
items that maximizes the worst-case value of several reward functions
simultaneously. Our work differs from existing studies in two ways: (1) we
study the robust optimization problem under the adaptive setting, i.e., one
needs to adaptively select items based on the feedback collected from picked
items, and (2) our results apply to a broad range of reward functions
characterized by $\epsilon$-nearly submodular function. We first analyze the
adaptvity gap of ARONSS and show that the gap between the best adaptive
solution and the best non-adaptive solution is bounded. Then we propose a
approximate solution to this problem when all reward functions are submodular.
Our algorithm achieves approximation ratio $(1-1/e)$ when considering matroid
constraint. At last, we present two heuristics for the general case. All
proposed solutions are non-adaptive which are easy to implement.
