# Adaptive-treed bandits

arXiv: https://arxiv.org/abs/1302.2489 · HTML: https://mlsanity.com/paper/1302.2489/

## Key facts

- Cited by 6 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Feb 2013.

## Built on by (most cited first, 6 of 6)

- [Improving LLM-based Global Optimization with Search Space Partitioning](https://mlsanity.com/paper/2505.21372/) (2025)
- [Black-box optimization of noisy functions with unknown smoothness](https://mlsanity.com/paper/2605.02462/) (2026)
- [Efficient Sampling in POMDPs with Lipschitz Bandits for Motion Planning in Continuous Spaces](https://mlsanity.com/paper/2106.04206/) (2021)
- [Variational Quantum Optimization with Continuous Bandits](https://mlsanity.com/paper/2502.04021/) (2025)
- [Optimal Stochastic Nonconvex Optimization with Bandit Feedback](https://mlsanity.com/paper/2103.16082/) (2021)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)

## Abstract (arXiv)

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.