Go to  Advanced Search

Regret bounds for Gaussian process bandits without observation noise

Show full item record

Files in this item

Files Size Format Description   View
ubc_2012_fall_zoghi_masrour.pdf 604.0Kb Adobe Portable Document Format   View/Open
Title: Regret bounds for Gaussian process bandits without observation noise
Author: Zoghi, Masrour
Degree: Master of Science - MSc
Program: Computer Science
Copyright Date: 2012
Issue Date: 2012-08-02
Publisher University of British Columbia
Abstract: 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.
Affiliation: Science, Faculty of
URI: http://hdl.handle.net/2429/42865
Scholarly Level: Graduate

This item appears in the following Collection(s)

Show full item record

Attribution-NonCommercial 2.5 Canada Except where otherwise noted, this item's license is described as Attribution-NonCommercial 2.5 Canada

UBC Library
1961 East Mall
Vancouver, B.C.
Canada V6T 1Z1
Tel: 604-822-6375
Fax: 604-822-3893