Adaptive-treed bandits
arXiv:1302.2489 · doi:10.3150/14-BEJ644
Abstract
We describe a novel algorithm for noisy global optimisation and continuum-armed bandits, with good convergence properties over any continuous reward function having finitely many polynomial maxima. Over such functions, our algorithm achieves square-root regret in bandits, and inverse-square-root error in optimisation, without prior information. Our algorithm works by reducing these problems to tree-armed bandits, and we also provide new results in this setting. We show it is possible to adaptively combine multiple trees so as to minimise the regret, and also give near-matching lower bounds on the regret in terms of the zooming dimension.
arXiv commentPublished at http://dx.doi.org/10.3150/14-BEJ644 in the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)
References in corpus (2)
Cited by in corpus (9)
- Black-box optimization of noisy functions with unknown smoothness
- Convergence rate of a simulated annealing algorithm with noisy observations
- Adaptive Contract Design for Crowdsourcing Markets: Bandit Algorithms for Repeated Principal-Agent Problems
- Active Learning for Binary Classification with Abstention
- Polynomial Cost of Adaptation for X -Armed Bandits
- On Regret with Multiple Best Arms
- Adaptive Discretization against an Adversary: Lipschitz bandits, Dynamic Pricing, and Auction Tuning
- A Parallel algorithm for -Armed bandits
- Optimal Stochastic Nonconvex Optimization with Bandit Feedback