  In this paper, we analyze a generic algorithm scheme for sequential global
optimization using Gaussian processes. The upper bounds we derive on the
cumulative regret for this generic algorithm improve by an exponential factor
the previously known bounds for algorithms like GP-UCB. We also introduce the
novel Gaussian Process Mutual Information algorithm (GP-MI), which
significantly improves further these upper bounds for the cumulative regret. We
confirm the efficiency of this algorithm on synthetic and real tasks against
the natural competitor, GP-UCB, and also the Expected Improvement heuristic.
