Open Collections

Regret bounds for Gaussian process bandits without observation noise

University of British Columbia

This thesis presents some statistical refinements of the bandits approach presented in [11] in the situation where there is no observation noise. We give an improved bound on the cumulative regret of the samples chosen by an algorithm that is related (though not identical) to the UCB algorithm of [11] in a complementary setting. Given a function f on a domain D ⊆ R^d , sampled from a Gaussian process with an anisotropic kernel that is four times differentiable at 0, and a lattice L ⊆ D, we show that if the points in L are chosen for sampling using our branch-and-bound algorithm, the regret asymptotically decreases according to O(e^{τt/(ln t)^{d/4}}) with high probability, where t is the number of observations carried out so far and τ is a constant that depends on the objective function.

Text

2012-08-02

Attribution-NonCommercial-ShareAlike 3.0 Unported

http://hdl.handle.net/2429/42865

Computer Science

University of British Columbia

UBCV

http://creativecommons.org/licenses/by-nc-sa/3.0/