# Stochastic simultaneous optimistic optimization

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 24 references that are in the map.
- First posted on arXiv 27 Apr 2026.

## Builds on (most cited first, 1 of 1)

- [Bandit Algorithms for Tree Search](https://mlsanity.com/paper/1408.2028/) (2014)

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

- [Black-box optimization of noisy functions with unknown smoothness](https://mlsanity.com/paper/2605.02462/) (2026)
- [Optimal Regret for Single Index Bandits](https://mlsanity.com/paper/2605.09454/) (2026)
- [Bandits on graphs and structures](https://mlsanity.com/paper/2605.03493/) (2026)
- [Bandits attack function optimization](https://mlsanity.com/paper/2605.03496/) (2026)
- [Instance-dependent Stochastic Lipschitz bandit](https://mlsanity.com/paper/2605.29748/) (2026)
- [Bandits in Prod: Hyperparameter Optimization at Inference Time](https://mlsanity.com/paper/2609.01335/) (2026)
- [Canopy: Exploiting Piecewise Smooth Tree Priors for Multi-Fidelity Bandits](https://mlsanity.com/paper/2609.30017/) (2026)
- [Adaptive Partitioning Schemes for Optimistic Optimization](https://mlsanity.com/paper/2610.04039/) (2026)

## Abstract (arXiv)

We study the problem of global maximization of a function f given a finite number of evaluations perturbed by noise. We consider a very weak assumption on the function, namely that it is locally smooth (in some precise sense) with respect to some semi-metric, around one of its global maxima. Compared to previous works on bandits in general spaces (Kleinberg et al., 2008; Bubeck et al., 2011a) our algorithm does not require the knowledge of this semi-metric. Our algorithm, StoSOO, follows an optimistic strategy to iteratively construct upper confidence bounds over the hierarchical partitions of the function domain to decide which point to sample next. A finite-time analysis of StoSOO shows that it performs almost as well as the best specifically-tuned algorithms even though the local smoothness of the function is not known.