Maximizing Stochastic Monotone Submodular Functions

We study the problem of maximizing a stochastic monotone submodular function with respect to a matroid constraint. We study the adaptivity gap – the ratio between the values of optimal adaptive and non-adaptive policies – and show that it is equal to e/(e-1) . This result implies that the benefit of adaptivity is bounded. We also study the myopic policy and show that it is a (1/2)-approximation. Furthermore, when the matroid is uniform, approximation ratio of the myopic policy becomes 1-(1/e) which is optimum.