Sign in
Author

Conference

Journal

Organization

Year

DOI
Look for results that meet for the following criteria:
since
equal to
before
between
and
Search in all fields of study
Limit my searches in the following fields of study
Agriculture Science
Arts & Humanities
Biology
Chemistry
Computer Science
Economics & Business
Engineering
Environmental Sciences
Geosciences
Material Science
Mathematics
Medicine
Physics
Social Science
Multidisciplinary
Keywords
(5)
Euclidean Space
Large Classes
Rate of Growth
Science Learning
Decision Maker
Subscribe
Academic
Publications
XArmed Bandits
XArmed Bandits,Computing Research Repository,Sébastien Bubeck,Rémi Munos,Gilles Stoltz,Csaba Szepesvari
Edit
XArmed Bandits
(
Citations: 1
)
BibTex

RIS

RefWorks
Download
Sébastien Bubeck
,
Rémi Munos
,
Gilles Stoltz
,
Csaba Szepesvari
We consider a generalization of stochastic bandits where the set of arms, $\cX$, is allowed to be a generic measurable space and the meanpayoff function is "locally Lipschitz" with respect to a dissimilarity function that is known to the decision maker. Under this condition we construct an arm selection policy, called HOO hierarchical optimistic optimization), with improved regret bounds compared to previous results for a large class of problems. In particular, our results imply that if $\cX$ is the unit hypercube in a
Euclidean space
and the meanpayoff function has a finite number of global maxima around which the behavior of the function is locally H\"older continuous with a known exponent, then the expected of HOO regret is bounded up to a logarithmic factor by $\sqrt{n}$, i.e., the
rate of growth
of the regret is independent of the dimension of the space. We also prove the minimax optimality of our algorithm when the dissimilarity is a metric.
Journal:
Computing Research Repository  CORR
, vol. abs/1001.4, 2010
Cumulative
Annual
View Publication
The following links allow you to view full publications. These links are maintained by other sources not affiliated with Microsoft Academic Search.
(
adsabs.harvard.edu
)
(
www.informatik.unitrier.de
)
(
arxiv.org
)
References
(23)
Competing in the Dark: An Efficient Algorithm for Bandit Linear Optimization
(
Citations: 22
)
Jacob Abernethy
,
Elad Hazan
,
Alexander Rakhlin
Conference:
Computational Learning Theory  COLT
, pp. 263274, 2008
The ContinuumArmed Bandit Problem
(
Citations: 33
)
Rajeev Agrawal
Journal:
Siam Journal on Control and Optimization  SIAM J CONTR OPTIMIZAT
, vol. 33, no. 6, 1995
Finitetime Analysis of the Multiarmed Bandit Problem
(
Citations: 277
)
Peter Auer
,
Nicolò Cesabianchi
,
Paul Fischer
Journal:
Machine Learning  ML
, vol. 47, no. 23, pp. 235256, 2002
The nonstochastic multiarmed bandit problem
(
Citations: 56
)
Peter Auer
,
Yoav Freund
,
Robert E. Schapire
Journal:
Siam Journal on Computing  SIAMCOMP
Improved Rates for the Stochastic ContinuumArmed Bandit Problem
(
Citations: 16
)
Peter Auer
,
Ronald Ortner
,
Cs. Szepesv'ari
Conference:
Computational Learning Theory  COLT
, pp. 454468, 2007
Sort by:
Citations
(1)
Convergence rates of efficient global optimization algorithms
(
Citations: 1
)
Adam D. Bull
Published in 2011.