  In this paper, the problem of maximizing a black-box function $f:\mathcal{X}
\to \mathbb{R}$ is studied in the Bayesian framework with a Gaussian Process
(GP) prior. In particular, a new algorithm for this problem is proposed, and
high probability bounds on its simple and cumulative regret are established.
The query point selection rule in most existing methods involves an exhaustive
search over an increasingly fine sequence of uniform discretizations of
$\mathcal{X}$. The proposed algorithm, in contrast, adaptively refines
$\mathcal{X}$ which leads to a lower computational complexity, particularly
when $\mathcal{X}$ is a subset of a high dimensional Euclidean space. In
addition to the computational gains, sufficient conditions are identified under
which the regret bounds of the new algorithm improve upon the known results.
Finally an extension of the algorithm to the case of contextual bandits is
proposed, and high probability bounds on the contextual regret are presented.
