Independent Reading · 2011

X-Armed Bandits

Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári · Journal of Machine Learning Research

X-Armed BanditsOnline OptimizationHierarchical Search

Full text

Read the Paper

Use View PDF or Download PDF to read the full paper on this device.

Paper Information

Authors
Sébastien Bubeck, Rémi Munos, Gilles Stoltz, and Csaba Szepesvári
Venue
Journal of Machine Learning Research · 2011
Open official paper

Summary

This paper studies stochastic bandits over general measurable action spaces with local smoothness expressed through a known dissimilarity function.

Core Idea

Hierarchical optimistic optimization focuses exploration on increasingly promising regions of a potentially infinite action space.

Method

The paper introduces HOO and a computationally faster doubled variant, then proves regret bounds and minimax optimality under metric assumptions.

Key Takeaways

  • Hierarchical partitions make infinite or continuous arm spaces tractable.
  • Local smoothness near optimal actions can be sufficient for strong regret guarantees.
  • The near-optimality dimension captures problem difficulty more precisely than ambient dimension.

Questions

  • How should the hierarchy be chosen when smoothness is unknown?
  • How well do theoretical near-optimality measures predict empirical performance?