Adaptive-treed bandits

DOI10.3150/14-BEJ644zbMATH Open1364.90269arXiv1302.2489MaRDI QIDQ888482FDOQ888482

Authors: Adam D. Bull 

Publication date: 30 October 2015

Published in: Bernoulli (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1302.2489

Recommendations

• \(X\)-armed bandits
• Gaussian process bandits with adaptive discretization
• The Continuum-Armed Bandit Problem
• Contextual bandits with continuous actions: smoothing, zooming, and adapting
• Improved Rates for the Stochastic Continuum-Armed Bandit Problem

zbMATH Keywords

bandits on taxonomiescontinuum-armed banditsnoisy global optimisationtree-armed banditszooming dimension

Mathematics Subject Classification ID

Asymptotic properties of nonparametric inference (62G20) Sequential statistical design (62L05) Nonconvex programming, global optimization (90C26)

Cites Work

• Pure exploration in multi-armed bandits problems
• Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting
• \(X\)-armed bandits
• Title not available (Why is that?)
• Finite-time analysis of the multiarmed bandit problem
• Lipschitz bandits without the Lipschitz constant
• The Continuum-Armed Bandit Problem
• Regret and Convergence Bounds for a Class of Continuum-Armed Bandit Problems
• Title not available (Why is that?)
• Improved Rates for the Stochastic Continuum-Armed Bandit Problem
• Stochastic Estimation of the Maximum of a Regression Function
• Regret analysis of stochastic and nonstochastic multi-armed bandit problems
• The knowledge-gradient policy for correlated normal beliefs
• Recent approaches to global optimization problems through particle Swarm optimization

Cited In (9)

• \(X\)-armed bandits
• Filtered Poisson process bandit on a continuum
• Lipschitz bandits without the Lipschitz constant
• Contextual bandits with continuous actions: smoothing, zooming, and adapting
• Gaussian process bandits with adaptive discretization
• Stochastic continuum-armed bandits with additive models: minimax regrets and adaptive algorithm
• From bandits to Monte-Carlo tree search: the optimistic principle applied to optimization and planning
• The Continuum-Armed Bandit Problem
• Convergence rate of a simulated annealing algorithm with noisy observations

This page was built for publication: Adaptive-treed bandits

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q888482)