Stochastic simultaneous optimistic optimization

Michal Valko · A Carpentier · Rémi Munos

72 citations0/0 files storedarXiv (Cornell University)

No readable copy stored yet — this record is metadata only.

No open-access location is known for this record yet.

Literature note Cite in a project Citation map

Advanced Bandit Algorithms Research Simulation Techniques and Applications Optimization and Search Problems

Abstract

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.

Paper brief

Loading…

Cite this work

Citation unavailable for this work.

BibTeX RIS CSL-JSON

No public copy is stored for this record, so only the metadata is cited.

Citations in this library

Citation map →

Stored only when both papers are in the corpus — 72 citations exist upstream.

References

2002Finite-time Analysis of the Multiarmed Bandit Problem 2012Information-Theoretic Regret Bounds for Gaussian Process Optimization in the Bandit Setting 2011Convergence rates of efficient global optimization algorithms 2009Pure Exploration in Multi-armed Bandits Problems 2008Multi-armed bandits in metric spaces 2011X -Armed Bandits 2014Bandit Algorithms for Tree Search 2011Optimistic Optimization of a Deterministic Function without the Knowledge of its Smoothness

Cited by

2013Relative Upper Confidence Bound for the K-Armed Dueling Bandit Problem 2014Online Stochastic Optimization under Correlated Bandit Feedback 2026Black-box optimization of noisy functions with unknown smoothness

Explore the map →

Papers that cite the same references — the relational fallback while embeddings are still backfilling.

Imported from OpenAlex (CC0) — nothing here is generated.