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
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?